Tuning HNSW for recall vs latency

What's really being asked

This evaluates whether you understand that approximate nearest neighbor search trades accuracy for speed, and can intelligently tune HNSW parameters against an application's latency and recall budget.

The core trade-off

Exact nearest neighbor search over millions of high-dimensional vectors is too slow because it must compare against every vector. ANN indexes accept a small chance of missing the true nearest neighbors, measured as recall, in exchange for sublinear query time. So the fundamental dial is recall versus latency: more thorough search raises recall but costs time, and you cannot have maximal recall and minimal latency at once.

Hnsw parameters

HNSW builds a multi-layer navigable small-world graph. M controls how many neighbor links each node keeps; higher M produces a richer graph with better recall and faster convergence but uses more memory and slows index building. efConstruction sets how many candidates are explored when inserting each node at build time; higher values build a higher-quality graph improving achievable recall, again at the cost of longer build time. efSearch, the key runtime parameter, sets the size of the dynamic candidate list during a query; raising it explores more of the graph, increasing recall but directly increasing query latency.

How to tune

Fix M and efConstruction at build time to set the quality ceiling and memory footprint, larger for high-recall needs. Then, at query time, choose efSearch by sweeping it and measuring the recall-latency curve on a representative dataset, picking the smallest efSearch that meets your recall target within your latency budget. For a latency-critical feature, accept lower efSearch and recall; for an accuracy-critical batch job, raise efSearch.

What usually comes next

How do you measure recall. Why does higher M cost memory. How does IVF or product quantization compare. How do filters interact with HNSW.

A concrete example

For an interactive image-similarity feature with a 50 ms budget, you build with moderate M and efConstruction, then sweep efSearch: efSearch 64 gives 95 percent recall at 20 ms, efSearch 256 gives 99 percent at 70 ms. You pick efSearch around 100 for about 97 percent recall within budget.