# ANN Search: Recall What Matters

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 22 of its 57 references that are in the map.
- First posted on arXiv 3 Jun 2026.

## Placed in

- Retrieval-augmented generation / [Vector search and ANN indexes](https://mlsanity.com/rag/vector-search-and-ann-indexes/)

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

- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [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)
- [PubMedQA: A Dataset for Biomedical Research Question Answering](https://mlsanity.com/paper/1909.06146/) (2019)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [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)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [K-nearest Neighbor Search by Random Projection Forests](https://mlsanity.com/paper/1812.11689/) (2018)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2411.12229/) (2024)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [How Does Knowledge Selection Help Retrieval Augmented Generation?](https://mlsanity.com/paper/2410.13258/) (2024)
- [Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study](https://mlsanity.com/paper/2508.16263/) (2025)
- [The Role of Local Intrinsic Dimensionality in Benchmarking Nearest Neighbor Search](https://mlsanity.com/paper/1907.07387/) (2019)
- [Towards Robustness: A Critique of Current Vector Database Assessments](https://mlsanity.com/paper/2507.00379/) (2025)
- [WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2508.18617/) (2025)
- [DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries](https://mlsanity.com/paper/2510.25401/) (2025)

## Abstract (arXiv)

Approximate nearest neighbor (ANN) search has become a core primitive in information retrieval and modern machine learning tasks, from classification to retrieval-augmented generation. The community evaluates and tunes ANN algorithms primarily on their throughput at a given Recall@k, the fraction of true exact neighbors retrieved. We argue that what really matters in ANN search is the quality of the retrieved results and not their overlap with the true kNN set. We show that using Recall@k to assess retrieval quality forces unnecessary computational overhead and investigate replacing it by 1/Ratio@k, the inverse approximation ratio. 1/Ratio@k evaluates the differences between the distances of the retrieved and true neighbors. It is judge-free, hyperparameter-free, and computable from standard ANN benchmark inputs alone. We benchmark state-of-the-art ANN algorithms across diverse datasets spanning a wide range of intrinsic dimensionalities, evaluating the two metrics comprehensively across efficiency, downstream classification, and retrieval-augmented generation. On the efficiency axis, optimizing for 1/Ratio@k reaches operational quality thresholds at a substantially lower computational cost than Recall@k. In downstream tasks, performance indicators (label precision, semantic similarity, BERTScore, and LLM-graded quality) remain highly stable even when Recall@k drops significantly. The inverse approximation ratio, on the other hand, closely mirrors this stability, tracking true utility much better than Recall@k. Ultimately, while Recall@k overstates the true cost of approximation, 1/Ratio@k offers a more accurate, deployable proxy for actual ANN quality.