Topic 3.3
IVF by Hand
In one line
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.
Think of it like this
You are looking for the nearest cafe in a big city. You do not check every street. The city is divided into districts, you look first in your own district, and if you are standing near a border you look in the next district too. Almost always the nearest cafe is in one of those districts. Very rarely it is just over a border you did not cross.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Cluster
- A group of vectors that are close to each other.
- Centroid
- The centre of a cluster: the average of its vectors.
- k-means
- A method that finds k clusters by repeatedly assigning points to the nearest centroid and moving each centroid to the average of its points.
- nlist
- How many clusters (inverted lists) the IVF index has. pgvector calls it lists.
- nprobe
- How many of the nearest clusters a search opens. pgvector calls it probes.
- Inverted list
- The list of vector ids stored for one cluster.
- IVF
- Inverted file index: clusters plus the lists of vectors in them. Often called IVFFlat when the lists hold the full vectors.
Step by step
01Step 1: a picture of the idea
Sixty points are scattered over a square. Four starting centroids are picked from the data. Every point joins the nearest centroid, then each centroid moves to the middle of its group. After a few rounds the four groups settle.
02Step 2: run k-means by hand
The first example prints the cluster sizes and the total squared distance after each of five rounds. Round 1 has sizes 4, 35, 6 and 15 (the guesses were poor), round 5 has 18, 8, 11 and 23. The total distance drops every round, which is how you know the method is working.
for step in range(5):
labels = [nearest_centroid(p, centroids) for p in points] # assign
centroids = [mean(points of cluster c) for c in range(k)] # move03Step 3: build the lists
Once the centroids are fixed, one more pass sends every vector to its list. The result is lists[c], the ids of the vectors in cluster c. The vectors themselves stay where they are.
04Step 4: search the nearest lists only
Sort the centroids by distance to the question, keep the first nprobe, join their lists, and rank just those candidates exactly. The result is an exact top k *among the candidates*.
probes = sorted(range(nlist), key=lambda c: dist2(q, centroids[c]))[:nprobe]
candidates = [i for c in probes for i in lists[c]]
candidates.sort(key=lambda i: dist2(q, points[i]))
return candidates[:k]05Step 5: read the table
The second example prints recall@3 and the distances computed for nprobe 1, 2, 3 and 8. Recall reaches 1.00 at nprobe = 2 for 82 distances, against 300 for exact search: about 3.7 times less work with no loss on these 30 questions. At nprobe = 8 (every list) it is 308: exact search plus overhead.
06Step 6: find a miss
The last line of the example finds the first question that nprobe = 1 gets wrong, and shows why: the neighbour lives in list 0, but the question's nearest centroid is centroid 5. The question sits near a border. Opening one more list would have fixed it.
Try it yourself
- 1
Different starting points
In the first example change the starting centroids to
points[1], points[2], points[3], points[4]. Do the sizes after round 5 match the original? Is the final distance higher or lower? What does that say about trusting one run of k-means? - 2
Turn the knobs
In the second example set
NLIST = 16and keep the starting stepi * 37by changing it toi * 18. Fornprobe1, 2 and 3 compare recall and distances with the table forNLIST = 8. Which setting gets recall 1.00 with the fewest distances? - 3
Predict the miss
Change the final loop to print the first three queries that
nprobe = 1gets wrong. For each, check whether the true neighbour's list is the second-closest centroid to the question. Is it always?
Code & diagrams
Real k-means libraries pick random or smarter starting centroids. Fixed starting points keep this example identical in all three languages.
Expected output
step 1: cluster sizes [4, 35, 6, 15], total squared distance to centroids 6.326
step 2: cluster sizes [14, 20, 7, 19], total squared distance to centroids 3.849
step 3: cluster sizes [18, 11, 9, 22], total squared distance to centroids 2.973
step 4: cluster sizes [17, 9, 11, 23], total squared distance to centroids 2.649
step 5: cluster sizes [18, 8, 11, 23], total squared distance to centroids 2.574
centroid 0: (0.197, 0.352)
centroid 1: (0.582, 0.095)
centroid 2: (0.270, 0.803)
centroid 3: (0.769, 0.616)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.
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 5Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Open the farthest lists instead of the nearest
In the Python tab of the second example, in ivf_search, change the sort key to key=lambda c: -dist2(q, centroids[c]).
Break #2
Skip the training rounds
In the Python tab of the second example, change the number of k-means rounds in the call kmeans(points, ..., 5) from 5 to 0.
Myth vs fact
Myth
More clusters always gives a faster and better index.
Fact
More clusters make lists shorter but add centroid comparisons and more borders to fall across, so you often need a larger nprobe to keep recall. Measure instead of assuming.
Myth
With nprobe = 1 IVF finds the exact nearest neighbour.
Fact
Only when the neighbour happens to be in the same cluster as the question's nearest centroid. Near borders it is not.
Myth
k-means gives one correct answer.
Fact
It depends on the starting centroids and can settle into different groupings. That is fine for an index, because any reasonable grouping works, as long as you measure recall afterwards.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Real IVF indexes usually pair the clusters with compressed vectors (Faiss calls the combination IVFPQ) so that million-scale lists fit in memory (Topic 3.5). The lists then hold short codes, and a final re-score with full vectors fixes the ranking.
- ▸
List sizes decide latency. A cluster with ten times the average size makes every question that opens it ten times slower. Watch the size distribution after training, and consider more clusters or a better training sample if it is very skewed.
- ▸
For cosine similarity, normalise the vectors first and cluster by Euclidean distance: on unit vectors it ranks identically to cosine (Topic 2.3). Mixing the two measures in training and search is a quiet recall killer.
- ▸
Updates are cheap (assign the new vector to its nearest centroid and append it) but the centroids never move, so a data set that drifts, such as a new product line, slowly degrades recall until you retrain.
Remember this
- 1
Why this exists. Topic 3.2 showed that we must look at fewer vectors. The cheapest way to decide which vectors to skip is to sort them into groups ahead of time, and to open only the groups that look promising for the question at hand. That is IVF, the inverted file index. The name comes from the keyword indexes of Topic 1.2: there, each word points to a list of the documents containing it. Here, each *cluster* points to a list of the vectors inside it.
- 2
Step one: find the clusters with k-means. k-means starts with
kguesses for the cluster centres (the centroids). Then it repeats two steps: assign every point to its nearest centroid, and move each centroid to the average of the points assigned to it. A tiny case: if three points(0, 0),(2, 0)and(1, 3)are assigned to one centroid, it moves to their average,(1, 1), because (0 + 2 + 1) / 3 = 1 and (0 + 0 + 3) / 3 = 1. The first example runs five rounds on 60 points in 2 dimensions with 4 clusters. The "total squared distance to centroids" falls round by round (6.326, 3.849, 2.973, 2.649, 2.574), so the clusters tighten around their points and the changes get smaller. The example starts from fixed points so it prints the same thing in every language; real libraries choose the starting centroids randomly or with a smarter rule, train on a sample of the data, and stop after a fixed number of rounds or when little changes. - 3
Step two: build the inverted lists. After training, every stored vector is assigned to its nearest centroid and written into that centroid's list. The number of clusters is called **
nlist**. The second example usesnlist = 8over 300 points, giving lists of 27, 44, 48, 23, 30, 45, 36 and 47 vectors. Uneven sizes are normal. - 4
Step three: search. For a question, compute its distance to all
nlistcentroids (cheap: only 8 here), pick the **nprobe** closest ones, and compare the question only with the vectors in those lists. Withnprobe = 1the example computes about 44 distances per question (8 centroids plus the vectors in one list) instead of 300; withnprobe = 2, about 82. The work isnlist + (vectors in the opened lists). - 5
What it misses, and why. A true neighbour is missed when it sits in a cluster that was not opened. This happens near the border between two clusters: the question falls on one side, its neighbour on the other. In the example, for question 0 a true neighbour (id 267) lives in list 0, but the question's closest centroid belongs to list 5. Recall (Topic 3.2) is the share of the true top 3 that the search found. With
nprobe = 1recall@3 is about 0.88 over 30 questions; withnprobe = 2it is 1.00, at about 82 distances instead of 44. Raisingnprobebuys recall with work, andnprobe = nlistis exact search plus the cost of the centroids (308 distances, more than the 300 of plain exact search). - 6
Choosing the numbers. More clusters make each list shorter, but there are more centroids to compare with and more borders to fall across. A common starting rule is about the square root of the number of vectors for
nlist; pgvector's documentation suggestslistsof rows / 1,000 up to a million rows and the square root of the rows beyond that, withprobesstarting around the square root oflists(its default is 1). Treat these as starting points and measure recall (Topic 3.6). Also remember that IVF learns its clusters from the data it is built on: if the data changes a lot later, new vectors are placed in the old clusters and quality drifts, so rebuild occasionally.
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.
Practice
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?
Trade-offs
- ↔
Larger nprobe: higher recall and slower queries. Smaller nprobe: the reverse.
- ↔
More clusters: shorter lists but more centroid work and more borders. Fewer clusters: long lists and close to exact search.
- ↔
IVF versus graph indexes (next topic): IVF builds fast, uses little extra memory and updates cheaply, while graph indexes usually give better recall for the same speed at the cost of memory and build time.
Done when you can
Done when you can run k-means by hand for one round on a few points.
Done when you can describe how an IVF index is built and searched.
Done when you can compute the distances per query for given nlist, list sizes and nprobe.
Done when you can explain a missed neighbour by pointing at a cluster border.
Done when you can name what to check after training (list sizes, recall at the production nprobe).