Product Quantization (PQ)

The foundational step of PQ is decomposing the original high-dimensional vector space into M distinct subspaces. A D-dimensional vector is split into M subvectors, each of dimension D/M. This decomposition transforms the problem of quantizing a single high-dimensional space into quantizing multiple lower-dimensional subspaces, which is statistically and computationally more tractable. For example, a 128-dimensional vector might be split into M=8 subvectors of 16 dimensions each.

For each of the M subspaces, a separate codebook is learned via k-means clustering on a representative dataset. Each codebook contains k centroid vectors (e.g., k=256). This process quantizes the continuous subspace into a finite set of representative points. The key is that k is kept small (e.g., 256 centroids, representable by an 8-bit integer), but because quantization is performed independently per subspace, the total number of possible centroids across all subspaces is k^M, enabling an astronomically large effective vocabulary (e.g., 256^8 possibilities) with only M * k * (D/M) storage.

To encode a new vector, it is first split into M subvectors. Each subvector is then assigned to the nearest centroid in its corresponding subspace codebook. This assignment yields an integer index (0 to k-1) for each subspace. The final PQ code for the original vector is the concatenation of these M indices. This results in an extremely compact representation: the vector is stored not by its D floating-point values, but by M integers (e.g., 8 bytes for M=8, k=256).

ADC is the efficient distance calculation method that makes PQ practical for search. During query time, the uncompressed query vector is split into M subvectors. Precomputed distance tables are created: for each subspace m, a table of the distances between the query's subvector and all k centroids in that subspace's codebook is computed and stored. To estimate the distance between the query and a database vector (represented by its M centroid indices), the system performs a lookup: for each subspace m, it fetches the precomputed distance corresponding to the database vector's centroid index for that subspace. The total distance is the sum of these M looked-up values. This replaces an expensive D-dimensional distance calculation with M table lookups and additions.

IVFPQ is a standard, production-grade indexing structure that combines PQ with a coarse quantizer. The vector space is first partitioned using a coarse k-means clustering (with a relatively small number of centroids, e.g., 1024). Each vector is assigned to its nearest coarse centroid, and all vectors in a cluster are stored in an inverted list. Product Quantization is then applied residually: the difference (residual) between each vector and its coarse centroid is encoded using PQ. During search, the system only probes the inverted lists of the query's nearest coarse centroids (non-exhaustive search), then uses ADC on the PQ codes within those lists. This two-tiered approach provides a superior trade-off between search accuracy, speed, and memory usage.

OPQ addresses a key limitation of standard PQ: the arbitrary splitting of dimensions into subspaces may group highly correlated and uncorrelated dimensions together, reducing quantization efficiency. OPQ precedes the PQ encoding with a learned linear transformation (an orthogonal rotation matrix) of the original vector space. This rotation is optimized to minimize the quantization error after subsequent PQ. The goal is to make the subspaces more independent and the data within each subspace more amenable to clustering. In practice, OPQ can significantly improve the accuracy of compressed retrieval for the same memory budget.

Post-Training Quantization is a model compression technique that reduces the numerical precision of a trained neural network's weights and activations after training is complete. Common reductions are from 32-bit floating-point (FP32) to 16-bit (FP16) or 8-bit integers (INT8).

• Goal: Decrease model memory footprint and accelerate inference.
• Contrast with PQ: PTQ quantizes the model parameters (weights) of a neural network (like an embedding model). PQ quantizes the output vectors (embeddings) produced by the model for storage and search. They operate at different stages of the pipeline: PTQ optimizes the generator of vectors, while PQ optimizes the storage and retrieval of the vectors themselves.

A dense vector index is any database index specifically optimized for storing and querying dense vector embeddings. It is the abstract category that includes all structures like HNSW graphs, IVF lists, and PQ codebooks. The index's primary job is to solve the nearest neighbor search problem at scale.

• Core Challenge: The "curse of dimensionality" makes exact search intractable for large datasets.
• Solutions: Approximate algorithms that trade perfect accuracy for speed and memory efficiency.
• PQ's Role: PQ is a compression method used within a dense vector index. It is not a standalone search index. An index structure (like IVF) uses PQ codes to represent compressed vectors, enabling the index to hold billions of vectors in RAM.

The Inverted File index is a two-stage search structure commonly used with PQ. It first partitions the vector space into Voronoi cells using k-means clustering (the coarse quantizer). Each cell has an inverted list containing the IDs of vectors belonging to it.

• Search Process: 1) Find the nearest nprobe cells to the query. 2) Search only the vectors within those cells.
• Efficiency: Dramatically reduces the number of vectors compared during search.
• Standard Combination: IVF-PQ is a canonical architecture. Vectors in each IVF list are stored using PQ codes. The query is quantized by the same PQ codebooks, and distances are computed efficiently using lookup tables, searching only within the probed IVF cells. This combines coarse filtering (IVF) with compressed distance computation (PQ).