Google DeepMind의 AlphaProof Nexus가 어떻게 56년 된 수학 문제를 해결했는가: Agentic LLM 루프와 Lean 형식 검증 (Formal Verification) 심층 분석

발행일: 2026년 5월 27일 | 핵심 키워드: AI 형식 증명 생성 (AI formal proof generation) | 읽기 시간: 약 15분

목차

1. 수학계를 뒤흔든 300달러짜리 증명
2. 핵심 문제: 왜 LLM은 수학을 풀 때 환각 (Hallucination)을 일으키는가
3. Lean 4의 등장: 결코 틀리지 않는 진리 기계로서의 컴파일러 (Compiler)
4. AlphaProof Nexus: 아키텍처 개요
5. 네 가지 에이전트 (Agents): 각 설계에 대한 심층 분석
6. 진화 엔진 (Evolutionary Engine): Elo, P-UCB, 그리고 그래디언트 (Gradient) 없는 적합도 (Fitness)
7. 수학계를 놀라게 한 결과들
8. 충격적인 발견: 단순한 에이전트도 승리한다
9. 실패 모드 (Failure Modes): 시스템이 여전히 무너지는 지점
10. 엔지니어를 위한 시사점: AI 형식 증명 생성에서의 에이전틱 패러다임 전환 (Agentic Paradigm Shift)
11. 결론: 뉴로-심볼릭 AI (Neuro-Symbolic AI)의 미래

1. 수학계를 뒤흔든 300달러짜리 증명

1970년, 수학자 Paul Erdős와 András Sárközy는 정수의 무한 집합에 대해 겉보기에는 매우 단순해 보이는 질문을 던졌습니다. 즉, 어떤 원소도 더 큰 두 원소의 합을 나누지 않으면서도, 집합의 크기가 √N보다 빠르게 성장할 만큼 충분히 조밀한 집합 A를 구성할 수 있는가 하는 문제였습니다. 연구자들은 56년 동안 이 문제에 매달렸습니다. 부분적인 결과를 발표하고, 범위를 좁혀 나갔지만, 결코 그 간극을 완전히 메우지는 못했습니다.

2026년 5월 21일, Google DeepMind의 AI 에이전트가 단 몇 백 달러의 추론 비용(Inference cost)만으로 하룻밤 사이에 이 문제를 자율적으로 해결했습니다.

이것은 단순한 눈속임이나 정교하게 선별된 벤치마크가 아니었습니다. 이는 AlphaProof Nexus가 단 한 번의 체계적인 스윕(sweep)으로 해결한 9개의 미해결 Erdős 문제 중 하나였습니다. 또한 이 시스템은 온라인 정수 수열 백과사전(OEIS)에서 이전에 증명되지 않았던 44개의 추측을 증명했으며, 대수 기하학(Algebraic geometry) 분야의 15년 된 미해결 문제를 해결했고, 이전에는 아무도 식별하지 못했던 새로운 알고리즘 파라미터 스케줄(Algorithmic parameter schedule)을 발견함으로써 볼록 최적화(Convex optimization)의 미해결 수렴 경계(Convergence bound)를 개선했습니다.

Google DeepMind의 Tsoukalas 등이 작성한 논문 — arXiv:2605.22763 — 은 경쟁 방식이 아닌, 진정으로 미해결된 연구 수학 분야에서 **AI 형식 증명 생성 (AI formal proof generation)**을 대규모로 평가한 첫 번째 사례입니다. 그리고 그 결과 속에는 신뢰할 수 있는 AI 시스템을 구축하는 방식에 대한 여러분의 생각을 근본적으로 바꿔 놓아야 할 엔지니어링적 통찰이 숨겨져 있습니다.

이 포스트는 완전한 기술적 심층 분석(Technical deep dive)입니다. 우리는 아키텍처를 해부하고, 에이전트 설계를 연구하며, 실제 코드 패턴을 살펴보고, 오늘날 프로덕션 AI 시스템을 구축하는 엔지니어들에게 가장 중요한 교훈을 추출할 것입니다.

2. 핵심 문제: 왜 LLM은 수학 문제에서 환각(Hallucination)을 일으키는가

기준점을 먼저 설정해 봅시다. 최신 프런티어 LLM들 — GPT-5.x, Claude Opus 4.x, Gemini 3.x — 은 수학적 추론(Mathematical reasoning) 능력이 놀라울 정도로 뛰어납니다. 이들은 증명의 개요를 작성하고, 접근 방식을 제안하며, 경시대회 수준의 문제를 다루고, 올바르게 보이는 자연어 논증을 생성할 수 있습니다.

여기서 핵심 단어는 보이는 입니다.

LLM이 자연어로 다단계 수학 증명을 작성할 때, 이는 통계적 개연성 (statistical plausibility)에 기반하여 작동합니다. 각 토큰은 이전 문맥을 고려했을 때 발생할 확률이 높은 방향으로 생성됩니다. 논리적 단계 N이 실제로 단계 N-1로부터 도출되는지를 확인하는 내부 메커니즘은 존재하지 않습니다. 모델은 "~임을 쉽게 알 수 있습니다..."라고 작성한 뒤, 미묘하게 — 혹은 치명적으로 — 틀린 주장을 이어갈 수 있습니다. 40단계로 이루어진 증명에서 12단계의 오류는 이후의 모든 과정을 무효화할 수 있으며, 이는 해당 분야의 전문가가 아니라면 누구에게도 명확히 드러나지 않을 수 있습니다.

이는 실제 수학 연구에 LLM을 배치하는 데 있어 가혹한 병목 현상을 초래합니다:

• 검토 비용이 막대합니다. 분야 전문가가 LLM이 생성한 모든 논증의 모든 단계를 검증해야 합니다. 복잡한 증명의 경우, 이 작업에는 며칠 또는 몇 주가 소요될 수 있습니다.
• 오류의 연쇄 반응이 보이지 않습니다. 중간 단계에서의 작은 환각 (hallucination)은 예외를 발생시키지 않습니다. 대신, 여전히 유창하게 읽히지만 수학적으로는 틀린 내용을 생성합니다.
• 신뢰는 이진적이지만, 확신은 연속적입니다. 증명을 부분적으로 신뢰할 수는 없습니다. 모든 단계가 유효하거나, 아니면 전체가 의심스럽거나 둘 중 하나입니다.

이것이 바로 AI 형식 증명 생성 (AI formal proof generation)이 해결하고자 하는 문제이며, AlphaProof Nexus는 이를 위한 현재까지 가장 야심 찬 시도입니다.

3. Lean 4의 등장: 불변의 진리 기계로서의 컴파일러 (Compiler)

Lean 4는 Microsoft Research(현재는 AWS 소속)의 Leonardo de Moura가 개발한 증명 보조 도구 (proof assistant)이자 함수형 프로그래밍 언어 (functional programming language)입니다. Lean에서 수학적 증명은 _프로그램 (programs)_입니다. 정리 (theorems)는 _타입 (types)_입니다. 정리의 증명은 해당 타입의 _항 (term)_입니다. 그리고 결정적으로, Lean 컴파일러는 모든 개별 택틱 (tactic) 단계를 기계적으로 검증합니다.

다음은 간단한 Lean 4 증명의 모습입니다:

-- 정리: 첫 n개 자연수의 합은 n*(n+1)/2와 같다
theorem sum_formula (n : ℕ) : 2 * ∑ i in Finset.range (n + 1), i = n * (n + 1) := by
  induction n with
...

모든 by, induction, rw, simp, ring_nf, linarith는 하나의 택틱 (tactic) — 즉, 기계적으로 검증 가능한 기초적인 증명 단계입니다. 컴파일러는 각 택틱이 실행된 후 현재의 증명 목표 (proof goals) 집합을 추적합니다. 증명이 완료되고 정확하려면, 반드시 남은 목표가 0개인 상태로 이어져야 합니다.

Lean에는 특별한 탈출구인 sorry 택틱이 있습니다. 이는 실제로 증명하지 않고도 대기 중인 모든 목표를 즉시 종료시킵니다. 이는 "나중에 채워 넣겠다"라는 의미를 가진 플레이스홀더 (placeholder)입니다. sorry가 포함된 파일은 컴파일되지만, 해당 정리는 증명된 것이 아닙니다. AlphaProof Nexus의 전체 목표는 증명 본문이 sorry로 대체된 Lean 파일을 가져와서, sorry가 전혀 없는 완전한 버전을 생성하는 것입니다.

-- AlphaProof Nexus의 입력: sorry 플레이스홀더가 포함된 정리
theorem erdos_12i : ∃ A : Set ℕ, IsMultiplicativelyIndependent A ∧
    0 < liminf (fun N => |A ∩ Finset.range N| / Real.sqrt N) := by
...

컴파일러 피드백 루프 (compiler feedback loop)는 핵심적인 아키텍처 프리미티브 (architectural primitive)입니다. LLM이 잘못된 증명 단계를 생성할 때, Lean은 조용히 잘못된 출력을 내보내는 대신 다음과 같은 구조화된 에러 메시지를 반환합니다.

error: tactic 'ring_nf' failed, no progress made
⊢ 2 * (∑ i in Finset.range (n + 1), i + (n + 1)) = (n + 1) * (n + 2)

이 에러에는 정확한 현재 증명 상태, 실패한 택틱, 그리고 남은 목표의 모습이 포함되어 있습니다. 이는 LLM이 다음 턴에서 추론할 수 있는 구조화된 피드백의 노다지입니다. 이는 인간이 논증이 왜 틀렸는지 파악한 후에야 수정할 수 있는 자연어 방식의 증명 검토와는 다릅니다.

4. AlphaProof Nexus: 아키텍처 개요

AlphaProof Nexus는 LLM 호출과 Lean 컴파일러 호출을 교차하여 수행하는 에이전트를 구축하기 위한 _프레임워크 (framework)_입니다. I/O 계약 (I/O contract)은 명확합니다.

입력:

• 증명이 들어가야 할 자리에 sorry가 포함된 정리 문장(theorem statement)이 담긴 Lean .lean 파일
• 에이전트가 수정할 수 있는 코드 영역을 지정하는 EVOLVE-BLOCK 마커
• 에이전트가 변경할 수 있는 표현식(예: 알고리즘 파라미터)에 표시된 EVOLVE-VALUE 마커
• 선택 사항: 자연어 문맥(natural language context), Lean에 인코딩된 도메인 지식(domain knowledge), 관련 Mathlib 보조정리(lemmas)

출력:

• sorry가 제거된 대상 정리의 Lean 증명
• 증명 전략에 대한 자연어 요약

-- 예시: AlphaProof Nexus를 위한 주석이 달린 입력 파일
import Mathlib

...

이 프레임워크는 병렬 서브에이전트(subagents) _풀 (pool)_을 실행하며, 각 에이전트는 독립적으로 증명을 탐색합니다. 이러한 병렬성은 매우 중요합니다. 증명 탐색(proof search)은 매우 비결정론적(non-deterministic)이며, N개의 독립적인 탐색을 동시에 실행하면 계산 예산(compute budget) 내에서 최소 하나가 성공할 확률을 극적으로 높일 수 있기 때문입니다.

모든 에이전트는 기본 LLM으로 Gemini 3.1 Pro를 사용하여 구동되며, 더 저렴한 등급 산정(rating) 및 평가(evaluation) 작업에는 경량화된 Gemini 3.0 Flash가 사용됩니다.

5. 네 가지 에이전트: 각 설계에 대한 심층 분석

AlphaProof Nexus는 정교함이 점진적으로 증가하는 네 가지 에이전트 변체(A부터 D까지)를 정의합니다. 각 에이전트의 설계 결정 사항을 이해하는 것은 여러분의 에이전트 시스템(agentic systems)에 이러한 패턴을 적용하는 데 필수적입니다.

에이전트 A: Ralph 루프 (Baseline)

가장 단순한 에이전트는 논문에서 **"Ralph 루프 (Ralph loop)"**라고 부르는 것을 구현합니다. 이 명칭은 에이전트 AI 엔지니어링 분야에서 전문 용어(term of art)가 될 가능성이 높습니다. 이 패턴은 깔끔합니다:

def ralph_loop(theorem_file: str, llm, lean_compiler, max_episodes: int = 50):
    """
    핵심 에이전트 원시 기능 (agentic primitive): LLM이 증명 단계(proof steps)를 생성하고,
...

핵심 통찰: Lean 컴파일러의 에러 메시지가 다음 턴을 위해 LLM의 컨텍스트(context)로 직접 피드백된다는 점입니다. LLM은 정확히 무엇이 잘못되었는지, 어떤 전술(tactic)에서 문제가 발생했는지, 그리고 현재의 증명 상태(proof state)가 어떠한지를 파악합니다. 이러한 구조화된 피드백은 기본적인 에이전트조차 놀라울 정도로 강력하게 만듭니다. 이는 단순히 자유 형식으로 "다시 시도해봐"라고 반복하는 루프보다 훨씬 더 강력합니다.

각 에피소드는 학습된 교훈을 자연어 요약 형태로 작성하여 Lean 파일 내에 주석으로 추가하며 종료됩니다. 이를 통해 원시 컴파일러 출력값으로 컨텍스트 윈도우(context window)를 가득 채우지 않으면서도, 에피소드 전반에 걸쳐 맥락적 지식(contextual knowledge)을 축적할 수 있습니다.

에이전트 B: 하위 도구로서의 AlphaProof

에이전트 B는 증명기 하위 에이전트(prover subagent)에게 AlphaProof를 호출할 수 있는 능력을 부여함으로써 에이전트 A를 확장합니다. AlphaProof는 올림피아드 수준의 정리 증명(theorem proving)을 위해 Google이 기존에 보유한 강화학습 (RL) 시스템입니다. 증명기가 스스로 처리할 수 없는 하위 목표(sub-goal)를 마주하면, 이를 AlphaProof에 위임합니다:

-- 증명기가 증명을 분해하고 하위 목표를 AlphaProof에 위임함
theorem main_result : ComplexStatement := by
  -- AlphaProof가 RL 탐색을 통해 이 다룰 수 있는 하위 목표를 처리함
...

AlphaProof는 다음 세 가지 신호 중 하나를 반환하며, 이 모든 신호는 구조화된 프롬프트 컨텍스트(prompt context)로 다시 피드백됩니다:

• 증명 발견 (Proof found): 스케치(sketch)에 직접 대입됨
• 반증 발견 (Disproof found): 하위 목표가 _거짓(false)_임을 의미하며, 증명기가 문제를 잘못 분해했음을 알려줌
• 실패 (Failure): AlphaProof가 할당된 예산(budget) 내에서 문제를 해결하지 못함 — 다른 분해 방식을 시도할 것

에이전트 C: Elo 레이팅을 활용한 진화적 개체군

에이전트 C는 AlphaEvolve에서 영감을 얻은 진화적 구성 요소를 도입합니다. 핵심 혁신은 **개체군 데이터베이스 (Population Database)**로, 이는 모든 증명기 하위 에이전트들이 읽고 기여하는 증명 스케치(proof sketches)의 공유 저장소입니다.

과제: 표준적인 진화 알고리즘(evolutionary algorithms)은 _단계적인 적합도 지형(graduated fitness landscape)_을 가정합니다. 하지만 증명 검증(Proof checking)은 이진적(binary)입니다. 즉, sorry가 없는 상태로 컴파일되거나, 그렇지 않거나 둘 중 하나입니다. 따라갈 수 있는 기울기(gradient)가 존재하지 않습니다. 에이전트 C(Agent C)의 우아한 해결책은 저렴한 Gemini 3.0 Flash 평가 에이전트(rating agents) 풀을 사용하여 증명 스케치(proof sketches)의 타당성, 명확성 및 참신함을 일대일(head-to-head)로 심사하는 것이었습니다. 이를 통해 이진 결과로부터 연속적인 대리 적합도 신호(continuous proxy fitness signal)를 생성합니다.

이러한 쌍체 비교(pairwise) 평가는 각 스케치에 대한 **Elo 점수(Elo scores)**로 집계됩니다. 새로운 증명기 에피소드는 (AlphaZero에서 직접 차용한) **P-UCB 공식(P-UCB formula)**을 사용하여 모집단에서 샘플을 추출하며, 높은 Elo를 가진 스케치를 활용(exploitation)하는 것과 아직 충분히 탐색되지 않은 스케치를 탐색(exploration)하는 것 사이의 균형을 맞춤으로써 다양성을 유지합니다.

이러한 연속적인 적합도 대리 신호가 구축됨에 따라, 에이전트 D(Agent D)는 세 가지 모든 기능을 전체 시스템으로 결합합니다.

에이전트 D: 전체 시스템 (Agent D: The Full System)

에이전트 D는 Ralph 루프, AlphaProof 하위 도구 통합, 그리고 진화적 모집단 데이터베이스를 결합합니다. 이는 모든 주요 Erdős 및 OEIS 실험에 사용되었습니다. 가장 강력한 기능은 EVOLVE-VALUE 메커니즘으로, 이는 증명을 동시에 검색하면서 최적의 알고리즘 파라미터(algorithm parameters)를 동시에 발견하는 능력입니다.

-- Agent D: 알고리즘 파라미터와 증명에 대한 공동 검색 (joint search)
-- 이것이 Anchored GDA를 위한 새로운 학습률 스케줄(learning rate schedule)을 발견한 방식입니다.

...

볼록 최적화(convex optimization) 실험에서, 에이전트에게 학습 스케줄에 대한 EVOLVE-VALUE 블록이 주어졌습니다. 에이전트는 단순히 증명을 찾아낸 것에 그치지 않고, 기존에 알려진 것보다 엄격하게 더 나은 O(1/t) 수렴 속도(convergence rate)를 달성하는 새로운 스케줄을 발견했습니다.