# Debate is efficient with your time

arXiv: https://arxiv.org/abs/2602.08630 · HTML: https://mlsanity.com/paper/2602.08630/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 7 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## Builds on (most cited first, 3 of 3)

- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Scalable AI Safety via Doubly-Efficient Debate](https://mlsanity.com/paper/2311.14125/) (2023)
- [Avoiding Obfuscation with Prover-Estimator Debate](https://mlsanity.com/paper/2506.13609/) (2025)

## Built on by (most cited first, 2 of 2)

- [Knowledge Divergence and the Value of Debate for Scalable Oversight](https://mlsanity.com/paper/2603.05293/) (2026)
- [When Honesty is Not Enough in AI Debate](https://mlsanity.com/paper/2609.29189/) (2026)

## Abstract (arXiv)

AI safety via debate uses two competing models to help a human judge verify complex computational tasks. Previous work has established what problems debate can solve in principle, but has not analysed the practical cost of human oversight: how many queries must the judge make to the debate transcript? We introduce Debate Query Complexity}(DQC), the minimum number of bits a verifier must inspect to correctly decide a debate. Surprisingly, we find that PSPACE/poly (the class of problems which debate can efficiently decide) is precisely the class of functions decidable with O(log n) queries. This characterisation shows that debate is remarkably query-efficient: even for highly complex problems, logarithmic oversight suffices. We also establish that functions depending on all their input bits require Omega(log n) queries, and that any function computable by a circuit of size s satisfies DQC(f) <= log(s) + 3. Interestingly, this last result implies that proving DQC lower bounds of log(n) + 6 for languages in P would yield new circuit lower bounds, connecting debate query complexity to central questions in circuit complexity.