Product Quantization: Vector Compression for ANN Search › PQ Accuracy Trade-offs in Depth

Understanding when PQ works well and when it struggles helps you configure it appropriately. The accuracy of PQ is not a fixed property of the algorithm but a function of how well the learned codebooks match your data distribution, how many subspaces you use, and whether the geometric structure of your embeddings aligns with the product decomposition that PQ assumes.

The fundamental source of error is the quantization step: by replacing each subvector with its nearest centroid, you introduce a residual error that corrupts the distance estimate. Whether this matters for recall depends on how large the residual errors are relative to the distances separating the true nearest neighbors from their non-neighbor competitors. If the true nearest neighbor is much closer to the query than the second-closest vector, PQ can afford substantial quantization error without disrupting the ranking. If many vectors are nearly equidistant from the query, even small quantization errors can flip the ranking and cause true neighbors to be missed.

When we compress a vector using PQ, the stored centroid indices only approximate the original subvectors. The quantization error measures how much information is lost: it is the total squared distance between each original subvector and the centroid used to represent it. Minimizing this error during codebook training (via k-means) directly improves the quality of approximate distance computations at search time. When quantization error is large, the centroids are poor representatives of the data points they are assigned to, and the approximate distances computed by ADC will deviate substantially from the true distances.

For a vector $x$ encoded as code $(k_1, \ldots, k_M)$, the quantization error is:

$$\epsilon(x) = \sum_{m=1}^{M} \left\| x^{(m)} - c_{m, k_m} \right\|^2$$

where:

• $\epsilon(x)$: the total quantization error for vector $x$, measuring how far the compressed representation deviates from the original
• $x^{(m)}$: the original (uncompressed) $m$-th subvector of $x$
• $c_{m, k_m}$: the centroid assigned to represent $x^{(m)}$, i.e., the nearest centroid found during encoding
• $\left\| x^{(m)} - c_{m, k_m} \right\|^2$: the per-subspace reconstruction error for subspace $m$

This reconstruction error is always non-negative. It does not, however, simply get added to every ADC distance. The difference between the approximate and true distances also contains a signed cross-term, derived below, so ADC can either overestimate or underestimate an individual distance. Smaller reconstruction error still tends to make the approximate distances more accurate and improve recall.

To understand how quantization error affects the approximate distance, consider that ADC computes the distance from the full-precision query $q$ to the centroid representing $x$, rather than to $x$ itself. This means the result differs from the true distance by correction terms that depend on the quantization of $x$. Specifically, the approximate distance can be written as:

$$\begin{aligned} \hat{d}(q, x) &= \sum_{m=1}^{M} \left\| q^{(m)} - c_{m,k_m} \right\|^2 && \text{(ADC uses centroid, not } x \text{)} \\ &= \sum_{m=1}^{M} \left\| (q^{(m)} - x^{(m)}) + (x^{(m)} - c_{m,k_m}) \right\|^2 && \text{(add and subtract } x^{(m)} \text{)} \\ &= \sum_{m=1}^{M} \left\| q^{(m)} - x^{(m)} \right\|^2 + 2\sum_{m=1}^{M} \langle q^{(m)} - x^{(m)},\, x^{(m)} - c_{m,k_m} \rangle + \sum_{m=1}^{M} \left\| x^{(m)} - c_{m,k_m} \right\|^2 && \text{(expand squared norm)} \\ &= d(q, x) + \epsilon_q^{\text{corr}} + \epsilon_x^{\text{corr}} && \text{(collect terms)} \end{aligned}$$

where:

• $\hat{d}(q, x)$: the approximate distance returned by ADC
• $d(q, x) = \sum_{m=1}^{M} \left\| q^{(m)} - x^{(m)} \right\|^2$: the true squared Euclidean distance between $q$ and $x$
• $\epsilon_q^{\text{corr}} = 2\sum_{m=1}^{M} \langle q^{(m)} - x^{(m)},\, x^{(m)} - c_{m,k_m} \rangle$: a cross-term arising from the interaction between the true displacement and the quantization error of $x$
• $\epsilon_x^{\text{corr}} = \sum_{m=1}^{M} \left\| x^{(m)} - c_{m,k_m} \right\|^2$: the quantization error of database vector $x$, i.e., the total squared distance between $x$ and its assigned centroids

The algebraic expansion above is more than a curiosity. It shows precisely which quantities control the quality of the approximation. The term $d(q, x)$ is the true distance, which is what we want. The non-negative term $\epsilon_x^{\text{corr}}$ depends only on how well $x$ is quantized, while the signed cross-term $\epsilon_q^{\text{corr}}$ also depends on the query and can reinforce or offset it. ADC therefore has no universal overestimation guarantee for individual query-vector pairs. When the cross-term is small in expectation, lower reconstruction error makes the approximate distances more stable and reduces ranking mistakes among nearby candidates.

Several factors degrade PQ recall. Understanding these failure modes helps you diagnose poor performance and choose the right remediation:

• Too few code bits: At fixed nbits, a small $M$ gives each vector a short code. A 128-dimensional vector with $M=2$ and nbits=8, for example, receives only 16 total bits, so each 64-dimensional subvector must be represented by one of just 256 centroids. Increasing $M$ lowers this distortion by spending more bits per vector.
• Insufficient training data: K-means needs at least $K \times$ a few hundred training points per subspace to converge well. With $K = 256$ and $M = 8$, you need on the order of 200,000 training vectors minimum. With fewer, some centroids will be initialized in empty regions and never attract any training points, leaving voids in the codebook coverage.
• Non-uniform distributions: If your embeddings have strong correlations between dimensions that span subspace boundaries, independent per-subspace quantization misses that structure. Optimized PQ (OPQ) applies a rotation to the embedding space before quantization to reduce such correlations, at the cost of a rotation step at query time.
• Mismatched preprocessing or metric: Cosine search requires consistent normalization of training, database, and query vectors. For unit-normalized vectors, exact cosine and squared-Euclidean rankings agree; without that normalization, changing metrics changes the neighbor ordering that the index is trying to preserve.

ADC keeps the query in full precision, which is why it outperforms Symmetric Distance Computation (SDC), where both the query and database vectors are quantized before comparison. With SDC, you accumulate quantization error from both sides: the query contributes its own per-subspace reconstruction errors on top of those from the database vector. Looking at the error expansion above, SDC adds an additional cross-term and an additional quantization error term for the query, making the approximation systematically worse.

In practice, ADC is almost always preferred. The only advantage of SDC is that you do not need to keep the codebooks in memory during search, which rarely matters compared to the recall cost. The memory overhead of the codebooks is negligible compared to the index itself: for $M = 96$, $K = 256$, $d^* = 8$, the codebooks occupy only $96 \times 256 \times 8 \times 4 = 786{,}432$ bytes, less than 1 MB. There is virtually never a practical reason to accept the accuracy penalty of SDC when the codebooks are so cheap to store. ADC is always the right choice unless you are operating under severe memory constraints at truly extraordinary scale.