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

AI summary

Authors: Xing Zhang, Yanwei Cui, Guanghui Wang, Wei Qiu, Ziyuan Li, Fangwei Han, Yajing Huang, Hengzhi Qiu, Bing Zhu, Peiyang He Affiliations: AWS Generative AI Innovation Center; HSBC arXiv: 2603.11445v2 [cs.AI], 15 Mar 2026 — License: CC BY-NC-SA 4.0

Overview

Research area: Artificial Intelligence — LLM-based multi-agent orchestration and agentic deep-research systems.

Technical level: Intermediate to Advanced. The paper assumes familiarity with LLM agents, tool use, and planning/decomposition techniques, though the architecture itself is described in accessible terms.

Scope: The paper presents Verified Multi-Agent Orchestration (VMAO), a framework that decomposes complex queries into a directed acyclic graph (DAG) of sub-questions, executes them through specialized agents, verifies collective completeness with an LLM, and replans when gaps are found — evaluated on 25 expert-curated market research queries.

What This Paper Is About

Multi-agent LLM systems struggle with coordination: how to split a complex query among specialized agents, how to know whether their combined output actually answers the question, and when to stop iterating. Existing frameworks (debate-style, role-playing, AutoGen, MetaGPT) offer interaction patterns but lack principled quality verification and adaptive refinement at the orchestration level. The goal of this paper is to add a verification-driven loop — where an independent LLM judges whether the collective agent results satisfy the original query and triggers targeted replanning — so that complex research tasks can be answered reliably without constant human oversight.

Key Contributions

1. DAG-based query decomposition and execution. Complex queries are broken into sub-questions organized as a directed acyclic graph, enabling dependency-aware parallel execution with automatic context propagation from upstream results to downstream questions.
2. Verification-driven adaptive replanning. An LLM-based verifier evaluates result completeness at the orchestration level and acts as a coordination signal that is decoupled from individual agent implementations; it triggers retries, new queries, or merging of results.
3. Configurable stop conditions. Termination is governed by five explicit criteria — completeness threshold, high confidence with partial coverage, diminishing returns, token budget, and maximum iterations — making the quality-cost tradeoff explicit and tunable.
4. An implemented, modular system. The framework is built with LangGraph, the Strands Agent framework, and AWS Bedrock, with agents accessing 42 unique tools across 8 MCP servers, plus safety mechanisms such as tool call limiters and per-execution timeouts.

Main Findings

• Completeness improved from 3.1 to 4.2 (1–5 scale) for VMAO compared to the Single-Agent baseline, a reported improvement of +35%.
• Source quality improved from 2.6 to 4.1 (1–5 scale) compared to Single-Agent, a reported improvement of +58%.
• Static Pipeline landed between the two extremes — completeness 3.5 and source quality 3.2 — showing that removing verification and replanning costs quality even when a predefined agent sequence is used.
• Token cost is substantially higher. VMAO averaged 850K tokens versus 100K for Single-Agent and 350K for Static Pipeline, an 8.5× increase over a single agent. Average time was 900s versus 165s (Single-Agent) and 420s (Static Pipeline).
• Largest gains appear on open-ended queries. Strategic Assessment queries saw +53% completeness, while Performance Analysis queries improved more modestly because their well-defined data sources are easier for even a single agent to locate.
• Execution dominates resource use. In a typical query, execution accounts for 61% of tokens, while verification and synthesis remain comparatively efficient.
• Most runs stop for resource reasons. More than 75% of queries terminated through resource-based conditions (diminishing returns, max iterations, or token budget) rather than the quality thresholds, reflecting conservative defaults that favor thoroughness over speed.
• Most replanning actions are retries, not new queries. This suggests agent execution variance — tool failures, insufficient search results — contributes more to gaps than poor initial decomposition.
• Human–LLM evaluation agreement was high. Domain experts adjusted fewer than 15% of LLM judge scores, typically by ±0.5 points.

Methodology in Plain English

The system runs a five-phase loop: Plan, Execute, Verify, Replan, Synthesize.

In the Plan phase, a QueryPlanner LLM breaks the user's query into sub-questions. Each sub-question carries an ID, question text, assigned agent type, list of dependencies, a priority from 1 to 10, a flag for whether to include dependency results in the prompt, and verification criteria. The sub-questions form a DAG.

In the Execute phase, a DAGExecutor repeatedly finds sub-questions whose dependencies have all completed and runs them in parallel batches of up to 3 (the default concurrency), prioritized by priority score. Results from dependencies are prepended to a sub-question's prompt when context propagation is enabled. Each execution is wrapped in a 600-second timeout and a tool-call limiter.

Agents are organized into three tiers: Tier 1 (Data Gathering) covers RAG, Web Search, Financial, and Competitor agents; Tier 2 (Analysis) covers Analysis, Reasoning, and Raw Data agents; Tier 3 (Output) covers Document and Visualization agents. The nine agents share access to 42 unique tools distributed over 8 MCP servers.

In the Verify phase, a ResultVerifier LLM inspects each result and returns a status (complete / partial / incomplete), a completeness score between 0 and 1, missing aspects, contradictions, and a recommendation (accept / retry / escalate). Already-complete results are reused to avoid redundant LLM calls.

In the Replan phase, an AdaptiveReplanner decides between retrying low-scoring sub-questions while preserving prior results, adding new queries to fill specific gaps, or merging results from multiple attempts.

The loop ends when any of five stop conditions fire: 80% of sub-questions answered, 75% confidence with 50% coverage, less than 5% improvement, 1M tokens consumed, or 3 iterations reached. Large result sets (over 15K characters or 10+ results) go through hierarchical synthesis: group by agent type, condense within groups, then integrate.

Configuration: Claude Sonnet 4.5 is the primary execution model, with Claude Haiku 4.5 as fallback for graceful degradation; Claude Opus 4.5 handles verification and evaluation to provide an independent quality signal. Safety mechanisms include a limit of 10 consecutive same-tool calls and 50 total tool calls per agent, plus phase-level token tracking and Server-Sent Events for real-time observability.

Evaluation: 25 expert-curated market research queries across four categories — Performance Analysis (8), Competitive Intelligence (7), Financial Investigation (5), and Strategic Assessment (5). Complexity ranged from 3–5 sub-questions with 2–3 agent types to 8–12 sub-questions with 5+ agent types and multi-level dependencies. Each query consumes 500K–1.1M tokens and requires 10–20 minutes of execution plus expert review. Three configurations were compared: Single-Agent (one reasoning agent with all tools), Static Pipeline (fixed RAG → Web → Financial → Analysis → Synthesis sequence with no verification or replanning), and VMAO. Scoring used a two-stage process: an LLM judge (Claude Opus 4.5) scored with structured rubrics, then human domain experts reviewed and adjusted. The paper notes it measures completeness rather than accuracy because deep research queries have no single ground truth.

Why This Matters

Impact on research. The paper argues that verification at the orchestration level — judging whether the collective output of many agents satisfies the original query — is distinct from prior verification work such as Self-Consistency, Self-Refine, and Reflexion, which all operate at the individual response level. It also contrasts itself with closed-source agentic research systems like Perplexity and deep research features in frontier models, which are difficult to study or reproduce. VMAO offers an explicit, configurable, and (upon publication) open coordination strategy.

Real-world applications:

• Market research and competitive intelligence. The evaluated domain, where the paper notes traditional research typically requires 2–4 weeks of human effort; examples include comparing market share to regional competitors and identifying risks and opportunities for geographic expansion.
• Financial investigation and operational analysis. Queries combining financial metrics with operational context, such as what drives changes in revenue per customer or year-over-year customer satisfaction.
• Strategic decision support. Open-ended, multi-dimensional synthesis questions where VMAO showed its largest completeness gains (+53%).
• Other domain-agnostic research workflows. The authors state the core components — DAG decomposition, verification, and replanning — should transfer to areas like legal discovery or scientific literature review with appropriate agent and tool configuration.

Industry relevance. The work is a collaboration between the AWS Generative AI Innovation Center and HSBC, built on production-oriented infrastructure (LangGraph, Strands Agent framework, AWS Bedrock, MCP microservices) with explicit attention to fault isolation, horizontal scaling, timeouts, and cost budgets. Its explicit quality-cost tradeoff framing addresses a practical requirement: reliable outputs without constant human oversight.

Future Directions

• Learning-based stop conditions trained on execution traces, replacing the current hand-set thresholds.
• Component-level ablation studies to isolate the contribution of each element. The paper concedes that the Static Pipeline baseline tests verification and replanning jointly rather than separately, so the individual contribution of each is not established.
• Generalization testing across model families and domains. All experiments used the Claude family, and effectiveness with other LLM families remains untested.
• Scalable evaluation methodology. The current evaluation uses 25 queries with no reported confidence intervals, and the LLM judge (Opus 4.5) belongs to the same model family as the execution model (Sonnet 4.5), potentially introducing shared biases.
• Human-in-the-loop verification for high-stakes queries, given that LLM-based verification evaluates completeness rather than factual accuracy and may miss subtle hallucinations.

Target Audience

Researchers and engineers working on LLM-based multi-agent systems, agentic search, and deep-research pipelines will get the most from this paper, especially those concerned with orchestration design, quality assurance without human oversight, and production deployment constraints. It is also relevant to practitioners in market research, financial analysis, and competitive intelligence who want to understand where agentic systems can substitute for multi-week manual research efforts, and to teams weighing quality improvements against the 8.5× token cost the paper reports.

Authors’ abstract

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.