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

The core claim here is that evolution strategies beat reinforcement learning for fine-tuning LLM agents not because they are cheaper, but because they are structurally better matched to long-horizon tasks. The argument is precise: RL estimators accumulate action-score terms across every turn of a trajectory, so their variance grows roughly linearly with horizon length. ES samples one parameter perturbation for the entire rollout and scores it against the terminal reward, so the parameter-score factor contains no sum over turns. As horizons lengthen and rewards grow sparse, that structural difference compounds.

The Sudoku experiments make this concrete in a way that is hard to dismiss. At a minimum successful horizon of 5 turns, PPO leads. At 10, GRPO edges ahead. At 15, Agentic ESOpt reaches the top by 12.5 percentage points over the strongest GRPO configuration, while PPO essentially collapses because its critic cannot learn a reliable value signal from sparse terminal rewards alone. The ordering reversal across three horizon lengths is the real result — it is consistent with a horizon-dependent advantage regime, not a globally stronger optimizer.

The memory story is equally concrete. Agentic ESOpt requires only 8.41 GB to train Qwen3.5-4B — identical to inference — versus 58.88 GB for GRPO. That gap is what allows full-parameter adaptation of a 27B model on four H100 GPUs, something full-parameter RL cannot do on the same hardware. On WebArena-Lite, the 27B model improves from 29.47% to 36.16% with no-skill prompting, and combining with Trace2Skill pushes it to 36.36%.

The FLOPs accounting is careful. ES requires a larger population — 32 perturbation directions versus 8 GRPO rollouts in the Sudoku comparison — but each trajectory needs only a forward pass rather than the roughly four forward-pass equivalents that GRPO demands. The paper shows these cancel at matched trajectory lengths, and that GRPO's credit-assignment failures actually cause longer trajectories, making its real compute cost higher.

The flexibility argument is demonstrated rather than just asserted. Agentic ESOpt slots into EoH's outer evolutionary search for automatic heuristic design by attaching parameter updates only to mutation operators, leaving the rest of the scaffold unchanged. It improves 28 of 36 matched comparisons across six combinatorial optimization scenarios. The overhead is modest: attaching parameter updates adds 5 to 7.4 minutes to Sample runs that already take tens of minutes.

A preliminary population-sensitivity result suggests stronger backbones need smaller populations to get useful updates — the 9B model shows almost no improvement from doubling population size where the 4B model shows clear gains. The paper frames this as motivation for future scaling-law work rather than a settled finding, which is the right framing.

The one genuine limitation the paper names: ES trades backpropagation cost for more independent environment evaluations, so when environment rollouts themselves are expensive, the trade-off can flip. That caveat is stated plainly and is worth keeping in mind before applying this to any setting where simulation is the bottleneck.