The "Librarian" Approach
Imagine a library with one million unsorted books piled randomly on the floor. Finding a specific book would require checking every single one. A librarian solves this by organizing books into labeled sections (History, Science, Fiction) and placing them on dedicated shelves. To find a book, you first identify the right section, then search only that shelf.
IVF (Inverted File Index) applies this exact logic to vectors:
Step 1 — Training (Clustering): IVF runs a clustering algorithm (typically k-means) over your entire dataset to identify natural groupings. It computes a centroid (center point) for each cluster. You choose the number of clusters, typically in the range of sqrt(n) where n is your dataset size.
Step 2 — Assignment: Every vector in your database is assigned to its nearest centroid and stored in that cluster's "bucket."
Step 3 — Searching: When a query vector arrives, IVF first compares it to all centroids (a fast operation since there are far fewer centroids than vectors). It identifies the closest nprobe clusters (a tunable parameter, typically 1–10). It then performs exact search only within those clusters, ignoring the rest of the database.
The key tunable parameter is nprobe: higher values search more clusters, improving recall at the cost of speed. Lower values are faster but may miss the true nearest neighbor if it sits in a cluster whose centroid is not the closest to the query.
IVF trade-offs:
- ✅ Memory-efficient — vectors can be compressed with quantization
- ✅ Good for very large datasets (billions of vectors)
- ❌ Requires a training step before indexing
- ❌ Can miss neighbors near cluster boundaries ("boundary problem")
- ❌ Performance degrades if data distribution shifts after training