acceptodds
Under review as a conference paper at ICLR 2027

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

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 bind the signal to raw strings and break in two ways. AgentMark's own robustness test paraphrases the observation alone and bit-recovery falls to 16.8%; its released script holds the per-step key fixed, so that experiment measures distribution drift, not the key desynchronization its context-hash design separately admits. All three prior schemes also bind the watermark to the exact action symbol, so renaming a tool desynchronizes decoding even when the observation is untouched — the axis we measure and close. And 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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
behavioral watermarking, LLM agents, provenance, forgery resistance, paraphrase robustness, semantic clustering, tool use, model IP protection

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_NEecOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Semantic Behavioral Watermarking (SBW), which maps agent actions into semantic clusters and embeds behavioral watermarks using history-conditioned encoding to improve robustness against tool renaming and semantic rewriting. In addition, the authors employ keyed random projection and binning to mitigate watermark forgery attacks and provide theoretical analyses of watermark stability and capacity. Experiments on ToolBench and ALFWorld demonstrate the effectiveness of the proposed approach.

Critical strengths
  1. The paper investigates semantic rewriting robustness and forgery resistance in agent behavioral watermarking, addressing research problems of potential significance.

  2. The proposed method requires no additional model training, making it relatively straightforward to implement.

  3. The experiments cover multiple models, semantic encoders, and datasets, with additional analyses of the trade-offs among watermark capacity, robustness, and forgery resistance.

Critical weaknesses
  1. Limited realism of the threat model. The proposed method assumes that the verifier can access the agent's execution trajectories. However, commercial agent APIs typically only need to return final results. An adversary could simply hide internal tool calls and execution traces, making behavioral watermark detection impossible. The paper does not adequately justify the practical scenarios in which this assumption holds.

  2. Insufficient justification for behavioral watermarking. If the objective is to verify agent ownership, why not embed the watermark directly into the final output? Compared with output-level watermarking, behavioral trajectory watermarking introduces additional complexity and potential performance degradation, yet the paper lacks sufficient comparisons or justification for this design choice.

  3. Limited methodological novelty. Semantic clustering-based watermarking, history-conditioned encoding, and keyed random mapping have all been explored in prior research. The proposed method primarily combines and adapts these existing techniques to the agent setting, without demonstrating substantial new methodological insights.

Questions for authors
  1. In practical commercial agent API scenarios, why is it reasonable to assume that the verifier can access internal execution trajectories? How would SBW function if an adversary only returned the final execution results?

  2. What are the irreplaceable advantages of behavioral trajectory watermarking over directly embedding watermarks into the agent's final outputs? Could the authors provide comparative experiments or concrete application scenarios to justify this choice?

2 comments

Response to Reviewer NEec — Part 1/2

We thank the reviewer for the careful assessment and for recognizing the importance of studying both semantic rewriting and forgery, the training-free design, and the evaluation across models, encoders, and benchmarks. We appreciate the concerns about deployment assumptions, the motivation for behavioral watermarking, and methodological novelty. We clarify the scope and evidence already provided in the submission below.

1. When are execution trajectories available?

We agree that SBW cannot verify an agent from its final answer alone. Our threat model in Section 3 explicitly assumes that the verifier observes an action trajectory. This is an access requirement, not a claim that all commercial agent APIs expose their internal traces.

The intended use cases are settings where tool-call or workflow traces are retained and made available to an authorized verifier, for example: (i) enterprise deployments with audit logs; (ii) agent platforms where tool invocations are logged for monitoring or compliance; and (iii) shared or transferred agent workflows where the trajectory itself is the object whose provenance is checked. These are examples of deployment settings, not settings we claim to have evaluated end-to-end.

If a third-party service returns only a final response and neither the verifier nor a trusted logging service can access the underlying actions, SBW is not applicable. We agree that this limits deployment coverage. Our claim concerns provenance of observable agent behavior, not ownership verification for arbitrary black-box APIs.

2. Why watermark behavior rather than only the final output?

The two approaches verify different artifacts. An output watermark can provide evidence about a marked final response; it does not, by itself, identify the sequence of tool choices and intermediate actions that produced that response. Different agents can produce similar final answers while following different tool-use trajectories, and the same agent may express a final answer in many ways. For applications where the execution trace is retained and its provenance matters, behavioral watermarking targets information not represented by the final answer alone.

We do not argue that behavioral watermarking universally replaces output watermarking. They are complementary: output watermarking is more appropriate when only the final text is observable; behavioral watermarking is relevant when the action sequence is available and is itself the provenance target. This distinction is also why the introduction (Section 1) motivates ownership signals in discrete agent behavior rather than surface tokens.

We acknowledge that the current paper does not provide a matched experimental comparison with final-output watermarking. Such a comparison would address a broader deployment question, but it would not make the two methods interchangeable: they mark different objects and require different observations. The experiments in this submission establish robustness properties of the trajectory-level signal, not superiority over output-level methods.

Response to Reviewer NEec — Part 2/2

3. What is technically new beyond combining existing components?

We agree that semantic clustering, keyed pseudorandom functions, and history-conditioned watermarking are not individually new, and we do not rely on novelty of these primitives. The contribution is the construction and characterization of a semantic action-level watermark for multi-step agent trajectories, including the limitations that emerge in this setting.

First, Section 4.1 changes the watermark symbol and its conditioning history from exact action strings to semantic-cluster symbols. This addresses a specific synchronization failure under tool renaming: both the current symbol and the history used for verification can change under a semantics-preserving rewrite. Section 6.1, Table 2 shows paraphrase detection of 0.49–0.66 for CLUSTER versus 0.05–0.17 for the exact-symbol baseline on ToolBench across five agent models; Section 6.4, Table 5 shows 0.92–0.97 versus 0.00–0.01 on ALFWorld. These results are accompanied by measurable costs: clean detection and deletion robustness can be lower than the exact-symbol baseline (Table 2).

Second, Section 5 studies two constraints of this agent setting: synchronization stability under semantic displacement and watermark capacity under the elicited action distribution. The latter matters because watermarking cannot assume a freely selectable output token at each agent step. Section 6.1 reports that clustering at k=100 retains only 41.9–50.1% of tool-level capacity across the five models; this is a limitation, not an unqualified improvement.

Third, Sections 4.2 and 6.2 examine a forgery surface arising when the semantic representation is public. Keyed binning reduces the evaluated adaptive fresh-action forgery success, while the paper also reports attacks that remain effective: Table 3 gives chained-replay success of 0.763–0.980 across models. The fresh-bucket guarantee is explicitly narrower than general resistance to all forms of stealing or replay. Moreover, the robustness and forgery results use different operating configurations; we do not claim that a single high-dimensional keyed configuration has been jointly validated for both properties.

We therefore view the contribution as an agent-specific design, quantitative analysis of its robustness–capacity trade-offs, and a transparent examination of both successful and unsuccessful forgery defenses—not as the invention of clustering or PRFs.

We appreciate the reviewer's recognition of the problem's significance and the empirical breadth of the study. We agree that trajectory visibility limits where SBW can be deployed, and that output-level watermarking is preferable when only final responses are available. Within the explicitly stated trajectory-observable setting, however, we hope the reviewer will consider the demonstrated semantic-rewriting robustness, the analysis of agent-action capacity and synchronization, and the measured forgery boundaries as substantive contributions.

Reviewer_qCDEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Semantic Behavioral Watermarking (SBW) for LLM agents. It uses semantic action clusters and history-conditioned detection to improve robustness against action rewriting, and introduces keyed random-projection binning to mitigate forgery.

Critical strengths
  1. The paper addresses a meaningful problem by considering both watermark removal and identity forgery in agent trajectories.
  2. The paraphrase-robustness improvements are supported across multiple models and benchmarks.
Critical weaknesses
  1. The key concern is that no single configuration is shown to achieve both paraphrase robustness and forgery resistance: the main robustness results come from semantic-cluster watermarking, while the strongest forgery results come from keyed random-projection binning under a different configuration. Paraphrase robustness at high dimensionality (especially r=64) is not reported, and since stability under semantic clustering does not imply stability under random-projection quantization, a joint evaluation is needed to support the central claim.
  2. The advantage over existing methods with semantic re-identification remains unclear. Encoder-assisted AgentMark and AGENTWM achieve stronger results on several robustness metrics, although the evaluation settings are not fully comparable.
  3. Practical utility is evaluated mainly through action-choice agreement rather than task completion. Without environment-execution feedback on ToolBench, the impact on actual agent performance remains uncertain.
Questions for authors
  1. Could the authors evaluate paraphrase detection and forgery resistance using the same random-projection, history-conditioned configuration?
  2. Could the authors compare against encoder-assisted baselines under matched false-positive rates and utility constraints?
  3. Could the authors report task success rates with and without watermarking in an executable environment?
2 comments

Response to Reviewer qCDE – Part 1/2

We thank the reviewer for the careful assessment and for recognizing the importance of studying both watermark removal and identity forgery, as well as the consistent paraphrase-robustness results across models and benchmarks. We agree that the distinction between our evaluated configurations and the scope of our conclusions is important. We address the three concerns below using the results already reported in the submission.

1. Joint paraphrase robustness and forgery resistance

The reviewer raises an important point. Section 6.1 evaluates paraphrase robustness with the semantic-cluster, history-conditioned configuration (ToolBench: k=100, p_green=0.95, M=300), while Section 6.2 evaluates the keyed-binning forgery defense under a different operating point (ToolBench: k=60; ALFWorld: k=40; p_green=0.85, M=100). The r-sweep in Section 6.2 measures forgery success as the projection dimension increases, but does not report paraphrase-detection rates at r=64 under that same configuration.

We therefore agree that the reported experiments do not establish a single operating point simultaneously achieving the headline paraphrase-detection and forgery-resistance results. In particular, the semantic-cluster stability results in Section 5.1 concern the nearest-centroid assignment; they should not be read as a proof of paraphrase invariance for the keyed random-projection buckets in Section 4.2. We do not intend to infer that invariance from the clustering analysis.

What the current evidence does establish is more specific. First, the history-conditioned semantic-cluster representation substantially improves detection under action rewriting compared with exact-symbol history conditioning: on ToolBench, 0.49–0.66 versus 0.05–0.17 across five agent models (Table 2); on ALFWorld, 0.92–0.97 versus 0.00–0.01 (Table 5), at the stated permutation-calibrated 1% FPR. Second, in the separate fresh-action forgery setting, increasing the keyed projection dimension substantially reduces the evaluated adaptive forgery success; for ToolBench with bge at r=64, the reported rate is 0.012 (Section 6.2 and Appendix A). Third, Section 6.2 explicitly identifies copy-style attacks that remain effective, particularly chained replay (0.763–0.980 across models in Table 3).

These findings are independently meaningful, but the reviewer is correct that their simultaneous realization at one deployment configuration is not demonstrated by the present evaluation. We regard this as a limitation of the current evidence rather than a result that can be resolved by citing the separate experiments alone.

2. Comparison with semantic re-identification baselines

We agree that the encoder-assisted comparisons require careful interpretation. Table 4 explicitly reports that AgentMark benefits substantially from encoder-assisted re-identification: for example, at p=16, paraphrase detection increases from 0.633 without re-identification to 0.900 with it, and detection under paraphrase plus 30% deletion increases from 0.295 to 0.842. These values exceed the corresponding SBW CLUSTER results of 0.533 and 0.340. We do not claim that SBW dominates encoder-assisted AgentMark across all robustness metrics.

The comparison is also not a fully matched security–utility–detection comparison. As discussed in Section 6.3, AgentMark uses payload recovery, while SBW uses a permutation-test detector; the payload sizes and false-positive calibration differ. The encoder-assisted AGENTWM reimplementation similarly shows that semantic re-identification can restore strong paraphrase detection. These observations support a narrower conclusion: semantic re-identification is an important mechanism, not a benefit unique to SBW.

Our technical contribution is therefore not the general observation that an encoder can match rewritten action strings. It is the use of semantic action symbols as the watermarking unit in a history-conditioned agent trajectory, together with the synchronization-stability and capacity analyses (Section 5), the open-set and cross-action-space evaluations (Sections 6.1 and 6.4), and the explicit study of fresh-action and copy-style forgery boundaries (Section 6.2). We agree that a fully matched comparison against encoder-assisted baselines would be needed to establish superiority under a common utility and false-positive-rate budget, and we do not claim that such superiority has been demonstrated.

Response to Reviewer qCDE – Part 2/2

3. Practical utility and task completion

We agree that action-choice agreement is a proxy for behavioral preservation, not a substitute for task success. Section 6.1 reports agreement with the unwatermarked argmax, and Section 7 explicitly states that the ToolBench rollouts do not include environment-execution feedback. Therefore, the present ToolBench experiments cannot establish that watermarking preserves end-to-end task completion.

The utility result supports the more limited observation that the proposed support-restricted sampling changes the agent's selected actions less often than the evaluated KGW-style logit-biasing baseline (72–83% versus 22–27% choice agreement on ToolBench). It should not be interpreted as a task-success comparison. Although ALFWorld provides a different action-space setting for the robustness study (Section 6.4), the submitted results likewise do not provide a controlled watermarked-versus-unwatermarked task-success evaluation.

We appreciate the reviewer's recognition of the problem's relevance and the cross-model evidence for paraphrase robustness. We also acknowledge the central distinction raised in the review: the submitted results establish robust semantic-cluster detection and a keyed defense against the evaluated fresh-action forgery attack in separate experimental settings, but do not establish their joint performance at one operating point. Our request is that the reviewer consider the independently supported contributions—agent-level semantic synchronization, its measured robustness and capacity trade-offs, and the explicit characterization of forgery successes and failures—while evaluating the untested joint configuration and end-to-end task utility as limitations rather than as demonstrated results.

Reviewer_EUNCOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents a watermarking scheme for LLM agents. The high-level idea is that, the agent behaviors at step t are mapped to an embedding space using an embedding model and run k-means on the obtained embedding vectors. Then, the paper uses a KGW-style watermarking to bias the behaviors whose PRF evaluation equals to 1. The PRF also takes a secret key as input. Because paraphrased actions tend to remain in the same cluster, the authors argue that the watermark is robust to tool renaming and rewriting. The authors show its effectiveness under different models and editing strategies.

Critical strengths

Agentic watermarking is an interesting and timely research question. And designing a watermark that is both robust to editing and resistant against spoofing is important.

Critical weaknesses
  • The writing needs substantial improvements, it's extremely hard to follow the flow.
  • Some notations are weird, I'd suggest the authors carefully check the AI-generated sentences. For instance, line 634, synthetic:deepseek-v4-flash, what does synthetic mean? Line 637, "reported as-is" what does this mean? There are many other such issues throughout the paper.
  • The claim on "every prior agent watermark studies only removal" does not hold.
  • The security against spoofing/stealing attacks relies on unrealistic assumptions.
  • Technically, I don't find any novel or interesting contributions.
Questions for authors
  1. "every prior agent watermark studies only removal" does not hold. If you do a literature search on "watermark spoofing attack", you can find many relevant papers [1,2,3].
  2. The security proof on the stealing/spoofing requires that the distinguisher only observe the behaviors/tokens once, which cannot hold in practice. And the proposed watermark is not a distortion-free watermarking, I don't see reasons why the prior watermarking stealing does not generalize (prior watermarking like KGW also uses PRF with a secret key).
  3. Can the authors clarify the technical contributions?
  4. Can the authors explain the weird wording throughout this paper?

[1] Pang, Qi, et al. "No free lunch in llm watermarking: Trade-offs in watermarking design choices." Advances in Neural Information Processing Systems 37 (2024).

[2] An, Hyeseon, et al. "Ditto: A spoofing attack framework on watermarked llms via knowledge distillation." Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics. 2026.

[3] Gloaguen, Thibaud, et al. "Discovering spoofing attempts on language model watermarks." ICML 2025.

2 comments

Response to Reviewer EUNC — Part 1/2

We thank the reviewer for the careful reading and for recognizing the importance of robust agent provenance and resistance to spoofing. We understand the concerns about technical novelty, the security assumptions, prior work, and presentation. We would like to clarify the precise scope of our claims and point to the evidence already included in the submission.

1. Security model and watermark stealing (Q2)

We agree that a secret-key PRF alone does not prevent watermark stealing, and that an attacker may observe multiple watermarked trajectories. Our threat model does not restrict the attacker to one observation: Section 3 explicitly allows an adversary with the public encoder and M observed watermarked trajectories. Appendix A.7 similarly states the fresh-bucket result after N observed (action, bit) pairs.

The important distinction is between the number of observations and whether the particular keyed bucket of a candidate action has already been observed. Theorem G.1 addresses only the latter, fresh-bucket case, in the random-oracle model. It is not a proof of security against unrestricted adaptive querying or copying observed transitions. We agree that this is a limited guarantee, and do not claim that keying makes every stealing strategy ineffective.

Our empirical evaluation therefore reports the uncovered cases separately. In Section 6.2, the adaptive nearest-neighbor-transfer forgery against public clustering succeeds at 100%, while keyed binning reduces it to 0.213 ± 0.117 at r=8 and to 0.012 at the ToolBench/bge r=64 operating point, close to its measured false-positive floor. The r-sweep and observed/fresh bucket decomposition directly measure how bucket collisions affect this result. These results are attack-specific, not a general security guarantee.

We also report attacks that remain effective: contiguous segment splicing succeeds at 0.623–0.940, and chained replay at 0.763–0.980 across the five models (Table 3). Section 6.2 explicitly states that increasing the history window does not stop an adaptive chainer who knows the window length. These negative results are important boundaries of the method, not attacks we claim to solve. We therefore agree with the reviewer that unrestricted watermark stealing remains an open concern; our narrower contribution is a keyed defense against the evaluated fresh-action attack, together with a characterization of its collision-dependent limitations.

2. Technical contributions (Q3)

We do not claim that semantic clustering, keyed PRFs, or history-conditioned watermarking are individually new. The contribution is the agent-specific construction, analysis, and evaluation of their interaction under semantic rewriting and forgery:

(a) Semantic synchronization for multi-step agent actions (Section 4.1). SeqWM conditions on exact action symbols. A semantics-preserving rewrite can change both the current symbol and the subsequent history used for detection. SBW instead conditions on semantic action-cluster symbols, so the detector can preserve its history representation when a rewritten action remains in the same cluster. This is a different failure mode from ordinary token-level paraphrase robustness.

(b) Quantified robustness and its costs (Sections 5 and 6.1). On ToolBench, paraphrase detection at a calibrated 1% FPR is 0.49–0.66 for CLUSTER versus 0.05–0.17 for the exact-symbol baseline across five models. On ALFWorld, the corresponding ranges are 0.92–0.97 versus 0.00–0.01 (Tables 2 and 5). We also report the unfavorable side of the tradeoff: exact-symbol detection is stronger under deletion alone, and clustering retains only 41.9–50.1% of tool-level watermark capacity at k=100 on ToolBench. Section 5 analyzes cluster stability, abstention, and capacity under the specified elicitation operator.

(c) An agent-specific forgery evaluation and bounded defense (Sections 4.2 and 6.2). We evaluate whether an attacker can use observed watermarked behavior and a public semantic representation to steer new action choices toward acceptance. Keyed binning reduces this particular transfer attack, while the observed-bucket and copy-style experiments identify where it does not help. We view the explicit separation of fresh-action forgery from replay and splicing as an important part of the contribution.

We recognize that the method builds on existing watermarking ideas. Our novelty claim is about addressing these linked problems in multi-step agent behavior and measuring both the gains and the limitations, not about inventing the underlying primitives.

Response to Reviewer EUNC — Part 2/2

3. Prior spoofing literature and the scope of the related-work claim (Q1)

We agree with the reviewer that spoofing and watermark stealing have been studied in the broader LLM text-watermarking literature, including the three cited papers. The wording “every prior agent watermark studies only removal” is too broad if read as a statement about all watermarking research, and we should have made the distinction clearer.

Our intended claim concerns the agent behavioral watermarking methods compared in this paper, rather than watermarking in general. Section 2 already discusses text-watermark stealing, including Jovanović et al. (2024), and distinguishes it from watermarking over multi-step tool/action trajectories. We appreciate the additional references, which are relevant context for understanding the limits of any key-based defense. Our contribution should not be read as claiming to introduce the general notion of watermark spoofing.

4. Presentation and terminology (Q4)

We agree that the paper is dense and that several expressions are unnecessarily difficult to follow. We apologize for the unclear wording. To answer the two specific examples:

  • “synthetic:deepseek-v4-flash” (Appendix A.2, line 634) is an experiment provenance label for the stronger-model-generated paraphrase pool, not a methodological term. The same passage states that all 2,128 tool paraphrases were regenerated for this test, with zero fallbacks.
  • “reported as-is” (Appendix A.2, line 637) means that the lower combined paraphrase-plus-deletion detection values, 0.27/0.22, are disclosed rather than omitted or replaced by the stronger paraphrase-only results. We agree that directly stating this would be clearer.

For clarity, the main experimental message is summarized by Tables 2 and 5 (rewriting robustness), Figure 2 and Section 6.2 (fresh-action forgery and copy-style failures), and Section 5 (stability and capacity tradeoffs). We appreciate the presentation feedback and acknowledge that the current organization makes these distinctions harder to find than they should be.

We appreciate the reviewer's concerns, especially the warning against treating a secret key as a blanket defense against stealing. We hope the distinction between fresh-bucket unpredictability, attack-specific empirical resistance, and unresolved replay/adaptive-stealing attacks helps clarify the scope of our security claim. We also hope the cross-model and cross-benchmark results, together with the measured capacity and security limitations, make the technical contribution easier to assess. Thank you for reconsidering the paper in light of these clarifications.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.