When to Repair a Graph ANN Index:
Navigability-Signal-Triggered Local Repair Protects Tail Recall Under Bursty Churn
July 01, 2026
Abstract
Graph approximate-nearest-neighbor (ANN) indexes—HNSW, DiskANN/Vamana—lose recall under insert/delete churn, because deletions orphan the greedy-search paths that route through removed nodes. Production systems restore navigability by repairing the graph on a fixed schedule (consolidate every \(X\) operations). We ask whether triggering local edge repair on a measured navigability-degradation signal, rather than a blind clock, spends a fixed repair budget better. On two real ANN datasets (SIFT-128 and Fashion-MNIST-784) under a controlled bursty churn stream, and comparing repair policies at matched amortized repair budget (equal consolidation count), signal-triggered repair Pareto-dominates fixed-cadence repair. The gain is concentrated on worst-case (tail) recall at scarce budget: at roughly one consolidation it improves the minimum \(\mathrm{recall}@10\) by \(+0.014\) (SIFT) to \(+0.050\) (Fashion-MNIST) across four stream seeds, with 95% confidence intervals excluding zero, while the mean-recall gain is small (\(<0.005\)). The advantage follows a clean drift-severity gradient—larger for sparser, more fragile graphs—and fades to parity when the index is robust or budget is ample. A cheap probe-recall signal is a valid, leading indicator of true recall (Spearman \(\rho\approx0.95\)). We contribute the mechanism, a budget-matched evaluation protocol that separates repair scheduling from repair spend, and an open, reproducible churn-repair harness. We deliberately do not claim a mean-recall improvement or a new index; a recall-versus-repair-cost bound and data-distribution-drift coupling are left as future work.
1 Introduction↩︎
Vector search increasingly runs over churning corpora: embeddings are continuously inserted (new items) and deleted (expired or removed items). Graph ANN indexes [1], [2] answer a \(k\)-nearest-neighbor query by a greedy best-first walk over a navigable proximity graph. A deletion removes a node but leaves the greedy-search paths that routed through it dangling; recall then falls. Restoring monotone reachability requires local edge repair over the affected neighborhood (re-linking the deleted node’s in-neighbors to its out-neighbors and re-pruning for diversity). Systems perform this repair on a fixed schedule—FreshDiskANN’s delete-consolidation runs when a delete list fills [3]; the operational folklore is “rebuild every \(X\%\).”
We study a simple lever: when to repair. A fixed cadence is blind to whether the graph has actually degraded. We instead trigger local repair on a measured navigability signal—a cheap probe-set recall that tracks true recall—and ask whether, at the same repair budget, this places repairs better than a clock.
1.0.0.1 Contributions.
A navigability-signal-triggered local-repair controller (§3) for graph ANN indexes: fire local consolidation when a measured degradation signal crosses a calibrated level, instead of on a fixed cadence.
A matched-budget evaluation protocol (§4) that compares policies at equal consolidation count, isolating repair scheduling from repair spend—so a policy cannot “win” merely by repairing more.
An empirical result (§5): on two real datasets, signal-triggering Pareto-dominates fixed-cadence on tail recall at scarce budget (min-\(\mathrm{recall}@10\) up by \(+0.014\) to \(+0.050\), four seeds, CIs exclude zero), with a drift-severity regime map and a signal-validity analysis (\(\rho\approx0.95\)). The mean-recall gain is small; we say so.
An open harness: a big-ann-streaming-compatible [4] churn runbook, an exact live-set recall oracle, repair-budget accounting, and one-command reproduction.
1.0.0.2 What this is not.
We do not propose a new index, and we do not claim a mean-recall improvement—the mean gain is below \(0.005\) and below our pre-registered target (§7). The effect we establish is on worst-case recall under scarce budget, exactly where a degradation-triggered controller should help. We build on, and compare against, existing repair mechanisms rather than replacing them.
2 Problem and model↩︎
An in-memory graph index over a live point set \(S\subseteq\mathbb{R}^d\) answers queries by greedy search. Under a stream of insertions and deletions, deletions are handled lazily (tombstone, filtered from results) until a consolidation pass physically removes tombstoned nodes and locally repairs edges (the \(\alpha\)-relative-neighborhood re-prune of [2]). We measure \(\mathrm{recall}@10\) against an exact brute-force oracle recomputed on the current live set after each window—never against frozen initial ground truth, which would manufacture drift as points are deleted. We define the repair budget as the number of consolidation passes over the stream; because each pass consolidates all currently-tombstoned nodes, the total repair volume over a run is approximately the total number of deletions regardless of schedule, so equal pass-count \(\approx\) equal spend (we verify this via logged consolidation wall-time and tombstones cleared).
3 Method: the repair controller↩︎
We compare three repair policies on the same index and stream:
P0 (no repair): lazy tombstoning only—a floor.
P1 (fixed-cadence): consolidate every \(c\) operations (FreshDiskANN-style).
P2 (signal-triggered): consolidate when the navigability signal \(s(t)\) drops a threshold \(\delta\) below its post-repair baseline.
The signal \(s(t)\) is the recall@10 on a small, held-out probe query set (disjoint from the evaluation set), recomputed cheaply each window—a black-box proxy that needs no engine-internal instrumentation. The matched-budget comparison interpolates P1’s recall-versus-consolidation-count curve at P2’s realized count, so P1 and P2 are read off at the same budget.
4 Experimental setup↩︎
Apparatus. DiskANN’s in-memory Vamana index (diskannpy) built single-threaded for determinism; a real index, no simulation. Data. SIFT-128 and Fashion-MNIST-784 (both \(L_2\), from ann-benchmarks), live set \(20\)k / \(10\)k, roughly \(10\times\) turnover. Churn. A bursty stream
that alternates delete-heavy bursts with insert-heavy calm, so drift is bursty rather than smooth; graph degree \(R{=}16\) unless swept. Metric. \(\mathrm{recall}@10\) vs
the exact live-set oracle per window; four stream seeds for confidence intervals. Controls (all pass): a static/no-churn stream yields \(\approx\)zero drift and P2 never fires; insert-only drifts less than
delete-heavy; budget parity (a P2 that wins only by spending more is disqualified); the oracle matches a freshly-built static index and flags the single-delete orphaning fixture.
5 Results↩︎
Repair helps, monotonically in budget. Without repair, min-\(\mathrm{recall}@10\) drifts to \(0.935\) (SIFT, \(R{=}16\)) and \(0.92\) (Fashion-MNIST); consolidation restores it, and more consolidations give higher recall (Fig. 2).
H1: signal-triggering beats fixed-cadence at matched budget, on the tail. Table 1 reports the matched-budget delta P2\(-\)P1. On both datasets and all four seeds, the tail (min-recall) delta is positive at scarce budget with 95% \(t\)-CIs excluding zero; the mean delta is consistently positive but small. The tail win is \(\sim3\)–\(4\times\) larger on Fashion-MNIST, whose higher dimension drifts more. Figure 1 shows why: under bursts, fixed-cadence lets recall crater during unattended bursts, while signal-triggering repairs at burst onset.
| dataset | budget | \(\Delta\) mean recall | \(\Delta\) min (tail) recall |
|---|---|---|---|
| SIFT-128 | \(\sim\)1 consol | \(+0.0056\pm0.0006\) | \(+0.0136\pm0.0093\) |
| \(\sim\)2 consol | \(+0.0045\pm0.0010\) | \(+0.0112\pm0.0088\) | |
| Fashion-MNIST-784 | \(\sim\)1 consol | \(+0.0013\pm0.0006\) | \(+0.0502\pm0.0097\) |
| \(\sim\)1 consol | \(+0.0009\pm0.0005\) | \(+0.0416\pm0.0148\) |
Regime: the win tracks drift severity. Sweeping graph degree \(R\) (a robustness knob) at fixed churn, the scarce-budget tail win shrinks as the index gets more robust (Table 2, Fig. 3) and fades to \(\approx\)zero at ample budget—signal-triggering helps precisely where the index is fragile and budget is scarce.
| graph degree \(R\) | P0 min-recall (drift) | tail win \(\Delta\)min |
|---|---|---|
| 16 | 0.935 | \(+0.0210\) |
| 24 | 0.967 | \(+0.0124\) |
| 32 | 0.973 | \(+0.0092\) |
H3: the signal is a valid, leading indicator. On the no-repair drift trajectory, the cheap probe signal correlates with true full-eval recall at Spearman \(\rho=0.95\) (concurrent) and \(0.95\) (one-window lead)—well above a \(0.6\) pre-registered bar—so triggering on it is justified.
Scale. The effect persists at a larger scale: on SIFT with a \(100\)k-vector live set (\(5\times\) the headline index), signal-triggering again beats fixed-cadence at matched budget on all operating points, with a tail win of \(+0.009\) min-\(\mathrm{recall}@10\) at \(\sim\)1 consolidation (single seed).
6 Related work↩︎
Streaming graph ANN indexes repair locally but on a fixed schedule (FreshDiskANN [3]; topology-aware localized update [5]), per deletion (Wolverine [6], which repairs navigability on every delete), or trigger on a measured signal but for IVF partitions with non-navigability signals (Quake [7], Ada-IVF [8], which react to partition imbalance/cost). SPFresh [9] rebalances IVF/SPANN posting lists, not graph edges. [10] propose evaluation metrics for the recall-versus-repair-cost trade-off on graph indexes; we adopt that framing and add a controller plus a budget-matched protocol. Provably dynamic structures such as cover trees [11] have update guarantees but are not the deployed graph indexes; navigable-graph limits are studied by [12]. To our knowledge no prior work fires local graph-edge repair on a measured navigability signal; that is the cell we occupy.
7 Limitations and honest negatives↩︎
Mean recall. Our pre-registered success criterion was a mean-recall gain \(\ge0.02\); it is not met—the mean gain is \(<0.005\). The \(>0.02\) effect is on min/tail recall, the more service-level-relevant metric, and we frame the claim there, not on the mean. Regime-bound. The advantage fades to \(\approx\)zero (occasionally slightly negative) for robust indexes or ample budget—signal-triggering helps only where the index actually drifts under scarce budget. Design correction. A delete-fraction sweep is invalid under our burst generator (the burst phase overrides the delete fraction, producing identical streams); those runs were discarded, and we vary churn severity via \(R\) instead. Scope. Single-node in-memory Vamana; \(L_2\) data; a black-box probe-recall signal (true graph-internal monotonicity signals need engine instrumentation); \(10\times\) turnover at \(10\)–\(20\)k live. Not claimed. A recall-versus-repair-cost lower bound (with the navigability signal as a potential function) and coupling repair to data-distribution drift are natural next steps, not results here.
8 Conclusion↩︎
When repair budget is scarce and a graph ANN index drifts under bursty churn, when you repair matters: triggering local repair on a cheap navigability signal protects worst-case recall better than a fixed clock at the same budget. The effect is modest on the mean, clear on the tail, replicated across two datasets and four seeds, and graded by drift severity. We release the harness and the budget-matched protocol so the mechanism can be tested at larger scale and in deployed engines.