PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models As Evolution Strategies

Robert Tjarko Lange, Yingtao Tian, Yujin Tang

arXiv:2402.18381v1cs.AIcs.LGcs.NE

TL;DR

The paper asks whether text-trained LLMs can perform black-box optimization without explicit task training. It prompts them with discretized, fitness-sorted candidates to propose a search mean; EvoLLM performs optimization on BBOB functions and small neuroevolution tasks, and teacher-trajectory fine-tuning can improve performance.

  • Problem

    The paper investigates whether LLMs that have not explicitly encountered black-box optimization can implement evolutionary optimization algorithms in a zero-shot setting.

    Source: §1 · p. 2

  • Method

    EvoLLM prompts a text-trained LLM with discretized, fitness-sorted candidate solutions to propose an improved mean for an evolution strategy.

    Source: §1 · p. 2, §4 · p. 3

  • Results

    EvoLLM performs black-box optimization on synthetic BBOB functions and small neuroevolution tasks, and its performance can improve through fine-tuning on teacher-algorithm trajectories.

    Source: §1 · p. 2, §8 · p. 8

  • Takeaways & Limitations

    Text-trained LLMs can act as in-context recombination operators for evolutionary optimization, with teacher-algorithm information providing a way to improve performance.

    Source: §1 · p. 2

    Performance is expected to vary with pretraining and fine-tuning protocols, and scaling to larger search spaces may require long-context reasoning.

    Source: §8 · p. 8

Abstract

from arXiv · show

Large Transformer models are capable of implementing a plethora of so-called in-context learning algorithms. These include gradient descent, classification, sequence completion, transformation, and improvement. In this work, we investigate whether large language models (LLMs), which never explicitly encountered the task of black-box optimization, are in principle capable of implementing evolutionary optimization algorithms. While previous works have solely focused on language-based task specification, we move forward and focus on the zero-shot application of LLMs to black-box optimization. We introduce a novel prompting strategy, consisting of least-to-most sorting of discretized population members and querying the LLM to propose an improvement to the mean statistic, i.e. perform a type of black-box recombination operation. Empirically, we find that our setup allows the user to obtain an LLM-based evolution strategy, which we call `EvoLLM', that robustly outperforms baseline algorithms such as random search and Gaussian Hill Climbing on synthetic BBOB functions as well as small neuroevolution tasks. Hence, LLMs can act as `plug-in' in-context recombination operators. We provide several comparative studies of the LLM's model size, prompt strategy, and context construction. Finally, we show that one can flexibly improve EvoLLM's performance by providing teacher algorithm information via instruction fine-tuning on previously collected teacher optimization trajectories.

1 INTRODUCTION

The paper asks whether text-trained LLMs can perform black-box optimization without explicit training on that task, and proposes EvoLLM, a prompt-based evolution strategy. Experiments report zero-shot optimization across synthetic benchmarks and small neuroevolution tasks, alongside prompt studies and teacher-trajectory fine-tuning.

1 INTRODUCTION

  • The motivating question is whether text-trained LLMs can generalize to optimization algorithms, including training neural-network weights as in evolutionary strategies.Prior examples include in-context sequence improvement and LLMs used for code-level mutation or crossover.Source: §1 · p. 2
  • EvoLLM performs zero-shot black-box optimization on synthetic BBOB functions and small neuroevolution tasks across varied dimensions and evaluation budgets.The experiments also report prompt-design ablations and construction recommendations.Source: §1 · p. 2
  • The method represents discretized candidate solutions, sorts them by performance using least-to-most prompting, and queries the LLM for an improved mean statistic.The resulting LLM-based evolution strategy is called EvoLLM.Source: §1 · p. 2
  • Discretized solution representations greatly outperform common natural-language instructions, while EvoLLM is largely robust to discretization and context choices.Among the selected LLMs, smaller models tend to outperform larger ones.Source: §1 · p. 2
  • Fine-tuning the base model on teacher-algorithm black-box optimization trajectories can improve EvoLLM’s performance.The paper uses trajectories generated by teacher algorithms as additional information.Source: §1 · p. 2

2 RELATED WORK

Related work spans Transformer in-context learning, autoregressive black-box optimization, LLM prompting and optimization, and learned evolutionary updates. The paper distinguishes its approach as using text-trained LLMs for evolution strategies without explicit training on black-box optimization tasks.

2 RELATED WORK

  • Prior work applied Transformers to in-context image classification, reinforcement learning, and meta-reinforcement learning.These studies investigate models trained from scratch to perform in-context learning.Source: §2 · p. 2
  • Earlier autoregressive black-box optimization methods trained sequence models on generated or augmented task spaces, whereas this work tests text-trained models without explicit black-box optimization training.The cited methods include RNN-based and T5 Encoder-Decoder approaches.Source: §2 · p. 2
  • LLMs have been used as text-based optimizers and for evolutionary mutation, crossover, genetic programming, and prompt evolution; this paper examines their use as ES recombination operators and on small neural networks.The authors characterize their work as the first to consider LLMs for ES while comparing base models and prompt construction approaches.Source: §2 · p. 2
  • Learned ES and genetic-algorithm methods used attention trained through meta-evolution on small task distributions, while this method does not meta-train a new optimizer.The comparison is specifically with methods processing information within a generation using self- and cross-attention.Source: §2 · p. 2

3 BACKGROUND

The background defines derivative-free black-box optimization and isotropic Gaussian evolution strategies, then frames the LLM as a possible update operator. It also motivates prompt construction and integer-based solution representations.

3 BACKGROUND

  • Black-box optimization seeks a global optimum using function evaluations when the function’s form or derivatives are unavailable or infeasible to compute.The stated problem constrains each coordinate to its specified interval.Source: §3 · p. 3
  • In an isotropic Gaussian ES, a population is sampled from a search distribution, evaluated, and used with search history to update the distribution toward better-performing solutions.The paper asks whether an LLM can represent this UPDATE operation from a context string built from the history.Source: §3 · p. 3
  • The paper uses text-trained Transformer models to process black-box optimization trajectories represented by discretized candidates and their fitness or rank.It asks whether in-context learning can resemble an efficient update operation.Source: §3 · p. 3
  • Because raw high-precision floating-point values tend to be underrepresented by language-model tokenizers, the authors propose an integer-based representation.They also compare prompt-construction approaches to examine LLM behavior.Source: §3 · p. 3

4 TURNING LLMS INTO ES ALGORITHMS

EvoLLM uses discretized, fitness-sorted search histories to prompt an LLM for a new search mean, then samples and evaluates a population. Its context construction offers alternative selection schemes, while dimension-batched queries trade added inference time for scalability.

4 TURNING LLMS INTO ES ALGORITHMS

  • EvoLLM lets an LLM perform an ES search-distribution update from text-context information, within an ask-evaluate-tell procedure.An initial buffer is seeded, candidates and fitnesses are tracked, and new evaluations are added after each update.Source: §4 · pp. 3–4, Figure 2 · p. 4
  • The prompt represents solutions as discretized integers, sorts prior evaluations by fitness across generations, selects high-performing generations and candidates, and asks the LLM for a mean at a desired fitness level.The method avoids raw floating-point numbers because tokenization may use differing numbers of tokens for individual values, hindering inference of improvement sequences.Source: §4 · p. 3
  • Context construction can select generations at random, most recently, or by their best-performing candidates, and can select candidates randomly or by within-generation or cumulative performance.The ordering of generations and candidates may affect how easily the LLM infers improving directions such as momentum.Source: §4 · p. 4
  • The LLM’s proposed mean is parsed and used to sample the next population; if parsing fails, the backup is sampling around the previous best evaluation.The resulting population is evaluated and its information is added to the context buffer.Source: §4 · p. 4
  • Figure 4 reports lower-is-better BBOB performance for different LLM base models and states that EvoLLM’s behavior is robust to the model choice.The caption says results are averaged across 10 independent runs.Source: Figure 4 · p. 5
  • When context length becomes too large, EvoLLM splits dimensions into blocks and makes multiple LLM queries per generation, trading inference time for scalability.Each query handles a dimension batch that fits the context; in the limit, each call processes one dimension.Source: §4 · pp. 4–5, Figure 3 · p. 4

5 LLMS ARE ZERO-SHOT EVOLUTION STRATEGIES

EvoLLM optimizes synthetic BBOB functions and small neural-network control policies, often outperforming baseline optimizers, especially under small evaluation budgets. Its performance also holds under batched queries for 10-dimensional problems.

5.1 Evaluation on Synthetic BBO Functions

  • On the cited BBOB evaluations, EvoLLM can outperform random search and Gaussian Hill Climbing at D∈{3, 5} and N∈{5, 10}, and beats all baselines on every task below 10 generations.The named functions are Rosenbrock, Discus, and Schwefel.Source: §5.1 · p. 5
  • The authors report that model size inversely affects EvoLLM’s downstream performance, comparing differently sized pretrained models from PaLM2, OpenAI, and Llama2.Source: §5.1 · p. 5
  • For 10-dimensional Sphere and Rosenbrock, performance does not significantly decline when parameters are optimized in groups using batched LLM queries.This pattern holds for PaLM2-XS and text-davinci-003.Source: §5.1 · p. 6, Figure 5 · p. 6

5.2 Evaluation on Neuroevolution Tasks

  • EvoLLM optimizes CartPole and Acrobot neural-network policies and can outperform competitive baselines in the small-budget regime.The evaluated single-hidden-layer networks contain 16–40 weights and biases; optimization becomes harder as parameter count increases.Source: §5.2 · p. 6, Figure 6 · p. 6

6 EVOLLM ABLATION STUDIES

The ablations examine prompt construction, numerical representation, discretization resolution, and context length. They find that sorting and fitness information matter, discretized representations outperform raw text over longer trajectories, and useful resolution depends on the problem.

6.1 Prompt Strategy Ablations

  • Randomly sorting generations and members substantially decreases performance, while omitting fitness information decreases GPT-4 performance; context selection is largely robust.Filtering generations by mean uniqueness is not beneficial.Source: §6.1 · p. 6, Figure 7 · p. 7

6.3 Impact of Resolution & Context Length

  • On the examined Sphere settings, performance improves as resolution rises to 1000 bins and then declines at 10000, while the Rosenbrock trend is unclear.The authors suggest that the optimum resolution is problem-specific.Source: §6.3 · p. 7

6.2 Raw text vs. discretized representation

  • Discretized solution representations continue improving over longer trajectories, whereas raw text-based prompting quickly saturates.The authors attribute the raw-text limitation to difficulty zooming into optima and overly large perturbations after initial improvements.Source: Figure 8 · p. 7, §6.2 · p. 7

6.3 Impact of Resolution & Context Length

  • EvoLLM can improve the mean with very limited context, and more context generations often appear more beneficial than more context members.The authors suggest clearer improvement sequences may help the LLM infer continuation patterns such as momentum.Source: §6.3 · p. 7

7 EVOLLM WITH TEACHER FINE-TUNING

The authors fine-tune EvoLLM on teacher-generated optimization trajectories and evaluate the tuned model on BBO tasks and neuroevolution. They report robust performance gains across the evaluated tasks.

7 EVOLLM WITH TEACHER FINE-TUNING

  • On PaLM-XS, instruction-based fine-tuning on Gaussian Hill-Climbing trajectories yields a small but robust performance increase across Sphere and Rastrigin at 2 and 5 search dimensions, outperforming both teacher and untuned LLM in almost all cases.Source: §7 · p. 8

8 DISCUSSION

The discussion summarizes EvoLLM’s ability to act as an evolution strategy across varied black-box optimization tasks and notes that teacher-trajectory fine-tuning can improve its capabilities. It also identifies protocol dependence and scaling to larger search spaces as open challenges.

8 DISCUSSION

  • The authors summarize a prompt strategy for purely text-trained LLMs to act as evolution strategies and report improved capabilities after fine-tuning on teacher sequences.Their ablations emphasize solution representation and context construction.Source: §8 · p. 8
  • EvoLLM’s performance may depend on pretraining and fine-tuning protocols, and scaling to larger search spaces may require long-context reasoning.The effects of those protocols are described as an open challenge.Source: §8 · p. 8
  • Preliminary attempts to extend the prompt to non-isotropic evolution strategies by adding diagonal-covariance updates did not yield significant improvements.Source: §8 · p. 8

A.1 Impact of Search Space Resolution

Search resolution affects EvoLLM’s ability to optimize: low resolutions hinder zooming into optima basins, while high resolutions degrade performance due to tokenization.

A.1 Impact of Search Space Resolution

  • Low resolutions hinder EvoLLM from zooming into optima basins, while high resolutions degrade performance due to tokenization.Results are averaged over five independent runs.Source: Figure 11 · p. 10

A.2 Context Members & Generations

The supplied passages show EvoLLM’s behavior under varying context information, illustrate a two-dimensional Sphere prompt example, describe number-tokenization behavior, and identify fine-tuning diagnostics.

A.2 Context Members & Generations

  • Even with limited context information, the LLM can infer improving sequence patterns.Results are averaged over five independent runs.Source: Figure 12 · p. 10

B PROMPT CONSTRUCTION EXAMPLE: 2 DIM. SPHERE / 5 POPULATION MEMBERS

C FLOATING POINT NUMBER TOKENIZATION

D HILL CLIMBING INSTRUCTION FINE-TUNING

  • Figure 14 presents fine-tuning loss and accuracy for instruction fine-tuning on PaLM-XS using Hill Climbing teacher-algorithm trajectories.Source: Figure 14 · p. 11

Related papers

Loading 2402.18381v1…