Asynchrony Is Nearly Free for Evolution Strategies on Long-Horizon LLM Agentic Tasks

William Hoy; Jingxuan Fan; Nurcin Celik; Xu Pan

cs.AIOct 3, 2026

Asynchrony Is Nearly Free for Evolution Strategies on Long-Horizon LLM Agentic Tasks

Authors: William Hoy, Jingxuan Fan, Nurcin Celik, Xu Pan

Organizations: University of Miami · Harvard University

Abstract

Synchronous policy updates can limit the efficiency of post-training for long-horizon LLM agents. When trajectories span multiple interaction turns, completion times can vary substantially, and synchronous update barriers leave faster workers idling, wasting compute resources. Asynchronous reinforcement learning addresses this inefficiency but introduces policy lag and off-policy optimization. Evolution strategies (ES) are a backpropagation-free alternative to gradient-based training, yet require many perturbed-policy evaluations and have remained largely synchronous in current LLM post-training. We introduce bounded-staleness asynchronous ES and investigate its training behavior under stale fitness measurements. On WebShop, we systematically vary the lag and fraction of stale fitness measurements and additionally introduce two stress tests to probe extreme staleness cases. Natural asynchrony closely tracks synchronous ES, and degradation in evaluation accuracy remains small even under extreme staleness, including when all fitness measurements are stale. These findings suggest that ES can tolerate substantial policy staleness without explicit off-policy correction, supporting its use in asynchronous post-training for long-horizon LLM agents.

Figures & tables

Figure 1: WebShop rollout workload and asynchronous dispatch. Left: rollout-batch durations for synchronous ES with 32 tasks per perturbation, pooled across training. Right: synchronous and asynchronous scheduling with four workers and an eight-result update cohort. Asynchronous ES updates after eight accepted evaluations complete while other evaluations remain in flight.

Figure 2: WebShop

16\times 16

exact success on the fixed 128-task eval set at update 200. Controlled Lag-4/8 sub-rows are ordered by stale fraction: 18.75%, 50%, and 100%. Tail conditions mix fresh and delayed evaluations. Each point represents one training run.

Figure 3: WebShop

16\times 16

staircase test. Brackets link evaluations around

\theta_{0}

to consumption at updates 33, 65, and 129, with lags 32, 64, and 128. Staircase fitness is raw; reference fitness shows five-update trailing means with faint raw values.

Method	MMLU-Pro	HellaSwag
Base	0.5894	0.8018
Synchronous ES	0.5586	0.7603
Natural Async-1 ES	0.5410	0.7559
Lag-4 (18.75% stale)	0.5293	0.7349
Lag-8 (18.75% stale)	0.5181	0.7651
Lag-4 (50% stale)	0.5371	0.7695

Table 1: General-capability retention after WebShop post-training with ES (

16\times 16

), initialized from Qwen3-4B-Instruct-2507. All methods are evaluated after 200 updates. Base-model accuracies are 0.5894 on MMLU-Pro and 0.8018 on HellaSwag. Each final checkpoint uses the same 2,048 examples per benchmark and greedy decoding.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Configuration	Schedule	Fresh	Lag 1	Lag 2	Lag 4	Lag 8	Lag 32	Lag 64	Lag 128
$30\times 32$	Tail-32	15	3	2	2	6	2	0	0
	Tail-64	15	3	2	2	4	2	2	0
	Tail-128	15	3	2	2	2	2	2	2
$16\times 16$	Tail-32	8	2	1	1	3	1	0	0
	Tail-64	8	2	1	1	2	1	1	0
	Tail-128	8	2	1	1	1	1	1	1

Appendix

Table 2: Number of accepted perturbation evaluations at each policy lag in the long-tail cohorts.

Figure 4: WebShop

16\times 16

ES learning curves through update 200. Left: training fitness. Right: eval success. Sync and Async-1 are repeated as references across schedule groups. Non-staircase fitness uses five-update trailing means; staircase fitness is raw. Each condition represents one training run.

Condition	Peak success (%)	Peak update	Final success (%)
Sync	72.66	200	72.66
Natural Async-1	75.00	170	71.88
Lag-4, 18.75% stale	72.66	140	72.66
Lag-4, 50% stale	73.44	200	73.44
Lag-4, 100% stale	73.44	160	71.09
Lag-8, 18.75% stale	74.22	200	74.22

Appendix

Table 3: WebShop

16\times 16

exact success on the fixed 128-task set. Peak is the highest logged scheduled evaluation over training, with ties assigned to the earliest update. Final is update 200. Each condition represents one training run.

Figure 5: WebShop

30\times 32

exact success on the fixed 128-task eval set at update 200. Controlled Lag-4/8 sub-rows use fractions of 10%, 50%, and 100%. Tail conditions mix fresh and delayed evaluations. Each point represents one training run.

Figure 6: WebShop

30\times 32

staircase stress test. Brackets link evaluations around

\theta_{0}

to consumption at updates 33, 65, and 129, with lags 32, 64, and 128. Staircase fitness is raw; reference fitness shows five-update trailing means with faint raw values.

Figure 7: WebShop

30\times 32

Condition	Peak success (%)	Peak update	Final success (%)
Sync	73.44	180	72.66
Natural Async-1	77.34	190	73.44
Lag-1, 50% stale	73.44	150	70.31
Lag-1, 100% stale	75.00	190	73.44
Lag-4, 10% stale	71.88	170	71.88
Lag-4, 50% stale	72.66	180	71.09

Appendix

Table 4: WebShop

30\times 32

Figure 8: WebShop

30\times 100

ES learning curves through update 120. Left: training fitness Right: eval success Async-1 denotes natural asynchrony; controlled Lag-4 and Lag-8 use 10% stale evaluations. Each condition represents one training run.

Condition	Peak success (%)	Peak update	Final success (%)
Sync	75.00	100	74.22
Natural Async-1	73.44	90	69.53
Lag-4, 10% stale	72.66	120	72.66
Lag-8, 10% stale	72.66	90	71.88

Appendix

Table 5: WebShop

30\times 100

exact success on the fixed 128-task set. Peak is the highest logged scheduled evaluation over training, with ties assigned to the earliest update. Final is update 120. Each condition represents one training run.

Figure 9: WebShop GRPO learning curves through update 100. Left: training reward Right: eval success Each condition represents one training run.

Condition	Peak success (%)	Peak update	Final success (%)
Synchronous GRPO	78.91	90	77.34
Natural Async-1 GRPO	82.81	100	82.81
Controlled Lag-4 GRPO (100% stale)	82.03	100	82.03
Controlled Lag-8 GRPO (100% stale)	71.88	100	71.88

Appendix

Table 6: WebShop GRPO exact success on the fixed 128-task eval set. Peak is the highest success, with ties assigned to the earliest update; final is update 100. Each condition represents one training run.

Base and GRPO
Method	Updates	MMLU-Pro	$\Delta$	HellaSwag	$\Delta$
Base	–	0.5894	–	0.8018	–
Synchronous GRPO	100	0.5815	$-0.0078$	0.7988	$-0.0029$
Natural Async-1 GRPO	100	0.5811	$-0.0083$	0.7998	$-0.0020$
Controlled Lag-4 GRPO (100% stale)	100	0.5894	$+0.0000$	0.7974	$-0.0044$
Controlled Lag-8 GRPO (100% stale)	100	0.5869	$-0.0024$	0.8008	$-0.0010$

Appendix

Table 7: General-capability retention after WebShop post-training with GRPO and ES (

30\times 32

and

30\times 100

), initialized from Qwen3-4B-Instruct-2507.

\Delta

is the absolute accuracy change from the base model. Each final checkpoint uses the same 2,048 examples per benchmark and greedy decoding.

ES setup	Updates	Per update	Full run
$16\times 16$	200	$0.20\times$	$0.40\times$
$30\times 32$	200	$0.75\times$	$1.50\times$
$30\times 100$	120	$2.34\times$	$2.81\times$

Appendix

Table 8: Nominal ES compute relative to GRPO. The full-run reference is 100 GRPO updates.

Evolution Strategies

Evolution strategies are gradient-free, population-based methods that optimize black-box objectives through parameter perturbations and selection.

See all 34 papers

Agentic ESOpt: Fine-Tuning Long-Horizon LLM Agents with Minimal GPU Requirements
Aug 18, 2026Zhi Zheng, Rongsheng Chen, Yunpeng Ba +3LLM Agent Training Long-Horizon LLM Agents
National University of Singapore · Southern University of Science and Technology · Oxford
Where Does Staleness Accumulate? Pool Aware Effective Staleness Control for Asynchronous RL in LLM Post-Training
Sep 29, 2026Chenliang Li, Neiwen Ling, Zijun Wei +1Asynchronous RL RL for Language Model Reasoning
ByteDance · Texas A&M University · University of Virginia
Single-Rollout Asynchronous Optimization for Agentic Reinforcement Learning
Jul 8, 2026Zhenyu Hou, Yujiang Li, Jie Tang +1Agentic RL Asynchronous RL
Tsinghua University · Work done while ZH and YL interned at Z.AI.

Aug 18, 2026J/K move · Enter open · S save

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

Zhi Zheng, Rongsheng Chen, Yunpeng Ba, Zhenkun Wang+2

National University of Singapore · Southern University of Science and Technology · Oxford

LLM Agent Training Long-Horizon LLM Agents Evolution Strategies

Open paper AskPDF arXiv

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.

Abstract

Evolution Strategies

Explore similar work

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

Where Does Staleness Accumulate? Pool Aware Effective Staleness Control for Asynchronous RL in LLM Post-Training

Single-Rollout Asynchronous Optimization for Agentic Reinforcement Learning