Scaling Multi-Agent Intelligence with Substrate-Centric Coordination
Zhenting Qi, Zhuokai Zhao, Rulin Shao, Kerem Oktar, Zhiyuan Yao, Himabindu Lakkaraju, Wen-tau Yih, Ansong Ni, Bhargavi Paranjape, Yilun Du
cs.CL, cs.MA
2026-10-12
ScaleMAS caps each search at 8 messages. Sixteen Qwen3.5-9B agents raise BrowseComp-Plus from 38.1% to 65.3%, and 128 agents reach 50.9% on Contradiction Audit.
Adding agents does not automatically make an LLM group more capable. Prior measurements show superlinear inference cost, diminishing or negative returns from extra agents, and groups that lose to a single agent on the same budget. ScaleMAS pins this on three effects that worsen with headcount: each reader must ingest more text, useful work is mixed with shared output of unknown quality, and one failed member can stall everyone.
All-to-all messaging dumps every peer's intermediate work on the receiver. A coordinator routes every sub-agent into one main context. Either design fills that context as the group grows. Workflows freeze each role and its successor at design time, and a coordinator is a single point of failure, so one crash can stop the run. Blackboards keep a note after its author leaves, and nobody has to wait on a named peer. The shared surface still grows with the group, and nothing marks which notes later work actually used.
Every agent runs the same prompt and the same loop. There are no roles, no direct messages, and no assigned subtasks. Execution is asynchronous. Besides the task's own tools, only publish, search, and visit can touch the store.
The store is append-only. A message records one finished piece of work: a subtask, an artifact, a short rationale, and references. A reference points at an earlier message or at a resource the task tools already expose. The address is fixed at write time and the text is never edited, so a citation still resolves to the wording it was written against. Subtask plus artifact is capped at 256 or 1,024 tokens, and a message carries at most 32 references.
publish is visible to every agent as soon as it is accepted. Every reference must already exist, and the rationale must name each one and say what it contributed. Fail either check and the whole message is rejected. search takes free text and returns at most 8 messages, ranked by BM25 lexical relevance normalized to the range 0 to 1, plus a citation weight. BM25 is a standard word-overlap ranker. visit fetches messages by address, again at most 8 per call. Author identity and weight are hidden from the reader.
A new message starts at weight 0. Each citation moves it 30% of the remaining distance toward 1. After every step of the group, all weights are multiplied by 0.98, so notes that later work keeps using get heavier and unused notes fade. A message with zero lexical score cannot surface on weight alone. One read therefore adds at most eight length-capped messages. How much an agent reads depends on how often it searches, not on how many agents are writing.
The tasks are BrowseComp-Plus deep research (first 100 questions), FATE proofs checked by the Lean 4 compiler, SWE-bench Verified (first 100 GitHub issues, on mini-SWE-agent), and Contradiction Audit. Audit uses documentation from 16 open-source projects. GPT-5.6 injects 20 contradictions into each corpus. Extra reports are not penalized, and a pair counts as found if it includes the edited snippet. Qwen3.5-9B runs audit level x4 (160 snippets per corpus) and mid-tier FATE-M. Claude-5-Sonnet runs the harder x8 audit and FATE-H. SWE-bench is Qwen only. Baselines are parallel ReAct with no communication, all-to-all Debate, the coordinator system AOrchestra, and DeLM, a blackboard over a shared context. The score is Pass@N: any one correct answer among the N submissions counts as success.
With Qwen, ScaleMAS from 1 agent to 16 moves retrieval from 38.1% to 65.3%, FATE-M from 24.0% to 56.0%, and audit x4 from 4.1% to 29.4%. SWE-bench stops rising after 8 agents, and so does ReAct. At about 20 million tokens, 8 ScaleMAS agents reach 60.0% on retrieval while 16 DeLM agents reach 26.0%. On SWE-bench, 4 ScaleMAS agents hit 80.0% with 15.3 million tokens; 8 ReAct agents need 28.3 million to match it. With Claude at about 3.5 million tokens, 8 ScaleMAS agents reach 79.8%, against 73.0% for 8 Debate agents and 72.0% for 4 ReAct agents. Debate from 2 to 16 agents on the Qwen retrieval task grows from 5.6 million to 48.5 million tokens while accuracy stays between 28% and 32%. Debate and DeLM never clear 7% on the audit. Claude on audit x8 goes from 10.6% with one agent to 57.5% with eight.
Turns per agent fall as the group grows. On Qwen retrieval the average drops from 304 to 205 at eight agents, and total turns are about 5.4 times a single agent. At 128 Qwen agents, FATE-M gains most of its ground by 16 and then sits just under 60%. Debate peaks at 32 and then declines. DeLM at 128 is worse than DeLM at 8. Audit x4 keeps climbing, to 50.9%. Messages in the most-cited fifth sit on a correct answer's evidence chain 85% of the time, against 29% in the least-cited fifth. Correct answers that use a gold document found by someone else, and never opened by the submitter, rise from 9% with two agents to 24% with eight.
Seven healthy agents plus one that fails on every step still score 19.4% on the audit, matching the healthy agents alone. DeLM falls below 1%. If each agent skips each step with probability 0.8, eight ScaleMAS agents still solve 22.0% of FATE-M, against 2.0% for one agent. AOrchestra loses more than half its score at probability 0.2, because it cannot lose the coordinator.
| Setup (4 Qwen agents) | Retrieval | FATE-M | SWE | Audit |
| ScaleMAS | 55.1% | 42.0% | 80.0% | 10.0% |
| Read only own messages | 46.8% | 38.0% | 71.6% | 6.6% |
| Parallel ReAct | 38.0% | 36.0% | 68.0% | 8.1% |
Reading other agents accounts for about half or more of the gain over independent sampling. On the audit, a private store (6.6%) scores below ReAct with no store (8.1%). Removing citation weight at eight agents drops retrieval from 60.0% to 40.8%, the audit from 23.1% to 9.7%, and FATE-M from 49.0% to 42.0%. On FATE-M, BM25 alone also reads about twice the tokens, 5.7 million against 2.7 million.
The cost that blows up in a multi-agent run is every agent rereading everyone else's output. A ScaleMAS read does not grow with the group. On retrieval and audit, tokens therefore rise more slowly than headcount, because a later agent can pick up a result that is already published.
On software engineering the gain is narrower. Four agents match the 80% of eight independent ReAct agents at about half the tokens, and both curves flatten after eight. The store does not invent patches the model cannot write. Agents are not trained for this medium. The lift comes from a hard cap on reading, and from search ranking notes that later work actually built on.
Runs stop at 128 agents, and the substrate is used only at inference time. Training agents to coordinate through it is left open.
The 65.3% figure is Pass@N. A correct answer showed up among 16 submissions. That is not a promise about which answer the system would commit to. At four agents on retrieval, ReAct scores 38.0%, a private store 46.8%, and full ScaleMAS 55.1%. Part of the gap is an agent keeping notes for itself.
Audit scoring is loose: extra guesses are free, and a hit only needs to include the edited snippet. GPT-5.6 both writes the contradictions and accepts them with four unanimous judges, so the claim that they cannot be found from memory is itself a model judgment. Each corpus has 20 injected pairs, not conflicts that arose in the docs on their own. FATE-M levels off under 60% once the group is large, so continued scaling shows up mainly on the audit. Citation weight also pushes a message forward once others build on it. The case studies show a wrong candidate losing rank, but there is no separate measure of how hard a popular error is to overturn. The step size, the decay, and the cap of 8 are a single default. SWE-bench has no Claude run.