Auditing an AI-Generated Mathematical Proof: A Correction to a Greedy Conditioning Lemma in Quantum Parallel Repetition

이론 컴퓨터 과학의 영역에서 연구자들은 두 명의 플레이어가 서로 떨어져 대화할 수 없는 상태에서, 상을 얻기 위해 자신들의 답변을 조율해야 하는 게임을 연구한다. 이것은 주사위를 가지고 하는 확률 게임이 아니라, 플레이어들이 양자 물리학에서 유래한, 멀리 떨어진 입자들이 즉각적으로 서로에게 영향을 미칠 수 있게 하는 '얽힘(entanglement)'이라는 신비로운 연결을 공유하는 복잡한 퍼즐이다. 만약 이 플레이어들이 이러한 게임을 한 라운드에 여러 번 반복할 때, 확률의 법칙에 따르면 그들이 매번 승리할 수 없다면, 그들이 모두 함께 승리할 확률은 뜨거운 태양 아래서 녹아내리는 눈덩이처럼 급격히 떨어져야 한다. '병렬 반복(parallel repetition)'이라 불리는 이 개념은 양자 통신의 한계와 미래 암호 시스템의 보안을 이해하는 데 있어 초석이 된다. 수년 동안 수학자들은 이러한 확률의 하락이 단순히 가능성에 그치는 것이 아니라, 모든 그러한 게임에 대해 보장된 지수적 감소라는 것을 증명하기 위해 노력해 왔으며, 이는 압박 속에서 양자 세계가 어떻게 작동하는지에 대한 우리의 이해를 공고히 할 결과가 될 것이다.

OpenAI에서 발표한 Ten Advances in Mathematics and Theoretical Computation Science라는 제목의 최근 논문은 마침내 이 오래된 난제를 해결했다고 주장했다. 이 문서는 임의의 유한한 게임을 수행하는 두 얽힌 플레이어를 위해 지수적 병렬 반복 정리에 대한 포괄적인 증명을 제시하며, 게임의 복사본들을 동시에 승리할 확률이 복사본의 수가 증가함에 따라 믿기 힘들 정도로 빠르게 줄어든다고 주장했다. 증명은 특정 논리적 단계, 즉 집중할 작은 게임 라운드 그룹을 선택하는 방법에 의존했는데, 이는 플레이어들이 선택된 라운드들에서 승리한다면 나머지 라운드들에서도 승리할 가능성이 거의 확실하다는 것을 보여주기 위한 의도였다. 이 방법은 "탐욕적 조건화(greedy conditioning)" 과정으로 묘사되었는데, 이는 확률을 끊임없이 확인하고 전략을 조정함으로써 가능성을 좁혀가는 방식이다. 이 논증은 유창하고 정교한 수학적 산문으로 작성되어 양자 세계의 규칙에 대한 깊고 엄격한 검증을 시사하며 매우 타당해 보였다.

그러나 미코와이 시에니키(Mikołaj Sienicki)와 크리슈토프 시에니키(Krzysztof Sienicki)에 의한 이 증명에 대한 세밀한 감사는 그 특정 단계의 논리 속에 숨겨진 결정적인 결함을 발견했다. 연구자들은 전체적인 목표는 옳았지만, 그곳에 도달하기 위해 사용된 메커니즘이 성공과 실패를 측정하는 방식에서 단순하지만 결정적인 오류를 포함하고 있다는 것을 찾아냈다. 원래의 텍text는 남은 라운드들의 평균 승리 확률이 작은 임계값보다 클 때마다 새로운 라운드를 찾는 데 계속 집중하라고 지시했다. 그러나 이 지시는 다음으로 요구되는 행동, 즉 실패 확률이 높은 특정 라운드를 찾는 것과 수학적으로 단절되어 있었다. 증명은 평균적인 성공률이 높다면 반드시 특정 사례의 높은 실패율이 존재해야 한다고 가정했는데, 이는 단순히 논리적 비약이며 사실이 아니다. 평균은 높을 수 있지만 개별적인 실패 확률은 모두 낮을 수 있으며, 이 경우 절차는 유효한 움직임을 찾지 못해 전체 논증이 멈춰버릴 수 있다.

이러한 붕괴를 입증하기 위해, 감사자들은 단 두 번의 게임 라운드로 구성된 간단한 시나리오를 구축했다. 이 예시에서 플레이어들은 두 라운드 모두에서 승리할 확률이 매우 높았으며, 이는 프로세스를 멈추기 위한 임계값을 훨씬 초과했다. 그럼-에도 불구하고, 원래의 증명에 적힌 규칙에 따르면 알고리즘은 높은 실패율을 가진 라운드를 찾는 데 계속 머물러야 했다. 절차는 이미 원하는 결론에 도달했음에도 불구하고, 중단 조건이 충족되지 않아 빈 허수아비 속에서 바늘을 찾으려는 듯 루프에 빠져 있었다. 이 반례는 인쇄된 절차가 근본적으로 고장 났으며, 플레이어들이 이미 압도적으로 승리하고 있는 특정한 경우에서도 제대로 작동할 수 없음을 증명했다.

감사자들은 전체 증명이나 주요 정리를 폐기하지 않았다. 대신, 그들은 논리가 실패한 정확한 지점을 식별하고 국소적인 수정을 제안했다. 그들은 탐색을 계속하기 위한 조건이 반전되어야 함을 보여주었다. 즉, 프로세스는 높은 평균 성공률이 아니라 높은 평균 실패율을 찾아야 한다는 것이다. 이 하나의 논리적 스위치를 전환했을 때, 렙마(lemma) 자체의 증명은 통과되었다. 교정된 방법은 필요한 라운드들을 성공적으로 식별했고, 승리 확률이 높게 유지됨을 보장했으며, 해당 장에서 이후에 사용되는 정량적 파라미터들을 보존했다. 그러나 감사자들은 이 수리가 메인 병렬 반복 정리에 대한 독립적인 검증으로 읽혀서는 안 된다고 명시적으로 밝혔다. 샘플링 가능성(sampleability), 상관 샘플링(correlated-sampling), 상태 정렬(state-alignment), 그리고 라운딩(rounding)에 관한 후속 논의들은 나머지 증명이 성립하는지를 확인하기 위해 전문가의 검증이 필요한 별개의 문제로 남아 있다.

이 사건은 인공지능이 생성한 수학을 검증할 때 직면하는 도전 과제들에 대해 강력한 경종을 울린다. AI 논증의 성공적인 부분들은 양자 상태와 확률에 관한 복잡한 아이디어들을 결합하여 매우 정교하고 설득력 있게 엮어냈으며, 권위 있는 방식으로 들렸다. 그러나 오류는 심오한 이론의 미묘한 실패나 복잡한 계산의 오류가 아니었다. 그것은 보완적인 사건들 사이의 기본적인 역전, 즉 인간 수학자라면 눈길 한 번으로도 잡아낼 수 있었을 승리와 패배의 혼동이었다. 감사는 타당해 보이는 수학적 논증이, 비록 궁극적인 결론은 참일지라도, 절차를 무효화하는 작고 국소적인 실수를 숨길 수 있음을 보여준다. 교정된 증명이 이제 특정 렙마를 뒷받침하게 되었지만, 감사자들의 작업은 거기까지다. 그들은 부서진 기계의 톱니바퀴를 고쳤을 뿐, 전체 엔진을 검증한 것은 아니다. 양자 샘플링 가능성과 최종 라운딩 논증에 관한 더 깊은 질문들은, 나머지 기계가 수리된 부품처럼 매끄럽게 돌아가는지 확인하기 위한 전문가의 검증을 기다리며 여전히 열려 있다.