Approximate Nearest Neighbour Indexes and the Recall They Trade Away

Exact nearest-neighbour search over N vectors of dimension d costs N distance computations per query, each of which is d multiplications and additions. For a corpus of ten million chunks embedded at 768 dimensions, that is 7.7 billion multiply-adds per query before the first result is known, and the vectors themselves occupy 10^7 x 768 x 4 bytes, about 30 GB in 32-bit floats. Both numbers are the reason exact search is not used at scale: the memory does not fit on one machine and the compute is a hundred times what a query’s latency budget allows.

Approximate search replaces the scan with a bounded amount of work and accepts that some true neighbours will be missed. The quantity that describes how many are missed is recall at k: of the k vectors a brute-force scan would return, what fraction does the index return. Recall is not a property of an index in the abstract. It depends on the data distribution, the query distribution, and the parameter settings, and an index tuned to 0.95 recall on one corpus can fall to 0.7 on another without any change to its configuration.

Three families and what each one exploits

Vector indexes exploit different kinds of structure, and the family determines the failure mode.

Partition-based indexes divide the space into cells and search only the cells nearest the query. The k-means variant trains m centroids on a sample of the corpus, assigns every vector to its nearest centroid, and stores an inverted list per centroid. A query computes its distance to all m centroids, picks the n nearest cells, and scans only the vectors in those lists. The work per query becomes m centroid comparisons plus the population of n cells, so with m in the thousands and n around ten, the scanned fraction is a few percent of the corpus. The parameters are the number of cells and the number probed; probing more cells raises recall and raises latency almost linearly. The failure mode is boundary cases: a vector just inside a cell boundary has its true neighbours in an adjacent cell, and if that cell is not among the n nearest centroids, the neighbour is unreachable no matter how the rest of the search is tuned.

Graph indexes build a navigable graph in which every vector is a node connected to a set of near neighbours, plus a small number of long-range links. A query starts at an entry point, walks greedily toward the query, and at each step moves to the neighbour closest to the target until no neighbour is closer. The hierarchical variant layers the graph so that the top layer is sparse and covers the space coarsely, and each lower layer is denser, which gives the walk a logarithmic-ish path from a coarse entry to a fine neighbourhood. Search cost is proportional to the number of hops times the degree, and the parameter that controls recall is the size of the candidate list maintained during the walk: a wider beam explores more branches and finds more of the true neighbours. Graph indexes have the best recall-per-distance-computation of the common families on high-dimensional data, and the worst build time and memory profile, because every node stores its adjacency list on top of its vector.

Hash-based indexes map vectors to buckets so that similar vectors collide. Locality-sensitive hashing uses a family of random projections, and the guarantee it provides is a probability statement about collision rather than a bound on distance: two vectors within distance r collide with probability p1, two vectors beyond distance c times r collide with probability p2 less than p1, and repeating the projection with several independent tables amplifies the gap. The method is old, has clean analysis, and adapts poorly to data with clustered structure, where a single bucket can absorb a large fraction of the corpus. It remains useful where inserts are continuous and the index must not be rebuilt.

Quantization as an orthogonal axis

Compression is a separate decision from partitioning, and it composes with all three families. Storing a 768-dimension vector as 768 32-bit floats costs 3,072 bytes; storing it as 768 8-bit integers costs 768 bytes, a factor of four, at the price of a small ranking error. Product quantization goes further: split the vector into subvectors, learn a small codebook per subvector, and store the index of the nearest codeword. With 8-bit codes and 96 subvectors of 8 dimensions each, a vector costs 96 bytes, a factor of 32, and the distance between a query and a stored vector is computed by table lookup over the per-subvector codebooks rather than by arithmetic over the full vector.

The asymmetry matters. Compressed vectors are compared to uncompressed queries by precomputing a lookup table of query-to-codeword distances for each subvector, after which a distance is 96 table reads and additions. That is why the compressed representation is fast as well as small, and why it is often used as a first pass whose candidates are rescored against the full-precision vectors kept on disk. The recall cost of quantization is real and it interacts with the index parameters: a cell that looks far away under compressed distance may be near under exact distance, so the beam must be wider to compensate.

import numpy as np

def pq_distance_table(query, codebooks, m):
    # codebooks[j] has shape (256, d/m); m is the number of subvectors
    sub = len(query) // m
    return [
        ((codebooks[j] - query[j * sub:(j + 1) * sub]) ** 2).sum(axis=1)
        for j in range(m)
    ]

def pq_distance(table, code):
    # code[j] is the codeword index chosen for subvector j
    return sum(table[j][code[j]] for j in range(len(code)))

The table build is O(m x 256 x d/m), which is O(256 x d) and independent of the corpus size: for 96 subvectors of 8 dimensions it is under two hundred thousand operations, negligible against the scan it accelerates.

Recall is measured, not configured

The parameter that a serving system exposes is usually a search-time knob: candidates to examine, cells to probe, or beam width. The relationship between that knob and recall is monotonic and unknown in advance, so it must be measured against the actual corpus.

The measurement requires ground truth, which means an exact scan over a sample of real queries. A few hundred queries against the full corpus produces, for each, the true top k; the index is then run with the same queries and the overlap is computed. This is the only honest way to know what recall the configuration delivers, and it must be repeated whenever the corpus changes substantially, because recall degrades silently as data drifts away from the distribution the index was built around.

Two failure modes make the measurement misleading.

The first is that recall at k is not the metric the pipeline cares about. A retrieval stage that returns 20 candidates to a reranker only needs the relevant chunk somewhere in those 20; whether it was ranked first or fifteenth does not change the final answer. Recall at 20 is therefore the useful figure, and it is typically much higher than recall at 1 for the same index settings. Optimising the wrong one leads to over-provisioned indexes.

The second is that recall measured on a query sample says nothing about queries unlike the sample. A corpus of technical documentation with queries drawn from its own headings will show high recall, because the queries sit close to the documents. The same index receiving queries phrased in a user’s vocabulary, or in a second language, or about a topic the corpus covers thinly, will show lower recall. The index did not change; the query distribution did.

Deletion and update are the weak spot

An index built once from a static corpus can be rebuilt when the corpus changes. An index serving a corpus that changes continuously cannot, and the families differ sharply in how well they tolerate mutation.

Partition-based indexes handle deletion by tombstoning and handle insertion by appending to the nearest cell’s list, which is cheap but unbalances the cells over time; the centroids were chosen for a distribution that no longer holds, and a rebuild is eventually required. Graph indexes handle deletion badly because removing a node breaks the paths that routed through it, and re-linking its neighbours to preserve connectivity is expensive; the usual approach is to mark the node deleted, keep it as a routing waypoint, and exclude it from results, which slowly degrades both memory and path quality. Hash indexes tolerate insertion trivially and deletion by tombstone.

This is the reason many systems run two structures: an immutable, compressed, well-tuned index over the bulk of the corpus, and a small mutable index over recent additions that is merged periodically. The query hits both and the results are merged by score, which means the merge must handle score comparability, a concern shared with the fusion step in Hybrid Lexical and Dense Retrieval. The maintenance side of that arrangement is treated in Incremental Index Maintenance.

What the index cannot do

Three limits are structural rather than tunable.

An index ranks by the metric it was built for. Cosine similarity, inner product, and Euclidean distance induce different neighbourhoods, and an index tuned for one does not answer the others correctly; the normalisation decision has to be settled before the index is built, as covered in Similarity Metrics and Normalisation.

An index cannot recover from a bad embedding. If the encoder places a relevant passage far from every plausible query, no amount of beam width finds it, because the search is faithful to the geometry it was given. Recall measured against exact search will look fine while end-to-end answer quality is poor.

An index has no notion of permission, freshness, or tenant. Those constraints are not geometric, so they cannot be expressed as a distance, and they must be applied either before the search by restricting the candidate set or after it by filtering results and re-searching. Both approaches have costs that are large enough to deserve separate treatment, in Metadata Filtering Inside Vector Search.