acceptodds
Under review as a conference paper at ICLR 2027

Task-Oriented Learning of Dynamic Communication Graphs for Multi-Round LLM Agents

Abstract

Multi-round LLM-based multi-agent systems solve tasks through repeated inter-agent communication, making who communicates with whom at each round consequential to the final answer. Most existing methods either fix the communication graph at inference or sample edges from behavior-independent distributions, preventing the topology from responding to evolving agent behavior. We introduce TodyComm, a task-oriented policy that constructs constrained, directed acyclic communication graphs conditioned on the unfolding interactions. The resulting graph policy is optimized end-to-end using the final task reward. We evaluate TodyComm in a dynamically adversarial setting, a controlled instance of shifting graph distributions, where agents may silently become unreliable at unknown rounds. Across six benchmarks, TodyComm outperforms fixed-graph and behavior-independent graph-learning baselines while retaining generalizability.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM-based multi-agent systems, dynamic communication topology, multi-agent collaboration, graph structure learning, reinforcement learning

Reviews

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

TodyComm learns how agents should communicate as their behavior changes during a task. A recurrent controller assigns each agent a score, which is used to select participants, construct communication graphs, and choose the final answer. It is trained with the final task reward and evaluated on six benchmarks with agents that become unreliable during interaction.

Critical strengths
  • Adapting communication to observed behavior is a sensible and useful design. The method does not need labels identifying malicious agents or examples of the correct communication graph. This makes the approach more appealing than one that depends on knowing the failure type beforehand.

  • The experiments examine several important aspects of the method. Tests across attack mechanisms, agent counts, tasks, and model backbones provide reasonably broad support within the studied setting. The comparison with a more flexible edge-scoring model also helps justify the simpler node-score design.

Critical weaknesses
  • The theory assumes much of what the learning method needs to achieve. It assumes that the learned node scores are accurate and leaves the loss from greedy graph construction as an uncontrolled term. It therefore offers a conditional explanation, but does not establish that RL learns a good graph or adapts successfully after behavior changes.

  • The specific contribution of communication learning remains partly unclear. Section 5.5 shows that replacing learned final-answer selection with majority voting causes a very large performance drop. The ablation is useful, but it also shows that the gains cannot be attributed to communication graphs alone. A comparison using the same final-answer selection rule would better establish the value of the central contribution.

Questions for authors
  • How much improvement remains when competing communication methods use the same final-answer selection rule and a comparable token budget?

  • Is there evidence that the node scores actually learned by RL satisfy the theory’s approximation assumptions closely enough to give a useful bound in the main experiments?

Reviewer_gp53OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TodyComm, a policy for adapting communication graphs in multi-round LLM agent systems to agents' observed behavior. A graph recurrent network produces scalar node potentials from previous outputs and neighborhood information. These potentials guide node screening, constrained construction of directed acyclic communication graphs, and final-answer selection. The policy is trained with REINFORCE using final task rewards. Evaluation focuses on agents that become adversarial during an interaction and covers six benchmarks, multiple LLMs, and several transfer settings. The paper also provides a conditional regret decomposition for graph construction.

Critical strengths
  1. Substantial empirical gains under changing agent reliability. The problem is well motivated, and the reported improvements are substantial at higher adversarial fractions. At the 50% attack rate in Table 3, TodyComm achieves 67.32% on MMLU and 49.39% on MBPP, compared with 44.44% and 31.71% for the strongest listed baselines. The larger MMLU evaluation, additional models, and transfer experiments strengthen the empirical contribution. These results provide the main support for acceptance.

  2. Meaningful separation of communication and final selection. Section 5.5 reports 67.32% for full TodyComm on MMLU/Qwen3-8B at the 50% attack rate, compared with 51.63% when communication is replaced by a fully connected graph and 20.26% when final selection is replaced by majority voting. This analysis supports a contribution from both components and provides evidence beyond final-answer filtering alone.

Critical weaknesses
  1. The training procedure needs more detail. Algorithm 3 combines Bernoulli sampling, exploration flips, and score-based graph construction, but the paper does not clearly explain their treatment in REINFORCE or how final-answer selection is trained.

  2. The adaptation ablation is limited. Section 5.5 evaluates the communication and decision components only on MMLU/Qwen3-8B at a 50% attack rate, without separating round-3 and round-4 transitions.

  3. The theoretical guarantee is limited. Theorem 1 assumes accurate scalar-potential estimates and leaves the greedy construction loss as a residual, rather than bounding it for Algorithm 4.

Questions for authors
  1. Please provide the full REINFORCE loss, including how exploration flips and final-answer selection are handled.

  2. For the component ablation in Section 5.5, could you report round-3 and round-4 transitions separately and clarify whether each variant was retrained?

Reviewer_zYkvOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the role of communication topology in multi-agent debate and introduces TodyComm, which adapts the topology at each round based on agents’ interaction histories. In contrast to approaches that maintain a fixed topology throughout an entire interaction, TodyComm uses reinforcement learning to optimize history-conditioned node potentials that jointly guide agent participation and constrained edge construction. Furthermore, the paper provides a theoretical analysis of this design under stated assumptions and evaluates the method across multiple benchmarks in dynamic adversarial settings, examining its effectiveness when agents’ behavior changes over the course of an interaction.

Critical strengths

1. Theoretical Analysis of TodyComm. TodyComm connects its structured approach to learning round-adaptive communication graphs with a theoretical analysis that bounds the suboptimality of the constructed graphs under stated assumptions.

Critical weaknesses

1. Justification for Assumption 3. While a bounded approximation error is a reasonable analytical assumption, it remains unclear whether the proposed training procedure yields node potentials that approximate the latent potentials accurately enough for the resulting bound to be informative. Further theoretical justification or empirical evidence assessing this approximation would help clarify the practical relevance of the guarantee.

2. Quality of Presentation. The presentation could benefit from a more balanced organization and clearer progression of ideas. For example, a substantial amount of information is concentrated on the final page of the main text, and the connections between methodological choices, theoretical justification, and empirical findings are sometimes difficult to follow. Redistributing this material and making these connections more explicit would help readers understand and assess the contributions.

Questions for authors
  1. While a bounded approximation error is a reasonable analytical assumption, it remains unclear whether the proposed training procedure yields node potentials that approximate the latent potentials accurately enough for the resulting bound to be informative. Further theoretical justification or empirical evidence assessing this approximation would help clarify the practical relevance of the guarantee.

  2. Have the authors assessed how consistently agents follow the intended adversarial instructions after the designated transition? For example, how often do they produce the specified incorrect answer together with misleading reasoning supporting it? Is there a metric or qualitative analysis examining this behavior? To clarify, my question concerns the adversarial agents’ own adherence to these instructions, rather than their effectiveness in corrupting other agents’ answers.

Comments on the paper

1 comment

Hi everyone, please acknowledge the authors’ rebuttal with a brief reply, even if your assessment is unchanged (if you already did or are about to do so, please ignore this message).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.