Paper deep dive
Multi-Agent Coordination Adaptation via Structure-Guided Orchestration
Haoran Li, Shulun Chen, Shaoyuan Sun, Hanchen Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 87%
Last extracted: 7/8/2026, 8:27:14 PM
Summary
The paper introduces MACA, a multi-agent coordination framework that reformulates coordination as posterior inference over structural and orchestration variables. By learning a task- and budget-conditioned structural prior (GraphSpec) to guide token-aware orchestration, MACA suppresses redundant interactions and outperforms adaptive baselines by 8.42% while reducing token consumption by 43.19%.
Entities (11)
Relation Signals (10)
MACA → uses → GraphSpec
confidence 95% · MACA learns a task- and budget-conditioned structural prior over agent participation and interactions.
MACA → evaluatedon → LLaMA-3.1-8B
confidence 90% · Performance comparison of baseline methods on Llama-3.1-8B.
MACA → implements → Token-Aware Orchestration
confidence 90% · MACA performs orchestration within the constrained space using a policy-based approach.
MACA → outperforms → LLM-based Multi-Agent Systems
confidence 90% · Across benchmarks, MACA outperforms adaptive multi-agent baselines by an average of 8.42% while using 43.19% fewer tokens.
MACA → casts → Posterior Inference
confidence 85% · We revisit multi-agent coordination from a probabilistic perspective, casting it as posterior inference over the joint distribution of structure and orchestration.
GraphSpec → comprises → Interaction Plausibility Estimation
confidence 85% · GraphSpec models coordination uncertainty by jointly inferring Agent Relevance and Interaction Plausibility.
GraphSpec → comprises → Agent Relevance Scoring
confidence 85% · GraphSpec models coordination uncertainty by jointly inferring Agent Relevance and Interaction Plausibility.
Structure-Centric Adaptation → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:As large language model (LLM)-based multi-agent systems scale to handle increasingly complex tasks, balancing structural stability and dynamic adaptability becomes increasingly challenging. Existing systems typically adopt either structure-centric methods, committing to structures determined upfront that limit fine-grained control, or orchestration-centric methods, adapting decisions dynamically while leaving coordination structure implicit and unstable. To address this challenge, we revisit multi-agent coordination from a probabilistic perspective, casting it as posterior inference over the joint distribution of structure and orchestration. We introduce MACA, an automated coordination framework that learns a task- and budget-conditioned structural prior over agent participation and interactions. This prior guides a policy-based orchestration as an approximation to posterior inference, enabling efficient solutions with fine-grained control. Across benchmarks, MACA outperforms adaptive multi-agent baselines by an average of 8.42% while using 43.19% fewer tokens. Further investigation reveals that joint adaptation of structure and orchestration suppresses redundant interactions, converging coordination toward task-effective execution.
Tags
Links
- Source: https://arxiv.org/abs/2605.25746v1
- Canonical: https://arxiv.org/abs/2605.25746v1
Trouble viewing inline? Open PDF directly →
Full Text
76,532 characters extracted from source content.
Expand or collapse full text
Multi-Agent Coordination Adaptation via Structure-Guided Orchestration Haoran Li1,*, Shulun Chen2,*,†, Shaoyuan Sun3, Hanchen Wang2 1Nanjing University 2University of Technology Sydney, Sydney, Australia 3University of New South Wales, Sydney, Australia Abstract As large language model (LLM)-based multi-agent systems scale to handle increasingly complex tasks, balancing structural stability and dynamic adaptability becomes increasingly challenging. Existing systems typically adopt either structure-centric methods, committing to structures determined upfront that limit fine-grained control, or orchestration-centric methods, adapting decisions dynamically while leaving coordination structure implicit and unstable. To address this challenge, we revisit multi-agent coordination from a probabilistic perspective, casting it as posterior inference over the joint distribution of structure and orchestration. We introduce MACA, an automated coordination framework that learns a task- and budget-conditioned structural prior over agent participation and interactions. This prior guides a policy-based orchestration as an approximation to posterior inference, enabling efficient solutions with fine-grained control. Across benchmarks, MACA outperforms adaptive multi-agent baselines by an average of 8.42% while using 43.19% fewer tokens. Further investigation reveals that joint adaptation of structure and orchestration suppresses redundant interactions, converging coordination toward task-effective execution. The code is available at: https://github.com/However-Li/MACA. Multi-Agent Coordination Adaptation via Structure-Guided Orchestration Haoran Li1,*, Shulun Chen2,*,†, Shaoyuan Sun3, Hanchen Wang2 1Nanjing University 2University of Technology Sydney, Sydney, Australia 3University of New South Wales, Sydney, Australia 11footnotetext: Equal Contribution.22footnotetext: Corresponding Author: Shulun.Chen@student.uts.edu.au 1 Introduction In an era marked by the maturation of foundation models Tu et al. (2024), computational resources Burns et al. (2016), and low-latency communication Adhikari and Hazra (2022), machine cognition is undergoing a paradigm shift from isolated computation to collective intelligence. As Minsky envisioned in Society of Mind Minsky (1986), intelligence arises from the interplay of simple agents, and this vision now unfolds at scale. Within this context, LLM-based multi-agent systems He et al. (2025); Li et al. (2024); Cheng et al. (2024) focus on harnessing collective intelligence through coordinated reasoning and organization to address increasingly complex challenges that transcend individual capability. Such LLM-based multi-agent systems have been demonstrated to be effective across a broad range of application domains, including question answering Chen et al. (2025); Zhu et al. (2024); Zhang et al. (2024d), software development Zhang et al. (2024c); Wang et al. (2025c), and data analysis Xiao et al. (2024); Rasheed et al. (2024); Wang et al. (2025b), where structure and orchestration become critical for effective problem solving Wu et al. (2023). Early approaches to LLM-based multi-agent coordination, such as ChatDev Qian et al. (2024a), MetaGPT Hong et al. (2023), and AgentVerse Chen et al. (2024), typically rely on hand-crafted topologies and fixed interaction orders Guo et al. (2024). While effective at encoding domain-specific structure Yang et al. (2025a) and enabling role-level functional specialization Lin et al. (2025); Naik et al. (2025), such designs rely heavily on manually engineered agent or coordination rules Tang et al. (2024), and typically assume a fixed collaboration structure shared across tasks, prompting efforts for autonomous multi-agent systems. Zhang et al. (2024a) and Talebirad and Nadiri (2023) have formalized multi-agent systems as computational graphs, enabling structural and communication optimization. Methods such as GPTSwarm Zhuge et al. (2024) and G-Designer Zhang et al. (2024b) investigate learning adaptive communication structures or interaction patterns to reduce redundancy. A closer examination of recent autonomous mechanisms reveals two predominant paradigms, as illustrated in Figure 1: (I) Structure-Centric Adaptation: Given a query, the system adapts the multi-agent topology either by explicitly inferring a task-specific interaction structure Zhang et al. (2025a); Yuan et al. (2025); Shang et al. (2024), or by refining a pre-defined structure via agent generation Tian et al. (2025), agent selection Zhang et al. (2024b), agent dropout Wang et al. (2025d), and communication pruning Zhang et al. (2024a). Since the system commits to a query-conditioned interaction structure prior to execution, it implicitly assumes that coordination efficiency is largely determined by this structural choice, leaving limited capacity for dynamic adaptation as task states evolve. (I) Orchestration-Centric Adaptation: Such methods adapt system behavior through sequential decision making, typically by selecting the next agent(s) at each step. Some works rely on heuristic or rule-based strategies Rasal and Hauer (2024); Rasal (2024); Qayyum et al. (2025), while more recent methods formulate orchestration as an optimization problem, leveraging reinforcement learning (RL) Sun et al. (2024); Dang et al. (2025); Zhang et al. (2025b); Liu et al. (2025) to optimize coordination policies. Despite their practical effectiveness, the absence of explicit interaction modeling induces role drift and high-variance credit assignment under increasing task complexity. Figure 1: (a) Structure-centric methods fix a topology before inference, limiting adaptation as task states evolve. (b) Orchestration-centric methods offer step-by-step adaptability without a predefined structure, but incur high-variance coordination as scale increases. (c) Our method bridges these two paradigms by guiding adaptive orchestration with an explicit structural prior, achieving both stability and flexibility. Revisiting these paradigms reveals a fundamental limitation of current adaptive multi-agent systems: coordination is frequently treated as a single, monolithic process. While Yang et al. (2025a) highlight the role of topological structure as a primary research objective and Bhatt et al. (2025) further investigate when orchestration is necessary, the separation between structure and orchestration prevents the system from jointly reasoning about how coordination should be organized and evolve over time, rendering coordination brittle and inefficient under scaling complexity Cemri et al. (2025); Zhang et al. (2025c). Moreover, resource budgets (e.g., token limits) do not merely act as external constraints, but fundamentally shape the feasible coordination space and its inherent performance trade-offs. Ignoring these signals during either structural formulation or dynamic orchestration leads to unstable learning dynamics. To address the above challenges, we propose a Multi-Agent Coordination Adaptation Framework (MACA) that casts multi-agent coordination as a posterior inference problem, where structural priors define a constrained interaction space and orchestration policies optimize within it. Specifically, our framework advances multi-agent coordination through two key innovations: (I) Structural Prior Learning. MACA models the structural prior as a task- and budget-conditioned variable by jointly estimating agent relevance and interaction plausibility. This process infers a probabilistic interaction graph that constrains agent participation and information flow, thereby yielding a principled foundation for downstream orchestration. (I) Token-Aware Orchestration. Given the inferred structure, MACA performs orchestration within the constrained space. The orchestration policy operates over a reduced space, where structural priors act as constraints through reward modulation, enabling flexible adaptation as task states evolve while maintaining scalability and efficiency. Figure 2: The overall framework of MACA. It consists of three main components: (a) Structural Prior Learning, (b) Token-Aware Orchestration, and (c) the overall pipeline for a given task. Our contributions are summarized as follows: • We are the first to cast multi-agent optimization as posterior inference over structural and orchestration variables. This elevates adaptive coordination from architecture selection or sampling to a principled probabilistic formulation. • We introduce a novel and adaptive inference framework MACA, which learns a structural prior, subsequently optimizing orchestration within the generated prior to enable fine-grained and resource-efficient coordination. • Extensive experiments across six benchmarks show that MACA yields robust and efficient coordination, surpassing adaptive multi-agent baselines with an average 8.42% performance boost and a 43.19% token reduction, thus achieving stronger task generalization and budget stability. 2 Methodology Figure 2 provides an overview of our proposed Multi-Agent Coordination Adaptation framework, namely MACA. We construct a structural prior from a space of agent compositions and interaction patterns. Building upon this prior, MACA approximates posterior inference over coordination decisions via reinforcement learning. The model leverages orchestration feedback to progressively refine system behaviors. In the following sections, Section 2.1 formally defines the coordination formulation and optimization objective of our framework, Section 2.2 presents the construction of structural prior, and Section 2.3 details the token-aware orchestration for adaptive multi-agent systems. 2.1 Preliminaries (a) System Definition. We introduce the first unified definition for LLM-based multi-agent coordination systems, formulated as ℳ=,M=\G,T\, where coordination is characterized by structure G and orchestration T. Specifically, the structure is defined as a directed graph =(,ℰ),G=(V,E), where ⊆V is a subset of a universal agent set O, each node vi∈v_i represents an agent as in previous practices Zhang et al. (2024a). ℰ⊆×E ×V specifies admissible interaction relations among agents, each edge eij∈ℰe_ij characterizes the potential for interaction from agent viv_i to agent vjv_j, thereby defining a structured interaction space for downstream orchestration. The process T represents an ordered sequence of orchestration decisions. A particular realization τ can be modeled as a state-action trajectory τ=(s0,a0,s1,a1,…,sT)τ=(s_0,a_0,s_1,a_1,…,s_T), where each state sts_t summarizes the coordination context at step t, including the task input, intermediate agent outputs, and available resource signals. Each action ata_t corresponds to an orchestration decision, such as selecting a subset of agents to invoke, routing information among agents, or terminating execution. The action selection process is guided by the structure G, i.e., at∼π(⋅∣st;G)a_t π(· s_t;G). (b) Posterior Coordination. We refine the coordination mechanism to a posterior inference problem. Rather than treating the structure G and the orchestration T as fixed design choices, we model them as random variables that govern the solution process. Given a task instance x and a resource budget b, we model a hierarchical dependency. A structure G is first drawn from a task- and budget-conditioned structural space. This structure constrains the distribution of the execution orchestration τ. The resulting orchestration then determines the fidelity of producing the optimal output y⋆y . Accordingly, coordination reduces to finding the joint posterior over structure and trajectory that best explains y⋆y : p(G,τ∣x,b,y⋆) p(G,τ x,b,y ) (1) ∝ \; p(y⋆∣τ,x)⏟Output Fidelity⋅p(τ∣G,x,b)⏟Orchestration⋅p(G∣x,b)⏟Structural Prior p(y τ,x)_ Output Fidelity· p(τ G,x,b)_ Orchestration· p(G x,b)_ Structural Prior The posterior factorizes into (I) a structural prior p(G∣x,b)p(G x,b) that assigns probability to valid agent topologies under the given conditions, (I) an orchestration p(τ∣G,x,b)p(τ G,x,b) capturing how execution evolves within the structural constraints, and (I) output fidelity p(y⋆∣τ,x)p(y τ,x) that measures how likely an orchestration yields the optimal solution. (c) Problem Formulation. To compute the intractable posterior in Eq. 1 and thereby infer the joint distribution of structure G and orchestration τ, we adopt variational inference Levine (2018) to approximate the target distribution p(G,τ∣x,b,y⋆)p(G,τ x,b,y ) with a parameterized generative policy πθ(G,τ∣x,b) _θ(G,τ x,b). Specifically, the Kullback-Leibler (KL) divergence between the variational distribution and the target posterior is defined as follows: DKL(πθ∥p) D_KL( _θ p) (2) =(G,τ)∼πθ =E_(G,τ) _θ [logπθ(G,τ∣x,b)−logp(G,τ∣x,b,y⋆)] [ _θ(G,τ x,b)- p(G,τ x,b,y ) ] By minimizing the KL divergence, the inference process can be formulated into an optimization problem. We define a utility function U(τ,y)=logp(y∣τ,x)U(τ,y)= p(y τ,x), representing the log-likelihood of the ground truth outcome with given orchestration and task instance. Assuming a fixed budget constraint implicit in the structural prior, the minimization of the KL divergence is mathematically equivalent to maximizing the evidence lower bound (ELBO), which yields the optimization objective: maxθτ∼πθ,G[U(τ,y⋆)+α⋅Ω(πθ∣G,x,b)] _θ\;E_τ _θ,G [U(τ,y )+α· ( _θ G,x,b) ] (3) where the regularization term Ω(πθ∣G,x,b) ( _θ G,x,b) encodes an objective that constrains the orchestration policy to remain aligned with the structural prior under the task input x and budget b. The coefficient α∈[0,1]α∈[0,1] controls the trade-off between maximizing task utility and enforcing structural consistency. 2.2 Structural Prior Learning Inspired by the success of learned priors for capturing data-driven regularities Ulyanov et al. (2018); Wang et al. (2025a), we introduce a structural prior termed GraphSpec, which models coordination uncertainty by jointly inferring Agent Relevance and Interaction Plausibility. Agent Relevance Scoring. Agent suitability varies with task semantics and resource budgets. Recent findings Yang et al. (2025b); Wang et al. (2024a) show that complex reasoning benefits from selective agent engagement. Accordingly, agent relevance is estimated by modeling the semantic compatibility between each agent representation and the task–budget context. For each agent vi∈v_i , we introduce a continuous variable zi∈[0,1]z_i∈[0,1] that represents its participation strength in the coordination structure. Let si=cos((x,b),i)s_i=cos~\! (e(x,b),\,e_i ) denote the resulting relevance score, where (x,b)e(x,b) denotes the embedding of the input context and ie_i represents the embedding of agent viv_i, both obtained via a sentence encoder Xiao et al. (2023). cos(⋅,⋅)cos~(·,·) denotes the cosine similarity. We then obtain a participation weight: qi=σ(siβ(b)),zi=qi,qi≥γ,0,qi<γ,q_i=σ\! ( s_iβ(b) ), z_i= casesq_i,&q_i≥γ,\\ 0,&q_i<γ, cases (4) where β(b)β(b) is a budget-dependent temperature. qivi∈\q_i\_v_i represents a continuous score. We apply a thresholded gating operation with parameter γ to suppress low-confidence agents. Agents with qi<γq_i<γ are filtered out, while agents exceeding the threshold retain their participation strength. The resulting Zprior=ziZ_prior=\z_i\ specifies agent relevance. Interaction Plausibility Estimation. We model interaction plausibility as an edge-level prior over directed agent transitions vi→vjv_i→ v_j. Intuitively, interactions that remain consistently effective under stochastic structural variations are more likely to reflect stable coordination patterns and thus should receive higher prior probability. We define a policy πϕ _φ that directly parameterizes graph topology via learnable edge logits ϕ=ℓij∈ℝφ=\ _ij \, which quantify the interaction plausibility between agents. This policy independently samples directed edges eij∼Bernoulli(σ(ℓij))e_ij (σ( _ij)). The parameters ϕφ are optimized by minimizing the following loss function: ℒ(ϕ)=−⋅∑(vi,vj)∈logσ(ℓij)+λℛsL(φ)=-U· _(v_i,v_j) σ( _ij)+ _s (5) where ∈0,1U∈\0,1\\ represents a utility signal. ℛs=1||∑(vi,vj)∈σ(ℓij)R_s= 1|O| _(v_i,v_j) σ( _ij) serves as a regularizer to prevent over-fitting. Subsequently, we maintain a buffer of the high quality interaction trajectories sampled from πϕ _φ, filtering for instances that achieve correct reasoning. These filtered trajectories are used as pseudo-labels to train a Multi-Layer Perceptron (MLP): P(vi→vj|x)=MLPψ([i,j,(x)])P(v_i→ v_j|x)=MLP_ψ([e_i,e_j,e(x)]) (6) The MLP maps the task x to the edge interaction probability for any agent pair (vi,vj)(v_i,v_j). GraphSpec Construction. We synthesize the estimated agent relevance and interaction plausibility into GraphSpec, a unified probabilistic prior that adapts the structure to the task-budget context. We modulate the raw edge probabilities by the participation strengths of the incident nodes. The effective connection probability PpriorP_prior is defined as: p~ij=pij⋅qj,Pprior=[p~ij]∈[0,1]N×N p_ij=p_ij· q_j, P_prior=[ p_ij]∈[0,1]^N× N (7) This modulation suppresses links involving low-confidence agents. The resulting GraphSpec, denoted by (x,b)=(Zprior,Pprior),GS(x,b)=(Z_prior,P_prior), defines a parameterization of the structural prior p(∣x,b)p(G x,b). 2.3 Token-Aware Orchestration The orchestration problem is formulated as a Markov Decision Process (MDP), and the policy is optimized using a GRPO-based method Guo et al. (2025). At each step t, the state st∈s_t encapsulates the task input x, history state hth_t, and budget btb_t. The objective is to learn a policy πθ(at∣st) _θ(a_t s_t) that maximizes the expected return: maxθτ∼πθ[R−α⋅DKL(πθ∥πref)] _θ\;E_τ _θ [R-α· D_KL ( _θ\;\|\; _ref ) ] (8) where R=∑t=1Trt′R= _t=1^Tr_t denotes the total return of trajectory τ, with rt′r_t defined in Eq. (12). πref _ref denotes the frozen reference policy, and α is a trade-off parameter. The policy πθ _θ selects an action ata_t from an action space =∪STOPA=O∪\STOP\. For each task, we sample a group of K trajectories τ(k)k=1K\τ^(k)\_k=1^K using the current policy. Let R(k)R^(k) denote the reward of trajectory k. Group-relative advantages are computed as: A(k)=R(k)−1K∑k′=1KR(k′),A~(k)=A(k)Std(R(k′))+ϵA^(k)=R^(k)- 1K _k =1^KR^(k ), A^(k)= A^(k)Std(\R^(k )\)+ε (9) The overall loss function combines a clipped term Lclip(θ)L_clip(θ) with a KL divergence penalty, denoted as: Lclip(θ) L_clip(θ) =min(ρt(θ)A~,clip(ρt(θ),1−ϵ,1+ϵ)A~), = ( _t(θ) A,clip( _t(θ),1-ε,1+ε) A ), (θ) (θ) =−[1K∑k(Lclip(k)(θ)−α⋅DKL(πθ∥πref))]. =-E [ 1K _k (L_clip^(k)(θ)-α· D_KL ( _θ\,\|\, _ref ) ) ]. (10) where ρt(θ)=exp(logπθ−logπθold) _t(θ)= ( _θ- _ _old) is the likelihood ratio, ϵε is the clipping range. A KL divergence term is introduced to regularize πθ _θ, keeping it close to πref _ref, which balances reward maximization with stability. However, relying solely on standard regularization leaves the vast multi-agent interaction space unconstrained, allowing the policy to waste tokens on spurious interactions. To address this, we introduce a hybrid supervision mechanism that incorporates both hard constraints and soft regularization into the orchestration. We first impose constraints on the action space to filter out structurally implausible interactions. Given the structural mask ℋH, we enforce the validity of the policy πθ _θ by masking out invalid actions. The masked policy distribution is formally defined as: πmasked(at|st)=exp(l(at|st))⋅ℋat∑a′∈exp(l(a′|st))⋅ℋa′ _masked(a_t|s_t)= (l(a_t|s_t))·H_a_t _a (l(a |s_t))·H_a (11) where l(⋅|st)l(·|s_t) denotes the raw logits generated by the policy network. By setting the probability of masked actions to zero, we restrict the policy to a prior-consistent subset of actions, constraining exploration to plausible connections. To prevent the policy from engaging in aimless exploration among valid but low-value interactions, we incorporate the edge probabilities from the prior as a reference distribution πmix=12(πref+πprior) _mix= 12 ( _ref+ _prior ). Here, πprior _prior denotes the prior action distribution induced by GraphSpec. Distinct from GRPO, we leverage a KL penalty that encourages the policy to anchor its exploration around the learned structural prior. The reward function is formulated as: rt′=rt−λ⋅DKL(πθ∥πmix),r_t =r_t-λ· D_KL ( _θ _mix ), (12) where rt=Racc−βCttokenr_t=R_acc-β C_t^token denotes the extrinsic reward, which balances task utility RaccR_acc against token cost CttokenC_t^token through the trade-off parameter β. λ is a regularization coefficient balancing task performance and structural adherence. This soft regularization keeps the policy close to the learned prior, stabilizing the training process in complex scenarios. More details of the training algorithm can be found in Appendix C.6. 3 Experiments Table 1: Performance comparison of baseline methods on Llama-3.1-8B. The best results are shown in bold, and the second-best are underlined. Avg Cost is compared among multi-agent methods to reflect their efficiency. Model: Llama-3.1-8B Structure Adaptation Orchestration Adaptation Code Generation Question Answering Math Reasoning HumanEval MBPP MMLU-Pro ARC-C SVAMP GSM-Hard Acc (%) Avg Cost Acc (%) Avg Cost Acc (%) Avg Cost Acc (%) Avg Cost Acc (%) Avg Cost Acc (%) Avg Cost Vanilla ✗ ✗ 60.61 256.6 45.97 138.4 38.50 246.7 83.09 279.6 82.18 209.6 32.31 345.3 CoT ✗ ✗ 56.44 297.9 44.62 146.1 39.24 379.5 83.17 443.7 82.51 267.8 36.36 387.0 ComplexCoT ✗ ✗ 57.58 1154.4 44.18 247.4 38.54 1304.2 82.18 883.1 86.33 2658.9 32.83 2766.3 Self-Refine ✗ ✗ 62.12 1609.8 47.53 498.7 33.75 1646.5 83.16 1191.4 83.67 1195.3 26.26 2525.5 SC (CoT×5) ✗ ✗ 55.38 2389.6 46.36 1206.9 41.62 2406.9 84.16 1545.0 88.67 1080.7 40.40 1639.8 DyLAN ✗ ✗ 72.73 15256.7 12.50 11647.8 47.26 11874.6 83.33 3471.6 86.33 6675.6 33.63 15338.0 MacNet ✗ ✗ 68.18 8782.6 47.83 6794.8 25.47 10284.4 83.83 3596.3 79.74 6912.6 19.84 12468.3 AgentVerse ✗ ✗ 66.18 6826.9 48.94 5017.5 41.69 6193.2 85.61 3014.9 86.03 4184.7 38.19 6768.4 AgentPrune ✓ ✗ 62.50 2357.0 31.44 2787.8 43.53 2713.6 86.09 2691.3 88.44 2780.8 33.86 3815.8 MaAS ✓ ✗ 65.15 4796.9 42.05 3215.7 43.94 2978.4 43.83 2674.7 92.28 2827.7 51.52 2224.8 Puppeteer ✗ ✓ 71.49 2798.3 47.17 3696.5 51.25 4097.8 85.57 3753.3 94.18 4204.7 49.25 4196.6 MACA (Ours) ✓ ✓ 75.76 2100.1 49.23 2412.3 52.67 2117.8 87.75 1656.3 96.00 2057.2 50.30 1602.5 3.1 Experiment Setup Benchmarks and Metrics. We comprehensively evaluate MACA across six benchmarks spanning three domains. (I) Code generation, HumanEval Chen et al. (2021) and MBPP Austin et al. (2021); (I) Question Answering, MMLU-Pro Wang et al. (2024b) and ARC-C Clark et al. (2018); and (I) Math Reasoning, SVAMP Patel et al. (2021) and GSM-Hard Gao et al. (2022). We evaluate models in terms of Accuracy and Average Cost. Accuracy is computed as 1N∑i=1N(y^i is correct) 1N _i=1^N1( y_i is correct), where correctness follows task-specific criteria (e.g., Pass@1 or Exact Match). Average Cost is measured as 1N∑i=1Nci 1N _i=1^Nc_i, where cic_i denotes the token cost of task i, including both prompt tokens and completion tokens. The dataset statistics are in Appendix C.1. Baselines. We compare MACA against baselines categorized by their coordination and adaptation mechanisms: (I) single-agent methods including CoT Wei et al. (2022), ComplexCoT Fu et al. (2022), Self-refine Madaan et al. (2023), and Self-Consistency Wang et al. (2022). (I) hand-crafted multi-agent systems including DyLAN Liu et al. (2024), AgentVerse Chen et al. (2024), and MacNet Qian et al. (2024b). (I) Adaptive multi-agent systems including AgentPrune Zhang et al. (2024a), MaAS Zhang et al. (2025a) and Puppeteer Dang et al. (2025). Additional details for baselines are provided in Appendix C.2. Table 2: Results on Llama-3.1-70B. The best and runnerup results are bolded and underlined, respectively. Avg Cost is compared among multi-agent methods. Model: Llama-3.1-70B MMLU-Pro HumanEval GSM-Hard Acc (%) Avg Cost Acc (%) Avg Cost Acc (%) Avg Cost Vanilla 53.50 250.6 78.78 239.8 48.87 206.7 CoT 54.25 274.1 80.30 247.1 57.14 292.8 DyLAN 60.09 12068.9 84.25 12984.5 55.05 14186.4 AgentPrune 57.74 3128.7 80.25 3186.9 51.44 4372.5 MaAS 58.74 2868.2 83.33 3758.5 64.03 3125.8 MACA (Ours) 64.57 2438.6 88.89 2672.2 67.37 2747.7 3.2 Performance Comparison MACA consistently outperforms baselines. As shown in Table 1, MACA achieves the highest average accuracy of 68.62% across six benchmarks. Compared to single-agent methods, MACA yields an average accuracy improvement of 9.19%∼12.54%9.19\% 12.54\%. Against adaptive multi-agent baselines, MACA delivers an 8.42% improvement in accuracy while simultaneously reducing token costs by 36.2% to 51.9%. These results confirm the effectiveness and cost-efficiency of MACA. Notably, this advantage remains consistent across model scales, from Llama-3.1-8B to Llama-3.1-70B. RQ1: Can coordination itself induce reasoning capability? At the Llama-3.1-8B scale (Table 1), MACA yields clear gains over single-agent baselines, suggesting that the improvements arise from coordinated interaction. While methods such as CoT Wei et al. (2022) improve reasoning by prompting models to generate explicit step-by-step rationales, they remain bounded by single-model limitations and may reinforce incorrect trajectories. By contrast, MACA mitigates the self-reinforcing error loops inherent in monolithic generation through coordination among diverse agents, achieving an average absolute gain of 13.69% over CoT on MMLU-Pro and GSM-Hard. More importantly, cross-scale results (Tables 1 and 2) show that MACA with Llama-3.1-8B can outperform a vanilla Llama-3.1-70B model on GSM-Hard (50.30% vs. 48.87%), while remaining competitive on MMLU-Pro and HumanEval (reaching ~97.3% of the vanilla 70B model’s performance). 3.3 Framework Analysis Ablation Study. Table 3 presents an ablation study on key components of MACA: (1) w/o ZpriorZ_prior, removing agent relevance prior; (2) w/o PpriorP_prior, removing interaction plausibility prior; (3) w/o GraphSpec, eliminating the entire structural prior; and (4) w/o πθ _θ, removing the learnable policy. Table 3: Ablation study of MACA. Dataset ARC-C GSM-Hard Metric Acc (%) Avg Cost Acc (%) Avg Cost MACA 87.75 1656.3 50.30 1602.5 MACA w/o ZpriorZ_prior 82.64 1920.4 44.37 1885.2 MACA w/o PpriorP_prior 81.31 1896.7 43.92 1830.8 MACA w/o GraphSpec 72.35 2285.9 36.80 2050.1 MACA w/o πθ _θ 85.53 2109.6 47.96 1785.5 Removing GraphSpec degenerates the system into an orchestration-centric approach. Without a structural prior to constrain the vast interaction space, performance drops most severely (14.45% ↓ in accuracy). Conversely, removing the policy πθ _θ reduces the system to a structure-centric approach. While accuracy only drops slightly, the token cost surges drastically (19.40% ↑ in cost). This reveals a clear functional division: GraphSpec preserves reasoning fidelity by constraining the search space, while the token-aware policy πθ _θ optimizes efficiency. Focusing on the structural prior itself, we observe that dropping either agent relevance ZpriorZ_prior or interaction plausibility PpriorP_prior leads to distinct accuracy degradation and increased overhead. This highlights that the joint effect of participating agents and their interaction patterns is essential for a robust coordination prior. RQ2: How does the prior affect orchestration decisions? Figure 3 shows that GraphSpec imposes a structural bias on orchestration. Without it, coordination is highly unconstrained, with probability mass diffusely spread across transitions. With GraphSpec, the distribution concentrates on a few dominant, task-relevant paths. Even when the same agent is selected, the prior still reshapes the confidence of execution. For example, the top-2 transition mass increases from 0.37 to 0.71 on HumanEval and from 0.38 to 0.72 on SVAMP, showing that GraphSpec turns diffuse routing into concentrated, task-relevant orchestration. This concentration makes orchestration more selective and cost-efficient, improving MACA’s efficiency. Figure 3: Impact of the prior on orchestration. 3.4 Cost Analysis RQ3: How does MACA balance cost and task performance? We evaluate cost–performance by jointly considering task accuracy and token consumption during inference, as shown in Figure 4. Figure 4: Cost–performance trade-offs of MACA and baseline approaches across datasets. MACA exhibits a clear cost-performance trade-off: higher cost consistently yields higher accuracy. MACA is tunable with respect to budget, enabling practitioners to flexibly trade computation for performance under different constraints. In practice, this allows accuracy to improve in a predictable manner. More importantly, MACA achieves a more favorable cost–performance frontier than existing multi-agent baselines. This advantage stems not merely from budget tunability, but from how the budget is utilized. MACA allocates computation through structured and selective coordination, converting additional cost into accuracy gains more effectively while avoiding unnecessary interaction. 3.5 Coordination Mechanisms Analysis RQ4: What coordination patterns emerge in MACA? Analysis of agent transition probabilities and coordination patterns on GSM-Hard trajectories reveals the following mechanisms: Figure 5: Column-to-row Transition Probabilities. Self-Correction (X → Checker): Figure 5 shows a coupling between generation and verification modules, particularly transitions such as Solver → Checker (0.30) and Router → Checker (0.27), with iterative feedback (e.g., Checker → Solver, 0.21). This pattern mirrors the Self-Refine Madaan et al. (2023), where candidate solutions are followed by verification and revision. However, MACA goes beyond fixed self-refine loops by learning an orchestration policy over when and where verification should occur: verification is invoked more frequently along complex reasoning while being skipped for simpler steps. This mechanism allows MACA to balance accuracy and token efficiency. Hierarchical Coordination: Figure 6 aggregates the most frequent three-agent transition sequences, revealing clear hierarchical coordination patterns. The first layer, Router and Designer, is responsible for task decomposition and strategy selection. The second layer, Parser and Analyzer, translates high-level intent into structured representations. The final layer, Solver and Checker, carries out computational reasoning and verification. Rather than relying on manually designed workflows, these coordination strata emerge from optimizing the structural prior and orchestration policy. This process structures agent capabilities into a cascaded reasoning framework, ensuring efficient task execution. Figure 6: Dominant Three-Agent Coordination Patterns. 3.6 Sensitivity Analysis Figure 7 illustrates the sensitivity of MACA to two core parameters: the threshold γ in Eq. (4), and the regularization coefficient λ in Eq. (12). Figure 7: Parameter sensitivity analysis of MACA. Threshold γ. An accuracy-efficiency trade-off emerges as γ varies. As γ increases from 0.1 to 0.4, accuracy rises from 72.8% to 75.2% while token cost drops, showing that moderate thresholding removes redundant coordination. Further increasing γ causes accuracy to decline steadily, indicating that overly aggressive sparsification discards useful coordination paths. We therefore set γ=0.4γ=0.4. Regularization coefficient λ. Increasing λ from 0.4 to 0.7 improves accuracy from 55.4% to 75.1%, but also raises token cost, indicating that stronger regularization improves orchestration quality at the expense of computation. Beyond this point, accuracy saturates while cost continues to grow, suggesting diminishing returns from overly large regularization. Accordingly, we adopt λ=0.7λ=0.7. 4 Related Work LLM-based Multi-Agent Systems. Advances in language models Guo et al. (2025); Hurst et al. (2024) have driven progress in LLM-based agents Zhao et al. (2024); Li et al. (2023a); Xie et al. (2024). As tasks grow complex, research has increasingly turned to LLM-based multi-agent systems Bo et al. (2024); Du et al. (2023). Prior work demonstrates empirical performance in such systems, exemplified by MacNet Qian et al. (2024b), ChatDev Qian et al. (2024a), and AutoGen Wu et al. (2023). Despite progress, early approaches rely on handcrafted structures Hong et al. (2023), limiting the exploration of structural optimality and transferability Cemri et al. (2025). Hence, research has begun to explore adaptive agentic systems. Adaptive Agentic Systems Optimization. Recent work explores how agent compositions Zhuge et al. (2024); Zhang et al. (2024b) and execution policies Yuan et al. (2025) can be optimized, broadly categorized into two streams: (I) Structure-Centric Adaptation methods Yang et al. (2025b); Wang et al. (2025d) adapt multi-agent topology, with methods such as AgentPrune Zhang et al. (2024a) and MaAS Zhang et al. (2025a) parameterizing agent interactions Li et al. (2023b); Yan et al. (2021). (I) Orchestration-Centric Adaptation methods Qayyum et al. (2025); Rasal (2024) introduce adaptivity at the execution level. Structure-centric methods favor stability, whereas orchestration-centric methods provide finer-grained control, yet both remain limited in isolation. RL as Inference. Reinforcement Learning (RL) has been widely used in LLM-based multi-agent coordination Sun et al. (2024). Applications include structural reasoning like BAMAS Yang et al. (2025b) and DyLAN Liu et al. (2024), as well as execution orchestration such as Puppeteer Dang et al. (2025) and OSC Zhang et al. (2025b). MAPRO Zhang et al. (2025d) uses posterior inference for multi-agent prompt optimization. More broadly, prior research has established the concept of RL as Inference Levine (2018); O’Donoghue et al. (2020); Tarbouriech et al. (2023). This view casts control as probabilistic inference and provides a principled foundation for execution optimization. 5 Conclusion In this paper, we introduce MACA, a probabilistic framework that rethinks automated multi-agent system design from a posterior inference perspective. MACA explicitly factorizes system adaptation into a task- and budget-conditioned structural prior and a token-aware orchestration policy, enabling principled uncertainty modeling and fine-grained control. MACA enables adaptive multi-agent systems that are effective across diverse tasks. The probabilistic perspective provides a foundation for future research on adaptive multi-agent systems. Limitations Although MACA demonstrates clear gains in both task performance and cost-efficiency, the current evaluation is still centered on relatively structured benchmarks, so its generalizability to more open-ended, interactive, or domain-specific settings is not yet fully established. In addition, MACA depends on a predefined agent pool with manually specified capabilities and role descriptions, which means that part of its effectiveness may still come from careful agent initialization rather than from coordination alone. Another limitation lies in the way the structural prior is learned: GraphSpec is trained from filtered high-quality trajectories and supervision signals derived from final outcome quality, which can favor coordination patterns that are easy to verify on benchmark tasks while making it harder to capture useful but less immediately rewarded interactions. This may reduce robustness in settings where credit assignment is noisy, intermediate collaboration is important, or success cannot be cleanly reflected by final answers alone. References M. Adhikari and A. Hazra (2022) 6G-enabled ultra-reliable low-latency communication in edge networks. IEEE Communications Standards Magazine 6 (1), p. 67–74. Cited by: §1. J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, et al. (2021) Program synthesis with large language models. arXiv preprint arXiv:2108.07732. Cited by: §3.1. U. Bhatt, S. Kapoor, M. Upadhyay, I. Sucholutsky, F. Quinzan, K. M. Collins, A. Weller, A. G. Wilson, and M. B. Zafar (2025) When should we orchestrate multiple agents?. arXiv preprint arXiv:2503.13577. Cited by: §1. X. Bo, Z. Zhang, Q. Dai, X. Feng, L. Wang, R. Li, X. Chen, and J. Wen (2024) Reflective multi-agent collaboration based on large language models. Advances in Neural Information Processing Systems 37, p. 138595–138631. Cited by: §4. B. Burns, B. Grant, D. Oppenheimer, E. Brewer, and J. Wilkes (2016) Borg, omega, and kubernetes. Communications of the ACM 59 (5), p. 50–57. Cited by: §1. M. Cemri, M. Z. Pan, S. Yang, L. A. Agrawal, B. Chopra, R. Tiwari, K. Keutzer, A. Parameswaran, D. Klein, K. Ramchandran, et al. (2025) Why do multi-agent llm systems fail?. arXiv preprint arXiv:2503.13657. Cited by: §1, §4. 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. External Links: 2107.03374 Cited by: §3.1. W. Chen, Y. Su, J. Zuo, C. Yang, C. Yuan, C. Chan, H. Yu, Y. Lu, Y. Hung, C. Qian, et al. (2024) AgentVerse: facilitating multi-agent collaboration and exploring emergent behaviors.. In ICLR, Cited by: §C.2, §1, §3.1. Y. Chen, Y. Wang, S. Zhu, H. Yu, T. Feng, M. Zhang, M. Patwary, and J. You (2025) Multi-agent evolve: llm self-improve through co-evolution. arXiv preprint arXiv:2510.23595. Cited by: §1. Y. Cheng, C. Zhang, Z. Zhang, X. Meng, S. Hong, W. Li, Z. Wang, Z. Wang, F. Yin, J. Zhao, et al. (2024) Exploring large language model based intelligent agents: definitions, methods, and prospects. arXiv preprint arXiv:2401.03428. Cited by: §1. P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord (2018) Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv:1803.05457v1. Cited by: §3.1. Y. Dang, C. Qian, X. Luo, J. Fan, Z. Xie, R. Shi, W. Chen, C. Yang, X. Che, Y. Tian, et al. (2025) Multi-agent collaboration via evolving orchestration. arXiv preprint arXiv:2505.19591. Cited by: §C.2, §1, §3.1, §4. 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: §4. Y. Fu, H. Peng, A. Sabharwal, P. Clark, and T. Khot (2022) Complexity-based prompting for multi-step reasoning. arXiv preprint arXiv:2210.00720. Cited by: §C.2, §3.1. L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig (2022) PAL: program-aided language models. arXiv preprint arXiv:2211.10435. Cited by: §3.1. D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. (2025) Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §2.3, §4. T. Guo, X. Chen, Y. Wang, R. Chang, S. Pei, N. V. Chawla, O. Wiest, and X. Zhang (2024) Large language model based multi-agents: a survey of progress and challenges. arXiv preprint arXiv:2402.01680. Cited by: §1. J. He, C. Treude, and D. Lo (2025) LLM-based multi-agent systems for software engineering: literature review, vision, and the road ahead. ACM Transactions on Software Engineering and Methodology 34 (5), p. 1–30. Cited by: §1. S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, et al. (2023) MetaGPT: meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, Cited by: §1, §4. A. Hurst, A. Lerer, A. P. Goucher, A. Perelman, A. Ramesh, A. Clark, A. Ostrow, A. Welihinda, A. Hayes, A. Radford, et al. (2024) Gpt-4o system card. arXiv preprint arXiv:2410.21276. Cited by: §4. W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica (2023) Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, Cited by: §C.3. S. Levine (2018) Reinforcement learning and control as probabilistic inference: tutorial and review. arXiv preprint arXiv:1805.00909. Cited by: §2.1, §4. G. Li, H. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem (2023a) Camel: communicative agents for" mind" exploration of large language model society. Advances in Neural Information Processing Systems 36, p. 51991–52008. Cited by: §4. X. Li, S. Wang, S. Zeng, Y. Wu, and Y. Yang (2024) A survey on llm-based multi-agent systems: workflow, infrastructure, and challenges. Vicinagearth 1 (1), p. 9. Cited by: §1. Z. Li, L. Wang, X. Sun, Y. Luo, Y. Zhu, D. Chen, Y. Luo, X. Zhou, Q. Liu, S. Wu, et al. (2023b) GSLB: the graph structure learning benchmark. Advances in Neural Information Processing Systems 36, p. 30306–30318. Cited by: §4. Y. Lin, K. Chen, Z. Li, T. Wu, T. Wu, K. Chen, H. Lee, and Y. Chen (2025) Creativity in llm-based multi-agent systems: a survey. arXiv preprint arXiv:2505.21116. Cited by: §1. S. Liu, T. Chen, Z. Liang, X. Lyu, and C. Amato (2025) Llm collaboration with multi-agent reinforcement learning. arXiv preprint arXiv:2508.04652. Cited by: §1. 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, Cited by: §C.2, §3.1, §4. A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. (2023) Self-refine: iterative refinement with self-feedback. Advances in Neural Information Processing Systems 36, p. 46534–46594. Cited by: §C.2, §3.1, §3.5. M. Minsky (1986) Society of mind. Simon and Schuster. Cited by: §1. A. Naik, P. Quinn, G. Bosch, E. Gouné, F. J. C. Zabala, J. R. Brown, and E. J. Young (2025) AgentMisalignment: measuring the propensity for misaligned behaviour in llm-based agents. arXiv preprint arXiv:2506.04018. Cited by: §1. B. O’Donoghue, I. Osband, and C. Ionescu (2020) Making sense of reinforcement learning and probabilistic inference. arXiv preprint arXiv:2001.00805. Cited by: §4. A. Patel, S. Bhattamishra, and N. Goyal (2021) Are nlp models really able to solve simple math word problems?. arXiv preprint arXiv:2103.07191. Cited by: §3.1. A. Qayyum, A. Albaseer, J. Qadir, A. Al-Fuqaha, and M. Abdallah (2025) LLM-driven multi-agent architectures for intelligent self-organizing networks. IEEE Network. Cited by: §1, §4. C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, et al. (2024a) Chatdev: communicative agents for software development. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 15174–15186. Cited by: §1, §4. C. Qian, Z. Xie, Y. Wang, W. Liu, K. Zhu, H. Xia, Y. Dang, Z. Du, W. Chen, C. Yang, et al. (2024b) Scaling large language model-based multi-agent collaboration. arXiv preprint arXiv:2406.07155. Cited by: §C.2, §3.1, §4. S. Rasal and E. Hauer (2024) Navigating complexity: orchestrated problem solving with multi-agent llms. arXiv preprint arXiv:2402.16713. Cited by: §1. S. Rasal (2024) Llm harmony: multi-agent communication for problem solving. arXiv preprint arXiv:2401.01312. Cited by: §1, §4. Z. Rasheed, M. Waseem, A. Ahmad, K. Kemell, W. Xiaofeng, A. N. Duc, and P. Abrahamsson (2024) Can large language models serve as data analysts? a multi-agent assisted approach for qualitative data analysis. arXiv preprint arXiv:2402.01386. Cited by: §1. Y. Shang, Y. Li, K. Zhao, L. Ma, J. Liu, F. Xu, and Y. Li (2024) Agentsquare: automatic llm agent search in modular design space. 2024. Cited by: §1. C. Sun, S. Huang, and D. Pompili (2024) Llm-based multi-agent reinforcement learning: current and future directions. arXiv preprint arXiv:2405.11106. Cited by: §1, §4. Y. Talebirad and A. Nadiri (2023) Multi-agent collaboration: harnessing the power of intelligent llm agents. arXiv preprint arXiv:2306.03314. Cited by: §1. X. Tang, A. Zou, Z. Zhang, Z. Li, Y. Zhao, X. Zhang, A. Cohan, and M. Gerstein (2024) Medagents: large language models as collaborators for zero-shot medical reasoning. In Findings of the Association for Computational Linguistics: ACL 2024, p. 599–621. Cited by: §1. J. Tarbouriech, T. Lattimore, and B. O’Donoghue (2023) Probabilistic inference in reinforcement learning done right. Advances in Neural Information Processing Systems 36, p. 33687–33725. Cited by: §4. C. Tian, Y. Wang, X. Liu, Z. Wang, L. Ding, M. Zhang, and M. Zhang (2025) AgentInit: initializing llm-based multi-agent systems via diversity and expertise orchestration for effective and efficient collaboration. In Findings of the Association for Computational Linguistics: EMNLP 2025, p. 11870–11902. Cited by: §1. X. Tu, Z. He, Y. Huang, Z. Zhang, M. Yang, and J. Zhao (2024) An overview of large ai models and their applications. Visual Intelligence 2 (1), p. 34. Cited by: §1. D. Ulyanov, A. Vedaldi, and V. Lempitsky (2018) Deep image prior. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 9446–9454. Cited by: §2.2. H. Wang, D. Cheng, Y. Zhang, and W. Zhang (2025a) AIGC for graphs: current techniques and future trends. In 2025 IEEE 41st International Conference on Data Engineering (ICDE), p. 4504–4508. Cited by: §2.2. P. Wang, Y. Yu, K. Chen, X. Zhan, and H. Wang (2025b) Large language model-based data science agent: a survey. arXiv preprint arXiv:2508.02744. Cited by: §1. Q. Wang, T. Wang, Z. Tang, Q. Li, N. Chen, J. Liang, and B. He (2025c) MegaAgent: a large-scale autonomous llm-based multi-agent system without predefined sops. In Findings of the Association for Computational Linguistics: ACL 2025, p. 4998–5036. Cited by: §1. Q. Wang, Z. Wang, Y. Su, H. Tong, and Y. Song (2024a) Rethinking the bounds of llm reasoning: are multi-agent discussions the key?. arXiv preprint arXiv:2402.18272. Cited by: §2.2. X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou (2022) Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171. Cited by: §C.2, §3.1. Y. Wang, X. Ma, G. Zhang, Y. Ni, A. Chandra, S. Guo, W. Ren, A. Arulraj, X. He, Z. Jiang, et al. (2024b) Mmlu-pro: a more robust and challenging multi-task language understanding benchmark. Advances in Neural Information Processing Systems 37, p. 95266–95290. Cited by: §3.1. Z. Wang, Y. Wang, X. Liu, L. Ding, M. Zhang, J. Liu, and M. Zhang (2025d) Agentdropout: dynamic agent elimination for token-efficient and high-performance llm-based multi-agent collaboration. arXiv preprint arXiv:2503.18891. Cited by: §1, §4. 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: §C.2, §3.1, §3.2. Q. Wu, G. Bansal, J. Zhang, Y. Wu, S. Zhang, E. Zhu, B. Li, L. Jiang, X. Zhang, and C. Wang (2023) Autogen: enabling next-gen llm applications via multi-agent conversation framework. arXiv preprint arXiv:2308.08155 3 (4). Cited by: §1, §4. S. Xiao, Z. Liu, P. Zhang, and N. Muennighoff (2023) C-pack: packaged resources to advance general chinese embedding. External Links: 2309.07597 Cited by: §2.2. Y. Xiao, J. Liu, Y. Zheng, X. Xie, J. Hao, M. Li, R. Wang, F. Ni, Y. Li, J. Luo, et al. (2024) Cellagent: an llm-driven multi-agent framework for automated single-cell data analysis. arXiv preprint arXiv:2407.09811. Cited by: §1. C. Xie, C. Chen, F. Jia, Z. Ye, S. Lai, K. Shu, J. Gu, A. Bibi, Z. Hu, D. Jurgens, et al. (2024) Can large language model agents simulate human trust behavior?. Advances in neural information processing systems 37, p. 15674–15729. Cited by: §4. Z. Yan, X. Dai, P. Zhang, Y. Tian, B. Wu, and M. Feiszli (2021) Fp-nas: fast probabilistic neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 15139–15148. Cited by: §4. J. Yang, M. Zhang, Y. Jin, H. Chen, Q. Wen, L. Lin, Y. He, S. Kumar, W. Xu, J. Evans, et al. (2025a) Topological structure learning should be a research priority for llm-based multi-agent systems. arXiv preprint arXiv:2505.22467. Cited by: §1, §1. L. Yang, J. Luo, X. Liu, Y. Lou, and Z. Chen (2025b) BAMAS: structuring budget-aware multi-agent systems. arXiv preprint arXiv:2511.21572. Cited by: §C.1, §2.2, §4, §4. S. Yuan, K. Song, J. Chen, X. Tan, D. Li, and D. Yang (2025) Evoagent: towards automatic multi-agent generation via evolutionary algorithms. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 6192–6217. Cited by: §1, §4. G. Zhang, L. Niu, J. Fang, K. Wang, L. Bai, and X. Wang (2025a) Multi-agent architecture search via agentic supernet. arXiv preprint arXiv:2502.04180. Cited by: §C.1, §C.2, §1, §3.1, §4. G. Zhang, Y. Yue, Z. Li, S. Yun, G. Wan, K. Wang, D. Cheng, J. X. Yu, and T. Chen (2024a) Cut the crap: an economical communication pipeline for llm-based multi-agent systems. arXiv preprint arXiv:2410.02506. Cited by: §C.2, §1, §2.1, §3.1, §4. G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng (2024b) G-designer: architecting multi-agent communication topologies via graph neural networks. arXiv preprint arXiv:2410.11782. Cited by: §1, §4. J. Zhang, J. Xiang, Z. Yu, F. Teng, X. Chen, J. Chen, M. Zhuge, X. Cheng, S. Hong, J. Wang, et al. (2024c) Aflow: automating agentic workflow generation. arXiv preprint arXiv:2410.10762. Cited by: §1. J. Zhang, Y. Fan, K. Cai, J. Tang, X. Sun, and K. Wang (2025b) OSC: cognitive orchestration through dynamic knowledge alignment in multi-agent llm collaboration. Rn 100 (R1), p. R2. Cited by: §1, §4. S. Zhang, M. Yin, J. Zhang, J. Liu, Z. Han, J. Zhang, B. Li, C. Wang, H. Wang, Y. Chen, et al. (2025c) Which agent causes task failures and when? on automated failure attribution of llm multi-agent systems. arXiv preprint arXiv:2505.00212. Cited by: §1. Y. Zhang, R. Sun, Y. Chen, T. Pfister, R. Zhang, and S. Arik (2024d) Chain of agents: large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems 37, p. 132208–132237. Cited by: §1. Z. Zhang, L. Ge, H. Li, W. Zhu, C. Zhang, and Y. Ye (2025d) MAPRO: recasting multi-agent prompt optimization as maximum a posteriori inference. arXiv preprint arXiv:2510.07475. Cited by: §4. A. Zhao, D. Huang, Q. Xu, M. Lin, Y. Liu, and G. Huang (2024) Expel: llm agents are experiential learners. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 19632–19642. Cited by: §4. J. Zhu, P. Cai, K. Xu, L. Li, Y. Sun, S. Zhou, H. Su, L. Tang, and Q. Liu (2024) Autotqa: towards autonomous tabular question answering through multi-agent large language models. Proceedings of the VLDB Endowment 17 (12), p. 3920–3933. Cited by: §1. M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber (2024) Gptswarm: language agents as optimizable graphs. In Forty-first International Conference on Machine Learning, Cited by: §1, §4. Appendix Appendix A LLM Usage ChatGPT was used solely to support language refinement during the writing process, including spellchecking, grammar improvement, and paraphrasing of the authors’ original text. The assistant was not used to generate new technical content, research ideas, or experimental results. All AI-assisted revisions were carefully checked, edited where necessary, and approved by the authors. Appendix B Probabilistic Assumptions for Posterior Inference We adopt a probabilistic view of coordination in which the coordination structure G affects the target outcome y⋆y only through the induced execution trajectory τ. Formally, conditioned on the input x and trajectory τ, the output is independent of G, i.e., y⋆⟂G∣(τ,x)y G (τ,x). Under this assumption, the output fidelity term in Equation (1) depends only on the realized trajectory and the given task, while G remains important because it constrains which trajectories are plausible under the task and budget. From this perspective, once a suitable structural prior is learned, posterior inference favors trajectories with higher utility. In MACA, this intractable inference is approximated by a learnable parameterized policy, while the structural prior induces a reference distribution πmix _mix to guide exploration toward structurally plausible and high-value coordination patterns. In this sense, MACA can be interpreted as an approximation to posterior coordination inference under a learned structural prior. Appendix C Experimental Details C.1 Dataset Following practice in prior work Zhang et al. (2025a); Yang et al. (2025b), we split each benchmark into training and test sets. As shown in Table 4, our experiments cover three task domains: code generation, math reasoning, and question answering. For code generation, we use HumanEval and MBPP, evaluated by pass@1. For math reasoning, we include GSM-Hard and SVAMP, both evaluated by accuracy. For question answering, we use MMLU-Pro and ARC-Challenge (ARC-C), also measured by accuracy. Table 4: Dataset Statistics. Domain Dataset #Train #Test Metric Code Generation HumanEval 96 68 pass@1 MBPP 587 387 pass@1 Math Reasoning GSM-Hard 611 389 Accuracy SVAMP 593 407 Accuracy Question Answering MMLU-Pro 731 487 Accuracy ARC-Challenge 689 483 Accuracy C.2 Baseline Setups To ensure fair comparison, all baselines are rerun under a unified experimental protocol. All methods use the same backbone LLM, the same dataset split, and the same evaluation metrics as in the experiments. For methods with public implementations, we follow their original core design; otherwise, we reproduce them according to the descriptions in their papers. The mean performance over three independent trials is reported. We describe the configurations of the baseline methods in detail: Vanilla. A single LLM directly produces the final answer without explicit deliberation or interaction. CoT. We use standard Chain-of-Thought prompting Wei et al. (2022). ComplexCoT. We adopt complexity-based prompting Fu et al. (2022) with more elaborate intermediate reasoning than standard CoT. Self-Refine. We follow Self-Refine Madaan et al. (2023) and let a single LLM iteratively generate, critique, and refine its answer. SC (CoT×5). We apply self-consistency Wang et al. (2022) by sampling five CoT reasoning paths and aggregating the final answer. DyLAN. We follow the collaborative discussion setting of DyLAN Liu et al. (2024). MacNet. We use MacNet Qian et al. (2024b) with a fixed fully connected communication topology. AgentVerse. We follow the role-based collaboration framework of AgentVerse Chen et al. (2024). AgentPrune. We implement AgentPrune Zhang et al. (2024a) as a structure-centric adaptive baseline that prunes agents or communication edges before execution. MaAS. We follow MaAS Zhang et al. (2025a) as a structure-adaptive baseline that dynamically selects task-relevant agents and interaction patterns. Puppeteer. We follow Puppeteer Dang et al. (2025) as an orchestration-centric baseline where a controller dynamically selects which agent to invoke at each step. C.3 Computational Resources All experiments are conducted on servers equipped with 8 NVIDIA A800 GPUs, and mixed-precision training is used throughout. The underlying large language model is deployed through vLLM Kwon et al. (2023) during both training and evaluation. Unless otherwise specified, all reported results are obtained under the same hardware setting. Our framework is trained in two stages. The prior learning stage typically takes about 3–6 hours per dataset. The policy optimization stage is more computationally intensive due to rollout sampling, reward computation, and parameter updates, and usually requires about 12–24 hours per dataset. During evaluation, a full benchmark run typically takes about 1–3 hours. C.4 Agent Setups We instantiate a pool of functionally specialized agents with distinct roles. Table 5 summarizes the candidate agent pools used for different task families, while Figures 9–12 provide the corresponding role prompts. Table 5: Candidate Agent Pools. Task Family Candidate Agent Pool Question Answering [Fig. 10] TaskRouter, AnalyzeAgent, ChoiceEliminator, EvidenceChecker, Skeptic, QASynthesizer Math Reasoning [Fig. 11] WordProblemParser, MathSolver, ArithmeticChecker, StepChecker, AlgebraSimplifier, GeneralCritic Code Generation [Fig. 12] AlgorithmDesigner, CodeWriting, CodeReviewer, UnitTestWriter, EdgeCaseHunter, BugFixer Auxiliary Roles [Fig. 9] TaskPlanner, Summarizer, BudgetController, RedTeamCritic In our framework, prior shaping is achieved by first estimating task- and budget-conditioned agent relevance scores to identify which roles are most useful for the current input, and then modeling interaction plausibility to characterize which inter-agent communications are likely to be beneficial. Based on these two components, the framework organizes their communication according to the learned orchestration structure. During analysis, we maintain a lightweight mapping that canonicalizes implementation-specific agent names into shared functional roles (e.g., mapping planning-related agents to Planner) to enable consistent role-level statistics and comparisons. C.5 Component and Threshold Sensitivity The structural prior in MACA is not solely determined by the threshold γ. Instead, γ is used as a gating mechanism to filter low-confidence agents. The full structural prior consists of two complementary components: agent relevance ZpriorZ_prior, estimated from prior knowledge, and interaction plausibility PpriorP_prior, estimated from trajectory experience. Therefore, sensitivity should be understood from two perspectives: component sensitivity, which studies whether removing ZpriorZ_prior or PpriorP_prior affects performance, and parameter sensitivity, which studies how γ changes the accuracy–efficiency trade-off. To analyze the effect of γ on agent-selection sparsity, a sensitivity study is conducted by varying γ and measuring the precision and recall of the retained agent set. Here, precision denotes the proportion of retained agents that belong to the correct domain, while recall denotes the proportion of correct-domain agents successfully retained. As shown in Figure 8, a moderate γ removes redundant agents while preserving the complete correct-domain agent set. In contrast, an overly large γ may discard useful agents or interaction paths. Figure 8: Sensitivity of Agent-Selection Sparsity to γ. Overall, γ controls the sparsity of the retained agent set rather than defining the structural prior itself. Moderate values achieve a favorable accuracy–efficiency trade-off by pruning redundant agents, whereas excessively large values may reduce recall by filtering out useful agents. C.6 Algorithm This subsection summarizes the training procedure of MACA, as detailed in Algorithm 1. Training consists of two stages: learning a task- and budget-conditioned structural prior, and optimizing a token-aware orchestration policy over execution trajectories. We adopt this two-stage strategy to stabilize policy learning by first providing a learned structural reference distribution, rather than jointly updating the structure and policy in a non-stationary coordination space. The policy is trained with policy-gradient updates to favor task-effective coordination under explicit budget constraints. Figure 9: Auxiliary role prompts. TaskPlanner TaskPlanner: Produces a coarse multi-step execution plan before detailed reasoning begins. Prompt summary: Break the task into a small number of necessary steps, identify dependencies between them, and suggest a compact execution plan. Summarizer Summarizer: Compresses intermediate discussion into a concise state summary for downstream agents. Prompt summary: Summarize the most useful intermediate conclusions, unresolved uncertainties, and next-step recommendations in a compact form. BudgetController BudgetController: Monitors communication cost and recommends more economical coordination behavior. Prompt summary: Estimate whether the current discussion is becoming unnecessarily expensive and suggest cheaper alternatives when possible. RedTeamCritic RedTeamCritic: Stress-tests the current reasoning by searching for overlooked risks, counterexamples, or failure modes. Prompt summary: Deliberately challenge the current solution, identify brittle assumptions, and point out scenarios in which the answer may fail. Figure 10: Question-answering role prompts. TaskRouter TaskRouter: Determines the task type and proposes a minimal, task-appropriate coordination team. Prompt summary: Classify the task as code, math, or QA, and provide a concise routing rationale without solving the task. AnalyzeAgent AnalyzeAgent: Extracts task constraints, key entities, hidden assumptions, and salient evidence from the input and peer outputs. Prompt summary: Analyze the problem structure carefully and summarize the most decision-relevant information. ChoiceEliminator ChoiceEliminator: Reduces the answer space by explicitly ruling out implausible or contradicted options. Prompt summary: Eliminate incorrect choices one by one and then provide the final answer letter. EvidenceChecker EvidenceChecker: Verifies whether candidate answers are supported by the question facts and flags contradictions. Prompt summary: Match each option against the evidence, identify factual mismatches, and select the most supported answer. Skeptic Skeptic: Challenges intermediate reasoning and exposes weak assumptions or unsupported jumps. Prompt summary: Critique other agents’ reasoning, highlight likely errors, and question overconfident conclusions. QASynthesizer QASynthesizer: Produces the final concise answer by aggregating validated evidence from upstream agents. Prompt summary: Return a short, direct final answer grounded in the strongest available evidence. Figure 11: Math reasoning role prompts. WordProblemParser WordProblemParser: Transforms a math word problem into explicit quantities, variables, and equations before solving. Prompt summary: List known values, define variables, and derive equations or constraints without computing the final answer. MathSolver MathSolver: Carries out the main step-by-step derivation for numerical reasoning tasks. Prompt summary: Solve the problem sequentially, show the key arithmetic or algebraic steps, and produce the final numeric answer. ArithmeticChecker ArithmeticChecker: Recomputes arithmetic operations to detect calculation mistakes in intermediate or final steps. Prompt summary: Recalculate sums, products, ratios, and final values, then confirm or correct the numeric answer. StepChecker StepChecker: Identifies the first invalid step in a reasoning chain and repairs it. Prompt summary: Locate the first incorrect step, explain why it is wrong, and provide a corrected derivation with unit consistency. AlgebraSimplifier AlgebraSimplifier: Simplifies symbolic expressions and rewrites equations into cleaner, easier-to-verify forms. Prompt summary: Rearrange equations and simplify intermediate expressions while preserving correctness. GeneralCritic GeneralCritic: Detects hidden assumptions, missing constraints, and logically weak solution paths. Prompt summary: Review the proposed solution critically and point out logical gaps, overlooked cases, or unjustified assumptions. Figure 12: Code generation role prompts. AlgorithmDesigner AlgorithmDesigner: Designs the algorithmic strategy and data structures before implementation. Prompt summary: Outline the intended approach, complexity, and edge cases without writing the full program. CodeWriting CodeWriting: Produces the executable implementation for the target coding task. Prompt summary: Write the complete Python solution, preserve the required function signature, and output valid code only. CodeReviewer CodeReviewer: Inspects correctness, boundary conditions, and code quality after implementation. Prompt summary: Review the candidate program for logical bugs, edge cases, and maintainability issues. UnitTestWriter UnitTestWriter: Constructs representative and adversarial tests for validating candidate programs. Prompt summary: Provide concise assertions or test cases that cover both standard and corner-case behavior. EdgeCaseHunter EdgeCaseHunter: Searches for pathological inputs and counterexamples likely to break a candidate solution. Prompt summary: List tricky boundary conditions or adversarial inputs and explain why they are risky. BugFixer BugFixer: Repairs incorrect implementations using minimal but targeted modifications. Prompt summary: Identify the failure mode and provide a corrected version of the code with minimal necessary changes. Algorithm 1 : Training Procedure of MACA 1:Training dataset trainD_train, Agent set O, Generation group size g, Reference policy πref _ref, Budget constraint b, Threshold γ, Regularization coefficient λ 2:Output: Orchestration policy πθ _θ Structural Prior Learning: 3:for each episode do 4: Sample G(k)k=1K∼πϕ(⋅∣x)\G^(k)\_k=1^K _φ(· x) 5: Update ϕφ accordingly ⊳ Eq. 5 6: Derive ψ from the sampled structures G(k)G^(k) via πϕ _φ 7:end forToken-Aware Orchestration Policy Learning: 8:Initialize parameters θ 9:for each episode do 10: Sample a task x∼trainx _train 11: Compute agent relevance prior ZpriorZ_prior given (x,b,γ)(x,b,γ) ⊳ Eq. 4 12: Compute interaction plausibility prior PpriorP_prior with MLPψMLP_ψ ⊳ Eq. 7 13: Construct GraphSpec 14: Construct State s and Action mask ℳM 15: Sample outputs τ(1),τ(2),…,τ(g)∼πθ(⋅|s,ℳ)\τ^(1),τ^(2),…,τ^(g)\ _θ(·|s,M) 16: Obtain rewards rλ(1),rλ(2),…,rλ(g)\r_λ^(1),r_λ^(2),…,r_λ^(g)\⊳ Eq. 12 17: Compute advantage for each group member⊳ Eq. 9 18: Compute loss w.r.t. πθ _θ⊳ Eq. 10 19: Update θ accordingly 20:end for 21: Return πθ _θ Appendix D Supplementary Results and Analysis D.1 Results on Qwen2.5-14B-Instruct We additionally conduct experiments using Qwen2.5-14B-Instruct as the backbone LLM. As shown in Table 6, MACA consistently achieves the best accuracy while maintaining substantially lower token cost than dynamic multi-agent baselines. These results indicate that our proposed method is not tied to a specific LLM family, and can improve the accuracy–efficiency trade-off. Table 6: Results on Qwen2.5-14B-Instruct. Method MMLU-Pro HumanEval GSM-Hard Acc (%) Cost Acc (%) Cost Acc (%) Cost Vanilla 59.12 248.6 80.54 251.3 47.36 266.8 CoT 60.94 286.7 82.15 317.5 51.28 391.4 DyLAN 64.08 11960.2 84.37 12784.6 52.64 13926.8 AgentPrune 63.71 2958.4 82.76 3168.2 55.92 4236.5 MaAS 63.22 3147.9 85.98 3625.7 61.37 3784.3 MACA 64.46 2412.5 86.89 2848.9 63.28 2966.4 D.2 Results on Reasoning-Oriented Models To further examine whether MACA generalizes beyond instruct-tuned models, we conduct additional experiments on GSM-Hard using a reasoning-oriented 14B model. As shown in Table 7, MACA consistently improves accuracy while substantially reducing token cost compared with DyLAN. On Qwen2.5-14B-Instruct, MACA improves accuracy by 10.64% and reduces average token cost by 78.7%. On DeepSeek-R1-Distill-Qwen-14B, where extended reasoning introduces much higher token pressure, MACA still improves accuracy by 4.03% and reduces average token cost by 71.4%. These results suggest that MACA remains effective under reasoning-oriented backbones. Table 7: Results on GSM-Hard. Model Method Acc (%) Cost Qwen2.5-14B-Instruct DyLAN 52.64 13926.8 Qwen2.5-14B-Instruct MACA 63.28 2966.4 DS-R1-Distill-Qwen-14B DyLAN 65.91 49780.3 DS-R1-Distill-Qwen-14B MACA 69.94 14241.7 D.3 Cost of Training the Orchestration Policy We use GRPO-style group sampling with group size G=8G=8. The orchestration policy is optimized using AdamW with learning rate 1×10−51× 10^-5. The cost penalty coefficient is set to β=0.02β=0.02. The maximum sequence length is 4096. We run MACA on 8×8× A800 GPUs. The policy optimization stage takes approximately 12–24 hours per dataset, depending on dataset size and convergence behavior. Including structural-prior learning, the total training cost is approximately 15–30 hours per dataset. This cost is incurred once per dataset. After training, MACA amortizes this cost by pruning redundant agent invocations and producing more efficient coordination trajectories. Table 8: Training cost and inference-time efficiency. Method Extra Training Train Time Cost / Acc (%) Vanilla LLM No 0 hrs 251.3 / 80.54 DyLAN No 0 hrs 12784.6 / 84.37 MaAS No 0 hrs 3625.7 / 85.98 MACA Yes 12–24 hrs/dataset 2848.9 / 86.89 As shown in Table 8, although MACA introduces additional one-time training cost, it achieves the best accuracy while maintaining lower inference cost than multi-agent baselines. The policy learns reusable orchestration behavior during training and reduces unnecessary agent calls during inference. D.4 Case Study Task-Conditioned Agent Specialization. As shown in Table 9, AlgorithmDesigner and CodeWriting receive different relevance scores because their prompts encode distinct functional roles: AlgorithmDesigner focuses on designing the solution before implementation, whereas CodeWriting focuses on producing executable code. Thus, even within the same broad domain, agents can differ in their task-level relevance. Table 9: Examples of task-conditioned agent relevance scores. Task AlgorithmDesigner CodeWriting CodeReviewer UnitTestWriter EdgeCaseHunter BugFixer below_zero 0.52 0.86 0.48 0.71 0.41 0.39 find_zero 0.66 0.88 0.61 0.73 0.58 0.54 Importantly, node-level relevance only determines which agents are retained after filtering; the final orchestration is not determined by relevance alone. MACA further combines node-level relevance with edge-level transition weights in Eq. 7. Therefore, even when two agents are both relevant to the same domain, their coordination patterns may differ depending on interaction plausibility and task-instance complexity. Table 10: Case comparison between manual orchestration and MACA on HumanEval. Task Method Orchestration Path Result Cost below_zero Manual AlgorithmDesigner → CodeWriting → UnitTestWriter → BugFixer Pass 1.63k below_zero MACA CodeWriting → UnitTestWriter → STOP Pass 0.84k find_zero Manual AlgorithmDesigner → CodeWriting → UnitTestWriter → BugFixer Fail 2.41k find_zero MACA AlgorithmDesigner → CodeWriting → EdgeCaseHunter → CodeReviewer → BugFixer → UnitTestWriter → STOP Pass 3.54k Table 11: Comparison between LLM-router variants and MACA on GSM-Hard. Orchestrator Constraint Optimizable Acc (%) Invalid Action Rate LLM Router None ✗ 42.42 6.4% LLM Router + GraphSpec Prompt Natural-language hint ✗ 45.45 3.5% LLM Router + Mask Rule-based constraint ✗ 47.47 1.1% MACA Mask + Prior regularization ✓ 50.30 0.0% Adaptive Orchestration Versus Manual Orchestration. To further illustrate the difference between fixed manual orchestration and adaptive orchestration, we compare MACA with a manually designed workflow on two HumanEval examples in Table 10. Manual orchestration follows a fixed path, whereas MACA adjusts the path according to task difficulty. For a simpler task, MACA uses a shorter path and reduces token cost. For a harder task, it invokes additional verification and repair agents, improving the final result. D.5 RL-based Orchestration versus LLM Routers We further compare the learned orchestration policy in MACA against an LLM-based router. An LLM router relies on pretrained instruction-following behavior and remains static with respect to task-specific outcomes. In contrast, the RL policy in MACA is optimized using task-level rewards, allowing the routing strategy to adapt to the target benchmark and budget constraints. Table 11 compares MACA with several LLM-router variants on GSM-Hard. The plain LLM router achieves 42.42% accuracy and exhibits a 6.4% invalid action rate. Adding GraphSpec as a natural-language hint improves accuracy, while enforcing GraphSpec as a hard mask further reduces invalid actions. However, both variants remain non-optimizable and are still weaker than MACA. With mask-based constraints and prior regularization, MACA improves accuracy by 7.88% over the plain LLM router and reduces invalid actions to zero, confirming the necessity of RL-based orchestration.