University of Ioannina Says ANN Search Wastes 9x Compute on the Wrong Metric
A new paper argues Recall@k is the wrong metric for ANN search, wasting compute and misrepresenting real-world quality — and proposes a better drop-in replacement.
Takeaways
- Core claim: Recall@k, the standard ANN search metric for over a decade, systematically overstates the cost of approximation and is misaligned with real downstream quality.
- Proposed replacement: 1/Ratio@k (inverse approximation ratio) measures distance quality rather than ID overlap — no LLM judge, no hyperparameters, computable from standard benchmark inputs.
- Compute savings: Optimizing for 1/Ratio@k instead of Recall@k requires 1.86x–9.36x fewer distance computations and delivers up to 9.98x higher QPS at equivalent quality thresholds.
- Downstream tasks unaffected: Label Precision in image classification and LLM answer quality in RAG stay above 94% even when Recall drops to 0.4 — a 60% fall that Recall treats as catastrophic.
- Prediction accuracy: 1/Ratio@k predicts downstream quality with under 3% error (MAD); Recall@k has 25–30% error — an 11x to 57x improvement in proxy accuracy.
- Algorithm rankings preserved: Switching from Recall to 1/Ratio does not reorder which ANN algorithms are fastest or cheapest — existing benchmark conclusions remain valid, just reproducible at lower cost.
Every vector database, every RAG pipeline, every embedding-based classifier running in production today depends on Approximate Nearest Neighbor (ANN) search. And for over a decade, the field has evaluated and tuned ANN algorithms almost exclusively on one metric: Recall@k , the fraction of the true k nearest neighbors that the algorithm actually retrieves. A new paper from the University of Ioannina makes a pointed argument: that metric is wrong, and chasing it is costing you real compute.
The metric everyone uses , and why it misleads
Recall@k is a set-overlap measure. It counts how many of the returned vector IDs match the IDs of the exact k nearest neighbors. If your algorithm returns 9 of the true 10 neighbors, Recall@10 = 0.9. Simple. But here is the problem: it treats a near-miss as a total failure, regardless of how close that near-miss actually is.
Imagine searching a 1,000-dimensional embedding space. The 10th and 11th nearest neighbors are almost equidistant from your query , separated by a tiny fraction of the total distance. If your ANN algorithm returns the 11th neighbor instead of the 10th, Recall@k penalizes that as a full miss. But geometrically, the two results are essentially identical in quality. As intrinsic dimensionality grows or k becomes large, distances to successive neighbors concentrate and many near-equidistant candidates appear. An ANN algorithm can return points geometrically as close as the true neighbors but carrying different identifiers, causing Recall@k to degrade while the actual retrieval quality stays high.

This is not a niche edge case. Modern AI and ML applications form embeddings of hundreds to thousands of dimensions, making this divergence increasingly common. ANN methods may unnecessarily be tuned to achieve high recall levels, while ANN results of low recall may be of high quality. The entire research community , including the benchmarks that rank algorithms and the production systems that are tuned against them , has been optimizing for a metric that overstates the cost of approximation.
A better yardstick: 1/Ratio@k
The paper proposes replacing Recall@k with 1/Ratio@k, the inverse approximation ratio. Rather than asking "did you return the exact right IDs?", it asks "how far are your returned vectors from the true nearest neighbors, in distance terms?"
Formally, for each position i, you compute the ratio of the distance to the i-th returned neighbor over the distance to the i-th true neighbor, then average across all k positions and take the inverse. A value of 1.0 means perfect retrieval; lower values quantify how much further out the returned set lies. Both metrics live in [0, 1] with 1 being perfect, but they measure fundamentally different things: