Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents

2026-06-30 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, extended

Summary

AgentEval is a novel black-box testing framework designed to identify and stress state-dependent failures in conversational LLM agents, such as transactions without confirmation. Traditional testing struggles with these hidden, multi-turn "workflow boundaries." AgentEval addresses this by interacting with an agent to mine a "conversational workflow graph," a model of its behavior. This graph's structure enables the framework to enumerate specific guards and prerequisites as test targets, replaying conversational paths to a boundary before applying a perturbation. Benchmarked against a privileged white-box auditor on four τ³-bench agents, AgentEval successfully generated tests covering 23–38 distinct boundaries per agent. Ablation studies confirmed the graph's efficacy, yielding 23 distinct boundaries compared to 12 from a prompt-only baseline, while also achieving lower duplicate and false-alarm rates.

Key takeaway

For MLOps Engineers deploying conversational LLM agents, you should integrate black-box, graph-guided testing like AgentEval into your CI/CD pipeline. This approach effectively uncovers critical, state-dependent workflow failures that traditional methods miss, ensuring your agents enforce necessary guards and prerequisites. By leveraging conversational workflow graphs, you can generate diverse, high-quality boundary tests, significantly improving the reliability and safety of your deployed agents against real-world harm.

Key insights

Black-box testing of LLM agent workflow boundaries is effective via graph-guided exploration and perturbation.

Principles

• Conversational workflow graphs reveal hidden stateful boundaries.
• Structural graph analysis improves test diversity and reduces duplicates.
• Independent LLM judges enhance black-box test reliability.

Method

AgentEval operates in two phases: Discovery, which explores the agent to build a conversational workflow graph and synthesize a test plan; and Execution, which runs tests and judges outcomes from traces.

In practice

• Mine conversational workflow graphs from agent interaction traces.
• Use graph structure to target stateful boundaries for perturbation.
• Employ separate LLMs for test generation and verdict judgment.

Topics

• LLM Agents
• Black-box Testing
• Conversational AI
• Workflow Graphs
• AI Safety
• Software Testing

Code references

• sierra-research/tau2-bench

Best for: Machine Learning Engineer, NLP Engineer, Research Scientist, AI Scientist, AI Engineer, MLOps Engineer

Related on AIssential

• Chat2Workflow: A Benchmark for Generating Executable Visual Workflows with Natural Language — Automating executable visual workflow generation from natural language remains a significant challenge for current LLMs.
• LogicHunter: Testing LLM Agent Frameworks with an Agentic Oracle — Active, specification-aware fuzzing with an agentic oracle effectively uncovers deep semantic bugs in LLM agent frameworks.
• Connecting the Dots with Context Graphs — Stephen Chin, Neo4j — Context graphs integrate LLMs with knowledge graphs to provide grounded, explainable, and auditable AI-driven decision-making by connecting disparate enterprise data.
• The Infrastructure Behind Making Local LLM Agents Actually Useful — Local LLM agents require deliberate infrastructure for performance and long-session stability beyond basic model serving.
• Beyond the Leaderboard: A Synthesis of Tool-Use, Planning, and Reasoning Failures in Large Language Model Agents — LLM agent failures compound nonlinearly with task length, despite progress in specific sub-tasks.
• How can you test your code when you don’t know what’s in it? — Testing AI-driven agentic workflows requires adapting to LLM non-determinism, moving beyond rigid assertions to intent-based validation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.