{"id":"bde4fb1c-6eb8-4cd8-9b56-3741ff951a7f","arxiv_id":"2607.27623","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"crEG, an even-regular undirected proximity graph with continuous edge refinement, matches or beats HNSW/NSG/ONNG in standard and exploratory query settings while building 2-3x faster.","lead":"This paper introduces crEG, a graph-based approximate nearest neighbor search index built with even-regular undirected edges and an optional edge-refinement pass. On standard benchmarks it claims up to 2.5x faster search at 99% recall, plus a new evaluation protocol for exploration-style 'more like this' queries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 4's own Step (3) admits vertices 'may become unreachable', directly contradicting the claimed 'guarantee graph connectivity at any time' for concurrent queries; the window is unquantified.","rationale":"I agree with the reader's identification of the weakest assumption. The paper's own text—Algorithm 4, Step (3)—directly contradicts the 'guarantee graph connectivity at any time' claim, and the missing quantification and lack of a concurrency analysis are clear omissions. This is a load-bearing concern because it affects a stated contribution and the practical claim that edge optimization can run concurrently with queries. However, the central search-speed and construction-speed comparisons are measured on the final graph and are not necessarily affected by transient disconnections during optimization. Thus the paper remains conditionally acceptable rather than rejected. My concrete test would settle whether the concern actually lands by checking for disconnection and measuring concurrent-query degradation. No change to the reader's verdict is needed.","tokens_in":15937,"tokens_out":6880,"duration_ms":65353,"concrete_test":"Instrument Algorithm 4 to run a connectivity check (BFS or union-find) after every graph modification, especially after Step (3)'s edge swap, on a small even-regular graph (e.g., 10k random SIFT1M points). If the graph is found disconnected before Step (4) or Step (6) completes, the 'guarantee graph connectivity at any time' claim is false. Additionally, run a concurrent workload: one thread performs RangeSearch queries seeded near vA/vB while another thread executes optimizeEdge; measure the fraction of queries that fail to return k results or whose recall drops below a baseline. If this fraction is nonzero, the production-parallel refinement claim fails. Also inspect the reference implementation to see whether a global lock makes the swap atomic; if so, the paper must state this explicitly and define 'at any time' accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Section 3.1 claim both manipulation algorithms 'guarantee graph connectivity at any time.' Section 3.3 further claims edge optimization 'can still operate in parallel with regular user search queries in a production system.' However, Algorithm 4, Step (3) (Edge Swap) explicitly states: 'The vertices {vB, vC} may become unreachable for vA and vD.' This is an admission of a transient disconnection. Step (4) is only a 'Restore' attempt, and Step (6) reverts if no solution is found, meaning the graph is not guaranteed connected during the optimization. If concurrent queries are executed in this window, they can be trapped in a component, fail to reach relevant vertices, or return incomplete results. The paper neither quantifies the duration or frequency of these disconnections nor proves that queries are unaffected. Thus the connectivity guarantee—a stated contribution and the basis for the production-parallel refinement claim—is not established. This does not directly invalidate the offline QPS/construction comparisons, but it weakens a headline property and the claimed ability to refine edges while serving queries.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes crEG, an even-regular undirected proximity graph for approximate nearest-neighbor search (ANNS) and exploratory search. Construction is incremental: a new vertex is attached by removing existing edges and connecting it to neighbors found by range search, while an optional edge-optimization stage swaps edge endpoints to reduce the average neighbor distance δN. The authors claim that both manipulation algorithms preserve connectivity at all times, that the unoptimized graph (EG) is 2–3 times faster to construct than current state-of-the-art graphs, and that the optimized graph (crEG) achieves up to 250% higher QPS at recall@100=0.99 on GloVe, with additional gains in an exploratory-search protocol. Experiments compare against HNSW, NSG, NSSG, kGraph, EFANNA, DPG, and ONNG on Audio, SIFT1M, Deep1M, and GloVe.","tokens_in":16275,"tokens_out":4842,"duration_ms":50553,"significance":"If the results hold, the paper offers a useful construction-speed/search-speed trade-off for graph-based ANNS, and its exploration protocol is a valuable addition to the evaluation toolkit. The method is simple and does not require a hierarchical structure or a separate VP-tree, and the paper includes ablation studies (e.g., random graph plus edge optimization) that isolate the contribution of the proposed components. However, the two headline theoretical contributions—connectivity at any time and the ability to run edge optimization in parallel with live user queries—are undermined by the algorithm's own statements, and the empirical scalability claim is presented as a complexity result without a derivation. The performance comparisons also lack variance estimates and full hyperparameter disclosure.","major_comments":[{"comment":"The abstract and §3.1 claim both manipulation algorithms 'guarantee graph connectivity at any time,' and §3.3 states the optimizer 'can still operate in parallel with regular user search queries in a production system.' Yet Algorithm 4, Step (3) explicitly states: 'The vertices {vB, vC} may become unreachable for vA and vD.' Step (4) is only an attempt to restore connectivity, and Step (6) reverts changes only after several iterations. Thus the graph is not guaranteed connected during the optimization process. The manuscript neither quantifies the disconnection window nor proves that a concurrent RangeSearch cannot be trapped in a component or return incomplete results. This directly contradicts a stated contribution. Please either provide a proof that the intermediate states are connected, or empirically bound the disconnection duration and its effect on concurrent searches, or remove t","section":"§3.3, Algorithm 4, Step (3)"},{"comment":"The paper states the search time complexity 'can be expressed as O(n^{1/9} log(n^{1/9}))' and further extrapolates to a 1-billion-point dataset ('about 6.6 ms'). This appears to be a curve fit to measured points, not a complexity derived from the algorithm's structure. The fitted curves in Fig. 6 include arbitrary prefactors (e.g., 'n^(1/9)*log(n^(1.2/9))*600') with no residuals or confidence intervals. As presented, this is an empirical scaling observation, not an algorithmic complexity bound. Please either derive the exponent from the search/insertion process or explicitly label it as an empirical fit and provide the supporting data, error bars, and extrapolation caveats.","section":"§5.1, Fig. 6 and Eq. (4)"},{"comment":"The empirical claims are the central evidence for the paper's headline results, but the evaluation reports single runs without standard deviations or error bars, and the baseline hyperparameters are only 'documented on our project page' rather than in the paper or an appendix. Given that the claimed speedups are large (up to 250% on GloVe) and the experimental setup includes a reduced serial-scan curve with unspecified reduction, the reported numbers are not fully reproducible from the manuscript. Please provide multiple runs with variance estimates for the main QPS/recall comparisons, and include all hyperparameters (construction and search) for all methods in the paper.","section":"§4.1 and Table 2"}],"minor_comments":[{"comment":"The text refers to 'Figure 2' when discussing exploration curves; this should be Figure 5.","section":"§4.3, last paragraph"},{"comment":"The abstract and §4.1 refer to 'SSG' while the rest of the paper uses NSSG; please make the naming consistent.","section":"Throughout"},{"comment":"The table formatting appears broken in places (especially the EG and crEG rows), making the reported memory/timing values difficult to parse. Please reformat and double-check the alignment.","section":"Table 2"},{"comment":"The sentence 'The Audio dataset is an outlier due to its smaller size, resulting in less pronounced differences' is speculative without supporting evidence; please either provide a quantitative justification or soften the claim.","section":"§4.1"},{"comment":"The serial scan curve uses a 'reduced base data set' but no reduction factor or procedure is given. Please specify the subset size and selection scheme.","section":"§4.1"},{"comment":"The paper lists four neighbor selection schemes (A–D) but does not provide a table of the dataset-dependent choices used in the experiments. Since scheme choice is a hyperparameter, it should be disclosed for each dataset.","section":"§3.2"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The paper is a solid systems contribution, and the offline performance comparisons may well be reproducible given the project code. The main blocker is the connectivity guarantee: Algorithm 4's own Step (3) explicitly admits a transient disconnection, which contradicts the 'guarantee connectivity at any time' and 'parallel with user queries' claims made in the abstract and §3.3. This is not an internal inconsistency in the offline results, but it is a load-bearing part of the paper's stated contributions. The empirical scalability 'complexity' is also a curve fit, not a proof. I recommend major revision: the authors should either repair or qualify these claims, and add variance estimates for the headline speedups."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuine improvement in graph-based ANNS construction speed with competitive search speed, and the exploratory-search evaluation is useful. The connectivity guarantee, however, is not established; the paper's own Algorithm 4 admits vertices 'may become unreachable' during edge swaps. That is a real hole in a headline claim, not a nitpick.\n\nWhat's new: the even-regular incremental construction (crEG/EG), the average-neighbor-distance (δN) metric for guiding edge swaps, and the exploratory-search protocol where queries are graph vertices with the seed at the query. The construction is 2–3x faster than HNSW/NSG/SSG, and search speed improvements up to 250% on GloVe are plausible given the reported curves. The δN metric is a reasonable heuristic, and the ablation in Figure 7 shows it steering edge optimization works. That is solid evidence.\n\nSoft spots: three. (1) The connectivity guarantee. Section 3.1 proves 2-edge connectivity for a static Eulerian graph, but the manipulation algorithms are claimed to preserve it. Algorithm 4's Step (3) explicitly allows transient disconnection, with only a 'restore' attempt and a revert if none is found. The paper never bounds the duration or probability of that window, so the production-parallel refinement claim rests on an unquantified risk. (2) The scaling law O(n^{1/9} log n) is an empirical fit, not a derived bound. The caption shows a fitted constant (600) and a 'DEG log(n)/1.5' curve; that is a description of the data, not a complexity proof. (3) No error bars and baseline hyperparameters from a project page we can't access. These are reportable weaknesses but not fatal: the main QPS comparisons are consistent across four datasets and the effect is large.\n\nI don't think the central performance claim is invalidated. The connectivity issue is the main thing that needs a fix or a qualification. The paper deserves a serious referee; it has new algorithmic content and enough evidence to be worth engaging with. For a reading group, it's a good example of how to present construction/search trade-offs, but I'd pair it with a critical note on the guarantees.","headline":"A solid incremental ANNS paper with real contributions, but the 'connectivity at any time' guarantee is contradicted by the paper's own algorithm.","tokens_in":16692,"tokens_out":1460,"would_cite":true,"duration_ms":14111,"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":"This paper claims that a continuously refined even-regular graph, crEG, achieves up to 250% higher search throughput than state-of-the-art proximity graphs at 99% recall, while its unrefined version is 2–3 times faster to construct and both","keywords":["approximate nearest neighbor search","proximity graph","even-regular graph","exploratory search","continuous edge optimization","average neighbor distance","multimedia retrieval","graph construction"],"falsifier":"Instrument Algorithm 4 while running on SIFT1M or GloVe: during each optimization iteration, immediately after Step (3) of an edge swap, issue a range search from a random vertex to a random target and check whether the search can reach the target within a fixed hop budget. If even a small percentage of such concurrent searches fail to complete, the 'guarantee graph connectivity at any time' claim is false. Separately, re-running the GloVe experiment with concurrent edge optimization and without it should show crEG still beats HNSW by 250% at recall@100=0.99; if the gap shrinks substantially u","tokens_in":15848,"feed_emoji":"🔍","tokens_out":3180,"duration_ms":35569,"temperature":0.7,"pith_summary":"Approximate nearest neighbor search underpins multimedia retrieval, but graph-based indexes are often slow to build and are evaluated only for query points outside the database. The authors propose crEG, an even-regular undirected graph that is constructed incrementally and can be continuously refined by swapping edges while serving searches. They show that this design leads to state-of-the-art search speed, especially on high-dimensional datasets, with dramatically lower construction time. They also introduce a protocol for 'exploratory search' where the query is an indexed item, and show that crEG is up to 50% more efficient there, a setting in which ordinary ANNS effectiveness does not translate directly.","feed_headline":"Even-degree graph with live edge repair runs 250% faster","feed_subtitle":"A continuously refined proximity graph builds up to 3x faster and stays connected for exploratory browsing.","key_machinery":"The central objects are the even-regular undirected graph (every vertex has exactly d neighbors, d even) and the Average Neighbor Distance δN, a metric that sums the distances from each vertex to its neighbors. Because swapping endpoints of two edges only changes δN by comparing sums of edge weights, δN offers a cheap, locally sensitive signal for deciding which edges to replace—unlike graph quality, which is insensitive to such small changes. Construction and optimization both consist of carefully orchestrated edge removals and additions that preserve even regularity and, the authors argue, connectivity. The even degree also guarantees an Eulerian cycle, giving every vertex two edge-disjoin","core_discovery":"crEG maintains a fixed even degree per vertex, which makes the graph Eulerian and 2-edge-connected, and guides all edge changes by a new metric, the Average Neighbor Distance (δN), that is sensitive to small local swaps. New vertices are added by performing a range search and replacing d/2 existing edges with d new ones, in a way that approximates a Monotonic Relative Neighborhood Graph. A separate continuous edge-optimization routine can then iteratively improve the graph in the background, reducing δN and increasing search efficiency. Experiments show that the unoptimized EG builds 2–3 times faster than HNSW, NSG, and SSG while remaining competitive, and that the optimized crEG reaches up","pith_inferences":["The Average Neighbor Distance metric, because it is locally computable from edge weights, could be adopted by other graph-construction methods as a cheaper substitute for graph quality, independent of the rest of crEG.","The paper's finding that standard ANNS efficiency does not transfer to exploratory search suggests that production systems with item-based recommendations should benchmark with seeded queries; one can test this hypothesis by running the same protocol on other graph families not in the original comparison.","The connectivity-at-any-time claim is the weakest link: Algorithm 4 explicitly states that vertices {vB, vC} 'may become unreachable' during a swap. A testable extension would instrument the optimization loop and count transient disconnections, then measure whether concurrent searches ever fail during that window.","The stated complexity O(n^{1/9} log n) for search and insertion is derived empirically on SIFT-like data; an obvious stress test is to repeat the scalability experiment on datasets with higher local intrinsic dimension (e.g., LID > 25), where the constants could degrade the predicted 6.6 ms insertion time."],"forward_implications":["If the construction-time claim holds, multimedia indexes can be built incrementally in near real time; the paper estimates that adding a vertex to a billion-point SIFT index would take roughly 6.6 ms on the test hardware.","The 250% search-speed gain at 99% recall on high-dimensional embeddings would make high-accuracy ANNS practical in latency-sensitive production systems, where recall targets of 0.99 are often considered too expensive.","The exploratory-search protocol, treating indexed items as queries with the query vertex as the seed, could become a standard evaluation for recommendation-style browsing, revealing behavior that standard ANNS benchmarks miss.","The continuous edge-optimization algorithm is designed to run in parallel with user queries, so an index could improve over time without downtime, effectively self-tuning the graph as it serves traffic.","The even-regularity and connectivity properties are prerequisites for future dynamic ops, specifically vertex deletion, which the paper identifies as open future work."],"fun_headline_variants":["Even-degree graph builds 3x faster, stays connected for exploratory search","crEG graph: even-degree, always connected, builds 3x faster","Even-degree graph keeps connectivity while building 2-3x faster","Exploratory search gets connected graph that builds 3x faster"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the continuous edge-optimization algorithm can operate in the background without hurting user searches, which requires that the graph remains navigable at every intermediate step; the paper acknowledges transient states where two vertices may become unreachable, but never measures how often or for how long those states occur.","fun_headline_variants_meta":{"raw":{"variants":["Even-degree graph builds 3x faster, stays connected for exploratory search","crEG graph: even-degree, always connected, builds 3x faster","Even-degree graph keeps connectivity while building 2-3x faster","Exploratory search gets connected graph that builds 3x faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00097,"raw_usage":{"total_tokens":3958,"prompt_tokens":733,"completion_tokens":3225,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":477,"completion_tokens_details":{"reasoning_tokens":3147}},"tokens_in":477,"tokens_out":3225,"duration_ms":22890,"temperature":1.0,"reasoning_tokens":3147,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T04:27:17.459451+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument Algorithm 4 while running on SIFT1M or GloVe: during each optimization iteration, immediately after Step (3) of an edge swap, issue a range search from a random vertex to a random target and check whether the search can reach the target within a fixed hop budget. If even a small percentage of such concurrent searches fail to complete, the 'guarantee graph connectivity at any time' claim is false. Separately, re-running the GloVe experiment with concurrent edge optimization and without it should show crEG still beats HNSW by 250% at recall@100=0.99; if the gap shrinks substantially u","supporting_citations":[],"review_version":1}