SIGMA: Skill-Incidence Graphs for Compositional Multi-Agent Design
For multi-agent system designers, SIGMA provides a novel compositional approach that complements existing topology optimization, enabling better generalization to novel tasks.
SIGMA introduces a skill-incidence graph framework for multi-agent systems that constructs agents as task-conditioned bundles of reusable skills, enabling generalization to unseen capability combinations. Across six benchmarks with three LLMs, it outperforms the strongest baseline CARD by 2.06, 2.36, and 1.75 points respectively, and shows robust performance with only 0.96 points drop on unseen skill libraries.
Existing graph-based multi-agent system (MAS) designers mainly improve collaboration by optimizing communication topologies over predefined agents, roles, or groups. However, because each node remains a closed-set entity, these methods struggle to generalize to tasks that require unseen combinations of capabilities. We propose SIGMA, a skill-incidence graph framework that constructs agents as task-conditioned bundles of reusable skills. Given a task and a skill library, SIGMA predicts a skill-agent incidence matrix, composes agent node embeddings from selected skills, and decodes a communication topology over the constructed agents. During execution, skill-specific mailboxes route messages to the relevant assigned capabilities, making the incidence structure directly operational. Across six reasoning and coding benchmarks with three base LLMs, SIGMA achieves the best average performance and improves over CARD, the strongest non-compositional topology-based baseline, by 2.06, 2.36, and 1.75 points, respectively. It also shows stronger robustness to unseen skill libraries, with an average performance drop of only 0.96 points. These results suggest that compositional node construction is a complementary and important axis for multi-agent design beyond communication topology optimization. Code is available at https://anonymous.4open.science/r/SIGMA-2338/.