Approximate Nearest Neighbor Search

Nearest-neighbor search finds the \(k\) vectors in a collection most similar to a query vector. The exact method scores every vector: for \(N\) vectors of dimension \(d\), that is \(N\cdot d\) multiply-adds per query, and the cost grows linearly with the collection. Approximate nearest neighbor (ANN) search gives up the guarantee of returning the exact top \(k\) in exchange for scoring only a small part of the collection. It is the technique behind most vector indexes used for retrieval.

Why exactness is traded away

In high dimensions no tree or grid structure prunes the search reliably, so an exact method cannot do much better than a scan. ANN methods exploit a weaker requirement: for retrieval, returning a vector almost as close as the true neighbor is usually acceptable, and the embedding that produced the vectors is itself only an approximation of relevance. The cost is that the index can miss true neighbors, and that miss is silent: a result list looks normal whether or not it is the exact one.

Two common families

Inverted file (IVF). Cluster the vectors with k-means into nlist cells, each with a centroid, and store the member rows of each cell. At query time compare the query with the nlist centroids, pick the nprobe closest cells, and score only the vectors in them. The work is about \(nlist\cdot d + N\cdot(nprobe/nlist)\cdot d\) when cells are balanced. The failure mode is a true neighbor sitting in a cell whose centroid is not among the nprobe closest, which happens near cell boundaries.

Graph indexes (HNSW). Malkov and Yashunin's Hierarchical Navigable Small World index links each vector to nearby vectors in a layered graph. A search starts at a coarse top layer, moves greedily toward the query, and descends. The parameter efSearch is the size of the candidate list kept during the search: a larger value explores more of the graph, finds better results and takes longer. HNSW generally gives a better speed-recall trade-off than IVF at the price of more memory and slower builds.

Measuring what was lost: recall@k of the index

The quality of an ANN index is a separate quantity from the quality of the embedding. Define

\[ \text{recall@}k = \frac{1}{|Q|}\sum_{q\in Q}\frac{|\text{approx}_k(q)\cap \text{exact}_k(q)|}{k}, \]

the average fraction of the exact top \(k\) that the approximate search returned, over a set of queries \(Q\). It compares the index with an exact scan of the same vectors, so it says nothing about whether those vectors were good at representing relevance. Both numbers are needed: an index with recall@10 of 1.0 over bad embeddings is still bad, and good embeddings behind an index with recall@10 of 0.5 lose half their neighbors.

A worked example

The table illustrates a hypothetical benchmark: 20,000 synthetic unit vectors of dimension 32 drawn around 64 overlapping clusters, an IVF index with 64 cells, and 200 queries made by perturbing stored vectors. Recall is measured against an exact scan, and the cost is the average number of vectors scored (including the 64 centroid comparisons).

nprobe	recall@10	vectors scored (of 20,000)
1	0.277	394
2	0.409	710
4	0.563	1,335
8	0.750	2,591
16	0.896	5,085
64	1.000	20,064

Probing all 64 cells equals the exact scan and costs slightly more because of the centroid step. Probing 16 cells recovers about 90% of the true top 10 for about a quarter of the work. The recall gains from doubling nprobe are not monotonically smaller: they rise from 0.132 to 0.154 to 0.187 before falling to 0.146. Increasing nprobe from 16 to 64 then adds only 0.104 recall while roughly quadrupling the work, so the high-recall end has diminishing returns. These numbers belong to this synthetic data. Real collections have different cluster structure, and the right setting is chosen by measuring recall@k and latency on queries from the application.

Conditions and failure modes

• Recall depends on the data distribution. Clusters that overlap heavily, as here, make small nprobe lose more.
• An IVF index that is updated by assigning new vectors to existing centroids degrades when new documents have different vocabulary than the data used to train the centroids. Recall measured on old queries will not reveal this, so measure on queries about the new material and rebuild the cells when it drops.
• Filters applied after the ANN step can leave fewer than \(k\) results, because the approximate top \(k\) was computed before the filter removed entries.
• A higher recall index does not repair a retrieval problem caused by chunking or embedding, and the reverse is also true.

Related terms

ANN search is the index-level approximation. Reranking is a later stage that reorders a candidate list and cannot recover a neighbor the index never returned. Exact search is the baseline against which ANN recall is defined.

References

• Malkov and Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
• Johnson, Douze and Jégou, Billion-scale similarity search with GPUs (Faiss)