Why does HNSW’s neighbor-selection heuristic matter more than raw distance?

HNSW’s neighbor-selection heuristic matters more than raw distance because connecting a new vector to its literal closest neighbors, while intuitive, tends to produce a graph that’s easy to build but bad at answering queries that fall outside whatever small cluster those closest neighbors happen to belong to — the heuristic exists specifically to avoid that failure mode by spending part of a vector’s limited connection budget on diversity rather than pure proximity.

What goes wrong if a new vector simply connects to its closest neighbors?

Picture two dense clusters of vectors sitting some distance apart, with only a thin scattering of points in between. If every vector simply connects to whichever other vectors are nearest to it, a vector deep inside one cluster will end up surrounded entirely by other members of that same cluster — its closest neighbors truly are all nearby, and none of them happen to point toward the other cluster at all. A search that starts inside this cluster and is actually looking for something in the other cluster has no edge to follow that leads in the right direction; it can wander among the closest neighbors as much as it likes without ever discovering that a better answer exists somewhere else entirely. This isn’t a rare edge case — real embeddings frequently form exactly this kind of clustered structure, since vectors representing similar concepts tend to sit near each other and distinct concepts tend to sit far apart.

How does favoring diverse directions fix the disconnection problem?

The heuristic addresses this by changing what counts as a “good” neighbor during selection. Rather than simply keeping the closest handful of candidates, it favors a set of neighbors that are spread across different directions relative to the vector being connected, even when that means keeping a slightly farther candidate over a slightly closer one that points in nearly the same direction as a neighbor already selected. In the two-cluster example above, this means a vector near the boundary between clusters is more likely to keep a connection reaching into the neighboring cluster, rather than filling its entire connection budget with redundant nearby points that all say roughly the same thing about where to go next. That one bridging connection is often all a search needs to discover that a better answer exists on the other side, even though most of its other connections stay local and short-range as usual.

How does this heuristic relate to the relative neighborhood graph idea from earlier?

This diversity-favoring selection is closely related to the relative neighborhood graph concept introduced when discussing proximity graphs more generally: a relative neighborhood graph keeps an edge between two points only when no third point sits closer to both of them than they are to each other, which has the effect of preserving exactly the kind of long-range structural edges that keep a graph connected across clusters, while dropping the redundant short-range edges a naive nearest-neighbor approach accumulates. HNSW’s neighbor-selection heuristic can be understood as a practical, efficiently computable approximation of that same underlying goal — it doesn’t reconstruct an exact relative neighborhood graph, which would be too expensive to compute during ordinary insertion, but it pursues the same property of preserving connectivity and navigability rather than simply preserving proximity.

Where does this idea’s history actually come from?

The idea of pruning a candidate neighbor set for diversity rather than pure closeness has a longer history than HNSW itself. Closely related pruning rules appear in earlier work on spatial approximation trees from the early 1990s, including a 1993 paper by Sunil Arya and David Mount, discovered only after HNSW’s own construction was published — a reminder that this particular solution tends to get independently rediscovered because it’s close to the only reasonable answer once the underlying problem, keeping a graph both compact and navigable, is properly understood.

With both search and construction now covered in detail, the next page turns to a question those mechanics only partially answer: what can actually be proven about how HNSW’s performance scales, and where does the commonly repeated claim of logarithmic search time hold up under scrutiny versus where it doesn’t. Readers interested in the formal underpinnings of relative neighborhood graphs themselves, rather than HNSW’s practical approximation of the idea, will find that covered on its own dedicated page in this site’s graph-theory glossary section.