Keeping the Communication Graph Secret: Randomized Topologies Against Adaptive Attacks on Agent Networks

When several language-model agents work together, the pattern of who talks to whom (the communication graph, or topology) largely decides how badly one compromised agent can hurt the group. A single attacker at the hub of a star network flips consensus far more often than one at a leaf. Dense graphs give an attacker many paths along which to split a malicious prompt into innocent-looking pieces. Linear chains let a single man-in-the-middle corrupt everything downstream. Almost every one of these attacks assumes the attacker knows, or can quickly learn, the graph. This proposal asks whether the defender can turn that assumption into a weakness. Suppose the defender draws the communication graph at random for each task from a distribution tuned to keep clean task accuracy high. An attacker who knows the distribution but not the draw must then craft an attack that works across topologies. Robustness becomes a question of cross-topology transferability: does an attack tuned for one graph still work on another?

The core claim is testable and could fail. We claim that the protection a randomized topology gives against a fully adaptive attacker is predicted by a measurable quantity, the cross-topology transfer matrix of attack success. We also claim a defender can search for graph distributions that sit on a better robustness-versus-clean-accuracy frontier than any single fixed graph. If an attacker who optimizes over the whole distribution recovers nearly the fixed-graph success rate, that is a clean negative result: topology secrecy is worthless, and future defenses should stop relying on it.

Where This Sits in Prior Work

Four lines of evidence motivate the proposal by showing that attack impact depends on topology and position.

Two of these attacks are explicitly topology-aware. The max-flow router needs the graph as input, and ATLAS (ATLAS) spends its first phase probing to fingerprint defenses before routing attacks through a Markov decision process over delegation paths. None of this work asks what happens when the graph the attacker plans against differs from the one deployed. The research file flags cross-topology transfer as open.

A second group constrains the design. The warm-up trust defense in Don't Trust Stubborn Neighbors is beaten by a "long-con" attacker who behaves well during profiling. That warns us that any defense relying on a secret must be tested against an attacker who can probe during the task itself. The same paper's "agreeableness trap" shows that making agents more skeptical buys robustness at the cost of collaborative accuracy. Baseline Defenses reports a roughly 10% false-positive rate for perplexity filtering, which also compounds across hops. Together these tell us that clean accuracy must be a hard constraint, not an afterthought.

A third group supplies methods.

  • CARD learns a conditional graph designer that trades task accuracy against communication cost. It reports 90.50% on HumanEval, but it was never tested against intentional attacks. We reuse its designer as the generator of our graph distribution and add a robustness term.
  • G-Safeguard detects compromised agents with a graph neural network and prunes their edges after the fact. It was not evaluated against adaptive attackers. Our proposal is preemptive where G-Safeguard is reactive.
  • Randomized smoothing for multi-agent systems randomizes agents' continuous numerical states, not the graph, and was not tested against attackers who know the noise distribution.
  • For the mechanistic side, Adversarial Vulnerability from Interference Between Features in Superposition shows that transfer jumps from 5% to 98% when models are forced into shared geometry. This is the representation-level analogue of our question, and it suggests that transfer is structured and predictable rather than noise.

Core Claim and Formulation

Let $\mathcal{G}$ be a finite family of candidate communication graphs over $n$ agents and let $P$ be a distribution over $\mathcal{G}$. Let $\mathrm{ASR}(a, G)$ be the success rate of attack strategy $a$ when the deployed graph is $G$, and let $\mathrm{Acc}(G)$ be clean task accuracy on $G$. The defender solves

$$\max_{P} \; \min_{a \in \mathcal{A}} \; \mathbb{E}_{G \sim P}\big[1 - \mathrm{ASR}(a, G)\big] \quad \text{subject to} \quad \mathbb{E}_{G \sim P}[\mathrm{Acc}(G)] \ge \mathrm{Acc}_{\mathrm{ref}} - \epsilon,$$

where $\mathcal{A}$ is the set of attacks available to an adversary who knows $P$ but not the draw, $\mathrm{Acc}_{\mathrm{ref}}$ is the clean accuracy of the best fixed graph, and $\epsilon$ is the tolerated clean-accuracy loss.

The prediction links this game to transfer. Define $T_{ij}$ as the success rate on graph $G_j$ of an attack optimized for $G_i$. If attacks are strongly graph-specific, meaning off-diagonal $T_{ij}$ is much smaller than the diagonal, then randomization helps. We predict the achievable gain over the best fixed graph scales with the gap between diagonal and $P$-weighted off-diagonal transfer. If the adversary can find a single attack with high success on every graph in the support of $P$, the gain vanishes. Measuring $T$ is therefore both the diagnostic and the design tool.

Research Program

Measuring transfer across topologies. The first stage builds the transfer matrix across the topologies used in the benchmarks: chain, tree, star, ring, random, and complete graphs, with the attacker placed at each structural role. We use three attack families that stress topology in different ways:

  • Friedkin–Johnsen persuasion hijacking, which depends on the attacker's position.
  • Max-flow fragment routing with the permutation-invariant loss of Agents Under Siege, which depends on the available paths.
  • Man-in-the-middle message tampering, which depends on having no redundant paths.

Each attack is optimized on a source graph and replayed on every target graph with the attacker's structural role mapped as closely as possible. This alone answers the open question of cross-topology transfer.

Designing the graph distribution. The second stage learns $P$. We extend CARD's conditional designer to output a distribution over edges rather than one graph. Its training objective adds a robustness term, estimated against a population of attacks from stage one, to CARD's existing accuracy and communication-cost terms. We also test a simpler constructive alternative: a mixture over a small support of hand-chosen graphs, with weights set by solving the matrix game on the measured $T$.

Fully adaptive attacks. The third stage breaks the defense. Following the lesson that non-adaptive evaluations give an illusion of robustness (Optimizing Adaptive Attacks against Content Watermarks), we give the attacker full knowledge of $P$ and test four strengthening strategies:

  • Optimizing the expected success over $P$, the standard expectation-over-transformations approach.
  • Choosing the placement that is central on average across draws.
  • An ATLAS-style probing attacker that spends queries early in a task to infer the realized graph before committing.
  • A long-con attacker that behaves honestly until it has located itself in the draw.

Resampling frequency is a defender knob. We draw a new graph per task, per deliberation round, or per message. Faster resampling defeats in-task probing but may cost clean accuracy, and we measure that cost directly.

Baselines

The naive reference point is the fixed topology each benchmark ships with: the star and complete graphs of the Friedkin–Johnsen testbed, the dense graphs of Agents Under Siege, and the chains of MetaGPT and ChatDev. We evaluate it under the same attacks and backbones as every other condition. Known anchors on these fixed graphs are the 0.65 hub success rate reported in Don't Trust Stubborn Neighbors and the up-to-94% distributed-jailbreak success reported in Agents Under Siege.

The most important competitor is the best fixed graph. For each clean-accuracy floor we choose, by exhaustive search over $\mathcal{G}$, the single deterministic graph with the lowest worst-case success rate against a topology-aware attacker. We give it the same attack suite and the same number of evaluation episodes. It is the strongest competitor because the whole claim is that randomness beats the best deterministic choice. If a single sparse tree matches our distribution's frontier, the proposal fails. No reported result was found on Lacuna for this search, so we compute it ourselves.

The strongest existing defenses are the following, each run on shared backbones and task sets with the same tuning budget in detector threshold sweeps:

  • G-Safeguard's reactive pruning. It reports about a 22% reduction in success rate for prompt injections on MMLU and recovery of over 40% of attack-induced performance loss (G-Safeguard). We retrain its detector on our message traffic and also attack it adaptively, which its authors did not do.
  • The warm-up plus sparse trust defense from Don't Trust Stubborn Neighbors, for which no single reported success rate was found on Lacuna beyond its described "partial recovery."
  • CARD run without a robustness term, which represents the clean-accuracy ceiling of adaptive graph design. Its reported HumanEval accuracy is 90.50% (CARD).

Beating the baselines means the following. At matched clean accuracy on HumanEval, MMLU and CommonsenseQA, within $\epsilon$ of the best fixed graph and with $\epsilon$ reported at 1 and 3 points, our distribution must lower worst-case success under the strongest adaptive attacker. The margin must be outside the confidence intervals of repeated runs, relative to both the best fixed graph and G-Safeguard.

Two ablations isolate the key ingredient. The first is uniform random edge dropout at the same expected density, which tests whether the learned distribution matters or any randomness helps. The second tells the attacker the realized draw, which separates the protection that comes from secrecy from the protection that comes from the structures in the support of $P$.

Why not just…?

Why not just pick one sparse, well-chosen topology? This is the most serious alternative, and the best-fixed-graph baseline tests it directly. Prior evidence cuts both ways. Chains are nearly fully exploitable by message interception (Red-Teaming via Communication Attacks), stars expose the hub, and complete graphs expose fragment routing. Because different attacks favor different graphs, no single graph looks best against all of them. CARD also reports that rigid graphs underperform adaptive ones on clean tasks. Still, if a single tree matches our frontier, we will report that and conclude that secrecy adds nothing.

Why not just put a global monitor that reads every message? A global filter would reassemble the fragments that local Llama-Guard filters miss in Agents Under Siege, so it is a real threat against that attack. It does not address persuasion hijacking or delegation laundering, where each message is benign in isolation (ATLAS). It also adds a single point of failure and a false-positive tax like the roughly 10% reported in Baseline Defenses. We include a global Llama-Guard monitor as a comparator on all three attack families and test its combination with randomization. The combination may be the practical answer.

Why not just randomize messages or states, as in randomized smoothing? Randomized smoothing for MAS perturbs continuous states and multiplies queries. It has not been shown for text, and it was not tested against distribution-aware attackers. Graph randomization costs no extra queries per message. The uniform edge-dropout ablation is our closest analogue and shows whether structured randomness is needed.

Why not just harden each agent with adversarial training? Robust-refusal training such as R2D2 (HarmBench) targets single endpoints. ATLAS reports that strong instruction-followers readily execute harmful requests from internal peers, and superposition results suggest shared geometry survives alignment. Graph randomization is complementary to such training. As one condition we run a hardened backbone, if one is available, to check that gains persist.

Proposed Experiments and Decisive Checks

We will use the following testbeds:

  • The Friedkin–Johnsen deliberation testbed of Don't Trust Stubborn Neighbors on CommonsenseQA and MMLU-Pro, scaled from 6 agents to 12 so that the graph family is non-trivial.
  • The distributed-jailbreak setting of Agents Under Siege on JailBreakBench, scored with the HarmBench classifier.
  • The prompt-injection setting of G-Safeguard with InjecAgent payloads on MMLU and GSM8K.
  • Clean accuracy measured on HumanEval, MMLU and MATH using CARD's protocol.

The backbones are open models: the Llama, Mistral and Qwen families used across these papers.

Metrics are:

  • Worst-case attack success over the adaptive suite.
  • Clean accuracy.
  • Messages and tokens per task.
  • The full robustness-versus-accuracy frontier traced by sweeping $\epsilon$ and resampling frequency.

The first decisive check is whether off-diagonal transfer in $T$ is substantially below the diagonal for at least two of the three attack families. If it is not, randomization cannot help and we stop there with a transfer study.

The second check is whether the expected-over-$P$ adaptive attacker and the in-task probing attacker leave a gap over the best fixed graph at matched clean accuracy. The third is whether the gap measured in the matrix game on $T$ predicts the gain actually realized under those attackers, which tests the mechanistic claim.

The fourth check asks what per-round resampling, the setting needed to defeat probing, costs in clean accuracy relative to per-task resampling. This quantifies the agreeableness-trap analogue at the level of the graph rather than the individual agent.