CS Paper Radar

Global Coherence: When Every Agent Is Right and the Team Is Still Wrong - A Local-to-Global Semantic Foundation for Multi-Agent Collaboration

Xin Heng

cs.AI ·submitted 2026-10-01 16:49 UTC · v3
theoryhot direction

Abstract

AI agents share code, documents, tools, and analyses. No participant sees the whole state, so every step can look right while the combined result is wrong. We call this the global coherence problem. It is a problem of state, not only of intelligence: a stronger model decides better locally, but cannot see what is missing from its context. The Observation-Aliasing Impossibility Theorem gives the exact condition. An agent can always act validly exactly when every world consistent with its context allows a common action. When look-alike worlds need different actions, no reasoning, role, message, or sample can guarantee the right one; with k such worlds whose valid actions are disjoint, the best randomized policy succeeds with probability 1/k. Finding the smallest sufficient context is NP-hard, but refinement finds one and keeps it current as rules change. A second failure survives full information: valid pieces can fail to fit into one world. The same theorem sets the conditions for coherence; sheaves and groupoids are one way to meet them. Models propose, and the harness decides what is valid. Ten studies test it. On TeamBench, teams overspend a shared budget in 5/5 runs; showing them the live count still leaves 4/5, and a harness that owns the budget leaves 0/5. Identity collisions that no pairwise check can see appear in 23 of 45 public alignment networks; split-view agents create them in 9 of 40 merges, and a network check removes all nine. A frontier LLM solves 40/40 revision tasks when it sees the deciding event; with the event hidden, no arm that reasons longer, votes, or splits into roles significantly beats chance, and a companion study replicates this on models from a second provider. In tau2-bench Telecom, after a silent revert, the harness scores 1.00 against 0.07 for call-time policy checks. Refinement keeps a sufficient context at 28% of the cost of sharing every field.

Comment
44 pages. Revised: simpler wording with one term per concept, and the hidden-fact study replicated on models from a second provider. Companion paper: "Knowing Is Not Deciding: Symmetry Breaking and Ownership in Multi-Agent Systems", doi:10.5281/zenodo.23893802

Closest papers

Nearest neighbours by meaning across the whole index.

Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration

cs.MA cs.AIcs.LGmath.OC ·2026-10-20 ·Ivan Ilin, Peter Richtárik
theorycode/data similarity 0.61
Abstract · 59 pages, 15 figures, 28 tables. Code: https://github.com/vectozavr/local-work-global-progress

Teams of large language model (LLM) agents are increasingly applied to complex tasks, but their collaboration protocols are mostly designed empirically, without convergence guarantees. We formalize collaborative problem solving as block optimization: each agent improves one part of a shared solution, guided by its local objective plus a correction for how its changes affect the other parts. A coordinator checks every proposal against the global objective and merges proposals that do not interfere with each other. We prove linear convergence up to an error floor that vanishes when the corrections are exact. Interfering proposals can also be merged once their combination has been checked; the rate then depends on how well the proposals actually combine, not on worst-case interactions. With GPT-OSS-120B agents on robot routing, a three-agent team finds collision-free plans in every run, better than those of a single agent that controls all robots. On a larger routing task, a six-agent team completes its search about twice as fast as the single agent (in median). Merging the best checked combination of proposals, rather than only proposals that do not interfere, cuts the team's search time by about 30%. With constants measured on the runs, our convergence bound holds in every round and follows the observed progress. We also test the theory on query planning in SQLite and on a synthetic task.

0.59

Theory of Scene: Breaking the Symmetry Trap in Multi-Agent LLM Coordination

cs.LG cs.CLcs.MA ·2026-09-26 ·Liangqi Yuan, Wenzhi Fang, Shiqiang Wang, Christopher G. Brinton
benchmark similarity 0.60
Abstract

Multi-agent systems built on large language models (LLMs) are largely homogeneous, as their agents behave alike even across distinct LLMs. We show that when such agents act concurrently without communication, they collide on targets they must split and diverge on targets they must take together, a double failure we term the symmetry trap. Theory of Mind (ToM), widely used for coordination without communication, cannot escape this trap, since homogeneous agents form the same prediction of one another and respond to it in the same way. We propose Theory of Scene (ToS), a training-free reasoning schema in which each agent reads its public role, the only difference between the agents, and the task context they all observe. Homogeneous agents thereby derive one division of labor, each taking the part its role fixes, which turns homogeneity from the cause of the trap into the cure. ToS reads the role together with the scene through role gating, which determines whether ownership overlaps or is already divided, and the task context through task coupling, which infers whether the team must converge on each target, divide it, or take its stages in turn. We evaluate on DivvyBench, a controlled environment we introduce, whose target types make an episode Competitive, Cooperative, or Mixed across Tabletop, Airspace, and Household scenarios, and on two established agentic benchmarks, GovSim and Overcooked. ToS outperforms all six baselines on every benchmark, and each baseline falls far behind it in at least one setting. Against ToM given the same inputs, ToS raises the DivvyBench success rate from 71.1% to 99.6%, the GovSim total gain from 207 to 400, and the Overcooked level-normalized throughput from 1.41 to 1.67.

0.36

MELD: A Protocol for Merging Knowledge Across Distributed Agentic Memories

cs.DC cs.AIcs.MA ·2026-08-17 ·Lauri Lovén, Jaakko Sauvola, Jukka Riekki, Sasu Tarkoma
similarity 0.60
Abstract · 30 pages, 3 figures, 1 table, plus an 11-page appendix (A-N). Code and experiment data: https://doi.org/10.5281/zenodo.21878274

Autonomous agents share a transport and can call each other's tools, but they cannot share what they know: no protocol lets two agents' memories reconcile a fact phrased two ways, link related facts held apart, or reconcile contradictory knowledge without silently discarding either claim. We present MELD, a self-managing coherence mechanism for a federation of agent memories whose run-time model is the knowledge graph itself. Each brain admits every incoming claim through a five-outcome procedure (insert, merge, relate, conflict, or reject), decided from three signals (scoped claim-key identity, embedding similarity, and a natural-language-inference verdict) under context and freshness gates, and acting through exactly one auditable, authenticated Patch, the only object that mutates state. A binding onto standard publish/subscribe transport with a per-claim status CRDT keeps sovereign brains coherent in claim status without a coordinator: self-healing after partitions and under lossy routing, and self-protecting against silent rewrite by a peer, under a benign-fault model. MELD does not adjudicate truth; a detected contradiction is preserved for later adjudication, never silently resolved. On HotpotQA distractor, distributed merge is recall-non-inferior to a centralized store under a pre-specified equivalence test and recall-superior to naive union at about 11% less live storage; the merge classifier separates at AUC 0.968 with a 0.013 false-merge rate on adjudicated candidate pairs; the status CRDT reconverges in 30/30 real partition-heal trials where last-writer-wins manages 11/30; and semantic routing delivers about 3x fewer messages at matched recall. We evaluate on a real computing continuum spanning an operator-grade 5G edge, national HPC, and a local tier, with empirically calibrated thresholds.

0.55

Zero-Shot Coordination among LLM Agents

cs.LG cs.AI ·2026-11-04 ·Adrian Hayler, Shashank Reddy Chirra, Andrei Lupu, Johannes Forkel, Bidipta Sarkar +2 more
publishedcode/data similarity 0.59
Abstract · NeurIPS 2026 Poster. ICLR 26 MALGAI Workshop Oral. The first two authors contributed equally

We study zero-shot coordination (ZSC), where independently developed agents must coordinate at test time. While ZSC has been well studied in the RL literature, far less is known about the performance of LLM agents despite their increasing deployment in such settings. Existing work on LLM coordination often relies on specialised scaffolding that independently developed agents are unlikely to share in practice. Moreover, evaluations on complex environments (e.g., Hanabi) make it difficult to pinpoint the sources of coordination failure. In contrast, we focus on simple, general-purpose scaffolds in minimal environments designed to isolate specific coordination challenges. Our results show that even in these controlled settings, frontier LLM agents struggle to coordinate, largely due to limited understanding of the coordination problem and weak reasoning about their partner's beliefs. While LLMs introduce semantic information as an additional axis for coordination, they nonetheless fail to exploit this structure effectively. Towards this, we propose Coordination-friendly definitions (CFDs) as a principled approach for enabling robust coordination among LLM agents. Finally, we show that CFDs can be discovered automatically, removing the need for manual engineering. Code is available at https://github.com/ahayler/zsc-llm-agents.

0.56

Topological Coherence for Self-evolving Multi-agent Systems

cs.AI ·2026-09-29 ·Sen Zhao, Ruiqi Kong, Zuyu Zhang, Lifeng Shen, Xinyu He +2 more
similarity 0.59
Abstract

Complex tasks inherently couple workflow structure, agent responsibility, collaboration, and memory access: task regions delimit responsibility and tool scope, cross-region dependencies give rise to handoffs, and ownership boundaries delimit private and selectively shared memory. Existing methods can jointly optimize agent and communication structures, yet such optimization does not by itself require responsibility, handoff, and memory boundaries to remain consistent with task dependencies. We term this requirement topological coherence. We introduce TOCOMAS, a Topology-Coherent Multi-Agent System. TOCOMAS grounds a task graph in tool interfaces, organizes compatible task nodes into reusable responsibility domains, and derives dependency-induced and profile-conditioned collaboration together with boundary-regulated memory visibility. During online self-evolution, TOCOMAS proposes coupled changes to agent, collaboration, and memory policies, retaining for subsequent tasks only candidates that satisfy structural constraints and improve evaluated reward. Across BBEH, WorkBench, SWE-Bench-Verified, and CoMemBench, TOCOMAS improves task success over baselines across backbones. CoMemBench also shows gains over the self-evolving baseline in verified progress, handoffs, and memory isolation.

0.12

Communications-free Collective Intelligence Via Allocentric Belief

cs.RO eess.SY ·2026-11-18 ·Cameron Mehlman, Arjun Mulchandani, Hovik Grigoryan, Anurag Koyyada, Gregory Falco
similarity 0.59
Abstract

A team of skilled card players share no information amongst each other, and yet still are able to coordinate their play by watching the same players and reading the same tells. Autonomous systems have failed to exploit this logic, relying instead on explicit communication or complex state estimation schemes that can fail when it matters most. Without it, decentralized agents diverge in their world beliefs, and coordination collapses. Here we show that anchoring all agents to a single shared external actor, a common witness whose reactions encode team state, produces spontaneous, communication-free coordination. An allocentric belief network trained on witness behavior allows each agent to independently reconstruct full team state, keeping group beliefs consistent with no inter-agent exchange. Across five competitive environments allocentric belief alignment outperforms egocentric approaches in collective performance, and even scales to sixty-agent teams where standard methods fail. These results establish a new principle for collective intelligence: in the absence of communication, a shared gaze replaces a shared channel.

0.19

Topological Sheaves of Irreducibility: A Theoretical Framework for Multi-Agent Task Obstructions

cs.LG cs.MA ·2026-10-19 ·Steven Motta, Davide Mambelli, Alessandro Rozza
similarity 0.59
Abstract · 31 pages, 1 figure, 3 tables

Multi-agent systems can differ under identical agents and communication budgets when they support different forms of joint interaction. We introduce Topological Sheaves of Irreducibility (TSI), a sheaf-theoretic framework separating task-level compatibility obstructions from system capability. A task is represented by an interaction complex $K$ and a capacity sheaf $\mathcal{F}$; nonzero $H^n(K;\mathcal{F})$ defines a structural signature, while registered interventions test capability. For cocycle data, cochain realization is solvable exactly when the represented cohomology class vanishes. Examples show that the signature is sheaf-relative, and the degree-1 reduction yields cycle-space witnesses and observation requirements. We evaluate two finite one-round models. Across 15,625 degree-1 inputs, an all-agent additive primitive solves decision and repair exactly; the optimal pairwise system reaches 88.80% on decision, one input above the 88.79% majority-class baseline, and 26.63% on repair. On a degree-2 tetrahedral-boundary task over 531,441 inputs, the same-2-skeleton system retains all four three-agent primitives yet matches the pairwise-only optimum throughout the registered separation window, whereas adding the class-filling four-agent primitive makes both tasks exact. Status-preserving robustness checks retain exact performance but are not cost-matched to the class-restoring ablation. Conditional on the registered primitives and cost models, TSI provides task-relative, falsifiable tests of higher-order interaction.

0.28

Self-Organizing Agent Teams Learn to Reason Together

cs.AI cs.MA ·2026-09-19 ·Aneesh Pappu, Mirac Suzgun, Yongchan Kwon, Federico Bianchi, Batu El +3 more
highly cited similarity 0.58
Abstract · Preprint

Collective intelligence depends not only on what team members know, but also on how they organize their work. When the structure of a solution is unknown, useful roles and divisions of labor cannot be specified in advance; teams must learn from experience how to organize reasoning as it unfolds. Human teams routinely adapt this way, while existing AI agent teams rely on fixed protocols, explicit task decomposition, or routing. We introduce Self-Organizing Agent Teams (SAT), fixed teams of AI agents that learn reusable strategies from prior collaborations to organize roles, conversational phases, participation, and information flow. These strategies enable what we call collaborative computation: agents exchange, challenge, repair, and synthesize partial reasoning into solutions no member produced independently. In two independent settings, we learn teamwork strategies that transfer unchanged to unseen benchmarks, using only 15 mathematics and 25 graduate-level knowledge problems. Across five mathematics and physics benchmarks, self-organizing teams average 66.7% accuracy, versus 48.8% for their strongest member, 58.7% for compute-matched inference by that agent, and 59.0% for a perfect router over members' independent answers; on AIME 2026, they exceed this router by 13.4 points. Because gains vary across benchmarks, we ask when self-organizing collaboration helps. Across eight benchmarks, demonstrability (the organizational-psychology construct of whether a team can distinguish correct from incorrect reasoning) strongly tracks improvement over the strongest member (Spearman $ρ=0.90$, $p=0.005$): teams benefit most when correct reasoning can be recognized once it appears. More broadly, these results suggest that organization itself can become an agent capability: agent teams can learn how to reason together and produce solutions their members could not reach independently.

0.52