acceptodds
Under review as a conference paper at ICLR 2027

TreeRollout: Resource-Aware Tree Sampling for Efficient Agentic LLM Post-Training

Abstract

Generating rollouts is a major cost in group-based reinforcement learning and rejection sampling for large language models. In agentic tasks, each trajectory alternates between GPU decoding and tool execution. The independence of individual trajectories leads to continuously fluctuating demand for concurrent tool execution and GPU decoding, intermittently leaving GPUs or tool executors idle. Scheduling can improve resource utilization, but spare capacity can remain unused when no trajectory is ready to use it. We introduce TreeRollout, a rollout engine that adapts trajectory generation to current GPU and tool bottlenecks by expanding policy-sampled trajectories into a tree. When tools are saturated, it branches after completed tool responses, reusing tool work to supply ready decoding work. When decoding becomes the bottleneck, the engine spawns new branches for tool calls from selected reasoning prefixes, enabling more frequent tool invocation with reduced reasoning overhead. We evaluate TreeRollout on different benchmarks covering math, search, and code generation. Given the same rollout time, TreeRollout yields significantly more trajectories than the baseline, with speedups of up to 1.82× in GRPO and 1.63× in RFT, and the largest gains appearing under severely imbalanced GPU and tool resources. Beyond raw throughput, these additional rollouts also lift the final trained model’s task performance.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, Reinforcement Learning, Post-Training, Rejection Sampling, Agent, Deep Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dBnrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors introduce a sampling method called treerollout for RL training. They find that GPU and tool calling can bring one idle when another is full-used. They push the model to generate additional trajectory when this appear. I find the idea is interesting and the studied problem is important. However, some details are confusing and the method seems to have biased estimation on advantage of GRPO. I still doult the stablity of the method. I think more details should be claimed well.

Critical strengths
  1. The paper is well motivated. TreeRollout addresses resource underutilization during RL training, a common and practically important problem.
  2. The paper is well organized, and the figures help convey the approach clearly.
Critical weaknesses
  1. The proposed sampling procedure alters the distribution of model-generated outputs. Consequently, the resulting advantage estimates may be biased relative to those obtained with standard GRPO. The implications of this potential bias remain unclear.
  2. During batch rollout, greater resource contention can lead to more responses being sampled for certain instances. This allocation depends on runtime conditions and may devote excessive resources to particularly easy or difficult instances.
  3. The improvements reported in Table 1 appear marginal. Moreover, the evaluation compares only rollout time and does not report training time. Because TreeRollout generates additional trajectories, it may increase the computational cost of policy updates.
Questions for authors
  1. During policy updates, shared prefixes may contribute to the optimization objective multiple times. Could this disproportionately weight these prefixes, introduce optimization bias, or destabilize training? Have the authors observed such effects, and does the method require a smaller learning rate to remain stable?
  2. Generating alternative reasoning continuations after tool calls when the GPU is idle seems reasonable. However, what justifies selecting random branching points for tool calls when tool-execution resources are idle? Although the method imposes constraints on point selection, could this procedure still produce low-quality reasoning trajectories and adversely affect model performance?
  3. How many additional trajectories does TreeRollout generate, and which factors determine this number? To what extent do the performance gains arise from the sampling strategy itself, rather than simply from using more training data? If standard GRPO were trained on a comparable number of trajectories, how would its runtime and performance compare? The current ablation studies seem insufficient to distinguish these effects.
  4. What is the total end-to-end training time of TreeRollout, including both rollout generation and policy updates, and how does it compare with standard GRPO?
Reviewer_UD3oOpenReview ↗
Rating
2
Confidence
3(−1)
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper targets idle GPU and tool capacity during agentic GRPO/RFT rollouts. TreeRollout expands each prompt's GG policy-sampled "primary" trajectories into a tree of lower-priority "filler" branches whose placement depends on the current bottleneck. When tools are saturated, fillers fork after completed tool responses; when decoding is saturated, they fork at reasoning positions with a high tool-call probability. A primary-first scheduler, control-token injection, and early stopping keep fillers within the primaries' completion time, and all complete trajectories are used for training. On five math, code, and search benchmarks with Qwen3-4B and Gemma-4-E2B, the paper reports 31–81% higher token throughput, modestly lower rollout time, and comparable or slightly better task scores than linear rollouts.

Critical strengths
  1. Important problem and a new angle. Idle GPU and tool capacity, together with long-tail stragglers, are a real and growing cost in agentic post-training. Letting the current resource state decide where and when to branch, instead of only scheduling a fixed set of trajectories, is a new and practically relevant idea.

  2. Simple, low-overhead mechanisms with broad evaluation. Branching after completed tool responses reuses tool work already paid for, and fork points are chosen from token probabilities recorded during generation, so no extra decoding is needed. Primary-first dispatch protects the training batch. The evaluation covers five tasks, both GRPO and RFT, two model families, and a tool-capacity sweep.

Critical weaknesses

1.The reported rollout-time reductions are inconsistent with the method's own mechanism, so the efficiency claim is not causally supported.

By design, primaries keep baseline sampling and termination and are always dispatched first. Fillers are not free: the paper acknowledges that they consume KV memory, increase decode-step latency, and can hold non-preemptible tool slots, and a rollout batch only ends once fillers have completed or been truncated. For a fixed policy snapshot, per-round rollout time should therefore be at least the baseline's. The paper nevertheless reports large reductions. RFT-GSM8K drops from 38.2h to 23.5h (−38%, Table 1), the constrained-tool setting from 80.3h to 44.1h (−45%, Table 2), and adding tree sampling alone already lowers rollout time from 30.9h to 28.3h (Table 3).

Because rollout time is accumulated over two epochs of training, a likely explanation is that the trained policies differ, for instance becoming shorter after training on truncated or answer-forced fillers. That would be a training-dynamics effect, not a property of the rollout engine. Without a fixed-checkpoint, per-round comparison, the paper's central efficiency claim cannot be attributed to TreeRollout.

The headline metrics compound the problem. The abstract's "1.82×" is a token-throughput ratio, while its "1.63×" is a rollout-time ratio. Tokens/s rises almost by construction for a method that generates more, so it is a weak proxy for training efficiency. The paper claims "more trajectories in the same rollout time" but never reports trajectory counts or NxN_x. End-to-end time including updates is defined in App. B.3 but never reported, even though NxN_x can reach 96 versus 16, i.e. up to roughly 6× the update compute.

The task gains of 0.2–0.8 pt come from single runs and do not offset these concerns. Some tables also contain contradictory numbers. In Table 4, 0.059 candidates/s × 495 s ≈ 29 candidates, yet 2.48M output tokens are reported, i.e. about 85k tokens per candidate, above the 32k sequence cap. In Table 3, the baseline's "Tokens (k)" value of 142.2k is about three orders of magnitude below the ~3.2×10⁸ tokens implied by Table 1 (2.85k tok/s × 30.9h).

2. The evaluation omits alternative bubble-filling baselines, and the evidence that resource-awareness drives the gains is weak.

Comparing at a fixed number of epochs is reasonable, since fillers use otherwise idle capacity. The open question is whether tree branching fills that capacity better than simpler options at a matched rollout wall-clock budget. The most direct alternative is to keep more work in flight: more concurrent prompts, or larger nn with independent sampling. With only 8×16 = 128 concurrent trajectories for a 4B model on four GPUs, part of the "bubble" likely reflects low decode concurrency rather than a fundamental GPU–tool imbalance.

Partial and asynchronous rollout are the established remedies for long-tail idleness. Kimi k1.5 uses partial rollouts to carry unfinished long trajectories across iterations [1], and AReaL fully decouples generation from training to keep devices busy [2]. Neither is compared. Nor are the scheduling systems the paper itself cites, such as ThunderAgent [3], Heddle [4], and ARL-Tangram [5]. ARPO [6], which already branches after tool calls based on post-tool entropy, is not discussed, even though post-tool-response branching is one of TreeRollout's two core mechanisms.

The paper's own results point to long-tail filling rather than resource-aware placement as the main source of gains. In the non-artificial settings, tool capacity barely limits the baseline. Raising tool concurrency from 10 to 100 shortens baseline rollout time by only about 5% (46.6h → 44.2h). TreeRollout's gain is nearly the same in both settings (throughput ~1.31× vs. ~1.34×; rollout time ~1.13× vs. ~1.14×). It becomes large only after tools are artificially slowed 20× plus 5 s. This suggests that much of the benefit comes from filling the long tail, as seen in the baseline's late-stage decay in Figure 3, rather than from bottleneck-specific branch placement.

The paper does not report per-branch-type trigger statistics or measured idle fractions that could settle this. Figure 3 shows only the default setting, so it cannot support the claim that "gains come from resource-aware branching rather than tree sampling alone", and Figure 1 is a schematic rather than measured profiling. In Table 3, "+Placement" yields 1.9h and +0.4 pt in a single run. The all-branch/random ablation (App. C.3) also removes primary-first dispatch, so it cannot isolate the effect of placement.

References

[1] Kimi Team. Kimi k1.5: Scaling Reinforcement Learning with LLMs. https://arxiv.org/abs/2501.12599

[2] Wei Fu, Jiaxuan Gao, Xujie Shen, et al. AReaL: A Large-Scale Asynchronous Reinforcement Learning System for Language Reasoning. https://arxiv.org/abs/2505.24298

[3] Hao Kang, Ziyang Li, Xinyu Yang, et al. ThunderAgent: A Fast, Simple, and Program-Aware Agentic Inference System. ICML 2026. https://icml.cc/virtual/2026/poster/62040

[4] Zili Zhang, Yinmin Zhong, Chengxu Yang, et al. Heddle: A Distributed Orchestration System for Agentic RL Rollout. https://arxiv.org/abs/2603.28101

[5] Bangjun Xiao, Yihao Zhao, Xiangwei Deng, et al. ARL-Tangram: Unleash the Resource Efficiency in Agentic Reinforcement Learning. https://arxiv.org/abs/2603.13019

[6] Guanting Dong, Hangyu Mao, Kai Ma, et al. Agentic Reinforced Policy Optimization. https://arxiv.org/abs/2507.19849

Questions for authors
  1. Source of the rollout-time reduction. Primaries keep baseline sampling and termination rules and are always dispatched first, while fillers only add load. What mechanism, then, lets TreeRollout reduce cumulative rollout time, especially by 38% on RFT-GSM8K and 45% in the constrained-tool setting? Please report, at a fixed policy checkpoint, the per-round rollout wall-clock and primary completion time for Linear and TreeRollout. Please also show response length and tool calls per trajectory over training for both methods, so that engine effects can be separated from changes in the trained policy. Please also report end-to-end training time including updates, and correct Tables 3 and 4, whose token counts are inconsistent with the 32k sequence cap and with the totals implied by Table 1.

  2. Comparison with simpler bubble-filling strategies. Is resource-aware tree expansion better at filling idle capacity than keeping more independent work in flight? Under a matched rollout wall-clock budget, how does TreeRollout compare with (a) linear rollout with more concurrent prompts or a larger nn, and (b) a partial or asynchronous rollout baseline [1, 2]? Please report verified candidates per hour and final task scores with at least three seeds. Please also report how often each branch type (after a tool response vs. a tool-directed fork) is triggered, and how GPU and tool idle fractions compare with the baseline across tool capacities. A clear and consistent advantage in these comparisons would substantially raise my assessment.

References

[1] Kimi Team. Kimi k1.5: Scaling Reinforcement Learning with LLMs. https://arxiv.org/abs/2501.12599

[2] Wei Fu, Jiaxuan Gao, Xujie Shen, et al. AReaL: A Large-Scale Asynchronous Reinforcement Learning System for Language Reasoning. https://arxiv.org/abs/2505.24298

Reviewer_yig7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes TreeRollout, a resource-aware tree sampling framework designed to improve rollout efficiency in agentic LLM post-training. The method addresses resource underutilization caused by the alternating demands of GPU decoding and tool execution. Specifically, it dynamically selects branching points based on resource availability, reusing completed tool responses when GPUs are idle and generating tool-directed branches when tool executors have spare capacity. It further incorporates priority-based scheduling, control-token injection, and early stopping to manage additional trajectories. Experiments across mathematical reasoning, code generation, and question answering tasks under GRPO and RFT demonstrate improved rollout throughput and comparable or better downstream performance than baseline methods.

Critical strengths

The paper presents an interesting perspective on improving agentic RL efficiency by dynamically adapting rollout generation to GPU and tool resource availability. The proposed resource-aware tree sampling framework is intuitive and combines prefix reuse, adaptive branching, and scheduling in a unified design. The experiments cover multiple benchmarks and training paradigms (GRPO and RFT), demonstrating consistent improvements in rollout throughput while maintaining or improving downstream task performance.

Critical weaknesses
  1. Existing advanced agentic RL systems typically decouple GPU inference engines from sandbox/tool execution clusters, enabling asynchronous execution and independent resource scaling. It is unclear whether the proposed method remains beneficial in a fully decoupled system with sufficient concurrent rollouts.
  2. TreeRollout generates additional trajectories by forking from existing reasoning prefixes. It introduces correlations among trajectories and may limit exploration across different reasoning strategies.
  3. When GPU decoding becomes the bottleneck, TreeRollout creates tool-directed branches to utilize idle tool executors. However, these additional branches still consume GPU computation to generate tool calls and subsequent reasoning. Under GPU saturation, does this strategy actually improve completed-trajectory throughput, or does it merely increase tool utilization at the expense of additional GPU workload?
Questions for authors
  1. What are the advantages of reasoning-level forking over generating additional independent rollouts? Under the same GPU compute budget, does fork-based sampling provide more effective training signals while preserving sufficient reward diversity?
  2. The experiments use vLLM 0.11.0, whereas more recent versions have introduced further improvements in automatic prefix caching, KV cache management, and KV transfer. Given that part of TreeRollout's efficiency gains comes from prefix reuse, could the authors clarify whether automatic prefix caching is enabled in the baseline? More importantly, how much additional benefit does resource-aware branching provide beyond existing caching mechanisms when evaluated with a modern vLLM backend?
  3. The paper primarily evaluates efficiency using rollout generation time and token throughput. However, additional filler trajectories also introduce verification, candidate selection, and policy-update overhead. Therefore, higher generation throughput does not necessarily translate into better end-to-end training efficiency. Could the authors compare end-to-end training time, completed trajectories per second, and total computational cost required to reach the same performance level under matched GPU and sandbox resource budgets?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.