acceptodds
Under review as a conference paper at ICLR 2027

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

Abstract

Reinforcement learning (RL) has become a key approach for training LLM agents, yet popular methods such as GRPO/RLOO rely on multiple independently sampled complete trajectories for advantage estimation. In long-horizon agentic tasks, such a uniform rollout strategy can waste budget on uninformative dead-end attempts, while promising intermediate states do not receive sufficient exploration. We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL. PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops degenerate paths to reduce wasted sampling. The resulting rollout groups remain compatible with standard policy optimization while providing more efficient exploration under the same training budget. We evaluate PATR on FrozenLake and the challenging SWE-Bench, which is largely unexplored by prior tree-rollout agent RL methods. Experiments show that PATR improves performance by up to points on SWE-Bench and points on FrozenLake, highlighting process-guided tree rollouts as an effective strategy for scalable multi-turn RL.

Primary area:
reinforcement learning
Keywords:
LLM Agents, Reinforcement Learning, Process Reward Models, Tree Rollout

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NUCMOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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].

  4. 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.

  5. 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.

  6. 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.

  7. 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?

  8. 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.

  9. 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.

  10. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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 KK 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 K=13K=13 achieves a 27.2% resolved rate on SWE-Bench, compared with 23.4% and 24.6% for K=15K=15 and K=20K=20, 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

AuthorsOpenReview ↗

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.

MethodQwen2.5-0.5BQwen2.5-3B
GRPO66.566.8
TSR70.071.5
PATR (ours)75.874.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.

MethodResolved Rate ↑Env Done ↑Turns ↓
GRPO22.279.225.8
TSR-SWE25.288.426.1
PATR-Judge26.090.824.1
PATR-PRM27.292.224.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.

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

This paper introduces Process-Scorer Guided Adaptive Tree Rollout (PATR), a tree-based rollout framework designed for multi-turn LLM agent training. PATR allows the intermediate trajectories to be scored by either heuristic rules, a pre-trained Process Reward Model (PRM), or an LLM judge, and then dynamically determine the branching strategy of future rollouts: expand high-quality branches, retain medium-quality ones, or terminate low-quality branches early.

Critical strengths

The paper is well motivated, the idea is straightforward and to the point. PATR is a simple but practical framework to adaptively allocate promising intermediate states larger compute budget. It does not change the GRPO objective and is compatible with various types of process scorers.

Critical weaknesses

The method design could use better justification. Currently the paper claims PATR is better than entropy- or uncertainty-based branching because "process score" is a better indicator of task progress than entropy or uncertainty, which makes sense by intuition, but further empirical verification could help. Moreover, it is unclear why, or whether, PATR can outperform other score-based methods discussed in the related works, such as TSR or IGRPO. A direct comparison with these baselines could further strengthen the paper.

Questions for authors

See weakness

4 comments
AuthorsOpenReview ↗

Response to Reviewer Qgtv

We thank the reviewer for the constructive suggestions. We provide additional entropy-guided and TSR comparisons and clarify the relationship to IGRPO.

Response to Weakness 1

We thank the reviewer for these constructive suggestions. To strengthen the empirical justification of process-guided branching, we have conducted additional experiments with an entropy-guided tree baseline (Tree-Entropy) and direct comparisons with TSR on both FrozenLake and SWE-Bench. We address the concerns below.

1. Process scores vs. entropy-based branching. While entropy reflects the policy's uncertainty, it does not necessarily indicate whether an intermediate state is making meaningful progress toward task completion. Our existing ARPO baseline uses entropy-guided branching, and PATR consistently outperforms it across both benchmarks. However, to further isolate the effect of the scoring signal, we introduce Tree-Entropy, which uses the same tree-rollout structure and hyperparameters as PATR but replaces process scores with the policy's mean token entropy over the last KK turns for branch selection. Together with Tree-Random, this provides a controlled comparison of random, entropy-guided, and process-guided rollout allocation.

FrozenLake success rate (%):

Method0.5B3B
GRPO66.566.8
ARPO69.768.7
Tree-Random56.372.7
Tree-Entropy (new)68.370.3
TSR (new)70.071.5
PATR (ours)75.874.3

SWE-Bench Verified:

MethodResolved ↑Env Done ↑Turns ↓
GRPO22.279.225.8
ARPO25.474.027.3
Tree-Random24.884.430.1
Tree-Entropy (new)25.085.628.4
TSR-SWE (new)25.288.426.1
PATR-Judge26.090.824.1
PATR-PRM27.292.224.4

PATR consistently outperforms Tree-Entropy across both benchmarks, achieving improvements of 7.5/4.0 percentage points on FrozenLake and 2.2 points on SWE-Bench for PATR-PRM. Since Tree-Entropy shares PATR's rollout structure, these results provide direct empirical evidence that process scores offer a more effective allocation signal than entropy in our evaluated settings, rather than the improvement arising solely from tree construction.

2. Comparison with TSR. We additionally evaluate TSR using its released workflow on FrozenLake with the same BFS progress signal, and a budget-matched adaptation on SWE-Bench using the same pretrained PRM. As shown above, PATR outperforms TSR on both benchmarks, including improvements of 5.8/2.8 points on FrozenLake and 2.0 points in SWE-Bench resolved rate for PATR-PRM.

The key distinction lies in how the methods use intermediate feedback. TSR performs search and selection to retain high-scoring candidates, whereas PATR uses process scores to adaptively allocate additional rollouts through expansion, survival, and pruning, while retaining all generated trajectories for GRPO training, including failed and early-stopped branches. This preserves informative negative outcomes rather than exclusively selecting promising continuations. Our existing ablation (Table 4) further supports this design, showing that retaining pruned trajectories improves SWE-Bench resolved rates by 1.4/2.6 points for PATR-PRM/PATR-Judge.

3. Comparison with IGRPO. IGRPO uses information gain based on changes in the policy's likelihood of a ground-truth answer to guide rollout allocation. While designed for search-augmented question answering, this scoring mechanism requires reference answer sequences that are not directly available in our environment-based evaluation protocols. FrozenLake evaluates goal-reaching behavior, while SWE-Bench evaluates repository modifications through executable tests, where multiple action sequences or patches can lead to successful outcomes. Therefore, directly applying IGRPO requires additional task-specific adaptation of its information-gain criterion rather than using its original implementation. We appreciate the reviewer's suggestion and recognize IGRPO as a valuable baseline for further comparison. Given the limited rebuttal period, we prioritized the direct TSR comparisons and controlled Tree-Entropy experiments, while a faithful adaptation of IGRPO requires additional implementation and validation. We plan to extend IGRPO to our multi-turn agent settings and include this comparison in the revised paper.

We will incorporate these new experimental results and clarify the methodological distinctions in the revision. Together, the controlled Tree-Entropy ablation and direct TSR comparisons provide stronger empirical support for PATR's process-guided adaptive rollout design in multi-turn agent RL.

AuthorsOpenReview ↗

Follow-up to Reviewer Qgtv

Dear Reviewer,

We would like to kindly follow up on our rebuttal. In response to your suggestions, we conducted additional experiments comparing PATR with entropy-guided tree rollouts and TSR on both FrozenLake and SWE-Bench. We believe these new results directly address your concerns and further strengthen the empirical support for our method.

We would greatly appreciate it if you could revisit our responses and let us know whether the additional evidence addresses your concerns and further strengthens your assessment of our work.

Thank you again for your time and consideration!

Thank you for the detailed response. My concerns have been addressed and I will maintain the positive score.

Thank you for your positive feedback and for confirming that our responses have addressed your concerns! We sincerely appreciate your constructive suggestions and support. We will incorporate the additional experiments and methodological clarifications into the revised paper to further strengthen our work.

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

GRPO-style agent training samples complete trajectories independently, so budget is spread uniformly over dead ends and promising intermediate states alike. PATR instead builds a rollout tree: every KK turns a process scorer SϕS_\phi scores each active branch, high-scoring branches are expanded with MM children, moderate ones survive, and branches below the group median minus a margin (or repeating an action Θ\Theta times) are pruned but kept as negative samples. The resulting group is optimized with the unchanged GRPO objective on outcome rewards; the scorer only allocates rollout budget. Experiments on FrozenLake and SWE-Bench Verified report up to +9.3 and +5.0 points over GRPO.

Critical strengths
  1. The design is simple and well targeted: process feedback changes only where budget goes, not the objective, so the method drops into existing GRPO pipelines and keeps failed trajectories for advantage contrast. The Tree-Random baseline is the right control and isolates the value of quality-aware allocation from tree construction itself.

  2. The evidence is on a genuinely hard setting. Gains hold at two model scales on FrozenLake, and on SWE-Bench the resolved rate improves while turns and response length decrease, which rules out "just sample longer". Retaining pruned branches is ablated and shown to matter.

Critical weaknesses
  1. The rollout group is no longer sampled from the policy, and the resulting gradient bias is acknowledged but not corrected. Expanding high-scoring states over-represents them, siblings share prefixes so their outcomes are correlated, and the effective sample size is below ∣G(x)∣|G(x)|; the paper defers probability reweighting to future work. Without it, the reported gains may partly reflect a changed training distribution rather than better exploration.

  2. The compute comparison is not fully specified. PATR adds scorer calls (a 7B PRM or a 7B judge, larger than the 4B policy), extra child rollouts and tree bookkeeping, while baselines use a fixed group of 8; the paper does not report matched wall-clock, token, or scorer-call budgets. Statistical support is also thin: SWE-Bench differences of 1-2 points carry roughly ±1\pm 1 variation, and FrozenLake numbers are reported without variance or seed counts.

Questions for authors
  1. Can you report matched budgets (environment steps, tokens, and scorer calls) and show the gain persists when baselines receive an equal total budget?
  2. How large is the gradient bias from non-uniform branching, and does probability reweighting recover or reduce the gain?
  3. With the judge replaced by a model no stronger than the policy, does PATR still beat ARPO on SWE-Bench?
  4. How many training seeds underlie Table 2, and are the 1-2 point gaps significant?
  5. Is there any overlap between R2E-Gym-Lite training instances and SWE-Bench Verified?
6 comments
AuthorsOpenReview ↗

Response to Reviewer 3exg (1/3)

We thank the reviewer for the thoughtful evaluation and recognition of PATR’s simple design and empirical benefits. Below, we clarify the methodology and provide additional experiments addressing robustness, compute budgets, scorer size, and statistical support.

Response to Weakness 1 and Question 2

We thank the reviewer for this important question. PATR preserves policy-based action generation while intentionally reallocating rollout computation across intermediate states. Every action, including child continuations created by expansion (Eq. 3), is sampled from the rollout policy π(at∣ht)\pi(a_t\mid h_t) conditioned on its history. The process scorer does not modify the policy's action probabilities, so the token-level probability ratio in the clipped GRPO objective remains valid for the sampled actions. What changes is the frequency with which different intermediate states appear in the training group, as explicitly acknowledged in the Remark of Section 4.3. Importantly, the size of this change is known exactly from the tree structure. Each expansion replaces a branch with MM child continuations, so a leaf trajectory with did_i expansions along its path is represented MdiM^{d_i} times more often than under independent sampling. The weight that exactly undoes this over-representation is wi=1B0M−di,w_i=\frac{1}{B_0}M^{-d_i}, where B0B_0 denotes the number of initial branches. These weights sum to one over the complete retained tree and require no probability estimation, because each child is a fresh sample from the policy. Sibling trajectories share a prefix, which lowers the effective sample size relative to ∣G(x)∣|G(x)| independent rollouts. This is the intended trade-off of PATR: when the process scorer identifies a promising intermediate state, PATR spends additional rollouts on continuations from that state instead of restarting from the initial prompt. The group therefore contains several outcomes from the same promising state, and the differences among them tell GRPO which continuations lead to success.

To empirically investigate whether the branching-induced weighting imbalance drives PATR's improvements, we conducted an additional branch-reweighting experiment on FrozenLake, keeping the remaining experimental settings unchanged.

MethodQwen2.5-0.5BQwen2.5-3B
GRPO66.566.8
PATR (original)75.874.3
PATR (reweighted)75.374.5

With reweighting, the success rates differ from the original PATR by only −0.5 and +0.2 percentage points, and the gain over GRPO is preserved. PATR's gains therefore do not depend on the over-representation of expanded branches. Furthermore, Tree-Random uses the same tree-rollout framework without process-guided allocation but performs worse than PATR on both FrozenLake and SWE-Bench. Together with Table 4, where retaining early-pruned trajectories improves SWE-Bench resolved rates by 1.4/2.6 points, these findings provide complementary evidence for the benefits of process-guided exploration and informative outcome contrasts. While the reweighting experiment does not directly estimate the exact expected-gradient bias, it demonstrates that correcting branch-multiplicity imbalance preserves PATR's substantial performance gains.

AuthorsOpenReview ↗

Response to Reviewer 3exg (2/3)

Response to Weakness 2 and Question 1

We thank the reviewer for this constructive suggestion. To address these concerns, we have conducted additional compute profiling, a token-budget-matched comparison, and repeated evaluations to quantify performance variability. The results provide further evidence that PATR's improvements arise from more effective rollout allocation rather than simply increased computational budgets.

1. Computational overhead. PATR's additional branches do not require generating independent full trajectories. Each child inherits its parent's prefix, including previous environment interactions, and generates only a new continuation. Together with early stopping, this reduces redundant computation. Furthermore, process scoring is performed sparsely (every K=13K=13 turns on SWE-Bench) using a frozen scorer operating on recent trajectory context.

We provide the following measured compute breakdown for SWE-agent training:

Compute metricGRPO (n=8)PATR-PRMRatio
Environment turns per task2192301.05×
Policy training tokens per step1.36M1.47M1.08×
Scorer calls per task011.3—
End-to-end wall-clock1.00×1.12×1.12×

PATR requires approximately 5% more environment interactions and 8% more policy training tokens, with only a 12% increase in training time. The scorer is frozen and runs on a separate inference GPU, whose additional resource consumption is accounted for separately from wall-clock time. On FrozenLake, PATR uses a lightweight heuristic without auxiliary model inference.

2. Token-budget-matched comparison. To directly examine whether PATR's improvements simply result from additional sampling, we conduct a new FrozenLake experiment with GRPO's rollout group size increased from 8 to 10, matching PATR's policy-generation-token budget.

MethodQwen2.5-0.5BQwen2.5-3B
GRPO (n=8)66.566.8
GRPO (token-matched, n=10)70.568.3
Tree-Random (same tree budget)56.372.7
PATR (ours)75.874.3

PATR continues to outperform token-matched GRPO by 5.3 and 6.0 percentage points, respectively, demonstrating that its gains cannot be explained simply by generating more policy tokens. Furthermore, Tree-Random uses the same tree structure and branching budget as PATR but achieves lower performance, supporting the importance of process-guided allocation rather than additional sampling alone.

Due to the substantial cost of multi-turn SWE-agent training and the limited rebuttal period, we prioritized the token-matched comparison on FrozenLake. We plan to extend this controlled comparison to SWE-Bench in the revised paper.

3. Statistical support. To address the missing variance estimates on FrozenLake, we additionally conduct five repeated evaluations with different inference sampling seeds, each using 100 evaluation instances with four rollouts per instance. We report the mean success rate and standard deviation across these evaluations:

MethodQwen2.5-0.5BQwen2.5-3B
GRPO66.5 ± 0.666.8 ± 0.5
DAPO71.0 ± 0.872.7 ± 1.2
ARPO69.7 ± 0.968.7 ± 0.8
Tree-Random56.3 ± 1.172.7 ± 0.9
PATR (ours)75.8 ± 0.874.3 ± 0.6

PATR achieves the highest mean success rate on both model scales, with consistent performance across repeated evaluations. For SWE-Bench, Table 2 reports one training run per method, and the reported ± values reflect inference-seed variability, as stated in its caption. While these estimates do not establish statistical significance across independent training runs, both PATR variants consistently achieve higher resolved and environment completion rates than the baselines. In particular, PATR-PRM improves resolved rate over GRPO by 5.0 points, while both scorer variants achieve substantially higher environment completion rates (92.2%/90.8% vs. at most 84.4% among baselines).

We will incorporate these compute measurements, token-matched experiments, and variance estimates into the revised paper. Together, these additional results strengthen the evidence that process-guided rollout allocation improves learning effectiveness with modest computational overhead, rather than relying primarily on increased sampling budgets.

AuthorsOpenReview ↗

Response to Reviewer 3exg (3/3)

Response to Question 3

Thank you for this valuable suggestion. Yes, our additional experiments show that PATR continues to outperform ARPO when using an auxiliary scorer smaller than the policy model. Specifically, we replace the original 7B Skywork PRM with Skywork-o1-Open-PRM-Qwen-2.5-1.5B, which is smaller than our Qwen3-4B policy, and retrain PATR with all other settings unchanged. We evaluate on the same 500 SWE-Bench Verified instances following the protocol in Table 2.

MethodScorerResolved Rate ↑Env Done ↑Turns ↓
GRPONone22.2 ± 1.279.225.8
ARPONone25.4 ± 0.974.027.3
Tree-RandomNone24.8 ± 1.184.430.1
PATR-PRM (new)1.5B26.6 ± 0.891.624.9
PATR-PRM (original)7B27.2 ± 0.992.224.4

With the 1.5B scorer, PATR still outperforms ARPO by 1.2 percentage points in resolved rate, 17.6 points in environment completion, and 2.4 fewer interaction turns. Furthermore, its resolved rate is only 0.6 points below that of the original 7B scorer, demonstrating that PATR maintains competitive performance with a substantially smaller scoring model.

To further investigate scoring capability, we evaluate both PRMs on identical intermediate trajectory prefixes to assess how well their scores predict eventual task success. At the first scoring checkpoint (turn 13), we score each prefix and associate it with the final success or failure of its corresponding trajectory. The 7B and 1.5B scorers achieve AUROCs of 0.58 and 0.55, respectively, indicating that both provide useful, comparable signals for identifying promising trajectories despite their substantial size difference.

Importantly, PATR uses the auxiliary scorer only to guide rollout allocation, not to generate actions or provide training rewards. The policy is optimized using its own trajectories and environment-based outcome rewards. Although we originally selected the 7B PRM as an established pretrained scorer, these results demonstrate that PATR's gains do not depend on a scorer larger than the policy. We will include these findings in the revised paper.

Response to Question 4

Table 2 is based on one training run per method. As noted in the Table 2 caption, the reported ± values reflect variation across repeated inference evaluations with different sampling seeds, rather than independent training runs.

Regarding the performance gaps, we would like to emphasize that PATR achieves consistent improvements under the same backbone model, training dataset, and evaluation protocol, without requiring additional training data or modifying the original GRPO objective. Specifically, PATR-PRM achieves a resolved rate of 27.2%, compared with 22.2% for GRPO (+5.0 points), 24.6% for DAPO (+2.6 points), and 25.4% for ARPO (+1.8 points). PATR-Judge also achieves 26.0%, further demonstrating the effectiveness of process-guided rollout allocation across different scoring mechanisms. Importantly, these improvements are not limited to resolved rate. Both PATR variants achieve substantially 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. at least 25.8 among baselines). These consistent gains across different scorers and evaluation metrics provide additional evidence of the effectiveness of our approach.

While the reported inference-seed variation does not constitute a formal statistical significance test across independent training runs, the improvements across multiple baselines, scoring mechanisms, and evaluation metrics provide encouraging empirical evidence beyond the individual 1–2 point differences.

Response to Question 5

Thank you for raising this important question. We verified that there is no overlap between our R2E-Gym-Lite training data and SWE-Bench Verified evaluation data, even at the repository level. Specifically, the training set contains 10 repositories (e.g., pandas, numpy, pillow, aiohttp, and tornado), while SWE-Bench Verified contains 12 different repositories (e.g., django, sympy, sphinx, matplotlib, and scikit-learn). Our dataset audit confirms zero overlapping repositories, consistent with the original R2E-Gym construction, which excludes repositories shared with SWE-Bench evaluation. Therefore, our evaluation measures generalization to unseen repositories, rather than merely unseen issues within previously encountered repositories.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.