Product Quantization (PQ)

The fundamental first step where a D-dimensional vector is split into m distinct subvectors, each of dimension D/m. This decomposition treats the high-dimensional space as a Cartesian product of lower-dimensional subspaces. The critical assumption is that these subspaces are statistically independent, allowing them to be quantized separately. This reduces the complexity of learning a single quantizer for the entire space from an intractable k^D possibilities to a manageable m * k^(D/m).

For each of the m subspaces, a separate codebook is learned, typically using k-means clustering on a training set of subvectors. Each codebook contains k centroid vectors (e.g., k=256). During compression, every subvector of a database vector is replaced by the index (0 to k-1) of its nearest centroid in that subspace's codebook. Thus, a full vector is represented by a concatenation of m indices, forming a compact PQ code.

The standard method for querying a PQ-compressed database. The query vector remains uncompressed. Distances are approximated by:

• Decomposing the query into m subvectors.
• Pre-computing the distance between each query subvector and all k centroids in the corresponding subspace codebook, resulting in m lookup tables.
• For each database item, its PQ code (m indices) is used to look up and sum the m partial distances from these tables. This asymmetric approach (raw query vs. compressed DB) yields more accurate distances than symmetric computation between two compressed vectors.

PQ achieves extreme compression. Storing a full-precision (e.g., 32-bit float) D-dimensional vector requires 32 * D bits. A PQ code with m subvectors and k=256 centroids requires only m * 8 bits (since 256 indices need 8 bits each).

Example: A 128-D vector (4096 bits) compressed with m=8, k=256 uses a 64-bit (8-byte) PQ code, achieving a 64:1 compression ratio. This enables storing billions of vectors in RAM, making exhaustive ADC search possible where a full-precision index would not fit.

PQ is rarely used alone for large-scale search due to the linear O(N) cost of ADC. It is combined with a coarse quantizer (like IVF) to create a multi-level index (IVFPQ or IVFADC).

• First Level (IVF): A coarse quantizer (e.g., k-means with 1024 clusters) partitions the database into Voronoi cells.
• Second Level (PQ): Vectors within each cell are compressed using PQ.
• Search: For a query, only vectors in the nearest few cells are decompressed and ranked using ADC. This combines non-exhaustive search with compressed domain comparison, enabling fast, billion-scale ANN.

PQ involves inherent lossy compression, creating a trade-off governed by its parameters:

• Number of Subvectors (m): Higher m increases code length and memory usage but provides finer quantization, improving accuracy.
• Centroids per Subspace (k): Higher k (e.g., 256 vs. 16) dramatically increases accuracy but also expands the pre-computed distance lookup tables, slightly increasing query latency.
• The primary speed advantage comes from the reduction in memory bandwidth (reading compact codes) and the use of efficient table lookups for distance computation instead of full floating-point operations.

PQ is the core compression layer in large-scale vector databases like Milvus, Weaviate, and Qdrant. It enables storing billions of embeddings in RAM by reducing memory footprint by 10x to 30x. For example, a 128-dimensional float32 vector (512 bytes) can be compressed to an 8-byte PQ code. This compression is essential for in-memory indices that power real-time semantic search across massive datasets.

Major platforms use PQ to power user and item embedding retrieval. The technique is integral to Faiss and ScaNN indices deployed at Meta and Google for:

• Social media feed ranking: Finding similar content embeddings.
• E-commerce product recommendations: Retrieving similar item vectors from catalogs of millions of products.
• Video/content suggestion: Matching user interest profiles to content embeddings. PQ allows these systems to perform millisecond-latency searches over embedding spaces with hundreds of millions of vectors.

PQ compresses embeddings from CLIP, DALL-E, and other multimodal models, enabling unified search across text, image, and audio. Applications include:

• Text-to-image retrieval: Finding relevant images from a compressed gallery using a text query embedding.
• Reverse image search: Compressing image embeddings for fast lookup.
• Audio fingerprinting: Storing compressed acoustic embeddings for music or sound identification. The subspace quantization of PQ preserves the relational structure necessary for cross-modal alignment.

PQ is rarely used alone. Its most powerful application is in composite indices, particularly the IVFPQ (Inverted File with Product Quantization) architecture, which combines:

1. Coarse Quantizer (IVF): Partitions the dataset into Voronoi cells.
2. PQ Compression: Compresses vectors within each cell. This hybrid approach, implemented in Faiss's IndexIVFPQ, enables two-stage search: first find the most promising cell(s), then perform efficient distance computations using PQ codes within those cells. This achieves an optimal trade-off between recall, speed, and memory.

For edge deployment on mobile phones, IoT devices, and embedded systems, PQ drastically reduces the model footprint for neural network embeddings. Use cases include:

• On-device photo search: Compressing personal photo library embeddings.
• Keyword spotting: Storing compressed audio embeddings for wake-word detection.
• Privacy-preserving biometrics: Storing compressed face or voice templates locally. By converting float embeddings to short integer codes, PQ minimizes RAM usage and power consumption, making ANN feasible on resource-constrained hardware.

Beyond pure search, PQ compresses high-dimensional feature vectors in ML training and inference pipelines:

• Caching deep features: Storing intermediate layer outputs from vision models for transfer learning.
• Dimensionality reduction for classifiers: Providing a compressed, dense input representation.
• Anomaly detection: Maintaining a compressed database of normal pattern embeddings for comparison. This use case highlights PQ's role as a general-purpose lossy compression codec for continuous vector data, analogous to JPEG for images.

An Inverted File Index (IVF) is a two-stage indexing structure that partitions a vector dataset into Voronoi cells using a coarse quantizer (like k-means). For a query, it searches only within the most promising cell(s), dramatically reducing the search space. IVF is often combined with PQ in the IVFADC (Inverted File with Asymmetric Distance Computation) index, where IVF handles coarse retrieval and PQ compresses the vectors within each cell for efficient storage and distance computation.

Asymmetric Distance Computation (ADC) is the distance calculation method used when querying a PQ-compressed index. It computes the distance between a raw (uncompressed) query vector and a database vector represented by its PQ code. This is more accurate than Symmetric Distance Computation (SDC), which would compare two compressed vectors. ADC is key to maintaining high recall while benefiting from PQ's massive compression, as it uses higher-fidelity information from the query.

Hierarchical Navigable Small World (HNSW) is a state-of-the-art, graph-based ANN algorithm. It constructs a multi-layered graph where long-range connections in higher layers enable fast, logarithmic-time traversal, while lower layers provide high accuracy. HNSW is often used as a standalone index but can be combined with PQ (e.g., in Faiss as IndexHNSWPQ) to create a memory-efficient graph index, where the graph nodes store PQ codes instead of full vectors.

Locality-Sensitive Hashing (LSH) is a different family of ANN techniques based on probabilistic hashing. It uses hash functions designed so that similar vectors map to the same hash bucket with high probability. Unlike PQ, which is a lossy compression technique, LSH is a filtering mechanism. Searches only compare vectors within the same or neighboring buckets. LSH is generally less memory-efficient than PQ for very high-dimensional data but offers different trade-offs in build time and simplicity.

The recall-precision trade-off is the fundamental compromise in ANN search. For PQ-based indexes, this trade-off is tuned by several parameters:

• Number of Probes (nprobe) in IVF: Searching more cells increases recall but slows the query.
• PQ Configuration: More subspaces (m) and centroids (k*) improve reconstruction fidelity (aiding recall) but increase memory and distance computation cost.
• ADC vs. SDC: Using Asymmetric Distance Computation improves accuracy (precision of the distance metric) at a computational cost. System designers must balance these knobs against latency and resource constraints.