Optimal Watermark Localization
Posted on
formulate watermark localization as a token-level multiple-testing problem based on pivotal statistics, with a latent indicator recording whether watermark dependence survives at each position.
under an asymptotic regime indexed by exponents for signal sparsity, next-token concentration, and effective-vocabulary growth, they derive a sharp boundary for global detection and phase transitions for discovery and classification within the class of coordinatewise pivot-based localization rules.
show that discovery is strictly harder than detection and that consistent classification is impossile across the parameter regime within this class.
develop an adaptive thresholding method that does not require knowledge of the exponents or time-varying next-token distributions, but uses a data-driven estimate of the surviving watermark fraction.
the method attains the optimal discovery boundary and near-optimal discovery power relative to homogeneous pivot-based rules.
Introduction
for a mixed-source text, can we identify which parts still preserve watermark evidence? refer to this task as watermark localization, or watermark discovery, following the terminology of signal discovery in the multiple testing literature.
recent works have explored this problem using change-point detection or online learning ideas, showing that localization is achievable in practice.
however, these works are mainly algorithmic and do not characterize the statistical limits of localization for mixed-source data.
the paper asks: for mixed-source text, when is watermark localization statistically possible, and can it be achieved adaptively whenever localization is information-theoretically possible, without requiring prior knowledge of the source-mixing process?
Contributions
A robust multiple-testing framework for watermark localization
for each position $t$, introduce a latent survival indicator $\theta_t\in {0, 1}$:
- $\theta_t = 1$ means that the watermark dependence at position $t$ survives editing
- $\theta_t = 0$ means that this dependence is erased.
conditional on $\theta_t$, the pivotal statistic follows either the null law $\mu_0$ or a watermark-induced alternative law $\mu_{1,P_t}$, determined by the local NTP distribution $P_t$ of token $w_t$.