Split a vector into subspaces, replace each chunk with a codebook id, and search a billion vectors in RAM you can actually afford.
Instead of writing down a full address, you write down the nearest landmark in each district. Much shorter to store, and close enough to find your way.
Past a few tens of millions of vectors, memory is the entire cost model, and PQ is the 32× that makes the bill survivable.
HNSW is fast but stores every full-precision vector, so memory is the wall: a billion 768-dim float32 vectors is roughly 3 TB. Product quantization attacks that directly. Split each vector into m sub-vectors, run k-means over each subspace to learn a 256-entry codebook, and store only the m byte-sized codebook ids — a 768-dim vector becomes 96 bytes instead of 3072, a 32× reduction. Distances are computed with an asymmetric lookup table: the query stays full precision, and each sub-distance is a table read rather than arithmetic. IVF adds a coarse partition first so a query only scans a few of the thousands of cells. The cost is approximation error, which is why production systems always re-score the shortlist with the exact vectors.
Product quantization compresses vectors by splitting them into sub-vectors and replacing each with the id of its nearest codebook centroid, typically 32× smaller. Distances are approximated by summing precomputed lookup-table entries, so search is both smaller and faster. Combined with an IVF partition to limit how much of the index is scanned, it's how billion-scale search fits in memory — and you always re-score the shortlist exactly to recover the lost precision.
Day 28: Product Quantization (PQ) Explained: HNSW vs IVF vs PQ vs LSH – Which Should You Use? — Cloud and Coffee with Navnit, 6:56