TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories

🕒 Published (v1): 2026-07-09 12:25 UTC · Source: Arxiv · link

Why this paper was selected

Watermarking LLM-agent trajectories for provenance; security primitive for agent systems

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

TRACE is a two-channel behavioral watermark for LLM-agent trajectory logs that survives an adversary — a reseller — who has full read/write access to the evidence. It superimposes a content-keyed selection channel (deletion-robust, distortion-free) and a skeleton-keyed tally channel (unconditionally rewrite-invariant) on each decision group, with provable guarantees rather than empirical robustness claims. On ToolBench and ALFWorld it matches the unwatermarked agent's task success while achieving near-perfect detection under either attack axis.

Problem

LLM agents increasingly reach end-users through resellers who may rebrand the upstream provider's agent or silently substitute a cheaper model. Attribution relies on the trajectory log (the structured record of tool calls and observations), but the reseller who meters usage also stores and controls that log. Existing agent watermarks (Agent Guide, AgentMark, AgentWM, ActHook) carry a single signal under a single keying and measure robustness against generic perturbations — none is designed for an adversary with lawful write access to the evidence. Two orthogonal laundering moves break any single-channel scheme: deletion (dropping records desynchronizes position-derived keys) and rewriting (paraphrasing observation text and renaming actions destroys content-derived keys). No single keying is resistant to both.

Method

TRACE formalizes a reseller threat model in which the adversary may freely read/write the log but cannot re-execute actions or forge the action stream.

Trajectory structure. A trajectory \(\tau = (e_1,\ldots,e_T)\) alternates dec (agent decision) and obs (environment observation) records. The skeleton \(s(\tau)\) is the tag sequence; it is invariant under rewriting. Records are partitioned into decision groups \(g_1,\ldots,g_m\), each comprising one dec record plus its subsequent obs records.

Selection channel (content-keyed, deletion-robust). At each effective group \(g_i\), the action \(b_i\) is sampled via an exponential race (Kuditipudi et al. 2023 lifted to behaviors): $\(r_b = \text{DRBG}(\text{key}_1, \text{ctx}_i \| b), \quad b_i = \operatorname{argmax}_{b \in B_i} r_b^{1/P_i[b]}\)$ where \(\text{ctx}_i\) encodes the preceding action sequence \(A_{i-1}\). This is distortion-free: the sampled distribution equals \(P_i\) exactly (Theorem 5.1). Detection replays the race and pools \(\varphi_i = -\ln(1-r_{b_i})\), which is stochastically larger than \(\text{Exp}(1)\) under \(H_1\), into a z-score \(z_1\). Content keying means a deletion only corrupts keys in the immediate neighborhood, so detection resynchronizes at the next group (Proposition D.9). Each decision contributes at least \(\frac{1}{2}H(P_i)\) nats of signal; deterministic decisions contribute zero (Theorem 5.2).

Tally channel (skeleton-keyed, rewrite-invariant). For each group \(i\), a keyed bit \(G_i \in \{1,2\}\) is drawn from \(\text{DRBG}(\text{key}_2, \text{H}(\text{qid}\|i))\); \(G_i=2\) causes the embedder to append one redundant obs record (context-neutral, no tool call) so \(k_i=2\); \(G_i=1\) leaves \(k_i=1\). The detector counts how many observed \(k_i\) match their keyed target and forms \(z_2\). Because both the counts and the keys are functions of the skeleton alone, and rewriting cannot alter the skeleton by definition, this channel is unconditionally invariant under every rewriting attack (Theorem 5.3).

Joint-erasure lower bound. Silencing both channels simultaneously requires the adversary to edit the skeleton (corrupting tally) and, unless it targets groups by their realized scores, alter \(\Omega(1)\) fraction of group contents (corrupting selection) — both actions degrade service quality and undermine the product the reseller is selling (Theorem 5.4).

The paper also introduces the LLM rewriter — a new, strongest-known informed rewriting attack where an LLM sees the genuine chosen action and substitutes a different plausible one — and sweeps it against all baselines.

Key Contributions

• Formal reseller threat model with full log read/write access, decomposing attacks into deletion and rewriting classes with the LLM rewriter as the first plausibility-preserving, informed instance.
• TRACE: the first agent watermark that is simultaneously distortion-free, deletion-self-synchronizing, and unconditionally rewrite-invariant, achieved by routing two independent watermarks through complementary invariant carriers.
• Exact finite-sample null distributions for both detectors, an entropy lower bound pricing distortion-free detectability, a pooling rate derivation, and a joint-erasure theorem with structural (not empirical) proofs.
• Introduction of the LLM rewriter attack (Definition 3.7 instantiated with an LLM), evaluated against all comparison schemes.

Results

• Task success parity: TRACE matches unwatermarked agent success rate on ToolBench and ALFWorld; the biased red-green baseline pays up to 8.1 percentage points in task success.
• Selection channel detection: z-scores near z = 100 on long-horizon ALFWorld trajectories (~23–25 effective decision steps).
• Deletion robustness: selection channel remains detectable under 70% obs-record deletion rate.
• Rewriting invariance: tally channel counts are exactly unchanged under LLM rewriting at any strength \(q \in [0,1]\).
• Attribution at 1% FPR: TRACE attributes correctly under either single-axis attack (deletion alone or rewriting alone) where a single rewriting pass erases both baselines (AgentMark and red-green).
• Combined attack: only the joint deletion+rewriting corner degrades TRACE — but at that point the reseller has already corrupted the service it resells.
• ToolBench offers only ~1.4 effective decision groups per task (low entropy per step), making it the harder regime; ALFWorld's ~23–25 steps sustain strong detection.

Limitations

• Sparse signal on short/low-entropy trajectories: only effective groups (≥2 admissible actions, non-terminal) contribute; ToolBench averages ~1.4 such groups per task, requiring cross-task pooling.
• Deterministic decisions are transparent: groups with \(H(P_i)=0\) contribute zero signal to the selection channel; agents operating in highly constrained environments yield weak watermarks.
• Combined attack is the weak corner: simultaneous high-rate deletion plus strong LLM rewriting does degrade joint detection, even though the attack also destroys service quality.
• Tally channel capacity is low: one bit per group; only gross skeleton corruption erases it, but the channel carries no multi-bit identity payload.
• Requires sampler access: the provider must control the action sampler at inference time; black-box or post-hoc watermarking of existing logs is not addressed.

Relevance to Agentic AI / LLM Agents

TRACE directly addresses the provenance and accountability gap that emerges when LLM agents are deployed through multi-party supply chains — a governance concern growing in urgency as agents take consequential real-world actions. The formalization of the reseller threat model (adversary owns the evidence log) is a practically grounded and previously underexplored threat surface in the agent-watermarking literature, complementing work on imitation defense and dataset copyright. The distortion-free guarantee is critical for deployment: any watermark that degrades task success will be rejected by operators, and TRACE's entropy-lower-bounded signal shows exactly what is paid for detectability. More broadly, the dual-channel design — pairing content-invariant and structure-invariant embeddings as complementary defenses — is a transferable architectural pattern for securing other structured agent artifacts (e.g., multi-agent communication logs, tool-call audit trails).