PaperlayerView exact revision on arXiv

Source-linked AI summary

PORTool: Importance-Aware Policy Optimization with Rewarded Tree for Multi-Tool-Integrated Reasoning

Feijie Wu, Weiwu Zhu, Yuxiang Zhang, Soumya Chatterjee, Jiarong Zhu, Fan Mo, Rong Luo, Jing Gao

arXiv:2510.26020v2cs.CLcs.AIcs.LG

TL;DR

Outcome-only training for multi-tool reasoning leaves ambiguity about which intermediate decisions matter. PORTool uses shared-prefix rollout trees to estimate step importance and combine local comparisons with trajectory feedback. The paper reports improved final-answer accuracy and fewer tool-call steps than state-of-the-art policy-optimization baselines.

  • Problem

    Outcome-only rewards for complete tool-use trajectories do not reliably identify which intermediate decisions drive success, while step-level supervision can miss long-horizon dependencies and penalize valid alternatives.

    Source: §1 · p. 2

  • Method

    PORTool branches rollouts from shared prefixes, estimates step importance from terminal correctness and bounded execution/format feedback, and combines fork-relative with trajectory-relative advantages.

    Source: §1 · p. 2, §3.2 · p. 6, §5 · p. 10

  • Results

    PORTool consistently improves final-answer accuracy while reducing tool-call steps and failure modes compared with state-of-the-art policy-optimization baselines.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The rewarded rollout tree supports fine-grained credit assignment from outcome feedback while keeping training trajectory-supervised.

    Source: §3.2 · p. 7

    The formulation assumes queries generally require multi-step reasoning and may admit multiple valid tool-use trajectories.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

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 from outcome-only rewards suffers from credit-assignment ambiguity, obscuring which intermediate tool-use decisions drive 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 satisfy formatting constraints and 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 policy-optimization baselines, and ablation studies confirm the robustness of the proposed step-wise importance estimates.

1 Introduction

The introduction identifies credit-assignment ambiguity in outcome-supervised tool use and limitations of step-level supervision. It presents PORTool’s rewarded rollout tree and step-wise importance estimates as an approach to improving tool-use learning.

1 Introduction

  • Step-level supervision can enforce canonical tool-use routines and miss long-horizon dependencies, making behavior brittle to unexpected or failed tool outputs.This is especially relevant when tools return different results for equivalent queries or at different times.Source: §1 · p. 2
  • Outcome-only trajectory rewards provide no reliable signal about which intermediate decisions are decisive, recoverable, or incidental.Broadcasting a shared reward can reinforce invalid calls or suppress useful steps that co-occur with failures.Source: §1 · p. 2
  • PORTool branches rollouts from shared prefixes to compare alternative tool-use decisions under the same interaction history.It estimates step importance using final-answer correctness and lightweight tool-format and execution signals.Source: §1 · p. 2
  • PORTool updates its policy using both fork-level comparisons and trajectory-level feedback to favor effective, robust, and efficient tool calls.The introduction contrasts interactive tool learning with prompting approaches that guide reasoning and calls through demonstrations.Source: §1 · pp. 1, 3
  • PORTool improves final-answer accuracy while reducing tool-call steps compared with state-of-the-art baselines, and ablations validate its step-wise design.The method combines fork-level comparisons with trajectory-level feedback.Source: §1 · p. 3

2 Related Works

Related work covers policy optimization for reasoning and two main approaches to tool-use training: supervised imitation and reinforcement learning. PORTool is positioned against methods that use uniform trajectory feedback or heuristic branching.

RL Algorithms for LLM Reasoning

  • Reasoning-focused policy optimization uses verifiable or rule-based rewards, while process rewards can require dense annotations or an additional verifier.GiGPO derives step-wise rewards from final outcomes but relies on matching repeated anchor states; PORTool compares actions under identical prefixes and adds execution and format checks.Source: §2 · p. 3

Tool-use Agent Training

  • Tool-use agents are trained with supervised fine-tuning on traces or reinforcement learning with interaction feedback; imitation can limit exploration and robustness under distribution shifts.The passage also describes RL methods including Search-R1, ARPO, and PORTool.Source: §2 · p. 3
  • Search-R1 uses uniform trajectory-level feedback, while ARPO branches at uncertain tool-call steps and may miss confident-but-wrong decisions.PORTool instead uses shared-prefix rollouts and outcome plus execution/format feedback to infer step importance.Source: §2 · p. 3

3 PORTool

PORTool addresses outcome-only credit-assignment ambiguity with shared-prefix rollout trees and step-wise importance estimates, then combines fork-level and trajectory-level advantages to guide policy updates.

3.1 Problem Formulation

  • The training system pairs a tool-use agent interacting with executable tools with an evaluation agent that judges final-answer correctness and assigns outcome rewards.The judge maps true, false, and unable-to-answer outcomes to +1, −1, and 0, respectively.Source: §3.1 · p. 4
  • Uniform trajectory-level credit can decrease the sampling probability of a step necessary for correctness, potentially unlearning that correct step.Theorem 3.1 formalizes this collateral-unlearning risk for GRPO-style updates.Source: §3.1 · p. 5

3.2 Algorithm Description

  • PORTool organizes rollouts into a bounded-branching tree: trajectories share prefixes, then branch into alternative next steps under the same interaction history.This enables direct comparison of competing tool-use decisions within a shared prefix.Source: §3.2 · pp. 5–6
  • Each step’s importance reflects whether its descendants can reach a correct outcome, with decay favoring shorter solutions and bounded formatting/execution feedback.The adaptive aggregator uses max when sibling rewards differ and average otherwise; correctness remains dominant over the auxiliary signal.Source: §3.2 · p. 6
  • PORTool combines trajectory-relative advantages, scoring whole rollouts, with fork-relative advantages, comparing sibling candidates, to guide token-level policy optimization.The fork term is scaled to account for the different averaging schemes of the two signals.Source: §3.2 · pp. 6–7

4 Experiments

Experiments evaluate PORTool on real assistant queries and public benchmarks, compare it with RL baselines, and test design choices through ablations. PORTool improves accuracy while reducing tool-call steps, and the ablations favor a decay factor of 0.95, scaled advantage blending, and adaptive aggregation.

4.1 Setup

  • The setup uses 3,607 real assistant queries split into 3,072 training and 535 evaluation queries, with 21 function-style tools and four evaluation metrics.The metrics are final-answer accuracy, tool-call steps, unanswerable rate, and formatting reward.Source: §4.1 · pp. 7–8

4.2 Comparison with Other Baselines

  • 3.84% higher accuracy than GRPOfm on Qwen-3-1.7B; PORTool also beats the second-best RL baseline in accuracy with fewer tool-call steps on Qwen-2.5-7B-Instruct.On Qwen-3-1.7B, PORTool also has the lowest unanswerable rate and fewest tool-call steps; SimpleTIR has the highest formatting reward at 0.884, while PORTool reaches 0.877.Source: §4.2 · pp. 8–9, Table 1 · p. 8
  • PORTool achieves the best or tied-best aggregate performance on ToolBench and TravelPlanner, with a consistent average gain over the strongest ToolBench baseline.These are out-of-distribution tasks evaluated with Qwen-2.5-7B-Instruct.Source: §4.2 · p. 9, Table 2 · p. 9

4.3.1 Effect of the Decay Factor γ

  • γ = 0.95 gives the highest final outcome and formatting rewards while converging to the fewest tool-call steps; γ = 1.0 tends to use more steps.At γ = 0.0, the discounted outcome term vanishes for non-terminal steps, weakening guidance for long-horizon correctness.Source: §4.3.1 · p. 9, Figure 3 · p. 10

4.3.2 Effect of the Advantage Coefficients

  • The scaled combination of trajectory-relative and fork-relative advantages outperforms trajectory-only, fork-only, and unscaled settings.Trajectory-only lacks fork-level comparisons, while fork-only supplies no informative signal at steps without meaningful siblings.Source: §4.3.2 · pp. 9–10, Figure 5 · p. 10

4.3.3 Effect of Reward Function R(sj,t) Design

  • Adaptive G achieves the best final outcome and formatting rewards, outperforming always-average, always-max, and mix2 aggregation designs.Always-average can dilute rare successful branches, while always-max can overemphasize a single high-reward descendant.Source: §4.3.3 · p. 10, Figure 6 · p. 10

5 Conclusion

PORTool addresses trajectory-level credit-assignment ambiguity with prefix-sharing rollouts and prefix-consistent step-wise importance derived from correctness and bounded execution/format feedback. The conclusion reports improved final-answer accuracy and fewer tool-call steps than state-of-the-art policy-optimization baselines.

5 Conclusion

  • PORTool improves final-answer accuracy while reducing tool-call steps and failure modes compared with state-of-the-art policy-optimization baselines.Its mixed advantage combines coarse trajectory-relative and fine-grained fork-relative signals.Source: §5 · p. 10

A.1 Tree Rollout

  • Rollouts share prefixes and diverge at selected tool-call steps, enabling matched comparisons between alternative decisions under the same interaction history.The rollout procedure maintains a bounded branching factor while generating a fixed number of trajectories.Source: §5 · p. 10, §A.1 · p. 14

A.2 Rollout-Tree Notations

  • A rollout-tree node represents a shared-prefix step, and its child set identifies distinct next-step branches from that history.Multiple trajectories may pass through one node, while duplicate next steps are represented by a single distinct child.Source: §A.2 · p. 15

A.3 Reward Components and Rescaled Formatting Reward

  • Step-wise importance combines descendant outcome rewards with bounded formatting and execution feedback, rescaled so correctness dominates.The formatting rubric rewards reasoning-block presence, valid tool-call structure, parseable JSON, required fields, and successful invocation.Source: §A.4 · p. 15, §A.3 · p. 15

A.4 Step-wise Reward and Adaptive Aggregation G

  • At forks, PORTool uses max when child best-case values differ and average when they tie, emphasizing the best viable branch or its reliability.Averaging distinguishes children with equally successful best cases when one succeeds more consistently; discounting also reflects efficiency when γ < 1.Source: §A.4 · pp. 15–16

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

This section derives how PORTool combines trajectory-relative and fork-relative advantages in a token-level policy objective. Its scaling aligns fork-level averaging with the objective’s per-trajectory and per-token averaging.

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

  • PORTool defines trajectory-relative and fork-relative advantages using z-score normalization, with fork-relative advantages set to zero for steps that are not children of a fork.The two signals provide coarse trajectory scoring and fine-grained comparisons among sibling tool-call candidates.Source: §A.5 · p. 16
  • The formulation combines trajectory and fork objectives additively rather than placing a summed advantage inside a single clipped objective.The stated scaling aligns the fork contribution with trajectory/token averaging, up to a constant that cancels when applied to both numerator and denominator.Source: §A.5 · pp. 17–18
  • The fork-wise objective averages over forks, then children and their tokens, and rescales the fork advantage to match per-trajectory/token averaging.The scaling ω2 is specified by the relative weights of these averaging schemes.Source: §A.5 · pp. 17–18

B Proof of Theorem 3.1

The proof analyzes whether trajectory-level reward broadcasting can reduce the probability of a necessary tool-use step. It identifies conditions under which this collateral unlearning occurs under a local, small-step GRPO-style update.

B Proof of Theorem 3.1

  • Under binary terminal outcomes, a necessary step, z-score trajectory advantages, and per-token averaging, the proof studies one expected local GRPO-style update.The local step probability is parameterized directly, and the update is assumed small enough for a first-order expansion to determine its direction.Source: B Proof of Theorem 3.1 · p. 19
  • Trajectories omitting a necessary step are incorrect, and their contributions must be included alongside trajectories containing that step when computing its local probability update.The term 1{E} − p accounts for both groups under the softmax-policy analysis.Source: B Proof of Theorem 3.1 · pp. 19–20
  • Collateral unlearning is more likely when correct trajectories containing the necessary step are long or rare, while incorrect trajectories containing it are relatively short.The passage attributes this condition to per-token weighting induced by broadcasting trajectory-level rewards.Source: B Proof of Theorem 3.1 · p. 21

C.1 Data Construction and Splits

The experiments use real assistant queries and executable tool interactions, with a held-out evaluation split and a calibrated automatic outcome judge. Training proceeds through supervised fine-tuning followed by reinforcement learning.

C.1 Data Construction and Splits

  • The dataset contains 3,607 anonymized real-user queries across eight assistant domains, split into 3,072 training and 535 evaluation queries.The queries include both time-sensitive and time-invariant tasks.Source: §C.1 · p. 22

C.2 Executable Tool Environment and Interaction Format

  • Tool outputs, including explicit errors, are appended to context, and evaluation interactions terminate at response_gen or after six tool-call steps.The agent emits reasoning followed by structured JSON tool calls.Source: §C.2 · p. 22

C.3 Automatic Outcome Judge and Calibration

  • The GPT-4o outcome judge agrees with human annotations on 94.37% of a calibration set of approximately 700 query–answer pairs.Each evaluated trajectory is judged five times, with correctness assigned by majority vote.Source: §C.3 · p. 23

C.4 Training and Implementation Details

  • Training uses five epochs of supervised fine-tuning followed by 15 epochs of reinforcement learning, with eight rollouts per query and a six-step episode cap.The specified LoRA configuration uses rank 16 and α=8.Source: §C.4 · p. 23

C.5 Additional Benchmarks

The paper evaluates tool use on ToolBench and multi-step planning on TravelPlanner, following each benchmark’s stated evaluation setup.

C.5 Additional Benchmarks

  • ToolBench evaluation uses StableToolBench to simulate responses from APIs originally hosted on third-party platforms.The evaluation follows the standard ToolBench protocol.Source: §C.5 · p. 23
  • ToolBench evaluation follows its standard protocol for measuring tool-call success and task completion.Source: §C.5 · p. 23
  • TravelPlanner tests multi-step planning and execution in travel scenarios using the benchmark’s default splits and evaluation settings.Source: §C.5 · p. 23

C.6 Implementation

The implementation specifies training and rollout settings, tool-call schemas and prompt rules, and illustrative examples of agent tool use.

C.6 Implementation

  • Experiments use eight NVIDIA H100 GPUs, eight rollouts per query, and 15 training epochs, with five epochs of supervised fine-tuning beforehand.The batch size is 512, with 128 samples per policy update; the reported performance averages the best three checkpoints.Source: §C.6 · p. 24

D Tool Schemas and Prompt Cards

  • The prompt requires a reasoning block and a JSON-array tool-call block, and directs the agent to use response_gen only after the task is resolved.Tool calls contain a tool name and argument dictionary; multiple calls may be made simultaneously.Source: D Tool Schemas and Prompt Cards · p. 25
  • The prompt-card schemas include tools for evaluating math expressions, comparing timestamps, and sorting objects by a numeric field.The timestamp comparator requires two timestamps and a comparison operator; the sorter requires an object list, property path, and sort order.Source: D Tool Schemas and Prompt Cards · pp. 28–29

E.1 PORTool

  • In the Steelers, Ravens, and Eagles example, all three standings calls return no data.The query asks which team performed better over the last three seasons.Source: §E.1 · p. 30

F.2 PORTool

The PORTool example retries a failed date calculation with a timestamp format the tool accepts; another example is captioned as step-by-step tool use with Qwen-2.5-7B.

F.2 PORTool

  • For a query asking 70 days from March 21, the calculator rejected the date-only input 2023-03-21 as invalid, then adding P70D to 2023-03-21T00:00:00 returned Tuesday, May 30, 2023.The result was reported in America/Los_Angeles as 2023-05-30T00:00:00-07:00.Source: §F.2 · pp. 32–33
  • The figure caption says the answer is correct despite adding the meaningless year 2023, which the evaluation agent labels true.Source: Figure 9 · p. 33

G.1 PORTool with Qwen-2.5-7B

  • The next example asks how many hours remain until tomorrow, and its figure caption identifies step-by-step PORTool reasoning with Qwen-2.5-7B.Source: §G.1 · p. 34, Figure 10 · p. 34

G.2 PORTool with Qwen-3-1.7B

The Qwen-3-1.7B example shows an agent using current-time context to answer a question about hours until tomorrow, with conflicting arithmetic in its reasoning.

G.2 PORTool with Qwen-3-1.7B

  • The example asks how many hours remain until tomorrow and uses get_current_context to retrieve the current time in Los Angeles.The retrieved time is Sunday, October 5, 2025, at 16:52:30.Source: §G.2 · p. 35
  • The reasoning first gives 8 hours, then corrects this to 7 hours and 8 minutes from 4:52 PM to midnight.A later continuation reverses course and says 8 hours and 8 minutes before returning to 7 hours.Source: §G.2 · pp. 35–36
  • Figure 11 is captioned as step-by-step reasoning and tool use with the Qwen-3-1.7B backbone.Source: Figure 11 · p. 36
Loading 2510.26020v2…