Sparse Attention at 10M-Token Contexts: The Rising Cost of Indexing

    As context windows scale from 1M to 10M tokens, sparse attention does not eliminate quadratic pressure; it shifts much of it to the indexer. This article breaks down prefill cost into representation preparation, candidate scoring, and sparse attention, then explains how latent-space filtering can make candidate scoring subquadratic while preserving recall. It also covers recall and task-accuracy validation, latency and memory profiling, layer-specific sparsity, training-inference consistency, decoding behavior, numerical precision, and when this approach is worth adopting.

    Why the Problem Changes Shape

    Standard self-attention lets every query compute relevance against all previous keys. When the sequence length is T, attention compute in the prefill stage grows as O(T²), and every generated token must also scan a history of length T. Moving context from one million to ten million tokens magnifies this term by roughly two orders of magnitude. For online inference, this means memory bandwidth, compute quota, and time to first token all degrade at the same time.

    Sparse attention splits the work into two steps: first, a lighter indexer selects a small number of relevant keys for each query; then true attention runs only on those k positions. Attention itself therefore approaches O(Tk). This approach depends on an empirical fact: in many tasks, only a small fraction of the history is strongly relevant to a single query. If those k positions are selected accurately, accuracy on long-context benchmarks can approach that of full attention.

    The tension appears here as well. For the indexer to know which k keys are most relevant, it usually still has to score every key. Lower precision, lower dimensionality, and compressing adjacent keys into blocks only shrink the constant; they do not change the asymptotic shape of “every query scans the entire history.” As T continues to grow, the indexing stage moves from a supporting role to the main role: most prefill time is spent deciding what to look at, not on the short attention segment that follows.

    How to Break Down the Cost

    A single prefill layer can be viewed in three parts.

    The first part is representation preparation: query, key, and value projections, plus optional positional encoding. It grows roughly linearly with T and is relatively easy to amortize with fused operators and batching.

    The second part is candidate scoring. If the indexer computes a score for every query and every key (or every block), the compute is still Θ(T²/B), where B is the block size. Larger blocks mean fewer scoring operations, but irrelevant words inside a block are tied together, so recall and accuracy constrain each other.

    The third part is sparse attention itself: scaled dot product, normalization, and weighted summation over the selected k keys, on the order of O(Tk·d), where d is the head dimension. When k is fixed or grows slowly with T, this part can remain modest.

    The optimization target should therefore no longer be “make the attention matrix multiply faster,” but rather make candidate scoring itself grow subquadratically with length while the recalled set still covers the positions the model actually depends on. If a key evidence sentence is missed, faster matrix multiplication only performs precise computation on the wrong subset.

    What Latent-Space Filtering Solves

    A more sensible boundary is to place “finding locations” and “reading content” at different resolutions.

    Keys can first be compressed into low-dimensional latent representations, or summarized per block into a small number of summary vectors. Queries are projected into the same space and compared only with summaries or hierarchical nodes that are far fewer than T, producing coarse candidates. If necessary, a finer scoring pass can run inside candidate blocks, and finally only the top k original keys are sent into attention. The number of coarse comparisons depends on the number of summaries M, not the number of original tokens. If M grows sublinearly with T—for example, by summarizing at a fixed block length and then merging hierarchically—scoring has a chance to move from quadratic to roughly T·log T or T·M, with M ≪ T.

    The accuracy precondition is specific: the latent representation must preserve the ranking of “whether something is relevant,” but it does not need to preserve all semantics required for generation. If the ranking is wrong, sparse computation cannot rescue it; if the ranking is right, value vectors still participate in weighting at the original high precision, giving generation quality a chance to approach dense attention.

    In engineering practice, three types of positions are usually retained so that pure retrieval does not miss structural dependencies:

    • Local window: neighboring tokens carry syntax and coreference; cost is low and recall is stable.
    • A small number of global or summary slots: information that is repeatedly referenced, such as titles, system constraints, and section beginnings or endings.
    • Content retrieval slots: distant evidence dynamically added by latent-space scoring.

    The budget for k should be allocated across these three categories rather than giving all slots to the blocks with the highest similarity.

    Validating Accuracy and Speed Together

    Do not look only at operator latency. At minimum, track four things at the same time.

    Recall: on a small calibration set, use the true top-k from full scoring as a reference and measure how much of that set is covered by latent-space filtering. If coverage collapses, downstream scores have no explanatory value.

    Task accuracy: compare against dense attention or the original sparse method on sets that require cross-segment retrieval, multi-hop alignment, and long-document question answering. Small fluctuations on individual tasks are acceptable, but the method cannot only “look fine” on short contexts.

    Latency structure: measure projection, indexing, sparse attention, and memory stalls separately. If the indexing share still rises steeply with length, the block length or number of layers is wrong; it does not mean the method is already subquadratic.

    Memory: score matrices, block tables, and top-level indexes all consume space. At tens-of-millions-token sequence lengths, avoid materializing full T×T scores. Instead, use block-streaming scoring and retain only a top-k heap per row.

    An illustrative prefill budget can be written as the following pseudocode. It is not an interface for any framework; it is only meant to make the complexity clear:

    1. for each query block Q:
    2. scores = match(project(Q), latent_keys) # compare with M summaries
    3. blocks = top_blocks(scores, local_window)
    4. K, V = gather(blocks) # take only k original keys and values
    5. out = attention(Q, K, V)

    Common Pitfalls in Deployment

    Block boundaries can split an evidence sentence in half. Overlapping blocks or boundary rescoring can mitigate this, but too much overlap multiplies M back. In practice, use a small overlap and allow adjacent blocks to share one summary update.

    Sparsity patterns differ across layers. Shallow layers are more local, while deep layers rely more on distant facts. Sharing the same k and the same summary across all layers often wastes budget in one layer and under-recalls in another. Analyze the distance distribution of selected positions by layer, then tune the window and retrieval slots.

    Training and inference must be consistent. If training uses differentiable soft selection for the index but inference switches to hard top-k, ranking bias is amplified. A safer approach is to use the same hard filtering as production late in training and let the selector learn ranking through a straight-through estimator or a separate index loss.

    Decoding and prefill do not follow the same curve. Prefill faces the entire history, and indexing is heaviest there; token-by-token decoding has only one query and can reuse an already built summary tree while incrementally inserting new keys. Optimizing prefill without updating the index structure means subsequent latency in long conversations will still climb linearly or worse.

    Numerically, low precision is sufficient for ranking but not suitable for final weighting. A common approach is to use lower precision and lower dimensionality for the index while keeping attention at the original head dimension. Pass only integer indices between them, and avoid reading coarse vectors as values.

    When to Adopt This Step

    If the workload’s context stays stably within the model’s training length, dense attention or a fixed local window is often simpler and has lower maintenance cost. The signals for introducing latent-space filtering are clear: profiling shows that indexing or full scoring accounts for the vast majority of prefill time, and the task truly depends on sparse distant facts rather than only on the most recent span.

    The rollout order should also be restrained. First use offline profiling to confirm whether top-k recall is sufficient to preserve metrics, then replace the scoring path, and only after that work on kernel fusion and cache layout. Re-test every step with the same length ladder—from 100K to 1M to 10M—and observe whether latency flattens as expected, rather than reporting a speedup only at the shortest sequence.

    The competitiveness of ultra-long context ultimately lies not in “looking at every token,” but in “finding the small subset of tokens that must be read in a scalable way.” After moving the bill from attention multiply-adds to indexing, the next step should be to move indexing itself off the quadratic curve.