Vector Search: Exact Search and the Approximate Indexes

Embeddings and Contrastive Learning turned text into vectors whose closeness means similar meaning. Retrieval, the subject of Part IX: Retrieval, starts by finding the stored vectors closest to a query’s vector: nearest-neighbor search. Done exactly, it is one line of linear algebra and costs time in proportion to the number of vectors. Every index built since trades a little accuracy, a few true neighbors missed, for a large saving in that time, and the right trade depends on how many vectors there are, how much memory there is, and how often the data changes.

Table of contents

Similarity, three ways

Three measures are common: the dot product $q \cdot x$, the cosine $\frac{q \cdot x}{\|q\| \|x\|}$, and the Euclidean distance $\|q - x\|$. They usually agree, because embedding models are trained with normalized vectors and their output is normalized before storing. For unit vectors the cosine is the dot product, and

so the smallest distance is the largest dot product: all three rank identically. (The measurement below confirms it on real embeddings, up to ties between duplicate sentences.) Without normalization they don’t: the dot product favors long vectors, which some models use on purpose, so search with the measure the model was trained for.

Exact search, and why trees don’t save it

Exact search computes the query’s similarity to every stored vector: $N \times d$ multiply-adds, 27.6 million for the 71,865 vectors of 384 dimensions below, about 1.8 ms on one CPU core of an Apple M4 laptop (1.776 ms in the run below). That is fast enough for tens of thousands of vectors, and it is always right. Below about a hundred thousand vectors, it is usually the right choice.

For low-dimensional data, k-d trees (Bentley, 1975) cut the work by splitting space into boxes and skipping boxes too far from the query. In high dimensions this stops working, because distances stop telling points apart (Beyer et al., 1999). For random points, the nearest and the farthest neighbor of a query end up nearly equally far away:

import numpy as np

# Why trees fail in high dimensions: for 10,000 random points, the nearest
# and the farthest neighbor of a random query end up almost equally far away.
rng = np.random.default_rng(0)
for dim in (2, 10, 100, 384):
    P = rng.normal(size=(10_000, dim)); q = rng.normal(size=dim)
    dist = np.linalg.norm(P - q, axis=1)
    print(f"random points, {dim:3d} dimensions: nearest / farthest distance = {dist.min() / dist.max():.2f}")

# The real sentence embeddings of the next section (384 dimensions), for
# 200 of the query sentences: median of the same ratio.
X, Q = np.load("docs.npy"), np.load("queries.npy")
r = [np.sqrt(np.maximum(2 - 2 * (X @ q).max(), 0)) / np.sqrt(2 - 2 * (X @ q).min()) for q in Q[:200]]
print(f"real embeddings,   384 dimensions: nearest / farthest distance = {np.median(r):.2f} (median of 200 queries)")

Full script: distances.py

random points,   2 dimensions: nearest / farthest distance = 0.00
random points,  10 dimensions: nearest / farthest distance = 0.19
random points, 100 dimensions: nearest / farthest distance = 0.61
random points, 384 dimensions: nearest / farthest distance = 0.78
real embeddings,   384 dimensions: nearest / farthest distance = 0.63 (median of 200 queries)

At 384 dimensions the nearest random point is 78% as far as the farthest, so almost every box might hold a near neighbor and the tree visits almost all of them. Real embeddings are less uniform: for the sentence embeddings below the ratio is 0.63, like 100-dimensional random data. That structure is why the approximate methods below work at all, but it isn’t enough for exact pruning.

Locality-sensitive hashing

LSH (Indyk and Motwani, 1998) hashes vectors so that close vectors probably share a hash, and looks only in the query’s buckets. For cosine similarity, the hash Charikar (2002) introduced takes random hyperplanes and records which side of each a vector falls on, one bit each: two vectors at angle $\theta$ disagree on each bit with probability $\theta / \pi$. It has clean guarantees, but needs many bits or many tables for good recall, and in practice the data-dependent methods below beat it. (The measurement below uses such bit codes as a 128-byte sketch scanned exhaustively, not as hash tables, so it shows their accuracy, not LSH’s speed.)

IVF: search only the nearby lists

An inverted file index (IVF) runs k-means on the vectors, into 4 to 16 times $\sqrt{N}$ clusters by FAISS’s guideline, and stores each vector in the list of its nearest centroid. A query is compared with the centroids, then searched exhaustively in only the nprobe nearest lists. With 256 lists (about $\sqrt{N}$ here) and 4 probes it scans about 1.6% of the vectors; the measurement also tries 1,024 lists, about $4\sqrt{N}$. A true neighbor is missed when it sits in a list whose centroid wasn’t among the closest few, near a boundary; probing more lists recovers it, at linear cost.

Product quantization: an 8-byte vector, worked

IVF still stores every vector in full: 384 floats, 1,536 bytes. Product quantization (PQ; Jégou et al., 2011) compresses them. Split each vector into $m$ sub-vectors, run k-means with 256 centroids on each sub-space separately, and store each sub-vector as the one-byte index of its nearest centroid. With $m = 8$, a 384-dimensional vector becomes 8 sub-vectors of 48 dimensions and is stored as 8 bytes, 192 times smaller, and the 8 codebooks, $8 \times 256$ centroids of 48 floats, are shared by all vectors.

Distances need no decompression, and the query itself is never quantized (Jégou et al. call this asymmetric distance computation). For a query, compute once the dot product of each of its 8 sub-vectors with each of that sub-space’s 256 centroids: 8 tables of 256 numbers. The approximate similarity to any stored vector is then the sum of 8 table lookups, one per byte of its code. The answer is approximate because each stored sub-vector was replaced by its centroid; the more sub-vectors, the finer the approximation (the measurement uses 48, 48 bytes a vector). PQ is usually combined with IVF (IVF-PQ) for speed, and followed by re-ranking: re-score the best few hundred candidates with the exact vectors, kept on disk or in cheaper memory. ScaNN (Guo et al., 2020) improves the quantization itself: it penalizes the part of each vector’s quantization error parallel to the vector more than the part orthogonal to it, since that is what changes large inner products.

HNSW: a navigable small world

HNSW (hierarchical navigable small world; Malkov and Yashunin, 2016) is a graph. Every vector is a node linked to up to $M$ neighbors on each upper layer and $2M$ on layer 0. Vectors are inserted one at a time, and each new vector’s links are chosen with a heuristic that prefers neighbors in different directions over a tight cluster of near ones, which keeps the graph connected and gives it some long links. To search, start somewhere, move to whichever neighbor is closer to the query, and repeat until no neighbor is closer. On a plain neighbor graph that walk is slow, because it takes many short steps. HNSW adds layers: every node is on layer 0, about one in $M$ also on layer 1, fewer again on layer 2, each layer a sparser graph with longer links. The search starts on the top layer, crosses the space in a few long hops, drops a layer, and refines, like zooming in on a map. On layer 0 it keeps a beam of the ef best candidates rather than just one, which makes it less likely to stop at a point that is only locally nearest.

The widget builds a simplified one over 200 points: each point links to its $M$ nearest, and about one in six reaches each higher layer. Click to move the query; the thick lines are the search’s moves on the upper layers, the thin ones on layer 0. Compare the distances computed with the 200 of brute force. With 2 links per point it misses often, mostly because a plain nearest-neighbor graph that sparse falls apart into islands the search can’t cross, which HNSW’s neighbor heuristic prevents; with 8 it rarely misses:

Measured: recall, speed and memory

All of the above, in FAISS (Johnson et al., 2017), on the sentences of WikiText-2’s training set embedded with Embeddings and Contrastive Learning’s MiniLM, searched with 1,000 sentences from its test set. embed.py embeds both once, on the CPU, and saves them as docs.npy and queries.npy.

Full script: embed.py

Recall@10 is the fraction of the true 10 nearest neighbors an index returns. recall_speed.py first finds the true top 10 by exact search, and checks that L2 distance and the dot product rank these unit vectors the same way. Its measure() queries an index one query at a time, three times, and prints recall, the fastest time per query, and bytes per vector. Then each index is built and measured:

print(f"\n{N:,} vectors, {d} dimensions:")
measure(exact, "flat (exact)", 4 * d)
t0 = time.perf_counter()
ivf = faiss.IndexIVFFlat(faiss.IndexFlatIP(d), d, 256, faiss.METRIC_INNER_PRODUCT); ivf.train(X); ivf.add(X)
print(f"  (IVF, 256 lists: built in {time.perf_counter() - t0:.1f} s)")
measure(ivf, "IVF 256 lists, probe", 4 * d + 8, lambda v: setattr(ivf, "nprobe", v), (1, 4, 16, 64))
# FAISS's guideline is 4 to 16 times sqrt(N) lists; sqrt(71,865) is 268.
ivf4 = faiss.IndexIVFFlat(faiss.IndexFlatIP(d), d, 1024, faiss.METRIC_INNER_PRODUCT); ivf4.train(X); ivf4.add(X)
measure(ivf4, "IVF 1024 lists, probe", 4 * d + 8, lambda v: setattr(ivf4, "nprobe", v), (8, 16, 32, 64))
t0 = time.perf_counter()
pq = faiss.IndexPQ(d, 48, 8, faiss.METRIC_INNER_PRODUCT); pq.train(X); pq.add(X)
print(f"  (PQ, 48 sub-vectors x 8 bits: built in {time.perf_counter() - t0:.1f} s)")
measure(pq, "PQ, 48-byte codes", 48)
ivfpq = faiss.IndexIVFPQ(faiss.IndexFlatIP(d), d, 256, 48, 8, faiss.METRIC_INNER_PRODUCT); ivfpq.train(X); ivfpq.add(X)
measure(ivfpq, "IVF-PQ, probe", 48 + 8, lambda v: setattr(ivfpq, "nprobe", v), (4, 16, 64))
# PQ's recall is capped by its coarse codes; re-scoring the top 100
# candidates with the exact vectors (kept in memory, or on disk) lifts it.
base = faiss.IndexIVFPQ(faiss.IndexFlatIP(d), d, 256, 48, 8, faiss.METRIC_INNER_PRODUCT); base.train(X)
refine = faiss.IndexRefineFlat(base); refine.k_factor = 10; refine.add(X)
measure(refine, "IVF-PQ + re-rank 100, probe", 48 + 8 + 4 * d, lambda v: setattr(base, "nprobe", v), (16, 64))
t0 = time.perf_counter()
hnsw = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT); hnsw.hnsw.efConstruction = 128; hnsw.add(X)
print(f"  (HNSW, M = 32: built in {time.perf_counter() - t0:.1f} s)")
measure(hnsw, "HNSW M=32, efSearch", 4 * d + 2 * 32 * 4, lambda v: setattr(hnsw.hnsw, "efSearch", v), (16, 32, 64, 128))
lsh = faiss.IndexLSH(d, 1024); lsh.add(X)
measure(lsh, "LSH, 1024-bit codes, scanned", 1024 / 8)

Full script: recall_speed.py

L2 vs dot product, 100 queries: same top-10 sets: True; order differs at 4 positions, all between exactly tied scores (duplicate sentences): True

71,865 vectors, 384 dimensions:
flat (exact)                     recall@10  1.000    1.776 ms/query    1536 bytes/vector
  (IVF, 256 lists: built in 0.2 s)
IVF 256 lists, probe, 1          recall@10  0.496    0.018 ms/query    1544 bytes/vector
IVF 256 lists, probe, 4          recall@10  0.812    0.042 ms/query    1544 bytes/vector
IVF 256 lists, probe, 16         recall@10  0.955    0.128 ms/query    1544 bytes/vector
IVF 256 lists, probe, 64         recall@10  0.994    0.468 ms/query    1544 bytes/vector
IVF 1024 lists, probe, 8         recall@10  0.799    0.040 ms/query    1544 bytes/vector
IVF 1024 lists, probe, 16        recall@10  0.886    0.056 ms/query    1544 bytes/vector
IVF 1024 lists, probe, 32        recall@10  0.941    0.088 ms/query    1544 bytes/vector
IVF 1024 lists, probe, 64        recall@10  0.974    0.149 ms/query    1544 bytes/vector
  (PQ, 48 sub-vectors x 8 bits: built in 10.5 s)
PQ, 48-byte codes                recall@10  0.626    0.634 ms/query      48 bytes/vector
IVF-PQ, probe, 4                 recall@10  0.568    0.055 ms/query      56 bytes/vector
IVF-PQ, probe, 16                recall@10  0.604    0.088 ms/query      56 bytes/vector
IVF-PQ, probe, 64                recall@10  0.608    0.212 ms/query      56 bytes/vector
IVF-PQ + re-rank 100, probe, 16  recall@10  0.942    0.105 ms/query    1592 bytes/vector
IVF-PQ + re-rank 100, probe, 64  recall@10  0.969    0.231 ms/query    1592 bytes/vector
  (HNSW, M = 32: built in 19.9 s)
HNSW M=32, efSearch, 16          recall@10  0.876    0.042 ms/query    1792 bytes/vector
HNSW M=32, efSearch, 32          recall@10  0.950    0.065 ms/query    1792 bytes/vector
HNSW M=32, efSearch, 64          recall@10  0.983    0.116 ms/query    1792 bytes/vector
HNSW M=32, efSearch, 128         recall@10  0.994    0.201 ms/query    1792 bytes/vector
LSH, 1024-bit codes, scanned     recall@10  0.631    0.195 ms/query     128 bytes/vector

Read it as a menu of trades. Timings are one query at a time on one core of the same Apple M4 laptop with nothing else running, the fastest of three repeats.

• Exact search: 1.8 ms a query in this run, always right. At 72,000 vectors that is fast enough for most uses; an index starts to pay at hundreds of thousands or millions, or at many queries per second.
• IVF buys speed with the number of lists probed. With 256 lists, 4 probes find 81% of the true top 10 in 0.042 ms, 42 times faster than exact; 16 find 96%; 64 find 99.4%, 3.8 times faster than exact. With 1,024 lists, the guideline’s size, each probe scans less: 94% recall takes 0.088 ms, where 256 lists need 0.128 ms for 96%. Memory is unchanged: it stores every vector in full.
• PQ buys memory: 48 bytes per vector instead of 1,536, 32 times smaller, but at 48 bytes the codes alone cap recall near 61 to 63%, however many lists IVF-PQ probes. Re-ranking its top 100 with the exact vectors lifts it to 94 to 97%, at the cost of keeping those vectors somewhere.
• HNSW reaches 95% at 0.065 ms, 98% at 0.116 ms and 99.4% at 0.201 ms. Against IVF with the guideline’s 1,024 lists it takes about a quarter less time around 95% (0.065 ms against 0.088 ms for 94%), reaches 98% in less time than that IVF takes for 97.4%, and at 99.4% it is 2.3 times as fast as the 256-list IVF that reaches it. Its edge grows with the recall target; how it scales with the number of vectors was not measured here. It costs memory (about 256 bytes of links and bookkeeping per vector), build time (20 seconds, against a fifth of a second for IVF), and, being a graph, it is awkward to delete from.
• Random-hyperplane codes of 1,024 bits reach 63% recall: data-independent hashing loses to methods that learn the data’s structure.

At this scale every method is fast in absolute terms. What the table is for is the shape of the trade, which holds at larger scale: IVF and HNSW trade recall for time, PQ trades recall for memory, and re-ranking buys the recall back.

What a vector database adds

An index answers “nearest vectors to this one”. A vector database wraps it with what an application needs around that:

• Filtering: “nearest, among this user’s documents from this year”. Filtering after the search can leave fewer than $k$ results; filtering before it can break a graph index’s navigation, so databases build filters into the search itself.
• Updates and deletes: IVF and PQ take new vectors easily, but their centroids go stale as the data shifts; HNSW handles inserts, while deletes are tombstoned (marked and skipped) and reclaimed by reusing the slot or rebuilding.
• Persistence, sharding and replication, like any database.
• Hybrid search: combining vector similarity with keyword matching, the subject of Semantic and Hybrid Search.

Where this leads

• Semantic and Hybrid Search adds keyword search, BM25, and fuses the two rankings.
• Reranking and Late Interaction re-ranks the top results with a more expensive model.
• Building RAG builds retrieval-augmented generation on all of it.

Takeaways

• On normalized embeddings, dot product, cosine and Euclidean distance rank identically; use the measure the model was trained with.
• Exact search costs $N \times d$ per query, under 2 ms for 72,000 vectors of 384 dimensions here, and is the right choice until it isn’t fast enough. Trees don’t help in high dimensions: distances concentrate.
• IVF searches only the nearest clusters (94% recall at about 1/20 of exact’s time with 1,024 lists); PQ compresses vectors 32 times but, at 48 bytes, caps recall near 62% until re-ranking with exact vectors (94 to 97%); HNSW navigates a layered graph, ahead of a well-sized IVF at 95% recall and further ahead at the highest recall, at extra memory and build time.
• A vector database adds what an index doesn’t: filtering, updates, persistence and hybrid search.

References

Start with the FAISS paper for the indexes in practice, then Malkov and Yashunin for HNSW and Jégou et al. for product quantization; Beyer et al. is the short classic on why high dimensions defeat exact pruning.

• Beyer, Goldstein, Ramakrishnan and Shaft, When Is “Nearest Neighbor” Meaningful? (ICDT, 1999): distance concentration in high dimensions, the reason trees fail.
• Charikar, Similarity Estimation Techniques from Rounding Algorithms (STOC, 2002): the random-hyperplane hash for cosine similarity, used in the LSH section.
• Bentley, Multidimensional Binary Search Trees Used for Associative Searching (Communications of the ACM, 1975): k-d trees, the exact method that high dimensions defeat.
• Indyk and Motwani, Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality (STOC, 1998): locality-sensitive hashing, the idea behind the LSH section.
• Jégou, Douze and Schmid, Product Quantization for Nearest Neighbor Search (IEEE TPAMI, 2011): product quantization and asymmetric distance computation, as the PQ section uses them.
• Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2016; IEEE TPAMI, 2020): HNSW, the layered navigable small-world graph.
• Johnson, Douze and Jégou, Billion-scale similarity search with GPUs (2017; IEEE Transactions on Big Data, 2021): FAISS, the library every index here is measured with.
• Guo et al., Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ICML, 2020): ScaNN, the anisotropic quantization loss mentioned with PQ.