Day 2:Week 10, Day 2: Partition-Based ANN — Inverted File Index (`IVF`), Voronoi Cells & `nlist`/`nprobe`
Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz
Week 10, Day 2: Partition-Based ANN — Inverted File Index (IVF), Voronoi Cells & nlist/nprobe
1. How IVF (IndexIVFFlat) Cuts Search Cost by $20\times\text{–}100\times$
Instead of comparing a query against all vectors, Inverted File Index (IVF) partitions the vector space into nlist (, typically to $4\sqrt{N}K$-Means clustering during index construction:
┌───────────────────────────────┐
│ nlist = 4 Voronoi Cells │
├───────────────┬───────────────┤
│ Cell 0 (C0) │ Cell 1 (C1) │
│ • • • │ • ★ q │ <-- Query q lands near C1 & C3 border!
├───────────────┼───────────────┤
│ Cell 2 (C2) │ Cell 3 (C3) │
│ • • │ • • │
└───────────────┴───────────────┘
- Build Phase: Learn
nlistcentroids and assign each document vector to the inverted list (bucket) of its closest centroid. - Search Phase (
nprobe):- Compare query against the
nlistcentroids (). - Select the
nprobeclosest centroids (e.g.,nprobe = 8out ofnlist = 1024). - Only scan vectors inside those
nprobebuckets! - Expected Candidate Fraction Scanned: (e.g., of the dataset )
- Compare query against the
2. Why nprobe > 1 is Essential (The Boundary Problem)
What if a query lands right on the boundary between Cell 1 and Cell 3?
Its true nearest neighbor might sit just 0.01 units across the border inside Cell 3!
If nprobe = 1, IVF only checks Cell 1 and misses the neighbor in Cell 3. Increasing nprobe (1 -> 4 -> 16) smoothly trades extra CPU compute for higher Recall@K!
In Simple English: How IVF Works Like Shopping Mall Aisle Signs
Searching 10 million vectors without an index is checking every single item in a warehouse one by one.
IVF (Inverted File Index) groups similar vectors into neighborhoods (Voronoi clusters, say nlist = 1,000 grocery aisles):
- When a query arrives ("almond milk"), you don't walk down all 1,000 aisles!
- First check the Aisle Directory (
nprobe = 10nearest aisle signs: "Dairy Alternatives", "Health Foods"...), then scan ONLY the items sitting inside those 10 aisles — jumping 100x faster! - Tuning Rule: Higher
nprobe= better accuracy (recall), slightly slower search. Lowernprobe= faster search, higher chance of missing borderline items!