The 80% Compute Waste Problem in Agentic RL: Peking University Rewrites Scheduling with a "Trajectory-Centric" Approach
> Paper: Heddle: A Distributed Orchestration System for Agentic RL Rollout > Authors: Yinmin Zhong, Jiaming Liu, et al. (Peking University, ByteDance) > arXiv: 2603.28101 > Code: No standalone open-source repo yet, but implemented on top of Verl + SGLang + Ray
---
A Number That Won't Let You Sit Still: 80%
If you've ever trained with Agentic RL—letting an LLM agent interact multi-step with an environment, call tools, and collect trajectories for reinforcement learning—you've almost certainly run into this scenario:
The cluster is running fine, and then suddenly all GPUs go idle. Nothing crashed—they're waiting. Waiting for the single longest trajectory to finish.
The Peking University and ByteDance team quantified this phenomenon: in Agentic RL training, the rollout phase consumes over 80% of the total training time. It's not that training is slow—it's that data collection is slow. And it's not that data collection itself is slow—it's the "long-tail trajectories" in data collection that drag everyone down.
That number made me sit up. 80% of compute wasted on waiting means that 80% of what you pay for your H100s is spent on idling.
How the Long Tail Emerges
Before understanding the problem, consider a fact: the trajectory length distribution in Agentic RL is severely long-tailed.
The paper includes a figure: on a coding agent task (CodeForces dataset), the trajectory completion time distribution is extremely skewed. The median trajectory might finish in tens of seconds, but the slowest one—due to repeated debugging, repeated sandbox calls, repeated code fixes—takes more than 4x the median time.
This is completely different from traditional LLM training. Traditional training feeds static data where each sample's length is controllable and predictable. Agentic RL trajectories are generated in real time through agent-environment interaction; their length depends on task difficulty, tool feedback, and agent policy—and you can't know in advance which trajectory will be long.
Worse still, in RL algorithms like GRPO, a single prompt requires sampling 16 trajectories for advantage estimation. Sampling at temperature 1.0 means: among 16 trajectories from the same prompt, lengths can differ by 10x. One trajectory passes the test cases and ends; another fails repeatedly, fixes repeatedly, calls tools repeatedly, and becomes a super long tail.
In synchronous frameworks, all trajectories must wait for the slowest one to finish before the next training round. That is the root of the 80% waste—the GPUs aren't too slow; they're waiting for the slowest trajectory.
The Old Paradigm: "Step-Centric"
How do existing Agentic RL frameworks (Verl, Slime, SGLang-router) handle this problem?
The answer is: they don't.
These systems inherit their design from traditional LLM serving—scheduling at the granularity of a "step." Every time an agent invokes the LLM for generation, it's an independent inference request. The system assigns the request to some worker, the worker generates and returns, the agent gets the result and calls a tool, and after the tool returns, the agent issues the next LLM request.
Each step is scheduled independently. The system has no idea where a trajectory came from, where it's going, or how far it has left.
This causes three fatal problems:
1. Queueing latency (T_queue): Long-tail trajectories must re-queue at every step. Under round-robin scheduling, they compete for the same queue slots with short trajectories that finish in 2-3 steps. The result: long-tail trajectories queue and wait repeatedly, accumulating massive latency.
2. Interference overhead: Long-tail and short trajectories are mixed on the same worker. Long-tail trajectories have large batches that squeeze compute away from short trajectories, slowing them down too. This is the classic problem of GPU resource contention.
3. Per-token time inflation (T_base): All workers use homogeneous configurations (e.g., all MP=1 or all MP=8). MP=1 has high throughput but long per-token times for long-tail trajectories; MP=8 has short per-token times but low throughput. You can only pick one, and either choice is wrong.
Heddle's Approach: "Trajectory-Centric"
Heddle's core innovation is a shift in perspective: global management that moves from "step-centric" to "trajectory-centric."
This is not a parameter-tuning optimization but a redesign of the system architecture. Heddle unifies three previously independent decisions—when to schedule, where to place, and how to allocate resources—and optimizes them all at the trajectory level.
1. When to Schedule: Progressive Priority Scheduling
Heddle's first mechanism addresses queueing latency.
Traditional schedulers use FCFS, Round-Robin, or SJF (shortest job first). All these policies have a problem: they need to know trajectory lengths in advance. In Agentic RL, you don't.
Heddle's solution: progressive prediction + dynamic priority.
It trains a lightweight prediction model that continuously updates its length estimate during trajectory execution. It predicts once after the first step, refines after the second, and so on—as the trajectory unfolds, predictions get more accurate.
Based on this prediction, Heddle gives long-tail trajectories higher priority—letting them jump the queue and execute directly. This is the opposite of SJF: SJF prioritizes short jobs, Heddle prioritizes long ones. Why? Because short jobs finish quickly even if queued, but queueing long jobs is a disaster.
Experiments show this scheduling policy reduces end-to-end rollout time by 1.1-1.26x. The key gains come from reduced queueing latency—long-tail trajectories no longer queue repeatedly.
2. Where to Place: Trajectory-Aware Physical Isolation
The second mechanism addresses interference overhead.
Traditional placement policies are either cache-affinity (pin a trajectory to one worker to preserve KV cache) or least-load (send requests to the most idle worker). The former causes load imbalance (long-tail trajectories pile onto one worker); the latter causes frequent cache invalidation (switching workers every step destroys the KV cache).
Heddle's approach: presorted dynamic programming + runtime migration.
Presorted DP: Heddle first sorts all trajectories by predicted length, then uses a dynamic programming algorithm to find an optimal grouping—assigning trajectories to m workers such that each worker's "longest trajectory × interference factor" is as balanced as possible.
There's an elegant mathematical insight here: there exists an optimal solution where each group is a contiguous subsequence of the sorted trajectory list (Lemma 5.0). This lemma compresses the search space from the Stirling number S(n,m) (combinatorial explosion) down to C(n-1, m-1) (polynomially solvable). Combined with DP, complexity drops to O(n²m)—for n=6400 and m=16, it completes in 42 milliseconds.
Runtime migration: Predictions have errors, and the initial placement may be wrong. During trajectory execution, if Heddle detects a significant update in predicted length, it migrates the trajectory's KV cache via GPU-Direct RDMA to a more suitable worker.
A key engineering detail: migration happens during tool-call gaps. When the agent calls a tool, the GPU is idle. Heddle uses this idle window to transfer the KV cache asynchronously without blocking the critical path. It's an elegant "hidden overhead" design.
3. How Many Resources: Trajectory-Adaptive Resource Management
The third mechanism addresses per-token time inflation.
Traditional systems use homogeneous worker configurations. Heddle proposes heterogeneous ones: assign high model parallelism (short per-token time) to long-tail trajectories and low model parallelism (high throughput) to short trajectories.
It's a classic trade-off: MP=1 workers have high throughput but slow per-token speed; MP=8 workers are fast per token but low throughput. Heddle deploys both worker types simultaneously—routing long-tail trajectories to high-MP workers and short trajectories to low-MP workers.
How is the GPU budget divided? Heddle uses sorting-initialized simulated annealing to search for the optimal allocation. It starts by randomly sampling a set of MP configurations, sorting them, and aligning them with trajectory groups (long trajectories get high MP). Then simulated annealing searches—each step randomly perturbs (redistribute/split/merge); moves that reduce makespan are accepted, and moves that increase it are sometimes accepted with a probability (to escape local optima).
The evaluation function in this search is the presorted DP algorithm—each perturbation runs a DP to compute the makespan. One DP costs 42ms; simulated annealing runs a few hundred iterations, totaling about 5 seconds. But these 5 seconds are executed periodically and can be amortized over many training rounds, making the impact negligible.
Experimental Results: 2.5x Throughput
Heddle was comprehensively evaluated on a 64-GPU Hopper cluster (8 nodes × 8 GPUs).
Three task domains: coding agents (CodeForces), search agents (HotpotQA), math agents (DAPO-Math).
Three model scales: Qwen3-8B, 14B, 32B.
Baselines: Verl, Verl* (Verl + SGLang-router hybrid policy), Slime.
Results:
| Comparison | Heddle speedup | |------|----------------| | vs Verl | 1.4x – 2.3x | | vs Verl* | 1.1x – 2.4x | | vs Slime | 1.2x – 2.5x |
Up to 2.5x throughput improvement. And the larger the model, the bigger the gain—because larger models suffer more compute and memory contention, the interference factor of long-tail trajectories is higher, and Heddle's trajectory-aware placement pays off more.
Ablation: Contribution of Each Component
- Scheduler: 1.1-1.26x speedup, mainly from reduced queueing latency
- Placement policy: 1.2-1.5x speedup, outperforming cache-aware and least-load baselines
- Resource manager: 1.1-1.3x speedup, outperforming Fix-1 (throughput-optimized) and Fix-8 (latency-optimized)
- Scheduling: from "who gets the next step" to "how is this trajectory arranged"
- Placement: from "where does this request go" to "where does this trajectory go"
- Resources: from "all workers identical" to "different trajectories get different resources"
The three components stack multiplicatively. That is the systemic advantage of being "trajectory-centric"—each component addresses a different dimension of the same problem.
Engineering Details: A Few Practices Worth Learning From
1. A Rust-implemented Agentic Trajectory Router
Heddle's router is written in Rust and maintains trajectory metadata (placement assignments, predicted lengths, presorted ranks). Why Rust? Because the router sits on the critical path—every step queries it, and latency must stay in the microsecond range. Python can't do it; Rust can.
2. Asynchronous Migration During Tool-Call Gaps
This is the most elegant engineering detail in the paper. When the agent calls a tool, the worker's GPU is idle. Heddle uses this window for KV cache migration—transferring the trajectory's prefix cache via RDMA to the target worker. By the time the tool call ends and the agent returns to generate the next step, the migration is already done, and the GPU continues on the new worker directly.
Effectively, migration happens "for free"—no extra overhead, because it fills a window that would have been idle anyway.
3. Profiler-Based Simulation of the Interference Factor
The interference factor F has no analytical expression, so Heddle uses a profiler to sample per-token times at various batch sizes and then simulates the interference when a set of trajectories runs concurrently. A pragmatic choice—not chasing theoretical optimality, but engineering usability.
4. Short-Trajectory Aggregation for Faster Planning
The presorted DP is O(n²m), still somewhat slow at n=6400. Heddle aggregates short trajectories below a threshold into a single "super trajectory," reducing the effective input size. This doesn't affect placement decisions for long-tail trajectories (short trajectories can go anywhere), but it significantly speeds up the algorithm.
Orthogonality to Other Techniques
In its Discussion section, the paper examines Heddle's relationship with three other techniques, and this discussion is quite valuable:
Asynchronous RL: Async RL improves throughput via partial rollout but needs staleness thresholds to prevent gradient bias. Heddle integrates seamlessly with async RL—accelerating long-tail trajectories introduces no additional policy divergence.
PD Disaggregation: Prefill-Decode disaggregation uses different MP levels between prefill and decode phases, but within each phase configurations remain homogeneous. Heddle can further perform heterogeneous allocation within the prefill phase—giving long-tail trajectories higher MP.
Speculative Decoding: Speculative decoding uses a small model to draft tokens and a large model to verify in parallel. But for prefill-heavy Agentic RL tasks (short generations, frequent tool calls), SD performs poorly. Heddle optimizes the prefill phase and is orthogonal to SD—they can be combined.
This "orthogonal to existing techniques" property shows that Heddle's design is a system-level incremental innovation—not competing with existing frameworks, but layerable on top of them.
My Take: A Paradigm Shift from "Step" to "Trajectory"
This paper points to a broader trend: the granularity of LLM system design is shifting from "single inference" to "complete interaction."
Traditional LLM serving optimizes the throughput and latency of a single inference—batch size, KV cache, model parallelism are all designed around "one generation."
But Agentic RL isn't a single generation—it's a trajectory composed of many generations, many tool calls, and many environment interactions. If you keep optimizing at the granularity of "single inference," you'll forever spin in local optima—every step is fast, but the whole trajectory is slow.
Heddle's contribution is elevating the optimization granularity to the trajectory level. This isn't a technical detail; it's a paradigm choice:
This shares structural similarities with CodeRescue (a coding-agent recovery routing paper I wrote about earlier)—CodeRescue also elevates decisions from "single failure" to the "recovery action" level. Both papers point in the same direction: in the agent era, a system's unit of optimization must upgrade from "call" to "trajectory."
Deeper still: this may be a universal principle of agent system design. Agent behavior isn't discrete calls—it's continuous trajectories. The granularity you optimize determines the problems you can see. Step-centric, you see queueing latency and cache hit rates; trajectory-centric, you see long-tail effects and resource heterogeneity. The former is tactics; the latter is strategy.
Heddle's real lesson isn't the specific conclusion "prioritize long-tail trajectories" but rather: the granularity at which you optimize a system should match the granularity of the object being optimized. Agents are trajectory-level entities, so system design should be trajectory-level too. This idea generalizes across agent systems—monitoring, debugging, evaluation, and billing should all be measured per trajectory, not per call.
Limitations
The paper honestly acknowledges several limitations:
1. Predictor depends on runtime context: First-step predictions have limited accuracy; Heddle-1's recall is notably worse than Heddle-2's. This means early-trajectory scheduling decisions may be inaccurate. 2. The interference factor is empirically modeled: The F function has no analytical form and relies on profiler sampling. Different hardware and models may require re-profiling. 3. Heterogeneous resource management uses simulated annealing: Not guaranteed globally optimal, only near-optimal. The 5-second overhead is amortizable, but may still be too slow for extremely latency-sensitive scenarios. 4. Only evaluated at 64-GPU scale: Behavior at much larger scales (hundreds to thousands of GPUs) is unknown. The O(n²m) DP takes 42ms at n=6400—what about n=64000?
These limitations aren't fatal, but they outline Heddle's applicability boundary: medium-to-large Agentic RL training, severely long-tailed trajectory length distributions, and hardware supporting RDMA migration. Within that range, Heddle's gains are real.
Conclusion
Agentic RL is one of the most cutting-edge training paradigms in AI today. Behind products like Claude Code, Deep Research, and OpenClaw, Agentic RL is driving LLMs to learn multi-step reasoning and tool use.
But this paradigm's training-efficiency problem has never been systematically solved. Heddle's contribution isn't inventing a new algorithm—it's identifying the essence of the problem—long-tail trajectories—and delivering a complete solution at the system architecture level.
80% compute waste is not a problem you can solve by tuning parameters. It requires rethinking scheduling granularity, placement strategy, and resource allocation. Heddle did that rethinking and proved its value with a 2.5x throughput improvement.
The next time you train Agentic RL and can't get GPU utilization up, first look at your trajectory length distribution. If it's long-tailed—and it probably is—what you need isn't more GPUs, but a trajectory-centric scheduling system.
---
Paper link: https://arxiv.org/abs/2603.28101 Baseline frameworks: Verl | Slime | SGLang
---
*When you find your GPUs waiting, first ask: what are they waiting for? The answer is most likely—a long-tail trajectory.*