IVF search: nlist, nprobe, recall and cost
300 random points in 2 dimensions keep every number checkable. Real data has hundreds of dimensions and many more vectors, but the mechanism is the same.
IVF (inverted file) groups the vectors into clusters with k-means, then answers a question by searching only the few clusters whose centres are closest to it. The number of clusters (nlist) and the number searched (nprobe) set the speed against recall.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write assign(points, centroids) for 2-D points that returns each point's nearest centroid index using squared distance, with ties going to the lower index. Print the labels for the points (0, 0), (1, 1), (5, 5), (6, 5), (2.5, 2.5) and centroids (0, 0), (5, 5). The last point is exactly in the middle.
Write scan_cost(list_sizes, probe_order, nprobe) returning the distances an IVF search computes: one per centroid plus every vector in the first nprobe lists of probe_order. For list sizes [10, 20, 30, 40] and probe order [2, 0, 3, 1], print the cost for nprobe 1 to 4 next to the exact-search cost. What do you notice at nprobe 4?
Explain it without notes
Describe how an IVF index is built and how it answers a question.
What do nlist and nprobe control, and what happens to speed and recall as you raise each?
Why can IVF miss a true nearest neighbour? Give the example from this topic.
Compute the number of distances a search needs for nlist = 100, 100,000 vectors in equal lists and nprobe = 5. Compare with exact search.
Expected output
list sizes: 27 44 48 23 30 45 36 47
nprobe=1: recall@3 0.878, distances computed per query 44 (exact: 300)
nprobe=2: recall@3 1.000, distances computed per query 82 (exact: 300)
nprobe=3: recall@3 1.000, distances computed per query 121 (exact: 300)
nprobe=8: recall@3 1.000, distances computed per query 308 (exact: 300)
query 0: true neighbour 267 lives in list 0, but the closest centroid is 5