ANN Search: New metric 1/Ratio@k beats Recall@k for efficiency and quality

Approximate nearest neighbor (ANN) search is central to modern ML — from classification to retrieval-augmented generation (RAG). For decades, the field has been optimized around Recall@k, the fraction of true exact neighbors retrieved. But a new paper from Dimitris Dimitropoulos and Nikos Mamoulis (University of Ioannina and Aalborg University, arXiv:2606.04522) argues that Recall@k is a misleading proxy for actual search quality. By focusing on overlap with the exact kNN set, it forces ANN algorithms to waste compute on returning exact neighbors that don’t actually improve downstream outcomes.

The authors propose replacing Recall@k with 1/Ratio@k, the inverse approximation ratio — a metric that measures the ratio of distances between retrieved and true neighbors. It’s hyperparameter‑free and requires only standard benchmark inputs. Across datasets with varying intrinsic dimensionality, optimizing for 1/Ratio@k achieves operational quality thresholds at substantially lower computational cost than Recall@k. In downstream tasks — label precision, semantic similarity, BERTScore, and LLM‑graded quality — performance remains stable even when Recall@k drops significantly, while 1/Ratio@k closely tracks true utility. The work suggests the ANN community should retire Recall@k in favor of a more deployable, cost‑effective metric that reflects what really matters: the quality of retrieved results, not their overlap with a theoretical ideal.