Sparse attention

On this page 7

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.

ApproachScore computationsTypical setting
Dense self-attentionn squaredShort and medium contexts
Sliding windown times ww between 512 and 4,096 tokens
Strided factorized patternAbout n times the square root of nImages, audio and long text
Top-k selectionn times k, plus selection costk of a few hundred to a few thousand
Hashing or clusteringAbout n log nVery long sequences
Computational cost per layer

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.

PatternWhich keys a query seesKnown example
Local windowTokens within a fixed distanceSliding window layers in Longformer and Mistral 7B
Strided or dilatedEvery s-th earlier tokenSparse Transformer
Global tokensA few designated tokens that see and are seen by allLongformer, BigBird
Random linksA small random set of keysBigBird
Block-sparseSelected blocks of contiguous tokensBlock-sparse GPU kernels
Content-basedKeys chosen by hashing, clustering or scoringReformer, Routing Transformer, DeepSeek Sparse Attention
Common sparse attention patterns

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 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.

TechniqueHow it saves costExact softmax over chosen keys
Sparse attentionComputes scores for a subset of pairsYes
Linear attentionReplaces softmax with a kernel feature mapNo
Sliding window attentionA specific local sparse patternYes
Grouped-query attentionShares key and value heads to shrink the cacheYes, over all keys
Multi-head latent attentionCompresses keys and values into a latent vectorYes, over all keys
FlashAttentionReorders dense attention to reduce memory trafficYes, over all keys
How sparse attention differs from neighboring techniques

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.

SituationRecommended patternReason
Long documents with local structureWindow plus global tokensCaptures nearby context and document-level summary
Retrieval of facts far back in contextContent-based top-k selectionReaches relevant tokens regardless of distance
Images or audio as long sequencesStrided or block patternsMatches the grid or periodic structure
Throughput-critical servingBlock-sparse with hardware-aligned blocksKeeps GPU tensor cores busy
Short contexts under a few thousand tokensDense attentionSparsity overhead outweighs savings
Decision guide for typical workloads

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.