Summary
Tracking who created the actions of language model agents is tricky because changes like paraphrasing or renaming tools can break existing methods that mark the agent's behavior. The authors propose a new way called Semantic Behavioral Watermarking, which groups similar actions and uses a secret method to assign them into bins, making the watermark both hard to remove and hard to fake. They tested this approach on several language model agents and found it detects watermarks reliably even when the input is changed. However, copying and slightly rearranging the exact same actions can still trick the watermark, and making it robust costs some capacity.
What this means in practice
- •For ai product teams: Protect ownership and verify source of LLM agent behaviors even when inputs are paraphrased or tools renamed, reducing false identifications.$Commercial implications: Enables companies to offer provenance verification services for AI agents that resist tampering and forging.
- •For security engineering teams: Detect unauthorized copying or splicing of an LLM agent's action sequences to identify misuse or impersonation attempts.
Authors
Suxin Ji, Hungtao Wan, Shaoxuan Chen, An Zhang
Abstract
Behavioral watermarking embeds an owner identifier in an LLM agent's high-level action choices, giving provenance without touching output tokens. Prior agent watermarks break in two ways. First, all three prior schemes bind the watermark to the exact action symbol, so renaming a tool desynchronizes decoding even when the observation is untouched; in AgentMark's own robustness test, paraphrasing the observation alone drops bit-recovery to 16.8%. Second, every prior agent watermark studies only removal: none asks whether an adversary can forge a trajectory that verifies as someone else's, a question answered affirmatively for text watermarks (Jovanović et al., 2024). We present Semantic Behavioral Watermarking (SBW): watermarking over semantic action clusters under history conditioning, with the public-cluster bin replaced by keyed collision-resistant binning whose fresh-bucket assignment is provably unpredictable in the random-oracle model. Across five agent models (3B-14B, four vendors) and three encoders the ordering holds on both benchmarks: on ToolBench (600 trajectories per model) detection under rewriting is 0.49-0.66 for cluster-level versus 0.05-0.17 for exact-symbol at a permutation-calibrated 1% FPR, at 72-83% choice agreement against 22-27% for logit biasing; on ALFWorld (100 episodes per model) it is 0.92-0.97 versus 0.00-0.01. Keyed binning takes adaptive forgery from 100% to the false-positive floor at the primary operating point (bge, r=64). We also mark the boundary that guarantee does not cover: when the adversary copies the victim's own steps, shuffled splicing is neutralized (0.000 on Qwen2.5-3B) but chained replay remains at 0.76-0.98 across the five models, reported as open. Paraphrase robustness costs about half of the per-step watermark capacity. Code is available at https://anonymous.4open.science/r/SBW-Agent-Watermark.