Product quantization,
explained.

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.

Product quantization rarely works alone; it pairs with a coarse index to avoid scanning the whole dataset:

The knobs are intuitive: more subquantizers m or a larger k lowers distortion (better recall) at the cost of more bytes and slower scoring. Tuning m and k against a memory and recall budget is the core of deploying PQ-based search.

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.