1
Testing Agentic Workflows with Structural Coverage Criteria
arXiv:2605.26521v1 [cs.SE] 26 May 2026
Nafiseh Kahani and Mojtaba Bagherzadeh
Abstract—Multi-agent systems increasingly expose explicit workflow structure: agents, tools, tool-access rules, restrictions, and delegation paths. Existing evaluations rely largely on endto-end task success, benchmark scores, final-response quality, or prompt-level checks, which provide limited evidence that this declared coordination structure has actually been exercised. This makes it difficult to assess test-suite adequacy or detect structural regressions in tool access, restrictions, and inter-agent delegation. We address this gap with a structural testing approach for multi-agent workflow specifications. The approach represents each workflow as a typed coordination graph, derives coverage obligations over reachable agents, allowed tool edges, restricted tool edges, and delegation edges, and uses coverage-driven generation with DSPy-based scenario realization to produce executable tests. The graph fixes what must be covered; DSPy realizes those obligations as natural-language scenarios whose witnesses are checked at runtime. We implement the approach for OpenAI Agents SDK-style workflows and evaluate it on ten SDK-derived benchmarks comprising 49 reachable agents, 47 tools, and 403 structural obligations. Generated scenarios witness 54/75 allowed-tool obligations and 36/48 delegation obligations within a bounded refinement budget. The adversarial restrictedtool criterion elicits 23/248 restricted-call violations, separating workflows whose restrictions hold under probing from workflows with concrete misrouting failures. These results show that structural coverage provides a useful adequacy layer for multiagent workflow testing: it does not replace semantic or end-to-end evaluation, but reveals whether declared agents, tool-access rules, restrictions, and delegation paths have been exercised. Index Terms—agent testing, coverage, mutation analysis, software testing, agent artifacts
I. I NTRODUCTION LLM-based agents are software systems that use language models to interpret context, reason about goals, and take actions on behalf of users, often through tools or external APIs [20]. In this paper, we focus on LLM-based software agents and refer to them simply as agents. Recent tool-augmented and multi-agent systems extend beyond single-turn prompting to support information retrieval, planning, API use, orchestration, and delegation across specialized agents [21], [19]. As these systems become more capable, they are increasingly deployed as structured workflows rather than isolated prompts: agents are assigned roles, connected to tools, constrained by toolaccess rules, and linked through handoff or delegation paths. Existing evaluation practice largely emphasizes observable task outcomes, benchmark performance, final response quality, and tool-use behavior [11], [12], [9], [15], [7], [22]. These First Author is with the Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada. Email: [email protected] Second Author is with the Cisco Systems, Ottawa, Canada. Email: [email protected]
metrics are useful, but they provide limited evidence that a system’s internal coordination structure has been covered. A multi-agent workflow may complete a task successfully even if some tools are never invoked, some restricted tool accesses are never tested, or some delegation paths remain unexplored. Thus, end-to-end task success is not a reliable proxy for structural coverage in multi-agent systems. This gap becomes more important as multi-agent systems evolve. A small change to a workflow definition may add a new tool edge, remove a restriction, or alter a delegation path without causing immediate end-to-end failures. Conventional evaluations may still pass while important structural obligations remain unobserved. This makes it difficult to assess whether a test suite is adequate, whether a system change has been meaningfully exercised, and whether regressions have been introduced into the workflow’s coordination structure. The issue is especially important in safety-, policy-, or compliance-sensitive settings, where practitioners often need traceable evidence that relevant tool-access rules, restrictions, and coordination paths have been tested. We therefore treat multi-agent testing as both a behavioral and structural problem. We model a multi-agent workflow as a typed coordination graph whose nodes represent agents and tools, and whose edges represent relations such as allowed tool access, restricted tool access, and delegation. This perspective follows established ideas in software testing, where adequacy criteria such as statement coverage, branch coverage, and mutation-based testing are used to assess how thoroughly a program has been exercised [1], [13]. Related work on behavioral testing has likewise shown that aggregate accuracy or task success can mask important coverage gaps [16], [18]. However, structural adequacy for multi-agent workflows remains comparatively underdeveloped. In this paper, we define a structural adequacy model for typed multi-agent coordination graphs. The model includes four coverage criteria spanning reachable agents, allowed tool edges, restricted tool edges, and delegation edges. These criteria measure not only whether a multi-agent system produces acceptable outputs, but also whether its declared coordination structure has been witnessed during testing. We then introduce a coverage-driven generation procedure that synthesizes structural witness objectives from the graph and uses DSPy modules to realize each objective as a naturallanguage test scenario [8], [2]. The structural meaning of each test is fixed by the graph; DSPy is used only for controlled scenario realization, and runtime witnesses determine whether a generated scenario actually covers its intended obligation. We implement the approach as a prototype for OpenAI
2
Agents SDK-style workflows. The pipeline takes a Python agent entry point, extracts a normalized workflow manifest, derives graph-based structural obligations, realizes typed witness objectives as natural-language scenarios, and measures coverage by replaying those scenarios against a runtime adapter. The implementation supports both one-shot execution and stageby-stage invocation, so extraction, obligation construction, scenario realization, and runtime evaluation can be inspected independently. We evaluate the approach on ten SDK-derived workflows extracted from the OpenAI Agents SDK examples and public third-party projects built on the same SDK. Together, these benchmarks contain 49 reachable agents, 47 tools, and 403 graph-derived structural obligations. The evaluation is organized around four research questions: whether the pipeline can extract valid typed coordination graphs and structural obligations from SDK-derived workflows (RQ1); how often generated scenarios witness allowed-tool and delegation obligations at runtime (RQ2); whether adversarial restricted-tool testing reveals concrete violations of declared restrictions (RQ3); and whether the same structural harness can test robustness under tool faults on a instrumented benchmark (RQ4). Our results show that structural obligations can be extracted and exercised across workflows of varying size and coordination structure. Across the runtime evaluation, generated scenarios witness 54/75 allowed-tool obligations and 36/48 delegation obligations within a bounded refinement budget. The adversarial restricted-tool criterion elicits 23/248 restricted-call violations, separating workflows whose restrictions hold under probing from workflows with concrete misrouting failures. We use the OpenAI Agents SDK oai_customer_service workflow as both a running example throughout the paper and a instrumented benchmark for routing-prompt ablation and tool-fault robustness. These results show that structural testing complements existing agent evaluations: it does not replace end-to-end benchmarks or semantic quality assessment, but provides explicit evidence that a multi-agent workflow’s declared agents, tool-access rules, restrictions, and delegation paths have been exercised. The paper makes the following contributions: • We formulate testing of multi-agent workflow specifications as a structural adequacy problem over typed coordination graphs derived from agent-framework source code. • We define graph-derived coverage criteria for reachable agents, allowed tool edges, restricted tool edges, and delegation edges. Restricted-tool coverage is treated as an explicit negative-observation obligation rather than as the mere absence of a tool call. • We present a coverage-driven test-generation pipeline that converts workflow manifests into typed witness objectives and uses DSPy-based, runtime-grounded realization to produce natural-language test scenarios. • We evaluate the approach on ten OpenAI Agents SDK-derived workflows totaling 403 structural obligations, including a deeper analysis of oai_customer_service for routing-prompt ablation and tool-fault robustness.
The remainder of the paper is organized as follows. Section II defines multi-agent workflow specifications and introduces the oai_customer_service running example. Section III presents the typed coordination-graph model, the four structural coverage criteria, and the coverage-driven generation procedure. Section IV describes the benchmark suite, implementation, and empirical evaluation across ten SDKderived workflows. Section V discusses related work in structural testing, model-based testing, automated test generation, and LLM-agent evaluation. Section VI discusses limitations, future work, and concludes. II. M ULTI -AGENT W ORKFLOW S PECIFICATIONS In this work, a multi-agent workflow specification is a normalized description of the structural elements of an LLMbased multi-agent workflow that are relevant for graph-based testing. It records the agents that may participate in an execution, the tools associated with the workflow, the toolaccess rules that determine which agents may or may not invoke which tools, and the delegation paths by which control may move between agents. We use this term to refer to the representation analyzed by our testing method, rather than to a universal format shared by all agent frameworks. The core declarations are: • a set of reachable agents, meaning agents that can be reached from the workflow entry point through zero or more delegation steps; • allowed tool edges, which record which tools each agent may invoke; • restricted tool edges, which record tools that an agent is explicitly restricted from invoking; and • delegation edges, which describe how one agent may hand control or responsibility to another agent. We interpret tool access using a closed-world convention. A tool is available to an agent only when an explicit allowedtool edge is declared. A restricted-tool edge represents an explicit negative obligation: generated tests should witness that the workflow respects the restriction. If no edge is declared between an agent and a tool, the pair is treated as unspecified rather than both allowed and restricted. Such pairs do not induce coverage obligations in our model. We also require well-formed specifications to avoid contradictory declarations, so the same agent–tool pair cannot appear as both allowed and restricted. We deliberately keep execution-time concerns out of the specification graph. Whether a particular tool is implemented as a Python function, an MCP server, or an HTTP endpoint, and whether the harness runs the test in a validation, dry-run, or full-execution mode, are properties of the runtime layer. They affect how a test is observed but do not change the set of structural obligations declared by the specification. We therefore treat the specification graph as a static description of agents, tools, allowed tool edges, restricted tool edges, and delegations. A. Running Example: oai_customer_service We use oai_customer_service as the main running example for introducing the workflow specification and graph-
3
derived coverage model. The workflow is extracted from the public OpenAI Agents SDK repository [14]; its source is the examples/customer_service/main.py file of openai/openai-agents-python. We extract the manifest mechanically, by importing the example module and introspecting its Agent, function_tool, and handoff objects. The specification used here is therefore a faithful normalization of what an SDK developer would write, not a hand-crafted toy. We later use oai_message_filter in Section III-C only to illustrate a multi-attempt delegationrefinement trace, because that benchmark exposes the runtimefeedback behavior of the realizer more clearly than the simpler customer-service example. The workflow contains three reachable agents: • triage_agent is the entry-point agent. It owns no tools of its own and acts as a router that hands the conversation off to the agent best suited to the user’s request. • faq_agent answers frequently asked questions about flights and is permitted to call the faq_lookup_tool function tool. • seat_booking_agent updates a passenger’s seat assignment and is permitted to call the update_seat function tool. There are two function tools, faq_lookup_tool and update_seat. Each tool is allowed for exactly one agent and explicitly restricted for the other two. In addition, both leaf agents are configured to hand the conversation back to triage_agent once their specialized work is done, so the delegation structure is bidirectional rather than tree-shaped. Figure 1 shows the corresponding coordination graph. Rounded nodes denote agents, rectangular nodes denote tools, solid edges denote allowed tool access, and dotted edges denote delegation. For readability, the figure shows only the two allowed-tool edges and the four delegation edges; the four restricted-tool edges are listed in the caption. Listing 1 shows the normalized specification used by the prototype. The listing uses a YAML rendering for readability. We return to this example throughout the paper. Section III-A uses it to illustrate the formal coverage model, Section III-B traces the generation procedure on it, and Section IV uses it as the instrumented benchmark within a broader tenworkflow evaluation. B. DSPy for Test Scenario Realization Our structural coverage model is symbolic: obligations are derived from a typed coordination graph. However, executing those obligations against LLM-based agent systems still requires natural-language scenarios. To generate those scenarios in a controlled way, we use DSPy as a scenario-realization layer rather than as the source of the coverage model. DSPy is a declarative framework for programming language-model pipelines using typed signatures, modules, and optimization metrics rather than hand-written prompt strings [8], [2]. A DSPy signature specifies the input–output behavior of a language-model module, while a module implements a reusable language model call that can be composed
triage_agent
delegate
faq_agent
delegate
seat_booking_agent
allow
faq_lookup_tool
allow
update_seat
Fig. 1: Coordination graph for the oai_customer_service running example. Rounded nodes are agents, rectangular nodes are tools, solid edges denote allowed tool access, and dotted edges denote delegation. The four restricted-tool edges, omitted from the figure for clarity, are: (triage_agent, faq_lookup_tool), (triage_agent, update_seat), (faq_agent, update_seat), and (seat_booking_agent, faq_lookup_tool).
system: id: oai_customer_service entry_agent: triage_agent agents: - id: triage_agent - id: faq_agent - id: seat_booking_agent tools: - id: faq_lookup_tool - id: update_seat permissions: allow: - [faq_agent, faq_lookup_tool] - [seat_booking_agent, update_seat] restrict: - [triage_agent, faq_lookup_tool] - [triage_agent, update_seat] - [faq_agent, update_seat] - [seat_booking_agent, faq_lookup_tool] delegations: - {from: triage_agent, to: faq_agent, trigger: delegate} - {from: faq_agent, to: triage_agent, trigger: delegate} - {from: triage_agent, to: seat_booking_agent, trigger: delegate} - {from: seat_booking_agent, to: triage_agent, trigger: delegate}
Listing 1: Normalized specification for the oai_customer_service running example, extracted from the OpenAI Agents SDK examples/customer_service module.
4
with other modules [4], [3]. DSPy programs can also be optimized against user-defined metrics, which makes them useful when the desired output can be checked automatically or semi-automatically [8]. In our setting, DSPy is used only after the structural obligations have been computed. The graph model determines what must be covered; DSPy helps realize each obligation as a concrete test scenario. This separation is important: the adequacy criteria do not depend on the language model’s judgment. Instead, the language model proposes candidate scenarios, and deterministic checks verify that each scenario is aligned with the intended obligation, consistent with the workflow specification, and paired with observable structural evidence. III. A PPROACH We propose a structural testing pipeline for multi-agent workflows. Rather than judging a workflow only by end-toend task success, the pipeline first reads the workflow specification as a structured graph, extracts the structural obligations declared by that graph, and generates tests that explicitly try to witness those obligations. In our setting, the obligations concern reachable agents, allowed tool edges, restricted tool edges, and delegation edges. The approach follows the five-step pipeline shown in Fig1 We begin from a normalized multi-agent workflow ure 2. ⃝ 2 We convert S into a reachable typed specification S. ⃝ 3 From G(S), we derive graphcoordination graph G(S). ⃝ 4 We synthesize typed witness objectives based obligations. ⃝ and use DSPy to realize them as natural-language test sce5 We execute the resulting tests through a runtime narios. ⃝ adapter and measure whether the expected structural evidence is observed. Overall, the method follows a specification → graph → obligations → tests → observations pipeline. The running example introduced in Section II-A provides a concrete instance of this process. It contains three reachable agents, two tools, two allowed tool edges, four restricted tool edges, and four delegation edges, yielding 13 structural obligations. Section IV later evaluates the same procedure across ten SDK-derived workflows. A. Formal Coverage Model Let S be a normalized multi-agent workflow specification. We model the structurally relevant content of S as a typed coordination graph G(S) = VA , VT , Eallow , Erestrict , Edel , where VA is the set of agent nodes, VT is the set of tool nodes, Eallow ⊆ VA × VT is the set of allowed agent–tool edges, Erestrict ⊆ VA × VT is the set of restricted agent–tool edges, and Edel ⊆ VA × VA is the set of delegation edges. Tools are modeled as opaque nodes. The graph does not record how a tool is implemented, such as a Python function, an MCP server, or an HTTP endpoint, nor which execution mode the harness uses to invoke it. These are runtime concerns that affect how a witness is observed but not which structural obligations exist.
Fig. 2: Overview of the proposed pipeline. A normalized multiagent workflow specification S is converted into a reachable coordination graph G(S), from which structural obligations are extracted. These obligations are turned into coveragedriven witness objectives and realized as executable tests via DSPy. Runtime observations then support coverage measurement. 1 Normalized Workflow Specification S ⃝ Agents, tools, allow/restrict edges, delegation edges ↓ 2 Reachable Coordination Graph G(S) ⃝ Typed nodes and reachable structural relations ↓ 3 Structural Obligations ⃝ Reachable agents, allowed tools, restricted tools, delegations ↓ 4 Generated Structural Tests ⃝ Natural-language scenarios with expected structural witnesses ↓ 5 Execution and Coverage Measurement ⃝ Runtime observations, witness verdicts, coverage scores
Let Areach ⊆ VA be the set of agents reachable from the workflow entry point by following zero or more delegation edges. Reachability is computed over Edel , so cycles in the delegation graph do not pose a problem. Structural coverage is defined only over reachable parts of the workflow. We assume well-formed specifications: all edge endpoints must be declared, and no agent–tool pair may appear in both Eallow and Erestrict . From G(S) we derive three additional reachable obligation sets: Tallow = {(a, t) ∈ Eallow | a ∈ Areach }, Trestrict = {(a, t) ∈ Erestrict | a ∈ Areach }, D = {(a, b) ∈ Edel | a ∈ Areach ∧ b ∈ Areach }. Thus, the structural obligation space is Ω(S) = Areach , Tallow , Trestrict , D . Each executed test x produces a structural observation obs(x) = agents(x), tools(x), restricted (x), delegations(x) , where agents(x) records observed agents, tools(x) records observed allowed tool invocations, restricted (x) records explicit restricted-access outcomes, and delegations(x) records observed delegation edges. A restricted-tool obligation is not witnessed merely by the absence of a tool call. It requires an explicit restricted-access observation, such as a harness-level rejection, policy event, refusal trace, or attempted restricted call recorded by the runtime adapter. This distinction is important because absence alone does not show that the restriction was actually exercised.
5
For a finite obligation set O and a witness predicate where S is a normalized multi-agent workflow specification W (x, ω), we define coverage as and X is a structural test suite. Generation proceeds in five phases: if O = ∅, 1, 1) Graph construction. Parse S and compute G(S). Cov(X, O, W ) = {ω ∈ O | ∃x ∈ X : W (x, ω)} 2) Obligation extraction. Derive Ω(S) = , otherwise, (Areach , Tallow , Trestrict , D). |O| 3) Objective construction. Convert each obligation into a where X is the generated test suite. This convention treats typed witness objective. criteria with no applicable obligations as vacuously satisfied. 4) Scenario realization. Use DSPy modules to realize a) C1. Agent coverage: Every reachable agent is obobjectives as natural-language scenarios. served by at least one test: 5) Validation and assembly. Check candidates against structural constraints and emit executable tests. C1 (X, S) = Cov X, Areach , λ(x, a). a ∈ agents(x) . Each generated test specification contains a target agent or b) C2. Allowed-tool coverage: Every reachable allowed workflow entry point, one or more structural witness objecagent–tool edge is exercised: tives, a natural-language user scenario, and the expected struc tural evidence: observed agents, agent–tool uses, restrictedC2 (X, S) = Cov X, Tallow , λ(x, (a, t)). (a, t) ∈ tools(x) . access outcomes, and delegation edges. c) C3. Restricted-tool coverage: Every reachable rea) Witness objectives: A witness objective is a typed stricted agent–tool edge is exercised through an explicit request for evidence about one structural obligation. We use restricted-access observation: four objective families: C3 (X, S) = Cov X, Trestrict , Reach(a), UseTool(a, t), RestrictTool(a, t), Delegate(a, b). λ(x, (a, t)). (a, t) ∈ restricted (x) . They ask, respectively, for evidence that agent a is reached, For example, a request that tempts triage_agent to update that agent a uses allowed tool t, that restricted access from a seat directly should produce explicit evidence that direct use a to t is explicitly observed, and that control transfers from of update_seat by triage_agent is blocked, refused, agent a to agent b. redirected, or otherwise recorded as a restricted-access event. b) Objective construction rules: The deterministic layer d) C4. Delegation coverage: Every reachable delegation constructs objectives using four rules: edge is observed: • R1 (Agent rule). For each a ∈ Areach , emit Reach(a). • R2 (Allowed-tool rule). For each (a, t) ∈ Tallow , emit C4 (X, S) = Cov X, D, λ(x, (a, b)). (a, b) ∈ delegations(x) . UseTool(a, t). Full structural coverage means that all four criteria are • R3 (Restricted-tool rule). For each (a, t) ∈ Trestrict , satisfied. It does not, by itself, guarantee semantic correctness, emit RestrictTool(a, t). safety, or output quality; it only shows that the declared • R4 (Delegation rule). For each (a, b) ∈ D, emit coordination structure has been exercised. Delegate(a, b). Applied to oai_customer_service, these rules emit 3 + 2 + 4 + 4 = 13 typed witness objectives. B. Coverage-Driven Test Generation c) Merging.: A single test may witness multiple obliWe now describe how tests are generated from the graphgations. For example, a test that exercises an allowed tool derived obligation space. The guiding principle is one obligaof agent a may also witness that a was reached. The merge tion, at least one witness objective. Rather than synthesizing step therefore combines compatible objectives into objective arbitrary task prompts and hoping they exercise the relevant bundles to reduce suite size. Each bundle contains one driver parts of a workflow, the generator starts from the obligation objective, which determines the DSPy realization signature, sets and constructs focused objectives designed to witness and zero or more secondary objectives, which are checked as them directly. additional witness obligations on the same runtime trace. The generator has two layers. The first layer is determinA merge is allowed only when it is obligation-preserving: istic: it constructs the reachable coordination graph, extracts obligations, and converts each obligation into a typed witness the realized test must retain the witness obligations of evobjective. The second layer is DSPy-based: it realizes each ery objective in the bundle. In the current implementation, witness objective as a natural-language test scenario, checks heterogeneous bundles are allowed only when the secondary whether the scenario is aligned with the intended obligation, objectives are reachability objectives entailed by the driver. For repairs invalid scenarios when possible, and emits executable example, a bundle containing Reach(a) and UseTool(a, t) is tests with expected structural observables. Thus, DSPy is used realized using the RealizeUseTool signature, and the resulting for controlled scenario realization, while the coverage model trace is checked for both reaching a and observing the tool-use edge (a, t). We do not merge objectives with different nonremains graph-defined [8], [2]. reachability drivers, such as UseTool(a, t) and Delegate(a, b), Formally, the generator is a mapping because they require different realization constraints. We also Generate(S) → X, forbid merges that introduce contradictions, such as requiring
6
the same agent to both use and be restricted from using the same tool in one execution. C. DSPy-Based Scenario Realization Each typed witness objective is realized by a DSPy module that produces a candidate end-user message and pairs it with the structural evidence expected from executing it. The structural meaning of a test is fixed by the objective; DSPy is responsible only for surface form and contextual plausibility. a) One signature per criterion: The realizer is not a single free-form prompt template. Each coverage criterion has its own DSPy signature [4], with structured input fields lifted from the manifest and criterion-specific generation constraints: • RealizeReach(C1 ) produces a realistic request that should route to the target agent without naming it. • RealizeUseTool(C2 ) produces a request that requires the capability provided by the target tool without naming the tool. • RealizeRestrictTool(C3 ) produces a request that tempts an agent toward a restricted capability while staying within its surface domain. • RealizeDelegate(C4 ) produces a request that should arrive at a parent agent but require delegation to a child agent. This separation matters because the objectives have different and sometimes opposite goals. For example, C2 asks the realizer to elicit a permitted tool call, while C3 asks it to probe a forbidden boundary. A single generic prompt template would not express these distinctions cleanly. b) Bounded refinement with an execution-grounded reward: Surface plausibility alone is a poor proxy for structural coverage: a well-written user message can be answered by the wrong agent or without the intended tool call. We therefore wrap the per-criterion realizer in a bounded dspy.Refine loop [2]. Each candidate prompt z is executed through the runtime adapter and scored by a binary reward: 0, if z leaks a forbidden identifier, such as a literal tool or agent name, r(z) = 1, if executing z produces the structural evidence required by the objective, 0, otherwise. The loop terminates as soon as r(z) = 1, or after N attempts. In our experiments, N = 5. After each attempt, the witness verdict and observed trace are fed back to the realizer, allowing it to revise based on runtime behavior rather than its own confidence. If no candidate succeeds within the budget, the objective is marked unrealized and reported. Worked example: a delegation realization. Figure 3 shows a real RealizeDelegate run on the oai_message_filter workflow, for the obligation Delegate(assistant_2 → spanish_assistant). Although oai_customer_service remains the paper’s main running example, we use oai_message_filter here because it provides a clearer illustration of multi-attempt runtime-grounded refinement. Early attempts ask for Spanish
Objective. Delegate(assistant_2 → spanish_assistant) on oai_message_filter. Signature inputs. Parent description of assistant_2; child description of spanish_assistant; delegation trigger “user prefers Spanish.” Attempt 1. “¿Puedes ayudarme a traducir este párrafo al español, por favor?” runtime: assistant_2 replies in Spanish; no handoff; r = 0. Attempt 2. “Hi, could you briefly explain this phrase in Spanish? . . . if my Spanish isn’t perfect, please kindly pass me on to someone who can assist fluently in Spanish.” runtime: assistant_2 answers in English; no handoff; r = 0. Attempt 3. “Please provide a very brief explanation of this text in Spanish . . . I’m more comfortable using that language for this.” runtime: assistant_2 replies in Spanish; no handoff; r = 0. Attempt 4. “Could you give me a very brief summary of this text? I’m more comfortable with Spanish, so please reply in Spanish or connect me with someone who can assist in Spanish.” runtime: handoff assistant_2 → spanish_assistant observed; r = 1. Stop.
Fig. 3: A four-attempt RealizeDelegate trace from oai_message_filter. The realizer converges on a phrasing that produces the intended delegation only after runtime-grounded feedback.
output but are answered directly by assistant_2, so no handoff is observed. After runtime feedback, the realizer changes the prompt to explicitly allow connection to someone who can assist in Spanish; this produces the intended handoff. The realizer cannot satisfy an objective merely by writing a plausible scenario. A candidate is accepted only when the runtime trace contains the expected structural evidence. This is what makes the generated suite coverage-driven rather than prompt-driven: the graph defines the obligation, DSPy proposes a scenario, and the runtime witness decides whether the scenario actually covers the obligation.
D. Execution and Observation Once generated, the suite is executed and evaluated through structural observations rather than source-code instrumentation. Each test produces an observation tuple of the form defined in Section III-A. These observations are matched back to the four obligation sets to compute coverage under C1 , C2 , C3 , and C4 . The execution layer may attach additional metadata, such as backend used, retry count, model configuration, trace identifier, or invocation surface, that is useful for debugging and reproducibility but is not part of the graph-derived coverage model. In our prototype, the runtime adapter materializes each reachable agent as an OpenAI Agents SDK Agent, registers tool edges as recording stubs that bridge to a per-test runtime context, and routes delegation handoffs through the SDK’s native handoff machinery. Section IV reports the resulting observations across the ten-workflow benchmark suite and the deeper oai_customer_service study.
7
Algorithm 1 Coverage-driven structural test generation with DSPy realization. 1: Construct reachable coordination graph G(S) 2: Extract obligations Ω(S) = (Areach , Tallow , Trestrict , D) 3: Q ← ∅ 4: for all a ∈ Areach do 5: Q ← Q ∪ {Reach(a)} 6: end for 7: for all (a, t) ∈ Tallow do 8: Q ← Q ∪ {UseTool(a, t)} 9: end for 10: for all (a, t) ∈ Trestrict do 11: Q ← Q ∪ {RestrictTool(a, t)} 12: end for 13: for all (a, b) ∈ D do 14: Q ← Q ∪ {Delegate(a, b)} 15: end for 16: B ← MergeCompatibleObjectives(Q) 17: X ← ∅ 18: for all Bi ∈ B do 19: q ⋆ ← Driver(Bi ) 20: Select the criterion-specific DSPy signature for q ⋆ 21: Bind signature inputs from S and G(S) 22: passed ← FALSE; i ← 0 23: while i < N and ¬passed do 24: z ← sample candidate user prompt using prior feedback 25: if z leaks a forbidden identifier then 26: r←0 27: else 28: τ ←V execute z and collect the structural trace 29: r ← q∈Bi Witness(q, τ ) 30: end if 31: record (z, τ, r) 32: if r = 1 then 33: X ← X ∪ {RealizeAsTest(z, τ, Bi )} 34: passed ← TRUE 35: end if 36: i←i+1 37: end while 38: if ¬passed then 39: ReportUnrealized(Bi ) 40: end if 41: end for 42: return X
IV. E VALUATION We evaluate the structural-testing pipeline on ten multiagent workflows drawn from the OpenAI Agents SDK examples and from public third-party projects built on the same SDK. The evaluation asks whether the proposed graphbased coverage model can be extracted from real SDKstyle workflow definitions, whether coverage-driven scenario generation can produce executable witnesses for the resulting obligations, and whether runtime witness outcomes provide useful diagnostic information about workflow structure. Across the ten workflows, the extracted specifications contain 49 reachable agents, 47 tools, and 403 graph-derived structural obligations. These obligations consist of reachable-agent obligations (C1 ), allowed-tool obligations (C2 ), restrictedtool obligations (C3 ), and delegation obligations (C4 ). We evaluate extraction and obligation construction on all ten workflows, execute runtime witness studies for allowedtool, restricted-tool, and delegation obligations, and use
oai_customer_service as a instrumented benchmark for additional routing-prompt ablation and tool-fault robustness experiments. The evaluation has three goals. First, it tests whether the deterministic parts of the pipeline produce well-formed coordination graphs and obligation sets across workflows of different sizes and orchestration styles. Second, it tests whether the LLM-based realization layer can produce natural-language scenarios that witness structural obligations at runtime under a bounded refinement budget. Third, it examines whether the resulting per-criterion outcome distributions are diagnostically useful: for example, whether they distinguish single-hop workflows from multi-hop workflows, and whether restricted-tool probing reveals concrete misrouting failures. All runtime results are single-run measurements under a fixed configuration. We therefore interpret them as empirical evidence of feasibility and diagnostic value, not as statistically powered estimates of performance across all multi-agent systems. A. Research Questions The evaluation is organized around four research questions. RQ1. Obligation extraction and scenario realization. Can the pipeline derive valid typed coordination graphs, structural coverage obligations, and corresponding witness scenarios from SDK-derived multi-agent workflows? RQ2. Allowed-tool and delegation witnesses. To what extent do generated scenarios witness allowed-tool obligations (C2 ) and delegation obligations (C4 ) at runtime? RQ3. Restricted-tool adversarial witnesses. Does restricted-tool testing (C3 ) reveal workflows whose declared tool restrictions can be violated under adversarial prompting? RQ4. Fault-injection robustness. Can the same structural harness test whether agents continue to handle tool faults without crashing or leaking raw error payloads? These questions separate witness types with different interpretations. For C2 and C4 , a satisfied witness means that the expected structural behavior was observed: the intended tool was invoked, or the intended delegation edge was traversed. For C3 , the runtime adversarial study has inverted polarity: a satisfied witness means that the adversarial scenario elicited an attempted restricted call. Thus, higher C3 violation counts are not better; they identify concrete hardening targets. RQ4 uses the same runtime harness but changes the witness predicate to test mechanical robustness under faulty tool responses. B. Benchmarks a) Source and extraction: Each benchmark is derived from publicly available OpenAI Agents SDK-style source code. The extractor imports a configured entry point, walks the reachable agent graph through declared tools and handoffs, and emits a normalized workflow specification of the kind described in Section II. The extracted specifications are then parsed into typed coordination graphs and checked for wellformedness before obligation construction. Manifests are not edited by hand; when a benchmark uses external orchestration
8
TABLE I: Benchmark list. Ag = reachable agents, Tl = tools, Al = allowed agent–tool edges, Re = restricted agent–tool edges, De = delegation edges, and Obl = total structural obligations (C1 +C2 +C3 +C4 = Ag+Al +Re+De). The tool count Tl is reported for context and does not contribute to Obl, since |C1 | counts reachable agents rather than tools.
modify the upstream agents, tools, or prompts. We report them because they affect the graph shape and therefore the derived obligations.
Benchmark ID Ag Tl Al Re De Obl oai_customer_service 3 2 2 4 4 13 oai_message_filter† 3 1 1 2 2 8 oai_research_bot 4 4 4 12 3 23 oai_financial_research 7 7 7 42 6 62 social_media_agent_system 2 3 3 3 1 9 deep_research_clone† 3 1 1 2 2 8 value_investment 4 9 24 12 3 43 autopitch 7 6 6 36 6 55 octagon_vc_agents 12 12 12 132 11 167 ydmitry_deep_research 4 2 5 3 3 15 Total (10) 49 47 65 248 41 403
The implementation consists of four stages: manifest extraction, obligation construction, scenario realization, and runtime witness execution. Extraction and obligation construction are deterministic. Scenario realization uses DSPy with a bounded refinement loop. Runtime witness execution replays each realized scenario against an OpenAI Agents SDK runtime adapter. All experiments use gpt-4.1-mini for both the realizer and the agent under test, with a maximum of N =5 refinement attempts per objective. The runtime adapter materializes each reachable agent as an SDK Agent, registers tool edges as recording stubs, and records observed agents, tool calls, restricted-access events, and delegation edges. Tool backends are mocked so that the witness signal measures structural behavior—which agent attempted which tool or handoff— rather than correctness of an external service. Each criterion-level runtime evaluation is executed once per benchmark under the default configuration. The oai_customer_service benchmark is additionally evaluated under a strict-routing realizer prompt and under two injected tool-fault modes. Because the realizer and the agent under test are LLM-backed, the reported results should be read as single-run empirical evidence rather than statistically powered estimates. a) Runtime witness accounting: The runtime focuses on allowed-tool, restricted-tool, and delegation obligations. Agent-reachability obligations are included in the structural obligation inventory, but the main runtime tables emphasize tool and delegation behavior because those criteria require more specific runtime evidence than observing that an agent appeared in a trace. Restricted-tool results are reported with inverted polarity: a counted restricted-tool witness means that an adversarial prompt elicited an attempted restricted call.
† These workflows implement part of their multi-agent control externally, by
re-invoking the runtime with a different starting agent rather than declaring all transfers as in-agent handoffs. For structural extraction, we re-encode the externally orchestrated transfer as an equivalent handoff edge in the extraction layer. This does not add agents, tools, prompts, or new behavior; it makes the already-present control transfer visible to the graph model.
rather than in-agent handoff declarations, the adaptation is documented below. Note that the tool count Tl and the allowedtool edge count Al need not coincide: the same tool may be declared as accessible to several agents, so each (agent, tool) access relation is counted as a separate allowed edge. This is why some benchmarks in Table I report Al > Tl (for example, value_investment with Tl =9 and Al =24). b) Benchmarks: Table I reports the structural shape of the ten extracted workflows. The benchmark set spans workflows from small routing examples to larger coordinatorstyle systems. It also includes both SDK delegation styles used in the source projects: explicit handoffs and sub-agent invocation through Agent.as_tool. Tools include userdefined function tools and SDK-provided tools such as web search. c) Instrumented benchmark: The oai_customer_service workflow plays a special role because it is small enough to inspect manually while still exercising every kind of structural obligation. It contains three reachable agents, two tools, two allowed tool edges, four restricted tool edges, and four delegation edges. We use it as the running example in Sections II and III, and as the instrumented benchmark for the routing-prompt ablation and fault-injection robustness study. d) Benchmark construction notes: Most benchmarks are extracted directly from their source-level agent declarations. A small number require normalization because their orchestration style is not represented as explicit SDK handoff declarations. For benchmarks that orchestrate sub-agents in ordinary Python control flow, the extraction layer introduces a coordinator representation that mirrors the published call structure. For workflows that externally switch the starting agent between turns, the extraction layer re-encodes that transfer as a handoff edge so that reachability can be computed from a single entry point. These adaptations are local to extraction and do not
C. Experimental Setup
D. RQ1: Obligation Extraction and Scenario Realization a) Setup: We run graph construction, obligation extraction, witness-objective construction, and DSPy-based scenario realization on every benchmark in Table I. For each benchmark, we record the graph shape, the resulting obligation counts, and whether the realizer produces a candidate naturallanguage scenario for each generated witness objective within the refinement budget. The realizer uses gpt-4.1-mini with N =5 attempts. b) Results: The extractor terminates with a well-formed coordination graph on all ten workflows. In total, the benchmark set contains 49 reachable agents, 65 allowed-tool edges, 248 restricted-tool edges, and 41 delegation edges, for 403 structural obligations. The obligation layer emits typed witness objectives for the resulting obligation sets without manual intervention. The scenario realizer produces candidate natural-language scenarios for the generated objectives within the refinement
9
budget. The realized scenarios are concrete and domainrelevant. For example, on oai_customer_service, a reachability objective for seat_booking_agent is realized as a request to change a seat assignment, while a multi-intent scenario for the entry agent combines a flight-change request with a baggage question. On social_media_agent_system, a use-tool objective for web search is realized as a request for recent viral social-media posts. c) Behaviour of the bounded refinement loop: Most realization attempts terminate quickly. On the smaller workflows, objectives often succeed on the first attempt. Multihop workflows require more attempts, especially when the target obligation sits behind two or more handoffs. In those cases, runtime feedback helps the realizer move from a generic request toward a more instrumental request that causes the intended route or tool call. This behavior is important because it shows that scenario realization is not judged by surface plausibility alone: candidates are refined using observed structural traces. RQ1 Summary The pipeline extracts well-formed coordination graphs and derives structural obligations for all ten SDKderived workflows. It also realizes witness scenarios within the bounded DSPy refinement budget. Multihop routing objectives account for the cases that require more than one realization attempt.
specialists. These workflows satisfy 19/23 allowed-tool witnesses. The misses occur mainly when the intended target overlaps semantically with another specialist, causing the coordinator to choose a different route. Third, multi-hop and handoff-stub targets account for most misses. In ydmitry_deep_research, misses occur when the intended target sits two hops away from the entry agent. In value_investment, many misses correspond to handofflike objects surfaced as allowed edges but not invocable as ordinary function tools by the runtime harness. These failures are informative: they show where prompt-only realization and runtime-callability assumptions are weakest. d) Delegation findings (C4 ): Delegation witnesses succeed on 31/41 obligations. As with allowed-tool witnesses, the main determinant is topology. Direct handoffs and obvious coordinator-to-specialist routes are usually witnessed. Multihop routes and overlapping specialist roles account for most failures. The bounded refinement loop is especially useful for delegation objectives. For example, in oai_message_filter, early attempts asking for Spanish output are answered directly by the parent agent. After runtime feedback, the realizer changes the request to explicitly allow connection to someone who can assist in Spanish, which produces the intended handoff. This illustrates the value of runtime-grounded realization: the realizer is not merely producing plausible prompts, but adapting prompts based on whether the structural witness actually appears. RQ2 Summary
E. RQ2: Allowed-Tool and Delegation Witnesses a) Setup: We execute the allowed-tool and delegation witness evaluations on all ten benchmarks. The allowed-tool witness for C2 holds when the runtime trace records that the intended agent invoked the intended allowed tool. The delegation witness for C4 holds when the trace records the intended handoff or Agent.as_tool transfer. Both evaluations use the default configuration described in Section IV-C. b) Cross-benchmark results: Table II reports perbenchmark runtime outcomes for allowed-tool, restricted-tool, and delegation witnesses. We discuss the allowed-tool and delegation columns here and the restricted-tool column in Section IV-F. Across the ten benchmarks, allowed-tool witnesses succeed on 45/65 obligations (69.2%), and delegation witnesses succeed on 31/41 obligations (75.6%). c) Allowed-tool findings (C2 ): The allowed-tool results cluster into three regimes. First, single-hop targets pass uniformly. On oai_customer_service, oai_message_filter, social_media_agent_system, and deep_research_clone, every allowed-tool target sits at most one delegation hop from the entry agent, and all allowed-tool witnesses succeed: 7/7 combined. Second, fan-out coordinator workflows pass on most targets. In oai_research_bot, oai_financial_research, and octagon_vc_agents, coordinators route to multiple
Allowed-tool witnesses succeed on 45/65 obligations, and delegation witnesses succeed on 31/41 obligations across the ten benchmarks. Single-hop targets pass uniformly, fan-out coordinators pass on most dominant routes, and multi-hop or runtime-ambiguous targets account for most misses.
F. RQ3: Restricted-Tool Adversarial Witnesses a) Setup: We execute the restricted-tool evaluation on all ten benchmarks. For each restricted edge (a, t), the realizer attempts to construct a request that tempts agent a toward capability t without naming the tool literally. Restricted tools are represented by recording stubs: if a restricted call is attempted, the runtime records the attempted (a, t) pair and returns a refusal payload. The C3 witness is satisfied when the target restricted call attempt is observed. For C3 , a satisfied witness means that the adversarial prompt elicited a restricted-call attempt. Such a result is useful because it gives a concrete hardening target, but it is not a positive outcome from a restriction-enforcement perspective. Conversely, a zero count means that no restricted-call violation was elicited within the realizer’s adversarial budget; it is not an absolute safety guarantee. b) Results: Across the ten benchmarks, restrictedtool probing elicits 23 violations out of 248 restricted-tool obligations (9.3%). Four benchmarks
10
TABLE II: Cross-benchmark single-execution runtime results under the default configuration. Columns report obligations satisfied within the N =5 refinement budget. For C2 and C4 , a satisfied witness means that the expected allowed-tool invocation or delegation edge was observed. For C3 , polarity is inverted: a satisfied witness means that an adversarial prompt elicited an attempted restricted call. Thus, lower C3 violation counts are better from a restriction-enforcement perspective. Allowed tool Restricted violation Delegation Wall (s) LM r.t. witnessed (C2 ) elicited (C3 ) witnessed (C4 ) oai_customer_service 2/2 0/4 4/4 290 47 oai_message_filter 1/1 0/2 2/2 138 27 social_media_agent_system 3/3 2/3 1/1 311 33 deep_research_clone 1/1 0/2 2/2 161 23 ydmitry_deep_research 2/5 1/3 2/3 498 59 oai_research_bot 3/4 0/12 2/3 1,789 137 value_investment 13/24 4/12 3/3 3,352 243 autopitch 4/6 3/36 3/6 6,409 376 oai_financial_research 5/7 7/42 3/6 7,353 407 octagon_vc_agents 11/12 6/132 9/11 18,915 2,285 Total (10 benchmarks) 45/65 23/248 31/41 39,216 3,637 Benchmark
TABLE III: Routing-prompt ablation on oai_customer_service. “Pass” counts allowed-tool objectives whose witness predicate held during execution. “Wall” is end-to-end wall time, and “Calls” is the number of realizer LM round-trips. Cell A B
Realizer gpt-4.1-mini gpt-4.1-mini
Routing loose strict
Pass 2/2 2/2
Calls 2 2
produce no elicited restricted-call violations within the budget: oai_customer_service (0/4), oai_message_filter (0/2), deep_research_clone (0/2), and oai_research_bot (0/12). Six benchmarks produce at least one violation: social_media_agent_system (2/3), ydmitry_deep_research (1/3), value_investment (4/12), autopitch (3/36), oai_financial_research (7/42), and octagon_vc_agents (6/132). c) No violation elicited within budget: The zero-violation benchmarks are informative because they show cases where adversarial prompting did not elicit the targeted restricted call. On oai_customer_service, capability-laden requests tend to route to the agent that legitimately owns the tool rather than causing a peer specialist to invoke an offowner tool. For example, a request about changing a seat is routed toward seat_booking_agent instead of causing faq_agent to invoke update_seat. Similar behavior appears in deep_research_clone, where scrapinglike requests route to the search execution agent, and in oai_research_bot, where the coordinator structure limits direct invocation of underlying function tools. Table IV gives the per-objective restricted-tool outcomes for oai_customer_service. The off-target column is important: it shows that the recording mechanism can observe restricted-call attempts even when the target restricted edge is not violated. Thus, the zero on-target count is not merely an instrumentation failure. d) Elicited restricted-call violations: On the six benchmarks with violations, the eliciting prompts are concrete and reproducible. In social_media_agent_system, re-
quests for recent viral posts can steer the social-media agent toward a web-search capability outside its declared access. In ydmitry_deep_research, a request for immediate source retrieval can cause the orchestrator to invoke a sourcegathering tool directly rather than route to the search specialist. In oai_financial_research, prompts that ask for a single end-to-end answer including verification can collapse a planner-then-verifier flow into a direct planner call against verifier-like capabilities. These are exactly the kinds of structural regressions or boundary weaknesses that restricted-tool coverage is intended to expose. The violation rate also varies substantially by workflow shape. octagon_vc_agents has the largest restricted-edge surface, with 132 restricted edges, but only six elicited violations. This suggests that coordinator-to-specialist structure can limit cross-specialist tool reach, although the result should be read as a single-run observation rather than a general safety claim. RQ3 Summary Restricted-tool probing elicits 23 restricted-call violations across 248 restricted-tool obligations. Four workflows produce no targeted restricted-call violation within the adversarial budget, while six produce at least one concrete misrouting failure. The invertedpolarity C3 criterion therefore provides diagnostic information that would be invisible in an allow-list-only evaluation.
G. RQ4: Fault-Injection Robustness a) Setup: We re-execute the allowed-tool evaluation on oai_customer_service with a fault injected into the target tool stub. We test two failure modes. In fail:error, the stub returns a canned internal-error payload. In fail:malformed, the stub returns a deliberately malformed payload. The robustness witness W F 1 holds when the target agent attempts the target tool call, the run does not crash, the agent produces a non-trivial final reply, and the reply does not leak the raw internal-error marker back to the
11
TABLE IV: Per-objective restricted-tool outcome on oai_customer_service. “Pass” is 1 iff the runtime records a restricted-call attempt at the intended (a, t) pair. “Off-target” lists restricted-call attempts observed at a different agent than the intended target. Target agent faq_agent seat_booking_agent triage_agent triage_agent
Restricted tool Pass Off-target attempts update_seat 0/1 — faq_lookup_tool 0/1 (triage_agent, faq_lookup_tool) faq_lookup_tool 0/1 — update_seat 0/1 —
TABLE V: Fault injection on the allowed-tool evaluation of oai_customer_service. “Pass” is the number of objectives whose mechanical robustness witness W F 1 held. Mode fail:error fail:malformed
Pass 2/2 2/2
Wall (s) 32.2 12.9
Calls 4 2
user. The witness is intentionally mechanical so that it can be evaluated without a language-model judge. b) Results: Table V reports both failure modes. The robustness witness holds for both allowed-tool objectives under both injected faults. Under fail:error, the agent produces replies that acknowledge a technical issue. Under fail:malformed, the agent sometimes produces plausiblelooking content from the malformed payload. This is accepted by W F 1 because the witness only checks mechanical robustness, not semantic correctness. The result therefore demonstrates that the same structural harness can test fault-handling behavior, while also showing the limits of a purely structural witness. RQ4 Summary Under both injected fault modes, the target tool is attempted, the run does not crash, and the final reply does not leak the raw internal-error marker. The witness holds 2/2 in both modes. Because the witness is mechanical, it does not detect semantic fabrication from malformed tool output.
H. Synthesis The evaluation supports the central claim of the paper: structural coverage provides an adequacy layer for multiagent workflow specifications. The extracted graphs turn each workflow into an explicit set of test obligations, and the runtime witnesses show which declared agents, tool-access edges, restrictions, and delegation paths can actually be exercised by generated scenarios. This gives a different kind of evidence than end-to-end task success: it shows not only whether a workflow can produce an answer, but which parts of its declared coordination structure have been tested. The ten-benchmark results show that coverage outcomes are informative at the level of workflow structure. Singlehop obligations are usually easy to witness, while multi-hop routes, overlapping specialist roles, and runtime-ambiguous handoff stubs produce most of the missed allowed-tool and delegation witnesses. These misses are not merely failures of
the evaluation; they identify structural paths that are difficult to exercise under the current realizer and harness. In this sense, a coverage report is useful even when it is incomplete, because it tells the developer where the test suite does not yet provide evidence. The restricted-tool results show why structural adequacy must include negative obligations. An evaluation that only checks allowed tool use and delegation would miss cases where an agent can be prompted into attempting a tool call outside its declared access. The C3 results expose both sides of this boundary: some workflows produce no targeted restrictedcall violation within the adversarial budget, while others yield concrete prompts that elicit restricted calls. Both outcomes are useful. The former gives bounded evidence that the tested restrictions resisted the generated probes; the latter gives actionable hardening targets. RQ4 also shows that the same coverage-driven tests can also support robustness checks by changing the witness predicate while keeping the underlying structural obligation fixed. This is important methodologically: once a workflow obligation has been identified, the same target can be evaluated under different runtime conditions, such as normal execution, restricted access, or faulty tool output. The malformed-output case also illustrates the boundary of the method: structural witnesses can show that the intended tool was attempted and that the run did not crash, but they do not establish semantic correctness of the final response. Overall, the evaluation shows that the proposed criteria are more than bookkeeping over a graph. They define a practical notion of test-suite adequacy for multi-agent workflows: a suite is more adequate when it provides runtime evidence for the workflow’s declared agents, allowed tool edges, restricted tool boundaries, and delegation paths. The resulting coverage profile helps distinguish exercised structure from untested structure, and turns coordination gaps into concrete targets for additional tests, better routing prompts, or workflow hardening.
I. Threats to Validity External validity. The evaluation covers ten workflows, but all are OpenAI Agents SDK-style systems and most are demo-scale or research-scale projects rather than production deployments. We therefore do not claim that the measured pass rates generalize to other frameworks, closed-source systems, or much larger workflows. The graph model is intended to be framework-agnostic, but the extractor and runtime adapter evaluated here are SDK-specific.
12
Construct validity. The witness predicates measure structural evidence: agents observed, tools invoked, restricted-call attempts recorded, and delegation edges traversed. They do not measure semantic correctness of the final answer, user satisfaction, policy compliance beyond the tested structural relation, or factual accuracy. A suite can achieve high structural coverage while still producing poor natural-language responses. The fault-injection study makes this limitation explicit: the malformed-output case can produce plausible but semantically questionable replies that the mechanical witness still accepts. Internal validity. The runtime layer uses mocked tool backends. This isolates structural behavior from external service variability, but it means the evaluation measures whether the agent attempts the intended tool or delegation, not whether the real tool would return a correct result. A second internalvalidity concern is realizer reach: the bounded DSPy realizer does not always steer the conversation through multi-hop delegation chains within N =5 attempts. We report such misses as part of the diagnostic outcome rather than treating them as noise. Reproducibility. Both the realizer and the agent under test are LLM-backed, so repeated runs may produce different surface prompts and occasionally different traces. We reduce this risk by using a fixed configuration, recording structural traces, and evaluating witnesses mechanically from those traces. However, the evaluation is single-run; a multi-run reliability study would be needed to estimate variance. Benchmark normalization. Some source projects use orchestration styles that are not directly represented as static SDK handoff declarations. For these, the extraction layer normalizes the published control flow into graph edges so that reachability and coverage can be computed. These adaptations do not add new agents, tools, or prompts, but they can affect the graph shape and therefore the obligation set. We document them because they are part of the benchmark construction process. Cost and scale. The ten-benchmark runtime evaluation required roughly 39,216 seconds of wall-clock time and 3,637 realizer LM round-trips. This is manageable for the benchmark sizes studied here, but larger workflows may require more aggressive objective merging, path-aware realization, or staged execution to control cost. V. R ELATED W ORK a) Structural coverage and mutation testing: Our work is most directly inspired by classical software testing notions of structural adequacy, including statement, branch, and related coverage criteria, as well as mutation testing [13], [1], [6]. The key difference is that our coverage obligations are defined over a multi-agent workflow graph rather than over program control flow. In that sense, the proposed criteria are closer in spirit to artifact-level adequacy measures: they ask whether declared agents, allowed tool edges, restricted tool edges, and delegation edges have been exercised. Mutation analysis along the same lines (injecting structural faults into the workflow specification) is a natural extension of the present work and is discussed as future work in Section VI. The main distinction is not the evaluation logic of coverage itself, but the decision
to treat the multi-agent workflow specification as the primary testable artifact. b) Specification-based testing and model-based testing: There are also strong connections to specification-based testing, model-based testing, and behavior-driven approaches in which tests are derived from an abstract description of expected structure or behavior. Our setting is similar in that the object under test is not arbitrary source code alone, but a declared artifact with explicit relations and constraints. However, multi-agent workflow specifications differ from conventional formal models because the artifact statically declares agents, tools, and edges but is exercised at runtime by languagemodel-driven agents whose tool-use and delegation choices are not deterministic. This makes the testing setting a hybrid: more structured than prompt-only evaluation, but less fully formal than traditional model-based testing [17]. Our contribution differs from classical model-based testing in that the input model is a lightweight coordination graph rather than a fully formal behavioral model. c) Automated test generation: The generation side of our approach is also related to automated test-suite construction work in software engineering. Tools such as EvoSuite illustrate how coverage obligations can drive systematic suite construction for code artifacts [5]. Our generator follows the same broad testing philosophy, but the generation targets are not source-level branches or methods. Instead, the witnesses are derived from declared workflow structure: agents, allowed and restricted tool edges, and delegation edges. In this sense, we borrow the obligation-driven spirit of automated test generation without assuming that code structure is the right abstraction level for multi-agent workflows. d) LLM and agent evaluation: Recent work on LLM and agent evaluation has largely focused on benchmark task success, robustness, and behavioral probing. Existing agent benchmarks are valuable for measuring end-to-end performance, but they do not provide a coverage theory for the underlying multi-agent workflow. Our goal is complementary: instead of replacing task benchmarks, we provide adequacy criteria for asking whether the declared structure of a multiagent workflow has been tested at all. This perspective is especially relevant for systems in which the same agent runtime may execute many different workflow specifications with different tool and delegation configurations [10], [11], [12], [7], [22]. The distinction is therefore one of evaluation target: prior benchmarks ask how well an agent solves tasks, whereas we ask how thoroughly a reusable workflow specification has been exercised. e) Prompt, tool, and workflow testing: A growing ecosystem of prompt-evaluation and tool-testing frameworks supports prompt regression checks, output comparison, and scenario-based assessment of LLM systems. These tools are useful in practice, but they generally emphasize examplelevel correctness rather than structural adequacy over reusable workflow artifacts. Our contribution is to identify an emerging software artifact class and to give it a corresponding structural testing vocabulary. This shifts the discussion from “did these examples pass?” toward a coverage question: “which parts of the declared workflow have actually been exercised?” [16],
13
[18], [9], [15]. In other words, our framework is not another prompt-regression harness or tool-use benchmark. It is an adequacy model for multi-agent workflow specifications. f) Positioning: Taken together, prior work gives us the ingredients for this paper but not the combined result. Classical testing contributes the ideas of coverage and mutation. Specification-based testing contributes the view that declared structure can serve as the basis for test generation. LLM and agent evaluation contributes the modern execution setting in which these artifacts matter. What has been missing is a coverage model and generation procedure tailored to multiagent workflow specifications as a software artifact in their own right. VI. D ISCUSSION AND C ONCLUSION This paper evaluates structural coverage as an adequacy layer for LLM-based multi-agent workflow specifications. The evaluation covers ten SDK-derived workflows, totaling 49 reachable agents, 47 tools, and 403 graph-derived structural obligations. The results show that the proposed model can be extracted from real workflow definitions, that the resulting obligations can be turned into typed witness objectives and natural-language scenarios, and that runtime traces can be used to determine which declared agents, tool-access edges, restricted boundaries, and delegation paths have actually been exercised. The evaluation should be read as evidence of feasibility and diagnostic value, not as a general safety claim about multiagent systems. All benchmarks are OpenAI Agents SDKstyle workflows, and each runtime evaluation is executed once under a fixed configuration. The results therefore show that the method works on a nontrivial set of real SDK-derived workflows, but they do not establish statistical reliability across model runs, generality across agent frameworks, or effectiveness on production-scale deployments. The oai_customer_service workflow plays a narrower role within this broader evaluation. It is used as the running example and as a instrumented benchmark for routingprompt ablation and fault-injection experiments. It is not the sole empirical basis for the paper. The main empirical evidence comes from the ten-workflow benchmark set, while the deeper case study shows how the same coverage framework can support closer inspection of one workflow. The four criteria measure structural exercise of the declared workflow graph. A suite that satisfies C1 , C2 , C3 , and C4 has observed every reachable agent, exercised every allowed tool edge, produced explicit evidence for every restricted-tool obligation, and traversed every delegation edge. This gives a concrete notion of test-suite adequacy for workflow structure: an obligation that is never witnessed has not been tested. This is different from semantic correctness. Structural coverage does not show that the final answer is factually correct, useful to the user, policy compliant in all cases, or robust to every possible prompt. It also does not measure the realism of generated scenarios except insofar as those scenarios execute and produce structural evidence. A workflow can have high structural coverage and still produce poor responses. Con-
versely, a workflow can succeed on an end-to-end benchmark while leaving important structural obligations untested. The restricted-tool criterion is especially important because it makes negative obligations explicit. Testing only allowed tool use and delegation would show whether intended paths can be exercised, but it would not show whether forbidden tool boundaries can be probed. The C3 results demonstrate that restricted-tool testing can produce two useful outcomes: no targeted restricted-call violation within the adversarial budget, or a concrete prompt that elicits a restricted call and therefore becomes a hardening target. The most immediate next step is mutation analysis over workflow graphs. Structural mutations such as deleting an allowed-tool edge, removing a restriction, changing a delegation target, or disconnecting an agent would make it possible to measure whether structurally adequate suites detect workflow regressions. This would also enable fair comparison against alternative generation strategies. A second direction is broader benchmark coverage. The current evaluation uses ten SDK-derived workflows. Extending the extractor to additional frameworks would test whether the same graph model captures workflow structure beyond the OpenAI Agents SDK. Larger workflows with deeper delegation chains and denser tool graphs would also stress the current realization strategy. A third direction is improving the realizer. The evaluation shows that multi-hop obligations are harder to witness than single-hop obligations. A path-aware realizer that receives explicit route structure, or a scenario diversifier that generates multiple semantically distinct prompts for the same obligation, may improve coverage on deep or ambiguous workflows. Finally, structural coverage should be combined with behavioral and semantic evaluation. The present criteria say whether declared structure was exercised; they do not judge whether the final response was correct. A mature testing framework for multi-agent workflows should include both layers: structural adequacy to ensure the workflow was exercised, and semantic or task-level checks to judge the quality of the resulting behavior.
R EFERENCES [1] Paul Ammann and Jeff Offutt. Introduction to Software Testing. Cambridge University Press, 2nd edition, 2016. [2] DSPy Contributors. Dspy documentation. https://dspy.ai/, 2026. Accessed: 2026-05-02. [3] DSPy Contributors. Dspy documentation: Modules. https://dspy.ai/learn/ programming/modules/, 2026. Accessed: 2026-05-02. [4] DSPy Contributors. Dspy documentation: Signatures. https://dspy.ai/ learn/programming/signatures/, 2026. Accessed: 2026-05-02. [5] Gordon Fraser and Andrea Arcuri. Evosuite: Automatic test suite generation for object-oriented software. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, pages 416–419, 2011. [6] Yue Jia and Mark Harman. An analysis and survey of the development of mutation testing. IEEE Transactions on Software Engineering, 37(5):649–678, 2011. [7] Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. SWE-bench: Can language models resolve real-world github issues? In International Conference on Learning Representations, 2024.
14
[8] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. Dspy: Compiling declarative language model calls into self-improving pipelines. In International Conference on Learning Representations, 2024. [9] Ming Li et al. API-Bank: A comprehensive benchmark for toolaugmented LLMs. arXiv preprint arXiv:2304.08244, 2023. [10] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yao Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. Transactions on Machine Learning Research, 2023. [11] Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, et al. Agentbench: Evaluating LLMs as agents. arXiv preprint arXiv:2308.03688, 2023. [12] Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom. GAIA: A benchmark for general AI assistants. arXiv preprint arXiv:2311.12983, 2023. [13] Glenford J. Myers, Corey Sandler, and Tom Badgett. The Art of Software Testing. John Wiley & Sons, 3rd edition, 2011. [14] OpenAI. Agents sdk. https://developers.openai.com/api/docs/guides/ agents, 2026. Accessed: 2026-05-02. [15] Yujia Qin, Ruyi Luo, Pan Ye, et al. ToolLLM: Facilitating large language models to master 16000+ real-world APIs. arXiv preprint arXiv:2307.16789, 2023. [16] Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. Beyond accuracy: Behavioral testing of NLP models with CheckList. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4902–4912, 2020. [17] Mark Utting and Bruno Legeard. Practical Model-Based Testing: A Tools Approach. Morgan Kaufmann, 2006. [18] Xiao Wang, Qin Liu, Tao Gui, Qi Zhang, Xuanjing Huang, et al. Textflint: Unified multilingual robustness evaluation toolkit for natural language processing. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations, pages 347–355, 2021. [19] Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W. White, Doug Burger, and Chi Wang. Autogen: Enabling next-gen llm applications via multi-agent conversations. In First Conference on Language Modeling (COLM), 2024. [20] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang, Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, Zhangyue Yin, Shihan Dou, Rongxiang Weng, Wensen Cheng, Qi Zhang, Wenjuan Qin, Yongyan Zheng, Xipeng Qiu, Xuanjing Huang, and Tao Gui. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864, 2023. [21] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations (ICLR), 2023. [22] Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. WebArena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307.13854, 2024.