Don't Just Optimize Prompts: Evolving Agent Communication Protocols with EvoProtocol

Multi-agent systems (MAS) tackle complex tasks by coordinating role-specialized agents with focused context. By iteratively optimizing and evolving their components from execution feedback, these systems can improve their performance and efficiency over time. However, prior work mainly focuses on optimizing agent prompts or coordination workflows, while the inter-agent communication protocol, a fundamental component that determines what agents communicate and how they exchange information, remains largely underexplored. To address this limitation, we propose EvoProtocol, a framework that exposes the communication protocol as an explicit optimization variable and evolves it jointly with agent prompts. On MAS-PromptBench, jointly evolving prompts and protocols outperforms prompt optimization under every fixed protocol on all five tasks, even when compared against the best-performing fixed protocol for each task. On BrowseComp-Plus with a dynamic planner–executor workflow, EvoProtocol improves accuracy by $5.5$–$16$ points over prompt optimization with fixed protocols, and its cost-aware variant achieves higher accuracy at lower cost than prompt optimization with the hand-designed PACT protocol. These results show that co-evolving communication protocols with agent prompts yields better combinations of prompts and protocols than prompt optimization under fixed protocols.