💬 NLP

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

This paper introduces RGA-Designer, a reward-guided autoregressive graph generation method inspired by RLHF that optimizes multi-agent communication topologies to reduce token consumption by an average of 20.5% while maintaining task accuracy.

Original authors: Poomphob Suwannapichat, Boonyarit Changaival, Caesar Wu, Pascal Bouvry

Published 2026-08-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Poomphob Suwannapichat, Boonyarit Changaival, Caesar Wu, Pascal Bouvry

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of artificial intelligence, a powerful tool known as the Large Language Model has emerged, capable of generating human-like text and solving complex problems. However, these models are not perfect; they can stumble when faced with tasks requiring deep reasoning or intricate planning. To overcome this, researchers have developed Multi-Agent Systems, where several specialized AI assistants work together, much like a team of experts in a room, each handling a specific part of a problem. One agent might plan the steps, another writes the code, and a third checks for errors. While this teamwork often produces better results than a single AI working alone, it comes with a significant cost. Every time these agents communicate, the system consumes a vast amount of digital resources, measured in tokens, which are the basic units of text the computer processes. This high consumption makes the systems expensive to run and slow to respond, creating a need for a way to make these digital teams more efficient without sacrificing their intelligence.

The challenge lies in how these agents are connected. In many current systems, the connections between agents are fixed or created by simply removing unnecessary parts from a pre-existing, overly complex network. A recent approach called ARG-Designer attempted to build these networks from scratch, creating a new map of connections for every single question asked. While this offered great flexibility, the system had a blind spot: it was trained to simply copy the patterns it saw in its training data, without any specific instruction to keep the network small or simple. As a result, it often built elaborate, crowded maps of communication that used far more resources than necessary, even when a simpler path would have worked just as well.

To solve this, a team of researchers introduced a new method called RGA-Designer, which acts as a strict but helpful coach for the AI. Instead of just asking the AI to mimic past examples, this new system teaches the AI to value efficiency. The researchers trained a separate "reward model," a kind of digital judge, to evaluate every network the AI creates. This judge looks at two things: did the team solve the problem correctly, and was the network of connections as small and compact as possible? If the AI builds a massive, tangled web that solves the problem, the judge gives it a lower score than if it builds a lean, direct line of communication that achieves the same result. The AI then learns from these scores, adjusting its behavior to favor the simpler, more efficient designs. This process is inspired by how humans learn from feedback, where a student improves not just by getting answers right, but by finding the most elegant way to get there.

The results of this approach were tested across six different types of difficult tasks, ranging from solving math word problems to writing computer code and answering general knowledge questions. The researchers found that the new method maintained the same high level of accuracy as the previous best system. The teams still solved the problems correctly, and the quality of the answers did not drop. However, the difference in efficiency was striking. On average, the new system used about 20.5 percent fewer digital tokens to complete the same tasks. In some specific tests, the savings were even more dramatic, with the system using significantly less computing power to reach the same conclusion. This reduction means that these intelligent teams can work faster and cost less to operate, making advanced AI collaboration more accessible.

One interesting exception was a dataset of math problems generated from fixed templates. In these cases, the questions were so similar and the solutions so straightforward that the system could not find much extra space to trim. This suggests that the method works best when the problems are diverse and complex enough to allow for different ways of organizing the team. The researchers also noted that their system is flexible; because the judge evaluates the overall structure of the team rather than memorizing specific roles, it can adapt to new types of agents without needing to be completely retrained. While the system currently relies on tasks with clear, verifiable answers, the success of this reward-guided approach suggests a promising path forward for making artificial intelligence teams not just smarter, but also leaner and more economical.

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

Problem Statement

Large Language Model (LLM)-based Multi-Agent Systems (MAS) have demonstrated strong performance on complex reasoning tasks by coordinating specialized agents. However, this performance comes at the cost of substantial token consumption. While recent work like ARG-Designer reframed topology design as an autoregressive graph generation task—constructing communication topologies from scratch rather than pruning predefined templates—it suffers from a critical limitation: its training objective maximizes the likelihood of observed topologies without providing an explicit incentive for structural compactness. Consequently, the model lacks a mechanism to favor sparse, efficient structures over dense ones, leading to unnecessary inference costs.

Methodology

The authors propose RGA-Designer (Reward-Guided Autoregressive Graph Generator), a framework inspired by Reinforcement Learning from Human Feedback (RLHF) but adapted for graph generation using verifiable rewards. The pipeline consists of three main stages following a pretrained generator:

Dataset Collection: Candidate graphs are sampled from the pretrained ARG-Designer model for various task queries. These graphs are executed on the MAS to determine if they successfully complete the task. The dataset includes both successful and failed samples to provide informative signals for the reward model.
Reward Model Training: A graph-level reward model is trained on preference pairs constructed from the collected data.
- Reward Function: The reward $r$ is a weighted sum of task correctness ( $c$ ), agent count ( $|V|$ ), and edge count ( $|E|$ ). Task completion is the dominant criterion ( $\lambda_c = 0.6$ ), while structural compactness serves as a secondary preference ( $\lambda_V = 0.3, \lambda_E = 0.1$ ).
- Architecture: The reward model is a Graph Neural Network (GNN) using GraphSAGE layers. It encodes node features by concatenating role embeddings, task query embeddings, and structural features (graph size, edge count, position, in/out-degree).
- Training Objective: The model is trained using the Bradley-Terry pairwise ranking objective on pairs where at least one sample succeeds and the reward difference exceeds a margin.
Policy Optimization: The pretrained graph generator is fine-tuned using Group Relative Policy Optimization (GRPO). The policy is optimized to maximize the advantage signal derived from the reward model while constraining the generated distribution to remain close to the reference model via KL regularization. During inference, a Best-of-N (BoN) strategy is employed, where $N=5$ candidate graphs are sampled, and the one with the highest reward score is selected.

Key Contributions

Reward-Guided Training Schema: The authors apply a reward-guided training approach to autoregressive MAS topology generation, addressing the lack of structural compactness incentives in standard likelihood-based objectives.
Joint Reward Model Design: They designed a graph-level reward model that jointly captures task correctness and structural compactness, allowing the system to discover sparser topologies without sacrificing performance.
Efficiency Gains: The method achieves a significant reduction in token consumption while maintaining task accuracy comparable to the baseline.

Experimental Results

The method was evaluated on six benchmarks: GSM8K, AQuA, MultiArith, SVAMP (mathematical reasoning), MMLU (general reasoning), and HumanEval (code generation). The underlying LLM used was Qwen3-4B.

Token Efficiency: RGA-Designer reduced token consumption by an average of 20.5% compared to ARG-Designer. This reduction was statistically significant (via Welch's t-test) on five of the six benchmarks. The exception was MultiArith, where questions are generated from rigid templates with limited linguistic variation, leaving little structural redundancy to compress.
Task Accuracy: RGA-Designer preserved task accuracy at the level of ARG-Designer. Statistical analysis indicated that differences in accuracy were generally insignificant, with no significant degradation observed.
Ablation Study: Removing the global reward model or the Best-of-N selection resulted in higher token consumption, confirming the necessity of both components for optimal efficiency.

Significance and Claims

The paper claims that RGA-Designer successfully addresses the efficiency bottleneck in LLM-based MAS by shifting the training paradigm from simple likelihood maximization to reward-guided optimization. By leveraging a learned reward model that prioritizes correctness while penalizing structural complexity, the system generates communication topologies that are "sparse but functional."

The authors highlight a specific architectural advantage: because the reward model operates in an embedding space, it can be trained on a unified dataset across different benchmarks and accommodate unseen agent roles without retraining the generator's classification head. This contrasts with ARG-Designer, which requires explicit conditioning on a fixed role pool.

The paper maintains a modest tone regarding its limitations, acknowledging that the approach relies on ground-truth labels (limiting applicability to tasks with verifiable answers) and that the current experiments are constrained to a specific base LLM (Qwen3-4B), with performance potentially varying across different model backbones.