A Watermark for Large Language Models

2 A simple proof of concept

1. Describe the “hard red list” watermark.
   At each step, hash the previous token to seed a random generator, use it to split the vocabulary into a green and a red list, and sample the next token only from the green list. A detector that knows the hash can rebuild each red list and count violations.
   • Kirchenbauer et al., 2023, A Watermark for Large Language Models (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §2
2. How is the watermark detected statistically?
   Under the null hypothesis that the text was written without knowing the red list rule, the green-token count \(|s|_G\) of \(T\) tokens has mean \(\gamma T\) and variance \(T\gamma(1-\gamma)\); compute \(z = (|s|_G - \gamma T)/\sqrt{T\gamma(1-\gamma)}\) and flag the text if \(z\) exceeds a threshold, e.g. \(z > 4\) (false-positive rate \(3 \times 10^{-5}\)).
   • Kirchenbauer et al., 2023, A Watermark for Large Language Models (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §2
3. With the hard red list (\(\gamma = 1/2\)) and threshold \(z = 4\), how many tokens are needed for detection, and why?
   16: if every token is green, \(z = 2(T - T/2)/\sqrt{T} = \sqrt{T}\), which reaches 4 at \(T = 16\).
   • Kirchenbauer et al., 2023, A Watermark for Large Language Models (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §2
4. Why is the watermark hard to remove by editing tokens?
   Each changed token can create at most two red-list violations (itself and the next token, whose list it seeds). Even a maximally adversarial edit of 200 of 1,000 tokens leaves 600 green tokens, \(z \approx 6.3\); removal needs changing roughly a quarter of the tokens, and an attacker who doesn’t know the lists does far worse.
   • Kirchenbauer et al., 2023, A Watermark for Large Language Models (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §2
5. What is the drawback of the hard red list rule?
   It forbids red tokens even when they are the only sensible continuation (e.g. “Obama” after “Barack”), degrading low-entropy text.
   • Kirchenbauer et al., 2023, A Watermark for Large Language Models (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §2