Latent Sparse Attention at 10M tokens — Hierarchical key clusters — What does it mean?
The news. On October 30, 2026, researchers at Prefrontal AI and ETH Zurich posted a preprint on Latent Sparse Attention. On GLM-5.3-Flash at 10M tokens, the distilled variant speeds up one attention layer by 22.7× in prefill and 4.6× in decode over the model's original sparse attention, and by 72.4× and 42.5× over full attention on Qwen-3.8-27B, with similar task accuracy. Read the paper →
Picture a library with ten million books and a reader who wants the few that matter. The expensive part of sparse attention is often not reading the chosen books but deciding which ones to read. The cheap way to decide is to walk every shelf and read every spine, once per reader. That is what a token-level indexer does: it scores every earlier key for every query, so its work grows with the square of the context length during prefill (and linearly per generated token in decode). At 1M tokens and beyond, the paper argues, the indexer itself becomes the thing that stops long context from scaling.
LSA changes how the reader searches, not what the reader reads. Keys are grouped by content into clusters, and clusters are grouped into bigger clusters, like a floor sign, aisle signs and shelf labels. A query reads the few signs at each level, follows the best ones down, and only then picks up individual books. Attention itself is still the normal query-key scoring, run over the small set of keys the walk selected.
How the hierarchy is built
The clusters are made as the context grows, not recomputed for every query. First each index key is length-normalized, and every n_pool consecutive normalized keys are summed into one pooled key, so clustering runs over T / n_pool items instead of T. Keys are then handled in cluster blocks of consecutive positions. When a block is full, its pooled keys are merged bottom-up with Ward's method into a fixed number of buckets. Each bucket stores one centroid and a table of the key positions it contains, and once a block is clustered its buckets never change. In the tree variant the same process is repeated on the buckets to form higher levels.
The space is learned: in D-LSA the clustering runs on index projections trained by distillation, and in N-LSA it runs on the attention's own keys. That is what "latent" refers to. The bucket cache holds one centroid per group of keys, so the paper describes it as a small fraction of the KV cache (about 24.5 bytes per token in its setup, with the share depending on model and parallelism); the memory cost of the KV cache is the budget this has to fit inside.
| Search style | What a query does | Work per query |
|---|---|---|
| Flat search | Score every group (centroid or block) directly | O(T) |
| Fixed-level search | Score coarse groups, then refine inside the winners, with a fixed number of levels | O(T) |
| Tree search (LSA Tree) | Descend a deeper hierarchy, expanding only the groups kept at each level | O(log T) |
What one query actually does
The query is normalized, then scored against centroids. In the flat version it scores every bucket centroid from earlier cluster blocks and takes the top buckets. In the tree version it uses beam search: at each level it expands only the best nodes it kept, so the number of scores grows with the depth of the tree rather than with the context length. The chosen buckets are expanded into key positions, best first, until k long-range keys are collected.
Two things are always added. The first few tokens (the attention sink) are kept, and a recent window, set to one cluster block, covers the newest keys that have not been clustered yet. One index list is built per query and shared by all of its attention heads, so the indexer runs once, not once per head. Then ordinary attention runs over sink, selected keys and window.
A worked example (illustrative)
Hold three things fixed: a context of 10,000,000 keys, a tree where each node has 64 children, and a beam that keeps 8 nodes per level. A flat indexer that scored every key would do 10,000,000 scores per query. A tree with 64 children per node needs about 4 levels to cover 10M keys (644 is about 16.8M). At each level the beam of 8 nodes expands to 8 × 64 = 512 children to score, so the descent costs about 4 × 512 = 2,048 scores per query, roughly 4,900× fewer.
The paper's measured speedups are far smaller than that ratio, 22.7× in prefill and 4.6× in decode against an already-sparse baseline. That gap is plausible: its baseline does not score all 10M keys either, and a layer also spends time on attention over the selected keys and other work. The point of the example is the shape of the curve: flat indexing grows linearly with context, tree indexing grows with its depth. The numbers 64, 8 and 4 levels are chosen for illustration and are not the paper's settings.
Two ways to get it, and what is not yet shown
D-LSA retrofits an existing pretrained model: the indexer projections are trained by distillation so the model's own attention need not change. N-LSA trains the hierarchy from scratch with only the next-token loss, and the authors report it matches full-attention accuracy with a 1.6× per-layer training speedup at 128K tokens. Both build their index lists with the same selection process.
Treat the headline numbers as per-layer measurements on the two models in the paper at 10M tokens, not as end-to-end serving speedups. The source does not report system-level throughput, and how the approach behaves on other model families is not documented in the material we reviewed.
Goes deeper in: LLM Internals → Attention → Computing Attention Scores
Related explainers
- LatentIndex: shared latent indexer cache — also attacks indexer cost, but by sharing one cache across layers instead of reorganizing the search.
- HY4 IndexCache: cross-layer index reuse — reuses a layer's chosen indices in neighboring layers.