This paper analyzes the information-theoretic costs of watermarking capabilities such as user attribution, payload extraction, and localization in generative models. It introduces an information profile to quantify how much each token reveals about a secret, establishing that detection relies on distribution distance while other tasks depend on information mass.
- Multi-user attribution for N users costs Θ(log N/h) tokens over stationary-ergodic sources, achieved by thresholding candidates by realized surprisal.
- Extraction of an l-bit payload requires Θ(l/h) tokens.
- A Θ(log N)-token window exists where text is provably machine-made but unattributable.
- Experiments on GPT-2, Pythia-410M, and Qwen2.5 recover the predicted constants.
The study provides a tight entropy-rate law for multi-user attribution and identifies fundamental limits like footprint-resolution uncertainty in watermark design.