Pith. sign in

REVIEW 4 major objections 6 minor 33 references

Three Algorithms for Merging Hierarchical Navigable Small World Graphs

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

Pith's one-line read The paper claims that merging two HNSW graphs can be done with up to 70 percent fewer distance computations by reusing candidate sets from nearby vertices, and that the intra-graph traversal variant IGTM is faster than the cross-graph…

desk verdict A clearly described, genuinely new set of HNSW merge heuristics, but the 70% headline rests on a single best-of-sweep run and is not yet supported by the experiment as reported. read the letter →

arxiv 2505.16064 v1 pith:ROJ35MVP submitted 2025-05-21 cs.DS

classification cs.DS
keywords approximatenearestneighborsearchhierarchicalnavigablesmallworldgraphmergingvectordatabaseslocalSIFT1Minformationretrieval
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

The paper asks how to combine two separately built hierarchical navigable small world (HNSW) indexes, a task that arises when vector databases merge partitions, ingest incrementally, or compact indexes whose deleted entries have accumulated. It proposes three merge algorithms—Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM)—organized around four steps: picking the next vertex, collecting candidate neighbors from both graphs, constructing the neighborhood, and carrying information to the next iteration. The central empirical claim is that IGTM and CGTM reduce the number of distance computations by up to 70 percent relative to naive or insertion-based merging while keeping recall@5 essentially unchanged, and that IGTM is faster than CGTM, which the paper says was unexpected. If that claim holds, merging becomes cheap enough to run routinely instead of occasionally rebuilding an index.

What carries the argument

The load-bearing mechanism is candidate-set inheritance. After building the neighborhood of a vertex v*, the algorithm keeps the M closest candidates found for v* and uses them to seed a LocalSearch for the next vertex, which is chosen to be a nearby unprocessed vertex rather than a random one; only when that walk stalls does it fall back to a full HNSW-Search, a hierarchical search that descends from the top layer to the target layer. CGTM applies the same idea while maintaining inherited candidate sets from both input graphs and selecting the next vertex from either one. The shared abstraction is an iterative loop whose four steps—processing vertex selection, candidate collection, neighborhood construction, and information propagation—are each replaceable, with relative-neighborhood-graph construction used in the experiments to decide which candidate edges survive.

What would settle it

Run IGTM on a dataset in which consecutive vertices in the processing order have disjoint neighborhoods—for example, two interleaved well-separated clusters so the traversal alternates between them—and measure both distance computations and recall@5 against the SIFT1M result. If the cost reduction drops well below 70 percent or recall falls materially relative to naive merging, the locality assumption is falsified.

Watch

Extended reading notes

Core claim

The central discovery is that a merge does not need to run the full hierarchical search for every vertex. When consecutive vertices chosen for processing lie close together in the vector space, the candidate set built for one vertex is a good seed for a cheap single-layer LocalSearch on the next vertex; IGTM exploits this by walking within the same input graph, while CGTM walks across both graphs. The paper reports that this reuse cuts distance computations by roughly 70 percent for IGTM compared with naive graph merge and simple insertion, and by roughly 60 percent for CGTM, with recall slightly better than simple insertion using construction effort 24 and close to the recall of the most expensive naive merge. It also reports that intra-graph walking beats cross-graph walking, because CGTM's extra step of choosing the next vertex from either graph costs more than it saves.

Load-bearing premise

The speedup rests on the untested assumption that vertices processed one after another have similar neighbor sets, so the candidate list from one vertex can seed a cheap local search for the next; if neighborhoods are not coherent, the algorithm falls back to expensive full searches and the savings disappear.

Editorial extensions

If this is right

  • Merging two 500k-vector HNSW indexes can be done with up to 70 percent fewer distance computations than insertion-based merging, making routine consolidation of distributed or partitioned indexes practical.
  • Intra-graph traversal (IGTM) is the better default: it is about 20 percent cheaper than cross-graph traversal (CGTM) at the same recall, so the extra flexibility of choosing the next vertex from either graph does not pay for itself.
  • Because the four merge steps are pluggable, the same traversal machinery can be paired with different neighborhood construction rules without changing the search strategy.
  • At a fixed search expansion factor L, the number of distance computations during search is nearly the same across all merged graphs, so recall at fixed L is a direct measure of merge quality.
  • Deleting vertices during the processing-vertex-selection step would let these algorithms compact an index by merging it with a filtered copy, avoiding a full rebuild.

Reading between the lines

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

  • Editorial inference: the 70 percent speedup is a property of the data's spatial coherence, not of HNSW itself; on datasets where nearby vertices in the traversal order do not share neighbors, the algorithm should degrade toward naive-merge cost.
  • Editorial inference: the same candidate-seeding trick could turn batch insertion of new points into a merge-like operation, potentially making incremental index updates sub-rebuild in cost.
  • Editorial inference: an adaptive policy that watches LocalSearch quality and decides when to trigger a full HNSW-Search jump could remove the need to hand-tune jump_ef and M across datasets.
  • Editorial inference: since the merge is built on the two generic primitives LocalSearch and HNSW-Search, the framework should transfer to other layered navigable-graph indexes, though the paper demonstrates it only for HNSW.
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

4 major / 6 minor

Summary. The paper addresses the problem of merging two HNSW graphs, motivated by distributed vector databases, incremental indexing, and compaction. It proposes three merge algorithms: Naive Graph Merge (NGM), which performs a full HNSW search per vertex; Intra Graph Traversal Merge (IGTM), which reuses the previous vertex's candidate set and a cheap LocalSearch for nearby vertices; and Cross Graph Traversal Merge (CGTM), which applies the same idea while allowing the next vertex to be selected from either input graph. The algorithms are described within a four-step framework (processing vertex selection, candidate collection, neighborhood construction, information propagation). Experiments on SIFT1M (split into two 500k halves) compare merge distance counts and recall@5 at several search expansion factors L. The central claim is that IGTM and CGTM reduce merge distance computations by up to 70% compared with NGM and the simple insertion baseline SIGM while maintaining comparable search accuracy.

Significance. If the claimed savings hold, the paper makes a practically useful contribution: graph merging is a real operational bottleneck in HNSW-based systems, and a locality-aware traversal that avoids a full hierarchical search for every vertex is a plausible and interesting way to reduce merge cost. The paper is clearly structured, includes pseudocode for all algorithms, and points to a public GitHub implementation, which are strengths. However, the quantitative claims are supported only by a single dataset, a single run, and a best-of-sweep selection on the evaluation data; the 'comparable accuracy' wording is not rigorously defined. The algorithmic idea is promising but the empirical evidence as currently presented is not sufficient to establish the headline numbers, and the pseudocode has specification gaps (undefined parameters and entry points) that prevent exact reproduction.

major comments (4)
  1. [§5.2, Fig. 3 and abstract] The claim of 'up to 70% fewer distance computations while maintaining comparable search accuracy' is not supported by the reported data. At a fixed search L, the lowest-cost IGTM/CGTM configurations in Fig. 3 appear to have lower recall than NGM/SIGM; since Fig. 2 shows that search-phase distance counts are essentially equal for equal L, the recall deficit is a real accuracy loss rather than a runtime artifact. The paper should compare merge costs at matched recall levels (e.g., the recall achieved by NGM at a given L) or explicitly quantify the recall reduction and rephrase the claim. Without this, 'comparable' is undefined and the headline 70% figure is potentially misleading.
  2. [§5.1–§5.2, Fig. 3] The 70% figure is selected from a parameter sweep on the same data used for evaluation, and no repeated runs or error bars are reported. The algorithms contain randomized steps (random choice of v* in Algorithms 7–8 and randomized neighbor selection), so both merge distance count and recall@5 are random variables; a single run cannot establish the claimed 20% IGTM-over-CGTM advantage. The paper also does not state the number of queries used for the recall@5 average. Please report means and variances over multiple independent runs, and either use a validation set for parameter selection or clearly label the reported numbers as in-sample best cases.
  3. [§4.4–§4.5, Algorithms 7 and 8] The merge algorithms as written are not fully specified. Algorithm 7 line 15 uses 'next_step_ef' which does not appear in the algorithm's input list; Algorithm 7 line 8 and Algorithm 8 lines 8–9 call HNSW-Search with an entry point v0 that is not defined in the inputs or the surrounding text. In addition, line 1 of Algorithms 6, 7, and 8 reads 'Gb ← Ha.GetLayer(ℓ)' where Hb.GetLayer(ℓ) is clearly intended. These omissions make the pseudocode non-executable as presented and should be corrected by adding the missing parameters and entry-point definitions to the algorithm signatures and bodies.
  4. [§4.4, Algorithms 7–8] The efficiency of IGTM and CGTM rests on an unstated locality assumption: that the candidate set P b inherited from the previous vertex's LocalSearch (Algorithm 7, lines 11–14) still provides a good seed for the next vertex's search. This assumption is only validated on SIFT1M. The paper should either provide evidence on at least a second dataset or report a diagnostic that quantifies how often the inner while loop succeeds versus falls back to the expensive HNSW-Search path (the break at line 17). Without such evidence, the generality of the claimed savings is uncertain.
minor comments (6)
  1. [§2.2, Algorithm 2] The pseudocode loop 'for i = lmax down to ℓ' performs LocalSearch on the target layer twice; the text says the loop runs from lmax to ℓ+1. Align the pseudocode and the prose.
  2. [§4.3, Algorithm 6] The input list defines 'ventry' but the body uses 'vb_entry' and 'va_entry'; define these variables or remove the inconsistency.
  3. [§4.5, Algorithm 8] Lines 15 and 17 contain stray closing braces in the set definitions, and line 18 calls 'neighborhood construction' without passing the NeighborhoodConstruction parameter, unlike the corresponding call in Algorithm 7.
  4. [§5.1] The number of queries used to compute recall@5 is not stated. The text says 'averaged over all sequences of searches' but the query count is needed to assess the reliability of the reported recall values.
  5. [Fig. 2 and Fig. 3] The legends for IGTM and CGTM repeat similar marker shapes for many parameter configurations, making the figures difficult to read. Consider using distinct markers or plotting only the Pareto frontier of recall versus merge distance count.
  6. [§6] The related work on the Elastic join-set approach and Zhao et al.'s k-NN graph merge is described, but no experimental comparison is provided; a sentence justifying why direct comparison is left to future work would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central efficiency claim is an empirical benchmark result, not a derivation from fitted inputs or self-cited theorems.

full rationale

The paper's central claim—that IGTM and CGTM require up to 70% fewer distance computations while maintaining comparable recall—is an experimental comparison on the external SIFT1M benchmark against NGM and SIGM baselines. The merge algorithms are defined constructively in Algorithms 6-8, and the reported cost and recall are measured from the resulting merged graphs using Algorithm 2 and recall@5. No parameter is fitted to the target claim and then renamed as a prediction: the parameter sweep shown in Fig. 3 selects configurations, which raises evaluation robustness concerns (single dataset, no variance estimates), but that is post-hoc selection, not circular derivation. The self-citations ([23]-[25], [31]) are background references for NSW, LocalSearch, and HNSW implementations; the paper restates LocalSearch in Algorithm 1 and does not rely on an unverified self-cited uniqueness theorem or imported ansatz. The efficiency gain rests on an empirical locality assumption, explicitly acknowledged as such in the conclusion, so it is a falsifiable empirical claim rather than a definitional equivalence. The derivation chain is self-contained against an external benchmark.

Assumptions & free parameters 5 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. Its central claim depends on the locality assumption about HNSW neighborhoods and on the chosen parameter values, all validated on one dataset.

free parameters (5)
  • jump_ef = 20 or 64 (swept)
    Beam width for the HNSW-Search 'jump' phase; chosen from a grid to maximize recall/cost on SIFT1M.
  • local_ef = 5 or 10 (swept)
    Beam width for LocalSearch in the traversal phase; tuned on the same test data.
  • next_step_k = 3 (with some 5,10 in sweep)
    Number of candidate next vertices requested from LocalSearch to continue the traversal.
  • next_step_ef = 3 or 10 (swept)
    Beam width for the next-vertex LocalSearch; affects how far the traversal can jump.
  • M = 1,2,3,5,10,20 (swept)
    Number of closest candidates retained in P b between iterations.
assumptions (3)
  • domain assumption The number of distance computations is a valid proxy for merge runtime.
    Stated in Section 5.1 as the basis for comparing algorithms without implementation-dependent effects.
  • domain assumption Approximate candidates from HNSW-Search and LocalSearch are sufficient to reconstruct neighborhoods of comparable quality to exhaustive insertion.
    This is the core assumption of IGTM and CGTM; no proof is provided, only the SIFT1M experiment.
  • domain assumption SIFT1M is representative of ANN workloads in vector databases.
    The paper generalizes to production HNSW use without testing other datasets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Three Algorithms for Merging Hierarchical Navigable Small World Graphs." pith.science (2026). https://pith.science/paper/ROJ35MVP

@misc{pith2026250516064,
  author       = {Pith},
  title        = {Pith review of: Three Algorithms for Merging Hierarchical Navigable Small World Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ROJ35MVP}},
  note         = {Machine review of arXiv:2505.16064}
}
read the original abstract

This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection and candidate collection during the merge process. We conceptualize graph merging as an iterative process with four key steps: processing vertex selection, candidate collection, neighborhood construction, and information propagation. Our experimental evaluation on the SIFT1M dataset demonstrates that IGTM and CGTM significantly reduce computational costs compared to naive approaches, requiring up to 70\% fewer distance computations while maintaining comparable search accuracy. Surprisingly, IGTM outperforms CGTM in efficiency, contrary to our initial expectations. The proposed algorithms enable efficient consolidation of separately constructed indices, supporting critical operations in modern vector databases and retrieval systems that rely on HNSW for similarity search.

Figures

Figures reproduced from arXiv: 2505.16064 by the authors.

Figure 1
Figure 1. Schematic example HNSW structure. Each layer is a navigable graph [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Recall vs distance count on search stage for merged graphs. [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Recall of final merged graph vs merging efforts [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 30 canonical work pages

  1. [1]

    K-d trees for semidynamic point sets

    Jon Louis Bentley. K-d trees for semidynamic point sets. In Proceedings of the sixth annual symposium on Computational geometry, pages 187–197, 1990

  2. [2]

    R-trees: A dynamic index structure for spatial search- ing

    Antonin Guttman. R-trees: A dynamic index structure for spatial search- ing. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pages 47–57, 1984

  3. [3]

    Data structures and algorithms for nearest neighbor search in general metric spaces

    Peter N Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda, volume 93, pages 311–21, 1993

  4. [4]

    M-tree: An e cient access method for similarity search in metric spaces

    Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An e cient access method for similarity search in metric spaces. In Proceedings of the 23rd VLDB conference, Athens, Greece, pages 426–435. Citeseer, 1997

  5. [5]

    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, pages 97–104, 2006

  6. [6]

    Sim- ilarity search: the metric space approach, volume 32

    Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. Sim- ilarity search: the metric space approach, volume 32. Springer Science & Business Media, 2006

  7. [7]

    Local-descriptor matching for image identification

    Piotr Indyk. Local-descriptor matching for image identification. In Pro- ceedings of the Conference on High-Dimensional Hashing, 1998

  8. [8]

    Similarity search in high dimensions via hashing

    Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. ACM SIGMOD Record, 28(2):517–528, 1999

Show all 33 references
  1. [9]

    Locality-sensitive hashing scheme based on p-stable distributions

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Pro- ceedings of the 20th Annual Symposium on Computational Geometry, pages 253–262, 2004

  2. [10]

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

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

  3. [11]

    Optimal data-dependent hashing for approximate near neighbors

    Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 793–801, 2015

  4. [12]

    Product quantization for nearest neighbor search

    Herv´ e J´ egou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011. 17

  5. [13]

    Optimized product quantization for approximate nearest neighbor search

    Tiezheng Ge, Kaiming He, Qifeng Chen, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 863–870, 2013

  6. [14]

    Mohammad Norouzi and David J. Fleet. Cartesian k-means for product quantization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 119–126, 2013

  7. [15]

    Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs

    Yu A Malkov and Dmitry 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, 2018

  8. [16]

    Ann- benchmarks: A benchmarking tool for approximate nearest neighbor al- gorithms

    Martin Aum¨ uller, Erik Bernhardsson, and Alexander Faithfull. Ann- benchmarks: A benchmarking tool for approximate nearest neighbor al- gorithms. Information Systems, 87:101374, 2020

  9. [17]

    The faiss library

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazar´ e, Maria Lomeli, Lucas Hosseini, and Herv´ e J´ egou. The faiss library. 2024

  10. [18]

    Engineering efficient and effec- tive non-metric space library

    Leonid Boytsov and Bilegsaikhan Naidan. Engineering efficient and effec- tive non-metric space library. In Nieves R. Brisaboa, Oscar Pedreira, and Pavel Zezula, editors,Similarity Search and Applications - 6th International Conference, SISAP 2013, A Coru˜ na, Spain, October 2-...

  11. [19]

    Understanding Hierarchical Navigable Small World Indexes, 2023

    Oracle Corporation. Understanding Hierarchical Navigable Small World Indexes, 2023. Accessed: 2025-04-05

  12. [20]

    https://milvus.io/docs/hnsw.md, 2024

    Hnsw index. https://milvus.io/docs/hnsw.md, 2024. Accessed: 2024- 05-20

  13. [21]

    https://zilliz.com/blog/ hnsw, 2022

    Hierarchical navigable small world (hnsw). https://zilliz.com/blog/ hnsw, 2022. Accessed: 2024-05-20

  14. [22]

    Vector Index

    Weaviate Team. Vector Index. Weaviate, 2024. Accessed: 2025-04-05

  15. [23]

    Approximate nearest neighbor search small world approach

    Alexander Ponomarenko, Yury Malkov, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor search small world approach. In International Conference on Information and Communication Technologies & Applications, volume 17, 2011

  16. [24]

    Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces

    Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces. In Similar- ity Search and Applications: 5th International Conference, SISAP 2012...

  17. [25]

    Approximate nearest neighbor algorithm based on navigable small world graphs

    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

  18. [26]

    Graph-based nearest neighbor search: From practice to theory

    Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pages 7803–7813. PMLR, 2020

  19. [27]

    Revisiting the index construction of proximity graph-based approximate nearest neighbor search.arXiv preprint arXiv:2410.01231, 2024

    Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. Revisiting the index construction of proximity graph-based approximate nearest neighbor search.arXiv preprint arXiv:2410.01231, 2024

  20. [28]

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

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Rav- ishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems, 32, 2019

  21. [29]

    A com- prehensive survey and experimental comparison of graph-based approx- imate nearest neighbor search

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A com- prehensive survey and experimental comparison of graph-based approx- imate nearest neighbor search. Proceedings of the VLDB Endowment, 14(11):1964–1978, 2021

  22. [30]

    USearch by Unum Cloud

    Ash Vardanian. USearch by Unum Cloud. https://github.com/ unum-cloud/usearch, 2025. Version 2.17.7, May 2025

  23. [31]

    hnswlib: Hierarchical navigable small world graphs library

    Yury Malkov et al. hnswlib: Hierarchical navigable small world graphs library. https://github.com/nmslib/hnswlib, 2025. Accessed: 2025-05- 04

  24. [32]

    https://www.elastic.co/blog/ introducing-hnsw-graphs, 2023

    Hnsw graphs: Speed up merging. https://www.elastic.co/blog/ introducing-hnsw-graphs, 2023. Accessed: 2024-05-20

  25. [33]

    On the merge of k-nn graph

    Wan-Lei Zhao, Hui Wang, Peng-Cheng Lin, and Chong-Wah Ngo. On the merge of k-nn graph. IEEE Transactions on Big Data, 8(6):1496–1510, 2021. 19

Pith tools

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