Toward Scalable Verifiable Reward: Proxy State-Based Evaluation for Multi-turn Tool-Calling LLM Agents

Yun-Shiuan Chuang; Chaitanya Kulkarni; Alec Chiu; Avinash Thangali; Zijie Pan; Shivani Shekhar; Yirou Ge; Yixi Li

cs.AIFeb 18, 2026

Toward Scalable Verifiable Reward: Proxy State-Based Evaluation for Multi-turn Tool-Calling LLM Agents

Authors: Yun-Shiuan Chuang, Chaitanya Kulkarni, Alec Chiu, Avinash Thangali, Zijie Pan, Shivani Shekhar, Yirou Ge, Yixi Li, +3 more

Organizations: PayPal AI

Abstract

Interactive large language model (LLM) agents operating via multi-turn dialogue and multi-step tool calling are increasingly used in production. Benchmarks for these agents must both reliably compare models and yield on-policy training data. Prior agentic benchmarks, such as tau-bench, tau^2-bench, and AppWorld, rely on fully deterministic backends, which are costly to build and iterate. We propose Proxy State-Based Evaluation, an LLM-driven simulation framework that preserves final state-based evaluation without a deterministic database. Specifically, a scenario specifies the user goal, user/system facts, expected final state, and expected agent behavior, and an LLM state tracker infers a structured proxy state from the full interaction trace. LLM judges then verify goal completion and detect tool/user hallucinations against scenario constraints. Empirically, our benchmark produces stable, model-differentiating rankings across model families and inference-time reasoning efforts, and its on-/off-policy rollouts provide supervision that transfers to unseen scenarios. Careful scenario specification yields near-zero simulator hallucination rates, as supported by ablation studies. The framework also supports sensitivity analyses over user personas. Human-LLM judge agreement exceeds 90%, indicating reliable automated evaluation. Overall, proxy state-based evaluation offers a practical, scalable alternative to deterministic agentic benchmarks for industrial LLM agents.

Figures & tables

Figure 1: Overview of the proxy state-based evaluation benchmark. In a multi-turn interaction, an LLM-based user simulator converses with a reasoning agent that plans and executes multi-step tool calls to LLM-based tool simulators. An LLM judge, calibrated with human experts, determines goal completion by checking the final proxy state. The benchmark 1) evaluates the reasoning agent’s ability to achieve goals via multi-turn dialogue and tool-calling, and also 2) yields conversation data with rewards and supporting a leaderboard for comparing reasoning agents.

Figure 2: A scenario $z$ specifies user goal $g(z)$ and user facts $u(z)$ (both used by user simulator and LLM judge), system facts $s_{0}(z)$ (used by tool simulators, state tracker, and LLM judge), expected final state $s^{\ast}(z)$ , and expected agent behavior (both used by LLM judge). Arrows denote inputs. These fields drive the interactive simulation and proxy state-based evaluation.

Figure 3: Goal completion rate (GC) on testing scenarios $\mathcal{Z}_{\text{test}}$ across baseline reasoning agents and trained models. Error bars show the bootstrap standard error. Fine-tuning substantially improves the base Qwen3-30B-A3B-Thinking-2507 model. RE: reasoning effort.

Figure 4: Ablations on scenario facts increase hallucinations. We randomly remove a fraction of system facts $s_{0}(z)$ or user facts $u(z)$ . Tool hallucination rate and user hallucination rate rise steadily with more facts being removed. Error bars show the bootstrap standard error.

Figure 5: User persona sensitivity analysis. Error due to user ( $\mathrm{ER}_{\text{user}}$ ) and user hallucination rate ( $\mathrm{HR}_{\text{user}}$ ) across three personas $p$ . More challenging personas increase user-induced errors and user hallucination rates. Error bars denote bootstrap standard error.

Turn depth	# Scenarios (%)	Base GC	SFT GC
Short (1–2)	40.35	74.75	82.44
Medium (3–4)	35.04	69.51	85.39
Long (5+)	24.61	42.75	69.44

Table 1: Goal completion rate (%) stratified by conversation turn depth on

\mathcal{Z}_{\text{test}}

RA Model	Original	Exp (a)	Exp (b)
GPT-5 (high)	85.76	75.78	86.59
Gemini-2.5-Pro	76.08	65.79	70.56
Qwen3-235B-A22B	71.74	62.22	68.61
Qwen3-30B-A3B	65.64	53.75	64.59
Qwen3-30B-A3B-SFT	77.34	71.89	79.96

Table 2: Cross-model robustness: GC (%) under different simulator/judge configurations. Original: all GPT-5o; (a): sim. = GPT-5 (med.), judge = Gemini-2.5-Pro; (b): all Gemini-2.5-Pro.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Dimension	Three-way Agreement (%)
Goal completion ( $c$ )	82.7
Tool hallucination ( $h_{\text{tool}}$ )	94.7
User hallucination ( $h_{\text{user}}$ )	94.7

Appendix

Table 3: Three-way agreement among two human experts and the LLM judge on

n{=}50

conversations.

Figure 6: Conversation flow across sequential steps, showing user turns, reasoning-agent tool calls, and tool responses. Brand names and trademarks have been redacted.

Figure 7: Conversation flow across sequential steps, showing user turns, reasoning-agent tool calls, and tool responses. Brand names and trademarks have been redacted.

Figure 8: Conversation flow across sequential steps, showing user turns, reasoning-agent tool calls, and tool responses. Brand names and trademarks have been redacted.

Explore similar work

Evaluating Tool-Using Language Agents: Judge Reliability, Propagation Cascades, and Runtime Mitigation in AgentProp-Bench
Apr 17, 2026Bhaskar GurramAI Agent Reliability Tool-Augmented Language Model Agents
Zasti Inc., Ashburn, VA, USA
UserProxyBench: Evaluating LLM User Simulators for Agent Benchmarks and Training
Sep 29, 2026Ashish Jain, Armaan SandhuAI Agent Benchmarks User Simulation
Sarvam AI
PACE: A Proxy for Agentic Capability Evaluation
Jul 2, 2026Yueqi Song, Lintang Sutawika, Jiarui Liu +8Benchmark Design LLM Agent Evaluation
Carnegie Mellon University · Salesforce AI Research

Apr 17, 2026J/K move · Enter open · S save

Evaluating Tool-Using Language Agents: Judge Reliability, Propagation Cascades, and Runtime Mitigation in AgentProp-Bench

Bhaskar Gurram

Zasti Inc., Ashburn, VA, USA

AI Agent Reliability Tool-Augmented Language Model Agents LLM-as-a-Judge LLM Agent Evaluation AI Agent Benchmarks LLM Reliability+2

Open paper AskPDF arXiv

Automated evaluation of tool-using large language model (LLM) agents is widely assumed to be reliable, but this assumption has rarely been validated against human annotation. We introduce AgentProp-Bench, a 2,000-task benchmark with 2,300 traces across four domains, nine production LLMs, and a 100-label human-validated subset. We quantify judge reliability, characterize error propagation, and evaluate a runtime mitigation. Substring-based judging agrees with human annotation at kappa=0.049 (chance-level); a three-LLM ensemble reaches kappa=0.432 (moderate) with a conservative bias. Under validated evaluation, a parameter-level injection propagates to a wrong final answer with human-calibrated probability approximately 0.62 (range 0.46-0.73 across models). Rejection (catching bad parameters) and recovery (correcting after acceptance) are independent model capabilities (Spearman rho=0.126, p=0.747). A tuned runtime interceptor reduces hallucination on GPT-4o-mini by 23.0 percentage points under a concurrent n=600 control, but shows no significant effect on Gemini-2.0-Flash, whose aggressive parameter rejection eliminates the target failure mode. All code, data, traces, and human labels are released at https://github.com/bhaskargurram-ai/agenthallu-bench.

Abstract

Explore similar work

Evaluating Tool-Using Language Agents: Judge Reliability, Propagation Cascades, and Runtime Mitigation in AgentProp-Bench

UserProxyBench: Evaluating LLM User Simulators for Agent Benchmarks and Training

PACE: A Proxy for Agentic Capability Evaluation