技术摘要：在漂移情况下，分片 ANN 索引何时需要主动重新分区？

问题陈述
近似最近邻（ANN）索引越来越多地用于非平稳语料库，由于持续的插入、删除和模型更新，数据分布会发生偏移。系统研究领域（如 Quake, Ada-IVF, GTI, CrackIVF, SPFresh）的一个普遍前提是：静态分区在数据漂移下会变得陈旧，除非通过主动重新分区（通过拆分、合并、重聚类或裂解/cracking），否则会导致召回率崩溃。本文挑战了这一前提的普适性，探讨了：在何种特定的漂移条件下，主动重新分区是真正必要的，而在何种情况下，可以通过调整探测预算（probe budget）的静态索引来吸收漂移？

方法论
作者并未进行现有系统的头对头基准测试。相反，他们构建了一个受控的、匹配召回率（matched-recall）的测试框架，以表征维护成本与重建成本之间的权衡。关键的方法论组成部分包括：

• 匹配召回率协议： 不同于固定成本控制参数（如探测预算 $b$）并测量召回率的基准测试，该协议固定了一个召回率底线（0.90），并测量实现该底线所需的最小探测预算（$b_{needed}$）和延迟。这隔离了维护成本与覆盖范围变化（例如，拆分分区会减少固定 $b$ 所覆盖的质量）带来的混淆效应。
• 工作负载生成器： 研究使用参数化的漂移轴：
  • 周转率 ($\tau$): 被替换的活跃集比例。
  • 更新率 ($u$): 更新量与查询量的比例。
  • 相关性 ($\rho$): 将数据漂移与查询漂移解耦。
  • 有界窗口 (Bounded Window): 一种基数保持不变而分布旋转的模式，将漂移从规模效应中分离出来。
• 共享地面真值 (Shared Ground Truth): 每个检查点计算一次基于内容的键值精确地面真值，并在所有实验组（静态、拆分/合并、重聚类、重建）之间共享，以确保公平比较。
• 预注册终止门 (Pre-Registered Kill-Gates): 研究采用了一系列可证伪的标准，以防止“挽救”失败的假设。如果一个假设（例如，“叶子节点内图结构是静态优势”）未能通过门槛，研究工作将转向其他方向，而不是调整参数以强行获得正向结果。
• 测试分支：
  • 静态 (C0): 无维护，使用墓碑删除（tombstone deletes）。
  • 维护变体: 漂移触发的拆分/合并、基数触发的拆分以及增量重中心化（incremental re-centering）。
  • 参考基准 (R): 一个在架构内进行的完整重聚类（从头开始重建），作为质量基准。
  • 外部检查: 在相同的追踪数据上运行了真实的 Quake 构件（OSDI'25），进行外部验证。

关键结果

1. 中度漂移下的静态充分性：
   在具有中度增长/周转的数据集（SIFT1M, GIST1M）上，使用墓碑删除的静态分区在与维护变体相同的探测预算下，仍能维持 0.90 的召回率底线。在这种机制下，主动维护是不必要的；探测预算中的“冗余”（slack）吸收了漂移。

2. 叶子节点内图结构并非静态优势：
   图叶子节点混合索引（原工作的动机）在静态召回率–QPS 前沿面上被扁平 HNSW 所支配。它不提供静态搜索优势，仅提供更快的构建时间。

3. 机制边界（旋转漂移）：
   在一个真实的、规模受控的旋转窗口（MS-Turing-10M）上，静态分区表现出明显的退化。随着分布旋转，其所需的探测预算（$b_{needed}$）从 64 上升到 112+。在这种机制下，重中心化是真正需要的。

4. 增量重中心化 vs. 完整重建：
   在旋转漂移机制下，廉价的增量重中心化能以大约 1/6 的再生成本达到与完整重聚类相同的召回质量（即相同的 $b_{needed}$）。

   • 总拥有成本 (TCO): 在现实的查询密集型工作负载中，增量重中心化和完整重建在 TCO 上是等效的。增量重中心化仅在更新密集型工作负载中具有绝对优势。
   • 不存在偏向重建的交叉点： 本文反驳了此前关于存在交叉点（$u^* \approx 4.7$）即完整重建变得更优的说法，指出该点是由于将新鲜构建的延迟归功于陈旧索引以及顺序计时漂移所导致的产物。

5. 外部验证 (Quake)：
   在相同追踪数据上运行真实的 Quake 系统证实了该机制边界：Quake 能在受限的扫描比例下维持召回率底线。然而，其默认的规模触发策略导致了索引碎片化（使 $nlist$ 增加了 13 倍），产生了高昂的维护成本，而受控的重中心化则能以低廉成本维持较小的预算。

贡献

1. 受控基准测试： 一个参数化的漂移工作负载和带有匹配召回率协议的测试框架，实现了数据/查询漂移的解耦，并提供了逐区域的地面真值。
2. 机制图谱 (Regime Map)： 一个区分“静态充分”机制（中度增长/周转）与“重中心化有益”机制（旋转漂移）的特征描述。
3. 决策规则： 为从业者提供的实用指南：
   • 中度增长： 保持静态；使用墓碑删除和略大的探测预算。
   • 旋转漂移： 进行重中心化，但使用增量重中心化而非完整重建。
   • 触发选择： 基于漂移的触发与基于基数的触发在召回率上没有差异；请根据工程便利性进行选择。
4. 解释性框架： 一个“探测预算冗余”模型（$\sigma < b$），解释了何时陈旧性是可以被吸收的，何时会迫使重新分区。
5. 诚实的负面结果： 对领域内过度声明的修正，特别是指出“叶子节点内图结构”并非静态优势，且如果不进行重中心化，单纯的拆分/合并只会导致索引碎片化而非减少陈旧性。

意义与主张
本文声称其主要贡献是机制图谱和决策规则，而非一种新的维护算法。它认为“漂移必然导致主动重新分区”这一前提是有条件的。

• 在冗余机制（中度漂移）下，维护不是正确性的必要条件；它是一个成本权衡，且通常是不必要的。
• 在强制机制（旋转漂移）下，维护是必要的，但可以避免进行完整的周期性重建。增量重中心化能以极低的再生成本实现与完整重建相同的召回质量。
• 本文强调，匹配召回率、受竞争控制的协议本身与结果同样重要，因为它防止了先前导致关于维护必要性和成本错误结论的混淆错误（例如，固定预算比较）。

作者明确表示，他们并不声称解决了所有漂移模式（例如，未涵盖纯消失漂移或真实的查询漂移追踪），且其发现仅限于特定的索引族（k-means 路由结合 HNSW/扁平叶子节点）及测试的漂移幅度。