Pith. sign in

REVIEW 3 major objections 3 minor 2 cited by

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search

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

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

Pith's one-line read The paper proves that a distance-based stopping rule — keep expanding until k discovered points are within a factor 1+γ of the current node — turns beam search on navigable graphs into a method with guaranteed approximate nearest-neighbor…

desk verdict A clean, useful theorem about beam-search termination on navigable graphs, with an experimental section that overclaims by extending the guarantee to heuristic graphs where navigability is never checked. read the letter →

arxiv 2505.15636 v1 pith:TSZMRN2E submitted 2025-05-21 cs.IR cs.DBcs.DScs.LG

Yousef Al-Jazzazi , Haya Diwan , Jinrui Gou , Cameron Musco , Christopher Musco , Torsten Suel This is my paper · ORCID
classification cs.IRcs.DBcs.DScs.LG
keywords nearestneighborsearchgraph-basedANNbeamadaptiveterminationnavigablegraphsapproximationguaranteesHNSWVamana
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

Graph-based nearest neighbor search finds close points by walking a prebuilt graph, and its standard engine—beam search—stops when a fixed beam width of candidates has been checked. This paper argues that the beam width is the wrong thing to terminate on, and replaces it with a distance-based rule: keep expanding until k already-discovered points are within a factor $1+\gamma$ of the node about to be expanded. It proves that on any navigable graph (where every point has a neighbor strictly closer to any target), this Adaptive Beam Search returns a set whose kth member is within a factor $2/\gamma$ of every unreturned point; setting $\gamma=2$ gives the exact k nearest neighbors. Standard beam search is shown to have no comparable guarantee on navigable graphs, and in experiments on both constructed navigable graphs and common heuristic graphs, the distance-based rule consistently matches or beats beam search, typically using 10–50% fewer distance computations at the same recall.

What carries the argument

The load-bearing object is the graph property the paper calls navigability: for every ordered pair of distinct points $x,y$, some out-neighbor $z$ of $x$ satisfies $d(z,y)<d(x,y)$, which guarantees a strictly distance-decreasing path to any target. The method's new ingredient is stopping condition (3): terminate when $k$ discovered points $j_1,\ldots,j_k$ satisfy $(1+\gamma)d(q,j_i)\le d(q,x)$ for the node $x$ about to be expanded, replacing the beam-width condition (2). In the proof, navigability is what converts the assumption that an undiscovered point $z$ is close to $q$ into the existence of a discovered-but-unexpanded node $w$ on a monotone path from the expanded farthest returned point to $z$; the triangle inequality then forces $d(q,w)<(1+\gamma)d(q,\tilde{x})$, contradicting the stopping rule.

What would settle it

Run Adaptive Beam Search with $\gamma=2$ on a small graph exhaustively verified to satisfy Definition 1 with unique pairwise distances; if some query $q$ returns a set $B$ while a point $v\notin B$ satisfies $d(q,v)<\max_{j\in B}d(q,j)$, Theorem 1 is false. To test the empirical claim instead, compare tuned parameters on a heuristic graph and look for matched-recall settings where standard beam search uses fewer distance computations than Adaptive Beam Search.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any metric $d$, any graph $G$ that is navigable under $d$, and any query $q$, Adaptive Beam Search with parameter $0<\gamma\le2$ returns a set $B$ of $k$ points such that every point outside $B$ has distance at least $\frac{\gamma}{2}\max_{j\in B} d(q,j)$ from $q$. Because $\gamma\le2$, this means no unreturned point is more than $2/\gamma$ times farther from $q$ than the worst returned point, and when $\gamma=2$ the returned set is exactly the k nearest neighbors. The proof shows the farthest returned point must have been expanded, and then uses navigability to rule out any undiscovered point that is too close: a closer undiscovered point would force an unexpanded node on its decreasing-distance path into a forbidden ball around $q$. The paper also proves the converse contrast: standard beam search with width $b\le n-3$ cannot achieve any finite approximation factor on all navigable graphs, even in two-dimensional Euclidean space.

Load-bearing premise

The proof hinges on the search graph having the navigability property — from every point, some outgoing edge goes strictly closer to any chosen target — and on tie-breaking to make all pairwise distances unique; the practical HNSW, Vamana, NSG, and EFANNA graphs are not proven to have this property, so those experiments rest on the assumption that they are approximately navigable.

Editorial extensions

If this is right

  • On any navigable graph, $\gamma$ gives a clean accuracy–cost dial: $\gamma=2$ solves k-nearest neighbors exactly, and smaller $\gamma$ returns a $2/\gamma$-approximation with fewer distance computations.
  • Because only the stopping condition changes, existing graph-based search code can adopt the method by changing a few lines, with the same traversal order and graph construction.
  • Standard beam search is inherently different: for any finite approximation factor, there is a navigable graph in the plane where beam width $b\le n-3$ returns a point arbitrarily far from the query, so no analogous theorem can hold for it.
  • On heuristic graphs used in practice (HNSW, Vamana, NSG, EFANNA), matched-recall comparisons across datasets and $k$ values show Adaptive Beam Search using fewer distance computations, typically 10–50% fewer, with gains that vary by dataset and $k$.
  • The distance-based rule adapts per query: the histogram of distance computations is flatter than beam search's, using fewer computations on easy queries and more on hard ones, which is the mechanism behind the average gain.

Reading between the lines

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

  • Beyond the paper, the theory suggests a cheap diagnostic for practical graphs: record, for each expanded node, whether one of its out-neighbors ever lies on the decreasing-distance path to the eventual nearest neighbor; regions where this never happens are where the formal guarantee cannot be expected to hold.
  • Because Theorem 1 uses only the metric axioms, the same proof would apply to non-Euclidean distances such as Chamfer distance; the experiments are Euclidean only, so this transfer is an untested inference.
  • The near-tie between Adaptive Beam Search and the hybrid rule that also keeps a beam width suggests the distance-based slack, not the width parameter, is the main driver of the observed speedup; a focused ablation varying only the slack function would test this directly.
  • A worst-case runtime bound is still missing, and one route is to bound the number of decreasing-distance hops or the out-degree required for navigability under curvature or doubling-dimension assumptions; the paper's guarantee is about accuracy alone.
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.

Referee Report

3 major / 3 minor

Summary. The paper studies graph-based approximate nearest neighbor search and proposes replacing the fixed beam-width termination rule of standard beam search with a distance-based rule ('Adaptive Beam Search' with a slack parameter gamma). The main theoretical result, Theorem 1, states that on any graph satisfying the paper's Definition 1 of navigability, Adaptive Beam Search with 0<gamma<=2 returns k points B such that every point outside B is at distance at least (gamma/2) max_{j in B} d(q,j) from the query; in particular gamma=2 yields an exact k-nearest-neighbor answer. The proof uses navigability to obtain a monotonically decreasing path from the kth-best returned point to any undiscovered point, and a triangle-inequality argument to show that an undiscovered point too close to the query would force an unexpanded node to violate the termination condition. The paper also proves (Claim 6) that ordinary beam search with beam width b<=n-3 cannot have any finite approximation guarantee on navigable graphs. Experiments compare the new termination rule with standard beam search on six datasets, on both pruned navigable graphs and heuristic HNSW, Vamana, NSG, and EFANNA graphs, reporting reductions in distance computations for a given recall. The authors conclude that Adaptive Beam Search is a practical drop-in replacement for standard beam search.

Significance. If sound, Theorem 1 is a meaningful step: it is, to my knowledge, the first formal connection between a navigability-type graph property and the accuracy of a beam-search-style traversal, and it separates the accuracy of the stopping rule from the graph-construction heuristic. The result is clean and parameter-free in the sense that the guarantee depends only on gamma and the metric axioms; it does not rely on fitted constants. The negative result for standard beam search is also valuable because it explains why the distance-based rule is needed. The experimental study is extensive, with public datasets, detailed hyperparameters, and pseudocode that make the method easy to reimplement. The main caveats are that the formal guarantee applies only to navigable graphs, and the paper's empirical validation of that hypothesis is incomplete; these issues are local and fixable, so the contribution is publishable after revision.

major comments (3)
  1. [Section 4, Claim 3 and Algorithm 1] In Algorithm 1, D includes the node x that was just popped (it is inserted into D on line 2 or line 7 before being popped). Under this reading, stopping condition (3) is satisfied for k=1 and d(q,tilde x)=0 when xterm=tilde x itself, so the statement in Claim 3 that 'tilde x is guaranteed to have been expanded' is false; the footnote in the proof does not rule out xterm=tilde x, since uniqueness only excludes another database point at distance 0. The theorem's conclusion still holds in this case, so the gap is patchable, but the proof as written is incomplete. The same convention makes conditions (1) and (2) trivially true at the first pop when b=k=1, contradicting the claim in Section 3.2 that beam search with b=k is identical to greedy search; the definitions should either count only discovered nodes other than the current candidate or treat the zero-distance case separately.
  2. [Section 5.2 and Section B.2] The 'truly navigable' graphs used in Figure 3 are produced by Algorithm 4, and while the pruning rule is intended to preserve Definition 1, the paper reports no check that the pruned graphs actually satisfy Definition 1 on the subsampled datasets. Since Theorem 1 predicts that gamma=2 gives recall exactly 1.0 on any navigable graph, the authors should report the gamma=2 recall value for these graphs; its absence leaves the experimental validation of the theorem's hypothesis indirect and would also serve as a falsifiable test of the implementation.
  3. [Section 5, 'Results for Heuristic Graphs', and abstract] The practical claim that Adaptive Beam Search is a 'drop-in replacement' for standard beam search is supported for HNSW, Vamana, NSG, and EFANNA graphs only empirically; for none of these constructions is Definition 1 verified, and 'approximately navigable' is never formalized or tested. Consequently the title's 'provably accurate' and the abstract's guarantee should be explicitly scoped to navigable graphs, and the heuristic-graph section should not be read as covered by Theorem 1. At minimum, the authors should state this limitation prominently and, if possible, test whether the heuristic graphs satisfy or approximately satisfy Definition 1 (e.g., by measuring the fraction of pairs violating it).
minor comments (3)
  1. [Section 5.2, Figure 3] The text says the navigable-graph experiments use SIFT, DEEP256, and MNIST, while Figure 3's caption and Table 2 refer to DEEP96; these should be reconciled.
  2. [Section B.3] There are typos in the computational-resources and license paragraphs: '32GM' should be '32GB' and 'MNSIST' should be 'MNIST'; the Table 3 caption also contains 'a dn' for 'and'.
  3. [Abstract, Section 1, and Section C.2] The abstract and Section 1 say Adaptive Beam Search 'universally outperforms' classic beam search, but Section C.2 reports that for GIST with k=1, standard beam search performs marginally better; the wording should be softened to reflect the empirical exception.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: Theorem 1 is proven from Definition 1 and metric axioms, with the only self-citations supplying navigable graph constructions that are not load-bearing for the theorem.

full rationale

The paper's central claim is a conditional theorem: if the search graph is navigable (Definition 1), then Adaptive Beam Search with parameter gamma returns a set B for which every excluded point is at distance at least (gamma/2) times the maximum returned distance, with gamma=2 giving exact kNN. The proof is self-contained: it derives strong connectivity from navigability, establishes that the kth-best returned point must have been expanded (Claim 3), and then uses a monotone path from that point to any hypothetical undiscovered closer point to obtain a contradiction with the stopping threshold (Claim 4 and the triangle-inequality argument). No fitted constant, no empirical quantity, and no prior result is substituted for any step of this derivation. The stopping condition (3) is defined with parameter gamma, and the approximation factor 2/gamma follows from the proof rather than being imposed by the algorithm, so there is no self-definitional or fitted-input-called-prediction circularity. The paper does rely on the authors' prior work [12] in two auxiliary places: to cite that navigable graphs exist for any metric, and to construct the 'truly navigable' graphs used in Section 5.2. This self-citation is not load-bearing for Theorem 1, which is conditional on navigability regardless of whether such graphs exist; [12] is used for experiments and to contrast with alpha-shortcut reachable graphs. The paper also acknowledges that the Adaptive Beam Search stopping rule was previously suggested as an early-stopping heuristic [40, 39], so the algorithmic idea is not presented as entirely novel. The main caveat is not circularity but an assumption gap: Theorem 1 applies only to graphs satisfying Definition 1, while the headline experiments on HNSW, Vamana, NSG, and EFANNA use 'approximately navigable' graphs for which Definition 1 is neither proven nor empirically verified, so the strong guarantee does not formally cover those practical graphs. That gap weakens the practical force of the 'provably accurate' claim but does not make the derivation circular. Overall, the derivation chain is independent and the theorem is a genuine conditional result; the minor use of a same-author citation for graph construction and background motivates a score of 1 rather than 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The theory pulls in only standard metric axioms, unique-distance tie-breaking, and the navigability assumption. The empirical conclusions additionally assume that heuristic graphs are approximately navigable and depend on several tuned graph-construction hyperparameters. No parameters are fitted to derive Theorem 1.

free parameters (4)
  • gamma (Adaptive Beam Search slack) = tuned per dataset/recall target, 0 < gamma <= 2
    Algorithm parameter in Eq. (3) controlling the distance threshold. Theorem 1 holds for any gamma in (0,2], so it is not fitted to make the proof work, but the experimental comparison tunes it to equalize recall against beam width b.
  • beam width b (baseline) = tuned per dataset/recall target
    Standard beam search width in Eq. (2); comparison curves are generated by sweeping and tuning b to match the recall levels of Adaptive Beam Search.
  • m and random edges for navigable graph construction = m = floor(sqrt(3 n ln n)) and ceil(3 n ln n / m) random edges (Section B.2)
    From [12], a design choice rather than a fit; determines sparsity of experimental navigable graphs and therefore the empirical curves in Figure 3.
  • Graph construction hyperparameters (HNSW M/efC, NSG L/R, EFANNA K/L/iter/S, Vamana alpha, etc.) = Table 3; some chosen by testing on the benchmark query sets
    Affects approximate navigability of the heuristic graphs used in Figures 4, 7, 8. For HNSW on MNIST/DEEP256 and NSG/EFANNA on several datasets the paper selects among tested values using the benchmark itself.
assumptions (4)
  • standard math d is a metric satisfying the triangle inequality
    Used throughout the Theorem 1 proof, specifically in the final triangle inequality chain around Eq. (5).
  • domain assumption All database distances are unique, ensured by tie-breaking on node id
    Used to guarantee strict inequality in Claim 3 and to make monotone paths well-defined, as stated in Section 2 and used in the Theorem 1 proof.
  • domain assumption Search graph G is navigable under d (Definition 1)
    The core premise of Theorem 1; all proof claims about existence of monotone paths from expanded nodes use it.
  • domain assumption Heuristic graphs (HNSW, Vamana, NSG, EFANNA) are approximately navigable in practice
    The empirical transfer of Theorem 1 to practical graphs assumes these constructions behave like navigable graphs; the paper does not prove navigability for them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/TSZMRN2E

@misc{pith2026250515636,
  author       = {Pith},
  title        = {Pith review of: Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TSZMRN2E}},
  note         = {Machine review of arXiv:2505.15636}
}
read the original abstract

Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.

Figures

Figures reproduced from arXiv: 2505.15636 by the authors.

Figure 1
Figure 1. Histograms for the number of distance computations performed by standard beam search [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Visualization of the proof of Theorem 1. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Navigable Graphs: Comparison of generalized beam search termination conditions on navigable graphs across three datasets: SIFT1M, DEEP96, and MNIST (columns), with k = 1, and k = 10 (rows). Adaptive Beam Search consistently outperforms standard beam search, while the alternative Adaptive Beam Search V2 underperforms both by a significant margin. Note that for k = 1, Adaptive Beam Search and Adaptive Beam Search V2 a… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Heuristic Graphs: Comparison of generalized beam search termination methods on heuristic graphs produced by NSG, Vamana, EFANNA, and HNSW (rows), for k = 10 with 3 datasets: SIFT1M, DEEP256, and MNIST (columns). Adaptive beam search consistently outperforms standard be…
Figure 5
Figure 5. Figure 5: Example showing that standard beam search fails to find a nearest neighbor in a navigable [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Comparison of generalized beam search termination conditions on navigable graphs across [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]
Figure 7
Figure 7. Figure 7: Comparison of generalized beam search termination methods on HNSW graphs with [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. Figure 8: Comparison of generalized beam search termination methods on HNSW graphs across [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: Histograms for the number of distance computations performed by Adaptive Beam Search [PITH_FULL_IMAGE:figures/full_fig_p021_9.png]
Figure 10
Figure 10. Figure 10: Evaluation of the Hybrid Beam Search termination rule from [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. HNSW with Accuracy Guarantees Using Graph Spanners

    cs.DB 2026-07 unverdicted novelty 7.0 of 10

    A tiered Certify-then-Rectify system for HNSW that certifies approximate results statistically and falls back to exact recovery by treating the graph as a spanner whose stretch is bounded via extreme value theory.

  2. Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

    cs.DS 2025-07 conditional novelty 7.0 of 10

    Sparsest navigable graph construction is approximation-equivalent to Set Cover, yielding a (ln n+1)-approximation, o(ln n)-hardness, fast bicriteria algorithms, and an Ω(n squared) query lower bound.

Reference graph

Works this paper leans on

60 extracted references · 53 canonical work pages · cited by 2 Pith papers

  1. [1]

    Raykar, Kirankumar Shiragur, and Haike Xu

    Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi, Vikas C. Raykar, Kirankumar Shiragur, and Haike Xu. Graph-based algorithms for diverse similarity search. arXiv:2502.13336, 2025

    arXiv 2025

  2. [2]

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.Commun

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

    work page 2008

  3. [3]

    Practical and optimal LSH for angular distance

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

    work page 2015

  4. [4]

    Nguyen, and Ilya Razenshteyn

    Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. 10

    work page 2014

  5. [5]

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

    work page 1993

  6. [6]

    ANN-Benchmarks: A bench- marking tool for approximate nearest neighbor algorithms.Information Systems, 87, 2020

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-Benchmarks: A bench- marking tool for approximate nearest neighbor algorithms.Information Systems, 87, 2020. Data accessed athttps://github.com/erikbern/ann-benchmarks

    work page 2020

  7. [7]

    Efficient indexing of billion-scale datasets of deep descriptors

    Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2055–2063, 2016. Data accessed at https://github.com/erikbern/ ann-benchmarks

    work page 2016

  8. [8]

    Cover trees for nearest neighbor

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

    work page 2006

Show all 60 references
  1. [9]

    Springer, 2024

    Sebastian Bruch.Foundations of Vector Retrieval. Springer, 2024

    2024

  2. [10]

    Kernel density estimation through density constrained near neighbor search

    Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. InProceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 172–183, 2020

    2020

  3. [11]

    BERT: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Langua...

    2019

  4. [12]

    Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits

    Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits. InAdvances in Neural Information Processing Systems 37 (NeurIPS), 2024

    2024

  5. [13]

    SPLADE: sparse lexical and expansion model for first stage ranking

    Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. SPLADE: sparse lexical and expansion model for first stage ranking. InProceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021

    2021

  6. [14]

    EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph.arXiv:1609.07228, 2016

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

    2016 arXiv

  7. [15]

    Fast approximate nearest neighbor search with the navigating spreading-out graph.Proceedings of the VLDB Endowment, 12(5):461–474,

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph.Proceedings of the VLDB Endowment, 12(5):461–474,

  8. [16]

    Fast k nearest neighbor search using GPU

    Vincent Garcia, Eric Debreuve, and Michel Barlaud. Fast k nearest neighbor search using GPU. InIEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2008

    2008

  9. [17]

    Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters

    Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Beg- wani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. Filtered-DiskANN: Graph algorithms for approximate nearest neighb...

    2023

  10. [18]

    Approximate nearest neighbors: towards removing the curse of dimensionality

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

    1998

  11. [19]

    Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations

    Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. InAdvances in Neural Information Processing Systems 36 (NeurIPS), 2023

    2023

  12. [20]

    MUVERA: Multi-vector retrieval via fixed dimensional encoding

    Rajesh Jayaram, Laxman Dhulipala, Majid Hadian, Jason Lee, and Vahab Mirrokni. MUVERA: Multi-vector retrieval via fixed dimensional encoding. InAdvances in Neural Information Processing Systems 37 (NeurIPS), 2024. 11

    2024

  13. [21]

    Product quantization for nearest neighbor search.IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011

    Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search.IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011. Data accessed athttp://corpus-texmex.irisa.fr

    2011

  14. [22]

    Billion-scale similarity search with GPUs

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(03):535–547, 2021

    2021

  15. [23]

    DEANN: Speeding up kernel-density estimation using approximate nearest neighbor search

    Matti Karppa, Martin Aumüller, and Rasmus Pagh. DEANN: Speeding up kernel-density estimation using approximate nearest neighbor search. InProceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151, pages 3108–3137, 2022

    2022

  16. [24]

    Reformer: The efficient transformer

    Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020

    2020

  17. [25]

    Kleinberg

    Jon M. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. InProceed- ings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997

    1997

  18. [26]

    Kleinberg

    Jon M. Kleinberg. Navigation in a small world.Nature, 406(6798):845–845, 2000

    2000

  19. [27]

    Kleinberg

    Jon M. Kleinberg. The small-world phenomenon: an algorithmic perspective. InProceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 2000

    2000

  20. [28]

    The diskann library: Graph-based indices for fast, fresh and filtered vector search.IEEE Data Eng

    Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. The diskann library: Graph-based indices for fast, fresh and filtered vector search.IEEE Data Eng. Bull., 48(3):20–42, 2024

    2024

  21. [29]

    Efficient search for approximate nearest neighbor in high dimensional spaces

    Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. InProceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998

    1998

  22. [30]

    Graph-based time-space trade-offs for approximate near neighbors

    Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. In Proceedings of the 34th Annual Symposium on Computational Geometry (SOCG), 2018

    2018

  23. [31]

    Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998

    Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998. Data accessed athttps://github.com/erikbern/ann-benchmarks

    1998

  24. [32]

    Retrieval-augmented generation for knowledge-intensive NLP tasks

    Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. InAdvances in Neural ...

    2020

  25. [33]

    Improving approximate nearest neighbor search through learned adaptive early termination

    Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. InProceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 2539–2554, 2020

    2020

  26. [34]

    Jinfeng Li, Xiao Yan, Jian Zhang, An Xu, James Cheng, Jie Liu, Kelvin K. W. Ng, and Ti-chung Cheng. A general and efficient querying method for learning to hash. InProceedings of the 2018 ACM SIGMOD International Conference on Management of Data, pages 1333–1347, 2018. Data ac...

    2018

  27. [35]

    ROSE: Robust caches for amazon product search

    Chen Luo, Vihan Lakshman, Anshumali Shrivastava, Tianyu Cao, Sreyashi Nag, Rahul Goutam, Hanqing Lu, Yiwei Song, and Bing Yin. ROSE: Robust caches for amazon product search. https://www.amazon.science/publications/rose-robust-caches-for-amazon-product-search, 2022

    2022

  28. [36]

    Multi-probe LSH: efficient indexing for high-dimensional similarity search

    Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for high-dimensional similarity search. InProceedings of the 33rd International Conference on Very Large Data Bases, pages 950–961, 2007

    2007

  29. [37]

    Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems, 45:61–68, 2014

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems, 45:61–68, 2014. 12

    2014

  30. [38]

    Malkov and D

    Yury. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020

    2020

  31. [39]

    Blelloch

    Magdalen Dobson Manohar, Taekseung Kim, and Guy E. Blelloch. Range retrieval with graph-based indices.arXiv:2502.13245, 2025

    2025 arXiv

  32. [40]

    ParlayANN: Scalable and deterministic parallel graph- based approximate nearest neighbor search algorithms

    Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Har- sha Vardhan Simhadri, and Yihan Sun. ParlayANN: Scalable and deterministic parallel graph- based approximate nearest neighbor search algorithms. InProceedings of the 29th ACM SIGPLAN Annual Sympo...

    2024

  33. [41]

    Augmented language models: a survey.Transactions on Machine Learning Research, 2023

    Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ramakanth Pasunuru, Roberta Raileanu, Baptiste Roziere, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, Edouard Grave, Yann LeCun, and Thomas Scialom. Augmented language models: a survey.Transactions on Mac...

    2023

  34. [42]

    The small world problem.Psychology Today, 2(1):60–67, 1967

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

    1967

  35. [43]

    An introduction to neural information retrieval.Foundations and Trends® in Information Retrieval, 13(1):1–126, 2018

    Bhaskar Mitra, Nick Craswell, et al. An introduction to neural information retrieval.Foundations and Trends® in Information Retrieval, 13(1):1–126, 2018

    2018

  36. [44]

    Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data.IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11):2227–2240, 2014

    2014

  37. [45]

    Modeling the shape of the scene: A holistic representation of the spatial envelope.International journal of computer vision, 42:145–175, 2001

    Aude Oliva and Antonio Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope.International journal of computer vision, 42:145–175, 2001. Data accessed athttps://github.com/erikbern/ann-benchmarks

    2001

  38. [46]

    Papadopoulos and Yannis Manolopoulos.Nearest Neighbor Search:: A Database Perspective

    Apostolos N. Papadopoulos and Yannis Manolopoulos.Nearest Neighbor Search:: A Database Perspective. Springer Science & Business Media, 2005

    2005

  39. [47]

    Jeffrey Pennington, Richard Socher, and Christopher D. Manning. GloVe: Global vectors for word representation. InProceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014. Data accessed at https: //github.com/erikbern...

    2014

  40. [48]

    Graph-based nearest neighbor search: From practice to theory

    Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. InProceedings of the 37th International Conference on Machine Learning (ICML), 2020

    2020

  41. [49]

    Results of the Big ANN: NeurIPS’23 competition.arXiv:2409.17424, 2024

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

    2024 arXiv

  42. [50]

    Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search

    Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the NeurIPS’21 challenge on billion-scale ap...

    2021

  43. [51]

    FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search.arXiv:2105.09613, 2021

    Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search.arXiv:2105.09613, 2021

    2021 arXiv

  44. [52]

    Scalable and sustainable deep learning via randomized hashing

    Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. InProceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 445–454, 2017. 13

    2017

  45. [53]

    DiskANN: Fast accurate billion-point nearest neighbor search on a single node

    Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Har- sha Vardhan Simhadri. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. InAdvances in Neural Information Processing Systems 32 (NeurIPS), 2019

    2019

  46. [54]

    Gonçalves, Zanoni Dias, and Ricardo da S

    Javier Vargas Muñoz, Marcos A. Gonçalves, Zanoni Dias, and Ricardo da S. Torres. Hierar- chical clustering-based graphs for large scale approximate nearest neighbor search.Pattern Recognition, 96, 2019

    2019

  47. [55]

    Bennett, Junaid Ahmed, and Arnold Overwijk

    Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. InProceedings of the 9th International Conference on Learning Representations (...

    2021

  48. [56]

    Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri

    Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. In-place updates of a graph index for streaming approximate nearest neighbor search.arXiv:2502.13826, 2025

    2025 arXiv

  49. [57]

    A bi-metric framework for fast similarity search

    Haike Xu, Sandeep Silwal, and Piotr Indyk. A bi-metric framework for fast similarity search. arXiv:2406.02891, 2024

    2024 arXiv

  50. [58]

    GraSP: Optimizing graph-based nearest neighbor search with subgraph sampling and pruning

    Minjia Zhang, Wenhan Wang, and Yuxiong He. GraSP: Optimizing graph-based nearest neighbor search with subgraph sampling and pruning. InProceedings of the 15th International Conference on Web Search and Data Mining (WSDM), pages 1395–1405, 2022

    2022

  51. [59]

    distance based

    Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces.Proceedings of the VLDB Endowment, 16(8):1979–1991, 2023. 14 A Additional Proofs A.1 Nonexistence of Sparseα-S...

    1979

  52. [2019]

    Data acccessed at:https://github.com/ZJULearning/nsg

Pith tools

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