{"id":"1b479739-36a3-4c48-9d9a-8a4ba4efc6eb","arxiv_id":"2507.19802","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"CleANN combines workload-aware bridge building, on-the-fly neighborhood consolidation, and semi-lazy memory cleaning to keep graph-based ANNS recall near static-build levels under fully dynamic concurrent workloads.","lead":"CleANN is a new graph-based approximate nearest neighbor search system that keeps search quality high while insertions and deletions run concurrently, avoiding the expensive global rebuilds that earlier dynamic indexes require. On large real-world datasets it reports 7 to 1200 times higher throughput than the FreshVamana baseline while maintaining comparable recall.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Recall evidence is in-sample: Section 6.1 derives training queries from the test queries, so the reported recall gains from GuidedBridgeBuild may be test-set adaptation rather than robust maintenance; Table 3 also shows CleANN below RebuildVamana on Sift and MS-SpaceV.","rationale":"The reader's CONDITIONAL verdict identifies the same core weakness: the recall comparisons rely on training queries generated from the test queries, making the headline quality claim partly in-sample. My independent reading of the manuscript confirms this is the most load-bearing threat to the central claim. Section 6.1 explicitly describes the perturbation procedure, and Section 3.1.2 confirms that search queries can trigger GuidedBridgeBuild, so the adaptation mechanism is active during training and only disabled for performance-sensitive test queries. This is not a hypothetical confound: on datasets labeled as having distribution shift or out-of-distribution queries, the training set is constructed to be close to the test set, so any measured recall gain from query-aware bridge building could be a function of test-set familiarity rather than robust index maintenance. The no-training comparison in Figure 37 is encouraging evidence that some benefit is real, but it is not the protocol used for the main benchmarks. I also confirmed the separate issue in Table 3: CleANN's recall is below RebuildVamana on Sift and MS-SpaceV, and below FreshVamana on four datasets, so the unqualified 'at least as good as static' statement in the abstract is not supported by the paper's own data even before considering the training-set issue. The throughput claim depends on approximately matched rather than exactly matched recall, which further weakens the quantitative headline. None of this invalidates the engineering contribution: the algorithms are well specified, the ablations are informative, and the speedups are large enough that a clean evaluation will likely retain a substantial advantage. The fix is straightforward and does not require rethinking the system design, so conditional acceptance is the right level of scrutiny. I agree with the reader's weighting of the concern and recommend no change to the verdict.","tokens_in":28163,"tokens_out":4404,"duration_ms":54239,"concrete_test":"Rerun the Sliding Window Batched Update experiments on RedCaps, Yandex-tti, and MS-SpaceV with training queries drawn from a held-out temporal split of the query stream (e.g., the first half of each round's queries for training and the second half for testing, with no perturbation), and report recall across all 200 rounds. If CleANN's recall stays within 0.5 points of RebuildVamana and remains above it on the distribution-shift datasets, the quality claim survives; if recall drops by more than 2 points or falls below RebuildVamana, the reported advantage is an artifact of test-derived training queries. As a secondary check, test whether any parameter setting gives CleANN recall at least as high as RebuildVamana on Sift and MS-SpaceV; if not, the abstract should be weakened from 'at least as good' to 'comparable'.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that CleANN has query quality at least as good as a static rebuild rests on the recall comparisons in Table 3 and Figures 6-12. That evidence is compromised by the training-query construction in Section 6.1: training queries are formed by randomly sampling the test queries and adding a perturbation scaled by the dataset's average nearest-neighbor distance. Since GuidedBridgeBuild is activated during training searches (Section 3.1.2) and only the test queries are marked performance-sensitive, the index is adapted to a distribution that is deliberately close to the test distribution. The measured recall on datasets with distribution shift or out-of-distribution queries (RedCaps, Yandex-tti, Adversarial, MS-SpaceV) can therefore reflect in-sample adaptation rather than robust dynamic maintenance. The no-training variant in Figure 37 gives some support, but the main benchmark numbers all use this in-sample training regime, so the headline quality claim is not yet established for the reported workloads. Independently, Table 3 directly undercuts the 'at least as good as static' phrasing: CleANN's recall is below RebuildVamana on Sift (98.81% vs 98.98%) and MS-SpaceV (89.54% vs 89.72%), and below FreshVamana on four of seven datasets. These gaps are small, but they contradict the unqualified abstract claim. The throughput claims are also reported at approximately matched, not exactly matched, recall, so the magnitude of the 7-1200x speedup could change under a stricter recall-matched comparison. All of these issues are fixable with an out-of-sample evaluation, which is why the appropriate outcome is a conditional acceptance pending that check rather than a rejection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CleANN, a concurrent dynamic graph-based approximate nearest neighbor search (ANNS) system built on Vamana/DiskANN. CleANN combines three techniques: guided bridge building, which adds edges between nodes at similar depths of the beam-search tree during inserts and training searches; on-the-fly neighborhood consolidation, which repairs the graph around tombstones when they are encountered during searches; and semi-lazy cleaning, which recycles tombstone nodes after a tunable number of consolidations without fully removing all dangling edges. The authors claim that CleANN achieves query quality at least as good as a static rebuild on fully dynamic sliding-window workloads, and that at the same recall level it achieves 7-1200x throughput improvements over FreshVamana on million-scale datasets. The evaluation covers 7 datasets, compares against RebuildVamana, FreshVamana, NaiveVamana, and DEG, and includes ablations, hyperparameter sensitivity, memory overhead, and scalability studies.","tokens_in":28461,"tokens_out":4044,"duration_ms":45505,"significance":"If the main claims hold, this would be a significant contribution: CleANN would be the first concurrent graph-based ANNS index that maintains static-build-quality recall under full dynamism without expensive global consolidation, while also supporting concurrent inserts, deletes, and searches. The paper is engineering-heavy but presents a coherent set of mechanisms with a publicly available implementation. Strengths include the breadth of datasets, the ablation studies (especially the no-training and memory-reuse experiments), the sensitivity analysis of the cleaning threshold C, and the direct comparison with the sequential DEG baseline. However, the headline quality and throughput claims are weakened by the evaluation design: training queries are derived from the test queries, and the throughput numbers are reported at approximately matched recall rather than exactly matched recall.","major_comments":[{"comment":"The recall evidence for the central 'at least as good as static' claim is in-sample. The training queries used to activate GuidedBridgeBuild during searches are generated by 'randomly sampling from test queries and adding a perturbation parameterized by the average nearest neighbor distance'. Since GuidedBridgeBuild modifies the graph during training searches (Section 3.1.2, Algorithm 8, lines 29-30) and only the test queries are marked performance-sensitive, the index is explicitly adapted to a distribution that is deliberately close to the test distribution before recall is measured. On datasets with distribution shift or out-of-distribution queries (RedCaps, Yandex-tti, Adversarial, MS-SpaceV), the reported recall advantage may therefore reflect test-set adaptation rather than robust dynamic maintenance. The no-training variant in Figure 37 provides partial independent evidence, and the ablation in Figure 36 does not use the training phase, but the main benchmark numbers in Table 3 and Figures 6-12 all use this in-sample training regime. Please report the main recall comparisons for a no-training configuration, or with held-out queries that are disjoint from the training queries, and state clearly whether the quality claim applies to the query-adapted setting only.","section":"Section 6.1, 'Sliding Window Batched Update'"},{"comment":"The unqualified abstract claim that 'CleANN has query quality at least as good as if the index had been built statically' is contradicted by the paper's own Table 3: CleANN's recall is below RebuildVamana on Sift (98.81% vs. 98.98%) and on MS-SpaceV (89.54% vs. 89.72%), and below FreshVamana on four of the seven datasets (Sift, MS-SpaceV, RedCaps, HuffPost). The gaps are small, but the claim as stated is not supported. Either qualify the claim (e.g., 'competitive with' or 'within measurement noise of') or provide statistical significance or repeated-run variability to justify the 'at least as good' phrasing.","section":"Table 3, rows Sift and MS-SpaceV"},{"comment":"The throughput claims are reported at 'approximately matched' recall, not at exactly the same recall level. Table 3 states that 'Other parameters are varied to approximately match the recalls of different approaches.' Since the abstract claims 'at the same recall level', the 7-1200x speedup numbers could change if recalls were exactly matched, especially on datasets where CleANN's recall is slightly lower. Please present throughput at several matched recall levels (e.g., by interpolating the recall-throughput tradeoff curves in Figures 22-33) or report the recall values used for each throughput number so the reader can judge the size of the recall gaps.","section":"Section 6.2 and Table 3, throughput comparison"}],"minor_comments":[{"comment":"Several figure captions appear to be duplicated or mismatched with the surrounding text: for example, Figure 23 is captioned 'on RedCaps' while the text refers to GloVe, and Figure 25 says 'RedCaps' in the caption but the text references GloVe. Please re-check the correspondence between figures and captions.","section":"Section 6.3.1, Figures 22-33"},{"comment":"The index sizes used in the main benchmark are inconsistent between Table 3 and the figure captions: for instance, Table 3 lists Sift at 150k and RedCaps at 1.5M used, while Figures 6 and 9 captions state index sizes of 50k and 500k respectively. Please clarify which index sizes correspond to which experimental round and how the 'Size Used' column relates to the sliding-window initial size.","section":"Table 3 and Figures 6-19"},{"comment":"The phrase 'maintains a similar recall as CleANN' for FreshVamana is imprecise; the recall differences in Figures 6-12 are up to several percentage points. Please state numeric recall ranges or use a consistent 'matched recall' protocol for the throughput comparison.","section":"Section 6.2.2"},{"comment":"When search throughput is reported for the Sliding Window Mixed Update setting, the text says the weighted average across training and test queries is used. Please state explicitly what fraction of the reported throughput corresponds to training queries and how much the GuidedBridgeBuild overhead in those queries contributes to the reported numbers.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's central novelty claim ('the first concurrent ANNS index to achieve such efficiency while maintaining quality under full dynamism') may need softening given the concurrently published IP-DiskANN (arXiv:2502.13826) which also targets in-place updates for streaming ANNS. The authors already cite this work, but the wording of the abstract and conclusion should be checked. The in-sample training-query design is the main correctness-risk area; the no-training ablations are a good start, but the primary benchmark should be reported without test-derived training queries to convincingly separate workload adaptation from overfitting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"CleANN is a serious systems paper with real new mechanisms, but the paper's own data contradicts its strongest claim, and the main recall evaluation is partly in-sample. The three ingredients—bridge building, on-the-fly neighborhood consolidation, semi-lazy cleaning—are clearly specified, individually ablated, and backed by released code. The bridge-building idea is the most interesting: adding edges between search-tree cousins at moderate depths during traversals is a simple move that plausibly addresses insertion-order robustness without global rebuilds. The consolidation and cleaning machinery is also thoughtfully designed, and the empirical work is extensive: seven datasets, sliding-window and mixed workloads, thread scaling up to 224, memory overhead, and a no-training ablation that gives independent evidence the mechanisms do something.\n\nThe soft spots are real but fixable. First, Section 6.1 generates training queries by randomly sampling the test queries and adding a perturbation scaled by the dataset's average nearest-neighbor distance. That makes the training distribution artificially close to the test distribution, so the recall gains from GuidedBridgeBuild on distribution-shift datasets (RedCaps, Yandex-tti, Adversarial, MS-SpaceV) are partly test-set adaptation rather than robust maintenance. The no-training variant in Figure 37 mitigates this for one dataset, but the main benchmark numbers all use the in-sample regime. Second, Table 3 directly undercuts the abstract's 'at least as good as static' phrasing: CleANN's recall is below RebuildVamana on Sift (98.81 vs 98.98) and MS-SpaceV (89.54 vs 89.72), and below FreshVamana on four of seven datasets. The gaps are small, but they still contradict the unqualified claim. Third, throughput is reported at approximately matched recall, not exactly matched, so the 7–1200x speedup could shift under stricter recall matching. None of these are fatal; they are the difference between a conditional accept and a fully supported claim.\n\nThere is also a missing comparison: IP-DiskANN, cited as concurrent and independent, works on exactly this problem. The paper notes it would be interesting to compare but doesn't do it. That is a gap a referee should push on.\n\nWho should read this: anyone building or evaluating dynamic graph-based ANNS for vector databases. It deserves a serious referee, not a desk reject. The right outcome is major revision with an out-of-sample evaluation and a softened or qualified version of the 'at least as good as static' claim.","headline":"CleANN is a serious systems paper with real new mechanisms, but the paper's own data contradicts its strongest claim, and the main recall benchmark is partly in-sample.","tokens_in":29048,"tokens_out":2935,"would_cite":true,"duration_ms":32192,"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":"CleANN claims graph-based vector search keeps static-build quality under inserts, deletes, and concurrent searches, with 7–1200x throughput gains over FreshVamana at equal recall.","keywords":["approximate nearest neighbor search","graph-based index","dynamic indexing","concurrent inserts and deletes","sliding window","vector database","recall","throughput"],"falsifier":"Run the sliding-window benchmark with training queries drawn from an earlier time window or from a separate held-out query set that is not derived from the test queries, and check whether CleANN still matches RebuildVamana recall on distribution-shift datasets such as RedCaps or MS-SpaceV; if the recall gap reappears, a significant part of the bridge-building advantage is an artifact of the training distribution.","tokens_in":27905,"feed_emoji":"⚡","tokens_out":3324,"duration_ms":40484,"temperature":0.7,"pith_summary":"The paper claims that a graph-based approximate nearest neighbor search index can be made fully dynamic—concurrent inserts, deletes, and searches—without the periodic global consolidation that previous dynamic indexes require. The proposed system, CleANN, is said to maintain query recall at least as good as an index rebuilt from scratch on the corresponding data, while achieving 7–1200x higher search throughput than FreshVamana at equal recall on million-scale datasets. Three mechanisms carry the argument: workload-aware bridge edges among nodes visited during search-tree exploration, on-the-fly consolidation around deleted nodes triggered by searches, and semi-lazy memory cleaning that recycles tombstones before all their incoming edges are fixed. If the claim holds, full dynamism stops being the weak point of graph-based ANNS and becomes a head-to-head contest with static rebuilds.","feed_headline":"Vector index matches static quality under churn, 7–1200x faster","feed_subtitle":"CleANN merges bridge-building, on-the-fly consolidation, and lazy cleaning to keep search quality under inserts and deletes.","key_machinery":"The central object is the search tree T built during each GreedyBeamSearch traversal, together with the bridge-building step GuidedBridgeBuild that connects nodes at selected depths of T (typically Θ(log |D|) layers) subject to a heuristic predicate—in practice, endpoints at the same depth. These bridge edges restore the missing shortcuts that static builds obtain through global passes. For deletions, the key structure is the tombstone counter H(w), which counts how many times a deleted node has been consolidated by a live parent during a traversal; once H(w) exceeds an eagerness threshold C, the node becomes replaceable and can represent a new data point. Consolidation itself is the operation that copies a tombstone's out-neighborhood into the live parent's neighborhood (Algorithm 7). The entire CleANN system combines these on-the-fly repairs with the Vamana graph, using this machinery to avoid global consolidation entirely.","core_discovery":"The central discovery is that the robustness problems of dynamic graph-based indexes can be solved locally and lazily rather than globally. During any beam search, the visited nodes form a search tree; adding a few edges between same-depth cousins in that tree—nodes that are nearby but lacked a short connection—dramatically improves navigability under adversarial insertion orderings. For deletions, the index does not need to connect every in-neighbor of a tombstone to every out-neighbor; instead, while traversing, a live node that encounters a tombstone absorbs the tombstone's out-neighborhood on the spot, and after a small number of such consolidations the tombstone is marked replaceable and reused for new data, even if some incoming edges still point at it. The paper argues that these random residual edges do little harm because beam search and pruning naturally ignore them. Together these mechanisms let CleANN match the recall of a freshly rebuilt index while avoiding the costly global scans that make prior dynamic indexes an order of magnitude slower.","pith_inferences":["The reported recall parity on distribution-shift datasets depends on the training-query construction, which samples test queries and perturbs them; a cleaner evaluation would train on queries from an earlier time window and would reveal how much of the advantage is genuine adaptivity versus test-set adaptation.","The fact that a small training batch (2% of test queries) suffices suggests that only a few high-value edges carry most of the navigability; identifying which edges these are could let other indexes add bridges more cheaply.","The experiments are in-memory, so the benefits may not transfer to out-of-core settings where tombstones and random edges increase I/O; testing under a disk-based index or a memory cap would clarify the boundary of the claim.","If the bridge-building mechanism is as robust as claimed, it could also improve static index construction under non-uniform insertion orders, which would simplify build pipelines that currently require careful ordering or global passes."],"forward_implications":["On sliding-window workloads, a graph-based index using CleANN's insertion and cleaning routines can match the recall of a freshly rebuilt static index without paying the rebuild cost.","Because cleaning is trigger-driven and local, searches and updates can run concurrently without a global scan, so throughput does not collapse while deletions are being processed.","The core techniques are portable: guided bridge building and on-the-fly consolidation apply to any graph-based ANNS index that uses beam search plus a pruning routine, not just Vamana.","On datasets with distribution shift or out-of-distribution queries, query-aware bridge building can push recall above a static rebuild on the same data.","At a fixed recall target, CleANN's throughput advantage over FreshVamana grows as the write share of the workload increases."],"supporting_citations":[{"why":"Supplies the Vamana base graph, the beam search, the RobustPrune routine, and the insertion procedure that CleANN extends.","marker":"[20]"},{"why":"Provides FreshVamana, the main baseline that CleANN must beat, and defines the tombstone-plus-global-consolidation delete routine that CleANN avoids.","marker":"[45]"},{"why":"Describes DEG, the sequential global-refinement baseline that CleANN compares against in single-threaded experiments.","marker":"[15]"},{"why":"Supplies the open-source in-memory DiskANN implementation on which CleANN is built.","marker":"[44]"},{"why":"Documents the recall and efficiency degradation caused by unchecked tombstones, motivating the need for the cleaning techniques developed here.","marker":"[50]"},{"why":"Provides several benchmark datasets (Sift, GloVe) and the static-baseline context used in the evaluation.","marker":"[3]"}],"fun_headline_variants":["CleANN: dynamic ANNS with static-like recall, 7-1200x faster","Local lazy updates for graph ANNS, up to 1200x throughput gain","Full dynamism without quality drop: CleANN's lazy consolidation","Match static index quality under churn, 7-1200x faster","Beats global rebuilds: CleANN's local consolidation for dynamic ANNS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The measured recall parity assumes that the in-distribution training queries—generated by randomly sampling the actual test queries and perturbing them by a scale tied to the dataset's average nearest-neighbor distance—are a fair proxy for the query workload rather than a form of test-set adaptation.","fun_headline_variants_meta":{"raw":{"variants":["CleANN: dynamic ANNS with static-like recall, 7-1200x faster","Local lazy updates for graph ANNS, up to 1200x throughput gain","Full dynamism without quality drop: CleANN's lazy consolidation","Match static index quality under churn, 7-1200x faster","Beats global rebuilds: CleANN's local consolidation for dynamic ANNS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000259,"raw_usage":{"total_tokens":1656,"prompt_tokens":1084,"completion_tokens":572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":470}},"tokens_in":700,"tokens_out":572,"duration_ms":6128,"temperature":1.0,"reasoning_tokens":470,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:59:44.152432+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the sliding-window benchmark with training queries drawn from an earlier time window or from a separate held-out query set that is not derived from the test queries, and check whether CleANN still matches RebuildVamana recall on distribution-shift datasets such as RedCaps or MS-SpaceV; if the recall gap reappears, a significant part of the bridge-building advantage is an artifact of the training distribution.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Vamana base graph, the beam search, the RobustPrune routine, and the insertion procedure that CleANN extends."},{"cited_title":"Fast Approximate Nearest Neighbor Search with a Dynamic Exploration Graph using Continuous Refinement","cited_arxiv_id":"2307.10479","evidence_quote":"Describes DEG, the sequential global-refinement baseline that CleANN compares against in single-threaded experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the open-source in-memory DiskANN implementation on which CleANN is built."}],"review_version":1}