Large language models improve search with context-aware post training
From Search to Signal: Online Post-Training in Automatic Heuristic Design
Machine LearningArtificial Intelligence
Summary
Finding good problem-solving strategies automatically can be tricky and slow because many ideas have to be tested and improved. This paper looks at how small language models, which suggest these strategies, can learn and get better during the search process itself by using feedback about what works well. The authors explore different ways to turn performance feedback into learning signals, considering the context in which strategies were generated. Their experiments show how these online updates can make the models suggest better and more valid solutions, beyond just remembering what happened before.
What this means in practice
- •For software engineers: Enhance automated code optimization tools by enabling heuristic suggestions that adapt online using execution feedback to improve performance during development.
- •For optimization specialists: Improve algorithm design by integrating context-aware online learning methods to refine heuristics while searching for better solutions.
Authors
Yilun Yuan, Tianyu Zhou, Zhenzhou Tang
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.