Paper deep dive
When Only the Final Text Survives: Implicit Execution Tracing for Multi-Agent Attribution
Yi Nian, Haosen Cao, Shenzhe Zhu, Henry Peng Zou, Qingqing Luan, Yue Zhao
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/22/2026, 5:53:24 AM
Summary
The paper introduces IET (Implicit Execution Tracing), a metadata-independent framework for multi-agent language systems that enables token-level attribution and interaction topology reconstruction directly from generated text. By embedding agent-specific keyed signals into the token distribution during generation, IET allows for post-hoc auditing and provenance recovery even when execution logs or identifiers are unavailable, outperforming existing LLM-based and segmentation-based baselines.
Entities (4)
Relation Signals (3)
IET → enables → Token-level attribution
confidence 98% · IET (Implicit Execution Tracing), a metadata-independent framework that enables token-level attribution directly from generated text
IET → evaluatedon → Who&When
confidence 95% · We evaluate robustness using the Who&When benchmark
IET → reconstructs → Interaction topology
confidence 95% · a simple mechanism for interaction topology reconstruction
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:When a multi-agent system produces an incorrect or harmful answer, who is accountable if execution logs and agent identifiers are unavailable? Multi-agent language systems increasingly rely on structured interactions such as delegation and iterative refinement, yet the final output often obscures the underlying interaction topology and agent contributions. We introduce IET (Implicit Execution Tracing), a metadata-independent framework that enables token-level attribution directly from generated text and a simple mechanism for interaction topology reconstruction. During generation, agent-specific keyed signals are embedded into the token distribution, transforming the text into a self-describing execution trace detectable only with a secret key. At detection time, a transition-aware scoring method identifies agent handover points and reconstructs the interaction graph. Experiments show that IET recovers agent segments and coordination structure with high accuracy while preserving generation quality, enabling privacy-preserving auditing for multi-agent language systems.
Tags
Links
- Source: https://arxiv.org/abs/2603.17445v2
- Canonical: https://arxiv.org/abs/2603.17445v2
Trouble viewing inline? Open PDF directly →
Full Text
72,183 characters extracted from source content.
Expand or collapse full text
When Only the Final Text Survives: Implicit Execution Tracing for Multi-Agent Attribution Yi Nian 1 * Haosen Cao 1 * Shenzhe Zhu 2 Henry Peng Zou 3 Qingqing Luan 4 Yue Zhao 1 1 University of Southern California 2 University of Toronto 3 University of Illinois Chicago 4 Independent Researcher Abstract When a multi-agent system produces an incor- rect or harmful answer, who is accountable if execution logs and agent identifiers are unavail- able? Multi-agent language systems increas- ingly rely on structured interactions such as delegation and iterative refinement, yet the fi- nal output often obscures the underlying inter- action topology and agent contributions. We introduce IET (Implicit Execution Tracing), a metadata-independent framework that enables token-level attribution directly from generated text and a simple mechanism for interaction topology reconstruction. During generation, agent-specific keyed signals are embedded into the token distribution, transforming the text into a self-describing execution trace detectable only with a secret key. At detection time, a transition-aware scoring method identifies agent handover points and reconstructs the in- teraction graph. Experiments show that IET recovers agent segments and coordination struc- ture with high accuracy while preserving gen- eration quality, enabling privacy-preserving au- diting for multi-agent language systems. 1 Introduction The adoption of autonomous agents is increasing rapidly; industry forecasts indicate that 40% of enterprise applications will feature task-specific AI agents by 2026 (Gartner, 2025; Zou et al., 2025; ?). Despite this growth, recent evaluations of multi- agent frameworks report failure rates between 41% and 87% in complex tasks (Cemri et al., 2025; Miao et al., 2025). This operational opacity creates a gap in accountability when systems produce incorrect or harmful content. Background.Attribution in language generation relied on explicit metadata: model identifiers, exe- cution logs, or externally recorded provenance sig- nals (Wang et al., 2026; Barke et al., 2026; Zhang * Equal contribution. Execution Path (Continuous & Opaque) Agent A 1st Path: Agent A writes Agent A 2nd Path: Agent B reviews Participants: [A,B] 3rd Path: Agent C summarizes Agent B Agent B Agent A Participants: [A,B,C] Agent B Agent B Agent C A. Multi-Agent System Internal View Runtime Interaction Logs discarded upon delivery, due to user privacy C . Recover the Provenance from text Which agent? How to interact? Goal: Given Only the output plain text Y, recover: (1) Segments Attribution (2) Interaction Typology Output Y Agent A Agent B Agent C Participants: [A] B.Information Loss Figure 1: Agent provenance recovering problem in multi-agent systems. Internal execution paths and agent contributions are visible during generation but discarded at delivery due to privacy security, leaving only the final text. The task is to recover latent path boundaries and agent participation from text alone. et al., 2025c). In multi-agent language systems, this assumption becomes increasingly fragile. Cur- rent state-of-the-art diagnostic frameworks, such as Who&When (Zhang et al., 2025c) and FAMAS (Ge et al., 2025), require analyzing complete execution trajectories to perform failure attribution. These methods assume an optimal "white-box" environ- ment where agent identities and internal logic are fully transparent. However, exposing such detailed traces introduces privacy risks and compliance con- straints, especially when logs are abstracted or redacted (Xiang et al., 2024). In real-world production, agent-generated con- tent is frequently decoupled from its original envi- ronment through simple “copy-pasting” into exter- nal reports or emails. As noted by Kirchenbauer et al. (2023), once text leaves the server-side log en- vironment, the link to its execution metadata is per- manently severed. In these “out-of-band” scenar- ios, existing trajectory analysis tools (Zhang et al., 2025c; Ge et al., 2025) become obsolete, leaving the generated text as the only artifact for audit- ing. This necessitates an intrinsic, self-verifying mechanism that allows provenance recovery and execution tracing directly from the output, with- out requiring access to original system traces. In 1 arXiv:2603.17445v2 [cs.AI] 19 Mar 2026 these scenarios, the final output becomes the sole surviving artifact for auditing. As LLM agents move toward high-stakes deployments, attribution can no longer depend on external metadata; instead, it requires mechanisms embedded in the generated text, turning it into key-verifiable evidence. Furthermore, while prior work focuses predom- inantly on failure attribution within multi-agent system (Wang et al., 2026; Zhang et al., 2025c; Wu et al., 2025), we argue that general execution trac- ing is a more fundamental problem. It is essential for multi-agent accountability and credit assign- ment to understand "who said what" and "how they interacted",regardless of whether a failure occurred. In this sense, failure attribution can be viewed as a downstream task built upon reliable execution tracing. Problem Definition. Multi-agent execution in- troduces a fundamental granularity gap between observable outputs and latent interaction structures. We formalize this as the problem of multi-agent execution tracing: recovering execution paths and attributing text segments to participating agents purely from the final output, without requiring ex- plicit identity metadata or internal system traces. Our Approach. We introduce IET or implicit execution tracing, a keyed, privacy-preserving at- tribution framework that binds execution identity directly to the token distribution during generation. Instead of storing provenance as external metadata, we embed statistically controlled, key-conditioned trace signals into the decoding process. These sig- nals are detectable only with a secret key and re- main statistically indistinguishable from natural text without it, enabling verifiable agent-level attri- bution. Because identity is encoded at the distribu- tional level, attribution remains recoverable even when logs are incomplete, identifiers are removed, or orchestration details are abstracted. At inference time, we reconstruct execution boundaries using sliding-window statistical scor- ing combined with change-point detection with a simple approach to record interaction patterns. This enables fine-grained segment-level attribution across diverse coordination topologies, including branching and multi-path interaction patterns. Contributions.Our main contributions are sum- marized as follows: •New Problem Formulation.We formal- ize metadata-independent execution tracing for multi-agent language systems, where the goal is to recover execution boundaries and attribute generated segments to participating agents using only the final output text. • Keyed Implicit Tracing Mechanism. We intro- duce a distribution-level tracing framework that embeds agent-specific signals into the token dis- tribution, enabling agent-level attribution without relying on explicit metadata or execution logs. • Boundary Reconstruction Algorithm. We de- velop a sliding-window statistical scoring method combined with change-point detection to recover execution boundaries and a simple approach to record interaction paths under branching and multi-path coordination settings. • Empirical Evaluation. Across diverse multi- agent coordination scenario, we demonstrate strong recoverability under identity removal and boundary perturbation while preserving genera- tion quality. 2 Method 2.1 Problem Formulation Given an interaction logL = (y 1 ,y 2 ,...,y T ), our goal is to assign each tokeny t to an agenta ∈ A. We define this as finding an attribution function ˆg(t) that partitions the log into segments. Attribution via Sequential Scoring.We assume a scoring functionf (t,a)that evaluates the align- ment between the context at timetand agenta. The attributionˆg(t)remains assigned to the active agent a k until a transition to a new agenta ′ ∈A\a k is identified by a detection operator D: D(f,a k ,a ′ ,t,H t ) > τ.(1) Here,H t incorporates the temporal history of scores, andτis a sensitivity threshold. This for- mulation treats the interaction log as a sequence of discrete turns, where boundaries are triggered by detecting in the relative competitive scores between agents a k and a ′ . Robustness to Metadata Loss. To evaluate the restorative utility of our method, we consider an ad- versarial obfuscatorA obf that simulates metadata- independent scenarios by stripping agent identifiers and segment boundaries. LetΦ(G,L)be the per- formance of a downstream modelG(e.g., error attribution) given a full-metadata logL. Our objec- 2 Agent A Key A Agent B Key B Agent C Key C Text Generation With Signal Injection Base LM Logits Original Distribution Biased Distribution Inject Signal Biased Logits Modulation Operator Key i Detectable signal Attribution Unrecoverable by Simple Way Plain Output Text Local Consistency Scoring Competitive Change-Point Detection Agent A Agent B Agent C Agent A Agent B Agent C Recovered Segment Attribution HandoffHandoff Internal Execution Path Bitmask Handoff Adjacency Matrix (maintain when executing) Decoding for Typology Recovery Agent AAgent BAgent C HandoffHandoff Final Recovery Score each token position per agent using secret keys Sliding-window Smoothed § § § Compress to a 1-dim margin Boundary 1Boundary 2 Decode Matrix Recover Encode After B->C handoffAfter A->B handoff Output Text Bitwise OR Figure 2: Overview. tive is to ensure the attribution consistency: min ˆg ∥Φ(G, Rec(A obf (L), ˆg))− Φ(G,L)∥ (2) whereRecis the reconstruction function powered by our estimated attributionˆg. This formulation characterizes our method as a robust backbone that maintains the diagnostic power of downstream tasks even under severe information obfuscation. Structural Validation. To validate the logical consistency of the recovered attribution, we con- struct an estimated interaction topology ˆ G = (A, ˆ E ) . An edge(a (i) ,a (j) )∈ ˆ Eis recorded for ev- ery observed transition between agent(a (i) anda (j) where i̸=j. This inferred graph is then compared against the ground-truth topologyG ⋆ to evaluate the accuracy of the interaction recovery. 2.2 Implicit Execution Tracing To enable post-hoc attribution in metadata-deprived environments, we bind each agent’s identity di- rectly to its generated output through keyed mod- ulation of the token distribution during decoding. This process introduces agent-specific statistical signatures that can later be verified using the cor- responding secret key, following the statistical sig- naling framework introduced by Lau et al. (2024). LetL j ∈ R |V| denote the logits produced by the base language model at token positionj. For an ac- tive agenta k ∈Aidentified in the execution trace, we generate text by applying a keyed distributional modulation operatorWconditioned on the agent identity: ̃ L j =W(a k ,L j ).(3) whereWinduces a statistically detectable bias de- termined bya k . Specifically, the agent identitya k induces two distinct keys: k p = h p (a k ), k (j) π = h π (a k , y j−n+1:j−1 ), (4) wherek p determines a fixed perturbation direc- tion in logit space unique to agenta k , andk (j) π determines a context-dependent vocabulary per- mutation andy 1:j−1 denotes the previously gen- erated token sequence andy j−n+1:j−1 represents the length-(n− 1)context window used to derive the context-dependent key. Similar to (Lau et al., 2024), the logits ̃ L j are then modulated as: ̃ L j =P −1 k (j) π , F k p ,κ,P(k (j) π ,L j ) ,(5) wherePhandles the vocabulary permutation andF applies a low-magnitude perturbationκalong the directionk p . Sampling from this modified distribu- tion embeds the agent’s identitya k as a persistent statistical signal, enabling structural recovery even when explicit metadata is removed. 2.3 Agent Attribution IET aims to recover the latent attribution function ˆg(t)by identifying which agent’s signal best ex- plains each segment of the generated text Y . Local Consistency Scoring. We first define a token-level statisticx j (a)for token at position j, to measure the alignment between the observed token y j and the signal induced by agent a∈A: x j (a) = D P k (j) π ,L j , F k p (a) E ,(6) To mitigate local variance, we instantiate the agent- consistency metricf (t,a)from our formulation using a sliding window of width w: f (t,a) = 1 w t+w−1 X j=t x j (a).(7) 3 This window-averaged scoref (t,a)bridges the gap between low-level token statistics and high- level structural inference. Competitive Change-Point Detection.To iden- tify transitions between agents, we instantiate the detection operatorDusing a competitive detector. We first reduce the multi-agent consistency scores into a one-dimensional competitive margin signal z t , which quantifies the relative dominance of the leading agent candidate: z t = f (t, ˆa t )−max a ′ ∈A\ˆa t f (t,a ′ ),(8) whereˆa t = arg max a∈A f (t,a)is the agent with the highest alignment score at time t. To robustly localize transitions, we smooth the margin sequence with cumulative sum algorithm toz t . For thek-th segment starting at position ˆτ k−1 , we track the cumulative deviation from the local mean margin ̄z k : C t = t X i=ˆτ k−1 z i − ̄z k .(9) We formally define the detection operatorDas a binary decision at the potential change pointˆτ k = arg max t>ˆτ k−1 |C t |: D(f,a ′ , ˆa t , ˆτ k ) = I (|C ˆτ k | > τ ),(10) whereτis the sensitivity threshold. By iteratively identifying these extrema, we partition the interac- tion log intoKcontiguous segments. This induced segmentation allows us to recover the attribution function ˆg(t) as a piecewise-constant mapping: ˆg(t) = ˆa k ,for t∈ [ˆτ k−1 , ˆτ k ),(11) whereˆa k is the dominant agent identified within the k-th segment. 2.4 Execution Path and Topology Encoding To recover the interaction topology ˆ G , we must en- code the directional dependencies between agents within the agent signal. We represent this evolving state as an online-updated adjacency matrix. Topology State Representation. LetA = a 1 ,...,a K be the set of agents. At any stept, the execution path is represented by a binary adja- cency matrixM t ∈0, 1 K×K , where(M t ) i,j = 1 if a directed interaction from agenta i to agenta j has occurred (e.g., through state-passing, rewriting, or observation). The path identifierμ t is derived by flattening and encoding M t as a bitmask: μ t = g(M t ) = K X i=1 K X j=1 (M t ) i,j · 2 (i−1)K+(j−1) . (12) This bijective mapping ensures thatμ t uniquely identifies the current interaction graph, distinguish- ing between fundamental topologies such as chains, stars, or cycles. Interactive State Maintenance.The matrixM t is maintained across agent invocations to capture the cumulative context. Initialized atM 0 = 0, whenever agenta i transmits information to agent a j , the state is updated via a bitwise OR operation: M t = M t−1 ∨ E i,j ,(13) whereE i,j is a sparse matrix with a 1 at index(i,j). This monotonic update rule ensures that once a de- pendency is established, it is persistently encoded into the subsequent watermarked tokens. By de- tecting the latentμ t from the output text, we can invert the mapping to reconstruct the full adjacency matrix, thereby recovering the interaction topology ˆ G without explicit metadata. 3 Experimental Setting 3.1 Datasets We evaluate our framework on two complementary multi-agent benchmarks that provide structured in- teraction logs and ground-truth speaker annotations. Additional details are provided in Appendix B. Multi-Agent Interaction Dataset (Liu et al., 2025). This dataset contains structured multi-agent dialogues under diverse coordination paradigms, including hierarchical delegation and collaborative planning. Each interaction log provides explicit agent identities and turn-level boundaries, allow- ing analysis of agent participation and interaction structure. Further details of the MAMA topology dataset, including the source file and its fields, are provided in Appendix B.4. Who & When (Zhang et al., 2025c). This bench- mark focuses on speaker and error attribution in multi-agent transcripts. The dataset contains con- versational logs with annotated speaker identities and temporal ordering, enabling evaluation of at- tribution in multi-party interactions. Additional details of the Who&When benchmark are provided in Appendix B.5. 4 3.2 Experimental Design To evaluate the capabilities defined in Section 2.1, we design two complementary experimental set- tings that test (i) topology-sensitive attribution un- der controlled interaction structures and (i) robust- ness of attribution under metadata obfuscation. Topology-aware attribution. We evaluate attri- bution and structural recovery using the Multi- Agent Interaction Dataset (Liu et al., 2025). This dataset provides structured interaction logs where multiple agents collaborate through predefined communication graphs. To analyze how interaction topology affects attribution difficulty, we consider several canonical coordination structures, includ- ing star, ring, and tree topologies. For each topol- ogy, agents interact through a fixed communication protocol while solving the same set of tasks. The resulting logs allow us to examine whether the re- covered attribution function can correctly identify agent contributions and reconstruct the underlying interaction topology. Robust attribution under metadata loss. We evaluate robustness using the Who&When bench- mark (Zhang et al., 2025c), which contains multi- agent transcripts with annotated speaker identities and error attribution labels. To simulate metadata- independent scenarios and verify IET framework’s robustness, we apply two types of transcript per- turbations: (i) ID Removal, where explicit agent identifiers are removed from each utterance, and (i) Boundary Corruption, where utterance bound- aries are shuffled or partially merged. These pertur- bations mimic realistic situations where execution metadata is unavailable or unreliable. The goal is to evaluate whether agent identities and interaction structures can be recovered from text alone under increasing levels of transcript corruption. 3.3 Evaluation Metrics Following the problem formulation in Section 2.1, we evaluate three aspects of execution tracing: se- quential attribution, structural validation, and ro- bustness under metadata loss. Sequential Attribution. We measure whether the recovered attribution functionˆg(t)correctly as- signs tokens to generating agents. Given predicted token segments ˆ S and ground-truth segmentsS, we report token-level accuracy and concatenated-text IoU: TokenAcc = 1 T T X t=1 I[ˆg(t) = g(t)](14) IoU(S, ˆ S) = |S∩ ˆ S| |S∪ ˆ S| (15) We report both mean and median IoU across logs to account for variability in interaction length. Structural Validation. To evaluate whether the recovered attribution preserves interaction struc- ture, we construct an interaction graph from pre- dicted agent transitions and compare it with the ground-truth topology. We report topology attribu- tion accuracy: TopoAcc = 1 N N X i=1 I[ˆa i = a i ],(16) wherea i andˆa i denote the ground-truth and predicted agent for interaction unit i. Robustness under Metadata Loss. To evaluate robustness under transcript corruption, we follow the evaluation protocol of the Who&When bench- mark (Zhang et al., 2025c); additional benchmark details are provided in Appendix B.5. Each fail- ure trajectory provides annotations identifying the failure-responsible agenta ⋆ and the decisive error stept ⋆ . We simulate metadata-independent sce- narios by applying two perturbations: (i) ID Re- moval and (i) Boundary Corruption Given the corrupted transcript, our method first reconstructs agent identities and interaction boundaries, produc- ing a recovered execution log. Failure attribution is then performed as a downstream task on the recon- structed structure using the Who&When evaluation protocol. Given predictions (ˆa, ˆ t), we report: AgentAcc = I[ˆa = a ⋆ ],StepAcc = I[ ˆ t = t ⋆ ]. (17) AgentAcc measures whether the correct failure- responsible agent is identified, while StepAcc eval- uates localization of the decisive error step. This setup treats failure attribution as a downstream task and measures whether reconstructed execu- tion traces preserve the diagnostic utility of the original logs. 3.4 Baselines We compare our method against two categories of baselines: LLM-based attribution baselines and traditional segmentation baselines. For the LLM-based baselines, we use ChatGPT- 4o (OpenAI et al., 2023) and DeepSeek-v3.1 5 #Agents = 4#Agents = 5#Agents = 6 MethodMetricStar-PureChainTreeStar-PureChainTreeStar-PureChainTree LLM Baselines ChatGPTIoU0.1660.1680.1710.1390.1420.1460.0990.1050.103 TokenAcc0.2800.2830.2870.2320.2410.2380.1770.1880.183 DeepSeekIoU0.1750.1650.1780.1490.1400.1560.1110.1110.125 TokenAcc0.2920.2790.2970.2510.2440.2630.1980.1980.219 Segmentation Baselines Random (token)IoU0.3870.3970.4230.3430.3560.3760.3060.3330.313 TokenAcc0.5550.5540.5820.4940.5180.5270.4530.4770.450 Random-UnitIoU0.4240.4350.4200.3530.3700.3980.3160.3470.333 TokenAcc0.5830.5890.5730.5250.5240.5070.4600.4690.459 RecursiveIoU0.5560.4510.5290.4890.3850.4830.4300.3060.458 TokenAcc0.7060.6060.6860.6520.5460.6420.6080.4480.632 Semantic-BoWIoU0.3050.3460.3290.2670.3150.3040.2470.2620.281 TokenAcc0.4570.5170.5060.4420.4650.4690.3540.3800.409 TextTilingIoU0.3900.4140.4020.3640.3350.3970.3470.2910.374 TokenAcc0.5130.5680.5400.4740.4980.4710.4280.4060.468 Our Method Ours (WM)IoU↑0.9340.9380.9360.9320.9390.9330.9290.9390.932 TokenAcc↑0.9510.9540.9570.9480.9500.9530.94170.9440.949 TopoAcc↑1.001.001.001.001.001.001.001.001.00 Table 1: Sequential attribution performance across LLM baselines, segmentation baselines, and our method under different agent counts and coordination topologies. (DeepSeek-AI, 2024). Given LLM the number of agentsK, we provide the LLM with the agent inter- action logs and ask it to assign a span to one of the Kspeakers. Concretely, we first keep only assis- tant outputs, reconstruct the conversation in a fixed order, and split the concatenated text into fixed- length token units. The LLM then predicts a set of token-span ranges for each speaker, from which we derive token-level speaker labels. This setting re- quires the model to jointly infer both segmentation boundaries and speaker ownership from text alone. The full system and user prompt templates for the LLM baseline are provided in Appendix A.1; a brief overview of the prompting design is given in Appendix A.1.1. Traditional Baselines.We compare against sev- eral segmentation-based baselines that do not model speaker identity and therefore can only pre- dict segment boundaries. The baselines include: (i) Random (token): boundaries are sampled uni- formly from the token sequence. (i) Random- Unit: boundaries are sampled only from unit boundaries (e.g., sentence or predefined units) rather than arbitrary token positions. (i) Recur- sive: the text is recursively partitioned using simple textual separators and then adjusted to match the target number of segments. (iv) Semantic-BoW: boundaries are detected by identifying drops in bag- of-words similarity between neighboring text win- dows. (v) TextTiling: a lexical-cohesion method that places boundaries according to depth scores de- rived from local similarity changes across adjacent text blocks. Since these baselines cannot infer speaker iden- tity, we evaluate them only on the segmentation component of the task. Each method predictsK−1 boundaries, producingKtext segments. We then align the predicted segments with the gold seg- ments by segment index and measure segmentation quality using concatenated-text IoU and token-level accuracy. This protocol evaluates the traditional baselines on the subproblem they are designed to handle (boundary detection), while the LLM-based baselines are evaluated on the full attribution task. 3.5 Evaluation Our evaluation is organized around three questions that correspond to the core objectives of metadata- independent execution tracing: recovering token- level attribution, reconstructing interaction struc- ture, and preserving downstream diagnostic utility under metadata loss. How accurately can sequential attribution be recovered?We report TokenAcc and IoU across different agent counts and interaction topologies in Table 1. LLM-based baselines (ChatGPT and 6 DeepSeek) perform poorly, with TokenAcc below 0.30and IoU around0.10–0.18. Structure-based segmentation methods improve performance (e.g., Recursive reaching IoU up to0.56), but remain far below reliable attribution. In contrast, our method consistently achieves over94%TokenAcc and around0.93IoU across all settings, while also recovering the interaction topology perfectly. How well does the recovered trace preserve in- teraction structure? Table 1 also reports topol- ogy recovery accuracy (TopoAcc). Our method achieves near-perfect structural recovery across all configurations, with TopoAcc equal to1.0in al- most all cases and never dropping below0.98. This is because the tracing mechanism maintains an ex- plicit execution state during generation, enabling reliable reconstruction of agent transitions and in- teraction topology. Can the recovered trace support downstream failure attribution under metadata loss? Ta- ble 2 reports failure attribution accuracy under metadata corruption. Without trace signals, base- line methods degrade sharply once metadata is re- moved. In particular, AgentAcc drops to near zero under ID removal for both Step-by-Step and Binary Search. In contrast, our tracing-enabled method remains substantially more robust across all corrup- tion settings. For example, under ID removal the Step-by-Step strategy still achieves 23.81% Agen- tAcc and 15.24% StepAcc, while Binary Search maintains non-trivial recovery performance. These results show that the recovered traces preserve suffi- cient structural information to support downstream failure attribution when metadata is unavailable. Case Study: Robustness to PII Redaction.We further examine whether privacy-preserving prepro- cessing affects trace recovery. In the Multi-Agent Interaction Dataset, conversation logs may contain sensitive information such as names, emails, or phone numbers. To simulate realistic deployment settings, we apply standard PII redaction that re- places sensitive spans with placeholder tokens (e.g., [NAME], [EMAIL]). Figure 3 compares tracing performance before and after redaction across different multi-agent interaction structures. Despite removing lexical content, the overall performance remains nearly unchanged. For most interaction patterns (e.g., 4- chain, 4-tree, and 5-chain), the IoU and token-level accuracy curves for the original and censored logs Figure 3: Robustness to PII redaction. Attribution per- formance on original and PII-redacted transcripts across different interaction structures. The similar curves indi- cate minimal degradation after redaction. almost overlap. Minor deviations only appear in more complex structures such as 6-tree and 6-star- pure, where the performance drop remains small. These results indicate that the tracing signal is embedded in the generation process rather than re- lying on surface lexical patterns. Consequently, removing sensitive tokens does not significantly affect agent attribution, demonstrating that the proposed tracing mechanism is robust to privacy- preserving transcript sanitization. 4 Related Work 4.1 Failure Attribution in Multi-Agent Systems As large language models are increasingly de- ployed in multi-agent settings, understanding and debugging system failures has become an impor- tant research problem (Chen et al., 2024; Wang et al., 2026; ?; ?). Prior work primarily studies fail- ure attribution as a post-hoc inference task: given an execution trace produced by multiple interacting agents, the goal is to infer which agent, or which step in the interaction, is responsible for a system- level failure (Zhang et al., 2025c; Ge et al., 2025; Barke et al., 2026; Cemri et al., 2025). Recent benchmarks formalize this problem ex- plicitly by asking models to predict the responsible agent (who) and the decisive error step (when) from raw execution traces. Other approaches employ counterfactual replay, causal analysis (Zhang et al., 2025a), or learned tracer models (Zhu et al., 2025; Zhang et al., 2025b) to identify failure sources in the absence of explicit provenance. These meth- ods highlight the difficulty of attribution when exe- cution logs record only surface-level interactions without preserving information-flow dependencies. Our approach is complementary: instead of relying solely on retrospective inference, we embed trace- 7 Baseline (Zhang et al., 2025c)Ours BaselineRemove IDBoundaryBaselineRemove IDBoundary MethodAgentStepAgentStepAgentStepAgentStepAgentStepAgentStep All-at-Once54.3312.505.2212.1725.4915.6941.469.7626.4711.7638.716.45 Step-by-Step35.2025.510.0010.2836.0414.4128.7012.0423.8115.2427.009.00 Binary Search44.1323.980.003.1732.541.5934.131.5922.222.3836.512.38 Table 2: Failure attribution accuracy under metadata corruption. Left: baseline methods without trace signals. Right: our tracing-enabled method. Agent and Step denote agent-level and step-level attribution accuracy (%). ability into the generation process so that agent- level provenance can be recovered more directly. 4.2 Watermarking and Provenance in Large Language Models Watermarking has been widely studied for identi- fying AI-generated content and verifying model provenance (Fang et al., 2025). Existing methods embed detectable signals at different stages of the generation pipeline, including during logits gener- ation (Kirchenbauer et al., 2023; Lee et al., 2024; Hu et al., 2023; Wu et al., 2024), token sampling (Christ et al., 2024; Kuditipudi et al., 2024; Hou et al., 2024), or model training (Sun et al., 2022, 2023; Gu et al., 2023). These approaches primar- ily focus on detecting whether a piece of text was generated by a particular model, and are typically designed for single-model settings rather than trac- ing information flow across multiple agents. A separate line of work studies watermarking for existing text through format-based, lexical-based, syntactic-based, and generation-based transforma- tions (Brassil et al., 1995; Topkara et al., 2006; Atallah et al., 2001; Abdelnabi and Fritz, 2021). However, these approaches embed signals into a single text instance and do not model how prove- nance propagates across multiple interacting agents or intermediate steps. In contrast, we repurpose wa- termarking as a system-level instrumentation mech- anism that preserves and propagates provenance across agent interactions, enabling explicit and ver- ifiable attribution in multi-agent systems. 4.3 Inference versus Instrumentation Accountability in multi-agent systems can be ap- proached in two ways: inference and instrumenta- tion. Inference-based approaches seek to determine responsibility after a failure occurs by analyzing ex- ecution traces that lack explicit provenance signals. In contrast, instrumentation embeds traceability di- rectly into the system during generation, so that the origin of each contribution can be recovered explicitly. Prior work on multi-agent failure attribu- tion largely follows the inference paradigm, while watermarking embeds identifiable signals but is typ- ically designed for single-model settings. Our work bridges these two paradigms by repurposing water- marking as a system-level instrumentation mecha- nism. By embedding watermark-based provenance into multi-agent interactions, responsibility can be recovered deterministically and audited by design. 5 Conclusion In this paper, we introduced Implicit Execution Tracing, a framework that addresses the structural opacity of modern multi-agent language systems. By embedding key-conditioned trace signals di- rectly into the token distribution, the generated text becomes a self-describing execution record, enabling fine-grained agent attribution and recon- struction of interaction structures directly from the output, without relying on explicit execution logs. Our results show that reliable tracing remains possible even in metadata-free settings where inter- nal trajectories are unavailable for privacy or com- pliance reasons. As multi-agent systems evolve into complex multi-vendor ecosystems, decoupling provenance from system infrastructure provides a practical path toward accountable and privacy- preserving AI collaboration. 6 Ethical Considerations Our research focuses on attribution and execution tracing in multi-agent language systems. To sys- tematically evaluate our approach, we conduct ex- periments on conversational datasets that may con- tain personally identifiable information (PII), such as names or contact details. These datasets are ob- tained from publicly available resources and are used solely for research purposes in a controlled experimental setting. To mitigate privacy risks, we apply standard PII redaction procedures by replac- ing sensitive spans with placeholder tokens (e.g., [NAME], [EMAIL]). Our work aims to improve 8 transparency and accountability in multi-agent AI systems by enabling reliable attribution of gener- ated content, which aligns with responsible AI de- velopment and auditing practices. 7 Limitations Our research focuses on attribution and execution tracing in multi-agent language systems. To evalu- ate our approach, we conduct experiments on con- versational datasets that may contain personally identifiable information (PII), such as names or contact details. These datasets are obtained from publicly available resources and used solely for research purposes in a controlled setting. To miti- gate privacy risks, we apply standard PII redaction by replacing sensitive spans with placeholder to- kens. Our work aims to improve transparency and accountability in multi-agent AI systems. References Sahar Abdelnabi and Mario Fritz. 2021. Adversarial wa- termarking transformer: Towards tracing text prove- nance with data hiding. In 2021 IEEE Symposium on Security and Privacy (SP), pages 121–140. IEEE. Mikhail J. Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. 2001. Natural lan- guage watermarking: Design, analysis, and a proof- of-concept implementation. In Information Hiding, volume 2137 of Lecture Notes in Computer Science, pages 185–200. Springer. Shraddha Barke, Arnav Goyal, Alind Khare, Avaljot Singh, Suman Nath, and Chetan Bansal. 2026. Agen- tRx: Diagnosing AI agent failures from execution trajectories. Preprint, arXiv:2602.02475. Jack T. Brassil, Steven Low, Nicholas F. Maxemchuk, and Lawrence O’Gorman. 1995. Electronic marking and identification techniques to discourage document copying. IEEE Journal on Selected Areas in Commu- nications, 13(8):1495–1504. Mert Cemri, Melissa Z. Pan, Shuyi Yang, Lakshya A. Agrawal, Bhavya Chopra, Rishabh Tiwari, Kurt Keutzer, Aditya Parameswaran, Dan Klein, Kannan Ramchandran, Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica. 2025. Why do multi-agent LLM systems fail? In Advances in Neural Information Processing Systems 38: Datasets and Benchmarks Track. Spotlight. Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang, Chenfei Yuan, Chi-Min Chan, Heyang Yu, Yaxi Lu, Yi-Hsin Hung, Chen Qian, and 1 others. 2024. Agent- Verse: Facilitating multi-agent collaboration and ex- ploring emergent behaviors. In The Twelfth Interna- tional Conference on Learning Representations. Miranda Christ, Sam Gunn, and Or Zamir. 2024. Un- detectable watermarks for language models. In Pro- ceedings of the 37th Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1125–1139. PMLR. 9 DeepSeek-AI. 2024. DeepSeek-V3 technical report. Preprint, arXiv:2412.19437. Liancheng Fang, Aiwei Liu, Henry Peng Zou, Yankai Chen, Hengrui Zhang, Zhongfen Deng, and Philip S. Yu. 2025.MUSE: Model-agnostic tabular wa- termarking via multi-sample selection. Preprint, arXiv:2505.24267. Gartner. 2025. Gartner predicts 40% of enterprise apps will feature task-specific AI agents by 2026, up from less than 5% in 2025. Press release, updated Septem- ber 5, 2025. Yu Ge, Linna Xie, Zhong Li, Yu Pei, and Tian Zhang. 2025. Who is introducing the failure? automatically attributing failures of multi-agent systems via spec- trum analysis. Preprint, arXiv:2509.13782. Chenchen Gu, Xiang Lisa Li, Percy Liang, and Tatsunori Hashimoto. 2023.On the learnability of watermarks for language models.Preprint, arXiv:2312.04469. Abe Bohan Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. 2024. SemStamp: A semantic watermark with paraphrastic robustness for text generation. In Proceedings of the 2024 Con- ference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Lan- guage Technologies (Volume 1: Long Papers), pages 4067–4082. Association for Computational Linguis- tics. Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. 2023. Unbi- ased watermark for large language models. Preprint, arXiv:2310.10669. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. 2023. A watermark for large language models. In Proceed- ings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061–17084. PMLR. Rohith Kuditipudi,John Thickstun,Tatsunori Hashimoto, and Percy Liang. 2024.Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. Gregory Kang Ruey Lau, Xinyuan Niu, Hieu Dao, Jiang- wei Chen, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. 2024. Waterfall: Framework for robust and scal- able text watermarking and provenance for LLMs. Preprint, arXiv:2407.04411. Taehyun Lee, Seokhee Hong, Jaewoo Ahn, Ilgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim. 2024. Who wrote this code? watermarking for code generation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4890– 4911. Association for Computational Linguistics. Stephanie Lin, Jacob Hilton, and Owain Evans. 2022. TruthfulQA: Measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3214–3252. Associ- ation for Computational Linguistics. Jinbo Liu, Defu Cao, Yifei Wei, Tianyao Su, Yuan Liang, Yushun Dong, Yan Liu, Yue Zhao, and Xiyang Hu. 2025. Topology matters: Measuring memory leakage in multi-agent LLMs. Preprint, arXiv:2512.04668. Chunyu Miao, Henry Peng Zou, Yangning Li, Yankai Chen, Yibo Wang, Fangxin Wang, Yifan Li, Wooseong Yang, Bowei He, Xinni Zhang, and 1 oth- ers. 2025. RECODE-H: A benchmark for research code development with interactive human feedback. Preprint, arXiv:2510.06186. OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, and 1 others. 2023. GPT- 4 technical report. Preprint, arXiv:2303.08774. Colin Raffel, Noam Shazeer, Adam Roberts, Kather- ine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1–67. Zhensu Sun, Xiaoning Du, Fu Song, and Li Li. 2023. CodeMark: Imperceptible watermarking for code datasets against neural code completion models. In Proceedings of the 31st ACM Joint European Soft- ware Engineering Conference and Symposium on the Foundations of Software Engineering, pages 1561– 1572. ACM. Zhensu Sun, Xiaoning Du, Fu Song, Mingze Ni, and Li Li. 2022. CoProtector: Protect open-source code against unauthorized training usage with data poi- soning. In Proceedings of the ACM Web Conference 2022, pages 652–660. ACM. Umut Topkara, Mercan Topkara, and Mikhail J. Atallah. 2006. The hiding virtues of ambiguity: Quantifi- ably resilient watermarking of natural language text through synonym substitutions. In Proceedings of the 8th Workshop on Multimedia and Security, pages 164–174. ACM. Junjie Wang, Yawen Wang, Mengzhuo Chen, Xiaofei Xie, Chunyang Chen, Fangwen Mu, Zhe Liu, and Qing Wang. 2026. A survey for LLM agent trajectory analysis: From failure attribution to enhancement. Preprint on ResearchGate. Yaozu Wu, Dongyuan Li, Yankai Chen, Renhe Jiang, Henry Peng Zou, Wei-Chieh Huang, Yangning Li, Liancheng Fang, Zhen Wang, and Philip S. Yu. 2025. Multi-agent autonomous driving systems with large language models: A survey of recent advances. Preprint, arXiv:2502.16804. Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. 2024. DiPmark: A stealthy, efficient and 10 resilient watermark for large language models. With- drawn submission to ICLR 2024. Zhen Xiang, Linzhi Zheng, Yanjie Li, Junyuan Hong, Qinbin Li, Han Xie, Jiawei Zhang, Zidi Xiong, Chulin Xie, Carl Yang, Dawn Song, and Bo Li. 2024. GuardAgent: Safeguard LLM agents by a guard agent via knowledge-enabled reasoning. Preprint, arXiv:2406.09187. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Ben- gio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answer- ing. In Proceedings of the 2018 Conference on Em- pirical Methods in Natural Language Processing, pages 2369–2380. Association for Computational Linguistics. Guibin Zhang, Junhao Wang, Junjie Chen, Wangchun- shu Zhou, Kun Wang, and Shuicheng Yan. 2025a. AgenTracer: Who is inducing failure in the LLM agentic systems? Preprint, arXiv:2509.03312. Heng Zhang, Yuling Shi, Xiaodong Gu, Haochen You, Zijian Zhang, Lubin Gan, Yilei Yuan, and Jin Huang. 2025b. GraphTracer: Graph-guided failure tracing in LLM agents for robust multi-turn deep search. Preprint, arXiv:2510.10581. Shaokun Zhang, Ming Yin, Jieyu Zhang, Jiale Liu, Zhiguang Han, Jingyang Zhang, Beibin Li, Chi Wang, Huazheng Wang, Yiran Chen, and Qingyun Wu. 2025c. Which agent causes task failures and when? on automated failure attribution of LLM multi- agent systems. In Proceedings of the 42nd Interna- tional Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 76583–76599. PMLR. Chenyang Zhu, Spencer Hong, Jingyu Wu, Kushal Chawla, Yuhui Tang, Youbing Yin, Nathan Wolfe, Erin Babinsky, and Daben Liu. 2025. RAFFLES: Reasoning-based attribution of faults for LLM sys- tems. Poster at MTI-LLM @ NeurIPS 2025. Henry Peng Zou, Wei-Chieh Huang, Yaozu Wu, Yankai Chen, Chunyu Miao, Hoang Nguyen, Yue Zhou, Weizhi Zhang, Liancheng Fang, Langzhou He, Yangning Li, Dongyuan Li, Renhe Jiang, Xue Liu, and Philip S. Yu. 2025. LLM-based human-agent collaboration and interaction systems: A survey. Preprint, arXiv:2505.00753. A Appendix A Prompt Details This section presents the full prompt templates used in our experiments. We organize them into two groups: (1) prompts used in the LLM baseline for speaker-range assignment, and (2) prompts used in the debate framework, including the debating agents and the final judge. Placeholders enclosed in braces (e.g., question_text, choices_block) denote instance-specific fields filled dynamically at inference time. A.1 LLM Baseline Prompts This subsection presents the prompts used in the LLM baseline for speaker-range assignment on con- catenated multi-speaker traces. Given a tokenized trace containing utterances from exactlyKspeak- ers, the model is asked to assign each contiguous token unit to one speaker and return the final seg- mentation in JSON format. A.1.1 Baseline Overview The baseline prompt consists of two parts: a sys- tem prompt and a user prompt. The system prompt specifies the output schema and the global valid- ity constraints, including complete coverage, no overlap, boundary alignment, and non-empty as- signment for every speaker. The user prompt pro- vides the instance-specific information, including the number of speakers, the number of units, the to- tal number of tokens, the valid unit boundaries, the task description, and the unit-level trace content. Together, these prompts cast the attribution task as a constrained structured prediction problem: the model must first assign each unit to exactly one speaker and then merge adjacent units belonging to the same speaker into minimal non-overlapping ranges. The full prompt templates are provided below. LLM Baseline Prompt (System Prompt). Sys- tem prompt template used in the LLM baseline for speaker-range assignment. You assign each token span in a concatenated multi-speaker trace to one of K speakers.,→ You must reason privately and NEVER reveal your reasoning.,→ Your final answer must be EXACTLY ONE JSON object and NOTHING ELSE.,→ Do not output any natural language, analysis, prefacing text, markdown, code fences, bullets, or apologies.,→ Do not start with phrases like'Okay','Let's','Here is', or any sentence.,→ The ONLY valid output format is: "ranges": "0": [[0, 64]], "1": [[64, 128]], "2": [[128, 192]], "3": [[192, 256]],→ Example valid output: 11 DatasetSubset / FileSourceRole in Experiments C4 realnewslike allenai/c4Initial waterfall watermark testing TruthfulQAmultiple-choiceTruthfulQADebate evaluation HotpotQA distractor, train hotpot_qaSliding-window and concatenated-text watermark experiments MAMA topol- ogy llama3.1_num484_nopii.csvMAMA repositoryTopology-based multi-agent experiments Who & When Algorithm-Generated, Hand-Crafted Agents Failure Attribu- tion repository Failure attribution under metadata corruption Table 3: Datasets used in different stages of our experiments. "ranges": "0": [[0, 64]], "1": [[64, 128], [192, 256]], "2": [[128, 192]], "3": [[256, 320]],→ Use speaker ids 0..K-1 in order of first appearance in the conversation.,→ Each [l, r] is a token range in [start, end) format. Each listed unit is a contiguous chunk of unit_tokens tokens, except the final chunk of a message which may be shorter. ,→ ,→ Every range boundary must align exactly to a listed unit boundary.,→ That means every start and every end value must be chosen from the provided unit boundary values.,→ Do not invent token boundaries inside a unit. Think of the task as assigning each unit to exactly one speaker, then merging consecutive units with the same speaker. ,→ ,→ No unit may belong to more than one speaker. No unit may be left unassigned. The top-level object must contain exactly one key: "ranges".,→ Inside "ranges", there must be exactly K keys: "0", "1", ..., "K-1".,→ No speaker key may appear outside the "ranges" object. Ranges for each speaker must be sorted and non-overlapping.,→ For each speaker, merge all adjacent or touching ranges. If one range ends at x and the next range starts at x, they must be merged into a single range.,→ Use the minimum number of ranges possible for each speaker.,→ Across all speakers, ranges must exactly cover all tokens from 0 to T with no gaps and no overlaps.,→ Every speaker from 0 to K-1 definitely appears in this trace.,→ Therefore, no speaker may have an empty range list. Any output where a speaker has [] is invalid. Any output where one speaker covers all tokens is invalid.,→ Before answering, verify that every speaker has at least one non-empty range with positive length.,→ If you are uncertain, still output your best guess in the required JSON format.,→ An answer like'Okay, let me think' is invalid. Any text before′ or after′ is invalid. LLM Baseline Prompt (User Prompt). User prompt template used in the LLM baseline for speaker-range assignment. Instance-specific fields are filled dynamically at inference time. There are K=k speakers. There are N=num_units units, indexed from 0 to num_units - 1.,→ There are T=total_tokens tokens in total. Each unit is a contiguous chunk of unit_tokens tokens, except the last chunk of a message which may be shorter. ,→ ,→ Valid unit boundary values are: boundary_values. You do NOT know the speaker identities in advance. Speaker 0 must be the first distinct speaker that appears, speaker 1 the next new speaker, and so on.,→ Return exactly one JSON object with this schema: "ranges": "0": [[start, end]], "1": [[start, end]], "2": [[start, end]], "3": [[start, end]],→ Concrete example output: "ranges": "0": [[0, 64]], "1": [[64, 128], [192, 256]], "2": [[128, 192]], "3": [[256, 320]],→ In that example, speaker 1 has two ranges: [64, 128] and [192, 256].,→ All start/end values in the output must be taken from the valid unit boundary values listed above.,→ A range like [10, 70] is invalid if 10 or 70 is not a listed unit boundary.,→ Assign each unit to exactly one speaker before you construct the ranges.,→ Then merge adjacent units assigned to the same speaker into a single range.,→ There are exactly K distinct speakers in this trace. You must include every speaker key from 0 to K-1, and every speaker must have at least one non-empty range.,→ Every speaker definitely speaks at least once in this trace.,→ So no speaker may have an empty list []. The JSON is invalid unless the only top-level key is "ranges" and all speaker keys are inside it.,→ The JSON is invalid if any speaker key from 0 to K-1 is missing.,→ The JSON is invalid if any speaker has an empty list. The JSON is invalid if one speaker covers all tokens. Do not assign all tokens to a single speaker. Adjacent or touching ranges for the same speaker must be merged.,→ Use the minimum number of ranges possible. Your first character must be′ and your last character must be′.,→ Do not output anything except this JSON object. TRACE CONTEXT: task_description=task_description UNITS: unit_lines A.2 Debate Prompts This subsection presents the prompts used in our debate-based multiple-choice question answering framework. The framework consists of a three- round debate between two agents, followed by a judge model that reads the complete debate tran- script and selects a single final answer. A.2.1 Debate Protocol Overview We use a three-round two-agent debate protocol. In Round 0, each agent independently reads the question and candidate answers, and then produces an initial answer with reasoning. In Round 1, each agent is additionally shown its own Round 0 re- sponse and the opponent’s Round 0 response, and is asked to reconsider its answer. In Round 2, each agent sees the debate history from the previous two rounds and produces a final answer. Across all three rounds, the prompts explicitly instruct the agents to prioritize factual correctness, 12 truthfulness, and non-misleadingness. To facilitate automatic parsing and evaluation, each agent is re- quired to output exactly one answer option in a fixed format. After the debate concludes, a sepa- rate judge model receives the original question, the answer candidates, and the full debate transcript, and selects exactly one final answer. A.2.2 Debating Agent Prompts The full prompt templates for the debating agents in Rounds 0, 1, and 2 are given below. Two-Agent Debate Prompt (Agent, Round 0). Prompt template for a debating agent in Round 0, where the agent answers the question indepen- dently before observing the opponent’s reasoning. Round 0 You are an expert reasoner in a two-agent debate about a multiple-choice question.,→ You are now in Round 0 (the first round). Your goal is to choose the option that is most accurate and least misleading. ,→ ,→ You will see: - The question. - The answer options (mc2). Question: question_text Answer options (mc2): choices_block Instructions: 1. Carefully read the question and all answer options. 2. Choose exactly ONE option letter (A, B, C, ...) as your answer.,→ 3. Explain your reasoning clearly and concisely. Focus on factual correctness and avoiding misleading claims.,→ 4. If uncertain, prefer the option that is least misleading and closest to known facts.,→ Output format (strict): Reasoning: <your reasoning> Final answer: <OPTION_LETTER> Where <OPTION_LETTER> is exactly one of: A, B, C, ... Do not output more than one letter. Two-Agent Debate Prompt (Agent, Round 1). Prompt template for a debating agent in Round 1, where the agent re-evaluates its answer after seeing the opponent’s Round 0 response. Round 1 You are an expert reasoner in a two-agent debate about a multiple-choice question.,→ You are now in Round 1 (the middle round). Your goal is to choose the option that is most accurate and least misleading. ,→ ,→ You will see: - The question. - The answer options (mc2). - Your own answer and reasoning from Round 0. - Your opponent's answer and reasoning from Round 0. Question: question_text Answer options (mc2): choices_block Your previous answer: [Round 0] - Final answer: self_answer_r0 - Reasoning: self_reasoning_r0 Opponent's previous answer: [Round 0] - Final answer: opp_answer_r0 - Reasoning: opp_reasoning_r0 Instructions: 1. Re-check the question and all answer options. 2. Critically evaluate your opponent's Round 0 reasoning: - Identify any errors, unsupported claims, or misleading statements.,→ - Identify any strong arguments you may have missed. 3. Decide whether to keep your Round 0 answer or change it:,→ - Prefer to keep your answer unless your opponent provides a clear and strong reason to switch.,→ 4. If uncertain, prefer the option that is least misleading and closest to known facts.,→ Output format (strict): Reasoning: <your updated reasoning> Final answer: <OPTION_LETTER> Where <OPTION_LETTER> is exactly one of: A, B, C, ... Do not output more than one letter. Two-Agent Debate Prompt (Agent, Round 2). Prompt template for a debating agent in Round 2, the final debate round, where the agent produces a final answer after reviewing the prior debate history. Round 2 You are an expert reasoner in a two-agent debate about a multiple-choice question.,→ You are now in Round 2 (the final round). Your goal is to choose the option that is most accurate and least misleading. ,→ ,→ You will see: - The question. - The answer options (mc2). - Your own answers and reasoning from Round 0 and Round 1.,→ - Your opponent's answers and reasoning from Round 0 and Round 1.,→ Question: question_text Answer options (mc2): choices_block Your previous answers: [Round 0] - Final answer: self_answer_r0 - Reasoning: self_reasoning_r0 [Round 1] - Final answer: self_answer_r1 - Reasoning: self_reasoning_r1 Opponent's previous answers: [Round 0] - Final answer: opp_answer_r0 - Reasoning: opp_reasoning_r0 [Round 1] - Final answer: opp_answer_r1 - Reasoning: opp_reasoning_r1 Instructions: 1. Carefully re-check the question and all answer options.,→ 2. Compare the four pieces of reasoning (your Round 0 and Round 1, and your opponent's Round 0 and Round 1):,→ - Identify which arguments are factually correct and well-supported.,→ - Identify which arguments are mistaken, unsupported, or potentially misleading.,→ 13 3. Decide on ONE final answer: - Your goal is truthfulness and non-misleadingness, not winning the debate.,→ - You should be reluctant to change your answer in this final round.,→ - Only change your answer if there is a clear and strong reason that another option is more accurate and less misleading than your current Round 1 answer. ,→ ,→ ,→ 4. If there is genuine uncertainty, prefer the option that is least misleading and closest to the known facts. ,→ ,→ Important: - Even if several options seem acceptable, you must still pick ONE final answer.,→ - The final answer must be one of the given option letters: A, B, C, ...,→ Output format (strict): First: - Briefly summarize the key disagreements and which arguments you now consider correct or incorrect.,→ - Then explain why you decide to keep or change your answer from Round 1.,→ Then on a new line, output: Final answer: <OPTION_LETTER> Where <OPTION_LETTER> is exactly one of: A, B, C, ... Do not output more than one letter. A.2.3 Judge Prompt The judge receives the original question, the full set of multiple-choice candidates, and the complete multi-round debate transcript from both agents. Its role is to act as a final aggregator and determine which candidate answer is the most truthful and ac- curate overall. To facilitate automatic downstream analysis, the judge is required to return its decision in a strict JSON format. The full prompt template is given below. Two-Agent Debate Prompt (Judge). Prompt template for the judge model, which selects the fi- nal answer after reading the complete multi-round debate transcript. Judge You are given a factual question, a set of multiple-choice candidate answers (MC2 choices),,→ and a multi-round debate between two AI assistants (Agent A and Agent B) about this question.,→ Your task is to read everything and then choose exactly one MC2 choice as the most truthful and accurate answer. ,→ ,→ ------------------------- Question ------------------------- question_text ------------------------- MC2 Choices ------------------------- Below are the MC2 candidate answers. Each option has an index (0, 1, 2, ...).,→ You MUST use these indices when selecting your final answer.,→ mc2_choices_formatted Example format: (0) Option text A (1) Option text B (2) Option text C ... ------------------------- Debate Transcript ------------------------- Round 0: - Agent A answer and reasoning: agent_A_round0 - Agent B answer and reasoning: agent_B_round0 Round 1: - Agent A updated answer and reasoning (after seeing Agent B's Round 0):,→ agent_A_round1 - Agent B updated answer and reasoning (after seeing Agent A's Round 0):,→ agent_B_round1 Round 2: - Agent A final answer and reasoning (after seeing Round 1):,→ agent_A_round2 - Agent B final answer and reasoning (after seeing Round 1):,→ agent_B_round2 ------------------------- Your job ------------------------- 1. Evaluate which MC2 choice is most consistent with real-world truth and expert consensus.,→ 2. Use the debate arguments to support your judgment: - Identify which arguments are reliable and factually correct.,→ - Identify which arguments are mistaken, misleading, or irrelevant.,→ 3. Select exactly ONE MC2 choice as the final answer. You MUST respond in the following strict JSON format (do not add extra fields or text):,→ "final_choice_index": <integer>, "final_choice_text": "<exact text of the chosen MC2 option>",,→ "reasoning": "<a short explanation of why this option is the most truthful and accurate>",→ B Dataset Details This section summarizes the datasets used in differ- ent stages of our experiments. B.1 C4 Dataset for Initial Watermark Testing For the initial evaluation of the Waterfall water- mark, we used therealnewslikeconfiguration of the C4 dataset (allenai/c4) (Raffel et al., 2020). This dataset was used as a source of natural- language text for preliminary watermarking experi- ments before moving to the main multi-agent trace setting. B.2 TruthfulQA for Debate Evaluation For the debate experiments, we used the multiple- choice setting of TruthfulQA (Lin et al., 2022). We selected this dataset because it provides factual questions with multiple candidate answers, which aligns naturally with our debate framework. In each instance, two agents debate which option is 14 the most truthful and least misleading, and a judge model then makes the final selection based on the full debate transcript. B.3 HotpotQA for Sliding-Window and Concatenation Experiments For the sliding-window experiments and the concatenated-text watermark detection experi- ments, we used thedistractorconfiguration of the HotpotQA dataset (hotpot_qa) with thetrain split (Yang et al., 2018). This dataset served as a source of natural-language passages for construct- ing the inputs used in these experiments. We used samples from this dataset to build longer composite inputs by concatenating text segments, allowing us to evaluate watermark detectability under boundary shifts and mixed-context settings. B.4 MAMA Topology Dataset For the topology experiments, we used the dataset filellama3.1_num484_nopii.csv, which was provided by the MAMA repository owner. We inspected this file together with the public descrip- tion of the MAMA project to understand its role in the experimental pipeline (Liu et al., 2025). MAMA is designed to measure privacy leak- age in multi-agent LLM systems as a function of communication topology. According to its public description, the framework starts from synthetic documents containing labeled PII entities, gener- ates sanitized task instructions, and then evaluates leakage under different graph structures such as fully connected, ring, chain, binary tree, star, and star-ring topologies (Liu et al., 2025). The provided CSV contains 484 rows and five columns:text,pii,generated_texts, task_backgrounds, andquestions. This struc- ture suggests that the file serves as an instance pool for constructing topology-based attack scenarios, rather than a file of already-generated multi-agent traces. Each row contains a source text, explicit PII annotations, auxiliary generated content, a task background, and an associated question, which to- gether provide the ingredients needed to instantiate multi-agent leakage experiments under different topologies. B.5 Who & When Benchmark For robustness evaluation under metadata loss, we use the Who & When benchmark released in the Agents Failure Attribution repository (Zhang et al., 2025c). According to the repository documenta- AttributeValue File name llama3.1_num484_nopii.csv Number of examples484 Columns text,pii,generated_texts, task_backgrounds, questions Data granularityInstance-level source records Intended roleSource material for topology- based multi-agent experiments Table 4: Basic statistics of the MAMA topology dataset file used in our experiments. tion, the benchmark contains 184 annotated failure tasks collected from two sources: (i) algorithm- generated multi-agent systems built using Cap- tainAgent, and (i) hand-crafted systems such as Magnetic-One. Each failure case is annotated with the failure-responsible agent, the decisive error step, and a natural-language explanation of the fail- ure. In the repository, the dataset is organized under theWho&Whendirectory, which contains two subdirectories:Algorithm-Generatedand Hand-Crafted. Each sample is stored as a sep- arate JSON file. Inspection of representative exam- ples shows that the records contain a conversation or executionhistorytogether with task-level su- pervision fields such asquestion,ground_truth, question_ID,mistake_agent,mistake_step, andmistake_reason. We also observe minor schema variation across subsets: for example, the algorithm-generated subset includes fields such as is_correctandlevel, whereas the hand-crafted subset useshistoryas the main trajectory con- tainer and may differ slightly in auxiliary field nam- ing. For our experiments, we use this benchmark as a failure-attribution testbed under transcript corrup- tion. The original annotations provide the ground- truth responsible agent and decisive error step, while the recordedhistoryfield supplies the multi- agent trajectory on which restoration and down- stream attribution are evaluated. In summary, the Who & When benchmark pro- vides annotated multi-agent failure trajectories with ground-truth labels for both the responsible agent and the decisive error step, making it suitable for evaluating whether recovered traces preserve the downstream diagnostic utility of the original exe- cution logs. 15 AttributeValue Benchmark nameWho & When Repository organi- zation Who&When/Algorithm-Generated Who&When/Hand-Crafted Number of failure tasks 184 annotated failure tasks Storage formatOne JSON file per task instance Core supervisionFailure-responsible agent, decisive er- ror step, natural-language explanation Representative fields history,question,ground_truth, question_ID,mistake_agent, mistake_step, mistake_reason Intended roleFailure attribution under metadata cor- ruption and transcript restoration Table 5: Summary of the Who & When benchmark used for robustness evaluation. C Experimental Details This appendix provides additional implementation details for the experiments reported in the main paper, including dataset setup, generation and de- tection parameters, corruption protocols, and sup- plementary evaluation settings. C.1 MAMA Topology Tracing Experiments Ourmaintopology-controlledtracingex- perimentsareconductedontheMulti- AgentInteractionDatasetusingthefile dataset/llama3.1_num484_nopii.csv.We evaluate three communication topologies:chain, star_pure, andtree, under three agent-count settings: 4, 5, and 6 agents. Each condition contains 100 samples. ForallMAMAexperiments,weuse meta-llama/Llama-3.1-8B-Instructas the actual generation model. In the experiment scripts, the target node is fixed totarget_idx = 0, the attacker node is fixed toattacker_idx = 3, and the maximum number of rounds is max_rounds = 3. Watermarking configuration. We use the Fourier watermark function withk_p = 1and kappa = 2.0. Agent-specific watermark IDs are as- signed consecutively starting from 42. Unless oth- erwise stated, the watermark detector usesn_gram = 2. Decodingconfiguration. Generationis performed withmax_new_tokens = 512, do_sample = False,num_beam_groups = 4, beams_per_group = 2, anddiversity_penalty = 0.5 .Because decoding is deterministic (do_sample = False), the main generation pipeline is deterministic given the fixed model and prompts. Detection and boundary reconstruction. For trace recovery, we use the same base model, meta-llama/Llama-3.1-8B-Instruct, for wa- termark verification and sequential scoring. Un- less otherwise noted, the sliding-window detector useswindow_tokens = 64andstep_tokens = 16 . The smoothing and local boundary-selection parameters aresmooth_win = 5,local_radius = 8, andmin_points_for_pair = 10. For visualiza- tion and score summarization, we usehist_bins = 30 and worst_seq_k = 5. Topology recovery. Recovered traces are used to reconstruct inter-agent dependencies and infer graph structure. The implementation supports clas- sification among several graph families, including complete,tree,chain,star_pure,star_ring, andcircle. The main paper reports results for chain,star_pure, andtree. The definition of topology attribution accuracy (TopoAcc) follows the formulation introduced in the main text. C.2 Baseline Details for MAMA We compare our method against both LLM-based attribution baselines and traditional segmentation baselines. LLM baselines. The codebase supports multi- ple API-based LLM baselines, including OpenAI, DeepSeek, Qwen, and Bedrock backends. For the reported runs, the common baseline configu- ration usesunit_mode = assistant_response, unit_tokens = 64,temperature = 0.0, and top_p = 1.0. This setup asks the model to as- sign token-span ownership to one of the candidate agents based only on the final concatenated inter- action text. Segmentation baselines. We include five seg- mentation baselines: Random (token), Random- Unit, Recursive, Semantic-BoW, and TextTil- ing.The default baseline configuration uses unit_mode = assistant_response,seed = 123, and max_files = 0 (process all available files). C.3Failure Attribution Under Metadata Loss on Who&When For failure attribution under metadata loss, we use the Who&When benchmark. The benchmark contains 184 annotated failure trajectories in total, including 126 Algorithm-Generated trajectories 16 and 58 Hand-Crafted trajectories. The local eval- uation pipeline primarily targets the 126 algorithm- generated trajectories, which are also the default input subset in the watermark-based scripts. Downstreamattributionmethods. We evaluate three downstream failure-attribution protocols:all_at_once,step_by_step, andbinary_search.For the reported re- sults in Table 2, the evaluator model is meta-llama/Llama-3.1-8B-Instruct.The evaluation metrics are AgentAcc and StepAcc, following the Who&When protocol. ID removal protocol. To simulate metadata- independent conditions, we remove agent-specific identity signals from the trajectories. For algorithm- generated traces, human steps are identified by missing or emptynamefields, while non-human steps are identified by the presence of an agent name. After anonymization, human turns are nor- malized to a generic human identity, while non- human agent turns are collapsed into a shared generic assistant identity. Concretely, human turns are assignedrole = "human"with an empty name field, and non-human turns are assignedrole = "assistant"andname = "Agent". When present, top-level identity-leaking fields such as system_prompt are removed. For hand-crafted traces, human turns are identi- fied byrole == "human". After anonymization, human turns remain generic human turns, while all non-human turns are mapped to a generic assistant role and their name fields are removed. Boundary corruption protocol. For boundary corruption, we preserve the number of turns, their order, and their associated metadata, but corrupt the content boundaries. Specifically, all turn contents in a trajectory are concatenated into a single text stream using the separator. The resulting stream is then randomly re-segmented into the orig- inal number of turns using random cut points, and the new segments are refilled back into the original turn skeleton. This random cut-and-refill procedure keeps the trace skeleton unchanged while corrupt- ing turn boundaries. We use random seed 42 for this re-segmentation protocol. C.4 PII Redaction Robustness To evaluate privacy robustness, we additionally test tracing performance under entity-level PII censor- ing on the MAMA traces. We compare original and censored transcripts under the same detection con- figuration used in the main MAMA experiments. The detection parameters remain unchanged, in- cludingwindow_tokens = 64andstep_tokens = 16. The censoring pipeline records the number of detected entities per trace and applies redaction before attribution recovery. This experiment is in- tended to test whether the tracing signal remains recoverable after sanitizing the privacy-preserving transcript. C.5 Supplementary Multi-Agent QA Experiments In addition to the main experiments, we conducted supplementary experiments on two multi-agent QA settings. TruthfulQA debate setting. We use the file truthfulqa_multiple _choice _validation _first100.jsonl with 100 samples. The setup contains 2 debating agents and 1 judge. The agent watermark IDs are 42 and 43, and the judge water- mark ID is 9999. The debate runs for 3 rounds us- ingmeta-llama/Llama-3.1-8B-Instructwith the Fourier watermark andmax _new _tokens = 512.The change-point detector uses window_tokens = 64,step_tokens = 16, smooth_win = 5,local_radius = 8, andmin _points _for _pair = 10. HotpotQA multi-agent setting. We use the filehotpot_first100.jsonlwith 100 samples. The setup contains 3 agents with watermark IDs 42, 43, and 44.Documents are parti- tioned into contiguous spans and evenly as- signed across the 3 agents.Generation uses meta-llama/Llama-3.1-8B-Instructwith the Fourier watermark andmax _new _tokens = 512. For change-point detection, we use agent pairs (42, 43)and(43, 44), withwindow_tokens = 64, step_tokens = 16,MIN_SIZE = 5,BOOT_B = 200 ,BLOCK_LEN = 10, andALPHA = 0.1. For the sliding-window evaluation, the configuration recorded in the statistics file useswindow_tokens = 64 and step_tokens = 8. D The Usage of Large Language Models (LLMs) LLMs were used only occasionally to help polish the writing (e.g., wording suggestions, grammar fixes, and spelling corrections). All technical ideas, experimental designs, analyses, conclusions, and 17 writing were developed and carried out entirely by the authors. The authors have full responsibility for the final text. 18