TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition

• URL: http://arxiv.org/abs/2605.16790v1
• Date: Sat, 16 May 2026 03:47:26 GMT
• Title: TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition
• Abstract summary: Outcome-based rewards provide only sparse feedback, while trajectory-supervised rewards depend on annotated reference solutions.<n>We propose TIER: Trajectory-Invariant Execution Rewards, a reward framework that derives supervision directly from function schemas and runtime execution.
• Score: 62.56752617853322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tool use enables large language models to solve complex tasks through sequences of API calls, yet existing reinforcement learning approaches fail to scale to multi-step composition settings. Outcome-based rewards provide only sparse feedback, while trajectory-supervised rewards depend on annotated reference solutions, penalizing valid alternatives and limiting scalability. We propose TIER: Trajectory-Invariant Execution Rewards, a reward framework that derives supervision directly from function schemas and runtime execution, rather than from reference trajectories. The reward decomposes into format validity, schema adherence, execution success, and answer correctness, providing dense, interpretable sequence-level feedback derived from fine-grained verification of individual steps of tool use. This design allows any valid execution path to receive credit, naturally supporting multiple solution strategies and adapting to evolving tool interfaces. On DepthBench, a compositional benchmark stratified by depth (1 to 6 steps), TIER achieves >90% accuracy across steps, where trajectory-supervised rewards collapse beyond step-4. We further demonstrate consistent gains on benchmarks like BFCL v3 and NestFUL. Ablation studies confirm that all reward components are necessary, highlighting the importance of multi-level supervision for compositional reasoning.

Related papers

• StructReward: Efficient Structured Process Rewards for Self-Correcting Multimodal Reasoning [3.6795543408370466]
  Reinforcement learning with verifiable rewards (RLVR) has emerged as an effective approach for improving multimodal reasoning.<n>Process reward models offer finer-grained feedback, but they typically rely on separately trained verifiers, costly chain-of-thought annotations, or online judging by large language models.<n>We introduce StructReward, a compute-efficient framework that provides dense reinforcement signals through structured step-level reward alignment.
  arXiv  Detail & Related papers  (2026-08-08T20:29:32Z)
• ExTra: Exploratory Trajectory Optimization for Language Model Reinforcement Learning [75.26064451955199]
  ExTra is a framework that extracts exploration signals from the model's own rollouts.<n>It improves Qwen3-1.7B over GRPO by about +5 points on pass@1 and +7 points on pass@16.
  arXiv  Detail & Related papers  (2026-06-23T15:51:39Z)
• Every Step Counts: Step-Level Credit Assignment for Tool-Integrated Text-to-SQL [13.130554329857496]
  We propose FineStep, a novel framework for step-level credit assignment in tool-augmented Text-to-augmented Text.<n>We show that FineStep achieves state-of-the-art performance and reduces redundant tool interactions, with a 3.25% average EX gain over GRPO at the 4B scale.
  arXiv  Detail & Related papers  (2026-05-06T10:10:31Z)
• SWE-Shepherd: Advancing PRMs for Reinforcing Code Agents [0.31034395048547575]
  Existing approaches rely on static prompting strategies or handcrafteds to select actions such as code editing, file navigation, and test execution.<n>We propose SWE-Shepherd, a framework that introduces Process Reward Models (PRMs) to provide dense, step-level supervision for repository-level code agents.<n>Experiments on SWE-Bench Verified demonstrate improved interaction efficiency and action quality, while also highlighting challenges in aligning intermediate rewards with final task success.
  arXiv  Detail & Related papers  (2026-04-12T06:51:47Z)
• Training LLMs for Multi-Step Tool Orchestration with Constrained Data Synthesis and Graduated Rewards [76.49428173793386]
  LLMs must invoke multiple dependent APIs in the correct order while propagating intermediate outputs.<n>Training models to handle such faces two obstacles: existing environments focus on simple per-turn function calls with simulated data, and binary rewards.<n>We present a framework addressing both challenges. First, we construct a reinforcement learning environment backed by a large-scale cache of real API responses, enabling a data synthesis pipeline that samples valid multi-step orchestration traces.<n>Second, we propose a graduated reward design that decomposes correctness into atomic validity and orchestration.
  arXiv  Detail & Related papers  (2026-03-25T18:31:39Z)
• TopoCurate:Modeling Interaction Topology for Tool-Use Agent Training [53.93696896939915]
  Training tool-use agents typically rely on Supervised Fine-Tuning (SFT) on successful trajectories and Reinforcement Learning (RL) on pass-rate-selected tasks.<n>We propose TopoCurate, an interaction-aware framework that projects multi-trial rollouts from the same task into a unified semantic quotient topology.<n>TopoCurate achieves consistent gains of 4.2% (SFT) and 6.9% (RL) over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-03-02T10:38:54Z)
• ProRAG: Process-Supervised Reinforcement Learning for Retrieval-Augmented Generation [54.071574153853994]
  ProRAG is a process-supervised reinforcement learning framework designed to integrate learned step-level supervision into the online optimization loop.<n>Our framework consists of four stages: (1) Supervised Policy Warmup to initialize the model with a structured reasoning format; (2) construction of an MCTS-based Process Reward Model (PRM) to quantify intermediate reasoning quality; (3) PRM-Guided Reasoning Refinement to align the policy with fine-grained process preferences; and (4) Process-Supervised Reinforcement Learning with a dual-granularity advantage mechanism.
  arXiv  Detail & Related papers  (2026-01-29T16:04:59Z)
• MatchTIR: Fine-Grained Supervision for Tool-Integrated Reasoning via Bipartite Matching [60.886768806064936]
  Tool-Integrated Reasoning empowers large language models to tackle complex tasks by interleaving reasoning steps with external tool interactions.<n>Existing reinforcement learning methods rely on outcome- or trajectory-level rewards, assigning uniform advantages to all steps within a trajectory.<n>We propose MatchTIR, a framework that introduces fine-grained supervision via bipartite matching-based turn-level reward assignment and dual-level advantage estimation.
  arXiv  Detail & Related papers  (2026-01-15T18:59:23Z)
• Integrating Diverse Assignment Strategies into DETRs [61.61489761918158]
  Label assignment is a critical component in object detectors, particularly within DETR-style frameworks.<n>We propose LoRA-DETR, a flexible and lightweight framework that seamlessly integrates diverse assignment strategies into any DETR-style detector.
  arXiv  Detail & Related papers  (2026-01-14T07:28:54Z)
• Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation [27.484259938667776]
  Large Language Models excel at code generation yet struggle with complex programming tasks that demand reasoning.<n>We introduce Outcome Refining Process Supervision, which unifies process and outcome supervision by leveraging executable verification.<n>Experiments across 5 models and 3 benchmarks show consistent gains, with 26.9% higher correctness and 42.2% improved code efficiency.
  arXiv  Detail & Related papers  (2024-12-19T17:59:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.