Paper deep dive
Response-Conditioned Parallel-to-Sequential Orchestration for Multi-Agent Systems
Nurbek Tastan, Alex Iacob, Lorenzo Sani, Meghdad Kurmanji, Nicholas D. Lane, Samuel Horvath, Karthik Nandakumar
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/8/2026, 3:50:22 PM
Summary
The paper introduces Nexa, a hybrid orchestration framework for multi-agent LLM systems that dynamically bridges parallel and sequential execution modes. Nexa initiates with a parallel draft stage, embeds responses into a shared semantic space, and uses a lightweight transformer policy to predict a sparse directed acyclic graph (DAG). If the graph is empty, the system remains parallel; otherwise, it performs one sequential propagation pass. Trained via policy-gradient optimization with a sparsity penalty, Nexa eliminates the need for external judges or fixed topologies, demonstrating improved accuracy-cost tradeoffs and strong generalizability across tasks, agent counts, and model scales on benchmarks like AQUA-RAT, HumanEval, and GSM8K.
Entities (12)
Relation Signals (11)
Nexa → bridges → Parallel execution
confidence 95% · Nexa begins with a parallel execution stage... bridges the gap between the two modes.
Nexa → bridges → Sequential execution
confidence 95% · Nexa begins with a parallel execution stage... bridges the gap between the two modes.
Multi-agent systems → solvetasksusing → LLMs
confidence 95% · Multi-agent systems can solve complex tasks through collaboration between multiple Large Language Model agents.
Nexa → uses → Directed Acyclic Graph
confidence 94% · predicts a sparse directed acyclic communication graph.
Sequential execution → communicatesvia → Directed Acyclic Graph
confidence 92% · In contrast, sequential systems allow agents to communicate via a directed topology and refine one another step by step.
Nexa → evaluatedon → HumanEval
confidence 90% · The empirical study is designed to demonstrate the generalizability... across AQUA-RAT, HumanEval, and GSM8K.
Nexa → evaluatedon → AQUA-RAT
confidence 90% · The base training setting uses Qwen2.5-1.5B-Instruct agents on AQUA-RAT
Nexa → evaluatedon → GSM8K
confidence 90% · The empirical study is designed to demonstrate the generalizability... across AQUA-RAT, HumanEval, and GSM8K.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-agent systems can solve complex tasks through collaboration between multiple Large Language Model agents. Existing collaboration frameworks typically operate in either a parallel or a sequential mode. In the parallel mode, agents respond independently to queries followed by aggregation of responses. In contrast, sequential systems allow agents to communicate via a directed topology and refine one another step by step. However, both modes are inadequate for achieving the desired objectives of minimizing communication and latency while simultaneously maximizing the accuracy of the final response. In this work, we introduce a hybrid paradigm called Nexa, a trainable response-conditioned policy that bridges the gap between the two modes. Nexa begins with a parallel execution stage, embeds the resulting responses into a shared semantic space, and then predicts a sparse directed acyclic communication graph. If the graph is empty, the system remains purely parallel; if it is non-empty, the system performs one sequential message propagation. The policy is a lightweight transformer model, and the method avoids the need for external LLM judges or reward models, as well as hand-crafted test-time topology search. We formalize this hybrid execution problem, show that the resulting graph is acyclic by construction, and that the framework strictly subsumes pure parallel execution, and present a training procedure based on policy-gradient optimization. Results demonstrate that the response-conditioned policy learned by Nexa under one setting can be reused when the number of agents, the task, or the underlying agent changes, thus emphasizing the generalizability of the learned communication policy.
Tags
Links
- Source: https://arxiv.org/abs/2605.15573v1
- Canonical: https://arxiv.org/abs/2605.15573v1
Trouble viewing inline? Open PDF directly →
Full Text
54,682 characters extracted from source content.
Expand or collapse full text
Response-Conditioned Parallel-to-Sequential Orchestration for Multi-Agent Systems Nurbek Tastan1,2 Alex Iacob2,3 Lorenzo Sani2,3 Meghdad Kurmanji2 Nicholas D. Lane2,3 Samuel Horváth1 Karthik Nandakumar1,4 1MBZUAI, UAE 2University of Cambridge, UK 3Flower Labs, UK 4Michigan State University, USA Abstract Multi-agent systems can solve complex tasks through collaboration between multiple Large Language Model agents. Existing collaboration frameworks typically operate in either a parallel or a sequential mode. In the parallel mode, agents respond independently to queries followed by aggregation of responses. In contrast, sequential systems allow agents to communicate via a directed topology and refine one another step by step. However, both modes are inadequate for achieving the desired objectives of minimizing communication and latency while simultaneously maximizing the accuracy of the final response. In this work, we introduce a hybrid paradigm called Nexa, a trainable response-conditioned policy that bridges the gap between the two modes. Nexa begins with a parallel execution stage, embeds the resulting responses into a shared semantic space, and then predicts a sparse directed acyclic communication graph. If the graph is empty, the system remains purely parallel; if it is non-empty, the system performs one sequential message propagation. The policy is a lightweight transformer model, and the method avoids the need for external LLM judges or reward models, as well as hand-crafted test-time topology search. We formalize this hybrid execution problem, show that the resulting graph is acyclic by construction, and that the framework strictly subsumes pure parallel execution, and present a training procedure based on policy-gradient optimization. Results demonstrate that the response-conditioned policy learned by Nexa under one setting can be reused when the number of agents, the task, or the underlying agent changes, thus emphasizing the generalizability of the learned communication policy. 1 Introduction Large language models (LLMs) have become increasingly capable at reasoning, coding, planning, and dialogue, yet a single model still suffers from stochastic failures, brittle long-horizon reasoning, and occasional hallucinations. Multi-agent systems aim to address these weaknesses by distributing problem solving across multiple agents whose outputs can complement, critique, or refine one another. The central question of such systems is how that collaboration should be orchestrated. Existing LLM-based multi-agent systems largely fall into two categories. In parallel systems, agents answer independently, and their outputs are combined by majority voting, self-consistency, or a learned aggregation rule (Wang et al., 2023; Jiang et al., 2023). In sequential systems, agents are arranged in a communication topology, often a chain, tree, or a more general graph, and information is propagated step by step (Zhuge et al., 2024; Qian et al., 2025). Parallel systems are simple and scalable, but they are computationally expensive, token-intensive, and often redundant, requiring multiple rounds of parallel message propagation while still being unable to exploit targeted communication when one draft could help repair another. Sequential systems can support error correction and information flow, but they require a topology and therefore inherit the burden of deciding who should communicate with whom. Prior work has explored fixed topologies, policy-gradient optimization over edges, graph generators conditioned on tasks or roles, and judge-based routing, each adding substantial token, compute, optimization, coordination overhead, or reducing transferability across settings (Qian et al., 2025; Zhuge et al., 2024; Zhang et al., 2025b). These two paradigms are often treated as separate design choices. A system is either built as a parallel ensemble or as a sequential graph-based collaboration mechanism. Yet, this distinction is too rigid. In many realistic settings, the right approach is not to commit in advance to a single paradigm, but to start in parallel and then decide, based on the agent’s actual outputs, whether sequential propagation is necessary. If the initial responses already contain strong agreement and sufficient information, additional communication may be unnecessary. If they disagree in informative ways, or if useful signals are scattered across agents, then structured propagation may help. This suggests that the real problem is not “parallel or sequential” in the abstract, but rather: Given the current pool of agent responses, should the system remain in the parallel regime, or should it instantiate a communication graph and perform sequential refinement? To answer this question, we introduce Nexa (from “nexus”, a connection or link), a trainable policy for communication graph prediction in multi-agent LLM systems. Nexa begins with a parallel draft stage in which all agents answer independently. The resulting response pool is embedded into a shared semantic space, producing a compact representation of the current response state of the team. A lightweight transformer-based policy then predicts a sparse directed acyclic graph (DAG). If the graph is empty, the system remains in the parallel regime and returns the parallel aggregate. If the graph is non-empty, the system executes one sequential consolidation pass in which selected agents update their responses using information from upstream nodes. This formulation deliberately treats parallel and sequential execution not as mutually exclusive system designs, but as two outcomes of the same learned policy. In this sense, the central contribution of Nexa is not merely graph prediction. It is a mechanism for bridging the gap between parallel execution and sequential execution by using parallel drafts to decide whether structured propagation is needed and, if so, how it should proceed. A second principle of the method is simplicity. We do not learn the topological order. Instead, we induce the order from agent contributions, retaining the most stable organizing principle of response-conditioned communication. The policy learns only the communication edges. We score the candidate communication edges using the affinity matrix formed from transformer-contextualized response representations. This makes the policy lightweight and keeps the graph decoder tightly coupled to the semantic interactions encoded by the backbone. Nexa is also designed to be agnostic to superficial configuration details. The policy consumes semantic representations of agent outputs rather than role labels, agent identities, or model-family indicators. As a consequence, the planner is structurally insensitive to which agent is called “Programmer” or “Assistant”; what matters is what the agents actually say. This does not by itself guarantee transfer across all tasks or backbones, and we explicitly treat that as an empirical question. But it does mean that the policy class is not intrinsically tied to a fixed role inventory or a single team structure. The paper makes four contributions. First, it formalizes a hybrid decision problem in which a learned communication graph determines whether a multi-agent system remains parallel or enters a sequential propagation regime. Second, it proposes a contribution-ordered, attention-based graph policy that predicts only the communication edges, keeping the controller simple and acyclic by construction. Third, it integrates the key theoretical properties of the method directly into the formulation: DAG validity, hybrid subsumption, and permutation-based identity agnosticism. Fourth, it empirically evaluates Nexa across reasoning and programming tasks, showing improved accuracy-cost tradeoffs, sparse communication behavior, and transfer across agent counts, tasks, model scales, and generations. 2 Problem Formulation and Preliminaries Let ∈1,…,NA∈\A_1,…,A_N\ be a set of N agents, and let Q be a user query. Each agent may differ in prompt, role, or backbone model, but the communication policy introduced in this work does not rely on these identities explicitly. Instead, it operates on the semantic content of the agents’ responses. Given the query, each agent independently produces an initial response ℛn(0)=n(),n∈1,2,…,N.R_n^(0)=A_n(Q), n∈\1,2,…,N\. (1) The first phase is fully parallel and produces a draft response set ℛ(0)=ℛ1(0),…,ℛN(0)R^(0)=\R_1^(0),…,R_N^(0)\. The purpose of this is twofold. First, it provides diverse candidate solutions to the query. Second, and more importantly for our setting, it exposes the current response state of the multi-agent system. Since LLM outputs are inherently stochastic, this realized state is more informative for downstream coordination than static task labels or role descriptions. This response-conditioned perspective is central to the present work and follows the same foundational motivation that underlies SelfOrg (Tastan et al., 2026). To reason about relations among agent outputs, we map each response into a shared semantic embedding space using a fixed lightweight encoder f (all-MiniLM-L6-v2 (Reimers and Gurevych, 2019)): rn=f(ℛn(0))∈ℝd.r_n=f(R_n^(0)) ^d. Following SelfOrg (Tastan et al., 2026), we define the average response embedding ravg=1N∑n=1Nrnr_avg= 1N _n=1^Nr_n and contribution scores ψn=cos(rn,ravg). _n= (r_n,r_avg). SelfOrg motivates ψn _n as a linear-time approximation to a Shapley-style contribution value (Shapley, 1953) and shows that, under suitable separation conditions, ranking by ψn _n preserves the normalized Shapley ordering. This is precisely why Nexa uses contribution to define the topological ordering of the edges. The orchestration problem is to predict a directed communication graph =(,ℰ,π),G=(V,E,π), where V=1,…,N,E⊆V×V,V=\1,…,N\,E V× V, and π is an order over the nodes. If the graph is empty (ℰ=∅E= ), the system stays in the parallel regime and outputs an aggregate of the initial drafts. If it is non-empty (ℰ≠∅E≠ ), the graph induces a sequential propagation step. For each node n, define its parent set Pa(n)=m:(m→n)∈ℰ.Pa(n)=\m:(m→ n)∈E\. Then the updated response is ℛn(1)=n(,ℛm(⋆):m∈Pa(n)),Pa(n)≠∅,ℛn(0),Pa(n)=∅,R_n^(1)= casesA_n(Q,\R_m^( ):m (n)\),&Pa(n)≠ ,\\ R_n^(0),&Pa(n)= , cases (2) where ℛm(⋆)R_m^( ) denotes the most recent available parent response under the topological execution order. The final answer is selected from the resulting response pool using a judge-free aggregation rule. Let n\ z_n\ be the final response embeddings and wn\w_n\ their contribution weights. We compute zcentroid=∑n=1Nwnn∑n=1Nwn,n⋆=argmaxncos(n,centroid).z_centroid= _n=1^Nw_n z_n _n=1^Nw_n, n = _n ( z_n, z_centroid). (3) and return the corresponding response. The learning objective is to maximize final task correctness. Given ground truth y and final prediction y y_G under graph G, the reward is R()=[Eval(y^,y)=1].R(G)= 1 [Eval( y_G,y)=1 ]. (4) The policy, therefore, learns to predict a communication graph that determines whether the initial parallel responses should remain as they are or be further refined through structured propagation. 3 Methodology 3.1 System Overview Nexa consists of five stages. First, all agents produce draft responses in parallel. Second, those responses are embedded into a shared semantic space. Third, a response-conditioned transformer policy predicts a sparse communication graph. Fourth, if the graph is non-empty, the corresponding destination nodes are updated sequentially. Fifth, the final answer is selected from the resulting response pool by weighted-centroid-based aggregation. This design has a central conceptual consequence: parallel execution is not discarded when sequential communication is introduced. Instead, the parallel draft stage becomes the source of evidence that determines whether the system should remain in the parallel regime or transition into a sequential propagation regime. 3.2 Contribution-Defined Order and DAG Validity We set the topological order as π=argsort(ψ1,…,ψN;ψk≥ψk+1,∀k∈[N]).π=argsort( _1,…, _N; _k≥ _k+1,∀ k∈[N]). In other words, higher-contribution agents are always placed earlier in the communication order. The feasible edge set is therefore restricted to ℰπ=(m,n):π−1(m)<π−1(n),E_π=\(m,n):π^-1(m)<π^-1(n)\, (5) so that communication is only allowed to move forward under the contribution order. Proposition 1 (Acyclicity by construction). For any edge set ℰ⊆ℰπE E_π, the graph =(,ℰ,π)G=(V,E,π) is a directed acyclic graph. Proof. Assume for contradiction that G contains a directed cycle v1→v2→⋯→vK→v1.v_1→ v_2→·s→ v_K→ v_1. (6) Because every edge must go forward under π, we must simultaneously have π−1(v1)<π−1(v2)<⋯<π−1(vK)<π−1(v1),π^-1(v_1)<π^-1(v_2)<·s<π^-1(v_K)<π^-1(v_1), (7) which is impossible. Hence, no directed cycle can exist. ∎ This parameterization is simpler than detecting and repairing cycles after graph prediction because DAG validity is built directly into the action space of the policy. 3.3 Response-Conditioned Graph Policy The graph policy consumes only the current response set, not agent identities, role labels, or model-family indicators. Let =[r1,…,rN]⊤∈ℝN×d.X=[r_1,…,r_N] ^N× d. (8) A transformer encoder (Vaswani et al., 2017) EncθEnc_θ maps the response set to contextualized node states ℋ=Encθ(X)=[1,…,N]⊤,n∈ℝdh.H=Enc_θ(X)=[ h_1,…, h_N] , h_n ^d_h. (9) Because the encoder operates on the response embeddings without identity-specific tokens, the policy is permutation-equivariant over the agent dimension. Proposition 2 (Permutation-based identity agnosticism). Assume that the response encoder f is applied independently to each response and that EncθEnc_θ is permutation-equivariant. Then, for any permutation matrix P, Encθ(P)=PEncθ(),Enc_θ(PX)=PEnc_θ(X), (10) the induced graph distribution is equivariant to any relabeling of agents. Proof. Since EncθEnc_θ (transformer) without positional encodings is permutation-equivariant, permuting agent indices permutes X and thus Encθ()Enc_θ(X); the remaining steps (cosine-to-mean scoring, ordering, and edge construction) are permutation-consistent, so the graph distribution is equivariant. ∎ We then predict communication edges directly from the globally contextualized hidden states. Concretely, we form a response-response score matrix from the contextualized states: Λ=ℋℋ⊤. =HH . (11) Here, Λ is not the final adjacency matrix; it provides edge logits that are passed through a sigmoid and then sampled to obtain the communication graph. This construction is deliberate. The hidden states in ℋH are already globally contextualized, so the resulting edge logits are informed by the entire response set rather than by isolated response pairs. In this way, the communication graph is read directly from the shared semantic structure induced by the encoder. 3.4 Response Propagation and Aggregation Nexa does not require a separate stop network or node-activation network. The graph itself determines both whether sequential communication occurs and which nodes are updated. A node is updated if and only if it has at least one incoming edge: un=[∑m=1N[(m→n)∈ℰ]>0].u_n= 1 [ _m=1^N 1[(m→ n)∈E]>0 ]. (12) If ℰ=∅E= , then un=0u_n=0 for all nodes, no additional calls are made, and the system returns the parallel aggregate. If ℰ≠∅E≠ , the graph induces one sequential consolidation pass. Proposition 3 (Hybrid subsumption). The policy class of Nexa strictly subsumes the pure parallel regime. Proof. The empty graph ℰ=∅E= is always attainable (all edge probabilities zero/small), in which case no updates occur, and the method reduces to pure parallel execution with aggregation. Any ℰ≠∅E≠ induces at least one sequential update, so the policy class strictly contains the parallel regime. ∎ When ℰ≠∅E≠ , sequential propagation follows the contribution order π. For node n, define Pa(n)=m:(m→n)∈ℰ.Pa(n)=\m:(m→ n)∈E\. (13) The updated response is then ℛn(1)=n(,ℛm(⋆):m∈Pa(n)),Pa(n)≠∅,ℛn(0),Pa(n)=∅,R_n^(1)= casesA_n\! (Q,\R_m^( ):m (n)\ ),&Pa(n)≠ ,\\ R_n^(0),&Pa(n)= , cases (14) where ℛm(⋆)R_m^( ) denotes the most recent available parent response under the topological execution order. Because all edges go forward under π, each parent response is available when a destination node is updated. After either staying in the parallel regime or completing one propagation pass, Nexa selects the final answer without using an external judge. Let ℛ~n R_n denote the final candidate response for agent n and let zn=f(ℛ~n),zavg=1N∑n=1Nzn,wn=cos(zn,zavg).z_n=f( R_n), z_avg= 1N _n=1^Nz_n, w_n= (z_n,z_avg). (15) We then compute the contribution-weighted centroid zcentroid=∑n=1Nwnzn∑n=1Nwnz_centroid= _n=1^Nw_nz_n _n=1^Nw_n and select n⋆=argmaxncos(zn,zcentroid),y^=ℛ~n⋆.n = _n (z_n,z_centroid), y= R_n . (16) This aggregation rule directly inherits the response-conditioned, judge-free philosophy of SelfOrg (Tastan et al., 2026). 3.5 Training Objective The deployment objective is the final task correctness. For a labeled example (,y)(Q,y), let y y_G denote the final output under graph G. In the current implementation, correctness is checked with the same verifier used in evaluation, instantiated as an xVerify-based binary reward (Chen et al., 2025). We therefore define the task reward Rtask()=[Eval(y^,y)=1].R_task(G)= 1 [Eval( y_G,y)=1 ]. (17) Because the order π is fixed by the contribution scores, the graph log-probability decomposes over feasible forward edges: logpθ(ℰ∣,π)=∑(m,n)∈ℰπ(em→nlogpm→n+(1−em→n)log(1−pm→n)). p_θ(E X,π)= _(m,n)∈E_π (e_m→ n p_m→ n+(1-e_m→ n) (1-p_m→ n) ). (18) The algorithm also applies an explicit sparsity penalty to the sampled graph reward in the same spirit as topology-economical methods (Zhang et al., 2025a). Let M=|ℰπ|=N(N−1)2M=|E_π|= N(N-1)2 be the number of feasible forward edges under the contribution-defined order. For a sampled graph G, we define the sparsity-regularized reward Rsp()=Rtask()−λsp|ℰ|M,R_sp(G)=R_task(G)- _sp |E|M, (19) where λsp≥0 _sp≥ 0 controls how strongly dense communication graphs are penalized. We train Nexa with REINFORCE and a batch-mean baseline. For a mini-batch of sampled graphs (i)i=1B\G^(i)\_i=1^B, we set b=1B∑i=1BRsp((i)),A(i)=Rsp((i))−b.b= 1B _i=1^BR_sp(G^(i)), A^(i)=R_sp(G^(i))-b. (20) The policy-gradient term is ℒ=−1B∑i=1BA(i)logpθ(ℰ(i)∣(i),π(i)).L=- 1B _i=1^BA^(i) p_θ(E^(i) X^(i),π^(i)). (21) Finally, we obtain the final optimization goal: it is REINFORCE with batch-mean advantage, while sparsity is enforced through the edge-count penalty in the reward. The full procedure is summarized in Algorithm 1. 4 Experiments The empirical study is designed to demonstrate the generalizability of the learned communication policy. Rather than only reporting in-domain performance for the training configuration, we evaluate whether a response-conditioned policy learned in one setting can be reused when the number of agents, the task, or the underlying agent changes, thus emphasizing training efficiency. 4.1 Experimental Setup The base training setting uses Qwen2.5-1.5B-Instruct agents (Qwen et al., 2025) on AQUA-RAT (Ling et al., 2017) and GSM8K (Cobbe et al., 2021) with N=10N=10 agents. Unless otherwise specified, the policy is trained with REINFORCE, a batch-mean baseline, batch size 3232, 5050 policy updates, learning rate 0.10.1, dropout 0.30.3, and edge-count sparsity coefficient λsp=0.1 _sp=0.1. The policy architecture is kept fixed: a one-layer, one-head transformer encoder followed by the ℋℋ⊤HH edge construction described in Section 3. We consider single-agent system, chain-of-thought (CoT) (Wei et al., 2022), self-consistency (Wang et al., 2023), SelfOrg⋆111SelfOrg⋆ indicates SelfOrg with a single sequential communication round. (Tastan et al., 2026), and topology-learning or pruning methods, including GPTSwarm (Zhuge et al., 2024), AgentPrune (Zhang et al., 2025a), and G-Designer (Zhang et al., 2025b) as baselines. While the primary metric is accuracy of the final response, we also report the mean edge count and token consumption usage as proxies for the communication burden and inference cost, respectively. 4.2 Main Results Table 1 reports the main comparison across AQUA-RAT (Ling et al., 2017), HumanEval (Chen et al., 2021), and GSM8K (Cobbe et al., 2021). Nexa achieves the best average accuracy, 60.90%60.90\%, improving over SelfOrg⋆ while also obtaining the best average rating. Its gains are strongest on AQUA-RAT and GSM8K while remaining competitive on HumanEval. Table 1: Main comparison across AQUA-RAT, HumanEval, and GSM8K. Accuracy is reported as mean ± std over runs. Rating uses average rating only. Token usage is total prompt plus completion tokens. Lower average rating and lower token usage are better. Method AQUA-RAT HumanEval GSM8K Avg. Acc. Avg. Rating Token Usage Single 52.62±0.9952.62±0.99 50.41±3.7350.41±3.73 70.07±1.3070.07±1.30 57.70±2.0157.70±2.01 5.675.67 !100!toklow1,149,3211,149,321 CoT 54.46±1.9454.46±1.94 45.93±1.2745.93±1.27 70.47±1.0370.47±1.03 56.95±1.4156.95±1.41 5.335.33 !100!toklow1,298,4711,298,471 SC 56.82±2.2756.82±2.27 12.52±3.4112.52±3.41 71.53±0.9071.53±0.90 46.96±2.2046.96±2.20 5.005.00 !78!toklow11,215,15311,215,153 SelfOrg⋆ 56.46±1.2856.46±1.28 52.03±2.4452.03 2.44 72.60±0.60¯ 72.60±0.60 60.36±1.44¯ 60.36±1.44 2.67¯ 2.67 !26!toklow28,405,94128,405,941 GPTSwarm 55.91±1.9755.91±1.97 36.79±1.9636.79±1.96 69.33±2.6169.33±2.61 54.01±2.1854.01±2.18 6.336.33 !0!toklow38,021,21338,021,213 AgentPrune 57.58±2.84¯ 57.58±2.84 29.47±0.9329.47±0.93 71.07±1.9471.07±1.94 52.71±1.9052.71±1.90 4.004.00 !18!toklow31,444,70931,444,709 GDesigner 57.13±1.7457.13±1.74 28.25±1.5428.25±1.54 70.00±1.0670.00±1.06 51.79±1.4451.79±1.44 5.675.67 !17!toklow31,798,54031,798,540 Nexa 57.74±2.3157.74 2.31 51.42±0.70¯ 51.42±0.70 73.53±0.2373.53 0.23 60.90±1.0860.90 1.08 1.331.33 !67!toklow18,363,82518,363,825 Figure 1: Accuracy-cost tradeoff for multi-agent system baselines across three tasks. Each point corresponds to one method, with the x-axis showing total token usage including prompt and completion tokens and the y-axis showing mean accuracy. The efficiency results are central to the comparison. Nexa uses 18.3618.36M total tokens, compared with 28.4128.41M for SelfOrg∗, 38.0238.02M for GPTSwarm, 31.4431.44M for AgentPrune, and 31.8031.80M for GDesigner. It therefore reduces token usage by about 35%35\% relative to SelfOrg∗ and by more than 50%50\% relative to GPTSwarm, while achieving the highest average accuracy. Figure 1 makes this tradeoff explicit: in the average panel, Nexa occupies the favorable region of the accuracy-cost plane, indicating that its improvements are not simply the result of spending more tokens but of selectively invoking communication when the response pool warrants it. 4.3 Generalizability Across Different Axes Number of agents. Figure 2: Agent-count transfer for Nexa. The policy is trained with N=10N=10 Qwen2.5-1.5B agents and evaluated without retraining at N∈5,…,20N∈\5,…,20\. We first examine generalizability across the number of agents. Nexa is trained with N=10N=10 agents and evaluated without retraining for N∈5,10,15,20N∈\5,10,15,20\, keeping the task and agent backbone fixed. This setting tests whether the learned graph policy behaves as a reusable response-conditioned rule rather than as a memorized topology for a fixed team size. As shown in Figure 2, Nexa remains above the single-call and chain-of-thought baselines (Wei et al., 2022) for all tested values of N on both AQUA-RAT and GSM8K. Accuracy peaks at N=15N=15 for both tasks, suggesting that the policy can benefit from additional candidate responses beyond the training configuration while still remaining stable when the team size is smaller or larger than N=10N=10. Task transfer. We next consider generalizability across tasks while keeping the model family, model size, and training team size fixed. Nexa is trained with N=10N=10 Qwen2.5-1.5B agents on either AQUA-RAT or GSM8K, then evaluated without retraining on both tasks. Figure 3 compares same-task training against cross-task training at two tested team sizes, N=5N=5 and N=20N=20. Across all four settings, the transfer gap remains small: 0.180.18 and 0.140.14 points on AQUA-RAT, and 0.080.08 and 0.050.05 points on GSM8K. This suggests that Nexa may learn a reusable response-conditioned rule rather than merely memorizing a task-specific pattern, although this requires further confirmation under more heterogeneous model families and agent pools. Figure 3: Task-transfer comparison for Nexa on Qwen2.5-1.5B. Model scale generalizability. We then evaluate whether the learned communication policy transfers across model scales. Nexa is trained using Qwen2.5-1.5B agents and evaluated without retraining on Qwen2.5-7B agents, then compared against a policy trained directly with Qwen2.5-7B agents. As shown in Figure 4, the 1.5B-trained policy closely matches the 7B-trained policy on both tasks: 90.4890.48 versus 90.5290.52 on GSM8K, and 76.9876.98 versus 77.4077.40 on AQUA-RAT. This suggests that the learned graph policy is not tightly coupled to the competence level of the training backbone and can be reused when deployed with a stronger model. Figure 4: Model-scale transfer for Nexa. Model generation transfer. Finally, we evaluate whether the learned communication policy remains usable when the underlying model is updated to a newer generation. Nexa trained on Qwen2.5-1.5B is evaluated without retraining on Qwen3.5-2B (Qwen Team, 2026) and compared against a policy trained directly on Qwen3.5-2B. At N=5N=5, the transferred policy reaches 77.4077.40, compared with 77.7377.73 for the target-generation policy. The resulting 0.170.17-point gap suggests that an existing policy can remain effective after a model upgrade, reducing the need to retrain the communication controller every time the base model is changed. 4.4 How Communication Changes Answers Figure 5: Model-generation transfer for Nexa. We further analyze how Nexa changes answers after communication by decomposing each example according to whether the initial draft (parallel execution responses) and final answer (sequential execution responses) are correct. Figure 6 reports rescue, harm, and preservation rates for Qwen2.5-7B agents on GSM8K. As the tested team size increases from N=5N=5 to N=20N=20, the rescue rate rises from 19.2%19.2\% to 23.8%23.8\%, showing that additional agents provide useful opportunities for correcting initially wrong answers. At the same time, harm remains low, between 1.6%1.6\% and 2.5%2.5\%, while preservation stays above 97.5%97.5\% across all tested values of N. These results suggest that Nexa does not simply perturb answers through extra communication; it mostly preserves correct predictions while selectively improving initially incorrect ones. Additional sparsity diagnostics in Appendix D show that Nexa often selects low-edge communication plans, indicating that the learned policy does not rely on dense all-to-all interaction as team size increases. Figure 6: Policy behavior analysis for Nexa with Qwen2.5-7B agents on GSM8K. Rescue, harm, and preservation rates compare initial draft correctness with final answer correctness after communication. 4.5 Ablations Policy backbone. Table 2: Backbone ablation on GSM8K with Qwen2.5-1.5B agents. Accuracy is mean ± std. over three runs. (Backbone) =N=5 =N=10 Nexa (Transformer) 72.53±1.1772.53±1.17 75.00±0.3575.00±0.35 Nexa (GNN) 72.47±1.6872.47±1.68 74.87±1.2774.87±1.27 Nexa is not tied to a single policy-network backbone. Although our main implementation uses a Transformer to predict response-conditioned communication graphs, the same formulation can be instantiated with other graph-prediction architectures. As one example, we adapt the GNN architecture from GDesigner, originally used for agent-role-specific (and fixed-agent-number) design, to Nexa’s response-conditioned communication graph prediction setting while keeping the rest of the training and communication procedure unchanged. Table 2 shows that this GNN backbone closely matches the Transformer backbone on GSM8K with Qwen2.5-1.5B agents, suggesting that the core benefit comes from the Nexa formulation rather than a specific neural backbone. Policy optimization. Table 3: Policy-optimization ablation on AQUA-RAT with N=5N=5 Qwen2.5-1.5B agents. AQUA→ GSM8K→ GRPO 57.56±3.8357.56± 3.83 57.48±2.3057.48± 2.30 PG 57.74±2.3157.74± 2.31 57.56±1.4957.56± 1.49 We also compare the policy-gradient objective used in Nexa with a GRPO-style alternative. The ablation is conducted on AQUA-RAT with Qwen2.5-1.5B agents at N=5N=5, considering both same-task training and cross-task transfer from GSM8K. As shown in Table 3, PG slightly outperforms GRPO in both settings, with 57.7457.74 versus 57.5657.56 for AQUA→ and 57.5657.56 versus 57.4857.48 for GSM8K→ . The gaps are small, indicating that the learned communication policy is not highly sensitive. 5 Related Works LLM-based multi-agent collaboration. Multi-agent LLM systems have been studied as role-based societies, conversational workflows, and dynamically routed agent networks. CAMEL instantiates role-playing agents for cooperative problem solving (Li et al., 2023), ChatDev organizes specialized agents into staged communicative workflows (Qian et al., 2024), AutoGen provides a general framework for multi-agent conversations (Wu et al., 2024), and AgentVerse studies collaborative behaviors across agent groups (Chen et al., 2024). DyLAN adapts the active agent set during task solving (Liu et al., 2024), while multi-agent debate methods use disagreement to improve reasoning or factuality (Du et al., 2023; Liang et al., 2024). Multiagent finetuning further studies whether diverse reasoning chains can improve a base model through self-improvement (Subramaniam et al., 2025). These systems show that collaboration can improve reasoning, but they typically require a chosen communication protocol, a task-specific workflow, or an explicit judging mechanism. Nexa instead begins with independent responses and learns whether any sequential communication should occur at all. Communication topology and workflow design. Several recent methods treat agent orchestration as a graph or workflow optimization problem. GPTSwarm represents language agents as optimizable computational graphs (Zhuge et al., 2024); AgentPrune removes unnecessary communication to reduce costs (Zhang et al., 2025a); G-Designer learns communication topologies with graph neural networks (Zhang et al., 2025b); and MacNet studies scaling laws for LLM-based multi-agent collaboration (Qian et al., 2025). Related work also explores training LLMs to construct multi-agent systems (Ye et al., 2025c), automated agentic workflow generation (Hu et al., 2025; Zhang et al., 2025c), decentralized evolutionary coordination (Yang et al., 2025), self-evolving agent profiles (Lu et al., 2024), heterogeneous multi-agent systems (Ye et al., 2025b), and unified experimental platforms for multi-agent evaluation (Ye et al., 2025a). Nexa is closest in spirit to graph-based topology learning but differs in three ways: the graph is conditioned on the realized response pool rather than only on a task or role template; the empty graph is a valid decision corresponding to pure parallel execution; and sparsity is controlled directly through an edge-count penalty in the task reward. Judge-free aggregation and acyclicity. Response selection and ensemble fusion are often performed by majority voting, learned rankers, or generative fusion models such as LLM-Blender (Jiang et al., 2023); other systems introduce credibility scores or adversary-resistant judges (Ebrahimi et al., 2025). SelfOrg takes a different route by estimating response contribution from semantic embeddings and using that signal to organize communication without an external judge (Tastan et al., 2026). Its contribution score is motivated by Shapley-style valuation (Shapley, 1953; Tastan et al., 2025) and can be computed from sentence embeddings (Reimers and Gurevych, 2019). Nexa keeps this judge-free contribution ordering but replaces the stochastic self-organization rule with a trainable structure policy. The method, therefore, preserves the stable ordering principle of SelfOrg while learning the forward edges that determine whether and where refinement should happen. 6 Conclusion We introduced Nexa, a response-conditioned policy that bridges parallel and sequential multi-agent execution by learning sparse acyclic communication graphs from initial agent drafts. The method remains lightweight and judge-free, can reduce to pure parallel execution, and improves the accuracy-cost tradeoff while transferring across tasks, agent counts, and model settings. References D. Chen, Q. Yu, P. Wang, W. Zhang, B. Tang, F. Xiong, X. Li, M. Yang, and Z. Li (2025) XVerify: efficient answer verifier for reasoning model evaluations. External Links: 2504.10481, Link Cited by: §3.5. 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 (2021) Evaluating large language models trained on code. CoRR abs/2107.03374. External Links: Link, 2107.03374 Cited by: §F.1, §4.2. W. Chen, Y. Su, J. Zuo, C. Yang, C. Yuan, C. Chan, H. Yu, Y. Lu, Y. Hung, C. Qian, Y. Qin, X. Cong, R. Xie, Z. Liu, M. Sun, and J. Zhou (2024) AgentVerse: facilitating multi-agent collaboration and exploring emergent behaviors. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §5. K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. (2021) Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §4.1, §4.2. Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch (2023) Improving factuality and reasoning in language models through multiagent debate. In Forty-first International Conference on Machine Learning, Cited by: §5. S. Ebrahimi, M. Dehghankar, and A. Asudeh (2025) An adversary-resistant multi-agent llm system via credibility scoring. arXiv preprint arXiv:2505.24239. Cited by: §5. L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig (2023) PAL: program-aided language models. In Proceedings of the 40th International Conference on Machine LearningProceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)First Conference on Language ModelingThe Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks TrackThe Eleventh International Conference on Learning RepresentationsThe Thirty-ninth Annual Conference on Neural Information Processing SystemsAdvances in Neural Information Processing Systems, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, J. Scarlett, R. Barzilay, M. Kan, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Proceedings of Machine Learning Research, Vol. 20230, p. 10764–10799. External Links: Link Cited by: §F.1. D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt (2021) Measuring mathematical problem solving with the MATH dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), External Links: Link Cited by: §F.1. S. Hu, C. Lu, and J. Clune (2025) Automated design of agentic systems. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §5. D. Jiang, X. Ren, and B. Y. Lin (2023) LLM-blender: ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), A. Rogers, J. Boyd-Graber, and N. Okazaki (Eds.), Toronto, Canada, p. 14165–14178. External Links: Link, Document Cited by: §1, §5. G. Li, H. A. A. K. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem (2023) CAMEL: communicative agents for ”mind” exploration of large language model society. In Thirty-seventh Conference on Neural Information Processing Systems, External Links: Link Cited by: §5. T. Liang, Z. He, W. Jiao, X. Wang, Y. Wang, R. Wang, Y. Yang, S. Shi, and Z. Tu (2024) Encouraging divergent thinking in large language models through multi-agent debate. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 17889–17904. External Links: Link, Document Cited by: §5. W. Ling, D. Yogatama, C. Dyer, and P. Blunsom (2017) Program induction by rationale generation: learning to solve and explain algebraic word problems. Vancouver, Canada, p. 158–167. External Links: Link, Document Cited by: §4.1, §4.2. Z. Liu, Y. Zhang, P. Li, Y. Liu, and D. Yang (2024) A dynamic LLM-powered agent network for task-oriented agent collaboration. In First Conference on Language Modeling, External Links: Link Cited by: §5. S. Lu, J. Shao, B. Luo, and T. Lin (2024) Morphagent: empowering agents through self-evolving profiles and decentralized collaboration. arXiv preprint arXiv:2410.15048. Cited by: §5. 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 (2024) 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: §5. C. Qian, Z. Xie, Y. Wang, W. Liu, K. Zhu, H. Xia, Y. Dang, Z. Du, W. Chen, C. Yang, Z. Liu, and M. Sun (2025) Scaling large language model-based multi-agent collaboration. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1, §5. Qwen, :, A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu (2025) Qwen2.5 technical report. External Links: 2412.15115, Link Cited by: §4.1. Qwen Team (2026) Qwen3.5: towards native multimodal agents. External Links: Link Cited by: §4.3. N. Reimers and I. Gurevych (2019) Sentence-bert: sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, External Links: Link Cited by: §2, §5. L. S. Shapley (1953) A value for n-person games. In Contributions to the Theory of Games I, H. W. Kuhn and A. W. Tucker (Eds.), p. 307–317. Cited by: §2, §5. V. Subramaniam, Y. Du, J. B. Tenenbaum, A. Torralba, S. Li, and I. Mordatch (2025) Multiagent finetuning: self improvement with diverse reasoning chains. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §5. N. Tastan, S. Horváth, and K. Nandakumar (2025) Aequa: Fair Model Rewards in Collaborative Learning via Slimmable Networks. In Proceedings of the 42nd International Conference on Machine Learning, A. Singh, M. Fazel, D. Hsu, S. Lacoste-Julien, F. Berkenkamp, T. Maharaj, K. Wagstaff, and J. Zhu (Eds.), Proceedings of Machine Learning Research, Vol. 267, p. 59210–59236. External Links: Link Cited by: §5. N. Tastan, S. Horváth, and K. Nandakumar (2026) Stochastic self-organization in multi-agent systems. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix A, §2, §2, §3.4, §4.1, §5. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin (2017) Attention is all you need. p. . External Links: Link Cited by: §3.3. X. Wang, J. Wei, D. Schuurmans, Q. V. Le, E. H. Chi, S. Narang, A. Chowdhery, and D. Zhou (2023) Self-consistency improves chain of thought reasoning in language models. External Links: Link Cited by: §1, §4.1. J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35, p. 24824–24837. Cited by: §4.1, §4.3. Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, A. H. Awadallah, R. W. White, D. Burger, and C. Wang (2024) AutoGen: enabling next-gen LLM applications via multi-agent conversations. In First Conference on Language Modeling, External Links: Link Cited by: §5. Y. Yang, H. Chai, S. Shao, Y. Song, S. Qi, R. Rui, and W. Zhang (2025) AgentNet: decentralized evolutionary coordination for LLM-based multi-agent systems. External Links: Link Cited by: §5. R. Ye, K. Huang, Q. Wu, Y. Cai, T. Jin, X. Pang, X. Liu, J. Su, C. Qian, B. Tang, et al. (2025a) MASLab: a unified and comprehensive codebase for llm-based multi-agent systems. arXiv preprint arXiv:2505.16988. Cited by: §5. R. Ye, X. Liu, Q. Wu, X. Pang, Z. Yin, L. Bai, and S. Chen (2025b) X-mas: towards building multi-agent systems with heterogeneous llms. arXiv preprint arXiv:2505.16997. Cited by: §5. R. Ye, S. Tang, R. Ge, Y. Du, Z. Yin, S. Chen, and J. Shao (2025c) MAS-GPT: training LLMs to build LLM-based multi-agent systems. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §5. G. Zhang, Y. Yue, Z. Li, S. Yun, G. Wan, K. Wang, D. Cheng, J. X. Yu, and T. Chen (2025a) 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: §3.5, §4.1, §5. G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng (2025b) 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, §4.1, §5. J. Zhang, J. Xiang, Z. Yu, F. Teng, X. Chen, J. Chen, M. Zhuge, X. Cheng, S. Hong, J. Wang, B. Zheng, B. Liu, Y. Luo, and C. Wu (2025c) AFlow: automating agentic workflow generation. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §5. M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber (2024) GPTSwarm: language agents as optimizable graphs. In Proceedings of the 41st International Conference on Machine Learning, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp (Eds.), Proceedings of Machine Learning Research, Vol. 235, p. 62743–62767. External Links: Link Cited by: §1, §4.1, §5. Appendix A Limitations Nexa is evaluated primarily on reasoning and programming benchmarks where answer correctness can be measured reliably. This focus allows controlled comparisons across task, agent count, model scale, and model generation, but leaves broader open-ended settings such as long-form generation, interactive tool use, and multi-turn planning as natural directions for future evaluation. The method also depends on response embeddings. If the embedding model fails to capture task-relevant differences between candidate answers, the contribution ordering and graph policy may miss useful communication paths. For the goodness of the selected embedding model, we refer the reader to [Tastan et al., 2026]. Finally, Nexa deliberately uses one parallel draft round as the evidence-gathering stage for deciding whether communication is needed. This makes the sequential part selective and often sparse, but it also means that the initial agent pool size remains an important efficiency knob. Future extensions could combine Nexa with adaptive agent selection so that both the number of initial drafts and the communication graph are chosen instance by instance. Appendix B Algorithm Algorithm 1 Nexa 1:Query Q, agents nn=1N\A_n\_n=1^N, encoder f, policy pθ(ℰ∣,π)p_θ(E X,π) 2:for n=1n=1 to N do 3: ℛn(0)←n()R_n^(0)←A_n(Q), rn←f(ℛn(0))r_n← f(R_n^(0)) 4:end for 5:ravg←1N∑nrnr_ avg← 1N _nr_n, ψn←cos(rn,ravg) _n← (r_n,r_ avg) 6:π←argsort(ψnn=1N;desc)π (\ _n\_n=1^N;desc) 7:←[r1,…,rN]⊤X←[r_1,…,r_N] , ℋ←Encθ()H _θ(X) 8:Compute masked forward logits ℓm→n _m→ n 9:Sample/decode ℰ∼pθ(⋅∣,π)E p_θ(· X,π) 10:if ℰ=∅E= then return centroid response from ℛn(0)n=1N\R_n^(0)\_n=1^N 11:for each node n in order π do 12: Pa(n)←m:(m→n)∈ℰPa(n)←\m:(m→ n)∈E\ 13: ℛn(1)←n(,ℛm(⋆):m∈Pa(n)),Pa(n)≠∅,ℛn(0),otherwise.R_n^(1)← casesA_n\! (Q,\R_m^( ):m (n)\ ),&Pa(n)≠ ,\\ R_n^(0),&otherwise. cases 14:end for 15:return centroid response from ℛn(1)n=1N\R_n^(1)\_n=1^N Appendix C Policy Behavior with Smaller Agents We observe the same qualitative behavior with Qwen2.5-1.5B agents. As shown in Figure 7, the rescue rate increases from 15.6%15.6\% at N=5N=5 to 20.6%20.6\% at N=20N=20, while the preservation rate remains above 92.8%92.8\% for all tested team sizes. Harm is higher than in the 7B setting (refer to Figure 6), ranging from 5.6%5.6\% to 7.2%7.2\%, which is expected given the weaker base agents. Nevertheless, the policy still improves a meaningful fraction of initially wrong answers while preserving the vast majority of initially correct ones, indicating that the same communication behavior appears even with smaller models. Figure 7: Policy behavior analysis for Nexa with Qwen2.5-1.5B agents on GSM8K. Rescue, harm, and preservation rates are computed by comparing each initial draft answer with the final answer after communication. Nexa rescues 15.6%15.6\%-20.6%20.6\% of initially wrong answers while preserving 92.8%92.8\%-94.4%94.4\% of initially correct answers across tested team sizes. Appendix D Communication Sparsity Figure 8 reports the fraction of low-edge communication plans produced by Nexa on GSM8K. For Qwen2.5-1.5B, low-edge plans occur in 35.0%35.0\% of examples at N=5N=5 and remain near 4747–50%50\% for larger tested team sizes. For Qwen2.5-7B, the fraction increases from 43.4%43.4\% at N=5N=5 to more than 70%70\% at N=15N=15 and N=20N=20. These results suggest that increasing the number of agents does not force dense communication; the learned policy often selects sparse interaction patterns. We also observe that, as we scale the capability of the backbone, it leads to more frequent sparse communication than less capable or weaker backbone, indicating that as individual agents become more capable, the policy can rely on fewer communication edges. Figure 8: Communication sparsity for Nexa on GSM8K with Qwen2.5-1.5B and Qwen2.5-7B agents. We report the fraction of examples whose predicted communication graph uses at most half of the possible edges. Across both model sizes, Nexa frequently selects low-edge plans, indicating that the learned policy does not rely on dense all-to-all communication as team size increases. Appendix E Experimental Settings Compute resources. All experiments were run on NVIDIA A100 40GB GPUs. The same GPU class was used both to serve the LLM agents during multi-agent inference and to train the Nexa policy. Backbone ablation setting. For the policy-backbone ablation, we restrict training to 5 epochs for both the Transformer and GNN variants to keep the comparison controlled and computationally lightweight. Both variants use the same Nexa training objective, the same GSM8K training setting, Qwen2.5-1.5B agents, sampled graph plans at evaluation, temperature 0.50.5, and three random repeats. The only changed component is the policy-network backbone used to score response-conditioned communication graphs. The GNN variant adapts the graph neural architecture from GDesigner from agent-role-specific graph design to Nexa’s response-conditioned graph prediction setting. Policy-optimization ablation setting. For the policy-optimization ablation, we compare the policy-gradient objective used in Nexa against a GRPO-style update. Both use Qwen2.5-1.5B agents, response-only inputs, contribution-based ordering, weighted aggregation, and XVerify-based evaluation at temperature 0.00.0. Evaluation is conducted on AQUA-RAT at N=5N=5 for both same-task training, AQUA-RAT→ -RAT, and cross-task transfer, GSM8K→ -RAT. Both variants use ‘transformer’ backbone, 5050 policy-training iterations, batch size 3232, learning rate 0.10.1, a hidden dimension 128128, 11 transformer layers, 11 attention heads, dropout 0.30.3, Adam optimizer, gradient clipping 1.01.0, and batch-mean baseline. For GRPO, we use 44 rollouts. Appendix F Additional Experiments F.1 Extended Task Transfer We additionally provide studies on whether a policy trained on one source task can transfer to additional target tasks beyond the main transfer experiments. In this setting, Nexa is trained on GSM8K and evaluated without retraining on GSM-Hard [Gao et al., 2023], HumanEval [Chen et al., 2021], and MMLU [Hendrycks et al., 2021]. We compare against single-call and chain-of-thought baselines using the same target-task evaluation protocol. As shown in Table 4, the GSM8K-trained Nexa policy improves over both baselines on GSM-Hard and HumanEval and remains comparable to the baselines on MMLU. These results suggest that the learned communication policy can transfer beyond the training task, especially when the target task benefits from structured multi-agent reasoning. Table 4: Extended task-transfer results. Nexa is trained on GSM8K and evaluated without retraining on GSM-Hard, HumanEval, and MMLU. Accuracy is reported as mean ± standard deviation. Trained on Tested on Single CoT Nexa GSM8K GSM-Hard 34.40±0.7234.40±0.72 36.07±0.3136.07±0.31 37.13±1.2137.13 1.21 HumanEval 50.41±3.7350.41±3.73 45.93±1.2745.93±1.27 51.42±0.7051.42 0.70 MMLU 52.07±1.0352.07 1.03 51.27±1.5051.27±1.50 52.00±1.0652.00±1.06 Avg. Acc. 45.6345.63 44.4244.42 46.8546.85 Avg. Rating 2.002.00 2.672.67 1.331.33