The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.
Paper
Similar papers
Peer review
Summary
This paper studies how to search for the best heuristics for combinatorial optimization problems (COPs) with large language models (LLM). The key idea is to use genetic programming (GP) to dynamically update the heuristics with LLM. Short-term reflection and long-term reflection are also incorporated in the GP algorithm as the guidance. The proposed methods are demonstrated on five different COPs and compared against other heuristic solvers and neural solvers.
Strengths
1. Applying LLM to generate heuristics for COPs is novel. 2. The experiements are extensive and in detail. 3. The paper is well-written and the idea is easy to understand, except that the details of the GP algorithm are a bit vague.
Weaknesses
1. The proposed ReEvo seems to rely on existing heuristic or neural solvers. Can ReEvo discover new heuristics independently? Incorporating LLM to generate heuristics for COPs is interesting, but it seems trivial if LLM can only be used as a post-processing to improve the existing methods. 2. The experiments are not conducted with state-of-the-art (SOTA) methods. For example, on TSP problem, can ReEvo improve the LKH-3 [1] solver? Can ReEvo improve the non-autoregressive neural solvers such as DIFUSCO [2], T2TCO [3]? 3. The writing in Sec. 4 needs improvement. For example, how the short-term and long-term reflection is utilized to improve heuristic design? how to guarantee the generated code is executable? [1] Helsgaun, Keld. "An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems." Roskilde: Roskilde University 12 (2017): 966-980. [2] Sun, Zhiqing, and Yiming Yang. "Difusco: Graph-based diffusion solvers for combinatorial optimization." Advances in Neural Information Processing Systems 36 (2023): 3706-3731. [3] Li, Yang, et al. "From distribution learning in training to gradient search in testing for combinatorial optimization." Advances in Neural Information Processing Systems 36 (2024).
Questions
I would appreciate the authors' response on my main concerns listed above.
Rating
5
Confidence
5
Soundness
3
Presentation
3
Contribution
2
Limitations
I have no concerns regarding the impact of the manuscript.
Request for Feedback
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.
Thank you for the rebuttal. While I have major concerns regarding your model's contributions to the CO community, you indeed conduct extensive experiments to demonstrate your model. So I will maintain my score, which is leaning acceptance.
Summary
The paper presents a LLM-enhanced evolutionary algorithm to solve diverse combinatorial optimization problems. The method is evaludated on various COPs and heuristics, however, the advantage of proposed method compared to recent ML4CO methods that does not use LLM requires more specification.
Strengths
1. The paper proposed a LLM-enhanced hyper-heuristic model to solve various combinatorial optimization problems. 2. Extensive experiments show the efficacy of the proposed method on five different COPs and multiple heuristics.
Weaknesses
1. Some details of model is not fully specified from the text, including the meaning, output of "short-term reflection" and "long-term reflection". It is unclear how the process is done and how this process completes the "reflection"？ 2. Though the proposed method has demonstrated the advances compared with heuristics, on specific problems (take TSP as example), there might be some recent models undiscussed in this paper that does not use heuristic but still achieve competitive results, such as [1,2] that conducts TSP experiments on 1000 and 10000. 3. The paper does not specify the costs of using LLM APIs, which could be real challenges when readers want to follow and reproduce the results in this paper. [1] Qiu R, Sun Z, Yang Y. Dimes: A differentiable meta solver for combinatorial optimization problems[J]. Advances in Neural Information Processing Systems, 2022, 35: 25531-25546. [2] Li Y, Guo J, Wang R, et al. From distribution learning in training to gradient search in testing for combinatorial optimization[J]. Advances in Neural Information Processing Systems, 2024, 36
Questions
1. What result does figure 4(B) shows, the obejective value or the gap towards the optimal? Without specifying the evaluation metric, it is difficult to interpret the results. 2. How does the proposed method compared to recent ML4CO method on TSP [1,2], or probably other methods on VRP? From my experience, hyper-heuristic methods may not perform well as these methods on solution quality or solving time. What is the advantage of LLM-enhanced heuristics in these COPs?
Rating
5
Confidence
3
Soundness
2
Presentation
3
Contribution
2
Limitations
The paper discuss some limitations, but the method may be limited by cost of LLM inference and problem scale.
Summary
This article proposes a large language model (LLM) assisted evolutionary computation (EC)-based method, to solve combinatorial optimization problems. It incorporates a reflection mechanism to enhance performance in black-box settings.
Strengths
1. The method shows an impressive performance on several CO problems with a black-box setting. 2. The article is well-written.
Weaknesses
1. The reflection technique has been well-developed and widely used in prompt engineering and code generation [1,2]. 2. Evolution methods based on LLM have been adopted in EOH [3] and Funsearch [4], limiting the contribution to the framework. [1] Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems 36 (2024). [2] Promptbreeder: Self-referential self-improvement via prompt evolution. arxiv preprint arxiv:2309.16797 (2023). [3] Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. Forty-first International Conference on Machine Learning. 2024. [4] Mathematical discoveries from program search with large language models. Nature 625.7995 (2024): 468-475.
Questions
1. As an EC-based method, what is the primary distinction or improvement compared to EoH, FunSearch, and other similar methods [1,2,3]? The reflection technique was developed early and is widely used in prompt engineering and code generation(Shown in Weakness1). To what extent do you think designing more complex reflection and prompt engineering strategies contributes to optimization [4]? 2. In the ablation experiments, Please include ReEvo based on more open-source LLMs (such as DeepSeek and Gemini). 3. Testing on the online bin packing problem is recommended [5]. 4. In Table 1, the result of EoH is drawn from the literature, testing it with the released code would be beneficial. 5. ReEvo requires three LLM calls to complete a single iteration, while other compared EC+LLM methods (such as EoH) only need one LLM call per iteration. Considering the comparison in the degree of LLM calls would be beneficial. [1] Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arxiv preprint arxiv:2309.08532 (2023). [2] Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization. arxiv preprint arxiv:2405.05767 (2024). [3] Large language models as evolutionary optimizers." arxiv preprint arxiv:2310.19046 (2023). [4] Are Large Language Models Good Prompt Optimizers?. arxiv preprint arxiv:2402.02101 (2024). [5] Mathematical discoveries from program search with large language models. Nature 625.7995 (2024): 468-475.
Rating
4
Confidence
5
Soundness
3
Presentation
3
Contribution
1
Limitations
N/A
Summary
The paper's contributions consist of multiple sections, which could be orthogonal: 1. The paper proposes a new ReEvo algorithm within the class of string-mutation evolutionary search methods. The core idea is to add a "Reflection LLM" which observes patterns over the history of trials, and proposes a new generation instruction for the regular Generator LLM. 2. This algorithm is applied on the area of combinatorial optimization, to mutate the code specifying a search heuristic. Experiments are conducted to: 1. Show better heuristic search over a variety problems and situations like Travelling Salesman (TSP), Ant Colony Optimization, Electronic Design Automation, and Neural Combinatorial Optimization 2. Ablate the importance of using the "Reflection LLM" especially over longer terms, and outperformance over other string-mutation methods like EoH.
Strengths
* This paper is very well written and structured. It demonstrates a strong understanding of the current literature and the nuanced differences against previous works, and their strengths/weaknesses. * The paper supports itself well with numerous experiments among multiple dimensions (e.g. varying combinatorial optimization applications, ablation studies on its own components, comparisons against other string-mutation baselines). * Overall, the paper does not have any glaring weaknesses and should be a solid accept.
Weaknesses
* The current writing style is a bit too strong on the evolutionary side (e.g. targeted towards an audience like GECCO), which makes parts of the paper unmotivated to readers who are not deep into the evolutionary literature. It becomes too easy to view the paper as a incremental improvement in the class of evolutionary string-mutation methods, which in itself is a good contribution, but not groundbreaking given previous works (PromptBreeder, FunSearch, and other works that the paper itself has cited). * There are possibly better ways to phrase the paper to make the method more natural. For example, I believe the Reflection LLM with its short-term + long-term variants, is effectively a technique to load in-context samples without incurring memory-blowups. * It is unclear whether ReEvo can be applied to any other string-based optimization scenarios (e.g. Prompt optimization, generic code search). Currently the Reflection LLM is very targeted towards summarizing combinatorial heuristics. If so, this would be nice to touch upon, or if not, this should be listed in the limitations section. * Following up on the above comment, this could imply that ReEvo is over-engineered at the moment; is there a more general and simpler variant of it, applicable to any string problems?
Questions
Please address my weaknesses above.
Rating
7
Confidence
4
Soundness
3
Presentation
4
Contribution
3
Limitations
Yes, in Section 7 (Conclusion).
A different writing strategy may have been better.
Thanks for the clarification. As I mentioned, because the focus of the paper is on combinatorial heuristics, this is causing the other reviewers to require multiple comparisons to SOTA combinatorial optimizers, which I'm not sure is even worth the time to address. I think the strategy of phrasing the paper's contributions in terms of the general algorithm (rather than specific combinatorial application) may have been better. I retain my score, but acknowledge the above issue may lead to a possible rejection of the paper.
Thank you for reviewing
Thank you for reviewing. We will follow your suggestions to rephrase the paper's contributions. Regarding the comparison with SOTA heuristic solvers (e.g. LKH), LHHs are general and versatile. They are especially suitable for cases where expert knowledge is lacking or the problem is treated as a black box. Regarding the comparison with SOTA ML4CO optimizers, LHHs demonstrate unique strengths: - 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.
Thank you for your explanations. I still have a few concerns that I would appreciate further clarification on. > W1 and W2 follow up: Firstly, while it is mentioned that LLM-based methods are less likely to cause memory blowups (such as compared to learning-based methods or complex heuristics like LKH3), this does not seem to highlight the specific contribution of integrating the self-reflection technique. Additionally, although I understand that reflection can enhance performance, it appears to me that the paradigm you proposed is more of a combination of the reflection technique and Evolutionary Computation (EC). This essentially allows the LLM to generate dynamic prompts to guide heuristic generation, as opposed to manually designed prompts used in the methods you compared. Moreover, in your experiments, did you control parameters such as the population size or LLM calls to prove that your proposed paradigm is overall superior to the state-of-the-art methods? > Q2 follow up: Could you clarify whether the performance of your proposed method varies significantly when applied to different LLMs? If so, should this be considered a major challenge for researchers attempting to follow your work, given that your method seems to rely heavily on the choice of LLM? > Q5 follow up: I still have some concerns about the logic presented. You mentioned that LLM inference can be accelerated through hardware scaling and that there are rapid advancements in both algorithmic and hardware technologies. However, currently, would it be fair to assume that comparisons based on LLM call counts could still lead to inconsistencies in terms of cost and performance?
Further clarifications
We appreciate your response. Below we clarify your remaining concerns. > LLM-based methods are less likely to cause memory blowups; mitigating memory blowups is not the contribution of EA-reflection integration. It seems there may be a misunderstanding regarding the concept of memory blowups in this context. Here, memory blowups do not refer to GPU memory usage (though that is also a concern). Instead, **it refers to the LLM agent's memory**. An LLM agentic architecture involves modules for (1) profile, (2) memory, (3) planning, and (4) action [1]. During its interactions with the environment (in our context, designing heuristics and receiving their fitness values as feedback), the agent's memory module stores the agent's experiences [1]. Although we want to load as much experience as possible into the LLM's context during inference, the context length is limited; the LLM's capability to process in-context knowledge/examples is also limited. This is the memory blowup we are referring to. In ReEvo, short-term reflections interpret the environmental feedback in each round of interaction. Long-term reflections distill the accumulated experiences and knowledge so that they can be loaded into context during inference without causing memory blowups. We hope this clarifies the contribution of EA-reflection integration in mitigating memory blowups. [1] A Survey on Large Language Model-based Autonomous Agents, 2024 > Automated dynamic prompting for heuristic generation. Leveraging reflections to dynamically guide heuristic generation with accumulated knowledge is the core contribution of ReEvo. We hope ReEvo can inspire future research in combining EC with LLMs to eliminate manual prompt design and enhance the EoH performance with LLMs-derived prompts. > Control parameters for comparisons Due to the combinational nature of the parameter space, we believe it's reasonable to use the original parameters of the compared methods. > Does your method's performance vary significantly with different LLMs, posing a major challenge for researchers replicating it? LLM reasoning techniques generally show performance variations across different LLMs [1]. It is not challenging for researchers to follow our work, as it is evident that stronger LLMs are better at leveraging reflections or general reasoning techniques [1]. We recommend using advanced LLMs (e.g., GPT-3.5-turbo and its successors) to maximize the utility of reflection and other LLM techniques that require reasoning capabilities [1]. In the future, we only expect LLMs to become even more powerful and more capable of leveraging reflections [2]. [1] Reasoning with Language Model Prompting: A Survey, 2024 [2] Reflexion: Language agents with verbal reinforcement learning, 2023 > Would it be fair to assume that comparisons based on LLM call counts could still lead to inconsistencies in terms of cost and performance? When a large number of heuristic evaluations are permitted, the performance of different EAs within the EoH/LHH context becomes nearly indistinguishable [1]. Therefore, we believe the primary goal of designing better EAs is to **address scenarios where heuristic evaluations are costly**, which is common in many industrial applications. To this end, we propose ReEvo and adopt an experimental setting that limits heuristic evaluations. LLM inference today, whether through local models or commercial APIs, **is already highly cost-effective**—both in terms of expense (e.g., about $0.0003 per call in ReEvo using GPT-3.5-turbo) and time (e.g., less than one second on average with asynchronous API calls or batched inference). These costs are negligible compared to real-world heuristic evaluations, which, even on simplified academic benchmarks, can take over 20 minutes per evaluation in EDA problems. **LLM reasoning techniques** (e.g., Chain of Thought or CoT) offer another perspective for fair comparisons. Although variants like Tree of Thought (ToT), Graph of Thought (GoT), and MCTS-based methods require more LLM calls, performance is typically assessed by the final evaluation outcomes, such as k-shot solution assessments, similar to k heuristic evaluations in the EoH/LHH context. If one has to compare EoH/LHHs based on LLM inference costs, it is essential to consider token usage, as tokens determine both the cost and time, not the number of LLM calls. Requiring additional heuristic descriptions, as in EoH, increases these costs, which ReEvo avoids. In summary, comparing LLMs based on the number of LLM calls is less reasonable or meaningful. [1] Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models, 2024
Request for Feedback
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 clarifications. Please let us know if you have any further questions or concerns.
Thank you for your clarification. 1. I still have concerns about the performance under different LLMs. I believe it is necessary to test the performance under different LLMs: 1.) GPT is one of the LLMs with the best overall performance; however, it might not necessarily be the best model for heuristic design combined with search methods. For instance, certain LLMs may provide better results in tasks. Additionally, it is worth exploring whether different LLMs are better suited for reflection and code generation tasks, as well as choosing the most appropriate model for this specific task. 2.) Testing different LLMs would help in understanding the performance boundaries of the method and assist users in various application scenarios in selecting the most suitable LLM configuration. The most optimal LLM configuration for different combinatorial optimization heuristic design tasks may vary. 3.) GPT is closed-source and cannot be deployed locally, which makes it challenging to use in many industry scenarios where API is unavailable. 2. The results on bin packing are not convincing. With a specific setting, the results are much worse than those in the FunSearch and EoH papers. I know it's difficult to add experiments during the rebuttal period. I will increase my score by 1. But I still think it's an incremental work based on FunSearch and EoH with marginal novelty.
Thanks for reviewing
Thank you for reviewing. In the future update, we commit to adding more experiments based on your suggestions. We would like to, again, respectfully argue that our work meaningfully extends FunSearch and EoH through three primary lenses: (1) the search algorithm, (2) the downstream CO applications, and (3) the evaluation methodologies. - Search Algorithm: We introduce the Reflective Evolution, 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.
Request for Feedback
Dear reviewers, as the author-reviewer discussion phase is coming to an end, please let us know if there are further questions or concerns to address. Thanks in advance for your time and consideration!
Thanks for the author's detailed response. I agree with the point on the distinctive advantage of LHH compared with ML4CO, where LHH could benefit CO problem-solving. I would raise my score to 5.
Decision
Accept (poster)