Learn to Collaborate: Autoregressive Diversity-Aware Graph Generation for Multi-Agent Systems

Large Language Model (LLM)-based multi-agent systems have demonstrated strong capabilities on complex reasoning and decision-making tasks. However, existing approaches typically suffer from temporal-agnostic node selection, homogeneous interaction patterns, or topology-agnostic LLM routing, which may compromise collaborative performance while increasing computational costs. In this work, we propose GraphMAC, an autoregressive diversity-aware graph generation method for multi-agent systems. GraphMAC formulates multi-agent collaboration consisting of three stages: temporal-aware node selection, diverse edge construction, and graph-aware LLM allocation. Specifically, we first recruit agents autoregressively using a GRU-based historical aggregation mechanism that captures temporal dependencies during role selection. We then construct heterogeneous interaction graphs with multiple self-loop and cross-node edge types, enabling diverse collaborative interaction patterns. Finally, we employ relational graph convolutional networks to perform topology-aware message passing and dynamically allocate heterogeneous LLM backbones from a graph-level perspective. To jointly optimize task performance, interaction diversity, and computational cost, we further introduce a reinforcement learning objective with structural diversity entropy. Extensive experiments on multiple datasets demonstrate that GraphMAC consistently outperforms existing methods, achieving up to 5.8% performance improvement while maintaining superior cost-performance trade-offs.