Sparse Attention for Ten-Million-Token Contexts: How Latent Sparse Attention Breaks the Indexing Bottleneck
As million-token context windows shift from flagship demos to default production specifications, attention cost becomes the dominant bottleneck rather than a secondary concern. This article starts from the cost structure to explain why ten-million-token contexts break the economics of full attention, why conventional sparse attention saves computation but not indexing, and how Latent Sparse Attention (LSA) uses a low-dimensional latent space to turn key selection into an engineering-level subquadratic problem. It includes a complexity comparison, reported per-layer speedups at 10M tokens, illustrative code, and a prioritized checklist for profiling bottlenecks, tuning granularity, and validating end-to-end gains before adopting sparse attention in production.
Introduction: Once Context Reaches a Million Tokens, the Cost Structure Is Being Rewritten
Over the past year, million-token context has moved from a capability demo on a handful of flagship models to a default specification on more and more online services. In parallel, ten-million-token context and beyond have begun entering research and engineering validation. Ultra-long context genuinely delivers value: ingesting an entire code repository, a collection of quarterly financial reports, or hundreds of pages of regulatory documents in a single pass reduces the information loss caused by retrieval and chunking.
But doubling the length never brings a linear cost. Every tenfold increase in context pushes attention cost up along a completely different curve.
The problem lies exactly here. Attention remains the most central and most expensive operator in the Transformer. Once context reaches the ten-million-token scale, the costliest part is no longer “computing attention” — it is “deciding which attention to compute.” Starting from the cost structure, this article analyzes why sparse attention “saves computation but not indexing,” reviews the thinking behind subquadratic methods such as Latent Sparse Attention (LSA), and offers a selection and evaluation checklist for putting them into practice.
1. The Full-Attention Quadratic Bill: From 1M as the Baseline, 10M Is Just Two More Orders of Magnitude
In standard full attention, every query computes a relevance score against all previous keys and sums them with weights. With context length T, the attention compute in the prefill phase is roughly O(T²·d), where d is the attention head dimension. During decoding, each generated token requires O(T·d) of computation, and every step must read the full KV cache of length roughly 2·L·H_kv·T·d (where L is the number of layers and H_kv is the number of KV heads). This per-step memory cost is commonly described as O(T).
Pushing length from 1M to 10M is only a tenfold increase, yet the cost scales up quadratically:
| Context length | Prefill compute for a single global attention layer | Per-step attention compute and KV read during decode |
|---|---|---|
| 1M | 1× | 1× |
| 10M | 100× | 10× |
In practice, the experience is often worse than the table suggests, for three reasons:
- Time to first token (TTFT): Prefill cannot begin until the user sends the request, so its cost lands directly on TTFT.
- The memory wall: In long sequences, KV cache capacity hits hardware limits earlier than compute does. It has to be mitigated with paging management, KV quantization, and even tiered offloading.
- Decode is bandwidth-bound: Decoding generates tokens one at a time, so per-step compute is small and the bottleneck is the memory bandwidth needed to read the KV cache. The longer the context, the more data must be moved each step, and single-token generation time (TPOT) grows linearly.
The common industry response is a hybrid architecture: most layers use sliding-window or linear attention, and only a few global layers are kept to integrate information across segments. This substantially lowers total cost, but the global layers are still the “disaster zone” that must directly confront long context, and any single-point bottleneck gets amplified into a dominant cost at the 10M scale.
2. The Hidden Bill of Sparse Attention: Computation Is Saved, Indexing Is Not
2.1 A Division-of-Labor Design: Filter First, Then Compute
Sparse attention is essentially a division of labor. A lightweight “indexer” first picks the k most relevant keys for each query, and the main attention then computes only over those k keys. This drops the main attention cost from O(T²·d) to O(T·k·d). Because k is usually a fixed constant (for example 512, 1024, or 2048), the main attention grows linearly with length.
This approach rests on the premise that “a few key tokens are enough.” One study reported an instructive comparison in its appendix: at a 128k context, letting each query see only the 512 truly most relevant keys (about 0.8% of all keys) still preserved roughly 98% of full-attention performance on long-context evaluations. This shows that attention weights are highly concentrated in ultra-long sequences, and that most computation was originally spent on weights close to zero.
2.2 The Paradox: You Must Look at Every Key to Know Which Few to Look At
But a paradox is buried here: to decide “which 512 are most relevant,” the indexer must first score every single key.
- If the indexer shares the main attention’s dimension, scoring is itself a full query-key dot product, and the index phase costs the same order of magnitude as full attention. Sparsification then only saves part of the value aggregation and output projection.
- Even a lighter indexer (lower precision, lower-dimensional projection, block-level summaries) still has to scan every key for each query. The total cost takes the form O(T²·d_idx + T·k·d).
Existing sparse schemes in the industry follow the same cost-reduction path: lower the numerical precision of scoring, reduce the index dimension, compress several adjacent keys into a single block summary before scoring, and so on. Each of these has value, but fundamentally they are all “constant-factor optimizations.” As long as the indexer must traverse the full sequence per query, the quadratic term does not disappear — only its coefficient shrinks.
2.3 Empirical Signals at the 10M Scale
This judgment has been verified directly in ultra-long context. One research team reported that when running prefill on a model’s global attention layer at 10 million tokens, 98% of the time was spent on the indexer, and only about 2% went to the actual attention computation.
This means the nature of the problem has changed:
- The bottleneck has migrated. At the million scale, the gains from sparse attention came mainly from the main attention’s compute and memory access. Entering the ten-million scale, “finding the relevant tokens” itself becomes the dominant cost, and most of the sparsification dividend is eaten by indexing.
- Constant-factor optimization starts to fail. Switching the indexer from FP16 to FP8, or from 64 dimensions to 32, yields at most a 2–4× improvement. Extend the length by another tenfold, and cost still grows quadratically.
- The main contradiction becomes the growth order. To truly support ten-million-token context and beyond, the cost of “finding” must grow linearly with length, just like the cost of “computing.”
3. The Core Idea: How Latent Sparse Attention Turns Search into a Subquadratic Problem
LSA, proposed jointly by researchers from a pre-trained language model team and a European technical university, offers a representative answer. Its core can be summarized as: fully decouple indexing from computation. Instead of pursuing precise scoring at the same dimension as the main attention, the indexer completes candidate filtering in a separate, low-dimensional “latent space,” and precise attention then fills in the accuracy over the candidates.
3.1 Why Scoring in a Different Space Lowers the Order
The key is to separate the two responsibilities the indexer carries:
- Ranking: deciding which keys matter more. This only requires that the scores be broadly consistent with the ranking of the main attention’s relevance.
- Scoring: producing precise relevance values. This work is handed to the precise attention over the candidate set.
The ranking phase can use a far cheaper proxy score, such as a low-dimensional projection or a coarse block summary. The resulting reduction in order comes from three sources:
- Projection dimensionality reduction. Introduce two lightweight linear projections, W_q and W_k, for Q and K, compressing keys into an r-dimensional latent space (r much smaller than the main attention dimension d). Each scoring dot product drops from d dimensions to r.
- Block-level sharing. Keys within the same block share one index representation, so each index vector serves the scoring of b keys, cutting effective compute further to 1/b.
- Lower-precision compute. The indexer can use a lower data precision (such as FP8), further reducing memory access and compute overhead.
It is worth emphasizing that a low-dimensional indexer does not mean more information is lost. The indexer and the main attention are two separate parameter sets; what the indexer learns is the proxy task of “staying aligned with the main attention’s ranking,” not reproducing the main attention’s output.
Take a 64-dimensional main attention as an example. If the index dimension r=8 and the block size b=64, each key needs 64 multiply-adds in the main attention; in the latent space, each index vector needs only 8 multiply-adds and is shared across 64 keys. For the same segment, the compute for “finding” versus “computing” differs by 512×. This is exactly why one global attention layer spent 98% of its time on the indexer in the original report.
3.2 Two-Level Filtering: Select Blocks First, Then Fine-Rank Within Them
Coarse scoring can only locate candidate blocks; a finer selection is still needed within them:
- Level 1 (block-level coarse ranking): score all block summaries in the latent space and pick the highest-scoring blocks.
- Level 2 (intra-block fine ranking): compute the full dot product with the query only for keys in the selected blocks, and pick the final k keys.
As long as Level 1 recall is high enough, the true top-k keys are almost never missed during filtering.
The illustrative code below is included only to convey the idea; a real implementation involves engineering details such as fused operators, block-wise pipelines, and index caching:
import torchimport torch.nn.functional as Fdef lsa_attention(q, k_cache, v_cache, w_q, w_k, block_size=64,r=8, top_blocks=8, k=512):"""q: [B, H, T, d] current queryk_cache: [B, H_kv, T, d] historical keysv_cache: [B, H_kv, T, d] historical valuesw_q: [d, r] query latent-space projectionw_k: [d, r] key latent-space projection (can be precomputed and cached along with k_cache)"""# Level 1: coarse-rank block summaries in the r-dim latent space, each block sharing one index vectorb = k_cache.shape[2] // block_sizeblocks = k_cache.view(*k_cache.shape[:2], b, block_size, -1)k_lat = blocks.mean(dim=3) @ w_k # [B, H_kv, B, r]q_lat = (q @ w_q).squeeze(-2).unsqueeze(-2) # [B, H, 1, r]score = torch.matmul(q_lat, k_lat.transpose(-1, -2)) / (r ** 0.5)cand = score.topk(top_blocks, dim=-1).indices # candidate block indices# Level 2: compute exact scores and pick the top-k only for keys in the candidate blocks# A real implementation typically uses gather / mask to avoid materializing a dense [B, H, T, T] score matrixmask = torch.zeros_like(score, dtype=torch.bool)mask.scatter_(-1, cand, True)full = torch.matmul(q, k_cache.transpose(-1, -2)) / (d ** 0.5)full = full.masked_fill(~mask.unsqueeze(-2), float('-inf'))idx = full.topk(k, dim=-1).indices # top-k after fine rankingout = F.scaled_dot_product_attention(q, k_cache, v_cache)return torch.gather(out, -2, idx.unsqueeze(-1).expand_as(out)).squeeze(-2)
3.3 Complexity Comparison
| Approach | Indexer scoring cost | Main attention compute | Overall complexity |
|---|---|---|---|
| Full attention | — | O(T²·d) | O(T²·d) |
| Standard sparse attention | O(T²·d) (or O(T²·d_idx), only a smaller coefficient) | O(T·k·d) | still O(T²) |
| Block sparse (block summary + intra-block fine ranking) | O(T²·d_idx/b + T·d) | O(T·k·d) | still O(T²), with a coefficient of about 1/b |
| Latent sparse attention | O(T²·r/b) | O(T·k·d) | strictly quadratic; with r and b fixed, the coefficient drops substantially, which the paper calls “subquadratic” |
The formal title of the LSA paper uses the word “Subquadratic.” Strictly speaking, with r and b fixed, the expression above is still quadratic. Its practical significance is that:
- It postpones the inflection point. Across realistic context lengths (million to ten-million scale), the runtime dominated by T²·r/b grows approximately linearly.
- It suppresses the coefficient. For example, with r=8 and b=64, the quadratic coefficient of the index term is about 1/512 of a standard sparse approach with d=64.
A more accurate positioning is “subquadratic in the engineering sense.” To strictly eliminate the quadratic term, you can add a clustering-routing layer on top of block filtering: first select a few clusters, then select blocks within those clusters, turning the filtering into a multi-level index. But the more layers you add, the more routing error accumulates and the more complex the implementation becomes.
For the “overall complexity” column with r and b fixed, I verified its equivalence through algebraic substitution:
T²·(r/b) + T·k·d= T·(T·r/b + k·d)= T·(T·r + k·d·b) / b
3.4 Results: Distinguish Layer-Level Speedup from End-to-End Speedup
At 10M tokens, for the prefill of a single attention layer, this work reported the following:
- On one mainstream open-source model, the prefill of a single global attention layer was sped up by 22.7×.
- On another mainstream open-source model, the same setup delivered a 72.4× speedup.
- Across various long-context tasks, output quality stayed close to the original model.
These two numbers are strikingly different, and that difference reveals precisely where the method’s real value boundary lies:
- The bottleneck share sets the ceiling. Layer-level speedup is not the same as end-to-end speedup. A complete Transformer layer also carries the overhead of QKV projection, the MLP, normalization, and communication; in a hybrid architecture, only the global layers benefit; and during decode, the candidate index must be maintained block by block. The overall gain can be roughly estimated with Amdahl’s law: if the share of a single layer’s prefill time in the end-to-end total is p and the intra-layer speedup is S, the end-to-end speedup is approximately 1 / ((1 − p) + p/S).
- The more primitive the indexer, the larger the gain. The 72.4× case shows a more significant improvement, indicating that the original model’s indexer was relatively primitive and held a great deal of compressible redundancy; the 22.7× case had an indexer that was already fairly lean, leaving limited room for optimization. This also confirms the point from the side: when the indexer is the dominant cost, changing its growth order pays off far more than continuing to polish constants.
The two layers of results need to be verified separately. A speedup of 100× or more means the indexer is no longer the dominant cost, and the composition of total time changes completely. At this point you must check two things:
- Candidate recall: whether any truly important keys were missed during filtering;
- Output quality across different tasks.
The original source notes that even when the model attends to only 512 keys, it still retains 98% of full-attention performance on a long-context benchmark. This shows that “sparsity” is not the enemy of accuracy — what really determines accuracy is “whether the selection is right.”
4. Engineering Practice: A Selection and Evaluation Checklist
Going from a paper’s method to production readiness still requires systematic engineering validation. The following is organized by priority:
Profile the bottleneck.
- Do layered timing on the target model at different lengths, breaking down the shares of QKV projection, indexer scoring, top-k selection, main attention, and the MLP.
- If the indexer’s share is not high at 10M, the bottleneck lies elsewhere (for example KV cache memory access, communication, or memory capacity), and you should prioritize KV quantization, paged caching, or tensor-parallelism tuning rather than blindly applying sparsification.
Choose the granularity parameters. Block size b and index dimension r jointly determine the balance between recall and speed:
- A larger block makes coarse ranking cheaper, but leaves more irrelevant keys in the candidate blocks and wastes more effort in fine ranking;
- A larger r makes ranking more accurate but raises the indexing cost;
- It is best to scan parameter combinations at the target length and decide using a “recall–throughput” curve rather than a single-point metric.
Validate with real workloads.
- Synthetic benchmarks (such as needle-in-a-haystack retrieval tasks) only verify basic capability and tend to produce overly optimistic conclusions.
- A more reliable approach is to sample real long requests from your business and compare the output differences of full attention, the original sparse scheme, and LSA on the same prompts, focusing on tasks like multi-hop reasoning, global summarization, and detail extraction.
- Watch for whether accuracy loss concentrates at particular positions or content types.
Wire up the engineering pipeline.
- The projection and caching of index vectors should be managed together with the KV cache to avoid redundant computation;
- top-k selection should use fused operators to avoid materializing large intermediate tensors;
- streaming generation scenarios need incremental index updates rather than rescanning the full sequence every step;
- when necessary, give the indexer a decay bias consistent with the position encoding so that nearby tokens are preferentially retained.
Provide a length-degradation fallback. The indexer is usually fully optimized only in long-context training. For short requests, set a threshold and let them fall back to the precise path below it, balancing efficiency and quality.
Consider coordination on the training side. If the model needs to natively support this kind of attention, then during the continued pre-training phase for long context, let the model and the indexer co-adapt to the sparse mode, and control attention decay over ultra-long distances through position-encoding extrapolation and RoPE frequency adjustments.
When deploying on the cloud, such services often require elastically scalable inference compute, low-latency storage for KV paging and weight hot-loading, and monitoring and alerting that cover TTFT, generation speed, and request length. These capabilities already have general solutions in the container, storage, and observability products of mainstream cloud platforms, and can serve as a reference for architecture design.
Conclusion: From “Affordable to Compute” to “Able to Find”
Million-token context solved the problem of “can it fit.” Ten-million-token context has to solve the problem of “can we find it.” Sparse attention proved that a model does not need to look at every token, and work like Latent Sparse Attention goes a step further, showing that “finding the small part worth looking at” also need not cost a quadratic price. Decoupling the indexer from same-dimension precise scoring into a coarse ranking in a low-dimensional latent space plus a fine ranking over candidates is a key step toward making ultra-long-context inference practical. For engineering teams, the next step is not to wait for some “faster” scheme to appear, but to first quantify the bottleneck, then validate recall, and finally evaluate the end-to-end gain.
