Technical Summary: PROVE — Programmatic Rewards On Verified Environments

Problem Statement

Training Large Language Models (LLMs) to orchestrate multi-step tool calls faces three coupled obstacles that hinder the deployment of autonomous agents:

1. Costly Realistic Environments: Building realistic, stateful execution environments is resource-intensive, leading many pipelines to rely on cached or simulated APIs that miss state-dependent failure modes.
2. Detached Synthetic Data: Synthetic training queries are often generated without grounding in the server's actual state. Consequently, generated tool calls reference non-existent entities, causing execution failures during training.
3. Verbosity Incentives: Standard recall-based Reinforcement Learning (RL) rewards incentivize verbose tool-calling patterns. Models learn to emit excess tool calls to maximize Ground Truth (GT) coverage, a regression rarely penalized explicitly.

Methodology: The PROVE Framework

The authors propose PROVE (Programmatic Rewards On Verified Environments), a framework that tightly couples data synthesis to the RL loop via a shared live-execution backend. The methodology consists of three core components:

1. Live MCP Environment Framework

Instead of static caches, PROVE utilizes a library of 20 stateful Model Context Protocol (MCP) servers exposing 343 tools across domains such as finance, productivity, commerce, travel, and IoT.

• Stateful Execution: Unlike cached APIs, these servers capture realistic state-dependent dynamics (e.g., account balances changing after transfers, persistent calendar events).
• Session-Scoped Isolation: Each RL rollout episode receives a unique session ID, ensuring state isolation and reproducible initial conditions.
• Integration: The framework integrates with the VERL RL framework, routing model-generated tool calls to the appropriate MCP server and returning execution responses.

2. Grounded State-Machine Data Synthesis

To address the issue of detached synthetic data, PROVE employs an automated pipeline that generates validated multi-turn trajectories:

• Dependency Graph Discovery: An LLM classifies relationships between tool pairs (explicit, implicit, or none) to build a dependency graph, seeding realistic multi-step chains.
• Live-State Sampling: Before query generation, the system probes the live MCP server to enumerate real entities (e.g., valid account IDs, existing cities). This "sampling context" is injected into the prompt, constraining the LLM to use only entities that actually exist in the server state.
• State-Machine Orchestrator: A finite state machine drives the conversation, managing transitions between query generation, LLM processing, tool execution, and recovery (retrying with corrected parameters or alternative tools).
• Robustness & Validation: The pipeline introduces probabilistic perturbations (distractors, stripped enums, irrelevant queries) and performs replay validation against freshly reset environments. Only conversations with error rates below 30% and valid sensitive-parameter provenance are retained.
• Dataset: The process yields ~13,517 training examples, including multi-turn conversations, clarification trajectories, and abstention examples.

3. Multi-Component Programmatic Reward

PROVE introduces a fully programmatic reward function ($R_{total}$) composed of five parts, requiring no external "LLM-as-judge" model:

1. Validity ($R_{validity}$): A graduated score (0–1) based on function name existence, parameter compatibility, and successful live execution.
2. Coverage ($R_{coverage}$): Measures if all GT workflow steps are completed in the correct dependency order. It enforces that model calls must include all GT argument keys to match.
3. Adaptive Efficiency ($R_{efficiency}$): A key contribution designed to counter verbosity. It applies a penalty for calls exceeding a complexity-scaled budget ($B = n_{gt} + \lceil n_{gt} \cdot \beta \rceil$). This allows slack for complex tasks while penalizing unnecessary calls.
4. Tool-Name Signal ($R_{name}$): An explicit bonus for selecting tools whose names appear in the ground truth, addressing the bottleneck where validity scores saturate before correct tool selection is learned.
5. Argument-Value Matching ($R_{arg}$): A bonus for matching specific argument values (not just keys) to the ground truth, disproportionately aiding multi-turn dialog performance.

Experimental Setup

• Models: Four instruction-tuned models from two families: Qwen3-4B, Qwen3-8B, Qwen2.5-7B, and Granite-4.1-8B.
• Training: All models were trained using Group Relative Policy Optimization (GRPO) for 350 steps on 8×H100 GPUs.
• Hyperparameters: Identical reward weights were used across all models; only the learning rate was tuned per family.
• Benchmarks: Evaluation on BFCL Multi-Turn, $\tau$2-bench, and T-Eval.

Results

PROVE demonstrated consistent improvements across all four models and three benchmarks using only ~13K training examples (roughly 8× less than concurrent RL pipelines like AgenticQwen):

• BFCL Multi-Turn: Improvements of up to +10.2 points (Qwen3-4B).
• $\tau$2-bench: Improvements of up to +6.8 points (Qwen2.5-7B).
• T-Eval: Improvements of up to +6.5 points (Qwen2.5-7B).

Ablation Studies:

• Reward Components: Removing the Adaptive Efficiency penalty ($\beta=0$) or the Tool-Name signal resulted in the largest aggregate drops (~9 points across benchmarks), confirming their critical role in preventing verbosity and guiding tool selection.
• RL vs. SFT: When trained on the same data via Supervised Fine-Tuning (SFT), models often regressed on multi-turn benchmarks (e.g., $\tau$2-bench), whereas PROVE consistently improved performance. This suggests the reward signal is essential for converting synthetic trajectories into reliable agentic behavior.
• Teacher Robustness: Results remained stable when the data synthesis "teacher" LLM was swapped (Gemma-4-31B-it vs. Qwen3-32B), indicating gains stem from the reward formulation and live-execution loop rather than specific teacher styles.

Significance and Claims

The paper claims that a compact, fully programmatic reward coupled with grounded data synthesis can drive consistent multi-step tool-orchestration gains without:

• Large-scale data pipelines (using ~13K examples vs. millions).
• Expensive "LLM-as-judge" models for reward calculation.
• Manual annotation.

The authors emphasize that the adaptive efficiency penalty and the tool-name signal are the most load-bearing components, successfully addressing the verbosity and tool-selection bottlenecks that have historically limited RL for tool use. By tightly coupling synthesis to live execution, PROVE ensures that training data is executable and that the reward signal reflects real-world state-dependent dynamics.