PaperlayerView exact revision on arXiv

Source-linked AI summary

EvoAlloc: A Self-Evolving Resource Allocation Agent for Efficient Program Evolution

Yanning Dai, Yuhui Wang, Nanbo Li, Wenyi Wang, Jürgen Schmidhuber

arXiv:2610.12086v1cs.AI

TL;DR

Expensive evaluation makes resource allocation central to LLM-based program evolution, but existing approaches typically keep allocation strategies fixed during search. EvoAlloc revises its strategy from accumulated search outcomes and uses counterfactual exploration to expose selected skipped candidates. Across coding and agent-harness benchmarks, it uses fewer evaluations and tokens to reach baseline-level performance while achieving higher final performance at the same full-evaluation budget.

  • Problem

    Existing LLM-based program-evolution methods typically use fixed allocation strategies, even as the search state and the value of evaluating candidates change.

    Source: §1 · p. 2

  • Method

    EvoAlloc evolves an explicit allocation strategy using reusable experience distilled from search outcomes, and counterfactually evaluates selected candidates otherwise skipped.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    8.7–12.0% higher final performance under the same evaluation budget, with 59–82% fewer full evaluations and 61–89% fewer LLM tokens to match baseline performance across coding and agent-harness benchmarks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Across ADAS-AIME and Circle Packing, EvoAlloc reaches reference final-performance targets with fewer full evaluations and LLM tokens while improving final performance.

    Source: §6 · p. 9

    The study evaluates allocation at the evaluation layer on two benchmarks, within a single search run, while holding generation, evaluators, and update mechanisms fixed.

    Source: §6 · p. 9

Abstract

from arXiv · show

LLM-based program evolution relies on evaluation feedback to guide the iterative search for high-performing programs. However, evaluation is often computationally expensive, making it essential to allocate limited resources to candidates that can most effectively advance the search. Existing LLM-based methods typically rely on fixed allocation strategies throughout the search, potentially wasting resources on low-value candidates while overlooking promising ones. We propose EvoAlloc, a self-evolving resource-allocation agent that learns from search experience to revise its strategy for allocating computational resources across candidates. EvoAlloc periodically consolidates prior search and allocation outcomes into reusable experience, which informs subsequent strategy revisions. It further uses a counterfactual exploration mechanism to occasionally evaluate candidates denied resources by the allocator, revealing their outcomes to enrich its experience for future strategy updates. Across coding and agent-harness optimization benchmarks, EvoAlloc requires 59-82% fewer full evaluations and 61-89% fewer total LLM tokens to reach baseline-level performance. Moreover, under the same full-evaluation budget, EvoAlloc achieves 8.7-12.0% higher final performance.

1 INTRODUCTION

Evaluation allocation shapes which programs enter the search, yet existing approaches largely keep their allocation rule fixed as search conditions change. EvoAlloc instead revises its allocation strategy using accumulated outcomes and counterfactual feedback, improving performance while reducing evaluation and token costs.

Motivation

  • Evaluation decisions shape search because evaluated programs can become future parents, while unevaluated promising candidates cannot influence what is explored next.Full evaluation can require many benchmark runs, external model or solver calls, or multi-step agent rollouts.Source: §1 · p. 2
  • Existing allocation rules may react to individual results or search history, but their underlying strategy remains fixed as the search state and value of evaluation change.The passage notes that improvements become rarer as the incumbent improves and the remaining budget shrinks.Source: §1 · p. 2

Main contributions

  • 8.7–12.0% higher final performance under the same evaluation budget, with 59–82% fewer full evaluations and 61–89% fewer LLM tokens to match baseline performance.The reported gains span coding and agent-harness optimization benchmarks.Source: §1 · p. 2

EvoAlloc

  • EvoAlloc distills search history and allocation outcomes into reusable experience, then revises its strategy and uses counterfactual exploration to reveal selected skipped outcomes.Proposed revisions are adopted through shared validation that prioritizes fewer missed new-best candidates, then lower evaluation cost.Source: §1 · p. 2

Contributions

  • The paper frames allocation as an evolving part of program evolution and analyzes its effects on resource use, candidate coverage, and search trajectories.Its contributions include an empirical analysis across coding and agent-harness benchmarks.Source: §1 · p. 2

2 RELATED WORK

Prior work adapts program generation and search, and separately studies selective evaluation and resource allocation. EvoAlloc’s distinction is to revise an explicit allocation strategy from accumulated search and evaluation outcomes.

Program Evolution and Self-Improving Search

  • Prior self-improving program-evolution work adapts candidate generation and search, while EvoAlloc also lets the evaluation-allocation mechanism evolve from accumulated search experience.The passage situates this distinction alongside adaptive parent selection, novelty control, population management, and learned search strategies.Source: §2 · p. 3

Selective Evaluation and Adaptive Resource Allocation

  • Earlier resource-allocation work distributes computation among algorithms or configurations, while other methods selectively evaluate candidate solutions using surrogates, multi-fidelity evaluation, racing, or capping.The passage also describes selective-evaluation approaches in LLM-based program evolution.Source: §2 · p. 3
  • LLM-based program-evolution methods can adapt individual evaluation decisions while retaining predefined allocation rules; EvoAlloc instead revises its explicit strategy using accumulated outcomes.Examples include cascade evaluation, novelty-based rejection, and LLM-based ranking or filtering.Source: §2 · p. 3

3 PROBLEM FORMULATION

The paper formulates evaluation allocation as a sequential search-level decision: an agent assigns limited evaluation resources across candidates to maximize the best fully evaluated score reached. Its decision mechanism may evolve using the accumulated history of allocation interactions.

3.1 EVALUATION ALLOCATION IN PROGRAM EVOLUTION

  • Evaluation allocation is a sequential decision problem in which an agent distributes a limited budget across candidates to maximize the search’s best program score.Resources saved on one candidate remain available for later search, while fully evaluated candidates can affect which programs are explored next.Source: §3.1 · pp. 3–4
  • Before evaluating a candidate, the agent observes decision-time context such as its parent program and score, the best score so far, and the remaining budget..Source: §3.1 · p. 3
  • A candidate’s allocation episode can contain multiple actions, with intermediate actions acquiring evidence and a final action committing to full evaluation or stopping.Later decisions can use evidence gathered earlier in the same episode.Source: §3.1 · p. 3
  • Only a fully evaluated candidate’s score is observed; scores of candidates that are not fully evaluated remain hidden.The full-evaluation score is defined even when the candidate is not actually evaluated.Source: §3.1 · pp. 3–4
  • Resource use can be measured by completed full evaluations or cumulative LLM tokens, and the objective tracks the best fully evaluated score obtained within that resource level.The formulation also defines the resource required to reach a target score.Source: §3.1 · p. 4

3.2 SELF-EVOLVING ALLOCATION FROM SEARCH EXPERIENCE

  • The interaction history records prior candidates, contexts, allocation episodes, and observed outcomes, including episodes without full evaluation.Each episode records allocation actions and intermediate evidence.Source: §3.2 · p. 4
  • An agent is self-evolving when it can revise its decision mechanism using accumulated interaction history, rather than keeping that mechanism fixed throughout the search.In EvoAlloc, an explicit strategy and reusable experiences distilled from observed outcomes guide decisions.Source: §3.2 · p. 4

4 METHOD

EvoAlloc uses a persistent explicit strategy to guide evaluation decisions, distills observed outcomes into reusable experience, and revises the strategy as search proceeds. Counterfactual exploration supplies feedback about selected candidates that the strategy would otherwise skip.

4 METHOD

  • EvoAlloc’s allocation agent uses a persistent, revisable strategy and reusable experiences distilled from search outcomes, with counterfactual exploration adding otherwise missing feedback.The method comprises explicit allocation, experience-driven strategy evolution, and counterfactual exploration.Source: §4 · p. 4

4.1 EXPLICIT EVALUATION ALLOCATION STRATEGY

  • The explicit strategy provides run-level guidance on overall selectivity and on allocation actions under different search contexts.The allocator also receives decision-time context and evidence gathered earlier in the candidate’s allocation episode.Source: §4.1 · p. 4
  • Allocation outcomes feed later strategy updates, while the illustrated strategy changes reflect feedback accumulated across multiple proposals rather than one proposal alone.Figure 2 depicts the information flow from strategy and search context to allocation decisions and then to later updates.Source: Figure 2 · p. 5

4.2 EXPERIENCE-DRIVEN STRATEGY EVOLUTION

  • Experiences summarize recurring patterns from observed cases, while the strategy translates those patterns into allocation criteria.New experiences may be tentative, active, or stale as supporting and contradicting cases accumulate.Source: §4.2 · p. 5
  • A challenger strategy is validated against the current strategy on disagreements, and is adopted by comparing missed new-best candidates first, then full and partial evaluation counts.For disagreements, both strategies’ requested evaluations are executed and evidence is shared; validation ends after two disagreements with an observed full outcome.Source: §4.2 · pp. 5–6

4.3 COUNTERFACTUAL EXPLORATION

  • Because selective allocation hides outcomes for candidates stopped without full evaluation, counterfactual exploration sometimes fully evaluates a randomly selected discarded candidate.The default exploration rate is 0.3; exploratory outcomes provide counterevidence or support for current criteria and inform later updates.Source: §4.3 · p. 6
  • Once explored candidates are fully evaluated, they rejoin the program search, and their outcomes can inform revised strategy criteria.The paper describes this as a loop linking strategy-guided decisions, their outcomes, and subsequent strategy revision.Source: §4.3 · p. 6

5 EXPERIMENTS

Across two benchmarks, EvoAlloc improves final performance while reducing matched-target evaluation and token costs. Ablations and search analyses show how adaptation, exploration, and selective allocation shape those outcomes.

5.1 EXPERIMENTAL SETUP

  • Experiments used five independent seeds in a shared ShinkaEvolve pipeline and evaluated reasoning-harness optimization on ADAS-AIME and solution-program optimization on Circle Packing.ADAS-AIME candidates were scored across three runs, with Full evaluations using all 30 problems and Partial evaluations using the first eight; Circle Packing had deterministic evaluation and no lower-cost intermediate stage.Source: §5.1 · p. 6

5.2 MAIN RESULTS

  • 12.0% higher mean final performance on ADAS-AIME and 8.7% on Circle Packing, with 59–82% fewer Full evaluations and 61–89% fewer LLM tokens to reach ShinkaEvolve’s final-performance target.Figure 3 reports the main results; token costs include proposal generation, benchmark evaluation, and allocation or selection calls.Source: Figure 3 · p. 7, §5.2 · p. 7

5.3 ABLATION AND SENSITIVITY ANALYSIS

  • The full EvoAlloc achieved the strongest mean best-so-far trajectories across both benchmarks, outperforming one-step allocation and fixed custom guidance; removing exploration weakened performance.On Circle Packing, final performance was similar across exploration rates, but token costs varied substantially; ρ = 0.3 was most efficient, while too much exploration offset selective-allocation savings.Source: §5.3 · pp. 7–8, Figure 4 · p. 8

5.4 HOW THE ALLOCATION STRATEGY EVOLVES AND RESHAPES SEARCH

  • On ADAS-AIME, allocation shifted from Partial evaluation without direct discards toward discarding most proposals, yet EvoAlloc still found a late improvement.The reported stage-wise changes support revising allocation criteria as search experience accumulates.Source: §5.4 · p. 8, Figure 5 · p. 8
  • At the same Full-evaluation budget, EvoAlloc examined 124 proposals versus 75 for ShinkaEvolve on ADAS-AIME and 302 versus 150 on Circle Packing.The additional proposals expand the search tree with more siblings and descendants; evaluated candidates also tend to score higher despite being selected before their Full outcomes are known.Source: §5.4 · p. 8, Figure 6 · p. 9
  • One-Step Alloc sent most proposals to Full evaluation, fixed custom guidance remained Partial-heavy, and without exploration discarded outcomes stayed hidden and pruning errors went uncorrected.The analysis identifies explicit criteria, their evolution, and exploration as jointly shaping allocation behavior.Source: §5.4 · p. 9, Figure 7 · p. 9

6 CONCLUSION AND LIMITATIONS

EvoAlloc evolves evaluation allocation using accumulated experience and counterfactual feedback, improving final performance while reducing the cost of reaching reference targets. The study is limited to evaluation-layer allocation on two benchmarks within a single search run, with generation, evaluators, and update mechanisms held fixed.

6 CONCLUSION AND LIMITATIONS

  • EvoAlloc improves final performance on ADAS-AIME and Circle Packing while reaching reference final-performance targets with 59–82% fewer Full evaluations and 61–89% fewer LLM tokens.The authors frame these findings as pointing toward systems that learn where to spend evaluation effort as well as what to search.Source: §6 · p. 9
  • EvoAlloc revises an explicit allocation Strategy from accumulated Experiences and uses counterfactual exploration to reveal otherwise-hidden outcomes.The paper treats evaluation allocation as an evolving component of program evolution.Source: §6 · p. 9
  • The study tests evaluation-layer allocation on two benchmarks within a single run, holding generation, evaluators, and update mechanisms fixed.The authors identify evolving these components and retaining allocation experience across runs as possible extensions.Source: §6 · p. 9

AI USE STATEMENT

Generative AI tools assisted with code implementation and debugging, and with manuscript language editing and presentation.

AI USE STATEMENT

  • Generative AI tools assisted with code implementation and debugging.The authors report that they reviewed and tested AI-assisted code before using it in experiments.Source: AI USE STATEMENT · p. 10
  • Generative AI tools also assisted with language editing and manuscript presentation.The authors manually reviewed and revised AI-assisted manuscript content for technical correctness and consistency with reported results.Source: AI USE STATEMENT · p. 10
  • The authors state that they developed the core research idea and experimental design and take responsibility for the final content.They also state that AI-assisted code and manuscript content were reviewed by the authors.Source: AI USE STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The reproducibility materials include method details and an algorithm outline, alongside information on implementation, benchmarks, evaluation, and budget accounting.

REPRODUCIBILITY STATEMENT

  • The appendix provides EvoAlloc pseudocode, implementation details and hyperparameters, benchmark and evaluation protocols, budget accounting, and prompts for reproducing the method.It also reports five-seed results and allocation breakdowns; code and configurations are slated for release upon acceptance.Source: REPRODUCIBILITY STATEMENT · p. 10

A EVOALLOC ALGORITHM

  • Algorithm 1 identifies EvoAlloc-specific operations while leaving parent selection, proposal generation, archive updates, and benchmark evaluation to the underlying search procedure.The algorithm takes initial programs, example cases, a Full-evaluation budget, an exploration rate, and update intervals, and returns the best program.Source: A EVOALLOC ALGORITHM · p. 12
  • The algorithm allocates evaluations using a strategy and experience, while validation shares evidence from the union of requested evaluations and counts all Full evaluations toward the budget.The described accounting includes warm-up, validation, and exploration Full evaluations; the interaction history retains original allocation episodes when outcomes are later revealed.Source: A EVOALLOC ALGORITHM · p. 12

B IMPLEMENTATION AND BENCHMARKS

The implementation uses a shared ShinkaEvolve program-evolution substrate and evaluates EvoAlloc on reasoning-harness and circle-packing tasks with different evaluation setups.

B.1 MODELS AND EVOALLOC CONFIGURATION

  • EvoAlloc runs on the public ShinkaEvolve loop with default substrate hyperparameters unless otherwise stated, using open-weight models served locally on NVIDIA A100 GPUs.Table 1 summarizes the backbone models, main EvoAlloc configuration, and benchmark-specific settings; the initial strategy uses 50 examples from five baseline runs, whose cost is excluded from reported search costs.Source: §B.1 · p. 13, Table 1 · p. 13

B.2 ADAS-AIME

  • ADAS-AIME evolves a Python reasoning scaffold around a fixed solver, using three-run accuracy over 30 AIME 2024 problems for Full evaluation and a single-seed Partial evaluation on the first eight.The Partial result determines whether to continue to Full; final performance is measured by the full evaluator, and the three repetitions count as one Full evaluation.Source: §B.2 · p. 14

B.3 CIRCLE PACKING

  • Circle Packing evolves Python programs for placing 26 circles in the unit square, with a deterministic non-LLM evaluator checking feasibility and computing the packing objective.This setting has no Partial evaluation: the allocator chooses between FULL_EVAL and DISCARD.Source: §B.3 · p. 15

C EVOLUTION AND SEARCH ANALYSIS

  • The appendix analyzes how EvoAlloc’s Strategy and Experiences change during search on ADAS-AIME and Circle Packing, and examines the resulting search trees.The passage describes the analysis scope but does not report its findings.Source: C EVOLUTION AND SEARCH ANALYSIS · p. 16

C.1 ADAS-AIME STRATEGY AND EXPERIENCE EVOLUTION

The appendix traces how EvoAlloc’s allocation strategy becomes more selective as search evidence accumulates, while its Experiences retain case-grounded tendencies for recurring proposal patterns. The ADAS-AIME and Circle Packing examples differ in whether decisions can use partial evaluation.

C.1 ADAS-AIME STRATEGY AND EXPERIENCE EVOLUTION

  • On ADAS-AIME, the Strategy moves from permissive S0 to medium selectivity and then highly selective stages with more specific lineage-conditioned criteria.Table 2 lists each stage’s full-evaluation window and Strategy text.Source: §C.1 · p. 16, Table 2 · p. 16
  • A separate ADAS-AIME Experience records that targeted fixes to known failure modes can improve over the parent and sometimes establish a new best (2 support, 0 counter).Its applicability includes recurring AIME patterns with at most 2/8 partial successes on flat or declining lineages.Source: §C.1 · p. 17

C.2 CIRCLE PACKING STRATEGY AND EXPERIENCE EVOLUTION

  • On Circle Packing, the Strategy progresses from broad evaluation to greater selectivity, choosing directly between Full evaluation and discard because there is no Partial evaluation.Figure 8 shows the representative run; Table 3 lists Strategy stages.Source: §C.2 · p. 18, Figure 8 · p. 18, Table 3 · p. 18
  • Circle Packing also records local parent improvements as potentially useful motifs, while rare new-best outcomes after repeated poor attempts are not reliably predictable from local scores.The rare-outcome Experience has 9 support and 1 counter; full evaluation may be needed to confirm such gains.Source: §C.2 · p. 19

C.3 SEARCH-TREE ANALYSIS

This appendix analyzes search trees and details the baseline configurations, performance measures, resource costs, and allocation breakdowns. The comparisons use a shared search framework and report resource use both at matched targets and at the full evaluation budget.

C.3 SEARCH-TREE ANALYSIS

  • With the same seed and 150 Full evaluations, EvoAlloc considers 302 Circle Packing proposals versus ShinkaEvolve’s 150.Figure 9’s highlighted edges trace the best-program lineages.Source: Figure 9 · p. 20, §C.3 · p. 20

D EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS

  • The appendix reports detailed performance, resource costs, and allocation breakdowns, with implementation settings and benchmark protocols described in Appendix B.Its comparisons use a common ShinkaEvolve framework unless otherwise stated.Source: D EXPERIMENTAL DETAILS AND ADDITIONAL… · p. 21

D.1 BASELINES AND COMPARISON CONFIGURATION

  • All methods share the ShinkaEvolve search backbone and differ in resource allocation; five seeds are used, and the baseline rerun uses the shared open-weight models rather than the original proprietary ensemble.Unselected candidates are discarded and cannot become parents, so allocation can alter later proposal streams.Source: §D.1 · pp. 21–22

D.2 DETAILED PERFORMANCE

  • Table 4 reports final performance and normalized best-so-far trajectory AUC, with AUC serving as an auxiliary anytime measure.AUC is computed over the evaluation budget or the common token range; values are five-seed means and standard deviations.Source: Table 4 · p. 22, §D.2 · p. 22

D.3 RESOURCE AND TOKEN COSTS

  • Matched-target costs are the Full-evaluation index and corresponding mean cumulative tokens when the five-seed mean score first reaches a target, including a target at 95% of ShinkaEvolve’s gain.At the full budget, EvoAlloc uses more total tokens than ShinkaEvolve because withheld evaluations are reinvested in examining more proposals; matched-target savings concern reaching a target, not end-budget consumption.Source: §D.3 · pp. 22–23, Table 5 · p. 23

D.4 ALLOCATION BREAKDOWN

  • At the full evaluation budget, EvoAlloc considers 136.8 proposals per seed on ADAS-AIME and 243.0 on Circle Packing, versus ShinkaEvolve’s 75.0 and 150.0.Table 6 reports five-seed token costs and allocation decisions; allocation categories record original decisions, not every executed evaluation.Source: §D.4 · p. 23, Table 6 · p. 24

D.5 ADDITIONAL ABLATION EXPERIMENTS

The appendix tests the contribution of exploration feedback, examines counterfactual recoveries and Strategy validation, and documents EvoAlloc’s prompts and search context. Its examples show how outcomes and case-grounded Experiences inform allocation and strategy updates.

D.5 ADDITIONAL ABLATION EXPERIMENTS

  • Without explicit exploration feedback, Circle Packing scores 2.446±0.110 versus EvoAlloc’s 2.547±0.030, while ADAS-AIME accuracy is (32.22±4.10)% versus (39.56±6.80)%.The comparison uses 150 Full evaluations on Circle Packing and 75 on ADAS-AIME; Figure 11 shows the Circle Packing trajectories.Source: §D.5 · p. 25, Figure 11 · p. 26

D.6 EXPLORATION OUTCOMES ACROSS STRATEGY STAGES

  • Counterfactual exploration recovers new-best candidates beyond the initial Strategy: all six ADAS-AIME cases occur under S2 or S3, and Circle Packing recovers 15 under S2.Only one run per benchmark reached S3, so pooled rates do not establish a common temporal trend.Source: §D.6 · p. 26, Table 7 · p. 26

D.7 STRATEGY VALIDATION DETAILS

  • Strategy challengers were adopted when they used fewer Full or Partial evaluations while matching the incumbent’s missed-new-best count within validation windows.Validation compares challengers and incumbents on shared proposals and realized outcomes.Source: §D.7 · p. 27

E PROMPTS AND CONTEXT

  • The appendix documents the inputs, prompts, and representative outputs for EvoAlloc’s resource-allocation and self-evolution calls.These are the two LLM calls detailed in the appendix.Source: E PROMPTS AND CONTEXT · p. 28

E.1 INPUT CONTEXT

  • Both calls receive benchmark setup, allocation guidance, recent cases, and search progress; allocation additionally receives the candidate, search context, and similar retrieved cases.The candidate’s own Full outcome is unavailable when the allocation decision is made.Source: §E.1 · p. 28

E.2 RESOURCE ALLOCATION PROMPT

  • Partial evaluation is treated as information acquisition: it is used when plausible observations could change the action, and a second decision follows its verified observation.The prompt cautions that successful execution alone does not justify continuing to Full evaluation.Source: §E.2 · pp. 28–29

E.3 SELF-EVOLUTION PROMPTS

  • Experience updates attach supporting or contradicting cases to fixed descriptions, while Strategy updates propose challengers for shadow validation.Exploration outcomes provide grounded evidence; unexplored DISCARD and STOP cases have unknown Full outcomes.Source: §E.3 · p. 29

E.4 CASE CARD EXAMPLES

  • Case cards record each proposal, its search context, allocation decision, and observed outcomes; examples include partial evaluation followed by Full evaluation or STOP followed by exploration.The examples include a 40.000 valid new-best outcome and a 28.889 valid improved-parent outcome.Source: §E.4 · pp. 30–31
Loading 2610.12086v1…