Source-linked AI summary
Verified Multi-Agent Orchestration: A Plan-Execute-Verify-Replan Framework for Complex Query Resolution
Xing Zhang, Yanwei Cui, Guanghui Wang, Wei Qiu, Ziyuan Li, Fangwei Han, Yajing Huang, Hengzhi Qiu, Bing Zhu, Peiyang He
TL;DR
Complex multi-agent queries require structured coordination, reliable completeness checks, and principled stopping without constant human oversight. VMAO uses DAG-based parallel execution with context propagation, verification-driven replanning, and configurable stop conditions; on 25 market research queries, it improves completeness and source quality over baselines, especially for open-ended queries.
Problem
Existing multi-agent frameworks lack a combined mechanism for structured task decomposition, completeness verification, adaptive refinement, and reliable stopping.
Method
VMAO decomposes queries into dependency-aware DAGs, executes specialized agents in parallel, verifies collective completeness, replans gaps, and stops using configurable quality and resource conditions.
Results
VMAO raises answer completeness from 3.1 to 4.2 and source quality from 2.6 to 4.1 on 25 market research queries, with largest gains on open-ended multi-dimensional queries.
Takeaways & Limitations
Orchestration-level verification is an effective coordination mechanism for multi-agent systems within the evaluated market research setting.
Takeaways & Limitations
The evaluation uses a modest query set, same-family LLM judge and execution model, no component-level ablation, and a framework with 8.5× single-agent token cost.
Abstract
from arXiv · showhide
We present Verified Multi-Agent Orchestration (VMAO), a framework that coordinates specialized LLM-based agents through a verification-driven iterative loop. Given a complex query, our system decomposes it into a directed acyclic graph (DAG) of sub-questions, executes them through domain-specific agents in parallel, verifies result completeness via LLM-based evaluation, and adaptively replans to address gaps. The key contributions are: (1) dependency-aware parallel execution over a DAG of sub-questions with automatic context propagation, (2) verification-driven adaptive replanning that uses an LLM-based verifier as an orchestration-level coordination signal, and (3) configurable stop conditions that balance answer quality against resource usage. On 25 expert-curated market research queries, VMAO improves answer completeness from 3.1 to 4.2 and source quality from 2.6 to 4.1 (1-5 scale) compared to a single-agent baseline, demonstrating that orchestration-level verification is an effective mechanism for multi-agent quality assurance.
1 INTRODUCTION
VMAO addresses coordination and quality-assurance gaps in multi-agent systems by combining DAG-based execution, orchestration-level verification, adaptive replanning, and configurable termination. On 25 market research queries, it improves completeness and source quality over baseline systems.
- Motivation: Existing multi-agent frameworks provide collaboration or flexible interactions but lack structured decomposition, principled completeness verification, and adaptive refinement.These gaps limit reliable deployment without constant human oversight.
- Contributions: VMAO decomposes complex queries into dependency-organized DAG sub-questions, enabling parallel execution with automatic context propagation.The DAG structure assigns specialized agents while preserving dependencies between sub-questions.
- Contributions: An LLM-based verifier evaluates result completeness at the orchestration level and triggers adaptive replanning when gaps are identified.This provides a coordination signal decoupled from individual agent implementations.
- Contributions: Configurable stop conditions use completeness thresholds, confidence scores, and resource constraints to make quality–cost tradeoffs explicit.The framework can terminate based on predefined orchestration criteria rather than a fixed iteration pattern.
- Empirical results: VMAO improves answer completeness from 3.1 to 4.2 and source quality from 2.6 to 4.1 on 25 expert-curated market research queries.Scores use a 1–5 scale and are compared with single-agent and static multi-agent baselines.
2 RELATED WORK
Prior work explores multi-agent coordination, structured reasoning, output refinement, and agentic research, but VMAO combines these ideas in an open framework centered on DAG decomposition and verification-driven coordination.
- Multi-agent coordination: Prior multi-agent systems use conversational, role-playing, workflow, or controller-based coordination, while tool-use research largely focuses on single-agent settings.These approaches establish complementary coordination and tool-use patterns rather than VMAO’s combined orchestration design.
- Planning and verification: Chain-of-Thought, Tree-of-Thoughts, and Least-to-Most structure reasoning within one model, whereas Self-Consistency, Self-Refine, and Reflexion improve individual responses.The related approaches do not distribute sub-tasks across specialized agents at the orchestration level.
- Agentic research: Commercial agentic research systems demonstrate iterative investigation but remain closed-source, making their coordination mechanisms difficult to study or reproduce.VMAO is presented as an open, modular alternative for examining coordination strategy.
- VMAO positioning: VMAO unifies DAG-based sub-question decomposition, dependency-aware parallel execution, LLM completeness verification, adaptive replanning, and verifiable synthesis for complex queries.The framework is evaluated on market research tasks with explicit coordination mechanisms.
3 FRAMEWORK ARCHITECTURE
VMAO resolves complex queries through a five-phase orchestration loop that plans a dependency DAG, executes ready tasks in parallel, verifies completeness, replans gaps, and synthesizes attributed answers under explicit stop conditions.
- 3.1 OVERVIEW: VMAO proceeds through Plan, Execute, Verify, Replan, and Synthesize phases, repeating until stop conditions trigger final synthesis with source attribution.The loop decomposes queries, executes specialized agents, evaluates completeness, and corrects deficiencies before synthesis.
- 3.1 OVERVIEW: Agents are organized into Data Gathering, Analysis, and Output tiers that follow information flow from retrieval through reasoning to final deliverables.This hierarchy supports task assignment by the planner.
- Planning and execution: The QueryPlanner assigns sub-questions, agent types, dependencies, and priorities within a directed acyclic graph.Dependencies encode when one sub-question requires another’s output.
- Planning and execution: Independent sub-questions execute in Wave 1, while dependent questions run in later waves after their prerequisites complete.The DAGExecutor identifies ready questions, batches up to k = 3 by default, executes them in parallel, and can prepend dependency context.
- Verification and replanning: The ResultVerifier labels outputs complete, partial, or incomplete, scores completeness, identifies gaps or contradictions, and recommends acceptance, retry, or escalation.Completed results are reused to avoid redundant verification calls.
- Verification and replanning: Adaptive replanning retries weak sub-questions, adds queries for missing aspects, or merges attempts while preserving earlier results.This enables progressive refinement without discarding previous findings.
- Verification, replanning, and synthesis: Five configurable stop conditions balance quality and cost: 80% completeness, high confidence with partial coverage, less than 5% improvement, a 1M-token budget, or three iterations.Meeting any condition triggers synthesis.
- Verification, replanning, and synthesis: Hierarchical synthesis groups large result sets by agent type before integrating condensed summaries into an attributed final answer.This is used when results exceed 15K characters or contain at least 10 outputs.
4 IMPLEMENTATION
The implementation uses modular workflow and agent frameworks, model specialization, MCP-based tools, and production safeguards for scaling, fault isolation, bounded execution, and observability.
- Implementation architecture: VMAO uses LangGraph for orchestration, Strands for agent execution, AWS Bedrock, Claude models, and MCP microservices for domain-specific tools.Sonnet 4.5 is primary, Haiku 4.5 is fallback, and Opus 4.5 supplies verification and evaluation.
- Tool infrastructure: Eight independently running MCP servers provide 42 unique tools, enabling horizontal scaling, fault isolation, and automatic tool selection by agents.Tools are allocated through the agent taxonomy according to sub-question requirements.
- Production safeguards: Safety mechanisms enforce bounded execution through tool-call limits, 600-second default timeouts, phase-level token tracking, and fallback models.Server-Sent Events provide real-time execution-progress observability.
5 EXPERIMENTS
VMAO is evaluated on 25 expert-curated market research queries against single-agent and static-pipeline baselines, using completeness and source quality as primary measures. It improves both metrics while incurring verification-related resource costs, with benefits varying by query category.
- 5.1 TASKS: The study evaluates market research queries spanning heterogeneous sources, diverse expertise, and cross-referenced synthesis requirements.The 25-query set covers four expert-curated categories, with complexity ranging from 3–5 to 8–12 sub-questions.
- 5.3 RESULTS: +35% completeness and +58% source quality are achieved by VMAO over Single-Agent across all 25 queries.The evaluation uses 1–5 scales and co-scores responses with an LLM judge and human domain experts.
- 5.3 RESULTS: VMAO shows consistent completeness gains across query categories, largest for Strategic Assessment at +53%.Performance Analysis shows more modest gains because single agents can often locate its well-defined data sources.
- 5.4 STOP CONDITIONS: More than 75% of queries terminate through resource-based conditions, reflecting conservative thresholds that prioritize thoroughness over speed.Stop conditions include diminishing returns, maximum iterations, and token budgets, with parameters configurable for faster or cheaper deployments.
- 5.3 RESULTS: Execution consumes 61% of typical orchestration tokens, while verification and synthesis remain efficient.The resource distribution reflects the cost of agents invoking tools and processing results.
- 5.5 LIMITATIONS: The evaluation is limited by a modest 25-query set, no reported confidence intervals, same-family judging, and no component-level ablation.The authors state that larger-scale evaluation with independent judges would strengthen the conclusions.
6 DISCUSSION
VMAO distinguishes itself through explicit DAG planning, parallel execution, verification-driven refinement, and cross-agent synthesis with source attribution. Discussion findings indicate that verification helps most on open-ended queries, while substantial cost and evaluation limitations constrain current conclusions.
- Framework Implications: VMAO uses DAG decomposition for interpretable plans, parallel execution to reduce latency, verification for refinement, and cross-agent synthesis with source attribution.Its LLM verifier assesses whether collective results satisfy the query while remaining decoupled from agent implementation.
- When Does Verification Help Most?: Verification-driven replanning yields its largest gains on open-ended, multi-dimensional queries such as Strategic Assessment.For narrower queries with well-defined sources, single agents already locate much of the relevant information, reducing replanning’s marginal benefit.
- When Does Verification Help Most?: Most replanning actions retry incomplete sub-questions, implicating execution variance more than poor initial decomposition in observed gaps.The reported execution issues include tool failures and insufficient search results.
- Limitations: The framework’s 8.5× token cost may be prohibitive for latency-sensitive or cost-constrained settings.The comparison is 850K tokens for VMAO versus 100K for a single agent.
- Limitations: Completeness-focused verification may miss subtle factual errors or hallucinations because it cannot independently establish claim truth.Poor decomposition can also propagate well-sourced but irrelevant answers downstream.
- Limitations: All experiments use the Claude model family, leaving effectiveness with other LLM families untested.The authors identify diverse-model evaluation and component ablations as future work.
7 CONCLUSION
VMAO coordinates specialized LLM agents through a Plan-Execute-Verify-Replan loop and improves completeness and source quality on 25 market research queries. The largest gains occur on open-ended queries requiring multi-dimensional synthesis, while questions remain about component contributions, generalization, and scalable evaluation.
- Completeness rose from 3.1 to 4.2 and source quality from 2.6 to 4.1 on 25 market research queries versus single-agent baselines.Both metrics use a 1–5 scale.
- VMAO coordinates specialized LLM agents through a Plan-Execute-Verify-Replan loop.
- The largest gains occurred on open-ended queries requiring multi-dimensional synthesis.
- The results suggest orchestration-level verification is an effective coordination mechanism for multi-agent systems.An independent model evaluates whether collective agent results satisfy the original query.
- Open questions concern component-level contributions, generalization across model families and domains, and scalable evaluation methodology.
A PROMPT TEMPLATES
The prompt templates define structured planning, verification, replanning, and synthesis stages for VMAO. They specify dependency-aware execution, completeness checks, retry and gap-filling logic, contradiction handling, and cited final-answer structure.
- The templates use structured inputs, decision rules, and JSON output schemas across the orchestration stages.
- Planning decomposes complex queries into dependency-linked sub-questions for specialized agents while maximizing parallel execution.The planner uses fields for dependencies, priority, propagated context, and verification criteria.
- Verification evaluates completeness, evidence quality, source metadata, specificity, and contradictions, producing a status, score, missing aspects, confidence, and recommendation.
- Replanning retries every incomplete sub-question, adds gap-filling questions for intermediate completeness, targets different sources for contradictions, and stops at the iteration limit.Results with completeness above 0.8 proceed to synthesis.
- Synthesis produces an executive summary, cited key findings, connecting analysis, conclusions, confidence, sources, and gaps.
B CONFIGURATION PARAMETERS
The configuration parameters in Table 5 define the default VMAO orchestration setup. These parameters can be tuned to balance answer quality against latency.
- Table 5 lists the default configuration parameters used for VMAO orchestration.
- The parameters can be tuned for different quality-latency tradeoffs.