# Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 29 Oct 2023.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [Learning to Hash for Indexing Big Data - A Survey](https://mlsanity.com/paper/1509.05472/) (2015)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree](https://mlsanity.com/paper/2111.15478/) (2021)
- [Graph-based time-space trade-offs for approximate near neighbors](https://mlsanity.com/paper/1712.03158/) (2017)

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

- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits](https://mlsanity.com/paper/2405.18680/) (2024)
- [Beyond Sequential Reranking: Reranker-Guided Search Improves Reasoning Intensive Retrieval](https://mlsanity.com/paper/2509.07163/) (2025)
- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [A Bi-metric Framework for Fast Similarity Search](https://mlsanity.com/paper/2406.02891/) (2024)
- [Cloud-Native Vector Search: A Comprehensive Performance Analysis](https://mlsanity.com/paper/2511.14748/) (2025)
- [Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.04713/) (2024)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [MINT: Multi-Vector Search Index Tuning](https://mlsanity.com/paper/2504.20018/) (2025)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [The kernel of graph indices for vector search](https://mlsanity.com/paper/2506.20584/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search](https://mlsanity.com/paper/2601.01930/) (2026)
- [EGA: Adapting Frozen Encoders for Vector Search with Bounded Out-of-Distribution Degradation](https://mlsanity.com/paper/2605.05674/) (2026)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)
- [MegaMem: A Retrieval Solution for Ultra-Large Context Windows](https://mlsanity.com/paper/2608.22137/) (2026)
- [MEMONDEMAND: A Memory Management System for Large-Scale Enterprise Data](https://mlsanity.com/paper/2608.22141/) (2026)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)
- [Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning](https://mlsanity.com/paper/2609.36359/) (2026)

## Abstract (arXiv)

Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing" version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic" dimension. For the other data structure variants studied, including DiskANN with "fast preprocessing", HNSW and NSG, we present a family of instances on which the empirical query time required to achieve a "reasonable" accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least 0.1 n steps on instances of size n before it encounters any of the 5 nearest neighbors of the query.