ANN Search: Recall What Matters Dimitris Dimitropoulos
University of Ioannina & Archimedes, Athena RC Ioannina, Greece [email protected]
arXiv:2606.04522v1 [cs.IR] 3 Jun 2026
Abstract 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.
1
Introduction
Approximate Nearest Neighbor (ANN) search is a foundational operation in modern data management, finding application in information retrieval, recommender systems, and retrieval-augmented generation. Because exact nearest neighbor search is computationally prohibitive at scale, production systems trade accuracy for efficiency. The central empirical question in ANN research is therefore: how much ANN query throughput in Queries-Per-Second (QPS) can we achieve at a given accuracy level? The community answers this question largely under a specific definition of accuracy; Recall@𝑘, defined as the fraction of the exact 𝑘NN set retrieved by A𝑘NN search, has become the standard measure of retrieval quality in ANN evaluation. Algorithms are typically compared via the QPS-vs-Recall curve, which plots throughput against retrieval quality across configurations. Established ANN benchmarks [3, 25, 37] rank algorithms by their throughput at fixed Recall thresholds, and state-of-the-art ANN algorithms [14, 18– 20, 22, 23, 32, 42, 45, 52, 55] are designed and tuned to optimize the QPS-vs-Recall@𝑘 trade-off. The QPS-vs-Recall@𝑘 curve has shaped more than a decade of ANN research.
Nikos Mamoulis
University of Ioannina & Archimedes, Athena RC Ioannina, Greece [email protected] In this paper, we question the appropriateness of Recall as a target accuracy measure. We argue that the QPS-vs-Recall convention is misaligned with what ANN algorithms actually deliver, and that the community tunes ANN methods to optimize for a metric that overstates the difficulty of the task. We investigate whether 1/Ratio@𝑘, the inverse of the approximation ratio between the distances of an algorithm’s retrieved results and the true 𝑘NNs, is a more effective quality measure than Recall@𝑘. 1/Ratio@𝑘 generalizes the approximation ratio definition of Indyk and Motwani [24] by averaging the per-position distance ratios across all 𝑘 positions. Both Recall@𝑘 and 1/Ratio@𝑘 take values between 0 and 1 with 1 indicating perfect retrieval, but they measure different things. Recall counts identifier matches, while 1/Ratio measures the quality of the retrieved results compared to the true 𝑘 NNs. When intrinsic dimensionality is low, successive neighbors are well-separated in distance, especially for small 𝑘 values, so Recall@𝑘 and 1/Ratio@𝑘 are naturally aligned. As intrinsic dimensionality grows or 𝑘 becomes large, however, distances to successive neighbors concentrate [7] and many near-equidistant candidates appear [4]. As a result, an ANN algorithm can return points geometrically as close as the true neighbors but carrying different identifiers, causing Recall@𝑘 to degrade while 1/Ratio@𝑘 remains high. Figure 1 exemplifies the exact and approximate 𝑘NN results for a RAG downstream task. Although Recall is low, retrieval quality is high. This divergence is apparent in modern AI and ML applications, where object embeddings are formed by hundreds to thousands of dimensions. Based on this, we conjecture that ANN methods may unnecessarily be tuned to achieve high recall levels, while ANN results of low recall may be of high quality, as reflected by 1/Ratio@𝑘. Query q: “Who is the greatest football player in history?” exact kNN bounds “Messi is the best footballer in history”
AkNN bounds
q
Approved by Recall Penalized by Recall Missed by ANN search
“Messi is the GOAT”
Figure 1: Approximate and exact 𝑘NN results in a RAG downstream task. The embeddings missed by the ANN algorithm are not necessarily of much higher quality compared to the retrieved ones not in the exact 𝑘NN set. Recall@𝑘 gives unreasonably high penalty to retrieval quality. Other alternatives to Recall@𝑘. Several recent works have questioned the effectiveness of Recall@𝑘 as a metric for ANN evaluation [10, 33, 53]. Kuffo et al. [33] introduce Semantic Recall and Tolerant Recall, both of which down-weight retrieval misses involving semantically irrelevant ground-truth neighbors. Semantic Recall
Dimitris Dimitropoulos and Nikos Mamoulis
requires an external LLM judge and access to the underlying raw documents; Tolerant Recall requires tuning a tolerance hyperparameter. Iceberg [10] is a framework that re-ranks ANN algorithms by application-specific metrics such as Hit@K for classification and retrieval tasks. These efforts share our claim that Recall@𝑘 is misaligned with downstream utility, but their proposed solutions either have external dependencies or require hyperparameter tuning, which limits their deployability. On the other hand, 1/Ratio@𝑘 requires only the embeddings indexed by the ANN algorithm; hence, 1/Ratio@𝑘 is judge-free, hyperparameter-free, and computable from the data that standard ANN benchmarks already provide. Striving for high Recall@𝑘 is expensive. To evaluate the appropriateness of 1/Ratio@𝑘 as opposed to Recall@𝑘, across six datasets, we benchmark five state-of-the-art ANN algorithms: Annoy [46], a tree-based index; SuCo [55], a collision-based framework; HNSW [42], the industry-standard graph-based index; RaBitQ [20], a quantization-based method; and SymphonyQG [22], a hybrid graph-andquantization approach. We measure how much work each metric demands before reaching a target quality level (e.g., accuracy ≥ 0.95). We consider four cost factors: query time, distance computations per query, index build time, and memory footprint of the index. We find that for 1/Ratio@𝑘, it is substantially easier to reach operational thresholds compared to Recall@𝑘 across all algorithms and datasets, with the gap growing with 𝑘. Recall@𝑘 and 1/Ratio@𝑘 also disagree on which configurations meet the required quality standards, as Recall@𝑘 largely underestimates quality. Achieving high Recall@𝑘 is not crucial for downstream tasks. This disagreement matters in practice: configurations of ANN algorithms characterized as “inadequate” by not meeting high-Recall standards, actually deliver similar results as high-recall configurations, as Figure 1 exemplifies. We verify this across two downstream task families. In the first task, an image classification experiment on four benchmark datasets, Label Precision@100 barely changes as Recall drops to 0.4, while 1/Ratio@100 tracks it much more closely than Recall does. Second, we apply a retrieval-augmented generation experiment on five benchmarks, measuring LLM answer quality by BERTScore F1, semantic similarity, and an LLM graded score. Across all settings, the actual quality difference between high-recall and moderate-to-low recall retrieval is negligible, while 1/Ratio is shown to be a much better quality proxy. Summary of contributions • We analyze the drawbacks of Recall@𝑘 as a quality measure for ANN search and investigate the effectiveness of 1/Ratio@𝑘 as an appropriate replacement. Unlike recently proposed alternatives to Recall@k [10, 33, 53], 1/Ratio@𝑘 is simultaneously judge-free, hyperparameter-free, and computable from the embeddings and ground-truth identifiers that standard ANN benchmarks already provide (see Table 1 for a comparison). • We benchmark five ANN algorithms across 6 datasets, comparing the required cost to reach a quality target level under Recall@𝑘 and 1/Ratio@𝑘, in terms of query time, distance computations, build time, and memory. Across all algorithms, reaching a Recall@𝑘 target is substantially more expensive than reaching the same 1/Ratio@𝑘 target, and the gap widens with 𝑘 (except for memory which is mainly unaffected).
• We show that Recall loss does not essentially degrade image classification quality. Under synthetic recall control on MNIST, Fashion-MNIST, CIFAR-10, and SVHN, Label Precision@100 is stable across Recall@100 ∈ [0.4, 1.0]. On the other hand, 1/Ratio@100 tracks Label Precision substantially more closely than Recall does, providing evidence that 1/Ratio is a better predictor of downstream task quality. • Similarly, we show that Recall loss does not degrade retrievalaugmented generation quality. On three QA datasets evaluated against human-annotated ground truth and two BEIR datasets evaluated against an LLM perfect-recall baseline, answer quality measured by BERTScore F1, semantic similarity, and LLM graded score is preserved across the same recall range. 1/Ratio tracks this stability closely, confirming that it is a more accurate estimator of true downstream quality than Recall.
2 2.1
Related Work ANN Algorithms
ANN search has been studied for decades, and the methods that dominate fall into five broad families. Tree-based methods partition the vector space recursively along axis-aligned or random hyperplanes and route a query down the resulting hierarchy. Early instances such as KD-trees [6] were designed for exact nearest neighbor search; approximate variants emerged by relaxing exactness and limiting the number of partitions visited during traversal [2]. Annoy [46] builds forests of independently randomized trees and merges their candidate sets. Tree-based methods underperform in embedding spaces, where dimensionality is high, as their partitions become ineffective: the volume of each leaf cell concentrates near its boundary, and search ends up traversing a large fraction of the tree [11, 54]. Hash-based methods map vectors to short binary codes so that nearby points collide under the same hash bucket with high probability. Locality-Sensitive Hashing (LSH) [24] provides sublinear query time with provable approximation guarantees by hashing to multiple independently constructed tables. LSH is applied in Euclidean spaces via p-stable distributions [12] and indexing with data-adaptive encoding schemes [56]. Learning-to-hash methods train hash functions tailored to the input dataset [49]. Recently, collision-based frameworks such as SuCo [55] generalize the hashing paradigm by counting subspace collisions as a proxy for Euclidean distance, while retaining theoretical guarantees on result quality. Recent benchmarks [3, 25, 38] show that hash-based and collision-based methods are outperformed in throughput by graphbased and quantization-based indices. Quantization-based methods compress each vector into a short code and estimate distances directly on the codes. Product quantization (PQ) [27] splits a vector into sub-vectors and quantizes each sub-vector against a learned codebook; OPQ [21] adds a rotation that aligns the data with the PQ partition; ScaNN [23] learns a quantizer that minimizes the inner-product estimation error. Invertedfile (IVF) structures are typically layered on top to first restrict the search to a small number of clusters and then estimate distances on the codes inside those clusters. RaBitQ [20], a randomized 1-bit
ANN Search: Recall What Matters
quantizer with a theoretical error bound, is the current state-ofthe-art in this family. Quantization-based methods depend on how well the learned codebooks or cluster partitions capture the data distribution: when the data is poorly fit by the quantizer, distance estimation errors can be high. Graph-based methods precompute a navigable proximity graph over the dataset and answer queries by greedy traversal: starting from an entry point, the search moves to the neighbor closest to the query and repeats until no closer neighbor is found. Variants differ in how the graph is constructed. NSW [41] grows the graph incrementally with small-world properties; NSG [17] sparsifies it for fewer hops; SSG [16] refines NSG with a satellite-system construction for improved robustness; and Vamana/DiskANN [26] adapts the construction to disk-resident indices. Graph-based methods currently dominate ANN benchmarks and production systems [50, 51]; HNSW [42], the hierarchical variant of NSW, is the most established index in this family and is the default vector index in PostgreSQL, Pinecone, Milvus [48], and Elasticsearch [50]. While being very efficient, graph-based methods are limited by their large memory footprint [40, 61] and high construction cost [50, 51]. Hybrid Methods combine techniques from different families; e.g., a graph for navigation and quantized codes for distance computations. NGT-QG [58] and SymphonyQG [22] are representative of this hybrid line, inheriting the routing efficiency of graph traversal and the throughput of quantized distance estimation.
2.2
Benchmarking conventions
The research community evaluates ANN indexes almost exclusively along Recall@k versus queries-per-second (QPS) curves. This convention was established by early ANN benchmarks [3] and remains the reference framework for the field. The recently released VIBE benchmark [25], which tests out-of-distribution workloads on very high dimensional embeddings, still uses Recall as the primary quality metric. DARTH [8] turns Recall into a service-level objective via adaptive early termination at user-declared Recall targets. In general, optimizing for Recall is the main objective of published work on ANN indexing during the past several years [9, 13, 14, 18– 20, 22, 23, 32, 42, 45, 52, 55], where headline results are reported by Recall-QPS curves and ANN indices tune build and search hyperparameters to hit pre-specified Recall thresholds. Recall@k is therefore not merely one evaluation choice among many: it is the optimization target that has shaped both the design of ANN search methods and modern retrieval systems.
2.3
Criticism on Recall
Few recent studies question whether Recall@k measures what practitioners actually need. Kuffo et al. [33] argue that traditional Recall penalizes algorithms for missing ground-truth neighbors that are actually not semantically relevant to the query. They propose two replacements: Semantic Recall, the fraction of semantically relevant ground-truth neighbors an algorithm retrieves, where relevance is determined by human judges or by LLMs and Tolerant Recall, which counts a retrieved item as a match whenever its distance to the query is close enough to the true neighbor’s distance, with closeness set by a tunable tolerance. Neither replacement is simultaneously judge-free and hyperparameter-free. Semantic
Table 1: Proposed alternatives to Recall@𝑘 Metric
Judge-free Hyperparameter-free Benchmark-inputs-only
Semantic Recall [33] Tolerant Recall [33] Iceberg task metrics [10] Robustness-𝛿 @K [53] 1/Ratio@𝑘 (our proposal)
× ✓ ✓ ✓ ✓
✓ × ✓ × ✓
× ✓ × ✓ ✓
Recall requires ground truth which standard ANN benchmarks do not provide. Tolerant Recall is conceptually similar to 1/Ratio@k, but requires tuning a tolerance hyperparameter per dataset. Iceberg [10] evaluates SOTA vector-similarity-search methods in downstream tasks, scoring them by application-level metrics such as label recall, hit rate, and matching score. It is shown that an algorithm that wins on Recall is often not the best algorithm based on the task-level metric (e.g. label recall). However, this methodology is expensive to apply: each evaluation needs the source data the embeddings come from, a separate embedding model, and task-specific labels, none of which standard ANN benchmarks provide. Wang et al. [53] criticize Recall-based benchmarking from a different angle. Standard ANN benchmarks report a single number, the mean of Recall@k across the query set, which can hide a long tail of hard queries: two systems with the same average Recall can behave very differently across queries, one delivering consistent quality, and the other excelling on most queries while performing poorly on a minority of hard queries. They suggest counting quality, rather than averaging by proposing Robustness𝛿@K, which reports the fraction of queries whose Recall exceeds a user-chosen floor 𝛿. They validate this metric in an end-to-end RAG case study where systems with similar mean Recall produce noticeably different answer quality, and conclude that Recall ranks systems inconsistently, depending on whether one averages or counts. Like 1/Ratio, Robustness-𝛿@k is judge-free and requires only benchmark-standard inputs; however (i) it is still based on Recall, so it disregards the similarity between retrieved and exact results, and (ii) it relies on a user-chosen floor parameter 𝛿 that must be tuned per dataset, limiting its deployability. Our paper joins this line of skepticism against Recall@k, showing that it systematically overstates the cost of approximation in distance computations, query time, and index build time. We also show that the configurations Recall@𝑘 finds inadequate in fact deliver equivalent results in downstream tasks. Going one step further compared to previous work, we compare Recall@𝑘 against 1/Ratio@𝑘, which, unlike alternative measures [10, 33, 53], is a judge-free, hyperparameter-free quality measure computable from the same inputs ANN benchmarks already provide; see Table 1. We experimentally show that 1/Ratio@𝑘 (i) converges to its operational thresholds substantially faster than Recall@𝑘 and (ii) matches the quality of downstream tasks more closely than Recall@𝑘.
3 3.1
Preliminaries and Compared ANN Methods Problem definition
Let 𝑋 be a set of 𝑁 vectors in R𝐷 . Depending on the application, nearest neighbor search aims to find the most relevant vectors to a query by either minimizing a distance function 𝑑𝑖𝑠𝑡 (·, ·) or maximizing a similarity function 𝑠𝑖𝑚(·, ·). We use Euclidean distance (𝐿2 ) for the cost-accuracy and classification experiments, which
Dimitris Dimitropoulos and Nikos Mamoulis
has conventionally been used in the evaluation of state-of-the-art algorithms [20, 22, 42] and in ANN benchmarking [38, 49]. For the RAG experiments, we use cosine similarity, as the inner product of 𝐿2 -normalized vectors, matching the standard configuration for dense text retrieval [30]. Since we can set 𝑑𝑖𝑠𝑡 (𝑥, 𝑦) = 1 − 𝑠𝑖𝑚(𝑥, 𝑦), a unified definition of similarity search using 𝑑𝑖𝑠𝑡 (·, ·) is as follows. For a query 𝑞 ∈ R𝐷 and an integer 𝑘 ≥ 1, the exact 𝑘 nearest neighbors of 𝑞 form the set 𝑁𝑘 (𝑞) ⊆ 𝑋 of the 𝑘 vectors in 𝑋 closest to 𝑞 under 𝑑𝑖𝑠𝑡 (·, ·). Approximate nearest neighbor (ANN) search finds a e𝑘 (𝑞) ⊆ 𝑋 of size 𝑘 that approximates 𝑁𝑘 (𝑞). set 𝑁
3.2
Accuracy Measures for ANN Search
We evaluate ANN algorithms with two quality metrics between 0 and 1, with 1 indicating perfect retrieval w.r.t. the exact 𝑘NN set. Recall@𝑘 is the fraction of retrieved true 𝑘 neighbors: e𝑘 (𝑞) ∩ 𝑁𝑘 (𝑞)| |𝑁 . (1) Recall@𝑘 (𝑞) = 𝑘 Recall@𝑘 is a set-overlap measure: it counts identifier matches e𝑘 (𝑞) and the true 𝑘NN set 𝑁𝑘 (𝑞), and between the returned set 𝑁 ignores how close the missed candidates are to the true neighbors. 1/Ratio@k measures how close the returned neighbors are to the true 𝑘NN set. Let 𝑑𝑖 (𝑞) denote the distance from 𝑞 to the 𝑖-th true neighbor by distance and 𝑑e𝑖 (𝑞) the distance to the 𝑖-th returned neighbor by distance. Following Indyk and Motwani’s original ratio formulation [24], we first define the approximation Ratio@𝑘 as the mean of per-position distance ratios: 𝑘 1 ∑︁ 𝑑e𝑖 (𝑞) Ratio@𝑘 (𝑞) = . (2) 𝑘 𝑖=1 𝑑𝑖 (𝑞) Since the true 𝑘NNs are by definition the closest points to 𝑞, each per-position ratio 𝑑e𝑖 (𝑞)/𝑑𝑖 (𝑞) lies in [1, ∞), so Ratio@𝑘 ≥ 1, with equality at perfect retrieval. We evaluate algorithms by its inverse: 1 𝑘 (𝑞) = Í e , (3) Ratio@𝑘 𝑘 𝑑𝑖 (𝑞) 𝑖=1 𝑑𝑖 (𝑞)
which takes values in (0, 1]. A value of 1 means the returned neighbors have the same distances to the query as the true neighbors, while a value below 1 quantifies how much further out the returned set lies. Recently, ANN evaluation has moved away from distancebased definitions of approximation quality, adopting Recall@k as a quality measure [9, 13, 14, 18–20, 22, 23, 32, 42, 45, 52, 55].
3.3
Downstream Task Evaluation Metrics
Label Precision at 𝑘 (LP@𝑘), used in the classification experiments (Section 6.2), is the fraction of the 𝑘 approximate NNs returned for a query 𝑞 that share 𝑞’s class label: LP@𝑘 (𝑞) =
e𝑘 (𝑞) : ℓ𝑖 = ℓ𝑞 } {𝑖 ∈ 𝑁 , 𝑘
(4)
e𝑘 (𝑞) is the set of 𝑘 approximate neighbors returned for where 𝑁 query 𝑞 and ℓ𝑞 is its ground-truth class label. A value of 1.0 means every retrieved neighbor shares 𝑞’s label. Semantic Similarity [48] is used in the RAG experiments (Section 6.3). It is the cosine similarity between dense sentence embeddings of the generated answer and the reference answer, produced
by all-mpnet-base-v2. A score of 1.0 indicates perfect semantic agreement with the reference. BERTScore F1 [62] is used in the RAG experiments (Section 6.3). It evaluates textual similarity between a candidate and a reference by matching, via cosine similarity, their contextual token embeddings (distilbert-base-uncased). Unlike Semantic Similarity, which embeds the answer as a single vector, BERTScore operates at the token level. A score of 1.0 indicates perfect token-level alignment with the reference; lower values reflect increasing textual divergence.
3.4
Local intrinsic dimensionality
In accordance to previous studies [4] and also based on our experimental results, performance of ANN search is more closely related to the dataset’s intrinsic difficulty than to the ambient dimensionality 𝐷. Local Intrinsic Dimensionality (LID) estimates the effective dimensionality of the data; higher LID has been shown to correlate with increased query difficulty in ANN search [4, 38]. In our evaluation we compute the LID for each dataset under its own distance function, using the TwoNN estimator [15], which derives LID from the ratio of distances to the first and second nearest neighbors and is robust to the choice of neighborhood size. LID values in our benchmark range from 7.19 (PubMedQA) to 32.35 (Gist), covering a wide range of difficulty levels. Throughout the paper, we examine how the divergence between Recall@𝑘 and 1/Ratio@𝑘 relates to LID across datasets and algorithms.
3.5
ANN algorithms benchmarked
In our efficiency experiments, we benchmark five algorithms spanning the graph, quantization, hybrid, tree, and collision-based categories, serving as prominent representatives of their respective families. Our classification and RAG experiments use HNSW only, as it is the established production default [50]. Annoy [46] is a tree-based index built from a forest of random projection trees. During construction, each tree recursively partitions the space by selecting two points at random and splitting along the hyperplane equidistant between them, continuing until leaf nodes hold only a few vectors. At query time, the algorithm traverses all trees using a priority queue, preferring branches closer to the query and exploring both sides of a split when the query falls near the boundary. Candidates from the visited leaves are collected and ranked. Two parameters control the speed–accuracy trade-off: the number of trees built (num_trees) and the number of nodes inspected during search (search_k). SuCo [55] is a collision-based framework that estimates vector similarity by counting subspace collisions. The index splits the vector space into several disjoint, lower-dimensional subspaces and clusters each using an Inverted Multi-Index (IMI) [5], forming a joint codebook of centroid combinations. At query time, the query vector is projected into each subspace to identify its nearest cells. Any database vector sharing an activated cell registers a collision. Vectors that collide in enough subspaces are forwarded for re-ranking by exact Euclidean distance. The speed–accuracy tradeoff is controlled by the subspace layout, the collision threshold, and the candidate limit for re-ranking.
ANN Search: Recall What Matters
HNSW [42] is a hierarchical proximity graph. Vectors are inserted incrementally, and each vector is assigned a maximum layer level drawn from a geometric distribution. Each layer is a navigablesmall-world graph, with higher layers containing fewer points and longer-range edges. Search begins at the top layer with a single entry point and proceeds greedily: at each layer, the algorithm maintains a candidate list of size efSearch (the search beam) and descends to the next layer once a local minimum is reached. Index construction is controlled by two parameters, 𝑀 (the per-element degree budget) and efConstruction (the build-time candidate-list size). We follow the parameter naming used by the Faiss implementation [29]. RaBitQ [20] is a randomized 1-bit quantization method. Vectors are first normalized onto the unit hypersphere and then rotated via a random orthogonal transformation. Each coordinate of a rotated vector is then mapped to a single bit, giving a 𝐷-bit code per vector. From these bit codes, RaBitQ constructs an unbiased estimator of inner products and Euclidean distances with a theoretical error bound √ that scales with 1/ 𝐷, i.e., the bound tightens as the (embedded) dimensionality grows. Distance estimation is implemented with bitwise operations or SIMD-based routines for high throughput. SymphonyQG [22] integrates RaBitQ-style quantization with a navigable-graph routing structure. Each vertex stores the quantization codes of its graph neighbors in a packed layout that can be scanned sequentially with FastScan, a SIMD-based batched distance estimation routine. The standard quantize-then-rerank pipeline used in earlier graph–quantization hybrids is avoided: SymphonyQG searches directly on quantized distances and uses a refinement strategy based on multiple estimated distances to compensate for the accuracy loss this would otherwise introduce.
4
Research Questions (RQs)
To evaluate the appropriateness of Recall@𝑘 in assessing ANN search performance and the utility of our suggested 1/Ratio@𝑘 measure, we structure our study around four research questions. RQ1. Cost of optimizing for Recall@𝑘 vs. 1/Ratio@𝑘. Index construction parameters, search budget parameters, and quantization parameters are all conventionally tuned to achieve a target Recall@𝑘 threshold in ANN search, and benchmarks rank algorithms by their QPS at fixed retrieval quality levels. As Recall@𝑘 and 1/Ratio@𝑘 can diverge substantially, we first quantify the overhead incurred to satisfy Recall@𝑘 targets when distance quality (measured by 1/Ratio@𝑘) is already satisfied. RQ1. How much overhead does optimizing ANN indices for Recall@k impose, in query time, distance computations, index build time, and memory footprint, compared to optimizing for 1/Ratio@k? RQ2. Stability of algorithm rankings. As replacing Recall by a different quality metric may change the ANN algorithm that performs best under a target QPS throughput or construction cost budget, a natural question is whether the conclusions by Recallbased experimental analyses generalize. We therefore investigate whether replacing Recall with 1/Ratio reorders algorithm rankings.
RQ2. Does replacing Recall@𝑘 with 1/Ratio@𝑘 change the relative ranking of ANN algorithms under fixed budgets of query throughput, distance computations, index build time, or memory? RQ3. Geometric explanation. If there is a divergence between the achieved 1/Ratio and Recall by an index configuration, the gap should be predictable from properties of the data rather than from algorithmic artifacts. LID is the most established data property in the ANN literature, and neighborhood size 𝑘 is a natural search parameter: as 𝑘 grows, the query boundary enclosing the true nearest neighbors expands, increasing the probability that an ANN algorithm returns a geometrically close vector with a different identifier, penalizing Recall while leaving 1/Ratio largely unchanged. We therefore investigate whether the gap between Recall and 1/Ratio degradation grows with LID and with 𝑘, and whether this connection holds across algorithm families. RQ3. Is the divergence between Recall@k and 1/Ratio@𝑘 systematically related to the intrinsic dimensionality of the dataset’s embedding space and the size of the retrieved neighborhood 𝑘? RQ4. Downstream task quality at “inadequate” Recall. Recall@𝑘 labels a configuration as inadequate if it fails to return a target percentage of the 𝑘 most relevant objects. The implicit assumption is that objects missing from the exact 𝑘NN set crucially affect the performance of downstream tasks. We evaluate this assumption directly across two task families. In an image classification task, we measure whether Label Precision degrades when retrieval is performed at lower Recall levels. In a retrieval-augmented generation task, we measure whether LLM answer quality, judged by both automatic metrics and human-annotated gold answers, degrades when retrieval Recall drops. If neither task degrades materially, the configurations Recall dismisses are not inadequate in an operational sense, since the retrieved objects not in the exact 𝑘NN set can still assist the downstream task to achieve satisfactory accuracy. RQ4. Do ANN index configurations that have low Recall@k deliver significantly degraded downstream task quality compared to high-Recall configurations? Furthermore, between Recall@k and 1/Ratio@k, which metric serves as a more faithful proxy for true real-world performance of downstream tasks?
5
Experimental Setup
Our evaluation is conducted on a machine with an 11th Gen Intel® Core™ i7-11700K (3.60 GHz), 32 GB RAM, and AVX-512 support. All indexing and query code is C++ compiled with gcc 11.4 on Ubuntu 22.04 LTS using each project’s official configuration. We utilize OpenMP and native threading policies for multi-threading across all indexing and query phases. The implementations of Annoy (github.com/spotify/annoy), SuCo (github.com/WeiJiuQi/ SuCo), FAISS-HNSW (github.com/facebookresearch/faiss), and SymphonyQG (https://github.com/gouyt13/SymphonyQG) fully utilize AVX-512 instructions (either via explicit intrinsics or compiler autovectorization). In contrast, RaBitQ (https://github.com/gaoj0017/ RaBitQ) is evaluated using AVX2, as it lacks support for AVX-512. Algorithms and Parameter Sweeps. We compare Annoy [46], SuCo [55], HNSW [42] (FAISS implementation [29]), RaBitQ [20],
Dimitris Dimitropoulos and Nikos Mamoulis
and SymphonyQG [22], sweeping each method’s primary hyperparameters to meet our target quality thresholds. Annoy: number of random projection trees ∈ {10, 20, 50, 100}, search boundary limits ∈ {100, 500, 1000, 5000}. SuCo: collision ratios ∈ {0.02, 0.03, ..., 0.06}, candidate ratios ∈ {0.001, 0.002, ..., 0.006}; we test multiple subspace partition configurations, starting from a baseline tuned to roughly 16 dimensions per subspace, with the total number of subspaces scaled by variations of /3, /2, ×2, and ×3. RaBitQ: cluster sizes 𝐶 ∈ {32, 64, ..., 4096} in powers of two, 𝑁 probe in powers of two from 2 to 256 with 𝑁 probe ≤ 𝐶, and a fast k-means (2 iterations) versus standard 20-iterations based training. HNSW: 𝑀 ∈ {16, 32, 48, 64}, efConstruction ∈ {32, 64, 128}, efSearch ∈ {32, 64, 128, 256}. SymphonyQG: 𝑀 ∈ {32, 64} (aligned to the 32-bit SIMD boundary), efConstruction ∈ {32, 64, 128, 256, 512}, efSearch ∈ {32, 64, 128, 256, 512, 1024}; quantization training fixed at 3 iterations (codebase default). Cost-Accuracy Datasets and Metrics. The cost-accuracy tradeoff experiments (RQ1–RQ3) use six 𝐷-dimensional datasets of varying intrinsic dimensionalities (LID), modalities, and cardinalities (Table 2). 𝐿2 stands for Euclidean distance (the smaller the better) and IP for (normalized) inner product (the larger the better). We sweep 𝑘 ∈ {1, 20, 50, 100} and, for each configuration, record Recall@𝑘, 1/Ratio@𝑘, QPS, index build time, and distance computations per query, building one Pareto frontier per quality metric. Table 2: Dataset Characteristics and LID Dataset
Type
Card. (𝑁 )
𝐷
#Queries (𝑄)
𝑘
Metric
LID
1,000,000 260,372 1,281,167 769,382
960 3,072 640 1,024
1,000 1,000 1,000 1,000
100 100 100 100
𝐿2 𝐿2 (norm.) 𝐿2 (norm.) 𝐿2
32.35 27.45 17.85 24.09
Cost-Accuracy Experiments Gist [1] SimpleWiki [35] ImageNet [35] AGNews [35]
Image Text Image Text
Cost-Accuracy and Classification Experiments MNIST [34, 35] Fashion-MNIST [35, 57]
Image Image
60,000 60,000
784 784
10,000 10,000
100 100
𝐿2 𝐿2
12.41 13.99
50,000 73,257
3,072 3,072
10,000 10,000
100 100
𝐿2 𝐿2
27.25 18.99
292 117 200 200 200
10 10 10 10 10
IP (norm.) IP (norm.) IP (norm.) IP (norm.) IP (norm.)
13.67 10.58 22.68 7.56 7.19
Classification Experiments CIFAR-10 [31] SVHN [43]
Image Image
Retrieval-Augmented Generation (RAG) Experiments SciFact [47] NFCorpus [47] HotpotQA [60] MS-MARCO [44] PubMedQA [28]
Text Text Text Text Text
5,183 3,633 66,581 78,675 3,358
384 384 384 384 384
Classification Datasets and Metrics. We evaluate the recallratio divergence on a downstream image-classification task over MNIST, Fashion-MNIST, CIFAR-10, and SVHN. All four datasets use 10,000 test images as queries. MNIST, Fashion-MNIST and CIFAR10 use the standard image training split as the base corpus and the complete test split as queries. For SVHN, we use the training split as the base corpus and the first 10,000 images of the test split as queries, matching the query count of the other three datasets. All benchmarks reuse the standard datasets and class labels from huggingface.co/datasets/. Following recent works that isolate the effect of retrieval quality on downstream performance by constructing retrieval sets from controlled mixtures of gold and near-miss items [36, 39], we evaluate performance using artificially synthesized retrieval sets at controlled recall levels 𝑟 ∈ {0.4, 0.5, ..., 1.0}. This synthesis is necessary as HNSW typically achieves near-1.0
Recall, making a wide accuracy spectrum otherwise difficult to observe empirically. Specifically, for a target recall 𝑟 , we construct a 100-item result set by mixing 100𝑟 exact top-100 items (the "gold set") with 100(1 − 𝑟 ) items drawn in rank order from the nearest non-gold neighbors immediately beyond the gold set. We report Label Precision at 𝑘 = 100 (LP@100), i.e., the fraction of returned vectors sharing the query’s class. We normalize the LP@100 of ANN results to the LP of the exact 𝑘NN set as follows. If LP@100(𝑟 ) denotes LP at 𝑘 = 100 on the synthesized set at recall LP@100(𝑟 ) level 𝑟 , the normalized LP@100 value is LPnorm (𝑟 ) = LP@100(1.0) . This is done because exact-search LP@100 varies widely across datasets (from 0.228 on CIFAR-10 to 0.887 on MNIST); dividing by the LP value at 𝑟 = 1.0 removes these baseline differences and places LP, 1/Ratio, and Recall on a common scale where 1.0 denotes exact-search quality, isolating quality changes as recall drops. RAG Datasets and Metrics. Documents and queries across five RAG datasets are encoded using all-MiniLM-L6-v2 to 384-dim vectors, which were 𝐿2 -normalized, and indexed with hnswlib. For HotpotQA, MS-MARCO, and PubMedQA, the retrieval corpus is the union of the candidate passages bundled with each query in the dataset, deduplicated where applicable; the corpus sizes in Table 2 reflect this, not the full document collection. We mirror the controlled evaluation protocol used in our classification setup, fixing the generation neighborhood context size to 𝑘 = 10. To construct the artificially synthesized retrieval sets for our target recall levels 𝑟 ∈ {0.4, 0.5, ..., 1.0}, we replace 𝑘 (1 − 𝑟 ) gold items with the nearest non-gold neighbors drawn in rank order from positions 𝑘 + 1 onward in the exact HNSW ranking. For each target recall level 𝑟 ∈ {0.4, 0.5, ..., 1.0}, we feed the mixed retrieval context into Llama 3.1:8b (temperature 0, via Ollama). To ensure a comprehensive evaluation, we analyze these datasets under two complementary reference paradigms. The first group, HotpotQA, MS-MARCO and PubMedQA (we use the first 200 queries of the standard split) evaluates performance against independent, humanwritten ground-truth annotations, cross-validating the trends under a setup free from LLM self-evaluation bias. The second group, SciFact and NFCorpus (from the BEIR benchmark [47]) utilizes LLM-generated reference answers at 𝑟 = 1.0 (temperature 0.3) to isolate how approximate context alters the model’s internal consistency. Each query is subject to a per-query generation timeout of 120 minutes; queries exceeding this limit are excluded from results. For SciFact, 292 of the 300 standard BEIR test queries produced valid results. For NFCorpus, 117 of the 323 BEIR test queries produced valid results; the remainder either had no relevance judgments or exceeded the timeout. We evaluate downstream answer quality via Semantic Similarity (cosine similarity over all-mpnet-base-v2 embeddings), a 1-10 LLM grade, and a BERTScore F1 (distilbert-base-uncased), discussed in Section 3.3. As in the classification setup, all quality metrics are normalized to the exact-search value (𝑟 = 1.0). Even at 𝑟 = 1.0, absolute scores vary substantially across datasets (e.g. Semantic Similarity is 0.517 on MS-MARCO vs. 0.755 on PubMedQA). normalizing to this value isolates how much each metric changes as recall drops.
ANN Search: Recall What Matters
6 6.1
Experimental Results and Analysis Cost-Accuracy Tradeoff (RQ1, RQ2, RQ3)
We begin by quantifying the computational overhead that optimizing for Recall@𝑘 imposes over optimizing for 1/Ratio@𝑘. For each algorithm and dataset, we sweep the full hyperparameter grid described in Section 5, recording QPS, distance computations per query, index build time and memory footprint for every configuration at different Recall@𝑘 and 1/Ratio@𝑘 levels. We report results at 𝑘 = 100 by default, and analyze the effect of 𝑘 at the end. QPS-quality trade-offs (RQ1, RQ3). Figure 2 plots the maximum achievable throughput for configurations satisfying target quality thresholds under both metrics. Across all tested algorithms and datasets, the maximum throughput that can be achieved by a configuration that satisfies a given 1/Ratio threshold 𝑇 (e.g., at least 𝑇 = 0.9) is strictly higher than the maximum throughput of a configuration satisfying the same threshold 𝑇 when Recall is used. The gap between the solid and hatched bars represents the throughput that the community currently loses by tuning ANN algorithms to reach minimum Recall targets as opposed to 1/Ratio targets. On low-LID datasets (MNIST, Fashion-MNIST), Recall and 1/Ratio have moderate QPS difference for HNSW, RaBitQ, and SymphonyQG, reaching up to 2.25×. In such data, the true neighbors are well separated from the rest, so geometric closeness and identifier match are aligned. SuCo cannot reach Recall@100 ≥ 0.95 on either dataset, and Annoy fails on MNIST while exhibiting a 3.07× speedup on Fashion-MNIST. On the other hand, SuCo and Annoy satisfy 1/Ratio@100 ≥ 0.95 at thousands of QPS. On mid-to-high LID datasets (AGNews, SimpleWiki, Gist, ImageNet), the gap between Recall and 1/Ratio QPS widens. Annoy fails to reach Recall@100 ≥ 0.95 on any of the four datasets, but reaches 1/Ratio@100 ≥ 0.95 at thousands of QPS on AGNews, SimpleWiki, and Gist (ImageNet is unreachable under both metrics). For AGNews, the remaining algorithms reach 2×–3× speedups. SimpleWiki is a notable exception for SymphonyQG. At such a high dimensionality (𝐷 = 3,072), the product-quantization codes introduce high distortion such that graph traversal follows suboptimal paths, returning near-zero Recall across all configurations and preventing a speedup comparison. On Gist, HNSW and SuCo also fail to reach Recall@100 ≥ 0.95 at any tested configuration, while 1/Ratio@100 ≥ 0.95 is achievable for both at 5,338 and 1,821 QPS, respectively; RaBitQ and SymphonyQG reach speedups of 4.49× and 5.27×. ImageNet produces the largest speedups of 1/Ratio over Recall despite moderate LID, reaching 9.98× for HNSW, 8.21× for RaBitQ, and 8.54× for SymphonyQG; SuCo cannot reach Recall@100 ≥ 0.95 here, and Annoy fails to reach either threshold. This suggests that while LID captures the main trend, factors such as the data distribution also contribute to the gap. The pattern intensifies at higher thresholds. At 𝑇 = 0.99, the average QPS speedup across reachable datasets rises to 4.38× for HNSW, 3.90× for RaBitQ, and 3.71× for SuCo. Recall@100 ≥ 0.99 becomes unreachable for HNSW on both Gist and ImageNet, while 1/Ratio@100 ≥ 0.99 is reached in both. Most strikingly, Annoy cannot reach Recall@100 ≥ 0.99 on any of the six tested datasets, while 1/Ratio@100 ≥ 0.99 remains achievable in multiple configurations. Under 1/Ratio, these configurations
achieve near-perfect distance-based quality; under Recall, they are rejected because of low overlap to the true 𝑘NN set. Distance computations (RQ1). QPS is system-dependent: it reflects CPU speed, memory bandwidth, SIMD width, and parallelism. To isolate the algorithmic cost independently of hardware, Figure 3 reports the minimum number of distance computations per query needed to reach each quality threshold. For a given threshold 𝑇 , we take the configuration with the fewest distance computations among all configurations satisfying score ≥ 𝑇 , and report this minimum separately for Recall and 1/Ratio. At 𝑇 = 0.95 and 𝑘 = 100, satisfying Recall requires more distance computations than satisfying 1/Ratio across all five algorithms: 9.36× for HNSW, 2.48× for RaBitQ, 2.38× for SymphonyQG, 1.86× for SuCo, and 3.22× for Annoy on average across datasets. The distance-computation gap and the QPS gap do not always align in magnitude, because different algorithmic bottlenecks dominate in each case. For HNSW, the distance-computation gap consistently exceeds the QPS gap (e.g., 33× vs. 10× on ImageNet at 𝑇 = 0.95): graph-traversal overhead (pointer chasing, branch misprediction, candidate-list management) adds a per-hop cost that does not scale with the number of distances computed. For RaBitQ, the pattern inverts: on Gist at 𝑇 = 0.99, the distance-computation gap is 1.33× while the QPS gap is 4.57×, because each quantized distance estimate is a cheap bitwise operation, so the distance-computation count alone understates the total cost of scanning additional IVF clusters. Distance computations and QPS therefore tell complementary stories, but both independently confirm that 1/Ratio reaches quality thresholds with less work than Recall. Note that this divergence is not an artifact of parallelism; the queries are independent, and running them across multiple cores speeds up both configurations by about the same factor, so the ratio between their throughputs is not affected. Index build time (RQ1). Next, we investigate whether the overhead of optimizing for Recall also extends to index construction. Table 3 reports the ratio of the minimum build time required to satisfy Recall versus 1/Ratio at 𝑘 = 100. For some thresholds 𝑇 , Recall ≥ 𝑇 was unachievable; these cases were marked by N/A. For HNSW, the build-time overhead depends on the threshold. At 𝑇 = 0.90 and 𝑇 = 0.95, the cheapest Recall-satisfying and 1/Ratiosatisfying configurations require essentially the same build time in most cases. On Gist the difference is exceptionally high at 𝑇 = 0.90 (18.39×); having high LID, Gist requires a much denser graph to satisfy Recall. At 𝑇 = 0.99, however, the Recall-satisfying build cost rises on average to 2.73×, as denser graphs are required (higher 𝑀 or efConstruction) than 1/Ratio demands. For SymphonyQG, the pattern is different: the average build-time ratio is ≈ 2.40× at 𝑇 = 0.90 and 𝑇 = 0.95, narrowing to ≈ 1.06× at 𝑇 = 0.99 on three of the four reachable datasets. At the highest threshold, only the densest configurations satisfy either metric, so the build-time gap closes; Gist is an exception at 5.96×, where its high LID still demands a substantially denser graph for Recall@99 than for 1/Ratio@99. For RaBitQ, SuCo, and Annoy, the minimum build time achieving each threshold is essentially the same under both metrics (average ratios of 1.00×, 1.37× or less, and 1.00× respectively), indicating that the cheapest Recall-satisfying and 1/Ratio-satisfying configurations use the same index construction parameters. For Annoy in particular,
Dimitris Dimitropoulos and Nikos Mamoulis
Recall@100 Threshold
1/Ratio@100 Threshold
Annoy
Max QPS (log scale)
T = 0.90 104
104
103
103
IST
T NIS
M
-MN ion
h Fas
iki Ne eW AG Simpl ws
SuCo
RaBitQ
HNSW
T = 0.95
ist
G
Net
104 103
T NIS
ge Ima
SymphonyQG
T = 0.99
M
IST
N
-M ion
h Fas
s iki New eW AG Simpl
ist
G
Net
102
ge Ima
iki ws IST IST MN n-MN AGNe pleW Sim hio Fas
t
Gis
Net
ge Ima
Min dist. comps / query (log scale)
Figure 2: Maximum achievable QPS under Recall@100 and 1/Ratio@100 across target quality thresholds 𝑇 ∈ {0.90, 0.95, 0.99}. Missing bars indicate the threshold was unreachable by any tested configuration.
Recall@100 Threshold
1/Ratio@100 Threshold
T = 0.90 104
104
103
103
102
M
T NIS
IST
-MN ion
h Fas
Ne
ws
AG
i Wik
ple Sim
Annoy
SuCo
RaBitQ
T = 0.95
t Gis
Im
102
Net age
HNSW
SymphonyQG
T = 0.99 104 103
iki ws IST IST MN n-MN AGNe pleW m o Si hi Fas
t
Gis
Ima
et geN
102
iki ws IST IST MN n-MN AGNe pleW m o Si hi Fas
t
Gis
geN
Ima
et
Figure 3: Minimum distance computations per query to reach quality threshold 𝑇 at 𝑘 = 100, for 𝑇 ∈ {0.90, 0.95, 0.99} (rows) and each algorithm (columns). Missing bars: threshold unreachable. Table 3: Ratio of minimum index build time required to satisfy Recall@100 ≥ 𝑇 versus 1/Ratio@100 ≥ 𝑇 . "N/A" indicates Recall ≥ 𝑇 was unreachable at any configuration. RaBitQ, SuCo, and Annoy are omitted as their build-time ratios stay at or near 1.00× across all datasets and thresholds. HNSW Dataset MNIST Fashion-MNIST ImageNet AGNews SimpleWiki Gist
SymphonyQG
𝑇 = 0.90
𝑇 = 0.95
𝑇 = 0.99
𝑇 = 0.90
𝑇 = 0.95
𝑇 = 0.99
1.00× 1.00× 1.84× 1.00× 1.00× 18.39×
1.00× 1.00× 3.63× 1.00× 1.52× N/A
1.44× 1.00× N/A 4.58× 3.91× N/A
2.28× 2.13× 2.31× 2.82× N/A 2.45×
2.28× 2.12× 2.31× 2.82× N/A 2.45×
1.09× 1.08× N/A 1.00× N/A 5.96×
this comparison is restricted to 𝑇 ∈ {0.90, 0.95}, as Recall@100 ≥ 0.99 is unreachable on every tested dataset. Memory footprint (RQ1). We also studied the memory overhead of indices optimized for Recall vs. 1/Ratio. We report the main observations; details are not shown due to the interest of space. Across most algorithms, datasets, and thresholds, the average ratio of Recall-satisfying to 1/Ratio-satisfying memory is near 1.0× (exactly 1.00× for RaBitQ and Annoy, and within a few percent for SuCo, HNSW, and SymphonyQG). Memory overheads become visible only at the highest quality thresholds, and even there remain modest: the largest gap we observe is SymphonyQG on Gist at 𝑇 = 0.99, where Recall demands 1.32× the memory of 1/Ratio, followed by HNSW on ImageNet at 𝑇 = 0.95 (1.05× overhead).
Interestingly, large build-time gaps do not translate into large memory gaps. The most striking case is HNSW on Gist at 𝑇 = 0.90: the Recall-satisfying configuration doubles the graph connectivity parameter from 𝑀 = 16 to 𝑀 = 32 and requires 18.39× more build time, yet the final memory footprint grows by only 1.6%. This is consistent with the in-memory footprint of HNSW being dominated by raw vector storage [42, 61] rather than graph adjacency. Algorithm rankings (RQ2). As shown in Figure 2, the relative ranking of algorithms in terms of throughput remains largely unchanged if we optimize them for 1/Ratio instead of Recall: SymphonyQG generally achieves the highest QPS under both metrics across most datasets, with HNSW, RaBitQ, SuCo, and Annoy trading the remaining positions depending on the dataset and threshold. The relative gaps between algorithms, however, are not preserved; cross-algorithm differences can widen or narrow. At 𝑇 = 0.95, SymphonyQG is 3.1× faster than HNSW on MNIST under Recall but 6.9× faster under 1/Ratio; on Fashion-MNIST, HNSW is 2.9× faster than Annoy under Recall but only 1.4× faster under 1/Ratio. Algorithms with near-identical throughput (e.g., HNSW and RaBitQ on SimpleWiki at 𝑇 = 0.95) may change rank if 1/Ratio is used instead of Recall, but this does not change the winner algorithm. The same observation holds along the other cost axes. For minimum distance computations per query (Figure 3), satisfying Recall requires between 1.86× and 9.36× more distance computations than 1/Ratio across the five algorithms at 𝑇 = 0.95, a multiplier consistent enough not to reorder them. Regarding index build time, the Recall-to-1/Ratio ratio is essentially flat for RaBitQ, SuCo, and
ANN Search: Recall What Matters
Annoy and reaches up to 2.39× on average for SymphonyQG at 𝑇 = 0.95, but no algorithm changes its rank under the new metric. Finally, search-phase memory is essentially identical under both metrics for every algorithm, so cross-algorithm memory rankings are unchanged. The overall conclusion is therefore: changing the evaluation metric from Recall to 1/Ratio shifts the absolute cost at which each algorithm reaches operational quality, but it does not change which algorithms are faster, lighter, or cheaper to build. This has a practical implication: since the ranking is stable, the comparative conclusions of Recall-based benchmarks [3, 25, 37] carry over to 1/Ratio, and can be reproduced more cheaply by benchmarking under 1/Ratio. Only the magnitude of the differences is metric-specific. Effect of 𝑘 (RQ3). Figure 4 reports the QPS speedup of 1/Ratio over Recall at 𝑇 = 0.95 as a function of 𝑘 ∈ {1, 20, 50, 100}, broken down by algorithm and dataset. The speedup grows monotonically with 𝑘 in most algorithm-dataset-threshold combinations we tested. As 𝑘 increases, the query boundary in the search space that encloses the true NNs expands, and the probability that an ANN algorithm returns a neighbor geometrically as close as a ground-truth vector but with a different identifier rises [7], penalizing Recall while leaving 1/Ratio essentially unchanged. On ImageNet under HNSW, the QPS speedup rises from 6.29× at 𝑘 = 1 to 9.98× at 𝑘 = 100; on Gist under SymphonyQG, from 3.64× at 𝑘 = 1 to 5.27× at 𝑘 = 100. The same trend holds at 𝑇 = 0.90 and 𝑇 = 0.99, with larger absolute speedups at higher thresholds. Geometric divergence across datasets (RQ3). The results above show that the efficiency gap between Recall and 1/Ratio varies across datasets and is related to, though not fully determined by, LID. To isolate this relationship, we examine how each metric degrades as 𝑘 grows, fixing the algorithm configuration and varying only 𝑘 ∈ {1, 20, 50, 100}. Figure 5 reports, for every algorithm and dataset, the average percentage change of Recall@𝑘 and 1/Ratio@𝑘 relative to their 𝑘=1 values across all configurations in the parameter sweep. A consistent pattern emerges across all five algorithms: Recall@𝑘 drops substantially as 𝑘 grows, with the magnitude broadly tracking LID for RaBitQ, HNSW, and SymphonyQG. For Annoy and SuCo, the Recall@𝑘 degradation is less related to LID; because tree-based and subspace-partitioning indices restrict query routing to pre-computed structures (such as leaf nodes or projected subspaces), their approximation errors are dominated by structural partitioning boundaries rather than pure geometric distance spacing [5, 59]. On the other hand, 1/Ratio@𝑘 stays within a much narrower band, with 𝑦-axis ranges roughly 4×-5× smaller. SuCo exhibits the largest 1/Ratio drop (up to 6.4%), which is still much smaller than its corresponding Recall drop (28.6%). The connection to dimensionality is geometric. In high-LID spaces the data manifold is locally uniform, so successive neighbors are nearly equidistant; as 𝑘 grows, the retrieved set extends deeper into this equidistant shell, making strict identifier matching (what Recall measures) increasingly unreliable while the distance quality of retrieved vectors (what 1/Ratio measures) stays high. In low-LID spaces, the effect of 𝑘 is smaller, explaining the broader trend in Figure 5.
6.2
Classification (RQ4)
The cost-accuracy experiments show that 1/Ratio@𝑘 reaches operational thresholds at substantially lower cost than Recall@𝑘. But a metric with easy-to-achieve quality targets, like 1/Ratio@𝑘, is only useful if it actually tracks what matters: downstream task quality. In this subsection we test this directly by investigating whether 1/Ratio@𝑘 is aligned with downstream task retrieval quality. We use 𝑘-nearest neighbor classification on four image benchmarks (MNIST, Fashion-MNIST, CIFAR-10, and SVHN) and measure Label Precision at 𝑘 = 100 (LP@100), the fraction of retrieved vectors that share the query’s class label. We ask two questions: (i) does LP@100 actually degrade as Recall drops, and (ii) which retrieval metric, Recall or 1/Ratio tracks LP@100 more faithfully? To answer, we apply the synthetic recall control and normalization and report normalized precision 𝐿𝑃𝑛𝑜𝑟𝑚 , as defined in Section 5. Downstream quality under recall degradation. Figure 6 plots LP@100 and 1/Ratio@100 against synthetic recall level for all four datasets, both normalized so that the quality of exact search (𝑟 = 1.0) corresponds to 1.0. As recall drops from 1.0 to 0.4 (a 60% change) we observe a consistent behavior across all datasets: downstream quality barely moves. At 𝑟 = 0.4, 𝐿𝑃𝑛𝑜𝑟𝑚 remains remarkably stable at 0.974 for MNIST, 0.978 for Fashion-MNIST, 0.968 for CIFAR-10, and 0.943 for SVHN. Over the exact same sweep, 1/Ratio@100 perfectly mirrors this stability, resting at 0.967, 0.968, 0.982, and 0.977 respectively. Even in the worst-case dataset (SVHN), 𝐿𝑃𝑛𝑜𝑟𝑚 only drops by 0.057 (from 1.0 down to 0.943). This is an order of magnitude smaller than the massive 0.60 drop in Recall that produced it. The dotted 𝑦 = 𝑥 diagonal in each plot of Figure 6 marks where Recall itself sits as a quality predictor. The gap between the diagonal and the LP and 1/Ratio curves is wide and consistent: LP and 1/Ratio both stay above 0.94 across the entire sweep, while Recall drops to a level (0.4) far from the actual task quality. Quantifying the gap between the two metrics. To measure how well each metric predicts downstream performance, we compute the Mean Absolute Deviation (MAD) between the predictor metric (Recall or 1/Ratio) and the true normalized quality (𝐿𝑃𝑛𝑜𝑟𝑚 ) across the 𝑟 ∈ [0.4, 1.0] sweep. If a metric were a perfect proxy for quality, its value would exactly equal the normalized LP@100, yielding a MAD of zero. As Figure 7 demonstrates, Recall is a remarkably poor predictor of actual quality, heavily underestimating performance with MAD values around 0.26. In contrast, 1/Ratio’s MAD is up to two orders of magnitude lower. For instance, on MNIST at 𝑟 = 0.4, a 1/Ratio value of 0.967 closely matches the actual 𝐿𝑃𝑛𝑜𝑟𝑚 of 0.974, a prediction error of less than 1%. Overall, besides enabling more efficient ANN search configurations, 1/Ratio serves as a much better predictor of downstream quality compared to Recall. Stability of the predictor metric across neighborhood sizes. The experimental results presented thus far establish that at 𝑘 = 100 1/Ratio serves as a far more accurate proxy for downstream quality (𝐿𝑃𝑛𝑜𝑟𝑚 ) than Recall. To ensure this advantage is not an artifact of evaluating a wide search depth (large 𝑘), Table 4 reports the MAD of each metric against 𝐿𝑃𝑛𝑜𝑟𝑚 for smaller neighborhood sizes (𝑘 ∈ {1, 20, 50, 100}). The disconnect between Recall and downstream task performance holds at every search depth. Recall’s MAD remains high, ranging between 23.3% and 26.6% across all datasets
Dimitris Dimitropoulos and Nikos Mamoulis
QPS speedup (log scale)
MNIST (LID=12.41)
Fashion-MNIST (LID=13.99)
Annoy
15× 10×
ImageNet (LID=17.85)
SuCo
AGNews (LID=24.09)
RaBitQ
SimpleWiki (LID=27.45)
Gist (LID=32.35)
HNSW
SymphonyQG
5× 3× 2× 1× 1
20
50
100 1
k
20
50
100 1
k
20
50
100 1
k
20
50
100 1
k
20
50
100
k
Figure 4: QPS speedup of 1/Ratio over Recall as a function of 𝑘 ∈ {1, 20, 50, 100} at 𝑇 = 0.95, per algorithm and dataset. Absent lines indicate that Recall@𝑘 ≥ 0.95 was unreachable at all tested configurations: at 𝑇 = 0.95, Annoy maintains Recall across the full range of 𝑘 only on Fashion-MNIST, SuCo only on AGNews and SimpleWiki, and HNSW on Gist is reachable only at 𝑘 = 1.
MNIST (LID=12.41) Fashion-MNIST (LID=13.99) Annoy
ImageNet (LID=17.85) AGNews (LID=24.09) SuCo
SimpleWiki (LID=27.45) Gist (LID=32.35)
RaBitQ
Recall degradation 1/Ratio degradation
HNSW
SymphonyQG
Metric (% from k=1)
0% -10% -20% -30% -40%
1
20
50
100 1
k
20
50
100 1
k
20
50
100 1
k
20
50
100 1
k
20
50
100
k
Figure 5: Average change in Recall@𝑘 and 1/Ratio@𝑘 relative to their 𝑘=1 values, as 𝑘 grows from 1 to 100, across all parameter configurations per algorithm. Recall degrades substantially with 𝑘, while 1/Ratio remains nearly flat.
% of r=1.0 Performance
100
LP@100(r) / LP@100(1.0)
1 / Ratio@100
Recall (= x, reference)
MNIST
Fashion-MNIST
CIFAR-10
SVHN
80 60 40
0.4
0.5
0.6
0.7
0.8
Recall@100
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@100
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@100
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@100
0.9
1.0
Figure 6: LP@100 and 1/Ratio@100 (normalized to exact search) versus synthetic recall. Both metrics stay near 1.0 as recall drops to 0.4; the dotted 𝑦=𝑥 diagonal shows how far Recall diverges from actual downstream quality. and 𝑘 values. Regardless of neighborhood size, Recall consistently overstates the drop in true classification quality. By contrast, 1/Ratio is a more accurate predictor even at 𝑘 = 1. In this case, where substituting a single vector determines the prediction, its MAD is between 1.0% and 2.3%. As 𝑘 increases, this advantage widens.
6.3
RAG Experiments (RQ4)
The classification experiments show that Label Precision remains stable as Recall degrades, and that 1/Ratio@𝑘 tracks this stability far more faithfully than Recall does. We now extend the analysis to retrieval-augmented generation (RAG), where the downstream task is fundamentally more complex: the system must synthesize a
free-form answer from retrieved passages and quality is measured by how closely that answer matches a reference. We evaluate across five datasets under two reference paradigms, as discussed in Section 5. First, on three QA benchmarks with human-written gold answers (HotpotQA, MS-MARCO, and PubMedQA), we measure absolute task accuracy. For each query and synthetic recall level, the LLM generates an answer from the approximate retrieved context, and we evaluate this generated text against the independent, human-written ground-truth reference. Next, we evaluate the LLM’s internal consistency on two BEIR benchmarks (SciFact and NFCorpus), where no human gold answers are available. Again, for each query and synthetic recall level, the LLM generates an answer from the approximate context at temperature 0. The
ANN Search: Recall What Matters
1/Ratio@100 (prediction error)
Recall@100 (prediction error)
Mean Absolute Deviation (MAD) from True Quality
0.30 0.25
0.262
0.260
0.258
0.251
0.20 0.15 0.10 0.05 0.00
0.002
MNIST
0.003
0.011
0.005
Fashion-MNIST CIFAR-10
SVHN
Figure 7: Mean Absolute Deviation (MAD) of Recall and 1/Ratio from the true normalized downstream quality (LP@100). Perfect proxies for quality have zero MAD. Table 4: Mean Absolute Deviation (MAD), representing the prediction error (in %) of Recall and 1/Ratio from normalized downstream quality (𝐿𝑃𝑛𝑜𝑟𝑚 = LP@𝑘 / LP@𝑘 (1.0)), for 𝑘 ∈ {1, 20, 50, 100}. Lower values indicate a more faithful proxy for true downstream quality. Prediction error (%) Dataset
Predictor
k=1
k = 20
k = 50
k = 100
MNIST
Recall 1/Ratio
26.6 1.3
26.5 0.6
26.3 0.4
26.0 0.2
Fashion-MNIST
Recall 1/Ratio
26.0 1.0
26.4 0.4
26.4 0.4
26.2 0.3
CIFAR-10
Recall 1/Ratio
23.3 2.3
25.6 0.8
25.8 0.6
25.8 0.5
SVHN
Recall 1/Ratio
24.5 1.3
25.3 1.0
25.2 1.0
25.1 1.1
difference is the reference, which is now generated by the same LLM from the exact top-𝑘 neighbors at temperature 0.3, to avoid the deterministic self-comparison artifact that temperature 0 would cause at 𝑟 = 1.0. These experiment setups isolate the generation phase, allowing us to accurately quantify how approximation impacts the final output; specifically, whether supplying the LLM with geometrically close near-misses instead of exact nearest neighbors degrades task accuracy or alters the synthesized response. Answer quality under recall degradation. We begin with the human-annotated benchmarks, where the gold answer is entirely independent of the retrieval and generation pipeline. Figure 8 plots the three normalized quality metrics and 1/Ratio@10 against synthetic recall for the three datasets. Answer quality is effectively decoupled from recall across the full range 𝑟 ∈ [0.4, 1.0]: BERTScore F1 varies by at most 1.2% on HotpotQA and under 1% on MS-MARCO and PubMedQA. Similarly, the LLM-graded score varies by under 1% on all three datasets. Semantic Similarity is the noisiest of the three metrics (up to 5.1% variation across recall levels). On HotpotQA, it is non-monotonic: it starts at 97.0% at recall 𝑟 = 0.4, but peaks at 102.1% at 𝑟 = 0.6, surpassing the perfect-recall baseline.
The spikes above 100% do not mean the answer actually got better; rather, the mix of passages at that specific step triggers slightly different wording that happens to align a bit closer with the human text. While these wording shifts make language scores look messy, the underlying system is actually highly stable. We can verify this through the 1/Ratio metric, which bypasses text entirely to measure the vector distances. Across all three datasets, 1/Ratio remains tight, dropping by at most 6.9% on MS-MARCO and under 2.5% on HotpotQA and PubMedQA. Because the text quality drops even less than the vector math, 1/Ratio serves as a safe, conservative floor for how well the system performs. Table 5 reports the exact raw scores ranges across all configurations, confirming this flat performance trend. On HotpotQA, MS-MARCO, and PubMedQA, the text quality metrics barely budge. For example, on PubMedQA, the LLM-graded score varies by a mere 0.07 points on a 10-point scale across the entire recall sweep. Recall forces a massive drop of 60% (from 1.0 down to 0.4). In contrast, 1/Ratio numbers remain remarkably steady and never drop below 93.14% on any dataset. Ultimately, these raw values confirm that configurations that Recall flags as “inadequate” can still produce answers of identical quality as exact 𝑘NN search. Table 5: Range of raw quality metrics across the recall sweep 𝑟 ∈ [0.4, 1.0] for all five RAG datasets. Dataset
1/Ratio
Sem. Sim. BERTScore Grade/10
HotpotQA MS-MARCO PubMedQA SciFact NFCorpus
0.98–1.00 0.93–1.00 0.98–1.00 0.98–1.00 0.98–1.00
0.52–0.55 0.51–0.53 0.75–0.76 0.80–0.83 0.76–0.81
0.75–0.76 0.76 0.80 0.86–0.87 0.81–0.84
9.13–9.19 8.95–9.01 8.66–8.73 8.80–8.92 8.71–8.83
LLM internal consistency under approximate retrieval. The human-annotated experiments measure quality against an external ground truth. A complementary question is whether the LLM’s generative process is itself sensitive to recall degradation, i.e., whether substituting exact neighbors with geometrically close but identifierdistinct passages causes the model’s output to meaningfully diverge from what it would produce exact 𝑘NN retrieval. We test this on two BEIR datasets (SciFact and NFCorpus). For each query, a reference answer is generated from the exact 𝑘 nearest neighbors using Llama 3.1:8b at temperature 0.3, while the sweep answers (𝑟 ∈ [0.4, 1.0]) are generated at temperature 0 and evaluated against this reference. Temperature 0.3 avoids a deterministic artifact: at temperature 0 the 𝑟 =1.0 sweep answer and the reference are identical strings, inflating apparent degradation at lower recall levels. Temperature 0.3 introduces slight wording variance, providing a high-quality but non-identical string. Figure 8 normalizes all metrics to their 𝑟 =1.0 values, so that 100% represents performance under perfect recall and any drop reflects recall-induced degradation alone. The degradation is remarkably small: Semantic Similarity drops 3.5% on SciFact and 5.7% on NFCorpus as recall degrades to 𝑟 =0.4; BERTScore F1 drops 2–3%; the LLMgraded score drops 1.5% or less. Over the same range, 1/Ratio@10 drops by under 2.4% on both datasets. BERTScore and the LLM grade closely track the geometric signal; Semantic Similarity shows slightly more variation (3.5% on SciFact, 5.7% on NFCorpus). In all
Dimitris Dimitropoulos and Nikos Mamoulis
% of r=1.0 Performance
1 / Ratio 106 104 102 100 98 96 94 92
SciFact
0.4
0.5
0.6
0.7
Semantic Similarity
NFCorpus
0.8
Recall@10
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@10
BERTScore F1
Grade /10 (Llama)
HotpotQA
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@10
MS-MARCO
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@10
PubMedQA
0.9
1.0
0.4
0.5
0.6
0.7
0.8
Recall@10
0.9
1.0
Figure 8: Downstream generation quality (Semantic Similarity, BERTScore F1, Grade/10) and geometric stability (1/Ratio) versus synthetic search recall, normalized to the 𝑟 =1.0 exact-search baseline. cases, quality loss is bounded within a narrow interval even when Recall degrades by 60%. 1/Ratio@10 (prediction error)
Recall@10 (prediction error) Mean Absolute Deviation (MAD) from True Quality
0.35 0.30
0.304
0.287
0.287
0.302
0.299
0.25 0.20 0.15 0.10 0.05 0.00
0.006
0.005
0.011
SciFact
NFCorpus
HotpotQA
0.026
MS-MARCO
0.008
PubMedQA
Figure 9: MAD of Recall and 1/Ratio from true RAG quality across datasets. Recall vs. 1/Ratio as quality proxies. Both experiments arrive at the same conclusion: answer quality is quite stable across a wide range of Recall levels. To quantify whether 1/Ratio reflects this stability better than Recall, we compute their MAD against a composite true quality score (the average of the three normalized metrics). Figure 9 shows the MAD of Recall and 1/Ratio across the human-annotated benchmarks: 1/Ratio’s MAD is 1.1% (HotpotQA), 2.6% (MS-MARCO), and 0.8% (PubMedQA); Recall’s MAD is approximately 30% across all three –an improvement of 11× to 37×. On the BEIR benchmarks, 1/Ratio achieves a MAD of 0.6% (SciFact) and 0.5% (NFCorpus), compared to Recall’s 28.7% –a 47× to 57× improvement. Across all five datasets, 1/Ratio is consistently a much better predictor of downstream RAG quality than Recall.
6.4
Summary of Experimental findings
Our experiments support four main conclusions. Optimizing for 1/Ratio is substantially cheaper than optimizing for Recall (RQ1). Reaching a fixed quality threshold under 1/Ratio requires far less work than under Recall: at 𝑇 = 0.95 and 𝑘 = 100, satisfying Recall costs on average 1.86×-9.36× more distance computations (up to 33.3× for HNSW on ImageNet), yields an average 3.27× lower QPS, and takes up to 3.63× (HNSW) and 2.82× (SymphonyQG) more build time. The gap widens with 𝑘 and, in most cases, with intrinsic dimensionality, and Recall frequently rejects configurations that 1/Ratio accepts as distance-accurate. The advantage of 1/Ratio is computational rather than spatial (RQ1). The memory footprint of ANN methods is dominated by the base index structure rather
than the parameters for achieving high Recall, so it is similar under both metrics. Algorithm rankings are mostly stable (RQ2). Replacing Recall with 1/Ratio does not change which algorithms are faster, lighter, or cheaper to build, only the absolute cost at which each reaches a given quality level. The relative magnitude of the differences; however, is metric-specific and can widen or narrow. Recall overstates the cost of approximation (RQ3, RQ4). The two metrics diverge as 𝑘 and LID grow: an algorithm increasingly returns neighbors that are as close as the true 𝑘NNs but carry different identifiers, penalizing Recall while leaving 1/Ratio high. Low Recall values have little effect on downstream task quality. Across image classification and RAG, retrieval quality stays stable as Recall falls to 0.4, and 1/Ratio tracks true quality far more faithfully (prediction error stays under 3%, against 25-30% for Recall).
7
Conclusions
In this paper we questioned the long-standing convention of evaluating and tuning ANN algorithms based on Recall@𝑘, and investigated 1/Ratio@𝑘, the inverse approximation ratio, as a target quality measure. Unlike recently proposed alternatives, 1/Ratio@𝑘 is simultaneously judge-free, hyperparameter-free, and computable from the embeddings and ground-truth identifiers that standard ANN benchmarks already provide. Benchmarking five state-of-the-art algorithms across six datasets of varying intrinsic dimensionality, we found that Recall@𝑘 systematically overstates the cost of approximation: optimizing for 1/Ratio@𝑘 reaches the same operational quality thresholds at substantially lower cost in query time, distance computations, and index build time, with the gap widening as 𝑘 and intrinsic dimensionality grow, while leaving the relative ranking of algorithms essentially unchanged. Crucially, index configurations that would be dismissed due to low Recall, are not inaccurate in practice: across image classification and retrieval-augmented generation, downstream quality remained stable even as Recall dropped to 0.4, while 1/Ratio@𝑘 tracked quality more faithfully. The key takeouts from this study are (i) by using 1/Ratio@𝑘 as an objective instead of Recall@k, researchers and practitioners can evaluate and tune equally effective ANN methods much faster; and (ii) expensive ANN index configurations that target high Recall levels can be replaced by faster and cheaper-to-construct configurations that achieve high 1/Ratio@𝑘, without affecting the actual quality of the intended downstream tasks.
ANN Search: Recall What Matters
References [1] Laurent Amsaleg and Hervé Jégou. 2026. Datasets for approximate nearest neighbor search. http://corpus-texmex.irisa.fr/. (Accessed: February, 2026). [2] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. 1998. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45, 6 (Nov. 1998), 891–923. doi:10.1145/293347.293348 [3] Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020). doi:10.1016/J.IS.2019.02.006 [4] Martin Aumüller and Matteo Ceccarello. 2019. The Role of Local Intrinsic Dimensionality in Benchmarking Nearest Neighbor Search. In Similarity Search and Applications - 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2-4, 2019, Proceedings (Lecture Notes in Computer Science), Giuseppe Amato, Claudio Gennaro, Vincent Oria, and Milos Radovanovic (Eds.). Springer, 113–127. doi:10.1007/978-3-030-32047-8_11 [5] Artem Babenko and Victor S. Lempitsky. 2012. The inverted multi-index. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012. IEEE Computer Society, 3069–3076. doi:10.1109/CVPR.2012. 6248038 [6] Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18, 9 (1975), 509–517. doi:10.1145/361002.361007 [7] Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When Is ”Nearest Neighbor” Meaningful?. In Database Theory - ICDT ’99, 7th International Conference, Jerusalem, Israel, January 10-12, 1999, Proceedings (Lecture Notes in Computer Science), Catriel Beeri and Peter Buneman (Eds.). Springer, 217–235. doi:10.1007/3-540-49257-7_15 [8] Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. 2025. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 4 (2025), 242:1–242:26. doi:10.1145/3749160 [9] Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. 2024. RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 11 (2024), 2735–2749. doi:10. 14778/3681954.3681959 [10] Tingyang Chen, Cong Fu, Jiahua Wu, Haotian Wu, Hua Fan, Xiangyu Ke, Yunjun Gao, Yabo Ni, and Anxiang Zeng. 2025. Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views. CoRR abs/2512.12980 (2025). arXiv:2512.12980 doi:10.48550/ARXIV.2512.12980 [11] Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, Cynthia Dwork (Ed.). ACM, 537–546. doi:10.1145/1374376.1374452 [12] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004, Jack Snoeyink and Jean-Daniel Boissonnat (Eds.). ACM, 253–262. doi:10.1145/997817.997857 [13] Laxman Dhulipala, Majid Hadian, Rajesh Jayaram, Jason Lee, and Vahab Mirrokni. 2024. MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings. CoRR abs/2405.19504 (2024). arXiv:2405.19504 doi:10.48550/ARXIV.2405.19504 [14] Dimitris Dimitropoulos, Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis. 2026. CRISP: Correlation-Resilient Indexing via Subspace Partitioning. CoRR abs/2603.05180 (2026). arXiv:2603.05180 doi:10.48550/ARXIV. 2603.05180 [15] Elena Facco, Maria d’Errico, Alex Rodriguez, and Alessandro Laio. 2018. Estimating the intrinsic dimension of datasets by a minimal neighborhood information. CoRR abs/1803.06992 (2018). arXiv:1803.06992 http://arxiv.org/abs/1803.06992 [16] Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell. 44, 8 (2022), 4139–4150. doi:10.1109/TPAMI.2021.3067706 [17] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Proc. VLDB Endow. 12, 5 (2019), 461–474. doi:10.14778/3303753.3303754 [18] Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3 (2025), 202:1–202:26. doi:10.1145/3725413 [19] Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. Proc. ACM Manag. Data 1, 2 (2023), 137:1–137:27. doi:10.1145/3589282 [20] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3 (2024), 167. doi:10.1145/3654970 [21] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36, 4 (2014), 744–755. doi:10. 1109/TPAMI.2013.240
[22] Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1 (2025), 80:1–80:26. doi:10. 1145/3709730 [23] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research). PMLR, 3887–3896. http://proceedings.mlr.press/v119/guo20h. html [24] Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, Jeffrey Scott Vitter (Ed.). ACM, 604–613. doi:10.1145/276698.276876 [25] Elias Jääsaari, Ville Hyvönen, Matteo Ceccarello, Teemu Roos, and Martin Aumüller. 2025. VIBE: Vector Index Benchmark for Embeddings. CoRR abs/2505.17810 (2025). arXiv:2505.17810 doi:10.48550/ARXIV.2505.17810 [26] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https://papers.nips. cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf [27] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. doi:10.1109/TPAMI.2010.57 [28] Qiao Jin, Bhuwan Dhingra, Zhengping Liu, William W. Cohen, and Xinghua Lu. 2019. PubMedQA: A Dataset for Biomedical Research Question Answering. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, 2567–2577. doi:10.18653/V1/D19-1259 [29] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Trans. Big Data 7, 3 (2021), 535–547. doi:10.1109/ TBDATA.2019.2921572 [30] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense Passage Retrieval for OpenDomain Question Answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association for Computational Linguistics, 6769–6781. doi:10.18653/V1/2020.EMNLP-MAIN.550 [31] Alex Krizhevsky. 2009. Learning Multiple Layers of Features from Tiny Images. https://api.semanticscholar.org/CorpusID:18268744 [32] Leonardo Kuffó, Elena Krippner, and Peter Boncz. 2025. PDX: A Data Layout for Vector Similarity Search. Proc. ACM Manag. Data 3, 3 (2025), 196:1–196:26. doi:10.1145/3725333 [33] Leonardo Kuffo, Ioanna Tsakalidou, Roberta Viti, Albert Angel, Jiří Iša, and Rastislav Lenhardt. 2026. Semantic Recall for Vector Search. doi:10.48550/arXiv. 2604.20417 [34] Yann LeCun, Corinna Cortes, and CJ Burges. 2010. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist 2 (2010). [35] Leonardo Kuffo, Elena Krippner, Peter Boncz. 2026. PDX: Public Data. https:// drive.google.com/drive/u/1/folders/1f76UCrU52N2wToGMFg9ir1MY8ZocrN34. (Accessed: February, 2026). [36] Alexandria Leto, Cecilia Aguerrebere, Ishwar Singh Bhati, Ted Willke, Mariano Tepper, and Vy Ai Vo. 2024. Toward Optimal Search and Retrieval for RAG. CoRR abs/2411.07396 (2024). arXiv:2411.07396 doi:10.48550/ARXIV.2411.07396 [37] Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma. 2025. Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. Proc. ACM Manag. Data 3, 6 (2025), 1–26. doi:10.1145/ 3769763 [38] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement. IEEE Trans. Knowl. Data Eng. 32, 8 (2020), 1475–1488. doi:10.1109/TKDE.2019.2909204 [39] Xiangci Li and Jessica Ouyang. 2025. How Does Knowledge Selection Help Retrieval Augmented Generation?. In Findings of the Association for Computational Linguistics: EMNLP 2025, Suzhou, China, November 4-9, 2025, Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (Eds.). Association for Computational Linguistics, 4104–4121. https://aclanthology.org/ 2025.findings-emnlp.218/ [40] Jiahao Lou, Quan Yu, Shufeng Gong, Song Yu, Yanfeng Zhang, and Ge Yu. 2025. DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries. CoRR abs/2510.25401 (2025). arXiv:2510.25401 doi:10.48550/ARXIV.2510. 25401 [41] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world
Dimitris Dimitropoulos and Nikos Mamoulis
graphs. Inf. Syst. 45 (2014), 61–68. doi:10.1016/J.IS.2013.10.006 [42] Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. doi:10.1109/TPAMI.2018. 2889473 [43] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. 2011. Reading digits in natural images with unsupervised feature learning. (2011). [44] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. In Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016 (CEUR Workshop Proceedings), Tarek Richard Besold, Antoine Bordes, Artur S. d’Avila Garcez, and Greg Wayne (Eds.). CEURWS.org. https://ceur-ws.org/Vol-1773/CoCoNIPS_2016_paper9.pdf [45] John Paparrizos, Ikraduya Edian, Chunwei Liu, Aaron J. Elmore, and Michael J. Franklin. 2022. Fast Adaptive Similarity Search through Variance-Aware Quantization. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. IEEE, 2969–2983. doi:10.1109/ ICDE53745.2022.00268 [46] Spotify AB. 2025. spotify/annoy: Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk. https://github.com/ spotify/annoy. commit on main branch accessed on 2025-11-29. [47] Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, Joaquin Vanschoren and Sai-Kit Yeung (Eds.). [48] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021. ACM, 2614–2627. doi:10.1145/3448016.3457550 [49] Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018. A Survey on Learning to Hash. IEEE Trans. Pattern Anal. Mach. Intell. 40, 4 (2018), 769–790. doi:10.1109/TPAMI.2017.2699960 [50] Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Yifan Zhu, and Wenchao Zhou. 2025. Accelerating Graph Indexing for ANNS on Modern CPUs. Proc. ACM Manag. Data 3, 3 (2025), 123:1–123:29. doi:10.1145/3725260 [51] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 14, 11 (2021), 1964–1978. doi:10.14778/3476249.3476255 [52] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 6 (2025), 1–27. doi:10.1145/3769843 [53] Zikai Wang, Qianxi Zhang, Baotong Lu, Qi Chen, and Cheng Tan. 2025. Towards Robustness: A Critique of Current Vector Database Assessments. CoRR abs/2507.00379 (2025). arXiv:2507.00379 doi:10.48550/ARXIV.2507.00379 [54] Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA, Ashish Gupta, Oded Shmueli, and Jennifer Widom (Eds.). Morgan Kaufmann, 194–205. http: //www.vldb.org/conf/1998/p194.pdf [55] Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng. 2025. Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1 (2025), 79:1–79:29. doi:10.1145/3709729 [56] Jiuqi Wei, Botao Peng, Xiaodong Lee, and Themis Palpanas. 2024. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 9 (2024), 2241–2254. doi:10.14778/3665844.3665854 [57] Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. CoRR abs/1708.07747 (2017). arXiv:1708.07747 http://arxiv.org/abs/1708.07747 [58] Yahoo Japan. 2018. NGT: Neighborhood Graph and Tree for Indexing Highdimensional Data. https://github.com/yahoojapan/NGT. Accessed: 2026-05-20. [59] Donghui Yan, Yingjie Wang, Jin Wang, Honggang Wang, and Zhenpeng Li. 2018. K-nearest Neighbor Search by Random Projection Forests. In IEEE International Conference on Big Data (IEEE BigData 2018), Seattle, WA, USA, December 10-13, 2018, Naoki Abe, Huan Liu, Calton Pu, Xiaohua Hu, Nesreen K. Ahmed, Mu Qiao, Yang Song, Donald Kossmann, Bing Liu, Kisung Lee, Jiliang Tang, Jingrui He, and Jeffrey S. Saltz (Eds.). IEEE, 4775–4781. doi:10.1109/BIGDATA.2018.8622307
[60] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP). [61] Qiang Yue, Xiaoliang Xu, Yuxiang Wang, Yikun Tao, and Xuliyuan Luo. 2024. Routing-Guided Learned Product Quantization for Graph-Based Approximate Nearest Neighbor Search. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 4870–4883. doi:10.1109/ICDE60146.2024.00370 [62] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2019. BERTScore: Evaluating Text Generation with BERT. ArXiv abs/1904.09675 (2019). https://api.semanticscholar.org/CorpusID:127986044