PaperlayerView exact revision on arXiv

Source-linked AI summary

Language Model Crossover: Variation through Few-Shot Prompting

Elliot Meyerson, Mark J. Nelson, Herbie Bradley, Adam Gaier, Arash Moradi, Amy K. Hoover, Joel Lehman

arXiv:2302.12170v3cs.NE

TL;DR

The paper examines how LLM pattern-learning abilities can support language-model crossover as a genetic operator. Experiments span equations, plain-text sentences, images, and code, supporting LMX as a flexible approach for evolving text-representable genomes.

  • Problem

    The paper examines how LLMs’ pattern-learning abilities can support broader applications of language models.

  • Method

    LMX uses an LLM as a flexible genetic operator, with universality allowing programs with arguments to be implemented through the model.

  • Results

    Experiments span equations, plain-text sentences, images, and code, demonstrating LMX across a broad range of potential applications.

  • Takeaways & Limitations

    LMX provides a simple way for evolutionary-algorithm practitioners to use recent progress in language models.

  • Takeaways & Limitations

    LMX is limited by the LLM context window and can generate invalid outputs, while access to suitable resources may be less accessible to some users.

Abstract

from arXiv · show

This paper pursues the insight that language models naturally enable an intelligent variation operator similar in spirit to evolutionary crossover. In particular, language models of sufficient scale demonstrate in-context learning, i.e. they can learn from associations between a small number of input patterns to generate outputs incorporating such associations (also called few-shot prompting). This ability can be leveraged to form a simple but powerful variation operator, i.e. to prompt a language model with a few text-based genotypes (such as code, plain-text sentences, or equations), and to parse its corresponding output as those genotypes' offspring. The promise of such language model crossover (which is simple to implement and can leverage many different open-source language models) is that it enables a simple mechanism to evolve semantically-rich text representations (with few domain-specific tweaks), and naturally benefits from current progress in language models. Experiments in this paper highlight the versatility of language-model crossover, through evolving binary bit-strings, sentences, equations, text-to-image prompts, and Python code. The conclusion is that language model crossover is a promising method for evolving genomes representable as text.

1 INTRODUCTION

The paper introduces language-model crossover (LMX), using few-shot prompting to generate offspring from text-based parent genotypes. Experiments across multiple representations support its versatility and potential for semantically rich evolution.

  • LMX leverages few-shot prompting to create an intelligent evolutionary crossover operator from text-based parent genotypes.A language model analyzes several concatenated genotypes and generates a new genotype that follows their inferred distribution.
  • The operator can implicitly model parent genotypes and sample offspring through a single language-model forward pass.The paper connects this mechanism theoretically to estimation of distribution algorithms.
  • LMX is designed to exploit text’s semantically rich representation without requiring domain-specific variation operators.The method can use specialized open-source models by changing the hosted model used by the implementation.
  • Experiments apply LMX to binary strings, plain-text sentence style transfer, mathematical expressions, text-to-image prompts, and Python code.These experiments are presented as evidence of the method’s versatility across domains and modalities.
  • The paper introduces LMX, explores its basic properties, and reports a reusable implementation for reproducing the main experiments.The authors state that the implementation and experiment-recreation code will be released.

2 BACKGROUND

The background frames LMX within foundation models, few-shot prompting, and intelligent variation in evolutionary computation. It contrasts LMX’s implicit modeling of parent genotypes with traditional and learned variation strategies.

  • Foundation Models: Foundation models provide broad pretrained representations that can be specialized or combined for domains such as text, images, and code.The background emphasizes their plug-and-play ecosystem and use in evolving high-quality artifacts.
  • Foundation Models: Autoregressive language models generate text probabilistically by sampling tokens conditioned on an input sequence.This next-token formulation underlies their use as pattern-completion engines.
  • Few-Shot Prompting: Few-shot prompting supplies example input-output pairs before a target input, enabling in-context learning from limited examples.Performance at in-context learning improves with model scale.
  • Intelligent Variation Operators: Traditional genetic operators do not explicitly model regularities among high-performing individuals, contributing to sample inefficiency in some situations.Intelligent variation methods address this limitation by using learned spaces, mutation models, repair knowledge, or probabilistic distributions.
  • Intelligent Variation Operators: Estimation-of-distribution methods build explicit probability models, whereas LMX implicitly models parent genotypes during an LLM forward pass.The paper positions LMX as related to EDAs while using pretrained foundation models and prompting.
  • Intelligent Variation Operators: Foundation models can be directly leveraged through strategic prompting rather than trained on solutions generated during the current search.The paper presents this as a shift toward pre-existing models and prompting.

3 APPROACH: LANGUAGE MODEL CROSSOVER (LMX)

LMX turns in-context learning into an evolutionary variation operator by prompting an LLM with parent genotypes and extracting valid offspring. The approach supports standard evolutionary loops and is intended to improve with language-model capability.

  • LMX follows from next-token prediction by treating example genotypes as context for generating further genotypes from their implied distribution.The paper frames this as a direct generalization of few-shot prompting.
  • LMX is simple to implement, relatively domain-independent, and intended to produce increasingly semantically sophisticated variation with more capable LLMs.The basic implementation concatenates text genotypes, runs an LLM, and extracts a new genotype.
  • An LMX evolutionary loop selects parents, concatenates them into a prompt, samples output from the LLM, extracts valid candidates, and refines the population by fitness.These steps are the core of Algorithm 1.
  • The operator’s core crossover step concatenates parent genotypes, generates output text, and extracts valid children.The algorithm identifies Lines 7–9 as the essence of LMX.
  • The paper hypothesizes that crossover with k > 1 parents will outperform mutation with k = 1 or random sampling with k = 0.This expectation is based on the connection between LMX and k-shot prompting.
  • LMX can replace the variation operator in many evolutionary algorithms, although its use in algorithms with explicit probabilistic genotype models remains future work.The paper specifically identifies EDAs, natural evolution strategies, and CMA-ES as an open question.

4 EXPERIMENTS

Experiments apply LMX across five domains to test its generic ability to generate and evolve text-based variation. Across binary strings, symbolic regression, natural language, image prompts, and Python code, LMX produces valid, diverse, and often competitive solutions with limited domain-specific tuning.

  • Experimental scope: LMX is evaluated across binary strings, symbolic regression, natural-language style transfer, text-to-image prompts, and Python code.These experiments probe both basic properties and breadth of applicability.
  • Binary strings: LMX reliably generates novel, valid binary offspring, preserves heritable variation, and drives evolutionary search without domain-specific operators.In binary strings, offspring distributions depend on parent neighborhoods, and LMX achieves higher mean fitness than one-point crossover despite fewer optimum convergences.
  • Symbolic regression: In symbolic regression, LMX evolves fit and parsimonious expressions, tunes constants, and discovers later structural improvements despite using a simple optimization loop.The method settles on functional scaffolding, refines constants, and can produce substantial improvements late in evolution.
  • Symbolic regression: With Galactica, LMX achieves higher fitness and lower expression size than gplearn, while Pythia performs less strongly, showing that LLM choice matters.The authors report comparable or competitive final expression quality, but caution that the comparison is not a comprehensive state-of-the-art evaluation.
  • Natural language and images: LMX improves sentiment-diversity quality scores, discovers diverse image prompts, and enables sensible evolution of images and natural-language style variants.For sentiment modification, both LMX variants outperform the control across three quotes; for image prompts, evolution finds diverse solutions targeting specified colors.
  • Python code: In Python-code evolution, roughly 30% of offspring are valid with the 6B model, with higher fitness and diversity and a slight validity trend as model scale increases.These results demonstrate promise for evolving non-trivial Python programs.

5 WHAT MAKES LMX EFFECTIVE?

LMX can be interpreted as an estimation-of-distribution algorithm whose language-model distribution generates offspring from parent prompts. Its effectiveness is linked to parent-set modeling, increasing similarity to EDA behavior with more parents, and flexible prompt-based reproductive behavior.

  • EDA connection: LMX combines aspects of input genotypes by sampling offspring from a language model conditioned on parent text.The operator uses the LLM’s autoregressive output distribution as its implicit reproductive mechanism.
  • EDA connection: LMX acts like an EDA by constructing an implicit probabilistic model of parents and sampling children from it.Unlike explicit EDA distributions, the relevant model is encoded opaquely in the LLM’s parameters and activations.
  • EDA connection: LMX and the selection operator S_n are sufficient to define an estimation-of-distribution algorithm.Each iteration samples N candidates from LMX conditioned on the current population, then selects n candidates.
  • EDA connection: As the number of parents increases, the disparity between LMX and EDA distributions diminishes, and both approaches converge toward the same distribution.The paper investigates this relationship in a bitstring case and connects it to LMX’s effectiveness across domains.
  • Universality of LMX: Theorems establish that LMX can theoretically express any genetic operator under weight-based or prompt-based universality conditions.The prompt-based result uses a universal Turing machine assumption, while the weight-based result relies on injective encoding and surjective decoding conditions.
  • Expressive encodings: LMX can support expressive encodings by treating the solution, LLM, and prompting mechanisms as components of the genotype.The paper also suggests that jointly evolving these components could support more open-ended systems.
  • Biasing through parental ordering: LMX’s input ordering can bias offspring distributions, with sorted parents producing offspring patterns that reflect the chosen sorting criterion.In the one-max setting, descending order favors lower scores while ascending order favors higher scores; leading-ones sorting produces a corresponding bias.

6 LIMITATIONS

LMX is constrained by the LLM’s context window, domain coverage, opacity, computational requirements, invalid outputs, and unresolved population-dynamics challenges. These limitations affect scalability, initialization, interpretability, accessibility, and validity guarantees.

  • Computational access: LMX requires GPU compute in the reported experiments, which may reduce accessibility for users without suitable resources.The paper notes ongoing efforts toward efficient CPU inference but still reports a benefit from GPU access.
  • Validity: LLMs can generate invalid outputs that cannot be parsed as solutions, unlike carefully designed traditional genetic operators with formal validity guarantees.A high invalid-output rate increases the computational cost of producing the next generation.
  • Initialization: For domains far from the LLM’s training data, population initialization becomes particularly important because unconditional text sampling is impractical.The experiments instead use phenotype-space samples, human-designed examples, or fixed seed examples.
  • Scale and context: LMX cannot efficiently handle solutions larger than the LLM context window, limiting performance on very large search spaces.The paper notes that decomposition into appropriately sized subproblems may be necessary.
  • Opacity and bias: LMX’s opaque behavior can make failure causes and undesirable model biases difficult to diagnose.This concern is especially relevant for applications with societal implications, although independent bias investigation is possible.
  • Population dynamics: LMX does not solve premature convergence, diversity maintenance, or exploration–exploitation problems inherited from evolutionary algorithms.It provides a generic operator rather than resolving these broader population-dynamics challenges.

7 DISCUSSION AND CONCLUSIONS

The discussion presents LMX as a flexible text-based genetic operator with broad experimental reach, while emphasizing dependence on model quality, parent selection, and further validation.

  • Contributions: LMX provides a flexible genetic operator for evolving equations, sentences, images, and code through open-source neural networks.The paper positions LMX as simple to use and applicable across multiple evolutionary settings.
  • Scope and future work: Experiments span broad applications, but the paper prioritizes breadth over depth and leaves state-of-the-art performance for future work.The authors identify symbolic regression as one area where further effort could improve results.
  • Optimization behavior: LMX can represent continuous optimization despite operating over discrete tokens, including by tuning floating-point constants.The authors describe this capability as an interesting direction for further exploration.
  • Model dependence: Performance depends substantially on the underlying LLM, with training-data coverage and model specialization affecting domain-relevant variation.The discrepancy between Pythia and Galactica is offered as evidence, although its broader generality remains unresolved.
  • Variation control: Parent ordering, parent selection, and prompt design provide controllable dimensions of offspring variation, but robust parent-selection methods remain an open question.Preliminary experiments found qualitative effects from similar-embedding parents, while different parent-feeding strategies substantially changed generation.
  • Future directions: The authors suggest integrating LMX with other evolutionary frameworks and mutation operators, while noting computational expense and limited experimental depth.Most experiments ran on a single GPU or Google Colab, excluding the Python Sodaracer experiment.

A BINARY STRING EXPERIMENTAL DETAILS

The binary-string experiments standardize tokenization and sampling, then examine how model size affects offspring validity and novelty.

  • Sampling: Sampling used a maximum of 150 tokens with top-p = 0.8 and top-k = 30 after mild tuning.Top-k restricts outputs to the k highest-probability tokens, while top-p restricts them by cumulative probability mass.
  • Evolutionary setup: The evolutionary baseline used truncation selection of the top 50%, elitism, one-point crossover, and bit-flip mutation with probability 0.1.The population size, genome length, and generation count were each 10.
  • Representation: Binary genomes were separated with underscores so each bit became a single token, avoiding tokenizer-dependent effects.For example, 0011 was represented as _0_0_1_1.
  • Model-size experiment: The model-size experiment fixed the number of parents at 3 and generated variation from randomly sampled binary strings across Pythia models.Results were averaged over 15 randomly generated parent sets.
  • Results: As model size increased, both valid-offspring percentage and novel-offspring count generally increased.This pattern was reported for the averaged binary-string experiment.

B SYMBOLIC REGRESSION EXPERIMENTAL DETAILS

The symbolic-regression details describe a constrained, compute-conscious evolutionary setup using LMX alongside benchmark-expression seeding and diversity safeguards.

  • Model and sampling: The experiment used GALACTICA 1.3B with sampling temperature 0.8 for LMX-based symbolic regression.The model was selected for this experiment as the language model used for LMX.
  • Population: The initial population contained 1000 candidates, followed by population size 50 for computational efficiency.The authors note that a larger population could improve performance.
  • Diversity control: Duplicate offspring were discarded, and a 0.05 probability of direct benchmark-expression generation was used to prevent stagnation.The direct-generation path randomly selected and mapped a benchmark expression instead of using LMX.
  • Benchmarks: Benchmark expressions were taken from popular symbolic-regression benchmarks represented in Python.The source repository was the deep-symbolic-optimization GitHub repository.
  • Compute: Running 5000 generations took around 100 hours, with most wall-clock time spent in the LLM forward pass.The authors note that batching offspring generation could reduce this cost.

C MODIFYING SENTIMENT EXPERIMENTAL DETAILS

The sentiment experiments apply LMX with Pythia models to quality-diversity maps and compare its performance with a baseline across quote-modification tasks.

  • Setup: The LMX sentiment experiments used a 1.4-billion-parameter Pythia model with top-p = 0.8, top-k = 30, and a 128-token generation limit.These settings were used for the experiment described in this section.
  • Quality diversity: MAP-Elites heatmaps show final maps for LMX-Near, LMX, and a baseline control on the Homer Simpson quote.Grid position represents similarity to the original quote, while color indicates fitness and black indicates unfilled niches.
  • Woody Allen: For the Woody Allen quote, LMX and LMX-Near did not differ significantly, but both significantly outperformed the control.The task increased positive sentiment for “Life is divided into the horrible and the miserable.”

C.1 Additional Positive Sentiment Results

Additional positive-sentiment results report representative Pareto fronts for sentiment modification of three quotations using LMX-Near.

  • Simpsons quote: A representative LMX-Near run modifies the Simpsons quote and produces a full Pareto front.The full front is reported for the Simpsons sentiment-modification task.
  • Gore Vidal quote: A representative LMX-Near run modifies the Gore Vidal quote and produces a full Pareto front.The full front is reported in Table 4.
  • Woody Allen quote: A representative LMX-Near run modifies the Woody Allen quote and produces a full Pareto front.The full front is reported in Table 5.

C.2 Evolving towards Negative Sentiment

LMX can evolve quotations toward negative sentiment, but the resulting high-negativity outputs often invoke vulgar language, dark situations, or failure-oriented themes. Changing the classifier label may enable style transfer to other text properties or styles.

  • Negative sentiment: LMX successfully evolves positive quotations toward high negativity.The experiments target the negative sentiment class and produce modifications achieving high negativity.
  • Observed outputs: High-negativity outputs often use vulgar language, death, depressive thoughts, or other dark situations.Examples include vulgar or dark content and statements emphasizing failure or bleakness.
  • Style transfer: Using a different classification label, or a model recognizing other text properties, could support style transfer across many other styles.The paper presents this as a possibility highlighted by the preliminary experiments.

D IMAGE GENERATION EXPERIMENTAL DETAILS

The image-generation experiments evolve text-to-image prompts with LMX, using Stable Diffusion and constrained sampling, evaluation, and evolutionary-loop settings.

  • Image generation: Stable Diffusion v1.4 converts each LMX-generated prompt into an image.The experiment uses the 16-bit-weight variant and default 512 × 512 image resolution.
  • Fitness evaluation: Image fitness was computed from 8-bit integer RGB images and normalized against a maximum fitness of 66,846,720.The maximum corresponds to a monochromatic image of the target color.
  • Prompt length: 75 tokens were sampled per LMX-generated prompt to remain within Stable Diffusion’s 77-token prompt limit.Pythia and Stable Diffusion use slightly different tokenizers.
  • Evolutionary loop: The evolutionary loop used four parents per child, 0.95 probability of LMX generation, and 0.05 probability of sampling a new human-written prompt.The population size was 50, and each generation took about 4 minutes on an NVIDIA GeForce RTX 3090.

E PYTHON SODARACERS EXPERIMENTAL DETAILS

The Sodaracers experiments evolve Python programs with CodeGen models in a Box2D simulation, while examining prompt design, model scale, and parent-order effects on valid offspring.

  • Evaluation: Sodaracer fitness was the horizontal distance traveled by an instantiated robot after 1 second of Box2D simulation.The abbreviated evaluation time was chosen to demonstrate meaningful evolution within computational constraints.
  • Parent ordering: Parent order changed valid-generation success rates by over 50% in some cases.Results were therefore averaged over all parent permutations or sampled from permutations during long runs.
  • Prompt design: Forcing the make_walker function signature improved validation relative to removing it; single-seed mutation failed completely, while two- or three-parent LMX fell 15%.The prompt appended def make_walker(): to force completion with the required signature.
  • Future direction: Instruction prompting was identified as a promising but unexplored direction for improving evolved-program quality and diversity.The paper connects this possibility to instruction-finetuned models and prompts compatible with their training data.
Loading 2302.12170v3…