Topic 3.6
Tuning Recall Against Speed
In one line
A faster index is only better if you know what it gave up. A trustworthy benchmark uses exact search as ground truth, real questions, a hardware-independent cost such as distances computed, and one knob turned at a time, then reads the curve for the cheapest setting that meets a recall target.
Think of it like this
You find a shortcut to work and want to know if it is really better. Taking it once proves nothing. You would take both routes on many mornings, check that you always arrive at the same door (not a similar one), and time both. Only then do you say "the shortcut is faster, and gets me to the right place 19 mornings out of 20". A benchmark for an index is exactly this, with numbers.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Benchmark
- A repeatable test that measures recall and cost for given settings.
- Ground truth
- The exact top k for each test question, from exact search.
- Knob (parameter)
- A setting you choose, such as nprobe or efSearch.
- Sweep
- Running the benchmark for a range of values of one knob.
- Knee
- The point on a recall curve where extra work starts buying very little extra recall.
- Distances computed
- A count of similarity computations per question: a cost measure that does not depend on hardware.
- Held-out questions
- Test questions not used to choose the settings.
- Noise
- Random variation that makes small recall differences meaningless on a small test set.
Step by step
01Step 1: build the ground truth once
For each of the 50 test questions, run exact search and keep the 5 nearest ids. This is the slow step and it runs once. Every later comparison reads these lists.
02Step 2: one function that scores any setting
evaluate runs every test question through the index with a given nprobe, counts how many of the stored true neighbours came back, and counts the distances computed. Averaging gives recall and cost for that setting.
def evaluate(points, queries, truths, centroids, lists, nprobe, k):
hits = cost = 0
for q, truth in zip(queries, truths):
probes = sorted(range(len(centroids)), key=lambda c: dist2(q, centroids[c]))[:nprobe]
candidates = [i for c in probes for i in lists[c]]
found = sorted(candidates, key=lambda i: dist2(q, points[i]))[:k]
hits += len(set(found) & set(truth))
cost += len(centroids) + len(candidates)
return hits / (k * len(queries)), cost // len(queries)03Step 3: sweep one knob
Run evaluate for nprobe in 1, 2, 3, 4, 6, 8, 16 and print one line each. Plot or just read: recall from 0.80 to 1.00, cost from 142 to 2,016.
04Step 4: pick by a target
Decide the recall you need first (say 0.95), then choose the cheapest setting that reaches it. The example prints that choice: nprobe = 2. If recall must be 0.99, the answer becomes 4.
05Step 5: turn a different knob
Fix nprobe = 2 and sweep nlist over 8, 16 and 32. The second table shows cost falling and recall falling together, which says that nlist and nprobe must be chosen as a pair.
06Step 6: write the result down
Record the settings, the recall, the cost, the data size and the date, and keep the benchmark script in the repository. When data or the embedding model changes, rerun it. The playbook (Topic 3.9) packages this as a reusable harness.
Try it yourself
- 1
Raise the bar
Change the recall target from 0.95 to 0.99. Which
nprobeis now the cheapest, and how much more work does that cost than the 0.95 choice? - 2
Change k
Set
K = 10. Does recall atnprobe = 2go up or down compared withK = 5, and why? (Think about how far the 10th neighbour is from the question.) - 3
Measure the noise
Change the queries' seed from 99 to 123 and rerun. How much does recall at
nprobe = 2move? Then use 200 queries instead of 50 and see how the movement changes. - 4
Find a better pair
For
nlist = 32, find the smallestnprobethat reaches recall 0.96. Is its cost lower thannlist = 16withnprobe = 2(265 distances)?
Code & diagrams
2,000 random 4-dimensional points keep the run instant. Real embeddings will show different numbers, but the method (ground truth, sweep, pick by target) is the same one to use on them.
Expected output
nlist = 16, turning nprobe (exact search computes 2000 distances)
nprobe 1: recall@5 0.800, 142 distances
nprobe 2: recall@5 0.964, 265 distances
nprobe 3: recall@5 0.984, 396 distances
nprobe 4: recall@5 0.996, 521 distances
nprobe 6: recall@5 1.000, 768 distances
nprobe 8: recall@5 1.000, 1015 distances
nprobe 16: recall@5 1.000, 2016 distances
smallest nprobe with recall@5 of at least 0.95: 2
nprobe = 2, turning nlist
nlist 8: recall@5 0.944, 519 distances
nlist 16: recall@5 0.964, 265 distances
nlist 32: recall@5 0.896, 160 distancesBreak it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Forget to count the centroid distances
In the Python tab, in evaluate, change cost += len(centroids) + len(candidates) to cost += len(candidates).
Break #2
Benchmark on five questions
In the Python tab, change queries = make_points(50, 4, 99) to queries = make_points(5, 4, 99).
Myth vs fact
Myth
The default parameters are tuned for everyone.
Fact
Defaults are a safe guess. Whether they give enough recall on your data is a measurement, and it is common to find either wasted work or missing neighbours.
Myth
Lower latency always means a better index.
Fact
Only at equal recall. An index that returns in half the time with recall 0.7 has just done less work. Compare settings at the same recall.
Myth
Recall 1.00 on the benchmark means the index is perfect.
Fact
It means it matched exact search on those questions, with that data. A small or unrepresentative set can look perfect and still miss on real traffic.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Add percentiles for latency (p50, p95, p99), not only the average, because search time varies with how many lists are opened or how long a graph walk is. Users feel the slow tail.
- ▸
Re-benchmark when the data distribution shifts (a new product, a new language, a new embedding model) and after big loads. IVF centroids and HNSW graphs both reflect the data they were built on.
- ▸
Make the benchmark a test: assert in your build that recall@k on a fixed question set stays above a floor at the production settings. An index change that quietly drops recall then fails the build.
- ▸
When query-time knobs change per request (HNSW's efSearch, IVF's nprobe), you can offer fast and thorough modes, or raise them automatically when the first results look weak. Both are easy once you know the curve.
Remember this
- 1
Why this exists. Every approximate index (Topics 3.3 to 3.5) has knobs:
nlist,nprobe,M,efConstruction,efSearch, the number of bits, the shortlist size. Defaults are a guess made by someone who did not see your data. "Faster" means nothing without the recall that came with it, and recall means nothing without a cost. You need a small, repeatable benchmark that reports both. - 2
The ingredients. One: the ground truth, the exact top k for each test question from exact search (Topic 3.1), computed once and stored. Two: representative questions, ideally real ones from users, never copies of stored vectors (Topic 3.2). Three: enough of them: with 50 questions and k = 5 the benchmark checks 250 neighbours, so one miss moves recall by 0.004 and differences smaller than about 0.01 are noise. Four: a fixed k, the one your pipeline uses. Five: a cost measure. Six: discipline, changing one thing at a time.
- 3
Count comparisons, then time. The cost in the example is the number of distances computed per question (centroids plus the vectors in opened lists). It is deterministic and does not depend on your computer, so it is perfect for understanding and for tests. It is not the whole story: real speed depends on memory access, caches, threads and vector instructions. So use counted comparisons to learn how a knob behaves, and use real timings on the target machine, with the real data size, for the final decision. Also record memory, and build time for graph indexes.
- 4
**Read the curve for
nprobe.** The example builds an IVF index withnlist = 16on 2,000 vectors (4 dimensions) and sweepsnprobe. Recall@5 is 0.80 atnprobe = 1(142 distances), 0.96 at 2 (265), 0.98 at 3 (396), 0.996 at 4 (521) and 1.00 from 6 (768). Exact search computes 2,000. Recall climbs fast and then flattens, while cost keeps growing in a straight line: the knee is the sweet spot. For a target of at least 0.95, the cheapest setting isnprobe = 2: about 7.5 times fewer distances than exact search. - 5
Turn a second knob. Now fix
nprobe = 2and changenlist. With 8 lists: recall 0.944 at 519 distances. With 16: 0.964 at 265. With 32: 0.896 at 160. Doubling the lists roughly halves the work but loses recall, because there are more borders and two lists cover a smaller part of the space. This is why you compare *points on a recall-and-cost chart*, not knob values:nlist = 32with a largernprobemay beatnlist = 16at the same recall, and only the sweep tells you. The same method works for HNSW: sweepefSearch(Topic 3.4's table went from 0.91 to 1.00 asefrose from 3 to 10) and compare cost. - 6
Pitfalls. Do not tune and report on the same few questions: hold some out. Do not compare two indexes at the same knob value; compare them at the same recall. Do not trust one run on a tiny question set. Do not forget that a benchmark on today's data says little after the data changes a lot, so keep the benchmark in your repository and rerun it when you rebuild. And remember that recall is a proxy: Phase 9 measures the answers themselves.
Explain it without notes
What are the parts of a trustworthy benchmark for an approximate index?
Why count distance computations as well as timing?
Looking at the nprobe sweep, how would you choose a setting, and what changes if the target recall goes from 0.95 to 0.99?
Why should two indexes be compared at the same recall rather than at the same knob value?
Practice
Write cheapest_meeting(results, target) where results is a list of (setting, recall, cost) triples. Return the setting with the lowest cost among those with recall at or above target, or None if none qualifies. Print the answers for the results [(1, 0.800, 142), (2, 0.964, 265), (3, 0.984, 396)] with targets 0.95 and 0.99, and for an empty list.
For 50 test questions with k = 5, and for 1,000 questions with k = 10, print how many neighbours the benchmark checks and how much one miss moves the recall (4 decimals).
Trade-offs
- ↔
A bigger benchmark: more trustworthy numbers, with more compute for ground truth and for each rerun.
- ↔
A higher recall target: closer to exact, and disproportionately more work for the last points.
- ↔
Counted comparisons versus timings: counts are portable and repeatable, timings are what users feel.
Done when you can
Done when you can list the ingredients of a trustworthy benchmark.
Done when you can sweep one knob and pick the cheapest setting that meets a recall target.
Done when you can explain why indexes are compared at equal recall.
Done when you can say how many questions you need to see a difference of a given size.