PaperlayerView exact revision on arXiv

Source-linked AI summary

Mendel Gödel Machine: Recursive Self-Improving Coding Agents via Comparative Evolution

Changzhi Liu, Yilun Liu, Sikuan Yan, Volker Tresp, Yunpu Ma

arXiv:2608.07645v1cs.AIcs.LG

TL;DR

Existing self-improving coding agents generally condition self-modification on single failure trajectories, leaving comparative archive evidence underused. MGM adds reaction-norm mutation and cross-lineage hybridization, and reports consistent gains over baselines in performance, efficiency, and generalizability on SWE-bench and Polyglot.

  • Problem

    Existing self-modification typically uses one agent’s single-task failure trajectory, overlooking comparative evidence accumulated across archived agents and tasks.

  • Method

    MGM adds reaction-norm mutation and cross-lineage hybridization to clonal mutation, reusing archived trajectories across tasks and lineages without additional task evaluations.

  • Results

    MGM consistently improves performance and efficiency over baselines on SWE-bench and Polyglot, with stronger generalization across benchmarks and backbone models.

  • Takeaways & Limitations

    Comparative conditioning discovers reusable workflow-level improvements that support strong coding-agent performance under matched evaluation budgets.

  • Takeaways & Limitations

    The formal analysis and Monte Carlo study use an additive surrogate, while primary evolution uses fixed 60-task subsets under a single matched budget and limited seed diversity.

Abstract

from arXiv · show

Self-improving coding agents that iteratively rewrite their own source code have demonstrated impressive performance on coding tasks. However, existing solutions generally derive self-modification from a single failure trajectory at a time, overlooking rich comparative signals available in the agent's expanding archive of past attempts. According to Mendelian principles of controlled inheritance, we introduce Mendel Gödel Machine (MGM). In addition to the general single-trajectory clonal mutation, MGM includes two new types of self-modification that better utilizes evidences accumulated: the reaction-norm mutation edits an agent based on its trajectories on multiple tasks simultaneously, and the cross-lineage hybridization edits an agent using the trajectory of a reference agent from another lineage on the same task. Under an additive fitness landscape model, we prove theoretically and demonstrate via controlled surrogate simulation that the new strategies facilitate a faster and better convergence over single-trajectory baselines. Experiments on SWE-bench and Polyglot confirm MGM's consistent improvement in performance, efficiency, and generalizability.

1 INTRODUCTION

MGM addresses the underuse of comparative archive evidence in self-modification by adding reaction-norm mutation and cross-lineage hybridization to standard clonal mutation. Theory, simulations, and experiments report faster convergence and consistent gains in performance, efficiency, and generalizability.

  • Research gap: Existing self-modification typically uses one agent’s single-task failure trajectory, while the archive’s comparative evidence remains underused.The archive records agent variants and their behavior across evaluated tasks, but is mainly used for sampling.
  • MGM contribution: Reaction-norm mutation conditions edits on one agent’s trajectories across multiple tasks, while cross-lineage hybridization uses another lineage’s trajectory on the same task.Clonal mutation remains the single-agent, single-trajectory baseline.
  • MGM contribution: MGM’s operators reuse trajectories accumulated during routine archive evaluation and therefore require no extra task evaluations.The operators directly exploit evidence already present in the archive.
  • Evaluation: Under an additive fitness landscape, MGM has strictly faster expected convergence than single-trajectory baselines, validated through controlled Monte Carlo surrogate simulations.Progress is measured by reduction in Hamming distance to an oracle genotype.
  • Results: MGM shows consistent gains in performance and efficiency on Polyglot and SWE-bench, while also improving transfer across unseen benchmarks and backbone models.On Polyglot, Qwen3.6-35B-A3B advances from 50.8% to 93.3%, and the transferred scaffold reaches 96.9% on DeepSeek-V4-Pro.

2 PRELIMINARIES

The preliminaries represent executable coding agents and their scaffolding as genotypes whose task trajectories and binary outcomes are phenotypes. HGM maintains an archive tree and uses evaluation and expansion policies to allocate a fixed-budget search.

  • Agent representation: An executable coding agent together with its auxiliary scaffolding is treated as the genotype being evolved.Running the agent on a task produces an evaluation trajectory and binary outcome viewed as its phenotype.
  • Agent representation: The expected utility U(a) is the expectation over tasks of the agent’s binary outcome r(a, τ).The outcome is evaluated under the task distribution D.
  • Archive search: DGM maintains an expanding tree of generated agents and evaluation trajectories, while HGM formulates self-improvement as a fixed-budget tree-search problem.For each archive node, evaluated and failed task sets support subsequent decisions.
  • Archive search: At each step, HGM allocates either an evaluation or an expansion to its archive.The choice is governed by its evaluation and expansion policies.
  • Archive search: HGM samples evaluation candidates using Thompson sampling from node-level Beta posteriors, with concentration parameter κ controlling exploration versus exploitation.The posterior uses the node’s numbers of successful and failed tasks.

3 MENDEL GÖDEL MACHINE

MGM extends archive-based tree search by partitioning self-modification into clonal mutation, reaction-norm mutation, and cross-lineage hybridization. These operators select diagnostic evidence from single failures, multiple tasks, or shared-task comparisons, with task sampling designed to increase useful overlap.

  • Mendelian self-modification operators: MGM partitions the expansion operator into clonal mutation, reaction-norm mutation, and cross-lineage hybridization according to available archive evidence.The framework retains HGM’s selection, evaluation, and expansion policies.
  • Clonal mutation: Clonal mutation edits an agent from one failed task trajectory and preserves HGM-style self-modification when only one informative failure is available.It also allows search to proceed while the archive is small.
  • Reaction-norm mutation: Reaction-norm mutation compares multiple trajectories from the same genotype to identify recurring or contrastive patterns across tasks.It becomes available after enough trajectories have accumulated and at least one target failure exists.
  • Cross-lineage hybridization: Cross-lineage hybridization compares different genotypes on a shared task and asks the target agent to adapt a transferable behavioral trait from the reference trajectory.It does not splice source files; the target agent extracts and adapts the trait to its own codebase.
  • Sampling tasks and operators: The global failed-task pool boosts sampling of tasks that exposed failures and deliberately creates cross-lineage overlap without extra evaluations.This increases the availability of controlled comparisons for cross-lineage hybridization.
  • Sampling tasks and operators: MGM constructs eligible operators from archive conditions, applies the selected operator to produce a child, and substitutes evaluation when no operator is eligible.Clonal mutation requires a failure, reaction-norm mutation requires multiple task trajectories, and cross-lineage hybridization requires a shared task across lineages.

4 SIMULATIONS

MGM’s comparative operators are modeled as diagnostic processes that improve self-modification by increasing the probability of correcting hidden genotype defects. Controlled simulations test whether this advantage produces faster convergence and better final performance under varied initial difficulty and operator quality.

  • 4.1 ADDITIVE FITNESS LANDSCAPE: The surrogate model represents each agent as a binary genotype whose hidden mismatches are corrected through task evaluations and self-modification edits.Tasks succeed only when all required loci are correct, while edits may correct mismatched loci or corrupt correct ones.
  • 4.2 COMPARATIVE EVIDENCE AS DIAGNOSTIC COMPRESSION: Comparative evidence improves effective fix probability by concentrating edits on candidate loci with a higher density of truly incorrect defects.The editor does not observe incorrect loci directly; it infers candidate sets from phenotype evidence and repairs targeted incorrect loci with probability s.
  • 4.2 COMPARATIVE EVIDENCE AS DIAGNOSTIC COMPRESSION: ΦRM and ΦCH have strictly higher effective fix probability than single-trajectory ΦCM under sound comparative evidence.ΦRM intersects failure regions across tasks, while ΦCH uses a successful reference trajectory to filter non-causal loci from a failed target task.
  • 4.3 MONTE CARLO SIMULATION: The simulation compares DGM, HGM, and MGM while varying initial edit distance d0, diagnostic advantage ρ, budget allocation, and edit costs.All operators incur the same cost, and performance is recorded as minimum edit distance at budget checkpoints and as final mean ± 95 % CI across seeds.
  • 4.3 MONTE CARLO SIMULATION: MGM consistently outperforms baselines in convergence speed and final performance across all tested d0 and ρ > 1.0 settings.When ρ = 1, MGM collapses to HGM-like behavior; as ρ increases, MGM’s advantage grows, especially at smaller d0, with the lowest mean and tightest spread in final performance.

5 EXPERIMENTS

Experiments evaluate whether MGM improves coding-agent performance and efficiency, and whether its evolved scaffolds generalize across benchmarks and backbone models. MGM consistently outperforms HGM, achieves positive cross-benchmark transfer, and retains stronger performance when paired with different LLMs without higher token expenditure.

  • 5.1 PERFORMANCE: Under an identical budget of 200 evaluations, MGM outperforms HGM on both SWE-bench Verified and Polyglot from the same initial scaffolds.On SWE-bench Verified, MGM reaches 78.3% versus HGM’s 73.3%; on Polyglot, MGM reaches 93.2% versus HGM’s 77.9%.
  • 5.1 PERFORMANCE: The performance gap spans standalone coding and repository-level software-engineering tasks, where failures involve localization, environment understanding, and repair workflows.Both methods use exactly the same number of evaluation and expansion operations, so the gap is not attributed to a larger search budget.
  • 5.1 PERFORMANCE: Comparable token-cost distributions indicate that MGM’s performance gains are not achieved simply through increased token expenditure.Figure 6 reports similar average token costs across HGM and MGM evaluation and expansion operations.
  • 5.2 GENERALIZATION: MGM transfers positively from Polyglot to both SWE-bench Pro and SWE-bench Multilingual, reaching 26.7% and 55.0% accuracy respectively.These correspond to +10.0 and +13.3 percentage-point improvements over the initial scaffold, whereas HGM shows limited transfer.
  • 5.2 GENERALIZATION: Across transferred DeepSeek backbones, MGM averages 70.8% accuracy versus 65.0% for HGM and 47.5% for the initial scaffold.MGM reaches 66.7% with DeepSeek-V4-Flash and 75.0% with DeepSeek-V4-Pro after evolution on Qwen3.6-35B-A3B.
  • 5.2 GENERALIZATION: The cross-benchmark and cross-model results indicate that MGM improves both in-domain performance and scaffold generalizability.The paper frames this as a potential route for reusing scaffolds evolved on smaller datasets and cheaper backbones with stronger models.

6 RELATED WORK

Related work situates MGM within self-evolving agents, executable scaffold optimization, and software-engineering benchmarks. The supplied passages identify prior archive-based self-improvement and benchmark settings but do not provide further detailed comparison results.

  • LLM AGENT SYSTEMS AND AUTOMATED AGENT DESIGN: Prior work studies prompts, tools, and workflows as executable scaffolds that can be optimized by meta-agents using archives of prior discoveries.These approaches establish agent scaffolding as a setting for designs that may transfer across tasks and models.
  • SELF-IMPROVING CODING AGENTS: Self-improving coding-agent research includes self-evaluation, source-code editing, archive-based evolution, and fixed-budget tree-search formulations.The supplied passage names prior systems that progressively extend inherited self-modification and archive expansion.
  • SOFTWARE-ENGINEERING BENCHMARKS: SWE-bench variants and Polyglot evaluate repository-level repair, long-horizon reasoning, and cross-language coding ability.These benchmarks test whether coding agents can make workflow-level improvements.
  • ADDITIONAL RELATED WORK: Additional related work on self-evolving agents, runtime adaptation methods, and datasets is discussed in Appendix G.The supplied passage provides only this pointer rather than substantive details.

7 CONCLUSION

MGM is an archive-based self-improving coding-agent framework that uses comparative trajectory evidence through reaction-norm mutation and cross-lineage hybridization. Theory, simulations, and benchmark experiments support faster convergence and consistent gains, while its scope remains scaffold-level evolution under sandboxed, budgeted archive search.

  • Conclusion: MGM conditions self-modification on comparative evidence from archived evaluation trajectories, adding reaction-norm mutation and cross-lineage hybridization beyond clonal mutation.These operators reuse archived phenotypes across tasks and lineages without additional task evaluations.
  • Conclusion: Under an additive fitness landscape, theory and controlled simulations show that richer diagnostic evidence can accelerate convergence relative to single-trajectory baselines.The analysis links the advantage to improved diagnostic information rather than to a stronger editor.
  • Conclusion: Experiments on SWE-bench and Polyglot confirm consistent gains over HGM in performance and efficiency under a matched budget.Ablations show that both comparative operators contribute to these gains.
  • Conclusion: Held-out evaluations suggest that evolved scaffolds transfer across benchmarks and backbone LLMs, indicating reusable workflow-level improvements rather than narrow task-specific patches.The conclusion presents this as evidence that comparative conditioning can discover reusable scaffold changes.
  • Conclusion: MGM’s supported scope is scaffold-level evolution under sandboxed, budgeted archive search.The paper presents this setting as a potentially compute-efficient path in which scaffolds evolved on smaller backbones can later be reused on stronger models.

LIMITATIONS

The study is constrained by substantial computational cost, dependence on accumulated comparative evidence, uncertainty from limited experimental diversity, and the limits of LLM-generated scaffold edits. Its formal and empirical claims are also bounded by surrogate assumptions, selected task subsets, coding-agent benchmarks, and sandboxed settings.

  • Computational constraints: Evolution and evaluation on repository-level tasks consume substantial wall-clock and GPU resources, limiting independent seeds and hyperparameter sweeps.This restricts the breadth of reported robustness checks.
  • Archive dependence: MGM depends on archive history: sparse task overlap or insufficient accumulated failures can leave it with little comparative evidence and baseline-like behavior.The failed-task pool increases diagnostic overlap but cannot create informative contrasts before failures accumulate.
  • Editor limitations: Comparative evidence does not guarantee edits that are correct, general, or maintainable because scaffold changes are still produced by an LLM-based editor.High-quality evidence can still yield low-quality modifications and waste budget.
  • Evaluation scope: The formal analysis uses an additive fitness surrogate, while primary evolution relies on fixed 60-task subsets under a single matched budget.Subset selection and limited seed diversity leave uncertainty about random restarts and alternative task samples.
  • Evaluation scope: The claims concern coding-agent scaffolds evaluated on public software-engineering benchmarks and do not establish unchanged transfer to non-coding agents or open-ended maintenance.The paper also reports broader checks on full Polyglot and held-out SWE-bench variants.

ETHICAL CONSIDERATIONS

MGM’s self-modification is evaluated in isolated containers with no network access and read-only host mounts, but scaffold evolution has dual-use and inherited-data risks. The paper therefore bounds its evidence to coding-agent settings and emphasizes controlled deployment and task-specific safety review.

  • Sandboxing: Self-modification and evaluation run inside isolated containers with no network access and read-only mounts of the host file system.This follows the safety protocol used by prior archive-based self-improving agents.
  • Dual-use implications: Removing isolation could allow scaffold-level self-improvement to amplify harmful automation, including malicious software generation or exploitation of vulnerable systems.The public release is intended for research on sandboxed self-evolution.
  • Data and model risks: The benchmarks and backbone models may contain insecure code patterns, biased content, and overrepresented languages, ecosystems, or problem domains.The paper did not conduct dedicated bias or safety audits of the evolved agents.
  • Evaluation boundaries: Offline scores should not be read as evidence of robust real-world competence because public benchmark material may overlap with pretraining data.The work focuses on coding agents that are not equipped to act outside software-engineering-related repositories.
  • Deployment: Task-specific safety evaluation remains necessary before use beyond general-purpose coding assistance.The paper discourages unconstrained deployment of evolved scaffolds outside controlled environments.

B.1 THEORETICAL JUSTIFICATION OF COMPARATIVE FIX PROBABILITY

The theoretical analysis models self-modification as diagnostic search over candidate loci and shows why comparative evidence can increase effective fix probability under explicit assumptions. Reaction-norm mutation narrows candidates using recurring failures, while cross-lineage hybridization removes non-causal explanations using a successful reference.

  • Diagnostic framework: An operator’s effective fix probability rises when its evidence yields a candidate set with higher posterior density of truly incorrect loci.The editor selects a candidate locus and repairs it with probability s when that locus is incorrect.
  • Reaction-norm mutation: Reaction-norm mutation intersects multiple failures from the same genotype to compress the candidate set around recurring defects.Under the sound-comparison assumption, the common explanatory region is CRM = Rτt ∩ Rτr.
  • Cross-lineage hybridization: Cross-lineage hybridization compares a failed target with a successful reference on the same task to remove non-causal candidate loci.The resulting contrastive set contains target defects plus residual non-causal differences, yielding f = s · c/(c + h) > s · c when comparison removes at least one irrelevant candidate.
  • Assumptions and boundary: The comparative advantage depends on sparse causal defects, recurring same-agent weaknesses, informative reference trajectories, and an editor capable of exploiting the evidence.When these assumptions fail, the simulation represents little or no fix-quality advantage with the null setting ρ = 1.

C.1 COMPUTE AND SOFTWARE ENVIRONMENT

The experiments use a high-memory multi-GPU cluster and standardized software settings documented through implementation hyperparameters. Qwen models are served with vLLM, and benchmark tasks run in Apptainer containers.

  • Hardware and serving: Experiments run on nodes with eight NVIDIA H100 GPUs and approximately 2 TB of host memory.The Qwen models use vLLM with tensor parallelism across visible GPUs.
  • Hardware and serving: The Qwen serving configuration uses a 262,144-token maximum context length and 92% GPU memory utilization.The models are exposed through an OpenAI-compatible API.
  • Software environment: Benchmark tasks execute inside Apptainer containers built from a Python 3.10 base image, with repository directories bind-mounted into the containers.The implementation hyper-parameter settings are reported in Table 6.

D BENCHMARK DETAILS

The benchmark evaluation uses selected task subsets to control compute while preserving language and repository coverage. SWE-bench Multilingual spans 300 tasks, 42 repositories, and nine programming languages, while SWE-bench Pro uses a representative 60-task subset across six languages.

  • Task selection: 60 representative tasks are randomly selected separately for SWE-bench Pro and SWE-bench Multilingual to control evaluation cost.The full SWE-bench Pro and SWE-bench Multilingual benchmarks are not evaluated in this procedure.
  • SWE-bench Pro: SWE-bench Pro’s selected subset covers JavaScript, Python, Java, C++, TypeScript, and Go.The subset is required to be representative and involve all six programming languages.
  • SWE-bench Multilingual: SWE-bench Multilingual contains 300 tasks from 42 repositories spanning C, C++, Go, Java, JavaScript, TypeScript, PHP, Ruby, and Rust.Its subset is constructed to cover these language groups while keeping evaluation cost manageable.

E.1 FULL EVALUATION ON POLYGLOT

Full-benchmark evaluation confirms that the evolved MGM agent’s Polyglot performance remains stable beyond the 60-task subset and is broadly distributed across languages. The evolution-tree figures show how MGM’s comparative operators and evaluation-supported selection shape the final result.

  • Full Polyglot evaluation: The full Polyglot evaluation is conducted only after evolution, without further agent updates or benchmark-driven adaptation.The full benchmark is used for post-evolution evaluation rather than updating the agent.
  • Full Polyglot evaluation: 210 out of 225 tasks are solved, yielding 93.3% overall accuracy on full Polyglot.This closely matches the 93.2% accuracy on Polyglot-60, and the agent solves tasks across six reported languages.
  • Evolution trees: MGM’s 24-node evolution tree uses clonal mutation, reaction-norm mutation, and cross-lineage hybridization under a 200-task-evaluation budget.Node fill color encodes evaluation accuracy, and edge color identifies the child’s self-improvement operator.
  • Evolution-tree comparison: The selected MGM result has utility 0.91 after 35 evaluations, whereas the selected reaction-norm ablation has utility 0.84 after 50 evaluations and the hybridization ablation has utility 0.88 after 16 evaluations.Raw utility maxima can come from sparsely evaluated nodes, so selection favors estimates backed by more evaluations.
  • Hybridization case study: Cross-lineage hybridization transfers a test-contract skill from a successful donor lineage to a separate failing lineage, producing a hybrid child that solves javascript__queen-attack.The transferred behavior emphasizes exact public APIs, expected values, and error messages.

F.2 BIGGER MODEL DOES NOT ALWAYS LEAD TO BETTER RESULTS

Self-improvement quality is not determined by model size or coding specialization alone: trajectory diagnosis and general reasoning shape the usefulness of scaffold edits. MGM’s comparative operators make this diagnosis more informative but also more reasoning-intensive, while its evolved changes appear more workflow-general than HGM’s.

  • Model capability and self-improvement: Self-improvement performance cannot be predicted solely from model size or coding specialization.The model must diagnose failure mechanisms before modifying the scaffold.
  • Model capability and self-improvement: Trajectory-level diagnosis requires reasoning about prompts, tools, control flow, repository exploration, execution feedback, and prior behavior.Shallow diagnosis can produce valid edits that target the wrong mechanism or create brittle workflow changes.
  • Model capability and self-improvement: Qwen3.6 outperforms Qwen3-Coder-Next by 11.51 points on GPQA, 7.25 on SuperGPQA, and 21.47 on LiveCodeBench v6.It also scores higher on MMLU-Redux and MMLU-Pro despite having fewer total parameters.
  • MGM’s evolved workflows: Reaction-norm mutation and cross-lineage hybridization increase comparative evidence, making MGM’s diagnosis more informative but more reasoning-intensive.The operators compare multiple trajectories of one agent or different agents on the same task.
  • MGM’s evolved workflows: MGM’s evolved changes cluster around reusable workflow capabilities, whereas HGM’s changes are more dispersed across heterogeneous interventions.The MGM cluster centers on exact contract extraction, API adherence, and pre-implementation verification.

G.2 RUNTIME ADAPTATION VERSUS TRAINING-TIME SELF-EVOLUTION

Runtime adaptation improves the current problem-solving process, whereas MGM performs persistent, training-time evolution across many episodes. Their complementary roles support evolving robust base agents offline before specializing them at runtime.

  • Scope and timing: Live-SWE-agent adapts an agent’s capabilities during a real software issue, while MGM evolves persistent scaffold changes across many episodes.MGM evaluates modifications over a task distribution and stores descendants in an archive.
  • Scope and timing: MGM targets general capabilities that remain useful beyond the tasks exposing them, including planning, validation, context management, debugging, and tool usage.Its modifications are training-time self-evolution rather than within-episode adaptation.
  • Complementary paradigms: Chain-of-thought prompting and runtime adaptation improve a current trajectory, whereas policy optimization and MGM change what future trajectories inherit.The paper presents these paradigms as complementary.
  • Evaluation setting: SWE-bench evaluates repository-level issue resolution through patches tested against corresponding pull-request tests, stressing navigation, fault localization, construction, and validation.SWE-bench Pro adds harder long-horizon tasks from a broader range of maintained repositories.
  • Evaluation setting: MGM’s benchmark choices test cross-task generality and behavioral transfer across complementary settings including SWE-bench Verified, SWE-bench Pro, and Polyglot.The experiments do not expose private test cases or test results during evolution.
  • Evolved workflow: An MGM example transforms single-pass repair into a trace-aware, patch-constrained workflow rather than a task-specific repository patch.The scaffold extracts tests, traces code paths, reviews remaining failures, and constrains changes using exploration provenance.
Loading 2608.07645v1…