AgentAssay: Token-Efficient Regression Testing for Non-Deterministic AI Agent Workflows

Varun Pratap Bhardwaj

cs.AIMar 3, 2026

AgentAssay: Token-Efficient Regression Testing for Non-Deterministic AI Agent Workflows

Authors: Varun Pratap Bhardwaj

Organizations: Independent Researcher

Abstract

Autonomous AI agents are deployed at unprecedented scale, yet no principled methodology exists for verifying that an agent has not regressed after changes to its prompts, tools, models, or orchestration logic. We present AgentAssay, the first token-efficient framework for regression testing non-deterministic AI agent workflows, achieving 78-100% cost reduction while maintaining rigorous statistical guarantees. Our contributions include: (1) stochastic three-valued verdicts (PASS/FAIL/INCONCLUSIVE) grounded in hypothesis testing; (2) five-dimensional agent coverage metrics; (3) agent-specific mutation testing operators; (4) metamorphic relations for agent workflows; (5) CI/CD deployment gates as statistical decision procedures; (6) behavioral fingerprinting that maps execution traces to compact vectors, enabling multivariate regression detection; (7) adaptive budget optimization calibrating trial counts to behavioral variance; and (8) trace-first offline analysis enabling zero-cost testing on production traces. Experiments across 5 models (GPT-5.2, Claude Sonnet 4.6, Mistral-Large-3, Llama-4-Maverick, Phi-4), 3 scenarios, and 7,605 trials demonstrate that behavioral fingerprinting achieves 86% detection power where binary testing has 0%, SPRT reduces trials by 78%, and the full pipeline achieves 100% cost savings through trace-first analysis. Implementation: 20,000+ lines of Python, 751 tests, 10 framework adapters.

Figures & tables

Feature	AgentAssay	agentrial	deepeval	promptfoo	METAL	ProbTest
Multi-step agent workflows	✓	✓	—	—	—	—
Stochastic verdicts	✓	$\circ$	—	—	—	$\circ$
Formal test semantics	✓	—	—	—	—	$\circ$
Confidence intervals	✓	✓	—	—	—	—
Regression detection	✓	✓	—	—	—	—
SPRT adaptive stopping	✓	—	—	—	—	—

Table 1: Feature comparison of agent testing approaches. ✓ indicates full support,

\circ

partial support, — no support.

Test Type	Offline?	Soundness	Live Cost
Coverage analysis	Yes	Lower bound	$0
Contract checking	Yes	Sound	$0
Metamorphic relations	Yes	Sound (unbiased)	$0
Mutation testing	Partial	Evaluator only	$\approx$ $0
SPRT regression	No	Sound	Reduced by Pillars 1–2
Deployment gate	Hybrid	Sound	Reduced

Table 2: Trace-first compatibility of AgentAssay test types. “Offline” means the test can run at zero additional token cost given a sufficient trace store. “Reduced” means only a subset of the test requires live agent executions.

Figure 1: AgentAssay token-efficient testing pipeline. Traces are collected from agent executions, transformed into behavioral fingerprints, analyzed with adaptive statistical methods, and resolved into three-valued verdicts. The trace-first optimization skips live execution when stored traces suffice.

Component	Lines of Code
Core Engine (statistics, verdicts)	3,092
Coverage Analyzer	844
Mutation & Metamorphic Engine	3,710
Token-Efficient Engine	2,324
Framework Adapters (10 frameworks)	4,469
Infrastructure (CLI, dashboard, persistence)	5,644

Table 3: Implementation statistics for AgentAssay .

Model	Trials	Tokens/Trial	Cost/Trial	Latency (ms)
GPT-5.2	1,050	$112\pm 23$	$0.0009	$2{,}295\pm 465$
Sonnet 4.6	1,050	$142\pm 31$	$0.0018	$2{,}920\pm 3{,}820$
Mistral-Large-3	1,050	$561\pm 346$	$0.0033	$4{,}422\pm 3{,}034$
Llama-4-Maverick	1,050	$106\pm 20$	$0.0000	$613\pm 180$
Phi-4	1,050	$116\pm 64$	$0.0000	$12{,}874\pm 11{,}877$

Table 4: Agent behavioral characterization across 5 models, 3 scenarios, and 7 experiment configurations (E1–E6). Each cell aggregates

7\times 3\times 50=1{,}050

trials per model. Significant cross-model variation confirms the need for stochastic testing.

Figure 2: E7: Cost per regression check across five approaches. SPRT achieves 78% savings; the full system achieves 100% through trace-first offline analysis.

Approach	Mean Trials	Mean Cost	Savings	Power
Fixed- $n$ (baseline)	$100\pm 0$	$\$ 0.287\pm 0.184$	—	0.00
SPRT	$22\pm 0$	$\$ 0.064\pm 0.042$	77.6%	0.00
SPRT + Fingerprint	$20.3\pm 0.7$	$\$ 0.059\pm 0.038$	79.5%	0.86
SPRT + FP + Budget	$20.3\pm 0.7$	$\$ 0.058\pm 0.038$	79.7%	0.86
Full system	$0\pm 0$	$\$ 0.000\pm 0.000$	100.0%	0.94

Table 5: E7: Token-efficient testing. Mean cost per regression check at equivalent

(\alpha=0.05,\beta=0.10)

guarantees. Results aggregated across 4 models, 3 scenarios, and 25 repetitions (

n=1{,}250

data points).

Figure 3: Detection power comparison. Binary pass/fail testing (Fixed-

n

, SPRT) achieves 0% power. Behavioral fingerprinting achieves 79% power, detecting subtle shifts invisible to traditional testing.

Figure 4: Cost savings consistency across three agent domains. SPRT savings are remarkably stable (77.7–78.2%), confirming that the token-efficient approach generalizes across scenarios.

Figure 5: Per-model cost comparison. Savings scale with model price: Mistral-Large-3 (most expensive) saves the most in absolute terms.

Model	Fixed- $n$	SPRT (savings)	Full (savings)
GPT-5.2	$0.127	$0.028 (78%)	$0.000 (100%)
Sonnet 4.6	$0.196	$0.043 (78%)	$0.000 (100%)
Mistral-L3	$0.338	$0.076 (77%)	$0.000 (100%)
Llama-4-Maverick	$0.000	$0.000 (N/A)	$0.000 (N/A)

Table 6: E7: Per-model cost comparison across all 3 scenarios. Fixed-

n

baseline cost vs. SPRT and full-system savings.

Scenario	Fixed- $n$ Cost	SPRT Savings	Full Savings
E-commerce	$0.170	77.7%	100%
Customer Support	$0.372	77.5%	100%
Code Generation	$0.174	78.2%	100%

Table 7: E7: Per-scenario consistency. SPRT savings are remarkably stable across all three agent domains.

Explore similar work

Willful Disobedience: Automatically Detecting Failures in Agentic Traces
Mar 25, 2026Reshabh K Sharma, Shraddha Barke, Benjamin ZornAI Agent Evaluation AI Agent Auditing
University of Washington Seattle, Washington, USA · Microsoft Research Redmond, Washington, USA
AgentCheck: A Reproduce-Intervene-Mitigate Workbench for LLM Agents over MCP
Jul 13, 2026Aritra Mazumder, Nusrat jahan LiaAI Agent Reliability LLM Agent Evaluation
University of Utah · University of Dhaka
Chronicle: Cut-Point Replay for Regression Testing of LLM Agents
Sep 17, 2026Tisha Chawla, Susheem KoulLLM Agents LLM Agent Reliability
Microsoft

Mar 25, 2026J/K move · Enter open · S save

Willful Disobedience: Automatically Detecting Failures in Agentic Traces

Reshabh K Sharma, Shraddha Barke, Benjamin Zorn

University of Washington Seattle, Washington, USA · Microsoft Research Redmond, Washington, USA

AI Agent Evaluation AI Agent Auditing

Open paper AskPDF arXiv

AI agents are increasingly embedded in real software systems, where they execute multi-step workflows through multi-turn dialogue, tool invocations, and intermediate decisions. These long execution histories, called agentic traces, make validation difficult. Outcome-only benchmarks can miss critical procedural failures, such as incorrect workflow routing, unsafe tool usage, or violations of prompt-specified rules. This paper presents AgentPex, an AI-powered tool designed to systematically evaluate agentic traces. AgentPex extracts behavioral rules from agent prompts and system instructions, then uses these specifications to automatically evaluate traces for compliance. We evaluate AgentPex on 424 traces from

τ^2

-bench across models in telecom, retail, and airline customer service. Our results show that AgentPex distinguishes agent behavior across models and surfaces specification violations that are not captured by outcome-only scoring. It also provides fine-grained analysis by domain and metric, enabling developers to understand agent strengths and weaknesses at scale. The source code of AgentPex is available at https://github.com/microsoft/agentpex.

Abstract

Explore similar work

Willful Disobedience: Automatically Detecting Failures in Agentic Traces

AgentCheck: A Reproduce-Intervene-Mitigate Workbench for LLM Agents over MCP

Chronicle: Cut-Point Replay for Regression Testing of LLM Agents