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

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 do not optimize against a static environment, but 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 Gödel Machine (RQGM)1, an evolutionary framework for recursive self-improvement under non-stationary utilities. We make 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. This mechanism is instantiated by co-evolving the utility itself, using learned evaluators that improve alongside the task agents they guide.

Introduction. Self-improving agents aim to turn local improvements in coding and reasoning into a recursive loop, where each stronger agent can produce better variants of itself. Search methods such as the Darwin and Huxley Gödel Machines [2, 3] recently set the open-source state-of-the-art on agentic coding tasks by editing their own code and retaining variants that improve an external utility signal. HyperAgents [4] then extended this self-improvement beyond coding to task agents in arbitrary domains. Despite this progress, current search methods still depend on stationary evaluation fixed outside the improvement loop, unlike biological evolution, where each species adapts to competitors that evolve in turn. This dependence also constrains self-improvement in three settings: when a target task has no direct benchmark, for example paper writing and proof writing lack one while paper reviewing and proof grading do not [5–7]; when evaluation is slow or weakly informative [8–10]; and when static benchmarks saturate or become vulnerable to reward hacking as agents improve [11, 12].

Discussion / Conclusion. We introduced the Red Queen Gödel Machine (RQGM), a framework in which evaluators co-evolve with the agents they score. Our results suggest two broad principles. First, co-evolving the evaluator alongside the generator enables improvement on hard-to-verify tasks such as paper writing and proof writing, where a fixed benchmark cannot score the artifact directly, mirroring co-evolutionary dynamics observed in nature [1]. Second, co-evolved systems match or exceed fixed-evaluator baselines while often being more token-efficient, which we posit is due to shared expansion costs, more heterogeneous utility signals, and a curriculum-like effect in which a progressively stricter evaluator hardens the population over time.