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

Authors: haoran  ye
jiarui  wang
zhiguang  cao
federico  berto
chuanbo  hua
haeyeon  kim
jinkyoo  park
guojie  song
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:43:02

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

Main paper: 
 introduction: 
 NP-hard combinatorial optimization problems (COPs) pervade numerous real-world systems, each characterized by distinct constraints and objectives. The intrinsic complexity and heterogeneity of these problems compel domain experts to laboriously develop heuristics for their approximate solutions [23] . Automation of heuristic designs represents a longstanding pursuit.Classic Hyper-Heuristics (HHs) automate heuristic design by searching for the best heuristic (combination) from a set of heuristics or heuristic components [64] . Despite decades of development, HHs are limited by heuristic spaces predefined by human experts [64] . The rise of large language models (LLMs) opens up new possibilities for HHs. This paper introduces the general concept of Language Hyper-Heuristics (LHH) to advance beyond preliminary attempts in individual COP settings [68, 46] . LHH constitutes an emerging variant of HH that utilizes LLMs for heuristic generations. It features minimal human intervention and open-ended heuristic spaces, showing promise to comprehensively shift the HH research paradigm.Pure LHH (e.g., LLM generations alone) is sample-inefficient and exhibits limited inference capability for black-box COPs. This work elicits the power of LHH with Reflective Evolution (ReEvo). ReEvo couples evolutionary search for efficiently exploring heuristic spaces, with self-reflections to boost the reasoning capabilities of LLMs. It emulates human experts by reflecting on the relative performance of two heuristics and gathering insights across iterations. This reflection approach is analogous to interpreting genetic cues and providing "verbal gradient" within search spaces. We introduce fitness landscape analysis and black-box prompting for reliable evaluation of LHHs. The dual-level reflections are shown to enhance heuristic search and induce verbal inference for black-box COPs, enabling ReEvo to outperform prior state-of-the-art (SOTA) LHH [47] .We introduce novel applications of LHHs and yield SOTA solvers with ReEvo: (1) We evolve penalty heuristics for Guided Local Search (GLS), which outperforms SOTA learning-based [52, 24, 75] and knowledge-based [1] (G)LS solvers. (2) We enhance Ant Colony Optimization (ACO) by evolving its heuristic measures, surpassing both neural-enhanced heuristics [94] and expert-designed heuristics [71, 6, 72, 17, 39] . (3) We refine the genetic algorithm (GA) for Electronic Design Automation (EDA) by evolving genetic operators, outperforming expert-designed GA [63] and the SOTA neural solver [31] for the Decap Placement Problem (DPP). ( 4) Compared to a classic HH [15] , ReEvo generates superior constructive heuristics for the Traveling Salesman Problem (TSP). (5) We enhance the generalization of SOTA neural combinatorial optimization (NCO) solvers [37, 51] by evolving heuristics for attention reshaping. For example, we improve the optimality gap of POMO [37] from 52% to 29% and LEHD [51] from 3.2% to 3.0% on TSP1000, with negligible additional time overhead and no need for tuning neural models.We summarize our contributions as follows. (1) We propose the concept of Language Hyper-Heuristics (LHHs), which bridges emerging attempts using LLMs for heuristic generation with a methodological group that enjoys decades of development. (2) We present Reflective Evolution (ReEvo), coupling evolutionary computation with humanoid reflections to elicit the power of LHHs. We introduce fitness landscape analysis and black-box prompting for reliable LHH evaluations, where ReEvo achieves SOTA sample efficiency. (3) We introduce novel applications of LHHs and present SOTA COP solvers with ReEvo, across five heterogeneous algorithmic types and six different COPs. 
related work: 
 Traditional Hyper-Heuristics. Traditional HHs select the best performing heuristic from a predefined set [13] or generate new heuristics through the combination of simpler heuristic components [15, 104] . HHs offer a higher level of generality in solving various optimization problems [109, 96, 19, 44, 103, 58] , but are limited by the heuristic space predefined by human experts.Neural Combinatorial Optimization. Recent advances of NCO show promise in learning endto-end solutions for COPs [2, 93, 3] . NCO can be regarded as a variant of HH, wherein neural architectures and solution pipelines define a heuristic space, and training algorithms search within it. A well-trained neural network (NN), under certain solution pipelines, represents a distinct heuristic. From this perspective, recent advancements in NCO HHs have led to better-aligned neural architectures [28, 51, 34, 73] and advanced solution pipelines [32, 52, 42, 89, 95, 12, 5] to define effective heuristic spaces, and improved training algorithms to efficiently explore heuristic spaces [33, 27, 14, 76, 18, 90, 79, 35] , while targeting increasingly broader applications [9, 107, 54, 77] . In this work, we show that ReEvo-generated heuristics can outperform or enhance NCO methods.LLMs for code generation and optimization. The rise of LLMs introduces new prospects for diverse fields [88, 82, 105, 25, 50, 99] . Among others, code generation capabilities of LLMs are utilized for code debugging [10, 49] , enhancing code performance [55] , solving algorithmic competition challenges [41, 70] , robotics [38, 43, 81] , and general task solving [92, 102] . Interleaving LLM generations with evaluations [74] yields powerful methods for prompt optimization [108, 83, 20] , reinforcement learning (RL) reward design [53] , algorithmic (self-)improvement [98, 48, 45] , neural architecture search [8] , and general solution optimization [91, 4, 80] , with many under evolutionary frameworks [57, 87, 21, 7, 40] . Most related to ReEvo, concurrent efforts by Liu et al. [47] and Romera-Paredes et al. [68] leverage LLMs to develop heuristics for COPs. We go beyond and propose generic LHH for COPs, along with better sample efficiency, broader applications, more reliable evaluations, and improved heuristics. In addition, ReEvo contributes to a smoother fitness landscape, showing the potential to enhance other tasks involving LLMs for optimization. We present further discussions in Appendix A.Self-reflections of LLMs. Shinn et al. [70] propose to reinforce language agents via linguistic feedback, which is subsequently harnessed for various tasks [56, 84] . While Shinn et al. [70] leverage binary rewards indicating passing or failing test cases in programming, ReEvo extends the scope of verbal RL feedback to comparative analysis of two heuristics, analogous to verbal gradient information [66] within heuristic spaces. Also, ReEvo incorporates reflection within an evolutionary framework, presenting a novel and powerful integration. 
language hyper-heuristics for combinatorial optimization: 
 HHs explore a search space of heuristic configurations to select or generate effective heuristics, indirectly optimizing the underlying COP. This dual-level framework is formally defined as follows.Definition 3.1 (Hyper-Heuristic). For COP with solution space S and objective function f : S → R, a Hyper-Heuristic (HH) searches for the optimal heuristic h * in a heuristic space H such that a meta-objective function F : H → R is minimized, i.e., h * = argmin h∈H F (h).Depending on how the heuristic space H is defined, traditional HHs can be categorized into selection and generation HHs, both entailing manually defined heuristic primitives. Here, we introduce a novel variant of HHs, Language Hyper-Heuristics (LHH), wherein heuristics in H are generated by LLMs. LHHs dispense with the need for predefined H, and instead leverage LLMs to explore an open-ended heuristic space. We recursively define LHHs as follows.Definition 3.2 (Language Hyper-Heuristic). A Language Hyper-Heuristic (LHH) is an HH variant where heuristics in H are generated by LLMs.In this work, we define the meta-objective function F as the expected performance of a heuristic h for certain COP. It is estimated by the average performance on a dataset of problem instances. 
language hyper-heuristic with reevo: 
 LHH takes COP specifications as input and outputs the best inductive heuristic found for this COP. Vanilla LHH can be repeated LLM generations to randomly search the heuristic space, which is sample-inefficient and lacks reasoning capabilities for complex and black-box problems (see § 6) . Therefore, we propose Reflective Evolution (ReEvo) to interpret genetic cues of evolutionary search and unleash the power of LHHs.ReEvo is schematically illustrated in Fig. 1 . Under an evolutionary framework, LLMs assume two roles: a generator LLM for generating individuals and a reflector LLM for guiding the generation with reflections. ReEvo, as an LHH, features a distinct individual encoding, where each individual is the code snippet of a heuristic. Its evolution begins with population initialization, followed by five iterative steps: selection, short-term reflection, crossover, long-term reflection, and elitist mutation. We evaluate the meta-objective of all heuristics, both after crossover and mutation. Our prompts are gathered in Appendix B.Individual encoding. ReEvo optimizes toward best-performing heuristics via an evolutionary process, specifically a Genetic Programming (GP). It diverges from traditional GPs in that (1) individuals are code snippets generated by LLMs, and (2) individuals are not constrained by any predefined encoding format, except for adhering to a specified function signature.Population initialization. ReEvo initializes a heuristic population by prompting the generator LLM with a task specification. A task specification contains COP descriptions (if available), heuristic designation, and heuristic functionality. Optionally, including seed heuristics, either trivial or expertly crafted to improve upon, can provide in-context examples that encourage valid heuristic generation and bias the search toward more promising directions.A ReEvo iteration contains the following five sequential steps. Selection. ReEvo selects parent pairs from successfully executed heuristics at random, while avoiding pairing heuristics with an identical meta-objective value F .Short-term reflection. For each pair of heuristic parents, the reflector LLM reflects upon their relative performance and gives hints accordingly for improved design. Unlike prior work [70] , ReEvo integrates the reflections into evolutionary search and reflects by performing comparative analyses.Our proposed approach is analogous to interpreting genetic cues and providing verbal gradients within search spaces, which leads to smoother fitness landscapes and better search results (see § 6.1).Crossover. ReEvo prompts the generator LLM to generate an offspring heuristic, given task specifications, a pair of parent heuristics, explicit indications of their relative performance, short-term reflections over the pair, and generation instructions.Long-term reflection. ReEvo accumulates expertise in improving heuristics via long-term reflections. The reflector LLM, given previous long-term reflections and newly gained short-term ones, summarizes them and gives hints for improved heuristic design.Elitist mutation. ReEvo employs an elitist mutation approach. Based on long-term reflections, the generator LLM samples multiple heuristics to improve the current best one. A mutation prompt consists of task specifications, the elite heuristic, long-term reflections, and generation instructions.Viewing ReEvo from the perspective of an LLM agentic architecture [88] , short-term reflections interpret the environmental feedback from each round of interaction. Long-term reflections distill accumulated experiences and knowledge, enabling them to be loaded into the inference context without causing memory blowups. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Full experimental details and results are provided in § 5, § 6, Appendix B, Appendix C, and Appendix D. Our code is also available. 
penalty heuristics for guided local search: 
 We evolve penalty heuristics for Guided Local Search (GLS) [1] . GLS interleaves local search with solution perturbation. The perturbation is guided by the penalty heuristics to maximize its utility.ReEvo searches for the penalty heuristic that leads to the best GLS performance.We implement the best heuristic generated by ReEvo within KGLS [1] and refer to such coupling as KGLS-ReEvo. In Table 1 , we compare KGLS-ReEvo with the original KGLS, other GLS variants [24, 75, 47] , and SOTA NCO method that learns to improve a solution [52] . The results show that ReEvo can improve KGLS and outperform SOTA baselines. In addition, we use a single heuristic for TSP20 to 200, while NCO baselines require training models specific to each problem size. †: The results are drawn from the original literature. ‡: They are based on our own GLS implementation.Solutions to COPs can be stochastically sampled, with heuristic measures indicating the promise of solution components and biasing the sampling. Ant Colony Optimization (ACO), which interleaves stochastic solution sampling with pheromone update, builds on this idea. We generate such heuristic measures for five different COPs: TSP, CVRP, OP, MKP, and BPP.Under the ACO framework, we evaluate the best ReEvo-generated heuristics against the expertdesigned ones and neural heuristics specifically learned for ACO [94] . The evolution curves displayed in Fig. 2 verify the consistent superiority of ReEvo across COPs and problem sizes. Notably, on 3 out of 5 COPs, ReEvo outperforms DeepACO [94] even when the latter overfits the test problem size (TSP50, OP50, and MKP100). We observe that most ReEvo-generated heuristics show consistent performance across problem sizes and distributions. Hence, their advantages grow as the distributional shift increases for neural heuristics.Expert-designed GAs are widely adopted in EDA [69, 97, 11, 26] . Besides directly solving EDA problems, GA-generated solutions can be used to train amortized neural solvers [31] . Here, we show that ReEvo can improve the expert-designed GAs and outperform DevFormer [31] , the SOTA solver for the DPP problem. We sequentially evolve with ReEvo the crossover and mutation operators for the GA expert-designed by Park et al. [63] . Fig. 3 compares online and offline learned methods, DevFormer, the original expert-designed GA, and the GA with ReEvo-generated operators, showing that the ReEvo-designed GA outperforms previous methods and, importantly, both the expert-designed GA and DevFormer.Heuristics can be used for deterministic solution construction by sequentially assigning values to each decision variable. We evaluate the constructive heuristic for TSP generated by ReEvo on real-world benchmark instances from TSPLIB [67] in Table 2 . ReEvo can generate better heuristics than GHPP [15] , a classic HH based on GP.Autoregressive NCO solvers suffer from limited scaling-up generalization [29] , partially due to the dispersion of attention scores [85] . Wang et al. [85] design a distance-aware heuristic to reshape the attention scores, which improves the generalization of NCO solvers without additional training. However, the expert-designed attention-reshaping can be suboptimal and does not generalize across neural models or problem distributions.Here we show that ReEvo can automatically and efficiently tailor attention reshaping for specific neural models and problem distributions of interest. We apply attention reshaping designed by experts [85] and ReEvo to two distinct model architectures: POMO with heavy encoder and light decoder [37] , and LEHD with light encoder and heavy decoder [51] . On TSP and CVRP, Table 3 compares the original NCO solvers [37, 51] , those with expert-designed attention reshaping [85] , and those with ReEvo-designed attention reshaping. The results reveal that the ReEvo-generated heuristics can improve the original models and outperform their expert-designed counterparts. Note that implementing ReEvo-generated attention reshaping takes negligible additional time; e.g., solving a CVRP1000 with LEHD takes 50.0 seconds with reshaping, compared to 49.8 seconds without.6 Evaluating ReEvoQuestion: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Our code is available, with sufficient instructions to faithfully reproduce the main experimental results. 
fitness landscape analysis: 
 The fitness landscape of a searching algorithm depicts the structure and characteristics of its search space F : H → R [59] . This understanding is essential for designing effective HHs. Here we introduce this technique to LHHs and evaluate the impact of reflections on the fitness landscape.Traditionally, the neighborhood of a solution is defined as a set of solutions that can be reached after a single move of a certain heuristic. However, LHHs feature a probabilistic nature and open-ended search space, and we redefine its neighborhood as follows. Definition 6.1 (Neighborhood). Let LLM denote an LHH move, x a specific prompt, and h c the current heuristic. Given LLM and x, the neighborhood of h c is defined as a set N , where each EQUATIONHere, LLM (h|h c , x) denotes the probability of generating h after prompting with h c and x, and ξ is a small threshold value. In practice, the neighborhood can be approximated by sampling from the distribution LLM (•|h c , x) for a large number of times.We extend the concept of autocorrelation to LHHs under our definition of neighborhood. Autocorrelation reflects the ruggedness of a landscape, indicating the difficulty of a COP [59, 22] . Definition 6.2 (Autocorrelation). Autocorrelation measures the correlation structure of a fitness landscape. It is derived from the autocorrelation function r of a time series of fitness values, which are generated by a random walk on the landscape via neighboring points:EQUATION)where f is the mean fitness of the points visited, T is the size of the random walk, and i is the time lag between points in the walk.Based on the autocorrelation function, correlation length is defined below [86] . Definition 6.3 (Correlation Length). Given an autocorrelation function r, the correlation length l is formulated as l = -1/ ln(|r 1 |) for r 1 ̸ = 0. It reflects the ruggedness of a landscape, and smaller values indicate a more rugged landscape.To perform autocorrelation analysis for ReEvo, we conduct random walks based on the neighborhood established with our crossover prompt either with or without short-term reflections. In practice, we set the population size to 1 and skip invalid heuristics; the selection always picks the current and last heuristics for short-term reflection and crossover, and we do not implement mutation. In this section, we investigate the effects of the proposed components of ReEvo with both white and black-box prompting.Black-box prompting. We do not reveal any information related to the COPs and prompt LHHs in general forms (e.g., edge_attr in place of distance_matrix). Black-box settings allow reliable evaluations of LHHs in designing effective heuristics for novel and complex problems, rather than merely retrieving code tailored for prominent COPs from their parameterized knowledge. We evaluate sampling LLM generations without evolution (LLM) and ReEvo without long-term reflections, short-term reflections, crossover, or mutation on generating ACO heuristics for TSP100. Table 5 shows that ReEvo enhances sample efficiency, and all its components positively contribute to its performance, both in white-box and black-box prompting.This section compares ReEvo with EoH [47] , a recent SOTA LHH that is more sample-efficient than FunSearch [68] . We adhere to the original code and (hyper)parameters of EoH. Our experiments apply both LHHs to generate ACO heuristics for TSP, CVRP, OP, MKP, and BPP, using black-box prompting and three LLMs: GPT-3.5 Turbo, GPT-4 Turbo, and Llama 3 (70B). MKP100 Figure 4 : Comparisons between EoH [47] and ReEvo on five COPs with black-box prompting and using different LLMs. We perform three runs for each setting.↑ E o H R eE v o E o H R eE v o E o H RQuestion: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: See § 5, § 6, Appendix B, Appendix C, and Appendix D.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
discussions and limitations: 
 When to use ReEvo as an LHH. Our experiments limit the number of heuristic evaluations to 100 shots and the results do not necessarily scale up. ReEvo is designed for scenarios where sample efficiency is crucial, such as real-world applications where heuristic evaluation can be costly. Allowing a large number of heuristic evaluations could obscure the impact of reflection or other prompting techniques, as reported by Zhang et al. [101] .When to use ReEvo as an (alternative to) NCO/ML4CO method. LHH can be categorized as an NCO/ML4CO method. However, to facilitate our discussion, we differentiate LHHs from "traditional" NCO methods that usually train NN-parameterized heuristics via parameter adjustment.In § 5, we demonstrate that ReEvo can either outperform or enhance NCO methods. Below, we explore the complementary nature of LHH and NCO methods.• Rule-based v.s. NN-parameterized policies. LHHs generate interpretable and rule-based heuristics (code snippets), while NCO generates black-box NN-parameterized policies. Interpretable heuristics offer insights for human designers and can be more reliable in practice when faced with dynamic environments, limited data, distributional shifts, or adversarial attacks. However, they may not be as expressive as neural networks and may underfit in complex environments. The choice of LLMs for ReEvo. Reflection is more effective when using capable LLMs, such as GPT-3.5 Turbo and its successors, as discussed by Shinn et al. [70] . Currently, many open-source LLMs are not capable enough to guarantee statistically significant improvement of reflections [101] . However, as LLM capabilities improve, we only expect this paradigm to get better over time [70] .One can refer to [101] for extended evaluations based on more LLMs and problem settings.Benchmarking LHHs based on heuristic evaluations. We argue that benchmarking LHHs should prioritize the number of heuristic evaluations rather than LLM query budgets [101] due to the following reasons.• Prioritizing scenarios where heuristic evaluations are costly leads to meaningful comparisons between LHHs. The performance of different LHH methods becomes nearly indistinguishable when a large number of heuristic evaluations are allowed [101] . • The overhead of LLM queries is negligible compared to real-world heuristic evaluations. LLM inference-whether via local models or commercial APIs-is highly cost-effective nowadays, with expenses averaging around $0.0003 per call in ReEvo using GPT-3.5-turbo, and response times of under one second on average for asynchronous API calls or batched inference. These costs are negligible compared to real-world heuristic evaluations, which, taking the toy EDA problem in this paper as an example, exceeds 20 minutes per evaluation. • Benchmarking LHHs based on LLM inference costs presents additional challenges. Costs and processing time are driven by token usage rather than the number of queries, complicating the benchmarking process. For instance, EoH [47] requires heuristic descriptions before code generation, resulting in higher token usage. In contrast, although ReEvo involves more queries for reflections, it is more token-efficient when generating heuristics.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: See Fig. 3 , Table 4 , Fig. 4 , Table 5 , etc. 
conclusion: 
 This paper presents Language Hyper-Heuristics (LHHs), a rising variant of HHs, alongside Reflective Evolution (ReEvo), an evolutionary framework to elicit the power of LHHs. Applying ReEvo across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, we yield state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers. Comparing against SOTA LHH [47] , ReEvo demonstrates superior sample efficiency. The development of LHHs is still at its emerging stage. It is promising to explore their broader applications, better dual-level optimization architectures, and theoretical foundations. We also expect ReEvo to enrich the landscape of evolutionary computation, by showing that genetic cues can be interpreted and verbalized using LLMs.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: See Appendix C.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• We recognize that providing effective safeguards challenging, and papers do not this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: See Appendix F.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing with human subjects.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Our work is developed concurrently with Evolution of Heuristics (EoH) [47] , which establishes the groundwork for this emerging field. Nonetheless, our work extends the boundaries of LHH 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 LHH to five heterogeneous algorithmic types and six different COPs, advancing the state-of-the-art in GLS, EDA, ACO, and NCO. • 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.ReEvo is generally applicable to other string-based optimization scenarios [57] as long as reflecting the relative performance of strings is meaningful. Preliminary experiments on prompt tuning verify the advantage of ReEvo over random search and vanilla genetic programming. Furthermore, we identify in reasoning-capable LLM approaches released after ReEvo such as OpenAI o1 [106] an interesting avenue of future works and experimentation that could yield even better sample efficiency and performance.We gather prompts used for ReEvo in this section. Our prompt structure is flexible and extensible.To adapt ReEvo to a new problem setting, one only needs to define its problem description, function description, and function signature.The prompt formats are given below. They are used for all COP settings.You are an expert in the domain of optimization heuristics . Your task is to design heuristics that can effectively solve optimization problems. Your response outputs Python code and nothing else . Format your code as a Python code string : "''' python ... '''".Prompt 1: System prompt for generator LLM. § ¤You are an expert in the domain of optimization heuristics . Your task is to give hints to design better heuristics . You respond with some hints for designing better heuristics , based on the two code versions and using less than 20 words.Prompt 5: User prompt for short-term reflection. Prompt 7: User prompt for crossover.The function signature variables here are used to adjust function names with their versions, which is similar to the design in [68] . For example, when designing "heuristics", the worse code is named "heuristics_v0" while the better code "heuristics_v1". In Prompt 9, the elitist code is named "heuristic_v1".Below is your prior long-term reflection on designing heuristics for { problem_description } { prior_long -term_reflection } Below are some newly gained insights . {new_short-term_reflections } Write constructive hints for designing better heuristics , based on prior reflections and new insights and using less than 50 words. Prompt 9: User prompt for elitist mutation.Problem-specific prompt components are given below.• Problem descriptions of all COP settings are given in Table 6 .• The function descriptions of all COP settings are presented in The 'heuristics' function takes as input a distance matrix, and returns prior indicators of how bad it is to include each edge in a solution. The return is of the same shape as the input.The 'heuristics' function takes as input a distance matrix, and returns prior indicators of how promising it is to include each edge in a solution. The return is of the same shape as the input.The 'heuristics' function takes as input a matrix of edge attributes with shape '(n_edges, n_attributes)', where 'n_attributes=1' in this case. It computes prior indicators of how promising it is to include each edge in a solution. The return is of the shape of '(n_edges,)'.The 'heuristics' function takes as input a distance matrix (shape: n by n), Euclidean coordinates of nodes (shape: n by 2), a vector of customer demands (shape: n), and the integer capacity of vehicle capacity. It returns prior indicators of how promising it is to include each edge in a solution. The return is of the same shape as the distance matrix. The depot node is indexed by 0.CVRP_ACO_black-box The 'heuristics' function takes as input a matrix of edge attributes (shape: n by n) and a vector of node attributes (shape: n). A special node is indexed by 0. 'heuristics' returns prior indicators of how promising it is to include each edge in a solution. The return is of the same shape as the input matrix of edge attributes.OP_ACO Suppose 'n' represents the number of nodes in the problem, with the depot being the first node. The 'heuristics' function takes as input a 'prize' array of shape (n,), a 'distance' matrix of shape (n,n), and a 'max_len' float which is the constraint to total travel distance, and it returns 'heuristics' of shape (n, n), where 'heuristics[i][j]' indicates the promise of including the edge from node #i to node #j in the solution.The 'heuristics' function takes as input a vector of node attributes (shape: n), a matrix of edge attributes (shape: n by n), and a constraint imposed on the sum of edge attributes. A special node is indexed by 0. 'heuristics' returns prior indicators of how promising it is to include each edge in a solution. The return is of the same shape as the input matrix of edge attributes. MKP_ACO Suppose 'n' indicates the scale of the problem, and 'm' is the dimension of weights each item has. The constraint of each dimension is fixed to 1. The 'heuristics' function takes as input a 'prize' of shape (n,), a 'weight' of shape (n, m), and returns 'heuristics' of shape (n,). 'heuristics[i]' indicates how promising it is to include item i in the solution.MKP_ACO_black-box Suppose 'n' indicates the scale of the problem, and 'm' is the dimension of some attributes each involved item has. The 'heuristics' function takes as input an 'item_attr1' of shape (n,), an 'item_attr2' of shape (n, m), and returns 'heuristics' of shape (n,). 'heuristics[i]' indicates how promising it is to include item i in the solution. indicates how promising it is to put item i and item j in the same bin.BPP_ACO_black-box Suppose 'n' represents the scale of the problem. The heuristics function takes as input an 'item_attr' array of shape (n,) and an integer as a certain constraint imposed on the item attributes. The heuristics function returns a 'heuristics' array of shape (n, n). 'heuristics[i][j]' indicates how promising it is to group item i and item j.The select_next_node function takes as input the current node, the destination node, a set of unvisited nodes, and a distance matrix, and returns the next node to visit.Hyperparameters for ReEvo. Unless otherwise stated, we adopt the parameters in Table 8 for ReEvo runs.During initialization, the LLM temperature is added by 0.3 to diversify the initial population.Heuristic generation pipeline. We perform 3 ReEvo runs for each COP setting. Unless otherwise stated, the heuristic with the best validation performance is selected for final testing on 64 held-out instances.Cost and hardware. When the hardware permits, heuristics from the same generation are generated, reflected upon, and evaluated in parallel. The duration of a single ReEvo run can range from approximately two minutes to hours, depending on the evaluation runtime and the hardware used. Each run costs about $0.06 when using GPT3.5 Turbo. When conducting runtime comparisons, we employ a single core of an AMD EPYC 7742 CPU and an NVIDIA GeForce RTX 3090 GPU.Guided Local Search (GLS) explores solution space through local search operations under the guidance of heuristics. We aim to use ReEvo to find the most effective heuristics to enhance GLS. In our experimental setup, we employed a variation of the classical GLS algorithm [78] that incorporated perturbation phases [1] , wherein edges with higher heuristic values will be prioritized for penalization. In the training phase, we evaluate each heuristic with TSP200 using 1200 GLS iterations. For generating results in Table 1 , we use the parameters in Table 9 . The iterations stop when reaching the predefined threshold or when the optimality gap is reduced to zero.Ant Colony Optimization is an evolutionary algorithm that interleaves solution samplings with the update of pheromone trails. Stochastic solution samplings are biased toward more promising solution space by heuristics, and ReEvo searches for the best of such heuristics. For more details, please refer to [94] .Table 10 presents the ACO parameters used for heuristic evaluations during LHH evolution. They are adjusted to maximize ACO performance while ensuring efficient evaluations. Instance generations and ACO implementations follow Ye et al. [94] . To conduct tests in Fig. 2 , we increase the number of iterations to ensure full convergence.Here we briefly introduce the expert-design GA for DPP. Further details can be found in [31, Appendix B] .The GA designed by Kim et al. [31] is utilized as an expert policy to collect expert guiding labels for imitation learning. The GA is a widely used search heuristic method for the Decoupling Capacitor Placement Problem (DPP), which aims to find the optimal placement of a given number of decoupling capacitors (decaps) on a Power Distribution Network (PDN) with a probing port and 0-15 keep-out regions to best suppress the impedance of the probing port.Key aspects of the designed GA include: • Encoding and initialization. The GA generates an initial population randomly, and each solution consists of a set of numbers representing decap locations on the PDN. The population size is fixed to 20, and each solution is evaluated and sorted based on its objective value.• Elitism. After the initial population is formulated, the top-performing solutions (elite population) are kept for the next generation. The size of the elite population is predefined as 4.• Selection. The better half of the population is selected for crossover.• Crossover. This process generates new population candidates by dividing each solution from the selected population in half and performing random crossover.• Mutation. After crossover, solutions with overlapping numbers are replaced with random numbers while avoiding locations of the probing port and keep-out regions.In this work, we sequentially optimize the crossover and mutation operators using ReEvo. When optimizing crossover, all other components of the GA pipeline remain identical to the expert-designed one. When optimizing mutation, we additionally set the crossover operator to the best one previously generated by ReEvo.During training, we evaluate F on three training instances randomly generated following [31, Appendix A.5 ].The evaluation on each instance runs 10 GA iterations and returns the objective value of the best-performing solution. For the final test in Fig. 3 , we utilize the same test dataset as in [31] .For autoregressive NCO solvers, e.g. POMO [37] and LEHD [51] , the last decoder layer outputs the logits of the next node to visit. Then, the attention-reshaping heuristic values are added to the logits before masking, logit clipping, and softmax operation.For the autoregressive NCO models with a heavy encoder and a light decoder, the last decoder layer computes logits using [36] Here, u (c)j is the compatibility between current context and node j, C a constant for logit clipping, q (c) the query embedding of the current context, kj the key embedding of node j, and dk the query/key For each node j already visited, i.e. j = π t ′ , ∃t ′ < t, u (c)j is masked.EQUATIONWe reshape the attention scores by usingEQUATIONh (c)j is computed via attention-reshaping heuristics. In practice, for TSP and CVRP, h (c)j = Hc,j, where H is the heuristic matrix and c is simplified to the current node.For the autoregressive NCO models with a light encoder and a heavy decoder [51] , or only a decoder [14] , the last decoder layer computes logits using:EQUATIONwhere Wo is a learnable matrix at the output layer and node i is among the available nodes. We reshape the logits withEQUATIONwhere node c is the current node.For evaluations in Table 3 , we generalize the models trained on TSP100 and CVRP100 to larger instances with 200, 500, and 1000 nodes. For TSP, we apply the same ReEvo-generated heuristic across all sizes, whereas for the CVRP, we use distinct heuristics for each size due to the observed variations in desirable heuristics.Definition. The Traveling Salesman Problem (TSP) is a classic optimization challenge that seeks the shortest possible route for a salesman to visit each city in a list exactly once and return to the origin city.Instance generation. Nodes are sampled uniformly from [0, 1] 2 unit for the synthetic datasets.Definition. The Capacitated Vehicle Routing Problem (CVRP) extends the TSP by adding constraints on vehicle capacity. Each vehicle can carry a limited load, and the objective is to minimize the total distance traveled while delivering goods to various locations.Instance generation. For § 5.2, We follow DeepACO [94] . Customer locations are sampled uniformly in the unit square; customer demands are sampled from the discrete set {1, 2, . . . , 9}; the capacity of each vehicle is set to 50; the depot is located at the center of the unit square. For § 5.5, we use the test instances provided by LEHD [51] .Definition. In the Orienteering Problem (OP), the goal is to maximize the total score collected by visiting nodes while subject to a maximum tour length constraint.Instance generation. The generation of synthetic datasets aligns with DeepACO [94] . We uniformly sample the nodes, including the depot node, from the unit [0, 1] 2 . We use a challenging prize distribution [36] :pi = (1 + 99 • d 0i max n j=1 d 0j )/100, where d0i is the distance between the depot and node i. The maximum length constraint is also designed to be challenging. As suggested by Kool et al. [36] , we set it to 3, 4, 5, 8, and 12 for OP50, OP100, OP200, OP500, and OP1000, respectively.Definition. The Multiple Knapsack Problem (MKP) involves distributing a set of items, each with a given weight and value, among multiple knapsacks to maximize the total value without exceeding the capacity of any knapsack.Instance generation. Instance generation follows DeepACO [94] . The values and weights are uniformly sampled from [0, 1]. To make all instances well-stated, we uniformly sample ci from (max j wij, j wij).Definition. The Bin Packing Problem requires packing objects of different into a finite number of bins or containers of a fixed volume in a way that minimizes the number of bins used. It is widely applicable in manufacturing, shipping, and storage optimization.Instance generation. Following Levine and Ducatelle [39] , we set the bin capacity to 150, and item sizes are uniformly sampled between 20 and 100.Definition. The Decap Placement Problem (DPP) is a critical hardware design optimization issue that involves finding the optimal placement of decoupling capacitors (decap) within a power distribution network (PDN) to enhance power integrity (PI) [65, 69, 16, 63] . Decoupling capacitors are hardware components that help reduce power noise and ensure a stable supply of power to the operating integrated circuits within hardware devices such as CPUs, GPUs, and AI accelerators [65] . The DPP is formulated as a black-box contextual optimization problem, where the goal is to determine the best positions for a set of decaps to maximize the PI objective. This objective is contextualized by the target hardware's feature vectors, with the constraint of a limited number of decaps. Interested readers can refer to [31] for more details.Instance generation. 10 × 10 PDN instances are used. We generate training and validation instances following Kim et al. [31] . The test instances are directly drawn from [31] .This section presents the best heuristics generated by ReEvo for all problem settings. def heuristics(distance_matrix: torch.Tensor) -> torch.Tensor: n = distance_matrix.size(0) # Calculate the average distance for each node with symmetrical adjustments avg_distances = (torch.sum(distance_matrix, dim=1, keepdim=True) + torch.sum(distance_matrix, dim=0, keepdim=True) -2 * torch.diag(distance_matrix).unsqueeze(1)) / (2 * (n -1)) # Calculate heuristics based on the difference between each distance and the average distances with emphasis on nodecentric averages heuristics = 2 * (distance_matrix -avg_distances) + 0.5 * (distance_matrix -torch.mean(distance_matrix, dim=1, keepdim =True)) # Normalize the heuristics to have a mean of 0 and standard deviation of 1 heuristics = (heuristics -torch.mean(heuristics)) / torch.std(heuristics) return heuristics Heuristic 2: The best ReEvo-generated heuristic for TSP_NCO_LEHD. Heuristic 12 gives the best-ReEvo generated constructive heuristic for TSP. We used the best heuristic found in AEL [46] as the seed for ReEvo. As a result, our heuristic closely mirrors the one in AEL, scoring each node mostly using a weighted combination of the four factors. MIT License Evaluation GNNGLS [24] MIT License Evaluation EoH [47] MIT License Evaluation DeepACO [94] MIT License Evaluation DevFormer [31] Apache-2.0 license Evaluation POMO [37] MIT License Evaluation LEHD [51] MIT License Evaluation Dataset TSPLIB [67] Available for any non-commercial use Testing DPP PDNs [63] Apache-2.0 license Testing• The proofs can either appear in paper or the material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on access and including how to the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 


Decision: The paper presents a novel and general framework that uses LLMs to evolve hyper-heuristics. The framework is built primarily from existing LLM-based components, but coheres well and achieves its goal of an approach that feels like what it's like to design heuristics as a human, leading to interpretable insights in specific results, and allowing the reader to reflect on their own scientific/engineering process through this exercise in formalizing it. The method should be inspiring for many long-term evolutionary improvement approaches.

The main remaining concern about the paper is its similarity to a very recent work EoH, which also frames itself in the lineage of hyper-heuristics. The present work is sufficiently novel to merit its own publication, and the empirical results show strong benefits compared with EoH. However, I suggest the authors clearly state that EoH was developed _concurrently_ to this work, and enumerate the exact differences. To further clarify the paper's place in the literature, it would also be helpful to reference the earliest work using LLMs for mutations [1] and crossover [2] of code. 

Beyond incorporating the changes agreed upon in the discussion with reviewers, I would also encourage a longer dedicated limitations section; since the method appears so general, it would be helpful to clearly identify scenarios where it is not expected to be a good choice.

[1] Lehman et al. "Evolution through Large Models" arXiv:2206.08896 (2023, Handbook of Evolutionary Machine Learning)
[2] Meyerson et al. "Language Model Crossover: Variation through Few-Shot Prompting" arXiv:2302.12170

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: questions: Please address my weaknesses above.
limitations: limitations: Yes, in Section 7 (Conclusion).
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: The paper discuss some limitations, but the method may be limited by cost of LLM inference and problem scale.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: I would appreciate the authors' response on my main concerns listed above.
limitations: limitations: I have no concerns regarding the impact of the manuscript.

Comments: title: Thanks for reviewing
Thanks for reviewing
Request for Feedback
Request for Feedback
Thanks for reviewing
Request for Feedback
Further clarifications
Thank you for reviewing
A different writing strategy may have been better.
comment: 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.
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.
Thank you again for reviewing and for your constructive feedback.
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.
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.
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 again for reviewing and for your constructive feedback.
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.
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!
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
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?
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.
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.