토론은 시간 효율적이다

Debate is efficient with your time

토론을 통한 AI 안전성은 인간 심판이 복잡한 계산 작업을 검증하는 것을 돕기 위해 두 개의 경쟁 모델을 사용한다. 이전 연구들은 토론이 원칙적으로 어떤 문제들을 해결할 수 있는지 확립했으나, 인간 감독의 실질적 비용, 즉 심판이 토론 기록에 대해 얼마나 많은 질의를 해야 하는지는 분석하지 않았다. 우리는 검증자가 토론을 올바르게 판정하기 위해 검사해야 하는 최소 비트 수인 '토론 질의 복잡도(Debate Query Complexity, DQC)'를 소개한다. 놀랍게도, 우리는 PSPACE/poly(토론이 효율적으로 판정할 수 있는 문제들의 클래스)가 O(log n)회의 질의만으로 판정 가능한 함수들의 클래스와 정확히 일치함을 발견했다. 이러한 특성은 토론이 놀라울 정도로 질의 효율적임을 보여준다. 즉, 매우 복잡한 문제에 대해서도 로그 수준의 검토만으로 충분하다는 것이다. 또한 우리는 모든 입력 비트에 의존하는 함수는 Omega(log n)회의 질의를 필요로 하며, 크기 s인 회로로 계산 가능한 모든 함수는 DQC(f) <= log(s) + 3을 만족함을 입증한다. 흥미롭게도, 이 마지막 결과는 P 클래스 내의 언어에 대해 log(n) + 6의 DQC 하한을 증명할 경우 새로운 회로 하한을 얻을 수 있음을 의미하며, 이는 토론 질의 복잡도를 회로 복잡도 이론의 핵심 문제들과 연결시킨다.

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.