Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2

IMO 기하학 문제 해결률 84% 달성, 인간 금메달리스트 수준 입증

구글 딥마인드가 발표한 연구 논문에 따르면, 알파지오메트리2(AlphaGeometry2)가 국제수학올림피아드(IMO) 기하학 문제 해결에서 평균적인 금메달리스트급 성능을 달성했다.

알파지오메트리2는 2000년부터 2024년까지의 IMO 기하학 문제 50개 중 42개를 해결하는데 성공했다. 이는 평균 금메달리스트의 해결률인 40.9개를 뛰어넘는 수치다. 특히 이전 버전인 알파지오메트리의 54% 해결률에서 크게 향상되었으며, 2024년 IMO에서는 은메달 수준의 성과를 거두었다.

이는 다른 AI 시스템들의 성과를 크게 앞지르는 결과다. OpenAI o1과 Gemini thinking은 단 한 문제도 해결하지 못했으며, TongGeometry DD는 18개, Wu with AG1 DDAR은 21개를 해결하는데 그쳤다. 특히 평균 은메달리스트가 33.9개, 동메달리스트가 27.1개를 해결한다는 점을 고려하면, 알파지오메트리2의 성과는 더욱 주목할 만하다.

도메인 언어 커버리지 66%에서 88%로 확장

알파지오메트리2는 도메인 언어를 확장해 선형 방정식, 각도, 비율, 거리 관련 문제와 물체의 움직임이 포함된 복잡한 문제도 해결할 수 있게 되었다. 이를 통해 IMO 2000-2024 기하학 문제의 언어 커버리지가 66%에서 88%로 향상되었다. 남은 12%는 3D 기하학, 부등식, 비선형 방정식, 그리고 가변적 점의 수를 포함하는 문제들이다. 알파지오메트리2는 11가지 유형의 궤적 문제도 처리할 수 있게 되었다.

시스템은 distmeq, distseq, angeq와 같은 새로운 술어들을 도입해 기하학적 양들 간의 선형 방정식을 표현할 수 있게 되었다. 또한 고정점 플레이스홀더를 사용해 점, 선, 원의 움직임을 표현하는 새로운 술어 구문도 개발했다.

다중 검색 트리로 구현한 혁신적 검색 시스템 SKEST

알파지오메트리2는 여러 개의 검색 트리가 병렬로 실행되며 지식을 공유하는 새로운 검색 알고리즘 SKEST(Shared Knowledge Ensemble of Search Trees)를 도입했다. 각 검색 트리는 보조점 구성을 시도한 후 심볼릭 엔진을 실행하며, 성공하지 못한 경우에도 증명된 사실들을 공유 데이터베이스에 기록해 다른 트리들이 활용할 수 있게 했다. 이 시스템은 고전적인 검색 트리, 다중 보조점 예측 트리, 균일한 분포의 보조점 유형 예측 트리 등 다양한 검색 전략을 결합했다.

이 시스템은 TPUv4를 활용해 모델당 여러 개의 복제본을 서비스하며, 각 검색 트리는 자체 검색 전략에 따라 동일 서버에 쿼리를 보낸다. DDAR 작업자들은 문제들 간에 공유되어 이미 해결된 문제의 컴퓨팅 자원을 다른 문제 해결에 활용할 수 있다.

300배 빨라진 심볼릭 엔진과 최적화된 검색 알고리즘

C++로 구현된 새로운 심볼릭 엔진 DDAR2는 이전 버전보다 300배 이상 빠른 처리 속도를 보여준다. 25개의 IMO 문제에 대한 벤치마크 테스트에서 DDAR1이 평균 1179.57초가 걸린 반면, DDAR2는 3.44711초만에 처리를 완료했다. 또한 빔 크기 128, 빔 깊이 4, 32개의 샘플을 사용하는 최적화된 검색 알고리즘을 도입했다. 이러한 성능 개선은 AMD EPYC 7B13 64 코어 CPU 환경에서 검증되었으며, pybind11을 통해 Python과 연동되어 효율적인 처리가 가능하다. 특히 가우스 소거법의 핵심 연산을 C++로 구현하여 획기적인 속도 향상을 달성했다.

30초 만에 IMO 문제 해결하는 놀라운 성능

2024년 IMO 4번 문제를 단 30초 만에 해결하는 등 인상적인 성과를 보였다. 이 해결책은 IMO 2024 문제선정위원회 의장이자 2회 금메달리스트인 조셉 마이어스로부터 만점을 받았다. 또한 IMO 2013 P3, IMO 2014 P3과 같은 난해한 문제들도 단 하나의 보조점만으로 해결하는 창의적인 접근법을 보여주었다.

자동화된 문제 이해와 다이어그램 생성 시스템 구축

제미니를 활용해 39개의 IMO 문제 중 30개를 자동으로 형식화하는데 성공했다. 다이어그램 생성에서도 큰 성과를 보여, 44개의 IMO 문제 중 41개에 대해 자동으로 다이어그램을 생성했다. 40개의 문제는 40개의 병렬 프로세스를 사용해 1시간 이내에 처리가 가능하며, 가장 복잡한 IMO-2011-6 문제는 3333개의 프로세스로 400분 만에 다이어그램을 생성했다.

다이어그램 생성 과정에서는 Adam gradient descent optimization과 Gauss-Newton-Levenberg method를 결합한 2단계 최적화 방법을 사용한다. 첫 단계에서는 비퇴화 손실을 포함한 평균 제곱 오차를 최소화하고, 두 번째 단계에서는 비선형 방정식의 수치해를 찾는다. 이 방법은 기존의 gradient descent 최적화만 사용할 때보다 일관되게 더 나은 결과를 보여준다.

3억 개의 정리로 훈련된 강력한 언어 모델

약 3억 개의 정리로 구성된 대규모 합성 훈련 데이터셋을 사용했으며, 이전 버전과 비교해 2배 더 큰 무작위 다이어그램을 탐색하고 10배 더 복잡한 증명 단계를 생성할 수 있게 되었다. 단 250회의 훈련 단계(약 2억 개의 토큰)만으로도 50개 중 27개의 IMO 문제를 해결할 수 있는 수준에 도달했다.

시스템은 few-shot 프롬프트를 사용해 Gemini에 5회 쿼리를 보내고 결과를 통합하는 방식으로 자연어 문제를 형식화한다. 실험 결과, 커스텀 토크나이저와 대규모 언어 모델 토크나이저 모두 비슷한 성능을 보였으며, top-k 샘플링에서 temperature=1.0, k=32 설정이 최적의 결과를 산출했다. 이는 낮은 temperature에서는 충분히 다양한 보조 구성이 생성되지 않고, 높은 temperature에서는 잘못된 문법의 출력이 증가하기 때문이다.

멀티모달 추론과 언어 모델의 발전 가능성

알파지오메트리2의 언어 모델은 제미니 1.5를 기반으로 멀티모달 추론 능력을 갖추었다. 다이어그램 이미지를 입력으로 받아 문제를 해결할 수 있지만, 복잡한 다이어그램의 경우 이미지 토큰화 과정에서 공간 정보가 손실되는 한계가 있다. 연구진은 현재 언어 모델이 보조점 생성뿐만 아니라 완전한 증명 생성도 가능하다는 것을 발견했으나, 추론 속도와 환각 현상 해결이 필요해 당분간은 외부 도구의 도움이 필수적이라고 밝혔다.

IMO 쇼트리스트 최난도 문제 해결 성과

알파지오메트리2는 2002년부터 2022년까지 IMO 쇼트리스트에서 선정된 30개의 최난도 문제 중 20개를 해결하는데 성공했다. 이는 시스템이 실제 IMO에 출제된 문제뿐만 아니라 더 광범위한 올림피아드 기하학 문제를 해결할 수 있는 강력한 능력을 갖추었음을 보여준다.

남은 과제: 고급 기하학 문제 해결

IMO 2018 P6, IMO 2023 P6와 같이 반전, 사영기하학, 근축이 필요한 고급 기하학 문제는 여전히 도전 과제로 남아있다. 연구진은 이러한 문제들을 해결하기 위해 하위 문제로 분해하고 강화학습 접근법을 적용하는 추가 연구를 진행할 예정이다.

해당 기사에 인용된 논문 원문은 링크에서 확인 가능하다.

기사는 클로드 3.5 Sonnet과 챗GPT를 활용해 작성되었습니다.