# Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD](https://mlsanity.com/paper/1812.09162/) (2018)
- [Spectrum Estimation from Samples](https://mlsanity.com/paper/1602.00061/) (2016)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Bridging Dense and Sparse Maximum Inner Product Search](https://mlsanity.com/paper/2309.09013/) (2023)
- [Learning to Index for Nearest Neighbor Search](https://mlsanity.com/paper/1807.02962/) (2018)
- [A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.11731/) (2024)
- [A Learned Index for Exact Similarity Search in Metric Spaces](https://mlsanity.com/paper/2204.10028/) (2022)
- [Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search](https://mlsanity.com/paper/2403.01797/) (2024)

## Built on by (most cited first, 3 of 3)

- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025)
- [Neighborhood Stability as a Measure of Nearest Neighbor Searchability](https://mlsanity.com/paper/2602.16673/) (2026)

## Abstract (arXiv)

Clustering-based nearest neighbor search is an effective method in which points are partitioned into geometric shards to form an index, with only a few shards searched during query processing to find a set of top-k vectors. Even though the search efficacy is heavily influenced by the algorithm that identifies the shards to probe, it has received little attention in the literature. This work bridges that gap by studying routing in clustering-based maximum inner product search. We unpack existing routers and notice the surprising contribution of optimism. We then take a page from the sequential decision making literature and formalize that insight following the principle of ``optimism in the face of uncertainty.'' In particular, we present a framework that incorporates the moments of the distribution of inner products within each shard to estimate the maximum inner product. We then present an instance of our algorithm that uses only the first two moments to reach the same accuracy as state-of-the-art routers such as ScaNN by probing up to 50% fewer points on benchmark datasets. Our algorithm is also space-efficient: we design a sketch of the second moment whose size is independent of the number of points and requires O(1) vectors per shard.