mlsanityData to 14 Oct 2026

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

arXiv 2310.19126 ↗First posted 29 Oct 2023cs.DS cs.CG cs.LGcited by 20

Not on the map. Why?

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.

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

13 of 32 references.

References · 13

  1. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
  2. 2016A Survey on Learning to Hashcited by 119
  3. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 104
  4. 2021A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Searchcited by 82
  5. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 47
  6. 2016Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)cited by 44
  7. 2015Learning to Hash for Indexing Big Data - A Surveycited by 39
  8. 2021SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Searchcited by 35
  9. 2018Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Datacited by 20
  10. 2019Graph-based Nearest Neighbor Search: From Practice to Theorycited by 19
  11. 2016EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graphcited by 15
  12. 2021A new near-linear time algorithm for k-nearest neighbor search using a compressed cover treecited by 8
1 more
  1. 2017Graph-based time-space trade-offs for approximate near neighborscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 7; 2026: 7.

20 papers.

Sort:

By area:

  1. 2024Approximate Nearest Neighbor Search with Window Filterscited by 11
  2. 2024Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limitscited by 7
  3. 2025Beyond Sequential Reranking: Reranker-Guided Search Improves Reasoning Intensive Retrievalcited by 5
  4. 2023PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Searchcited by 3
  5. 2024Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Searchcited by 3
  6. 2024A Bi-metric Framework for Fast Similarity Searchcited by 3
  7. 2025Cloud-Native Vector Search: A Comprehensive Performance Analysiscited by 3
  8. 2024Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Searchcited by 1
  9. 2025Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Searchcited by 0
  10. 2025MINT: Multi-Vector Search Index Tuningcited by 0
  11. 2025Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Searchcited by 0
  12. 2025The kernel of graph indices for vector searchcited by 0
8 more
  1. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0
  2. 2026MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Searchcited by 0
  3. 2026EGA: Adapting Frozen Encoders for Vector Search with Bounded Out-of-Distribution Degradationcited by 0
  4. 2026Learning Partition Trees for Nearest Neighbor Searchcited by 0
  5. 2026MegaMem: A Retrieval Solution for Ultra-Large Context Windowscited by 0
  6. 2026MEMONDEMAND: A Memory Management System for Large-Scale Enterprise Datacited by 0
  7. 2026A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Searchcited by 0
  8. 2026Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruningcited by 0