---
title: "PORTool : Importance-Aware Policy Optimization with Rewarded Tree for Multi-Tool-Integrated Reasoning"
authors: ["{}^{\\text{\\faIconFromMacro{faApple}}}", "Feijie Wu", ",", "Weiwu Zhu", "Yuxiang Zhang", "Soumya Chatterjee", "Jiarong Zhu", "Fan Mo", ", Rong Luo", ", Jing Gao", "Apple,", "Purdue University"]
url: "https://arxiv.org/abs/2510.26020"
sections: 92
estimated_tokens: "21.7k"
---

## Contents
- 1 Introduction
- 2 Related Works
  - RL Algorithms for LLM Reasoning.
  - Tool-use Agent Training.
- 3 PORTool
  - 3.1 Problem Formulation
    - Autonomous Agentic System.
    - Problem Formulation.
    - Limitations of GRPO in Training Tool-use Agent.
      - Theorem 3.1 (Collateral Unlearning of Correct Steps) .
  - 3.2 Algorithm Description
    - Step 1: Tree Rollouts.
    - Step 2: Reward Computation.
    - Step 3: Policy Optimization.
      - Theorem 3.2 .
- 4 Experiments
  - 4.1 Setup
    - Dataset.
    - Tool environment.
    - Models and training protocol.
    - Baselines.
    - Evaluation Metrics and Evaluation Benchmark.
  - 4.2 Comparison with Other Baselines
  - 4.3 Discussions
    - 4.3.1 Effect of the Decay Factor γ \gamma
    - 4.3.2 Effect of the Advantage Coefficients
    - 4.3.3 Effect of Reward Function R ​ ( s j , t ) R(s_{j,t}) Design
- 5 Conclusion
- References
- Appendix A Additional Details of PORTool
  - A.1 Tree Rollout
  - A.2 Rollout-Tree Notations
    - Shared-step index set m ​ ( ⋅ ) m(\cdot) .
    - Child set C ​ ( ⋅ ) C(\cdot) .
    - Fork set and fork count.
  - A.3 Reward Components and Rescaled Formatting Reward
    - Outcome reward R out R_{\mathrm{out}} .
    - Raw formatting score r fm ∈ [ 0 , 1 ] r_{\mathrm{fm}}\in[0,1] .
    - Correctness-dominant rescaling.
  - A.4 Step-wise Reward and Adaptive Aggregation G G
    - Adaptive rule for G G .
    - Toy example: when G = avg G=\mathrm{avg} (tied best-case children).
  - A.5 Fork-Relative Advantages and Derivation of Theorem 3.2
    - Trajectory-relative and fork-relative advantages.
    - Token-level mixed advantage.
    - Fork set and notation.
    - Token-level GRPO losses.
    - Fork-wise empirical objective.
    - Reindexing lemma (disjoint union).
    - Matching normalizers and the choice of ω 2 \omega_{2} .
    - Remarks.
- Appendix B Proof of Theorem 3.1
  - Assumptions.
  - Why the additional assumption is needed.
  - Notation.
  - Step 1: z-score values.
  - Step 2: local GRPO update on the probability of s ∗ s^{*} .
  - Step 3: expected change in log ⁡ p s ∗ \log p_{s^{*}} .
  - Step 4: simplify the condition B − C < 0 B-C<0 .
  - Step 5: conclusion.
- Appendix C Extended Experimental Details
  - C.1 Data Construction and Splits
    - Source and anonymization.
    - Domains and temporal properties.
    - Splits.
    - Why train on our dataset instead of existing tool-use benchmarks.
  - C.2 Executable Tool Environment and Interaction Format
    - Agent I/O contract.
    - Termination.
    - Reproducibility for time-sensitive queries.
  - C.3 Automatic Outcome Judge and Calibration
    - Evaluator Agent.
    - Calibration.
    - Variance reduction.
  - C.4 Training and Implementation Details
    - Framework and decoding.
    - Rollouts and horizons.
    - Optimization details.
    - Key hyperparameters.
  - C.5 Additional Benchmarks
    - ToolBench.
    - TravelPlanner.
  - C.6 Implementation
- Appendix D Tool Schemas and Prompt Cards
- Appendix E Example I: which team has better performance in the last three seasons: the steelers, ravens, or eagles
  - E.1 PORTool
- Appendix F Example II: What’s 70 days from march 21
  - F.1 ToolRL
  - F.2 PORTool
- Appendix G Example III: How many hours to tomorrow
  - G.1 PORTool with Qwen-2.5-7B
  - G.2 PORTool with Qwen-3-1.7B

## Abstract

Abstract Multi-tool-integrated reasoning enables LLM-empowered tool-use agents to solve complex tasks by interleaving natural-language reasoning with calls to external tools. However, training such agents using outcome-only rewards suffers from credit-assignment ambiguity , obscuring which intermediate steps (or tool-use decisions) lead to success or failure. In this paper, we propose PORTool , an importance-aware policy-optimization algorithm that reinforces agents’ tool-use competence from outcome-level supervision while assigning reward at the step level. Specifically, PORTool generates a rewarded rollout tree in which trajectories share prefixes before branching, enabling direct comparisons among alternative tool-use decisions within the same context. It then estimates each step’s importance by a correctness-dominant signal, i.e., whether descendants of that step can ultimately produce a correct final answer, plus an auxiliary term indicating whether the step’s tool calls execute successfully. Using these step-wise importance estimates, PORTool updates the policy to generate efficient tool-call steps, guided by both local comparisons within each branching decision and the overall quality of entire trajectories. Experiments show that PORTool improves final-answer accuracy while reducing tool-call steps compared with state-of-the-art baselines, and ablation studies confirm the robustness of the proposed step-wise importance estimates.

## 1 Introduction

As a representative paradigm for synergizing reasoning and action, the ReAct framework yao2023react activates large language models (LLMs) to interleave step-by-step reasoning with structured tool calls, achieving strong problem-solving performance. Early works yao2023tree; yao2023react; wei2022chain; schick2023toolformer; wu2025talk enable such a tool-integrated capability primarily through prompt engineering, in which crafted demonstrations guide the model to alternate between generating reasoning traces and invoking tools. However, these approaches provide reasoning within a generic context rather than learning from actual interactions with external tools, thereby limiting their effectiveness in solving complex, multi-step tasks. This limitation highlights the importance of exploring how to augment LLMs’ reasoning and acting capabilities through the interactive use of multiple executable tools.

Agentic reinforcement learning (agentic RL) zhang2025landscape has therefore emerged as a promising direction to address this gap, spurring a growing number of works on tool-use training qian2025toolrl; zhang2025nemotron; dong2025agentic; zeng2025reinforcing; jin2025search; li2025torl; singh2025agentic; xue2025simpletir; feng2025retool; wei2025autotir; lin2025understanding. Specifically, it is a paradigm that optimizes an LLM as a *sequential decision-making agent*: given a user query and an interaction history, the agent repeatedly (i) reasons over its current context, (ii) takes actions such as calling external tools, (iii) observes tool outputs and other environment feedback, and (iv) updates its policy to maximize the expected reward over the interaction episode. In the multi-tool-use setting, existing agentic RL methods differ mainly in where the supervised reward signal is applied: some provide rewards at each action step (e.g., next-tool-call validity and correctness), denoted by *step-supervised*, while others optimize complete multi-step trajectories from outcome-level reward, denoted by *trajectory-supervised*.

Figure: Figure 1: ToolRL qian2025toolrl (step-supervised; top) fails under a real-time ambiguity, while PORTool (trajectory-supervised; bottom) queries runtime context and answers correctly.
Refer to caption: 2510.26020v2/x1.png

In the *step-supervised* regime, agentic RL applies rewards at each action step, effectively reducing multi-tool interaction to a sequence of *next-tool-call* decisions. Representative examples include ToolRL qian2025toolrl and Tool-N1 zhang2025nemotron, which construct training data in a structured state-action form: each state contains the user query, tool descriptions, and optionally a partial tool-call history, while the supervised signal specifies the *expected* tool call(s) for the next step.
Both methods fine-tune with group-relative policy optimization (GRPO) shao2024deepseekmath to improve local tool-call selection: they sample multiple candidate tool calls under the same state and assign step-level rewards based on consistency with the expected call (e.g., correct tool name/arguments and valid formatting).
However, step-level supervision has notable limitations:
(i) it implicitly enforces a canonical routine, penalizing alternative but valid tool-use strategies and thereby discouraging exploration; and (ii) since rewards are provided only for the next action, training does not capture long-horizon dependencies across tool interactions. In non-stationary settings (e.g., search results differ for equivalent paraphrases or for the same query at different times), this leads to brittle behavior when tools return unexpected outputs or fail (as in [Figure˜1](#S1.F1)).

A complementary line of work studies *trajectory-supervised* agentic RL, including ARPO dong2025agentic and AgentFlow li2025flow. By executing tools during training and optimizing from outcome-level feedback on complete trajectories, these methods avoid relying on ground-truth intermediate tool calls and better match the deployment interaction pattern.
However, outcome-only optimization exposes a fundamental *credit-assignment ambiguity*: many distinct tool-use trajectories can reach the same outcome, but a single trajectory-level reward provides no reliable signal about which intermediate decisions are decisive, recoverable, or incidental. As a result, existing approaches often broadcast the same trajectory-level reward across all steps zeng2025reinforcing, which can (i) reinforce formatting-invalid or failure-prone tool calls that happen to appear in otherwise successful rollouts, and (ii) suppress steps that are necessary or informative but frequently co-occur with failures under dynamic tool responses.
These challenges motivate learning a *step-wise importance* signal using only outcome feedback and tool-execution traces—so that optimization can focus updates on the tool decisions that actually determine downstream success.

To overcome this credit-assignment ambiguity, our key idea is to turn sparse outcome feedback into *prefix-matched, within-context comparisons* by organizing rollouts into a rewarded tree.
Building on this idea, we propose PORTool, an importance-aware Policy Optimization method built around a Rewarded rollout tree for multi-tool-integrated reasoning.
Instead of sampling trajectories independently, PORTool generates a bounded-branching set of rollouts that share the same prefix and then diverge at selected tool-call steps, creating matched-prefix comparisons between competing tool-use decisions under an identical interaction history. From sparse outcome supervision (final-answer correctness) and lightweight tool-execution signals (format validity and successful invocation), PORTool assigns each step a prefix-consistent importance score by aggregating the outcomes of its descendants—so shared steps receive a single consistent credit, while sibling candidates at a fork are distinguished by how reliably they lead to success. PORTool then updates the policy using both (i) these fine-grained, fork-level comparisons and (ii) coarse-grained, trajectory-level feedback, steering learning toward tool calls that are effective, robust to tool variability, and efficient in tool usage. As illustrated in [Figure˜1](#S1.F1), PORTool improves robustness to ambiguous intent and dynamic tool responses, while reducing failure-prone or unnecessary tool calls.

Contributions. Throughout this work, our contributions are summarized as follows:

- •
We study *trajectory-supervised* agentic RL for multi-tool-integrated reasoning in an executable environment with dynamic, real-time tool outputs. We also show that *credit-assignment ambiguity* can cause collateral unlearning of steps that are necessary for correctness ([Theorem˜3.1](#S3.Thmtheorem1)).
- •
We propose PORTool, which organizes rollouts into a *rewarded, prefix-sharing tree* to enable *prefix-matched within-context comparisons*, and learns a *prefix-consistent step-wise importance* signal from sparse outcome feedback augmented with bounded tool-execution/format validity signals (with correctness dominance).
- •
We derive a principled scaling for combining *fork-relative* and *trajectory-relative* advantages, and empirically show that PORTool improves final-answer accuracy while reducing the number of tool-call steps compared with state-of-the-art baselines; extensive ablations validate the necessity and robustness of the proposed step-wise design.

## 2 Related Works

##### RL Algorithms for LLM Reasoning.

Recent works schulman2017proximal; rafailov_direct_2023; ethayarajh2024kto; ahmadian2024back; zheng2025group; yu2025dapo; chu2025gpg; wu2024towards; wang2025reinforcement1 show that policy-optimization post-training can reliably improve LLM behaviors. As a promising direction, reasoning-aware RL algorithms equip LLMs with autonomous reasoning capabilities by applying verifiable or rule-based rewards, thereby boosting their performance on math, code, and long-horizon tasks havrilla2024teaching; zhu2025surprising; yeo2025demystifying; liu2025understanding; chu2025gpg; zeng2025reinforcing. As a type of verifiable reward, process reward could assign a finer importance score to each step, but these approaches require dense step annotations or an additional verifier yu2025steptool; zeng2025reinforcing; lightman2023let; uesato2022solving; setlur2024rewarding, which may be costly and brittle under dynamic tool execution. The recent GiGPO feng2025group has addressed these limitations by deriving step-wise rewards from the final outcome and normalizing them across actions within the same state.
However, it matches repeated "anchor" states across trajectories, which depends on reliable state matching; PORTool instead compares sibling actions under identical prefixes and incorporates tool-call execution/format checks.
This avoids brittle state matching under dynamic tool outputs and yields more reliable step-wise reward and advantage assignments.

##### Tool-use Agent Training.

Recent works train tool-use agents mainly via two paradigms: supervised fine-tuning (SFT) on curated or synthetic tool-call traces schick2023toolformer; qin2023toolllm; parisi2022talm; patil2024gorilla; tang2023toolalpaca; liu2024apigen; liu2024toolace and reinforcement learning (RL) with interaction/execution feedback nakano2021webgpt; jin2025search; qian2025toolrl; zhang2025nemotron; feng2025retool; li2025torl; li2025flow; sheng2024hybridflow; yu2025steptool; dong2025agentic; wei2025autotir; yifeilu2025codetool; gao2026teaching.
SFT improves tool-call formatting and basic tool selection, but models trained solely by imitation often exhibit limited exploration and robustness under distribution shifts chu2025sft.
RL mitigates these issues by learning from trial-and-error:
Search-R1 jin2025search applies GRPO-style optimization for search-augmented reasoning, but a uniform trajectory-level feedback to all steps could result in the method having credit-assignment ambiguity.
ARPO dong2025agentic improves trajectory sample efficiency by branching additional partial rollouts only at tool-call steps where the policy is deemed uncertain. However, because these branching points are chosen by hand-designed uncertainty heuristics, ARPO may fail to explore or correct confident-but-wrong (low-uncertainty) tool decisions. In contrast, the proposed PORTool constructs shared-prefix rollouts and leverages outcome supervision, along with execution/format feedback, to infer step importance, ultimately enabling finer-grained and more reliable step-level advantage assignment.

## 3 PORTool

### 3.1 Problem Formulation

##### Autonomous Agentic System.

We train multi-tool-use LLMs in an autonomous agentic system composed of two agents with distinct roles: (i) a tool-use agent that interacts with an executable tool environment and optimizes its local policy via reinforcement learning, and (ii) an evaluation agent that provides outcome-level supervision by judging whether the final answer is correct.

$\bullet$ Tool-use agent: The tool-use agent is parameterized by a policy $\pi_{\theta}$ (an LLM) and is trained on a dataset of user queries $\mathcal{Q}$. Queries in $\mathcal{Q}$ generally require multi-step reasoning and may admit multiple valid tool-use trajectories (e.g., different decompositions or tool-invocation orders that all lead to correct answers). The agent is equipped with a tool set $\mathcal{U}$, consisting of multiple function-like tools. Each tool is identified by a unique name and a schema that specifies required arguments, types, and validity constraints (e.g., structured JSON formatting). Executing a tool call returns a structured output; malformed calls or invalid configurations yield explicit error messages. The tool set includes a dedicated terminal tool, response_gen, whose invocation indicates that the agent has finished reasoning and is ready to output the final answer.

Given a query $q\in\mathcal{Q}$, the tool-use agent produces a multi-step interaction trajectory with multiple external tools. At each step, it emits a reasoning segment (e.g., <think> ... </think>) followed by a structured tool-call segment (e.g., <tool_call> ... </tool_call>) that may contain one or more tool calls that can be executed independently. Tool responses are appended to the context and condition subsequent steps. This process repeats until either the agent invokes response_gen or the maximum step limit is reached.

$\bullet$ Evaluation agent: After the tool-use agent terminates, an evaluation agent $R_{out}$ (implemented as a stronger, fixed LLM judge) evaluates the correctness of the final answer for query $q$, using the full trajectory (including intermediate tool outputs and errors) as evidence. Specifically, the agent could compare the trajectory outcome against a reference answer when available, or judge evidence-supported correctness for queries lacking a fixed expected answer. The evaluation returns one of {true, false, unable_to_answer}, which we map to outcome rewards $\{+1,-1,0\}$. The unable_to_answer outcome is important in practice: it distinguishes trajectories that follow a reasonable strategy but cannot complete the task due to tool limitations (e.g., missing information, tool failures, or irrecoverable execution issues) from trajectories that produce a "no answer" response.

##### Problem Formulation.

We train the tool-use agent $\pi_{\theta}$ in the autonomous agentic system described above. For each query $q\sim\mathcal{Q}$, the agent interacts with the executable multi-tool environment $\mathcal{U}$ to generate a *multi-step tool-call trajectory* $\tau\overset{\triangle}{=}\{q,(s_{1},a_{1}),\dots,(s_{T},a_{T})\}$. At each step $t\in[T]$, the agent samples a tool-call step $s_{t}\sim\pi_{\theta}(\cdot|q,U,\{(s_{i},a_{i})\}_{i<t})$, where $s_{t}$ contains both reasoning traces and one or more structured tool calls. The environment executes the tool calls embedded in $s_{t}$ and returns tool outputs (or explicit error messages) $a_{t}=\mathcal{U}(s_{t})$, which are appended to the agent’s context to condition subsequent steps. The trajectory terminates when the agent invokes response_gen or reaches the step limit.

Let us consider that a query $q$ would create $n$ different tool-call trajectories $\{\tau_{j}\}_{j\in[n]}$ ($n\geq 1$) from the behavior policy $\pi_{\theta_{\text{old}}}$, where $\tau_{j}=\{q,(s_{j,1},a_{j,1}),\dots,(s_{j,T_{j}},a_{j,T_{j}})\}$. The evaluation agent assigns an outcome reward $R_{out}(q,\tau_{j})\in\{+1,0,-1\}$. Subsequently, we optimize $\pi_{\theta}$ using a GRPO-style clipped surrogate at the token level without an explicit KL regularizer to a reference model shao2024deepseekmath; guo2025deepseek; qu2025tool, by maximizing

$$ $\displaystyle J(\theta)=\mathbb{E}_{\begin{subarray}{c}q\sim Q,\\ \{\tau_{j}\}_{j=1}^{n}\sim\pi_{\theta_{\text{old}}}(\tau\mid q,U)\end{subarray}}\left[\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tau_{j}|}\sum_{t=1}^{T_{j}}\sum_{o=1}^{|s_{j,t}|}f_{\theta}(s_{j,t,o})\right],$ (1) $$

where $|\tau_{j}|=\sum_{t\in[T_{j}]}|s_{j,t}|$ indicates the total token length of the generated content; $s_{j,t,o}$ is the $o$-th token of step $s_{j,t}$. The per-token objective is

$$ $\displaystyle f_{\theta}(s_{j,t,o})\overset{\triangle}{=}\min\Bigl(\rho_{\theta}(s_{j,t,o})\,A(s_{j,t,o}),\textsf{clip}_{1-\varepsilon}^{1+\varepsilon}\!\bigl(\rho_{\theta}(s_{j,t,o})\bigr)\,A(s_{j,t,o})\Bigr),$ $$

where $A(s_{j,t,o})$ is the token-level advantage at $s_{j,t,o}$, and

$$ $\displaystyle\rho_{\theta}(s_{j,t,o})\overset{\triangle}{=}\frac{\pi_{\theta}(s_{j,t,o}|q,U,\{(s_{j,i},a_{j,i})\}_{i<t},s_{j,t,<o})}{\pi_{\theta_{old}}(s_{j,t,o}|q,U,\{(s_{j,i},a_{j,i})\}_{i<t},s_{j,t,<o})}.$ $$

##### Limitations of GRPO in Training Tool-use Agent.

An important ingredient in Problem equation [1](#S3.E1) is the token-level advantage, which quantifies the relative contribution of each step (and its tokens) to the final outcome. Existing trajectory-supervised methods, such as GRPO, typically assign a *uniform* advantage within each trajectory (i.e., all tokens in $\tau_{j}$ receive the same credit derived from $R_{out}(q,\tau_{j})$, which ignores the fact that different tool-call steps can have vastly different causal importance.
This creates a *credit-assignment ambiguity*: when a single trajectory-level advantage is broadcast to all steps, the update cannot distinguish which intermediate tool decisions actually caused success.
[Theorem˜3.1](#S3.Thmtheorem1) formalizes this ambiguity by showing that, given a step $s^{*}$ is *necessary* for correctness, i.e., $\Pr(\text{correct}\mid s^{*}\,\text{absent})=0$, a GRPO-style update can *decrease* its sampling probability $p_{s^{*}}(\theta)$, which *unlearns* the correct step.

###### Theorem 3.1 (Collateral Unlearning of Correct Steps) .

Suppose $s^{*}$ is a necessary step for answering a query $q$. Under a policy $\theta$, denote by $p_{s^{*}}(\theta)$ the probability that $s^{*}$ appears in a trajectory, and by $p^{(c)}_{s^{*}}(\theta)\overset{\triangle}{=}\Pr(\text{correct}\mid s^{*}\text{ appears})$ the probability of a correct outcome conditioned on trajectories that contain $s^{*}$.
For the pre-update policy $\theta_{\text{old}}$, define

$$ $L_{c}\triangleq\mathbb{E}_{\theta_{\text{old}}}\!\left[|\tau|^{-1}\,\middle|\,s^{*},\,\text{correct}\right];\,L_{w}\triangleq\mathbb{E}_{\theta_{\text{old}}}\!\left[|\tau|^{-1}\,\middle|\,s^{*},\,\text{incorrect}\right];\,L_{\neg}\triangleq\mathbb{E}_{\theta_{\text{old}}}\!\left[|\tau|^{-1}\,\middle|\,s^{*}\text{ absent}\right],$ $$

where $|\tau|$ denotes the total trajectory length in tokens.
After applying a GRPO-style update from $\theta_{\text{old}}$ to $\theta_{\text{new}}$, if

$$ $\bigl(1-p_{s^{*}}(\theta_{\text{old}})p^{(c)}_{s^{*}}(\theta_{\text{old}})\bigr)L_{c}<p_{s^{*}}(\theta_{\text{old}})\left(\bigl(1-p^{(c)}_{s^{*}}(\theta_{\text{old}})\bigr)L_{w}-L_{\neg}\right),$ $$

then

$$ $p_{s^{*}}(\theta_{\text{new}})<p_{s^{*}}(\theta_{\text{old}})$ $$

for sufficiently small update step size.

The proof is provided in [Appendix˜B](#A2). This theorem motivates designing an advantage signal so that the important steps always receive positive advantages to prevent unlearning, which is the goal of PORTool.

###### Theorem 3.1 (Collateral Unlearning of Correct Steps) .

### 3.2 Algorithm Description

Figure: Figure 2: Overview of PORTool Workflow
Refer to caption: 2510.26020v2/x2.png

Optimizing the tool-use agent with the formulated objective (i.e., Problem equation [1](#S3.E1)) hinges on estimating advantages of informative tokens $A(\cdot)$. A core difficulty of existing agentic RL methods shao2024deepseekmath; li2025flow is that multiple trajectories are typically generated *independently*, so when only the final outcome reward is available, all tokens in a trajectory receive the same credit. This leads to credit-assignment ambiguity and even unlearns necessary steps for correctness (Theorem [3.1](#S3.Thmtheorem1)). PORTool resolves this by (i) generating *prefix-sharing* trajectories organized as a bounded-branching tree, (ii) computing a *step-wise importance* score from dominant outcome supervision plus auxiliary execution/format feedback, and (iii) using this importance signal to construct *fork-relative* advantages that complement standard trajectory-relative advantages. [Figure˜2](#S3.F2) provides an overview of how the proposed PORTool runs these steps.
Due to space limit, more concrete details are provided in [Appendix˜A](#A1).

##### Step 1: Tree Rollouts.

Given an input query $q\sim\mathcal{Q}$, we sample $n$ tool-call trajectories under the policy $\pi_{\theta_{old}}$, but unlike standard GRPO, we do not sample them independently. Instead, we organize rollouts as a *bounded-branching rollout tree* with branching factor $f$: trajectories are encouraged to share prefixes for several steps and then diverge at selected steps, producing multiple alternative actions under the *same* interaction history. Algorithm [1](#alg1) summarizes the rollout process in pseudocode form.

Concretely, each node in the tree corresponds to a tool-call step $s$ (reasoning + tool calls) together with its executed tool responses. Let $m(s)$ denote the set of trajectory indices that pass through step $s$, and let $C(s)$ denote the (index set of) child branches that correspond to *distinct* next-step candidates from the same prefix. This tree structure provides the key training signal missing in independent rollouts: *within the same prefix*, we can directly compare competing next-step decisions.

##### Step 2: Reward Computation.

After executing tools and terminating all sampled trajectories, the evaluation agent assigns an outcome reward $R_{out}(q,\tau_{j})\in\{+1,0,-1\}$ to each complete trajectory $\tau_{j}$. PORTool then assigns each intermediate step $s_{j,t}$ a *step-wise importance score* that reflects whether descendants of that step can ultimately reach a correct outcome, while also incorporating a small auxiliary signal for tool-call formatting/execution:

$$ $\displaystyle R(s_{j,t})\overset{\triangle}{=}G\!\left(\left\{\gamma^{T_{k}-t}R_{out}\!\left(q,\tau_{k}\right)+R_{fm}\!\left(s_{j,t}\right)\right\}_{k\in m\!\left(s_{j,t}\right)}\right)$ (2) $$

where $\gamma\in[0,1]$ is a decay factor that favors trajectories that solve the task with fewer steps, $R_{fm}(s_{j,t})\in[-0.25,0.25]$ is a bounded formatting/execution reward derived from tool-call validity (e.g., parseable structured tool calls and successful tool invocation), and $G$ is an aggregation operator applied *consistently* to all trajectories sharing the same step. Intuitively, $R(s_{j,t})$ estimates the *importance* of step $s_{j,t}$: a step receives high reward if it reliably leads (via its descendants) to correct outcomes.

To be more specific, we choose $G$ adaptively to support robust importance score assignment at forks:
(i) $G=\max$ if the rewards of all sibling nodes are not identical, i.e., there exists a pair $k_{1},k_{2}\in\mathcal{C}(s_{j,t-1})$ such that $R(s_{k_{1},t})\neq R(s_{k_{2},t})$; and (ii) $G=\text{avg}$ otherwise. A toy example is illustrated in Appendix [A.4](#A1.SS4).
This formulation encourages the model to prioritize high-quality tool-call steps that yield higher outcome rewards while maintaining proper formatting. When all sibling steps under a fork achieve equivalent optimal performance, the averaging rule prefers the trajectory with higher probability and efficiency of leading to a correct final answer.

In addition, $R_{fm}$ is rescaled so that *final-answer correctness dominates*: formatting/execution feedback can help differentiate otherwise-correct behaviors and reduce tool errors, but it cannot outweigh the term for outcome correctness reward, i.e., $R_{fm}(s_{j,t})<\gamma^{T_{k}-t}R_{out}\!\left(q,\tau_{k}\right)$ for the step $s_{j,t}$.
Full definitions of $R_{fm}$ are in [Appendix˜A](#A1).

##### Step 3: Policy Optimization.

In the final stage, we compute token-level advantages to guide policy optimization.
We compute advantages at two granularities: (i) a trajectory-relative advantage $A_{\text{trj}}(\tau_{j})$, a coarse-grained signal that scores an entire trajectory among the $n$ candidates using only the outcome reward; and (ii) a fork-relative advantage $A_{\text{fork}}(s_{j,t})$, a fine-grained signal that compares a step against its sibling tool-call candidates at the same fork in the rollout tree.
Mathematically, denote $\textsf{norm}(\cdot,\cdot)$ as a z-score normalization function applied to a value with respect to a set of values, and these two advantages are formulated as

$$ $\displaystyle A_{\text{trj}}(\tau_{j})$ $\displaystyle=\textsf{norm}\big(R_{out}(q,\tau_{j}),\{R_{out}(q,\tau_{k})\}_{k\in[n]}\big),$ $\displaystyle A_{\text{fork}}(s_{j,t})$ $\displaystyle=\textsf{norm}\big(R(s_{j,t}),\{R(s_{k,t})\}_{k\in\mathcal{C}(s_{j,t-1})}\big).$ $$

For all tokens within a step $s_{j,t}$, the advantage is thereby defined as

$$ $\displaystyle A(s_{j,t,o})\overset{\triangle}{=}\frac{\omega_{1}}{|m(s_{j,t})|}\sum_{k\in m(s_{j,t})}A_{\text{trj}}(\tau_{k})+\omega_{2}A_{\text{fork}}(s_{j,t})$ (3) $$

where $\omega_{1}$ and $\omega_{2}$ are weighting coefficients balancing trajectory-level and fork-level influences. This formulation prevents a shared step $s_{j,t}$ that has various advantages across different trajectories. The trajectory-relative advantage provides a coarse-grained measure of the overall effectiveness of a tool-call trajectory, offering advantage estimation for every generated token. In contrast, the fork-relative advantage offers a fine-grained signal for distinguishing the best choice at a fork with several competing candidates. We optimize the policy model $\pi_{\theta}$ in Problem equation [1](#S3.E1) by applying the formulated advantage (i.e., [Equation˜3](#S3.E3)) so that it gradually learns to generate a meaningful tool-call step based on the input context (including a user query and historical tool responses) through trial and error.

Discussion: Setting $\omega_{1}$ and $\omega_{2}$.  The two terms in [Equation˜3](#S3.E3) correspond to different empirical normalizations (trajectory averaging vs. fork averaging). We therefore rescale the fork term to match the per-token objective’s averaging. Let $n_{\text{forks}}(q)$ be the number of fork nodes (steps with $|\mathcal{C}(s)|>1$) in the rollout tree for query $q$.

###### Theorem 3.2 .

By setting $\omega_{1}=1$ and

$$ $\displaystyle\omega_{2}=\frac{n|\tau_{j}|}{|m(s_{j,t})||s_{j,t}||\mathcal{C}(s_{j,t-1})|n_{\text{forks}}(q)},$ $$

we have the $J(\theta)=J_{GRPO_trj}(\theta)+J_{GRPO_fork}(\theta)$.

In summary, PORTool replaces independent rollouts with a rewarded rollout tree and uses Equations equation [2](#S3.E2) and equation [3](#S3.E3) to construct importance-aware advantages, enabling fine-grained credit assignment while remaining trajectory-supervised to address credit-assignment ambiguity.

###### Theorem 3.2 .

## 4 Experiments

### 4.1 Setup

##### Dataset.

We train and evaluate on an in-the-wild dataset of 3,607 real user queries collected from interactions with a deployed virtual assistant.(^1^11We only use anonymized text queries and remove any user-identifying information.)
The queries span eight common assistant domains: *Weather, Sports, Geo, Knowledge, Clock, News, Flight,* and *Stock*.
Crucially, the dataset contains both (i) time-/location-invariant queries whose answers should remain stable (e.g., general factual questions), and (ii) time-/location-dependent queries whose correct answers evolve with *current time and/or user location* (e.g., "today", "right now", "near me", "latest").
We split the dataset into 3,072 training queries and 535 evaluation queries.
As described by kim2026beyond, real-time tool use would be hindered by execution complexity, including feature limitations and partially relevant information.

##### Tool environment.

The tool-use agent interacts with an executable environment consisting of 21 function-style tools (including the terminal tool response_gen).
The tools correspond to production-style assistant capabilities (e.g., weather, news, maps/geo, flights, sports, and finance) as well as utility operators for date/time manipulation, conversions, math, and list filtering/sorting.
Each tool enforces a rigid JSON schema and exposes explicit error modes (e.g., malformed arguments, invalid formats, or tool failures).
At each step, the agent emits a short reasoning block (<think>) and a structured tool-call block (<tool_call>) that contains a JSON array of one or more tool invocations; tool outputs are appended to the context to condition subsequent steps.
An episode terminates when response_gen is invoked or when a maximum interaction horizon is reached.

##### Models and training protocol.

We instantiate the tool-use policy with two backbones: *Qwen-2.5-7B-Instruct* bai2023qwen and *Qwen-3-1.7B* yang2025qwen3.
We warm-start the agent with supervised fine-tuning and then apply agentic RL with PORTool and baseline algorithms.
During RL, each query samples $n=8$ tool-call trajectories, and we cap interaction at 6 tool-call steps.
Both models are trained for 15 epochs, and the details of settings are described in Appendix [C](#A3).

##### Baselines.

We compare PORTool with a diverse set of agentic-RL baselines—GRPO shao2024deepseekmath, DAPO yu2025dapo, ARPO dong2025agentic, AgentFlow li2025flow, SimpleTIR xue2025simpletir, and ToRL li2025torl—which cover different rollout-generation recipes, reward-design choices, and policy-optimization strategies for tool-use agents.
In addition, we construct two variants whose trajectory-level feedback is further augmented by formatting/execution reward, i.e., GRPO${}_{\text{fm}}$ and ARPO${}_{\text{fm}}$, which are expected to outperform the base methods GRPO and ARPO, respectively.

##### Evaluation Metrics and Evaluation Benchmark.

We evaluate each method along four axes:
(i) final-answer accuracy, computed over queries by treating a response as correct if it is judged correct by the evaluation agent(^2^22The evaluation agent is empowered by GPT-4o, which could match human adjudication with an accuracy of 94.37% under a dataset of 700 query-answer pairs with human labels), plus cases that are initially marked as unable_to_answer but later verified as correct by human adjudication;
(ii) average tool-call steps, i.e., the mean number of tool-invocation steps taken before termination (capped at 6);
(iii) unanswerable rate, defined as the fraction of episodes that fail to invoke response_gen within 6 tool-call steps; and
(iv) average formatting reward, i.e., the mean step-wise formatting/execution score averaged over steps and then over queries.
To reduce evaluator stochasticity, we query the judge five times per trajectory and take a majority vote.
To assess cross-benchmark generalization of PORTool and the baselines, we additionally report results on two public benchmarks:
ToolBench qin2023toolllm (with RapidAPI calls supported via the MirrorAPI model from StableToolBench guo2024stabletoolbench) and TravelPlanner xie2024travelplanner.
We follow each benchmark’s official protocol and report the required metrics.

### 4.2 Comparison with Other Baselines

**Table 1: Performance comparisons among different RL training methods on the evaluation dataset**
| Method | Qwen-2.5-7B-Instruct |  | Qwen-3-1.7B |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Accuracy (%) | # Tool-call<br>Steps | Unanswerable<br>Rate (%) | Formatting<br>Reward |  | Accuracy (%) | # Tool-call<br>Steps | Unanswerable<br>Rate (%) | Formatting<br>Reward |  |
| Prompting | 24.36 $\pm$ 0.75 | 4.76 | 58.50 | 0.466 |  | 12.06 $\pm$ 1.03 | 5.50 | 83.92 | 0.322 |
| GRPO | 46.09 $\pm$ 1.22 | 3.31 | 13.27 | 0.808 |  | 39.08 $\pm$ 0.64 | 2.96 | 10.65 | 0.834 |
| GRPO${}_{\text{fm}}$ | 47.58 $\pm$ 1.43 | 3.18 | 11.52 | 0.826 |  | 42.76 $\pm$ 1.78 | 2.79 | 9.91 | 0.857 |
| DAPO | 43.51 $\pm$ 1.06 | 3.37 | 14.58 | 0.790 |  | 39.47 $\pm$ 1.20 | 3.08 | 11.96 | 0.793 |
| ARPO | 48.18 $\pm$ 0.62 | 3.19 | 12.34 | 0.819 |  | 39.27 $\pm$ 1.14 | 3.07 | 11.96 | 0.784 |
| ARPO${}_{\text{fm}}$ | 44.97 $\pm$ 0.97 | 3.16 | 11.56 | 0.827 |  | 34.56 $\pm$ 1.05 | 3.21 | 11.03 | 0.808 |
| AgentFlow | 48.23 $\pm$ 1.06 | 3.30 | 11.21 | 0.816 |  | 37.20 $\pm$ 1.05 | 3.21 | 13.27 | 0.767 |
| SimpleTIR | 47.62 $\pm$ 1.16 | 3.12 | 10.47 | 0.832 |  | 41.76 $\pm$ 1.44 | 2.82 | 11.03 | 0.884 |
| ToRL | 45.52 $\pm$ 1.14 | 3.20 | 12.33 | 0.814 |  | 41.73 $\pm$ 1.18 | 2.94 | 11.40 | 0.810 |
| PORTool | 51.98 $\pm$ 1.09 | 3.07 | 7.10 | 0.851 |  | 46.60 $\pm$ 1.22 | 2.64 | 7.29 | 0.877 |
|  |  |  |  |  |  |  |  |  |  |

Results with Qwen-2.5-7B-Instruct.
PORTool achieves the strongest overall performance across accuracy, completion, and efficiency ([Table˜1](#S4.T1)). Specifically, PORTool outperforms the second-best RL baseline by a clear margin in accuracy while also using fewer tool-call steps, showing that it improves decision quality rather than trading correctness for longer trajectories.

We attribute this improvement to PORTool ’s importance-aware credit assignment. Most trajectory-supervised baselines (e.g., GRPO, DAPO) broadcast outcome supervision uniformly across steps, which obscures which tool-use decision at a branching point caused success or failure. Prefix-sharing methods such as ARPO and AgentFlow improve sampling efficiency but still rely largely on trajectory-level updates. In contrast, PORTool introduces fork-relative advantages that directly compare sibling actions under the same prefix, allowing the policy to reinforce the locally better tool-use decision without penalizing shared prefix steps. This resolves mis-credit at forks and reduces redundant exploration. Augmenting trajectory rewards with formatting feedback (e.g., GRPO${}_{\text{fm}}$) improves executability, but lacks this localized comparison, which explains why PORTool achieves higher correctness with fewer tool calls.

**Table 2: Performance on two out-of-distribution tasks with Qwen-2.5-7B-Instruct.**
|  | ToolBench Pass Rate (%) | TravelPlanner (%) |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | I1-Ins. | I1-Tool | I1-Cat. | I2-Ins. | I2-Cat. | I3-Ins. | Avg. | Delivery | Pass Avg. |
| GRPO${}_{\text{fm}}$ | 55.1 | 50.7 | 57.2 | 38.1 | 46.7 | 48.4 | 49.4 | 90.6 | 16.4 |
| ARPO${}_{\text{fm}}$ | 58.4 | 49.6 | 56.0 | 47.9 | 50.3 | 43.4 | 50.9 | 92.2 | 16.7 |
| AgentFlow | 52.6 | 45.3 | 54.2 | 38.4 | 50.8 | 49.5 | 48.5 | 91.7 | 16.2 |
| SimpleTIR | 53.8 | 47.2 | 55.0 | 46.6 | 50.2 | 42.1 | 49.2 | 88.9 | 16.2 |
| ToRL | 52.7 | 49.1 | 54.5 | 41.7 | 48.5 | 49.0 | 49.3 | 86.7 | 14.8 |
| PORTool | 57.6 | 55.2 | 56.3 | 47.6 | 47.8 | 52.2 | 52.8 | 92.8 | 16.7 |

Results with Qwen-3-1.7B.
Agentic RL training markedly reduces tool-format failures (formatting rewards move from $0.322$ under prompting to $0.79$–$0.88$ across RL methods), and PORTool again delivers the best end performance on correctness and completion. PORTool achieves the highest accuracy and the lowest unanswerable rate, while also requiring the fewest tool-call steps. Compared to the strongest baseline by accuracy (GRPO${}_{\text{fm}}$), PORTool improves accuracy by $3.84\%$, reduces unanswerable rate by round $3\%$, and shortens trajectories. Although the best formatting reward is attained by SimpleTIR ($0.884$), PORTool remains very close ($0.877$) while substantially improving correctness, indicating that its gains are not merely from stricter formatting but from better tool-use decisions and more reliable recovery from tool feedback.

Cross-benchmark Generalization.
[Table˜2](#S4.T2) shows that PORTool generalizes well to ToolBench qin2023toolllm and TravelPlanner xie2024travelplanner, achieving the best or tied-best aggregate performance and improving over prompting by a wide margin. Compared with the strongest baseline on ToolBench, PORTool yields a consistent average gain, rather than excelling on only specific subsets.
This robustness follows from PORTool’s learning signal. It does not rely on benchmark-specific intermediate supervision or fixed tool routines. Instead, it uses outcome supervision and generic execution validity, transformed into prefix-local, sibling-normalized comparisons. The discounted outcome term further biases learning toward plans that reach correct termination with fewer steps, improving efficiency across tasks. Consequently, PORTool learns a transferable tool-use decision rule that remains effective across different tool inventories, task structures, and interaction dynamics.

### 4.3 Discussions

#### 4.3.1 Effect of the Decay Factor γ \gamma

$\gamma$ is a decay factor of step-wise importance score as defined in [Equation˜2](#S3.E2). [Figure˜3](#S4.F3) compares four decay settings and tracks how outcome reward, formatting reward, and tool-call steps evolve during training.
A clear pattern is that $\gamma=0.95$ offers the best overall balance among correctness, formatting robustness, and efficiency: it reaches the highest final outcome reward and formatting reward, while also converging to the smallest number of tool-call steps. When $\gamma$ is too small (e.g., $\gamma=0.0$), the discounted outcome term in [Equation˜2](#S3.E2) vanishes for non-terminal steps, so step-wise importance is dominated by the formatting/execution signal. As a result, the agent receives weak guidance for long-horizon correctness, which yields slower improvement and a lower final outcome reward.

At the other extreme, $\gamma=1.0$ propagates outcome reward equally across all preceding steps regardless of the remaining horizon, eliminating the length-sensitive preference and allowing unnecessarily long tool interactions. Consistent with [Figure˜3(c)](#S4.F3.sf3), this setting tends to converge to more tool-call steps than $\gamma=0.95$, even when the final outcome reward becomes competitive. Based on these observations, we adopt $\gamma=0.95$ in all main experiments.

#### 4.3.2 Effect of the Advantage Coefficients

[Figure˜4](#S4.F4) studies how different ways of combining trajectory-relative and fork-relative advantages affect optimization. We compare: (i) PORTool using the scaled coefficients implied by [Theorem˜3.2](#S3.Thmtheorem2), (ii) traj.-only with $\omega_{2}=0$, (iii) fork-only with $\omega_{1}=0$ (keeping the same scaling for $\omega_{2}$), and (iv) no scale with $\omega_{1}=\omega_{2}=1$.

The results show that both advantage components are necessary, and that proper scaling matters. Trajectory-only underperforms substantially: broadcasting a single trajectory-level advantage to all steps provides no mechanism to prefer the correct tool-use decision at a fork when multiple candidates share the same prefix. Fork-only performs much better than trajectory-only because it directly compares sibling actions under the same history, but it still falls short of PORTool since fork-relative signals are only available at forked steps (and are zero when no meaningful siblings exist), leaving large parts of the trajectory no informative credit. The unscaled combination (*no scale*) improves over trajectory-only but consistently underperforms PORTool, matching the intuition that mixing two differently-normalized advantages without accounting for their averaging schemes can distort credit assignment. Overall, the ordering in [Figure˜4](#S4.F4)
empirically validates the benefit of blending the two signals using the theoretically motivated scaling.

Figure: (a)
Refer to caption: 2510.26020v2/x3.png

Figure: (a)
Refer to caption: 2510.26020v2/x6.png

#### 4.3.3 Effect of Reward Function R ​ ( s j , t ) R(s_{j,t}) Design

[Figure˜5](#S4.F5) evaluates alternative designs of the aggregation operator $G(\cdot)$ used in [Equation˜2](#S3.E2) to compute step-wise importance from descendant outcomes. We compare PORTool’s adaptive aggregation (max when sibling children are discriminative; average when effectively tied) against three variants: avg (always average), max (always max), and mix2 (a mixed formulation that aggregates the discounted outcome term but adds the formatting/execution reward outside the aggregation).

Across both outcome and formatting rewards, PORTool achieves the best final performance as shown in [Figure˜5](#S4.F5). The always-average variant performs worst: averaging can dilute rare-but-critical successful branches at a fork, weakening the relative signal needed to learn decisive tool-use choices. The always-max variant is stronger than always-average, but it can over-emphasize a single high-reward descendant (including lucky rollouts), which increases variance in step credit assignment and slightly degrades the final plateau compared to the adaptive rule. Finally, mix2 underperforms the adaptive design because separating formatting from the aggregation reduces the influence of execution quality when determining whether sibling branches should be treated as “tied” and averaged; empirically, this leads to lower formatting reward and slightly weaker outcome reward than PORTool. These comparisons support the adaptive $G(\cdot)$ design as a practical way to preserve strong learning signals at forks while avoiding brittle, high-variance updates.

## 5 Conclusion

In this work, we study trajectory-supervised agentic RL for enabling multi-tool-integrated reasoning under executable, dynamic tool feedback. We identify a core limitation of outcome-reward only optimization—*credit-assignment ambiguity*—where broadcasting a single trajectory-level reward to all intermediate steps provides no reliable signal about which tool decisions caused success, and can even *unlearn* tool-call steps that are necessary for correctness. To address this, we propose PORTool, which organizes rollouts into a *rewarded, prefix-sharing rollout tree* to create *prefix-matched within-context comparisons* at tool-call forks, and learns *prefix-consistent* step-wise importance from terminal correctness augmented with bounded execution/format feedback. Using a mixed advantage that combines coarse trajectory-relative and fine-grained fork-relative advantage, PORTool consistently improves final-answer accuracy while reducing tool-call steps and failure modes compared with state-of-the-art policy-optimization baselines.

## References

## Appendix A Additional Details of PORTool

### A.1 Tree Rollout

For each query $q$, PORTool generates exactly $n$ tool-call trajectories while constraining each expansion to a maximum branching factor $f$. The resulting rollouts naturally induce a tree structure: trajectories share prefixes (common histories) and diverge only at selected steps. Algorithm [1](#alg1) provides the official pseudocode of the rollout procedure used in this work.

Figure: Algorithm 1 Tree Rollout

### A.2 Rollout-Tree Notations

A completed rollout for query $q$ is a tool-call trajectory
$\tau_{j}=\{q,(s_{j,1},a_{j,1}),\ldots,(s_{j,T_{j}},a_{j,T_{j}})\}$.
At each step, $s_{j,t}$ is the tool-use agent’s generated content (reasoning traces plus one or more structured tool calls), and $a_{j,t}=U(s_{j,t})$ is the corresponding tool response (or error message).

##### Shared-step index set m ​ ( ⋅ ) m(\cdot) .

We represent the $n$ rollouts as a tree where each node corresponds to a *shared prefix step* (i.e., a step reached under the same interaction history). For any node/step $s_{j,t}$, define

$$ $m(s_{j,t})\triangleq\{k\in[n]:\text{trajectory }\tau_{k}\text{ passes through the same node as }s_{j,t}\}.$ $$

Intuitively, $m(s_{j,t})$ contains all trajectory indices that share the same prefix up to (and including) step $t$.

##### Child set C ​ ( ⋅ ) C(\cdot) .

For any step (node) $s_{j,t}$, define its child set $C(s_{j,t})$ as the set of trajectory indices corresponding to *distinct* $(t+1)$-th steps branching from $s_{j,t}$. By construction, for any $k_{1}\neq k_{2}\in C(s_{j,t})$, we have $s_{k_{1},t+1}\neq s_{k_{2},t+1}$. It is possible that two distinct trajectories $k_{1},k_{2}\in m(s_{j,t})$ generate the same next step (duplicate children), so $C(s_{j,t})\subseteq m(s_{j,t})$.

##### Fork set and fork count.

A node is a *fork* if it has more than one distinct child:

$$ $\mathcal{F}(q)\triangleq\{s_{j,t}:\ |C(s_{j,t})|>1,\ j\in[n],\ t\in[T_{j}]\},\qquad n_{\mathrm{forks}}(q)\triangleq|\mathcal{F}(q)|.$ $$

### A.3 Reward Components and Rescaled Formatting Reward

PORTool computes step-wise importance by combining (i) the evaluation agent’s trajectory outcome reward and (ii) an auxiliary formatting/execution reward.

##### Outcome reward R out R_{\mathrm{out}} .

After a rollout terminates, the evaluation agent assigns

$$ $R_{\mathrm{out}}(q,\tau_{j})\in\{+1,0,-1\},$ $$

corresponding to {true, unable_to_answer, false}.

##### Raw formatting score r fm ∈ [ 0 , 1 ] r_{\mathrm{fm}}\in[0,1] .

For each step $s_{j,t}$, we compute a raw formatting score using the following rubric:

- 1.
Reasoning block: if the output includes a <think> ... </think> block, add $+0.2$.
- 2.
Formatting checks (activated only if the reasoning block is present):
•
If the tool-call wrapper <tool_call> ... </tool_call> is included, add $+0.1$.
•
If the enclosed content can be parsed as valid JSON, add $+0.1$.
•
If every tool call includes the required fields "name" (string) and "arguments" (dictionary), add $+0.05$.
•
Tool invocation success: if all tool calls succeed, add $+0.55$; otherwise assign partial credit proportional to the fraction of successful tool calls.

By construction, $r_{\mathrm{fm}}(s_{j,t})\in[0,1]$.

##### Correctness-dominant rescaling.

To ensure correctness always dominates formatting, we rescale the raw formatting score to a bounded, centered reward:

$$ $R_{\mathrm{fm}}(s_{j,t})\triangleq\alpha\Bigl(r_{\mathrm{fm}}(s_{j,t})-\tfrac{1}{2}\Bigr),\qquad R_{\mathrm{fm}}(s_{j,t})\in\bigl[-\tfrac{\alpha}{2},\tfrac{\alpha}{2}\bigr].$ $$

We choose $\alpha>0$ sufficiently small so that, at any step, the discounted outcome term $\gamma^{T_{j}-t}R_{\mathrm{out}}(q,\tau_{j})$ dominates the largest possible formatting difference. A sufficient condition is $\alpha<2\min_{t\leq T_{\max}}\gamma^{T_{\max}-t}$.

### A.4 Step-wise Reward and Adaptive Aggregation G G

Given a step (node) $s_{j,t}$, we define its step-wise reward by aggregating descendant outcomes plus the formatting reward:

$$ $R(s_{j,t})\triangleq G\!\Bigl(\bigl\{\gamma^{T_{k}-t}R_{\mathrm{out}}(q,\tau_{k})+R_{\mathrm{fm}}(s_{j,t})\bigr\}_{k\in m(s_{j,t})}\Bigr),$ (4) $$

where $\gamma\in[0,1]$ is the decay factor and $G(\cdot)$ is chosen adaptively to stabilize credit assignment at forks.

##### Adaptive rule for G G .

Let $p$ be the parent of $s_{j,t}$ (i.e., $p=s_{j,t-1}$) and let $\mathrm{Ch}(p)$ denote the set of distinct child steps under $p$. Define the set of *provisional* values

$$ $\widetilde{R}(s)\triangleq\max_{k\in m(s)}\Bigl(\gamma^{T_{k}-t}R_{\mathrm{out}}(q,\tau_{k})+R_{\mathrm{fm}}(s)\Bigr),\qquad s\in\mathrm{Ch}(p).$ $$

If the children are discriminative (i.e., $\{\widetilde{R}(s):s\in\mathrm{Ch}(p)\}$ is not a singleton), we set $G=\max$ in equation [4](#A1.E4) to emphasize the best branch. Otherwise (children are effectively tied), we set $G=\mathrm{avg}$ so that the score reflects reliability rather than a single lucky rollout.

##### Toy example: when G = avg G=\mathrm{avg} (tied best-case children).

Recall that for a node/step $s$ we aggregate the set of descendant values
$v_{k}(s)\triangleq\gamma^{T_{k}-t}R_{\mathrm{out}}(q,\tau_{k})+R_{\mathrm{fm}}(s)$ over $k\in m(s)$,
and define $R(s)=G(\{v_{k}(s)\}_{k\in m(s)})$.
At a fork parent step $p$ with multiple children $s\in\mathrm{Ch}(p)$, we use the adaptive rule:
we first compute each child’s *best-case* provisional value
$R^{\max}(s)=\max_{k\in m(s)}v_{k}(s)$; if $\{R^{\max}(s)\}_{s\in\mathrm{Ch}(p)}$ is not a singleton,
we set $G=\max$; otherwise (children are best-case tied) we set $G=\mathrm{avg}$.

Setup.
Consider a fork with two candidate tool-call steps $s^{A}$ and $s^{B}$ under the same prefix history.
Assume $R_{\mathrm{fm}}(s^{A})=R_{\mathrm{fm}}(s^{B})=0$ and $\gamma=1$ for simplicity, so $v_{k}(s)=R_{\mathrm{out}}(q,\tau_{k})\in\{+1,-1\}$.
Suppose we sample four continuations under each child:

| Child step | Outcomes of its descendant rollouts | $R^{\max}(s)$ |
| --- | --- | --- |
| $s^{A}$ | $\{+1,-1,-1,-1\}$ | $+1$ |
| $s^{B}$ | $\{+1,+1,+1,-1\}$ | $+1$ |

Why $\max$ is insufficient here.
Both children have the same best-case value ($R^{\max}(s^{A})=R^{\max}(s^{B})=+1$),
meaning that *each child has at least one successful descendant*.
If we used $G=\max$ unconditionally, then $R(s^{A})=R(s^{B})=+1$ and the fork-level comparison
cannot prefer the more reliable tool decision.

Why the adaptive rule chooses $\mathrm{avg}$.
Because the best-case values are tied, we set $G=\mathrm{avg}$ and obtain

$$ $R(s^{A})=\mathrm{avg}(\{+1,-1,-1,-1\})=-0.5,\qquad R(s^{B})=\mathrm{avg}(\{+1,+1,+1,-1\})=+0.5.$ $$

Thus, although both children can sometimes lead to success, averaging assigns higher importance to $s^{B}$
because it succeeds more consistently. In this way, the $\mathrm{avg}$ case measures *reliability* (and, when $\gamma<1$, also *average efficiency* via discounting), rather than being dominated by a single lucky successful rollout.

Contrast: when the rule uses $\max$.
If instead $s^{A}$ *never* leads to a correct completion (e.g., $\{-1,-1,-1,-1\}$), then
$R^{\max}(s^{A})=-1$ and $R^{\max}(s^{B})=+1$ are discriminative; the adaptive rule sets $G=\max$
to emphasize that $s^{B}$ is the only branch that can reach a correct outcome.

### A.5 Fork-Relative Advantages and Derivation of Theorem 3.2

This section provides additional details for the fork-relative advantage and the coefficient scaling in Theorem [3.2](#S3.Thmtheorem2).

##### Trajectory-relative and fork-relative advantages.

Let $\mathrm{norm}(x;\mathcal{S})$ denote z-score normalization of $x$ with respect to a set $\mathcal{S}$. We define

$$ $A_{\mathrm{trj}}(\tau_{j})\triangleq\mathrm{norm}\!\Bigl(R_{\mathrm{out}}(q,\tau_{j});\ \{R_{\mathrm{out}}(q,\tau_{k})\}_{k=1}^{n}\Bigr),$ $$

and for a step $s_{j,t}$ that is a child of a forked parent step,

$$ $A_{\mathrm{fork}}(s_{j,t})\triangleq\mathrm{norm}\!\Bigl(R(s_{j,t});\ \{R(s_{k,t})\}_{k\in C(s_{j,t-1})}\Bigr),$ $$

and set $A_{\mathrm{fork}}(s_{j,t})=0$ if $|C(s_{j,t-1})|\leq 1$.

##### Token-level mixed advantage.

For any token $s_{j,t,o}$ within step $s_{j,t}$, PORTool uses

$$ $A(s_{j,t,o})\triangleq\frac{\omega_{1}}{|m(s_{j,t})|}\sum_{k\in m(s_{j,t})}A_{\mathrm{trj}}(\tau_{k})\;+\;\omega_{2}\,A_{\mathrm{fork}}(s_{j,t}).$ $$

##### Fork set and notation.

Let $\mathcal{C}(s)$ be the index set of children of step $s$, and $m(s)$ map a step to the index set of its descendant steps whose tokens we average when we expand beyond $s$ (both return sets of indices). Define the set of forked steps

$$ $\mathcal{F}\overset{\triangle}{=}\{\,s_{j,t}\;:\;|\mathcal{C}(s_{j,t})|>1,\ j\in[n],\ t\in[T_{j}]\,\},$ $$

and write $n_{\mathrm{forks}}(q)\overset{\triangle}{=}|\mathcal{F}|$ for query $q$.

##### Token-level GRPO losses.

Recall the objective in equation [1](#S3.E1):

$$ $\displaystyle J(\theta)$ $\displaystyle=\mathbb{E}\left[\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tau_{j}|}\sum_{t=1}^{T_{j}}\sum_{o=1}^{|s_{j,t}|}f_{\theta}(s_{j,t,o})\right],$ $$

with the standard PPO/GRPO per-token term

$$ $f_{\theta}(s)\overset{\triangle}{=}\min\!\Big(\rho_{\theta}(s)A(s),\,\textsf{clip}_{1-\varepsilon}^{1+\varepsilon}(\rho_{\theta}(s))A(s)\Big).$ $$

We instantiate an *additive* token loss (a standard multi-objective construction) as

$$ $f_{\theta}(s)\;=\;f_{\theta}^{(\mathrm{trj})}(s)\;+\;f_{\theta}^{(\mathrm{fork})}(s),$ $$

where

$$ $\displaystyle f_{\theta}^{(\mathrm{trj})}(s)\overset{\triangle}{=}\min\!\Big($ $\displaystyle\rho_{\theta}(s)A_{\mathrm{trj}}(s),\textsf{clip}_{1-\varepsilon}^{1+\varepsilon}(\rho_{\theta}(s))A_{\mathrm{trj}}(s)\Big),$ $$

and, for a *rescaled* fork advantage $\overline{A}_{\mathrm{fork}}$ to be determined,

$$ $\displaystyle f_{\theta}^{(\mathrm{fork})}(s)\overset{\triangle}{=}\min\!\Big($ $\displaystyle\rho_{\theta}(s)\overline{A}_{\mathrm{fork}}(s),\textsf{clip}_{1-\varepsilon}^{1+\varepsilon}(\rho_{\theta}(s))\overline{A}_{\mathrm{fork}}(s)\Big).$ $$

By construction,

$$ $J(\theta)=J_{\mathrm{GRPO_trj}}(\theta)+J_{\mathrm{GRPO_fork}}(\theta),$ $$

with $J_{\mathrm{GRPO_trj}}$ and $J_{\mathrm{GRPO_fork}}$ the expectations of the empirical sums formed with $f_{\theta}^{(\mathrm{trj})}$ and $f_{\theta}^{(\mathrm{fork})}$ respectively. We set $\omega_{1}=1$ in $A_{\mathrm{trj}}$.

##### Fork-wise empirical objective.

Independently, define the fork-wise objective by averaging over forks, then over children and their tokens:

$$ $J_{\mathrm{GRPO_fork}}(\theta)\overset{\triangle}{=}\mathbb{E}\underbrace{\left[\frac{1}{|\mathcal{F}|}\sum_{s_{j,t}\in\mathcal{F}}\frac{1}{|\mathcal{C}(s_{j,t})|}\sum_{k\in\mathcal{C}(s_{j,t})}\frac{1}{|s_{k,t+1}|}\sum_{o=1}^{|s_{k,t+1}|}f_{\theta}^{(\mathrm{fork})}(s_{k,t+1,o})\right]}_{\mathcal{L}^{(\mathrm{fork})}_{\mathrm{emp}}(\theta;\{\tau_{j}\})},$ $$

##### Reindexing lemma (disjoint union).

For any fork $s_{j,t}\in\mathcal{F}$,

$$ $\displaystyle m(s_{j,t})=\bigcup_{k\in\mathcal{C}(s_{j,t})}m(s_{k,t+1}),\quad m(s_{k,t+1})\cap m(s_{k^{\prime},t+1})=\emptyset\ \ \text{for }k\neq k^{\prime}.$ $$

Consequently,

$$ $\displaystyle\sum_{k\in\mathcal{C}(s_{j,t})}\frac{1}{|s_{k,t+1}|}\sum_{o=1}^{|s_{k,t+1}|}f_{\theta}^{(\mathrm{fork})}(s_{k,t+1,o})=\sum_{k\in m(s_{j,t})}\ \sum_{o=1}^{|s_{k,t+1}|}\frac{f_{\theta}^{(\mathrm{fork})}(s_{k,t+1,o})}{|m(s_{k,t+1})|\,|s_{k,t+1}|},$ $$

##### Matching normalizers and the choice of ω 2 \omega_{2} .

Insert the lemma into $\mathcal{L}^{(\mathrm{fork})}_{\mathrm{emp}}$:

$$ $\displaystyle\mathcal{L}^{(\mathrm{fork})}_{\mathrm{emp}}(\theta;\{\tau_{j}\})=\frac{1}{|\mathcal{F}|}\sum_{s_{j,t}\in\mathcal{F}}\ \sum_{k\in m(s_{j,t})}\ \sum_{o=1}^{|s_{k,t+1}|}\frac{f_{\theta}^{(\mathrm{fork})}(s_{k,t+1,o})}{|\mathcal{C}(s_{j,t})|\,|m(s_{k,t+1})|\,|s_{k,t+1}|}.$ $$

To embed this into the per-trajectory/token averaging of equation [1](#S3.E1), observe that a token $s_{u,o}$ appearing as a child of a forked *parent* step $s_{j,t-1}$ receives weight

$$ $\underbrace{\frac{1}{|\mathcal{F}|}}_{\text{fork avg}}\cdot\underbrace{\frac{1}{|\mathcal{C}(s_{j,t-1})|}}_{\text{children avg}}\cdot\underbrace{\frac{1}{|m(s_{j,t})|}}_{\text{descendants split}}\cdot\underbrace{\frac{1}{|s_{j,t}|}}_{\text{token avg}}.$ $$

In contrast, in equation [1](#S3.E1) the empirical averaging for any token of trajectory $j$ is
$\frac{1}{n}\cdot\frac{1}{|\tau_{j}|}.$
Therefore, to write the fork contribution *in the same empirical form as* equation [1](#S3.E1), we absorb the ratio of these weights into the advantage via

$$ $\displaystyle\overline{A}_{\mathrm{fork}}(s_{j,t,o})\overset{\triangle}{=}\omega_{2}\;A_{\mathrm{fork}}(s_{j,t,o}),$ $$

where

$$ $\displaystyle\omega_{2}\;$ $\displaystyle=\;\frac{n\,|\tau_{j}|}{|m(s_{j,t})|\,|s_{j,t}|\,|\mathcal{C}(s_{j,t-1})|\,n_{\mathrm{forks}}(q)}.$ $$

(When $s_{j,t}$ is not a child of a fork, take $\overline{A}_{\mathrm{fork}}(s_{j,t,o})=0$.) With this choice,

$$ $\mathcal{L}^{(\mathrm{fork})}_{\mathrm{emp}}(\theta;\{\tau_{j}\})=\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tau_{j}|}\sum_{t=1}^{T_{j}}\sum_{o=1}^{|s_{j,t}|}f_{\theta}^{(\mathrm{fork})}(s_{j,t,o}).$ $$

Combining with the trajectory term (where we set $\omega_{1}=1$),

$$ $\displaystyle\mathcal{L}_{\mathrm{emp}}(\theta;\{\tau_{j}\})=\frac{1}{n}\sum_{j=1}^{n}\frac{1}{|\tau_{j}|}\sum_{t,o}\Big(f_{\theta}^{(\mathrm{trj})}(s_{j,t,o})+f_{\theta}^{(\mathrm{fork})}(s_{j,t,o})\Big),$ $$

and taking expectations yields

$$ $J(\theta)=J_{\mathrm{GRPO_trj}}(\theta)+J_{\mathrm{GRPO_fork}}(\theta).$ $$

##### Remarks.

(i) The additivity $f_{\theta}=f_{\theta}^{(\mathrm{trj})}+f_{\theta}^{(\mathrm{fork})}$ is the usual way to combine multiple GRPO/PPO-style objectives; we do *not* replace $A$ by a single sum inside one $\min(\cdot)$ (which would not in general be additive).
(ii) The scaling $\omega_{2}$ is the unique choice (up to a constant that cancels if applied to both numerator and denominator) that aligns the fork averaging with the per-trajectory/token averaging in equation [1](#S3.E1).

## Appendix B Proof of Theorem 3.1

##### Assumptions.

We analyze one query $q$ and one expected GRPO-style update around $\theta_{\text{old}}$.

- (A1)
Binary terminal outcome.
Each trajectory $\tau$ receives an outcome reward
$r(\tau)\in\{+1,-1\}$, where $+1$ means correct and $-1$ means incorrect.
- (A2)
Necessary step.
Let $E$ denote the event that a trajectory contains $s^{*}$.
Necessity means
$\Pr_{\theta_{\text{old}}}(\text{correct}\mid\neg E)=0.$
Thus every correct trajectory must contain $s^{*}$.
- (A3)
Z-score trajectory advantage.
GRPO assigns each trajectory a scalar advantage $A(\tau)$ by z-score normalizing $r(\tau)$.
For analysis, we use the population form
$A(\tau)=\frac{r(\tau)-\mu}{\sigma},\qquad\mu=\mathbb{E}[r],\qquad\sigma=\sqrt{\mathbb{E}[(r-\mu)^{2}]}.$
We assume $\sigma>0$, i.e., both correct and incorrect trajectories exist.
- (A4)
Trajectory-level credit assignment with per-token averaging.
The scalar advantage $A(\tau)$ is broadcast to all tokens in $\tau$, and the token-level loss is averaged over trajectory length, giving a weight $1/|\tau|$.
- (A5)
Local step-probability parameterization.
We analyze the local probability of taking $s^{*}$ at its generation context. Let this probability be
$p_{s^{*}}(\theta)$.
Equivalently, one may view $s^{*}$ as controlled by a local softmax logit $z$, so that
$\frac{\partial}{\partial z}\log\pi_{\theta}(a)=\mathbf{1}\{a=s^{*}\}-p_{s^{*}}(\theta).$
- (A6)
Small-step update.
The update from $\theta_{\text{old}}$ to $\theta_{\text{new}}$ is sufficiently small, so first-order Taylor expansion determines the sign of the change in $\log p_{s^{*}}(\theta)$.

##### Why the additional assumption is needed.

The original proof only used the contribution from trajectories containing $s^{*}$.
However, in a softmax policy, trajectories not containing $s^{*}$ also affect $p_{s^{*}}$: penalizing competing steps tends to increase the probability of $s^{*}$.
Assumption (A5) makes this interaction explicit and allows us to compute the true local update direction.

##### Notation.

Let

$$ $p\triangleq p_{s^{*}}(\theta_{\text{old}})=\Pr(E),\qquad q\triangleq p^{(c)}_{s^{*}}(\theta_{\text{old}})=\Pr(\text{correct}\mid E).$ $$

Since $s^{*}$ is necessary for correctness,

$$ $\pi\triangleq\Pr(\text{correct})=\Pr(E)\Pr(\text{correct}\mid E)=pq.$ $$

Define

$$ $L_{c}\triangleq\mathbb{E}\!\left[\frac{1}{|\tau|}\,\middle|\,E,\text{correct}\right],\qquad L_{w}\triangleq\mathbb{E}\!\left[\frac{1}{|\tau|}\,\middle|\,E,\text{incorrect}\right],$ $$

and

$$ $L_{\neg}\triangleq\mathbb{E}\!\left[\frac{1}{|\tau|}\,\middle|\,\neg E\right].$ $$

By necessity, all trajectories in $\neg E$ are incorrect.

##### Step 1: z-score values.

Since $r(\tau)\in\{+1,-1\}$ and $\Pr(\text{correct})=\pi$, we have

$$ $\mu=2\pi-1,\qquad\sigma=2\sqrt{\pi(1-\pi)}.$ $$

Therefore

$$ $A^{+}\triangleq A(\tau)\mid\text{correct}=\sqrt{\frac{1-\pi}{\pi}},$ $$

and

$$ $A^{-}\triangleq A(\tau)\mid\text{incorrect}=-\sqrt{\frac{\pi}{1-\pi}}.$ $$

##### Step 2: local GRPO update on the probability of s ∗ s^{*} .

Let $z$ be the local logit controlling $s^{*}$.
Under a GRPO-style update with per-token averaging, the local gradient with respect to $z$ is proportional to

$$ $G_{z}=\mathbb{E}\!\left[\frac{A(\tau)}{|\tau|}\left(\mathbf{1}\{E\}-p\right)\right].$ $$

This is the key correction relative to the earlier proof. The term
$\mathbf{1}\{E\}-p$ accounts for both trajectories containing $s^{*}$ and trajectories not containing $s^{*}$.

Now define

$$ $B\triangleq\mathbb{E}\!\left[\frac{A(\tau)}{|\tau|}\,\middle|\,E\right]=qA^{+}L_{c}+(1-q)A^{-}L_{w},$ $$

and

$$ $C\triangleq\mathbb{E}\!\left[\frac{A(\tau)}{|\tau|}\,\middle|\,\neg E\right]=A^{-}L_{\neg},$ $$

because $\neg E$ implies incorrectness.

Then

$$ $\mathbb{E}\!\left[\mathbf{1}\{E\}\frac{A(\tau)}{|\tau|}\right]=pB,$ $$

and

$$ $\mathbb{E}\!\left[\frac{A(\tau)}{|\tau|}\right]=pB+(1-p)C.$ $$

Therefore

$$ $G_{z}=pB-p\bigl(pB+(1-p)C\bigr)=p(1-p)(B-C).$ $$

##### Step 3: expected change in log ⁡ p s ∗ \log p_{s^{*}} .

Since

$$ $\frac{\partial}{\partial z}\log p_{s^{*}}(\theta_{\text{old}})=1-p,$ $$

a small gradient step gives

$$ $\mathbb{E}[\Delta\log p_{s^{*}}]=\eta(1-p)G_{z}+o(\eta).$ $$

Substituting the expression for $G_{z}$,

$$ $\mathbb{E}[\Delta\log p_{s^{*}}]=\eta p(1-p)^{2}(B-C)+o(\eta).$ $$

Equivalently,

$$ $\mathbb{E}\!\left[\log p_{s^{*}}(\theta_{\text{old}})-\log p_{s^{*}}(\theta_{\text{new}})\right]=-\eta p(1-p)^{2}(B-C)+o(\eta).$ $$

Thus the expected log-probability of $s^{*}$ decreases iff

$$ $B-C<0.$ $$

##### Step 4: simplify the condition B − C < 0 B-C<0 .

We have

$$ $B-C=qA^{+}L_{c}+(1-q)A^{-}L_{w}-A^{-}L_{\neg}.$ $$

Therefore $B-C<0$ iff

$$ $qA^{+}L_{c}<(-A^{-})\bigl((1-q)L_{w}-L_{\neg}\bigr).$ $$

Using

$$ $A^{+}=\sqrt{\frac{1-\pi}{\pi}},\qquad-A^{-}=\sqrt{\frac{\pi}{1-\pi}},$ $$

this becomes

$$ $q\sqrt{\frac{1-\pi}{\pi}}L_{c}<\sqrt{\frac{\pi}{1-\pi}}\bigl((1-q)L_{w}-L_{\neg}\bigr).$ $$

Multiplying both sides by $\sqrt{\pi(1-\pi)}>0$ gives

$$ $q(1-\pi)L_{c}<\pi\bigl((1-q)L_{w}-L_{\neg}\bigr).$ $$

Substituting $\pi=pq$ and canceling $q>0$, we get

$$ $(1-pq)L_{c}<p\bigl((1-q)L_{w}-L_{\neg}\bigr).$ $$

Substituting back

$$ $p=p_{s^{*}}(\theta_{\text{old}}),\qquad q=p^{(c)}_{s^{*}}(\theta_{\text{old}})$ $$

gives the theorem condition:

$$ $\bigl(1-p_{s^{*}}(\theta_{\text{old}})p^{(c)}_{s^{*}}(\theta_{\text{old}})\bigr)L_{c}<p_{s^{*}}(\theta_{\text{old}})\left(\bigl(1-p^{(c)}_{s^{*}}(\theta_{\text{old}})\bigr)L_{w}-L_{\neg}\right).$ $$

The condition is more likely to hold when correct trajectories containing $s^{*}$ are long or rare, while incorrect trajectories containing $s^{*}$ are relatively short and receive stronger per-token weight than incorrect trajectories that omit $s^{*}$. This reflects the bias introduced by broadcasting trajectory-level rewards with per-token averaging.

##### Step 5: conclusion.

Under this condition, $B-C<0$, so

$$ $\mathbb{E}[\Delta\log p_{s^{*}}]<0$ $$

for sufficiently small $\eta$.
Hence

$$ $p_{s^{*}}(\theta_{\text{new}})<p_{s^{*}}(\theta_{\text{old}})$ $$

in the expected small-step regime.
This proves the theorem.
∎

## Appendix C Extended Experimental Details

### C.1 Data Construction and Splits

##### Source and anonymization.

The dataset is constructed from real user interactions with a production mobile assistant.
All queries are anonymized and de-identified prior to use.

##### Domains and temporal properties.

Queries span eight assistant domains: Weather, Sports, Geo/Maps, Knowledge, Clock/Time, News, Flight, and Stock.
We label each query as either time-invariant or time-sensitive.
Time-sensitive queries require executing tools with an explicit time (and often an implicit location context), while time-invariant queries admit stable answers. Here is the data distribution for our collected data:

**Table 3: Time/location dependency distribution across domains (3607 queries).**
|  | Weather | Sports | Geo | Knowledge | Clock | News | Flight | Stock | Total |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Time/Loc-dependent | 454 | 10 | 562 | 51 | 199 | 2 | 6 | 3 | 1287 |
| Time/Loc-invariant | 1 | 85 | 448 | 1349 | 428 | 0 | 6 | 3 | 2320 |
| Total | 455 | 95 | 1010 | 1400 | 627 | 2 | 12 | 6 | 3607 |

##### Splits.

We use 3072 queries for training and 535 queries for evaluation.
Unless otherwise stated, all reported evaluation metrics are computed on this held-out split.

##### Why train on our dataset instead of existing tool-use benchmarks.

Existing large-scale tool-use benchmarks are indispensable for *evaluation*, but are often not ideal as a *training* environment for trajectory-supervised agentic RL.
First, training requires generating thousands of rollouts, which in turn demands a large number of *live* tool executions; benchmarks built around web API marketplaces frequently face hard quota limits, making repeated interaction prohibitively costly and unreliable at scale.
Second, many benchmark pipelines rely on cached or simulated tool outputs and/or tool preselection, which can mask real execution failures and reduce exposure to the non-stationarity that arises in realistic deployments.
In contrast, our sandboxed environment exposes a compact set of *core assistant tools* (e.g., weather, maps/geo, news, finance/stocks, flights, sports, clock, and supporting utilities) with rigid schemas and explicit error modes, and supports *unlimited* executions during rollout generation.
This design enables training directly on real-time tool responses without preselecting a subset of tools for each query, which better matches the intended deployment setting.
Importantly, PORTool itself is agnostic to the number of tools; scaling to larger tool catalogs is therefore primarily an engineering extension of the environment and tool-routing layer, rather than a constraint of the learning algorithm.

### C.2 Executable Tool Environment and Interaction Format

##### Agent I/O contract.

The tool-use agent is instructed to solve tasks by (i) generating a brief reasoning segment in <think>... </think>, and (ii) emitting a <tool_call>... </tool_call> block that contains a JSON array of tool invocations of the form:

$$ $\{\texttt{"name": <tool_name>, "arguments": <dict>}\}.$ $$

Tool outputs (including explicit error messages) are appended to the running context, which is used in subsequent tool calls.

##### Termination.

The interaction ends when the agent invokes response_gen (the terminal tool for producing the final natural-language answer) or reaches the maximum step budget (6 tool-call steps in our evaluation protocol).

##### Reproducibility for time-sensitive queries.

For time-sensitive evaluation, we (i) record tool-execution timestamps at second-level precision and (ii) evaluate under a fixed reference context (e.g., a fixed location/timezone setting) to make re-runs deterministic at the tool layer.

### C.3 Automatic Outcome Judge and Calibration

##### Evaluator Agent.

We use GPT-4o as a fixed evaluator that assigns each completed trajectory one label in
$\{\texttt{true},\ \texttt{false},\ \texttt{unable_to_answer}\}$,
based on whether the final answer is supported by the executed tool outputs (including errors).

**Table 4: Training and rollout hyperparameter configuration.**
| Category | Hyperparameter |
| --- | --- |
| Data Configuration |  |
| Train Batch Size | 512 |
| Max Prompt Length (Total) | 30720 |
| Max Response Length (Per Response) | 1024 |
| Optimization |  |
| Learning Rate | 1e-6 |
| PPO Mini Batch Size | 128 |
| KL Loss Used | False |
| Rollout Configuration |  |
| Rollout Name | vllm |
| GPU Memory Utilization | 0.4 |
| Number of Rollouts | 8 |
| Training & Logging |  |
| Total Epochs | 15 |

##### Calibration.

To validate evaluation reliability, we build a calibration set of $\sim$700 query–answer pairs by sampling queries and generating tool-call trajectories with multiple strong LLMs (e.g., Claude and Gemini families), then collecting human correctness labels using the tool outputs as evidence.
On this set, the GPT-4o judge achieves 94.37% agreement with human annotations.

##### Variance reduction.

Each evaluated trajectory is judged five times independently; we report correctness by majority vote and compute uncertainty estimates from judge variance.

### C.4 Training and Implementation Details

##### Framework and decoding.

We implement training with a standard RLHF/agentic-RL codebase and execute rollouts with an efficient LLM serving engine.
During training, we sample rollouts with stochastic decoding; during evaluation, we use a more conservative decoding configuration.

##### Rollouts and horizons.

We generate $n{=}8$ rollouts per training query.
Each episode is capped at 6 tool-call steps for both training rollouts and evaluation.

##### Optimization details.

We first run supervised fine-tuning for five epochs, then apply RL for 15 epochs.
Unless otherwise specified, we use LoRA adaptation with rank $16$ and $\alpha{=}8$.

##### Key hyperparameters.

We use a training batch size of 512, learning rate $10^{-6}$, and PPO-style minibatch size 128.
We cap the maximum total prompt length and the per-step response length to fit within GPU memory constraints.
(If desired, the values in Table 2 of the draft can be retained verbatim here.)

### C.5 Additional Benchmarks

##### ToolBench.

We additionally evaluate on ToolBench, using StableToolBench to simulate tool responses for APIs originally hosted on third-party platforms.
We follow the standard ToolBench protocol for tool-call success and task completion.

##### TravelPlanner.

We also evaluate on TravelPlanner to test multi-step planning and execution in travel-related scenarios, following the benchmark’s default splits and evaluation settings.

### C.6 Implementation

Our implementation is built upon the VeRL framework sheng2024hybridflow, with rollouts executed using VLLM kwon2023efficient. All experiments are conducted on a single node equipped with eight NVIDIA H100 GPUs. The training batch size is set to 512, and in each update round, 128 samples are used to optimize the policy model. During training, text generation adopts a temperature of 1.0, top-p of 1.0, and top-k of -1, while validation employs the suggested configuration (Qwen-2.5-7B-Instruct: temperature is 0.7, top-p is 0.8, and top-k is -1; Qwen-3-1.7B: temperature is 0.6, top-p is 0.95, and top-k is 20). Each reasoning step is capped at 2,048 tokens, and eight rollouts are generated per query. For time-sensitive queries, the reference location is fixed to Cupertino, California (USA), and execution timestamps are recorded with second-level precision to ensure reproducibility. Prior to reinforcement learning, supervised fine-tuning (SFT) is performed for five epochs. All baselines are trained for 15 epochs (equivalent to 90 steps in total), and we report the average performance of the best three checkpoints during training. Unless otherwise specified, LoRA fine-tuning is adopted with rank = 16 and $\alpha$ = 8. A summary of detailed training and rollout configurations is provided in Table [4](#A3.T4).

## Appendix D Tool Schemas and Prompt Cards

## Appendix E Example I: which team has better performance in the last three seasons: the steelers, ravens, or eagles

**Table 5: Generated results across different methods with Qwen-2.5-7B**
| Method | Generated Result |
| --- | --- |
| GRPO | I encountered an issue retrieving the specific performance data for the Steelers, Ravens, and Eagles for the last three seasons. Please provide more specific details or context for the sport and league you are interested in. |
| ARPO | There seems to be an issue with retrieving the football standings for the Steelers, Ravens, and Eagles. Please try again later or use a different source for this information. |
| DAPO | The performance data for the Steelers, Ravens, and Eagles in the last three seasons is not available in the expected format. Based on the information provided, we cannot determine which team has the better performance. |
| PORTool | Based on the data extracted, the Raptors (Ravens) had a positive performance in the last three seasons. They won 12 out of their final 15 games and finished the season with a record of 12-5. On the other hand, the Steelers had a record of 4-2 after snapping their losing streak in Week 6. The Eagles, however, faced an embarrassing collapse, losing five out of their last six games. Therefore, in the last three seasons, the Ravens had a better performance compared to the Steelers and Eagles. |

### E.1 PORTool

Figure: Figure 6: Step-by-step reasoning and tool usage under PORTool. Tool calls are shown in blue and tool responses in green. Formatting edition for presentation clarification.

## Appendix F Example II: What’s 70 days from march 21

### F.1 ToolRL

Figure: Figure 7: Step-by-step reasoning and tool usage under ToolRL, a step-supervised RL approach. The generated answer is incorrect because it cannot correct the errors in a tool call.

### F.2 PORTool

Figure: Figure 8: Step-by-step reasoning and tool usage under PORTool with Qwen-2.5-7B backbone. While the method generates a correct answer, it also adds a meaningless year, 2023. From the evaluation agent’s perspective, this answer is labeled as true.

## Appendix G Example III: How many hours to tomorrow

### G.1 PORTool with Qwen-2.5-7B

Figure: Figure 9: Step-by-step reasoning and tool usage under PORTool with the Qwen-2.5-7B backbone.

### G.2 PORTool with Qwen-3-1.7B

Figure: Figure 10: Step-by-step reasoning and tool usage under PORTool with the Qwen-3-1.7B backbone.