Technical Summary: Proxy State-Based Evaluation for Multi-turn Tool-Calling LLM Agents

Problem Statement

Interactive Large Language Model (LLM) agents are increasingly deployed in industrial workflows (e.g., commerce, account management) to solve multi-turn, multi-step tool-calling tasks. Effective development requires two components: (1) stable evaluation that accurately reflects whether an agent achieves user goals, and (2) on-policy data generation to enable learning from interaction and environment feedback.

Current agentic benchmarks (e.g., $\tau$-bench, $\tau^2$-bench, AppWorld) utilize a "benchmark-as-environment" paradigm with final state-based evaluation. While this approach correctly scores terminal database states rather than rigid trajectory matching, it relies on fully deterministic backends. Building and iterating on these deterministic engines demands substantial engineering effort (e.g., schema design, deterministic tools, assertions), with some benchmarks requiring tens of thousands of lines of code and extensive unit testing. This engineering burden slows iteration and limits scalability for industrial applications.

The central question addressed is: Can we retain the benefits of final state-based evaluation without building a heavy deterministic backend?

Methodology: Proxy State-Based Evaluation

The authors propose Proxy State-Based Evaluation, an LLM-driven simulation framework that replaces the deterministic database with an LLM-inferred "proxy state." The system operates as a "benchmark-as-environment" consisting of five cooperating LLM components:

1. Scenario Specification ($z$): A structured object defining the user goal, user facts, system facts (initial state), expected final proxy state, and expected agent behavior. This replaces the need for a ground-truth trajectory.
2. Reasoning Agent (RA): The model under evaluation, which follows a ReAct-style loop (reason $\to$ act $\to$ observe) to interact with the environment via multi-turn dialogue and multi-step tool calls.
3. User Simulator ($f_{user}$): Generates user utterances conditioned on the scenario's user facts, goals, and a specific persona (e.g., power user, confused, ambiguous).
4. Tool Simulators ($f_{tool}$): Simulate tool responses (e.g., account management, commerce) by "reading from" and "writing to" the current proxy state based on the RA's subqueries and system facts.
5. State Tracker ($f_{state}$): An LLM component that infers the structured proxy state ($\tilde{s}_{t,k}$) from the full interaction trace up to step $(t,k)$. Unlike step-by-step state updates, it conditions on the entire trajectory prefix to ensure robustness against error accumulation.
6. LLM Judges:
   • Goal-Completion Judge: Evaluates the final proxy state and agent response against the scenario's expected final state and behavior to classify outcomes (goal completed, user error, or agent error).
   • Hallucination Detection Judge: Detects if the tool simulator or user simulator generated information inconsistent with the scenario constraints.

Evaluation Metrics: The framework measures Goal Completion (GC) rates, user/agent error rates, and hallucination rates (tool and user). It supports both on-policy data generation (for Rejection Sampling Fine-Tuning) and off-policy data generation (for Supervised Fine-Tuning).

Key Contributions

1. Formalization of Proxy State-Based Evaluation: The paper formalizes a practical benchmark that preserves state-based evaluation principles without requiring a deterministic backend, utilizing an LLM-inferred proxy state extracted from interaction traces.
2. Scenario Schema and Component Architecture: It introduces a specific scenario schema and a five-component LLM architecture (Reasoning Agent, User Simulator, Tool Simulators, State Tracker, Judge) that cooperates to simulate complex workflows.
3. Reliability Framework: The authors define reliability criteria including bootstrapped standard errors, hallucination rates, and human-LLM judge agreement. They execute targeted ablations on persona sensitivity, system/user fact completeness, and state-tracker strength.
4. Scalable Data Generation: The environment generates scalable on-policy and off-policy rollouts suitable for post-training (SFT/RFT) and provides stable metrics for model comparison.

Results

The benchmark was evaluated across diverse model families (GPT-5, GPT-4o, Gemini-2.5, Qwen3) and reasoning efforts:

• Model Differentiation: Goal Completion (GC) rates scale consistently with model strength and inference-time reasoning effort. For instance, within the GPT-5 family, higher reasoning effort yields monotonic GC gains (High: 85.76% > Minimal: 66.04%).
• Training Effectiveness: Training the base Qwen3-30B-A3B model within this environment significantly improved performance. Supervised Fine-Tuning (SFT) using off-policy data from a stronger teacher increased GC from 65.64% to 77.34%. Rejection Sampling Fine-Tuning (RFT) also yielded improvements.
• Robustness to Complexity: While performance decreases with conversation depth for base models, SFT training provides substantial gains in long conversations (+26.69 percentage points), indicating the training signal generalizes to harder, multi-step interactions.
• Reliability and Hallucination:
  • Human-LLM Agreement: Exceeded 90%, validating the automated evaluation.
  • Simulator Hallucinations: Under default configurations (GPT-5o with medium reasoning effort), tool and user hallucination rates were near-zero (1.33% and 0.67%, respectively).
  • Ablation Findings: Removing system facts or user facts from scenarios caused a monotonic increase in hallucination rates, confirming that meticulous scenario specification is critical. Weaker state trackers (e.g., GPT-4o) increased tool hallucination rates, highlighting the need for accurate state inference.
• Cross-Model Robustness: Model rankings and training gains remained consistent even when the simulator and judge models were swapped (e.g., using Gemini-2.5-Pro instead of GPT-5o), ruling out circular bias from a single-model family setup.

Significance and Claims

The paper claims that Proxy State-Based Evaluation offers a practical, scalable alternative to deterministic agentic benchmarks for industrial LLM agents. By decoupling state-based evaluation from the engineering burden of building deterministic backends, the framework enables:

• Faster Iteration: Scenarios can be stood up quickly and evolve with product roadmaps without extensive code engineering.
• Rigorous Evaluation: It maintains the rigor of final state verification while supporting the flexibility of multiple correct tool-calling paths.
• Effective Training: It generates high-quality on-policy and off-policy data that successfully improves open-weight agents via SFT and RFT, with gains transferring to unseen scenarios.

The authors position this work not as a replacement for all deterministic testing, but as a necessary evolution for industrial settings where the cost of deterministic backends is prohibitive, yet the need for state-based, goal-oriented evaluation remains paramount.