PaperlayerView exact revision on arXiv

Source-linked AI summary

MAS-ZERO: Designing Multi-Agent Systems with Zero Supervision

Zixuan Ke, Austin Xu, Yifei Ming, Xuan-Phi Nguyen, Ryan Chin, Caiming Xiong, Shafiq Joty

arXiv:2505.14996v4cs.CLcs.AIcs.LG

TL;DR

Manual and validation-tuned MAS designs can be poorly aligned with LLM capabilities and lack per-problem adaptability or fallback to simpler systems. MAS-ZERO evolves task-specific designs at inference time without validation data. It outperforms strong manual and automatic baselines across reasoning, coding, and agentic benchmarks, with reported average accuracy gains in each domain.

  • Problem

    Manual MAS can be poorly aligned with LLM strengths, while automatic approaches often rely on validation sets and fixed designs that lack per-problem adaptability and simpler-system fallback.

    Source: §1 · pp. 1–2

  • Method

    MAS-ZERO uses a meta-agent to iteratively design, critique, and refine per-problem MAS configurations at inference time, with decomposition, feedback, and candidate verification.

    Source: §1 · p. 2

  • Results

    Across reasoning, coding, and agentic benchmarks, MAS-ZERO outperforms strong manual and automatic baselines, with average accuracy gains up to 16.69%, 16.66%, and 5.45%, respectively.

    Source: §1 · p. 3

  • Takeaways & Limitations

    MAS-ZERO can dynamically revert to simpler or single-agent strategies that can be surprisingly strong, rather than overlooking them in favor of more sophisticated designs.

    Source: §1 · p. 3

    Meta-design and meta-feedback signals may be imperfect and ultimately depend on the underlying LLM.

    Source: §3.2.3 · p. 6

Abstract

from arXiv · show

Multi-agent systems (MAS) leveraging the impressive capabilities of Large Language Models (LLMs) hold significant potential for tackling complex tasks. However, most current MAS depend on manually designed agent roles and communication protocols. These manual designs often fail to align with the underlying LLMs' strengths and struggle to adapt to novel tasks. Recent automatic MAS approaches attempt to mitigate these limitations but typically necessitate a validation set for tuning and yield static MAS designs lacking adaptability during inference, while also removing the flexibility to reduce to simpler systems. We introduce MAS-ZERO, the first self-evolved, inference-time framework for automatic MAS design. MAS-ZERO employs meta-level design to iteratively design, critique, and refine MAS configurations tailored to each problem instance, without requiring a validation set. Critically, it enables dynamic problem decomposition and agent composition through meta-feedback on solvability and completeness, and reduction to simpler systems when appropriate. Experiments across reasoning (math and graduate-level QA), coding, and agentic (search-based) benchmarks, using both closed-source and open-source LLM backbones of varying sizes, demonstrate that MAS-ZERO outperforms strong manual and automatic MAS baselines. It achieves substantial average accuracy improvements of up to 16.69% on reasoning, 16.66% on coding, and 5.45% on agentic tasks, while maintaining cost efficiency.

1 Introduction

MAS-ZERO addresses the limits of manual designs and validation-tuned automatic systems with inference-time, per-problem MAS evolution. It outperforms strong manual and automatic baselines across reasoning, coding, and agentic tasks while maintaining cost efficiency.

1 Introduction

  • Manual MAS designs can suffer from poor problem specification and inter-agent misalignment, while scaling poorly to novel and more complex problems.These issues are especially relevant when human designers and underlying LLMs are not well aligned.Source: §1 · p. 2
  • Validation-tuned automatic MAS often produce fixed architectures and cannot flexibly decompose problems or revert to simpler systems when those would be stronger.The passage notes that this limitation is especially consequential on challenging tasks such as AIME24.Source: §1 · p. 2
  • MAS-ZERO performs inference-time, per-instance design without validation sets, using a meta-agent to learn agent capabilities and refine configurations.The meta-agent also verifies candidate answers from refined designs and simpler MAS or single-agent systems.Source: §1 · p. 2
  • MAS-ZERO initializes from established single-agent and simple MAS building blocks, then iteratively designs and critiques configurations using solvability and completeness feedback.An experience library accumulates prior designs and feedback to guide refinement.Source: §1 · p. 2
  • MAS-ZERO improves average accuracy by up to 16.69% on reasoning, 16.66% on coding, and 5.45% on agentic tasks, outperforming strong manual and automatic baselines.It also lies on the accuracy-cost Pareto frontier.Source: Figure 1 · p. 2, §1 · p. 3

2 Related Work

Prior MAS work includes manually designed multi-agent strategies and automatic systems that generate or prune configurations. MAS-ZERO instead evolves task-specific designs at inference time without validation-set tuning.

2 Related Work

  • Manual MAS methods include debate and self-refinement, but rigid designs may not align with LLM strengths and have limited adaptability and scalability.Examples of cited manual approaches include LLM debate [10] and self-refine [33].Source: §2 · p. 3
  • Validation-based automatic MAS pruning methods, including MASS and MaAS, select subnetworks from predefined structures that may constrain design flexibility.MaAS adds question-wise masking, but the core structure remains predefined.Source: §2 · p. 4
  • Automatic generation methods such as ADAS [17] and AFlow use code generation, while MAS-ZERO replaces validation-set search with inference-time evolution, decomposition, and reversion to simpler blocks.ADAS searches historical designs and AFlow adds Monte Carlo Tree Search.Source: §2 · p. 4

3 MAS-ZERO Framework

MAS-ZERO uses a prompting-based, black-box pipeline to initialize candidate strategies, evolve task-specific MAS designs through decomposition and feedback, and verify candidate answers. Its iterative experience and answer-selection mechanisms support refinement and fallback to simpler strategies.

3 MAS-ZERO Framework

  • The framework takes a question and building blocks, runs MAS-Init, MAS-Evolve, and MAS-Verify, and requires only black-box LLM generation without fine-tuning or internal modifications.The process does not require prior knowledge of the underlying agents’ internal details.Source: §3 · p. 4

3.1 MAS-Init

  • MAS-Init executes established strategies including CoT, CoT-SC, Debate, and Self-Refine to create initial solutions that inform design and remain eligible for answer selection.These outputs support reduction to simpler MAS or single-agent systems when appropriate.Source: §3.1 · p. 4

3.2 MAS-Evolve

  • MAS-Evolve alternates between decomposition and MAS proposal, then feedback on solvability and completeness, storing designs and feedback in an experience library for subsequent refinement.The cycle progressively adjusts decompositions and configurations without external supervision.Source: §3.2 · p. 5

3.2.1 Meta-Design

  • Meta-design decomposes the question into interdependent sub-tasks and assigns each a sub-MAS by modifying connections or parameters of provided building blocks.The design process should not arbitrarily invent agents or blocks or prune architecture without grounding in the provided blocks.Source: §3.2.1 · p. 5

3.2.2 Meta-Feedback

  • Meta-feedback evaluates MAS designs using sub-task- and agent-level intermediate outputs, assessing whether each sub-task is solvable and whether the set covers necessary information.Feedback may recommend further decomposition or revising the task decomposition to cover missing information.Source: §3.2.2 · p. 5

3.2.3 Storing the Experience and Refining the design

  • The experience library stores each design, its intermediate outputs, and feedback to guide later iterations, although meta-design and feedback signals may be imperfect and depend on the underlying LLM.Accumulated experience informs subsequent decomposition and sub-MAS assignments.Source: §3.2.3 · p. 6

3.3 MAS-Verify

  • MAS-Verify selects the most reliable candidate from refined iterations and initial building blocks, ranking by final-answer frequency, filtering invalid answers, then choosing among the remainder.Selection avoids relying on a single stochastic iteration and can favor simpler strategies when they suffice.Source: §3.3 · p. 6

4 Experiments

Across reasoning, coding, and agentic benchmarks, MAS-ZERO achieves the best average performance across evaluated LLMs and lies on the Pareto front for accuracy and cost. Ablations show that its initialization, iterative evolution, feedback, and verification steps all contribute to performance.

4 Experiments

  • Experiments cover AIME24, GPQA, SWE-Bench-Lite-Oracle, BrowseComp, and Frames, using GPT-4o, Llama3.3-70B-inst, and Qwen2.5-32B-inst; validation-based baselines use a held-out 20% split.The comparison includes single-agent, manual, val-pruning, val-generation, and training-based automatic MAS baselines.Source: §4 · pp. 6–7

4.1 Overall Results

  • MAS-ZERO achieves the best average performance across LLMs and domains, with results reported for reasoning, SWE coding, and agentic tasks.It lies on the Pareto front across the three datasets.Source: §4.1 · pp. 7–8, Table 1 · p. 7, Table 2 · p. 7
  • MAS-ZERO exceeds the strongest reasoning baseline, AFlow, by 13.03% on average with GPT-4o, with only one-sample shortfalls on Qwen AIME24 and two manual-MAS exceptions on GPQA.ADAS records 0% accuracy on AIME24 despite using a validation set.Source: §4.1 · p. 7, Table 1 · p. 7
  • MAS-ZERO yields relative coding gains over AFlow of 58% with GPT-4o and 149% with Llama.The reported margins exceed those on reasoning tasks.Source: §4.1 · p. 7, Table 2 · p. 7
  • On agentic tasks, MAS-ZERO improves on its basic building blocks on average but underperforms Debate and Self-Refine on Frames.The authors speculate that retrieved-content errors can be harder for MAS-Verify to detect, motivating stronger verification.Source: §4.1 · pp. 7–8, Table 3 · p. 7

4.2 Further Analysis and Ablations

  • A stronger o3-mini meta-agent outperforms considered baselines on average, while weaker tested models often fail to follow instructions or produce syntactically valid Python; heterogeneous results indicate individual-agent capability constrains overall performance.Replacing GPT-4o with o3-mini as meta-agent improves results when GPT-4o is the individual agent, but still falls short of using o3-mini for both roles.Source: §4.2 · p. 8, Table 4 · p. 8, Table 5 · p. 8
  • Ablations show that omitting MAS-Init, MAS-Evolve, task decomposition, or meta-feedback degrades performance, while ensembling meta-feedback reduces it.The authors conclude the three steps contribute meaningfully and complementarily.Source: §4.2 · pp. 8–9, Table 6 · p. 8
  • Performance improves across MAS-Evolve iterations, but selecting the last iteration without MAS-Verify causes the largest ablation drop; an oracle verifier further widens the performance gap and pushes GPQA close to 95%.The authors say iterative refinement alone is insufficient and effective verification counters stochasticity without ground-truth signals.Source: §4.2 · p. 9, Figure 4 · p. 9

5 Conclusion

MAS-ZERO combines inference-time automatic MAS design with iterative refinement, dynamic decomposition, simpler strategies when sufficient, and candidate-answer verification. The paper reports effectiveness and cost-efficiency across its experiments.

5 Conclusion

  • MAS-ZERO is an inference-time-only automatic MAS design framework that operates without supervision.It iteratively designs and refines MAS, decomposes complex questions, reverts to simpler strategies when sufficient, and verifies candidate answers.Source: §5 · p. 9
  • Comprehensive experiments show MAS-ZERO's strong effectiveness, cost-efficiency, and the contribution of each step.Source: §5 · p. 10

A MAS-ZERO Algorithm

Algorithm 1 initializes MAS-ZERO with building blocks, iteratively designs and revises decompositions and sub-MAS configurations, then selects a final answer from the candidates.

A MAS-ZERO Algorithm

  • MAS-ZERO takes a question, building blocks, a meta-agent, and an iteration count, and returns a final answer.Source: A MAS-ZERO Algorithm · p. 14
  • MAS-Init executes each building block and extracts its final answer to seed the stored answers.Source: A MAS-ZERO Algorithm · p. 14
  • The meta-agent decomposes the question into sub-tasks, assigns a sub-MAS, executes it iteratively, and revises the design using solvability and completeness feedback.The algorithm stores sub-tasks, sub-MAS configurations, intermediate outputs, and feedback in its experience library.Source: A MAS-ZERO Algorithm · p. 14
  • MAS-Verify selects the final answer from all candidates after the design and execution steps.Source: A MAS-ZERO Algorithm · p. 14

B Implementations, Benchmarks and Baselines Details

The implementation compares nine MAS-ZERO candidate answers with matched multi-output baselines and evaluates reasoning, coding, and search-based agentic benchmarks. The appendix also specifies data splits and baseline sources.

B Implementations, Benchmarks and Baselines Details

C Cost Computation

The paper computes monetary cost from actual API token usage using OpenAI pricing as of May 2025. Its related-work appendix surveys prompt optimization, manual and automatic MAS design, and training-based approaches.

C Cost Computation

  • Reported monetary costs use OpenAI's official May 2025 pricing and API-recorded input and output token usage.Source: C Cost Computation · p. 15

D Additional Related Work

  • Prompt optimization for individual agents has also been incorporated into broader automatic MAS design as a design step or search-space element.Examples include PromptBreeder [11], DsPy, and Self-Discover.Source: D Additional Related Work · p. 15
  • Manual MAS approaches include dynamic message-passing compositions, debate or round-table discussion, and collaboration among personas.DyLAN [30], Reconcile [5], MAD [28], and SPP [49] exemplify these approaches.Source: D Additional Related Work · p. 15
  • Automatic MAS design includes validation-guided pruning and generation, while training-based methods train agents or meta-agents using supervised learning or reinforcement learning.Examples include GPTSwarm and AgentSquare [42] for pruning, AutoAgents and AgentVerse for generation, and ReMA, OWL, MAS-GPT, FlowReasoner, and Puppeteer for training-based approaches.Source: D Additional Related Work · p. 15

E Standard deviation for the Experiments

The experiments were repeated three times to assess statistical significance, with standard deviations reported for AIME24. MAS-ZERO remains significantly stronger than other baselines in most reported comparisons, despite substantial variance.

F Illustration of MAS-Evolve

MAS-Evolve generates a task-specific MAS and iteratively refines it using feedback about solvability and completeness. The process and its iterations are illustrated in Fig. F.1.

G Example of MAS produced from MAS-ZERO

MAS-ZERO dynamically decomposes questions and assigns sub-MAS, adapting architecture complexity to each task. The supplied example and implementation details show how this design is constructed and prompted.

G Example of MAS produced from MAS-ZERO

H Prompt Details

  • Prompt details cover MAS-Init building blocks, MAS-Evolve Meta-Design and Meta-Feedback, and MAS-Verify.Source: H Prompt Details · p. 16

G Example of MAS produced from MAS-ZERO

  • In the example, MAS-ZERO outperforms CoT and early iterations by assigning CoT, CoT-SC, and Debate to four sub-tasks.The assignments are CoT for the first two sub-tasks, CoT-SC with five sampled completions for the third, and two-round Debate for the fourth.Source: G Example of MAS produced from MAS-ZERO · p. 16, Figure G.1 · p. 17

I Code Template

  • A code template supports MAS code generation by having the model fill in a specific forward function.Source: I Code Template · p. 17
Loading 2505.14996v4…