EvoMAS: Learning Execution-Time Workflows for Multi-Agent Systems
EvoMAS framework enhances complex task success by constructing execution-time multi-agent workflows.
Key Findings
Methodology
EvoMAS formulates workflow construction as a meta-level sequential decision problem along a single task trajectory. At each stage, it constructs an explicit task state via a Planner-Evaluator-Updater pipeline and uses a learned Workflow Adapter to instantiate a stage-specific layered workflow from a fixed pool of candidate agents. The adapter is trained with policy gradients using sparse, verifiable terminal task success as the main supervision signal.
Key Results
- EvoMAS outperforms single-agent baselines and recent automated multi-agent workflow design methods on GAIA, HLE, and DeepResearcher, with an average success rate improvement of 30.2%.
- On GAIA Level 2, EvoMAS-7's success rate increased from 14.2% to 42.9%, demonstrating the impact of candidate pool richness on execution-time workflow adaptation.
- Analyses show that explicit task-state construction and learned workflow adaptation provide complementary benefits.
Significance
EvoMAS addresses the limitations of static coordination strategies in long-horizon tasks by dynamically adjusting multi-agent workflows. This approach not only improves task success rates but also offers new insights into applying multi-agent systems to complex tasks, especially when task states evolve.
Technical Contribution
EvoMAS technically contrasts with existing methods by treating workflow selection as a sequential decision problem. Its innovation lies in combining explicit task states with learned workflow adaptation, providing execution-aware coordination structures rather than static initialization-time designs.
Novelty
EvoMAS is the first to treat multi-agent system workflow construction as an execution-time sequential decision problem, differing from traditional one-shot optimization methods. Its core innovation is dynamically adapting to changing task states, offering flexible coordination strategies.
Limitations
- EvoMAS assumes a fixed candidate pool and maximum workflow depth, limiting its application in larger-scale systems.
- In extremely sparse reward environments, terminal rewards may be insufficient to provide effective learning signals.
Future Work
Future research could explore larger candidate pools, open-ended agent creation, runtime depth adaptation, and richer credit assignment mechanisms to further enhance EvoMAS's adaptability and performance.
AI Executive Summary
In complex long-horizon tasks, traditional multi-agent systems often employ static coordination strategies, which fall short when task states change. The EvoMAS framework addresses this by dynamically adjusting multi-agent workflows at execution time. Its core lies in treating workflow construction as a sequential decision problem and constructing explicit task states via a Planner-Evaluator-Updater pipeline.
Experimental results show that EvoMAS excels in benchmarks like GAIA, HLE, and DeepResearcher, significantly outperforming single-agent baselines and other automated multi-agent methods. This dynamic adaptability allows EvoMAS to flexibly adjust coordination strategies as task states change, enhancing task success rates.
Despite significant technical advances, EvoMAS faces challenges such as fixed candidate pools limiting its application in larger systems. Future research directions include exploring larger candidate pools and open-ended agent creation to further enhance adaptability and performance.
Deep Analysis
Background
Multi-agent systems have significant advantages in solving complex tasks, especially when tasks require multi-stage execution and dynamic coordination. However, traditional methods often rely on static workflow designs, which fall short when task states change. Recent research attempts to optimize multi-agent system coordination structures through automated design, but most methods still follow a one-shot optimization paradigm.
Core Problem
Traditional multi-agent system design methods fall short in long-horizon tasks, which typically require multi-stage execution and evolving task states. Fixed coordination strategies struggle to adapt to these dynamic changes, leading to reduced task success rates.
Innovation
EvoMAS's core innovation lies in treating multi-agent workflow construction as an execution-time sequential decision problem. β’ Constructs explicit task states via a Planner-Evaluator-Updater pipeline. β’ Uses a learned Workflow Adapter to dynamically adjust coordination strategies. β’ Trains with sparse terminal rewards using policy gradients.
Methodology
EvoMAS methodology includes: β’ Task state construction: Constructs explicit task states via a Planner-Evaluator-Updater pipeline. β’ Workflow adaptation: Uses a learned adapter to select stage-specific workflows from candidate agents. β’ Policy optimization: Trains with sparse terminal rewards using policy gradients to dynamically adjust coordination strategies.
Experiments
Experiments were conducted on benchmarks like GAIA, HLE, and DeepResearcher, using fixed candidate agent pools and three-layer workflow structures. Baselines include single-agent methods and recent automated multi-agent design methods. The primary evaluation metric is task success rate.
Results
Results show that EvoMAS outperforms single-agent baselines and other automated multi-agent methods across all benchmarks, with a notable 28.7% success rate increase on GAIA Level 2. This demonstrates EvoMAS's dynamic adaptability to changing task states significantly enhances task success rates.
Applications
EvoMAS is applicable in complex task scenarios requiring dynamic coordination, such as autonomous driving and smart manufacturing. In these scenarios, task states may change during execution, requiring flexible coordination strategies.
Limitations & Outlook
EvoMAS assumes a fixed candidate pool and maximum workflow depth, limiting its application in larger-scale systems. Additionally, in extremely sparse reward environments, terminal rewards may be insufficient to provide effective learning signals.
Plain Language Accessible to non-experts
Imagine a kitchen where chefs need to dynamically adjust workflows based on different dishes. EvoMAS is like an intelligent kitchen management system that adjusts chefs' tasks in real-time according to each dish's specific needs. For example, more preparation work is needed at the start, so the system assigns more chefs to prepare ingredients. When fine cooking is required, the system adjusts the chefs' division of labor to ensure each step is efficiently completed. Thus, the entire cooking process is like a carefully choreographed dance, ensuring each dish is completed in its best state.
ELI14 Explained like you're 14
Imagine you're playing a multiplayer online game where each player has different skills. EvoMAS is like a super-smart team captain who adjusts each player's tasks in real-time based on the game's progress. For example, at the start, when exploration is needed, the captain sends scouts to explore. When enemies appear, the captain sends warriors to fight. This way, the whole team can flexibly tackle various challenges in the game and easily win the victory!
Glossary
Multi-Agent System
A system composed of multiple agents that can collaborate to complete complex tasks.
EvoMAS enhances task success rates by dynamically adjusting multi-agent workflows.
Workflow
An ordered execution process of a series of tasks or activities.
EvoMAS constructs execution-time multi-agent workflows dynamically.
Reinforcement Learning
A machine learning method that optimizes policies through reward signals.
EvoMAS uses reinforcement learning to optimize the workflow adapter.
Task State
Current state information during task execution.
EvoMAS constructs explicit task states via a Planner-Evaluator-Updater pipeline.
Sparse Reward
Reward signals that occur infrequently during task execution.
EvoMAS uses sparse terminal rewards for policy optimization.
Open Questions Unanswered questions from this research
- 1 How to achieve EvoMAS's dynamic adaptability in larger-scale systems?
- 2 How to effectively provide learning signals in extremely sparse reward environments?
Applications
Immediate Applications
Autonomous Driving
EvoMAS can be used in autonomous driving systems to dynamically adjust vehicle decision strategies, improving driving safety and efficiency.
Long-term Vision
Smart Manufacturing
EvoMAS has the potential to achieve dynamic production process optimization in smart manufacturing, improving production efficiency and product quality.
Abstract
Large language model (LLM)-based multi-agent systems have shown strong potential on complex tasks through agent specialization, tool use, and collaborative reasoning. However, most automated multi-agent system design methods still follow a one-shot paradigm: a workflow is optimized or selected before execution and then reused unchanged throughout the task. This static coordination strategy is ill-suited for long-horizon tasks whose subgoals, intermediate evidence, and information needs evolve over multiple execution stages. We propose EvoMAS, a framework for execution-time multi-agent workflow construction. EvoMAS formulates workflow construction as a meta-level sequential decision problem along a single task trajectory. At each stage, it constructs an explicit task state through a Planner-Evaluator-Updater pipeline and uses a learned Workflow Adapter to instantiate a stage-specific layered workflow from a fixed pool of candidate agents. The adapter is trained with policy gradients using sparse, verifiable terminal task success as the main supervision signal, while evaluator-based process reward is analyzed separately under very-hard sparse-reward settings. Experiments on GAIA, HLE, and DeepResearcher show that EvoMAS outperforms single-agent baselines and recent automated multi-agent workflow design methods. Our analyses further show that explicit task-state construction and learned workflow adaptation provide complementary benefits. Additional results indicate that process reward is most useful when terminal success is extremely sparse, and qualitative case studies illustrate that EvoMAS adapts agent coordination as the task state evolves.