Technical Summary: Compute Allocation in Evolutionary Search

Problem Statement

Large Language Model (LLM)-guided evolutionary search systems (e.g., FunSearch, AlphaEvolve, CodeEvolve) have achieved state-of-the-art results in mathematical discovery and combinatorial optimization. However, existing literature predominantly reports the single best outcome from an unspecified number of runs, leaving the run-to-run distribution undocumented. Furthermore, reported computational costs vary by orders of magnitude, making it difficult to assess the reliability of a single run under a fixed budget.

The core problem addressed is compute allocation: given a fixed budget of LLM calls ($C$), how should this budget be distributed between depth (sequential refinement of a single trajectory) and breadth (parallel exploration of multiple trajectories)? Current systems often fix these hyperparameters (e.g., population size and generation count) without a systematic understanding of how the allocation affects expected performance and reliability.

Methodology

1. Empirical Characterization of Depth–Breadth Allocation

The authors conducted a systematic empirical study across three geometric optimization tasks (Circle Packing, MinMaxDist, Heilbronn Triangle) and four model sizes (Qwen3-1.7B to 14B, plus Llama-3.1-8B). They defined the allocation problem as splitting the budget $C$ into $T$ generations of $N$ parallel children ($C = T \times N$).

• Fitness–Compute Envelope: They analyzed the relationship between attainable fitness and effective FLOPs (accounting for model size and cache efficiency). They observed that while larger models lead at equal call counts, their performance ordering largely collapses when measured against effective FLOPs, provided the model-task pair is "capable."
• Depth–Breadth Regularity: They fitted a parametric bilinear model to the fitness landscape:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  where $V$ is the fitness. The interaction coefficient $c$ determines the geometry of the optimal allocation:
  • Corner Optima ($|c| \approx 0$): Tasks like Circle Packing exhibit broad plateaus where many allocations yield similar results, often favoring depth.
  • Interior Ridges ($c < 0$): Tasks like MinMaxDist exhibit a sharp ridge where a balanced mix of depth and breadth is required for optimal performance.
  • Capability Gating: These regularities only hold for models that have crossed a capability threshold for the specific task; weak models fail to exhibit structured depth–breadth trade-offs.

2. BaSE: Bandit-based Self-Evolving

Motivated by the high variance in run outcomes (where identical configurations produce widely different final fitness scores due to stochasticity in the LLM's mutation process), the authors proposed BaSE.

• Mechanism: BaSE treats the evolutionary search as a Multi-Armed Bandit (MAB) problem. Instead of committing the entire budget to a single trajectory (Greedy) or a fixed set of islands (Island protocol), BaSE maintains $K$ parallel trajectories.
• Adaptive Allocation: At each step, a bandit algorithm (UCB, EXP3.P, or Thompson Sampling) selects which trajectory to extend with the next LLM call. This dynamically routes compute away from stagnating runs toward promising ones.
• Orthogonality: BaSE does not alter the base model, the prompt, or the parent-sampling logic within a trajectory. It operates strictly at the level of cross-trajectory resource allocation.

Key Results

1. Empirical Regularities

• Capability Collapse: For capable models, the performance envelope is determined by effective FLOPs rather than model size alone.
• Task-Dependent Geometry: The optimal depth–breadth split is not universal; it depends on the task's "algorithmic family" (e.g., whether the solution requires a specific library like scipy or a specific analytic construction).
• Stochasticity: Even with fixed allocation, individual runs vary significantly. Some runs converge to high fitness, while others stagnate early due to locking onto a suboptimal algorithmic family.

2. Performance of BaSE

• Mean Fitness Improvement: Across 8 (model, task) cells, BaSE improved the mean best fitness by 12.3% over the strongest island-protocol baselines (e.g., OpenEvolve, CodeEvolve, ShinkaEvolve) without changing the model or prompt.
• Reliability Gains: The most significant gains were observed in high-variance settings. For example, on the Heilbronn Triangle task with Llama-3.1-8B, non-BaSE methods often failed to produce valid solutions (fitness $\approx 0$), while BaSE (Thompson Sampling) achieved a mean fitness of 0.4387.
• Sample Efficiency: BaSE reached target fitness thresholds significantly faster (fewer generations and FLOPs) than greedy or fixed-allocation baselines. For instance, on MinMaxDist, UCB reached a threshold of 0.95 in 92 generations, whereas the greedy baseline required 485.
• Ablation: Moderate arm-pool sizes ($K \in \{5, 10, 20\}$) provided the best trade-off between diversity and refinement depth.

Significance and Claims

The paper claims that compute allocation is a distinct and critical lever for improving LLM-guided evolutionary search, separate from model scaling or prompt engineering.

• Allocation vs. Engineering: The authors emphasize that their improvements are not due to better prompts or models. In fact, they note that some baselines (like ShinkaEvolve) achieved high scores on specific tasks partly due to prompt-induced hints (e.g., suggesting scipy.optimize), whereas BaSE achieves gains purely through adaptive resource routing.
• Reliability: The primary contribution is shifting the focus from "best-case" reporting to "expected" performance. BaSE provides a reliability gain, ensuring that a practitioner is less likely to waste a fixed budget on a trajectory that has already stagnated.
• Complementarity: BaSE is presented as complementary to existing within-run mechanisms (like parent sampling). It can be layered on top of existing protocols (Greedy, Island) to further improve performance, particularly in unstable or high-variance settings.

The work concludes that while model capability sets the ceiling for what is achievable, allocation governs how efficiently a method approaches that ceiling, and adaptive allocation via bandits is a robust strategy for finite-budget search.