acceptodds
Under review as a conference paper at ICLR 2027

Learn to Collaborate: Autoregressive Diversity-Aware Graph Generation for Multi-Agent Systems

Abstract

Large Language Model (LLM)-based multi-agent systems have demonstrated strong capabilities on complex reasoning and decision-making tasks. However, existing approaches typically suffer from temporal-agnostic node selection, homogeneous interaction patterns, or topology-agnostic LLM routing, which may compromise collaborative performance while increasing computational costs. In this work, we propose GraphMAC, an autoregressive diversity-aware graph generation method for multi-agent systems. GraphMAC formulates multi-agent collaboration consisting of three stages: temporal-aware node selection, diverse edge construction, and graph-aware LLM allocation. Specifically, we first recruit agents autoregressively using a GRU-based historical aggregation mechanism that captures temporal dependencies during role selection. We then construct heterogeneous interaction graphs with multiple self-loop and cross-node edge types, enabling diverse collaborative interaction patterns. Finally, we employ relational graph convolutional networks to perform topology-aware message passing and dynamically allocate heterogeneous LLM backbones from a graph-level perspective. To jointly optimize task performance, interaction diversity, and computational cost, we further introduce a reinforcement learning objective with structural diversity entropy. Extensive experiments on multiple datasets demonstrate that GraphMAC consistently outperforms existing methods, achieving up to 5.8% performance improvement while maintaining superior cost-performance trade-offs.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi-Agent System, LLM Collaboration, Graph Neural Network

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_uPWcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

GraphMAC generates a query-specific multi-agent system by autoregressively selecting roles with a GRU, choosing heterogeneous self and cross-agent interactions, and assigning LLMs through relational graph convolution. The paper reports improvements over MasRouter on five benchmarks, including 5.80 percentage points on MBPP and approximately 43% lower MATH inference cost. It also presents component comparisons and routing to an additional LLM without retraining.

Critical strengths

The unified treatment of role composition, interaction operations, and heterogeneous LLM assignment is a useful problem. Graph-conditioned routing offers a coherent way to allocate models to different structural roles.

Critical weaknesses
  1. The comparability of the main baselines are unclear. The 15 rows from CoT through RouterDC in Table 1 exactly reproduce the corresponding results in the published MasRouter Table 1, although that work used a different routing pool. MasRouter, Section 5.1 and Table 1. Furthermore, four entries in Vanilla (GPT) match its GPT-3.5-turbo row, while the MATH entry matches its GPT-4o-mini row; Section 5.1 identifies GPT as GPT-4o-mini.

  2. The executable collaboration evidence for its specific improvements are incomplete. Section 4.2 defines local edge operations but does not specify execution order, cyclic interactions, merging multiple incoming contexts, or final aggregation. These choices determine both correctness and cost; Appendix A.2 only instructs the reader to execute the graph.

  3. Table 2 replaces entire learned modules with random choices. It therefore does not isolate the claimed advantages of GRU history over mean pooling, heterogeneous operations over a single pattern, or graph-conditioned routing over a learned graph-independent router.

Questions for authors
  1. Were the matching baseline results reused or rerun, and how was comparability across model pools ensured? Please clarify which model produced each Vanilla (GPT) entry.

  2. How is the generated graph executed, including execution order, cyclic interactions, incoming-message merging, and final aggregation?

  3. Could you provide controlled comparisons of GRU versus mean pooling, heterogeneous versus homogeneous interactions, and graph-conditioned versus learned graph-independent routing under comparable inference budgets?

  4. Hetero-Designer (Zhang et al., ACL 2026) is closely related and warrants discussion. Could you compare its interleaved role/model selection and edge construction with GraphMAC, explaining the benefits of assigning models after graph construction and using typed interactions over equivalent unrolled DAGs?

1 comment

Thanks for your constructive comments!

W1 & Q1. Baseline Comparability

A1: We clarify that we reused published results because these methods employed the same GPT-4o-mini (GPT) backbone as our experiments. Since the backbone was identical, rerunning these evaluations was unnecessary. For methods involving different LLM backbones, we independently reran the experiments under our settings to ensure consistent evaluation conditions.

We adopted an updated LLM pool for two reasons. It reflects recent advances in LLM capabilities rather than relying on older model generations. Second, it provides a broader range of capability–cost trade-offs, which is particularly important for evaluating GraphMAC's graph-aware LLM allocation strategy. All independently rerun comparisons follow consistent model configurations, token-counting rules, and pricing assumptions.


W2 & Q2. Executable Collaboration Evidence

A2: We clarify that GraphMAC executes graph in two stages:

  • Main Execution: Agents are scheduled using Kahn's topological sorting algorithm. Chain and Criticism edges define spatial dependencies, while Debate edges also contribute to execution dependencies. Each agent is executed once after all its predecessors finish, jointly processing their outputs and interaction types in a single LLM call.
  • Focused Debate: After main execution, each retained Debate edge triggers two additional LLM calls, allowing both agents to exchange feedback based on their pre-debate outputs.
  • Termination and Aggregation: Execution terminates after the predefined rounds. A final decision agent collects all agents' outputs and performs one aggregation call using the most frequently selected LLM backbone.
  • The autoregressive generator creates edges from earlier to later nodes, naturally ensuring a DAG. An additional execution-time cycle check discards edges that would introduce cycles. When an agent participates in multiple interactions, all predecessor outputs are jointly processed in a single main-mode LLM call, with roles and interaction types preserved. Afterward, outputs are cached. For each Debate edge, both agents perform focused rebuttal calls using their opponent' s pre-debate output, ensuring symmetric information exchange.

The execution procedure is summarized below:

Initialize agent outputs and memory
Construct DAG by discarding cycle-forming edges

for each execution round:
    order = TopologicalSort(G)
    for agent in order:
        context = collect_all_predecessor_outputs(agent)
        agent.output = LLM(agent, context)

    memory = cache_all_agent_outputs()

    for (u, v) in Debate_edges:
        v.output = LLM(v, memory[u])
        u.output = LLM(u, memory[v])

y = FinalAggregator(all_agent_outputs)
return y

For the default single-round setting, the nominal number of LLM calls per query is: $ N_{\mathrm{LLM}}=|V_{\mathrm{active}}|+ 2|E_{\mathrm{Debate}}|+1, $ where the final call performs answer aggregation. All intermediate and aggregation calls are included in inference cost accounting.


W3 & Q3. Controlled Ablation Studies

A3: We provide targeted comparisons that replace only one design component at a time: GRU with mean pooling, heterogeneous interactions with a homogeneous interaction pattern, and graph-conditioned routing with a learned graph-independent router.

Table R1. Targeted Ablation of GraphMAC Components.

MBPP acc (%)MBPP cost ($)HumanEval acc (%)HumanEval cost ($)
Mean Pooling85.006.9594.530.54
Single-type Edges86.607.1292.970.64
Graph-agnostic Routing88.408.1396.090.51
GraphMAC88.807.5696.090.57

All variants retain the same LLM pool, training protocol, and cost constraints. These comparisons isolate the contributions of temporal role selection, typed communication, and topology-aware model allocation while accounting for inference-budget differences.


Q4. Comparison with Hetero-Designer

A4: Although both methods construct query-adaptive multi-agent systems, they differ in two aspects:

  • LLM allocation. Hetero-Designer jointly predicts LLM-role pairs and incoming edges autoregressively. In contrast, GraphMAC first constructs the collaboration graph and then assigns LLMs using R-GCN representations, allowing allocation to leverage the complete interaction topology.

  • Interaction modeling. Hetero-Designer primarily represents dependencies through DAG edges, whereas GraphMAC distinguishes Chain, Criticism, Debate, CoT, and Reflection, each with relation-specific transformations. This enables distinct information propagation patterns and more structured, compact interaction representations without relying solely on graph expansion.

Although unrolled DAGs offer similar execution semantics, typed interactions provide relation-specific biases for learning diverse information flows and guiding heterogeneous LLM allocation, coupling diversity-aware interactions with topology-aware routing.

Reviewer_MC1nOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GraphMAC, a query-conditioned framework for jointly selecting agent roles, constructing heterogeneous interaction graphs, and allocating LLM backbones to individual agents. It combines GRU-based autoregressive role selection, typed interactions with edge pruning, and R-GCN-based model allocation. The policy is trained using REINFORCE with task-success, diversity, and cost objectives. Experiments on five benchmarks report improvements over MasRouter, with the largest gain being 5.80 percentage points on MBPP, together with reduced inference costs on most evaluated datasets.

Critical strengths
  1. A coherent approach to joint collaboration and resource allocation. GraphMAC considers agent roles, interaction types, and LLM assignments within a unified framework. In particular, conditioning model allocation on the constructed interaction graph is a meaningful design choice: the appropriate backbone may depend on an agent’s collaborators and interaction responsibilities, in addition to its role and the query.
  2. Promising results against a directly relevant baseline. The comparison with MasRouter is informative because both methods address multi-agent routing with heterogeneous model pools. GraphMAC reports improvements across all five benchmarks, including an increase from 83.00 to 88.80 on MBPP. The reported cost reductions on most tasks also support the practical relevance of the approach.
Critical weaknesses
  1. The execution semantics of the generated graph are insufficiently specified. Section 4.2 defines local interaction operators, but the paper does not adequately explain how they compose into a complete executable workflow. Criticism includes feedback and revision, debate involves multiple exchanges, and reflection requires additional calls. When several such operators involve the same agent, their ordering, intermediate-output handling, and termination rules become consequential. The generator also lacks an explicit global acyclicity constraint or an alternative scheduling specification. Appendix A.2 summarizes execution in a single step, while the final aggregation remains an unspecified Aggregate function. These choices directly affect both answer quality and inference cost, making the main experimental procedure difficult to reproduce.
  2. The incremental contribution is not sufficiently isolated from existing methods and alternative explanations. TopoDIM, which the paper cites, already studies typed interactions, relational graph encoding, edge sparsification, and diversity-aware policy optimization. GraphMAC uses relational encoding for a different purpose—allocating LLM backbones over the constructed graph, but this distinction and its empirical benefit need a more direct evaluation. Moreover, Table 2 replaces entire modules with random strategies. Such comparisons establish the value of learned selection over random choices, but do not isolate GRU versus mean pooling, heterogeneous versus homogeneous interactions, or graph-aware versus topology-agnostic routing. The substantial cost differences between ablations further complicate attribution of the accuracy gains. TopoDIM, Sections 3.1–3.3
Questions for authors
  1. The overall pipeline is clear, but I would appreciate a bit more detail on how the generated graph is executed. For example, when an agent participates in several interactions, how are these ordered, and how are any cycles handled? A small worked example or brief pseudocode showing the execution steps, stopping rule, and final aggregation would be helpful, especially for understanding the number of LLM calls involved.
  2. I have a small clarification question about Equation 7. The self-loop term seems to sum over all self-loop types. Is this sum restricted to the types actually selected and retained for each node? I would like to better understand how choosing CoT, reflection, or no self-loop affects the representation used for model allocation.
  3. The ablations provide useful evidence that the learned components matter. To better understand the source of the gains, it would be interesting to see a few more targeted comparisons—for example, GRU versus mean pooling, or graph-aware versus topology-agnostic model allocation at similar budgets. A comparison of typed and single-type interactions, or a closer discussion of the connection to TopoDIM, could also help clarify what the proposed interaction design adds.
  4. A few additional details would make the experimental results easier to interpret. Could you clarify the train/validation/test sizes, how the MATH subset was constructed, and how hyperparameters were selected? It would also help to know whether the results are averaged over multiple runs and how much they vary. For the cost results, could you specify whether the reported amounts are per query or for the full evaluation set, and which calls and token costs are included?
1 comment

Thanks for your constructive comments!

W1. Graph Execution Semantics

A1: We clarify that GraphMAC executes graph in two stages:

  • Main Execution: Agents are scheduled using Kahn's topological sorting algorithm. Chain and Criticism edges define spatial dependencies, while Debate edges also contribute to execution dependencies. Each agent is executed once after all its predecessors finish, jointly processing their outputs and interaction types in a single LLM call. CoT and Reflection are node-level reasoning modes, requiring no additional interaction calls.
  • Focused Debate: After main execution, each retained Debate edge triggers two additional LLM calls, allowing both agents to exchange feedback based on their pre-debate outputs.
  • Termination and Aggregation: Execution terminates after the predefined rounds. A final decision agent collects all agents' outputs and performs one aggregation call using the most frequently selected LLM backbone.
  • The autoregressive generator creates edges from earlier to later nodes, naturally ensuring a DAG. An additional execution-time cycle check discards edges that would introduce cycles.

W2. Incremental Contribution and TopoDIM

A2: While TopoDIM studies typed interactions, edge sparsification, and diversity-aware optimization, GraphMAC focuses on jointly generating collaboration graphs and allocating heterogeneous LLMs. Specifically, GraphMAC introduces (1) GRU-based temporal role selection, (2) query-adaptive heterogeneous interactions, and (3) R-GCN-based per-agent LLM routing. Unlike conventional topology encoding, our R-GCN representations directly determine each agent's LLM backbone (Eq. 8). Targeted ablations in Q3 further validate these contributions.


Q1. Execution Order, Cycles, and Aggregation

A3: When an agent participates in multiple interactions, all predecessor outputs are jointly processed in a single main-mode LLM call, with roles and interaction types preserved. Afterward, outputs are cached. For each Debate edge, both agents perform focused rebuttal calls using their opponent' s pre-debate output, ensuring symmetric information exchange.

The execution procedure is summarized below:

Initialize agent outputs and memory
Construct DAG by discarding cycle-forming edges

for each execution round:
    order = TopologicalSort(G)
    for agent in order:
        context = collect_all_predecessor_outputs(agent)
        agent.output = LLM(agent, context)

    memory = cache_all_agent_outputs()

    for (u, v) in Debate_edges:
        v.output = LLM(v, memory[u])
        u.output = LLM(u, memory[v])

y = FinalAggregator(all_agent_outputs)
return y

For the default single-round setting, the nominal number of LLM calls per query is: $ N_{\mathrm{LLM}}=|V_{\mathrm{active}}|+ 2|E_{\mathrm{Debate}}|+1, $ where the final call performs answer aggregation. All intermediate and aggregation calls are included in inference cost accounting.


Q2. Self-loop Term in Equation 7

A4: The self-loop summation in Eq. (7) includes only edge types selected and retained for each node. Nodes with CoT or Reflection use the corresponding relation-specific transformation, while nodes without a retained self-loop receive no such contribution. Thus, self-loop selection directly affects the representations used for LLM allocation.


Q3. Targeted Ablation Studies

A5: We conduct targeted ablations, replacing one component at a time while keeping others unchanged.

Table R1. Targeted Ablation of GraphMAC Components.

MBPP acc (%)MBPP cost ($)HumanEval acc (%)HumanEval cost ($)
Mean Pooling85.006.9594.530.54
Single-type Edges86.607.1292.970.64
Graph-agnostic Routing88.408.1396.090.51
GraphMAC88.807.5696.090.57

These results isolate the contributions of temporal modeling, heterogeneous interactions, and topology-aware routing, while comparing accuracy and inference cost.


Q4. Clarification of Settings

A6:

  • Dataset splits. All five benchmarks use a 4:1 training–test split. Their original sizes are 12,500 (MATH), 974 (MBPP), 8,792 (GSM8K), 164 (HumanEval), and approximately 15.9K (MMLU).
  • MATH sampling. Following MasRouter, we sample 519 problems across difficulty levels to cover diverse mathematical reasoning complexity.
  • Hyperparameter selection. Search spaces and implementation settings are provided in the Implementation Details section.
  • Run variability. Across three independent seeds, GraphMAC achieves 89.65% ± 0.33% on MATH and 88.20% ± 0.72% on MBPP, close to the originally reported 89.84% and 88.80%, respectively, demonstrating stable performance.
  • Inference cost. Figure 3 reports the total cost over the full inference set. GraphMAC and MasRouter use identical model-specific input/output token prices and counting rules. Costs include all execution-stage LLM calls, including intermediate interactions, Criticism/Debate/Reflection, and final aggregation.
Reviewer_s5CdOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GraphMAC, an autoregressive, diversity-aware graph generation method. By leveraging temporal-aware node selection, diverse interaction edge construction, and graph-aware LLM routing, and jointly optimizing them via reinforcement learning, GraphMAC effectively enhances the collaborative performance of multi-agent systems while significantly reducing computational costs.

Critical strengths

1- The proposed GraphMAC systematically addresses the limitations of existing MAS routing methods—namely, the lack of temporal dependencies, homogeneous interaction patterns, and topology-agnostic routing, thereby significantly enhancing the structural expressiveness of multi-agent collaboration graphs.

2- Experiments across five mainstream datasets not only demonstrate its superior performance compared to the strongest baselines, but also highlight its significant capability in reducing inference costs.

Critical weaknesses
  1. The paper employs the REINFORCE algorithm for joint optimization but fails to adequately discuss the massive training overhead and extremely high reward variance incurred by actually invoking LLMs to compute token costs and accuracy during each policy rollout. This severely compromises the method's scalability and training stability in large-scale scenarios.

  2. Although the paper emphasizes the introduction of "structural diversity entropy" to prevent mode collapse, its ablation study (Table 2) only removes entire macro-level modules and lacks an independent empirical validation of the diversity entropy weight.

Questions for authors

1- When using the REINFORCE algorithm for policy optimization, the reward function includes costicost_i (cost) and answer correctness. Please clarify how these metrics are calculated during the training rollout phase. Are LLMs actually invoked after each sampled graph to compute the real token cost and answer correctness?

2- Since the node selection process is autoregressive and the graph allocation phase uses R-GCN for message passing, its computational complexity is closely related to the number of generated nodes nn. Please provide the average and maximum distribution of the number of agents (nn) actually selected/generated per query across the five datasets. Furthermore, how does the overall training time and GPU memory footprint of GraphMAC compare to the baseline MasRouter?

3- Figure 3 claims that GraphMAC significantly reduces inference costs compared to MasRouter. Please explicitly confirm whether GraphMAC and MasRouter used the exact same LLM pricing assumptions and token counting methods when calculating these costs, to ensure that this performance-cost trade-off comparison is absolutely fair.

3 comments

Thanks for your valuable suggestions!

W1: Training Overhead and Reward Variance

A1: GraphMAC optimizes only lightweight policy networks, without backpropagating through LLMs. Although LLM-based rollouts introduce training overhead, we employ an exponential moving average (EMA) baseline in REINFORCE to center the reward signal, reducing gradient variance across sampled graphs and improving training stability. Additionally, structural diversity entropy encourages exploration of diverse interaction patterns, mitigating premature policy collapse and complementing the variance reduction mechanism.

The training cost comparison in Table R1 demonstrates that GraphMAC achieves lower training costs than MasRouter on datasets, highlighting its superior training efficiency without additional computational overhead.

Table R1. Training Cost Comparison with MasRouter.

DatasetsMATHMBPPGSM8KHumanEvalMMLU
MasRouter17.1414.576.881.5529.82
GraphMAC9.7012.589.511.3217.78

W2. Independent Validation of Structural Diversity Entropy

A2: We respectfully clarify that Figure 5(c) already provides an independent ablation of η, which is separate from the module-level ablations. Table R2 presents the validation of the diversity entropy weight on 5 datasets.

Table R2. Ablation Study of Structural Diversity Entropy Weight η.

DatasetsMATHMBPPGSM8KHumanEvalMMLU
GraphMAC (η=0)87.8986.4094.7994.5389.58
GraphMAC89.8488.8095.5596.0990.48

Q1. Reward Computation During Training

A3: Each sampled graph is executed using its assigned LLMs during training. The reward is computed as follows:

  • Correctness: The final answer is compared with the ground truth, yielding a binary reward (1/0).

  • Cost: Input and output tokens from all agent interactions are recorded and converted into monetary cost using model-specific pricing.

  • Diversity: The normalized number of distinct edge types is calculated according to Eq. (11).

The overall reward is calculated according to Eq. (10). Importantly, reward computation requires no additional LLM calls. Answer correctness is determined by comparing the generated answer against the ground truth using the corresponding benchmark evaluation protocol, while token costs are calculated directly from the usage statistics of LLM calls during rollout. LLMs are invoked only to execute the sampled collaboration graphs, and gradients are backpropagated exclusively through the graph-generation policy, without updating the LLM backbones.


Q2. Agent Counts and Computational Complexity

A4: The average and maximum distribution of N is presented in Table R3.

Table R3. Agent Count Statistics across Five Datasets.

DatasetsMATHMBPPGSM8KHumanEvalMMLU
Avg. n4.964.664.453.824.95
Max. n65556

Training efficiency comparison on HumanEval is shown in Table R4. Both GraphMAC and MasRouter employ lightweight controller networks without locally deploying or fine-tuning large LLM backbones. GraphMAC introduces only modest training overhead, mainly due to GRU-based temporal modeling and R-GCN message passing.

Table R4. Training Efficiency Comparison.

Time (h)Peak GPU (GB)
MasRouter1.632.3
GraphMAC1.842.9

Q3: Clarification on Fairness

A5: We confirm that both GraphMAC and MasRouter were evaluated using our own implementations under identical experimental settings. Specifically, we used the same LLM pool, model-specific pricing, and token-counting methodology for both methods, ensuring a fair and consistent inference cost comparison in Figure 3.

Reviewer_s5CdOpenReview ↗

Update

Thank you for the author's detailed response, these rebuttals further increase my confidence. Hence, I maintain my positive scores and upweight my confidence scores.

We greatly appreciate your comments and recognition. We also look forward to receiving any further suggestions and advice.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.