Cost-Aware Best-LLM Identification using Dueling Feedback¶

会议: NeurIPS2026
arXiv: 2609.30360
领域: 学习理论
关键词: 决斗老虎机、最优臂识别、异质查询成本、Condorcet 赢家、序贯检验

一句话总结¶

本文把“以给定置信度找出两两偏好中的最佳模型”建模为异质成本决斗老虎机，用单位成本拒绝证据分配比较预算、跟踪抽样并通过最佳臂假设检验停止，获得几乎处处的渐近成本保证，但有限实验中置信区间版本 DCTAC 比主算法 DCTAS 更省成本。

研究背景与动机¶

模型评测不一定能得到稳定的绝对分数。给同一问题的两个回答，用户通常更容易判断哪个更好，因此 Chatbot Arena 一类平台采用两两比较。不过，模型间的偏好不一定存在完整排名：某个模型可以战胜所有对手，其余模型之间却仍出现循环。本文只要求存在 Condorcet 赢家，即某个模型对每个其他模型的真实胜率都严格超过一半；不要求全局总序，也不要求随机传递性。

已有固定置信度决斗老虎机方法主要优化比较次数，但比较一次廉价模型与比较一次昂贵模型并不等价。本文假定每个模型的查询成本预先已知，一场比较的成本是两个模型成本之和。需要选择的不是“性价比最高的模型”，而是偏好意义上最好的模型；成本决定如何寻找它，而不改变最终赢家的定义。

关键转变在于，不必反复让昂贵赢家亲自击败每一个竞争者。只要为每个非赢家找到一个可信的失败对手，就能排除它成为 Condorcet 赢家的可能；这些对手本身可以不是赢家。核心 idea：把识别最佳模型转化为为每个竞争者购买最有效的拒绝证据，按照信息量除以比较成本分配预算，再用同一识别目标指导停止。

方法详解¶

整体框架¶

DCTAS（Dueling Bandit Cost-Aware Track and Stop）的输入是候选模型、已知成本向量与允许错误率；真实偏好矩阵未知，需要在线估计。每轮先根据经验胜率计算单位成本拒绝证据，得到预算与抽样配额，再以强制探索与配额跟踪选择比较对，接收一次胜负观测，最后进行最佳臂假设检验。这里没有模型参数训练，反馈只更新胜率估计与比较次数。

需要区分两条信息流：分配器决定“下一次比较谁”，停止器决定“证据是否足够”；胜负观测既刷新下一轮分配，也供停止检验使用。图中成本与置信度是控制输入，不是生成的回答或训练标签。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["已知成本与经验胜率"] --> B["单位成本拒绝证据"]
    B --> C["预算到抽样配额"]
    C --> D["强制探索与配额跟踪"]
    D --> E["比较选中模型对<br/>观测胜负并更新统计"]
    E --> F["最佳臂假设检验"]
    G["允许错误率"] --> F
    F -->|通过阈值| H["输出估计赢家"]
    F -->|未通过：继续分配| B

关键设计¶

1. 单位成本拒绝证据：为每个非赢家寻找最划算的失败见证

记真实胜率为 \(p_{m,n}\)，模型成本为 \(c_m\)，真实赢家为 \(a^*\)，\(d(x,y)\) 是两个 Bernoulli 分布的 KL 散度。若模型 \(m\) 输给 \(n\)，把它与 \(n\) 的胜率抬到一半，是令它有资格成为赢家必须跨过的统计边界；离边界越远，越容易排除。若它本来就胜过 \(n\)，这条边不能提供拒绝它的证据，对应 KL 项为零。作者据此得到如下闭式量：

\[ \alpha_m=\max_{n\ne m}\frac{d\!\left(p_{m,n},\max\{0.5,p_{m,n}\}\right)}{c_m+c_n},\qquad c^*(\nu)=\sum_{m\ne a^*}\frac{1}{\alpha_m}. \]

\(\alpha_m\) 是拒绝模型 \(m\) 的最佳单位成本信息率，而特征成本 \(c^*(\nu)\) 汇总了拒绝所有非赢家的困难程度。最大化对手的集合 \(\Gamma_m\) 可以包含多个模型，不必包含真实赢家。信息论下界是期望总成本至少为 \(c^*(\nu)\log(1/(4\delta))\)；它衡量的是在未知矩阵下区分不同赢家所需的信息，并非部署赢家的费用。

分配时，难拒绝的模型获得更多拒绝预算：其份额按 \(1/\alpha_m\) 归一化，再分到最有效的对手。若多个对手同样有效，最优分配不是唯一向量，而是一个集合；算法可以在等效对手之间分配预算。原文 Proposition 1 对“涉及一个模型的总权重”与“拒绝该模型的预算”存在记号解释问题，下面采用后者说明机制，不把前者的字面公式当作无歧义的实现规格。

2. 预算到抽样配额：预算比例不能直接当成比较次数比例

上述优化首先得到比较对占总花费的比例 \(w_{i,j}\)。如果两种比较分别花费 2 和 5，给它们相同预算并不意味着抽样同样多次；必须先除以单次比较成本，再归一化为抽样比例。令 \(\mathcal K\) 为无序模型对集合，原文 Lemma 2 的转换是：

\[ \alpha_{i,j}=\frac{w_{i,j}/(c_i+c_j)}{\sum_{(m,n)\in\mathcal K}w_{m,n}/(c_m+c_n)}. \]

这里 \(\alpha_{i,j}\) 是比较对的抽样份额，与上一设计中带单个下标的拒绝信息率 \(\alpha_m\) 含义不同。WeightPullAllocation 用当前经验矩阵代替真实矩阵，计算预算分配，再执行这一转换；伪代码对并列最优对手采用均分。省钱不是抽样之后再把账单乘上价格，而是价格事先改变了选择哪些比较以及各比较的频率。

3. 强制探索与配额跟踪：避免早期误判永久切断信息来源

算法先比较每一对模型一次。此后，若存在比较对的累计次数少于 \(\sqrt t\)，便选择当前比较次数最少的一对；没有这种欠探索情况时，选择“实际比较次数减去历轮目标抽样份额之和”最小的一对，补偿其相对目标的欠账。使用累计目标而非只看本轮概率，使过去的分配决定也被落实。

强制探索尤其重要：经验矩阵可能暂时选错拒绝对手，或者没有明确经验赢家，不能因此让某条边永远没有新观测。随着时间增加，每条边持续得到观测，经验胜率几乎处处收敛。附录证明跟踪份额到最优分配集合的距离趋于零，而不是必须收敛到某个唯一权重；这正面处理了并列最优对手带来的不唯一性。不过，早期经验矩阵不满足赢家假设时，正文分配伪代码没有完整交代回退处理，不能直接据此认定实现细节已完备。

4. 最佳臂假设检验：检验“谁能是赢家”，而不只检验一场胜负

停止器比较两个全局假设：“模型 \(i\) 是 Condorcet 赢家”与“模型 \(j\) 是 Condorcet 赢家”。每个假设需要它对所有其他模型的胜率至少到达一半，因此可以用所有相关失败边的 KL 代价计算约束最大似然之差。原文 Lemma 3 给出闭式统计量；以下省略无意义的自身比较项：

\[ Z_{i,j}(t)=\sum_{k\ne j}N_{j,k}(t)d\!\left(\hat p_{j,k}(t),\max\{\hat p_{j,k}(t),0.5\}\right)-\sum_{k\ne i}N_{i,k}(t)d\!\left(\hat p_{i,k}(t),\max\{\hat p_{i,k}(t),0.5\}\right). \]

直观上，第一项衡量“强行让 \(j\) 成为赢家”需要违背多少已有证据，第二项对 \(i\) 作相同衡量；差值越大，数据越支持 \(i\)。所以模型 \(j\) 被另一个廉价模型可靠击败，也能帮助排除 \(j\)，不要求证据只来自 \(i\) 与 \(j\) 的直接对决。

只有存在某个 \(i\)，使它对每个其他赢家假设的统计量都超过动态阈值 \(\beta(t,\delta)\)，算法才停止并输出它。原文阈值来自混合鞅型序贯界，依赖模型数、时间与错误率，不是固定的 0.5 胜率门槛；本文不展开其辅助函数 \(C\) 的繁复定义。Theorem 2 保证停止且答错的概率不超过 \(\delta\)，Theorem 3 则给出另一个性质：

\[ \limsup_{\delta\to0}\frac{J(\tau_\delta)}{\log(1/\delta)}\le c^*(\nu)\quad\text{almost surely}. \]

这是一条几乎处处的渐近总成本上界。它与期望成本下界共享主导常数，但不是任意有限错误率下 DCTAS 都比所有方法便宜的保证，也不能不经额外论证就改写为期望成本收敛定理。

一个完整示例¶

原文三臂实例中，模型 1 对模型 2 和 3 的胜率分别为 0.63、0.65，模型 2 对模型 3 的胜率为 0.60，因此模型 1 是赢家。成本向量取 \((k,1,1)\)，让赢家逐渐变贵；以下抽样份额是已知真实矩阵时的最优目标，不是每个有限运行已经达到的实际次数。

当 \(k=4\) 时，成本无关方法把全部目标抽样分给 \((1,2)\) 和 \((1,3)\)；成本感知方法则用 \((1,2)\) 拒绝模型 2，用便宜的 \((2,3)\) 拒绝模型 3。模型 2 虽然不是赢家，却可以成为模型 3 的有效失败见证。

这里没有通过传递性推算缺失胜率：模型 3 已有直接输给模型 2 的证据，因此不能是 Condorcet 赢家；模型 2 也已被拒绝，剩下的模型 1 才是赢家。原文主文用“利用传递性”描述此例，但一般方法只依赖存在赢家，笔记不把这句话扩展为额外算法假设。目标中 \((1,3)\) 份额为零，也不意味着有限运行完全不比较它，因为强制探索仍然存在。

实验关键数据¶

主实验¶

真实数据实验使用四类 Chatbot Arena 偏好矩阵及公开价格构造 Bernoulli 比较实例，设置 \(\delta=10^{-10}\)，每个数据点运行 100 次。下表取自原文 Table 2，数值为平均累计成本及 99.7% 置信区间；越低越好，不同任务的成本定义与尺度不同，不宜跨列比较绝对大小。

算法	T2I	T2T	Vision	Search
DCTAS	2823 ± 89	21.5 ± 0.9	77.0 ± 4.3	1015 ± 28
TAS	2931 ± 171	22.8 ± 1.2	78.9 ± 4.0	1079 ± 59
DPCA	13017 ± 138	未报告	304.2 ± 70.4	9184 ± 212
CRR	未报告	73.8 ± 2.0	364.2 ± 16.3	未报告
DCTAC	1461 ± 907	12.8 ± 1.7	42.6 ± 2.9	973 ± 67

“未报告”不是零成本或算法不可用；作者说明对应运行成本过高，平均成本会超过 DCTAS 的十倍。这里的 ± 是作者所述置信区间，不是标准差。DCTAC 在全部四列平均成本最低，但 T2I 的区间尤其宽，不能只凭均值推断稳定优势。

这些实验没有训练模型，也没有现场执行 GPU 推理来测延迟；它们在 Google Cloud e2-highcpu-8（8 vCPU、8 GB 内存）上模拟比较。T2I 按单图费用计价，T2T 与 Vision 假设每次查询生成 1000 个 token，Search 采用 High 档价格及请求/token 归一化假设。

消融实验¶

原文没有常见的网络模块删除消融，最清楚的机制分析是固定偏好、改变赢家成本，以及在相同跟踪规则下替换停止规则。下表来自 Table 1，比较三臂实例在 \(k=4\) 时的最优抽样份额。

比较对	成本无关抽样份额	成本感知抽样份额	机制解释
1 与 2	0.5720	0.3706	保留拒绝模型 2 的比较
1 与 3	0.4280	0	昂贵赢家不再承担模型 3 的主要拒绝预算
2 与 3	0	0.6294	用廉价失败见证拒绝模型 3

合成实验将 \(k\) 从 1 变到 19，每个值运行 500 次，取 \(\delta=0.01\)，Figure 2 展示平均成本及 95% 置信区间。原文图的具体纵轴数据未在缓存中给出，因此不补造逐点成本；正文报告小成本区间 \(k<4\) 时 TAS 与 DCTAS 接近，赢家变贵后两者差距增大。

关键发现¶

TAS 与 DCTAS 使用相同 GLRT 停止机制，主要区别是分配是否使用成本，因此两者对照更直接地隔离了成本感知抽样的效果。真实数据上的提升远小于它们相对 CRR、DPCA 的优势。
Table 3 报告 DCTAS 相对 TAS 的平均成本降幅为 T2I 3.8%、T2T 5.7%、Vision 2.4%、Search 5.9%。T2I 用表中已显示均值重算约为 3.7%，与所报 3.8% 有舍入或统计口径差异；保留原文报告并标明差异，不自行修正。
DCTAC 共享 DCTAS 的抽样规则，但改为检查候选模型对所有对手的胜率置信下界是否超过一半。它的有限实验成本更低，说明渐近最优分配与有限样本停止开销是两个问题；原文并未给 DCTAC 同样的渐近成本定理。

亮点与洞察¶

最有价值的转化是“为每个非赢家找失败见证”，而不是“让赢家逐一认证自己”。当赢家昂贵时，非赢家之间的比较也能承担排除工作，这使成本真正改变证据结构。
单位成本信息率把统计难度与价格放在同一个量里。单纯选最便宜的模型对不够，因为接近五五开的廉价比较仍可能极难形成拒绝证据。
最优配额不唯一并非罕见实现噪声，而是等效拒绝对手带来的数学结构。把目标设为接近最优分配集合，可避免理论依赖一个并不存在的唯一权重。

局限与展望¶

存在 Condorcet 赢家、比较独立且来自固定 Bernoulli 胜率、模型成本已知，是保证的前提。没有赢家、平局、用户群变化或价格随输出长度变化时，不能直接沿用定理。
实验把已有经验矩阵当作真实实例再模拟，未评估原始偏好估计误差、在线标注费用、响应缓存或实际 API 成本波动。它支持比较分配的统计成本优势，不等于真实评测服务的端到端节省。
Proposition 1 将模型权重定义为所有涉及该模型的边权之和，但同时把其质量限制到能拒绝该模型的对手；在一条边被用于拒绝另一端时，这两种解释可能不同。Algorithm 2 也没有充分说明初始经验矩阵没有赢家时如何定义这些份额，复现需核对作者实现或澄清记号。
表格中的 DCTAC 有限成本优势、T2I 宽区间，以及 Table 3 的舍入差异，都应独立于渐近结论阅读。进一步工作可研究停止阈值的有限样本紧度，并引入随机查询成本，而不是宣称主算法已全面支配其他方案。

评分¶

新颖性: 4/5。异质成本与 Condorcet 决斗识别结合，给出可解释的闭式信息结构。
实验充分度: 3/5。有合成成本扫描、四类真实偏好矩阵和停止规则对照，但不是现场模型调用实验。
写作质量: 3/5。主线清楚，但权重记号、早期分配处理和局部数值口径需进一步澄清。
价值: 4/5。适合预算敏感的模型选择与主动比较设计，实际应用仍需检查偏好与成本假设。