IVF: Inverted File Index (The "Clustering" Part)

Divide and Conquer

If HNSW is a highway system that lets you navigate anywhere quickly, IVF (Inverted File Index) is a filing cabinet. Instead of navigating a graph, IVF partitions your entire vector space into regions and, at query time, only searches the relevant region. You trade some recall for a dramatic reduction in the number of vectors you need to examine.

Building the IVF Index

Step 1 — Training (K-Means Clustering):
IVF requires an offline training step. You run K-Means clustering on a representative sample of your vectors to find nlist centroids — representative points that define regions of the vector space. A typical value is nlist = sqrt(N), so for 1 million vectors you'd use ~1,000 centroids.

Step 2 — Assignment (Voronoi Cells):
Every vector in your database is assigned to its nearest centroid. This partitions the vector space into nlist Voronoi cells — regions where every point is closer to that cell's centroid than to any other centroid.

Step 3 — Inverted Index Construction:
An inverted index is built: a mapping from each centroid ID to the list of vectors assigned to it.

Centroid_0  → [vec_4, vec_17, vec_203, ...]
Centroid_1  → [vec_2, vec_88, vec_991, ...]
...
Centroid_999 → [vec_7, vec_55, vec_10001, ...]

The Search

When a query vector arrives:

1. Coarse search: Compare the query to all nlist centroids. Find the nprobe closest centroids. This is fast — you're comparing against 1,000 centroids, not 1 million vectors.
2. Fine search: Retrieve all vectors from those nprobe cells. Compute exact distances within this subset.
3. Return top-K.

The nprobe parameter is the primary recall-vs-speed knob:
- nprobe=1: Search only the single closest cell. Fastest, lowest recall.
- nprobe=10: Search the 10 closest cells. Slower, higher recall.
- nprobe=nlist: Equivalent to brute force. Perfect recall, no speedup.

The border problem: A query vector sitting near the boundary of two Voronoi cells might have its true nearest neighbor in the adjacent cell. With nprobe=1, you'd miss it. This is the fundamental recall limitation of IVF. Setting nprobe to 5–20% of nlist typically recovers most of the lost recall at a modest speed cost.

Senior depth — training data matters: IVF's quality depends entirely on how representative the training sample is. If your training data doesn't reflect the distribution of your actual vectors (e.g., you train on English text but later add multilingual embeddings), the centroids will be poorly placed and recall will degrade silently. Production systems should retrain the IVF index whenever the data distribution shifts significantly — a fact that is easy to overlook and expensive to discover after deployment.