Compute Allocation in Evolutionary Search: From Depth–Breadth to Multi-Armed Bandits
Sixue Xing 1 Haoyu He 2 Kerui Wu 3 Zhuo Yang 4 Haozheng Luo 5 Tianfan Fu 6, 7 Aarthy Nagarajan 1 1 University of Notre Dame 2 Northeastern University 3 University of Massachusetts Amherst 4 Southeast University 5 Northwestern University 6 Nanjing University 7 Shanghai Artificial Intelligence Laboratory · 2026
Read Compute Allocation in Evolutionary Search: From Depth–Breadth to Multi-Armed Bandits by Sixue Xing 1 Haoyu He 2 Kerui Wu 3 Zhuo Yang 4 Haozheng Luo 5 Tianfan Fu 6, 7 Aarthy Nagarajan 1 1 University of Notre Dame 2 Northeastern University 3 University of Massachusetts Amherst 4 Southeast University 5 Northwestern University 6 Nanjing University 7 Shanghai Artificial Intelligence Laboratory (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29268.txt.
Introduction
Sixue Xing asks how a fixed budget of language-model calls should be split across runs. Current systems report only the best of many runs, leaving reliability unclear. Sweeping depth and breadth over five models and three tasks yields two patterns. The first is a fitness-compute envelope along which capability order largely collapses. The second is a bilinear depth-breadth fit with task-specific interaction. Their BaSE method splits calls across parallel runs via a multi-armed bandit, improving mean fitness by about twelve percent over baseline.
Catalog record
| CREATOR | Sixue Xing 1 Haoyu He 2 Kerui Wu 3 Zhuo Yang 4 Haozheng Luo 5 Tianfan Fu 6, 7 Aarthy Nagarajan 1 1 University of Notre Dame 2 Northeastern University 3 University of Massachusetts Amherst 4 Southeast University 5 Northwestern University 6 Nanjing University 7 Shanghai Artificial Intelligence Laboratory |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81319 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29268
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compute Allocation in Evolutionary Search: From Depth–Breadth to Multi-Armed Bandits Sixue Xing 1 Haoyu He 2 Kerui Wu 3 Zhuo Yang 4 Haozheng Luo 5 Tianfan Fu 6, 7 Aarthy Nagarajan 1 1 University of Notre Dame 2 Northeastern University 3 University of Massachusetts Amherst 4 Southeast University 5 Northwestern University 6 Nanjing University 7 Shanghai Artificial Intelligence Laboratory Abstract LLM-guided evolutionary search (Evolve systems) has reached state-of-the-art results on mathematical and combinatorial tasks, yet most existing systems report only the best of many runs and leave the run-to-run distribution undocumented. We ask how a fixed budget of LLM calls should be allocated, and how reliably a single run reaches the reported numbers. Sweeping the depth–breadth grid over five models and three tasks, we identify two empirical regularities: a fitness–compute envelope along which capability ordering largely collapses on effective FLOPs, and a bilinear depth–breadth fit with task-specific interaction; both are gated by model–task capability. Motivated by these regularities, we propose BaSE (Bandit-based Self-Evolving), a multi-armed bandit that allocates LLM calls across parallel trajectories. Without changing the model, prompt, or evaluator, BaSE improves mean fitness by 12.3% over the strongest island-protocol baseline across 8 (model, task) cells, with the largest gains on high-variance settings: a reliability gain from allocation alone. The code is available at: https://github.com/keruiwu/self-evolving-allocation . 1 Introduction Large language models are increasingly used as mutation engines for evolutionary search: given a candidate program, a frozen LLM proposes variants; a deterministic evaluator scores them; the best variant seeds the next round ( 33 ; 32 ) . The resulting Evolve systems ( 23 ; 41 ; 3 ; 10 ) have produced state-of-the-art results across mathematical discovery, combinatorial optimization, and algorithm design. However, the headline numbers *Evolve systems report are systematically incomparable: FunSearch reports a 4-of-140 hit rate ( 33 ) ; CodeEvolve displays “only the best” ( 3 ) ; AlphaEvolve reports a single number on the n{=}26 Circle Packing benchmark ( 32 ) . Reported per-run cost spans more than two orders of magnitude, from \sim 150 LLM calls in ShinkaEvolve ( 23 ) to the 204,800 candidates ThetaEvolve processes in a single run ( 41 ) . Figure 1 plots these reports on a common axis: each point is a single hand-picked configuration, and the dominant convention is to report only the best of an unspecified number of runs. Few systems report the run-to-run distribution behind these headline numbers. Combined with the order-of-magnitude variation in reported computational cost, this makes the numbers an unreliable guide to single-run performance under realistic deployment settings: existing reports characterize what is achievable on a favorable run, not what a practitioner should expect at a finite computational cost. Figure 1: Cost–performance frontier on n{=}26 Circle Packing (CP). The expected performance is shaped by multiple design choices. A stronger base model can generate better mutations; a more informative prompt can guide the search toward more useful edits; and, importantly, allocation determines how the evolutionary process balances exploration and exploitation. This allocation effect is orthogonal to model and prompt quality, and remains meaningful once the model, prompt, and evaluator are fixed. Better allocation can improve expected outcomes by avoiding both premature commitment to weak trajectories and excessive breadth without refinement. While *Evolve systems are often described as iterative loops that continue until progress saturates, practical deployments must operate under explicit resource constraints, such as a fixed number of model calls, a limited compute allocation, or a bounded experimental campaign. This motivates a controlled study of expected performance and reliability in LLM-guided evolutionary search. We adopt the fixed-budget perspective ( 19 ) from classical evolutionary computation and bring it to LLM-guided evolution. To this end, we conduct the first empirical study of cost allocation in LLM-guided evolutionary search, characterizing how a fixed number of LLM call should be spent, and use the resulting picture to ask whether allocation can be precomputed offline or must be discovered online. In summary, our contributions are listed below: 1. Proposed the first systematic empirical measurement of fixed-budget allocation between exploration and exploitation in LLM-guided evolutionary search. 2. Identified two regularities: (i) a performance–compute envelope of attainable fitness against effective FLOPs, along which capability ordering largely collapses among capable models; and (ii) a parametric depth–breadth regularity characterizing each model-task cell. 3. Designed an adaptive bandit allocator ( BaSE ) over parallel evolutionary trajectories, improving best mean fitness by 12.3% on average over the strongest island-protocol baseline across 8 (model, task) cells — this is not a model improvement, nor a prompt improvement, but an allocation improvement. 2 Related Work LLM-Guided Evolutionary Search. FunSearch ( 33 ) introduced LLMs as mutation operators in evolutionary program synthesis, and AlphaEvolve ( 32 ) scaled the paradigm to state-of-the-art results. *Evolve variants vary individual axes — sample efficiency ( 23 ) , test-time RL ( 41 ) , open-source islands — with adjacent work on code, architectures, and prompts ( 26 ; 11 ; 44 ) ; all leave population size and generation count hand-set. ThetaEvolve only notes qualitatively that small databases progress faster early but large ones win at scale ( 41 ) , and Population-Evolve sweeps population size without holding total budget fixed ( 45 ) . Adjacent allocation work routes compute between islands ( 10 ) , compares evolution to best-of-N and sequential revision ( 25 ) , or focuses on parent sampling ( 32 ; 23 ) and combination operators ( 22 ; 28 ) . The closest precedent, ShinkaEvolve ( 23 ) , uses a bandit to ensemble models at the final phase; we instead target the within-run depth–breadth split. Compute Allocation. Inference-scaling work allocates test-time compute ( 36 ; 9 ; 43 ; 12 ) , with breadth-vs-depth studies on single-query reasoning and tree search ( 34 ; 42 ; 17 ; 29 ) reporting empirical, regime-dependent curves; none targets population-based evolution with parent-conditioned mutation. Our online allocator draws on multi-armed bandits ( 5 ; 24 ) and fixed-budget best-arm identification ( 4 ; 21 ) , with precedents in hyperparameter search ( 27 ) , prompt selection ( 35 ) , MCTS expansion ( 17 ) , island routing ( 10 ) , and code repair ( 38 ) , all of which assume adaptive allocation helps. Classical EA contributes optimal-population-under-fixed-compute analyses ( 31 ; 8 ) , offspring-size theory ( 18 ; 13 ; 14 ; 7 ) , and the fixed-budget framing ( 19 ; 20 ) ; all assume random mutation, whereas LLM mutation carries code priors and discrete attractors that break i.i.d. mean-field assumptions, so we characterize the surface empirically. 3 Problem Formulation Self-Evolving. In high level, we formulate self-evolution as an iterative optimization process under a fixed inference budget of C LLM calls. Specifically, as described in Algorithm 1 , a Self-Evolve system repeatedly generates a candidate response, evaluates its quality, and refines the proposed solution based on historical response-evaluation pairs. Algorithm 1 Self-Evolving Process 1: Task q , base LLM f , prompt generator h , budget (number of LLM calls) C 2: for c=1,\dots,C do 3: \mathrm{prompt}\leftarrow h\left(q,\left(\mathrm{response}^{(j)},\mathrm{score}^{(j)}\right)_{j\in[c]}\right) 4: \mathrm{response}^{(c+1)}\leftarrow f(\mathrm{prompt}) 5: \mathrm{score}^{(c+1)}\leftarrow\mathrm{Eval}\left(q,\mathrm{response}^{(c+1)}\right) 6: end for 7: j^{*}\leftarrow\arg\max_{j\in[C]}\mathrm{score}^{(j)} 8: return \mathrm{response}^{(j^{*})} The key design question in this process is the