Skip to content

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

🕒 Published (v1): 2026-07-17 04:16 UTC · Source: Arxiv · link

Why this paper was selected

Process-reward tree rollout for multi-turn RL; solves GRPO/RLOO credit-assignment failure on long-horizon agent tasks

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

PATR (Process-Scorer Guided Adaptive Tree Rollout) replaces GRPO's flat independent-trajectory sampling with a tree rollout scheme that periodically scores partial trajectories and selectively expands, survives, or prunes branches. Applied to multi-turn LLM agent training, it improves SWE-Bench Verified resolved rate by +5.0 points and FrozenLake success rate by +9.3 points over GRPO, without altering the policy optimization objective.

Problem

GRPO and related methods sample complete trajectories independently and uniformly, treating every trajectory equally regardless of whether intermediate states are promising or degenerate. In long-horizon agentic tasks with sparse/delayed rewards, this wastes rollout budget on dead-end attempts (e.g., repeated tool-use loops) and under-explores high-quality partial states. Existing tree-rollout methods for agents either branch on entropy/uncertainty signals that do not measure task progress, or greedily select the highest-scoring action at every turn (biasing distribution and discarding informative negatives).

Method

PATR constructs a tree of partial trajectories per task prompt rather than sampling full independent rollouts. Starting from \(B_0\) initial branches, every \(K\) turns a task-adaptive process scorer \(S_\phi : (x, \tau^t_i) \to [0,1]\) evaluates each active partial trajectory and routes it into one of three paths:

  • Expansion: high-scoring branches spawn \(M\) child continuations from the same intermediate state (sharing the parent prefix), replacing the parent in the active set.
  • Survival: moderate-scoring branches advance another \(K\) steps and are re-evaluated.
  • Pruning: branches scoring below \(\text{median} - \alpha\) or repeating the same action for \(\Theta\) consecutive turns are terminated early and moved to the completed set \(C\) as negative examples.

The process scorer is instantiated in three ways: (1) a heuristic over accumulated step rewards and distance-to-goal for navigation; (2) a pretrained PRM (Skywork-o1-Open-PRM-Qwen-2.5-7B) with recent trajectory serialized into a problem–response format and step-level scores aggregated via \(s^t_i = f_\text{agg}(c_1,\ldots,c_{L_i})\); (3) an LLM-as-judge (Qwen2.5-Coder-7B-Instruct) with phase-specific prompts (diagnosis/edit/verification) blended with a lightweight heuristic: \(s^t_i = \lambda s_\text{judge}(\tau^t_i) + (1-\lambda)s_\text{heur}(\tau^t_i)\).

After tree construction, all completed/failed/pruned trajectories form the rollout group \(G(x)\), and standard GRPO is applied with outcome rewards only — the process scorer never enters the policy objective or advantage normalization.

Key Contributions

  • PATR framework: process-scorer-guided expansion/survival/pruning over a multi-turn trajectory tree, replacing flat independent rollout in GRPO.
  • Three plug-in process scorer instantiations (heuristic, pretrained PRM, LLM-as-judge) behind a unified scalar interface, requiring no changes to the GRPO objective.
  • Empirical validation on FrozenLake and SWE-Bench Verified, including analysis of tree hyperparameters (branch factor \(M\), scoring interval \(K\), expansion set size).
  • Demonstrated compatibility: process scores guide allocation only; pruned branches are retained as negative examples, preserving rollout diversity for advantage estimation.

Results

  • FrozenLake (Qwen2.5-0.5B): PATR 75.8% success rate vs. GRPO 66.5% (+9.3 pp), ARPO 69.7%, DAPO 71.0%; Pass@4: 78% vs. 67%.
  • FrozenLake (Qwen2.5-3B): PATR 74.3% vs. GRPO 66.8% (+7.5 pp), ARPO 68.7%, DAPO 72.7%; shortest average response length (327 tokens vs. next-best 367).
  • SWE-Bench Verified (Qwen3-4B-Instruct-2507): PATR-PRM 27.2% resolved rate vs. GRPO 22.2% (+5.0 pp), ARPO 25.4% (+1.8 pp over strongest baseline), DAPO 24.6%; PATR-Judge 26.0%.
  • PATR-PRM achieves 92.2% environment-done rate vs. GRPO 79.2%, with fewer average turns (24.4) than DAPO (31.6) and ARPO (27.3).
  • Ablation: \(M=2\), \(K=13\), top-\(k=2\) is the best configuration; broader expansion or longer scoring intervals degrade performance.
  • Training curves show PATR reaches higher resolved rates earlier, indicating improved sample efficiency.

Limitations

  • Introduces additional inference cost from periodic process scoring (LLM-as-judge or PRM calls every \(K\) turns), which is not fully quantified against the baseline sampling budget.
  • Tree construction hyperparameters (\(B_0\), \(K\), \(M\), \(\alpha\), \(\Theta\)) require task-specific tuning; sensitivities are only analyzed for PATR-PRM on SWE-Bench.
  • The LLM-as-judge scorer requires phase-specific prompt engineering (diagnosis/edit/verification phases) that may not transfer automatically to new task domains.
  • Evaluated on two task families (grid navigation, code editing); generalization to other multi-turn agent domains (e.g., web browsing, tool-use dialogue) is not demonstrated.
  • The bias introduced by non-uniform rollout sampling relative to the current policy is discussed qualitatively but not formally bounded.

Relevance to Agentic AI / LLM Agents

PATR directly addresses a core bottleneck in training LLM agents via RL: the inefficiency of flat trajectory sampling when tasks are long-horizon, rewards are sparse, and intermediate states vary widely in quality. By reframing the rollout group as a process-score-guided tree, it offers a modular improvement to GRPO-style training that is compatible with existing policy objectives — relevant to any agentic RL pipeline (SWE-agents, tool-use agents, navigation agents). The three scorer variants (heuristic, PRM, LLM-judge) make the approach practically deployable across domains even without a task-specific PRM, connecting to the broader literature on process reward models and their role in agent training. This sits at the intersection of RL training efficiency and agentic scaffolding, with direct implications for researchers working on scalable agent fine-tuning.