MonoScale: Scaling Multi-Agent System with Monotonic Improvement

Technical Summary: MonoScale

Problem Statement
Large Language Model (LLM)-based Multi-Agent Systems (MAS) typically rely on a central router to decompose tasks and delegate subtasks to specialized agents. While expanding the agent pool by integrating new functional agents or tools is a natural strategy for increasing system capability, naive scale-up often leads to performance collapse. This failure occurs because routers face a "cold-start" problem when encountering new, heterogeneous, and potentially unreliable agents. Without grounded knowledge of an agent's specific capabilities, boundaries, and failure modes, the router may make mis-routing decisions (e.g., assigning high-precision tasks to unstable agents or delegating complex tool calls to agents unfamiliar with interfaces). These errors can amplify at the system level, causing end-to-end performance to stagnate or degrade as the pool grows, even when stronger agents are added. Existing methods either assume a static agent pool or lack controlled update mechanisms to prevent regressions during continual expansion.

Methodology: MonoScale
The authors propose MonoScale, an expansion-aware update framework designed to ensure monotonic non-decreasing performance as the agent pool grows. The framework operates through a two-stage process whenever a new agent is integrated:

1. Expansion-Aware Task Synthesis (Familiarization): Instead of waiting for real user traffic to reveal failures, the system proactively generates a small set of "warm-up" tasks conditioned on the new agent's profile (agent card). These tasks are synthesized via a planner-executor-validator loop to specifically probe the new agent's strengths, interface constraints, and failure modes. The router executes these tasks under its current policy to collect both successful and failed interaction traces.

2. Memory-Based Router Update: The collected evidence is distilled into auditable, natural-language memory entries. These entries encode actionable routing principles, including:

   • Positive constraints: When and how to invoke the new agent.
   • Negative constraints: When not to invoke the agent or under what conditions it fails.
   • Interface caveats: Specific tool usage patterns and error handling.

   The router policy is updated by selecting a safe memory state from a candidate set. This selection is governed by a trust-region constraint (inspired by Trust Region Policy Optimization) to prevent drastic behavioral shifts. Crucially, the candidate set always includes a conservative fallback option that forbids invoking the new agent, ensuring the system can revert to pre-expansion behavior if no safe update is found.

Theoretical Formalization
The authors formalize sequential agent augmentation as a contextual bandit problem. Under the assumption of non-interfering expansion (where adding a new agent does not alter the reward of plans that do not use it), they prove that their trust-region memory optimization yields a monotonic non-decreasing performance guarantee across expansion rounds. This provides a verifiable conditional lower bound for open MAS expansion.

Key Contributions

1. Problem Formalization: A unified model and notation for analyzing cold-start-induced performance collapse in sequentially expanding MAS.
2. Method and Protocol: An expansion-aware strategy involving agent-conditioned task synthesis and a router update protocol that utilizes auditable, rollbackable natural-language memory.
3. Theoretical Guarantee: A proof that, under non-interfering expansion and conservative fallback assumptions, the proposed method guarantees monotonic improvement during scaling.

Experimental Results
The authors evaluated MonoScale on the GAIA benchmark and the Humanity's Last Exam (HLE) multiple-choice subset, scaling agent pools from 3 to 10 agents.

• Stable Scaling: Unlike naive scale-up, which exhibited performance collapse (e.g., DeepSeek-V3.2 dropping from 0.558 to 0.491 on GAIA as agents increased from 5 to 10), MonoScale demonstrated consistent performance gains.
• Competitive Capability: A MonoScale system using a smaller open-weight router (Qwen-3-30B-A3B-Instruct) with 10 agents achieved an overall GAIA score of 55.15%, outperforming the 3-agent baseline of DeepSeek-V3.2 (51.52%) and competing with proprietary strong-router baselines like GPT-5 and Gemini-2.5-Pro.
• Robustness: In "Malfunctioning Pool" settings containing unreliable agents, MonoScale maintained stable performance, whereas strong-router baselines (e.g., Gemini-3-Pro) suffered significant degradation without memory updates.
• Transferability: Routing memory distilled by one router (Qwen) transferred effectively to another (Gemini-3-Flash) without adaptation, suggesting the memory captures router-agnostic agent profiles.

Significance and Claims
The paper claims that MonoScale provides a safe and controllable expansion protocol for large-scale, open agent onboarding in the emerging "Agentic Web." The authors argue that simply upgrading the router model does not solve the lack of execution-grounded evidence; instead, a mandatory warm-up protocol that probes new agents and distills both successes and failures into auditable constraints is essential to prevent post-expansion performance collapse.

The work is modest in its scope, noting that the monotonicity guarantee is conditional on non-interfering expansion (which may fail under persistent environment drift, such as changing external APIs). Furthermore, while effective up to 10 agents (with preliminary tests up to 20), the authors acknowledge that Web-scale settings (thousands to millions of agents) will require integrating retrieval-driven routing and explicit memory management strategies, which remain open challenges for future work.