🤖 AI

AgentMark: Utility-Preserving Behavioral Watermarking for Agents

AgentMark is a behavioral watermarking framework designed to protect the intellectual property of LLM-based agents by embedding multi-bit identifiers into their high-level planning decisions through distribution-preserving conditional sampling, ensuring robust provenance without compromising task utility or requiring direct access to the agent's internal weights.

Original authors: Kaibo Huang, Jin Tan, Yukun Wei, Wanling Li, Zipei Zhang, Hui Tian, Zhongliang Yang, Linna Zhou

Published 2026-04-27

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Kaibo Huang, Jin Tan, Yukun Wei, Wanling Li, Zipei Zhang, Hui Tian, Zhongliang Yang, Linna Zhou

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

Imagine you have a highly advanced Robot Butler. This butler is amazing: it can plan a whole day, use your kitchen appliances, manage your calendar, and even chat with your neighbors.

Because this robot is so capable, two big problems arise:

The "Copycat" Problem: What if a company steals the "brain" (the logic and planning style) of your expensive robot and sells a cheap knock-off?
The "Blame" Problem: If the robot accidentally breaks a vase or makes a bad social decision, how do we prove which specific version of the software was running at that exact moment?

Current technology can watermark the words the robot says (like a digital stamp on a letter), but it can't easily watermark the decisions the robot makes (like the specific way it chooses to walk through a room or which tool it picks up first).

AgentMark is the solution. Here is how it works using two simple analogies.

1. The "Secret Dance" (How it works)

Imagine you want to prove that a specific dance troupe performed a routine, even if they are wearing masks. Instead of changing their clothes (which would be like changing the robot's code and making it clumsy), you teach them a Secret Dance Step.

In every routine, there are moments where the dancers have a choice: “Should I spin left or spin right?”

Normally, they might choose based on what feels natural. But with AgentMark, they follow a rule: "Pick a move that feels natural, but slightly favor a specific pattern that encodes our secret ID."

Crucially, they don't do anything weird or jerky that ruins the dance. They stay perfectly in rhythm (this is what the researchers call "Utility Preservation"). To an outsider, it looks like a normal dance. But to a judge who knows the secret rhythm, the specific sequence of "lefts" and "rights" reveals the troupe's unique ID.

2. The "Jigsaw Puzzle" (How it stays robust)

In the real world, things go wrong. Maybe the security camera missed a few seconds of the dance, or a page of the dance notes got torn (this is "Step Erasure").

If you were using a simple code, losing one piece might ruin the whole thing. But AgentMark uses a mathematical trick called RLNC (think of it like a Smart Jigsaw Puzzle).

In a normal puzzle, if you lose the corner piece, you can't finish the picture. In a "Smart Jigsaw," every single piece contains a little bit of information about every other piece. Even if you only find 70% of the pieces, you can use the overlapping information to mathematically reconstruct the entire image. This means even if the robot's logs are messy or incomplete, we can still recover its "ID."

Summary: Why does this matter?

It’s Invisible: It doesn't make the robot "stupid" or slow. It works within the robot's existing decision-making process.
It’s Deep: It doesn't just watermark the text (the "what"); it watermarks the behavior (the "how").
It’s Tough: It can survive "noise," like missing data or slightly different ways of describing a situation.

In short: AgentMark gives autonomous AI agents a "behavioral DNA" that is nearly impossible to fake, easy to track, and doesn't get in the way of their work.

Technical Summary: AgentMark: Utility-Preserving Behavioral Watermarking for Agents

1. Problem Statement

As Large Language Model (LLM)-based agents transition from passive text generators to autonomous decision-makers (performing tool use, embodied tasks, and social interactions), they introduce new security and governance risks, such as impersonation, unauthorized replication, and automated manipulation.

Existing content watermarking (e.g., SynthID) focuses on the final text output (the "action" layer). However, this fails to capture the high-level planning behaviors (the "behavior" layer)—such as which tools are selected or which subgoals are prioritized—that drive long-horizon agentic outcomes. Directly watermarking these behaviors is difficult because:

Utility Degradation: Biasing decision probabilities can cause "task drift," where small errors compound over long trajectories, leading to task failure.
Black-Box Constraints: Many agents rely on closed APIs where model weights cannot be modified.
Robustness Issues: Agent logs are often incomplete due to platform filtering, execution failures, or truncation, making traditional watermarking hard to recover.

2. Methodology

The authors propose AgentMark, a framework that embeds multi-bit identifiers into an agent's planning decisions while ensuring the agent's underlying decision logic remains unchanged.

A. Behavior–Action Separation
AgentMark distinguishes between planning behavior (the choice of what to do) and execution action (how to do it). It intervenes only at the planning stage by eliciting an explicit probability distribution $P_t$ over candidate behaviors $B_t$ and then sampling from that distribution in a way that preserves its marginal probabilities.

B. AgentMark-F (The Concrete Instantiation)
The framework uses a specific construction called AgentMark-F, which relies on two core mathematical components:

Differential Recombination: To ensure utility preservation, the framework transforms the elicited probability distribution into a mixture of "uniform bins." By sampling from these bins, the marginal probability of selecting any specific behavior remains exactly equal to the original distribution ( $Pr[\hat{b}_t = b] = P_t(b)$ ).
Cyclic-Shift Uniform Encoding: Within a selected bin, the framework uses a keyed pseudorandom cyclic shift to embed a variable-length bitstring. This ensures that the selection within the bin is computationally indistinguishable from uniform sampling, making the watermark invisible to the agent's performance.

C. Robustness via RLNC
To handle "erasure" (missing steps in logs) and "truncation" (incomplete trajectories), AgentMark-F employs Random Linear Network Coding (RLNC) over $F_2$ . Instead of treating the watermark as a fixed block, it treats each embedded bit as a linear equation. As long as the verifier collects enough surviving equations (bits) from any subset of the trajectory, they can solve the system to recover the original ID.

3. Key Contributions

New Watermarking Layer: Shifts the focus from token-level content to high-level planning behavior.
Distribution-Preserving Sampling: Provides a mathematical guarantee that watermarking does not shift the agent's policy, thereby preventing task drift.
Erasure-Resilient Coding: Uses RLNC to enable robust provenance recovery even when agent logs are partially lost or truncated.
Black-Box Compatibility: Operates via prompting (eliciting probability lists) rather than weight manipulation, making it compatible with proprietary APIs like GPT-4 or Gemini.

4. Experimental Results

The framework was evaluated across three diverse environments: ALFWorld (embodied tasks), ToolBench (tool-use), and OASIS (social simulation).

Utility Preservation: Unlike baseline bias-based methods (Red-Green watermarking) which significantly degraded success rates in long-horizon tasks, AgentMark-F maintained success rates nearly identical to unwatermarked agents.
Capacity: Achieved practical multi-bit capacity (e.g., ~1.2 bps in ALFWorld and ~4.9 bits per task in ToolBench).
Robustness:
- Erasure: RLNC allowed for successful ID recovery even with significant step loss, showing a clear "phase transition" where recovery becomes highly reliable once a threshold of bits is met.
- Rewriting: The watermark remained recoverable even when environment observations were semantically rewritten by other LLMs.
Composability: Demonstrated that AgentMark (behavioral) and SynthID (content) can be used simultaneously without interfering with each other.

5. Significance

AgentMark provides a critical primitive for the governance and auditing of autonomous AI systems. By enabling reliable, utility-preserving provenance, it allows enterprises to protect their proprietary agent logic and enables regulators to trace the origins of autonomous actions in complex, multi-agent ecosystems. It bridges the gap between "what an agent says" and "how an agent behaves," ensuring accountability for the actual decisions made by AI.