Sparse Attention
An attention variant that computes scores only for a subset of token pairs instead of every query-key combination.
Sparse attention is an attention variant that computes scores only for selected token pairs, trading full connectivity for lower cost on long contexts.
At a glance
Released
April 2019
Authors
Rewon Child, Scott Gray, Alec Radford, et al.
Optimizes
- Attention Compute
- Memory Bandwidth
- Long Context Inference
What It Is
Sparse attention is an attention variant that restricts which query-key pairs participate in the softmax. Instead of a full n-by-n attention matrix, only entries allowed by a sparsity pattern receive non-zero weight.Why It Exists
Sparse attention targets attention compute, memory bandwidth for score materialization, and the cost of serving long sequences when dense all-pairs attention would dominate runtime.How It Works
Each query position attends only to keys permitted by a sparsity mask or fixed pattern. Disallowed pairs are zeroed before softmax normalization, so the model spends compute on selected connections rather than the full token grid.q_tKV_0KV_1\cdotsKV_{t-3}KV_{t-2}KV_{t-1}q_t to KV_0q_t to KV_{t-3}q_t to KV_{t-1}
Math Or Compute Schema
With sequence length n and sparsity mask M, sparse attention applies M to the score matrix before softmax. The formulas below contrast dense multi-head attention against masked sparse attention that limits which pairs receive weight.Compared To Nearby Modules
Compared with multi-head attention, sparse attention skips most token pairs rather than scoring all of them. Multi-query and grouped-query attention remain dense over allowed positions but reduce key-value head count. Sparse attention instead changes which positions connect at all.| Comparison dimension | Sparse Attention | Multi-Head Attention | Multi-Query Attention | Grouped-Query Attention |
|---|---|---|---|---|
| Attention connectivity | Mask-limited subset of query-key pairs | All n-by-n query-key pairs per head | All n-by-n pairs with shared key-value heads | All n-by-n pairs with grouped key-value heads |
| Compute scaling with sequence length | Subquadratic when sparsity fraction is fixed | Quadratic O(n²) per head | Quadratic O(n²) with fewer key-value projections | Quadratic O(n²) with reduced key-value head count |
| Global token reach | Depends on sparsity pattern; often local or block-structured | Any position can attend to any other position | Any position can attend to any other position | Any position can attend to any other position |