Product Quantization: Vector Compression for ANN Search › Summary

Product Quantization compresses high-dimensional vectors into compact codes by splitting each vector into $M$ subvectors and replacing each with the index of its nearest centroid in a learned codebook:

• Codebook learning runs k-means independently in each of the $M$ subspaces on a sample of your training data. Each subspace gets $K$ centroids (typically $K = 256$ for one-byte codes). The codebooks must match your data distribution; mismatched codebooks inflate quantization error and reduce recall.
• Encoding replaces each subvector with its centroid index, compressing a float32 vector of $d$ dimensions (which requires $d \times 4$ bytes) to $M$ bytes (one byte per subspace when nbits=8), giving a compression ratio of $4d/M$. Encoding happens once at index build time and the result is stored as compact integer codes.
• Asymmetric Distance Computation precomputes a lookup table of distances from the query to all centroids in each subspace, then reduces each database comparison to $M$ table lookups and additions. The lookup tables fit in CPU cache, making ADC limited by memory bandwidth rather than arithmetic throughput.
• The recall-compression trade-off is governed by the total code length $M \cdot \text{nbits}$. At fixed nbits, more subspaces mean more bytes, less compression, lower reconstruction error, and generally higher recall. For 768-dimensional embeddings with nbits=8, $M = 48$ and $M = 96$ correspond to 48-byte and 96-byte codes respectively.
• IVFPQ combines coarse partitioning (IVF) with compression (PQ), achieving both fewer comparisons and smaller memory footprint. This is the dominant configuration in production vector search systems, used by Pinecone, Weaviate, Milvus, and the FAISS library.
• At scale, PQ is what makes billion-vector indexes feasible on a single server, transforming a distributed-computing problem into one that runs on commodity hardware. The practical difference between a 3 TB flat index and a 48 GB PQ index is the difference between a cluster deployment and a single machine.