Indexing Bottlenecks in Sparse Attention at 10M Tokens, and How to Optimize Them
Sparse attention can keep long-context quality with a small key set, but the indexer that finds those keys can still scale quadratically. This article explains why “finding k” becomes the bottleneck from 1M to 10M tokens, how latent-space coarse routing plus fine selection reduces indexer cost, and how to evaluate recall, latency, and scaling in production.
From 1M to 10M: Why Sparse Attention Still Stalls on Finding Keys
Once million-token context became a common spec, engineering teams found that the expensive part is not “letting the model see a long sequence,” but letting each query efficiently decide which history tokens to attend to. Full attention has a clear cost structure. With context length T, prefill requires every query to score against all previous keys, so compute grows as T². In decoding, each new token attends over the KV cache, so cost grows linearly with T. Scaling from 1M to 10M tokens multiplies pairwise attention comparisons in prefill by about 100×, which is not sustainable.
Sparse attention splits the work: a lightweight indexer first selects k relevant keys per query, then true attention runs only on those k keys. Main attention then costs O(Tk). When k ≪ T, the gain is large. Public research also supports a premise: long-context tasks do not need every query to scan the full history. At 128k context, keeping well under 1% of keys per query can still retain most of full-attention accuracy. “Looking at a small subset” is usually valid for quality.
The indexer itself is not automatically cheap. To know which k keys are most relevant, it must score many keys. If every query still compares against all keys, indexing remains T×T pairwise scoring. Sparse attention can drop main attention from O(T²) to O(Tk) while quietly moving quadratic cost into the indexer. When T grows from 1M to 10M and k is fixed, main attention grows about 10×, but indexer pairwise comparisons grow about 100×. Indexing, once minor, can dominate. Public experiments on 10M-token single-layer prefill have seen indexing take most of the time, in extreme cases near 98%. The next step is not only shrinking k, but making “find k” sub-quadratic.
The Indexer’s Hidden Bill: Where Quadratic Cost Hides
A typical sparse attention layer has four steps: query projection, index scoring, top-k selection, and attention on candidate keys. Steps two and three are easy to underestimate.
First, index scoring is still pairwise query–key comparison. Even with a small indexer hidden size d_i, each query produces T scores; T queries yield T² scores. A smaller dimension only reduces constants, not the growth order. Second, top-k must scan or sort many scores, adding compute and memory-bandwidth pressure. At extreme lengths the score matrix is often not fully materialized, but blocked scans, candidate merges, and approximate selection still cost. Third, the indexer must read key representations or block summaries; KV scans at long context amplify bandwidth limits. Prefill is often stalled by data movement and candidate management, not FLOPs. Fourth, indexer and main attention add sync and scheduling overhead. In batched, variable-length, multi-tenant inference, uneven candidate budgets can hurt kernel utilization.
Evaluating sparse attention therefore requires latency breakdown, not only “how much faster attention is”: summary/projection time, block-level scoring, in-block fine scoring, top-k, main attention, and bandwidth. For 10M-token settings, a practical rule is: if the indexer still scores all keys pairwise, it will become the new quadratic bottleneck.
Latent-Space Sparse Attention: Coarse Route, Then Fine Select
The idea is not merely “look at less,” but “search candidates in a cheaper space.” One workable design has three layers:
Low-dimensional latent projection. Project queries and keys into a lower-dimensional space and score there. Each comparison uses fewer MACs and less cache, which helps large batches. Dimension must be tuned with recall: too low loses discrimination; too high brings indexer cost back.
Block-level coarse routing. Partition history into fixed-size blocks and keep an incrementally updatable summary per block (mean of keys, low-rank compression, or cluster center). Each query scores only against block summaries and keeps a few candidate blocks. With block size B, block scoring is about T²/B. Large B turns “all-token comparison” into “coarse block screening.”
Fine scoring inside candidate blocks. Inside those blocks, score token-level keys and keep the final k. Fine scoring happens only in a few blocks, about O(T·k·d), aligned with the sparse attention budget. The target is “block-level O(T²/B) + in-candidate O(Tk),” then ANN, clustering, low-rank approximation, or hierarchical routing can push block comparison toward sub-quadratic.
Illustrative pseudocode:
function select_keys(query, block_summaries, block_tokens, k_block, k_token):# query is already projected to latent spaceblock_scores = []for block_id, summary in enumerate(block_summaries):block_scores.append(dot(query, summary))candidate_blocks = topk(block_scores, k_block)candidates = []for block_id in candidate_blocks:for key in block_tokens[block_id]:# in-block fine scoring; latent projections can be reusedcandidates.append((dot(query, project_key(key)), key))return topk(candidates, k_token)
This omits fused batching, numerical stability, incremental summaries, and approximate top-k, but shows the path: coarse block filter, then token-level select. Production kernels should fuse summary computation, block scoring, and in-block scoring to avoid materializing intermediates.
Engineering and Evaluation
A usable latent-space sparse attention design must jointly manage quality, latency, and system complexity.
Incremental block summaries. Decoding must not recompute all summaries when a token is appended. Maintain a running vector and count per block; for low-rank compression, mix periodic recompute with incremental updates. Count summary-update cost in the latency breakdown, or “faster scoring” can hide slower maintenance.
Dynamic candidate budgets. Fixed k_block and k_token vary a lot across layers, heads, and tasks. Adjust using score gaps vs. summaries, in-block variance, or historical recall: simple queries keep fewer candidates, hard queries keep more. Dynamic budgets unbalance batches and need scheduling.
Measure recall, not only end-to-end accuracy. The indexer’s direct metric is recall@k: how often the selected k keys cover the true top-k. Calibrate stratified recall on a small set, then check long-context accuracy retention. High recall but lower accuracy may point to fusion or positional encoding; low recall should drive latent dim, block size, and budget.
Scaling curves, not single points. Measure prefill latency, time-to-first-token, throughput, and memory at least at 128k, 1M, and 10M, and split indexer share. Indexer share must fall as T grows if the design is truly sub-quadratic; otherwise cost only moved.
Keep a fallback. For short context or high-precision tasks, fall back to full attention or larger budgets; for ultra-long context, use block routing plus in-candidate selection. Choose by length, batch size, and SLA.
Conclusion
Sparse attention has shown that attending to a small subset can preserve long-context quality, but 10M tokens surfaces another issue: the indexer that finds that subset can still grow quadratically. Latent-space sparse attention moves indexing from high-dimensional all-pairs scoring to coarse routing in a cheap representation plus fine selection in candidates, with incremental summaries, dynamic budgets, and latency breakdowns to control engineering cost. Public experiments report order-of-magnitude speedups on 10M-token single-layer prefill, but gains depend on model structure, block size, candidate budget, and hardware. The reliable path is to profile indexer latency first, then iterate on recall and scaling curves so sparse attention goes from “look at less” to “find what to look at cheaply.”
