Long-Context Attention: Breaking the Quadratic Bottleneck in Sparse Indexing
Over the past year, million-token (1M) context has become the default specification for mainstream large models, but pushing toward 10M tokens has exposed a new bottleneck: with well-validated sparse attention in place, roughly 98% of single-layer prefill time is spent deciding which tokens to attend to, not on the attention computation itself. This article breaks down the attention cost structure, explains why the indexer remains quadratic even when the attention core becomes linear, and introduces latent sparse attention — which moves relevance scoring into a compressed low-dimensional latent space, delivering more than an order-of-magnitude layer-level speedup in prefill at 10M-token scale. You will also find guidance on profiling to confirm where your bottleneck actually sits, how to separate indexing from exact computation across layers, which recall and fallback metrics to monitor, and why the gains concentrate in prefill-heavy workloads while being strongly dependent on model architecture.
1. Once 1M Context Became the Default, the Cost Problem Surfaced
Over the past year, mainstream large models have gradually made million-token (1M) context the default specification of their official services. Long-document understanding, cross-repository code analysis, and long-session memory became practical as a result. Engineering practice quickly hit a new ceiling, though: as context grows from 1M toward 10M tokens, single-layer prefill latency still inflates abnormally — even with widely validated sparse attention in place.
One representative observation: in a certain global attention layer at 10M tokens of context, roughly 98% of prefill time is not spent on the actual attention computation, but on the step of “deciding which tokens to look at.” In other words, sparse attention solved the problem of looking at less, but did not solve the problem of choosing what to look at. That is the core issue this article examines.
2. The Cost Structure of Attention: Why Doubling Length Breaks the Budget
To understand how the bottleneck shifts, start with the computational complexity of attention. In standard full attention, every query computes relevance against all preceding keys:
- With context length T, prefill compute is roughly O(T²);
- Decoding each token costs roughly O(T).
This means that when context grows from 1M to 10M tokens (10x), attention-related compute grows by roughly 100x. This quadratic growth is the root reason ultra-long context is hard to sustain.
3. The Idea Behind Sparse Attention, and the Assumption It Depends On
The basic division of labor in sparse attention is this: a lightweight indexer first selects the k most relevant keys for each query, and the real attention is then computed over only those k keys. The cost of the attention core drops from O(T²) to roughly O(Tk).
This idea rests on one critical assumption: the model genuinely only needs to look at a few keys. Research supports this on validation sets — when each query attends only to the small set of keys that are truly most relevant to it (under roughly 1% of all keys), the model still retains about 98% of full-attention accuracy on long-context benchmarks. So “looking at only a small fraction” is nearly lossless in accuracy, which means the direction of sparsification is sound.
4. The Overlooked Hidden Bill: the Indexer Is Quadratic Too
The problem hides in how that assumption is implemented. For the indexer to know which k keys are most relevant, it must first score every key. A paradox follows:
Sparse attention brings the attention core down to linear cost, but the indexer’s scoring process is still quadratic — and it grows out of control with context length.
Common mitigations in the industry include lowering the scoring precision of the indexer, compressing the feature dimension used for scoring, and aggregating several adjacent keys into a block that is scored jointly (block sparsity). These techniques spread the cost somewhat, but they do not change the essential fact that scoring complexity grows quadratically with length. Once context reaches the ten-million-token range, this indexing overhead overtakes the attention core and becomes the dominant cost — which is exactly the “98% of time spent in the indexer” mentioned above.
The illustrative pseudocode below compares where cost comes from in the three paths:
# 1) Full attention: attention core is O(T^2)def full_attention(Q, K, V):scores = Q @ K.transpose(-1, -2) # [T, T], quadraticattn = softmax(scores)return attn @ V# 2) Sparse attention: core drops to O(T*k), but the indexer is still O(T^2)def sparse_attention(Q, K, V, k):# The indexer scores all keys for each query (this step is quadratic)index_scores = indexer_score(Q, K) # [T, T], the hidden billtopk_idx = index_scores.topk(k, dim=-1) # select k keysK_sel, V_sel = gather(K, V, topk_idx)scores = Q @ K_sel.transpose(-1, -2) # [T, k], cheapreturn softmax(scores) @ V_sel# 3) Latent sparse attention: move scoring into a low-dimensional# latent space to approach sub-quadratic costdef latent_sparse_attention(Q, K, V, k):# First compress K in latent space; the indexer only interacts# with the compressed representationK_latent = compress_to_latent(K) # dimension greatly reducedindex_scores = latent_indexer(Q, K_latent) # well below O(T^2)topk_idx = index_scores.topk(k, dim=-1)K_sel, V_sel = gather(K, V, topk_idx)scores = Q @ K_sel.transpose(-1, -2)return softmax(scores) @ V_sel
5. The Turning Point: From Scoring in the Original Space to Retrieval in Latent Space
Against this bill, a class of approaches called Latent Sparse Attention offers a new answer. Its core insight: the indexer does not have to score over the full representation of the original keys — relevance retrieval can happen in a compressed, low-dimensional latent space instead.
The chain of reasoning:
- Dimensionality reduction. Project the verbose key representations into a compact latent space, sharply lowering the cost of each relevance score and weakening the indexer’s quadratic growth at the source.
- Low-dimensional retrieval. The indexer estimates the relevance between each query and each key (or its aggregated representation) in latent space, and selects the top-k candidates.
- Exact computation in the original space. True attention is computed only over the selected k keys, at original precision, so accuracy is unaffected by the compression.
The retrieval stage now approaches sub-quadratic cost, the attention core stays at O(Tk), and overall complexity improves substantially. You can think of it as “use a cheap index to narrow the candidate set fast, then use expensive exact computation to confirm the result” — fundamentally a division of labor between retrieval and exact computation, except that the single most expensive scoring pass is moved into a low-cost space.
6. Impact: Order-of-Magnitude Layer-Level Gains and End-to-End Trade-offs
The value of this approach stands out most in ultra-long context. At ten-million-token scale, in the prefill scenario of a single global attention layer, latent-space retrieval delivers more than an order-of-magnitude speedup over naive sparse indexing (on some model structures, single-layer speedup can exceed 20x; certain architectures, where indexing overhead takes up a larger share, see even larger gains). Meanwhile, because the exact-computation stage still runs at original precision, accuracy on long-context evaluation tasks stays close to that of full attention or conventional sparse attention.
Some points deserve an objective view:
- The speedup is concentrated in the prefill stage, because that stage is dominated by the quadratic term. Each decode step is already dominated by O(T), so gains there are comparatively limited.
- Gains are strongly tied to model architecture. The higher the share of total latency taken by indexing overhead, the more visible the speedup; the lower the share, the smaller the improvement. This is also why speedup factors differ substantially across models for the same method.
- The latent compression ratio is a trade-off. The harder you compress, the cheaper retrieval becomes, but candidate recall may suffer, so tuning must account for the accuracy requirements of the specific task.
7. Implementation Guidance
If you want to borrow this idea in your own model or inference framework, consider these practical points:
- Locate the bottleneck before optimizing. Use profiling to confirm whether latency sits in the attention core or in the indexer. Latent-space retrieval is worthwhile when the indexer dominates (the common situation in ultra-long context); if the bottleneck is elsewhere, gains will be limited.
- Design indexing and exact computation as separate layers. Indexing handles “cast a wide net, at low precision and low dimension”; exact computation handles “high precision, focused on top-k.” Clear separation of responsibilities makes each easier to tune independently.
- Control recall metrics. Treat “did the selected k keys cover the set that is truly most relevant?” as a core monitoring metric, and validate accuracy regressions through replay evaluation when necessary.
- Mind the difference between prefill and decode. Workloads that are prefill-intensive — batch processing of long documents, cold starts of long sessions — benefit most and should be prioritized.
- Keep an accuracy fallback path. For accuracy-sensitive tasks, add a fallback switch that reverts to a larger k value or the original sparse scheme under abnormal conditions.
Conclusion
The battlefield of ultra-long context optimization has shifted from “can we look at less” to “can we find the right tokens cheaply.” Sparse attention proved that looking at less is good enough, but the real bottleneck moved to how that small fraction is found. Moving retrieval into latent space, and using the division of labor between retrieval and exact computation to push quadratic cost toward sub-quadratic, is a representative technical path today. For engineering teams, understanding this shift in cost structure matters more than memorizing any specific number — it determines which stage you should optimize first at ten-million-token context.
