Sliding Window Attention

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. The Local Window Formulation
5. Effective Receptive Field
6. Dilated Sliding Window
7. Global + Local Hybrid (Longformer)
8. Alternating Window Patterns (Mistral)
9. Memory and Compute Analysis
10. Comparison with Full Attention
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Derive the sliding window attention mask and its complexity.
2. Prove the effective receptive field grows linearly with depth.
3. Explain how dilated windows extend the receptive field without extra compute.
4. Describe the Longformer hybrid pattern combining local, global, and sliding attention.
5. Analyze when sliding window is preferable to full attention.

Notation

• $w$ — window size (number of tokens each position attends to)
• $L$ — number of layers
• $d$ — dilation factor
• $T$ — sequence length
• $\mathbf{M}_w$ — sliding window mask

Core Intuition

Most information in natural language is local: a word's meaning depends primarily on its neighbors. Full $O(T^2)$ attention is overkill for most positions — distant tokens contribute negligibly to the softmax distribution. Sliding window attention exploits this locality by restricting each token to attend only within a fixed window, achieving linear complexity in sequence length.

The Local Window Formulation

Each token at position $i$ attends to positions in the window $[i - w/2, i + w/2]$:

where $s_{ij} = \mathbf{q}_i^T\mathbf{k}_j/\sqrt{d_k}$.

Mask matrix: The window mask $\mathbf{M}_w$ is a banded matrix:

Applied as: $\mathbf{A} = \text{softmax}(\mathbf{QK}^T/\sqrt{d_k} + \mathbf{M}_w)$.

For causal models: The window is one-sided: position $i$ attends to $[i-w+1, i]$.

Effective Receptive Field

Theorem. After $L$ layers of sliding window attention with window $w$, position $t$ can be influenced by any position in $[t - Lw, t]$ (causal case).

Proof. At layer 1, position $t$ sees positions $[t-w+1, t]$. At layer 2, each of those positions has already incorporated information from their own window at layer 1. Position $t-w+1$ at layer 1 saw positions $[t-2w+2, t-w+1]$. Thus after 2 layers, position $t$ is influenced by $[t-2w+2, t]$. By induction, after $L$ layers: $[t-Lw+L, t] \approx [t-Lw, t]$. $\blacksquare$

Example: Mistral with $w=4096$ and $L=32$: effective receptive field = $32 \times 4096 = 131{,}072$ tokens — sufficient for 128K contexts even with local attention.

Important caveat: While information can propagate $Lw$ positions, the signal attenuates exponentially with distance (each hop through a residual connection adds noise).

Dilated Sliding Window

Instead of attending to consecutive neighbors, skip every $d$ positions:

Receptive field per layer: $w \times d$ positions (covers a wider range with the same number of attended tokens).

Multi-head dilation: Different heads use different dilation factors:

• Head 1: $d=1$ (local)
• Head 2: $d=2$ (skip one)
• Head 4: $d=4$ (skip three)

This gives each layer access to both fine-grained local and coarse-grained distant information.

Global + Local Hybrid (Longformer)

Architecture: Combine three attention patterns:

1. Sliding window (all tokens): Local context, $O(Tw)$ complexity.
2. Global tokens (selected positions): Attend to/from all positions. Typically: [CLS] token, question tokens, or every $k$-th position.
3. Random attention (optional): Attend to a few random positions for diversity.

Formulation for token $i$:

Complexity: $O(T \cdot (w + |\mathcal{G}|))$ — linear in $T$ if $|\mathcal{G}|$ is fixed.

Use cases: Document classification (global = [CLS]), QA (global = question tokens).

Alternating Window Patterns (Mistral)

Mistral's approach: Use sliding window attention in every layer, but the effective context comes from stacking layers:

• Every layer: causal sliding window of size $w=4096$.
• No global tokens, no dilated attention.
• Effective context: $L \times w = 32 \times 4096 = 128K$.

KV-cache optimization: Only need to cache $w$ tokens per layer (older tokens are evicted). Fixed KV-cache size regardless of sequence length:

Comparison with Llama: Llama uses full attention (KV-cache grows with $T$). Mistral's sliding window gives constant memory but relies on information propagation through layers.

Memory and Compute Analysis

Standard attention: $O(T^2 d)$ compute, $O(T^2)$ memory.

Sliding window: $O(Twd)$ compute, $O(Tw)$ memory.

Speedup factor: $T/w$. For $T=128K, w=4096$: $32\times$ faster attention.

Implementation: Can be implemented as a block-sparse matrix multiply, or via FlashAttention with masking (FlashAttention-2 supports arbitrary causal masks including sliding window).

Comparison with Full Attention

• Quality at short context ($T < w$): Identical (window covers everything).
• Quality at long context ($T \gg w$): Sliding window loses direct access to distant tokens. Quality depends on task:
  • Summarization, local understanding: minimal degradation.
  • Fact retrieval from specific distant position: significant degradation.
  • Reasoning chains: moderate (info propagates through layers).

Empirical finding: For most language modeling tasks, sliding window with $w=4096$ and 32 layers achieves comparable perplexity to full attention, at dramatically lower cost.

Common Pitfalls

Pitfall 1. Setting window too small. With $w=512$ and $L=12$: effective context is only $6144$ tokens. For long-document tasks, this is insufficient.

Pitfall 2. Forgetting that information must traverse multiple layers. A token at distance $Lw$ influences position $t$ only through a chain of $L$ intermediate representations — the signal is heavily processed and potentially distorted.

Pitfall 3. Applying sliding window to cross-attention. In encoder-decoder models, the decoder should typically attend to the full encoder output, not a window (the "relevant" encoder positions aren't necessarily nearby).

Summary

• Sliding window restricts attention to $w$ nearest tokens: $O(Tw)$ complexity.
• Effective receptive field = $L \times w$ across layers.
• Dilated windows extend range without additional compute.
• Longformer adds global tokens for long-range connections.
• Mistral uses pure sliding window with layer stacking for 128K context.
• Fixed KV-cache size ($Lw$) regardless of sequence length.

Exercises

Exercise 1. For $T=65536, w=4096, L=32$: compute the sliding window attention FLOPs and compare to full attention FLOPs.

Exercise 2. Prove that the effective receptive field after $L$ layers of dilated attention with dilation $d$ and window $w$ is $Lwd$.

Exercise 3. Design a hybrid attention pattern for a 32-layer model processing 100K tokens: specify which layers use sliding window, which use full attention, and justify your choices.

Exercise 4. Compute the maximum KV-cache memory for Mistral ($w=4096, L=32, d_k=128, G=8$) in FP16, and compare to Llama at $T=32768$.

Exercise 5. Explain why simply increasing $w$ to equal $T$ doesn't recover full attention performance if the model was trained with small $w$.