Paper deep dive
Verified Multi-Agent Orchestration: A Plan-Execute-Verify-Replan Framework for Complex Query Resolution
Xing Zhang, Yanwei Cui, Guanghui Wang, Qucy Wei Qiu, Ziyuan Li, Fangwei Han, Yajing Huang, Hengzhi Qiu, Bin Zhu, Peiyang He
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/22/2026, 6:23:45 AM
Summary
Verified Multi-Agent Orchestration (VMAO) is a framework for complex query resolution that utilizes a Plan-Execute-Verify-Replan loop. It decomposes queries into a Directed Acyclic Graph (DAG) of sub-questions, executes them in parallel using specialized agents, verifies results for completeness, and adaptively replans to address gaps. VMAO demonstrates significant improvements in answer completeness and source quality over single-agent and static multi-agent baselines in market research tasks.
Entities (5)
Relation Signals (3)
VMAO â uses â DAG
confidence 98% ¡ Given a complex query, our system decomposes it into a directed acyclic graph (DAG) of sub-questions
VMAO â implements â LangGraph
confidence 95% ¡ We implement VMAO using LangGraph for workflow orchestration
VMAO â utilizes â Claude Sonnet 4.5
confidence 95% ¡ Agent execution uses Claude Sonnet 4.5 as the primary model
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.11445v1
- Canonical: https://arxiv.org/abs/2603.11445v1
Trouble viewing inline? Open PDF directly â
Full Text
32,904 characters extracted from source content.
Expand or collapse full text
Published as a conference paper at ICLR 2026 Workshop on MALGAI VERIFIED MULTI-AGENT ORCHESTRATION: A PLAN- EXECUTE-VERIFY-REPLAN FRAMEWORK FOR COM- PLEX QUERY RESOLUTION Xing Zhang 1 Yanwei Cui 1 Guanghui Wang 1 Qucy Wei Qiu 2 Ziyuan Li 2 Fangwei Han 2 Yajing Huang 2 Hengzhi Qiu 2 Bin Zhu 2 Peiyang He 1â 1 AWS Generative AI Innovation Center 2 HSBC 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. 1INTRODUCTION Large language models (LLMs) have enabled a new generation of multi-agent systems where specialized agents collaborate to solve complex tasks. A central challenge in such systems is coordination: given a complex query that requires information from heterogeneous sources and diverse analytical expertise, how should agents be organized and assigned to sub-tasks? How can we ensure result quality without constant human oversight? When should the system stop iterating and synthesize a final answer? These questions are especially acute in domains like market research, where analysts gather data from internal databases, public filings, news sources, and competitor reports, then synthesize findings into actionable insights. Information is scattered across heterogeneous sources, analysis requires diverse expertise (financial, operational, competitive), and synthesis demands cross-referencing while resolving contradictions. Existing multi-agent frameworks fall short of these requirements. Debate-style approaches where agents critique each otherâs outputs (Du et al., 2023) improve reasoning quality but lack structured task decomposition. Role-playing frameworks where agents assume personas (Li et al., 2023) enable collaboration but provide no mechanism for verifying completeness. More recent systems like AutoGen (Wu et al., 2024) and MetaGPT (Hong et al., 2024) offer flexible interaction patterns, yet still lack principled quality verification and adaptive refinementâcritical requirements for production deployment where outputs must be reliable without constant human oversight. We introduce Verified Multi-Agent Orchestration (VMAO), a framework that addresses these gaps through three key contributions: 1.DAG-Based Query Decomposition and Execution: Complex queries are decomposed into sub-questions organized as a directed acyclic graph (DAG), enabling dependency-aware parallel execution with automatic context propagation from upstream results. â Corresponding author: peiyan@amazon.com 1 arXiv:2603.11445v1 [cs.AI] 12 Mar 2026 Published as a conference paper at ICLR 2026 Workshop on MALGAI 2.Verification-Driven Replanning: An LLM-based verifier evaluates result completeness at the orchestration level, triggering adaptive replanning when gaps are identifiedâproviding a principled coordination signal that is decoupled from individual agent implementations. 3.Configurable Stop Conditions: Termination decisions are based on completeness thresh- olds, confidence scores, and resource constraints, enabling explicit quality-cost tradeoffs. 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 single-agent and static multi-agent baselines. 2RELATED WORK Multi-Agent Coordination and Tool Use. Recent surveys (Wang et al., 2024; Xi et al., 2023) document the rapid growth of LLM-based multi-agent systems, which vary in coordination strategy: AutoGen (Wu et al., 2024) uses conversational patterns, CAMEL (Li et al., 2023) employs role- playing, MetaGPT (Hong et al., 2024) enforces software engineering workflows, and HuggingGPT (Shen et al., 2023) orchestrates specialized models via a central controller. Orthogonally, work on tool use has focused on single-agent settings: ReAct (Yao et al., 2023b) established the thought- action-observation paradigm, Toolformer (Schick et al., 2023) enables self-supervised tool learning, and ToolLLM (Qin et al., 2023) scales to 16,000+ APIs. These lines of work address coordination and tool use separately, but production systems require both: multiple specialized agents, each with domain-specific tools, working in concert. Planning, Decomposition, and Verification. Chain-of-Thought (Wei et al., 2022), Tree-of-Thoughts (Yao et al., 2023a), and Least-to-Most prompting (Zhou et al., 2023) decompose complex reasoning into structured steps, but operate within a single LLM rather than distributing sub-tasks across specialized agents. For output quality, Self-Consistency (Wang et al., 2022) aggregates multiple reasoning paths, Self-Refine (Madaan et al., 2023) iterates on single outputs, and Reflexion (Shinn et al., 2023) uses verbal reinforcementâall operating at the individual response level. Missing from prior work is verification at the orchestration level: evaluating whether collective results from multiple agents adequately address the original query, and triggering targeted replanning when gaps are detected. Agentic Search and Deep Research. Recent commercial systems have demonstrated the potential of multi-step agentic research: search-augmented assistants like Perplexity iteratively refine queries to synthesize information from web sources, while deep research features in frontier models (OpenAI, 2025) perform extended multi-step investigation. These systems demonstrate the value of iterative research loops but are closed-source, making their coordination mechanisms difficult to study or reproduce. Our work provides an open, modular framework where the coordination strategyâ particularly the verification-driven replanning loopâis explicit and configurable. Our Approach. VMAO synthesizes these threads into a unified framework for complex query resolution. We decompose queries into a DAG of sub-questions assigned to domain-specific agents, execute them in parallel with dependency-aware scheduling, verify collective completeness via LLM- based evaluation, and adaptively replan to address gaps. We evaluate VMAO on market research tasks, maintaining verifiable output quality through explicit coordination mechanisms. 3FRAMEWORK ARCHITECTURE 3.1OVERVIEW VMAO operates through five phases: Plan, Execute, Verify, Replan, and Synthesize (Figure 1a). Given a complex query, the system first decomposes it into sub-questions with assigned agent types and dependencies. It then executes these through specialized agents in parallel where dependencies permit. The verify phase evaluates completeness and identifies gaps. If deficiencies exist, the system replans by generating new sub-questions or marking incomplete ones for retry. This loop continues until stop conditions are met, triggering synthesis of a final answer with proper source attribution. 2 Published as a conference paper at ICLR 2026 Workshop on MALGAI PLAN Query Decomp. EXECUTE DAG Parallel VERIFY LLM Complete. REPLAN Gap Filling SYNTHESIZE Merge & Cite incomplete Iterative Refinement Loop stop conditions met (a) Plan-Execute-Verify-Replan Architecture Tier 1: DATA RAG, Web Financial, Competitor Tier 2: ANALYSIS Analysis, Reasoning Raw Data Tier 3: OUTPUT Document Visualization Information Flow (b) Agent Taxonomy by Functional Tier Figure 1: (a) VMAO framework architecture showing the iterative Plan-Execute-Verify-Replan loop. (b) Agent taxonomy organized by functional tier with information flow from data gathering through analysis to output generation. Table 1: Sub-question structure generated by the QueryPlanner FieldDescription idUnique identifier (e.g., sq001) questionSpecific, answerable question text agent typeAgent from taxonomy to handle this question dependenciesIDs of sub-questions that must complete first priorityExecution priority (1â10); higher = more important contextfromdepsWhether to include dependency results in prompt verificationcriteriaCriteria for determining answer completeness Agents are organized into three functional tiers (Figure 1b): Tier 1 (Data Gathering) agents retrieve information from diverse sources, Tier 2 (Analysis) agents reason over this data, and Tier 3 (Output) agents produce final deliverables. This hierarchy reflects the natural information flow in research tasks and enables principled task assignment by the planner. 3.2PLANNING AND EXECUTION The QueryPlanner decomposes a complex query into sub-questions organized as a DAG (Table 1). An LLM identifies distinct information requirements, assigns each to an appropriate agent type, establishes dependencies where one sub-question requires anotherâs output, and sets execution priorities. The DAGExecutor then orchestrates execution while respecting dependencies and maximizing parallelism (Algorithm 1). It iteratively identifies ready questionsâthose whose dependencies have completedâand executes batches in parallel (defaultk = 3). For sub-questions with contextfromdepsenabled, results from dependencies are prepended to the query. Figure 2a illustrates how independent sub-questions execute concurrently in Wave 1, while dependent questions execute in subsequent waves. Each execution is wrapped with a configurable timeout (default: 600s) and a tool call limiter to prevent infinite loops. 3 Published as a conference paper at ICLR 2026 Workshop on MALGAI Algorithm 1 DAG-Based Parallel Execution Require: Execution plan P = (Q, G), max concurrent k Ensure: Results R =r 1 , ..., r n 1: completedââ 2: while|completed| <|Q| do 3:ready âq â Q : deps(q)â completed⧠q /â completed 4:batchâ top-k(ready, by = priority) 5:resultsâ parallel execute(batch) 6:for (q, r) in results do 7:if q.context f romdeps then 8:r â enrichwithcontext(r,R[d] : dâ deps(q)) 9:end if 10:R[q.id]â r; completedâ completedâŞq 11:end for 12: end while 13: return R Query: "Why did service quality decline and what is the profit impact?" Wave 1 (Parallel) Wave 2 (Parallel) Wave 3 sq_001 RAG service metrics sq_002 RAG customer feedback sq_003 Financial profit data sq_006 Web external factors sq_004 Competitor benchmarking sq_007 Analysis correlation sq_005 Analysis root cause Time (a) DAG Execution Example Iteration 1Iteration 2 Execution Results sq_001 (0.90) sq_002 (0.45) sq_003 (0.85) sq_004 (0.30) sq_005 (0.25) Execution Results sq_001 (0.90) sq_002 (0.45) sq_003 (0.85) sq_004 (0.75) sq_005 (0.80) + sq_006 (0.80) + sq_007 (0.85) Overall: 40.0% | Complete: 2/5Overall: 85.7% | Complete: 6/7 REPLAN retry: [002, 004, 005] new: [006: external factors, 007: correlation analysis] SYNTHESIZE >80% complete Ready for final answer (b) Verification and Replanning CompleteIncompleteInheritedNew Figure 2: (a) DAG execution: independent sub-questions execute in Wave 1; dependent questions in subsequent waves. (b) Verification-driven iteration: Iteration 1 identifies incomplete results, triggering replanning; Iteration 2 achieves sufficient completeness for synthesis. 3.3VERIFICATION, REPLANNING, AND SYNTHESIS The ResultVerifier evaluates whether execution results adequately answer their sub-questions (Fig- ure 2b). For each result, it produces: status (complete/partial/incomplete), completeness score (0â1), missing aspects, contradictions, and a recommendation (accept/retry/escalate). Results already marked complete are reused to avoid redundant LLM calls. When verification identifies gaps, the AdaptiveReplanner determines corrective actions: retry sub- questions with low scores while preserving previous results, introduce new queries to address specific missing aspects, or merge results from multiple attempts. A key feature is result preservationâ previous results are stored and merged with retry attempts, enabling progressive refinement without losing earlier findings. Determining when to stop iterating is critical for balancing quality and cost. We introduce five configurable stop conditions (Table 2), evaluated after each verification phase: completeness threshold (80% of sub-questions answered), high confidence with partial coverage, diminishing returns (<5% improvement), token budget (1M tokens), and maximum iterations (3). When any condition is met, the system proceeds to synthesis. For large result sets (>15K characters or 10+ results), direct synthesis would exceed context limits. We address this through hierarchical synthesis: group results by agent type, synthesize within each group to produce condensed summaries, then integrate group summaries into a coherent final answer with proper source attribution. 4 Published as a conference paper at ICLR 2026 Workshop on MALGAI Table 2: Stop conditions for orchestration termination ConditionThresholdRationale Ready for Synthesis80% completeSufficient sub-questions answered High Confidence75% conf, 50% completeHigh reliability despite partial coverage Diminishing Returns <5% improvementFurther iteration yields minimal gain Token Budget1M tokensHard cost limit Max Iterations3 iterationsHard iteration limit Table 3: Agent taxonomy with tool allocation across MCP servers (42 unique tools total) TierAgentToolsKey Capabilities 1: Data RAG13Semantic, keyword, and hybrid retrieval; metadata filtering Web Search4General and AI-powered search, news retrieval Financial7Stock quotes, technical indicators, fundamentals Competitor11Market positioning, benchmarks, competitor news 2: Analysis Analysis20Survey analytics, financial and competitor analysis Reasoning24Cross-domain reasoning with RAG, web, and financial tools Raw Data1Python execution (pandas, matplotlib) 3: Output Document4Report generation, tables, source citations Visualization6Chart generation, statistical summaries 4IMPLEMENTATION We implement VMAO using LangGraph for workflow orchestration and the Strands Agent framework for agent execution, integrated with AWS Bedrock. Agent execution uses Claude Sonnet 4.5 as the primary model with Claude Haiku 4.5 as a fallback for graceful degradation; verification and evaluation use Claude Opus 4.5 to provide an independent quality signal. Agents access tools through the Model Context Protocol (MCP), which exposes domain-specific capabilities via independent HTTP microservices. This modular architecture allows adding new tools without modifying agent code. Table 3 shows the agent taxonomy with tool allocation across eight MCP servers (42 unique tools total). Each server runs independently, enabling horizontal scaling and fault isolation. Agents automatically select appropriate tools based on sub-question requirements. For production deployment, we implement several safety mechanisms: tool call limiters prevent infinite loops (max 10 consecutive same-tool calls, 50 total per agent), per-execution timeouts enforce bounded latency (default 600s), and phase-level token tracking enables budget enforcement. When the primary model (Sonnet 4.5) is unavailable, the system falls back to Haiku 4.5 with graceful degradation. Real-time observability is provided through Server-Sent Events that stream execution progress to the frontend. 5EXPERIMENTS 5.1DATASET: MARKET RESEARCH QUERIES We evaluate VMAO on market research tasksâa domain where traditional research typically requires 2â4 weeks of human effort. These tasks are challenging because relevant data is scattered across heterogeneous sources, answering questions requires diverse expertise (financial, operational, competitive), and synthesis demands cross-referencing while resolving contradictions. We curated 25 queries from domain experts spanning four categories: 5 Published as a conference paper at ICLR 2026 Workshop on MALGAI â˘Performance Analysis (8 queries): Operational metrics, trends, and causal factors. Example: âWhat factors explain the year-over-year change in customer satisfaction?â â˘Competitive Intelligence (7 queries): Comparison with industry peers and market position- ing. Example: âHow does our market share compare to regional competitors?â â˘Financial Investigation (5 queries): Financial metrics combined with operational context. Example: âWhat is driving the change in revenue per customer?â â˘Strategic Assessment (5 queries): Open-ended synthesis across multiple dimensions. Ex- ample: âWhat are the key risks and opportunities for geographic expansion?â Query complexity varies from simpler queries (3â5 sub-questions, 2â3 agent types) to complex ones (8â12 sub-questions, 5+ agent types with multi-level dependencies). Each query consumes 500Kâ1.1M tokens and requires 10â20 minutes of execution plus domain expert review, making 25 queries a practical yet meaningful evaluation set. 5.2BASELINES AND CONFIGURATION We compare three configurations: â˘Single-Agent: One reasoning agent with access to all tools, relying on internal reasoning to determine tool invocation order. â˘Static Pipeline: Predefined agent sequence (RAGâWebâFinancialâAnalysisâ Synthesis) without verification or replanning. â˘VMAO: Full framework with dynamic decomposition, parallel execution, verification- driven replanning, and stop conditions. All configurations use Claude Sonnet 4.5 for agent execution and the same tool set. We evaluate Completeness (how thoroughly all query aspects are addressed, 1â5 scale) and Source Quality (proper citation and traceability, 1â5 scale). Evaluation follows a two-stage process: an LLM judge (Claude Opus 4.5) first scores each response using structured rubrics, then human domain experts review and adjust scores where the LLM assessment appears inconsistent or misses domain-specific nuances. We deliberately use a different, more capable model for evaluation than for execution to reduce self-evaluation bias, though both models belong to the same family. In practice, human reviewers adjusted fewer than 15% of LLM scores, typically byÂą0.5 points, indicating reasonable LLM-human alignment on these metrics. We evaluate Completeness rather than accuracy because deep research queries have no single ground truthâa question like âWhat factors explain declining satisfaction?â admits multiple valid answers. Completeness measures whether all relevant aspects are addressed with supporting evidence, better capturing the exploratory nature of research. Source Quality ensures answers are grounded in verifiable sources. 5.3RESULTS Table 4 presents the main results across all 25 queries. VMAO achieves substantially higher completeness (+35%) and source quality (+58%) compared to Single-Agent. The Static Pipeline improves over Single-Agent but cannot adapt when initial agents return insufficient results. VMAOâs verification-driven approach identifies gaps and adaptively replans, leading to more complete answers with better source attribution. The increased resource usage reflects verification overhead, justified by quality improvements. Figure 3(a) shows a typical token distribution across orchestration phases: execution dominates (61%) as agents invoke tools and process results, while verification and synthesis remain efficient. VMAO demonstrates consistent improvements across all query categories (Figure 3(b)), with the largest gains on Strategic Assessment queries (+53% completeness), which require synthesizing information across multiple dimensions. Performance Analysis queries show more modest gains, as these often have well-defined data sources that even single agents can locate. In our experiments, most queries (>75%) terminate via resource-based conditions (diminishing re- turns, max iterations, or token budget), reflecting conservative thresholds that prioritize thoroughness 6 Published as a conference paper at ICLR 2026 Workshop on MALGAI Planning 8% Execution 61% Verification 16% Replanning 5% Synthesis 10% (a) Token Usage by Phase Performance Analysis Competitive Intelligence Financial Investigation Strategic Assessment 1 2 3 4 5 Completeness Score (1-5) 3.4 2.9 3.2 2.8 3.7 3.4 3.6 3.2 4.1 4.2 4.34.3 (b) Completeness by Query Category Single-Agent Static Pipeline VMAO (Ours) Figure 3: (a) Token usage breakdown by orchestration phase for a typical query. Execution dominates at 61%, while verification and synthesis remain efficient. (b) Completeness scores by query category across methods. VMAO shows consistent improvements, with largest gains on Strategic Assessment (+53%). Table 4: Comparison of orchestration methods on market research tasks. Completeness and Source Quality are co-scored by LLM and human evaluators (1â5 scale, higher is better). MethodCompletenessSource QualityAvg TokensAvg Time (s) Single-Agent3.12.6100K165 Static Pipeline3.53.2350K420 VMAO (Ours)4.24.1850K900 over speed. These parameters are configurable for deployments requiring faster responses or lower costs. Evaluation Limitations. We acknowledge three caveats: (1) 25 queries is a modest evaluation set without reported confidence intervals, (2) the LLM judge (Opus 4.5) belongs to the same model family as the execution model (Sonnet 4.5), potentially introducing shared biases despite human review, and (3) the Static Pipeline baseline tests verification and replanning jointly without a component-level ablation. We view the current evaluation as a meaningful signal of the frameworkâs potential, while acknowledging that larger-scale evaluation with independent judges would strengthen the conclusions. 6DISCUSSION Unlike skill-based systems (e.g., AutoGPT plugins) that invoke capabilities sequentially within a single agent, VMAO offers explicit DAG decomposition for interpretable plans, parallel execution re- ducing latency, verification-driven iteration for progressive refinement, and cross-agent synthesis with source attribution. The LLM-based verification serves as a principled coordination signalâassessing whether collective results satisfy the queryâdecoupling coordination from agent implementation. When Does Verification Help Most? The largest gains from verification-driven replanning appear on open-ended, multi-dimensional queries (Strategic Assessment: +53% completeness) where initial decomposition inevitably misses relevant aspects. For narrower queries with well-defined data sources (Performance Analysis), single agents already locate most relevant information, and the marginal benefit of replanning is smaller. This suggests verification is most valuable when the query space is difficult to fully characterize upfrontâprecisely the setting where static pipelines fail. We also observe that the majority of replanning actions are retries of incomplete sub-questions rather than introduction of entirely new ones, indicating that agent execution variance (tool failures, insufficient search results) is a larger contributor to gaps than poor initial decomposition. 7 Published as a conference paper at ICLR 2026 Workshop on MALGAI Limitations. Our framework has several limitations beyond the evaluation caveats noted in Sec- tion 5.3. LLM-based verification may miss subtle factual errors or hallucinations, as it evaluates completeness rather than accuracyâthe verifier can confirm that a claim is present and sourced, but cannot independently establish its truth. Poor query decomposition can propagate errors downstream: if the planner misframes a sub-question, the verifier may accept a well-sourced but irrelevant answer. The systemâs 8.5Ătoken cost relative to a single agent (850K vs. 100K tokens) may be prohibitive for latency-sensitive or cost-constrained settings. Finally, all experiments use a single model family (Claude); the frameworkâs effectiveness with other LLM families remains untested. Transferability and Future Work. The core componentsâDAG decomposition, verification, and replanningâare domain-agnostic and should transfer to domains like legal discovery or scientific literature review with appropriate agent and tool configuration. Future directions include learning- based stop conditions trained on execution traces, component-level ablation studies to isolate the contribution of each framework element, evaluation with diverse model families, and human-in-the- loop verification for high-stakes queries. 7CONCLUSION We presented VMAO, a framework that coordinates specialized LLM agents through a Plan-Execute- Verify-Replan loop. On 25 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 single-agent baselines, with the largest gains on open-ended queries that require multi-dimensional synthesis. Our results suggest that orchestration-level verificationâwhere an independent model evaluates whether collective agent results satisfy the original queryâis an effective coordination mechanism for multi-agent systems. Key open questions remain around component-level contributions, generalization across model families and domains, and scalable evaluation methodology. We will release the implementation upon publication. REFERENCES Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In Forty-first International Conference on Machine Learning, 2023. Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, et al. Metagpt: Meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, 2024. Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Com- municative agents forâ mindâ exploration of large language model society. Advances in Neural Information Processing Systems, 36:51991â52008, 2023. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36:46534â46594, 2023. OpenAI. Introducing deep research. OpenAI Blog, 2025. URLhttps://openai.com/index/ introducing-deep-research/. Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307.16789, 2023. Timo Schick, Jane Dwivedi-Yu, Roberto Dess ` Äą, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 36:68539â68551, 2023. 8 Published as a conference paper at ICLR 2026 Workshop on MALGAI Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. Advances in Neural Information Processing Systems, 36:38154â38180, 2023. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634â8652, 2023. Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345, 2024. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824â24837, 2022. Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, et al. Autogen: Enabling next-gen llm applications via multi-agent conversations. In First Conference on Language Modeling, 2024. Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864, 2023. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36:11809â11822, 2023a. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The eleventh international conference on learning representations, 2023b. Denny Zhou, Nathanael Sch Ě arli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, 2023. APROMPT TEMPLATES We provide simplified versions of the core prompts. Each follows a structured format with input specifications, decision rules, and JSON output schemas. Planning Prompt You are a query planner. Decompose complex queries into sub-questions for specialized agents. Input: Original query, conversation context, available agents Planning Rules: â RAG First: Always search internal knowledge base first or in parallel â Maximize Parallelism: Execute independent questions simultaneously â Minimize Dependencies: Only when results feed into other questions â Be Specific: Clear, answerable scope for each question Sub-question Fields: id, question, agenttype, dependencies, priority, contextfromdeps, verifica- tioncriteria Output: JSON with subquestions array and explanation 9 Published as a conference paper at ICLR 2026 Workshop on MALGAI Verification Prompt Verify if the sub-question has been adequately answered with proper metadata. Input: Sub-question, verification criteria, result, dependency results Evaluation Criteria: â Completeness: All aspects of question addressed? â Evidence Quality: Multiple sources? Cross-referenced? â Metadata: Source attribution (filename/URL/date) present? â Specificity: Concrete facts/numbers vs vague claims? â Contradictions: Conflicts between sources? Output: JSON with verificationstatus (complete/partial/incomplete), completenessscore (0â1), missingaspects, confidence, recommendation (accept/retry/escalate) Replanning Prompt Determine next actions based on verification results. Input: Original query, execution plan, completed/incomplete results, iteration count Critical Rule: MUST include ALL incomplete sub-question IDs in retry list. Decision Logic: â completeness> 0.8: Proceed to synthesis (done) â Incomplete results exist: Add ALL to retry subquestions â completeness 0.5â0.8: Add new subquestions to fill gaps â Contradictions found: Add queries targeting different sources â iterations⼠max: Return empty lists (done) Output: JSON with retrysubquestions, newsubquestions, explanation Synthesis Prompt Synthesize results from multiple agents into a concise, well-cited answer. Input: Original query, sub-question results, verification summary Required Structure: 1. Executive Summary (2â3 sentences with key metrics) 2. Key Findings (5â8 bullets with source citations) 3. Analysis (2â3 paragraphs connecting insights) 4. Conclusions (confidence level and limitations) Citation Format: [source - section/URL, metadata] Output: JSON with answer, key findings, confidence, sources, gaps BCONFIGURATION PARAMETERS Table 5 lists the default configuration parameters used in our experiments. These can be tuned for different quality-latency tradeoffs. Table 5: Configuration parameters for VMAO orchestration ParameterDefaultDescription maxiterations3Maximum replanning iterations tokenbudget1MMaximum tokens before stopping readythreshold0.8Completeness ratio for synthesis highconfidence0.75Confidence threshold for early stop diminishingreturns0.05Minimum improvement to continue maxconcurrent3Parallel agent executions agent timeout600sPer-agent timeout 10