Scaling Discovery through Test-Time Communication
Jongho Park, Vasilis Kontonis, Shivam Garg, Akshay Krishnamurthy, Dimitris Papailiopoulos
cs.LG, cs.AI, cs.CL
2026-09-18
Identical agents sharing a workspace beat best-of-k: team@5 hits 8.0% on ARC-AGI-3 (matching 33 independents), packing 0.945, and a 1,957-byte MNIST classifier.
The default way to spend test-time compute is to sample k independent traces and keep a majority vote or best@k. Intermediate results, failed experiments, and reusable artifacts in one trace never reach a sibling that is still searching. That waste is larger for agents that sit on a terminal, run code, and stay alive for hours.
Whether talking helps is unsettled. Debate often loses to chain-of-thought. Without a verifier, teams drift toward a wrong majority or dilute an expert judgment into a compromise. Anthropic found coordinating agents surface more vulnerabilities, yet tokens per vulnerability look similar inside a matched search scope. When a task splits cleanly into subtasks, parallelism already explains the gain. The open question is whether communication can turn parallel search into cumulative progress when the work does not split.
The Berkeley and Microsoft Research setup is deliberately thin. k identical GitHub Copilot CLI agents share a model, instruction, and container. No roles, no orchestrator. Each agent keeps a private scratch directory and a shared task filesystem. They talk through an append-only log, plus records of adopted approaches, disconfirming evidence, and a scoreboard. The only protocol-level allocation is a slot: agents race to create numbered directories with an atomic filesystem operation so two of them do not claim the same approach.
The prompt forces two habits. Declare a distinct approach after seeing claimed slots. Adopt a peer's method only after a clearly better measured result, and keep one meaningful variation even then. Scores are how bad ideas get filtered. The paper calls this verified progress sharing: once a measurable gate is cleared, the whole group continues from that state, rather than each agent walking the full trajectory alone.
The comparison is team@k versus best@k at matched per-agent resources. Three tasks: 25 public ARC-AGI-3 games with Claude Sonnet 4.6 (64 solo trials per game, 20 team trials); Frontier-CS polyomino packing with Sonnet and Opus 4.6; MNIST classifier compression with a 99.4% test-accuracy floor and gzip-9 size of code plus weights, using four GPT-5.6 Sol agents for 96 hours.
On ARC-AGI-3, a single Sonnet 4.6 agent clears a full game less than 1% of the time. team@3 reaches 4.6% versus 1.4% for best@3; 13 independent agents are needed to hit 4.7%. team@5 reaches 8.0% versus 2.2% for best@5; 33 independents hit 8.1%. The multiplier grows from 4.3× to 6.6×. The gap widens with depth: at k=5 it is 1.2× on shallow levels and 3.6× on a full solve.
Some games stay closed to solo search. LP85 has 0 solves in 64 solo trials and a 65% solve rate under team@5. FT09 moves from 9.4% for a single agent and 25.9% for best@3 to 90% for team@3. Across the four games team@5 ever solves, the average solve rate rises from 13.8% to 50.0%. Communication helps on 18 of 25 games and hurts on 7. The best gain is +4.30 levels on LP85; no loss exceeds 0.85.
| Setup | Full-game solve rate | Independents needed |
| best@3 | 1.4% | n/a |
| team@3 | 4.6% | 13 (4.3×) |
| best@5 | 2.2% | n/a |
| team@5 | 8.0% | 33 (6.6×) |
Tokens are not free. team@3 and team@5 spend about 8 million and 24 million output tokens, nearly twice best@k. Matching the team's solve rate still costs 3.8× and 4.9× as many tokens from pools of 13 and 33. Below about 400K output tokens per agent, best@k still leads: a coordination tax. Cut each of five agents to 0.2× the native action budget and team@5 dies after level 1 on LP85 and level 3 on SB26, losing to a single agent with the same total budget. Give each the native budget and team@5 finishes SB26 15% of the time versus about 8% for best@5 and 0 for a 5×-budget solo agent; on LP85 the team finishes 65% while best@5 falls to 0 by level 4.
Action efficiency moves too. Mean RHAE of the best member rises from 3.8% solo to 9.7% in team@3 and 13.6% in team@5, above 7.0% and 8.8% for best@3 and best@5. The average member of team@5 sits at 8.9%, matching the best of five independents.
On packing, the prior best was 0.894 from Qu et al. with four Opus 4.6 agents. A Sonnet team@3 run hits 0.945 inside the official three-hour limit, against 0.883 for the strongest solo, cutting unused area from 11.7% to 5.5%. Over 72 hours, Opus team@4 reaches 0.922 versus 0.893 solo, and Sonnet team@4 reaches 0.910 versus 0.891. The winning three-hour trace is a relay: a1 proposes contact maximization and implements it slowly; a2 rebuilds from the log and adds all-orientation search past 0.90; a3 adds a boundary bonus to 0.945. On one 172-piece instance, density goes from 74.9% to 93.8%.
For MNIST compression, the human reference tinyMNIST reproduces at 2,461 bytes and 99.40% accuracy. best@4 stops at 3,160 bytes. Independent runs sit in a 3–5KB band and never cross the human line. team@4 crosses after about 20 hours and finishes at 1,957 bytes and 99.41%, 20.5% smaller than the human artifact. The team trails for the first hour and the first 100K output tokens.
On Terminal-Bench 2.0's 89 tasks, team@2 averages 60.67%, above pass@1 at 52.53% and below pass@2 at 62.36%. The official verifier often runs after the agent finishes, and intermediate checks do not always rank partial solutions. team@2 also writes one shared final container state, while pass@2 keeps two isolated attempts.
This is a condition table, not a claim that multi-agent systems always win. Communication turns parallel search into cumulative progress when the task does not split, when agents can query a score or a level signal, and when each agent has enough budget to explore on its own. Miss those, and independent sampling is cleaner and skips the coordination tax.
For people shipping agents, the default on short tasks with weak feedback is still best@k. On long-horizon algorithm search, compression, and leveled exploration, a shared workspace plus a scoreboard can beat opening more independent copies. The protocol is small: claim a slot, publish evidence, follow only a better score, keep a variant.
The ARC lift is concentrated. Most of the 25 games remain out of reach for Sonnet 4.6 either way. LP85, unsolved in 64 solo trials and solved 65% of the time by a team of five, is the case that communication can open a region a single agent never reaches.
The authors draw the boundary themselves. At low budget the coordination tax dominates. Without a ranking signal for partial work, communication can lose to pass@k. The harness is one shared-workspace scaffold of homogeneous, unassigned peers, so the result does not transfer to role graphs or mixed models. Herding can collapse k agents into g duplicate search groups; sharing helps only while independent search still happens after a transfer.
The experiments have soft spots. ARC uses an unsaturated Sonnet 4.6 on purpose; the text notes that GPT-6 Astra already clears this benchmark easily, and whether the communication gain shrinks as the base model saturates is untested. The 72-hour packing study has two team@4 trials, and the authors say the 0.922 / 0.910 scores sitting below the three-hour 0.945 is likely the small sample. Terminal-Bench is a handful of trials, treated as descriptive. The packing case study used Opus 5 to read traces after the fact, which is a recap, not a controlled comparison.
Whether the same pattern holds when feedback is sparse, noisy, or subjective is left open.