{"id":"dd6c540d-ec71-4bd4-82df-6da41c70f5dd","arxiv_id":"2505.16064","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Three HNSW merge algorithms are proposed, and the fastest (IGTM) reportedly achieves roughly 70 percent fewer distance computations with comparable recall on SIFT1M.","lead":"This paper introduces three algorithms for merging two HNSW similarity-search indexes, an operation needed in vector databases and distributed systems. The fastest method, Intra Graph Traversal Merge, is claimed to cut merge cost by about 70 percent in distance computations on the SIFT1M dataset while keeping search recall nearly unchanged.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 70% cost-reduction claim rests on a single-run, best-of-sweep evaluation on one dataset; without variance estimates or a recall-matched comparison, the measured effect may not be robust.","rationale":"The reader's verdict (CONDITIONAL) already captures the need for more evidence, so I do not change it. The reader's stated weakest assumption is the empirical locality assumption behind IGTM/CGTM (that a candidate set inherited from a nearby vertex seeds a successful LocalSearch). That is a plausible algorithmic concern, but the paper's experiments do provide some support for it on SIFT1M. My broader concern is the reliability of the headline number itself: with a single dataset, no repeated trials, and a large parameter sweep, the 'up to 70% fewer distance computations' figure is the best observed point, not a statistically supported effect. This is more load-bearing than the locality assumption because even if locality holds perfectly, the reported savings could be a selection artifact. The concrete test I propose—multi-split replication with a pre-registered parameter set and recall-matched comparison—would directly settle whether the claimed advantage is real. Secondary issues I noticed but did not use as the main attack: (1) Algorithms 6 and 7 both contain the same typo in line 1, assigning Gb from Ha instead of Hb, which as written makes the 'merge' a self-merge; this must be corrected for reproducibility, though the surrounding text clearly indicates the intent. (2) The paper measures 'computational cost' as distance computations only, which is a reasonable proxy, but the CGTM overhead for selecting the next vertex (line 24) is acknowledged as expensive and is not captured by the metric; this does not undermine the distance-computation claim, but it qualifies the practical speedup. My recommended verdict stays CONDITIONAL because the central claim is plausible and the code is public, but it is not yet established with statistical confidence.","tokens_in":13762,"tokens_out":6513,"duration_ms":55545,"concrete_test":"Run the merge experiment on 5 independent 500k/500k random splits of SIFT1M plus one additional dataset (e.g., GIST1M or GloVe-100). Fix the parameter set in advance to the configuration that appears best in the current sweep (or choose parameters on a validation split and evaluate on a test split). For each split, measure the minimum merge distance count required by each algorithm to reach the recall@5 level of the best NGM configuration at L=64, and report the mean and standard deviation of the ratios IGTM/NGM and IGTM/CGTM. If the mean IGTM saving over NGM is less than 50%, or if IGTM does not beat CGTM in at least 4 of 5 splits, the headline 70% claim is not robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim is that IGTM and CGTM require 'up to 70% fewer distance computations' than NGM/SIGM 'while maintaining comparable search accuracy.' The evidence is Fig. 3, which plots recall at a fixed search L against total merge distance count for dozens of parameter combinations. The 70% figure is the best-case ratio between the best IGTM configuration and the best NGM/SIGM configuration, selected from the same plot that is used to support the claim. No error bars, repeated runs, or held-out data are provided; the random choices in HNSW construction and in line 7 of Algorithms 7-8 (random v*) make merge distance count and recall random variables. The 'comparable recall' assertion is also not anchored to a statistical test: at fixed L, the low-cost IGTM configurations appear to deliver slightly lower recall than the high-cost NGM/SIGM configurations, so the 70% saving is measured at a different, lower recall point. If a fair comparison fixes the recall level (e.g., the recall of the best NGM configuration) and measures the minimum merge cost to achieve it, the claimed advantage could shrink substantially. The paper's own 'surprising' ordering—IGTM outperforming CGTM by about 20%—is exactly the kind of small effect that single-run evaluation cannot reliably establish.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14032,"tokens_out":7496,"duration_ms":63916,"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":[{"comment":"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.","section":"§5.2, Fig. 3 and abstract"},{"comment":"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.","section":"§5.1–§5.2, Fig. 3"},{"comment":"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.","section":"§4.4–§4.5, Algorithms 7 and 8"},{"comment":"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.","section":"§4.4, Algorithms 7–8"}],"minor_comments":[{"comment":"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.","section":"§2.2, Algorithm 2"},{"comment":"The input list defines 'ventry' but the body uses 'vb_entry' and 'va_entry'; define these variables or remove the inconsistency.","section":"§4.3, Algorithm 6"},{"comment":"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.","section":"§4.5, Algorithm 8"},{"comment":"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.","section":"§5.1"},{"comment":"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.","section":"Fig. 2 and Fig. 3"},{"comment":"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.","section":"§6"}],"recommendation":"major_revision","confidential_remarks":"The paper is a purely empirical cs.DS contribution with no theoretical analysis; the editor may wish to consider whether the current level of experimental evidence (one dataset, one run, best-of-sweep) meets the journal's standards. The algorithmic idea is plausible and the code release is a positive sign, but the central quantitative claim needs substantial additional support. The pseudocode specification gaps should also be fixed before any acceptance decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The IGTM and CGTM algorithms are the real thing: a recognizable new technique for HNSW merging. Warm-starting the candidate set from the previous vertex's LocalSearch, and using that to avoid repeated top-level HNSW-Search jumps, is a concrete and sensible idea that I have not seen in the Elastic join-set post or in Zhao et al.'s symmetric prune. The four-step iterative framework is clearly explained, the pseudocode is mostly readable, and the GitHub release makes the work reproducible. Credit is also due for comparing against SIGM and NGM rather than only against rebuilding.\n\nThe soft spots are real and concentrated in the evaluation. The stress-test note is fair: the \"up to 70% fewer distance computations\" is the best configuration from a parameter sweep, on one dataset (SIFT1M), with no error bars or repeated runs. The distance count is a random variable here, since HNSW construction and the random v* choices in Algorithms 7 and 8 both have randomness. And the \"comparable recall\" claim is not recall-matched: the cheap IGTM points in Figure 3 sit at slightly lower recall than the expensive NGM/SIGM points. If you fix recall at the NGM level and ask for the minimum merge cost to reach it, the 70% advantage could shrink substantially. The IGTM-over-CGTM ordering by about 20% is exactly the kind of small effect that single-run evaluation cannot reliably establish.\n\nThere are also concrete technical fixables. Algorithm 6 line 1 reads Gb from Ha instead of Hb, and Algorithm 7 uses next_step_ef in line 15 but does not list it in the input parameters, even though Figure 2 and Figure 3 sweep it. Those are typos, not deep flaws, but they should be corrected.\n\nNone of this undermines the core idea. I believe the direction of the result is plausible, and the algorithm design is worth taking seriously. The paper is a legitimate systems contribution, not a breakthrough, and it deserves a serious referee. The evaluation needs more datasets, repeated runs, a fixed protocol that does not select the headline from a sweep, and ideally a recall-matched cost comparison. If those are added, the paper would be solid for a venue like SISAP or a systems-oriented workshop.","headline":"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.","tokens_in":14558,"tokens_out":2068,"would_cite":true,"duration_ms":18999,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["approximate nearest neighbor search","hierarchical navigable small world","graph merging","vector databases","local search","SIFT1M","information retrieval"],"falsifier":"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.","tokens_in":13547,"feed_emoji":"🔀","tokens_out":8486,"duration_ms":66634,"temperature":0.7,"pith_summary":"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.","feed_headline":"Merging two HNSW graphs cuts distance computations by 70 percent","feed_subtitle":"Processing nearby vertices in sequence lets local search reuse candidate lists, speeding up index consolidation","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines HNSW and its construction parameters; the graphs being merged are built with this method.","marker":"[15]"},{"why":"Introduces the greedy navigable-graph search that the LocalSearch primitive in this paper is based on.","marker":"[23]"},{"why":"Formalizes beam search, the search primitive whose reuse drives the reported speedup.","marker":"[26]"},{"why":"Describes the closest prior merge strategy, which selects a join set and performs limited beam search.","marker":"[32]"},{"why":"Presents earlier symmetric and joint merge algorithms for k-NN graphs that this work contrasts with its HNSW-specific approach.","marker":"[33]"},{"why":"Supplies the SIFT1M benchmark dataset and the recall-versus-distance methodology used to evaluate the merged graphs.","marker":"[16]"}],"fun_headline_variants":["Merging HNSW graphs: reuse candidates to cut distance calls by 70%","Efficient HNSW merge: neighboring vertices share search seeds, savings 70%","New merge algorithms for HNSW cut distance computations by up to 70%","HNSW merging: walk within graph to slash 70% of distance checks","Smart HNSW merge reuses candidate lists, trims 70% of calculations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Merging HNSW graphs: reuse candidates to cut distance calls by 70%","Efficient HNSW merge: neighboring vertices share search seeds, savings 70%","New merge algorithms for HNSW cut distance computations by up to 70%","HNSW merging: walk within graph to slash 70% of distance checks","Smart HNSW merge reuses candidate lists, trims 70% of calculations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000653,"raw_usage":{"total_tokens":2967,"prompt_tokens":891,"completion_tokens":2076,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":1966}},"tokens_in":507,"tokens_out":2076,"duration_ms":11985,"temperature":1.0,"reasoning_tokens":1966,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:06:38.997788+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs","cited_arxiv_id":null,"evidence_quote":"Defines HNSW and its construction parameters; the graphs being merged are built with this method."},{"cited_title":"Approximate nearest neighbor search small world approach","cited_arxiv_id":null,"evidence_quote":"Introduces the greedy navigable-graph search that the LocalSearch primitive in this paper is based on."},{"cited_title":"https://www.elastic.co/blog/ introducing-hnsw-graphs, 2023","cited_arxiv_id":null,"evidence_quote":"Describes the closest prior merge strategy, which selects a join set and performs limited beam search."},{"cited_title":"On the merge of k-nn graph","cited_arxiv_id":null,"evidence_quote":"Presents earlier symmetric and joint merge algorithms for k-NN graphs that this work contrasts with its HNSW-specific approach."},{"cited_title":"Ann- benchmarks: A benchmarking tool for approximate nearest neighbor al- gorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the SIFT1M benchmark dataset and the recall-versus-distance methodology used to evaluate the merged graphs."}],"review_version":1}