AI summaryⓘ
The authors studied how graph-based systems that quickly find nearest neighbors (ANN indexes) lose accuracy when items are frequently added or removed, because the pathways in the graph get broken. Instead of fixing these graphs on a fixed schedule, they tested repairing only when a signal shows the graph’s navigability has worsened. Their experiments on real datasets showed that this signal-based repair method improves the worst-case accuracy, especially when repair resources are limited, but doesn't much change average accuracy. They also introduced a way to measure repair efficiency and shared their testing setup. They did not claim overall accuracy improvements or new graph types, leaving further work for the future.
Approximate Nearest Neighbor (ANN) SearchGraph IndexHNSWDiskANNRecallChurnEdge RepairNavigabilityConsolidationRepair Scheduling
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 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 ~= 0.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.