How does HNSW search a graph, step by step?

Searching an HNSW graph means descending through its layers one at a time, starting with a fast, low-effort walk through the sparse upper layers and finishing with a more thorough, wider search once the query reaches the dense base layer — the same overall shape described elsewhere on this site, but worth tracing through in the actual mechanical detail of what the algorithm is tracking and deciding at each step.

What happens during the upper-layer descent, before the real search begins?

The search starts at the graph’s single designated entry point, sitting at the topmost occupied layer, and performs a plain greedy walk: look at the current node’s neighbors in this layer, move to whichever one is closest to the query, and repeat until no neighbor is closer than the node currently standing on. Because the upper layers are sparse, this greedy walk converges quickly, usually after only a handful of hops, and it only ever needs to track a single current-best node rather than a wider pool of candidates — there’s no need for more caution here, since the point of the upper layers is only to get roughly to the right neighborhood, not to find the precise answer. Once the walk stalls, meaning no neighbor in the current layer is closer than the current position, the algorithm drops down to the next layer, carrying that same best-known node forward as the starting point for the layer below.

What is actually being tracked while the algorithm searches a single layer?

Underneath the greedy walk described above sits a slightly more general search procedure, one that gets used at every layer but only really shows its full behavior once the search reaches the base layer. It maintains two things at once: a set of candidates still worth exploring, ordered so the most promising one can always be examined next, and a running set of the best results found so far, capped at a fixed size. A visited set sits alongside both, recording which nodes have already been examined during this particular search so the algorithm never wastes work re-examining the same node twice — necessary because the graph contains cycles, and without this bookkeeping a search could loop back over ground it’s already covered.

When does the search decide to stop exploring at a given layer?

The search keeps pulling the most promising unexplored candidate off its candidate list, examining that candidate’s neighbors, and adding any sufficiently close ones to both the candidate list and the results list. It stops once the closest remaining unexplored candidate is no longer closer than the worst result currently being kept — at that point, continuing to explore can’t possibly improve the answer, since nothing left to look at could beat what’s already been found. This stopping condition is what keeps the algorithm from wastefully exploring a graph that could otherwise be arbitrarily large.

Why does the base layer get a wider search than every layer above it?

At the upper layers, the results list effectively holds only one node, matching the plain greedy behavior described earlier — good enough for coarse navigation, where the goal is simply reaching the right neighborhood before descending further. At the base layer, holding all of the dataset’s vectors and representing the algorithm’s last chance to get the answer right, the results list is widened to hold a configurable number of candidates rather than just one. This wider candidate pool is what lets the search recover from an unlucky path instead of settling for the first local optimum it happens to stumble into, and how wide that pool is set directly controls the trade-off between how thorough the base-layer search is and how much it costs to run — a single adjustable dial that can be tuned per query without touching the graph itself.

How does the algorithm turn a pool of candidates into the final top-k answer?

Once the base-layer search has stopped, its results list generally holds more candidates than the number of neighbors actually requested, since a wider exploration produces a wider set of good options along the way. The final step simply sorts that results list by distance to the query and returns the closest ones, trimmed down to exactly the requested count. The gap between how wide the exploration was and how many results were ultimately asked for is itself informative: a search run with a much wider candidate pool than requested results tends to be noticeably more accurate, precisely because it had more genuine alternatives to choose the final answer from.

The next page walks through the mirror-image process — how a new vector gets inserted into a graph that already exists, which turns out to rely on this same search procedure as one of its core building blocks. For a closer look at exactly how the exploration-width parameter mentioned above should be chosen in practice, the tuning-and-optimization section of this site works through concrete guidance rather than the conceptual description given here.