A vector database ships one knob for how hard to look. It fixes neither the bill nor the recall.
Run it: https://dev48.infy.uk/ai/days/day77-ann-recall.html
Nothing here simulates language. The engine simulates the partition — documents in cells, a query that opens some of them, and brute force standing next to it the whole way as the only ground truth on the page. 1,600 documents, 16 dimensions, 48 cells holding between 1 and 93 documents each, 320 queries. Cost is counted in distance computations, centroids included.
The setting a team ships
Opening 3 cells returns 0.9456 of the true neighbours; opening 4 returns 0.9725. So nprobe = 4 goes in the config.
nprobe is a count of cells, and a cell is not a unit of work.
| at nprobe = 4 | |
|---|---|
| cost | 113 → 325 distance computations depending on the query |
| recall | 50.00% → 100.00% depending on the query |
| bottom tenth of queries | 90.00% recall or below |
A capacity plan built on the mean cost is wrong for 47.8% of traffic. Neither spread is noise — the index is deterministic and every query is answered the same way twice.
The money goes to the wrong queries
Sort the 320 queries by what they cost and cut into halves:
| spend | misses | |
|---|---|---|
| cheaper half | 167.0 | 5.19% of true neighbours |
| dearer half | 234.4 | 0.31% |
1.40× the spend on the half that was already right, and a 16.60× miss rate on the half that was not. The correlation between what a query costs and how well it is answered is +0.479 — positive, which is the wrong sign.
Nobody chose this. k-means cuts a tight region finely, so the query whose ten neighbours are scattered across many small cells is exactly the query for which "4 cells" is the least work.
The fix is one word, and it is not a trade
Same index, same probe order — stop after a fixed number of documents instead of a fixed number of cells, cutting mid-cell if that is where the budget falls:
| policy | mean cost | worst | recall | misses / 1k |
|---|---|---|---|---|
| 4 cells | 200.7 | 325 | 0.9725 | 27.50 |
| 153 documents | 201.0 | 201 | 0.9919 | 8.12 |
Matched to within 0.3 computations out of 200.7. Misses fall 3.38× and the worst-case bill falls at the same time, because a document budget is a constant and a cell budget is not. Both axes improve — the cell count was simply spending the money in the wrong place.
Repeated at every cell setting worth shipping: 6 of 6 matched bills favour the document budget, and the gap widens exactly where a team would ship.
And the exact rule has a tail
Stop when the cell's centroid distance minus its radius clears the k-th best hit in hand, and no unopened cell can hold a better neighbour. Exact on 100.00% of queries — checked as an identity against brute force, list against list.
It costs 31.1% of a full scan on average, and its worst case is 1,447 — 90.4% of just scanning everything.
🔴 The version without the radius — stop when the next centroid is further than the k-th hit — is exact on 13.75% of queries and returns 74.75% of true neighbours. It looks like the same idea and is not a bound at all: a centroid can be far while a member of its cell is close. It is 4.37× cheaper, which is why it is the version that gets written, and the failure is silent — results come back, ranked, looking exactly like results.
Verifier 982 asserts, page self-check 327, 0 failures.
Top comments (0)