{"id":"0d41614b-6282-4bd7-b164-4ddaf65c3a2b","arxiv_id":"2502.05575","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"An evaluation of twelve graph-based vector search methods on up to one billion vectors shows that incremental insertion and neighborhood diversification are the design choices that scale best.","lead":"This paper compares twelve graph-based vector search methods on datasets with up to one billion vectors, and groups them into five design families: seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, and divide-and-conquer. It finds that incremental insertion and neighborhood diversification give the best scalability and query efficiency, with ELPIS leading at billion scale.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1B speed claim may conflate ELPIS's multi-threaded query execution with algorithmic design; a controlled thread-count comparison is needed.","rationale":"The reader's weakest assumption correctly identifies the 100-query extrapolation as a statistical representativeness risk. That is a valid concern, but it does not have a known directional bias and does not uniquely target the flagship 1B comparison. The multi-threading issue is more load-bearing because the paper itself states that ELPIS's Figure 16 advantage is 'thanks to its design that supports multi-threading for single query answering.' Without a controlled thread count, the headline 'order of magnitude faster' claim can be explained by hardware utilization alone. This does not invalidate the broader qualitative conclusions: the taxonomy, the distance-calculation comparisons in Sections 4.2 and 4.3, and the 25GB/100GB results are meaningful, and Figure 17 shows ELPIS retaining a lead even against optimized parallel variants. However, the central 1B recommendation is conditional on resolving the thread confound. Since the reader's verdict is already CONDITIONAL, my read does not move it; it sharpens the condition that must be checked.","tokens_in":30647,"tokens_out":6617,"duration_ms":65026,"concrete_test":"Re-run the Deep1B recall-vs-latency experiment (Figure 16) with ELPIS pinned to a single thread (e.g., OMP_NUM_THREADS=1 or CPU affinity), and separately with HNSW and Vamana given the same multi-thread budget as ELPIS; also report distance calculations per query at 0.95 recall. If the wall-clock gap between ELPIS and HNSW/Vamana collapses under equal thread counts, then the order-of-magnitude claim is a parallelism artifact rather than evidence for the II+ND paradigm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The flagship quantitative claim—that ELPIS is up to an order of magnitude faster than HNSW and Vamana at 0.95 recall on Deep1B (Section 4.5, Figure 16)—is not a controlled test of algorithmic paradigm. The text attributes the advantage to 'multi-threading for single query answering,' but the paper does not report a per-method thread budget or core-allocation control for HNSW and Vamana. The setup is a 4-socket Xeon with 112 cores, so ELPIS can consume many cores to answer one query while the default HNSW/Vamana implementations are effectively single-threaded. This conflates parallel hardware utilization with the II+ND design insight. The implementation-impact experiment (Figure 17) compares against ParlayANN's optimized parallel variants, but again no thread-count control is stated, so the confound is not resolved. If the order-of-magnitude gap shrinks or disappears when ELPIS is limited to one thread, the central recommendation for practitioners would rest on an implementation artifact rather than on the paper's design-paradigm claim. The 100-query extrapolation flagged by the reader is a real but secondary issue; the thread confound has a known direction and directly affects the headline 1B result.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper surveys in-memory graph-based approximate vector search, proposes a taxonomy of five design paradigms (seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, and divide-and-conquer), and experimentally evaluates twelve methods on seven real datasets with sizes up to one billion vectors. The main claims are that incremental insertion and neighborhood diversification are the most effective design paradigms, that the choice of the base graph can hurt scalability, and that ELPIS is up to an order of magnitude faster than HNSW and Vamana at 0.95 recall on Deep1B. The paper also isolates the effects of seed selection and neighborhood diversification using custom baselines, and concludes with research directions.","tokens_in":30912,"tokens_out":4898,"duration_ms":43849,"significance":"If the findings hold, this would be a valuable benchmark for practitioners and a useful update to the prior survey [142], with datasets at larger scale, a more detailed taxonomy, and a companion repository with parametrizations. The paper deserves credit for tuning twelve implementations, clearing caches, trimming repeated runs, documenting code modifications, and making artifacts available. The central claim, however, hinges on the ELPIS 1B result, which is currently confounded by parallel hardware utilization and by an unvalidated 100-query-to-1M-query extrapolation.","major_comments":[{"comment":"The claim that ELPIS is up to an order of magnitude faster than HNSW and Vamana at 0.95 recall on Deep1B is not a controlled test of algorithmic design. The text attributes the advantage to 'multi-threading for single query answering,' but the paper does not report a per-method thread budget or core-allocation control. On the 4-socket, 112-core Xeon, ELPIS can consume many cores to answer one query while the default HNSW/Vamana implementations may be effectively single-threaded. Figure 17 compares with ParlayANN's optimized variants, but again no thread-count control is stated. Please provide a controlled comparison (all methods with one thread, and all methods with the same thread budget) or explicitly scope the claim to the default implementations.","section":"Section 4.5, Figure 16"},{"comment":"The text states 'Results with 1 million queries are extrapolated from 100 query sets.' The paper provides no evidence that 100 queries are representative of a 1M-query workload or that distance calculations and timings extrapolate linearly. Figures 6, 16, and 17 present these extrapolated values; under a workload with a different hardness distribution, the reported method ordering, including the ELPIS lead, could change. Please validate the extrapolation on a medium-size workload (e.g., 10K queries) for the main methods or report per-query distributions with confidence intervals.","section":"Section 4.1, Queries"}],"minor_comments":[{"comment":"The sentence 'We consider the baseline method SF which has not been used in the literature before.' appears twice verbatim; the duplicate should be removed.","section":"Section 4.3"},{"comment":"The word 'acccuracy' should be 'accuracy'.","section":"Section 2.1, Summary paragraph"},{"comment":"SPTAG appears in two rows with different ratings; clarify which variant (SPTAG-BKT versus SPTAG-KDT) each row refers to and reconcile the inconsistency.","section":"Table 3"},{"comment":"Figures presenting the extrapolated 1M-query values should label the y-axis as estimated values rather than measured values.","section":"Section 4.1 and Figures 6, 16, 17"},{"comment":"The capitalization of 'Elpis' is inconsistent; use 'ELPIS' throughout.","section":"Figure 11 and Section 4.5"},{"comment":"The values alpha=1.3 and theta=60 are tuned on the same datasets used for the evaluation; state whether this is a held-out tuning set or report sensitivity to these parameters.","section":"Section 4.2"},{"comment":"Despite six repeated runs, the paper reports only trimmed means without any variance measure; for the 100-query workloads, a confidence interval or a spread statistic would help assess the stability of the rankings.","section":"Section 4.1, Procedure"}],"recommendation":"major_revision","confidential_remarks":"The benchmark effort is substantial and the companion repository is a strength. The main risk is that the headline 1B-speed claim conflates parallel implementation quality with algorithmic paradigm; if a controlled thread comparison weakens the ELPIS advantage, the paper's central recommendation would need to be reworded. The omitted proof in Section 3.4 is secondary but should be checked against [3]. The paper fits the journal's scope and, after the confounding issue is addressed, could be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Take a look at this one, but read the 1B speed comparison carefully. The paper is a serious experimental evaluation of twelve graph-based ANN methods, with a five-paradigm taxonomy (seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, divide-and-conquer) that gives the community a shared vocabulary. The strongest part is the controlled isolation: they build the same II base graph and vary only the ND strategy, and similarly compare seed selection strategies on the same graph. That is a genuinely useful way to disentangle design choices, and the results (RND and MOND beat RRND and NoND; SN wins at 1B while KS is better at smaller sizes) are informative and backed by distance-calculation counts. The evaluation goes to 1B vectors on real data, with a companion repo, documented code modifications, and six-repeat trimmed timings. The paper also explains where it disagrees with the prior survey [142], which is the right way to run a follow-up benchmark.\n\nThe soft spot is the headline result on Deep1B. The paper says ELPIS is up to an order of magnitude faster at 0.95 recall 'thanks to its design that supports multi-threading for single query answering.' That is not a controlled test of the algorithmic paradigm. The machine has 112 cores; ELPIS can apparently use many of them to answer one query, while the default HNSW and Vamana implementations are effectively single-threaded. The paper does not report a thread budget or core allocation per method. The implementation-impact experiment (Figure 17) compares against ParlayANN's parallel variants, but still no thread count is stated, so the confound remains. This matters: if the gap shrinks or disappears at one thread per method, the practical recommendation for large collections rests partly on an implementation artifact. The central qualitative claims—II is the most scalable construction paradigm, ND improves query efficiency, the EFANNA base graph hurts NSG/SSG scalability—are supported across multiple datasets and sizes and do not depend on that one figure. But the quantitative 1B ranking is not fully trustworthy as an algorithmic statement.\n\nOther concerns are real but secondary: the 100-query extrapolation to 1M queries is stated honestly but unvalidated; index times are reported without variance; alpha and theta are tuned on the same data being evaluated; and the pruning property proof in Section 3.4 is deferred to the companion repo.\n\nBottom line: this paper deserves a serious referee, and I'd engage with it. The taxonomy and isolation experiments are a real contribution. The referee should request a controlled thread-count comparison, error bars on index times, and a sensitivity check on query-set size. If those come back, the paper is a solid benchmark that belongs in the literature.","headline":"Solid benchmark with a genuinely useful taxonomy, but the 1B speed claim for ELPIS is partly a multi-threading effect that the paper never isolates.","tokens_in":31464,"tokens_out":3014,"would_cite":true,"duration_ms":27696,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Incremental insertion and neighborhood diversification drive billion-scale graph vector search; ELPIS is fastest.","keywords":["vector search","approximate nearest neighbor","graph-based indexing","incremental insertion","neighborhood diversification","seed selection","billion-scale datasets","experimental evaluation"],"falsifier":"Run the same Deep1B benchmark with one million real or adversarially sampled queries instead of extrapolating from 100 queries; if the larger workload includes hard regions that the 100-query set missed, the ordering, and especially ELPIS's order-of-magnitude lead, could change.","tokens_in":1841,"feed_emoji":"⚡","tokens_out":4649,"duration_ms":88264,"temperature":0.7,"pith_summary":"The paper is an experimental study of twelve graph-based approximate nearest-neighbor methods on real datasets up to one billion vectors. It argues that the methods differ along five design paradigms and that two of them, incremental insertion and neighborhood diversification, explain most of the variation in query speed and scalability. The headline quantitative result is that ELPIS, which combines divide-and-conquer with incremental insertion and diversification, is up to an order of magnitude faster than HNSW and Vamana at 0.95 recall on Deep1B. The study also isolates the effect of seed selection and diversification strategies by layering each variant on a common incremental-insertion graph, which allows it to attribute performance differences to design choices rather than implementation details. A skeptical reader should care because the paper replaces contradictory benchmarks with a small set of design principles that predict which methods will scale to 100GB and beyond.","feed_headline":"ELPIS up to 10x faster at 0.95 recall on 1B-vector search","feed_subtitle":"The largest graph-ANN benchmark to date shows which design choices scale and which fall off past 25GB.","key_machinery":"The central machinery is a taxonomy of five design paradigms: seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, and divide-and-conquer. The taxonomy classifies twelve methods and is tested by isolating each strategy on a common incremental-insertion graph, then measuring distance calculations, wall-clock time, accuracy, and memory at scales from 1M to 1B vectors. The shared query algorithm is a beam search, so differences in performance are attributed to graph construction and seed choice. The diversification definitions (relative neighborhood diversification, relaxed relative neighborhood diversification, and maximum-oriented neighborhood diversification) provide the geometric pruning rules that the paper shows are responsible for different graph sizes and search speeds.","core_discovery":"On datasets up to one billion vectors, the paper finds that methods built on incremental insertion and neighborhood diversification scale best and answer queries fastest. HNSW, Vamana, and especially ELPIS are the only methods that build indexes on 100GB and 1B collections within the 48-hour budget, and ELPIS is up to an order of magnitude faster than HNSW and Vamana at 0.95 recall on Deep1B. Neighborhood diversification always improves search, with relative neighborhood diversification (RND) and maximum-oriented diversification (MOND) outperforming the relaxed variant (RRND) and no diversification performing worst. Seed selection affects both querying and indexing: stacked-NSW and k-sampled random seeds are the most efficient, while fixed or medoid seeds are poor. Methods that depend on an expensive base graph such as EFANNA (NSG, SSG) or on neighborhood propagation alone (KGraph, DPG) fail to scale beyond 25GB or 100GB due to memory and build-time constraints.","pith_inferences":["The billion-scale rankings are extrapolated from 100-query workloads, so a million-query workload that includes harder or adversarial queries could change the ordering, particularly the size of ELPIS's lead.","The failure of NSG and SSG appears tied to the EFANNA base graph; replacing that base graph with a scalable incremental-insertion or inverted-index-plus-product-quantization construction could make neighborhood-diversification methods competitive at 100GB and beyond.","The seed-selection experiments suggest that a lightweight data-adaptive seed structure could improve both indexing and query time, especially for out-of-distribution queries where fixed trees degrade.","The five-paradigm taxonomy could be turned into a decision rule mapping dataset size, local intrinsic dimensionality, and recall target to the best paradigm mix; the paper's data provide the ingredients for such a rule."],"forward_implications":["Practitioners should prefer methods that combine incremental insertion with neighborhood diversification (HNSW, Vamana, ELPIS) for large in-memory collections, because these are the only ones that scale past 100GB within the 48-hour build budget.","At 1B scale, ELPIS achieves 0.95 recall up to an order of magnitude faster than HNSW and Vamana, so divide-and-conquer plus parallel per-partition incremental-insertion graphs is currently the fastest recipe.","Among diversification strategies, RND and MOND should be preferred over RRND; using no diversification is worst, and the gap widens as dataset size grows.","Seed selection is not a minor detail: stacked-NSW and k-sampled random seeds are the most efficient, while fixed or medoid seeds are poor, and stacked-NSW wins at billion scale.","Methods relying on expensive base graphs (NSG, SSG, DPG, EFANNA) are limited to 25GB to 100GB, so a scalable base-graph construction would be needed to make those paradigms viable at larger sizes."],"supporting_citations":[{"why":"Defines ELPIS, the divide-and-conquer plus incremental-insertion hybrid that is the top performer on billion-scale datasets.","marker":"[11]"},{"why":"Introduces HNSW, the baseline for incremental insertion with relative neighborhood diversification and stacked-NSW seed selection.","marker":"[97]"},{"why":"Defines Vamana, the relaxed-relative-diversification method that scales to 1B and is a key comparison point.","marker":"[129]"},{"why":"Introduces NSG, which applies diversification to an EFANNA base graph and shows the scalability limits of the base graph choice.","marker":"[54]"},{"why":"Defines EFANNA, the base graph whose memory footprint prevents NSG, SSG, and related methods from scaling beyond 25GB to 100GB.","marker":"[52]"},{"why":"The previous survey on graph-based ANN that this paper extends and corrects for small datasets and different rankings.","marker":"[142]"},{"why":"Provides the benchmarking methodology and query conventions used to compare approximate nearest neighbor algorithms.","marker":"[8]"},{"why":"Supplies optimized implementations used in the implementation-impact experiments on Deep1B.","marker":"[98]"}],"fun_headline_variants":["ELPIS 10x faster on billion-scale vector search","Largest graph-ANN benchmark: ELPIS up to 10x faster","Billion-scale vector search: ELPIS up to 10x faster","ELPIS: 10x faster than HNSW at 1B-scale vector search","Graph search at 1B vectors: ELPIS 10x faster than HNSW"],"cache_read_input_tokens":33536,"weakest_assumption_plain":"The rankings rest on the assumption that a 100-query workload represents the full distribution of queries a system would see in practice; if the 100 queries under-sample hard regions or adversarial cases, the reported ordering of methods could change.","fun_headline_variants_meta":{"raw":{"variants":["ELPIS 10x faster on billion-scale vector search","Largest graph-ANN benchmark: ELPIS up to 10x faster","Billion-scale vector search: ELPIS up to 10x faster","ELPIS: 10x faster than HNSW at 1B-scale vector search","Graph search at 1B vectors: ELPIS 10x faster than HNSW"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001681,"raw_usage":{"total_tokens":6670,"prompt_tokens":958,"completion_tokens":5712,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":5605}},"tokens_in":574,"tokens_out":5712,"duration_ms":37120,"temperature":1.0,"reasoning_tokens":5605,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T18:47:58.619753+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same Deep1B benchmark with one million real or adversarially sampled queries instead of extrapolating from 100 queries; if the larger workload includes hard regions that the 100-query set missed, the ordering, and especially ELPIS's order-of-magnitude lead, could change.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Vamana, the relaxed-relative-diversification method that scales to 1B and is a key comparison point."}],"review_version":1}