Vector Similarity Search: Metrics & Approximate Methods › Approximate Nearest Neighbor Search

The main point behind approximate nearest neighbor (ANN) search is that you rarely need the exact nearest neighbors. In most retrieval applications, the downstream task (such as generating an answer from retrieved documents) is reliable to small perturbations in the retrieved set. If the true 3rd-closest document has a similarity of 0.873 and the ANN algorithm returns a document with similarity 0.871 instead, the difference is negligible for downstream generation. The answer produced by the language model will be virtually indistinguishable regardless of which document was included.

By accepting this small accuracy trade-off, ANN algorithms can reduce search time from linear in $n$ to sublinear, often logarithmic or even near-constant. This is a dramatic improvement. Whereas exact search over 100 million vectors might take several seconds, a well-tuned ANN index can return results in a few milliseconds, a speedup of three orders of magnitude. This is what makes real-time retrieval over massive collections feasible.

Every ANN algorithm offers knobs that control this trade-off. Turning the knob toward more accuracy means searching more of the index, examining more candidates, and spending more time verifying potential neighbors. Turning it toward more speed means searching less of the index, examining fewer candidates, and accepting a higher risk of missing relevant results. The art of ANN tuning is finding the sweet spot where recall is high enough (typically 95-99%) while latency meets your application requirements.

This trade-off is not binary: it is a continuous spectrum. For a given index structure, you can choose any operating point along a curve that runs from very fast and low recall to slow and perfect recall. This trade-off is usually visualized as a recall-vs-queries-per-second curve. A well-designed index will have an "elbow" where you get most of the recall for a modest time investment, with diminishing returns beyond that point. The ideal operating point is typically just past this elbow, where you have captured the large majority of relevant neighbors while keeping latency well within your budget.

Understanding this trade-off geometrically helps build intuition. The reason approximate methods can be fast is that they avoid examining regions of the space that are unlikely to contain relevant neighbors. An IVF index, for instance, identifies the cluster whose centroid is closest to the query and then searches only within that cluster. This works because nearby vectors tend to cluster together in the learned embedding space. The approximation error arises when a true nearest neighbor happens to fall in a different cluster, which occurs occasionally near cluster boundaries.

ANN algorithms generally fall into several broad categories, each based on a different strategy for avoiding the exhaustive scan over all vectors. Understanding these families at a conceptual level helps you choose an approach that meets your accuracy target at the required scale on the available hardware.

Tree-Based MethodsLink Copied

Tree-based methods partition the vector space recursively using a tree structure, then search by traversing only the branches of the tree near the query. The canonical example is the KD-tree (k-dimensional tree), which works by choosing one dimension at each level of the tree and splitting vectors by their median value along that dimension. To search, you traverse from the root toward the leaf containing the query, then backtrack to check neighboring branches when necessary.

KD-trees work well in low dimensions (up to around 10-20) but suffer severely from the curse of dimensionality in high-dimensional spaces. In high dimensions, almost every data point is "near" the query in the sense that backtracking is required at nearly every node, causing the search to degenerate toward brute force. The fraction of the space you can prune away shrinks exponentially with dimension.

Random projection trees (and their more sophisticated variant, the randomized KD-tree used in FLANN) address this by choosing split dimensions randomly rather than greedily, which provides better coverage of the vector space. Spotify's Annoy library uses a forest of random projection trees and averages the results across multiple trees to achieve good recall. The key insight is that by building many trees with different random splits, you reduce the probability that a true neighbor falls in an inaccessible region of any single tree.

Locality-Sensitive HashingLink Copied

Locality-Sensitive Hashing (LSH) takes a different approach, mapping nearby vectors to the same hash bucket with high probability and distant vectors to different buckets with high probability. The definition of "nearby" is formalized by the sensitivity of the hash function to the chosen metric.

For cosine similarity, a classic LSH scheme uses random hyperplanes. Each hyperplane divides the space into two half-spaces. A vector is assigned a bit based on which side of the hyperplane it falls on. With $b$ hyperplanes, each vector receives a $b$-bit hash code. Two vectors with high cosine similarity tend to fall on the same side of each hyperplane, creating similar hash codes, while dissimilar vectors tend to disagree on more bits. At query time, you compute the query's hash code and retrieve all vectors from the matching bucket, then compute exact distances among this candidate set.

The challenge with LSH is that a single hash table has limited recall, because some true neighbors inevitably fall in different buckets (false negatives). The standard solution is to use multiple hash tables with different random hyperplanes and take the union of all retrieved candidates. With $L$ tables, a true near neighbor must end up in the wrong bucket in all $L$ tables to be missed, which becomes exponentially unlikely as $L$ increases. However, increasing $L$ also increases both memory usage and query time, creating the familiar speed-recall trade-off. LSH systems typically require $L = 10$-$50$ tables for competitive recall, which makes them memory-intensive relative to graph-based methods.

Graph-Based MethodsLink Copied

Graph-based methods build a proximity graph where each vector is a node and edges connect each vector to its approximate nearest neighbors. To answer a query, you start at some entry point (often a randomly chosen or centrally located vector) and greedily move toward the query by repeatedly choosing the neighbor that is closest to it. This greedy traversal follows a path through the graph from the starting node toward the region of space containing the nearest neighbors.

The key challenge in graph-based search is escaping local minima: the greedy path might get stuck at a node that is locally close to the query but not globally among the nearest neighbors. The solution is to maintain a candidate list during traversal, exploring multiple frontier nodes simultaneously rather than committing to a single greedy path. This beam-search-like approach explores a broader region at the cost of examining more nodes.

HNSW (Hierarchical Navigable Small World) graphs, which we cover in the next chapter, solve the local minimum problem elegantly by building a multi-layer graph structure inspired by skip lists. The top layers of the graph contain long-range connections that enable fast coarse navigation, while the bottom layer contains short-range connections for fine-grained refinement. This hierarchy makes graph-based search efficient even in high dimensions and is currently the dominant ANN algorithm in production systems.

Quantization-Based MethodsLink Copied

Quantization-based methods compress vectors into compact binary or integer codes, then perform search in the compressed space. The extreme version is binary quantization, which replaces each float32 component with a single bit (1 for positive, 0 for negative). This reduces memory by 32x and enables extremely fast Hamming distance computation but sacrifices significant accuracy.

Product Quantization (PQ) is a more principled approach that divides the vector into $m$ equal sub-vectors, learns a small codebook for each sub-vector separately, and represents each sub-vector by the index of its nearest codeword. With $m = 8$ sub-vectors and $256$ codewords each, each vector is compressed from 768 float32 values (3 KB) to 8 bytes, a compression ratio of 384x. Distances can then be computed using precomputed lookup tables rather than full vector arithmetic, dramatically accelerating the comparison step. The PQ approximation introduces error, but for large collections where memory is the bottleneck, this trade-off is often worthwhile.

Inverted File MethodsLink Copied

Inverted file methods partition vectors into clusters using k-means or similar algorithms, then at query time, search only the clusters closest to the query. This is the IVF (Inverted File) approach, directly analogous to the inverted index in keyword search but operating on vector clusters instead of term occurrence lists.

The partitioning step maps each vector to its nearest cluster centroid. At search time, the query is compared against all $K$ centroids to find the $n_{\text{probe}}$ nearest clusters, and then only vectors within those clusters are examined. If $n_{\text{probe}} = 1$ and each cluster contains $n/K$ vectors, the search examines $n/K$ vectors instead of $n$, a $K$-fold speedup. With $n_{\text{probe}} = \sqrt{K}$ (a common heuristic), the search examines $\sqrt{n}$ vectors, achieving $O(\sqrt{n})$ effective cost.

In practice, production systems often combine multiple approaches. FAISS's IVF_PQ index uses inverted file partitioning for coarse navigation, then applies product quantization to compress the vectors within each partition for efficient in-cluster comparison. Understanding the individual building blocks is needed for understanding these combinations.

To compare ANN algorithms and tune their parameters, we need a principled way to measure how close an approximate result is to the true answer. The standard metric for ANN quality is recall@k, which directly measures the overlap between the approximate results and the exact results:

$$\text{recall@}k = \frac{|\text{ANN results} \cap \text{true } k\text{-NN}|}{k}$$

where:

• $\text{ANN results}$: the set of $k$ document identifiers returned by the approximate search
• $\text{true } k\text{-NN}$: the set of $k$ document identifiers returned by an exact (brute-force) search
• $|\dots|$: the cardinality (count) of the intersection between the two sets
• $k$: the number of neighbors requested

The numerator counts how many of the true nearest neighbors appear in the ANN result set. The denominator normalizes by $k$, the total number of neighbors requested, so that the metric always falls between 0 and 1. A recall of 1.0 means the ANN algorithm returned exactly the same set of neighbors as exact search (though possibly in a different order). A recall of 0.0 means it missed every single true neighbor.

To make this concrete with an example: if the true 10 nearest neighbors are documents {A, B, C, D, E, F, G, H, I, J} and your ANN algorithm returns {A, B, C, D, E, F, G, H, K, L}, then $\text{recall@}10 = 8/10 = 0.80$. The algorithm found 8 of the 10 true nearest neighbors, missing I and J while incorrectly including K and L. Note that the documents K and L are not necessarily irrelevant; they are simply not among the true top 10. In most practical scenarios, the documents that ANN returns instead of the missed true neighbors tend to have very similar scores, since the "mistakes" typically involve swapping neighbors that are nearly equidistant from the query.

For RAG applications, $\text{recall@}10$ values above 0.95 are typically sufficient. The reranking stage that follows retrieval (which we will cover later in this part) can further compensate for occasional misses. When evaluating your own system, it is useful to measure recall at multiple values of $k$, because the behavior can differ. An index might have recall@1 of 0.85 (sometimes missing the single best match) but recall@10 of 0.98 (almost always including the true top results when you fetch 10). For RAG, where you typically retrieve 5-20 documents and pass them all to the language model, the recall@k for your actual retrieval size is the most relevant metric.

One subtlety that benchmarks often obscure is that ANN performance depends heavily on the structure of your data. ANN algorithms exploit the fact that real embeddings have natural clustering structure: documents about similar topics cluster together, and queries tend to fall near relevant documents in this clustered space. When this structure is strong, as it is for diverse corpora with well-separated topics, IVF and graph-based methods achieve excellent recall because cluster boundaries rarely separate truly similar documents.

However, when the data is more uniformly distributed (less natural clustering), or when queries fall near cluster boundaries, recall degrades. This is why it is important to benchmark ANN methods on your actual data and query distribution, not just on standard benchmarks. The ANN-Benchmarks suite (ann-benchmarks.com) provides standardized comparisons, but your production recall may differ from these numbers depending on the nature of your documents and queries.