- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes Process-Scorer Guided Adaptive Tree Rollout (PATR), a framework that improves multi-turn reinforcement learning for LLM agents by adaptively allocating exploration effort during rollout generation. Unlike standard GRPO, which samples multiple independent trajectories, PATR constructs tree-structured rollouts and uses intermediate process scores to identify high-quality trajectories for further expansion, allow moderately promising ones to continue, and terminate low-quality trajectories early.
Critical strengths
The paper addresses a challenging problem with the potential to improve the effectiveness of reinforcement learning-based fine-tuning for large language models.
Critical weaknesses
-
The paper does not mention what happens to the trajectories in the "Pruning" group, which are not terminated naturally but remain partial and are moved to "C" as they are. The authors state that they use these trajectories to train the policy. However, if these trajectories are not terminated, how can they use the task reward to assign rewards to them? As the paper mentions, the task reward is sparse and is only given at the end of a trajectory.
-
Scoring intermediate states in trajectories is a desirable approach, but it is very challenging. The authors use heuristics and other scoring methods for the benchmarks in their experiments, but there is no guarantee that good scorers can be found for other tasks, especially those that require deep reasoning about future outcomes.
-
The literature review is also shallow. There are many papers that study rollout efficiency for training LLMs with RL, but here we only see a short list of them. One of the missing ones is [1].
-
The authors mention that the heuristic score based on distance to the goal is very suitable for navigation-style tasks. However, there are numerous cases where this heuristic can be misleading, since reaching the goal may require the agent to first move away from it for some time before approaching it.
-
The authors cite [2] and claim that there is a similarity between their approach and the cited paper. However, the cited paper establishes a foundation for balancing the exploration-exploitation trade-off. The PATR framework only removes low-quality trajectories, and this is done every K steps rather than at every state.
-
The paper focuses on rollout budget efficiency but does not consider the computational overhead introduced by scoring trajectories using PRMs or LLM-as-judge scorers, even assuming that a good scorer is available before training.
-
GRPO was proposed to eliminate the need for a value function when training LLMs. However, the proposed method introduces an additional scorer, which raises questions about the fairness of comparing it with standard GRPO. Shouldn't the scorer require an evaluation similar to a value function in long-horizon tasks, since scoring intermediate trajectories requires accounting for outcomes that occur only at the end of the trajectory?
-
The authors mention TSR as one of the related works but do not include it as a baseline in their experiments. Given that both methods use tree structures and FrozenLake is also one of the tasks considered in the TSR paper, TSR should have been included as an experimental baseline.
-
In Figure 3, the authors claim that both versions of their method outperform the other baselines. However, the curves are very close, and the performance margins are not significant. Moreover, for each criterion, at least one other baseline appears to perform better than their method.
-
In Figure 2, the authors also claim that their method achieves higher completion rates during training. However, in the plots where their method achieves a higher completion rate, the margins are very small. In the other plots, depending on what is considered an early stage of training, other methods sometimes perform better.
1- TreeRL: LLM Reinforcement Learning with On-Policy Tree Search 2- Bandit based monte-carlo planning.
Questions for authors
Please refer to the weaknesses section. I put only one question here.
1- Can the authors show that generating tree-structured rollouts by terminating some branches and focusing on others does not change the distribution of the base rollout policy? This seems to be implicitly assumed in the paper, but I believe it may not hold.
8 comments
Response to Reviewer NUCM (2/4)
Response to Weakness 4
We agree that geometric distance can be misleading when reaching the goal requires temporarily moving away from it. However, our default FrozenLake scorer already accounts for this issue by using BFS shortest-path distance rather than geometric distance, as specified in Appendix A. Specifically, the scorer computes the shortest valid path to the goal with holes treated as obstacles. Therefore, following a necessary detour reduces the remaining shortest-path distance, even when the agent initially moves geometrically away from the goal.
We further evaluate precisely the failure case described by the reviewer in Appendix B (Table 6). We replace the default BFS scorer with a deliberately imperfect Manhattan-distance scorer that ignores holes and can incorrectly favor dead-end states or penalize necessary detours. Despite this limitation, PATR achieves success rates of 74.9%/74.5% for the 0.5B/3B models, comparable to the default BFS scorer (75.8%/74.3%), while outperforming all baselines. These results provide evidence that PATR remains effective even with imperfect distance-based guidance.
Response to Weakness 5
We thank the reviewer for highlighting this distinction. Kocsis and Szepesvári (2006) provide a principled framework for balancing exploration and exploitation. Our citation in Section 4.3 is intended to highlight the shared motivation of adaptive allocation of sampling effort, while PATR achieves this through a different mechanism based on intermediate process feedback. PATR does not simply remove low-quality trajectories, but incorporates both exploration and exploitation through three complementary operations, as described in Section 4.1 and Algorithm 1. Expansion allocates additional continuations to high-scoring branches, exploiting promising intermediate states while exploring multiple possible continuations. Survival preserves moderately scored branches for continued exploration and reassessment, rather than exclusively favoring the highest-scoring branches. Pruning terminates unpromising or repetitive branches early while retaining them for GRPO training. Together, these operations focus computation on promising states while maintaining alternative exploration paths.
Regarding the scoring interval, evaluating branches every turns is a deliberate design choice to balance adaptive rollout allocation with scoring overhead in long-horizon agent interactions. More frequent scoring enables earlier adjustments but incurs additional computation. We study this choice in Table 3, where the default achieves a 27.2% resolved rate on SWE-Bench, compared with 23.4% and 24.6% for and , respectively. We will clarify that PATR's periodic process-guided allocation differs from UCT's state-by-state selection mechanism.
Response to Weakness 6
We appreciate the reviewer highlighting the importance of accounting for auxiliary scoring costs. While PRM and LLM-judge inference introduce additional computation, PATR is designed to keep this overhead limited relative to long-horizon rollout generation.
First, process scoring is performed sparsely rather than at every interaction step. As described in Section 5.1 and Appendix A, PATR evaluates branches every (K) turns (K=5 for FrozenLake and K=13 for SWE-agent training), using compact recent trajectory context. The pretrained PRM performs forward-pass scoring without generating text, while the LLM judge produces only a short score response. Both are hosted on separate vLLM inference servers, avoiding GPU contention with policy rollout generation. Furthermore, shared-prefix reuse and early pruning reduce redundant rollout computation, partially offsetting the additional scoring cost. Using auxiliary reward or feedback models is an established practice in LLM reinforcement learning, as demonstrated by Math-Shepherd, PRIME, SPA-RL, and RLAIF [1–4]. Unlike methods that incorporate auxiliary feedback into the training signal, PATR uses the scorer only for sparse rollout allocation while retaining the original task reward and standard GRPO objective.
Empirically, our measurements show that PATR incurs only approximately 1.12× the end-to-end runtime of standard GRPO on SWE-agent training, including scoring overhead. On FrozenLake, the lightweight heuristic requires no auxiliary model inference, and the overall runtime remains comparable to GRPO. These results indicate that PATR introduces a modest computational overhead while improving rollout allocation. We will include these measurements in the revised efficiency analysis.
[1]. Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations
[2]. Process Reinforcement through Implicit Rewards
[3]. SPA-RL: Reinforcing LLM Agents via Stepwise Progress Attribution
[4]. RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback
Response to Reviewer NUCM (3/4)
Response to Weakness 7
We understand the reviewer's concern that introducing an additional scorer may raise questions about GRPO's value-function-free training. We would like to clarify that GRPO eliminates the need for a learned value function in advantage estimation, and PATR preserves this property. As described in Sections 4.2 and 4.3, PATR uses a frozen process scorer solely to guide rollout allocation, without modifying the task reward, advantage estimation, or GRPO objective. The advantages in Eq. 8 are still computed exclusively from task-level outcome rewards, without introducing a learned critic.
Importantly, PATR does not require the scorer to estimate expected returns or provide calibrated predictions of long-horizon outcomes, as a value function aims to do. Instead, it only requires intermediate process scores that provide useful relative rankings of partial trajectories within the same task, identifying which branches are more promising for further exploration. The scorer does not need to predict their eventual outcomes or estimate future returns. We recognize that scorer quality matters, particularly for long-horizon tasks, and evaluate its effectiveness empirically. Tree-Random uses the same tree-rollout structure without process-guided selection, allowing us to assess the contribution of intermediate scoring. On SWE-Bench, both PATR-PRM (27.2%) and PATR-Judge (26.0%) outperform Tree-Random (24.8%) and standard GRPO (22.2%). Furthermore, Appendix B (Table 6) demonstrates that PATR remains effective with an imperfect Manhattan-distance scorer, supporting its tolerance to imperfect process feedback. Regarding comparison fairness, PATR uses the same policy backbone, task rewards, and GRPO optimization objective, with the primary difference being process-guided rollout construction. We will clarify these distinctions in the revision.
Response to Weakness 8
We thank the reviewer for suggesting TSR as an additional baseline. We conducted new experiments on FrozenLake and SWE-Bench and will include the results in the revision.
1. FrozenLake comparison. We evaluate TSR using its released workflow and the same BFS-based progress signal.
| Method | Qwen2.5-0.5B | Qwen2.5-3B |
|---|---|---|
| GRPO | 66.5 | 66.8 |
| TSR | 70.0 | 71.5 |
| PATR (ours) | 75.8 | 74.3 |
PATR outperforms TSR by 5.8 and 2.8 percentage points, respectively.
2. SWE-Bench comparison. We evaluate a budget-matched adaptation of TSR using the same pretrained PRM as PATR-PRM.
| Method | Resolved Rate ↑ | Env Done ↑ | Turns ↓ |
|---|---|---|---|
| GRPO | 22.2 | 79.2 | 25.8 |
| TSR-SWE | 25.2 | 88.4 | 26.1 |
| PATR-Judge | 26.0 | 90.8 | 24.1 |
| PATR-PRM | 27.2 | 92.2 | 24.4 |
Both PATR variants outperform TSR in resolved rate and environment completion while requiring fewer turns.
The key distinction is how process feedback guides rollouts. TSR uses search and selection to retain high-scoring candidates, whereas PATR adaptively allocates rollouts through expansion, survival, and pruning while retaining failed and early-stopped trajectories for GRPO training. This preserves informative negative outcomes. Table 4 supports this design: retaining pruned trajectories improves SWE-Bench resolved rates from 25.8% to 27.2% for PATR-PRM and from 23.4% to 26.0% for PATR-Judge.
Response to Weakness 9
We would like to clarify that Figure 3 is intended to illustrate training dynamics rather than demonstrate that PATR outperforms every baseline on each individual metric. As discussed in Section 6.4, the figure examines training reward, interaction length, and policy entropy, which reflect different aspects of the learning process rather than final task performance. Specifically, training reward reflects learning progress over training steps, but it is computed from sampled trajectories on training tasks and can be noisy, making direct comparisons between methods less informative than held-out evaluation. Similarly, policy entropy characterizes how exploration evolves, rather than serving as a metric where higher values necessarily indicate better performance. Interaction length reflects rollout behavior and should be considered alongside task success. Therefore, differences or overlaps among these curves do not directly determine which method achieves better final task performance.
Our primary performance claims are supported by the evaluation results in Table 2. On SWE-Bench Verified, PATR-PRM and PATR-Judge achieve resolved rates of 27.2% and 26.0%, respectively, outperforming GRPO (22.2%) and the strongest baseline, ARPO (25.4%). Both variants also achieve higher environment completion rates (92.2%/90.8% vs. at most 84.4% among baselines) while requiring fewer average interaction turns (24.4/24.1 vs. 25.8 for GRPO). These results provide more direct evidence of task-level improvements than the training-dynamics curves.
Response to Reviewer NUCM (1/4)
We thank the reviewer for the detailed evaluation. Below, we address the concerns through methodological clarifications, additional baseline comparisons, and measured compute costs, providing stronger evidence for PATR’s design and performance gains.
Response to Weakness 1
Thank you for highlighting this concern. We would like to clarify that pruned trajectories are explicitly terminated by PATR and assigned the original task-level outcome reward, rather than being left as unevaluated partial trajectories. When a branch is pruned, the task's outcome evaluator is invoked on the environment state reached so far. Thus, natural termination by the agent is not required for reward assignment.
Specifically, for SWE-agent training, the task verifier evaluates the repository with all edits made up to the pruning point, assigning reward 1 if the issue is resolved and 0 otherwise. For FrozenLake, a branch stopped before reaching the goal receives reward 0. The reward remains sparse and is assigned only at the trajectory's endpoint; the process score guides rollout allocation and never replaces the task reward. This mechanism is already reflected in the paper: Section 4.1 specifies that early-stopped branches are retained in the completed set (C), and Section 4.3 states that all completed, failed, and pruned branches are retained with their outcome rewards for GRPO training. Section 6.3 (Table 4) further demonstrates the benefit of retaining these trajectories, improving SWE-Bench resolved rates from 25.8% to 27.2% for PATR-PRM and from 23.4% to 26.0% for PATR-Judge.
Response to Weakness 2
We agree that obtaining reliable intermediate process scores can be challenging, particularly for tasks requiring long-horizon reasoning. However, PATR does not require the intermediate process scorer to accurately predict final task outcomes. Instead, it only requires process scores that provide useful relative rankings of partial trajectories within the same task. As described in Section 4.2, these scores guide rollout allocation without requiring calibrated success probabilities, while policy optimization relies on the original task-level outcome rewards. Moreover, moderately scored branches continue exploring and are reassessed after another (K) turns, reducing reliance on a single early assessment.
Our experiments provide evidence that PATR can benefit from imperfect scorers across different tasks. In Appendix B (Table 6), we evaluate a deliberately imperfect Manhattan-distance scorer that ignores obstacles and can incorrectly favor dead-end states. Despite this limitation, PATR achieves success rates of 74.9%/74.5%, comparable to the BFS scorer (75.8%/74.3%), while outperforming all baselines. More importantly, on the challenging long-horizon SWE-Bench tasks, where intermediate progress is difficult to evaluate, two distinct scoring approaches, a pretrained PRM and an LLM judge, both outperform all baselines, achieving resolved rates of 27.2% and 26.0%, respectively (Table 2).
Regarding generalization to other tasks, we acknowledge that obtaining informative process scores can be challenging, especially for tasks requiring complex reasoning about future outcomes. However, PATR is designed to tolerate imperfect intermediate feedback rather than depend on highly accurate scorers, as supported by our robustness experiments. PATR also supports different scoring mechanisms, including pretrained PRMs and general-purpose LLM judges, without relying on task-specific heuristics. As described in Section 4.2, the LLM-judge approach provides a practical alternative without task-specific scorer training.
Response to Weakness 3
Thank you for pointing out this relevant work. We appreciate the suggestion and will cite TreeRL and expand the discussion of rollout efficiency and tree-based RL in the Related Work section.
While TreeRL and PATR both leverage tree-structured rollouts, they differ fundamentally in how the tree is constructed and used for training. TreeRL focuses on mathematical and code reasoning, using token-level uncertainty to guide branching and deriving intermediate supervision from the resulting tree for policy optimization. In contrast, PATR targets multi-turn agents interacting with external environments, where branching occurs at interaction-step boundaries and intermediate process scores guide the expansion, continuation, and pruning of trajectories. Importantly, PATR uses the tree to adaptively allocate rollout budgets based on task progress, while retaining the original outcome-based GRPO advantage and objective. Thus, TreeRL's token-level search is not directly designed for multi-turn environment interactions, where branching also requires maintaining consistent environment states.