Skip to content

Testing Agentic Workflows with Structural Coverage Criteria

🕒 Published (v1): 2026-05-26 04:07 UTC · Source: Arxiv · link

Why this paper was selected

Structural coverage criteria for agentic workflow testing beyond task-success metrics

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper proposes structural testing for multi-agent workflows by modeling workflows as typed coordination graphs and deriving graph-based coverage criteria (reachable agents, allowed tool edges, restricted tool edges, delegation edges). A DSPy-based test generation pipeline converts structural obligations into natural-language test scenarios, then verifies at runtime that each obligation was actually witnessed. On ten OpenAI Agents SDK benchmarks with 403 total structural obligations, the approach covers 54/75 allowed-tool and 36/48 delegation obligations, and elicits 23/248 concrete restricted-tool violations.

Problem

Multi-agent workflow evaluation relies almost entirely on end-to-end task success, benchmark scores, or final-response quality. This provides no evidence that the declared coordination structure—tool-access rules, restricted tool edges, delegation paths—was actually exercised. A workflow can pass all task-level tests while leaving entire branches of its agent topology untested, making it impossible to assess test-suite adequacy or detect structural regressions when workflow specifications change.

Method

The approach represents a multi-agent workflow specification as a typed coordination graph \(G(S) = \langle V_A, V_T, E_{allow}, E_{restrict}, E_{del} \rangle\), where \(V_A\) are agent nodes, \(V_T\) are tool nodes, and the three edge sets encode allowed tool access, restricted tool access, and delegation.

From the reachable subgraph, four obligation sets are derived: - \(\Omega(S) = \langle A_{reach}, T_{allow}, T_{restrict}, D \rangle\)

Four coverage criteria (C1–C4) map to agent reachability, allowed-tool witnessing, explicit restricted-access events, and delegation witnessing. Coverage is \(\text{Cov}(X, O, W) = |\{\omega \in O \mid \exists x \in X : W(x,\omega)\}| / |O|\).

A two-layer generator then operates: (1) a deterministic layer produces typed witness objectives via rules R1–R4; (2) a DSPy-based realization layer maps each objective to a natural-language scenario using criterion-specific signatures (RealizeReach, RealizeUseTool, RealizeRestrictTool, RealizeDelegate). Each candidate is executed through a runtime adapter; a binary reward \(r(z) = 1\) iff the scenario produces the required structural evidence without leaking forbidden identifiers. A dspy.Refine loop runs up to \(N = 5\) attempts per objective. Compatible objectives are merged into bundles to reduce suite size.

Key Contributions

  • Formulation of multi-agent workflow testing as a structural adequacy problem over typed coordination graphs derived from framework source code (OpenAI Agents SDK).
  • Four graph-derived coverage criteria (C1–C4) spanning reachable agents, allowed tool edges, restricted tool edges, and delegation edges; restricted-tool coverage is an explicit negative-observation obligation, not mere absence of a call.
  • A coverage-driven test-generation pipeline: deterministic obligation extraction → typed witness objectives → DSPy-based scenario realization with runtime-grounded refinement.
  • Evaluation on ten SDK-derived workflows (49 agents, 47 tools, 403 structural obligations) including routing-prompt ablation and tool-fault robustness on an instrumented benchmark.

Results

  • Allowed-tool coverage (C2): 54/75 obligations witnessed (72%).
  • Delegation coverage (C4): 36/48 obligations witnessed (75%).
  • Restricted-tool violations (C3): 23/248 adversarial probes elicited concrete restriction violations, distinguishing workflows with robust restrictions from those with misrouting failures.
  • Agent coverage (C1): Implied complete across evaluated workflows (reachable agents are a prerequisite for tool/delegation coverage).
  • All results are within a bounded refinement budget of \(N = 5\) attempts per objective.
  • The approach separated compliant workflows from those with concrete structural failures under adversarial probing—a distinction end-to-end success metrics could not make.

Limitations

  • Restricted-tool coverage yield (23/248, ~9%) is low; most adversarial probes do not elicit violations, so restriction robustness is underexplored.
  • Allowed-tool and delegation coverage gaps (21/75 and 12/48 unwitnessed) indicate that some structural obligations cannot be realized within a budget of 5 refinement attempts.
  • The implementation is prototype-level, targeting only the OpenAI Agents SDK; generalization to other frameworks (LangGraph, AutoGen, custom harnesses) is not demonstrated.
  • Witness verification relies on runtime adapter instrumentation; tool faults or missing runtime traces can cause false negatives.
  • The approach tests structure only—semantic correctness, output quality, and safety are explicitly out of scope.
  • Coverage criteria assume a closed-world specification; undeclared agent–tool pairs generate no obligations and may harbor real access violations.

Relevance to Harnesses / Meta-Harnesses

This paper directly addresses the testing and verification layer for multi-agent workflow harnesses: it treats the harness specification itself (agents, tools, access rules, delegation paths) as the artifact under test. The structural coverage model and DSPy-based test generation form a meta-harness—a system that takes a workflow harness specification as input and produces executable tests to verify its coordination structure. For researchers building or auditing meta-harnesses, the typed coordination graph abstraction and the separation of structural adequacy from semantic evaluation provide a principled framework for regression detection when harness configurations change.