Coarse Quantization with Inverted Files and the nprobe Setting

The inverted file is the least exotic approximate index and the one that most directly converts a clustering result into a speedup. It is older than the embedding era, its parameters have interpretations in terms of the collection rather than the algorithm, and its failure modes are easy to predict: it fails on the boundaries between clusters, and it fails when the query lands in a cell whose true neighbors are in the adjacent one. Understanding the mechanism means understanding exactly how much is being skipped and what is being given up.

Partition once, scan a few cells

Building the index has two stages.

The first trains a quantizer. A sample of the collection, typically a fraction of records drawn uniformly, is clustered by k-means into $K$ centroids. $K$ is usually a power of two and is chosen so that each cell holds a workable number of records; the square root of the collection size is a common starting heuristic, so a million records produce roughly a thousand centroids. The centroids are $d$-dimensional vectors of the same width as the data, and they are stored in a flat array of $K \cdot d$ floats: a thousand centroids at 768 dimensions is about three megabytes, small enough to remain in cache throughout a query.

The second stage assigns each record to its nearest centroid, computed exactly, and appends the record’s identifier to that centroid’s posting list. The vectors themselves can be stored in the posting lists in their original form, which is the flat variant, or replaced by a compressed code, which is the product-quantized variant. The assignment step is one full distance computation per record against all $K$ centroids, the dominant cost of construction.

A query then computes its distance to all $K$ centroids, sorts the centroids by that distance, and scans the posting lists of the $n_{\text{probe}}$ closest cells. Every scanned record is compared exactly and inserted into a bounded result heap of size $k$.

The work per query is $K$ centroid comparisons plus $n_{\text{probe}} \cdot n/K$ record comparisons, since the cells are approximately equal in size by construction. With $K = 1000$, $n = 10^6$, and $n_{\text{probe}} = 8$, that is a thousand centroid comparisons plus about eight thousand record comparisons: roughly a hundredth of a full scan’s million comparisons. The centroid stage is not free at that scale; it is comparable to the record stage, which is why a larger $K$ does not monotonically improve latency.

What k-means is optimizing, and why it is the wrong objective

k-means minimizes the sum of squared distances from each record to its assigned centroid. That objective is about representing the data accurately, not about making retrieval cheap. The two are related but not identical, and the gap shows up in a specific way.

Consider a record that sits almost exactly between two centroids. Its nearest centroid assignment is essentially arbitrary. A query whose true nearest neighbor is that record will probe the cell the record was assigned to only if that cell happens to be among the $n_{\text{probe}}$ nearest to the query. Since the query’s own nearest centroids are ranked by centroid distance, and the record’s distance to its centroid is large (it is on the boundary), the record is likely to be missed unless $n_{\text{probe}}$ is large.

This is the fundamental asymmetry of the design: a record’s cost of being missed is proportional to its distance from its own centroid, and k-means deliberately assigns boundary records to cells they are far from. The number of records whose distance to their assigned centroid exceeds the cell radius is a large fraction of the collection in a high-dimensional space, because of the concentration effect described in Distance Concentration and Why Tree Indexes Collapse in High Dimensions.

The usual remedy is to probe by a distance rather than by a count: scan every cell whose centroid lies within some radius of the query. This adapts the work to the query’s position, since a query in a dense region probes more cells, and it makes the recall-loss mechanism explicit, because the radius is exactly the distance beyond which a cell cannot contain a neighbor that beats the current best. The count-based parameter is more common because it gives a predictable cost bound.

A second remedy is to assign each record to several cells, which duplicates posting entries and multiplies storage. A record in two or three cells is unlikely to be missed, but the index grows accordingly and the scan begins to duplicate work when two of a record’s cells are both probed.

The nprobe curve

Recall as a function of $n_{\text{probe}}$ has a characteristic shape: it rises quickly while the true neighbors’ cells are being added, then flattens as the remaining cells contribute mostly noise. The knee of that curve is the useful operating point. On the left of the knee, each additional probe adds recall; on the right, it adds latency and few correct results. For a collection with well-separated clusters, the knee can sit at a small multiple of the number of true neighbors, since the neighbors of a query tend to share a cell.

The curve’s position depends on the collection, and the dependence is strong enough that $n_{\text{probe}}$ values are not transferable. A collection with $K$ cells each holding $n/K$ records and a uniform distribution has most of a query’s true nearest neighbors in the same cell only when the centroid count is small relative to the local density. Increasing $K$ improves the pruning, since more cells mean each scanned cell is closer to the query, but shrinks each posting list, so recall at fixed $n_{\text{probe}}$ may fall because the query’s neighbors spread across more cells. The two effects trade against each other, and the product $K \cdot n_{\text{probe}}$ is not a sufficient statistic.

A rough scaling rule that is commonly quoted: to hold recall constant while $n$ grows, $K$ should grow roughly with the square root of $n$, and $n_{\text{probe}}$ with the square root of $K$. This keeps the fraction of the collection scanned roughly constant, but real collections are not uniform, and the rule gives a starting point rather than an answer.

import numpy as np

def build_ivf(vectors: np.ndarray, k: int, iters: int = 12, seed: int = 0):
    """One pass of Lloyd's algorithm over a sample, then a full assignment."""
    rng = np.random.default_rng(seed)
    # k-means++ seeding: first pick uniformly, then weight by squared distance.
    centroids = vectors[rng.integers(len(vectors), size=1)]
    for _ in range(1, k):
        d2 = ((vectors - centroids[:, None]) ** 2).sum(-1).T   # n x c, squared distances
        probs = d2.min(axis=1)          # k-means++ weights by squared distance to the nearest seed
        centroids = np.vstack([centroids, vectors[rng.choice(len(vectors), p=probs / probs.sum())]])

    for _ in range(iters):
        assign = np.argmin(((vectors - centroids[:, None]) ** 2).sum(-1).T, axis=1)
        for c in range(k):
            members = vectors[assign == c]
            if len(members):
                centroids[c] = members.mean(axis=0)
    assign = np.argmin(((vectors - centroids[:, None]) ** 2).sum(-1).T, axis=1)
    lists = [np.flatnonzero(assign == c) for c in range(k)]
    return centroids, lists

def search_ivf(query, centroids, lists, vectors, nprobe=8, k=10):
    order = np.argsort(((centroids - query) ** 2).sum(1))[:nprobe]
    cand = np.concatenate([lists[c] for c in order if len(lists[c])])
    if len(cand) == 0:
        return np.empty(0, dtype=int)
    d = ((vectors[cand] - query) ** 2).sum(1)
    sel = np.argpartition(d, min(k, len(d)) - 1)[:k]
    return cand[sel][np.argsort(d[sel])]

The training loop above is deliberately plain; production implementations use blocked distance computation, subsampling, and early stopping. What matters for the mechanism is that the assignment is a hard nearest-centroid partition and that the posting lists are fixed after construction.

Failure modes that are specific to this structure

Imbalanced cells are the most common operational problem. Real embeddings cluster: a corpus with one dominant topic produces a cell containing a large share of the collection, and any query that probes it scans that share. Detecting the imbalance is trivial at build time, since the posting list lengths are available, and the usual responses are to increase $K$ until the largest list is bounded, or to split the largest cell recursively. Splitting is preferable because it preserves the total cell count’s relationship to the data rather than inflating it uniformly.

Deleted records leave gaps. Removing a record from a posting list requires either shifting the list or leaving a tombstone, and tombstones accumulate until a rebuild. The cost of that maintenance is examined in Tombstones, Merges, and the Cost of Keeping a Vector Index Current.

A query outside the data’s distribution behaves worse than its in-distribution counterpart, not better. Its nearest centroids are determined by distance, but the cells contain records that are all far away, and the top-$k$ returned can be arbitrary. Many systems attach a distance threshold and return nothing when the best score does not clear it, which is safer than returning a confident-looking list of unrelated records.

Finally, the flat variant’s scan cost is dominated by memory, not arithmetic. Each scanned record requires reading $4d$ bytes and performing $d$ multiply-accumulates. At 768 dimensions the ratio is fixed: 3072 bytes to 1536 floating-point operations. Any CPU-wide vector instruction set executes the arithmetic many times faster than memory delivers the bytes, so the scan is bandwidth-bound and compression of the stored vectors is the lever that changes the slope. That is the subject of Product Quantization and the Asymmetric Distance Computation, where the same inverted-file structure holds codes instead of vectors and the scan becomes a lookup in a precomputed table.

The design’s real virtue is that its cost model is closed-form. The number of comparisons is known before the query arrives, the recall loss is explained by cell boundaries, and every parameter has a meaning in terms of the data. For collections up to the tens of millions, that predictability is often worth more than the better recall-per-cycle of a graph index.