HNSW Approximate Nearest Neighbor Search: The Recall-Latency Trade-off, Benchmarked

By kongastral

Published September 22, 2026 · 15 min read

Exact nearest neighbor search compares a query vector against every stored vector and returns the true closest matches; approximate nearest neighbor search visits only a small, deliberately chosen subset of the data and returns matches that are almost always the same. The two answer the same question, but their cost can differ by more than an order of magnitude. This difference is what makes semantic search, recommendation, and retrieval-augmented generation practical once a collection grows past a few hundred thousand vectors. The measurements below, produced on a single workstation, quantify exactly what is traded away when exact search is replaced by the Hierarchical Navigable Small World (HNSW) graph, and how a single parameter moves the result along a smooth recall-against-speed curve.

Exact search and why it stops scaling

A nearest neighbor query takes a single query vector and returns the k stored vectors closest to it under some distance, here the squared Euclidean (L2) distance. The exact answer is defined by brute force: compute the distance from the query to every stored vector, then keep the smallest k. This is correct by construction and simple to implement with a single matrix operation, but its work grows linearly with the number of stored vectors and with their dimensionality. Doubling the collection doubles the query time.

For a few thousand vectors that linear cost is invisible. For the tens or hundreds of millions of embeddings that a production retrieval system holds, scanning the whole collection for every query becomes the dominant expense. The standard response is to accept a small, controllable error: return neighbors that are correct almost all of the time, in exchange for touching only a fraction of the data. The quality of that approximation is measured by recall@k, the fraction of the true k nearest neighbors that the approximate method actually returns, averaged over many queries. A recall of 1.0 means the approximate answer is identical to the exact answer; a recall of 0.90 means that, on average, nine of every ten true neighbors were found.

How HNSW searches a graph

HNSW, introduced by Malkov and Yashunin in 2016 and published in IEEE Transactions on Pattern Analysis and Machine Intelligence in 2020, is a graph-based index. Every stored vector becomes a node, and each node is connected to a bounded number of nearby nodes. A query is answered by greedy graph traversal: start at an entry node, look at its neighbors, move to whichever neighbor is closest to the query, and repeat until no neighbor is closer. Because edges connect points that are already near one another, this walk converges quickly toward the query’s neighborhood without inspecting the rest of the collection.

The “hierarchical” part adds several layers. Upper layers contain a sparse random sample of the points connected by long-range links; the bottom layer contains every point. A search descends from the top, using the coarse upper layers to jump across the space in a few large steps, then refines within the dense bottom layer. The structure resembles a skip list generalized to a graph.

Three parameters govern the structure and the search. M is the maximum number of bidirectional links each node keeps per layer, the graph’s degree; a higher M builds a richer graph that reaches more candidates per step. ef_construction is the size of the candidate list explored while inserting each new point during index construction; a larger value produces a higher-quality graph at the cost of a slower build. ef, also called efSearch, is the size of the candidate list kept during a query; it must be at least k, and raising it makes the traversal examine more of the graph before stopping. Of the three, ef is the one adjusted at query time, and it is the primary knob that trades recall against latency without rebuilding the index.

The benchmark setup

The measurements use hnswlib, the reference implementation written by the algorithm’s authors. The data is a seeded synthetic set: 100,000 base vectors and 1,000 query vectors of dimension 96, drawn from a mixture of 200 Gaussian clusters so that genuine neighborhood structure exists. The distance is squared L2, and every query asks for its ten nearest neighbors. Exact ground truth for all 1,000 queries is computed by brute force with a single matrix operation, and each approximate result is scored against it. The full script, its raw output, and the results file are published in the companion repository listed under References. The run is reproduced with one command:

uv run --with numpy --with hnswlib \
  python _workspace/bench/ann_hnsw/bench.py

The environment recorded by the script was an arm64 machine running Python 3.11.14, numpy 2.4.6, and hnswlib 0.8.0, with a fixed random seed of 20260921. A short excerpt of the console output shows the exact baseline and the first rows of the effort sweep:

brute force: 1.424 ms/query  (702 QPS)
building HNSW (M=16, ef_construction=200) ...
build time: 2.28s
  ef=  10  recall@10=0.7789  0.0328 ms/q  30,518 QPS  44x
  ef=  16  recall@10=0.8788  0.0411 ms/q  24,314 QPS  35x
  ef=  32  recall@10=0.9677  0.0557 ms/q  17,946 QPS  26x
  ef=  64  recall@10=0.9963  0.0743 ms/q  13,456 QPS  19x
  ef= 128  recall@10=0.9988  0.1000 ms/q   9,996 QPS  14x
  ef= 256  recall@10=0.9998  0.1284 ms/q   7,791 QPS  11x

Building the index took 2.28 seconds, a one-time cost paid before any query. That construction expense is the price of the graph; it is amortized across every subsequent search, which is why graph indexes suit collections queried far more often than they are rebuilt.

Recall against search effort

The clearest single result is how recall responds to ef. As the candidate list grows from 10 to 256, recall@10 climbs from 0.7789 to 0.9998, and the gain is steeply diminishing. Moving from ef=10 to ef=32 recovers most of the missing neighbors, lifting recall from about 78 percent to about 97 percent; the further climb from 0.9963 at ef=64 to 0.9998 at ef=256 buys only a few tenths of a percent for a fourfold increase in effort.

Every increment in ef also lengthens the query. Mean latency rose monotonically from 0.0328 milliseconds at ef=10 to 0.1284 milliseconds at ef=256, a factor of 3.9 across the sweep. Latency and recall move together because both are driven by how much of the graph the traversal visits: a larger candidate list examines more nodes, which finds more true neighbors and costs more time. The relationship is close to linear in ef, in contrast to the sharply concave recall curve, which is why the last few points of recall are so expensive.

The recall–throughput frontier

Plotting throughput against recall exposes the frontier a system actually operates on. Each point is one setting of ef; the exact brute-force baseline sits at recall 1.0 and 702 queries per second. The HNSW settings form a curve far above the baseline in throughput: at recall 0.968 the index sustained about 17,900 queries per second, roughly 26 times the exact scan, and even at recall 0.9998 it held about 7,800 queries per second, about 11 times faster. The curve bends sharply near the top, the visual signature of the recall saturation seen in Figure 2. A practitioner chooses an operating point on this frontier rather than a single “best” value.

Graph degree: the M parameter

The ef sweep holds the graph fixed and varies only the query. The other lever is the graph itself. Rebuilding the index with different values of M, the number of links per node, and querying each at a fixed ef=64 shows that a denser graph reaches higher recall for the same search effort. Recall@10 rose from 0.9685 at M=8 to 0.9943 at M=16, 0.9986 at M=32, and 0.9996 at M=48. Throughput fell gently over the same range, from about 15,000 to about 11,100 queries per second, because each traversal step in a denser graph inspects more neighbors. Build time changed little, from 2.13 to 2.45 seconds, and index memory grows with M as well.

M and ef are complementary. A larger M lifts the whole recall-against-effort curve and is chosen once, at build time, subject to a memory budget; ef then selects an operating point on that curve at query time and can differ per request. A common pattern is to fix a moderate M, such as 16 or 32, and tune ef to the recall a given application needs.

Reading the trade-off in practice

The practical procedure is to decide how much error the downstream task tolerates. A retrieval-augmented generation pipeline that feeds a language model many candidates can often accept recall around 0.95, because a missed neighbor is frequently redundant with a retrieved one; a system that must not miss a specific match needs recall much closer to 1.0. Once that target is set, the smallest ef that reaches it on representative data is the efficient choice, and everything beyond it spends latency for accuracy the task will not notice. This is why an approximate index is reported as a curve rather than a single number, and why quality is stated as recall at a chosen operating point.

The evaluation method matters as much as the index. Recall is meaningful only against exact ground truth, so a benchmark computes the true neighbors by brute force on a held-out query set, then scores the approximate results. The convention of plotting recall against queries per second, popularized by the ANN-Benchmarks project, is the standard way to compare methods precisely because no single point captures an approximate index. The same discipline of building embeddings from a trained encoder, as covered in the discussion of self-supervised pretraining, applies here: the index is only as useful as the vectors fed into it.

Limitations of this measurement

These numbers describe one configuration and should not be read as universal. The collection is a single seeded set of 100,000 vectors of dimension 96 drawn from Gaussian clusters; real embedding sets differ in scale, dimensionality, and cluster structure, all of which shift the recall curve. Latency was measured one query at a time rather than in batches, and on a single machine, so absolute microsecond figures are hardware-specific. The distance was squared L2; cosine or inner-product spaces behave similarly in shape but not in exact values.

The most important caveat concerns the speed-up magnitude. At 100,000 vectors an exact scan is already fast, so the observed 11-to-44-fold advantage is modest. Because exact search grows linearly with collection size while HNSW query time grows only logarithmically, the same experiment at tens of millions of vectors would show the exact baseline slowing by orders of magnitude while the graph query changes little. The figures reported here therefore understate the advantage at production scale; the reliable, transferable finding is the shape of the curves, not the absolute multiplier. Techniques that reduce per-query work in other parts of a system, such as the draft-and-verify approach to language-model inference, address a different stage than retrieval, but the same accounting applies: measure the operating point, not a single headline number.

Conclusion

Approximate nearest neighbor search trades a small, measurable loss in recall for a large gain in throughput, and HNSW exposes that trade as two clean parameters. The query-time ef moves a fixed index along a steep recall curve, recovering most true neighbors cheaply and the last fraction of a percent only at rising cost; the build-time M raises the whole curve at the price of memory and a little speed. On the seeded 100,000-vector set measured here, HNSW matched exact search to within a fraction of a percent while running an order of magnitude faster, and every point on the frontier was reproducible from a single command with a fixed seed. The right way to use such an index is to fix the recall a task needs, find the least effort that reaches it on representative data, and treat the published curve, not any single number, as the specification. Related graph-structured methods for learning on connected data appear in the treatment of graph attention networks, and distance-based decision boundaries in the discussion of one-class deep anomaly detection.

Frequently asked questions

What is the difference between recall@k and accuracy in nearest neighbor search?

Recall@k is the fraction of the true k nearest neighbors that an approximate index returns, averaged over queries, measured against an exact brute-force ground truth. It is not classification accuracy; it specifically quantifies how faithfully the approximate result reproduces the exact neighbor set. A recall@10 of 0.99 means that, on average, 9.9 of the ten true neighbors were retrieved.

Which HNSW parameter should be tuned first?

Tune ef, the query-time candidate list, first, because it changes recall and latency without rebuilding the index. Set M, the graph degree, once at build time according to a memory budget; a moderate value such as 16 or 32 is a common starting point. Raise M only if the recall-against-effort curve is too low across all reasonable ef values.

Why was the measured speed-up only 11 to 44 times rather than thousands?

Exact search on 100,000 vectors is already fast, so the baseline is a low bar to clear. Exact scan cost grows linearly with collection size while graph query cost grows roughly logarithmically, so the advantage widens sharply at larger scales. The experiment reports the shape of the trade-off, which transfers; the absolute multiplier understates production-scale gains.

Can this benchmark be reproduced?

Yes. The dataset is generated from a fixed random seed, and the single command in the setup section runs the whole sweep with the pinned library versions recorded by the script. The script, its raw console log, and the results file are published in the companion repository listed in the references.

References

• Yu A. Malkov and D. A. Yashunin. “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4):824–836, April 2020. Preprint: arXiv:1603.09320 (2016).
• hnswlib — reference implementation and parameter guide (ALGO_PARAMS): github.com/nmslib/hnswlib. Retrieved 2026-09-21.
• Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. “ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms.” Information Systems 87 (2020). DOI: 10.1016/j.is.2019.02.006. Interactive results: ann-benchmarks.com.
• Benchmark script, raw log, and results for this post: github.com/jkc4416/analytics-bench (ann_hnsw study). Retrieved 2026-09-21.