EPOCH: Reshaping LLM Heuristic Design with Coverage-Aware Evolution and Preference Optimization

Title

EPOCH: Reshaping LLM Heuristic Design with Coverage-Aware Evolution and Preference Optimization

Meta Description

EPOCH treats instance coverage as an evolutionary objective for LLM-based automatic heuristic design (AHD) and uses experiential preference optimization to inject reflective signals into the generator's weights, outperforming inference-only and fine-tuning baselines across multiple combinatorial optimization problems and open-source LLM backbones.

Article Content

Combinatorial optimization problems (COPs) have long been a tough nut to crack in operations research and computer science. From path planning to resource scheduling, heuristics are indispensable in practice, yet manually designing high-quality heuristics is both time-consuming and heavily dependent on expert experience. In recent years, using large language models to automatically generate and evolve heuristics (AHD) has emerged as a new path. However, existing frameworks share a fundamental limitation: they either freeze the generator or fine-tune the model with only a scalar fitness signal, ignoring the critical information of which problem instances each heuristic actually covers.

A new paper proposes the EPOCH framework, which attempts to fundamentally change this situation. It makes instance coverage a direct objective of the evolutionary search and uses experiential preference optimization to let the generator internalize reflective signals. In short, EPOCH is not satisfied with "finding one good heuristic" but aims to "find a set of complementary heuristics."

The Blind Spot of Existing Methods: Fitness Signals Lose Coverage Information

LLM-based automatic heuristic design typically employs evolutionary search: the LLM generates candidate heuristics, evaluates them on training instances, then selects and mutates based on fitness, repeating the cycle. The problem is that scalar fitness is just an aggregate number—it tells you how a heuristic performs on average, but masks which instances it succeeds on and which it fails on.

Another class of methods introduces a reflection mechanism: the LLM provides natural language feedback on generated heuristics and improves them accordingly. But such feedback remains at the prompt level and never truly enters the generator's weights. In other words, the model "knows" what is wrong with a heuristic but may not avoid it in the next generation.

These two blind spots compound, causing the search to easily fall into a single-mode heuristic with poor overall coverage of training instances.

Direct Preference Optimization (DPO) is a key technique in recent years for replacing traditional RLHF alignment methods. Traditional methods such as PPO require training a separate reward model and then using reinforcement learning to adjust the language model policy, which is complex and unstable. DPO bypasses the reward model and directly optimizes the language model on preference data pairs (such as "improved version is better than original version"), with a loss function equivalent to maximizing the preference probability under an implicit reward. Mathematically, DPO uses the log-probability difference between the policy model and a reference model as an implicit reward, enabling the model to increase the generation probability of better responses while staying close to the reference model. It trains stably and requires no sampling loop, but by nature it teaches the model to "judge which is better" rather than directly constraining the model to "generate that better one itself"—this is also the motivation for EPOCH introducing a reflective self-distillation term.

EPOCH's Core Idea: Let Coverage Drive Everything

EPOCH's key innovation is elevating instance coverage to the primary objective of evolutionary search. Specifically, it optimizes coverage simultaneously from three angles:

Parent selection no longer relies solely on fitness ranking but prioritizes individuals that can fill gaps in the existing heuristic coverage. Operator assignment dynamically adjusts mutation and crossover strategies based on the current population's coverage gaps. The stagnation recovery mechanism, when search falls into a local optimum, actively seeks new directions that can cover untouched instances.

The result is that the search process tends to return a complementary ensemble of heuristics rather than a single optimal solution. In combinatorial optimization, different instances often require different strategies, and a set of complementary heuristics jointly covering the training set performs far better than a single "best on average" heuristic.

Heuristic ensembles in combinatorial optimization are conceptually similar to ensemble learning in machine learning, but with a different goal. In problems such as path planning, bin packing, and scheduling, no single heuristic is optimal on all instances: nearest-neighbor strategies perform well on small-scale dense graphs, insertion heuristics are better suited to constraints with time windows, and local search operators depend on initial solution quality. Ensemble learning reduces variance by combining multiple weak learners; heuristic ensembles instead cover different instance distributions through complementary strategies, and their evaluation metrics include not only average performance but also the breadth of coverage of the problem space. EPOCH treats coverage as a selection pressure, which is equivalent to actively maintaining population diversity during evolution to prevent all individuals from converging to the same strategy—fundamentally different from traditional evolutionary algorithms that select purely by fitness ranking.

Experiential Preference Optimization: Let Reflection Truly Enter Model Weights

Another core contribution of EPOCH is Experiential Preference Optimization. It lets the generator learn from its own search history rather than relying solely on external fitness signals.

The specific mechanism has two steps. A teacher LLM provides natural language insights on generated heuristics—for example, pointing out that a heuristic performs poorly on a specific type of instance. The generator then regenerates an improved heuristic based on this insight. These two versions of the heuristic form a preference data pair: the improved version is better than the original.

These preference pairs are used for Direct Preference Optimization (DPO), teaching the generator to rank between the two. But DPO's limitation is that it only teaches the model "which is better" and does not guarantee the model can autonomously generate that better version. To address this, EPOCH introduces a Reflective Self-Distillation (RSD) term that explicitly increases the generator's likelihood of autonomously producing the improved version. As the search progresses over the long term, this capability continues to accumulate.

Reflective Self-Distillation (RSD) draws on the combination of knowledge distillation and self-training. Standard knowledge distillation has a student model imitate the teacher model's output distribution; self-distillation uses the model's own different versions or different reasoning paths as supervision signals. RSD adds a reflection step: the teacher LLM first provides a natural language diagnosis of the current heuristic, the generator produces an improved version accordingly, and then the improved version is used as the target distribution to explicitly increase the original generator's likelihood of producing that version under the given diagnosis condition. This term complements DPO—DPO adjusts the relative preference between two versions, while RSD directly raises the absolute probability of the "correct answer." Together, they enable the model not only to judge quality but also to gradually internalize the ability to "how to improve," which is the key mechanism by which reflective signals move from the prompt level into the weight level.

Experimental Performance and Generalization Ability

The paper validates EPOCH on multiple combinatorial optimization problems and various open-source LLM backbones. The heuristic ensembles generated by EPOCH outperform inference-only and fine-tuning baselines in performance and can generalize across problem scales. This means that a heuristic combination trained on smaller-scale instances remains effective on larger-scale instances, which is crucial for real-world deployment.

Why This Line of Work Is Worth Watching

EPOCH's value is not just in performance numbers. It raises a more fundamental question: when LLMs are used for search and optimization, what exactly should we optimize? Scalar fitness is a simplification that compresses multi-dimensional performance information into a single number. EPOCH chooses to preserve the structural information of coverage and carries it through the entire process of search and training.

For researchers and engineers interested in LLM applications in algorithm discovery, automated reasoning, and combinatorial optimization, EPOCH provides a paradigm worth borrowing: reflection should not stay in prompts but should be transformed into the model's intrinsic capability through preference optimization and self-distillation.

Of course, this line of work still awaits more independent verification. EPOCH's results across multiple backbone models and problems are encouraging, but questions such as the computational overhead of coverage objectives on larger-scale problems and the stability of teacher LLM insight quality still need answers from follow-up work.

One-line Summary

EPOCH treats instance coverage as an evolutionary search objective and uses experiential preference optimization to bring reflection into model weights, generating complementary heuristic ensembles.

Paragraph Summary

EPOCH is an LLM-based automatic heuristic design framework for combinatorial optimization problems. Addressing the limitations of existing methods that fine-tune generators with only scalar fitness, lose instance coverage information, and keep reflection at the prompt level, EPOCH elevates instance coverage to the primary objective of evolutionary search, optimizing coverage simultaneously in parent selection, operator assignment, and stagnation recovery, and tends to produce a complementary heuristic ensemble rather than a single optimal solution. It also proposes experiential preference optimization: a teacher LLM provides natural language insights, the generator produces an improved version accordingly, the two form a preference pair for DPO, and a reflective self-distillation term explicitly increases the ability to autonomously generate the improved version. Experiments show that EPOCH outperforms inference and fine-tuning baselines across multiple combinatorial optimization problems and open-source LLM backbones, and generalizes across problem scales.