PaperlayerView exact revision on arXiv

Source-linked AI summary

How to Have a Sensitive Debate: An Instance-Optimal Protocol for AI Debate

Jiawei Li, Zhiyang Xun, Lijie Chen, Jonah Brown-Cohen

arXiv:2610.02557v1cs.AIcs.CCcs.GTcs.LG

TL;DR

Complex AI outputs increasingly require human oversight, but can be difficult to verify directly. This paper uses fractional block sensitivity to design a debate protocol for problems with sufficiently stable decompositions. It establishes worst-case guarantees, dominant-strategy honesty, and instance-wise optimality when human judgments are accessed as a black box.

  • Problem

    Complex, open-ended AI tasks can require human judgment, while their outputs may be difficult for experts to evaluate directly.

    Source: §1 · pp. 1–2

  • Method

    The protocol connects stable decompositions to fractional block sensitivity, letting Bob challenge an overly sensitive decomposition or select a sub-claim for recursive debate.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Results

    The protocol provides worst-case guarantees and dominant-strategy honesty, and matches an instance-wise black-box query lower bound for finding flawed sub-claims.

    Source: §1.2 · pp. 4–5

  • Takeaways & Limitations

    Within the recursive-decomposition framework, fractional block sensitivity characterizes problems efficiently solvable by debate, and Bob need not determine whether Alice’s individual answers are correct.

    Source: §6 · p. 14

    The protocol’s structural assumption is that functions in the problem decomposition have bounded fractional block sensitivity.

    Source: §3.3 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

AI debate aims to make complex, judgment-dependent outputs supervisable by breaking them into simpler claims. The paper introduces a protocol for problems with sufficiently stable decompositions, using fractional block sensitivity to establish worst-case guarantees, dominant-strategy honesty, and instance-wise optimality under black-box human judgment.

1 Introduction

  • The motivating oversight problem is that complex, open-ended outputs can require human judgment and be difficult for experts to evaluate directly.AI debate is presented as a way to break such evaluations into simpler claims for a human judge.Source: §1 · pp. 1–2

1.1 Our Results

  • Fractional block sensitivity links stable decompositions to an efficient strategy for Bob to sample a sub-claim that has a non-trivial chance of being incorrect.The paper relates this quantity to the number of queries a randomized verifier needs to check an untrusted proof.Source: §1.1 · p. 3

1.2 Technical Overview

  • Alice decomposes a claim into sub-claims, while Bob either challenges excessive sensitivity or selects a sub-claim for recursive debate.The process ends at depth d, when a human judge evaluates the selected sub-claim; the stated repetition cost is O(ρ^d log n), rather than exhaustive exploration of q^d sub-claims.Source: §1.2 · pp. 3–4
  • The protocol gives worst-case guarantees and makes honest, correct play a dominant strategy for both debaters, improving on the prior average-case and weaker-equilibrium guarantee.It also matches the instance-wise query lower bound when human judgments are available only as black-box queries.Source: §1 · p. 2, §1.2 · pp. 4–5
  • For an instance whose best decomposition has fractional block sensitivity ρ per step, any black-box protocol needs at least Ω(ρ^d) queries to find a flawed sub-claim with constant probability.This matches the cost of the paper’s protocol on that instance.Source: §1.1 · p. 3, §1.2 · p. 5

2 Related work

The section traces theoretical debate from early protocols through work on computationally bounded debaters, then situates this paper among related verification and empirical research.

Prior debate protocols

  • Brown-Cohen et al. [2025] introduced prover-estimator debate for a broader class of recursively decomposable problems and the stability notion studied here.The paper relates stability to fractional block sensitivity.Source: §2 · p. 5

Related theoretical work

  • Earlier complexity-theoretic work includes alternating Turing machines, private-communication arguments, and secure delegation of computation [Chandra et al., 1981; Feige and Kilian, 1997; Canetti et al., 2013].Chen et al. [2023] study algorithms for learning equilibria in debate games, focusing on computational efficiency for judges and learners.Source: §2 · p. 5

Related verification frameworks

  • Chen et al. [2026] study fixed-circuit oracle computations under robustness or low-degree conditions, while this work uses online recursive decompositions with a fixed aggregator.The frameworks are incomparable; their low-degree result is orthogonal to this paper’s lower bound because it adds algebraic structure.Source: §2 · p. 5

Empirical debate

Related verification frameworks

  • Chen et al. [2026]’s ε-robustness condition implies fbs = O(1/ε) for its induced Boolean function.The implication uses a uniform weighting of oracle-answer coordinates in the dual FBS program.Source: §2 · p. 5

3 Preliminaries

The preliminaries model human judgment as a queryable oracle, specify recursively decomposable problems, and introduce fractional block sensitivity as a measure of decomposition stability.

3.1 Complexity-theoretic framework of AI debate

  • Debate protocols are modeled as Turing-machine algorithms that query a human-judgment oracle O, with decision problems represented as Boolean functions.The protocol-design aim is to solve broad classes of problems using few oracle queries.Source: §3.1 · p. 6

3.2 Recursively decomposable problems

  • A recursively decomposable problem uses a fixed one-step aggregator to combine answers to q subproblems arranged in a depth-d decomposition tree.The aggregator must return the correct answer when supplied correct subproblem answers; it may reject decompositions that are difficult to verify. A brute-force protocol visits q^d leaves, so recursive debate seeks to avoid checking most nodes.Source: §3.2 · pp. 6–7
  • The aggregator can range from AND over supporting claims to a majority vote, provided its properties are readily verifiable by human judgment.A rejected decomposition can cause its proposer to lose immediately.Source: §3.2 · pp. 6–7

3.3 Fractional block sensitivity

  • Fractional block sensitivity measures how closely a distribution can match an input’s coordinate marginals while still changing a Boolean function’s output.The paper’s structural assumption is bounded fractional block sensitivity for functions arising in the decomposition.Source: §3.3 · p. 7
  • For majority at an input with two-thirds ones, the example gives fractional block sensitivity 4, whereas AND on the all-ones input has value n.The contrast illustrates that a single randomly flipped bit can change AND’s output, while changing majority requires flipping a larger portion of the ones.Source: §3.3 · p. 7
  • The dual FBS linear program assigns nonnegative weights to coordinates so every sensitive block receives total weight at least 1, minimizing total weight.Its optimum equals the primal value by strong duality; the dual is a fractional cover of sensitive blocks by coordinates.Source: §3.3 · p. 8

4 Protocol

The FBS debate recursively checks selected subclaims while testing the stability of Alice’s decompositions. Under the stated solvability and bounded-FBS conditions, honest Alice wins, while an incorrect top-level answer is detected with probability at least ρ^-d.

Protocol

  • Alice decomposes each claim into q subproblems and answers; Bob checks consistency and bounded fractional block sensitivity, then samples a subproblem for recursive debate.At a leaf, the human-judgment oracle determines whether Alice’s answer wins; Figure 1 depicts a round and its recursion.Source: §4 · pp. 8–9, Figure 1 · p. 10

Completeness

  • An honest Alice wins with probability 1 when a solving decomposition tree satisfies the solvability and FBS conditions.The conditions require computable children, a way to solve nodes, and fractional block sensitivity at most ρ at each non-leaf node.Source: §4 · p. 9
  • Under those conditions, honest Alice’s running time is O(d · (TD + q · T)) and her oracle-query count is O(d · q · Q).TD is the time to calculate a node’s children; T and Q are the time and oracle queries needed to solve a node.Source: §4 · p. 9

Soundness

  • An incorrect top-level answer is caught with probability at least ρ^-d, and O(ρ^d log n) repetitions raise detection probability to at least 1 − 1/poly(n).The result applies regardless of Alice’s strategy; the parameters are fractional block sensitivity ρ and decomposition depth d.Source: §4 · pp. 9, 11

Protocol

  • The protocol trades inference-time computation for allowing arguments with greater sensitivity.The soundness repetition count grows with ρ^d.Source: §4 · p. 9

5 Lower Bound

The lower bound models verification as an adaptive checker with the full visible decomposition tree and oracle queries. It relates the checker’s distinguishing advantage to fractional block sensitivity, yielding a query lower bound that grows exponentially with tree depth under local sensitivity assumptions.

5 Lower Bound

  • The lower bound applies even when the checker receives the full visible tree, has an honest Bob, and may communicate arbitrarily with Alice.The checker is a randomized algorithm making at most m adaptive oracle queries.Source: §5 · p. 11
  • The argument treats the fixed tree as a composed Boolean function over its leaf-query strings, with the reference oracle supplying the leaf assignment.The leaf queries must be pairwise distinct; otherwise, for example, an AND tree querying one repeated string computes only a one-bit identity function.Source: §5 · pp. 11–12
  • The proof bounds the checker’s distinguishing advantage by mρ_T, then constructs an oracle that flips the root while differing only on a sensitive block.Coupled executions have identical transcripts until a query hits the flipped block.Source: §5 · pp. 12–13
  • A tree’s global fractional block sensitivity is at least ρ^d when every internal node has local fractional block sensitivity at least ρ.The proof establishes this recursively over the depth-d tree.Source: §5 · pp. 13–14
  • m ≥ (1 − 2ε)ρ^d queries are required for correctness probability at least 1 − ε under each oracle, when every local aggregator has fractional block sensitivity at least ρ.The bound assumes ε < 1/2 and pairwise distinct leaf queries.Source: §5 · pp. 11, 13, 14
  • The ρ^d scale matches the standard fractional-certificate composition barrier, while the debate-verification bound permits arbitrary adaptive oracle queries.The passage connects the independent-leaf case to randomized-query lower bounds via composition theory.Source: §5 · p. 14

6 Discussion and Open Problems

Fractional block sensitivity characterizes efficient debate within the recursive-decomposition framework, while the protocol asks Bob to sample sensitive subproblems rather than determine whether Alice’s answers are correct. The discussion leaves open whether protocols can surpass this barrier, noting that the lower bounds assume human judgments are accessible only through black-box queries.

6 Discussion and Open Problems

  • Fractional block sensitivity precisely characterizes which problems debate can solve efficiently within the recursive-decomposition framework.The protocol does not require Bob to determine whether Alice’s subproblem answers are correct; he samples subproblems to which the outcome is sufficiently sensitive.Source: §6 · p. 14
  • Unlike Debate = PSPACE, this protocol asks Bob to sample sensitive subproblems rather than identify Alice’s flawed subproblems.The discussion notes that identifying flaws may be more computationally complex than creating subproblems, posing an obstacle for computationally bounded debaters.Source: §6 · p. 14
  • Whether protocols can surpass the fractional block sensitivity barrier remains open, and the lower bounds apply only when human judgment is accessible through black-box queries.The discussion suggests that relaxing the black-box oracle assumption might yield better debate protocols.Source: §6 · p. 14
Loading 2610.02557v1…