Product Quantization (PQ)

The core mechanism of PQ involves splitting a high-dimensional vector (e.g., 1024 dimensions) into M distinct, lower-dimensional sub-vectors (e.g., 8 sub-vectors of 128 dimensions each). This decomposition is the foundational step that makes independent quantization possible. The original vector is reconstructed by concatenating the quantized representations of its sub-vectors.

For each of the M sub-spaces, a separate codebook is learned using k-means clustering on the training data. Each codebook contains k centroid vectors (e.g., 256 centroids). During quantization, each original sub-vector is replaced by the ID of its nearest centroid in that sub-space's codebook. This replaces floating-point vectors with compact integer codes.

PQ achieves massive compression by storing only the centroid IDs instead of the original floating-point vectors.

• Original vector: 1024 dimensions × 4 bytes (float32) = 4096 bytes
• PQ-compressed: 8 sub-vectors × 1 byte (for k=256) = 8 bytes This represents a 512x reduction in storage, enabling billion-scale vector indexes to fit entirely in RAM.

To perform similarity search without decompressing the entire database, PQ uses Asymmetric Distance Computation. The query vector is kept in full precision and split into sub-vectors. The distances between each query sub-vector and all centroids in the corresponding codebook are pre-computed into a lookup table. The distance to any compressed database vector is then approximated by summing the pre-computed distances from the lookup table using the stored centroid IDs.

PQ is a lossy compression method. The approximation error is controlled by two hyperparameters:

• M (number of sub-vectors): Fewer sub-vectors means coarser quantization and higher compression but lower accuracy.
• k (number of centroids per codebook): More centroids provide finer granularity but require more bits per code (e.g., k=256 requires 8 bits). Tuning these parameters balances the memory-accuracy trade-off for a specific application.

PQ is often combined with an Inverted File (IVF) structure to avoid exhaustive search. The vector space is first partitioned into Voronoi cells using coarse quantization. A query only visits the nearest cells. Within each cell, vectors are stored in PQ-compressed form. This two-stage approach—coarse partitioning followed by fine PQ compression—is the foundation of the IVFPQ index, a standard for billion-scale ANN search.

The class of algorithms that trade a small amount of accuracy for significant speed improvements when finding the closest vectors to a query in high-dimensional embedding spaces. PQ is a compression technique that enables ANN indexes to store vectors in memory, but the ANN algorithm itself—such as HNSW or IVF—is responsible for the actual search traversal. Without ANN, exhaustive search over PQ-compressed vectors would still be computationally prohibitive at scale.

A partitioning strategy that clusters the vector space into Voronoi cells using k-means, assigning each vector to its nearest centroid. At query time, only a small number of cells are searched. IVF is the most common pairing with Product Quantization, forming the IVFPQ index. The IVF coarse quantizer narrows the search scope, while PQ compresses the residual vectors within each cell, combining to deliver sub-linear search complexity with a drastically reduced memory footprint.

A simpler compression alternative that maps each continuous floating-point dimension to a discrete integer representation, typically converting 32-bit floats to 8-bit integers. Unlike PQ, SQ does not decompose the vector into sub-vectors, making it less aggressive in compression but faster to encode and decode. SQ is often used as a baseline: it achieves a 4x memory reduction with minimal accuracy loss, while PQ can achieve 8-16x or more by exploiting subspace structure.

The standard query-time distance estimation method for PQ. In ADC, the query vector is not quantized; instead, the distances between the query's sub-vectors and all centroids in each codebook are pre-computed into lookup tables. The distance to a database vector is then approximated by summing the corresponding pre-computed distances. This asymmetry preserves more information from the query, yielding higher search accuracy than the symmetric variant where both query and database vectors are quantized.

An enhancement to standard PQ that learns an orthogonal rotation matrix applied to the vector space before subspace decomposition. This rotation decorrelates dimensions and balances the variance across sub-vectors, ensuring that each codebook captures roughly equal information. OPQ significantly reduces quantization error compared to naive PQ, especially for data with correlated dimensions, and is a default preprocessing step in FAISS for maximum recall at a given compression rate.

A multi-stage compression approach where the error between the original vector and its first-level quantization is quantized by a second codebook, and so on. Unlike PQ, which partitions the vector space into orthogonal subspaces, residual quantization applies successive corrections to the full vector. This hierarchical refinement can achieve lower distortion than PQ for a given bitrate, but lacks the fast distance computation structure that makes PQ so efficient for ANN search.