Sparse attention estimation reduces keys needed with fewer searches
Attention via Black-Box Vector Search
Data Structures and AlgorithmsMachine Learning
Summary
When computers read long texts using attention, it’s slow to consider every word. The authors studied how to find just a small, important set of words quickly using a black-box search tool called MIPS. They showed mathematically how many words need to be checked to get a good approximation, and invented better methods that use fewer searches. Their approach helps speed up attention calculations for large language models when reading long passages.
What this means in practice
- •For machine learning engineers: Implement faster attention layers in large language model inference to handle longer contexts more efficiently.
- •For search infrastructure teams: Optimize retrieval systems where fast estimation of highest scoring items among many is required using fewer queries.
Authors
Stepan Zharkov, Krish Singal, Ashwin Padaki, Alexandr Andoni
Abstract
Sparse attention mechanisms estimate attention over $n$ tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heaviest keys, which motivates the following question: given black-box access to a MIPS oracle, how many keys must be retrieved to output an $\varepsilon$-accurate attention estimate? We answer this question by unifying prior approaches through the framework of priority sampling. With a single MIPS index, we show that $Θ(\sqrt{n}/\varepsilon)$ retrieved keys are both sufficient and necessary. With $Θ(\log n)$ indices, we give an algorithm that retrieves only $O(\log n+1/\varepsilon^2)$ keys and prove that this is near-optimal. More generally, we design algorithms that establish a smooth tradeoff between the number of MIPS indices and number of retrieved keys. We then show that if we allow augmentation of keys and queries, we can bypass the above lower bounds: there exists a simple priority-sampling estimator using a single MIPS index and $O(1/\varepsilon^2)$ retrieved keys. When integrated into LLM inference, our algorithms outperform top-$k$ and sampling approaches used in prior work and yield attention approximation that scales favorably to long contexts.