Product Quantization (PQ)

The original D-dimensional vector is split into M disjoint subvectors of dimension D/M. Each subvector is quantized independently using its own codebook of k centroids. This Cartesian product structure means the effective number of representable vectors is k^M, achieving exponential compression with linear codebook storage. For example, a 128-dimensional vector split into M=8 subvectors with k=256 centroids per subspace can represent 256^8 distinct combinations while storing only 8×256 centroids.

Each subspace codebook is trained independently using k-means clustering on the subvectors extracted from a representative training set. The Lloyd algorithm iteratively assigns subvectors to the nearest centroid and recomputes centroid positions until convergence. The resulting M codebooks collectively form the PQ model. During encoding, each subvector is replaced by the index of its nearest centroid, reducing storage from D×32 bits to M×log2(k) bits. A typical configuration compresses 128-dimensional float32 vectors (512 bytes) to just 8 bytes.

During query time, PQ employs asymmetric distance computation (ADC) to approximate distances without decompressing stored vectors. The query vector is split into subvectors, and the distance from each query subvector to every centroid in the corresponding codebook is precomputed into a lookup table of size M×k. For each database vector, the approximate distance is computed by summing M table lookups using the stored centroid indices. This reduces distance computation from O(D) floating-point operations to O(M) integer lookups and additions, achieving orders-of-magnitude speedup.

PQ achieves compression ratios of 8× to 64× while preserving semantic search quality. A billion 128-dimensional float32 vectors require 512 GB uncompressed. With PQ using M=64 and k=256 (8-bit codes), each vector compresses to 64 bytes, reducing the total to 64 GB—fitting entirely in RAM on a single high-memory server. This eliminates the need for disk-based retrieval and enables sub-millisecond approximate distance computations across billion-scale collections.

Standard PQ assumes subspace independence, which is suboptimal when dimensions are correlated. OPQ applies an orthogonal rotation matrix R to the vectors before subspace decomposition, minimizing quantization distortion by aligning the data distribution with the coordinate axes. The rotation is learned jointly with the codebooks using alternating optimization. OPQ consistently reduces mean squared error by 20-30% compared to vanilla PQ at the same bitrate, making it the default choice in production systems like FAISS.

For billion-scale datasets, exhaustive search even with PQ is too slow. IVFPQ combines an inverted file index with PQ compression. The vector space is first partitioned into L Voronoi cells using coarse k-means. During indexing, each vector is assigned to its nearest cell and stored with its PQ code. At query time, only the nprobe nearest cells are searched—typically 1-10% of the dataset. This two-stage approach reduces search scope while PQ handles compression within each cell, enabling interactive latency on billion-vector indices.

The primary application of PQ is enabling exact nearest neighbor search to approximate brute-force accuracy while using a fraction of the RAM. By compressing dense embeddings from 1024 floats (4KB) to 64 bytes, a billion-vector index fits in 64GB of RAM instead of 4TB.

• FAISS IndexIVFPQ: Combines inverted file indexing with PQ for sub-millisecond latency
• Disk-backed search: PQ-compressed vectors allow SSD-based indices to minimize page faults
• Hybrid retrieval: PQ-compressed dense vectors fused with sparse BM25 scores using Reciprocal Rank Fusion

PQ is critical for deploying neural models on edge hardware with constrained SRAM. By quantizing weight matrices and embedding lookup tables, models that require hundreds of megabytes can execute within the tight memory budgets of microcontrollers and mobile NPUs.

• TinyML deployment: PQ-compressed embeddings for keyword spotting on ARM Cortex-M processors
• Mobile visual search: On-device image retrieval using PQ-quantized global descriptors
• Federated learning: Compressing model updates before transmission to reduce bandwidth costs

Modern recommender systems generate embeddings for millions of users and items. Storing these at full precision is cost-prohibitive. PQ compresses item embeddings in the candidate generation stage, allowing real-time retrieval from massive catalogs without GPU acceleration.

• Two-tower models: Compress the item tower output for fast dot-product scoring
• Cold-start mitigation: PQ codebooks can represent novel items by combining existing sub-vectors
• A/B testing infrastructure: Multiple PQ codebooks can coexist to test different quantization strategies

Bioinformatics pipelines compare massive collections of genomic sequences to find evolutionary relationships. PQ compresses sequence embeddings generated by models like ProtBERT or DNABERT, enabling rapid similarity searches across entire genomic databases without lossy decompression.

• Protein structure search: Compress fold embeddings for structural homology detection
• Metagenomic classification: PQ-accelerated k-NN classification of microbial sequences
• Variant effect prediction: Rapid lookup of known variant embeddings against reference databases

In cybersecurity and industrial IoT, PQ enables streaming data points to be compared against a compressed history of normal behavior. Anomalies are flagged when the asymmetric distance computation between a full-precision query vector and PQ-compressed database vectors exceeds a threshold.

• Network intrusion detection: Compare flow embeddings against compressed baselines
• Predictive maintenance: Sensor telemetry embeddings quantized for edge gateways
• Financial fraud: Transaction embeddings compressed for real-time scoring pipelines

PQ bridges modalities by compressing embeddings from different encoders into a shared quantized space. A text query can retrieve images, or an audio clip can find related video frames, all operating on PQ-compressed indices that unify the multimodal embedding space.

• Text-to-image search: CLIP embeddings compressed with PQ for large-scale visual search
• Audio fingerprinting: Compressed audio embeddings for copyright detection
• Video moment retrieval: Frame-level embeddings quantized for temporal localization queries