Topic 3.2
Why Search Becomes Approximate
In one line
Sorting and tree structures that make ordinary database lookups fast stop helping when vectors have hundreds of numbers. Vector indexes therefore trade a little accuracy for a lot of speed, and the accuracy is measured as recall against the exact answer.
Think of it like this
A librarian is asked for "a book that feels like this one". The shelves are sorted by author, which is no help at all, because "feels like" is not a position on a shelf. To be sure of the very best match she would have to open every book. A faster librarian walks to the shelves where similar books usually sit, looks there, and accepts that once in a while the best match was on a shelf she skipped.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Approximate nearest neighbour (ANN)
- Search that returns mostly, but not always exactly, the true nearest vectors, in return for much less work.
- Recall@k
- Of the k true nearest neighbours, the fraction the search returned. 1.0 means it found all of them.
- Index
- A structure built ahead of time from the vectors so that searching them takes less work than looking at all of them.
- k-d tree
- A tree that splits points by one coordinate at a time. Fast in a few dimensions, little help in hundreds.
- Curse of dimensionality
- The set of effects that make geometry unhelpful in many dimensions, such as distances bunching together.
- Ground truth
- The exact top k, used to score an approximate method.
Step by step
01Step 1: what a database does for one number
To find the price 25 among a million prices, a database keeps them sorted and jumps: about 20 steps instead of a million. That works because one number has one order. Ask yourself what order would put "similar meaning" next to each other for vectors of 384 numbers. There is none.
02Step 2: watch the distances bunch together
Run the first example. The ratio nearest/farthest climbs from 0.02 in 2 dimensions to 0.42 in 16 and 0.76 in 128. When the closest point is three quarters as far as the farthest, a rule like "skip everything beyond this line" skips almost nothing.
03Step 3: accept looking at less
The second example is the laziest approximation: only look at the first 100, 200 or 300 of 400 vectors. Fewer comparisons, so faster. The cost is that the true neighbours in the part you skipped are never found.
04Step 4: score it with recall
A small function does the scoring: the size of the overlap between the approximate list and the exact list, divided by k.
def recall(found, truth):
return len(set(found) & set(truth)) / len(truth)
recall([3, 1, 7, 9], [1, 2, 3, 4]) # 0.5: it found 1 and 305Step 5: read the dial
Averaged over 20 questions, scanning 25 percent of the vectors gives recall@5 of 0.23, 50 percent gives 0.44, 75 percent gives 0.72 and 100 percent gives 1.00. Recall rises with work. A good index bends this curve: high recall for a small fraction of the work.
06Step 6: look at real scores
The lab below uses a real embedding model. Ask "Do you rent scooters?", which the handbook cannot answer: the best passage still scores about 0.38 (the helmet passage) and the next about 0.36, and only the very worst is near or below zero. Real similarity scores of unrelated texts sit in a band well above zero, which is the same bunching you measured with random points, and which is why a threshold on score needs care (Topic 8.4).
Try it yourself
- 1
More dimensions
In the first example change the list of dimensions to
[2, 3, 4, 8, 32, 256]. Predict where the ratio crosses 0.5, then run. What happens to the cost of the run? - 2
Change k
In the second example set
Kto 1 and then to 20. Does recall at the same scan size go up or down? Why is finding only the single best neighbour easier or harder than finding twenty? - 3
Look at one query
Print recall for each query separately instead of the average. Is every query roughly equal, or do some score 0 while others score 1? What does that say about reporting only an average?
- 4
Switch languages
Run both examples in Python, Java and JavaScript. The three outputs are identical because all three use the same seeded generator, so you can trust a number like 0.440 on any of them.
Code & diagrams
Uniform random points have no structure, so this exaggerates the effect for real embeddings. It shows the direction of the problem, not the exact numbers you will see on real data.
Expected output
300 random points; distance from one query to its nearest and its farthest point
2 dims: nearest 0.024, farthest 1.093, nearest/farthest 0.022
16 dims: nearest 0.932, farthest 2.248, nearest/farthest 0.415
128 dims: nearest 4.011, farthest 5.274, nearest/farthest 0.760"First part of the data" is a deliberately bad approximation. Real indexes (the next topics) choose which part to look at.
Expected output
approximation: look only at the first part of the data (20 queries, k = 5)
scan 100 of 400 vectors: recall@5 = 0.230
scan 200 of 400 vectors: recall@5 = 0.440
scan 300 of 400 vectors: recall@5 = 0.720
scan 400 of 400 vectors: recall@5 = 1.000
query 0, exact top-5: 136, 309, 388, 51, 244
query 0, first 200: 136, 51, 0, 169, 115Try: Press Search for scooters, which no passage mentions, and note the best cosine score (about 0.38, even though nothing is relevant). Then solve the goal: change the question so that the helmet passage scores at least 0.55 against it. Hint: write a question that is about what the helmet passage says, for example one that mentions wearing a helmet. Which words pushed the score up?
Goals
- The helmet passage scores at least 0.55
Press Search. Then change one thing (a word in the question, a passage, the ranker) and compare the scores.
Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Measure recall against the approximate answer itself
In the Python tab of the second example, change the ground truth in the loop from top_ids(points, q, K, 400) to top_ids(points, q, K, scan).
Break #2
Test with queries that are copies of stored vectors
In the Python tab of the second example, replace the line that defines queries with queries = points[:20].
Myth vs fact
Myth
Approximate means inaccurate.
Fact
Good indexes return the exact top k for most questions and a near-neighbour in its place for the rest. You choose the accuracy with the settings, and you measure it.
Myth
A recall of 0.95 means 5 percent of answers are wrong.
Fact
A missed neighbour matters only if it held the answer, and a close substitute often serves just as well. Measure answer quality directly as well (Phase 9).
Myth
Tests on random vectors show how an index will behave on my data.
Fact
Random points have no structure. Real embeddings cluster, so indexes usually do better on them than on random data, and some settings behave differently. Always benchmark on your own embeddings and your own questions.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Report recall as a distribution, not one average: the mean, the worst few questions and the share of questions below some floor (say, recall below 0.5). A single query with recall 0 is a user who got no relevant context.
- ▸
Recall depends on k. Recall@100 is usually higher than recall@10 for the same index, because there are more chances to include each true neighbour, and what matters is the k your pipeline actually uses (including any wider first stage before re-ranking, Phase 6).
- ▸
Ties and near-ties make recall noisy: two passages at 0.542 and 0.538 are interchangeable for the user, but swapping them counts as a miss. Some teams score by similarity (is the returned score close to the best score?) in addition to membership.
Remember this
- 1
Why exact search stops being enough. Topic 3.1 showed the cost: every question touches every vector. At a million vectors that is hundreds of milliseconds and gigabytes of memory per copy. A database avoids this for ordinary columns by keeping them in order or in a tree, so a lookup skips almost everything. The question for this phase is whether vectors allow the same trick.
- 2
Why sorting and trees fail. Sorting works on one number: the answer to "which comes next" is clear. A vector has hundreds of numbers and no single order that keeps similar vectors together. The classic tree for points, the k-d tree, splits the space one coordinate at a time, and in 2 or 3 dimensions a query can skip most branches. In hundreds of dimensions the nearest neighbours sit close to many splits at once, so the search must visit nearly every branch. A rule of thumb from the literature is that such trees only pay off when the number of points is far larger than 2 to the power of the dimension, which for 384 dimensions is never. This is one face of the curse of dimensionality.
- 3
Distances bunch together. The first example draws 300 random points and measures the distance from one question to its nearest and farthest point. In 2 dimensions the nearest is about 0.02 times as far as the farthest, so the neighbour stands out clearly. In 16 dimensions the ratio is about 0.42, and in 128 dimensions about 0.76: almost everything is nearly the same distance away, so there is little to skip. Real embeddings are not uniformly random (they have structure, similar texts really are close, and that structure is what lets the methods in this phase work), but the pull toward "everything looks equally far" is why you cannot rely on simple shortcuts.
- 4
The deal: approximate nearest neighbours. Instead of the exact top k, an index returns k results that are *mostly* the true nearest. This is approximate nearest-neighbour search (ANN). The second example is the crudest possible version, looking only at the first part of the data, and it already shows the dial every ANN method has: scanning a quarter of the vectors takes a quarter of the work and finds about 23 percent of the true top 5, half the data finds about 44 percent. Good indexes do far better than this, because they look at the *right* part of the data, but the dial is the same: more work, higher accuracy.
- 5
Recall, by hand. The accuracy of an approximate search is recall@k: of the k true nearest neighbours (from exact search, Topic 3.1), how many did the index return? If the true top 4 are 1, 2, 3, 4 and the index returned 3, 1, 7, 9, it found 2 of 4: recall 0.5. Order inside the list does not count, only membership. You compute it for many questions and average, and you also look at the worst questions, because an average of 0.95 can hide questions with recall 0. Query 0 in the example: the true top 5 are 136, 309, 388, 51, 244 and scanning half the data returns 136, 51, 0, 169, 115, which contains 2 of them: recall 0.4.
- 6
Why recall is a means, not the goal. In a RAG system a missed neighbour only hurts if it is the passage that holds the answer, and a near-miss in its place may be nearly as good. So recall@k is a fast, cheap stand-in you can compute without a language model, to compare indexes and settings. The final judge is still whether the *answers* are right (Phase 9). Use recall to keep the index from silently getting worse, not as a promise about answer quality.
- 7
The rest of the phase. Three families of ideas follow. Look at fewer vectors by grouping them into clusters (IVF, Topic 3.3) or by walking a graph of neighbours (HNSW, Topic 3.4). Make each comparison cheaper with smaller numbers (quantisation, Topic 3.5). Then learn to measure the trade properly (Topic 3.6).
Explain it without notes
Why can a database find one number among millions with about twenty steps, but not the nearest vector among millions?
What does the distance table in the first example show, and why does it hurt indexing?
Define recall@k and compute it for found = [3, 1, 7, 9] against truth = [1, 2, 3, 4].
Why must the ground truth for recall come from exact search over the whole collection?
A teammate says the index has recall 0.97, so it is fine. What would you check before agreeing?
Practice
Write recall_at_k(found, truth) that returns the fraction of truth present in found. Print it with 3 decimals for found [3, 1, 7, 9] against truth [1, 2, 3, 4], for an empty found list, and for the same four ids in reverse order.
Three queries have (found, truth) pairs ([1, 2, 3], [1, 2, 3]), ([4, 5, 6], [4, 9, 6]) and ([7, 8, 9], [1, 2, 3]). Print each query's recall and then the average and the worst, to 3 decimals. What does the average hide?
Trade-offs
- ↔
Approximate search: far less work per question, at the price of occasionally missing a true neighbour.
- ↔
Higher recall targets: closer to exact, and they cost more work and memory. Each extra point of recall costs more than the previous one.
- ↔
Measuring recall needs the exact top k for every test question: some one-time compute, in return for numbers you can trust.
Done when you can
Done when you can explain why sorting and trees do not give fast nearest-vector search in many dimensions.
Done when you can compute recall@k by hand for two lists.
Done when you can explain why ground truth must come from exact search over everything.
Done when you can name what recall does and does not tell you about answer quality.