# Automating Nearest Neighbor Search Configuration with Constrained Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 4 Jan 2023.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Thinking Fast and Slow: Efficient Text-to-Visual Retrieval with Transformers](https://mlsanity.com/paper/2103.16553/) (2021)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Now Playing: Continuous low-power music recognition](https://mlsanity.com/paper/1711.10958/) (2017)
- [A Bandit Approach to Maximum Inner Product Search](https://mlsanity.com/paper/1812.06360/) (2018)
- [Song Recommendation with Non-Negative Matrix Factorization and Graph Total Variation](https://mlsanity.com/paper/1601.01892/) (2016)

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

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [RAGO: Systematic Performance Optimization for Retrieval-Augmented Generation Serving](https://mlsanity.com/paper/2503.14649/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)
- [Semantic Recall for Vector Search](https://mlsanity.com/paper/2604.20417/) (2026)

## Abstract (arXiv)

The approximate nearest neighbor (ANN) search problem is fundamental to efficiently serving many real-world machine learning applications. A number of techniques have been developed for ANN search that are efficient, accurate, and scalable. However, such techniques typically have a number of parameters that affect the speed-recall tradeoff, and exhibit poor performance when such parameters aren't properly set. Tuning these parameters has traditionally been a manual process, demanding in-depth knowledge of the underlying search algorithm. This is becoming an increasingly unrealistic demand as ANN search grows in popularity. To tackle this obstacle to ANN adoption, this work proposes a constrained optimization-based approach to tuning quantization-based ANN algorithms. Our technique takes just a desired search cost or recall as input, and then generates tunings that, empirically, are very close to the speed-recall Pareto frontier and give leading performance on standard benchmarks.