A new technique just made attention 23x faster!
At 10M tokens, sparse attention slows down not because of attention itself but rather because of deciding which keys to attend to.
Let's understand why and how a new technique solves it without scanning every key.
1) Full attention at long context:
In full attention, every query is compared against every earlier key. This leads to O(T^2) complexity for prefill, and at 10M tokens it dominates the forward pass.
2) Sparse attention:
Sparse attention lets each query read only a small set of keys instead of all of them, so the attention becomes cheap.
But something still has to pick those keys, and at long context, this step becomes the bottleneck.
3) Why picking keys is still quadratic:
DeepSeek's DSA uses a lightning indexer that scores every earlier key. GLM-5.3-Flash pools 4 keys into 1 before scoring. NSA, MoBA, and Quest score blocks of nearby keys.
Each of them scans the whole context for every query, so the indexer stays O(T^2), and at 10M tokens, it takes 98% of the layer's time.
Block methods have another issue. Blocks group keys by position, so one relevant key within filler can get averaged away in the block summary.
4) How LSA picks keys:
Latent Sparse Attention (LSA) is a new approach that groups keys by meaning instead of position.
- Each key is projected into a 64-dim index space, and every 4 consecutive keys are pooled into one.
- When a 512-key block fills up, it's clustered into buckets of ~8 similar keys, with one centroid per bucket. Finished blocks are never rebuilt.
- A query scores only the centroids, keeps the top 1,024 buckets, and expands them into 4,096 keys, plus 4 sink tokens and the 512 most recent keys.
- Exact FlashAttention then runs over that list with an unchanged kernel.
If you've built RAG, this is like cluster-based vector search running inside attention. The kernel design even cites FAISS.
At 10M tokens, LSA's prefill is 72.4x faster than full attention on Qwen-3.8-27B and 22.7x faster than GLM-5.3-Flash's own sparse attention.
The time to first token improves:
- 9.2x on Qwen
- 2.2x on GLM
Below ~512k tokens, it's roughly break-even.
Here's the paper:
That said, LSA attempts to find the keys more cheaply, not storing them. The KV cache still grows linearly with context, and at 10M tokens, managing that memory becomes the next engineering problem.
I wrote an article on how 12 ways serving systems handle it, covering paging, offloading, quantizing, and more.
Read it below.
Show more