MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes

Haoyang Li; Heng Tao Shen; Jiabao Jin; Jingkuan Song; Junjie Yao; Lei Chen; Peng Cheng; Wangze Ni; Zekai Wu

This paper claims that deleting a vector from a graph-based approximate nearest neighbor index can be made nearly as cheap as inserting one, while keeping recall stable or even improving it as deletions accumulate.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 12:16 UTC pith:OZR2BGT6

load-bearing objection Clean combination of known techniques yields a plausible deletion path for graph ANNS; experiments are broad, but the connectivity proof doesn't cover the implemented pruning and recall-stability lacks a theoretical bound. the 2 major comments →

arxiv 2607.29173 v2 pith:OZR2BGT6 submitted 2026-07-31 cs.DB

MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes

Zekai Wu , Jiabao Jin , Peng Cheng , Wangze Ni , Haoyang Li , Lei Chen , Junjie Yao , Jingkuan Song

show 1 more author

Heng Tao Shen

This is my paper

classification cs.DB

keywords approximate nearest neighbor searchgraph-based indexdynamic deletionin-place updateversioned edge invalidationMST repairstreaming vector searchretrieval-augmented generation

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper confronts the asymmetry in graph-based approximate nearest neighbor (ANNS) indexes: insertion is cheap because only outgoing neighbors are stored, but deletion requires repairing the unknown incoming edges that point to the removed vertex. MERIT's thesis is that you do not need to find or repair every incoming edge. Instead, you make the deleted vertex logically invisible immediately, repair only the 'readily searchable' boundary of its surviving neighbors plus a few recovered in-neighbors, and use a per-vertex version number to invalidate every stale incoming edge in O(1) without locating it. If deletions are indeed made invisible and the local repair preserves navigable routes, then dynamic workloads such as retrieval-augmented generation can remove stale or expired vectors at near-insertion cost without periodic rebuilds or recall collapse. The paper supports this with a complexity analysis and experiments showing up to 3.02x–18.87x faster deletion than prior state-of-the-art while maintaining stable recall.

Core claim

The central claim is that an in-place deletion can be decomposed into three ordered stages that together keep cost local and correctness global. First, the target vertex is marked invalid and its outgoing neighbors are snapshotted as repair seeds. Second, a bounded beam search recovers an approximate set of in-neighbors (vertices whose adjacency lists contain the deleted vertex); these are merged with the outgoing neighbors into a candidate set over which an incremental k_r-MST construction inserts up to k_r short edges per vertex, preserving connectivity and routing diversity under the graph's degree bound. Third, incrementing the target's version number logically invalidates every residual

What carries the argument

The pair of mechanisms that carries the argument is the k_r-MST local repair graph and the versioned-edge encoding. The repair graph is built over the union of the deleted vertex's outgoing neighbors and the in-neighbors recovered by a small beam search, using an incremental Prim-style construction that retains a mandatory MST backbone plus up to k_r−1 extra edges per vertex; this preserves connectivity and multiple routing choices after the vertex is removed. The versioned-edge scheme packs a 16-bit target version into each stored edge word (alongside a 48-bit vertex id) and increments the target's version on deletion, so a single O(1) version bump makes every incoming edge to the deleted v

Load-bearing premise

The bounded beam search (with a width proportional to the maximum out-degree) is assumed to find the in-neighbors that matter for routing; if it misses many important in-neighbors, version invalidation prevents wrong answers but leaves broken routes, and recall could decline as deletions accumulate.

What would settle it

Measure Recall@10 and search distance computations on a hub-heavy dataset (e.g., GloVe) after deleting 50% of vectors with MERIT, while logging the fraction of in-neighbors recovered by the bounded search per deletion. If recall drops by more than about two percentage points or search NDC rises while recovered in-neighbor count lags significantly behind actual in-degree for hub vertices, then the 'readily searchable' recovery assumption is violated and the guarantee fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Deletion latency becomes independent of the deleted vertex's in-degree and of graph size; it is bounded by local repair parameters, bringing deletion cost in line with insertion cost.
Stale incoming edges no longer consume candidate-set capacity or expansion budget during beam search, because version mismatches filter them before they enter the queue.
Long-running sliding-window updates (delete plus insert) can maintain stable recall without periodic full rebuilds, since residual stale edges are progressively removed as adjacency lists are touched.
The approach applies to both hierarchical and single-layer graph indexes, suggesting it generalizes across graph ANN index families.
The finite 16-bit version counter is shown, under a uniform-reuse model, to support trillions of updates before wrap-around, so the mechanism is durable for long-running services.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The approximate in-neighbor recovery suggests a testable dependency: on graphs with strong hubness, a fixed beam width may miss a large fraction of important in-neighbors; one could test whether an adaptive beam that grows with the deleted vertex's out-degree or recent query traffic improves recall stability.
Versioned invalidation could be extended beyond deletion to support concurrent updates and crash recovery, since it already detects version mismatches; the paper does not discuss this, but the encoding is a natural fit.
The repair strategy implicitly assumes that the 'readily searchable' in-neighbors are the ones that matter for routing; if a dataset's geometry makes important in-neighbors hard to reach from the entry point, the recall stability guarantee may degrade. A stress test on a dataset with irregular density could reveal this boundary.
The progressive cleanup means memory may still hold stale edge entries until their lists are rewritten; a reader might infer that memory footprint could grow under workloads that touch few lists, and that a trigger for forced compaction might be needed—this is not analyzed in the paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Clean combination of known techniques yields a plausible deletion path for graph ANNS; experiments are broad, but the connectivity proof doesn't cover the implemented pruning and recall-stability lacks a theoretical bound.

read the letter

This is a solid, well-motivated systems paper on the deletion bottleneck in dynamic graph-based ANNS. The central idea is clean: after marking a vertex invalid, repair only the boundary that matters for routing — the deleted vertex's outgoing neighbors plus the in-neighbors reachable by a bounded search — and use a target-version stamp to invalidate any residual stale edges. That combination is genuinely new relative to Wolverine's two-hop recovery, IP-Vamana's search-based cleanup, and FreshDiskANN's deferred consolidation. The experiments are broad: two graph families (HNSW and Vamana), multiple datasets, deletion rates of 5% and 50%, a sliding-window update workload, an ablation, and a Deep100M run. The reported speedups (up to ~19x) and stable recall are plausible, and the ablation shows both MST repair and versioned edges contribute. The version-counter lifetime analysis is a nice practical touch.

The weaknesses are real but mostly addressable. The paper claims a connectivity guarantee in §4.3 for k_r-MST repair under RNG pruning, but the actual InsertAndPrune also enforces a degree bound M that could evict MST backbone edges; the proof does not cover the implemented pruning. That's a genuine gap, though the experiments suggest the repair holds up in practice. More importantly, the recall-stability claim rests on the assumption that a single bounded search with e_f'_c = 2M recovers the routing-relevant in-neighbors. The paper says this explicitly and defends it only experimentally, over a 50-batch horizon. If important in-neighbors are routinely missed, versioned invalidation filters stale edges but does not replace broken routes, so recall could degrade on longer update streams. The 50-batch tests are a reasonable start, but the absence of any bound or a longer-horizon experiment leaves the central claim only conditionally supported.

Smaller issues: no code release, k_r and e_f'_c are tuned on the evaluation datasets, and all results are means without variance. These are standard for systems papers and don't change the verdict.

Bottom line: this is a serious, well-executed contribution that deserves peer review. The gaps — the proof/implementation mismatch and the unsupported completeness of approximate recovery — are specific and fixable with a sharper theoretical statement and either a bound or longer update-stream experiments. I'd cite it if I worked on dynamic ANNS, and I'd bring it to a reading group to discuss the recovery-repair tradeoff.

Referee Report

2 major / 4 minor

Summary. The paper proposes MERIT, an in-place deletion mechanism for graph-based approximate nearest neighbor indexes. Deletion proceeds in three stages: logical invalidation and snapshotting of the deleted vertex's outgoing neighbors; bounded-search recovery of approximate in-neighbors combined with a k_r-MST-style local repair; and versioned-edge invalidation that filters residual stale incoming edges. The authors instantiate MERIT on HNSW and Vamana and report that deletion latency is close to insertion latency, up to 3.02x–18.87x faster than Wolverine, FreshVamana, and IP-Vamana, while Recall@10 remains stable over 50 deletion batches or sliding-window update batches on several million-scale datasets and on Deep100M.

Significance. If the central claims hold, MERIT would be a practically useful step toward making graph-based ANNS indexes fully dynamic: deletion cost comparable to insertion, immediate visibility of deletions, and no periodic global cleanup. The paper is strong on the systems side: it integrates with two different graph families, reports extensive experiments across seven datasets including a 100M-scale run, provides an ablation isolating the MST-repair and versioning components, and gives a complexity analysis plus a probabilistic lifetime bound for the version counter. The main risk is not empirical breadth but whether the repair algorithm is guaranteed, or even measured, to preserve routing-relevant connectivity over sustained churn. I do not see circularity: the speedup claims are independent empirical comparisons, and hyperparameter choices are disclosed. The correctness of the recall-stability claim is what needs strengthening.

major comments (2)

[§4.3, Definition 4.3, Algorithm 3] The connectivity guarantee for k_r-MST is proven only for RNG-based pruning of the complete graph K(C): the argument that every MST edge satisfies the RNG criterion is a statement about K(C). The implemented InsertAndPrune, however, prunes to degree bound M and operates on the full graph G, not on an isolated complete graph over C. A degree cap can evict an MST backbone edge, and existing edges outside C can also affect which edges survive pruning. Thus the proof as written does not establish that the repaired candidate set remains connected under the implemented procedure. Since the recall-stability claim depends on local connectivity after repair, this gap is load-bearing. Please either extend the proof to the actual InsertAndPrune operation or add an experimental check that tracks whether the MST backbone edges survive degree-bounded pruning.
[§4.3, §6.3, §6.6] The statement that bounded search with e_f'_c = 2M recovers 'the readily searchable part of I(v_d) that affects near-term navigation' is an assumption, not a demonstrated invariant. Missed in-neighbors are version-invalidated, but their broken routes u -> v_d -> w are not repaired because u is not in candidate set C. The paper does not measure what fraction of routing-relevant in-neighbors is recovered, nor how misses accumulate over longer update streams. Experiments run for 50 batches, and the Deep100M experiment also uses a 50-batch horizon. Given that the headline includes 'keeps search recall stable or even improves it as deletions accumulate,' this needs either a formal bound on the effect of missed in-neighbors or an empirical study that varies e_f'_c and measures recovery coverage and recall decay well beyond 50 batches.

minor comments (4)

[§6.3] The text contains a duplicated sentence: 'Answer to RQ2. Answer to RQ2.'
[§6.3] The sentence 'Figure 9 reports the QPS and NDC' appears to refer to Figure 10, which is the figure whose caption describes QPS and NDC. Please fix the cross-reference.
[§4.4] The versioned-edge encoding uses 16 bits for the version and 48 bits for the identifier. Please state explicitly what happens when a slot is reused exactly V_max times and the high bits wrap; the current text only gives a probabilistic lifetime bound under an idealized uniform-reuse model.
[§5.1] In the complexity expression O(|E_C| log|C|) = O(|C|^2 log|C|), E_C is described as the edge set of the implicit complete graph over C. For readers not familiar with Prim's implementation, it may be clearer to write the Prim term as O(|C|^2 log|C|) directly.

Circularity Check

0 steps flagged

No circularity found: MERIT's claims rest on independent experiments and standard algorithmic arguments, not on definitions that presuppose their conclusions.

full rationale

The paper's central claims — deletion latency close to insertion and stable recall under accumulated deletions — are established by direct measurements against SOTA baselines on public datasets, not by a derived prediction that reduces to its inputs. The repair candidate set C is defined as the union of the outgoing-neighbor snapshot and search-recovered in-neighbors, but no equation predicts recall or latency from C by construction; the bounded-recovery step is explicitly labeled an intentional approximation whose adequacy is checked experimentally (§4.3: 'The recovery is intentionally approximate'). The k_r-MST connectivity argument is a standard exchange proof (MST edges satisfy the RNG criterion), and the complexity analysis is a conventional O(·) accounting with no fitted parameters masquerading as predictions. The single self-citation used for the search-cost bound ([48] in §4.3/§5.1) is not load-bearing: the claim that beam-search work grows with beam width is standard and independently cited. Hyperparameters (k_r, e_f'_c) are tuned on evaluation datasets, which is a methodological weakness but not circular reasoning. The concern that missed in-neighbors may break routes over long streams is a real correctness risk, not a circularity, because the paper does not derive its recall-stability claim from the recovery assumption; it demonstrates it empirically over a 50-batch horizon.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The central claim rests on empirical assumptions about routing-relevant recovery and on an idealized version-counter lifetime model. The formal connectivity guarantee has a gap between the proven RNG-pruning case and the implemented degree-bounded pruning. No new physical entities are introduced; the version table and deletion bitmap are data structures. Free parameters are k_r, e_f'_c, and the version width, with k_r tuned on evaluation datasets.

free parameters (3)

k_r (repair edges per candidate) = 2 (default; 1–5 ablated)
Chosen by ablation on Sift1M and Gist1M (§6.5 RQ4-1) and used for all main results; controls the deletion-latency / recall tradeoff.
e_f'_c (repair beam width) = 2M (e.g., 64 or 128)
Set by hand in §6.1 ('Unless otherwise stated, MERIT uses e_f'_c = 2M'); no ablation is reported, and it bounds recovery cost and candidate-set size.
version_bits = 16
Engineering choice for a 64-bit edge word (§4.4); the probabilistic lifetime analysis in §5.2 is used to argue wrap-around is unlikely, but this width is still arbitrary.

axioms (4)

domain assumption Beam search from the deleted vector with beam width e_f'_c finds in-neighbors that are routing-relevant; unrecovered in-neighbors are not needed for navigation.
Central design premise, stated in §3.2.1 and §4.3. If false, versioned invalidation filters stale edges but does not repair broken routes, so recall could degrade.
ad hoc to paper The k_r-MST local repair graph over C remains connected after the implemented degree-bounded pruning.
The proof in §4.3 covers pure RNG pruning, but InsertAndPrune in Algorithm 3 also enforces degree bound M, which can evict MST backbone edges. No argument shows connectivity holds under the implemented pruning.
domain assumption The version counter does not wrap during the workload; the probabilistic bound in §5.2 assumes an idealized uniform slot-reuse model.
The safe-budget calculation depends on every vertex slot being reused uniformly at random; real workloads with hot slots could wrap sooner. The paper acknowledges this is a model.
domain assumption The base graph (HNSW/Vamana) remains navigable when only the local boundary set C is repaired.
MERIT does not assert a global navigability guarantee; the stable recall reported in experiments is the only evidence for this assumption.

pith-pipeline@v1.3.0-daily-deepseek · 21902 in / 13105 out tokens · 119955 ms · 2026-08-03T12:16:54.293014+00:00 · methodology

0 comments

read the original abstract

Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose MERIT (MST-based Efficient Repair with In-place updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex's outgoing neighbors with its readily searchable in-neighbors, (2) $k_r$-Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the single-layer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that MERIT processes deletion at nearly the cost of inserting one vector, achieves up to $3.02\times$--$18.87\times$ faster deletion than state-of-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.

Figures

Figures reproduced from arXiv: 2607.29173 by Haoyang Li, Heng Tao Shen, Jiabao Jin, Jingkuan Song, Junjie Yao, Lei Chen, Peng Cheng, Wangze Ni, Zekai Wu.