{"id":"faa1fcb2-e5e0-4d54-bc62-f5a15fe97225","arxiv_id":"2509.05750","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"In head-to-head tests on up to one billion vectors, graph-based vector search methods that use incremental insertion and neighborhood diversification (especially RND and MOND) beat propagation- and most divide-and-conquer-based methods on the workloads tested.","lead":"This paper ran head-to-head tests of twelve graph-based methods for finding similar items in huge vector datasets (up to a billion items). The results show that building the graph by inserting items one at a time and diversifying the connections usually works best, while some popular base graph choices do not scale.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Comparability of implementations is the paper's own acknowledged weak spot; Figure 21 shows optimization changes rankings, so the central II+ND dominance claim may be an engineering artifact.","rationale":"The reader's weakest assumption—that the twelve implementations are comparable proxies—is exactly the load-bearing point, and I find it reinforced by the paper's own Section B/Figure 21 evidence. This is not a manufactured concern; the paper explicitly acknowledges the ideal of uniform re-implementation and instead relies on 'carefully adjusting each implementation.' The internal evidence that optimization changes scalability and query-time rankings makes the proxy assumption not merely hypothetical but demonstrably fragile. The concrete test I propose would settle whether the central claim survives a fair comparison. I do not see a separate, more load-bearing objection: the 100-query extrapolation is real but secondary, and the placeholder artifact URL affects reproducibility, not the correctness of the qualitative ranking. The reader's CONDITIONAL verdict is therefore appropriate; my stress-test does not move it.","tokens_in":23862,"tokens_out":2704,"duration_ms":29878,"concrete_test":"Re-run the billion-scale query and indexing comparisons (Figure 20 and Section B.3) using the ParlayANN-optimized implementations of HNSW, Vamana, and HCNNG alongside the official ELPIS, all under the same hardware and query protocol. If ELPIS remains fastest and the II+ND methods still dominate while NP/DC methods still fail to scale, the central claim is supported. If optimized baselines close the gap or change the ranking, the paper's conclusions must be revised to reflect implementation sensitivity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that II+ND methods (HNSW, VAMANA, ELPIS) dominate and that NP-based methods do not scale—rests on treating the twelve implementations as faithful, equally-optimized proxies for their design paradigms. The paper admits this is not the case (Appendix B: 'Ideally, all methods would be re-implemented from scratch... but this is highly time-consuming.'). More importantly, the paper's own Figure 21 demonstrates that implementation quality materially changes performance: optimized ParlayANN versions of Vamana and HNSW are faster than their original counterparts at recall <0.97, and HCNNG Opt scales to 1B whereas the original HCNNG failed beyond 25GB. This is direct evidence that the observed rankings—especially the superiority of ELPIS (authored by the same group) and the failure of NP-based methods to scale—could be driven by engineering asymmetry rather than by the algorithmic paradigms the taxonomy claims to isolate. Because the headline conclusions are qualitative dominance claims (Section 4, Conclusions), the absence of a uniform-implementation control leaves the central inference underdetermined. The 100-query extrapolation is a secondary issue; the comparability problem is load-bearing because it undermines the attribution of performance differences to paradigm rather than code quality.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a taxonomy of five design paradigms for in-memory graph-based approximate nearest neighbor search—seed selection (SS), neighborhood propagation (NP), incremental insertion (II), neighborhood diversification (ND), and divide-and-conquer (DC)—and reports an experimental comparison of twelve public graph-based ANN implementations on seven real and three synthetic datasets up to 1B vectors. The central claims are that II+ND designs (HNSW, VAMANA, ELPIS) dominate in query performance and index efficiency, that NP-based methods with expensive base graphs do not scale, that RND and MOND are the best ND strategies, and that on billion-scale data hierarchical seed selection (SN) becomes preferable to k-random sampling (KS). The paper also proposes research directions and gives implementation-specific recommendations.","tokens_in":24175,"tokens_out":5111,"duration_ms":56612,"significance":"If the claims hold, the paper provides a useful systematization of a fragmented literature and the largest comparative evaluation of graph-based ANN paradigms to date. Strengths include the breadth of datasets (up to 1B vectors), the use of public implementations, controlled cache behavior, a 48-hour indexing limit, repeated runs with trimmed means for query workloads, and release of code. For the ND and SS ablations, the paper reports both wall-clock time and distance calculations, which is the right kind of evidence for isolating algorithmic effects. However, the central paradigm-level conclusions rest on an implementation-comparability assumption that the paper itself concedes is imperfect (Appendix B). Because Figure 21 shows that implementation optimization changes rankings and even scalability, the significance of the headline conclusions is conditional until this confound is addressed.","major_comments":[{"comment":"The paper states: \"Ideally, all methods would be re-implemented from scratch to ensure uniformity, but this is highly time-consuming.\" Yet Section 4 and Conclusions make paradigm-level dominance claims (e.g., \"II+ND designs dominate\", \"NP-based methods do not scale\"). Figure 21 demonstrates that optimized ParlayANN versions of Vamana and HNSW are faster than their original counterparts at recall <0.97, and HCNNG Opt scales to 1B whereas the original failed beyond 25GB. This is direct evidence that the observed ranking can be driven by engineering asymmetries rather than by the algorithmic paradigms. The authors should provide a common-codebase control for at least the leading representatives, or explicitly restrict the conclusions to the specific implementations tested, or provide quantitative evidence that engineering differences are second-order (e.g., distance calculations for all SOT","section":"Appendix B, \"Implementations\" and Figure 21"},{"comment":"Section 3.1 says distance calculations are measured for both indexing and query answering, but Appendix B states that search time is reported and that reporting distance calculations is planned future work. The SOTA comparisons in Figures 7 and 16-20 appear to use wall-clock time only. Since the paper's thesis is about algorithmic paradigms rather than engineering quality, wall-clock time conflates the two. Please report distance-calculation curves for the SOTA comparison wherever possible, and clearly label which figures use time and which use distance calculations.","section":"Section 3.1, \"Measures\" vs Appendix B, \"Comparison\""},{"comment":"Each query workload consists of 100 queries, and the text says \"results for 1M queries are extrapolated from these workloads.\" No statistical procedure is described. All recall-time and recall-distance curves, including the high-recall conclusions in Figures 9 and 10, are based on 100 query points. Please provide confidence intervals or per-query distributions, justify the extrapolation, or relabel the figures as 100-query results. At minimum, the paper should state the uncertainty so that the reported ranking at recall 0.99 is not over-interpreted.","section":"Section 3.1, \"Queries\""},{"comment":"Section 2.4 and the taxonomy classify DPG as using MOND. However, Appendix A explicitly says that DPG's publicly available implementation uses RND rather than MOND. Therefore the DPG experiments do not evaluate the MOND strategy attributed to it. The MOND evidence then rests only on the synthetic ND ablation and SSG. Please correct the classification or rerun a MOND-compliant DPG implementation; otherwise the claim that MOND is among the best ND techniques is not fully supported by the SOTA comparison.","section":"Appendix A, \"DPG\" and Section 2.4"},{"comment":"The paper's treatment of HCNNG is internally inconsistent. Section 4 says \"The assessment of HCNNG is based on the optimized parlayANN implementation,\" while Appendix B.3 reports that HCNNG takes over 24 hours on 25GB and was excluded from larger datasets, and Figure 21 introduces HCNNG Opt separately. The reader cannot tell whether Table 1 and the recommendations in Figure 8 refer to the original or optimized implementation. Please label every HCNNG result with its exact version and discuss both variants consistently.","section":"Section 4, Table 1, and Appendix B.3"}],"minor_comments":[{"comment":"The paragraph beginning \"In these experiments, we focus on the four most common SS strategies...\" is duplicated verbatim. Please remove the duplicate.","section":"Appendix B.2"},{"comment":"The text refers to \"Fig.4a\" and \"Fig.4b\" when discussing seed selection, but the seed-selection results appear in Figure 5, while Figure 4 shows ND results. Update the cross-references.","section":"Section 3.3"},{"comment":"Several references are given only as \"url, 2025\" (e.g., the proof in Section 2.4, the artifacts, the supplementary results). These placeholders should be replaced with actual URLs or repository identifiers.","section":"Sections 2.4, 3.1, Appendix throughout"},{"comment":"The caption says \"Indexing + 10K queries,\" but the methodology Section 3.1 specifies 100-query workloads. Clarify the figure's workload size or correct the caption.","section":"Figure 8"},{"comment":"The reference \"Team, T. P. Parlayann: A deep learning library for parallel computation\" appears misattributed; ParlayANN should be cited via Manohar et al. (2024) or the official repository with the correct author list.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The experimental effort is substantial, and the taxonomy is a useful contribution even if the dominance claims need to be softened or better supported. The comparability problem is the central issue: because the paper is explicitly an experimental evaluation, the acknowledged lack of uniform reimplementation is not a peripheral caveat but a load-bearing threat to the paradigm-level conclusions. I would welcome a revision that either adds a common-codebase control for the leading methods or restricts the conclusions to the tested implementations. The paper's heavy citation of the authors' own systems is not disqualifying, but the consistent lead of ELPIS is exactly where an independent implementation or a distance-calculation cross-check would add the most credibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things before reading this paper. First, it is a workshop condensation of a SIGMOD 2025 paper by the same group; the abstract and references say so explicitly. If you have seen that extended version, there is little new here. Second, the central claim that incremental insertion plus neighborhood diversification (HNSW, Vamana, ELPIS) dominates is plausible but underdetermined by the evidence as presented, because the comparison rests on unequal implementations.\n\nWhat the paper does well: it runs twelve methods across seven datasets up to 1B vectors, uses public C/C++ implementations, reports wall-clock and distance calculations for the ablations, and proposes a five-paradigm taxonomy (SS, NP, II, ND, DC) that is a reasonable way to organize the design space. The finding that NP-based methods with expensive base graphs do not scale beyond a few hundred million vectors is consistent with what others have reported. The ablation isolating ND and seed selection on a common HNSW base is a nice idea and the ranking (RND/MOND over RRND, SN/KS over MD/SF) is believable.\n\nThe soft spots are real. The paper admits in Appendix B that ideally all methods would be re-implemented from scratch, but that was too time-consuming. That is exactly where the load-bearing inference lives. Figure 21 is direct evidence that implementation quality moves rankings: ParlayANN versions of Vamana and HNSW beat the authors' versions at recall below 0.97, and HCNNG Opt scales to 1B while the original fails beyond 25GB. So the observed dominance of ELPIS (the authors' own system) and the failure of NP methods to scale could be partly engineering asymmetry, not paradigm. Also, the artifact link is a literal placeholder; the text repeatedly says '(url, 2025)' where a DOI or repository should be. And the 100-query workloads are extrapolated to 1M queries without any statistical support. None of these are fatal to the qualitative conclusions, but they prevent the paper from being the definitive comparison it claims to be.\n\nWho is this for? Practitioners who want a quick overview of graph-based ANN design choices and researchers working on index construction. A serious referee would be justified in asking for the artifact, error-bar-aware measurements on larger query sets, and a direct comparison against at least one uniform re-implementation of a few methods. I would not desk-reject it, but I would not accept it in its current form.","headline":"Solid experimental survey but the central dominance claim is undercut by implementation asymmetry and the artifact link is a placeholder.","tokens_in":24705,"tokens_out":2532,"would_cite":false,"duration_ms":25822,"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":"A 12-method test at up to 1 billion vectors finds HNSW, Vamana, and ELPIS lead because of incremental insertion plus neighborhood-diversity pruning.","keywords":["graph-based vector search","approximate nearest neighbor","incremental insertion","neighborhood diversification","seed selection","divide-and-conquer","billion-scale evaluation","in-memory indexing"],"falsifier":"A decisive test would reimplement the top trio (HNSW, Vamana, ELPIS) and the main NP and multi-tree rivals (NSG, SSG, KGraph, SPTAG) from one codebase with uniform engineering and rerun the Deep and Sift 100GB-1B experiments. If a neighborhood-propagation method on a cheaply built base graph matches the II+ND trio, or if equal optimization shifts the billion-scale ranking, the central claim is falsified. A cheaper check: use real million-query streams instead of 100-query extrapolations to see whether the billion-scale preference for hierarchical over k-random seeds holds.","tokens_in":2070,"feed_emoji":"🔍","tokens_out":5061,"duration_ms":204962,"temperature":0.7,"pith_summary":"This paper tries to settle which algorithmic design choices make in-memory graph-based approximate vector search fast and scalable: it runs 12 state-of-the-art methods on 7 datasets up to 1 billion vectors, isolating five construction paradigms (seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, divide-and-conquer) in a controlled testbed. The central claim is that the best methods use incremental insertion for scalability to 100GB and beyond, and neighborhood diversification for cheap queries, with RND and MOND as the best pruning rules. If correct, new in-memory indexes should be assembled from II+ND plus lightweight hierarchical seeds instead of expensive base-graph pipelines, and divide-and-conquer should be reserved for hard datasets and noisy workloads.","feed_headline":"1B vectors: incremental build plus diversified edges wins search","feed_subtitle":"A 12-method test on up to 1B vectors pinpoints which design choices actually scale.","key_machinery":"The carrying object is a five-paradigm taxonomy (seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, divide-and-conquer) used as a controlled testbed: a basic II graph (HNSW's base construction) on which each seed-selection and diversification strategy is swapped in independently. The load-bearing components are the named pruning rules RND (keep a candidate neighbor only if no already-kept neighbor is closer to it), RRND (the same test relaxed by a factor alpha >= 1), and MOND (keep candidates whose edge direction differs from existing neighbors by at least a 60-degree angle), plus seed strategies SN (hierarchical stacked-NSW layers) and KS (k rando","core_discovery":"The paper establishes that construction paradigm, not the abstract graph family, determines performance. Across 12 methods, only HNSW, Vamana, and ELPIS index and search efficiently at billion scale, and they are precisely the ones that combine incremental insertion (II) with neighborhood diversification (ND). RND and MOND prune best, followed by RRND, while no diversification is worst; and hierarchical stacked-NSW seeds beat k-random sampling at 1B scale. Neighborhood-propagation methods (KGraph, NSG, SSG) fail past 100GB because their expensive base graphs bury them in indexing time and memory.","pith_inferences":["The study isolates only seed selection and diversification on a single II+RND base; an equally controlled swap of DC partitioning and NP initialization is a natural next experiment to test causal generality.","The billion-scale seed-selection conclusion rests on 100-query extrapolated workloads; a real million-query run with out-of-distribution queries would verify whether the hierarchical-vs-random gap widens.","The RND-over-MOND-over-RRND ranking is established for in-memory Euclidean search only; the paper itself notes denser relaxed-alpha graphs help when I/O dominates, so disk-based re-runs map the boundary.","Quantifying the actual edge-overlap among RND, RRND, and MOND at billion scale would reveal whether RND's lead is structural or just stricter pruning."],"forward_implications":["New in-memory graph indexes should be built with incremental insertion plus RND or MOND pruning; that combination is what indexes and queries past 100GB.","At billion scale, seed selection matters: hierarchical stacked-NSW entry points save roughly 10 million distance calculations over k-random sampling at 0.99 recall on Deep1B.","For hard datasets (high local intrinsic dimensionality, low contrast) and noisy queries, divide-and-conquer graphs on clustered subsets outperform single-graph beam search.","Indexing time is dominated by base-graph construction: ELPIS indexes about 2x faster than HNSW and 2.7x faster than Vamana at billion scale, while SPTAG's multi-tree construction is roughly 24x slower.","Because ND and SS cut both wall-clock time and distance computations, the paper argues these design choices double as energy-efficiency levers."],"supporting_citations":[{"why":"Supplies HNSW, the II+RND method that ranks among the best three; its base graph is the isolation testbed.","marker":"(Malkov & Yashunin, 2020)"},{"why":"Supplies ELPIS, the divide-and-conquer plus II+ND method that wins indexing speed and query performance at billion scale.","marker":"(Azizi et al., 2023)"},{"why":"Supplies Vamana and the RRND relaxation rule, showing ND without incremental insertion can still reach the top tier.","marker":"(Subramanya et al., 2019)"},{"why":"Supplies NSG, whose RND-diversified graph with EFANNA base causes the scaling failure of NP methods.","marker":"(Fu et al., 2019)"},{"why":"Supplies EFANNA, the base graph whose construction cost and footprint anchor the claim that base-graph choice hurts scalability.","marker":"(Fu & Cai, 2016)"},{"why":"Supplies DPG and the MOND edge-angle pruning rule, one of the two diversification techniques found most effective.","marker":"(Li et al., 2019)"},{"why":"Supplies SSG, confirming MOND behavior on an EFANNA base at 1M and 25GB scale.","marker":"(Fu et al., 2021)"},{"why":"Supplies KGraph/NNDescent, the neighborhood-propagation paradigm whose methods perform worst and are excluded from large-scale runs.","marker":"(Dong et al., 2011)"},{"why":"The only prior dedicated comparison, at only about 1M vectors, whose small-scale conclusions this study revises.","marker":"(Wang et al., 2021)"},{"why":"Supplies SPTAG, the divide-and-conquer comparator whose much slower indexing supports the indexing-efficiency ranking.","marker":"(Chen et al., 2018)"}],"fun_headline_variants":["At 1B vectors, only incremental insertion plus diversification scales","Graph search at 1B: construction method matters most","Why most graph vector indexes fail at billion scale","Incremental insertion and diversified edges: the 1B vector recipe","12 methods, 1B vectors: the winning design is clear"],"cache_read_input_tokens":26368,"weakest_assumption_plain":"The evaluation assumes the twelve implementations, after the authors' adjustments, are comparable proxies for the algorithms, so observed differences reflect design paradigm rather than engineering quality; the paper itself concedes full re-implementation is not done, and 100-query workloads are extrapolated to 1M-query behavior.","fun_headline_variants_meta":{"raw":{"variants":["At 1B vectors, only incremental insertion plus diversification scales","Graph search at 1B: construction method matters most","Why most graph vector indexes fail at billion scale","Incremental insertion and diversified edges: the 1B vector recipe","12 methods, 1B vectors: the winning design is clear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001389,"raw_usage":{"total_tokens":5440,"prompt_tokens":706,"completion_tokens":4734,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":450,"completion_tokens_details":{"reasoning_tokens":4649}},"tokens_in":450,"tokens_out":4734,"duration_ms":31371,"temperature":1.0,"reasoning_tokens":4649,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:05:21.618215+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A decisive test would reimplement the top trio (HNSW, Vamana, ELPIS) and the main NP and multi-tree rivals (NSG, SSG, KGraph, SPTAG) from one codebase with uniform engineering and rerun the Deep and Sift 100GB-1B experiments. If a neighborhood-propagation method on a cheaply built base graph matches the II+ND trio, or if equal optimization shifts the billion-scale ranking, the central claim is falsified. A cheaper check: use real million-query streams instead of 100-query extrapolations to see whether the billion-scale preference for hierarchical over k-random seeds holds.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies HNSW, the II+RND method that ranks among the best three; its base graph is the isolation testbed."},{"cited_title":"J., Kadekodi, R., Krishaswamy, R., and Simhadri, H","cited_arxiv_id":null,"evidence_quote":"Supplies Vamana and the RRND relaxation rule, showing ND without incremental insertion can still reach the top tier."},{"cited_title":"Efficient k-nearest neighbor graph construction for generic similarity measures","cited_arxiv_id":null,"evidence_quote":"Supplies KGraph/NNDescent, the neighborhood-propagation paradigm whose methods perform worst and are excluded from large-scale runs."},{"cited_title":"SPTAG: A library for fast approximate nearest neighbor search, 2018","cited_arxiv_id":null,"evidence_quote":"Supplies SPTAG, the divide-and-conquer comparator whose much slower indexing supports the indexing-efficiency ranking."}],"review_version":1}