From Static to Dynamic: Towards Runtime Multi-Agent Topology Planning via Progressive Next Layer Generation

Large language model (LLM)-driven agents are designed to handle a wide range of tasks autonomously. As tasks become increasingly complex, the multi-agent system (MAS) becomes a promising solution, where the underlying communications are typically represented as a directed acyclic graph. To autonomously construct a desired MAS topology, various design strategies are proposed based on graph-informed techniques. However, these frameworks primarily follow the "design-then-deploy" paradigm. As a result, the generated graph-structure MAS cannot satisfy runtime requirements and adapt to the dynamic environment. To break the constraints of static designs, our key insight is that the dynamic planning of interaction topology for MAS is inherently an autoregressive next layer generation problem, where nodes are agents and connections are information dependencies. Building upon this motivation, we propose a Runtime Multi-Agent topology Planning scheme named RMAP. Specifically, to capture the evolving semantics of agents during runtime topology construction, RMAP progressively integrates three agentic semantics, including role descriptions, topological context, and execution outputs, into unified task-oriented representations. To enable layer-wise execution, RMAP decomposes topology prediction into two stages: first generating the leaf agents of the current layer, followed by supplementing optional connections between these leaf agents and their ancestor agents. Experimental results show that our scheme improves task performance in 92.8% of scenarios, and can be easily implemented on personal computers with less than 1 second of additional latency. The code is available at https://anonymous.4open.science/r/RMAP-1884.