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

• URL: http://arxiv.org/abs/2603.15183v1
• Date: Mon, 16 Mar 2026 12:20:06 GMT
• Title: Token Coherence: Adapting MESI Cache Protocols to Minimize Synchronization Overhead in Multi-Agent LLM Systems
• Abstract summary: Multi-agent LLM orchestration incurs synchronization costs scaling as O(n x S x |D|) in agents, steps, and artifact size under naive broadcast.<n>I argue this pathology is a structural residue of full-state rebroadcast, not an inherent property of multi-agent coordination.<n>I construct the Artifact Coherence System (ACS) and prove the Token Coherence Theorem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Omni2LoRA: Coherence-Preserving Parametric Memory for Efficient Omni Language Models [65.49950267695267]
  We introduce Omni2LoRA, a framework for efficient parametric memory compression via coherence-preserving context distillation.<n>By converting multimodal memory into a fixed-budget, reusable parameter state, our method drives answer-time multimodal-token load to zero.
  arXiv  Detail & Related papers  (2026-08-10T07:49:10Z)
• Cross-Layer Error Compensation and Finite-Sample Feature-Statistics Matching for Extreme Low-Bit Quantization of Large Language Models [0.0]
  We formulate quantization as a joint optimization over the discrete codes and scales of all layers.<n>We show that error compensation alone reaches a perplexity ratio of 9.56 +/- 0.15 over the FP16 teacher.<n>On Qwen2.5-1.5B with 1.125-bit group-binary weights, error compensation alone reaches a perplexity ratio of 9.56 +/- 0.15 over the FP16 teacher.
  arXiv  Detail & Related papers  (2026-07-16T06:47:52Z)
• Verified Detection and Prevention of Concurrency Anomalies in Multi-Agent Large Language Model Systems [0.0]
  Multi-agent LLM systems state through memory stores, vector indices, and tool registries.<n>We model such sharing as long-running read-generate-write operations under deterministic-generation semantics.<n>We formalize four anomalies in TLA+: stale-generation, phantom-tool, causal-cascade, and tool-effect reordering.
  arXiv  Detail & Related papers  (2026-06-15T18:19:34Z)
• Tensor-Coord: Algebraic Decomposition of Joint Plan Tensors for Conflict-Free Multi-Agent LLM Planning [0.0]
  Large language models (LLMs) remain limited in multi-agent planning because independently generated plans can create coordination failures.<n>We introduce 3.9-Coord, a multilinear algebra framework that represents the joint plan of N agents as a third-order tensor (T in RN times H times A) over agents, timesteps, and actions.
  arXiv  Detail & Related papers  (2026-06-15T09:44:26Z)
• Scaling Parallel Sequence Models to Foundation-Scale Vision Encoders [123.58723804218151]
  Vision foundation models are bottlenecked by the quadratic cost of self-attention.<n>We present C-GSPN based on 2D spatial propagation propagation.
  arXiv  Detail & Related papers  (2026-05-30T14:29:43Z)
• Convergence Theory for Iterative LLM-Based Neural Architecture Search: A Parametric Cross-Entropy Framework with Closed-Form Proxy Reliability [48.83701310501069]
  Large language models (LLMs) are increasingly used as generators in iterative neural architecture search (NAS)<n>We model iterative LLM-NAS as a parametric Cross-Entropy (CE) method over executable programs.<n>We prove six results: (1) iterative LLM fine-tuning on elite architectures is equivalent to the CE update restricted to the LLM family; (2) expected architecture quality is monotonically non-decreasing across cycles; and (3) elite-set probability converges to a fixed point at a geometric rate.
  arXiv  Detail & Related papers  (2026-05-28T15:45:19Z)
• Collapse or Preserve: Data-Dependent Temporal Aggregation for Spiking Neural Network Acceleration [1.1597621848542221]
  Spike sparsity is widely believed to enable efficient spiking neural network (SNN) inference on GPU hardware.<n>We demonstrate this is an illusion: SIMD architectures cannot exploit the fine-grained, unstructured sparsity of i.i.d. binary spikes.<n>We propose Temporal Aggregated Convolution (TAC), which exploits convolution linearity to pre-aggregate $K$ spike frames before a single convolution call.
  arXiv  Detail & Related papers  (2026-03-14T07:30:22Z)
• Cost-Efficient Multimodal LLM Inference via Cross-Tier GPU Heterogeneity [0.0]
  Multimodal large language model (MLLM) inference splits into two phases with opposing hardware demands.<n>We show that under standard transformer KV caching, the modality boundary minimizes cross-device transfer.<n>We build HeteroServe, a phase-aware runtime with modality-level partitioning and cross-tier scheduling.
  arXiv  Detail & Related papers  (2026-03-13T06:42:35Z)
• The Bureaucracy of Speed: Structural Equivalence Between Memory Consistency Models and Multi-Agent Authorization Revocation [0.0]
  We develop a Capability Coherence System for Identity and Access Management.<n>A safety theorem bounds unauthorized operations for the execution-count Release Consistency-directed Coherence strategy.<n> Tick-based discrete event simulation confirms per-capability safety guarantee.
  arXiv  Detail & Related papers  (2026-03-10T16:37:02Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• Hierarchical Federated Graph Attention Networks for Scalable and Resilient UAV Collision Avoidance [0.5505634045241287]
  Real-time performance, adversarial resiliency, and privacy preservation are the most important metrics that need to be balanced to practice collision avoidance.<n>We have proposed an adaptive differential privacy mechanism, wherein the noise level $(in [0.1, 1.0])$ is dynamically reduced based on an evaluation of the measured real-time threat.<n>This architecture provides a scalable scenario of 500 UAVs with a collision rate of $ 2.0%$ and the Byzantine fault tolerance of $f n/3$.
  arXiv  Detail & Related papers  (2025-11-05T12:01:00Z)
• Constructive Lyapunov Functions via Topology-Preserving Neural Networks [0.0]
  ONN achieves order-optimal performance on convergence rate, edge efficiency, and computational complexity.<n> Empirical validation on 3M-node semantic networks demonstrates 99.75% improvement over baseline methods.<n>ORTSF integration into transformers achieves 14.7% perplexity reduction and 2.3 faster convergence.
  arXiv  Detail & Related papers  (2025-10-10T17:46:52Z)
• SIM-CoT: Supervised Implicit Chain-of-Thought [108.30049193668083]
  Implicit Chain-of-Thought (CoT) methods offer a token-efficient alternative to explicit CoT reasoning in Large Language Models.<n>We identify a core latent instability issue when scaling the computational budget of implicit CoT.<n>We propose SIM-CoT, a plug-and-play training module that introduces step-level supervision to stabilize and enrich the latent reasoning space.
  arXiv  Detail & Related papers  (2025-09-24T17:01:32Z)
• Tensor Decomposition Networks for Fast Machine Learning Interatomic Potential Computations [48.46721044282335]
  tensor decomposition networks (TDNs) achieve competitive performance with dramatic speedup in computations.<n>We evaluate TDNs on PubChemQCR, a newly curated molecular relaxation dataset containing 105 million DFT-calculated snapshots.<n>Results show that TDNs achieve competitive performance with dramatic speedup in computations.
  arXiv  Detail & Related papers  (2025-07-01T18:46:27Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear Speedup [56.27526702716774]
  This paper revisits the A3C algorithm with TD(0) for the critic update, termed A3C-TD(0), with provable convergence guarantees. Under i.i.d. sampling, A3C-TD(0) obtains sample complexity of $mathcalO(epsilon-2.5/N)$ per worker to achieve $epsilon$ accuracy, where $N$ is the number of workers. Compared to the best-known sample complexity of $mathcalO(epsilon-2.5/N)$ for two
  arXiv  Detail & Related papers  (2020-12-31T09:07:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.