# Attention via Black-Box Vector Search

arXiv: https://arxiv.org/abs/2610.10135 · HTML: https://mlsanity.com/paper/2610.10135/

## Key facts

- No citing papers in the map yet (data through 7 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 7 Oct 2026.

## Builds on (most cited first, 10 of 10)

- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Post-Training Sparse Attention with Double Sparsity](https://mlsanity.com/paper/2408.07092/) (2024)
- [Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs](https://mlsanity.com/paper/2502.12216/) (2025)
- [A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models](https://mlsanity.com/paper/1703.05160/) (2017)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [Nearly Optimal Attention Coresets](https://mlsanity.com/paper/2605.05602/) (2026)
- [Sum Estimation via Vector Similarity Search](https://mlsanity.com/paper/2601.11765/) (2026)

## Abstract (arXiv)

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 Theta(√n/varepsilon) retrieved keys are both sufficient and necessary. With Theta(log n) indices, we give an algorithm that retrieves only O(log n+1/varepsilon2) 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/varepsilon2) 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.