MonoScale: Scaling Multi-Agent System with Monotonic Improvement

In recent years, LLM-based multi-agent systems (MAS) have advanced rapidly, using a router to decompose tasks and delegate subtasks to specialized agents. A natural way to expand capability is to scale up the agent pool by continually integrating new functional agents or tool interfaces, but naive expansion can trigger performance collapse when the router cold-starts on newly added, heterogeneous, and unreliable agents. We propose MonoScale, an expansion-aware update framework that proactively generates a small set of agent-conditioned familiarization tasks, harvests evidence from both successful and failed interactions, and distills it into auditable natural-language memory to guide future routing. We formalize sequential augmentation as a contextual bandit and perform trust-region memory updates, yielding a monotonic non-decreasing performance guarantee across onboarding rounds under a non-interfering expansion assumption. Experiments on GAIA and Humanity's Last Exam show stable gains as the agent pool grows, outperforming naive scale-up and strong-router fixed-pool baselines. Our code is available here.

Modern AI applications often rely not on a single model but on a team of specialized AI assistants (“agents”)—one for web search, one for code, one for reading documents, and so on—steered by a coordinator that decides which assistant should handle each step of a user’s request. As new specialists become available, one would like to keep adding them and watch overall capability grow. In practice, this often backfires: the coordinator has never worked with the new assistant, makes poor delegation choices, and the team’s performance can stagnate or sharply collapse the moment a new helper joins. We introduce MonoScale, a protocol for safely growing such teams. Whenever a new assistant is onboarded, MonoScale automatically generates a small set of trial tasks tailored to that assistant, observes its successes and failures, and distills the lessons, such as “use it for X, avoid it for Y,” into a short, human-readable notebook that the coordinator consults afterwards. A “do not use this new assistant” option is always kept as a safety net, so the team’s expected performance can never drop merely because a specialist was added. We prove this guarantee formally and verify it on standard benchmarks. There, MonoScale lets a smaller, openly available coordinator keep improving as its team grows from 3 to 20 assistants, while the same teams without MonoScale plateau or collapse; the protocol also stays robust when some new assistants are unreliable. We hope this offers a safer way to scale AI assistant teams as more specialists come online.