Certified Local Repair for Proximity Graphs Under Deletion

Vector search engines find nearest neighbors quickly by walking a proximity graph, a graph in which each stored vector links to a few nearby vectors. A query starts somewhere and repeatedly moves to whichever neighbor is closer to it. When stored vectors are deleted, the links that passed through them vanish, and searches start to dead-end. Current systems fall into three camps. Some keep deleted vectors as invisible "tombstones" that still carry traffic. Some reconnect every affected neighbor by running a full search over the whole index. Some add replacement links from a fixed local recipe with a hand-tuned cutoff. The first is slow at query time, the second is slow at deletion time, and the third has no way to know when its local fix was not enough.

This note proposes treating each deletion as a small coverage problem, borrowing the running-threshold idea from streaming submodular optimization. Every point that used to route through the deleted vertex had "routing obligations": targets it could reach greedily only via that vertex. Candidate replacement edges are streamed from the local neighborhood. An edge is accepted only if the number of lost obligations it restores clears a threshold that adapts as the repair proceeds. Whatever remains uncovered is an explicit certificate that local repair failed, and only those points are sent to expensive global search. The point is not a better fixed cutoff but a repair rule that knows how well it worked and pays for global work only where the graph has actually fragmented.

Core Claim

Our claim is that the lost-obligation coverage count gives three things at once. It is a per-deletion stopping rule that needs no dataset-specific tuning. It is a cheap signal for when to escalate to global reconnection. And it is a quality guarantee stated in terms of deterministic greedy search. Together these should match the query speed of physical deletion methods and approach the recall of global reconnection, with global work concentrated in the heavy- and clustered-deletion regimes where local patches are known to fail.

To make this concrete, let $v$ be the deleted vertex and $u$ one of its in-neighbors. We call $u$ an orphan. Its obligation set $O_u$ contains the targets $w$, drawn from $v$'s out-neighbors and two-hop neighborhood, for which $v$ was $u$'s only neighbor closer to $w$ than $u$ itself. An edge $(u,c)$ covers $w$ if $d(c,w) < d(u,w)$, where $d$ is the vector distance. For a set $S$ of added edges, the repair value is

$$f_u(S) = \big|\{\, w \in O_u : \exists (u,c) \in S,\ d(c,w) < d(u,w) \,\}\big|,$$

which is a monotone submodular coverage function. Candidates $c$ arrive in one pass from $N(v) \cup N(u)$ and their neighbors. With current set $S$ and remaining degree slots $b$, the rule accepts $c$ if

$$f_u(S \cup \{(u,c)\}) - f_u(S) \ \ge\ \tau_u = \frac{|O_u| - f_u(S)}{\beta\, b}.$$

Here $\beta \ge 1$ is a single slack constant. The threshold asks each new edge to carry its fair share of the uncovered obligations given the slots left. It is therefore set per orphan and per moment rather than globally. When the pass ends, the residual $r_u = |O_u| - f_u(S)$ is the certificate. Orphans with $r_u > 0$ go to global reinsertion. All others are done.

Relation to Prior Work

Two papers supply the pruning method. QuickPrune prunes large ground sets in a single pass by accepting items whose gain per unit cost clears a threshold that rises with solution value, and it keeps more than 99% of value in practice. Kuhnle's quick streaming algorithms show that a threshold tied to current solution quality reduces per-item work to a constant-time check. Both assume a static ground set and a single objective. We reuse the threshold mechanism in a setting that is inherently dynamic: each deletion spawns many tiny coverage instances, one per orphan.

Three papers mark the endpoints we sit between.

  • SPatch models search as a softmax random walk. It links a deleted node's neighbors into a clique, which preserves hitting time, and keeps the top-$t$ heaviest edges. It is 2.5x to 3x faster at query time than tombstones and up to 35x faster at deletion than global methods. Its cutoff is static, however, and its guarantee is about random walks rather than the greedy search actually deployed.
  • IPGM reinserts every orphan with a global search and proves that the result stays an approximate Delaunay graph. The price is cost on every deletion.
  • FreshVamana in the DiskANN library keeps deleted nodes as routing points until a batch consolidation step. That step reruns RobustPrune with a fixed relaxation $\alpha \approx 1.2$.

Our rule differs from all three. The acceptance threshold adapts per orphan. The target is only the lost obligations, not a full re-prune of the orphan's neighborhood. And the residual decides when global work is needed.

Two papers motivate the escalation half of the design. LSM-VEC reports that under delete-heavy workloads DiskANN's recall fell to 61% "due to graph fragmentation" while LSM-VEC held 77.4%. The research file also notes that local heuristic rewiring loses long-range paths under mass or clustered deletion. These are exactly the cases where a residual certificate should trigger global reconnection and a fixed local cutoff cannot.

One adjacent paper does not overlap. DQF thresholds search termination with a decision tree and found this brittle on GloVe. That thresholding happens at query time, not during structural repair.

Research Program

The work has four parts.

The first part is the repair rule. We will build it on top of an HNSW implementation and a Vamana implementation, maintaining a reverse-edge index as IPGM does so that orphans can be found. Obligations can be computed at deletion time with a bounded number of distance evaluations, because $O_u$ is drawn from a small neighborhood. We will cap $|O_u|$ and measure what the cap costs.

The second part is analysis. We will prove that when every orphan ends with $r_u = 0$, every greedy step that previously succeeded through $v$ toward a target in $O_u$ still has a strictly improving move. This is a local greedy-navigability guarantee, and it speaks directly to the gap between softmax and greedy search left open by SPatch. We will also bound the edges added per orphan using the standard threshold-coverage argument, in which each accepted edge covers at least a $1/(\beta b)$ fraction of what remains. That gives a logarithmic dependence on $|O_u|$.

The third part is escalation policy. We will study whether escalating only orphans with $r_u > 0$ is enough, or whether orphans whose residual is small but nonzero can be repaired lazily. We will also track how the escalation rate grows with the deletion fraction. That rate is a diagnostic of fragmentation that no current system exposes.

The fourth part is an insertion-side check. We will use the same coverage accounting to decide whether a newly inserted point's back-edges displace obligations, since the research file notes that SPatch handles deletions only.

Baselines

The naive reference points are No Patch and Tombstones.

  • No Patch drops the vertex and its incident edges. It is known to make recall "plummet" in SPatch's evaluation.
  • Tombstones with periodic full rebuild mark deleted points and rebuild once they reach 20% of the index.

Both are run on the same graphs, the same deletion stream, and the same query sets.

The strongest local competitor is SPatch, reimplemented on HNSW as described in its paper. We will give it the same tuning budget as our method: a grid search over its cutoff $t$ run separately on each dataset, compared against our method with one $\beta$ fixed across all datasets. The fixed $\beta$ is the fairness point that matters, because our claim is about not needing per-dataset tuning. No reported absolute recall figure for SPatch was found in the research file, so we will reproduce its curves. The reported relative figure we will try to match is its 2.5x to 3x query speedup over tombstones.

The strongest quality competitor is IPGM's Global Reconnect. We have no reported absolute recall for it; the file reports only that it beats full ReBuild by up to 18.8% in efficiency and that it is up to 35x slower at deletion than SPatch.

The strongest system baseline is FreshVamana. The DiskANN paper reports that it maintained more than 95% recall over 50 cycles of churn. We will run it with an eager variant that applies RobustPrune at $\alpha = 1.2$ to each orphan's neighborhood at deletion time instead of in batches.

Two ablations isolate our ingredients:

  • a fixed-budget coverage ablation that replaces $\tau_u$ with a constant threshold;
  • a no-escalation ablation that ignores the residual.

Beating the baselines means the following. Our method should lie on or above SPatch's recall@10-versus-QPS frontier across all datasets with no per-dataset tuning. Its deletion throughput should be within a small constant factor of SPatch's, and at least an order of magnitude better than IPGM's. Under the 80% deletion and cluster-deletion workloads, its recall should be statistically indistinguishable from IPGM's.

Why not just…?

Why not just tune SPatch's cutoff per dataset? Per-dataset tuning may well close much of the average-case gap. What it cannot supply is the certificate. A fixed $t$ applies the same budget to a deletion in a dense cluster and to one that severs a bridge. The clustered-deletion workload from IPGM is the test: if tuned SPatch matches us there, the adaptive threshold is not needed. We would then reduce the contribution to the escalation signal layered on SPatch.

Why not just run RobustPrune eagerly on the orphan's local neighborhood? This is the most serious threat. RobustPrune is already a greedy covering procedure, and running it at deletion time is cheap. The differences are that RobustPrune re-covers the orphan's whole neighborhood with a fixed $\alpha$ and fixed degree, and that it reports nothing when it fails. The eager-RobustPrune baseline, both with and without our residual-triggered escalation added, settles which ingredient carries the result. If eager RobustPrune plus escalation matches the full method, we will report that the certificate is the contribution and the adaptive threshold is not.

Why not just use tombstones and rebuild periodically? The evidence already weighs against this. SPatch reports that physical deletion answers queries 2.5x to 3x faster than tombstones, and tombstoned points cannot free memory. We keep it as the naive reference and report its memory and query cost over the deletion stream.

Why not just reconnect globally, as IPGM does? Its quality is the ceiling we aim for, but it is up to 35x slower at deletion. Our method can only win if the escalation rate stays low. We will report that rate directly as a function of deletion fraction. If it approaches 100% under heavy deletion, our method reduces to IPGM in that regime, and we will say so.

Proposed Experiments

We will evaluate on SIFT1M, GIST1M, GloVe200, NYTimes, MPNet, and MiniLM. These are the datasets shared by the SPatch and IPGM evaluations, which lets us check our reproductions against their published trends. The workloads are:

  • SPatch's gradual 80% deletion stress test;
  • IPGM's cluster updates, in which spatially adjacent batches are removed;
  • ten mixed batches of insertions and deletions, following IPGM;
  • a 50-cycle churn loop modeled on the FreshVamana evaluation.

We will measure recall@10 against QPS at checkpoints along each stream. We will also record deletion latency and distance computations per deletion, edges added per orphan, memory footprint, and the escalation rate.

Four checks decide the outcome:

  1. With a single $\beta$, the method matches or exceeds per-dataset-tuned SPatch on the recall-QPS frontier, including GloVe, where DQF found fixed thresholds brittle.
  2. Under cluster deletion, the escalated orphans coincide with the regions where No Patch loses reachability, and recall tracks IPGM.
  3. The escalation rate stays low at moderate deletion fractions and rises sharply only near fragmentation, which would show that the residual measures real structural damage.
  4. The eager-RobustPrune ablation separates the value of the adaptive threshold from the value of the certificate.

A negative outcome on check 4 still leaves the certificate as a usable fragmentation monitor.