Scaling Sparse Attention to 10M Tokens: The Indexing Bottleneck
As context windows scale to tens of millions of tokens, sparse attention shifts the bottleneck from attention computation to candidate selection. This article explains why finding the right tokens—not attending to them—becomes the dominant cost, and how latent-space sparse attention (compressing history into low-dimensional block descriptors, retrieving block-level candidates, then attending only within those blocks) keeps indexing costs linear and cacheable. It covers the sources of quadratic growth, why precision often holds, system-level optimizations, and how to combine this approach with linear attention and global layers.
The shift from 100K to 10M tokens changes which part of the attention pipeline actually hurts. When every query must retrieve a small subset of relevant history, the indexing process—deciding which positions to look at—re-emerges as the dominant cost.
Attention is saved, selection is not
Standard self-attention on a sequence of length n requires computing query-key similarity over n×n pairs. Sparse attention narrows each query’s effective field to k positions, where k is much smaller than n, bringing value aggregation down to roughly O(nk) or even lower with block-based access. However, if finding which k positions matter still requires scoring, sorting, or gating over all history, the selection phase grows with n—often with quadratic or near-quadratic memory bandwidth.
Think of one prefill layer as three stages:
- Build a retrievable representation of history (keys, block summaries, routing vectors)
- Select candidates for each query or query block
- Compute attention over candidates only, then write back residuals
At 1M tokens, matrix multiplication in stage 3 typically outweighs stages 1 and 2. At 10M tokens, the history representation no longer fits in high-speed cache, and stage 2 repeatedly scans massive numbers of keys or block descriptors. Even with a highly optimized sparse kernel compressing stage 3, the indexing step dominates end-to-end time. In practice, during 10M-token prefill, the majority of time in global sparse layers goes to finding positions, not computing attention. This is not an implementation issue—it is inherent to scaling. Sparsity has proven that “reading less” is sufficient; the blocker is that “finding the small subset” is still too expensive.
Where quadratic growth comes from
Let the block size be b and the number of blocks be m = n/b. If every query block must take inner products with all block summaries, you still get O(m²) comparisons—just with a smaller constant. An exact top-k selection adds another logarithmic or linear factor for comparisons and temporary buffers. Additional overhead:
- Key caches are spread across heads and layers, addresses are non-contiguous, and bandwidth utilization is poor
- Selection results are irregular, so subsequent sparse reads cannot be coalesced into large memory accesses
- Prefill must produce selections for the entire query sequence at once, unlike decoding which can reuse step by step
- Independent retrieval per head or per query group multiplies the indexing work
This is why “keeping only 1%–5% of connections” does not automatically translate into the same speedup. Connection sparsity and selection sparsity are different. The former determines attention FLOPs; the latter determines whether you can afford to discover those connections in the first place.
Latent-space sparsity: coarse filtering in a low-dimensional space
The core idea of latent-space sparse attention is to move candidate discovery from the original high-dimensional key space to a cheaper latent representation—without doing exact full-connection scoring over all tokens.
The approach can be abstracted into three general steps, none tied to a specific implementation:
- Compress history. For each block, learn or pool a low-dimensional descriptor with dimension d’ much smaller than the head dimension d. The descriptor needs to capture “what this history is roughly about” without preserving per-token phase information.
- Retrieve in latent space. Project the query into d’ and compare only against m block descriptors to get a small set of block-level candidates. The number of comparisons drops from “queries × tokens” to “query blocks × blocks,” multiplied by a small d’.
- Refine locally. Apply standard or lightly sparse attention only within the selected blocks, using high-dimensional keys and values to restore precision. Blocks that were not selected do not participate in value aggregation.
Latent space handles recall; the original space handles ranking. Recall can be approximate: missing a slightly relevant block costs less than the latency of exact indexing over all history. The refinement scope is fixed to k blocks, making attention computation predictable again.
The schematic flow (illustrating data flow, not runnable code):
blocks = pool(hidden_states, block_size) # [m, d']scores = query_latent @ blocks.T # [q_blocks, m]idx = topk(scores, k) # block-level candidatesout = attend(query, key_value_gather(idx)) # attention within candidates only
Compared with “scan all keys per token, then top-k,” the primary dimension of inner products drops from n to m, computed in d’. With block lengths in the hundreds and latent dimensions in the tens, arithmetic intensity and intermediate result size both drop by more than an order of magnitude. The exact speedup depends on sequence length, block size, head count, memory hierarchy, and kernel fusion—this is not a model-agnostic constant. Engineering teams should measure the indexing time share at the target length rather than extrapolating from short-context profiling.
Why precision often holds
Sparse attention works because relevant evidence in natural language and code is highly concentrated over long ranges. What determines the current prediction is usually a few entities, definitions, constraints, or earlier conclusions—not tokens spread uniformly across the entire history. A block-level latent vector only needs to distinguish “whether the topic is relevant” to recall the blocks that hold the evidence. Fine-grained attention within a block then recovers word order and coreference information that the latent space discards.
Cases where it fails need separate treatment:
- Fine-grained alignment. The answer depends on a rare symbol, line number, or exact citation. The block summary gets diluted by majority tokens, and recall ranking suffers.
- Uniform dependence. Tasks require counting over a sequence, computing global statistics, or checking consistency—reading less inevitably misses information. Keep a few global markers, summary tokens, or periodic full-attention layers instead of imposing sparsity everywhere.
- Train-inference mismatch. If the model was trained on dense or a different sparse mask, suddenly changing the candidate distribution at inference causes logits to drift. Better to use the same selector during continued training or distillation, or calibrate selection temperature and k on short contexts.
“Keeping comparable precision” therefore means: on reading comprehension, long-document QA, and multi-hop retrieval, block recall covers the key evidence. It does not guarantee zero loss on synthetic “needle-in-haystack” probes. Evaluation should report both task scores and recall rates—whether key blocks enter the top-k, and whether increasing k shows diminishing returns.
System side: treat the indexer as a first-class citizen
At 10M-token prefill, the bottleneck is bandwidth and temporary memory, not peak compute. When deploying, budget for the selector explicitly:
- Block descriptor cache. Latent vectors for history blocks can be persisted with the key-value cache. When appending context, update only new blocks instead of rescanning all history per request.
- Query grouping. Adjacent queries often attend to the same evidence. Cluster queries or share candidates per query block to reduce duplicate top-k operations.
- Two-stage pipelining. Overlap indexing and refinement: while the current block computes attention, the next block is already scoring in latent space. Ensure candidate index writes do not block a global sync point.
- Regular sparse access. Gather by block, not scattered token indices. Irregular reads make “computing less” still “waiting long.”
- Adaptive k. Increase k for high-uncertainty queries; decrease it for repeated templates and punctuation-dense regions. Fixed k wastes cycles on simple passages and falls short on hard ones.
- Numerical paths. Latent-space scoring can use lower precision; refinement attention should follow the original model’s numerical strategy to avoid overflow or underflow when aggregation is correct but unstable.
Memory-wise, block descriptors are O(m·d’), much smaller than the complete key cache of O(n·d). But stacked across 10M tokens, multiple layers, and multiple heads, they are still substantial. Define before deployment: which storage tier holds descriptor vectors, the eviction policy, and whether request cancellation can abort unfinished indexing.
Combining with linear attention and global layers
In practice, very few networks use a single attention type. Common architectures use a few global or sliding-window layers for local coherence and fallback, with most layers using sparse or linear recurrent approaches to extend context length. Linear attention compresses state for O(n) updates—good at smoothly remembering topics, bad at retrieving an exact fragment from long ago. Latent-space sparsity fills this gap: details that cannot stay in state are read back on demand via block recall.
The combination principle is simple. Layers that require exact position lookup use block recall plus local refinement. Layers that need overall style or topic continuity use linear or sliding-window attention. Do not apply heavy indexing on every layer, or the indexer multiplies by layer count and re-dominates prefill.
Pre-deployment checklist
- Profile at the target length (not 4K or 32K): split time into indexing, gather, attention, and communication.
- Plot k, block size, and latent dimension against task score and latency. Find the recall saturation point instead of blindly increasing k.
- Prepare a probe set of “must-hit” items: key sentences, constraint clauses, cross-section coreference. Measure block recall.
- Check multi-turn conversation behavior: when new tokens arrive, are old block descriptors updated incrementally? Is selection consistent with full recomputation within acceptable error?
- Watch long-tail requests. Extremely long, scattered inputs destabilize top-k. Need global fallback layers or context-budget limits—do not silently drop evidence.
- Do capacity planning on index bandwidth plus key-value cache. Sizing by sparse attention FLOPs alone will severely underestimate prefill time at 10M scale.
Summary
Sparse attention answers the question “do we need to read everything?” At 10M tokens, the real problem is “we cannot scan everything just to decide what to read less.” By moving selection to low-dimensional block descriptors and letting the original space handle only the recalled subset, indexing becomes linear in the number of blocks, cacheable, and pipelineable. The speedup depends on length and implementation—there is no universal multiplier. What engineering teams should track are three numbers: whether indexing time share grows out of control with length, whether recall of key evidence blocks saturates, and whether global fallback layers cover the tasks that should not be sparse to begin with. Quantify those three, and ultra-long context becomes an operable capability—not just a structure that looks good on short-sequence benchmarks.
