Approximate search is a dial, not a fixed thing: every index trades accuracy against speed.
Recall here means the share of the true nearest neighbours the index actually returned.
Pushing recall from ninety to ninety-nine per cent often costs several times the query time.
The right point depends on the application, since a reranker can repair a slightly imperfect list.
Measure it against a brute-force ground truth on a sample, because untested settings are guesses.
Exact nearest-neighbour search is easy and slow: compare the query with everything and sort.
Every practical index is approximate, and approximate means some true neighbours will be missed.
Recall at k is the measure: of the k genuine nearest neighbours, how many did the index return.
Ninety-five per cent recall at ten means that on average half a real result was lost per query.
Whether that matters depends entirely on what happens next.
Every index exposes parameters that move along this curve rather than escaping it.
In HNSW the search breadth controls how many candidates are kept while walking the graph.
In IVF it is the number of clusters probed, and in quantized indexes it is the candidate list size.
The curve is steep at the top: the last few points of recall are disproportionately expensive.
Going from ninety to ninety-nine per cent can multiply query time several times over.
The mistake is to pick a target in the abstract instead of from the application.
In a RAG pipeline a reranker reads far more candidates than the model will see, so moderate recall is fine.
In deduplication or entity matching a missed neighbour is a wrong answer, so high recall is worth paying for.
The only honest way to choose is to build a ground truth by brute force over a sample of queries.
Then plot recall against latency for a few parameter settings and pick a point deliberately.
Recall is measured against what a brute-force scan would have returned, so it needs a ground truth computed exactly, once, on a sample of queries.
Report queries per second at recall 0.9, 0.95 and 0.99.
Every approximate index has a dial, and turning it trades one for the other. The only honest way to compare two indexes is at equal recall.
A benchmark reporting queries per second without a recall number is reporting nothing, since any index can be made arbitrarily fast by returning worse answers.
Going from 0.80 to 0.90 is cheap. From 0.95 to 0.99 often costs three or four times the work, because the last few results are the boundary cases the structure was designed to skip.
Those are the dials, one per family, and they are query-time parameters rather than build-time ones, so the trade can be set per request.
A search that allows a longer tail for some queries and not others is therefore possible, and it is how a system serves an interactive path and a batch path from one index.
A document missed by the index cannot be recovered by anything downstream, so retrieval recall is a ceiling on the whole pipeline.
Reranking fixes order, not absence.
That is why the usual configuration retrieves many candidates at moderate recall and spends the saved time on reranking, rather than retrieving few candidates at very high recall.
Ninety of the true top hundred is a better input to a reranker than ten near-perfect ones, for the same latency budget.
Report percentiles rather than an average. Approximate search has a long tail, since some queries land in dense regions and visit far more nodes than the median.
Better recall at the same latency is not won by tuning. It comes from a better index structure, a better embedding, or fewer vectors to search.
Metadata filtering is the largest available win when it applies, because searching a tenth of the corpus moves the curve rather than sliding along it.
Quantisation moves it too, in a way that looks wrong at first: the vectors are less accurate, more of them fit in cache, and the net effect at fixed latency is usually higher recall.
One question on this card. Every option explains itself once you pick, right or wrong.
17 concepts in this module, then a graded test with every answer explained.