One-sentence Summary

Researchers from National University of Singapore, Southern University of Science and Technology, and Oxford propose Agentic ESOpt, a full-parameter evolution-strategy fine-tuning framework for long-horizon LLM agents that uses perturbation sampling, online reward-weighted updates, and a cosine decay schedule for the perturbation scale σ while requiring only inference-level GPU memory; on long-horizon Sudoku it outperforms RL by 12.50% with Qwen3.5-4B, and on WebArena-Lite full-parameter optimization of Qwen3.5-27B improves the No Skill baseline by 6.69% while combining Agentic ESOpt with Trace2Skill improves the Trace2Skill baseline by 2.42%.

Key Contributions

• Agentic ESOpt is introduced as a full-parameter evolution-strategy fine-tuning framework for long-horizon LLM agents that samples parameter perturbations, evaluates the resulting agents with trajectory-level rewards, and applies online reward-weighted updates without backpropagation or explicit per-action credit assignment, requiring only inference-level GPU memory.
• The method includes a cosine decay schedule for the perturbation scale to manage the exploration-adaptation trade-off and supports parameter-context co-evolution with prompt-space optimization such as skill optimization and test-time compute.
• Experiments show that Agentic ESOpt outperforms agentic RL baselines on long-horizon Sudoku by 12.50% with Qwen3.5-4B; on WebArena-Lite, full-parameter optimization of Qwen3.5-27B improves the No Skill baseline by 6.69%, and combining Agentic ESOpt with Trace2Skill improves the Trace2Skill baseline by 2.42%; in test-time automatic heuristic design, Agentic ESOpt improves its matched baseline in 28 of 36 settings. Its inference-level memory footprint enables full-parameter adaptation of a Qwen3.5-27B WebArena agent on four H100 GPUs.

Introduction

Advanced Large Language Models such as Qwen3, DeepSeek-R1, and Gemini 2.5 can act as general-purpose agents that use tools, process long contexts, and coordinate multi-step software workflows, but they still struggle with uncommon tool APIs and specialized scientific or algorithmic tasks, so efficient task-specific fine-tuning remains important. Prior agentic reinforcement learning methods require heavyweight activations and optimizer states, backpropagation through long branching trajectories, and turn-level or critic-based credit assignment under sparse rewards, which becomes increasingly impractical as horizons grow. Previous evolution-strategy work on single-turn reasoning was mostly memory efficient but often slightly weaker than RL. The authors argue that for long-horizon agentic reasoning, evolution strategies become structurally preferable rather than merely cheaper. They introduce Agentic ESOpt, a full-parameter evolution-strategy framework that samples parameter perturbations, evaluates agents with environment rewards, and applies reward-weighted updates without backpropagation. It supports both train-time fine-tuning and test-time compute, uses a cosine perturbation schedule to balance exploration and adaptation, and enables full-parameter optimization with only inference-level GPU memory.

Method

The authors propose Agentic ESOpt, a method that performs full-parameter Evolutionary Strategy (ES) optimization for Large Language Models (LLMs). The framework operates by sampling parameter perturbations around the current LLM, evaluating the perturbed agents using scalar environment rewards, and applying a reward-weighted parameter update. This forward-only process requires storing only the noise seed and utilizing in-place addition and subtraction, ensuring that GPU memory requirements remain minimal and equivalent to standard inference. Additionally, the black-box trajectory feedback generated can be reused by skill-space optimizers or test-time compute procedures.

As illustrated in the framework diagram:

Formally, let $\pmb{\tau} = (o_0, a_0, \dots, o_H, a_H)$τ=(o0​,a0​,…,oH​,aH​) denote an interaction trajectory induced by policy $\pi_\theta$πθ​, and let $R(\tau)$R(τ) denote its scalar trajectory return. For a fixed external agent state $c$c, the objective is defined as:

$$J(\theta; c) = \mathbb{E}_{\boldsymbol{\tau} \sim \pi_\theta(\cdot|c)} [R(\boldsymbol{\tau})]$$J(θ;c)=Eτ∼πθ​(⋅∣c)​[R(τ)]

Agentic ESOpt optimizes this objective by searching the parameter space around $\theta$θ. Let $\epsilon \in \mathbb{R}^d$ϵ∈Rd be a full-parameter perturbation on the $d$d-dimensional parameters. The Gaussian-smoothed objective is formulated as:

$$J_\sigma(\theta; c) = \mathbb{E}_{\epsilon \sim \mathcal{N}(0, I)} [J(\theta + \sigma \epsilon; c)]$$Jσ​(θ;c)=Eϵ∼N(0,I)​[J(θ+σϵ;c)]

The ES pseudo-gradient is then derived as:

$$\nabla_\theta J_\sigma(\theta; c) = \frac{1}{\sigma} \mathbb{E}_\epsilon [J(\theta + \sigma \epsilon; c) \epsilon]$$∇θ​Jσ​(θ;c)=σ1​Eϵ​[J(θ+σϵ;c)ϵ]

These ES gradients are estimated from scalar scores without differentiating through the agent-environment interaction. In implementation, to estimate the gradient, the authors sample $G$G perturbations $\epsilon_1, \dots, \epsilon_G$ϵ1​,…,ϵG​, evaluate the corresponding perturbed agents, and obtain rewards $R_i = R(\tau_i)$Ri​=R(τi​). To reduce variance, the rewards are normalized within the population using a z-score:

$$\hat{R}_i = \frac{R_i - \mu_R}{s_R + \varepsilon}, \quad \text{where} \quad \mu_R = \frac{1}{G} \sum_{j=1}^G R_j, \quad s_R^2 = \frac{1}{G} \sum_{j=1}^G (R_j - \mu_R)^2$$R^i​=sR​+εRi​−μR​​,whereμR​=G1​j=1∑G​Rj​,sR2​=G1​j=1∑G​(Rj​−μR​)2

In practice, the explicit $1/\sigma$1/σ factor is omitted, with $\alpha$α serving as the effective update scale. The implemented update rule is:

$$\theta_{t+1} = \theta_t + \frac{\alpha}{G} \sum_{i=1}^G \hat{R}_i \boldsymbol{\epsilon}_i$$θt+1​=θt​+Gα​i=1∑G​R^i​ϵi​

The method also facilitates prompt-space composition and prompt-parameter co-evolution. Unlike test-time compute and prompt-space optimization methods that keep LLM parameters fixed, the lightweight black-box updates of Agentic ESOpt allow parameter adaptation to occur on the fly alongside prompt-space search. Let $\mathcal{D}_t$Dt​ denote the trajectories and scores collected at iteration $t$t, $\mathcal{U}_{ES}$UES​ the Agentic ESOpt parameter update, and $\mathcal{U}_c$Uc​ an external update rule for prompt $c_t$ct​. A general alternating outer loop updates the two spaces as:

$$\theta_{t+1} = \mathcal{U}_{ES}(\theta_t; c_t, \mathcal{D}_t), \quad c_{t+1} = \mathcal{U}_c(c_t; \mathcal{D}_t)$$θt+1​=UES​(θt​;ct​,Dt​),ct+1​=Uc​(ct​;Dt​)

To manage the trade-off between exploration and objective bias, the authors introduce a cosine decay for the perturbation radius $\sigma$σ. The Gaussian-smoothed objective introduces a smoothing bias characterized by the second-order term $\text{Tr}(\nabla_\theta^2 J)$Tr(∇θ2​J), which acts as a regularization term penalizing sharp local optima. A larger $\sigma$σ increases this regularization but also increases bias from the original objective. The radius is gradually decreased over $T$T update steps as follows:

$$\sigma_t = \sigma_T + (\sigma_0 - \sigma_T) \frac{1 + \cos(\pi t / T)}{2}, \qquad t = 0, \dots, T$$σt​=σT​+(σ0​−σT​)21+cos(πt/T)​,t=0,…,T

For train-time Agentic ESOpt, a nonzero $\sigma_T$σT​ is retained to balance exploitation with exploration and regularization. In contrast, for test-time compute, which focuses on the unbiased outcome of the current task rather than generalization, $\sigma_T$σT​ is decayed to zero to minimize objective bias toward the end of optimization.

Experiment

The experiments evaluate Agentic ESOpt across controlled long-horizon tasks, train-time fine-tuning, test-time compute, and population scaling. In multi-turn Sudoku, parameter-space search shows a horizon-dependent advantage over action-space policy gradients because it avoids per-step credit assignment, while also requiring only inference-level GPU memory. For ReAct-style Math and DocVQA fine-tuning, Agentic ESOpt consistently outperforms matched Agentic GRPO baselines and composes effectively with Trace2Skill, and WebArena results confirm that full-parameter adaptation of a 27B agent is feasible. On automatic heuristic design, Agentic ESOpt improves most Sample and EoH comparisons under matched budgets, and population-scaling experiments suggest stronger backbones are less sensitive to small population sizes.

Success rates decline for all methods as the minimum required planning horizon increases. Agentic ESOpt with sigma decay maintains the highest success at the longest horizon and keeps GPU memory at the lightweight 4B backbone level, while Agentic PPO collapses to zero success and requires substantially more memory. Removing sigma decay from the ES run reduces success relative to Agentic ESOpt across tested horizons. Every evaluated method loses success rate as the minimum successful horizon grows. Agentic ESOpt is the strongest at the longest horizon and uses far less GPU memory than Agentic PPO and Agentic GRPO. Agentic PPO performs well at the shortest horizon but fails at the longest horizon. Vanilla ES without sigma decay trails Agentic ESOpt at all tested horizons.

Across the agentic Sudoku horizons tested, Qwen3.5-4B with Agentic ESOpt requires less training compute and less wall-clock time than with Agentic GRPO on the same four-GPU hardware. The compute advantage is small at the shortest horizon and widens as the horizon lengthens, while wall-clock time remains substantially lower throughout. Agentic ESOpt reduces training FLOPs relative to Agentic GRPO at every tested horizon, with the savings increasing as the horizon grows. Wall-clock time for Agentic ESOpt is roughly half that of Agentic GRPO at the longer horizons and remains lower at the shortest horizon, despite both methods fully using the same four H100 GPUs.

Agentic ESOpt consistently improves the Qwen3.5-4B base model and matched Agentic GRPO baselines on math reasoning and DocVQA. The gains are strongest on DAPO, AIME 2026, and DocVQA Mean@4, and the method composes with Trace2Skill to reach the strongest Qwen3.5-4B Mean@4 results. Pass@4 and Max@4 metrics also favor Agentic ESOpt over Agentic GRPO, while DAPO Pass@4 is unchanged from the No Skill baseline. Agentic ESOpt plus No Skill produces double-digit Mean@4 gains on DAPO and AIME 2026 and a large DocVQA accuracy improvement over the Qwen3.5-4B No Skill baseline. Agentic ESOpt plus No Skill outperforms matched Agentic GRPO plus No Skill on DAPO, AIME 2026, and DocVQA mean and best-of-four metrics, with especially large AIME 2026 Pass@4 and DocVQA Max@4 gains.

On WebArena-Lite, Agentic ESOpt improves the Qwen3.5-27B No Skill baseline on the dataset average and across most major site categories, with particularly large gains in OSS, GitLab, CMS, and Map. The Reddit category is a slight exception, where the adapted model does not improve over its baseline. Combining Agentic ESOpt with Trace2Skill yields the highest reported Qwen3.5-27B average, indicating compatibility with skill-space optimization. Agentic ESOpt improves the Qwen3.5-27B No Skill baseline on the dataset average and in four of the five major site categories, while Reddit shows a small decline. The largest category gains over the No Skill baseline appear in OSS, GitLab, CMS, and Map, in that order. The strongest Qwen3.5-27B dataset average is achieved by combining Agentic ESOpt with Trace2Skill, surpassing the No Skill and Trace2Skill baselines.

Agentic ESOpt improves existing heuristic design search methods across most constructive problem settings. When paired with EoH, it improves all six constructive test sets at both evaluation budgets; when paired with Sample, it improves nine of twelve matched comparisons. Across constructive and ACO-style settings, the approach improves 28 of 36 matched comparisons. Agentic ESOpt + EoH improves all six constructive heuristic design test sets at both evaluation budgets. Agentic ESOpt + Sample improves nine of twelve matched comparisons, with one tie and two regressions. Across both constructive baselines, Agentic ESOpt improves 21 of 24 matched comparisons. In the T=1000 results, Agentic ESOpt + Sample shows the largest relative gains on TSP instances and smaller mixed changes on KP and ASP instances.

Across agentic Sudoku, math reasoning, web navigation, and heuristic design tasks, Agentic ESOpt is evaluated against PPO, GRPO, and baseline skill or search methods. It maintains higher success at long planning horizons while using substantially less GPU memory, training compute, and wall-clock time than PPO and GRPO, and sigma decay contributes to that advantage. Agentic ESOpt also improves Qwen3.5-4B results on math reasoning and DocVQA, improves Qwen3.5-27B WebArena-Lite performance especially when combined with Trace2Skill, and enhances existing heuristic design search methods in most matched comparisons.