Inverted files
Trace IVF and HNSW search and explain how candidate exploration trades latency for recall.
THE IDEA
Inverted files: search only some clusters
An inverted file (IVF) index first groups the vectors into clusters around coarse centroids. At query time it finds the centroids nearest the query and scans only the vectors in those lists. With 102,400 vectors in 1024 cells (about 100 each), probing 8 cells scans about 800 vectors instead of 102,400. The price: a true neighbour sitting in a cell that was not probed is never seen.
Try query 5.1 with nprobe 1: the point at 4.6 lives in the neighbouring cell, so it is never looked at. At scale, 102,400 vectors in 1024 cells means about 100 per cell, so probing 8 cells scans about 800 vectors.
Predict first. Does searching only the nearest coarse centroid guarantee the exact nearest original vector?
Chapter context
An approximate index organizes vectors so a query can avoid most comparisons. Clustering and graph navigation use different mechanisms to choose candidates, and their build settings influence later search quality.
TRY IT YOURSELF
Part 1. Do it hands-on
Work out the cost and the miss by hand, then build an IVF index and search.
Try query 5.1 with nprobe 1: the point at 4.6 lives in the neighbouring cell, so it is never looked at. At scale, 102,400 vectors in 1024 cells means about 100 per cell, so probing 8 cells scans about 800 vectors.
- To do: 102,400 vectors divided evenly among 1024 cells: vectors per cell?
- To do: Probing 8 cells scans about how many vectors (excluding the 1024 centroid comparisons)?
- To do: Toy data on a line: centroids 0, 10, 20; points 0:−1, 1:1, 2:4.6, 3:7, 4:9, 5:11, 6:19, 7:21, 8:22, 9:24. Query 5.1, nprobe = 1. Which point id does the IVF search return (the nearest inside the probed list)?
- To do: Which id is the true nearest neighbour of 5.1?
Part 2. Do it in code
- assign(x, centroids): the index of the nearest centroid (ties: lower index).
- build_lists(xs, centroids): a list with one list of point ids (ascending) per centroid.
- ivf_search(q, xs, centroids, lists, nprobe, k): rank centroids by distance to q (ties: lower index), take the first nprobe lists, and return the k nearest point ids among those candidates, nearest first (ties: lower id). nprobe < 1 raises ValueError; nprobe above the number of lists is clamped.
- exact_search(q, xs, k): the k nearest ids over all points (the ground truth).
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Does searching one nearest coarse centroid guarantee the exact nearest original vector?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
Under the simplifying assumption of equally sized IVF lists, N vectors, C cells and p probes produce approximately
Add coarse scoring, uneven list sizes and any reranking costs separately. HNSW has no equivalent universal fixed candidate-count formula.
Worked example
For 102,400 vectors evenly divided among 1024 cells, a cell has 100 vectors. Probing eight cells scans about 800 candidates, compared with 102,400 in a full scan. This excludes coarse-centroid comparisons and says nothing by itself about recall.
Reference code
The following example uses the Python standard library and does not call a remote service.
total,cells,probes=102400,1024,8
assert total/cells == 100
assert total*probes/cells == 800
assert total/(total*probes/cells) == 128
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
An average candidate count is not an actual worst-case bound. More graph edges consume memory. Approximate search settings must be evaluated against the current corpus and metric.