Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents
summary
The gist
Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation <ref:2607.06873#pg2> This paper presents AGENTEVAL…
In short
AGENTEVAL is a black-box testing framework designed to find and stress hidden failures in conversational AI agents, like failing a transaction without confirmation. It works by mining a workflow graph from observed conversations to identify where stateful boundaries exist. This structure guides the generation of targeted tests that probe these critical points, providing a repeatable way to test complex agent behavior.
Key concepts
- Conversational Workflow Graph
- This is a map created by analyzing an agent's conversation history. It abstracts raw chat turns into discrete activities and links them based on which action immediately followed another. This graph shows the sequence of steps the agent takes, revealing the structure where critical decisions or 'guards' must be enforced.
- Direct-Follows Construction
- This is a specific method used to build the workflow graph. It connects two activities in the graph if one appears immediately after another in a conversation trace. This technique helps model how an agent moves from one state or action to the next, creating a structural representation of its behavior.
- Graph-Guided Boundary Testing
- Instead of testing random inputs, this method uses the workflow graph's structure to generate tests. It identifies specific points (nodes or edges) in the graph and creates a test that intentionally perturbs the agent's state right at that structural location to stress its limits or guard conditions.
- Black-Box Testing Framework
- AGENTEVAL is a testing tool that interacts with an agent only through its chat interface. It does not need access to the agent's internal code. It discovers failures by observing the external conversation and using the derived workflow graph to strategically create tests that expose hidden stateful errors.
Terminology used across episodes
This episode discusses
- Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents · Paper Radio
- tau-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains
- tau squared-Bench: Evaluating Conversational Agents in a Dual-Control Environment
- STELLAR: A Search-Based Testing Framework for Large Language Model Applications
- tau-Knowledge: Evaluating Conversational Agents over Unstructured Knowledge
- Towards Self-Evolving Benchmarks: Synthesizing Agent Trajectories via Test-Time Exploration under Validate-by-Reproduce Paradigm
- TestAgent: Automatic Benchmarking and Exploratory Interaction for Evaluating LLMs in Vertical Domains
- Graph2Eval: Automatic Multimodal Task Generation for Agents via Knowledge Graphs
- Are Large Language Models Reliable AI Scientists? Assessing Reverse-Engineering of Black-Box Systems
- TestART: Improving LLM-based Unit Testing via Co-evolution of Automated Generation and Repair Iteration
- On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks
The paper
Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents · Read on arXiv
Lero, the Research Ireland Centre for Software at the University of Limerick, Ireland · The Chinese University of Hong Kong, Shenzhen China
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents".
Jane: Here's the gist of the paper. Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation <ref:2607.06873#pg2> This paper presents AGENTEVAL, a black-box testing framework that discovers and stresses these stateful boundaries <ref:2607.06873#pg2>.
Tom: The Problem of Hidden Boundaries Critical failures in conversational agents often occur at workflow boundaries where guards or prerequisites must be enforced, but these points are hidden behind multiturn conversational prerequisites, making them inaccessible to standard tests <ref:2607.06873#pg2>.
Jane: Existing testing paradigms fall short because they either test for overall task success or perturb single inputs rather than stressing stateful guards <ref:2607.06873#pg2>.
Tom: A tester cannot write a test plan for a workflow it cannot see, and the black box hides where a boundary is and how to reach it <ref:2607.06873#pg2>.
Title and authors: Jane: So, what's the main point of this paper called "Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents"?
Tom: It’s essentially about using a graph structure to guide testing instead of just blindly prompting the agent.
Lu: The core idea is building a model, or a graph, of how the agent behaves based on real conversations, and then using that map to generate specific tests that hit those tricky points.
Meng: So you're saying instead of trying random things, you look at the conversation flow and target where the agent has to make a decision or follow a rule.
Tom: That’s right. The paper says this is important because standard testing methods usually miss these crucial points because they don't know where those boundaries are hidden in the long conversation sequence.
Jane: It sounds like they’re trying to map out the agent's logic from scratch just by watching it interact with a user, which is a pretty clever way to build that understanding.
Lalam: If I’m looking at this, I see them using something called a directly-follows graph to link observed events together in the conversation.
The paper's summary: Tom: They spend a lot of time talking about how they mine this conversational workflow graph from unstructured turns using an LLM to turn raw text into discrete agent activities.
Lu: That abstraction is key because it lets them build a structure, and then they use that structure to deterministically walk every location in the graph.
Jane: So, if you have this map of the conversation flow, AGENTEVAL doesn't just pick random spots; it asks an LLM for a test specifically designed to stress the guard or limit observed at that spot.
Tom: That’s what they call graph-guided boundary testing, and it means they are generating tests that directly target where stateful boundaries like confirmation gates are supposed to be enforced.
Meng: I'm curious how deep this goes when we talk about those structural locations, because for us in production, we need to know exactly what breaks at scale.
Jane: The paper shows them using these structural locations, like node activities or edges, and perturbing the workflow near them to stress those stateful boundaries.
Lalam: I see they are looking at things like confirmation gates which are marked as amber nodes in their examples, and they generate tests by trying things like a premature confirmation or a cancel anyway perturbation.
The paper's improvements: Tom: One of the big claims is that this graph-guided generation yields twenty-three to thirty-eight distinct boundaries per agent, which is nearly double what you get without any structural guidance.
Lu: That jump from a baseline of zero point five six duplicate rate down to zero point two six in their airline agent example shows that targeting the structure really helps cut down on redundant tests.
Jane: They also mention that this method maintains near-zero false-alarm rates, which is important because we don't want this framework just finding fake problems.
Meng: I have to ask, what about the actual effort? The paper mentions it uses twenty-eighty five LLM calls and a million five hundred thousand tokens in about two and a half hours for the airline domain.
Tom: That’s actually pretty efficient when you compare it to just prompting blindly or using graph context methods.
Lu: The efficiency comes from structural targeting rather than just feeding the whole graph into the prompt context, which is what they found was more economical in terms of LLM calls and tokens.
Conclusion: Jane: So to wrap up, AGENTEVAL provides a way to test conversational agents black-box without needing access to their source code.
Tom: It does this by mining the conversation into a workflow graph and using that structure to generate targeted tests that replay paths right up to those stateful boundaries.
Lu: The real power here is how it uncovers a larger, more diverse set of critical boundaries than methods that don't use structural guidance at all.
Meng: From a deployment standpoint, the ability to get this kind of coverage on a black-box system is valuable, even if we have to be careful about how much we rely on LLM proposals for those boundary counts.
Lalam: I’m just confident in the results because the execution phase judge reliably catches twenty-two out of twenty-seven seeded faults on airline scenarios, which shows it's sensitive to what actually happens in the behavior.
Tom: So, the full picture is that we have a repeatable foundation for regression testing these complex systems using this method called Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game