💻 computer science

Sequential Behavioral Watermarking for LLM Agents

This paper introduces SeqWM, a sequential behavioral watermarking framework that embeds ownership signals into history-conditioned agent transition patterns to enable robust, position-agnostic trajectory verification while preserving agent utility, overcoming the fragility of existing methods that treat actions as independent trials.

Original authors: Hyeseon An, Shinwoo Park, Dongsu Kim, Yo-Sub Han

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hyeseon An, Shinwoo Park, Dongsu Kim, Yo-Sub Han

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Black Box" Agent

Imagine you hire a highly skilled robot assistant (an LLM Agent) to do a complex job, like planning a trip or debugging code. This robot doesn't just write a final report; it makes a long chain of decisions: "I'll check the weather," then "I'll book a flight," then "I'll call a taxi."

The Problem: If you see a list of these actions, how do you know which robot did them?

Did your robot do it?
Did a competitor's robot do it?
Did a hacker steal your robot's "brain" and make a copy that does the exact same thing?

Currently, it's very hard to tell. The robot's internal thoughts (the text it generates) are often hidden, and we only see the final actions. If someone copies your robot's behavior, they can steal your intellectual property without you knowing.

Why Old Methods Failed

Scientists previously tried to solve this by putting a "digital watermark" on the words the robot wrote (like a hidden ink stain on a letter).

The Flaw: In the world of agents, the action matters more than the words. If a robot decides to "call a taxi," it might say that in a thousand different ways. A watermark on the words gets lost in the noise.
The "Round Number" Trap: Some newer methods tried to watermark the actions by tagging them based on their order (e.g., "The 1st action must be A, the 2nd must be B").
- The Analogy: Imagine a dance routine where the watermark is "Step 1 is a spin, Step 2 is a jump." If the audience misses Step 1 (maybe the video cuts out), they lose the count. Suddenly, Step 2 looks like a "Step 1," and the whole watermark breaks. The system is too fragile; one missing step ruins the whole proof.

The Solution: SeqWM (The "Contextual Dance" Watermark)

The authors propose SeqWM, a new way to watermark agents that doesn't care about the specific step number. Instead, it looks at the pattern of movement.

1. The Core Idea: "History is the Key"

Instead of asking, "What is the 5th step?" SeqWM asks, "What happened in the last few steps?"

The Analogy: Imagine a secret handshake.
- Old Way: "If you are the 5th person in line, do a high-five." (If someone leaves the line, everyone shifts, and the 5th person is now the 4th, so the rule breaks).
- SeqWM Way: "If the person before you did a 'wave' and the one before that did a 'nod,' then you must do a 'clap'."
- Why it works: It doesn't matter if you are the 5th person or the 50th person. As long as the pattern (Wave -> Nod -> Clap) exists, the watermark is there. If someone deletes a step in the middle, the pattern just shifts slightly, but the rest of the dance still holds the secret.

2. The "Multi-Channel" Safety Net

To make sure the watermark survives even if parts of the video are chopped up, SeqWM uses multiple channels (like having 8 different secret codes running at once).

The Analogy: Instead of writing a secret message on one piece of paper, you write it on 8 different pieces of paper. If a thief burns one or two, you can still read the message from the remaining six.
In SeqWM, the agent's decision is slightly nudged based on 8 different "secret keys" derived from the recent history. Even if the agent's behavior is messy, the statistical pattern across these 8 channels reveals the watermark.

3. The "Random Key" Detective

How do you prove it's a watermark and not just a coincidence?

The Old Way: You try to guess the secret code. If you guess right, you find the watermark.
The SeqWM Way: The detective takes the action sequence and runs it through a "simulator" using thousands of wrong secret keys.
- If the sequence was watermarked with the real key, the score will be very high.
- If you run it with wrong keys, the score will be low (like background noise).
- The Analogy: Imagine trying to find a specific radio station. You tune through 1,000 random frequencies. Most sound like static. But one frequency (the real key) plays a clear song. If the song is loud enough compared to the static, you know it's real. This method is mathematically proven to be fair, even if the robot's behavior is weird or the video is cut up.

What the Experiments Showed

The researchers tested this on three different types of AI agents (one for tools, one for physical tasks, one for social simulation) using different AI models.

Reliability: SeqWM successfully identified the "owner" of the agent's behavior almost 100% of the time, whereas older methods failed frequently.
Robustness: When they simulated "attacks" by deleting 10%, 20%, or even 50% of the actions (like cutting chunks out of a video), SeqWM still worked. The old "round-number" methods collapsed immediately after just one deletion.
No Harm: The watermark didn't make the robot "dumber" or change its ability to solve problems. It just slightly nudged the choices in a way that was invisible to the user but detectable by the verifier.

Summary

SeqWM is like putting a watermark on a robot's dance moves rather than its words. Instead of counting steps (which breaks if you miss one), it looks at the relationship between moves (e.g., "After a spin, a jump is likely"). By using multiple secret codes and a clever statistical test, it can prove who created a robot's behavior, even if parts of the behavior are missing or hidden. This protects the creators of AI agents from having their work stolen or copied.

Technical Summary: Sequential Behavioral Watermarking for LLM Agents (SeqWM)

1. Problem Statement

Large Language Model (LLM) agents have evolved from text generators into autonomous decision-makers that plan, invoke tools, and interact with external environments. This shift creates a critical provenance gap: while the intellectual property of these agents resides in their decision-making capabilities (acquired via expensive post-training on trajectory data), the trajectories themselves are valuable assets vulnerable to unauthorized replication and imitation attacks.

Existing watermarking solutions for LLMs primarily operate at the token level, biasing the sampling of vocabulary tokens. However, this approach fails for agents for two reasons:

Mismatched Units: High-level agent decisions (e.g., "call tool X") are realized through many tokens. A token-level bias dilutes the signal before it influences the actual action.
Observability Limits: In many deployed agentic systems (82.8% of surveyed platforms), internal reasoning traces and intermediate tokens are hidden; detectors only observe the final action stream. Consequently, token-level signals are discarded before verification.

Recent behavioral watermarking attempts treat each action step as an independent trial, often seeding watermarks based on absolute round indices. This approach is fragile: if a trajectory is truncated, deleted, or observed without perfect alignment, the index shifts, causing the detector to misalign with the watermark logic and rendering the entire sequence undetectable.

2. Methodology: SeqWM

The authors propose SeqWM, a framework that embeds watermark signals into history-conditioned transition patterns rather than marginal action frequencies or absolute positions. The method consists of three core components:

A. History-Conditioned Multi-Channel Encoding

Instead of using the absolute step index $t$ to seed the watermark, SeqWM uses a window of preceding actions $c_t = (b_{t-w}, \dots, b_{t-1})$ as the seed.

Mechanism: For a secret key $K$ , the system derives a pseudorandom subset of candidate actions $B^{(j)}_{g,t}$ for each of $m$ independent channels using a keyed hash function: $B^{(j)}_{g,t} = G_K(c_t \parallel j)$ .
Biasing: The agent's action distribution $P_t$ is modified to a watermarked distribution $P^{wm}_t$ via an exponential tilt based on a multi-channel score $s_t(b)$ , which counts how many channels favor a specific action $b$ .
Effect: The watermark biases the conditional transition $P(b_t | c_t)$ rather than the marginal frequency of $b_t$ . This ensures the signal survives even if an adversary matches the marginal distribution.

B. Sliding-Window Detection

The detector operates position-agnostically. It does not rely on knowing the absolute step index of the observed sequence.

Mechanism: The detector slides a window of size $w$ over the observed action sequence $\hat{b}$ . For every substring of length $w$ , it checks if the subsequent action matches the guided subset derived from that specific history and the secret key.
Robustness: Because the same history window deterministically yields the same guided subset regardless of its absolute position, the detector can aggregate evidence from any valid transition in a truncated or corrupted sequence. This contrasts with round-indexed detectors, where a single deletion shifts all subsequent indices, causing global misalignment.

C. Random-Key Calibration

Standard statistical tests (e.g., binomial $z$ -tests) assume independence between detection indicators, which is invalid here due to the sequential nature of agent behavior and overlapping windows.

Solution: The framework constructs an empirical null distribution using the observed sequence itself. It computes the detection score using the true key $K$ and compares it against scores generated using $M$ random "wrong" keys $K_r$ .
Validity: Since the wrong keys preserve the natural dependencies of the sequence but erase the watermark alignment, the resulting $p$ -value is distribution-free and valid even under adversarial corruption (deletion, truncation).

3. Key Contributions

Framing: The paper reframes agent watermarking as a sequential coding problem, identifying an asymmetry: generation is chained through history, but verification can aggregate local transition evidence without reconstructing the chain.
Method: Introduction of SeqWM, which combines history-conditioned encoding, sliding-window detection, and random-key calibration to achieve position-agnostic verification.
Theory: Theoretical analysis proving that while round-indexed detection collapses under deletion (expected aligned prefix length $O(1/\rho)$ ), sliding-window detection suffers only a local, additive loss of evidence ( $d(w+1)m$ indicators), preserving detection power.
Empirical Evaluation: Extensive experiments across three benchmarks (ToolBench, ALFWorld, OASIS) and three LLM backbones (Gemma, LLaMA, Qwen).

4. Experimental Results

Detection Reliability: SeqWM consistently achieves statistically significant detection ( $p < 0.01$ ) across all models and benchmarks, whereas baseline methods (AgentGuide, AgentMark) frequently fail to separate from the null hypothesis, especially in OASIS and with certain LLMs.
Robustness to Deletion: Under random action deletion rates up to 50%, SeqWM maintains high True Positive Rates (TPR). In contrast, round-indexed baselines (AgentGuide) collapse immediately after small deletion rates due to index misalignment.
Utility Preservation: The watermarking process preserves agent utility. The bias strength ( $\gamma$ ) can be tuned (e.g., $\gamma=2.0$ ) to achieve reliable detection without significantly degrading task performance.
Multi-Channel Necessity: Ablation studies show that single-channel variants fail to provide reliable detection even with high bias strength, confirming that redundant channels are essential for accumulating sufficient evidence across the trajectory.

5. Significance and Claims

The paper claims that sequential structure is not merely a nuisance in agent watermarking but a powerful carrier of provenance signals. By shifting the watermark from per-step statistics to conditional transition patterns, SeqWM solves the alignment problem inherent in previous behavioral watermarking methods.

The authors position SeqWM as a net-positive for accountability and post-hoc auditing in autonomous agent deployments. They emphasize that their approach makes trajectory corruption (deletion, truncation) a local source of evidence loss rather than a global detector failure. The work suggests that extending this perspective to stronger adaptive attacks and semantic-level trajectory edits is a necessary direction for future research, but the current contribution establishes a robust, position-agnostic foundation for verifying agent provenance.