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

Anay Kulkarni, ChiaEn Lu, Dheeraj Mekala, Jayanth Srinivasa, Gaowen Liu, Jingbo ShangarXiv 2026 · arXiv

TL;DR

Reinforcement learning for multi-step LLM tool use typically fails because final outcome rewards are too sparse, while trajectory-matching rewards are too rigid. This paper introduces TIER (Trajectory-Invariant Execution Rewards), a framework that ditches reference trajectories entirely, instead calculating dense rewards directly from API schemas and runtime execution feedback. TIER enables stable training, maintaining over 90% accuracy even on complex 6-step tool composition tasks where traditional methods completely collapse.

What Problem Does This Paper Address?

Large Language Models (LLMs) excel at simple, single-step tool use, but real-world agent tasks often require multi-step tool composition—chaining multiple interdependent API calls together (e.g., fetching a flight status, extracting the destination city, and then querying the weather for that city). As the depth of these tool chains increases, performance drops precipitously.

Training these agents using Reinforcement Learning (RL) typically runs into a reward design bottleneck:

  1. Outcome-based rewards (did the model get the final answer right?) are too sparse. For a 4+ step composition, the odds of an LLM randomly stumbling upon the exact right sequence of API calls during exploration are near zero.
  2. Trajectory-supervised rewards (did the model match a human-annotated sequence of tool calls?) are too rigid. They penalize perfectly valid alternative paths (like swapping the execution order of two independent APIs) and require expensive re-annotation whenever an API schema changes.

Methods

The authors propose TIER, a trajectory-invariant reward framework. TIER evaluates what a tool-use sequence accomplishes rather than which path it takes to get there. It reads API schemas and executes code dynamically at training time to provide dense, sequence-level feedback.

Figure 1: Left: Overview of TIER for tool-augmented LLM agents. The model generates structured tool calls as abstract syntax trees (ASTs), which are executed against external tools. Unlike trajectory- supervised approaches, rewards are computed directly from function schemas and execution outcomes. Right (Top): TIER provides fine-grained, multi-level supervision decomposing into format, schema, execution, and answer correctness. In contrast, simple outcome rewards offer only sparse binary feedback. Right (Bottom): Training curves under different reward designs. Only the full fine- grained TIER reward achieves stable convergence to high performance. Partial rewards plateau early, and trajectory-supervised rewards (ToolRL) exhibit high variance due to inconsistent supervision across alternative valid compositions. All training reward curves are exponentially weighted moving averages of per-step batch-mean reward logged over a 50-step rolling window (smoothing constant, α = 0.01). The shaded region is a ±1 rolling standard deviation. For visualization, we linearly rescale the rewards to [0, 1]

The TIER reward function decomposes into four distinct, verifiable components:

  • Format Validity ($R_{format}$): A binary check ensuring the generated tool calls are syntactically well-formed and parsable into an Abstract Syntax Tree (AST).
  • Schema Adherence ($R_{parse}$): Graded feedback checking if tool names, parameter names, and data types match the actual API definitions.
  • Execution Success ($R_{exec}$): An all-or-nothing binary reward indicating whether every tool call executed successfully without runtime errors. Because multi-step tasks are highly interdependent, a failure at step $k$ invalidates all downstream steps.
  • Answer Correctness ($R_{answer}$): A heavily weighted reward given only if the final output matches the expected answer. This high weight prevents the model from "reward hacking" (i.e., executing safe, error-free tools that don't actually answer the prompt).

TIER is optimization-agnostic and was validated using Group Relative Policy Optimization (GRPO) and Direct Advantage Policy Optimization (DAPO).

Datasets

The paper evaluates TIER on three benchmarks:

  1. DepthBench (New): A depth-stratified benchmark created by the authors containing 1,710 queries requiring tool compositions ranging from 0 to 6 steps deep. It features a fully executable backend with 163 hand-crafted tools and includes deceptive "distractor" tools to rigorously test generalization.
  2. BFCL v3 (Berkeley Function Calling Leaderboard): A real-world function-calling benchmark used to evaluate out-of-distribution generalization.
  3. NestFUL: A benchmark specifically designed for nested and sequential API compositions.

Key Insights and Ideas

  • The "Union" Sufficiency Threshold: Multi-step composition capability does not scale linearly with partial rewards. Ablation studies revealed a sharp threshold: adding only execution feedback or only parsing feedback still results in a total performance collapse (0% accuracy) at depths 5 and 6. All four components must act in unison to unlock deep compositional reasoning.
  • The Danger of Missing Schema Discrimination: Counterintuitively, adding execution rewards without schema parsing rewards actually decreases accuracy. Without schema verification, the model quickly learns to reward-hack by routing queries to a small set of "safe" tools that always execute successfully without error, ignoring the user's actual request.
  • Automatic Adaptation: Because TIER derives its supervision directly from live function schemas rather than static human annotations, it automatically adapts to API updates, deprecations, or additions without requiring data regeneration.

Key Results

  • Sustained Depth Performance: On DepthBench, TIER maintains >90% accuracy across all composition depths (1 to 6 steps). Meanwhile, simple outcome rewards drop below 2% at step 2, and trajectory-supervised rewards (ToolRL) completely collapse to 0% beyond step 4.
Figure 2: (a) Performance on DepthBench. (b) Reward component ablations under TIER
  • State-of-the-Art Transfer: When evaluated on BFCL v3, TIER achieves the highest overall performance (68.92%), significantly outperforming ToolRL (37.27%), which overfits to its training trajectories and fails on multi-turn or irrelevance tasks.
  • Outperforming Giant Models: On NestFUL, a post-trained Qwen-8B model optimized with TIER achieved 75% exact-match accuracy, outperforming massive frontier models like DeepSeek-V3 (685B parameters) and GPT-4o, which scored 60%.

Limitations and Future Work

  • Assumption of Cheap Execution: TIER assumes that executing tools during RL exploration is cheap, safe, and repeatable. This holds true for synthetic environments but is a major challenge for real-world deployment involving stochastic APIs, financial costs, rate limits, or irreversible side effects (like sending an email or making a purchase).
  • Single-Turn Training Constraint: The current RL training setup is restricted to single-turn generation, meaning the model cannot yet dynamically react to execution errors across multiple conversational turns during training.
  • Future Work: The authors highlight extending TIER to multi-turn RL environments and applying its underlying execution-grounded principles to adjacent fields like code generation and NL-to-SQL.

Summary updated

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.
BibTeX
@misc{kulkarni2026tier,
  author = {Anay Kulkarni and ChiaEn Lu and Dheeraj Mekala and Jayanth Srinivasa and Gaowen Liu and Jingbo Shang},
  title = {{TIER: Trajectory-Invariant Execution Rewards for Multi-Step Tool Composition}},
  year = {2026},
  eprint = {2605.16790},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.16790},
}

Loading related content...

Figure