BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design

Chuyang Xiang; Yichen Wei; Jiale Ma; Handing Wang; Junchi Yan

cs.AIApr 14, 2026

BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design

Authors: Chuyang Xiang, Yichen Wei, Jiale Ma, Handing Wang, Junchi Yan

Abstract

Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic heuristic design. However, most existing LHHs just perform well in optimizing a single function within a pre-defined solver. Their single-layer evolution makes them not effective enough to write a competent complete solver. While some variants incorporate hyperparameter tuning or attempt to generate complex code through iterative local modifications, they still lack a high-level algorithmic modeling, leading to limited exploration efficiency. To address this, we reformulate heuristic design as a Bi-level Optimization problem and propose BEAM (Bi-level Memory-adaptive Algorithmic Evolution). BEAM's exterior layer evolves high-level algorithmic structures with function placeholders through genetic algorithm (GA), while the interior layer realizes these placeholders via Monte Carlo Tree Search (MCTS). We further introduce an Adaptive Memory module to facilitate complex code generation. To support the evaluation for complex code generation, we point out the limitations of starting LHHs from scratch or from code templates and introduce a Knowledge Augmentation (KA) Pipeline. Experimental results on several optimization problems demonstrate that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84% on aggregate in CVRP hybrid algorithm design. BEAM also designs a heuristic that outperforms SOTA Maximum Independent Set (MIS) solver KaMIS.

Figures & tables

Fig. 1: LHH Usage: 1) Single function design (used in [ 11 , 7 , 12 ] ) for a given algorithm structure. 2) Hybrid algorithm design (proposed): designing a whole solver with given heuristic components. 3) Entire algorithm design: designing algorithms from scratch.

Fig. 2: Pipeline of our BEAM. The exterior layer designs the heuristic (code) structure (the heuristic()) via genetic evolution; the interior layer designs the functions (the func_i()s) by MCTS. Evaluation happens every time when designing a new function to ensure the function quality. After the entire genetic evolution, the best heuristic (code structure + functions) are printed out, and the functions (the func_i()s) are stored into the adaptive memory for future code structures to call directly. As shown in our experiments (Table V ), BEAM has better performance over Google’s AlphaEvolve [ 9 ] .

Methods	Individual Strategy	Search Method	Calibration
FunSearch [ 29 ]	One-shot	Random sampling	/
EoH [ 11 ]	One-shot	Simple evolution ∗	LLM
EvoCAF [ 40 ]	One-shot	Simple evolution	LLM
HSEvo [ 41 ]	One-shot	GA	HS
LLaMEA-HPO [ 42 ]	One-shot	GA	SMAC3
MCTS-AHD [ 33 ]	One-shot	MCTS	/

TABLE I: Language Hyper Heuristic (LHH) comparison. *: Simple evolution means simply updating all heuristics using different prompts,

{\dagger}

: AlphaEvolve outputs formatted instructions on revising code templates.

Fig. 3: Proposed KA pipeline. For each task, LLMs first summarize problem-specific tags and then use them to construct KnoBase and the LLM-retrieved part of HeuBase.

Section	Problem	LLM Model	Budget Type	Budget	Attempts	Metric
Section V-A	TSP	DeepSeek-V3	Time	40min	5	Best & Average
Section V-A	BPP	DeepSeek-V3	Time	60min	5	Best & Average
Section V-A	CAF	DeepSeek-V3	Time	100min	5	Best
Section V-B	MIS (w/ RLSA)	DeepSeek-V3	Time	4h	3	Best ∗
Section V-B	MIS (w/ KaHIP & ARW)	DeepSeek-V3	Time	4h	3	Best
Section V-B	CVRP	DeepSeek-R1	Time	5h	3	Best

TABLE II: Detailed Budget Settings for Comparison with LHHs (Evolving Stage).

Methods	TSP-100		TSP-500		Weibull5k		Weibull10k		Weibull100k
	MIN $\downarrow$	AVG $\downarrow$	MIN $\downarrow$	AVG $\downarrow$	MIN $\downarrow$	AVG $\downarrow$	MIN $\downarrow$	AVG $\downarrow$	MIN $\downarrow$	AVG $\downarrow$
ReEvo [ 7 ]	0.01%	0.03%	1.00%	1.07%	2.83%	3.36%	2.71%	3.33%	2.38%	3.07%
EoH [ 11 ]	8.39e-3%	0.01%	0.85%	0.96%	3.13%	3.18%	2.90%	3.02%	2.75%	2.87%
MCTS-AHD [ 33 ]	0.02%	0.04%	0.99%	1.12%	4.25%	4.25%	4.06%	4.06%	3.88%	3.88%
BEAM (ours)	2.63e-3%	6.77e-3%	0.88%	0.95%	2.58%	3.26%	1.99%	3.04%	1.82%	2.86%

TABLE III: Results on Traditional CO Benchmark (TSP & BPP Single Function Design).

Methods	Type	Griewank $\downarrow$		Rosenbrock $\downarrow$		Levy $\downarrow$		TH $\downarrow$		Styblinski $\downarrow$
		C=12	C=120	C=12	C=120	C=12	C=120	C=12	C=120	C=12	C=120
EI-cool	MH	0.78	0.18	7.14	1.85	0.43	9.14e-4	1.78	1.05e-3	11.88	3.92e-3
EvoCAF ∗	LHH	1.06	0.13	4.75	0.05	0.11	1.77e-3	0.24	1.67e-3	1.93	0.02
MCTS-AHD ∗	LHH	0.56	0.22	19.81	0.48	0.06	2.67e-3	0.08	3.34e-3	0.69	7.10e-3
AlphaEvolve	LHH	0.89	0.19	15.93	0.14	0.15	2.18e-3	1.89	3.06e-3	14.82	0.02
BEAM (Ours)	LHH	0.49	0.13	9.81	0.41	0.26	6.99e-4	1.68	2.70e-4	1.25	1.54e-3

TABLE IV: Results on Traditional CAF Benchmark. ∗ Best heuristic from their repository; MH: Manually-designed Heuristic; TH: Trigonometric-Hump, Styblinski: Styblinski-Tang, HM: Hartmann.

Methods	Type	RB-200-300 (t=5s)			RB-800-1200 (t=60s)			SATLIB (t=60s)
		T ∗	OBJ $\uparrow$	GAP $\downarrow$	T	OBJ $\uparrow$	GAP $\downarrow$	T	OBJ $\uparrow$	GAP $\downarrow$
KaMIS (ReduMIS, 60s)	GA	15k	20.09	0.00%	15k	43.00	0.00%	15k	425.95	0.00%
RLSA	SA	9k	19.92	0.85%	60k	39.79	7.47%	60k	411.81	3.32%
ReEvo w/ RLSA	LHH	75	19.99	0.50%	150	40.79	5.03%	150	423.61	0.55%
EoH w/ RLSA	LHH	75	20.05	0.18%	150	41.21	4.04%	150	424.20	0.41%
MCTS-AHD w/ RLSA	LHH	75	20.01	0.39%	150	41.13	4.35%	150	423.96	0.47%

TABLE V: Performance comparison on MIS, CVRP, and TSP.

Methods	Rastrigin	Rosenbrock	Sphere	Ackley	Griewank	Average
Methods	GAP $\downarrow$	GAP $\downarrow$	GAP $\downarrow$	GAP $\downarrow$	GAP $\downarrow$	GAP $\downarrow$
LLaMEA [ 8 ] ∗	0.995	0.000	0.000	4.4e-16	0.007	0.201
ReEvo [ 7 ]	0.002	4.785	0.000	1.1e-5	1e-6	0.957
EoH [ 11 ]	10.519	14.804	0.543	0.714	3.5799	6.032
LlaMEA-HPO	1.512	0.419	5.5e-10	6.9e-5	0.001	0.386
BEAM	0.026	0.000	0.000	0.000	0.007	0.007

TABLE VI: Different LHHs on BBOB evaluation. ∗ From LLaMEA’s repository [ 57 ] (we test the ERADS function which is claimed to be its best design).

Adaptive Memory	TSP	CVRP	CAF
BEAM	-9.55%	0.86%	3.46%
BE	-8.12%	0.89%	4.41%
Education Method	MIS	CVRP	CAF
One-Shot	3.63%	1.07%	5.12%
MCTS	3.05%	0.86%	8.17%
Model Generalization	TSP-50	TSP-100	TSP-500

TABLE VII: Ablation study on Adaptive memory, education, and model-generalization (TSP is tested on TSP-500, MIS is tested on RB 800-1200, CVRP is tested on CVRP-500, CAF is tested on Ackley & Rastrigin.)

Fig. 4: Best individual distribution. Label ‘Gap’ is the performance of the code generated by the models. It shows that the code generated by BEAM has the best average performance and the smallest variance among the three models.

Fig. 5: Heuristic Length Distribution. BEAM consistently produces the longest and most complex heuristics, which is one reason for its superior performance.

Methods	AVG $\downarrow$	VAR $\downarrow$
BEAM	3.46	0.01
BE	4.41	0.19

TABLE VIII: BEAM vs. BE: Average and Variance of Gaps.

Fig. 6: BEAM vs. BE: Best Gap - Iteration.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Function	Selection Frequency
kaffpa	82%
node_separator	56%
arw	80%
arw_1iter	86%
deterministic_rounding	14%

Appendix

TABLE IX: Selection Frequency of HeuBase Functions.

Method	MCTS Usage
MCTS-AHD	This work just substitutes EoH’s evolutionary operator with an MCTS-like strategy for algorithm search, still being a single-layer framework.
PoH	The only difference between PoH and MCTS-AHD is that PoH introduced a reflection step similar to ReEvo in the MCTS process.
BEAM (Ours)	In our work, MCTS is used as the education strategy for an algorithm structure in the interior layer of our bi-layer structure, searching different realization for the unrealized functions of the structure.

Appendix

TABLE X: Further Comparison.

Prob.	MC	Type	Design Type	Heuristic Type	Dataset Size	Allowed KA
TSP ∗	Easy	GCO	Single Function	Not Restricted	3*128	/
BPP	Easy	CO	Single Function	Not Restricted	3*5	/
CAF	Easy	BO	Single Function	Not Restricted	1025	/
MIS	Medium	GCO	Hybrid Algorithm	GA	3*500	HeuBase (RLSA)
MIS	Medium	GCO	Hybrid Algorithm	GA	3*500	HeuBase (KaHIP, ARW)
TSP	Medium	GCO	Entire Algorithm	ACO	3*128	/

Appendix

TABLE XI: Unified LHH Evaluation Settings with KA.

Problem	Dataset	Instances
TSP (GLS)	TSP-200	10
BPP	Weibull5k	10
CAF	Ackley & Rastrigin	5*2
MIS (w/ RLSA)	RB 200-300	25
MIS (w/ KaHIP & ARW)	RB 800-1200	10
CVRP	CVRP-100	20

Appendix

TABLE XII: Evaluation Dataset for BEAM.

Parameter	Value
llm_temperature	0.7 (for Fixing) / 1.0 (others)
crossover_rate	0.7
mutation_rate	0.3
mc_func_pop	3
max_func_num	4

Appendix

TABLE XIII: Common Hyperparameter Setting for BEAM.

Methods	iter	ips	mps	mft
One-Shot	8	20	5	3
MCTS	3	5	3	3

Appendix

TABLE XIV: Hyperparamter Setting for Education Method Ablation Study.

Fig. 10: EoH vs. BEAM: MIS solver with RLSA.

Fig. 11: Generated Algorithm Iteration Curve.

Automated Heuristic Design

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

See all 84 papers

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design
Jun 12, 2026Zishang Qiu, Xinan Chen, Rong Qu +1Automated Heuristic Design Evolutionary Optimization
School of Computer Science, University of Nottingham Ningbo China, Ningbo, China · School of Computer Science, University of Nottingham, Nottingham, UK
A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees
Apr 27, 2026Bin Chen, Shouliang Zhu, Beidan Liu +4Automated Algorithm Discovery Automated Heuristic Design
The Institute of Intelligent Computing, University of Electronic Science and Technology of China, Chengdu 611731, China · College of Systems Engineering, National University of Defense Technology, Changsha 410073, China · Academy of Military Medical Sciences, Beijing 100071, China
ES-AHD: An Evolution Strategy Framework for Automatic Heuristic Design
Aug 26, 2026Yutao Lai, Kezhao Lai, Hai-Lin Liu +2Automated Heuristic Design Large Language Model-Guided Optimization
School of Mathematics and Statistics Guangdong University of Technology Guangzhou, China · School of Computer Science and Technology Xidian University Xi’an, China · School of Systems Science Beijing Normal University Beijing, China

Jun 12, 2026J/K move · Enter open · S save

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design

Zishang Qiu, Xinan Chen, Rong Qu, Ruibin Bai

School of Computer Science, University of Nottingham Ningbo China, Ningbo, China · School of Computer Science, University of Nottingham, Nottingham, UK

Automated Heuristic Design Evolutionary Optimization Large Language Model-Guided Optimization Metacognition in Language Models

Open paper AskPDF arXiv

Large Language Models (LLMs) have advanced Automatic Heuristic Design (AHD) by enabling heuristic generation through reasoning and code synthesis. In LLM-based AHD, the LLM reasons about algorithm design and generates executable heuristic code. Existing architectures adopt two main paradigms: Natural Evolution applies crossover and mutation to this code to explore diverse strategies, but discards the reasoning traces behind the design decisions, weakening knowledge retention; Metacognitive Evolution retains these reasoning traces and refines them through reflection, but lacks population-level recombination, limiting exploration. These limitations reduce search efficiency, stability, and solution quality on complex problems. To address this gap, we propose MeEvo, an AHD framework that cyclically couples Natural Evolution and Metacognitive Evolution with operator balance that shifts from exploration to exploitation. Natural Evolution explores heuristic code while recording LLM-generated reasoning traces, fitness values, errors and best heuristic into a shared history; Metacognitive Evolution then reflects on this history to generate improved heuristics that feed into the next Natural Evolution cycle. This design enables population-driven exploration and reflection-driven refinement to reinforce each other. Experiments on five optimization problems show that MeEvo achieves stronger performance and lower variance than tested LLM-based AHD architectures, especially on complex constrained tasks.

Abstract

Automated Heuristic Design

Explore similar work

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design

A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees

ES-AHD: An Evolution Strategy Framework for Automatic Heuristic Design