HyperMAS: Evolving Collaboration Primitives for Scalable Multi-Agent LLM Collaboration

Multi-agent systems (MAS) powered by Large Language Models (LLMs) have demonstrated strong collaborative reasoning capabilities across complex tasks, yet their effectiveness often comes with substantial communication cost. Existing adaptive MAS methods can customize roles, models, and communication structures for each query, but they still rely on an implicit execution assumption: collaboration capability must be unfolded through explicit agent communication whenever a task is solved. As a result, even repeatedly validated coordination processes are re-executed from scratch, causing redundant token consumption and limiting long-term scalability. In this work, we propose \ourmethod, a hypergraph-centered framework that evolves collaborative skills for scalable multi-agent LLM systems. \ourmethod represents functional roles as role-level mixture nodes enhanced by heterogeneous LLMs and organizes multi-role coordination through high-order hyperedges. During training, \ourmethod explores explicit hypergraph collaboration, identifies reliable and cost-effective sub-hypergraphs from execution traces, and distills them into evolved collaborative skills. During inference, \ourmethod adaptively invokes compact skills for familiar routines and expands into explicit hypergraph communication for uncertain cases, balancing efficiency and flexibility. Extensive experiments on mathematical reasoning, code generation, and knowledge-intensive benchmarks show that \ourmethod is (1) effective, improving average accuracy by $3.1$ points over strong adaptive MAS baselines; (2) efficient, reducing token cost by $28.4\%$; and (3) scalable, decreasing active hyperedge communication by $36.7\%$ after skill accumulation.