🔢 mathematics

Securing Multi-Agent Systems Against Corruptions via Node Contribution Backpropagation

This paper proposes a dynamic defense paradigm called Node Contribution Backpropagation that models multi-agent system communication as a signed directed acyclic graph to compute individual agent contributions via backward propagation, thereby enabling the accurate identification and isolation of malicious agents to secure collaborative tasks against adversarial corruptions.

Original authors: Chengcan Wu, Zhixin Zhang, Mingqian Xu, Zeming Wei, Meng Sun

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chengcan Wu, Zhixin Zhang, Mingqian Xu, Zeming Wei, Meng Sun

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

The Problem: The "Bad Apple" in the Group Chat

Imagine a team of expert AI assistants working together to solve a difficult puzzle, like a group of detectives trying to solve a crime. This is called a Multi-Agent System (MAS). They talk to each other, share clues, and vote on the final answer.

The problem is that one of the detectives might be a "bad actor" (a malicious agent). Instead of helping, this bad actor whispers false information to the others. Because the team trusts each other, the lie spreads like a virus. One detective believes the lie, tells another, and soon the whole team is convinced of a false conclusion. This is called a corruption attack.

Existing defenses are like security guards who only look at the content of what people say. If a bad actor says something that sounds reasonable but is actually a lie, the guards miss it. Other defenses look at the team's structure but assume the team never changes its members or roles, which isn't true in the real world.

The Solution: The "Scorecard Backward" Method

The authors propose a new method called BPD (Backward Propagation Detection). Think of it as a smart detective who doesn't just listen to what people say, but traces the influence of every single word back to the final verdict.

Here is how it works, step-by-step:

1. Drawing the Map (The DAG)

First, the system draws a map of the conversation. Imagine a timeline where every time an agent speaks, it's a new stop on a train line.

Nodes: The stops (agents at specific times).
Edges: The tracks connecting them (who spoke to whom).
Signs: Every track has a sign: Green (+1) if the listener agreed, Red (-1) if they disagreed, or Gray (0) if they ignored it.

This creates a "Signed Directed Acyclic Graph" (a fancy way of saying a one-way map with colored tracks).

2. The "Backward Propagation" (Tracing the Ripple)

Usually, we think forward: "I said X, so you said Y."
BPD works backward. It starts at the very end, with the final answer the team decided on.

The Question: "Who actually pushed us toward this final answer?"
The Math: The system runs a calculation (similar to how Google's PageRank ranks websites) backward from the final answer to the beginning.
The Logic:
- If the final answer is correct, agents who agreed with the right path get a high score.
- If an agent pushed the team toward a wrong answer, they get a low (or negative) score.
- Crucially, if a bad actor tricks a good agent, the bad actor's "influence score" gets passed down the chain. The system calculates exactly how much credit or blame each agent deserves for the final result.

3. Spotting the Outliers

Once everyone has a score, the system looks for the odd ones out.

Imagine a classroom where everyone gets a score of 80, except one student who gets a -50. That student is likely the troublemaker.
BPD flags agents whose scores deviate wildly from the group average. These are the malicious agents.

4. The "Surgery" (Repairing the Graph)

Once the bad agent is identified, the system performs "surgery." It cuts the communication lines coming from that bad agent. It essentially says, "Ignore everything this person said." The team then re-runs the conversation without that bad influence to get the correct answer.

Why This is Better (The Results)

The paper tested this method against various "attacks" where bad actors tried to trick the team in different ways:

The "Subtle Lie": Changing just a few words to make a wrong answer look right.
The "Safety Trap": Pretending a normal question is dangerous to stop the team from answering.
The "Moving Target": Changing the team structure or the bad actor's identity mid-conversation.

The Findings:

Accuracy: BPD caught malicious agents over 90% of the time, beating all other existing methods.
Resilience: Even when the team structure changed (dynamic graphs), BPD kept working perfectly, while other methods failed.
Speed: The method is very fast. It only adds about 10% extra time to the conversation, which is a small price to pay for security.
No Training Needed: Unlike other methods that need to be "taught" what a bad agent looks like (which takes time and data), BPD figures it out on the spot just by looking at the conversation flow.

Summary Analogy

Imagine a group of friends trying to decide where to eat dinner.

Old Defense: A friend checks if everyone's menu choice looks "safe." A sneaky friend could suggest a terrible restaurant that looks safe, and the group goes there.
BPD: A friend looks at the final decision ("We are going to Pizza Place"). They trace back: "Who suggested Pizza? Who agreed? Who disagreed?" They realize that one friend kept pushing for Pizza despite everyone else saying they hated it, and that friend's suggestions led to a bad outcome. The group then ignores that friend's suggestions for the next decision.

This paper proves that by mathematically tracing who influenced the final decision, we can spot and remove the "bad apples" in AI teams, keeping the whole system safe and accurate.

Technical Summary: Securing Multi-Agent Systems Against Corruptions via Node Contribution Backpropagation

Problem Statement

Multi-Agent Systems (MAS) utilizing Large Language Models (LLMs) have become a prevalent paradigm for complex tasks such as software engineering and market analysis. However, the structural complexity of MAS introduces unique security vulnerabilities distinct from single-agent attacks. Specifically, MAS are susceptible to corruption attacks, where adversarial agents inject misleading information that propagates contagiously through the system. Unlike attacks targeting individual LLMs, these attacks exploit the collaborative nature of MAS, causing cascading failures where benign agents are corrupted by the malicious influence of a single compromised node.

Existing defense mechanisms face significant limitations:

Output-based defenses (e.g., multi-round debates, output similarity checks) are vulnerable to subtle textual perturbations and can be bypassed if attackers target the evaluator.
Graph-based defenses often rely on static topologies or local signals (e.g., training classifiers on local states). These fail to capture the global propagation of corrupted information to the final decision and cannot adapt to dynamic environments or evolving attack strategies.

Methodology: Backward Propagation Detection (BPD)

The authors propose Backward Propagation Detection (BPD), a dynamic defense paradigm that models MAS communication as a signed directed acyclic graph (DAG) to globally analyze agent influence. The methodology consists of four key stages:

1. Graph Reconstruction (Signed DAG)

The MAS interaction is modeled as a temporal DAG where:

Nodes represent agents at specific communication rounds ( $A_t^{(i)}$ ).
Edges represent messages sent between agents.
Edge Weights are signed scores ( $g_{ij} \in \{-1, 0, 1\}$ ) determined by an external, independent LLM evaluator. These scores indicate whether the receiver agrees with ($1$), disagrees with ($-1$), or finds low contribution from ($0$) the sender's message.

2. Signed Influence Operator

A signed propagation operator $B = D^{-1}G$ is defined, where $G$ is the signed edge-weight matrix and $D$ is the out-degree diagonal matrix. This operator quantifies the signed influence of one agent on another, normalized by the receiver's out-degree.

3. Backward Score Propagation

The core innovation is a backward propagation mechanism that computes each agent's contribution to the final decision:

Initialization: The terminal layer (final answer) is initialized with $+1$ if an agent's output matches the final decision, and $-1$ otherwise.
Propagation: Scores are propagated backward from the final round ( $T$ ) to the initial round ($1$) using the chain-rule structure of the DAG. The contribution score $S(C_i)$ for a node is the weighted sum of its successors' scores.
Mechanism: This process aggregates both local agreement and downstream impact in a single efficient pass, analogous to a signed, layer-wise PageRank on a DAG.

4. Outlier Detection and Mitigation

Aggregation: Per-agent contribution scores are averaged across all rounds.
Detection: Agents with contribution scores deviating significantly from the majority (measured by pairwise deviation $\Delta(i)$ exceeding a threshold $\epsilon$ ) are flagged as malicious.
Repair: The system is repaired by pruning (removing) all outgoing communication edges from the detected malicious agents, effectively isolating the corruption source.

Key Contributions

Signed DAG Formulation: The paper introduces a principled, global modeling of MAS communication as a signed DAG, addressing the limitation of existing defenses that rely solely on local signals.
Backward Propagation Method: A novel algorithm is proposed to reliably evaluate agent contributions by tracing signed cumulative influence from the final decision back to the source, enabling the identification of latent malicious agents without offline training.
Empirical Validation: Comprehensive experiments demonstrate that BPD outperforms existing baselines (e.g., G-Safeguard, AgentXposed) across diverse MAS architectures (Flat and Hierarchical), backbone models (GPT-4o, DeepSeek-V3), and attack types.

Experimental Results

The authors evaluated BPD on knowledge question-answering (MMLU) and open-ended generation tasks (Alpaca, Samsum, ChatDoctor) under five representative corruption attacks (Harmful, Suboptimal, Reframing, Trigger, Modification).

Accuracy Improvement: BPD improved task accuracy by 3% to 7% across benchmarks compared to the strongest baselines. In Flat and Hierarchical structures, it improved accuracy by 10% and 8% respectively under attack.
Detection Performance: BPD achieved over 90% average detection accuracy for malicious agents, significantly outperforming baselines. Notably, on "Modification" attacks (subtle semantic changes), BPD secured gains of 16% and 10% over baselines, which struggled to detect these stealthy perturbations.
Dynamic Adaptability: In dynamic scenarios where graph structures and attacker identities change over time, competing defenses degraded by an average of 3%, whereas BPD maintained its performance, confirming its adaptability.
Efficiency: The method incurs less than 10% additional time overhead (approx. 9-10.6%) compared to standard MAS, as it relies on lightweight external scoring rather than iterative convergence or retraining.
Robustness: BPD remained robust against System-Aware (SA) adaptive attacks, where attackers possess knowledge of the defense mechanism, maintaining average accuracy between 83% and 85%.

Significance and Claims

The paper claims that BPD provides an effective "guardrail" for trustworthy MAS deployment by shifting the defense paradigm from static, local analysis to dynamic, global reasoning.

Adaptability: Unlike static defenses, BPD does not require retraining when the topology changes, making it suitable for evolving MAS environments.
Interpretability: The signed propagation operator offers a transparent mechanism for tracing influence, directly reflecting an agent's cumulative impact on the final decision.
Practicality: The method achieves high security with minimal computational cost, making it viable for real-world deployment.

The authors conclude that structural and dynamic analysis is critical for securing collaborative AI systems and that their approach paves the way for more robust, topology-aware protection strategies. Future work is suggested to explore adaptive threshold mechanisms and real-time detection in larger-scale deployments.