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

Jul 16, 2026

TRACE addresses attribution of LLM-agent behavior when resellers may rebrand or replace models and when adversaries have full read/write access to the trajectory evidence. It reframes watermarking for agent action streams and introduces a two-channel watermark: a selection channel that is distortion-free, self-synchronizing under deletion, and invariant to rewriting; and a tally channel keyed on the log skeleton that rewriting cannot alter. Experiments on ToolBench and ALFWorld match baseline success while achieving near-perfect detection on long-horizon trajectories and strong deletion robustness.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages41

Reading Time1 h 43 min

Introduction

Agent trajectory logs and attribution needs

Why token-level watermarking fails for agents

From behavior biasing to action-stream watermarks

TRACE two-channel design (selection and tally)

arXiv :2607 .08400v 1 [ cs .CR] 9 Jul 2026 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Zheng Gao1 Xiaoyu Li1 Xiaoyan Feng2 Jiaojiao Jiang1 Yang Song1 Yulei Sui1 Zhenchang Xing3 Liming Zhu3 1University of New South Wales {zheng.gao1, [xiaoyu.li2](xiaoyu.li2) , jiaojiao.jiang, [yang.song1](yang.song1) , [y.sui}@unsw.edu.au](y.sui}@unsw.edu.au) [2](2 Griffith University xiaoyan.feng@griffithuni.edu.au)[ Griffith University](2 Griffith University xiaoyan.feng@griffithuni.edu.au)[ xiaoyan.feng@griffithuni.edu.au](2 Griffith University xiaoyan.feng@griffithuni.edu.au) 3 CSIRO’s Data61 {zhenchang.xing, [liming.zhu}@data61.csiro.au](liming.zhu}@data61.csiro.au) LLM agents reach users through resellers, who may rebrand a developer’s agent or substitute a cheaper model. When provenance is disputed, attribution rests on the trajectory log (the record of tool calls, observations, and executed actions, not the model’s reasoning), which the reseller stores and processes to meter usage. A watermark must therefore survive an adversary with full read/write access to the very evidence it is detected from; existing agent watermarks do not, as their attribution is read straight off that log. We present TRACE, to our knowledge the first agent watermark that is distortion-free in its action choices, self-synchronizing under deletion, and unconditionally invariant under rewriting. Deletion desynchronizes a position-derived key and rewriting alters content, so a deletion-robust key must come from content and a rewrite-robust key from position, and no single key serves both. A trajectory, however, has room for two watermarks. TRACE superposes a selection channel that sets which action is chosen, keyed on local content with a distortion-free sampler, so the agent’s distribution is provably unchanged and detection resynchronizes after deletions, and a tally channel that sets how many records each decision group holds, keyed on the log’s skeleton alone, which no rewriting can touch. We prove this behavioral watermark’s signal is bought with decision entropy, each decision paying at least half its entropy and deterministic decisions nothing, and that erasing both channels forces the reseller to corrupt the trajectories it resells. On ToolBench and ALFWorld, TRACE matches the unwatermarked agent’s success rate while its selection channel reaches detection scores near z = 100 on long-horizon trajectories, stays detectable under 70% step deletion, and keeps a tally channel exactly unchanged under LLM rewriting of any strength. Figure 1 | The reseller threat model: the adversary owns the evidence it audits. 1. Introduction Large language model agents no longer merely produce text: they invoke search APIs, file tickets, send messages, book services, execute code, and respond to security incidents [Yao et al., 2022, Schick et al., 2023, Qin et al., 2024, Park et al., 2023, Li et al., 2026] . Actions carry consequences that prose does not. An operator audited after an incident must show which of the logged actions its agent did and did not take. When agent behavior causes harm, attribution is the first step of liability. Governance proposals reach the same point from the policy side, calling for visibility into agent activity through identifiers and activity logs [Chan et al., 2024] . Every one of these needs runs through the same artifact, the agent’s trajectory log, and the log serves them only if it can be attributed to the agent that produced it. Throughout, trajectory means this execution trace, the logged tool calls, observations, and actions, not the model’s reasoning trace or a bare conversation history. A system exposing no such trace (a chat model’s single response, an image generator’s single image) presents no decision sequence for Trace to mark. For text, provenance has a mature answer: watermarking. Biasing or derandomizing the token sampler with a secret key le

FAQs

What problem does TRACE solve in LLM-agent attribution?

TRACE targets attribution when a reseller disputes provenance by rebranding or substituting agents. It assumes adversaries can access and modify the same trajectory evidence used for detection, so watermark signals must remain reliable under that threat model.

Why are token-level watermarking methods not sufficient for agent trajectories?

Agent systems translate decisions into structured action logs that largely discard the original token stream, leaving no token-level signal. Trajectories also have limited decision counts and many low-entropy decisions where shifting probability mass could degrade task success.

How does TRACE achieve robustness against deletion and rewriting?

TRACE uses two complementary watermark channels: a selection channel that is distortion-free and self-synchronizing after deletions, with keys split to ensure deletion-robustness comes from content and rewrite-robustness from position. It also includes a tally channel keyed to the log’s skeleton so rewriting cannot change it, and both channels together force attackers to corrupt trajectories if they attempt to erase the signal.

Jul 16, 2026

Upload by Valentina