Product Quantization

Product Quantization (PQ) is a vector-compression technique for Approximate Nearest Neighbour (ANN) search, introduced by Hervé Jégou, Matthijs Douze, and Cordelia Schmid (INRIA) in their 2011 IEEE TPAMI paper “Product Quantization for Nearest Neighbor Search”. PQ decomposes a high-dimensional vector space into a Cartesian product of low-dimensional subspaces and quantizes each subspace independently using vector quantization (k-means clustering). Each high-dimensional vector is represented as a short code — one cluster index per subspace — that occupies a tiny fraction of the original vector’s memory (typically 8 bytes per vector instead of d × 4 bytes for a 32-bit float vector). Despite the lossy compression, asymmetric distance computations (between full-precision queries and PQ-coded database vectors) preserve nearest-neighbour relationships well enough for high-recall ANN search. PQ is widely used as a building block in FAISS (the IVF-PQ composite index is one of FAISS’s most popular configurations), ScaNN, and other vector databases. In recommender systems, PQ is what makes billion-item embedding indexes fit in main memory.

1. The Compression Problem

A d-dimensional float32 vector occupies 4d bytes. For d = 256 that is 1 KB per vector; for a billion vectors, 1 TB of memory just for the vectors. Most servers cannot fit a billion-vector index in RAM at full precision.

Vector compression reduces memory by representing each vector with fewer bytes. The compression must preserve nearest-neighbour relationships well enough that ANN search remains accurate.

PQ achieves dramatic compression: typical PQ codes are 8–32 bytes per vector regardless of dimension d, a 50–500× compression ratio. The compression is lossy — the original vector cannot be reconstructed exactly — but the structure preserves most of the geometric relationships needed for similarity search.

2. The PQ Decomposition

For input vector dimensionality d, PQ splits the vector into M subvectors of dimension d/M each. Each subvector is quantized independently via k-means clustering with k cluster centroids per subspace.

The procedure:

Training (offline):

1. Take the entire database of vectors. Split each into M subvectors of dimension d/M.
2. For each subspace m = 1, ..., M:
   • Run k-means on the m-th subvectors of all database vectors with k clusters.
   • Store the k centroids C^m = {c^m_1, ..., c^m_k} of dimension d/M.
3. Total storage for the codebooks: M · k · (d/M) · 4 bytes = k · d · 4 bytes (independent of dataset size).

Encoding (per database vector):

1. Split v ∈ ℝ^d into M subvectors v^1, v^2, ..., v^M.
2. For each subspace m, find the nearest centroid index: q^m(v) = argmin_j ||v^m − c^m_j||².
3. The PQ code for v is the tuple (q^1, q^2, ..., q^M) — M integers, each in [0, k).

If k = 256, each q^m fits in 8 bits = 1 byte. So the PQ code for each vector is M bytes total (typical: 8–32 bytes). For d = 256 and M = 16 (each subvector is 16-dimensional, with 256 centroids), this is 16 bytes per vector — a 64× compression versus float32.

3. Asymmetric Distance Computation

To search efficiently, PQ uses asymmetric distance computation (ADC): the query is kept at full precision, and only database vectors are PQ-encoded. The squared Euclidean distance from query q to PQ-coded database vector v is approximated:

||q − v||²  ≈  Σ_{m=1}^{M}  ||q^m − c^m_{q^m(v)}||²

where q^m is the m-th subvector of the query, c^m_{q^m(v)} is the centroid in subspace m corresponding to database vector v’s code in that subspace, and the sum is over all M subspaces.

The clever optimization: precompute the distance lookup table of size M × k containing ||q^m − c^m_j||² for every subspace m and every centroid j. This table is computed once per query in O(M · k · d/M) = O(k · d) time.

To compute the distance from q to a database vector v, look up M values from the table (one per subspace) and sum them. Each per-vector distance computation is O(M) — typically M ≤ 32, so a few dozen lookups and adds.

For a database of n vectors, the total per-query distance computation is O(n · M), plus the one-time O(k · d) table precomputation. Compared to naive exact search at O(n · d), this is a d/M speedup factor — typically 16× to 64×.

Combined with an upstream coarse partitioning (like an Inverted File Index) that restricts the search to a small subset of the database per query, PQ-coded ANN can achieve sub-millisecond query latencies on billion-vector datasets.

4. The IVF-PQ Composite Index

The most-used PQ-based index in FAISS is the IVF-PQ composite: an Inverted File Index (IVF) for coarse partitioning combined with PQ for compressed distance computation within each partition.

Index construction:
1. Run k-means on all database vectors with K_IVF coarse clusters.
2. Assign each database vector to its nearest coarse cluster.
3. Within each coarse cluster, train PQ codes for the vectors (often on the residuals from the cluster centroid).

Query:
1. Find the n_probe nearest coarse clusters to the query.
2. Compute PQ-coded distances to all database vectors in those clusters.
3. Return top-K nearest.

This composite achieves both the partitioning savings (only search a fraction of the database) and the per-vector compression savings.

5. Hyperparameters

Hyperparameter	Typical range	Effect
M (subspaces)	8 to 64	More subspaces = more bytes per code, better accuracy.
k (centroids per subspace)	256 (often fixed)	Larger k improves accuracy but slows the lookup table.
Sub-vector dimension d/M	4 to 16	Smaller subvectors have less structure to exploit.
n_probe (in IVF-PQ)	1 to 100	More probes search more clusters; higher recall at higher cost.

The standard parameter choices for production: M = 16, k = 256, giving 16-byte codes. For higher accuracy, M = 32 or M = 64.

6. When to Use PQ

PQ is appropriate when:

• You have a billion-vector database and cannot fit full-precision vectors in memory.
• You can tolerate small recall loss (typically a few percent below full-precision search).
• You can afford the offline training time (k-means on each subspace).

PQ is the canonical solution for billion-scale ANN. For smaller datasets (millions of vectors) where full-precision indexing fits in memory, HNSW alone (without PQ compression) gives better recall.

7. Strengths

• Massive compression — typical 50–500× memory reduction.
• Sub-millisecond per-query latency for billion-vector indexes.
• Composes with other ANN structures (IVF, HNSW).
• Mature implementation in FAISS and ScaNN.

8. Weaknesses

• Lossy compression — small recall loss compared to full-precision search.
• Training required — k-means on each subspace, possibly expensive.
• Sub-vector dimensionality matters — features that span subspace boundaries are not well captured.
• Optimization trade-off space is large — many hyperparameters interact.

9. See Also

• FAISS — primary library implementing PQ
• ScaNN — Google’s alternative with anisotropic PQ variant
• Inverted File Index — coarse partitioning often combined with PQ
• HNSW — graph-based ANN alternative; can be combined with PQ
• Two-Tower Retrieval Model — primary recommender consumer
• Recommender Algorithms Catalog
• Recommender Systems