Vector Search — Exact and Approximate Nearest Neighbours

The complexity of exact search, why tree methods fail in high dimension, and the mathematics of LSH, IVF, product quantisation and HNSW.

RAGGraduate⏱ 1 day11 min readannnearest neighbour searchlshivfproduct quantisation

6 problems →

AssumesEmbedding Geometry and Similarity · Nearest Neighbours and the Curse of Dimensionality

Exact search

PropositionCost of exact nearest-neighbour search

For $N$ vectors in $\R^d$ , brute-force search costs $O(Nd)$ time per query and $O(Nd)$ space, with no preprocessing. Every known data structure achieving query time $o(N)$ for exact nearest neighbour in the worst case uses space exponential in $d$ or is no better than brute force once $d = \Omega(\log N)$ .

PropositionWhy space-partitioning trees fail in high dimension

Consider a $k$ -d tree or any partition of $\R^d$ into cells, with pruning based on the rule "skip a cell whose bounding box is farther than the current best distance $r$ ". If the data is i.i.d. with independent coordinates, then by distance concentration all $N$ distances lie in a window of width $O(\sqrt{\log N})$ around $\sqrt{2d}$ , so

\frac{r}{\text{typical distance}} \to 1 ,

and the ball of radius $r$ around the query intersects essentially every cell. Pruning eliminates nothing and the search degenerates to brute force.

Key idea

This is the sharpest form of the curse of dimensionality for search: it is not that trees are slow, it is that the pruning criterion becomes vacuous. Once exact search is hopeless, the only way forward is to relax the problem, and every method below relaxes it in one of two ways: return an approximately-nearest neighbour ( $c$ -ANN), or return the true nearest neighbour with probability less than one.

Locality-sensitive hashing

DefinitionLocality-sensitive hash family

A family $\mathcal{H}$ of hash functions is $(r, cr, p_1, p_2)$ -sensitive for a distance $\rho$ if for $h$ drawn uniformly from $\mathcal{H}$ ,

\rho(u,v)\le r \implies \P\big(h(u)=h(v)\big)\ge p_1, \qquad \rho(u,v)\ge cr \implies \P\big(h(u)=h(v)\big)\le p_2,

with $p_1>p_2$ . The exponent is $\varrho = \dfrac{\log(1/p_1)}{\log(1/p_2)} \in (0,1)$ .

TheoremRandom-hyperplane LSH collision probability

Let $h_w(u) = \sign\ip wu$ for $w\sim\Ncal(0,I_d)$ . Then for any non-zero $u,v$ ,

\P\big(h_w(u)\ne h_w(v)\big) = \frac{\theta(u,v)}{\pi}, \qquad \theta(u,v) = \arccos\frac{\ip uv}{\norm u\norm v} .

Key idea

The collision probability is $1 - \theta/\pi$ , a monotone function of the angle. Combined with the cosine geometry, that makes SimHash the natural LSH family for cosine retrieval: it hashes by direction only, which is exactly what cosine similarity measures. A single bit costs one inner product, and $b$ bits give a $b$ -bit sketch whose Hamming distance estimates the angle unbiasedly with variance $O(1/b)$ .

PropositionAND/OR amplification and the LSH exponent

Concatenate $k$ independent hashes into $g = (h_1,\dots,h_k)$ (an AND, requiring all to match) and build $L$ independent tables (an OR, accepting a match in any). Then

a near pair collides in a given table with probability $p_1^k$ , hence in some table with probability $1-(1-p_1^k)^L$ ;
a far pair collides in a given table with probability $p_2^k$ , so the expected number of far candidates examined is $LNp_2^k$ .

Choosing $k = \log_{1/p_2}N$ and $L = N^{\varrho}$ with $\varrho = \log(1/p_1)/\log(1/p_2)$ gives query time $\tilde O(N^\varrho)$ and constant success probability, with space $\tilde O(N^{1+\varrho})$ .

IVF and product quantisation

DefinitionInverted file index (IVF)

Cluster the $N$ vectors into $n_{\text{list}}$ Voronoi cells by $k$ -means. At query time, compute distances to the $n_{\text{list}}$ centroids, select the $n_{\text{probe}}$ nearest cells, and search only those. Expected cost per query:

O\!\left(n_{\text{list}}d + \frac{n_{\text{probe}}}{n_{\text{list}}}Nd\right),

minimised over $n_{\text{list}}$ at $n_{\text{list}}\asymp\sqrt{N n_{\text{probe}}}$ , giving $O(\sqrt{Nn_{\text{probe}}}\,d)$ .

PropositionProduct quantisation error and compression

Split $x\in\R^d$ into $m$ contiguous sub-vectors of dimension $d/m$ and quantise each with its own codebook of $2^b$ centroids. Then

storage is $mb$ bits per vector, independent of $d$ — for $m=8$ , $b=8$ that is $8$ bytes, a $384\times$ compression of a $768$ -dimensional float32 vector;
the squared error decomposes as $\norm{x-\hat x}_2^2 = \sum_{j=1}^m\norm{x^{(j)} - \hat x^{(j)}}_2^2$ ;
the codebook has $m2^b$ centroids representing $2^{mb}$ distinct quantised points.

Key idea

Product quantisation gets $2^{mb}$ representable points from $m2^b$ stored ones. At $m=8,b=8$ that is $2^{64}$ points from $2048$ centroids. And asymmetric distance computation — quantising only the database, keeping the query exact — lets the distance to every code be read from $m$ precomputed lookup tables of $2^b$ entries, so a distance evaluation is $m$ table lookups and additions rather than $d$ multiplications. That is the actual source of the speedup; the compression is what makes the index fit in memory.

HNSW

DefinitionHierarchical navigable small world graph

Build a multi-layer proximity graph. Each vector is inserted at a random level $\ell\sim\lfloor-\log U/\log M\rfloor$ ; at each level it is connected to its approximate $M$ nearest neighbours among nodes present at that level. Search starts at the top (sparsest) layer, greedily descends to the closest node, then drops a layer and repeats, finishing with a best-first search at layer $0$ maintaining a candidate list of size $\mathrm{efSearch}$ .

Empirical observationHNSW has no worst-case guarantee

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

HNSW is the default index in most production vector databases and dominates ANN benchmarks at high recall. It has no proof of its recall or query complexity on general data.

What this does not say

The heuristic justification is the small-world argument: a graph with short-range links (for accuracy) and long-range links (for navigation) has $O(\log N)$ greedy routing, by analogy with Kleinberg's navigable small-world results. That analogy is not a proof for HNSW: Kleinberg's theorems are about specific lattice-plus-power-law-link constructions, and HNSW's links come from the data's own geometry.

What is actually known:

No recall guarantee. There is no bound of the form "HNSW with parameters $(M,\mathrm{efSearch})$ achieves recall $\ge1-\delta$ ", for any nontrivial data assumption.
Adversarial failure is possible and observed. Greedy graph search can get trapped in a local minimum of the distance function; clustered data with a query between clusters is a realistic hard case.
Construction is $O(N\log N)$ empirically, not provably, and is expensive in absolute terms; the index is also awkward to update and delete from.
LSH has guarantees but loses on benchmarks. This is the honest tension: the method with theory is not the method people use, and the method people use has no theory.

So recall is measured, not proved, and measured on the specific corpus and query distribution. A recall figure from a public benchmark does not transfer to a different corpus.

PropositionRecall composes multiplicatively through a pipeline

Let a retrieval pipeline consist of stages with recall $\gamma_1,\dots,\gamma_m$ — where $\gamma_i$ is the probability that stage $i$ passes on the relevant document given that it received it. Then the end-to-end recall is $\prod_i\gamma_i$ , and in particular is at most $\min_i\gamma_i$ .

Key idea

This is the most consequential and most ignored fact about RAG system design. A cross-encoder reranker cannot recover a document the ANN index did not return: if the index has recall $0.9$ , the system's ceiling is $0.9$ however good the reranker is. Tuning the reranker while the index silently drops $10\%$ of relevant documents is effort spent on the wrong stage.

The same multiplicative structure propagates into generation, quantified on the latent-variable page: retrieval failure is not a soft degradation but a hard ceiling on the information available to the model.

Comparison

Method	Query time	Space	Guarantee	Metric
Brute force	$O(Nd)$	$O(Nd)$	exact	any
LSH (SimHash)	$\tilde O(N^{\varrho})$	$\tilde O(N^{1+\varrho})$	$c$ -ANN with probability	cosine
IVF	$O(\sqrt{Nn_{\text{probe}}}d)$	$O(Nd)$	none	$\ell^2$ , inner product
IVF + PQ	as IVF, smaller constant	$O(Nmb/8)$ bytes	none	$\ell^2$ , inner product
HNSW	$O(\log N)$ empirical	$O(NM)$ links $+ O(Nd)$	none	$\ell^2$ , cosine, inner product

Problems

Why space-partitioning trees fail in high dimensionProof · Advanced · 30 min The random-hyperplane collision probabilityProof · Intermediate · 30 min The LSH amplification exponentProof · Graduate · 1 hour Product quantisation budget arithmeticNumerical · Beginner · 30 min Recall composes multiplicativelyNumerical · Beginner · 15 min Implement SimHash LSH and measure recallCoding · Advanced · 3 hours

References

PaperPiotr Indyk and Rajeev Motwani (1998). Approximate Nearest Neighbors — Towards Removing the Curse of Dimensionality
PaperMoses S. Charikar (2002). Similarity Estimation Techniques from Rounding Algorithms
PaperHervé Jégou, Matthijs Douze and Cordelia Schmid (2011). Product Quantization for Nearest Neighbor Search
PaperYury A. Malkov and Dmitry A. Yashunin (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
SurveyAlexandr Andoni, Piotr Indyk and Ilya Razenshteyn (2018). Approximate Nearest Neighbor Search in High Dimensions

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionCost of exact nearest-neighbour searchproof includedBrute force is N d per query with no preprocessing; no known method achieves both sublinear query time and subexponential space in high dimension.
PropositionWhy space-partitioning trees fail in high dimensionproof includedPruning requires the query ball to miss most cells, and concentration of distances makes that impossible once the dimension exceeds log of the number of points.
DefinitionLocality-sensitive hash familyA hash family whose collision probability decreases with distance, with a gap parameter that determines the achievable exponent.
TheoremRandom-hyperplane LSH collision probabilityproof includedThe probability that a random hyperplane separates two vectors is their angle divided by pi.
PropositionAND/OR amplification and the LSH exponentproof includedConcatenating k hashes and using L tables turns the collision gap into a sublinear query exponent.
PropositionProduct quantisation error and compressionproof includedSplitting the vector into m subspaces with 256 centroids each gives m bytes per vector and an error that is the sum of subspace quantisation errors.
Empirical observationHNSW has no worst-case guaranteeThe dominant ANN index in practice is justified by benchmarks and a small-world heuristic, not by a theorem about its recall.
PropositionRecall composes multiplicatively through a pipelineproof includedA retrieval stage's recall bounds everything downstream, so a 0.9-recall index caps the whole system at 0.9 regardless of the reranker.

Problems (6)

All problems

Papers that use this mathematics

Dense Passage Retrieval for Open-Domain Question Answering
Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, Wen-tau Yih · 2020