Multi-Agent Coordination via Shared Memory Graphs
Nexus Research • NeurIPS 2026 Workshop on Agentic AI
Abstract
We extend persistent agent memory to multi-agent settings by introducing Shared Memory Graphs (SMG), a distributed graph structure enabling teams of autonomous agents to coordinate, delegate, and resolve conflicts without centralized orchestration. The graph encodes agent context as typed nodes, with directed edges for information flow, task dependencies, and delegation. Agents interact through four primitive operations (READ_NODE, WRITE_NODE, ADD_EDGE, RESOLVE_CONFLICT) integrated into normal memory operations. Evaluation on 1,200 multi-agent sessions shows 2.3x improvement in task completion, 67% reduction in redundant work, and 3.1x cross-agent knowledge transfer. Three emergent coordination behaviors are observed: automatic task decomposition, skill-based delegation, and consensus-based conflict resolution.
1. Introduction
The most effective engineering organizations operate as teams of specialists: backend engineers, frontend engineers, data engineers, SREs, and security engineers coordinate through shared artifacts, code reviews, design documents, and synchronous communication. This collective intelligence exceeds any individual's knowledge. Individual AI agents face fundamental limitations that teams inherently solve: bounded context windows (~128K tokens cannot hold a large codebase), limited skill diversity (one model architecture cannot excel at all tasks), single points of failure, and inability to parallelize.
Multi-agent systems have been explored in prior work (Wu et al., 2024; Park et al., 2023; Li et al., 2025), but most approaches fall into two camps. Orchestrated systems use a central controller that decomposes tasks, assigns subtasks, and manages communication —creating a single point of failure and limiting emergent coordination. Message-passing systems define explicit communication protocols between agents —requiring agents to know about each other and agree on message formats a priori. Both approaches constrain the flexible, emergent coordination that makes human teams effective.
We introduce Shared Memory Graphs (SMG), a third approach where coordination emerges as a side effect of shared memory access, not explicit communication. The key insight is that human teams coordinate most naturally when they share context —through a shared codebase, shared documentation, and shared history —rather than through explicit coordination meetings. SMG replicates this mechanism for agent teams.
2. Related Work
Orchestrated multi-agent frameworks. AutoGen (Wu et al., 2024) provides a conversational framework where agents pass structured messages through a central orchestrator. CrewAI enables role-based agent teams with predefined workflows and sequential task assignment. Both require explicit coordination protocols that scale poorly with team size and limit emergent behaviors. SMG replaces protocols with shared memory, reducing coordination overhead from 12% (in orchestrated systems) to 4.7%.
Shared memory and tuple spaces. The Linda coordination language (Carriero & Gelernter, 1989) introduced tuple-space coordination: agents read and write to a shared space without knowing about each other. JavaSpaces extended this to distributed systems. SMG builds on this paradigm but adds semantic indexing (agents retrieve context by meaning rather than exact match), typed edges (relationships carry semantic meaning), and autonomous conflict resolution (the graph resolves inconsistencies without a coordinator).
Knowledge graphs for AI. Enterprise knowledge graphs (Pan et al., 2023) organize facts as entities and relations. SMG extends knowledge graphs with dynamic evolution (nodes are created and deleted as agent contexts change), agent-specific attributes (task progress, confidence, provenance), and typed interaction semantics (delegation, dependency, conflict edges carry operational meaning for coordination).
Emergent coordination. Work on emergent communication (Lazaridou & Baroni, 2020) shows that agents can develop coordination protocols through interaction. SMG provides a structured environment where coordination emerges through graph operations rather than learned communication protocols, giving stronger guarantees about coordination semantics.
3. SMG Architecture
The SMG is formalized as a directed, attributed graph G = (V, E, A, τ) where V is a set of typed nodes, E a set of typed directed edges, A a function mapping nodes and edges to attribute vectors, and τ a type function mapping nodes and edges to their respective types.
\[G = (V, E, A, \tau), \quad V = V_{\text{task}} \cup V_{\text{knowledge}} \cup V_{\text{artifact}}\]Node types. Task nodes Vtask represent an agent's working context for a specific goal, containing the task description, current plan, execution progress, intermediate artifacts, and confidence estimates. Knowledge nodes Vknowledge represent standalone facts, rules, or patterns that agents have learned (e.g., "this project uses Result types for error handling"). Artifact nodes Vartifact represent shared outputs such as code files, documents, or design diagrams that multiple agents may reference. Each node carries an attribute vector including creation timestamp, last-access timestamp, creator agent, confidence score, and access count.
Edge types. Edges carry one of five semantic types:
\[E \subseteq V \times V \times \{\text{delegates, depends, informs, conflicts, agrees}\}\]Delegation edges (A → B: "agent A gave subtask to agent B"), dependency edges (Y → Z: "task Y requires output from task Z"), informed-by edges (agent → knowledge: "the agent used this knowledge"), conflict edges (knowledge → knowledge: "contradictory facts"), and consensus edges (agent → knowledge: "agent agrees after resolution").
Graph operations. Agents interact through four primitive operations. READ_NODE(v) retrieves node v and its 1-hop neighborhood with typed edges (average degree 4.7, p95 retrieval 28ms). WRITE_NODE(v, attrs) creates or updates a node with type and attributes. ADD_EDGE(u, v, type) creates a typed relationship. RESOLVE_CONFLICT(topic) triggers consensus-based resolution for conflicting knowledge on a given topic. Each operation is causally logged with a unique trace identifier linking it to the agent's reasoning chain.
Figure 1: Shared Memory Graph example with 4 agents, 1 knowledge node, 1 task node
3.1 Formal Properties of SMG
The SMG formalization as a directed attributed graph G = (V, E, A, tau) admits several important properties that distinguish it from unstructured shared memory.
Property 1: Causal consistency. For any two agents alpha and beta, if alpha executes WRITE_NODE(v) at time t_a and beta executes READ_NODE(v) at time t_b > t_a, then beta reads alpha's update (or a later update). This is enforced by the causally-logged trace: each write is assigned a unique Lamport timestamp, and reads return the latest write with timestamp <= read time. The causal log is a DAG over graph operations, enabling deterministic replay and audit.
Property 2: Partial order convergence. The graph G converges to a unique state for any set of operations that are not in conflict. Formal proof: two operations op1 and op2 commute if they operate on different nodes or if they are both READ_NODE operations. For conflicting writes to the same node, the last-writer-wins policy applies based on the causal timestamp. This ensures that all agents eventually observe a consistent graph state.
Property 3: Bounded staleness. The maximum time between a write by agent alpha and its visibility to agent beta is bounded by max(delta_p, delta_r) where delta_p is the publish latency (mean 40ms, p99 180ms) and delta_r is the retrieval latency (mean 12ms, p99 45ms). This bound enables agents to reason about information freshness: an agent reading a node can compute the maximum possible staleness of the data and adjust its confidence accordingly.
Figure 2: SMG operation latency distribution
4. Graph Operations in Detail
Each of the four primitive operations is designed around a specific coordination pattern that emerges from shared memory access rather than direct communication.
READ_NODE: Context-aware retrieval. When an agent executes READ_NODE(v), the graph returns v and its neighbors with their edge types. The agent can then decide whether to read neighbor nodes based on their types and attributes. This enables serendipitous coordination: an agent working on task T may discover that another agent has already addressed a subproblem, without any explicit notification. In our deployments, 23% of coordination events begin with a serendipitous READ_NODE discovery.
WRITE_NODE: Context broadcasting. When an agent writes to a node, the update is visible to all agents that subsequently read the node or its neighbors. This is analogous to updating a shared document: the author does not need to notify readers; readers discover the update when they next access the document. WRITE_NODE carries an attribute merge strategy parameter controlling whether the write overwrites, appends, or merges with existing content.
ADD_EDGE: Relationship declaration. Adding an edge is the SMG equivalent of "I have a relationship with this context." Delegation edges signal task handoff; dependency edges signal blocking relationships; informed-by edges signal knowledge provenance. The edge type encodes the coordination semantics, enabling other agents to reason about the graph structure without needing to interpret node content.
RESOLVE_CONFLICT: Consensus mechanism. When two knowledge nodes with overlapping scope have contradictory content, any agent can trigger the RESOLVE_CONFLICT operation. The graph broadcasts the conflict to all agents that have accessed either node and collects supporting evidence. Resolution occurs when >66% of responding agents connect to a single consensus node via a "consensus" edge. If no consensus is reached within 4 hours, the conflict is escalated to a human administrator.
5. Emergent Coordination Behaviors
We analyzed 2,847 coordination events across all three evaluation scenarios and identified three recurring behavioral patterns that emerged from the graph structure without explicit programming.
Automatic Task Decomposition. When an agent creates a task node with a complex goal, other agents that subsequently READ_NODE on the task may autonomously create subtask nodes connected via delegation edges to the parent. This produces hierarchical decomposition without any agent being designated as the decomposer. In 47% of complex tasks (>5 steps), at least one autonomous sub-delegation occurred. The median depth of autonomous decomposition is 2.3 levels. This behavior emerges because agents naturally want to make progress on visible work items —the graph makes task structure visible, and agents self-select the work they are best suited for.
Skill-Based Delegation. Agents develop specialized capabilities over time (e.g., deep knowledge of a specific framework). The graph learns a distributed skill directory: agents that successfully complete tasks in domain D attract delegation edges from agents working on related tasks. After a median of 12 sessions, agents working on related tasks are 3.4x more likely to receive delegation edges in their domain of expertise. This happens without any agent explicitly advertising its skills —the graph structure encodes capability implicitly through delegation edge patterns.
Consensus-Based Conflict Resolution. When two agents create knowledge nodes with contradictory content about the same topic (e.g., different interpretations of an API specification), a conflict edge is created between the nodes. Other agents that encounter the conflict may contribute supporting evidence via informed-by edges toward one side. Resolution occurs when a supermajority (>66%) of agents that have engaged with the conflict connect to a single consensus node. In our evaluation, 41% of sessions saw at least one conflict resolution event. Median resolution time: 47 minutes. Resolution accuracy (verified by human review of 500 resolved conflicts): 91%.
Table 1: Emergent behavior prevalence
| Behavior | Code Eng. | Review | Debugging | Overall |
|---|---|---|---|---|
| Task decomposition | 52% | 31% | 58% | 47% |
| Skill delegation | 41% | 28% | 63% | 44% |
| Conflict resolution | 23% | 47% | 52% | 41% |
| Any coordination | 74% | 68% | 89% | 77% |
6. Evaluation
We evaluate SMG on 1,200 multi-agent sessions across three scenarios. Collaborative Code Engineering: teams of 3-5 agents implementing a feature across multiple files in a TypeScript monorepo (8,000+ files, 500+ modules). Parallel Code Review: teams of 3 agents reviewing the same pull request for different concern types (correctness, style, security). Distributed Debugging: teams of 4 agents debugging a microservice system failure with access to different log sources and service metrics.
6.1 Comparison with Alternative Multi-Agent Frameworks
We compare SMG against three alternative coordination approaches on 200 matched tasks across all three evaluation scenarios. AutoGen (Wu et al., 2024): conversation-based orchestration with a central coordinator. CrewAI: role-based agents with predefined sequential workflows. Message-passing baseline: agents communicate via direct messages with a shared message bus.
Table 2: Framework comparison on 200 matched tasks
| Metric | AutoGen | CrewAI | Msg-pass | SMG |
|---|---|---|---|---|
| Task completion | 51.3% | 47.8% | 44.2% | 73.1% |
| Coordination overhead | 12.1% | 14.8% | 18.3% | 4.7% |
| Redundant work | 31% | 28% | 41% | 10.2% |
| Cross-agent transfer | 1.2x | 1.4x | 1.1x | 3.1x |
| Emergent behaviors | Limited | None observed | None observed | 3 types |
| Setup time | 45 min | 30 min | 60 min | 10 min |
SMG achieves the highest task completion (73.1% vs 51.3% for AutoGen) with the lowest coordination overhead (4.7% vs 12.1%). The improvement is particularly pronounced in the debugging scenario (89% vs 58%), where shared context across agents is most valuable. The comparison also reveals that coordination overhead in message-passing systems grows super-linearly with team size (O(n^2) vs O(n log n) for SMG), making SMG increasingly attractive as team size grows beyond 4 agents.
We also measured the cost of coordination. SMG operations account for 4.7% of total agent actions (READ_NODE: 2.8%, WRITE_NODE: 1.1%, ADD_EDGE: 0.5%, RESOLVE_CONFLICT: 0.3%). This is well below the 12% overhead of explicit orchestration (measured by comparing SMG against an AutoGen-based system on 200 matched tasks). 89% of human evaluators reported that SMG-equipped agents showed "noticeable coordination improvement" within 3 sessions. The primary failure mode (8% of sessions) is unresolved conflict deadlock, where two agents hold contradictory positions and neither can provide sufficient evidence to sway the consensus.
7. Scaling and Performance
We evaluate SMG scaling by measuring coordination overhead and task completion rate as a function of graph size. Overhead scales sub-linearly: 4.7% at 10 agents, 6.2% at 30 agents, 8.1% at 50 agents. Beyond 50 agents, we observe super-linear scaling due to increased conflict rate and longer resolution times. The conflict rate follows a quadratic trend: 0.3% per session at 10 agents, 1.8% at 30 agents, 4.2% at 50 agents. For deployments exceeding 50 agents, we recommend graph partitioning by domain or team.
Memory requirements per agent average 12 MB for the local graph cache and 4 MB for the shared graph index. Total storage for a 50-agent graph with 30-day retention averages 3.2 GB. Retrieval latency remains under 50ms p95 up to 100K nodes (tested via stress simulation).
8. Discussion and Limitations
Emergence vs. control. The power of SMG is that coordination emerges without explicit protocols. The risk is that emergent behaviors may be unpredictable or suboptimal. We observed one case where agents autonomously decomposed a task into 47 subtasks (the optimal was 12), creating unnecessary overhead. Addressing this requires lightweight coordination cost awareness: agents should consider whether the benefit of delegation exceeds the overhead of graph operations.
Security. In the current SMG implementation, any agent can read any node and add edges to any other node. Malicious agents could inject false information or create spurious delegation edges. We are extending capability-based access control to SMG nodes at the per-agent-type level.
Generalization. Our evaluation spans software engineering tasks. Generalization to other domains (scientific research, business operations, creative work) requires validation on domain-specific multi-agent workflows.
8.1 Graph Dynamics and Convergence
An important consideration for production deployment is how SMG behaves over extended operation. We analyze graph dynamics over a 6-month deployment with 15 agents across 3 teams.
Graph growth. The graph grows at an average rate of 47 nodes/day and 82 edges/day. After 6 months: 8,460 nodes and 14,760 edges. Growth is not uniform: knowledge nodes grow rapidly in the first month (32/day), then plateau at 8/day as agents converge on a shared understanding. Task nodes follow the project cycle: spikes during active development, plateaus during maintenance.
Edge type distribution. After 6 months: informed-by edges (41%) dominate, reflecting agents building on each other'''s knowledge. Dependency edges (28%) reflect task structure. Delegation edges (17%) reflect work distribution. Conflict edges (8%) reflect knowledge disagreements. Consensus edges (6%) reflect resolved conflicts. The conflict-to-consensus ratio of 1.33 suggests that most conflicts are eventually resolved.
Convergence analysis. We measure convergence as the rate at which new nodes replicate existing knowledge (a sign that the graph has converged to a stable representation). After 90 days, the duplication rate drops below 5%, indicating that the agent team has developed a shared vocabulary and knowledge base. Between days 90-180, most growth is genuinely new knowledge rather than re-learning. This convergence timeline matches the optimal 90-day retention window we recommend for production deployments.
9. Conclusion
Shared Memory Graphs enable effective multi-agent coordination with emergent behaviors arising from graph structure. Deployed as the default coordination mechanism for multi-agent Nexus deployments.
References
[1] Wu, Q., et al. (2024). AutoGen. arXiv:2308.08155.
[2] Park, J. S., et al. (2023). Generative Agents. arXiv:2304.03442.
[3] Carriero, N. & Gelernter, D. (1989). Linda in Context. CACM.
[4] Chen, K., et al. (2026). Persistent Memory. Nexus Research.
[5] Nexus Research. (2026). Nexus-1 Technical Report.
[6] Wang, L., et al. (2026). TAR. ICML 2026.
[7] Yao, S., et al. (2023). ReAct. ICLR 2023.
[8] CrewAI. (2025). Multi-Agent Orchestration.
[9] Li, G., et al. (2025). Distributed Knowledge Graphs. arXiv:2502.12345.
[10] Lazaridou, A. & Baroni, M. (2020). Emergent Multi-Agent Communication in the Deep Learning Era. arXiv:2006.02419.
[11] Sukhbaatar, S., et al. (2016). Learning Multiagent Communication with Backpropagation. NeurIPS 2016.
[12] Das, A., et al. (2019). TarMAC: Targeted Multi-Agent Communication. ICML 2019.
[13] Foerster, J., et al. (2016). Learning to Communicate with Deep Multi-Agent Reinforcement Learning. NeurIPS 2016.
[14] Vinyals, O., et al. (2019). Grandmaster Level in StarCraft II using Multi-Agent RL. Nature.