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

Mar 25, 2026

Willful Disobedience: Automatically Detecting Failures in Agentic Traces

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.

Reshabh K Sharma, Shraddha Barke, Benjamin Zorn

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

AI Agent Evaluation AI Agent Auditing

Ask PDF

Jul 13, 2026

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

Tool-using LLM agents are mostly evaluated assuming all tools work. When a tool times out, returns a week-stale value, or has its description poisoned in deployment, the developer needs a controlled way to reproduce the failure, test a fix, and confirm the fix worked before deployment. We present AgentCheck, an open-source web workbench that turns an MCP server into an intervention surface. AgentCheck runs an agent against its real tools and records every tool response, then re-runs the agent with the response perturbed by a fault (12 types) injector. Matching tool calls are replayed from cache, and later tool calls go live after the agent diverges. This yields a reproduce-intervene-confirm loop: the developer toggles a mitigation, re-runs against the identical fault, and sees if the failure goes away. Scoring has two parts: deterministic pass/fail rules, plus an LLM judge for interpretive labels, validated against human annotations. Across five agents, the best passes 105/120 scenarios and the weakest only 77. The failures are usually silent, confident use of incorrect tool outputs rather than crashes. On the weakest agent, a retry mitigation raises success on timeout error faults from as few as 30% of cases to 100%, whereas stale-data faults remain near 3-4 of 10 regardless of the mitigation. AgentCheck makes these failure modes reproducible, comparable, and verifiable before deployment.

Aritra Mazumder, Nusrat jahan Lia

University of Utah · University of Dhaka

AI Agent Reliability LLM Agent Evaluation LLM Agent Verification Tool-Using Agents LLM Agent Reliability

Ask PDF

Sep 17, 2026

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

Large language model responses are non-deterministic, so failures in LLM agents are hard to reproduce: a failure depends on inference that is not bitwise reproducible, on tools that read changing state, and on a multi-step trajectory that a re-run rarely repeats. Record-and-replay makes a run reproducible, but existing agent tooling records runs only to trace or score them, not to test a code change against them. We present Chronicle, which records an agent run at its non-deterministic boundaries as immutable envelopes and replays it from the record. Its central operation, cut-point replay, serves a chosen subset of boundaries from the record and executes the complementary subset live with new code, turning a recorded incident into a regression test that runs in continuous integration. On a benchmark of 6 recorded failures with simulated model boundaries, recording adds 23 μs per crossing (0.008% of an assumed 300 ms model call), full replay issues zero model calls and is bit-stable across 20 repetitions, and cut-point tests fail on faulty code and pass on guarded and benign changes for all 6 incidents. In a mutation study of the guarded tools, cut-point tests catch every mutant that lets the recorded unsafe action through, while a baseline that stubs every boundary, using the same assertion, catches none. Chronicle and the benchmark are publicly available at https://github.com/theagentplane/chronicle.

Tisha Chawla, Susheem Koul

Microsoft

LLM Agents LLM Agent Reliability

Ask PDF