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

Skip to main content

arXiv is now an independent nonprofit!<br>Learn more<br>&times;

Search arXiv

Press Enter to search &middot; Advanced search

-->

Computer Science > Machine Learning

arXiv:2606.26294 (cs)

[Submitted on 24 Jun 2026 (v1), last revised 29 Jun 2026 (this version, v2)]

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

Authors:Alex Iacob, Andrej Jovanović, William F. Shen, Daniel Burkhardt, Meghdad Kurmanji, Nurbek Tastan, Lorenzo Sani, Niccolò Alberto Elia Venanzi, Ambroise Odonnat, Zeyu Cao, Bill Marino, Xinchi Qiu, Nicholas D. Lane<br>View a PDF of the paper titled The Red Queen G\"odel Machine: Co-Evolving Agents and Their Evaluators, by Alex Iacob and 12 other authors

View PDF

Abstract:Self-improving agents are state-of-the-art (SOTA) on agentic coding benchmarks and have recently been extended to general domains. However, their search methods generally assume a stationary evaluation criterion: a fixed verifier, benchmark, or labeled dataset that remains valid as the agent improves. This ignores a central feature of evolution: species adapt as their environments change with them. We aim to bring the same principle to recursive self-improvement, making evaluation part of the improvement loop and opening search to evolving evaluators, adversarial objectives, and dynamic utilities that may surpass static benchmarks. We introduce the Red Queen Godel Machine (RQGM), an evolutionary framework for recursive self-improvement under non-stationary utilities. The RQGM makes this possible through controlled utility evolution: search is organized into epochs with a fixed within-epoch evaluation criterion, while the utility can be updated at epoch boundaries, so self-improvement guarantees hold per epoch as the objective evolves across them. We begin by showing that even on verifiable coding tasks, the RQGM improves test pass rate over the prior SOTA by adding a complementary agent-as-a-judge code-review signal. This signal is cheaper and the RQGM uses 1.35x-1.72x fewer tokens. We then turn to scientific paper writing and reviewing, and Olympiad-level proof writing and grading, where the RQGM improves performance over prior self-improving agents: co-evolved writers reach 1.78x-1.86x higher acceptance rates under a diverse agent-as-a-judge panel, while co-evolved graders reach 9% higher ground-truth accuracy. In paper reviewing, the strongest baseline reviewer over-accepts AI-generated papers at up to 1.91x the human rate. The RQGM corrects this by introducing an adversarial objective that discovers reviewers equally stringent on AI and human work.

Comments:<br>13 pages main text + 21 pages appendix (38 pages total, incl. references); 11 figures (7 main text + 4 appendix); 10 tables (2 main text + 8 appendix). Preliminary preprint; work in progress. Keywords: self-improving agents, learned evaluation, multi-agent systems, auto-mated scientific discovery, controlled utility evolution, co-evolutionary search, autoresearch

Subjects:

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA); Neural and Evolutionary Computing (cs.NE)

ACM classes:<br>I.2.6; I.2.8; I.2.11

Cite as:<br>arXiv:2606.26294 [cs.LG]

(or<br>arXiv:2606.26294v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.26294

Focus to learn more

arXiv-issued DOI via DataCite

Submission history<br>From: Alex Iacob [view email]<br>[v1]<br>Wed, 24 Jun 2026 18:38:26 UTC (1,058 KB)

[v2]<br>Mon, 29 Jun 2026 17:13:25 UTC (1,116 KB)

Full-text links:<br>Access Paper:

View a PDF of the paper titled The Red Queen G\"odel Machine: Co-Evolving Agents and Their Evaluators, by Alex Iacob and 12 other authors<br>View PDF<br>TeX Source

view license

Current browse context:

cs.LG

next >

new<br>recent<br>| 2026-06

Change to browse by:

cs<br>cs.AI<br>cs.MA<br>cs.NE

References & Citations

NASA ADS<br>Google Scholar

Semantic Scholar

export BibTeX citation<br>Loading...

BibTeX formatted citation

&times;

loading...

Data provided by:

Bookmark

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)

Related Papers

Recommenders and Search...