Latent Sparse Attention (LSA): 22x Faster Sparse Attention in the 10M-Token Context Era

    As long-context language models move from million-token contexts toward ten-million-token contexts, sparse attention still reduces attention computation but often leaves an expensive token-selection step behind. This article explains why the indexer becomes the bottleneck, how Latent Sparse Attention (LSA) moves selection into a latent index space to achieve subquadratic indexing, and what the reported speedups mean. It also covers training, inference, evaluation, deployment considerations, and limitations. The reported 22.7x and 72.4x speedups are single-layer prefill results, not end-to-end throughput gains.

    1. Million-Token Context Becomes a Specification; 10M Tokens Push the Bottleneck to Indexer Scoring

    Recently, long-context capability has shifted from a selling point to a specification. Some leading model providers have begun offering million-token-level context as part of their default services, while newer models are exploring hybrid architectures that combine sparse attention, linear attention, and global attention. Behind these approaches is a common judgment: when the context is long enough, having every query scan all historical tokens is neither necessary nor economical.

    At the million-token scale, sparse attention has repeatedly shown that selecting only the most relevant tokens for computation can provide clear efficiency gains while keeping accuracy loss under control. However, as the context moves toward ten million tokens, a new problem becomes more prominent: what often slows the system down is not the attention computation itself, but the indexer scoring stage targeted by Latent Sparse Attention (LSA), namely the step that decides which tokens should be attended.

    The paper reports a representative observation: at 10M tokens, when running prefill for a certain global attention layer, about 98% of the time is spent not on attention computation but on the indexer that decides which tokens to attend. This ratio comes from a specific measurement in the paper under particular layer types, context lengths, model conditions, and hardware conditions, and it should not be generalized directly to all systems. To reproduce the result or make an engineering judgment, one should at least record consistently: layer type, context length T, index dimension d_i, attention dimension d, batch size, numerical precision, and whether communication and memory-access overhead are included. Different measurement assumptions can lead to very different conclusions.

    The nature of the problem has therefore changed. Sparse attention has already shown that attending to only a small subset of tokens can preserve accuracy. What blocks ultra-long context is now the cost of finding that subset, which still grows quadratically with context length.

    2. The Cost Structure of Sparse Attention: The Overlooked Indexer Bill

    2.1 Baseline Cost of Full Attention

    In standard full attention, every query computes relevance against all previous keys. Let the context length be T and the per-head dimension be d:

    • Prefill stage: T queries interact pairwise with T keys, so the computation is approximately O(T²·d).
    • Decode stage: For every generated token, the new query must interact with all historical keys, so each step is approximately O(T·d).

    When the context grows from 1 million to 10 million tokens, prefill attention computation theoretically needs to grow by about 100x. This is the fundamental reason why long-context inference must introduce sparsification, linearization, or hierarchical indexing.

    2.2 Sparse Attention Solves “Compute” but Not “Find”

    The basic idea of sparse attention is to split the work into two steps:

    1. A lightweight indexer selects the k most relevant keys for each query.
    2. The actual attention is computed only over these k keys.

    The attention cost therefore drops from O(T²·d) to O(T·k·d). When k is much smaller than T, the benefit is very clear.

    This idea relies on one premise: the model really does need only a small number of keys. The paper’s appendix provides a reference validation: under a 128k context setting where each query retains only 512 keys, 512/131072 is about 0.4% of all keys. In that setting, the larger models reported in the paper still retained about 98% of full-attention accuracy on mainstream long-context benchmarks such as RULER. This indicates that “attending to only a small subset” is not merely an engineering compromise, but a design choice with experimental support.

    2.3 The Indexer Hides the Quadratic Term

    The problem is that, to know which 512 keys are most relevant, the indexer must first score candidate keys. If it scans all T keys for each of the T queries, the cost is still O(T²).

    Most mainstream sparse attention methods today do not avoid this issue:

    • Dynamic Sparse Attention (DSA): Scores all keys first, then selects the highest-scoring ones.
    • Sparse attention for compression scenarios: Reduces the scoring burden by lowering precision or compressing the representation dimension.
    • Block sparse attention: Selects blocks first and then computes within blocks, or aggregates consecutive keys before scoring.

    These approaches reduce constants, and some reduce the asymptotic order, but if they do not change the action of “scanning all history for every query,” the indexer will remain a critical path in long-context scenarios.

    The prefill attention cost can be roughly divided into two parts:

    1. # T: context length; d: per-head dimension
    2. # k: number of keys actually used by each query; d_i: key dimension of the indexer
    3. # c_idx, c_attn: constants related to hardware and operator implementation
    4. prefill_cost ≈ c_idx · T² · d_i # Indexer: score all keys for each query
    5. + c_attn · T · k · d # Sparse attention: compute only selected keys
    6. When k << T, the first term grows quadratically with T,
    7. while the second term grows linearly with T.
    8. As T becomes larger, the indexer takes a larger share of total cost.

    This explains why the indexer dominates the cost at 10M tokens: sparse attention has already made the second term small, while the remaining major cost comes from the first term. The problem is no longer how to “look” better, but how to “find” faster.

    2.4 Quadratic Growth Affects Both Prefill and Decode

    The indexer overhead is not limited to prefill; it exists throughout the inference process.

    Prefill is mainly compute-bound. At 10M tokens, the indexer needs to perform a large amount of scoring and filtering. If token-by-token scoring is used, the computation grows rapidly with context length. The actual latency depends on layer type, model dimension, index dimension, batch size, precision, and whether communication and memory-access overhead are fused. It cannot be extrapolated without a clear measurement setup.

    Decode is mainly memory-bandwidth-bound. Even if attention reads only the K/V of k keys, the indexer may still need to access historical index structures during decoding. As a simplified theoretical estimate for a single layer, a single step, an index key dimension of 128, and FP8 storage:

    • Each step may need to read about 10M × 128 B ≈ 1.3 GB.
    • The 512 K/V entries that actually participate account for only about 128 KB.
    • The difference is more than 10,000x.
    • If the model has dozens of layers, generating one token may move tens of GB of data just for the indexer.

    This is a simplified estimate used to illustrate the trend, not a universal conclusion. Actual systems must also consider batch size, KV cache layout, operator implementation, communication overhead, storage hierarchy, and scheduling strategy. The longer the context, the closer the indexer’s memory traffic gets to full K/V access. The bandwidth savings achieved by sparse attention during decode may be consumed again by the indexer.

    There is also an easily overlooked illusion: at context lengths such as 128k, which are relatively common today, the indexer overhead share may appear limited and can be mistakenly treated as an implementation detail. The ratio of indexer time to attention time is roughly:

    1. indexer_time / attention_time ≈ c_idx · T · d_i / (c_attn · k · d)

    This ratio is proportional to T. Every time the context expands by 10x, the relative overhead of the indexer compared with attention also increases by about 10x. Therefore, optimization conclusions drawn at 128k cannot be simply extrapolated to 1M or 10M.

    2.5 The Optimization Goal Should Be: Selection Must Be Subquadratic

    Long-context optimization therefore needs to be reframed:

    It is not enough to make attention compute less; the indexer must also find faster.

    The complexity comparison can be summarized as follows, treating d, k, and L as constants:

    Method Prefill Indexer Cost Decode Per-Step Indexer Cost Key Characteristics
    Full attention O(T²) O(T), requires reading all K/V No indexer, but every step reads full K/V
    Sparse attention with token-wise scoring O(T²) O(T), indexer memory access is roughly equivalent to full K/V Attention is sparse, but selection remains expensive
    Block sparse / multi-level selection Lower than token-wise scoring, depending on block size and implementation Lower than O(T) Often offset by context parallelism, memory locality, and other factors
    Latent Sparse Attention (LSA) Approximately O(T) Approximately O(1), interacting only with fixed-size latent variables Selection itself is subquadratic

    3. Latent Sparse Attention: Moving Selection into Latent Space

    The paper Latent Sparse Attention: Towards Subquadratic Ultra-Long Context Attention proposes Latent Sparse Attention (LSA). The work is presented as a collaboration between a European startup research team and researchers from a Swiss technical university. Specific authors, institutions, paper links, and experimental configurations should be based on the official paper page. Its core claim can be summarized in one sentence:

    Instead of having each query directly search through T historical tokens, let it complete the selection in an index space formed by latent variables.

    3.1 From Token-Wise Search to Latent-Space Localization

    The problem with token-wise scoring is that each query must be compared against all historical tokens one by one, so the cost grows with T. A more hidden issue is that noise in the scoring space also accumulates as the context becomes longer. The more tokens there are, the more irrelevant keys may happen to receive high scores due to superficial features, making top-k selection less stable.

    LSA first learns a set of compact latent variables and compresses or aggregates retrieval-relevant information from the long context into these latent variables. A query then only needs to complete two steps:

    1. Locate: Interact with the latent variables to decide which regions to search.
    2. Revisit: Return to the corresponding original keys and retrieve the tokens that actually participate in attention.

    Because the number of latent variables is fixed and independent of context length, the cost of selection no longer grows quadratically with T. The term “Subquadratic” in the paper’s title refers to this point.

    3.2 The Essential Difference from Block Sparse Attention

    On the surface, LSA is similar to block sparse attention: both introduce a summary layer above the original tokens. However, the difference between them is structural.

    • Block sparse attention: Each block usually corresponds to a fixed position segment. The summary only covers a local region, and the scoring unit is still O(T/B) blocks. As the context becomes longer, more units need to be scanned.
    • LSA: Latent variables are not bound to fixed positions. They are learned during training to decide “what to remember.” The number of objects a query interacts with is mainly determined by the size of the latent variables and the candidate bucket size, not by the context length.

    A dictionary analogy can help:

    • Token-wise scoring is like flipping through the book from the first page to the last page.
    • Block sparse attention is like first turning to an index of radicals and then searching within several pages.
    • LSA is like first reading a summary catalog that covers the whole book and lists only key entries, then going directly to the content that needs to be read in detail.

    3.3 Illustrative Implementation: Global Block Prior + Query-Level Reranking

    The following pseudocode is only an illustration of the idea of “global block prior + query-level reranking.” It omits details such as multi-head attention, causal masking, distributed partitioning, and exact intra-block top-k selection:

    1. # Illustrative pseudocode: global block prior + query-level reranking
    2. # L: number of latent variables; b: block size; k: final number of retained keys
    3. # C: number of candidate blocks retained for each latent variable
    4. build_index(k_cache):
    5. idx_k = Wk(k_cache) # [T, d_i]
    6. logits[t, l] = idx_k[t] · latent[l]
    7. weights[:, l] = softmax(logits[:, l]) # Normalize over the token dimension
    8. latent_kv[l] = sum_t weights[t, l] * idx_k[t]
    9. blocks[j] = mean(idx_k[j*b:(j+1)*b]) # [T/b, d_i]
    10. block_prior[l, j] = latent_kv[l] · blocks[j]
    11. for l in range(L):
    12. bucket[l] = TopK(block_prior[l, :], C) # Fixed candidate bucket
    13. select(q):
    14. latent_scores[l] = q · latent_kv[l]
    15. # Perform query-level reranking only within fixed candidate buckets
    16. # to avoid scanning the entire history
    17. for j in union(bucket):
    18. score[j] = sum_l latent_scores[l] * block_prior[l, j]
    19. final_blocks = TopK(score, k/b)
    20. # Then collect tokens within final_blocks and perform exact intra-block top-k

    The key point here is that block_prior is a global block prior and does not depend on a single query. latent_scores is the query-level signal used to rerank candidate blocks. If an implementation lets every query scan all blocks again, or lets candidate buckets grow with context length, the complexity may still degenerate. Therefore, LSA’s subquadratic advantage depends on three engineering premises: fixed latent variables, controlled candidate buckets, and reusable global priors.

    3.4 Complexity and Parallelism Benefits

    Under the illustrative implementation above, the index cost can be divided into two parts:

    1. build_index ≈ O(T·L·d_i + (T/b)·L·d_i + T·d_i)
    2. single-query select ≈ O(L·C + k)

    When L, b, C, and k are treated as constants, the total prefill index cost is approximately O(T), rather than the O(T²) cost of token-wise scoring. The premise is that the global block prior is built only once, and query-level processing is only lightweight reranking over fixed-size latent variables and candidate buckets. If candidate buckets grow with T, or if every query scans all block summaries, this conclusion does not hold.

    In sequence-parallel scenarios, LSA also has a communication advantage. Each rank processes a segment of the sequence, and the latent variables are a fixed-size global summary that is much smaller than full K/V. After each rank computes its local summary, only one small-scale global reduction is needed so that all ranks can see the global latent index. This avoids moving TB-scale K/V data across multiple devices.

    4. Interpreting the Results: The 22x Speedup Comes from the Indexer, Not End-to-End

    The paper reports that at 10M tokens, LSA achieved approximately 22.7x and 72.4x speedups on prefill for one attention layer in two models, while maintaining accuracy close to the original models on a series of tasks. Specific model names, layer types, hardware configurations, and measurement setups should be based on the paper. It must be emphasized here that these are experimental results for a single attention layer during prefill, and they are not equivalent to end-to-end throughput improvement.

    These numbers can be understood as follows.

    First, the speedup magnitude is close to the indexer’s share of the original runtime. If most of an attention layer’s time is spent on the indexer, then greatly compressing the indexer naturally leads to a significant reduction in the end-to-end time of that layer. The reported 98% indexer time share is an important background for speedups above 20x.

    Second, the reason larger models benefit more can be roughly modeled as follows:

    1. single-layer speedup ≈ 1 / [(1 - p) + p / s]
    2. # p: share of indexer time in the original implementation
    3. # s: speedup of the indexer itself

    Larger models usually have higher per-layer attention dimensions, so the absolute cost of token-wise scoring is larger, making p closer to 1. In contrast, LSA’s index cost mainly depends on the number of latent variables and the candidate bucket size, and it does not scale proportionally with model size. Therefore, larger models can obtain higher leverage from indexer speedup.

    Third, “maintaining similar accuracy” shows that the key to long-context tasks is localization. In the 128k context setting with 512 keys, the model retains only about 0.4% of keys but can still preserve relatively high accuracy. This suggests that the difficulty of long-context tasks lies mainly in locating the correct information, not in how many tokens the model interacts with.

    Fourth, the prerequisites need attention. Actual gains also depend on the indexer’s share of total inference time, parallelism efficiency across layers and stages, memory-bandwidth bottlenecks during decode, candidate block quality, and training adaptation. A single-point speedup cannot automatically translate into business throughput improvement.

    5. Engineering Implementation: Making Subquadratic Indexers Run Effectively

    5.1 Training: Let the Model Learn to Locate in Latent Space

    The effectiveness of sparse attention is based on one premise: the model must learn to rely only on a small number of tokens. If the indexer and attention are not trained sufficiently, the model may over-rely on other parts of the context, ultimately leading to accuracy degradation. In practice, there are three key points:

    • Long-context continued training: Jointly optimize the latent variables, index projections, and the backbone model. Gradients flow from the attention layers back to the indexer, forcing the indexer to learn “what to remember.”
    • Progressive window expansion: Train on shorter contexts first, then gradually increase the length, for example 32k → 128k → 1M → 10M. Each stage should continue the parameters and optimizer state from the previous stage to reduce training instability.
    • Preventing attention collapse: If the indexer concentrates weights on a small number of tokens too early, the remaining tokens may lose gradient signal. Entropy regularization or an annealed learnable-temperature strategy can be used to make selection smoother early in training and more concentrated later.

    5.2 Inference: Make Latent Variables an Incrementally Maintained Global Index

    Latent variables need incremental updates. During decoding, every new token changes the global context, so latent variables should also be updated incrementally rather than recomputed from scratch each time. There are two key engineering points:

    • The update method must be consistent with training, such as the decay coefficient of the exponential moving average, normalization method, and temperature parameters. Otherwise, distribution shift may be introduced.
    • Latent variable updates are serially dependent: step t depends on the previous step. Block summaries and candidate bucket maintenance can be partially parallelized. When orchestrating kernels, these operations should be pipelined and overlapped to avoid unnecessary waiting.

    Prefill and decode have different roles.

    • Prefill: Compute-intensive. Latent variables, block summaries, and batch indexing are computed at once. The goal is to maximize tensor-core utilization.
    • Decode: Memory-bandwidth-intensive. The indexer only needs to interact with fixed-size latent variables and controlled candidate buckets, and no longer scans the context linearly. The longer the context, the more obvious the bandwidth savings become.

    This division naturally fits the prefill-decode disaggregation deployment mode. When using PD separation, the following points also need to be checked:

    • The bandwidth and latency of migrating KV cache from prefill nodes to decode nodes.
    • Whether latent variables, block summaries, and candidate buckets need to be synchronized, and at what frequency.
    • Whether scheduling overhead offsets the benefits of the indexer.
    • The impact of cross-node communication, cache consistency, failure retries, and elastic scaling.

    Context parallelism and KV offloading.

    • Sequence parallelism: Use a two-level structure of “global latent variables + local block summaries” to reduce cross-device communication volume.
    • Hierarchical KV cache: When cold data is moved to external storage, keep only latent variables, block summaries, and candidate block indices in GPU memory, and fetch the original K/V when needed.

    5.3 Validation: Do Not Only Check “Can It Find?”

    Long-context systems should cover at least three types of evaluation tasks:

    1. Needle-in-a-haystack retrieval: Verify “can it find?”
    2. Multi-hop reasoning and aggregation tasks: Verify “can it use the information correctly after finding it?”
    3. Model-capability-related tasks: Such as code and math, to verify whether overall capability has regressed.

    A minimal evaluation set can be designed as follows:

    • Needle-in-a-haystack: One single-needle task and one multi-needle distraction task. Pass criteria can reference target-snippet recall or answer accuracy, for example, not lower than a preset threshold of the full-attention baseline.
    • RULER multi-hop: One multi-hop question-answering task and one aggregation statistics task. Focus on whether multi-hop chains break and whether aggregation results are accurate.
    • Long code or math: One repository-level question-answering task and one long reasoning task. Focus on whether obvious regressions or tool-call failures occur.

    A full-attention baseline must be set. The score of the same model’s full-attention version, or the same model’s short-context version on the same tasks, is the only reference for judging whether accuracy loss is acceptable. If the same model is used for block sparse attention and LSA, differences may come from both the sparse strategy and the model itself, so they need to be evaluated separately.

    Metrics that need separate monitoring include:

    • Selection quality: The attention-quality share of selected keys, namely attention recall, and cross-layer stability.
    • Performance: TTFT, prefill throughput, decode memory-bandwidth utilization, and indexer time share.
    • Length sensitivity: Repeat tests under different context lengths and plot curves showing how indexer time share and attention recall change with length. If recall drops significantly as the context grows, it may indicate insufficient latent capacity or insufficient training.

    Long-context benchmarks are often dominated by synthetic retrieval tasks, while real business scenarios often involve multi-document question answering, long-codebase understanding, and multi-turn dialogue summarization. Therefore, it is recommended to build regression baselines on proprietary datasets and cross-check them with public leaderboards.

    5.4 Platform Side: General Cloud Capabilities

    Long-context inference places higher demands on platform resource management and observability. General cloud capabilities can play a role in the following areas:

    • Object storage: Storing original long documents, cold-data K/V, and index snapshots.
    • Message queues: Smoothing peaks and valleys for asynchronous, long-running inference tasks.
    • Container platforms: Elastically scaling prefill and decode instances according to load.
    • Logging services and monitoring/alerting: Tracking metrics such as TTFT, indexer time, attention recall, and KV migration latency.

    On Baidu AI Cloud, these capabilities can be combined to build observable and elastically scalable long-context inference services. Regardless of which attention scheme is used underneath, the evaluation method should remain consistent, and the full-attention result of the same model should be used as the baseline.

    6. Relationship with Adjacent Routes: Complement, Not Replacement

    Current ultra-long-context technologies can be roughly divided into four routes:

    • Full attention: Has the highest quality ceiling, but complexity is quadratic.
    • Sparse attention: Is sparse in computation, but may still be expensive in selection.
    • Linear attention, state space models, and similar approaches: Have linear complexity and fixed decoding states, but may struggle on precise-retrieval long-context tasks.
    • Latent Sparse Attention: Achieves subquadratic selection while retaining the ability to perform exact top-k selection over original keys.

    The value of LSA is that it fills the shortest board in sparse attention. It does not require overturning existing engineering experience in block sparse attention, quantization, or context parallelism. Instead, it can be stacked on top of these methods.

    Before selection, it is recommended to perform three measurements:

    1. Measure indexer time share: Separately record indexer time, attention time, communication time, and scheduling time to identify the bottleneck.
    2. Measure attention recall: Observe whether the attention-quality share of selected keys decreases as length grows.
    3. Measure TTFT, prefill throughput, and decode bandwidth utilization: Confirm whether the optimization can be translated into business benefits.

    After these measurements, choices can be made based on context scale:

    • 128k-level context: Indexer overhead is usually limited, so mature block sparse and quantization methods can be prioritized.
    • 1M-level context and above: It is necessary to measure indexer time share. If it becomes dominant, latent indexing is worth considering.
    • 10M-level context: Quadratic growth of the indexer is difficult to avoid, so latent indexing often becomes a necessary option.

    7. Limitations and Open Questions

    Objectively speaking, this type of method is still in the stage of paper validation and early engineering exploration. Several issues deserve continued attention.

    First, the information bottleneck of latent variables. The number of latent variables is fixed. Whether they can losslessly summarize all key information in 10M tokens still lacks long-term validation. For tasks where key information is extremely sparse and highly dispersed, such as locating an isolated configuration item among ten million tokens, latent variables may lose necessary details. Possible responses include increasing the number of latent variables, introducing multi-resolution latent variables, or combining with an exact retrieval module.

    Second, accuracy decay during long-context decoding. Prefill speedup does not mean decoding stability. During decoding, latent variables are updated incrementally, and errors may accumulate over time. This requires dedicated evaluation for long-sequence generation.

    Third, training cost and adaptation. Existing models are usually trained under full attention or block sparse attention. Migrating them to LSA requires continued pre-training or carefully designed fine-tuning, which imposes requirements on compute and data. Before adaptation is complete, short-term benefits are more likely to appear in the training of new models.

    Fourth, interaction with quantization, distillation, and other techniques. If the indexer’s precision is reduced, top-k selection may become unstable. The combined effects of quantization, distillation, and sparsity still lack systematic study.

    Fifth, reproducibility and ecosystem maturity. Current evidence mainly relies on data reported in the paper. Whether these methods can run stably in mainstream inference frameworks still requires broader independent reproduction.

    8. Summary

    As context moves from million-level to ten-million-level, the bottleneck of sparse attention has shifted from “compute” to “find.”

    • In terms of compute, sparse attention already performs well: each query interacts with only a fixed number of keys.
    • In terms of find, the indexer that scans all historical tokens for every query still keeps overall complexity quadratic. In the paper’s specific 10M-token, single-layer prefill measurement, the indexer even consumed about 98% of the time.

    Latent Sparse Attention takes a different approach: it moves selection into an index space formed by latent variables, shifting the indexer from token-wise scanning to global block priors and query-level reranking. In the paper’s experiments, a single attention layer in two models achieved approximately 22.7x and 72.4x prefill speedups while maintaining similar accuracy. However, these are single-layer, prefill-level results and should not be directly equated with end-to-end throughput.

    For engineering teams, three takeaways are most direct:

    1. The focus of long-context optimization is shifting from attention operators to indexing mechanisms.
    2. Hierarchical index structures such as latent variables and block summaries can be incrementally maintained, reduced across devices, and stacked with existing sparse and quantization methods.
    3. When evaluating long-context systems, in addition to accuracy and TTFT, teams should include indexer time share and attention-recall changes across lengths in routine monitoring.

    Every time the context expands by one order of magnitude, the quadratic growth of the indexer is amplified again. Whoever can reduce the cost of “finding” first will be able to turn long context into a truly usable capability in the ten-million-token era.