When you look for a book in a library, you do not read every book. The books are sorted by subject, so you walk to the right section and look there.

Every search in this chapter so far has been exact: the question is compared with every stored piece. That is fine for 1,823 pieces. With millions of pieces, comparing every one for every question is a lot of work, which is why large systems usually avoid it. This lesson measures the library trick: group the pieces first, then search only the nearest groups.

Neighbour. A stored piece whose embedding is close to the question's.

Exact search. Compare the question with every stored piece. Nothing is missed, but every piece costs one comparison: one cosine score, as in earlier lessons.

Cluster. A group of pieces whose embeddings are close to each other.

Centre. One embedding that stands for a whole cluster: the average of its pieces, scaled back to length 1.

Probe. One cluster you choose to search inside. More probes means more clusters searched.

Recall. Exact search finds the best results. Recall is the share of those that a faster search also finds. The report below calls it "found exact top 5".

Right lesson. As in lesson 6, each quiz question comes from one lesson, and that lesson is the right answer.

Seed. The number that fixes a random start, so a run can be repeated. Seed 1, 2 and 3 are three different random starts.

This file embeds nine short texts about three topics, groups them into three clusters with a method called k-means (explained two slides on), and then answers one question two ways: by comparing it with all nine, and by comparing it only with the texts in the nearest cluster. Here it is, open in my VS Code.

And this is what it printed:

Both searches found the same best text. Exact search compared the question with 9 texts. Cluster search compared it with 3 centres and then only the 2 texts in cluster 0.

Look at cluster 1, though. "A token bucket refills slowly and allows short bursts" is about rate limiting, the very topic of the question. It landed in cluster 1 with two caching texts, so the cluster search never looked at it.

Here that did not change the best answer. But it shows the risk: clusters are built from closeness between numbers, not from topics, and a good match can sit in a cluster you skipped.

Exact search compares the question with every piece, every time.

Clustered search does some work once, before any question arrives. It groups the pieces with a method called k-means:

1. Pick some pieces at random as the first centres. Here, 32 of them.
2. Assign every piece to its nearest centre.
3. Move each centre to the average of the pieces now assigned to it.
4. Repeat assign and move. The lab did it 25 times.

That map is the real data, squashed from 768 numbers to 2 so it can be drawn. This flat picture keeps only 9% of the differences between the pieces, which is why the colours look mixed. The clusters are built in the full 768 numbers, not on this map.

Then, for each question:

This is called an inverted file index, or IVF. You choose how many clusters to search; that number is called the probes. It is the dial you turn: more probes means more work and fewer misses.

The same test as lessons 6, 8 and 9:

• Documents: 1,823 pieces of 200 words from 112 lessons, nomic-embed-text vectors.
• Questions: the 470 quiz questions inside those lessons.
• Exact search as the reference.
• Clustered search with 32 clusters, about 57 pieces each on average, searching 1, 2, 4, 8, 16 or all 32 of them. 32 is a choice for this size, not a rule; with more pieces you would use more clusters.
• Three random starts for k-means, to see how much luck matters.

The work is counted, not timed. With only 1,823 pieces every search takes a tiny fraction of a second on a laptop, so a timing would say almost nothing. The count of comparisons says exactly how much less work was done. It includes the 32 comparisons with the centres, which is why searching all 32 clusters comes to 102% of exact search.

Here is the lab's report, from the terminal.

As a check, exact search found the right lesson in the top 5 for 441, the same as lessons 8 and 9.

The curve rises fast and then flattens:

• 1 cluster of 32: 6% of the comparisons, and 53 to 59% of the exact top 5 found.
• 8 clusters: 32% of the comparisons, and 94 to 95% found.
• 16 clusters: 60% of the comparisons, and 99% found.

Each range is the lowest to the highest of the three random starts.

For finding the right lesson, the picture is the same. With 8 probes, 429 to 430 questions still found their lesson in the top 5, against 441 with exact search.

Why can the right lesson still be found when some of the exact top 5 pieces are missed? Two reasons. A lesson has many pieces, so if its best piece sits in a skipped cluster, another of its pieces may still be searched; its score drops a little, but it can stay in the top 5. And lessons with no piece searched cannot compete at all, which can move the right lesson up.

With only 1 probe, the three random starts gave 349, 343 and 338 right lessons. This is surprising: seed 1 found only 53% of the exact top 5 pieces, but it found the most right lessons. That is the effect from the last slide: finding a lesson needs only one of its pieces, not its best one. With one probe, luck decides a lot. The start decides which pieces end up together, and when you search one small group, that decision matters. With 16 probes, the starts differed by only one question.

Notice the last point: searching all 32 clusters costs a little more than exact search, 1,855 against 1,823, because the 32 centres are compared as well. Clustered search only pays off when you search a fraction of the clusters.

This box holds the real ranks from the test, for seed 1: for each of the 470 questions, which place the right lesson got (112, the last place, means it was not found at all), with exact search and with 1, 4, 8 or 16 clusters searched. Press Run. Then change PROBES to "1" or "16", and TOP to 1.

1. Start with exact search. It never misses. This lesson did not time anything, so time it yourself on your own data.
2. When it becomes too slow for you, for example when answers take longer than your users will wait, switch to a clustered or other approximate method. Approximate means it may miss a few results in exchange for less work.
3. Turn the dial: raise the number of clusters searched until the misses are few enough for you. Here, 16 of 32 missed 1 or 2 of 441 right lessons.
4. Always measure against exact search. Exact is the reference that tells you what the shortcut costs.

Vector databases (databases built to store embeddings and search them) offer several fast search methods. The clustered one in this lesson is often called IVF. Another common one, HNSW, links each piece to a few of its near neighbours, like a map of roads between them, and walks along those links towards the question. This lesson did not test HNSW.

Measured: one model, 32 clusters, three random starts, 470 quiz questions over 1,823 pieces. Work was counted as comparisons, exactly.

Not measured: time, other numbers of clusters, graph methods like HNSW, and questions from real users. At millions of pieces the numbers would change, and a real database adds its own costs, such as reading from disk.

1. Run find_neighbours.py and read which texts landed together.
2. Start with exact search, until it is too slow for you.
3. Then cluster, and raise the probes until misses are rare.
4. Measure against exact search, on your own questions.