10M-Token Context: Speeding Up Sparse Attention with Latent-Space Indexing

    Sparse attention can preserve accuracy while looking at only a small subset of tokens, but its indexer still costs time that grows quadratically with context length—often dominating prefill at the 10M-token scale. This article explains how latent-space indexing addresses this by retrieving in a compressed representation before returning to the original tokens, cutting indexing complexity from O(T²) toward near-linear and reporting roughly 22.7x and 72.4x single-layer prefill speedups on two open-source models at 10M tokens. It covers where attention cost goes, why sparse attention works, the indexer's quadratic dilemma, the design trade-offs that preserve accuracy, seven engineering details for production, and how to validate the benefits in practice.

    1. From 1M to 10M: Sparse Attention Meets a New Bottleneck

    Pushing context from millions to tens of millions of tokens is no longer a niche research topic—it is an everyday requirement in production. Whole-repository code comprehension, clause-by-clause comparison of extremely long contracts, and global traceback across hundreds of conversation turns are all pushing “how much you can see at once” to a new order of magnitude. As a reference point in public technical developments: one cloud vendor has set 1M-token context as the default spec for its next-generation foundation model service; a model vendor’s subsequently released lightweight model also supports 1M-token context and, for the first time in its lineup, adopts a hybrid architecture combining sparse attention with linear attention. In short, “starting at 1M, exploring 10M” is becoming the shared roadmap of leading models.

    The underlying consensus of this roadmap is clear: a model does not need to—and should not—scan every historical token for every query. It only needs to pick out the few most relevant ones. The problem is that when the scale reaches 10 million tokens, an overhead that was once negligible begins to spiral out of control. One research team has publicly disclosed that at this scale, for a single global attention layer of an open-source model during prefill, about 98% of the time is spent not on the attention computation itself but on the indexing step of “deciding which tokens to look at.”

    This means the nature of the problem has changed. Sparse attention has repeatedly proven that “looking at only a small subset” is enough to preserve accuracy. What actually blocks ultra-long context is that: finding that small subset still costs time that grows quadratically with context length.

    To address this bottleneck, a research team proposed an approach—perform the retrieval in a compressed latent space, then return to the original tokens to execute attention, reducing the indexing step from quadratic complexity to sub-quadratic or even near-linear. Public results show that at 10M tokens, it speeds up the prefill of a single attention layer by roughly 22.7x and 72.4x on two open-source models with different architectures, while maintaining accuracy close to full attention on several long-context tasks. This article follows this thread, explaining the problem, the principle, and engineering practice layer by layer.

    2. First, Look at the Ledger: Where Does Attention Spend Its Cost?

    To understand the significance of this speedup, first break down the cost of attention.

    2.1 Full Attention: Prefill Is Quadratic, Decode Is Linear

    In standard full attention, every query must compute relevance against all previous keys. Let the context length be T and the hidden dimension be d, then:

    • Prefill stage (processing the entire input at once): the computation is roughly O(T²·d). Going from 1M to 10M tokens, the length becomes 10x, and the attention computation grows about 100x.
    • Decode stage (generating token by token): each generated token must interact with all historical keys, and the per-step computation is O(T·d), tied directly to the size of the existing KV cache.

    2.2 Sparse Attention: Reducing the Main Term from T² to T·k

    Sparse attention works by “division of labor”: a lightweight indexer first selects the k most relevant keys for each query, and then real attention is computed only over these k keys. So:

    • The main attention term drops to O(T·k·d), where k is typically 512–2048, independent of T;
    • If the indexer itself is implemented naively, it still has to score all T keys, costing O(T²·d’) (where d’ is the indexing dimension).

    In other words, sparse attention moves the quadratic term from “computing attention” to “finding attention”—it does not eliminate it. This is the premise for understanding all the optimizations later.

    2.3 Why “Looking at Only a Small Subset” Holds Up

    This approach rests on a premise: the model really only needs very few keys. Related research has provided a compelling validation: at 128k tokens, forcing each query to keep only its “truly” most relevant 512 keys (about 0.8% of all keys), the model still retained about 98% of full-attention performance on mainstream long-context benchmarks.

    This conclusion has several implications:

    1. Information demand in long context is highly concentrated, and the attention distribution is naturally sparse;
    2. The accuracy loss comes mainly from “missing key segments,” not from “looking at fewer of most tokens”;
    3. The recall quality of the indexer directly determines the accuracy ceiling of sparse attention.

    This explains why the industry is willing to invest significant engineering effort in the indexer—it is both a cost center and the linchpin of accuracy.

    3. The Essence of the Bottleneck: The Indexer’s Quadratic Dilemma

    3.1 An Inescapable Logical Loop

    For the indexer to know which 512 keys are most relevant, it must first score every key; to score every key, it must let the query interact with all keys. This forms a loop:

    1. To score all keys → must access all keys → cost grows linearly with T
    2. Every query does this → total cost grows quadratically with T → same order as full attention

    In other words, a naive indexer does not truly save asymptotic complexity; it merely swaps one expensive matrix multiplication for another cheaper one.

    3.2 Three Existing Engineering Compromises

    The industry has not been idle. The current mainstream approaches fall into roughly three categories:

    Strategy Approach Benefit Cost
    Lower numerical precision Indexer scores using FP8/INT8 or even lower bit widths Constant-factor speedup, half the bandwidth Scoring/ranking noise, nearby keys easily misordered
    Compress representation dimension Project keys to a very low dimension (e.g., below 64) for scoring Computation drops linearly with dimension Limited discriminative power in low dimension, lower approximate recall
    Block-level coarse aggregation Compress a run of 4 (or one block of) keys into a single representative for scoring Fewer scoring passes Intra-block position information lost, requires secondary correction

    These methods are indeed effective; in practice they can often cut the indexing cost by several times. But they share a common trait: they all optimize on the constant factor, while the complexity remains O(T²). When T grows from 1M to 10M, such optimizations can only delay the “loss of control” a bit—they cannot change the trend.

    3.3 A New Idea: Latent-Space Indexing

    Latent Sparse Attention (referred to here as latent-space indexing) takes a different angle: instead of trying to scan all keys more cheaply, it first builds a “representation space” much smaller than T, retrieves within the representation space, and then returns to the original tokens for precise attention.

    Its typical flow is:

    1. Build latent-space representations: compress the key sequence by block (learnable projection, mean pooling, cluster centers, etc.) to obtain M latent vectors, with M much smaller than T;
    2. Coarse filtering: score the query against all M latents and select the Top-N candidate blocks;
    3. Fine ranking (optional): do fine-grained scoring over original keys within candidate blocks to select the final k;
    4. Execute attention: compute softmax attention only over the finally selected keys.

    The cost of step 2 is O(T·M·d) (each query scans M latents, for a total of T queries), and step 4 remains O(T·k·d). The key difference is that M can be chosen to be weakly correlated or even independent of T, thereby reducing the indexing step from O(T²) to close to O(T).

    There is even more room here. The structure can be made multi-level: first scan coarse-grained super-blocks, then drill down to sub-blocks, and finally to tokens. If each level’s block size is B, the total cost can be written as:

    1. Indexing cost ≈ T · (T/B^L + L·k·B) L = number of levels

    Theoretically, taking B ≈ √T and L = 1 achieves O(T^1.5); with a fixed-capacity latent space (M constant), it degrades to approximately O(T)—which is exactly the origin of the “sub-quadratic” name for this goal.

    4. Why Latent-Space Indexing Still Preserves Accuracy

    Saving cost is easy; losing accuracy is the real problem. The latent-space approach manages both thanks to three design trade-offs:

    First, coarse filtering is only responsible for “not missing,” not for “ranking precisely.” The latent representation is used to recall the candidate set, and the final ranking is still done on the original keys. This decouples “approximate retrieval” from “precise ranking”—coarse filtering can be rough, but fine ranking must be accurate.

    Second, the latent-space representation is learnable, not fixed pooling. Mean pooling erases local peaks, whereas a learnable projection lets the latent retain the directions most discriminative for relevance. This also means latent-space indexing usually needs to be jointly optimized with the main model during training or lightweight fine-tuning, rather than being a pure inference-time add-on.

    Third, the candidate-set budget is an adjustable accuracy knob. Given k = 512, coarse filtering can recall 1024 or even 2048 candidates, pushing recall close to 1, at the cost of computing a bit more in the fine-ranking stage. This leaves room for accuracy/speed trade-offs across different tasks.

    From public results, this combination achieved single-layer prefill speedups of roughly 22.7x and 72.4x on two models at 10M tokens, while maintaining accuracy close to full attention across multiple tasks—showing that the “coarse filtering + fine ranking” division of labor is indeed effective.

    5. Engineering Practice: Seven Details That Must Be Handled

    The speedup ratios in papers are often built on idealized implementations. To actually put such a scheme into a production inference stack, the points below determine how much real-world benefit you can capture.

    5.1 The Recall of Coarse Filtering Must Be Measured

    It is advisable to monitor “recall @ candidate-set size” as a first-class metric: whether the candidate set selected by coarse filtering contains the vast majority of full-attention’s Top-k. This metric surfaces problems earlier than end-to-end accuracy and is easier to attribute.

    5.2 The Construction of Latent-Space Representations Should Be Amortizable

    If latents must be reconstructed at every prefill, the cost itself is also O(T). Feasible approaches include: making the construction highly parallel and overlapping it with the main compute stream, or caching and reusing it in supported scenarios (e.g., multi-turn Q&A over the same document).

    5.3 Coordinate with Quantization, Don’t Just Stack It

    Using low precision for the indexer is almost inevitable, but note the isolation of the numerical path from main attention: using FP8/INT8 for the indexing stage is fine, but the final softmax should still be done in BF16/FP16 to avoid ranking noise propagating into the output.

    5.4 Fuse Precise Operators

    The indexing stage involves many small-scale scoring and Top-K operations, easily dragged down by kernel launch overhead and irregular memory access. In practice, this usually requires: fusing “scoring + block-level Top-K” into a single kernel; using approximate Top-K (e.g., block-max filtering) instead of a global sort; and gathering candidate keys before entering the attention kernel to reduce intermediate tensors spilling to disk.

    5.5 Block-Level Pipelining to Overlap Indexing with Attention

    During prefill, queries are processed by block. You can overlap the indexing of block i with the attention computation of block i-1, hiding indexing latency inside the compute bubbles. In large-scale long-context prefill, this often brings more direct wall-clock benefit than the algorithm itself.

    5.6 Dynamic Budget: Don’t Spend the Same on Every Query

    Queries at different positions differ enormously in their need for information. You can assign a smaller k to content-type tokens and a larger k to key tokens (e.g., retrieved anchors, special markers), trading average budget for overall throughput.

    5.7 Natural Fit with Hybrid Architectures

    Sparse indexing solves the cost of “global attention layers,” while hybrid architectures (global layers + linear layers / local-window layers) themselves reduce the number of global layers. When the two are combined, the fewer the global layers, the more the indexing step’s share of the entire prefill is amplified—which is exactly why, on models with a high proportion of global layers, the leverage of index optimization is greater.

    6. How to Validate the Benefits in Production

    If you are evaluating this kind of capability, it is advisable to validate in the order below to avoid being misled by a single speedup ratio:

    1. Baseline alignment: first get a full-attention baseline with the same configuration running, and record prefill time, peak GPU memory, and time to first token (TTFT);
    2. Layered attribution: separately measure the time share of “attention computation,” “indexing,” and “other” to confirm the bottleneck really lies on the indexing side, then judge whether the optimization is on target;
    3. Accuracy comparison: cover at least three task types—single-point information retrieval (needle-in-a-haystack), multi-hop aggregation (reasoning across multiple segments), and global summarization (needs to cover the whole text). Sparse schemes are most likely to lose points on the third, because it relies on long-range coverage rather than local hits;
    4. Stress curve: plot the time curve at several tiers—64k/256k/1M/4M/10M—to see whether it truly shifts from “quadratic” to “close to linear”; a single speedup ratio cannot demonstrate asymptotic complexity;
    5. Engineering regression: confirm long-term stability, no memory leaks, and no throughput collapse under concurrency.

    7. Conclusion

    Sparse attention’s historical contribution was proving that “long context” does not mean “computation must be expensive.” But it also left a new bill: the cost of finding key tokens grows quadratically with length. The value of latent-space indexing lies not in any specific multiple, but in moving this problem from “how to save on the constant” to “how to change the order of complexity.”

    For teams building long-context applications, the pragmatic conclusions are three: first, the indexing step deserves to be treated as a first-class optimization target in its own right, not a free add-on to attention; second, the “coarse filtering + fine ranking” division of labor is a general engineering paradigm, not limited to any particular model structure; third, any speedup must be backed by recall and multiple types of long-context tasks, or the saved compute will be paid back in the form of accuracy.

    Bringing ultra-long context to production on the Baidu AI Cloud Qianfan platform also requires supporting engineering: an elastic compute resource pool to absorb the peak pressure of the prefill stage, model serving and inference acceleration to optimize time to first token, and logging, monitoring, and alerting systems to track changes in per-stage time and recall metrics. Chaining these together is what turns “10M tokens” from a paper metric into a stable business capability.