Sparse Attention Optimization for 10-Million-Token Long Contexts
This article explains why full attention becomes expensive as context grows to millions or tens of millions of tokens. It describes how sparse attention addresses this with two stages: a lightweight indexer selects candidate tokens, and exact attention runs only on those candidates. It also covers the indexer's own cost, the different needs of prefill and decoding, adaptive candidate budgets, validation, and deployment risks.
In ultra-long context scenarios, the factor that most limits a model’s ability to scale is often not the peak compute of a single matrix multiplication. It is the combined cost of attention, which grows quadratically with sequence length. For inputs of millions or even tens of millions of tokens, standard full attention requires every query position to compute relevance against every historical key. Compute, memory reads and writes, and cache management pressure all increase at the same time.
The core idea of sparse attention is to split two tasks: finding relevant content among all positions, and precisely aggregating that content. The first task is handled by a lighter indexing module, which selects a small set of candidate keys for each query position. The second task runs full attention only over those candidates. As long as the candidate set covers the information that matters most, compute cost drops significantly while model quality can stay close to the original.
1. The Cost of Full Attention in Ultra-Long Contexts
Let the context length be (T) and the hidden dimension be (d). In standard attention, the query and key matrices compute relevance scores:
[
S=QK^T
]
Both (Q) and (K) contain one representation per token, so the relevance matrix is close to (T\times T) in size. In the prefill stage, total attention compute typically grows as (O(T^2d)). In token-by-token decoding, each new query still needs to access all previous keys, so the compute and memory access for a single token scale roughly as (O(Td)).
Going from 1 million to 10 million tokens increases resource use far more than tenfold. For prefill, the theoretical scale of relevance computation may grow about one hundredfold. For decoding, each generated token must scan a longer history cache, so throughput drops and latency rises more sharply.
The practical bottleneck also includes factors beyond arithmetic:
Growing key-value cache capacity
Every historical token must store its keys and values. The longer the context, the larger the cache, which makes GPU memory capacity a constraint.Memory bandwidth as the main constraint
During decoding, the limit is often not a lack of compute. The model repeatedly reads long-range history from memory. Even with powerful compute units, they may sit idle while data movement falls behind.Weaker memory locality
A full scan touches many historical positions that turn out to be irrelevant. Cache hit rates and the share of useful data both decline.Lower batching efficiency
Requests in the same batch can have very different context lengths. To handle the longest request, the system often reserves more cache space, which lowers overall resource utilization.
Stronger hardware or larger memory alone therefore does not solve the scaling problem at the 10-million-token level. The number of historical positions each query attends to must be reduced.
2. The Two-Stage Structure of Sparse Attention
Sparse attention can generally be described as two steps: indexing, then exact computation.
1. Lightweight Indexing
The indexer takes the current query and a compressed representation of the historical keys. It estimates how relevant each historical position is to the query. It does not need to reproduce the final attention scores exactly. Its job is to answer an approximate search question quickly:
Among all historical positions, which ones are most likely to contain the information the current query needs?
Let the history length be (T), and keep only (k) candidate positions per query, where (k\ll T). The indexer outputs the candidate set:
[
\mathcal{I}(q)={i_1,i_2,\ldots,i_k}
]
The indexing stage can use low-dimensional representations, compressed keys, chunk summaries, or other approximate features to reduce compute and data reads.
2. Exact Attention
After the candidate set is obtained, the model runs full key-value computation only on those positions:
[
\text{Attention}(q)=\text{Softmax}\left(\frac{qK{\mathcal{I}}^T}{\sqrt d}\right)V{\mathcal{I}}
]
The number of positions in the exact stage drops from (T) to (k). Attention compute then scales as (O(Tk)), or with the complexity of the candidate set, instead of the full (O(T^2)) matching.
If (k) is fixed while context length keeps growing, attention compute can in theory shift from quadratic growth to near-linear growth. This does not mean that all model compute becomes constant. The indexer, cache management, candidate aggregation, and parallel scheduling still consume resources.
3. Why a Small Candidate Set Can Be Enough
Information in long texts is usually unevenly distributed. A query does not need to access every historical token. It only needs to locate the few segments relevant to the task. For example:
- When answering a factual question, the relevant content may be concentrated in one definition or explanation.
- In code analysis, queries often depend on function declarations, variable definitions, and call relationships.
- In multi-turn dialogue, the current question usually relates directly to only some earlier turns.
- In long-document reasoning, different query positions may focus on entirely different sections, entities, or events.
Attention weights are therefore often concentrated on a small number of key positions rather than spread evenly across the context. If the indexer identifies these positions accurately, keeping a very small share of candidates may still preserve high task accuracy.
A common validation method is to run full attention first to get reference results, then examine where the most important historical keys for each query are located. If, at a smaller candidate size, the model still performs close to full attention on long-context retrieval, information localization, and multi-step reasoning, the sparsification is feasible.
For example, in a 100K-token context, keeping a few hundred highly relevant positions gives a candidate ratio below 1%. If those positions cover most of the key evidence, model performance may still stay close to full attention. The deciding factor is not the absolute size of the candidate set, but whether the candidate recall rate is high enough.
4. The Hidden Cost: The Indexer Itself
Sparse attention is not just a matter of replacing full attention with Top-k selection. If the indexer’s cost is poorly controlled, it can cancel out the gains from sparsity.
First, the indexer must process a large number of historical positions. If it still matches each query against all high-dimensional keys, the complexity has not decreased. The cost has only moved to a different component. Index features therefore usually need compression, such as lower-dimensional representations, grouped summaries, or hierarchical candidate structures.
Second, the memory access pattern of the candidates affects hardware efficiency. Full matrix operations suit regular, contiguous memory access, while Top-k results are usually non-contiguous. If each query reads a small number of historical keys and values at random, the theoretical
