Testing Agentic Workflows with Structural Coverage Criteria

• URL: http://arxiv.org/abs/2605.26521v1
• Date: Tue, 26 May 2026 04:07:55 GMT
• Title: Testing Agentic Workflows with Structural Coverage Criteria
• Abstract summary: We present a structural testing approach for multi-agent workflow specifications.<n>The approach represents each workflow as a typed coordination graph.<n>It derives coverage obligations over reachable agents, allowed tool edges, restricted tool edges, and delegation edges.
• Score: 0.21485350418225244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent systems increasingly expose explicit workflow structure: agents, tools, tool-access rules, restrictions, and delegation paths. Existing evaluations rely largely on end-to-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 restricted-tool 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 multi-agent 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.

Related papers

• Formal Verification of Agentic Systems over Operational Data [59.98246281888422]
  Agentic systems driven by large language models (LLMs) are increasingly deployed in real-world where they act on persistent operational data.<n>Existing approaches do not provide such system-level guarantees.<n>We study here the verification of agentic systems comprising a single LLM and a tool orchestration harness over relational operational data.
  arXiv  Detail & Related papers  (2026-08-04T13:01:30Z)
• StructureClaw: Traceable LLM Agents and an Executable Benchmark for Structural Engineering Workflows [15.552044829103373]
  We present StructureClaw, an artifact-centered workbench for structural engineering requests.<n>We also introduce StructureClaw-Bench, an executable benchmark of 150 controlled scenarios.<n>Across ten agent-model configurations, each evaluated on the same 50 standard cases, the average Success Rate rises from 56.8% with the generic-skill baseline to 88.6% with the full automatic workflow.
  arXiv  Detail & Related papers  (2026-07-16T12:13:41Z)
• A Five-Plane Reference Architecture for Runtime Governance of Production AI Agents [0.0]
  We present a reference architecture for the governance of production AI agents.<n>We define a taxonomy of six interruption primitives that generalize allow and deny, state and argue for four correctness invariants.<n>We demonstrate the foreclosure of seven production-agent threats across five concrete adjudications.
  arXiv  Detail & Related papers  (2026-06-10T16:54:47Z)
• Queen-Bee Agents: A BeeSpec-Centered Architecture for Governed Enterprise MCP Orchestration [0.0]
  We present Queen-Bee, a governed multi-agent architecture in which a Queen control plane retrieves capabilities, plans task-scoped execution, and compiles a structured BeeSpec.<n>We evaluate the system on 59 enterprise-style tasks spanning governance-sensitive requests, retrieval-driven provisioning, scoped local execution, and chemistry workflow integration.<n>The retrieval-driven Queen-Bee variant achieves a task success rate of 0.964, zero governance failures, and substantially better scoped execution quality than both a static Queen-Bee baseline and a permissive single-agent baseline.
  arXiv  Detail & Related papers  (2026-06-04T07:12:00Z)
• What to Test Next: Interpretable Coverage Gap Discovery in Driving VLMs [52.50210189669399]
  Driving vision-language models (VLMs) must accurately understand scenes across diverse conditions defined by Operational Design Domains (ODDs)<n>We propose SliceScorer, a deterministic scoring rule for missing-slice recommendation.<n>We show that SliceNav surfaces high-risk coverage gaps more effectively than prior slice-discovery methods.
  arXiv  Detail & Related papers  (2026-06-01T03:18:01Z)
• Specifying AI-SDLC Processes: A Protocol Language for Human-Agent Boundaries [0.0]
  We propose a domain-specific language for specifying AI-SDLC processes as protocols.<n>The language distinguishes policy (declared intent) from mechanism (structural enforcement)<n>A working implementation demonstrates feasibility; empirical evaluation is future work.
  arXiv  Detail & Related papers  (2026-05-24T02:52:47Z)
• Governance by Construction for Generalist Agents [7.48004748585128]
  This demo presents CUGA's policy system, a modular policy-as-code layer that composes with a generalist agent to deliver predictable, auditable, and compliance-aware behavior.<n>We present a governance architecture that enforces policy interventions at every critical stage of execution.
  arXiv  Detail & Related papers  (2026-05-20T08:13:16Z)
• ClawForge: Generating Executable Interactive Benchmarks for Command-Line Agents [59.626170560327274]
  We present textbfClawForge, a generator-backed benchmark framework for executable command-line categories under state conflict.<n>We instantiate this framework as the ClawForge-Bench (17 scenarios, 6 ability categories)
  arXiv  Detail & Related papers  (2026-05-13T21:34:08Z)
• Beyond the All-in-One Agent: Benchmarking Role-Specialized Multi-Agent Collaboration in Enterprise Workflows [24.72893952080658]
  Large language model (LLM) agents are increasingly expected to operate in enterprise environments.<n>Existing benchmarks largely evaluate single agents with broad tool access.<n>We introduce textscEntCollabBench, a benchmark for evaluating enterprise multi-agent collaboration.
  arXiv  Detail & Related papers  (2026-05-09T07:47:07Z)
• SARC: A Governance-by-Architecture Framework for Agentic AI Systems [0.0]
  Agentic AI systems increasingly act through tools, sub-agents, and external services, but governance controls are still commonly attached to prompts, dashboards, or post-hoc documentation.<n>We introduce SARC, a runtime governance architecture for tool-using agents that treats constraints as first-class specification objects alongside state, action space, and reward.<n>SARC executes zero hard-constraint violations under exact predicates; its declared PAA throttling response reduces soft-window overages by 89.5% relative to policy-as-code-only.
  arXiv  Detail & Related papers  (2026-05-08T13:34:36Z)
• Constraint Decay: The Fragility of LLM Agents in Backend Code Generation [9.659020624935687]
  Large Language Model (LLM) agents demonstrate strong performance in autonomous code generation under loose specifications.<n>Production-grade software requires strict adherence to structural constraints, such as architectural patterns, databases, and object-relational mappings.<n>We present a systematic study evaluating how well agents handle structural constraints in backend generation.
  arXiv  Detail & Related papers  (2026-05-07T15:44:40Z)
• Claw-Eval-Live: A Live Agent Benchmark for Evolving Real-World Workflows [67.92316850084575]
  We introduce Claw-Eval-Live, a live benchmark for workflow agents.<n>Each release is constructed from public workflow-demand signals.<n>Claw-Eval-Live records execution traces, audit logs, service state, and post-run workspace artifacts.
  arXiv  Detail & Related papers  (2026-04-30T17:23:19Z)
• A Trace-Based Assurance Framework for Agentic AI Orchestration: Contracts, Testing, and Governance [0.22940141855172028]
  This paper presents an assurance framework for Agentic AI systems using Large Language Models (LLMs)<n>Executions are instrumented as Message-Action Traces (MAT) with explicit step and trace contracts.<n>The framework includes stress testing, formulated as a budgeted counterexample search over bounded perturbations.
  arXiv  Detail & Related papers  (2026-03-18T10:23:48Z)
• CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
  We introduce CCTU, a benchmark for evaluating large language models (LLMs) under complex constraints.<n>The benchmark comprises 200 carefully curated and challenging test cases across diverse tool-use scenarios.<n>We develop an executable constraint validation module that performs step-level validation and enforces compliance.
  arXiv  Detail & Related papers  (2026-03-16T14:05:13Z)
• SOPBench: Evaluating Language Agents at Following Standard Operating Procedures and Constraints [59.645885492637845]
  SOPBench is an evaluation pipeline that transforms each service-specific SOP code program into a directed graph of executable functions.<n>Our approach transforms each service-specific SOP code program into a directed graph of executable functions and requires agents to call these functions based on natural language SOP descriptions.<n>We evaluate 18 leading models, and results show the task is challenging even for top-tier models.
  arXiv  Detail & Related papers  (2025-03-11T17:53:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.