Research map / Large language models / Agents, code and math
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Language Hyper-Heuristics (LHHs) and Reflective Evolution (ReEvo), an evolutionary search over LLM-generated heuristic code with LLM short- and long-term verbal reflections, applied to six combinatorial optimization problems.
Problem
Automating heuristic design for NP-hard combinatorial optimization problems (COPs) with LLMs, where prior LLM-based heuristic search is sample-inefficient and weak at inferring structure of black-box problems.
Approach
Couples genetic-programming-style evolution of heuristic code with LLM reflections: a reflector LLM compares pairs of heuristics (short-term) and accumulates insights across iterations (long-term) to act as verbal gradients guiding crossover and elitist mutation.
Key results
- On TSP1000 attention reshaping, POMO optimality gap improves from 52.11% to 29.08% with ReEvo versus 44.05% with expert DAR.
- KGLS-ReEvo reaches 0.000% gap on TSP20/50/100 and 0.216% on TSP200 versus 0.284% for KGLS.
- ReEvo achieves lower objective than EoH in sample efficiency comparisons on black-box ACO problems, with white-box ablation reaching 8.40 versus 8.64 for vanilla LLM sampling.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the KGLS penalty heuristic with a ReEvo-generated penalty heuristic | KGLS · TSP20–TSP200 | optimality gap (%): 0.004 -> 0.000 (TSP20); 0.017 -> 0.000 (TSP50); 0.002 -> 0.000 (TSP100); 0.284 -> 0.216 (TSP200) | Helped |
| Generate a constructive TSP heuristic with ReEvo instead of GHPP | TSP constructive heuristic · TSP TSPLIB instances (average) | average optimality gap: 16.7 -> 14.6 | Helped |
| Use ReEvo-generated attention reshaping instead of no reshaping | POMO · TSP1000 | optimality gap (%): 52.11 -> 29.08 | Helped |
| Use ReEvo-generated attention reshaping instead of expert-designed DAR | POMO · TSP1000 | optimality gap (%): 44.05 -> 29.08 | Helped |
| Use ReEvo-generated attention reshaping instead of no reshaping | LEHD · TSP1000 | optimality gap (%): 3.17 -> 2.97 | Helped |
| Use ReEvo-generated attention reshaping instead of expert-designed DAR | POMO · CVRP1000 | optimality gap (%): 286.37 -> 218.22 | Helped |
| Use ReEvo-generated attention reshaping instead of expert-designed DAR | LEHD · CVRP1000 | optimality gap (%): 6.35 -> 4.76 | Helped |
| Add short-term reflection | ReEvo ACO heuristic search · TSP50 ACO random walk | objective: 12.08 ± 7.15 -> 6.53 ± 0.60 | Helped |
| Remove long-term reflections (ablation) | ReEvo · TSP100 white-box prompting | objective: 8.40 ± 0.02 -> 8.61 ± 0.21 | Hurt |
| Remove long-term reflections (ablation) | ReEvo · TSP100 black-box prompting | objective: 8.96 ± 0.82 -> 9.32 ± 0.71 | Hurt |
| Remove short-term reflections (ablation) | ReEvo · TSP100 white-box prompting | objective: 8.40 ± 0.02 -> 8.46 ± 0.01 | Hurt |
| Remove short-term reflections (ablation) | ReEvo · TSP100 black-box prompting | objective: 8.96 ± 0.82 -> 9.05 ± 0.83 | Hurt |
Surprising findings
- Reflections reduce the ruggedness of the heuristic fitness landscape, with correlation length rising from 0.28 to 1.28 when reflection is used.
- Open-source LLMs are reported as not capable enough to guarantee statistically significant gains from reflection.
Limitations
- Experiments limited to 100 heuristic evaluations, so results may not scale to larger budgets where reflection's benefit may be obscured.
- Open-source LLMs were judged insufficiently capable for reliable reflection gains.
- Heuristic evaluation costs in the EDA case exceed 20 minutes per evaluation, making the approach costly in some settings.
Experimental setup
Datasets: TSPLIB problem instances for TSP, CVRP, OP, MKP, BPP, DPP
Benchmarks: TSP20-200 GLS ACO on TSP/CVRP/OP/MKP/BPP DPP genetic algorithm TSPLIB constructive TSP POMO/LEHD attention reshaping on TSP and CVRP
Metrics: optimality gap (%) objective value execution time correlation length sample efficiency
Baselines: EoH KGLS GNNGLS NeuralGLS NeuOpt DeepACO GHPP DevFormer POMO + DAR LEHD
Builds on: EoH FunSearch KGLS DeepACO Reflexion
Closest papers by meaning
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.92)
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.90)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.88)
- OptMATH: A Scalable Bidirectional Data Synthesis Framework for Optimization Modeling (ICML 2025 · similarity 0.88)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
- Revolve: Optimizing AI Systems by Tracking Response Evolution in Textual Optimization (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.