Why do recall and query difficulty vary so much from query to query?

Recall and query difficulty vary so much from query to query because a single exploration-width setting has to serve every query the same way, while the actual difficulty of finding a given query’s true nearest neighbors depends on where that query happens to land relative to the graph’s structure — some queries sit in easy, well-connected regions where a narrow search finds the right answer immediately, and others sit in harder regions where the same narrow search comes up short.

What does recall actually measure, precisely?

Recall compares what a search actually returned against what the true, exact nearest neighbors would have been, expressed as the fraction of the true neighbors that were successfully found. A recall of 0.9 for a top-10 search means that, on average, 9 of the 10 true nearest neighbors were returned and one was missed. This number is normally computed by running an exact brute-force search once to establish ground truth, then comparing the approximate search’s output against it — recall isn’t something that can be measured from a single query in isolation, since it requires knowing what the correct answer actually was.

What specific failure modes cause a query to miss its true nearest neighbors?

Several distinct things can go wrong during a single search. A local minimum, where every neighbor of the current best candidate happens to be farther from the query than the candidate itself, can end a search prematurely if the exploration width isn’t wide enough to look past it and find a better path. A missing bridge — a case where the graph simply lacks a good connection between the region the search enters and the region the true answer actually lives in — can leave an answer unreachable no matter how much exploration is applied within the wrong neighborhood. A poor entry region, where the upper-layer descent happens to land somewhere unhelpful for this particular query even though it works well for most others, can put the base-layer search at a disadvantage before it even begins. And simple under-exploration, an exploration width too narrow for what a particular query needs, can miss neighbors that a wider search would have found without any of the above problems being present at all.

Why do some queries need far more exploration than others?

The underlying data’s local density and intrinsic dimensionality drive most of this variation. A query landing in a sparse, spread-out region of the vector space tends to have a small number of genuinely close candidates that are relatively easy to identify with a modest search. A query landing in a dense, crowded region — surrounded by many other vectors that are all roughly equally close to it — faces a much harder discrimination problem, since telling the true top few neighbors apart from many nearly-as-close alternatives requires examining a larger pool of candidates before settling on an answer with any confidence. Because a fixed exploration width is set once for an entire workload rather than per query, it inevitably ends up doing more work than necessary on the easy queries and less work than would help on the hard ones, unless it’s set conservatively wide enough to handle the hardest queries a workload is expected to produce — which then wastes effort on every easier query along the way.

Is there a way around having to pick one fixed exploration width for every query?

This mismatch between a single global setting and per-query difficulty is an active area of research rather than a fully solved problem. Query-adaptive exploration approaches try to estimate how much search effort a specific query actually needs and adjust the exploration width accordingly, rather than applying the same fixed value to every request regardless of difficulty. A related and even newer direction is accuracy certification, which tries to give some formal confidence about whether a particular search actually found the true nearest neighbors rather than relying purely on recall measured across a large batch of queries after the fact — worth being aware of as an emerging idea, though not yet something in wide practical use the way fixed exploration-width tuning is.

This closes out the algorithms-and-theory material with a clear picture of what HNSW actually does and why — the next part of this site shifts from theory to practice, starting with what a minimal, correct implementation of everything described so far actually looks like in code. Readers specifically weighing how wide to set their own exploration width in light of the difficulty variation described here should move next to the tuning-and-optimization section, which turns this into concrete, actionable guidance.