Technical Summary: EvoMAS

Problem Statement

Large Language Model (LLM)-based multi-agent systems (MAS) have demonstrated potential in complex tasks through specialization and collaborative reasoning. However, current automated design methods largely adhere to a one-shot paradigm: a workflow is optimized or selected prior to execution and remains static throughout the task. This approach is ill-suited for long-horizon tasks where subgoals, intermediate evidence, and information needs evolve across multiple execution stages. Relying on a single, fixed coordination strategy for such dynamic environments is inherently suboptimal.

The paper identifies two fundamental challenges in addressing this limitation:

1. Constructing an Explicit Execution-Time Task State: Long-horizon tasks require a system to maintain an explicit state summarizing execution progress, intermediate artifacts, and solution quality to make principled coordination decisions. Without this, workflow adaptation lacks a concrete basis.
2. Adapting Workflows to Evolving Task States: Different execution stages impose heterogeneous coordination requirements (e.g., exploration vs. refinement). A system must dynamically construct stage-specific workflows conditioned on the current task state rather than relying on a static design.

Methodology: EvoMAS

The authors propose EvoMAS, a framework for execution-time multi-agent workflow construction. EvoMAS reformulates workflow selection as a meta-level sequential decision-making problem along a single task trajectory.

1. Formalization (Meta-Level MDP)

EvoMAS models the process as a Meta-Markov Decision Process (Meta-MDP) $M = (S^m, A^m, T^m, R^m)$:

• Meta-State ($s^m_t$): A structured textual representation of the current task progress, intermediate artifacts, and feedback.
• Meta-Action ($a^m_t$): The selection of a concrete multi-agent workflow $G_t = (V_t, E_t)$, where $V_t$ is a subset of agents from a fixed pool $\mathcal{P}$, and $E_t$ defines the information flow (layered DAG structure).
• Transition: Executing $G_t$ produces an aggregated outcome $\xi_t$ (messages, tool observations, evaluator feedback), which updates the meta-state via a transition function.
• Objective: Learn a policy $\pi_{wf}$ that maximizes expected cumulative meta-level reward, primarily using sparse, verifiable terminal task success.

2. System Components

EvoMAS operates through three core components:

• Task State Construction (Planner–Evaluator–Updater Pipeline):

  • Planner: Maintains the subtask plan, identifying active subtasks and handling failures by attaching context for refinement.
  • Evaluator: Assesses the previous execution outcome against the active subtask, producing verdicts (success/fail/refine), confidence scores, and natural language feedback.
  • Updater: Integrates the previous state, executed workflow, and execution record into a new structured task state $\tilde{s}_t$. This state serves as context for agents and conditions the workflow adapter.

• Execution-Time Workflow Construction (Workflow Adapter):

  • Given the task state $\tilde{s}_t$, a Workflow Adapter instantiates a stage-specific layered workflow from a fixed candidate agent pool.
  • The adapter encodes the task state and agent embeddings (derived from role, capabilities, and tools).
  • It uses cross-attention to score agents and employs a cumulative-mass soft-sampling mechanism to select agents for each layer without replacement, ensuring the selected set meets a probability mass threshold.
  • This allows the same agent to appear in multiple layers or meta-steps, enabling iterative refinement.

• Workflow Policy Optimization:

  • The adapter parameters are optimized using Reinforcement Learning (REINFORCE).
  • The primary supervision signal is sparse terminal task success (verifiable via benchmark evaluation), avoiding direct optimization against potentially biased evaluator judgments.
  • Process rewards (evaluator-based) are analyzed separately as a credit-assignment aid for extremely sparse-reward regimes.

Key Contributions

1. Paradigm Reformulation: The authors shift automated multi-agent workflow construction from a one-shot, initialization-time design to a sequential decision-making problem occurring during task execution.
2. Execution-Time Framework: EvoMAS combines explicit task-state construction with a learned, state-conditioned workflow adapter, enabling dynamic reorganization of agent coordination structures as the task evolves.
3. Empirical Validation: The framework is validated on complex, multi-step benchmarks (GAIA, HLE, DeepResearcher), demonstrating that execution-time adaptation outperforms both single-agent baselines and recent automated MAS design methods.

Experimental Results

Experiments were conducted on GAIA (Levels 1–3), HLE, and DeepResearcher.

• Performance: EvoMAS-7 (using a 7-agent pool) achieved an average success rate of 65.0, outperforming the strongest automated MAS baseline (G-Designer/MaAS) by 30.2 points and the strongest single-agent baseline (GPT-4o) by 35.2 points.
• Generalization: EvoMAS achieved the best results across all four evaluated benchmarks, indicating broad applicability rather than benchmark-specific overfitting.
• Ablation Studies:
  • Task State: Explicit execution-time task state construction improved success rates even when the workflow structure was fixed, highlighting the value of structured bookkeeping for intermediate artifacts and subgoal revisions.
  • Learning from Sparse Rewards: The Workflow Adapter successfully learned effective policies using only sparse terminal rewards, with performance improving steadily on GAIA Level 1 and 2.
  • Process Reward: Evaluator-based process rewards were found to be unnecessary for standard tasks but crucial for "very-hard" settings (e.g., GAIA Level 3, BrowserComp) where terminal success is too sparse to provide learning signals.
  • Backbone Sensitivity: Stronger underlying LLMs (e.g., GPT-4o vs. GPT-4o-mini) further improved performance, suggesting EvoMAS is complementary to backbone improvements.

Significance and Claims

The paper claims that EvoMAS addresses the rigidity of current multi-agent systems by enabling execution-aware adaptation. By treating workflow selection as a sequential decision problem conditioned on an explicit task state, EvoMAS allows systems to shift between information acquisition, refinement, aggregation, and termination as needed.

The authors emphasize that their approach provides complementary benefits from both explicit state construction and learned workflow adaptation. They note that while the current framework assumes a fixed candidate pool and maximum depth, it establishes a foundation for future work in open-ended agent creation and dynamic depth adaptation. The study suggests that for moderate-difficulty tasks, sparse terminal rewards are sufficient for training, while process rewards serve as a specialized tool for extreme sparsity.