Skip to content

OptiMAS: Automatically Optimize Multi-Agent System

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Agent
Keywords: multi-agent evolution, agentic optimizer, textual gradient, dual-track memory, adaptive sampling

TL;DR

Addressing evolutionary instability and the isolation of insights across lineages in discrete search-based multi-agent evolution, OptiMAS introduces an end-to-end continuous optimization paradigm over a unified ReAct substrate, leveraging textual gradients, dual-track memory, and adaptive sampling to achieve steady, compounding performance gains across four challenging agentic benchmarks.

Background & Motivation

Collaborative multi-agent systems (MAS) driven by large language models (LLMs) have substantially expanded autonomous capabilities in challenging domains, such as production software engineering, multi-hop web browsing, and multi-step computational reasoning. However, building performant MAS architectures remains labor-intensive and empirical: human engineers must painstakingly hand-craft role prompts, orchestrate static workflow graphs, and calibrate tool routing protocols through trial and error. While automated agent evolution has recently emerged to liberate human effort (as seen in frameworks like ADAS and AFlow), current self-evolving systems still fail to match the reliability and efficacy of finely tuned human-engineered systems in practical deployments.

This deficiency originates from two fundamental structural dilemmas in existing evolutionary paradigms. First, expanding the optimization scope introduces acute evolutionary instability. Constraining search to surface-level prompt tuning or fixed role profiles prevents the emergence of novel collaborative workflows; conversely, unconstrained evolution that mutates arbitrary Python execution code (such as Gรถdel Agent or Darwin Gรถdel Machine) frequently produces syntax crashes, dependency conflicts, and non-convergent behavior. Second, prevailing methods formulate evolution as discrete, stochastic search across divergent tree branches. At each generation, multiple candidate workflows are evaluated over an entire dataset, after which non-selected candidate branches are discarded. This branch-and-discard dynamic isolates valuable failure lessons and successful heuristics within distinct lineages, making it impossible to accumulate and compound evolutionary insights across steps.

To bridge these gaps, this work reformulates MAS evolution from discrete search into a continuous, data-driven optimization process inspired by gradient descent in deep learning. Instead of sampling disconnected topologies, a general-purpose agentic optimizer deeply audits execution trajectories and intermediate artifacts produced on a training partition to derive actionable "textual gradients", continuously refining agent prompts, skills, coordination topologies, and tool permissions. Core idea: establish a unified ReAct substrate with a proactive assign-deliver protocol, recasting MAS evolution into data-driven continuous optimization driven by textual gradients from rich execution trajectories and stabilized by plan-oriented short-term memory and hypothesis-driven long-term memory.

Method

Overall Architecture

OptiMAS structures multi-agent evolution analogously to an end-to-end supervised learning loop: the task query set is rigorously split into training (\(X_{train}\)), validation (\(X_{val}\)), and held-out test (\(X_{test}\)) partitions. At each optimization step \(t\), an adaptive sampling mechanism constructs a training batch \(B_t\) of size \(n\) by prioritizing previously failed instances. The current multi-agent system \(\mathcal{E}_{t-1}\) executes tasks in \(B_t\), logging complete reasoning traces, tool calls, bash execution outputs, and scratchpad artifacts into an audit workspace \(W_{train}\). Concurrently, \(\mathcal{E}_{t-1}\) executes over \(X_{val}\) to produce a scalar generalization signal \(R_{val}\), while its workspace remains strictly hidden from the optimizer.

In the backward pass, the agentic optimizer OptiMAS deeply navigates \(W_{train}\), extracts root causes of task failures, derives textual gradients, and updates the configuration of \(\mathcal{E}_{t-1}\) to form \(\mathcal{E}_t\). To guarantee operational stability across millions of trajectory tokens, the optimizer is governed by a plan-oriented short-term memory for intra-step consistency and a hypothesis-driven long-term memory that tracks falsifiable scientific hypotheses across iterations, alongside a multi-tier context lifecycle management mechanism built upon the Model Context Protocol (MCP).

The end-to-end forward execution and backward evolution pipeline is illustrated below:

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["Task Query Partitioning<br/>X_train / X_val / X_test"] --> D1["Unified ReAct Infrastructure & Assign-Deliver<br/>Atomic ReAct Primitives & Dynamic DAG Tool Delegation"]
    D1 --> D2["Textual Gradients & Adaptive Sampling Optimization<br/>Failure Resampling & Workspace Backward Pass"]
    D2 --> D3["Dual-Track Memory & Hypothesis-Driven Evolution<br/>Plan Short-Term Memory & Hypothesis Lifecycle Ledger"]
    D3 --> D4["Three-Tier Context Lifecycle Management<br/>Soft Warning / Tool Masking / Semantic Compression"]
    D4 --> Out["Optimized Multi-Agent System E*<br/>Frozen Topology & Compiled Prompts for Test Evaluation"]

Key Designs

1. Unified ReAct Infrastructure & Assign-Deliver: Overcoming Static Workflow Rigidity -> Atomic ReAct Primitives with On-Demand Sub-Agent Tool Invocations -> Broad Optimization Freedom with Guaranteed Termination

Prior workflow search methods either restrict agents to shallow single-call nodes or attempt unconstrained code-level rewriting that frequently breaks execution. OptiMAS establishes a symmetric, ReAct-centric execution substrate where every agent \(A\) operates as an autonomous reasoner maintaining a trajectory \(S_i = (P_A, \tau_1, a_1, o_1, \dots, \tau_i, a_i, o_i)\). Rather than pre-defining hard-coded routing or static execution schedules, multi-agent collaboration is orchestrated via an on-demand "assign-deliver" protocol: a parent agent delegates sub-tasks to child agents explicitly via tool invocations, and child agents resolve the task within their own private environment and return structured deliverables as tool observations. The evolutionary optimization scope \(\mathcal{E}\) encompasses the agent population \(\mathcal{A}\), the orchestration graph \(G(\mathcal{A})\), backbone models \(M_A\), compiled prompts \(P_A\), skill sets \(K_A\), and accessible toolkits \(T_A \subseteq \mathcal{T}\). To preserve absolute operational stability, tools are composed from a predefined macro-library rather than synthesized from scratch, and \(G(\mathcal{A})\) is structurally constrained to a Directed Acyclic Graph (DAG), guaranteeing deterministic termination without deadlocks.

2. Textual Gradients & Adaptive Sampling Optimization: Inefficient Tree Exploration -> Full Workspace Backward Audit with Priority Resampling -> Preventing Search Isolation and Ensuring Monotonic Improvement

Evaluating candidate architectures over entire datasets incurs prohibitive computational costs and fails to provide fine-grained causal diagnosis. OptiMAS formulates evolution as data-driven mini-batch optimization. In each step \(t\), an adaptive sampling strategy reserves a fraction \(\phi = 0.5\) of the batch size \(n=10\) specifically for queries that failed in the preceding step (\(F_{prev}\)), while drawing the remaining slots probabilistically from \(X_{train}\). The optimizer inspects the detailed artifacts in \(W_{train}\)โ€”including failed shell commands, malformed regex queries, and incomplete file editsโ€”to derive textual gradients (\(\nabla_{text}\)) that precisely pinpoint missing collaboration protocols or ambiguous instructions. Furthermore, the optimizer only receives the scalar accuracy \(R_{val}\) and its step-over-step differential \(\Delta R_{val}\) over the held-out validation set \(X_{val}\), while validation workspaces remain strictly invisible, preventing parameter and prompt over-fitting on training failure modes.

3. Dual-Track Memory & Hypothesis-Driven Evolution: Severe LLM Amnesia & Decision Drift over Long Horizons -> Structured Intra-Step Plan & Falsifiable Scientific Ledger -> Traceable Causal Evolution and Compounding Experience

Across multi-epoch optimizations involving millions of trajectory tokens, LLM optimizers inevitably suffer from context amnesia, hallucinated modifications, and accidental reversions of effective designs. OptiMAS addresses this by decoupling memory into two coordinated mechanisms. Plan-oriented short-term memory enforces intra-step rigor: prior to modifying \(\mathcal{E}\), the optimizer outlines a structured plan tracking tasks across four states (waiting, executing, completed, dropped); instructions can never be erased, and dropped tasks require explicit justifications. At step conclusion, a programmatic check in finalize_optimization halts delivery if any task remains un-terminal. Hypothesis-driven long-term memory maintains an evolving disk-persistent ledger of falsifiable scientific hypotheses across steps. Each hypothesis records observations, root cause analyses, prescriptive actions, measurable expectations, and concrete evidence trails, adhering to a strict lifecycle:

\[\text{PROPOSE} \xrightarrow{\text{Apply Changes}} \text{ENACT} \xrightarrow{\text{Trajectory Evidence Validated}} \text{VALIDATE}\]

If an enacted modification causes regression or fails to deliver expected behavioral shifts, it transitions via \(\text{ENACT} \rightarrow \text{REFUTE}\), triggering targeted rollback, or shifts to \(\text{SUSPEND}/\text{DORMANT}\). This ensures that every MAS modification is traceable to a hypothesis identifier, transforming undirected evolutionary search into an evidence-grounded scientific refinement process.

4. Three-Tier Context Lifecycle Management: Massive Trajectory Context Explosions -> Progressive Capacity Envelope Cascade -> Reliable Long-Horizon Operation with Information Preservation

In complex software engineering and deep web navigation tasks, agent context histories expand rapidly, causing context window overflows or information loss if arbitrarily truncated. Built on the Model Context Protocol (MCP) client-server architecture, OptiMAS incorporates a three-tier capacity envelope based on current payload size \(S(H_t)\): - Tier 3: Soft Limit (\(S > C_{soft}\)): Injects non-restrictive advisory warnings encouraging the agent to invoke phase_done_and_summarize proactively to distill its progress; - Tier 2: Hard Limit (\(S > C_{hard}\)): Dynamically masks all operational tools (file editing, shell execution, search) from the agent's schema, restricting available actions strictly to phase summarization or task finalization; - Tier 1: Force Limit (\(S > C_{force}\)): Executes an automated LLM semantic compression pipeline that segments history into task preambles (\(P\), preserved verbatim), the latest turn (\(L\), preserved verbatim), and the compressible middle segment (\(C\)). Segment \(C\) is structured into an actionable summary capturing task understanding, completed actions, key decisions, active working state, pending plans, blockers, and verbatim identifiers. If LLM summarization fails, the system safely falls back to deterministic tail-drop compaction retaining the most recent \(0.7 \times C_{hard}\) tokens.

Search and Evolutionary Optimization Strategy

OptiMAS guarantees steady convergence and robust architecture optimization through the following rigorous operational policies: 1. Adaptive Probability Weight Updating: For each sample \(x_i \in X_{train}\), the sampling weight \(p_i\) is updated dynamically at each step. If \(x_i\) is solved correctly, its priority is discounted by \(p_i \leftarrow \max(p_{min}, p_i \cdot \alpha)\) with decay factor \(\alpha = 0.6\); if failed, it is boosted via \(p_i \leftarrow \min(p_{max}, p_i \cdot \beta)\) with boost factor \(\beta = 1.2\). Clamping boundaries \(p_{min} = 0.2\) and \(p_{max} = 2.0\) enforce a strict \(10\times\) probability ratio limit, preventing distribution degeneration. A global reset to uniform probability \(p_i \leftarrow \frac{1}{|X_{train}|}\) is enforced every \(\tau = 2 \times \lceil |X_{train}| / n \rceil\) steps. 2. Evidence-Grounded Rollback and Refinement: Architectural promotions and prompt adjustments are strictly forbidden from relying on aggregate validation scores alone; they mandate explicit trajectory-level proof that the mechanism solved the intended failure mode without side effects. In the event of conflicting hypotheses or regressions, the persistent ledger enables precise rollbacks to validated ancestral configurations.

Key Experimental Results

Main Results

The framework was evaluated across four diverse agentic benchmarks: WorkBench (hierarchical workplace task execution across six enterprise domains, 690 tasks), GAIA-text (multi-modal and multi-tool reasoning, 103 tasks), BrowseComp (long-horizon web exploration and cross-source verification, 100-query subset), and SWE-Bench-Verified (resolving real-world GitHub issues, 100-query subset). Evaluations spanned three distinct LLM backbones: closed-source GPT-5-Nano (128K context), open-source Qwen-3.6-35B-A3B (262K context), and frontier Gemini-3-Flash (1M context). The main results across all settings are presented below:

Benchmark Dataset Backbone LLM Initial Baseline Single \(E_0\) Hand-Crafted SOTA (SWE-Agent / Tongyi-DR) Evolutionary Baselines (ADAS / DGM) OptiMAS (Ours) Relative Gain over \(E_0\)
WorkBench (%) GPT-5-Nano 18.6 15.0 (Debate) 41.6 (ADAS) 64.0 +45.4%
Qwen-3.6-35B 65.6 57.4 (SMoA) 56.4 (EvoAgent) 84.5 +18.9%
Gemini-3-Flash 71.7 66.3 (SMoA) 67.5 (EvoAgent) 92.93 +21.23%
GAIA-text (%) GPT-5-Nano 49.5 62.9 (Tongyi-DR) 41.9 (EvoAgent) 56.9 +7.4%
Qwen-3.6-35B 73.1 80.7 (Tongyi-DR) 46.8 (EvoAgent) 81.2 +8.1%
Gemini-3-Flash 80.7 75.8 (Tongyi-DR) 62.9 (EvoAgent) 87.1 +6.4%
BrowseComp (%) GPT-5-Nano 8.3 10.0 (Tongyi-DR) 3.3 (ADAS/Evo) 11.1 +2.8%
Qwen-3.6-35B 33.9 38.3 (Tongyi-DR) 8.3 (ADAS) 43.8 +9.9%
Gemini-3-Flash 52.2 48.3 (Tongyi-DR) 23.3 (EvoAgent) 58.3 +6.1%
SWE-Bench (%) GPT-5-Nano 29.4 16.7 (SWE-Agent) 18.3 (ADAS) 41.7 +12.3%
Qwen-3.6-35B 61.1 67.2 (SWE-Agent) 25.0 (DGM) 68.9 +7.8%
Gemini-3-Flash 72.8 75.0 (SWE-Agent) 55.0 (DGM) 77.2 +4.4%

(Note: Bold text denotes the best performance in each column; Tongyi-DR and SWE-Agent represent top domain-specialized handcrafted systems; DGM is non-executable on web benchmarks due to sandbox constraints marked as -).

Ablation Study

To rigorously dissect the contribution of each core architectural component, ablation experiments were conducted on WorkBench and SWE-Bench-Verified across two representative backbones:

Ablation Configuration WorkBench (GPT5) WorkBench (Qwen3.6) SWE-Bench (GPT5) SWE-Bench (Qwen3.6) Key Empirical Observations & Mechanics
Initial Single-Agent \(E_0\) 18.6 65.6 29.4 61.1 Minimalist baseline lacking specialized skills and collaborative roles
OptiMAS Full System (\(n=10\)) 64.0 (+45.4) 84.5 (+18.9) 41.7 (+12.3) 68.9 (+7.8) Full framework with adaptive sampling, dual-track memory & validation guard
Reduced Batch Size (\(n=4\)) 55.0 (+36.4) 81.1 (+15.5) 24.4 (-5.0) 62.8 (+1.7) Weaker backbones produce fully failed batches, depriving optimizer of positive gradient signal
w/o Validation Metric 58.2 (+39.6) 82.8 (+17.2) 28.9 (-0.5) 64.4 (+3.3) Absence of scalar generalization signal leads to mild over-fitting on training failure modes
w/o Hypothesis Memory 53.9 (+35.3) 71.4 (+5.8) 22.2 (-7.2) 53.3 (-7.8) Severe catastrophic regression below \(E_0\); evolution degrades into isolated trial-and-error
w/o Adaptive Sampling 60.3 (+41.7) 75.1 (+9.5) 24.4 (-5.0) 60.6 (-0.5) Optimizer loses targeted re-evaluation of prior errors, failing to verify hypothesis fixes

Key Findings

  • Hypothesis memory is the critical anchor for sustained evolution: Removing the hypothesis-driven long-term memory caused severe regression, dropping SWE-Bench accuracy by more than 7% below the initial baseline \(E_0\) on both backbones (-7.2% on GPT5, -7.8% on Qwen3.6). Without a persistent ledger tracking falsifiable expectations, the optimizer constantly reverts effective improvements and repeats failed interventions.
  • Evolutionary gains inversely correlate with backbone reasoning capacity: The largest relative performance improvements were achieved on the lightweight GPT-5-Nano backbone (+45.4% on WorkBench, +12.3% on SWE-Bench), whereas frontier Gemini-3-Flash yielded gains of +4.4% to +21.23%. This demonstrates that specialized emergent workflows, role delegation, and domain-adapted skills can effectively compensate for intrinsic reasoning deficiencies in smaller models.
  • Task-agnostic optimization outperforms specialized handcrafted systems: With a single invariant optimizer configuration, OptiMAS surpassed domain-specialized handcrafted systems on their native benchmarks, exceeding Tongyi-DeepResearch on GAIA (81.2% vs. 80.7%) and BrowseComp (43.8% vs. 38.3%), and outperforming SWE-Agent on SWE-Bench (68.9% vs. 67.2%).

Highlights & Insights

  • Paradigm Shift in MAS Evolution: Replaces discrete branch-and-discard search with a data-driven continuous optimization paradigm, using execution trajectories as loss signals to extract textual gradients and deliver smooth, near-monotonic architectural refinement.
  • Scientific Falsification Lifecycle: Enforces a rigorous hypothesis lifecycle (PROPOSE \(\rightarrow\) ENACT \(\rightarrow\) VALIDATE / REFUTE) grounded exclusively in trajectory-level causal evidence rather than stochastic scalar score fluctuations, preventing hallucinated and destabilizing mutations.
  • Robust Model Context Protocol (MCP) Foundation: Client-server decoupling combined with a three-tier capacity envelope allows the optimizer to process 1.4Mโ€“3.2M tokens per step seamlessly, bringing automated multi-agent evolution to production-grade feasibility.

Limitations & Future Work

  • Reliance on Minimum Backbone Tool-Use Proficiency: The framework relies on autonomous ReAct tool calling, hierarchical sub-agent delegation, and structured context summarization. Extremely small or quantized edge models that cannot reliably follow JSON schemas or system protocols may struggle to operate within this substrate.
  • High Computational Token Overhead During Training: Processing 1.4M to 3.2M trajectory tokens per step over multi-epoch runs requires substantial API token budgets or dedicated local compute infrastructure, though post-evolution inference operates at standard deployment costs.
  • Predefined Macro Tool Library Constraints: To guarantee execution safety, tools are composed from a predefined macro-library \(\mathcal{T}\). Extending the optimization scope to synthesize sandboxed, arbitrary tool implementations safely remains an open research frontier.
  • vs ADAS / AFlow: ADAS and AFlow rely on discrete tree search and programmatic workflow mutation where discarded branches lose accumulated insights; OptiMAS maintains a continuous optimization trajectory with cross-step hypothesis memory to ensure compounding progress.
  • vs Darwin Gรถdel Machine (DGM) / Gรถdel Agent: DGM permits arbitrary code modification of agent scripts, frequently inducing syntax errors and non-executable states; OptiMAS achieves expansive optimization scope (prompts, skills, DAG topologies, tools) under a stable configuration-driven ReAct substrate.
  • vs SWE-Agent / Tongyi-DeepResearch: Handcrafted systems require extensive manual engineering and domain-specific reinforcement learning fine-tuning; OptiMAS automatically evolves competitive or superior multi-agent coalitions from an un-tuned single-agent baseline using a universal, task-agnostic optimizer.

Rating

  • Novelty: โญโญโญโญโญ Formulates multi-agent evolution as continuous data-driven textual gradient optimization with a scientific hypothesis lifecycle.
  • Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluations across four challenging benchmarks and three distinct model backbones with deep ablation analyses.
  • Writing Quality: โญโญโญโญโญ Rigorous conceptual formulation, exceptionally clear architectural exposition, and comprehensive appendix details.
  • Value: โญโญโญโญโญ Establishes a highly practical, robust engineering foundation for the automated discovery and deployment of complex multi-agent systems.