Product Quantization: Vector Compression for ANN Search › Product Quantization

In the previous two chapters, we explored IVF indexes and HNSW graphs, two strategies that reduce the number of comparisons needed to find approximate nearest neighbors. But there is another bottleneck we have not addressed: even when you only compare a query against a small fraction of your index, each comparison still requires loading a full 768-dimensional float32 vector from memory and computing a dot product. When your index holds tens of millions of embeddings, that memory footprint alone can exceed the capacity of a single machine.

Product Quantization (PQ) attacks this problem from a different angle: rather than reducing the number of comparisons, PQ reduces the cost and size of each comparison. It compresses each embedding from hundreds of floating-point numbers down to a handful of small integers, achieving compression ratios of 10x to 100x while preserving enough geometric structure to compute useful approximate distances. The resulting index can fit in RAM where a full-precision index would require a distributed cluster.

Think of PQ as giving each vector a compact postal address rather than GPS coordinates. Instead of storing the precise latitude and longitude of every building in a city, you store only the zip code and block number. You lose some precision, but you gain the ability to store every address in the city in a pocket notebook. When someone asks "which buildings are near this location?", you can narrow the search to a few zip codes and find good candidates without ever loading the full coordinate database.

The insight that makes PQ so powerful is the combination of two ideas. First, the high-dimensional space can be factored into independent lower-dimensional subspaces, where each subspace is much easier to quantize accurately than the full space. Second, distances in the full space decompose exactly across those subspaces, so you can estimate the full distance by summing independently precomputed per-subspace distances. This second property is what allows the entire expensive computation to happen once per query rather than once per database vector, cutting the inner loop to a series of simple memory reads.

To understand why those two ideas combine to produce such dramatic speedups, you need to understand the geometry of quantization, why the product decomposition matters, and how the resulting lookup-table machinery achieves both memory compression and fast distance estimation. This chapter covers all three: how PQ codebooks are learned, how distances are approximated efficiently with Asymmetric Distance Computation, and how PQ combines with IVF to give you both reduced comparisons and reduced memory at scale.

The practical stakes are real. A production RAG system indexing 500 million document chunks at 768 dimensions needs roughly 1.5 TB of RAM just to hold the raw embeddings, which forces a distributed deployment. The same index with PQ at $M = 96$ fits in 48 GB on a single server. This reduction can turn a distributed system that requires an infrastructure team into one that a single engineer can deploy and operate.