PaperlayerView exact revision on arXiv

Source-linked AI summary

Agentic ESOpt: Fine-Tuning Long-Horizon LLM Agents with Minimal GPU Requirements

Zhi Zheng, Rongsheng Chen, Yunpeng Ba, Zhenkun Wang, Yee Whye Teh, Wee Sun Lee

arXiv:2608.17310v1cs.LG

TL;DR

Long-horizon LLM agents challenge reinforcement learning because branching interactions and sparse rewards make large-model optimization and credit assignment difficult. Agentic ESOpt uses full-parameter evolution strategies for parameter–context co-evolution, becoming strongest as horizons grow and improving 28 of 36 matched test-time heuristic settings.

  • Problem

    Long-horizon agentic reasoning makes reinforcement-learning fine-tuning increasingly impractical for larger LLMs and makes sparse trajectory-level credit assignment harder.

  • Method

    Agentic ESOpt samples full-parameter perturbations, evaluates agents with environment rewards, and applies online reward-weighted updates for parameter–context co-evolution.

  • Results

    Across controlled Sudoku, ReAct-style Math and DocVQA, and test-time heuristic search, Agentic ESOpt strengthens as horizons grow and improves 28 of 36 matched comparisons.

  • Takeaways & Limitations

    Inference-level memory enables full-parameter adaptation of a Qwen3.5-27B WebArena agent on four H100 GPUs.

  • Takeaways & Limitations

    Establishing a universal scaling law and implementing Agentic ESOpt on frontier LLMs remain future work.

Abstract

from arXiv · show

Reinforcement Learning (RL) has been promising in single-turn LLM fine-tuning. However, long-horizon agentic reasoning introduces increasingly branching interactions and sparse rewards, exposing several limitations of RL: its heavyweight backpropagation-based training stack makes it impractical to fine-tune larger LLMs, and longer-horizon trajectories make credit assignment in RL substantially harder. This paper argues that evolution strategies (ES) can be a better choice for fine-tuning long-horizon LLM agents. Compared with agentic RL, ES offers three key advantages: 1) Model Scalability: ES enables full-parameter optimization with only minimal, inference-level GPU memory, making it possible to fine-tune large LLMs. 2) Flexibility: its lightweight, black-box feedback interface makes ES fine-tuning easy to compose with prompt-space evolution (e.g., skill optimization & test-time compute); and 3) Long-Horizon Scalability: ES performs trajectory-level parameter attribution without decomposing rewards across horizons, yielding better scalability than Agentic RL as the horizon length grows. Based on this insight, we propose Agentic ESOpt, a full-parameter agentic fine-tuning framework tailored to flexible parameter--context co-evolution. At each step, Agentic ESOpt samples perturbations around the current LLM parameters, evaluates the resulting agents with rewards, and applies an online reward-weighted update. To improve the exploration--adaptation trade-off, Agentic ESOpt further introduces a cosine decay schedule of the perturbation scale $σ$. On WebArena-Lite, full-parameter optimization of Qwen-3.5-27B improves the No Skill baseline by 6.69%. In test-time automatic heuristic design, Agentic ESOpt performs online prompt--parameter co-evolution, improving its matched baseline in 28 of 36 settings.

1 Introduction

The introduction argues that evolution strategies are preferable to Agentic RL for fine-tuning long-horizon LLM agents because they reduce memory barriers, support flexible black-box composition, and avoid horizon-dependent credit assignment. It introduces Agentic ESOpt as a backpropagation-free, full-parameter framework and reports validation across agentic tasks and model scales.

  • Motivation: Agentic RL faces heavyweight training requirements and difficult credit assignment in long-horizon reasoning with branching interactions and sparse feedback.The limitations include storing activations and optimizer states and performing backpropagation, while sparse rewards make long-horizon credit assignment harder.
  • Why ES: ES optimizes full parameters using inference-level GPU memory, enabling fine-tuning of larger LLM agents with a substantially lower memory barrier.ES samples parameter perturbations, evaluates perturbed agents with environment rewards, and applies reward-weighted updates without backpropagation.
  • Why ES: ES combines a lightweight black-box feedback interface with trajectory-level parameter attribution, supporting prompt-space composition and avoiding reward decomposition across turns as horizons grow.The framework is designed to compose with skill-space evolution and test-time compute while improving long-horizon scalability relative to Agentic RL.
  • Agentic ESOpt: Agentic ESOpt is a backpropagation-free, full-parameter framework that supports train-time adaptation, test-time compute, prompt-space evolution, and cosine-scheduled perturbation scales.The cosine schedule is intended to improve the exploration–adaptation trade-off.
  • Evaluation: +12.5%: Agentic ESOpt exceeds the strongest GRPO baseline on 15-turn Sudoku, after matched-FLOP methods are competitive at shorter horizons.The introduction reports that the relative ordering of RL- and ES-based methods changes as the horizon grows.
  • Evaluation: 28 of 36 settings: Agentic ESOpt enhances existing test-time evolutionary search across long-horizon Sudoku, ReAct-style tool use, web agents, and automatic heuristic design.The evaluation covers LLMs from 4B to 27B and includes full-parameter adaptation of a 27B WebArena agent.

2 Preliminaries: Agentic LLM Reasoning

Agentic LLM reasoning is modeled as multi-turn interaction over a finite horizon, with trajectories receiving discounted returns that are often sparse and terminal. Optimization can target prompts or model parameters, while existing multi-turn policy-gradient methods face difficult credit assignment as horizons grow.

  • Agentic interaction: An agent repeatedly observes the environment and produces actions, generating a trajectory τ over H agent–environment turns until termination.θ denotes model parameters, o≤t the interaction history, and ct an external prompt, memory, skill, or tool instruction.
  • Rewards and observations: Sparse rewards typically assign zero intermediate rewards and give the completed trajectory the task score.Some tasks provide the complete trajectory as input, whereas partially Markov tasks may require only local observations.
  • Optimization targets: Prompt-space optimization updates ct while freezing the LLM, whereas policy fine-tuning updates θ to improve agentic ability.Prompt optimization is lightweight but can only elicit behaviors already accessible to the frozen policy; listed fine-tuning methods include SFT, OPD, GRPO, and PPO.
  • Supervised policy methods: Agentic SFT and OPD require supervision beyond scalar environment rewards, so they are excluded from the comparison scope.SFT learns from expert actions, while OPD learns from token distributions produced by higher-ability LLMs.
  • Multi-turn policy gradients: PPO cannot fully remove long-horizon difficulty because critic warm-up is unreliable under sparse terminal rewards and its policy gradient sums H action-level score terms.Even with a well-trained critic, the resulting variance remains dependent on horizon length, motivating a trajectory-level estimator.

3 Methodology: Agentic ESOpt

Agentic ESOpt fine-tunes all LLM parameters through forward-only, reward-weighted evolution-strategy updates that require only inference-level GPU memory. It also supports alternating prompt–parameter optimization and uses cosine decay of the perturbation scale to balance exploration, exploitation, and bias.

  • Core ES optimization: Agentic ESOpt samples full-parameter perturbations, evaluates perturbed agents with scalar environment rewards, and applies reward-weighted parameter updates.The update is forward-only and does not differentiate through agent–environment interactions.
  • Core ES optimization: Inference-level GPU memory is sufficient because perturbations are reconstructed from stored noise seeds with in-place parameter addition and subtraction.This makes full-parameter optimization feasible without backpropagation-scale memory requirements.
  • Implementation: Reward normalization reduces population variance by converting sampled rewards into within-population z-scores before the update.The implementation samples G perturbations, evaluates their corresponding agents, and obtains rewards Ri = R(τi).
  • Prompt-Space Composition and Prompt-Parameter Co-Evolution: Agentic ESOpt alternates parameter updates with external prompt updates, enabling prompt–parameter co-evolution rather than restricting search to behaviors of a frozen policy.The outer loop uses Agentic ESOpt parameter update UES and an external prompt update rule Uc.
  • Perturbation-Scale Scheduling: Agentic ESOpt gradually decreases σ over T steps, using larger perturbations early for exploration and regularization and smaller perturbations later for exploitation and reduced objective bias.For train-time optimization, σT remains nonzero; for test-time compute, σT decays to zero to minimize end-of-optimization objective bias.

4 Agentic Sudoku: Controlled Experiments on Long-Horizon Scalability

Agentic ESOpt’s trajectory-level parameter attribution avoids the explicit horizon-wise score accumulation of Agentic RL, predicting better scalability as horizons grow. Controlled Sudoku experiments show a horizon-dependent crossover, with Agentic ESOpt strongest at H∗ = 15 while requiring only inference-level GPU memory and comparable wall-clock/model-FLOPs budgets.

  • Theoretical Reason for Scalability: Agentic ESOpt assigns terminal return to one complete parameter perturbation, avoiding Agentic RL’s action-score accumulation across H turns.Under the stated weak-correlation assumptions, this yields a relative advantage as the effective horizon grows.
  • Controlled Long-Horizon Sudoku: The controlled Sudoku environment provides only terminal rewards, with shortest successful horizons H∗ ∈ {5, 10, 15} from masking 5, 10, or 15 cells.Invalid or unproductive actions can make the realized horizon exceed H∗.
  • Controlled Long-Horizon Sudoku: 53.13%: Agentic ESOpt leads at H∗ = 15, exceeding GRPO’s 40.63% by 12.50 percentage points, while PPO becomes ineffective with only terminal reward.At H∗ = 5, PPO leads with 90.63%; at H∗ = 10, GRPO leads with 67.71%.
  • Controlled Long-Horizon Sudoku: At H∗ = 15, GRPO variants fail to improve quickly initially and PPO collapses, consistent with poor long-horizon credit assignment under a 45-turn interaction budget.At H∗ = 5, methods have similar learning curves.
  • Controlled Long-Horizon Sudoku: From 39.58% at step 60 to 53.13% at step 100, Agentic ESOpt improves late in training as cosine sigma decay supports exploration and avoids local optima.Removing cosine decay worsens Vanilla Agentic ES, while setting final sigma to 0 causes overfitting and poor evaluation performance.
  • Compute and wall-clock efficiency: 8.41GB: Agentic ESOpt uses inference-level GPU memory, 85.7% below GRPO’s 58.88GB requirement, while model FLOPs and measured wall-clock time remain comparable.This efficiency supports full-parameter adaptation despite Agentic ESOpt using G = 32 versus eight GRPO rollouts.

5 Agentic ESOpt for Train-Time Fine-tuning

Agentic ESOpt fine-tunes long-horizon tool-use and web agents, consistently outperforming matched Agentic GRPO baselines while preserving Pass@K coverage. On WebArena-Lite, it enables full-parameter adaptation of Qwen3.5-27B and improves both No Skill and Trace2Skill baselines.

  • Math and DocVQA: Agentic ESOpt consistently outperforms matched Agentic GRPO baselines across ReAct-style Math and DocVQA tool-use tasks.The Math setting trains on 400 DAPO problems and evaluates on held-out DAPO and AIME 2026 problems; DocVQA uses 50 validation questions for fine-tuning and 100 held-out questions for evaluation.
  • Math and DocVQA: 13.8 and 15.0 percentage points: Agentic ESOpt improves Qwen3.5-4B base performance on DAPO and AIME 2026 Mean@4, respectively, without evolved skills.It also improves DocVQA Mean@4 accuracy by 12.3 points; averaged across the three metrics, gains are 13.7 points over the base model and 8.3 points over Agentic GRPO.
  • Math and DocVQA: Agentic ESOpt variants improve every reported Pass@K metric over matched GRPO baselines across datasets, while improving Pass@K over the base LLM in AIME 2026 and DocVQA.Both variants outperform matched Agentic GRPO baselines on every reported Pass@4 metric across Math and DocVQA.
  • WebArena-Lite: Full-parameter adaptation of Qwen3.5-27B is feasible with Agentic ESOpt on four NVIDIA H100 80GB GPUs, whereas full-parameter Agentic RL is no longer practical at this scale.Agentic ESOpt retains inference-level memory requirements, enabling adaptation of the 27B web agent.
  • WebArena-Lite: 6.69 percentage points: Agentic ESOpt raises the Qwen3.5-27B No Skill baseline from 29.47% to 36.16% on WebArena-Lite.WebArena-Lite is a 165-task browser benchmark with task-success feedback after interactive trajectories.
  • WebArena-Lite: Agentic ESOpt further raises the Trace2Skill baseline from 33.94% to 36.36% on WebArena-Lite, demonstrating composition with skill-space optimization on larger LLMs.The final results use the official 165-task WebArena-Lite evaluation set.

6 Agentic ESOpt on Test-Time Compute: Automatic Heuristic Design

Agentic ESOpt extends automatic heuristic design beyond search over a frozen LLM policy by jointly adapting heuristic and parameter spaces. Under matched evaluation budgets, it improves 28 of 36 method–budget comparisons across constructive and ACO-style settings.

  • Automatic Heuristic Design: Agentic ESOpt couples heuristic-space search with parameter-space adaptation, addressing the limitation of fixed LLM parameters during test-time compute.It preserves the outer Sample or EoH search scaffold while enabling lightweight black-box parameter updates.
  • Automatic Heuristic Design: The evaluation covers constructive AHD on TSP, KP, and ASP, plus ACO-style AHD on TSP, CVRP, and BPP under matched evaluation budgets.Sample and EoH are compared with corresponding Agentic ESOpt variants.
  • Automatic Heuristic Design: 28 of 36 matched method–budget comparisons improve when constructive and ACO-style settings are combined.Across constructive baselines alone, Agentic ESOpt improves 21 of 24 matched comparisons; Agentic ESOpt + EoH improves all six constructive test sets at both budgets.

7 Discussion

The discussion identifies population size as a key ES hyperparameter and presents preliminary evidence that stronger backbones are less sensitive to small populations. This supports using Agentic ESOpt to fine-tune larger LLMs with fewer sampled directions and FLOPs, while noting the evidence remains preliminary.

  • Population scaling: Population size G is a key ES hyperparameter whose sensitivity may decrease with stronger backbones.The paper frames this as preliminary evidence from the reported population experiments.
  • Population scaling: 35.42% best test accuracy and 22.92% final test success result when the 4B model’s population increases from G = 8 to G = 16.These results use the same 15-turn Sudoku setting; the corresponding increases are from 5.10% and 2.95%.
  • Population scaling: A stronger pretrained backbone may create a more competent local region where more nearby perturbations inform the Agentic ESOpt update.The discussion connects this interpretation to denser useful behavioral diversity around stronger pretrained models and to fine-tuning larger LLMs with fewer FLOPs.
  • Population scaling: +677.0% final-test success change occurs for 4B when doubling G, compared with 0.0% for 9B.This indicates that stronger backbones may need fewer sampled directions.

8 Conclusion … A Limitations & Future Work

Agentic ESOpt is presented as a full-parameter, inference-memory-efficient optimization framework that better matches long-horizon, sparse-feedback LLM agents than conventional Agentic RL. Experiments support its long-horizon, model-scaling, and parameter–context co-evolution advantages, while limitations and future work are deferred to Appendix A.

  • 8 Conclusion: Agentic ESOpt uses full-parameter evolution-strategy fine-tuning with only minimal inference-level GPU memory for long-horizon LLM agents.The framework attributes outcomes at the trajectory level rather than assigning them across an expanding action sequence.
  • 8 Conclusion: Agentic ESOpt becomes strongest as the minimum successful horizon grows, extending its advantage from controlled Sudoku to ReAct-style Math and DocVQA.Agentic PPO and Agentic GRPO remain competitive at shorter horizons.
  • 8 Conclusion: Its inference-level memory footprint enables full-parameter adaptation of a Qwen3.5-27B WebArena agent on four H100 GPUs.This provides a model-scaling advantage through forward-only optimization.
  • 8 Conclusion: 28 of 36 matched AHD comparisons improve under fixed evaluation budgets when Agentic ESOpt integrates parameter adaptation into test-time compute optimization loops.The improvements include skill optimization and test-time heuristic search.
  • 8 Conclusion: The paper positions ES as a better-matched optimization mechanism, rather than merely a cheaper substitute for RL, for long-horizon, sparse-feedback LLM agents.The authors suggest this paradigm may support agent fine-tuning and online self-improvement as interactions, models, and prompt-space components grow more complex.
  • A Limitations & Future Work: Limitations of the current study are discussed in Appendix A.1, while future work is outlined in Appendix A.2.The conclusion explicitly directs readers to these appendices for limitations and future-work discussion.
  • Appendix: The appendices cover related work on Agentic Reinforcement Learning, Evolution Strategies, and skill- and memory-based self-improvement.These topics appear in Appendix B and its subsections.
  • Appendix Contents: The appendix contents also include theoretical analysis, computational accounting, experimental settings and additional results, prompts and skills, and licensing and external components.Listed subsections include ES-gradient and Gaussian-smoothing analyses, long-horizon credit assignment, Sudoku, Math Reasoning, DocVQA, and licensing scope.

A.1 Limitations … B.2 Evolution Strategies for single-turn LLM Fine-Tuning.

The paper identifies evaluation cost, perturbation-hyperparameter tuning, and unresolved continual-learning behavior as limitations, while outlining scalability, quantization, and tighter skill–parameter co-evolution as future directions. Related work positions Agentic ESOpt against agentic RL and within the broader emergence of ES for single-turn LLM fine-tuning.

  • A.1 Limitations: Agentic ESOpt introduces perturbation-radius hyperparameters whose optimal values may depend on the LLM, reward distribution, and environment.Across five experiments, the paper uses relatively consistent settings of σ0 ≈ 1e−3 and α ≈ 5e−4.
  • A.1 Limitations: Agentic ESOpt may be less favorable when environment evaluation is extremely expensive because rollout cost can dominate the total budget.Under matched model FLOPs, ES can afford more trajectories because each trajectory requires only a forward pass.
  • A.1 Limitations: Continual-learning behavior remains unclear because ES may random-walk in directions irrelevant to the objective, despite update magnitudes being highly concentrated.Table 7 examines parameter-update magnitudes for WebArena on Qwen3.5-27B at σt = 1.5 × 10−3.
  • A.2 Future Work: Agentic ESOpt’s inference-level memory requirement offers a path toward full-parameter adaptation of substantially larger LLM agents.The 4B/9B results suggest stronger backbones may require fewer perturbation directions, motivating population-scaling studies.
  • A.2 Future Work: Quantized ES optimization requires scale-aware noise generation, numerically stable updates, and seed-replay infrastructure for quantization-compatible perturbations.The paper identifies quantization-specific systems infrastructure as an important direction for large-scale ES fine-tuning.
  • A.2 Future Work: Future work could tightly couple multi-step skill optimization with parameter adaptation so external context and model parameters evolve on comparable timescales.This co-evolution would allow skill- and parameter-space updates to continually reshape each other’s data distributions.
  • B.1 Agentic Reinforcement Learning: Agentic ESOpt addresses agentic-RL training complexity by replacing rollout storage, token-level policy gradients, reference models, and KL constraints with scalar black-box fitness.Prior agentic-RL work improves rollout or credit assignment, but the paper presents ES as a more direct solution for parameter adaptation.
  • B.2 Evolution Strategies for single-turn LLM Fine-Tuning.: Evolution strategies have emerged as efficient gradient-free optimizers for single-turn LLM fine-tuning as growing model sizes make moderate-device training unaffordable.Qiu et al. (2026) reported that ES can scale to full-parameter LLM fine-tuning while matching or exceeding GRPO in sample efficiency and training stability.

B.3 Skill and Memory-Based Self-Improvement and Test-Time Compute … C.4 AHD as Heuristic-Space Optimization

The paper positions Agentic ESOpt as a parameter-adaptation complement to skill, memory, and test-time optimization, with theoretical analysis emphasizing black-box estimation, smoothing bias, and long-horizon variance structure. It also frames automatic heuristic design as optimization over LLM-induced heuristic distributions across five NP-hard problems.

  • B.3 Skill and Memory-Based Self-Improvement and Test-Time Compute: Frozen-policy self-improvement optimizes verbal feedback, executable skills, memories, skill documents, or additional search while leaving the underlying LLM unchanged.Examples include Reflexion, Voyager, memory systems, SkillOpt, Trace2Skill, and test-time compute methods.
  • B.3 Skill and Memory-Based Self-Improvement and Test-Time Compute: Agentic ESOpt adds parameter adaptation to external-space optimization, reusing trajectory-level feedback so skills, memories, test-time search, and parameters can co-evolve.Its black-box update complements optimization of non-parametric components and can strengthen behaviors beyond those accessible to a frozen policy.
  • C.1 Derivation of the Scalar-Score ES Gradient: Agentic ESOpt estimates updates from scalar trajectory rewards without differentiating sampled actions, environment transitions, or the reward function.A perturbation-independent baseline may be subtracted without changing the expectation, while within-population reward standardization is the practical finite-sample variant.
  • C.2 Proof of the Gaussian-Smoothing Bias Expansion: The population ES estimator is unbiased for the gradient of the Gaussian-smoothed objective, whose leading bias relative to the original gradient is proportional to σ^2.The result follows from the Gaussian score-function identity and a centered-Gaussian expansion.
  • C.3 Long-Horizon Credit Assignment: Under weak-correlation scaling assumptions, action-space policy-gradient score variance grows approximately linearly with realized horizon H.The trajectory-level policy-gradient estimator uses a terminal return and sums policy scores across turns.
  • C.3 Long-Horizon Credit Assignment: Agentic ESOpt’s complete-trajectory perturbation has no sum over turns in its parameter-score factor, isolating a horizon-dependent variance source absent from ES.The comparison concerns score structure only; ES can still become harder with sparse returns and may depend on d, σ, population size G, and local objective geometry.
  • C.4 AHD as Heuristic-Space Optimization: Automatic heuristic design treats generated text as an optimization object only through the algorithmic behavior it induces, using an LLM-induced proposal distribution over heuristics.A solver applies each sampled heuristic to problem instances and evaluates the resulting solutions with a signed score.
  • C.4 AHD as Heuristic-Space Optimization: 5 NP-hard combinatorial optimization problems are covered, including TSP, CVRP, and KP, to test whether altered proposal distributions yield better global solutions.The tasks evaluate tour length, routing cost, item-set value, and related solution quality as local heuristic decisions accumulate.

C.5 Training FLOPs Calculation · D Experimental Settings and Additional Results · D.1 Sudoku

The appendix quantifies model-side training FLOPs for Agentic ESOpt, GRPO, and PPO, while detailing experimental settings and Sudoku compute comparisons. Agentic ESOpt uses one policy forward pass per sampled trajectory and requires approximately half the matched GRPO FLOPs on Math Reasoning and DocVQA.

  • C.5 Training FLOPs Calculation: A forward pass costs approximately 2P L̄ FLOPs and a backward pass approximately 4P L̄ FLOPs for P parameters and L̄ processed tokens.Training costs are expressed using iterations T, prompt batch size B, and rollouts or perturbation directions G.
  • C.5 Training FLOPs Calculation: For equal-length trajectories, Agentic ESOpt costs one policy forward pass per sampled trajectory, versus approximately four forward-pass equivalents for GRPO and seven for PPO.Environment execution is excluded because the comparison measures model-side training FLOPs.
  • D.1 Sudoku: Sudoku uses 100 update rounds for Agentic ESOpt and GRPO with prompt batch size 32, while Agentic PPO uses 500 update rounds.Agentic ESOpt evaluates 32 perturbation directions per prompt, whereas GRPO uses 8 rollouts.
  • D.1 Sudoku: The fourfold larger ES population is exactly offset by its fourfold lower model-side cost per trajectory, while PPO is capped at 500 training steps for a comparable compute budget.These settings compare training compute under equal trajectory-length assumptions.
  • D.1 Sudoku: 3.1/6.3/9.4 EFLOPs are reported for Agentic ESOpt and 3.2/7.6/10.9 EFLOPs for Agentic GRPO at H∗∈{5, 10, 15}.The measured values replace nominal trajectory length with actual model-processed tokens.
  • C.5 Training FLOPs Calculation: Agentic ESOpt requires approximately half the model-side training FLOPs of the matched Agentic GRPO configuration on Math Reasoning and DocVQA.For Math Reasoning, ESOpt uses G = 16 and GRPO G = 8 while each covers 400 training examples once; both cover 640 DocVQA examples.
  • D Experimental Settings and Additional Results: The appendix supplies task-specific implementation details and additional diagnostics supporting experiments in Sections 4–6.It follows the order Sudoku, Math reasoning, DocVQA, WebArena-Lite, automatic heuristic design, and a cross-setting hyperparameter summary.

D.1.1 Empirical Diagnostics for Long-Horizon Scaling … D.4.3 Parameter and Skill Adaptation Stages

Across Sudoku, Math, DocVQA, and WebArena-Lite, the appendix documents long-horizon diagnostics, aligned training and evaluation protocols, and staged parameter–skill adaptation for Agentic ESOpt. The experiments consistently show sparse-feedback robustness, shorter trajectories, and preserved gains under repeated sampling.

  • D.1.1 Empirical Diagnostics for Long-Horizon Scaling: As H∗ increases, reward level and contrast decline, yet local parameter variation remains visible at H∗=15; Agentic ESOpt stays near minimum-length paths while GRPO accumulates excess turns.The schematic relation gives S_H∗=0.774, 0.599, and 0.463 for p=0.95 at H∗=5, 10, and 15, respectively, but is not fitted to measured trajectories.
  • D.1.2 Training Configuration; D.1.3 Vanilla-ES Population-Sensitivity Configuration: Sudoku ES uses 32 full-parameter directions on 32 puzzles for 100 generations, while population-sensitivity runs compare G∈{8,16} with σ=5 × 10^-4 and α=5 × 10^-4.The fixed ES interaction budgets are 15, 30, and 45 turns for H∗=5, 10, and 15; population-sensitivity runs use eight training puzzles per direction.
  • D.2 Math Reasoning; D.2.1 Agentic ESOpt Training Configuration; D.2.2 Multi-Turn GRPO Training Configuration: Math Agentic ESOpt evaluates 256 direction–problem trajectories per generation using exact-match final-answer rewards, while Math GRPO matches sampling but uses learning rate 10^-6 and KL coefficient 10^-3.The Math setup uses temperature 1, top-p=1, top-k=40, presence penalty 2, and repetition penalty 1.
  • D.2.3 Common Evaluation Configuration: Math evaluation uses 100 held-out DAPO problems and 30 AIME 2026 problems, with four samples per problem and up to 50 interaction turns and 4096 generated tokens per turn.These settings are shared by Agentic ESOpt, Agentic GRPO, Trace2Skill, combined variants, and other baselines.
  • D.3 DocVQA; D.3.1 Agentic ESOpt Training Configuration; D.3.2 Multi-Turn GRPO Training Configuration: DocVQA Agentic ESOpt and GRPO align training interaction and generation settings, with 256 direction–question trajectories per generation and continuous ANLS as the ES reward.DocVQA training and evaluation use the same sampling configuration, while valid ES trajectories require at least one parsed tool action before the final answer.
  • D.3.3 Common Evaluation Configuration; D.3.4 Repeated-Sampling Profiles for Math and DocVQA; D.3.5 DocVQA Training-Stage Turn Diagnostics: DocVQA evaluation gives every method four samples per question, 50 interaction turns, 512 tokens per turn, and 32,768 total tokens, while ESOpt remains above matched GRPO as sampling budgets increase.On AIME 2026 and both DocVQA metrics, ESOpt also remains above the base policy at larger k.
  • D.4 WebArena-Lite; D.4.1 Goal-Conditioned Task Formulation; D.4.2 Rollout Protocol and Data Split: WebArena-Lite measures sparse terminal success in a partially observed browser environment, using 30 browser actions per task, 2048 tokens per response, and 582 training plus 65 validation tasks.Tasks never contribute parameter-update rewards or trajectory-to-skill inputs, and all six sites remain enabled.
  • D.4.3 Parameter and Skill Adaptation Stages: WebArena-Lite adaptation combines 70 Trace2Skill skill-evolution iterations with a No Skill stage of 70 full-parameter ES updates using G=8 on eight training tasks per generation.Each No Skill generation contains 8 × 8 = 64 direction–task rollouts, and the combined condition adds post-hoc skill distillation to shared No Skill parameter updates.

D.4.4 Full-Evaluation Curve · D.5 Automatic Heuristic Design

The full WebArena-Lite evaluation curve for the No Skill Qwen3.5-27B Agentic ESOpt run rises from a 29.50% base checkpoint to 35.76% after 70 updates, despite non-monotonic intermediate performance. The final update achieves the best observed success rate and is followed by a three-run final evaluation for the main comparison.

  • D.4.4 Full-Evaluation Curve: 35.76% success rate is reached after 70 updates from the 29.50% base checkpoint in the full WebArena-Lite evaluation.Evaluation occurs every 10 ES updates during the No Skill Qwen3.5-27B Agentic ESOpt run.
  • D.4.4 Full-Evaluation Curve: The full-set curve is non-monotonic across intermediate checkpoints, but the final update reaches the best observed success rate.Table 4 reports the three-run final evaluation used for the main comparison.

D.5.1 Experimental Configuration

The AHD experiments evaluate Agentic ESOpt under fixed Sample and EoH outer-search scaffolds using LLaMA-3.1-8B-Instruct on eight 3090 GPUs. Agentic ESOpt adds only parameter-space updates while preserving proposal budgets and outer procedures.

  • Experimental setup: Experiments use eight 3090 24GB GPUs, fixed independent Sample and EoH scaffolds, unchanged proposal budgets and outer procedures, and LLaMA-3.1-8B-Instruct.Agentic ESOpt adds only the parameter-space update in each paired comparison.
  • EoH configuration: EoH maintains N = 10 heuristics for 25 outer generations, with total budget 25N(2+2k), using k = 1 for T = 1,000 and k = 3 for T = 2,000.Operators e1 and e2 each generate N candidates, while m1 and m2 each generate kN candidates.
  • Sample configuration: The Sample scaffold evaluates independent i1 proposals in batches of 20, with each batch forming one Agentic ESOpt update.Matched baselines use the same proposal counts.
  • Parameter updates: Agentic ESOpt uses full-parameter one-sided Gaussian perturbations, cosine decay σ : 10−3 →0, no warmup, α = 5 × 10−4, and population z-score normalization.All objectives are converted internally to minimization costs.
  • Update units: In EoH, only mutation operators m1 and m2 trigger parameter updates, producing two update batches per outer generation, while e1 and e2 remain unchanged.Each mutation operator forms one ES update batch per outer generation.

D.5.2 Additional ACO-Style Results and Ablations … F.2 Upstream Repositories Used by the Released Workflow

Additional ablations show that Agentic ESOpt improves most matched ACO-style settings, depends on both its update and perturbation schedule, remains significant across repeated runs, and adds limited runtime overhead. The paper also documents cross-setting implementation details, agent environments and skills, and licensing boundaries for released workflow components.

  • D.5.2 Additional ACO-Style Results and Ablations: 28 of 36 matched method–budget settings improve across 12 test sets and six scenarios, with one tie and seven regressions.At T = 1,000, gains occur on both TSP settings and CVRP-50; at T = 2,000, gains occur on both CVRP and both BPP settings.
  • D.5.2 Additional ACO-Style Results and Ablations: Both the reward-weighted parameter update and cosine perturbation schedule contribute to performance, while retuning EoH sampling temperature does not reproduce the gain.Temperature 0.6 is the strongest EoH setting, yet Agentic ESOpt remains better on TSP.
  • D.5.2 Additional ACO-Style Results and Ablations: Both repeated-run comparisons are significant at the 0.05 level, supporting consistency of AHD gains beyond a single search seed.The analysis uses 20 independent runs per method on TSP (N = 50) and KP (N = 100, W = 25).
  • D.5.2 Additional ACO-Style Results and Ablations: 5.0–7.4 minutes of added runtime corresponds to a 9.7%–18.0% increase over the original Sample runtime across three tasks.Updates run nearly on the fly within candidate generation and evaluation, without a separate post-search training stage.
  • D.6 Cross-Setting Hyperparameter Summary: Across settings, Agentic ESOpt uses full-parameter, one-sided Gaussian perturbations, population z-score normalization, seeded direction reconstruction, and an effective update scale α.For candidate i, the implementation applies θ + σ_tϵ_i, evaluates the complete trajectory or generated heuristic, reverts the perturbation, and reconstructs the direction from its integer seed.
  • E Prompts and Skills: Agent environments cover multi-turn Sudoku actions, ReAct tool trajectories for AIME and DocVQA, browser navigation in WebArena-Lite, and heuristic generation for AHD.Rewards or evaluators include binary Sudoku completion, binary AIME exact match, DocVQA ANLS, WebArena task outcomes, and AHD solution quality.
  • E.2.2 and E.3.2 Trajectory-to-Skill Composition: Trace2Skill compositions retain failed or successful traces under task-specific selection rules, distill skills with GPT-5.4-nano at temperature 1, and evaluate models with three seeds.Math keeps at most one failed trajectory per training problem, while DocVQA keeps at most one failed and one successful trace per occurrence when available.
  • F.1 Licensing Scope and F.2 Upstream Repositories Used by the Released Workflow: Released study code is under the MIT License, while external code, benchmark assets, datasets, checkpoints, API services, and upstream repositories remain governed by their respective terms.The licensing table is limited to resources directly invoked, vendored, or copied by the released workflow; reference-only and unexecuted baseline repositories are excluded.
Loading 2608.17310v1…