Paper deep dive

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

Zheng Gao, Xiaoyu Li, Xiaoyan Feng, Jiaojiao Jiang, Yang Song, Yulei Sui, Zhenchang Xing, Liming Zhu

Year: 2026Venue: arXiv preprintArea: cs.CRType: PreprintEmbeddings: 121

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%

Last extracted: 7/10/2026, 5:37:39 AM

Summary

The paper introduces TRACE, a two-channel robust attribution watermark for LLM-agent trajectories designed to withstand a reseller adversary with full read/write access to trajectory logs. It employs a content-keyed selection channel for deletion robustness and a position-keyed tally channel for rewriting invariance, evaluated on ToolBench and ALFWorld.

Entities (15)

ALFWorld · benchmark · 99%CSIRO Data61 · organization · 99%Griffith University · organization · 99%ToolBench · benchmark · 99%University of New South Wales · organization · 99%TRACE · method · 98%Reseller · role · 97%Deletion Attack · attack · 96%Rewriting Attack · attack · 96%Selection Channel · component · 95%Tally Channel · component · 95%ActHook · method · 94%Agent Guide · method · 94%AgentMark · method · 94%AgentWM · method · 94%

Relation Signals (15)

Zheng Gao → affiliatedwith → University of New South Wales

confidence 99% · Zheng Gao 1 Xiaoyu Li 1 ... 1 University of New South Wales

Zhenchang Xing → affiliatedwith → CSIRO Data61

confidence 99% · 3 CSIRO’s Data61 {zhenchang.xing, liming.zhu}@data61.csiro.au

Xiaoyan Feng → affiliatedwith → Griffith University

confidence 99% · 2 Griffith University xiaoyan.feng@griffithuni.edu.au

TRACE → evaluatedon → ALFWorld

confidence 98% · On ToolBench and ALFWorld, TRACE matches the unwatermarked agent's success rate

TRACE → evaluatedon → ToolBench

confidence 98% · On ToolBench and ALFWorld, TRACE matches the unwatermarked agent's success rate

Reseller → performs → Rewriting Attack

confidence 96% · To rebrand what it forwards, the reseller rewrites the log: it paraphrases observations and renames tools into its own namespace while preserving the step structure. This is a rewriting attack.

Reseller → performs → Deletion Attack

confidence 96% · To shrink and sanitize what it forwards, the reseller prunes the log: it drops steps, truncates, and discards records that betray the upstream provider. This is a deletion attack.

TRACE → implements → Selection Channel

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

120,140 characters extracted from source content.

Expand or collapse full text

Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Zheng Gao 1 Xiaoyu Li 1 Xiaoyan Feng 2 Jiaojiao Jiang 1 Yang Song 1 Yulei Sui 1 Zhenchang Xing 3 Liming Zhu 3 1 University of New South Wales zheng.gao1, xiaoyu.li2, jiaojiao.jiang, yang.song1, y.sui@unsw.edu.au 2 Griffith University xiaoyan.feng@griffithuni.edu.au 3 CSIRO’s Data61 zhenchang.xing, 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. arXiv:2607.08400v1 [cs.CR] 9 Jul 2026 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 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 lets a detector that holds the key distinguish watermarked output from natural text [Kirchenbauer et al., 2023, Aaronson and Kirchner, 2023, Kuditipudi et al., 2023, Christ et al., 2024], and the approach is deployed at production scale [Dathathri et al., 2024]. For agents, however, token-level watermarks are the wrong primitive, for three reasons. First, the log does not store the token stream. An agent’s decisions are translated into structured records of behaviors and actions, tool calls, their arguments, and the environment’s observations, and the sampled tokens that would carry a text watermark are largely lost in that translation [Huang et al., 2025, 2026]. The artifact that survives, and the one that matters for attribution, is the action stream. Second, the signal-bearing units are scarce. A trajectory carries its identity in the decision sequence, and decisions number in the single digits to a few dozen per task: we measure roughly 1.4 effective decision groups per task on ToolBench and 23 to 25 decision steps per task on ALFWorld, far below the token counts at which text watermarks attain power. Third, agent decisions are frequently low-entropy, often admitting a single tool, and any watermark that moves probability mass at such steps directly damages task success. The watermark has accordingly begun to move from the tokens to the behavior. Agent Guide [Huang et al., 2025] biases the agent’s high-level choices toward a keyed subset and detects the bias with a z-statistic. AgentMark [Huang et al., 2026] removes the bias, embedding a multi-bit identifier into planning decisions through distribution-preserving conditional sampling under black-box APIs. AgentWM [Wang et al., 2026] biases selection among semantically equivalent tool paths, so that the signal survives into models trained to imitate the agent. ActHook [Meng et al., 2026] watermarks trajectories as training data, planting keyed hook actions that resurface in any model trained on a stolen log. The decision stream, these works establish, is a viable carrier. They differ in goal, from provenance to imitation defense to dataset copyright, but share one structure: each carries its signal once, under one keying, and measures robustness empirically against generic perturbations. Their adversaries perturb logs, paraphrase text, or train imitators. None of them holds the evidence itself. Yet that is exactly the party through which agents increasingly reach users. A reseller licenses a developer’s agent and forwards it to customers, but advertises it as something it is not (Figure 1): as the reseller’s own in-house system, or as a premium, safety-evaluated provider while a cheaper model runs underneath, a substitution pattern cost-aware LLM deployments already practice systematically [Zhang et al., 2026]. Metering and billing already require the reseller to process every trajectory, so it is entitled to store, read, and edit the very logs from which provenance would be judged. When a harmed customer, a contested contract, or a platform auditing a partner’s traffic raises the question did this trajectory come from that agent?, the answer must be established 2 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories against an adversary who owns the evidence. Attribution that the log-holder can quietly strip is no attribution at all. The reseller’s two natural laundering moves pull keying design in opposite directions. To shrink and sanitize what it forwards, the reseller prunes the log: it drops steps, truncates, and discards records that betray the upstream provider. This is a deletion attack. Deletion desynchronizes any position- derived key, so surviving it demands a key derived from local content, which lets detection re-align at the very next decision after a dropped record. To rebrand what it forwards, the reseller rewrites the log: it paraphrases observations and renames tools into its own namespace while preserving the step structure. This is a rewriting attack. Rewriting can alter every content field, so surviving it demands a key derived from position, which content edits cannot move. No single keying satisfies both demands, which is why a single-signal scheme, whatever its keying, falls to one move or the other. A trajectory, however, has room for two watermarks: one on the identity of its decisions, one on their shape. Our approach. Trace superposes two watermarks on one trajectory, with independent keys, disjoint carriers, and, by design, disjoint vulnerable surfaces. It is, to our knowledge, the first agent watermark that is distortion-free in its action choices, self-synchronizing under deletion, and unconditionally invariant under rewriting. The selection channel modulates which action is selected, sampling the agent’s distribution through a distortion-free exponential race [Kuditipudi et al., 2023] keyed on preceding content. The sampled distribution provably equals the agent’s (Theorem 5.1), and content keying confines a deletion’s damage to one neighboring key, so detection resynchronizes (Proposition D.9). Zero distortion does not make detection free: each decision’s signal is lower- bounded by half its entropy and vanishes exactly at deterministic decisions, so short trajectories are pooled, at an explicit rate (Theorem 5.2, Corollary D.8). The tally channel modulates how many records each decision group contains, appending a context-neutral redundant record under a key derived from group position alone. Count and key are functions of the trajectory’s skeleton, which rewriting cannot touch, so the channel is unconditionally invariant under every rewriting attack (Theorem 5.3). Erasing both layers at once is provably expensive: the attack must edit the skeleton and, unless it targets groups by their realized scores, alter a constant fraction of group contents (Theorem 5.4). Both edits degrade the service the reseller is paid to deliver. Laundering the log means corrupting the product. Contributions. We make the following contributions: • We formalize attribution against the party that holds the evidence: a reseller with full read and write access to the trajectory log, whose two laundering moves induce the deletion and rewriting attack classes (Section 3). •We design Trace, which superposes a content-keyed selection channel and a position-keyed tally channel on one trajectory: to our knowledge the first agent watermark that is distortion-free, deletion-self-synchronizing, and rewrite-invariant at once (Section 4). •We back the design with guarantees proved structurally where prior agent watermarks measure robustness empirically: exact null laws for both detectors, an entropy lower bound that prices distortion-free detectability and yields the pooling rate, and a joint-erasure theorem charging any attack that silences both channels with skeleton edits and, when obliviously targeted, a constant fraction of altered groups (Section 5). •We introduce the LLM rewriter, to our knowledge the first informed, plausibility-preserving instance of the rewriting class, mounted by a language model that sees the genuine choice, and 3 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories we run it against every scheme in the comparison (Section 3.3). •We evaluate on ToolBench and ALFWorld against red–green and multi-bit baselines: Trace matches the unwatermarked agent’s success rate while the biased red–green watermark pays up to 8.1 points, attributes at 1% FPR under either single-axis attack where a single rewriting pass erases both baselines, and concedes essentially only the combined-attack corner, where the reseller has already destroyed the service it resells (Section 6). 2. Related Work Watermarking LLM text. Statistical watermarks bias or derandomize token sampling with a pseu- dorandom key. Kirchenbauer et al. [2023] boost the logits of a keyed green list, trading detection power against distortion, and Zhao et al. [2023] harden the partition with a fixed unigram key. Distortion-free and unbiased schemes remove the quality cost: Aaronson and Kirchner [2023] couples sampling to a keyed Gumbel trick, Kuditipudi et al. [2023] formalize distortion-free samplers with edit- robust detection, Hu et al. [2024] and Christ et al. [2024] construct unbiased and cryptographically undetectable variants, and Dathathri et al. [2024] deploy sampling-level watermarking at production scale. Multi-bit schemes carry identity payloads [Yoo et al., 2024]; BiMark [Feng et al., 2025] stacks several unbiased reweightings on each token, strengthening one signal on one carrier, whereas our two layers place two signals on disjoint carriers against two different attacks. A parallel line binds the signal to sentence-level semantics so that it survives paraphrase [Hou et al., 2024]; reliability studies and benchmarks map the quality versus robustness frontier [Kirchenbauer et al., 2024, Piet et al., 2025, Liu et al., 2024]. On the attack side, paraphrase removes token-level signals [Krishna et al., 2023], watermark stealing reverse-engineers the keyed rules from API access [Jovanović et al., 2024], Sadasivan et al. [2023] evade detectors through recursive paraphrasing, and Zhang et al. [2024] prove that a quality oracle and a perturbation oracle suffice to erase any strong watermark. These results shape our design rather than threaten it: the tally channel’s rewrite invariance is structural, not a statistical claim a stronger paraphraser could erode (Theorem 5.3), and for the selection channel we prove what an informed rewriter achieves (Proposition D.10). The selection channel transplants the exponential race of Kuditipudi et al. [2023] from tokens to behaviors, where the candidate set is the environment’s admissible action set; the conditional law and entropy bound we prove for its score (Lemma D.4, Theorem 5.2) appear to be new even in the token setting. Watermarking other generative modalities. Image watermarking has walked an arc from content- independent to content-bound signals, and then to the granularity of the binding. Regeneration attacks provably strip post-hoc invisible watermarks [Zhao et al., 2024], pushing the signal into the generation process itself; the resulting initial-noise schemes, Tree-Ring [Wen et al., 2023], Gaussian Shading [Yang et al., 2024], and pseudorandom codes [Gunn et al., 2025], are training-free but keyed independently of content, which black-box forgery exploits to transplant a watermark onto arbitrary images [Müller et al., 2025]. Responses anchor detection in the initial noise itself [Arabi et al., 2025a], root the signal in model weights or training data [Fernandez et al., 2023, Yu et al., 2021], or bind verification to image semantics [Arabi et al., 2025b]. The binding itself then became the target: LLM-guided semantic injection defeats a single global binding with edits that are locally substantial yet globally coherent [Gao et al., 2026a], and SLICE answers by anchoring distinct semantic factors to disjoint regions of the initial noise [Gao et al., 2026b]. Behavioral trajectories invite the same lesson in a different geometry: the selection channel binds the signal to trajectory content and the tally channel to trajectory structure, and the two bindings fail under complementary attacks by design. 4 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Watermarking agent behavior. Tool-using agents [Yao et al., 2022, Schick et al., 2023, Qin et al., 2024, Patil et al., 2024, Park et al., 2023, Shridhar et al., 2020] and the benchmarks that evaluate them as decision makers [Liu et al., 2023] expose a structured decision and observation loop that text watermarks do not exploit, and a young line of work embeds the signal there. Agent Guide [Huang et al., 2025] biases the behavior distribution toward a keyed subset, a red–green rule lifted to the decision level. AgentMark [Huang et al., 2026] removes the bias through distribution-preserving conditional sampling and carries a multi-bit identifier; it serves as a baseline in our experiments. AgentWM [Wang et al., 2026] targets model imitation, biasing selection among semantically equivalent tool paths so that the signal survives training on stolen outputs, and ActHook [Meng et al., 2026] watermarks trajectory datasets with keyed hook actions that a model trained on the data reproduces. Across this line the adversary perturbs, paraphrases, or distills, and the watermark is one signal under one keying. Trace differs on the axis these works leave open: the adversary who holds the log itself. We formalize a reseller with lawful write access and two laundering moves, and answer with a zero-bit, two-layer scheme carrying exact finite-sample null distributions, unconditional rewrite invariance, and a joint-erasure lower bound. The closest operational practice, log signing, proves integrity of a log one already trusts but cannot attribute an unsigned, possibly edited trajectory: a reseller relaying a rebranded log simply drops the provider’s signature. Behavioral watermarking therefore sits inside a broader provenance architecture, alongside trusted execution environments, attestation, and authenticated logs, as one complementary signal, the one that still speaks when the party holding those records is itself the adversary. Our threat model (Section 3.2) is built for exactly this case, letting the reseller edit everything except the environment-supplied action space and the executed action stream. 3. Problem Formulation and Threat Model This section fixes, in the order a security argument needs them, the object being watermarked (Section 3.1), the parties and their capabilities (Section 3.2), and the attack classes that every guarantee in this paper is stated against (Section 3.3). 3.1. Agent Trajectories An agent interacts with an environment through alternating decisions and observations; the log is modeled as a tagged sequence. Definition 3.1 (Agent trajectory). An agent trajectory is a finite sequence휏:=(푒 1 , . . . , 푒 푇 )of records, each carrying a role tag휌(푒 푡 ) ∈ dec, obsand a content string푐(푒 푡 ): dec records are decisions emitted by the agent, obs records are observations returned by the environment. The tag sequence 푠(휏) :=(휌(푒 1 ), . . . , 휌(푒 푇 )) is the skeleton of 휏. These records log emitted behavior, not the reasoning that produced it. A deployment may expose three artifacts: internal reasoning traces (increasingly hidden or encrypted), user-facing reasoning summaries (which may diverge from the underlying computation), and the agent trajectory just defined; Trace reads and marks only the third. Definition 3.2 (Decision-boundary grouping). The decision-boundary grouping of휏is the unique partition of휏into consecutive blocks푔 1 , . . . , 푔 푚 , each consisting of exactly one dec record followed by all obs records preceding the next dec record (or the end of휏); we write푘 푖 ≥0 for the number of obs records in 푔 푖 . The grouping reads no textual markers and no content heuristics, only the positions of dec tags; this gives it the invariance the design will lean on. 5 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Proposition 3.3 (Skeleton determines positions). If푠(휏)= 푠(휏 ′ ), then휏and휏 ′ have the same number of groups, the same group boundaries, and the same counts (푘 1 , . . . , 푘 푚 ). Definition 3.4 (Group attributes). For each group푔 푖 : (i)퐵 푖 is the candidate behavior set presented to the agent at decision푖by the environment (the available tools of a ToolBench task, the admissible commands of an ALFWorld step; terminal actions excluded), with푁 푖 :=|퐵 푖 |; (i)푃 푖 :퐵 푖 → [0,1]is the agent’s normalized distribution over퐵 푖 , elicited at decision time, with uniform fallback; (i)푏 푖 ∈ 퐵 푖 is the behavior actually selected; and (iv)퐴 푖 is the sequence of action identities recorded in푔 푖 . We writeH(푃 푖 )for the Shannon entropy of푃 푖 in nats. Group푔 푖 is effective if푁 푖 ≥2 and the selection is non-terminal, both predicates evaluated against the environment-supplied퐵 푖 and the executed action stream rather than any reseller-editable record content, so the set of effective groups is itself invariant under rewriting; only effective groups are pooled. Both layers draw randomness from one primitive, a deterministic random bit generatorDRBG(key, nonce) ∈ [0,1)instantiated with HMAC-SHA512 [Bellare et al., 1996, Barker and Kelsey, 2012]: embedder and detector recompute identical values from identical inputs, and no side information is ever transmit- ted. The analysis adopts the standard pseudorandom-function idealization [Goldreich et al., 1986]; independence holds only across distinct evaluation points, so pooled detection deduplicates groups whose evaluation points coincide. Assumption 3.5 (Ideal pseudorandomness). To any party not holding the key, the valuesDRBG(key, 휈) 휈 across distinct nonces휈are i.i.d. uniform on[0,1), independent of all other randomness; calls under independent keys are mutually independent. 3.2. Threat Model Provider (defender). Two parties interact through the resale of an agentic service (Figure 1): a provider, who develops and serves the agent, and a reseller, who licenses that agent and relays it to customers under a misrepresentation, as the reseller’s own in-house system or as a provider other than the one running underneath. The provider’s goal is a test that, given a trajectory, decides whether its agent produced it, at a false positive rate fixed in advance that no key-less party can inflate, and at no cost to the service itself, since a watermark that degrades task success will not be deployed; formally, the provider, or an auditor acting with its keys, tests퐻 0 (the trajectory was produced without knowledge of the keys) against퐻 1 (it was produced by the watermarked agent). Its capability is control of the sampler and the keys: it holds the secret(key 1 , key 2 )and embeds Trace at decision time (Section 4), so every trajectory its agent produces carries the watermark before leaving its control. Reseller (adversary). The reseller’s goal is to defeat attribution: a trajectory the provider’s agent in fact produced must not be attributable to the provider. Its defining capability is full access to the evidence: because it meters and bills usage, it stores and processes every trajectory and may read and edit the log at will before any copy reaches a verifier. Three limits bind it, and the design turns on all three. No keys: it does not hold(key 1 , key 2 ), so it cannot forge the watermark, only attempt to remove it. No re-execution: it resells the provider’s live service, so the executed action stream is genuine and its only lever is to edit the recorded log. Utility and consistency: the edited log must remain useful and consistent, since a service that no longer completes its customers’ tasks is worthless to resell, and the same logs substantiate the reseller’s charges, so they can be audited against the provider’s upstream record of consumption. 6 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 3.3. Attack Classes Within these limits, editing the log decomposes into two operations, which we formalize as the attack classes the analysis must withstand; their composition is the combined attack. Pruning the log, to shrink it or to strip records that name the provider, is deletion. Definition 3.6 (Deletion attack). A deletion attack drops records from the log. Because the reseller cannot re-execute (Section 3.2), the executed dec records are preserved; the attack removes obs records, lowering the counts푘 푖 of the affected groups (a group whose redundant record is dropped falls from푘 푖 =2 to푘 푖 =1) and, in the limit, reducing an affected group to its single preserved dec record (푘 푖 =0). The i.i.d. instance we sweep is parameterized by a rate푟 ∈ [0,1]: each obs record is deleted independently with probability푟. Targeted removal of provider-identifying or redundant records, truncation, and log loss are further instances. Rebranding the log, paraphrasing observation text and renaming actions into the reseller’s namespace, is rewriting. Definition 3.7 (Rewriting attack). A rewriting attack is any map푅on trajectories with푠(푅(휏))= 푠(휏): record contents (observation text and action identities alike) may be edited arbitrarily, but no record is inserted or deleted and no tag is changed. The LLM rewriter: a new informed attack. Definition 3.7 is a class; evaluating against it requires an instance, and prior work on behavioral watermarks tests only generic perturbations such as random substitution or paraphrase [Huang et al., 2025, 2026, Wang et al., 2026]. We introduce the LLM rewriter, an attack we define here, to our knowledge for the first time, that realizes the strongest rewrite a reseller can mount without the keys: an informed, plausibility-preserving edit executed by a language model (Figure 2). For each attacked group, an LLM receives the observation, the admissible action set, and the action the agent actually chose, and returns a different action that a reasonable agent could plausibly have taken; the recorded identity is replaced with its answer (exact prompt in Appendix C). The substitution is informed, since the model sees the genuine choice, which is exactly the regime Proposition D.10 characterizes for the selection channel; and it is plausibility-preserving, since an implausible replacement would betray the edit to any reader and violate the consistency constraint above. Applied to a fraction푞of groups, the LLM rewriter realizes Definition 3.7 at strength 푞and leaves the skeleton untouched by construction. Section 6 sweeps푞from 0 to 1 and runs this attack against every scheme under comparison, ours and the baselines alike. Figure 2|The LLM rewriter swaps the recorded action for a different plausible one, leaving the skeleton untouched. What the reseller cannot touch. Two things lie outside the rewriting class and beyond the reseller’s reach. The candi- date behavior set퐵 푖 is supplied by the environment, not the log, so the verifier reads it at audit time from fields the re- seller cannot edit rather than trusting it. And the executed action stream is what the provider actually ran on the reseller’s behalf: forging or deleting a dec record breaks the correspondence between the log and that stream, so attacks are required to act on the ex- ecution stream itself, the data every detector under comparison reads. The detector accordingly 7 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories LLM Agent candidate set Bᵢ watermarked trajectory τ observation redundant record gᵢ released log Reseller (no keys) EMBED: inject the mark at each decision group (provider holds key₁, key₂) (1) Selection Channel: content-keyed sampling, distortion-free (survives deletion) key₁ ctxᵢ = enc(Aᵢ₋₁) || key₁ r b = DRBG(H(ctxᵢ), b) for each b ∈ Bᵢ Pᵢ[b]r b r b 1/Pᵢ[b] 0.500.910.83 0.300.420.06 0.200.770.27 ← winner bᵢ bᵢ = argmax r b 1/Pᵢ[b] recorded as the decision; the agent’s own distribution is exactly preserved write bᵢ into trajectory (2) Tally Channel: skeleton-keyed counting, rewrite-invariant (survives rewriting) key₂ Gᵢ = 1 ifDRBG(H(key₂), H(qid||i)) < 1/2 else2 kᵢ = 1: decision + observation kᵢ = 2: redundant record: no tool call, log semantics & task success unchanged append into trajectory DETECT: replay both channels from the log Detector Replay Tally: checkkᵢ ∈ Gᵢ → count → z₂ keyed targets observed counts ✓ a clean log matches only half the time reject H₀ if min(p₁, p₂) ≤ α/2 ✓ TRACE: Two-Channel Watermark for LLM-Agent Trajectories decision observation decision observation decision ...... decision + observation + redundant record 2121 2121 Replay Selection: recomputer b atctxᵢ :φᵢ = −ln(1 − r b ᵢ) poolφᵢ → z₁ the winner’s r b skews high Figure 3|Overview of Trace: a content-keyed selection channel and a skeleton-keyed tally channel embed two complementary marks at each decision, read back by replaying both from the log. supports verification both from the reseller-released log and from the grouping reconstructed from execution, the latter trusting no reseller-editable field; large divergence between the two sources is itself evidence of tampering, a log/execution consistency audit to which Section 5 returns. 4. The Trace Scheme Fix independent keyskey 1 , key 2 . Trace consists of an embedder, which replaces the agent’s sampler at each decision and appends keyed redundant records, and a detector, which maps an observed trajectory to the statistics(푧 1 , 푧 2 )of(5)and(7); pseudocode for both is given as Algorithms 1 and 2 in Appendix C. One principle governs the construction: a statistic is invariant under an attack class as soon as its carrier and its keying are functions of data preserved by every attack in the class. A rewriting attack preserves exactly the skeleton (Proposition 3.3); a deletion attack preserves the contents of surviving groups and no positions; and no carrier–keying pair is preserved by both classes, content failing under rewriting and position under deletion. Trace therefore runs one layer on each invariant, both instances of the same template: keyed pseudorandomness evaluated on invariant data, coupled to one carrier, detected by replay (Figure 3). The selection channel modulates which action is selected, keyed on content; the tally channel modulates how many records each decision group contains, keyed on position. Subscript 1 refers throughout to the selection channel, 2 to the tally channel; Section 5 proves every property cited below. 8 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 4.1. The Selection Channel: Content-Keyed Sampling The carrier is the selected behavior 푏 푖 . The watermark context of group 푖 is ctx 푖 := enc(퐴 푖−1 )∥ key 1 , ctx 1 := bootstrap∥ key 1 ,(1) with enc an injective encoding of action-identity sequences, and each candidate receives the value 푟 푏 := DRBG key= 퐻(ctx 푖 ), nonce= 푏 ∈ (0, 1), 푏∈ 퐵 푖 .(2) Position is deliberately absent from(1): under deletion at rate푟, the contextctx 푖 is unchanged for every group whose predecessor retains all its records, so only the immediate successors of groups that lost a record evaluate the primitive at fresh points (blast radius one) and the detector re-aligns at the next group, whereas a single position in the keying path would desynchronize every group from the first dropped record onward. The window has memory one because a longer window, while equally admissible, widens the damage of each deletion from one group to the window length (Remark E.1, Appendix E). We realize the selection rule as a keyed exponential race over the candidate set, 푏 푖 := argmin 푏∈퐵 푖 − ln푟 푏 푃 푖 [푏] = argmax 푏∈퐵 푖 푟 1/푃 푖 [푏] 푏 ,(3) implemented in logarithmic form: every admissible behavior runs against its own keyed clock, and the agent plays the winner. By Theorem 5.1 the race reproduces the agent’s distribution exactly, Pr[ 푏 푖 = 푏]= 푃 푖 [푏]for every푏 ∈ 퐵 푖 , so utility is settled by construction. The winner’s value푟 푏 푖 is stochastically above uniform precisely because it won; this residue is the watermark. The detector replays(1)and(2)on the observed trajectory, trusting no self-reported value, and scores each effective group by 휑 푖 :=−ln 1− 푟 푏 푖 ,(4) so that휑 푖 ∼ Exp(1)exactly when푟 푏 푖 is an unwatermarked uniform. Pooled over the푛effective groups, deduplicated so that no two share an evaluation point (Assumption 3.5), 푋 1 := 푛 ∑︁ 푖=1 휑 푖 , 푧 1 := 푋 1 − 푛 √ 푛 ,(5) with exact푝-value푄(푛, 푋 1 ), the upper Gamma tail. Section 5 and Appendix D supply the quantitative content:푋 1 ∼ Gamma(푛,1)under퐻 0 (Lemma D.2);피[휑 푖 ] ≥1+ 1 2 H(푃 푖 )under퐻 1 (Theorem 5.2); and under deletion at rate푟every score generically stays at or above the null while at least a(1− 푟) 2 fraction of the entropy signal survives, so the expected selection푧stays positive for every푟 <1 (Proposition D.9). Against rewriting the layer claims nothing: the carrier itself is overwritten, and replacing푏 푖 by a race loser never raises피[휑 푖 ]above 1, driving it strictly below whenever the substitute carries positive probability (Proposition D.10). Covering this gap is the purpose of the tally channel. 4.2. The Tally Channel: Skeleton-Keyed Counting Rewriting fixes the skeleton, hence the group count푚and the counts(푘 1 , . . . , 푘 푚 )(Proposition 3.3); the tally channel reads nothing else. The carrier is푘 푖 ∈ 1,2, a zero-bit keyed pattern, and the keying is a function of (key 2 , qid, 푖) alone: 휌 푖 := DRBG key= 퐻(key 2 ), nonce= 퐻(qid∥ 푖) , 퐺 푖 := ( 1, 휌 푖 < 1 2 , 2, 휌 푖 ≥ 1 2 , (6) 9 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories withqidthe task-instance identifier. Position, fatal in the selection channel, is admissible here because rewriting cannot move it; an earlier design keyed the target on퐴 푖−1 , and identity substitution then desynchronized the recomputed targets from the embedded ones, destroying the channel. The embedder realizes the target by 푘 푖 = 1 + 1 퐺 푖 =2 · 1 augmentation admissible for 푔 푖 , appending, when both indicators equal 1, one redundant record of the following kind after the group’s primary observation, a record that disturbs neither the semantic content of the log nor the task’s execution; admissibility means that the environment’s logging format permits such a record. Definition 4.1 (Context-neutral redundant record). Let휋be the trajectory prefix up to and including the primary observation of group푔 푖 . A record ̃푒appended to푔 푖 is context-neutral if (i)푐( ̃푒)= 푓(휋)for a fixed deterministic function푓, so that ̃푒is informationally redundant with the prefix and the agent’s effective context is unchanged; (i) producing ̃푒invokes no tool and incurs no environment side effect; and (i) 휌( ̃푒)= obs, with no leading dec record. Conditions (i) and (i) are the utility guarantee:푐( ̃푒)is a deterministic function of a prefix the agent already possesses, so no decision-relevant information changes downstream, and no tool is re-executed (real agent tools are frequently side-effectful APIs). The layer’s resistance to forging or erasing the tally signal rests on condition (i) alone (Remark 4.2), while its invariance under rewriting is a separate guarantee, carried by the skeleton keying (Theorem 5.3). Remark 4.2 (Why no leading decision). A genuine extra tool call is necessarily headed by its own dec record and therefore opens a new group of count 1 under Definition 3.2; the watermark’s redundant record, having no leading decision, folds into the current group and raises its count to 2. The tally channel’s signal is thus precisely “a record with no decision at its head.” To forge or erase it the reseller must insert or delete a dec record, an operation outside the rewriting class of Definition 3.7, and one that desynchronizes the log from the executed action stream. The detector replays(6)on the observed skeleton, trusting no self-reported field, and counts hits over the푛pooled groups, whose index set is determined by the skeleton and the environment-evaluated effectiveness of Definition 3.4 and is therefore itself untouched by rewriting, 푋 2 := 푛 ∑︁ 푖=1 1 푘 푖 ∈ 퐺 푖 , 푧 2 := 푋 2 − 푛푝 0 √︁ 푛 푝 0 (1− 푝 0 ) ,(7) with exact Binomial푝-value; here푝 0 = 1 2 for every baseline whose group counts satisfy푘 푖 ≡1 (Appendix E treats the general case). For a baseline whose groups carry a single observation absent augmentation, the watermarked agent with admissible augmentation attains푋 2 = 푛, that is,푧 2 = √ 푛, deterministically. The statistic푋 2 is invariant under every rewriting attack (Theorem 5.3), and Pr 퐻 0 [푋 2 = 푛]=2 −푛 when every pooled group carries one or two records, conservatively less otherwise (Lemma D.3). 4.3. The Composed Scheme The coupling between the layers is one-way: when푘 푖 =2 the augmented sequence퐴 푖 , the chosen action followed by the redundant record’s identity, enters the selection channel’s window at group 푖+1, but the tally channel reads no content, so the coupling graph is acyclic, a single edge from the tally channel into the selection channel. Consequently the exact푝-values푝 1 and푝 2 are independent 10 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories under퐻 0 (Proposition D.13), and the detector rejects whenmin(푝 1 , 푝 2 ) ≤ 훼/2, which bounds the false positive rate by훼. Whether the selection channel’s window includes redundant records is a design knob that trades a sliver of deletion exposure against decoupling; our experiments use the coupled default (Remark E.1, Appendix E). 5. Theoretical Analysis This section states the four theorems that carry the paper’s claims and reads each one against the experiments of Section 6; false-positive control, exact at every sample size, needs no theorem of its own (Section 5.2). The supporting lemmas and propositions, together with all proofs, are deferred to Appendix D, and every distributional claim was additionally verified by Monte Carlo simulation (Appendix E). Appendix A collects the notation, and Appendix B maps the dependency structure of every result below. 5.1. Utility Preservation Theorem 5.1 (Distortion-freeness). Under Assumption 3.5, the rule(3)satisfiesPr[ 푏 푖 = 푏]= 푃 푖 [푏] for every 푏∈ 퐵 푖 . Takeaway. The watermark is invisible in distribution at every decision: the keyed race plays exactly the agent’s own action distribution, not an approximation of it, so the threat model’s deployment constraint is met by construction rather than by tuning. The proof, via the race lemma (Lemma D.1, Appendix D.1), is the exponential-clocks form of the Gumbel-max trick [Maddison et al., 2014]. Table 2 is the theorem made visible: Trace sits within seed noise of Base on every benchmark, while the biased red–green watermark pays 8.1 points on ALFWorld ID, the price of moving probability mass at low-entropy decisions that a distortion-free sampler never moves. The tally channel’s utility guarantee is definitional rather than distributional: by Definition 4.1(i)–(i) the appended record is a deterministic function of context the agent already possesses, invokes no tool, and incurs no side effect, so it changes no decision-relevant information downstream. 5.2. Exact False-Positive Control Both detectors are exactly calibrated at every sample size, with no asymptotics and no assumption beyond Assumption 3.5. Under퐻 0 the selection scores are i.i.d.Exp(1), so푋 1 ∼ Gamma(푛,1)and its푝-value is the upper Gamma tail푄(푛, 푋 1 )at every푛(Lemma D.2); the tally hits are fair coins, so 푋 2 ∼ Bin(푛, 1 2 ), exactly so when every pooled group carries one or two records and conservatively otherwise, and a perfect hit count has probability exactly 2 −푛 (Lemma D.3). The numbers compound fast: a watermarked agent forces every admissible tally hit, so 30 effective groups already certify provenance at a false positive rate of 2 −30 ≈10 −9 . Forcing every hit also pins the alternative at푧 2 = √ 푛by(7), the pooling rule visible in Table 6, where the푛=50 split’s tally푧scales over the푛=20 splits close to the predicted ratio (1.45 against √ 2.5 ≈1.58), and Trace’s wrong-key controls in Table 3 are this null observed empirically: the tally controls sit within noise of zero, and the selection controls sit systematically below it, a direction that cannot inflate a one-sided false positive rate. Rejecting whenmin(푝 1 , 푝 2 ) ≤ 훼/2 bounds the combined false positive 11 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories rate by훼via the union bound; the two channels’ exact푝-values are moreover independent under퐻 0 (Proposition D.13), which licenses sharper combinations. 5.3. The Entropy–Detectability Trade-off Under퐻 1 the sampler(3)prefers candidates with large푟 푏 , so the replayed score sits stochastically above the null; conditional on the winner푏it follows a generalized exponential law with mean 휓(1/푝 푏 +1)+ 훾, where휓is the digamma function and훾the Euler–Mascheroni constant (Lemma D.4; Corollaries D.5 and D.6 give its uniform and deterministic extremes). Averaging that closed form yields the bound the channel turns on (proof in Appendix D.4); to our knowledge it is new. Theorem 5.2 (Entropy lower bound on the signal). For every distribution 푃 푖 , 피[휑 푖 ] ≥ 1+ 1 2 H(푃 푖 ), with equality if and only if 푃 푖 is a point mass. Takeaway. Detection is paid for in entropy: every decision yields signal worth at least half its entropy, and a deterministic decision yields none, so a distortion-free watermark must pool short or low-entropy trajectories rather than bias them. The limit is broader than Trace: a deterministic decision admits no keyed variation under any distortion-free rule, so we read the entropy price as intrinsic to distortion-free behavioral watermarking, and the theorem as one sharp instance of it. The trade-off is visible in the experiments. The detector pools groups across trajectories at the explicit sample-complexity rate of Corollary D.8, and the two benchmarks separate just as the bound’sH/2 per-group rate predicts (Table 3): ToolBench’s roughly 1.4 effective groups per task yield selection푧 ≈4.5 per split, while ALFWorld’s 23 to 25 decision steps accumulate the same guaranteed per-group drift into푧between 94 and 103. The red–green watermark buys its signal with probability mass instead and trails Trace by 9.3 success-rate points on ALFWorld ID (Table 2); Trace pays only in randomness the agent already spends. 5.4. Robustness under the Threat Model Table 1 is the design in one view: each layer’s soft spot is the other’s strength. Deletion: blast radius one. Deletion drops observation records, so it lowers the counts푘 푖 the tally reads and corrupts that channel directly. The selection channel is content-keyed: its carrier is the preserved decision푏 푖 , so deletion cannot substitute a race loser and every score stays at or above the null, never below it save a rare context coincidence (the loser drift of rewriting is impossible here). Only the keying context can desynchronize, and the memory-one window(1)confines each dropped record’s damage to a single neighboring group, so at least a(1− 푟) 2 fraction of the entropy signal survives at rate푟and the selection channel’s expected score stays positive for every푟 <1 (Proposition D.9, Appendix D.6). This is the formal sense in which the selection channel is self- synchronizing, and it is what Figure 5(a) shows: selection푧falls from 11.34 to 4.06 at 70% deletion yet still clears the threshold, while the count-keyed tally crosses it. Rewriting: the selection channel inverts; the tally channel does not move. Against rewriting the selection channel claims nothing, and its failure is sharper than erasure. Every identity the LLM 12 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories rewriter substitutes is, by construction, a candidate that lost the keyed race, so the replayed score never rises above the null and falls strictly below even an unwatermarked log’s whenever the substitute carried positive probability under the agent’s distribution (Proposition D.10, Appendix D.7). That is the below-null drift of Figure 5(b), where selection푧crosses zero near푞≈0.5 and ends at−3.51, and it is why no amount of extra pooling rescues a content-keyed channel against a rewriting reseller: pooling amplifies negative drift. A second, rewrite-invariant channel is a necessity, not a preference, and its guarantee is unconditional. Theorem 5.3 (Rewrite invariance of the tally). For every rewriting attack푅(Definition 3.7) and every trajectory 휏: 푋 2 (푅(휏))= 푋 2 (휏), hence 푧 2 (푅(휏))= 푧 2 (휏). Takeaway. Rewrite robustness here is an identity, not a bound: no rewriting attack of any strength moves the tally statistic by a single bit, because both its carrier and its key live in the skeleton that rewriting, by definition, cannot touch. The invariance is exactly as wide as Definition 3.7: semantic rebranding (paraphrase and renaming in place) is covered, since it preserves the tag sequence, whereas transformations that alter that sequence, by inserting or deleting records, leave the class and are met by Theorem 5.4(a) and the log/execution consistency audit. The experiments realize the identity to the digit: the tally푧stays pinned at 14.34 for every rewriting strength푞in Figure 5(b), with zero variation within each seed, while both single-signal baselines collapse on the same axis. Against a reseller who owns the log, an invariant the editor cannot move is the one guarantee no rewriting effort can buy down. The headline claim is then that erasing both layers at once is qualitatively more expensive than erasing either. Theorem 5.4 (Cost of joint erasure). Let휏be watermarked with푚effective single primary- observation groups (푘 푖 =1 absent augmentation) and admissible augmentation throughout, each group withH(푃 푖 ) ≥ ℎ > 0, and let 퐴 be any attack producing 휏 ′ . (a) If퐴is skeleton-preserving, then푧 2 (휏 ′ )= 푧 2 (휏)= √ 푚: the tally channel is untouched. Hence any attack with피[푧 2 (휏 ′ )] < √ 푚edits the skeleton, deleting or inserting records, and is exposed to the log/execution consistency audit. (b)If퐴corrupts the selection-channel evaluation point (its context or its selected identity) of at most푎groups, whether by deleting records that feed a group’s context or by altering a selected identity, and chooses the corrupted set obliviously, that is, independently of the realized selection-channel values (the substitution within a corrupted group may still be informed), then, since the preserved decisions keep all 푚 groups, 피 푧 1 (휏 ′ ) ≥ (푚− 푎) 1+ ℎ 2 − 푚 √ 푚 . Consequently, for any threshold 휃≥ 0,피[푧 1 (휏 ′ )] ≤ 휃 forces 푎 ≥ ℎ 2+ ℎ 푚 − 휃 √ 푚 : the reseller must corrupt a constant fraction of the trajectory. 13 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 1|Orthogonal vulnerable surfaces: each channel is robust precisely where the other breaks, with the cited results carrying the guarantees. AttackSelection channel (carrier 푏 푖 )Tally channel (carrier 푘 푖 ) Deletion / dropped observations robust: blast radius 1 (Prop. D.9) broken (counts fall) Rewriting / LLM rewriterbroken (Prop. D.10)invariant (Thm. 5.3) Combined (delete+ rewrite)cost bounded below by Theorem 5.4 Takeaway. There is no cheap way to erase both channels: silencing the tally channel means editing the skeleton and facing the consistency audit, and silencing the selection channel means that any attack not targeting groups by their realized scores must corrupt a constant fraction of the very actions the resold service depends on. Laundering the log means corrupting the product. This is why only the joint high-deletion, high-substitution corner of Figure 6 suppresses both detectors, and why neither cost can be avoided by attacking only the released log, since detection reads the grouping reconstructed from execution (Section 3.2). The oblivious-set hypothesis in (b) is necessary rather than technical, since an attacker that targets groups by their realized scores can do better, and the score-adaptive rate is open (Remark D.12, Appendix D.8); the LLM rewriter of Section 6 attacks a random fraction of groups and so falls inside the covered regime. 6. Experiments We evaluate the three claims the theory makes: distortion-freeness costs no utility (Section 6.2), detection is calibrated and attributes the agent at deployment-relevant evidence sizes (Section 6.3), and the two channels fail only together, under exactly the attacks the threat model names (Section 6.4). 6.1. Experimental Setup Schemes. Four arms run on every benchmark. Base is the unwatermarked agent. AM-F is Agent- Mark [Huang et al., 2026], the closest existing agent watermark: distribution-preserving multi-bit embedding whose payload is recovered through random linear network coding (RLNC). RG is the red–green watermark of Kirchenbauer et al. [2023] lifted from tokens to behaviors, biasing selection toward a keyed green subset of퐵 푖 (훾=0.5,훿=2.0) under the same content window as Trace’s selection channel; it represents the canonical biased, single-signal design point. Trace is the scheme of Section 4, its keys expanded through SHA-256 into the material driving the HMAC-SHA512 DRBG. Data. ToolBench [Qin et al., 2024] evaluates tool-use decision making over a large corpus of real- world APIs. We use its six test splits, T1 to T6, spanning the single-tool, intra-category multi-tool, and intra-collection multi-tool regimes under held-out instructions, tools, and categories (푛=20 per seed and split, except T5 with푛=50); its trajectories are short, roughly 1.4 effective decision groups per task. ALFWorld [Shridhar et al., 2020] evaluates embodied household planning in interactive text environments. Its six task families, A1 to A6, ask the agent to find, process, and place objects: simple pick-and-place, cleaning, heating, or cooling an item before putting it away, examining an object under a lamp, and placing two objects; trajectories are long, 23 to 25 decision steps. We use ALFWorld’s in-distribution validation split (ID, 140 tasks) and its out-of-distribution split of unseen environments (OOD, 134 tasks). Task subsets are fixed and shared across arms and seeds, all results 14 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 2|Main results on the principal backbone: per-task success rate and steps, mean±std over three seeds (Avg. rows푛-weighted with deltas vs. Base; green: no degradation beyond seed noise, red: clear drop;†: no pooled std; Trace steps include the tally channel’s redundant records). SettingTask SR (%)↑Steps / task BaseAM-FRGTraceBaseAM-FRGTrace A191.4±2.993.3±4.489.5±1.691.4±2.918.1±2.317.9±1.617.8±0.924.7±2.7 A285.2±3.784.0±4.381.5±7.488.9±7.424.3±3.223.5±1.626.8±3.230.1±5.4 A381.2±12.589.6±3.675.0±6.293.8±6.225.1±3.123.9±3.730.6±0.937.8±2.7 A476.0±4.080.0±4.057.3±8.377.3±4.627.3±3.324.6±1.733.6±2.740.7±3.3 A587.2±4.492.3±7.782.1±4.494.9±8.919.6±0.817.7±5.121.6±2.818.9±4.2 A670.8±0.066.7±7.256.9±9.659.7±8.735.9±1.032.7±1.837.6±0.951.7±2.2 ALFWorld ID Avg.82.4±2.184.0±3.0(↑ 1.6)74.3±2.9(↓ 8.1)83.6±2.6(↑ 1.2)24.9 † 23.4 † (↓ 1.5) 27.6 † (↑ 2.7) 34.2±2.6(↑ 9.3) A190.3±4.898.6±2.480.6±2.490.3±6.421.6±3.215.2±0.423.9±2.629.6±2.4 A287.1±5.684.9±4.982.8±4.978.5±8.120.7±2.423.1±1.022.9±3.138.9±4.3 A385.5±2.591.3±4.376.8±6.676.8±5.024.1±4.121.9±2.930.7±0.341.9±3.2 A490.5±0.088.9±2.787.3±5.590.5±8.221.7±0.919.8±1.520.3±4.327.9±3.5 A588.9±5.683.3±5.683.3±0.092.6±3.223.0±1.219.0±1.523.9±1.627.9±4.9 A633.3±9.045.1±12.251.0±6.854.9±14.843.1±0.842.4±0.940.0±0.655.6±6.6 ALFWorld OOD Avg.81.3±2.283.8±2.2(↑ 2.5)78.1±4.1(↓ 3.2)81.1±4.2(↓ 0.2)24.8 † 22.9 † (↓ 1.9) 26.3 † (↑ 1.5) 36.7±2.1(↑ 11.9) T172.5±10.983.3±2.978.3±2.981.7±2.92.18±0.331.97±0.131.98±0.081.80±0.22 T285.0±5.086.7±5.878.3±12.686.7±7.62.17±0.132.00±0.222.10±0.131.93±0.13 T378.3±7.675.0±0.076.7±10.483.3±5.82.17±0.132.07±0.102.33±0.242.37±0.34 T491.7±7.690.0±0.088.3±2.990.0±10.02.38±0.252.28±0.192.17±0.032.40±0.66 T569.3±5.073.3±1.275.3±3.165.7±5.92.12±0.222.01±0.162.07±0.201.81±0.05 T678.3±2.973.3±2.971.7±2.968.3±11.52.27±0.121.97±0.082.02±0.162.35±0.90 ToolBench Avg.77.2±1.878.9±0.4(↑ 1.7)77.6±3.4(↑ 0.4)76.6±2.2(↓ 0.6)2.20±0.10 2.04±0.05(↓ 0.16) 2.10±0.08(↓ 0.10) 2.05±0.16(↓ 0.15) are mean±sample standard deviation over three seeds, and the label-to-split mapping is tabulated in Table 5 (Appendix F). The backbone is GPT-5.4-mini, served through an API relay; an ALFWorld ablation on a second, locally deployed Qwen backbone is in Appendix F.4 (Tables 9 and 10). Metrics. 1) Utility: success rate (SR), scored by one LLM judge (GPT-5.4-mini, identical across arms; solved 1, unsure 0.5, unsolved 0), and steps per task; Trace step counts include the tally channel’s redundant records, so they measure the full logged overhead. 2) Detection: the pooled per-channel푧of Section 4, thresholded at휃=2 and combined across channels bymax(푧 1 , 푧 2 ), the normal-approximation counterpart of Algorithm 2’s exact rule; wrong-key controls (wk) rerun each detector under an independent key never used at embedding, estimating the empirical null. Because the threat model fixes the verifier’s false positive rate in advance, we also report TPR at calibrated FPR: positives are watermarked trajectories scored under the true key, negatives the same trajectories under the wrong key; bundles of퐵trajectories are pooled into one statistic, and TPR@푥%FPR is the fraction of positive bundles above the(1−푥%)quantile of the negative bundles (5000 bootstrap resamples). Under attack, each attack cell already pools 118 to 127 trajectories into one 푧, so a cell is one fixed-size bundle and TPR@1%FPR is the fraction of cells above the one-sided Gaussian 1% threshold 2.326, calibrated by the wrong-key per-cell null. Together these measure what a verifier holding the evidence can attribute at its chosen FPR (protocol details in Appendix F.6). AM-F is additionally scored on its native metric, verified channel bits per task. Attacks. The two classes of Section 3.3, applied to every arm: random observation deletion at rate 푟(five trials per seed), our LLM rewriter at strength푞(three trials per seed), and their composition, rewriting at strength푞followed by deletion at rate푟, over a 3×6 grid of(푟, 푞)with nine runs per cell; the detection threshold is 휃= 2 throughout. 15 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 3|Detection on the principal backbone: pooled푧per channel with wrong-key (wk) controls and AM-F capacity in verified channel bits (‡: mean over the six per-split statistics of Table 6). Setting RGTraceAM-F 푧↑wkSel. 푧↑Tally 푧↑wk sel.wk tallybits/task↑ ToolBench2.72 ‡ −0.88 ‡ 4.51 ‡ 5.77 ‡ −0.16 ‡ 0.43 ‡ 1.68±0.06 ALFWorld ID37.37±0.58 −0.04±1.2994.15±6.1654.38±2.22−4.53±1.62 1.06±0.4853.85±1.30 ALFWorld OOD34.48±1.31 1.99±0.55102.53±6.1655.32±1.74−2.43±0.67 0.73±0.2949.34±2.21 11050 bundle size B (trajectories pooled) 0.0 0.2 0.4 0.6 0.8 1.0 TPR @ 1 % FPR Trace selection Trace tally RG AM-F Figure 4|TPR at 1% FPR on ToolBench against the wrong-key null, as a function of the number of pooled trajectories 퐵 (ALFWorld and per-FPR breakdowns in Appendix F.6). 6.2. Task Utility under Watermarking Table 2 is the empirical face of Theorem 5.1. On ToolBench every arm sits within about two points of Base in aggregate, where Trace’s weighted success rate is indistinguishable from Base at seed noise; the wider per-split swings (most visibly T5 and T6) sit within the larger seed variance on those splits. On ALFWorld Trace matches Base in aggregate on both splits (+1.2 p ID,−0.2 p OOD, within seed noise), while the biased RG pays 8.1 points ID and 3.2 OOD; the per-type rows locate the damage where low-entropy decisions concentrate, most visibly A4 ID. AM-F, also distribution-preserving, stays at Base level, confirming that what RG pays for is the bias itself. Trace’s step counts include the tally channel’s redundant records, reported on the same all-episode denominator as every other arm, and decomposing them shows where the gap to Base lives: the redundant records contribute 11.0 (ID) and 11.9 (OOD) entries per task, while the decision path itself runs 23.2 and 24.8 steps against Base’s 24.9 and 24.8, at parity. The entire overhead is watermark records that by Definition 4.1 invoke no tool and incur no environment side effect, log lines rather than agent work; on ToolBench the same accounting adds about 0.7 redundant records on top of 1.4 decision groups per task. The full accounting, per split and per backbone, is tabulated in Table 8 (Appendix F.3). Distortion-freeness is free in practice: Trace tracks the unwatermarked agent within seed noise on every benchmark, while the biased watermark pays its utility tax exactly where decisions are low-entropy. 6.3. Detection Power and Evidence Requirements Table 3 reports pooled detection, and Trace’s wrong-key controls behave as Section 5.2 demands: the tally controls sit within noise of zero, and the selection controls sit systematically below it, the harmless 16 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 0.00.10.20.30.40.50.60.7 deletion rate r −5 0 5 10 15 detection z τ (a) Deletion 0.00.20.40.60.81.0 rewriting strength q −5 0 5 10 15 τ exactly invariant (Thm. 5.3) (b) LLM rewriter Trace selectionTrace tallyRGAM-F Figure 5|Detection푧on ToolBench under (a) observation deletion at rate푟and (b) our LLM rewriter at strength 푞 (shaded: below the threshold 휃= 2). 0.00.20.40.60.81.0 rewriting strength q 0.3 0.5 0.7 deletion rate r 8.46.54.3-0.9-2.5-2.6 6.04.83.2-1.1-1.9-2.1 4.63.63.1-0.9-1.2-1.6 (a) Selection channel z 1 0.00.20.40.60.81.0 rewriting strength q 0.3 0.5 0.7 5.25.95.95.45.75.0 2.11.72.02.41.82.1 -0.5-0.30.2-0.8-0.1-0.3 (b) Tally channel z 2 0.00.20.40.60.81.0 rewriting strength q 0.3 0.5 0.7 8.46.55.95.45.75.0 6.04.83.22.41.82.1 4.63.63.1-0.8-0.1-0.3 (c) Stronger channel max(z 1 , z 2 ) -3.5 0 τ= 2 5 9 Figure 6|Combined attack on Trace (ToolBench): per-channel detection푧and, in panel (c), the stronger channel, over deletion rate 푟 and rewriting strength 푞, with colors diverging at 휃= 2. side of a one-sided test. The two benchmarks separate exactly along Theorem 5.2: ToolBench’s 1.4 effective groups per task yield single-digit per-split푧, while ALFWorld’s long horizons push the selection channel to푧between 94 and 103 and the tally into the fifties (Table 3; per-seed values in Table 7), well above RG. AM-F’s verified channel bits follow the same horizons, 1.68 per ToolBench task against 49 to 54 on ALFWorld: capacity, like our signal, is bought with decision entropy. Figure 4 asks the question a verifier actually faces: how many trajectories buy attribution at a fixed false positive rate? On ToolBench a single trajectory is not enough for any behavioral watermark: its trajectories are simply too short, and 1.4 effective decisions carry too little entropy, the price Theorem 5.2 fixes for every scheme that leaves the agent’s distribution intact. Trace converts evidence into attribution as fast as anything we tested. On the long-horizon ALFWorld a single trajectory already attributes most of the time, TPR@1%FPR reaching 0.87 to 0.94 for the selection channel and 0.85 to 0.86 for the tally (full tables in Appendix F.6, Tables 14 and 15); on ToolBench, ten pooled trajectories take the tally channel to TPR 1.000, volume the resale setting supplies by definition. AM-F’s clean detection keeps pace at퐵=10, but it buys that power with a payload design that Section 6.4 shows collapsing under a single rewriting pass, while the tally channel does not move. A single long-horizon trajectory, or ten short ones, attributes Trace’s agent at 1% FPR, and Trace alone keeps this power under every single-axis attack that follows. 17 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 6.4. Robustness under Deletion, Rewriting, and Combined Attacks The reseller of Section 3.2 launders the log with two moves, pruning and rebranding, and its goal is to push detection below휃while keeping the log sellable. Table 1 predicts exactly how this plays out: each attack class breaks one of Trace’s channels by design and cannot touch the other, whereas every baseline carries a single signal and therefore owns a single fatal axis. This subsection tests that prediction move by move. Deletion (Figure 5a). Dropping observations lowers the counts푘 푖 the tally reads, so the count- keyed tally channel must fail, and it does, crossing휃near푟 ≈0.5. The question deletion actually poses is whether anything survives it, and the selection channel does: its carrier is the preserved decision, so deletion can only desynchronize the keying context, and the memory-one window confines each dropped record’s damage to a single neighboring group (Proposition D.9), so the detector resynchronizes after every cut, and푧decays gracefully from 11.34 to 4.06 at 70% deletion, still above threshold, with TPR@1%FPR never below 0.93 at any tested rate (Table 16). To even reach that point, the reseller has already discarded seventy percent of the service it bills for. The baselines also weather this axis: RG, content-keyed like our selection channel but with a weaker per-group signal, decays from 7.09 to 2.80; AM-F rides its RLNC erasure coding to푧=8.67 at bit accuracy 1.00 (full sweep in Table 11). Deletion alone launders nothing. Rewriting (Figure 5b). Rebranding, renaming actions into the reseller’s own namespace, is the move a reseller mounts as a matter of course, and our LLM rewriter is its strongest informed instance. It erases every content-keyed signal in the comparison: RG falls from 7.09 to 0.29, AM-F from 15.85 to−4.04 with bit accuracy 0.34, and both baselines’ TPR collapses from 1.000 to 0.000 by푞=0.8 (full sweep in Table 12). The schemes that kept pace with Trace on clean logs are erased by a single rewriting pass. Trace’s own selection channel fails on this axis too, by design, and even inverts: every substituted identity is a race loser, so the replayed score sinks below the null, crossing zero near 푞≈0.5 and ending at−3.51, the drift Proposition D.10 predicts. The tally channel, whose carrier and key live in the skeleton the rewriter cannot touch by definition, does not move at all:푧=14.34 at every strength, with zero variation across strengths within every seed, TPR 1.000 throughout, Theorem 5.3 realized to the digit. This is the gap between empirical robustness and structural invariance: no rewriting budget, however large, buys the reseller anything against the tally. Combined attack (Figure 6). The only move left is to delete and rewrite at once. Panels (a) and (b) confirm that the two channels fail orthogonally,푞draining the selection channel and푟the tally, nearly independently of one another. Panel (c) shows what the combined detector sees, the stronger of the two channels, and it stays above휃everywhere except the corner푟=0.7 with푞≥0.6 (plus the marginal cell(0.5,0.8)at푧=1.81), exactly the regime Theorem 5.4 prices. Reaching that corner means rewriting most of the steps and deleting 70% of the result: a log that no longer resembles the service the reseller bills for, carrying the skeleton edits the log/execution consistency audit flags. The RG and AM-F grids (Table 13; TPR versions in Table 17) need no corner: each is already erased by one axis alone. Every single-signal scheme has a fatal axis; Trace has none: under either single-axis attack one channel keeps attributing at 1% FPR, and silencing both costs the reseller the very product it resells. 18 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories 7. Conclusion We introduced Trace, a two-layer behavioral watermark for LLM agents in which a distortion-free, content-keyed selection channel (robust to deletion, blast radius one) and a position-keyed tally channel (unconditionally invariant to rewriting) are superposed on one trajectory with independent keys and one-way coupling. Against an adversary holding the evidence, attribution should decompose across complementary invariants, each keyed to data one attack class must preserve, a principle we conjecture extends beyond watermarking. The analysis gives exact null distributions for both detectors, a closed-form conditional law for the selection score, an entropy lower bound that makes the trade-off between utility and detectability of distortion-free agent watermarking precise, and a joint-erasure theorem showing that suppressing both layers forces skeleton edits and, for obliviously targeted attacks, constant-fraction deletion or alteration simultaneously. Experiments on ToolBench and ALFWorld bear the predictions out, including the exact invariance of the tally channel under substitution and the below-null drift of the selection channel under informed rewriting. Limitations and directions: detection requires the verifier to access the candidate sets, which assumes the environment’s action space is available at audit time; the two channels buy their robustness at complementary prices, the selection channel paying in entropy, its power degrading on near-deterministic agents exactly as Theorem 5.2 predicts with pooling requirements growing accordingly, and the tally channel paying in log volume, its redundant records adding eleven to twelve entries per ALFWorld task, an overhead in storage and audit length rather than in tool calls or task success, since the decision path stays at parity with the unwatermarked agent (Section 6.2); and our guarantees concern removal, so a reseller that abandons the provider’s agent entirely and re-runs the task on a different model produces a genuinely unwatermarked trajectory, whose missing mark flags the misrepresentation but does not by itself name the substitute. Extending the tally channel beyond1,2, watermarking multi-agent interaction patterns, and treating watermark removal as the attacker’s joint optimization of attribution score, task utility, and stealth are natural next steps. Impact statement. This work targets accountability infrastructure for autonomous agents, specifi- cally the resale setting in which a middleman controls the logs. Watermarks of this kind can deter the misattribution of agent behavior and support audit trails; conversely, any provenance tool can in principle be used to track benign users of an agent system. Our scheme watermarks the provider’s own trajectories with the provider’s keys and reveals nothing about third parties; we believe the accountability benefits outweigh the risks. References Scott Aaronson and H Kirchner. Watermarking of large language models. In Large language models and transformers workshop at Simons Institute for the Theory of Computing, volume 2023, 2023. Kasra Arabi, Benjamin Feuer, R Teal Witter, Chinmay Hegde, and Niv Cohen. Hidden in the noise: Two-stage robust watermarking for images. In International Conference on Learning Representations, volume 2025, pages 61271–61304, 2025a. Kasra Arabi, R Teal Witter, Chinmay Hegde, and Niv Cohen. Seal: Semantic aware image watermarking. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16196–16205, 2025b. Elaine B. Barker and John Kelsey. Recommendation for random number generation using deterministic random bit generators. Technical Report NIST Special Publication 800-90A, National Institute 19 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories of Standards and Technology, 2012. URLhttps://api.semanticscholar.org/CorpusID: 263042844. Mihir Bellare, Ran Canetti, and Hugo Krawczyk. Keying hash functions for message authentication. In Annual International Cryptology Conference, 1996. URLhttps://api.semanticscholar.org/ CorpusID:6345601. Alan Chan, Carson Ezell, Max Kaufmann, Kevin Wei, Lewis Hammond, Herbie Bradley, Emma Bluemke, Nitarshan Rajkumar, David Krueger, Noam Kolt, Lennart Heim, and Markus Anderljung. Visibility into ai agents. Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, 2024. URL https://api.semanticscholar.org/CorpusID:267199743. Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125–1139. PMLR, 2024. Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Van- dana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, et al. Scalable watermarking for identifying large language model outputs. Nature, 634(8035):818–823, 2024. Xiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang, and Shirui Pan. Bimark: Unbiased multilayer watermarking for large language models. arXiv preprint arXiv:2506.21602, 2025. Pierre Fernandez, Guillaume Couairon, Hervé Jégou, Matthijs Douze, and Teddy Furon. The sta- ble signature: Rooting watermarks in latent diffusion models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 22466–22477, 2023. Ronald A. Fisher. Statistical Methods for Research Workers. Oliver and Boyd, Edinburgh, 1925. URL https://api.semanticscholar.org/CorpusID:7812384. Zheng Gao, Xiaoyu Li, Zhicheng Bao, Xiaoyan Feng, and Jiaojiao Jiang. Breaking semantic-aware watermarks via llm-guided coherence-preserving semantic injection. In Proceedings of the ACM Web Conference 2026, pages 8569–8572, 2026a. Zheng Gao, Yifan Yang, Xiaoyu Li, Xiaoyan Feng, Haoran Fan, Yang Song, and Jiaojiao Jiang. Slice: Semantic latent injection via compartmentalized embedding for image watermarking. arXiv preprint arXiv:2603.12749, 2026b. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, 1986. URLhttps://api.semanticscholar.org/CorpusID: 17064126. Samuel Gunn, Xuandong Zhao, and Dawn Song. An undetectable watermark for generative image models. In International Conference on Learning Representations, volume 2025, pages 6612–6637, 2025. Rameshwar D. Gupta and Debasis Kundu. Theory & methods: Generalized exponential distributions. Australian & New Zealand Journal of Statistics, 41, 1999. URLhttps://api.semanticscholar. org/CorpusID:118877852. Abe Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. Semstamp: A semantic watermark with paraphrastic robustness for text generation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4067–4082, 2024. 20 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In International Conference on Learning Representations, volume 2024, pages 45408–45436, 2024. Kaibo Huang, Zipei Zhang, Zhongliang Yang, and Linna Zhou. Agent guide: A simple agent behavioral watermarking framework. arXiv preprint arXiv:2504.05871, 2025. Kaibo Huang, Jin Tan, Yukun Wei, Wanling Li, Zipei Zhang, Hui Tian, Zhongliang Yang, and Linna Zhou. Agentmark: Utility-preserving behavioral watermarking for agents. arXiv preprint arXiv:2601.03294, 2026. Nikola Jovanović, Robin Staab, and Martin Vechev. Watermark stealing in large language models. arXiv preprint arXiv:2402.19361, 2024. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International conference on machine learning, pages 17061–17084. PMLR, 2023. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. In International Conference on Learning Representations, volume 2024, pages 49660–49704, 2024. Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. Advances in neural information processing systems, 36:27469–27500, 2023. Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023. Xiaoyu Li, Nan Sun, and Jiaojiao Jiang. Harnessing large language models for real-time cyber threat detection and response: A comprehensive survey. In Proceedings of the Australasian Conference on Information Security and Privacy (ACISP), 2026. Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1–36, 2024. Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Yuxian Gu, Han Ding, Kai Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Shengqi Shen, Tianjun Zhang, Sheng Shen, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. Agentbench: Evaluating llms as agents. ArXiv, abs/2308.03688, 2023. URL https://api.semanticscholar.org/CorpusID:260682249. Chris J. Maddison, Daniel Tarlow, and Thomas P. Minka. A* sampling. In Neural Information Processing Systems, 2014. URL https://api.semanticscholar.org/CorpusID:204937530. Wenlong Meng, Chen Gong, Terry Yue Zhuo, Fan Zhang, Kecen Li, Zheng Liu, Zhou Yang, Chengkun Wei, and Wenzhi Chen. Watermarking llm agent trajectories. arXiv preprint arXiv:2602.18700, 2026. Andreas Müller, Denis Lukovnikov, Jonas Thietke, Asja Fischer, and Erwin Quiring. Black-box forgery attacks on semantic watermarks for diffusion models. In Proceedings of the Computer Vision and Pattern Recognition Conference, pages 20937–20946, 2025. 21 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Joon Sung Park, Joseph O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, 2023. URLhttps://api. semanticscholar.org/CorpusID:258040990. Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. Gorilla: Large language model connected with massive apis. Advances in Neural Information Processing Systems, 37:126544–126565, 2024. Julien Piet, Chawin Sitawarin, Vivian Fang, Norman Mu, and David Wagner. Markmywords: Analyzing and evaluating language model watermarks. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 68–91. IEEE, 2025. Tiberiu Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica (Cluj), 9:129–145, 1935. Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. In International Conference on Learning Representations, volume 2024, pages 9695–9717, 2024. Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? arXiv preprint arXiv:2303.11156, 2023. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in neural information processing systems, 36:68539–68551, 2023. Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew J. Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. ArXiv, abs/2010.03768, 2020. URL https://api.semanticscholar.org/CorpusID:222208810. Liwen Wang, Zongjie Li, Yuchong Xie, Shuai Wang, Dongdong She, Wei Wang, and Juergen Rahmel. On protecting agentic systems’ intellectual property via watermarking. arXiv preprint arXiv:2602.08401, 2026. Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein. Tree-rings watermarks: Invisible fingerprints for diffusion images. Advances in Neural Information Processing Systems, 36:58047– 58063, 2023. Zijin Yang, Kai Zeng, Kejiang Chen, Han Fang, Weiming Zhang, and Nenghai Yu. Gaussian shading: Provable performance-lossless image watermarking for diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12162–12171, 2024. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022. KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4031–4055, 2024. Ning Yu, Vladislav Skripniuk, Sahar Abdelnabi, and Mario Fritz. Artificial fingerprinting for generative models: Rooting deepfake attribution in training data. In Proceedings of the IEEE/CVF International conference on computer vision, pages 14448–14457, 2021. 22 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Hanlin Zhang, Benjamin L Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: impossibility of strong watermarking for language models. In Forty-first International Conference on Machine Learning, 2024. Zhixiang Zhang, Zhicheng Bao, Xiaoyu Li, Jiaojiao Jiang, Qinghua Lu, Yulei Sui, and Liming Zhu. APR-router: Complexity-aware cascade routing for cost-effective LLM-based program repair. In Proceedings of the 37th IEEE International Symposium on Software Reliability Engineering (ISSRE), 2026. Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text. arXiv preprint arXiv:2306.17439, 2023. Xuandong Zhao, Kexun Zhang, Zihao Su, Saastha Vasan, Ilya Grishchenko, Christopher Kruegel, Giovanni Vigna, Yu-Xiang Wang, and Lei Li. Invisible image watermarks are provably removable using generative ai. Advances in neural information processing systems, 37:8643–8672, 2024. 23 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table of Contents A Notation25 B Map of the Results26 C Algorithms and the LLM Rewriter Prompt27 D Supporting Theory and Missing Proofs28 D.1 The Race Lemma and Proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . 28 D.2 Exact Null Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 D.3 The Conditional Law of the Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 D.4 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 D.5 Detection Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 D.6 Deletion Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 D.7 Informed Substitution and Rewrite Invariance . . . . . . . . . . . . . . . . . . . . . . 32 D.8 Proof of Theorem 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 D.9 Composition of the Two Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 E Practical Notes35 F Additional Experimental Results36 F.1 ToolBench Detection per Split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 F.2 ALFWorld per Seed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 F.3 Redundant-Record Accounting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 F.4 Backbone Ablation (Local Qwen under vLLM) . . . . . . . . . . . . . . . . . . . . . . 38 F.5 Baseline Robustness in Full . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 F.6 Detection Power at Calibrated FPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 24 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Appendix A. Notation We collect the symbols used throughout. The conventions are those of Sections 3 and 4; this table is a reference, not a redefinition, and every entry points to the place where the object is introduced. Table 4 | Symbols used throughout Trace, each with a pointer to where it is introduced. SymbolMeaning Trajectories and grouping (Section 3.1) 휏agent trajectory: a finite sequence of tagged records (Def. 3.1) 푒 푡 , 휌(푒 푡 ), 푐(푒 푡 )record 푡, its role tag 휌∈ dec, obs, its content string (Def. 3.1) 푠(휏)skeleton: the tag sequence (휌(푒 1 ), . . . , 휌(푒 푇 )) (Def. 3.1) 푔 1 , . . . , 푔 푚 decision-boundary grouping into 푚 groups (Def. 3.2) 푘 푖 number of obs records in 푔 푖 ; the tally channel’s carrier (Def. 3.2) 퐵 푖 , 푁 푖 =|퐵 푖 |candidate behavior set at decision 푖 and its size (Def. 3.4) 푃 푖 , 푏 푖 , 퐴 푖 agent distribution over퐵 푖 ; the selected behavior; the recorded action- identity sequence (Def. 3.4) H(푃 푖 )Shannon entropy of 푃 푖 in nats (Def. 3.4) effective groupa group with푁 푖 ≥2 and non-terminal selection; only these are pooled (Def. 3.4) 푛number of effective, deduplicated pooled groups Keyed pseudorandomness (Section 3.1) DRBG(key, nonce)deterministic random bit generator in[0,1), instantiated with HMAC- SHA512 퐻(·)hash deriving drbg keys and nonces from structured inputs key 1 , key 2 the provider’s two independent secret keys Assumption 3.5ideal pseudorandomness: i.i.d. uniform across distinct nonces, inde- pendent across keys Selection channel (Section 4.1) ctx 푖 = enc(퐴 푖−1 )∥ key 1 content-keyed watermark context of group 푖 (1) encinjective encoding of action-identity sequences 푟 푏 = DRBG(퐻(ctx 푖 ), 푏)keyed value in (0, 1) for candidate 푏 (2) 푏 푖 = argmax 푏 푟 1/푃 푖 [푏] 푏 distortion-free keyed exponential race (3) 휑 푖 =−ln(1− 푟 푏 푖 )selection score of group 푖 (4) 푋 1 , 푧 1 pooled selection sum Í 푖 휑 푖 and its 푧-statistic (5) 푄(푛, 푋 1 )upper regularized incomplete Gamma tail: the selection 푝-value 푝 1 exact selection-channel 푝-value Tally channel (Section 4.2) 휌 푖 = DRBG(퐻(key 2 ), 퐻(qid∥ 푖)) skeleton-keyed target draw for group 푖 (6) 퐺 푖 ∈ 1,2keyed target count set (6) qidtask-instance identifier ̃푒context-neutral redundant record appended when 퐺 푖 =2 (Def. 4.1) 푝 0 = 1 2 tally null hit rate continued on next page 25 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories SymbolMeaning 푋 2 , 푧 2 tally hit count Í 푖 1[푘 푖 ∈ 퐺 푖 ] and its 푧-statistic (7) 푝 2 exact tally-channel 푝-value 휃detection threshold on the pooled푧-statistic (휃=2 in the experiments) Threat model and attacks (Sections 3.2–3.3) provider / reseller / verifierdefender; log-holding adversary; key-holding auditor (Section 3.2) 푟 per-observation deletion rate: each obs record dropped independently w.p. 푟 (Def. 3.6) 푅, 푞rewriting attack with 푠(푅(휏))= 푠(휏), at strength 푞 (Def. 3.7) LLM rewriterinformed, plausibility-preserving substitution instance (Section 3.3) Detection and constants (Section 5) 퐻 0 , 퐻 1 null (key-less) and alternative (watermarked) hypotheses (Section 3.2) 훼target false positive rate; the detector rejects when min(푝 1 , 푝 2 ) ≤ 훼/2 휓, 휓 ′ , 훾digamma, trigamma, and the Euler–Mascheroni constant (Lem. D.4) generalized exponential lawconditional law of 휑 푖 given the winner, shape 1/푝 푏 (Lem. D.4) B. Map of the Results Figure 7 traces the dependency structure of the theory in four layers. Two restated facts supply the inputs the construction stands on: the ideal-pseudorandomness assumption (Assumption 3.5) and the skeleton invariance of the grouping (Proposition 3.3, immediate from Definition 3.2). The lemmas are the load-bearing mechanisms: the race lemma (Lemma D.1) for distortion-freeness, the conditional law of the score (Lemma D.4) and the trigamma estimate (Lemma D.7) for the entropy bound, and the two null laws (Lemmas D.2 and D.3) for exact false-positive control. The four boxed theorems assemble these: distortion-freeness (Theorem 5.1) from the race lemma, the entropy– detectability bound (Theorem 5.2) from the conditional law and the trigamma estimate, rewrite invariance (Theorem 5.3) from skeleton invariance, and the robustness propositions, blast radius one (Proposition D.9) and below-null drift under informed substitution (Proposition D.10), from the entropy bound and the conditional law respectively. Everything converges on the capstone: the joint-erasure theorem (Theorem 5.4) reads off rewrite invariance, the tally null, the entropy bound, and the two robustness propositions, pricing the cost of silencing both channels at once. Off to the side, one-way coupling (Proposition D.13) combines the two null laws under the cross-key independence of Assumption 3.5 to license the joint test, and the sample-complexity corollary (Corollary D.8) turns the entropy bound, together with the conditional-law variance, into the pooling rate. 26 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Assumption 3.5 ideal PRF Prop. 3.3 skeleton fixes positions Lemma D.1 race property Lemma D.4 conditional law Lemma D.7 trigamma bound Lemma D.2 selection null Lemma D.3 tally null Thm 5.1 distortion-free Thm 5.2 entropy bound Prop. D.9 blast radius one Prop. D.10 below-null drift Prop. D.13 joint FPR Thm 5.3 rewrite invariance Cor. D.8 detection power Thm 5.4 joint erasure Figure 7|Dependency map of the theory. Dashed boxes are restated foundational facts; solid boxes are results of this paper; the yellow box is the capstone. Arrows trace each result’s principal proof inputs; secondary and purely transitive dependencies are omitted for clarity. Utility and detection (top) and robustness (bottom) meet at the joint-erasure theorem. C. Algorithms and the LLM Rewriter Prompt Algorithms 1 and 2 give the embedder and detector of Section 4 in full. The prompt below instantiates the LLM rewriter, the informed rewriting attack we introduce in Section 3.3; one call is issued per attacked group. Algorithm 1 Trace embedding (one task instance) 1: 퐴 0 ← bootstrap 2: for each decision 푖= 1, 2, . . . do 3:elicit 퐵 푖 , 푃 푖 from agent and environment 4: ctx 푖 ← enc(퐴 푖−1 )∥ key 1 ; 푟 푏 ← DRBG(퐻(ctx 푖 ), 푏) for all 푏∈ 퐵 푖 5: 푏 푖 ← argmin 푏 (− ln푟 푏 )/푃 푖 [푏]⊲ selection channel: distortion-free selection 6:execute 푏 푖 ; record decision and primary observation 7: 휌 푖 ← DRBG(퐻(key 2 ), 퐻(qid∥푖)) 8: if 휌 푖 ≥ 1 2 and augmentation admissible then 9:append context-neutral redundant record ̃푒 with 푐( ̃푒)= 푓(휋)⊲ tally channel: 푘 푖 = 2 10: end if 11: 퐴 푖 ← action identities recorded in 푔 푖 12: end for 27 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Algorithm 2 Trace detection (pooled over trajectories) 1:regroup each trajectory by its skeleton (Definition 3.2); never trust self-reported indices or values 2:deduplicate: among groups sharing an evaluation point, keep one representative (Assumption 3.5) 3: for each effective group 푖 do 4:recompute ctx 푖 , (푟 푏 ) 푏∈퐵 푖 , and 휑 푖 ←−ln(1− 푟 푏 푖 )⊲ selection channel 5:recompute 퐺 푖 from (6); record hit 1[푘 푖 ∈ 퐺 푖 ]⊲ tally channel 6: end for 7: 푧 1 ← (푋 1 − 푛)/ √ 푛 with exact 푝-value 푄(푛, 푋 1 ) 8: 푧 2 ← (푋 2 − 푛푝 0 )/ √︁ 푛푝 0 (1− 푝 0 ) with exact Binomial 푝-value 9: return reject 퐻 0 if min(푝 1 , 푝 2 ) ≤ 훼/2 LLM rewriter prompt System. You audit AI-agent trajectories. Given one decision step, you pick a different but still plausible action the agent could have taken. User (template, one call per attacked group). At this step the agent observed: obs Available actions: actions The agent chose: chosen Pick ONE different action from the available list that a reasonable agent could plausibly have taken instead. Reply with only the exact action name, nothing else. D. Supporting Theory and Missing Proofs This appendix states the supporting results deferred from Section 5 and proves every claim of the paper. Throughout,휓is the digamma function,휓 ′ = 휓 (1) the trigamma function, and훾=−휓(1)the Euler–Mascheroni constant. Proposition 3.3 is immediate from Definition 3.2: the partition depends only on the positions of dec tags. The remaining results follow in order of appearance. D.1. The Race Lemma and Proof of Theorem 5.1 Lemma D.1 (Race property). Let퐸 푏 :=− ln푟 푏 ,푇 푏 := 퐸 푏 /푃 푖 [푏], and푇:= min 푏 푇 푏 . Then푏 푖 and푇are independent, Pr[ 푏 푖 = 푏]= 푃 푖 [푏], and 푇 ∼ Exp(1). Proof.The퐸 푏 are i.i.d.Exp(1)by Assumption 3.5, so푇 푏 ∼ Exp(푃 푖 [푏])independently (we restrict to the support푏:푃 푖 [푏] >0; a candidate with푃 푖 [푏]=0 sets푇 푏 =+∞and is selected with probability 0). For 푡 ≥ 0, Pr[ 푏 푖 = 푏, 푇 > 푡]= ∫ ∞ 푡 푃 푖 [푏] 푒 −푃 푖 [푏]푠 Ö 푏 ′ ≠푏 푒 −푃 푖 [푏 ′ ]푠 푑푠= 푃 푖 [푏] ∫ ∞ 푡 푒 −푠 푑푠= 푃 푖 [푏] 푒 −푡 , using Í 푏 ′ 푃 푖 [푏 ′ ]=1. The product form gives independence and both marginals at once. Theorem 5.1 is immediate.□ D.2. Exact Null Distributions 28 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Lemma D.2 (Selection-channel null distribution). Under퐻 0 and Assumption 3.5, the scores 휑 1 , . . . , 휑 푛 of the푛pooled (effective, deduplicated) groups are i.i.d.Exp(1); hence푋 1 ∼ Gamma(푛,1) exactly, the one-sided푝-value is the regularized upper incomplete Gamma function푄(푛, 푋 1 ), and 푧 1 ⇒N(0, 1) as 푛→∞. Proof.Under퐻 0 the producer holds no information aboutkey 1 , so by Assumption 3.5 the value푟 푏 푖 at the realized (deduplicated) evaluation point(ctx 푖 , 푏 푖 )is uniform on(0,1), independently across groups. Then휑 푖 ∼ Exp(1), and the remaining claims are standard properties of sums of i.i.d. exponentials.□ Lemma D.3 (Tally null distribution and exact tail). Under퐻 0 with푝 0 = 1 2 , if every pooled group has푘 푖 ∈ 1,2then푋 2 ∼ Bin(푛, 1 2 ); in particularPr[푋 2 = 푛]=2 −푛 . A group with푘 푖 ∉ 1,2is a forced miss, so for a general baseline푋 2 is stochastically dominated byBin(푛, 1 2 )and the upper tail remains a conservative 푝-value. Proof.The pooled groups’ tally evaluation points퐻(qid∥ 푖)are pairwise distinct, distinct task in- stances carrying distinctqidand within-trajectory indices being distinct, with any residual collision removed by the deduplication of Assumption 3.5. Under퐻 0 the targets퐺 푖 are therefore, by Assump- tion 3.5, i.i.d. uniform over1,2and independent of the trajectory. When푘 푖 ∈ 1,2, exactly one of1,2contains푘 푖 , so each indicator in(7)is a fair coin; a group with푘 푖 ∉ 1,2lies in neither target and is a deterministic miss, which only lowers 푋 2 (Appendix E).□ D.3. The Conditional Law of the Score Lemma D.4 (Conditional law of the score). Let group푖be watermarked via(3)and write푝 푏 := 푃 푖 [푏]. Conditional on 푏 푖 = 푏, the score 휑 푖 has distribution function 퐹 푏 (푡)= 1− 푒 −푡 1/푝 푏 , 푡 ≥ 0, the generalized exponential law with shape 1/푝 푏 [Gupta and Kundu, 1999]. Consequently 피[휑 푖 | 푏 푖 = 푏]= 휓 1 푝 푏 + 1 + 훾, Var[휑 푖 | 푏 푖 = 푏]= 휓 ′ (1)− 휓 ′ 1 푝 푏 + 1 < 휋 2 6 , and, unconditionally,피[휑 푖 ]= Í 푏 푝 푏 휓(1/푝 푏 + 1)+ 훾 . Proof.Write푝:= 푝 푏 and condition throughout on푏 푖 = 푏. By Lemma D.1, the winning exponential satisfies퐸 푏 푖 = 푝푇where푇:= min 푏 ′ 푇 푏 ′ ∼ Exp(1)is independent of the identity of the winner. Hence 푟 푏 푖 = 푒 −퐸 푏 푖 = 푒 −푝푇 and 휑 푖 =−ln 1− 푒 −푝푇 , 푇 ∼ Exp(1). For 푡 ≥ 0, Pr[휑 푖 ≤ 푡]= Pr 푒 −푝푇 ≤ 1− 푒 −푡 = Pr h 푇 ≥− 1 푝 ln(1− 푒 −푡 ) i = 1− 푒 −푡 1/푝 , which is the claimed distribution function with shape 훼 := 1/푝≥ 1. 29 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories For the moments we compute the moment generating function. The density is푓(푡)= 훼(1− 푒 −푡 ) 훼−1 푒 −푡 , and for 푠 < 1 the substitution 푣= 푒 −푡 (so 푒 푠푡 = 푣 −푠 , 푑푡=−푑푣/푣) gives 피 푒 푠휑 푖 = 훼 ∫ ∞ 0 푒 푠푡 (1− 푒 −푡 ) 훼−1 푒 −푡 푑푡= 훼 ∫ 1 0 푣 −푠 (1− 푣) 훼−1 푑푣= 훼 퐵(1− 푠, 훼)= Γ(1− 푠)Γ(훼+ 1) Γ(훼+ 1− 푠) . The cumulant generating function is therefore 퐾(푠)= lnΓ(1− 푠)+ lnΓ(훼+ 1)− lnΓ(훼+ 1− 푠), with 퐾 ′ (푠)=−휓(1− 푠)+ 휓(훼+ 1− 푠), 퐾 ′ (푠)= 휓 ′ (1− 푠)− 휓 ′ (훼+ 1− 푠). Evaluating at푠=0 and using휓(1)=−훾:피[휑 푖 | 푏]= 휓(훼+1)+ 훾andVar[휑 푖 | 푏]= 휓 ′ (1)− 휓 ′ (훼+1). The variance bound follows from휓 ′ (1)= 휋 2 /6 and휓 ′ >0. The unconditional mean follows from Lemma D.1 (the winner is 푏 with probability 푝 푏 ) and the tower rule.□ Corollary D.5 (Uniform decisions). If푃 푖 is uniform on푁 푖 candidates, then conditional on any selection휑 푖 is distributed as the maximum of푁 푖 i.i.d.Exp(1)variables; in particular피[휑 푖 ]= 퐻 푁 푖 := Í 푁 푖 푗=1 1/푗= ln 푁 푖 + 훾+ 표(1) and Var[휑 푖 ]= Í 푁 푖 푗=1 1/푗 2 ≤ 휋 2 /6. Proof.With푝 푏 =1/푁 푖 for all푏, the shape is훼= 푁 푖 and the conditional distribution function is (1−푒 −푡 ) 푁 푖 , exactly that of the maximum of푁 푖 i.i.d.Exp(1)variables, whose mean and variance are the classical퐻 푁 푖 and Í 푁 푖 푗=1 1/푗 2 . (Equivalently: from Lemma D.4 and the recurrence휓(푥+1)= 휓(푥)+1/푥, induction gives휓(푁+1)+ 훾= 퐻 푁 and휓 ′ (1)− 휓 ′ (푁+1)= Í 푁 푗=1 1/푗 2 .) The conditional law does not depend on which candidate won, so it is also the unconditional law.□ Corollary D.6 (Deterministic decisions). If푃 푖 is a point mass, then휑 푖 ∼ Exp(1), identical to the null. Proof.With푝 푏 =1 the shape is훼=1 and the distribution function is 1− 푒 −푡 , i.e.,Exp(1). (Directly: the selection is deterministic, so it reveals nothing about 푟 푏 , which remains uniform.)□ D.4. Proof of Theorem 5.2 We first isolate the trigamma estimate. Lemma D.7. For every 푦 > 0: 휓 ′ (푦) > 1 푦 + 1 2푦 2 . Proof.Recall휓 ′ (푦)= Í 푘≥0 (푦+ 푘) −2 . The function푓(푡):= (푦+ 푡) −2 is strictly convex on[0,∞), so the trapezoid rule strictly overestimates each panel: ∫ 푘+1 푘 푓(푡) 푑푡 < 1 2 푓(푘)+ 푓(푘+1) for every푘≥0. Summing over 푘 and telescoping, 1 푦 = ∫ ∞ 0 푓(푡) 푑푡 < ∑︁ 푘≥0 푓(푘)− 푓(0) 2 = 휓 ′ (푦)− 1 2푦 2 .□ 30 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Theorem 5.2 (Entropy lower bound on the signal). For every distribution 푃 푖 , 피[휑 푖 ] ≥ 1+ 1 2 H(푃 푖 ), with equality if and only if 푃 푖 is a point mass. Proof. By Lemma D.4 it suffices to prove the scalar inequality 휓(푥+ 1)+ 훾 ≥ 1+ 1 2 ln 푥for all 푥 ≥ 1,(8) with equality only at푥=1; the theorem then follows by applying(8)with푥=1/푝 푏 ≥1 for each푏in the support of 푃 푖 and averaging: 피[휑 푖 ]= ∑︁ 푏 푝 푏 휓 1 푝 푏 + 1 + 훾 ≥ ∑︁ 푏 푝 푏 1+ 1 2 ln 1 푝 푏 = 1+ 1 2 H(푃 푖 ), with equality iff every supported 푝 푏 equals 1, i.e., iff 푃 푖 is a point mass. To prove(8), set퐹(푥):= 휓(푥+1)+ 훾−1− 1 2 ln 푥on[1,∞). Since휓(2)=1− 훾, we have퐹(1)=0. Differentiating and applying Lemma D.7 at 푦= 푥+ 1, 퐹 ′ (푥)= 휓 ′ (푥+ 1)− 1 2푥 > 1 푥+ 1 + 1 2(푥+ 1) 2 − 1 2푥 = 2푥(푥+ 1)+ 푥−(푥+ 1) 2 2푥(푥+ 1) 2 = 푥 2 + 푥− 1 2푥(푥+ 1) 2 , which is strictly positive for푥 ≥1. Hence퐹is strictly increasing on[1,∞)with퐹(1)=0, proving(8) with the stated equality case.□ D.5. Detection Power Corollary D.8 (Detection power). Suppose every effective group satisfiesH(푃 푖 ) ≥ ̄ ℎ >0 and all nonzero candidate probabilities lie in[푝 ∗ ,1], and set휎 2 ∗ := 휋 2 /6+ 1 4 휓(1/푝 ∗ +1)+ 훾−1 2 . Then for every threshold 휃 > 0 and every 훽 ∈ (0, 1), 푛 ≥ 4 휃+ 휎 ∗ 훽 −1/2 2 ̄ ℎ 2 =⇒ Pr 퐻 1 푧 1 ≤ 휃 ≤ 훽. Proof.Fix an effective group푖and abbreviate휇 푖 :=피[휑 푖 ],푔(푝):= 휓(1/푝+1)+ 훾. By Theorem 5.2, 휇 푖 ≥ 1+ ̄ ℎ/2. By Lemma D.4 and the law of total variance, Var[휑 푖 ]=피 푏 Var[휑 푖 | 푏] + Var 푏 푔(푝 푏 ) ≤ 휋 2 6 + 푔(푝 ∗ )− 푔(1) 2 4 = 휎 2 ∗ , where the second term uses Popoviciu’s inequality [Popoviciu, 1935] for the random variable푔(푝 푏 푖 ) ∈ [푔( 1), 푔(푝 ∗ )]=[1, 휓(1/푝 ∗ +1)+ 훾](푔is decreasing and all supported probabilities lie in[푝 ∗ ,1]). The scores are independent across (deduplicated) groups, so피[푋 1 ] ≥ 푛(1+ ̄ ℎ/2)andVar[푋 1 ] ≤ 푛휎 2 ∗ . The event 푧 1 ≤ 휃 is 푋 1 ≤ 푛+ 휃 √ 푛; whenever √ 푛 ̄ ℎ/2 > 휃, Chebyshev’s inequality gives Pr[ 푋 1 ≤ 푛+ 휃 √ 푛] ≤ 푛휎 2 ∗ 푛 ̄ ℎ/2− 휃 √ 푛 2 = 휎 2 ∗ √ 푛 ̄ ℎ/2− 휃 2 . This is at most훽as soon as √ 푛 ̄ ℎ/2− 휃≥ 휎 ∗ / √︁ 훽, i.e.,푛≥4(휃+ 휎 ∗ 훽 −1/2 ) 2 / ̄ ℎ 2 (which also implies the side condition).□ 31 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories D.6. Deletion Robustness Proposition D.9 (Blast radius one: deletion attenuates but never inverts). Let휏be watermarked with푚effective single primary-observation groups (푘 푖 ∈ 1,2: one genuine observation plus an optional redundant record), and let휏 ′ be obtained by deleting each obs record independently with probability푟, the dec records (hence all푚groups) preserved. The detector reads the genuine selected identity푏 푖 , so, absent post-deletion evaluation-point collisions (a deletion-shifted context coinciding with another group’s embedded or deletion-shifted context, a generic condition; see the proof), every score is stochastically at least the null,휑 푖 ⪰ Exp(1)with피[휑 푖 ] ≥1 and never below it; a group whose predecessor retains all its records keeps its embedded above-null score,피[휑 푖 ] ≥1+ 1 2 H(푃 푖 ). Consequently 피 푋 1 (휏 ′ ) ≥ 푚 + 1 2 (1− 푟) 2 푚 ∑︁ 푖=1 H(푃 푖 ) ≥ 푚+ 1 2 (1− 푟) 2 푚H min , whereH min := min 푖 H(푃 푖 )and all groups are effective, so피[푧 1 (휏 ′ )] ≥ 1 2 ( 1− 푟) 2 √ 푚H min >0 for every 푟 < 1. Proof.By(1)the contextctx 푖 depends only on퐴 푖−1 and the key, which the detector recomputes from the surviving records of group푔 푖−1 . Two facts drive the result. First, the dec records are preserved, so the detector reads the genuine selected identity푏 푖 and the only effect of deletion is on the keying context: deletion can never substitute a race loser, so, in contrast with rewriting (Proposition D.10), it cannot push a score below the null. Second, the window has memory one, so deleting a record from 푔 푗 disturbs the context of at most its immediate successor 푔 푗+1 (blast radius one). A group푔 푖 whose predecessor retains all its records hasctx 푖 unchanged: the detector recomputes the embedded value푟 푏 푖 , and휑 푖 keeps the above-null law of Lemma D.4,피[휑 푖 ] ≥1+ 1 2 H(푃 푖 ) by Theorem 5.2. Otherwise the recomputedctx 푖 differs from the embedded one and the detector queries the drbg at the point(ctx 푖 , 푏 푖 ). Unless the shifted context coincides with another group’s embedded context, this point went unqueried during embedding, so by Assumption 3.5 the value푟 푏 푖 is uniform and independent of the embedder’s selection푏 푖 (made under the old context), giving휑 푖 ∼ Exp(1): mean exactly 1, never below. We take such collisions to be absent, the generic case, since a collision requires the deletion-shortened sequence퐴 ′ 푖−1 to reproduce another group’s verbatim sequence퐴 푗−1 under the injective encodingenc; deduplication does not remove it, because the two share a context but not a full evaluation point(ctx, 푏). The same genericity excludes two deletion-shifted groups sharing a full evaluation point, so deduplication removes nothing and푛= 푚. Were one collision to occur, that single group would read a race loser of the collided group and fall below the null (Proposition D.10), but never beneath the pointwise floor휑 푖 ≥0 of(4), which bounds every group in every case. Group푔 푖−1 retains all푘 푖−1 ≤2 of its records with probability(1− 푟) 푘 푖−1 ≥ (1− 푟) 2 (group푔 1 , with the bootstrap context, is always intact). Conditioning,피[휑 푖 ] ≥1+ 1 2 H(푃 푖 )(1− 푟) 푘 푖−1 , and summing over the 푚 preserved groups gives the displayed bound.□ D.7. Informed Substitution and Rewrite Invariance 32 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Proposition D.10 (Informed substitution overshoots the null). Fix a group with푝 푏 <1 for the selected푏. If the recorded identity is replaced by a candidate푏 ′ ≠ 푏 푖 from the same group with푝 푏 ′ >0 (so the detector evaluates a race loser), then피[− ln(1− 푟 푏 ′ ) | 푏 푖 ≠ 푏 ′ ] <1: the substituted score falls strictly below the null mean. If instead푝 푏 ′ =0, the substituted score has conditional mean exactly 1; in no case does substitution push the score above the null. Proof.Unconditionally피[− ln(1− 푟 푏 ′ )]=1 since푟 푏 ′ is uniform. If푝 푏 ′ =0, then푏 ′ is never selected (Lemma D.1), so푟 푏 ′ never affects the selection and remains an independent uniform on the conditioning event푏 푖 ≠ 푏 ′ , giving conditional mean exactly 1. Now let푝 푏 ′ >0. The selected푏is realized, so 푝 푏 >0 (Theorem 5.1), and since푏 ′ ≠ 푏we have푝 푏 ′ ≤1− 푝 푏 <1, so푝 푏 ′ ∈ (0,1). By Lemma D.4, 피[− ln(1− 푟 푏 ′ ) | 푏 푖 = 푏 ′ ]= 휓(1/푝 푏 ′ +1) + 훾 >1. SincePr[푏 푖 = 푏 ′ ]= 푝 푏 ′ (Theorem 5.1) and 1= 푝 푏 ′ 피[− ln(1−푟 푏 ′ ) | 푏 푖 = 푏 ′ ]+(1− 푝 푏 ′ )피[−ln(1−푟 푏 ′ ) | 푏 푖 ≠ 푏 ′ ]with 1− 푝 푏 ′ >0, the complementary conditional expectation is forced strictly below 1.□ Theorem 5.3 (Rewrite invariance of the tally). For every rewriting attack푅(Definition 3.7) and every trajectory 휏: 푋 2 (푅(휏))= 푋 2 (휏), hence 푧 2 (푅(휏))= 푧 2 (휏). Proof. By Proposition 3.3, 푅 preserves group positions and the counts (푘 푖 ), which are the carrier. By (6) , each target퐺 푖 depends only on(key 2 , qid, 푖); the task identifierqidis trajectory-level metadata reconciled against the provider’s upstream consumption record, not an editable record content푐(푒 푡 ), so the keying reads nothing a rewriting attack can alter. Every indicator in(7)is therefore unchanged. Finally, the pooled index set is unchanged as well: by Definition 3.4, effectiveness is evaluated against the environment-supplied퐵 푖 and the executed action stream, neither of which푅can edit, and the tally evaluation points퐻(qid∥ 푖)are content-free, so deduplication reads nothing푅can touch. Hence the summation set and its size푛coincide for휏and푅(휏), giving푋 2 (푅(휏))= 푋 2 (휏)and푧 2 (푅(휏))= 푧 2 (휏).□ D.8. Proof of Theorem 5.4 33 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Theorem 5.4 (Cost of joint erasure). Let휏be watermarked with푚effective single primary- observation groups (푘 푖 =1 absent augmentation) and admissible augmentation throughout, each group withH(푃 푖 ) ≥ ℎ > 0, and let 퐴 be any attack producing 휏 ′ . (a)If퐴is skeleton-preserving, then푧 2 (휏 ′ )= 푧 2 (휏)= √ 푚: the tally channel is untouched. Hence any attack with피[푧 2 (휏 ′ )] < √ 푚edits the skeleton, deleting or inserting records, and is exposed to the log/execution consistency audit. (b) If퐴corrupts the selection-channel evaluation point (its context or its selected identity) of at most푎groups, whether by deleting records that feed a group’s context or by altering a selected identity, and chooses the corrupted set obliviously, that is, independently of the realized selection-channel values (the substitution within a corrupted group may still be informed), then, since the preserved decisions keep all 푚 groups, 피 푧 1 (휏 ′ ) ≥ (푚− 푎) 1+ ℎ 2 − 푚 √ 푚 . Consequently, for any threshold 휃≥ 0,피[푧 1 (휏 ′ )] ≤ 휃 forces 푎 ≥ ℎ 2+ ℎ 푚 − 휃 √ 푚 : the reseller must corrupt a constant fraction of the trajectory. Proof.(a) If푠(휏 ′ )= 푠(휏), Theorem 5.3 gives푧 2 (휏 ′ )= 푧 2 (휏), and Lemma D.3 together with the embed- ding rule gives푧 2 (휏)= √ 푚for the watermarked휏with admissible augmentation. The contrapositive is the second sentence. (b) The preserved decisions keep all푚groups, so푛= 푚groups are scored. Call a group intact if its selection-channel evaluation point is uncorrupted; by hypothesis at least푚− 푎are intact. Because the corrupted set is chosen obliviously, it is independent of the realized race values, so conditioning on it leaves each intact group’s score with conditional mean at least 1+ 1 2 H(푃 푖 ) ≥1+ ℎ 2 (Theorem 5.2 and the entropy floor ℎ); summing and taking expectations, 피 h Í 푖 intact 휑 푖 i ≥ 1+ ℎ 2 피 #푖 intact ≥ (푚− 푎) 1+ ℎ 2 , which needs only that the kept set is independent of the realized scores, not of the elicited entropies. (Without obliviousness this step fails: an attacker targeting groups whose realized winner was improbable removes more than 1+ ℎ/2 per corrupted group; see Remark D.12.) For the corrupted groups we use only휑 푖 ≥0, which holds pointwise by(4): a deletion-shifted context contributes mean 1 (Proposition D.9) and a rewriting substitution mean below 1 (Proposition D.10), both nonnegative; note we may not credit the rewritten groups with the null mean 1. Therefore, with 푛= 푚, 피 푋 1 (휏 ′ ) ≥ (푚− 푎) 1+ ℎ 2 ,피 푧 1 (휏 ′ ) ≥ (푚− 푎)(1+ ℎ/2)− 푚 √ 푚 . Now suppose피[푧 1 (휏 ′ )] ≤ 휃 for a threshold 휃≥ 0. Rearranging, (푚− 푎) 1+ ℎ 2 ≤ 푚+ 휃 √ 푚, hence 푎 ≥ 푚− 푚+ 휃 √ 푚 1+ ℎ/2 = ℎ 2+ ℎ 푚− 휃 √ 푚 1+ ℎ/2 ≥ ℎ 2+ ℎ 푚− 휃 √ 푚.□ 34 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Remark D.11. A single content edit can alter at most two groups’ selection-channel evaluation points (its own selected identity and, through the memory-one window, its successor’s context), so the bound on푎translates into a bound of at least푎/2 on the number of edited records; the constant-fraction conclusion is unchanged. Remark D.12 (Why obliviousness is needed in (b)). The hypothesis is necessary, not an artifact of the proof. By Lemma D.4 the conditional mean of a score given its winner,휓(1/푝 푏 +1)+ 훾, is unbounded as푝 푏 →0 whileH(푃 푖 )can stay small, so an attacker that observes the realized selections and targets precisely the groups whose winner was improbable removes more than 1+ ℎ/2 of expected signal per altered group, and with sufficiently skewed decision distributions it suppresses푧 1 on a budget below the bound. The oblivious class still covers intervention sets chosen by position, at random, or by any rule ignorant of the realized selections; in particular it covers the attacks of Section 6, where the LLM rewriter attacks a random fraction푞of groups while remaining fully informed within each attacked group. Quantifying the score-adaptive rate, which involves the order statistics of the conditional laws of Lemma D.4, is left open. D.9. Composition of the Two Tests Proposition D.13 (One-way coupling and joint FPR). The tally-channel targets(퐺 푖 )are independent ofkey 1 and of all selection-channel randomness; under퐻 0 the exact푝-values푝 1 and푝 2 are independent (the 푧-scores, sharing the random count 푛, are independent only conditional on the trajectory). The combined test that rejects when either layer’s exact푝-value falls below훼/2 has false positive rate at most훼by the union bound; independence of(푝 1 , 푝 2 )further licenses the Fisher and Stouffer combinations, which remain valid but are conservative because the Binomial 푝 2 is discrete. Proof.By(6)the targets(퐺 푖 )are functions of(key 2 , qid, 푖)only. Under Assumption 3.5, DRBG calls under the independent keyskey 1 andkey 2 are mutually independent, so(퐺 푖 )is independent of the family(푟 푏 )of(2)and of everything computed from it. Under퐻 0 the trajectory휏is independent of both keys, andkey 1 ⊥ key 2 . Condition on the pair(휏, 푋 2 ), which fixes the skeleton, the counts (푘 푖 ), every selection-channel evaluation point, the deduplicated index set, the count푛, and the tally statistic. Given(휏, 푋 2 ), the selection statistic푋 1 is a function of thekey 1 -values at the now-fixed evaluation points alone, and, sincekey 1 is independent of휏and ofkey 2 (hence of푋 2 ), it remains Gamma(푛,1); so by Lemma D.2 the exact푝-value푝 1 = 푄(푛, 푋 1 )is uniform on(0,1)given(휏, 푋 2 )(the probability integral transform). As this holds for every value of(휏, 푋 2 ),푝 1 is independent of(휏, 푋 2 ), and in particular of푝 2 , which is a function of(푛, 푋 2 ). The푧-scores are not in general independent marginally, as both standardize by the same random푛= 푛(휏); the dependence vanishes only at the 푝-value level. The union bound, which uses no independence, givesPr 퐻 0 [ 푝 1 ≤ 훼/ 2or 푝 2 ≤ 훼/2] ≤ 훼. Independence of(푝 1 , 푝 2 )licenses Fisher’s method [Fisher, 1925] applied to−2ln 푝 1 −2ln 푝 2 and Stouffer’s to(푧 1 + 푧 2 )/ √ 2; because the Binomial푝 2 is discrete (super-uniform), the휒 2 4 and normal references are conservative rather than exact.□ E. Practical Notes Elicitation of푃 푖 . The distribution푃 푖 is elicited from the agent at decision time (e.g., as normalized scores over퐵 푖 ); when parsing fails we fall back to the uniform distribution on퐵 푖 , which by Corollary D.5 is the most detectable case and by Theorem 5.1 still leaves the realized selection a faithful sample of the fallback distribution actually used. 35 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Estimating푝 0 . The tally-channel null rate푝 0 = 1 2 is exact whenever the baseline agent’s group counts satisfy푘 푖 ≡1, because the balanced keyed pattern(6)then makes each hit a fair coin regardless of the baseline’s behavior. A baseline that emits푘 푖 =2 keeps a fair-coin hit, but a group with푘 푖 ∉1,2 is a guaranteed miss, since neither1nor2contains푘 푖 . Such groups only lower the null hit rate below 1 2 , so for heavy-observation baselines theBin(푛, 1 2 )tail is a conservative bound on the null 푝-value rather than exact; we report empirically calibrated 푝 0 for transparency. Log/execution consistency audit. Operationally, the verifier compares the skeleton of the reseller- released log against the grouping reconstructed from the provider-side execution record; any mismatch in dec counts or group boundaries flags tampering (Section 3.2). The audit is assumed available rather than evaluated in our experiments. Admissibility. When a group’s logging format does not admit a redundant record, the embedder leaves푘 푖 =1; if the target was2this group becomes a guaranteed miss. With admissibility rate휂 over target-2 groups, the watermarked hit rate is 1− 1 2 (1− 휂)and the detection statistics adjust in the obvious way; all groups remain usable. Remark E.1 (Window knob). Whether the selection channel’s window includes redundant records is a design choice. Including them (our default) couples the layers: a targeted deletion of redundant records then also corrupts the selection-channel contexts of the following groups, so the selection channel shares a sliver of the tally channel’s deletion exposure, bounded as in Proposition D.9. Sliding the window over genuine actions only makes the selection channel entirely immune to targeted redundant-record deletion, at the price of decoupling; our experiments use the coupled default (Section 6). A window longer than one is equally admissible but widens the damage of each deletion from one group to the window length. Numerical verification. All distributional claims in this paper (Lemma D.1 (independence and marginals of the race), Theorem 5.1, Lemma D.4 (conditional CDF, digamma mean, trigamma variance), Corollaries D.5–D.6, Theorem 5.2 (including Lemma D.7 on a dense grid), Lemma D.2, Proposition D.10, Corollary D.8, Proposition D.9, Lemma D.3, and Proposition D.13) were additionally verified by Monte Carlo simulation; the script is included in the supplementary material. F. Additional Experimental Results This appendix records the per-split detection values, per-seed raw values, the backbone ablation, the full baseline-robustness tables, and the calibrated-FPR detection-power tables behind Section 6. Table 5 maps the split labels used throughout to the benchmarks’ native identifiers. All values are mean±sample standard deviation over three seeds unless marked. The per-task utility breakdown appears in Table 2; further per-seed raw values are included in the supplementary material. F.1. ToolBench Detection per Split 36 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 5 | Split labels and the benchmarks’ native identifiers. Label ToolBench splitLabel ALFWorld task type T1 G1_categoryA1 pick_and_place T2 G1_instructionA2 pick_clean_then_place T3 G1_tool A3 pick_heat_then_place T4 G2_categoryA4 pick_cool_then_place T5 G2_instructionA5 look_at_obj_in_light T6 G3_instruction A6 pick_two_obj_and_place ID = valid_seenOOD = valid_unseen Table 6|ToolBench detection per split: RG single-layer푧and Trace per-channel푧, each with its wrong-key control. Split RGTrace 푧wkSel. 푧Tally 푧wk sel.wk tally T10.65±0.92 0.62±0.893.78±0.23 5.12±0.40 −0.30±0.41 0.19±0.40 T21.87±0.34 −0.46±0.615.40±2.16 5.32±0.29 1.07±0.95 1.29±0.69 T33.04±0.23 −1.77±0.966.03±0.44 5.44±0.37 −0.10±0.54 1.42±0.55 T44.32±0.81 −1.70±1.082.10±2.00 5.54±0.70 −0.35±0.25 −0.44±0.51 T54.23±0.18 −0.04±0.026.72±1.67 7.77±0.04 −1.66±0.48 0.64±0.23 T6 2.23±0.53 −1.94±0.663.04±0.57 5.41±1.06 0.37±0.36 −0.54±0.37 Mean over splits2.72 −0.884.515.77 −0.160.43 F.2. ALFWorld per Seed Table 7 | Trace ALFWorld per-seed values behind the headline aggregates. Split SR (%)Sel. 푧 seed 1 seed 2 seed 3seed 1 seed 2 seed 3 ID (valid_seen)85.7 80.7 84.387.5 99.6 95.3 OOD (valid_unseen)85.8 79.9 77.695.4 106.4 105.8 F.3. Redundant-Record Accounting Table 8 itemizes the redundant records behind the Trace step counts of Table 2: per task, the decision steps the agent actually takes, the redundant records the tally channel appends, and their total, for every benchmark split and both backbones. The volume scales with trajectory length, about half a record per decision group on ToolBench and eleven to fifteen records per task on ALFWorld horizons, and the records disturb neither the semantic content of the log nor the task’s execution (Definition 4.1): the decision-step column tracks Base throughout, so the accounting confirms that the entire step overhead in Table 2 is watermark records rather than agent work. 37 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 8|Redundant-record accounting for Trace per task: decision steps, appended redundant records, and total logged steps (†: difference of the two measured columns). SettingDecision steps Redundant recordsTotal ToolBench T11.32±0.210.48 † 1.80±0.22 ToolBench T21.42±0.150.51 † 1.93±0.13 ToolBench T3 1.48±0.200.89 † 2.37±0.34 ToolBench T41.55±0.400.85 † 2.40±0.66 ToolBench T51.21±0.010.60 † 1.81±0.05 ToolBench T6 1.50±0.590.85 † 2.35±0.90 ToolBench Avg.1.37±0.090.68 † 2.05±0.16 ALFWorld ID23.15±1.7311.04±0.8534.19±2.58 ALFWorld OOD24.80±1.4211.85±0.7136.65±2.13 ALFWorld ID (Qwen)30.28±0.1714.68±0.1544.96±0.28 ALFWorld OOD (Qwen)29.15±0.2413.82±0.1542.97±0.39 F.4. Backbone Ablation (Local Qwen under vLLM) The second backbone is a locally deployed Qwen3-4B-Instruct model served with vLLM. The ablation runs ALFWorld only: a ToolBench decision presents dozens of candidate tools at once, more than a 4B-parameter backbone can reliably discriminate among, so that benchmark is uninformative at this model scale. On ALFWorld the baselines transfer: RG reaches푧=38.16±0.98 (ID) and 35.63±0.75 (OOD) with wrong-key controls near zero, AM-F recovers 56.05 and 54.98 bits per task, and the qualitative utility picture matches the main backbone, RG paying the largest cost while the distribution-preserving arms stay near Base (Tables 9 and 10). Trace itself transfers as well, reaching SR 63.8±0.4 (ID) and 67.2±1.3 (OOD), 3.1 and 4.3 points above RG on the same backbone and task subsets: the distortion-free advantage is even more visible at the 4B scale, where the model tolerates less interference with its sampling. Its step counts again include the tally channel’s redundant records, 14.7 (ID) and 13.8 (OOD) per task at this backbone’s lower success rate, where failed episodes run to the 50-step cap; net of them the decision path runs 30.3 and 29.2 steps against Base’s 30.5 and 30.8, at parity here as on the main backbone. Detection reaches selection푧=90.21 (ID) and 93.88 (OOD) with the tally at 62.96 and 60.44, and all wrong-key controls stay far from the threshold. Table 9|Qwen backbone, ALFWorld utility (†:푛-weighted mean over task types; Trace steps include the tally channel’s redundant records). Arm SR (%)↑Steps / task IDOODIDOOD Base64.5±0.8 62.9±2.330.5 † 30.8 † AM-F 67.4±0.8 66.9±5.229.7 † 29.5 † RG60.7±3.8 62.9±0.431.7 † 31.3 † Trace63.8±0.4 67.2±1.345.0±0.3 43.0±0.4 38 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 10 | Qwen backbone, ALFWorld detection. SettingRG 푧↑RG wkTrace Sel. 푧↑ Trace Tally 푧↑AM-F bits/task↑ ALFWorld ID38.16±0.98 0.15±0.3590.21±2.0062.96±0.1756.05±1.93 ALFWorld OOD35.63±0.75 0.46±0.9193.88±2.0560.44±0.3154.98±4.82 F.5. Baseline Robustness in Full Table 11 | RG and AM-F under the deletion sweep on ToolBench (15 runs per rate). Deletion rateRG 푧 AM-F 푧 AM-F bit acc. AM-F RLNC succ. 0.07.09 15.851.000.56 0.16.58 14.981.000.54 0.25.61 14.121.000.56 0.3 5.07 13.151.000.52 0.44.74 11.971.000.47 0.54.27 11.261.000.49 0.63.20 10.101.000.46 0.72.80 8.671.000.24 Table 12 | RG and AM-F under the rewriting sweep on ToolBench (9 runs per strength). Substitution 푞RG 푧 AM-F 푧 AM-F bit acc. AM-F RLNC succ. 0.07.09 15.851.000.56 0.25.39 13.990.950.44 0.43.79 11.560.880.20 0.61.33 1.470.550.04 0.80.60 −1.620.440.00 1.00.29 −4.040.340.00 Table 13|RG and AM-F under the combined attack on ToolBench: detection푧at deletion rate푟and rewriting strength 푞 (nine runs per cell). Arm, rate풒=0.0풒=0.2풒=0.4풒=0.6풒=0.8풒=1.0 RG, 푟= 0.35.16 4.38 3.38 1.91 1.68 1.37 RG, 푟= 0.5 4.29 3.37 2.70 2.32 1.45 0.41 RG, 푟= 0.72.93 2.35 2.15 0.62 0.74 0.48 AM-F, 푟= 0.313.07 11.90 10.02 1.70 −0.54 −3.12 AM-F, 푟= 0.511.27 9.98 8.10 1.72 −0.78 −2.69 AM-F, 푟= 0.76.05 6.06 5.56 −0.74 −1.25 −2.11 F.6. Detection Power at Calibrated FPR Protocol. Positives are watermarked trajectories scored under the true key; negatives are the same trajectories scored under the wrong key (99990001/99990002). For clean detection,퐵trajectories 39 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories are pooled into one bundle statistic푧 bundle =( Í 푋 − Í 퐸)/ √︁ Í 푉 , and TPR@푥%FPR is the fraction of positive bundles exceeding the(1−푥%)quantile of the negative bundles (5000 bootstrap resamples). For detection under attack, each attack cell already pools 118 to 127 trajectories into one푧, so one cell is one fixed-size bundle; TPR@1%FPR is the fraction of cells above휃 1% =2.326, the one-sided Gaussian 1% threshold, which the wrong-key per-cell푧calibrates (granularity 1/15 per deletion strength, 1/9 otherwise). Grand-pooled wrong-key selection scores sit slightly below zero (about −0.06 to−0.10 per group), the harmless side of a one-sided upper-tail test; TPR thresholds are taken from the null’s own quantiles, so the shift cannot inflate false positives. Table 14|Clean detection power: single-trajectory AUC and TPR at 1% FPR for bundle sizes퐵 ∈ 1, 10, 50. SettingScheme / channelAUC (퐵=1)퐵=1 퐵=10 퐵=50 ToolBench Trace selection0.7110.080 0.618 1.000 Trace tally0.8020.083 1.000 1.000 RG 0.6500.030 0.563 1.000 AM-F0.8820.130 1.000 1.000 ALFWorld ID Trace selection0.9740.874 1.000 1.000 Trace tally0.9850.850 1.000 1.000 RG0.9330.562 1.000 1.000 ALFWorld OOD Trace selection0.9950.938 1.000 1.000 Trace tally0.9950.860 1.000 1.000 RG0.9000.563 1.000 1.000 Table 15 | Single-trajectory (퐵= 1) TPR at three FPR levels. SettingScheme / channel@5% @1% @0.1% ToolBench Trace selection0.260 0.080 0.051 Trace tally0.147 0.083 0.033 RG 0.075 0.030 0.030 AM-F0.227 0.130 0.082 ALFWorld ID Trace selection0.924 0.874 0.648 Trace tally0.930 0.850 0.786 RG 0.721 0.562 0.351 ALFWorld OOD Trace selection 0.979 0.938 0.865 Trace tally0.959 0.860 0.826 RG0.677 0.563 0.457 40 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Table 16 | TPR at 1% FPR under single-axis attacks (ToolBench; bundle-level, see protocol). 푟Sel. Tally RG AM-F푞Sel. Tally RG AM-F 0.01.000 1.000 1.000 1.0000.01.000 1.000 1.000 1.000 0.1 1.000 1.000 1.000 1.0000.21.000 1.000 1.000 1.000 0.21.000 1.000 1.000 1.0000.41.000 1.000 1.000 1.000 0.31.000 1.000 1.000 1.0000.60.000 1.000 0.333 0.111 0.4 1.000 0.867 1.000 1.0000.80.000 1.000 0.000 0.000 0.51.000 0.267 1.000 1.0001.00.000 1.000 0.000 0.000 0.61.000 0.000 0.933 1.000 0.70.933 0.000 0.733 1.000 Table 17 | TPR at 1% FPR under the combined attack (ToolBench; nine cells per (푟, 푞)). 푟 푞Trace Sel. Trace Tally RG AM-F 0.3 0.01.0001.0001.000 1.000 0.3 0.2 1.0001.0001.000 1.000 0.3 0.40.8891.0000.889 1.000 0.3 0.6 0.0001.0000.333 0.222 0.3 0.8 0.0001.0000.111 0.000 0.3 1.0 0.0001.0000.000 0.000 0.5 0.01.0000.4441.000 1.000 0.5 0.21.0000.4440.889 1.000 0.5 0.40.7780.4440.778 1.000 0.5 0.6 0.0000.6670.556 0.222 0.5 0.80.0000.2220.111 0.000 0.5 1.0 0.0000.3330.000 0.000 0.7 0.01.0000.0000.778 1.000 0.7 0.2 0.8890.0000.556 1.000 0.7 0.40.6670.0000.444 1.000 0.7 0.60.0000.0000.111 0.000 0.7 0.8 0.0000.0000.000 0.000 0.7 1.00.0000.0000.111 0.000 41

Instant research discovery