Agentic Reinforcement Learning (RL) enables LLMs to solve complex tasks by alternating between a data-collection rollout phase and a policy training phase. During rollout, the agent generates trajectories, i.e., multi-step interactions between LLMs and external tools. Yet, frequent tool calls induce long-tailed trajectory generation that bottlenecks rollouts. This stems from step-centric designs that ignore trajectory context, triggering three system problems for long-tail trajectory generation: queueing delays, interference overhead, and inflated per-token time. We propose Heddle, a trajectory-centric system to optimize the when, where, and how of agentic rollout execution. Heddle integrates three core mechanisms: trajectory-level scheduling using runtime prediction and progressive priority to minimize cumulative queueing; trajectory-aware placement via presorted dynamic programming and opportunistic migration during idle tool call intervals to minimize interference; and trajectory-adaptive resource manager that dynamically tunes model parallelism to accelerate the per-token time of long-tail trajectories while maintaining high throughput for short trajectories. Evaluations across diverse agentic RL workloads demonstrate that Heddle effectively neutralizes the long-tail bottleneck, achieving up to 2.5× higher end-to-end rollout throughput compared to state-of-the-art baselines.
Figures & tables
Figure 1. Illustration of the agentic trajectory and the straggler effect.
Figure 2. Long-tailed distribution of coding agents.
Figure 3. Existing agentic RL framework.
Figure 4. CDF of normalized agentic trajectory completion time.
Figure 5. Trajectory length distribution across different prompts.
Figure 6. Interference of long-tailed trajectories.
Figure 7. Performance under different resource allocation strategies.
Figure 8. Overview of Heddle .
Figure 9. Progressive trajectory prediction.
Figure 10. Illustration of the placement algorithm.
Figure 11. Insight of heterogeneous resource allocation.
Figure 12. Rollout throughput of agentic RL systems under different workloads and models.
Figure 13. Precision of progressive trajectory prediction under different workloads and models.
Figure 14. Performance of trajectory-level scheduler.
Figure 15. Performance of trajectory-aware placement.
Figure 16. Performance of trajectory-adaptive resource management.
Models
Coding
Search
Math
Qwen3-8B
Tool Exec. (s)
0.46
1.42
0.051
Pred. (s)
0.103
0.15
0.26
Migration (s)
0.26
0.12
0.24
Qwen3-14B
Tool Exec. (s)
0.41
1.41
0.046
Pred. (s)
0.099
0.15
0.27
Migration (s)
0.27
0.15
0.25
Table 1. Prediction and migration overhead in Heddle .
Reinforcement learning (RL) has emerged as a standard post-training paradigm for shaping large language models (LLMs) into capable agents. In agentic RL, the rollout stage generates trajectories while invoking tools, producing long-tailed and non-stationary workloads that expose two fundamental challenges. First, due to the long-tailed response distribution, a small fraction of trajectories dominates rollout makespan.Second, rollout and training differ in their compute patterns, memory demands, and sensitivity to sequence length. As the policy evolves, shifts in the workload distribution further change their relative resource demands, making it difficult to maintain balanced execution across the two stages. We present Libra, an adaptive runtime for agentic RL post-training with two complementary components: (1) intra-stage scheduling via a Causality-Guided Bucket Scheduler that routes requests across execution buckets with different parallelism configurations, reducing delays from rollout stragglers; and (2) cross-stage coordination that dynamically reallocates workers between rollout and training as the workload changes. It moves workers between the two stages through a non-blocking protocol without interrupting ongoing training. Evaluated on a 48x NVIDIA A800 GPU cluster and a 160x Ascend 910B3 NPU cluster across three agentic benchmarks, Libra achieves up to 4.2x higher throughput and up to 2.7x faster reward convergence
Kaiwen Chen, Xin Tan, Jingzong Li +6
The Chinese University of Hong Kong · The Hang Seng University of Hong Kong · Independent Researcher
Agentic reinforcement learning (RL) is commonly used to enhance the capabilities of large language models (LLMs) in solving complex multi-turn tasks. During rollout, agentic RL exhibits a workload pattern distinct from that of traditional RL: multi-turn interactions repeatedly introduce prefill requests, causing prefill and decode workloads to coexist throughout rollout. This workload makes prefill-decode (PD) disaggregation, a design widely used for online LLM serving, promising for speeding up agentic RL rollout. This paper shows that PD disaggregation can improve rollout efficiency by (a) mitigating interference among data-parallel attention modules, (b) enabling stage-specific parallelism, and (c) reducing end-to-end trajectory completion time. However, a fixed prefill-decode allocation may fail to sustain these benefits as workload composition varies across tasks and over time. We therefore present Prorsa, an agentic RL framework for prediction-guided prefill-decode resource allocation. Prorsa observes the lifecycle of every trajectory to forecast short-horizon prefill and decode demand. These forecasts then guide worker allocation decisions and trigger role switching of rollout engines, aligning prefill and decode capacity with anticipated workload demand. Across synchronous and asynchronous agentic RL settings, Prorsa achieves end-to-end rollout speedups of 1.11x-4.05x over prefill-decode colocation.
Chiheng Lou, Xiangwei Deng, Bangjun Xiao +4
†School of Computer Science, Peking University · ‡LLM-Core Xiaomi
Long-horizon rollout generation has become the dominant systems bottleneck in agentic reinforcement learning (RL). As agents interact with environments over many turns, trajectories rapidly grow to tens of thousands of tokens, making synchronous RL training increasingly constrained by rollout. We propose WAR, a workload-aware rollout system that substantially accelerates synchronous agentic RL by jointly optimizing decoding and scheduling. WAR is built on a key observation: the optimal rollout optimization strategy depends on runtime load: (1) Under low load, WAR enables model-free speculative decoding with SuffixDecoding, which reuses suffix patterns from previously completed trajectories as speculative drafts for future rollouts. Unlike model-based drafters, SuffixDecoding introduces no additional draft model and avoids GPU contention with rollout generation. (2) Under high load, where saturated batched decoding leaves limited room for speculative speedup, WAR shifts the optimization focus to cache-aware scheduling. A global scheduler places requests across rollout replicas based on cache locality, trajectory progress and server load, reducing redundant KV-cache recomputation and mitigating load imbalance. By combining decoding-level suffix reuse with system-level rollout scheduling, WAR delivers robust throughput improvements across workload regimes without changing the underlying RL algorithm. WAR improves long-context agentic rollout throughput by 1.4x under low load and up to 1.6x under high load. These results show that WAR removes a major rollout bottleneck in synchronous agentic RL and provides a practical path toward scalable long-context agent training.