Search papers, labs, and topics across Lattice.
This paper introduces a novel framework called Relay, which optimizes budget allocation in LLM-driven evolutionary searches by focusing on adaptive population handoff rather than individual query costs. The authors demonstrate that early performance in evolutionary trajectories is both informative and recoverable by cheaper models, leading to significant cost savings without sacrificing effectiveness. Empirical results show that Relay outperforms existing methods across multiple benchmarks, achieving the highest mean score in 11 out of 12 settings, thereby redefining how resources can be allocated in stateful evolutionary processes.
Cheap models can recover early evolutionary progress, enabling a shift in budget allocation that dramatically enhances LLM-driven algorithm discovery.
Large language model (LLM)-driven evolution has shown promise for program search and algorithm discovery, but relying on strong models throughout long evolutionary runs is costly. A natural alternative is to combine cheap and strong models under a fixed inference budget. However, existing approaches typically allocate models at the level of individual queries or mutation steps, overlooking that evolutionary search is \textit{stateful}: each generated candidate changes the population from which subsequent mutations are produced. We empirically analyze LLM-driven evolutionary trajectories and find that search progress is strongly front-loaded, early trajectory performance is informative but noisy, and cheap models recover much of the early progress achieved by strong models at lower cost. Motivated by these findings, we propose \textbf{\model}, a training-free framework that shifts budget allocation from individual calls to evolving populations through adaptive \textit{population handoff}. A cheap model explores multiple trajectories in short blocks allocated by a bandit scheduler. Relay Gain, defined as the marginal improvement of a compact, quality-diverse candidate bank constructed for handoff, serves as the scheduler reward and determines when to hand off. The curated candidates initialize a shared strong model population for refinement. Across four benchmarks and three budgets, \model achieves the highest mean score in 11 of 12 settings, outperforming competitive baselines. Our results suggest that in stateful search, budget allocation should be organized around the population, not the individual call.
CMU ML