Sparse Attention at Ten-Million-Token Context: Overcoming the Indexing Bottleneck
This article examines why sparse attention becomes bottlenecked by its indexer as context grows from one million to ten million tokens, and how latent-space sparse attention can address the problem through low-dimensional coarse filtering, block-level candidates, token-level reranking, and exact attention. It also covers cost structure, recall-precision tradeoffs, implementation considerations, deployment practices, and current limitations for ultra-long-context inference.
Sparse Attention at Ten-Million-Token Context: Overcoming the Indexing Bottleneck
1. From One Million to Ten Million Tokens: The Problem Changes
For some time, million-token context has been an important specification for long-context models. To keep inference costs manageable, sparse attention has been widely adopted: instead of computing attention between every query and all historical tokens, a lightweight indexer first selects a small set of relevant keys, and exact attention is then computed over that candidate set. This approach has been repeatedly validated at million-token scale. As long as the candidate set is accurate enough, model accuracy can approach that of full attention, while attention computation changes from quadratic growth with context length to approximately proportional to “context length × number of candidates.”
As context moves toward ten million tokens, however, previously minor costs begin to dominate. Public experimental data shows that, at ten-million-token scale, when running prefill for a certain type of hybrid attention layer, most of the time is not spent on attention computation itself but on the indexer that decides which tokens to attend to. In other words, sparse attention reduces exact attention to O(Tk), but it does not automatically solve the problem of “how to find k keys from T keys.” If the indexer still scans all keys for every query, its cost remains quadratic with context length, even if the constant factor is smaller.
This is the key conceptual shift as ultra-long context reaches ten million tokens: sparse attention has already shown that “looking at only a small subset” is enough to preserve accuracy. The real obstacle to scale is that “finding that small subset” is still too expensive. The bottleneck moves from the attention operator to retrieval and indexing.
2. The Hidden Bill of Sparse Attention
Consider the cost structure. In standard full attention, every query computes relevance against all previous keys. When context length is T, attention computation during prefill is approximately O(T²), and the incremental cost per decoded token is approximately O(T). When context grows from 1 million to 10 million tokens, prefill attention computation theoretically grows by about 100×.
Sparse attention splits the process into two steps. First, an indexer selects the k most relevant keys for each query. Second, attention is computed only over those k keys. The second step can be reduced to O(Tk), which delivers significant savings when k is much smaller than T. But the first step is not inherently cheap. To determine which keys are most relevant, the indexer must score candidate keys. If every query must be compared with all keys, the indexer itself is O(T²). Even when constant factors are reduced through lower precision, fewer dimensions, or merging multiple keys into block representatives, the asymptotic complexity does not fundamentally change.
Block-sparse methods are a common optimization: consecutive tokens are merged into blocks, similarity is first computed between the query and block representatives, and token-level attention is then performed within a small number of blocks. This can significantly reduce unnecessary indexer accesses, improve cache locality, and reduce the size of top-k sorting. At ten-million-token scale, however, the number of blocks is still large, and scoring every query against all blocks still creates substantial quadratic pressure. More importantly, the indexer usually needs to access key representations, block summaries, or compressed caches. These accesses introduce memory bandwidth, cache hit rate, and scheduling overhead. Computation is only part of the bill; data movement and candidate ranking are also costs.
The hidden bill of sparse attention can therefore be divided into four categories:
- Full scoring cost: Every query computes similarity against a large number of keys or block representatives, and this cost rises rapidly with T.
- Candidate ranking cost: Top-k selection, threshold filtering, sorting, and heap operations are not cheap on very large candidate sets.
- Memory access cost: The indexer must read key representations, block summaries, and metadata. Random access reduces effective bandwidth.
- Accuracy recovery cost: When coarse filtering has insufficient recall, larger candidate sets, reranking, or fallback mechanisms are needed, further increasing cost.
When these four costs combine, the result is the phenomenon in which “attention accounts for only a small part while the indexer accounts for the large part.” Sparse attention has not failed; the optimization focus must shift from the attention operator to the indexing structure.
3. Core Idea of Latent-Space Sparse Attention
To address this bottleneck, public research has proposed a class of latent-space sparse attention methods. The core idea is not to continue making full scoring cheaper in the original high-dimensional space, but to move the process of “finding relevant tokens” into a low-dimensional latent space. Through a hierarchical structure of “coarse filtering — reranking — exact attention,” the indexer is freed from quadratic complexity.
This can be understood in three layers:
The first layer is low-dimensional latent representation for coarse filtering. Queries and keys are projected into a lower-dimensional latent space, and a cheaper inner product or approximate similarity measure performs the first round of filtering. The low-dimensional representation does not aim for final accuracy. Instead, it quickly eliminates many clearly irrelevant blocks or tokens with high recall. Because dimensionality and data volume are reduced, both unit computation and memory access cost decrease during coarse filtering.
The second layer is block-level candidates and token-level reranking. Coarse filtering first selects several candidate blocks, and finer token-level scoring is then performed inside those blocks to obtain the final top-k. Block-level structure can turn random access into contiguous access and improve cache locality. The number of candidate blocks is controllable, which also avoids fine-grained sorting directly over all tokens. Coarse filtering handles recall, while reranking handles precision.
The third layer is exact attention computation. Standard attention is finally executed only on the k keys after reranking. Because k is much smaller than T, the cost of this stage is effectively controlled. More importantly, the indexer no longer needs to scan all keys for every query. Through approximate retrieval in latent space or hierarchical indexing, indexing cost can move toward sub-quadratic growth.
The key to this approach is not merely “dimensionality reduction.” It is splitting the indexer into a multi-stage pipeline with adjustable budgets: the coarse-filtering stage pursues high throughput and high recall, the reranking stage pursues ranking quality, and the exact-attention stage pursues numerical precision. Each stage can be optimized independently and tuned across different hardware and service-level requirements.
4. Accuracy and Performance: Sparse Is Enough, but Recall Is Critical
Sparse attention relies on the premise that the model truly needs only a small number of keys. Public validation shows that, in contexts around 100,000 tokens, letting each query attend to only about 0.8% of its most relevant keys still preserves accuracy close to full attention on long-context retrieval, aggregation, and multi-hop tasks. This suggests that “sparsity” itself is not the main cause of accuracy loss. What really affects quality is the recall of the candidate set: if the most relevant keys are not selected by the indexer, no amount of subsequent attention precision can compensate.
The value of latent-space sparse attention is that it attempts to maintain acceptable recall at lower indexing cost. Public experiments show that, at ten-million-token scale, prefill for a single attention layer can achieve roughly 20× to 70× speedup while maintaining accuracy close to the original model on a range of tasks. These numbers should be understood as single-layer gains under specific experimental conditions, not as direct end-to-end service throughput improvements. End-to-end performance is also affected by the number of model layers, batch size, sequence distribution, candidate count, hardware memory bandwidth, and scheduling strategy.
From an engineering perspective, three metrics deserve particular attention: index recall, candidate set size, and the proportion of exact attention. Recall determines the upper bound of accuracy, candidate set size determines reranking and attention cost, and the proportion of exact attention indicates whether optimization has truly moved the bottleneck. A healthy sparse attention service should be able to spend most of its time on effective computation rather than inefficient indexing, without significantly sacrificing recall.
5. Implementation Notes and Example Flow
In practice, latent-space sparse attention can usually be abstracted as a two-stage or three-stage pipeline. The following illustrative pseudocode expresses only the structure, not a specific implementation or interface:
function SparseAttention(query, key, value, candidate_blocks, final_topk):# 1. Low-dimensional latent representationsq_latent = project_query(query)k_latent = project_key(key)block_summaries = aggregate_keys_in_blocks(k_latent)# 2. Block-level coarse filtering: each query is compared only with block summariesblock_scores = similarity(q_latent, block_summaries)candidate_blocks = select_top_blocks(block_scores, candidate_blocks)# 3. Token-level reranking within candidate blockstoken_scores = similarity(q_latent, k_latent_in(candidate_blocks))candidate_key_indices = select_top_tokens(token_scores, final_topk)# 4. Exact attentionoutput = softmax(dot(query, candidate_keys) / scale) weighted by candidate_valuesreturn output
Several key tradeoffs arise during implementation:
- Block size: Larger blocks mean fewer block summaries and cheaper coarse filtering, but higher intra-block reranking cost and coarser recall granularity. Smaller blocks have the opposite effect. Tune according to sequence distribution and cache structure.
- Number of candidate blocks: More candidate blocks improve recall but increase reranking cost. Dynamic budgets can be used: simple queries select fewer blocks, while complex queries select more.
- Latent dimensionality: Too low a dimensionality loses discriminative power; too high a dimensionality makes coarse filtering expensive. Use offline evaluation to find the point where recall and cost trade off best.
- Fallback mechanism: When coarse-filtering confidence is low or candidate score distributions are flat, expand the candidate set or fall back to a more precise indexing path to avoid sharp accuracy drops on long-tail queries.
- Cache layout: Store block summaries, key latent representations, and values in blocks to encourage contiguous access. Cache frequently accessed blocks to reduce random reads and writes.
- Monitoring loop: Record proxy recall metrics, top-k score distributions, index time proportion, and end-to-end latency online. Adjust budgets promptly when recall drift is detected.
6. Deployment Practice: Include Indexing Cost in the Service Capacity Model
When deploying ten-million-token context inference services on general cloud infrastructure, indexer cost must be included in the capacity model rather than estimated only from attention FLOPs. General cloud infrastructure can provide object storage for long documents and index metadata, container platforms for inference and indexing services, and monitoring, alerting, and logging services for observing latency, recall proxy metrics, and resource utilization. The value of such infrastructure lies in decoupling storage, computation, and monitoring so they can be scaled independently.
For service design, consider the following:
- Separate indexing and attention resources: The indexer is often memory-bandwidth-sensitive, while exact attention is more compute-intensive. Their resource ratios differ, and co-locating them can cause interference.
- Tier by sequence length: Short contexts can use full attention or a lightweight sparse path, while only long contexts enable multi-stage indexing. This avoids imposing extra scheduling overhead on small requests.
- Set latency budgets: Define time budgets separately for coarse filtering, reranking, and exact attention. When budgets are exceeded, reduce candidate scale rather than allowing tail latency to spiral.
- Preserve observability: Record per-stage latency, candidate counts, recall proxy metrics, and fallback counts to build a traceable performance profile.
- Manage hot and cold data: Block summaries and latent representations for long documents can be precomputed and cached, but version consistency and update costs must be handled carefully.
7. Limitations and Outlook
Latent-space sparse attention is not a universal solution. First, low-dimensional coarse filtering has long-tail recall problems. Complex reasoning or multi-hop queries may require larger candidate sets, making dynamic budgets and fallback mechanisms essential. Second, training consistency between the indexer and the main model affects quality. If the indexer is only approximated during inference, distribution bias may be introduced. Third, the decode stage and prefill stage have different bottlenecks: prefill focuses more on large-scale parallel indexing, while decode focuses more on incremental candidate maintenance and cache hit rate, so they need separate optimization. Finally, end-to-end cost at ten-million-token scale remains high. Sparse attention lowers the cost curve, but it does not eliminate the storage, transmission, and scheduling overhead of long context itself.
Overall, sparse attention for ultra-long context is moving from “optimizing only the attention operator” to “optimizing the indexing structure as well.” The lesson from latent-space sparse attention is that making ten-million-token context truly usable requires treating the process of “finding relevant tokens” as a first-class design problem. Hierarchical indexing, low-dimensional coarse filtering, block-level candidates, and exact reranking must work together to control cost. Only when the indexer is freed from quadratic growth can sparse attention deliver on its accuracy and efficiency promises at ten-million-token scale.
