Latent Sparse Attention for 10M-Token Contexts: Moving the Indexer Off the Quadratic Path
As context windows have grown from 1M to 10M tokens, the bottleneck in sparse attention has shifted: reported profiles show that in a 10M-token prefill, roughly 98% of a single global attention layer's time goes to the indexer that decides which tokens to attend to, not to the attention math itself. This article re-derives the cost structure of full and sparse attention, explains why cheaper FLOPs do not translate into speed once the workload is bandwidth-bound, reviews the three common indexer-compression paths and their shared recall penalty, and describes Latent Sparse Attention (LSA) — a two-level retrieval scheme that performs coarse selection over a fixed-length latent representation of the context and fine selection over original keys. Readers will learn how to interpret published speedup figures and their caveats, the engineering knobs and constraints for production deployment, and an evaluation checklist that keeps retrieval quality from regressing while latency drops.
1. The Shifting Bottleneck: From “Computing Less” to “Finding the Right Tokens”
Over the past two years, the default context length for mainstream LLM serving has climbed steadily: a million tokens first became standard in hosted APIs, and open-weight releases followed with models that support million-token contexts and, for the first time, mix sparse attention with linear attention inside a single model. These designs share the same engineering judgment: instead of letting every query scan the entire history, select a small number of the most relevant keys to attend to.
That judgment has been validated repeatedly at the million-token scale. But as the context is pushed toward tens of millions of tokens, a cost that used to be inconspicuous starts to run away. Profiling data from public research shows that on a single global attention layer of a general-purpose large model, during the prefill of a 10M-token sequence, roughly 98% of the time is not spent on attention computation at all — it is spent in the indexer that decides which tokens to look at.
The nature of the bottleneck has changed. Sparse attention has long demonstrated that attending to a small subset is enough to preserve accuracy. What actually blocks very long contexts is the act of finding that subset, which still grows quadratically with context length.
2. Re-deriving the Cost Structure
The full-attention baseline
Let the context length be T and the hidden dimension be d. Under standard full attention, prefill must compute relevance between every query and all historical keys, roughly O(T²·d); decoding each new token costs O(T·d). Going from 1M to 10M tokens multiplies the prefill cost of the attention portion by 100×, while the KV cache grows linearly until it no longer fits in device memory.
The division of labor in sparse attention
Sparse methods are essentially a two-step process:
- Indexing: a lightweight scorer (the indexer) picks k of the most relevant keys for each query.
- Refined computation: the actual attention runs only over those k keys.
This drops the refined portion from O(T²·d) to O(T·k·d). When k is fixed in the low hundreds, this term is negligible relative to full attention.
The step that gets overlooked
The problem is that the indexing stage must still score every key. If the scorer evaluates all T candidates for each query, its cost remains O(T²). It is not much cheaper than full attention; it merely replaces expensive multiply-accumulates with far cheaper dot products — and on bandwidth-constrained hardware, that difference gets largely erased.
3. Why “Cheaper FLOPs” Doesn’t Always Mean Faster
Understanding the 98% figure requires switching from a FLOPs view to a roofline view.
- Low arithmetic intensity: indexer scoring is a dot product over low-dimensional vectors — only d multiply-accumulates per key read. Its compute-to-memory ratio is far below that of the attention matmul, making it a classic memory-bound operator whose measured throughput is set by memory bandwidth rather than compute.
- Selection is inherently expensive: top-k selection (whether exact sorting or approximate selection) involves serial reduction and irregular memory access. It cannot saturate Tensor Cores the way a GEMM can, and it often falls back to inefficient generic kernels.
- Results can’t be reused: the indexer’s output has a different shape and a different lifetime from the attention output, so it is hard to fuse into one efficient kernel. The result is a large volume of intermediate reads and writes plus kernel-launch overhead.
Together, these three factors mean the indexer’s cost is dominated by memory movement and scheduling. They also explain why simply lowering scoring precision to FP8 or INT4 usually delivers a speedup well below the theoretical expectation: the bottleneck has moved from compute to bandwidth, which calls for a structural change rather than a numeric one.
4. Three Existing Compression Paths and Their Limits
Industry efforts to cut indexer cost fall roughly into three directions:
- Lower-precision scoring: dot products over quantized query/key vectors, trading score fidelity for memory bandwidth.
- Dimensionality reduction: projecting d-dimensional vectors into a smaller shared subspace before scoring, shortening the dot product by some factor.
- Hierarchical or block-level aggregation: compressing several consecutive keys into a single proxy representation (for example, 4 keys into 1), selecting blocks first and tokens within them second.
All three work, and all three pay the same price: recall. If the indexer drops a key that should have been selected, the refined stage cannot recover it, and the visible symptom is accuracy degradation on long-context tasks. Low precision produces score ties; dimensionality reduction discards discriminative features; block aggregation introduces a failure mode where the correct token is crowded out by other tokens in the same block. In other words, compressing the indexer is a local trade-off within the “speed–recall–accuracy” triangle, not a change to the asymptotic complexity.
5. Latent Sparse Attention: Moving Retrieval into a Compressed Space
The idea behind Latent Sparse Attention (LSA) is not to make scoring cheaper but to change what gets scored: instead of exhaustively retrieving in the original token space, build a fixed-length, compressed representation of the context, perform sparse retrieval in that latent space, and then do a small-scale refinement back on the original tokens.
Conceptually, this is a two-level retrieval scheme:
# Conceptual sketch: indexing stage with two-level retrieval# 1) Block compression: every B tokens become r latent vectors (r << B, usually fixed)latent_blocks = compress(context, block_size=B, latent_dim=r) # O(T * B * d)# 2) Block-level coarse filtering: score against latents,# cost scales with number of blocks, not number of tokensscores = dot(query, latent_blocks) # ~ (T/B) candidatestop_blocks = approx_topk(scores, k=k1) # k1 blocks move on to refinement# 3) Token-level refinement: score original keys only inside selected blocks,# candidate set size ~ k1 * Bcand = gather(context_keys, top_blocks)final_idx = topk(dot(query, cand), k=k2) # k2 = tokens that attend# 4) Sparse attention: computed only over final_idxout = sparse_attention(query, context_values[final_idx])
This structure yields two important properties:
- The candidate set decouples from T. Coarse filtering compares the query against O(T/B) latent vectors rather than T keys, and refinement operates on a candidate set of size k1·B, independent of total context length. The indexer therefore shifts from quadratic growth to near-linear growth, and overall prefill enters the subquadratic regime.
- Retrieval happens in a “cleaner” space. Latent vectors are a low-rank, redundancy-reduced representation of block content, so their discriminative signal-to-noise ratio is higher; at the same budget, recall is clearly better than dimensionality-reduced dot products over raw keys. Compression stops being a pure accuracy loss — it compresses the noise along with everything else.
LSA differs from another family of approaches, low-rank latent KV caches, in its objective function. The latter compresses in order to save memory bandwidth, and its compressed products still participate in attention; LSA’s latents primarily serve retrieval, while the attention input remains the original (or lightly reconstructed) key/value. That gives LSA a shorter path for accuracy loss.
6. How to Read the Reported Speedups
Public reports cite two sets of numbers: at the 10M-token scale, a single attention layer’s prefill achieves roughly 22.7× and 72.4× speedup respectively, while maintaining accuracy close to full attention on long-context benchmarks. Three qualifications are needed to interpret these figures:
- The denominator is “attention layer,” not end-to-end. By Amdahl’s law, end-to-end gains are further diluted by MLPs, communication, sampling, and KV-cache writes.
- Speedups depend heavily on the baseline implementation. When the baseline model’s indexer is already low-precision and block-sparse, its share is lower and there is less room to compress; conversely, a baseline with high-dimensional exact scoring produces a much more dramatic multiple. The gap between 72.4× and 22.7× comes mainly from differences in baseline architecture, not from the method behaving differently on two models.
- Accuracy conclusions depend on task distribution. Claims of near-full-attention quality are usually established on retrieval-style and aggregation-style long-context tasks; for tasks requiring whole-document global statistics or cross-corpus aggregation, any sparse approximation degrades more visibly.
A more reliable way to evaluate is therefore to look at the shape of the curve: sweep the context from 128K to 1M, 4M, and 10M, and observe whether prefill time grows linearly or near-linearly, or whether a quadratic knee reappears.
7. Engineering Notes for Deployment
1. Profile first, then act
Confirm that the indexer genuinely dominates on your own model and hardware. The method is simple: measure prefill time at 1M and 4M tokens. If the ratio is clearly greater than 4 (close to 16 indicates quadratic behavior), the indexer is still the bottleneck.
2. Block size and latent dimension are the primary knobs
Blocks that are too small push the number of candidate blocks back up, offsetting the gains from coarse filtering; blocks that are too large raise refinement cost inside the block and hurt recall. The latent dimension determines the compression ratio and discriminative power. A two-dimensional sweep with recall@k as an intermediate metric is recommended rather than looking only at final loss — intermediate metrics converge faster and make problems easier to localize.
3. Make memory movement and scheduling cooperate
Latent vectors are usually small enough to stay resident on chip or in a high-bandwidth cache level, so coarse filtering should be implemented as batched GEMV/GEMM rather than a per-query loop. Refinement inside blocks should use small gather-based operators, avoid global sorting, and prefer approximate selection algorithms (hierarchical filtering, radix selection, and similar).
4. Sequence parallelism must split indexer state the same way
Very long contexts require context parallelism, so latent vectors and block summaries must be partitioned with the same blocking strategy. During coarse filtering, exchange candidate block identifiers with a single reduction, moving only candidates rather than the full KV set — otherwise communication becomes the new bottleneck.
5. Don’t take positional encoding and causal masking for granted
When positional information is applied to the compressed representation, the relative positions of tokens within a block must be recoverable. Causality must be preserved so that a query can never see latent vectors of any future block. During incremental decoding, only the new block’s latent vectors need to be appended, with the candidate set maintained incrementally.
6. Training and inference must stay consistent
If a model is trained with full attention and switched to sparse retrieval at inference time, that is out-of-distribution generalization and long-context capability drops noticeably. A workable approach is to enable the same sparse pattern from the long-context continued-pretraining or post-training stage onward, and to keep a few full-attention layers as “anchors,” trading cost for stability.
8. Evaluation Checklist: How to Tell Whether the Optimization Actually Holds
- Report per layer: separate prefill from decode, and single operator from single layer from end-to-end. Avoid substituting a single-layer number for an end-to-end conclusion.
- Use a hardware view: report memory bandwidth utilization and operator arithmetic intensity, showing that the speedup comes from saved bandwidth rather than wasted compute.
- Use a curve view: at least three context lengths, to verify that the growth order has genuinely dropped.
- Use a quality view: regress on recall@k, long-context retrieval and multi-hop tasks, perplexity, and long-output stability together, to prevent “faster and dumber.”
- Use a stability view: latency jitter across input lengths and batch sizes; for sparse operators, tail latency often matters more than the mean.
9. Supporting Platform Capabilities
For teams running very long contexts in production, infrastructure matters alongside the algorithmic work:
- Elastic GPU capacity: scale container platforms or GPU instance pools with prefill peaks instead of holding expensive capacity for peak load year-round.
- Cache and object storage: persist block summaries, latent vectors, and other intermediate representations so the same long context does not require recomputing its index.
- Message queues and asynchronous preprocessing: build block compression and index structures offline, moving that cost off the online request path.
- Logging and monitoring/alerting: instrument the indexer’s share of latency, candidate recall, and latency percentiles by context length, so a “quadratic knee” shows up in business metrics rather than at the next capacity alarm.
On Baidu AI Cloud, this kind of requirement is typically met by combining containerized GPU inference services, object storage and caching, logging, and monitoring/alerting capabilities, together with autoscaling policies to control cost, without binding to any single implementation.
10. Conclusion
The next round of performance gains for very long contexts does not come from making sparse attention “even sparser.” It comes from pushing the growth order of indexer cost from quadratic down to near-linear. The value of Latent Sparse Attention is that it offers a structural lever: a fixed-length, low-rank, redundancy-reduced representation of the context takes on the coarse-filtering job, so that original tokens are only precisely computed over a small necessary candidate set.
For developers, this translates into three actionable judgments. First, quantify the indexer’s share before committing effort. Second, optimize memory movement and scheduling rather than pushing precision down by default. Third, treat recall as a first-class metric and include it alongside accuracy regressions in release gates. With those three in place, 10M-token prefill can realistically land inside acceptable latency and cost bounds.
