Research map / Large language models / AI and society
Scalable AI Safety via Doubly-Efficient Debate
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces doubly-efficient debate, a complexity-theoretic model where polynomial-time provers debate and a near-linear verifier uses a constant number of black-box human judgement queries, with protocols for deterministic, stochastic, and witness-based settings.
Problem
Scalable AI oversight: debate protocols where the honest prover must be computationally efficient and the verifier must query human judgement only a constant number of times, including when human judgements are stochastic.
Approach
Designs debate protocols in which the honest prover runs in polynomial time and the verifier makes O(1) oracle queries: for deterministic oracles, the prover outputs a middle configuration or full transcript with bisection/cross-examination; for stochastic oracles, the prover proposes next-bit probabilities and coin-flipping under cross-examination with abort-and-sample checks, under a Lipschitz a
Key results
- Deterministic debate decides any time-T, space-S language with (O(T log T), O(S log T), O(1)) debate protocol.
- Stochastic debate for K-Lipschitz machines achieves completeness 3/5 and soundness 2/5 with verifier time O(K^2 + l log T) and O(K^2) oracle queries.
- Cross-examination debate decides any polynomial-time language with O(l log T) verifier time and O(1) oracle queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use deterministic debate without cross-examination | Deterministic oracle computation using time T and space S · Deterministic oracle computation | verifier time: O(S\log T) | Helped |
| Add cross-examination | Debate for deterministic oracle computation · Deterministic oracle computation (time T; query length l) | verifier time: O(l\log T) | Helped |
| Add cross-examination | Debate for deterministic oracle computation · Deterministic oracle computation (time T; query length l) | verifier oracle queries: O(1) | Helped |
| Use a stochastic-oracle debate protocol with cross-examination under the K-Lipschitz assumption | K-Lipschitz probabilistic oracle computation · Stochastic oracle computation | verifier oracle queries: O(K^2) | Helped |
| Use a stochastic-oracle debate protocol with cross-examination under the K-Lipschitz assumption | K-Lipschitz probabilistic oracle computation · Stochastic oracle computation | verifier time: O(K^2 + l\log T) | Helped |
| Provide a witness and use cross-examination | NP^O computation · NP^O with witness | verifier oracle queries: O(1) | Helped |
| Provide a witness and use stochastic debate with cross-examination | K-Lipschitz MA^O computation · MA^O with witness | verifier oracle queries: O(K^2) | Helped |
Surprising findings
- With black-box oracle access, the main IP=PSPACE and PCP theorems are false, so debate by competing provers is needed instead.
Limitations
- Assumes provers can accurately simulate human judgements on any query.
- Requires debaters to produce polynomial-length human-verifiable natural-language transcripts.
- Verifier oracle assumed correct; flawed oracles not handled.
Experimental setup
Metrics: completeness soundness prover and verifier running time verifier query complexity
Baselines: original debate protocol (Irving et al. 2018) cross-examination debate (Barnes & Christiano)
Builds on: AI safety via debate doubly-efficient interactive proofs IP=PSPACE cross-examination debate
Closest papers by meaning
- RedDebate: Safer Responses Through Multi-Agent Red Teaming Debates (ICML 2026 · similarity 0.87)
- On scalable oversight with weak LLMs judging strong LLMs (NeurIPS 2024 · similarity 0.86)
- SAFEPATH: Preventing Harmful Reasoning in Chain-of-Thought via Early Alignment (NeurIPS 2025 · similarity 0.85)
- Position: AI Safety Must Embrace an Antifragile Perspective (ICML 2025 · similarity 0.85)
- When Debate Helps: Proposal Supply and Verification-Aware Readout in Multi-Agent Reasoning (NeurIPS 2026 · similarity 0.84)
- Towards Safe Reasoning in Large Reasoning Models via Corrective Intervention (ICLR 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.