ProtoGuard: Safe and Token-Efficient LLM Agent Interaction through Formal Protocols

LLM agent teams are commonly coordinated through workflow graphs, yet structural and input/output type checks do not ensure interaction safety: agents may deadlock, fail to propagate decisions, or act prematurely. Even with a sound interaction plan, runtime deviations remain possible for LLM agents. We introduce ProtoGuard, a framework that specifies multi-agent interactions as formal protocols and connects static validation with runtime governance. Building on multiparty session types (MPST), a formalism for modelling interactions with rigorous guarantees of communication safety and progress, ProtoGuard uses an LLM to draft a global protocol, checks and refines it for formal validity under MPST, and derives a role-specific contract for each agent. The resulting contracts provide protocol-governed execution through agent prompts, deterministic monitoring, pre-delivery gating, and protocol-aware scheduling. Runtime enforcement keeps agent interaction within the validated protocol, preserving its guarantees by construction without constraining task-specific agent decisions. We evaluate protocol-governed execution on diverse multi-agent benchmarks and LLMs. Across the evaluated benchmark–model settings, macro-averaged goal-completion rate increases from 4.1% under the skills-only baseline (role-specific instructions without protocol support) to 98.9% under the full configuration, while runtime enforcement eliminates delivered protocol violations. Mean execution time decreases from 249.6s to 47.6s, and runtime token cost per trial run falls by 91.5%. These results demonstrate that validated and enforced interaction protocols can improve the correctness, safety, and efficiency of LLM-agent coordination, suggesting formal specifications as a principled execution layer for stochastic LLM agents.