Session-Bound Behavioral Watermarking for Autonomous LLM Agents

What it claims

AgentAnchor watermarks LLM agent action choices so that an owner can later attribute a trajectory log. It also tries to stop observers who read many watermarked logs from forging new trajectories that verify as the owner's. The authors' central argument is that prior agent watermarks key on context that recurs across runs: AgentMark uses the step index, SeqWM and TRACE use previous actions, and TrajMark uses file names. Recurring context makes keyed preferences learnable from public logs. Binding each step key to a fresh public session identifier is meant to prevent that transfer. Evaluation covers ALFWorld (50 tasks) and the 1,000-product WebShop subset (WebShop-1K).

How it works

• Action distribution. Each admissible action is scored by its length-normalized token log-likelihood under the agent's own model. The prompt includes the goal, the current observation, the last eight steps, and a short ReAct-style planning note. This requires an enumerable action set. Free-form WebShop search text is generated greedily without the key and becomes the only admissible action.
• Step key. An HMAC over the secret key, a 128-bit session ID, and semantic clusters of recent observations. The ID must be unique but need not be secret. Semantic clusters make the key independent of step numbering and tolerant of moderate rewording.
• Coding row. A perturbation-tolerant digest of the most probable actions selects a random linear coding row, borrowed from AgentMark, which yields one parity bit of an 8-bit owner payload (256 identifiers).
• Embedding. A KL-bounded exponential tilt, borrowed from SeqWM, pushes the distribution toward one half of a keyed action split. Unlike AgentMark, TRACE and MemMark, this tilt does not preserve the action distribution.
• Logging. Every record stores the observation, the admissible set, a fixed-point copy of the action distribution, the chosen action and the session ID. It does not store the key or the planning notes.
• Verification. The verifier recomputes keys from the log and decodes the payload. It calibrates the evidence against many wrong keys and returns one of three outcomes: unique attribution, detection of a pre-named owner, or abstention.

Evidence

The paper gives one forgery result, from a post-hoc ALFWorld replay. An attacker observed 200 watermarked logs and rewrote 50 unwatermarked trajectories. The table shows how many of those 50 forgeries passed claimed-owner detection and how many were attributed to the owner:

The authors also report that deliberately reusing a session restores transferable, forgeable behavior. The fetched text lists the removal attacks tested, including renumbering, paraphrasing, round-trip translation, probability perturbation, step erasure, reordering and session replacement. It cuts off in Section 3 before any removal results, detection rates or task-success numbers.

Limits

• Session IDs must be fresh and authentic, for example issued by the verifier or gateway. AgentAnchor does not authenticate logs or prevent replay.
• A missing or malformed session ID causes abstention. A different but valid ID is treated as a separate session.
• Genuine-log attribution trusts the logged probabilities. Probability edits were tested only empirically.
• Anyone holding the key can forge any payload, so all key holders must be honest.
• The adversary has no oracle access to the verifier.
• The forgery results cover only the implemented attackers.
• The method changes agent behavior. Its effect on task success does not appear in the fetched text.