Fast Attention and Long Context
Sparse and block attention patterns
Sparse attention makes each token read only a chosen subset of the others, and the pattern must be arranged in blocks or the hardware saves nothing at all.
- 12 min read
- 3 reading levels
- Updated
Read these first
On this page 10
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
The short answer
Sparse attention lets each word read only a chosen few of the earlier words, instead of all of them.
The thick manual on your desk
You have a five-hundred-page manual and one question to answer. You do not read every page against every other page.
You read the pages around the part you are on. You keep a finger in the contents page and flip back to it often. And you glance at the chapter headings.
Three habits: read nearby, always keep a few key pages available, and skip in regular jumps. Every sparse attention pattern ever published is some mixture of those three.
Why skipping is needed at all
Full attention has every word read every earlier word. Double the document and you quadruple the work.
At a hundred thousand words that becomes the largest single cost in the model. Most of it is wasted, because most word pairs have nothing to do with each other.
So: choose which pairs to compute, and skip the rest.
The three building blocks
Local. Read the nearest few hundred words. Covers grammar, the current sentence, the current paragraph.
Global. A few special positions that everyone can read and that can read everyone. The contents page.
Strided. Read every eighth word, or every sixty-fourth. A regular skim that reaches far back cheaply.
rows are words asking, columns are words being read
# = computed, . = skipped
local + global (4 global, window of 8)
####....................
####.########...........
####..########..........
####...########.........
####....########........
the four left-hand columns are always read
the moving band is the local neighbourhoodThe trap almost everyone falls into
Here is the part that separates a paper from a working system.
Suppose you skip ninety percent of the pairs. The ten percent you keep are scattered at random across the page. A graphics card cannot use that. It works on square tiles, and a tile with one live entry costs the same as a full one.
So a random pattern that skips ninety percent of the work saves close to nothing. It is slower than doing everything, once you add the bookkeeping.
The pattern must be arranged in blocks — solid squares that are either all kept or all dropped. Neat patterns beat clever ones, and this is why.
Chosen by hand, or chosen by the model
Older methods fixed the pattern in advance. Local plus global plus strided, written into the code.
Newer methods let the model choose. A cheap first pass scores which blocks look relevant for this query. The best few are picked, and only those are read properly.
That is more work, and it adapts. A question about page four hundred pulls in page four hundred, which no fixed pattern would have done.
The honest picture
Sparse attention is not settled. One well-known lab shipped a sparse model, then went back to full attention in its next release. Their reason: no sparse variant matched full attention on reasoning, coding and agent tasks in production.
Another lab shipped sparse attention in its flagship and reports it working well. Both are being honest. The technique helps most where contexts are longest.
Where you have already seen this
- Services offering a million-word context at a sane price.
- Long-document search tools that answer in seconds rather than minutes.
- Models advertised as handling entire code repositories.
Remember this
- Sparse attention computes a chosen subset of word pairs instead of all of them.
- The subset must be arranged in blocks, or the hardware saves nothing.
- Fixed patterns are simple; learned patterns adapt, and cost more to build.
What to learn next
- Linear attention — removing the quadratic term instead of skipping parts of it.
- Advertised context vs usable context — how to catch a sparse method that broke recall.
- What a mixture of experts really is — the same routing idea, applied to the feed-forward layers.
Developer — Code and libraries.
Setup
pip install torchWritten against PyTorch 2.5.1, Python 3.10. CPU only.
Building the patterns, and measuring the right thing
import torch
N = 64
i = torch.arange(N)[:, None]
j = torch.arange(N)[None, :]
causal = j <= i
patterns = {
"full causal": causal,
"local w=8": causal & (i - j < 8),
"strided s=8": causal & ((j % 8) == 0),
"global 4 + local 8": causal & ((i - j < 8) | (j < 4) | (i < 4)),
"random 10%": causal & (torch.rand(N, N, generator=torch.Generator().manual_seed(0)) < 0.10),
}
print(f"{'pattern':<20}{'kept':>7}{'of':>7}{'density':>9}")
for name, m in patterns.items():
print(f"{name:<20}{int(m.sum()):>7}{int(causal.sum()):>7}{m.sum().item()/causal.sum().item():>9.3f}")
def show(m, name, n=24):
print(f"\n{name} (first {n} x {n})")
for r in range(n):
print(" " + "".join("#" if m[r, c] else "." for c in range(n)))
show(patterns["global 4 + local 8"], "global 4 + local 8")
# Block sparsity is what a kernel can actually skip.
BS = 8
print(f"\n{'pattern':<20}{'live blocks':>13}{'of':>5}{'block density':>15}")
nb = N // BS
for name, m in patterns.items():
blocks = m.view(nb, BS, nb, BS).any(1).any(-1)
print(f"{name:<20}{int(blocks.sum()):>13}{nb*nb:>5}{blocks.sum().item()/(nb*nb):>15.3f}")pattern kept of density full causal 2080 2080 1.000 local w=8 484 2080 0.233 strided s=8 288 2080 0.138 global 4 + local 8 702 2080 0.338 random 10% 208 2080 0.100 global 4 + local 8 (first 24 x 24) #....................... ##...................... ###..................... ####.................... #####................... ######.................. #######................. ########................ #########............... ##########.............. ###########............. ############............ ####.########........... ####..########.......... ####...########......... ####....########........ ####.....########....... ####......########...... ####.......########..... ####........########.... ####.........########... ####..........########.. ####...........########. ####............######## pattern live blocks of block density full causal 36 64 0.562 local w=8 15 64 0.234 strided s=8 36 64 0.562 global 4 + local 8 21 64 0.328 random 10% 36 64 0.562
Read the two density tables against each other
This comparison is the entire practical content of the lesson.
random 10% has element density 0.100 and block density 0.562. It computes one tenth of the entries and a kernel can skip nothing, because every 8x8 block contains at least one live entry. On real hardware it would run at full cost plus gather overhead, so slower than dense.
strided s=8 is the same story. Element density 0.138, block density 0.562. A stride that hits every block is invisible to a tiled kernel. To be useful, the stride must be a multiple of the block size and aligned to it.
local w=8 is honest sparsity. 0.234 element density, 0.234 block density. Everything the pattern drops, the kernel can actually drop.
global 4 + local 8 costs more than local alone — 0.328 against 0.234 — and buys direct long-range edges. The four leftmost columns live in one block column that is never skipped. Global tokens are cheap precisely because there are few of them and they are contiguous.
The rule to carry away: measure block density, not element density. A paper reporting 95% sparsity that never mentions block structure is reporting a number that will not appear in your wall clock.
Doing it with a real kernel
torch.nn.attention.flex_attention takes a mask_mod and builds a block mask, so entirely-masked blocks are skipped in the fused kernel.
from torch.nn.attention.flex_attention import create_block_mask, flex_attention
def local_global(b, h, q_idx, kv_idx):
causal = kv_idx <= q_idx
return causal & ((q_idx - kv_idx < 512) | (kv_idx < 4))
mask = create_block_mask(local_global, B=None, H=None, Q_LEN=8192, KV_LEN=8192, device="cuda")
out = flex_attention(q, k, v, block_mask=mask)mask_mod receives scalar index tensors and returns a boolean. create_block_mask evaluates it on a block grid, defaulting to BLOCK_SIZE=128, and records which blocks are live. This is a prototype API as of PyTorch 2.13 and its signature has changed between releases, so pin your version. The concept — express the pattern as a predicate, let the compiler find the block structure — is stable even where the function is not.
Fixed patterns, and learned ones
| Approach | Pattern chosen by | Example |
|---|---|---|
| Band | the architect | Mistral's 4096 window |
| Band + global | the architect | Longformer, BigBird |
| Strided / dilated | the architect | Sparse Transformer |
| Top-k blocks per query | the model, at run time | NSA, MoBA, DeepSeek Sparse Attention |
Learned selection runs a cheap scoring pass first. DeepSeek-V3.2's "lightning indexer" scores blocks, keeps the top 2048 tokens in the released configuration, then runs full attention over those. It is retrieval bolted to the front of attention.
Common mistakes
Reporting element sparsity as a speed-up. Covered above, and it is the single most common error in this area.
Forgetting the sink. Every sparse pattern must keep the first tokens reachable, or you hit the failure in attention sinks. Note that global 4 + local 8 gets this right by accident.
Materialising the mask. An N x N boolean tensor at N = 131072 is 17 GB. Use a predicate, not a tensor. The example above uses a dense mask only because N = 64.
Assuming a sparse-trained pattern can be applied at inference to a densely trained model. Sometimes it works, often it does not. If the model never trained under the mask, its heads may depend on edges you removed.
Benchmarking sparse attention at short context. Below a few thousand tokens the bookkeeping dominates and dense wins. Sparse methods are a long-context tool.
Try it yourself
Change random 10% to a block-random pattern: pick random 8x8 blocks rather than random entries, at the same overall density. Confirm block density now equals element density. That one edit is the difference between a paper and a product.
What to learn next
- Linear attention — removing the quadratic term instead of skipping parts of it.
- Advertised context vs usable context — how to catch a sparse method that broke recall.
- What a mixture of experts really is — the same routing idea, applied to the feed-forward layers.
Researcher — Mathematics and papers.
The design space
Fix a block size $B$. Attention becomes a computation over an $\lceil N/B \rceil \times \lceil N/B \rceil$ block adjacency matrix $\mathcal{B}$. Cost is $\Theta(|\mathcal{B}| B^2 d)$ where $|\mathcal{B}|$ is the number of live blocks. Element-level sparsity within a live block is free in the sense that it costs the same as density.
This single fact rules out most theoretically attractive patterns. Any scheme whose live entries are spread uniformly has $|\mathcal{B}| \to$ full, regardless of element density.
Fixed patterns
Child, Gray, Radford and Sutskever (2019), Generating Long Sequences with Sparse Transformers (arXiv:1904.10509) factorise attention into strided and fixed heads, achieving $O(N\sqrt{N})$ with two-hop coverage of all positions.
Beltagy, Peters and Cohan (2020), Longformer (arXiv:2004.05150) combine a sliding window, dilated windows in upper layers, and task-specific global tokens, giving $O(N w)$.
Zaheer et al. (2020), Big Bird: Transformers for Longer Sequences (arXiv:2007.14062, NeurIPS 2020) add random attention to window plus global, and prove the resulting sparse attention is a universal approximator of sequence functions and Turing complete — but also prove that matching full attention on some tasks requires $\Omega(N)$ layers under sparsity. The theory says sparse attention is expressive enough in principle, and gives no comfort about a fixed layer budget.
The random component in BigBird is theoretically load-bearing and practically the awkward part, for exactly the block-density reason above. Implementations block-align it.
Learned selection
DeepSeek (2025), Native Sparse Attention (arXiv:2502.11089) combines coarse-grained token compression with fine-grained token selection, plus a sliding-window branch, in a design described as "hardware-aligned" through "arithmetic intensity-balanced algorithm design" and "natively trainable" so that sparsity is present during pre-training rather than imposed afterwards. They report speedups over full attention on 64k sequences in forward, backward and decoding.
That last property matters more than the speed. A model trained dense and sparsified at inference has heads that were optimised against edges you have deleted. NSA's claim is that training under the sparsity pattern removes that mismatch.
Lu et al. (2025), MoBA: Mixture of Block Attention for Long-Context LLMs (arXiv:2502.13189, Moonshot AI) apply mixture-of-experts routing to attention blocks, letting the model pick which blocks each query attends to, with "seamless transitions between full and sparse attention". It is deployed in Kimi's long-context path. The connection to mixture of experts is direct: a router over blocks instead of a router over feed-forward networks.
DeepSeek-V3.2 ships DeepSeek Sparse Attention: a lightning indexer scores query-block relevance, top-$k$ (2048 in the released code) tokens are selected, and fine-grained attention runs over those alone. Layered on top of MLA, so cache compression and attention sparsity compose.
The dissenting result
MiniMax shipped Lightning Attention in MiniMax-01 and reverted to full multi-head attention in MiniMax-M2, reporting that no efficient-attention variant they tested reliably matched full attention across reasoning, coding and agentic tasks in production.
Take this seriously. It is one of the few public negative results from a team that had already shipped the alternative, and it is a useful corrective to a literature where sparse methods are compared on perplexity and long-context synthetics rather than on the tasks that pay for the model.
The reconciliation most practitioners reach: sparsity pays at very long context and on retrieval-shaped workloads, and is a liability at moderate context on reasoning-shaped workloads. Which regime you are in is an empirical question about your traffic, not a question about the technique.
Evaluation
Report all four of these or the result is not interpretable:
- Block density, not element density.
- Measured wall-clock and memory at the context lengths you serve, against a FlashAttention baseline on the same hardware.
- Retrieval-sensitive accuracy — RULER-style multi-needle and aggregation tasks, where sparsity fails first.
- Whether the pattern was present during training. Post-hoc sparsification and native sparsity are different techniques with different results.
What to learn next
- Linear attention — removing the quadratic term instead of skipping parts of it.
- Advertised context vs usable context — how to catch a sparse method that broke recall.
- What a mixture of experts really is — the same routing idea, applied to the feed-forward layers.