When Local Monitors Miss Compositional Harm: Diagnosing Distributed Backdoors in Multi-Agent Systems

🕒 Published (v1): 2026-07-13 16:08 UTC · Source: Arxiv · link

Why this paper was selected

Exposes fundamental hole in per-step MAS monitors; critical for safe multi-agent deployment

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Local runtime monitors in multi-agent LLM systems share a fundamental blind spot: a distributed backdoor can split a malicious payload across agents so every per-step check passes while the assembled output is an executable attack. The paper formalizes this as an observability boundary, proves it is information-theoretically unavoidable for locally indistinguishable fragments, and demonstrates it empirically across three testbeds. Recovery requires reaching the representation in which the payload is exposed—wider observation windows alone are insufficient.

Problem

Multi-agent and tool-using LLM deployments commonly defend with per-step monitors that score each message or tool call independently. This evaluation paradigm conflates two different things: catching split fragments that still leak suspicious tokens, and catching harms that form only after composition. When every fragment is locally benign—statistically indistinguishable from normal traffic—no local monitor can detect the attack however powerful it is. This gap is unaddressed by existing prompt-injection detectors, taint trackers, or trained classifiers.

Method

The paper formalizes the observability boundary via two conditions:

1. Local benignness (Definition 1): \(h(v(x_i)) = 0\) for all \(i\), yet \(h(C(x_1,\ldots,x_K)) = 1\), where \(v\) is the monitor's observation function and \(C\) is the assembly composition.
2. \(\varepsilon\)-local indistinguishability (Definition 2): \(\mathrm{TV}(P^v_{\mathrm{ben},i}, P^v_{\mathrm{att},i}) \le \varepsilon\) at every fragment position.

Proposition 1 proves that under these conditions, any (possibly randomized) detector restricted to a single local observation achieves per-fragment detection advantage at most \(\varepsilon\): \(\mathrm{TPR} - \mathrm{FPR} \le \varepsilon\).

The empirical design uses a locality sweep: the assembled payload (credential exfiltration code, \(K{=}3\) fragments) is held fixed while a single dial varies how much evidence each fragment exposes—from visible source-to-sink edges and suspicious encodings down to completely benign-looking carrier text. Detection is measured as per-step AUROC and end-to-end attack-success rate (ASR) under six monitor types spanning local, taint, marker-based assembly, marker-free assembly, codec-blind, and decoded-view access (Table 1). A marker-free one-class model trained only on benign traffic and evaluated in leave-one-family-out (LOFO) protocol tests whether assembled code structure is recoverable without attack supervision. Four testbeds are used: R-Judge, Collaborative Shadows (main controllable bed), AgentDojo (external shipped detector), and DemonAgent (second independent codec).

Key Contributions

• Formal definition of the observability boundary: the hard failure case is local benignness + local indistinguishability, not splitting per se; Proposition 1 makes the detection limit exact in total-variation terms.
• A controllable testbed (based on Collaborative Shadows) with a single dial over local evidence, separating three failure modes: visible edges, local artifacts, and locally benign fragments.
• Demonstration that changing what the monitor observes—not training a stronger classifier—is the only route to recovery; a marker-free one-class assembly monitor trained on benign traffic achieves 0.874 mean AUROC across held-out encoding families.
• Identification that breadth without the right representation fails: codec-blind full-trace monitors and LLM-based reconstruction probes (DeepSeek-V4-Flash) block 0/50 and 6/50 attacks respectively; only the decoded-view gate (given the encoding family) blocks 50/50 across all tested models and codecs.
• Generalization to a second independent codec (DemonAgent dynamic encryption), confirming the boundary is codec-agnostic.

Results

• R-Judge artifact check: a length-only classifier (no content) reaches AUROC 0.940, nearly matching a full content classifier, then collapses to chance under length-matched attacks—showing benchmark scores can be misleading.
• Locality sweep (Collaborative Shadows): taint/provenance AUROC falls to chance once the visible source-to-sink edge is removed; per-step AUROC degrades as fragments become more natural; marker-based assembly AUROC stays high while assembled structure is recoverable (Figure 2).
• AgentDojo (external detector): shipped neural detector achieves per-step AUROC 0.82–0.84 on naively split attacks, but collapses to ≈0.50 under locally benign fragments; cross-fragment coordination view restores AUROC to 1.000 (Table 2).
• Marker-free assembly recovery (LOFO): one-class benign-only model achieves 0.874 mean AUROC across held-out encoding families (including F_none, the no-marker family); supervised assembly monitor reaches 1.000; per-step baseline stays at ≈0.49 (Figure 3).
• End-to-end ASR under local views vs. decoded-view gate (n=50 per cell, 5% benign FPR):

Model	No/local views ASR	Decoded-view gate ASR
Llama-3.1-8B	0.58	0.00
Qwen2.5-7B	0.78	0.00
Qwen2.5-14B	1.00	0.00
Qwen2.5-32B-AWQ	1.00	0.00

• Codec-blind full-trace monitor: blocks 0/50; AUROC 0.564 for common-decoder ensemble.
• LLM reconstruction probe (DeepSeek-V4-Flash): blocks 6/50; AUROC 0.521.
• DemonAgent codec: local and full-trace non-oracle monitors stay near chance and block 0/50; decoded-view gate blocks 50/50.

Limitations

• Experiments use structured code-payload exfiltration (\(K{=}3\) fragments, fixed family); non-code compositional harms (e.g., covert natural-language self-reassembly) are explicitly out of scope.
• The decoded-view gate is a diagnostic ceiling, not a deployable defense: it requires knowing the encoding family in advance, which an adversary need not reveal.
• The marker-free recovery signal is specific to code-structure density; the paper leaves representation discovery for non-code harms as the main open problem.
• Longer horizons, larger or changing \(K\), session-mediated assembly, and full adaptive attackers are not studied in the main experiments.
• Total variation \(\mathrm{TV}(P^v_{\mathrm{ben}}, P^v_{\mathrm{att}})\) is not estimated directly; the AUROC bound \(\leq \tfrac{1}{2} + \mathrm{TV}\) is used qualitatively.
• No practical deployable mechanism that can discover the right representation without oracle knowledge is proposed; the paper is diagnostic, not prescriptive.

Relevance to Agentic AI / LLM Agents

This work directly addresses the safety architecture of multi-agent LLM pipelines, which are increasingly the dominant paradigm for deploying capable AI systems. It exposes a structural gap in the dominant defense model—per-step monitoring—that cannot be closed by making monitors stronger locally, only by redesigning what they observe. For researchers building or auditing agentic systems, the formalism (observability boundary, Proposition 1) provides a principled diagnostic tool to evaluate whether a given monitor architecture can, in principle, detect compositional attacks. The finding that full-trace access without the right decoding is still insufficient raises deep questions about what runtime safety guarantees are achievable when agent communications can use arbitrary encodings, directly relevant to work on agent sandboxing, tool-call auditing, and multi-agent trust hierarchies.