Researchers present TRACE, the first agent watermark that is distortion-free in action choices, self-synchronizing under deletion, and unconditionally invariant under rewriting. This addresses the challenge of attributing provenance when resellers may rebrand or substitute models, as existing watermarks fail to survive adversarial access to trajectory logs.
- TRACE superposes a selection channel keyed on local content for distortion-free sampling and a tally channel keyed on the log's skeleton for rewrite invariance.
- The watermark signal is bounded by decision entropy, with each decision paying at least half its entropy.
- On ToolBench and ALFWorld, TRACE matches the unwatermarked agent's success rate while maintaining detection scores near z = 100 on long-horizon trajectories.
- The selection channel remains detectable under 70% step deletion, and the tally channel stays exactly unchanged under LLM rewriting of any strength.
Erasing both channels forces resellers to corrupt the trajectories they resell, ensuring that attribution cannot be removed without altering the evidence itself.