cs.AIOct 1, 2026

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

Authors: Xin Heng

Organizations: Tote AI

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

AI agents can each make locally valid decisions yet jointly produce an invalid result. We call this the global coherence problem: a failure of shared state, not merely of model intelligence. Our Observation-Aliasing Impossibility Theorem gives the exact boundary. A policy can guarantee a valid action exactly when all worlds producing the same observation share an admissible action. If k indistinguishable worlds require pairwise-disjoint actions, the best randomized worst-case success is 1/k; more reasoning, roles, messages, or samples cannot recover the missing distinction. A stronger model can reason better within its context, but it cannot see beyond it. We then give local-to-global runtime semantics X = (H, C, G, F; D): topology H records overlapping scopes; category C governs state-changing actions; groupoid G retains reversible translations; sheaf F tests whether local views glue into one world; and minimal history D keeps only distinctions that alter legal futures. Models propose; the harness owns shared state and governs commit. Nine studies test both the failure and its boundary. On a controlled revision benchmark, the same frontier model scores 40/40 when the deciding event is visible; when it is hidden, tested arms score 12--17/40, consistent with chance (1/3); restoring one authoritative fact returns 40/40. On TeamBench, ordinary teams exceed a shared budget in 5/5 runs, a visible live count leaves 4/5 violations, and commit enforcement leaves 0/5. In tau2-bench Telecom, current-state checks score 0.07 after silent reverts, while the harness scores 1.00. Where a conventional solver already owns the complete relevant state, it ties the harness as predicted. The counterintuitive conclusion is that local intelligence cannot substitute for missing global state.

Figures & tables

Figure 1: The two failure modes. (a) Two worlds that need different actions produce the same view, so no policy that acts on the view can be right in both (Theorem 2.1 ). (b) Three views agree pairwise, yet no single world agrees with all three; the inconsistency lives on the loop, not on any edge (Sections 3.1 and 3.3 ).
Figure 2: The framework X=(H,C,G,F;D)\mathfrak{X}=(H,\mathcal{C},\mathcal{G},\mathcal{F};D) on one example. (a) Three agents share one beam. HH is the triangle of who shares what, and because it is a cycle, pairwise checks are not enough. G\mathcal{G} is the unit translations on its edges, which must return the identity around the loop. F\mathcal{F} asks whether the three local values come from one beam. (b) C\mathcal{C} is the real changes, which compose into a history and are checked at commit. DD is the little the harness must remember to check them; here it refuses an order priced for the old beam.
Figure 3: Headline results, all with the same LLM (models and settings in Section 5 ). (a) The LLM solves all 40 tasks when the deciding event is visible. With it hidden, the tested arms score 12–17 of 40 and none is significantly above chance ( 1/31/3 ); adding the missing fact (blue) gives 40/40 again. One majority-vote cell failed on an API error, so that arm has 39 tasks. (b) Each dot is one of five runs of TeamBench’s budgeted-workflow task (LH2). Ordinary teams overspend the 20-call budget in 5/5 runs; showing the live count still leaves 4/5; enforcing the budget at commit stops every run at exactly 20. (c) Ontology-alignment tasks under the stated unique-name rule: agents with split views leave hidden collisions in 9 of 40 tasks; a pairwise check never fires; a network-level check removes all nine, with the repair-quality cost reported in Study IX. (d) τ2\tau^{2} -bench Telecom tasks in which a change the agent already committed is quietly undone, scored by τ2\tau^{2} ’s own grader: the stock agent and call-time policy checks believe the job is done; the coherence harness sends one notice and the agent redoes the change in 15 of 15 episodes. Bars and dots are plotted directly from the recorded run results.
Figure 4: The architecture the theory leads to. Stochastic agents propose from their own contexts; the coherence harness keeps only the state that changes validity, checks each proposal, and commits accepted ones to the world. The five rows are the structures H,C,G,F,DH,\mathcal{C},\mathcal{G},\mathcal{F},D of Section 4.4 ; each is needed only when the map it guards (restriction, transition, translation, history) can lose information (Corollary 4.2 ).

Explore similar work

CardsList
Oct 1, 2026cs.CL

Right Answers, Wrong States: Hidden Information Failures in Multi-Agent Collaboration

Multi-agent systems are often judged by whether they reach the correct answer. This can miss a distinct failure: collaboration may leave behind a corrupted information state even when the immediate decision is correct. We call this an off-query failure. To study this failure in collaborative decision support, we introduce OffQuery, which separately evaluates evidence verification (T1), shared-state reconstruction (T2), and task resolution (T3) in two representative high-stakes settings: healthcare and disaster response. Across GPT, Gemini, and Qwen models, standard collaboration shows much stronger task performance than state reliability. Averaged over 21 model--setting combinations, task resolution reaches 64.7%, while evidence verification and state reconstruction reach only 14.3% and 43.1%. We trace this gap to selective information use: current queries often bypass corrupted facts, which become consequential when later tasks require them. We further introduce ReGround, which resolves conflicting evidence, verifies shared facts, reconstructs a trusted state, and reasons over that state. Across seven models from three families, ReGround improves all three capabilities in every evaluated setting, with average relative gains of 309.0%, 82.9%, and 17.6% on T1, T2, and T3. Reliable collaboration therefore requires both a correct decision and a reliable shared state for future reasoning.

Herun Wan, Jiaying Wu, Minnan Luo +4

Xi’an Jiaotong University · National University of Singapore · Yunnan University +1

CollaborationMulti-Agent ReasoningSoftware Engineering Decision SupportAnswerMotion Reconstruction Branch
AskPDF
May 8, 2026cs.AI

TeamBench: Evaluating Agent Coordination under Enforced Role Separation

Agent systems often decompose a task across multiple roles, but these roles are typically specified by prompts rather than enforced by access controls. Without enforcement, a team pass rate can mask whether agents actually coordinated or whether one role effectively did another role's work. We present TeamBench, a benchmark with 851 task templates and 931 seeded instances for evaluating agent coordination under operating system-enforced role separation. TeamBench separates specification access, workspace editing, and final certification across Planner, Executor, and Verifier roles, so that no role can read the full requirements, modify the workspace, and certify the final answer. Prompt-only and sandbox-enforced teams reach statistically indistinguishable pass rates, but prompt-only runs produce 3.6 times more cases where the verifier attempts to edit the executor's code. Verifiers approve 49% of submissions that fail the deterministic grader, and removing the verifier improves mean partial score in the ablation. Team value is also conditional. Teams benefit when single agents struggle, but hurt when single agents already perform well. A 40-session human study under the same role separation shows that our benchmark exposes interaction patterns that pass rate misses. Solo participants work through the task directly, human participants paired with agents often collapse into quick approval, and human teams spend more effort coordinating missing information across roles.

Yubin Kim, Chanwoo Park, Taehan Kim +9

MIT · Google Research · Independent Researcher +1

TeamingRoleKernel-Resident Tool Governance GatewayVerification Framework
AskPDF
Sep 30, 2026cs.AI

Worse Together: How Performance Breaks Down in Multi-User Multi-Agent Teams

People are increasingly delegating tasks to AI agents, and those agents are increasingly encountering other people's agents over shared resources such as a codebase, a calendar, or a budget. When each agent acts for a different user with different goals, coordination often fails, and the group ends up worse off than if a single agent had acted for everyone. We study this multi-user, multi-agent setting across five frontier models and 77 scenarios in four environments: an API key environment in which agents share a compute budget, a clinic in which they share a calendar, a personal assistant environment in which they share a group order or booking, and a merge queue in which they share a release cutoff. In each scenario, we compare a single agent that serves every user (a coordinator) to a team in which each agent serves one user, with and without a communication channel between the agents. Teams deliver worse group outcomes than the coordinator in every environment: without a channel, they completely collapse in two environments, and even with one, coordination overhead creates substantial gaps. For example, in the personal assistant environment, the coordinator fulfills a targeted user request about twice as often as teams. We identify distinct behaviors associated with this poor group-level performance, including stalling as teams grow, overriding each other's actions, and fabricating claims. We find effective but environment-specific mitigations, such as a team lead, explicit procedural instructions, and a platform check that makes an agent read its peers' messages before committing. We will release the API key, clinic, and personal assistant environments as MAMUBench, comprising 74 scenarios for evaluating multi-user, multi-agent coordination.

Sahan Paliskara, Nattaput Namchittai, Andrew Lampinen

Independent Researcher · Anthropic

Multi-Agent CoordinationMulti-Agent CommunicationArtificial Intelligence AssistantsComputational Cost
AskPDF