Vector Search Without the Hype: Embeddings, Indexes and the Recall Trade

Approximate nearest-neighbor (ANN) search into vector indexes returns a sized set that aims to serve as a stand-in for the true k-nearest-neighbor set. Recall@k in this context measures the ratio of objects brought back that are also in the true k-nearest-neighbor set. [1] However, as this definition suggests, ANN search deliberately skips exhaustive object scans. The total number of database objects measured against is less, which is how ANN search achieves the high speed for which it is marketed.

What an ANN Index Buys

Databases such as Google Cloud Spanner allow you to query points from a multi-dimensional vector space, but you must create a vector index first. [7] One role of an ANN index in this context is figuring which parts of the database to compare a query vector against, instead of comparing it against everything. For an ANN vector index, scanning only 0.6% of database objects can give 92% recall, according to one academic report on 30-nearest-neighbor search. [3], [5] In a ten-million-object database, one version of that experiment reported sub-second query times. [4], [6] These results show the speed payoff of using an ANN index to do an "approximate" vector comparison.

According to a 2012 paper, recall@k counts the identifier matches between the size-(k) set that ANN search returns, and the true (k)-nearest-neighbor set; it doesn't factor in the proximity of objects that are not in common. [2] This measure only counts identifier overlap, not the degree to which it fails to find some elements close to the query.

Why Recall@k Is Not the Whole Story

For tasks where only the top-rank neighbors matter, the missing objects that recall@k counts may be relatively far from the query, as per the definition itself. [2] If the downstream process isn't actually trying to recover all elements up to a fixed distance, then an alternative definition called "semantic recall" may be more informative, as it takes account of the distance of the elements that are retrieved. [11]

Semantic recall is defined as the number of semantic neighbors retrieved by an ANNS algorithm, divided by the number that are retrievable via exact nearest-neighbor search. [12], This tailors the recall calculation to the specific distance, not the number, of objects that an ANN search might miss.

The right measure for vector search performance is unclear, as papers [11], [2] show, when comparing size of retrieved sets versus ranked points near the query. [11], [2] If you frame retrieval as a ranking problem, you may not actually need highest possible recall, just a high-ranked answer. [1], [2], [7], [12]

What the Benchmarks Show

Highly compressed algorithms for nearest-neighbor search, such as L&C, are outperformed on latency@recall recalls by HM-ANN, according to a 2020 NeurIPS paper. [9] In other words, many ANN solutions can skip exhaustive vector scans, and still give you most of the neighbors.

A 2012 paper showed an ANN query reviewing just 0.6% of the database, on average. [3] Some ANN benchmarks may not specify the exact scale of approximation; [11] [9] it's downplayed, so users can accept it as a tradeoff.

Conclusion

ANN searches inspect a tiny fraction of the data in a ten-million-object database when finding 92% of its nearest neighbors. [3,5,6] However, as vector search replicates a vector space, it applies differently. Like RAG and many users of embedding search, the task you import may not be the same as nearest-neighbor.

Before adopting an ANN system, consider how much more trouble high-ranking neighbors might reduce if you can retrieve some without them. Data that matches semantically may still be valuable even if it lies a bit farther from the query. [11] [2] When evaluating a vector index, begin by constructing one that reaches high recall, or use an exactly solution if you can. Then check if its shortest results improve the ranking below that threshold.