# Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2605.29268 · HTML: https://mlsanity.com/paper/2605.29268/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Self-evolving LLM agents, one of 13 directions in Synthetic data and self-improvement for LLMs.
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 28 May 2026.

## Placed in

- Synthetic data and self-improvement for LLMs / [Self-evolving LLM agents](https://mlsanity.com/synth/self-evolving-llm-agents/)

## Builds on (most cited first, 13 of 13)

- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution](https://mlsanity.com/paper/2509.19349/) (2025)
- [ThetaEvolve: Test-time Learning on Open Problems](https://mlsanity.com/paper/2511.23473/) (2025)
- [Code Repair with LLMs gives an Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17503/) (2024)
- [CodeEvolve: an open source evolutionary coding agent for algorithmic discovery and optimization](https://mlsanity.com/paper/2510.14150/) (2025)
- [ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Compute](https://mlsanity.com/paper/2509.04475/) (2025)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [The Sequential Edge: Inverse-Entropy Voting Beats Parallel Self-Consistency at Matched Compute](https://mlsanity.com/paper/2511.02309/) (2025)
- [Population-Evolve: a Parallel Sampling and Evolutionary Method for LLM Math Reasoning](https://mlsanity.com/paper/2512.19081/) (2025)
- [Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs](https://mlsanity.com/paper/2602.09574/) (2026)
- [More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)](https://mlsanity.com/paper/2601.21522/) (2026)

## Built on by (most cited first, 4 of 4)

- [Automated Discovery Has No Universally Superior Harness](https://mlsanity.com/paper/2607.18235/) (2026)
- [Efficiency Matters in Autonomous Research](https://mlsanity.com/paper/2607.24647/) (2026)
- [Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility](https://mlsanity.com/paper/2607.26828/) (2026)
- [The Little Scientist: LLM Agent-Driven Discovery via the Scientific Method](https://mlsanity.com/paper/2608.16951/) (2026)

## Abstract (arXiv)

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 when measured in 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.