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.

IVF-PQ — cluster the space, then compress the vectors: fast, memory-tiny ANN searchcoarse quantizer narrows the search, product quantizer shrinks each vectorQuery vectord-dimensionalCoarse quantizerassign to nlist cellsProbe nprobe cellsinverted listsPQ codesm subvectors × 8-bitSubspace codebooksk-means per subvectorDistance tablesprecompute per queryADC scansum table lookupsTop-k candidatesapproximate distancesRerankexact distance on full vectorsResultk nearest neighborsOps — recall vs latency tuning (nprobe) + memory budget (m, bits) + retraining on driftinrouteread codestrainbuildlookupdecodererankreturnoperate
IVF-PQ: a coarse quantizer routes the query to a few inverted lists; within them, product-quantized codes are scanned with precomputed distance tables, and top candidates are reranked exactly.

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.

IVF-PQ worked example in faiss: recall vs nprobe and bytes per vector

IVF-PQ (inverted file with product quantization) is an approximate nearest-neighbor index: a k-means coarse quantizer splits the data into nlist cells, each vector is stored as an m-byte PQ code, and a query scans only the nprobe closest cells. Two numbers decide whether it works for you: recall@10 against exact search, and bytes per vector. The script below measures both on seeded synthetic data with faiss IndexIVFPQ, so you can see each knob move before tuning a production index.

# pip install faiss-cpu numpy   (run here with faiss-cpu 1.15.1)
import numpy as np
import faiss

rng = np.random.default_rng(42)
d, n, nq, k = 64, 100_000, 500, 10

# Seeded synthetic data: 50 broad blobs, so neighbors often straddle cell borders
centers = rng.normal(size=(50, d)).astype("float32")
def sample(count):
    return (centers[rng.integers(0, 50, count)] + rng.normal(size=(count, d))).astype("float32")
xb, xq = sample(n), sample(nq)

flat = faiss.IndexFlatL2(d)               # exact search = ground truth
flat.add(xb)
_, gt = flat.search(xq, k)

nlist, m, nbits = 1024, 16, 8             # 16 sub-vectors of 4 dims, 2^8 = 256 centroids each
index = faiss.IndexIVFPQ(faiss.IndexFlatL2(d), d, nlist, m, nbits)
index.train(xb[:50_000])
refine = faiss.IndexRefineFlat(index)     # also keeps raw vectors for the rerank step
refine.add(xb)                            # PQ codes go into the inverted lists
refine.k_factor = 10                      # rerank the top 100 PQ candidates exactly

print(f"bytes/vector: float32={d * 4}  PQ code={index.code_size}")

def recall(ids):
    return np.mean([len(set(ids[i]) & set(gt[i])) / k for i in range(nq)])

print("nprobe  scanned  recall@10(PQ only)  recall@10(+rerank)")
for nprobe in (1, 2, 4, 8, 16, 32, 64):
    index.nprobe = nprobe
    _, pq_ids = index.search(xq, k)
    _, rr_ids = refine.search(xq, k)
    print(f"{nprobe:6d}  {nprobe / nlist:7.1%}  {recall(pq_ids):18.3f}  {recall(rr_ids):18.3f}")

Output (identical on two runs):

bytes/vector: float32=256  PQ code=16
nprobe  scanned  recall@10(PQ only)  recall@10(+rerank)
     1     0.1%               0.169               0.173
     2     0.2%               0.286               0.307
     4     0.4%               0.411               0.506
     8     0.8%               0.522               0.760
    16     1.6%               0.586               0.971
    32     3.1%               0.591               0.996
    64     6.2%               0.591               0.996

The "scanned" column is the share of cells probed; the share of vectors scanned tracks it only roughly, because cells are not equal in size.

How to read the numbers

ObservationWhat it means
16 bytes per code vs 256 bytes of float3216x compression, set by m times nbits. faiss also keeps a 64-bit id per vector in each inverted list, so plan on roughly 24 bytes per vector in RAM.
PQ-only recall stops at 0.591 from nprobe 32 onwardProbing more cells no longer helps; quantization error is now the limit. Only a larger m, more bits or a rerank lifts it.
With rerank, recall goes from 0.173 to 0.971 between nprobe 1 and 16Here nprobe is the main lever: the true neighbors sit in cells the query never visited.
Rerank reaches 0.996 at nprobe 32Re-scoring the top 100 candidates on full vectors fixes most of the mis-ordering PQ introduced, but it needs the raw vectors stored somewhere (here in RAM inside IndexRefineFlat).

To tune your own index, swap in a sample of your real embeddings and keep the exact IndexFlatL2 ground truth. Raise nprobe until recall stops climbing, then decide whether the remaining gap is worth more bytes per code or a rerank stage. Train on a representative sample: faiss warns when there are fewer than about 39 training points per centroid, so nlist=1024 needs at least roughly 40,000 training vectors. These figures come from synthetic Gaussian blobs, so treat them as the shape of the trade-off, not a forecast for your data.