Evaluation of search strategies changes with budget and task
Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search
Computation and LanguageArtificial IntelligenceMachine Learning
Summary
Finding the best way to search for solutions using large language models depends on how you spend your time on trying different starting points (seeds) and how many times you improve each one (iterations). The authors show that just testing one fixed setup can be misleading because different ways to balance seeds and iterations work better depending on the problem and total time allowed. They tested three search methods on five problems with many settings and found rankings of these methods can change a lot. They suggest a better way to report results by showing performance across different numbers of seeds and iterations.
What this means in practice
- •For machine learning engineers: Choose how to allocate computing budget between more initial runs or longer improvements when using evolutionary search with language models.
- •For software optimization teams: Improve software tuning by selecting search strategies based on task-specific budget settings shown by seeds-iterations performance tradeoffs.
Authors
Tal Oved, Roi Pony, Oshri Naparstek, Udi Barzelay
Abstract
LLM-driven evolutionary search finds programs by launching seeds and iterating each one. Papers report a single budget setting, usually one seed run for a fixed number of iterations, and rank methods from that one point. We show this is not enough. We evaluate three evolutionary search strategies on five optimization tasks, commonly used by papers in the genre to report results. We run the analysis over a full grid of seeds and iterations. Our findings suggest that the best way to split a fixed budget between more seeds (width) and more iterations (depth) changes with the strategy, the task, and the total budget. Furthermore, we observe that the ranking of strategies also changes with the budget. On one task the strategy that looks worst at one seed is best at forty seeds. On another the best number of iterations is well below the value common in practice, so extra depth wastes budget that more seeds would turn into score. We provide a measurement protocol that reports the seeds-by-iterations frontier and practical guidance for using it.