At ultra-long context, sparse attention reduces the number of keys a query attends to, but the indexer that chooses those keys still scores every preceding key or block, so prefill remains quadratic in context length.
Clustering keys makes 10-million-token attention 22x faster with similar accuracy
A learned hierarchy of key clusters lets queries skip the scan over every key, speeding up prefill and decode in both pretrained and natively trained language models at extreme context lengths.
Independent
Ales Kubicek · Andrea Caciolai · Liangzu Peng · Sukrit Sumant · Benjamin Hoover · Fraser Greenlee · +4 more
Research Digest··3 min read
Before you read this
Three ideas this paper builds onsparse attentionSelectively attending to only the most relevant positions or tokens to reduce computational overhead.36 papers →kv cache compressionReducing the size of the key-value cache in transformers via selective retention, low-rank updates, or adaptive compression.52 papers →self-supervised learningA paradigm where models learn representations from unlabeled data by predicting hidden or transformed parts of the input.49 papers →
Ales Kubicek and colleagues introduce Latent Sparse Attention (LSA), which clusters keys in a learned latent space so each query searches cluster centroids rather than every key.
How it works
before and afterThe Daily Edition
The front page in your inbox each weekday morning: the lead, the picks, and why each one earned its place.