CoEvo-MAS: Co-Evolving Skills and Agent Organizations in Multi-Agent Systems

Large language model (LLM)-based multi-agent systems (MASs) often rely on fixed organizations designed before deployment. As tasks change, these organizations may fail to cover new capability requirements. Skill learning methods can extract reusable knowledge from agent experience, but they typically leave the underlying organization unchanged. Automated organization design methods can adjust agent roles or compositions, yet they often rely on short-term signals such as the current task, isolated failures or raw interaction trajectories. In this paper, we propose CoEvo-MAS, a framework that co-evolves skills and multi-agent organizations in a closed loop. From task execution, CoEvo-MAS distills reusable skills and tracks their utility, usage frequency and compatibility with agents. The resulting empirical skill distribution is summarized as a skill profile that reflects recurring capability needs. At regular intervals, a meta agent uses this profile to identify organization-level issues and propose changes to skill assignments, agent roles or agent composition. Each candidate organization is validated on held-out tasks and deployed only if it improves over the current one. CoEvo-MAS is evaluated on ALFWorld and ${\tau }^2$-bench, where it outperforms the compared methods. Ablation studies further confirm the contribution of skill evolution, skill-profile-guided organization adaptation, and validation-gated updates.