TrajMark: 95.5–100% Tamper Detection for Agent Trajectories

Every coding agent leaves a trail: the READs, edits, and tool calls that produced the patch. Enterprises increasingly need to prove whose agent produced a trajectory — and where it was edited afterward. Prior behavioral watermarking gives you a global yes/no signal. A new preprint, TrajMark, splits the problem in two and reports 95.5–100% detection of exhaustive single-site edits, 95.8% localization of random corruption to the right protocol region, exact owner recovery in every clean batch — and a pooled Pass@1 of 26.9% vs 26.3% unwatermarked. That last number is the quiet headline: the whole apparatus is essentially free at task-success level.

The Problem: Provenance Without a Map

Watermarking the final patch authenticates the artifact, not the process. Two different trajectories can yield the same patch, and a trajectory can be edited without touching the patch at all. Behavioral watermarking methods (AgentMark, AGENTWM, ActHook) detect that a trajectory was marked, but when a local edit breaks the evidence, they can't tell you which region went inconsistent — a global detector gives no forensics. For audit workflows (insurance, regulated dev, incident response), "something changed" without "what and where" is nearly useless.

The Method: Two Channels, Two Lifetimes

TrajMark is training-free, symmetric-key, and operates only on the visible action stream — no logits, no hidden state. It decouples two requirements with opposite robustness needs:

• Owner layer (robust). A six-bit deployment ID is encoded by rewriting a keyed, sparse subset of READ actions the agent already intended to run into masked linear equations embedded in the requested file contents. Zero added actions. Evidence accumulates across the trajectory, so deletion-resistant decoding with a three-way decision (accept/abstain/reject) survives corruption.
• Integrity layer (fragile, by design). Linked "seals" — ordinary, group, and terminal commitments keyed with HMACs over ordinal, payload, and preceding observation — are interleaved around protected critical-action segments. Fragility is a feature: any local edit perturbs the nearby commitment, exposing the affected protocol region.

graph LR
    T["Coding-agent trajectory"] --> W["Keyed wrapper"]
    W --> O["Owner layer
6-bit ID in sparse READs
robust, zero added actions"]
    W --> I["Integrity layer
ordinary/group/terminal seals
fragile, tamper-evident"]
    O --> V["Verifier (holds key)"]
    I --> V
    V --> R1["Owner: accept / abstain / reject"]
    V --> R2["Localization: which segment broke"]
            

The verification input is a versioned canonicalization of public records only, so replay works from the released stream alone.

The Results

• Ownership: exact 6-bit owner recovered in 100% of clean full-watermark batches across three agent frameworks (SWE-agent, OpenHands, OpenDev) and three LLMs (DeepSeek V4 Flash, GPT-5 mini, MiniMax M3).
• Detection: 95.5–100% of exhaustive eligible single-site edits caught by the integrity layer.
• Localization: 95.8% of randomly corrupted actions localized to the accepted protocol region.
• Utility: pooled Pass@1 26.9% (TrajMark) vs 26.3% (No-WM) over 1,350 task runs; sign test p = 1.00. The owner layer adds no trajectory actions; only the integrity layer adds read-only seals.

The comparison table carries the sharpest finding: AgentMark-U — the closest behavioral baseline — craters Pass@1 to 18.4% pooled (−7.9pp), including a −23.3pp collapse on GPT-5 mini / SWE-agent. TrajMark's structural carriers (rewriting real READs rather than steering action probabilities) cost +0.6pp. The design choice isn't just aesthetic; it's the difference between watermarked and functional.

Limitations — Some the Authors Bury

The threat model is honest but narrow. This is symmetric-key inside a trusted domain: anyone holding K can forge any label, there is no public verifiability and no non-repudiation. A dishonest embedding service or verifier defeats it entirely. It's tamper-evident, not tamper-proof — and the keyless adaptive adversary (an attacker who learns the carrier scheme from repeated releases and verifier feedback) is explicitly not evaluated.

Two more things worth flagging that the abstract doesn't say: under white-box carrier deletion, OpenHands detection floors at 84.8% — because OpenHands joins an action to its observation as one deletable atom, letting a critical action and its adjacent seal vanish together. Detection topology is adapter-dependent, so your framework choice changes your security margin. And localization granularity is the protocol region, not the individual action — 95.8% means "which segment," not "which keystroke."

Why Builders Should Care

If you ship coding agents into audited environments, trajectory provenance is coming for you the way SBOMs came for dependencies. TrajMark's blueprint is directly reusable: separate your robust channel from your fragile one. Robust attribution (who ran this) and fragile integrity (was this edited) have opposite failure requirements, and bolting them together is why prior behavioral watermarks give detection without forensics. The second lesson: prefer structural carriers over generation steering — rewriting actions the agent was going to take anyway cost ~0 utility, while probability-steering baselines lost up to 23pp of task success. Pair this with patch watermarks, not instead of them: the paper's own argument is that artifact and process provenance are complementary because the same patch can come from many trajectories.