새로운 아이디어와 인간 주도 AI로 연구진, 31년 된 수학 난제 해결

Microsoft 연구진, 31년 묵은 수학 난제 'KLS 추측' 해결

마이크로소프트 리서치의 장신즈(Xinzhi Zhang) 연구원과 공동 연구진이 1995년 제기된 고차원 기하학의 핵심 난제인 KLS 추측(Kannan-Lovász-Simonovits conjecture)을 증명했다고 발표했다. 이번 성과는 통계학, 최적화, 알고리즘, 컴퓨터 과학 전반에 영향을 줄 수 있는 근본적 진전으로 평가된다.

수십 년 동안 고차원 공간에서의 계산 난이도에 관한 근본적 질문은 증명되지 않은 채 남아 있었다. 이번 연구는 이 질문에 답을 내놓으며, 과학과 컴퓨팅 전반에서 사용되는 무작위 알고리즘의 효율성을 이해하는 데 있어 주요 이론적 장애물을 제거했다.

KLS 추측은 1995년에 제기되었다. 폭넓은 종류의 고차원 확률 분포에 대해 최적의 평평한 절단면(초평면 절단)이 임의 형태의 최적 절단면과 거의 같은 효과를 내는지를 묻는 질문이다. 보다 정확히 말하면, KLS 추측은 차원의 수와 관계없이 두 값의 차이가 보편적 상수를 넘지 않는다고 예측한다. 이것이 참이라면 고차원 기하학, 확률론, 이론 컴퓨터 과학에 중요한 결과를 가져올 차원 독립적 기하 원리가 확립되는 셈이다. 이러한 절단면의 기하가 무작위 보행(random walk)이 분포를 얼마나 빠르게 탐색하는지를 결정하기 때문에, KLS 추측은 고차원 샘플링 이론에서도 중심적 역할을 한다.

그림 1: 정사면체를 활용한 KLS 추측의 단순화된 시각화

1995년 이후 수학자들은 이 추측이 참일 가능성을 뒷받침하는 증거를 축적해 왔지만, 완전한 증명은 이루어지지 않았다. 이번에 마이크로소프트 리서치의 머신러닝 및 최적화 그룹 소속 장신즈 연구원을 포함한 두 연구자가 KLS 추측을 증명했다. 이들은 도형의 차원이 얼마나 많든 관계없이 이 관계가 고정된 상한으로 성립함을 보였다. 이 연구 이전에 알려진 최선의 결과는 2026년 7월에 확립된 것으로, 차원이 늘어남에 따라 그 상한이 천천히 커지는 것을 허용하는 수준이었다.

이번 연구는 고차원 공간이 기존에 알려진 것보다 더 잘 작동하며, 그 공간을 탐색하는 데 따르는 장애물이 차원이 증가해도 무한히 커지지 않는다는 근본적 기하 원리를 확립했다.

KLS 추측의 중요성은 해결되기 훨씬 전부터 학계에서 인정받아 왔다. 수리과학연구소(MSRI)는 2017~2018년 연간 보고서에서 이를 "고차원 볼록 기하학의 핵심 미해결 문제"라고 불렀다. 사이먼스 연구소(Simons Institute)는 "볼록 기하학에서 가장 중요한 미해결 문제 중 하나"라고 설명했다. 2022년 국제수학자대회(ICM) 회의록에서 로넨 엘단(Ronen Eldan)은 이 추측이 고차원 볼록 기하학 및 계산 기하학에 미치는 광범위한 영향을 지적했다. 퀀타 매거진(Quanta Magazine)은 KLS 추측이 "통계학과 컴퓨터 과학의 여러 질문의 중심에 놓여 있다"고 보도했다.

연구의 기술적 세부 사항을 보면, 연구진은 먼저 2026년 7월의 결과를 개선해 수학적 상한을 더 정밀하게 만드는 데서 출발했다. AI 에이전트와 함께 구조화된, 사람이 주도하는 과정을 통해 연구진은 100개 이상의 후보 접근법을 탐색했으며, 그중 상당수는 고차 텐서를 다루는 긴 계산을 포함했다. 이 과정에서 최종 증명의 토대가 된 새로운 수학적 판단 기준이 도출되었다.

이후 연구진은 이 새로운 기준을 재귀적으로 적용할 수 있음을 발견했다. 개선된 상한을 동일한 논증에 다시 입력하면 더 촘촘한 상한을 얻을 수 있었다. 2026년 10월 1일자 논문 버전에서는 이 과정을 통해 차원에 대한 의존도를 반복 로그 함수(iterated logarithm)까지 줄였다. 이 함수는 극도로 느리게 증가하지만 여전히 차원에 따라 커지므로, 아직 추측을 완전히 해결한 것은 아니었다.

최종 단계는 재귀적 정제를 한 번만 적용하는 대신 전체 과정을 반복하는 것이었다. 이 아이디어는 연구진이 앞서 수행한 선형 계획법의 고속 알고리즘 연구에서 영감을 얻은 것이다. 연구진은 각 단계에서 생기는 작은 오차가 충분히 빠르게 줄어들어 그 총합이 차원과 무관한 보편 상수 이내로 유지됨을 증명했다. 이로써 차원 수에 대한 의존성이 제거되었고, 2026년 10월 4일자 논문 버전에서 증명이 완료되었다. 재귀적 방법, 그 반복적 적용, 누적 오차가 유계임을 보인 증명은 연구자들의 독창적 기여다. AI 도구는 후보 접근법 탐색, 세부 유도 계산, 원고 작성, 내부 증명 점검에 활용되었다. 수학적 방향을 정하고, 유망한 아이디어를 선별하고, 최종 논증으로 조립하고, 증명을 검증한 것은 연구자들이다.

독립적 검증도 이어졌다. 연구진이 완전한 증명을 공개한 같은 날, 별도의 전문가 집단이 병행하여 개발한 완전한 증명을 공개했다. 이들의 연구는 마이크로소프트 논문 첫 버전의 결과를 토대로 했으며, 이를 "증명의 결정적 단계"라고 평가했다. 같은 날 별도로 발표된 세 번째 증명은 밀접하게 관련된 아이디어에 기반한다. 또한 이후 Lean 4 형식화가 공개되었는데, 이는 마이크로소프트 첫 논문의 핵심 기준과 추가 연구를 결합한 것이다. 독립적 증명은 수학에서 가장 강력한 검증 방식 중 하나로, 결과가 단일한 추론 사슬에 의존하지 않음을 보여준다. 이후 대안적 접근법과 형식 검증이 등장한 것은 이 분야가 취약한 기술적 논증이 아니라 실제 근본 원리를 발견했다는 확신을 더 강화한다.

연구진은 증명을 간결하게 줄이고 간소화된 논증을 Lean으로 검증했으며, 최종 검토를 거친 뒤 두 가지를 모두 공개할 계획이다. 이러한 전개들은 상호 보완적인 방식의 확인을 제공한다.

이번 연구는 KLS 추측 증명 과정에서 연구자가 AI를 주도적으로 이끄는 것이 얼마나 강력한지도 보여준다. 연구진은 단일 end-to-end 실행으로 최첨단 모델이나 에이전트에게 복잡한 문제를 통째로 맡기는 대신, 반복적이고 사람이 보조하는 "가지치기(pruning)" 방식의 에이전트 탐색을 사용했다. 여러 에이전트가 하나의 아이디어를 병렬로 변형하며 탐색하면, 연구자가 중간 결과를 검토해 유망하지 않은 방향을 제거하고 가장 유망한 결과를 다음 라운드로 넘겼다. 핵심 돌파구가 나오기까지 약 100개의 연구 경로가 탐색되었다.

프로젝트의 별도 트랙에서는 연구진이 메인 과정과 대략 같은 총 토큰 예산을 들여, 여러 선도적 AI 모델에 같은 문제를 사람의 개입 없이 반복적으로 시도하게 했다. 그러나 이 시도는 목표에 이르지 못했다. 최종 성공은 AI 시스템의 역량과 연구자의 수학적 판단이 함께 작용한 결과였다.

종합하면, KLS 추측의 해결은 고차원 기하학의 핵심 문제를 정리한 것이다. 그동안 이 추측을 가정으로 삼아 제시되었던 여러 결과들이 이제 무조건적으로 진술될 수 있게 되었다. 따라서 이번 증명은 볼록 기하학, 확률론, 이론 컴퓨터 과학 연구에 더 강력한 기반을 제공한다.

이 연구는 신중하게 설계된 인간-AI 협업이 인간의 통찰을 대체하지 않고 오히려 강화하면서도 실질적인 과학적 발견에 기여할 수 있음을 보여준다. 유망한 방향을 식별하고, 개념적 연결을 알아보며, 부분적 통찰이 더 깊은 결과를 가리키는 순간을 알아보는 데 있어 과학적 판단이 여전히 중요하다는 점을 드러낸다.

연구진은 이제 수학 및 이론 컴퓨터 과학 공동체가 결과를 더 쉽게 검토하고 발전시킬 수 있도록 증명을 단순화하고 형식 검증을 확장하고 있다.

감사의 글: 이 연구에 기여한 공동 저자 자오 쏭(Zhao Song)에게 감사드린다. 또한 프로젝트 전반에 걸쳐 유익한 논의를 해준 빅터 레이스(Victor Reis)와 이샤이 메나헴(Ishai Menache)에게도 감사를 표한다.

관련 논문: "An O(1) Bound for the KLS Constant"

연구 분야: 인공지능, 수학