Tuning the recall versus latency knobs of approximate nearest neighbor search

Short answer·Hard·4.0 · 0·~3 min·Asked atCerebras Krutrim Servicenow

Attempt it

ANN search is approximate, so it can miss true neighbors. Which parameters trade recall against latency, and how would you tune them rather than guessing?

Free · 2 AI evals / day

Exact nearest-neighbor search compares your query against every vector in the index. That is correct but slow once you have millions of chunks. **Approximate nearest-neighbor** (ANN) search is fast because it only looks at part of the index. That is also why it can miss the true closest neighbor. The knobs that control this all answer one question: how much of the index is explored before answering? For HNSW, `ef_search` sets how many candidates the graph keeps in its frontier at query time. M sets how connected the graph is at build time. For IVF, `nprobe` sets how many clusters get scanned. Turn any of these up and you explore more, so recall rises but latency rises too. Turn them down and queries get faster but skip more true neighbors. The right way to set them is to measure, not guess. Build an evaluation set where you know the correct neighbors for each query, sweep the parameter, and record recall@k at each value. Pick the smallest value that still hits your recall target, because that gives the lowest latency for the accuracy you need. Throughout, watch p95 and p99 latency so a recall gain never breaks your SLA.

Approximate nearest-neighbor search gains speed by exploring only a slice of the index. So every recall versus latency knob controls the size of that slice. For **HNSW**, the dominant query-time dial is `ef_search`: the width of the candidate frontier the greedy graph traversal maintains. The build-time dial `M` (neighbors per node) sets how navigable the graph is and bounds how high `ef_search` can usefully go. For **IVF** indexes, `nprobe` decides how many coarse clusters you scan. The direction is consistent: higher values explore more candidates, lifting recall@k but adding latency and CPU. Lower values are faster but more likely to drop the true nearest neighbor. There is no universal best value. It depends on corpus size, embedding distribution, and your query mix. That is why you tune empirically. First build a labeled set with ground-truth neighbors, computed by brute-force exact search over a representative query sample. Then sweep the knob across a range and plot recall@k against measured p95/p99 latency. The operating point is the smallest knob value that clears your recall target, because that minimizes latency at the accuracy you require. The latency budget is a hard constraint, not a suggestion. A configuration that hits recall but breaks the p99 SLA is rejected. The biggest pitfall is tuning on a tiny or unrepresentative query set. The next is stopping at "recall looks fine" with no number. The correct operating point shifts with the real query distribution and corpus growth, so re-tune as the index scales.

TL;DR

ANN trades exactness for speed via knobs like HNSW ef_search and IVF nprobe. Tune them by sweeping against a measured recall@k target under a latency budget, never by intuition.

Memory aid

Easy to grasp

Imagine looking for the closest coffee shop on a map. Checking every shop in the city is exact but slow. Instead you only check the few blocks around you. That is fast, but you might miss a great place one street over. The knob is how many blocks you bother to check. Check more blocks and you almost never miss the best shop, but it takes longer. Check fewer and you answer instantly but sometimes settle for second-best. Approximate nearest-neighbor search works the same way: a dial decides how much of the index it scans before answering. The smart move is not to guess the dial. You make a list where you already know the true best shops. Then you turn the dial up bit by bit until your search finds them often enough. You stop there so it stays fast.

Key concepts

Vector Databases Retrieval-Augmented Generation Embeddings

Concept explanation~2 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Every production RAG system above a few hundred thousand vectors runs approximate nearest-neighbor search. Each one makes a recall versus latency trade-off without anyone noticing. The trade-off stays invisible until a user complains that the assistant missed an obvious document, or until the p99 latency graph rises past the SLA during a traffic spike. Both symptoms trace back to the same set of index parameters, set once at launch and rarely revisited.

The vector index is not a black box. It is a tunable system with a measurable operating point. Two things matter: knowing which specific knobs move the tradeoff, and having a disciplined, numbers-driven method for setting them. Guessing a value, or copying one from a blog post, is the failure mode.

Why approximate search misses neighbors in the first place

Exact nearest-neighbor search compares the query against every vector and returns the true top-k. It is correct by construction, but its cost grows linearly with corpus size. At tens of millions of vectors, a single query becomes too slow for an interactive system.

Approximate indexes break that linear cost by not looking at everything. An HNSW index builds a layered proximity graph and answers a query with a greedy walk: start at an entry point, hop to the neighbor closest to the query, repeat. The walk only ever touches a small fraction of nodes, which is the speedup and also the source of error. If the true nearest neighbor sits in a region the walk never enters, it is never considered.

An IVF index does something analogous with clustering. It partitions the vectors into clusters during build, and at query time it scans only the clusters whose centroids are closest to the query. A true neighbor that happens to land in a cluster you did not scan is invisible.

So the inaccuracy is not a bug. It is the mechanism. The knobs all control the same thing: how much of the index the query is allowed to touch before it must answer. More exploration recovers more of the true neighbors. Less exploration is faster but riskier.

The knobs: ef_search, M, and nprobe

The tuning loop: from guessing to measuring

The latency budget as a hard constraint

Why the operating point drifts and tuning recurs

Situations where this technique stops working.

2–4 min · Everything important, quickly.

Knob	Index family	When it applies	Turning it up
ef_search	HNSW	Query time, per request	Wider search frontier: more recall, more latency
M	HNSW	Build time, fixed at index creation	More connected graph: higher recall ceiling, more memory and build time
nprobe	IVF	Query time, per request	More clusters scanned: more recall, roughly linear latency

Real products, models, and research that use this idea.

Qdrant accepts hnsw_ef per search request, and Weaviate's ef is a collection setting you can change without rebuilding the index. Pinecone does not expose it
FAISS IVF indexes ship nprobe as the primary recall dial, and exact search with IndexFlat is the baseline FAISS uses to measure the recall of approximate indexes

What an interviewer would ask next. Try answering before peeking at the approach.

QHow do you construct ground-truth neighbors when you have no human relevance labels?

Run exact brute-force (flat) search over a representative sample of real production queries. The exact top-k for each query is the ground truth the ANN result is scored against. Sample the queries from logs so the distribution matches traffic, and refresh the sample when the corpus or query mix shifts.

2 more follow-ups an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases that signal junior thinking. Click to expand.

Most common mistake

Eyeballing a few queries, deciding recall 'looks fine', and shipping. Later, the team finds the operating point was tuned on a handful of unrepresentative questions that do not match real traffic.

60 second bullets to scan on the way to the call.

Why approximate search can miss the true nearest neighbor at all
What ef_search controls in HNSW versus what M controls

Primary sources. Browse if you want the original framing.