Sparse attention is a family of attention mechanisms in which each query token computes scores against only a selected subset of key positions instead of every position in the sequence. In Neural networks built on the transformer, it reduces the quadratic cost of full self-attention toward linear or near-linear cost, which makes long contexts of tens or hundreds of thousands of tokens practical.
The subset is defined either by a fixed pattern, such as a local window or strided positions, or by a learned or content-based selection that picks the most relevant tokens at run time. The result is still softmax attention, but computed over a sparse attention mask rather than a dense one.
How sparse attention restricts the attention matrix
Full self-attention compares every query with every key, producing an n by n score matrix for a sequence of n tokens. Memory and compute therefore grow with n squared: doubling the context quadruples the work. Sparse attention keeps the same query, key and value projections but evaluates only the entries allowed by a mask, and the softmax is normalized over that allowed set.
The design goal is to preserve information flow across the whole sequence while computing far fewer scores. Even if one layer connects a token only to nearby positions, stacking layers widens the effective receptive field, and a few global or strided connections let distant tokens exchange information in two or three hops.
The table below compares the cost of the main approaches, where n is sequence length, w is window size and k is the number of selected tokens.
| Approach | Score computations | Typical setting |
|---|---|---|
| Dense self-attention | n squared | Short and medium contexts |
| Sliding window | n times w | w between 512 and 4,096 tokens |
| Strided factorized pattern | About n times the square root of n | Images, audio and long text |
| Top-k selection | n times k, plus selection cost | k of a few hundred to a few thousand |
| Hashing or clustering | About n log n | Very long sequences |
Main sparsity patterns
Sparsity patterns fall into fixed patterns, which are decided before training, and adaptive patterns, which depend on the content of each input. Many production models combine several patterns in one layer or alternate them across layers.
| Pattern | Which keys a query sees | Known example |
|---|---|---|
| Local window | Tokens within a fixed distance | Sliding window layers in Longformer and Mistral 7B |
| Strided or dilated | Every s-th earlier token | Sparse Transformer |
| Global tokens | A few designated tokens that see and are seen by all | Longformer, BigBird |
| Random links | A small random set of keys | BigBird |
| Block-sparse | Selected blocks of contiguous tokens | Block-sparse GPU kernels |
| Content-based | Keys chosen by hashing, clustering or scoring | Reformer, Routing Transformer, DeepSeek Sparse Attention |
Content-based methods first run a cheap selection step, such as locality-sensitive hashing, k-means routing or a lightweight indexer that scores tokens, and then apply full-precision attention only to the winners. Native sparse attention designs train this selection end to end together with the model, which avoids the accuracy loss of adding sparsity after training.
Sparse attention compared with related attention variants
Sparse attention is one of several answers to the long-context bottleneck, and it is often confused with techniques that reduce cost in different ways. The key distinction is that sparse attention skips most query and key pairs, while other variants approximate, compress or reorganize the same computation.
| Technique | How it saves cost | Exact softmax over chosen keys |
|---|---|---|
| Sparse attention | Computes scores for a subset of pairs | Yes |
| Linear attention | Replaces softmax with a kernel feature map | No |
| Sliding window attention | A specific local sparse pattern | Yes |
| Grouped-query attention | Shares key and value heads to shrink the cache | Yes, over all keys |
| Multi-head latent attention | Compresses keys and values into a latent vector | Yes, over all keys |
| FlashAttention | Reorders dense attention to reduce memory traffic | Yes, over all keys |
These techniques are complementary rather than competing. A model can use grouped-query attention to shrink the key-value cache, block-sparse kernels in the FlashAttention style for speed, and a sparse pattern to limit the number of keys each query reads. State space models such as Mamba take a different route by removing attention altogether in some layers.
Choosing and configuring a sparse pattern
The right pattern depends on where the relevant information lies in the data and on the hardware that will run the model. Local patterns fit data with strong locality, while retrieval-style tasks over long documents need some route to distant, content-relevant tokens.
| Situation | Recommended pattern | Reason |
|---|---|---|
| Long documents with local structure | Window plus global tokens | Captures nearby context and document-level summary |
| Retrieval of facts far back in context | Content-based top-k selection | Reaches relevant tokens regardless of distance |
| Images or audio as long sequences | Strided or block patterns | Matches the grid or periodic structure |
| Throughput-critical serving | Block-sparse with hardware-aligned blocks | Keeps GPU tensor cores busy |
| Short contexts under a few thousand tokens | Dense attention | Sparsity overhead outweighs savings |
Configuration choices include window size, block size, number of global tokens and the top-k budget. A common practice is to keep a few dense layers, or to alternate dense and sparse layers, so that the model retains at least some unrestricted global mixing.
Limitations and common mistakes
The central trade-off of sparse attention is efficiency against recall: every skipped pair is a connection the model cannot use directly. Fixed patterns can miss a crucial token outside the window, and adaptive patterns can select the wrong tokens when the selection step is too crude.
- Theoretical savings that do not appear in practice: irregular masks map poorly to GPUs, so wall-clock speedups can be far smaller than the reduction in operations.
- Retrofitting sparsity after dense pretraining: imposing a mask on a dense model usually degrades quality unless the model is further trained with it.
- Weak long-range retrieval: purely local patterns often fail needle-in-a-haystack style tests despite good perplexity.
- Ignoring the key-value cache: sparse computation does not automatically shrink cache memory if all keys must still be stored.
- Selection cost blind spots: an indexer that scores every token still has quadratic components, although with a much smaller constant.
Theoretical work on BigBird showed that patterns combining window, global and random links can preserve the expressive power of full attention, but such results do not guarantee equal accuracy on every task, so empirical long-context evaluation remains essential.
The simple explanation
Imagine a meeting where every participant must listen to every other participant before speaking. With ten people this works, but with ten thousand it becomes impossible. Sparse attention lets each word in a text listen only to the words most likely to matter, such as its neighbors and a few important ones.
The model does much less work and can read far longer texts. The price is a small risk that it overlooks something important it was not set up to notice.
How it is used in practice
A legal technology team builds an assistant that answers questions about contracts of about 120,000 tokens. With dense attention, each layer would compute roughly 14 billion query and key scores per document, which makes serving slow and expensive on their GPUs.
The team chooses a model that combines a 4,096-token sliding window with a learned top-k selector that picks about 2,000 relevant tokens for each query. Attention work per layer falls by more than an order of magnitude, and response latency drops substantially. Before deployment the team runs a retrieval test that hides clauses deep inside long contracts, confirming that the selector still finds them, and keeps a dense fallback model for the rare cases where answers appear incomplete.