How do proximity graphs support nearest-neighbor search without a hierarchy?

A proximity graph supports nearest-neighbor search by connecting each vector directly to a handful of others that are close to it, so that a query can move from one vector to a nearer one by following edges instead of measuring its distance to every vector in the dataset — no hierarchy is required for this idea to work at all, and the earliest versions of this approach were built as a single flat graph, which is worth understanding on its own before adding any layers on top.

What is a proximity graph, and how does a k-nearest-neighbor graph build one?

A proximity graph is any graph where an edge between two nodes signals that those two nodes are close to each other under whatever distance function is in use, rather than signaling some other kind of relationship. The most direct way to build one is a k-nearest-neighbor graph: for every vector in the dataset, connect it to its k closest other vectors. This produces exactly the kind of structure a greedy search needs — starting anywhere in the graph, a search can repeatedly move to whichever connected neighbor is closer to the query, gradually approaching the true answer without ever comparing against most of the dataset. The open question is how well this simple construction actually performs, and the answer depends heavily on which vectors end up connected to which.

Why is a Delaunay-style graph the theoretical ideal for greedy routing?

A Delaunay graph — built from the same geometric construction that defines a Voronoi diagram, where each region of space is assigned to whichever data point is closest to it — has a remarkable property: a greedy search that always moves to the nearest connected neighbor is mathematically guaranteed to reach the true nearest neighbor to any query, with no risk of getting stuck partway there. This makes it the theoretical gold standard for graph-based search. Unfortunately, building an exact Delaunay graph becomes computationally impractical as the number of dimensions grows, and worse, it isn’t even well-defined in the general case of an arbitrary distance function over data with no known global structure — a real system has no way to construct anything resembling a true Delaunay graph over high-dimensional embeddings. What practical algorithms do instead is aim for a graph that approximates some of the useful properties of a Delaunay graph without needing to construct one exactly, and a relative neighborhood graph is one well-studied way of getting closer to that goal: it keeps an edge between two points only when no third point sits closer to both of them than they are to each other, which tends to preserve exactly the kind of long-range structural edges a Delaunay graph would have while dropping the redundant short-range ones a naive nearest-neighbor graph accumulates.

What goes wrong when a flat proximity graph is searched with pure greedy routing?

Even a well-built proximity graph runs into a structural problem when searched too literally: greedy routing can reach a local minimum, a node that has no neighbor closer to the query than itself, without that node actually being the true nearest neighbor anywhere in the dataset. This happens because a graph built from a limited number of connections per node inevitably leaves some queries in awkward positions relative to the available edges, particularly in the same high-dimensional settings where distance concentration already makes every comparison harder. A search that stops the instant it hits a local minimum will sometimes report the wrong answer with complete confidence, since nothing in a purely greedy walk signals that a better answer might still be reachable through a slightly less direct path.

How does widening the search beyond a single path help?

The practical fix is to stop tracking only the single current-best candidate and instead maintain a small set of the best candidates seen so far, expanding outward from whichever one currently looks most promising rather than committing to one path immediately — a strategy generally called best-first or beam search. This doesn’t guarantee finding the exact true nearest neighbor any more than pure greedy search does, but it makes getting trapped in a bad local minimum far less likely, since the search can back away from a disappointing path and continue exploring from a different candidate instead. The width of that candidate set becomes a direct, adjustable trade-off between search quality and search cost — a wider set explores more of the graph and is less likely to settle for a mediocre local minimum, at the price of more distance calculations per query, which is precisely the trade-off that HNSW‘s own search-time parameter controls once a graph has layers built on top of this same basic idea.

None of this yet explains why a proximity graph should be split into layers rather than searched as a single structure, and that’s exactly where the next page picks up: the small-world and navigable small-world ideas that motivated stacking multiple graphs on top of each other in the first place. For the underlying vocabulary used throughout this page — Delaunay graphs, Voronoi regions, relative neighborhood graphs, and local minima — the graph-theory glossary section has a dedicated page working through each one in more depth.