Quantization Error

Quantization error represents the irreversible loss of information when a high-precision vector is approximated by a discrete codebook entry. The error vector is the difference between the original vector and its quantized reconstruction.

• Mathematical definition: error = x_original - x_quantized
• Mean Squared Quantization Error (MSQE) is the standard metric for measuring distortion across a dataset
• Higher error directly correlates with degraded recall in ANN search, as distance rankings become less accurate
• The error is bounded by the Voronoi cell radius—vectors near cell boundaries suffer the most distortion

The codebook size (number of centroids) is the primary lever controlling quantization error. A larger codebook provides finer granularity but increases memory overhead and encoding cost.

• Rate-Distortion Theory: The fundamental limit describing the minimum achievable distortion for a given encoding rate
• Doubling the codebook size typically reduces MSQE by a factor dependent on the data distribution's intrinsic dimensionality
• Practical example: Product Quantization with 256 centroids per subspace achieves 8-bit encoding; increasing to 65536 centroids yields 16-bit encoding with significantly lower error
• The Lloyd-Max algorithm iteratively optimizes codebook centroids to minimize MSQE for a given distribution

Different quantization strategies produce error with distinct statistical properties, affecting how distortion propagates through multi-stage indexing pipelines.

• Product Quantization (PQ): Error is distributed across independent subspaces; the total distortion is the sum of per-subspace errors
• Residual Quantization (RQ): Error is reduced iteratively by quantizing the residual from the previous stage, producing a hierarchical error structure
• Additive Quantization: Multiple codebooks are summed to reconstruct the vector, with error concentrated in dimensions where codebooks disagree
• IVFPQ combines coarse quantization error (partition assignment) with fine quantization error (residual encoding), requiring joint optimization

Quantization error directly degrades the accuracy of approximate distance computations, which are the foundation of fast ANN search. The relationship between quantization error and distance error is non-linear.

• Asymmetric Distance Computation (ADC) reduces error impact by keeping the query vector in full precision, only quantizing database vectors
• Symmetric Distance Computation (SDC) quantizes both query and database vectors, compounding the error but enabling faster computation
• Distance approximation error grows with the L2 norm of the quantization error vector
• ScaNN's anisotropic quantization explicitly optimizes for inner product preservation rather than minimizing Euclidean reconstruction error, prioritizing search-relevant distortion

In hierarchical indices like IVFPQ, quantization error accumulates across levels. The coarse quantizer introduces partition assignment error, while the fine quantizer adds residual encoding error.

• Coarse quantization error: A query vector near a Voronoi boundary may be assigned to a suboptimal partition, causing true neighbors to be missed entirely
• Residual quantization error: Within a partition, compressed residual vectors may reorder candidate rankings
• Error compounding: The total recall loss is a function of both error sources, not simply additive
• Mitigation strategies include multi-probe search (searching multiple partitions) and re-ranking with full-precision vectors on the candidate set

Quantization error is evaluated using both reconstruction fidelity metrics and end-to-end retrieval quality metrics, as minimizing reconstruction error does not always maximize recall.

• Mean Squared Error (MSE): Average squared L2 distance between original and quantized vectors across the dataset
• Signal-to-Quantization-Noise Ratio (SQNR): Ratio of original vector power to quantization error power, expressed in decibels
• Recall@K degradation: The practical metric—measuring how many true nearest neighbors are lost due to quantization at a given K
• Rate-Distortion curves plot the Pareto frontier of compression ratio vs. distortion, guiding codebook parameter selection