AgentMark: Utility-Preserving Behavioral Watermarking for Agents

Idea

AgentMark在agent的planning behavior选择中编码provenance watermark，而不改写最终tool参数或输出措辞。它先显式提取候选行为概率，再用保持该分布的keyed sampling嵌入bits，并用抗擦除编码支持从不完整轨迹恢复来源信息。

Research Problem

文本水印难覆盖agent多步工具行为，直接对执行动作施加偏置又可能影响任务成功并在长轨迹中累积损失。实际审计日志还会缺步或截断，因此水印需要兼顾行为效用、可解码容量以及部分日志情况下的恢复。

Insight

planning层常存在多个可接受行为，可以在保持每步边际选择概率的同时改变随机选择与payload的关联，从而承载来源信息。编码保证应相对于实际提取的概率表建立，而不是无法直接观察的latent policy；日志缺失则通过收集足够独立线性方程恢复payload。

Method

1. 在每步由观察与history得到有限候选behavior set及显式概率P_t；embedder和verifier共享secret key与step context，派生同步伪随机源，先选watermarked behavior，再由agent据此生成执行action。
2. AgentMark-F按概率排序，以相邻概率差构成top-k均匀bins，并用k倍差值作为bin权重；在选中bin内通过cyclic-shift uniform encoding嵌入可变长度bits，使行为边际仍等于P_t。
3. 解码端利用已记录behavior、对应P_t和相同context重建bin与随机过程，恢复各步bit片段；可选RLNC将payload编码为F2上的伪随机线性方程，剩余记录提供的方程矩阵满秩时唯一解码。
4. 在ALFWorld、ToolBench和OASIS中比较ReAct基线及带选择偏置的red–green水印，评价任务成功、轨迹长度、容量与擦除/截断恢复；理论恢复下界按实际收到的总bit数及随机系数假设给出。