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

2024 · Paper

---

1. Motivation

Combinatorial optimization problems (COPs) such as routing and packing rely on hand-crafted heuristics that take experts months to design, while neural combinatorial solvers need expensive per-size training and generalize poorly.¹ FunSearch and EoH showed that LLMs can evolve heuristic code, but they treat the LLM as a blind mutation operator: failed or inferior candidates generate no transferable insight, so search is sample-hungry.¹ ReEvo’s premise is that Reflexion-style verbal feedback can be lifted from single agents into evolutionary search - the population should not just keep its best code but also keep a running, natural-language theory of why some code is better.¹²

---

2. Methodology

2.1 Search Structure

ReEvo introduces Language Hyper-Heuristics (LHHs): hyper-heuristics whose heuristic space is open-ended LLM-generated code with no predefined primitive set. Search is genetic programming over that space. Each iteration runs five sequential steps:¹

1. Selection        : pick a parent pair (random among valid heuristics)
2. Short-term refl. : reflector LLM compares the two parents
3. Crossover        : generator LLM produces offspring from parents + reflection
4. Long-term refl.  : reflector LLM updates persistent expertise text
5. Elitist mutation : generator LLM mutates the current best, guided by long-term text

The meta-objective $F(h)$ is the average performance of heuristic $h$ over a dataset of problem instances; all offspring are evaluated after both crossover and mutation. Two LLM roles are fixed: a generator (makes code) and a reflector (makes verbal guidance).¹

2.2 State Representation

An individual is a code snippet with a fixed function signature but otherwise unconstrained (“individuals are not constrained by any predefined encoding format”).¹ Population state additionally carries the long-term reflection text - a persistent natural-language summary of design expertise accumulated across generations, compact enough “to be loaded into the inference context without causing memory blowups.”¹

2.3 Generation Mechanism

(i) Initialization from a task specification (COP description, heuristic functionality; optional seed heuristics as in-context examples). (ii) Crossover: the generator receives task spec + parent pair + an explicit relative-performance indication + the short-term reflection, and produces offspring. (iii) Elitist mutation: the generator samples multiple mutants of the current best heuristic conditioned on long-term reflections.¹ Unlike blind mutation, every variation step is conditioned on a verbal analysis of what differs between a better and a worse parent - the “verbal gradient” analogue of $\nabla F$ in heuristic space.¹

2.4 Evaluation & Grounding

Evaluation is fully execution-grounded: each candidate runs on problem-instance datasets and $F(h)$ is measured, never judged by an LLM. Two prompting regimes are defined:¹

• White-box: the COP identity is revealed (e.g., “traveling salesman problem”).
• Black-box: generic variable names (e.g., edge_attr instead of distance_matrix) hide the problem class, guarding against the LLM “merely retrieving code tailored for prominent COPs from their parameterized knowledge” - an explicit anti-recitation protocol.¹

Six COPs are covered (TSP, CVRP, OP, MKP, BPP, DPP) across five algorithmic targets: guided local search (GLS) penalties, ant colony optimization (ACO) heuristic measures, constructive heuristics, genetic-algorithm crossover/mutation operators, and attention reshaping for neural solvers.¹

2.5 Memory / Information Flow

Two memory tiers, explicitly framed as agent architecture. Short-term reflection = the reflector’s comparative analysis of one parent pair (“why is A better than B; what to keep/change”) - consumed once, by crossover, like per-round environmental feedback. Long-term reflection = the reflector summarizes the previous long-term text plus new short-term reflections into persistent expertise - consumed by elitist mutation and carried across generations.¹ Reflection text thus propagates even when code does not: a linguistic analogue of inheritance in which design knowledge, not just genomes, is heritable.

2.6 Selection & Propagation

Parent pairs are sampled at random among successfully executed heuristics, excluding pairs with identical $F$. Mutation is strictly elitist - only the best individual is mutated - making ReEvo an exploitation-leaning design at the optimization pole, in contrast to archive-based exploration (MAP-Elites³, AlphaEvolve’s database).¹⁴

2.7 Anti-Slop / Anti-Hallucination Mechanisms

Four structural controls: (i) black-box prompting blocks memorized-solution recitation; (ii) invalid heuristics are skipped, not scored; (iii) evaluation is capped at 100 heuristic executions so sample-efficiency claims stay honest; (iv) a fitness-landscape autocorrelation analysis verifies rather than asserts the benefit of reflection: correlation length 1.28 ± 0.62 with reflection vs 0.28 ± 0.07 without, and objective 6.53 ± 0.60 vs 12.08 ± 7.15 (TSP50 ACO random walk) - reflection smooths the search landscape measurably.¹

---

3. Results

• GLS penalties (Table 1): KGLS-ReEvo reaches 0.000% optimality gap on TSP20/50/100/200 with a single heuristic, versus KGLS (0.004/0.017/-/0.284), neural baselines (NeuOpt up to 0.403, GNNGLS up to 3.522), and EoH (up to 0.563); neural combinatorial baselines additionally need per-size training.¹
• ACO heuristics: ReEvo beats expert-designed ACO heuristics and DeepACO across five COPs “even when the latter overfits the test problem size.”¹
• Ablation (Table 5, TSP100 ACO, objective ↓): full ReEvo 8.40 ± 0.02 (white-box) / 8.96 ± 0.82 (black-box); removing long-term reflection → 8.61/9.32; short-term → 8.46/9.05; crossover → 8.45/9.47; mutation → 8.83/9.34; random LLM sampling → 8.64/9.74. Every component contributes.¹
• Sample efficiency: ReEvo outperforms EoH (itself more efficient than FunSearch) across TSP/CVRP/OP/MKP/BPP under black-box prompting with GPT-3.5-Turbo, GPT-4-Turbo, and Llama-3-70B backbones; cost is ~$0.0003 per LLM call (GPT-3.5-Turbo) and ~5 minutes per strong heuristic.¹

---

4. Limitations & Assumptions

The authors cap heuristic evaluations at 100 shots and warn results “do not necessarily scale up… Allowing a large number of heuristic evaluations could obscure the impact of reflection.”¹ Reflection quality depends on capable LLMs: “many open-source LLMs are not capable enough to guarantee statistically significant improvement of reflections.”¹ Rule-based heuristics may underfit relative to neural-parameterized policies in complex environments, and the paper’s benchmarking position (count heuristic evaluations, not LLM queries) is a stance, not a consensus.¹

---

5. Critical Analysis

• Distinctive strength: ReEvo is the cleanest fusion of verbal reflection with population search, and unusually it proves the reflection mechanism works via landscape autocorrelation and a full factorial-style ablation rather than anecdote; the black-box protocol is a transferable anti-recitation standard.¹
• Structural weakness / trade-off: elitist mutation around a single best individual plus a single global long-term text concentrates search; there is no diversity-preserving archive, so on deceptive landscapes it can stall where island or MAP-Elites-style designs keep exploring.¹⁴
• Connections: ReEvo explicitly extends Reflexion “from binary rewards to comparative analysis of two heuristics, analogous to verbal gradient information,” embedded in evolution.¹² It positions itself against FunSearch/EoH on sample efficiency, and AlphaEvolve can be read as the same program-evolution idea scaled up with a MAP-Elites-inspired database while dropping explicit verbal reflection - a direct contrast on the reflection-versus-artifact-memory axis.⁴⁵ MLE agents such as ML-Master and MARS reuse ReEvo’s template of evolving code artifacts with verbal critique as gradient.

---

6. References

Footnotes

1. Ye et al., ReEvo, NeurIPS 2024 (PDF v3): https://arxiv.org/pdf/2402.01145.pdf · code: https://github.com/henry-yeh/ReEvo ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³ ↩¹⁴ ↩¹⁵ ↩¹⁶ ↩¹⁷ ↩¹⁸ ↩¹⁹ ↩²⁰ ↩²¹ ↩²² ↩²³ ↩²⁴ ↩²⁵

2. Shinn et al., Reflexion, NeurIPS 2023: https://arxiv.org/abs/2303.11366 ↩ ↩²

3. Mouret & Clune, MAP-Elites: https://arxiv.org/abs/1504.04909 ↩

4. Novikov et al., AlphaEvolve: https://arxiv.org/abs/2506.13131 ↩ ↩² ↩³

5. Romera-Paredes et al., FunSearch, Nature 625:468–475: https://www.nature.com/articles/s41586-023-06924-6 ↩