如何进行敏感辩论：面向AI辩论的实例最优协议

# How to Have a Sensitive Debate:An Instance-Optimal Protocol for AI Debate
Source: [https://arxiv.org/html/2610.02557](https://arxiv.org/html/2610.02557)
###### Abstract

As powerful AI systems reach and sometimes surpass the abilities of human experts across a range of cognitively demanding tasks, the problem of accurate oversight and supervision of these systems has become increasingly urgent\. One promising approach is AI debate, which seeks to leverage a debate between two powerful AIs to break complex questions down into simpler claims that can be easily judged directly\. Theoretical work on debate has formalized this intuition in the language of computational complexity theory, where the goal is to design protocols \(i\.e\., rules of the debate game\) that provide rigorous guarantees on correctness for judging solutions to complex problems with limited supervision\. Specifically, the current best protocol has been shown to work for all problems that have sufficiently stable decompositions into subproblems\. In this paper, we design a new protocol for this same class of problems that improves on the prior work in several ways\. First, correctness holds in a worst\-case rather than an average\-case sense\. Second, being honest and correct is a dominant\-strategy equilibrium for both debaters, rather than a Stackelberg equilibrium\. Finally, we prove black\-box lower bounds, showing that our new protocol is instance\-wise optimal\. That is, no protocol for this class of problems can outperform ours while making only black\-box queries to human judgments\. We obtain these results by relating the notion of stable problem decompositions to the concept of fractional block sensitivity from query complexity\.

00footnotetext:\*Equal contribution\. Listing order is random\.## 1Introduction

Modern AI systems are trained to perform complex reasoning tasks including autonomous software engineering\([Anthropic, 2026](https://arxiv.org/html/2610.02557#bib.bib5)\), novel mathematical research\([Abouzaid et al\., 2026](https://arxiv.org/html/2610.02557#bib.bib2)\), and general economically valuable tasks across a wide range of occupations\([Patwardhan et al\., 2025](https://arxiv.org/html/2610.02557#bib.bib24)\)\. One of the core drivers of this progress is the ability to design training environments with verifiable reward signals, e\.g\., numerical solutions or automatically verifiable proofs for mathematics or automated test cases for code\. As the scope of tasks performed by AI systems broadens and increases in complexity, it becomes increasingly difficult to provide automatically verifiable rewards that capture all relevant aspects of the task\. Furthermore, many tasks of interest have inherently subjective or fuzzy descriptions, so that human verification of AI outputs is necessary\. These difficulties lead to the problem of*scalable oversight*— the design of training protocols that leverage the power of rapidly improving AI systems in order to augment human abilities to provide accurate training supervision to these same systems\([Leike et al\., 2018](https://arxiv.org/html/2610.02557#bib.bib21)\)\.

As a motivating example, consider the case of an autonomous AI agent tasked with completing a research project in the quantitative social sciences\. The description of the task will likely be high\-level and somewhat open\-ended, possibly including relevant data sources and the question the analysis is trying to answer\. However, in any such project there will be many individual decisions with multiple plausible choices, along with requirements that are not explicitly mentioned, e\.g\., don’t calculate hundreds of different subpopulation statistics from the data, and then choose to analyze the most surprising one post hoc\. Hence, directly evaluating the full output of an autonomous AI agent would both require human judgment to some degree and be very difficult even for an expert human to judge directly\. Furthermore, the cost of failing to provide accurate supervision in such settings can be quite high\. For example, even in slightly misconfigured training environments for software engineering, AI systems often find cheating solutions, such as editing test cases to always pass, rather than actually solving the problem\. Worse still, in some such cases AI systems have learned to generalize this negative behavior, resulting in dishonest and harmful actions across many other settings unrelated to coding\([MacDiarmid et al\., 2025](https://arxiv.org/html/2610.02557#bib.bib22)\)\.

One of the primary approaches to addressing the scalable oversight question is*AI debate*, where two powerful AI systems argue about the correctness of an AI output, and a human judges the outcome\([Irving et al\., 2018](https://arxiv.org/html/2610.02557#bib.bib16)\)\. Intuitively, the idea is that each debater will be able to recursively zoom in on individual flaws in specific pieces of their opponent’s arguments, until the original problem has been broken down to a level that is simple enough for a human to judge directly\. Critically, there are complexity\-theoretic formalizations of this setup that can allow for rigorous definitions and evaluations of what it means for limited human judges to verify the outputs of AI systems that are much too complex to judge\.

Prior theoretical research has focused on the design of provably\-correct debate protocols, i\.e\., rules of the game that constrain the AI debaters and specify how the human judge should evaluate their arguments\. This prior work encountered a major obstacle known as the*obfuscated arguments problem*, where one debater can efficiently produce a dishonest argument which cannot be efficiently refuted by their opponent\([Barnes, 2020](https://arxiv.org/html/2610.02557#bib.bib6)\)\. While it was shown to be possible to obtain provably\-correct protocols for certain limited classes of problems\([Brown\-Cohen et al\., 2024](https://arxiv.org/html/2610.02557#bib.bib7)\), the initial promise of debate for recursively decomposing highly complex problems remained in doubt\. Subsequent progress on the obfuscated argument problem was made via the prover\-estimator debate protocol of[Brown\-Cohen et al\. \(2025\)](https://arxiv.org/html/2610.02557#bib.bib8), which avoids obfuscated arguments for a class of problems that admit*sufficiently stable*decompositions into subproblems\. Despite this progress on expanding the class of problems that can be handled by debate, the prover\-estimator protocol has additional limitations when compared to prior work: it provides average\-case guarantees that hold for a weaker equilibrium concept than previously studied\.

In this paper we design a new debate protocol that provides worst\-case guarantees for the original, stronger dominant\-strategy equilibrium concept\. The protocol handles exactly the same class of sufficiently stable problems as prover\-estimator debate, while also being simpler to execute and analyze\. We further prove that this protocol is instance optimal unless further structural assumptions are made on the human judgments used to verify debates\.

### 1\.1Our Results

Our new protocol is simple to describe\. The first debater, Alice, decomposes the original claim into sub\-claims\. The second debater, Bob, then has two choices: either \(1\) demonstrate that Alice’s decomposition is too*sensitive*to small errors in the sub\-claims, or \(2\) choose a sub\-claim on which to continue the debate recursively\. The key to the analysis is the equivalence between the notion of stable decompositions required for prover\-estimator debate and bounds on*fractional block sensitivity*, a quantity defined in the query complexity literature which is tightly connected to the number of queries a randomized verifier must make to check an untrusted proof\([Kulkarni and Tal, 2016](https://arxiv.org/html/2610.02557#bib.bib20)\)\. In particular, an upper bound on the fractional block sensitivity of Alice’s decomposition implies an efficiently computable strategy for Bob to select a sub\-claim that has a non\-trivial chance of being incorrect\.

The equivalence to fractional block sensitivity further enables us to prove that the performance of our protocol is*instance optimal*assuming black\-box access to human judgments\. That is, if the particular problem instance admits a decomposition with fractional block sensitivityρ\\rho, then*any protocol*which correctly decides the outcome on this instance cannot have asymptotically lower complexity for the debaters\. All prior theoretical work on debate has modeled human judgment as a black\-box oracle, so this result can be interpreted as demonstrating the necessity of going beyond this model in order to further expand the class of problems solvable via debate\.

### 1\.2Technical Overview

We next give an informal mathematical overview of our protocol and proof techniques\. We will begin by describing how the protocol works in our running example of an autonomous AI agent Alice performing quantitative social science research\.

#### The protocol in action\.

In order to efficiently evaluate the correctness of the final research paper and codebase produced by the quantitative social science agent, we use a debate between Alice, who defends her work, and another AI Bob who attempts to find flaws\. To determine the validity of a claim in the paper, we ask Alice to decompose the original claimxxinto sub\-claimsy1,…,yqy\_\{1\},\\dots,y\_\{q\}\. One can view these sub\-claims as pieces of supporting evidence\. For example, the claimxxmight be that a certain statistical modeling assumption is justified\. Suppose that we would believe this claim if a majority of correct, published papers in the existing literature supported it\. In this case, the sub\-claimsyiy\_\{i\}are of the form: this particular paper from the existing literature is both correct and supports the original claim\. Furthermore, the truth of the original claimxxis the majority vote of the truth values of the sub\-claimsyiy\_\{i\}\.

Next, suppose that Alice claims that in fact2/32/3of the published papersyiy\_\{i\}support the claim\. We view this as an assignment by Alice of alleged truth valuesziz\_\{i\}to each sub\-claimyiy\_\{i\}\. In this case, the key insight is that Bob need not check every single paper for correctness in order to verify the overall claim\. Instead, Bob can just randomly sample a paper among the2/32/3that Alice says support the original claim, i\.e\., those wherezi=1z\_\{i\}=1\. If Alice is lying about the original claimxx, then at least1/61/6of the sub\-claims must also be lies\. Hence, by sampling randomly among the2/32/3wherezi=1z\_\{i\}=1, Bob will have a1/62/3=1/4\\frac\{1/6\}\{2/3\}=1/4chance of catching Alice in a lie\. Thus, just by sampling a few research papers from the entire area to check, Bob can be confident of catching Alice in a lie\.

On the other hand, suppose that Alice claims that 50 out of a total of 99 papersyiy\_\{i\}support the original claimxx\. In this case, Bob has no recourse but to check every single one of the 50 papers, as even a single incorrect paper would flip the majority vote and overturn the truth of the original claim\. The key to our protocol is that Bob is allowed to demonstrate that Alice has made an unreasonably sensitive claim of this form, in which case Alice will lose the debate\. This in turn requires Alice to only decompose her claims in a way that is not too sensitive to errors in individual sub\-claims\. We view this as a very natural restriction when arguing about claims that inherently involve fuzzy human judgment\. Indeed, one should be very suspicious of any argument that is highly sensitive to changes in individual pieces of evidence, and yet relies on fuzzy human judgments in each step\.

#### Formalization via fractional block sensitivity\.

Our protocol follows the same outline as described in the example: Alice decomposes a claimxxinto sub\-claimsyiy\_\{i\}, Bob either objects that Alice’s decomposition is too sensitive, or instead selects a sub\-claim to debate further\. The key technical component is the notion of*fractional block sensitivity*which generalizes the intuition above about the majority function to all possible aggregation functions Alice might choose\. In particular, the fractional block sensitivityρ\\rhois defined as the optimum of a linear program that depends on the aggregation function and Alice’s alleged truth valuesziz\_\{i\}for the sub\-claimsyiy\_\{i\}\. In the case of the majority vote function with2/32/3of the truth valuesziz\_\{i\}set to 1, the optimum of the linear program isρ=4\\rho=4, which corresponds to Bob’s chance of1/41/4of catching Alice in a lie if he samples a randomyiy\_\{i\}among the2/32/3claimed true\. This correspondence is not a coincidence–it generalizes to any aggregation function\. More formally, the dual solution of the fractional block sensitivity linear program directly yields probabilitiespip\_\{i\}for Bob to sample sub\-claims\. When sampling sub\-claims with these probabilities, Bob has at least a chance of1/ρ1/\\rhoof catching Alice in a lie\. See[Section3\.3](https://arxiv.org/html/2610.02557#S3.SS3)for the precise formal definition\.

The protocol runs recursively on the sub\-claim sampled by Bob, until it reaches a depth ofdd, whereupon a human judge directly evaluates the final selected sub\-claim\. Unless Alice wants to lose immediately, she must ensure that in each round the decomposition into sub\-claims that she makes has fractional block sensitivity bounded byρ\\rho\. Thus, we conclude that if Bob follows the sampling scheme provided above, he will catch Alice in a lie with probability at leastρ−d\\rho^\{\-d\}\. Hence, by running the protocolO⁡\(ρd​log⁡n\)O\(\\rho^\{d\}\\log n\)times, Bob will catch Alice in a lie with probability at least1−O⁡\(1/poly⁡\(n\)\)1\-O\(1/\\poly\(n\)\)\. See[Section4](https://arxiv.org/html/2610.02557#S4)for details\. To make sense of this result, recall that Alice decomposes each original claim intoqqsub\-claims\. So exploring the full tree of sub\-claims would require timeqdq^\{d\}\. As shown in the example of the majority vote aggregation function, one can haveq=99q=99, whileρ=4\\rho=4, implying thatρd\\rho^\{d\}can be significantly smaller\. In the standard setting, the debate has depthd=O⁡\(log⁡n\)d=O\(\\log n\), implying that our protocol allows for a polynomial innnspeed\-up beyond exhaustive search of Alice’s decomposition\.

#### Honesty and correctness are dominant strategies\.

Our protocol for fractional block sensitivity \(FBS\) debate satisfies the key properties of*completeness*and*soundness*\. Completeness requires that if the original claimxxis correct, then no matter what strategy Bob employs, Alice can always win by honestly and correctly decomposing every claim\. Similarly, soundness requires that if the original claimxxis incorrect, then no matter what strategy Alice employs, Bob can win with overwhelming probability by honestly following the prescribed protocol\. In other words, honestly and correctly following the prescribed protocol is a*dominant strategy*for each player in the debate game\. This is in contrast to the prior prover\-estimator debate protocol, which only guarantees soundness under the following Stackelberg equilibrium condition: for any dishonest strategy selected by Alice, there exists a winning strategy by Bob, which in general depends on Alice’s strategy in a potentially complicated way\. This is a technically much weaker condition, and in practice training for dominant strategy equilibria is much more stable and tractable than Stackelberg equilibria\.

Furthermore, our protocol applies on a worst\-case basis: if an individual claimxxis incorrect, our protocol will allow Bob to efficiently identify a flawed sub\-claim for the human judge\. In contrast, the prover\-estimator protocol only satisfies soundness on average over a distribution on inputs\. This is sufficient to guarantee that training the debaters to maximize their expected win rates leads to a debate equilibrium where the debaters are honest on all but a small fraction of questions\. However, our protocol for FBS debate goes further by guaranteeing that on each individual question, honesty is the best policy\.

#### Instance\-wise optimality\.

Finally, we show in[Section5](https://arxiv.org/html/2610.02557#S5)that any protocol with only black\-box access to human judgments must make at leastΩ⁡\(ρd\)\\Omega\(\\rho^\{d\}\)queries to find a flawed sub\-claim with constant probability, matching the cost of our FBS debate protocol\. This lower bound holds instance\-wise: if the best decomposition of an original claimxxinto a tree of sub\-claims has fractional block sensitivityρ\\rhoin each step, thenρd\\rho^\{d\}queries are required on that particular instancexx\. The assumption of black\-box access to human judgments is critical for the lower bound to hold\. One can view this instance\-wise optimality as demonstrating that the black\-box judgment assumption, which is common to all prior theoretical work on debate, must be relaxed in order to make further progress on debate protocols\.

## 2Related work

Prior work on the complexity\-theoretic formulation of debate began with[Irving et al\. \(2018\)](https://arxiv.org/html/2610.02557#bib.bib16), whose protocol works for computationally unbounded provers\. Subsequently,[Barnes \(2020\)](https://arxiv.org/html/2610.02557#bib.bib6)pointed out the obfuscated arguments problem, demonstrating that current protocols would fail in the case that the AI debaters were equally computationally powerful, but still computationally bounded\.[Brown\-Cohen et al\. \(2024\)](https://arxiv.org/html/2610.02557#bib.bib7)introduced doubly\-efficient debate, which works for computationally bounded debaters, but solves a more limited class of problems\. Most closely related to our work is that of[Brown\-Cohen et al\. \(2025\)](https://arxiv.org/html/2610.02557#bib.bib8), which introduced the prover\-estimator debate protocol to handle a broader class of recursively decomposable problems for computationally bounded debaters\. Prover\-estimator debate introduced the notion of stability \(equivalent to fractional block sensitivity\) that we study in this paper\.

The idea of having computationally unbounded provers convince a polynomial\-time verifier was already present in the work on alternating Turing machines of[Chandra et al\. \(1981\)](https://arxiv.org/html/2610.02557#bib.bib10)\. Another complexity\-theoretic model of arguments involving private communication between adversarial provers and a judge is due to[Feige and Kilian \(1997\)](https://arxiv.org/html/2610.02557#bib.bib13)\. Finally, competing provers have been studied in the context of secure delegation of computation by[Canetti et al\. \(2013\)](https://arxiv.org/html/2610.02557#bib.bib9)\. On the algorithmic side,[Chen et al\. \(2023\)](https://arxiv.org/html/2610.02557#bib.bib12)designed algorithms for the problem of learning the equilibrium in the zero\-sum game defined by a debate protocol\. Here the focus is on ensuring the learning algorithms and the effort of the judge are computationally efficient while the strategy space may be exponentially large\.

There have also been several recent works on utilizing more classical single\-prover interactive proofs in machine learning\. This has been done most frequently with the goal of verifying that the output of an AI is correct\([Amit et al\., 2024](https://arxiv.org/html/2610.02557#bib.bib3);[Anil et al\., 2021](https://arxiv.org/html/2610.02557#bib.bib4);[Hammond and Adam\-Day, 2025](https://arxiv.org/html/2610.02557#bib.bib15);[Chen et al\., 2026](https://arxiv.org/html/2610.02557#bib.bib11)\), while some research has also focused on using these techniques for interpretability and legibility\([Wäldchen et al\., 2022](https://arxiv.org/html/2610.02557#bib.bib26);[Kirchner et al\., 2024](https://arxiv.org/html/2610.02557#bib.bib19)\)\. In particular,[Chen et al\. \(2026\)](https://arxiv.org/html/2610.02557#bib.bib11)construct doubly\-efficient interactive proofs and arguments for*oracle*circuits when either the computation is*robust*to corruption of a small fraction of its oracle transcript or the oracle has low\-degree algebraic structure\. Their robustness condition is a uniform\-weight special case of bounded FBS at the level of a fixed one\-step aggregator, while our local FBS condition permits an optimized nonuniform sampling distribution\.111Theirε\\varepsilon\-robustness assumption impliesfbs=O⁡\(1/ε\)\\operatorname\{fbs\}=O\(1/\\varepsilon\)for the induced Boolean function: uniformly assigning weight1/\(ε​ℓ\)1/\(\\varepsilon\\ell\)to each of theℓ\\elloracle\-answer coordinates gives a feasible solution to the dual FBS program\.Their full framework remains incomparable to ours: their protocol assumes an explicit circuit fixed at the beginning for the target computation, whereas ours uses an \(online\) recursive decomposition framework with a fixed one\-step aggregator\. Their low\-degree\-oracle result is orthogonal to our lower bound because it imposes additional algebraic structure on the oracle\.

Several empirical works have measured the performance of actual LLMs in setups inspired by theoretical debate protocols\([Michael et al\., 2023](https://arxiv.org/html/2610.02557#bib.bib23);[Kenton et al\., 2024](https://arxiv.org/html/2610.02557#bib.bib17);[Khan et al\., 2024](https://arxiv.org/html/2610.02557#bib.bib18)\)\. These results provided some evidence that debate helps certain limited LLM judges more accurately verify the output of other LLMs\. Finally, large\-scale training for mathematical reasoning has relied on the power of a debate\-like training protocol in which one model critiques a proof and another model further critiques the critique\([Shao et al\., 2025](https://arxiv.org/html/2610.02557#bib.bib25)\)\.

## 3Preliminaries

### 3\.1Complexity\-theoretic framework of AI debate

We adopt a complexity\-theoretic framework \(cf\.[Brown\-Cohen et al\. \(2025\)](https://arxiv.org/html/2610.02557#bib.bib8)\) for studying the power of AI debate\. We represent the human judgment as an oracle𝒪:\{0,1\}n→\{0,1\}\\mathcal\{O\}:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}, where the value of𝒪⁡\(u\)∈\{0,1\}\\mathcal\{O\}\(u\)\\in\\\{0,1\\\}corresponds to the human judgment on a particular questionuu\. Both debaters and the judge are algorithms modeled as Turing machines given black\-box query access to the oracle𝒪\\mathcal\{O\}\. We denote byM𝒪​\(x\)M^\{\\mathcal\{O\}\}\(x\)the result of running algorithmMMon inputxxgiven access to𝒪\\mathcal\{O\}\.

The aim of debate is to design protocols that solve broad classes of computational problems while using few queries to the human\-judgment oracle𝒪\\mathcal\{O\}\. Any decision problem \(yes\-or\-no problem\) can be represented by a*language*L⊆\{0,1\}∗L\\subseteq\\\{0,1\\\}^\{\*\}, wherex∈Lx\\in Lmeans that the correct answer on inputxxis “yes\.” Equivalently, we may viewLLas a Boolean functionL:\{0,1\}n→\{0,1\}L:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}, withL⁡\(x\)=1L\(x\)=1iffx∈Lx\\in L\.

### 3\.2Recursively decomposable problems

In this paper, we focus on the class of problemsLLthat exhibit a recursive decomposition\. There are two components of a recursive decomposition: a*one\-step aggregator*, and a*decomposition tree*\. Intuitively, if the original problemxxis decomposed intoqqsub\-problemsy=\(y1,…,yq\)y=\(y\_\{1\},\\dots,y\_\{q\}\)in one step, then a one\-step aggregator should return the correct answer forxxwhen given the correct answers toyy\.

###### Definition 3\.1\(One\-step aggregator\)\.

LetLLbe a language\. A widthqqone\-step aggregatorMDM\_\{D\}forLLis an algorithm that takes as input a problem instancex∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, a sequence ofqq*sub\-problems*y=\(y1,…,yq\)∈\{0,1\}n×qy=\(y\_\{1\},\\dots,y\_\{q\}\)\\in\\\{0,1\\\}^\{n\\times q\}, and a sequence ofqq*answers*z=\(z1,…,zq\)∈\{0,1\}qz=\(z\_\{1\},\\dots,z\_\{q\}\)\\in\\\{0,1\\\}^\{q\}\. The pair\(x,y\)\(x,y\)is called a one\-step decomposition ofxx\.

The one\-step aggregatorMDM\_\{D\}should either accept or reject a one\-step decomposition\(x,y\)\(x,y\)\. IfMDM\_\{D\}rejects a one\-step decomposition\(x,y\)\(x,y\), thenMD\(x,y,z\)=⊥M\_\{D\}\(x,y,z\)=\\botfor anyzz; otherwise,MD​\(x,y,z\)∈\{0,1\}M\_\{D\}\(x,y,z\)\\in\\\{0,1\\\}for anyzz\. Furthermore, ifMDM\_\{D\}accepts a one\-step decomposition\(x,y\)\(x,y\), thenMD​\(x,y,z\)=L⁡\(x\)M\_\{D\}\(x,y,z\)=L\(x\)ifzzgives the correct answers toyy, i\.e\.,zi=L⁡\(yi\)z\_\{i\}=L\(y\_\{i\}\)for alli∈\[q\]i\\in\[q\]\.

In the setting of AI debate, we assume the one\-step aggregatorMDM\_\{D\}is a rather simple and efficient algorithm that all parties agree on at the beginning of the protocol\. One simple example ofMDM\_\{D\}is taking the AND of all answersziz\_\{i\}, which captures a classic debate strategy — if all the supporting sub\-claims are correct, then the original claim is also correct\. We will be interested more generally in one\-step aggregators that make fuzzier use of supporting sub\-claims\. To return to the running example of the autonomous agent performing quantitative social science research, the one\-step aggregator might take the form: if the majority of published papers in an area support the original claim, then the claim is true\. In this case, the supporting sub\-claimsyiy\_\{i\}correspond to the set of published papers in the area, and the aggregatorMDM\_\{D\}is the majority vote ofziz\_\{i\}, each of which represents whether or not the paperyiy\_\{i\}supports the original claim\.

We further require that the property ofMDM\_\{D\}as defined in[Definition3\.1](https://arxiv.org/html/2610.02557#S3.Thmtheorem1)can be easily verified by human judgment\. Note that in this definition,MDM\_\{D\}is allowed to reject a possibly correct but hard\-to\-verify one\-step decomposition; it could still be useful as long as it accepts most of the obviously valid decompositions\. Given this, we can assume thatMDM\_\{D\}never outputs⊥\\botin a debate protocol without loss of generality: If any debater proposes a one\-step decomposition rejected byMDM\_\{D\}, then we can make that debater immediately lose the debate, so any clever debater would avoid that\.

We now define the decomposition tree using the one\-step aggregator\.

###### Definition 3\.2\(Decomposition Tree\)\.

LetLLbe a language and fix a widthqqone\-step aggregatorMDM\_\{D\}forLL\. A depthdd, widthqq*decomposition tree*𝒯\\mathcal\{T\}for inputx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}is defined as follows\.

1. 1\.Each tree nodeuucorresponds to a problem instancex^u∈\{0,1\}n\\hat\{x\}\_\{u\}\\in\\\{0,1\\\}^\{n\}for languageLL; the root node at levelk=dk=dcorresponds to the inputxx\.
2. 2\.For each non\-leaf nodeuuat levelk\>0k\>0, we haveL⁡\(x^u\)=MD​\(x^u,yu,zu\)L\(\\hat\{x\}\_\{u\}\)=M\_\{D\}\(\\hat\{x\}\_\{u\},y\_\{u\},z\_\{u\}\), whereyu=\(yu,1,…,yu,q\)y\_\{u\}=\(y\_\{u,1\},\\dots,y\_\{u,q\}\)are the sub\-problems from the child nodes ofuuat levelk−1k\-1, andzu=\(L⁡\(yu,1\),…,L⁡\(yu,q\)\)z\_\{u\}=\(L\(y\_\{u,1\}\),\\ldots,L\(y\_\{u,q\}\)\)\.
3. 3\.For each leaf nodeuuat levelk=0k=0, there exists a single queryquq\_\{u\}such thatL⁡\(x^u\)=𝒪⁡\(qu\)L\(\\hat\{x\}\_\{u\}\)=\\mathcal\{O\}\(q\_\{u\}\)\.

Unlike the one\-step aggregatorMDM\_\{D\}, which is fixed at the beginning, a decomposition tree𝒯\\mathcal\{T\}for a given inputxxis usually generated on the fly as the debate protocol proceeds\. A brute\-force debate protocol that visits all the leaves of a decomposition tree requiresqdq^\{d\}queries to the oracle𝒪\\mathcal\{O\}\.222One can apply the*doubly\-efficient*debate protocol[Brown\-Cohen et al\. \(2024\)](https://arxiv.org/html/2610.02557#bib.bib7)here to reduce the number of queries to𝒪\\mathcal\{O\}to only11\. However, the time complexity of this protocol is stillO⁡\(qd\)O\(q^\{d\}\), which is infeasible in most cases\.A better debate protocol based on recursive decomposition should avoid checking most of the nodes in the decomposition tree\.

### 3\.3Fractional block sensitivity

The main structural assumption that characterizes the class of problems solvable by our protocol is that the functions arising in the decomposition of the problem have bounded*fractional block sensitivity*\. Fractional block sensitivity is a metric from query complexity defined for a Boolean functionff\. Intuitively, it captures how closely a distribution can match its individual marginals to a fixed inputxxwhile still flipping the output offf\.

To gain an intuition for this notion, consider the majority vote functionf⁡\(x\)=Majority\(x\)f\(x\)=\\textsc\{Majority\(x\)\}and the stringx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}where the first 2/3rds of the inputs are 1 and the rest are 0\. In this case, in order to change the output off⁡\(x\)f\(x\), one would need to flip at least 1/6th of the input bits among the 2/3rds that are 1\. Thus, in any distribution which flips the output, the marginal distribution on each input coordinate in the first 2/3rds must be off by at least1/62/3=1/4\\frac\{1/6\}\{2/3\}=1/4\. In this case the fractional block sensitivity offfwould be44\.

On the other hand, for the Boolean AND functionf​\(x\)=And​\(x\)f\(x\)=\\textsc\{And\}\(x\)on the all\-ones input, it is possible to flip the output offfby selecting just one input bit uniformly at random to flip to 0\. The marginals of this distribution are all1n\\frac\{1\}\{n\}, and so the fractional block sensitivity isnn\. This is a much higher fractional block sensitivity than for the majority vote function, capturing the idea that it is much easier to hide a single mistake that changes the entire outcome for the AND function than it is for the majority function\. In general, fractional block sensitivity generalizes this intuition that one should not be able to stealthily flip the output of a function while maintaining a very similar marginal distribution on input bits\.

###### Definition 3\.3\(Fractional block sensitivity\)\.

Letf:\{0,1\}n→\{0,1\}f:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}andx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}\. For a nonempty setB⊆\[n\]B\\subseteq\[n\], letxBx^\{B\}denote the string obtained fromxxby flipping the bits in the coordinates ofBB, i\.e\.,

\(xB\)i=\{1−xiif​i∈B,xiif​i∉B\.\(x^\{B\}\)\_\{i\}\\;=\\;\\begin\{cases\}1\-x\_\{i\}&\\text\{if \}i\\in B,\\\\ x\_\{i\}&\\text\{if \}i\\notin B\.\\end\{cases\}A setB⊆\[n\]B\\subseteq\[n\]is a*sensitive block forffatxx*iff⁡\(x\)≠f⁡\(xB\)f\(x\)\\neq f\(x^\{B\}\)\. Write𝒮x​\(f\)\\mathcal\{S\}\_\{x\}\(f\)for the family of all sensitive blocks atxx\.

The*fractional block sensitivity offfatxx*is the optimal value of the linear program

fbsx⁡\(f\)=max⁡\{∑B∈𝒮x​\(f\)wB\|wB≥0​for all​B∈𝒮x​\(f\),∑B∈𝒮x​\(f\)i∈BwB≤1for all​i∈\[n\]\}\.\\operatorname\{fbs\}\_\{x\}\(f\)\\;=\\;\\max\\left\\\{\\sum\_\{B\\in\\mathcal\{S\}\_\{x\}\(f\)\}w\_\{B\}\\;\\middle\|\\;\\begin\{array\}\[\]\{l\}w\_\{B\}\\geq 0\\ \\text\{for all \}B\\in\\mathcal\{S\}\_\{x\}\(f\),\\\\\[2\.0pt\] \\displaystyle\\sum\_\{\\begin\{subarray\}\{c\}B\\in\\mathcal\{S\}\_\{x\}\(f\)\\\\ i\\in B\\end\{subarray\}\}w\_\{B\}\\;\\leq\\;1\\quad\\text\{for all \}i\\in\[n\]\\end\{array\}\\right\\\}\.The*fractional block sensitivity offf*is

fbs⁡\(f\)=maxx∈\{0,1\}n⁡fbsx⁡\(f\)\.\\operatorname\{fbs\}\(f\)\\;=\\;\\max\_\{x\\in\\\{0,1\\\}^\{n\}\}\\operatorname\{fbs\}\_\{x\}\(f\)\.

###### Definition 3\.4\(Dual of fractional block sensitivity\)\.

Fixf:\{0,1\}n→\{0,1\}f:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}andx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, and let𝒮x​\(f\)\\mathcal\{S\}\_\{x\}\(f\)denote the family of sensitive blocks atxx\(as above\)\. The dual linear program to the definition offbsx⁡\(f\)\\operatorname\{fbs\}\_\{x\}\(f\)is

fbsx⁡\(f\)=min⁡\{∑i=1nti\|ti≥0for all​i∈\[n\],∑i∈Bti≥1for all​B∈𝒮x​\(f\)\}\.\\operatorname\{fbs\}\_\{x\}\(f\)\\;=\\;\\min\\left\\\{\\sum\_\{i=1\}^\{n\}t\_\{i\}\\ \\middle\|\\ \\begin\{array\}\[\]\{l\}t\_\{i\}\\geq 0\\quad\\text\{for all \}i\\in\[n\],\\\\\[2\.0pt\] \\displaystyle\\sum\_\{i\\in B\}t\_\{i\}\\;\\geq\\;1\\quad\\text\{for all \}B\\in\\mathcal\{S\}\_\{x\}\(f\)\\end\{array\}\\right\\\}\.

The dual assigns nonnegative weights\{ti\}i∈\[n\]\\\{t\_\{i\}\\\}\_\{i\\in\[n\]\}to coordinates so that every sensitive blockBBhas total weight at least11; it minimizes the total weight∑iti\\sum\_\{i\}t\_\{i\}\. Thus the dual is a fractional*hitting set/cover*of the sensitive blocks by coordinates\.333The dual of fractional block sensitivity is essentially the*randomized certificate complexity*defined in[Aaronson \(2008\)](https://arxiv.org/html/2610.02557#bib.bib1)\.By strong duality, its optimum equals the primal valuefbsx⁡\(f\)\\operatorname\{fbs\}\_\{x\}\(f\)\.

## 4Protocol

In this section, we present our debate protocol based on the fractional block sensitivity of the recursive decomposition\. We then prove that our protocol satisfies both the completeness and soundness conditions in the worst case\.

FBS Debate ProtocolSetup:Access to the inputx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}, a languageLL, the human\-judgment oracle𝒪\\mathcal\{O\}, a one\-step aggregatorMDM\_\{D\}with widthqq, the depth of the decomposition treedd, and a hyperparameterρ\\rho\.Initialization:Alice outputs a bitA⁡\(x\)A\(x\)as the answer toL⁡\(x\)L\(x\)\.At levelk∈\{d,d−1,…,1\}k\\in\\\{d,d\-1,\\ldots,1\\\}:1\.Alice decomposes the current problemx^\\hat\{x\}intoqqsub\-problemsy=\(y1,…,yq\)y=\(y\_\{1\},\\ldots,y\_\{q\}\), and then outputs a sequencez=\(z1,…,zq\)z=\(z\_\{1\},\\ldots,z\_\{q\}\)as the answers toy1,…,yqy\_\{1\},\\ldots,y\_\{q\}\.MD​\(x^,y,z\)M\_\{D\}\(\\hat\{x\},y,z\)must be equal to the answer Alice claimed forx^\\hat\{x\}in the previous round, denoted byA⁡\(x^\)A\(\\hat\{x\}\); otherwise Alice loses immediately\.2\.Bob checks whetherfbsz\(MD\(x^,y,⋅\)\)≤ρ\\operatorname\{fbs\}\_\{z\}\\left\(M\_\{D\}\(\\hat\{x\},y,\\cdot\)\\right\)\\leq\\rhoby solving the dual LP\. If not, Alice immediately loses\.3\.If true, letpi≔ti/∑j=1qtjp\_\{i\}\\coloneqq t\_\{i\}/\\sum\_\{j=1\}^\{q\}t\_\{j\}, wherettis the optimal solution to the dual LP\. With probabilitypip\_\{i\}, Bob will pick theii\-th sub\-problemyiy\_\{i\}for recursion, setx^←yi\\hat\{x\}\\leftarrow y\_\{i\}andA⁡\(x^\)←ziA\(\\hat\{x\}\)\\leftarrow z\_\{i\}, and continue to levelk−1k\-1\.At the leaf level \(k=0k=0\):If the answer Alice claimed for the current sub\-problem matches𝒪\\mathcal\{O\}, Alice wins; otherwise Bob wins\.

We show that an honest Alice can win the debate if Alice can find a decomposition tree solving the problem with low fractional block sensitivity\.

###### Theorem 4\.1\(Completeness\)\.

LetT,TD,QT,T\_\{D\},Qbe three parameters\. An honest Alice can always win in the FBS debate on inputxxinO⁡\(d⋅\(TD\+q⋅T\)\)O\\big\(d\\cdot\(T\_\{D\}\+q\\cdot T\)\\big\)time andO⁡\(d⋅q⋅Q\)O\(d\\cdot q\\cdot Q\)queries to𝒪\\mathcal\{O\}if there exists a decomposition tree𝒯\\mathcal\{T\}forxxsuch that

- •Alice can calculate the children of any non\-leaf node in𝒯\\mathcal\{T\}in timeTDT\_\{D\}\.
- •Alice can solveL⁡\(x^u\)L\(\\hat\{x\}\_\{u\}\)at any nodeuuin𝒯\\mathcal\{T\}in timeTTandQQqueries to𝒪\\mathcal\{O\}; \(Solvability\)
- •For every non\-leaf nodeuuin𝒯\\mathcal\{T\}, ifyyare the sub\-problems in the child nodes ofuuandzzare the correct answers toyy, thenfbsz\(MD\(x^u,y,⋅\)\)≤ρ\\operatorname\{fbs\}\_\{z\}\\left\(M\_\{D\}\(\\hat\{x\}\_\{u\},y,\\cdot\)\\right\)\\leq\\rho\. \(FBS condition\)

x^\\hat\{x\}Alice claimsA⁡\(x^\)A\(\\hat\{x\}\)levelkkStep 1 — Alice Decomposesx^\\hat\{x\}into y=\(y1,…,yq\),\\;\\;\\;y=\(y\_\{1\},\\dots,y\_\{q\}\), claims answers z=\(z1,…,zq\)\\;\\;\\;z=\(z\_\{1\},\\dots,z\_\{q\}\)\. Must satisfy MD​\(x^,y,z\)=A⁡\(x^\)\\;\\;\\;M\_\{D\}\(\\hat\{x\},y,z\)=A\(\\hat\{x\}\) elseAlice losesy1y\_\{1\}y2y\_\{2\}⋯\\cdotsyiy\_\{i\}yqy\_\{q\}z1z\_\{1\}z2z\_\{2\}ziz\_\{i\}zqz\_\{q\}Step 2 — BobSolve dual LP forfbsz\(MD\(x^,y,⋅\)\)\\mathrm\{fbs\}\_\{z\}\\\!\\bigl\(M\_\{D\}\(\\hat\{x\},y,\\cdot\)\\bigr\):min∑j=1qtjs\.t\.tj≥0,∑j∈Btj≥1∀B∈Sz\\displaystyle\\min\\sum\_\{j=1\}^\{q\}t\_\{j\}\\;\\;\\text\{s\.t\.\}\\;\\;t\_\{j\}\\geq 0,\\;\\sum\_\{j\\in B\}t\_\{j\}\\geq 1\\;\\forall B\\in S\_\{z\}iffbsz\>ρ\\;\\mathrm\{fbs\}\_\{z\}\>\\rho⇒\\RightarrowAlice loseselsesampleiiwithpi=ti∑jtjp\_\{i\}=\\dfrac\{t\_\{i\}\}\{\\sum\_\{j\}t\_\{j\}\}yiy\_\{i\}levelk−1k\-1— recursion continues on the sampled childyiy\_\{i\}One round of FBS Debate \(at levelkk\)x=x^dx=\\hat\{x\}^\{d\}leveldd⋯\\cdotsx^d−1\\hat\{x\}^\{d\-1\}leveld−1d\{\-\}1⋮\\vdots⋮\\;\\vdotsx^1\\hat\{x\}^\{1\}level11⋯\\cdotsx^0\\hat\{x\}^\{0\}level00\(leaf\)Leaf check Query oracleO⁡\(qx^0\)O\(q\_\{\\hat\{x\}^\{0\}\}\) ifA⁡\(x^0\)=O⁡\(qx^0\)A\(\\hat\{x\}^\{0\}\)=O\(q\_\{\\hat\{x\}^\{0\}\}\)⇒\\RightarrowAlice wins else⇒\\RightarrowBob winsRecursive structureAt each levelk↓k−1k\\\!\\downarrow\\\!k\{\-\}1thesingle round above is repeated:Alicedecomposes→\\toBobruns FBS checkBobsamples one child asx^k−1\\hat\{x\}^\{k\-1\}ddlevels ofrecursion

Figure 1:The FBS debate protocol\.*Top:*one round at levelkk\.*Bottom:*the recursion forddlevels\.###### Proof\.

The honest strategy takesA⁡\(x\)=L⁡\(x\)A\(x\)=L\(x\), decomposes exactly as𝒯\\mathcal\{T\}at every node, and setszzto be the correct answers at every decomposition step\. Then \(i\) the consistency check always passes by the solvability condition; \(ii\) the stability check always passes due to the FBS condition; and \(iii\) at depth00the oracle agrees with Alice\. An induction on depthk=d,d−1,…,0k=d,d\-1,\\dots,0shows that the run never triggers a losing condition, hence Alice wins with probability11\.

It is easy to check that this strategy takesO⁡\(d⋅\(TD\+q⋅T\)\)O\\big\(d\\cdot\(T\_\{D\}\+q\\cdot T\)\\big\)time andO⁡\(d⋅q⋅Q\)O\(d\\cdot q\\cdot Q\)queries to𝒪\\mathcal\{O\}\. ∎

We then show that whenever Alice answers the top\-level problem incorrectly, the protocol will catch her mistake with probabilityρ−d\\rho^\{\-d\}, whereddis the depth of the recursive decomposition andρ\\rhois the fractional block sensitivity\. This immediately implies that by running the protocolO⁡\(ρd​log⁡n\)O\(\\rho^\{d\}\\log n\)times, any incorrect answer by Alice will be caught with probability at least1−1/poly⁡\(n\)1\-1/\\poly\(n\)\. Viewed from the lens of practical AI debate, this represents a trade\-off between allowing highly sensitive arguments and the inference\-time computation required to verify them\.

###### Theorem 4\.2\.

SupposeA⁡\(x\)≠L⁡\(x\)A\(x\)\\neq L\(x\)\. Then, regardless of Alice’s strategy,

ℙ\[Alice loses\]≥ρ−d\.\\ProbOp\[\\textup\{Alice loses\}\]\\;\\geq\\;\\rho^\{\-d\}\.

###### Proof\.

Letx^k\\hat\{x\}^\{k\}be the problem at levelk∈\{d,d−1,…,0\}k\\in\\\{d,d\-1,\\ldots,0\\\}during the execution of the FBS debate withx^d:=x\\hat\{x\}^\{d\}:=x\. At levelkk, let

ak:=A⁡\(x^k\),gk:=L⁡\(x^k\),a\_\{k\}:=A\(\\hat\{x\}^\{k\}\),\\qquad g\_\{k\}:=L\(\\hat\{x\}^\{k\}\),and letEkE\_\{k\}be the event thatak≠gka\_\{k\}\\neq g\_\{k\}\. Fork∈\{d,…,0\}k\\in\\\{d,\\ldots,0\\\}, define the event

Wk:=\\displaystyle W\_\{k\}:=\{\}\{Alice loses before the recursion reaches level​k\}\\displaystyle\\\{\\text\{Alice loses before the recursion reaches level \}k\\\}∪\{the recursion reaches level​k​and​Ek​holds\}\.\\displaystyle\\cup\\\{\\text\{the recursion reaches level \}k\\text\{ and \}E\_\{k\}\\text\{ holds\}\\\}\.SinceA⁡\(x\)≠L⁡\(x\)A\(x\)\\neq L\(x\), we haveℙ\[Wd\]=1\\ProbOp\[W\_\{d\}\]=1\. We claim that for eachk≥1k\\geq 1, conditioned on any transcript through levelkkfor whichWkW\_\{k\}holds,

ℙ\[Wk−1∣transcript through level​k\]≥1ρ\.\\ProbOp\\\!\\big\[W\_\{k\-1\}\\mid\\text\{transcript through level \}k\\big\]\\ \\geq\\ \\frac\{1\}\{\\rho\}\.\(1\)If Alice has already lost, or if she fails the consistency or the stability check at levelkk, thenWk−1W\_\{k\-1\}holds trivially\. So assume the recursion reaches levelkkwithEkE\_\{k\}and both checks pass\. Letyyandzzbe the sub\-problems and answers proposed by Alice at levelkk, and let𝒈∈\{0,1\}q\\boldsymbol\{g\}\\in\\\{0,1\\\}^\{q\},𝒈i:=L⁡\(yi\)\\boldsymbol\{g\}\_\{i\}:=L\(y\_\{i\}\), be the correct answers toyy\. DefineB:=\{i∈\[q\]:zi≠𝒈i\}B:=\\\{i\\in\[q\]:z\_\{i\}\\neq\\boldsymbol\{g\}\_\{i\}\\\}\. ThenB≠∅B\\neq\\varnothing: otherwisez=𝒈z=\\boldsymbol\{g\}, and the consistency check would giveak=MD​\(x^k,y,z\)=gka\_\{k\}=M\_\{D\}\(\\hat\{x\}^\{k\},y,z\)=g\_\{k\}, contradictingEkE\_\{k\}\. Moreover,BBis sensitive forMD\(x^k,y,⋅\)M\_\{D\}\(\\hat\{x\}^\{k\},y,\\cdot\)atzz, becausezB=𝒈z^\{B\}=\\boldsymbol\{g\}and hence

MD​\(x^k,y,zB\)=MD​\(x^k,y,𝒈\)=gk≠ak=MD​\(x^k,y,z\)\.M\_\{D\}\(\\hat\{x\}^\{k\},y,z^\{B\}\)=M\_\{D\}\(\\hat\{x\}^\{k\},y,\\boldsymbol\{g\}\)=g\_\{k\}\\neq a\_\{k\}=M\_\{D\}\(\\hat\{x\}^\{k\},y,z\)\.Letttbe the optimal dual solution computed by Bob in the stability check\. By dual feasibility,∑i∈B′ti≥1\\sum\_\{i\\in B^\{\\prime\}\}t\_\{i\}\\geq 1for every sensitive blockB′B^\{\\prime\}, and since the check passed,∑iti=fbsz\(MD\(x^k,y,⋅\)\)≤ρ\\sum\_\{i\}t\_\{i\}=\\operatorname\{fbs\}\_\{z\}\\\!\\big\(M\_\{D\}\(\\hat\{x\}^\{k\},y,\\cdot\)\\big\)\\leq\\rho\. Thus the indexIIchosen by Bob satisfies

ℙ\[I∈B\]=∑i∈Bti∑jtj≥1∑jtj≥1ρ\.\\ProbOp\[I\\in B\]=\\sum\_\{i\\in B\}\\frac\{t\_\{i\}\}\{\\sum\_\{j\}t\_\{j\}\}\\ \\geq\\ \\frac\{1\}\{\\sum\_\{j\}t\_\{j\}\}\\ \\geq\\ \\frac\{1\}\{\\rho\}\.IfI∈BI\\in B, thenak−1=zI≠𝒈I=gk−1a\_\{k\-1\}=z\_\{I\}\\neq\\boldsymbol\{g\}\_\{I\}=g\_\{k\-1\}, i\.e\.,Ek−1E\_\{k\-1\}occurs andWk−1W\_\{k\-1\}holds\. This proves \([1](https://arxiv.org/html/2610.02557#S4.E1)\)\.

AsWkW\_\{k\}is determined by the transcript through levelkk, averaging \([1](https://arxiv.org/html/2610.02557#S4.E1)\) over all transcripts realizingWkW\_\{k\}givesℙ\[Wk−1\]≥ℙ\[Wk−1∩Wk\]≥ρ−1ℙ\[Wk\]\\ProbOp\[W\_\{k\-1\}\]\\geq\\ProbOp\[W\_\{k\-1\}\\cap W\_\{k\}\]\\geq\\rho^\{\-1\}\\ProbOp\[W\_\{k\}\], and hence

ℙ\[W0\]≥ρ−dℙ\[Wd\]=ρ−d\.\\ProbOp\[W\_\{0\}\]\\ \\geq\\ \\rho^\{\-d\}\\,\\ProbOp\[W\_\{d\}\]\\ =\\ \\rho^\{\-d\}\.Finally,W0W\_\{0\}implies that Alice loses: either she has already lost, or the recursion reaches level00and her claimed answer disagrees with𝒪\\mathcal\{O\}\. Henceℙ\[Alice loses\]≥ρ−d\\ProbOp\[\\textup\{Alice loses\}\]\\geq\\rho^\{\-d\}\. ∎

## 5Lower Bound

In this section, we prove an instance\-wise lower bound for debate protocols in the recursive decomposition framework\. The bound is governed by the fractional block sensitivity of the local aggregation functions\.

#### Setup\.

Fix a languageLL, a one\-step aggregatorMDM\_\{D\}, an inputxx, and a depth\-ddvisible tree𝒯\\mathcal\{T\}forxxwith respect toMDM\_\{D\}\. For every internal nodeuu, letyu=\(yu,1,…,yu,q\)y\_\{u\}=\(y\_\{u,1\},\\ldots,y\_\{u,q\}\)be its children and let

ϕu​\(z\)≔MD​\(x^u,yu,z\)\\phi\_\{u\}\(z\)\\coloneqq M\_\{D\}\(\\hat\{x\}\_\{u\},y\_\{u\},z\)be its local aggregator\. For any oracle𝒪\\mathcal\{O\}, define the value of a node by bottom\-up evaluation:

val𝒪​\(u\)≔\{𝒪⁡\(qu\)if​u​is a leaf,ϕu​\(val𝒪​\(u1\),…,val𝒪​\(uq\)\)if​u​is internal,\\mathrm\{val\}\_\{\\mathcal\{O\}\}\(u\)\\coloneqq\\begin\{cases\}\\mathcal\{O\}\(q\_\{u\}\)&\\text\{if \}u\\text\{ is a leaf\},\\\\ \\phi\_\{u\}\\bigl\(\\mathrm\{val\}\_\{\\mathcal\{O\}\}\(u\_\{1\}\),\\ldots,\\mathrm\{val\}\_\{\\mathcal\{O\}\}\(u\_\{q\}\)\\bigr\)&\\text\{if \}u\\text\{ is internal\},\\end\{cases\}whereu1,…,uqu\_\{1\},\\ldots,u\_\{q\}are the children ofuu\. For the lower bound, we treat𝒯\\mathcal\{T\}as a syntactic transcript whose truth value under𝒪\\mathcal\{O\}isval𝒪​\(root\)\\mathrm\{val\}\_\{\\mathcal\{O\}\}\(\\mathrm\{root\}\)\.

We assume that the leaf queriesqℓq\_\{\\ell\}are pairwise distinct\. This assumption is needed for a non\-trivial lower bound: for example, if allqqleaves of aqq\-ary AND root query the same string, then the decomposition tree𝒯\\mathcal\{T\}computes only a one\-bit identity function\.

#### Adaptive checker\.

To strengthen the lower bound, we assume that the second debater Bob is honest and assists the judge, while Alice may use an arbitrary strategy\. We model Bob and the judge together as a single*adaptive checker*\. Specifically, anmm\-query adaptive checker𝒱\\mathcal\{V\}for𝒯\\mathcal\{T\}is a randomized algorithm that receives the full visible tree𝒯\\mathcal\{T\}, makes at mostmmadaptive queries to𝒪\\mathcal\{O\}, may communicate arbitrarily with Alice, and finally outputs a bit intended to equalL⁡\(x\)L\(x\)\. Giving the checker an honest Bob and the full visible tree can only make its task easier, so a lower bound in this model also applies to the original debate protocol\.

Fix a reference oracle𝒪Y\\mathcal\{O\}\_\{Y\}\. For any alternative oracle𝒪N\\mathcal\{O\}\_\{N\}, let𝖠𝖼𝖼Y\\mathsf\{Acc\}\_\{Y\}and𝖠𝖼𝖼N\\mathsf\{Acc\}\_\{N\}denote the events that𝒱\\mathcal\{V\}accepts under𝒪Y\\mathcal\{O\}\_\{Y\}and𝒪N\\mathcal\{O\}\_\{N\}, respectively, with Alice using the same fixed strategy in both executions\. When the two oracles give different values at the root,\|ℙ\[𝖠𝖼𝖼Y\]−ℙ\[𝖠𝖼𝖼N\]\|\|\\ProbOp\[\\mathsf\{Acc\}\_\{Y\}\]\-\\ProbOp\[\\mathsf\{Acc\}\_\{N\}\]\|measures the checker’s oracle\-distinguishing advantage\. We show that if every local aggregator has fractional block sensitivity at leastρ\\rhoat the child values induced by𝒪Y\\mathcal\{O\}\_\{Y\}, then some alternative oracle changes the root value while giving anymm\-query checker distinguishing advantage at mostm​ρ−dm\\rho^\{\-d\}\.

###### Theorem 5\.1\.

Letρ≥1\\rho\\geq 1, and suppose every internal nodeuusatisfies

fbs𝒛u⁡\(ϕu\)≥ρ,\\operatorname\{fbs\}\_\{\\boldsymbol\{z\}^\{u\}\}\(\\phi\_\{u\}\)\\geq\\rho,where𝐳u∈\{0,1\}q\\boldsymbol\{z\}^\{u\}\\in\\\{0,1\\\}^\{q\}is the vector of child values induced by𝒪Y\\mathcal\{O\}\_\{Y\}\. Then for everymm\-query adaptive checker𝒱\\mathcal\{V\}for𝒯\\mathcal\{T\}, there is an oracle𝒪N\\mathcal\{O\}\_\{N\}such that

val𝒪N​\(root\)≠val𝒪Y​\(root\)\\mathrm\{val\}\_\{\\mathcal\{O\}\_\{N\}\}\(\\mathrm\{root\}\)\\neq\\mathrm\{val\}\_\{\\mathcal\{O\}\_\{Y\}\}\(\\mathrm\{root\}\)and

\|ℙ\[𝖠𝖼𝖼Y\]−ℙ\[𝖠𝖼𝖼N\]\|≤min⁡\{1,m​ρ−d\}\.\\left\|\\ProbOp\[\\mathsf\{Acc\}\_\{Y\}\]\-\\ProbOp\[\\mathsf\{Acc\}\_\{N\}\]\\right\|\\leq\\min\\\{1,m\\rho^\{\-d\}\\\}\.

The proof proceeds in two steps\. First, we bound the checker’s distinguishing advantage in terms of the fractional block sensitivity of the Boolean function computed by the entire tree\. We then show that this global sensitivity is at leastρd\\rho^\{d\}when every local sensitivity is at leastρ\\rho\. We begin by defining the global function and its sensitivity\.

#### Notation\.

For a leafℓ\\ell, letqℓq\_\{\\ell\}be its base\-case oracle query\. Let

Q⁡\(𝒯\)≔\{qℓ:ℓ​is a leaf of​𝒯\}Q\(\\mathcal\{T\}\)\\coloneqq\\\{q\_\{\\ell\}:\\ell\\text\{ is a leaf of \}\\mathcal\{T\}\\\}be the set of leaf\-query strings\. The decomposition tree𝒯\\mathcal\{T\}induces a Boolean function

F𝒯:\{0,1\}Q⁡\(𝒯\)→\{0,1\}F\_\{\\mathcal\{T\}\}:\\\{0,1\\\}^\{Q\(\\mathcal\{T\}\)\}\\to\\\{0,1\\\}by assigning each leafℓ\\ellthe variable indexed byqℓq\_\{\\ell\}and evaluating the tree bottom\-up\.

The reference oracle𝒪Y\\mathcal\{O\}\_\{Y\}induces an assignmentα∈\{0,1\}Q⁡\(𝒯\)\\alpha\\in\\\{0,1\\\}^\{Q\(\\mathcal\{T\}\)\}, defined byαqℓ≔𝒪Y​\(qℓ\)\\alpha\_\{q\_\{\\ell\}\}\\coloneqq\\mathcal\{O\}\_\{Y\}\(q\_\{\\ell\}\)for every leafℓ\\ell\. Let

ρ𝒯≔fbsα⁡\(F𝒯\),\\rho\_\{\\mathcal\{T\}\}\\coloneqq\\operatorname\{fbs\}\_\{\\alpha\}\(F\_\{\\mathcal\{T\}\}\),that is, the fractional block sensitivity of the whole decomposition tree𝒯\\mathcal\{T\}at the reference assignmentα\\alpha\.

We first prove an auxiliary lemma on fractional block sensitivity\.

###### Lemma 5\.2\(A light sensitive block\)\.

Letf:\{0,1\}I→\{0,1\}f:\\\{0,1\\\}^\{I\}\\to\\\{0,1\\\}be a Boolean function on a finite coordinate setII, letx∈\{0,1\}Ix\\in\\\{0,1\\\}^\{I\}, and letR=fbsx⁡\(f\)\>0R=\\operatorname\{fbs\}\_\{x\}\(f\)\>0\. For every distributionpponII, there is a sensitive blockH∈𝒮x​\(f\)H\\in\\mathcal\{S\}\_\{x\}\(f\)such that

∑i∈Hpi≤1R\.\\sum\_\{i\\in H\}p\_\{i\}\\leq\\frac\{1\}\{R\}\.

###### Proof\.

Let\{wH\}H∈𝒮x​\(f\)\\\{w\_\{H\}\\\}\_\{H\\in\\mathcal\{S\}\_\{x\}\(f\)\}be an optimal primal solution forfbsx⁡\(f\)\\operatorname\{fbs\}\_\{x\}\(f\)\. Thus∑HwH=R\\sum\_\{H\}w\_\{H\}=Rand∑H∋iwH≤1\\sum\_\{H\\ni i\}w\_\{H\}\\leq 1for everyi∈Ii\\in I\. Sample a sensitive block𝐇\\mathbf\{H\}with probability proportional towHw\_\{H\}\. Then

𝔼⁡\[∑i∈𝐇pi\]=∑i∈Ipi​∑H∋iwH∑HwH≤∑i∈Ipi​1R=1R\.\\mathbb\{E\}\\left\[\\sum\_\{i\\in\\mathbf\{H\}\}p\_\{i\}\\right\]=\\sum\_\{i\\in I\}p\_\{i\}\\frac\{\\sum\_\{H\\ni i\}w\_\{H\}\}\{\\sum\_\{H\}w\_\{H\}\}\\leq\\sum\_\{i\\in I\}p\_\{i\}\\frac\{1\}\{R\}=\\frac\{1\}\{R\}\.Therefore, some blockHHin the support satisfies∑i∈Hpi≤1/R\\sum\_\{i\\in H\}p\_\{i\}\\leq 1/R\. ∎

Recall that𝖠𝖼𝖼Y\\mathsf\{Acc\}\_\{Y\}and𝖠𝖼𝖼N\\mathsf\{Acc\}\_\{N\}denote the events that the adaptive checker𝒱\\mathcal\{V\}accepts under𝒪Y\\mathcal\{O\}\_\{Y\}and𝒪N\\mathcal\{O\}\_\{N\}, respectively\. We show thatρ𝒯\\rho\_\{\\mathcal\{T\}\}controls the maximal gap betweenℙ\[𝖠𝖼𝖼Y\]\\ProbOp\[\\mathsf\{Acc\}\_\{Y\}\]andℙ\[𝖠𝖼𝖼N\]\\ProbOp\[\\mathsf\{Acc\}\_\{N\}\]\.

###### Theorem 5\.3\(Collapsed\-function lower bound\)\.

Assumeρ𝒯\>0\\rho\_\{\\mathcal\{T\}\}\>0\. For everymm\-query adaptive checker𝒱\\mathcal\{V\}for𝒯\\mathcal\{T\}, there is an oracle𝒪N\\mathcal\{O\}\_\{N\}such that

val𝒪N​\(root\)≠val𝒪Y​\(root\)\\mathrm\{val\}\_\{\\mathcal\{O\}\_\{N\}\}\(\\mathrm\{root\}\)\\neq\\mathrm\{val\}\_\{\\mathcal\{O\}\_\{Y\}\}\(\\mathrm\{root\}\)and

\|ℙ\[𝖠𝖼𝖼Y\]−ℙ\[𝖠𝖼𝖼N\]\|≤min⁡\{1,mρ𝒯\}\.\\left\|\\ProbOp\[\\mathsf\{Acc\}\_\{Y\}\]\-\\ProbOp\[\\mathsf\{Acc\}\_\{N\}\]\\right\|\\leq\\min\\left\\\{1,\\frac\{m\}\{\\rho\_\{\\mathcal\{T\}\}\}\\right\\\}\.

###### Proof\.

For any leaf querys∈Q⁡\(𝒯\)s\\in Q\(\\mathcal\{T\}\), let

as=ℙ𝒪Y\[𝒱​queries​s\]\.a\_\{s\}=\\ProbOp\_\{\\mathcal\{O\}\_\{Y\}\}\[\\mathcal\{V\}\\text\{ queries \}s\]\.Then

Γ:=∑s∈Q⁡\(𝒯\)as=𝔼𝒪Y​\[\#⁡\{s∈Q⁡\(𝒯\):𝒱​queries​s\}\]≤m,\\Gamma:=\\sum\_\{s\\in Q\(\\mathcal\{T\}\)\}a\_\{s\}=\\mathbb\{E\}\_\{\\mathcal\{O\}\_\{Y\}\}\\bigl\[\\\#\\\{s\\in Q\(\\mathcal\{T\}\):\\mathcal\{V\}\\text\{ queries \}s\\\}\\bigr\]\\leq m,since the number of distinct leaf\-query strings queried is at most the total number of oracle queries\.

IfΓ\>0\\Gamma\>0, setps=as/Γp\_\{s\}=a\_\{s\}/\\Gamma; ifΓ=0\\Gamma=0, take any distributionpponQ⁡\(𝒯\)Q\(\\mathcal\{T\}\)\. By[Lemma5\.2](https://arxiv.org/html/2610.02557#S5.Thmtheorem2), there is a sensitive blockHHforF𝒯F\_\{\\mathcal\{T\}\}atα\\alphawithp⁡\(H\):=∑s∈Hps≤1/ρ𝒯p\(H\):=\\sum\_\{s\\in H\}p\_\{s\}\\leq 1/\\rho\_\{\\mathcal\{T\}\}\. Define𝒪N\\mathcal\{O\}\_\{N\}by flipping𝒪Y\\mathcal\{O\}\_\{Y\}onHHand leaving all other oracle strings unchanged\. SinceHHis sensitive, the root value flips\. Moreover,

∑s∈Has≤Γρ𝒯≤mρ𝒯,\\sum\_\{s\\in H\}a\_\{s\}\\leq\\frac\{\\Gamma\}\{\\rho\_\{\\mathcal\{T\}\}\}\\leq\\frac\{m\}\{\\rho\_\{\\mathcal\{T\}\}\},with the caseΓ=0\\Gamma=0being trivial\.

Couple the two executions with the same random tapes for𝒱\\mathcal\{V\}and Alice\. Since the oracles agree outsideHH, the two executions have identical transcripts until𝒱\\mathcal\{V\}first queries a string inHH\. Therefore the outputs can differ only if𝒱\\mathcal\{V\}queries some string inHHunder𝒪Y\\mathcal\{O\}\_\{Y\}\. By the union bound,

\|ℙ\[𝖠𝖼𝖼Y\]−ℙ\[𝖠𝖼𝖼N\]\|≤ℙ𝒪Y\[𝒱​queries​H\]≤∑s∈Has≤mρ𝒯\.\\left\|\\ProbOp\[\\mathsf\{Acc\}\_\{Y\}\]\-\\ProbOp\[\\mathsf\{Acc\}\_\{N\}\]\\right\|\\leq\\ProbOp\_\{\\mathcal\{O\}\_\{Y\}\}\[\\mathcal\{V\}\\text\{ queries \}H\]\\leq\\sum\_\{s\\in H\}a\_\{s\}\\leq\\frac\{m\}\{\\rho\_\{\\mathcal\{T\}\}\}\.The left\-hand side is also at most11\. ∎

We next lower boundρ𝒯\\rho\_\{\\mathcal\{T\}\}in terms of the local fractional block sensitivities at the internal nodes\.

###### Lemma 5\.4\.

Letρ≥1\\rho\\geq 1, and suppose every internal nodeuusatisfies

fbs𝒛u⁡\(ϕu\)≥ρ,\\operatorname\{fbs\}\_\{\\boldsymbol\{z\}^\{u\}\}\(\\phi\_\{u\}\)\\geq\\rho,where𝐳u∈\{0,1\}q\\boldsymbol\{z\}^\{u\}\\in\\\{0,1\\\}^\{q\}is the vector of child values induced by𝒪Y\\mathcal\{O\}\_\{Y\}\. Thenρ𝒯≥ρd\\rho\_\{\\mathcal\{T\}\}\\geq\\rho^\{d\}\.

###### Proof\.

By LP duality, it is enough to show that every distributionpponQ⁡\(𝒯\)Q\(\\mathcal\{T\}\)admits a sensitive block forF𝒯F\_\{\\mathcal\{T\}\}atα\\alphaofpp\-mass at mostρ−d\\rho^\{\-d\}\. We prove this by induction ondd\.

Ford=0d=0the claim is immediate\. Ford≥1d\\geq 1, letrrbe the root and let𝒯i\\mathcal\{T\}\_\{i\}be the subtree rooted at itsiith child\. Putpi=p⁡\(Q⁡\(𝒯i\)\)p\_\{i\}=p\(Q\(\\mathcal\{T\}\_\{i\}\)\)\. Because the leaf queries are pairwise distinct, the setsQ⁡\(𝒯i\)Q\(\\mathcal\{T\}\_\{i\}\)are disjoint, so\(p1,…,pq\)\(p\_\{1\},\\ldots,p\_\{q\}\)is a distribution on\[q\]\[q\]\. By[Lemma5\.2](https://arxiv.org/html/2610.02557#S5.Thmtheorem2)applied toϕr\\phi\_\{r\}at𝒛r\\boldsymbol\{z\}^\{r\}, there is a sensitive blockJ⊆\[q\]J\\subseteq\[q\]with∑i∈Jpi≤1/ρ\\sum\_\{i\\in J\}p\_\{i\}\\leq 1/\\rho\.

For eachi∈Ji\\in J, apply the induction hypothesis inside𝒯i\\mathcal\{T\}\_\{i\}to the conditional distributionp\(i\)p^\{\(i\)\}onQ⁡\(𝒯i\)Q\(\\mathcal\{T\}\_\{i\}\), choosing an arbitrary distribution ifpi=0p\_\{i\}=0\. This gives a sensitive blockHi⊆Q⁡\(𝒯i\)H\_\{i\}\\subseteq Q\(\\mathcal\{T\}\_\{i\}\)withp\(i\)​\(Hi\)≤ρ−\(d−1\)p^\{\(i\)\}\(H\_\{i\}\)\\leq\\rho^\{\-\(d\-1\)\}\. LetH=⋃i∈JHiH=\\bigcup\_\{i\\in J\}H\_\{i\}\. FlippingHHflips exactly the child values inJJ, andJJis sensitive forϕr\\phi\_\{r\}; henceHHis sensitive forF𝒯F\_\{\\mathcal\{T\}\}\. Finally,

p\(H\)=∑i∈J:pi\>0pip\(i\)\(Hi\)≤ρ−\(d−1\)∑i∈Jpi≤ρ−d\.p\(H\)=\\sum\_\{i\\in J:p\_\{i\}\>0\}p\_\{i\}\\,p^\{\(i\)\}\(H\_\{i\}\)\\leq\\rho^\{\-\(d\-1\)\}\\sum\_\{i\\in J\}p\_\{i\}\\leq\\rho^\{\-d\}\.∎

We can now complete the proof of[Theorem5\.1](https://arxiv.org/html/2610.02557#S5.Thmtheorem1)\.

###### Proof\.

By[Lemma5\.4](https://arxiv.org/html/2610.02557#S5.Thmtheorem4),ρ𝒯≥ρd≥1\\rho\_\{\\mathcal\{T\}\}\\geq\\rho^\{d\}\\geq 1\. The claim then follows from[Theorem5\.3](https://arxiv.org/html/2610.02557#S5.Thmtheorem3), since

min⁡\{1,mρ𝒯\}≤min⁡\{1,m​ρ−d\}\.\\min\\left\\\{1,\\frac\{m\}\{\\rho\_\{\\mathcal\{T\}\}\}\\right\\\}\\leq\\min\\\{1,m\\rho^\{\-d\}\\\}\.∎

Consequently, if a checker outputs the correct root value with probability at least1−ε1\-\\varepsilonunder each oracle, for someε<1/2\\varepsilon<1/2, then1−2​ε≤m​ρ−d1\-2\\varepsilon\\leq m\\rho^\{\-d\}and hencem≥\(1−2​ε\)​ρdm\\geq\(1\-2\\varepsilon\)\\rho^\{d\}\.

## 6Discussion and Open Problems

Our protocol and matching lower bound show that fractional block sensitivity precisely characterizes the set of problems that can be efficiently solved by debate within this recursive\-decomposition framework\. Notably, the protocol does not require Bob to determine whether or not Alice’s answers to subproblems are correct, but only to understand the structure of the argument well enough to sample subproblems to which the outcome is sufficiently sensitive\. This stands in contrast to the originalDebate=PSPACE\\text\{Debate\}=\\text\{PSPACE\}result of[Irving et al\. \(2018\)](https://arxiv.org/html/2610.02557#bib.bib16), which requires Bob to actually directly determine which of Alice’s subproblems are flawed\. Of course, this comes with the limitation that the identification of flawed subproblems might actually have much greater computational complexity than creating the subproblems\. This is not an issue if we assume that both Alice and Bob have the power to solve any problem in PSPACE, but is a serious obstacle if the debaters are assumed to be computationally bounded \(as they will be in practice\)\.

Given this discussion, the question remains: is it possible to design a protocol that goes beyond the fractional block sensitivity barrier we identify? One might hope that utilizing Bob’s ability to solve the same problems as Alice could help with this issue, perhaps by allowing Bob to take advantage of Alice’s computational limitations in some way\. Alternatively, our lower bounds only apply when human judgment is modeled as a black box, accessible only via queries\. Classical results in interactive proofs likeIP=PSPACE\\text\{IP\}=\\text\{PSPACE\}show that opening up the black box yields much stronger protocols\. It seems implausible that these methods can be adapted to the case of human judgment—one would need to essentially be able to “read the code” that implements the human judgment\. However, it is still possible that some other relaxation of the black\-box oracle assumption could lead to better debate protocols\.

## Acknowledgments

JL is supported by Scott Aaronson’s Coefficient Giving grant\. ZX is supported by the NSF AI Institute for Foundations of Machine Learning \(IFML\)\.

## References

- Aaronson \[2008\]Scott Aaronson\.Quantum certificate complexity\.*Journal of Computer and System Sciences*, 74\(3\):313–322, 2008\.
- Abouzaid et al\. \[2026\]Mohammed Abouzaid, Andrew J\. Blumberg, Martin Hairer, Joe Kileel, Tamara G\. Kolda, Paul D\. Nelson, Daniel Spielman, Nikhil Srivastava, Rachel Ward, Shmuel Weinberger, and Lauren Williams\.First proof, 2026\.URL[https://arxiv\.org/abs/2602\.05192](https://arxiv.org/abs/2602.05192)\.
- Amit et al\. \[2024\]Noga Amit, Shafi Goldwasser, Orr Paradise, and Guy Rothblum\.Models that prove their own correctness\.*arXiv preprint arXiv:2405\.15722*, 2024\.
- Anil et al\. \[2021\]Cem Anil, Guodong Zhang, Yuhuai Wu, and Roger Grosse\.Learning to give checkable answers with prover\-verifier games\.*arXiv preprint arXiv:2108\.12099*, 2021\.
- Anthropic \[2026\]Anthropic\.Claude opus 4\.6 system card\.System card, Anthropic, February 2026\.URL[https://www\.anthropic\.com/claude\-opus\-4\-6\-system\-card](https://www.anthropic.com/claude-opus-4-6-system-card)\.
- Barnes \[2020\]Beth Barnes\.Debate update: Obfuscated arguments problem, 2020\.URL[https://www\.alignmentforum\.org/posts/PJLABqQ962hZEqhdB/debate\-update\-obfuscated\-arguments\-problem](https://www.alignmentforum.org/posts/PJLABqQ962hZEqhdB/debate-update-obfuscated-arguments-problem)\.
- Brown\-Cohen et al\. \[2024\]Jonah Brown\-Cohen, Geoffrey Irving, and Georgios Piliouras\.Scalable AI safety via doubly\-efficient debate\.In*Forty\-first International Conference on Machine Learning*, 2024\.
- Brown\-Cohen et al\. \[2025\]Jonah Brown\-Cohen, Geoffrey Irving, and Georgios Piliouras\.Avoiding obfuscation with prover\-estimator debate, 2025\.URL[https://arxiv\.org/abs/2506\.13609](https://arxiv.org/abs/2506.13609)\.
- Canetti et al\. \[2013\]Ran Canetti, Ben Riva, and Guy N Rothblum\.Refereed delegation of computation\.*Information and Computation*, 226:16–36, 2013\.
- Chandra et al\. \[1981\]Ashok K\. Chandra, Dexter C\. Kozen, and Larry J\. Stockmeyer\.Alternation\.*J\. ACM*, 28\(1\):114–133, January 1981\.ISSN 0004\-5411\.doi:10\.1145/322234\.322243\.URL[https://doi\.org/10\.1145/322234\.322243](https://doi.org/10.1145/322234.322243)\.
- Chen et al\. \[2026\]Liyan Chen, Yael Tauman Kalai, and Zoe Xi\.How to avoid debate: Scalable ai safety via doubly\-efficient interactive proofs\.*arXiv preprint arXiv:2607\.03561*, 2026\.
- Chen et al\. \[2023\]Xinyi Chen, Angelica Chen, Dean Foster, and Elad Hazan\.Playing large games with oracles and AI debate\.*arXiv preprint arXiv:2312\.04792*, 2023\.
- Feige and Kilian \[1997\]Uriel Feige and Joe Kilian\.Making games short\.In*Proceedings of the twenty\-ninth annual ACM symposium on Theory of computing*, pages 506–516, 1997\.
- Gilmer et al\. \[2016\]Justin Gilmer, Michael Saks, and Srikanth Srinivasan\.Composition limits and separating examples for some boolean function complexity measures\.*Combinatorica*, 36\(3\):265–311, June 2016\.ISSN 0209\-9683\.doi:10\.1007/s00493\-014\-3189\-x\.URL[https://doi\.org/10\.1007/s00493\-014\-3189\-x](https://doi.org/10.1007/s00493-014-3189-x)\.
- Hammond and Adam\-Day \[2025\]Lewis Hammond and Sam Adam\-Day\.Neural interactive proofs\.In*The Thirteenth International Conference on Learning Representations*, 2025\.
- Irving et al\. \[2018\]Geoffrey Irving, Paul Christiano, and Dario Amodei\.AI safety via debate\.*arXiv preprint arXiv:1805\.00899*, 2018\.
- Kenton et al\. \[2024\]Zachary Kenton, Noah Yamamoto Siegel, Janos Kramar, Jonah Brown\-Cohen, Samuel Albanie, Jannis Bulian, Rishabh Agarwal, David Lindner, Yunhao Tang, Noah Goodman, and Rohin Shah\.On scalable oversight with weak LLMs judging strong LLMs\.In*The Thirty\-eighth Annual Conference on Neural Information Processing Systems*, 2024\.URL[https://openreview\.net/forum?id=O1fp9nVraj](https://openreview.net/forum?id=O1fp9nVraj)\.
- Khan et al\. \[2024\]Akbir Khan, John Hughes, Dan Valentine, Laura Ruis, Kshitij Sachan, Ansh Radhakrishnan, Edward Grefenstette, Samuel R Bowman, Tim Rocktäschel, and Ethan Perez\.Debating with more persuasive LLMs leads to more truthful answers\.In*Forty\-first International Conference on Machine Learning*, 2024\.
- Kirchner et al\. \[2024\]Jan Hendrik Kirchner, Yining Chen, Harri Edwards, Jan Leike, Nat McAleese, and Yuri Burda\.Prover\-verifier games improve legibility of LLM outputs\.*arXiv preprint arXiv:2407\.13692*, 2024\.
- Kulkarni and Tal \[2016\]Raghav Kulkarni and Avishay Tal\.On fractional block sensitivity\.*Chicago Journal of Theoretical Computer Science*, 2016\(8\):1–16, 2016\.doi:10\.4086/cjtcs\.2016\.008\.
- Leike et al\. \[2018\]Jan Leike, David Krueger, Tom Everitt, Miljan Martic, Vishal Maini, and Shane Legg\.Scalable agent alignment via reward modeling: a research direction\.*arXiv preprint arXiv:1811\.07871*, 2018\.
- MacDiarmid et al\. \[2025\]Monte MacDiarmid, Benjamin Wright, Jonathan Uesato, Joe Benton, Jon Kutasov, Sara Price, Naia Bouscal, Sam Bowman, Trenton Bricken, Alex Cloud, Carson Denison, Johannes Gasteiger, Ryan Greenblatt, Jan Leike, Jack Lindsey, Vlad Mikulik, Ethan Perez, Alex Rodrigues, Drake Thomas, Albert Webson, Daniel Ziegler, and Evan Hubinger\.Natural emergent misalignment from reward hacking in production rl, 2025\.URL[https://arxiv\.org/abs/2511\.18397](https://arxiv.org/abs/2511.18397)\.
- Michael et al\. \[2023\]Julian Michael, Salsabila Mahdi, David Rein, Jackson Petty, Julien Dirani, Vishakh Padmakumar, and Samuel R Bowman\.Debate helps supervise unreliable experts\.*arXiv preprint arXiv:2311\.08702*, 2023\.
- Patwardhan et al\. \[2025\]Tejal Patwardhan, Rachel Dias, Elizabeth Proehl, Grace Kim, Michele Wang, Olivia Watkins, Sim’on Posada Fishman, Marwan Aljubeh, Phoebe Thacker, Laurance Fauconnet, Natalie S\. Kim, Patrick Chao, Samuel Miserendino, Gildas Chabot, David Li, Michael Sharman, Alexandra Barr, Amelia Glaese, and Jerry Tworek\.Gdpval: Evaluating ai model performance on real\-world economically valuable tasks\.*ArXiv*, abs/2510\.04374, 2025\.
- Shao et al\. \[2025\]Zhihong Shao, Yuxiang Luo, Chengda Lu, Z\. Z\. Ren, Jiewen Hu, Tian Ye, Zhibin Gou, Shirong Ma, and Xiaokang Zhang\.Deepseekmath\-v2: Towards self\-verifiable mathematical reasoning, 2025\.URL[https://arxiv\.org/abs/2511\.22570](https://arxiv.org/abs/2511.22570)\.
- Wäldchen et al\. \[2022\]Stephan Wäldchen, Kartikey Sharma, Max Zimmer, and Sebastian Pokutta\.Merlin\-Arthur classifiers: Formal interpretability with interactive black boxes\.*arXiv preprint arXiv:2206\.00759*, 2022\.