arXiv CSopen access

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

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

Liting Lin

Yuzhong Zhang

arXiv:2607.06873v1 [cs.SE] 8 Jul 2026

Lero, the Research Ireland Centre for Software Lero, the Research Ireland Centre for Software The Chinese University of Hong Kong, Shenzhen University of Limerick, Ireland University of Limerick, Ireland China [email protected] [email protected] [email protected]

Lionel Briand

David-Paul Niland

Emir Muñoz

Lero, the Research Ireland Centre for Software University of Limerick, Ireland University of Ottawa, Canada [email protected]

Genesys Ireland [email protected]

Genesys Ireland [email protected]

Abstract—Conversational LLM agents can cause real-world harm when their internal workflows fail, such as completing a transaction without confirmation. 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. We present AGENT E VAL, a black-box testing framework that discovers and stresses these stateful boundaries. AGENT E VAL interacts with an agent to mine a conversational workflow graph, a model of its behavior. Instead of prompting blindly, AGENT E VAL uses this graph’s structure to enumerate specific guards and prerequisites as test targets, replaying the conversational path to a boundary before applying a perturbation. AGENT E VAL then executes each test, determining whether it passes or fails using only the conversation turns. We benchmark AGENT E VAL against a privileged, white-box auditor with access to the agent’s underlying source code, which AGENT E VAL never sees. On four τ 3 -bench agents, AGENT E VAL successfully generates tests covering 23–38 distinct boundaries per agent; ablation studies attribute the gain to the graph’s structure: 23 distinct boundaries versus 12 with a prompt-only baseline, at lower duplicate and false-alarm rates.

I. I NTRODUCTION 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 τ -bench and

τ 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 multiturn 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 blackbox 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 AGENT E VAL, a black-box conversational agent tester. AGENT E VAL adopts the directlyfollows 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 AGENT E VAL mined from the τ 3 -bench airline agent using only black-box interaction. The graph’s structure marks where boundaries can sit, and

no availability

request_ present_ dates search_flights select booking_details booking_details

Booking

confirm

confirm_ booking

k

boo

Cancellation

describe_ list_ supported_tasks cancel reservations

details

present_ eligibility

confirm

confirm_ cancellation

details

present_mod. confirmation

confirm

confirm_ modification

mo dif y

Modification

request_ modification

Fig. 1. Excerpt of a conversational workflow graph AGENT E VAL induced from the τ 3 -bench airline agent by black-box, text-only exploration (46 activities and 54 transitions in the full graph; the booking, cancellation, and modification workflows are shown). Nodes are LLM-induced activity labels (abbreviated) and edges are labeled with the observed user action; amber nodes are confirmation gates, and the rightmost confirm_* states are observed completions.

its observed routes show how to reach them. AGENT E VAL 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 statedependent behavior that a single prompt cannot. This also makes the boundary tests diverse, as covering every structural location spreads coverage across many distinct boundaries. AGENT E VAL 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 AGENT E VAL’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 falsealarm 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 τ 3 -bench agents. Rather than using τ 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 AGENT E VAL, 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 III–V). 2) Graph-guided boundary testing. We adapt the directlyfollows 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 IV and V-B). 3) A benchmark for black-box conversational agent testing. We design a benchmark for assessing blackbox 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 VI).

list_reservations cancel details

e bl

gi

eli in

present_eligibility

premature confirm?

request_confirmation

deny_and_ explain_policy

confirm

confirm_completion

observed

perturbation

cancel anyway? gate

Fig. 2. A workflow-graph fragment AGENT E VAL induces from the τ 3 -bench airline agent (real activity labels, abbreviated). Solid edges are observed transitions labeled with the user action or condition that caused them; the shaded (amber) node is a confirmation gate. The two dashed edges (premature confirm? and cancel anyway?) are boundary perturbations that tests will attempt, not observed transitions; deny_and_explain_policy is the observed branch for an ineligible reservation.

II. P RELIMINARIES A. Interaction Model Let A be the conversational agent under test. 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. 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 σ = ⟨(u1 , r1 ), . . . , (um , rm )⟩, where each turn (ui , ri ) 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. B. Running Example We use one running example throughout, drawn from the airline domain of τ 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, AGENT E VAL 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. An example session trace σ: u1 : “Hi, I’m olivia_gonzalez_2305. List my reservations and cancel one.” r1 : “You have Z7GOZK, K67C4W, and THY2DG. Which should I cancel, and why?” u2 : “Cancel Z7GOZK; my plans changed.” r2 : “Reservation Z7GOZK is eligible to cancel. Shall I go ahead and cancel it?” u3 : “Yes.” r3 : “Done. Reservation Z7GOZK has been canceled.”

C. 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 AGENT E VAL and for any black-box method. D. The Conversational Workflow Graph A conversational workflow graph is the model AGENT E VAL 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 IV 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 AGENT E VAL 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 AGENT E VAL’s LLM-driven components, as later sections describe. Formally, 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 ⊆ V × 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

1

Discovery

Execution

2

synthesis

exploration

Test Test plan

×𝑅!"#$

Functional synthesizer Sec. V-A

interact

target agent black box

planner

driver

Sec. III-A

traces

target selection

workflow graph

boundary synthesizer

Sec. IV

Sec. V-B

functional tests cancel reservation modify booking for each … boundary tests skip confirm gate override eligibility …

· goal: … · step_hints: … · success criteria: … · failure criteria: …

Results ✓ pass ✗ fail

~ inconclusive one verdict per test

runner

traces

judge

Sec. III-B

Fig. 3. AGENT E VAL overview, in two phases that share the black-box agent. Discovery explores the agent over Rdisc rounds and collects traces. From those traces AGENT E VAL synthesizes functional tests directly and induces the workflow graph; the graph then drives boundary-test synthesis. Execution drives each test turn by turn with the agent and makes a judgment from the resulting session trace. The LLM generates labels and tests; a separate judge decides each verdict from the trace.

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 IV explains why). E. Assumptions AGENT E VAL 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. III. A PPROACH OVERVIEW Figure 3 shows the AGENT E VAL pipeline, including two phases: discovery and execution. Discovery explores the agent over Rdisc rounds, where each round is one fresh session that yields a single trace of at most Bturn 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. A. 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). AGENT E VAL 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 mcap capability-discovery sessions, then mhp happy-path sessions, then mcc consistency-check sessions. In these warmup 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 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, AGENT E VAL’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 V-A). Boundary tests stress the guards a workflow enforces— confirmation gates, eligibility checks, value validation—at structural locations selected from the workflow graph induced

surface variants

raw turns

workflow activities

user: “I’d like to cancel a flight.”

request_cancellation

user action

agent: “What is your reservation code?” agent: “Could you give me the booking reference?”

agent activity request_reservation_code

agent: “Please provide the confirmation number.”

Fig. 4. Event abstraction maps each turn to a user action (from the user utterance) and an agent activity (from the agent reply). Differently worded replies that express the same activity (surface variants) receive the same agentactivity label and merge into one node.

from those same traces (Section V-B).

Algorithm 1 Constructing the conversational workflow graph Require: abstracted traces Σ; each trace is a turn sequence ⟨(a1 , u1 ), . . . , (am , um )⟩ of agent activity ai and user action ui Ensure: graph G = (V, E, S, T ) with per-node support and per-edge frequency and user actions 1: V, E, S, T ← ∅ 2: for each trace σ ∈ Σ with m turns do 3: for i ← 1 to m do 4: add ai to V ; increment its support 5: end for 6: for i ← 1 to m − 1 do 7: add edge (ai , ai+1 ) to E; increment its frequency 8: add ui+1 to the edge’s user actions 9: end for 10: add a1 to S (entry); add am to T (terminal) 11: end for 12: return G = (V, E, S, T )

B. 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 5 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. IV. M INING THE C ONVERSATIONAL W ORKFLOW G RAPH 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 AGENT E VAL must abstract them into user actions and activity states before counting. This section describes how AGENT E VAL 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. A. 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]; AGENT E VAL 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 IV-B), these variants map to a single activity state (Figure 4). B. Graph Construction Once discovery has finished, AGENT E VAL builds G from all collected session traces by the standard directly-follows construction over the abstracted events (Algorithm 1). Each distinct agent activity becomes a node, carrying its support. Whenever one activity directly follows another within a session, AGENT E VAL 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 V-B. V. T EST G ENERATION AGENT E VAL generates two kinds of test, both LLMgenerated and grounded in the discovery traces: functional

Functional test (replay the cancellation workflow). Goal: check several reservations and explain the cancellation policy by cabin class. User turns: (1) “user ID mia_li_3668; cancel AIXC49”; (2) “reason: change of plan”; (3) “check HKEG34 instead, with details and insurance status?” Pass if the agent denies AIXC49 with a policy reason, reports HKEG34 as business class and cancellable, and offers to cancel it; fail if it skips HKEG34 or calls business class non-cancellable. Turn budget: 3. Boundary test (target: node show_reservation_details, premature activity without prerequisite context). Goal: when details are requested before any lookup, the agent must look up first or ask which reservation. User turn (the single perturbation): “user ID olivia_gonzalez_2305; show me the details of my reservation.” Pass if the agent asks for a reservation ID or offers to look up first and reveals no details; fail if it shows details without establishing which reservation. Turn budget: 3. Fig. 5. Two tests AGENT E VAL generated for the τ 3 -bench airline agent (abbreviated from the run artifacts), one of each kind. Both use the test schema of Section II: a goal, user-turn hints, observable pass and fail criteria, and a turn budget. The boundary test also specifies the graph location it targets and the type of boundary.

tests synthesized directly from them, and boundary tests guided by the workflow graph. Figure 5 shows one generated test of each kind, both drawn from the running example’s cancellation workflow and both using the schema of Section II. 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. A. Functional Test Synthesis AGENT E VAL 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; AGENT E VAL adds rounds up to a cap of Nf tests and stops early once new tests stop appearing. Every test follows the schema of Section II, and AGENT E VAL 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, AGENT E VAL carries forward the tests it has already accepted so the LLM does not repeat them. B. 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

TABLE I S TRUCTURAL BOUNDARY TARGETS ENUMERATED FROM THE GRAPH . E ACH LOCATION BECOMES A TARGET; THE LLM RANKS TARGETS BY BOUNDARY POTENTIAL AND GENERATES TESTS GROUNDED IN THE BEHAVIOR OBSERVED AT THE LOCATION .

Target

Graph element

What stressing it tests

Node

an observed activity (v ∈ V )

Edge

an observed transition ((v, v ′ ) ∈ E) an entry activity (v ∈ S)

whether the agent guards, clarifies, or recovers when its required context is perturbed whether the agent handles a skipped, incomplete, ambiguous, or unsupported continuation visibly whether the agent asks for required context before proceeding from an alternate or incomplete start whether the agent handles continuation or unsupported follow-up after an observed end

Start End

a terminal activity (v ∈ T )

boundaries are instead stateful: the confirmation gate, the slot that validates an identifier, the prerequisite that must precede an action. AGENT E VAL 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 2). Target selection. AGENT E VAL deterministically enumerates one boundary target per structural location of the graph: every node, every edge, every entry activity, and every terminal activity (Table I). 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, AGENT E VAL 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. AGENT E VAL 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 5 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 pro-

Algorithm 2 Graph-guided boundary test synthesis Require: workflow graph G, budget Nb 1: L ← enumerate node/edge/start/end targets of G 2: L ← rank L by LLM-scored boundary potential, keep top Nb 3: P ← ∅ 4: for each selected target ℓ ∈ L (up to Nb ) do 5: generate boundary tests stressing ℓ, grounded in ℓ’s observed behavior; add them to P 6: end for 7: return P ceeding 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 AGENT E VAL 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 VI measures as a lower duplicate rate and a higher distinct-boundary count. VI. E VALUATION To evaluate AGENT E VAL, we run the full system across all four τ 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 VI-C); 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 AGENT E VAL 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 AGENT E VAL’s execution-phase judge reliably tell a real fault from correct behavior, from the visible conversation alone? 5) RQ5 (Efficiency). What do AGENT E VAL’s discovery, functional, and boundary stages cost in LLM calls, tokens, and wall-clock time? A. Configurations The full-system results (Table III) 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 IV). Naive uses naive, unguided discovery; Phase-guided uses the phase-guided discovery of Section III-A. 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 V). 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 V-B). B. 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 Tv , the validity rate |Tv |/|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|/|I| is the fraction of the documented-behavior inventory 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 |/|Tv |. 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

TABLE II AUDITOR - MODEL SELECTION ( AIRLINE , 26 SCENARIOS ); AGREEMENT IS THE JACCARD OVERLAP WITH AN EXPERT ’ S COVERED - ITEM SET. Auditor model Human reference GLM-5.2 (chosen) MiMo-v2.5-pro DeepSeek-v4-pro GPT-5.4-mini

Recall

Agreement

0.82 0.82 0.90 0.90 0.85

— 0.94 0.91 0.91 0.86

at runtime; a judge-inconclusive run is inconclusive here too). From these it reports the false-alarm rate FAR = FP/(FP + TN), accuracy Acc = (TP + TN)/N , and inconclusive rate Inc = INC/N (with N = TP + FP + TN + FN + INC). C. Setup We evaluate on the four text domains of τ 3 -bench [16]: airline, retail, and telecom from τ 2 -bench [6], and banking from τ -Knowledge [21].We use these environments only as black-box targets; we do not run τ 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 MiMov2.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 Rdisc = 12 discovery rounds; Bturn = 6 turns per session; a phase warm-up of mcap = 1 capabilitydiscovery, mhp = 2 happy-path, and mcc = 1 consistencycheck sessions before free phase choice; and a target of Nf = 50 functional tests, plus an additional Nb = 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 II)—and adopt GLM-5.2, which agrees most closely (0.94) and matches the expert’s coverage recall (0.82) exactly. D. Results RQ1: Functional testing effectiveness across domains. Table III 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 (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 (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 IV), raising coverage recall from 0.72 to 0.97 at unchanged validity (1.00). RQ2: Boundary testing effectiveness across domains. Table III also reports the full system’s graph-guided boundary pass. With a budget of 50 boundary tests per domain, AGEN T E VAL 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-falsealarm 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 V 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 freeform 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× 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 V-B, 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

TABLE III F ULL - SYSTEM RESULTS ACROSS THE FOUR τ 3 - BENCH DOMAINS . Valid: VALIDITY RATE ; CovRec: COVERAGE RECALL ; Act./Tr.: GRAPH ACTIVITIES / TRANSITIONS ; Distinct: DISTINCT- BOUNDARY COUNT; Dup.: DUPLICATE RATE ; FAR/Acc/Inc: FALSE - ALARM / ACCURACY / INCONCLUSIVE RATES .

Functional tests

Graph

Boundary tests

Domain

Valid

CovRec

FAR

Acc

Inc

Act.

Tr.

Distinct

Valid

Dup.

FAR

Acc

Inc

Airline Retail Telecom Banking

1.00 0.97 0.91 0.94

0.97 1.00 0.73 0.53

0.07 0.00 0.05 0.00

0.93 0.97 0.95 1.00

0.04 0.00 0.05 0.00

46 50 55 153

54 51 59 139

23 26 28 38

0.78 0.79 0.97 0.98

0.26 0.16 0.24 0.19

0.00 0.06 0.09 0.02

1.00 0.94 0.91 0.98

0.03 0.00 0.05 0.04

TABLE IV D ISCOVERY ABLATION ON THE AIRLINE FUNCTIONAL PLAN (NAIVE VS . P HASE - GUIDED ); METRICS AS IN TABLE III.

TABLE VI J UDGE RELIABILITY ON process/guard FAULTS ( AIRLINE , SEEDED SINGLE - TURN TRANSCRIPT EDITS ).

Discovery

Valid

CovRec

FAR

Acc

Inc

Injected fault class

Naive Phase-guided

1.00 1.00

0.72 0.97

0.00 0.07

1.00 0.93

0.13 0.04

TABLE V B OUNDARY- GENERATION ABLATION ON THE AIRLINE DOMAIN (50 BOUNDARY TESTS ); METRICS AS IN TABLE III. Boundary generation Prompt-only Graph-context Ours

Distinct

Valid

Dup.

FAR

Acc

Inc

12 9 23

0.96 1.00 0.78

0.56 0.40 0.26

0.04 0.00 0.00

0.96 1.00 1.00

0.00 0.00 0.03

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 VI) 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 VII): 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

Seeded

Caught

Confirmation gate removed Identity prerequisite dropped Eligibility check skipped Invalid value accepted

6 4 14 3

4 3 12 3

Total

27

22

Rate

0.81

TABLE VII J UDGE RELIABILITY ON value/accuracy FAULTS ( AIRLINE , LIVE TOOL - OUTPUT MUTATIONS ); Rel. COUNTS RELEVANT TESTS , AND A MUTANT IS KILLED IF ≥ 1 TEST CATCHES IT. Live tool-output mutation

Rel.

Caught

Killed

Insurance status flipped Reservation price doubled Search price inflated Flight status masked

5 10 14 11

2 1 8 1

✓ ✓ ✓ ✓

Total

40

12

4/4

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 VIII reports the cost of the airline ablation. The Naive baseline makes 142 LLM calls and consumes 0.60M tokens; the full system (Ours) makes 285 calls and consumes 1.55M 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 67K tokens per distinct boundary, against 108K for Prompt-only and 149K for Graph-context, which yields the fewest distinct boundaries for comparable cost; structural targeting spends its budget on distinct boundaries rather than duplicates.

TABLE VIII C OST OF EACH CONFIGURATION ON THE AIRLINE ABLATION : LLM CALLS , TOKENS , AND WALL - CLOCK TIME . Configuration

LLM calls

Tokens (M)

Time (h)

Naive Prompt-only Graph-context Ours

142 268 274 285

0.60 1.30 1.34 1.55

1.3 2.3 2.4 2.5

E. 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. MiMov2.5-pro) to avoid self-audit bias, and validate its coverage audit against an expert reference (Section VI-C); its run-audit labels behind FAR are not independently validated, however, so residual auditor error there remains a threat that a humanvalidated 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 AGENT E VAL 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 τ 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. AGENT E VAL 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. AGENT E VAL’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. VII. R ELATED W ORK 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-byreproduce 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. AGENT E VAL 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. AGENT E VAL’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; AGENT E VAL 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-asjudge is biased [55], and intrinsic self-correction is unreliable without external grounding [56]–[59]. AGENT E VAL’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]; AGEN T E VAL lifts the boundary idea from input edges to workflowstate preconditions, which is precisely where conversational agents fail. VIII. C ONCLUSION We presented AGENT E VAL, 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, AGENT E VAL 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 graphguided 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. R EFERENCES [1] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao, “ReAct: Synergizing reasoning and acting in language models,” in International Conference on Learning Representations (ICLR), 2023. [2] T. Schick, J. Dwivedi-Yu, R. Dessı̀, R. Raileanu, M. Lomeli, E. Hambro, L. Zettlemoyer, N. Cancedda, and T. Scialom, “Toolformer: Language models can teach themselves to use tools,” in Advances in Neural Information Processing Systems (NeurIPS), 2023. [3] S. Yao, N. Shinn, P. Razavi, and K. Narasimhan, “τ -bench: A benchmark for tool-agent-user interaction in real-world domains,” arXiv preprint arXiv:2406.12045, 2024. [4] S. McGregor, “Preventing repeated real world AI failures by cataloging incidents: The AI incident database,” in Proceedings of the AAAI Conference on Artificial Intelligence (IAAI track), vol. 35, no. 17, 2021, pp. 15 458–15 463. [5] P. Le Jeune, J. Liu, L. Rossi, and M. Dora, “RealHarm: A collection of real-world language model application failures,” in Proceedings of the First Workshop on Large Language Model Security (LLMSEC), 2025, pp. 87–100. [6] V. Barres, H. Dong, S. Ray, X. Si, and K. Narasimhan, “τ 2 -bench: Evaluating conversational agents in a dual-control environment,” arXiv preprint arXiv:2506.07982, 2025. [7] S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, T. Ou, Y. Bisk, D. Fried, U. Alon, and G. Neubig, “WebArena: A realistic web environment for building autonomous agents,” in International Conference on Learning Representations (ICLR), 2024. [8] G. Mialon, C. Fourrier, C. Swift, T. Wolf, Y. LeCun, and T. Scialom, “GAIA: A benchmark for general AI assistants,” in International Conference on Learning Representations (ICLR), 2024. [9] H. Trivedi, T. Khot, M. Hartmann, R. Manku, V. Dong, E. Li, S. Gupta, A. Sabharwal, and N. Balasubramanian, “AppWorld: A controllable world of apps and people for benchmarking interactive coding agents,” in Annual Meeting of the Association for Computational Linguistics (ACL), 2024, pp. 16 022–16 076.

[10] C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan, “SWE-bench: Can language models resolve real-world GitHub issues?” in International Conference on Learning Representations (ICLR), 2024. [11] G. J. Myers, C. Sandler, and T. Badgett, The Art of Software Testing, 3rd ed. Wiley, 2011. [12] S. Y. Ahmed, S. Feng, C. Bae, C. Barrus, and X. Zhang, “SpecOps: A fully automated AI agent testing framework in real-world GUI environments,” in Proceedings of the 48th IEEE/ACM International Conference on Software Engineering (ICSE), 2026. [13] L. Sorokin, I. Vasilev, K. E. Friedl, and A. Stocco, “STELLAR: A search-based testing framework for large language model applications,” arXiv preprint arXiv:2601.00497, 2026. [14] W. M. P. van der Aalst, Process Mining: Data Science in Action, 2nd ed. Springer, 2016. [15] ——, “A practitioner’s guide to process mining: Limitations of the directly-follows graph,” in International Conference on Enterprise Information Systems (CENTERIS), Procedia Computer Science vol. 164, 2019, pp. 321–328. [16] Sierra Research, “τ 3 -bench: From text-only to multimodal, knowledgeaware agent evaluation,” https://github.com/sierra-research/tau2-bench, 2026, accessed: 2026-06-30. [17] N. Tax, N. Sidorova, R. Haakma, and W. M. P. van der Aalst, “Event abstraction for process mining using supervised learning techniques,” in Intelligent Systems Conference (IntelliSys), 2016, pp. 251–269. [18] S. J. van Zelst, F. Mannhardt, M. de Leoni, and A. Koschmider, “Event abstraction in process mining: Literature review and taxonomy,” Granular Computing, vol. 6, no. 3, pp. 719–736, 2021. [19] F. Dobslaw, F. G. de Oliveira Neto, and R. Feldt, “Boundary value exploration for software analysis,” in IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2020, pp. 346–353. [20] N. P. Kropp, P. J. Koopman, and D. P. Siewiorek, “Automated robustness testing of off-the-shelf software components,” in International Symposium on Fault-Tolerant Computing (FTCS), 1998, pp. 230–239. [21] Q. Shi, A. Zytek, P. Razavi, K. Narasimhan, and V. Barres, “τ knowledge: Evaluating conversational agents over unstructured knowledge,” arXiv preprint arXiv:2603.04370, 2026. [22] Y. Qin, S. Liang, Y. Ye, K. Zhu, L. Yan, Y. Lu, Y. Lin, X. Cong, X. Tang, B. Qian, S. Zhao, L. Hong, R. Tian, R. Xie, J. Zhou, M. Gerstein, D. Li, Z. Liu, and M. Sun, “ToolLLM: Facilitating large language models to master 16000+ real-world APIs,” in International Conference on Learning Representations (ICLR), 2024. [23] D. Guo, T. Zhou, D. Liu, C. Qian, Q. Ren, S. Shao, Z. Fan, Y. R. Fung, K. Wang, L. Zhang, and J. Shao, “Towards self-evolving benchmarks: Synthesizing agent trajectories via test-time exploration under validateby-reproduce paradigm,” arXiv preprint arXiv:2510.00415, 2025. [24] W. Wang, Z. Ma, X. Wang, Y. Zhang, P. Liu, and M. Chen, “TestAgent: Automatic benchmarking and exploratory interaction for evaluating LLMs in vertical domains,” arXiv preprint arXiv:2410.11507, 2024. [25] Y. Chen, X. Hu, Y. Liu, Z. Wang, Z. Liao, L. Chen, F. Wei, Y. Qian, B. Zheng, K. Yin, and S. Zhang, “Graph2Eval: Automatic multimodal task generation for agents via knowledge graphs,” arXiv preprint arXiv:2510.00507, 2025. [26] J. Geng, H. Chen, D. Arumugam, and T. L. Griffiths, “Are large language models reliable AI scientists? assessing reverse-engineering of black-box systems,” arXiv preprint arXiv:2505.17968, 2025. [27] G. Ammons, R. Bodı́k, and J. R. Larus, “Mining specifications,” in ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2002, pp. 4–16. [28] J. E. Cook and A. L. Wolf, “Discovering models of software processes from event-based data,” ACM Transactions on Software Engineering and Methodology, vol. 7, no. 3, pp. 215–249, 1998. [29] D. Lorenzoli, L. Mariani, and M. Pezzè, “Automatic generation of software behavioral models,” in International Conference on Software Engineering (ICSE), 2008, pp. 501–510. [30] I. Beschastnikh, Y. Brun, M. D. Ernst, and A. Krishnamurthy, “Inferring models of concurrent systems from logs of their behavior with CSight,” in International Conference on Software Engineering (ICSE), 2014, pp. 468–479. [31] W. M. P. van der Aalst, T. Weijters, and L. Maruster, “Workflow mining: Discovering process models from event logs,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128–1142, 2004.

[32] S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, “Discovering block-structured process models from event logs—a constructive approach,” in Application and Theory of Petri Nets and Concurrency, LNCS 7927, 2013, pp. 311–329. [33] W. Sadiq and M. E. Orlowska, “Applying graph reduction techniques for identifying structural conflicts in process models,” in International Conference on Advanced Information Systems Engineering (CAiSE), LNCS 1626, 1999, pp. 195–209. [34] D. Angluin, “Learning regular sets from queries and counterexamples,” Information and Computation, vol. 75, no. 2, pp. 87–106, 1987. [35] W. Shi, T. Zhao, and Z. Yu, “Unsupervised dialog structure learning,” in Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT), 2019, pp. 1797–1807. [36] S. Burdisso, S. Madikeri, and P. Motlicek, “Dialog2Flow: Pre-training soft-contrastive action-driven sentence embeddings for automatic dialog flow extraction,” in Conference on Empirical Methods in Natural Language Processing (EMNLP), 2024, pp. 5421–5440. [37] J. Schatzmann, B. Thomson, K. Weilhammer, H. Ye, and S. Young, “Agenda-based user simulation for bootstrapping a POMDP dialogue system,” in Human Language Technologies: Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT), Short Papers, 2007, pp. 149–152. [38] Q. Zhu, Z. Zhang, Y. Fang, X. Li, R. Takanobu, J. Li, B. Peng, J. Gao, X. Zhu, and M. Huang, “ConvLab-2: An open-source toolkit for building, evaluating, and diagnosing dialogue systems,” in Annual Meeting of the Association for Computational Linguistics (ACL), System Demonstrations, 2020, pp. 142–149. [39] M. Utting, A. Pretschner, and B. Legeard, “A taxonomy of modelbased testing approaches,” Software Testing, Verification and Reliability, vol. 22, no. 5, pp. 297–312, 2012. [40] D. Lee and M. Yannakakis, “Principles and methods of testing finite state machines—a survey,” Proceedings of the IEEE, vol. 84, no. 8, pp. 1090–1123, 1996. [41] T. S. Chow, “Testing software design modeled by finite-state machines,” IEEE Transactions on Software Engineering, vol. SE-4, no. 3, pp. 178– 187, 1978. [42] V. Atlidakis, P. Godefroid, and M. Polishchuk, “RESTler: Stateful REST API fuzzing,” in International Conference on Software Engineering (ICSE), 2019, pp. 748–758. [43] A. Arcuri, “RESTful API automated test case generation with EvoMaster,” ACM Transactions on Software Engineering and Methodology, vol. 28, no. 1, pp. 3:1–3:37, 2019. [44] Y. Liu, Y. Li, G. Deng, Y. Liu, R. Wan, R. Wu, D. Ji, S. Xu, and M. Bao, “Morest: Model-based RESTful API testing with execution feedback,” in International Conference on Software Engineering (ICSE), 2022, pp. 1406–1417. [45] T. Le, T. Tran, D. Cao, V. Le, T. N. Nguyen, and V. Nguyen, “KAT: Dependency-aware automated API testing with large language models,” in IEEE Conference on Software Testing, Verification and Validation (ICST), 2024. [46] A. Golmohammadi, M. Zhang, and A. Arcuri, “Testing RESTful APIs: A survey,” ACM Transactions on Software Engineering and Methodology, vol. 33, no. 1, pp. 27:1–27:41, 2023. [47] M. Schäfer, S. Nadi, A. Eghbali, and F. Tip, “An empirical evaluation of using large language models for automated unit test generation,” IEEE Transactions on Software Engineering, vol. 50, no. 1, pp. 85–105, 2024. [48] J. Altmayer Pizzorno and E. D. Berger, “CoverUp: Effective high coverage test generation for Python,” Proceedings of the ACM on Software Engineering, vol. 2, no. FSE, 2025. [49] Z. Yuan, M. Liu, S. Ding, K. Wang, Y. Chen, X. Peng, and Y. Lou, “Evaluating and improving ChatGPT for unit test generation,” in ACM International Conference on the Foundations of Software Engineering (FSE), 2024, pp. 1703–1726. [50] C. Lemieux, J. P. Inala, S. K. Lahiri, and S. Sen, “CodaMosa: Escaping coverage plateaus in test generation with pre-trained large language models,” in International Conference on Software Engineering (ICSE), 2023, pp. 919–931. [51] S. Gu, Q. Zhang, K. Li, C. Fang, F. Tian, L. Zhu, J. Zhou, and Z. Chen, “TestART: Improving LLM-based unit testing via co-evolution of automated generation and repair iteration,” arXiv preprint arXiv:2408.03095, 2024. [52] E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo, “The oracle problem in software testing: A survey,” IEEE Transactions on Software Engineering, vol. 41, no. 5, pp. 507–525, 2015.

[53] M. D. Davis and E. J. Weyuker, “Pseudo-oracles for non-testable programs,” in Proceedings of the ACM ’81 Conference, 1981, pp. 254– 257. [54] E. J. Weyuker, “On testing non-testable programs,” The Computer Journal, vol. 25, no. 4, pp. 465–470, 1982. [55] L. Zheng, W.-L. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. P. Xing, H. Zhang, J. E. Gonzalez, and I. Stoica, “Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena,” in Advances in Neural Information Processing Systems (NeurIPS), Datasets and Benchmarks Track, 2023. [56] J. Huang, X. Chen, S. Mishra, H. S. Zheng, A. W. Yu, X. Song, and D. Zhou, “Large language models cannot self-correct reasoning yet,” in International Conference on Learning Representations (ICLR), 2024. [57] K. Stechly, K. Valmeekam, and S. Kambhampati, “On the selfverification limitations of large language models on reasoning and planning tasks,” arXiv preprint arXiv:2402.08115, 2024. [58] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, S. Gupta, B. P. Majumder, K. Hermann, S. Welleck, A. Yazdanbakhsh, and P. Clark, “Self-Refine: Iterative refinement with self-feedback,” in Advances in Neural Information Processing Systems (NeurIPS), 2023. [59] Z. Gou, Z. Shao, Y. Gong, Y. Shen, Y. Yang, N. Duan, and W. Chen, “CRITIC: Large language models can self-correct with tool-interactive critiquing,” in International Conference on Learning Representations (ICLR), 2024. [60] T. Y. Chen, F.-C. Kuo, H. Liu, P.-L. Poon, D. Towey, T. H. Tse, and Z. Q. Zhou, “Metamorphic testing: A review of challenges and opportunities,” ACM Computing Surveys, vol. 51, no. 1, pp. 4:1–4:27, 2018. [61] K. Greshake, S. Abdelnabi, S. Mishra, C. Endres, T. Holz, and M. Fritz, “Not what you’ve signed up for: Compromising real-world LLMintegrated applications with indirect prompt injection,” in ACM Workshop on Artificial Intelligence and Security (AISec), 2023, pp. 79–90. [62] F. Perez and I. Ribeiro, “Ignore previous prompt: Attack techniques for language models,” in NeurIPS ML Safety Workshop, 2022.