Complexity of Graph-Based Approximate Nearest Neighbor Search

Greedy search holds a few milliseconds in production measurements, yet its worst-case guarantees stayed empty until recently, and probabilistic analyses published in 2025 began filling that gap.

Why greedy search is fast

Approximate nearest neighbor (ANN) search returns a sufficiently close candidate quickly instead of finding the exact closest vector. Graph-based methods precompute a proximity graph in which each vector is a node and edges connect vectors that are close to one another. When a query arrives, the search starts from a single entry point and repeatedly moves to whichever neighbor of the current node sits closer to the query.

The procedure is fast because a single move shrinks the candidate space substantially. When edges genuinely connect nearby vectors, a handful of moves lands the search near the query. This is where the measured behavior comes from: latency grows very little as the corpus grows.

Nothing guarantees that the stopping point is the global nearest neighbor. The termination condition, that no neighbor is closer, also holds at a local optimum. Practical implementations soften this with beam search, which keeps a queue of candidates rather than carrying a single one. Hierarchical Navigable Small World (HNSW) improves the entry point through a layered graph, controls the beam width with efSearch, and caps the neighbors per node with M.

That mitigation is empirical. Which values of M and efSearch produce which recall is found per dataset through a parameter sweep. Ma et al. (2025, arXiv:2509.15531) frame this situation as a gap between theory and practical optimization.

The lineage of the SNG pruning rule

How edges get chosen determines the character of a graph index. The Sparse Neighborhood Graph (SNG), proposed by Arya and Mount in 1993, defines a pruning rule that greedily selects the out-neighbors of each point. The candidate set of a point p starts as every other point. The rule adds an edge to the closest candidate, removes every candidate that is closer to that point than to p, and repeats until the set is empty.

SNG-prune(p, S):            # S = all points except p, as candidates
    while S is not empty:
        p* = argmin_{q in S} dist(p, q)
        add edge p -> p*
        for q in S:
            if dist(p*, q) <= dist(p, q):   # drop q if p* is closer to it
                remove q from S

The removal condition $d(p^*, q) \le d(p, q)$ eliminates redundant edges. Going through p* still brings the search closer to q than p is, so the direct edge from p to q is unnecessary. Only one representative edge survives per direction, which lowers the degree while preserving a path that can advance in any direction.

The indexes in wide use today are variants of this rule. NSG is designed to approximate the Monotonic Relative Neighborhood Graph (MRNG). MRNG guarantees that a path of monotonically decreasing distance exists for any query, which gives it near-logarithmic search complexity. The Vamana graph in DiskANN relaxes the removal condition to $\alpha \cdot d(y^*, y) \le d(x, y)$. A larger $\alpha$ produces a sparser graph.

This is where the guarantee breaks. MRNG guarantees a monotonic path but is too expensive to construct directly, and NSG, being an approximation of it, does not inherit the original guarantee. Vamana tunes sparsity through $\alpha$ without making any statement about path length.

Trading degree against path length

The cost of a graph index splits into two quantities. One is the out-degree, the number of outgoing edges per node. The other is the path length, the number of moves from the entry point to the neighborhood of the target. Every move measures the distance from the query to all neighbors of the current node, so the number of distance computations is roughly proportional to the product of the two.

The two quantities move in opposite directions. Keeping many edges makes it easy to jump far and shortens the path, but it raises the distances measured per move and enlarges the index. Pruning edges aggressively lowers the per-move cost while lengthening the path and raising the chance of getting trapped in a local optimum.

This is why any meaningful complexity statement has to bound both quantities together. A graph is not good merely because its degree is small, and it is not cheap merely because its paths are short. The truncation parameter that sets the strength of the pruning rule is exactly the handle on this trade.

The lower-bound side remains empty. Both 2025 results discussed below give upper bounds and conditional guarantees, and neither addresses lower bounds. How far the product of degree and path length can be pushed down on arbitrary high-dimensional data falls outside their scope.

Upper bounds from martingale analysis

Ma et al. (2025) modeled SNG construction as a stochastic process and proved asymptotic bounds on both quantities for the first time. The core move is treating the probabilistic shrinkage of the candidate set, which happens each time an edge is added, as a martingale. A martingale is a stochastic process whose conditional expectation for the next step equals the current value, which makes the shrinkage rate controllable step by step.

Obtaining both bounds together is what matters. A path of $O(\log n)$ is worthless if the degree is uncontrolled, because every move then explodes in cost, and a small degree buys nothing if the path is long.

The same model yields a closed-form optimization rule for the truncation parameter $R$. A value that previously took a multi-hour sweep to find is replaced by a calculation. In experiments on real datasets, index construction time dropped by 5.9x on average and by 15.4x at most, while recall stayed equal to or better than the existing methods.

The bound's scale differs from practical parameters. For $n$ of one million, $n^{2/3}$ is on the order of ten thousand, whereas the M used in practice usually falls between 16 and 64. The bound establishes that the degree does not explode; it does not tell anyone which value to set.

A poly-logarithmic exact search guarantee

Li et al. (2025, arXiv:2510.05975, SIGMOD 2026) approach the problem from a different angle. They define a new proximity graph called the α-convergent graph (α-CG). Pruning removes candidate neighbors with a rule built on a shifted-scaled triangle inequality. It belongs to the same family as the $\alpha$ relaxation in Vamana, but it aims at something else.

The guarantee is conditional in form. The paper proves that when the query lies within a constant $\tau$ of its exact nearest neighbor, that exact neighbor is found in poly-logarithmic time. In every other case the same time complexity returns an approximate nearest neighbor.

One premise comes attached. Bounded intrinsic dimensionality means the data must actually lie on a low-dimensional structure. Even with an embedding dimension of 1024, the condition holds when the data concentrates on a far lower manifold, so whether it holds depends on the dataset.

The practical variant α-CNG reduced distance computations by more than 15% and search steps by more than 45% against existing proximity graphs. Ma et al. address construction cost while Li et al. address accuracy guarantees at search time, which makes the two results complementary.

Where theory meets practical parameters

The M in HNSW corresponds to the truncation parameter of a pruning rule. Raising M increases the degree and shortens paths, and lowering it does the reverse. The sweep that finds this value is precisely what the closed-form rule from Ma et al. aims to replace.

efSearch sits on a different axis. A wider beam raises the probability of escaping a local optimum, but it also raises latency because more candidates must be kept. The theoretical results address the path length of greedy search, whereas how much a wider beam lifts recall remains an empirical matter.

All of these guarantees assume pure nearest neighbor search with no filters. A real-time recommendation case from the Woowa Brothers engineering blog shows where that assumption breaks. When a pre-filter condition is decided only at runtime, such as the deliverable service area, a precomputed static graph index cannot be used as it is.

The team chose to run HNSW from pgvector 0.5.0 on RDS instead of a pure ANN graph index. In load tests, RDS with pgvector recorded the highest throughput and the lowest failure rate against OpenSearch and Atlas MongoDB. They worked around the filter problem by combining several queries with UNION to cut database round trips and merging the results with Reciprocal Rank Fusion. Even as asymptotic complexity improves, in a service with filtering requirements the integration approach shapes performance more than the choice of index structure does.

Summary

Graph-based ANN search rests on an SNG pruning rule in use for more than thirty years, and the degree and path-length bounds of that rule were proved only in 2025. Ma et al. modeled construction as a martingale and proved a maximum degree of $O(n^{2/3+\epsilon})$ and an expected path length of $O(\log n)$. The closed-form rule for the truncation parameter that follows from the same model cut index construction time by 5.9x on average.

Li et al. presented α-CG, which guarantees exact search in poly-logarithmic time under a bounded intrinsic dimensionality premise. Both results are upper bounds and conditional guarantees, so neither fixes a practical parameter directly. Orders of magnitude still separate the worst-case bound from the M actually used. In a service with filters these guarantees do not apply at all, which makes the integration approach the thing to settle before the index structure.