Vector search at scale
A retrieval system turns every document, image or video frame into a vector, and then must find the closest vectors to a query among millions or billions, in a few milliseconds. This session shows why exact search is too slow and too big at that scale, and how three ideas fix it: clusters (IVF), compression (PQ) and graphs (HNSW). We do the memory and speed math, measure the recall versus latency trade-off, and end with FAISS on CPU and GPU, filters and updates.
What you will learn
- Exact k-nearest-neighbor search: inner product, cosine and L2, why it is one matrix multiply, and what it costs in memory and time
- Approximate nearest neighbor (ANN) search and its one quality number, recall@k
- IVF: cluster the database with k-means, search only nprobe lists, and choose nlist from the cost formula
- Product quantization: store each vector in a few bytes, and score it with table lookups (asymmetric distance computation)
- HNSW: a layered small-world graph, greedy search from the top, and the parameters M, efConstruction and efSearch
- Memory and speed math for 100 million vectors, and how to read a recall versus latency curve
- FAISS index strings, CPU vs GPU, metadata filters, adds, deletes and re-training
Why this matters
In session 150 we turned text into vectors and found the best documents by comparing a query vector with every document vector. That works for ten thousand documents. A real company has one hundred million documents, a photo app has billions of images, and a video platform has one vector for every second of every video. Comparing with all of them for every query is too slow and needs too much memory.
Vector search is the job of finding the \(k\) stored vectors closest to a query vector. At scale we accept a small loss of quality to win a large gain in speed and memory: we find most of the true nearest neighbors, not always all of them. This is called approximate nearest neighbor (ANN) search. Every retrieval-augmented generation (RAG) system (session 152), every image and video search engine, every recommendation system and every duplicate detector has an ANN index inside it.
Three ideas carry almost all of the field, and this session builds each one by hand:
- IVF (inverted file): cluster the vectors, and at query time look only inside the few clusters closest to the query.
- PQ (product quantization): compress each vector from thousands of bytes to a few dozen bytes, and compute distances on the compressed codes.
- HNSW (hierarchical navigable small world): link the vectors into a graph and walk the graph toward the query.
The tools are mature. FAISS, the library from Meta, implements all three ideas on CPU and GPU [Certain]. Vector databases (Milvus, Qdrant, Weaviate, pgvector, Elasticsearch and others) wrap the same algorithms with storage, filters and replication. [Likely] If you understand IVF, PQ and HNSW, you can read the settings of any of them.
Exact search and what it costs
We have \(N\) database vectors \(\mathbf{x}_1, \dots, \mathbf{x}_N \in \R^d\) and a query \(\mathbf{q} \in \R^d\). A similarity \(s(\mathbf{q}, \mathbf{x})\) says how close two vectors are (larger means closer). The exact k-nearest-neighbor (kNN) answer is the set of the \(k\) indices with the largest similarity:
Three similarities are common. Inner product \(\mathbf{q}^\top \mathbf{x}\). Cosine \(\mathbf{q}^\top \mathbf{x} / (\lVert \mathbf{q} \rVert \lVert \mathbf{x} \rVert)\). Negative L2 distance \(-\lVert \mathbf{q} - \mathbf{x} \rVert\). They are closely related:
- Read the symbols
- \(\mathbf{q}, \mathbf{x}\)
- the query vector and one database vector, both with \(d\) numbers
- \(\lVert \cdot \rVert\)
- the length (L2 norm) of a vector
- \(\mathbf{q}^\top \mathbf{x}\)
- the inner product: multiply the numbers pairwise and add them up
If all vectors are normalized to length 1, then \(\lVert \mathbf{q} - \mathbf{x} \rVert^2 = 2 - 2\,\mathbf{q}^\top \mathbf{x}\), and the three similarities give the same ranking. That is why most text-embedding pipelines normalize once and then use inner product everywhere. [Certain]
Exact search is one matrix multiply
Put the database in a matrix \(X \in \R^{N \times d}\) and a batch of \(B\) queries in \(Q \in \R^{B \times d}\). All similarities at once are \(S = Q X^\top \in \R^{B \times N}\), followed by a top-\(k\) per row. On a GPU this is a large matrix multiply, the operation GPUs do best (session 126). FAISS calls this a flat index: no structure, just the raw vectors.
The cost has two parts. The work is \(N d\) multiply-adds per query. The memory traffic is reading all \(N d\) numbers. For one query at a time, reading memory is the bottleneck, so the time is about
- Read the symbols
- \(N, d\)
- number of stored vectors and their dimension
- \(b\)
- bytes per number: 4 for FP32, 2 for FP16, 1 for INT8
- \(\text{BW}\)
- memory bandwidth in bytes per second
A batch of \(B\) queries reads the database once and reuses it \(B\) times, so batching makes exact search compute-bound and much cheaper per query. This is the same reuse argument as for decode in LLM serving (session 42).
Take \(N = 10^8\) vectors with \(d = 768\) in FP32. Storage: \(10^8 \times 768 \times 4 = 307.2\) GB. In FP16 it is 153.6 GB. Neither fits in one 80 GB GPU.
One query needs \(10^8 \times 768 = 7.68 \times 10^{10}\) multiply-adds. If it reads the FP32 data at the 3.35 TB/s of an H100 (if the data could fit there), formula (151.3) gives \(307.2 / 3350 \approx 0.092\) s, so 92 ms. On a CPU server, assume about 100 GB/s: 3.07 s per query. A search engine needs a few milliseconds. We need to look at fewer vectors, store fewer bytes per vector, or both.
Exact search is still the right choice more often than people think. Below a few million vectors, or with large query batches on a GPU, a flat index is simple, has perfect recall, and is fast enough. [Likely] It is also always needed to compute the ground truth that you measure every ANN index against.
Approximate search and recall@k
An ANN index returns a set \(\mathcal{A}_k(\mathbf{q})\) of \(k\) results that may differ from the true set \(\mathcal{N}_k(\mathbf{q})\). Its quality is measured by recall@k: the fraction of the true \(k\) nearest neighbors that the index found, averaged over many test queries:
- Read the symbols
- \(\mathcal{Q}\)
- a set of test queries (a few hundred to a few thousand)
- \(\mathcal{A}_k, \mathcal{N}_k\)
- the approximate answer and the exact answer, each with \(k\) items
- \(|\cdot \cap \cdot|\)
- how many items the two sets share
Note that this recall is about the index, not about relevance. In session 150, recall@k compared the results with human labels. Here we compare with what exact search would return. A perfect index (recall 1.0) still returns wrong documents if the embedding model is bad. In practice, an ANN recall of 0.9 to 0.95 costs little end-to-end quality, because a reranker or the LLM sees the top results anyway. [Likely] Measure it on your own data.
Why not use a tree, like a k-d tree, to search exactly but fast? In 2 or 3 dimensions trees work very well. In hundreds of dimensions they do not: almost every branch can contain a near neighbor, so the tree ends up visiting most of the data. This is part of the curse of dimensionality. [Certain] ANN methods give up exactness and gain speed.
IVF: search only the nearby clusters
Training. Run k-means on (a sample of) the database to get \(n_{\text{list}}\) centroids \(\mathbf{c}_1, \dots, \mathbf{c}_{n_\text{list}}\). The centroids are called the coarse quantizer. Adding. Put each vector into the list of its nearest centroid. Each list is an inverted list (the name comes from text search, where a word points to the list of documents that contain it). Searching. Compare the query with all centroids, open the \(n_{\text{probe}}\) closest lists, and search exactly inside them.
The cost of one query in multiply-adds, if lists have about equal size:
- Read the symbols
- \(n_{\text{list}}\)
- number of clusters (inverted lists)
- \(n_{\text{probe}}\)
- number of lists opened per query; the main speed/recall knob
- \(N / n_{\text{list}}\)
- the average number of vectors in one list
The first term grows with \(n_\text{list}\), the second shrinks. Setting the derivative to zero gives the best number of lists and the smallest cost:
So the cost grows with \(\sqrt{N}\), not with \(N\). The FAISS guidelines recommend \(n_\text{list}\) between \(4\sqrt{N}\) and \(16\sqrt{N}\), and between \(30\) and \(256\) training vectors per centroid for k-means. [Certain] (More lists than the formula's optimum is fine, because the centroid search can itself be made fast, for example with a small HNSW over the centroids.)
The weakness of IVF is the border problem. The true nearest neighbor of a query near the edge of a cell often lives in the cell next door. With \(n_\text{probe} = 1\) it is missed. Try it in Figure 1: put the query on a border between two clusters.
- search(\(\mathbf{q}, k = 10, n_\text{probe}\)):
- \(d_j \leftarrow \lVert \mathbf{q} - \mathbf{c}_j \rVert\) for all \(n_\text{list}\) centroids // \(n_\text{list} \cdot d\) work
- \(P \leftarrow\) the \(n_\text{probe}\) centroids with the smallest \(d_j\)
- \(H \leftarrow\) empty top-\(k\) heap
- for \(j \in P\), for \(\mathbf{x}_i \in L_j\): push \((\lVert \mathbf{q} - \mathbf{x}_i \rVert, i)\) into \(H\), keep the best \(k\)
- return \(H\) // recall@10 by (151.4)
How to read Figure 1
Press Play or Step to run the search one line of the algorithm at a time: first the query is compared with every centroid (dashed lines), then the \(n_\text{probe}\) closest cells are chosen, then each chosen list is scanned in turn (the brighter cell) while the heap \(H\) (green dots) keeps the 10 closest points seen so far. The last step draws rings on the true top-10. Click or tap anywhere to move the query; the figure jumps to the final step, and Reset goes back to the start. The live panel counts the work (centroid comparisons plus scanned points) and the recall@10. Start with \(n_\text{probe} = 1\) and put the query near the line between two cells: red rings appear, because some true neighbors sit in the next cell. Raise \(n_\text{probe}\) to 2 or 3 and they turn green, at the price of scanning more points. Then change \(n_\text{list}\): more lists means smaller cells, so each opened cell is cheaper, but you need a larger \(n_\text{probe}\) for the same recall. Two dimensions are kind to IVF; in hundreds of dimensions most points are near some border, which is why real systems use \(n_\text{probe}\) of 16 to 128. [Likely]
\(\sqrt{N} = 10{,}000\), so the guideline range is 40,000 to 160,000 lists. Take \(n_\text{list} = 65{,}536\) (\(= 2^{16}\), which is \(6.55\sqrt{N}\)). Training needs at least \(30 \times 65{,}536 \approx 2.0\) million sample vectors.
With \(n_\text{probe} = 64\), a query scans \(64 / 65{,}536 = 0.098\%\) of the data, about 97,656 vectors, plus 65,536 centroid comparisons. Total work by formula (151.5): \(1.25 \times 10^8\) multiply-adds instead of \(7.68 \times 10^{10}\), about 613 times less. Memory does not shrink: IVF-Flat still stores every full vector (307.2 GB), plus an 8-byte id per vector.
- train(sample \(S\)): \(\{\mathbf{c}_j\} \leftarrow\) k-means\((S, n_\text{list})\) // 30 to 256 sample vectors per centroid
- add(\(\mathbf{x}_i\), id \(i\)): \(j \leftarrow \argmax_j s(\mathbf{x}_i, \mathbf{c}_j)\); append \((i, \mathbf{x}_i)\) to list \(L_j\)
- search(\(\mathbf{q}, k, n_\text{probe}\)):
- \(P \leftarrow\) the \(n_\text{probe}\) centroids with the largest \(s(\mathbf{q}, \mathbf{c}_j)\) // \(n_\text{list} \cdot d\) work
- \(H \leftarrow\) empty top-\(k\) heap
- for \(j \in P\), for \((i, \mathbf{x}) \in L_j\): push \((s(\mathbf{q}, \mathbf{x}), i)\) into \(H\), keep only the best \(k\)
- return the ids in \(H\), best first
PQ: store each vector in a few bytes
IVF reduces the work but not the memory. Product quantization (Jégou et al., 2011) reduces the memory. The idea: split each vector into \(M\) short sub-vectors of \(d/M\) numbers. For each of the \(M\) positions, learn a small codebook of \(K\) centroids with k-means (usually \(K = 256\)). Replace each sub-vector by the index of its nearest centroid. With \(K = 256\), each index fits in one byte:
- Read the symbols
- \(M\)
- number of sub-vectors (sub-spaces); each has \(d/M\) dimensions
- \(K\)
- centroids per codebook; \(K = 256\) gives 8 bits per sub-vector
- \(\mathbf{c}^{m}_{j}\)
- centroid number \(j\) of codebook \(m\)
- \(i_m\)
- the stored code: which centroid is closest to sub-vector \(m\)
Why “product”? The \(M\) codebooks together describe \(K^M\) different vectors (with \(M = 96\) and \(K = 256\), that is \(256^{96}\)), but we only store and train \(M \times K\) small centroids. A single k-means with that many centroids would be impossible.
Distances on codes: asymmetric distance computation
At search time we do not decompress the database. The query stays exact (not quantized; this is why it is called asymmetric). For each sub-space \(m\), we compute the score of the query's sub-vector \(\mathbf{q}^m\) with all \(K\) centroids once, and store them in a table \(T_m\). Then the score of any stored vector is a sum of \(M\) table lookups:
Building the tables costs \(M \cdot K \cdot (d/M) = K d\) multiply-adds per query, the same as comparing with only \(K\) full vectors. After that, each database vector costs \(M\) lookups instead of \(d\) multiply-adds. For L2 distance it works the same way, with squared distances in the tables. FAISS also has a fast-scan variant with \(K = 16\) (4 bits), where the tables fit in CPU vector registers. [Certain]
Tiny case: \(d = 4\), \(M = 2\), \(K = 2\). Codebook 1 has \(\mathbf{c}^1_0 = (1, 1)\) and \(\mathbf{c}^1_1 = (0, 2)\). Codebook 2 has \(\mathbf{c}^2_0 = (0, 1)\) and \(\mathbf{c}^2_1 = (1, 0)\). The stored vector \(\mathbf{x} = (0.8, 1.3, 0.9, 0.2)\) is encoded as codes \((0, 1)\): \((0.8, 1.3)\) is closest to \((1, 1)\), and \((0.9, 0.2)\) is closest to \((1, 0)\).
Query \(\mathbf{q} = (1, 0, 0.5, 2)\). Tables: \(T_1 = [\,1 \cdot 1 + 0 \cdot 1,\; 0\,] = [1, 0]\) and \(T_2 = [\,0.5 \cdot 0 + 2 \cdot 1,\; 0.5 \cdot 1 + 2 \cdot 0\,] = [2, 0.5]\). Score: \(T_1[0] + T_2[1] = 1 + 0.5 = 1.5\). The exact score is \(\mathbf{q}^\top\mathbf{x} = 0.8 + 0 + 0.45 + 0.4 = 1.65\). The error comes from the compression.
At scale: \(d = 768\) with \(M = 96\) gives 96 bytes per vector instead of 3,072 (FP32), a factor of 32. For \(10^8\) vectors: 9.6 GB of codes plus 0.8 GB of 8-byte ids, small enough for one GPU or one server. The tables have \(96 \times 256 = 24{,}576\) entries and cost \(256 \times 768 = 196{,}608\) multiply-adds to build.
Figure 2 runs the whole PQ pipeline in your browser on 240 database vectors with \(d = 8\) and \(M = 4\), so each sub-vector has only 2 numbers and each codebook can be drawn as a small map. It trains the codebooks, encodes one vector, fills the tables (151.8) for a query, and scores every code by lookups.
- train: for \(m = 1..M\): \(\{\mathbf{c}^m_j\}_{j=1}^{K} \leftarrow\) k-means(sub-vectors \(m\), \(K\))
- encode \(\mathbf{x}\): \(i_m \leftarrow \argmin_j \lVert \mathbf{x}^m - \mathbf{c}^m_j \rVert^2\) for each \(m\)
- store \((i_1, \dots, i_M)\): \(M \log_2 K\) bits // (151.7)
- query: \(T_m[j] \leftarrow (\mathbf{q}^m)^\top \mathbf{c}^m_j\) for all \(m, j\) // \(K d\) work, once
- score each code: \(s(\mathbf{x}) \leftarrow \sum_m T_m[i_m]\) // (151.8), \(M\) lookups
- return the top-\(k\) by \(s\); re-rank with exact vectors if needed
How to read Figure 2
Press Play or Step. Steps 2 to 5 encode \(\mathbf{x}\): in each map the orange dot (the sub-vector) is linked to its nearest cross, and that cross's number becomes one code \(i_m\). Steps 7 to 10 fill one table row each: the blue star is the query's sub-vector, and each cell is its inner product with one centroid. Step 11 adds four table cells and compares the sum with the exact inner product; step 12 scores all 240 codes and checks the top-5 against exact search. With \(K = 8\) and the first query, \(\mathbf{x}\) is vector #155 with code [5, 8, 7, 2]; its PQ score is 4.29 while the exact inner product is 5.43. The nearest neighbor of a query often lies far out in the query's direction, and every centroid sits nearer the middle of its cluster, so the sum comes out too small: \(\mathbf{x}\) drops to rank 2 and recall@5 is 0.8. With \(K = 4\) recall@5 is 0.6; with \(K = 16\) it is 1.0, yet \(\mathbf{x}\) is only ranked 3rd: the top-5 set is right but the order is not, which is why re-ranking with exact vectors matters. Switch \(K\) to see the trade-off: more centroids cost more bits but give smaller errors. Press “Next query” for another query.
IVF-PQ and re-ranking
The standard billion-scale index combines both ideas: IVF-PQ. IVF chooses the lists. Inside the lists, vectors are stored as PQ codes. Usually PQ encodes the residual \(\mathbf{x} - \mathbf{c}_j\) (the vector minus its IVF centroid), which is smaller and easier to compress than \(\mathbf{x}\) itself. [Certain]
PQ scores are approximate, so the top-10 by PQ score are often not the true top-10. The fix is re-ranking (FAISS calls it refine): take the top \(k' \gg k\) by PQ score (for example \(k' = 10k\)), load their full vectors (from RAM, SSD, or a cheaper FP16 copy), compute exact scores, and keep the best \(k\). Compression decides which candidates you keep; the exact vectors decide the final order.
- input: query \(\mathbf{q}\), \(k\), \(n_\text{probe}\), re-rank depth \(k'\)
- \(P \leftarrow\) the \(n_\text{probe}\) nearest IVF centroids to \(\mathbf{q}\)
- for \(j \in P\):
- \(\mathbf{r} \leftarrow \mathbf{q} - \mathbf{c}_j\) // for L2 with residual encoding
- build tables \(T_m[\cdot]\) from \(\mathbf{r}\), \(m = 1..M\) // formula (151.8)
- for each code \((i, i_1..i_M)\) in list \(L_j\): score \(\leftarrow \sum_m T_m[i_m]\); keep the best \(k'\)
- load full vectors of the \(k'\) candidates; compute exact scores // re-rank
- return the best \(k\) by exact score
HNSW: walk a graph toward the query
IVF and PQ change what we compare. Graph methods change the order: start somewhere and repeatedly move to a neighbor that is closer to the query. If every vector is linked to its near neighbors, this greedy walk reaches the right area quickly. A graph where a few hops connect any two nodes, like a social network, is a small world.
HNSW (Malkov and Yashunin) adds layers, like a highway system. Every vector is in layer 0. A random few are also in layer 1, fewer in layer 2, and so on. Upper layers have few nodes and long links, so a search can cross the space in a few hops. Lower layers are dense and give the fine detail. When a vector is inserted, its top layer is drawn at random:
- Read the symbols
- \(\ell\)
- the highest layer this vector appears in
- \(M\)
- the number of links each node keeps per layer (layer 0 usually keeps \(2M\))
- \(m_L\)
- the level multiplier; \(1/\ln M\) is the choice suggested in the paper
- \(P(\ell \ge L)\)
- with \(M = 32\): 1 node in 32 reaches layer 1, 1 in 1,024 reaches layer 2
So each layer has about \(M\) times fewer nodes than the one below, and the number of layers grows like \(\log_M N\): about 5.3 for \(N = 10^8\) and \(M = 32\). Search cost grows roughly with \(\log N\) for well-behaved data. [Likely]
Search: start at the single entry node in the top layer. In each upper layer, move greedily to the closest neighbor until no neighbor is closer; then go down one layer and continue from there. In layer 0, run a beam search that keeps the best \(ef\) nodes found so far (\(ef\) = efSearch), not just one. A larger \(ef\) explores more and finds more true neighbors. Insertion is a search too: find the \(ef_\text{construction}\) nearest nodes of the new vector in each of its layers, and link it to \(M\) of them (with a heuristic that prefers neighbors in different directions). Step through a search in Figure 3.
- \(ep \leftarrow\) entry node; \(L \leftarrow\) its top layer
- for \(l_c = L\) down to 1: // greedy, one node
- \(c \leftarrow\) neighbor of \(ep\) in layer \(l_c\) closest to \(\mathbf{q}\); if closer than \(ep\): \(ep \leftarrow c\), repeat
- no neighbor closer: go down one layer, keep \(ep\)
- layer 0: \(C \leftarrow \{ep\}\), \(W \leftarrow \{ep\}\) // beam of width \(ef\)
- while \(C\) not empty: \(c \leftarrow\) pop the closest from \(C\)
- if \(\text{dist}(c) \gt \text{dist}(\text{worst in } W)\): stop
- for each unvisited neighbor \(e\) of \(c\): if \(|W| \lt ef\) or \(e\) beats the worst in \(W\): add \(e\) to \(C\) and \(W\); trim \(W\) to \(ef\)
- return the best \(k\) of \(W\)
How to read Figure 3
Press Play or Step; the highlighted line of the algorithm is the one being run, and the live panel shows the distances it compares. In the upper layers, the orange node jumps far with each hop: that is the highway. In layer 0 the steps become short. Count the gray dots at the end: they are all the vectors whose distance was computed, usually a small part of the 90. With \(ef = 1\) the search can stop in a local minimum: a node whose neighbors are all farther from the query, even though the true nearest neighbor is elsewhere. Press “Next query” until you see a miss with \(ef = 1\), then switch to \(ef = 4\) or \(10\): the beam explores more and finds it.
HNSW has very good recall at low latency, which made it the default index in many vector databases. [Likely] Its costs: the graph must live in RAM, with random memory access; links add memory; building is slow; and deleting nodes is hard, because removing a node can cut paths through the graph. FAISS gives the memory of an HNSW index with full vectors as
(\(4d\) for the FP32 vector, and \(2M\) links of 4 bytes each in layer 0; upper layers add little). [Certain] The FAISS guidelines suggest \(4 \le M \le 64\): larger \(M\) is more accurate but uses more memory. HNSW can also store compressed vectors (for example HNSW32,PQ64 or HNSW32,SQ8) to save memory.
Graphs also scale beyond RAM. DiskANN keeps a graph and full vectors on SSD and only PQ codes in RAM, so one machine can serve a billion vectors. CAGRA builds and searches graphs on GPUs. ScaNN from Google uses partitioning with an improved (anisotropic) quantization. [Certain]
Memory and speed math
Now put the pieces together. For any design, compute two numbers first: bytes per vector (does it fit?) and bytes or vectors touched per query (how fast can it be?). Figure 4 does this for each index family.
How to read Figure 4
Start at the default: 100 million vectors of 768 numbers. Flat FP32 needs 307.2 GB, and a single query would read all of it. IVF-Flat reads only the probed share, but stores the same bytes. IVF-PQ shrinks both. HNSW stores the most, but it touches only the vectors along its search path (a few thousand, depending on efSearch), so its time per query is not a simple share; we show “path” instead. Move \(N\) to \(10^{10}\): even PQ needs about a terabyte, and you must split the index over many machines (sharding). [Likely]
Some rules of thumb follow from these numbers. [Likely]
- Up to a few million vectors: Flat (exact) or HNSW. Memory is not a problem.
- Tens to hundreds of millions, enough RAM: HNSW with full or 8-bit vectors, or IVF with SQ8. Fast and high recall.
- Hundreds of millions to billions, or GPU: IVF-PQ with re-ranking, or an SSD graph like DiskANN.
- Always: reduce \(d\) if the embedding model allows it (Matryoshka embeddings, session 150), and use FP16 or INT8 where recall allows. Halving \(d\) halves every number in Figure 4. Scalar quantization (SQ8: one byte per number, with a per-dimension scale) is the same idea as weight quantization in LLMs (session 103).
The recall versus latency trade-off
Every ANN index has a knob that trades speed for recall: \(n_\text{probe}\) for IVF, \(ef\) (efSearch) for HNSW, the re-rank depth \(k'\) for PQ. Plotting recall@k against queries per second (or against work per query) for many knob values gives a curve. The best index for you is the one whose curve is highest at your latency budget. This is how the public ANN-Benchmarks compare libraries. [Certain]
Figure 5 builds three indexes in your browser on 4,000 random vectors with 32 dimensions (clustered, normalized, like small embeddings) and measures recall@10 on 60 queries against exact search. The PQ here uses 8 sub-vectors with 16 centroids each, so each vector is stored in 4 bytes instead of 128 (32 times smaller).
How to read Figure 5
Press “Sweep nprobe” to raise \(n_\text{probe}\) from 1 to \(n_\text{list}\) automatically, or move the \(n_\text{probe}\) slider yourself, and watch the marked points climb each curve. IVF-Flat reaches recall 1.0 when every list is opened: it is then exact search. IVF-PQ without re-ranking flattens out well below 1.0: compression errors reorder close candidates, and no amount of probing fixes that. Re-ranking the top 50 with exact vectors recovers a large part of the gap, for a small extra cost (50 exact scores per query); a deeper re-rank recovers more. Change nlist: with more lists, the same share scanned gives slightly better recall, because cells follow the data more closely, but you need a larger \(n_\text{probe}\).
FAISS on CPU and GPU
FAISS describes an index with a short factory string. Read it from left to right: optional transform, then the coarse structure, then the vector encoding. [Certain]
| Factory string | Meaning | Bytes per vector (\(d = 768\)) |
|---|---|---|
Flat | exact search, FP32 vectors | 3,072 |
HNSW32,Flat | HNSW graph, \(M = 32\), full vectors | 3,072 + 256 = 3,328 |
IVF65536,Flat | IVF with \(2^{16}\) lists, full vectors | 3,072 + 8 (id) |
IVF65536,SQ8 | IVF, one byte per number | 768 + 8 |
IVF65536,PQ96 | IVF-PQ, 96 one-byte codes | 96 + 8 |
OPQ96,IVF65536,PQ96 | first a learned rotation (OPQ) that makes PQ more accurate | 96 + 8 |
IVF65536,PQ96,RFlat | IVF-PQ, then exact re-rank (refine) with stored full vectors | 96 + 8 + 3,072 |
CPU vs GPU. On GPU, FAISS supports Flat, IVF-Flat, IVF-SQ and IVF-PQ, and a fast k-selection (top-\(k\)) kernel, which was a key part of the original FAISS paper. HNSW is not supported on GPU; the FAISS guidelines list it as CPU-only. [Certain] Newer FAISS versions can use NVIDIA cuVS, which adds the CAGRA graph index on GPU. [Likely] GPUs shine for large query batches and for building indexes quickly (k-means on millions of vectors). For single queries at low traffic, a CPU HNSW is often cheaper. GPU memory (80 GB on an H100) limits the index size unless you shard over GPUs or use compression.
The PyTorch code below builds exact search, IVF and PQ from scratch on 20,000 random 64-dimensional vectors, and measures recall@10 on 200 queries. It is deterministic; the printed numbers are from a real run (torch 2.8, CPU).
import torch torch.manual_seed(0) N, d, nq, k = 20000, 64, 200, 10 # synthetic "embeddings": 200 topics plus noise, L2-normalized (cosine = inner product) topics = torch.randn(200, d) def sample(n): x = topics[torch.randint(0, 200, (n,))] + 1.5 * torch.randn(n, d) return torch.nn.functional.normalize(x, dim=1) xb, xq = sample(N), sample(nq) # 1) exact search: one matrix multiply plus top-k, formula (151.1) def exact(q, x, k): return (q @ x.T).topk(k, dim=1).indices gt = exact(xq, xb, k) def recall_at_k(found, gt): # formula (151.4) return sum(len(set(f.tolist()) & set(g.tolist())) for f, g in zip(found, gt)) / gt.numel() # 2) k-means (used by IVF and by PQ) def kmeans(x, K, iters=20, seed=0): g = torch.Generator().manual_seed(seed) C = x[torch.randperm(len(x), generator=g)[:K]].clone() for _ in range(iters): a = torch.cdist(x, C).argmin(dim=1) for c in range(K): m = a == c if m.any(): C[c] = x[m].mean(0) return C, torch.cdist(x, C).argmin(dim=1) # 3) IVF: cluster the database, search only the nprobe closest lists nlist = 256 C, assign = kmeans(xb, nlist) lists = [torch.nonzero(assign == c).squeeze(1) for c in range(nlist)] def ivf_search(q, nprobe): out, scanned = [], 0 for qi in q: probe = (C @ qi).topk(nprobe).indices cand = torch.cat([lists[c] for c in probe.tolist()]) scanned += len(cand) out.append(cand[(xb[cand] @ qi).topk(min(k, len(cand))).indices]) return out, scanned / (len(q) * N) for nprobe in [1, 4, 16, 64]: found, frac = ivf_search(xq, nprobe) print(f"IVF nprobe={nprobe:3d} recall@10={recall_at_k(found, gt):.3f} scanned={100*frac:.1f}%") # 4) PQ: M sub-vectors, 256 centroids each -> M bytes per vector, formula (151.7) M, ks = 8, 256 ds = d // M books, codes = [], torch.empty(N, M, dtype=torch.uint8) for m in range(M): Cm, am = kmeans(xb[:, m*ds:(m+1)*ds], ks, iters=15, seed=m) books.append(Cm); codes[:, m] = am.to(torch.uint8) books = torch.stack(books) # (M, 256, ds) def pq_search(q, kk): # ADC, formula (151.8) T = torch.einsum('qmd,mkd->qmk', q.view(-1, M, ds), books) # tables (nq, M, 256) cidx = codes.long() # (N, M) scores = sum(T[:, m, cidx[:, m]] for m in range(M)) # M lookups per vector return scores.topk(kk, dim=1).indices pq_top = pq_search(xq, k) print(f"PQ M={M} ({M} bytes/vector vs {4*d}) recall@10={recall_at_k(pq_top, gt):.3f}") cand = pq_search(xq, 100) # re-rank 100 PQ candidates with exact vectors rr = torch.stack([c[(xb[c] @ qi).topk(k).indices] for c, qi in zip(cand, xq)]) print(f"PQ + exact re-rank of top 100 recall@10={recall_at_k(rr, gt):.3f}") # Output of this run: # IVF nprobe= 1 recall@10=0.671 scanned=0.4% # IVF nprobe= 4 recall@10=0.814 scanned=1.6% # IVF nprobe= 16 recall@10=0.914 scanned=6.4% # IVF nprobe= 64 recall@10=0.984 scanned=25.2% # PQ M=8 (8 bytes/vector vs 256) recall@10=0.376 # PQ + exact re-rank of top 100 recall@10=0.848
Read the output like an engineer. IVF reaches 0.914 recall while scanning 6.4% of the data. PQ with 8 bytes (32 times smaller) alone finds only 0.376 of the true top-10, but re-ranking 100 PQ candidates with the exact vectors lifts it to 0.848. The same experiment with the FAISS library (faiss-cpu 1.13, run in a separate process from torch, on the same kind of data drawn with NumPy):
import faiss, numpy as np N, d, nq, k = 20000, 64, 200, 10 rng = np.random.default_rng(0) topics = rng.standard_normal((200, d)).astype("float32") def sample(n): x = topics[rng.integers(0, 200, n)] + 1.5 * rng.standard_normal((n, d)).astype("float32") return x / np.linalg.norm(x, axis=1, keepdims=True) xb, xq = sample(N), sample(nq) faiss.omp_set_num_threads(1) # one thread: same result every run flat = faiss.IndexFlatIP(d); flat.add(xb) # exact search = ground truth _, gt = flat.search(xq, k) def recall(I): return np.mean([len(set(a) & set(b)) / k for a, b in zip(I, gt)]) ivf = faiss.index_factory(d, "IVF256,Flat", faiss.METRIC_INNER_PRODUCT) ivf.train(xb); ivf.add(xb) for p in [1, 4, 16, 64]: ivf.nprobe = p; print("IVF256,Flat nprobe", p, round(recall(ivf.search(xq, k)[1]), 3)) hnsw = faiss.index_factory(d, "HNSW32,Flat", faiss.METRIC_INNER_PRODUCT) hnsw.hnsw.efConstruction = 40; hnsw.add(xb) # HNSW needs no training for ef in [10, 20, 40, 80]: hnsw.hnsw.efSearch = ef; print("HNSW32 efSearch", ef, round(recall(hnsw.search(xq, k)[1]), 3)) ivfpq = faiss.index_factory(d, "IVF256,PQ8", faiss.METRIC_INNER_PRODUCT) ivfpq.train(xb); ivfpq.add(xb); ivfpq.nprobe = 16 print("IVF256,PQ8 nprobe 16", round(recall(ivfpq.search(xq, k)[1]), 3)) ivfpqr = faiss.index_factory(d, "IVF256,PQ8,RFlat", faiss.METRIC_INNER_PRODUCT) ivfpqr.train(xb); ivfpqr.add(xb) faiss.extract_index_ivf(ivfpqr).nprobe = 16 params = faiss.IndexRefineSearchParameters(k_factor=10) # re-rank top 10*k print("IVF256,PQ8,RFlat k_factor 10", round(recall(ivfpqr.search(xq, k, params=params)[1]), 3)) # Output of this run: # IVF256,Flat nprobe 1 0.647 IVF256,Flat nprobe 4 0.803 # IVF256,Flat nprobe 16 0.904 IVF256,Flat nprobe 64 0.985 # HNSW32 efSearch 10 0.812 HNSW32 efSearch 20 0.888 # HNSW32 efSearch 40 0.94 HNSW32 efSearch 80 0.973 # IVF256,PQ8 nprobe 16 0.44 IVF256,PQ8,RFlat k_factor 10 0.879
The library numbers agree with our hand-written version. Note that this tiny dataset uses \(n_\text{list} = 256\), above the \(\sqrt{N} \approx 141\) of formula (151.6) and below the \(4\sqrt{N}\) of the guideline; for a demo this does not matter. On macOS we saw importing torch and faiss in the same Python process crash (two copies of the OpenMP runtime); run them in separate processes if that happens.
Filters and updates
Metadata filters
Real queries come with conditions: “only documents this user may read”, “only videos from 2025”, “only products in stock”. The fraction of the database that passes the filter is the selectivity \(s\). There are three ways to combine a filter with ANN search:
- Post-filtering: run ANN search for more results, then drop those that fail the filter. To still get \(k\) results you must ask for about
results. With \(k = 10\) and a filter that keeps 1% of the data, that is 1,000 results, and for a filter that keeps 0.01%, it is 100,000. Post-filtering is simple but breaks down for strict filters.
- Pre-filtering: compute the set of allowed ids first, then search only among them. For very strict filters, just do exact search over the allowed vectors; it is small. FAISS supports this with an
IDSelectorpassed in the search parameters, which skips vectors that are not allowed. [Certain] - Filter during the search: the graph walk or list scan skips disallowed vectors but still uses them for navigation. This is what most vector databases do. With HNSW it has a known failure: if few nodes pass the filter, the allowed nodes are poorly connected, and the search gets stuck. Databases detect strict filters and switch to exact search, or add extra links (Filtered-DiskANN builds the graph with labels in mind). [Likely]
A practical alternative for a few big categories (for example, one per language or per customer) is partitioning: one index per category. Then the filter costs nothing.
Adds, deletes and drift
Adds. IVF and PQ indexes accept new vectors without retraining: each new vector goes into its nearest list. HNSW inserts with a search, which is slower but online. Deletes. IVF can remove an id from its list. HNSW usually marks a deleted node with a tombstone (it stays in the graph for navigation but is never returned), and rebuilds the graph when too many tombstones collect. [Likely] Drift. The IVF centroids and PQ codebooks were trained on old data. If new data looks different (a new product line, a new language), lists become unbalanced and recall drops. Monitor list sizes and recall on fresh queries, and retrain when needed. Model change. If you change the embedding model, every vector must be re-embedded and the whole index rebuilt: vectors from two models are not comparable. Plan for it; it is often the largest cost of a model upgrade.
Where this is used
| Application | What is indexed | Typical index choice |
|---|---|---|
| RAG over company documents (session 152) | one vector per text chunk, millions of chunks | HNSW or IVF with SQ8 in a vector database, with access-control filters |
| Web-scale or e-commerce search | billions of documents or products | IVF-PQ or a disk graph (DiskANN), sharded over many machines, then a reranker |
| Image search and near-duplicate photos | one CLIP-style vector per image | IVF-PQ on GPU for batch de-duplication; HNSW for online search |
| Text-to-video retrieval (session 208) | one vector per clip or per second of video: 3,600 per hour at 1 frame per second | IVF-PQ for large archives; then group frame hits into clips |
| Video fingerprinting and copy detection (session 209) | compact per-frame descriptors of a huge reference library | PQ codes (memory-bound), exact re-rank and a temporal check of matched frames |
| Key-moment detection and Video-RAG (session 210) | vectors of frames, captions and transcript pieces | HNSW with a filter on video id and time range |
| Recommendation (candidate generation) | item vectors from a two-tower model | IVF or ScaNN-style partitioning, very high query rates |
| Data pipelines for LLM pretraining | embeddings of web documents | GPU k-means and IVF to find and remove near-duplicates at scale (session 34) |
A video example in numbers: 10,000 hours of video at one 512-dimensional FP16 vector per second is 36 million vectors and 36.9 GB. That fits in RAM as HNSW or on one GPU as IVF-PQ, but not as Flat FP32 on one GPU.
Common mistakes
- Mixing metrics. Building an L2 index on vectors that the model trained for cosine, without normalizing. Normalize both database and queries, then use inner product, or the ranking is wrong.
- Measuring recall against the wrong thing. Index recall must be measured against exact search on the same vectors. Do not report human-label recall as if it measured the index, and do not skip the exact baseline.
- Training IVF or PQ on too little or unrepresentative data. Use 30 to 256 vectors per centroid, drawn from the same distribution as the data (not the first million rows, which may be sorted by date or source).
- Leaving \(n_\text{probe}\) or efSearch at the default. FAISS's default \(n_\text{probe}\) is 1, which often gives poor recall. [Certain] Always sweep the knob and pick the point on the curve that meets your recall target.
- Using PQ scores as the final ranking. Compression reorders close candidates. Re-rank the top few hundred with full or FP16 vectors.
- Post-filtering with strict filters. With 0.1% selectivity, a top-100 ANN search returns almost nothing that passes. Detect strict filters and pre-filter or switch to exact search.
- Forgetting HNSW memory and build time. The links add \(8M\) bytes per vector, the graph needs RAM, and building 100 million nodes takes hours. [Likely] Deletes need tombstones and rebuilds.
- Mixing embeddings from two model versions in one index. Distances between them are meaningless. Re-embed everything when the model changes.
Interview questions
What is the difference between exact kNN and ANN search, and how do you measure an ANN index?basic
Why do cosine, inner product and L2 give the same ranking for normalized vectors?basic
Explain IVF. How do you choose nlist and nprobe?core
How does product quantization compress vectors, and how are distances computed without decompressing?core
Explain HNSW search. What do M, efConstruction and efSearch control?core
You have 1 billion 768-dimensional vectors. Size the index.advanced
Why does PQ-only search have a recall ceiling, and how do you remove it?core
How do you combine ANN search with a metadata filter?advanced
When would you use FAISS on GPU instead of CPU?advanced
How do you handle updates and deletes in a vector index?core
Why do trees like k-d trees not work for 768-dimensional embeddings?basic
Exercises
- How many GB does a flat FP16 index of 50 million 1,024-dimensional vectors need? Does it fit on one 80 GB GPU?
- For \(N = 10^6\) and \(n_\text{probe} = 16\), what \(n_\text{list}\) minimizes formula (151.5), and what is the cost relative to exact search?
- A 1,536-dimensional FP32 embedding is compressed with PQ, \(M = 192\), \(K = 256\). Bytes per vector and compression factor?
- HNSW with \(M = 16\) on \(10^7\) vectors: about how many nodes are in layer 1 and in layer 2?
- Your filter keeps 0.5% of the data, and you need \(k = 20\) results. How many results must a post-filtering search ask for?
- In Figure 1, set \(n_\text{list} = 12\). Find a query position where \(n_\text{probe} = 1\) gives recall below 0.5. What \(n_\text{probe}\) brings it to 1.0?
Answerscheck
Key takeaways
- Exact search is one matrix multiply (151.1) with perfect recall, but at 100 million 768-dimensional vectors it needs 307.2 GB and reads all of it per query (151.3). Normalize and use inner product (151.2).
- ANN quality is recall@k against exact search (151.4); always report it as a curve over the speed knob, with memory.
- IVF scans only \(n_\text{probe}\) lists; cost grows like \(\sqrt{N}\) (151.5, 151.6). It cuts work, not memory.
- PQ stores \(M\) bytes per vector (151.7) and scores with table lookups (151.8). It cuts memory 10 to 100 times, but needs re-ranking for high recall.
- HNSW walks a layered graph (151.9); it gives high recall at low latency, costs \(4d + 8M\) bytes per vector (151.10), and is CPU-only in FAISS.
- Filters: post-filter needs \(k/s\) results (151.11); strict filters need pre-filtering or exact search. Plan for adds, deletes, drift and full rebuilds.
Key formulas
References for this session
- Malkov & Yashunin (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Johnson et al. (2017). Billion-scale similarity search with GPUs
- Jégou et al. (2011). Product Quantization for Nearest Neighbor Search
- Meta (code). FAISS library
- Malkov & Yashunin (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Johnson et al. (2017). Billion-scale similarity search with GPUs
- Jégou et al. (2011). Product Quantization for Nearest Neighbor Search
- Meta (code). FAISS library
- Douze et al. (2024). The Faiss library
- Guo et al. (2019). Accelerating Large-Scale Inference with Anisotropic Vector Quantization
- Subramanya et al. (2019). DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
- Ootomo et al. (2023). CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs
- Aumüller, Bernhardsson & Faithfull (2018). ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms