IVF splits the space into cells and nprobe picks how many you visit

An IVF index — inverted file, the structure that Postgres's pgvector extension exposes under the name ivfflat — answers a query by cutting the stored vectors into groups and reading only a few of the groups. A legal-research team moved a corpus of 2.1M chunks, cut from case law and contracts, onto pgvector, the extension that stores embeddings in a column and indexes them, and created an ivfflat index with the documented defaults. Query latency went from 130 ms to 4 ms, which everyone noticed. Index recall went to 0.61, which nobody measured for another five months.

Index recall is the overlap between what an index returns for a query and what an exact scan over every stored vector would have returned for the same query — a property of the index alone, and a different quantity from the relevance score a retrieval evaluation reports. When the team finally ran the harness from chapter 2, which computes that overlap against brute-force ground truth, over 500 logged queries, the per-query distribution was strange: a little over half the queries scored 1.0, and most of the rest scored between 0.1 and 0.4. That shape is not noise, and it is not a property of approximation in general. It comes directly from how an IVF index is built, and once you can see the structure the failure stops being surprising.

Cells, and the two-step search they enable#

The name is borrowed from text retrieval, where an inverted file maps each term to the list of documents containing it, so a query for "indemnity" reads one short list instead of every document. What makes that work is that a term partitions the corpus into documents containing it and documents not containing it, and a query names its own partition. Vectors carry no terms, so the partition has to be manufactured out of the only property the search can exploit, which is proximity: something must cut the space into regions whose members are mutually close, and label each region with a point a query can be compared against cheaply.

k-means supplies both — the clustering algorithm that scatters k centres through the data, assigns every point to the centre nearest it, moves each centre to the average of the points it caught, and repeats until the assignment settles. At build time the index runs k-means over the corpus (or a sample of it) to produce nlist centroids, then assigns every vector to its nearest centroid. What comes out is nlist inverted lists — cell 0 holds the IDs and vectors closest to centroid 0, cell 1 holds those closest to centroid 1, and so on. Geometrically these cells are the Voronoi regions of the centroid set: every point in space belongs to exactly one cell, the one whose centroid it is nearest.

That last clause is a decision rather than a requirement, and it is worth marking as one because everything this chapter is about follows from it. Nothing in the two-step search below needs a vector to sit in exactly one cell. Storing each vector in the two cells nearest it would work identically at query time and would cost twice the storage. Exclusive assignment is what makes a cell you did not open an irrecoverable miss rather than a slower path to the same answer.

A query is then answered in two passes. First the query vector is compared against the nlist centroids, which is a small exact scan, and the nprobe nearest centroids are selected. Second, the vectors inside those nprobe cells are scanned exhaustively and the top-k taken. Everything in the other nlist - nprobe cells is never touched, never scored, and cannot appear in the results no matter how close it is to the query.

The arithmetic explains the 4 ms. With 2.1M vectors and nlist = 4096, the average cell holds 513 vectors. At nprobe = 3 a query computes 4,096 centroid comparisons plus about 1,540 vector comparisons, so roughly 5,600 dot products instead of 2.1 million — a factor of 375 less work.

Every line of that closes on the one before it, which is what makes it a model rather than three measurements. The corpus divided by the cell count gives the average cell. Three average cells give the vector term. The centroid term and the vector term added give the total. The corpus divided by that total gives the saving. So the general form is two terms: one comparison per centroid, which is nlist of them and does not depend on nprobe at all, plus one comparison per vector in each cell opened, which is nprobe times the corpus divided by nlist. A fixed cost and a proportional one. Everything IVF does to latency lives in that sum, and it predicts rows of the sweep below without running them.

The three cells in the diagram hold 512, 488 and 471 rather than 513 each, which is worth noticing rather than rounding away. k-means equalises cell sizes only on average, and a query has no control over which cells it lands in, so the work a query does varies with the luck of its draw. That is why the sweep below quotes p95 latency, meaning the figure that 95% of queries come in under, rather than a mean: the slowest twentieth of queries is where a probe lands in an unusually large cell.

The centroid scan is not free and it becomes the floor on latency: at nlist = 65536 you would be doing 65,536 dot products before touching a single document, which is why very large nlist values eventually need a second-level index over the centroids themselves.

Why the loss is structural#

The vectors that get skipped are not a random sample. A query lands somewhere in the space, and the cells it probes are the ones whose centroids are nearest. If the query sits comfortably inside one cell, far from every boundary, then its true nearest neighbours are almost certainly in that same cell and nprobe = 1 returns the exact answer. If the query sits near a boundary between two cells — or, in 768 dimensions, near the meeting point of a great many cells at once — then its true neighbours are split across several of them, and the ones on the far side of a boundary you did not probe are invisible.

Two steps in that make it inevitable rather than unlucky. A query's true neighbours are whatever lies within some small radius of it, and that radius is a fact about the embeddings alone — it knows nothing about where k-means put the boundaries, so any query closer to a boundary than its own neighbour radius has neighbours on the far side by definition. Exclusive assignment then puts those far-side neighbours in a different list, reachable only by opening it. The boundary was drawn before the query existed and the query cannot move it.

This is a different failure mode from the one people expect. Approximate search is usually imagined as a fuzzy scan that gets things slightly wrong everywhere, and that intuition predicts that a recall of 0.61 means each query loses about four of its ten neighbours. What IVF actually produces is closer to a partition of the queries: interior queries are exact, boundary queries are badly wrong, and the average is a mixture of the two.

The measured distribution lets you check that claim rather than accept it, and the check is arithmetic. If a fraction of queries score 1.0 and the rest average something, the mean is the first fraction plus the second fraction times its own average — the headline is a mixing weight and nothing else. Put "a little over half" into the first slot and ask what the remainder has to average for the sum to come out at 0.61, and the answer sits near the bottom of the 0.1-to-0.4 band, not in the middle of it. So the failing half is not losing four neighbours out of ten. It is losing eight or nine. The two-population reading reconstructs the headline exactly; the headline reconstructs neither population, which is the whole reason chapter 2 insisted the harness return per-query values.

The legal corpus made this vivid because "indemnity cap" and "limitation of liability" are semantically adjacent, which put the two clusters of chunks next to each other in embedding space with a boundary running between them, and queries about the interaction of the two landed squarely on that boundary.

There is a tempting belief to name here, because it is the one that keeps an index at 0.61 for five months after somebody has started tuning it: that nprobe is the recall knob. It is a knob and it does move recall, so the belief survives contact with a sweep. What it gets wrong is that nprobe is a constant, applied identically to a population that is not uniform. The property that decides whether a query needed more probes is how close that query sits to a boundary, and that property varies enormously from query to query while nprobe does not vary at all. A defence that holds still while the thing it must discriminate moves cannot discriminate. Raising nprobe therefore buys recall for the boundary queries by making every interior query — the half that was already exact — pay for probes it had no use for.

The information needed to tell the two apart is already in hand, which is what makes the constant crude rather than merely coarse. The first pass computes the query's distance to every centroid, and the gap between the nearest and the second-nearest of those distances is small exactly when the query sits near a seam and large when it sits deep inside a cell. That quantity is a by-product of work the search does anyway, on every query, before it opens a single list, and a fixed nprobe discards it.

Being crude does not stop it working. Raising nprobe fixes the problem in the obvious way, for every query at once, by widening the set of cells visited until the boundary no longer excludes anything.

The third column is the cost model rather than a set of independent measurements, and checking that changes what the table is for. Add 4,096 centroid comparisons to nprobe average cells of 513 each: one cell gives the first row's ~4.6k, four cells a little over two thousand vectors for ~6.1k, sixteen cells a little over eight thousand for ~12.3k, sixty-four cells roughly thirty-three thousand for ~37k, and two hundred and fifty-six cells about a hundred and thirty-one thousand for ~135k. Every row falls out of two figures fixed at build time, which licenses prediction: the cost of an nprobe you have not tried is readable off the same two numbers, and a measured latency that disagrees with the model is reporting something about the index rather than about nprobe.

The two remaining columns are worth reading as gaps rather than as levels. Recall gains 22 points from nprobe = 1 to 4, then eleven, then between four and five, then a little over one, then a fifth of one — each step multiplies nprobe by four and buys roughly half what the step before it did. Latency moves in the opposite direction and at a different moment: half a millisecond, then under two, then nearly seven, then twenty-eight, then six hundred and forty-nine.

Those two readings cross at one point, and it is the most useful thing in the table. The centroid scan is worth about eight average cells, since 4,096 divided by 513 is very nearly eight, so nprobe has to reach roughly eight before the cells cost what the centroids do. Below that the fixed term dominates and extra probes are close to free; above it latency tracks nprobe almost exactly, which is why a fourfold rise from 64 to 256 roughly triples the figure and a sixteenfold rise from 256 to 4096 multiplies it by about sixteen. The rows where recall climbs fastest are exactly the rows where latency barely moves, and one cause produces both. That is why going from nprobe = 1 to nprobe = 4 costs almost nothing in latency and buys 22 points of recall — the cheapest tuning move available anywhere in this topic, and cheap because of how nlist was chosen rather than because IVF is generous.

The last row is exact search with extra steps: probing every cell scans every vector and pays for the centroid comparisons on top, which is slightly slower than the plain scan from chapter 1. That comparison needs its conditions stated, because the two figures are not measured the same way. Chapter 1's is a much smaller corpus scanned by eight threads as one contiguous BLAS pass; this row is a single query against a corpus an order of magnitude larger, read as 4,096 separate list traversals with an indirection into an ID array at each one. Same bytes, worse access pattern, plus the centroids. Held at the same corpus size and the same thread count, "slightly slower" is the right reading of the overhead; taken as a comparison of the two printed numbers, it is not.

What is frozen and what is free#

nlist is decided before the index exists, because the k-means run that produces the centroids is the build. Changing it means retraining and reassigning every vector, and the cost is real: k-means over a 2.1M × 768 float32 corpus, or over a representative sample of it, takes a few minutes on a CPU and produces a full rewrite of the inverted lists. nprobe is read at query time and can be set per request, which means it can be changed in a config, raised for a slow-but-important query class, or lowered under load, with no rebuild and no downtime.

import faiss, numpy as np

d, nlist = 768, 4096
quantizer = faiss.IndexFlatIP(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_INNER_PRODUCT)

# nlist is fixed here, at training time, and cannot change afterwards.
sample = corpus[np.random.default_rng(0).choice(len(corpus), 400_000, replace=False)]
index.train(sample)          # k-means: ~3 min for 4096 centroids on 400k vectors
index.add(corpus)            # assigns every vector to its nearest centroid

# nprobe is read on every search and is free to change.
for nprobe in (1, 4, 16, 64, 256):
    index.nprobe = nprobe
    _, ids = index.search(queries, 10)
    print(nprobe, index_recall(ids, gt_ids).mean())

The training set size matters and is easy to get wrong. FAISS wants at least 39 × nlist training points and prefers 256 × nlist; at nlist = 4096 that is 160k to 1M vectors, and training on 10,000 vectors because it was faster produces centroids that describe a sample rather than the corpus. Those centroids then partition the space badly — some cells hold 40 vectors, others hold 20,000 — and the recall table above shifts down by ten to twenty points at every nprobe. A quick check on any inherited IVF index is the distribution of list lengths; if the longest list is more than about five times the mean, the training was inadequate or the corpus has changed shape since.

lengths = np.array([index.invlists.list_size(i) for i in range(index.nlist)])
print(f"mean={lengths.mean():.0f} p50={np.percentile(lengths, 50):.0f} "
      f"p99={np.percentile(lengths, 99):.0f} max={lengths.max()} empty={(lengths == 0).sum()}")
# healthy:   mean=513 p50=498 p99=1120 max=1613 empty=0
# undertrained: mean=513 p50=214 p99=8840 max=24107 empty=193

The mean is identical on both lines, and it has to be: it is the corpus divided by nlist, and neither of those changes when the training set does. Every symptom of undertraining is therefore in the spread and none of it is in the average, which is why an index summary that reports the mean list length reports nothing at all.

The second line is what an index trained on 10,000 vectors looks like at nlist = 4096. Half the cells hold fewer than 214 vectors, 193 of them hold nothing at all, and the largest holds 24,107 — so a query that probes the big cell pays five times the expected latency while a query that probes three empty ones gets almost no candidates back. Both the recall and the latency distributions get worse, and neither symptom points obviously at the training step. Running this check takes a second and it should be the first thing you do to an IVF index you did not build.

The choice of nlist itself is a balance rather than a maximum. Common practice sets it between √N and 4√N, which for 2.1M vectors is 1,450 to 5,800. More cells means smaller cells, so less work per probe and lower latency at fixed nprobe, but also more boundaries and therefore lower recall at fixed nprobe, plus a larger centroid scan. Fewer cells means the opposite. The two effects roughly cancel in terms of the recall-per-millisecond frontier, which is why the rule of thumb survives despite being crude: nlist moves you along the curve rather than off it, and nprobe is the knob you actually tune.

The lower end of that band is not folklore, and the cost model derives it. Total work at nprobe = 1 is nlist plus the corpus divided by nlist. The first term grows as cells are added and the second shrinks, so the sum is smallest where the two are equal, and they are equal when nlist multiplied by itself equals the corpus. That is the square root, and √N is therefore the setting at which scanning the centroids costs exactly as much as scanning one cell — the cheapest single-probe index there is.

Pushing above √N is a design decision, and the same model says what it buys. Set nlist to a multiple of √N and the centroid scan grows by that multiple while the cells shrink by it, so the fixed term becomes worth the square of that multiple in cells. At the band's upper end it is worth sixteen cells, meaning the first sixteen probes are nearly free, which is the whole reason the top of the sweep table was so cheap. This index sits nearer the top of the band than the bottom, and that is where its eight-cells-worth of centroids came from. Nobody serves at nprobe = 1, so paying a larger fixed cost to make the first several probes free is the right trade — and the width of the band is convention rather than consequence.

One structural detail explains why very large nlist values are usable at all. The first step of the search — comparing the query against every centroid — is itself a nearest-neighbour problem over nlist vectors, and it is solved in the code above by IndexFlatIP, an exact scan. That is fine at 4,096 centroids and becomes the dominant cost somewhere past 30,000, at which point the standard move is to make the coarse quantizer, which is the name that first step goes by, an approximate index in its own right: FAISS's IVF262144_HNSW32 factory string means 262,144 cells whose centroids are searched with a small HNSW graph. The composition is worth knowing about because it explains why the two index families are not really rivals at the largest scales, and because it puts a name to the latency floor you hit when you keep raising nlist with a flat quantizer.

The same structure appears with different vocabulary in the systems most teams actually use. In pgvector, CREATE INDEX ... USING ivfflat (embedding vector_ip_ops) WITH (lists = 4096) is nlist, and SET ivfflat.probes = 16 is nprobe, set per session and therefore per query. The build-time and query-time split from the previous paragraphs is visible directly in the SQL: one is an argument to CREATE INDEX and requires a REINDEX to change, the other is a session variable.

Storage cost, and a corpus that changes shape#

The cell structure is a way of skipping work; it is not a way of using less memory. IndexIVFFlat stores every vector in full, so the 2.1M × 768 float32 corpus still occupies 6.4 GB in RAM plus a few megabytes of centroids and list overhead. The memory savings people associate with IVF come from pairing it with product quantisation — IVFPQ, where each vector is replaced by a short code of typically 16 to 64 bytes — and that is an orthogonal decision with its own recall cost, applied on top of the partitioning rather than caused by it. Treating "IVF" as shorthand for "compressed index" leads to sizing plans that are off by a factor of forty in one direction or the other.

IVF also assumes the corpus keeps the shape its centroids were trained on. New documents are assigned to whichever existing centroid is nearest, even if they belong to a region the training data never covered, so a corpus that grows into new subject matter accumulates vectors piled into a few cells that no longer describe them. Nothing errors. The lists get longer, latency creeps up, and recall for queries about the new material drops, because those queries probe cells whose centroids are a poor summary of what is now inside them. Chapters 5 and 7 come back to this, since it is the main reason IVF wants a retraining cadence and HNSW does not.

The recall column of the sweep is also more corpus-specific than the latency column, and quoting the two with equal confidence is a mistake. The cost model behind the vector counts holds for any corpus, because it is built out of nlist, nprobe and a division. The recall figures are not: they depend on how tightly the embeddings cluster and therefore on what fraction of queries land near a seam, and a corpus whose documents fall into well-separated topics will show a much flatter climb than one where every region borders several others. What transfers between corpora is the shape — cheap early probes, a sharp knee, a long flat tail — rather than the values, and the only way to get your own values is to run the sweep on your own queries.

Once the cells are in view, the failure this chapter opened on stops being an anomaly and becomes a prediction. A corpus is cut into regions before any query arrives, each query is answered out of a fixed number of those regions, and the queries that suffer are the ones whose neighbours the cut separated. nprobe widens the answer and nlist decides how finely the cut was made, and only one of those two is available to you on the afternoon somebody notices.

The other index family takes a different route entirely. Rather than partitioning the space and scanning inside a partition, it builds a graph over the vectors and walks it, which removes the boundary problem and replaces it with a different one: the search can only go where the edges lead, and the edges were decided when the graph was built.