{"id":"c5127327-01fe-4bed-a287-fd71eecaaf52","arxiv_id":"2501.13992","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"HNSW++ modifies HNSW with a dual-branch graph, LID-based insertion, and skip bridges, reporting better recall and construction speed on six small datasets.","lead":"This paper introduces HNSW++, a modified HNSW graph for approximate nearest neighbor search that adds a two-branch structure, LID-based insertion, and layer-skipping bridges. Tests on six small datasets report up to 30% higher recall and 20% faster construction than standard HNSW, but no code is released and the evaluation is limited.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Construction-speed claim omits mandatory LID precomputation; the no-trade-off result is unverified for end-to-end index building.","rationale":"The reader's weakest assumption was the spatial-division justification for dual branches. That is a valid concern, but I judge the more load-bearing gap to be the omitted LID precomputation cost, because it directly undermines the headline construction-speed and no-trade-off claims. The paper itself flags the assumption in Section 3.5.2, but the experimental section does not account for it. I am not claiming the algorithm is wrong; rather, the central speed claim is not yet supported by a fair end-to-end measurement. The paper has a clear algorithmic description and a reasonable ablation structure, and I would not reject it outright. The verdict remains CONDITIONAL, pending an end-to-end construction-time comparison and, ideally, released code. My disagreement with the reader is therefore about which weakness is most load-bearing, not about the overall conditional verdict.","tokens_in":11274,"tokens_out":7824,"duration_ms":74716,"concrete_test":"Re-run the construction benchmark with LID estimation included in HNSW++ wall-clock time: for each dataset, time the exact/approximate k-NN LID computation exactly as described in Section 4.1 and add it to HNSW++ graph-construction time; compare this total against Basic HNSW construction on the same machine and data. If HNSW++ total time is not below Basic, the construction-time claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central no-trade-off claim rests on a construction-time comparison that excludes the cost of computing LID values, even though LID is a required input to HNSW++. Section 3.5.2 states \"Assuming the LID values are provided beforehand, HNSW++ does not add significant computational overhead,\" and Section 4.1 says LID was computed using MLE over exact k-NN (ef construction=128). For a 10,000-point index this is a substantial preprocessing step, yet the reported up-to-20% construction-time reduction (Section 4.3) compares only graph construction after LIDs are already available. A drop-in replacement must pay this cost. If end-to-end construction is measured, the claimed speed advantage may vanish or reverse, which would directly falsify the abstract's \"construction time reduced by up to 20%\" and \"we did not observe any trade-offs\" claims. This is a missing-cost fairness gap in the headline speed claim, not a dispute about consensus.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HNSW++, a modification of the Hierarchical Navigable Small World (HNSW) algorithm that adds a dual-branch graph structure, LID-based node insertion, and LID-threshold skip bridges. The authors claim that HNSW++ improves recall by 18% on NLP tasks and up to 30% on CV tasks, reduces construction time by up to 20%, maintains inference speed, and exhibits no trade-offs relative to the original HNSW. The method is evaluated on six datasets of 10,000 points each with 1,000 queries, comparing against FAISS, NMSLIB, PyNNDescent, and Annoy, and is accompanied by an ablation study separating the effects of the multi-branch structure, LID-based insertion, and skip-layer mechanism.","tokens_in":11523,"tokens_out":4316,"duration_ms":38113,"significance":"If the stated results hold, HNSW++ would be a practically valuable drop-in improvement to a widely used ANN method, and the LID-driven insertion idea is a plausible direction for improving cluster connectivity. The ablation study is a useful decomposition of the proposed components, and the use of ground-truth nearest neighbors for recall avoids circularity in the accuracy evaluation. However, the current evidence is not sufficient to support the headline no-trade-off claim: the construction-time comparison omits the mandatory LID precomputation cost, the central geometric justification for the dual-branch split is unsupported, and the complexity analysis is asserted rather than derived. The empirical scale and lack of error bars further limit confidence in the claimed improvements.","major_comments":[{"comment":"The construction-time comparison excludes the cost of computing LID values, despite LID being a required input to HNSW++. Section 3.5.2 states 'Assuming the LID values are provided beforehand,' and Section 4.1 reports that LID was computed via MLE over exact k-NN with efConstruction=128. For a 10,000-point index this is a substantial preprocessing step, so the up-to-20% construction-time reduction in Section 4.3 is not an end-to-end claim. The authors should report total wall-clock construction time including LID computation, or explicitly restrict the claim to graph-construction time after LID preprocessing; otherwise the abstract's 'construction time reduced by up to 20%' and 'no trade-offs' statements are not supported.","section":"§3.5.2, §4.1, Abstract"},{"comment":"The claim that partitioning nodes by insertion index divides the data into spatially distinct regions is unsupported. Section 3.2 states that splitting by 'the index of the inserted nodes' means 'spatial regions are divided into different branches,' but insertion order has no inherent geometric meaning. Without a geometric separation, the dual-branch search is simply running two searches over two arbitrary halves of the dataset, and the proposed mechanism for mitigating local minima is not established. The authors should provide evidence of spatial separation (e.g., overlap statistics or per-branch recall) or modify the algorithm and its justification.","section":"§3.2, Eq. (1)"},{"comment":"The complexity reduction to L_total·(1−P_skip) is asserted rather than derived. P_skip is controlled by thresholds T and epsilon and is not shown to be independent of layer or query; the analysis does not establish that expected traversal is indeed L_total·(1−P_skip). A concrete derivation or empirical layer-traversal counts are needed before the O(log N) claim can be considered credible.","section":"§3.5.1, Eq. (4)"},{"comment":"The skip condition in the pseudocode disagrees with Eq. (4). Algorithm 3 (lines 25–31) triggers a skip whenever the LID of the nearest neighbor exceeds the threshold, with no distance check, whereas Eq. (4) requires both LID(ep) > T and d(ep,q) < epsilon. This discrepancy means the reported query-time results do not identify which skip condition was actually used, and the experimental evaluation of the skip mechanism is ambiguous.","section":"§3.3, Algorithm 3"},{"comment":"The text states that cross-language timing comparisons are unfair because HNSW++ is implemented in Python while other methods use faster compiled languages, yet the same section reports construction-time comparisons against PyNNDescent and NMSLIB in Figure 9 and claims HNSW++ 'significantly surpasses' them. The authors should either remove the cross-language timing comparisons or provide a same-language or compiled baseline, and clarify which implementation (C++ or Python) produced each timing result.","section":"§4.2, Figure 9"},{"comment":"The experimental evaluation uses only 10,000 construction points and 1,000 queries, with no error bars or variance reporting despite the claim of '100 independent runs.' The 1–2% query-time differences and the no-trade-off conclusion require confidence intervals or per-run distributions. In addition, the hyperparameter selection procedure ('the best performance results for each algorithm were chosen based on recall across varying thresholds') should be specified precisely, because selecting parameters for best recall can bias the comparison in favor of the proposed method.","section":"§4, §4.3"}],"minor_comments":[{"comment":"The reference list contains formatting errors, including an extra parenthesis in '(Zhang et al., 2022))' and an unconventional entry for 'Cole Foster (2023)'; these should be corrected to match the journal style.","section":"References"},{"comment":"The caption for Figure 9 reads 'Illustration of recall of all algorithms on Random dataset,' but the surrounding text describes construction-time comparisons; the caption appears to be a copy-paste error and should be fixed.","section":"Figure 9 caption"},{"comment":"The threshold-analysis figures (Figures 14, 15a, 15b) are described in the appendix but referenced in the main text without clear cross-referencing; please add explicit calls to the appendix and ensure figure numbering is consistent.","section":"§3.4 and Appendix A.1"},{"comment":"The layer assignment in Algorithm 4 still relies on a random scaling factor via −log(random()) in line 6, even though the surrounding text emphasizes LID-based insertion; the exact role of randomness in the layer assignment should be clarified.","section":"Algorithm 4"},{"comment":"The sentence 'In terms of accuracy and recall, as depicted in Figures 15a and 15b, most datasets have minimal changes given different LID threshold' contains a grammatical error and should be rewritten for clarity.","section":"§4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a relevant practical problem and the LID-based insertion idea has merit, but the headline no-trade-off claim is not supported until the LID precomputation cost is included and the branch-split justification is tested. The issues are fixable within the manuscript's scope, so major revision is appropriate rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this paper proposes HNSW++, which adds three modifications to HNSW—a two-branch structure, LID-based node insertion, and LID-threshold skip bridges. The first and third are new as far as I can tell; LID-based insertion is already in Elliott & Clark (2024), which the paper cites. The ablation study is a real strength: it isolates each component and shows all three contribute, with LID insertion having the biggest effect.\n\nThe central claim is that HNSW++ improves recall and cuts construction time with no trade-offs. That claim is not established. The two problems that matter are the construction-time accounting and the branch-splitting assumption.\n\nSection 3.5.2 admits that LID values are assumed to be provided beforehand. Section 4.1 says LID was computed by MLE over exact k-NN with efConstruction=128. That precomputation is not included in the reported construction time. For a 10,000-point dataset it may be modest, but for the stated goal of large-scale search it is not negligible, and the abstract promises a 20% construction-time reduction without mentioning this cost. End-to-end, the speed advantage could shrink or disappear.\n\nThe second issue is that the dual-branch split is said to divide spatial regions, but the partition is based on insertion order / alternating assignment after sorting by LID. Insertion order carries no geometric guarantee. The claimed benefit of searching \"two distinct search regions\" (Section 3.3) is asserted, not shown. It might work heuristically, but the paper gives no analysis or evidence that the two branches are spatially separated.\n\nThere are other weaknesses, all in the same direction: 10,000-point datasets, no error bars, hyperparameters chosen per dataset for best recall, and a cross-language timing comparison that the paper itself says is unfair yet still uses in Figure 9. The complexity argument is also an assertion: O(log N) per branch and expected layer reduction by (1 - Pskip) are plausible but not derived.\n\nNone of these are fatal to the core idea. The paper is a legitimate attempt to improve a widely used algorithm, and the ablation is commendable. But the evidence does not support the strong \"no trade-offs\" conclusion. I would send it to peer review, with the expectation that the authors will need to release code, run larger benchmarks with error bars, include LID precomputation in construction time, and either justify or remove the spatial-splitting claim.\n\nWorth a quick read if you work on ANN search; not something to cite yet.","headline":"Plausible incremental improvement over HNSW with two genuinely new mechanisms, but the headline 'no trade-offs' claim is undercut by the omitted LID precomputation cost and an unjustified spatial-splitting assumption.","tokens_in":11963,"tokens_out":2691,"would_cite":false,"duration_ms":21914,"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":"HNSW++ outperforms the original HNSW on both accuracy and speed: recall rises by 18% on NLP tasks and up to 30% on CV tasks, construction time drops by up to 20%, and inference speed is maintained.","keywords":["approximate nearest neighbor search","HNSW","local intrinsic dimensionality","dual-branch graph","skip bridges","graph construction","high-dimensional search","recall optimization"],"falsifier":"Build HNSW++ on the same dataset twice, once with the original insertion order and once with randomly shuffled order, comparing recall and the overlap between the neighbor sets returned by the two branches. If shuffling preserves the gains and the two branches return nearly identical sets, the claimed spatial division by insertion index is not the operative mechanism.","tokens_in":11103,"feed_emoji":"🔎","tokens_out":6881,"duration_ms":57527,"temperature":0.7,"pith_summary":"The paper sets out to show that two known weaknesses of Hierarchical Navigable Small World graphs—greedy search falling into local optima and per-layer traversal that fails to reach logarithmic complexity—can be fixed together rather than traded off. It proposes HNSW++, which builds two parallel branches, inserts high-LID outlier nodes into upper layers, and adds skip bridges that jump to the base layer when a LID-distance condition holds. Across six datasets the authors report recall improvements of 18% on NLP data and up to 30% on vision data, construction time reductions up to 20%, and inference speed essentially unchanged. The paper concludes that HNSW++ is a drop-in replacement for HNSW with no observed trade-offs.","feed_headline":"HNSW++ lifts recall up to 30% and trims build time 20%","feed_subtitle":"Dual-branch search plus outlier-aware insertion and skip bridges boost accuracy without slowing queries.","key_machinery":"The central mechanism is a modified HNSW graph with three components: two parallel branches created by alternating node insertion by index, insertion guided by normalized Local Intrinsic Dimensionality (LID), and LID-threshold skip bridges. LID estimates local sparsity via the maximum-likelihood formula over k-nearest-neighbor distances; high-LID nodes are assigned to upper layers to improve inter-cluster connectivity. Skip bridges implement a Jump function that sends the search directly to layer 0 when the entry point's LID exceeds T and its distance to the query is below epsilon. These components together are what the paper credits for reducing local minima, cutting construction work roughly in half, and making layer traversal cheaper.","core_discovery":"The central claim is that HNSW++ dominates the original HNSW on both accuracy and speed. The dual-branch structure lets the search start from two entry points and explore two distinct regions, reducing the chance of being trapped in a local minimum; LID-based insertion places high-LID points in upper layers to bridge clusters; and skip bridges, triggered when a node's normalized LID exceeds a threshold and the distance to the query is small, bypass intermediate layers. In experiments on GLOVE, SIFT, RANDOM, DEEP, GIST, and GAUSSIAN, the authors report that HNSW++ outperforms the original HNSW and several established ANN libraries, with recall improving 18% in NLP tasks and up to 30% in CV tasks, construction time reduced by up to 20%, and inference time maintained. Ablation results rank LID-based insertion as the largest contributor, followed by the dual-branch structure and the skip bridges. The authors state that they observed no trade-offs.","pith_inferences":["Editorial inference: a shuffle test of insertion order would isolate whether the dual-branch gain comes from spatial separation or simply from running two independent greedy searches; the paper does not report such a test.","Editorial inference: since the ablation shows LID-based insertion contributes most, a single-branch HNSW with only LID-aware insertion may capture most of the recall improvement with less engineering complexity.","Editorial inference: the skip-bridge rule combines sparsity (LID) and proximity (epsilon), so a natural testable extension is an adaptive threshold that depends on local layer density or query difficulty rather than a fixed T."],"forward_implications":["Practitioners using HNSW could switch to HNSW++ and expect better recall at the same query speed, with faster graph construction.","Because LID is computed offline, the LID-based insertion rule can be layered onto other graph-based ANN indexes without changing their online search step.","The dual-branch construction suggests that per-insertion search cost should scale with half the dataset, which matters more as datasets grow.","The skip-bridge threshold gives a single knob that mainly trades inference latency against number of skips, with accuracy largely unaffected across tested datasets."],"supporting_citations":[{"why":"Defines the original HNSW algorithm, its layer construction, greedy search, and the O(n log n) complexity claim that HNSW++ modifies.","marker":"Malkov & Yashunin, 2020"},{"why":"Supplies the maximum-likelihood estimator formula the paper uses to compute each point's Local Intrinsic Dimensionality.","marker":"Levina & Bickel, 2004"},{"why":"Earlier evidence that insertion order and intrinsic dimensionality affect HNSW recall, motivating LID-based insertion.","marker":"Elliott & Clark, 2024"},{"why":"Establishes the correlation between high local intrinsic dimensionality and outlierness that justifies placing high-LID nodes in upper layers.","marker":"Houle et al., 2018"},{"why":"Documents that HNSW often fails to reach logarithmic complexity in high dimensions, the bottleneck the skip bridges target.","marker":"Lin & Zhao, 2019"},{"why":"Supports the claim that similarity-graph greedy search is vulnerable to local minima, the problem the dual-branch structure addresses.","marker":"Baranchuk et al., 2019"}],"fun_headline_variants":["HNSW++ lifts recall 30%, trims build time 20%","Dual-branch HNSW: 30% recall boost, 20% faster build","HNSW++ gains 30% recall, retains query speed","HNSW++: outlier-aware insertion lifts recall 30%","HNSW++ with skip bridges: recall up 30%, build down 20%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that splitting the dataset into two branches by insertion index actually separates spatial regions, so the two greedy searches explore genuinely different parts of the graph; if insertion order carries no geometric meaning, the dual-branch mechanism may just be two correlated restarts.","fun_headline_variants_meta":{"raw":{"variants":["HNSW++ lifts recall 30%, trims build time 20%","Dual-branch HNSW: 30% recall boost, 20% faster build","HNSW++ gains 30% recall, retains query speed","HNSW++: outlier-aware insertion lifts recall 30%","HNSW++ with skip bridges: recall up 30%, build down 20%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000799,"raw_usage":{"total_tokens":3572,"prompt_tokens":1059,"completion_tokens":2513,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":2408}},"tokens_in":675,"tokens_out":2513,"duration_ms":15922,"temperature":1.0,"reasoning_tokens":2408,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:51:29.847567+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build HNSW++ on the same dataset twice, once with the original insertion order and once with randomly shuffled order, comparing recall and the overlap between the neighbor sets returned by the two branches. If shuffling preserves the gains and the two branches return nearly identical sets, the claimed spatial division by insertion index is not the operative mechanism.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the maximum-likelihood estimator formula the paper uses to compute each point's Local Intrinsic Dimensionality."},{"cited_title":"Learning to route in similarity graphs","cited_arxiv_id":null,"evidence_quote":"Supports the claim that similarity-graph greedy search is vulnerable to local minima, the problem the dual-branch structure addresses."}],"review_version":1}