Process Reward Informed Tree Rollout for Effective Multi-Turn RL

# Process Reward Informed Tree Rollout for Effective Multi-Turn RL
Source: [https://arxiv.org/html/2607.15610](https://arxiv.org/html/2607.15610)
Xintong Li1, Sha Li2, Yuwei Zhang1, Changlong Yu2, Rongmei Lin2, Hongye Jin2, Shuyi Guan3, Xin Liu2, Linwei Li2, Qingyu Yin2, Jingbo Shang1 1UC San Diego2Amazon3MIT Alumni \{xil240,jshang\}@ucsd\.eduslliz@amazon\.com

###### 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\. The multi\-turn structure of agentic trajectories, with interleaved actions and observations, naturally supports organizing a trajectory group as a tree, where each turn serves as a decision point for exploration\. This perspective reframes effective exploration as the problem of deciding where to branch\. We propose Process\-Scorer Guided Adaptive Tree Rollout \(PaTR\), a quality\-aware rollout framework for multi\-turn agent RL\.PaTRuses 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 evaluatePaTRon FrozenLake and the challenging SWE\-Bench, which is largely unexplored by prior tree\-rollout agent RL methods\. Experiments show thatPaTRimproves performance by up to\+5\.0\+5\.0points on SWE\-Bench and\+9\.3\+9\.3points on FrozenLake, highlighting process\-guided tree rollouts as an effective strategy for scalable multi\-turn RL\.

Process Reward Informed Tree Rollout for Effective Multi\-Turn RL

Xintong Li1††thanks:Work done during internship at Amazon\., Sha Li2, Yuwei Zhang1, Changlong Yu2, Rongmei Lin2,Hongye Jin2, Shuyi Guan3, Xin Liu2, Linwei Li2, Qingyu Yin2, Jingbo Shang11UC San Diego2Amazon3MIT Alumni\{xil240,jshang\}@ucsd\.eduslliz@amazon\.com

## 1Introduction

Large language models \(LLMs\) are increasingly trained as agents that solve tasks through multi\-turn interactions with tools, feedback, and external observations\(Yaoet al\.,[2022](https://arxiv.org/html/2607.15610#bib.bib48); Schicket al\.,[2023](https://arxiv.org/html/2607.15610#bib.bib49); Shinnet al\.,[2023](https://arxiv.org/html/2607.15610#bib.bib50)\)\. Reinforcement learning \(RL\) such as GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib2)\)has become a standard approach for improving such agentic capabilities\. However, most existing GRPO\-style agent training still relies on independently sampled complete trajectories\(Liet al\.,[2026a](https://arxiv.org/html/2607.15610#bib.bib51)\)\. This rollout strategy allocates computation uniformly across trajectories, regardless of their intermediate quality\. For long\-horizon agentic tasks, such uniform allocation can waste budget on uninformative trajectories, such as repeated tool\-use loops, while promising intermediate states receive insufficient exploration\. As a result, the rollout group may contain redundant or low\-value trajectories, leading to inefficient exploration and noisy advantage estimation\.

![Refer to caption](https://arxiv.org/html/2607.15610v1/x1.png)Figure 1:Overview ofPaTR\. Task\-adaptive process scorer evaluates partial trajectories and guides adaptive rollout through expansion, survival, and pruning\. The rollout group is optimized with standard GRPO using task rewards\.Recent work has begun to improve rollout generation through tree\-structured sampling, dynamic branching, and step\-level feedback\. In single\-turn reasoning, tree\-based methods reuse shared prefixes and explore multiple continuations from intermediate states, showing that rollout construction itself can be an important component of RL training\(Suranaet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib46); Xinget al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib47)\)\. This idea is even more critical for multi\-turn agents, where each action changes the future context and final rewards are often sparse or delayed\(Fenget al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib4); Djuheraet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib15)\)\.

Nevertheless, existing multi\-turn tree rollout methods exhibit key limitations in how they guide exploration\. One line of work branch around high\-entropy tool\-use steps\(Donget al\.,[2025b](https://arxiv.org/html/2607.15610#bib.bib1),[a](https://arxiv.org/html/2607.15610#bib.bib17)\)or allocate rollout budget using value\-based uncertainty estimates\(Caoet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib16)\)\. While these signals encourage exploration, they do not directly measure whether a partial trajectory is making meaningful progress toward the task objective\. Another line of work applies per\-turn search to select the highest\-scoring action at every step\(Djuheraet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib15)\), which can bias the rollout distribution away from the current policy and discard informative negative examples\. These limitations motivate a rollout mechanism that allocates budget based on process\-level trajectory quality while preserving diverse outcomes, including failures, for policy learning\.

We propose Process\-Scorer Guided Adaptive Tree Rollout \(PaTR\), a cost\-effective rollout generation framework for multi\-turn agent RL that allocates more rollout budget to promising partial trajectories while terminating unpromising ones early\. For each training instance,PaTRconstructs a tree of partial trajectories instead of sampling independent full trajectories from scratch\. We periodically evaluate active branches by a task\-adaptive process scorer and route into one of three paths: high\-scoring branches are*expanded*by sampling multiple child continuations from the same intermediate state, moderate\-scoring branches*survive*into the next iteration, and low\-scoring or degenerate branches are*pruned*early\. Pruned branches are retained rather than discarded, preserving rollout diversity and serving as negative examples for policy optimization\. Since child branches inherit their parent prefixes,PaTRnaturally reuses shared computation and produces more informative rollout trajectories under a comparable sampling budget\. We then employ standard GRPO\-style policy optimization on the resulting rollout group with the same outcome rewards, avoiding direct optimization against the auxiliary process scorer\.

We evaluatePaTRon both FrozenLake and the more challenging SWE\-Bench\. FrozenLake provides a controlled testbed where process quality can be estimated with simple progress heuristics, while SWE\-Bench evaluates whether process\-guided tree rollouts can support realistic long\-horizon coding\-agent tasks\. Experiments show thatPaTRimproves performance by up to\+5\.0\+5\.0points on SWE\-Bench and\+9\.3\+9\.3points on FrozenLake, highlighting the value of process\-guided rollout construction for effective multi\-turn RL\.

Our contributions are summarized as follows:

- •We proposePaTR, a process\-guided adaptive tree rollout framework that expands promising partial trajectories, preserves surviving branches, and prunes degenerate paths\.
- •We keepPaTRcompatible with GRPO by using process feedback only for rollout allocation while optimizing the policy with standard outcome rewards\.
- •We validatePaTRon FrozenLake and SWE\-Bench, showing consistent gains over GRPO and other rollout\-generation baselines\.

## 2Related Work

#### Adaptive Rollout Generation for Agent RL\.

GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib2)\)and subsequent RL\-based reasoning and agent methods, such as DeepSeek\-R1\(Guoet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib3)\)and ARPO\(Donget al\.,[2025b](https://arxiv.org/html/2607.15610#bib.bib1)\), commonly sample multiple trajectories per task and compute group\-relative advantages from outcome rewards\. Recent work improves this rollout process through structured or adaptive sampling\. ARPO\(Donget al\.,[2025b](https://arxiv.org/html/2607.15610#bib.bib1)\)and AEPO\(Donget al\.,[2025a](https://arxiv.org/html/2607.15610#bib.bib17)\)branch around high\-entropy tool\-use steps, ATPO\(Caoet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib16)\)allocates rollout budget using uncertainty estimates in medical dialogue, and TSR\(Djuheraet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib15)\)applies tree\-style search during training\-time rollout generation\. Tree\-based reasoning methods such as Tree of Thoughts\(Yaoet al\.,[2023](https://arxiv.org/html/2607.15610#bib.bib12)\), RAP\(Haoet al\.,[2023](https://arxiv.org/html/2607.15610#bib.bib13)\), and tree\-search agents\(Kohet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib14)\)also explore multiple continuations, but mainly for inference\-time solution selection\. Our work follows the training\-time rollout perspective, but uses process\-level quality scores rather than entropy or uncertainty alone to guide branch expansion\.

#### Process Feedback and Step\-Level Supervision\.

Process reward models, introduced in step\-by\-step verification work such as PRM\(Lightmanet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib24)\), Math\-Shepherd\(Wanget al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib25)\), and Skywork PRM\(Heet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib26)\), provide intermediate quality estimates for multi\-step reasoning\. Several methods incorporate such signals into training objectives: PRIME\(Cuiet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib27)\)derives implicit process rewards, iStar\(Liuet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib28)\)learns step\-level rewards during agent training, WS\-GRPO\(Mundadaet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib29)\)constructs weakly supervised prefix rewards, and Step\-GRPO\(Liet al\.,[2026b](https://arxiv.org/html/2607.15610#bib.bib23)\)modifies GRPO with structured process supervision\. LLM\-as\-judge methods\(Zhenget al\.,[2023](https://arxiv.org/html/2607.15610#bib.bib30)\)offer a flexible alternative when task\-specific PRMs are unavailable, especially for open\-ended agentic tasks where intermediate progress is difficult to specify manually\. In contrast, our method uses process feedback only to allocate rollout budget, leaving the policy objective and outcome reward unchanged\.

## 3Preliminaries

### 3\.1Multi\-Turn Agentic Reinforcement Learning

We consider reinforcement learning for language agents that solve tasks through multi\-turn interaction with external systems\. Given a task promptxx, afterttturns the agent observes a historyht=\(x,a1,o1,…,at,ot\)h\_\{t\}=\(x,a\_\{1\},o\_\{1\},\\ldots,a\_\{t\},o\_\{t\}\), whereata\_\{t\}is the agent action andoto\_\{t\}is the corresponding observation\. The policy samples the next action asat\+1∼πθ\(⋅∣ht\)a\_\{t\+1\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid h\_\{t\}\)\. A completed rolloutτ=\(x,a1,o1,…,aT,oT\)\\tau=\(x,a\_\{1\},o\_\{1\},\\ldots,a\_\{T\},o\_\{T\}\)receives an outcome rewardrout​\(τ\)r^\{\\mathrm\{out\}\}\(\\tau\)upon termination\. In agentic tasks, this reward is often sparse or delayed, making rollout quality critical for policy optimizationWanget al\.\([2025](https://arxiv.org/html/2607.15610#bib.bib52)\)\.

### 3\.2Group\-Relative Policy Optimization

GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib2)\)samples a group ofGGrollouts for each task and computes group\-normalized rewards, avoiding the need for a learned value function\. For trajectoryτi\\tau\_\{i\}in the rollout group of taskxx, the outcome advantage is,

Aiout=riout−μout​\(x\)σout​\(x\)\+ε,A\_\{i\}^\{\\mathrm\{out\}\}=\\frac\{r\_\{i\}^\{\\mathrm\{out\}\}\-\\mu\_\{\\mathrm\{out\}\}\(x\)\}\{\\sigma\_\{\\mathrm\{out\}\}\(x\)\+\\varepsilon\},\(1\)whereriout=rout​\(τi\)r\_\{i\}^\{\\mathrm\{out\}\}=r^\{\\mathrm\{out\}\}\(\\tau\_\{i\}\), andμout​\(x\)\\mu\_\{\\mathrm\{out\}\}\(x\)andσout​\(x\)\\sigma\_\{\\mathrm\{out\}\}\(x\)are the mean and standard deviation of outcome rewards within the group\.

The policy is optimized with the clipped importance\-weighted objective

ℒ​\(θ\)=\\displaystyle\\mathcal\{L\}\(\\theta\)=𝔼x\[1G∑i=1G1\|τi\|∑t=1\|τi\|min\(ρi,t\(θ\)Aiout,\\displaystyle\\;\\mathbb\{E\}\_\{x\}\\left\[\\frac\{1\}\{G\}\\sum\_\{i=1\}^\{G\}\\frac\{1\}\{\|\\tau\_\{i\}\|\}\\sum\_\{t=1\}^\{\|\\tau\_\{i\}\|\}\\min\\Bigl\(\\rho\_\{i,t\}\(\\theta\)A\_\{i\}^\{\\mathrm\{out\}\},\\right\.clip\(ρi,t\(θ\),1−ϵ,1\+ϵ\)Aiout\)\],\\displaystyle\\left\.\\operatorname\{clip\}\\bigl\(\\rho\_\{i,t\}\(\\theta\),1\-\\epsilon,1\+\\epsilon\\bigr\)A\_\{i\}^\{\\mathrm\{out\}\}\\Bigr\)\\right\],\(2\)whereρi,t​\(θ\)=πθ​\(ai,t∣hi,t−1\)πθold​\(ai,t∣hi,t−1\)\\rho\_\{i,t\}\(\\theta\)=\\frac\{\\pi\_\{\\theta\}\(a\_\{i,t\}\\mid h\_\{i,t\-1\}\)\}\{\\pi\_\{\\theta\_\{\\mathrm\{old\}\}\}\(a\_\{i,t\}\\mid h\_\{i,t\-1\}\)\}is the importance ratio\. Since advantages are computed relative to the sampled group, policy learning depends directly on rollout\-group quality\. However, standard GRPO samples complete trajectories independently from the initial task state, without considering intermediate trajectory quality\.

## 4PaTR: Process\-Scorer Guided Adaptive Tree Rollout

We proposePaTR\(Process\-scorer guidedAdaptiveTreeRollout\), a cost\-effective rollout generation framework for multi\-turn agent RL, that allocates more rollout budget to promising partial trajectories and terminate unpromising ones early, producing groups with diverse outcomes from shared prefixes\. Given a task promptxx,PaTRconstructs a tree of partial trajectories and adaptively allocates rollout budget using an intermediate process scorer\. The full procedure is summarized in Algorithm[1](https://arxiv.org/html/2607.15610#alg1)\.

### 4\.1Adaptive Tree Construction

PaTRinitializes each task promptxxwithB0B\_\{0\}active branches sampled from the current policy\. Let𝒜\\mathcal\{A\}and𝒞\\mathcal\{C\}denote the sets of active and completed branches, respectively\. At each iteration, every active branch is advanced for up toKKinteraction steps\. Branches that terminate during this interval, such as by successful completion or reaching the maximum step budget, are moved from𝒜\\mathcal\{A\}to𝒞\\mathcal\{C\}\. For each remaining active branchτit\\tau\_\{i\}^\{t\}at steptt\(t∈\{K,2​K,3​K,…\}t\\in\\\{K,2K,3K,\\ldots\\\}\), a process scorerSϕS\_\{\\phi\}produces a scalar score

sit=Sϕ​\(x,τit\)∈\[0,1\],s\_\{i\}^\{t\}=S\_\{\\phi\}\(x,\\tau\_\{i\}^\{t\}\)\\in\[0,1\],\(3\)where higher scores indicate more promising partial trajectories for further exploration\.

After scoring, each active branch is routed into one of three paths based on its process score:expansion,survival, orpruning\. Expansion\.High\-scoring branches are selected into an expansion setℰ⊆𝒜\\mathcal\{E\}\\subseteq\\mathcal\{A\}\. For each selected branchτit\\tau\_\{i\}^\{t\},PaTRsamplesMMchild continuations from the same intermediate state:

τit,m∼πθ\(⋅∣x,τit\),m=1,…,M\.\\tau\_\{i\}^\{t,m\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid x,\\tau\_\{i\}^\{t\}\),\\qquad m=1,\\ldots,M\.\(4\)These children share the parent prefix and explore different continuations, allowingPaTRto allocate additional samples to promising intermediate states\. The parent branch is then removed from𝒜\\mathcal\{A\}and replaced by its children\. Survival\.Branches with moderate scores remain active\. They are advanced for anotherKKsteps in the next iteration and re\-evaluated with updated process scores\. Pruning\.PaTRterminates a branchτit\\tau\_\{i\}^\{t\}when its process score is substantially lower than the current active set:

sit<medianj∈𝒜⁡sjt−α,s\_\{i\}^\{t\}<\\operatorname\{median\}\_\{j\\in\\mathcal\{A\}\}s\_\{j\}^\{t\}\-\\alpha,\(5\)whereα\\alphais a margin threshold\.PaTRalso stops deterministically degenerate branches, such as those repeating the same action forΘ\\Thetaconsecutive turns\. Early\-stopped branches are moved to𝒞\\mathcal\{C\}rather than discarded, so they remain available as negative trajectories for policy optimization\.

The rollout process continues until no active branch remains\. The final rollout group is constructed from all completed trajectories\.

𝒢​\(x\)=𝒞\.\\mathcal\{G\}\(x\)=\\mathcal\{C\}\.\(6\)Importantly, process scores are used only to decide where to allocate additional rollout budget; they do not replace the task reward\. The resulting group contains both successful and failed trajectories generated from shared intermediate states, providing diverse samples for GRPO\-style relative advantage estimation\.

Algorithm 1PATR Rollout Generation0:Task prompt

xx; policy

πθ\\pi\_\{\\theta\}; process scorer

SϕS\_\{\\phi\}; budgets

\(B0,K,M\)\(B\_\{0\},K,M\); thresholds

\(α,Θ\)\(\\alpha,\\Theta\)
1:Initialize

𝒜\\mathcal\{A\}with

B0B\_\{0\}branches from

xxunder

πθ\\pi\_\{\\theta\};

𝒞←∅\\mathcal\{C\}\\leftarrow\\emptyset
2:while

𝒜≠∅\\mathcal\{A\}\\neq\\emptysetdo

3:Roll out each branch in

𝒜\\mathcal\{A\}for up to

KKsteps under

πθ\\pi\_\{\\theta\}
4:Move terminated branches from

𝒜\\mathcal\{A\}to

𝒞\\mathcal\{C\}
5:if

𝒜≠∅\\mathcal\{A\}\\neq\\emptysetthen

6:Compute

sit=Sϕ​\(x,τit\)s\_\{i\}^\{t\}=S\_\{\\phi\}\(x,\\tau\_\{i\}^\{t\}\)for each

τit∈𝒜\\tau\_\{i\}^\{t\}\\in\\mathcal\{A\}Eq\.[3](https://arxiv.org/html/2607.15610#S4.E3)

7:Select high\-scoring expansion set

ℰ⊆𝒜\\mathcal\{E\}\\subseteq\\mathcal\{A\}
8:Let

ℒ⊆𝒜∖ℰ\\mathcal\{L\}\\subseteq\\mathcal\{A\}\\setminus\\mathcal\{E\}be branches satisfying the low\-score or

Θ\\Theta\-repeat criterionEq\.[5](https://arxiv.org/html/2607.15610#S4.E5)

9:Sample child set

ℬ=\{τit,m:τit∈ℰ,m=1,…,M\}\\mathcal\{B\}=\\\{\\tau\_\{i\}^\{t,m\}:\\tau\_\{i\}^\{t\}\\in\\mathcal\{E\},\\,m=1,\\ldots,M\\\}Eq\.[4](https://arxiv.org/html/2607.15610#S4.E4)

10:

𝒜←\(𝒜∖\(ℰ∪ℒ\)\)∪ℬ\\mathcal\{A\}\\leftarrow\(\\mathcal\{A\}\\setminus\(\\mathcal\{E\}\\cup\\mathcal\{L\}\)\)\\cup\\mathcal\{B\};

𝒞←𝒞∪ℒ\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\cup\\mathcal\{L\}
11:endif

12:endwhile

13:return

𝒢​\(x\)=\{τ∈𝒞:\|τ\|\>0\}\\mathcal\{G\}\(x\)=\\\{\\tau\\in\\mathcal\{C\}:\|\\tau\|\>0\\\}

### 4\.2Task\-Adaptive Process Scoring

PaTRabstracts task\-specific intermediate feedback into a scalar process score as defined in Eq\.[3](https://arxiv.org/html/2607.15610#S4.E3), This interface supports different scorer instantiations, including domain\-specific heuristics, pretrained PRMs, and LLM judges, without changing the rollout algorithm or the GRPO objective\.

#### Heuristic scorer\.

When intermediate progress is directly observable, we instantiateSϕS\_\{\\phi\}as a lightweight heuristic over the current state and accumulated step rewards\. For example, in navigation\-style tasks, the scorer can combine the reward accumulated so far with a normalized progress measure such as distance to the goal\. This instantiation requires no learned model and provides a controlled setting for studying adaptive tree rollout when reliable progress signals are available\.

#### Pretrained PRM scorer\.

For tasks where a pretrained process reward model is available, we convert each partial trajectory into a problem–response format\. The problem field contains the task prompt, while the response field serializes recent interaction steps, including agent actions, observations, and available step rewards\. The PRM produces step\-level scores\{cℓ\}ℓ=1Li\\\{c\_\{\\ell\}\\\}\_\{\\ell=1\}^\{L\_\{i\}\}at designated step boundaries, which are aggregated into a branch score:

sit=fagg​\(c1,…,cLi\),s\_\{i\}^\{t\}=f\_\{\\mathrm\{agg\}\}\(c\_\{1\},\\ldots,c\_\{L\_\{i\}\}\),\(7\)wherefaggf\_\{\\mathrm\{agg\}\}can be the last\-step score, the mean score, the maximum score, or a weighted combination of the last and mean scores\. For long trajectories, we truncate the serialized input while preserving the task prompt and recent interaction steps, which are most relevant for deciding whether to expand the current branch\.

#### LLM\-as\-judge scorer\.

For complex agentic tasks where no reliable hand\-crafted signal or pretrained PRM is sufficient, we instantiateSϕS\_\{\\phi\}with an LLM judge\. The judge receives the task prompt and a compact representation of the partial trajectory, including recent actions, observations, and automatically extracted trajectory signals\. Specifically, to make scoring sensitive to different stages of SWE\-style problem solving, we use phase\-specific judge prompts for diagnosis, editing, and verification\. The judge is instructed to output a normalized JSON score indicating whether continuing from the current state is likely to lead to a successful solution\. We further blend the judge output with a lightweight heuristic based on trajectory features such as repeated actions, error or test signals in observations, evidence before editing, and targeted verification:

sit=λ​sjudge​\(τit\)\+\(1−λ\)​sheur​\(τit\)\.s\_\{i\}^\{t\}=\\lambda s\_\{\\mathrm\{judge\}\}\(\\tau\_\{i\}^\{t\}\)\+\(1\-\\lambda\)s\_\{\\mathrm\{heur\}\}\(\\tau\_\{i\}^\{t\}\)\.\(8\)This design provides robust process scores for long\-horizon tool\-use tasks while keeping the interface toPaTRidentical to the heuristic and pretrained\-PRM cases\. Appendix[B](https://arxiv.org/html/2607.15610#A2)provides the full prompts and describes the heuristic scoring signals in detail\.

### 4\.3GRPO Training with Tree\-Generated Rollout Groups

After tree rollout construction,PaTRuses𝒢​\(x\)\\mathcal\{G\}\(x\)from Eq\.[6](https://arxiv.org/html/2607.15610#S4.E6)as the rollout group for GRPO\. For each trajectoryτi∈𝒢​\(x\)\\tau\_\{i\}\\in\\mathcal\{G\}\(x\), we compute its outcome rewardriout=rout​\(τi\)r\_\{i\}^\{\\mathrm\{out\}\}=r^\{\\mathrm\{out\}\}\(\\tau\_\{i\}\)and normalize rewards within the tree\-generated group,

Aitree=riout−μ𝒢​\(x\)σ𝒢​\(x\)\+ε,A\_\{i\}^\{\\mathrm\{tree\}\}=\\frac\{r\_\{i\}^\{\\mathrm\{out\}\}\-\\mu\_\{\\mathcal\{G\}\}\(x\)\}\{\\sigma\_\{\\mathcal\{G\}\}\(x\)\+\\varepsilon\},\(9\)whereμ𝒢​\(x\)\\mu\_\{\\mathcal\{G\}\}\(x\)andσ𝒢​\(x\)\\sigma\_\{\\mathcal\{G\}\}\(x\)are computed over all valid trajectories in𝒢​\(x\)\\mathcal\{G\}\(x\)\. The policy is then updated with the same clipped GRPO objective in Eq\.[2](https://arxiv.org/html/2607.15610#S3.E2), replacing the independently sampled rollout group with the tree\-generated group\.

Remark\.PaTRdeparts from the uniform independent sampling used in vanilla GRPO by adaptively allocating more continuations to selected partial histories\. This introduces a controlled and localized bias in the rollout group\. Importantly, the process scorer is used only for branch selection: it does not alter the policy model, task reward, advantage normalization, or optimization objective\. After tree construction, completed, failed, and early\-stopped branches are all retained as outcome\-labeled trajectories, and the policy is updated using standard GRPO with task rewards\. This idea coincides with the efficiency\-bias trade\-off discussion in the literature of reinforcement learning, where non\-uniform allocation of computation or samples can improve data efficiency by focusing efforts on more informative states or transitionsKocsis and Szepesvári \([2006](https://arxiv.org/html/2607.15610#bib.bib43)\); Schaulet al\.\([2016](https://arxiv.org/html/2607.15610#bib.bib44)\); Espeholtet al\.\([2018](https://arxiv.org/html/2607.15610#bib.bib45)\)\. InPaTR, the induced mismatch is further limited because actions are still generated by the current rollout policy conditioned on realized histories, and only the number of continuations allocated to each partial history is adapted\. Thus,PaTRtrades strict uniform rollout sampling for more informative rollout groups while keeping the learning objective unchanged\.

## 5Experiments

### 5\.1Experimental Setup

#### Tasks, datasets, and models\.

We evaluatePaTRon two settings with different levels of interaction complexity\.FrozenLake\(Brockmanet al\.,[2016](https://arxiv.org/html/2607.15610#bib.bib35)\)is a grid\-world navigation task in which an agent must reach a goal while avoiding holes, providing a controlled testbed for multi\-turn exploration\. We use the rLLM FrozenLake environment\(Tanet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib36)\)with procedurally generated task prompts\.SWE\-agent trainingtargets long\-horizon software\-engineering tasks, where agents must inspect repositories, edit code, and verify fixes through tool interaction\. For training, we use a filtered subset of R2E\-Gym\-Lite\-with\-Difficulty, which is derived from R2E\-Gym\(Jainet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib37)\)by removing the most difficult instances\. We evaluate on SWE\-Bench Verified\(Jimenezet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib38)\), a human\-filtered set of 500 instances designed for reliable evaluation of coding agents and language models\. For FrozenLake, we train Qwen2\.5\-0\.5B\-Instruct and Qwen2\.5\-3B\-Instruct\(Yanget al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib40)\); for SWE\-agent training, we use Qwen3\-4B\-Instruct\-2507\(Yanget al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib41)\)\.

#### Baselines\.

We compare against representative GRPO\-based and tree\-style rollout strategies under the same policy optimization objective\.GRPO\(Shaoet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib2)\)samples independent complete trajectories for each task\.DAPO\(Yuet al\.,[2026](https://arxiv.org/html/2607.15610#bib.bib42)\)strengthens GRPO with token\-level policy\-gradient refinements, rejection sampling, and asymmetric clipping\.ARPO\(Donget al\.,[2025b](https://arxiv.org/html/2607.15610#bib.bib1)\)performs adaptive branching for agentic rollouts based on uncertainty signals rather than process\-level trajectory quality\.Tree\-Randomuses the same tree rollout structure asPaTRbut replaces process\-guided selection with random branch allocation\.

#### Evaluation\.

For FrozenLake, we follow the standard success\-rate evaluation\. Each test prompt is sampled four times, and we report the average fraction of successful task instances\. For SWE\-Bench evaluation, we use the SWE\-agent scaffold with Docker\-based execution environments\. Each trained agent generates one trajectory per SWE\-Bench Verified instance, and we report the resolved rate, following the standard SWE\-Bench protocol\.

#### Implementation Details\.

All experiments are implemented with the rLLM framework\(Tanet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib36)\)\. Across both tasks,PaTRstarts from four initial branches and samples two child continuations when expanding a branch\. Branching is performed at fixed intervals, withK=5K=5for FrozenLake andK=13K=13for SWE\-agent training\. We set the maximum interaction length to 10 turns for FrozenLake and 50 turns for SWE\-agent training, with maximum response lengths of 10K and 32K tokens, respectively\. Early stopping uses the score\-margin rule in Eq\.[5](https://arxiv.org/html/2607.15610#S4.E5)withα=0\.5\\alpha=0\.5, together with an action\-loop criterion that terminates branches repeating the same action six times\.

The process scorer is instantiated according to the task\. For FrozenLake, we use a lightweight progress heuristic based on accumulated rewards and shortest\-path distance to the goal, treating holes as blocked cells\. For SWE\-agent training, we evaluate two scorer variants:PaTR\-PRM, which uses Skywork\-o1\-Open\-PRM\-Qwen\-2\.5\-7B\(Heet al\.,[2025](https://arxiv.org/html/2607.15610#bib.bib26)\), andPaTR\-Judge, which uses Qwen2\.5\-Coder\-7B\-Instruct\(Huiet al\.,[2024](https://arxiv.org/html/2607.15610#bib.bib39)\)as an LLM judge with phase\-specific prompts\. Both scorers operate on recent trajectory context; additional scoring details are provided in Appendix[A](https://arxiv.org/html/2607.15610#A1)\. To ensure a fair comparison, GRPO and DAPO use a rollout group size of 8, while ARPO, Tree\-Random, andPaTRuse the same number of initial branches\. Detailed training hyperparameters and hardware settings are reported in Appendix[A](https://arxiv.org/html/2607.15610#A1)\.

MethodSucc\. Rate↑\\uparrowPass@4↑\\uparrowRLen↓\\downarrowTurns↓\\downarrowQwen2\.5\-0\.5B\-InstructGRPO66\.567\.05133\.4DAPO71\.071\.05624\.2ARPO69\.772\.03773\.3Random56\.363\.04003\.9\\rowcolorgreen\!15PaTR\(ours\)75\.878\.03443\.6Qwen2\.5\-3B\-InstructGRPO66\.871\.03672\.6DAPO72\.773\.05332\.7ARPO68\.772\.04973\.5Tree\-Random72\.775\.04193\.6\\rowcolorgreen\!15PaTR\(ours\)74\.379\.03272\.8

Table 1:FrozenLake results across two model scales\. We report success rate, Pass@4, and average response length \(RLen\) for each rollout method\.![Refer to caption](https://arxiv.org/html/2607.15610v1/x2.png)Figure 2:Training curves on FrozenLake and SWE\-Bench across methods\.PaTRimproves performance earlier in training and maintains stronger trajectory\-completion behavior throughout optimization\.Table 2:SWE\-Bench results with Qwen3\-4B\-Instruct\-2507\. We compare methods using resolved rate, environment completion rate \(Env Done\), and average turns\.

### 5\.2Main Results

#### FrozenLake\.

We report the final FrozenLake performance across two model scales in Table[1](https://arxiv.org/html/2607.15610#S5.T1)\.PaTRachieves the highest success rate and Pass@4 for both Qwen2\.5\-0\.5B\-Instruct and Qwen2\.5\-3B\-Instruct\. The gain is especially pronounced for the smaller model, wherePaTRimproves the success rate from66\.5%66\.5\\%with GRPO to75\.8%75\.8\\%, suggesting that process\-guided rollout allocation is particularly useful when the base policy is less reliable\. Beyond accuracy,PaTRalso produces the shortest average response length on both model scales, indicating that the gains do not come from simply exploring longer trajectories\. The comparison with Tree\-Random further isolates the effect of process guidance\. Although Tree\-Random benefits from shared\-prefix rollout construction and is competitive in some settings, it remains belowPaTRin both success rate and Pass@4\. This shows thatPaTRgains from combining tree\-structured exploration with quality\-aware expansion, rather than from tree construction alone\. DAPO also improves over GRPO but often produces longer trajectories, highlighting the difference between objective\-level improvements and rollout\-level allocation\.

#### SWE\-Bench\.

We next evaluate the more challenging SWE\-Bench Verified setting in Table[2](https://arxiv.org/html/2607.15610#S5.T2)\. BothPaTRvariants outperform all baselines in the resolved rate\.PaTR\-PRM achieves the best result, improving over GRPO by\+5\.0\+5\.0points and over the strongest baseline ARPO by\+1\.8\+1\.8points\.PaTR\-Judge also improves over all baselines, showing that the framework can benefit from either pretrained PRM scoring or LLM\-as\-judge feedback\. BothPaTR\-PRM andPaTR\-Judge complete substantially more task instances than the baselines while using fewer turns on average than DAPO, ARPO, and Tree\-Random\. This suggests that process\-guided expansion helps the policy learn more directed interaction patterns that reach natural task completion\. Tree\-Random achieves a high environment\-done rate but lower resolved rate, indicating that tree rollouts alone can improve completion behavior, while process\-guided branch selection is needed to better align exploration with successful issue resolution\. The stronger performance ofPaTR\-PRM suggests that step\-level PRM scores provide more stable branch\-ranking signals for SWE\-style code\-editing tasks, while the judge variant remains a flexible alternative when task\-specific PRMs are unavailable\.

![Refer to caption](https://arxiv.org/html/2607.15610v1/x3.png)Figure 3:Training dynamics on SWE\-Bench\.PaTRimproves the balance between reward acquisition, interaction length, and policy entropy compared with flat and unguided tree\-rollout baselines\.

### 5\.3Training Dynamics

We further analyze training dynamics in Figure[2](https://arxiv.org/html/2607.15610#S5.F2)\.PaTRreaches higher success rates earlier than the baselines on FrozenLake, especially with the smaller Qwen2\.5\-0\.5B model\. This supports the hypothesis that process\-guided branching improves sample efficiency by focusing exploration around partial trajectories that already show progress\. The larger gap in the low\-capacity setting further suggests that adaptive rollout construction can compensate for weaker initial policies by providing more informative training groups\.

On SWE\-Bench,PaTR\-PRM andPaTR\-Judge maintain higher resolved rates and environment\-done rates across training\. In contrast, flat rollout methods improve more slowly or plateau earlier, while tree\-based baselines without process\-guided selection show less consistent gains\. The training curves therefore reinforce the main results: shared\-prefix tree construction improves rollout diversity, but quality\-aware expansion is important for converting additional exploration into reliable task progress\. Overall, the dynamics indicate thatPaTRimproves not only final performance but also the efficiency and stability of multi\-turn agent RL\.

## 6Analysis

### 6\.1Effect of Tree Hyperparameters

We examine how tree construction choices affectPaTR\-PRM on SWE\-Bench Verified\. As shown in Table[6\.1](https://arxiv.org/html/2607.15610#S6.SS1), the default setting, with branch factorM=2M\{=\}2, scoring intervalK=13K\{=\}13, and top\-k=2k\{=\}2, achieves the best resolved rate\. Expanding more branches at each checkpoint slightly reduces performance, suggesting that overly broad expansion weakens the process\-score filter\. Increasing the branch factor toM=3M\{=\}3also hurts performance, especially when expansion is concentrated on a single selected branch, indicating reduced rollout\-group diversity\. Longer scoring intervals further degrade performance, showing that delayed rescoring limits the ability to redirect exploration during long\-horizon interaction\. Overall,PaTRbenefits from a moderate branching strategy that scores frequently while keeping expansion selective\.

Branch Factor\(MM\)Interval\(KK\)Top\-kkResolved Rate↑\\uparrow\\rowcolorgray\!12Varying Top\-kk213426\.6\\rowcolorgray\!12Varying Branch Factor313225\.8313122\.0\\rowcolorgray\!12Varying Branch Interval215223\.4220224\.6\\rowcolorgreen\!20PaTR\-PRM \(default\)\\rowcolorgreen\!20213227\.2

Table 3:Ablation of tree rollout hyperparameters on SWE\-Bench Verified\. We vary the branch factorMM, scoring intervalKK, and number of expanded brancheskkper checkpoint\.### 6\.2Effect of Rollout Group Construction

We study whether pruned trajectories should be retained in the rollout group for GRPO training\. Table[4](https://arxiv.org/html/2607.15610#S6.T4)comparesBest\_n, which excludes pruned trajectories, withKeep All, which retains them together with completed branches\. Keeping all trajectories consistently improves bothPaTR\-PRM andPaTR\-Judge, with a larger gain forPaTR\-Judge from23\.4%23\.4\\%to26\.0%26\.0\\%resolved rate\. This supports our design choice of preserving the full tree output for GRPO\. Because GRPO computes advantages relative to trajectories from the same task, failed and early\-pruned branches can provide useful reward contrast rather than being discarded\. The lower average turns underKeep Allfurther suggests that pruned trajectories serve as informative negative examples without requiring full interaction budgets\.

Table 4:Effect of rollout group construction on SWE\-Bench Verified\.Keep Allretains pruned trajectories in the GRPO group, whileBest\_nexcludes them\.### 6\.3Training Signal and Policy Dynamics

Figure[3](https://arxiv.org/html/2607.15610#S5.F3)compares training reward, interaction length, and policy entropy on SWE\-Bench\. BothPaTRvariants obtain competitive training rewards while avoiding the excessive interaction length observed in some baselines\.PaTR\-PRM maintains strong reward trends with relatively short episodes, consistent with its higher resolved rate in Table[2](https://arxiv.org/html/2607.15610#S5.T2)\. The entropy curves show different exploration patterns: flat GRPO rapidly loses entropy, whilePaTR\-Judge maintains higher entropy for longer andPaTR\-PRM follows a more conservative profile\. These dynamics suggest that process\-guided tree rollout improves the balance between exploration, trajectory length, and reward acquisition during training\.

## 7Conclusion

We introducedPaTR, a process\-guided adaptive tree rollout framework for multi\-turn agent RL\. Instead of sampling complete trajectories independently,PaTRorganizes rollout groups as trees and uses task\-adaptive process feedback to decide where to expand, preserve, or prune partial trajectories\. The resulting rollout groups remain compatible with standard GRPO, since process scores guide rollout construction while policy optimization still relies on task outcome rewards\. Experiments on FrozenLake and SWE\-Bench show consistent gains over independent\-rollout and other rollout\-generation baselines, with improvements of up to\+5\.0\+5\.0points on SWE\-Bench and\+9\.3\+9\.3points on FrozenLake\. These results highlight process\-guided tree rollouts as a promising direction for effective and scalable multi\-turn agent learning\.

## Limitations

This work has several limitations\. First,PaTRrelies on the quality of the process scorer used to rank partial trajectories\. Although we instantiate the scorer with heuristics, pretrained PRMs, and LLM\-as\-judge feedback, inaccurate process scores may lead the tree rollout to expand suboptimal branches or prune useful ones\. In particular, the pretrained PRM used in our SWE\-Bench experiments, Skywork\-o1\-Open\-PRM\-Qwen\-2\.5\-7B, may favor actions that generate longer responses, which can affect branch ranking and rollout allocation\. Second, our experiments focus on FrozenLake and SWE\-Bench\. While these benchmarks cover both controlled navigation and realistic long\-horizon coding\-agent tasks, further evaluation is needed on broader multi\-turn agent domains, such as web navigation, embodied interaction, and open\-ended tool use\.

#### LLM Usage Disclosure

LLMs were used only for grammar correction and writing polishing\.

## References

- G\. Brockman, V\. Cheung, L\. Pettersson, J\. Schneider, J\. Schulman, J\. Tang, and W\. Zaremba \(2016\)Openai gym\.arXiv preprint arXiv:1606\.01540\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1)\.
- R\. Cao, S\. Bai, F\. Yao, L\. Dong, J\. Xu, and L\. Xiao \(2026\)Atpo: adaptive tree policy optimization for multi\-turn medical dialogue\.arXiv preprint arXiv:2603\.02216\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p3.1),[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- G\. Cui, L\. Yuan, Z\. Wang, H\. Wang, Y\. Zhang, J\. Chen, W\. Li, B\. He, Y\. Fan, T\. Yu,et al\.\(2025\)Process reinforcement through implicit rewards\.arXiv preprint arXiv:2502\.01456\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- A\. Djuhera, S\. R\. Kadhe, F\. Ahmed, H\. Ludwig, and H\. Boche \(2026\)TSR: trajectory\-search rollouts for multi\-turn rl of llm agents\.arXiv preprint arXiv:2602\.11767\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p2.1),[§1](https://arxiv.org/html/2607.15610#S1.p3.1),[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- G\. Dong, L\. Bao, Z\. Wang, K\. Zhao, X\. Li, J\. Jin, J\. Yang, H\. Mao, F\. Zhang, K\. Gai,et al\.\(2025a\)Agentic entropy\-balanced policy optimization\.arXiv preprint arXiv:2510\.14545\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p3.1),[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- G\. Dong, H\. Mao, K\. Ma, L\. Bao, Y\. Chen, Z\. Wang, Z\. Chen, J\. Du, H\. Wang, F\. Zhang,et al\.\(2025b\)Agentic reinforced policy optimization\.arXiv preprint arXiv:2507\.19849\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p3.1),[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px2.p1.1)\.
- L\. Espeholt, H\. Soyer, R\. Munos, K\. Simonyan, V\. Mnih, T\. Ward, Y\. Doron, V\. Firoiu, T\. Harley, I\. Dunning, S\. Legg, and K\. Kavukcuoglu \(2018\)IMPALA: scalable distributed deep\-rl with importance weighted actor\-learner architectures\.External Links:1802\.01561,[Link](https://arxiv.org/abs/1802.01561)Cited by:[§4\.3](https://arxiv.org/html/2607.15610#S4.SS3.p2.1)\.
- L\. Feng, Z\. Xue, T\. Liu, and B\. An \(2026\)Group\-in\-group policy optimization for llm agent training\.Advances in Neural Information Processing Systems38,pp\. 46375–46408\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p2.1)\.
- D\. Guo, D\. Yang, H\. Zhang, J\. Song, P\. Wang, Q\. Zhu, R\. Xu, R\. Zhang, S\. Ma, X\. Bi,et al\.\(2025\)Deepseek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Hao, Y\. Gu, H\. Ma, J\. Hong, Z\. Wang, D\. Wang, and Z\. Hu \(2023\)Reasoning with language model is planning with world model\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,pp\. 8154–8173\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- J\. He, J\. Liu, C\. Y\. Liu, R\. Yan, C\. Wang, P\. Cheng, X\. Zhang, F\. Zhang, J\. Xu, W\. Shen,et al\.\(2025\)Skywork open reasoner 1 technical report\.arXiv preprint arXiv:2505\.22312\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px4.p2.1)\.
- B\. Hui, J\. Yang, Z\. Cui, J\. Yang, D\. Liu, L\. Zhang, T\. Liu, J\. Zhang, B\. Yu, K\. Lu,et al\.\(2024\)Qwen2\. 5\-coder technical report\.arXiv preprint arXiv:2409\.12186\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px4.p2.1)\.
- N\. Jain, J\. Singh, M\. Shetty, L\. Zheng, K\. Sen, and I\. Stoica \(2025\)R2e\-gym: procedural environments and hybrid verifiers for scaling open\-weights swe agents\.arXiv preprint arXiv:2504\.07164\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1)\.
- C\. E\. Jimenez, J\. Yang, A\. Wettig, S\. Yao, K\. Pei, O\. Press, and K\. Narasimhan \(2024\)Swe\-bench: can language models resolve real\-world github issues?\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 54107–54157\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1)\.
- L\. Kocsis and C\. Szepesvári \(2006\)Bandit based monte\-carlo planning\.InEuropean conference on machine learning,pp\. 282–293\.Cited by:[§4\.3](https://arxiv.org/html/2607.15610#S4.SS3.p2.1)\.
- J\. Y\. Koh, S\. McAleer, D\. Fried, and R\. Salakhutdinov \(2024\)Tree search for language model agents\.arXiv preprint arXiv:2407\.01476\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- J\. Li, Y\. Wang, Q\. Yan, Y\. Tian, Z\. Xu, H\. Song, P\. Xu, and L\. L\. Cheong \(2026a\)Salt: step\-level advantage assignment for long\-horizon agents via trajectory graph\.InFindings of the Association for Computational Linguistics: EACL 2026,pp\. 4709–4725\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p1.1)\.
- W\. Li, J\. Wang, L\. Yu, and X\. Zhang \(2026b\)Step\-grpo: enhancing reasoning quality and efficiency via structured prm\-based reinforcement learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 31734–31742\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. Cobbe \(2024\)Let’s verify step by step\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 39578–39601\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- X\. Liu, K\. Wang, Y\. Wu, F\. Huang, Y\. Li, J\. Zhang, and J\. Jiao \(2025\)Agentic reinforcement learning with implicit step rewards\.arXiv preprint arXiv:2509\.19199\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- G\. Mundada, Z\. Huang, R\. Surana, S\. Yu, J\. Y\. Zhang, X\. Li, T\. Yu, L\. Yao, J\. Shang, J\. McAuley,et al\.\(2026\)WS\-grpo: weakly\-supervised group\-relative policy optimization for rollout\-efficient reasoning\.arXiv preprint arXiv:2602\.17025\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- T\. Schaul, J\. Quan, I\. Antonoglou, and D\. Silver \(2016\)Prioritized experience replay\.External Links:1511\.05952,[Link](https://arxiv.org/abs/1511.05952)Cited by:[§4\.3](https://arxiv.org/html/2607.15610#S4.SS3.p2.1)\.
- T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom \(2023\)Toolformer: language models can teach themselves to use tools\.Advances in neural information processing systems36,pp\. 68539–68551\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p1.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. Li, Y\. Wu,et al\.\(2024\)Deepseekmath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p1.1),[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1),[§3\.2](https://arxiv.org/html/2607.15610#S3.SS2.p1.3),[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px2.p1.1)\.
- N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.Advances in neural information processing systems36,pp\. 8634–8652\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p1.1)\.
- R\. Surana, G\. Mundada, X\. Jiang, C\. Wang, Z\. Tang, D\. Jiao, Z\. Huang, Y\. Xiong, J\. Wu, S\. Yu, X\. Li, R\. Jain, N\. Kuang, S\. Zhou, B\. Jin, Z\. Chu, T\. Yu, R\. Rossi, K\. Huang, J\. Shang, J\. Han, and J\. McAuley \(2026\)Generate, filter, control, replay: a comprehensive survey of rollout strategies for llm reinforcement learning\.External Links:2605\.02913,[Link](https://arxiv.org/abs/2605.02913)Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p2.1)\.
- S\. Tan, M\. Luo, C\. Cai, T\. Venkat, K\. Montgomery, A\. Hao, T\. Wu, A\. Balyan, M\. Roongta, C\. Wang,et al\.\(2025\)Rllm: a framework for post\-training language agents\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px4.p1.3)\.
- H\. Wang, C\. T\. Leong, J\. Wang, J\. Wang, and W\. Li \(2025\)Spa\-rl: reinforcing llm agents via stepwise progress attribution\.arXiv preprint arXiv:2505\.20732\.Cited by:[§3\.1](https://arxiv.org/html/2607.15610#S3.SS1.p1.8)\.
- P\. Wang, L\. Li, Z\. Shao, R\. Xu, D\. Dai, Y\. Li, D\. Chen, Y\. Wu, and Z\. Sui \(2024\)Math\-shepherd: verify and reinforce llms step\-by\-step without human annotations\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 9426–9439\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.
- S\. Xing, S\. Wang, C\. Yang, X\. Dai, and X\. Ren \(2025\)Lookahead tree\-based rollouts for enhanced trajectory\-level exploration in reinforcement learning with verifiable rewards\.arXiv preprint arXiv:2510\.24302\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p2.1)\.
- A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv,et al\.\(2025\)Qwen3 technical report\.arXiv preprint arXiv:2505\.09388\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1)\.
- A\. Yang, B\. Yang, B\. Hui, B\. Zheng, B\. Yu, C\. Zhou, C\. Li, C\. Li, D\. Liu, F\. Huang, G\. Dong, H\. Wei, H\. Lin, J\. Tang, J\. Wang, J\. Yang, J\. Tu, J\. Zhang, J\. Ma, J\. Yang, J\. Xu, J\. Zhou, J\. Bai, J\. He, J\. Lin, K\. Dang, K\. Lu, K\. Chen, K\. Yang, M\. Li, M\. Xue, N\. Ni, P\. Zhang, P\. Wang, R\. Peng, R\. Men, R\. Gao, R\. Lin, S\. Wang, S\. Bai, S\. Tan, T\. Zhu, T\. Li, T\. Liu, W\. Ge, X\. Deng, X\. Zhou, X\. Ren, X\. Zhang, X\. Wei, X\. Ren, X\. Liu, Y\. Fan, Y\. Yao, Y\. Zhang, Y\. Wan, Y\. Chu, Y\. Liu, Z\. Cui, Z\. Zhang, Z\. Guo, and Z\. Fan \(2024\)Qwen2 technical report\.External Links:2407\.10671,[Link](https://arxiv.org/abs/2407.10671)Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px1.p1.1)\.
- S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. Griffiths, Y\. Cao, and K\. Narasimhan \(2023\)Tree of thoughts: deliberate problem solving with large language models\.Advances in neural information processing systems36,pp\. 11809–11822\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. Cao \(2022\)React: synergizing reasoning and acting in language models\.arXiv preprint arXiv:2210\.03629\.Cited by:[§1](https://arxiv.org/html/2607.15610#S1.p1.1)\.
- Q\. Yu, Z\. Zhang, R\. Zhu, Y\. Yuan, X\. Zuo, Y\. Yue, W\. Dai, T\. Fan, G\. Liu, L\. Liu,et al\.\(2026\)Dapo: an open\-source llm reinforcement learning system at scale\.Advances in Neural Information Processing Systems38,pp\. 113222–113244\.Cited by:[§5\.1](https://arxiv.org/html/2607.15610#S5.SS1.SSS0.Px2.p1.1)\.
- L\. Zheng, W\. Chiang, Y\. Sheng, S\. Zhuang, Z\. Wu, Y\. Zhuang, Z\. Lin, Z\. Li, D\. Li, E\. Xing,et al\.\(2023\)Judging llm\-as\-a\-judge with mt\-bench and chatbot arena\.Advances in neural information processing systems36,pp\. 46595–46623\.Cited by:[§2](https://arxiv.org/html/2607.15610#S2.SS0.SSS0.Px2.p1.1)\.

## Appendix AAdditional Implementation Details

#### Training details\.

We use the same optimization hyperparameters across methods unless otherwise specified\. The learning rate is1×10−61\\times 10^\{\-6\}, the clipping ratio is0\.280\.28, the KL coefficient is0\.0010\.001, and the rollout sampling temperature is1\.01\.0\. FrozenLake is trained with batch size 64 for 400 steps, while SWE\-agent training uses batch size 8 for 300 steps\. FrozenLake experiments are run on one A100 node, and SWE\-agent experiments are run on one H200 node\.

#### Process scoring details\.

For FrozenLake, the process scorer combines accumulated step rewards with a normalized BFS shortest\-path distance to the goal, where holes are treated as blocked cells\. For SWE\-agent training, bothPaTR\-PRM andPaTR\-Judge score each branch using recent trajectory context\.PaTR\-PRM serializes the most recent 10 interaction steps and feeds them to Skywork\-o1\-Open\-PRM\-Qwen\-2\.5\-7B, which returns step\-level process scores; we use the score of the most recent step as the branch score\.PaTR\-Judge provides Qwen2\.5\-Coder\-7B\-Instruct with the task context and a compact representation of recent actions, observations, tool types, and extracted trajectory signals\. The judge outputs a trajectory\-level score, which is blended with a lightweight heuristic that rewards useful signals such as targeted testing and evidence\-based editing while penalizing repeated actions and premature termination\. We describe the heuristic and provide all judge prompts in Appendix[B](https://arxiv.org/html/2607.15610#A2)\.

#### Scoring infrastructure\.

For SWE\-bench experiments, the PRM and LLM\-judge models are hosted on separate vLLM inference servers and queried during expansion checkpoints\. This separates policy rollout generation from process scoring and avoids GPU contention during training\.

## Appendix BLLM\-as\-Judge Scoring Details

This section provides additional details about the LLM\-as\-judge scorer used inPaTR\-Judge for SWE\-Bench\. At each scoring checkpoint, the judge receives the task description and a compact representation of the current partial trajectory, including recent agent actions, environment observations, inferred tool types, and automatically extracted trajectory signals\. The judge outputs a scalar score in\[0,1\]\[0,1\]indicating how promising the current branch is for further expansion\. To make the evaluation more stage\-aware, we use different prompts for diagnosis, editing, and verification phases\.

#### Phase selection\.

The prompt is selected automatically from recent interaction patterns\. If the recent trajectory contains test\-related actions or observations, such as runningpytest,unittest, or observing pass/fail messages, we use the verification prompt\. If the recent trajectory contains file modification actions, such as patching, insertion, or replacement, we use the editing prompt\. If the recent trajectory mainly contains repository exploration, such as search, file inspection, traceback analysis, or command\-line reading, we use the diagnosis prompt\. When no specific phase is detected, we use the default prompt\. This design allows the judge to evaluate the type of progress that is most relevant to the current stage of problem solving\.

#### Heuristic score\.

In addition to the LLM score, we compute a lightweight heuristic score from recent trajectory signals\. The heuristic starts from a neutral value and adjusts the score according to observable behaviors\. It penalizes repeated identical actions, premature finish actions, command failures, and edits made without prior evidence from search, file inspection, or testing\. It rewards signals associated with useful progress, including targeted test execution, passing tests, informative tracebacks, code or file information discovered during exploration, and edits made after relevant evidence has been collected\. The final branch score is a weighted combination of the LLM judgment and the heuristic score, with the LLM judgment receiving the larger weight\. The heuristic acts as a stabilizing signal, especially when the LLM judge assigns overly optimistic scores to repetitive or weakly grounded trajectories\.

#### Judge prompts\.

We list the system prompt and all phase\-specific scoring prompts below[1](https://arxiv.org/html/2607.15610#LST1),[2](https://arxiv.org/html/2607.15610#LST2),[3](https://arxiv.org/html/2607.15610#LST3),[4](https://arxiv.org/html/2607.15610#LST4), and[5](https://arxiv.org/html/2607.15610#LST5)\. The placeholders\{task\}and\{trajectory\}are filled with the task description and the compact trajectory representation at each scoring checkpoint\.

YouevaluatepartialSWE\-agenttrajectoriesfortree\-searchexpansion\.

OutputONLYvalidJSON:\{"score":<0\.0to1\.0\>\}\.Nothingelse\.

Code 1:System prompt for the LLM\-as\-judge scorer\.ScorethispartialSWE\-agenttrajectoryfortree\-searchbranching\.

Consider:

\-Istheagentmakingmeasurableprogresstowardsolvingtheissue?

\-Areitsactionsgroundedinevidencefromthecodeorobservations?

\-Isitavoidingrepetitiveoraimlesscommands?

\-Ifwecontinuefromthisstate,howlikelywillthisbranchleadtoacorrectfix?

0\.0=stuck,looping,orwrongdirection

0\.5=somerelevantworkbutunclearprogress

1\.0=clearlyontrack,strongevidenceofprogress

Task:

\{task\}

Trajectory:

\{trajectory\}

OutputONLY:\{"score":<0\.0to1\.0\>\}

Code 2:Default judge prompt\.ScorethispartialtrajectoryduringEXPLORATION/DIAGNOSIS\.

Consider:

\-Istheagentsearchingintherightfilesanddirectories?

\-Isitnarrowingdownthebuglocationwitheachstep?

\-Isitgatheringevidence\(readingcode,reproducingthebug\)ratherthanguessing?

\-Isitavoidingrepeatedsearchesthatyieldnonewinformation?

0\.0=aimlessbrowsing,wrongfiles,repetitivecommands

0\.5=relevantexplorationbutslowprogress

1\.0=efficientlylocatingtherootcause

Task:

\{task\}

Trajectory:

\{trajectory\}

OutputONLY:\{"score":<0\.0to1\.0\>\}

Code 3:Judge prompt for the diagnosis phase\.ScorethispartialtrajectoryduringEDITING\.

Consider:

\-Istheagenteditingthefilethatevidencepointedto?

\-Isthechangeminimalandtiedtothediagnosedrootcause?

\-Didtheagentcollectenoughevidencebeforeediting,orisitguessing?

\-Couldthiseditintroducenewbugsorbreakotherfunctionality?

0\.0=editingblind,wrongfile,speculativechanges

0\.5=reasonableeditbutunclearifitaddressesrootcause

1\.0=precise,evidence\-basedfixintherightlocation

Task:

\{task\}

Trajectory:

\{trajectory\}

OutputONLY:\{"score":<0\.0to1\.0\>\}

Code 4:Judge prompt for the editing phase\.ScorethispartialtrajectoryduringTESTING/VERIFICATION\.

Consider:

\-Istheagentrunningtestsrelevanttotheissue\(notrandomtestsuites\)?

\-Iftestsfail,doestheagentappeartounderstandthefailure?

\-Iftestspass,dotheyactuallycoverthebugthatwasfixed?

\-Istheagentverifyingthefixratherthandeclaringprematuresuccess?

0\.0=irrelevanttests,ignoringfailures,falsesuccess

0\.5=runningsometestsbutcoverageofthefixisunclear

1\.0=targetedverificationthatconfirmsthefixworks

Task:

\{task\}

Trajectory:

\{trajectory\}

OutputONLY:\{"score":<0\.0to1\.0\>\}

Code 5:Judge prompt for the verification phase\.