Almost Navigable Graphs

Christopher Musco; Pratyush Avi

REVIEW 3 major objections 5 minor 42 references

Almost Navigable Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Any dataset admits a near-navigable search graph with only O(n) edges, for any relaxation below full navigability.

desk verdict The core relaxation result is real and the proofs mostly check out; the empirical section is the soft spot but doesn't sink a solid theory paper. read the letter →

arxiv 2607.14564 v1 pith:PH64R24S submitted 2026-07-16 cs.DS

Pratyush Avi , Christopher Musco This is my paper · ORCID

classification cs.DS MSC 68P0568Q2568W20

keywords approximatenearestneighborsearchnavigablegraphsgraphsparsitygamma-almostnavigabilityrandomizedconstructionbeamgreedyvectordatabases

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces γ-almost navigability, a relaxation of the graph-navigability property used in approximate nearest-neighbor search. Instead of demanding that every node have an edge moving closer to every other node, it requires each node to have an edge moving closer to a γ fraction of the dataset. The central claim is that for any dataset, under any distance function, and any γ<1, there exists such a graph with average out-degree at most 4/(1−γ) — linear in the number of points. A randomized construction achieves this in near-linear time, both polynomial improvements over fully navigable graphs. The authors also show the relaxed definition alone guarantees nothing for greedy search, but report experiments where beam search on γ<1 graphs reaches the recall of fully navigable graphs with roughly half the degree and about 35–47% fewer distance computations.

What carries the argument

The central object is the ownership set: for a node v inside a subset S, its ownership set is all dataset points for which v is the closest point in S. Adding a clique on S guarantees v has an edge closer to every point outside its ownership set. The fact that the median of a list of numbers is at most twice the mean implies at least half the nodes in S own at most 2n/|S| points, which falls below (1−γ)n when |S| ≈ 2/(1−γ). Iterating this 'power of cliques' argument over shrinking sets yields the linear edge bound; replacing exact ownership counts with counts on a random sample reduces construction to near-linear time via a Chernoff bound.

What would settle it

Take a dataset approximating the disconnected 2D hard instance from Lemma 4, build a γ-almost navigable graph using either the paper's construction or the early-stopped pruning heuristic, run beam search, and measure recall on in-distribution queries. If recall collapses to roughly 1/(1−γ) of queries rather than matching a fully navigable graph, the empirical claim is falsified. A less adversarial test: find any real dataset where a γ<1 graph with half the degree yields recall more than a few percentage points lower than the fully navigable graph at the same number of distance computations.

Watch

Extended reading notes

Core claim

The paper proves that fully navigable graphs, which can require Ω(n^{3/2}) edges and Ω(n^{2−ε}) construction time in the worst case, are not necessary once a tiny fraction of navigation constraints is relaxed. Its main theorem states that for any finite point set, any distance function, and any γ∈[0,1), there exists a γ-almost navigable graph with average out-degree at most 4/(1−γ). The proof is constructive via iterative clique peeling: partition remaining points into cliques of size about 2/(1−γ); a median argument shows at least half the nodes in each clique gain edges closer to a γ fraction of the dataset; discard those and repeat, with leftover nodes connected to all points. A randomize

Load-bearing premise

The practical value claim rests on the assumption that the specific early-stopped pruning heuristic used in the experiments produces γ-almost navigable graphs that behave like the ones theory describes, and that beam-search performance transfers from the four tested datasets to other real datasets — since the formal definition alone, as Lemma 4 shows, guarantees nothing for search.

Editorial extensions

If this is right

The Ω(n^{3/2}) worst-case edge lower bound for fully navigable graphs is an artifact of demanding perfect navigability; allowing a tiny fraction of violated constraints reduces the bound to O(n/(1−γ)).
Near-linear construction replaces the Ω(n^{2−ε}) lower bound for exact navigability, making sparse search-graph construction feasible at billion-node scale at least in principle.
The formal definition alone offers no worst-case search guarantee, so practical benefits must come from the interaction between the specific heuristic construction and beam search; the experiments suggest this interaction is favorable on standard benchmarks.
If the empirical results hold, vector search systems could store indexes at roughly half the memory footprint while answering queries with comparable recall, directly addressing memory and latency constraints.
The results extend to any distance function satisfying minimal axioms, not just Euclidean space, so the existence theorem is universal across metrics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The existence theorem is parameter-free and holds for every metric, but the experiments use a different, heuristic construction; a testable prediction is that the two constructions behave differently on pathological datasets, and the heuristic's success is not implied by the theorem.
Lemma 4 constructs a disconnected γ-almost navigable graph; a natural next step would be to add a mild connectivity condition (e.g., every component has size Ω(n)) and ask whether worst-case search guarantees return.
Because the definition itself guarantees nothing for search, the paper implicitly shifts the burden to dataset structure; a promising extension is to characterize which structural properties (low intrinsic dimension, clusteredness) make γ<1 graphs actually searchable.
The reported gains are confined to Euclidean benchmarks; a direct test is to run the same comparisons on non-metric or adversarially generated distance matrices, where the definition still applies but the heuristic may not.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Core take: the paper introduces γ-almost navigability, proves any dataset admits such a graph with O(n/(1−γ)) edges, and gives a near-linear randomized construction. The existence and construction results are new and, as far as I can tell, correct. The negative Lemma 4 is also right, and I respect that they state it in the main text. The theory alone is a meaningful step for the graph-based ANNS subfield: it breaks the Ω(n^{3/2}) edge and Ω(n^{2−ε}) time barriers by relaxing the definition.

I checked the main proofs. Theorem 1's ownership-set/median argument works, and the edge count is fine. Theorem 2's Chernoff argument works, though the claimed 3/4 shrinkage of Π in Section 2.2 is not quite justified near the loop threshold; a weaker monotone-decrease argument suffices, so the theorem stands. Lemma 4's cluster separation should be ≥4ε rather than >2ε for the triangle-inequality argument to give the stated coverage; that's another easy fix. Both are minor.

The soft spot is the empirical section. The headline practical claim—comparable recall at 35–47% fewer distance computations and roughly half the edge count—depends entirely on the early-stopped robust prune heuristic in Algorithm 2. No code is released, the (γ, beam width) configurations in Tables 4–5 are chosen from the Pareto frontier after seeing test-set results, there are no error bars, and the retrieval experiments cover only four datasets. The stress-test note is also correct about an off-by-one: the stopping rule uses (1−γ)n while Definition 2 requires (1−γ)(n−1), so the reported γ values are slightly optimistic. That particular issue is small, but the general point stands: these experiments are suggestive, not conclusive. In particular, the dramatic degree savings on billion-scale data are estimates from 10,000 sampled nodes.

That said, the paper is transparent about these limitations—it calls the heuristic unguaranteed and notes the Pareto selection—and the theory section would stand even without the experiments. I'd send this to a serious referee. The proofs need the small fixes above, and the empirical claims need code and proper validation before they can be taken at face value. But the core idea is new, formally grounded, and worth engaging with.

Referee Report

3 major / 5 minor

Summary. The paper introduces γ-almost navigable graphs, a relaxation of the navigability property used in graph-based ANNS. For any finite point set and any distance function, Theorem 1 gives a constructive existence proof of a γ-almost navigable graph with average out-degree O(1/(1−γ)), hence O(n/(1−γ)) total edges. Theorem 2 gives a randomized algorithm that constructs such a graph in O(nT log(n/δ)/(1−γ)) time with probability 1−δ. A negative result (Lemma 4) shows that γ-almost navigability does not guarantee successful greedy search for in-distribution queries. Experiments using an early-stopped robust-prune heuristic on up to eight datasets report large reductions in degree and search cost at γ<1 relative to fully navigable graphs. The theoretical results are self-contained; the empirical section is explicitly preliminary.

Significance. The theoretical contribution is significant: it shows that relaxing navigability to cover a 1−γ fraction of constraints changes the worst-case edge count from Θ(n^{3/2}) to O(n/(1−γ)) and the construction time from near-quadratic to near-linear, for arbitrary distance functions and without data-dependent assumptions. The proof is simple, constructive, and parameter-free apart from the input γ; the sample-based construction is an elegant extension. The negative result honestly delineates the limits of the relaxation. The empirical results are promising and potentially important, but their current support is preliminary. The paper does not ship code, and the quantitative efficiency claims rest on post-hoc test-set selection. Nevertheless, the theoretical core stands on its own and is a meaningful contribution to the theory of graph-based ANNS.

major comments (3)

[Section 3.2, Tables 2/4/5] The quantitative claims (e.g., 35–47% fewer distance computations, 46–55% lower degree at fixed recall) are based on selecting (γ, beam width) from the Pareto frontier after observing test-set recall curves, with no held-out validation, no confidence intervals, and no released code. These numbers are therefore post-hoc descriptions of the test set rather than validated performance. Since the practical value of γ-almost navigability is a central claim, either provide a proper validation setup (e.g., parameter selection on a validation set, multiple runs with error bars) or explicitly reposition the experiments as preliminary and remove strong quantitative summaries from the abstract.
[Section 3.1, Algorithm 2] Algorithm 2 uses the stopping rule `while |U| > (1−γ)n`, with U initialized to P\{p}. Definition 2 requires each p to cover at least γ(n−1) other points, i.e., the uncovered set in P\{p} must have size at most (1−γ)(n−1). The implemented rule can therefore terminate with up to (1−γ) additional uncovered points per node, producing graphs that are only γ' = γ − (1−γ)/(n−1) almost navigable. The numerical gap is tiny for the reported settings, but the experiments do not strictly evaluate the defined property. The stopping rule should be corrected to `(1−γ)(n−1)` or the reported γ values should be adjusted.
[Section 2.1] The remark after Theorem 1 states that the lower bound of [13] extends to the 1−O(1/√n)-coverage setting, precluding bounds of the form O(n/√(1−γ)), and that this 'can be checked.' This is an omitted proof of a non-obvious claim about the optimal dependence on γ. If this optimality statement is part of the contribution, it should be proved or a precise citation provided; otherwise it should be removed or softened.

minor comments (5)

[Abstract] The phrase 'the sparsest navigable graph requires O(n√n) edges in the worst-case' is misleading; the known result is an upper bound of O(n√n) and a matching lower bound, so the worst-case requirement is Θ(n√n) (or 'can require Ω(n√n) edges').
[Section 3.1] The text says 'constructing a navigable graph requires hundreds of edges per node' for billion-scale datasets, but Table 1 reports mean degrees 144.1 and 105.5 for Yandex DEEP and BIGANN, which are below two hundred. Please qualify the statement.
[Section 3.2, Table 2] The 'Average' row in Table 2 is over only four datasets (MNIST, Fashion-MNIST, COCO-i2i, Glove25) and four recall targets. State this clearly in the caption/text so readers do not over-generalize.
[Lemma 4] The hard instance should specify that the cluster separation is large enough relative to the ball radius ε (e.g., intervals of length >4ε) for the triangle-inequality argument to hold exactly as stated; the current text says >2ε, which is insufficient to guarantee that a move to an adjacent cluster reduces distance to all points in a farther cluster.
[Appendix A] In Algorithms 2 and 3, the output line says 'γ-navigable graph'; this should be 'γ-almost navigable graph' for consistency with Definition 2.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; Theorems 1 and 2 are self-contained, and author-overlapping citations are motivational only.

full rationale

Theorem 1 is proven by a self-contained clique-peeling argument (Claim 3, median at most twice the mean), with no fitted constants and with the bound holding for any distance function and any gamma in [0,1). Theorem 2's correctness and runtime follow from a Chernoff bound on random samples of size w = 16 log(n/delta)/(1-gamma); no parameter is calibrated to data. Lemma 4 is an explicit worst-case construction. The citations to [12] and [13] (both coauthored by C. Musco) and to [25] are used to motivate the relaxation by citing established navigability barriers; they are not proof ingredients for the paper's theorems. The remark that 'the lower bound of [13] extends' is an unproved extension of a same-author result, but it is an aside about a possible improvement, not a load-bearing step. The empirical sections rely on early-stopped robust prune (which 'does not have any guarantees') and select (gamma, beam-width) points from the Pareto frontier after observing results; these are legitimate concerns about external validity and test-set selection, but they are not circularity because the reported tradeoffs are measurements rather than derivations from the definition. Overall, no claimed prediction reduces by construction to an input, fitted value, or self-citation chain.

Assumptions & free parameters 5 free parameters · 5 assumptions · 1 invented entities

The central theorems introduce no fitted parameters: γ is an input relaxation parameter, and constants (4/(1−γ), 16 log(n/δ)/(1−γ)) are explicit. The empirical section is where freedom enters: γ and beam width are tuned per dataset and per target recall on the Pareto frontier; billion-scale degree statistics use a 10,000-node subsample; and the baseline robust-prune implementation has unstated native parameters. Axioms are elementary (median≤2·mean, Chernoff, unique distances) with the caveat that Lemma 4’s stated cluster separation (“greater than 2ε”) is insufficient for its triangle-inequality claim (needs ≥4ε). The “invented entity” is the definition itself, which carries falsifiable empirical handles.

free parameters (5)

γ (coverage parameter in experiments) = 0.965–0.99995 depending on dataset and target recall (e.g., MNIST @0.90 recall→0.965–0.996; Glove25 →0.9997–0.99995)
In the theory γ is an input relaxation parameter. In the experiments γ is chosen per dataset and per target recall from the Pareto frontier over γ<1 after observing results (“On choosing γ,” Section 3.2), i.e., fitted to hit recall targets; it drives the reported degree and distance-computation savings.
beam width b = swept over {1,2,4,16,32,64,100,128,256}, selected per target recall
Search hyperparameter; the recall-runtime trade-off tables pick the b that achieves each target recall on the Pareto frontier.
subsample size for billion-scale degree statistics = 10,000 nodes
For Yandex DEEP, BIGANN, SimSearchNet++, and SPACEV1B, degrees are estimated from 10,000 randomly selected nodes (Section 3.1); the sampling seed is not stated.
robust prune parameters (R, pruning factor) = unspecified
Appendix Algorithm 2 omits the native DiskANN robust-prune parameters (max degree, pruning factor); the baseline navigable-graph degrees (e.g., SimSearchNet++ mean 2077.6) depend on these unstated choices.
sample-size constant in Algorithm 1 = w = 16 log(n/δ)/(1−γ)
Chosen by hand so the Chernoff bound gives failure probability δ/n² per point per round; a constant multiplier derived from the analysis, not fitted to data, and correctness does not depend on its exact value.

assumptions (5)

domain assumption All pairwise distances between distinct points in P are unique (ties broken by perturbation)
Stated in the preamble to Definition 1 (footnote 2). Every strict-improvement argument (argmin over S, d(s,r) < d(p,r)) needs uniqueness; the paper notes a random perturbation fixes it.
standard math Median ≤ 2× mean for non-negative numbers
Claim 3’s core fact; elementary and correct.
standard math Chernoff concentration for sums of independent Bernoulli variables
Theorem 2’s correctness proof; textbook bound.
domain assumption Euclidean triangle inequality (metric distances) in Lemma 4’s hard instance
The 2D line-cluster construction relies on cluster-to-cluster distances dominating intra-cluster diameters; the stated separation “greater than 2ε” is insufficient (needs ≥4ε) for the claimed closeness of adjacent-cluster edges.
domain assumption SETH and prior navigability lower/upper bounds (Ω(n^{3/2}) edges [13]; Ω(n^{2−ε}) construction time [12, 25])
Used only to motivate the barriers being relaxed; not an ingredient of the paper’s own theorems.

invented entities (1)

γ-almost navigable graph independent evidence
purpose: A relaxation of navigability in which each node must have an out-edge closer to ≥ γ(n−1) other nodes; enables O(n/(1−γ))-edge graphs and near-linear construction.
The object is a definition, not a physical postulate. It carries falsifiable handles: the paper predicts degree savings (Table 1) and recall/runtime trade-offs (Tables 2, 4, 5) on public benchmarks reproducible by others, and Lemma 4 characterizes its worst-case greedy-search behavior.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Almost Navigable Graphs." pith.science (2026). https://pith.science/paper/PH64R24S

@misc{pith2026260714564,
  author       = {Pith},
  title        = {Pith review of: Almost Navigable Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PH64R24S}},
  note         = {Machine review of arXiv:2607.14564}
}

abstract

Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $\Omega(n^{2-\epsilon})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$\gamma$-almost navigability'' for any $\gamma \in [0,1]$, with $\gamma = 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $\gamma$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $\gamma < 1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.

Figures

Figures reproduced from arXiv: 2607.14564 by the authors.

**Figure 2.** In these plots, the vertical axis shows the [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** These plots show average recall@𝑘 vs. average distance computations for various choices of navigability parameter, 𝛾, and beam width parameter, 𝑏. The red solid line represents the recall curve for fully navigable graphs for various choices of beam width. We only plot points corresponding to beam widths ≥ 𝑘, since having a lower beam width places a limit on the maximum achievable recall. In these plots, points up an… view at source ↗

Figures from the paper (1 more)

**Figure 3.** Figure 3: Dataset Target Recall Average Degree 𝑘 = 1 𝑘 = 10 𝑘 = 100 F A R 𝜸 F A R 𝜸 F A R 𝜸 MNIST 0.90 19.64 10.32 0.53 0.99500 19.64 10.81 0.55 0.99600 19.64 6.42 0.33 0.96500 0.95 19.64 10.81 0.55 0.99600 19.64 8.04 0.41 0.98500 19.64 8.04 0.41 0.98500 0.97 19.64 11.45 0.58 0.…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 1 linked inside Pith

[13]

Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2024. Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits. InAdvances in Neural Information Processing Systems 37 (NeurIPS)

2024
[1]

Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2025. Distance Adaptive Beam Search for Provably Accu- rate Graph-Based Nearest Neighbor Search. InAdvances in Neural Information Processing Systems 38 (NeurIPS)

2025
[2]

Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.Commun. ACM51, 1 (2008), 117–122

2008
[3]

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. InAdvances in Neural Information Processing Systems 28 (NeurIPS)

2015
[4]

Alexandr Andoni, Ilya Razenshteyn, and Negev Shekel Nosatzki. 2017. LSH Forest: Practical Algorithms Made Theoretical. InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 67–78

2017
[5]

Sunil Arya and David M. Mount. 1993. Approximate nearest neighbor queries in fixed dimensions. InProceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

1993
[6]

Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems87 (2020). Code available at https://github.com/erikbern/ann- benchmarks

2020
[7]

Mayank Bawa, Tyson Condie, and Prasanna Ganesan. 2005. LSH forest: self- tuning indexes for similarity search. InProceedings of the 14th International Conference on World Wide Web

2005

Show all 42 references

[8]

Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. InProceedings of the 23rd International Conference on Machine Learning (ICML)

2006
[9]

Marián Boguñá, Dmitri Krioukov, and K. C. Claffy. 2009. Navigability of Complex Networks.Nature Physics5, 1 (2009), 74–80

2009
[10]

Clarkson

Kenneth L. Clarkson. 1994. An algorithm for approximate closest-point queries. InProceedings of the 10th Annual Symposium on Computational Geometry (SOCG)

1994
[11]

Aaron Clauset and Cristopher Moore. 2003. How Do Networks Become Naviga- ble?arXiv:0309415(2003)

2003
[12]

Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, and Richard Wen
[14]

Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2026. The Faiss Library.IEEE Transactions on Big Data12, 2 (2026), 346–361

2026
[15]

Cong Fu and Deng Cai. 2016. EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph.arXiv:1609.07228(2016)

2016 arXiv
[16]

Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph.Proceedings of the VLDB Endowment12, 5 (2019), 461–474. Data acccessed at: https://github. com/ZJULearning/nsg

2019
[17]

Siddharth Gollapudi, Ravishankar Krishnaswamy, Kirankumar Shiragur, and Harsh Wardhan. 2025. Sort Before You Prune: Improved Worst-Case Guaran- tees of the DiskANN Family of Graphs. InProceedings of the 42nd International Conference on Machine Learning (ICML)

2025
[18]

Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. 2026. The Road to the Closest Point is Paved by Good Neighbors. InProceedings of the 9th Symposium on Simplicity in Algorithms (SOSA)

2026
[19]

Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. InIEEE Conference on Computer Vision and Pattern Recognition (CVPR)

2016
[20]

Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC). 604–613

1998
[21]

Piotr Indyk and Haike Xu. 2023. Worst-case Performance of Popular Approxi- mate Nearest Neighbor Search Implementations: Guarantees and Limitations. In Advances in Neural Information Processing Systems 36 (NeurIPS)

2023
[22]

Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search.IEEE Transactions on Pattern Analysis and Machine Intelligence33, 1 (2011), 117–128

2011
[23]

Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs.IEEE Transactions on Big Data7, 03 (2021), 535–547

2021
[24]

1990.The Computational Complexity of Machine Learning

Michael J Kearns. 1990.The Computational Complexity of Machine Learning. MIT Press, London, England

1990
[25]

Sanjeev Khanna, Ashwin Padaki, and Erik Waingarten. 2026. Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. InProceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

2026
[26]

Jon Kleinberg. 2000. The small-world phenomenon: An algorithmic perspective. InProceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). 163–170

2000
[27]

Robert Krauthgamer and James R Lee. 2004. Navigating nets: simple algorithms for proximity search.. InProceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

2004
[28]

Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. 2024. The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search.IEEE Data Eng. Bull.48, 3 (2024), 20–42

2024
[29]

Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi- probe LSH: efficient indexing for high-dimensional similarity search. InProceed- ings of the 33rd International Conference on Very Large Data Bases (VLDB)

2007
[30]

Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov
[31]

Malkov and D

Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence42, 4 (2020), 824– 836

2020
[32]

Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algo- rithms. InProceedings of the 29th ACM SIGPLAN Annual ...

2024
[33]

Stanley Milgram. 1967. The small world problem.Psychology today2, 1 (1967), 60–67

1967
[34]

G. Navarro. 1999. Searching in metric spaces by spatial approximation. In 6th International Symposium on String Processing and Information Retrieval. 5th International Workshop on Groupware

1999
[35]

Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proceeding of the ACM on Management of Data1, 1 (2023)

2023
[36]

Harsha Vardhan Simhadri, Martin Aumüller, Matthijs Douze, Dmitry Baranchuk, Amir Ingber, Edo Liberty, George Williams, Ben Landrum, Magdalen Dobson Manohar, Mazin Karjikar, Laxman Dhulipala, Meng Chen, Yue Chen, Rui Ma, Kai Zhang, Yuzheng Cai, Jiayang Shi, Weiguo Zheng, Yizhuo...

2026
[37]

Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Kr- ishnaswamny, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang
[38]

Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Kr- ishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node. InAdvances in Neural Information Processing Systems 32 (NeurIPS)

2019
[39]

Jeffrey Travers and Stanley Milgram. 1977. An Experimental Study of the Small World Problem. InSocial Networks. Academic Press, 179–197. Almost Navigable Graphs A ALGORITHMS In this section, we present pseudocode for the various algorithms used for the experimental analysis pr...

1977
[2014]

Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems45 (2014), 61–68

2014
[2022]

InProceedings of the NeurIPS 2021 Competitions and Demon- strations Track

Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Pratyush Avi and Christopher Musco Neighbor Search. InProceedings of the NeurIPS 2021 Competitions and Demon- strations Track

2021
[2026]

InProceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Efficiently Constructing Sparse Navigable Graphs. InProceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [13]

Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2024. Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits. InAdvances in Neural Information Processing Systems 37 (NeurIPS)

2024

[2] [1]

Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2025. Distance Adaptive Beam Search for Provably Accu- rate Graph-Based Nearest Neighbor Search. InAdvances in Neural Information Processing Systems 38 (NeurIPS)

2025

[3] [2]

Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.Commun. ACM51, 1 (2008), 117–122

2008

[4] [3]

Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. InAdvances in Neural Information Processing Systems 28 (NeurIPS)

2015

[5] [4]

Alexandr Andoni, Ilya Razenshteyn, and Negev Shekel Nosatzki. 2017. LSH Forest: Practical Algorithms Made Theoretical. InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 67–78

2017

[6] [5]

Sunil Arya and David M. Mount. 1993. Approximate nearest neighbor queries in fixed dimensions. InProceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

1993

[7] [6]

Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems87 (2020). Code available at https://github.com/erikbern/ann- benchmarks

2020

[8] [7]

Mayank Bawa, Tyson Condie, and Prasanna Ganesan. 2005. LSH forest: self- tuning indexes for similarity search. InProceedings of the 14th International Conference on World Wide Web

2005