IVF Indexes: Centroid Partitioning for Coarse-to-Fine Search
How inverted file (IVF) indexes use k-means centroids to partition vector space for fast coarse-to-fine similarity search, and how to tune nprobe.
Published on • November 22, 2026
AI Assistant

Introduction
While graph indexes like HNSW navigate point-to-point, IVF (Inverted File) indexes take a different route: divide the space into regions, then only search the regions that could contain good matches. It is the vector-search equivalent of knowing which neighbourhood to look in before checking every house.
How IVF Works
1. Training (offline)
Run k-means clustering over the corpus (or a sample) to produce nlist centroids. Each centroid defines a Voronoi cell — the region of space closer to that centroid than any other.
2. Assignment
Every vector is assigned to its nearest centroid and stored in that centroid’s postings list (the “inverted file” — same term as an inverted index in text search, but the term here is a cluster ID).
3. Coarse-to-fine query
- Compute distances from the query to all
nlistcentroids (cheap:nlistis thousands, not millions). - Select the
nprobeclosest centroids. - Exhaustively scan only those cells’ vectors.
- Merge and return the top-k.
Query cost ≈ nlist centroid distances + (n / nlist) × nprobe full-vector comparisons.
The Key Parameter: nprobe
nprobe slides along the recall–latency curve:
- nprobe = 1 → fastest, lowest recall (only the nearest cell)
- nprobe = nlist → exact brute force
- Typical starting point: 1–10% of nlist, tuned against ground-truth recall
Like HNSW’s efSearch, nprobe can be adjusted per query without rebuilding.
Choosing nlist
- More lists (e.g.,
4 × sqrt(n)to16 × sqrt(n)is a common rule of thumb) → smaller cells → fewer candidates per probe → faster, but clustering quality matters more - Clustering needs data: train on at least ~1000 vectors per centroid if possible
- Too few lists → huge cells → probes scan too much; too many lists → tiny cells → boundary effects and worse recall at low nprobe
Strengths and Weaknesses
Strengths
- Memory-efficient: postings are compact; pairs naturally with PQ compression (IVF-PQ is the classic FAISS billion-scale combo)
- Scales linearly with corpus size
- Simple, well-understood behaviour
Weaknesses
- Cluster quality is everything — skewed data breaks Voronoi assumptions
- Boundary problem: true neighbours can sit in a neighbouring cell just outside the probe set — a known recall ceiling that rescoring or graph refinement can fix
- Training is a separate, corpus-dependent step; distribution shift hurts
When to Use IVF
IVF shines at large scale with compression (IVF-PQ on billions of vectors), and where memory matters more than the last few recall points. For smaller corpora where raw recall and simple tuning dominate, HNSW is usually easier; for massive memory-bound indexes, IVF remains a workhorse.
Conclusion
IVF converts “search everything” into “search the right neighbourhoods”: k-means partitions the space at build time, and nprobe decides at query time how many neighbourhoods to visit. It is simple, compressible, and battle-tested at billion-vector scale — provided your clusters are healthy.