M4-037M4: Sequences & TransformersAttention Variants (MHA / MQA / GQA)Medium
⚡Flashcard Drill➔Mastery:

Sparse Attention Mechanisms and Sliding Window Attention (SWA)

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M4-038 →
📐 Mathematical Definition
sliding window: Attni=softmax(QiKi−w:i⊤)Vi−w:i;cost=O(Lw)\text{sliding window}:\ \text{Attn}_{i}=\mathrm{softmax}(Q_iK_{i-w:i}^{\top})V_{i-w:i};\qquad \text{cost}=O(Lw)
⚡ One-Sentence Core Answer
Sparse attention restricts tokens to attending to local sliding windows, dilated strides, or global anchor tokens, cutting O(N2)O(N^2) complexity to O(N⋅W)O(N \cdot W) linear time.

📌 Key Takeaways

  • •
    Sliding Window Attention (SWA / Mistral): token ii attends only to tokens within [i−W,i][i - W, i]; reduces complexity from O(N2)O(N^2) to O(N⋅W)O(N \cdot W)
  • •
    Receptive field accumulation: stacking LL layers expands effective receptive field to L×WL \times W through recursive multi-hop information routing
  • •
    Global tokens: BigBird and Longformer add full bidirectional attention to special anchor tokens (e.g., [CLS]) to bridge global context

📐 Mathematical Derivations

Mathematical Formulations:
① Sliding Window Attention (Beltagy et al., Longformer; Jiang et al., Mistral 7B):
Let window size be WW. Attention mask is defined as:
MSWA[i,j]={0if 0≤i−j≤W−∞otherwiseM_{\text{SWA}}[i, j] = \begin{cases} 0 & \text{if } 0 \le i - j \le W \\ -\infty & \text{otherwise} \end{cases}.
- Complexity: Memory and FLOPs scale as O(N⋅W)O(N \cdot W), strictly linear in sequence length NN.
- Theoretical Multi-Hop Receptive Field:
At layer 1, token ii sees [i−W,i][i - W, i].
At layer 2, tokens inside [i−W,i][i - W, i] have already attended to their own predecessors up to i−2Wi - 2W.
After LL stacked Transformer layers, the effective theoretical receptive field expands to: RFL=L×W\text{RF}_L = L \times W.
For Mistral (L=32,W=4096L=32, W=4096), the theoretical receptive field covers 32×4096=131,07232 \times 4096 = 131,072 tokens!
② Rolling Buffer KV Cache:
During inference, cache size is capped at WW. Position ii overwrites position i(modW)i \pmod W in circular buffers, capping VRAM memory permanently.

🏭 Production Trade-offs

GPU Hardware Reality: Irregular or dynamic sparsity patterns achieve zero hardware speedup on GPUs due to non-coalesced memory access. Sliding Window Attention succeeds because fixed, regular band-diagonal matrices are easily accelerated via custom FlashAttention kernels.
⚠️ Common Interview Pitfalls
  • ✕
    Using pure Sliding Window Attention without global tokens or interleaved full-attention layers on retrieval tasks, causing complete loss of long-range single-hop recall
  • ✕
    Confusing theoretical multi-hop receptive field (L×WL \times W) with effective single-hop attention capability
🎯 Interviewer Follow-up Inquiries
  • ?
    How does Mistral's Rolling Buffer Cache cap inference KV-cache memory to a fixed window size WW?
  • ?
    Why do arbitrary graph-based sparse attention patterns fail to accelerate execution on modern GPU architectures?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM4-036: Multi-Head Latent Attention (MLA): DeepSeek's Low-Rank KV Cache Compression📋 Back to BankNext →M4-038: Linear Attention and Kernel Methods: Associative Matrix Multiplication and O(N) Complexity