Source-linked AI summary
MatchTIR: Fine-Grained Supervision for Tool-Integrated Reasoning via Bipartite Matching
Changle Qu, Sunhao Dai, Hengyi Cai, Jun Xu, Shuaiqiang Wang, Dawei Yin
TL;DR
Existing TIR reinforcement learning methods assign uniform credit across multi-turn trajectories, making it difficult to distinguish effective from redundant or erroneous tool calls. MatchTIR uses bipartite matching for dense turn-level rewards and combines them with trajectory-level outcomes through dual-level advantage estimation. Experiments across three benchmarks show strong performance, particularly in long-horizon and multi-turn scenarios, including 4B models surpassing most 8B baselines.
Problem
Uniform outcome- or trajectory-level credit assignment fails to distinguish heterogeneous tool-call quality in long-horizon, multi-turn TIR.
Method
MatchTIR matches predicted and ground-truth tool calls with hard or soft bipartite assignment, then combines turn-level rewards with trajectory-level outcomes.
Results
MatchTIR achieves the highest performance among compared baselines across three benchmarks, with especially pronounced improvements in long-horizon, multi-turn scenarios.
Takeaways & Limitations
Fine-grained turn-level supervision enables MatchTIR to distinguish useful tool calls from redundant or uninformative ones across model scales.
Takeaways & Limitations
MatchTIR relies on ground-truth trajectories and was not evaluated on larger-scale models; open-ended tasks may lack verifiable ground-truth reasoning steps.
Abstract
from arXiv · showhide
Tool-Integrated Reasoning (TIR) empowers large language models (LLMs) to tackle complex tasks by interleaving reasoning steps with external tool interactions. However, existing reinforcement learning methods typically rely on outcome- or trajectory-level rewards, assigning uniform advantages to all steps within a trajectory. This coarse-grained credit assignment fails to distinguish effective tool calls from redundant or erroneous ones, particularly in long-horizon multi-turn scenarios. To address this, we propose MatchTIR, a framework that introduces fine-grained supervision via bipartite matching-based turn-level reward assignment and dual-level advantage estimation. Specifically, we formulate credit assignment as a bipartite matching problem between predicted and ground-truth traces, utilizing two assignment strategies to derive dense turn-level rewards. Furthermore, to balance local step precision with global task success, we introduce a dual-level advantage estimation scheme that integrates turn-level and trajectory-level signals, assigning distinct advantage values to individual interaction turns. Extensive experiments on three benchmarks demonstrate the superiority of MatchTIR. Notably, our 4B model surpasses the majority of 8B competitors, particularly in long-horizon and multi-turn tasks. Our codes are available at https://github.com/quchangle1/MatchTIR.
1 Introduction
Existing TIR reinforcement learning methods often assign uniform credit across all turns, obscuring the difference between useful and erroneous tool calls. MatchTIR addresses this with bipartite matching-based turn-level rewards and dual-level advantages, achieving strong results across three benchmarks, especially for long-horizon tasks.
- Motivation: Uniform advantages across trajectory turns fail to distinguish critical reasoning steps from redundant or erroneous tool calls.This coarse credit assignment can hinder learning precise and efficient tool-use strategies.
- Motivation: Existing fine-grained reward approaches face bias, hallucination, computational-cost, variance, or ground-truth ambiguities in long-horizon and open-ended settings.These limitations are especially relevant when intermediate tool calls lack a unique reliable reference.
- MatchTIR: MatchTIR formulates turn-level credit assignment as bipartite matching between predicted and ground-truth tool calls.Similarity scores use tool names, parameter names, and parameter contents to align calls.
- MatchTIR: Hard one-to-one and soft one-to-many assignment strategies produce dense, precise rewards for intermediate tool interactions.The two strategies convert matching relationships into turn-level reward signals.
- MatchTIR: MatchTIR combines turn-level rewards with outcome-based rewards through dual-level advantage estimation.The framework balances local turn accuracy with global trajectory success.
- Results: MatchTIR performs strongly across three benchmarks, with particularly pronounced gains in long-horizon scenarios.The reported experiments support effectiveness, robustness, and generalizability.
2 Preliminaries
The paper formulates TIR as generating multi-turn interaction trajectories with tool calls and environment observations, then optimizes the policy using GRPO. Its objective motivates precise turn-level rewards because uniform trajectory credit is poorly suited to heterogeneous multi-turn contributions.
- Task Formulation: TIR agents generate interaction trajectories whose turns contain reasoning, invoked tools with parameters, and environment observations.A trajectory ends with a final response or when the maximum turn limit is reached.
- Task Formulation: The training goal is to assign precise turn-level rewards that encourage effective tool use and penalize redundant or erroneous actions.This directly targets inefficient credit assignment in long-horizon, multi-turn reasoning.
- Agentic Reinforcement Learning: GRPO estimates advantages from relative performance among multiple rollouts generated for the same prompt, without requiring a learned value function.The framework uses a group of G rollouts to compute relative advantages.
- Agentic Reinforcement Learning: MatchTIR’s framework combines turn-level reward modeling with dual-level advantage estimation for policy optimization.The process matches predicted and golden tool calls using hard or soft assignment while integrating turn- and trajectory-level signals.
- Agentic Reinforcement Learning: GRPO’s objective uses importance sampling, normalized token advantages, clipping, and KL regularization against a reference model.Tokens generated by external tools are masked because they are not controlled by the agent.
3 Our Approach: MatchTIR
MatchTIR assigns fine-grained rewards to tool-use turns by matching predicted and ground-truth calls, then combines local and global signals for distinct advantages. Its reward design uses similarity-based alignment, hard or soft assignment, turn-level aggregation, and outcome supervision.
- Matching Matrix Construction: MatchTIR formulates turn-level credit assignment as alignment between predicted and ground-truth tool calls, rewarding informative actions while penalizing redundant or uninformative ones.The matching score incorporates tool names, parameter names, and parameter contents.
- Matching Matrix Construction: Matching scores compare tool-name consistency, parameter-name overlap, and parameter-content correctness between predicted and ground-truth calls.Tool-name matching uses an indicator function, while parameter-name matching uses Jaccard similarity.
- Hard Credit Assignment: Hard assignment solves a maximum-weight bipartite matching problem with one-to-one constraints, assigning a fixed penalty or zero to unmatched erroneous or redundant calls.The Hungarian algorithm solves the matching problem.
- Soft Credit Assignment: Soft assignment uses optimal transport to distribute credit across predicted turns, giving the largest share to the highest-alignment turn while retaining partial feedback for relevant attempts.The transport plan maps predicted and ground-truth interactions probabilistically.
- Turn-Level Reward: Tool-call rewards are averaged within each interaction turn, normalizing rewards across turns and discouraging excessive tool usage.The averaging accounts for turns containing different numbers of predicted tool calls.
- Dual-Level Advantage Estimation: MatchTIR combines turn-level and outcome-level supervision: the latter uses answer F1 as a global constraint, while dual-level advantages capture trajectory quality and discounted future consequences.Trajectory-level advantages compare complete rollouts within a sampled group; local advantages distinguish individual turns.
4 Experiments
Experiments across three benchmarks show that MatchTIR improves performance, especially for complex multi-turn tasks, while producing more selective tool use. Ablations and sensitivity analyses support combining turn-level rewards with trajectory-level signals.
- 4.2 Experimental Results: Posttraining methods generally improve over vanilla models across benchmarks, and multi-turn training outperforms single-turn training under similar reward designs.
- 4.2 Experimental Results: Both MatchTIR variants achieve the highest performance across three benchmarks, with 4B models surpassing most 8B baselines.The authors attribute this to turn-level rewards and dual-level advantage estimation.
- 4.2 Experimental Results: The hard KM variant consistently outperforms soft OT, which may assign partial credit to near-miss calls that are fatal during execution.KM enforces strict one-to-one matching and supplies a binary signal for exact tool usage.
- 4.3 Ablation Study: Ablations show that turn-level rewards outperform outcome rewards, while combining turn-level and outcome rewards and integrating both advantage levels yields further gains.The results support balancing local execution quality with global trajectory context.
- 4.4 Robustness to Task Complexity: MatchTIR’s gains over vanilla increase with task complexity, with the largest improvements on the Hard subset for both 4B and 8B models.Queries are grouped by the number of tool invocations required, and the trend favors long-horizon multi-turn tasks.
- 4.5 Tool-Use Efficiency and Accuracy: Fine-grained supervision reduces tool-call frequency and failure rates while increasing tool-call success rates across Qwen3-4B and Qwen3-8B.The authors interpret this as more selective and accurate tool invocation rather than excessive or redundant calling.
- 4.6 Hyper-parameter Analysis: Increasing penalty scale improves Solve-P but marginally reduces Solve-R, whereas increasing γ from 0.1 to 0.9 consistently improves all evaluation metrics.The analyses indicate a precision–success trade-off for penalties and sensitivity to long-horizon dependencies for discounting.
5 Related Work
Related work increasingly densifies reinforcement-learning supervision for tool-integrated reasoning, but existing approaches still struggle to assign credit to individual actions. MatchTIR addresses this gap with turn-level rewards and dual-level advantage estimation.
- 5 Related Work: RLVR methods progressed from outcome rewards to trajectory-level signals, but most still assign one reward across an entire trajectory.This leaves actions with identical advantages despite differing contributions.
- 5 Related Work: Coarse-grained feedback prevents models from distinguishing effective tool calls from ineffective ones in multi-turn scenarios.MatchTIR instead introduces turn-level reward assignment and dual-level advantage estimation.
- 5 Related Work: Fine-grained reward efforts include sampling-based and model-based methods, while Monte Carlo approaches can suffer high variance and computational cost.External reward models are also described as susceptible to bias and hallucination.
6 Conclusion
MatchTIR provides fine-grained supervision for Tool-integrated Reasoning through bipartite matching, turn-level rewards, and dual-level advantage estimation. Experiments show effectiveness across model scales, especially in long-horizon, multi-turn interactions.
- MatchTIR uses bipartite matching to provide fine-grained supervision for Tool-integrated Reasoning.
- The framework combines turn-level reward design with dual-level advantage estimation to distinguish high-quality tool calls from redundant or uninformative ones.
- Experiments across in-domain and out-of-domain benchmarks demonstrate effectiveness across various model scales.
- MatchTIR shows particularly pronounced improvements in long-horizon, multi-turn interaction scenarios.
Limitations
The study reports two limitations: experiments exclude larger-scale models, and the method depends on ground-truth trajectories that are difficult to obtain in open-ended tasks.
- Experiments were limited to Qwen3-4B and Qwen3-8B because computational resources prevented evaluation on larger-scale models.
- Turn-level supervision relies on ground-truth trajectories, whose parameters and reasoning steps are difficult to determine or verify in highly open-ended tasks.
- Adapting MatchTIR to tasks such as deep research remains a challenging direction for future work.
A Benchmark Details
The appendix describes FTRL, BFCL, and ToolHop as benchmarks for evaluating tool-integrated reasoning across execution difficulty, function-calling scenarios, and multi-hop tool use. It also defines the principal verifiable metrics and dataset statistics used in evaluation.
- FTRL: FTRL evaluates tool-integrated reasoning in automatically constructed local execution environments and organizes scenarios into four difficulty levels.The levels are Single-Hop, Parallel Single-Hop, Multi-Hop, and Parallel Multi-Hop.
- FTRL: FTRL reports Solve-P, Solve-R, and Solve-F1 to measure tool-call precision, subtask-completion completeness, and their harmonic mean.
- FTRL: FTRL is used for both training and in-domain evaluation because its structured feedback and multi-turn interactions suit fine-grained credit-assignment research.
- BFCL: BFCL evaluates function-calling across multi-turn and agentic scenarios, including incomplete information, long context, web search, and memory.
- ToolHop: ToolHop evaluates multi-hop tool use with 995 user queries and 3,912 locally executable tools, using Answer Correctness as its primary metric.
B More Implementation Details
The appendix provides training configurations and implementation details for MatchTIR’s advantage estimation and evaluation setup. Turn-level advantages compare only rollouts that reach the relevant turn, while BFCL Web Search uses the Bing Search API.
- Training configuration: Training hyper-parameter configurations are summarized in Table 5.
- Advantage estimation: Turn-level advantages are computed by comparing rollouts within the same group at each turn among trajectories that reach or exceed that turn.
- Evaluation setup: For BFCL Web Search evaluation, the implementation uses the Bing Search API as the underlying search engine.
C.1 Analysis on Advantage Estimation
This analysis compares intra-trajectory advantage estimation variants with MatchTIR, which combines local turn-level signals with global trajectory advantages. MatchTIR performs better because isolated within-trajectory variation overlooks dependencies between sequential tool calls.
- The Weighted Intra-trajectory Method computes a local turn-level advantage by treating each turn as an independent sample within one trajectory.
- Weighted Product uses the local advantage to scale the global signal, with the weighting direction aligned to trajectory performance.
- Weighted Sum adds the local turn-level signal directly to the global advantage for each turn.
- The Weighted Intra-trajectory Method performs worse than MatchTIR because intra-trajectory normalization overlooks temporal interdependencies between turns.Later-turn success in multi-turn TIR can depend on precise execution of earlier tool calls.
C.2 Analysis on Cost Matrix Construction
The cost-matrix analysis compares linear, normalized, and exponential transformations of matching similarities in the OT framework. Linear and normalized inversion perform similarly, whereas exponential transformation degrades performance through amplified numerical variation.
- The OT analysis constructs the cost matrix from the similarity matrix, so transforming similarity scores directly affects turn-level reward assignment.
- Linear Inversion uses C = −S, while Normalized Inversion uses C = 1−S_norm after min–max normalization.
- Exponential Transformation uses C = −e^S and amplifies differences between high-similarity pairs and other pairs.
- Linear Inversion and Normalized Inversion have relatively similar performance, whereas Exponential Transformation causes a performance drop.The authors attribute the drop to numerical instability, noise amplification, Sinkhorn convergence difficulties, and high-variance advantages.
- End-to-end multi-turn optimization outperforms expanded single-turn training, indicating that additional decomposed data does not explain the multi-turn advantage.On ToolRL, single-turn decomposition instead causes a performance decline; on FTRL, it improves performance but remains inferior.