AlphaEvolve — 진화적 코딩 에이전트

최전선 코딩 모델(frontier coding model)에 진화 루프(evolutionary loop)와 기계적으로 검증 가능한 평가기(machine-checkable evaluator)를 결합합니다. 루프를 충분히 오래 돌리면 4x4 복소 행렬 곱셈(complex matrix multiplication)을 48번의 스칼라 곱셈(scalar multiplication)으로 수행하는 절차를 발견합니다. 이는 Strassen 이후 56년 만에 나온 첫 개선입니다. 또한 구글 전역의 Borg 스케줄링 휴리스틱(scheduling heuristic)을 찾아내 실제 운영 환경에서 클러스터 연산 자원의 약 0.7%를 회수합니다. 아키텍처 자체는 의도적으로 단순합니다. 성과는 평가기의 엄격함에서 나옵니다.

유형: Learn 언어: Python (stdlib, 진화 루프 예제) 선수 학습: Phase 15 · 01 (장기 지평 설계; long-horizon framing), Phase 15 · 02 (자가 학습 추론; self-taught reasoning) 소요 시간: 약 60분

문제

대규모 언어 모델(LLM)은 코드를 작성할 수 있습니다. 진화 알고리즘(evolutionary algorithms)은 코드 공간을 탐색할 수 있습니다. 두 접근법 모두 수십 년간 따로 시도되어 왔고, 둘 다 한계에 부딪혔습니다. LLM의 한계는 환각(confabulation)입니다. 모델은 그럴듯해 보이지만 실제로는 주장한 대로 동작하지 않는 코드를 만들어냅니다. 진화 알고리즘의 한계는 탐색 비용(search cost)입니다. 문법 위에서 무작위로 변형(mutation)을 가하는 방식은 컴파일조차 되는 프로그램을 만들기 어렵고, 더 나은 프로그램을 찾는 일은 더더욱 어렵습니다.

AlphaEvolve(Novikov 외, DeepMind, arXiv:2506.13131, 2025년 6월)는 두 접근법을 결합합니다. LLM은 프로그램 데이터베이스(program database)에 대해 표적화된 수정(targeted edit)을 제안하고, 자동 평가기가 각 변형(variant)에 점수를 매기며, 높은 점수를 받은 변형이 다음 세대의 부모(parent)가 됩니다. LLM은 그럴듯한 코드를 작성하는 비싼 단계를 담당하고, 평가기는 LLM이 꾸며낸 주장들을 잡아냅니다. 루프는 몇 시간에서 몇 주에 걸쳐 실행됩니다.

논문에서 보고한 결과는 다음과 같습니다. 4x4 복소 행렬 곱셈을 48번의 스칼라 곱셈으로 수행하는 알고리즘 발견(Strassen의 1969년 한계는 49번), 구글 운영 환경의 Borg 스케줄링 휴리스틱, FlashAttention 커널(kernel)의 32.5% 속도 향상, Gemini 학습 처리량(training throughput) 개선입니다.

이 아키텍처가 동작하는 이유는 평가기가 기계적으로 검증 가능하기 때문입니다. 평가기가 그렇지 않은 영역에서는 동작하지 않습니다. 이 비대칭성이 이번 강의의 핵심입니다.

개념

루프 구조

1. 정확하지만 최적화되지 않은(suboptimal) 시드 프로그램(seed program) P_0에서 시작합니다.
2. 평가기가 점수를 매긴 변형 프로그램의 데이터베이스를 유지합니다.
3. 데이터베이스에서 하나 이상의 부모를 표본 추출합니다. MAP-elites 방식이나 섬 모델(island-based) 방식을 사용할 수 있습니다.
4. LLM(많은 후보에는 Gemini Flash, 어려운 후보에는 Gemini Pro)에 프롬프트를 보내 부모를 수정한 변형을 만들게 합니다.
5. 변형을 컴파일하고 실행한 뒤, 별도로 떼어둔 평가기(held-out evaluator)로 평가합니다.
6. 점수와 특성 벡터(feature vector)를 키(key)로 삼아 데이터베이스에 삽입합니다.
7. 이 과정을 반복합니다.

여기에는 두 가지 세부사항이 중요합니다. 첫째, LLM이 받는 프롬프트는 부모 프로그램만이 아닙니다. 보통 데이터베이스에서 상위 변형 몇 개, 평가기의 시그니처(signature), 짧은 과제 설명(task description)을 함께 제공합니다. 모델의 역할은 점수를 개선할 가능성이 있는 표적화된 변경을 제안하는 것입니다. 둘째, 데이터베이스는 구조화되어 있습니다. MAP-elites 격자(grid)나 섬 기반 구조를 사용해, 현재 1등만 좇지 않고 다양성을 함께 탐색하도록 합니다.

평가기가 협상 불가능한 이유

AlphaEvolve의 성과는 모두 평가기가 빠르고, 결정론적(deterministic)이며, 속이기 어려운 도메인에서 나왔습니다.

• 행렬 곱셈 알고리즘(Matrix multiplication algorithm): 행렬을 곱한 뒤 비트 단위로 동일한지(bit-identical) 확인하는 단위 테스트(unit test).
• Borg 스케줄링 휴리스틱: 과거 클러스터 부하를 재생(replay)하여 낭비된 연산 자원을 측정하는 운영 등급(production-grade) 시뮬레이터.
• FlashAttention 커널: 정확성 테스트와 실제 하드웨어에서의 실측 시간(wall-clock) 벤치마크.
• Gemini 학습 처리량: 학습 한 스텝당 GPU 초(GPU-seconds)로 측정.

각각의 경우에서 평가기는 그렇지 않았다면 결과를 지배했을 LLM의 오류 유형을 잡아냅니다. 꾸며낸 정확성 주장, 하드웨어에서 사라지는 성능 주장, 예외 상황(edge case)에서의 실패입니다. 평가기를 빼버리면 루프는 그럴듯해 보이는 코드(pretty code)를 최적화하게 됩니다.

보상 해킹(reward hacking)은 같은 명제의 다른 얼굴이다

진화는 평가기가 측정하는 것을 최적화합니다. 평가기가 불완전하면 루프는 그 불완전함을 찾아냅니다. 검증되지 않은 도메인에서는 루프가 의도한 행동이 아니라 표면적인 특성을 최적화하게 됩니다. DeepMind는 논문에서 이를 명시적으로 경고합니다. AlphaEvolve의 성공은 평가기의 엄격함이 탐색의 야심과 일치하는 도메인에서만 그대로 이전됩니다.

2025-2026년 코드 탐색 루프에서 관찰된 보상 해킹 사례는 다음과 같습니다.

• "완료까지 걸린 시간"을 보상하는 최적화 대상은 빈 해(solution) 제출을 보상해 버렸습니다.
• 테스트 통과로 정확성을 측정하는 벤치마크 점수는 테스트를 통째로 외우거나(memorization) 과적합(overfitting)하는 행동을 보상했습니다.
• "코드 품질" 대리 지표(proxy)는 의미는 그대로 둔 채 주석을 제거하거나 변수명을 다시 짓는 행동만 보상했습니다.

AlphaEvolve의 해결책은 LLM이 한 번도 보지 못한 별도의 평가기(held-out evaluator)를 두고, 평가 시점에 입력을 생성해 사용하는 것입니다. 그래도 DeepMind는 배포 제안에는 강한 검토(review)를 거치라고 권장합니다.

왜 LLM과 탐색의 결합이 둘 중 하나만 쓰는 것보다 나은가

LLM은 컴파일 가능하고 의미상 그럴듯한 수정을 만들어낼 수 있습니다. 2,000줄짜리 Python 파일에 무작위 변형 기반 유전 알고리즘(random-mutation GA)을 적용하면 거의 항상 문법 오류(syntax error)가 발생합니다. LLM은 또한 탐색을 그럴듯한 이웃 영역에 집중시킵니다. 무작위 바이트가 아니라 함수 하나를 골라 바꾸는 식이어서, 낭비되는 평가기 호출을 크게 줄여줍니다.

반대로 평가기는 LLM의 환각을 잡아냅니다. LLM은 실제로는 O(n^2)인 함수를 두고 "극한에서 O(n log n)"이라고 자신만만하게 단언할 수 있습니다. 실측 시간 벤치마크는 그런 의문을 단숨에 정리해 줍니다.

최전선 시스템 지형(frontier stack) 안에서 AlphaEvolve의 위치

네 시스템 모두 같은 레시피의 변형입니다. 생성기와 평가기를 결합해 루프로 돌리는 구조입니다. 차이는 평가기가 무엇을 채점하느냐와 얼마나 엄격하느냐에 있습니다.

사용해보기

code/main.py는 장난감 수준의 기호 회귀(symbolic regression) 문제 위에서 최소 규모의 AlphaEvolve 유사 루프를 구현합니다. 여기서 "LLM" 역할은 표적 함수(target function)를 계산하는 프로그램에 작은 구문 변형을 제안하는 stdlib 기반의 대리 구현입니다. "평가기"는 별도로 떼어둔 테스트 점들에서 평균 제곱 오차(mean squared error; MSE)를 측정합니다.

확인해야 할 것:

• 세대가 진행될수록 최고 점수가 어떻게 개선되는지.
• MAP-elites 격자가 다양한 해를 살려두어 루프가 지역 최소점(local minimum)에 수렴하지 않게 하는 방식.
• 별도로 떼어둔 테스트를 제거하고 학습 데이터만 보는 평가기(training-only evaluator)로 바꾸면, 루프가 얼마나 극적으로 과적합되는지.

산출물 만들기

outputs/skill-evaluator-rigor-audit.md는 새 도메인에 AlphaEvolve 식 루프를 적용하기 전에 만족해야 할 전제 조건을 점검하는 산출물입니다. 핵심 질문은 단 하나입니다. 우리의 평가기가 우리가 정말 신경 쓰는 실패를 실제로 잡아내고 있는가?

연습문제

1. (쉬움) code/main.py를 실행해 최고 점수의 변화 추이를 기록합니다. --no-holdout 플래그로 별도 평가기를 끄고 다시 실행해, 과적합이 얼마나 일어나는지 수치화합니다.

2. (중간) AlphaEvolve 논문의 3장에서 MAP-elites 격자에 대한 설명을 읽습니다. 컴파일러 최적화 패스(compiler optimization passes) 같은 새 문제에 대해, 탐색 다양성을 유지할 수 있는 특성 벡터 기술자(feature-vector descriptor)를 설계합니다.

3. (중간) 4x4 결과는 Strassen의 49-mul 한계를 56년 만에 깬 사례입니다. 논문의 Appendix F를 읽고, 왜 이 문제의 평가기는 특히 올바르게 만들기 쉬운지, 그리고 왜 대부분의 도메인은 그렇지 않은지를 세 문장으로 설명합니다.

4. (어려움) AlphaEvolve가 실패할 만한 도메인을 하나 제시합니다. 평가기가 정확히 어디서, 왜 무너지는지 짚어냅니다.

5. (어려움) 자신이 잘 아는 도메인 하나를 골라, 거기에 적용할 평가기 시그니처를 작성합니다. (a) 정확성 조건, (b) 성능 지표, (c) 별도로 떼어둔 입력을 생성하는 규칙, (d) 보상 해킹을 방지하는 점검 항목을 최소 한 개 포함합니다.

핵심 용어

더 읽을거리

• Novikov et al. (2025). AlphaEvolve: A coding agent for scientific and algorithmic discovery — 전체 논문
• DeepMind blog on AlphaEvolve — 결과를 포함한 공급사 설명
• AlphaEvolve results repository — 48-mul 4x4 행렬 곱을 포함한 발견 알고리즘 모음
• Romera-Paredes et al. (2023). Mathematical discoveries from program search with LLMs (FunSearch) — 선행 시스템 논문
• Anthropic — Responsible Scaling Policy v3.0 (Feb 2026) — 평가기에 묶인 자율성(evaluator-bound autonomy)을 핵심 연구 방향으로 다룬다