ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution

We deeply appreciate your time and effort in reviewing our work, and the insightful questions and suggestions you raised. We respond to your comments below.

W1: Reliance on existing heuristic or neural solvers.

ReEvo can discover new heuristics independently but integration currently leads to better performance. In Section 5.4, we show that ReEvo can independently discover new constructive heuristics for TSP, which outperform the algorithm designed by traditional hyper-heuristics.

ReEvo improves the key algorithmic components of existing methods, such as the perturbation in GLS, the crossover and mutation in GA for EDA, the heuristics in ACO, and the attention in NCO. We leave it to future work to further explore its potential to independently discover new complicated heuristics. Under an agentic framework, by first designing a skeleton of the program and then each individual function, we may be able to generate high-performing long programs using LLMs.

W2: Experiments with SOTA methods, such as T2TCO, DIFUSCO, and LKH-3.

LHH is complementary to your suggested SOTA methods.

• LKH-3 is a specialized solver for the TSP, which has been heavily optimized for the VRP over decades. LHHs, on the other hand, are more general and can be applied to any COP. They are especially suitable for cases where expert knowledge is lacking or the problem is treated as a black box.

• DIFUSCO and T2TCO require optimal solutions for training, which may not be available for many problems. LHHs, on the other hand, only require heuristic evaluations. We compare against T2TCO on TSP500 and TSP1000, each with 128 test instances. Below we report the optimality gap and running time for solving all instances. They indicate the competitive performance of GLS-ReEvo.

• LHH and general ML4CO [1] are complementary, each with its unique strengths and limitations. Some advantages of LHHs over ML4CO are:

  • LHHs generate interpretable heuristics (code snippets), while ML4CO generates black-box parameterized policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distribution shifts, or adversarial attacks.
  • LHHs generate heuristics that are more efficient in terms of computational resources, as they do not require GPU during deployment.
  • LHHs require only less than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many ML4CO methods require millions of samples and days of training. When the solution evaluation is expensive, LHHs are more practical.
  • LHHs only need some text-based (and even black-box) explanations to guide the search. ML4CO requires the development of NN architectures, hyperparameters, and training strategies, where informed inductive biases and manual tuning are crucial to guarantee performance.

[1] https://github.com/Thinklab-SJTU/awesome-ml4co

W3-1: The writing in Sec. 4 needs improvement. For example, how the short-term and long-term reflection is utilized to improve heuristic design?

We will improve the writing in Section 4 according to your suggestion.

An example of both short- and long-term reflection is illustrated in Figure 1(b). The process prompts LLM to reflect upon the relative performance of two heuristics (short-term), and accumulate such knowledge over iterations (long-term). The inputs and outputs of the reflection process are all texts.

Short-term reflection.

• Inputs: Two heuristics to crossover and indicators of their relative performance.
• Outputs: Text-based reflections upon the performance of the two heuristics, i.e. why the better heuristic is better, and how the worse heuristic can be improved. It is analogous to a verbal gradient derived from the performance comparison.
• How it is utilized: ReEvo incorporates the short-term reflections into the crossover prompt, leading to more informed offspring.

Long-term reflection.

• Inputs: prior long-term reflections and short-term reflections of the current iteration.
• Outputs: Text-based reflections upon the overall performance of the population, and strategic hints for better heuristic design.
• How it is utilized: ReEvo incorporates the long-term reflections into the mutation prompt, leading to more strategic exploration.

W3-2: How to guarantee the generated code is executable?

If the generated code is not executable, it is discarded.

As the author-reviewer discussion will end soon (< 24 hours from now), we would greatly appreciate it if you could take a moment to review our response. Please let us know if you have any further questions or concerns.

We deeply appreciate your time and effort in reviewing our work, as well as the insightful comments and questions you raised.

W1: Details of reflections.

We will revise the writing for better clarity according to your suggestions. An example of both short- and long-term reflection is illustrated in Figure 1(b). The process prompts LLM to reflect upon the relative performance of two heuristics (short-term), and accumulate such knowledge over iterations (long-term). The inputs and outputs of the reflection process are all texts.

Short-term reflection.

• Inputs: Two heuristics to crossover and indicators of their relative performance.
• Outputs: Text-based reflections upon the performance of the two heuristics, i.e. why the better heuristic is better, and how the worse heuristic can be improved. It is analogous to a verbal gradient derived from the performance comparison.
• How it is utilized: ReEvo incorporates the short-term reflections into the crossover prompt, leading to more informed offspring.
• Meaning: LLM reflects upon the performance of the two heuristics, providing insights for better heuristic design. It only targets the two heuristics for the current crossover, and does not consider the historical performance of the population.

Long-term reflection.

• Inputs: prior long-term reflections and short-term reflections of the current iteration.
• Outputs: Text-based reflections upon the overall performance of the population, and strategic hints for better heuristic design.
• How it is utilized: ReEvo incorporates the long-term reflections into the mutation prompt, leading to more strategic exploration.
• Meaning: LLM accumulates knowledge over iterations, combining past experiences with new insights to offer long-term strategic hints.

W2: Undiscussed recent baselines.

We comprehensively compare against 25 baselines across 6 COPs and 5 algorithmic types, under both black-box and white-box settings, and in terms of both LHH and generated heuristics. 8 of these baselines were published after 2023. We show that LHH can enhance ML4CO solvers in Section 5.5, involving TSP/CVRP with 1000 nodes.

Here, we compare against the suggested SOTA baselines, on TSP500 and TSP1000 each with 128 test instances. Below we report the optimality gap and running time for solving all instances. They indicate the competitive performance of GLS-ReEvo. Please note that T2TCO requires optimal solutions for training, which may not be available for many problems, while ReEvo only requires heuristic evaluations.

We respectfully bring to your attention that LHH and ML4CO [1] are complementary, each with its unique strengths and limitations. Some advantages of LHHs over ML4CO are:

• LHHs generate interpretable heuristics (code snippets), while ML4CO usually generates black-box parameterized policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distribution shifts, or adversarial attacks.
• LHHs generate heuristics that are more efficient in terms of computational resources, as they do not require GPU during deployment.
• LHHs require only less than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many ML4CO methods require millions of samples and days of training. When the solution evaluation is expensive, LHHs are more practical.
• LHHs only need some text-based (and even black-box) explanations to guide the search. ML4CO requires the development of NN architectures, hyperparameters, and training strategies, where informed inductive biases and manual tuning are crucial to guarantee performance.

[1] https://github.com/Thinklab-SJTU/awesome-ml4co

W3: The cost of using LLM APIs

As reported in Appendix B (line 858), each run costs about $0.06 when using GPT3.5 Turbo.

Q1: The y-axis of Figure 4(B).

As indicated by the y-axis label, Figure 4(B) shows the objective value of the best generated heuristic, against the number of heuristic evaluations for an LHH.

Q2-1: Comparisons with recent ML4CO method on TSP and VRP.

Please refer to our response to W2.

Q2-2: Advantage of LLM-enhanced heuristics over ML4CO methods.

Please refer to our response to W2.

Potential limitations regarding LLM inference cost and problem scale

Please also refer to our response to W2 and W3.

Inference cost. Please note that we don't need LLM inference once the heuristic is generated, and the generated heuristics are efficient in terms of computational resources. For LHH search, deploying local LLMs is also feasible, as verified in our work with Llama 3.

Problem scale. We have tested our method on large-scale problems, such as TSP1000 and CVRP1000. LHHs are currently most effective when integrated with existing algorithms. As long as the algorithm is scalable, its LHH-enhanced version is scalable as well.

We deeply appreciate your time and effort in reviewing our work, as well as the insightful comments and questions you raised.

W1: The reflection technique has been well-developed and widely used in prompt engineering and code generation.

Thank you for raising this point. Our work introduces a novel integration of reflection with evolutionary search. As noted by Reviewer v9WQ, this integration is effectively a novel technique to load in-context knowledge without incurring memory blowups.

We respectfully draw your attention to the fact that the reflection techniques, which were initially proposed at NeurIPS 2023 [1, 2], are still under active development. Adapting reflection for a downstream application itself constitutes a valuable contribution; recent examples include its application to translation tasks [3, 4].

W2: Evolution methods based on LLM have been adopted in EoH and Funsearch, limiting the contribution to the framework.

Thank you for highlighting the work done in EoH and FunSearch, which we extensively cite and acknowledge in our paper. These groundbreaking studies indeed lay the foundation for our work. We draw significant inspiration from them and aim to extend their contributions in meaningful ways.

We believe that the combination of LLMs with EA for CO can be explored through three primary lenses: (1) the search algorithm, (2) the downstream CO applications (the search space), and (3) the evaluation methodologies (ways to evaluate how well we search). We believe our work contributes to all three aspects:

• Search Algorithm: We introduce the Reflective Evolution method, demonstrating its superior sample efficiency.
• Applications: Our work broadens the scope by applying this paradigm to five heterogeneous algorithmic types and six different combinatorial optimization problems, advancing the state of the art in GLS, EDA, ACO, and NCO methods.
• Evaluation Methodologies: We employ fitness landscape analysis to explore the underlying mechanisms of our proposed method; we establish black-box experimental settings to ensure reliable comparisons and practical relevance to real-world applications.

We believe that building upon and extending the foundations laid by EoH and FunSearch, as we have done, constitutes solid contributions.

Q1-1: The primary distinction or improvement over prior methods.

Please refer to our response to W1 and W2.

Q1-2: The contributions of designing reflections and prompt engineering.

We verify its contributions in Section 6. They are important for better sample efficiency (e.g. using less than 100 evaluations for designing strong heuristics). Sample efficiency is crucial for real-world applications where heuristic evaluation could be expensive.

Reflection is more effective when using capable LLMs, such as GPT-3.5 Turbo and its successors, as discussed in prior works [1]. Allowing a large number of heuristic evaluations, or implementing weak open-source LLMs, could obscure the impact of reflection or other prompting techniques, as reported in [5].

Q2: Implement ReEvo based on more open-source LLMs for ablation.

According to Shinn et al. [1], "self-reflection relies on the power of the LLM’s self-evaluation capabilities and not having a formal guarantee for success." Currently, many open-source LLMs are not capable enough to guarantee the statistically significant improvement of reflections. However, as LLM capabilities improve, we only expect this paradigm to get better over time [1].

Q3: Testing on the online bin packing problem.

Below we present the comparative results on online BPP (weibull 5k), which are averaged over 3 runs.

Q4: Testing EoH with the released code

We will test EoH with its released code and update the results.

Q5: Comparisons based on LLM calls.

ReEvo doubles LLM calls when performing crossover. However, we believe LLM inference can be easily sped up by scaling up hardware, and is rapidly technically evolving on both algorithmic and hardware fronts. In contrast, evaluating the generated heuristics can be costly in real-world applications. Therefore, we believe that comparisons based on heuristic evaluations are more practical and meaningful.

References:

[1] Shinn et al., Reflexion: language agents with verbal reinforcement learning, NeurIPS 2023

[2] Madaan et al., Self-Refine: Iterative Refinement with Self-Feedback, NeurIPS 2023

[3] Wang et al., TASTE: Teaching Large Language Models to Translate through Self-Reflection, ACL 2024

[4] Chen et al., DUAL-REFLECT: Enhancing Large Language Models for Reflective Translation through Dual Learning Feedback Mechanisms, ACL 2024

[5] Zhang et al., Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models, 2024

We deeply appreciate your time and effort in reviewing our work, the insightful questions and suggestions you raised, and your recognition of our contributions. We respond to your comments below.

W1: The paper's evolutionary focus may be limiting its appeal and perceived novelty to a broader audience, and rephrasing it to emphasize the method's natural approach could be beneficial.

Thank you for providing a fresh perspective on the technical presentation. We will adopt your suggestion to generalize the description of the reflection technique. As you suggest, this approach loads in-context knowledge without causing memory blowups. We believe this could broaden its appeal to a wider audience.

W2: The paper should clarify ReEvo's applicability to other string-based optimization scenarios and consider discussing a more generalized version of the method.

Thank you for this valuable suggestion. ReEvo is generally applicable to other string-based optimization scenarios as long as the reflecting over the relative performance of strings is meaningful. We exemplify its generality by applying it to prompt learning. We evolve prompts for formal logic reasoning task from MMLU, using random search, vanilla GA, and ReEvo, respectively. The results below present the classification accuracy against the number of prompt evaluations, where ReEvo demonstrates superior sample efficiency.