Who Evaluates the Evaluator?: The Red Queen Gödel Machine

Authors: Alex Iacob^1,*, Andrej Jovanović^1,3,*, William F. Shen^1,*, Daniel Burkhardt², Meghdad Kurmanji¹, Nurbek Tastan⁴, Lorenzo Sani^1,3, Niccolò Alberto Elia Venanzi², Ambroise Odonnat⁵, Zeyu Cao¹, Bill Marino¹, Xinchi Qiu¹, Nicholas D. Lane^1,3.

¹ University of Cambridge · ² NVIDIA · ³ Flower Labs · ⁴ MBZUAI · ⁵ Inria
^* Equal contribution.

Recursively self-improving AI systems have recently crossed over into mainstream conversation (e.g., these articles in the The Economist and WSJ)

At a first glance, one might assume that such systems would be able to bootstrap themselves indefinitely. If you have ever run one, however, you know that they tend to improve for a while before ultimately plateauing, and that where they plateau is generally determined by two factors: (a) how good the system is and (b) how well you measure “improvement.”

Take coding. An agent edits its own code, runs the test suite using the number of passed tests as a score, keeps the version that passes more tests, and repeats. The recent systems that do this, the Darwin- and Huxley-Gödel Machines, set the open-source state of the art on agentic coding exactly this way. HyperAgents, meanwhile, pushed the same idea past coding into other domains by having a meta coding agent responsible for editing domain agents. All in all, boils down to: if you give the self-improvement loop a clear test and enough compute then it gets better.

A self-improving agent can only get as good as the test that scores it. The test does not merely measure progress, it defines it, so the efficacy of the test becomes a ceiling the agent cannot climb past.

Why? The loop only keeps what scores higher, so the agent becomes a student who studies only for a particular exam: if the exam is easy, it aces it and stops, because acing it was all “improvement” ever meant. We see this time and time again at the frontier of AI development, where each new benchmark from the big labs saturates within months and the scores pile up at the top, and the field spends real effort building harder benchmarks because the old ones can no longer tell the best models apart.

As an example: OpenAI’s GPT-5 line and Anthropic’s Claude are nearly tied on the standard coding benchmarks, and the community’s feelings about which is the better service is equally as mixed. Two new, harder benchmarks were built this year to separate these SOTA AI systems: DeepSWE, which rewrites tasks so they cannot be memorized, favors GPT-5.5, while FrontierCode, which asks whether the code is mergeable rather than just passing, favors Claude. Which model is better for you comes down to which benchmark you deem to be superior.

This is what we saw in our own experiments too. When we held on a fixed evaluation procedure, letting the search run long, it stalled. Once the population is strong enough, every candidate looks about the same. Who is the best? No useful signal.

This led us to the core question of this work: what if the thing doing the measuring improved too?

We will now commit the cardinal sin common to all Computer Scientists and bring previous findings of the natural sciences into this discussion via analogy. In 1973, Leigh Van Valen noticed that species do not evolve toward some fixed standard of fitness. They evolve against each other. A predator gets faster, so its prey gets faster, so the predator has to get faster again. He called it the Red Queen hypothesis, after the line in Through the Looking-Glass: “it takes all the running you can do to keep in the same place”.

Hence, why we built and named our system the Red Queen Gödel Machine (‘RQGM’). Instead of improving an agent against a fixed test, we let the evaluation evolve alongside the agent. As the agent gets better, the evaluation also gets harder, and the bar keeps rising.

Stated like that, the nonchalant nature of the proposal should worry you. The whole reason the fixed-test loop works is that the target sits still long enough for “improvement” to mean something. Let the target wander and “improvement” stops meaning anything. And in following the evolutionary analogy to its logical conclusion, you have traded a evolutionary ceiling for a system with no floor. Poor Pink Panther.

Source: MakeAGif.

Now, the problem is not whether to let the evaluation move, but how to move it without losing the floor. What we have settled on as our answer to this question is inspired by curriculum learning. Think about how you would teach someone. You do not hand a beginner the final exam on the first day. You give them a level they can make progress on, hold it steady while they climb it, and only then raise the difficulty once they have mastered the lesson. The raising is the point, but so is the holding. This is the basis of many models in skill mastery and education, for example Bloom’s Mastery Learning.

We will now go into the technical details of the implementation. If you choose to stop here the message you should walk away with is that:

The evaluation of any self-improving system should be systematically and automatically improved to keep up with the capabilities of said system.

Now for the technical explanation, here is a diagram generally showcasing the ‘RQGM’ system:

And here is the whole loop in about as much Python as fits neatly on a screen, most of which is building directly upon the previous algorithm from the Huxley Gödel Machine. The real system has more moving parts, primarily to handle concurrency and generality, but nothing essential is missing from this. Starting with the outer structure, whose entire purpose is to co-evolve evaluators, agents that produce a score, together with actual agents that perform tasks.

def search(seed, budget, checkpoints):
    archive, evaluators, n = [seed], freeze_incumbents(), 0
    while n < budget:
        stop = min([c for c in checkpoints if c > n] + [budget])
        n = run_epoch(archive, evaluators, n, stop)    # evaluators stay fixed inside
        maybe_replace_evaluators(archive, evaluators)        # the only place they change
    return best_belief_node(archive)

freeze_incumbents determines the set of evaluators that will not change until the next checkpoint. run_epoch does the actual search against those frozen evaluators, looping the step function below until it reaches the checkpoint. maybe_replace_evaluators is the only place an evaluator can change. At the end, we return the agent we trust most, which I will come back to.

A single step either grows the tree or tests a node already in it.

def step(archive, evaluators, n):
    if expand_gate(archive, n):               # explore: grow the tree
        parent = sample_by_cmp(archive)       # Thompson sampling over clade scores
        child = edit_workspace(parent)        # an agent edits its own code into a variant
        if valid(child): archive.append(child)
    node = sample_by_cmp(archive)             # exploit: pick a node to test
    role, task = least_measured(node)         # balance attention across roles and tasks
    record(node, evaluate(node, role, task, evaluators))   # the frozen evaluator scores the node

Two components are doing the critical work here. The first is how we pick nodes. Following the Huxley-Gödel Machine, we do not score an agent by how well it does on its own, but by how well its whole subtree of descendants does, thus accounting for self-improvement edits that do not immediately raise benchmark scores. The technical term used in the paper for this score (also borrowed from Huxley-Gödel Machine) is Clade Metaproductivity (CMP). sample_by_cmp then picks nodes roughly in proportion to how good they look under that score, using Thompson sampling, which is a principled way to spend most of the budget on the promising branches via exploitation while still occasionally checking the rest for exploration. We then introduce the second component: whatever score comes back is produced by the frozen evaluator for this epoch, so within an epoch the target never moves and we can provide per-epoch convergence guarantees.

Now, let’s focus on the part that makes it a curriculum and not a single fixed search: replacing the evaluator.

def maybe_replace_evaluators(archive, evaluators):
    for slot in evaluators:                       # one slot per learned evaluator
        field = [slot.current] + challengers(archive, slot)
        winner = max(field, key=lambda e: best_belief(e, slot.ground_truth))
        if winner is not slot.current:            # ties keep the incumbent
            slot.current = freeze(winner)
            erase_records(archive, slot)          # drop every score the old one gave
            recompute_clade_scores(archive)       # let the new ranking take hold

For each evaluator, we line up the current one against challengers the search has bred, and score them all on the ground-truth anchor, a fixed held-out set of real examples with known answers. best_belief is a deliberately cautious selection mechanism: instead of a candidate’s raw accuracy on the anchor, it takes a lower confidence bound, so a challenger is promoted only when we are fairly sure it is statistically better. The anchor is the metaphorical floor we discussed when opening this blog post. Of course, one can imagine a variety of composite objectives here, including ones that drop the benchmark as the sole target (for example, adversarial objectives); however, we believe that the ground truth must remain, providing part of the selection criterion to stop the system from diverging.

If a challenger wins, we do the step that turned out to matter most: we erase every score the old evaluator produced. Keeping them would leave the search ranking agents by judgments the new evaluator never made. For example, in a control experiment that kept the old scores, a new evaluator barely moved the ranking, while erasing the dependent scores let each new evaluator re-rank the population and change the search trajectory. Crucially, one winning lineage still persisted across replacements, so a stricter evaluator sharpens the search rather than restarting it under an unrelated objective.

This mechanism, while necessary for our convergence guarantees to hold, brings significant costs. Every replacement forces some old nodes to be re-evaluated under the new evaluator to bring them back to the same level of information they had prior to the replacement. If you allowed a swap after every single evaluation, those re-evaluations would pile up quadratically. So swaps happen only at checkpoints, and the checkpoints are spaced out exponentially with the following exponential_checkpoints function producing the checkpoints list which goes into the main algorithm.

def exponential_checkpoints(budget, ratio=2, start=1):
    points, c = [], start
    while c < budget:
        points.append(c)
        c = int(c * ratio)      # gaps grow, so swaps get rarer as the run goes on
    return points

The frequency at which evaluators are swapped reduces as the run goes on, which keeps the total re-scoring work linear in the budget instead of quadratic. This also has a side benefit that the later, better evaluators get to shape the search for longer.

Three things follow from all this that a static benchmark cannot give you.

The first surprised us, because it shows up even where verification already exists. On coding, you already have a perfectly good test suite, and adding a cheap learned reviewer on top still helps. Running the tests is expensive, because it means the full multi-turn loop of editing and performing tool calls; asking the reviewer is a single query by default. So the reviewer is a cheap second opinion that catches quality the tests miss, exactly the maintainability that a benchmark like FrontierCode was built to measure, and the search reaches a higher pass rate while spending 1.35 to 1.72 times fewer tokens than the best prior method. What we did not expect was when we looked at where the agent was actually editing its own code, nine in ten of the accepted edits changed machinery shared by both the coder and the reviewer, not code specific to one of them. What does this mean? Co-evolving two roles is not twice the work, because a single good edit tends to improve both at once.

The second is that you can improve on tasks that were never verifiable to begin with. Generally speaking, most tasks that we would want to automate do not some with a simple unit test. No script tells you whether prose is well-written. Under a fixed benchmark, those tasks are closed to self-improvement, because there is nothing to improve on. While you could construct some model or agent to serve as the evaluator by training it on the ground-truth, this just moves the problem one level higher, since that evaluator becomes inadequate as agent ability grows. With an evaluation that co-evolves and stays anchored to ground truth, you can simultaneously hill-climb on your task while making your hills harder to climb, and this is where we see the largest gains.

The table below scores papers from each writer against a fixed panel of four separate reviewers. The co-evolved writers get accepted far more often across the panel, 1.78 times more at the point where the fixed-evaluator baseline runs out of budget, and 1.86 times more for the best writer the search ever finds. We show writers at multiple search token costs in order to enable easy comparisons to the baseline. Generally, we find that previous static-benchmark methods plateau earlier, and thus do not benefit from longer searches.

Writer	Search tokens	Sakana	DGM-H	HGM-H	RQGM (adversarial)	Mean acceptance
HGM-H writer	42.5M	1.0	12.0	64.0	10.0	21.8
RQGM writer 1	44.6M	2.0	43.0	81.0	29.0	38.8 (1.78×)
RQGM writer 2	221.8M	5.0	40.0	86.0	31.0	40.5 (1.86×)

Each of the four middle columns is one reviewer’s acceptance rate, as a percentage, for that writer’s papers. The last column averages across the panel. The ‘RQGM’ (adversarial) column is our own co-evolved reviewer, regularized to be harsh on machine-written text, which is why its acceptances are low across the board. This is exactly the point, which we will elaborate on later. The HGM-H row refers to a version of Hyperagents running with the Huxley Gödel Machine as the search algorithm.

Proof writing is the hard case, and it is worth showing honestly because it does not all go our way. The grader is harder to fool than the reviewer, and the gains arrive only at longer horizons, and the wins are narrow.

Prover	Search tokens	Score (0–7)	Pass@6	Pass@7
Static ImoCode prover	N/A	4.07	55.0%	55.0%
HGM-H prover	21.5M	3.73	51.7%	45.0%
RQGM prover 1	37.9M	3.73	51.7%	45.0%
RQGM prover 2	88.0M	4.33	61.7%	48.3%

The best ‘RQGM’ prover the search finds takes the best mean score and the most near-complete proofs. However, the hand-built Static ImoCode baselines still leads on full-credit proofs. One of our provers only matches the fixed-evaluator HGM-H baseline while the other exceeds it only at the longest horizons we ran. The slow improvement with search horizon indicates to us that outperforming the Static ImoCode prover is likely within reach by just elongating search. As a caveat, the Static ImoCode pipeline uses many handcrafted rules that are generated by human expertise, something that our system does not leverage explicitly.

The third use is how we guide the search for evaluation. If the evaluation’s job is to get harder, you can re-use your agents’ outputs adversarially to harden the decision boundary. We did this to fix a known failure of language-model reviewers: they wave AI-written papers through more readily than human ones. In our setup, this occurred at up to 1.91 times. The fix falls out of the epoch structure almost for free. At an epoch boundary, take the AI-written papers the old reviewer accepted, and in the next epoch reward the new reviewer for catching them. Since blindly rejecting everything would reduce efficacy on the ground-truth data, the search settles on a reviewer that holds AI and human work to a similar standard, which is the harsh ‘RQGM’ (adversarial) column in the writer table.

So far the focus has been on what a co-evolving evaluation can do. It is worth being honest that doing it is expensive, and almost all of that cost is the evaluations rather than the search itself. That points at an obvious lever: run the expensive part on a cheaper model. We tried the split on the paper-reviewing task, using a frontier model, GPT-5.5, only for the meta-agent that proposes edits, and a fast, efficient one, NVIDIA’s Nemotron 3 Ultra, for the agents doing the actual reviewing. It held up. Performance stayed close to running GPT-5.5 everywhere, at 13 times lower search cost in terms of tokens. Of course, this particular saving is specific to paper reviewing, and whether it holds on harder tasks like coding or proofs is something we still need to test.

These are early results, from short search runs, and we want to be careful not to oversell them. The premise of the whole framework is that a longer curriculum compounds the effect, each generation of agents facing a stricter and more discerning evaluator, and that is exactly what we have not yet run at scale. If you are curious about how far we can push this, check back around mid-Autumn as we make our pre-print submission ready.

There is also a limit built into the design of the ‘RQGM’. Holding every replacement to fixed ground truth is what keeps the evaluation from drifting, but it also pins the evaluation to whatever that ground truth can already measure. The way past it is not to climb the anchor harder but to layer richer objectives on top of it, with the anchor demoted from target to guardrail, there only to keep you from wandering off. The adversarial reviewer is the first small example: it roughly holds its ground-truth accuracy while finding a human-versus-machine line the benchmark never drew. How far that goes is the open question, and it is the one we are spending a significant amount of time looking to answer.

That question is the part we would want you to keep, more than any single number. Most of the public conversation about self-improving AI is about the improving: agents that rewrite themselves, loops with no human in them, the runaway staircase. The improving turns out to be the easy half. The hard half is the evaluation: deciding what “improvement” means, and holding that honest while the thing you are measuring does everything it can to look like it is improving.

---

The paper: https://arxiv.org/abs/2606.26294