IVF and Product Quantization (IVF-PQ)
Two tricks that let large vector search fit in memory: IVF skips most of the data at query time, and product quantization shrinks each vector into a few bytes.
Why Does This Exist?
Exact search charges you twice. Say you hold a million 128-dim float embeddings. Each vector costs bytes, so the raw matrix is about 512 MB, and a billion of them is about 512 GB. A query then scores every stored vector, which is multiplies per question, where is your vector count and is the dimension count. You run out of RAM first and patience second.
Graph indexes such as HNSW answer fast but keep the raw vectors plus the graph around them, so memory stays the binding constraint. When RAM is the budget, you compress instead of adding servers. That is the trade this page is about: smaller memory and fewer distance checks in exchange for a small, measurable drop in recall.
You will meet two independent tricks here that people deploy together. The surrounding map: the general bargain of skipping work lives in approximate nearest neighbor search, the graph rival lives in HNSW, and the production wrapper with filters and persistence lives in vector databases. You need only one prerequisite: an embedding is a list of numbers and closer means more similar, covered in embeddings and similarity metrics.
Think of It Like This
A library with sections and summary cards
You walk into a library holding a million books and you want the three most like the one in your hand. You do not read every shelf. First you ask which section fits: history, cooking, science fiction. You search only that section and skip the rest. That choice is IVF. Each section desk that points you onward is a centroid, and the number of sections you agree to check is nprobe.
Now suppose every book on the shelf is a tiny card that reads "shelf code 42, style code 17" instead of the full text. A master catalogue at the desk says what each code typically looks like. You compare your book against the catalogue entries, add up the per-code resemblances, and guess well without pulling the full books. Those cards are PQ codes and the catalogues are codebooks.
Where it stops: books sit in fixed sections with real meanings, while IVF cells are learned boundaries that can turn lopsided. And a summary card never becomes the book again. The detail PQ throws away is gone, so close calls get fuzzy in a way a librarian paging the full text would not.
How It Actually Works
IVF and PQ compose because they attack different costs. Inverted file index (IVF) cuts how many vectors you score. Product quantization (PQ) cuts what each scored vector costs. A third piece, asymmetric distance computation, lets you score the compressed vectors without inflating them first.
IVF picks which lists to scan
At build time you run k-means over a sample of your data and keep centroids, where is the number of lists or cells you want. Every stored vector joins the list of its nearest centroid, so the index is literally inverted: centroid first, members after.
At query time you score the query against the centroids, keep the closest lists, where is how many lists you agree to scan, and score only the members inside them. Turn up and recall climbs while latency climbs with it. When lists are balanced, the fraction of the data you touch is about . With and , you scan roughly one percent of the index.
The assumption is that a query's true neighbours live in its nearby cells. That fails at boundaries: a neighbour sitting just across a cell wall is invisible when is 1, which is why production setups probe several lists and rerank.
PQ shrinks each vector
Take a -dim vector and cut it into subvectors, where is the split count. For each of the positions independently, run k-means and keep a codebook of centroids, where is the codebook size at that position. The standard choice is so each id fits in one byte.
Then replace each subvector with the id of its nearest centroid in that position's codebook. The stored vector is small ids. A 128-dim float32 vector is 512 bytes raw; with it becomes 16 bytes, a 32 to 1 saving before you count the shared codebooks. The price is quantization error: everything inside one centroid's cell is remembered as the centroid, and fine distinctions inside the cell are lost for good.
ADC scores without decompressing
Asymmetric distance computation (ADC) is the scoring trick, asymmetric because the two sides are treated differently: the query stays raw while the database stays packed. Split the query into the same pieces. For each position, precompute the squared distance from the query piece to every centroid in that position's codebook. That table costs small computations, for example in the tiny example below.
Each candidate's distance is then estimated by adding up its table entries, one per code. Squared Euclidean distance splits cleanly across the halves, so the sum has the same form as the true distance with centroids standing in for the original pieces. You never rebuild the original vectors, and each candidate costs lookups plus adds.
Worked example: 8 numbers become 2 codes
Take an 8-dim vector, so , split into halves:
with and . Suppose the first codebook's 42nd centroid is exactly and the second codebook's 17th centroid is exactly . The stored code is : 2 bytes standing in for bytes, a 16 to 1 saving on this vector.
Now a query arrives:
Split it the same way into and . Look up the two coded centroids and add the halves:
Here the estimate equals the true squared distance because the codes reproduce exactly. In production the codes approximate, so 1.25 would be an estimate with a small error from each half. The diagram draws these same numbers: one probed list out of three on the left, codes and the lookup on the right.
Do not use IVF-PQ when your whole index already fits in RAM with room to spare and you need the highest recall per millisecond. A raw or graph index without compression wins there. Reach for IVF-PQ when memory or hosting cost is the constraint you actually feel.
Code
This snippet replays the worked example with plain Python so you can check the ADC addition yourself. Every # -> comment is the real printed value for the numbers above.
def sq_dist(a: list[float], b: list[float]) -> float: return sum((x - y) ** 2 for x, y in zip(a, b))
q1: list[float] = [1.5, 2.0, 3.0, 4.5]c1: list[float] = [1.0, 2.0, 3.0, 4.0] # codebook 1, entry 42q2: list[float] = [4.5, 6.5, 7.0, 8.5]c2: list[float] = [5.0, 6.0, 7.0, 8.0] # codebook 2, entry 17
d1: float = sq_dist(q1, c1)d2: float = sq_dist(q2, c2)print(d1) # -> 0.5print(d2) # -> 0.75print(d1 + d2) # -> 1.25print(8 * 4, 2) # -> 32 2The last line is the memory moral: 32 raw bytes become a 2-byte code on this 8-dim toy. Scale the same arithmetic to 128 dims with and you get 512 bytes down to 16.
Watch Out For
Training on data that does not look like the index
IVF-PQ learns its centroids once, up front, from a training sample. If that sample comes from a different distribution than the vectors you later add, a few lists swallow most of the data while the rest sit nearly empty. You will feel it as latency that swings wildly per query plus recall that no tuning fixes, because one giant list dominates every probe.
Fix it at the source. Train on a large sample of the actual vectors you will serve, then check list sizes before shipping: the largest list should hold a small multiple of the average, not most of the index. Never ship an index whose training sample you cannot describe. If the data drifts later, retrain the codebooks and rebuild rather than raising to paper over the skew.
Compressing so hard that near duplicates go missing
Pushing down (fewer, wider subvectors) or probing a single list feels efficient until your exact near duplicate stops coming back top one. The symptom is specific: results look vaguely on topic while the one vector you know should win sits at rank twenty or never appears. That is quantization error plus a missed cell, not a bad embedding model.
Fix it in two steps. Raise until a known-duplicate probe returns correctly, then keep above 1 and rerank a shortlist against raw vectors when you can afford the RAM for the top candidates. Reranking is covered in reranking. Compression buys you the candidate list; it should not cast the final vote on the closest calls.
The Quick Version
- IVF groups vectors into lists at build time and scans only the lists nearest the query, so you pay for a slice of the index instead of all of it.
- PQ cuts each -dim vector into pieces and stores one codebook id per piece, turning 512 bytes into 16 bytes at and .
- ADC scores compressed candidates by adding precomputed per-piece distances, so queries never decompress the database.
- The pair trades a small recall loss for large RAM and latency savings, which pays off when the raw index does not fit comfortably in memory.
- Train codebooks on representative data, keep large enough to preserve near duplicates, and probe more than one list.