1 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]. However, conversational agents built on these models often fail, resulting in tangible real-world consequences [4], [5]. 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. A boundary that fails to hold changes the state of the system silently and often irreversibly: a booking canceled before the user confirmed it, an action taken for an unverified caller, a value accepted that should have been refused.

Most work on evaluating conversational LLM agents focuses on the underlying model’s capability, rather than the deployed system’s correctness: benchmarks such as \(\tau\)-bench and \(\tau^2\)-bench [3], [6], WebArena [7], GAIA [8], AppWorld [9], and SWE-bench [10] score how well a model plans and completes tasks in a fixed harness. The deployed agent, however, is the model combined with the prompts, policies, tools, and guardrails wrapped around it, and a change to any of these can silently break a workflow on the next release. What the deployer needs is ordinary software testing of the deployed agent: generate tests, run them, and report faults repeatably.

Testing these boundaries is hard. The agent is often a black box: reachable only through a conversational interface, with its internal prompts, tools, and state hidden [11]. If the testers do not have access to the internal state, they can see only the visible replies, and it is hard to tell where the boundaries are. These boundaries are also stateful, sitting behind multi-turn prerequisites: a confirmation gate, for instance, cannot be reached via a single prompt; the tester must carefully navigate the conversation to trigger it. Existing testing paradigms fall short: code-based tools require access to source code, crash logs, or specifications that the agent withholds, while black-box approaches either test for overall task success [12] or perturb single inputs [13], rather than stressing stateful guards. A tester cannot write a test plan for a workflow it cannot see; it must discover the boundaries by interacting with the agent, which leaves two questions the black box hides: where a boundary is and how to reach it.

Both questions are about the agent’s hidden workflow. Inspired by process mining, which mines a process model from event logs [14], we present AgentEval, a black-box conversational agent tester. AgentEval adopts the directly-follows graph [14], [15] to construct a conversational workflow graph from the unstructured turns of its conversations with the agent. In this model, nodes represent abstracted agent activities and edges carry the user actions observed between them. Figure 1 shows such a graph that AgentEval mined from the \(\tau^3\)-bench airline agent using only black-box interaction.

The graph’s structure marks where boundaries can sit, and its observed routes show how to reach them. AgentEval uses both for graph-guided boundary testing: it deterministically walks every structural location and asks an LLM for a test that stresses the guard, limit, or recovery behavior observed there, rather than prompting blindly. Because each test inherits its location’s route, the tester walks the conversation to the boundary before applying the perturbation, reaching the state-dependent behavior that a single prompt cannot. This also makes the boundary tests diverse, as covering every structural location spreads coverage across many distinct boundaries.

AgentEval runs in two phases. The Discovery phase begins by exploring the agent through a series of conversations to collect traces within a fixed interaction budget. It then synthesizes a test plan from these traces in two steps. First, it generates functional tests by replaying the successful workflows observed in the traces. Second, it induces the conversational workflow graph to guide the synthesis of boundary tests. The Execution phase then runs the plan. For each test, an LLM-driven runner re-enacts the conversation against a fresh session of the agent, following the required route to the target state. A separate judge then evaluates the resulting trace to return a pass, fail, or inconclusive verdict. The generated test plan is a reusable artifact for regression testing whenever the agent is updated.

To measure AgentEval’s effectiveness, we created a new benchmark. Our benchmark employs a privileged auditor that reads this source code and acts as the ground-truth oracle for scoring the tester. The auditor assesses each phase separately. For the Discovery phase, the auditor measures the plan’s validity rate by screening for ill-formed tests. For the valid tests, it then calculates two sets of metrics: for functional tests, it measures coverage recall against an inventory of documented behaviors; for boundary tests, it counts the number of distinct boundaries covered and calculates the duplicate rate, i.e.. the fraction of generated tests that redundantly target the same boundary. In the Execution phase, it analyzes test runs to distinguish real faults from false alarms and reports the false-alarm rate.

To our knowledge, this is the first benchmark to score a black-box tester of conversational agents against the agent’s own source code.

We instantiate the benchmark on the four \(\tau^3\)-bench agents. Rather than using \(\tau^3\)-bench’s own task-based scoring, we interact with the agents purely as black boxes, and for each, we hand-write a reference list of the behaviors of the agent. Two findings stand out. First, phase-guided discovery generates higher-quality tests than naive exploration, raising coverage recall from \(0.72\) to \(0.97\) in the airline agent. Second, the workflow graph is effective at driving boundary testing. Across all four agents, graph-guided generation yields \(23\)–\(38\) distinct boundaries per agent; in the airline agent, it yields \(23\) versus \(12\) with prompt-only generation, cutting the duplicate rate from \(0.56\) to \(0.26\) at near-zero false-alarm rates.

This paper makes three contributions.

1. A black-box conversational agent testing framework. We present AgentEval, which tests a deployed conversational agent using only its chat interface. It explores the agent, synthesizes a test plan of functional and boundary tests, executes the plan, and judges the outcomes based entirely on the resulting conversation, without ever inspecting the agent’s internals (Sections 3–5).

2. Graph-guided boundary testing. We adapt the directly-follows graph from process mining [15] to mine a conversational workflow graph from black-box conversations, employing an LLM to abstract raw conversation turns into discrete agent activities. Leveraging this structural model, we can generate targeted boundary tests that probe and stress the agent’s stateful boundaries (Sections 4 and 5.2).

3. A benchmark for black-box conversational agent testing. We design a benchmark for assessing black-box conversational agent testers. It pairs the tester with a privileged auditor who has white-box access to the agent’s source code and reports per-phase metrics: the test plan’s validity rate, functional coverage recall, distinct boundary counts, and execution false-alarm rates (Section 6).

2 Preliminaries↩︎

2.1 Interaction Model↩︎

Let \(A\) be the conversational agent under test. The tester has exactly two operations: \(\mathsf{reset}(A)\) starts a fresh session, and \(\mathsf{invoke}(A,u)\!\rightarrow\! r\) sends one user utterance \(u\) and returns the visible reply \(r\). Nothing else is observable: no prompts, no tool calls, no logs, no database state. A session trace (or simply trace) is the ordered sequence of turns \(\sigma=\langle(u_1,r_1),\ldots,(u_m,r_m)\rangle\), where each turn \((u_i,r_i)\) pairs a user utterance with the agent’s visible reply, and the number of turns \(m\) is bounded by a turn budget. A test is an executable objective: a goal (e.g., “cancel a reservation”), optional execution hints, observable success criteria, observable failure criteria, and a turn budget. Every test verdict must be justified by the trace alone.

2.2 Running Example↩︎

We use one running example throughout, drawn from the airline domain of \(\tau^3\)-bench [16]. The agent books, changes, and cancels flight reservations under a hidden policy, and the tester reaches it only through chat: it sends user messages and sees the agent’s replies, nothing else. In one exploration session, the tester poses as the customer, provides a user identifier, and asks the agent to list that customer’s reservations and cancel one. The agent returns the customer’s bookings and asks which one to cancel and why. The tester names the reservation Z7GOZK and provides a reason; the agent looks it up, reports that the booking is eligible for cancellation, and asks for explicit confirmation: “Shall I go ahead and cancel reservation Z7GOZK?” Only after the tester answers yes does the agent report the cancellation complete. In a second session, the tester asks to cancel a different booking; because that booking is ineligible, the agent refuses and explains the policy instead. From these visible replies alone, AgentEval abstracts each turn into an activity and induces the graph fragment of Figure 2. The confirmation step is a gate: in every observed session, the agent reaches confirm_completion only after the tester confirms at request_confirmation. The question that matters is whether the agent actually enforces that gate: whether it would still cancel if the tester answered yes before any confirmation was requested, or would push it to cancel the booking it had just refused as ineligible. Reaching that question means first walking the conversation to the gate and only then applying the perturbation, which is exactly what graph-guided boundary testing is built to do.

2.3 Fault Model↩︎

We target workflow faults: behaviors that violate the rules a service workflow is expected to enforce. Most involve the agent acting past a guard: it cancels a booking before presenting eligibility or before the user confirms, accepts a reservation code it has already rejected, or claims to complete a modification it never performed. What makes these faults hard to find is that each appears only at a particular workflow state and only when a specific input or precondition is perturbed. A fault is in scope only if it is visible in the trace; behavior that never surfaces in the agent’s text is out of reach for AgentEval and for any black-box method.

2.4 The Conversational Workflow Graph↩︎

A conversational workflow graph is the model AgentEval builds of an agent’s workflow from visible session traces alone. We build it as a directly-follows graph, one of the standard process-mining discovery algorithms [14], which links two activities whenever one is observed immediately after the other [15]; Section 4 gives the construction. We choose it for two properties that fit black-box testing: it is built deterministically by frequency counting, with no search or tuning, so AgentEval can build it efficiently once discovery has collected its traces; and it reads like a flowchart whose activities and transitions are easy to enumerate and target. The deeper structure that the graph cannot capture is left to AgentEval’s LLM-driven components, as later sections describe. Formally, \[\mathcal{G}=(V,\,E,\,S,\,T).\] \(V\) is the set of observed activity states: the recurring agent behaviors seen across the traces, each given a short label such as request_confirmation or confirm_completion in Figure 2. Each state records its support, the number of observed agent replies mapped to it. \(E\subseteq V\times V\) is the set of observed transitions: an edge \((v,v')\) exists whenever some trace moves from activity \(v\) at one turn to activity \(v'\) at the next. Each edge records its frequency, how often that succession was seen, and the user actions that drove it: the user’s labeled moves in between, such as an intent, a value, or a continuation like confirm. \(S\) and \(T\) collect the activities seen first and last in a session, the graph’s entry points and terminal states. A transition is replayable when its user actions can be re-issued verbatim in a fresh session; in Figure 2 every solid edge is replayable. This matters because a non-entry state, one that is not an entry point and so appears only partway through a session, can be reached only by replaying the observed user actions that lead to it. The model does not mark which states act as gates or which change state, because that is not observable from the replies (Section 4 explains why).

2.5 Assumptions↩︎

AgentEval assumes the agent can be reset to a fresh session, a standard requirement for automated testing environments; that interaction is budget-bounded, so the goal is effective testing rather than exhaustive learning; and that the agent exhibits recurring interaction patterns (routing, slot filling, validation, and confirmation) for the graph to capture, as is typical for conversational agents executing structured workflows.

3 Approach Overview↩︎

Figure 4 shows the AgentEval pipeline, including two phases: discovery and execution. Discovery explores the agent over \(R_{\mathrm{disc}}\) rounds, where each round is one fresh session that yields a single trace of at most \(B_{\mathrm{turn}}\) turns. It induces the workflow graph and then synthesizes the test plan from the collected traces. Execution drives each test turn by turn with the agent and judges the resulting trace. Discovery is paid once: the resulting plan is a reusable artifact that execution re-runs whenever the target agent’s code or model changes, verifying that the updated agent still passes the plan’s tests, as in CI/CD regression testing.

3.1 Phase-Guided Discovery↩︎

Discovery is a planner–driver loop over fresh sessions, both LLM-driven: in each round, the planner decides what to explore and the driver carries it out by conversing with the agent. At the start of a round, the planner sets an exploration phase (the kind of exploration to run), an objective (the goal the session should reach), and a strategy (a short tactical plan for how the driver pursues that goal). AgentEval defines three kinds of exploration phases, each with a default objective and strategy. Capability discovery maps what the agent says it can do and what inputs it requires. Happy-path carries one ordinary workflow through to completion, so the trace records its full path rather than only the entry steps. Consistency check repeats a previously observed request, verbatim or lightly rephrased, and checks whether the agent asks for the same information and reaches the same outcome.

To ensure broad coverage before probing deeper, discovery begins with a predefined warm-up schedule: it executes \(m_{\mathrm{cap}}\) capability-discovery sessions, then \(m_{\mathrm{hp}}\) happy-path sessions, then \(m_{\mathrm{cc}}\) consistency-check sessions. In these warm-up rounds, the phase follows the warm-up schedule and the objective and strategy are the phase defaults. The planner makes no LLM call in these rounds. Afterward an LLM planner reads the traces collected so far and which phases it has already covered, then writes the phase, objective, and strategy itself, choosing a behavior not yet well represented in the traces.

In every round the driver, which is also driven by an LLM, executes the strategy in a fresh session, generating and sending one plain user message per turn through \(\mathsf{invoke}\) and stopping when the objective is met or the turn budget is reached.

Discovery stops when the round budget is exhausted. Once discovery stops, AgentEval’s test generators synthesize a test plan from the collected traces. The plan contains two kinds of test, functional tests and boundary tests. Functional tests are synthesized directly from the collected traces, without the graph: each replays an observed workflow (Section 5.1). Boundary tests stress the guards a workflow enforces—confirmation gates, eligibility checks, value validation—at structural locations selected from the workflow graph induced from those same traces (Section 5.2).

3.2 Execution↩︎

Execution runs each test in the plan as an isolated session: an LLM driven runner resets the agent to a clean state, then reads the test’s goal and hints and issues one user message at a time, adapting to the agent’s replies, up to the test’s turn budget. A separate judge then reads the whole session trace and returns a verdict against the test’s visible criteria: pass when the trace satisfies the success criteria and avoids the failure criteria, fail when it violates a success criterion or triggers a failure criterion, and inconclusive when the trace does not settle whether those criteria were met, for example when a prerequisite was never reached or the turn budget ran out. The judge makes its verdict independently of the runner and the test generator. Figure 7 shows one functional test and one boundary test, including the goal, hinted user turns, and pass and fail criteria that the runner and judge act on.

4 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]. In our setting, a case is a single session trace, and its events are the user utterances and agent replies. One difference separates our setting from classic process discovery: these events are natural language, so AgentEval must abstract them into user actions and activity states before counting. This section describes how AgentEval abstracts trace events and builds the graph from the collected traces once discovery has finished; the graph in Figure 1 is what this procedure produces.

4.1 Event Abstraction↩︎

Raw wording is unstable: “What is your reservation code?”, “Could you give me the booking reference?”, and “Please provide the confirmation number” may express the same activity. Process mining faces the same problem when low-level events are too fine-grained to mine [17], [18]; AgentEval abstracts each turn before counting. A single LLM pass reads the collected sessions and labels each turn with a user action, an agent activity, and a one-sentence summary. A user action is a step taken by the user, such as requesting cancellation, providing a booking reference, or answering “yes”. An agent activity is the visible workflow state the reply created, such as request_confirmation or confirm_completion. Turns that differ only in wording, like the three phrasings above, are surface variants of one activity. The model produces labels that fit the trace and assigns the same label to all surface variants of an activity; because the mining step creates one node per distinct label (Section 4.2), these variants map to a single activity state (Figure 5).

4.2 Graph Construction↩︎

Once discovery has finished, AgentEval builds \(\mathcal{G}\) from all collected session traces by the standard directly-follows construction over the abstracted events (Algorithm 6). Each distinct agent activity becomes a node, carrying its support. Whenever one activity directly follows another within a session, AgentEval adds the edge between them or reinforces it, carrying its frequency and the user actions that drove it; this is the directly-follows relation that defines the graph. The first and last activities of each session are recorded as entry and terminal states. The user actions along an observed path from the session start to an activity \(v\) form a route to \(v\), which is replayable when those actions can be re-issued in a fresh session; in Figure 2, the route to request_confirmation is to list the reservations, give the cancellation details, and continue through the presented eligibility. The graph is built exactly once from the full trace set; its only consumer is the boundary-test generator in Section 5.2.

5 Test Generation↩︎

AgentEval generates two kinds of test, both LLM-generated and grounded in the discovery traces: functional tests synthesized directly from them, and boundary tests guided by the workflow graph.

Figure 7 shows one generated test of each kind, both drawn from the running example’s cancellation workflow and both using the schema of Section 2. They differ in what they test: the functional test (top) checks that the agent completes the multi-turn workflow correctly, while the boundary test (bottom) perturbs a single step—requesting reservation details before any lookup has fixed which reservation—and passes only when the agent visibly asks for the missing context.

5.1 Functional Test Synthesis↩︎

AgentEval builds functional tests with an LLM in a series of rounds. In each round the LLM reads the raw discovery traces and proposes a small batch of new tests, each replaying a workflow the agent was seen performing; AgentEval adds rounds up to a cap of \(N_f\) tests and stops early once new tests stop appearing. Every test follows the schema of Section 2, and AgentEval fills it entirely from the traces rather than inventing anything: the goal is the workflow being replayed, the hints are the user messages that drive it, and the pass and fail criteria come from the outcome the trace shows. Every concrete value a test names—an identifier, a date, a status, an expected result—is copied from a quoted trace turn or a benchmark-provided seed. Across rounds, AgentEval carries forward the tests it has already accepted so the LLM does not repeat them.

5.2 Graph-Guided Boundary Test Synthesis↩︎

Boundary value analysis perturbs the inputs of a single call [11], [19], and classic robustness testing deliberately excludes state [20]. A conversational agent’s most dangerous boundaries are instead stateful: the confirmation gate, the slot that validates an identifier, the prerequisite that must precede an action. AgentEval targets these workflow boundaries directly: it selects a location in the observed graph and generates a test that stresses the behavior observed there, without any fixed catalog of perturbations (Algorithm 8).

Target selection. AgentEval deterministically enumerates one boundary target per structural location of the graph: every node, every edge, every entry activity, and every terminal activity (Table 1). Each target inherits the support and user actions of its location, plus a fixed description of what perturbing near it can test. Because a full graph usually yields more targets than a test budget (i.e.., the cap on how many boundary tests to generate) allows, AgentEval asks an LLM to score each target’s boundary potential: a value in \([0,1]\) estimating how likely stressing that location is to expose a guard, limit, prerequisite, or recovery behavior worth testing. The LLM reads the behavior observed at the target—the agent activity and user actions there—and scores it high when that behavior already shows a guarded or stateful step, such as a confirmation, an eligibility check, or a required input, and low when it shows an ordinary step with nothing to stress. AgentEval keeps the highest-scoring targets within the budget, each with a concise label indicating the boundary it would stress (for example, cancel without confirmation at the cancellation gate).

Boundary test generation. For each selected target, an LLM generates boundary tests that perturb the workflow near that location, for instance requesting an action while skipping a prerequisite, supplying an incomplete or ambiguous value, attempting a premature continuation, or continuing after an observed end. The boundary test in Figure 7 is one such case at the show_reservation_details activity: its single perturbation requests that activity—“show me the details of my reservation”—before any lookup has fixed which reservation, the prerequisite context the activity normally has. Each test expects an observable response, the agent limiting, clarifying, protecting, correcting, or recovering rather than silently proceeding past the stressed condition; the figure’s test passes only if the agent asks which reservation or offers to look one up, and fails if it reveals details for an unspecified booking. Each generated test must stress a boundary rather than merely walk an ordinary successful workflow.

Because AgentEval covers every structural location rather than the few salient flows a free-form prompt tends to repeat, the generated boundary tests spread across the whole graph, which Section 6 measures as a lower duplicate rate and a higher distinct-boundary count.

6 Evaluation↩︎

To evaluate AgentEval, we run the full system across all four \(\tau^3\)-bench domains to assess its effectiveness and generalization, and conduct ablation studies on the airline domain to isolate which parts of the system contribute. Every result we report comes from a privileged LLM auditor, whose model we select in the setup (Section 6.3); we then ask five questions of the method: how effective is its functional and boundary testing, where does the boundary gain come from, whether the judge behind every verdict is reliable, and what it all costs.

1. RQ1 (Functional Testing Effectiveness). Across the four domains, how valid and complete are the functional tests AgentEval synthesizes, and does phase-guided exploration improve them over naive exploration?

2. RQ2 (Boundary Testing Effectiveness). Across the four domains, how many distinct, valid boundaries does graph-guided generation cover, and at what duplicate, invalid, and false-alarm rates?

3. RQ3 (Ablation on Workflow Graph). Does the boundary-testing gain come from the graph’s structural target selection, or merely from supplying the graph as prompt context?

4. RQ4 (Judge Reliability). Does AgentEval’s execution-phase judge reliably tell a real fault from correct behavior, from the visible conversation alone?

5. RQ5 (Efficiency). What do AgentEval’s discovery, functional, and boundary stages cost in LLM calls, tokens, and wall-clock time?

6.1 Configurations↩︎

The full-system results (Table 3) run every component at once: phase-guided discovery, trace-only functional synthesis, and graph-guided boundary testing. To attribute the gains, we ablate the functional and boundary stages separately on the airline domain, each with its own set of configurations.

Functional testing configurations vary only the discovery strategy and are scored on the functional plan (Table 4). Naive uses naive, unguided discovery; Phase-guided uses the phase-guided discovery of Section 3.1.

Boundary testing configurations all build on phase-guided discovery and vary only in how the workflow graph informs boundary generation, scored on the boundary tests (Table 5). Prompt-only generates boundary tests by prompting from the traces alone, with no graph. Graph-context builds the graph but feeds it to the generator only as a textual summary inside the prompt. Ours generates a boundary test at each structural location enumerated from the graph (Section 5.2).

6.2 Benchmark Design↩︎

An asymmetric oracle. Scoring a black-box tester is itself an oracle problem: seeing only the chat interface, the tester cannot certify that its own tests are valid or that a flagged failure is a real fault. The benchmark resolves this with a privileged auditor that sees everything the tester sees and more—the same conversations, plus the subject’s source code, a trace of its tool calls, and a fixed functionality inventory (a list of documented behaviors the target agent should support). The asymmetry is one-way: these privileged inputs never reach the tester, whose workflow graph and boundary targets come solely from visible text. The auditor’s judgments therefore serve as an independent ground truth, and it scores both the test plan from discovery and the run results from execution.

Discovery-phase metrics. For \(T\) generated tests with valid subset \(T_v\), the validity rate \(|T_v|/|T|\) is the fraction the auditor accepts; it is reported for both functional and boundary tests under a kind-specific criterion: a functional test is valid if it is grounded, actionable, and covers at least one inventory item; a boundary test if it describes a real boundary (not an ordinary success path) whose expected and forbidden behaviors are decidable from the trace and grounded in the scenario. For the valid functional tests, coverage recall \(|C|/|\mathcal{I}|\) is the fraction of the documented-behavior inventory \(\mathcal{I}\) they cover. Boundary tests have no fixed catalog, so for the valid ones the auditor extracts a boundary card \((c,g,p,e,f)\) from each—capability, stressed guard, perturbation, expected behavior, forbidden behavior—and clusters cards describing the same boundary: two match only when they share the same \(c\), \(g\), \(p\), and \(e\), compared semantically so paraphrases merge and conservatively so ambiguous pairs stay separate. The number of resulting clusters is the distinct-boundary count \(|U|\), and the duplicate rate is \(1-|U|/|T_v|\).

Execution-phase metrics. For both functional and boundary tests, the auditor labels each valid test’s run against the agent’s source code as TP (the run flagged a failure, and the trace shows a real fault caused it), FP (the run flagged a failure, but the agent was actually correct), TN, FN, or inconclusive (the run did not test the target behavior—the state was never reached, the turn budget ran out, or the target agent errored at runtime; a judge-inconclusive run is inconclusive here too). From these it reports the false-alarm rate \(\mathrm{FAR}=\mathrm{FP}/(\mathrm{FP}+\mathrm{TN})\), accuracy \(\mathrm{Acc}=(\mathrm{TP}+\mathrm{TN})/N\), and inconclusive rate \(\mathrm{Inc}=\mathrm{INC}/N\) (with \(N=\mathrm{TP}+\mathrm{FP}+\mathrm{TN}+\mathrm{FN}+\mathrm{INC}\)).

6.3 Setup↩︎

We evaluate on the four text domains of \(\tau^3\)-bench [16]: airline, retail, and telecom from \(\tau^2\)-bench [6], and banking from \(\tau\)-Knowledge [21].We use these environments only as black-box targets; we do not run \(\tau^3\)-bench’s official tasks, user simulators, or reward functions, and none of that machinery is visible to the tester. The functionality inventory is written from each domain’s policy and tool documentation, yielding \(39\) items for airline, \(31\) for retail, \(30\) for telecom, and \(45\) for banking (\(145\) in total). The tester and its judge run MiMo-v2.5-pro; the auditor runs GLM-5.2, a different model family selected based on the comparison below; the subject agent runs DeepSeek-v4-flash, a fast and reliable model. Using distinct families is deliberate: the auditor differs from the tester so the audit is not a self-evaluation, and the subject is independent of both. All roles are served over an OpenAI-compatible API at temperature \(0\). We set \(R_{\mathrm{disc}}=12\) discovery rounds; \(B_{\mathrm{turn}}=6\) turns per session; a phase warm-up of \(m_{\mathrm{cap}}=1\) capability-discovery, \(m_{\mathrm{hp}}=2\) happy-path, and \(m_{\mathrm{cc}}=1\) consistency-check sessions before free phase choice; and a target of \(N_f=50\) functional tests, plus an additional \(N_b=50\) boundary tests for boundary-enabled configurations. We fixed these values to balance coverage against experimentation cost (LLM calls and wall-clock time).

Auditor model. Because every reported number comes from the auditor, we deliberately select its model. We hold one discovery run and its replayed tests fixed (airline, \(26\) scenarios) and swap only the auditor model, re-running the coverage audit each time; each candidate reads the agent’s source code and documented-behavior inventory and decides which items the scenarios cover. We score each by agreement with an expert human reference—the Jaccard overlap of the two covered-item sets (Table 2)—and adopt GLM-5.2, which agrees most closely (\(0.94\)) and matches the expert’s coverage recall (\(0.82\)) exactly.

6.4 Results↩︎

RQ1: Functional testing effectiveness across domains. Table 3 reports, for the full system on each domain, the size of the mined graph and the quality of the trace-only functional plan. Black-box exploration recovers each domain’s principal workflows as graphs of \(46\)–\(153\) activities (Figure 1 shows an airline excerpt). The trace-only functional generator produces a high fraction of valid tests everywhere (validity rate \(0.91\)–\(1.00\)); inventory coverage (\(\mathrm{CovRec}\)) spans \(0.53\)–\(1.00\), high on the transactional airline and retail domains, mid on telecom, and lowest on the knowledge-heavy banking domain. Functional false-alarm rates stay low (\(\mathrm{FAR}\) \(0.00\)–\(0.07\)): on a mostly-correct agent the run audit almost never misattributes a passing interaction as a real functional fault, so the functional suite is trustworthy. Discovery strategy itself matters: on the airline domain, phase-guided exploration produces a far better functional plan than naive exploration (Table 4), raising coverage recall from \(0.72\) to \(0.97\) at unchanged validity (\(1.00\)).

RQ2: Boundary testing effectiveness across domains. Table 3 also reports the full system’s graph-guided boundary pass. With a budget of \(50\) boundary tests per domain, AgentEval covers \(23\)–\(38\) distinct boundaries, at duplicate rates of \(0.16\)–\(0.26\), validity rates of \(0.78\)–\(0.98\), and false-alarm rates of \(0.00\)–\(0.09\) on the unmodified agent. The result holds across very different agents—transactional booking (airline, retail), manual-policy support (telecom), and knowledge retrieval (banking)—each yielding a large, low-duplicate, low-false-alarm boundary suite whose distinct-boundary count tracks the size and branching of its mined graph. The lower boundary validity on airline and retail (\(0.78\) and \(0.79\), vs.\(0.97\) and \(0.98\) on telecom and banking) is a synthesis limitation rather than a testing failure: the generator is instructed to bind each boundary scenario to one real customer whose data state matches the boundary, drawn from the same golden session, but the model does not consistently honor this and pairs the authenticated caller with an order or reservation that belongs to a different customer. The identity-aware validity auditor catches the mismatch—a correct agent would refuse to act on another user’s record, leaving the boundary unreachable—and marks these scenarios invalid, which accounts for most of the invalid boundary tests in the two transactional domains.

RQ3: Ablation on the workflow graph—what about it drives the gain? Table 5 ablates boundary generation on the airline domain, varying only how the graph is used. With no graph, prompting the generator from the traces yields \(12\) distinct boundaries at a high duplicate rate (\(0.56\)): a free-form prompt clusters on a few salient flows and repeats them. Supplying the same mined graph as a textual summary in the prompt (Graph-context) lowers duplication (to \(0.40\)) but yields no more distinct boundaries (\(9\)) than the no-graph baseline—a free-form prompt still treats the graph as loose context. Only when the graph’s structural locations become explicit boundary targets (Ours) does coverage jump, to \(23\) distinct boundaries at the lowest duplicate rate (\(0.26\)), nearly \(2\times\) the no-graph baseline. Because Graph-context and Ours build an identical graph, this jump isolates the cause: the gain comes from the structural target selection of Section 5.2, not from the mere presence of a graph. False-alarm rates stay near zero throughout (\(0.04\), \(0.00\), \(0.00\)), so the gain incurs no loss of trustworthiness.

RQ4: Judge reliability. Every verdict in the results above is the execution-phase judge’s call, read from the visible trace alone, so we check that this judge tells a real fault from correct behavior, testing it on two fault classes. For process and guard violations, we seed faults by minimally editing a single agent turn of a passing recorded run so the reply acts before confirmation, proceeds without establishing identity, grants an action whose precondition is unmet, or accepts an invalid value, then replay the mutated trace through the same judge; a fault is caught when the judge fails the run, and the unmodified traces are the false-alarm control. Across \(27\) such faults on airline scenarios—the validity audit confirms each surfaces in the agent’s words—the judge catches \(22\) (\(0.81\); Table 6) at a low false-alarm rate on the controls, showing high sensitivity to violations that surface in behavior. For value and accuracy faults—a wrong fare, amount, or status, which need not read as a policy violation—we inject the fault live into the running agent rather than by editing a transcript: we corrupt the value a lookup tool returns (a reservation’s insurance status, a stored or searched fare, a flight status) and let the real agent relay it, replaying each test with its golden reference recorded so the judge compares the reply against the expected value instead of verifying it. All four mutants are killed (Table 7): for each one, a test that passed on the unmodified agent fails on the mutated agent, and the auditor confirms the injected fault caused the failure. Recording the expected value in the test plan thus makes value and accuracy faults detectable. How often a mutant is caught depends on how directly its corrupted value reaches the user: an inflated search fare, which the agent quotes to the user as the booking price, is caught in \(8\) of \(14\) relevant tests, whereas a doubled stored reservation price is caught in only \(1\) of \(10\), because the agent quotes the wrong figure but then executes the change by reading the true stored price (the mutation only alters what the lookup returns, not what the database stores), recomputing the correct total, so the outcome the test checks is usually right.

RQ5: Efficiency. Table 8 reports the cost of the airline ablation. The Naive baseline makes \(142\) LLM calls and consumes \(0.60\)M tokens; the full system (Ours) makes \(285\) calls and consumes \(1.55\)M tokens in roughly two and a half hours, with the boundary pass accounting for most of the increase and the graph induction adding only a single labeling pass over the collected traces. Read per distinct boundary, Ours is the most economical boundary generator, at roughly \(67\)K tokens per distinct boundary, against \(108\)K for Prompt-only and \(149\)K for Graph-context, which yields the fewest distinct boundaries for comparable cost; structural targeting spends its budget on distinct boundaries rather than duplicates.

6.5 Threats to Validity↩︎

Construct. Every metric comes from the LLM auditor, so an unreliable auditor would corrupt them all. We run it on a different model family from the tester (GLM-5.2 vs.. MiMo-v2.5-pro) to avoid self-audit bias, and validate its coverage audit against an expert reference (Section 6.3); its run-audit labels behind \(\mathrm{FAR}\) are not independently validated, however, so residual auditor error there remains a threat that a human-validated label sample would address. The distinct-boundary count relies on LLM-proposed same-boundary clusters the code then counts deterministically; stricter independent pairwise judgments are left to future work.

Internal. The numbers are from a single run per configuration, so small differences (for instance, the few-point spread in functional coverage recall) should not be overread; the boundary-count gap, by contrast, is large, and the duplicate rate falls monotonically across the ablation (\(0.56\), \(0.40\), \(0.26\)). The Graph-context variant and Ours AgentEval share the same mined graph, discovery, and budget, and differ only in whether the graph is passed as prompt text or used to enumerate targets structurally; that Ours still wins isolates structural target selection as the cause.

External. We study four \(\tau^3\)-bench text domains, all of which are tool-using service agents driven by a single model family; other architectures, modalities, and non-service domains may differ. AgentEval also assumes a recurring interaction structure (routes, slots, validation, confirmation gates) that is observable in bounded traces; for highly open-ended or non-repeatable agents, the mined graph may remain thin, yielding fewer boundary targets than a trace-only baseline.

Oracle scope. AgentEval’s run oracle judges only the visible conversation, as a deployed black-box tester must, so faults that never surface there are out of reach by construction. Our seeded-fault study makes this concrete: mutants that corrupt backend state while the reply stays correct—a tool that silently alters a refund amount—pass the oracle even though the privileged auditor confirms a real fault, so seeded-fault validation is meaningful only for faults visible in behavior.

7 Related Work↩︎

Evaluating and testing LLM agents. Agent benchmarks rank model capability on fixed task suites with programmatic or simulated-user scoring [3], [7]–[10], [22]. Closer to testing, TRACE evolves benchmark tasks under a validate-by-reproduce oracle [23], TestAgent sequences follow-up probes adaptively [24], and Graph2Eval seeds agent tasks from an external knowledge graph [25]; LLMs have also been used to reverse-engineer black-box systems [26]. These explore or adapt tasks, but none first induces a behavioral model of the agent under test and then tests systematically against it. AgentEval does both: it discovers the agent by interaction, synthesizes tests from the mined model, and judges each run with an oracle that reads only the conversation.

Mining behavioral models. AgentEval’s graph is a mined behavioral model. Specification mining infers models from execution traces [27], [28], including state-machine inference such as GK-tail and CSight [29], [30]; process mining discovers process models from event logs [14], [31], [32], with directly-follows graphs the pragmatic workhorse [15]—which can imply paths never observed as full traces—on which we build, alongside event abstraction for low-level logs [17], [18]. The name workflow graph also denotes a design-time business-process formalism [33]; ours has the opposite provenance, induced from the running system’s traces. Active automata learning reconstructs machines through membership and equivalence queries [34] that a conversational target does not answer, while dialog-structure induction and user simulators build models from conversations for analysis, training, or evaluation [35]–[38]. All of these mine a model to describe behavior; AgentEval mines one to act on it—generating tests, replaying routes to target states, and stressing them under a tester that chooses what to observe next.

Model-based and stateful API testing. Model-based testing derives tests from behavioral models [39], but those models are typically authored and serve as the test oracle; ours is mined from the system under test, so it can guide test generation but cannot itself judge correctness. Our prerequisite routes correspond to the transfer sequences, or preambles, that FSM conformance testing uses to drive a stateful system into the state under test [40], [41]. Stateful REST API testing infers operation dependencies to build executable sequences: RESTler from specifications [42], EvoMaster by search [43], Morest with an execution-refined property graph [44], and KAT with LLM-built dependency graphs [45]; see Golmohammadi et al.for a survey [46]. The conversational workflow graph serves as the dependency model, but is mined from natural-language conversations, and its routes replay user actions rather than API calls.

LLM test generation, oracles, and boundary testing. LLM-based test generators validate candidates against executable signals—compilation, coverage, a crashing oracle—and repair the rest: TestPilot [47], CoverUp [48], ChatTester [49], CodaMosa [50], and TestART [51]. A black-box conversational agent exposes none of these signals, so the oracle problem [52] is acute: classical pseudo-oracles need an independent implementation or checker [53], [54], LLM-as-judge is biased [55], and intrinsic self-correction is unreliable without external grounding [56]–[59]. AgentEval’s answer is to separate the actor from the oracle and leave every verdict to a judge confined to the visible trace—the weak black-box analogue of a pseudo-oracle. For the perturbations themselves, boundary value analysis targets the edges of input domains [11], [19], robustness testing perturbs single calls while excluding state [20], and metamorphic testing relates outputs when no oracle exists [60], while prompt-injection studies motivate one family of perturbation [61], [62]; AgentEval lifts the boundary idea from input edges to workflow-state preconditions, which is precisely where conversational agents fail.

8 Conclusion↩︎

We presented AgentEval, a black-box testing framework for conversational LLM agents that targets state-dependent workflow failures. To overcome the inaccessibility of hidden boundaries like confirmation gates, AgentEval mines a conversational workflow graph from observed interactions. It then uses this graph’s structure to guide the generation of tests that replay conversational paths to these boundaries before applying targeted perturbations. We find that 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.

Data Availability↩︎

The code, prompts, and data used in this paper will be made available upon acceptance.

Acknowledgements↩︎

This work has emanated from research jointly funded by Taighde Éireann – Research Ireland under Grant Number. 13/RC/2094_2, and by Genesys Cloud Services, Inc.

References↩︎