Skip to content

MAGIC: Mixed-Granularity Agent Graphs via Incremental Construction with Dense-Reward Reinforcement Learning

Sep 2026 · 0 citations · 25 references
Computer Science

TL;DR

MAGIC, a dense-reward reinforcement learning framework for mixed-granularity graph generation, outperforms state-of-the-art baselines across eight benchmarks and demonstrates strong inference efficiency in the efficiency study.

Abstract

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.

View source

Similar papers

Preprint Aug 2026

Reward-Guided Autoregressive Graph Generation for Efficient Multi-Agent Communication Topology Design

LLM-based Multi-Agent Systems (MAS) achieve strong performance on complex reasoning tasks by coordinating multiple agents, but at the cost of substantial token consumption. Recent work on automatic topology design, ARG-Designer, has reframed this problem as autoregressive graph generation. However, its training objecti...

Poomphob Suwannapichat, B. Changaival, Caesar Wu et al. · 0 citations

HySTAR: Anchored Hypergraphs for Stable Credit Assignment in Cooperative Multi-Agent Reinforcement Learning

This work introduces HySTAR, a MAPPO-based framework that separates adaptive representation learning from a temporally consistent high-order value-decomposition basis, and demonstrates consistent improvements over MAPPO-style, value-factorization, and dynamic-grouping baselines.

Xing-Long Luo, Yu-Ding Zhang, Yu-Heng Kuang et al. · 0 citations
#artificial intelligence Preprint Aug 2026

When Evidence Shapes Collaboration: Knowledge-Conditioned Topology Generation for Multi-Agent Systems

This work proposes K-GAT (Knowledge-Guided Agent Topology Generator), a neuro-symbolic framework that formulates collaboration topology design as a knowledge-conditioned structure learning problem, integrating external evidence directly into autoregressive graph generation.

Yang-Xiao Jiang, Jia-Run Fan, Ming-Cong Xu et al. · 1 citation
Sep 2026

AgentWorld: Benchmarking Long-Horizon Collaboration of Multi-agent LLMs

To quantify collaboration effectiveness in addition to conventional binary task success, Causal Collaboration Effectiveness (CCE) is proposed, a graph-based metric that traces causal dependencies between agent actions and measures what fraction of a team's effort actually contributed to the outcome.

Raphael Shu, Yu-Sen Zhang, Y. Cho et al. · 2 citations
#machine learning Preprint Oct 2026

Continual Graph Multi-Agent Reinforcement Learning

In Continual Multi-Agent Reinforcement Learning (CMARL), agents learn cooperative policies across sequences of tasks, aiming to adapt effectively to new tasks while preserving the ability to solve previously encountered ones. In many applications, tasks differ in their underlying structure, which can represent, for exa...

Tommaso Marzi, Ahmed Hendawy, Jan Peters et al. · 0 citations

Multi-Agent System Search via Active Substructure-aware Policy Optimization

ASPO introduces an Adaptive Query-Selection Mechanism (AQSM) that focuses training on queries at the policy's competence boundary: those it can solve but not yet reliably, and introduces substructure-level rewards that measure output-quality gains within each action's descendant subgraph.

Bei-Cheng Xu, Bo-Wen Fan, Wei Qian et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.