Scaling Context to 10M Tokens: Optimizing Sparse Attention Indexing
As context windows expand from 1M to 10M tokens, the main bottleneck in long-context systems is shifting. The expensive part may no longer be weighting a small set of relevant tokens, but finding those tokens in the first place. This article examines why sparse-attention indexers can dominate prefill latency, explains the coarse-to-fine strategy behind Latent Sparse Attention (LSA), analyzes reported 22.7× and 72.4× single-layer prefill speedups, and provides practical guidance for evaluation, tuning, and hybrid attention design.
Scaling Context to 10M Tokens: Optimizing Sparse Attention Indexing
As context windows grow from 1M to 10M tokens, the central performance problem in long-context systems changes. The expensive operation is not necessarily applying attention weights to a small number of relevant tokens. It may be identifying those tokens in the first place.
Sparse attention has already shown that a query does not need to examine the entire history to preserve accuracy on many tasks. However, candidate selection itself can still grow rapidly with context length. As the context becomes longer, this once-secondary indexing cost can become the primary bottleneck.
Publicly available material provides a representative observation: at a 10M-token scale, during prefill for a global attention layer, approximately 98% of the time was spent not on attention-value computation, but on the indexer that determines which tokens should be inspected. This highlights an important fact: sparse attention does not automatically eliminate quadratic costs. Instead, part of the cost is shifted from full attention computation to candidate search and routing.
This article focuses on that bottleneck. It first explains why indexers become inefficient at the 10M-token scale, then introduces the “coarse filtering followed by precise computation” strategy used by Latent Sparse Attention (LSA). It also examines the sources and limitations of the reported 22.7× and 72.4× single-layer prefill speedups, followed by an engineering checklist for evaluation, tuning, and hybrid architectures.
1. From Millions to Tens of Millions of Tokens: How the Indexer Can Still Become the Bottleneck
1.1 The problem splits into computation and search
The cost of standard full attention grows approximately with the square of sequence length. Sparse attention reduces the attention-weighting and memory-access costs by limiting the number of tokens visible to each query.
A typical sparse-attention pipeline can be summarized in three steps:
- Estimate the relevance of historical tokens or historical blocks for the current query.
- Select the top-k candidate tokens or blocks.
- Run exact attention only on the candidate set and aggregate the output.
The third step is usually the most visible computation in sparse attention. At a 10M-token context length, however, the first two steps can become the longer part of the critical path. The system must determine where to look before it can perform exact attention. If the indexer scans a massive history, the total cost remains substantial even when each individual relevance calculation uses a reduced representation.
1.2 Quadratic behavior can hide in several indexing stages
Indexer cost is not limited to calculating a relevance score. It can be divided into several categories:
- Scoring cost: If every query still computes relevance against every historical token or block, the number of scoring targets grows with sequence length. For block-level routing, the number of blocks grows linearly with the context, while the number of queries also grows linearly, producing significant near-quadratic pressure.
- Top-k and sorting cost: Repeatedly selecting the top-k candidates from millions of options introduces sorting, merging, threshold-comparison, and synchronization overhead. Approximate top-k methods can reduce this cost but cannot necessarily eliminate the need to traverse candidates.
- Explicit or implicit large-matrix access: If operators are not sufficiently fused, implementations may create large intermediate score matrices or tiled results, increasing memory-bandwidth demand and GPU memory usage.
- Irregular gather operations and load imbalance: After candidates are selected, the system must gather the corresponding Key/Value segments. Different queries may select very different blocks, leading to non-contiguous memory access, lower cache hit rates, and uneven parallel workloads.
- Causal masking and batching constraints: During prefill, all queries must obey causality, so future tokens cannot be selected. The placement of masking, variable batch lengths, and block partitioning all affect indexer efficiency.
Therefore, when public experiments report that 98% of the time is spent in the indexer, this does not mean attention computation has become irrelevant. It means that, under extremely long sequences and sparse candidate selection, the critical path has moved to relevance estimation and candidate management.
1.3 Prefill amplifies the indexing problem
During prefill, the system processes all input tokens at once to build the cache state required for subsequent generation. Prefill offers substantial parallelism, but it also forces the indexer to handle a very large number of queries and historical tokens in one pass.
If the indexer still performs a full scan, overall prefill latency can remain high even when the exact attention stage processes only a small candidate set.
This is why single-layer prefill speedup is an important metric. It directly reflects improvements in a key component of first-token latency for long-context requests. However, single-layer acceleration is not the same as end-to-end acceleration. A model has many layers, and sequence processing also includes embeddings, feed-forward networks, normalization, communication, and cache management.
Whether indexer optimization produces a user-visible throughput improvement must be evaluated using Amdahl’s law and the actual proportion of time spent in the optimized component.
2. The Core Idea of Latent Sparse Attention: Move Candidate Search into a Lower-Dimensional Space
2.1 Replace full exact comparison with hierarchical approximate filtering
The basic idea behind LSA is to avoid comparing every historical token one by one in the original high-dimensional Key/Value space. Instead, candidate search is performed in a lower-dimensional and coarser latent space. The system then returns to the original space to run exact attention on a small set of candidates.
A general engineering structure typically includes four operations:
- Organize history into blocks or levels: Divide the long sequence into contiguous blocks, segments, or hierarchical nodes. Perform coarse filtering at the block level first to reduce the number of candidates.
- Estimate relevance in latent space: Use low-dimensional projections, compressed summaries, or learned representations to estimate relevance between the query and candidate blocks. This space does not need to match the final attention dimension; its purpose is to rank candidates at lower cost.
- Filter and merge candidates: Select the top-k blocks, then perform token-level filtering within those blocks or expand them into a small token candidate set. Necessary paths such as local windows and global anchors can also be preserved.
- Run exact sparse attention: Apply exact attention only to the final candidate set while preserving causal masking, numerical stability, and mixed-precision requirements.
The exact projection method, block size, candidate-merging rule, and training strategy depend on the specific paper implementation and should be verified against its published materials. The description below is a general engineering abstraction intended to explain the source of the performance gains, not to make claims about every internal detail of a particular implementation.
2.2 Illustrative pseudocode
# Describes computational dependencies only;# it does not represent a specific framework implementation.def lsa_forward(q, k, v, block_size, topk_blocks, local_window):# 1. Coarse-grained routing in latent spaceq_lat = project_query(q)k_blocks = compress_blocks(k, block_size) # Block-level summariesblock_scores = q_lat @ project_block(k_blocks).transpose(-1, -2)block_scores = apply_causal_mask(block_scores) # Critical: mask future blocks first# 2. Select a small number of candidate blocks and add the local windowselected_blocks = topk(block_scores, k=topk_blocks, dim=-1)selected_idx = expand_blocks(selected_blocks)local_idx = get_local_window_indices(q, size=local_window)idx = unique_union(selected_idx, local_idx)# 3. Run exact attention only on candidate tokensk_sel = gather(k, idx)v_sel = gather(v, idx)attn = softmax(q @ k_sel.transpose(-1, -2) / sqrt(head_dim))return attn @ v_sel
Production implementations generally need to fuse projection, scoring, top-k selection, gather, and attention operations to avoid materializing a complete score matrix.
For causal masking, future blocks must be excluded before top-k selection. Otherwise, the model could access information that should not be visible during training. Variable-length batches also require careful handling of padding, differences in sequence length, and out-of-range candidate indices.
2.3 Why coarse filtering and precise computation can preserve both speed and accuracy
This approach is attractive because it does not simply discard long-range information. Instead, it processes information at two levels:
- The coarse stage uses lower-dimensional representations or block summaries. Its goal is to identify relevant regions with high recall, not to complete the final reasoning step.
- The precise stage retains the original high-dimensional Key/Value representations and performs exact interactions within the selected candidate set.
If coarse filtering can cover most truly relevant tokens at low cost, final accuracy can remain close to that of the original model. If the filter misses critical evidence, later exact computation cannot recover it. Routing recall and final task accuracy are therefore just as important as the speedup ratio.
3. How to Interpret the 22.7× and 72.4× Results
3.1 These are single-layer prefill metrics, not end-to-end throughput metrics
Public experiments report that, at a 10M-token context length, LSA achieved approximately 22.7× and 72.4× speedups for a single global attention layer during prefill, while maintaining accuracy close to the original model on multiple tasks.
“Single-layer prefill” means that the metric measures the improvement for one attention layer during input processing. It does not represent the complete response time of the model.
This distinction is essential. If a layer accounts for a fraction (p) of the original total prefill time and LSA accelerates that layer by a factor of (s), the theoretical end-to-end speedup can be approximated as:
overall_speedup = 1 / ((1 - p) + p / s)
If (p=0.5) and (s=20), the end-to-end speedup is approximately 1.90×. If (p=0.2) and (s=20), it is only about 1.23×.
Layer-level acceleration can therefore be substantial, while end-to-end gains depend on the layer’s share of the complete execution path and on whether other bottlenecks are also addressed.
3.2 Different speedups indicate strong dependence on the baseline
The difference between 22.7× and 72.4× is not surprising. The speedup depends on factors including:
- The proportion of single-layer prefill time originally spent in the indexer;
- Block size, candidate count, and latent-space dimension;
- The number of model heads, hidden dimensions, and Key/Value cache organization;
- Operator fusion, GPU memory-bandwidth utilization, and candidate-gather locality;
- Sequence length, batch size, and the effective candidate count after causal masking;
- Whether the baseline already uses optimized sparse kernels and memory layouts.
A result showing tens of times acceleration should not be interpreted as a tens-of-times increase in system throughput. A more reliable process is to first measure the indexer’s share of prefill and decode time in the target model, then reproduce layer-level results with the same sequence length, batch size, and precision settings, and finally estimate the end-to-end SLO improvement.
3.3 Track prefill, decode, and memory metrics separately
A long-context service should record at least the following metrics:
| Metric | What it indicates |
|---|---|
| Time to first token | Primarily affected by prefill, especially for very long inputs |
| Generation throughput | Affected by decode, KV-cache access, and batch scheduling |
| Single-layer prefill time | Whether indexer optimization is actually effective |
| Indexer time share | Whether candidate search remains a hotspot |
| Peak GPU memory or system memory | Whether intermediate score matrices and cache layouts are efficient |
| Routing recall | Whether candidate selection misses important evidence |
| Task accuracy | Performance on retrieval, multi-hop reasoning, aggregation, and long-document tasks |
4. Combining Hybrid Attention with LSA
4.1 Sparse global attention should not operate in isolation
At the 10M-token scale, a single attention mechanism often cannot simultaneously provide local syntactic modeling, global information compression, precise long-range retrieval, and cost control.
Common hybrid designs include:
- Local-window attention for high-precision interactions among nearby tokens;
- Linear attention, state-space-style layers, or global summaries for compressing long-term history;
- Sparse global attention for precise long-range retrieval at selected positions;
- Denser attention in selected layers or heads as an accuracy safeguard.
LSA primarily addresses candidate search in sparse global attention. It does not need to replace every layer. It is better suited to global attention layers that already handle long-range routing and selection.
Layer-specific candidate budgets can preserve more local inductive capability in early layers and strengthen cross-segment integration in deeper layers.
4.2 Global anchors and local windows provide important accuracy safeguards
Even a strong approximate router may occasionally miss a critical token. Engineering implementations therefore often retain fixed paths such as:
- Local windows: Ensure that nearby tokens remain visible.
- Global anchors: Preserve a small number of fixed or learned global tokens for shared context propagation.
- Layer-specific candidate budgets: Use different top-k budgets across layers instead of applying excessive sparsity everywhere.
- Precision fallback paths: Enable denser attention for high-value requests or unusual inputs.
These mechanisms add some computation, but they can substantially reduce long-tail risk. In long-document question answering, codebase understanding, log analysis, and multi-hop retrieval, missing a critical piece of evidence can be more costly than the computation saved.
4.3 Evaluate training and inference separately
If the routing module participates in training, evaluation should consider how gradients pass through top-k selection, how candidate blocks remain load-balanced, and whether the candidate distribution during training matches that during inference.
If routing relies on approximate indexing or structures built offline, distribution shift must also be considered. Patterns that are common during training may not cover the long-tail inputs seen in production.
Regardless of the implementation, evaluation should include:
- Single-point retrieval: Can the system select a critical piece of evidence at a precise location in a long context?
- Multi-hop associations: Can it select multiple pieces of evidence that are far apart?
- Long-document aggregation: Does sparse selection introduce bias when many segments must be summarized?
- Code and structured text: Are cross-file and cross-function dependencies preserved?
- Adversarial and out-of-distribution samples: How stable is routing under rare patterns, repeated segments, and unusual sequence lengths?
5. An Implementation Checklist for Production
5.1 Profile each stage before changing the algorithm
Before optimizing the indexer, establish a reproducible baseline:
- Bucket inputs by length, such as 1M, 2M, 5M, and 10M tokens;
- Break execution into projection, routing scores, top-k, candidate gather, exact attention, and communication;
- Measure prefill and decode separately instead of hiding differences in a combined average;
- Record batch size, parallelism strategy, precision mode, and memory usage;
- Calculate the indexer’s share of time at both the single-layer and full-model levels.
Only after confirming that the indexer is a genuine hotspot and that candidate-search cost grows rapidly with context length should a more complex latent-space routing method be introduced.
5.2 Tune using recall-versus-cost curves
Block size, latent-space dimension, and top-k budget create a three-way trade-off:
- Larger blocks reduce routing overhead but may produce more candidates for exact attention after expansion;
- Smaller blocks provide finer granularity but increase top-k and index-management costs;
- Lower latent dimensions make scoring faster but may increase approximation error;
- Larger top-k values improve recall but increase exact-attention and gather costs.
Plot routing recall against single-layer latency, and define minimum recall requirements for different tasks. Do not select a configuration based only on speed or average accuracy. Long-tail queries and missed critical evidence may not be visible in aggregate metrics.
5.3 Prioritize operator fusion and memory layout
The gains from latent-space routing can be canceled out by an inefficient implementation. Engineering priorities should include:
- Fuse projection and scoring to avoid repeated intermediate-tensor reads and writes;
- Compute relevance in blocks to avoid materializing a complete score matrix;
- Keep candidate blocks contiguous where possible to reduce random gathers;
- Balance candidate counts and schedule workloads for variable-length batches;
- Reuse compressed block summaries instead of rebuilding them for every request;
- Use paged or segmented layouts for long-context caches to reduce memory fragmentation.
5.4 End-to-end rollout and fallback strategies are essential
Because LSA uses approximate candidate selection, production deployment requires controlled rollout:
- Compare against the original model in offline evaluation and shadow traffic;
- Use more conservative candidate budgets for extremely long inputs, low-confidence routing, and high-value requests;
- Monitor routing recall, task failure rate, time to first token, and generation throughput;
- Fall back to denser attention when input distributions fall outside the training or calibration range;
- Bind routing parameters to model versions to prevent accuracy drift between releases.
6. Limitations and Future Directions
LSA demonstrates the importance of indexer optimization, but it does not eliminate every cost associated with 10M-token contexts. Even when the attention layer itself is accelerated substantially, storing, reading, and communicating KV caches can still consume significant resources.
As contexts grow, cache management, memory bandwidth, and service scheduling may become the next bottlenecks.
Approximate routing also remains risky for tasks that require strict evidence coverage. Multi-hop reasoning, cross-document comparison, long-range code dependencies, and audit-oriented question answering all require the model to avoid missing critical segments.
Future work should therefore treat candidate-selection quality as a first-class metric rather than reporting only layer-level speedup.
A more practical direction is system-level co-design. Sparse routing, local windows, linear layers, global summaries, cache layouts, and service scheduling should be designed together. Attention budgets can be allocated dynamically across layers, heads, and request types, with end-to-end time to first token, throughput, memory usage, and task accuracy as the unified objectives.
Overall, competition in the 10M-token context era is moving beyond whether sparse attention can be implemented. The more important question is whether a system can find the right information at low cost and with high recall.
LSA offers a clear lesson: move indexing from full high-dimensional search into a lower-dimensional, hierarchical, coarse-grained latent space, then perform exact computation on a small candidate set. This can produce order-of-magnitude gains for single-layer prefill. Whether those gains translate into real business value depends on the indexer’s share of total execution time, routing recall, hybrid-attention design, and end-to-end evaluation.
For teams building long-context systems, measuring the bottleneck first and jointly tuning recall, latency, and memory is more reliable than pursuing a single headline speedup number.
