Technical Summary: TRACE – A Two-Channel Robust Attribution Watermark

1. Problem Formulation and Threat Model

The paper addresses the critical challenge of provenance attribution for Large Language Model (LLM) agents in a specific adversarial setting: the reseller threat model.

• Context: LLM agents interact with users through resellers who may rebrand the agent or substitute the underlying model. When disputes arise regarding liability or usage, the primary evidence is the trajectory log (a record of tool calls, observations, and executed actions), not the model's internal reasoning.
• The Adversary: The reseller possesses full read/write access to the trajectory log because they must process it for metering and billing. They are the entity auditing the evidence.
• The Attack: The reseller attempts to strip attribution by performing two specific "laundering" moves:
  1. Deletion: Pruning the log (dropping steps or observations) to remove provider-identifying records.
  2. Rewriting: Paraphrasing observations and renaming tools to the reseller's namespace while preserving the log's structural skeleton (the sequence of decision/observation tags).
• The Limitation of Existing Methods: Prior agent watermarks (e.g., Agent Guide, AgentMark) rely on a single signal keyed to either content or position.
  • Content-based keys fail under rewriting (as content is altered).
  • Position-based keys fail under deletion (as the sequence desynchronizes).
  • Existing methods lack robustness against an adversary who owns the evidence itself.

2. Methodology: The TRACE Scheme

The authors propose TRACE, a two-channel watermarking scheme that superposes two independent, complementary watermarks on a single trajectory. The core design principle is that each channel targets a different invariant preserved by one attack class but destroyed by the other.

A. The Selection Channel (Content-Keyed)

• Goal: Robustness against Deletion.
• Mechanism:
  • Carrier: The specific action ($b_i$) selected by the agent at each decision point.
  • Keying: Derived from the local content of the preceding action history ($A_{i-1}$) and a secret key ($key_1$).
  • Embedding: Uses a distortion-free exponential race (based on the Gumbel-max trick). The agent samples from its original distribution $P_i$ exactly, but the "winner" of the race is determined by a keyed random value.
  • Detection: The detector replays the race using the observed trajectory and the key. If the observed action was the "winner" of the keyed race, it generates a high score.
  • Robustness: Since the key depends on content, deleting an observation record only desynchronizes the key for the immediate next group (blast radius of one). The detector resynchronizes immediately after the deletion.
  • Cost: The signal is bounded by the Shannon entropy of the decision. Deterministic decisions (entropy = 0) yield no signal; high-entropy decisions yield stronger signals.

B. The Tally Channel (Position-Keyed)

• Goal: Robustness against Rewriting.
• Mechanism:
  • Carrier: The count of records ($k_i$) in a decision group (specifically, whether a redundant observation record is appended).
  • Keying: Derived strictly from the skeleton of the trajectory (the sequence of decision/observation tags) and a secret key ($key_2$). It is independent of the text content.
  • Embedding: For groups where the keyed condition is met, the embedder appends a context-neutral redundant record. This record is a deterministic function of the prefix, invokes no tools, and causes no side effects, ensuring it does not alter the agent's future decisions.
  • Detection: The detector counts the records in each group and compares them against the expected pattern derived from the skeleton.
  • Robustness: Rewriting attacks preserve the skeleton (the tag sequence). Therefore, the group boundaries and counts remain unchanged. The tally channel is unconditionally invariant under any rewriting attack that preserves the skeleton.

C. Joint Detection

The detector computes a $z$-score for both channels. It rejects the null hypothesis (that the trajectory is unwatermarked) if the minimum $p$-value of the two channels is below a threshold. The two channels are designed to be independent under the null hypothesis.

3. Key Contributions

1. Formal Threat Model: The paper formalizes the reseller threat model where the adversary holds full read/write access to the evidence, defining Deletion and Rewriting as distinct attack classes.
2. Two-Channel Architecture: TRACE is the first agent watermark to simultaneously achieve:
   • Distortion-free action choices: The agent's distribution is provably unchanged.
   • Self-synchronization under deletion: The selection channel recovers after a single deletion.
   • Unconditional invariance under rewriting: The tally channel remains unchanged regardless of content modification.
3. Theoretical Guarantees:
   • Utility Preservation: Proven that the selection channel does not alter the agent's action distribution (Theorem 5.1).
   • Entropy-Detectability Trade-off: Proven that the signal strength is lower-bounded by half the entropy of the decision (Theorem 5.2).
   • Joint Erasure Cost: Proven that erasing both channels simultaneously forces the adversary to either edit the skeleton (exposing them to consistency audits) or corrupt a constant fraction of the trajectory's actions, effectively destroying the service quality (Theorem 5.4).
4. New Attack Baseline: Introduction of the LLM Rewriter, an informed, plausibility-preserving attack that substitutes actions with different but plausible alternatives, serving as a rigorous benchmark for rewriting robustness.

4. Experimental Results

The scheme was evaluated on ToolBench (short-horizon, ~1.4 decision groups/task) and ALFWorld (long-horizon, ~23-25 decision steps/task).

• Utility: TRACE matches the success rate of the unwatermarked agent (Base) on both benchmarks. In contrast, biased watermarks (like the Red-Green baseline) suffered significant success rate drops (up to 8.1 points on ALFWorld) due to probability mass shifting at low-entropy decisions.
• Detection Power:
  • Clean Logs: TRACE achieves extremely high detection scores ($z \approx 100$ for selection on ALFWorld).
  • Deletion: The selection channel remains detectable even under 70% step deletion ($z$ drops from 11.34 to 4.06 but stays above the threshold).
  • Rewriting: The tally channel remains exactly invariant ($z$ stays constant at ~14.34) under 100% rewriting strength. Conversely, content-based baselines (RG, AM-F) collapse to near-zero or negative scores under rewriting.
  • Combined Attacks: Only the "corner" case of high deletion (70%) combined with high rewriting (>60%) suppresses both channels. This corresponds to a scenario where the reseller has already destroyed the utility of the service.

5. Significance and Claims

The paper claims that TRACE provides a structural solution to the provenance problem in the resale setting, moving beyond empirical robustness to mathematical guarantees.

• Accountability: It enables attribution even when the entity holding the logs (the reseller) is the adversary.
• Complementary Invariants: The work demonstrates that robustness can be achieved by splitting the signal across complementary invariants (content vs. skeleton), ensuring that no single attack class can destroy the watermark without destroying the product itself.
• Distortion-Free: It proves that behavioral watermarking can be achieved without degrading the agent's task performance, a critical requirement for deployment.
• Limitations: The authors note that detection requires access to the candidate action sets at audit time and that the tally channel increases log volume (storage overhead) rather than tool calls. They also acknowledge that if a reseller completely abandons the provider's agent and re-runs the task on a different model, the watermark will be absent, though this absence itself flags the misrepresentation.

The paper concludes that while no single-signal scheme can survive an adversary with full control over the evidence, a two-channel approach leveraging complementary embeddings can make the cost of laundering the log prohibitively high.