修复图索引的时机选择:按信号触发不如定时修复,且此前正结果可能被误导。
When to Repair a Graph ANN Index: A Matched-Budget Negative Result, and the Interpolated-Baseline Trap That Hid It

- 用导航性能下降信号触发修复,比定时修复更省预算
- 在真实数据集上,两者召回率差异不显著,有时定时更优
- 发现早期研究误判源于插值基线的凹函数陷阱,适合严谨评估者
图近似最近邻索引(如HNSW、DiskANN/Vamana)在频繁插入删除时召回率下降,因删除导致搜索路径断裂。生产系统常固定周期修复(每X次操作合并一次)。本文探究是否可基于导航性退化信号触发局部边修复,以在相同修复预算下表现更优。在SIFT-128和Fashion-MNIST-784两个真实数据集、突发删改流下,与实际修复次数对齐的定时基线相比,信号触发策略的尾部召回优势不可区分于零;多个配置下定时策略反而更优。我们溯源发现此前正向结果源于插值基线:召回率随修复次数呈陡峭凹函数关系——一次合并获得超过一半增益——因此在0到4次之间线性插值会低估基线,夸大了提议效果。预注册指标(与后续召回下降的相关性)也表明该信号非领先指标。本文贡献包括:精确的在线召回真值工具、可复现的删改测试框架、漂移严重性映射图,以及实现预算对齐的协议,使此类错误可被检测。报告负结果及陷阱,因其具有普遍性:任何在凹响应稀缺端通过插值读取基线的‘预算匹配’比较,都会人为制造对提议有利的效果。
原文摘要 · Abstract (English)
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 asked whether triggering local edge repair on a measured navigability-degradation signal, rather than a blind clock, spends a fixed repair budget better. At matched repair budget, it does not. On two real ANN datasets (SIFT-128 and Fashion-MNIST-784) under a bursty churn stream, compared against a fixed-cadence baseline actually run at the triggered policy's realized consolidation count, the tail-recall advantage is indistinguishable from zero at every operating point, graph degree, and index scale; at several points the clock is better. We trace our earlier positive result to an interpolated baseline: recall is sharply concave in repair budget -- one consolidation captures over half of all achievable gain -- so reading the baseline off a straight line between zero and four passes understates it by more than the effect claimed. Evaluated by the statistic we pre-registered -- correlation with the subsequent recall drop rather than with the concurrent recall level -- the probe signal is also not a leading indicator. What remains is useful: an exact live-set recall oracle, a reproducible churn harness, a drift-severity regime map, and a budget-parity protocol that makes this error detectable. We report the negative result and the trap, because the trap generalizes: any "at matched budget X" comparison whose baseline is read off an interpolated curve, at the scarce end of a concave response, will manufacture an effect favouring the proposal.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。