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

arXiv: https://arxiv.org/abs/2610.08668 · HTML: https://mlsanity.com/paper/2610.08668/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 20 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)
- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 20 of 20)

- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [APIGen: Automated Pipeline for Generating Verifiable and Diverse Function-Calling Datasets](https://mlsanity.com/paper/2406.18518/) (2024)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [xLAM: A Family of Large Action Models to Empower AI Agent Systems](https://mlsanity.com/paper/2409.03215/) (2024)
- [Watermark Stealing in Large Language Models](https://mlsanity.com/paper/2402.19361/) (2024)
- [k-SemStamp: A Clustering-Based Semantic Watermark for Detection of Machine-Generated Text](https://mlsanity.com/paper/2402.11399/) (2024)
- [Tool-Planner: Task Planning with Clusters across Multiple Tools](https://mlsanity.com/paper/2406.03807/) (2024)
- [MemMark: State-Evolution Attribution Watermarking for Agent Long-Term Memory Systems](https://mlsanity.com/paper/2605.25002/) (2026)
- [Agent Guide: A Simple Agent Behavioral Watermarking Framework](https://mlsanity.com/paper/2504.05871/) (2025)
- [AgentMark: Utility-Preserving Behavioral Watermarking for Agents](https://mlsanity.com/paper/2601.03294/) (2026)
- [On Protecting Agentic Systems' Intellectual Property via Watermarking](https://mlsanity.com/paper/2602.08401/) (2026)
- [PASA: A Principled Embedding-Space Watermarking Approach for LLM-Generated Text under Semantic-Invariant Attacks](https://mlsanity.com/paper/2605.10977/) (2026)
- [Sequential Behavioral Watermarking for LLM Agents](https://mlsanity.com/paper/2605.11036/) (2026)
- [Watermarking LLM Agent Trajectories](https://mlsanity.com/paper/2602.18700/) (2026)
- [When Only the Final Text Survives: Implicit Execution Tracing for Multi-Agent Auditing](https://mlsanity.com/paper/2603.17445/) (2026)
- [SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation](https://mlsanity.com/paper/2310.03991/) (2023)

## Abstract (arXiv)

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'c 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.