Source-linked AI summary
From Search to Signal: Online Post-Training in Automatic Heuristic Design
Yilun Yuan, Tianyu Zhou, Zhenzhou Tang
TL;DR
In online AHD, evaluated candidates update both search state and the generator, but validity and performance alone do not specify learner credit. The paper compares reward mappings within a fixed CALM loop and finds live-search gains over Frozen without a uniformly dominant mapping.
Problem
Method
Results
All trained conditions improve live search over Frozen at the common horizon, but mappings trade validity, valid-only quality, signal density, and coverage without a uniform winner.
Source: §7 · p. 7Takeaways & Limitations
Archive admission, positive advantage, and strict discovery measure different outcomes, so online AHD should be evaluated as a search-to-signal system.
Source: §7 · p. 7Conclusions are limited to one co-evolutionary host; multi-seed efficacy covers TSP and one 7B model, while other task–model cells provide mechanism breadth only.
Source: §7 · p. 7
Abstract
from arXiv · showhide
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.
1 Introduction
AHD systems use evaluation feedback to refine executable heuristics, but frozen generators adapt only through external search state. This section frames online post-training as a separate learner-credit pathway and tests reward mappings within a fixed CALM search-and-learning loop.
1 Introduction
- Frozen generators adapt through external state, leaving recurring failures and task-specific design patterns unable to accumulate in generator parameters.External state includes retained programs, reflections, populations, and prompts.Source: §1 · p. 1
- Within-search updating lets feedback alter future proposals through both model parameters and external memory, while search and learning can assign different value to the same candidate.Search may retain a candidate in the population; learning assigns credit to the tokens that produced it.Source: §1 · p. 1
- RLVR verification reports outcomes, but reward construction and GRPO normalization determine which distinctions in validity, failure type, score, and context affect learning.Group-shared offsets disappear under normalization, while ordering, gating, and non-affine reward spacing can change the update.Source: §1 · p. 1
- CALM isolates record-to-reward mapping by holding search, context construction, evaluation, grouping, normalization, and optimization fixed while varying the learner-reward mapping.The contributions separate search-state updates from learner credit and layer attribution across checkpoint, search-state, and resource-allocation effects.Source: §1 · pp. 1–2
- At a common 500-group horizon, every trained condition improves live search over Frozen, but reward mappings trade validity, valid-only quality, contextual improvement yield, and coverage.Tail-weighted remains better than the initial model after population reset in all three seeds, but its relation to its own live endpoint is mixed; Native and Factorized each beat timing-derived Frozen-search anchors in only one of three seeds.Source: §1 · p. 2
2 Related Work
The related work spans LLM-based heuristic search, training from search experience, and verifiable-feedback reward design. This paper places its comparison at the intersection: online adaptation within a fixed search procedure and GRPO estimator.
Search Procedures for LLM-Based AHD
- LLM-based AHD methods vary in retained search state and prompting, but the surveyed systems improve candidates without updating the generator during a run.Examples include program databases, evolutionary search, reflection, and search trees.Source: Search Procedures for LLM-Based AHD · p. 2
Model Adaptation from Search Experience
- Prior adaptation work includes offline training from collected AHD data and online updates during search; the present intervention fixes CALM’s search transition, generator role, and GRPO normalizer.EvoTune and CALM are online-adaptation precedents, while other systems train selectors, advisors, or tool-using policies.Source: Model Adaptation from Search Experience · p. 2
Verifiable Feedback and Reward Construction
- Executable outcomes still require a reward function, and GRPO’s prompt-relative advantages make reward construction and group normalization jointly determine learner credit.The paper asks which evaluation-record distinctions survive when search and the GRPO estimator are fixed.Source: Verifiable Feedback and Reward… · p. 2
3 Search-Coupled Online AHD
The paper models online AHD as two consumers of the same evaluated candidate stream: a fixed search transition and a learner-reward pathway. It varies reward construction while controlling the rest of the loop and audits the signals that reach learning.
3 Search-Coupled Online AHD
- The prompt is constructed from the pre-generation population state and sampled operator and base heuristics, conditioning the candidate group.Candidates are then generated from the current policy and evaluated for validity or typed failure and, when valid, task score.Source: §3 · pp. 2–3
- Each evaluated group updates the search state and supplies learner rewards, while the intervention varies only the reward mapping.Search, group normalization, and optimization are held fixed.Source: Figure 1 · p. 3, §3 · p. 3
- The same records feed CALM’s fixed population transition and a learner path from reward components through scalar rewards and normalized advantages to optimization.The paper treats evaluation outcomes and search events as evidence that become learner credit only through the reward mapping.Source: §3 · p. 3
- A group-shared additive reward offset is eliminated by normalization, while ordering, gating, ties, and non-affine spacing can change the effective signal.The authors audit normalized advantages and matched parameter updates rather than assuming distinct reward formulas imply distinct learning signals.Source: §3 · p. 3
4 Reward Constructions
Four reward constructions are embedded in the same CALM loop, with search, evaluation, grouping, and GRPO held fixed. They encode different distinctions in candidate validity, quality, archive context, and estimated search exposure.
4 Reward Constructions
- The comparison treats Frozen CALM as the no-update control rather than a fifth reward construction.The mappings are compared with search, evaluation, grouping, and GRPO held fixed.Source: §4 · p. 3, Table 1 · p. 4
- Native CALM combines typed-failure severity, validity, and context-relative quality in a piecewise reward scale.Valid initialization candidates receive zero; improvements, equalities, degradations, and prompt-base candidates receive distinct treatment.Source: §4 · p. 3
- Factorized Validity–Quality combines a validity signal with an RMS-scaled quality signal before one joint GRPO normalization.It is a scalar reward construction, not a separately normalized multi-reward objective.Source: §4 · pp. 3–4
- Pre-Generation Tail Weighting ranks typed failures below valid candidates, rewards novelty relative to the pre-generation archive and group repetition, and retains positive frontier-gap magnitude.Its group-concentration rule follows TTT-Discover (Yuksekgonul et al. 2026), but not that method’s PUCT or leave-one-out objective.Source: §4 · p. 4, Table 1 · p. 4
- Search-Exposure Residual is a mechanism probe that estimates one-step exposure through CALM’s parent-selection routes and removes the immediate-quality direction.It tests whether the fixed parent-selection rule supplies information beyond immediate quality.Source: §4 · p. 4, Table 1 · p. 4
5 Controlled Evaluation
The evaluation holds the CALM search loop and update opportunities controlled while tracing how record-to-reward mappings affect learner signals, proposals, checkpoints, and search. It distinguishes proposal validity, conditional quality, contextual improvement, and search quality, with timing-derived frozen-search budgets used as anchors rather than exact time matches.
Scope
- The complete live cohort uses TSP with Qwen2.5-7B-Instruct, three seeds, 500 groups, and Native, Factorized, Tail-weighted, and Frozen conditions.Shared-record audits cover four tasks; matched updates span two tasks and two 7B model families, with one seed per cell.Source: §5 · p. 4
Implementation
- Each online condition receives one optimizer opportunity per group, but differing completion lengths mean live runs do not have equal training-token budgets.Prompts and completions are capped at 2,048 and 1,024 tokens, respectively, within a 4,096-token context.Source: §5 · p. 4
Attribution protocol
- Shared-record replays test normalized-advantage differences, matched updates test checkpoint signal propagation, and reset-population runs test subsequent search without further training.Frozen runs retain the initial model; timing-derived group budgets anchor the resource comparison, whose prefixes lack timestamps and therefore are not exact realized-time matches.Source: §5 · pp. 4–5
Metrics
- Proposal credit is compared with candidate-class prevalence and positive-advantage mass, while archive admission and uniqueness are reported as separate diagnostics.Validity requires a finite task score; ImproveYield describes the contextual proposal stream, and uniqueness measures are coverage proxies rather than semantic diversity.Source: §5 · p. 5
- Search quality uses final best and trajectory AUC for equal-horizon runs, but final best is primary at preregistered unequal resource-anchor horizons.AUC is descriptive only for unequal horizons.Source: §5 · p. 5
6 Results
Across the three-seed TSP–Qwen live cohort, all trained mappings improve final best and AUC over Frozen, while differing in validity, valid-only performance, and contextual improvement yield. Signal audits, restart tests, and timing-derived Frozen-search comparisons qualify what those live gains establish.
Signal-Propagation Analysis
- In 387 groups, comparator and frontier reward offsets vanish under normalization; among 422 midrank groups, score novelty and response repetition reorder 37.7% and 4.7%.Across 12 audited groups, Native and Factorized are nearly equivalent on OBP and OP but separate on TSP and CVRP; matched updates and fixed-context tests show mechanism separation, not efficacy.Source: Signal-Propagation Analysis · pp. 5–6
Live-Search Results
- +0.0240/+0.0214, +0.0289/+0.0238, and +0.0366/+0.0294 are the final-best/AUC gains over Frozen for Native, Factorized, and Tail-weighted, respectively.Every trained condition improves both metrics in every matched seed at 500 groups; Native and Factorized remain ahead in each seed when truncated to Frozen's same-seed evaluator-call count.Source: Figure 3 · p. 6, Live-Search Results · p. 7
Proposal-Stream Analysis
- Frozen yields 60.85% valid completions, versus 93.92% for Native, 95.60% for Factorized, and 85.12% for Tail-weighted.Every trained condition improves valid-only performance over Frozen in all seeds, while Native has the best trained-condition mean; Factorized and Tail-weighted raise contextual improvement yield relative to Native but reduce valid-only performance.Source: Proposal-Stream Analysis · p. 6
- Injection raises validity over Frozen by 86.73, 91.75, and 58.13 points for Native, Factorized, and Tail-weighted, respectively.The feasibility gain is operator dependent and does not alone establish stronger algorithmic reasoning.Source: Proposal-Stream Analysis · p. 6
Credit–Utility Alignment Analysis
- Valid non-improvers make up 90.93%, 92.00%, and 80.48% of Native, Factorized, and Tail-weighted candidates, while receiving 83.30%, 83.50%, and 85.51% of positive advantage mass.Parent- and frontier-improving candidates are enriched 2.83–6.72× relative to prevalence; group centering still assigns positive advantage within any nonconstant group, so that credit is not shown to be erroneous or harmful.Source: Credit–Utility Alignment Analysis · pp. 6–7
Live-Search Results
- No trained mapping uniformly dominates Native, and exact-response and prompt uniqueness changes vary by mapping and are coverage proxies, not semantic diversity measures.Single-seed live comparisons on remaining task–model cells are directionally mixed; in a separate held-out TSP cohort, Factorized has lower mean optimality gap at all three sizes, but seed ranges overlap.Source: Live-Search Results · p. 7
Checkpoint and Search-State Attribution Analysis
- After reset, Tail-weighted remains above the initial Frozen model in all three seeds, but its comparison with its own live parent has mixed final-score directions.Factorized has no consistent post-reset advantage over Native; the live endpoint reflects accumulated search state and its interaction with online updates.Source: Checkpoint and Search-State… · p. 7
- Under timing-derived Frozen-search budgets, online endpoint differences are mixed, although Native and Factorized improve validity and valid-only performance in every paired seed.These are budget anchors rather than exact time matches, and online updating does not reliably dominate additional Frozen search at the endpoint.Source: Checkpoint and Search-State… · p. 7
7 Discussion, Limitations, and Conclusion
At the common horizon, every trained condition improves live search over Frozen, but reward mappings trade off proposal properties without a uniform winner. The paper distinguishes learner credit from search-state updates and limits its conclusions to one co-evolutionary host.
7 Discussion, Limitations, and Conclusion
- At the common horizon, every trained condition improves live search over Frozen, but reward mappings trade validity, valid-only quality, signal density, and coverage.Tail-weighted retains an advantage over the initial model after reset without consistently reproducing its live endpoint; timing-derived anchors show no consistent endpoint advantage over additional Frozen search.Source: §7 · p. 7
- Search admission, positive advantage, and strict discovery measure different outcomes; the residual construction survives normalization but demonstrates mechanism rather than efficacy.Reward construction is a testable component of search-coupled AHD, so tracing search-state and learner paths helps distinguish parameter changes, reset-search behavior, and live gains.Source: §7 · p. 7
- Conclusions are limited to one co-evolutionary host; only TSP with one 7B model has multi-seed efficacy coverage, while other task–model cells provide mechanism breadth.Four-sample groups amplify ties, completion rewards cannot separate rationale from code, and coverage hashes do not measure semantic diversity.Source: §7 · p. 7
A Evidence Scope and Claim Hierarchy
- The three-seed TSP–Qwen cohort is the only full multi-seed live efficacy study; other task/model cells support mechanism or directional breadth, not pooled estimates.The evidence layers have different statistical units and claim scopes; no result is pooled as though they estimated one quantity.Source: A Evidence Scope and Claim Hierarchy · p. 10
Native CALM branch semantics
- Native CALM assigns typed invalid rewards, then gives 1 + δ for improvement, zero for equality, and −3δ/8 for degradation.A candidate identified as a prompt base receives −3/5, making the native reward context-relative and nonlinear rather than raw task performance.Source: Native CALM branch semantics · p. 10
Factorized Validity–Quality
- Factorized Validity–Quality combines typed validity and RMS-scaled eligible-valid score gaps into one reward, followed by joint GRPO normalization.Its quality channel is zero when the RMS is numerically zero, there is no initialization comparator, or no valid candidate is eligible.Source: Factorized Validity–Quality · p. 10
Pre-Generation Tail Weighting
- Tail weighting ranks typed failures below valid candidates and scores valid-candidate novelty against the pre-generation archive and exact group repetitions.It retains positive frontier-gap magnitude; a performance-monotone threshold tier with the same within-tier order is a learner no-op after midranking, so the final construction uses a numeric gap.Source: Pre-Generation Tail Weighting · p. 10, Implemented learner equivalence · p. 11
Search-Exposure Residual
- The search-exposure probe inserts a candidate into the frozen pre-generation population, measures parent-route exposure, and removes the immediate-quality direction.The residual is not normalized to unit RMS; its denominator bounds its RMS below 1/2, and it is combined with validity and quality before group normalization.Source: Search-Exposure Residual · p. 10
C Implementation and Reproducibility
The implementation pins the CALM source revision and records formal-run provenance, while the reported hardware description is limited to accelerator class and memory.
Source boundary and software
- The intervention runner executes native evaluation and population transitions before replacing only learner-facing rewards, with source, configuration, adapter, and record checksums logged.The source boundary is pinned to CALM revision ecb3cadcf4b0.Source: Source boundary and software · p. 11
Hardware
- The CALM evaluator is CPU-intensive, but hardware identifiers and runtime snapshots are not reported; accelerator class and memory describe the resource context.Historical shared-host CPU contention observations are not used as model-speed evidence.Source: Hardware · p. 11
Final experimental parameters
Run seeds are assigned to Python random, NumPy, Hugging Face/TRL, and LoRA initialization, while CUDA, vLLM, and Ray are not claimed to be bitwise deterministic.
Final experimental parameters
- Independent run seed is the statistical unit because CUDA, vLLM, and Ray execution are not claimed to be bitwise deterministic.Records retain outcomes, scores, prompt/operator context, reward components, normalized advantages, archive events, response hashes, and pre-generation frontiers.Source: Final experimental parameters · p. 11
Task and model breadth
Across the task–model breadth cells, online updating raises validity relative to Frozen, but final-best and AUC directions vary. Operator-level validity gains do not reliably translate into parent or frontier improvement, and archive admission is much more common than strict frontier progress.
Task and model breadth
- Online updating raises validity in all six trained task–model cells relative to Frozen, but final-best and AUC directions vary.The single-seed breadth results support separating feasibility learning from downstream search efficacy, not a cross-task superiority claim.Source: Task and model breadth · pp. 11–12
Operators and proposal outcomes
- Native and Factorized raise every operator’s validity in all three matched seeds, but Tail-weighted gains less and validity does not monotonically translate to parent or frontier improvement.Mean validity gains are 19.1–86.7 percentage points for Native, 19.5–91.7 for Factorized, and 14.2–58.1 for Tail-weighted.Source: Operators and proposal outcomes · p. 12
Population admission is not learner credit
- Frontier precision among archive admissions is 0.37–4.95% for Native/Factorized/Frozen and 0.95–2.14% for Tail-weighted, as CALM’s population also supports coverage and later parent construction.Archive admission therefore is not equivalent to immediate frontier improvement or positive learner credit.Source: Population admission is not learner… · p. 12
Credit allocation and base rates
The analyses distinguish the volume of positive learner credit from immediate search progress, then examine whether checkpoint and live-search results persist across resets and evaluation settings. They report mixed collapse-centered behavior, useful Tail-weighted checkpoint behavior beyond the initial model, and limits on resource-matched comparisons.
Credit allocation and base rates
- Valid non-improvers receive 83.3%, 83.5%, and 85.5% of positive advantage mass under Native, Factorized, and Tail-weighted, while immediate parent and strict-frontier improvements are enriched relative to their frequency.The corresponding mass-to-prevalence ratios are 5.19, 4.34, and 2.83 for parent improvements and 6.72, 6.10, and 3.98 for strict-frontier candidates; the mass distribution quantifies peer-relative credit, not immediate search progress.Source: Credit allocation and base rates · pp. 12–13
Collapse and exact recurrence
- Collapse-centered validity and valid-only performance changes are mixed and high-variance observational findings because collapse timing depends on prior trajectory; recurrence counts exact replay, not semantic diversity.Within 25 later groups, positive-minus-nonpositive recurrence differences vary by reward construction.Source: Collapse and exact recurrence · p. 13
Live versus population-reset search
- Tail-weighted restart beats initial Frozen by +0.0054, +0.0075, and +0.0444 (mean +0.0191), but averages −0.0175 versus its live endpoint.Restart loads the final adapter, resets the population, and uses zero optimizer steps; the live endpoint also includes accumulated search-state effects.Source: Live versus population-reset search · p. 13
Held-out TSP sizes
- Held-out TSP evaluation scores selected final heuristic artifacts at available sizes, separately from live proposal validity and fixed-context checkpoint behavior.The final heuristic is selected using the training evaluator.Source: Held-out TSP sizes · p. 14
Timing-derived Frozen-search anchors
- Native and Factorized average −0.0113 and +0.0035 online-minus-Frozen final-best deltas, but the timing-derived group-budget anchors are not exact realized-time matches.Full-run timing gaps and unavailable timestamps for shorter prefixes limit the resource comparison; unequal-horizon AUC is not used causally.Source: Timing-derived Frozen-search anchors · p. 14
G Common-Context Executable Checkpoint Probe
- In the common-context probe, Factorized leads validity and improvement in seed 3407 but has the lowest validity in seed 1926000, yielding no stable two-seed reward ordering.The probe uses a common bank of 64 prompts and two checkpoint seeds; its fixed prompt bank can be harder than endogenous live contexts.Source: G Common-Context Executable Checkpoint… · p. 14
H API-Served Frozen-System Reference
The completed API-served frozen-system reference provides a descriptive point of comparison under its own CALM protocol, not a model-only baseline. Supplementary material documents the reference’s scope, excluded incomplete runs, and the provenance and limits of the reproduction package.
H API-Served Frozen-System Reference
- The API reference uses different prompt grouping, latency, provider, and model, and its provider-reported model name was not independently verified.It is reported as a system reference under its own CALM protocol, not as a causal model-only baseline or claim against an official proprietary service.Source: H API-Served Frozen-System Reference · pp. 14–15
I Provenance, Exclusions, and Reproduction Map
- Supplementary visuals cover endogenous stage-wise proposals, single-seed breadth, observational diagnostic panels, restart search, and held-out artifacts; the captions state scope rather than comparative outcomes.The diagnostic panels explicitly do not identify causal effects of individual search operators.Source: Figure 5 · p. 15, Figure 6 · p. 16, Figure 7 · p. 17
H API-Served Frozen-System Reference
- At 2,000 completions, the API-served frozen reference has mean validity 82.45% and final best −6.2188; the comparison is descriptive, not model-isolating.The local conditions use four-way group generation and trained arms also update parameters, unlike the API reference.Source: H API-Served Frozen-System Reference · p. 15
- DeepSeek-v4-flash runs stopped at 845–1,281 completions and DeepSeek-v4-pro and GPT-5.5 runs were incomplete, so none enter efficacy tables or system rankings.No partial endpoint or best-so-far value from those runs is used to rank systems.Source: H API-Served Frozen-System Reference · p. 15
I Provenance, Exclusions, and Reproduction Map
- The source package contains manuscript assets but not experiment code or raw records; retained configurations, records, scripts, summaries, and environment files document study materials.Adapter checkpoints, model weights, credentials, and raw provider responses are excluded.Source: I Provenance, Exclusions, and… · p. 15
- Tables 9–11 describe timing-derived group budgets, a common-context executable checkpoint probe, and repeated-seed API-reference rows, respectively.The timing-derived budgets are not exact realized-time matches; the API rows are repeated seeds, not competing methods.Source: Table 9 · p. 16, Table 10 · p. 16, Table 11 · p. 17