用缓存协议思想降低多智能体大模型的同步开销
Token Coherence: Adapting MESI Cache Protocols to Minimize Synchronization Overhead in Multi-Agent LLM Systems
- 借鉴MESI缓存协议，用延迟失效机制减少状态广播
- 实测同步开销降低84%~95%，优于理论最低保障
- 适用于需要高效协作的大模型系统，如LangGraph等
多智能体大模型编排在简单广播模式下会产生随智能体数n、步骤数S和数据体量|D|呈三重乘积增长的同步开销（O(n×S×|D|)），我称之为广播引发的三重乘法开销。该问题本质源于全状态重传，而非多智能体协调的固有缺陷。核心观点：多智能体系统的同步开销可精确映射为共享内存多处理器中的缓存一致性问题，经微小结构调整后，MESI协议的失效机制可应用于智能体间数据项同步。本文构建了对象一致性系统（ACS），并证明了「令牌一致性定理」：当S > n + W(d_i)时，懒惰失效可将开销至少降低至S/(n + W(d_i))，使总复杂度从O(n×S×|D|)降至O((n + W)×|D|)。通过TLA+验证的协议，在约2,400个状态中保证单写安全、单调版本和有界过期。四种工作负载模拟显示：在V=0.05时节省95.0%±1.3%，V=0.10时92.3%±1.4%，V=0.25时88.3%±1.5%，V=0.50时84.2%±1.3%，均超过理论保守下限；甚至在V=0.9时仍保持约81%的节省，与预期崩溃阈值相悖。贡献包括：(1) 从缓存协议到对象状态的正式映射；(2) 令牌一致性定理作为性能下限；(3) TLA+验证的协议及三项形式化不变量；(4) 条件性对象访问语义的刻画，回应“总是读”质疑；(5) 提供与LangGraph、CrewAI、AutoGen集成的轻量级适配器参考实现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。