[ICML 2025] Implicit Execution Tracing: When the Final Text is Your Only Map to Agent Accountability

TL;DR

As multi-agent systems move into production, the "Who-Said-What" problem becomes a nightmare for auditors when execution logs are deleted for privacy. Implicit Execution Tracing (IET) solves this by embedding invisible, agent-specific signatures directly into the word choices of the LLM. It allows anyone with a secret key to reconstruct the entire interaction history—including the "who" and the interaction graph—purely from the final text output, with 94%+ accuracy.

The "Copy-Paste" Accountability Crisis

In the real world, AI-generated reports don't come with a 50MB execution log attached. They are copied into emails, Slack messages, and PDFs. Once the text leaves the server, the link to its "provenance" (which agent did what) is severed.

Existing SOTA diagnostic tools like Who&When or FAMAS fail here because they are inference-based: they try to guess the error source by looking at the content. IET proposes a shift to instrumentation: making the text itself the log.

Methodology: High-Fidelity Signal Embedding

The core of IET is to treat agent identity as a "keyed signal" injected into the token distribution.

1. Keyed Distributional Modulation

When Agent $A$ is generating text, IET doesn't just sample the most likely word. It applies a small, secret-key-controlled perturbation to the logits ($L_j$): $ilde{L}_j=\mathcal{W}(a_k,L_j)$ This perturbation is subtle enough that it doesn't degrade text quality (KL-divergence remains low), but it creates a statistical "fingerprint" only detectable if you have the agent's key.

2. Boundary and Topology Recovery

To figure out where one agent stopped and another began, IET uses Competitive Change-Point Detection. It calculates a "competitive margin" ($z_t$) which measures which agent's signal is currently winning. When the margin shifts significantly (calculated via a Cumulative Sum or CUSUM algorithm), a handover point is identified.

Figure 1: The IET Workflow—from keyed generation to statistical reconstruction of the interaction graph.

Experimental Battleground: SOTA Results

The authors tested IET on complex topologies (Star, Chain, Tree) against heavyweights like GPT-4o and DeepSeek-v3.

• The Baseline Collapse: When agent IDs were removed (simulating a "metadata-free" scenario), GPT-4o's ability to attribute text dropped to 28% accuracy.
• IET Dominance: IET maintained 94-95% Token Accuracy and 100% Topology Accuracy (reconstructing the exact interaction graph).

Robustness to PII Redaction

One of the most impressive findings is that tracing survives PII redaction. Even if you replace "John Doe" with [NAME], the statistical signature is embedded in the non-sensitive tokens surrounding it, meaning privacy scrubbing doesn't kill the audit trail.

Table 1: IET vs. LLM Baselines. Note the near-perfect TopoAcc of our method compared to the failure of traditional segmentation.

Critical Insight: Why This Matters

The industry is racing toward "Multi-Vendor AI" where an Agent from OpenAI might delegate to an Agent from Anthropic. In such an ecosystem, who is liable for a hallucination? IET provides a technical path to Decoupled Provenance: you don't need to trust the platform's logs; you only need to trust the math embedded in the text.

Limitations

Currently, IET requires "keyed" generation. If an agent in the chain is a "black-box" API that doesn't allow logit modulation, the chain of custody is broken. Standardizing these "tracing hooks" across the industry will be the next big hurdle.

Conclusion

IET turns a liability (opaque final text) into an asset (a self-describing execution record). By proving that we can recover 100% of the interaction topology from text alone, the authors have provided a robust framework for the next generation of accountable AI systems.