Product Quantization (PQ)

The core mechanism of PQ involves splitting a D-dimensional original vector into M distinct sub-vectors of dimension D/M. Each sub-vector is treated as an independent statistical entity. This decomposition breaks the exponential complexity of quantizing a single high-dimensional space into a manageable linear combination of smaller codebooks. For example, a 128-dimensional embedding is typically split into 8 sub-vectors of 16 dimensions each, allowing each sub-space to be clustered independently using k-means.

For each of the M sub-spaces, a distinct codebook of k centroids is learned offline using k-means clustering on a representative training dataset. A typical configuration uses 256 centroids per sub-space, requiring only 8 bits per sub-vector index. The final compressed representation of a vector is not the original floating-point values, but a short tuple of M integer indices—one per sub-codebook. This tuple is the PQ code, and its storage cost is M × log2(k) bits.

To perform a similarity search without decompressing the database vectors, PQ employs Asymmetric Distance Computation. The query vector remains in full floating-point precision and is split into sub-vectors. The distance from each query sub-vector to every centroid in the corresponding codebook is pre-computed and stored in a lookup table. The approximate distance to any compressed database vector is then reconstructed by summing the pre-computed distances indexed by its PQ code. This avoids expensive on-the-fly decompression.

PQ achieves compression ratios that make sovereign semantic caches economically viable. A standard 128-dimensional float32 vector requires 512 bytes of storage. With PQ using M=8 sub-vectors and k=256 centroids, the compressed representation requires only 8 bytes—a 64x reduction. For a cache of 1 billion embeddings, this reduces the storage requirement from 512 GB to just 8 GB, fitting entirely within the RAM of a single on-premises node.

PQ is a lossy compression method. The reconstruction error is directly proportional to the variance within each sub-space cluster. Increasing the number of sub-vectors M or the number of centroids k reduces distortion but increases the code size. In practice, PQ is used for Approximate Nearest Neighbor (ANN) search, not exact search. A slight loss in recall (e.g., 95% recall@10) is traded for a massive gain in speed and memory efficiency. Optimized Product Quantization (OPQ) pre-rotates the data to minimize quantization distortion.

For billion-scale datasets, a brute-force scan of PQ codes is still too slow. IVFPQ combines an inverted index with Product Quantization. The vector space is first partitioned into Voronoi cells using a coarse quantizer. A query only visits the nearest cells. Within each cell, the residual vectors (the difference between the original vector and the coarse centroid) are compressed using PQ. This two-level quantization drastically reduces the search scope while maintaining high recall.

The foundational precursor to PQ that maps entire high-dimensional vectors to a finite set of centroids from a learned codebook. Unlike PQ, VQ does not decompose the vector into sub-vectors, leading to exponential codebook growth as dimensionality increases. K-Means clustering is typically used to generate the codebook, and each original vector is replaced by the index of its nearest centroid. While memory-efficient for low dimensions, VQ suffers from severe distortion in high-dimensional spaces, making PQ the preferred choice for modern embedding compression.

An enhancement to standard PQ that applies an orthogonal rotation matrix to the vector space before decomposition and quantization. This rotation minimizes the statistical dependence between sub-vectors, ensuring that each sub-space captures maximal variance and reducing overall quantization distortion. OPQ is particularly effective for embeddings where dimensions are correlated, such as those from transformer models. The rotation matrix is learned jointly with the codebooks during training, leading to higher recall at the same bitrate.

A graph-based indexing algorithm that constructs a multi-layered navigable small world graph where nodes represent vectors and edges connect near neighbors. While HNSW achieves state-of-the-art query speed and recall without requiring vector compression, its memory footprint is substantial due to storing full-precision vectors and graph edges. In memory-constrained sovereign deployments, PQ-compressed vectors can be stored alongside HNSW graph structures to balance speed and storage, creating hybrid indexes that leverage the strengths of both approaches.

A simpler compression alternative that quantizes each dimension independently to a lower bit depth, typically converting 32-bit floats to 8-bit integers using uniform or learned thresholds. SQ preserves the original vector dimensionality and is computationally cheaper than PQ during encoding, but achieves lower compression ratios. For sovereign caching, SQ is often used as a fast pre-check before expensive PQ distance calculations, or in scenarios where minimal accuracy loss is paramount and memory savings are secondary.