PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable AI Safety via Doubly-Efficient Debate

Jonah Brown-Cohen, Geoffrey Irving, Georgios Piliouras

arXiv:2311.14125v1cs.AIcs.LG

TL;DR

Complex AI tasks can exceed the reach of direct human feedback, while interactive-proof guarantees do not directly cover black-box human judgments. The paper introduces doubly-efficient debate protocols and proves that arbitrary polynomial-time computations can be verified with a constant amount of human judgment, within the paper’s stated scope.

  • Problem

    Complex AI tasks can be difficult for humans to judge directly, and interactive-proof methods for precise tasks do not directly apply to black-box human judgments.

    Source: §1 · pp. 1–2

  • Method

    The paper develops debate protocols in which competing polynomial-time provers try to convince a more efficient verifier using access to black-box judgments.

    Source: §1 · p. 2

  • Results

    The main theorems show that doubly-efficient debate can verify arbitrary polynomial-time computations using only a constant amount of human judgment.

    Source: §8 · p. 9

  • Takeaways & Limitations

    The model provides theoretical grounding for scalable oversight of powerful AI systems using limited human feedback, as an initial step toward that goal.

    Source: §8 · p. 9

    The model covers computations verifiable by a human reading a polynomial-length transcript, not necessarily polynomial-time computations lacking such transcripts.

    Source: §8 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

As AI tasks grow more complex, direct human feedback on long reasoning and action traces becomes limited, creating a need for scalable oversight. The paper introduces doubly-efficient debate and develops protocols for deterministic, stochastic, and self-proposed solutions.

1 Introduction

  • Complex language-model tasks can outgrow direct human feedback, while high-stakes documents such as contracts require efficient oversight of their content.The paper motivates protocols that use human judgments efficiently for training and oversight.Source: §1 · p. 1
  • Interactive-proof methods handle precise computational tasks, but their guarantees do not directly extend to human judgments available only through a black box.The paper points to competition between provers as a way to pursue efficient verification with black-box judgments.Source: §1 · pp. 1–2
  • Doubly-efficient debate has two polynomial-time provers compete to convince a more efficient verifier of a computation that depends on black-box judgments.Under appropriate assumptions, the verifier uses a constant number of judgment queries and time linear in one query’s size.Source: §1 · p. 2

1.1 Our Results

  • The results cover deterministic judgments with explicit instructions, stochastic judgments, and cases where models propose solutions and justify them in natural language.The paper also formalizes its Section 6 main theorem in Lean 4.Source: §1.1 · p. 3

2 Related work

Prior debate theory studied powerful or unbounded provers, while this paper focuses on efficient honest strategies even against an unbounded dishonest prover. The authors also position debate among process-based feedback and other approaches to scalable oversight.

2 Related work

  • Debate between human-judged AI models was proposed by Irving et al. [2018], and follow-up cross-examination extended its power to NEXP [Barnes and Christiano, 2020b].Earlier work modeled both provers as computationally unbounded; this paper gives the honest prover a polynomial-time winning strategy even against an unbounded dishonest prover.Source: §2 · p. 3
  • Doubly-efficient interactive proofs, introduced by Goldwasser et al. [2015], aim to let a verifier check delegated computations efficiently; Reingold et al. [2021] gave the best known results for space-bounded computation.The related-work discussion also notes Feige and Kilian [1997] on competing unbounded provers and Wäldchen et al. [2022] on classifier interpretability.Source: §2 · p. 3
  • The authors connect debate to process-based feedback [Stuhlmüller and jungofthewon, 2022, Uesato et al., 2022], which supervises reasoning rather than only final outcomes.They distinguish debate from other scalable-oversight approaches, including recursive reward modelling [Leike et al., 2018] and iterated amplification [Christiano et al., 2018].Source: §2 · p. 3

3 Preliminaries

The preliminaries model natural-language instructions and human judgments as an oracle computation. They define decision and witness-verification settings, and describe computation transcripts and the coordinates relevant to each step.

3 Preliminaries

  • An oracle machine models instructions as a machine and human judgments or other external feedback as an oracle, whose responses may be stochastic and independent across queries.For language-model tasks, the oracle can also represent search results, sensor observations, or API outputs.Source: §3 · p. 4
  • NPO and MAO capture problems with polynomial-length witnesses whose correctness can be checked using polynomially many human judgments on a potentially long transcript.The paper connects these settings to plans proposed in natural language and justified through a sequence of steps.Source: §3 · p. 4
  • A transcript records the bits of a computation over time, and each output coordinate depends on a set of transcript coordinates read when computing it.For standard Turing machines this set has size O(1), while for oracle Turing machines it may be as large as the transcript length.Source: §3 · p. 4

4 Debate

The paper formalizes debate as interaction between two provers and a verifier, then imposes efficiency constraints on the provers, verifier, and oracle queries. It relates verifier queries to training-time human judgments and distinguishes inference-time behavior.

4 Debate

  • A debate consists of two provers exchanging messages over rounds, followed by a verifier that evaluates the full debate transcript.The provers and verifier are oracle Turing machines sharing an input and oracle access.Source: §4 · p. 4

4.1 Doubly-efficient debate

  • Completeness and soundness require the honest prover to win with the specified probability even against an unbounded dishonest strategy.For deterministic oracle machines, the honest prover always wins; for stochastic ones, the protocol requires a constant completeness-soundness gap that can be amplified.Source: §4.1 · p. 5
  • Doubly-efficient debate restricts provers to polynomial time and aims for verifier time linear in query length and input size, with a sublinear or ideally constant number of oracle queries.The original debate definition allowed unbounded prover time.Source: §4.1 · p. 5

4.2 Training and inference with debate

  • During training, provers’ oracle access represents predicted human judgments, while verifier queries represent actual human ratings, making human-label cost equal to verifier oracle queries.Thus, bounded verifier queries bound the number of human judgments even for arbitrarily complex computations performed by the provers.Source: §4.2 · p. 5
  • At inference time, the debate still runs without human feedback, and the output of prover A is trusted unless prover B aborts or identifies a flaw.Source: §4.2 · p. 5

5 Deterministic debate

Deterministic debate protocols decide bounded-space computations with a constant number of oracle queries; cross-examination extends this to polynomial-time computations while keeping verifier time and oracle-query costs small.

5 Deterministic debate

  • Theorem 5.1 gives a deterministic debate protocol for computations using time T and space S, with parameters (O(T log T), O(S log T), O(1)).The section summarizes this as deciding bounded-space problems with verifier time nearly linear in space and a constant number of oracle queries.Source: §5 · pp. 5–6
  • Theorem 5.1 is compared with doubly-efficient interactive proofs, whose O(S^2 polylog T) time bound has not been improved to O(S polylog T).The cited interactive-proof protocol also does not apply with a black-box oracle.Source: §5 · p. 6

5.1 Cross-examination

  • Cross-examination lets independent, non-communicating copies be queried and allows the verifier to inspect only selected parts of the transcript.For language-model debaters, independent copies can be run separately or queried without earlier debate messages in context.Source: §5.1 · p. 6
  • Theorem 5.3 gives a deterministic cross-examination protocol for oracle computations in time T, with parameters (O(T log T), O(l log T), O(1)).The oracle queries have length l.Source: §5.1 · p. 6
  • Theorem 5.3’s protocol has A provide the computation transcript, B identify a purported error, and the verifier check that location.This is the section’s stated basic mechanism for cross-examination.Source: §5.1 · p. 6

6 Stochastic debate

For stochastic-oracle computations, the section gives a cross-examination debate protocol under a Lipschitzness condition. Its round-by-round checks use oracle judgments to assess the honest debater’s proposed next-step distributions.

6 Stochastic debate

  • The machine must be K-Lipschitz because small changes in the stochastic oracle’s distribution can accumulate into an O(1) change in output probability over T steps.The section motivates the condition by noting that changes of order O(1/T) can accumulate over a time-T computation.Source: §6 · p. 6
  • Theorem 6.2 gives a cross-examination protocol for a K-Lipschitz probabilistic oracle machine running in time T, with completeness 3/5 and soundness 2/5.Its parameters are (O(K^2 T log T), O(K^2 + l log T), O(K^2)), for oracle queries of length l.Source: §6 · p. 7
  • In each of T rounds, A proposes a distribution for the next bit, the debaters use cross-examination to sample it, and B may trigger an oracle check.If B aborts, the verifier samples from O to check whether A’s proposed distribution is correct.Source: §6 · p. 7
  • A meta-analysis plan illustrates the protocol: A follows the instructions and presents supporting study text, while B can challenge a step.For a challenged study-exclusion decision, the proposed probability is checked against human raters’ responses.Source: §6 · p. 8

7 Doubly-efficient debate with a witness

The witness setting covers problems where a model proposes a solution and justification, with debate protocols checking the witness through a verifier. The section gives deterministic and stochastic-oracle results for this setting.

7 Doubly-efficient debate with a witness

  • The witness w can be a model-proposed solution accompanied by a step-by-step justification, and the protocol lets the human judge check only a constant number of argument steps.The verifier for the language receives both x and w as input.Source: §7 · p. 8
  • For L in NPO with a time-T verifier and oracle queries of length l, Theorem 7.1 gives a deterministic cross-examination protocol with parameters (O(T), O(l log T), O(1)), given witness w.Source: §7 · p. 9
  • For L in MAO with a K-Lipschitz probabilistic verifier running in time T, Theorem 7.2 gives a cross-examination protocol with completeness 3/5 and soundness 2/5, given witness w.Its parameters are (O(K^2 T log T), O(K^2 + l log T), O(K^2)), for oracle queries of length l.Source: §7 · p. 9
  • In the caffeine meta-analysis example, the proposed witness is a high-level plan plus its justification, followed by execution of the plan.The example contrasts this with the earlier setting where the plan is supplied in advance.Source: §7 · p. 9

8 Conclusion and Open Problems

The paper presents doubly-efficient debate as a theoretical basis for verifying computations with limited human judgment. Its stated results are an initial step, with important limits around human-verifiable transcripts, prover accuracy, and fallible judgments.

8 Conclusion and Open Problems

  • Doubly-efficient debate uses two polynomial-time provers to convince a more efficient verifier of a computation involving black-box human judgments.The stated goal is to verify arbitrary polynomial-time computations using only a constant amount of human judgment.Source: §8 · p. 9
  • The results cover computations whose transcripts a human could verify by reading the entire polynomial-length transcript.The authors ask whether the model can extend to computations without such transcripts, including those that may require interrogating implicitly represented exponential-length transcripts.Source: §8 · p. 9
  • The paper leaves open how to handle fallible human judgments, including oracles that err on limited or randomly selected subsets of queries.Theorem 6.2 allows stochastic oracle responses when the computation's correct answer has constant advantage over random guessing.Source: §8 · p. 10

A Deterministic Debate Protocols

The deterministic debate protocols are presented in figures for time T and space S, and for time T with cross-examination. The accompanying schematic depicts provers challenging and checking a computation step.

A Deterministic Debate Protocols

  • Figure 3 presents a doubly-efficient debate protocol parameterized by time T and space S.The supplied caption does not specify the protocol's steps.Source: Figure 3 · p. 13
  • Figure 4 presents a doubly-efficient debate protocol with cross-examination, parameterized by time T.The supplied caption does not specify the protocol's steps.Source: Figure 4 · p. 13
  • Figure 5 schematizes A simulating M(x), B identifying an allegedly incorrect step, and V checking that step.The supplied caption does not state how the step is selected or what other protocol checks occur.Source: Figure 5 · p. 14

B Missing Proofs for Deterministic Debate

The missing proofs establish completeness, soundness, and efficiency for deterministic debate protocols. The debate-game formulation expresses the protocol guarantee through polynomial-time strategies and expected payoffs.

B Missing Proofs for Deterministic Debate

  • For Theorem 5.1, an honest prover supplies the true middle configuration, while a dishonest claim leaves an incorrect half that the opposing prover can identify for rejection.The verifier's checks reject if the final configurations fail to form a correct step or a configuration is invalid.Source: B Missing Proofs for Deterministic… · p. 14
  • For Theorem 5.3, an honest prover supplies the true transcript, and an opposing prover can locate an incorrect step in a false transcript for the verifier to reject.The honest prover B runs M for O(T) total steps; the verifier runs in O(S log T) time.Source: B Missing Proofs for Deterministic… · p. 14
  • Theorem 5.1's simulation takes O(T log T) time for the provers, while the verifier takes O(l log T) time to inspect relevant bits and one machine step.The current head position is encoded in O(log T) bits.Source: B Missing Proofs for Deterministic… · p. 15

C The debate game

  • In the debate game, each prover's expected payoff depends on whether the verifier accepts, and a polynomial-time strategy can secure the correct-answer side's stated payoff bound.For x in L, A can achieve at least c; for x not in L, B can achieve at least 1 − s.Source: C The debate game · p. 15

D Missing Proofs for Stochastic Debate

The proof analyzes stochastic debate through sampling estimates, abort checks, and induction over good histories. Its soundness calculation bounds verifier acceptance by 2/5 when x is not in L.

Completeness

Soundness

  • The soundness proof divides A′’s estimates into E0, E1, and E2 according to their error from the true conditional probability.It defines good histories by requiring E0 and no abort in every preceding round.Source: D Missing Proofs for Stochastic Debate · p. 17

Inductive proof

  • A backward induction maintains a nearby oracle for each good history, adjusting the current query probability to the estimated value.The proof considers the E0 and E1 cases when establishing the next oracle’s distance bound.Source: D Missing Proofs for Stochastic Debate · pp. 18–19

Soundness

Efficiency

  • Both honest provers use O(K^2 log T) oracle samples per machine step, while the verifier reads O(l log T) bits and uses O(K^2) oracle samples.The machine head position is encoded using O(log T) bits.Source: D Missing Proofs for Stochastic Debate · p. 20

E Missing Proofs for Debate with a Witness

The proofs show that adding a witness preserves the completeness and soundness guarantees of the underlying debate protocols. The resulting prover and verifier costs match those protocols.

Theorem 7.1

Theorem 7.2

  • With a witness accepted with probability at least 2/3, the verifier accepts with probability at least 3/5 for x∈L and at most 2/5 for x∉L.The completeness and soundness guarantees hold against a potentially dishonest opposing prover.Source: E Missing Proofs for Debate with a… · p. 20
  • Theorem 7.2’s witness protocol has the same prover and verifier running times as the underlying protocol of Figure 1.Source: E Missing Proofs for Debate with a… · p. 20

Related papers

Loading 2311.14125v1…