PaperlayerView exact revision on arXiv

Source-linked AI summary

EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers

Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, Yujiu Yang

arXiv:2309.08532v3cs.CLcs.AI

TL;DR

Prompt design substantially affects LLM performance, motivating automatic optimization that avoids the human effort and expertise required for discrete prompts. EvoPrompt connects LLMs with evolutionary algorithms to iteratively generate and select prompts without parameters or gradients, and it consistently outperforms manual prompts and existing methods across 31 datasets, with up to a 25% BBH improvement.

  • Problem

    Effective discrete prompts require substantial human effort and expertise, despite strongly influencing downstream LLM performance.

  • Method

    EvoPrompt uses LLMs as evolutionary operators to generate prompt candidates from an initial population and preserves better development-set performers without LLM parameters or gradients.

  • Results

    EvoPrompt consistently outperforms manually designed prompts and existing methods across 31 datasets, achieving up to a 25% improvement across 22 BBH tasks.

  • Takeaways & Limitations

    LLMs can provide effective, interpretable interfaces for implementing evolutionary algorithms such as GA and DE.

Abstract

from arXiv · show

Large Language Models (LLMs) excel in various tasks, but they rely on carefully crafted prompts that often demand substantial human effort. To automate this process, in this paper, we propose a novel framework for discrete prompt optimization, called EvoPrompt, which borrows the idea of evolutionary algorithms (EAs) as they exhibit good performance and fast convergence. To enable EAs to work on discrete prompts, which are natural language expressions that need to be coherent and human-readable, we connect LLMs with EAs. This approach allows us to simultaneously leverage the powerful language processing capabilities of LLMs and the efficient optimization performance of EAs. Specifically, abstaining from any gradients or parameters, EvoPrompt starts from a population of prompts and iteratively generates new prompts with LLMs based on the evolutionary operators, improving the population based on the development set. We optimize prompts for both closed- and open-source LLMs including GPT-3.5 and Alpaca, on 31 datasets covering language understanding, generation tasks, as well as BIG-Bench Hard (BBH) tasks. EvoPrompt significantly outperforms human-engineered prompts and existing methods for automatic prompt generation (e.g., up to 25% on BBH). Furthermore, EvoPrompt demonstrates that connecting LLMs with EAs creates synergies, which could inspire further research on the combination of LLMs and conventional algorithms.

1 INTRODUCTION

Prompt design strongly affects LLM performance but typically requires substantial human effort and expertise. EVOPROMPT automates discrete prompt optimization by combining LLM language capabilities with evolutionary search and evaluates it across 31 datasets.

  • Prompt engineering is important because downstream LLM performance is significantly influenced by prompt choice.
  • Existing automatic approaches may require token probabilities, emphasize prompt enumeration, or modify prompts, creating access and search trade-offs.
  • EVOPROMPT connects LLMs and evolutionary algorithms to generate coherent candidate prompts while evolutionary search guides optimization toward better prompts.
  • EVOPROMPT iteratively generates candidates from initial prompts, preserves better development-set performers, and can instantiate multiple evolutionary algorithms.The experiments cover Alpaca and GPT-3.5 across 31 datasets.
  • EVOPROMPT requires neither LLM parameters nor gradients, balances exploration and exploitation, and produces human-readable prompts.
  • Experiments demonstrate effectiveness against crafted prompts and existing methods, while showing that LLMs can implement multiple evolutionary algorithms.

2 RELATED WORKS

Prior prompt-optimization methods trade off accessibility, interpretability, and search strategy. Related work includes continuous and discrete prompt methods, as well as attempts to connect LLMs with conventional optimization operations.

  • Prompts in LLMs: Continuous prompt methods tune input-token parameters but require LLM parameters and often provide less interpretability than discrete prompts.
  • Discrete Prompts: Discrete prompts provide human-interpretable instructions, but automatic search methods may still rely on gradients or output-layer token probabilities.
  • Discrete Prompts: Other discrete methods enumerate candidates and select among them, often using resampling to explore prompt variation.
  • LLMs and Optimization Algorithms: LLMs have been studied as black-box optimizers and as imitators of operations such as gradient descent, mutation, and crossover.

3 AUTOMATIC DISCRETE PROMPT OPTIMIZATION

EVOPROMPT applies evolutionary optimization to discrete prompts by having LLMs implement evolutionary operators over coherent natural-language candidates. Its framework initializes, evolves, evaluates, and updates prompt populations using GA or DE variants.

  • 3 AUTOMATIC DISCRETE PROMPT OPTIMIZATION: EVOPROMPT takes initial prompts, a population size, a development set, an iteration budget, and LLM-based evolutionary operators as inputs.
  • 3 AUTOMATIC DISCRETE PROMPT OPTIMIZATION: The algorithm evaluates the initial population, selects parent prompts, generates candidates with LLMs, updates the population, and returns the highest-scoring final prompt.
  • 3 AUTOMATIC DISCRETE PROMPT OPTIMIZATION: Evolutionary operators normally alter sequence elements independently, whereas discrete prompts require connected edits that preserve coherence and readability.
  • 3.1 FRAMEWORK OF EVOPROMPT: The framework follows initial-population, evolution, and update stages, then stops after a predefined number of iterations.
  • 3.2 INSTANTIATION WITH GENETIC ALGORITHM: GA selects two parents using roulette-wheel probabilities based on development-set scores, then applies crossover followed by mutation.
  • 3.2 INSTANTIATION WITH GENETIC ALGORITHM: GA updates the population by merging N generated prompts with N existing prompts and retaining the top N by score.
  • 3.3 INSTANTIATION WITH DIFFERENTIAL EVOLUTION: DE represents mutation as y = a + F(b − c), followed by crossover between the basic and mutated solutions.
  • 3.3 INSTANTIATION WITH DIFFERENTIAL EVOLUTION: EVOPROMPT’s DE variant mutates only differing prompt parts, preserves shared components, and combines mutated parts with the current best prompt.

4 EXPERIMENTS

Experiments evaluate EVOPROMPT across language understanding, generation, and BBH tasks on Alpaca-7b and GPT-3.5, comparing it with human-written and automatic prompt methods. EVOPROMPT generally improves results, with GA and DE showing task-dependent strengths and DE performing especially well on BBH and summarization.

  • Implementation Details and Baselines: EVOPROMPT is evaluated against manual instructions, PromptSource, Natural Instructions, APE, and APO across Alpaca-7b and GPT-3.5 settings.Results use accuracy for language understanding, ROUGE for SAMSum summarization, SARI for ASSET simplification, and normalized scores for BBH.
  • Language Understanding: EVOPROMPT based on both GA and DE significantly outperforms previous prompt-generation methods and human-written instructions on language understanding.GA is slightly better on sentiment classification, while DE performs better on topic classification and gains a 5% accuracy advantage on Subj over GA.
  • Language Generation: EVOPROMPT improves SARI scores by over 3 points over manually designed prompts across Alpaca and GPT-3.5 on text simplification.It also consistently outperforms APE across the evaluated summarization and simplification scenarios.
  • Language Generation: EVOPROMPT (DE) notably outperforms EVOPROMPT (GA) on summarization while achieving comparable performance on text simplification.The reported results identify DE as particularly effective for more complex language-generation tasks such as summarization.
  • BIG-Bench Hard: 25% is EVOPROMPT (DE)’s peak improvement on BBH, with a 3.5% average, while GA reaches 15% peak and 2.5% average improvements across all 22 tasks.DE surpasses GA by over 2% on 6 tasks, although GA leads on some tasks by around 1%.

5 ANALYSIS

The analysis evaluates design choices in EVOPROMPT’s GA and DE variants, including selection, mutation, Prompt 3 selection, and population initialization. Across these studies, roulette-wheel selection, mutating only differing prompt parts, and choosing the best Prompt 3 are supported design choices, while initialization quality has nuanced effects.

  • Designs in GA: Roulette-wheel selection gives EVOPROMPT (GA) higher scores than tournament and random selection.The comparison evaluates three parental-selection strategies.
  • Designs in DE: EVOPROMPT (DE) outperforms EVOPROMPT (GA) on Subj, while both variants perform similarly on ASSET.Subj is an understanding dataset and ASSET is a generation dataset.
  • Designs in DE: Mutating only the different parts of two prompts consistently improves performance across two tasks.The alternative mutates all prompt contents.
  • Designs in DE: Choosing the best current prompt as Prompt 3 is more effective than random sampling and is important to the DE design.Removing Prompt 3 is also evaluated as an alternative.
  • Population Initialization: Randomly selected initial prompts can perform similarly to top-performing prompts, so carefully crafted initialization is not essential.The study also tests bottom-performing prompts and generated variations.
  • Population Initialization: With bottom-performing initial prompts, EVOPROMPT (DE) outperforms EVOPROMPT (GA), whereas GA performs slightly better with top-performing prompts.Generated variations slightly improve performance for top-performing prompts but are unnecessary for randomly selected prompts in DE.

6 CONCLUSIONS

EVOPROMPT connects LLMs with evolutionary algorithms to optimize discrete prompts. Experiments on 31 datasets show consistent gains over manual instructions and existing methods, while the framework also supports LLM-mediated implementations of GA and DE and motivates extensions to other algorithms.

  • Conclusions: EVOPROMPT connects LLMs with evolutionary algorithms for discrete prompt optimization.The framework is instantiated with representative GA and DE algorithms.
  • Conclusions: Experiments on 31 datasets demonstrate consistent performance gains over manual instructions and existing methods.The conclusion reports this as evidence of EVOPROMPT’s superiority.
  • Conclusions: LLMs can serve as an effective, interpretable interface for implementing evolutionary algorithms such as GA and DE.The paper identifies extension to PSO, ACO, and Quality-Diversity algorithms as future research.

A DETAILS OF ALGORITHM IMPLEMENTATION

EVOPROMPT instantiates two representative evolutionary algorithms, GA and DE, while retaining a shared cycle of selection, offspring creation, and population updating. Their selection, mutation, crossover, and updating strategies differ.

  • Algorithm Instantiations: EVOPROMPT instantiates the two representative evolutionary algorithms GA and DE.The specific procedures are provided in separate algorithms.
  • Shared Processes: GA and DE share selection, offspring creation, and population updating as general processes.Their implementations differ in the strategies used within these processes.
  • Algorithm Differences: GA and DE differ in their selection strategies, mutation and crossover operations, and updating strategies.These differences define the algorithm-specific implementations.

B.1 DATASETS

The experiments cover natural-language understanding and generation datasets plus 22 BBH tasks, using model- and task-specific templates. Prompt generation uses resampling and LLM-implemented evolutionary procedures, with results averaged across three seeds for selected analyses.

  • Datasets: The dataset suite includes text classification, simplification, summarization, and 22 Big-Bench Hard tasks.Two BBH tasks contain three subtasks each, and web of lies is excluded because its baseline accuracy is 100%.
  • Task Templates: Task implementation uses different templates for models and task types, including Alpaca, summarization, simplification, and BBH.The templates follow prior work and include corresponding zero-shot examples where specified.
  • Prompt Generation: The resampling template generates variations of manual initial prompts, while LLMs implement the complete DE procedure for EVOPROMPT.One-shot algorithm-execution examples guide both DE and GA, and Figure 5 illustrates DE’s stages.
  • Decoding Settings: GPT-3.5 uses Top-p decoding for evolutionary algorithms, while task implementations use greedy decoding for Alpaca and temperature 0.0 for GPT-3.5 generation tasks.The evolutionary-algorithm setting uses temperature 0.5 and P = 0.95.
  • Analysis Settings: Results for the population-size analysis on SST-5, Subj, and ASSET are averaged over three random seeds.The figure compares population-size effects across the three named datasets.
  • Initial Populations: Manual initial prompts are paraphrased or collected and then expanded to initialize prompt populations for classification and generation tasks.The classification development set contains 200 examples, while generation populations are expanded to 10 prompts.

C.1 PARAMETERS IN EVOLUTIONARY ALGORITHMS

Population size affects EVOPROMPT’s performance and overhead differently across tasks, while iterative evolution steadily improves population quality. DE benefits more from diversity on complex classification tasks, whereas large populations are unnecessary for simpler generation tasks.

  • Population Size: As population size increases, DE and GA scores rise on classification datasets, with DE gaining more from population diversity.DE’s larger increase is attributed to exploring different parts while preserving common prompt components.
  • Population Size: For ASSET, population size 6 matches population size 10 despite the latter incurring a 2.5-fold overhead.The results suggest that larger populations are unnecessary for relatively simple generation tasks.
  • Population Size: For complex tasks such as Subj, larger and more diverse populations bring improvement.This contrasts with the comparable ASSET performance at population sizes 6 and 10.
  • Number of Iterations: Best and average scores on SST-5, Subj, and ASSET gradually converge upward as evolution proceeds.The convergence indicates that population quality steadily increases over iterative updates.
  • BBH Comparison: Figure 8 reports normalized BBH scores for APE, EVOPROMPT (GA), and EVOPROMPT (DE).The figure compares the two EVOPROMPT variants with APE across BBH tasks.

C.2 COMPARISON ON BBH TASKS

The BBH comparison evaluates APE against EVOPROMPT’s GA and DE variants using a shared initial population across 22 reasoning tasks. The associated materials report normalized scores and average accuracy, while the cost analysis defines convergence and iteration comparisons.

  • BBH Evaluation: APE, EVOPROMPT (GA), and EVOPROMPT (DE) are compared using normalized scores on BBH tasks.The comparison is presented in Figure 8.
  • BBH Evaluation: The evaluation uses the same initial population for all 22 BBH tasks without prior knowledge.APE’s Chain-of-Thought prompt is evaluated in a 3-shot setting on reasoning tasks.
  • BBH Evaluation: Table 12 reports average accuracy over 23 BBH tasks for different methods.The table provides an aggregate BBH accuracy comparison.
  • Cost-Aware Comparison: Table 13 compares iterations, API-request tokens, and corresponding scores for EVOPROMPT variants and APE.“Until convergence” means the average score improves by less than 0.3% for two consecutive iterations.

C.3 COST ANALYSIS

EVOPROMPT’s overhead comes from evaluating and generating prompts, with total API requests determined by population size, iterations, and development-set size. Compared with APE, both EVOPROMPT variants outperform significantly with only slight token overhead, while DE converges more slowly but performs better.

  • Overhead Definition: The total number of API requests is N ∗ T ∗ (1 + |D|), matching APE, while evaluation overhead is N ∗ |D| ∗ T.N is population size, |D| is development-set size, and T is the number of iterations.
  • Overhead Definition: EVOPROMPT’s prompt-generation cost mainly depends on the number of API results, T ∗ N.Overhead is analyzed through both fixed-iteration comparisons and performance until convergence.
  • Comparison with APE: With the same number of iterations, GA and DE significantly outperform APE while adding only slight token overhead.The comparison uses API-request token counts during prompt optimization and evaluation.
  • Convergence: APE and GA have similar convergence rates, whereas DE is slightly slower but delivers better performance.The authors interpret this pattern as indicating a relatively high ceiling for EVOPROMPT.
  • Released Outputs: The paper releases optimal prompts generated by EVOPROMPT for understanding, simplification, summarization, and BBH tasks.These prompts are provided in Tables 14–18.

D FUTURE WORKS

The paper identifies extensions to new applications, more advanced differential-evolution variants, and connections between LLMs and other traditional algorithms. It also highlights adaptation challenges when algorithmic elements or continuous controls must operate in discrete language space.

  • Applications: Future applications include game-level generation, text-to-image generation, and non-trivial NP-hard problems such as the traveling salesman problem.These directions are proposed as applications of the framework.
  • Advanced DE Variants: The current study prioritizes canonical classical DE variants, leaving adaptive-control DE variants for future investigation.The authors identify adapting continuous control parameters to discrete language space as a main challenge.
  • Released Outputs: The released prompt tables cover classification, summarization, text simplification, and BBH tasks.Tables 14–18 contain the reported instructions and generated prompts.
  • Beyond Evolutionary Algorithms: Extending the connection beyond EAs may require adapting elements such as motion direction, velocity, paths, or characteristics to LLMs.Examples include PSO, ant-colony optimization, and MAP-Elites.
Loading 2309.08532v3…