Scaling Sparse Attention to 10M Tokens: How Latent Sparse Attention (LSA) Cuts Indexer Overhead

    As context windows push from one million toward ten million tokens, the bottleneck in long-context models has shifted from computing attention to deciding what to compute. This article explains why the sparse-attention indexer becomes the dominant cost at extreme context lengths—where up to 98% of prefill time is spent scoring rather than attending—and examines Latent Sparse Attention (LSA), a method that moves pairwise scoring into a compressed latent space to reach sub-quadratic indexing while preserving accuracy through precise read-back in the original space. You will learn how to read the reported 22.7x and 72.4x layer-level prefill speedups correctly, follow a six-step adoption checklist, understand where the approach breaks down, and set up an experiment environment to validate it.

    Introduction: A Cost Hidden by “Savings”

    Over the past year, long-context capability has climbed a clear curve. First, million-token context became the default spec for flagship models’ official services. Then architectures that mix sparse and linear attention were introduced into cost-focused lightweight models. All of these approaches share one underlying choice: instead of having each query traverse every historical token, they let it select only the few most relevant keys to take part in the computation.

    The choice itself is not controversial. What began to spiral out of control, as context pushed toward the ten-million-token range, was a cost that had originally been a small fraction of the total: indexing.

    Take one global attention layer of a mainstream long-context model. During prefill at 10M tokens, roughly 98% of the time is not spent on attention computation itself, but on the indexer that “decides which tokens to look at.” In other words, sparse attention optimized away the expensive part, yet let another stage become the new dominant term.

    The nature of the problem has therefore changed. Sparse attention has long proven that “looking at only a small part” is enough to preserve accuracy. What actually blocks ultra-long context is that the cost of “finding that small part” still grows quadratically with context length.

    A research team, together with a European technical university, has jointly released a method called Latent Sparse Attention (LSA). According to the published results, at 10M tokens a mainstream long-context model achieves about a 22.7x prefill speedup on a single attention layer, while a 27B-class open-source model sees about a 72.4x speedup, with accuracy on multiple tasks remaining close to the original models. Both the paper and the code are open-sourced, but this article cites no specific addresses and discusses only the technical core.

    1. Cost Structure Revisited: Where Does the Quadratic Come From?

    In standard full attention, each query must compute relevance against all preceding keys. With context length T:

    • In the prefill stage, total compute is roughly O(T²), with the attention part adding an O(T²·d) matrix multiply on top;
    • In token-by-token decoding, each step sweeps the full KV cache, costing O(T) per step.

    Going from 1M to 10M, prefill attention compute scales by the square—100x. More troublesome is memory and memory access: even with highly efficient operators, the capacity and bandwidth pressure of the KV cache is a linear hard constraint.

    Two kinds of cost must be distinguished here:

    1. Arithmetic cost: the total number of floating-point multiply-adds, which determines whether compute is fully saturated;
    2. Memory-access and scheduling cost: reads and writes of intermediate results, kernel launches, and the construction of index structures plus random gather.

    Sparse attention was intended to compress both kinds of cost at once, but at ten-million tokens the share of the second kind swells abnormally—and this is exactly the source of the “hidden bill.”

    2. The Division-of-Labor Paradigm of Sparse Attention and Its Paradox

    The structure of mainstream sparse attention can be abstracted into two stages:

    1. # Stage 1: Index (select a candidate key set for each query)
    2. scores = indexer(Q, K) # lightweight scoring, outputs T x T relevance
    3. topk_idx = topk(scores, k) # keep k candidates per query
    4. # Stage 2: Sparse attention (compute only on candidates)
    5. out = sparse_attention(Q, K, V, topk_idx)

    Stage two’s cost is compressed to O(T·k), where k is usually only a few hundred to a few thousand—negligible relative to T. So the total cost is almost entirely determined by stage one.

    The essence of stage one is this: to know which k keys are most relevant, you must first score all keys. That is the paradox—using O(T²) scoring to buy O(T·k) computation. When k ≪ T, this trade is still worthwhile at the million-token level, but at ten-million tokens the scoring overhead is already of the same order as full attention, and can even be slower because its memory-access pattern is worse.

    The premise that makes this paradigm valid does exist. Existing work has validated, at 128k context, that letting each query look only at its “truly” most relevant 512 keys (about 0.8% of all keys) still retains roughly 98% of full-attention performance on mainstream long-context benchmarks. In other words, sparsity is not a compromise but a validated structural redundancy. What remains is purely an engineering question: how to find those 512 keys cheaply.

    3. The Boundaries of Existing Optimization Routes

    Before LSA, industry made many attempts to cut indexer costs, along roughly four lines:

    Route Approach Limitation
    Lower scoring precision Indexer uses FP8/INT8 or even lower precision Only reduces the constant factor; still quadratic
    Lower scoring dimension Project head dimension into a smaller space before computing similarity Dimensionality compression degrades ranking quality; recall drops
    Multi-key aggregation compression Compress every 4 adjacent keys into 1 before scoring Limited compression ratio; introduces boundary error
    Block sparsity + two-level screening Compute block-level scores first, then refine within blocks Recall insufficient when blocks are too coarse; reverts to the original problem when too fine

    What these methods have in common is worth noting: they optimize the unit price of a single scoring pass, not the number of scoring passes. When context grows tenfold each time and the number of scorings grows quadratically, unit-price optimizations are quickly swallowed by scale. To truly escape the quadratic, you must change the representation and algorithmic structure of indexing.

    4. LSA’s Core Idea: Move Scoring into the Latent Space

    From the public information, LSA’s key abstraction can be summed up in one sentence: don’t do full pairwise scoring in the original key space. Instead, first compress the key sequence into a low-rank latent representation, let queries interact with that latent representation, obtain a candidate set at a sub-quadratic cost, then return to the original space for precise sparse attention.

    Broken down, there are three layers of design:

    1) Latent Compression. A length-T key sequence is mapped, through a learnable low-rank projection or block aggregation, to a latent token sequence far smaller than T (length T/r, where r is the compression ratio). This superficially resembles “multi-key compression,” but the difference is that both the dimensionality and the number of positions of the latent space are trainable parameters. The model can learn, during training, to encode “which information must be retained for retrieval,” rather than relying on fixed adjacent-aggregation rules. The compressed representation serves as both the index and the carrier for retrieval.

    2) Sub-Quadratic Scoring. The cost of computing similarity between queries and latent tokens drops from T×T to T×(T/r). When r grows adaptively as context grows, the overall trend slides from quadratic toward near-linear. This corresponds to the “towards subquadratic” phrasing in the paper’s title—the goal is not to eliminate the quadratic, but to make it no longer dominant in the practical range.

    3) Sparse Read-back and Accuracy Guarantee. After obtaining the candidate set, return to the original, uncompressed K/V for precise attention. This step guarantees that output numerical accuracy is unaffected by compression error—compression acts only on “selection,” not on “computation.” Usually a few mandatory positions are also retained (such as attention sink tokens, a local window, and the most recent few tokens) to cover the high-frequency access patterns that compression might miss.

    The illustrative pseudocode structure is roughly as follows:

    1. def lsa_attention(Q, K, V, compress_ratio=64, k=512, keep_local=256):
    2. # 1. Latent compression: T -> T/r
    3. K_lat, K_lat_pos = compress(K, ratio=compress_ratio) # learnable projection / block pooling
    4. # 2. Sub-quadratic scoring: T x (T/r), far smaller than T x T
    5. coarse = einsum('bhqd,bkcd->bhtkc', Q, K_lat)
    6. # 3. In-block refinement (optional second level; expand original keys only within candidate blocks)
    7. coarse = refine_within_blocks(coarse, K, K_lat_pos, top_blocks=m)
    8. # 4. Add mandatory positions: attention sinks + local window
    9. idx = union(topk(coarse, k), sink_ids, recent_window(keep_local))
    10. # 5. Exact sparse attention over the original, uncompressed K/V
    11. return sparse_attn(Q, K, V, idx)

    5. How to Correctly Interpret the 22.7x and 72.4x

    Here the measurement basis must be emphasized, or it is easy to draw wrong conclusions:

    • This is a single attention layer’s, prefill-stage, operator-level speedup, not an end-to-end throughput gain;
    • The difference between the two models’ speedups (22.7x vs 72.4x) comes mainly from the difference in complexity of their original indexer designs—the heavier the native indexer and the higher the share of the quadratic term, the larger the relative gain after replacement;
    • End-to-end gains are diluted by other parts: MLP layers, normalization, communication, sampling, and so on still grow with their own complexity. If attention is only 30% of the total, even a 20x attention speedup yields only a few times overall improvement.

    The correct expectation should be built on Amdahl’s law: first measure the true share of attention (especially the indexer) in your model and on your hardware, then judge whether the change is worth it. And measured data shows that in the ten-million-token prefill scenario, this share really is high enough to be worth acting on—98% of time spent on indexing means the leverage of changing it is enormous.

    6. Engineering Adoption Checklist

    If you want to validate this line of thinking on your own model or inference framework, proceed in the following order:

    Step 1: Profile, don’t guess. Use a profiler to break down prefill time, separately measuring the time spent on index scoring, top-k selection, sparse attention, and gather/scatter. Many teams find that the real bottleneck is top-k and random access, not floating-point compute.

    Step 2: Evaluate index recall offline. This is the lifeline of any sparse approach. Run full attention over a small-scale context, record each query’s true top-k set, then use the indexer to predict, and compute Recall@k. Below a recall threshold, no speedup is acceptable.

    Step 3: Design an adaptive compression-ratio strategy. A larger ratio r saves more but retrieves more coarsely. In practice, you can tier by layer and by length: shallow layers use a larger r, deep layers a smaller r; for short contexts, fall back to full attention or a lightweight index to avoid the extra overhead at small scale.

    Step 4: Coordinate operators and memory. The latent representation requires extra memory and kernel support. It is advisable to combine it with paged KV-cache management, quantized KV, and chunked prefill, and to fuse the index and sparse attention within the same kernel to reduce round-trip reads and writes of intermediate tensors.

    Step 5: Align on the training side. The latent projection and selection strategy should be introduced in the late pre-training stage or during continued pre-training; otherwise, a distribution mismatch at inference time will cause a noticeable accuracy drop. Existing work generally reports that some scale of continued training or long-context fine-tuning is needed.

    Step 6: Run business-side A/B tests. Don’t rely only on general benchmark scores. Build an evaluation set from real business corpora covering long-document QA, multi-hop retrieval, cross-section summarization, and repository-level code understanding, and monitor latency, memory, and the distribution of failure cases at the same time.

    7. Failure Boundaries and Open Questions

    Every sparsification approach has clear applicability boundaries, and LSA is no exception:

    • Tasks requiring exhaustive scanning: such as exact counting, global ranking, and character-by-character verification, which inherently demand full coverage; sparse selection and compressed representations can both drop information.
    • Extreme needle-in-a-haystack: when there are many target tokens that are scattered and lack salient semantic features, coarse-grained indexing is prone to misses.
    • Accumulated compression error: with many layers in series, index error amplifies layer by layer, and recall in deep layers is often lower than in shallow ones.
    • Limited benefit in the decode stage: the speedups above concentrate in prefill. During token-by-token decoding, the bottleneck is usually memory bandwidth rather than compute, and it needs another set of optimizations (such as KV quantization, tiered caching, speculative decoding) to complement it.
    • Ranking stability under long-tail distributions: the consistency between latent-space similarity ranking and actual attention-score ranking is key to the accuracy guarantee—and the hardest part to guarantee theoretically, one that must be backstopped by large-scale evaluation.

    A pragmatic criterion: map capability boundaries first, then do architecture replacement. Identify which tasks are recall-sensitive, and keep a fallback path to full attention or high-precision indexing for them.

    8. Validation and Experiment Environment Suggestions

    Reproducing this kind of research is not cheap; the main pressure comes from long-sequence memory and training stability. One workable way to organize the experiments:

    • Data side: Store large-scale long-text corpora and evaluation sets in object storage, manage versions by training/evaluation partitions, so multiple experiment groups can fetch data in parallel.
    • Compute side: Use GPU instances with large memory. First validate numerical consistency at short sequences and small scale (aligning with full-attention output), then gradually extend context length.
    • Engineering side: Bring model, operator, data version, and hyperparameters into experiment tracking, so any accuracy drop can be traced back to a specific configuration.
    • Observability side: Hook into logging and monitoring/alerting, and continuously observe metrics such as prefill time, peak memory, and index recall—rather than glancing at them only during offline evaluation.

    Running this whole pipeline in the cloud ultimately relies on a combination of general capabilities: elastic compute, object storage, experiment tracking, and monitoring/alerting. These are infrastructure-level supports; the specific choices should be evaluated against your own scale and cost model.

    9. Conclusion

    The focus of competition in ultra-long context is shifting from “is attention computed fast enough” to “is the index found cheaply enough.” Sparse attention solved the former but transferred the cost to the latter, and the quadratic growth of indexing becomes impossible to ignore at the ten-million-token scale.

    The answer LSA gives has broad methodological value: when the algorithmic complexity of a stage becomes the bottleneck, rather than continuing to optimize its constant factors, it is better to change the representation space it operates on. Moving pairwise scoring into a compressed latent space, replacing per-key precise scoring with a learnable low-rank representation, and then using precise attention in the original space to hold the line on accuracy—this two-level structure of “coarse selection in the latent space, fine reading in the original space” can be transferred to many scenarios with the same quadratic bottleneck, such as vector retrieval, long-sequence modeling, and graph sampling.

    For engineering teams, the real question to answer first is not “should we adopt sparse attention,” but: at ten million tokens, does your system spend its time computing attention, or deciding what to compute? Once that is clear, the direction for optimization naturally becomes clear as well.