PaperlayerView exact revision on arXiv

Source-linked AI summary

EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design

Oguzhan Gungordu, Ayse Tursucular, Siheng Xiong, Faramarz Fekri

arXiv:2610.17379v1cs.AIcs.CL

TL;DR

EPOCH addresses the loss of instance-level coverage information in scalar-fitness AHD and the failure of prompt-based reflection to reach the generator’s weights. It uses coverage-aware evolutionary search and teacher-guided preference training with reflective self-distillation. Across COPs and LLM backbones, its heuristic ensembles outperform AHD baselines and generalize across problem scales.

  • Problem

    Scalar fitness hides which instances each heuristic covers, while reflection-based feedback stays in prompts rather than reaching generator weights.

    Source: §1 · p. 1

  • Method

    EPOCH guides evolutionary search with per-instance optimality gaps and trains the generator on teacher-guided improvements through preference optimization and reflective self-distillation.

    Source: §3.6 · p. 5, §3.7 · p. 6, §5 · p. 8

  • Results

    Across six test sets, EPOCH attains the lowest average gap among open-backbone methods at top-1 and top-4; its top-4 average is 44–55% below CALM.

    Source: §1 · p. 2, §4.1 · p. 7, §5 · p. 9

  • Takeaways & Limitations

    EPOCH’s complementary expert-heuristic ensembles outperform AHD methods and generalize across problem scales.

    Source: §5 · p. 9

    EPOCH is evaluated within step-by-step construction; solver-driven frameworks such as ant colony optimization and guided local search remain unexplored.

    Source: Limitations · p. 9

Abstract

from arXiv · show

LLM-based automated heuristic design (AHD) discovers heuristics for combinatorial optimization problems (COPs), where an LLM generates candidates in an evolutionary search. Existing frameworks freeze the generator or fine-tune it on a scalar fitness signal hiding which instances each heuristic covers. Reflection-based frameworks improve heuristics with natural-language feedback, but it stays in the prompt and never reaches the generator's weights. We propose EPOCH, which makes instance coverage the objective of the evolutionary search and fine-tunes the generator to internalize reflection. Parent selection, operator allocation, and stagnation recovery all optimize how well the heuristics jointly cover the training instances, so the search returns a complementary heuristic ensemble. The generator learns from its own search by experiential preference optimization. A teacher LLM returns a natural-language insight on the generated heuristics, and the generator produces new heuristics with this insight. These improvements join the preference pairs for direct preference optimization (DPO). Since DPO only teaches the generator to rank these improvements, a reflective self-distillation (RSD) term makes it more likely to generate them on its own, and the gains accumulate over the long horizon of the search. Across COPs and open-source LLM backbones, EPOCH's heuristic ensembles outperform inference-only and fine-tuned baselines and generalize across problem scales.

1 Introduction

LLM-based automated heuristic design searches for heuristics for combinatorial optimization, but existing approaches either hide instance-level coverage or fail to train the generator with reflection. EPOCH makes coverage guide the evolutionary search and trains the generator on teacher-guided improvements.

1 Introduction

  • Scalar fitness hides which instances each heuristic wins, while reflection-based feedback stays in prompts and fine-tuned methods do not use reflection.The authors identify both as limitations of prior approaches.Source: §1 · p. 1
  • Across COPs and LLM backbones, EPOCH’s heuristic ensembles outperform inference-only and fine-tuned LLM-based AHD baselines and generalize across problem scales.The authors report these outcomes as part of EPOCH’s main contributions.Source: §1 · p. 2
  • EPOCH uses per-instance optimality gaps to guide parent selection, operator allocation, stagnation recovery, and selection of the deployed heuristic ensemble.This makes the evolutionary search optimize instance coverage rather than average fitness.Source: §1 · p. 2
  • Teacher-guided improvements form preference pairs, and reflective self-distillation internalizes them so gains accumulate over the search.The teacher acts as a critic rather than generating heuristics or training data.Source: §1 · p. 2

2 Preliminaries

The preliminaries define heuristics as executable programs evaluated on training instances, contrast scalar-fitness search with coverage-oriented search, and introduce the DPO update used by EPOCH.

2 Preliminaries

  • A heuristic is an executable program mapping an instance to a feasible solution, which a cost function scores.Performance is assessed on a training set of instances.Source: §2 · p. 2
  • Conventional AHD returns the single best-on-average heuristic, whereas EPOCH searches for a complementary set covering the training instances using full per-instance performance profiles.The conventional scalar fitness summarizes a heuristic’s performance across the training set.Source: §2 · p. 2
  • DPO trains a policy on preferred and dispreferred responses relative to a reference policy, widening their implicit-reward margin; EPOCH applies updates in periodic bursts.The evolving policy generates the preference data.Source: §2 · p. 2

3 Methodology

EPOCH combines a coverage-aware heuristic search with experiential preference optimization that fine-tunes the generator using gains from teacher-guided reflection. Its methodology coordinates portfolio coverage across search decisions and trains the policy to generate reflective improvements without hints.

3.1 Per-Instance Gap Vectors, Experts, and Coverage

  • The pool is represented by per-instance gaps, and its coverage gap averages each instance’s best gap; complementarity measures how differently heuristics perform across instances.Unlike a single heuristic’s average gap, the pool coverage gap can improve when any member becomes a better expert on any instance.Source: §3.1 · p. 3

3.2 Expert-Aware Parent Selection

  • Parent selection balances expert counts and average-gap rank for mutations, and pairs parents by complementarity or average-gap rank for crossover.Expert counts are computed within the reproduction population.Source: §3.2 · p. 3

3.3 Evolutionary Operators

  • Five operators refine, simplify, inject, or replace components, or cross parents to exploit shared strengths or combine complementary strengths.Refine targets a parent’s main weakness while preserving what works; complementary crossover combines strengths across instances.Source: §3.3 · pp. 3–4

3.4 Adaptive Operator Bandit

  • An adaptive bandit rewards operators partly for improving coverage, with coverage gain weighted 0.6, and allocates probabilities while keeping every operator eligible.The reward also accounts for improved average gap and valid children; a probability floor prevents any operator from being starved.Source: §3.4 · p. 4

3.5 Coverage Stagnation and Expert-Preserving Recovery

  • When coverage stagnates, recovery rebuilds a smaller pool from strong average-gap and expert heuristics, resets bandit estimates, and preserves discovered experts in an archive.Recovery follows 10 iterations without improvement or a 40-iteration cap after the last recovery.Source: §3.5 · p. 4

3.6 Teacher-Guided Reflective Rollout

  • Each iteration, a teacher critiques first-round heuristics and the policy generates a second round from the insight; the critique adapts to how many first-round responses are valid.With multiple valid heuristics, the teacher contrasts the best and worst; with one or none, it gives repair or diagnostic critique.Source: §3.6 · p. 5

3.7 Experiential Preference Optimization

  • Preference pairs include better and worse valid responses, invalid-versus-valid responses, and hinted winners over strictly worse unhinted heuristics, all conditioned on the unhinted prompt.The optimality gap certifies the ordering of cross-round pairs.Source: §3.7 · p. 5
  • Reflective self-distillation adds an absolute likelihood objective for reflective winners, complementing DPO’s relative ranking so the unhinted policy becomes more likely to generate them.The term is applied only to the reflective buffer, whose pairs contain valid heuristics improved with hints; the paper says these gains accumulate over the search.Source: §3.7 · pp. 5–6

4 Experiments

EPOCH is evaluated across TSP, OBP, and KP using single-heuristic and portfolio metrics, with separate main-results and component-ablation analyses. Its ensembles show larger gains than single heuristics, while ablations test coverage-aware search and reflective learning.

4 Experiments

  • EPOCH is evaluated on TSP, OBP, and KP, assessing top-1 saved heuristics and top-K portfolios, plus generalization from in-domain training sizes to out-of-distribution sizes, with K ∈ {1, 3, 10} for TSP and {1, 4} for OBP.Llama-3.1-8B is fine-tuned online during the search with GPT-5-nano as teacher; every method uses 1,000 heuristic generations.Source: §4 · pp. 6–7

4.1 Main Results

  • Across six OBP test sets, EPOCH’s top-4 average gap is 44–55% below CALM, over 40% below the strongest open-backbone inference-only baseline, and 13–30% below the strongest GPT-4o-mini baseline.Source: Table 2 · p. 7, §4.1 · p. 7
  • At TSP n=50, EPOCH’s top-10 gap is 38–40% below CALM and 19–45% below the strongest inference-only baseline; gains persist OOD at n=200.Source: §4.1 · p. 7

4.2 Ablation Study

  • Replacing per-instance gap vectors with scalar averages widens ensemble gaps by 29% on TSP and 34% on OBP, the largest ablation degradation.The scalar removes per-instance structure used in selection, operator rewards, recovery, and ensemble choice.Source: §4.2 · p. 8
  • Removing expert-aware selection, the operator bandit, or its coverage reward widens ensemble gaps by 2–5% on TSP and 19–27% on OBP; simplified recovery degrades them by up to 5% and 19%, respectively.The ablations also report that preserving expert heuristics through recovery is essential.Source: §4.2 · p. 8
  • Removing RSD, teacher reflection, instance-grounded insight, or preference optimization widens gaps by 2–6% on TSP and 6–30% on OBP.Reflective cross-round pairs are a minority of the buffer; RSD raises unhinted-policy likelihood of reflective winners during training.Source: §4.2 · p. 8, Figure 2 · p. 8, Figure 3 · p. 8

5 Conclusion

EPOCH makes per-instance coverage guide the evolutionary search and fine-tunes its generator using teacher-guided reflection. Its complementary expert-heuristic ensembles outperform AHD methods and generalize across problem scales.

5 Conclusion

  • EPOCH represents each heuristic with a per-instance optimality-gap vector rather than scalar fitness, making the evolutionary search coverage-aware.The coverage signal guides expert-aware parent selection, an adaptive operator bandit, and coverage-based stagnation recovery.Source: §5 · p. 8
  • Teacher-guided reflection becomes a training signal, while reflective self-distillation internalizes improvements in the generator.The improvements accumulate across the search’s long horizon.Source: §5 · p. 9
  • Across COPs and LLM backbones, EPOCH’s complementary expert-heuristic ensembles outperform AHD methods and generalize across problem scales.Source: §5 · p. 9

Limitations

EPOCH fine-tunes the generator but keeps the teacher LLM fixed, and its evaluation is limited to the step-by-step construction framework.

Limitations

  • EPOCH fine-tunes only the generator; the teacher LLM that supplies natural-language insights remains fixed throughout the search.Source: Limitations · p. 9
  • Jointly fine-tuning the reflection process with the generator, toward an end-to-end system, is left for future work.Source: Limitations · p. 9
  • Evaluation uses the step-by-step construction framework; solver-driven approaches such as ant colony optimization and guided local search remain unexplored.Source: Limitations · p. 9

A Extended Related Work

Prior work automates heuristic construction, uses LLMs in evolutionary search, and explores reflection and generator training, but these lines leave distinct gaps that EPOCH addresses. EPOCH combines per-instance coverage control with preference learning from executable outcomes and reflection-guided improvements.

Heuristic design and hyper-heuristics

  • Classical genetic programming evolves heuristic programs from human-defined function sets, while free-form LLM code generation expands the expressible search space.Hyper-heuristics and automated heuristic design automate heuristic selection or construction for a problem class.Source: A Extended Related Work · p. 11

LLMs in evolutionary search

LLM-based AHD frameworks

Training the LLM generator for AHD

  • CALM and EvoTune fine-tune generators using scalar rewards or program-database preferences, whereas EPOCH uses per-instance gaps to govern search and reflection-based preference pairs (Huang et al., 2026; Šurina et al., 2025).EPOCH also distills hint-guided improvements into the unhinted policy and deploys a complementary expert ensemble.Source: A Extended Related Work · p. 11

Reflection and natural-language feedback

Preference optimization and learning from feedback

  • EPOCH uses DPO preference pairs certified by executed-code optimality gaps, contrasting hinted second-batch responses with strictly worse unhinted first-batch responses from the same iteration.Its RSD term distills hint-conditioned behavior into the unconditioned policy and is gated to pairs whose verifiable reward confirms a reflective gain.Source: A Extended Related Work · p. 12

B Problem Definitions and Datasets

The section defines three COP settings and their datasets, explains the construction-framework evaluation boundary, and specifies how ensembles and search subalgorithms operate. Evaluation compares each method’s returned set as well as its best individual heuristic.

B Problem Definitions and Datasets

  • The construction framework isolates the heuristic’s contribution because the heuristic alone builds the solution; solver-driven frameworks are deferred because the solver also narrows differences between heuristics and evaluations are costlier.Each candidate would require running the solver on every training instance, slowing the 1,000-generation search.Source: B Problem Definitions and Datasets · p. 12
  • TSP heuristics choose the next city in a Euclidean tour, OBP heuristics rank feasible bins for sequential Weibull-sized items, and KP heuristics select items under a capacity constraint.The problems are instantiated within a step-by-step construction framework, where the heuristic constructs the solution.Source: B Problem Definitions and Datasets · p. 12
  • TSP, OBP, and KP use distinct gap references and training/test sizes, with held-out scales designated ID or OOD as summarized in Table 4.TSP gaps use LKH-3 tour lengths, OBP uses the L1 lower bound on bin count, and KP uses the dynamic-programming optimum; reported results average five independent runs.Source: B Problem Definitions and Datasets · pp. 12–13, Table 4 · p. 13
  • Top-1 evaluates the best-training-fitness heuristic, while top-K routes each test instance to the lowest-cost member of the method’s returned set; EPOCH’s set is coverage-ranked.The top-K comparison with EoH-S uses each method’s own coverage-ranked set, and EPOCH always includes its training-fitness-best heuristic.Source: B Problem Definitions and Datasets · p. 13

C Algorithm Pseudocodes

  • The pseudocode covers expert-aware parent selection, an operator bandit, expert-preserving recovery, and construction of preference pairs from valid, invalid, and reflection-guided generations.Parent selection balances recruiting heuristics for under-covered instances with refining strong candidates; recovery rebuilds the pool when coverage stagnates.Source: C Algorithm Pseudocodes · p. 14
  • The operator bandit updates quality from expert-coverage gain, parent-beating and validity fractions, then resets quality estimates on recovery.The draw step allocates operators using bounded weights centered on the mean quality of eligible operators.Source: C Algorithm Pseudocodes · p. 14

D Reflective Self-Distillation: Derivation and Margin Analysis

EPOCH’s reflective self-distillation addresses the gap between ranking a hinted improvement above another heuristic and generating that improvement from an unhinted prompt. Extended KP results show strong ensemble performance across sizes.

D Reflective Self-Distillation: Derivation and Margin Analysis

  • DPO widens a preference margin without requiring higher likelihood for the preferred heuristic, so ranking a reflective winner does not ensure the unhinted policy will generate it.The margin can widen by lowering the rejected candidate’s log-probability; reflective pairs are also a minority with relatively small margins.Source: D Reflective Self-Distillation:… · p. 15
  • RSD minimizes the hinted-to-unhinted policy divergence, pulling the unhinted policy toward improvements produced with the insight.The hinted policy biases sampling toward better heuristics; the divergence vanishes when the hint changes nothing.Source: D Reflective Self-Distillation:… · p. 15
  • RSD estimates that divergence using already-sampled, certified reflective winners and a stop-gradient, yielding a negative log-likelihood term under the unhinted prompt.The RSD term reuses the DPO scoring pass and adds essentially no compute.Source: D Reflective Self-Distillation:… · p. 16
  • Interleaving policy updates with unhinted rollouts lets internalized improvements seed later parents, preference pairs, and experts over the search run.The paper distinguishes this training-time accumulation from inference-time hint independence because deployment uses saved heuristic artifacts, not the policy.Source: D Reflective Self-Distillation:… · p. 16
  • RSD is restricted to valid reflective gains and uses length normalization and a small weight to limit concentration that could erode output diversity.A zero weight recovers plain DPO.Source: D Reflective Self-Distillation:… · p. 16

E.1 Extended Experiment Results

  • 26–47% and 55–59%: EPOCH’s top-10 KP ensemble cuts the gap versus MCTS-AHD and ReEvo, respectively, with gains persisting out of distribution.Its top-3 ensemble also outperforms ReEvo’s top-10 at every size, while top-1 is best or comparable at every size.Source: §E.1 · p. 16

E.2 Robustness to Seed Quality

From a weak TSP seed, EPOCH retains strong ensemble performance and converges faster and to lower costs than the LLM-based AHD baselines. Its top-10 ensemble also performs well on real-world TSPLIB instances.

E.2 Robustness to Seed Quality

  • 6.71% and 6.76%: EPOCH’s weak-seed top-10 TSP gaps at n=50 on Llama and Qwen remain close to standard-seed results, and it has the lowest gap at every size, metric, and backbone.Its weak-seed top-3 ensemble still beats CALM’s full top-10 throughout; CALM’s weak-seed gaps rise to 14.51% and 16.10%.Source: §E.2 · p. 17, Table 8 · p. 20

E.3 Search Dynamics & Evolutionary Curves

  • EPOCH converges faster and to lower training costs than LLM-based AHD baselines on both backbones; its top-10 curve stays below every single-heuristic method across the budget.Figure 4 plots best-so-far cost against heuristic evaluations from the weak seed, averaged over at least five runs; the top-10 curve has low run-to-run deviation.Source: §E.3 · p. 17, Figure 4 · p. 20

E.4 Generalization to Real-World TSPLIB Instances

  • On TSPLIB’s 15 instances with fewer than 500 nodes, EPOCH has the lowest average optimality gap and the best result on most instances.The evaluation uses top-10 ensembles and compares against manual heuristics and a genetic-programming hyper-heuristic.Source: §E.4 · p. 21

F Significance Testing and Uncertainty Quantification

  • The significance analysis tests run-to-run variability and paired per-instance differences; every method is run at least five times.The passage describes the two evaluation axes but does not report their test outcomes.Source: F Significance Testing and Uncertainty… · p. 21

F.1 Statistical Significance Across Runs

Across-instance tests find EPOCH’s ensemble gains are not concentrated in a few easy cases, while across-run tests show significantly lower mean gaps in nearly all settings. Hyperparameter results favor moderate coverage pressure and periodic preference updates.

F.1 Statistical Significance Across Runs

  • EPOCH’s deployed ensemble has significantly lower mean gap than baselines in nearly all settings under across-run tests.The analysis uses a one-sided Welch t-test on run-level mean gaps; OBP gaps are averaged over six Weibull sets.Source: §F.1 · p. 21

F.2 Cross-Instance Uncertainty Quantification

  • EPOCH wins the large majority of TSP instances and several times more KP instances than it loses at every size; paired tests are significant throughout.Most KP ties occur where both ensembles solve instances optimally.Source: §F.2 · p. 21

G Extended Ablations

  • Component ablations replace one component at a time with a simpler untuned alternative while holding other components and hyperparameters fixed.The study uses Llama-3.1-8B on TSP and OBP, the full training budget, and five runs per variant.Source: G Extended Ablations · p. 21

G.1 Hyperparameter Ablation

  • The default RSD weight λ=0.1 is best or tied on both problems, and distilling certified cross-round winners outperforms distilling all pairs.Small λ values work across a broad range.Source: §G.1 · pp. 21–22

G.2 Teacher LLM Ablation

Across three teacher choices, EPOCH’s ensemble results remain ahead of baselines, including when its own frozen backbone supplies critiques. The teacher critiques candidates rather than generating heuristics.

G.2 Teacher LLM Ablation

  • The teacher reads two heuristics and their gaps, then explains their difference; the study also tests GPT-4o-mini and the generator’s own frozen backbone as teachers.GPT-5-nano is a reasoning model from a different family than the generator.Source: §G.2 · p. 22
  • Across three teachers, top-10 TSP gaps vary by less than 0.4 points and top-4 OBP averages by less than 0.2, while ensemble results remain ahead of same-backbone baselines.With its own backbone as teacher, EPOCH uses no external model and retains substantial top-10 TSP and top-4 OBP margins over CALM and EoH-S.Source: §G.2 · pp. 22–23
  • With GPT-4o-mini as teacher, EPOCH’s top-10 TSP gap is 11–19% below EoH-S and its top-4 OBP average is 20% below EoH-S, at 7–13× lower API cost per run.In this setting, GPT-4o-mini serves EPOCH only as a critic.Source: §G.2 · p. 23

H Implementation Details and Hyperparameters

EPOCH uses two instruction-tuned backbones, a fixed generation budget, and periodic preference-optimization bursts. Its prompts structure heuristic generation around parent algorithms and append teacher insights in Round 2.

H Implementation Details and Hyperparameters

  • Runs use Qwen2.5-7B-Instruct or Llama-3.1-8B-Instruct in 4-bit with LoRA rank 32, over 125 iterations and 1,000 heuristic generations.Each iteration has 4+4 generations across two rounds; a DPO burst runs every 20 iterations with β=0.1 and learning rate 5 × 10−6, while RSD uses λ=0.1.Source: H Implementation Details and… · pp. 23–24
  • All methods share the 1,000-generation budget; EPOCH’s phase rollouts run independently in parallel, unlike MCTS-AHD’s sequential tree expansion.Runs used two NVIDIA RTX 6000 Ada GPUs (48 GB each).Source: H Implementation Details and… · p. 24
  • EPOCH’s teacher calls cost $0.08 per run with GPT-5-nano and at most $0.05 with GPT-4o-mini; inference-only closed-model runs cost 4–8× or 14–29× as much, respectively.The only EPOCH API calls are teacher calls; the comparison is against inference-only runs using GPT-4o-mini or GPT-5-nano.Source: H Implementation Details and… · pp. 24, 26

I Prompt Templates

  • Operator prompts combine a problem-agnostic format, a per-problem function specification, one operator instruction, and parent heuristics; Round 2 appends the teacher’s insight.The shared output format requires a conceptual description followed by one deterministic Python function that conforms to the given signature.Source: I Prompt Templates · p. 26
  • The teacher is prompted to return standalone, generalizable hints for the next attempt, not an algorithm; contrastive critique can include how two heuristics split training instances.Hints are shown without the candidates, so references must be self-contained advice.Source: I Prompt Templates · p. 28

Related papers

Loading 2610.17379v1…