The Red Queen Gödel Machine: Co-Evolving Agents and Their Evaluators

3줄 요약

1. 케임브리지 ML Systems Lab과 NVIDIA·Flower Labs·MBZUAI·Inria 공동 연구진이 2026년 6월 arXiv에 올린 프리프린트다. 자기 개선 에이전트가 기대는 평가 기준이 탐색 내내 고정돼 있다는 점을 문제로 삼는다.
2. Red Queen Gödel Machine(RQGM)은 탐색을 에폭으로 나눠 에폭 안에서만 평가자를 얼려 두고, 에폭 경계에서 더 나은 도전자로 갈아 끼운다. 교체된 평가자가 매긴 기록만 선택적으로 지우기 때문에 에폭마다 기존 자기 개선 보장이 그대로 성립한다.
3. 검증 가능한 코딩에서 이전 최고 성적을 더 적은 토큰으로 넘었고, 벤치마크가 없는 논문 쓰기·증명 쓰기에서도 고정 평가자 기준선을 앞섰다. 심사자가 AI가 쓴 논문을 더 잘 받아주는 편향은 적대적 목표를 얹어 교정했다.

무엇을 문제로 보았나

자기 개선 에이전트는 스스로의 코드를 고치고, 외부 효용 신호가 개선됐다고 말하는 변종만 남기는 방식으로 성장한다. Darwin Gödel Machine과 Huxley Gödel Machine이 이 방식으로 오픈소스 코딩 에이전트의 최고 성적을 세웠고, HyperAgents가 그 범위를 코딩 밖으로 넓혔다.

문제는 그 효용 신호가 언제나 루프 바깥에 고정돼 있다는 것이다. 저자들은 이를 생물 진화와 대비한다. 자연에서 종은 멈춰 있는 환경을 최적화하지 않는다. 경쟁자가 함께 변하기 때문에 제자리에 머물려면 계속 달려야 한다. 논문 제목의 붉은 여왕은 1973년 Van Valen의 가설에서 왔다.

고정된 평가는 세 자리에서 자기 개선을 막는다. 목표 과제에 직접 대응하는 벤치마크가 아예 없는 경우가 첫째다. 논문 쓰기와 증명 쓰기가 그렇고, 반대로 논문 심사와 증명 채점에는 정답 데이터가 있다. 평가가 느리거나 정보량이 적은 경우가 둘째, 에이전트가 좋아질수록 벤치마크가 포화하거나 보상 해킹에 뚫리는 경우가 셋째다.

에폭 안에서만 얼려 두는 방식

RQGM이 이전 시스템에 더한 것은 네 가지다. 아카이브의 각 노드가 단일 에이전트가 아니라 여러 역할이 함께 사는 작업 공간이라는 점, 평가자 자신이 학습되는 에이전트라는 점, 탐색을 이끄는 효용 함수가 지정된 경계에서 바뀔 수 있다는 점, 그 경계에서 평가자가 교체될 수 있다는 점.

핵심 장치는 저자들이 통제된 효용 진화(controlled utility evolution)라고 부르는 규칙이다.

• 탐색은 에폭으로 쪼개진다. 한 에폭 안에서는 평가자 하나가 얼어 있고 모든 과제 에이전트를 채점한다. 그 구간의 효용 신호는 정지 상태다.
• 그동안 도전자 평가자들은 과제 에이전트와 같은 코드베이스에서 함께 진화하고, 따로 떼어 둔 정답 데이터 위에서 채점된다.
• 에폭 경계에서 도전자는 그 정답 앵커 위에서 현직을 통계적으로 앞설 때만 자리를 넘겨받는다. 판정 기준은 과제 에이전트 선택에 쓰는 것과 같은 ε-best-belief 점수이며, 동점이면 현직을 남겨 불필요한 삭제를 피한다.
• 교체가 일어나면 선택적 삭제(selective erasure)가 뒤따른다. 물러난 평가자에게 의존하던 효용 기록만 지우고 나머지는 보존한다.

이 구조 덕분에 에폭 하나하나가 기준이 고정된 탐색 문제가 되고, HGM의 수렴 보장이 에폭 단위로 그대로 적용된다. 대신 목표 자체는 경계를 넘을 때마다 바뀔 수 있다.

삭제 비용은 체크포인트를 지수 간격으로 두어 통제한다. 매 평가마다 효용 전이를 허용하면 삭제·재평가에 노출되는 기록 수가 예산의 제곱으로 늘지만, 지수 간격에서는 예산에 선형으로만 늘어난다. 오래된 노드는 나중에 탐색이 다시 찾아올 때만 재채점하고, 캐시된 출력을 재사용해 과제 에이전트를 다시 부르지 않는다.

검증기가 있는 자리에서도 값이 있었다

첫 실험은 정답이 있는 영역에서 학습된 평가가 무슨 소용인지 묻는다. Polyglot 코딩 과제에서 코더 옆에 코드 리뷰어를 함께 진화시켰다. 리뷰어는 CRAVE(승인·거절된 풀 리퀘스트 데이터셋)에 앵커를 두고, 생성 시점에 각 패치를 채점한다.

결과는 held-out 통과율 71.7%로, 이전 최고인 HGM-H의 69.9%를 넘었다. 토큰은 오히려 1.35배에서 1.72배 적게 썼다. 코딩 에이전트를 여러 턴 돌려 테스트를 실행하는 것보다 리뷰어를 한 번 부르는 쪽이 싸기 때문이다.

토큰이 줄어든 또 하나의 이유를 저자들은 메타 에이전트가 어디를 고치는지에서 찾는다. Polyglot 실행에서 채택된 패치의 90%는 코더와 리뷰어가 함께 쓰는 공용 기능이나 인프라를 건드렸다. 역할별 코드를 고친 것이 아니다. 편집 한 번이 두 역할을 동시에 밀어 올린다.

채점할 정답이 없는 영역

논문 쓰기와 올림피아드 증명 쓰기에는 산출물을 직접 채점할 벤치마크가 없다. 저자들은 각각 논문 심사, 증명 채점과 짝지어 앵커를 붙였다. 논문 심사는 APReS의 accept/reject 결정에, 증명 채점은 IMO-GradingBench의 인간 채점에 앵커를 둔다. 증명은 그 에폭의 채점자가 7점 만점을 줄 때만 통과로 본다.

논문 쓰기 결과는 네 심사자로 구성된 고정 패널로 채점했다.

증명 쓰기는 더 어려웠다. 같은 계산량에서는 RQGM 제너럴리스트가 HGM-H와 동률이고, 차이는 더 긴 탐색에서 벌어진다.

RQGM 스페셜리스트는 평균 점수와 Pass@6에서 IMO 2025 금메달 수준의 수작업 파이프라인 IMO25를 앞섰지만, 만점만 세는 Pass@7에서는 뒤진다. 거의 완성된 증명(7점 중 6점)을 더 많이 찾아낸 결과다. 저자들은 이 격차를 예산 문제로 본다.

평가자가 바뀔 때 순위가 어떻게 되는가

평가자가 강해지면 개체군이 단단해진다는 가설이 성립하려면, 교체가 두 가지를 동시에 해내야 한다. 새 기준으로 아카이브 순위를 실제로 다시 매겨야 하고, 그러면서도 강한 계보 하나는 살아남아야 한다. 매번 처음부터 다시 시작하면 진전이 없다.

교체 전후 순위의 스피어만 상관은 세 영역 모두에서 1보다 한참 아래로 내려앉고, 평가가 쌓여도 옛 순서로 돌아가지 않는다. 삭제를 끄고 낡은 점수를 그대로 둔 대조군에서는 상관이 0.90 근처에 머문다. 새 기준이 순위에 손을 대지 못한다는 뜻이고, 선택적 삭제가 있어야 효용 전이가 탐색을 이끈다는 증거다.

동시에 상위 8개 노드는 교체 때마다 구성원이 갈리는데, 우승 계보만은 온전히 살아남는다. 커리큘럼이 개체군을 흩는 대신 안정된 등뼈를 중심으로 끌어올린다는 것이 저자들의 해석이다. 이 글의 표지 그림이 그 아카이브다. 붉은 선이 살아남은 계보이고, 주황 고리는 상위권으로 올라오거나 밀려난 노드다.

심사자의 편향을 목표에 넣기

두 학습 평가자는 성격이 갈렸다. 증명 채점자는 참조 해답과 그 단계를 보고 판정하므로 표면 그럴듯함에 흔들릴 여지가 적다. 공진화만으로 충분히 좋아졌고, IMO-GradingBench 정확도에서 고정 기준선과 HGM-H 채점자를 모두 앞서면서 스페셜리스트 시점 기준 3배 적은 탐색 비용을 썼다.

논문 심사자는 반대였다. 참조 답이 없으니 논문을 그 자체로 판단해야 하고, 여기서 LLM 심사자의 알려진 약점인 자기 선호 편향이 드러난다. AI가 쓴 글을 사람이 쓴 글보다 더 쉽게 받아들이는 성향이다. HGM-H 심사자는 AI 생성 논문을 사람 논문의 1.42배에서 1.91배 비율로 수락했다. APReS의 accept/reject 비율이 관대한 심사자에게 유리하게 짜여 있어서, 편향과 벤치마크 정확도가 같은 방향으로 끌어당긴다.

RQGM은 에폭 경계를 이용해 이 목표를 바꾼다. 교체가 일어나면 물러난 심사자가 수락했던 AI 생성 논문들이 적대적 표본 풀이 되고, 다음 에폭은 그 표본을 거절하는 심사자에게 추가 점수를 준다. 평가자 교체 자체는 여전히 APReS에 앵커를 둔다.

그렇게 나온 심사자는 원래 벤치마크 정확도를 일부 잃는다. 설계상 당연한 대가다. 얻은 것은 보정이다. AI가 쓴 논문과 사람이 쓴 논문을 비슷한 비율로 받아들이면서 정답 정확도 80%를 유지한다. 그리고 이 까다로운 심사자가 위 표의 작성자 성적을 끌어올렸다. 평가자와 생성자가 따로 진화했다면 작성자가 심사자를 뚫었을 것이라는 게 저자들의 설명이다.

비용은 어디서 나오는가

탐색 비용의 주된 항목은 확장이 아니라 평가였다. 메타 에이전트가 노드를 편집하는 확장 호출은 전체 비용의 20% 정도에 그친다.

그래서 저자들은 메타 에이전트만 GPT-5.5(low)로 두고 탐색 중 과제 에이전트 호출을 더 싼 Nemotron 3 Ultra로 돌리는 혼합 구성을 시험했다. 논문 심사 영역에서 가격 환산 탐색 토큰이 13.0배 줄었고, 최종 평가 성능은 GPT-5.5 단일 구성에 근접했다. 저자들은 이 이점이 영역을 탄다고 본다. 과제 에이전트의 기반 모델이 그 영역에 부족하면, 예컨대 새 증명을 구성해야 하는 자리라면, 확장들의 품질 차이가 흐려져 오히려 비용이 늘 수 있다.

저자들이 인정한 한계

두 가지가 본문에 명시돼 있다. 첫째, 평가자의 품질은 앵커를 넘지 못한다. 약하거나 편향된 앵커는 쓸모없는 평가자를 낳는다. 둘째, 이론적 보장이 에폭 안에서만 성립한다. 에폭을 가로지르는 개선은 앵커 위 ε-best-belief 점수를 올린 평가자만 승격한다는 규칙이 떠받칠 뿐이다.

저자들 스스로 이번 판을 예비 조사라고 부른다. 탐색 지평이 짧고, SWE-bench는 실행 시간 때문에 이번 판에서 빠졌다. 본문 실험은 GPT-5.5(low)로 수행했다.

가장 눈여겨본 것은

앵커를 어떻게 다루는지였다. 평가자를 무제한 진화시키면 벤치마크를 떠나 표류할 것이고, 앵커에 묶어 두면 앵커의 결정 경계를 넘지 못한다. 저자들은 둘 중 하나를 고르는 대신 층을 나눈다. 앵커는 표류를 막는 난간으로 두고, 벤치마크가 규정한 적 없는 방향은 그 위에 얹는 목표로 만든다.

적대적 심사자가 그 첫 사례다. APReS는 사람과 기계가 쓴 글을 가르는 경계를 정의한 적이 없다. 그 경계는 진화 과정이 스스로 찾아냈고, 앵커 정확도는 대체로 유지됐다. 정답이 있는 데이터가 평가자를 훈련시키는 대상이 아니라 평가자가 미치지 않았음을 확인하는 안전장치로 물러앉은 셈이다.

한 가지가 계속 걸린다. 작성자에게 더 까다로운 심사자를 붙이면 작성자가 좋아진다는 결과는 우리가 심사자에게 무엇을 원하는지 되묻게 한다. 이 논문의 적대적 심사자는 APReS 정확도를 잃고도 채택됐다. 벤치마크 점수가 아니라 그 신호를 받는 쪽이 얼마나 자라는지로 평가자를 평가한 것인데, 그러면 좋은 평가자란 무엇인지가 다시 열린 질문이 된다.

출처

Alex Iacob, Andrej Jovanović, William F. Shen 외 10인 (University of Cambridge, NVIDIA, Flower Labs, MBZUAI, Inria). “The Red Queen Gödel Machine: Co-Evolving Agents and Their Evaluators”. arXiv:2606.26294 [cs.LG], v1 2026년 6월 24일, v2 2026년 6월 29일.

원문: https://arxiv.org/abs/2606.26294

본문 그림은 원 논문의 Figure 1·2·6과 Figure 4의 일부를 인용했다.