10M-Token Context: The Hidden Cost of Sparse Attention and How to Fix It

    As context windows climb from millions toward tens of millions of tokens, attention's real bottleneck shifts from computing scores to finding which tokens to score. This article breaks down why the indexer, not the attention math, dominates prefill time, then explains latent sparse attention, a CPU-like multi-level retrieval structure that moves candidate selection into a low-dimensional space. It covers the cost model, a three-level retrieval design with reference code, why lossy indexing still preserves accuracy, six precision safeguards, engineering tactics for turning complexity wins into throughput, and a decision guide for choosing the right configuration.

    Introduction: From Millions to Tens of Millions, the Attention Bill Quietly Changed Its Name

    Over the past couple of years, long context has been one of the main tracks of model capability iteration. Work has moved from document QA over hundreds of thousands of tokens, to million-token-level code repository analysis and multi-turn ultra-long conversations, and “feed in an entire book, or an entire project, at once” is gradually moving from demo to daily reality. After mainstream flagship models established million-token context as the default spec, pushing the threshold one level higher became the next stop: ten-million-token-level context.

    The most important judgment here is this: in ten-million-level context, what actually consumes time is usually not the attention computation itself. In today’s multi-layer architectures, only some attention layers cover the global context, while the rest are mostly sliding-window attention. Related papers decomposed a single global attention layer of a million-context-scale model: during the prefill of 10 million tokens, roughly 98% of the time is spent in the indexer. The indexer’s job is to decide, for each query, “which tokens should I look at.”

    This observation changes the nature of the problem. Sparse attention has repeatedly shown that “looking at only a small subset” is enough to preserve accuracy. What really blocks ultra-long context is the act of “finding that small subset”: it still grows with the square of the context length, so indexing has become the hidden bill of long-context inference.

    To keep references consistent in what follows, here are the notation conventions:

    Notation Meaning
    T Context length (number of tokens)
    d Model hidden dimension
    h Number of attention heads
    d_h Per-head dimension, d = h·d_h
    r Index block length, i.e., the block-level compression ratio
    k Number of tokens that ultimately participate in attention per query (the sparse budget)
    d_l Dimension of the latent space used for indexing

    1. Cost Structure: Why “Selecting” Costs More Than “Computing”

    1.1 The Quadratic Wall of Full Attention

    In standard attention, every query must compute relevance against all preceding keys. Let the attention matrix be A = softmax(QKᵀ/√d_h)·V:

    • QKᵀ requires about T²·d multiply-adds;
    • Multiplying by V also requires about T²·d multiply-adds.

    So the attention compute for a single-layer prefill is roughly 2T²d. When the context grows from 1 million to 10 million tokens, this term alone increases by about 100x. Worse still is memory access: each query must scan all preceding key-value pairs, and the bytes read per layer grow with T². Under long context, pressure on GPU memory bandwidth usually becomes a hard constraint earlier than the theoretical FLOPs.

    1.2 The Division of Labor in Sparse Attention, and the Loose End It Leaves

    Sparse attention works by dividing the labor:

    1. A lightweight indexer first picks the k most relevant keys for each query;
    2. Then the real attention computes only over those k keys.

    The attention part is thus compressed to about 2Tkd multiply-adds, genuinely linearizing the cost in T. But the first step never disappears: the indexer still must compare each query against every historical token one by one, on the order of T²/2 comparisons. Division of labor merely moves the quadratic cost from “computing attention” to “finding attention.”

    The key intuition is that both decoding and prefill must pay this bill. For every new token:

    • Full attention’s incremental cost is T multiply-adds;
    • Sparse attention must do T comparisons in the indexer, then run attention over the k selected keys.

    The longer the context, the larger the indexer’s share. Imagine a minimal model: let each comparison in the indexer cost 1, and let the attention over each selected key cost α. With m = T−k unselected tokens, the indexer’s share of total time is:

    1. r_index = m / (m + α·k)

    Plugging in two scenarios (with α = 1, k = 2048):

    Context length Unselected tokens m Index time share
    128K (~130k tokens) ~127k ~98.4%
    1M (~1M tokens) ~998k ~99.8%

    In other words, even at only million-level context, the vast majority of a naive sparse attention’s time is already spent in the indexer, and ten-million-level context just pushes this curve to a steeper position. This is consistent in order of magnitude with the paper’s reported “98% of the time spent in the indexer.”

    1.3 Indexing Is Not a “Free Lookup”

    The indexer’s overhead is often underestimated, and it includes at least three parts:

    1. Score computation: for each query and each historical token, a d_l-dimensional dot product with low arithmetic intensity. Latency is mainly bounded by memory bandwidth and by the large number of non-overlapping index accesses.
    2. Top-k selection: choosing k out of T candidates, a memory-intensive operation.
    3. Data movement: gathering the selected key-value pairs from scattered locations. Index accesses naturally lack locality and easily wreck the cache and memory-coalesced access.

    This work is typically implemented as a stitched-together chain of small operators, which also produces intermediate tensors and causes repeated reads and writes to GPU memory.

    1.4 Four Common “Cost-Reduction” Approaches and Their Boundaries

    Against the quadratic problem of long context, the industry mainly has four routes:

    • Full attention: the highest accuracy ceiling, but grows with the square of context, constrained by both compute and memory bandwidth;
    • Sliding-window / local attention: linear complexity, but a limited receptive field, with distant information only relayed indirectly through intermediate layers;
    • Linear attention and gated recurrence: compress history into a state, theoretically linear, but weak on exact-retrieval tasks due to limited state, and often combined with local attention;
    • Block-level sparse plus global tokens: use a small number of block-level representatives and global tokens to carry cross-segment information flow, but the “candidate screening” itself can still be quadratic.

    Moving the perspective down from “block” to “token” gives another sparse route: let each query dynamically select a few of the most relevant keys. The evidence presented earlier in the appendix is this: at 128K context, keeping only the 512 keys most relevant to each query (about 0.8% of all keys) still reaches roughly 98% of full attention’s performance on long-context capability tests.

    This evidence shows that the accuracy bottleneck is basically not about “how many you keep,” but about “whether you selected the right ones.” So the optimization direction is clear: there’s no need to compress k further, you only need to make the “finding” step itself cheaper.

    2. The Solution: Move the “Finding” into Latent Space

    Since “who to select” cannot be skipped and “comparing one by one” is too expensive, the natural idea is to change the way we compare: use a low-cost, low-resolution representation to complete the screening first, and only restore high precision on a small number of candidates.

    The latent sparse attention proposed in related research can be understood as fitting attention with a CPU-like multi-level retrieval structure. Here we uniformly call it “latent sparse attention,” to distinguish it from naive sparse attention that scores every key one by one.

    2.1 Core Mechanism: Three-Level Retrieval

    Latent sparse attention splits “finding relevant tokens” into three levels:

    1. Latent-space index. A lightweight linear mapping compresses each key into a d_l-dimensional vector (d_l much smaller than d, e.g., 32–64). The mapping can be shared across all tokens, or one per attention head. Its meaning is “use a lower-resolution, shorter-vector copy to do the retrieval.”
    2. Block-level coarse screening. Group the latent indices into blocks of r tokens each (r is often 64–128), reducing the index cost to the order of T²/r.
    3. Intra-block fine ranking. Take candidate tokens from the top-scoring blocks, re-score them in the high-precision space, then run top-k. The final attention computes over only k positions.

    The first level decides “where to look,” the second decides “how to rank,” and the third ensures “computing accurately.”

    The pseudocode below (showing only the algorithm skeleton, not any specific implementation):

    1. def latent_sparse_attention(q, k, v, r=128, d_l=64,
    2. top_blocks=8, budget=2048,
    3. window=512, sinks=4):
    4. """
    5. q: [T, d] query sequence for the current layer (prefill)
    6. k, v: [T, d] key / value sequence
    7. r: block compression ratio (latent index block length)
    8. d_l: latent-space dimension
    9. top_blocks: number of blocks kept per query after coarse screening
    10. budget: final sparse budget per query (including the local window)
    11. """
    12. T = q.shape[0]
    13. n_blocks = (T + r - 1) // r
    14. # 1. Latent projection: a lightweight linear layer decoupled from main attention
    15. W_q, W_k = get_latent_proj() # [d, d_l]
    16. q_l = q @ W_q # [T, d_l]
    17. k_l = k @ W_k # [T, d_l]
    18. # 2. Block compression: compress each block into one representative vector
    19. k_blk = block_compress(k_l, r) # [n_blocks, d_l], e.g. mean within a block
    20. q_blk = repeat_interleave(q_l, r)[:T] # [T, d_l]
    21. # 3. Block-level scores: an T×n_blocks matrix, naturally chunked and easy to parallelize
    22. s_blk = (q_blk * scale_l) @ k_blk.T # [T, n_blk]
    23. # 4. Causal handling: only allow seeing the current and earlier blocks; mask future tokens inside boundary blocks
    24. s_blk = causal_mask(s_blk, r) # mature techniques like block-level prefix reduction (prescan) still apply
    25. # 5. Coarse screening: each query selects the top_blocks blocks
    26. sel_blocks = topk(s_blk, top_blocks) # [T, top_blocks]
    27. # 6. Assemble the mandatory set:
    28. # - the first `sinks` tokens; many models have a stable attention preference for the sequence start
    29. # - the most recent `window` tokens, responsible for local modeling
    30. base_idx = concat([range(0, sinks), range(max(0, i - window), i + 1)])
    31. # 7. Candidate expansion + deduplication
    32. cand_idx = flatten_blocks(sel_blocks, r)
    33. cand_idx = union_unique(base_idx, cand_idx)
    34. # 8. High-precision fine ranking: re-score only with the original keys of the candidate tokens
    35. s_fine = einsum(q, k[cand_idx]) * scale
    36. s_fine = apply_causal_mask(s_fine, base_idx) # keep the local window and anchors preferentially
    37. # 9. Final budget: allocate the remaining slots to the highest-scoring tokens among the candidates
    38. idx = budget_fill(s_fine, cand_idx, budget)
    39. # 10. Attention is computed only over the finally selected key-value pairs
    40. # A real implementation needs to fuse gather with the attention computation
    41. # to avoid repeatedly reading/writing intermediate tensors to memory
    42. return sparse_attention(q, k[idx], v[idx])

    2.2 Complexity Analysis

    The latent index’s dot products need only d_l multiply-adds, not d. Counting by prefill:

    • Block-level scoring is on the order of T²·d_l/r;
    • Intra-block fine ranking is on the order of T·top_blocks·r·d;
    • The final attention is on the order of T·k·d.

    Compared with full attention’s 2T²d, the block-level share is:

    1. block-level cost / full-attention cost ≈ d_l / (2r)

    If d_l = 64 and r = 128, the coarse-screening cost is less than 0.25% of full attention. But d_l and r are both fixed constants, and T²/r relative to T²d is only a constant-factor reduction, so the asymptotic order doesn’t really change. The “quadratic” is merely moved into a lower-dimensional subspace.

    2.3 Why It’s “Sub-Quadratic” Rather Than “Linear”

    A more thorough compression is to let the granularity vary with the context, for example by setting the block length to r ≈ √T, then pairing it with a linear- or log-level attention backbone (such as linear attention or sliding-window attention), so the overall cost becomes sub-quadratic. This is precisely why related research titled its work “toward sub-quadratic.”

    Conversely, a block-level latent index implemented with a constant r is essentially a “constant-factor optimization,” that is, moving the most expensive comparisons into a lower-dimensional space. A large reduction in the cost of each single comparison, combined with high-precision local attention, can still bring order-of-magnitude gains on real workloads. Understanding this distinction matters, because it determines how you should pick a configuration for different scenarios:

    Configuration Index asymptotic complexity (coarse screening) Main source of gain Suitable scenarios
    Full per-token index T²·d_l None (dimension compression only) Control baseline for shorter contexts
    Block-level latent index (constant r) T²·d_l/r Fewer comparisons, cheaper per comparison Million-level context prefill and decoding
    Latent index with block length growing with T Asymptotically sub-quadratic The index term is genuinely reduced Ten-million-level and above context
    Compressed to a fixed-size state (e.g., recurrent-style compression) O(1)/step (bounded memory) Trades lossy information for linear/constant Ultra-long streaming dialogues, online serving

    2.4 Why Lossy Indexing Still Works

    Some will ask: if we rank using a low-dimensional compressed representation, won’t we miss the truly important tokens? Several points support this approach:

    1. The low-dimensional projection is a similarity approximation. Similar to how random projections preserve vector inner products, when the dimension is high enough, a high-dimensional dot product can be approximated by a low-dimensional one, and the ranking largely holds. The high-dimensional dot product’s dependence on a low-dimensional projection is itself limited: perturbations across most dimensions have little effect on the dot product, the approximation error grows with √d_l, while the signal term grows with d.
    2. The block-level representative is a coarse-grained estimate. The within-block mean represents the block’s overall topic, suitable for judging “which passage is relevant” but not “which single token is most critical.”
    3. The two-level cascade limits the error to the candidate set. The cost of coarse screening missing an entire block is covered by fine ranking at original precision; only the cost of fine ranking picking the wrong individual token truly enters the attention computation.

    So in engineering terms, “ensuring the right selection” should be placed at the coarse-screening layer:

    • Appropriately increase the number of candidate blocks; the goal of coarse screening is high recall, not high precision;
    • Handle boundary blocks and attention blocks separately (as discussed later, often only a few positions in the sequence carry a large amount of attention);
    • Set causal boundaries precisely, masking future tokens at block-level boundaries;
    • Make the local window and the sequence-start tokens a mandatory set, bypassing retrieval directly.

    3. Precision Guarantees: Making “Sparse” Not Hurt Capability

    Related papers report up to roughly 72x speedup on single-layer attention in a prefill of about 10 million tokens: about 72x on one mainstream open-source model, and about 22x on another. At the same time, across multiple long-context and general tasks, accuracy stays close to the original full-attention model.

    This result is unsurprising, because precision guarantees are not an afterthought, but part of the method design. The following six points can serve as a self-check list.

    1. Mandatory anchors: a small number of sequence-start tokens and the most recent local window always participate in attention, preventing the model from completely losing global information when relevance ranking fails.
    2. Layered, budgeted sparsity: deeper layers often need a larger global receptive field, and different layers and heads can be configured with different k, block lengths, and candidate block counts, rather than a one-size-fits-all setting across the network.
    3. Learn from full attention: during pretraining or continued training, distill the sparse model with full attention as the teacher, or use the same indexing logic during training, to avoid a “retrieval distribution mismatch” between inference and training.
    4. The non-differentiable problem during training: top-k is a discrete operation, so training often uses a “straight-through estimator” to backpropagate gradients along the selected path, or uses bucketing, temperature annealing, and other methods to smooth the selection boundary.
    5. Choose the right metrics: long-context capability tests (such as multi-hop retrieval, variable tracking, aggregation statistics, and other synthetic tasks) sensitively expose the “wrong selection” problem and are the most important validation method for this class of techniques. When necessary, downstream evaluations based on real long documents should also be added.
    6. Errors must be attributable: count “retrieval recall” and “attention accuracy loss” separately. If the selected set is already close to the ideal selection, the remaining loss comes from the low-dimensional representation itself, and d_l or the candidate block count should be increased first; otherwise, the coarse-screening recall surface should be widened.

    4. Engineering: Actually Turning “Savings” into Throughput

    No matter how good the complexity math looks, a poor implementation can eat up the gains through memory access and small-operator overhead. Here are a few practical measures.

    1. Operator fusion: fuse “projection, block-level scoring, causal reduction, top-k, gather, attention” as much as possible, avoiding repeatedly writing T×n_blk-scale intermediate tensors back to memory at each layer. Take T = 10 million and n_blk ≈ 78k (r = 128) as an example: if a single score matrix is stored in 4 bytes, its size is about 3.1TB, which simply doesn’t fit, so chunked, pipelined processing is mandatory.
    2. Memory localization: keep block-level representatives resident in cache in order, and scan query chunks block by block; for candidate keys, use a contiguous layout (re-arranged after deduplication) before gathering.
    3. Decode reuse of the index: since the prefill phase already computed the compressed keys, decoding only needs to score blocks for the new query, with no need to recompute all compressed representations.
    4. Quantized index: latent vectors are usually stored and computed at low precision of 8 or 16 bits, with little accuracy loss and a significant bandwidth reduction.
    5. Long-sequence parallelism: partition the prefill across multiple GPUs along the sequence dimension, aggregate block-level representatives via collective communication, so that only a small number of low-dimensional vectors need to be exchanged across GPUs, with far less communication than exchanging full key-value pairs.
    6. Operator implementation and data layout: watch for the “non-power-of-two sequence length” boundary issues common in block-attention operators; padding and tail-block handling must be explicitly covered.
    7. Parameter overhead control: at d_l = 64, the latent projection parameters per head are d·d_l, about 0.25–0.5x the head’s main attention parameters (2d·d_h); if the mapping is shared per layer, the overhead can be amortized further.
    8. Verify end to end: single-layer speedup is not equal to end-to-end speedup; also consider the index layer’s share of the total layer count, the cost of the non-attention parts (such as the feed-forward network), and actual operator efficiency on real hardware.

    5. Putting It in the Full Long-Context Landscape

    Latent sparse attention is not an isolated scheme; it sits at the intersection of three technology tracks:

    • Position and training side: methods like YaRN let RoPE extrapolate smoothly over long sequences; Ring Attention partitions the sequence across GPUs and stitches attention together with ring communication; PagedAttention manages the KV cache in a paged manner to reduce fragmentation; Linear Attention compresses history into a state. These solve “whether it can be computed at all,” while latent sparse attention solves “whether it can be computed fast.”
    • Retrieval side: sparse attention is the model’s internal “dynamic retrieval,” where the candidate set varies per token with the query. It doesn’t conflict with external retrieval augmentation, but it can eliminate the need to stuff an entire ultra-long document into the context.
    • Application side: repository-level code QA, ultra-long contract comparison, long-conversation memory, these scenarios share the common trait that “input far exceeds output.” Prefill cost dominates the total, so the gains from index optimization are the most direct.

    Quick Configuration Guide

    If your scenario is… Prioritize…
    Single long input, short output (document/repo QA, contract review) Block-level latent index + local window + anchors, with a focus on optimizing prefill
    Ultra-long multi-turn sessions, streaming input Linear/gated schemes compressed to a fixed-size state, or a block-level latent index with cache reuse
    Extremely sensitive to retrieval precision (exact numeric lookup, strong multi-hop reasoning) Measure index recall first, and if needed raise the candidate block count or d_l, keeping a larger sparse budget k
    Already using external retrieval augmentation First evaluate whether full context is still needed after compression; latent sparse can serve as a second layer of assurance

    6. Self-Check List and Conclusion

    Looking back over the whole picture, as context scales from millions to tens of millions of tokens, attention’s main conflict has shifted from “computing too much” to “finding too expensively.” Latent sparse attention offers a clear idea: use a low-dimensional, low-resolution index to handle “where to look,” use original precision to handle “compute accurately,” and connect the two with a lightweight coarse-screening pass.

    For implementation, start your self-check with these five questions:

    1. Bottleneck measurement: at your target context length, does index time truly dominate? If the attention computation itself is the bottleneck (for example, nearly every layer is full attention), the gains from optimizing the index are limited, and you should prioritize adjusting the sparsity or the layer configuration.
    2. Causal correctness: do block-level boundaries strictly mask future tokens? During decoding, can you reuse the compressed keys already computed in prefill?
    3. Recall verification: randomly sample several queries, compare the selected set against the results of high-precision full ranking, and quantify top-k recall.
    4. Mandatory set: do the local window and sequence-start tokens always participate in attention? Is the width sufficient to cover the local dependencies the task needs?
    5. Resources and gains: is the index’s extra memory and compute overhead smaller than the attention overhead saved? Are end-to-end throughput and time-to-first-token genuinely improved?

    Once these questions are answered clearly, latent sparse attention transforms from an acceleration number in a paper into an engineering capability that can be quantified, validated, and tuned on demand. The context window will keep growing, and making the “finding” cheap enough is the real prerequisite for long context to scale.