Product Quantization (PQ)

The core mechanism of PQ involves splitting a D-dimensional vector into M distinct sub-vectors of dimension D/M. Each sub-vector is then independently quantized using its own codebook. This decomposition transforms the exponential storage problem of quantizing a single high-dimensional space into a linear combination of smaller, manageable quantization problems, enabling efficient approximate distance computation.

Each sub-space is quantized by learning a codebook of k centroids using the K-Means clustering algorithm on a training set of sub-vectors. The result is M distinct codebooks, each containing k reproduction values. A full vector is then represented not by its original floating-point values, but by a short code composed of the indices of the nearest centroids in each sub-space.

To perform efficient similarity search, PQ employs Asymmetric Distance Computation. The query vector is not quantized; only the database vectors are compressed. The distance between a query and a database vector is approximated by summing the squared distances between the query's sub-vectors and the corresponding centroids indexed by the database code. This avoids the additional quantization error that would be introduced by compressing the query.

PQ achieves extreme compression. A standard 1024-dimensional float32 vector requires 4096 bytes. Using PQ with M=64 sub-vectors and k=256 centroids, each sub-vector index requires only 8 bits (1 byte). The total storage per vector collapses to just 64 bytes—a 64x reduction. This allows billion-scale vector indexes to reside entirely in RAM, eliminating costly disk I/O during search.

Distance computation is accelerated by pre-calculating a distance lookup table for each query. For a given query, the distance from each of its M sub-vectors to all k centroids in the corresponding codebook is computed once. The approximate distance to any database vector is then simply the sum of M pre-computed table lookups, reducing the complexity from O(D) to O(M) per distance calculation.

A core limitation of standard PQ is that the arbitrary axis-aligned sub-space decomposition may not align with the data's natural distribution. Optimized Product Quantization addresses this by learning an orthogonal rotation matrix applied to the data before splitting. This rotation minimizes quantization distortion by aligning the principal components of the data with the sub-space boundaries, significantly improving recall for the same compression ratio.

The simplest form of vector compression that maps 32-bit floating-point values to 8-bit integers. Unlike PQ, SQ operates on individual dimensions rather than sub-vectors.

• Mechanism: Computes min/max per dimension, then linearly maps floats to 0-255
• Compression Ratio: 4x reduction (32-bit to 8-bit)
• Trade-off: Lower recall than PQ but zero training overhead
• Use Case: Rapid prototyping and scenarios where training data is unavailable

A two-stage index combining IVF partitioning with PQ compression. IVF performs coarse clustering to narrow the search space, while PQ compresses the residual vectors within each cluster.

• Indexing: K-means partitions vectors into Voronoi cells; PQ encodes residuals
• Search: Probe nearest nprobe cells, then compute asymmetric distance with PQ codes
• Scale: Handles billion-scale datasets on a single machine
• Memory: Typical configuration uses 64-bit codes for 128-dimensional vectors

An alternative to quantization-based compression that uses random projection to hash similar vectors into the same buckets. Unlike PQ, LSH provides theoretical guarantees on collision probability.

• Hash Family: Uses random hyperplanes for cosine similarity or p-stable distributions for L2
• Amplification: Stacks multiple hash tables (AND-OR construction) to tune precision/recall
• Limitation: Requires more memory than PQ for equivalent recall; less effective on dense, high-dimensional embeddings
• When to Use: Streaming scenarios or when quantization training is impractical

A multi-stage quantization technique that iteratively quantizes the error from the previous stage. Each layer adds a codebook that captures finer detail, creating a coarse-to-fine representation.

• Process: Quantize vector → compute residual → quantize residual → repeat
• Rate-Distortion: Achieves lower distortion than PQ at equivalent bitrates
• Complexity: Decoding requires summing codes from all stages
• Application: Neural audio compression (SoundStream, EnCodec) and high-precision ANN search

A generalization of PQ where the compressed vector is the sum of multiple codewords drawn from a shared codebook, rather than concatenated from independent sub-codebooks.

• Key Difference: PQ concatenates sub-vectors; AQ sums them
• Advantage: More flexible codebook usage; each codeword can influence all dimensions
• Training: Requires beam search or greedy optimization to assign codes
• Performance: Often outperforms PQ at the same bitrate but with higher encoding cost