Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents
Listen
Radio episode about this paper
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.
Lero, the Research Ireland Centre for Software at the University of Limerick, Ireland · The Chinese University of Hong Kong, Shenzhen China
cs.SE
Submitted: 2026-07-08
Updated: 2026-11-16
Code: https://github.com/sierra-research/tau2-bench
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 96/100
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…
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
Summary
Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation <ref:2607. p. 006873#pg2> This paper presents AGENTEVAL, a black-box testing framework that discovers and stresses these stateful boundaries <ref:2607. p. 006873#pg2>.
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>. Existing testing paradigms fall short because they either test for overall task success or perturb single inputs rather than stressing stateful guards <ref:2607. p. 006873#pg2>. 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. p. 006873#pg2>.
The AGENTEVAL Framework
AGENTEVAL interacts with an agent to mine a conversational workflow graph, which serves as a model of its behavior <ref:2607.06873#pg2>. Instead of prompting blindly, AGENTEVAL uses this graph’s structure to enumerate specific guards and prerequisites as test targets <ref:2607. p. 006873#pg2>. The framework runs in two phases: Discovery, which explores the agent through a series of conversations to collect traces within a fixed interaction budget, and Execution, which runs the plan by re-enacting the conversation against a fresh session of the agent <ref:2607. p. 106873#pg2>.
Graph-Guided Boundary Testing
AGENTEVAL adopts the directlyfollows graph to construct a conversational workflow graph from unstructured turns using an LLM to abstract raw conversation turns into discrete agent activities <ref:2607.06873#pg2>. The graph’s structure marks where boundaries can sit, and AGENTEVAL deterministically walks every structural location and asks an LLM for a test that stresses the guard or limit observed there <ref:2607. p. 106873#pg2>. Boundary tests are generated by perturbing the workflow near a selected structural location, such as node activities or edges, to stress stateful boundaries like confirmation gates <ref:2607. p. 306873#pg2>.
Benchmark and Evaluation
To measure effectiveness, AGENTEVAL is benchmarked against a privileged auditor with access to the agent’s underlying source code acting as a ground-truth oracle <ref:2607.06873#pg2>. The benchmark assesses the tester by reporting metrics such as validity rate, distinct boundary count, and false-alarm rates <ref:2607. p. 106873#pg2>. Results show that graph-guided generation yields 23–38 distinct boundaries per agent, cutting the duplicate rate from 0. p. 156 to 0.26 in the airline agent while maintaining near-zero false-alarm rates <ref:2607. p. 106873#pg2>.
Key Contributions
The paper makes three main contributions:
-
A black-box conversational agent testing framework, AGENTEVAL, which tests a deployed conversational agent using only its chat interface without inspecting internals <ref:2607.06873#pg2>.
-
Graph-guided boundary testing, which adapts the directlyfollows graph to mine a conversational workflow graph from black-box conversations and uses this structural model to generate targeted boundary tests <ref:2607.06873#pg2>.
-
A benchmark for black-box conversational agent testing, pairing the tester with a privileged auditor who reports per-phase metrics like functional coverage recall and execution false-alarm rates <ref:2607.06873#pg2>.
Efficiency and Reliability
The full system on the airline domain makes 285 LLM calls and consumes 1.55M tokens in roughly two and a half hours, showing that structural targeting is the most economical boundary generator compared to prompt-only or graph-context methods <ref:2607. p. 806873#pg2>. The execution-phase judge reliably catches 22 out of 27 seeded faults on airline scenarios, demonstrating high sensitivity to violations that surface in behavior <ref:2607. p. 806873#pg2>.
Threats and Limitations
Threats to validity include the reliance on the LLM auditor and the fact that small differences in coverage recall are present across single runs <ref:2607.06873#pg2>. The distinct-boundary count relies on LLM-proposed same-boundary clusters which are then counted deterministically, suggesting stricter independent pairwise judgments are needed for future work <ref:2607. p. 906873#pg2>. The method assumes the agent exhibits recurring interaction patterns for the graph to capture, and faults that never surface in the agent’s text remain out of reach by construction <ref:2607. p. 306873#pg2>.
Related Work Context
AGENTEVAL combines process mining, which mines a process model from event logs, with direct-follows graphs for its conversational workflow graph <ref:2607.06873#pg2>. It also relates to model-based testing and stateful API testing by using the conversational workflow graph as the dependency model that guides test generation <ref:2607. p. 906873#pg2>. The approach lifts the boundary idea from input edges to workflow state preconditions, which is where conversational agents fail <ref:2607. p. 006873#pg2>. This work provides a repeatable foundation for regression testing these complex systems <ref:2607.06873#pg2>.
Conclusion
AGENTEVAL presents a black-box testing framework for conversational LLM agents that targets state-dependent workflow failures by mining a conversational workflow graph from observed interactions <ref:2607.06873#pg2>. It uses this graph’s structure to guide the generation of tests that replay conversational paths to these boundaries before applying targeted perturbations <ref:2607. p. 006873#pg2>. This graph-guided approach uncovers a larger, more diverse set of critical boundaries than methods without such structural guidance, providing a repeatable foundation for regression testing these complex systems <ref:2607.06873#pg2>.
Data Availability and Acknowledgements
The code, prompts, and data used in this paper will be made available upon acceptance <ref:2607.06873#pg2>. This work has emanated from research jointly funded by Taighde Eireann – Research Ireland under Grant Number 13/RC/2094 2, and by Genesys Cloud Services, Inc. p. 0 <ref:2607.06873#pg2>.
References
The references listed support the claims made in the paper regarding agent benchmarks, process mining techniques, and model-based testing approaches <ref:2607.06873#pg2>. The specific citations for each claim are found in the reference list provided at the end of this text <ref:2607.06873#pg2>.
Final Summary Sentence
AGENTEVAL discovers and stresses stateful boundaries by mining a conversational workflow graph from observed interactions to generate targeted, repeatable tests <ref:2607.06873#pg2>.
--- Page 1 ---
Mining Workflow Graphs for Black-Box Boundary Testing of Conversational LLM Agents
Liting Lin Lero, the Research Ireland Centre for Software University of Limerick, Ireland Boxi Yu Lero, the Research Ireland Centre for Software University of Limerick, Ireland Yuzhong Zhang The Chinese University of Hong Kong, Shenzhen China Lionel Briand Lero, the Research Ireland Centre for Software University of Limerick, Ireland David-Paul Niland Genesys Ireland Emir Munoz Genesys Ireland Abstract—Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation <ref:2607.06873#pg2>. Testing these state-dependent failures is difficult because critical boundaries, such as identity checks and confirmation gates, are hidden behind multiturn conversational prerequisites, rendering them inaccessible to standard tests <ref:2607. p. 006873#pg2>. We present AGENTEVAL, a black-box testing framework that discovers and stresses these stateful boundaries <ref:2607. p. 006873#pg2>.
I. INTRODUCTION
Large language models now power conversational agents that act on a user’s behalf [1], [2], calling tools to answer support requests, change bookings, and manage accounts [3] <ref:2607.06873#pg2>. However, conversational agents built on these models often fail, resulting in tangible real-world consequences [4], [5]. p. 0 The most critical failures occur at the agent’s workflow boundaries: the points where a correct agent must enforce a guard, a prerequisite, or a validation before proceeding <ref:2607. p. 006873#pg2>. Most work on evaluating conversational LLM agents focuses on the underlying model’s capability, rather than the deployed system’s correctness <ref:2607. p. 006873#pg2>. The deployed agent, however, is the model combined with the prompts, policies, tools, and guardrails wrapped around it <ref:2607. p. 006873#pg2>. Testing these boundaries is hard because the agent is often a black box: reachable only through a conversational interface <ref:2607. p. 006873#pg2>.
II. PRELIMINARIES
A. Interaction Model
Let A be the conversational agent under test <ref:2607.06873#pg2>. The tester has exactly two operations: reset(A) starts a fresh session, and invoke(A, u)→r sends one user utterance u and returns the visible reply r <ref:2607. p. 206873#pg2>. A session trace (or simply trace) is the ordered sequence of turns σ = ⟨(u1, r1),. p. 2..,(um, rm)⟩, where each turn (ui, ri) pairs a user utterance with the agent’s visible reply <ref:2607. p. 206873#pg2>.
III. APPROACH OVERVIEW
Figure 3 shows the AGENTEVAL pipeline, including two phases: discovery and execution <ref:2607.06873#pg2>. Discovery explores the agent over Rdisc rounds, where each round is one fresh session that yields a single trace of at most Bturn turns <ref:2607. p. 306873#pg2>. Once discovery stops, AGENTEVAL’s test generators synthesize a test plan from the collected traces <ref:2607. p. 306873#pg2>.
IV. MINING THE CONVERSATIONAL WORKFLOW GRAPH
Process mining starts from an event log: a collection of cases, each an observed execution of a process, represented as an ordered sequence of events [14] <ref:2607.06873#pg2>. AGENTEVAL abstracts trace events into user actions and activity states before counting <ref:2607. p. 406873#pg2>. The graph is built using the directly-follows construction over the abstracted events, linking two activities whenever one is observed immediately after the other <ref:2607. p. 206873#pg2>.
V. TEST GENERATION
AGENTEVAL generates two kinds of test, functional tests and boundary tests <ref:2607.06873#pg2>. Functional tests are synthesized directly from the collected traces, without the graph, by replaying an observed workflow <ref:2607. p. 306873#pg2>. Boundary tests are guided by the workflow graph to stress guards at structural locations selected from it <ref:2607. p. 306873#pg2>.
VI. EVALUATION
To evaluate AGENTEVAL, we run the full system across all four τ3-bench domains to assess its effectiveness and generalization <ref:2607.06873#pg2>. The benchmark resolves the oracle problem with a privileged auditor that reads source code and acts as a ground-truth oracle for scoring the tester <ref:2607. p. 106873#pg2>.
VII. RELATED WORK
AGENTEVAL mines a behavioral model, which is not authored but induced from the system under test, allowing it to guide test generation <ref:2607.06873#pg2>. It also relates to model-based testing by using the conversational workflow graph as the dependency model that guides test generation <ref:2607. p. 906873#pg2>. AGENTEVAL’s answer is to separate the actor from the oracle and leave every verdict to a judge confined to the visible trace <ref:2607. p. 906873#pg2>.
Pruning redundant reasoning tokens
The paper presents AGENTEVAL, a black-box testing framework that discovers and stresses these stateful boundaries <ref:2607.06873#pg2>. The framework interacts with an agent to mine a conversational workflow graph, which is a model of its behavior <ref:2607. p. 006873#pg2>.
How the training signal is built
The conversational workflow graph is built using the directly-follows construction over abstracted events, linking two activities whenever one is observed immediately after the other <ref:2607.06873#pg2>. This graph's structure marks where boundaries can sit, and AGENTEVAL uses it to guide boundary testing by selecting a structural location and generating a test that stresses the behavior observed there <ref:2607.06873#pg2>.
Where the gains come from
Graph-guided generation yields 23–38 distinct boundaries per agent, which is nearly 2× the no-graph baseline, isolating structural target selection as the cause of increased coverage <ref:2607.06873#pg2>. The gain comes from targeting structural locations rather than merely supplying the graph as prompt context <ref:2607. p. 606873#pg2>.
AGENTEVAL uncovers a larger, more diverse set of critical boundaries than methods without such structural guidance, providing a repeatable foundation for regression testing these complex systems <ref:2607.06873#pg2>. The framework is designed to stress state-dependent workflow failures by mining a conversational workflow graph from observed interactions <ref:2607. p. 006873#pg2>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Black-box conversational agent testing framework AGENTEVAL can discover and stress state-dependent failures by mining a conversational workflow graph from observed interactions, overcoming the difficulty of testing hidden boundaries that are
hidden behind multiturn conversational prerequisites.
-
Graph-guided boundary testing allows AGENTEVAL to
determine structurally where boundaries can sit,
generating tests that probe and stress guards, limits, or recovery behaviors by selecting targets from every node, edge, entry activity, and terminal activity in the workflow graph. -
The system can generate functional tests by
replaying the successful workflows observed in the traces
and boundary tests by targeting specific structural locations likeNode an observed activity (v ∈ V)
to stress whetherthe agent guards, clarifies, or recovers when its required context is perturbed.
-
A new benchmark allows for scoring a black-box tester against the agent’s source code using a privileged auditor that reports metrics such as
distinct boundary count,
duplicate rate,
andfalse-alarm rate
based on whether a flagged failure is areal fault from the visible conversation alone.
-
The system can differentiate real faults from false alarms by having an execution-phase judge evaluate the resulting trace to return a verdict, distinguishing between faults that are
visible in the trace
and those that are not.
Sources
- $\tau$-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains
- $\tau^2$-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
Related papers
- ArkEval: Benchmarking and Evaluating Automated CodeRepair for ArkTS
- TestPrism: Rethinking Test Evaluation Beyond a Single Reference
- Falsification-Based Verification of LLM-Generated Optimization Models: Sound Test Batteries and Their Detection Limits
- GitSkills: A Dataset of Agent Skills on GitHub
- For Coding Agents, the Repository Matters
- SABER: Benchmarking Operational Safety of LLM Coding Agents in Stateful Project Workspaces