We study statistical watermarking by formulating it as a hypothesis testing
problem, a general framework which subsumes all previous statistical
watermarking methods. Key to our formulation is a coupling of the output tokens
and the rejection region, realized by pseudo-random generators in practice,
that allows non-trivial trade-off between the Type I error and Type II error.
We characterize the Uniformly Most Powerful (UMP) watermark in this context. In
the most common scenario where the output is a sequence of $n$ tokens, we
establish matching upper and lower bounds on the number of i.i.d. tokens
required to guarantee small Type I and Type II errors. Our rate scales as
$\Theta(h^{-1} \log (1/h))$ with respect to the average entropy per token $h$
and thus greatly improves the $O(h^{-2})$ rate in the previous works. For
scenarios where the detector lacks knowledge of the model's distribution, we
introduce the concept of model-agnostic watermarking and establish the minimax
bounds for the resultant increase in Type II error. Moreover, we formulate the
robust watermarking problem where user is allowed to perform a class of
perturbation on the generated texts, and characterize the optimal type II error
of robust UMP tests via a linear programming problem. To the best of our
knowledge, this is the first systematic statistical treatment on the
watermarking problem with near-optimal rates in the i.i.d. setting, and might
be of interest for future works.

通过将统计水印技术作为一种假设检验问题进行研究，我们建立了一个通用框架，涵盖了所有以前的统计水印方法，并通过在实际中使用伪随机生成器将输出符号和拒绝域进行耦合，实现了类型 I 错误和类型 II 错误之间的非平凡权衡。我们描述了在这种情境中的均匀最有力（UMP）水印。对于输出为 $n$ 个符号序列的最常见情况，我们对所需的 i.i.d. 符号数量的上下界进行了匹配，以保证较小的类型 I 错误和类型 II 错误。我们的比率与每个符号的平均熵 $h$ 相关，因此大幅改进了先前作品中的 $O (h^{-2})$ 比率。对于检测器缺乏模型分布知识的情况，我们引入了模型无关水印技术，并为类型 II 错误增加的最小值界限建立了最小化界限。此外，我们还制定了鲁棒水印问题，允许用户对生成的文本进行一类扰动，并通过线性规划问题表征了鲁棒 UMP 检验的最佳类型 II 错误。据我们所知，这是第一个在 i.i.d. 设置中具有近乎最优速率的水印问题的系统统计处理，对于未来的研究可能具有兴趣。