The Agent Trajectory Becomes the Watermark

From Output to Trajectory

The paper is TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories, arXiv:2607.08400 [cs.CR]. The arXiv record lists Zheng Gao, Xiaoyu Li, Xiaoyan Feng, Jiaojiao Jiang, Yang Song, Yulei Sui, Zhenchang Xing, and Liming Zhu as authors, with submission on July 9, 2026. The arXiv subject listing includes Cryptography and Security, Artificial Intelligence, and Machine Learning.

The paper's first useful distinction is between a generated answer and an agent trajectory. A chatbot output is a text artifact. An agent trajectory is the execution trace: tool calls, observations, and actions taken over time. For a delegated system that searches, books, files tickets, executes code, or sends messages, the trajectory is the thing a later reviewer needs.

That changes the watermarking problem. A text watermark can live in token choices. But an agent's important record is often structured after the model's tokens have disappeared into tool calls, arguments, observations, and action entries. The authors therefore ask how to mark the behavior record itself, not the prose the model happened to emit while acting.

Reseller Threat Model

The threat model is commercial and institutional rather than mystical. LLM agents may reach users through resellers that rebrand a developer's agent or substitute a cheaper system while advertising something else. If a customer, regulator, platform, or contract reviewer later asks whether a trajectory came from a named agent, the evidence may sit in logs controlled by the reseller.

This is a hard provenance setting because the log holder is also the adversary. The reseller can delete records to shrink or sanitize the trace. It can rewrite observations, rename tools, and paraphrase entries to make the log look like its own system. A provenance mark that can be stripped by the party selling the trace is not enough.

The Spiralist reading is that attribution is not a decorative label. It is a liability precondition. Before an institution can assign responsibility for an agent action, it needs to know which agent produced the trajectory and whether the trajectory has been laundered.

Two Watermarks

TRACE uses two channels because deletion and rewriting attack different surfaces. The selection channel is keyed on local content and influences which action is selected while preserving the agent's action distribution. The authors describe this as distortion-free in the sense that the sampled behavior distribution remains the agent's distribution. The benefit of content keying is resynchronization after deleted steps.

The tally channel works differently. It keys on the log skeleton: how many records each decision group holds, not the words inside those records. Because rewriting can alter content while leaving the step structure intact, the tally channel is designed to survive content rewriting that would damage a content-keyed mark.

The two-channel design is the paper's core governance move. It does not ask one fragile marker to survive every laundering strategy. It splits the problem: one channel handles deletion better, the other handles rewriting better, and detection reasons over both. That is closer to how real evidence systems need to behave under adversarial custody.

What the Experiments Show

The arXiv abstract reports experiments on ToolBench and ALFWorld. In those settings, TRACE matches the unwatermarked agent's success rate. The selection channel reaches detection scores near z = 100 on long-horizon trajectories, remains detectable under 70 percent step deletion, and the tally channel remains exactly unchanged under LLM rewriting in the reported setup.

The paper also states an entropy cost. Signal comes from decisions with alternatives; deterministic decisions carry little or no watermarking room. That matters operationally. A short, low-entropy trajectory may need pooling or may be a poor attribution object. The watermark is not magic dust over every action. It depends on the shape of the agent's decision stream.

For governance, the valuable result is not only the benchmark number. It is the proposed unit of evidence: an agent trajectory can carry a behavioral mark even when the reseller edits the visible text. That turns the log from a passive audit artifact into a contested provenance object.

Limits and Receipts

The paper should not be read as proof that a watermarked agent is safe, truthful, authorized, or compliant. It is an attribution method under a specified threat model. It does not decide whether the agent should have taken an action, whether the action harmed someone, whether the tool result was correct, or whether the reseller's contract terms were fair.

It also depends on implementation details that governance has to preserve: key custody, trajectory schema, decision grouping, candidate-action distributions, entropy estimates, detection thresholds, false-positive calibration, pooling policy, and consistency checks between the execution record and the log offered for review. If those disappear, the watermark becomes a claim without an audit trail.

This page therefore belongs beside content provenance and watermarking, AI data provenance, agent log receipts, agent runtime governance, action certificates, and AI agent observability. The new lesson is that provenance has to follow the action stream, not only the output.

The Receipt

An agent-trajectory watermark receipt should name the provider, reseller, agent version, trajectory schema, logged tool calls, observations, executed actions, decision groups, candidate-action source, watermark channel versions, key custody, detector version, deletion test, rewriting test, threshold, false-positive calibration, pooling policy, and log/execution consistency audit.

The governance question is not whether the watermark makes the agent trustworthy. It is whether the agent's action history can still be attributed when the party selling the agent also controls the record.

Sources

• Zheng Gao, Xiaoyu Li, Xiaoyan Feng, Jiaojiao Jiang, Yang Song, Yulei Sui, Zhenchang Xing, and Liming Zhu, TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories, arXiv:2607.08400 [cs.CR], submitted July 9, 2026.
• arXiv experimental HTML for TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories, checked for the reseller threat model, trajectory definition, selection channel, tally channel, deletion and rewriting analysis, benchmark reports, and practical notes.
• arXiv API record for arXiv:2607.08400, checked for title, authors, subject categories, submission date, and version metadata.

Return to Blog