10-Million-Token Context: Cutting Sparse Indexing Overhead by Another 22×

    At multi-million-token lengths, sparse attention often spends most of its prefill time on candidate selection rather than exact attention. This article explains why full scoring inside the indexer recreates quadratic cost, how latent-space sparse attention replaces that search with coarse block routing, fine ranking, and exact attention, and how to train, measure, and engineer the indexer so recall and end-to-end accuracy stay close to full attention.

    10-Million-Token Context: Cutting Sparse Indexing Overhead by Another 22×

    As context grows from 1 million tokens toward 10 million, the first failure is often not that attention itself cannot be computed, but that the model loses control of which tokens to look at. Sparse attention has already shown that each query can attend to a small set of the most relevant keys and still approach full-attention accuracy. At extreme lengths, however, the indexer may still score every key to pick that small set, so the indexing stage falls back to quadratic cost. This article examines that bottleneck: the design logic of latent-space sparse attention, how its complexity changes, how to implement it, and how to evaluate it.

    1. The cost profile changes: sparse attention still has a hidden bill

    Full attention has a simple cost structure. With context length T, prefill scores every query against every historical key, about O(T²). During decoding, each new token interacts with the existing KV cache, about O(T). Growing the context from 1 million to 10 million tokens raises theoretical prefill attention compute by nearly 100×.

    Sparse attention splits the work: a lightweight indexer first selects k candidate keys for each query, then exact attention runs only on those k keys. Exact attention can therefore drop to O(Tk). The problem is that if the indexer decides relevance on the original high-dimensional token representations, it still scores every query against every key, so indexing remains on the order of O(T²). Reducing the scoring dimension, using lower precision, or merging keys into blocks can shrink the constant factor, but the quadratic trend remains.

    Public experiments make the point clearly: at 10 million tokens, about 98% of prefill time in some global attention layers is spent on candidate selection and the indexer, not on exact attention. Sparse attention shrinks the large attention matrix, then turns the routing decision into the new bottleneck.

    The sparse approach itself is not invalid. Public validation at 128K context shows that if each query keeps only its truly most relevant keys—about 512 keys, roughly 0.8% of all keys—long-context benchmarks can still retain about 98% of full-attention accuracy. Looking at a small subset is enough. What still needs solving is how to find that subset at sub-quadratic cost.

    2. Why indexers are hard to cheapen: recall and cost pull against each other

    The indexer is not the final attention computation. Its job is to make the candidate set contain the keys that actually matter. Two metrics constrain each other:

    • Candidate recall: how many of the truly important keys land in the candidate set. If recall is too low, stronger exact attention later cannot recover the miss.
    • Candidate-generation cost: higher recall usually means more dimensions, finer granularity, and more precise scoring, which raises cost.

    Common optimizations include lower indexer dimensions, low-precision scoring, compressing many keys into one block summary, and block-sparse candidates. These reduce constants. At tens of millions of tokens, indexing still grows roughly with T² as long as each query approximately scans the full set. The point of latent-space sparse attention is therefore not a lighter indexer on the same search space. It is a different search space: coarse-filter in a compressed latent space or block-summary space, fine-rank inside a small number of candidate blocks, then run exact attention only on the final top-k.

    3. The core of latent-space sparse attention: coarse filter, fine rank, exact attention

    Latent-space sparse attention can be read as a three-stage pipeline:

    1. Latent-space coarse filter. Map queries, keys, or KV blocks into a low-dimensional learned representation, producing block summaries or routing vectors. The query first finds a small set of candidate blocks in summary space, instead of scoring every original key pairwise.
    2. Fine ranking inside candidate blocks. Inside those blocks, score with a higher-dimensional representation or the original keys and select the final top-k keys.
    3. Exact attention with a hybrid fallback. Run exact attention only on the final keys, while keeping a local window, global tokens, or a linear-attention branch so local coherence and global information are not dropped.

    The pseudocode below is schematic. It describes the flow, not a specific interface:

    1. # Schematic: latent coarse filter + in-block fine rank + exact attention
    2. q_lat = project_query_to_latent(q) # [T, d_lat]
    3. block_summary = summarize_kv_blocks(k, v) # [N_block, d_lat]
    4. coarse_score = q_lat @ block_summary.T # [T, N_block]
    5. candidate_blocks = topk_blocks(coarse_score, r) # r blocks per query
    6. selected_keys = []
    7. selected_values = []
    8. for block in candidate_blocks:
    9. fine_score = q @ k[block].T # fine-grained scores inside the block
    10. idx = topk(fine_score, k_per_block)
    11. selected_keys.append(k[block][idx])
    12. selected_values.append(v[block][idx])
    13. # Exact attention only on candidate keys + local window + global tokens
    14. out = exact_attention(q, selected_keys, selected_values, local_window, global_tokens)

    If the number of blocks N_block is much smaller than T, coarse-filter cost is approximately O(T · N_block · d_lat), and exact attention is O(T · k · d). With a small latent dimension and a controlled number of candidate blocks, the overall cost can move below quadratic. Public experiments at 10 million tokens report about 22.7× prefill speedup for a single attention layer in one hybrid sparse architecture, and about 72.4× for another mid-scale long-context model, while accuracy on a series of tasks stays close to the original model. The gain is not a single constant-factor tweak. It comes from moving index search from pairwise comparison over all tokens to block-level or latent-space routing.

    4. Protecting accuracy: the indexer cannot be an after-the-fact patch

    For latent-space sparse attention to be usable, the indexer must be optimized jointly with the main attention, not attached as an approximate retriever after the main model is already trained. In practice, the following points matter:

    • Indexer supervision. Distill the indexer from the relevance distribution of full attention or high-precision sparse attention, so the coarse stage learns which blocks are worth looking at.
    • Recall monitoring. Offline, measure candidate-block recall and final top-k recall, and break the numbers down by task type. Retrieval-style tasks are more sensitive to recall; aggregation-style tasks are more sensitive to coverage.
    • Hybrid fallback. Keep a local window for nearby-token coherence, and keep global tokens or a linear-attention branch so distant information can still aggregate.
    • Training-distribution coverage. Long-context training samples should cover codebases, logs, multi-document question answering, multi-hop retrieval, and similar settings, so the indexer does not miss keys on out-of-distribution inputs.
    • Candidate redundancy. The number of coarse candidate blocks, r, should be slightly larger than the final k. Spend a little redundancy on recall, then compress with fine ranking.

    5. Engineering: hit the memory wall before chasing more compute

    At 10 million tokens, the indexer is often limited by both compute and memory bandwidth. Practical directions include:

    • Blocking and hierarchical summaries. Summarize KV in blocks so each query does not scan every key. Block size should be tuned together with hardware matrix-multiply efficiency and candidate recall.
    • Tiered KV cache. Keep original keys for hot data and compressed summaries or low-dimensional representations for cold data, reducing memory footprint and bandwidth pressure.
    • Low precision and batched matrix multiplies. Use lower precision for the coarse filter and higher precision for fine ranking, but measure how numerical error affects recall.
    • Candidate caching. Reuse candidate blocks across neighboring queries, using local correlation in long context to avoid repeated routing.
    • Parallelism. Pipeline block-summary generation, coarse filtering, fine ranking, and exact attention so no single stage becomes a serial bottleneck.

    When tuning, prioritize four variables: latent dimension, number of candidate blocks, block size, and final top-k. A latent dimension that is too small hurts recall; one that is too large erodes the speedup. Too few candidate blocks miss keys; too many raise fine-ranking cost. Blocks that are too large cut routing cost but lose granularity; blocks that are too small inflate the block count. Evaluation should cover prefill latency, decode throughput, memory use, candidate recall, and task accuracy—not single-layer speedup alone.

    6. Where it fits, and where it does not

    Latent-space sparse attention fits extremely long contexts where each query depends on a relatively sparse set of keys: large-codebase understanding, long-log analysis, multi-document retrieval and question answering, knowledge-base aggregation, and multi-hop reasoning. Tasks that need full exact coverage—token-level alignment, dense retrieval, or tightly constrained audit—should keep a high-precision fallback, and recall evaluation should confirm that sparse candidates do not drop critical evidence.

    Latent-space sparse attention is not free acceleration. It turns “the attention matrix is too large” into “is the router reliable?” Ten-million-token context becomes a stable service only when indexer recall, the hybrid fallback, and the engineering implementation all hold. The practical path is to profile long-context cost first and confirm that the indexer is the main time sink; replace full indexing with block-level latent coarse filtering; then shrink the candidate set under the constraints of recall and end-to-end task accuracy. A roughly 22× speedup obtained that way is not a paper number bought by giving up accuracy.