Why it matters
Exact nearest-neighbour search compares the query against every vector, which is linear in corpus size and quickly dominates request latency. ANN indexes prune the search space using a graph or a partition, so a query touches a small fraction of the vectors. The pruning is probabilistic: the correct neighbour can be skipped, and the parameters that control how hard the search tries are the difference between a fast wrong answer and a slower right one.
Mental model
ANN search is looking for a house by asking neighbours instead of driving every street: you start somewhere plausible and follow local directions. The metaphor breaks when the target sits in a cul-de-sac the walk never enters — the search returns confidently, just without the house.
How it works
The interactive figure loads with JavaScript. The text version below describes the same frame.
Figure. Twelve synthetic points, each tagged with the search effort at which a synthetic graph walk first reaches it. The slider sets ef_search; the rank panel lists what is returned at that effort and which exact neighbours were never reached.
What to notice. At ef_search = 3 the walk reaches five points: the three nearest true neighbours plus two weaker points, so recall is 3 of 5 and two returned passages are not neighbours at all. Raise the effort to 9 and the exact five are returned, with the two weak points still reachable but no longer in the top five. The effort order is hand-built to show the trade-off; a real index does not expose it this cleanly.
Text version
A scatter of twelve synthetic points with a query. At the default ef_search of 3, the true neighbours n1, n2 and n3 are ringed and joined to the query in teal with solid edges, two non-neighbour points x1 and x2 are joined with dashed warning edges, and the rank panel marks the returned set as three hits and two non-neighbours. The two remaining true neighbours, n5 reached at effort 6 and n4 reached at 9, are shown with dashed rings and marked missed with their reaching effort. Raising the slider to 9 returns n1, n2, n3, n5 and n4 and reaches full recall.
- Establish an exact-search baseline on a sample of queries so recall has a denominator.
- Choose the index family for the corpus size and memory budget, then build it with parameters that fit the build window.
- Set query-time effort, whether ef_search, nprobe or an equivalent, from a measured recall-latency curve rather than a default.
- Measure recall@k against the exact baseline at the k used in production, with the same filters applied.
- Over-fetch when filters are present, then verify the returned count still reaches k after filtering.
- Re-measure after bulk inserts, deletes or a rebuild, since graph quality and partitions change.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| High query-time effort | Recall close to exact | Higher latency per query and more CPU | Traffic is bursty and the latency budget is fixed |
| Low effort | Fast responses and high throughput | Misses true neighbours, hurting answer quality | Queries depend on rare terms or exact entities |
| Over-fetch then filter | Recovers k results under selective filters | More candidates scored and ranked | Filters are extremely selective |
| Exact search on a sample | Ground truth for recall | Too slow for production queries | The corpus is large enough to need ANN in the first place |
Good for
Recall close to exact
Cost
Higher latency per query and more CPU
Fails when
Traffic is bursty and the latency budget is fixed
- Traffic is bursty and the latency budget is fixed
- Queries depend on rare terms or exact entities
- Filters are extremely selective
- The corpus is large enough to need ANN in the first place
Figure. Each choice with what it buys, what it costs, and the case where it loses.
What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.
Text version
Four trade-offs: High query-time effort is good for Recall close to exact, costs Higher latency per query and more CPU, and fails when Traffic is bursty and the latency budget is fixed. Low effort is good for Fast responses and high throughput, costs Misses true neighbours, hurting answer quality, and fails when Queries depend on rare terms or exact entities. Over-fetch then filter is good for Recovers k results under selective filters, costs More candidates scored and ranked, and fails when Filters are extremely selective. Exact search on a sample is good for Ground truth for recall, costs Too slow for production queries, and fails when The corpus is large enough to need ANN in the first place
Failure modes
- Recall never measured. Latency looks healthy while the correct passage is silently skipped. Debug: run the same queries with exact search and compute the overlap at k.
- Filtered search returns too few. A tenant filter removes most candidates after the graph walk, so the response has two results instead of ten. Debug: log the pre-filter and post-filter candidate counts per query.
- Index degraded by churn. Frequent updates leave a graph with poor connectivity and recall falls over time. Debug: track recall against the exact baseline weekly and correlate with delete volume.
In production
Keep a nightly job that measures recall@k against exact search on a query sample, and alert when it drops. Cap over-fetch and query-time effort so a single expensive query cannot consume the latency budget.
Common misconceptions
People think: Approximate search is close enough for any use.
Actually: The error is query-dependent; a rare entity or a selective filter is exactly where the approximation fails.
People think: Lower latency means a better index.
Actually: Lower latency usually means less search effort, which trades directly against recall.
Interview angle
Separate build-time structure from query-time effort, and insist on measuring recall against exact search. Explain the filtered-search trap and how over-fetch interacts with it. Quoting a latency figure without the recall it was achieved at is the answer that should worry an interviewer.
Sources
- Malkov & Yashunin, HNSW — the graph index and the effort parameter that controls recall.
- Johnson, Douze & Jégou, Billion-scale similarity search with GPUs — the FAISS index families and their accuracy-speed trade-offs.
- pgvector — query-time recall settings and filtering behaviour in a database extension.