Runtime-Evolving Communication Topology Designer for LLM-Based Multi-Agent Collaboration

Large language model (LLM)-based multi-agent systems (MAS) have demonstrated remarkable collective intelligence, largely enabled by carefully designed inter-agent communication topologies. However, existing methods typically determine communication topologies before execution, preventing them from adapting information flow to runtime messages and evolving reasoning states. This can result in both redundant communication and missed task-critical interactions. To address this limitation, we propose RE-Designer, a Runtime-Evolving Communication Topology Designer that formulates topology construction as a sequential decision-making process and optimizes it through reinforcement learning (RL). Specifically, RE-Designer incrementally constructs a directed acyclic graph by dynamically adding agents and communication edges based on the partially constructed graph and the runtime messages generated by preceding agents. Since optimizing these sequential decisions with sparse task-level rewards is challenging, we introduce an information-bottleneck-inspired process reward that promotes task-relevant communication while penalizing redundant information propagation. To further reduce the exploration space, we develop a three-stage training strategy that first learns structural and message-aware priors through supervised learning and then refines runtime topology decisions through online RL. Extensive experiments on multiple reasoning benchmarks demonstrate that RE-Designer consistently achieves superior task performance, with favorable accuracy–communication trade-offs.