新 AI 辩论协议实现实例级最优：最坏情况正确且诚实为占优策略

如何在人类判断只是黑盒时，为稳定可分解问题设计最坏情况正确、且诚实为占优策略的辩论协议。

• 场景：作者称可扩展监督变紧迫，是因为许多任务没有覆盖全部要求的可验证奖励，完整输出又很难由专家直接判断。作者称，软件工程训练环境稍有偏差时，系统常常找到作弊解，例如改测试用例使它总是通过；有些情况下这种行为会泛化到与编程无关的场景。
• 现有协议的缺口：作者称 prover-estimator debate 能处理足够稳定的分解，但正确性是平均情况，均衡是 Stackelberg，弱于占优策略均衡，执行和分析也更复杂。更早的混淆论证问题使“双方都有界且能力相当”时的递归辩论难以保证正确。
• 核心对应：作者把这种稳定性对应到查询复杂性里的 fractional block sensitivity（fbs）。fbs 上界给出 Bob 抽样子命题、并以非平凡概率碰到错误的办法。作者称该抽样策略可有效计算。
• 本文给出的对象：FBS Debate，问题类与 prover-estimator 相同。作者称正确性改为每个实例上的最坏情况，诚实且正确是双方的占优策略均衡；并称只做黑盒人类判断查询时，协议按实例最优。
• 辩论设定：
  • 目标是判定语言 L 上输入 x 的是/否，并少查询人类判断。
  • 人类判断是 oracle O:{0,1}^n→{0,1}；辩论者与裁判建模为可黑盒查询 O 的图灵机。
  • Alice 给出宽度 q 的分解和声称答案；Bob 可在 fbs 超过 ρ 时判她失败，或抽样一个子命题，递归到深度 d。
  • 一步聚合器 MD 在开始前商定；分解树通常在线生成。论文未把被监督对象写成某个具名模型。

相关工作分成辩论的复杂性形式化、经典委托模型、单 prover 的 interactive proof，以及实证辩论。最近的理论对照是 prover-estimator debate。

辩论的复杂性形式化

• 早期协议：Irving et al. [2018] 的辩论协议面向计算无界的 prover。Barnes [2020] 提出 obfuscated arguments，指出当时的协议在双方计算能力相当、但仍有界时会失败。
• 有界辩论者：Brown-Cohen et al. [2024] 的 doubly-efficient debate 适用于有界辩论者，但问题类更窄。Brown-Cohen et al. [2025] 的 prover-estimator debate 处理更广的递归可分解问题，并引入稳定性；作者称该稳定性就是本文的 fbs。
• 作者点名的差别：引言称 prover-estimator 只有平均情况保证，均衡是 Stackelberg。第6节称 Irving et al. 的 Debate=PSPACE 要求 Bob 直接判断哪个子问题有缺陷，本文的 Bob 不必这样做。

经典模型

• 交替与论证：Chandra et al. [1981] 用交替图灵机讨论无界 prover 说服多项式时间验证者。Feige and Kilian [1997] 研究对抗 prover 与裁判之间可以有私密通信的论证。
• 委托与学均衡：Canetti et al. [2013] 用相互竞争的 prover 做计算委托。Chen et al. [2023] 学习辩论协议定义的零和博弈均衡，关注学习算法和裁判的计算开销，策略空间可以指数大。论文没有把这两类工作写成实验对照。

机器学习里的 interactive proof

• 两类用途：Amit et al. [2024]、Anil et al. [2021]、Hammond and Adam-Day [2025]、Chen et al. [2026] 用单 prover 的 interactive proof 核验 AI 输出是否正确。Wäldchen et al. [2022]、Kirchner et al. [2024] 把同类技术用于可解释性与可读性。
• 只对 Chen et al. [2026] 的对比：作者称其 ε-稳健性推出所诱导布尔函数的 fbs=O(1/ε)，是固定一步聚合器上有界 fbs 的均匀权重特例；本文的局部 fbs 允许非均匀抽样。作者称两边框架不可比：对方在开始时固定显式电路，本文是在线递归分解加固定的一步聚合器；其低次 oracle 结果因为多了代数结构，与本文下界正交。

实证工作与基线

• LLM 测量：Michael et al. [2023]、Kenton et al. [2024]、Khan et al. [2024] 在受理论协议启发的设置里测量实际 LLM。作者称这些结果提供了一些证据，辩论能帮助某些能力有限的 LLM 裁判核验其他 LLM 的输出。
• 训练流程：Shao et al. [2025] 的大规模数学推理训练使用类似辩论的流程，一个模型批评证明，另一个模型再批评该批评。
• 基线：论文没有实证基线，也没有基准数据集。理论上对照的是 prover-estimator debate，以及访问分解树全部叶子的 q^d 次查询。脚注称，此处使用 doubly-efficient debate 可把对 O 的查询降到 1，时间仍是 O(q^d)。

作者把本文放在 Brown-Cohen et al. [2025] 的同一问题类上：用 fbs 得到最坏情况的占优策略保证，并给出只做黑盒人类判断查询时的实例下界。

FBS Debate 让 Alice 递归分解命题并申报真值，Bob 只检查这一步聚合对错误有多敏感：过敏感则 Alice 立即失败，否则按对偶权重抽样深入，叶子交给人类判断 oracle。

递归可分解问题

• 语言与 oracle：决策问题写成语言 L。人类判断是 O:{0,1}^n→{0,1}。辩论者与裁判是可黑盒查询 O 的图灵机（第3.1节）。
• 一步聚合器：宽度 q 的 MD 接收实例 x、子问题 y 和答案 z。它可以拒绝分解；若接受，且每个 z_i 都等于 L(y_i)，则输出必须等于 L(x)（Definition 3.1）。MD 在协议开始前由各方商定。谁提出被 MD 拒绝的分解，谁立即失败，因此辩论中可认为 MD 不输出 ⊥。
• 分解树：深度 d、宽度 q。根在层 k=d，对应输入 x；非叶节点的值由 MD 聚合子节点真值；每个叶子有一次查询 q_u，使该叶子上的 L 等于 O(q_u)（Definition 3.2）。树通常在辩论过程中在线生成。逐个访问叶子需要 q^d 次查询。

分式块敏感度

• 定义：对布尔函数 f 与赋值 x，敏感块是翻转后会改变 f(x) 的坐标集合。fbs_x(f) 是这些块上的一个线性规划最优值：块权重非负，每个坐标被含它的块权重加总不超过 1，目标是块权重之和最大（Definition 3.3）。
• 对偶与抽样：对偶给每个坐标非负权重，使每个敏感块的权重和至少为 1，并最小化总权重；强对偶下等于 fbs（Definition 3.4）。作者称该对偶本质上是 Aaronson [2008] 的随机化证书复杂度，并称 fbs 与随机验证者核验不可信证明所需的查询数紧密相关。
• 两个函数例子：多数函数在前 2/3 位为 1 时 fbs=4。全 1 输入上的 AND，只随机翻转一位就能改变输出，fbs=n。作者用这个对比说明，AND 比多数函数更容易把单点错误藏在相近的边际分布里。

协议的一轮

• 输入：x、L、O、宽度 q 的 MD、深度 d，以及超参数 ρ。Alice 先输出一位 A(x)，作为对 L(x) 的答案（第4节，Figure 1）。
• 从层 d 到层 1：Alice 把当前命题分成 q 个子问题并给出声称答案 z。MD 的输出必须等于她对当前命题的声称，否则立即失败。Bob 解对偶线性规划，检查 fbs_z(MD(x̂,y,·)) 是否不超过 ρ；超过则 Alice 失败。
• 抽样分布：检查通过后，Bob 以 p_i=t_i/∑_j t_j 抽取第 i 个子问题继续，t 是对偶最优解。该式把对偶权重归一化成抽样概率。作者称这样抽样时，抓住谎言的机会至少为 1/ρ；证明里，这是在该层声称错误、且稳定性检查已通过时，抽中敏感块的条件概率。
• 叶子：k=0 时，Alice 的声称与 O 一致则 Alice 胜，否则 Bob 胜。作者称，Alice 若不希望立即失败，每一步分解的 fbs 都必须不超过 ρ。

诚实策略与胜负概念

• 诚实 Alice：取 A(x)=L(x)，按一棵每步 fbs 不超过 ρ 的分解树分解，z 用正确答案。Theorem 4.1 的结论是她以概率 1 获胜。若生成任一非叶节点的子节点用时 T_D，在任一节点上解 L 用时 T、查询 Q 次，则该策略时间为 O(d·(T_D+q·T))，查询 O(d·q·Q) 次。
• 两个均衡条件：作者把完备性定义为：原命题正确时，无论 Bob 采用什么策略，诚实且正确分解的 Alice 总能赢。soundness 定义为：原命题错误时，无论 Alice 采用什么策略，按协议行动的 Bob 都能赢。作者由此称，诚实且正确是辩论博弈里每一方的占优策略。
• 高概率来自重复：单次下界是 ρ^{-d}，不是 1。作者称把协议运行 O(ρ^d log n) 次，才能把错误答案放大到很高的抓住概率，并把这看成允许高敏感论证与验证所需推理时计算之间的权衡。
• Bob 不必先知道谁错：作者称 Bob 不需要判定每个子答案是否正确，只需要按论证结构抽样。这与 prover-estimator 不同：那里对任意不诚实的 Alice 策略，存在一个可能依赖该策略的 Bob 获胜策略，均衡概念是 Stackelberg。

论文没有模型实验或数值表格，结果是递归分解框架上的定理。单次抓住错误的概率下界是 ρ^{-d}，黑盒查询下界与之同阶。

实验设置

• 对象：语言 L、黑盒 oracle O、事先商定的宽度 q 一步聚合器 MD、深度 d 的分解树，以及超参数 ρ。论文未列出被测模型。
• 对照：没有实证基线。理论上对照 prover-estimator debate 的保证类型，以及穷举叶子的 q^d 次查询。脚注另写 doubly-efficient debate 可把对 O 的查询降到 1，时间仍为 O(q^d)。
• 指标与判定：单次辩论中 Alice 失败的概率、重复后的抓住概率、oracle 查询次数。叶子由 O 判定；Bob 用对偶线性规划检查 fbs 是否不超过 ρ。论文未报告评审模型、阈值以外的打分规则或人工一致性。
• 完备性的额外条件：存在一棵分解树，子节点可在 T_D 内生成，任一节点上的 L 可在时间 T、Q 次查询内解出，且正确 z 下每步 fbs 不超过 ρ（Theorem 4.1）。
• 下界模型：诚实 Bob 与裁判合成一个自适应检验器，最多 m 次查询 O，能看到整棵可见树，并可与 Alice 任意通信（第5节）。叶子查询假定两两不同。论文未报告样本量或重复实验次数。

主结果

论文没有结果表。下表是定理和正文中的保证，不是测量值。

Swipe horizontally to read the table

陈述	条件	保证	出处
完备性	存在满足可解性与 fbs≤ρ 的分解树	诚实 Alice 获胜概率为 1	Theorem 4.1
soundness	A(x)≠L(x)，Alice 策略任意	单次失败概率 ≥ ρ^{-d}	Theorem 4.2
重复	运行 O(ρ^d log n) 次	≥1−1/poly(n)；第1.2节写 ≥1−O(1/poly(n))	第4节、第1.2节
查询下界	每层 fbs≥ρ，正确概率 ≥1−ε，ε<1/2	查询数 m ≥ (1−2ε)ρ^d	Theorem 5.1 之后

• 作者称这是每个错误实例上的保证，而不是只在输入分布上平均成立；因此在每个具体问题上，诚实都是更好的选择。
• 单次成功概率随深度变成 ρ^{-d}。作者称高概率依赖随 ρ^d 增长的重复，并把它写成敏感程度与推理时计算量的权衡。
• 作者称标准设定取 d=O(log n)，相对穷举 q^d 有关于 n 的多项式加速；并称多数票聚合可以出现 q=99 而 ρ=4，使 ρ^d 小于 q^d。论文未报告具体 n 上的加速倍数。

黑盒实例下界

• 测了什么：固定一棵可见分解树后，m 次自适应查询能否区分两个使根值不同的 oracle。检验器已经看到整棵树，并有诚实 Bob 协助，作者称这只会让任务更容易，因此下界也适用于原辩论协议。
• 结果：若每个内部节点在参考 oracle 诱导的子值上 fbs 至少为 ρ，则存在另一个 oracle 使根值翻转，且接受概率之差不超过 min{1, mρ^{-d}}（Theorem 5.1）。Lemma 5.4 先得到整棵树在参考赋值上的 fbs 至少为 ρ^d。若检验器在每个 oracle 下都以至少 1−ε 的概率输出正确根值，且 ε<1/2，则 m ≥ (1−2ε)ρ^d。
• 作者的解读：若该实例最好的分解每步 fbs 为 ρ，则常数概率找到有缺陷子命题至少需要 Ω(ρ^d) 次黑盒查询，与本文代价匹配。作者称这是实例意义下的最优，并称要再扩大可处理的问题类，必须放松黑盒判断假设。作者同时写明，若全部叶子查询同一串，树可能只计算一位恒等函数，非平凡下界可以不成立。

与 prover-estimator 的理论对照

• 同一问题类：两边都处理足够稳定、作者称即 fbs 有界的递归分解。本文没有扩大这个类。
• 保证不同：本文是单个错误输入上的 soundness，以及不依赖对方具体策略的占优策略。prover-estimator 的 soundness 是输入分布上的平均，并且对每个不诚实的 Alice 策略，Bob 的获胜策略可以以复杂方式依赖该策略。
• 作者的训练解读：作者称占优策略均衡比 Stackelberg 更稳定、更好训练；平均情况保证只说明，最大化期望胜率会让辩论者在除一小部分问题外保持诚实。论文未报告训练过程或胜率曲线。

其他消融与分析

• 多数票、前 2/3 位为 1：fbs=4；在 z_i=1 的子命题中抽样，抓住谎言的概率为 1/4，因为错误时至少 1/6 的子命题也错（第1.2节）。
• 50/99 的多数票：作者称一篇错误就会翻转结果，Bob 只能逐一检查 Alice 声称支持的 50 篇；协议允许 Bob 指出这种过敏感声称并使 Alice 失败。论文未给出该例的 fbs 数值。
• 全 1 输入上的 AND：fbs=n（第3.3节）。
• Remark 5.5：独立叶子时，Gilmer、Saks 与 Srinivasan [2016] 的复合障碍给出同样的 Ω(ρ^d) 随机查询下界；Theorem 5.1 额外给出优势上界 mρ^{-d}，并允许任意自适应查询、保持已揭示的树不变。
• 论文未报告 ρ、d、q 的数值扫描，也未报告求解对偶线性规划的耗时或查询次数实测。

作者把计算有界时的找错难度，以及黑盒人类判断，写成继续改进辩论协议时要面对的障碍。

作者指出的局限与后续方向

• 找错可能难于构造：作者称，识别有缺陷子问题的计算复杂度可能远高于构造这些子问题。若 Alice 和 Bob 都能解 PSPACE 中的任意问题，这不是问题；若辩论者计算有界，作者称实践中会如此，这就是障碍（第6节，原文称为 serious obstacle）。
• 能否越过 fbs：作者提问，能否设计超出本文 fbs 障碍的协议。作者提出的一种希望是利用 Bob 解与 Alice 相同问题的能力，或许借此利用 Alice 的计算限制（第6节）。论文没有给出这样的协议。
• 下界依赖黑盒：作者写明，下界只在人类判断被建模为只能查询的黑盒时成立。作者认为，interactive proof 里打开黑盒、得到更强协议的方法，例如 IP=PSPACE，不太可能直接用于人类判断，因为那基本上要读取实现人类判断的代码（第6节）。
• 其他放松方式：作者认为，除了读取判断代码之外，某种别的放松黑盒 oracle 假设的办法，仍可能得到更好的辩论协议（第6节）。这是作者认为可能，不是已有构造。

实验覆盖范围

• 结果由 Theorem 4.1、Theorem 4.2、Theorem 5.1、Theorem 5.3 和 Lemma 5.2、Lemma 5.4 组成，对象是黑盒 oracle 上的递归分解。
• 完备性写明生成子节点的时间 T_D、节点上求解时间 T 与查询 Q，以及每步 fbs≤ρ；soundness 对任意 Alice 策略和单个错误输入成立，单次概率为 ρ^{-d}。
• 下界覆盖最多 m 次自适应查询、检验器可见整棵树、叶子查询两两不同；作者用全部叶子查询同一串的 q 元 AND 说明，查询可以相同时非平凡下界可以不成立。
• 正文中的定量例子是多数函数（前 2/3 位为 1 时 fbs=4、抽样概率 1/4；另有 50/99，以及 q=99 而 ρ=4 的说明）和 AND（全 1 输入上 fbs=n）。
• 论文未报告被测模型、实证辩论胜率、实际查询次数、重复次数，以及占优策略均衡与 Stackelberg 均衡的训练对比。

FBS Debate 是一套可扩展监督的辩论规则：两名计算方争论一个可递归分解的是非问题，人类只在最后选出的子问题上做黑盒判断。

要处理的缺口是，prover-estimator debate 虽能覆盖稳定分解，但只在输入分布的平均意义下成立，而且 Bob 的获胜策略一般要跟着 Alice 的作弊策略变。作者要在同一问题类上，让每个错误实例都能被抓住，并让诚实且正确成为双方的占优策略。

做法是把稳定性写成 fbs。Alice 每步给出 q 个子命题和声称真值；该步聚合必须与她先前的声称一致。Bob 解对偶线性规划，fbs 大于 ρ 则 Alice 立即失败，否则按对偶权重抽样一个子命题，从层 d 递归到层 0，再与 oracle O 对照。Bob 不必事先知道哪个子答案是错的。

主要理论结果是：

• 若存在每步 fbs 不超过 ρ、且节点上的问题可解的分解树，诚实 Alice 的获胜概率为 1；时间 O(d·(T_D+q·T))，查询 O(d·q·Q)（Theorem 4.1）。
• 顶层答案错误时，不论 Alice 如何行动，单次失败概率至少 ρ^{-d}（Theorem 4.2）。
• 重复 O(ρ^d log n) 次后，第4节写抓住概率至少 1−1/poly(n)，第1.2节写至少 1−O(1/poly(n))。
• 每层 fbs 至少为 ρ 时，要把每个 oracle 下的正确概率做到至少 1−ε（ε<1/2），黑盒自适应检验器至少需要 (1−2ε)ρ^d 次查询。
• 多数票且前 2/3 位为 1 时 fbs=4，按相应分布抽样碰到谎言的概率为 1/4。

作者的结论是：在这个递归分解框架里，fbs 刻画了辩论能处理的问题；只做黑盒人类判断查询时，不能再在该实例上渐近减少查询。他们同时认为，实践中计算有界的辩论者可能更难找出错误子问题，能否利用计算差距或放松黑盒假设越过这一障碍，仍是开放问题。