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

What it claims

SBW watermarks an LLM agent's tool choices over semantic clusters rather than exact tool names, so renamed or paraphrased tools still decode to the same symbol. A keyed binning step is meant to stop an adversary from forging trajectories that verify as someone else's.

• Paraphrase robustness: Detection under rewriting is 0.49–0.66, against 0.05–0.17 for the exact-symbol SeqWM baseline.
• Forgery resistance: Fresh-action forgery falls from 100% to about 21% at the default r=8 projection hyperplanes, and to 1.2% at r=64, which is the false-positive floor.
• Cost: Paraphrase robustness costs about half of per-step watermark capacity.
• Training: The method is entirely training-free. It uses no gradient steps and no learned watermark parameters.

How it works

1. Encode and cluster. A frozen sentence encoder (bge-base in the main runs) embeds each action. One k-means pass groups the actions, with k=100 over the 2,128 unique ToolBench tools.
2. Mark green steps. Step t is green if PRF(sk, c_t, s_t) = 1. Here s_t is the current cluster symbol and c_t is the previous w cluster symbols, giving SeqWM-style history conditioning over clusters.
3. Generate. The owner elicits an explicit action-weight distribution at each step. - With probability p_green = 0.95, the agent resamples from the green candidates in proportion to their elicited mass. - Otherwise, or when no candidate is green, it falls back to the unwatermarked argmax, and that step carries no bit. - The bias stays within the actions the agent already admitted, but it is not distribution-preserving in AgentMark's sense.
4. Key the binning against forgery. bin(a) = H(sk, quantize(R_sk · E(a))). R_sk is a secret random projection to r hyperplanes, so the bins no longer follow the public embedding geometry.
5. Abstain on boundary actions. Actions with a small cluster margin go to an abstain state. They carry no bit but keep the decoder synchronized.
6. Detect. A random-key permutation test (M=300 wrong keys) scores the number of green windows.

Window length w is a deployment trade-off. Tested at w = 1 / 2 / 3:

The paper uses w=1, the deletion-robust end.

Evidence

Setup:

• ToolBench: 600 tasks (100 from each G1/G2/G3 sub-split) per model, run in a bounded ReAct loop.
• ALFWorld: 100 episodes per model.
• Models: Qwen2.5-3B, LLaMA-3.2-3B, Qwen2.5-7B, Mistral-7B and phi-4 (14B).
• Metric: TPR at a permutation-calibrated 1% FPR, averaged over 5 seeds.

Results:

• ToolBench, paraphrase: CLUSTER scores 0.49–0.66 against 0.05–0.17 for EXACT.
• ALFWorld: CLUSTER scores 0.92–0.97 against 0.00–0.01 for EXACT.
• Pure deletion: EXACT does better. SBW trades deletion margin for paraphrase robustness. Only CLUSTER keeps meaningful detection under paraphrase plus deletion.
• Utility: Choice agreement with the unwatermarked argmax is 0.72–0.83 for SBW, against 0.22–0.27 for KGW-style logit biasing.
• Held-out tools: Open-set κ is 0.808 on every model.
• Capacity: Real per-step entropy is 1.32–1.99 bits, and tool-level capacity is 1.01–1.51 bits/step. Clustering at k=100 keeps 41.9–50.1% of it. phi-4 reaches 0.49 paraphrase detection with the lowest capacity of the five models.
• Payload budget: Recovering a 128-bit ID needs at least 422 steps, using the calibrated C=0.632 and ρ=0.117. Short episodes therefore require aggregation across a corpus: the experiments use documents of 20 trajectories each.
• Pre-registration: Mistral-7B was pre-registered as the fourth-vendor model and produced the highest results. The authors report ranges rather than peaks.

How to use it

The code is at an anonymous review link: https://anonymous.4open.science/r/SBW-Agent-Watermark.

Requirements stated in the paper:

• Control of generation-time decoding.
• The ability to elicit an explicit per-step action distribution from the agent.

Limits

• Replay is not covered. Chained replay of the victim's own steps still evades detection at 0.76–0.98 across the five models. Shuffled splicing is neutralized (0.000), but that was measured only on Qwen2.5-3B.
• The proof covers only unseen buckets. About 98% of fresh actions at r=8 fall into buckets the attacker has already observed. In that regime the only evidence is the empirical drop to about 21%. The script that produced that 98% figure was not retained.
• Policy flips are out of scope. Changes such as explore→grab alter task semantics and are not claimed to be detected.
• Capacity depends on how the distribution is elicited. Two elicitation methods gave per-step entropies correlating at only 0.13. Capacity figures hold only for the elicitation operator used.
• Deterministic policies carry no capacity, so they cannot be watermarked this way.
• Unexplained mechanism. The authors have not isolated why detection does not track policy entropy.
• Review status. The paper is under review at ICLR 2027, and the code is hosted at an anonymous review link.