W1. The claimed minimum navigable norm αnav is not supported by the theoretical analysis.
Section 4.2 presents αnav as the minimum normalized squared norm of vertices visited during greedy search, and concludes that hubs with smaller norms are never visited. However, Appendix D.2 defines αnav=α+(1,2) as the unique minimizer of the navigation rate function Inav, meaning it represents the most typical one-step output norm, not the minimum possible output norm. The actual lower boundary of the region defined in the appendix is infHnav, which is not shown to equal αnav. In fact, evaluating the authors' own equations with w=6.448 and ρs=0.5 gives α+(1,2)≈0.628583, while the feasible source state (α,θ)=(0.99,0) produces α+(0.99,1.99)≈0.627857. This source state has rate φ(0.99,0)≈2.52×10−5<1/w, and the resulting output norm is within the geometric-hub region, so it also belongs to Hnav under Definition 8. Therefore, even the authors' continuous model contains navigable norms below αnav, contradicting its interpretation as a lower bound in Section 4.2 and Figure 1d. The unique-minimizer statement in Theorem 11 is not itself disproved, but the main text draws a stronger conclusion that does not follow.
W2. The one-step continuous analysis does not establish which vertices are actually visited during greedy search.
Appendix D.2 analyzes the norm of a continuous optimizer x+ that minimizes the query distance under the large-deviation and neighborhood constraints. However, this optimizer is not necessarily an actual dataset vertex, and the authors do not establish that the norm of the selected neighbor in the finite graph concentrates around this optimizer uniformly over relevant source states. More importantly, the analysis considers source states drawn from the original Gaussian distribution, whereas the states encountered after one or more greedy steps follow a search-dependent distribution. The optimizer can also be defined for states in which it does not improve the query distance, in which case actual greedy search would stop rather than visit it. Consequently, this one-step analysis does not directly characterize vertices visited along complete greedy paths. The claim that the highest-in-degree hubs are never visited requires a stronger argument connecting the continuous optimizer to actual improving transitions and complete search trajectories.
W3. The formal definition of a navigable hub is inconsistent with the claimed result.
Definition 3 states that a geometric hub is navigable if there exists a starting vertex v′ and a query q such that the hub lies on the greedy path from v′ to q. As written, this definition does not exclude the starting vertex itself, which would make every geometric hub trivially navigable by choosing that vertex as the starting point. Even if the starting vertex is excluded, the definition quantifies over the existence of some query, whereas the theoretical analysis assumes a fixed query independent of the dataset. These are substantially different conditions, and results for an independent query do not establish that a hub can never be visited for any possible query. The definition and theorem statements should specify the intended quantifiers over queries and starting vertices.
W4. The proof of Theorem 11 contains incorrect equations and unsupported steps.
The proof of Theorem 11 in Appendix D.2 (page 41) contains several mathematical errors. First, it repeatedly uses s*(1; ρ_s) = m_flip² − m_flip, whereas the correct expression from the threshold definition is s*(1; ρ_s) = m_flip² + m_flip. Since 0 < m_flip < 1, the expression with the minus sign is negative and therefore cannot represent a normalized squared distance. Second, in the case λ_+ = 0, the proof states that α_(λ_+) = 0, although the definition of the interpolated center gives α_(λ=0) = 1. Finally, the theorem claims that sup H_nav < α_h, but the provided argument does not establish this strict inequality. These errors affect the proof relating the navigable and geometric hub regions. Although some may be fixable, the proof as written is not valid and requires revision.
W5. The geometric-hub analysis characterizes expected degrees rather than directly proving the claimed classification of vertices.
Definition 2 defines geometric hubs using their actual incoming and outgoing degrees. In Appendix D.1, however, Lemmas 21–25 characterize the expected incoming degree through a large-deviation exponent and compare it with the expected outgoing degree. These calculations explain why lower-norm vertices tend to have much larger incoming degrees, but a comparison of expectations alone does not prove that every vertex in the claimed norm region has incoming degree larger than outgoing degree. The main text presents the threshold αh as an if-and-only-if characterization of geometric hubs, which requires an additional concentration argument for realized degrees. Such an argument may be straightforward for norm levels separated from the threshold, but the behavior near αh also needs to be handled carefully.
W6. Some steps in the main Gaussian navigation proof require additional justification.
The overall argument for the constant-step navigation guarantee is promising, but several technical steps are not fully justified. In Lemma 7, the authors invoke Chebyshev's inequality to obtain a norm bound holding simultaneously for all n dataset points; this does not follow from the stated calculation when n grows exponentially with d, and an exponential tail bound is needed. The transfer from the threshold graph to the exact k-NN graph also relies on probability estimates that should be justified uniformly over the relevant source-norm interval, rather than only for each fixed norm. Furthermore, Theorem 10 uses the limiting nearest-neighbor distance sNN(1) to conclude a finite-sample c-ANN guarantee, which requires an additional argument using approximation slack and concentration of the actual nearest-neighbor distance. There are also smaller inaccuracies, such as the equality gG(x1)=r in Lemma 18, which does not hold throughout its stated Case 1. These issues appear more readily repairable than the problems with the navigable-hub theorem, but the proofs should be corrected.
W7. The comparison with spherical-uniform data does not establish that hubness accelerates greedy search.
Section 4.3 compares the sufficient graph-degree exponents required by the authors' analysis for Gaussian and spherical-uniform data. Although the derived comparison is interesting, a smaller sufficient exponent does not necessarily imply that the actual minimum degree required for successful search is smaller. The paper does not provide matching necessary bounds or otherwise establish that the derived thresholds are tight. Moreover, changing from spherical-uniform to Gaussian data changes several geometric properties simultaneously, so the comparison does not isolate hubness as the cause of any improvement. Therefore, the conclusion that hubs accelerate nearest-neighbor search is stronger than what the theoretical results establish. A more accurate interpretation would be that the analysis gives a more favorable sufficient degree bound for Gaussian data in certain parameter regimes.
W8. The constant-step guarantee should be distinguished from actual search complexity.
The main theorem guarantees that greedy search reaches an approximate nearest neighbor in O(1) steps, but each step examines k=nρs+o(1) outgoing neighbors. Thus, the number of distance evaluations can still be nρs+o(1), which is substantial when the required degree exponent is large. For example, the paper's near-exact asymptotic analysis gives a limiting critical exponent approaching 8/9 as w increases. While the constant-step result is theoretically interesting, its implications for efficient ANN search should be discussed in terms of the total number of distance evaluations and graph storage, rather than the number of greedy steps alone.
W9. The experiments provide limited validation of the strongest theoretical claims.
The experiments are restricted to synthetic Gaussian and spherical-uniform datasets, and the paper provides limited details about the exact graph construction, number of queries, and evaluation protocol. The empirical degree comparisons use a 90% success threshold with uniformly sampled starting vertices, whereas the main theorem provides a high-probability asymptotic guarantee simultaneously for every starting vertex. These are different guarantees, and the experiments do not directly evaluate the stronger condition. Similarly, Figure 1d compares visited norms with the proposed αnav, but does not distinguish the typical visited norm from the minimum visited norm or separately validate one-step and multi-step behavior. Given the central role of the navigable-hub claim, more direct experiments examining the full distribution of visited norms and the predicted lower boundary would be valuable. As a minor numerical point, evaluating the displayed near-exact degree formulas gives a Gaussian/spherical crossover near w=6.472, rather than the approximately 6.448 stated in Figure 1c.