The most useful compression trick in vector search has a strange little asymmetry:

keep the query as a real vector
replace every database vector with a short code

That is product quantization in its working clothes. It is not the same as saying “store fewer bits per float.” It is closer to saying: learn a small set of replacement parts for each slice of the vector, then remember which part was used in each slice.

At query time the system does not need to rebuild every stored vector. It builds a table once:

distance from query slice 1 to every slice-1 codeword
distance from query slice 2 to every slice-2 codeword
...

Then a database vector is just a few table indexes. The distance is a sum.

That is the quiet reason product quantization, usually abbreviated PQ, sits inside so many approximate-nearest-neighbor systems. The vector has been moved out of the hot loop. The distance table has replaced it.

The Codebook Is Exponential, But You Do Not Store It

Suppose a vector has dimension \(d\). Split it into \(m\) blocks:

\[x = \left(x^{(1)}, x^{(2)}, \ldots, x^{(m)}\right).\]

For each block, train a separate \(k\)-means codebook:

\[C_j = \{c_{j,1}, c_{j,2}, \ldots, c_{j,k}\}.\]

The encoder stores one integer per block:

\[z_j(x) = \arg\min_i \left\|x^{(j)} - c_{j,i}\right\|^2.\]

The reconstructed vector is the concatenation of those selected codewords:

\[\hat{x} = \left(c_{1,z_1(x)}, c_{2,z_2(x)}, \ldots, c_{m,z_m(x)}\right).\]

The full reconstruction codebook has \(k^m\) possible vectors. That sounds large, and it is the point. With \(m=8\) and \(k=256\), there are \(256^8\) possible reconstructions, but the trained object stores only \(m k\) small centroids, each living in a low-dimensional subspace. Jégou, Douze, and Schmid’s original PQ paper framed this as decomposing the space into a Cartesian product of low-dimensional subspaces, then quantizing each subspace separately.1

The database payload is even smaller. Each vector stores \(m\) codebook indices. With eight subquantizers and 256 centroids each, that is eight bytes per vector before any metadata or coarse index overhead. Compare that with a 768-dimensional float32 embedding at 3,072 bytes. The ratio is not a rounding error. It is a different storage regime.

Compression alone would be less interesting if search had to decode every candidate into \(\hat{x}\). Product quantization gets its speed from asymmetric distance computation, or ADC.2

Given a real query \(q\), precompute:

\[T[j,i] = \left\|q^{(j)} - c_{j,i}\right\|^2.\]

For a database vector with code \(z(x)\), the approximate distance is:

\[d_{\mathrm{ADC}}(q,x) = \sum_{j=1}^{m} T[j,z_j(x)].\]

No coordinate loop over \(d\). No decode required. The scan over compressed codes is mostly: read a byte, look up a float, add.

This identity is exact for the reconstructed vector:

\[d_{\mathrm{ADC}}(q,x) = \left\|q - \hat{x}\right\|^2.\]

It is only approximate relative to the original vector \(x\). That distinction is the whole bargain. PQ does not approximate the distance computation after compression; it approximates the database vector before distance computation. Faiss’s ProductQuantizer API exposes this directly: for one query it computes an \(M \times k_{\text{sub}}\) distance table whose entries are squared distances from each query subvector to each subquantizer centroid.3

The query remains uncompressed in ADC, which is why the computation is “asymmetric.” Symmetric distance computation also compresses the query, but Faiss’s recent system paper notes that most Faiss indexes prefer ADC because it keeps query-side accuracy.2

A Small PQ Machine Room

The lab below trains product quantizers on synthetic eight-dimensional embeddings. The projection is intentionally visible and small enough to audit. For each setting it:

  • generates a clustered vector database and one query,
  • optionally applies a fixed orthonormal rotation before slicing the vector,
  • trains one \(k\)-means codebook per subspace,
  • encodes every database vector as a product code,
  • compares exact nearest neighbors with ADC nearest neighbors, and
  • verifies that ADC equals distance to the reconstructed vector.

The “spread rotation” is not a full optimized product quantizer. It is a toy orthonormal mixing step that makes the same lesson visible: PQ’s split of the coordinate system is part of the model. Optimized Product Quantization later made that space-decomposition problem explicit by optimizing both the rotation and the subspace codebooks.4

query exact top-10 circle PQ top-10 square

The Table Has A Failure Mode

PQ can make a vector index feel magical because the arithmetic shrinks so cleanly. But the method has a very ordinary statistical failure mode: the codebooks are trained on a distribution.

If the training sample misses a tail, the tail will be badly reconstructed. If the embedding model changes, the codebooks may become stale. If a filter later removes most of the natural neighbors, the index might spend its approximate budget on candidates that the product quantizer thought were close before the filter was applied. In production systems PQ is often paired with a coarse candidate generator such as IVF or a graph, and then reranking with exact vectors recovers quality on a shortlist. Johnson, Douze, and Jégou’s GPU Faiss work discusses brute-force, approximate, and compressed-domain search, with product quantization appearing as one part of a larger memory-and-throughput design.5

The lab’s recall number is therefore not a universal property of “PQ with 16 codewords.” It is a property of this data distribution, this query, this axis split, this number of subquantizers, and this trained set of centroids. That is why the small frontier plot is more honest than one large headline number. Every point is a different compromise between payload bytes and neighborhood damage.

Why Rotation Matters

The Cartesian-product assumption is the beauty and the weakness of PQ.

The distance decomposition works because squared Euclidean distance is additive across disjoint coordinate blocks:

\[\left\|q - \hat{x}\right\|^2 = \sum_j \left\|q^{(j)} - \hat{x}^{(j)}\right\|^2.\]

But the data does not promise that its information is evenly divided across those blocks. If the first two dimensions carry most of the semantic variance and the remaining dimensions are quiet, then equal-size subquantizers are not equal-value subquantizers. One codebook is asked to model the hard part; the others spend their centroids on small noise.

An orthonormal rotation preserves exact distances, but it changes which coordinates fall into which subquantizer. The lab’s “spread rotation” is a fixed Hadamard-style mixing. It often helps the spiky-covariance setting because it distributes the important variance across all slices before training the sub-codebooks. It can also fail to help when the raw coordinates were already well matched to the split. That is the right moral. Rotation is not free accuracy; it is a modeling decision about where the product structure should live.

OPQ is the grown-up version of this idea: choose a transformation so the subspace quantizers waste less capacity. The CVPR 2013 paper by Ge, He, Ke, and Sun optimized product quantization by minimizing quantization distortion with respect to both the space decomposition and the codebooks.4

What I Would Audit Before Trusting It

For a real retrieval system, I would not stop at a PQ benchmark on random queries. I would keep separate ledgers:

Compression error. Measure reconstruction MSE by slice, by item family, by embedding norm, and by age of the vector. Averages hide the exact items that will become embarrassing search results.

Search recall. Measure recall at the shortlist size that the next stage actually sees. If a reranker receives 200 candidates, recall@200 is often more operationally meaningful than recall@10.

Latency and memory. Count the per-vector code payload, shared codebook overhead, graph or IVF metadata, cache behavior, and reranking reads. PQ saves the vector payload, but the whole index has more than one column in its budget.

Distribution shift. Re-train or at least re-evaluate codebooks when the embedding model, corpus mix, query mix, normalization convention, or filtering policy changes.

Distance convention. Cosine search is usually handled by normalizing vectors and using inner product or L2 on the normalized sphere. The quantizer has to be audited under the same convention the search system will use.

The little invariant in the lab is deliberately narrower: ADC equals squared distance from the real query to the reconstructed database vector. That is the piece the implementation must get exactly right. The rest is the statistical question: whether those reconstructed vectors are good enough for the search job.

The artifact ships with that invariant as executable code. In the console or in Node, ProductQuantizationLab.audit() trains 18 small PQ machines across three synthetic geometries, two coordinate systems, and three code budgets. The audit checks the product-code ranges, the distance-table shape, the non-increasing \(k\)-means distortion history, exact and ADC ranking order, byte accounting for codes and codebooks, and the frontier compression ledger. On the current build it performs 25,746 checks; the largest ADC identity error is \(2.84 \times 10^{-14}\), which is numerical roundoff rather than a search claim.

That distinction matters. A passing audit says the distance table is doing the mathematics claimed in the article. It does not say this synthetic quantizer is production-good, or that PQ alone is enough for a retrieval product. The engineering question remains empirical: once the compressed codes enter a real index, what shortlist recall, latency, memory footprint, and failure cases do you actually measure?

  1. Hervé Jégou, Matthijs Douze, and Cordelia Schmid, “Product Quantization for Nearest Neighbor Search”, IEEE TPAMI, 2011. A PubMed record for the same paper is available here. ↩

  2. Matthijs Douze et al., “The Faiss Library”, arXiv, 2024. See the sections on compression levels, vector codecs, ADC, and recall/resource metrics. ↩ ↩2

  3. Meta’s Faiss C++ documentation for faiss::ProductQuantizer, especially compute_distance_table, which defines the query-by-codeword distance table used by ADC. ↩

  4. Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun, “Optimized Product Quantization for Approximate Nearest Neighbor Search”, CVPR 2013. ↩ ↩2

  5. Jeff Johnson, Matthijs Douze, and Hervé Jégou, “Billion-scale similarity search with GPUs”, arXiv, 2017. ↩