Semantic Behavioral Watermarking: Paraphrase-Robust and Forgery-Resistant Provenance for LLM Agents

What it is

Semantic Behavioral Watermarking (SBW), from Ji, Wan, Chen, and Zhang (ICLR 2027 submission), is a training-free watermark for LLM agent trajectories: a frozen sentence encoder (bge-base) clusters tool/action embeddings via k-means, and a keyed PRF marks "green" steps over cluster symbols plus a history window (SeqWM-style), rather than exact action strings.

How it works

Binning is keyed: bin(a) = H(sk, quantize(R_sk · E(a))), where R_sk is a secret random projection to r hyperplanes — orthogonal to the public embedding geometry, so an adversary with only the public encoder can't recover which clusters are green. During generation, with green bias probability p=0.95, a step is resampled from green candidates (support-restricted, not distribution-preserving). Detection is a permutation test (M=300 wrong keys) scoring green windows over the observed cluster-symbol stream. History window length w is a tunable tradeoff: w=1 is used by default because it favors deletion robustness over clean detection (clean detection 0.83/0.91/0.98 for w=1/2/3, but deletion-robustness TPR at 30% deletion drops to 0.48/0.31/0.24 as w grows). Boundary actions near a cluster margin are routed to an abstain state rather than decoded, trading capacity for near-zero bit error.

Preconditions / Affected

Applies to agent architectures where ownership must be proven from discrete tool-call choices, not output tokens. Tested on 5 models (3B–14B: Qwen2.5-3B/7B, LLaMA-3.2-3B, Mistral-7B, phi-4) across ToolBench (600 trajectories) and ALFWorld (100 episodes). Requires the owner to control generation-time decoding and a fixed elicitation operator — the paper notes capacity is undefined without fixing this (two elicitation methods correlated at only 0.13 in per-step entropy).

What to do

Key quantitative thresholds from the paper for anyone evaluating or reproducing this:

• Detection under rewriting (TPR @ 1% FPR): cluster-level 0.49–0.66 vs exact-symbol 0.05–0.17 on ToolBench; 0.92–0.97 vs 0.00–0.01 on ALFWorld.
• Utility cost: choice agreement 72–83% (SBW) vs 22–27% (KGW-style logit biasing) against no-watermark argmax.
• Capacity cost: clustering at k=100 retains only 41.9–50.1% of tool-level entropy — the explicit price of paraphrase robustness.
• Forgery resistance: keyed binning drops adaptive forgery from 100% to ~21% at r=8, and to 1.2% (the FPR floor) at r=64 — raising projection dimension r is the concrete lever.
• Payload sizing: recovering a 128-bit ID needs T≥422 steps at their calibrated capacity/error rates — relevant for deciding episode/corpus aggregation granularity.
• Code: anonymous.4open.science/r/SBW-Agent-Watermark.

Caveats

The paper explicitly flags chained-replay forgery (adversary replays the victim's own steps in sequence) as unsolved: it succeeds 0.76–0.98 of the time across all five models, versus shuffled-splicing replay which SBW neutralizes (0.000 on Qwen2.5-3B). The fresh-bucket forgery guarantee (Thm. G.1) is provable only when the adversary's actions land in unobserved keyed buckets — not when buckets are already observed (~98% of fresh actions at r=8, per their own measurement). Mistral-7B was pre-registered as a fourth-vendor validation model and returned the highest score of the five, which the authors flag as a reason to weight that result carefully rather than cherry-pick it.