Product quantization,
explained.

Rung 3 gives one vector per item, which turns retrieval into nearest-neighbour search and immediately creates a memory problem. Vectors are typically hundreds of dimensions in four-byte floats, so a billion of them is a quantity of memory no single machine has. The obvious fix — keep them on disk — destroys the latency that made the approach attractive.

The change is to not keep the vectors at all, and to keep a short code per vector instead. Naively, quantising a whole high-dimensional vector to a codebook would need astronomically many codewords to be accurate. So split the vector into several contiguous sub-vectors and quantise each one separately with its own small codebook. A vector becomes a list of codebook indices — one small integer per sub-vector.

The reason this is a good idea rather than merely a compact one is combinatorial, and it is the rung's whole argument. With m sub-vectors and k entries per codebook, the scheme can represent k^^m distinct vectors while storing only m·k codewords — the expressible set is the product of the parts, and the storage is their sum. That is what buys compression ratios of the order of 64× and beyond. And distances stay fast because a query's distance to each codeword can be precomputed into small lookup tables, so scoring a compressed vector is a handful of table reads and additions, with the query kept at full precision so its own resolution is never thrown away.

Nearest-neighbour search over embeddings — find the vectors closest to a query — is the engine under semantic search, recommendations, and retrieval. At small scale you just store every vector and compare. But a modern embedding might be 128 or 768 dimensions of float32, and a billion of them is hundreds of gigabytes to terabytes. That won't fit in fast memory, and scanning it is slow. The bottleneck is not the math; it's the bytes.

The obvious fix — store fewer bits per number — is crude: uniformly rounding each dimension loses too much accuracy for too little saving. Product quantization does something smarter. It compresses groups of dimensions together by learning what typical groups look like, so each group is replaced by a pointer to its closest learned prototype. The savings are enormous and the distances survive well enough to search — which is exactly the balance vector search needs.

The recipe: split a D-dimensional vector into m contiguous subvectors. For each subspace, learn a codebook of k centroids (by k-means over the training data). To compress a vector, replace each subvector with the index of its nearest centroid in that subspace's codebook. The stored representation is just m indices. With the conventional k = 256, each index is one byte:

A 128-dim float vector is 512 bytes; split into m = 8 subvectors with 256-entry codebooks, it becomes 8 bytes — 64× smaller. The subvectors are quantized independently, which is what keeps the codebooks tiny (each covers only D/m dimensions) while still capturing the structure within each slice. The runnable version below computes the compression and the reconstruction.

Here's the beautiful part, and the reason it's called a product quantizer. Each subspace has only k centroids — a small catalog. But a full vector is an independent choice of centroid in every subspace, so the number of distinct vectors the scheme can represent is the product of the per-subspace choices: k^^m. Small catalogs, combined, span an astronomically large space.

Eight one-byte codebooks of 256 entries each yield 256⁸ ≈ 1.8 × 10¹⁹ possible codes — far more than any dataset you'd ever index, all from storing 8 bytes. That combinatorial explosion is why product quantization compresses so aggressively without collapsing distinct vectors onto the same code. You get the resolution of an enormous codebook at the storage cost of a tiny one.

Compression is only useful if you can still compare quickly. Product quantization uses asymmetric distance computation: keep the query at full precision, but for each subspace precompute the distance from the query's subvector to every centroid in that subspace's codebook — a small lookup table of m × k numbers, built once per query.

So scoring a billion compressed vectors is a billion sums of m small lookups — cache-friendly and blazing fast. Keeping the query uncompressed (the "asymmetric" part) makes the approximation noticeably more accurate than the symmetric alternative of quantizing the query too, at no extra storage cost.

The paper (Jégou, Douze and Schmid, IEEE TPAMI 2011) describes two search systems built on product quantization. ADC scans every compressed vector. IVFADC adds a coarse inverted file so that only a few cells are scanned, and encodes each vector's offset from its cell centre rather than the vector itself. IVFADC is the design FAISS later shipped as IVFPQ, and its procedure is below.

1. Train the coarse quantizer. Run k-means on a training sample to get k′ centroids; the paper's million-vector experiments use coarse vocabularies of 1,024 and 8,192 cells. Each centroid owns one inverted list.
2. Train the product quantizer on residuals. For each training vector compute its residual r = y − q_c(y), the offset from its nearest coarse centroid. Split the residuals into m sub-vectors of D/m dimensions and run k-means separately in each subspace, giving m codebooks of k* = 256 centroids. One product quantizer is shared by every cell.
3. Encode the database. Assign each vector y to its nearest coarse centroid, encode its residual with the product quantizer, and append the pair (id, code) to that centroid's list. With m = 8 a code is 8 bytes, so an entry is 12 bytes with a 4-byte id (the paper allows 8 to 32 bits for the identifier); the cell itself costs nothing to store, because the list a vector sits in records it.
4. Choose cells at query time. Find the w coarse centroids nearest to the query x — the paper's multiple assignment, which FAISS calls nprobe — and visit only their lists. With k′ = 1,024 and w = 8, a query touches about 0.8% of the database if the cells are balanced.
5. Build a distance table per visited cell. For cell i, take the query's residual x − c_i, split it into m sub-vectors, and compute the squared distance from each to all 256 sub-centroids of its subspace: an m × 256 table. Each cell needs its own table, because the query residual changes with the cell.
6. Scan and rank. For each entry in a visited list, the approximate squared distance is the sum of m table lookups indexed by its code bytes — no decompression, no full-precision arithmetic. A heap keeps the best k across all visited lists, and their ids are returned.

Symmetric versus asymmetric distances

The paper compares two ways to estimate a distance from codes. Symmetric distance computation (SDC) quantizes the query too and reads centroid-to-centroid distances from tables computed once for the whole index. Asymmetric distance computation (ADC) keeps the query exact and builds the m × k* table per query. Both store identical codes. By the triangle inequality, ADC's error is bounded by the database vector's quantization error alone, while SDC's bound adds the query's error as well, and in the experiments ADC gave better recall at every code size for a small extra cost per query. The paper also shows that which dimensions are grouped into a sub-vector affects accuracy, with a random ordering doing worse than one that keeps related dimensions together — the observation that later work turned into learned rotations.

• uj(·) — the j-th sub-vector: D/m consecutive dimensions.
• qj — the k-means quantizer of subspace j, with k* centroids; the code stores only the index.
• d̃ (ADC) — query exact, database quantized: one m × k* table per query, or per cell in IVFADC.
• d̂ (SDC) — both quantized: k* × k* centroid-to-centroid tables per subspace, computed once.
• qc, qp — in IVFADC, the coarse quantizer and the product quantizer that encodes residuals.

The two bounds are the triangle inequality, and they carry the whole SDC-versus-ADC argument: ADC's estimate is off by at most the database vector's own quantization error, SDC's by both errors added. At the extremes the product quantizer turns into familiar things. With m = 1 it is ordinary k-means with only 256 possible codes, far too coarse for any real collection. With m = D it is a scalar quantizer with 256 levels per dimension — 128 bytes for a 128-dimensional SIFT vector, only a 4× saving. Product quantization is the range in between, where the code space has (k*)^^m points but the codebooks cost only m · k* centroids to learn and store.

The benchmarks were introduced with this work and are still standard: SIFT1M, a million 128-dimensional SIFT descriptors with 10,000 queries and a separate 100,000-vector training set, and GIST1M, about a million 960-dimensional GIST descriptors with 500 queries. Ground truth is the exact Euclidean nearest neighbour, and the measure is recall@R: the fraction of queries whose true nearest neighbour appears in the first R results. Baselines were spectral hashing and Hamming embedding at equal code length, and FLANN, a tree-based method that keeps the full vectors; the abstract reports that the approach outperformed all three. A final experiment scaled IVFADC to two billion vectors.

The scan sizes assume balanced cells; real lists vary. Three results carry the paper. ADC beat SDC, as the error bounds predict, for the price of one small table per query. Encoding residuals beat encoding raw vectors, because the coarse centroid already says roughly where a vector is, so the same eight bytes describe a much smaller region. And the number of probed cells mattered: with w = 1 a query loses every true neighbour that fell into an adjacent cell, so recall levels off below 1 however long the code, and raising w buys it back at proportional cost. GIST, at 960 dimensions, was markedly harder than SIFT at equal code length — the cost of squeezing a much richer vector into the same few bytes.

The method is lossy and that is the deal: the returned neighbours are approximate, ranking near the top can be wrong, and the compression rate trades directly against recall. The paper is clear about this and about the tuning involved, and it is the reason production systems re-rank a candidate set with exact distances — the compressed index narrows, something precise decides.

The independence assumption is the technical weakness: quantising slices separately assumes the slices are not strongly correlated, and in real embeddings they are. Later work addressed this by rotating the space before splitting so that variance is spread evenly across the slices, which measurably improves recall at the same code length and is now standard. A rotation is a free change of basis — a clean case of getting accuracy from geometry rather than from bits.

How it held up: it is inside the infrastructure. The compressed-code index is a standard option in every serious vector store, generally combined with rung 5's graph or with a coarse partitioning so that compression handles memory and structure handles the search. Fifteen years on, the sum-versus-product argument above is still the reason billion-scale search fits on hardware you can rent.

Product quantization predates the deep-learning embedding boom — it came from image retrieval in 2011 — but it became foundational precisely when everything turned into vectors. When you embed a billion documents, images, or products, you hit exactly the memory wall PQ was built for, and its combination of aggressive compression with fast, decompression-free distances is hard to beat. Libraries like FAISS made it a default, and it lives inside many production vector databases today.

Its lasting idea is compression by learned structure. Generic bit-reduction throws away information blindly; product quantization instead learns what the data actually looks like, subspace by subspace, and spends its bits describing which learned prototype each piece resembles. That "quantize against a learned codebook" pattern recurs across the field — in model weight quantization, in KV-cache compression, and beyond — and this paper is one of its clearest, most enduring expressions.

Product Quantization (PQ) is the compression trick that makes billion-scale vector search affordable. Storing millions of high-dimensional float vectors in full precision is expensive in memory; PQ shrinks them dramatically by splitting each vector into several sub-vectors and replacing each sub-vector with the id of its nearest entry in a small learned codebook. A vector becomes a short list of codebook indices — often an order of magnitude or more smaller.

The cleverness is that distances can be computed without decompressing. You precompute, for the query, the distance to every codebook entry per sub-space (a small lookup table), then approximate the distance to any database vector by summing table lookups. Search becomes cheap table additions over compact codes instead of full-precision math over full vectors.

The trade-off is accuracy: PQ is lossy, so retrieved neighbors are approximate. In practice it is tuned (number of sub-quantizers, codebook size) and combined with a coarse index (IVF) to prune the search space, then often re-ranked with exact distances on a shortlist — the classic IVF-PQ pipeline.

PQ matters because it is foundational infrastructure under modern vector databases and ANN libraries (FAISS and its kin), which power RAG retrieval, semantic search, and recommendation at scale. Whenever a system searches hundreds of millions of embeddings on a memory budget, some descendant of product quantization is usually doing the heavy lifting.

Work each one out before you open it — a number, a prediction or a reason, not a definition. Producing the answer is what makes it stick. Your progress is kept on this device.

The longest ladder here, and the most linear: nine papers that carry one idea — text as geometry — from a 2013 word embedding to a graph-structured retrieval system.

1. 1Word2Vec2013
2. 2GloVe2014
3. 3Sentence-BERT2019
4. 4Product Quantization2011
5. 5HNSW2016
6. 6Dense Passage Retrieval2020
7. 7ColBERT2020
8. 8Retrieval-Augmented Generation2020
9. 9GraphRAG2024

All 110 papers, in 19 ladders →