High dimension: exactness becomes unaffordable

Why must nearest-neighbor search in high dimension be approximate, and which three approximations can you buy?

The criterion does not degrade gracefully with dimension. It collapses

Two things happen at once as the dimension d grows.

1. Distances concentrate. For many distributions the ratio of the farthest to the nearest neighbor approaches 1. "Nearest" carries less and less information, and the query ball that contains the true k nearest neighbors grows to cover most of the space.
2. Bounding regions become useless. To guarantee exactness, an index must visit every partition whose lower-bound distance could beat the current best. When all the bounds are nearly equal, that is every partition.

So the run count reaches N. The index becomes a scan, plus a large auxiliary structure you are also paying to maintain. Exact nearest-neighbor search in high dimension is not slow because implementations are poor. It is slow because there is nothing left to prune. This is the curse of dimensionality: past some d, all distances concentrate, and high-dimensional indexes are approximate by necessity, not by laziness. (The argument, stated carefully, and why ANN still works on real embeddings are on why exact indexes fail.)

Given approximation, the design space reorganizes around three things you can approximate. Here the concern is what the map costs to build and keep, not how good the returned neighbors are.

Approximate the traversal: graph methods (HNSW)

Build a navigable graph (each vector linked to some near neighbors) and greedily walk toward the query. For the map's upkeep this is the expensive family: construction is a search per inserted vector, the adjacency lists alone run to gigabytes at 10⁷ vectors, and a deleted node cannot be removed without risking disconnection, so it is tombstoned and the graph is rebuilt periodically: an entry that cannot be updated in place gets a mask and a collector. The family is laid out in the three ANN families.

Approximate the partition selection: inverted-file methods (IVF)

Cluster the vectors, index by cluster centroid (the cluster's center), and at query time search only the nprobe nearest cells out of nlist total. Scan volume is N × nprobe / nlist. Build cost is one clustering pass.

The balance has a clean derivation. Query cost is roughly

cost(nlist) = nlist  +  N · nprobe / nlist
              (compare to centroids)  (compare to vectors in probed cells)

Minimizing over nlist (the two terms are equal at the minimum) gives nlist ≈ √(N · nprobe). The folk rule nlist ≈ √N is that formula with nprobe = 1.

Note the shape: this is exactly the two-level sparse index of Index anatomy, with centroids as the sparse summary and cells as the blocks. The novelty is that the "blocks" are defined by clustering rather than by sort order, because no sort order exists.

Approximate the vectors themselves: quantization

Split each vector into subvectors and replace each with an index into a codebook (a table of representative sub-vectors). This is product quantization (PQ). A 768-dimensional float32 vector is 768 × 4 = 3,072 bytes. With 96 subvectors at 8 bits (1 byte) each, it is 96 bytes: a 32× reduction. The usual framing, "it makes distance computation faster", is the less important half.

The important half is the memory cliff from Why indexes exist. An index that does not fit in memory has a fundamentally different cost function from one that does, and the transition is a step, not a slope. Quantization's primary function is to move an index back across that threshold. 100 million 768-dimensional vectors are 100,000,000 × 3,072 B ≈ 300 GB raw and about 10 GB quantized. Those two numbers describe different machines, different architectures and different cost structures, not the same system at different speeds. The recall loss (the share of true neighbors that the search misses) is being traded against the memory cliff rather than against latency, which is the trade that decides whether the system is buildable.