What is the neighbor-selection heuristic?

The neighbor-selection heuristic is the specific algorithm HNSW uses to decide which candidates a node should actually keep as connections, out of a larger pool of nearby options found during construction — the concrete procedure that turns the general principle of diversified neighbor selection into an actual, repeatable rule a construction process can apply consistently across every insertion. Understanding exactly how this heuristic makes its decisions, one candidate at a time, clarifies precisely why HNSW‘s graph ends up better connected than a naive closest-candidates approach would produce, using the same limited connectivity budget.

What does the heuristic’s basic decision-making process actually look like?

The heuristic works through its pool of candidates roughly in order of increasing distance from the node being connected, tentatively building up a final selection one candidate at a time. For each candidate under consideration, it checks that candidate’s distance not just to the node itself, but also to every neighbor already tentatively accepted into the final selection so far. If the candidate turns out to be closer to the node being connected than it is to every already-accepted neighbor, it gets kept, since this means the candidate genuinely offers something new — a direction or region of the space not already well covered by the connections already selected. If instead the candidate is closer to one of the already-accepted neighbors than it is to the node itself, it gets rejected as redundant, on the reasoning that the already-accepted neighbor is already positioned to serve roughly the same navigational role this candidate would have served, making the candidate’s inclusion largely wasted connectivity budget.

This process continues through the candidate pool, in order, until the final selection reaches its target size — M or Mmax0, depending on the layer — or the pool of remaining candidates runs out. The result is a final set of neighbors chosen not purely by distance, but by a combination of distance and how much each successive candidate genuinely adds beyond what’s already been selected.

Why does this specific closer-to-the-node-than-to-existing-neighbors test actually work as a diversity check?

The geometric intuition behind this test is that if a candidate point sits closer to an already-selected neighbor than to the node being connected, the candidate and that existing neighbor likely occupy roughly the same region of the surrounding space relative to the node — connecting to both would mean spending two units of connectivity budget covering essentially the same direction, when one connection could serve nearly the same navigational purpose. By contrast, if a candidate is closer to the node itself than to anything already selected, it’s sitting in a part of the space the current selection doesn’t yet reach, meaning it genuinely extends the node’s coverage into new territory rather than duplicating something already accounted for.

This test is applied fresh against the entire set of already-accepted neighbors for every new candidate considered, which means the heuristic’s notion of “redundant” adapts dynamically as the selection grows — a candidate that would have been accepted early on, before certain other neighbors were selected, might get rejected later in the same process once those other neighbors have already claimed the region it would have covered, and vice versa.

How does this heuristic connect to the broader idea of an extended candidate set, and why does that connection matter?

The heuristic’s ability to make good diversity-aware decisions depends directly on how rich a pool of candidates it actually gets to choose from in the first place — a heuristic applied to a narrow, thin candidate pool has fewer options to work with when trying to find genuinely diverse connections, regardless of how well the selection logic itself is designed. This is exactly why efConstruction matters so much: a larger efConstruction feeds the heuristic a wider candidate pool during construction, giving it more raw material to actually exercise this diversity-preferring logic on, which is part of why increasing efConstruction tends to improve the finished graph‘s overall quality even though efConstruction itself doesn’t directly change how the selection logic works. Some implementations go further still, deliberately extending the candidate pool beyond what a plain search would find, through a technique covered on its own extended-candidate-set glossary page, specifically to give this heuristic an even richer set of options to choose diverse connections from.

Having covered exactly how the neighbor-selection heuristic decides which candidates to keep, the diversified-neighbor-selection and simple-neighbor-selection glossary pages are worth revisiting together with this fuller mechanical picture, since together they cover the principle this heuristic implements and the naive alternative it deliberately improves upon. From there, the extended-candidate-set glossary page looks at how construction feeds this heuristic an even richer pool of options than a plain, unmodified search would find on its own.