Skip to content
Blog

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

  1. Compute distances from the query to all nlist centroids (cheap: nlist is thousands, not millions).
  2. Select the nprobe closest centroids.
  3. Exhaustively scan only those cells’ vectors.
  4. 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) to 16 × 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.

References