IVF-PQ

Two problems, two solutions, composed

A billion vectors is hard for two independent reasons, and it is worth keeping them apart.

Latency. Comparing a query against a billion vectors takes seconds. The fix is pruning — organise the vectors so most are never examined. That is IVF.

Memory. A billion 768-dimensional float32 vectors is 3 TB. The fix is compression — store something smaller than the vector. That is PQ.

IVF-PQ is both: cluster the corpus with k-means, then store PQ codes in each cell instead of vectors. Search opens the nearest nprobe cells and scores the codes inside them with a lookup table.

The savings are independent and they multiply. IVF means touching perhaps 0.1% of the corpus; PQ means each of those touches costs a few table lookups on a 48-byte code rather than a dot product over a 3 KB vector.

The residual is the part people skip

Here is the detail that makes the combination more than the sum of its parts, and it is the one most explanations omit.

PQ is applied to the residual — the offset from the cell centroid — not to the vector.

residual = x − centroid(x)
code     = PQ_encode(residual)

Toggle Quantise the residual off in the visualisation and watch the mean reconstruction error jump, with no change to the code length at all.

The reason is about the range each codebook has to cover. With the toggle off, one codebook must describe positions anywhere in the space, so its centroids are spread thin and every vector sits far from the nearest one. With it on, the values being quantised are small offsets from a cell centre. Residuals from every cell are similar in scale and centred on zero, so a single shared codebook fits them tightly — and its resolution is effectively local to each cell, because the cell centroid supplies the coarse position and the code only has to supply the correction.

Same bits, same memory, several times less error. It is also the reason IVF-PQ is a genuine composition rather than two tricks stacked: the partition does not merely prune, it hands the quantiser a much easier problem.

Reranking, and why nearly everyone does it

A PQ distance is an estimate. It is good enough to decide that a vector is nowhere near the query, and not good enough to order the top ten reliably — the reconstruction errors are the same size as the differences you are trying to resolve.

So production setups add a rerank stage: take the top few hundred by PQ distance, fetch their full vectors, and rescore exactly. Move the rerank slider and watch recall climb back toward 1.0.

The cost is a few hundred random reads. If the full vectors are on SSD that is a few milliseconds; if they were never stored, reranking is not available and you live with the PQ ordering. In FAISS this is IndexRefineFlat wrapped around the IVF-PQ index, and skipping it is one of the most common reasons a deployment's recall is worse than the tuning guide promised.

Notice the general pattern, because it recurs everywhere in retrieval: a cheap stage produces a candidate set, an expensive stage produces the ordering. The cheap stage only has to be good at exclusion. This is the same argument as a bi-encoder followed by a cross-encoder reranker, and the same argument ScaNN uses for its rescoring pass.

Sizing one at a billion vectors

Take a billion 768-dimensional vectors, m = 64 subquantizers at 8 bits, and nlist = 100,000.

Two things stand out. The codes fit in RAM on one large machine, which is the whole point. And the centroid scan — 100,000 comparisons per query — is becoming significant; past this scale you need an index over the centroids too, which is what composite recipes like IVF262144_HNSW32 are for.

The training cost deserves a mention: IVF centroids and PQ codebooks are both learned from a sample. If the corpus drifts away from that sample — a new document type, a new language, a re-embedded corpus — the index degrades quietly. Recall falls, nothing errors, and nobody notices until someone measures. Retraining is periodic maintenance, not a one-off.

Reading a FAISS factory string

FAISS names these indexes with a factory string, and once you can read one the whole design space opens up:

OPQ64_256,IVF16384,PQ64
│         │        └── product quantization, 64 subquantizers → 64 bytes/vector
│         └────────── inverted file with 16,384 cells
└──────────────────── learned rotation to 256 dims before quantising

Everything on these pages is in there: a rotation for PQ's benefit, a partition from IVF, and the code length that sets your memory bill. Append ,RFlat and you get the reranking stage.

import faiss

index = faiss.index_factory(768, "OPQ64_256,IVF16384,PQ64", faiss.METRIC_INNER_PRODUCT)
index.train(sample)          # learns rotation, centroids and codebooks
index.add(vectors)

index.nprobe = 32
# Rerank the shortlist against the exact vectors.
refined = faiss.IndexRefineFlat(index, faiss.swig_ptr(vectors))
refined.k_factor = 4         # shortlist 4k candidates, return k
scores, ids = refined.search(queries, 10)

k_factor is the shortlist multiplier — the rerank slider on this page in production form. Raising it costs reads and buys recall, and it is usually the first thing to turn up when an IVF-PQ index underperforms.

Which stage is costing you the recall

An IVF-PQ index has three places recall can leak and they have three different fixes. Guessing which is responsible is how tuning sessions get long, and there is a short ablation that simply tells you.

Take four measurements over the same query set:

Each consecutive gap attributes the loss to one stage:

• Flat to IVF-Flat is the partition missing true neighbours across cell boundaries. The fix is more probes, or a larger nlist with nprobe raised to match.
• IVF-Flat to IVF-PQ is quantisation error. The fix is a longer code, OPQ, or checking that residual encoding is actually on.
• IVF-PQ to IVF-PQ with rerank is *ordering* error rather than candidate error, and the fix is a larger k_factor.

This answers the question people ask first — raise nprobe, or lengthen the code? — with a number instead of a guess. If the first gap is 0.02 and the second is 0.15, no amount of extra probing will help you.

The reason it is worth the hour: the three fixes cost different things. More probes cost latency, a longer code costs memory, and a bigger shortlist costs random reads. Which you can afford is a property of your deployment, and without the ablation you will often spend the one you have least of.

In one line

IVF-PQ partitions with k-means and stores PQ codes of the residual from each cell centroid, which makes the same code length far more accurate. Search opens nprobe cells and scores codes by table lookup; a rerank stage rescores the shortlist with exact vectors and recovers most of the lost recall. It is the default at billion scale because it is the only structure here where memory, not latency, is the thing being solved.

Questions people ask

Why quantise the residual rather than the vector? Because it makes the codebook's resolution effectively local to each cell. Residuals from every cell are small, centred on zero and similar in scale, so one shared codebook fits them tightly, where quantising raw vectors asks the same centroids to cover the whole space. Same bits, same memory, several times less error.

Do I have to rerank? If you want the top-10 *ordering* to be right, effectively yes. A PQ distance is good enough to rule a vector out and not good enough to order the shortlist, because the reconstruction errors are the same size as the differences you are trying to resolve. Skipping it is among the most common reasons a deployment's recall falls short of what the tuning guide promised.

What does k_factor do? It is the shortlist multiplier: take k_factor × k candidates by PQ distance, rescore them against exact vectors, return k. Raising it costs random reads and buys recall, and it is usually the first thing to turn up when an IVF-PQ index underperforms.

Where does the memory actually go at a billion vectors? The PQ codes at m = 64 are 64 GB against 3 TB for float32, which is the entire point — they fit in RAM on one large machine. The IVF centroids at nlist = 100,000 are only 307 MB, but they are scanned in full on every query, which is why composite recipes put an index over the centroids at that scale.

Recall dropped months after deployment and nothing changed. Why? Because both the IVF centroids and the PQ codebooks are learned from a sample. When the corpus drifts away from it — a new document type, a new language, a re-embedded corpus — the index degrades quietly: recall falls, nothing errors, and nobody notices until someone measures. Retraining is periodic maintenance, not a one-off.

How do I read OPQ64_256,IVF16384,PQ64? As a pipeline. PQ64 is 64 subquantizers, so 64 bytes per vector; IVF16384 is 16,384 cells; OPQ64_256 is the learned rotation applied before quantising. Append ,RFlat and you have the reranking stage too.

Recap in one screen

• Two independent problems: latency, fixed by pruning (IVF), and memory, fixed by compression (PQ). IVF-PQ is both, and because the savings are independent they multiply.
• PQ encodes the residual from the cell centroid, not the vector. The partition hands the quantiser an easier problem, which is what makes this a composition rather than two tricks stacked.
• Search opens nprobe cells and scores codes by table lookup; a rerank stage then rescores the shortlist against exact vectors.
• The recurring pattern: a cheap stage produces the candidate *set*, an expensive stage produces the *ordering*. The cheap stage only has to be good at exclusion.
• At a billion vectors the codes fit in RAM and the centroid scan itself starts to be the bottleneck.
• Centroids and codebooks are trained on a sample, so corpus drift degrades recall silently.