Trace-Level Analysis of Information Contamination in Multi-Agent Systems¶

🕒 Published (v1): 2026-04-30 08:39 UTC · Source: Arxiv · link

Why this paper was selected

Information contamination propagates through multi-agent workflows; trace-level analysis

Ask a follow-up

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

TL;DR¶

This paper introduces a trace-based measurement framework for studying how input uncertainty propagates through structured multi-agent workflows by injecting controlled perturbations and comparing execution traces. Across 614 paired clean/perturbed runs on 32 GAIA tasks, the authors discover a key decoupling: structural divergence in execution traces does not reliably predict outcome correctness, and vice versa. Three contamination manifestation types are taxonomized and their control-flow signatures characterized.

Problem¶

Existing evaluation of multi-agent systems relies on endpoint accuracy, which collapses internal workflow dynamics and provides no insight into how corrupted intermediate information propagates across agent boundaries. Locally plausible but globally corrupting extractions (e.g., misaligned table headers, OCR noise) pass local validation checks yet silently distort downstream reasoning—a failure mode invisible to outcome-only metrics. No systematic methodology existed for detecting, localizing, and categorizing such propagation.

Method¶

The authors model a multi-agent workflow as a directed interaction graph $G = (A, E)$ where agents exchange messages and tool outputs. Each run produces an execution trace $\tau = (e_1, \ldots, e_T)$; events are abstracted to structural signatures $\sigma(e_t)$ that retain only control-flow-relevant information (routing decisions, tool name/op/status) while discarding lexical content.

Contamination is quantified via normalized structural edit distance: $$d_{\text{norm}}(\tau, \tilde{\tau}) = \frac{\text{ED}(S(\tau), S(\tilde{\tau}))}{\max(|S(\tau)|, |S(\tilde{\tau})|)}$$ computed with Wagner–Fischer dynamic programming. The first divergence point $t^\star$ localizes where execution first deviates under the edit-distance alignment.

Perturbation operators $\pi$ are applied to artifact-derived representations (not raw files) across four modalities: tabular (column swap, row duplicate, unit change, data-type corruption, irrelevant columns, number corruption), document (OCR noise, paragraph shuffle, text redaction, watermark, encoding error), image (blur, contrast reduction, low resolution, partial occlusion, label corruption, noise), and audio (noise). Paired clean/perturbed runs use GPT-5-mini, LLaMA-3.1-70B, and Qwen3-235B at temperature 0 on 32 GAIA file-attachment tasks.

Key Contributions¶

Formal taxonomy of three contamination manifestation types: (1) silent semantic corruption ($d_\text{norm} \approx 0$, outcome changes; 15.3% of runs), (2) behavioral detours with recovery (high divergence, correct outcome; 40.3% of runs), and (3) combined structural disruption (high divergence + outcome change).
Trace-based measurement framework covering structural edit distance, first divergence point $t^\star$, and control-flow pattern prevalence (rerouting, extended execution, early termination) for detecting and localizing contamination.
Empirical characterization of modality-specific contamination fingerprints and token overhead across 614 paired runs.
Evidence that standard verification guardrails fail to intercept contamination because they operate on individual outputs rather than cross-boundary information flows.

Results¶

Behavioral detours with recovery: 40.3% of perturbed runs show high structural divergence but correct final answers.
Silent semantic corruption: 15.3% of runs show near-zero structural divergence ($d_\text{norm} \approx 0$) yet produce incorrect outputs—these are undetectable by trace monitoring alone.
Control-flow patterns in divergent runs: strategy rerouting (80.6%), extended execution (37.4%), early termination (25.3%).
Modality fingerprints: tabular perturbations predominantly trigger extended execution (24.4%); audio perturbations favor early termination.
Token overhead: behavioral detours consume median $1.5\times$ baseline tokens (IQR: 1.1–2.5×); silent semantic corruption exhibits near-baseline cost.
Baseline trace stability: on 20 tasks with 5 repeated clean runs, pairwise $d_\text{norm}$ median = 0.0, IQR = 0.1173, mean = 0.0501, confirming the perturbation signal is not confounded by sampling noise.
OCR noise induces consistent structural change with low variance; image blur exhibits high variance in divergence and first-divergence-point timing.

Limitations¶

Experiments cover only 32 GAIA tasks with file attachments—a narrow task distribution; generalizability to other benchmarks or real-world workflows is unverified.
The multi-agent orchestration apparatus is experimental and held fixed; results may not transfer to other architectures (e.g., single-planner, hierarchical, or fully dynamic topologies).
Primary analysis focuses on GPT-5-mini; LLaMA-3.1-70B and Qwen3-235B results are relegated to appendices with no cross-model comparison in the main text.
Silent semantic corruption ($d_\text{norm} \approx 0$, outcome changed) is undetectable by the structural trace metric by construction—the framework cannot distinguish it from a clean run without ground-truth outcome labels.
Perturbation operators target extracted representations rather than raw files, so they may not cover all realistic corruption modes (e.g., adversarial content injected mid-agent-turn).
No proposed remediation is evaluated; design implications (interface invariants, boundary checks) are stated as insights, not validated interventions.

Relevance to Harnesses / Meta-Harnesses¶

This paper directly informs the design of multi-agent harnesses by demonstrating that outcome-level logging is insufficient—harnesses must instrument execution traces at the event/routing level to detect costly internal instabilities that do not surface in final outputs. The trace-based measurement framework (structural signatures, edit distance, first-divergence-point localization) is a concrete blueprint for adding observability layers to orchestration harnesses, enabling runtime detection of contamination cascades before they compound. For meta-harnesses that fan out work across specialized subagents (e.g., extraction, analysis, synthesis), the taxonomy of silent corruption vs. behavioral detours motivates boundary-level invariant enforcement—validating intermediate artifacts at agent interfaces rather than only at the output stage. The modality-specific fingerprints (tabular → extended execution; audio → early termination) provide actionable heuristics for adaptive retry and cost-control policies within harness schedulers.