Structured Testing of Multi-Agent Workflows: From End-to-End Success Rate to Coverage Validation

Core Insight: Existing multi-agent system evaluations rely on end-to-end task success rates, which cannot verify whether the claimed coordination structure is actually triggered. A study published on arXiv in May 2026 proposes a structured coverage testing method. Using typed coordination graphs, coverage obligation derivation, and DSPy scenario generation, it generates executable tests for 403 structural obligations, supplementing the shortcomings of end-to-end testing and revealing structural defects such as zombie agents and ghost tools.

As the complexity of LLM multi-agent systems increases, workflows include multiple roles, tool sets, access rules, constraints, and delegation paths. However, existing tests only focus on end-to-end results, leading to blind spots:

• An agent is never invoked
• Some tool access rules are not verified
• Constraints never take effect
• Delegation paths exist but are not used This is like software testing that only looks at output without checking code branches, easily missing structural defects.

Core Steps of Structured Testing:

1. Typed Coordination Graph: Nodes are agents; edges represent tool calls, restricted calls, and delegation relationships, with interaction types labeled.
2. Coverage Obligation Derivation: Need to verify each agent's triggering, allowed tool calls, adversarial testing of restricted tools, and execution of delegation paths.
3. DSPy Scenario Generation: Convert obligations into natural language scenarios for runtime verification. Innovation: Adversarial testing of restricted tools—proactively attempting to violate forbidden calls to verify the effectiveness of restriction mechanisms (triggered 23/248 violations in 10 SDK benchmarks).

10 benchmark tests based on OpenAI Agents SDK:

• 49 agents, 47 tools, 403 obligations Coverage Results:
• Allowed tools: 54/75 (72%)
• Delegation obligations:36/48 (75%)
• Restriction violation triggers:23/248 (9.3%) Discovered Defects: Zombie agents, ghost tools, paper constraints, dead-end delegations—these are easily overlooked in end-to-end testing.

Limitations of End-to-End Testing: Opaque paths, incomplete coverage, weak regression detection. Value of Structured Testing: Explicitly verify the triggering of structural elements, strong regression detection, validate design intent, align with documentation. Analogy to Software Testing:

Software Testing	Multi-Agent Testing
Line coverage	Agent trigger coverage
Branch coverage	Tool call path coverage
Boundary testing	Adversarial testing of restriction rules
Integration testing	Delegation path validation

Application Scenarios:

• Development Phase: Identify unused agents/tools, verify coverage of new structures.
• Code Review: Include coverage reports as part of PR reviews.
• CI/CD: Integrate structural coverage into pipelines; trigger alerts if coverage drops.
• Production Monitoring: Collect actual coverage and compare with expected values.

Limitations:

• Scenario generation quality depends on DSPy prompts and model capabilities.
• Some obligations are hard to trigger via natural language.
• Only supports static workflow structures.
• Does not verify if triggers are correct (needs to combine with semantic testing). Future Directions:
• Efficient scenario generation algorithms.
• Reinforcement learning-based adversarial testing.
• Dynamic workflow expansion.
• Coverage visualization tools.

Structured coverage testing adds a new dimension to multi-agent quality assurance, answering the question: 'Is the designed structure actually used?' As multi-agent deployments become widespread, structured testing may become a standard practice, similar to the role of code coverage in software engineering.