图索引搜索学会提前收手：CaST在风险约束下把代价压到类最优的1.132倍以内
核心概要
带类别配额约束的向量检索此前只能靠固定访问预算或按平均召回率学习的停止规则，无法保证返回精确答案。CaST把停止规则限定在声明接口上的单调类，用固定序列二项检验校准，并用拉格朗日弱对偶给出该类最优代价的下界。在两个各含一百万条目的数据集上，风险水平0.03至0.10时其回放代价不超过类最优的1.132倍，95%置信度；在0.05风险目标下，其平均时延低于所测其他已校准规则。
深度剖析
图索引上的约束最近邻查询现在有了一个可校准的提前停止规则，它按查询自身的搜索进度决定何时收手，而不是给所有查询同一个访问预算。 固定访问预算必须覆盖完成时间的分位数才安全，在Amazon与arXiv的HNSW图上，按风险校准的预算分别为6,781和5,978次访问，是10,000条评估查询完成时间中位数的7.1倍和5.8倍。 在风险目标0.05下，CaST在Amazon与arXiv上平均访问4,166和3,780次，而固定预算规则为6,789和5,987次，两者失败率都接近目标。
停止规则只读取一个声明接口：学习分数的滑动最小值分桶，加上答案是否已满的标志，并要求规则对这些观测单调。 此前的学习式提前终止方法以平均召回率为目标，而高平均召回率并不保证高概率返回精确的约束答案；DARTH在目标平均召回0.95下，仅对71%和68%的查询返回精确约束答案。 在该单调类上，风险约束停止化为序多面体上的线性规划，其拉格朗日极小元构成一条嵌套阶梯链，可用动态规划精确求出，再沿链用固定序列精确二项检验校准。
同一结构还给出该类最优代价的下界，使校准规则的代价可以与其类内最优值比较，而不只是报告一个绝对数字。 此前的校准方法能控制所选参数的风险，却不给出同一风险与观测下更优规则还能省多少的下界。 在风险0.03至0.10、每个设置87.5%联合置信度下，各设置的最大比值为1.082至1.128；放宽到95%置信度后升至多0.004，即1.132。
启示与展望
结论针对单机内存内搜索、无过滤遍历，以及固定的容量设置；保证只对与标注样本同分布的查询成立，查询分布漂移或索引更新后需要在新校准查询上重新校准。
类内最优下界只覆盖限定在声明接口上的规则；一个知道每条查询完成时间的全知规则在0.05风险下比经验类最优便宜2.8至3.3倍，这给出更丰富观测在同一检查点上可能带来的收益上限。在YFCC-10M上3.9%的查询在32,768次访问内无法完成，因此只评估0.05至0.10的风险水平。