What is the Delaunay-like graph assumption?

The Delaunay-like graph assumption is the theoretical simplification treating a proximity graph as approximating a Delaunay graph, whose property guarantees greedy search always reaches the true nearest neighbor with no local minimum.
Created: Updated: 5 min read

The Delaunay-like graph assumption is the theoretical simplification, used in some analyses of HNSW‘s search guarantees, that treats the proximity graph as if it approximated a Delaunay graph — a specific, idealized graph structure with the property that a purely greedy search starting from any node is mathematically guaranteed to reach the true nearest neighbor to any query, with no possibility of getting stuck at a local minimum along the way. Real HNSW graphs don’t actually achieve this idealized structure exactly, but understanding what a genuine Delaunay graph promises, and why HNSW’s construction process only approximates that promise rather than fulfilling it perfectly, clarifies exactly what kind of theoretical footing HNSW’s greedy search guarantees actually stand on.

A Delaunay graph, in its classical geometric definition, connects points in a way derived from partitioning space into regions such that each point’s region contains everything closer to it than to any other point — two points get an edge specifically when their regions share a boundary. A remarkable consequence of this specific construction is that a greedy search — always moving to whichever neighbor is closest to the query — starting from any node in a Delaunay graph is provably guaranteed to reach the true nearest neighbor of any query point, with no possibility of a local minimum ever trapping the search along the way. This guarantee is exactly what makes the Delaunay graph theoretically appealing as a target structure for greedy nearest-neighbor search: if a graph genuinely has this property, greedy navigation on it is provably exact, sidestepping entirely the local-minimum vulnerability that ordinary greedy search on an arbitrary graph is exposed to.

This guarantee comes at a real structural cost, though — computing an exact Delaunay graph becomes prohibitively expensive as dimensionality grows, with both the computational cost of construction and the number of edges required scaling extremely poorly in high-dimensional spaces, which is exactly why no practical high-dimensional nearest-neighbor search system actually builds a true Delaunay graph directly.

Why does HNSW’s theoretical analysis lean on this idealized structure, given that HNSW doesn’t actually build one?

Because a genuine Delaunay graph is computationally infeasible in high dimensions, HNSW’s construction process instead builds an approximation — a graph whose diversified neighbor-selection heuristic is deliberately designed to mimic some of the Delaunay graph’s beneficial properties without paying its full computational cost. The Delaunay-like graph assumption, used in certain theoretical treatments of HNSW’s expected behavior, proceeds by assuming the constructed graph approximates a true Delaunay graph closely enough that the greedy-search guarantee approximately carries over, letting the analysis borrow the strong exactness result that a genuine Delaunay graph provides as a stand-in for what an HNSW-built graph might be expected to deliver in practice.

This is precisely the kind of idealizing assumption that lets a theoretical analysis produce a clean, tractable result — reasoning directly and rigorously about the messy, approximate connectivity HNSW’s heuristic actually produces would be considerably harder than reasoning about an idealized structure with a well-understood, provable guarantee already attached to it.

What actually happens to HNSW’s greedy-search guarantee once this idealizing assumption is dropped and the real, approximate graph is considered instead?

This is exactly the gap already discussed on the exact-nearest-neighbor-search and local-minimum-in-graph-search glossary pages: once the Delaunay-like assumption is relaxed to reflect what HNSW’s construction process actually produces, the strong, provable exactness guarantee doesn’t carry over cleanly. HNSW’s graph approximates some of the beneficial properties a Delaunay graph would provide, but it doesn’t achieve them exactly, which is precisely why HNSW’s greedy search retains a genuine, non-zero risk of stopping at a local minimum, and why HNSW is correctly described as an approximate rather than an exact nearest-neighbor search method despite the theoretical inspiration it draws from Delaunay-graph reasoning.

This gap between the idealized assumption and the real, constructed graph is exactly the tension explored on the difference-between-worst-case-and-idealized-HNSW-analysis glossary page — the Delaunay-like assumption produces clean, favorable theoretical results specifically because it’s an idealization, and the honest caveat accompanying any analysis built on it is that real HNSW graphs only approximate, rather than exactly satisfy, the property the analysis actually depends on.

Why is this idealizing assumption still considered useful, despite this acknowledged gap?

Even an approximate resemblance to Delaunay-like connectivity provides real, practical value: it explains, at least qualitatively, why HNSW’s neighbor-selection heuristic favoring diversified connections over simply the closest candidates tends to produce graphs that behave considerably better for greedy search than a naive k-nearest-neighbor graph would, since the heuristic is explicitly trying to approximate exactly the kind of well-spread, locally representative connectivity a genuine Delaunay graph would provide. The assumption’s value lies in the intuition and design guidance it offers, even though it stops short of delivering the same unconditional, provable exactness guarantee a true Delaunay graph would.

Having covered how the Delaunay-like graph assumption provides a useful, if idealized, theoretical anchor for reasoning about HNSW’s greedy-search behavior, the local-minimum-in-graph-search and diversified-neighbor-selection glossary pages are worth revisiting together with this fuller picture of what that idealization is actually standing in for. From there, the difference-between-worst-case-and-idealized-HNSW-analysis glossary page addresses directly the honest gap between this kind of clean theoretical reasoning and what real, imperfectly-constructed graphs can actually be expected to deliver.