MAGIC: Mixed-Granularity Agent Graphs via Incremental Construction with Dense-Reward Reinforcement Learning
MAGIC uses dense-reward reinforcement learning to build mixed-granularity multi-agent graphs that beat baselines on eight benchmarks.
The paper introduces MAGIC, a reinforcement-learning method that builds mixed-granularity collaboration graphs for LLM multi-agent systems. It sequentially selects a functional role, instantiates it as a single agent or a reusable group, and connects it to existing units. Potential-based reward shaping supplies intermediate feedback from probe utility and structural signals while preserving the cumulative task reward. The authors say MAGIC outperforms state-of-the-art baselines across eight benchmarks and shows strong inference efficiency.
- MAGIC builds graphs by selecting role, granularity, and connections sequentially.
- Dense rewards use potential-based shaping from utility and structure.
- Authors report gains over state-of-the-art baselines on eight benchmarks.
- The study also reports stronger inference efficiency than prior generators.
Full article185 words · extracted from arxiv.org · click to collapse
Collaboration topology shapes both the performance and execution cost of LLM-based multi-agent systems. Because tasks differ in complexity and required capabilities, recent approaches generate task-specific collaboration graphs that specify agent participation and information flow. However, representative topology generators use either individual agents or predefined groups throughout an organization, overlooking differing collaboration needs across subtasks. Our key insight is to select granularity locally for each functional role, combining fine-grained control with reusable collaboration patterns within one organization. Learning such organizations requires exploring a combinatorial construction space with limited intermediate feedback from final-answer rewards. Therefore, we propose MAGIC, a dense-reward reinforcement learning framework for mixed-granularity graph generation. Specifically, MAGIC constructs a mixed-granularity agent graph by sequentially selecting a functional role, instantiating it as a single agent or reusable group, and connecting it to existing units. We directly optimize the construction policy using returns from trajectories sampled under the current policy and use potential-based reward shaping to provide intermediate feedback from probe-based utility and structural signals while preserving the cumulative task reward. MAGIC outperforms state-of-the-art baselines across eight benchmarks and demonstrates strong inference efficiency in our efficiency study.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.26667