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

기술 요약: 이중 효율적 대화형 증명을 통한 확장 가능한 AI 안전성

문제 정의
AI 모델이 강력한 능력을 갖추게 됨에 따라, AI의 출력이 인간의 의도와 일치하는지 검증하는 것이 매우 중요해졌습니다. 특히 인간의 검증 비용이 지나치게 높은 복잡한 작업(예: 법률 계약서 생성 또는 웹 기반 데이터 검증)의 경우 더욱 그러합니다. 이러한 "확장 가능한 감독(scalable oversight)" 문제를 해결하기 위한 최근의 접근 방식은 **토론(debate)**입니다. 이는 두 개의 경쟁하는 AI 모델이 약한 인간 검증자를 설득하기 위해 토론하는 대화형 증명 모델입니다. 그러나 토론은 두 모델의 능력이 동일해야 하고, 적절한 동기가 부여되어야 하며, 결정적으로 하나는 반드시 진실만을 말해야 한다는 강력하고 잠재적으로 비현실적인 가정을 전제로 합니다. 거짓을 반박하는 것이 거짓을 말하는 것보다 어렵다는 가정은 모든 설정에서 보장되지 않습니다.

나아가, 고전적인 대화형 증명 결과(예: $IP = PSPACE$)는 AI 작업이 오라클(인간의 판단이나 웹과 같은 외부 데이터베이스를 나타내는 "블랙박스" 함수)에 접근할 수 있는 계산으로 모델링되는 경우가 많기 때문에 AI 안전성에 즉각적으로 적용되지 않습니다. 대화형 증명이 오라클을 가진 계산에 대해서는 **상대화(relativize)**되지 않는다(즉, 계산이 오라클에 접근할 때 성립하지 않는다)는 것은 알려진 한계입니다. 상대화가 AI 안전성 관련성 측면에서 필수적이라고 간주됨에 따라, 연구자들은 이 속성을 회복하기 위해 토론 방식에 주목해 왔습니다. 본 논문은 두 번째 토론 프로버(prover) 없이도 상대화가 가능한 단일 프로버(single-prover) 대화형 증명을 구축할 수 있는지 조사합니다.

방법론 및 기술적 접근
저자들은 계산을 오라클 불리언 회로(oracle Boolean circuit) $C^O$로 모델링합니다. 여기서 회로는 표준 논리 게이트와 오라클 $O$에 질의하는 오라클 게이트를 포함합니다. 저자들은 두 가지 특정 설정에 대해 이중 효율적 대화형 증명(정직한 프로버는 다항 시간 내에 실행되고 검증자는 근선형 시간 및 하위 선형 오라클 질의로 실행됨)과 대화형 인자(interactive arguments)(다항 시간 프로버에 대해 건전성이 유지됨)를 제안합니다.

1. 강건한 오라클 계산 (Robust Oracle Computation):

   • 정의: 계산이 $\epsilon$-강건하다는 것은 오라클 질의에 대한 답변 중 최대 $\epsilon$-비율이 틀리더라도 출력이 변하지 않음을 의미합니다. 이는 인간의 판단이 오류가 발생하기 쉽거나 중복성(예: 다수결 투표)이 사용되는 시나리오를 모델링합니다.
   • 비적응적 질의 (Non-Adaptive Queries): 비적응적 질의를 수행하는 회로의 경우, 저자들은 **근접성 대화형 증명(Interactive Proof of Proximity, IPP)**을 사용하여 프로토콜을 구성합니다. 프로버와 검증자는 회로가 실제 문자열에 가까운 질의-답변 문자열 $Q$를 수락함을 보여주는 IPP를 수행합니다. 검증자가 $Q$에 직접 신뢰성 있게 접근할 수 없다는 점을 처리하기 위해, 프로토콜은 질의들이 입력으로부터 올바르게 계산되었는지 검증하는 **이중 효율적 대화형 증명(DEIP)**을 포함합니다.
   • 적응적 질의 (Adaptive Queries): 이전 답변에 따라 이후의 질의가 결정되는 적응적 질의를 수행하는 회로의 경우, 저자들은 체크섬을 이용한 재귀적 접근 방식을 도입합니다. 프로버는 선형 오류 정정 코드를 기반으로 한 **고유 디코딩 체크섬(unique-decoding checksums)**을 사용하여 각 적응 단계의 질의-답변 문자열을 커밋합니다. 프로토콜은 단계별로 진행되며, 질의들이 체크섬 및 이전 단계($i-1$)의 답변과 일치하는지 확인하기 위해 IPP를 사용합니다. 이는 각 IPP의 입력을 "고정"함으로써, 질의의 적응적 특성에도 불구하고 건전성 보장이 유지되도록 합니다.

2. 저차 오라클 (Low-Degree Oracle):

   • 정의: 오라클 $O$는 유한체 위에서 저차 다항식으로 표현 가능합니다. 이는 단순한 머신 러닝 클래스에 의해 학습 가능하거나 저차 확장을 통해 변환된 데이터베이스와 같은 오라클을 모델링합니다.
   • 프로토콜: 프로버는 질의를 인코딩하는 $G$와 답변을 인코딩하는 $F$라는 두 다항식을 **다항식 커밋먼트 스킴(polynomial commitment scheme)**을 사용하여 커밋합니다. 프로버는 $G$와 $F$를 사용할 때 $C(x)$가 수락됨을 증명하기 위해 서리언트 지식 인자(succinct argument of knowledge, Kilian의 프로토콜)를 사용합니다. 그 후 검증자는 무작위 지점 $u$를 확인하여 $F(u) = O(G(u))$인지 확인합니다. **슈바르츠-지펠 보조정리(Schwartz-Zippel lemma)**에 의해, 만약 $F$가 $G$에 대한 오라클 답변을 올바르게 인코딩하지 않는다면, 무작위 지점에서 두 식은 높은 확률로 서로 다르게 나타납니다.

주요 기여 및 결과
본 논문은 오라클 보조 계산을 위한 최초의 상대화 가능한 이중 효율적 단일 프로버 대화형 증명 및 인자를 제시합니다. 결과는 다음과 같습니다.

• 강건한 회로 (비적응적): 검증자 실행 시간 $\tilde{O}(\epsilon \ell D + 1/\epsilon + n)$, 질의 복잡도 $\tilde{O}(1/\epsilon)$를 갖는 통계적 건전성 증명 시스템.
• 강건한 회로 (적응적): $d$-적응적 회로에 대해 검증자 실행 시간 $\tilde{O}(\sigma^d(\epsilon \ell D + 1/\epsilon + n))$, 질의 복잡도 $\tilde{O}(\sigma^d/\epsilon)$를 갖는 통계적 건전성 증명 시스템.
• 강건한 회로 (인자 시스템): 상수 라운드 복잡도 $O(1)$, 질의 복잡도 $O(1/\epsilon)$, 검증자 실행 시간 $\tilde{O}(1/\epsilon + n)$를 갖는 계산적 건전성 인자 시스템. 이는 해시 트리와 서리언트 지식 인자를 활용합니다.
• 저차 오라클 (인자 시스템): 단 한 번의 오라클 질의, 상수 통신 복잡도(보안 파라미터의 다항식 인자까지), 라운드 복잡도 $\tilde{O}(1)$를 갖는 계산적 건전성 인자 시스템.

의의
본 논문은 계산이 오라클 답변의 작은 오류에 강건하거나 오라클이 강력한 대수적 구조(저차)를 갖는 경우, 토론 없이도 상호작적인 검증이 가능하다는 것을 입증함으로써 이러한 결과를 주장합니다. 이는 상대화 가능한 대화형 증명을 달성하기 위해 토론 모델이 반드시 필요하다는 기존의 관점에 도전합니다. 본 연구는 이중 효율적 대화형 증명의 범위를 오라클 보조 계산으로 확장하여, 이론적 암호학과 실질적인 확장 가능한 AI 감독 간의 간극을 메웁니다.

저자들은 모든 오라클 보조 계산에 대한 증명을 구축한 것은 아니지만(이는 이전 연구에 의해 불가능함이 증명됨), 단일 프로버를 사용하여 상대화를 회복할 수 있는 두 가지 자연스러운 설정을 찾아냈다고 언급합니다. 결론적으로, 실세계 작업에서의 강건성에 대한 실험적 검증과 다른 "학습 가능한" 오라클 가정에 대한 탐구 등을 향후 연구 방향으로 제시합니다.