Red Queen Gödel Machine

Definition

The Red Queen Gödel Machine (RQGM) is an evolutionary self-improvement framework in which learned evaluators (judges) are co-evolved alongside the task agents (generators) they guide. Named after Van Valen’s Red Queen hypothesis—where species must continuously adapt relative to co-evolving competitors—the framework allows agent systems to recursively optimize their prompts, tools, and codebases under non-stationary (time-varying) utility signals.

By organizing the search process into discrete epochs where evaluation criteria remain frozen, the RQGM reconciles evaluator evolution with prior self-improvement guarantees, ensuring that agents optimize against a stable contract before the target objective is advanced.

Key Characteristics

The Red Queen Gödel Machine operates through four core architectural mechanisms:

1. Multi-Agent Workspaces

Unlike traditional self-improving agents that modify a single program, each node in the RQGM archive is structured as a shared, evolvable workspace. The workspace contains both task agents (generators) and evaluator agents (judges), overseen by an editable meta-agent. The meta-agent can modify any part of the workspace—including prompts, rubrics, and tool configurations—allowing task agents and evaluators to share code, infrastructure, and optimizations.

2. Controlled Utility Evolution (Epochs)

Evolving an evaluator dynamically introduces non-stationarity, which breaks standard reinforcement learning and tree-search guarantees. The RQGM resolves this by dividing the search into evolutionary epochs:

• Within-Epoch Stationarity: During an active epoch, the selected evaluator is completely frozen. It grades all task agents on their assignments, providing a time-homogeneous utility signal.
• Epoch Boundaries: The evaluator/utility is updated only at designated, checkpoints. This ensures that the agent optimization search is held to a static contract for the duration of the epoch.

3. Anchor-Guided Evaluator Promotion

To prevent evaluators from drifting or becoming overly lenient (reward hacking), evaluator replacement is guided by a fixed, human-governed Ground-Truth Anchor dataset. At checkpoint boundaries, the incumbent evaluator is compared against challenger evaluators developed in the archive.

Promotion is determined by the $\epsilon$-best-belief ($BB_\epsilon$) score—a conservative lower-bound quantile of the Beta posterior over successes ($S_{gt}$) and failures ($F_{gt}$) on the anchor:

$$BB_\epsilon(e) = I^{-1}\epsilon(1 + S{gt}, 1 + F_{gt})$$

A challenger evaluator is promoted to the next epoch only if it strictly outperforms the incumbent on this anchor, ensuring that evaluation criteria systematically improve over time.

4. Selective Erasure

When an evaluator is replaced at an epoch boundary, utility records scored by the displaced evaluator are immediately invalidated and erased. This prevents the blending of evidence from different utility functions.

To avoid the $O(B^2)$ cost of re-evaluating the entire archive under the new judge immediately, the RQGM amortizes this cost: it erases slot-specific records immediately and re-evaluates older nodes lazily only when the tree-search scheduler naturally returns to them. Using exponentially spaced checkpoints (ratio $\rho > 1$) bounds the cumulative work exposed to erasure to $O(B)$, keeping co-evolutionary search computationally tractable.

ASDLC Usage

In the ASDLC framework, the Red Queen Gödel Machine is positioned as the mathematical foundation for co-evolving soft judges (Review Gates) without violating the safety constraints of the Hard Harness Freeze (Lesson #4). While deterministic Quality Gates (compilers, linters) and the ground-truth anchor datasets remain strictly frozen and human-governed, the soft prompts, instructions, and rubrics of Critic agents are co-evolved within the Agent Optimization Loop under an epoch-gated Controlled Utility Evolution scheme. This co-evolutionary curriculum helps developers prune bad code generations early, saving token resources while preventing the system from drifting away from product intent.