Product Quantization (PQ)

The fundamental operation that splits a D-dimensional vector into M distinct subvectors of dimension D/M. Each subvector resides in its own orthogonal subspace, allowing independent quantization. This structural assumption—that the joint distribution factorizes across subspaces—is the key to PQ's efficiency, reducing the exponential complexity of full vector quantization to a linear combination of smaller problems.

A distinct codebook of k centroids is learned for each of the M subspaces, typically via k-means clustering on the subvector training data. The full vector is then represented by a compact tuple of M centroid indices. With M=8 and k=256, a 128-dimensional float32 vector (512 bytes) compresses to just 8 bytes, achieving a 64x memory reduction.

The standard distance approximation strategy where the query vector is kept in full precision while database vectors are compressed. The query is split into subvectors, and distances to all centroids in each subspace's codebook are precomputed into lookup tables. The approximate distance to any compressed database vector is then assembled by summing M table lookups, avoiding explicit vector reconstruction.

The distortion introduced by mapping continuous subvectors to discrete centroids. This error is the primary accuracy bottleneck and is controlled by two hyperparameters:

• M (number of subspaces): More subspaces mean shorter codes but coarser quantization per subspace.
• k (codebook size): Larger codebooks reduce error but increase training time and lookup table size. The optimal configuration balances memory footprint against recall degradation for the target application.

An enhancement that applies an orthogonal rotation matrix to the original vector space before subspace decomposition. This rotation minimizes the statistical dependence between subspaces, making the factorization assumption more valid. OPQ learns the rotation jointly with the codebooks, significantly reducing quantization error for correlated dimensions without increasing the code length.

The computational core of PQ search. For a query, M lookup tables of size k are precomputed once. The approximate distance to any database vector requires only M additions—reading precomputed values from each table using the stored centroid indices. This replaces a full D-dimensional float32 distance computation with simple integer-indexed additions, achieving orders-of-magnitude speedups on modern CPUs with SIMD.

The Inverted File with Product Quantization (IVFPQ) index is the canonical production deployment of PQ. It combines a coarse quantizer (typically IVF) for partitioning the vector space with product quantization for compressing residual vectors within each partition.

• Workflow: A query vector is first assigned to the nearest coarse centroid(s), then ADC is used to score PQ-compressed residuals only within those selected Voronoi cells.
• Memory Profile: A billion-scale index of 128-dimensional vectors can fit in under 64 GB of RAM, compared to 512 GB for raw float32 storage.
• Tradeoff: The coarse quantizer introduces a recall ceiling—true neighbors in unvisited partitions are missed—requiring careful tuning of the nprobe parameter.

ADC is the standard distance approximation method used with PQ-encoded databases. The query vector remains in full precision, while database vectors are represented by their PQ codes. Distances are computed using a pre-calculated lookup table.

• Mechanism: For each subquantizer, the squared distance between the query subvector and every centroid in that sub-codebook is precomputed. The distance to a database vector is then assembled by summing the appropriate lookup table entries.
• Advantage over SDC: Symmetric Distance Computation quantizes both query and database vectors, introducing error on both sides. ADC halves the quantization error by keeping the query exact.
• Computational Cost: ADC reduces distance computation from O(D) floating-point operations to O(M) table lookups and additions, where M is the number of subvectors.

The codebooks that define PQ's compression are learned offline using k-means clustering on the training distribution of subvectors. The quality of this clustering directly determines the quantization error and downstream search recall.

• Training Process: The original vector space is decomposed into M independent subspaces. For each subspace, k-means with k (typically 256) centroids is run on the corresponding subvectors from a representative training set.
• Centroid Count: Using k=256 yields 8-bit codes per subvector, aligning perfectly with byte boundaries for efficient storage and SIMD-accelerated lookup.
• Optimized Assignment: FAISS implements efficient k-means variants with mini-batch processing and GPU acceleration to handle training sets with millions of vectors across 96-dimensional subspaces.

OPQ is an enhancement to vanilla PQ that learns an orthogonal rotation matrix applied to the vector space before subspace decomposition. This rotation minimizes the quantization distortion by decorrelating dimensions across subvectors.

• Core Insight: Standard PQ assumes subspaces are statistically independent. When dimensions are correlated across subspace boundaries, quantization error increases. OPQ finds a rotation that concentrates variance within subspaces.
• Algorithm: Alternating optimization between the rotation matrix and the codebooks, minimizing the global reconstruction error. This is a non-convex problem solved via iterative Procrustes analysis.
• Practical Impact: OPQ can improve recall@10 by 5-15% at the same compression ratio, or achieve equivalent recall with 2x fewer bytes, making it a default preprocessing step in FAISS for high-accuracy deployments.

Scalar Quantization is the simpler precursor to PQ that compresses each dimension independently, mapping continuous floating-point values to discrete integer bins. It serves as a baseline and is often used for the coarse quantizer in IVF indices.

• Mechanism: Each dimension's value range is divided into uniform intervals, and values are stored as 8-bit or 4-bit integers. Reconstruction multiplies the integer by the bin width and adds the minimum offset.
• Comparison to PQ: SQ preserves the original dimensionality structure but offers lower compression ratios. A 128-dimensional float32 vector (512 bytes) becomes 128 bytes with 8-bit SQ, versus 16 bytes with 8-bit PQ using M=16.
• Use Case: SQ is preferred when the vector dimensions have clear independent semantic meaning and cross-dimensional correlation is low, or when ultra-fast decoding with minimal lookup tables is required.

In two-level indexes like IVFPQ, PQ does not compress the original vector but rather the residual vector—the difference between the original vector and its assigned coarse centroid. This residual has significantly lower variance, reducing quantization error.

• Why Residuals: The coarse quantizer captures the global structure. The residual encodes only the local deviation, which is typically concentrated near zero with a tighter distribution, making it easier for PQ codebooks to model accurately.
• Encoding Pipeline: residual = original_vector - coarse_centroid. This residual is then decomposed into subvectors and quantized using the PQ codebooks trained specifically on residuals.
• Search Impact: During ADC, the coarse centroid is added back to the PQ-reconstructed residual before computing the final distance to the query, ensuring the full vector is approximated for accurate scoring.