What is IVF (Inverted File Index)?

How IVF works

IVF works by first running a clustering algorithm (typically K-means) on the vectors to get a set of centroids. Each vector is assigned to its nearest centroid, forming Voronoi cells. The “inverted file” stores, for each cluster, the list of vector IDs (and optionally the vectors themselves) belonging to that cluster. To answer a query, you find the nearest centroids to the query vector (controlled by nprobe), then search only the vectors in those clusters—often combined with product quantization (PQ) or scalar quantization for further speed and memory savings.

The role of Voronoi cells in IVF is that each cell contains all points closer to one centroid than to any other; the inverted file is simply an index from centroid (cell) to the list of vectors in that cell. Search space reduction comes from only scanning the nprobe cells closest to the query instead of the full dataset.

Recall vs. speed

IVF trades some recall for speed: if the true nearest neighbor lives in a cluster you didn’t probe, you’ll miss it. Tuning the number of clusters (nlist) and how many to probe at query time (nprobe) controls this trade-off.

Practical tip: start with nlist on the order of sqrt(n) to 4×sqrt(n) and nprobe a small fraction of nlist (e.g. 1–10% of nlist); measure recall@k and latency. Increase nprobe for higher recall at the cost of query time; increase nlist for finer partitioning but more centroid comparisons at query time. Flat indexing (brute force) can be better when the dataset is small enough that scanning all vectors is fast.

Pipeline and combinations

Build pipeline: run K-means to get nlist centroids, assign each vector to its nearest centroid, build the inverted lists (optionally storing quantized codes). Query pipeline: compute distances to all centroids (or use a small index on centroids), select nprobe nearest clusters, search only those lists (with flat vectors, SQ, or PQ). Combining IVF and PQ (IVFPQ) is common for very large scale: coarse quantization by cluster plus fine quantization by PQ codes per vector.

Trade-off: IVF reduces search space but adds centroid-comparison cost; for very large n and moderate d, the reduction dominates. Memory can be reduced by storing PQ codes instead of full vectors in each list; see how PQ compresses vectors into codes and the concept of codebooks in PQ. Search space reduction techniques and flat indexing (when brute force is better) help choose the right design.