A dense retriever turns every passage into a vector and every query into a vector, and answers the query with the passages whose vectors are nearest to it. That leaves a plain computational problem: given $N$ stored vectors in $m$ dimensions and a query vector, find the $k$ nearest. Comparing the query with every stored vector always works and costs $N m$ multiplications. This unit is about doing better than that when $N$ is large, and about knowing when not to try.
The subject has an unusual shape. For vectors of two or three dimensions the problem was solved in the 1970s by trees that find the exact answer in logarithmic expected time. In a hundred dimensions those trees examine nearly every vector, and the best known bounds for exact search with storage near linear in $N$ are in effect no better than a full scan (the first article gives the measurement and the citation). What works in practice is to give up exactness: an approximate nearest neighbor index returns most of the true neighbors, at a small fraction of the cost. The fraction of true neighbors returned is the recall, and every index in this unit is described by the trade it offers between recall and cost.
What the unit assumes
The unit assumes the vector space model of the course, in particular cosine similarity, where the relations between the dot product, the cosine and the Euclidean distance of unit vectors are proved. Similarity measures for embeddings takes those relations further and shows how a search for the largest dot product reduces to a search for the nearest vector, which is why this unit can speak of distances only. K-means is used by two of the indexes, and near-duplicate detection introduced hashing by similarity for sets. Probability at the level of the site's statistics course is enough for the proofs.
One dataset, one measure
All seven articles measure their indexes on the same data, so that the numbers can be compared across the unit.
- The vectors. The 400,000 GloVe word vectors of 100 dimensions trained on Wikipedia and Gigaword (Pennington, Socher, and Manning, 2014), which their authors release under the Public Domain Dedication and License. Every vector is scaled to unit length, so that Euclidean distance, cosine and dot product give the same ranking. One thousand vectors drawn at random are set aside as queries, and the other $N = 399{,}000$ are the stored vectors.
- The truth. The 100 nearest stored vectors of each query, found by a full scan.
- The measure. Recall@$k$ is the share of a query's $k$ true nearest neighbors that appear among the $k$ vectors an index returns, averaged over the 1,000 queries. The headline cutoff is $k = 10$. The first article defines it and relates it to the other measure in the literature, the distance ratio.
- The cost. The number of full $m$-dimensional distance computations per query, which does not depend on the machine, with wall-clock times as a secondary figure. A full scan costs $N$.
- Small real sets. The passages of this site as encoded for the previous unit's experiments, at one commit (the site's own search is lexical and stores no vectors), and the Cranfield abstracts, from the same encoder. They hold about eleven thousand and 1,400 vectors, sizes at which the unit's conclusion is that a full scan is the right index.
Every index is implemented in NumPy from the paper that introduced it (tools/experiments/vectors/). Parts that involve chance (random hyperplanes, k-means starting points, the levels of a graph) are run with 30 seeds and reported as a median with its interquartile range.
What is proved and what is cited
Derived or proved on the pages:
- the distance-concentration theorem of Beyer and colleagues, with an explicit bound for each dimension, and the Johnson–Lindenstrauss lemma;
- the query-time bound of locality-sensitive hashing from the definition of a sensitive family, and the collision probabilities of the two families used;
- that the recall of an inverted file index is the share of true neighbors lying in the probed cells, and the cost model that sets the number of cells;
- the memory arithmetic of product quantization, its asymmetric distance computation, and the bounds that tie the error of an estimated distance to the quantization error;
- for graph indexes, the distribution of levels, the local optimality of the list a search returns, and the geometric convergence of a greedy walk toward a stored point on a fully pruned graph.
Cited, with the paper named: the analysis of k-d trees in a fixed dimension, the logarithmic scaling of graph indexes (an empirical finding with no worst-case guarantee), and every benchmark figure not measured here. Indexes on disk and filtered search are still changing; the article on them names published methods only and dates its claims.
Articles
The problem and the two classical answers:
- Nearest Neighbor Search in High Dimensions: the exact problem and its cost, k-d trees and why they examine nearly everything in 100 dimensions, the concentration of distances, proved, and how far real embeddings are from its limit, recall as the measure of an approximate index, and the Johnson–Lindenstrauss lemma with its proof.
- Locality-Sensitive Hashing: hash functions that collide more often for near vectors than for far ones, the random-hyperplane family, tables of concatenated bits, and the proof that such an index answers an approximate query in time sublinear in $N$; measured, it needs many candidates on this data.
Partitioning and compressing:
- Inverted File Indexes for Vectors: partition the vectors into cells with k-means and compare a query only with the vectors of the few cells nearest to it; the proof that recall is the share of true neighbors in the probed cells, the cost model that puts the number of cells near the square root of the collection size, and recall measured against cells probed.
- Product Quantization: store each vector as a few bytes with one small k-means codebook per sub-vector and compute distances from lookup tables; the error of the estimated distance bounded by the quantization error, an example on eight vectors by hand, the optimized rotation, and the inverted file with compressed lists.
Graphs:
- Hierarchical Navigable Small World Graphs: greedy search on a proximity graph and the local minima that stop it, small-world graphs, the insertion and search algorithms of the index followed line by line on twelve points, what its three parameters do, and the absence of a worst-case guarantee.
Practice:
- Vector Search on Disk and with Filters: a graph index on a solid-state drive and the pruning rule that keeps its walks short, quantization with a loss fitted to dot products, a metadata filter applied before, after or during the search with the regime in which each fails, and deletes and updates.
- Benchmarking Vector Indexes: recall, query cost, build cost and memory as the four axes, operating points and the Pareto frontier, how the public benchmark is run, all of the unit's indexes on the one dataset, and the measured collection size below which a full scan is the right index.
References
- Pennington, J., Socher, R., and Manning, C. D. (2014). GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 1532–1543. record · 5 pages