Dear Reviewer hqfj,

Thank you for taking the time to review. We appreciate that you found our paper well-written and the literature review comprehensive. We would like to make the following clarifications about your concern. If you find these responses useful to address your questions and concerns, we would be grateful and would consider increasing your score.

We summarize the mentioned concerns and we hope the corresponding comments address your concerns, we would be grateful if you could consider increasing the review score.

Q: More information on specific steps and instructions for each algorithm is needed.

A: Thanks for reminding us of the specific steps, which is helpful for readers to better comprehend our methods. In our original paper, we unify the evolutionary algorithms in a framework. Considering your comments, we have updated our draft and added detailed algorithms for GA and DE, respectively (See Appendix A for details of implementation). We hope this can be responsive to your concerns. Additionally, we have attached the corresponding code in the supplementary materials. Later we will release our code to the public.

Q: How the algorithms are adapted to work with discrete prompts and how the LLMs are used to generate new candidate prompts?

A: LLMs play a role in generating new prompts based on evolutionary operators including mutation and crossover according to the given candidates. Figure 1 and Figure 2 in the paper provide detailed instructions on guiding LLMs to generate a new discrete prompt. Meanwhile, we utilize the selection and updating strategy in evolutionary algorithms to control convergence and effectiveness.

Q: This paper could include more ablation studies to better understand the impact of different components of the proposed method, such as the effect of different population sizes, mutation rates, or selection strategies.

A: Sec. 5.1 and 5.2 in our original paper have explored the effect of important components designed in GA and DE respectively. Particularly, for GA (Sec. 5.1), we mainly analyze the selection strategy including the random, tournament roulette wheel strategy. For DE (Sec. 5.2), we demonstrate the importance of mutation over different parts and the selection of Prompt 3 in Figure 2. Due to the space limitation, the study on population sizes is in Appendix C.1 of our paper.

Besides, we would like to appreciate your suggestion about the mutation rates. Considering the LLMs may struggle with the rate of concrete float value since at the level of natural language, it is hard to measure the mutation extent, we leave this for future work.

We also want to kindly remind you that the discussion phase will end soon, so we would greatly appreciate your support in this regard before the deadline.

Dear Reviewer hqfj,

We greatly appreciate the time you've invested in reviewing our response. Having submitted our rebuttal, we are eager to know if you have any remaining concerns or require further clarification. Since the discussion phase will end soon, we would greatly appreciate your support and valuable feedback before the deadline (Nov. 22, 2023).

Best,

Authors

Our responses to the rest of the questions are as follows.

Q: Details about the runtime and resources.

A: Please refer to our general responses on cost analysis for details related to resources. The runtime varies from each dataset, the table below lists the runtime when optimizing for Alpaca on a single V100 GPU (except that BBH is optimized for GPT3.5). Additionally, the runtime of evaluation depends on iterations, the size of the population and the size of the dev set. Here we show the time under our default setting. The time for evaluation is almost the same for APE and our methods. Note that each task in BBH takes about the same amount of time to run.

Q: Negative examples where EvoPrompt fails and the limitations can lead to future investigation.

A: In our results of Big-Bench Hard, there are several tasks that either EvoPrompt (GA) or EvoPrompt (DE) fails. This is because the distribution of the randomly sampled dev set is not aligned with the test set, resulting in a performance gap between the evaluations based on them. Accordingly, though EvoPrompt gets a better prompt based on the dev set, it may not perform as well when tested on the test set. Thus, constructing a more effective dev set could further enhance the performance, which needs future investigation.

Q: What is the ratio of manually created and LLM-generated prompts in the initial population when DE works better than GA? & What would be the performance of EvoPrompt if the initial prompts were all generated by LLM?

A: There are two ratios of manually written prompts in the initial population, before top-k and after top-k and variations. Before selecting top-k, the ratio of manually written prompts is around 50%. The ratio after top-k and variations are listed in the table below. We haven't observed a significant correlation between the ratio of manual prompts in the initial population and the performance.

Additionally, here we conduct experiments with the initial prompts generated by LLMs completely, as shown in the table below. We can observe that for SST-5, initialization has little impact.

Q: Will there be any benefits to combining and alternating GA and DE updates during the search?

A: Thanks for your comments. It’s a promising suggestion. The selection and updating strategy differ from DE and GA, making the combination non-trivial. We will further investigate this for our extensions.

Dear Reviewer HRoN,

Thank you for your positive and thoughtful feedback and look into every detail of our work. We appreciate that you found our paper well-written and experiments commendable. We summarize the mentioned concerns and we hope the corresponding comments address your concerns, and we would be grateful if you could consider increasing the review score.

Q: EvoPrompt’s performance may be influenced by initial prompts.

A: In Sec 5.3, we investigate the effect of initial population quality. The results of random-k and top-k initialization exhibit a high degree of similarity and the random setting is more in line with the real situation. This suggests that EvoPrompt does not depend on carefully crafted manual prompts. Instead, even randomly selected prompts can achieve a good performance. Additionally, though DE (48.64) and GA (47.80) starting from the selected bottom population perform not that well, they still outperform APE (46.32), demonstrating the effectiveness and robustness of EvoPrompt.

Q: Deeper analysis for DE’s exploration over GA. & Diversity of prompts

A: We are very grateful for your insightful comments on comparing DE and GA from this perspective. Considering your suggestions, We mainly analyze prompt diversity through the following aspects: 1) the average length of the prompt and the corresponding variance in the population; 2) the number of new words after each iterative step; 3) the case study. We will briefly summarize the results in this response.

• Average length and variance: From Figure 9 (a, b) in the Appendix, DE shows higher length and variance than GA. This implies that the prompts generated in DE are more diverse in terms of length.

• Number of new words: From Figure 9 (c), we can observe that in the latter iterations, DE mutates more new words than GA, and thus shows better potential to explore and escape from the local optimum.

• Case study: in Figure 1 (GA) and Figure 2 (DE), the given examples are taken from our experimental logs. 1) For GA, in the final prompt (at the bottom), words in orange and blue are inherited from the parental prompts respectively, and words in black are mutated parts. 2) For DE, comparing the final generated prompt (wrapped by a box at the bottom) with the basic prompt (in the upper part of the figure, prompt in blue words), the new prompt keeps half of the original one, while the other half derives from crossover and mutation referring to other candidates. DE keeps the common parts between the given candidates as repetition and only performs mutation on different parts. Both of them have repetitions and mutations, corresponding to exploitation and exploration.

Results related to prompt diversity revealed that DE tends to generate more diverse prompts than GA. This result also indicates that DE is potentially better at exploration than GA. Please see Appendix C.4 in our revised version for more details. Thank you again for your insightful comments on comparing DE and GA from this perspective.

Q: The search doesn't appear to converge and it is possible to illustrate the effects of more iterations.

A: We increase the iteration steps and there’s still slight performance gain on the Subj dataset, but EvoPrompt, both GA and DE versions, on most of the datasets converge around 10 steps. To maintain uniformity and reduce hyperparameter elaboration in the experimental setup, we selected a consistent value of 10 across all tasks. It's true that at the iteration of 10, the average score still shows an increasing trend but there exists a trade-off between the number of iterative steps and performance. If we continue evolving until convergence, the best score of DE can rise. Please refer to Appendix C.3 for more detailed demonstrations.

Q: Are 10 iterations conducted in a single LLM session or a distinct new session?

A: Each evolution is in a distinct new session.

Dear Reviewer HRoN,

We greatly appreciate the time you've invested in reviewing our response. Having submitted our rebuttal, we are eager to know if you have any remaining concerns or require further clarification. Since the discussion phase will end soon, we would greatly appreciate your support and valuable feedback before the deadline (Nov. 22, 2023).

Best,

Authors

We would like to appreciate your comments on our method we will consider these directions, including application in image generation, introducing QD methods, etc., as our further extensions. Specific responses to each of your questions are as follows:

• Applications of our method: In this paper, we demonstrate the ability of LLMs to implement evolutionary algorithms given clear instructions and mainly aim at prompt optimization. In addition, our framework can be applied to various fields, such as non-trivial NP-hard problems (e.g. TSP), and multi-modality scenarios. It also can be deployed on agent-based systems to enhance cooperation among agents in diverse situations. We leave this for future exploration
• QD methods: Thanks for this insightful suggestion and for reminding us of the limitation of SA compared with EAs. QD methods like MAP-Elites are more recent and seek to find a set of policies with both high rewards and diverse behaviors. These approaches show a promising ability to balance exploitation and exploration, which is crucial for heuristic searches. We will further investigate this for future work.

Thank you again for your thoughtful feedback, and we hope our response has addressed your concerns adequately.

Dear Reviewer LYv4,

Thank you for taking the time to review and propose promising extensions. We appreciate that you found our paper well-written and sound with convincing results. If the following comments address your concerns, we would be grateful if you could consider increasing the review score.

Firstly, we would like to clarify our motivation for focusing on prompts.

• We kindly argue that prompts for large language models (LLMs) are crucial, as provide a necessary interface to interact with black-box LLMs. In the era of LLMs, the fine-tuning paradigm is computationally demanding, while the prompt in natural language is effective, interpretable and human-readable, especially practical for those limited by the computational budget. Previous works find prompt order [4], templates and examples can highly affect [5] the performance. The field of prompt engineering has recently gained significant popularity, evolving into a highly sought-after career. Automating this process, and achieving superior performance compared to human-designed prompts, signifies a major step forward in the area of language model optimization. This motivates us to study the automated generation of high-quality prompts.

• We understand your concern that prompt engineering might not be useful as the language model scales. However, it has not been proved that the larger the model is, the more robust it is to the given prompt. In our experiments, even GPT3.5 is sensitive to prompts. Lu et al. [4] demonstrate that models of different scales are sensitive to the prompt, with the largest LM being 175 billion. Meanwhile, our proposed EvoPrompt also achieves significant improvement on multiple tasks (e.g., up to 25% improvement on BBH compared with the famous Chain-of-Thought, which shows the influence of different prompts). Moreover, as the model's scale increases, the corresponding rise in computational cost renders fine-tuning methodologies less feasible. This shift amplifies the importance and relevance of prompts, known for their effectiveness and better interpretability.

• One major benefit of employing LLMs as evolutionary operators is their ability to take into account the coherence within a sequence. Consequently, the prompt in natural language is a particularly appropriate application. We begin with NLP tasks because they come with standard objective evaluation criteria, which are more effective in showcasing the performance of EvoPrompt. As you mentioned, it would indeed be intriguing to apply EvoPrompt to multi-modality applications (e.g., game level and image generation) by adjusting the evaluation and selection strategies.

Secondly, ICLR considers a broad range of subject areas. One contribution of our work is to connect LLMs with evolutionary algorithms, where, as you mentioned, the most innovative design is the LLM-based mutation/crossover operator. This connection does not contribute to improving the evolutionary algorithms, instead, it sparks new applications for both of these fields. Accordingly, besides evolutionary algorithms, it is also highly related to LLMs. For example, the works considering evolutionary algorithms with reinforcement learning [2, 3] were also accepted by ICLR’22 and ICLR’23. Another contribution is the prompt optimization framework. While our main focus is on prompts for NLP tasks, potential applications could also include prompts for vision tasks. This is in line with the "applications in language and vision" in the call for papers, as well as other previously accepted papers at ICLR'23 like APE [1].

Finally, to address your criticism regarding costs, we analyze the cost to apply our EvoPrompt in general responses. Intuitively, there exists a trade-off between costs and the corresponding performance. EvoPrompt shows a higher ceiling compared with APE. Besides, EvoPrompt outperforms APE when keeping the same number of API requests. Please see the general response for more statistics.

References

[1] Zhou, Yongchao, et al. "Large Language Models are Human-Level Prompt Engineers." The Eleventh International Conference on Learning Representations. 2023.

[2] Wang, Yutong, Ke Xue, and Chao Qian. "Evolutionary diversity optimization with clustering-based selection for reinforcement learning." International Conference on Learning Representations. 2022.

[3] Hao, Jianye, et al. "ERL-Re $^ 2$: Efficient Evolutionary Reinforcement Learning with Shared State Representation and Individual Policy Representation." The Eleventh International Conference on Learning Representations. 2023.

[4] Lu, Yao, et al. "Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity." Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

[5] Zhao, Zihao, et al. "Calibrate before use: Improving few-shot performance of language models." International Conference on Machine Learning. PMLR, 2021.

Dear Reviewer LYv4,

We greatly appreciate the time you've invested in reviewing our response. Having submitted our rebuttal, we are eager to know if you have any remaining concerns or require further clarification. Since the discussion phase will end soon, we would greatly appreciate your support and valuable feedback before the deadline (Nov. 22, 2023).

Best,

Authors

Specific responses to each of your questions are as follows:

• The reason for choosing GA and DE: We choose representative and widely used evolutionary algorithms, GA and DE for their fast convergence without any parameters. GA is among the most highly regarded evolutionary algorithms and DE has emerged as one of the most widely utilized algorithms for complex optimization challenges since its inception (first two paragraphs in Section 3). Apart from these two representative algorithms, other diverse algorithms can be further explored.
• Offspring generation strategy of DE: Our original paper has carefully investigated different generation strategies of DE (analysis in Sec 5.2). In the main experiments, we choose one of them with the best performance.
• Repairing infeasible offspring and effect on time complexity: For both GA and DE, after each iteration including selection, mutation and crossover, updating upon the current population, the infeasible offspring will be eliminated. The elimination is up to their fitness value, i.e., the performance on the given development set in our work. Eliminating infeasible offspring based on certain rules or a small subset of the development set, rather than evaluating them on the entire development set, could potentially reduce costs and leave them for future investigation.

Dear Reviewer ZLDk,

We are grateful for your careful review and the valuable feedback that you provided for our paper. We would like to make the following clarifications about your concern. We also want to remind you that the discussion phase will end soon, so we would greatly appreciate your support in this regard before the deadline.

Firstly, we would like to clarify the motivation and novelty of using the transitional evolutionary algorithms. The main novelty of this work is to propose a general framework that connects LLMs with evolutionary algorithms, as well as the LLM-based evolutionary operator design, which is also highlighted by all the other reviewers (LYv4, HRoN, hqfj). Furthermore, we believe that many traditional algorithms are still attractive due to their good performance, and connecting them with LLMs may encourage more innovative applications and not be limited to prompt optimization. Besides, many excellent works combine traditional well-performed algorithms with LLMs to get powerful methods. For instance, Self-Consistency [6] combines ensemble learning and LLMs (ICLR'23). [7] introduces effective beam search into reasoning paths (NeurIPS'23).

Secondly, we appreciate your concern that our contribution doesn't significantly advance the state of the art. As shown in the experiments, EvoPrompt shows significant improvement on multiple tasks (e.g., up to 25% improvement on BBH compared with the famous Chain-of-Thought) and Reviewer LYv4, HRoN, hqfj find our experimental results convincing.

Finally, we appreciate your concern regarding the novelty and appropriateness of prompt design for ICLR.

• Prompts provide a necessary and efficient interface to interact with black-box LLMs. Previous works find prompt order [8], templates and examples can highly affect [9] the performance. The field of prompt engineering has recently gained significant popularity, evolving into a highly sought-after career. Automating this process, and achieving superior performance compared to human-designed prompts, is challenging and also signifies a major step forward in the area of language model optimization. we have observed many good works related to prompts presented at previous ICLR, as well as other top conferences. For example, the famous Chain-of-Thought [1] has been accepted by NeurIPS'22. APE (one of our strong baselines [2]), GenRead [3], TEMPERA [4], least-to-most prompting [5] have been accepted by ICLR’23. Thus we believe that prompt design contributes to the advancement of the field and is in line with other previously accepted papers at ICLR'23.

• On the other hand, the contribution of this work extends beyond prompt optimization. It also establishes a novel connection between evolutionary algorithms and LLMs. This framework can also be applied to various tasks, such as non-trivial NP-hard problems. Furthermore, we hope our work can inspire future research at the intersection of LLMs and traditional algorithms, encouraging innovative applications.

References

[1] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." Advances in Neural Information Processing Systems. 2022.

[2] Zhou, Yongchao, et al. "Large Language Models are Human-Level Prompt Engineers." The Eleventh International Conference on Learning Representations. 2023.

[3] Yu, Wenhao, et al. "Generate rather than Retrieve: Large Language Models are Strong Context Generators." The Eleventh International Conference on Learning Representations. 2023.

[4] Zhang, Tianjun, et al. "Tempera: Test-time prompt editing via reinforcement learning." The Eleventh International Conference on Learning Representations. 2023.

[5] Zhou, Denny, et al. "Least-to-most prompting enables complex reasoning in large language models." The Eleventh International Conference on Learning Representations. 2023.

[6] Wang, Xuezhi, et al. "Self-Consistency Improves Chain of Thought Reasoning in Language Models." The Eleventh International Conference on Learning Representations. 2023.

[7] Xie, Yuxi, et al. "Decomposition enhances reasoning via self-evaluation guided decoding." Advances in Neural Information Processing Systems. 2023.

[8] Lu, Yao, et al. "Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity." Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

[9] Zhao, Zihao, et al. "Calibrate before use: Improving few-shot performance of language models." International Conference on Machine Learning. PMLR, 2021.

Dear Reviewer ZLDk,

We greatly appreciate the time you've invested in reviewing our response. Having submitted our rebuttal, we are eager to know if you have any remaining concerns or require further clarification. Since the discussion phase will end soon, we would greatly appreciate your support and valuable feedback before the deadline (Nov. 22, 2023).

Best,

Authors

I apologize for posting late on the authors' response. I will rethink of my score, after receiving some response for the following questions.

While I do appreciate the extensive attempts made by the authors for analyzing the cost function further and elaborate on the efficacy of their transitional EA based approaches, the questions still remains are: did you try the best and latest version of DE like SHADE or quivalent, as covered in a more latest survey (https://doi.org/10.1016/j.swevo.2016.01.004) ? If not, why?

Also, given the inherently discrete nature of the prompt optimization problem, why didn't you try binary PSO or the ant colony optimization type algorithms? WIll not doing round-off for the solutions returned by inherently continuous operators of DE introduce more quantization noise?

Dear Yujian,

Thank you for taking the time to share your feedback and results related to our work.

We'd like to highlight that our proposed EvoPrompt is stable. This has been demonstrated in our experiments, where we show the average performance over three runs on Alpaca, along with the standard deviation. As for GPT-3.5, due to budget limitations, we only conducted a single run.

For the unstable issue in your case, we concur that it should be eased when the target model is also a large language model. This is due to the fact that RoBERTa, being relatively small, may not effectively comprehend and follow the instructions produced by LLMs.