IVF-Flat

Cluster once, probe a few

An inverted file index has two phases and both are simple.

Build. Run k-means with nlist centroids over a sample of the corpus, then assign every vector to its nearest centroid. The result is a map from centroid ID to a list of vector IDs — an inverted file. The name is borrowed from text search, where the same structure maps a term to the documents containing it.

Search. Compare the query with all nlist centroids, sort them, take the nearest nprobe, and exhaustively scan the vectors in those lists.

The squares in the visualisation are the centroids, filled where the cell was opened. Everything inside an opened cell is compared; everything else is invisible to this query. The tradeoff is controlled entirely by nprobe: higher values give better recall at the cost of more comparisons, approaching brute force as nprobe reaches nlist.

Choosing nlist

Total work per query is:

nlist            centroid comparisons
+ nprobe × n/nlist   vector comparisons

Those two terms pull in opposite directions. A small nlist means few centroids to scan and large cells to search; a large nlist means the reverse. Differentiating with respect to nlist gives a minimum near nlist ≈ √n, which is where the usual rule of thumb comes from:

FAISS's own guidance is 4·√n to 16·√n for large corpora, on the reasoning that the centroid scan vectorises well and the list scan does not. Above roughly 100,000 centroids the centroid comparison becomes the bottleneck on its own, at which point you need a second level — an index over the centroids — which is what IVF_HNSW and similar composite indexes do.

Training matters too: k-means needs enough points per centroid to be meaningful, and FAISS warns below about 39 points per centroid. Asking for 100,000 cells over a million vectors gives ten points each and produces centroids that describe noise.

The failure mode, in red

Drag the query onto a boundary between two clusters and red points appear. Those are genuine top-k neighbours living in a cell the search never opened. The index did not rank them badly — it never computed their distance.

This is IVF's entire weakness and it is a clean one. A hard partition drawn through a continuous space will sometimes cut through a neighbourhood, and any query near that cut loses whatever is on the far side. The damage is query-dependent: the same index with the same nprobe is excellent for a query in the middle of a cell and poor for one on a boundary. An average recall over a realistic query set is the only number worth quoting.

The fix is always more probes, and the cost is always another n/nlist vectors scanned. There is no cleverness available here, which is in its way a virtue — the parameter does exactly one thing and you can reason about it.

Reading the two dials against each other

nprobe is the runtime knob, the direct analogue of HNSW's efSearch. More probes, more recall, more latency, adjustable per query.

nlist is fixed at build time and moves both numbers at once. Raise it with nprobe held constant: cells are smaller, fewer vectors are scanned, the search gets faster — and recall drops, because the same nprobe now covers less of the space. Raise both together and you are back where you started with a finer partition.

The instructive extreme is nprobe = nlist: every cell opened, recall exactly 1.0, and a flat scan with the centroid comparisons added as overhead. An index asked for perfect recall is not an index. That is worth internalising as the general shape of the trade — every approximate index degenerates to exhaustive search at its recall limit.

Why IVF is still here

HNSW beats IVF-Flat on recall per millisecond. Every vector database still ships IVF, for three reasons that have nothing to do with query speed.

Build cost. k-means over a sample, then one assignment pass. Minutes where a graph takes hours, and it parallelises trivially — each vector's assignment is independent.

Updates. Inserting means finding the nearest centroid and appending to a list. Deleting means removing an ID from one list. No rewiring, no tombstoning, no rebuild. The index degrades slowly as the data drifts away from the centroids it was trained on, and the remedy is a periodic retrain rather than a reconstruction.

It composes. The cell structure is what IVF-PQ quantises residuals against, and it makes sharding natural — a cell is an obvious unit to put on a machine, and a query only needs the shards holding its nprobe cells. Most billion-scale systems are IVF-shaped underneath, even when a graph does the work inside each shard.

import faiss

d, nlist = 768, 1024
quantizer = faiss.IndexFlatIP(d)                 # the centroid index
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_INNER_PRODUCT)

index.train(sample)      # k-means; needs enough points per centroid
index.add(vectors)

index.nprobe = 16        # the runtime knob, set per query if you like
scores, ids = index.search(queries, 10)

train is a separate call for a reason: it learns the partition and it needs a representative sample, not the whole corpus. Training on a biased sample — the first million documents, all from one source — produces centroids that fit that source and cells that are badly unbalanced for everything else, which shows up as recall that varies by document type for no visible reason.

Cells are not the same size

The nlist ≈ √n arithmetic assumes every cell holds n/nlist vectors. On real embeddings, none of them do.

k-means puts centroids where the data is, and embeddings are clustered rather than evenly spread — so a corpus of support tickets with one enormous "password reset" region and a long tail of rare topics produces cells whose populations differ by one or two orders of magnitude. FAISS reports this as an imbalance factor, where 1.0 would be perfectly even; real corpora commonly sit well above it.

Two consequences follow, and the second is the one that causes incidents.

The latency you tuned is an average. A query whose nprobe cells happen to be the large ones scans several times more vectors than one landing in the tail, at identical nprobe. So p99 latency is much worse than the mean, and it is worst for exactly the common queries that land in the dense regions.

Sharding by cell inherits the imbalance. A cell is the obvious unit to put on a machine, and if one cell holds a twentieth of the corpus then one machine holds a twentieth of the corpus and serves the queries most likely to probe it.

The mitigations are all partial. Training on a genuinely representative sample stops the imbalance being worse than the data warrants. Raising nlist makes cells smaller in absolute terms without making them relatively more even. Spherical k-means helps when the embeddings are normalised. And some systems split oversized cells after training, which breaks the clean n/nlist arithmetic but bounds the worst case. Whichever you pick, report p99 rather than the mean.

In one line

IVF-Flat clusters the corpus with k-means and scans only the nearest nprobe cells. nlist ≈ √n at build time; nprobe is the runtime recall/latency knob. It misses true neighbours across cell boundaries, visibly and fixably. It loses to HNSW on latency and wins on build time, update cost and composability — and it is the skeleton that IVF-PQ hangs compression on.

Questions people ask

What should nprobe be? Start around 1–2% of nlist and tune against measured recall on your own queries. It is a runtime knob, so it can differ per query — a "related documents" sidebar and a compliance search do not need the same recall, and they do not have to share a value.

Why does recall vary so much between queries? Because the damage is query-dependent by construction. A query in the middle of a cell is served well; one sitting on a boundary loses whatever is on the far side. Only average recall over a realistic query set means anything, and a single-query demo of an IVF index is close to meaningless.

How much training data does k-means need? FAISS warns below roughly 39 points per centroid. Asking for 100,000 cells over a million vectors gives ten points each and produces centroids that describe noise. The sample also has to be representative: train on the first million documents from one source and you get cells that are badly unbalanced for everything else, which surfaces as recall that varies by document type for no visible reason.

Can I change nlist after building? No — nlist *is* the partition, so changing it is a retrain and a full re-add. That asymmetry is worth planning around: nprobe is free to change at any time, nlist is a rebuild.

IVF or HNSW? HNSW wins on recall per millisecond and nothing else on this list. IVF wins on build time (minutes against hours), update cost (append to a list against rewiring a graph) and composability. If your corpus churns, or you need to shard, that usually settles it before latency is discussed.

Why is nprobe = nlist pointless? Because it is a flat scan with the centroid comparisons added as pure overhead, at recall exactly 1.0. It is worth knowing as the general shape of the trade: every approximate index degenerates into exhaustive search at its recall limit.

Recap in one screen

• Build is k-means with nlist centroids plus one assignment pass; search compares the query against all centroids and exhaustively scans the nearest nprobe cells.
• Work per query is nlist + nprobe · n/nlist, minimised near nlist ≈ √n; FAISS suggests 4√n to 16√n at large scale, because the centroid scan vectorises and the list scan does not.
• The failure mode is a hard partition through a continuous space: true neighbours in an unopened cell are never scored at all, rather than scored badly.
• nprobe is the runtime recall/latency knob. nlist is fixed at build and moves both numbers at once.
• Real cells are badly uneven, so per-query latency varies far more than the arithmetic suggests — quote p99.
• It outlived its latency disadvantage because of build cost, update cost and composability: most billion-scale systems are IVF-shaped underneath.