sparse attention
**Sparse Attention** is the **family of attention mechanism variants that restrict the full N×N attention matrix to a sparse pattern** — reducing the quadratic O(N²) time and memory complexity of standard self-attention to O(N√N), O(N log N), or O(N), enabling transformer models to process much longer sequences than would be feasible with dense attention while retaining most of the representational power.
**Why Sparse Attention?**
- Standard attention: Every token attends to every other token → O(N²) compute and memory.
- N = 4096: ~17M attention entries per head per layer. Manageable.
- N = 100K: ~10B entries. Expensive but doable with FlashAttention.
- N = 1M: ~1T entries. Impossible with dense attention → sparse patterns essential.
**Sparse Attention Patterns**
| Pattern | What Tokens Attend To | Complexity | Example |
|---------|----------------------|-----------|--------|
| Sliding Window | W nearest neighbors | O(N×W) | Mistral, Longformer (local) |
| Dilated | Every k-th token within window | O(N×W/k) | Longformer (dilated) |
| Global + Local | Some tokens attend globally, rest locally | O(N×(W+G)) | Longformer, BigBird |
| Strided | Fixed stride pattern (blockwise) | O(N√N) | Sparse Transformer (Strided) |
| Random | Randomly selected tokens | O(N×R) | BigBird (random component) |
| Block Sparse | Dense attention within blocks | O(N×B) | Block-sparse attention |
**Sliding Window Attention (Mistral/Mistral-style)**
- Each token attends to only the W previous tokens (e.g., W=4096).
- Effectively: Local context window that slides with the sequence.
- With L stacked layers: Effective receptive field = L × W tokens.
- Mistral: 32 layers × 4096 window = 131K effective context.
- **KV cache bounded**: Only need to cache W tokens → constant memory regardless of sequence length.
**Longformer (Beltagy et al., 2020)**
- Combines three patterns:
1. **Local (sliding window)**: Every token attends to W neighbors.
2. **Dilated**: Attend to tokens spaced k apart → larger receptive field.
3. **Global**: Designated tokens (e.g., [CLS]) attend to all tokens.
- Complexity: O(N × W) instead of O(N²) → handles documents up to 16K+ tokens.
**BigBird (Zaheer et al., 2020)**
- **Random + Local + Global** attention:
- Random: Each token attends to R random tokens → captures long-range dependencies.
- Local: Sliding window of W neighbors → local context.
- Global: G special tokens attend to all → aggregate global information.
- Theoretically: Random attention makes the graph an expander → provably approximates full attention.
**Linear Attention**
- Replace softmax(QKᵀ)V with φ(Q)φ(K)ᵀV → kernelized attention.
- Rearrange: φ(Q)(φ(K)ᵀV) → compute KᵀV first (d×d matrix) → O(Nd²) instead of O(N²d).
- If d << N → linear in N.
- Challenge: Quality gap vs. softmax attention — linear approximation loses sharpness.
**Modern Hybrid Approaches**
- **Mistral/Mixtral**: Sliding window + GQA → efficient long-context.
- **Gemini**: Hybrid with full attention at certain layers, sparse at others.
- **Ring Attention**: Distribute sequence across devices, overlap communication with attention compute.
Sparse attention is **the enabling architecture for long-context transformers** — by intelligently selecting which token pairs to compute attention for, these methods extend the practical reach of transformers from thousands to millions of tokens while preserving the ability to capture the long-range dependencies that make attention powerful.