Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design

Jianghan Zhu; Jianan Zhou; Fei Liu; Ni Zhang; Yaoxin Wu; Zhuoyi Lin; Zhiguang Cao

cs.AIOct 22, 2026

Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design

Authors: Jianghan Zhu, Jianan Zhou, Fei Liu, Ni Zhang, Yaoxin Wu, Zhuoyi Lin, Zhiguang Cao

Organizations: Singapore Management University · Nanyang Technological University · University of Zurich · ETH Zurich ·

Abstract

Large language models (LLMs) have demonstrated strong potential to automate heuristic design for NP-hard combinatorial optimization (CO) tasks without human intervention. Recent methods predominantly rely on evolutionary computation (EC) frameworks, where heuristic diversification is mainly induced through EC-like operators or downstream selection, while the direction of heuristic transformation remains largely unharnessed. In this paper, we propose a multi-directional Perturbation-Rewrite Search (PRS) framework for automatic heuristic design that factorizes heuristic transformation through directional search primitives at the generation level. Specifically, PRS operates on heuristic ideas through three complementary directions: expansion toward richer and more expressive designs, compression toward simpler and less specialized designs, and steering for fine-grained refinement, together enabling broader and more sustained exploration of diverse regions in the heuristic design space. PRS further organizes candidate exploration within a breadth-first search-based process with adaptive operator control, which ensures thorough candidate utilization and sustained exploration, and maintains strong search dynamics while preventing premature convergence. Extensive empirical results across diverse CO tasks show that PRS consistently discovers high-quality heuristics, demonstrating the effectiveness and generality of explicitly directional exploration design.

Figures & tables

Figure 1: An illustration of PRS pipeline.

Figure 2: An overview of BFS-based Heuristic Search. Starting from a root parent heuristic with its corresponding idea, PRS performs a BFS-style expansion in which new offspring ideas are generated via multi-directional perturbation and then realized as executable code through rewriting. The offspring codes are then evaluated and selectively retained in a fixed-size frontier at each depth. Terminal nodes correspond to pruned or non-extendable offspring. Dark green boxes denote heuristics that outperform the root parent, while light green (or light red ) boxes represent worse-than-root offspring that are accepted (or rejected) for inclusion in the next frontier. Each parent heuristic across BFS paths retains opportunity for further expansion, preventing early domination by a single trajectory. The beam size is set to $\kappa=3$ for illustration.


Task	CVRP						OP
N=	N=50		N=100		N=200		N=50		N=100		N=200
Method	Obj $\downarrow$	Gap $\downarrow$	Obj $\downarrow$	Gap $\downarrow$	Obj $\downarrow$	Gap $\downarrow$	Obj $\uparrow$	Gap $\downarrow$	Obj $\uparrow$	Gap $\downarrow$	Obj $\uparrow$	Gap $\downarrow$
DeepACO	8.888	–	14.932	–	27.159	–	19.867	–	36.392	–	63.380	–
ACO	18.282	105.69%	30.030	101.11%	48.582	78.88%	13.570	31.70%	24.149	33.64%	37.109	41.45%
LLM-based AHD (GPT-5-nano)

Table 1: Performance of ACO-based heuristics on CVRP and OP. All methods are evaluated on three test sets of 64 randomly generated instances each, following the setup in Dat et al. (2025) ; Zheng et al. (2025) . Test sets whose scales match the validation sets are underlined. Optimal solutions are approximated using DeepACO with significantly more ants and iterations than those in the baselines. The best-performing method is shaded, and each test set’s overall best result is in bold.


Test Sets	1k_100	1k_500	5k_100	5k_500	10k_100	10k_500	AVG
LLM-based AHD (GPT-5-nano)
Best Fit	4.77%	0.25%	4.31%	0.55%	4.05%	0.47%	2.40%
First Fit	5.02%	0.25%	4.65%	0.55%	4.36%	0.50%	2.56%
FunSearch	2.45%	0.66%	1.30%	0.25%	1.05%	0.21%	0.99%
EoH	2.69%	0.25%	1.63%	0.53%	1.47%	0.45%	1.17%

Table 2: Online bin packing problem results . The first four problem scales are used during validation, and the remaining are used for held-out test. Notations of problem scales are abbreviated, e.g., 1k_500 indicates 1,000 items and a fixed bin capacity 500.


Knapsack Problem (KP)
Test Sets	N=50		N=100		N=200
Method	Obj. $\uparrow$	Gap $\downarrow$	Obj. $\uparrow$	Gap $\downarrow$	Obj. $\uparrow$	Gap $\downarrow$
Optimal	20.037	–	40.271	–	57.448	–
GC	19.830	1.04%	40.030	0.60%	57.115	0.58%
POMO	19.612	2.12%	39.676	1.48%	57.271	0.31%

Table 3: Performance of step-by-step constructive heuristics on KP. Near-optimal objectives are obtained by OR-Tools. The best-performing method is shaded, and each test set’s overall best result is in bold.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Problem Size	Perturbation Moves	Iteration Limit
TSP20	5	73
TSP50	40	300
TSP100	40	1800
TSP200	40	1000
TSP500	60	250
TSP1000	80	100

Appendix

Table 4: GLS parameter settings for different TSP problem scales. The number of perturbation moves controls the strength of solution diversification, while the iteration limit determines the overall local search budget. Heuristics for TSP under GLS found by all LLM-based AHD frameworks are tested under the same configurations here.

Figure 5: Diversity analysis (CDI) of EoH, ReEvo, MCTS-AHD, and PRS on OBPP-Constructive and OP-ACO at different search stages ( $0.4T$ , $0.8T$ , and $T$ ). Error bars indicate standard deviation over three independent runs.

Figure 7: Operator contribution statistics. Each curve represents the cumulative share of best-so-far improvements triggered by each perturbation operator across all runs.

Task	Evaluation stage	Expansion			Compression			Steering
Task	Evaluation stage	Sel.	Imp.	Gain	Sel.	Imp.	Gain	Sel.	Imp.	Gain
OBPP-Constructive	0–249	32.42	35.21	3.241	34.25	26.67	5.881	33.33	41.10	4.849
	250–499	32.13	23.75	1.314	34.14	12.94	0.678	33.73	16.67	2.947
	500–749	34.15	20.24	3.541	32.11	16.46	2.415	33.74	22.89	1.958
	750–999	31.43	16.88	2.632	31.02	10.53	4.006	37.55	23.91	7.667
CVRP-ACO	0–249	31.36	66.67	3.947	34.09	66.67	4.059	34.55	53.95	6.751

Appendix

Table 5: Stage-wise behavior of UCB-based operator selection. For each operator, we report the selection rate (Sel.), any-improvement rate (Imp.), and mean best-child relative improvement (Gain), all in %. Statistics are aggregated over five runs.

Task	Operator	ID gap $\downarrow$	OOD gap $\downarrow$
KP-Constructive	Expansion	$\mathbf{0.03\%\pm 0.01\%}$	$0.04\%\pm 0.02\%$
	Compression	$0.06\%\pm 0.02\%$	$\mathbf{0.03\%\pm 0.00\%}$
	Steering	$0.05\%\pm 0.02\%$	$0.05\%\pm 0.03\%$
CVRP-ACO	Expansion	$\mathbf{0.89\%\pm 0.53\%}$	$6.31\%\pm 1.54\%$
	Compression	$1.45\%\pm 0.71\%$	$\mathbf{5.94\%\pm 1.02\%}$
	Steering	$1.26\%\pm 0.43\%$	$6.52\%\pm 0.63\%$

Appendix

Table 6: Generalization performance of the top-five children generated by each perturbation operator. Children are selected according to validation performance within each run. Lower gap is better.

LLM-based AHD (GPT-5-nano)
Task	CVRP		MKP		OP
N=	N=50	N=100	N=100	N=200	N=50	N=100
Method	Obj. $\downarrow$	Obj. $\downarrow$	Obj. $\uparrow$	Obj. $\uparrow$	Obj. $\uparrow$	Obj. $\uparrow$
ACO	18.282	30.030	18.969	38.766	13.570	24.149
DeepACO	8.888	14.932	23.091	41.988	19.867	36.392
EoH	9.360	16.700	22.518	40.568	14.776	28.627

Appendix

Table 7: Performance of ACO-based heuristics on black-box CVRP, MKP, and OP . We follow the settings of ReEvo ( Ye et al., 2024 ) in heuristic evolution and run each LLM-based method three times for average performance.

Travelling Salesman Problem (TSP)
Method	TSP 50		TSP 100		TSP 200		TSP 500
	Obj. $\downarrow$	Gap $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$
LKH3 ( Lin and Kernighan, 1973 )	5.680	–	7.762	–	10.715	–	16.524	–
POMO	5.697	0.30%	8.001	3.08%	12.897	20.37%	20.190	22.18%
GC (Nearest Neighbour)	6.944	22.26%	9.755	25.67%	13.502	26.02%	20.938	26.71%
LLM-based AHD GPT-4.1-nano

Appendix

Table 8: Performance of step-by-step construction heuristics on TSP, averaged over three runs. Bold denotes the best non-optimal objective value at each problem size. For each LLM setting, the best LLM-based AHD result in each column is shaded gray. Gaps are the relative difference to the optimal (or near-optimal) objective value obtained by LKH3.

Figure 8: Pareto analysis of runtime and solution quality on TSP under the GLS framework. Each scatter point corresponds to one heuristic candidate evaluated during search, where the x-axis denotes runtime per instance and the y-axis denotes tour length. Results are shown for four problem sizes ( $n=50,100,200,500$ ). The connected frontier for each method highlights the best observed quality–efficiency trade-off among its discovered heuristics. Lower tour length and runtime are preferred.

Method	TSP50		TSP100		TSP200		TSP500
	Gap(%) $\downarrow$	Time(s)	Gap(%) $\downarrow$	Time(s)	Gap(%) $\downarrow$	Time(s)	Gap(%) $\downarrow$	Time(s)
NeuOpt*	0.000	1.32	0.027	2.67	0.403	4.81	–	–
GNNGLS*	0.052	3.83	0.705	6.78	3.522	9.92	–	–
EoH	0.000	0.03	0.390	0.47	0.196	0.90	1.667	1.93
ReEvo	0.000	0.04	0.025	0.55	0.338	1.26	1.703	4.56
MCTS-AHD	0.000	0.02	0.000	0.47	0.270	0.90	1.680	1.82

Appendix

Table 9: Performance of heuristics on TSP benchmarks with guided local search framework. For a fair comparison, we report the result of the best performing heuristic over three independent runs following ReEvo ( Ye et al., 2024 ) . Gap (%) denotes the relative optimality gap to the best-known solution, and Time (s) denotes the average runtime per instance. * denotes results drawn from ReEvo ( Ye et al., 2024 ) .

Test Set	GUPTA	CDS	NEH	NEHFF	PFSPNet	LS	ILS1	ILS2	EoH	Ours
j50_m5	12.23	6.98	0.57	0.40	0.51	0.32	0.15	0.32	0.00	0.00
j50_m10	20.11	12.72	3.47	3.62	3.48	3.33	1.47	0.29	0.21	0.17
j50_m20	22.78	15.03	5.48	5.10	5.05	4.67	2.13	0.34	0.72	0.83
j100_m5	5.98	5.10	0.39	0.31	0.31	0.28	0.20	0.38	-0.04	-0.05
j100_m10	15.03	9.36	2.07	1.88	1.72	1.38	0.77	0.34	0.22	0.14
j100_m20	21.00	13.55	3.58	3.73	3.56	3.51	2.27	0.43	0.62	0.27

Appendix

Table 10: Results on Taillard ( Taillard, 1993 ) instance sets. The results of non-LLM-based methods are cited from EoH ( Liu et al., 2024a ) . Each entry reports the average relative gap (%) to the known upper bound in Taillard (lower is better). The best result in each row is highlighted in bold . Additionally, among all the LLM-based AHD methods, the best value is shaded.


Instance	Christofides	Greedy	Nearest insertion	Nearest-greedy	GHPP-best	EoH	ReEvo	Ours
bier127	13.03	19.50	23.05	23.25	15.64	19.60	10.79	8.31
d493	9.52	16.68	20.39	24.00	15.58	17.02	13.43	13.15
ch130	10.09	28.40	19.21	25.66	14.77	12.47	9.40	12.24
eil51	15.18	13.03	16.14	31.96	10.20	18.51	6.47	15.20
kroA150	13.44	20.24	19.09	26.08	15.59	24.61	11.62	9.86

Appendix

Table 11: Results of the GP-based method GHPP, and LLM-based AHD methods on designing step-by-step constructive heuristics for TSP on TSPLib instances. We report the optimality gap (%) of each instance. The results of GHPP-best, Christofides ( Christofides, 2022 ) , Greedy ( Brecklinghaus and Hougardy, 2015 ) , Nearest insertion and Nearest-greedy ( Rosenkrantz et al., 1977 ) are taken from ( Duflo et al., 2019 ) . LLM-based AHD methods (EoH, ReEvo, and PRS ) are each run three times with different starting nodes and averaged. The leading LLM-designed heuristic on each instance is shaded, and the overall best heuristic is shown in bold.


Method	run1	run2	run3	run4	run5	run6	run7	run8	run9	run10	avg	std	p-value
CVRP-ACO ( $\downarrow$ )
MCTS-AHD	8.842	8.957	8.623	8.993	9.012	8.790	9.103	8.929	9.231	9.186	8.967	0.184	–
PRS	8.563	8.588	8.751	8.785	8.989	8.949	8.835	8.943	9.012	9.058	8.847	0.174	0.0331
KP-Constructive ( $\uparrow$ )
MCTS-AHD	40.249	40.255	40.261	40.257	40.258	40.252	40.258	40.254	40.260	40.252	40.256	0.004	–

Appendix

Table 12: Statistical significance analysis of PRS over multiple independent runs. The reported p-values are from one-sided paired

t

-tests comparing PRS against MCTS-AHD. For TSP-GLS, the reported objective values denote gap (%).

Variations	KP ( $n=100$ ) $\uparrow$	CVRP ( $n=50$ ) $\downarrow$
PRS-BFS	40.2618 $\pm$ 0.0145	8.9583 $\pm$ 0.0726
PRS-CoT-SC	40.2532 $\pm$ 0.0418	9.3159 $\pm$ 0.0586
PRS-MCTS	40.2584 $\pm$ 0.0175	9.0728 $\pm$ 0.0960

Appendix

Table 13: Comparison of search strategy variants within the PRS framework. Results are reported as mean

\pm

standard deviation over three independent runs. For KP, higher is better; for CVRP, lower is better. The maximum number of evaluated heuristics is fixed to

T=1000

for all variants.


OBPP

N=	1k_100		5k_500
Method	Gap (%) $\downarrow$	std (%)	Gap (%) $\downarrow$	std (%)

Best Fit	4.77%	–	0.55%	–

Appendix

Table 14: Benchmarking PRS on different LLMs on OBPP (average gap (%) to the lower bound). Best result among all methods of each problem size is highlighted in bold while the best result among all LLM-based results of each scale is shaded.


KP

N=	N=100		N=200
Method	Obj. $\uparrow$	Gap (%) $\downarrow$	Obj. $\uparrow$	Gap (%) $\downarrow$

Optimal	40.271	–	57.448	–

Appendix

Table 15: Benchmarking PRS on different LLMs on KP (average objective and average gap (%) to optimal). Best result among all methods of each problem size is highlighted in bold while the best result among all LLM-based results of each scale is shaded.

Method	Metric	OBPP-Constructive	KP-Constructive	CVRP-ACO	OP-ACO
ReEvo	Time	8h	-	4h	5h
	Input Tokens	2.94M	-	3.30M	2.82M
	Output Tokens	1.02M	-	1.65M	1.68M
	#LLM Queries	2869	-	1433	1410
EoH	Time	10h	9h	6h	6h
	Input Tokens	2.40M	1.80M	1.83M	2.94M

Appendix

Table 16: Cost comparison across different AHD frameworks.

Modified Parameter	Value	KP-Constructive		OBPP-Constructive
		Gap	# Token (M)	Gap	# Token (M)
–	$(\kappa=d=3),\ \Delta/T=0.1$ $T_{\mathrm{sel}}=1.0,\ \|\mathcal{H}\|=50$	0.024%	4.25	0.802%	6.07
beam/depth	$(\kappa=d=4)$	0.026%	3.89	0.835%	5.72
beam/depth	$(\kappa=d=2)$	0.031%	4.98	0.913%	6.35
Stagnation ratio $\Delta/T$	0.05	0.027%	4.13	0.894%	6.18
Stagnation ratio $\Delta/T$	0.20	0.023%	4.40	0.836%	6.36

Appendix

Table 17: Sensitivity analysis of PRS on KP and OBPP under the step-by-step constructive framework. Lower gap is better.

Panel of Figure 9 — Figure 9: Example of an expansion operation on heuristics of OP under the ACO framework. The parent heuristic (top) primarily scores transitions using prize-to-distance preference and a route-length scaling factor. After expansion and LLM-based rewriting, the offspring (bottom) retains this backbone while introducing additional reward-aware structures, including local prize density and global high prize information. These additions enrich the heuristic’s decision logic and improve the validation score from $g=13.560$ to $g=14.194$ ( $+4.68\%$ ).

Panel of Figure 10 — Figure 10: Example of a compression operation on heuristics of OBPP under the step-by-step constructive framework. The parent heuristic (top) combines adaptive fit thresholds, variance-based global weighting, disparity control, and neighborhood smoothness. After compression and LLM-based rewriting, the offspring (bottom) retains the core fit, disparity, and smoothness mechanisms while simplifying the adaptive threshold and global weighting logic. The resulting heuristic improves the validation score from $g=2.170$ to $g=1.846$ .

Resource	License / Availability	URL
LKH3	Academic research use	http://webhotel4.ruc.dk/~keld/research/LKH-3/
OR-Tools	MIT License	https://developers.google.com/optimization/pack/knapsack
POMO	Available online	https://github.com/yd-kwon/POMO/tree/master
DeepACO	MIT License	https://github.com/henry-yeh/DeepACO
FunSearch	Apache License	https://github.com/google-deepmind/funsearch
EoH	MIT License	https://github.com/FeiLiu36/EoH/tree/main

Appendix

Table 18: External codebases and datasets used in this work.

Automated Heuristic Design

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

See all 84 papers

Heuristic Search as Language-Guided Program Optimization
Feb 17, 2026Mingxin Yu, Ruixiao Yang, Chuchu FanAutomated Heuristic Design Large Language Model-Guided Optimization
Massachusetts Institute of Technology, Cambridge, MA, USA
QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Design
Jul 6, 2026Nam Do Khanh, Nhat Nguyen Tran Minh, Dat Pham Vu Tuan +2Automated Algorithm Discovery Automated Heuristic Design
Hanoi University of Science and Technology Hanoi, Vietnam · George Mason University Fairfax, Virginia, USA
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

Feb 17, 2026J/K move · Enter open · S save

Heuristic Search as Language-Guided Program Optimization

Mingxin Yu, Ruixiao Yang, Chuchu Fan

Massachusetts Institute of Technology, Cambridge, MA, USA

Automated Heuristic Design Large Language Model-Guided Optimization Combinatorial Optimization LLM-Based Program Synthesis

Open paper AskPDF arXiv

Large Language Models (LLMs) have advanced Automated Heuristic Design (AHD) in combinatorial optimization (CO) in the past few years. However, existing discovery pipelines often require extensive manual trial-and-error or reliance on domain expertise to adapt to new or complex problems. This stems from tightly coupled internal mechanisms that limit systematic improvement of the LLM-driven design process. To address this challenge, we propose a structured framework for LLM-driven AHD that explicitly decomposes the heuristic discovery process into modular stages: a forward pass for evaluation, a backward pass for analytical feedback, and an update step for program refinement. This separation provides a clear abstraction for iterative refinement and enables principled improvements of individual components. We validate our framework across four diverse real-world CO domains, where it consistently outperforms baselines, achieving up to

0.17

improvement in QYI on unseen test sets. Finally, we show that several popular AHD methods are restricted instantiations of our framework. By integrating them in our structured pipeline, we can upgrade the components modularly and significantly improve their performance.

Abstract

Automated Heuristic Design

Explore similar work

Heuristic Search as Language-Guided Program Optimization

QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Design

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