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

Problem Statement

Large Language Models (LLMs) have demonstrated strong capabilities in single-step tool use, yet they struggle significantly when tasked with multi-step tool composition. As the depth of required tool calls increases (e.g., retrieving flight info to determine a destination, then checking weather at that destination), performance degrades rapidly. Existing Reinforcement Learning (RL) approaches fail to scale to these settings due to limitations in reward design:

1. Outcome-based rewards: Provide only sparse, binary feedback (success/failure) upon task completion. This makes credit assignment for intermediate decisions (tool selection, argument specification, execution order) extremely difficult, leading to training collapse beyond shallow depths (e.g., accuracy drops from >94% at 1-step to 0% beyond 4-steps).
2. Trajectory-supervised rewards: Rely on annotated reference trajectories to provide fine-grained feedback. While they offer denser signals, they penalize valid alternative solutions that deviate from the specific reference path. This rigidity becomes a critical bottleneck as the number of valid execution paths increases with composition depth, causing training instability and failure at deeper levels.

Methodology: TIER Framework

The authors propose TIER (Trajectory-Invariant Execution Rewards), a reward framework that derives supervision directly from function schemas and runtime execution, eliminating the need for annotated reference trajectories.

Core Principle: Trajectory Invariance

A reward function is trajectory-invariant if its value depends only on verifiable properties of the generated sequence and the tool environment, not on the sequence's similarity to a reference trajectory. This ensures that:

• All valid solution paths receive maximum reward, regardless of ordering or commutative operations.
• Invalid solutions are differentiated by the specific properties they violate, providing a graded learning signal without reference to a "gold" path.

Reward Decomposition

The total reward $R_{total}$ is computed per generated tool-call sequence and scaled to $[0, 1]$. It decomposes into four distinct components:

1. Format Validity ($R_{format}$): A binary check (0 or 1) ensuring the Abstract Syntax Tree (AST) of the tool calls is well-formed and parsable. Failure here zeroes all downstream rewards.
2. Schema Adherence / Parsing ($R_{parse}$): A graded score (0 to 3) checking:
   • Name Validity: Whether all tool names exist in the schema.
   • Parameter & Type Correctness: Penalizing mismatches in parameter names and data types against the function schema.
3. Execution Success ($R_{exec}$): A binary check (0 or 1) verifying that every tool call in the sequence executes successfully without runtime errors. This uses an "all-or-nothing" rule because a failure at step $k$ invalidates downstream dependent calls.
4. Answer Correctness ($R_{answer}$): A binary check (0 or 5) verifying if the final synthesized answer matches the expected ground truth. This component is weighted heavily to prevent "reward hacking" where the model satisfies format and execution constraints but fails the actual task.

Training Setup

• Algorithm: The framework is optimized using a GRPO-style policy gradient objective with group-normalized advantages.
• Intermediate Representation (IR): Models generate structured tool calls as JSON-based ASTs, which are parsed and executed against a deterministic backend.
• Agnosticism: The reward formulation is independent of the specific RL optimization algorithm (verified across GRPO, Batch-Normalized GRPO, and DAPO).

Key Contributions

1. TIER Reward Framework: A trajectory-invariant reward system that leverages function schemas and execution feedback, removing the dependency on costly human-annotated reference trajectories.
2. DepthBench: A new benchmark specifically designed to evaluate multi-step tool composition, stratified by depth (0 to 6 steps). It features 1,710 queries over 163 hand-crafted tools with executable backends, enabling systematic analysis of compositional generalization.
3. Empirical Validation of Multi-Level Supervision: The paper demonstrates that compositional tool learning requires concurrent supervision at syntactic (format), structural (schema), and functional (execution) levels. Ablation studies show that removing any component leads to catastrophic failure at deeper compositions.

Experimental Results

The authors evaluated TIER on DepthBench, BFCL v3, and NestFUL, comparing it against outcome-based baselines (Simple-RL) and trajectory-supervised baselines (ToolRL).

• DepthBench Performance:
  • TIER: Achieved >90% accuracy across all composition depths (1–6 steps), including 90% accuracy at depths 5 and 6.
  • Simple-RL (Outcome-based): Accuracy collapsed from 94% at 1-step to 0% beyond 4-steps.
  • ToolRL (Trajectory-supervised): Performance degraded significantly at depths 5 and 6, reaching 0% accuracy, confirming that penalizing valid alternative paths hinders deep composition.
• External Benchmarks:
  • BFCL v3: TIER achieved the best overall accuracy (68.92%), outperforming ToolRL (37.27%) and Simple-RL (66.30%). Notably, ToolRL failed on "Multiturn" and "Irrelevance" categories where adaptive decision-making is required.
  • NestFUL: TIER achieved a 0.684 Exact Match Accuracy, significantly outperforming ToolRL (0.476) and surpassing much larger models (e.g., GPT-4o, DeepSeek-V3) in a 3-shot setting.
• Ablation Insights:
  • Partial rewards (e.g., adding execution without parsing) led to "reward hacking," where models routed queries to "safe" tools to maximize execution rewards while ignoring correctness.
  • Only the full, decomposed reward enabled stable convergence to high performance, highlighting that the components are complementary and non-exchangeable.

Significance and Claims

The paper claims that reward design is the primary bottleneck for multi-step tool composition in RL-trained LLMs. By shifting from reference-trajectory dependence to execution-grounded, trajectory-invariant supervision, TIER enables models to learn complex, multi-step reasoning strategies that were previously intractable.

The authors emphasize that:

• Scalability: TIER naturally adapts to evolving tool interfaces without requiring re-annotation of reference data.
• Generalization: The approach transfers effectively to real-world function-calling settings (BFCL v3) and nested API compositions (NestFUL).
• Necessity of Granularity: Successful compositional reasoning is not a single objective but a multi-level credit-assignment problem requiring simultaneous supervision at format, schema, and execution levels.

The work concludes that TIER provides a robust foundation for scalable, multi-step tool use, though it acknowledges limitations regarding stochastic real-world environments and the current focus on single-turn training.