The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input

What it claims

The guarantee is proved for a specific HNSW-like index, not for HNSW as shipped. The index differs from HNSW in three ways:

• edges are chosen by direction sectors rather than HNSW's neighbor heuristic;
• search is pure greedy, with no beam;
• the number of layers is fixed by a deterministic cutoff.

Theorem 1 is deterministic. If the built hierarchy meets two local conditions, greedy search returns a (1+ε)-approximate nearest neighbor for every query, from every starting vertex, on every layer. If the query is itself a stored point, search reaches it exactly. The probabilistic results only show that random inputs satisfy those conditions with probability 1−O(n^−M) for any chosen M > 2.

How it works

Layers. Each point gets a geometric height with P(H ≥ ℓ) = ρ^ℓ, as in HNSW. Layers are cut off at L, chosen so the top layer holds about D·log n points, where D = exp(½ d log d + O(d)).

Edges (Algorithm 1).

1. Split the unit sphere into K cells. Each cell must have angular diameter ω < π/3, and ω must be below an ε-dependent threshold ω_ε.
2. For each vertex v on each layer, take its m = ⌈C_pool log n⌉ nearest points as a candidate pool.
3. For each sector that has a candidate in it, add one out-edge from v to the nearest candidate in that sector.

Out-degree is therefore at most K. The paper sets K = exp(O(d)) and C_pool = exp(O(d)).

Coverage condition (the hypothesis of Theorem 1). At every vertex on layer ℓ:

• at least m points lie within r_cov·h_ℓ, where h_ℓ = (log n / (nρ^ℓ))^(1/d) and r_cov = O(√d);
• every sector contains a point from the candidate pool.

Search (Algorithm 2). Start at any top-layer vertex. Move to the out-neighbor closest to the query only if it is strictly closer than the current vertex. When no neighbor improves, drop to the next layer at the same point. Return the final vertex on layer 0.

Proof idea. If the current vertex is far from the query, some sector edge points roughly toward the query. A cosine-rule argument shows that edge strictly reduces the distance. So greedy search can only stop near the query, and the number of hops is bounded by how many points lie in that neighborhood.

Evidence

The results are proofs, not benchmarks:

• Accuracy, input classes. Three input classes are covered: independent (homogeneous Poisson), repulsive (Hermitian determinantal process) and clustered (Cox process with intensity between fixed bounds a and b).
• Accuracy, probability. The probability that the coverage condition fails is o(n^−M). The probability of failure including an empty top layer is O(n^−M).
• Query cost. Search uses O(K(T_tot + L + 1)) distance computations, where T_tot is the total hop count. The summary's O(exp(½ d log d + O(d)) log n) is a bound on expected hops, so the distance-computation cost carries an extra K = exp(O(d)) factor.

The paper also motivates itself with earlier negative results:

• fixed-width beam search can lack any finite approximation guarantee for arbitrary queries, even on graphs where greedy routing works;
• on adversarially built datasets, practical HNSW may need to examine a constant fraction of points for high recall, even in 2-D.

Limits

• Low dimension only. The required regime d = o(log n / log log n) is far below real embedding dimensions. For example, at n = 10^9 the ratio log n / log log n is about 7, using natural logs.
• Toy space. The space is the unit torus with Euclidean distance. There are no boundaries and no real embedding distributions.
• Different algorithm from production. Faiss and hnswlib use beam search and different neighbor selection. The results do not transfer to them directly.
• Different strength of guarantee. The hop bound is an expectation for a fixed query, or a random query independent of the data. The accuracy bound is uniform over all queries.
• Experiments not available here. The paper says it has experiments on these point-process models, varying dimension and sector count. The fetched text ends before them, so no empirical numbers are available.