How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs

What it claims

The paper's payoff is a concrete table of four protocols, each a relativizing doubly-efficient interactive proof or argument for oracle-aided computation, with stated complexity tradeoffs. The computation is modeled as an oracle Boolean circuit of depth D with ℓ oracle gates over d levels; n is input size, ε the robustness fraction, σ the soundness parameter. The central promise: the verifier makes far fewer oracle queries than it would need to run the computation itself — meaning few queries to a human expert or database.

Why robustness/low-degree are needed

The summary says the paper handles these two settings but not why they are necessary. Barbara, Chiesa, and Guan [BCG25] proved that no interactive proof relativizes for all computations: if a computation makes many random-oracle queries and its output is "unstable" (hinges on every query being correct), the verifier must check every oracle call and cannot be efficient. Robustness (output unchanged if ≤ε-fraction of oracle answers are corrupted) lets the verifier spot-check; low-degree structure gives an algebraic handle instead. These are the two escape hatches around the impossibility result.

How it works

The robust-setting proof builds on an interactive proof of proximity (IPP), where a sublinear-time verifier has only query access to the input and rejects only inputs "far" from the language. The verifier runs an IPP on C^Q(x)=1, where Q is the queries C makes to oracle O plus their answers. Since the verifier lacks reliable access to Q, it asks the (untrusted) prover for the bits it needs, then checks each (x_i, y_i) by verifying y_i = O(x_i) with one oracle call. Ensuring x_i itself is computed correctly requires an additional DEIP — which works cleanly for nonadaptive queries (each x_i depends only on x), but breaks for adaptive queries where x_i depends on earlier oracle answers. The adaptive case (Theorems 4.5, 4.10) is the harder contribution.

Evidence (the four protocols)

• Thm 4.1 — statistical soundness, nonadaptive, ε-robust; V queries O(σ/ε).
• Thm 4.5 — statistical, adaptive, ε-robust; V time Õ(σd(εℓD + 1/ε + n)), queries Õ(σd/ε).
• Thm 4.10 — computational soundness, adaptive, ε-robust; V time Õ(1/ε + n), O(1) rounds.
• Thm 5.4 — computational, poly-degree oracle, adaptive; V time Õ(n), 1 oracle query.

Statistical soundness holds against unbounded provers; computational soundness (arguments, using hash trees and polynomial commitments) only against poly-time provers, but buys dramatically better verifier efficiency.

Limits

This is theory, not an implementation — no code, weights, or empirical results. The guarantees are conditional: robust protocols assume the computation's output tolerates ε-corruption (the authors argue human judgment is naturally robust, e.g. via majority vote over rephrasings), and the low-degree case assumes the oracle has that algebraic structure (a database's low-degree extension qualifies). The critique of debate — that it needs two equally-capable, properly-incentivized provers with one truthful — is the motivation, not a proven weakness of debate itself.