10M-Token Contexts: Breaking the Sparse Attention Indexing Bottleneck

    Long-context inference has shifted from 1M to 10M token windows, and at that scale the bottleneck is no longer compute — it is retrieval. This article breaks attention cost into scoring (indexing) and reading (attention compute), shows why block-sparse and low-precision indexing schemes only lower the constant while staying O(T²), and introduces latent-space retrieval: compress T keys into M = o(T) latents, retrieve in that space, then read back in the original token space. It covers the complexity comparison, coarse-to-fine two-stage retrieval, hybrid layer design, the three types of evidence needed to validate accuracy, reported single-layer prefill speedups, real-world trade-offs, and a practical checklist for making ultra-long-context serving stable.

    1. When Context Goes from 1M to 10M, the Cost Structure Inverts

    Over the past year or two, long context has become a standard feature of LLM serving. Mainstream services now treat a 1M-token context window as the default spec, and the architectural evolution that followed has generally adopted hybrid layer designs mixing sparse attention with linear attention (or gated convolutions). All of these approaches start from the same premise: stop making every query traverse the entire history of tokens, and instead select a few of the most relevant segments to participate in the computation.

    This approach has been validated repeatedly at the 1M scale. The problem appears when you keep pushing upward. As context grows from 1 million to 10 million tokens, an overhead that once looked negligible starts to spiral out of control.

    Consider one telling measurement. On a global attention layer of a 1M-class context model, during prefill over 10M tokens, roughly 98% of the time was spent not on the attention computation itself, but on the indexer that decides which tokens to look at. That number leads to a counterintuitive conclusion: at this point, retrieval is the constraint, not compute.

    The nature of the problem therefore changes. Sparse attention has already proven that “looking at only a small fraction” is enough to preserve accuracy. What actually blocks ultra-long context is something else: finding that small fraction still grows quadratically with context length.

    2. Attention Cost Splits into Two Distinct Things

    Understanding this bottleneck requires splitting the attention overhead into two phases.

    Phase 1: Scoring (retrieval). The indexer must score the relevance between each query and every candidate key, then take the top-k. Scoring every key requires traversing the entire key sequence. At context length T, this phase is O(T²) — the same order as full attention.

    Phase 2: Reading (computation). The actual attention runs only over the k selected keys, costing O(T·k). k is typically in the hundreds to thousands, which is constant-level relative to T.

    This leads to an awkward conclusion: sparsification reduced Phase 2 from quadratic to linear, yet left Phase 1 almost entirely intact. At T = 128k, the constant in Phase 1 is small enough that the overall gain is substantial. When T climbs to 10M, the quadratic term regains dominance, and on the retrieval side the sparsification was nearly wasted effort.

    Approach Retrieval cost Reading cost Total complexity
    Full attention — O(T²) O(T²)
    Naive block sparse / low-precision indexing O(T²) O(T·k) O(T²)
    Latent-space retrieval + sparse reading O(T·M), M = o(T) O(T·k) Sub-quadratic

    One engineering detail deserves emphasis: the indexer is typically memory-bandwidth bound rather than compute bound. It has to stream through the entire key sequence, and the access pattern is large-range, fine-grained reads. Wall-clock time is determined by memory bandwidth and cache behavior, not FLOPs. So even if the indexer accounts for a modest share of theoretical FLOPs, it can consume the vast majority of actual elapsed time — one reason behind that 98%. In a memory-bound regime, any optimization that only reduces the constant yields even smaller returns.

    3. “Looking at Just 0.8% Is Enough” Has Already Been Validated

    It is worth stressing that the accuracy ceiling of the selection strategy itself is very high. A relevant experiment performed an oracle-style validation: at 128k tokens, letting each query look at only the 512 keys that are “truly” most relevant to it — about 0.8% of all keys — the model still retained roughly 98% of full-attention performance on comprehensive long-context benchmarks.

    The implication is significant: accuracy loss does not come from “looking at too little,” but from “finding the wrong ones.” The optimization goal then becomes very clear — preserve selection quality while compressing selection cost from quadratic to sub-quadratic.

    4. Existing Mitigations: Lowering the Constant, Not the Order

    Industry block-sparse approaches have explored several paths. Their common trait:

    • Lowering scoring precision: computing relevance scores with low-bit or low-precision representations in exchange for higher throughput.
    • Compressing the scoring dimension: projecting d-dimensional representations down to a very small dimension before the dot product.
    • Packing representative vectors: compressing a run of consecutive keys into a single block-level representation, then refining within the block.
    • Sharing indexes across heads/layers: multiple attention heads or adjacent layers reuse the same selection result, amortizing the scoring work.
    • Hybridizing with linear attention: some layers replace retrieval with fixed state updates, reducing the number of layers that need retrieval at all.

    These are all correct engineering trade-offs, but they converge on the same lever: lowering the per-score cost, while the number of scores remains O(T²). At 1M context, the quadratic constant is small enough that the problem is masked. At 10M, constant-factor optimization cannot win against growth in the order. What is needed is a change of order.

    5. The Breakthrough: Decoupling Candidate Set Size from Context Length

    The core idea can be stated in one sentence: do not perform retrieval in the original token space.

    Concretely, the flow becomes three steps.

    Step 1: Build a latent candidate set. In a single linear pass, compress T keys into M latent representations. The compression can be segmented pooling, low-rank projection, or a learnable compression head. The key constraint is that M must grow sub-linearly with T (for example, on the order of √T), so retrieval cost becomes O(T·M) = o(T²) and the overall algorithm enters the sub-quadratic regime.

    Step 2: Retrieve in latent space. Score the query against the M latents with a dot product and take the top-m latents. Since M is far smaller than T, this step is close to linear in practice, and the access pattern is regular and hardware-friendly.

    Step 3: Read back in the original space. Using the ownership mapping between latents and original tokens (typically “one latent corresponds to one contiguous block”), expand the selected latents into the corresponding original key positions, then run the real sparse attention over those keys.

    Why does latent-space retrieval hold up in accuracy? The original key sequence contains substantial local redundancy — the representations of adjacent tokens are highly correlated. Folding them into a small number of representations loses far less information than the sequence-length reduction gains. At the same time, compressed representations group semantically similar tokens into the same region, which is exactly the property retrieval needs: it turns relevance search from “comparing against T candidates one by one” into “locate among M regions first, then refine within a region.”

    Why can’t naive pooling be used carelessly? Mean pooling flattens fine-grained signals, which is especially unfriendly to tasks like exact string matching and single-point information localization. In practice, three forms of compensation are needed: use a learnable compression head rather than fixed pooling; retain multi-resolution candidate granularity (coarse-grained localization plus a finer-grained re-check); and apply over-retrieval — select more latents than theoretically required, leaving headroom for recall.

    6. Illustrative Implementation and Complexity Comparison

    The pseudocode below illustrates the complexity structure only. It is not a directly runnable implementation.

    1. def lsa_attention(q, K, V, compress, M):
    2. # 1) One pass: compress T keys into M latents, with M = o(T)
    3. Z = compress(K) # (T, d) -> (M, d)
    4. # 2) Retrieve in latent space: O(T_q * M) instead of O(T_q * T)
    5. s = q @ Z.transpose(-1, -2) # (T_q, M)
    6. top_m = topk_index(s, m) # m latents per query
    7. # 3) Map latents -> original token positions (block- or bucket-level)
    8. idx = block_map.gather(top_m) # (T_q, m * b), b = tokens per block
    9. # 4) Read only over the selected original keys
    10. return sparse_attn(q, K.gather(idx), V.gather(idx))

    This can be extended into a coarse-to-fine, two-stage retrieval: first locate m candidate blocks among the M latents, then perform fine-grained scoring only inside those m blocks. The second stage costs O(T·m·b), which keeps overall retrieval cost linear when m and b are constants. This pattern is structurally identical to the mature inverted-index / coarse-then-fine ranking approach in vector retrieval, so existing infrastructure can often be reused with little effort.

    Layered design matters just as much. A practical arrangement mixes layer types: most layers go through latent-space retrieval, while a few layers retain global or linear attention to keep information flowing back through the deeper stack; local window attention is paired in to handle nearby dependencies. This mixture ensures long-range information does not depend on a single retrieval path, which visibly improves stability.

    7. How Accuracy Is Validated: Three Kinds of Evidence

    When evaluating an approach of this kind, it is worth requiring three kinds of evidence simultaneously — none can be skipped.

    1. Comparison against oracle selection (ceiling validation): replace the indexer with the true top-k to see how much accuracy headroom exists, then run the real indexer and measure how small the gap is. A small gap indicates retrieval is not the weak link.
    2. Recall metrics (process validation): the overlap between the selected token set and the true top-k, plus the fraction of cases where “the key information falls inside the selected set.” This localizes whether failure occurs at compression, retrieval, or read-back.
    3. Downstream tasks (result validation): single-hop retrieval, multi-hop reasoning, aggregation/statistics, long-document QA, and repository-level code understanding should each be covered, because different tasks depend very differently on “fine-grained matching” versus “global aggregation.”

    The reported results in the relevant work are as follows: at the 10M token scale, prefill for a single attention layer achieved roughly 22.7x and 72.4x speedups on two open-source models of different sizes, while retaining accuracy close to the original model across a range of long-context tasks. This figure needs to be read correctly — it is a single-layer, prefill-phase local measurement. End-to-end speedup also depends on inter-layer communication, feed-forward networks, memory capacity, and IO, and should not be extrapolated directly into a whole-model speedup.

    8. Costs and Applicability Boundaries

    Stating the boundaries honestly is more valuable than overstating the gains.

    • Training support is required. The compression head usually needs joint training with the main model, or at least post-training fine-tuning. Pure inference-side modification saves compute but sacrifices recall quality.
    • Sensitive to exact-match tasks. Rare strings and exact numeric lookups in very long documents are where compressed representations most easily lose points, requiring multi-resolution and over-retrieval compensation.
    • Unnecessary for short contexts. At 128k and below, the constant of naive block sparse is already low enough, and introducing latent-space retrieval only adds complexity. The benefit grows with T; the 10M range is its main battleground.
    • Higher engineering complexity. An additional layer of compression and mapping logic means more costly debugging and performance analysis, and it requires the ability to attribute latency per layer.

    9. Deployment Checklist: Making Ultra-Long-Context Inference Stable

    If you want to evaluate this class of optimization in your own inference stack, work through the following in order.

    1. Do latency attribution before optimization. In your logging service or distributed tracing, record latency and peak memory per layer and per phase (compression / retrieval / read-back) to confirm the bottleneck really is on the index side. Optimization without attribution data is guesswork.
    2. Add hot/cold tiering to the KV cache. Under ultra-long context, cache size is the dominant cost item. Cold data can be offloaded to block or object storage, hot data kept locally, with chunk granularity designed to reduce read-back amplification.
    3. Separate prefill and decode deployment. Prefill is compute-intensive and parallelizable; decode is memory-intensive and latency-sensitive. Scaling the two workloads independently on a container platform keeps time-to-first-token under control more easily than a mixed deployment.
    4. Match context parallelism to the retrieval pattern. The communication pattern of latent-space retrieval differs from full attention, so the sharding strategy must keep the ownership of each latent as local as possible, avoiding frequent cross-node fetches.
    5. Put the metrics into monitoring and alerting. At minimum, cover: time-to-first-token, prefill throughput, share of time spent in the index phase, recall proxy metrics (such as key-information hit rate), and memory water level. Index-phase share is the most sensitive early-warning signal.
    6. Build an accuracy regression suite. Use small-scale, short-context runs as the regression baseline and long-context benchmarks as the extension validation, ensuring that any adjustment to compression parameters does not silently change model behavior.

    Conclusion

    The next hurdle for ultra-long context is not whether the model can “fit it all in,” but whether it can cheaply find where to look. Sparse attention solved the quadratic in compute, but relocated the quadratic to the retrieval side. The real breakthrough is decoupling candidate set size from context length — localize in latent space, read back in the original space. With that in mind, evaluating any long-context approach comes down to one standard question: is its retrieval cost O(T²) or o(T²)? Only then do constants and hardware efficiency matter.