What can we actually prove about HNSW’s complexity, and what can’t we?

What can actually be proven about HNSW‘s complexity is more conditional than the commonly repeated claim that “HNSW search is O(log n)” suggests: the logarithmic argument holds under a specific set of idealized assumptions, and practical HNSW graphs don’t fully satisfy those assumptions, which means the honest answer separates a clean theoretical argument from an empirical, dataset-dependent reality rather than treating the two as the same thing.

Where does the O(log n) claim actually come from?

The argument starts from something genuinely provable: because each vector‘s maximum layer is chosen using a probability that decays exponentially, the expected height of the resulting layer structure — how many layers exist before the population thins down to nothing — scales with the logarithm of the number of vectors in the dataset. Building on that, if the graph at each layer behaved like an idealized, Delaunay-like proximity graph, and if the amount of work done at each layer during a search stayed bounded rather than growing with dataset size, then the number of layers visited during a search would itself scale logarithmically, and the total search cost would follow. This is a real and useful argument, but notice how much it depends on those two conditional clauses about the graph‘s structure and per-layer cost — the logarithmic conclusion is only as solid as those assumptions are.

What has to be true for that argument to hold, and does practical HNSW satisfy it?

Practical HNSW graphs use a finite, fixed connection budget per vector and a heuristic neighbor-selection rule rather than an exact Delaunay-style construction, precisely because building anything resembling a true Delaunay graph is computationally impractical in high dimensions and isn’t even well-defined for an arbitrary distance function over data with no known global structure. The heuristic approximates useful properties of an idealized proximity graph without reconstructing one exactly, and how well that approximation holds up depends on the dataset’s actual geometry, its intrinsic dimensionality, and the exploration width used at query time — none of which are accounted for in the clean version of the argument above. This is exactly why the original researchers who introduced HNSW described their own logarithmic scaling argument as conditional and noted that additional analytical work would be needed to fully justify it for practical, high-dimensional data. The responsible way to state the result is to keep the two halves separate: the layer-height argument is a solid piece of probability theory, while the claim that search itself runs in logarithmic time is an empirical regularity, well-supported by measurement on real datasets, rather than a proven worst-case guarantee.

What can be said about how long construction takes?

Under the same favorable assumptions used for the search argument — a well-behaved graph and roughly constant work per insertion — building the entire index by inserting vectors one at a time costs on the order of n times the per-insertion search cost, giving a construction complexity that scales as n multiplied by a logarithmic term, often written as n log n. This scaling is generally observed in practice for reasonably well-behaved data, though it carries the same caveat as the search argument: it describes typical behavior under favorable conditions rather than a guarantee that holds for every possible dataset and parameter setting.

What does the graph actually cost in memory, separate from the vectors themselves?

Memory cost splits cleanly into two components that are worth keeping separate. Storing the raw vectors themselves costs an amount proportional to the number of vectors multiplied by their dimensionality — unavoidable regardless of what index sits on top of them. The graph structure adds a second cost on top of that, proportional to the number of vectors multiplied by the maximum number of connections each one is allowed to keep, since every one of those connections has to be stored somewhere as a reference to another vector. This second cost is what people mean when they describe HNSW as memory-hungry compared to techniques that compress vectors more aggressively: the graph’s connections are a genuine additional expense layered on top of the vectors, not a replacement for storing them.

Complexity numbers only describe how much work gets done — they say nothing about whether that work actually finds the right answer, which is a separate question this site picks up next: why recall and the amount of exploration a query actually needs can vary enormously even among queries run against the exact same index. Readers who want the underlying probability argument behind the exponential layer distribution spelled out with actual notation, rather than described in words, will find it in this site’s appendix on mathematical notation.