{"id":"11225327-8e2a-4d80-8808-1fe782f52282","arxiv_id":"1908.00814","paper_version":6,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Three merge algorithms (S-Merge, J-Merge, H-Merge) combine or extend k-NN graphs efficiently, with quality close to building from scratch, and the hierarchical version speeds up nearest-neighbor search.","lead":"This paper proposes algorithms to combine two nearest-neighbor graphs into one, or to add new data to an existing graph, without rebuilding from scratch. The merged graphs are nearly as accurate as graphs built from scratch, cost less to produce, and the hierarchical version supports fast nearest-neighbor search.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Merge quality rests on an untested random-split assumption; under distribution shift the random cross-set seeds can fail to discover true cross-set edges.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern: the merge algorithms rely on random cross-set seeds to bootstrap discovery of cross-set edges, and this is only guaranteed when the two sets are random samples from the same distribution. The paper's experiments split existing datasets randomly (Sec. 5.2), so they never exercise the streaming or distributed scenarios where a new batch has a different distribution. This is not a question of tuning or error bars; it is a condition for the core mechanism to work at all. The cost accounting issue (subgraph construction excluded from the reported scanning rates) is real but secondary: the paper's own contribution is the merge step, and the experiments compare that merge step against whole-set NN-Descent. The absence of error bars is a reporting weakness, not a structural flaw. The distribution-shift assumption, by contrast, determines whether the algorithm generalizes beyond i.i.d. partitions, which the paper explicitly motivates in the streaming use case (Flickr-style uploads). A concrete experiment with two overlapping but differently proportioned mixtures would settle whether the random seeds still provide enough bridge links when the local densities differ. Since the reader already marked the paper CONDITIONAL and this concern is the basis for that condition, no change to the verdict is needed.","tokens_in":24804,"tokens_out":11568,"duration_ms":117069,"concrete_test":"Use a synthetic union of two distributions with partial overlap and shifted proportions (e.g., S1 ~ 0.8*U[0,0.5]^d + 0.2*U[0.5,1]^d; S2 ~ 0.2*U[0,0.5]^d + 0.8*U[0.5,1]^d), d=32, n=100K, k=40. Run S-Merge (and J-Merge) and compare recall@10 and total distance computations against NN-Descent on the full union. Repeat over 20 random splits of the same union as control. If recall@10 of the merged graph falls more than 3 percentage points below NN-Descent (e.g., >10% relative gap) while the control random-split gap stays below 3%, the distribution-shift assumption is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The merge algorithms' correctness rests on the initialization injecting enough cross-set edges for NN-Descent's hill-climbing to discover true cross-set neighbors. In S-Merge (Alg. 1, Lines 4-7) and J-Merge (Alg. 2, Lines 3-6), each list is seeded with k/2 random samples from the other set. NN-Descent can only compare pairs that co-occur in some list after the reverse/union steps; it cannot create a cross-set edge unless at least one initial cross-set link lies in the neighborhood of the true edge's endpoint. When S1 and S2 are random halves of one dataset (the only setting tested in Sec. 5.2), every region contains points from both sides with proportional density, so random seeds land near true cross-set neighbors with high probability. If the two sets instead come from different distributions (a new batch in streaming, or non-i.i.d. blocks in distributed construction), the bridge regions may be sparse or empty; random seeds from the other set can all be far from the relevant local neighborhoods, and the iterative comparisons never reach the true cross-set pairs. The paper explicitly requires random drawing for H-Merge (Sec. 3.3) but never tests or analyzes S-Merge/J-Merge under drift. Since the claimed 3% recall parity and 1/3-2/3 cost savings are established only for random splits, the central claim's scope is narrower than stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses the problem of merging approximate k-NN graphs, which has received little prior attention. Two algorithms are proposed: S-Merge, which merges two already-built k-NN graphs, and J-Merge, which merges a raw data batch into an existing graph. Both algorithms initialize each neighborhood list with a random half of samples from the other set and then run NN-Descent-style hill climbing, restricted in S-Merge to cross-set comparisons. Repeated J-Merge yields H-Merge, a hierarchical k-NN graph construction used for fast NN search. The paper reports that merge quality is within 3% of NN-Descent while scanning rates are about one-third and two-thirds of NN-Descent, and that H-Merge is competitive with HNSW on a broad set of datasets. A convergence argument and complexity analysis are given in Section 3.4, and experiments cover synthetic and real data with multiple distance measures.","tokens_in":25092,"tokens_out":8970,"duration_ms":89572,"significance":"If the results hold, the paper fills a genuine gap: k-NN graph merging enables parallel and incremental construction without rebuilding the graph from scratch. The empirical evaluation is broad, covering six synthetic and ten real-world datasets, several distance measures, and up to 10M points, and the authors state that the code is open-sourced, which supports reproducibility. The H-Merge search results are competitive with HNSW while preserving a full k-NN graph at each layer, a property useful for applications that need neighbor browsing as well as search. However, the paper's central cost claims rest on a complexity derivation that is internally inconsistent, and the merge-quality claim is demonstrated only for random splits of a single dataset. The contribution is valuable, but the theoretical arguments and the stated scope need significant revision.","major_comments":[{"comment":"The 'one-third' cross-comparison fraction is not supported by the algorithm's own initialization. In S-Merge, after Step 1 each NN list has k/2 samples from S1 and k/2 samples from S2; the fraction of unordered cross-set pairs among the k entries is approximately (k/2)^2 / C(k,2) ~ 1/2, not 1/3. Since Eq. (3) is the basis for the headline 'one-third of NN-Descent cost' claim and for Table 1, the derivation should be reworked or replaced by a direct empirical measurement of the cross-comparison fraction.","section":"Sec. 3.4, Eq. (3)"},{"comment":"The stated O(5 d n^ρ /3) complexity for H-Merge does not follow from the preceding text. If each level of the doubling hierarchy costs J-Merge's stated 2/3 d m^ρ, the geometric sum over m = n/2, n/4, ... gives approximately (2/3)/(1 - 2^{-ρ}) d n^ρ, which for ρ in [1.4, 1.9] is about 0.9–1.03 d n^ρ, not 5/3. The sentence claiming 'roughly 1.67 times' needs an explicit calculation identifying which operations contribute the extra constant.","section":"Sec. 3.4, Table 1 (H-Merge)"},{"comment":"The central merge-quality claim is established only for randomly split data. In Alg. 1 (lines 4–7) and Alg. 2 (lines 3–6), the only cross-set edges available to hill climbing are the k/2 random cross-set links seeded per list. All experiments in Sec. 5.2 divide each dataset randomly, so every local neighborhood contains both subsets with the same density. The paper motivates merging with streaming data (Sec. 1), where a new batch can follow a different distribution; in that case the random seeds may all lie far from the true cross-set neighbors, and the iterative comparisons cannot recover the missing edges. Please test non-i.i.d. partitions, such as batches drawn from different clusters or temporally shifted data, or narrow the claimed scope of S-Merge and J-Merge.","section":"Secs. 3.1–3.3, 5.2"},{"comment":"The scanning rates reported for S-Merge and J-Merge exclude the cost of building the input subgraphs, so the comparison against from-scratch NN-Descent is not end-to-end. For |S1| = |S2|, constructing the two subgraphs by NN-Descent adds roughly 2 d (n/2)^ρ distance computations, which partially or fully offsets the merge savings. The text's caveat in Sec. 5.2.2 acknowledges this only indirectly; the headline 'one-third / two-thirds of NN-Descent' should be presented with a full cost accounting.","section":"Sec. 5.2, Table 3"}],"minor_comments":[{"comment":"The initialization 'Initialize G2[i] with k random samples from S1∪S2' can select the sample itself; the paper should state that self-edges are excluded, as is standard in k-NN graph construction.","section":"Alg. 2, Line 6"},{"comment":"The sentence 'S-Merge actually shows slightly higher scanning rates than J-Merge...' is ambiguous because 'higher scanning rate' could be read as better quality; clarify that it means more distance computations.","section":"Sec. 5.2.2"},{"comment":"The requirement that each subset joined into the hierarchy be randomly drawn from the whole set is stated as an assumption, but it is not listed among the limitations in Secs. 1 or 5; the paper should state explicitly that the merge algorithms preserve quality only under this representativeness assumption.","section":"Sec. 3.3"},{"comment":"The statement that H-Merge takes 'roughly twice more' time than NN-Descent is inconsistent with RAND10M8D (597.07 s vs. 132.84 s, a factor of about 4.5); either the sentence should be qualified by dataset or the discrepancy explained.","section":"Sec. 5.3.1, Table 4"},{"comment":"The scanning rate c is defined with C as the total number of distance computations; please state explicitly whether C in Table 3 includes the distance computations spent in building the input subgraphs for S-Merge and J-Merge.","section":"Eq. (7)"},{"comment":"The caption of Fig. 5 contains the typo 'SIFT1HKMNIST'; it should read 'SIFT100K, MNIST'.","section":"Fig. 5"}],"recommendation":"major_revision","confidential_remarks":"The empirical core of the paper appears sound: on random splits, S-Merge and J-Merge achieve recall close to NN-Descent, and H-Merge is a credible alternative to HNSW. The main problems are the internally inconsistent complexity derivation in Sec. 3.4 and the unstated reliance on i.i.d. batch assumptions. Both are fixable by rewriting the analysis and adding a robustness experiment or explicitly narrowing the claims. I did not see citation issues beyond normal self-citation to closely related prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a careful read, and worth serious peer review. The genuinely new piece is the symmetric merge: combining two prebuilt k-NN graphs directly, instead of inserting points one by one or rebuilding from scratch. J-Merge extends the same idea to a raw batch, and H-Merge converts repeated J-Merge into a hierarchy whose search performance lands close to HNSW while still maintaining a full k-NN graph at the bottom layer—that is a real advantage for browsing or for merging indexes later.\n\nThe empirical work is solid. The recall parity with NN-Descent (within 3%) holds across ten datasets and several distance measures, and the measured scanning rates approximate the claimed 1/3 and 2/3 savings. The r-parameter ablation is informative and gives reasonable default settings. The code is open-sourced, which makes the claims checkable.\n\nThe soft spots are mostly at the edges. The complexity argument in Section 3.4 does not actually produce the 1/3 and 2/3 ratios: the mixing assumption leads to roughly half the comparisons being cross-set in S-Merge, not a third, and the reverse/union steps are ignored in the counting. The empirical savings land near the stated fractions, so the conclusion may be right, but the derivation needs to be reworked.\n\nMore important, the algorithms depend on the two subsets being random samples from the same distribution. The paper says this explicitly only for H-Merge (Sec. 3.3) and never tests S-Merge or J-Merge under distribution shift. If a new batch comes from a different region of the space, the random cross-set seeds can all be far from the true cross-set neighbors, and the hill-climbing cannot discover what the initialization missed. That narrows the streaming promise: the experiments only cover random splits. I would not call it a fatal flaw—the paper is honest about the requirement for H-Merge—but the claim in the abstract is broader than the evidence.\n\nMinor: the main recall/cost tables have no error bars, and the abstract's \"superior performance\" against HNSW really means \"comparable, with a win in low-dimensional cases.\"\n\nWho should read: anyone working on incremental or distributed k-NN graph construction or on graph-based ANN indexes. As a referee I would ask for a corrected complexity derivation and a clear statement of the distribution-shift limitation, but I would not block publication over either. This deserves serious peer review.","headline":"Solid empirical contribution on a genuinely unaddressed problem—k-NN graph merging—with a real but untested distribution-shift caveat and a shaky complexity derivation.","tokens_in":25643,"tokens_out":2965,"would_cite":true,"duration_ms":29223,"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":"Merging two approximate k-NN graphs can be done for about one-third of the from-scratch construction cost, while keeping graph recall within 3% of building the whole graph with NN-Descent.","keywords":["k-nearest neighbor graph","graph merging","NN-Descent","hierarchical graph","nearest neighbor search","incremental graph construction","approximate k-NN graph","hill-climbing"],"falsifier":"Construct a dataset from two well-separated Gaussian clusters, build a k-NN graph on one cluster and try to merge in the other cluster with S-Merge or J-Merge; if recall@10 on the merged graph falls far below the within-3% gap that the paper reports for random splits, the same-distribution assumption is violated. A simpler version: split MNIST into digit 0-4 and digit 5-9 and compare merge recall against NN-Descent on the full set.","tokens_in":24594,"feed_emoji":"🔗","tokens_out":5745,"duration_ms":50845,"temperature":0.7,"pith_summary":"Two approximate nearest-neighbor graphs can be fused without rebuilding the whole graph. This paper introduces S-Merge, which combines two existing k-NN graphs, and J-Merge, which absorbs a raw batch into an existing graph; both work by seeding each neighborhood list with random samples from the other side and then running the standard “neighbor’s neighbor” hill-climbing update restricted to cross-set pairs. The claimed payoff is a distance-computation cost around one-third (S-Merge) and two-thirds (J-Merge) of building the graph from scratch with NN-Descent, while keeping graph recall within 3% of NN-Descent. Because J-Merge handles raw batches, it also yields an incremental, hierarchical construction (H-Merge) whose top layers act as shortcuts for nearest-neighbor search. A sympathetic reader would care because this turns graph merging from an overlooked, apparently costly operation into a building block for parallel and streaming approximate graph construction.","feed_headline":"Merging k-NN graphs cuts rebuild cost to one-third","feed_subtitle":"Two merge algorithms keep recall within 3% of NN-Descent and enable incremental, hierarchical neighbor search.","key_machinery":"The load-bearing mechanism is the half-baked seed graph plus a restricted NN-Descent loop. Concretely, each k-NN list is truncated to $k/2$ entries and seeded with $k/2$ uniformly random samples from the other dataset, so the initial graph already contains enough cross-set edges for hill-climbing; the loop then uses the “neighbor’s neighbor is likely a neighbor” rule but only evaluates pairs that cross the $S_1/S_2$ boundary (S-Merge) or that cross the boundary or lie inside the raw set (J-Merge). Convergence is carried by the potential $\\varphi(G)$, the sum over all samples of all listed neighbor distances, which decreases monotonically on every accepted swap and is bounded below by the true k-NN graph’s sum; because the state space is finite, the loop must stop. The complexity ratios (one-third and two-thirds of NN-Descent) follow from the assumption that random seeding mixes the two sides so thoroughly that roughly one-third and two-thirds of all distance comparisons in the from-scratch run are retained.","core_discovery":"On the paper’s own terms, the central claim is that merging two approximate k-NN graphs is not a separate hard problem: it is NN-Descent starting halfway up the hill. S-Merge cuts the rear half off each NN list, appends $k/2$ uniformly random samples from the other subgraph, and iterates NN-Descent while comparing only samples that come from different sides; J-Merge does the same when one side is raw, initializing the raw samples’ lists from the union and also comparing within the raw set. Both end by merging the truncated rear lists back with a merge sort. The paper derives, from a monotone potential $\\varphi(G)$ that sums all listed neighbor distances, that the iteration converges, and argues from random mixing that S-Merge performs about one-third and J-Merge about two-thirds of the distance computations of constructing the whole graph from scratch. It reports recall within 3% of NN-Descent on synthetic and real datasets under $\\ell_1$, $\\ell_2$, cosine, $\\chi^2$, and Jaccard distances. Applying J-Merge to successively doubled random batches gives H-Merge, a hierarchy of approximate k-NN graphs whose top-down NN search is competitive with HNSW, with the extra property that every layer remains a true approximate k-NN graph.","pith_inferences":["Beyond the paper: the merge cost model assumes the two sides are random samples of one distribution. If a new batch arrives from a shifted distribution, random cross-set seeds may contain no close pairs, and the restricted hill-climb cannot recover them; a testable fix would seed cross-set links by a cheap retrieval step, such as coarse hashing, before the NN-Descent loop.","Beyond the paper: the one-third/two-thirds arithmetic suggests the same merge idea could be applied recursively to more than two graphs with a composition law; whether multi-way merging in one pass beats pairwise recursive merging is not addressed and could be measured as an extension.","Beyond the paper: H-Merge’s hierarchy sizes were fixed as a hyperparameter (e.g., 64, 512, and so on); choosing layer sizes adaptively from the data’s intrinsic dimension might further improve the search speed/recall trade-off, since the paper’s own results show the hierarchy helps most when intrinsic dimension is low."],"forward_implications":["Parallel construction of a k-NN graph can be done by building subgraphs independently and repeatedly applying S-Merge, rather than rebuilding on the union.","A k-NN graph over a streaming collection can be maintained incrementally: each new batch is absorbed by J-Merge at a fraction of the from-scratch cost, without ever needing all data in memory at once.","The H-Merge hierarchy supplies a nearest-neighbor index whose upper layers are coarse approximate k-NN graphs, so search can skip large portions of the data in low intrinsic dimension.","Because every layer of H-Merge remains an approximate k-NN graph, the same structure supports neighbor browsing tasks that HNSW-style sparsified graphs do not support.","The merge operations inherit NN-Descent’s generality across distance measures, so the cost savings extend to non-Euclidean metrics such as cosine, $\\chi^2$, and Jaccard."],"supporting_citations":[{"why":"Supplies NN-Descent, the hill-climbing construction and iteration that both merge algorithms extend.","marker":"[5]"},{"why":"Provides HNSW and the hierarchical search and graph-diversification scheme that H-Merge is compared against and adopts.","marker":"[13]"},{"why":"Supplies NSW, the online insertion baseline that J-Merge must beat in incremental merging.","marker":"[12]"},{"why":"Supplies RLB, the divide-and-conquer graph construction baseline used for comparison in the merging scenarios.","marker":"[7]"},{"why":"Provides the DPG graph-search benchmark and the observation that hierarchy helps most at low intrinsic dimension.","marker":"[31]"},{"why":"Supplies the online k-NN graph construction approach that H-Merge is compared with for open-set construction.","marker":"[32]"}],"fun_headline_variants":["S-Merge: one-third the distance computations of a rebuild","J-Merge: incremental k-NN graph expansion for hierarchy search","k-NN merge: NN-Descent starting from the halfway point","Two k-NN graph merge algorithms keep recall within 3%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the two datasets to be merged are random samples of the same underlying distribution, so that $k/2$ uniformly random cross-set links per list are enough for the hill-climbing loop to discover the true cross-set edges; if a batch comes from a different distribution, the random seeds miss the close pairs and the merge quality collapses.","fun_headline_variants_meta":{"raw":{"variants":["S-Merge: one-third the distance computations of a rebuild","J-Merge: incremental k-NN graph expansion for hierarchy search","k-NN merge: NN-Descent starting from the halfway point","Two k-NN graph merge algorithms keep recall within 3%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00091,"raw_usage":{"total_tokens":3931,"prompt_tokens":987,"completion_tokens":2944,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":2869}},"tokens_in":603,"tokens_out":2944,"duration_ms":24243,"temperature":1.0,"reasoning_tokens":2869,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:31:46.627533+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a dataset from two well-separated Gaussian clusters, build a k-NN graph on one cluster and try to merge in the other cluster with S-Merge or J-Merge; if recall@10 on the merged graph falls far below the within-3% gap that the paper reports for random splits, the same-distribution assumption is violated. A simpler version: split MNIST into digit 0-4 and digit 5-9 and compare merge recall against NN-Descent on the full set.","supporting_citations":[{"cited_title":"Efficient k-nearest neighbor graph construction for generic similarity measures,","cited_arxiv_id":null,"evidence_quote":"Supplies NN-Descent, the hill-climbing construction and iteration that both merge algorithms extend."},{"cited_title":"Efficient and robust approx- imate nearest neighbor search using hierarchical navigable small world graphs,","cited_arxiv_id":null,"evidence_quote":"Provides HNSW and the hierarchical search and graph-diversification scheme that H-Merge is compared against and adopts."},{"cited_title":"Ap- proximate nearest neighbor algorithm based on navigable small world graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies NSW, the online insertion baseline that J-Merge must beat in incremental merging."},{"cited_title":"Fast approximate knn graph construction for high dimensional data via recursive lanczos bisec- tion,","cited_arxiv_id":null,"evidence_quote":"Supplies RLB, the divide-and-conquer graph construction baseline used for comparison in the merging scenarios."},{"cited_title":"Ap- proximate nearest neighbor search on high dimensional data- experiments, analysis and improvement,","cited_arxiv_id":null,"evidence_quote":"Provides the DPG graph-search benchmark and the observation that hierarchy helps most at low intrinsic dimension."}],"review_version":1}