Verified Multi-Agent Orchestration: A Plan-Execute-Verify-Replan Framework for Complex Query Resolution¶

🕒 Published (v1): 2026-03-12 02:10 UTC · Source: Arxiv · Venue: ICLR 2026 · link

Ask a follow-up

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

TL;DR¶

VMAO (Verified Multi-Agent Orchestration) is a Plan-Execute-Verify-Replan framework that decomposes complex queries into a DAG of sub-questions, executes them in parallel via domain-specific agents, and iteratively replans based on LLM-driven completeness verification. On 25 market-research queries it raises completeness from 3.1 to 4.2 and source quality from 2.6 to 4.1 (1–5 scale) over a single-agent baseline. The key novelty is decoupling verification from individual agents and placing it at the orchestration level.

Problem¶

Existing multi-agent frameworks (AutoGen, MetaGPT, CAMEL) lack principled, orchestration-level quality verification and adaptive refinement. Debate-style approaches improve reasoning but not task decomposition; role-playing frameworks provide no completeness check; static pipelines cannot recover when initial agents return insufficient results. This makes them unsuitable for production settings requiring reliable, unsupervised complex-query resolution.

Method¶

VMAO runs a five-phase loop: Plan → Execute → Verify → Replan → Synthesize.

Planning: A QueryPlanner LLM decomposes the input query into a DAG of sub-questions, each annotated with agent_type, dependencies, priority, context_from_deps, and verification_criteria.
Execution: A DAGExecutor iteratively identifies "ready" sub-questions (dependencies satisfied) and dispatches them in parallel batches of \(k=3\) (default), with results from upstream nodes prepended to dependent prompts. A configurable 600 s timeout and a tool-call limiter (max 10 consecutive same-tool calls, 50 total per agent) bound execution.
Verification: A ResultVerifier (running Claude Opus 4.5, distinct from the execution model Sonnet 4.5) scores each result on completeness (0–1), labels it complete/partial/incomplete, and identifies missing aspects or contradictions. Already-complete results are cached to avoid redundant calls.
Replanning: An AdaptiveReplanner issues retry actions on low-scoring sub-questions, introduces new sub-questions targeting specific gaps, or merges multi-attempt results progressively.
Stop conditions (Table 2): any of—≥80% sub-questions complete, 75% confidence with ≥50% coverage, <5% improvement over prior iteration, 1M token budget, or 3 maximum iterations.
Synthesis: For results >15K characters or ≥10 items, hierarchical synthesis groups by agent type, condenses within groups, then integrates with source attribution.

Agents span three tiers: Tier 1 (Data: RAG, Web Search, Financial, Competitor), Tier 2 (Analysis, Reasoning), Tier 3 (Output: Document, Visualization), totaling 42 unique tools across 8 MCP servers. Implemented with LangGraph + Strands Agent on AWS Bedrock.

Key Contributions¶

DAG-based query decomposition enabling dependency-aware parallel execution with automatic upstream-context propagation.
Orchestration-level LLM verification decoupled from individual agent implementations, providing a principled coordination signal.
Configurable, multi-criterion stop conditions that make the quality-vs-cost tradeoff explicit and tunable.
Three-tier agent taxonomy with 42 tools across 8 MCP microservices, enabling horizontal scaling and fault isolation.
Hierarchical synthesis for large result sets that avoids context-window overflow.

Results¶

Completeness: Single-Agent 3.1 → Static Pipeline 3.5 → VMAO 4.2 (+35% over single-agent).
Source Quality: Single-Agent 2.6 → Static Pipeline 3.2 → VMAO 4.1 (+58% over single-agent).
Largest gain by category: Strategic Assessment queries +53% completeness (open-ended, multi-dimensional).
Modest gain: Performance Analysis (well-defined data sources already reachable by single agent).
Token cost: 100K (single-agent) → 850K (VMAO), ~8.5× increase; avg time 165 s → 900 s.
Token distribution in a typical run: execution 61%, synthesis 16%, verification 8%, planning 10%, replanning 5%.
75% of queries terminate via resource-based stop conditions (diminishing returns, max iterations, or token budget).
Human domain experts adjusted <15% of LLM evaluation scores, typically by ±0.5 points.

Limitations¶

Evaluation set of only 25 queries; no confidence intervals reported.
LLM judge (Opus 4.5) and execution model (Sonnet 4.5) belong to the same model family, risking shared bias despite human review.
No component-level ablation: Static Pipeline baseline tests verification and replanning jointly, making individual contributions unquantified.
LLM verifier assesses completeness, not factual accuracy—hallucinations present in well-sourced answers may pass verification.
Poor initial decomposition can propagate downstream: a misframed sub-question may yield a sourced but irrelevant answer that the verifier accepts.
8.5× token overhead and ~5.5× latency increase may be prohibitive for cost- or latency-sensitive deployments.
All experiments use a single model family (Claude); generalization to other LLM families untested.

Relevance to Harnesses / Meta-Harnesses¶

VMAO is a direct instantiation of the meta-harness pattern: a controller that orchestrates a fleet of specialized sub-agents rather than solving tasks directly, and whose core logic is the loop structure (Plan→Execute→Verify→Replan) rather than any individual agent's capability. The configurable stop conditions and the separation of a more-capable verifier model (Opus) from the execution model (Sonnet) mirror harness design choices around quality gates and resource budgets. The DAG-based scheduling with dependency propagation is a concrete, deployable mechanism for the "task graph" abstraction that many meta-harness proposals describe conceptually. For researchers building or studying harnesses, VMAO offers a fully specified reference architecture—including tool-limiter safety valves, hierarchical synthesis for context overflow, and real-time SSE observability—that can be directly compared against or adapted.