Product Quantization

Start with plain quantization

Before splitting anything, think of the obvious compression: run k-means over the whole corpus with 256 centroids and replace each vector with the index of its nearest one. Each vector becomes a single byte.

The compression is spectacular and the index is useless. 256 centroids cannot describe a million distinct 768-dimensional vectors; the average error is enormous, and any two vectors sharing a centroid are indistinguishable to the index. To get useful resolution you would need a codebook with millions of entries — which you would then have to store, and which k-means could not train.

Set m = 1 in the visualisation to see just this. One codebook, a handful of representable spots, and the top-k answer collapses.

This page shows how product quantization escapes that limit by splitting each vector into short subvectors and quantising each piece on its own. This trades a controllable amount of recall for a compression ratio that makes billion-scale search fit in RAM.

The product trick

Product quantization escapes that by quantising *pieces* of the vector on its own.

Split a 768-dimensional vector into m = 96 chunks of 8 dimensions each. Give each chunk its own codebook of 256 centroids, trained by k-means over that chunk across the whole corpus. Encoding means finding the nearest centroid in each of the 96 codebooks and storing 96 one-byte indices.

768 × 4 = 3,072 bytes  →  96 bytes.  A 32× reduction.

Now count what those 96 bytes can express. Any combination of centroids is a valid code, so the number of representable vectors is 256⁹⁶ — a number with 231 digits — from 24,576 stored centroids. That product is the entire idea, and "product" in the name is literally the Cartesian product of the subspace codebooks.

Set m = 2 in the visualisation at the same bit depth. The number of representable points squares, the grid appears, and recall jumps. Same centroids stored; vastly more spots described.

Reading the picture

With d = 2 and m = 2, each subspace is one axis and its codebook is a set of spots along it. The faint grid is each spot the index can represent — the intersections are the reachable points. The blue line from each vector runs to where the index thinks that vector is: the quantisation error, drawn right.

Lower the bit depth and watch the grid coarsen and the blue lines lengthen. That growing error is what in time costs you recall, and it is the only thing that does — PQ has no other failure mode.

Asymmetric distance, and why queries are cheap

The obvious way to compare a query with a code is to decode the code back into a vector and measure. PQ does something better and leaves the query exact.

For each of the m subspaces, compute the distance from the query's subvector to each of the 256 centroids in that subspace's codebook. That is an m × 256 lookup table, built once per query. The distance from the query to any stored code is then:

d(q, code) ≈ table[0][code[0]] + table[1][code[1]] + … + table[m-1][code[m-1]]

m table lookups and m additions. No products, no decoding, and — this is the part that matters — the per-candidate cost no longer depends on d. Scanning a million 96-byte codes is 96 million lookups; scanning a million 768-dimensional float vectors is 768 million times-adds over eight times the memory bandwidth.

It is called asymmetric because only one side is quantised. Quantising the query too would let you precompute a even table between codebook entries, which is marginally faster and measurably less exact: you would be adding the query's own quantisation error to each check for no gain. Always use asymmetric distance unless something very unusual is going on.

The parameters

m, the number of subquantizers, must divide d. Larger m means shorter subvectors, less data discarded per chunk, better recall — and a longer code. At 8 bits, m *is* your bytes per vector, which makes the trade easy to reason about.

nbits is almost always 8. A byte is what hardware likes, 256 centroids per subspace is a good operating point, and the SIMD lookup implementations that make PQ fast assume it. Lower values exist for extreme compression and cost recall quickly.

The useful way to hold this: the code length in bytes is the dial, equal to m × nbits / 8. Common choices at d = 768 are 96 bytes when recall matters and 32 bytes when memory is the binding constraint and a reranking stage will clean up afterwards.

One structural assumption worth knowing: PQ splits dimensions in their first order, which implicitly assumes neighbouring dimensions belong together. For learned embeddings that is arbitrary. OPQ — optimised product quantization — learns a rotation of the space first, so that variance is balanced across the subspaces before splitting. It costs a matrix times per query and often buys a few points of recall for free, which is why FAISS's OPQ64_256,IVF...,PQ64 recipes are so common.

What PQ does not do

PQ is a compression scheme, not a search structure. A pure PQ index still computes a distance for each vector in the corpus — it is a flat scan over short codes rather than over full vectors. That is roughly 20–30× faster than scanning float32, which is a real win, and it is still O(n).

So PQ is nearly always combined with something that prunes:

• IVF-PQ puts it inside cells. This is the standard billion-scale index.
• DiskANN keeps PQ codes in RAM to route a graph search whose full vectors live on SSD.
• ScaNN changes the quantisation objective itself for inner product search, then rescores just.

Pure PQ on its own is unusual, and appears mainly where you already have a small candidate set and only memory hurts.

import faiss

d, m, nbits = 768, 96, 8
index = faiss.IndexPQ(d, m, nbits)     # 96 bytes per vector

index.train(sample)                    # trains m codebooks of 256 centroids
index.add(vectors)
scores, ids = index.search(queries, 10)

# In practice, wrapped in something that prunes:
quantizer = faiss.IndexFlatL2(d)
ivfpq = faiss.IndexIVFPQ(quantizer, d, 1024, m, nbits)

m must divide d and FAISS will refuse if not — a constraint that catches people who change embedding models without changing the index recipe. 768 divides by 96, 64, 48, 32 and 16; 1536 divides by all of those too, which is one small reason those dimensions are popular.

PQ, int8 and binary

PQ is not the only way to make a vector smaller. And the options have become far more common since it was published. At d = 768 they line up like this:

Scalar quantization stores each dimension as one byte against a recorded range. There is no codebook, calibration is a single pass, and on normalised embeddings the ranking loss is often small enough to ignore. It is the cheapest real compression available and the first thing to try.

Binary quantization keeps one bit per dimension — the sign — and scores with Hamming distance, which is an XOR and a popcount. It lands at the same 96 bytes as PQ-96 with no training at all, and it works better than it sounds on high-dimensional embeddings *provided* a rescoring pass over the shortlist fixes the ordering. That proviso is the same one IVF-PQ needs, for the same reason.

Matryoshka embeddings are orthogonal to all of it: the model is trained so that the first 256 of its 768 dimensions are themselves a usable embedding, so you truncate rather than quantise — and you can still quantise afterwards.

What PQ retains is precision per byte at aggressive ratios, and the fact that it composes with a partition through residual encoding. If 4× is enough, int8 is less work than any of this.

In one line

PQ splits a vector into m subvectors and stores the index of the nearest centroid in each subspace's codebook. m codebooks of k centroids describe kᵐ spots from m·k stored centroids, which is why the compression is so extreme. Queries build an m × k distance table once. Then cost m lookups per candidate, free of dimension. It compresses but does not prune, so it is almost always paired with IVF or a graph.

Questions people ask

Why does splitting help so much? Because representable spots *times* while stored centroids only add. m codebooks of k centroids describe kᵐ spots from m·k stored centroids. At m = 96 and k = 256, that is 256⁹⁶ spots from 24,576 centroids. Plain quantization has to store each spot it can represent.

Should nbits ever be anything but 8? Rarely. A byte is what hardware likes, 256 centroids per subspace is a good operating point. And the SIMD lookup implementations that make PQ fast assume it. Lower values exist for extreme compression and lose recall quickly.

Should I use OPQ? Often yes. PQ splits dimensions in their first order, which implicitly assumes neighbouring dimensions belong together. Arbitrary for a learned embedding. OPQ learns a rotation that balances variance across the subspaces first, costs one matrix times per query, and often buys a few points of recall.

Why asymmetric distance instead of decoding the code? Because it leaves the query exact. Quantising the query too would let you precompute a even table between codebook entries. This is marginally faster and measurably less exact. You would be adding the query's own quantisation error to each check for no gain.

FAISS rejected my m. Why? Because m must divide d. 768 divides by 96, 64, 48, 32 and 16, and so does 1536. One small reason those embedding dimensions are popular. This is what catches people who change embedding model without revisiting the index recipe.

Is PQ an index? No, it is a compression scheme. A pure PQ index still computes a distance for each vector in the corpus. A flat scan over short codes, perhaps 20–30× faster than scanning float32, and still O(n). It is almost always wrapped in something that prunes.

Recap in one screen

• Quantise pieces rather than the whole vector: m subvectors, each with its own 256-entry codebook, stored as m one-byte indices.
• 3,072 bytes becomes 96 at m = 96. The compression comes from the Cartesian product of the codebooks — which is what "product" in the name means.
• A query builds an m × 256 distance table once. Then each candidate costs m lookups and m additions: no products, no decoding. And a cost free of d.
• Asymmetric is the default because only the stored side is quantised. So the query adds no error of its own.
• Quantisation error is PQ's only failure mode. It shows up as recall and as nothing else.
• It compresses without pruning, so pair it with IVF, a graph, or a rescoring stage. Pure PQ on its own is unusual.