Verified Concurrency Anomaly Detection for Multi-Agent LLM Systems

Researchers have addressed critical concurrency challenges in multi-agent Large Language Model (LLM) systems, which often share state through various mechanisms like memory stores and tool registries. They propose a formal model for these systems, treating shared state operations as long-running read-generate-write processes under deterministic-generation semantics. The work identifies and formalizes four specific concurrency anomalies: stale-generation, phantom-tool, causal-cascade, and tool-effect reordering, drawing parallels to classical isolation anomalies. A significant contribution is the development of a machine-checked consistency hierarchy, verified using 274 Verus obligations, which ensures the sound and complete detection of these anomalies. The study demonstrates the practical application of these findings by verifying three deployed Rust runtimes against specific anomaly levels and showing how to prevent higher-level anomalies. It also successfully reproduces and fixes a silent lost update in ByteDance's deer-flow and addresses tool-effect reordering in LangGraph's ToolNode, highlighting the real-world impact of these verified solutions.