Product Quantisation Codebooks and Asymmetric Distance

A 768-dimensional float32 embedding is 3,072 bytes. A hundred million of them is 307 GB, which prices the index out of commodity hardware before any graph or cell structure is added. Product quantisation stores the same vector in 96 bytes and computes distances against it faster than against the original, which is the part people find surprising.

Subspaces and codebooks

Split a \(d\)-dimensional vector \(x\) into \(m\) contiguous subvectors \(x = (x^1, \dots, x^m)\), each of dimension \(d/m\). Learn an independent codebook \(\mathcal{C}^j\) of \(2^b\) centroids per subspace by k-means over a training sample, and store, for each vector, the index of the nearest centroid in each subspace. The code is \(m\) integers of \(b\) bits, so storage is \(mb/8\) bytes per vector regardless of \(d\) (Jégou, Douze & Schmid, 2011, Product Quantization for Nearest Neighbor Search, IEEE TPAMI 33(1):117–128).

The combinatorics are the point. With \(m = 96\) subspaces and \(b = 8\) bits, the implied joint codebook has \(256^{96}\) entries, which no clustering algorithm could ever fit directly, yet it is represented by 96 tiny codebooks of 256 centroids each.

Because the subspace split is on fixed coordinate ranges, performance depends on how variance is distributed across dimensions. Optimised product quantisation learns an orthogonal rotation applied before the split, so subspaces end up with comparable variance (Ge, He, Ke & Sun, CVPR 2013). It adds no per-vector storage, which is why FAISS recommends it almost unconditionally wherever PQ is used.

Why the query stays uncompressed

Asymmetric distance computation is what makes PQ fast rather than merely small. Quantise only the stored vectors. At query time, precompute one table

for every subspace \(j\) and centroid \(c\), and then the approximate squared distance to any stored code is a sum of \(m\) lookups:

For \(m = 96\) and \(b = 8\) the table is 96 × 256 floats, about 98 KB, built once per query and reused across every candidate. The symmetric variant, which quantises the query too, is cheaper to set up and strictly worse: it adds the query's own quantisation error to every comparison, for no benefit once the table cost is amortised across thousands of candidates.

The modern refinement shrinks \(b\) rather than \(m\). At \(b = 4\) a subspace codebook fits inside a SIMD register, so a batch of candidates resolves in parallel; FAISS exposes this as the fs fast-scan variants, where PQ28x4fs costs about 14 bytes per vector (FAISS wiki, The index factory). ScaNN went the other direction and changed the loss rather than the width, penalising quantisation error parallel to the data point more heavily than the orthogonal component because that is the component that distorts inner-product ranking (Guo et al., ICML 2020, PMLR 119:3887–3896).

When it breaks

Codebooks are a learned model fitted once. Nothing re-fits them as the corpus changes, so onboarding new content, switching embedding model versions, or shifting language mix raises reconstruction error on exactly the material users are now asking about. The symptom is a recall regression confined to a subset of queries and invisible in an average.

PQ also has strong empirical results and no theoretical error guarantee, and its authors' successors note it can fail badly on some real datasets. RaBitQ was motivated by precisely that gap, quantising to one bit per dimension after a random rotation with a sharp provable error bound, at about d/8 + 8 bytes per vector (Gao & Long, SIGMOD 2024).

The limit that matters most operationally: a code sets a recall ceiling that no amount of extra probing can lift. RaBitQ's authors state the general case plainly, that aggressive quantisation "can hardly produce reasonable recall" without a re-ranking stage. Pair compression with exact rescoring or do not compress.