Paper deep dive
Reward-Guided Autoregressive Graph Generation for Efficient Multi-Agent Communication Topology Design
Poomphob Suwannapichat, Boonyarit Changaival, Caesar Wu, Pascal Bouvry
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/21/2026, 2:50:52 AM
Summary
The paper introduces RGA-Designer, a method for designing efficient Multi-Agent System (MAS) communication topologies using Reward-Guided Autoregressive Graph Generation. Building on ARG-Designer, it employs a reward model trained via Reinforcement Learning from Human Feedback (RLHF) principles to optimize for both task correctness and structural compactness (sparsity). This approach reduces token consumption by an average of 20.5% while maintaining task accuracy across six benchmarks.
Entities (7)
Relation Signals (6)
RGA-Designer → buildsupon → ARG-Designer
confidence 95% · ARG-Designer, the direct predecessor of our work... We address this limitation by introducing... RGA-Designer
RGA-Designer → usestechnique → RLHF
confidence 92% · introducing a Reward-Guided Autoregressive Graph Generation (RGA-Designer) inspired by Reinforcement Learning from Human Feedback (RLHF).
RGA-Designer → optimizesfor → structural compactness
confidence 90% · jointly captures task correctness and structural compactness
RGA-Designer → reduces → Token Consumption
confidence 90% · reducing token consumption by an average of 20.5%.
RGA-Designer → usesalgorithm → GRPO
confidence 85% · We adopt an on-policy variant of Group Relative Policy Optimization (GRPO) 22 for policy optimization.
RGA-Designer → usesmodel → GraphSAGE
confidence 85% · The graph is encoded by two GraphSAGE layers
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 objective provides no explicit incentive for the model to generate sparse and efficient topologies. We address this limitation by introducing a Reward-Guided Autoregressive Graph Generation (RGA-Designer) inspired by Reinforcement Learning from Human Feedback (RLHF). We train a reward model that jointly captures task correctness and structural compactness, and then fine-tune the pretrained graph generator using the reward model as feedback. Our method preserves task accuracy at the level of ARG-Designer while reducing token consumption by an average of 20.5%.
Tags
Links
- Source: https://arxiv.org/abs/2608.20099v1
- Canonical: https://arxiv.org/abs/2608.20099v1
Trouble viewing inline? Open PDF directly →
Full Text
46,800 characters extracted from source content.
Expand or collapse full text
Reward-Guided Autoregressive Graph Generation for Efficient Multi-Agent Communication Topology Design Poomphob Suwannapichat Affiliation: University of Luxembourg, Luxembourg Boonyarit Changaival Affiliation: King Mongkut’s University of Technology Thonburi, Thailandpoomphob.suwannapichat,pascal.bouvry@uni.lucaesar.wu@ext.uni.luboonyarit.chang@kmutt.ac.th Caesar Wu Affiliation: University of Luxembourg, Luxembourg Pascal Bouvry Affiliation: University of Luxembourg, Luxembourg Abstract 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 objective provides no explicit incentive for the model to generate sparse and efficient topologies. We address this limitation by introducing a Reward-Guided Autoregressive Graph Generation (RGA-Designer) inspired by Reinforcement Learning from Human Feedback (RLHF). We train a reward model that jointly captures task correctness and structural compactness, and then fine-tune the pretrained graph generator using the reward model as feedback. Our method preserves task accuracy at the level of ARG-Designer while reducing token consumption by an average of 20.5%20.5\%. 1 Introduction Large Language Models (LLMs) have recently addressed many problems that were considered challenging in the Natural Language Processing (NLP) domain. By framing other tasks in natural language, LLMs can be adapted to a wide array of applications, frequently achieving surprisingly strong performance. Nevertheless, LLMs still make mistakes, particularly in complex tasks such as reasoning 23. The reasoning capabilities of LLMs remain a subject of active debate. Because these models are fundamentally optimized for next-token prediction, it is difficult to claim that they truly reason rather than verbosely produce sequences of tokens that are likely to follow a given context 6. Several workarounds have been proposed to mitigate this issue, including chain-of-thought prompting 26 and self-verification 28. Although these techniques do not address the root cause of the reasoning limitation, they have been shown to substantially extend the practical performance of LLMs on complex tasks. LLM-based Multi-Agent Systems (MAS) represent another such workaround, in which multiple LLMs collaborate to solve complex problems. By assigning each LLM a specialized role, such as planner, coder, or critic, and orchestrating their interactions, MAS consistently achieve stronger performance than single-LLM baselines. However, MAS also increases inference cost as a trade-off for the improved performance. In static MAS, even simple tasks are processed through the same multi-step pipeline as complex ones, despite often being solvable with a single LLM inference. To make MAS architecture more dynamic, many existing works start from a predefined communication topology and either prune less important components or apply modifications to optimize it for each query 30; 25; 31. ARG-Designer 13 adopts a different perspective, employing an autoregressive graph generator that constructs topologies from scratch. This design enables the topologies to be more flexible and is not constrained by predefined templates. However, ARG-Designer trains the graph generator by maximizing the likelihood of topologies seen in the training set; under this objective, the model has no explicit incentive to favour sparser, more efficient structures. We incorporate a reward-guided training scheme inspired by Reinforcement Learning from Human Feedback (RLHF) 16 which guides the graph generator toward higher-quality graphs through a learned reward model that accounts for both graph size and task correctness. 11 1 Code and detailed hyperparameter settings of the experiments are available at https://github.com/psuwannapich/RGA-Designer. With this method, the graph generator is no longer restricted to reproducing structures seen during training; instead, it is encouraged to discover sparser topologies while preserving task performance. Our main contributions are as follows: • We apply reward-guided training schema to autoregressive MAS topology generation, addressing a limitation of likelihood-based objectives that have no incentive for structural compactness. • We design a graph-level reward model that jointly captures task correctness and structural compactness. • Across six benchmarks, our approach reduces token consumption by an average of 20.5%20.5\% over ARG-Designer while preserving task accuracy. 2 Related Works This section first reviews LLM-based multi-agent systems and the evolution of topology design from static structures to learned, task-adaptive configurations. It then introduces Reinforcement Learning from Human Feedback (RLHF), the training paradigm adapted to guide the graph generator. Finally, it discusses Graph Neural Networks (GNNs), which serve as the backbone of the reward model. 2.1 LLM-based Multi-Agent Systems LLM-based Multi-Agent Systems can be formalized as a directed acyclic graph (DAG), where nodes represent LLM agents with specific roles and edges represent information shared between them. The design of the collaboration graph and the selection of agent roles are crucial for the overall performance of a Multi-Agent System. Early work on MAS has proposed a range of static topologies, including chains, stars, and debate-style configurations 15; 11; 5; 2; 32. Other approaches draw inspiration from real-world workflows, such as role decomposition inspired by software development workflows 19. Subsequent works frame the MAS design problem as query-based topology adaptation. AgentPrune 30 uses a predefined template as the starting point then defines communication redundancy in MAS and performs pruning on graph edges, achieving performance comparable to dense baselines at a fraction of the inference cost. AgentDropout 25 expands this idea by eliminating low-contribution agents (graph nodes) via adjacency matrix optimization. However, both methods start from a predefined template and learn which nodes or edges to remove. They cannot create unseen structures. Rather than pruning predefined structures, G-Designer 31 employs a variational graph autoencoder that encodes a template graph topology along with a task-specific virtual node then decodes a task-adaptive graph with sparsity regularization. Although G-Designer goes beyond pruning, it still optimizes within fixed template graphs. ARG-Designer 13, the direct predecessor of our work, reframes MAS topology design as an autoregressive graph generation task. The collaboration graph is generated from scratch by iteratively producing nodes and edges until a termination signal is reached. At step i, the model samples the role of the next agent viv_i conditioned on the partial graph <iG_<i before step i, the task query q, and the available role pool ℛR: vi∼P(vi∣<i,q,ℛ).v_i P(v_i _<i,q,R). (1) If the sampled role corresponds to the special END token, generation terminates. Otherwise, viv_i is added to the graph, and the model then determines its incoming edges by sampling the existence of an edge from each previously generated node vjv_j (j<ij<i): ej,i∼P(ej,i∣vi,<i,q).e_j,i P(e_j,i v_i,G_<i,q). (2) The graph generation model is trained using a supervised paradigm: candidate graph iG_i is executed against its training query qiq_i and only the graph and query pairs that can complete the task correctly will be included in the dataset D. The graph generation model was trained on the dataset D in order to maximize the conditional log-likelihood of the ground-truth graphs given the query: ℒ(θ)=−∑(,q)∈logPθ(|q)L(θ)=- _(G,q) logP_θ(G|q) (3) To ensure the sparsity of graph generation, the ARG-Designer training pipeline is separated into two steps: cold start and efficiency fine-tuning. Cold start step lets the model explore diverse topologies by creating graph/query pairs candidates using various well-known structures such as complete graphs and star graphs. The efficiency fine-tuning step focuses on creating sparse but efficient graphs by including pruned graphs and verified efficient configurations. 2.2 Reinforcement Learning from Human Feedback Reinforcement learning (RL) is a learning paradigm in which a model improves its policy by interacting with an environment and receiving rewards for the actions it takes. Historically, RL has been mostly applied in robotics and control, where an agent performs actions in a physical environment, observes the resulting reward signal, and adjusts its policy to maximize long-term return. Recently, RL has driven one of the most significant breakthroughs in language modeling: the development of ChatGPT. Beyond pre-training on a large text corpus for next-token prediction, ChatGPT incorporates human preferences to align its outputs with what users find helpful and appropriate. Human annotators are presented with pairs of candidate responses and asked to indicate which one is preferred. The resulting preference dataset is used to train a reward model, which learns to assign a score to a given response that is consistent with human judgment. The LLM is then fine-tuned via reinforcement learning, using the reward model as a proxy for human feedback to refine its output policy. This procedure is known as Reinforcement Learning from Human Feedback (RLHF) 16. 2.3 Graph Neural Networks Graphs are widely used to represent relational data in many applications, including social network analysis, knowledge graphs, and information exchange in LLM-based Multi-Agent Systems. However, due to the nature of graph data, mapping graphs into numerical representations suitable for downstream analysis remains a challenging problem. The process of producing such numerical representations is referred to as graph embedding. Early graph embedding methods adapted objectives from word embedding in the natural language processing (NLP) domain. An embedding model is trained to predict masked nodes in node sequences obtained by traversing the graph through random walks 18; 8. However, these approaches cannot generalize to unseen nodes without re-running the embedding procedure on the new graph. To enable graph embedding models to generalize to unseen graph structures without retraining, the framework of Message Passing Neural Networks (MPNNs) was introduced 7. Each node is initialized with a feature vector, which can either be drawn at random or derived from node metadata. At each layer, every node sends a message to its direct neighbours; the receiving node then aggregates the incoming messages and uses them to update its own embedding. By stacking multiple MPNN layers, information can be propagated beyond direct neighbours to nodes that are several hops away. Building on this foundation, most modern graph embedding models are fundamentally constructed on the message-passing paradigm 21; 12; 9. 3 Problem Definition We represent a multi-agent system (MAS) as a directed acyclic graph =(,ℰ)G=(V,E) that captures the interactions between agents in the system. Each node vi∈v_i corresponds to an LLM-based agent augmented with a predefined role prompt Ri∈ℛR_i , which specifies its function and expertise. A directed edge (vi,vj)∈ℰ(v_i,v_j) indicates that agent viv_i forwards its output mim_i as a textual message to agent vjv_j. To invoke agent viv_i, the input prompt is assembled using template fTf_T from three components: the role prompt RiR_i, the user query q, and the set of messages mj∣(vj,vi)∈ℰ\m_j (v_j,v_i) \ received from its direct predecessors, as formalized in Eq. 4. mi=LLM(fT(Ri,q,mj|(vj,vi)∈ℰ))m_i=LLM (f_T(R_i,q,\m_j|(v_j,v_i) \) ) (4) To get the final answer of MAS, each agent vi∈v_i is executed in topological order of graph G using Eq. 4 to produce its message mim_i, and then aggregating the outputs of the terminal agents into a final answer: a^=Aggregate(mi∣vi∈out), a=Aggregate\! (\m_i v_i _out\ ), (5) where out⊆V_out denotes the set of output agents. The task-completion indicator is then obtained by comparing a a to the ground-truth answer a⋆a : c(,q)=1,if a^=a⋆,0,otherwise.c(G,q)= cases1,&if a=a ,\\ 0,&otherwise. cases (6) The goal of the MAS designer model πθ _θ is to generate a graph structure ∼πθ(∣q)G _θ(G q) from a given task query q that successfully completes the task with the smallest possible structure as shown in following constrained objective: minθq,∼πθ(∣q)[λ||+λℰ|ℰ|]s.t.c(,q)=1 split _θ\;\;E_q,G _θ(G q) [\, _V\,|V|\;+\; _E\,|E|\, ] \\ s.t. c(G,q)=1 split (7) where |||V| and |ℰ||E| are the number of agents and edges in G, and λ,λℰ≥0 _V, _E≥ 0 control the relative penalty on agent count and communication links. 4 Method We propose Reward-Guided Autoregressive Graph Generator (RGA-Designer), which applies the idea of RLHF to the graph generation model, guiding it to produce graphs that can complete the task while keeping the graph structure as compact as possible. Because graph quality is programmatically verifiable, we replace human feedback with explicit rule-based rewards that favor smaller, successful graphs. Our setup falls within the broader paradigm of Reinforcement Learning with Verifiable Rewards (RLVR) 22, where an automated reward signal is provided in place of human annotation. An overview of RGA-Designer is illustrated in Figure 1. Our pipeline consists of three stages, preceded by a prerequisite pretraining stage inherited from ARG-Designer. (0) Pretrained Generator Model: following ARG-Designer, an autoregressive graph generator is trained on query/graph pairs. (1) Dataset Collection: for each task query, candidate graphs are sampled and labeled as successful or failed by executing them on the underlying MAS topology; the resulting samples are then organized into preference pairs. (2) Reward Model Training: a graph-level reward model is trained on the preference pairs, learning to assign higher scores to graphs that are both correct and compact. (3) Policy Optimization: the pretrained generator is fine-tuned with policy optimization, where the reward model guides the policy toward generating graphs with higher task success and lower structural complexity. Figure 1: Overview of our reward-guided pipeline for MAS topology generation. 4.1 Dataset collections We construct the dataset by executing LLMs over candidate graph structures and recording whether each structure successfully completes the task. However, we retain not only the samples that complete the task but also those that fail, since both are informative for training the reward model. Graphs are generated using the pretrained ARG-Designer model with varying sampling temperatures. Due to the autoregressive nature of ARG-Designer, multiple distinct graphs 1(n),2(n),…,M(n)\G^(n)_1,G^(n)_2,…,G^(n)_M\ can be sampled from a single query q(n)q^(n). To further reduce the data collection cost, we additionally include the training samples from both the cold-start and fine-tuning stages of ARG-Designer; since these graph/query pairs have already been executed during ARG-Designer training, incorporating them into our dataset incurs no additional cost. Each training sample si(n)s^(n)_i for the reward model is represented as a triplet (i(n),q(n),ri(n))(G^(n)_i,q^(n),r^(n)_i). Every graph i(n)=(i(n),ℰi(n))G^(n)_i=(V^(n)_i,E^(n)_i) is executed on the agentic system with query q(n)q^(n), and its output is compared against the ground truth, yielding a binary completion flag ci(n)=c(i(n),q(n))c^(n)_i=c(G^(n)_i,q^(n)). The ground-truth reward for the sample is then computed as: ri(n)=λcci(n)+λmax(0,max−|i(n)|max−1)+λℰclip[0,1](ℰmax−|ℰi(n)|ℰmax−ℰmin) splitr^(n)_i=& _cc^(n)_i+ _V (0, V_max-|V^(n)_i|V_max-1 )\\ &+ _Eclip_[0,1] ( E_max-|E^(n)_i|E_max-E_min ) split (8) where λc _c, λ _V, and λℰ _E are hyperparameters that weight task completeness, agent count, and edge count, respectively. maxV_max denotes the maximum number of agents allowed for each dataset (inherited from ARG-Designer), while ℰmin=||−1E_min=|V|-1 and ℰmax=||(||−1)2E_max= |V|(|V|-1)2 correspond to the minimum and maximum possible edge counts for a connected graph of size |||V|. The reward ri(n)r^(n)_i is designed to lie in the range [0,1][0,1], with the weights λc _c, λ _V, and λℰ _E summing to 11. The choice of weights reflects a hierarchy in our design objective: task completion is treated as the dominant criterion (λc=0.6 _c=0.6), while structural compactness serves as a secondary preference (λ=0.3 _V=0.3, λℰ=0.1 _E=0.1). As a result, a candidate that fails to complete the task is penalized more than a candidate that succeeds but uses an inefficient topology, ensuring that correctness is never traded for sparsity. To train the reward model within the RLHF framework, sample pairs must be constructed. Let (n)S^(n) denote the set of training pairs associated with query q(n)q^(n). The pairs in (n)S^(n) are formed from all possible combinations, subject to two filtering conditions. First, at least one sample in each pair must successfully complete the task, as comparing two graphs that both fail provides little useful signal about graph quality. Second, the reward difference between the two samples must exceed a predefined margin δ (initially set to 0.050.05): (n)=(si,sj)∣ci=1∧ri−rj>δS^(n)=\(s_i,s_j) c_i=1 r_i-r_j>δ\ (9) where the indices i and j range over the candidate samples collected for query q(n)q^(n) 4.2 Reward Model The reward model rθr_θ is a graph neural network that scores a candidate graph =(,ℰ)G=(V,E) conditioned on a task query q. To inject both task semantic and graph structure into the encoder, we construct each node feature vector xix_i as the concatenation of three components: xi=[zri‖zq‖ϕi]x_i= [\,z_r_i\;\|\;z_q\;\|\; _i\, ] (10) where zriz_r_i is the role embedding of agent viv_i, zqz_q is the task query embedding. Both embeddings are retrieved from sentence-transformers/all-MiniLM-L6-v2 sentence encoder, yielding zri,zq∈ℝ384z_r_i,z_q ^384. ϕi∈ℝ5 _i ^5 is a vector of structural features comprising the graph size, edge count, generation-order position, in-degree, and out-degree. The graph is encoded by two GraphSAGE layers 9 with residual connections and layer normalization. For each layer ℓ∈1,2 ∈\1,2\: hi(ℓ)=ReLU(LN(SAGE(ℓ)(h(ℓ−1),ℰ)i))+Wres(ℓ)hi(ℓ−1) splith_i^( )=ReLU\! (LN (SAGE^( )(h^( -1),E)_i ) )\\ +W_res^( )h_i^( -1) split (11) where hi(0)=xih_i^(0)=x_i, and Wres(ℓ)W_res^( ) is a learnable projection for the residual. A graph-level embedding is then obtained by global mean pooling over all nodes, and a scalar reward is produced by a two-layer MLP head: rθ(,q)=MLP(1||∑i∈hi(2))r_θ(G,q)=MLP\! ( 1|V| _i h_i^(2) ) (12) Given the preference pairs (n)S^(n), the reward model is trained with the Bradley-Terry pairwise ranking objective 1: ℒr(n)=−wc,rlogσ(rθ(c(n),q(n))CLOSEOPEN−rθ(r(n),q(n))) splitL_r^(n)=-\,w_c,r σ (r_θ(G^(n)_c,q^(n))\\ -r_θ(G^(n)_r,q^(n)) ) split (13) where c(n)G^(n)_c and r(n)G^(n)_r denote the graphs of the chosen and rejected samples, respectively, and wc,r∈(0,1]w_c,r∈(0,1] is a per-pair weight that down-scales pairs carrying less informative signal. In particular, pairs in which both samples successfully complete the task (pass/pass pairs) convey only graph-size information, yet account for roughly 80–90% of the training data. We therefore set wc,r=1w_c,r=1 for pass/fail pairs and wc,r=λp,pw_c,r= _p,p for pass/pass pairs, where λp,p _p,p is initially set to 0.10.1. An additional benefit of training a reward model is that its training data can be shared across datasets. Because each (query, graph) pair is encoded into a latent vector xix_i before being scored (Eq. 10), the reward model can seamlessly accommodate samples containing unseen agent roles. In contrast, ARG-Designer’s node generator (Eq. 1) explicitly conditions on the role pool ℛR to score role candidates, meaning that any sample introducing a new role would require extending the node generator’s classification head and retraining the model. 4.3 Policy optimization Having trained reward model rθr_θ, we then fine-tune graph generator policy πθ _θ to generate graphs that produce high reward r r while remaining close to the pre-trained ARG-Designer reference model πref _ref. We adopt an on-policy variant of Group Relative Policy Optimization (GRPO) 22 for policy optimization. Given the group of graph rewards r^1(n),…,r^G(n)\ r^(n)_1,…, r^(n)_G\ for query q(n)q^(n), the advantage A^i(n) A^(n)_i for each candidate graph is computed by normalizing its reward as shown in Eq. 14, where μr(n)μ^(n)_r is the group mean, σr(n)σ^(n)_r is the group standard deviation. The denominator is lower-bounded by σmin=0.01 _ =0.01. A^i(n)=r^i(n)−μr(n)max(σr(n),σmin) A^(n)_i= r^(n)_i-μ^(n)_r \! (σ^(n)_r,\ _ ) (14) The graph generator policy πθ _θ is trained to maximize the advantage signal while constraining the generated distribution to remain close to the reference model πref _ref, as defined by the following objective: ℒπ(i,q∣θ)=−A^i⋅logπθ(i∣q) _π(G_i,q θ)=- A_i· _θ(G_i q) (15) +β⋅logπθ(i∣q)πref(i∣q) +β· _θ(G_i q) _ref(G_i q) where A^i A_i is the group-relative advantage from Eq. 14, and β is a hyperparameter controlling the strength of the Kullback-Leibler (KL) regularization. Since we can draw a fresh group of G graphs from the current policy πθ _θ at every update step, the standard GRPO importance ratio ρi _i equals 11 when the gradient is calculated. Consequently, ρi _i and the GRPO clipping term can be omitted. 5 Experiments We evaluate our method on the same six benchmarks 4; 14; 20; 17; 10; 3 used by ARG-Designer 13, summarized in Table 1. Each dataset was randomly divided into training, fine-tuning, and testing sets, consisting of 15, 25, and the remaining samples (capped at 500). Table 1: Summary of the six evaluation benchmarks used in our experiments. #Test denotes the number of test instances sampled from each dataset for evaluation. Category Dataset #Test Metric Mathematical GSM8K 500 Accuracy reasoning AQuA 214 Accuracy MultiArith 500 Accuracy SVAMP 500 Accuracy General reasoning MMLU 500 Accuracy Code generation HumanEval 121 Pass@1 To ensure the stability of our results, every experiment is repeated over 10 independent runs, and we report the mean and standard deviation across runs. We benchmark our approach against five baselines: (1) Vanilla, which relies on a single LLM call; (2) G-Designer 31; (3) AgentPrune 30; (4) AgentDropout 25; and (5) ARG or ARG-Designer 13, the direct predecessor of our method. Since MAS execution requires multiple LLM inferences and a long context window to support information exchange between agents, we adopt the open-source lightweight model Qwen3-4B 29 as the underlying LLM in this work. Qwen3-4B can be served on a single NVIDIA Tesla V100 GPU with 16 GB of VRAM handling long context lengths without running out of memory, making it well-suited for our multi-agent setting. We also disable Qwen3’s thinking mode to reduce the number of completion tokens generated per inference. As our reward model can be trained on graphs containing unseen roles (Section 4.2), we train a single global reward model on a combined preference dataset from all six benchmarks. This unified reward model is then used to supervise policy optimization across every benchmark. Furthermore, to ensure that the best topology is selected at inference time, we adopt a Best-of-N (BoN) generation scheme: the policy samples N (set N=5N=5 in our experiments) candidate graphs for each task query, and the candidate with the highest reward scored by the reward model is chosen as the final topology. Note that both the sampling and scoring steps are performed by the topology designer, not by an LLM. The overhead of BoN is negligible compared to LLM calls. To assess whether our results differ significantly in terms of both accuracy and token usage, we apply Welch’s t-test 27, which tests for a difference in means between two distributions. Table 2: Task accuracy (%) across six benchmarks, reported as mean ± standard deviation over 10 runs. Benchmark Vanilla G-Designer AgentPrune AgentDropout ARG RGA (Our) GSM8K 82.68± 0.72 86.98± 0.65 88.00± 1.59 89.08± 1.26 88.36± 1.04 88.76± 0.66 AQuA 76.87± 1.21 83.35± 1.86 82.90± 1.08 83.41± 1.86 81.64± 1.56 82.10± 3.89 MultiArith 97.56± 0.23 97.96± 0.08 98.02± 0.35 97.88± 0.33 98.46± 0.13 98.44± 0.23 SVAMP 90.20± 0.27 94.28± 0.21 94.80± 0.84 94.54± 0.38 94.98± 0.85 94.52± 0.49 HumanEval 73.22± 2.14 80.08± 1.29 82.23± 2.90 81.65± 3.67 82.56± 1.76 83.22± 1.95 MMLU 71.28± 0.78 60.46± 1.06 79.74± 1.49 79.86± 1.33 79.32± 0.91 79.78± 1.27 Average 81.97± 0.56 83.85± 0.52 87.61± 0.68 87.74± 0.64 87.55± 0.49 87.80± 0.60 Table 3: Average tokens usage per task across six benchmarks, reported as mean ± standard deviation over 10 runs (rounded to integer). Best results among MAS methods (excluding the Vanilla baseline) are in bold. Benchmark Vanilla G-Designer AgentPrune AgentDropout ARG RGA (Our) GSM8K 224 ± 10 6104 ± 12 5694 ± 118 6447 ± 441 4546 ± 275 3863 ± 195 AQuA 509 ± 97 9134 ± 67 5710 ± 263 5535 ± 266 3914 ± 162 2633 ± 191 MultiArith 135 ± 0 5347 ± 10 4997 ± 147 5644 ± 454 2824 ± 11 2754 ± 507 SVAMP 142 ± 10 5242 ± 12 4921 ± 84 5748 ± 471 3816 ± 290 3349 ± 446 HumanEval 262 ± 1 2851 ± 23 3043 ± 133 2659 ± 122 2238 ± 119 1715 ± 88 MMLU 208 ± 16 10498 ± 47 11030 ± 1388 8353 ± 1353 5554 ± 798 3875 ± 538 Average 247 ± 18 6529 ± 13 5899 ± 258 5731 ± 251 3815 ± 124 3032 ± 205 Table 4: Welch t-test p-values of RGA-Designer against each benchmark. Bold marks p<0.05p<0.05. Arrows give the direction of the difference: for accuracy ↑ favours RGA-Designer, for token usage ↓ favours RGA-Designer. Comparison GSM8K AQuA MultiArith SVAMP HumanEval MMLU Accuracy G-Designer < 0.001↑ 0.376↓ < 0.001↑ 0.180↑ < 0.001↑ < 0.001↑ AgentPrune 0.188↑ 0.544↓ 0.006↑ 0.377↓ 0.384↑ 0.949↑ AgentDropout 0.489↓ 0.354↓ < 0.001↑ 0.920↓ 0.252↑ 0.892↓ ARG-Designer 0.320↑ 0.735↑ 0.814↓ 0.160↓ 0.437↑ 0.365↑ Token usage G-Designer < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ AgentPrune < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ AgentDropout < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ < 0.001↓ ARG-Designer < 0.001↓ < 0.001↓ 0.673↓ 0.014↓ < 0.001↓ < 0.001↓ Table 2 and Table 3 report task accuracy and token usage for each method, while Table 4 summarizes the p-values from Welch’s t-test comparing our RGA-Designer against other baselines. In terms of accuracy, RGA-Designer yields minor improvements on several benchmarks; however, Welch’s t-test indicates that most of these differences are statistically insignificant (whether improvements or degradations). According to Table 4, none of the accuracy degradation is significant. In contrast, RGA-Designer delivers a substantial reduction in token usage, as clearly shown in Table 3 and confirmed by the corresponding p-values in Table 4. Token reduction is statistically significant on every benchmark except MultiArith when compared with ARG-Designer. We further investigate why MultiArith is the only benchmark that does not yield a significant token reduction. Questions in MultiArith are generated from predefined templates, with new numerical values substituted. As a result, the questions exhibit limited linguistic variation and can be solved with simple topologies, leaving little structural redundancy for RGA-Designer to compress. In contrast, the other benchmarks contain more diverse natural-language questions whose solutions benefit from optimal collaboration structures, providing a larger margin for RGA-Designer to optimize the topology. Table 5: Ablation study on three settings. Full is our complete method; w/o RM removes the global reward model; w/o BoN removes Best-of-N selection. w/o both removes both components. Results are reported as mean ± standard deviation over 10 runs. GSM8K HumanEval MMLU Acc. ↑ Tok. ↓ Acc. ↑ Tok. ↓ Acc. ↑ Tok. ↓ ARG-Designer 88.36 ± 1.04 4546 ± 275 82.56 ± 1.76 2238 ± 119 79.32 ± 0.91 5554 ± 798 Full 88.76 ± 0.66 3863 ± 195 83.22 ± 1.95 1715 ± 88 79.78 ± 1.27 3875 ± 538 w/o RM 88.72 ± 0.99 4166 ± 522 82.40 ± 2.17 1839 ± 116 79.42 ± 1.18 5288 ± 889 w/o BoN 88.28 ± 0.76 4281 ± 253 81.49 ± 2.45 1805 ± 119 79.84 ± 0.94 5056 ± 527 w/o both 88.72 ± 1.14 4207 ± 451 82.64 ± 2.02 1908 ± 95 78.36 ± 0.96 5425 ± 459 Table 5 reports the ablation study on three benchmarks, one from each task category: GSM8K (mathematical reasoning), HumanEval (code generation), and MMLU (general reasoning). The full method achieves the lowest token consumption. It also yields minor accuracy improvements on GSM8K and HumanEval, with the only exception being MMLU, where w/o BoN achieves the highest accuracy. However, this slightly higher accuracy on MMLU comes at a substantial cost in token consumption which uses 30.5%30.5\% more tokens than the full method. 6 Conclusion and Discussion In this work, we introduce RGA-Designer, a reward-guided training scheme that addresses a key limitation of ARG-Designer’s original supervised objective that has no explicit incentive for the model to generate compact topologies. Building on the autoregressive graph generation paradigm, we employ a learned reward model to provide feedback to the graph generator, optimizing it to produce graphs that are sparse but still functional. Across all benchmarks, RGA-Designer preserved task accuracy with no statistical differences, while achieving a substantial reduction in token consumption: on average, 20.5%20.5\% fewer tokens than ARG-Designer and reaching statistical significance on five of six benchmarks. The single exception, MultiArith, is a templated dataset that contains limited linguistic variation, leaving little redundancy for our method to compress. Beyond the efficiency results, our framework offers an additional benefit. Because the reward model scores graphs in embedding space, its training data can be reused across datasets without architectural changes. In contrast, ARG-Designer’s node generator conditions directly on the role pool ℛR, so introducing new agent roles requires extending the role classification head and retraining the generator. Limitations LLM backbone. Due to resource constraints, all experiments use Qwen3-4B as the underlying LLM, and the performance of RGA-Designer against baselines may shift when applied to different models. Our data construction pipeline depends on executing candidate graphs on a specific base LLM in order to label them as successful or failed. Switching to a different base model requires reconstructing the entire training dataset, and supporting heterogeneous MAS in which different agents are powered by different LLMs remains a challenge for our approach. Reliance on ground-truth labels. While RGA-Designer can adapt topologies on a per-query basis, training the graph generator still requires ground truth. Therefore, our method is applicable to tasks with explicit verifiable answers (e.g., code generation, multiple-choice classification). Extending the framework to open-ended tasks without verifiable ground truth is left to future work. Acknowledgment We express our gratitude to Phatarapran Saraluck for providing valuable feedback for methodology design. The experiments presented in this paper were carried out using the HPC facilities of the University of Luxembourg 24. References Bradley and Terry (1952) R. A. Bradley and M. E. Terry Rank analysis of incomplete block designs: i. the method of paired comparisons. Biometrika 39 (3/4), p. 324–345. External Links: ISSN 00063444, 14643510, Link Cited by: §4.2. Chan et al. (2024) C. Chan, W. Chen, Y. Su, J. Yu, W. Xue, S. Zhang, J. Fu, and Z. Liu ChatEval: towards better LLM-based evaluators through multi-agent debate. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §2.1. Chen et al. (2021) M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba Evaluating large language models trained on code. External Links: 2107.03374, Link Cited by: §5. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §5. Du et al. (2024) Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch Improving factuality and reasoning in language models through multiagent debate. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: §2.1. Dziri et al. (2023) N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, P. West, C. Bhagavatula, R. Le Bras, J. D. Hwang, S. Sanyal, S. Welleck, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi Faith and fate: limits of transformers on compositionality. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: §1. Gilmer et al. (2017) J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, p. 1263–1272. Cited by: §2.3. Grover and Leskovec (2016) A. Grover and J. Leskovec Node2vec: scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, New York, NY, USA, p. 855–864. External Links: ISBN 9781450342322, Link, Document Cited by: §2.3. Hamilton et al. (2017) W. L. Hamilton, R. Ying, and J. Leskovec Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, Red Hook, NY, USA, p. 1025–1035. External Links: ISBN 9781510860964 Cited by: §2.3, §4.2. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Basart, A. Zou, M. Mazeika, D. Song, and J. Steinhardt Measuring massive multitask language understanding. In International Conference on Learning Representations, External Links: Link Cited by: §5. Hong et al. (2024) S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou, C. Ran, L. Xiao, C. Wu, and J. Schmidhuber MetaGPT: meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §2.1. Kipf and Welling (2017) T. N. Kipf and M. Welling Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), Cited by: §2.3. Li et al. (2026) S. Li, Y. Liu, Q. Wen, C. Zhang, and S. Pan Assemble your crew: automatic multi-agent communication topology design via autoregressive graph generation. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §1, §2.1, §5, §5. Ling et al. (2017) W. Ling, D. Yogatama, C. Dyer, and P. Blunsom Program induction by rationale generation: learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), R. Barzilay and M. Kan (Eds.), Vancouver, Canada, p. 158–167. External Links: Link, Document Cited by: §5. Madaan et al. (2023) A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, S. Gupta, B. P. Majumder, K. Hermann, S. Welleck, A. Yazdanbakhsh, and P. Clark SELF-refine: iterative refinement with self-feedback. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: §2.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, and R. Lowe Training language models to follow instructions with human feedback. External Links: 2203.02155, Link Cited by: §1, §2.2. Patel et al. (2021) A. Patel, S. Bhattamishra, and N. Goyal Are NLP models really able to solve simple math word problems?. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, K. Toutanova, A. Rumshisky, L. Zettlemoyer, D. Hakkani-Tur, I. Beltagy, S. Bethard, R. Cotterell, T. Chakraborty, and Y. Zhou (Eds.), Online, p. 2080–2094. External Links: Link, Document Cited by: §5. Perozzi et al. (2014) B. Perozzi, R. Al-Rfou, and S. Skiena DeepWalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’14, p. 701–710. External Links: Link, Document Cited by: §2.3. Qian et al. (2024) C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, J. Xu, D. Li, Z. Liu, and M. Sun ChatDev: communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), L. Ku, A. Martins, and V. Srikumar (Eds.), Bangkok, Thailand, p. 15174–15186. External Links: Link, Document Cited by: §2.1. Roy and Roth (2015) S. Roy and D. Roth Solving general arithmetic word problems. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, L. Màrquez, C. Callison-Burch, and J. Su (Eds.), Lisbon, Portugal, p. 1743–1752. External Links: Link, Document Cited by: §5. Scarselli et al. (2009) F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini The graph neural network model. IEEE Transactions on Neural Networks 20 (1), p. 61–80. External Links: Document Cited by: §2.3. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. K. Li, Y. Wu, and D. Guo DeepSeekMath: pushing the limits of mathematical reasoning in open language models. External Links: 2402.03300, Link Cited by: §4.3, §4. Song et al. (2026) P. Song, P. Han, and N. Goodman Large language model reasoning failures. External Links: 2602.06176, Link Cited by: §1. Varrette et al. (2022) S. Varrette, H. Cartiaux, S. Peter, E. Kieffer, T. Valette, and A. Olloh Management of an Academic HPC & Research Computing Facility: The ULHPC Experience 2.0. In Proc. of the 6th ACM High Performance Computing and Cluster Technologies Conf. (HPCCT 2022), Fuzhou, China. External Links: ISBN 978-1-4503-9664-6 Cited by: Acknowledgment. Wang et al. (2025) Z. Wang, Y. Wang, X. Liu, L. Ding, M. Zhang, J. Liu, and M. Zhang AgentDropout: dynamic agent elimination for token-efficient and high-performance LLM-based multi-agent collaboration. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Vienna, Austria, p. 24013–24035. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §1, §2.1, §5. Wei et al. (2022) J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou Chain-of-thought prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA. External Links: ISBN 9781713871088 Cited by: §1. Welch (1947) B. L. Welch THE generalization of ‘student’s’ problem when several different population variances are involved. Biometrika 34 (1-2), p. 28–35. External Links: ISSN 0006-3444, Document, Link, https://academic.oup.com/biomet/article-pdf/34/1-2/28/553093/34-1-2-28.pdf Cited by: §5. Weng et al. (2023) Y. Weng, M. Zhu, F. Xia, B. Li, S. He, S. Liu, B. Sun, K. Liu, and J. Zhao Large language models are better reasoners with self-verification. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, p. 2550–2575. External Links: Link, Document Cited by: §1. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. Li, M. Xue, M. Li, P. Zhang, P. Wang, Q. Zhu, R. Men, R. Gao, S. Liu, S. Luo, T. Li, T. Tang, W. Yin, X. Ren, X. Wang, X. Zhang, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Zhang, Y. Wan, Y. Liu, Z. Wang, Z. Cui, Z. Zhang, Z. Zhou, and Z. Qiu Qwen3 technical report. External Links: 2505.09388, Link Cited by: §5. Zhang et al. (2025a) G. Zhang, Y. Yue, Z. Li, S. Yun, G. Wan, K. Wang, D. Cheng, J. X. Yu, and T. Chen Cut the crap: an economical communication pipeline for LLM-based multi-agent systems. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1, §2.1, §5. Zhang et al. (2025b) G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng G-designer: architecting multi-agent communication topologies via graph neural networks. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1, §2.1, §5. Zhuge et al. (2024) M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber GPTSwarm: language agents as optimizable graphs. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: §2.1. Appendix A Hyperparameter Settings Table 6 consolidates hyperparameters used in our experiments. All values were held fixed across the ten independent runs reported in Section 5. maxV_max is inherited from ARG-Designer and varies by benchmark: 4 for GSM8K, AQuA, MultiArith, and SVAMP, 5 for HumanEval, and 6 for MMLU. The minimum number of agents is 2 for all benchmarks. Table 6: Hyperparameter settings. Values are shared across all six benchmarks unless noted otherwise. Symbol Description Value λc _c Task-completion weight 0.6 λ _V Agent-count weight 0.3 λℰ _E Edge-count weight 0.1 maxV_max Maximum agents allowed 4 / 5 / 6 ℰminE_min Minimum edges ||−1|V|-1 ℰmaxE_max Maximum edges ||(||−1)2 |V|(|V|-1)2 δ Minimum reward gap per pair 0.05 zri,zqz_r_i,z_q Role / query embedding dim. 384 ϕi _i Structural feature dim. 5 wc,rw_c,r Pair weight (pass/fail) 1.0 λp,p _p,p Pair weight (pass/pass) 0.1 G GRPO group size 4 σmin _ Advantage denominator floor 0.01 β KL regularization strength 0.2 N Best-of-N candidates 5