Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

Researchers propose BaSE, a multi-armed bandit algorithm that optimizes how large language models allocate computational resources during evolutionary search tasks. By dynamically distributing LLM calls across parallel trajectories, BaSE improves mean fitness by 12.3% over existing baselines while addressing the reliability gap between reported best-case and typical run performance.

This research tackles a critical but underexplored challenge in AI systems: computational allocation efficiency. While evolutionary search guided by LLMs has achieved impressive results on mathematical and combinatorial problems, the field has largely reported cherry-picked best outcomes without documenting the consistency of single runs. The authors expose this reproducibility gap and propose a solution grounded in two empirical regularities they discovered through systematic experiments across multiple models and tasks.

The work builds on growing recognition that raw model capability matters less than how intelligently researchers deploy it. Their key insight—that a fitness-compute envelope exists where different model-task pairs collapse onto effective FLOPs—suggests fundamental scaling relationships worth understanding. The bilinear depth-breadth interaction finding further refines this, showing that optimal search strategies vary by task characteristics.

BaSE leverages multi-armed bandit theory to dynamically rebalance computational budget allocation, treating different search trajectories as exploration-exploitation problems. The 12.3% improvement in mean fitness, with particularly strong gains on high-variance settings, demonstrates that algorithmic allocation outperforms static approaches. This matters because it improves reliability without requiring model changes, prompt engineering, or new evaluation methods—pure architectural efficiency.

For the AI systems community, this validates that better search procedures can rival or exceed model scaling in cost-effectiveness. The framework opens avenues for studying how compute should flow through hierarchical AI systems. Future work likely explores whether these allocation principles transfer across different task domains or whether task-specific tuning remains necessary.

• →BaSE achieves 12.3% mean fitness improvement through dynamic LLM call allocation across parallel search trajectories.
• →Empirical analysis reveals a fitness-compute envelope where capability ordering largely collapses onto effective FLOPs.
• →Multi-armed bandit allocation improves reliability on high-variance tasks without modifying model, prompt, or evaluator.
• →Existing evolutionary search systems report only best-case outcomes, masking run-to-run variability and reproducibility gaps.
• →Task-specific depth-breadth interactions suggest optimal search strategy depends on problem characteristics, not just model capability.