Indexing Acceleration Practices for Ten-Million-Token Long-Context Sparse Attention
As context windows scale from millions to tens of millions of tokens, the primary bottleneck for engineering teams shifts from "the model cannot remember" to "prefilling is suddenly unaffordable." While sparse attention reduces the overhead of exact attention by allowing each query to attend to only a few relevant tokens, it does not automatically eliminate the hidden cost of finding those tokens. This article explores the cost structure reversal in large-scale prefilling, detailing a three-tier indexing design (local, coarse, and fine selection), reference implementation, training and precision alignment strategies, system engineering optimizations, evaluation methodologies, and deployment strategies for massive context scenarios.
As context windows scale from millions to tens of millions of tokens, many teams first encounter the issue not as “the model cannot remember,” but as “prefilling is suddenly unaffordable.” Traditional dense attention requires calculating relevance between each query and all historical tokens, causing computation and memory access to expand rapidly with sequence length. Sparse attention significantly reduces the overhead of the exact attention phase by “letting each query see only a small number of the most relevant tokens.” However, it does not automatically eliminate another, more hidden cost: how to find these few tokens.
Public materials detailing ten-million-token experiments have given a clear signal: after reconstructing the indexing path on certain global attention layers, single-layer prefilling can achieve roughly 20x or even dozens of times acceleration, though results vary widely across different model architectures, layer positions, and evaluation configurations. What truly deserves attention is not a specific multiplier, but the reversal of the cost structure. When the sequence is long enough, the indexer—the module that decides “which historical tokens to look at”—may occupy most of the prefilling time, far exceeding the attention multiply-accumulate operations themselves. At this point, continuing to optimize only matrix multiplication yields limited returns; the “candidate selection” process itself must be redesigned.
1. Why the Cost Structure Reverses at the Ten-Million Scale
Assume a sequence length of $n$, a hidden dimension of $d$, and each query ultimately retaining $k$ tokens. The primary computation of dense attention is approximately $O(n^2d)$; sparse attention reduces the exact phase to $O(nkd)$. Since $k$ is much smaller than $n$, this seems highly beneficial. However, if candidate selection still requires each query to scan all historical tokens, the indexing process complexity is approximately $O(n^2r)$, where $r$ is the dimension of the index’s low-dimensional representation. Even if $r$ is only 32 or 64, when $n$ reaches tens of millions, $n^2$ is an astronomical figure that cannot be ignored.
More critically, the indexer is typically not a high-arithmetic-intensity matrix multiplication. It often involves numerous low-dimensional dot products, sorting, threshold comparisons, block lookups, and irregular gather operations. These operations are unfriendly to cache and memory access, and easily generate intermediate score matrices. If the implementation materializes the “query × historical token” relevance scores completely—even if only retaining a portion—it will cause massive memory consumption and bandwidth pressure.
Therefore, in ten-million-scale prefilling, the common time consumption distribution shifts from “attention computation dominating” to “candidate selection dominating.” This can be understood as three phases:
- Encode queries: Generate a low-dimensional representation for retrieval for each query.
- Coarse screen history: Find candidates among block summaries, cluster centers, or low-dimensional key spaces.
- Exact lookback: Perform full-precision attention computation only on the shortlisted few tokens.
The first and third phases can be optimized through operator fusion, low precision, and high parallelism. The second phase is the new bottleneck for ultra-long contexts. Without a hierarchical structure, each query still needs to score all historical blocks one by one. Although the complexity is reduced by the block size, it remains significant at the ten-million-scale length.
2. Splitting “Finding Relevant Tokens” into Three Tiers
A more scalable design splits the indexer into three tiers: “local, coarse, and fine.” The local tier ensures nearby information is not lost; the coarse tier compresses ten-million-scale history into a few hundred block candidates; the fine tier performs token-level selection within the candidate blocks. The final exact attention only processes tokens in the shortlist.
2.1 Latent Space Projection and Block Summaries
Let the query vector be $q_i$ and the historical key vector be $k_j$. Two low-dimensional projection matrices, $P$ and $Q$, can be introduced to compress the query and key into a latent space:
$q’_i = P q_i$
$k’_j = Q k_j$
Block-level summaries can be represented using the mean of intra-block key vectors, cluster centers, or learnable summary representations. For the $b$-th historical block, let its summary be $c_b$, then the coarse screening score can be written as:
$s_{i,b} = \langle q’_i, c_b \rangle / \sqrt{r}$
Here, $r$ is the latent space dimension. Since the number of $c_b$ is approximately $n / \text{block_size}$, the coarse screening complexity drops from $O(n^2)$ to approximately $O(n \cdot n / \text{block_size} \cdot r)$. When the block size is set to several thousand or larger, the coarse screening scale decreases significantly. However, larger blocks mean coarser granularity of intra-block candidates, potentially bringing many irrelevant tokens into the exact phase. Therefore, a two-level summary is usually required: large blocks for fast regional location, and sub-blocks for fine splitting.
2.2 Query Blocking and Candidate Sharing
The characteristic of prefilling is that all queries are known simultaneously, providing room for engineering optimization. If each query individually scans all block summaries, the computation remains heavy. Adjacent queries can be divided into query blocks, first calculating the coarse screening results of a representative vector for that query block to obtain shared candidate regions, and then performing token-level fine screening for each query within the region.
This approach requires preventing “representative vector bias.” For example, if a query block contains questions on different topics, using only one central vector for retrieval might miss historical segments needed by some queries. A safer approach is to retain multiple query probes, take their union, and re-rank for each query; or allow different heads to share different candidate sets based on attention head differences. The more aggressive the sharing, the higher the system efficiency, but the greater the recall risk, requiring calibration through evaluation.
2.3 Exact Lookback from Coarse to Fine Screening
After selecting candidate blocks, token-level fine screening is required within the blocks. Fine screening does not need to use full-scale low-dimensional scanning; it can just compare tokens within candidate blocks, combined with the local window, initial tokens, and previously selected lower-layer tokens to form the final shortlist. The final attention is:
$\text{Attn}_i = \text{softmax}(Q_i K_S^T / \sqrt{d}) V_S$
Where $S$ is the shortlist. The shortlist usually consists of three parts:
- Local window: The most recent few tokens, ensuring grammar and short-range dependencies.
- Coarse candidates: Highly relevant regions from latent space block summaries.
- Stable anchors: A few tokens at the sequence’s beginning or specific positions, used to maintain global stability.
After concatenating the three parts, causal masking must be strictly observed to ensure that query positions cannot access future tokens. For decoder-only structures, the causal constraint changes the availability of block summaries: a query can only use the complete summary of its left-side historical blocks; the right-boundary block may only contain a partial prefix, requiring intra-block masking and incremental summaries.
3. Reference Implementation for a Global Attention Layer
The following pseudo-code illustrates the core process. It only expresses the structure and does not represent a specific product interface or parameters.
Function Long_Context_Attention(Query Q, Key K, Value V, Local_Window L, Block_Size B, Candidate_Blocks M):# Q, K, V shape schematic: [sequence_length, hidden_dimension]# Block summaries can be precomputed offline or incrementallyBlock_Summaries = Build_Block_Summaries(K, B) # [num_blocks, latent_dim]Local_Results = Local_Attention(Q, K, V, Window=L)Global_Results = Initialize_Empty_ResultsFor each Query_Block QB partitioned by step M_q:Query_Latent = Project_Queries(QB) # [query_block_size, latent_dim]Coarse_Scores = Query_Latent × Block_Summaries^T # Avoid constructing full n×n matrixCandidate_Blocks = TopM(Coarse_Scores, M, Causal_Constraint=True)Candidate_KV = Gather(K, V, Candidate_Blocks)Candidate_Tokens = Intra_Block_Fine_Screen(Query_Latent, Candidate_KV)Shortlist = Concatenate(Local_Tokens, Candidate_Tokens, Anchor_Tokens)Global_Results[QB] = Exact_Attention(QB, Shortlist)Return Fuse(Local_Results, Global_Results)
There are several easily overlooked implementation details in this workflow:
First, block summaries should ideally be built only once and reused across multiple query blocks. If summaries are rebuilt for every query block, the indexing cost will re-inflate. Second, coarse screening scores should not be fully materialized to disk. Top-k should be maintained on-the-fly during tiled matrix multiplication, or using streaming heaps, bucketing, and threshold pruning. Third, candidate gathering introduces irregular memory access, requiring the key-value cache to be organized contiguously by block and allowing the same batch of queries to share the same set of candidate blocks as much as possible. Fourth, the softmax fusion for exact attention must be numerically stable. Local and global results should be fused using a log-sum-exp approach to avoid numerical deviations caused by simple weighting.
4. Training and Precision Alignment Cannot Be Skipped
If a new indexing path simply replaces the existing model’s sparse attention, inference speed may increase, but precision may not remain stable. The reason is that the original model has adapted to a certain visible range during training, and new candidate selection changes the information distribution. Engineering typically employs three approaches:
First, replace the indexing path only in a few global layers, keeping the original structure for the rest. This controls risk and facilitates tracing the source of benefits. Second, use dense attention or the original sparse attention as a teacher to distill the new routing module. The student model should learn not only the final output but also the quality of the candidate set—for example, ensuring that shortlisted tokens cover the teacher’s high-weight tokens. Third, incorporate recall-oriented auxiliary objectives. Directly optimizing top-k is non-differentiable; soft sorting, sampling approximation, or piecewise ranking loss can be used so that the index representation focuses more on “whether high-attention tokens enter the shortlist” rather than just fitting a rough score.
During training, attention must also be paid to length curriculum. An indexer trained on short sequences may not handle the block distribution differences at the ten-million-scale position. Curriculum learning from short to long can be adopted, gradually increasing the number of blocks, candidates, and length; while retaining a certain proportion of the full attention path to prevent indexer collapse. For scenarios where the main model is completely frozen and only inference optimization is performed, a fallback strategy should be set: when abnormal candidate recall is detected, allow certain layers or requests to degrade to a more conservative local-plus-coarse strategy.
In terms of precision, index projection and coarse screening scores can use lower bit-widths to improve throughput, but the final attention shortlist should maintain the same numerical format as the main model. Low precision alters top-k rankings, especially when many scores are close. Risks can be mitigated through calibrated thresholds, retaining boundary candidates, or re-ranking scores, rather than simply compressing all intermediate results to the lowest precision.
5. System Engineering Optimization Priorities
Indexing optimization for ten-million-scale contexts is not just an algorithm problem, but also a data layout and kernel fusion problem. Efforts can focus on the following directions:
- Contiguous Block Storage: Organize the key-value cache by block, with block summaries and intra-block tokens stored contiguously. After candidate selection, the gather operation only processes contiguous blocks, reducing random memory access.
- Fused Projection and Coarse Screening: Fuse query projection, block summary dot products, and top-k maintenance as much as possible to avoid writing intermediate score matrices to memory. Utilize tiled matrix multiplication and maintain candidate sets in on-chip caches.
- Shared Summaries and Hierarchical Caching: Update block summaries incrementally only as history grows; for multi-turn conversations and streaming requests, cache computed summaries and candidate indices to avoid repeated prefilling.
- Query Bucketing: Bucket queries based on query block length, candidate count, and proximity to the sequence start to avoid long-tail waiting in variable-length batch processing. Short requests take a low-overhead path, while ultra-long requests enable hierarchical indexing.
- Causal Block Pruning: For each query block, scan only its left-side complete blocks and handle the right boundary separately. Utilize block-level upper-bound estimation to pre-exclude regions that cannot enter top-k.
- Candidate Budget Control: Dynamically adjust the number of candidate blocks per layer based on total token count, layer count, and latency targets. Shallow layers can retain more global candidates, while deeper layers tighten the budget, preventing all layers from using the same expensive configuration.
- Monitor Irregular Overheads: In addition to matrix multiplication throughput, record gather counts, block summary hit rates, top-k re-ranking time, candidate block duplication rates, and memory bandwidth usage. Many acceleration failures are not due to insufficient compute, but because candidate gathering saturates the bandwidth.
6. Evaluation and Online Observability
When evaluating such solutions, looking only at average accuracy is insufficient. It is recommended to cover at least four categories of metrics:
The first category is end-to-end task metrics, including long-document QA, summarization, code repository understanding, multi-turn dialogue, and structured data retrieval. The second is index quality metrics, such as the recall rate of the candidate set relative to dense attention high-weight tokens, top-k overlap, and candidate diversity across different attention heads. The third is system metrics, including prefilling latency, time to first token (TTFT), throughput, peak memory, and p99 latency under different length buckets. The fourth is robustness metrics, including scenarios where evidence is located at a distance, surrounded by numerous distractors, conflicting evidence exists, or mid-sequence information loss occurs.
An easily overlooked practice is to separate “candidate recall” from “final answer accuracy.” If recall has dropped but answer accuracy remains temporarily unchanged, the current task may simply be easy; once deployed to more complex corpora, risks will quickly surface. Conversely, if recall is high but latency has not decreased, it indicates that the bottleneck may have shifted to exact attention or data movement. At this point, block size, candidate count, and layer replacement ratio should be revisited.
7. Deployment Strategy and Risk Boundaries
This type of acceleration is more suitable for scenarios involving ten-million-scale, long documents, multi-turn history, and large-scale offline analysis. In shorter contexts, the indexer’s own overhead may exceed the exact attention savings, so a length threshold should be set. For tasks requiring high audit or high-precision retrieval, both a “high-precision mode” and an “accelerated mode” should be provided; the high-precision mode retains more candidates or falls back to more conservative computation for critical layers.
It should also be noted that latent space coarse screening is an approximate method. It offers efficiency advantages in most natural language scenarios but cannot guarantee the same recall for arbitrary adversarial inputs. Engineering-wise, three layers of protection can be set: validate with long-context benchmarks and synthetic stress tests offline; monitor candidate recall proxy metrics and abnormal requests online; and retain a fallback path during service. Only by building “detectable, fallback-able, and rate-limitable” mechanisms into the system can sparse routing achieve production readiness.
8. Conclusion
The core contradiction of ten-million-scale long contexts has shifted from “whether to look at only a small portion of tokens” to “how to find this portion of tokens with sufficiently high recall and sufficiently low cost.” Merely optimizing attention multiply-accumulate operations cannot solve the problem of the indexer expanding with historical length. A more feasible route is: compress queries and historical blocks using low-dimensional latent space representations, reduce the scanning range from ten-million-scale to a few hundred candidates using hierarchical block summaries, and then ensure quality through intra-block fine screening and exact attention; simultaneously suppressing system overhead with query blocking, candidate sharing, incremental summaries, low-precision coarse screening, and candidate budget control.
What truly determines the success or failure of the solution is not the nominal acceleration multiplier, but the balance among index recall, end-to-end precision, tail latency, and maintenance complexity. Designing, observing, and providing fallbacks for the indexing path as a first-class citizen is the only way to run fast while maintaining controllable accuracy and engineering stability at the ten-million-token scale.
