Latent Sparse Attention: 22x Speedup Over DeepSeek-Style at 10M Tokens
Prefrontal AI and ETH Zurich introduce Latent Sparse Attention (LSA), which clusters keys in a learned latent space and uses hierarchical bucket search to reduce indexer complexity from quadratic to O(T log T), achieving 22.7x prefill speedup over GLM-5.3-Flash and 72.4x over Qwen3.8-27B at 10M tokens while maintaining accuracy.
As million-token contexts become standard — DeepSeek-V4 and GLM-5.3-Flash both default to 1M — the industry has converged on sparse attention: each query attends only to a small subset of keys. This works well at 1M tokens, but at 10M tokens a new bottleneck emerges. In GLM-5.3-Flash's global attention layer, 98% of prefill time is spent not on attention computation but on the indexer that decides which keys to attend to. Existing sparse methods (DeepSeek's DSA, MiniMax, GLM's block-sparse, Qwen) reduce the indexer's constant factor via lower precision, dimension reduction, or key compression, yet the indexer's work still scales linearly with context length, keeping overall prefill quadratic.
Background: The Hidden Cost of Sparse Attention
Standard full attention costs O(T²) for prefill and O(T) per decode step. Sparse attention splits the work: a lightweight indexer selects k relevant keys per query, then attention computes only on those k keys, reducing attention cost to O(Tk). The premise is that models need very few keys; the paper verifies that at 128k tokens, letting each query attend to its true top-512 keys (≈0.8% of all keys) preserves 98% of full-attention accuracy on the RULER benchmark.
However, the indexer must score every key to find those top-k. Even with optimizations, the indexer's workload grows linearly with T, so prefill remains O(T²). An analogy: to borrow 4096 books from a 10-million-volume library, fetching the books is fast, but you must first scan every spine to decide which to borrow. At 10M tokens, if the indexer cost were zero, sparse attention could be 58× faster still.
LSA: Semantic Grouping and Hierarchical Search
LSA changes how the indexer works. Instead of checking keys one by one, it checks groups of keys . Crucially, groups are formed by semantic similarity , not by position. Existing block-sparse methods group adjacent keys (like boxing books by acquisition date), which can drown a key book in a box of irrelevant summaries. LSA projects keys into a learned low-dimensional latent space, then applies hierarchical clustering (Ward's method) to place semantically similar keys into the same bucket. Each bucket stores a centroid vector and an index table of its member keys' positions.
At query time, the query scores only bucket centroids, selects the most relevant buckets, expands them into concrete keys, and fills the top-k budget. This flat search yields constant-factor gains. The real complexity reduction comes from the Tree (hierarchical) variant : buckets are recursively clustered into larger nodes, forming a tree. The query performs a beam search from the root, descending only through the highest-scoring branches. Each query examines O(log T) centroids, reducing indexer prefill from quadratic to O(T log T) — the subquadratic complexity in the paper's title.
Two Deployment Modes: D-LSA and N-LSA
D-LSA (Distilled LSA) — Plug into Existing Models
Freezes the pretrained model and adds only two small projection matrices per layer to map keys and queries into a 64-dimensional index space. Distillation trains these projections to mimic the original attention distribution, using only 352 million tokens (DeepSeek DSA's dense warm-up alone used 2.1 billion tokens). A completely training-free version uses the principal component directions of keys as the projection; on Qwen3.8-27B it matches the trained version's accuracy.
N-LSA (Native LSA) — Train from Scratch
Uses LSA natively during pretraining. The attention layer clusters its own keys directly — no extra index projections, no teacher model, no auxiliary losses, and zero added parameters. Training relies solely on standard next-token prediction loss.
Engineering Integration
The team wrote custom GPU kernels for H200 and B300 (plus a portable Triton version) covering clustering, scoring, selection, and expansion. LSA is integrated into SGLang with support for tensor parallelism, expert parallelism, pipeline parallelism, and context parallelism for both prefill and decode.
Evaluation at 10M Tokens: Accuracy
D-LSA is tested on Qwen3.8-27B (full attention) and GLM-5.3-Flash (native sparse attention), pushing context to 10M tokens — far beyond their official 1M limits. On MMLU-Pro, GPQA-Diamond, AIME25, MATH500, and LongBench v2, D-LSA stays within the 95% confidence interval of the baselines and does not alter reasoning length.
On RULER (4k–10M tokens), Qwen3.8-27B + D-LSA trails full attention by ≤5 points up to 1M, but at 10M it outperforms full attention (63.9 vs 59.9). GLM-5.3-Flash + D-LSA stays within 3 points of its native sparse attention up to 1M, falls behind by up to 8 points at 2M–5M, and returns to within 4 points at 10M. Note that GLM's baseline was co-trained with sparse attention, while D-LSA is only distilled onto a frozen model, making the comparison favorable to the baseline.
PaperTrail: A New Long-Context Benchmark
To test realistic ultra-long reasoning, the authors created PaperTrail. It embeds a chain of fictional research findings into hundreds of real 2026 arXiv papers: a fictional paper proposes a result, later real papers cite it, then another fictional paper corrects the value and renames the method, while some subsequent papers still cite the old version. The model must trace these evolving facts like a literature review. At 10M tokens (≈400–465 papers), Qwen3.8-27B + D-LSA scores 29.1 vs 19.8 for full attention.
Speed and Memory Results
At 10M tokens, single-layer prefill: D-LSA is 22.7× faster than GLM-5.3-Flash's native sparse attention and 72.4× faster than Qwen3.8-27B's full attention . Decode speedups are 4.6× and 42.5× respectively. The speedup grows with context length: at 1M tokens prefill speedup over GLM is 3.5×, at 512k only 2.1× (because block scanning is cheap at short lengths). Extrapolating, the Tree variant is projected to exceed 90× over baseline sparse attention at 100M tokens.
End-to-end TTFT in SGLang (with context parallelism): GLM-5.3-Flash drops from ~7.5 minutes to ~3.4 minutes (2.2× faster); Qwen3.8-27B drops from ~76 minutes to ~8 minutes (9.2× faster).
Index memory at 10M tokens per layer: D-LSA 246 MiB, GLM-5.3-Flash native 331 MiB, Qwen-style block-sparse 642 MiB.
N-LSA Training Results
N-LSA experiments are smaller scale. A ~500M parameter hybrid model (24 layers, 1 attention layer every 4 layers, others Gated DeltaNet linear attention) was trained with annealing at 128k context. Validation loss matches full attention exactly (1.085 both). Under the same sparse budget, PISA, NSA, and sliding-window attention reach 1.100, 1.117, and 1.154 respectively. On 128k RULER, N-LSA scores 32.2 vs full attention 34.7, while NSA and PISA drop to 19.2 and 14.6. Training speed: single attention layer forward+backward at 128k is 1.6× faster than FlashAttention-3 full attention.
Conclusion
The long-context race has focused on making attention "look at less." From fixed sliding windows to DeepSeek's DSA to various block-sparse schemes, the field has proven that attending to <1% of tokens preserves accuracy. LSA identifies the next bottleneck: when "looking" becomes cheap, "finding" dominates cost. Turning the attention layer into a hierarchical retrieval system is not new (Reformer, Routing Transformer attempted content-based key organization), but few methods have simultaneously validated accuracy and speed at 1M+ scale. As agents take on multi-day research and coding tasks, context windows will keep growing, and the indexer's complexity may dictate the cost curve.
Paper: https://arxiv.org/abs/2610.42147
Code: https://github.com/Prefrontal-AI/latent-sparse-attention
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
