Coarse Quantisers and the Probe Budget

An inverted-file index is the bluntest workable idea in vector search: cluster the corpus, remember which cluster each vector landed in, and at query time only look inside the clusters nearest the query. It builds in a single k-means pass, retrains cheaply, stores almost no structural overhead, and its recall behaviour is governed by one runtime number. It is also the family whose failure mode is most often misdiagnosed.

The arithmetic that picks nlist

Train nlist centroids over the corpus, assign each of \(N\) vectors to its nearest, then at query time score the query against every centroid and exhaustively scan the nprobe nearest lists. Comparisons per query are

which is minimised near \(\sqrt{N}\) and grows in both directions from there: too few cells and each scan is huge, too many and the centroid scan itself dominates. FAISS recommends nlist between \(4\sqrt{N}\) and \(16\sqrt{N}\), with concrete recipes of IVF65536_HNSW32 for 1M–10M vectors and IVF1048576_HNSW32 for 100M–1B (FAISS wiki, Guidelines to choose an index). pgvector gives the same shape in simpler terms: lists = rows/1000 up to a million rows, \(\sqrt{\text{rows}}\) above that, with probes starting at \(\sqrt{\text{lists}}\) (pgvector README).

The _HNSW32 suffix is worth dwelling on. At a million centroids, finding the nearest cells is itself an approximate nearest-neighbour problem, so the coarse quantiser gets its own graph index. Routers nest, which is a useful corrective to the idea that "graph versus cell" is a single architectural fork.

Boundary loss, not code error

The intuition that a query lands "inside" a cell together with its neighbours is a two-dimensional intuition. In several hundred dimensions nearly every point sits near a Voronoi boundary, and a query's true nearest neighbours are routinely distributed across several cells. So nprobe = 1 is not "the right cell"; it is one of several cells the answer might be in, and recall at nprobe = 1 is a statement about geometry rather than about tuning.

This is the mechanism behind the characteristic IVF recall curve, and it is independent of compression. IVFADC, from the original product-quantisation paper, reduces code error by quantising each vector's residual from its centroid rather than the raw vector, which keeps reconstruction tight (Jégou, Douze & Schmid, 2011). It does nothing for boundary loss. No amount of code fidelity recovers a cell you never opened.

Training is a first-class build step

A coarse quantiser trained on too little data produces imbalanced cells, and imbalance quietly invalidates the probe arithmetic above. FAISS's guidance calls for 1.97M to 16.8M training vectors for IVF65536_HNSW32, with a note that training at larger nlist becomes slow enough to warrant GPU or two-level clustering. SPANN takes the opposite approach and makes balance an explicit objective, using hierarchical balanced clustering so posting lists come out comparable in length, plus a query-aware scheme that prunes lists it does not need to read; it reports 90% recall in about a millisecond at roughly 10% of the in-memory footprint, serving posting lists from SSD (Chen et al., NeurIPS 2021).

When it breaks

Imbalanced cells show up as a latency tail correlated with query region rather than query load: one probe scans 40,000 vectors where the average is 3,000. If a p99 is bad but throughput is fine, check cell occupancy before touching nprobe.

Distribution shift is the second failure. Centroids fitted to last quarter's corpus no longer partition this quarter's, so new content concentrates in a few cells and its recall degrades independently of everything else. Unlike a graph index, an IVF index at least retrains cheaply, which is a real operational advantage.

The third is a measurement trap: because nprobe is a live dial, it is tempting to treat every recall shortfall as under-probing. If four doublings of nprobe move recall by a few points, the remaining gap belongs to the quantiser, not the router.