Context windows have grown from a few thousand tokens to hundreds of thousands, and in some models to millions. That growth was not free. The core operation of a transformer, attention, gets expensive quickly as inputs get longer, and a large body of research has gone into making it cheaper. Sparse attention is one of the main families of techniques.
This explainer covers why standard attention scales badly, the three core ideas behind sparse attention (local windows, global tokens and block or learned sparsity), the papers that introduced them, and what the trade-offs mean if you are choosing or using a long-context model.
Why full attention is expensive
In standard ("dense" or "full") self-attention, every token computes a relevance score with every other token in the sequence. For a sequence of length *n*, that is *n × n* scores per attention head, per layer.
- Double the input length and the attention computation roughly quadruples.
- A 4,000-token input needs about 16 million pairwise scores per head per layer; a 128,000-token input needs about 16 billion.
Memory-efficient kernels such as FlashAttention (Dao et al., 2022) changed the picture a lot by computing exact attention without materialising the full score matrix, reducing memory use and making long contexts far more practical. But the amount of computation is still quadratic. Sparse attention attacks the computation itself by deciding that most token pairs do not need to be scored at all.
Idea 1: local (sliding window) attention
The simplest observation is that most of the information a token needs is nearby. In local attention, each token attends only to a fixed window of neighbouring tokens, for example the previous 4,096.
Cost becomes linear in sequence length: *n × w* instead of *n × n*, where *w* is the window size. Because layers are stacked, information can still travel further than one window: in a model with *L* layers, a token's effective receptive field can reach about *L × w* tokens, the same way stacked convolutions see further than one filter.
Sliding window attention appears in Longformer (Beltagy et al., 2020) and was used in Mistral 7B (2023), which combined it with a rolling key-value cache to reduce memory during generation.
Trade-off: distant information must hop through many layers to arrive, and each hop can lose detail. Tasks that need precise links between far-apart tokens, such as matching a definition on page 1 to a use on page 90, suffer most.
Idea 2: global tokens
Global attention adds a small number of special positions that attend to everything and are attended to by everything. They act as hubs: any two tokens can exchange information in two steps through a global token.
Longformer let task designers mark specific tokens as global (for example, the question tokens in question answering). BigBird (Zaheer et al., 2020) combined three patterns: a sliding window, a few global tokens and some random connections, and showed that this combination preserves important theoretical properties of full attention while staying linear in cost.
Trade-off: a handful of hubs is a bottleneck. Squeezing a whole document's relationships through a few tokens compresses information.
Idea 3: block and strided sparsity
The Sparse Transformer (Child et al., 2019) introduced fixed patterns in which tokens attend to their local block plus every *k*-th earlier token (a stride). Different heads use different patterns so that, together, they cover the sequence. Block-sparse layouts are also friendlier to GPU hardware, which prefers dense chunks to scattered individual entries.
More recent work learns or selects which blocks to attend to based on content: the model first computes a cheap summary of each block, then attends in full only to the most relevant blocks. This "dynamic" or "native" sparse attention aims to keep the efficiency of fixed patterns while letting the model decide where to look.
The patterns compared
| Pattern | Cost vs. length | Strength | Weakness |
|---|---|---|---|
| Full (dense) attention | Quadratic | Exact, any-to-any links | Expensive at long lengths |
| Sliding window | Linear | Simple, great for local structure | Distant links need many layers |
| Window + global tokens | Linear | Hubs connect distant parts | Hubs compress information |
| Strided / block patterns | Sub-quadratic | Hardware-friendly, broad coverage | Fixed pattern may miss content |
| Learned or dynamic blocks | Sub-quadratic | Attends where content is relevant | More complex, harder to train |
Many production models mix approaches, for example alternating local-attention layers with full-attention layers, so that cheap layers handle local structure and occasional dense layers keep long-range precision.
Sparse attention during generation
The discussion above is mostly about reading a long input. Generating output has a separate cost: the key-value (KV) cache. During generation, the model stores the keys and values for every previous token so it does not recompute them. With dense attention, this cache grows linearly with the sequence length and, at long contexts, can use more GPU memory than the model weights themselves.
Sparse patterns help here too. With a sliding window, tokens outside the window are never attended to again, so their cache entries can be discarded, which is the idea behind the rolling buffer cache used with Mistral 7B. Other techniques shrink the cache without sparsity: grouped-query attention shares keys and values across several heads, and cache quantization stores them at lower precision.
These details matter to you as a user because KV-cache memory is a large part of why long-context requests are slower and more expensive to serve, and why providers often price long inputs differently from short ones.
What this means for people using long-context models
You usually cannot see the attention pattern of a closed model, but the trade-offs show up in behaviour.
- A large context window is not uniform recall. Models may handle information near the start and end of the input better than the middle. We cover how to test this in why long context still forgets the middle.
- "Fits in the window" does not mean "used well." Retrieval that puts the most relevant passages near the question often beats stuffing everything in. See context windows are not memory.
- Long inputs cost more even with efficient attention. You pay per input token, and time-to-first-token grows with input length.
- Test with your own documents. Synthetic "needle in a haystack" tests are easy to pass; tasks that need several facts combined across distant sections are much harder.
Sparse attention is one of several efficiency ideas in modern models. Mixture of experts reduces the compute per token in the feed-forward layers, and speculative decoding speeds up generation without changing outputs.
Key papers to read
- Child et al., 2019, "Generating Long Sequences with Sparse Transformers": strided and fixed sparse patterns.
- Beltagy et al., 2020, "Longformer: The Long-Document Transformer": sliding window plus task-specific global attention.
- Zaheer et al., 2020, "Big Bird: Transformers for Longer Sequences": window, global and random attention with theoretical guarantees.
- Dao et al., 2022, "FlashAttention": not sparse, but the reason exact attention became practical at much longer lengths.
Frequently asked questions
What is sparse attention in transformers?
Sparse attention is a family of techniques in which each token computes attention scores with only a subset of other tokens instead of all of them, reducing the cost from quadratic to roughly linear in sequence length.
Is sparse attention less accurate than full attention?
It can be, because some token pairs are never compared directly. Well-designed patterns, global tokens and occasional full-attention layers recover most of the quality, but tasks that link distant details are the most sensitive.
What is the difference between FlashAttention and sparse attention?
FlashAttention computes exact full attention more efficiently by reorganising memory access; it does not skip any token pairs. Sparse attention deliberately skips pairs to reduce the total computation.
Do I need to know a model's attention type to use it?
No, but it helps to know that long-context performance varies. Test the model on long documents from your own domain, especially questions that require combining facts from distant sections.
