PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolution through Large Models

Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, Kenneth O. Stanley

arXiv:2206.08896v1cs.NE

TL;DR

When an agent has no prior experience in a domain, generating even valid artifacts can be effectively impossible, leaving reinforcement learning without a gradient to bootstrap. The paper introduces evolution through large models (ELM), using LLM-based program mutations with evolutionary search to generate examples in an unseen domain and bootstrap enhanced conditional models. ELM combined with MAP-Elites generates hundreds of thousands of examples in a foreign domain, and the generated data supports training models that cannot be trained from scratch.

  • Problem

    Without prior domain experience, an agent may be unable to generate valid artifacts, so reinforcement learning cannot bootstrap into a new domain.

  • Method

    ELM prompts an LLM to generate program changes as a mutation operator within evolutionary search, including fine-tuning the operator with accepted diffs and operating directly on Python programs.

  • Results

    Hundreds of thousands of examples were generated in a completely foreign domain, and the resulting data supported training LLMs that cannot be trained from scratch.

  • Takeaways & Limitations

    ELM offers a path toward open-endedness by combining evolutionary search with LLM-based program changes and using generated data to bootstrap enhanced models.

  • Takeaways & Limitations

    The resultant model’s ability to interpolate or extrapolate beyond its training distribution remains an open question, and preliminary experiments showed diminishing returns from repeated model improvement.

Abstract

from arXiv · show

This paper pursues the insight that large language models (LLMs) trained to generate code can vastly improve the effectiveness of mutation operators applied to programs in genetic programming (GP). Because such LLMs benefit from training data that includes sequential changes and modifications, they can approximate likely changes that humans would make. To highlight the breadth of implications of such evolution through large models (ELM), in the main experiment ELM combined with MAP-Elites generates hundreds of thousands of functional examples of Python programs that output working ambulating robots in the Sodarace domain, which the original LLM had never seen in pre-training. These examples then help to bootstrap training a new conditional language model that can output the right walker for a particular terrain. The ability to bootstrap new models that can output appropriate artifacts for a given context in a domain where zero training data was previously available carries implications for open-endedness, deep learning, and reinforcement learning. These implications are explored here in depth in the hope of inspiring new directions of research now opened up by ELM.

1 Introduction

ELM combines LLM-based code mutation with evolutionary search to make program evolution more effective and to generate training data in domains absent from the original model’s experience. The paper demonstrates this pipeline in Sodarace and connects it to conditional invention and open-endedness.

  • Core idea: ELM uses code-trained LLMs as intelligent mutation operators within evolutionary algorithms.The approach aims to make coordinated program changes while retaining evolutionary search over candidate solutions.
  • Core idea: Combining LLMs with evolution can steer search toward useful program regions that neither conventional evolution nor the LLM alone could reach.LLMs approximate how humans intentionally modify programs and can be fine-tuned on successful perturbations.
  • Experimental setting: A single mediocre human-designed Sodarace example is used to generate an entire dataset in a novel domain.The domain was not included in the generic code-generating LLM’s prior training experience.
  • Experimental setting: ELM represents Sodaracers as raw Python programs, allowing genetic programming to operate directly on a modern programming language without Sodarace-specific provisions.Sodarace provides a domain where two-dimensional robots are constructed for diverse terrains and evaluated through simulation.
  • Implications: Generated ELM data can fine-tune LLMs to produce viable Sodaracers consistently and support reinforcement learning for terrain-conditional outputs.The paper presents this as a route toward new forms of open-ended processes.
  • Contributions: The paper’s contributions include ELM, fine-tuning its mutation operator, demonstrating search in an unrepresented domain, and bootstrapping enhanced LLMs toward open-endedness.These contributions connect evolutionary computation, deep learning, and open-endedness.

2 Background

The background motivates ELM by contrasting GP’s constrained, often random code search with LLMs trained on human programming changes. It also frames computer programs as potentially expandable encodings for open-ended environments.

  • Genetic programming: Genetic programming evolves computer programs through evolutionary algorithms, but scaling it to complex programs and new domains remains difficult.Practical GP often requires researchers to specify available functions, variables, and control structures.
  • Genetic programming: Conventional GP commonly explores through random code perturbations, whereas human programmers make deliberate, complex, and coupled modifications.Discrete code changes can dramatically alter functionality, complicating evolutionary search.
  • Large language models: LLMs trained on large coding datasets can acquire function-synthesis capabilities, including through training on repository-level code changes.Diff models learn to suggest informed changes from code and commit-message context.
  • Large language models: Diff models can serve as intelligent perturbation operators because they learn incremental code changes that mimic human programmers.Their training on successful diffs also makes further adaptation through gradient descent possible.
  • Open-endedness: Open-endedness seeks systems that produce never-ending innovation, but existing algorithms generally reach plateaus rather than strong open-ended divergence.The paper describes strong open-endedness as continued improvement without a plateau.
  • Open-endedness: Fixed encodings make it difficult to expand evolving environments, while computer programs offer a general encoding for continually increasing environmental richness.The paper presents programs as a way to represent more of an environment without relying on ad-hoc principles.

3 Approach: Evolution through Large Models

ELM embeds an LLM-driven mutation operator inside an evolutionary quality-diversity loop and can update that operator from successful mutations. The approach is designed to search Python program spaces while addressing the broader challenge of strong open-endedness.

  • ELM architecture: ELM consists of an LLM-driven mutation operator, an evolutionary outer loop, and updates to the LLM based on prior performance.These three components jointly define the approach.
  • LLM mutation: A diff model generates code changes conditioned on a program and a natural-language commit message, providing a controllable mutation mechanism.Commit messages allow the mutation scope and intent to be varied.
  • Mutation experiment: In the 4-Parity experiment, a 300M-parameter diff model is compared with simple GP mutation on implementations containing increasing numbers of bugs.The test probes whether an intelligent operator can make multiple correlated corrections.
  • Mutation alternatives: Alternative edit-mode and prompt-engineered LLM mutations are viable implementations, and experiments report that they outperform the diff model used in the paper.The paper also notes that mutation operators are modular components that can be placed within diverse evolutionary algorithms.
  • Scope: ELM is most directly applicable when genotypes use programming languages supported by LLMs, and the experiments use variable-length Python programs.The paper identifies direct use of modern programming languages without special accommodation as a key benefit.
  • Open-endedness: The approach targets strong open-endedness, but no current algorithm is known to produce genuinely unbounded improvement without eventual plateaus.The paper presents ELM as an opportunity related to this challenge rather than as a demonstrated solution.
  • MAP-Elites: MAP-Elites repeatedly mutates Python solutions, evaluates them, and retains candidates that fill new behavior niches or outperform existing niche champions.This process gradually builds a diverse map of high-quality solutions from an initial seed.
  • Fine-tuning: Fine-tuning on accepted MAP-Elites diffs can update the mutation operator toward changes associated with higher quality, novelty, or both.The paper demonstrates one fine-tuning iteration while leaving continual refinement for future work.

4 Experiment and Results

The experiment uses ELM to generate diverse Sodaracer programs, then bootstraps an LLM that can produce inventions conditionally for observed terrain. The pipeline combines artifact search, LLM training, and reinforcement-learning fine-tuning, using Python as a generic representation.

  • Experiment domain: The experiment targets complex artifact invention in Sodarace, where two-dimensional robots must traverse varied terrain.Sodaracers consist of masses and oscillating springs, and their performance is evaluated through simulation.
  • Motivation: Reinforcement learning cannot bootstrap effectively when an agent lacks prior experience to produce even valid artifacts, motivating domain pretraining before conditional fine-tuning.The pipeline therefore uses generated Sodarace designs to teach the agent preliminary domain knowledge.
  • Three-stage pipeline: ELM first searches for diverse Sodaracer examples, which provide training data for subsequent model training.MAP-Elites searches the artifact space for functional examples rather than searching neural-network weights.
  • Three-stage pipeline: The pipeline pre-trains an LLM on ELM-generated examples and then fine-tunes it through reinforcement learning to produce inventions conditioned on terrain.The conditional inventor observes terrain and outputs an appropriate Sodaracer specification.
  • Python representation: Sodaracers are represented as executable plain-text Python programs, allowing ELM to operate directly on a modern programming language without specialized evolutionary encodings.The programs output enumerations of robot components and are evaluated by execution through the Python interpreter.
  • Python representation: The diff model’s initial ability to create useful perturbations depended on the procedural construction interface, with a more Pythonic class-based interface proving more effective.The interface exposes methods such as “add joint” and “add muscle” for constructing walkers.

5 Pipeline Stage 1: Data Generation through ELM

Stage 1 combines LLM-based program mutations with MAP-Elites to generate diverse, high-quality Sodaracer programs from simple hand-designed seeds. The process fills a broad behavior map, while fine-tuning the mutation model improves evolutionary performance.

  • Experimental details: Three independent runs per seed used 1,024,000 evaluations, with a 300M-parameter pretrained diff model providing perturbations.Each run comprised 2,000 iterations of 512 diffs.
  • Diversity: ELM discovered a large proportion of niches, showing that one user-provided example can bootstrap diverse data across the target behavior space.The Square seed spread more slowly because reaching high-mass niches required loops and/or function composition.
  • Quality evaluation: Quality-diversity score combines solution quality and diversity by summing the performance of all champions in the final map.Maximum fitness provides a separate gross measure of solution quality.
  • Mutation-model improvement: Fine-tuning the diff model on accepted diffs greatly increased performance and produced a significantly higher percentage of valid diffs.The fine-tuned model better aligned mutation proposals with the out-of-distribution Sodarace programming domain.
  • Stage 1 outcome: ELM generated hundreds of thousands of working training examples in a novel domain where no data was previously available.The results combine an intelligent LLM-based mutation operator with a quality-diversity algorithm.

6 Pipeline Stage 2: Language Model Training

Stage 2 fine-tunes code-generating language models on programs produced by ELM, testing whether they reproduce the generated data’s quality and diversity. Models trained on the 80% threshold generally perform better, while code pretraining provides a useful prior for out-of-distribution completion.

  • Training pipeline: Stage 2 fine-tunes language models on programs generated during Stage 1 to initialize the later conditional-invention stage.The Stage 1 programs are compiled into a fine-tuning dataset.
  • Dataset construction: The thresholded dataset includes reasonably capable solutions admitted to each MAP-Elites niche, with Radial-seed runs excluded because their chaotic behavior harmed downstream performance.Solutions are selected using a minimal performance bar, while preserving coverage of behavior-space niches.
  • Model training: Models ranging from 0.1M to 680M parameters were fine-tuned, alongside a randomly initialized 300M control model.Five percent of the data was held out as a test set.
  • Upstream comparison: Fine-tuning the diff model improves ELM performance across niche count, QD score, and percentage of valid diffs.These three metrics evaluate evolutionary search breadth, combined quality-diversity, and mutation applicability.
  • Loss results: Models above 85M parameters may not fit the data better, while random initialization performs worse than fine-tuning from code-pretrained models.The comparison concerns minimum test loss for the 80% threshold models.
  • Sample quality and diversity: Samples from trained models achieve performance similar to Stage 1 dataset samples, with a slight consistent QD benefit for models trained on the 80% cutoff.Each model contributed 1,024 samples evaluated in a new MAP-Elites map.
  • Generalization: Out-of-distribution completions generally perform better for larger models and models trained on the 80% threshold, whereas the randomly initialized 300M model significantly underperforms.The evaluation averaged results over three unseen solutions and used 1,024 completion samples per model for each task.
  • Stage 2 outcome: Overall, the results show that language models can integrate synthetic data generated through ELM in a novel domain.This conclusion follows from the models’ reproduction of generated-data quality and diversity and their out-of-distribution completion results.

7 Pipeline Stage 3: Conditional RL

Stage 3 converts an unconditional Sodaracer generator into a terrain-conditional inventor using a terrain embedding network and reinforcement learning. Despite brittle training, the resulting models generally produce terrain-specific Sodaracers with good conditioned performance.

  • Conditional RL: Stage 3 uses reinforcement learning to fine-tune a Stage 2 unconditional LLM into a model that accepts terrains and outputs Sodaracer programs.The target model produces Python programs representing Sodaracers in response to particular terrains.
  • Terrain Embeddings: The terrain embedding network maps each terrain into token-embedding space so the LLM can sample programs conditionally without architectural modification.The TEN output functions like an activation from a prefix, allowing the model to continue autoregressive sampling.
  • Training Procedure: RL episodes sample a terrain, generate a conditional program, simulate its Sodaracer on that terrain, and reward traversed distance.This trains the TEN and further fine-tunes the LLM parameters for conditional behavior.
  • Experimental Design: The terrain sets are designed so no single Sodaracer performs well everywhere, making conditionality necessary rather than allowing collapsed solutions.Preliminary experiments observed collapse toward one program that performed reasonably on only a subset of terrains.
  • Limitations: RL training was sometimes divergent and inconsistent, especially with ResNet TENs because they add many parameters trained from one image per terrain.The authors describe the RL procedure as brittle and identify the impoverished image distribution as a likely contributor.
  • Results: The resulting models tend to produce distinct Sodaracers for each terrain, with good performance on the conditioned terrain and failure to locomote on others.In most cases, RL models are comparable to or better than the best Sodaracers sampled from the dataset or pretrained LLM, though gains are not always significant.
  • Qualitative Observations: The pipeline produced qualitatively distinct solution classes, including very short Sodaracers that emerged for tunnel terrain.The authors interpret these observations as evidence of interesting and creative conditional solutions, while noting that the domain itself is not open-ended.

8 Discussion and Conclusion

The discussion presents ELM as a way to make program evolution more effective by using LLMs as intelligent mutation operators and by generating training data in domains lacking prior examples. It connects this capability to exploration, open-endedness, and future GP applications while noting uncertainty about generalization beyond the training distribution.

  • Motivation: ELM addresses the problem that arbitrary mutations of an already-formulated program are unlikely to be useful.Python programs can provide informative seeds, but conventional evolutionary computation often begins with randomized configurations containing little useful information.
  • Generated Data: MAP-Elites combined with ELM generated hundreds of thousands of examples in a domain foreign to the initial LLM, starting from human-written seeds.The paper states that the subsequent invention pipeline confirmed the validity of this generated data.
  • Bootstrapping: The generated data supported training LLMs that could not be trained from scratch on the target domain.This extends ELM beyond search by using evolved examples as data for later model training.
  • Implications for GP: ELM combines LLM-based intelligent mutation with evolutionary search to explore regions that neither conventional evolution nor the LLM alone could reach effectively.The paper presents this combination as a new form of GP that reduces dependence on the raw search landscape induced by code.
  • Applications: The approach offers a way to generate examples or optimize solutions in domains where data is sparse or nonexistent.The discussion mentions possible applications to MAP-Elites optimization and LLM architecture or hyperparameter search.
  • Open-Endedness: The experiment suggests that knowledge from simple flatground walkers can support specialized walkers for different terrains, a capability relevant to open-ended search beyond prior distributions.The paper frames continual movement beyond familiar regions as a central challenge for open-endedness.
  • Limitations: A key unresolved question is whether the resulting model can interpolate or extrapolate to environments outside its training distribution.The authors state that extrapolating principles may require additional weight updates beyond RL’s use of existing LLM knowledge.
  • Conclusion: The discussion argues that ELM can strengthen GP while also creating new synergies between evolutionary computation and deep learning.The paper presents this reciprocal relationship as motivation for further research and applications.

A.1 Python Source for Benchmark Tasks

The benchmark tasks provide small Python programs for parity and quadratic bug repair, alongside Sodarace walker constructions using reusable geometric and CPPN-like functions. Comparisons show diff mutation outperforming GP mutation, while alternative LLM-based operators can match or exceed the diff model.

  • 4-Parity: The 4-Parity benchmark defines binary parity as the sum of four input bits modulo two.Its implementation uses `bit_sum = sum([b1,b2,b3,b4])` and returns `bit_sum % 2`.
  • 4-Parity: Bugs in 4-Parity are introduced through variable renaming and replacing modulus two with modulus three, while GP receives additional c-prefixed terminals.The first four mutations rename b-prefixed variables individually; the fifth changes the modulus.
  • Quadratic: The Quadratic benchmark defines `quadratic(a,b,c,x)` as a*pow(x,2)+b*x+c and introduces up to two bugs by replacing plus operators with minus operators.The bugs are applied from left to right.
  • Mutation comparisons: Diff mutation outperforms GP mutation on the Quadratic task, and its performance remains unaffected when the second bug is added.The appendix reports a similar pattern for 4-Parity, where diff mutation is also better and degrades differently.
  • Mutation comparisons: Multiple OpenAI API mutation options perform as well as or better than the 300M diff model on the Quadratic task.Figure 21 compares edit-mode and prompt-engineering approaches with the diff model.
  • Sodarace source: Sodarace walker seeds use geometric motifs and CPPN-like encodings, with helper functions that create joints, muscles, squares, circles, and functionally connected grids.CPPN-Fixed preserves the core CPPN query logic, whereas CPPN-Mutable allows that logic to evolve.

C Model Architectures

The paper’s language models are based on the GPT-3 architecture, with model configurations described by standard architectural and attention hyperparameters.

  • Model basis: The models used in the paper are based on the GPT-3 architecture.Further architectural and hyperparameter details are attributed to Brown et al.
  • Reported hyperparameters: Table 1 reports parameter count, layer count, bottleneck width, attention-head count, and attention-head dimension for the model architectures.The corresponding labels are nparams, nlayers, dmodel, nheads, and dhead.

D Seed Robustness

Seed choice affects how well ELM products support later adaptation: high Stage 1 diversity does not necessarily yield robust generalization to novel terrains.

  • Seed–stage interactions: Some seeds achieve high Stage 1 QD scores but provide poor starting points for Stage 3 adaptation to novel terrains.Radial and some CPPN-Mutable products exhibited chaotic dynamics sensitive to initial conditions.
  • Seed–stage interactions: The results indicate that QD score alone does not fully capture the properties that enable generalization and adaptation to novel terrains.The paper identifies understanding this relationship as an important direction for further research.
  • Possible remedies: Proposed ways to bias seeds toward generalizable inventions include limiting precise parameter settings, adding stochasticity, and incrementally adjusting seeds.Preliminary results from disallowing precise parameter settings were mixed.
  • Possible remedies: Fine-tuning the diff model on CPPN-Fixed products improves the robustness of later CPPN-Mutable runs relative to directly using CPPN-Mutable products.The passage contrasts this with high-performing but chaotic inventions from the pretrained diff model.

E Final Map Approach to Stage 2

The final map approach distills Stage 1 into one highest-quality solution per discovered niche and produces a smaller dataset than the percentage-threshold method. In these experiments, that reduction weakened Stage 2 diversity and made Stage 3 unstable.

  • Dataset construction: The final map approach concatenates the best-quality solution for each discovered niche from every run.It differs from percentage thresholding, which includes all reasonably high-quality solutions after normalizing performance across runs and niches.
  • Dataset construction: 13K examples comprise the final map dataset, and models trained on it generally achieve lower QD scores than percentage-threshold models.Performance varies across seeds: Square is strong in some niches, while CPPN-like seeds cover more niches with weaker performance.
  • Stage 3 consequences: Preliminary Stage 3 experiments using final-map-trained models were unstable because the dataset appeared too small to provide a reliable starting point for reinforcement learning.The passage describes this as a practical limitation of the final map dataset.
  • Completion targets: ELM-generated completion targets add structure through nested loops, multiple loops, and reused function calls such as the Galloper’s repeated `make_sensor` calls.The Galloper’s `make_sensor` is a renamed and modified version of the Square seed’s `make_square` function.
  • Completion targets: Generated source can contain nonsensical comments, but MAP-Elites parsimony pressure can eventually remove them while sometimes preserving seed comments.The Wheel has no comments, whereas the Galloper retains the comment about connecting the square with distance muscles.

H Probing Stage 2 Models

Stage 2 models learned some structure within Sodarace, reliably associating properties within the training distribution but generalizing poorly outside it. Prefix training did not improve interpolation, leaving the best way to encode information useful for Stage 3 unresolved.

  • Within-distribution associations: Stage 2 models could associate Sodaracers with target properties within the training distribution, though fitness conditioning was less reliable.Postfix models consistently generated test-distribution examples matching held-out heights, widths, and masses, while fitness represented a more complicated association.
  • Out-of-distribution generalization: 300M-parameter models were less robust out-of-distribution, struggling to target widths and heights deliberately held out from training.Samples nevertheless covered the holdout area, suggesting variation sufficient for interpolation or slight extrapolation despite unreliable targeted generation.
  • Out-of-distribution generalization: A postfix model achieved a Spearman correlation of only 0.08 when predicting fitness for Sodaracers from the unseen Radial seed.The passage presents larger models and more generated data as a hypothesis for improving out-of-distribution robustness, not as an established result.
  • Implications for Stage 3: Prefix training did not improve performance in the Appendix I interpolation setup, leaving how to encode Stage 2 information that benefits Stage 3 reinforcement learning unresolved.The authors specifically identify fitness as intuitively relevant information whose incorporation remains an open question.
  • Implications for Stage 3: With 300M-parameter models and the current training-data volume, Stage 2 showed modest structure learning but was not yet robust out-of-distribution.The implication for open-endedness remains unclear, and stronger generalization may emerge as the pipeline develops.

I Interpolation Experiments

The interpolation experiments tested whether a conditional inventor would adjust Sodaracer size to smoothly varying tunnel heights. Instead, reinforcement learning repeatedly converged on one unconditional solution, limiting what these experiments could establish about domain interpolation.

  • I Interpolation Experiments: The experiment varied tunnel heights to test whether the inventor would adapt Sodaracer height to the terrain.Taller Sodaracers can locomote quickly on flat terrain but cannot navigate low tunnels, creating pressure for terrain-dependent adaptation.
  • I Interpolation Experiments: The model repeatedly output the same Sodaracer regardless of tunnel height, producing an unconditional solution.This convergence prevented the expected terrain-dependent adjustment from appearing in the experiment.
  • Interpretation: The unconditional Sodaracer could not navigate all terrains in the distribution, indicating that the learned solution was suboptimal.The authors interpret this behavior as a local unconditional optimum rather than deep domain understanding.
  • Interpretation: Unconditional local optima may be simpler for reinforcement learning to learn, causing models to gravitate toward them when they exist.The authors suggest testing more complex open-ended processes where unconditional solutions are insufficient and conditional inventors could earn higher rewards.
  • Future directions: Maximum-likelihood bootstrapping is proposed as an alternative way to ease Stage 3 learning by using high-performing terrain-Sodaracer pairs as supervised data.The proposed procedure would fine-tune both the LLM and terrain-embedding networks, while unseen terrains could encourage further generalization.
Loading 2206.08896v1…