Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers
Authors: Qingyan Guo
Rui Wang
Junliang Guo
Bei Li
Kaitao Song
Xu Tan
Guoqing Liu
Jiang Bian
Yujiu Yang
Venue: ICLR 2024 poster (2024)
Keywords: large language model
evolutionary algorithm
prompt engineering
natural language processing
Primary area: general machine learning (i.e., none of the above)
TL;DR: Automatic prompt optimization combining large language models and evolutionary algorithms

Abstract: 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.

Published as a conference paper at ICLR 2024
CONNECTING LARGE LANGUAGE MODELS WITH EvO- LUTIONARY ALGORITHMS YIELDS POWERFUL PROMPT OPTIMIZERS
Qingyan Guol2t*, Rui Wang" Junliang Guo", Bei Li Kaitao Song", Xu Tan Guoqing Liu?, Jiang Bian', Yujiu Yang"
'Tsinghua University "Microsoft Research Northeasternn University gay22emails, tsinghua. edu. cn, libei_neu@outlone com, {ruiwa,
kai taosong, xuta, guoqingliu, i jiabia cemcrrstttooo yang. yujjuuuj tsinghua. edu.cn
ABSTRACT
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 novel framework for discrete prompt opti- mization, 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 be coherent and numan-readable, we connect LLMs with EAs. This approach allows us to simultaneously leverage the powerful language processing capabil- ities of LLMs and the efficient optimization performance of EAs. Specifically, abstaining from any gradients or parameters, EvoPROMPT starts from popula- tion 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 spen-source LLMs including GPT-3.5 and Alpaca, on 31 datasets covering language understanding, generation tasks, 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 connect- ing LLMs with EAs creates synergies, which could inspire further research on the combination of LLMs and conventional algorithms. Our code is available at https: thub. wwwebeewwwwicoocoeeeeeeeeeeweeee tavororomptt...
INTRODUCTION
Large language models (LLMs) show remarkable performance multiple natural language pro- cessing (NLP) tasks (Touvron et al., 2023; Ouyang et al., 2022). To adapt to downstream tasks, simply adding an instruction the input text, also called discrete prompt, steers LLMs to carry the desired task with negligible impact on computational cost (Liu et al., 2023). Such approach also eliminates the need for all the parameters and gradients in LLMs, making it suitable for LLMs with block- box APIS such as GPT-3 and GPT-4 (Brown et al., 2020; OpenAl, 2023). Despite the convenience, the performance of the LLMs towards a certain task significantly influenced by the prompt (Liu et al., 2023: Zhu et al., 2023). Accordingly, the key challenge of this approach lies in the design of the prompt, which has emerged as a crucial technique known as prompt engineering (Zhou et al., 2022). Given the wide variation in prompts across language models and tasks, the prompt design typically requires substantial human effort and expertise with subjective and relatively limited guidelines (Mishra et al., 2022a;b; Liu et al., 2023; Zanfirescu-Pereira et al., 2023; Wang et al., 2023).
*Work done during internship at Microsoft Research Asia. 1 'quual Contribution. Corresponniig Author.

---

Published as a conference paper at ICLR 2024
To alleviate human effort discrete prompt design, previous approaches usually rely access to the token probabilities from the output layer of LLMs, which may not always be accessible through APIs (Deng et al., 2022; Zhang et al., 2023a). Some recent works consider enumerating diverse prompts and selecting the best ones (Zhou et al., 2022; Jiang et al., 2020), or modifying current prompts to improve them (Guo et al., 2023; Prasad et al., 2022; Pryzant et al., 2023). Such approaches either emphasize exploring diverse prompts, which may lead to indecisiveness and wasted resources, or focus on exploiting upon the current identified good prompts, which may result in stagnation and confine the search to local optima. Several conventional derivative- free algorithms are well-designed and strike good balance between exploration and exploitation (Conn al., 2009; Rios & Sahinidis, 2013). Among these, evolutionary algorithms (EAs) stand out they are simple and efficient, as well as suitable for discrete prompt optimization (Storn Price, 1997; Brest et al., 2006; Zhang & Sanderson, 2009; Vesterstrom & Thomsen, 2004). Sequences of phrases in prompts can be regarded as gene sequences in typical EAs, making them compatible with the natural cvolutionary process.
In this paper, we borrow the idea of EAs and propose a discrete prompt tuning framework, EvO- PROMPT. While evolutionary operators in EAs are typically designed for sequences, they tend to independently alter tokens to generate new candidate solutions. Unfortunately, this approach ignores the connections among tokens, which is crucial for maintaining coherence and readability in prompts. Taking advantage of LLMS'' expertise in NLP and the exceptional optimization capabilities of EAs, we connect these two approaches, where LLMS generate new candidate prompts following evolutionary operators, and EAs guide the optimization process to retain the optimal prompts.
Specifically, based on several initial prompts, we utilize LLMs to act as evolutionary operators to generate new prompt candidates, and the prompt with better performance on the development set is preserved. The above operations upon the updating population are iteratively applied to improve the quality. By elaborately designing the evolutionary operators and adjusting the update strategy. EvoPROMPT can be instantiated with various types of EAs. We optimize the prompts for two different L.LMs (i.e., Alpaca (Taori et al., 2023), and GPT-3.5 (Brown et al., 2020)) on diverse range of neural language understanding and generation tasks, as well as challenging BIG-Bench tasks, using a total of 31 datasets. EvoPROMPT consistently gets better prompts compared with both manually designed ones and previous automatic prompt generation methods. The main contributions of this paper include:
We propose novel framework for automatic discrete prompt optimization connecting LLMs and EAs, called EVOPROMPT, which enjoys the following advantages: 1) It does not require access to any parameters or gradients of LLMs; 2) It strikes balance between exploration and exploitation leading to better results; 3) The generated prompts are human-readable.
Experiments conducted on 31 datasets demonstrate the effectiveness of EVOPROMPT compared with crafted prompts, as well as existing methods. We release the optimal prompts obtained by EvoPROMPT for these common tasks such as sentiment classification, topic classification, subjectivity classification, simplification, summarization and reasoning.
We demonstrate that LLMs are capable of implementing multiple types of EAs provided with appropriate instructions. We hope that our explorations will inspire further investigations on the combination of LLMs and conventional algorithms, paving the way for new and innovative applications of LLMs.
2 RELATED WORKS
Prompting is an efficient method for employing LLMs in specialized tasks. However, the performance is heavily influenced by the choice of the prompt. Recently, automatic prompt optimization has obtained wide attention. Continuous promet-based methods, which only tune parameters of some input tokens (Li & Liang, 2021; Liu et al., 2021 Zhang et al., 2021) attract lots of attention. In spite of their effective performance, two drawbacks of such paradigms can not be ignored: 1) The optimization of continuous prompts requires parameters of LLMs that are inaccessible for black-box APIs 2) Soft prompts often fall short of interpretability (Lester et al., 2021). Discrete prompts, simply adding several discrete tokens, such as "It was" (Schick & Schütze, 2021), spec-fc descriptive instructions, such "Classify the comment into positive or negative.", " to the input text, can offer an interactive interface to humans with better interpretability and show promising performance in various NL.P tasks (Liu al., 2023).
Prompts in LLMs
2

---

Published as a conference paper at ICLR 2024
Discrete Prompts Various approaches have been proposed for automatic discrete prompt searching and generation (Shin et al., 2020; Shi et al., 2022: Wallace et al., 2019; Deng et al., 2022; Zhang et al., 2023a), while these methods still rely on the gradients the token probabilities from the output layer. More recently, considering the high variance of different prompts for downstream tasks, some works focus on exploration by enumerating and selecting the best prompt from numher of candidates, mainly augmented by re-sampling (Zhou et al., 2022; Jiang et al., 2020). Approaches based on prompt edit (Zhang al., 2023a; Prasad et al., 2022) emphasize exploitation, which may potentially lead to local optima. Another approach collects the incorrectly predicted cases and analyzes the corresponding root cause improve existing prompts (Pryzant et al., 2023; Guo et al., 2023). which also emphasizes exploitation. Additionally, such approaches are constrained to tasks with standard answers and cannot be directly applied to generation tasks. Our proposed EVOPROMPT empowered with evolutionary algorithms strikes a balance between exploration and exploitation without requiring any parameters or gradients.
LLMs and Optimization Algorithms LLMs demonstrate the potential to serve as black-box optimizers (Zheng et al., 2023); however, this black-box approach lacks explainabilityy Some works have revealed that LLMs have the capability to imitate specific operations in conventional algorithms. For instance, LLMs can perform "Gradient Descent" in discrete space by collecting incorrectly predicted samples (Pryzant et al., 2023; Guo et al., 2023). Meanwhile, has been demonstrated that LLMs can imitate the mutation (Lehmman al., 2022) or crossover (Meyerson al., 2023) operator in the genetic algorithm (GA), Chen et al. (2023) further integrates LLMs and GA for neural architecture search, while Lanzi & Loiacono (2023) introduce similar approach to game design. Our work has taken significant step forward by proposing a general framework that connects LLMs with evolutionary algorithms, which can be instantiated algorithms through customization of evolutionary and selection processes, thereby broadening its applicability and potential influence the domain. We aspire this work to inspire broader applications of combining LLMs and conventional algorithms.
diverse range of evolutionary
AUTOMATIC DISCRETE PROMPT OPTIMIZATION
Algorithm 1 Discrete prompt optimization: EVoPROMPT
Require:
Initial prompts Po {PI. ......... P j. size of population N, a dev set D, ff(+) denotes the score a prompt on the desired LLM evaluated on D, a pre-defined number of iterations T, carefully designed evolutionary operators to generate new prompt Evo(-)
1: Initial evaluation scores: S, + {s; = fr():) E [1,
2: for t = to T do
3: Selection: select a certain number prompts from current population as parent prompts
Prit...:Pr, Pry. P
4: Evolution: generate a new prompt based on the selected parent prompts by leveraging LLM
to perform evolutionary operators p + Evo(pr...... .PP.))
5: Evaluation: s/ t f(p,, D)
6: Update: Pt +- (Pt-1,P) and + (St-1, 5/} based on the evaluation scores
7: end for
8: Return the best prompt, p", among the final population Pr: p" +- argmar ((,
Current advanced LLMs are typically interacted via black-box APIs, while the gradients and parame- ters are inaccessible. Evolutionary algorithms (EAs) are derivative-fict algorithms with exceptional accuracy and rapid convergence. Accordingly, we consider introducing EAs into discrete prompt optimization. However, to generate new candidate solutions, evolutionary operators typically edit the elements in current solutions independently, without considering the connections between them. This makes it challenging apply evolutionary operators on discrete prompts, which require coherence and readability. To address this challenge, we propose a synergistic approach that connects the natural language processing expertise of LLMs with the optimization capabilities of EAs, called EvoPROMPT. Specifically, LLMs generate new candidate prompts based on evolutionary operators, while EAs guide the optimization process to find the optimal prompts.
3

---

Published as a conference paper at ICLR 2024
Genetic Algorithm (GA) Implemented by LLMs
Query:
Please follow instruction step-by-step to generate better prompt.
1. Cross over the following prompts and generate a new prompt:
Now you are categorizer, your mission is to ascertain the scntiment of the provided text, either favorable unfavourable.
Prompt 1:
Prompt 2:
Assign a sentiment label the given sentence from ('negative', 'positive'] and return only the label without any other text.
Mutate the prompt generated in Step and generate final prompt bracketed with <prompt> and </prompt>.
Response:
Crossover
1. Crossover Prompt: Your mission is to ascertain the sentiment of the provided text and assign sentiment label from ['negative', 'positive'].
Mutate
2. <prompt> preemie-Deeeminee from l'negative', </proopp>>
Determine the sentiment of the given sentence and assign label
Figure GA process implemented by LLMs (Evo(-) in Algorithm 1). In Step 1, LLMs perform crossover the given two prompts (words in orange and blue are inherited from Prompt I and Prompt 2, respectively). Step 2, LLMs perform mutation on the prompt.
In order to implement EVoPROMPT in practice, it is necessary to instantiate it with specific algorithm of EAs. There are various types of EAs, and this paper, we consider two widely used algorithms, including Genetic Algorithm (GA) (Holland, 1975) and Differential Evolution (DE) (Storn Price, 1997). GA is among the most highly regarded evolutionary algorithms (Holland, 1975; 1992; Mitchell, 1998; Mirjalili et al., 2020) and DE has emerged as one of the most widely utilized algorithms for complex optimization challenges since its inception (Storn Price, 1997; Price, 2013; Das & Suganthan. 2010; Pant et al., 2020). In the following, proposed EvoPROMPT, and then instantiate EVoPROMPT with GA and DE respectively.
will first outline the
3.1 FRAMEWORK OF EVOPROMPT
EAs typically start with an initial population of N solutions (prompts in our setting), then iteratively generate new solutions using evolutionary operators (c.g., mutation and crossover) on the current population and update based on a fitness function. Following typical EAs, EVOPROMPT mainly contains three steps:
Initial population: Contrary to most existing automatic prompt methods that neglect priori human knowledge, we apply available manual prompts as the initial population to leverage the wisdom of humans. Besides, EAs typically start from random solutions, resulting in a diverse population and avoiding being trapped a local optimum. Accordingly, we also introduce some prompts generated by LLMs (Zhou et al., 2022) into the initial population.
each iteration, EvoPROMPT uses LLMs as evolutionary operators generate a new prompt based on several parent prompts selected from the current population. To accomplish this, we design steps the mutation and crossover operators for each specific type EAs, along with corresponding instructions guide the LLMs in generating
Evolution:
prompts based on these steps.
Update: We evaluate the generated candidate prompts on development set and retain those with superior performance, similar to the survival of the fittest in nature. The specific updating strategy may vary depending on the type of EAs used.
The algorithm stops when the number of iterations reaches predefined value. The details of EvoPROMPT are outlined in Algorithm 1. When instantiating EvoPROMPT with specific algorithm of EAs. the evolutionary processes need to be adjusted, and the key challenge to design the evolutionary operators discrete prompts.
4

---

Published as a conference paper at ICLR 2024
Differential Evolution (DE) Algorithm Implemented by LLMs
Query:
Please follow the instruction step-by-step to generate a betoer prompt.
1. Identify the different parts between the Prompt and Prompt 2:
Prompt Categorize the tweet according to has positive or negative sentiment.
Prompt 2: Carry out sentiment analysis for every sentence decide if it is positive
negative.
2. Randomly mutate the different parts
3. Combine the different parts Prompt selectively replace it with the different parts prompt.
in Step and generate
Prompt 3: In this task, you given sentences from product reviews. The task is
classity sentence positive as negative.
Cross the prompt in the Step with the following basic prompt and generate final prompt bracketed with <prompt> and </prompt>:
Here, you'll given sentences from reviews about products and you'll need decide it's positive negative review.
Basic Prompt:
Response:
1. Different parts:
"tweet' "sentence"
"Categorize" "Carry sentiment analysis"
2. "tweet" "review"
F(b (
"Categorize"-> > "Analyze"
"Sentiment analysis" -> "Sentiment identification"
F(b
New Prompt: In this task, you are given reviews about products. The task is to analyze each review and Idencify is positive or negative.
4. Final Prompt: <prompt> Here, you'll be given reviews about products and you'll need analyze each review and identify if it is positive or negative. </prompt>
Crossaver
DE process implemented by LLMs (Evo(-) in Algorithm 1). In Step 1, LLMs find the different parts (words in and between Prompt and Prompt (b c in typical DE). In Step 2. LLMs perform mutation (words in @ them (imitation of F(b c)). Next, LLMs incorporate the current best prompt as Prompt 3 with the mutated results Step 2, to generate a new prompt (counterpart of F(b- c) in DE). Finally, LLMs perform crossover upon the current basic prompt and the generated prompt in Step 3. See Figure 5 in Appendix B.2 for the complete response.
Figure 2:
3.2 INSTANTIATION WITH GENETIC ALGORITIIM
Selection In GA, parent solutions conventionally selected using the roulette wheel selection method, guided by their fitness values (Lipowski & Lipowska, 2012). Analogously, we employ the roulette wheel selection choose two parent prompts from the current population, based on their performance scores obtained on the development sets. Let s; denote the performance score of the i-th prompt within population containing N prompts. The probability of selecting the i-th prompt as parent can be expressed as P: = 8// 15=18
Conforming to the GA framework, we generate a new candidate prompt via two steps: 1) Crossover is performed between the parent prompts to produce a new offspring prompt that inherits characteristics from both parents; 2) Mutation applied the offspring prompt, introducing random alterations to certain elements. We formalize this two-stage operation into algorithmic instructions for guiding LLMs to implement Evo(.) in Algorithm The entire process is illustrated in Figure
Evolution
Update We employ straightforward selection strategy for updating the population: at each iteration, EvoPROMPT produces N new prompts, which are merged with the existing population of N prompts. Subsequently, the top N prompts, based their scores, retained to form the updated population. Accordingly, the overall quality of the population undergoes continuous enhancement, culminating in the selection of the best within the final population the optimal prompt.
5

---

Published as a conference paper at ICLR 2024
3.3 INSTANTIATION WITH DIFFERENTIAL EVOLUTION
Here, we begin with some preliminary knowledge of DE. Unlike GA, the solutions of DE are represented by numerical vectors. Each vector within the population is sequentially selected as base vector, denoted as X, which subsequently undergoes mutation and crossover. During mutation, mutated solution y is generated from randomly selected solution from the current population. The mutation is achieved by adding scaled difference between two distinct, randomly selected solutions and c to a, i.c., y = a + F(b - c), where is the scaled parameter.
Crossover is to generate trial solution x' [a',,.., [.,,]_. by choosing each parameter in the vector from either the basic solution x or the mutated solution y. Then, x is replaced with if x' is better than x. Within step-by-step evolution, DE ends with a population of high quality. A modified version of DE uses the current best solution as vector a to exploit information from the best one.
Evolution The evolutionary process of DE can be decoupled into three steps: 1) F(b - c): 2) y + F(b c); 3) Crossover of x and In EvOPROMPT based on DE, we follow the three steps to design the evolutionary process, as well as the corresponding instructions for LLMs to generate a new prompt based these steps illustrated in Figure 2:
Inspired by the differential vector in DE, we consider mutating only the different parts of two randomly selected prompts in the current population (Step and Step in Figure 2). The prompts in the current population are considered the current best ones. Accordingly, the shared components two prompts tend to have a positive impact on the performance, and thus need to be preserved.
A variant of DE employs the current best vector during the mutation process, where a mutated vector is generated by adding the scale of the differential vector the current best vector. Building upon this idea, we generate mutated prompt by selectively replacing parts of the current best one with the mutated different parts for combination. (Step 3 in Figure 2).
Crossover replaces certain components of basic prompt (i.e., candidate of the current population) with segments from the mutated prompt. This operation combines the features of two different prompts, potentially creating a new and improved solution (Step in Figure 2).
Update Following the standard DE, each prompt P; in the current population is chosen basic prompt in turn to generate a corresponding new prompt pa using the instruction in Figure 2. Then, the prompt with higher score, either p: p/,- is retained. Accordingly, the population size remains constant while the overall quality of the population is enhanced.
4
EXPERIMENTS
4.1 IMPLEMENTATION DETAILS AND BASELINES
With GPT-3.5 performing evolutionary operators, we optimize prompts using EVOPROMPT for the open-soune source Alpaca-7b (Taori et al., 2023) and closed-source GPT-3.5 (ext-davinci-0033 (Brown et al., 2020). We pick the prompt with the highest score on the development set and report its score on the test set. Results reported on Alpaca are averaged over random seeds and the standard deviation provided, while for GPT-3.5, we report results of one seed due to budget limitation. In our evaluation, we compare EVOPROMPT against three categorics of prompt-base approaches, detailed as follows:
Manual Instructions (MI): These serve as task-specific guidelines and are crafted based on established works, specifically referenced from Zhang et al. (2023b) for language understanding, Sanh al. (2021) for summarization, and Zhang et al. (2023c) for text simplification.
PromptSource (Bach et al., 2022) and Natural Instructions (NI) (Mishra et al., 2022b): These repositories aggregate human-composed prompts across diverse range of datasets.
APE (Zhou et al., 2022) and APO (Pryzant et al., 2023): APE employs an iterative Monte Carlo Search strategy, emphasizing on exploration. We reproduce it and initialize populations of equivalent sizes to that of EvOPROMPT. APO harnesses incorrectly predicted instances as ppseudo-gradient to iteratively refine the original prompt, which emphasizes exploitation. We reproduce APO binary classification tasks with the optimal manual prompt the initial one.

---

Published as a conference paper at ICLR 2024
Method
SST-2
CR
MR
SST-5
AG's News
TREC
Subj
Avg.
MI (Zhang et al,, 2023b)
93.68
91.40
88.75
42,90
70.63
50.60
49.75
71.07
(Mishra al, 2022c)
92.86
90.90
89.60
48.64
48.89
55.00
52.55
PromptSource (Rach et al,, 2022)
93.03
45,43
36,20
APE (Zhou et al,, 2022)
93,450044)
91.13
89.98
46.32/044)
71.76
58.73
64.18..59
73.80
APO (Pryzant al., 2023)
93.87/0.39
91.20
89.85
70.55
EvoPROMPT (GA)
91.27 95.13
90.07
49.91 (0.61)
72.81 (0.61)
64.000.16)
70.55
76.25
EVoPROMPT (DE)
94.75
91.40.0.04)
90.22 (.09)
49. (.73)
73.82 0.35)
63.73 (.54)
75.55 2.20
77.05
Table 1: Main results on language understanding (accuracy) on Alpaca-7b.
Alpaca
GPT-3.5
Method
ROUGE-I
ROUGE-2
ROUGE-L
ROUGE-1
ROUGE-2
ROUGE-L
MI (Sanh al., 2021)
35.92
11.16
31.67
43.95
17.11
39.09
APE (Zhou et al., 2022)
35.44
10.60(0.38)
31.80(0.50)
43.43
16.72
38.25
EVoPROMPT (GA)
38.46(145)
13.36.0755)
34.20
45.22 46.49
18.52
41.06
EvoPROMPT (DE)
39.46(0.51)
13.93.0.33
05.49.0.6))
19.49
41.96
Table 2: Main results on SAMSum dataset (summarization task) for Alpaca-7b and GPT-3.5.
4.2 LANGUAGE UNDERSTANDING
Datasets and Settings We first conduct experiments on language understanding tasks across 7 datasets to validate our methods, including sentiment classification (SST-2 (Socher et al., 2013),
MR (PANG, 2005), CR (Hu & Liu, 2004), SST-5 (Socher et al., 20)3)). topic classification (AG's News (Zhang et al., 2015), TREC (Voorhees & Tice, 2000)) and subjectivity classification (Subj (Pang & Lee, 2004)). To constrain the output label space, we prepend the demonstration consisting of one example per class before the test case. See Appendix for more details.
Main Results Table 1, shows that: 1) Compared with previous works on prompt generation and human written instructions, EvoPROMPT based on both GA and DE delivers significantly better results. 2) EVOPROMPT (GA) slightly better than EvOPROMPT (DE) on sentiment classification datasets. When it comes to topic classification datasets, Evo (DE) performs better. Notably, on the subjectivity classification task (Subj). EVoPROMPT (DE) exhibits a substantial improvement over its GA counterpart, achieving 5% accuracy advantage. This may be contributed by the exceptional ability of DE to evade local optima when the initial prompts are not of high quality.
4.3 LANGUAGE GENERATION
Datasets and Settings For language genera- tion, we evaluate our EVOPROMPT on text sum- marization and simplification tasks. For summa- rization, we adopt SAMSum (Gliwa et al., 2019), challenging and intricate dialogue summariza- tion dataset, and report ROUGF-11/2/L scores on Alpaca-7b and GPT-3.5.. For text simplification, which aims to simplify the source text while preserving its original meaning, we employ the ASSET dataset -Ala--Mancher benchmark known for its multiple reference translations. We apply SARI score (Xu et al., 2016) as the evaluation metric, an n n-gram-basse based scoring system extensively utilized for text editing tasks. Additional details regarding our experimental setup can be found in Appendix B.
Method
Alpaca
GPTT-3.5
MI (Zhang et al., 2023c)
43.03
43.80
APE (Zhou et al., 2022)
45.90(0.09)
46.71
EVOPROMPT (GA) EVOPROMPT (DE)
46.43(0.19)
47.36
(6.21
47.40
Table 3: Main results (SARI) on simplification (ASSET) for Alpaca-7b and GPT3.5.
et al., 2020),
The summarization and simplification results are presented in Tables and 3. EVoPROMPT achieves substantial performance gain over manually designed prompts, exhibiting an improvement over points in SARI scores across both Alpaca and GPT-3.5 API. Furthermore, EvoPromPT consistently outperforms the APE approach across the evaluated scenarios, indicating
Main Results
7

---

Published as a conference paper at ICLR 2024
25
EvoPrompt (DE) EvoPrompt (GA)
Normalized Score
20
Taak
Figure 3: Normalized scores BBH tasks for EvoPROMPT (GA) and EVOPROMPT (DE).
that the generated prompts effectively harness the capabilities of LLMs for superior performance. Moreover, EvoPROMPT (DE) notably outperforms EvoPROMPT (GA) in the summarization task, while demonstrating comparable performance in the simplification task. This suggests that the DE variant is particularly effective for more complex language generation tasks like summarization.
4.4 BIG BENCH HARD (BBH)
Datasets and Settings To validate our methods on diverse tasks, we apply BBH (Suzgun et al., 2022) including a suite of 23 challenging BIG-Bench tasks requiring multi-step reasoning. Since these tasks are challenging, we focus on optimizing the prompts for GPT-3.5. We sample subset from the test prompt "Let's think step by step." (Kojima et al., 2022) with 3-shot Chain-of-Thougee demonstrations (following Fu et (2023)) on the test set. We use task IDs to simplify the denotation of each task and remove one since the accuracy already reaches 100% with the manual prompt. Please see Appendix C.2 and Table 17 for details, as well as further comparisons with previous works.
the development set and report the normalized scores' in comparison to the
Main Results EVOPROMPT obtains better prompts for all tasks (Figure 3). Specifically, Evo- PROMPT (DE) achieves up to a 25% improvement with an average of 3.5%, whereas EvoPROMPT (GA) reaches a peak improvement of 15% with 2.5% average. Though for some tasks the GA coun- terpart outperforms the DE version, the performance gap remains relatively small (i.e., around 1%). Meanwhile, EVOPROMPT (DE) surpasses EVOPROMPT (GA) by over 2% on 6 tasks. Accordingly, the DE version is generally good choice for these challenging tasks.
ANALYSIS
5.1 DESIGNS IN GA
For EVOPROMPT (GA), apply the roulette wheel selection strategy by default to select parental prompts, contributing to the offspring. To further ex- plore the effect of various selection strategies, we compare our approach with another two popular strategies, i.e., tournament (Wikipedia contributors, 2023) and random selection, as presented in Table 4. We observe that EVoPrOMPT (GA) with roulette wheel achieves higher scores, showcasing the effectiveness of this selection method.
Strategy
SST-5
ASSET
Avg.
random
48.67
(6.32(0.32)
47.50
tournament
49.70(0.60)
(6.29(0.18)
48,00
wheel
49.91
46.43
48.17
Table 4: Designs in EvoPROMPT (GA).
5.2 DESIGNS IN DE
For EvoPROMPT (DE), we delve into two key design considerations in adapting the evolutionary operators of DE to discrete prompts: 1) mutation different parts, and 2) choosing the current top-performing prompt as "Prompt 3" Figure 2. We assess the impact of these design choices on
'The accuracy difference between given prompt and the baseline prompt "I.et's think step by step." A score of corresponds the normalized score of the baseline prompt.
8

---

Published as a conference paper at ICLR 2024
two datasets: Subj, understanding dataset where EvOPROMPT (DE) outperforms EVOPROMPT (GA), and ASSET, a generation dataset where both variants demonstrate similar performance.
Mutation on Different Parts To illustrate the benefits of mutating only the different parts, we replace the first two steps in Figure with the instruction "Randomly mutate Prompt and Prompt 2" allow mutation on all contents in Prompts and 2, denoted as "All" in Table 5, Meanwhile, the original design EVOPROMPT, which mutates only the different parts, is denoted as "Diff". As shown Table 5, the design of mutation on only the different parts consistently yields performance gains across two tasks.
Mutation
Prompt 3
Subj
ASSET
Diff All
best
75,55
(0.27
best
(9.87(0.82)
(5.73
Diff Diff
random
69.82/2.47)
(0.89)))77)
eliminate
(9.07(4.21)
45.90(0.23)
Table 5: Designs in EvoPROMPT (DE).
Selection of Prompt Applying one of the variants of the DE algorithm, in EVOPROMPT (DE), we pick the best prompt in the current population as Prompt in Figure 2. We validate this design via the following settings: 1) Prompt 3 is randomly sampled from the current population, denoted as "random" Table 2) Eliminate the use of Prompt 3 by letting the Basic Prompt directly cross over with the mutated different parts (i.e., remove Step 3 in Figure 2), denoted as "eliminate" in Tabel 5. Table clearly demonstrates the importance of introducing Prompt 3. Moreover, it is shown that choosing the best prompt as Prompt 3 is more effective than random sampling.
5.3 POPULATION INITIALIZATION
We investigate the effect of initial population quality on EvoPROMPT. We conduct pilot experiments to sort the prompts (designed manually or generated by GPT-3.5) according to their performance on the dev We then select bottom, random and top prompts along with their corresponding variations as initial prompts. These variations are generated using the resampling template designed in Zhou et al. (2022), shown Figure 4 in the Appendix B.2, which is used to introduce randomness to the initialization.
Initialization
GA
DE
bottom- 100
(7.80(0.22)
48 48.64:0.15)
random-10
(9.34(0.53)
50.03
random-5 + var-5
49.84(1.49)
49.53(1.04)
top-10 10 top-5 var-5
(9.62(1.00)
49.61
(9.91(0.61)
(1.8)(
Table Ablations of the initial population on SST-5, where top-n, random-n, bottom-n de- notes the pop-pefforming randomly selected, nottom--erforming prompts, and var-n de- notes the number of generated n variations.
Table demonstrates that: 1) Crafted design of ini- tial prompts is not essential, as randomly selecting prompts can achieve a similar performance to select- ing the top-performing ones; 2) When selecting the lop-performing prompts, introducing randomness by allowing GPT-3.5 to generate variations can lead to a slight improvement in overall performance; however, when randomly selecting prompts, there is no need to introduce additional randomness for EvoPROMPT (DE); 3) When using cop-perfrrming initial prompts, EvoPrOMPT (GA) per- forms slightly better than EvOPROMPT (DE); however, when starting with nottom-performe initial prompts, EVOPROMPT (DE) outperforms EvOPROMPT (GA), which indicates that DE is better choice when the available manual prompts are not of high quality.
CONCLUSIONS
We introduce EVoPROMPT to optimize discrete prompts, which connects LLMs with evolutionary algorithms. Extensive experiments on 31 datasets demonstrate the superiority of EvoPROMPT, yielding consistent performance gains over both manual instructions and existing methods. Besides, We validate that LLMs can serve as an effective, interpretable interface for implementing evolutionary algorithms like GA and DE. While this study focused on EAs, the extensibility of our approach opens avenues for applying LLMs to other conventional algorithms, such as particle swarm optimization (PSO) (Kennedy & Eberhart, 1995), ant colony optimization (ACO) (Dorigo & Gambardella, 1997) and more recent Quality- Diverrtt (QD) optimization algorithms. Our findings aim to inspire future research at the intersection of L.MMs and traditional algorithms, encouraging innovative applications.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was partly supported by the National Key Research and Development Program of China (No. 2020YFB1708222 and the Shenzhen Science and Technology Program UCY1202208181010000
REFERENCES
Fernando Alva-Manchegg, Louis Martin, Antoine Bordes, Carolina Scarton, Benoît Sagot, and Lucia Specia. Asset: A dataset for tuning and evaluation of sentence simplification models with multiple rewriting transformations. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pp. 4668-4679, 2020.
Stephen Bach, Victor Sanh, Zheng Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Févry, et al. Promptsource: An integrated development environment and repository for natural language prompts. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pp. 93-104, 2022.
Janez Brest, Sao Greiner, Borko Boskovic, Marjan Mernik, and Viljem Zumer. Self-adapting control parameters differential evolution: A comparative study on numerical benchmark problems. IEEE transactions evolutionary computation, 1066):646-657, 2006.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Angelica Chen, David M Dohan, and David R So. Evoprompting: Language models for code-level neural architecture search. arXiv preprint arXiv:2302. 14838, 2023.
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009,
Swagatam Das and Ponnuthurai Nagaratnam Suganthan. Differential evolution: A survey of the state-of-the-art. IEEE transactions on evolutionary computation, 15(1):4-31, 2010.
Swagatam Das, Sankha Subhra Mullick, and Ponnuthurai N Suganthan. Recent advances in differen- tial evolution-an updated survey. Swarm and evolutionary computation, 27:1-30, 2016.
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. Riprompt: Optimizing discrete text prompts with reinforcement learning. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pp. 3369-3363390 13999-339,2000 2022.
Marco Dorigo and Luca Maria Gambardella. Ant colony system: cooperative learning approach to the traveling salesman problem. JEEE Transactions on evolutionary computation, 1(1):53-66 66, 1997.
Yao Fu, Litu Ou, Mingyu Chen, Yuhao Wan, Hao Peng, and Tushar Khot. thain-of-thought hub: A continuous effort to measure large language models' reasoning performance. arXiv preprint arXiv:2305. 17306, 2023.
Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. Samsum corpus: A human- annotated dialogue dataset for abstractive summarization. arXiv preprint 1rXiv:1911.12237. 2019.
Yiduo Guo, Yaobo Liang, Chenfei Wu, Wenshan Wu, Dongyan Zhao, and Nan Duan. Learning to program with natural language. arXiv preprint arXiv:2304. 10464, 2023.
John H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975. ISBN 02625811 16.
10

---

Published as a conference paper at ICLR 2024
John H Holland. Adaptation in natural and artificial systems: introductory analysis with applica- tions to biology, control, and artificial intelligence. MIT press, 1992.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In KDD, pp. 168 107-177,5500 2004.
Srinivasan Iyer, Xi Victoria Lin, Ramakanth Pasunuru, Todor Mihaylov, Daniel Simig, Ping Yu, Kurt Shuster, Tianlu Wang, Qing Liu, Punit Singh Koura, et al. Opt-iml: Scaling language model instruction meta learning through the lens of generalization. arXiv preprint arXiv:2212.12017, 2022.
Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig. How know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438, 2020.
James Kennedy and Russell Eberhart. Particle swarm optimization. In Proceedings of ICNN*95- international conference on neural networks, volume 4, pp. 1942-1948. IEEE, 1995.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22199-22211 2022.
Pier Luca Lanzi and Daniele Loiacono. Chatgpt and other large language models evolutionary engines for online interactive collaborative game design. arXiv preprint arXiv:2303.02/55. 2023.
Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O. Stanley. Evolution through large models. arXiv preprint arXiv:2206.0888 08896, 2022.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. In EMNLP, pp. 3045-3059, 2021.
Bei Li, Rui Wang, Junliang Guo, Kaitao Song. Xu Tan, Hany Hassan, Arul Menezes, Tong Xiao, Jiang Bian, and JingBo Zhu. Deliberate then generate: Enhanced prompting framework for text generation. arXiv preprint ar05v:2305. 19835, 2023.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4597-499, 2021.
Adam Lipowski and Dorota Lipowska. -hhlettee-weell selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, (91(6):2193-211 2012.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Lam Tam, Zhengxiao Du Zhilin Yang, and Jie Tang. P-tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprint 2rXiv:2//0.076// 2021a.
Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. Gpt understands, too. arXiv preprint arXiv:2103.10385. 2021b.
Elliot Meyerson, Mark J Nelson, Herbie Bradley, Arash Moradi, Amy K Hoover, and Joel Lehman. Language model crossover: Variation through few-shot prompting. arXiv preprint arXiv:2302. 12170, 2023.
Seyedali Mirjalili, Jin Song Dong, Ali Safa Sadiq, and Hossam Faris. Genetic algorithm: Theory, literature review, and application in image reconstruction. Nature-Inspired Optimizers: Theories, Literature Reviews and Applications, pp. 69-85, 2020.
Swaroop Mishra, Daniel Khashabi, Chitta Baral, Yejin Choi, and Hannaneh Hajishirzi. Reframing instructional prompts to gptk's language. In Findings of the Association for Computational Linguistics: ACI. 2022, pp. 512- 2022a.
11

---

Published as a conference paper at ICLR 2024
Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi. Cross-task generalization via natural language crowdsoureing instructions. Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3470-3487, 2022b.
Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi. Cross-task generalization via natural language crowdsoureing instructions. ACI,, 2022c.
Melanie Mitchell. An introduction to genetic algorithms. MIT press, 1998.
Saan-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504. 0499, 04909,
2015.
OpenAl. Gpt-4 technical report. arXiv preprint arXiv:2303.08777 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744 2022.
Bo PANG. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In ACL, 2005.
Bo Pang and Lillian Lee. sentimental education: Sentiment analysis using subjectivity summariza- tion based on minimum cuts. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACI.004) pp. 271-278, 2004.
Millie Pant, Hira Zaheer, Laura Garcia--ernaadez, Ajith Abraham, et al. Differential evolution: A review more than two decades research. Engineering Applications of Artificial Intelligence, 90:103479, 2020.
Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. Grips: Gradient-free, edit-based instruction search for prompting large language models. arXiv preprint urXiv:2203.0728! 2022.
Kenneth V Price. Differential evolution. In Handbook of optimization: From classical modern approach, pp. 187-214. Springer, 2013.
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with" gradient descent" and beam search. arXiv preprint arXiv:2305.0344 2023.
Chengwei Qin, Aston Zhang, Zhuosheng Zhang, Jiaao Chen, Michihiro Yasunaga, and Diyi Yang. Is chatgpt general-purpose natural language processing task solver? arXiv preprint arXiv:2302.06476, 2023.
Luis Miguel Rios and Nikolaos V Sahinidis. Derivative-free optimization: review algorithms and comparison of software implementations Journal of Global Optimization, 56: 36:1227-129, 2013.
Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, 7aid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, al. Multitask prompted training enables zero-shot task generalization. arXiv preprint w:Xiv:2110.08200 2021.
Timo Schick and Hinrich Schütze. Exploiting cloze-questions for few-shot text classification and natural language inference. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 255-269, 2021.
Chufan Shi, Haoran Yang, Deng Cai, Zhisong Zhang, Yifan Wang, Yujiu Yang, and Wai Lam. A thorough examination of decoding methods in the era of llms. arXiv preprint 2402.0692.. 2024.
Weijia Shi, Xiaochuang Han, Hila Gonen, Ari Holtzman, Yulia Tsvetkov, and Luke Zettlemoyer. Toward human readable prompt tuming: Kubrick's 's the shining is good movie, and good prompt too? arXiv preprint arXiv:2211. 10539, 2022.
12

---

Published as a conference paper at ICLR 2024
Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 4222 4235, 2020.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In EMNLP, pp. 1631-1642, 2013.
Rainer Storn and Kenneth Price. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, Journal of global optimization, 11:341-359, 1997.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sehastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261, 2022.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-follooinn Ilama model. 2023.
https://gt thub. watss-laabsstaarrrrarrro
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anna Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Jakob Vesterstrom and Rene Thomsen. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In Proceedings of the 2004 congress on evolutionary computation (IEEE Cat. No. 04TH87533, volume pp- 1980-1999 1987. IEEE, 2004.
Ellen M Voorhees and Dawn Tice. Building question answering test collection. Proceedings of the 23rd annual international ACM SIGIR conference Research and development in information retrieval, pp. 200-207, 2000.
Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing nlp. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) pp. 2153-2162, 2019.
Yifan Wang, Qingyan Guo, Xinzhe Ni, Chufan Shi, Lemao Liu, Haiyun Jiang, and Yujiu Yang. Hint-enhanced in-context learning wakes large language models up for knowledge-intentte tasks. arXiv preprint arXiv:2311.0194 2023.
Wikipedia contributors. Tournament selection Wikipedia, the free encyclopedia. https: // en. wikipedia. org/w//ndew/.. pttp:///ideee.ppptttiteeeoeooeee [Online; accessed 26- 26-September-20233.
2023.
Wei Xu, Courtney Napoles, Ellie Pavlick, Quanze Chen, and Chris Callison-Burch Optimizing statis- tical machine translation for text simplification. Transactions of the Association for Computational Linguistics, 4:401-415, 2016.
JD Zamfirescu- Pereira,, Richmond Wong, Bjoern Hartmann, and Qian Yang. Why johnny can't prompt: how non-ai experts try (and fail) design I1m prompts. In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pp. 1-21, 2023.
Jingqiao Zhang and Arthur C. Sanderson. Jade: Adaptive differential evolution with optional external archive. IEEE Transactions Evolutionary Computation, 13(5):945-958, 2009. doi:
10.1109/EEY.22009204444 200.141613.....
Ningyu Zhang. Luoqiu Li, Xiang Chen, Shumin Deng, Zhen Bi, Chuanqi Tan, Fei Huang, and Huajun Chen. Differentiable prompt makes pre- trainaine language models better few-shot learners. In International Conference Learning Representations, 2021.
13

---

Published as a conference paper at ICLR 2024
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre- trained transformer language models. arXiv preprint arXiv:2205.01066 2022.
Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez. Tempera: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023a.
Wenxuan Zhang, Yue Deng, Bing Liu, Sinno Jialin Pan, and Lidong Bing. Sentiment analysis in the era of large language models: A reality check. arXiv preprint 10X0v:2305.15003, 2023b.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. NeurlPS, 28, 2015.
Yue Zhang, Leyang Cui, Deng Cai, Xinting Huang, Tao Fang, and Wei Bi. Multi-task instruction tuning of Ilama for specific scenarios: A preliminary study on writing assistance. arXiv preprint 1322,5 2023c.
Mingkai Zheng, Xiu Su, Shan You, Fei Wang, Chen Qian, Chang Xu, and Samuel Albanie. Can gpt-4 perform neural architecture search? arXiv preprint arXiv:2304. 10970, 2023.
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human- level prompt engineers. In The Eleventh International Conference on Learning Representatios, 2022.
Kaijie Zhu, Jindong Wang. Jiaheng Zhou, Zichen Wang, Hao Chen, Yidong Wang, Linyi Yang, Wei Ye, Neil Zhenqiang Gong, Yue Zhang. al. Promptbench: Towards evaluating the robustness of 2023.
large language models on adversarial prompts. arXiv preprint
14

---

Published as a conference paper at ICLR 2024
Algorithm 2 Discrete prompt optimization: EVOPROMPT (GA)
Require: Initial prompts Po [P1, P2. . )N), size of population N, dev set D
1: Initial fitness evaluation: S0 < {8: f(p.. D) E [1,
2: for to do
T: Number of iterations
3: for 1o N do
4: Selection based on fitness using roulette wheel: Pri: Prz P1-1
5: Evolution: P <- GA(pris Pra) (Refer to Figure 1)
6: Evaluation: 8; f(p,, D)
7:
end for
8:
S + {sili E N],, P/ P/ t- E
9: Update score: St + 15
10: Update: Pt + (P:-NN(P.11..
using S.-1. S.
11: end for
12: Return the best prompt, p", among the final population Pr: p" +- argmar f(p, D)
Algorithm 3 Discrete prompt optimization: EVoPROMPT (DE)
Require: Initial prompts Po {PI,P2, P2, ........P..... .PN) size of population N, dev set 'D
1: for = 1 to do
b> T: Number of iterations
2:
for p; in Pt-1 do
3: Sample donors: Pr1, Py2 ~ Pa-1, f
4:
Evolution: pt: t DE Pris Przs Pbest) where Phest is the current best prompt. (Refer D Keep the better in the population
to Figure 2)
5:
Selection: P arg max (p, D)
6: end for
7: Update: P. [1,
8: end for
9: Return the best prompt. p", among the final population Pr: p" + argmarrpeP f(p, D)
A DETAILS OF ALGORITHM IMPLEMENTATION
We instantiate EVOPROMPT representative evolutionary algorithms, GA and DE. Though both algorithms use consistent general selection processes, creating offspring, and updating. it is worth noting that the selection strategies, ways of mutation and crossover, and the updating strategies in these two algorithms are different. The specific algorithms for each of them are shown in Algorithm 2 and Algorithm 3.
B EXPERIMENTAL SETTINGS
B.1 DATASETS
Table 7 shows the statistics of the text classification, simplification and summarization datasets. For Big-Bench Hard, We use serial numbers denote 22 tasks, the descriptions are reported in Table 17. Note that for the task of "web of lies", the accuracy of the baseline is 100%, so here we have not included this task for prompt optimization. Additionally, both tasks of "logical deduction objects" and "tracking shuffled objects" have three sub-tasks.
Template for Variation
B.2 TEMPLATES
Generate variation following
instruction while keep semantic meaning. Input: <prompe> Output:
Templates for Task Implementation For different mod- els, we apply different templates shown Table 8, and 10, referring to the previous works (lyer et al., 2022; Taori et al., 2023; Zhang et al., 2023b; Li et al., 2023; Fu et al., 2023).
Figure 4: Template used for resam- pling (Zhou al., 2022).
15

---

Published as a conference paper at ICLR 2024
Dataset
Type
Label space
Test
SST-2
Sentiment
[positive, negative)
1,821
CR
Sentiment
(positive, negative)
2,000
MR
Sentiment
(positive, negative) [terrible, bad. okay, good, great]
2,000
SST-5
Sentiment
2,210
AG's News
News topic
[World, Sports, Business, Tech)
7,600
TREC
Question topic
(Description, Entity, Expression, Human, Location, Number] (subjective, objective)
500
Subj
Subjectivity
2,000
SAMSum
Summarization
819
ASSET
Simplification
359
Table 7: Statistics for natural language understanding and generation datasets used in this work.
Template for Prompt Generation We apply the resampling template, shown in Figure 4, to generate variations of manual initial prompts. For our EvoPROMPT, the complete DE algorithm implemented by LLMs is shown in Figure 5. For both DE and GA, we prepend a one-shot example of the algorithm execution, guiding LLMS to operate precisely.
INSTRUCTIONAL PROMPTS
Below is an instruction that deseribes a task, paired with an input that provides further context. Write a response that appropriately completes the request.
# ## Instruction:
<PROMPT>
# # Input: <INPUT>
# # Response: <COMPLETE>
Zero-shot Example:
Below is an instruction that describes a task, paired with an input that provides further context. Write response that appropriately completes the request.
# # # Instruction:
Please perform Sentiment Classification task. Given the sentence, assign sentiment label from l'negative', "positive],, Return label only without any other text.
# # Input:
bcautifully observed, miraculously unsentimental comedy-drama.
## Response:
<COMPLETE>
Table 8: Template used for Alpaca (referring Taori al. (2023)).
B.3 HYPER PARAMETERS
The parameters for the experiments are shown in Table 11. For evolutionary algorithms implemented by GPT-3.5, following previous work (Shi et al., 2024), we use Top-p decoding (temperature-0.5, P = 0.95). For the task implementation, we use greedy decoding and the default temperature for Alpaca. For the generation tasks implemented by GPT-3.5, the temperature is 0.0.
16

---

Published as a conference paper at ICLR 2024
Differential Evolution (DE) Algorithm Implemented by LLMs
Query:
Please follow the instruction step-by-step generate
prompt.
Identify the different parts between the Prompt and Prompt 2:
Prompt 1: Categorize the tweet according to if it has positive or negative sentiment.
Prompt 2: Carry out sentiment analysis for every sentence to decide positive or negative.
Randomly mutate the different parts Combine the different in Seep 2 and generate new prompt.
with Prompt 3, selectively replace it with the different
Prompt 3: this task, you are given sentences from product reviews. The task to classify sentence as positive
negative.
Cross the prompt in the Step with the following basic prompe and generate final
prompt bracketed with <rommpe> and </prompt>;
Basic Prompt: Here, you'll be given sentences from reviews about products and you'll need decide it's positive or negative review.
Response:
Identifying the different between Prompt and Prompr
Prompt 1: Categorize the tweet according
positive negative sentiment.
Prompt 2: Carry sentiment analysis for every sentence decide if it is positive
negarive.
Different
"tweet" vs 'sentence'
"Categorize" vs 'Carry out sentiment analysis"
Randomly mutate different parts:
"tweet" "review"
"Categorize" ->> "Analyze"
"Sentiment analysis' -> 'Sentiment identification"
Combine the different parts in Step and generate
with Prompt 3, selectively replace with the different prompt:
Prompt 3: In this task, you are given sentences from product reviews, The task is to classiff sentence positive or as negative.
Prompt: this you given feviews about products. The task analyze each review and ddettiff positive negative.
4. Cross over the prompt in Step 3 with the following basic prompt and generate final prompt bracketed with <prompt> and </prompt>:
Basic Prompt: Here, you'll be given sentences from reviews about products and you'll need to decide if it's positive or negative review.
Crossover
Final Prompt: <prompt> Here, you'll be given reviews about products and you'll need to analyze each review and identify is positive or negative. </prompt>>>
Figure DE algorithm implemented by LLMs for discrete prompt optimization with complete response (Evo(-) in Algorithm 1). In Step 1, LLMs find the different parts (words in and
between Prompt and Prompt (b e in typical DE). Step LLMs perform mutation (words in
) on them (imitation of F(b- c)). Next, LLMs incorporate the current best prompt as Prompt with the mutated results in Step 2, to generate a new prompt (counterpart of a + F(b c) DE). Finally, LLMs perform crossover upon the current basic prompt P; and the generated prompt in Step
17

---

Published as a conference paper at ICLR 2024
TEMPLATE FOR SIMPLIFICATION
<PROMPT>
<INPUT>
The simplification of the sentence is <COMPLETE>
Zero-shot example:
Simplify the text.
Subsequently. in February 1941, 600 Jews were sent to Buchenwald and Mauthausen concentration camps.
The simplification of the sentence is <COMPLETE>
TEMPLATE FOR SUMMARIZATION
<PROMPT>
<INPUT>
TL:DR: <COMPLETE>
Zero-shot example:
How would rephrase that in few words?
Theresa: have you been Tom's place? Luis: yes, it's nice Marion: He invited us for dinner Adam: where is it? Marion: outside city Adam: where exactly? Marion: Fiesole Luis: very nice!
TL:DR: <COMPLETE>
Table 9: Templates of summarization (following Sanh al. (2021); Qin et al. (2023)), simplification (following Li et al. (2023)) and the corresponding zero-shot examples.
ATPPLATE FOR BIG-BENCH HARD
<DESC> Q: <INPU>> A: <PROMPT> <COMPLETE>
Zero-shot example:
Questions involve enumerating objects and asking the model count them. Q: have flute, a piano, a trombone, four stoves, a violin, an accordion, a clarinet, drum, two lamps, and trumpet. How many musical instruments do I have?
A: Let's think step by step. <COMPLETE>
Table 10: Template for Big-Bench Hard (following Suzgun et al. (2022)) used for GPT-3.5 and the corresponding zero-shot examples. <DESC> refers the specific description of each task.
18

---

Published as a conference paper at ICLR 2024
46.4
74
46.3
Score ASSET
Score on Solb)
46.2
Score on
72
46.1
46.0
70
68.5
46.9
60
48.0
Size
Size
Size
DE
GA
Figure 6: Effect of population size on SST-5 (left), Subj (middle), and ASSET (right), All the results averaged over random seeds.
Text Classification The population of prompts is initialized with widely used in- structions in the previous works (Mishra al., 2022b; Zhang et al., 2022). We para- phrase and rewrite them to initialize the population. The size the development set is 200. We report the results on the full test set (the same as the previous re- lated works (Deng al., 2022; Zhang al., 2023a)), as shown in Table 11.
Task LM
||
IPopulationl
iStepsl
IDevl
IShotsl
Text classification
Alpaca-7b
||
10
Text Generation
Alpaca-7b GPT-3.55
10
10
100
0
10
10
100
0
Big-Bench Hard
GPT-3.5
10
10
Table 11: Settings for experiments. IShotsl refers to the number of examples
demonstration. For the text classification task, set the value as 1, which means we prepend with sample of each category, to constrain the output in the label space.
Text Generation For the initial popula- tion, we collect instructions for summa- rization and simplification from Li et al. (2023); Sanh et al. (2021); Zhang et al. (2023c) and augment them to the expected size (10 in our setting), either written manually or generated by GPT-3.5.
C ADDITIONAL RESULTS
C.I PARAMETERS IN EVOLUTIONARY ALGORITHMS
Effect of Population Size Intuitively, a trade-off exists between the performance and the overhead caused by the population size. We explore the performance of EvoPROMPT (DE) and EvoPROMPT (GA) respectively at varying population sizes from to 12. The results are plotted in Figure
For classification datasets, the size increases, curves for DE and GA show ascending trend. Furthermore, the increase DE attributed to population diversity was greater than that in GA since DE focuses different parts. Differences among prompts within populations bring about substantial mutations, leading DE to explore potential prompts since keeping common parts balances exploration and exploitation effectively.
For the relatively simple generation task (i.c.. ASSET), a population size of 6 demonstrates comparable performance to population size of 10, though with 2.5-fold increase overhead. This suggests that for relatively simple tasks large populations are unnecessary, while for complex tasks (i.e., Subj). larger population with diversity brings improvement.
Effect of Number of Iterations To further explore the process of convergence, for SST-5, Subj and ASSET, we plot the best and average scores on the development set for EvoPROMPT for DE and GA over the whole population after each iterative step (Figure 7). Curves of best and average scores gradually converge with an increasing trend as evolution proceeds, indicating that the population's quality whole is steadily increasing the evolution process.
19

---

Published as a conference paper at ICLR 2024
0.500
Score on SST-5
0.475
Score on Sub]
Score on ASSET
0.450
0.70
48.0
0.425
45.5
0.400
2
10
10
10
lleration
Iteration
Iteration
GA-avg
DE-avg
Figure 7: The best and average scores of each iteration on SST-5 (left), Subj (middle), and ASSET (right) development set on Alpaca-7b. All the results are averaged over random seeds.
APE Prompt (DE)
EvoPrompl (GA)
Normalized
04
65
06
14
15
16
19
Figure 8: Normalized scores on BBH tasks for APE, EVoPROMPT (GA) and EvoPROMPT (DE).
C.2 COMPARISON ON BBH TASKS
APE (Zhou et al., 2022) optimizes the Chain-of- Thouught (CoT) prompt for reasoning tasks InstructGPT. Considering that both InstructGPT and GPT-3.5 belong to the GPT family and may observe similar trends, evaluate the CoT prompt proposed by APE, "Let's work this out in step by step way to be sure we have the right answer.". on reasoning tasks and plot the 3-shot performance in Figure 8. For simplicity, we use the same initial population for all the BBH tasks without priori knowledge of each task. In future works, by incorporating task-specific prompts, either manually designed generated by LLMs, we may further enhance the performance.
Method
Avg.
baseline
71.49
APE
71.85
EVOPROMPT (GA)
74.18
EXOPROMPT (DE)
75.03
Table 12: Average accuracy over 23 BBH tasks for different methods.
SST-5 EvoPROMPT (GA)
Subj EvoPROMPT (GA)
EVoPROMPT (DB)
APE
EvOPROMPT (DE)
Same iteration
iterations
15
tokens
5.39 M 45.79
5.40
5.52 M
5.66 M
5.73 M
5.93 M
score
50.23
49.23
67.20
70.10
79.35
Until convergence
iterations
7
11
15
15
17
tokens
5.39 M
4.20
6.75 M
5.66 M
5.73
6.72 M
score
50.23
51.13
70.10
79.35
Table Number of iterations, tokens within the API requests (including prompt optimization and evaluation) and the corresponding score for methods and APE. We choose the iteration that APE converges as the Same iteration for comparison. Until convergence means that the improvement of the average score is less than 0.3% for continuous two iterations.
20

---

Published as a conference paper at ICLR 2024
Average length prompls
Varianoe of the prngpt
Average number new words
Velue
Boration
Boration
Rerafion
(a) Average length over the population after each step.
(b) Variance of prompt length over the population of each step.
(c) Number of new words generated after each step.
Figure 9: Statistics about the prompt length, including average values over the whole population (a), variance over the prompt length (b), and number of new words evolved after each step (c). Note that all the values are averaged over 8 datasets, including 7 understanding datasets and one simplification dataset, and random seeds.
C.3 COST ANALYSIS
Overhead mainly comes from prompt evaluation and generation. For evaluation, our overhead is N D * T, where N is the size of the population, |D| is the size of the development set, and T is the number of iterations. These parameters differ from the task and can be found in Appendix B.3. For the cost from prompt generation, the cost mainly depends the total number of API requests is * T * (1 + DI). the same as APE. Moreover, given that the API of LLMs is typically billed based the number of tokens used, also estimate the total number of tokens used in the API requests during the prompt optimization process, as shown Table 13. All the scores reported are over the test set on one random seed. We analyze the overhead mainly from two aspects: 1) the performance of our methods compared with APE under the same number of iterations; 2) the performance until convergence measured by the average score on the dev set.
the number of API results, T N. So
We can observe that with the same number of iterations, both GA and DE outperform APE signifi- cantly while introducing only a slight overhead terms of the number of tokens. The convergence rates of APE and GA are similar while DE is slightly slower, but delivers better performance. This implies the relatively high ceiling of EvoPROMPT.
C.4 ANALYSIS PROMPT
Diversity Analysis We further investigate the diversity of prompts generated by GA and DE after each iterative step respectively. We mainly plot the average prompt length, variance and number of new words mutated after each step, shown in Figure 9. It can be observed that EvoPROMPT (DE) generates longer prompts with higher variances than EvOPROMPT (GA), which implies that DE prefers exploration for diversity. In the latter iterations, DE mutates more words than GA, and thus shows better potential to escape from the local optimum.
Optimal Prompts We release the optimal prompts generated by EVOPROMPT for understanding (Table 14), text simplification (Table 16), summarization (Table 15) and BBH tasks (Table 17, 18).
D FUTURE WORKS
There are several promising directions for future investigation:
Based on our framework, more applications can be explored, including game levels generation, text-to-images generation, non-trivial NP-hard problems (e.g. traveling salesman problem), etc.
There exist many variants of DE and we give priority to the most canonical and classical ones for current exploration. In future work, it will be interesting consider more advanced DE- variants (Das et al., 2016; Das Suganthan, 2010). For example, some recent DE-variants have been investigating adaptive control parameters. The main challenge in applying these variants to
21

---

Published as a conference paper at ICLR 2024
Datasel
Method
Content
Score
Manual Instruction
perform Sentiment Classification posilive') I. Return label only without any other toxt.
sentence, assign label ('negarive'
SST-2
Instruction
you are given sentences from sentiment of the senience is positive or as "temible" if the sentiment of the sentence is negarive. Does the following sentence have posilive or negative sentiment?
sentence as "great"
PromptSounce
93.03
EvoPROMPT
the movic
classify
possivve or negative.
Manual Instruction
Please perform Sentiment Classificttion task. Given the
assign semiiment label from ''negutive',
91,40
positive') Return only without any
Natural Instruction
In this you given sentences from reviews. The classify sentence "great" the sentiment the sentence is positive as categorize each
90.90
sentimnt the sentence is negarive.
KVOPROMPT
Analyze
"positive" 'neguiive..
Manual Instruction
Please perform Sentiment Clusification task. Given the posilive') J. Return only without any
semimmet label from ''segutive',
88.75
Natural Instruction
In this you sentence is positive as "temible"
sentences from movie reviews. The classify
the the sentence negative.
89.60
sentiment
RVOPROMPT
Idearify i movie review positive negative by accunstely categorizing input-ooiput either positive' or "negative.
Manual Instruction
Semimmnn Classification task. Given sentence, assign sentiment label l'tamible", 42.90
SST-3
'bad', 'okay", "godd" "grnn") Return label only without any other text.
Natural Instruction
you given sentences
movie reviews, Based on given review, classiff it
five classes: (1) terrible, (2) bud, (3) okay, (4) good, and (5) great.
EvoPROMPT
Have your friend evaluate the they had just seen provide summary opinion (e.g. terrible, okay, good, or great) to determine the sentiment the movie review.
Manual Instruction
Please perform "Basiness,, "Toch"]. Return label only without any other text.
Classification task.
news item, assign a
("World', 'Sports',
AG's News
Natural Instruction
In this lack, you are given news article. Your task classify the article to one out the four topics "World", "Sports", "Basiness", i "Tech" if the article'ss is main tapic is relevant to the world, sports, business, and technology, comrspondingly. you not sure abour the topic, choose the closest option.
48.89
PromptSource EvoPROMPT
What label best describes this news article"
45.43
Assess the entire concept of the news story and chouse from World, Sports, Business or Tech calegories to categorize into the correct category.
76.21
Manual Instruction
Please perform Question Classificaiin task. Given the question, assign a lahel from ("Description,, "Emity".
50.60
TREC
Expressiion' 'Humann. LLcatiin", 'Number') J. Return lahel only without any other text.
Notural Instruction
You are given question. You need to detect which category better describes the question. Answer with "Deseription, : "Ealily, "Expression" "Human", "Location, and "Number". Which category best describes the following question? Choose from the following list: Description, Emitty.
55.00
PromptSource
36,20
Abbreviation, Person, Quanityy Location.
EvoPROMPT
Recognize the inputs (explanations, entilies or humans) and provide the suitable outputs (numbers, descrip- Gonn, unittics) to
68.00
the questions way that undersianbable for non-mtive English speakers
Manual Instruction
Please perform Subjectivity Classifictiin task, Given the sentence, "objectivee) J. Return lahel only without any
label from l'subjective',
49,75
Subj
Natural Instruction
In this task, are given sentences from reviews. The task classity sentence as "subjecrive" if the objective.
52.55
opinion the
subjective
"objective" the opinion the
EVOPROMPT
to demonstrate the subjectivity of reviews and opinions, distinguishing between objective and subjective input peoducing examples pensoaal opinions illustrations subjective views, so can illustute the subjectvvity of judgmenis and perspactives.
Constract input-ourpul
77.60
Table 14: Manual Instructions (following Zhang et al. (2023b) and Zhang al. (2023c)), Natural Instructions (Mishra et al., 2022b), PromptSource (Bach et al., 2022) as basclines and instructions with best performance on Alpaca-7b generated by EvoPrOmPT (either DE or GA) on classification datasets.
Method
Model
Content
ROUGE-1/2/L
Manual Instruction
Alpaca-bb
How would you sppraas that in few words?
35.92/1 35.92/11.16/31.6
GPT
How would you rephrase that in few words?
43.95/17.11/39.09
Alpaca-bb
Carcfully esamine the text listen the conversation to identify the key ideas, comprehend the main idea, and sumnurize the critsal ficts and ideas in the cuncise lingagge without any unnecessary details duplication.
39.36114.4436.09
EvoPROMPT
GPT
Reduce the cone by reading or listening carefully to idearify the main ideas and key points, 46.49/19.49/41 readers comprehend the impoctant concepts and essential information.
Table 15: Manual Instructions (following Sanh et al. (2021) as the baseline and instructions with best performance on Alpaca-7b and GPT3.5 generated by EVoPROMPT (either DE GA) on SAMSum.
22

---

Published as a conference paper at ICLR 2024
Method
Model
Content
SARI
Alpoca-7b
Simplity the text.
43.03
Manual Instruction
GPT-3.5
Simplity the text.
43,80
Alpaca-7b
Rewrite input into simple English make casier compechend for noe-mative English speakers.
46.67
EvoPROMPT
GPT-3.5
given
accessible
for and
English speakers.
Table 16: Manual Instructions (following Zhang et al. (2023c) as the baseline and instructions with best performance on Alpaca-7b and GPT3.5 generated by EvoPROMPT (either DE or GA) on ASSET dataset.
Task ID
Task
Description
Prompt
Score
hyperbatinn
adjectives correclly English sentences.
Verify answer splitiing into components and inspecting ench part closely and logically, so we progress (houghtfully and methodically we
explore each part systematically and rationally myllly to reach our goal.
sqqueues
Answer questions about which times certain events
Start by breaking this cocundrum manageable component
78.80
chunks, carefally analyzing this problem and thooughly inspecting each aspect collaboraiveely tackling together progressively
the
outcome.
0.S
objoct_ counting
Questions that involve enumerating objocts and asking the model
Examine this logically and assess this mechodccally. 87.60 that obtain precise result by thinking critically dissecting cally.
task systemati-
04
disumbiguation.gg
Clarify the meaning of sentences with ambignous pronouns.
First, ponder and start off by taking time. going step by step. using logic appreach this before we dive into the answer
71.20
05
logical_deductien deduucioontceeeeeee seciiiin___he_eoee objects
A logical deduction task which
Let's upproach it cauticusly, examining thor- oughly methodically. crementally towards resolution.
94.40
quires deducing
approach
quence of objects.
05
degiccal_educcion. pwe.ucceoo_ooeeeeeeooo fiwe_fbeeeeeebeeee
A logical deduction task which quires deducing
Split the problem steps and thoughtfully progress through to answer proof.
65.20
quenee of objects.
05
logical www.dleetoonneeeee sevee_ohjezts
A logical deduction task which quires deducing order se-
Let's take step-by- by-step upproach systematically 54.40
dissect math task.
quence of objects.
Table 17: Instructions with the best performance on GPT3.5 generated by EvoPROMPT (either DE or GA) on BBH datasets. Duplicate IDs are due to the tasks with several sub-tasks.
prompt optimization within the discrete language space lies in assessing the capacity of LLMs to adapt to these continuous control parameters,
We hope our study inspire further exploration of the connection between LLMs and other traditional algorithms, extending beyond EAs. The main challenge is adapting the specific elements of traditional algorithms to work within L.Mss. For example, these elements may include direction of motion, velocity in partial swarm optimization (PSO) (Kennedy & Eberhart, 1995), the path in ant colony optimization algorithms (APO) (Dorigo & Gambardella, 1997), and characteristic in MAP-Elites (Mouret & Clune, 2015).
23

---

Published as a conference paper at ICLR 2024
Tack ID
Task
Description
Prompt
Score
06
causal, judgement
Answer questions about causal attri-
At first, let's handle things contiously and reselve examining every detail and dealing with problem time.
65.78
bution.
07
date understandingg
Infer the date from contest.
Be realistic and practical like detective, and use evidence to solve the problem in logical, seep-b--
85.60
appronch.
U8
input movie
solve
name.
D0
word socting
Sort list of words.
Analyze each part the problem logically solve
56.40
like detective.
geometric shapes
geometric shapes SVG putbs.
methodically through problem gether.
11
movie recommendation
Recommend movies similar to the given list movies.
Before exploring the answer.
86.00
salient, etror detection
type glish tramlationn ol'a German souree sentence.
down problem individual steps onder sulve
13
Fommal fullicies
Distinguish dedictively valid from formal fallacies.
Let's be realistic and evalunte the situation atically, tockling grachally.
$6.00
panguins, tahlee
Anewer questions penguins and their attrihutes.
Let's by taking rational organized ap- proach, breaking down into smaller parts and thinking it through logicallyy while heing realistic handling it carefully and methodically right
15
dyck. Janguages
Correctly close a Dyck-n word.
Let's realistic and solve this challenge carefally and slowly, taking at slow to complete it cornectly. can he realistic and cautiously reach the gool.
44.10
multistep
multi-stop lemss
Before
17
navigate
Given a series of navigarion instrie- tions, determine whether one would back at starting point.
Let's logically work together to systemarically 94.20 salve this math prablem one step time in uni.
reasoning_abevn objects
Answer extremely simple questions about the colors objccts on a sur face.
Using
mindset,
ment of this mathernatcaal reasoning challengs one slep a time and reason like a detective uncover the solution.
expressions
Let's geadually
this mathematical lange by methodically addressing it by examining ench element and investigating ench factor. Progress slowly and carefully through this mathe- matical reasoning challenge step
expression.
20
tracking ohujtted__hjjcsss._oooooe threceohjjeeeeeeeeeeeeeeeeees
A task requiring determining the fi- pasitioss
69.20
objects their positions descrip- tion sequence of swaps.
20
tracking shuifled shuffee
objjete objects
A task requiring determining the fi- nul pasitions of set of objects given their initial positions and descrip-
Using logical, step step-by-steg by-stop approsuc,, work 81.20 through this task to lind the cornect answer.
sequence of swaps.
20
tracking obijess weweesseeeooooeeeeeeeeeeeee
A task requiring determining the fi- nal pasitions of set of objects their initial positions and descrip-
Esamine this issue logically and in detail, step-by- analyzing each part of the problem one time.
84.50
sequence of swaps.
21
sports, understanding
Determine whether zn artificially constracted sentence relating sports is plausible
Break down the problem into steps and start salv. 96.80
ing it.
sentences
analyze part problem in a step by step way to ensune the right answer obtained.
sancastic.
Table 18: Instructions with the best performance on GPT3.5 generated by EvoPrompt (either DE or GA) on BBH datasets. Duplicate IDs are due to the tasks with several sub-tasks.
24


Reviews:
[{"review_id": "9xBcn7NzUJ", "reviewer": "Reviewer_ZLDk", "summary": "The paper introduces EVOPROMPT, a new framework that merges evolutionary algorithms (EAs) with Large Language Models (LLMs) to optimize human-readable prompts for language tasks. By using EAs to iteratively improve prompts for both open- and closed-source LLMs such as GPT-3.5 and Alpaca, the study reveals significant performance enhancements (up to 25%) over human-designed prompts, showcasing the potential synergy between LLMs and EAs for prompt optimization.", "questions": "Why out of so many available methods, you only chose DE and GA? Why you used only one particular offspring generation strategy of DE? How are you repairing infeasible set of offspring and how does that process affect your timing complexity?\n\nThe authors have provided extensive rebuttals and based on the discussions with the authors, I am revising my score to 6.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well organized and clearly written.", "weaknesses": "The paper's attempt to introduce EVOPROMPT as a groundbreaking framework for discrete prompt optimization feels uninspired due to its reliance on established evolutionary algorithms (EAs) rather than innovating with novel approaches. While the study showcases the ability to optimize prompts for language models like GPT-3.5 and Alpaca, this contribution doesn't significantly advance the state of the art, particularly given the use of well-known evolutionary operators of DE and GA. Designing prompts for language models, although important, might not meet the level of substantial novelty expected at a conference like ICLR. This approach, while showing performance enhancements, might not present a substantial leap forward in the field of language model optimization, especially considering the expectations of innovation and original contributions at such academic conferences. I think this paper would be better suited in a conference like IEEE CEC or PPSN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n0FgyX0C5A", "reviewer": "Reviewer_LYv4", "summary": "In this paper, the authors present EvoPrompt, a framework to combine Evolution Strategies and a Language Model to engineer prompts to improve the performance of possibly another Language Model on a variety of instruction tasks. The authors mention that the prompt used to instruct an LLM strongly influences its performance and that human crafted prompts are often sub-optimal thus motivating the need to use optimization algorithms to generate prompts so as to maximize the performance of an LLM on a given task. In that context, the authors motivate the use of Evolution based algorithms as they typically perform great on discrete sequential data and offer a good way to balance exploration and exploitation. Evolution algorithms also have the benefit from performing black box optimization - they do not access to the function or its gradient - which allows users to use them with models that are only accessible through an API for instance. However, standard mutation and crossover functions  that typically invert / replace / mutate individual elements in the discrete sequences without maintaining global coherence which would lead these operators to quickly generate prompts that are unreadable and non interpretable. Therefore, the authors propose to use an LLM to perform crossover and mutation operations to always generate coherent and meaningful new samples. The authors compare to Evolution strategies - genetic algorithms and differential evolution - and benchmark their method on a variety of tasks including language understanding and summarization. The method is applied both to Alpaca (instruction-fine tuned Llama which is open-source) and to GPT-3.5 (proprietary model accessible through an API). They compare obtained to several baselines and propose some ablations to study the impact of mutation strategy used and the impact of the initial population.", "questions": "All in all, I like the idea being introduced and I think the authors did a good job at introducing it and benchmarking it, therefore I would be happy to see this work published (it would be even better if the authors would demonstrate the method on a different use-case than prompt optimization however, I understand this would be a very different paper. It might be an idea for the next one though ;)). However, I have some doubts if ICLR is the best place for that as I think GECCO would be better suited. Therefore, I will say minor accept for now but I would be happy to increase my grade if the reviewers and other authors convince me that actually ICLR is the right place.\n\n\n**A few other general comments**:\n\n- As mentioned above, I think this would be very exciting to apply these LLM-based evo operators to other applications. For instance this could be used to generate game levels through textual description or coding exercises. With latest models such as DALLE-3, the same strategy could be applied to generate images.  \n\n- The authors mention that EA are good at balancing exploration and exploration, however it is not always the case and this is for instance often a limitation of GA methods. I would recommend the authors to have a glance at the Quality Diversity literature with algorithms such as MAP-Elites which are much better at balancing exploration. I think it would be very exciting to use EvoPrompt on top of a QD method.\n\n- In the conclusion, the authors mention looking at Simulated Annealing (SA) for future work. In my experience, GA and other more recent EAs always outperform SA by a strong margin (if correctly tuned and implemented). Thus, I would not advise going in that correction. QD methods are probably going to be more fun. Looking at multi-objectives methods such as NSGA-II might be interesting as well.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "First of all, I find the paper well written. The motivation is clearly explained, the context is well introduced and the authors do a great job in the literature review part. The method is also clearly explained and detailed which makes it easy for the reader to understand what is going on and which might help to reproduce the work as well. I also really enjoyed Figure 1 and 2 which are very clean, colorful and do a great job at illustrating the method.\n\nThe method itself is sound and I agree that Evolution Strategies make a lot of sense for this problem for all the reasons mentioned. I mainly like the way crossover and mutation is implemented by querying an LLM. I find this idea very powerful as indeed, in most cases the main challenge in using EAs lies in defining operators that can stay in the data distribution when perturbing samples. \n\nI also find the experimental setup convincing as the authors performed a large number of experiments and compared to several relevant baselines. The fact that the method was illustrated both on an open-source and on a proprietary model also strengthened that part and I also like that the authors illustrated how to apply their method and LLM-based evo operator with two different types of Evolution Strategies.", "weaknesses": "While I really appreciate the evo operator that leverages LLMs, I have more doubts about the relevance of the considered application. I feel like there are more interesting applications for this method than prompt engineering which I believe will soon not be a thing anymore as we see the latest language models becoming more and more robust to the prompt that is used. However, I acknowledge that there are ongoing efforts in that field and while I personally don't find it very exciting or relevant, this work contributes efficiently to this research track.\n\nI also have some doubts about the relevance of this work to ICLR. In my opinion, the main contribution of this work is this LLM-based mutation/crossover operator which would make more sense in an evolutionary algorithms conference such as GECCO than at ICLR. \n\nFinally, I think that this work would strongly benefit from a study of the computational cost of the approach in the main core of the paper. I saw some elements that could help towards this end in the supplementary, but I would like to see an analysis of the computational cost / financial cost and time needed to perform this optimization. It would be interesting also to add similar analysis for the baselines. I think this would be very useful to the readers to evaluate to what extent they could apply that to their research if they have either to serve themselves Alpaca on an accelerator or to query the OpenAI API after connecting their credit card.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fFaWdYiZ7Q", "reviewer": "Reviewer_HRoN", "summary": "This paper introduces EvoPrompt, a new framework that leverages evolutionary algorithms (EAs) for discrete prompt optimization in Large Language Models (LLMs) without requiring access to the gradient or parameters of the LLMs. Specifically, taking cues from EA concepts such as mutation and crossover, EvoPrompt uses the LLM itself to carry out crossovers and mutations on a collection of pre-defined prompts, leading to the generation of a fresh set of evolved prompts. The EvoPrompt has been instantiated to both Genetic Algorithm (GA) and Differential Evolution (DE) versions. Comprehensive experiments across 31 datasets have demonstrated the efficacy and good performance of EvoPrompt when tested on both closed-source and open-source LLMs.", "questions": "1. In EvoPrompt, most of the initial populations were generated with a mix of manually-created and LLM-generated prompts. What is their ratio when DE works better than GA? What would be the performance of EvoPrompt if the initial prompts were all generated by LLM?\n2. How effectively can EvoPrompt discover novel prompts utilizing EA operators? (e.g., considering factors such as prompt length and the variance in approaches between new and prior prompts). \n3. When the LLM generates mutated new words, is there adequate diversity in the new words introduced, or is there a repetition of the same words?\n4. See other questions in the weakness part.\n5. Will there be any benefits to combining and alternating GA and DE updates during search?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The combination of LLMs with EAs as presented is novel to me, providing insights for future LLM research.\n* I liked the design of using the LLM itself to iteratively refine candidate prompts, which harnesses the natural linguistic strengths of LLMs. This ensures that the generated prompts are coherent, readable, and well-constructed sentences.\n* The authors have conducted extensive experiments on benchmark datasets and the discussions on different designs and hyperparameters are commendable.\n* The paper is well-written and easy to follow. It offers useful examples and LLM templates.", "weaknesses": "* EvoPrompt's performance appears to be influenced by the quality of the initial prompts (initial population), which may limit its applications. While the paper emphasized the DE version's superior exploration over the GA, a deeper analysis would be beneficial.\n* Further discussion and evaluation of the diversity of the prompts produced by EvoPrompt would be beneficial.\n* The EA optimization for a single prompt involves iterations. However, the search doesn't appear to converge in Figure 6. Is it possible to illustrate the effects of more iterations? It's unclear if these 10 iterations are conducted within a single LLM session or if each iteration starts with a new session. Besides, more details should be provided regarding the runtime, and resources for running the GA.\n* It would be beneficial if the authors could present negative examples where EvoPrompt failed, as this could inspire direction for future research. Moreover, the limitations of this approach should be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KbreIurx0g", "reviewer": "Reviewer_hqfj", "summary": "The paper proposes a novel framework for automatic discrete prompt optimization, called EVOPROMPT, which connects Large Language Models (LLMs) with Evolutionary Algorithms (EAs). The authors demonstrate that this approach can generate better prompts compared to human-engineered prompts and existing methods for automatic prompt generation. The paper is well-structured, with clear explanations and thorough experiments conducted on 31 datasets.", "questions": "- Could you provide more detailed explanations of the implementation details for each type of EA (GA and DE) used in EVOPROMPT? Specifically, it would be helpful to understand how the algorithms are adapted to work with discrete prompts and how the LLMs are used to generate new candidate prompts.\n\n- How is the effect of different population sizes, mutation rates, or selection strategies on the performance of EVOPROMPT", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed EVOPROMPT framework is innovative, combining the language processing capabilities of LLMs with the optimization performance of EAs. This approach allows for the simultaneous leveraging of the powerful language processing capabilities of LLMs and the efficient optimization performance of EAs.\n\n- The paper provides a comprehensive review of related works, including prompt engineering, discrete prompts, and LLMs with optimization algorithms. This review helps readers understand the context and contributions of the proposed method.\n\n- The experiments conducted on 31 datasets demonstrate the effectiveness of EVOPROMPT compared to crafted prompts and existing methods. The results show consistent performance gains over both manual instructions and existing methods.", "weaknesses": "- The paper could benefit from more detailed explanations of the implementation details for each type of EA (GA and DE) used in EVOPROMPT. Providing more information on the specific steps and instructions for each algorithm would help readers better understand the proposed method and its connection to LLMs.\n\n- The paper could include more ablation studies to better understand the impact of different components of the proposed method. For example, analyzing the effect of different population sizes, mutation rates, or selection strategies on the performance of EVOPROMPT would provide valuable insights into the method's robustness and generalizability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)