Nearest-neighbour search

Exact k-nearest-neighbour search compares the query with all N stored vectors, costing O(N · d) per query for dimension d. That is fine for tens of thousands of vectors, especially on a GPU, but not for hundreds of millions under a latency budget. Space-partitioning trees such as k-d trees, which work well in two or three dimensions, degrade towards brute force at the several hundred dimensions typical of embeddings, a symptom of the curse of dimensionality. Approximate nearest-neighbour (ANN) methods therefore accept that some true neighbours are missed, and are evaluated by recall@k (the share of the exact top k that the index returns) against queries per second, memory and build time, as in the public ann-benchmarks suite.

Three families dominate. Locality-sensitive hashing (Indyk and Motwani, 1998) hashes vectors so that close ones collide with high probability; it has strong theoretical guarantees but usually needs much memory for high recall. Inverted-file indexes (IVF) cluster the data with k-means into nlist cells and, at query time, scan only the nprobe cells whose centroids are nearest; recall and cost both rise with nprobe. Product quantization (Jégou, Douze and Schmid, 2011) compresses each vector by splitting it into m sub-vectors and replacing each with the index of one of 256 learned centroids, so a vector takes m bytes and distances are computed from lookup tables; IVF-PQ in the FAISS library (Johnson, Douze and Jégou, 2017) scales this to billions of vectors on GPUs.

Graph indexes are the current default in vector databases. HNSW (Malkov and Yashunin, 2018) builds a multi-layer proximity graph: each node links to up to M neighbours (2M on the bottom layer), upper layers are sparse samples that act as express lanes, and search descends greedily from the top layer, keeping a candidate list of size efSearch on the bottom layer. Larger M and efConstruction improve graph quality at the cost of memory and build time; efSearch is the per-query recall/latency dial. HNSW is memory-resident and fast but costly in RAM, so DiskANN (Subramanya et al., 2019), built on the Vamana graph, keeps the graph on SSD with compressed vectors in memory for billion-scale collections.

Most production problems come from filters and churn. Post-filtering, where the index is searched first and metadata or permission conditions are applied afterwards, can return fewer than k results when the filter is selective: pgvector's documentation notes that with the default hnsw.ef_search of 40 and a condition matching 10 % of rows, only about four rows match on average, which is why pgvector 0.8.0 (November 2024) added iterative index scans. Pre-filtering can break graph connectivity or fall back to brute force. Deletions in graph indexes are usually tombstones that degrade recall until the index is compacted or rebuilt, and recall should be monitored in production against an exact search on a sample of queries rather than assumed from benchmarks.