Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits
On the map: Synthetic data and self-improvement for LLMs → Self-evolving LLM agents
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.
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.
Builds on
13 of 36 references.
References · 13
- 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,986
- 2016Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimizationcited by 699
- 2015Illuminating search spaces by mapping elitescited by 425
- 2025ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolutioncited by 174
- 2025ThetaEvolve: Test-time Learning on Open Problemscited by 64
- 2024Code Repair with LLMs gives an Exploration-Exploitation Tradeoffcited by 51
- 2025CodeEvolve: an open source evolutionary coding agent for algorithmic discovery and optimizationcited by 44
- 2025ParaThinker: Native Parallel Thinking as a New Paradigm to Scale LLM Test-time Computecited by 38
- 2024Efficient Prompt Optimization Through the Lens of Best Arm Identificationcited by 37
- 2025The Sequential Edge: Inverse-Entropy Voting Beats Parallel Self-Consistency at Matched Computecited by 11
- 2025Population-Evolve: a Parallel Sampling and Evolutionary Method for LLM Math Reasoningcited by 6
- 2026Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMscited by 4
Built on by
Citing papers per year: 2026: 4.
4 papers.
- 2026The Little Scientist: LLM Agent-Driven Discovery via the Scientific Method16 Aug 2026
- 2026Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility29 Jul 2026
- 2026Efficiency Matters in Autonomous Research27 Jul 2026
- 2026Automated Discovery Has No Universally Superior Harness20 Jul 2026
Similar, not cited
Close in wording, no citation either way
- 2026Understanding Evolution Strategies for LLM Reasoning: Broader Reasoning Coverage than GRPO
- 2025Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning
- 2026EPOCH: Coverage-Aware Evolution with Experiential Preference Optimization for LLM-based Automated Heuristic Design
- 2026What Makes an LLM a Good Optimizer? A Trajectory Analysis of LLM-Guided Evolutionary Search
- 2026Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search
- 2026Beyond the Capability Boundary: Zeroth-Order Optimization for Self-Evolving LLM Agents
- 2026Duel-Evolve: Reward-Free Test-Time Scaling via LLM Self-Preferences
- 2024Model Swarms: Collaborative Search to Adapt LLM Experts via Swarm Intelligence