Paper deep dive
Scalable AI Safety via Doubly-Efficient Debate
Jonah Brown-Cohen, Geoffrey Irving, Georgios Piliouras
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/12/2026, 7:55:44 PM
Summary
The paper introduces 'doubly-efficient debate', a complexity-theoretic framework for scalable AI safety. It addresses the limitation of previous debate methods by designing protocols where an honest prover can verify the alignment of stochastic AI systems using only a polynomial number of simulation steps and a constant number of human judgement queries, even against an exponentially powerful dishonest strategy.
Entities (5)
Relation Signals (3)
Doubly-efficient debate → formalizedin → Lean 4
confidence 98% · We also formalize the main theorem of Section 6 in the Lean 4 theorem prover
Doubly-efficient debate → improvesupon → Irving et al. [2018]
confidence 95% · While the promise of this approach is clear, the original framework was based on the assumption that the honest strategy is able to simulate deterministic AI systems for an exponential number of steps... In this paper, we show how to address these challenges
Doubly-efficient debate → enables → Scalable Oversight
confidence 90% · These theorems open up the door for training models with human feedback via self-play... as approaches to scalable oversight
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The emergence of pre-trained AI systems with powerful capabilities across a diverse and ever-increasing set of complex domains has raised a critical challenge for AI safety as tasks can become too complicated for humans to judge directly. Irving et al. [2018] proposed a debate method in this direction with the goal of pitting the power of such AI models against each other until the problem of identifying (mis)-alignment is broken down into a manageable subtask. While the promise of this approach is clear, the original framework was based on the assumption that the honest strategy is able to simulate deterministic AI systems for an exponential number of steps, limiting its applicability. In this paper, we show how to address these challenges by designing a new set of debate protocols where the honest strategy can always succeed using a simulation of a polynomial number of steps, whilst being able to verify the alignment of stochastic AI systems, even when the dishonest strategy is allowed to use exponentially many simulation steps.
Tags
Links
Trouble viewing inline? Open PDF directly →
Full Text
63,654 characters extracted from source content.
Expand or collapse full text
Scalable AI Safety via Doubly-Efficient Debate Jonah Brown-Cohen Google DeepMind jonahbc@google.com Geoffrey Irving Google DeepMind geoffreyi@google.com Georgios Piliouras Google DeepMind gpil@google.com November 27, 2023 Abstract The emergence of pre-trained AI systems with powerful capabilities across a diverse and ever-increasing set of complex domains has raised a critical challenge for AI safety as tasks can become too complicated for humans to judge directly. Irving et al. [2018] proposed a debate method in this direction with the goal of pitting the power of such AI models against each other until the problem of identifying (mis)-alignment is broken down into a manageable subtask. While the promise of this approach is clear, the original framework was based on the assumption that the honest strategy is able to simulatedeterministicAI systems for anexponentialnumber of steps, limiting its applicability. In this paper, we show how to address these challenges by designing a new set of debate protocols where the honest strategy can always succeed using a simulation of apolynomialnumber of steps, whilst being able to verify the alignment of stochasticAI systems, even when the dishonest strategy is allowed to use exponentially many simulation steps. 1 Introduction Large language models (LLMs) have demonstrated emergent capabilities, including the ability to follow natural-language instructions, use various tools, and perform some types of general-purpose abstract reasoning and planning [Saunders et al., 2022, Yao et al., 2023, Menick et al., 2022, Zhou et al., 2023]. Thus far, human feedback on LLM outputs has been used to improve the alignment between the behavior of these models and their designer’s intent [Ouyang et al., 2022]. However, these models are increasingly being used to perform complex tasks that can be viewed as the writing and execution of general-purpose computations described in natural language, where at each step the model is invoked with context given by some set of previous model outputs [Lu et al., 2023]. As the complexity of such tasks scales, the ability to provide direct human feedback for training on long complex traces involving reasoning, planning, and taking actions is limited. This limitation leads to the need for new approaches forscalable oversight[Leike et al., 2018, Christiano et al., 2018]–where carefully designed protocols involving the interaction of both humans and AI models are used to provide high-quality feedback for training and oversight of complex AI systems. As a motivating example, consider the case of using a language model to draft a law or a legal contract. Laws and contracts are written in natural language, refer to concepts in the real world, and require human judgement (in the worst case a judge in an actual court) to interpret their meaning. Furthermore, individual passages or even single characters in laws or contracts can have significant real-world consequences, as demonstrated by multimillion-dollar losses suffered by companies and governments due to misplaced commas [Kurtzleben, 2014, BBC, 2017]. In order to train a language model to write such high-stakes natural language, it is necessary to be certain that every passage of an extremely long document is correct, where correctness is defined by human judgement. However, requiring human experts to carefully read an entire law or contract produced by a language model to provide the training label for one example is clearly prohibitively expensive. Thus, in this setting it is necessary to design methods for training and oversight that are extremely efficient in their use of human judgements. A prominent approach to the oversight and safe training of AI systems builds upon the fact that there is a natural high-level correspondence between training techniques in machine learning and interactive proofs in 1 arXiv:2311.14125v1 [cs.AI] 23 Nov 2023 complexity theory, as exemplified by the proposal for AI safety via debate [Irving et al., 2018]. The overall goal of this approach is to enable the design of methods that allow the training of extremely computationally powerful learned models that nonetheless behave as desired, despite only being supervised by much more limited verifiers. For example, while no human Go player can instruct the AlphaZero model [Silver et al., 2017] on what move to make next, the model nonetheless was trained to a super-human level via self-play. This was possible precisely because it is computationally easy to verify which player has won at the end of a game of Go. Using such an approach for training LLMs to produce (and then successfully execute) computations described in natural-language requires some method of scalably verifying that the computations produced actually solve the intended task, and are executed correctly. The surprising ability of computationally limited verifiers to correctly judge the outputs of much more computationally powerful provers underlies some of the most celebrated results in computational complexity theory. Notably, any polynomial space (and potentially exponential time) computation can be verified by a polynomial time verifier interacting with a computationally unbounded prover i.e. IP=PSPACE [Shamir, 1992]. Further, for any problem with solutions which can be verified in polynomial time, one can efficiently encode the solutions in such a way that they can be non-trivially verified by reading only three bits chosen uniformly at random from the encoded solution i.e. the PCP theorem [Arora and Safra, 1998, Arora et al., 1998]. Recent work has introduced the notion of doubly-efficient interactive proofs [Goldwasser et al., 2015, Reingold et al., 2021] in the context of delegating computation. Here an untrusted prover is asked to run some polynomial-time computation, and the goal is for a linear-time verifier to interact with the prover in order to accurately judge that the computation was performed correctly. Thus, the time spent by the verifier is much less than the time to run the whole computation. Unfortunately, all of the methods from the theory of interactive proofs for the highly-efficient verification of computationally powerful provers apply only to tasks with mathematically precise definitions (e.g. find a solution to a problem, given the actual code of an algorithm for verifying that the solution is correct). However, in the case of training a model to follow human intent, the main source of feedback available is black-box access to human judgements of model outputs. Strikingly, when access to a black-box is allowed in computations, the main theorems regarding the power of interactive proofs (e.g. IP=PSPACE and the PCP theorem) are actually false [Chang et al., 1994, Fortnow, 1994]. However, the goal of efficient verification of powerful provers with access to black-box judgements can still be achieved by requiring that the provers compete. We introduce the theoretical model ofdoubly-efficient debate, where two polynomial-time provers compete with each other in order to convince a much more efficient verifier of the correctness of a computation that depends on access to black-box judgements. In this model we prove that, under appropriate assumptions, any polynomial-time computation can be verified using only a constant number of queries to the black-box representing human judgement (and in time linear in the size of a single query). Intuitively, our results show that, for any problem whose solutions can be verified by extremely extensive human reflection, the solutions can also be verified with a constant amount of human judgement and interaction with competing provers. A key requirement, and limitation, for applying our results in real-world settings, is that the debating models must have the ability to produce (potentially extensive) natural-language reasoning traces to solve the problem at hand, in such a way that (potentially extensive) careful human analysiscould have been used to judge that the reasoning was correct. These theorems open up the door for training models with human feedback via self-play, as even very complex and extensive computations described in natural language can be verified by querying human judgements for only a single step of such a computation. 1.1 Our Results Our definition of doubly-efficient debate is a complexity-theoretic formalization of a training setup in which two competing AI models attempt to convince a verifier, who has access to human judgements, of the correctness of a solution to a computational problem. At a high-level, the goal is to design protocols where (1) the model arguing for the correct solution convinces the verifier without expending computational effort much greater than would be necessary to correctly solve the problem by itself, and (2) the verifier makes a number of queries to human judgements that does not grow (i.e. is a fixed constant) with respect to the computational effort required to solve the problem. The details of the definition appear in Section 4. Recalling the example of models writing laws or contracts, the above goal would allow for training feedback 2 on an entire legal contract, by showing only a small, fixed (independently of the contract length) number of sentences to a human rater, allowing for scalable training of such models. In the subsequent sections we prove theorems achieving this high-level goal in several settings. As a warm- up, in Section 5 we give protocols achieving the goal when human judgements are modeled as deterministic, and the competing models are given explicit natural language instructions to follow. In order to better capture the fuzzy nature of human judgement, we then extend these results to the setting where human judgements are stochastic in Section 6. Finally, in Section 7 we prove theorems achieving our goal in the case where the models are asked to come up with a proposed solution themselves, and then are required to justify the correctness of the solution with a natural-language argument. We also formalize the main theorem of Section 6 in the Lean 4 theorem prover [Moura and Ullrich, 2021]; seehttps://github.com/google-deepmind/debate. 2 Related work The work most closely related to ours is the debate proposal by Irving et al. [2018], which proposed the setup of natural-language debates between AI models judged by humans. The original proposal showed that debates between two provers could naturally capture the complexity class PSPACE. Follow-up work of Barnes and Christiano [2020b] introduced cross-examination, which extends the power of debate to all of NEXP. This prior theoretical work models both provers in the debate as computationally unbounded, which leaves open the question of the ability of actual models to efficiently implement the protocols, and whether there may be an advantage for the dishonest prover in a computationally bounded setting. Our model of doubly-efficient debate makes progress on both of these questions, by giving debate protocols where the honest prover always has a winning strategy implementable in polynomial time, even when the dishonest prover is allowed unbounded computation. Earlier work of Feige and Kilian [1997] introduced a model of two competing unbounded provers attempting to convince a polynomial-time verifier, and used non-relativizing algebraic techniques in order to obtain protocols in this model for PSPACE with fewer rounds of interaction than achievable with standard interactive proofs. The model of doubly-efficient debate is inspired by doubly-efficient interactive proofs in computational complexity first introduced in Goldwasser et al. [2015]. The original purpose of this model was to capture the situation where a verifier wants to delegate a polynomial time computation to an untrusted prover, while spending much less time to verify that the computation was performed correctly. Later Reingold et al. [2021] gave the best results currently known for delegating space-bounded computation. See also Goldreich et al. [2018] for a survey of these results. Other related work connecting interactive proofs and machine learning includes Wäldchen et al. [2022], which uses the model of Merlin-Arthur (MA) proof systems in order to achieve formal interpretability of classifier outputs. The doubly-efficient debate protocols we design are strongly connected to the idea ofprocess-based feedback [Stuhlmüller and jungofthewon, 2022, Uesato et al., 2022], where the goal is to directly supervise the reasoning process of an AI system, rather than just the final outcome. Our protocols can be interpreted as a type of process-based feedback where two AI systems compete to convince a limited verifier that a given outcome has been arrived at by a (possibly complex) reasoning process that the verifier would endorse. On the safety side, there have been various proposals that directly supervise language models with human feedback [Ouyang et al., 2022], as well as with additional data from external sources [Menick et al., 2022]. There has also been work that utilizes language models to improve supervision of language models including Constitutional AI [Bai et al., 2022] and self-critique [Saunders et al., 2022]. There are also alternatives to debate as approaches to scalable oversight including recursive reward modelling [Leike et al., 2018] and iterated amplification [Christiano et al., 2018]. Another line of related work on LLMs that motivates the need for scalable oversight is the design of schemes for prompting language models to perform increasingly complex tasks. Notable examples include Chameleon [Lu et al., 2023], ReAct [Yao et al., 2023], and the direct use of language models as prompt engineers [Zhou et al., 2023]. 3 Preliminaries We will use the notation[n] =0,1,...,n. For a vectorx∈ 0,1 n and a subsetI⊆[n]we writex I to denote the restriction ofxto the set of coordinatesi∈I. We will model computations as Turing machines 3 Mwith inputx∈0,1 n , that additionally have access to an oracleO, which we refer to as oracle Turing machines. Formally, forl=l(n)anoracleis a functionO:0,1 l →0,1. Anoracle Turing machineMis a Turing machine with the additional ability to write a queryz∈0,1 l onto its tape, after which it will receive a responseO(z)in one step. We use the notationM O to indicate the oracle machineMwhere the querieszare answered by the oracleO. We will also consider the setting where the oracleOis stochastic, in which case the response to each oracle queryO(z)is an independent0,1-valued random variable. In the LLM setting, the machineMcorresponds to a set of natural language rules and instructions, and the oracle Orepresents human judgement along with any other external black-box feedback the model may receive (e.g. results from a search query, observations from a camera or sensor, outputs of API calls). AlanguageL⊆ 0,1 ∗ is a subset of finite-length strings. A deterministic oracle Turing machineM decides a languageLwith oracleOif it holds thatM O (x) = 1⇐⇒x∈L. A probabilistic oracle Turing machineMdecides a languageLwith oracleOif it holds thatx∈L=⇒P[M O (x) = 1]> 2 3 and x /∈L=⇒P[M O (x) = 1]< 1 3 . For LLMs, the languageLcorresponds to some class of problems describable in natural language, each with a yes or no answer that may depend on human judgement or other black-box feedback encoded by the oracleO. The stringsx∈Lare the problems where the answer is yes, andx /∈L the problems where the answer is no. As is usual this can be extended to search problems (where the answer is polynomial length) by classical search-to-decision reductions. Definition 3.1.A languageLis inNP O if there is a polynomial-time oracle machineMsuch that:x∈Lif and only if there exists a witnesswof length polynomial in|x|=nsuch thatM O (x,w) = 1. Definition 3.2.A languageLis inMA O if there is a probabilistic polynomial-time oracle machineMand a polynomialp(n)such that: •x∈L=⇒ ∃wof lengthp(n)s.t.P[M O (x,w) = 1]> 2 3 . •x /∈L=⇒ ∀wof lengthp(n),P[M O (x,w) = 1]< 1 3 . For the LLM setting, languages inNP O andMA O correspond to problemsxdescribable in natural language, where a correct solution (the witnessw) can be verified by polynomially many human judgements of a potentially polynomial length transcript arguing thatwis a solution tox. These sorts of problems are arguably the most important for safety and scalable oversight, as they correspond to the case where the LLM proposes a planwin natural language, and goes through a potentially quite long sequence of steps to argue that execution of the plan will have the desired outcome. The protocols establishing the power of debate in terms of standard complexity classes rely on producing verifiable transcripts of some prescribed computation. Atranscriptof a timeTcomputation of machineM on inputxis a stringy∈0,1 T , wherey t is the bit written at the current head position ofMin time stept. We will assume that theT-th coordinate of the transcript is equal to the output ofMonxi.e.y T =M(x). In the context of LLMs executing polynomial-length computations from natural-language instructions, the transcript is just the string of tokens output by the model. Given a transcripty, the subset of coordinates I M,x (t)⊆[T]ofyrelevantto coordinatet∈[T]are the coordinates of the transcript that are read byM when computingy t . When the machineMand inputxare obvious from context we will writeI(t)for the set of relevant coordinates. For standard Turing machines (without access to an oracle), the set of relevant coordinates has sizeO(1), but for oracle Turing machines may be as large asl. 4 Debate Adebate[Irving et al., 2018] is given by a triple(A,B,V)of oracle Turing machines, an oracleO, and a common inputxof lengthn. The machinesAandBare calledproversandVis called theverifier. A debate consists ofk=k(n)rounds, during which the provers exchange messages. In roundi∈[k]proverAsends a message a (i) =A O (x,a (1) ,b (1) ,...a (i−1) ,b (i−1) )and proverBsends a messageb (i) =B O (x,a (1) ,b (1) ,...a (i−1) ,b (i−1) ) which can be read by all parties involved. We leta= (a (1) ,...a (k) )andb= (b (1) ,...b (k) )denote the full transcript of the messages sent by each prover. At the end of thek-th round, the verifier runsV O (x,a,b) and outputs either zero or one. As defined, the two provers each send a message in one round, but this also captures the case of taking turns by having them alternate sending empty messages. 4 4.1 Doubly-efficient debate Different variants of debate arise depending on the computational power and/or limitations of the provers and the verifier. Definition 4.1.A(P time ,V time ,q)-debate protocolis given by a triple of oracle Turing machines(A,B,V) whereAandBrun in timeP time , andVruns in timeV time and makesqoracle queries. Let1≥c > 1 2 > s≥ 0. A debate protocol decides a languageLwith completenesscand soundnesssif: •Completeness:Ifx∈Lthen for all (unbounded time) oracle Turing machinesB ′ the debate(A,B ′ ,V), with oracleO, and inputxsatisfiesP[V O (x,a,b) = 1]≥c. •Soundness:Ifx /∈Lthen for all (unbounded time) oracle Turing machinesA ′ the debate(A ′ ,B,V), with oracleO, and inputxsatisfiesP[V O (x,a,b) = 1]≤s. Whenc= 1ands= 0we say that the debate protocoldeterministically decidesL. For deterministic oracle machines, as there is no randomness, it will always be the case thatc= 1and s= 0i.e. that the honest prover always wins. For stochastic oracle machines the definition requires a constant gap betweencands, which as usual can be amplified by repeating the protocol multiple times and taking the majority outcome. A debate protocol specifies the behavior of honest provers for both of the casesx∈L andx /∈L. Additionally, it is required that the honest prover wins the debate with higher probability while running in timeP time , against any (computationally unbounded) strategy by the dishonest prover. Note that this requirement gives a complexity theoretic formalization of the intuitively desirable property that debates should be structured so that it is easier to tell the truth than to lie. The original definition of debate requiresV time to be polynomial inn, but allowsP time to be unbounded. Doubly-efficient debaterefers to the setting whereP time is polynomial innandV time is linear inl, the length of each oracle query, and linear (or ideally sub-linear) inn, andVmakes a sub-linear (or ideally constant) numberqof oracle queries. 4.2 Training and inference with debate We first clarify the relationship between our formal theoretical model of debate, and practical training setups. The oracleO:Our theoretical model gives both the provers and the verifier access to an oracleO representing human judgement. The prover access to the oracle corresponds to the fact that the powerful pre-trained models already have extensive knowledge of human judgement on many questions, and will gain more knowledge throughout the training process. The verifier access to the oracleOcorresponds to actual judgements by human raters. At training time:The pretrained modelsAandBare trained via self-play to win the zero-sum game given by the debate protocol. When a model queriesOthis corresponds to using either pre-trained knowledge, or knowledge gained during self-play, to predict the answer that a human would give to the oracle query. When the veriferVqueriesOthis corresponds to asking an actual human rater to judge an oracle query. The distinction between pre-trained knowledge for provers, versus queries to human judgements for the verifier is critical, because it means that the training cost in terms of number of queries to human judgement is equal to the number of verifier queries toO. Thus, as long as the number of verifier oracle queries is bounded, the training procedure can scale to arbitrarily complex computations by the modelsAandB, while still only requiring a bounded number of human judgements. At inference time:When a model is asked to solve a problem or follow complex natural language instructions at inference time, the debate protocol is still run. However, no human feedback is used. Instead the output of the modelAis trusted, as long asBdoes not abort/point out a flaw. 5 Deterministic debate Doubly-efficient debate can decide any problem solvable in bounded space with verifier time that is nearly-linear in the space used, and only a constant number of verifier queries toO. 5 Theorem 5.1.LetLbe any language decidable by an oracle Turing machineMin timeT=T(n)using spaceS=S(n). Then there is a(O(TlogT),O(SlogT),O(1))-debate protocol deterministically decidingL. The proof appears in Section B. One can compare Theorem 5.1 to the setting of doubly-efficient interactive proofs where there is a single prover (and no black-box oracles). Reingold et al. [2021] show that any time TspaceScomputation can be decided by a doubly-efficient interactive proof in timeO(S 2 polylogT). It is currently an open question whether this can be improved toO(SpolylogT)[Goldreich et al., 2018]. Additionally, the protocol of Reingold et al. [2021] is quite complex, and relies on prior work in interactive proofs including the PCP theorem, so does not apply in the presence of a black-box oracle. The protocol achieving Theorem 5.1 is given in Figure 3 in Section A. The basic idea (which has been used in many classical PSPACE-completeness results), is to haveAoutput a supposed middle configuration of the computation ofM(x). ThenBdecides to recursively call the protocol on either the first or the second half of the computation. This recursion bottoms-out at a single transition of the machineMwhich can be checked byV. 5.1 Cross-examination The power of debate can be increased by allowing for cross-examination, where multiple copies of each debater are questioned independently. Intuitively this should give more power, as the independent copies must give consistent answers to the queries asked, and so may have more difficulty lying. Definition 5.2.A debate withcross-examinationis a debate whereA,B,andVcan query independent, non-communicating copies of bothAandB. Furthermore, the verifier is not required to read the entire transcript of the debate, but can selectively query a subset of the transcript. A debate protocol with cross-examination is a debate protocol where the debates appearing in the completeness and soundness case allow cross-examination. The definition of cross-examination is quite natural when considering language-model debaters. In this case, the ability to query independent copies can be achieved by either running multiple copies of the same LLM, or more efficiently by simply querying the same LLM with any previous messages in the debate removed from the context. Our next theorem shows that doubly-efficient debate with cross-examination can decide any problem solvable in polynomial time, using onlyO(llogT)verifier time, and onlyO(1)oracle queries. Theorem 5.3.LetLbe any language decidable by an oracle Turing machineMin timeT=T(n)with oracle queries of lengthl. Then there is a(O(TlogT),O(llogT),O(1))-debate protocol with cross-examination deterministically decidingL. The proof appears in Section B. The protocol achieving Theorem 5.3 is given in Figure 4 in Section A. Cross-examination allows for a simple and powerful protocol whereAoutputs the whole transcript of the computationM(x),Boutputs the location of a supposed mistake byA, andVchecks only this location. 6 Stochastic debate In this section we give a debate protocol for any languageLdecidable by a probabilistic oracle machineM with access to a stochastic oracleO. In the LLM setting, the oracleOis intended to model human judgement, as well as other types of responses from nature (e.g. real world data or observations). Thus, the oracleO must be stochastic in order for the model to be relevant in most real-world scenarios. However, access to a stochastic oracle introduces an additional subtlety, where changes on the order ofO( 1 T )in the oracle’s distribution may add up to anO(1)difference in the final output probability over the course of a timeT computation. To account for this issue, we require an additional Lipschitzness assumption for the machineM. Definition 6.1.ForK >0, a probabilistic oracle machineMisK-Lipschitz at oracleOif, for any other oracleO ′ , sup x P[M O (x) = 1]−P[M O ′ (x) = 1] < Ksup z |P[O(z) = 1]−P[O ′ (z) = 1]| 6 Debate protocol for a stochastic oracle All parties have access to anO, inputx∈0,1 n , andK-Lipschitz probabilistic oracle machineM. Aclaims thatP[M(x) = 1]≥ 2 3 , andBdisputes this claim. 1. Letybe the random variable representing the transcript ofMon inputx, and letd=⌈150K⌉. 2. The debate proceeds in a series ofTrounds, in lexicographic order fort∈[T]. In roundt: (a)Aoutputs a probabilityˆp t ∈[0,1], which is supposed to equalp t =P[y t = 1|y I(t) =a I(t) ]. (b)Aqueries an independent copy ofBfor a real numberz A t ∈[0,1], andBqueries an independent copy ofA for a real numberz B t ∈[0,1]. Bothz A t andz B t are supposed to be sampled uniformly at random from[0,1]. (c) Letz t =z A t +z B t mod 1. (d)Asetsa t = 1ifz t ≤ˆp t , anda t = 0otherwise. (e) At this pointBcan abort the protocol in roundt, and is supposed to do so ifAhas not followed the protocol. 3. If the protocol was aborted at roundt: (a)The verifierVdrawsr= 192d 2 log100samples ofy t conditioned ony I(t) =a I(t) to obtain an estimateˆp O t of the probabilityP[y t = 1|y I(t) =a I(t) ]via the sample mean. Note that ify t is supposed to be the output of an oracle query this can be done withrqueries toO(a I(t) ), otherwisey t is a deterministic function of a I(t) given by one step ofM. (b)Vchecks if ˆp O t −ˆp t ≥ 1 4d and outputs0if so and1otherwise. 4. If the protocol was not aborted, thenVoutputsa T . Figure 1: Doubly-efficient debate protocol for a stochastic oracle. In other words, ifMis run with any oracle which assigns similar probabilities toO, the probability thatMoutputs 1 should change by at most aKfactor more than the maximum difference in the oracle probabilities. Observe that every time-Tstochastic oracle machine isK-Lipschitz forK=O(T). Theorem 6.2.ForK >0, letLbe any language decidable by aK-Lipschitz probabilistic oracle Turing machine Min timeT=T(n)with oracle queries of lengthl. Then there is a(O(K 2 TlogT),O(K 2 +llogT),O(K 2 ))- debate protocol with cross-examination decidingLwith completeness 3 5 and soundness 2 5 . The proof appears in Section D. The debate protocol promised in Theorem 6.2 is given in Figure 1. As usual the protocol describes the prescribed behavior of the honest provers, but emphasizes that dishonest behavior may occur. The protocol proceeds inTrounds, where in each roundAproposes a probability distribution over the next bit given the computation so far. ThenAandBuse cross-examination to engage in a coin-flipping protocol (Steps 2.b. and 2.c.) in order to sample the next bit of the computation from the distribution proposed byA. Finally,Bcan abort the protocol at any roundt, whereuponVsamples fromO in order to check ifA’s proposed distribution at roundtis correct. Theorem 6.2 delivers non-trivial savings in verifier time and query complexity wheneverK=o( √ T). In particular, the most interesting case occurs forK=O(1)i.e. whenKis a constant independent ofT. An Example for Theorem 6.2.Suppose a researcher wants to perform a meta-analysis of the existing literature on whether caffeine improves learning in college students. The researcher could give a high-level plan in natural language for how to accomplish this task: 1. Search the literature for studies on caffeine consumption and learning in college students. 2. Among the studies found, select those studies which meet the following quality criteria: (a) Do not include any studies that contain clear methodological flaws. (b)Only include randomized control trials which measure final exam performance after at least six weeks of intervention. 7 3. Perform the actual statistical analysis using a random effects model. 4. Measure sources of heterogeneity between the included studies using meta-regression. The above natural language plan is the machineMin Theorem 6.2. Instructions such as 2.(a) correspond to queries to the human judgement oracleO, as whether a study contains a clear flaw is a question of judgement. To run the debate protocol the modelAis prompted to carry out the plan.Awill then carry out the instructions above while carefully listing everything relevant to show that the instructions are being followed correctly e.g. text from each study to explain why it is included. At the same timeBwill examine each step made byAand possibly abort ifBbelieves the step has been made incorrectly. To see how the protocol in Figure 4 works in this case suppose thatBaborts whenAdecides not to include a particular study at Step 2.(a). The protocol requiresAto output a probability estimate for how likely a human is to say that the study contains a clear methodological flaw. Assume thatAhas output probability 3 4 that the study contains a flaw. Then whenBaborts, the question of whether the study has the flaw claimed byAwill be sent to human raters. If the fraction of raters who agree withAabout the flaw is sufficiently close to 3 4 thenAwins. OtherwiseBwins. Lean 4 formalization.https://github.com/google-deepmind/debateformalizes Theorem 6.2 using Lean 4 and Mathlib [Moura and Ullrich, 2021, Mathlib Community, 2020]. (The purpose of the formalization was primarily to learn Lean 4.) Our algorithm differs from Figure 1 in a few details; e.g., we use external randomness rather thanz A t +z B t , and the constants are different (if unsure, trust the formalized constants). We formalize the debate protocol using two monads:Prob afor finitely supported probability distributions over a typea, andComp s afor stochastic computations that can make queries to any oracle in a sets(we use multiple oracles to track query complexity separately for the different participants). Monadic syntax is excellent for expressing stochastic algorithms, and working over finitely supported distributions avoids the need for integrability side conditions during proofs. 7 Doubly-efficient debate with a witness One should also consider the situation where the debaters additionally are able to non-deterministically produce a polynomial-sized witnesswfor the membership ofxin anNP O orMA O languageL. In this case the honest debaters are required to run in polynomial time as in Definition 4.1 when additionally given the witnesswas input. This case corresponds to the setting where an LLM proposes some solution to a very complex problem, and then argues for the correctness of the solution via a polynomially long natural-language argument. Our results in this section prove that, as long as this argument can be verified via extensive human reflection, then there is a debate protocol that allows a human judge to only check a constant number of steps of the argument when interacting with two competing models. The protocols of Figure 4 and Figure 1 then carry over immediately where the machineMis the polynomial-time verifier forLand bothxand the witnessware given as input. Debate protocol with a witness for timeT All parties have access to an oracleO, inputx∈0,1 n and the code of a timeToracle machineMfor verifying witnesses for a languageL. Aclaims thatxis inL, andBdisputes this claim. 1.Aoutputs a claimed witnesswfor the membership ofxinL. 2. If the oracleOis deterministic, run the protocol of Figure 4 with input(x, w)and machineM. 3. If the oracleOis stochastic, run the protocol of Figure 1 with input(x, w)and machineM. Figure 2: Doubly-efficient debate protocol with a witness. The protocol given in Figure 2 leads immediately to the following theorems. 8 Theorem 7.1.LetL∈NP O and letMbe the timeT=T(n)verifier forLwith oracle queries of lengthl. Then there is a(O(T),O(llogT),O(1))-debate protocol with cross-examination deterministically decidingL given a witnessw. Theorem 7.2.ForK >0, letL∈MA O be a language with a verifierMthat is aK-Lipschitz, time T=T(n)probabilistic oracle machine, with oracle queries of lengthl. Then there is a(O(K 2 TlogT),O(K 2 + llogT),O(K 2 ))-debate protocol with cross-examination decidingLwith completeness 3 5 and soundness 2 5 , given a witnessw. The proofs of Theorem 7.1 and Theorem 7.2 appear in Section E. An Example for Theorem 7.2.The simplest example for Debate with a witness is to take the setting of the example given for Theorem 6.2 above, but drop the assumption that the high-level natural language plan is given in advance. Instead one could assume that the researcher just asks the question “Does caffeine improve learning in college students? Produce a high-level plan to answer this question, give a step-by-step justification of the correctness of the plan, and then execute the plan.” Here the high-level plan plus the justification for its correctness is the witnesswproduced byAin Theorem 7.2. The machineMis given by the natural-language instructions (implicit in the prompt above): 1.Go through every step of the plan and the corresponding justification and check that it is clearly correct. 2. Execute the plan. Clearly many calls to the human-judgement oracleOare necessary to executeMwith witnessw. The protocol at this point will proceed as in the example above, withAgoing step-by-step throughM, andB aborting for a claimed incorrect step. 8 Conclusion and Open Problems We introduced the theoretical model of doubly-efficient debate, where two polynomial-time provers compete to convince a significantly more efficient verifier that they have correctly solved a computational problem that depends on black-box access to human judgements. At a high level, our main theorems show that doubly-efficient debate can be used to allow for the verification of arbitrary polynomial time computations using only a constant amount of human judgement. The overall aim of this model is to provide theoretical grounding for scalable oversight of powerful AI systems, using limited human feedback, and our theorems represent an initial step towards this goal. However, many open questions remain. The Power of the Provers:The theorems in this paper apply to the setting of verifying computations thatcould have beenverified by a human reading the entire (polynomial-length) transcript of the computation. How can the theoretical model be extended to settings where this is not possible? On the one hand, our model assumes the AI systems implementing the provers are powerful enough to very accurately simulate human judgements on any query. This may attribute too much power to these systems. Is it possible to relax the accuracy requirements for the provers e.g. by giving the provers access to an approximately correct oracle O ′ ? On the other hand, extremely powerful AI systems may be able to perform computations that, while polynomial time, do not have any polynomial length human-verifiable transcript. The original debate proposal with unbounded provers captures all of PSPACE, and thus is able to efficiently interrogate implicitly- represented exponential length transcripts. However, allowing both provers in the theoretical model to be unbounded runs into what is referred to by Barnes and Christiano [2020a] as theobfuscated argument problem, where a dishonest prover can in polynomial time produce an argument that would require the honest prover exponential time to refute. Is there some intermediate model where the honest prover always has an efficient strategy, but the computation to be verified does not require a polynomial-length human-verifiable transcript? 9 The Power of the Verifier:Human judgement is fallible in many ways. Furthermore, current approaches to scalable oversight, such as reinforcement learning from human feedback, generally train AI models (known as reward models) to approximate human judgements from a limited number of samples. Thus, in the practical settings of interest the oracleOused by the verifier is likely to be flawed. Theorem 6.2 partially addresses this problem by making each response ofOstochastic, and allowing for the verification of any computation that outputs the correct answer with a constant advantage over random guessing. Is it possible to extend these results to settings whereOgives incorrect answers on some subset of queries? There are many possible models in this direction e.g. is there a class of computations that can be verified by debate, where the oracle may make errors on an arbitrary subset of limited size? Alternately, can debate verify computations where the oracle makes arbitrary errors on a randomly selected subset of queries? Acknowledgements We would like to thank Eric Wieser for his careful review and many helpful suggestions on the Lean 4 formalization of Theorem 6.2. References Comma comeuppance: When rogue punctuation proves costly.BBC News, 2017. URLhttps://w.bbc. co.uk/news/business-39300432. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np.Journal of the ACM (JACM), 45(1):70–122, 1998. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems.Journal of the ACM (JACM), 45(3):501–555, 1998. Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback.arXiv preprint arXiv:2212.08073, 2022. Beth Barnes and Paul Christiano. Debate update: Obfuscated arguments problem, 2020a. URLhttps://w. alignmentforum.org/posts/PJLABqQ962hZEqhdB/debate-update-obfuscated-arguments-problem. Beth Barnes and Paul Christiano. Write-up: Progress on ai safety via debate, 2020b. URLhttps://w. alignmentforum.org/posts/Br4xDbYu4Frwrb64a/writeup-progress-on-ai-safety-via-debate-1. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false.J. Comput. Syst. Sci., 49:24–39, 1994. Paul Christiano, Buck Shlegeris, and Dario Amodei. Supervising strong learners by amplifying weak experts. arXiv preprint arXiv:1810.08575, 2018. Uriel Feige and Joe Kilian. Making games short. InProceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 506–516, 1997. Lance Fortnow. The role of relativization in complexity theory.Bulletin of the EATCS, 52:229–243, 1994. Oded Goldreich et al. On doubly-efficient interactive proof systems.Foundations and Trends®in Theoretical Computer Science, 13(3):158–246, 2018. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles.J. ACM, 62(4):27:1–27:64, 2015. doi: 10.1145/2699436. URLhttps://doi.org/10.1145/ 2699436. Geoffrey Irving, Paul Christiano, and Dario Amodei. AI safety via debate, 2018. 10 Danielle Kurtzleben.How a misplaced comma cost the us government $38.4 million.Vox, 2014.URLhttps://w.vox.com/xpress/2014/10/14/6971613/ how-a-misplaced-comma-cost-the-us-government-38-4-million. 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. Pan Lu, Baolin Peng, Hao Cheng, Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, and Jianfeng Gao. Chameleon: Plug-and-play compositional reasoning with large language models.arXiv preprint arXiv:2304.09842, 2023. The Mathlib Community. The Lean Mathematical Library. InProceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, page 367–381, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370974. doi: 10.1145/3372885.3373824. URL https://doi.org/10.1145/3372885.3373824. Jacob Menick, Maja Trebacz, Vladimir Mikulik, John Aslanides, Francis Song, Martin Chadwick, Mia Glaese, Susannah Young, Lucy Campbell-Gillingham, Geoffrey Irving, et al. Teaching language models to support answers with verified quotes.arXiv preprint arXiv:2203.11147, 2022. Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction–CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021, Proceedings 28, pages 625–635. Springer, 2021. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors,Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=TG8KACxEON. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation.SIAM J. Comput., 50(3), 2021. doi: 10.1137/16M1096773. URLhttps://doi.org/10. 1137/16M1096773. William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. Self-critiquing models for assisting human evaluators.arXiv preprint arXiv:2206.05802, 2022. Adi Shamir. Ip = pspace.J. ACM, 39(4):869–877, oct 1992. ISSN 0004-5411. doi: 10.1145/146585.146609. URLhttps://doi.org/10.1145/146585.146609. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge.nature, 550(7676):354–359, 2017. Andreas Stuhlmüller and jungofthewon. Supervise process, not outcomes, 2022. URLhttps://w. alignmentforum.org/posts/pYcFPMBtQveAjcSfH/supervise-process-not-outcomes. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14275, 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. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Syn- ergizing reasoning and acting in language models. InInternational Conference on Learning Representations (ICLR), 2023. 11 Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=92gvk82DE-. 12 A Deterministic Debate Protocols In this section we include the full specifications of the protocols for deterministic debate. Debate protocol for timeTand spaceS All parties have access to an oracleO, inputx∈0,1 n , and the code of the timeTspaceSoracle machineM. Aclaims thatM(x) = 1, andBdisputes this claim. 1.The debate proceeds recursively in a series ofO(logT)rounds. Letz 0 =xandt 0 =T. Thek-th round begins withAarguing that the execution ofMstarting in configurationz k ends in configurationz ′ k int k steps. (a)Aoutputs the configurationa k , which is supposed to be equal to the middle configuration ofMafter t k 2 steps starting fromz k . (b)Boutputs a bitb k , which is supposed to be 1 ifAis lying about the execution ofMfromz k toa k , and zero ifAis lying about the execution froma k toz ′ k . (c) Ifb k = 1thenAenters the next round withz k+1 =a k andz ′ k+1 =z ′ k . Ifb k = 0thenAenters the next round withz k+1 =z k andz ′ k+1 =a k . In either caset k+1 = t k 2 . 2. The verifierVchecks that each configurationa k output byAis a valid configuration ofM, and that the final two configurations output byAare a valid execution of one step ofM. Figure 3: Doubly-efficient debate protocol for timeTand spaceS. Debate protocol with cross-examination for timeT All parties have access to an oracleO, inputx∈0,1 n and the code of the timeToracle machineM. Aclaims thatM(x) = 1, andBdisputes this claim. 1.Aoutputs a stringa, which is supposed to be the transcriptyofMon inputx 2.Boutputs a locationt∈[T]as well as the relevant coordinatesI(t), whereAhas supposedly computeda t incorrectly. 3.The verifierVreads the relevant bitsa I(t) and checks thata t is correct for the execution ofMgiven these bits. If soVoutputs1, if not0. Figure 4: Doubly-efficient debate protocol with cross-examination for timeT. 13 A a 1 a 2 a T B a t V M x Figure 5: A schematic of the debate protocol with cross examination. The proverAsimulates the execution of the machineMon inputx. The proverBpoints to a location of an incorrect stepa t , andVchecks that step. B Missing Proofs for Deterministic Debate In this section we give the missing proofs for the theorems on the power of deterministic debate protocols, both with and without cross-examination. Proof of Theorem 5.1. CompletenessIfx∈Lthen an honest proverAcan runM(x)once to get the transcriptyand always output the appropriate middle configuration in Step 1a, no matter which bitsb k are chosen. The messagesa k will then pass all checks in Step 2. SoundnessSupposex /∈L. Then inductively in thek-th round a dishonest proverA ′ must output a middle configurationa k for which either the first half (z k toa k ) or the second half (a k toz ′ k ) is not a correct execution ofM. Then an honest proverBcan runMfor t k 2 steps fromz k and froma k , and output the appropriate bitb k indicating which half was incorrect. Thus, in Step 3 either the last two configurations are not a correct step ofMor one of the configurations output byMis invalid, soVwill reject. EfficiencyThe honest proverAonly needs to runM(x)once. The honest proverBalso only needs to run MforO(T)total steps. The current head position ofMcan be encoded inO(logT)bits, so simulating one step ofMrequires at mostO(log(T))time. The verifierVchecksO(logT)configurations each of sizeS, and simulates one step ofM(possibly issuing one query toO), for a total time ofO(SlogT). Proof of Theorem 5.3. CompletenessIfx∈Lthe honest proverAcan just output the true transcript ofMon inputx, and will pass the test in Step 3 no matter which locationtis checked byV. SoundnessIfx /∈Lthen a dishonest proverA ′ must output a transcriptAthat does not correspond to a correct execution ofM(x). In particular, there must be at least one locationtwherea t is not correct given the relevant bitsa I(t) . An honest proverBcan then executeM(x)and find such a location, which will in turn causeVto reject in Step 3. 14 EfficiencyThe current head position ofMcan be encoded inO(logT)bits, so simulating one step of Mrequires at mostO(log(T))time. Both provers need only simulateM(x)once which takesO(TlogT) time. The verifier only needs to read the at mostO(l)relevant bitsa I(t) , the locations of which can each be encoded inO(logT)bits, and execute one step ofM(possibly making one query toO), which takes a total ofO(llogT)time. C The debate game The verifierVin a debate protocol deciding a languageLnaturally defines a family of (potentially stochastic) two-player zero-sum gamesG(V,x), one for each inputx. The gameG(V,x)is defined as follows: • The strategies available to the first player are all oracle Turing machinesA, and to the second player all oracle Turing machinesB. •The expected payoff to the first player isP[V(x,a,b) = 1]. •The expected payoff for the second player is1−P[V(x,a,b) = 1]. The existence of a(P time ,V time )-debate-protocol deciding a languageLthen has an equivalent statement in game-theoretic language. In particular ifx∈Lthen there is a strategyAfor the first player inG(x,V) achieving value at leastc, regardless of the second player’s strategy. Furthermore, the strategyAis a time P time oracle Turing machine. Similarly, ifx /∈Lthen there is a strategyBfor the second player inG(x,V) achieving value at least1−s, whereBis a time-P time oracle Turing machine. This equivalent game-theoretic statement gives a justification for the safety of training a model to decide a languageLvia self-play in the gamesG x . In particular, the existence of a(P time ,V time )-debate protocol means that the prover tasked with arguing for the correct answer always receives a larger expected pay-off, even when restricted to strategies computable in timeP time . D Missing Proofs for Stochastic Debate In this section we give the missing proof for Theorem 6.2 on the power of stochastic debate protocols. For a pair of oraclesO,O ′ we will use the notation∥O−O ′ ∥ ∞ = max z P[O(z) = 1]−P[O ′ (z) = 1] Proof of Theorem 6.2.We will require the following version of the Chernoff bound throughout the proof: LetX 1 ,...,X N be independent Bernoulli random variables, each taking the value 1 with probabilitypand0 with probability(1−p). Letˆμ= 1 N P N i=1 X i be the empirical mean of the random variables. Then, P[|ˆμ−p|≥s]<2e − s 2 N 3 . SinceMisK-Lipschitz atO, for any oracleO ′ satisfying∥O−O ′ ∥< 1 d P h M O ′ (x) = 1 i −P M O (x) = 1 < K d ≤ 1 150 .(1) CompletenessIfx∈L, we first describe how the proverAcan efficiently follow the prescribed protocol. In each roundtthe proverAdrawsR= 192d 2 log100Tsamples fromy t conditioned ony I(t) =a I(t) (this may involve queryingO(a I(t) )up toRtimes). NextAoutputs the sample meanˆp t of theseRsamples as the probability in step 2.a. Finally, whenAis queried for a random integer in step 2.b,Aoutputs a number z A t ∈[0,1]sampled uniformly at random. Next we analyze the probability that the verifierVaccepts whenAfollows the protocol as described above, andB ′ is an arbitrary strategy. Letp t =P[y t = 1|y I(t) =a I(t) ]be the true probability thaty t = 1 conditioned on the execution so far. LetE t be the event that|ˆp t −p t |< 1 8d . LetH t be the history of all messages sent in the protocol up until the end of roundt. Leta(H t )denote the bitsa 1 ...a t output in the historyH t . We will call a historyH t “good” ifE t ′ occurs andB ′ does not abort in roundt ′ for allt ′ ≤tin the history. LetK t be the event thatB ′ aborts in roundt. 15 For the analysis it will be useful to define an alternative oracle machineM ′ . The machineM ′ is exactly the same asMexcept that in the final stepT, ifMoutputs 1, then with probability 1 50 M ′ outputs 0, otherwiseM ′ outputs the same value thatMoutputs. This implies that, given any initial setting of the transcripty ≤t =a ≤t and any oracleO ′ , P h M ′O ′ →1|y ≤t =a ≤t i = 49 50 P h M O ′ →1|y ≤t =a ≤t i ≤ 49 50 .(2) The proof proceeds by induction for decreasing values oft≤T. The inductive hypothesis is: For any good historyH t , there exists an oracleO t with∥O t −O∥ ∞ < 1 d satisfying P[V→1|H t ]≥ P M ′O t →1|y ≤t =a(H t ) 1− 1 50T T−t .(3) The base caset=Tfollows from the fact that, given a good historyH T ,Vsimply outputsa T . Thus, if a T = 1thenVoutputs 1 with probability one, andM ′ outputs 1 with probability 49 50 . Ifa T = 0bothVand M ′ output 0. For the inductive case, sinceAdrawsR= 192d 2 log100Tindependent samples conditioned on the value ofa I(t) to estimateˆp t , the Chernoff bound implies that for any historyH t−1 P h E t H t−1 i ≥1−P |ˆp t −p t |≥ 1 8d H t−1 >1−2e − R 192d 2 = 1− 1 50T .(4) Next ifE t occurs andB ′ aborts,V’s decision depends only on the value ofˆp t . Thus for any bitα t , the probability thatVoutputs 1 after takingr= 192d 2 log 100samples is, by the Chernoff bound, P[V→1|H t−1 ,E t ,a t =α t ,K t ]≥1−P ˆp O t −p t ≥ 1 8d H t−1 ,E t ,a t =α t ,K t ≥1−2e − r 48d 2 > 49 50 .(5) Next letH 1 t be the extension ofH t−1 whereE t occurs,a t = 1andB ′ does not abort. Similarly letH 0 t be the extension ofH t−1 whereE t occurs,a t = 0andB ′ does not abort. IfE t occurs, sinceAsamplesz A t independently of everything else in the protocol, the value ofz t =z A t +z B t (mod1)in step 2.c will be uniformly random in[0,1]. Thus,a t will be set to 1 with probability exactlyˆp t in stepti.e.P[a t = 1|H t−1 ,E t ] =ˆp t . Therefore, using (5) we have P[V→1|H t−1 ,E t ]≥P V→1|H 1 t ˆp t P[K t |H t−1 ,E t ,a t = 1] + 49 50 ˆp t P[K t |H t−1 ,E t ,a t = 1] +P V→1|H 0 t (1−ˆp t )P[K t |H t−1 ,E t ,a t = 0] + 49 50 (1−ˆp t )P[K t |H t−1 ,E t ,a t = 0] ≥min P V→1|H 1 t , 49 50 ˆp t + min P V→1|H 0 t , 49 50 (1−ˆp t ) For a good historyH t , letO t be the oracle guaranteed to exist by the inductive hypothesis, and define O t−1 to be identical toO t , except thatP[O t−1 (a I(t) ) = 1] =ˆp t . Observe that, for any good historyH t , the occurence ofE t implies that the oracleO t−1 will satisfy∥O t−1 −O∥ ∞ < 1 d . Applying the inductive 16 hypothesis (3) followed by (2) yields P[V→1|H t−1 ,E t ]≥min ( P M ′O t →1|y ≤t =a(H 1 t ) 1− 1 50T T−t , 49 50 ) ˆp t + min ( P M ′O t →1|y ≤t =a(H 0 t ) 1− 1 50T T−t , 49 50 ) (1−ˆp t ) ≥ P M ′O t →1|y ≤t =a(H 1 t ) 1− t 50T T−t ˆp t + P M ′O t →1|y ≤t =a(H 0 t ) 1− 1 50T T−t (1−ˆp t ) = P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) 1− 1 50T T−t . Therefore, combining the above calculation with (4) yields P[V→1|H t−1 ] =P[V→1|H t−1 ,E t ]P[E t |H t−1 ] ≥ P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) 1− 1 50T T−t 1− 1 50T =P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) 1− 1 50T T−(t−1) Thus by induction, (2), and (1) we conclude that P[V→1]≥P M ′O 1 →1 1− 1 50T T ≥ 49 50 P[M O →1]− 1 150 1− 1 50 ≥ 2 3 − 1 150 · 49 50 2 > 3 5 SoundnessIfx /∈L, we first describe how the proverBcan efficiently follow the prescribed protocol. In each roundtthe proverBdrawsR= 192d 2 log100Tsamples fromy t conditioned ony I(t) =a I(t) (this may involve queryingO(a I(t) )up toRtimes). NextBcomputes the sample meanˆq t of theseRsamples.B aborts if the valueˆp t output byA ′ in Step 2.a does not satisfy|ˆq t −ˆp t |< 1 2d . Finally, whenBis queried for a random integer in step 2.b,Boutputs a numberz B t ∈[0,1]sampled uniformly at random. Next we analyze the probability that the verifierVaccepts whenBfollows the protocol as described above, andA ′ is an arbitrary strategy. Letp t =P[y t = 1|y I(t) =a I(t) ]be the true probability thaty t = 1 conditioned on the execution so far. LetH t be the history of all messages sent in the protocol up until the end of roundt. Leta(H t )denote the bitsa 1 ...a t output in the historyH t . Throughout the proof we will consider three possible events based on the behavior ofA ′ in each step. LetE 0 t be the event that |ˆp t −p t |< 3 8d , letE 1 t be the event that 3 8d ≤|ˆp t −p t |< 3 4d , and letE 2 t be the event that|ˆp t −p t |≥ 3 4d . We will call a historyH t “good” ifE 0 t ′ ∪E 1 t ′ holds andBdoes not abort in roundt ′ for allt ′ ≤tin the history. LetK t be the event thatBaborts in roundt. For the analysis it will be useful to define an alternative oracle machineM ′ . The machineM ′ is exactly the same asMexcept that in the final stepT, ifMoutputs 0, then with probability 1 25 ,M ′ outputs 1, otherwiseM ′ outputs the same value thatMoutputs. This implies that, given any initial setting of the transcripty ≤t =a ≤t and any oracleO ′ , P h M ′O ′ →1|y ≤t =a ≤t i =P h M O ′ →1|y ≤t =a ≤t i + 1 25 ·P h M O ′ →0|y ≤t =a ≤t i ≥ 1 25 .(6) 17 The proof proceeds by induction for decreasing values oft≤T. The inductive hypothesis is: For any good historyH t there exists an oracleO t with∥O t −O∥ ∞ < 1 d satisfying P[V→1|H t ]≤P M ′O t →1|y ≤t =a(H t ) + T−t 50T .(7) The base caset=Tfollows from the fact that, given a full good historyH T ,Vsimply outputsa T . Thus, ifa T = 1bothM ′ andVoutput 1, and ifa T = 0,Voutputs0whileM ′ outputs 1 with probability 1 25 . For the inductive step we consider three cases, resulting from conditioning on each of theE i t fori=0,1,2. Conditioning onE 2 t .Observe that given any good historyH t−1 , ifE 2 t holds then the probability thatB fails to abort is, again by the Chernoff bound, P[K t |H t−1 ,E 2 t ] =P |ˆq t −ˆp t |< 1 2d H t−1 ,E 2 t ≤P |ˆq t −p t |> 1 4d H t−1 ,E 2 t < 1 50T Next ifE 2 t holds andBdoes abort, the probability thatVoutputs 1 after takingr= 192d 2 log100samples is, by the Chernoff bound, P[V→1|H t−1 ,E 2 t ,K t ]≤P ˆp O t −p t ≥ 3 8d H t−1 ,E 2 t ,K t < 1 50 . Therefore, combining the two above inequalities yields, P[V→1|H t−1 ,E 2 t ]≤ 1 50 + 1 50T < 1 25 .(8) Conditioning onE 0 t .Next we consider the case whereE 0 t occurs.B’s decision to abort at roundtdepends only on the value ofˆp t andˆq t . Thus for any bitα t , the Chernoff bound implies that the probability thatB aborts is at most P[K t |H t−1 ,E 0 t ,a t =α t ]≤P |ˆq t −p t |> 1 8d H t−1 ,E 0 t < 1 50T .(9) Next letH 1 t be the extension ofH t−1 whereE 0 t occurs,a t = 1andBdoes not abort. Similarly letH 0 t be the extension ofH t−1 whereE 0 t occurs,a t = 0andBdoes not abort. Observe that sinceBsamplesz B t independently of everything else in the protocol, the value ofz t =z A t +z B t (mod1)in step 2.c will be uniformly random in[0,1]. Thus,a t will be set to 1 with probability exactlyˆp t in stepti.e.P[a t = 1|H t−1 ,E 0 t ] =ˆp t . For a good historyH t , letO t be the oracle guaranteed to exist by the inductive hypothesis, and define O t−1 to be identical toO t , except thatP[O t−1 (a I(t) ) = 1] =ˆp t . Observe that, for any good historyH t , the occurrence ofE 0 t implies that the oracleO t−1 will satisfy∥O t−1 −O∥ ∞ < 1 d . Therefore, applying (9) followed by the inductive hypothesis (7) yields P[V→1|H t−1 ,E 0 t ]≤P[V→1|H 1 t ]ˆp t +P[V→1|H 0 t ](1−ˆp t ) + 1 50T ≤ P M ′O t →1|y ≤t =a(H 1 t ) + T−t 50T ·ˆp t + P M ′O t →1|y ≤t =a(H 0 t ) + T−t 50T ·(1−ˆp t ) + 1 50T =P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) + T−t 50T + 1 50T ≤P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) + T−(t−1) 50T .(10) 18 Conditioning onE 1 t .First observe that ifE 1 t occurs andBaborts, sinceVtakesr= 192d 2 log100 samples, the Chernoff bound implies that, P[V→1|H t−1 ,E 1 t ,K t ] =P ˆp O t −p t > 1 8d < 1 50 (11) Therefore, by (11) we have, P[V→1|H t−1 ,E 1 t ]<P V→1|H t−1 ,E 1 t , K t P K t |H t−1 ,E 1 t + 1 50 P K t |H t−1 ,E 1 t ≤max P[V→1|H t−1 ,E 1 t ,K t ], 1 50 (12) Next letG 1 t be the extension ofH t−1 whereE 1 t occurs,a t = 1andBdoes not abort. Similarly let G 0 t be the extension ofH t−1 whereE 0 t occurs,a t = 0andBdoes not abort. As before we know that the steps 2.b -2.d guarantee thatP[a t = 1|H t−1 ,E 1 t ] =ˆp t . Again for a good historyH t , letO t be the oracle guaranteed to exist by the inductive hypothesis, and defineO ′ t−1 to be identical toO t , except that P[O ′ t−1 (a I(t) ) = 1] =ˆp t . Observe that, for any good historyH t , the occurrence ofE 1 t implies that the oracle O ′ t−1 will satisfy∥O ′ t−1 −O∥ ∞ < 1 d . Continuing, the inductive hypothesis (7) implies that P V→1|H t−1 ,E 1 t , K t =P V→1|G 1 t ˆp t +P V→1|G 0 t (1−ˆp t ) ≤ P M ′O t →1|y ≤t =a(G 1 t ) + T−t 50T ˆp t + P M ′O t →1|y ≤t =a(G 0 t ) + T−t 50T (1−ˆp t ) =P h M ′O ′ t−1 →1|y ≤t =a(H t−1 ) i + T−t 50T (13) Therefore combining (12) and (13) we conclude that P V→1|H t−1 ,E 1 t ≤max P h M ′O ′ t−1 →1|y ≤t =a(H t−1 ) i + T−t 50T , 1 50 =P h M ′O ′ t−1 →1|y ≤t =a(H t−1 ) i + T−t 50T <P h M ′O ′ t−1 →1|y ≤t =a(H t−1 ) i + T−(t−1) 50T (14) where the penultimate equality follows from (6). Putting it all together.By (6) combined with (8), (10), and (14) we have P[V→1|H t−1 ] = 2 X i=0 P V→1|H t−1 ,E i t P E i t |H t−1 ≤max i∈0,1,2 P V→1|H t−1 ,E i t ≤P M ′O t−1 →1|y ≤t−1 =a(H t−1 ) + T−(t−1) 50T . Here the oracleO t−1 may either come from the case whereE 1 t achieves the maximum or whereE 0 t does. Either way,O t−1 satisfies∥O t−1 −O∥ ∞ < 1 d as required. Thus by induction, (6), and (1), P[V→1] =P M ′O 1 →1 + 1 50 =P M O 1 →1 + 1 25 P M O 1 →0 + 1 50 ≤ 1 3 + 1 150 + 1 25 + 1 50 = 2 5 . 19 EfficiencyBoth honest proversAandBneed to sample fromOat mostR=O(d 2 logT) =O(K 2 logT) times for each of theTsteps of the machineM. The current head position ofMcan be encoded inO(logT) bits, so simulating one step ofMrequires at mostO(log(T))time.Vneeds to read theO(l)relevant coordinates ofa I(t) , the locations of which can each be encoded inO(logT)bits, yielding a total ofO(llogT) bits read.Vmust further sample at mostO(d 2 ) =O(K 2 )times fromO. E Missing Proofs for Debate with a Witness This section gives the missing proofs for the power of debate with a witness. Proof of Theorem 7.1. CompletenessIfx∈Lthen an honest proverAcan output a valid witnessw(i.e. satisfyingM(x,w) = 1) and run the protocol of Figure 4 with input(x,w)and machineM. By the completeness case of Theorem 5.3, the verifier will output 1 no matter the behavior of a potentially dishonest proverB ′ . SoundnessSupposex /∈L. Letwbe any witness produced by a dishonest proverA ′ . ClearlyM(x,w) = 0, so by the soundness case of Theorem 5.3 the verifier will always output 0. EfficiencyThe only cost is running the protocol of Figure 4 and so the prover and verifier time are the same as Theorem 5.3. Proof of Theorem 7.2. CompletenessIfx∈Lthen an honest proverAcan output a valid witnessw(i.e. satisfyingM(x,w) = 1 with probability at least 2 3 ) and run the protocol of Figure 1 with input(x,w)and machineM. By the completeness case of Theorem 6.2, the verifier will output 1 with probability at least 3 5 , no matter the behavior of a potentially dishonest proverB ′ . SoundnessSupposex /∈L. Letwbe any witness produced by a dishonest proverA ′ . ClearlyM(x,w) = 0 with probability at least 2 3 . Thus, by the soundness case of Theorem 6.2 the verifier will output 1 with probability at most 2 5 . EfficiencyThe only cost is running the protocol of Figure 1 and so the prover and verifier time are the same as Theorem 6.2. 20