From Search to Signal: Online Post-Training in Automatic Heuristic Design

Yilun Yuan; Tianyu Zhou; Zhenzhou Tang

cs.LGSep 30, 2026

From Search to Signal: Online Post-Training in Automatic Heuristic Design

Authors: Yilun Yuan, Tianyu Zhou, Zhenzhou Tang

Organizations: Wenzhou University

Abstract

Large language model (LLM)-based automatic heuristic design (AHD) iteratively proposes and refines heuristics, pairing design rationales with executable code. Task-specific evaluators assess programs; execution outcomes and performance scores guide search. Many AHD systems keep the generator frozen; EvoTune and Co-Evolution of Algorithms and Language Model (CALM) instead update it from evaluated candidates. When such outcomes drive reinforcement learning with verifiable rewards (RLVR), they create a search-coupled loop: the evaluated candidate stream supplies both search-state updates and training signals for the model that generates future candidates. Yet validity and performance do not uniquely determine useful model updates; converting them into learning signals must account for the prompt and evolving search state that produced each candidate. We formulate online post-training of small open-weight LLMs in AHD as context-dependent signal construction and develop alternative mappings from program validity, task performance, and generation context to update signals. Using shared evaluated rollouts and matched update budgets, controlled experiments across AHD tasks and model families compare these mappings with online post-training baselines, testing their effects on validity, performance among valid proposals, and the yield of valid proposals that improve under contextual comparisons. Complementary checkpoint, frozen-search, and live-system evaluations assess whether proposal-level gains appear in updated checkpoint behavior and subsequent search, rather than arising solely from accumulated search state. A resource-matched comparison under pre-specified cost accounting tests whether online updating adds value beyond additional search with a frozen generator. Together, this design avoids treating end-to-end search gains alone as evidence of stronger heuristic-design capabilities.

Figures & tables

Figure 1: Search-coupled online post-training and our intervention boundary. Each evaluated group updates the search state and supplies learner rewards. We keep search, group normalization, and optimization fixed and vary only

\phi_{a}

. Live arms generate different future evidence once their models diverge.

Construction	Evidence and reference	Reward supplied to GRPO	Role
Native CALM	Typed failures; nonlinear comparison with $b_{t}$	Released piecewise reward $r^{\mathrm{N}}$	Online baseline
Factorized Validity–Quality	Binary validity; signed, RMS-scaled $\Delta_{t,i}$ for valid candidates	$r^{\mathrm{F}}_{t,i}=\tfrac{1}{2}v_{t,i}+\tfrac{1}{2}q_{t,i}$	Separate feasibility from quality
Pre-Generation Tail-Weighted	Typed outcomes; pre-generation score novelty, repetition, and gap above $F_{t}$	$r^{\mathrm{T}}_{t,i}=G\omega_{t,i}$	Emphasize the group upper tail
Search-Exposure Residual	Typed validity; $\Delta_{t,i}$ ; counterfactual one-step parent exposure $\rho_{t,i}$	$r^{\mathrm{S}}_{t,i}=a^{V}_{t,i}+a^{Q}_{t,i}+a^{S}_{t,i}$	Search-derived mechanism probe
Frozen CALM	Same search and evaluator; updates disabled	—	No-update control

Table 1: Reward constructions compared with search, evaluation, grouping, and GRPO held fixed. The tail-weighted construction uses the group-concentration rule of TTT-Discover ( Yuksekgonul et al. 2026 ) ; Search-Exposure Residual is evaluated only as a mechanism probe.

Figure 2: Learner-path audit. (a) Group standardization removes additive shifts and nearly removes positive rescaling, while gating and nonlinear spacing can survive. (b) Shared-record advantage separation, matched-update cosine, and fixed-context log-probability changes trace signal propagation; open markers denote a degenerate cell and green denotes Search-Exposure Residual. (c) Candidate prevalence calibrates positive-advantage mass by class base rate. Panel (b) establishes mechanism separation, not efficacy.

Figure 3: Proposal and search outcomes. (a) Execution outcomes across three TSP–Qwen seeds. (b) Mean best-so-far gain; bands show the observed seed range. (c) Same-seed gains over Frozen under live updating (filled) and restarted, update-disabled search (open); lines connect seeds. Native/Factorized and Tail-weighted use independently matched restart cohorts.

	Search outcomes		Proposal stream
Condition	Final best	Trajectory AUC	Valid (%)	Valid-only perf.	Improve yield (%)
Frozen	-6.2329 $\pm$ 0.0105	-6.2417 $\pm$ 0.0046	60.85 $\pm$ 0.55	-9.8800 $\pm$ 0.8639	2.83 $\pm$ 0.50
Native	-6.2090 $\pm$ 0.0289	-6.2203 $\pm$ 0.0196	93.92 $\pm$ 1.68	-6.4966 $\pm$ 0.0986	2.98 $\pm$ 1.16
Factorized	-6.2041 $\pm$ 0.0116	-6.2179 $\pm$ 0.0087	95.60 $\pm$ 0.64	-6.7488 $\pm$ 0.1168	3.60 $\pm$ 1.25
Tail-weighted	-6.1963 $\pm$ 0.0248	-6.2123 $\pm$ 0.0148	85.12 $\pm$ 2.50	-7.0468 $\pm$ 0.2214	4.63 $\pm$ 0.33

Table 2: Core TSP–Qwen2.5-7B live-search results over three matched seeds. Entries are mean

\pm

sample standard deviation, and higher is better throughout. Bold marks the highest descriptive mean in each column, not statistical significance. Validity requires an executable completion with a finite task score and is distinct from evaluator dispatch.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Layer	Tasks	Models	Seeds	Shared evidence	Claim supported
Normalizer replay	TSP, CVRP, OBP, OP	recorded generators	–	evaluated records	whether reward differences survive group normalization
Matched update	TSP, CVRP	Qwen2.5-7B, DeepSeek-Coder-7B	1/cell	tokens, masks, reference log probabilities, update budget	whether an advantage difference reaches parameter updates
Formal live cohort	TSP	Qwen2.5-7B	3	starts, seeds, 500 groups	proposal-stream and equal-horizon live-search effects
Frozen restart	TSP	Qwen2.5-7B	3	final adapter, reset population, zero updates	checkpoint effect after removing accumulated live population
Directional breadth	CVRP; TSP (DeepSeek only)	Qwen2.5-7B (CVRP); DeepSeek-Coder-7B	1/cell	task/model protocol within cell	directional breadth across three task–model cells, not multi-seed efficacy
Resource anchor	TSP	Qwen2.5-7B	3	preregistered timing-derived group budgets	endpoint sensitivity to allocating compute to extra Frozen search

Appendix

Table 3: Evidence hierarchy and claim map. “Shared” identifies quantities held identical across conditions. A dash under seeds means that the unit is a shared record group rather than an independently generated search trajectory.

Python	3.10.20	PyTorch	2.5.1
Transformers	4.49.0	TRL	0.15.1
PEFT	0.14.0	Unsloth	2025.3.18
vLLM	0.7.3	Ray	2.40.0
NumPy	1.26.4	bitsandbytes	0.45.2

Appendix

Table 4: Principal software environment recorded by formal manifests.

Host class	Accelerator	CPU / memory / OS	Evidence role
Local workstation	3 $\times$ NVIDIA RTX 4090, 24,564 MiB each; driver 550.144.03	Intel Xeon w5-2455X, 12 cores/24 threads; 125 GiB RAM; Linux 5.15	most formal live runs, including at least one run from every condition; Qwen breadth; Gate-4 prefixes; API-served frozen runs; common-context probe
Shared GPU host	4 $\times$ NVIDIA RTX 3090, 24,576 MiB each	CPU model, RAM, and OS not archived in formal manifests	selected Tail-weighted live/restart runs; one Frozen formal seed; DeepSeek-Coder breadth; sequential Frozen references
A100 host	1 $\times$ NVIDIA A100, 40,960 MiB	CPU model, RAM, and OS not archived in formal manifests	selected mechanism and breadth cells; one Tail-weighted formal seed

Appendix

Table 5: Hardware used by reported experiments. CPU and operating-system fields were not consistently captured on the historical remote 3090 and A100 hosts; we report this absence instead of inferring their models. Wall-clock claims use only the preregistered timing-derived resource protocol and do not pool throughput across these heterogeneous hosts.

Search / generation	Value	Optimization	Value
Task / live model	TSP / Qwen2.5-7B-Instruct	Adapter	LoRA rank 32, alpha 64
Seeds	42, 3407, 1926000	Target modules	q, k, v, o, gate, up, down projections
Groups / completions	500 / 2,000	Quantization	4-bit base model
Prompts per step / group size	1 / 4	Learning rate	$5\times 10^{-5}$ , constant
Population size	10	Optimizer	8-bit AdamW
Operator weights	simplification 1; injection 1; replacement 2; crossover 4	Adam betas / weight decay	0.9, 0.99 / 0.1

Appendix

Table 6: Final parameters for the formal local-model experiments. Values not explicitly overridden in the runner are the recorded TRL 0.15.1 defaults shown here.

Condition	Final best	Trajectory AUC	Valid (%)	Valid-only perf.	Improve (%)
Frozen	-6.2329 $\pm$ 0.0105	-6.2417 $\pm$ 0.0046	60.85 $\pm$ 0.55	-9.8800 $\pm$ 0.8639	2.83 $\pm$ 0.50
Native	-6.2090 $\pm$ 0.0289	-6.2203 $\pm$ 0.0196	93.92 $\pm$ 1.68	-6.4966 $\pm$ 0.0986	2.98 $\pm$ 1.16
Factorized	-6.2041 $\pm$ 0.0116	-6.2179 $\pm$ 0.0087	95.60 $\pm$ 0.64	-6.7488 $\pm$ 0.1168	3.60 $\pm$ 1.25
Tail-weighted	-6.1963 $\pm$ 0.0248	-6.2123 $\pm$ 0.0148	85.12 $\pm$ 2.50	-7.0468 $\pm$ 0.2214	4.63 $\pm$ 0.33

Appendix

Table 7: Complete three-seed TSP–Qwen live cohort. Panel (a) reports mean

\pm

sample standard deviation; bold marks the highest descriptive mean in each column and does not imply statistical significance. Panel (b) lists all seed-level records. Higher is better for all performance columns; Valid and Improve are percentages, and every seed contains 2,000 completions.

Figure 4: Within-seed paired differences for the formal live cohort. Diamonds denote means and bars the observed three-seed range. Positive values favor the first condition. Differences against Frozen combine online updating with the named reward construction; differences against Native isolate reward construction within the same online-training host.

Figure 5: Stage-wise proposal behavior over early (groups 1–100), middle (101–250), and late (251–500) search. These values describe each condition’s endogenous live contexts; they are not fixed-prompt checkpoint evaluations.

Task	Model	Variant	Final best	Trajectory AUC	Valid (%)	Valid-only perf.	Improve (%)
CVRP	DeepSeek Coder	Frozen	-9.0676	-9.3136	49.20	-12.2861	3.35
CVRP	DeepSeek Coder	Native	-8.7337	-8.8805	81.00	-10.6994	3.45
CVRP	DeepSeek Coder	Factorized	-8.9977	-9.0951	81.50	-11.2008	2.85
CVRP	Qwen2.5	Frozen	-9.1271	-9.4523	63.90	-11.0669	5.60
CVRP	Qwen2.5	Native	-9.1517	-9.4046	88.85	-10.3968	5.00
CVRP	Qwen2.5	Factorized	-9.1097	-9.4950	94.80	-10.5522	5.60

Appendix

Table 8: Single-seed directional live-search breadth. These cells assess directional consistency across tasks and model families and do not support uncertainty or aggregate superiority claims.

Figure 6: Directional live breadth in three single-seed cells spanning TSP/CVRP-ACO and two 7B model families. Markers show observed directions rather than uncertainty estimates.

Figure 7: Diagnostic atlas from the 12-run formal cohort. Panels decompose operator-conditioned proposal funnels, archive admission versus immediate frontier contribution, collapse-centered observational changes, and exact response recurrence. Coverage and collapse panels are descriptive and do not identify causal effects of individual search operators.

Figure 8: Same-seed live and frozen-restart results. Restart conditions load a final adapter, reset the population, and execute zero optimizer steps. A live endpoint therefore includes both checkpoint and accumulated-population effects, whereas restart tests the checkpoint in a new search trajectory.

Figure 9: Held-out TSP evaluation of final heuristics at the available problem sizes. This evaluates discovered heuristic artifacts, not fixed-context checkpoint generation. Seed-level points remain visible.

Seed	Online condition	Groups (online/Frozen)	Online final	Frozen final	$\Delta$ final	$\Delta$ valid (pp)	$\Delta$ valid-only
42	Native	500/883	-6.2176	-6.2167	-0.0010	+27.01	+0.742
42	Factorized	500/762	-6.2221	-6.2167	-0.0055	+25.42	+0.545
3407	Native	500/572	-6.2217	-6.2303	+0.0086	+34.45	+2.360
3407	Factorized	500/536	-6.1939	-6.2303	+0.0365	+34.43	+2.004
1926000	Native	500/581	-6.2419	-6.2003	-0.0415	+39.88	+1.045
1926000	Factorized	500/500	-6.2208	-6.2003	-0.0205	+40.50	+1.617

Appendix

Table 9: Three-seed Gate-4 endpoint comparisons under preregistered, timing-derived Frozen-search group budgets.

\Delta

is online minus Frozen, so higher values favor online updating. Frozen metrics are recomputed from exact stored prefixes. The budgets are not exact realized-time matches; full-run timing drift and unavailable timestamps for shorter prefixes are reported in the text.

Seed	Checkpoint	Valid / 256	Valid (%)	Valid-only perf.	Improve $\mid$ valid (%)	Best-of-4 improve (%)
3407	Frozen	7	2.73	-8.9086	0.00	0.00
3407	Native	12	4.69	-8.8106	8.33	1.56
3407	Factorized	33	12.89	-9.5113	12.12	3.12
1926000	Frozen	7	2.73	-8.9086	0.00	0.00
1926000	Native	8	3.12	-8.8336	0.00	0.00
1926000	Factorized	3	1.17	-8.6397	0.00	0.00

Appendix

Table 10: Common-context executable CVRP–Qwen checkpoint probe. The fixed prompt bank makes validity and contextual improvement directly comparable within a seed. “Improve

\mid

valid” conditions on valid completions; “Best-of-4 improve” is the fraction of the 64 prompts whose sampled group contains an improvement. Higher is better.

Seed	Valid (%)	Valid-only	Improve (%)	Frontier (%)	Final best	AUC	Prompt tok.	Completion tok.
42	82.05	-9.0526	3.25	0.25	-6.2202	-6.2435	1,745,317	672,208
3407	82.15	-9.8845	4.30	0.30	-6.2254	-6.2395	1,890,022	713,864
1926000	83.15	-9.6897	4.65	0.75	-6.2109	-6.2518	1,842,358	711,707
Mean	82.45	-9.5423	4.07	0.43	-6.2188	-6.2449	1,825,899	699,260

Appendix

Table 11: Completed provider-reported GPT-4o-mini frozen-system reference. Each row uses 2,000 sequential completions and zero updates. Higher is better for performance columns. Rows are repeated seeds rather than competing methods, so no best-seed value is highlighted.

Explore similar work

Jul 15, 2026cs.NE

How to Guide LLM Generation: Dual-Surrogate Guided Search for Automated Heuristic Design

Large language models (LLMs) have made automated heuristic design (AHD) increasingly practical by generating executable heuristic code from task descriptions and evaluator feedback. Yet under a limited query and evaluation budget, search efficiency depends critically on a pre-generation decision. Before each LLM query and black-box evaluation, the system must choose which archived heuristics to reuse as parents and which generation operator should transform them. Existing methods typically choose such actions with predefined rules, leaving the expected outcome of each concrete operator-parent action only indirectly modeled. Therefore, we propose \emph{\fullmethod{}} (\method{}), a surrogate-guided action-selection module for operator-parent selection in LLM-based AHD. \method{} guides the LLM code-generation process by scoring pre-generation actions with two complementary surrogates. Specifically, a transition surrogate is proposed to predict the latent distribution of the child representation induced by an operator-parent action, while an instance-conditioned utility surrogate is proposed to estimate the expected performance of sampled child latents. Moreover, we propose an uncertainty-aware acquisition rule that combines predicted utility, utility uncertainty, and transition uncertainty to select the next LLM generation action. Across a diverse heuristic-design suite, \method{} is competitive with strong LLM-AHD baselines, and ablation and action-selection analyses suggest that its behavior goes beyond simple archive ranking or fixed operator preferences.

Yuhan Wang, Chaoda Peng, Xingyu Wu +2

College of Mathematics and Informatics, South China Agricultural University · Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University · College of Artificial Intelligence, Nankai University

Automated Heuristic Design Artificial Intelligence Search Large Language Model Generation Action Selection

Ask PDF

May 9, 2026cs.AI

AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design

Automatic heuristic design (AHD) has emerged as a promising paradigm for solving NP-hard combinatorial optimization problems (COPs). Recent works show that large language models (LLMs), when integrated into well-designed frameworks (i.e., LLM-AHD), can autonomously discover high-performing heuristics. However, existing LLM-AHD frameworks typically treat LLMs as passive generators within fixed workflows, where the model generates heuristics from manually designed, limited context. Such context may fail to capture state-dependent information (e.g., specific failure modes), leading to inefficient trial-and-error exploration. To overcome these limitations, we propose AHD Agent, a novel tool-integrated, multi-turn framework that empowers LLMs to proactively decide whether to generate heuristics or invoke tools to retrieve targeted evidence from the solving environment. To effectively train such a dynamic decision-making agent, we introduce an agentic reinforcement learning (RL) system, which leverages a novel environment synthesis pipeline to optimize a compact model's generalizable AHD capabilities. Experiments across eight diverse domains, including four held-out tasks, demonstrate that our 4B-parameter agent matches or surpasses state-of-the-art baselines using much larger models, while requiring significantly fewer evaluations. Model and inference scaling analysis further reveals that AHD Agent offers an effective trajectory toward truly autonomous heuristic design.

Haoze Lv, Ning Lu, Ziang Zhou +1

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology · Zhongguancun Academy · The Hong Kong University of Science and Technology

Automated Heuristic Design Agentic Optimization Agentic Reinforcement Learning Large Language Models(Llms

Ask PDF

May 7, 2026cs.AI

Back to the Beginning of Heuristic Design: Bridging Code and Knowledge with LLMs

Large language models (LLMs) have recently advanced automatic heuristic design (AHD) for combinatorial optimization (CO), where candidate heuristics are iteratively proposed, evaluated, and refined. Most existing approaches search over executable programs and distill insights from execution feedback to guide later iterations. Because this process moves from low-level implementations to high-level principles, we refer to it as a bottom-up paradigm. We argue that this view is incomplete and introduce a complementary top-down perspective: knowledge becomes the primary search object and code merely instantiates and tests it, making what is learned explicit and reusable across problems and trajectories. We formalize this shift through a statistical-learning view that exposes a distortion--compression trade-off, and instantiate it in both population-based and tree-based AHD frameworks. Across CO and tasks beyond it, knowledge-first search improves discovery efficiency, transfer, and generalization, often outperforming code-centric pipelines, while combining both strategies yields further gains. Our results suggest that progress in AHD depends on iteratively constructing and evolving interpretable hypotheses that retain value beyond a single search trajectory.

Nguyen Viet Tuan Kiet, Bui Dinh Pham, Dao Van Tung +2

Hanoi University of Science and Technology, Hanoi, Vietnam · University of Sydney, Sydney, Australia

Automated Heuristic Design High-Level Source Code Optimization Modeling Bridging Language

Ask PDF