Search papers, labs, and topics across Lattice.
This paper investigates the effectiveness of a navigability-signal-triggered local repair strategy for graph approximate-nearest-neighbor (ANN) indexes in the face of insert/delete churn, contrasting it with fixed-schedule repairs. The authors demonstrate that this adaptive approach significantly enhances tail recall under constrained budgets, achieving improvements of +0.014 to +0.050 in minimum recall@10 across various datasets. Notably, the method's efficacy is particularly pronounced in sparser graphs, indicating a strong correlation between navigability signals and actual recall performance.
Local repair triggered by navigability signals can boost tail recall in graph ANN indexes by up to 0.050, outperforming fixed-schedule repairs when budgets are tight.
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.
