Product Quantization (PQ)

The core mechanism of PQ is dimensionality splitting. A D-dimensional vector is divided into M disjoint sub-vectors of dimension D/M. Each sub-vector is then quantized independently using its own codebook of k centroids. This transforms the original vector into a compact tuple of M codebook indices, reducing storage from D×32 bits to M×log₂(k) bits. For a 128-dimensional vector split into 8 sub-vectors with 256 centroids each, the compressed representation requires only 64 bits—a 64× compression ratio.

Each sub-space requires a codebook—a set of representative centroids learned offline using k-means clustering on a training set of sub-vectors. The process:

• Partition the training vectors into their M constituent sub-vectors
• Run independent k-means on each sub-space to produce k centroids
• Store the M codebooks as the quantization model

The quality of the codebook directly determines search accuracy. Typically, k=256 is used, meaning each sub-vector index fits in a single byte, enabling extremely cache-friendly memory layouts.

During query time, PQ employs Asymmetric Distance Computation (ADC) to approximate distances without decompressing the database vectors. The query vector is split into sub-vectors, and the exact distance from each query sub-vector to every centroid in the corresponding codebook is pre-computed into a lookup table. For each compressed database vector, the approximate distance is assembled by summing the pre-computed distances indexed by the stored codes. This avoids the costly operation of reconstructing the full vector, achieving sub-linear search complexity.

PQ delivers dramatic memory savings critical for billion-scale vector search. A typical 1024-dimensional float32 vector consumes 4 KB. With PQ using M=64 sub-vectors and k=256 centroids, the compressed representation requires only 64 bytes—a 64× reduction. For 1 billion vectors, this shrinks memory from 4 TB to 62.5 GB, enabling the entire index to reside in RAM on a single high-memory server. This eliminates the latency penalty of disk-based retrieval and makes real-time similarity search economically viable.

PQ introduces a tunable accuracy-efficiency trade-off governed by two parameters:

• M (number of sub-vectors): Higher M increases compression but reduces the dimensionality of each sub-space, potentially degrading distance approximation quality
• k (codebook size): Larger k improves quantization fidelity but increases codebook storage and lookup costs

Typical configurations balance M between D/8 and D/2. For exact search, PQ serves as a coarse quantizer in inverted file systems, where candidate vectors are first filtered by a separate IVF index before PQ-based distance refinement. This two-stage approach routinely achieves >95% recall@10 with sub-millisecond latency.

PQ is rarely used in isolation for large-scale search. The IVF-PQ architecture combines an Inverted File (IVF) index for coarse partitioning with PQ for fine-grained compression:

• A coarse quantizer partitions the vector space into Voronoi cells
• Each database vector is assigned to its nearest coarse centroid and stored in the corresponding inverted list
• Within each list, vectors are stored in PQ-compressed form
• At query time, only the nprobe nearest coarse centroids are visited, and ADC is applied to the compressed vectors in those lists

This hierarchical approach enables billion-scale ANN search with memory footprints measured in tens of gigabytes.

The algorithmic category that Product Quantization serves. ANN trades a small, controlled amount of recall accuracy for massive gains in query speed and memory efficiency. Exact search scales linearly with dimensionality and dataset size, becoming prohibitive beyond millions of vectors. ANN algorithms, including those leveraging PQ, achieve sub-linear or logarithmic time complexity.

• Core Trade-off: Speed and memory vs. perfect accuracy
• Common Use: The retrieval step in RAG pipelines
• Key Metric: Recall@k (e.g., 99% recall with 10x compression)

The dense, low-dimensional numerical representation that Product Quantization compresses. Embeddings are generated by encoder models (e.g., text embedding models, CLIP for images) and capture semantic relationships in a continuous vector space. Dimensionality typically ranges from 384 (MiniLM) to 4096 (larger models), directly impacting PQ's sub-vector partitioning strategy.

• Typical Dimensions: 768 (BERT-base), 1536 (Ada-002)
• Data Type: Usually float32, consuming 4 bytes per dimension
• PQ Impact: A 1536-dim float32 vector (6KB) can be compressed to ~256 bytes

A specialized data management system that indexes and queries high-dimensional embeddings while maintaining cryptographic privacy. Product Quantization introduces unique challenges in encrypted contexts because PQ centroids and codebooks constitute learned representations of the data distribution, which may leak information under certain threat models.

• Challenge: PQ codebooks are derived from plaintext data
• Mitigation: Train codebooks on public or synthetic data before encryption
• Integration: Combine with Homomorphic Encryption for distance computation over PQ codes