🤖 AI

TodyComm: Task-Oriented Dynamic Communication for Multi-Round LLM-based Multi-Agent System

The paper introduces TodyComm, a task-oriented dynamic communication algorithm that optimizes multi-round LLM-based multi-agent collaboration by adaptively generating behavior-driven topologies via policy gradient, thereby outperforming fixed-structure methods in dynamic adversarial and bandwidth-constrained environments while maintaining token efficiency and scalability.

Original authors: Wenzhe Fan, Tommaso Tognoli, Henry Peng Zou, Chunyu Miao, Yibo Wang, Xinhua Zhang

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wenzhe Fan, Tommaso Tognoli, Henry Peng Zou, Chunyu Miao, Yibo Wang, Xinhua Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of experts trying to solve a difficult puzzle together. In a perfect world, they would all talk to each other, share their ideas, and combine their knowledge to find the best answer. This is how many current AI systems work: a team of "agents" (AI models) collaborating over several rounds to solve a problem.

However, the paper points out a major flaw in how these teams currently operate. Most systems use a fixed communication plan. It's like a meeting where everyone is forced to sit in the same seats and talk to the same people, no matter what happens. If one person in the room starts giving bad advice (or is secretly trying to trick the group), the fixed plan doesn't change. The group keeps listening to the troublemaker, leading to a wrong answer.

The authors of this paper propose a new system called TodyComm (Task-Oriented Dynamic Communication). Think of TodyComm not as a rigid meeting schedule, but as a smart, shifting dance floor.

The Core Idea: A Dynamic Dance Floor

In a traditional system, the "dance partners" (who talks to whom) are decided once at the beginning and never change.

In TodyComm, the dance partners change every single round based on who is dancing well and who is stepping on toes.

The Problem: Sometimes, an agent (a team member) might start acting strangely. Maybe they are tired, confused, or even a "saboteur" trying to lead the group astray. In a fixed system, the group keeps listening to them.
The TodyComm Solution: The system watches the agents' behavior in real-time. If Agent A starts giving confusing or wrong answers, TodyComm instantly cuts the connection. Agent A is no longer allowed to talk to the rest of the team. Meanwhile, it strengthens the connections between the agents who are giving good, reliable answers.

How It Works (The "Magic" Behind the Scenes)

The paper describes this process using a few clever tricks:

The "Reputation Score" (Node Potentials):
Imagine every agent has a hidden "reputation score" that updates after every round. If an agent gives a good answer, their score goes up. If they give a bad or misleading answer, their score drops. TodyComm uses a special memory network (called a GRN) to remember an agent's history, so it knows if someone is consistently reliable or if they just had a bad day.
The "Smart Filter" (Dynamic Topology):
Instead of letting everyone talk to everyone, the system builds a new "map" of connections for every round. It asks: "Who should talk to whom right now to solve this specific problem?"
- If the team is facing a math problem, it might connect the "math expert" to the "logic checker."
- If a saboteur appears, the system effectively puts them in a "timeout," cutting off their lines of communication so they can't poison the group's thinking.
Learning by Doing (Reinforcement Learning):
The system doesn't just guess who to trust; it learns. It tries different connection patterns and sees which ones lead to the correct answer. Over time, it gets very good at spotting the "bad apples" and isolating them, while boosting the "good apples."

Why It Matters: The "Saboteur" Test

The researchers tested this in a very tough scenario: Dynamic Adversarial Settings.
Imagine a team of 6 agents. In the middle of the conversation, 3 of them suddenly decide to act as "saboteurs." They don't just give wrong answers; they give plausible-sounding but wrong answers designed to trick the others.

Old Systems: Because they stick to a fixed plan, they keep listening to the saboteurs. Their accuracy drops dramatically (sometimes by over 50%).
TodyComm: It notices the shift in behavior. It quickly reorganizes the team, silencing the saboteurs and letting the reliable agents take the lead. Even when half the team is trying to trick them, TodyComm still finds the right answer.

The Benefits

Efficiency: It doesn't waste time listening to people who aren't helping. This saves "tokens" (the computational cost of generating text), making the system faster and cheaper to run.
Flexibility: It works whether the team is small or large, and whether the problem is about science, math, or general knowledge.
Resilience: It can handle situations where the "bad actors" change their tactics or appear at different times.

In Summary

TodyComm is like a team captain who is incredibly observant. Instead of following a rigid script, this captain watches the team's performance round-by-round. If someone starts messing up or trying to trick the group, the captain instantly changes the seating arrangement to exclude them and focuses the group's energy on the members who are doing the right thing. This allows the team to solve complex problems even when the environment is chaotic or hostile.

Technical Summary: TodyComm

Problem Statement

Existing multi-round LLM-based multi-agent systems (MAS) typically rely on fixed communication topologies during inference. While effective in static environments, these fixed graphs fail to adapt to dynamic scenarios where agent roles, reliability, or environmental constraints (such as communication bandwidth) change across interaction rounds. Specifically, in dynamically adversarial settings, agents may transition to adversarial behavior at unknown rounds, producing plausible but misleading analyses. Fixed topologies cannot isolate these unreliable agents in real-time, leading to significant performance degradation. Furthermore, existing dynamic approaches often lack task-level feedback (utility) or require impractical adversarial labels during training.

Methodology: TodyComm

The authors propose TodyComm (Task-Oriented Dynamic Communication), a framework that learns behavior-driven, round-adaptive communication topologies for multi-round LLM-based MAS. The core methodology involves formulating the multi-agent interaction as a Markov Decision Process (MDP) and optimizing the communication structure via Reinforcement Learning (RL).

1. MDP Formulation

Episodes: Solving a query $q$ over $T$ interaction rounds.
Actions: The sequence of inter-agent communication graphs $G^t_C$ for rounds $t \in [2, \dots, T]$ and the final decision graph $G_D$ at round $T+1$ .
State: The collective responses of all agents $\{o^t_i\}$ , the query $q$ , and historical context.
Reward: The task utility (e.g., accuracy) of the final aggregated answer.
Objective: Maximize expected task utility $E[U_q(\tau)]$ by learning a policy $\pi_\theta$ that constructs optimal communication graphs.

2. Dynamic Edge Optimization

TodyComm learns to select edges based on agent behavior rather than static rules.

Node Embeddings: A Gated Recurrent Network (GRN) aggregates information across rounds, capturing temporal dependencies, individual agent behavior, and relational context. Node features $f^t_i$ are constructed from self-information, neighborhood information, and difference information (disagreement metrics).
Scalar Potentials: Instead of directly optimizing discrete edges, the model learns scalar node potentials $c^t_i \in [0, 1]$ via an MLP. These potentials represent the "communication potential" of an agent at a given round.
Constrained Graph Construction: The communication graph is constructed by:
1. Screening: Filtering nodes with low potentials to reduce the search space.
2. Greedy Edge Selection: Iteratively adding edges between high-potential nodes based on the product of their potentials ( $c^t_i c^t_j$ $c_{i}^{t} c_{j}^{t}$ ), subject to constraints:
  - DAG Constraint: The graph must be a Directed Acyclic Graph.
  - Degree Budgets: Node-wise limits on incoming ( $B_{in}$ ) and outgoing ( $B_{out}$ ) edges to control token usage.
  - Edge Masks: Predefined constraints on permissible connections.

3. Theoretical Guarantees

The paper provides a theoretical bound on the regret (loss in utility) of the learned graph compared to the optimal graph. The regret is bounded by the sum of:

Screening Regret: The utility lost by excluding potentially useful nodes during the screening phase.
Estimation Loss: Errors in estimating the scalar potentials.
Edge-Additivity Loss: Deviations from the assumption that task utility is approximately additive over edges.

Key Contributions

First Task-Oriented Dynamic Topology: TodyComm is the first framework to learn dynamic communication topologies driven by agent behavior and task utility in multi-round LLM-based MAS, adapting structures during both training and inference.
Robustness to Dynamic Adversaries: The method effectively handles scenarios where agents transition to adversarial behavior at unknown rounds, dynamically isolating them to preserve system performance.
Token Efficiency and Scalability: By enforcing degree budgets and pruning unreliable connections, TodyComm achieves high task accuracy with significantly reduced token consumption compared to fixed-topology baselines.
Generalization: The framework demonstrates strong generalization across varying numbers of agents, attack mechanisms (targeted vs. untargeted), attack outbreak modes, and task domains.

Experimental Results

Experiments were conducted on five benchmarks (MMLU, ARC-Challenge, GSM8K, OpenBookQA, MedQA) under various attack rates (<50%, =50%, >50%).

Performance: TodyComm consistently outperforms baselines (Random Graph, Complete Graph, G-Designer, AgentPrune). Under high attack rates (>50%), it achieves significantly higher accuracy (e.g., 64.71% vs. 45.97% on MMLU).
Token Efficiency: TodyComm matches or exceeds the token efficiency of pruning-based methods like AgentPrune while maintaining superior accuracy. It reduces token usage by up to 27% on OpenBookQA under budget constraints.
Stability: The method exhibits low variance across random seeds and converges rapidly during training without overfitting.
Scalability: Performance remains stable as the number of agents increases from 6 to 20, provided reasonable degree budgets are applied.
Generalization: The model generalizes well when trained on fewer agents, different datasets, or different attack mechanisms, and evaluated under mismatched conditions.

Significance and Claims

The paper claims that TodyComm addresses a critical gap in multi-agent research: the inability of existing systems to adapt communication structures to evolving agent behaviors and dynamic constraints. By framing topology selection as a task-driven optimization problem, TodyComm enables systems to maintain robustness and efficiency in realistic, unpredictable collaborative environments. The authors emphasize that their approach moves beyond static or heuristic graph designs, offering a principled, learnable mechanism for coordinating LLM agents that is both theoretically grounded and empirically validated across diverse reasoning tasks and adversarial settings. The work is presented primarily as a research advancement in robust and efficient multi-agent collaboration, with future work suggested for extending these dynamic graph capabilities to non-adversarial collaborative scenarios.