Why architecture matters here
The architecture matters because the naive options are both unusable at scale. Exact (flat) search gives perfect recall but costs a full-dataset scan per query — fine for a million vectors, hopeless for a billion, and it stores every vector at full precision, so the RAM bill alone is prohibitive. Pure IVF without compression speeds up search but still stores full vectors, so a billion-vector index needs terabytes of RAM. Pure PQ without IVF shrinks memory but still scans every code, so query time stays linear in dataset size. IVF-PQ exists precisely because you need both sublinear search and sublinear memory, and the two techniques attack the two problems independently.
Three properties follow from the design. Search is sublinear: routing to nprobe of nlist cells means you touch a tunable, tiny fraction of the data — the single biggest speedup lever. Memory is a knob: PQ's compression ratio is set by m (number of subquantizers) and the bits per code; you dial the footprint to fit RAM, trading accuracy for size explicitly. Distance is cheap: asymmetric distance computation precomputes, once per query, a table of distances from each query sub-vector to every codebook entry, so scanning a candidate is just m table lookups and adds — no multiplications, no decompression.
The trade-off is baked into the name: this is approximate nearest neighbor. Partitioning can miss the true neighbor if it sits just across a cell boundary you didn't probe; quantization introduces error because a code is a lossy summary of a vector. So IVF-PQ trades exactness for orders of magnitude in speed and memory, and the entire operational discipline is about managing that trade — measuring recall, tuning nprobe, choosing compression, and reranking top candidates on full vectors to recover precision at the very end.
The architecture: every piece explained
Top row: the search path. A query vector in d dimensions first hits the coarse quantizer — a k-means model with nlist centroids (typically a few thousand to a few hundred thousand) that assigns the query to its nearest cells. The index is an inverted file: for each cell, a posting list of the vector ids assigned to that centroid. At query time you probe nprobe cells — the nprobe centroids closest to the query — and only their inverted lists are candidates. Inside those lists, vectors are stored as PQ codes: each original vector was split into m contiguous sub-vectors, and each sub-vector replaced by the index (usually 8-bit, so 256 entries) of the nearest entry in that subspace's codebook.
Middle row: the quantization machinery. Training PQ learns subspace codebooks: run k-means separately in each of the m sub-vector spaces to get m codebooks of 256 centroids each. To compare a query against codes, the index builds distance tables once per query: for each of the m subspaces, compute the distance from the query's sub-vector to all 256 codebook centroids — an m × 256 table. Then the ADC scan (asymmetric distance computation) estimates a candidate's distance by, for each subspace, looking up the candidate's code in the table and summing — m lookups and adds per vector, no arithmetic on the raw dimensions. 'Asymmetric' means the query stays full-precision while only the database vectors are quantized, which is more accurate than quantizing both. This yields top-k candidates by approximate distance.
Bottom rows: precision recovery and control. Because PQ distances are approximate, a rerank stage takes the top candidates (say the best few hundred), fetches their full vectors (kept on disk or in a separate store, or reconstructed), computes exact distances, and re-sorts — cheap because it runs on a short list, and it dramatically lifts precision at the top. The final result is the k nearest neighbors. The ops strip names the levers: nprobe trades recall against latency (more cells probed = higher recall, slower); m and bits-per-code trade accuracy against memory; and both the coarse quantizer and the PQ codebooks must be retrained when the data distribution drifts, or partitioning and quantization both degrade.
End-to-end flow
Trace a semantic search over 200M product embeddings, indexed with nlist=16384, m=64 subquantizers at 8 bits (so 64 bytes per vector — a ~48× compression over 768-dim float32), reranking the top 200. A user query is embedded into a 768-dim vector.
Route. The coarse quantizer compares the query to the 16,384 centroids and picks the nearest nprobe=32 — so instead of 200M candidates, the search is confined to 32 inverted lists holding, on average, ~390k vectors total (0.2% of the dataset). Build tables. The index splits the query into 64 sub-vectors of 12 dimensions each and, for each, computes distances to that subspace's 256 codebook centroids — a 64×256 table, built once. Scan. For each of the ~390k candidate codes, the ADC scan does 64 table lookups and adds to estimate its distance — hundreds of thousands of near-free operations rather than 200M full 768-dim distance computations. A running heap keeps the best 200 by approximate distance.
Rerank. Those 200 candidates' full float32 vectors are fetched and exact distances computed; the list re-sorts, correcting the cases where PQ's lossy estimate had mis-ranked near-ties. The top 10 are returned. End to end: a few milliseconds, a 64-byte-per-vector index that fits 200M vectors in ~13GB of RAM instead of ~600GB, and recall in the high 90s against exact search — tunable by turning the knobs.
Now watch the knobs bite. The team notices recall is only 91% and users complain about missed matches. They raise nprobe from 32 to 64: recall climbs to 96% because the true neighbor was sometimes in the 33rd-closest cell, but latency roughly doubles on the scan — the recall/latency trade made concrete. Separately, memory pressure forces a choice: dropping to m=32 (32 bytes/vector) halves the index size but coarsens quantization, and recall falls a couple of points — the accuracy/memory trade. Finally, six months in, the catalog shifts toward a new product category; the coarse centroids and PQ codebooks were trained on the old distribution, so new vectors cluster unevenly (some cells balloon, some empty) and quantization error rises for the new region. Recall quietly decays until the team retrains both quantizers on a current sample and rebuilds the index — the maintenance obligation the architecture imposes.