오윤성 기자

마이크로소프트(MS) 연구원과 독립 연구자가 AI 에이전트를 활용해 31년간 풀리지 않은 KLS 추측의 완전 증명을 제시했다. AI는 100개가 넘는 후보 접근법과 고차 텐서 계산을 탐색했지만, 막힌 길을 버리고 유망한 길을 잇는 판단과 마지막 재귀 논리는 연구진이 맡았다. 비슷한 토큰 예산으로 AI만 반복 투입한 별도 시도는 결론에 닿지 못했다.

MS리서치가 21일 공개한 설명에 따르면 신즈 장(Xinzhi Zhang) 선임연구원과 자오 송(Zhao Song) 독립 연구자는 10월 1일 논문 1차본을 공개한 뒤, 4일(UTC 기준·한국시간 5일) 140쪽 분량의 ‘KLS 상수의 O(1) 경계’ 완전 증명판 v2로 개정했다. 논문은 현재 학술지 동료심사를 거치지 않은 아카이브(arXiv) 프리프린트다.

KLS는 라비 카난·라슬로 로바스·미클로시 시모노비츠가 1995년 제기한 추측이다. 고차원 볼록체나 로그오목 확률분포를 둘로 나눌 때, 최적의 초평면 절단이 임의 형태의 최적 절단면보다 얼마나 불리한지를 묻는다. 차원이 아무리 커져도 그 차이가 일정한 보편 상수배 안에 머문다는 것이 핵심이다.

이는 단순한 도형 문제가 아니다. 절단면의 병목은 무작위보행이 고차원 분포를 얼마나 빨리 탐색하는지를 결정한다. KLS가 성립하면 로그오목 분포 표본추출과 볼록체 부피 계산, 적분, 볼록최적화 알고리즘에서 추측을 전제로 사용하던 여러 결과를 무조건부 정리로 바꿀 수 있다. 다만 이번 연구가 당장 상용 제품이나 알고리즘의 처리 속도를 높였다는 뜻은 아니다.

돌파구는 지난 7월 27일 브레이든 렛윈이 KLS 상한을 차원 \(n\)에 대한 O((log n)^{1/4})까지 낮춘 논문에서 나왔다. 송과 장은 이튿날부터 AI 도구와 함께 100개가 넘는 접근법을 검토했다. 논문은 연구 전체에 GPT-6 Astra와 GPT-5.6 Sol, Claude Fable 5·5.1 등 네 모델을 사용했다고 밝혔고, 후보는 인간과 AI가 함께 만들었지만 무엇을 우선할지는 연구진이 결정했다고 명시했다.

1차본은 KLS 상수의 차원 의존성을 \(O(4^{\log^*(n+2)})\)까지 낮췄지만 완전한 해결은 아니었다. 연구진은 개선된 경계를 같은 논리에 다시 넣는 재귀 정련 전체를 반복하고, 각 단계에서 생기는 손실이 기하급수적으로 줄어 총합이 보편 상수 안에 머문다는 사실을 보였다. 그 결과 차원 의존성이 없는 O(1) 경계에 도달했다.

AI는 후보 탐색과 긴 유도 계산, 원고 작성, 내부 검산을 도왔다. 연구진은 방향 설정과 가지치기, 최종 논증의 조립·검증을 맡았다. MS는 재귀법의 반복 적용과 누적 손실을 상수로 묶는 논리를 연구진의 독창적 기여로 구분했다.

인간 판단의 효과를 보여주는 대조 시도도 있었다. MS에 따르면 연구진은 비슷한 총 토큰 예산으로 여러 AI 모델을 사람의 중간 개입 없이 반복 실행했지만 해법을 얻지 못했다. 다만 정확한 프롬프트와 실행 로그, 모델별 토큰·기여도는 공개되지 않아 재현된 비교실험으로 보기는 어렵다.

우선권과 검증 범위도 구분해야 한다. 피에르 비죌·보아즈 클라르타그·조제프 르에크 팀은 같은 날 송·장 팀보다 약 1시간 50분 먼저 별도 완전 증명을 올렸지만, 송·장 논문 1차본의 판정기준을 핵심 단계로 사용했다. 약 31시간 뒤인 6일에는 크리슈나쿠마르 발라수브라마니안과 시바 카시비스와나탄이 다른 증명을 공개했다.

공개된 Lean 4 형식화도 KLS 명제에 대한 기계 검증을 제공한다. 다만 이는 송·장 팀의 140쪽 원고 전체를 그대로 옮긴 것이 아니라, 송·장 팀의 판정기준과 다른 연구진의 증명 경로를 결합한 별도 형식증명이다. 복수의 증명과 형식 검증은 결과의 신뢰를 높이지만 학술지 동료심사가 끝났다는 의미는 아니다.

이번 성과가 보여준 것은 AI가 수학자를 대체했다는 장면보다 역할 분담의 변화다. AI가 탐색 공간을 넓히고 계산을 밀어붙이는 동안, 인간은 무엇이 진짜 진전인지 판별하고 다음 질문을 설계했다. 모델 단독 성능보다 탐색·가지치기·검증을 엮는 연구 운영체제가 과학적 성과를 가르는 단계로 넘어간 셈이다.