ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

Cuong Van Duc; Minh Nguyen Dinh Tuan; Tam Vu Duc; Tung Vu Duy; Son Nguyen Van; Hanh Nguyen Thi; Binh Huynh Thi Thanh

cs.AIMar 5, 2026

ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

Authors: Cuong Van Duc, Minh Nguyen Dinh Tuan, Tam Vu Duc, Tung Vu Duy, Son Nguyen Van, Hanh Nguyen Thi, Binh Huynh Thi Thanh

Organizations: VinMotion · Hanoi University of Science and Technology · VinUniversity · Phenikaa School of Computing, Phenikaa University ·

Abstract

Designing effective heuristics for NP-hard combinatorial optimization problems remains challenging and often requires substantial domain expertise. Recent LLM-guided evolutionary methods have shown promise for automated heuristic generation, but most existing approaches refine heuristics independently or through limited pairwise feedback. We propose ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback, a framework for group-wise multi-turn heuristic refinement. ReVEL organizes heuristics into behavior-aware reflective groups, including similarity-driven groups for localized refinement and diversity-driven groups for exploratory search. Within each group, the LLM performs iterative multi-turn refinement using accumulated performance feedback, enabling related heuristics to be jointly analyzed and progressively improved across evolutionary iterations. Experiments on standard combinatorial optimization benchmarks show that ReVEL generally improves optimization performance over existing LLM-guided evolutionary baselines across multiple settings and LLM backbones. Additional analyses suggest that behavior-aware grouping contributes to more consistent refinement trajectories during iterative heuristic evolution.

Figures & tables

Figure 1: The proposed REVEL framework addresses combinatorial optimization problems across diverse domains and problem scales through strategic multi-turn heuristic evolution. Starting from initial candidate search strategies, REVEL organizes heuristic populations into collaborative refinement groups that iteratively perform evaluation, strategic rewriting, and evolutionary adaptation. Through repeated multi-turn interactions, the framework progressively explores and refines increasingly effective search behaviors, enabling the automatic discovery of high-performing heuristics for complex combinatorial optimization problems.

Figure 2: ReVEL : Multi-turn reflective evolutionary optimization through structured population feedback. Starting from an initial heuristic population, ReVEL iteratively organizes heuristics into behaviorally coherent groups, performs reflective refinement over accumulated population feedback, and evolves improved heuristics through population-level reasoning.

Reasoning Category	Description	Freq	Example
Structure rewrite	Completely changes the algorithm family.	16	Given that the highest-performing known approach is “Stabilized Harmonic-Arctanh” $\ldots$ I should explore this proven algorithmic family rather than tuning simpler approaches.
Heuristic modification	Same algorithm family and pipeline structure, but decision and scoring logic is substantially rewritten.	89	Given the significant performance gap and clear indication that Worst-Fit works better, we should focus on refining this approach $\ldots$
Parameter tuning	Only numeric changes (weights, thresholds, constants) with formulas and pipeline unchanged.	75	Given the regression, we should revert to the simpler version and make minimal adjustments to core parameters $\ldots$

Table 1: Analysis of Reasoning Categories, their frequency, and examples.

\mathcal{G}\leftarrow\textsc{Group}\!\left(\mathcal{H}^{(g-1)},s_{\mathrm{perf}},s_{\mathrm{code}}\right)

Algorithm 1 ReVEL : Structured Multi-Turn Reflective Evolution

Capacity	Size	First Fit	Best Fit	EoH	ReEvo	ReVEL (ours)
100	1k	5.32%	4.87%	3.03%	3.78%	2.34%
	5k	4.40%	4.08%	2.15%	0.80%	1.13%
	10k	4.44%	4.09%	0.33%	0.33%	0.59%
300	1k	1.34%	1.19%	0.60%	1.04%	0.30%
	5k	0.93%	0.84%	0.63%	0.27%	0.24%
	10k	0.92%	0.86%	0.58%	0.19%	0.16%

Table 2: Online bin packing results. Fraction of excess bins to lower bound (lower is better).

Heuristic	TSP10 (%)	TSP20 (%)	TSP50 (%)	TSP100 (%)	TSP200 (%)
EoH	3.52	9.33	10.24	11.39	15.58
ReEvo	4.22	6.74	11.63	11.01	15.58
ReVEL (ours)	2.11	6.74	9.20	12.64	11.46

Table 3: Traveling Salesman Problem (TSP) results. Optimality gaps (%) relative to OR-Tools solutions.

Heuristic	Model	Gap(%)
ReVEL	deepseek-v3-0324	1.13
ReVEL	kimi-k2-instruct	1.95
ReVEL	qwen3-coder-480b-35a	1.41
ReVEL	glm-4.5	1.20

Table 4: Online Bin Packing: Method Across Models

Setting	Gap (%)	$\Delta_{t}$		Cons. (%)
Setting	Gap (%)	Mean	Var.	Cons. (%)
Random Grouping	15.97	0.86	1.79	45
Without Grouping	17.60	0.72	1.48	40
Pair-wise Grouping	15.55	0.92	1.67	45
w/o LLM Refinement	11.80	1.26	2.05	55
Our Method	9.20	1.61	2.84	65

Table 5: Performance of Grouping Strategies

Figure 3: Distribution of refinement operation types across optimization iterations.

Setting	Gap (%)
Single-turn Refinement	17.18
Best-of- $N$ Sampling	16.68
Random Grouping	15.97
Without Grouping	17.60
ReVEL (Full)	9.20

Table 6: Ablation study on TSP50.

$\alpha$	Gap (%)
0.2	15.79
0.4	14.06
0.5	9.20
0.6	15.97
0.8	12.50

Table 7: Effect of similarity balancing coefficient

\alpha

on TSP50.

Method	API Cost
ReEvo	$0.25
EoH	$0.33
ReVEL (Ours)	$0.41

Table 8: Average API Consumption Costs per Run

Figure 4: Cost–performance trade-off across optimization iterations.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Number of Cities
TSP10	10
TSP20	20
TSP50	50
TSP100	100
TSP200	200

Appendix

Table 9: TSP problem sizes

Dataset	Number of Items ( $T$ )	Capacity ( $C$ )
BPP-1K-100	1K	100
BPP-1K-300	1K	300
BPP-1K-500	1K	500
BPP-5K-100	5K	100
BPP-5K-300	5K	300
BPP-5K-500	5K	500

Appendix

Table 10: Online Bin Packing problem sizes

Figure 5: Qualitative example of reflective reasoning in ReVEL: Observations guide the LLM to alternate between exploration, exploitation, and innovation, resulting in progressive improvement of heuristic quality.

Method	API Cost
ReEvo	$0.25
EoH	$0.33
ReVEL (Ours)	$0.41

Appendix

Table 11: Average API Consumption Costs per Run

Instance	Nearest Neighbour	EoH	Our
Berlin52	19.06	17.68	6.24
Bier127	15.27	8.04	9.33
Ch130	23.98	6.81	10.21
D493	17.20	14.85	15.69
Eil51	19.72	3.19	3.68
KroA100	26.19	11.06	6.21

Appendix

Table 12: Results on TSPLib instances. The gap (%) to the best-known solution from TSPLib.

Evolution Loop Parameters
Parameter Name	Value
max_turns	6
num_candidates_to_initialize	10
epochs	20
top_k	10
reminder_probability	0.3

Appendix

Table 13: Hyperparameters Configuration

Heuristic	CVRP20 (%)	CVRP50 (%)	CVRP100 (%)
ReEvo	13.70	19.44	18.06
ReVEL (ours)	4.57	17.68	14.88

Appendix

Table 14: Baseline OR-Tools Results for the Capacitated Vehicle Routing Problem.

Capacity	Size	ReVEL (%)	CV
$100$	$1$ k	$2.32\pm 0.08$	$0.0345$
	$5$ k	$1.15\pm 0.11$	$0.0957$
	$10$ k	$0.53\pm 0.16$	$0.3019$
$300$	$1$ k	$0.31\pm 0.02$	$0.0645$
	$5$ k	$0.25\pm 0.03$	$0.1200$
	$10$ k	$0.18\pm 0.06$	$0.3333$

Appendix

Table 15: Repeated-run robustness on Online Bin Packing over 10 independent runs. Results report mean optimality gap

\pm

standard deviation and coefficient of variation (CV). Lower is better.

Benchmark	ReVEL (%)	CV
TSP10	$2.33\pm 0.61$	$0.2618$
TSP20	$6.72\pm 0.12$	$0.0179$
TSP50	$9.80\pm 0.79$	$0.0806$
TSP100	$13.83\pm 1.96$	$0.1417$
TSP200	$12.54\pm 2.03$	$0.1619$

Appendix

Table 16: Repeated-run robustness on the Traveling Salesman Problem over 10 independent runs. Results report mean optimality gap

\pm

standard deviation and coefficient of variation (CV). Lower is better.

Automated Heuristic Design

Automated heuristic design creates or adapts problem-solving rules for optimization, planning, scheduling, and related search tasks.

See all 84 papers

RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience
Jul 13, 2026Yang Wu, Junran Pan, Yifan Zhang +3Automated Heuristic Design Evolutionary Optimization
C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing · University of Chinese Academy of Sciences, Nanjing +1
MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble
Aug 4, 2026Haoze Lv, Ning Lu, Shengcai Liu +2Automated Heuristic Design Evolutionary Optimization
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · The Hong Kong University of Science and Technology
EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design
Oct 12, 2026Oguzhan Gungordu, Ayse Tursucular, Siheng Xiong +1Automated Heuristic Design Large Language Model-Guided Optimization
Georgia Institute of Technology

Jul 13, 2026J/K move · Enter open · S save

RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

Yang Wu, Junran Pan, Yifan Zhang, Ning Xu+2

C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing · University of Chinese Academy of Sciences, Nanjing+1

Automated Heuristic Design Evolutionary Optimization Large Language Model-Guided Optimization Combinatorial Optimization

Open paper AskPDF arXiv

Automatic Heuristic Design (AHD) has emerged as a transformative approach for solving combinatorial optimization problems. While recent Large Language Model (LLM)-based methods have shown promise, they predominantly rely on fixed evolutionary operators and struggle to effectively accumulate and reuse historical search experience. This paper proposes RefineEvo, a novel evolutionary framework that transforms AHD from a static trial-and-error process into a planning-guided, experience-driven system. RefineEvo introduces a Planner to dynamically schedule evolutionary operators and trigger refinement based on the current search state, and a Reflector to distill valuable lessons into a Bidirectional Experience Pool containing both positive insights and negative pitfalls. This synergistic framework enables the system to adapt its search tools to the evolving complexity of the problem and leverage trajectory-aware, situation-conditioned insights to guide generation. Experiments on several classic combinatorial optimization benchmarks demonstrate that RefineEvo consistently outperforms strong baselines. In particular, RefineEvo delivers superior solution quality while improving token efficiency, enabling more efficient and autonomous heuristic design.

Abstract

Automated Heuristic Design

Explore similar work

RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

MuEvo: LLM-Driven Evolution of Multi-Heuristic Ensemble

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