💻 computer science

Testing Agentic Workflows with Structural Coverage Criteria

This paper introduces a structural testing approach for multi-agent workflows that models them as coordination graphs to derive coverage obligations, which are then realized as executable tests via DSPy to verify that declared agents, tool-access rules, restrictions, and delegation paths are actually exercised.

Original authors: Nafiseh Kahani, Mojtaba Bagherzadeh

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nafiseh Kahani, Mojtaba Bagherzadeh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a team of specialized robots to run a customer service department. You give them a strict rulebook: "Robot A can only check flight schedules, Robot B can only book seats, and Robot C is the manager who decides who does what." You also write down specific rules like, "Robot A is forbidden from booking seats."

Now, imagine you want to test if this team is working correctly.

The Old Way (The "Happy Path" Test)
Traditionally, testers would just ask the team a simple question: "I need to book a seat." If the team successfully books the seat, the test is a "pass."

The Problem: This doesn't prove the team followed the rules. Maybe Robot A tried to book the seat, but Robot B just took over anyway. Or maybe Robot A never even saw the request. The test passed, but you have no idea if the specific rules you wrote down were actually followed. You might have a "hidden" robot that never gets used, or a forbidden action that was never checked.

The New Way (Structural Coverage)
This paper proposes a new way to test these AI teams. Instead of just checking if the final job got done, they check if every single rule and connection in the rulebook was actually used.

Think of the team's rulebook as a map of a subway system:

Stations are the different AI agents (Robots).
Tracks are the paths where they pass tasks to each other (Delegation).
Train lines are the tools they can use (like "Check Flight" or "Book Seat").
Red Zones are the tracks they are strictly forbidden from entering (Restricted Tools).

The authors' method treats the rulebook like this subway map. They don't just ask, "Did the train get to the destination?" They ask:

Did the train visit every station? (Did every robot get a turn?)
Did the train travel on every allowed track? (Did every robot use every tool it was allowed to?)
Did the train try to enter a Red Zone and get stopped? (Did we prove that the forbidden rules actually work?)
Did the train switch lines at every transfer point? (Did the robots hand off tasks correctly?)

How They Do It
The researchers built a system that acts like a super-smart scriptwriter (using a tool called DSPy).

Reading the Map: First, the system reads the code and draws the subway map (the "coordination graph").
Writing the Scenarios: It then writes specific, natural-language requests designed to force the AI team to use specific parts of the map.
- Example: To test a "Red Zone," it might ask the manager robot, "Please book a seat for me," hoping the manager tries to do it directly (which is forbidden). If the system catches the manager trying to break the rule and stopping itself, that's a successful test of the restriction.
The Reality Check: The system runs these scenarios against the real AI team. It doesn't just look at the final answer; it watches the internal logs to see exactly which robot spoke, which tool was clicked, and which handoff happened.

What They Found
They tested this on 10 different AI team setups (ranging from simple customer service bots to complex research teams).

The Good News: Their method successfully generated tests that proved the AI teams were using their allowed tools and passing tasks to each other correctly.
The "Red Zone" Discovery: When they tried to trick the AI teams into breaking the rules, they found that some teams were very good at stopping themselves (0 violations), while others accidentally tried to use forbidden tools (violations found). This is valuable because it shows exactly where the rules are weak.
The Limit: They found that if a task requires passing through many different robots (a long subway ride), it's harder for their scriptwriter to get the AI to take that exact path every time.

The Bottom Line
This paper argues that just because an AI team solves a problem doesn't mean it's following its design. You need to check the structure of the team, not just the result.

It's like checking a car: You don't just drive it to the store to see if it works. You also check if the brakes were tested, if the airbags deployed in a crash test, and if the engine oil was changed. This paper gives us a checklist to make sure every part of an AI team's design has been tested, ensuring that the rules we set are actually being followed.

Technical Summary: Testing Agentic Workflows with Structural Coverage Criteria

Problem Statement

Multi-agent systems are increasingly deployed as structured workflows where agents, tools, access rules, and delegation paths are explicitly defined. However, current evaluation practices rely heavily on end-to-end task success, benchmark scores, and final-response quality. These metrics provide limited evidence that the declared coordination structure has actually been exercised. A workflow may complete a task successfully while leaving specific tools uninvoked, restricted access rules untested, or delegation paths unexplored. Consequently, it is difficult to assess test-suite adequacy or detect structural regressions in tool access and inter-agent delegation. The paper argues that end-to-end success is an unreliable proxy for structural coverage in multi-agent systems, particularly as workflows evolve and small definition changes may alter structural obligations without causing immediate task failures.

Methodology

The authors propose a structural testing approach that treats multi-agent workflow specifications as the primary testable artifact. The methodology follows a five-step pipeline:

Specification Extraction: A normalized multi-agent workflow specification ( $S$ ) is extracted from source code (specifically OpenAI Agents SDK-style workflows). This specification defines reachable agents, allowed tool edges, restricted tool edges, and delegation edges.
Graph Construction: The specification is converted into a typed coordination graph $G(S)$ , where nodes represent agents and tools, and edges represent allowed access, restricted access, and delegation relations.
Obligation Derivation: Structural obligations are derived from the graph, categorized into four sets:
- Reachable agents ( $A_{reach}$ )
- Allowed tool edges ( $T_{allow}$ )
- Restricted tool edges ( $T_{restrict}$ )
- Delegation edges ( $D$ )
Coverage-Driven Generation: The system synthesizes "typed witness objectives" from the obligation sets. These objectives are realized as natural-language test scenarios using DSPy, a declarative framework for language model pipelines. Crucially, DSPy is used only for scenario realization, not for defining coverage. The generator employs a bounded refinement loop (up to $N=5$ attempts) where candidate prompts are executed against a runtime adapter. The loop terminates only when the execution produces the specific structural evidence required by the objective (e.g., a specific tool call or delegation handoff).
Runtime Observation and Measurement: Tests are executed via a runtime adapter that records structural traces. Coverage is measured by checking if the observed traces satisfy the witness predicates for each obligation.

Coverage Criteria

The paper defines four structural coverage criteria:

C1 (Agent Coverage): Every reachable agent is observed.
C2 (Allowed-Tool Coverage): Every allowed agent-tool edge is exercised.
C3 (Restricted-Tool Coverage): Every restricted agent-tool edge is exercised through an explicit restricted-access observation (e.g., a refusal or rejection event), rather than merely the absence of a call. This is treated as an adversarial test.
C4 (Delegation Coverage): Every reachable delegation edge is observed.

Key Contributions

The paper makes four primary contributions:

Formulation: It formulates multi-agent workflow testing as a structural adequacy problem over typed coordination graphs derived from agent-framework source code.
Coverage Model: It defines graph-derived coverage criteria for reachable agents, allowed tool edges, restricted tool edges, and delegation edges. Notably, it treats restricted-tool coverage as an explicit negative-observation obligation.
Generation Pipeline: It presents 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.
Empirical Evaluation: It evaluates the approach on ten OpenAI Agents SDK-derived workflows, totaling 49 reachable agents, 47 tools, and 403 structural obligations, including a detailed analysis of the oai_customer_service workflow.

Experimental Results

The evaluation was conducted on ten benchmarks with a fixed configuration (using gpt-4.1-mini for both the realizer and the agent under test).

Extraction (RQ1): The pipeline successfully extracted well-formed coordination graphs and derived structural obligations for all ten workflows without manual intervention.
Allowed-Tool and Delegation Witnesses (RQ2):
- Generated scenarios witnessed 54/75 (72%) allowed-tool obligations (aggregated across benchmarks, the paper notes 45/65 in Table II, but the abstract states 54/75; the text clarifies 45/65 in the results section).
- Generated scenarios witnessed 36/48 (75%) delegation obligations (aggregated; Table II shows 31/41).
- Single-hop targets passed uniformly. Misses occurred primarily in multi-hop workflows or where semantic overlap caused the coordinator to route to a different specialist.
Restricted-Tool Adversarial Witnesses (RQ3):
- Adversarial probing elicited 23/248 (9.3%) restricted-call violations.
- Four benchmarks produced no targeted violations, while six produced concrete misrouting failures. This demonstrates the criterion's ability to distinguish workflows with robust restrictions from those with exploitable boundaries.
Fault Injection (RQ4): On the oai_customer_service benchmark, the structural harness successfully tested robustness under injected tool faults (error and malformed payloads), confirming that the agent attempted the tool and did not crash or leak raw error payloads, though it did not verify semantic correctness.

Significance and Claims

The paper claims that structural coverage provides a useful adequacy layer for multi-agent workflow testing. It does not replace semantic evaluation or end-to-end benchmarks but offers explicit evidence that declared agents, tool-access rules, restrictions, and delegation paths have been exercised.

Diagnostic Value: The approach reveals "untested structure." Missed obligations identify specific coordination paths that are difficult to exercise, guiding developers to improve routing prompts or workflow hardening.
Negative Obligations: By explicitly testing restricted-tool edges, the method uncovers vulnerabilities (concrete prompts that bypass restrictions) that would remain invisible in allow-list-only evaluations.
Limitations: The authors are modest about their claims, noting that the results are single-run empirical evidence rather than statistically powered estimates. They acknowledge that high structural coverage does not guarantee semantic correctness, user satisfaction, or factual accuracy. The method is currently specific to OpenAI Agents SDK-style workflows, and the bounded refinement loop sometimes fails to witness complex multi-hop obligations within the attempt budget.

The paper concludes that structural testing complements existing agent evaluations by shifting the focus from "did the task succeed?" to "which parts of the declared workflow were actually tested?"