Token Coherence: Adapting MESI Cache Protocols to Minimize Synchronization Overhead in Multi-Agent LLM Systems

Vladyslav Parakhin

cs.DCMar 16, 2026

Token Coherence: Adapting MESI Cache Protocols to Minimize Synchronization Overhead in Multi-Agent LLM Systems

Authors: Vladyslav Parakhin

Organizations: Independent Researcher

Abstract

Multi-agent LLM orchestration incurs synchronization costs scaling as O(n x S x |D|) in agents, steps, and artifact size under naive broadcast -- a regime I term broadcast-induced triply-multiplicative overhead. I argue this pathology is a structural residue of full-state rebroadcast, not an inherent property of multi-agent coordination. The central claim: synchronization cost explosion in LLM multi-agent systems maps with formal precision onto the cache coherence problem in shared-memory multiprocessors, and MESI-protocol invalidation transfers to artifact synchronization under minimal structural modification. I construct the Artifact Coherence System (ACS) and prove the Token Coherence Theorem: lazy invalidation attenuates cost by at least S/(n + W(d_i)) when S > n + W(d_i), converting O(n x S x |D|) to O((n + W) x |D|). A TLA+-verified protocol enforces single-writer safety, monotonic versioning, and bounded staleness across ~2,400 explored states. Simulation across four workload configurations yields token savings of 95.0% +/- 1.3% at V=0.05, 92.3% +/- 1.4% at V=0.10, 88.3% +/- 1.5% at V=0.25, and 84.2% +/- 1.3% at V=0.50 -- each exceeding the theorem's conservative lower bounds. Savings of ~81% persist at V=0.9, contrary to the predicted collapse threshold. Contributions: (1) formal MESI-to-artifact state mapping; (2) Token Coherence Theorem as savings lower bound; (3) TLA+-verified protocol with three proven invariants; (4) characterization of conditional artifact access semantics resolving the always-read objection; (5) reference Python implementation integrating with LangGraph, CrewAI, and AutoGen via thin adapter layers.

Figures & tables

CPU Memory Hierarchy	Agent Memory Hierarchy	Coherence Mechanism
L1/L2 cache (per-core)	Agent artifact cache (per-agent runtime)	MESI state per agent–artifact pair
Shared LLC / main memory	Shared artifact store (authority service)	Canonical version + invalidation events
Memory bus / coherence fabric	Event bus (Redis / Kafka / NATS)	Invalidation and version-update messages
Disk / persistent storage	Long-term persistence (vector DB, file store)	Out of scope for CCS v0.1

Table 1

Hardware State	Artifact State	Semantic Interpretation
Modified ( $M$ )	Modified ( $M$ )	Agent holds the only valid copy; authority copy is stale; other agents are invalidated
Exclusive ( $E$ )	Exclusive ( $E$ )	Agent holds the only copy, identical to authority; write permitted without broadcast
Shared ( $S$ )	Shared ( $S$ )	Multiple agents hold valid copies; no agent has written since last commit
Invalid ( $I$ )	Invalid ( $I$ )	Agent’s cached copy is stale; full fetch required before next use

Table 2

Scenario	$V(d_{i})$	$T_{\text{broadcast}}$ ( $\pm\sigma$ )	$T_{\text{coherent}}$ ( $\pm\sigma$ )	Savings	CRR	CHR
A: Planning	0.05	$1{,}979.6\pm 3.2$	$98.1\pm 25.0$	$95.0\%\pm 1.3\%$	0.050	$79.4\%\pm 5.2\%$
B: Analysis	0.10	$1{,}979.6\pm 3.2$	$152.3\pm 28.5$	$92.3\%\pm 1.4\%$	0.077	$66.8\%\pm 6.0\%$
C: Development	0.25	$1{,}979.6\pm 3.2$	$231.2\pm 29.1$	$88.3\%\pm 1.5\%$	0.117	$51.1\%\pm 7.0\%$
D: High Churn	0.50	$1{,}979.2\pm 3.1$	$312.1\pm 25.6$	$84.2\%\pm 1.3\%$	0.158	$34.6\%\pm 7.0\%$

Table 3

Strategy	$T_{\text{sync}}$ ( $\pm\sigma$ )	Savings	Notes
Broadcast baseline	$1{,}979.6\pm 3.2$	—	Full rebroadcast every step
Eager invalidation	$132.7\pm 24.3$	$93.3\%\pm 1.2\%$	Lower fetch overhead; higher invalidation traffic
Lazy invalidation	$152.3\pm 28.5$	$92.3\%\pm 1.4\%$	Recommended default
TTL (lease = 10 steps)	$589.8\pm 0$	$70.2\%\pm 0\%$	Decoupled from write frequency
Access-count ( $k=8$ )	$155.2\pm 25.3$	$92.2\%\pm 1.3\%$	Near-equivalent to lazy at this $V$

Table 4

$V(d_{i})$	Formula Lower Bound	Observed Savings (10 runs)
0.01	89.0%	$97.1\%\pm 0.4\%$
0.05	85.0%	$95.0\%\pm 1.3\%$
0.10	80.0%	$92.4\%\pm 1.5\%$
0.25	65.0%	$88.3\%\pm 1.4\%$
0.50	40.0%	$84.3\%\pm 1.0\%$
0.75	15.0%	$82.2\%\pm 1.1\%$

Table 5

Agent Count $n$	$T_{\text{broadcast}}$	$T_{\text{coherent}}$ ( $\pm\sigma$ )	Savings	Formula LB
2	$989.2$ K	$44.3\pm 8.2$ K	95.5%	85.0%
4	$1{,}979.6$ K	$152.3\pm 28.5$ K	92.3%	80.0%
8	$3{,}956.7$ K	$468.6\pm 39.1$ K	88.2%	70.0%
16	$7{,}911.0$ K	$1{,}255.2\pm 65.0$ K	84.1%	50.0%

Table 6

$\|d_{i}\|$ (tokens)	$T_{\text{broadcast}}$	$T_{\text{coherent}}$ (lazy)	Savings	Absolute savings
4,096	$1{,}979.6$ K	$98.1$ K	95.0%	$1{,}881.5$ K tokens
8,192	$2{,}636.2$ K	$132.9$ K	95.0%	$2{,}503.3$ K tokens
32,768	$6{,}575.7$ K	$341.8$ K	94.8%	$6{,}234.0$ K tokens
65,536	$11{,}828.4$ K	$620.3$ K	94.8%	$11{,}208.1$ K tokens

Table 7

$S$ (steps)	$T_{\text{broadcast}}$	$T_{\text{coherent}}$ (sim)	Savings (sim)	Formula LB
5	$259.3$ K	$36.9$ K	85.8%	0% (bound<0)
10	$505.0$ K	$49.2$ K	90.3%	40.0%
20	$996.6$ K	$68.9$ K	93.1%	70.0%
40	$1{,}979.6$ K	$98.1$ K	95.0%	85.0%
50	$2{,}471.1$ K	$111.2$ K	95.5%	88.0%
100	$4{,}928.7$ K	$188.4$ K	96.2%	94.0%

Table 8

Strategy	sync_tokens	Cache Hit Rate
Eager	16,798	97.7%
Lazy	341,036	41.0%

Table 9

Multi-Agent LLM Systems

Multi-agent large language model systems coordinate multiple AI agents to solve tasks through communication, specialization, shared tools, and memory.

See all 1,039 papers

CoAgent: Concurrency Control for Multi-Agent Systems
Jun 13, 2026Hongtao Lyu, Dingyan Zhang, Mingyu Wu +2Multi-Agent LLM Systems Multi-Agent Coordination
Shanghai Jiao Tong University China
Token-Efficient Multi-Agent Collaboration via System One-Guided Computational Division of Labor
Oct 6, 2026Zihan Zhou, Xinzhe Hu, Hanxu Yang +2Multi-Agent LLM Systems Multi-Agent System Optimization
University of Electronic Science and Technology of China · Southwestern University of Finance and Economics
Mesh Memory Protocol: Semantic Infrastructure for Multi-Agent LLM Systems
Apr 21, 2026Hongwei XuLLM Agent Memory Multi-Agent Communication

Jun 13, 2026J/K move · Enter open · S save

CoAgent: Concurrency Control for Multi-Agent Systems

Hongtao Lyu, Dingyan Zhang, Mingyu Wu, Xingda Wei+1

Shanghai Jiao Tong University China

Multi-Agent LLM Systems Multi-Agent Coordination Multi-Agent Systems

Open paper AskPDF arXiv

Multi-agent LLM systems -- coding agents, devops agents, document agents -- now routinely run several agents in parallel against the same git tree, Kubernetes cluster, or document. As soon as two of them mutate shared state, they enter the regime classical concurrency control has studied for decades, but classical mechanisms fit LLM agents poorly. A single agent transaction spans minutes of inference, read sets are broad and opaque rather than statically inferable, and the live state agents act on admits neither fork nor buffer, so writes take effect the moment they execute. Locks block long inference intervals; OCC abort-and-retry discards minutes of work on every conflict. This paper builds concurrency control on a capability classical transactions lack: the LLM inside each agent can judge whether a conflicting write invalidates its plan, and can repair exactly the operations that depended on it. Control therefore turns advisory: the runtime informs, the agent repairs. Our protocol, MTPO (Monotonic Trajectory Pre-Order), fixes a serialization order at launch, serves each read the order-filtered value, and applies writes speculatively in place; a one-way notification asks an affected reader to re-judge and patch its plan, while the framework mechanically undoes and reorders misplaced writes through the saga-style inverse each tool registers in advance. At quiescence the run is serializable in the pre-decided order. We realize MTPO as CoAgent, toolcall middleware whose privileged ToolSmith grows footprint-declared, undoable tools online. On ten contended workloads, CoAgent stays within 5% of serial correctness at a

1.4\times

speedup and near-serial token cost, where 2PL and OCC surrender nearly all concurrency gains; on a bash-only target system, it grows a 25-tool library online and lifts the task pass rate from 45/71 to 63/71 at

0.80\times

the time and

0.86\times

the cost.

Abstract

Multi-Agent LLM Systems

Explore similar work

CoAgent: Concurrency Control for Multi-Agent Systems

Token-Efficient Multi-Agent Collaboration via System One-Guided Computational Division of Labor

Mesh Memory Protocol: Semantic Infrastructure for Multi-Agent LLM Systems