Paper Explained: Agentic ESOpt — Drop Backprop, Jiggle the Weights, and Train Long-Horizon LLM Agents

No gradients at all: spawn G perturbed copies of the model, run them in the environment, and nudge the weights toward the ones that scored well. That buys full-parameter updates of a 27B agent at inference-level memory (8.41GB) — and a 12.50-point lead over GRPO on 15-move Sudoku. A ground-up walkthrough of the NUS-led paper.

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

Two ways to climb a mountain in fog

You're climbing toward a summit, but the fog is thick and you can see nothing. There are two ways forward.

One is to measure the slope under your feet precisely. If you learn that the ground rises slightly to the northeast, you step northeast. That is the gradient method — backpropagation, in neural network terms. It is accurate, but the instrument is heavy, and the bigger the model, the less able you are to carry it.

The other is to walk a few paces in a random direction, read your altitude, and walk back. Do that with a crew of companions all at once, and if the person who went northeast came back highest, everyone shifts a little that way. Nobody measured a slope, yet the group moves uphill. That is Evolution Strategies (ES).

What this paper (NUS, SUSTech, and Oxford, August 2026) argues is that for the specific job of fine-tuning long-horizon LLM agents, the second option is not merely cheaper — it is actually better. ES has long been treated as "slightly weaker than gradients but affordable"; the authors argue the ranking flips as the horizon grows, and they check that claim on Sudoku, tool use, web navigation, and automatic heuristic design.

The actual problem: dozens of moves, then a single pass/fail bit

First, the setting. An LLM agent repeatedly observes the environment and emits an action (§2).

$$a_{t}\sim\pi_{\theta}(a_{t}\mid \bm{o}_{\leq t},c_{t})$$

Or, in words: pick the next move at random from a distribution shaped by everything seen so far plus whatever instruction was handed in. Here $\theta$ is the model's parameters, $\bm{o}_{\leq t}$ is the interaction history so far, and $c_t$ is external guidance such as a prompt or a skill document. One episode produces a trajectory $\bm{\tau}=(o_1,a_1,\ldots,o_H,a_H)$, and $H$ — the horizon — is the number of agent–environment turns before termination.

The trouble is how reward arrives. Most of the tasks in this paper are sparse-reward: every intermediate $r_t$ is zero, and a single "solved / not solved" bit arrives at the end (§2). Thirty browser clicks, then one verdict. For the shape of these systems generally, see LLM agents, from the ground up.

Bring the conventional answer — RL-style post-training — into this setting, and you hit the two walls the paper describes (§1).

Wall 1: memory. GRPO and PPO must retain rollouts, hold activations and optimizer states, and backpropagate through trajectories. The larger the model, the less practical full-parameter training becomes. In this paper's own experiments, full-parameter Agentic RL on a 27B model simply did not fit on four H100 80GB GPUs (§5.2). The hardware side of that story lives in the GPU memory hierarchy.

Wall 2: credit assignment. That final bit has to be apportioned across dozens of intermediate actions. GRPO hands out a group-relative advantage

$$\widehat{A}_{i}=\frac{R_{i}-\operatorname{mean}_{j}(R_{j})}{\operatorname{std}_{j}(R_{j})+\varepsilon}$$

as one value for the whole trajectory — which says, in words: solve the same problem $G$ times and praise whole trajectories that beat the group average. The paper cites prior work finding that while this is representative in single-turn settings, it does not cover multi-turn ones (§2). PPO instead asks a critic for turn-level advantages — but the paper argues this is not a fix either. The critic needs a warm-up phase; sparse terminal rewards make its early advantages unreliable; and even with a well-trained critic, the policy gradient still sums $H$ action-level score terms, so its variance stays tied to horizon length (§2).

The pivot: perturb the model, not the actions

What Agentic ESOpt does is almost anticlimactically simple (§3).

1. Around the current parameters $\theta$, sample $G$ random perturbations $\bm{\epsilon}_i$
2. Run all $G$ "perturbed twins" in the real environment and collect only a scalar reward $R_i$ from each
3. Nudge the parameters toward the directions that scored well

No gradient is ever computed. The environment need not be differentiable, and trajectories need not be retained for a backward pass.

Why does this go uphill? The key is the dot product. A random direction $\bm{\epsilon}_i$ raises or lowers reward depending on how well it aligns with the direction that genuinely improves the policy. Better-aligned directions earn higher reward, and that reward becomes the weight on $\bm{\epsilon}_i$ in the sum — so a reward-weighted sum of random arrows ends up pointing somewhere useful.

Formally, the objective ES actually optimizes is not the raw $J(\theta;c)=\mathbb{E}_{\bm{\tau}}[R(\bm{\tau})]$ but a Gaussian-blurred version of it.

$\sigma$ is the perturbation radius and $\bm{\epsilon}$ is standard Gaussian noise with the same dimension $d$ as the full parameter vector. Eq. (1), in words, measures how good the whole neighborhood around $\theta$ is on average, not how good one exact point is. ES climbs the average of the neighborhood.

The gradient of that objective can, remarkably, be written using nothing but rewards times noise (§3; derivation in Appendix C.1).

Put in words: average "the direction you jiggled × the score that came back," and you have a stand-in for the gradient. Nothing anywhere differentiates the model.

In practice the $G$ rewards are z-scored within the population ($\hat R_i=(R_i-\mu_R)/(s_R+\varepsilon)$) before being summed. The paper's implementation drops the canonical $1/\sigma$ factor, so $\alpha$ serves as the effective update scale (§3).

That is the entire update, and in words it says: step a distance $\alpha$ toward the twins that did well, and away from the ones that did badly. Because z-scoring makes $\hat R_i$ negative for below-average twins, the bottom of the population automatically pushes in the opposite direction.

And here is the part that matters most in practice: memory. Each perturbation is stored as nothing but its random seed, regenerated from that seed whenever needed, and applied and reverted with in-place addition and subtraction. So training requires exactly as much GPU memory as inference (§3) — no activations, no optimizer states, no reference model. On the Sudoku experiment with Qwen3.5-4B, GRPO needs 58.88GB while Agentic ESOpt needs 8.41GB: the same as inference, and 85.7% lower (§4, Table 1).