Elamur Research⌕
☰
home / papers / 2023 / Provable Robust Watermarking for AI-Generated Text

Provable Robust Watermarking for AI-Generated Text

Paper · 2023 · Xuandong Zhao, Prabhanjan Ananth, Lei Li et al.

Summary

Detectors that try to spot machine-written text in general depend on surface statistics. They break when the input distribution shifts, they are open to adversarial attack, and they can be biased against some writers. Watermarking avoids this by planting a hidden signal during generation. Existing schemes, however, can be removed through light editing or paraphrasing. The authors set out a formal framework that defines three properties of an LLM watermark: preserved output quality, error rates on both sides of detection, and robustness to post-hoc edits measured by edit distance. They then propose Unigram-Watermark. It simplifies the K-gram scheme of Kirchenbauer et al. by using one fixed Green-Red split of the vocabulary rather than a split tied to the prefix. They prove that the watermarked model stays close to the original in every Renyi divergence. They also prove that false-positive and false-negative rates shrink exponentially as the suspect text gets longer and more diverse, and that tolerance to edits is twice that of the baseline. Tests on three LLMs and two datasets show better detection under attack at similar perplexity. This makes provenance claims both checkable and harder to evade.

Key points

  • The core design change is a single global green/red vocabulary partition (K = 1). It replaces the partition re-derived from each preceding token in KGW+23. Most guarantees also carry over to K ≥ 2, except the Type II bound.
  • The paraphrase attacks used ChatGPT, DIPPER, and BART (bart-large-cnn). On OpenGen with LLaMA-7B, AUC rose from 0.949 to 0.989 against ChatGPT paraphrasing and from 0.892 to 0.949 against BART summarization. Accuracy stayed above 85% at a 10% false-positive rate.
  • Edit attacks on LFQA with LLaMA-7B covered synonym replacement, deletion, and swapping. With 50% of tokens swapped, AUC was 0.978 for Unigram-Watermark versus 0.702 for KGW+23.
  • On human-written TOEFL essays collected by Liang et al., z-scores stayed well under the detection threshold of z = 6.0. This avoids the misclassification of non-native writers seen in commercial detectors.
  • Code is released at github.com/XuandongZhao/Unigram-Watermark.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 worksHardware and Architecture · 167 works

Cite

Cite as Xuandong Zhao, Prabhanjan Ananth, Lei Li and Yu-Xiang Wang. 2023. Provable Robust Watermarking for AI-Generated Text. arXiv:2306.17439.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2306.17439 · arXiv 2306.17439

@misc{zhao2023provable,
  title = {{Provable Robust Watermarking for AI-Generated Text}},
  author = {Xuandong Zhao, Prabhanjan Ananth, Lei Li and Yu-Xiang Wang},
  year = {2023},
  doi = {10.48550/arxiv.2306.17439},
  eprint = {2306.17439},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2306.17439}
}

References

48 references, 24 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. International Conference on Machine Learning, 2023.
  2. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
  3. Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. ArXiv, abs/2204.06125, 2022.
  4. Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems, 35…
  5. OpenAI. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023a.
  6. OpenAI. Chatgpt: Optimizing language models for dialogue. OpenAI blog, 2022. URL https://openai.com/blog/chatgpt/. ↗
  7. Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. Advances in neural information processing systems, 32, 2019.
  8. Laura Weidinger, John F. J. Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, Zachary Kenton, Sande Minnich Brown, William T. Hawkins, Tom Stepleton, Courtney Biles, Abeba Birhane, Julia Haas, Laura Rimell, Lisa Anne Hendrick… — Ethical and social risks of harm from Language Models
  9. Chris Stokel-Walker. Ai bot chatgpt writes smart essays - should professors worry? Nature, 2022. find
  10. Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. ArXiv, abs/2212.04356, 2022.
  11. Nicholas Carlini, Matthew Jagielski, Christopher A. Choquette-Choo, Daniel Paleka, Will Pearce, H. Anderson, A. Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web-scale training datasets is practical. ArXiv, abs/2302.10149, 2023. — [arXiv:2302.10149](https://arxiv.org/abs/2302.10149) find
  12. Alan M Turing. Computing machinery and intelligence. 1950. find
  13. Sebastian Gehrmann, Hendrik Strobelt, and Alexander M. Rush. Gltr: Statistical detection and visualization of generated text. In Annual Meeting of the Association for Computational Linguistics, 2019.
  14. Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning, and Chelsea Finn. Detectgpt: Zero-shot machine-generated text detection using probability curvature. ArXiv, abs/2301.11305, 2023.
  15. Dirk Hovy. The enemy in your own camp: How well can we detect statistically-generated fake reviews – an adversarial study. In Annual Meeting of the Association for Computational Linguistics, 2016. find
  16. OpenAI. New ai classifier for indicating ai-written text. OpenAI blog, 2023b. URL https://openai.com/blog/new-ai-classifier-for-indicating-ai-written-text. ↗
  17. Weixin Liang, Mert Yuksekgonul, Yining Mao, Eric Wu, and James Y. Zou. Gpt detectors are biased against non-native english writers. ArXiv, abs/2304.02819, 2023.
  18. Xuandong Zhao, Yu xiang Wang, and Lei Li. Protecting language generation models via invisible watermarking. ArXiv, abs/2302.03162, 2023. — [arXiv:2302.03162](https://arxiv.org/abs/2302.03162) find
  19. Scott Aaronson. Simons institute talk on watermarking of large language models, 2023. URL https://simons.berkeley.edu/talks/scott-aaronson-ut-austin-openai-2023-08-17. ↗
  20. Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194, 2023. — [arXiv:2306.09194](https://arxiv.org/abs/2306.09194) find
  21. Mélisande Albert. Concentration inequalities for randomly permuted sums. In High Dimensional Probability VIII: The Oaxaca Volume, pages 341–383. Springer, 2019. find
  22. Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAI blog, 2019. find
  23. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
  24. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1907.11692, 2019.
  25. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, pages 265–284. Springer, 2006. find
  26. Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In International Conference on Machine Learning, pages 2597–2606. PMLR, 2020. find
  27. Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. ArXiv, abs/2303.13408, 2023.
  28. Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017.
  29. Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. Opt: Open pre-trained tr… — OPT: Open Pre-trained Transformer Language Models
  30. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aur’elien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, abs/23…
  31. Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020.
  32. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface’s transformers: State-ofthe-art natural language processing. ArXiv, abs/1910.03771, 2019.
  33. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Low… — Training language models to follow instructions with human feedback
  34. Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdel rahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. In Annual Meeting of the Association for Computationa…
  35. Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. Advances in neural information processing systems, 28, 2015.
  36. Katzenbeisser Stefan, AP Fabien, et al. Information hiding techniques for steganography and digital watermarking, 2000. find
  37. Umut Topkara, Mercan Topkara, and Mikhail J. Atallah. The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions. In Workshop on Multimedia & Security, 2006. find
  38. Mikhail J. Atallah, Victor Raskin, Michael Crogan, Christian F. Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. Natural language watermarking: Design, analysis, and a proof-of-concept implementation. In Information Hiding, 2001. find
  39. Mikhail J. Atallah, Victor Raskin, Christian F. Hempelmann, Mercan Topkara, Radu Sion, Umut Topkara, and Katrina E. Triezenberg. Natural language watermarking and tamperproofing. In Information Hiding, 2002. find
  40. Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Tracing text provenance via context-aware lexical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11613–11621, 2022. find
  41. Honai Ueoka, Yugo Murawaki, and Sadao Kurohashi. Frustratingly easy edit-based linguistic steganography with a masked language model. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021. find
  42. Margherita Gambini, Tiziano Fagni, F. Falchi, and Maurizio Tesconi. On pushing deepfake tweet detection capabilities to the limits. Proceedings of the 14th ACM Web Science Conference 2022, 2022. find
  43. Max Wolff. Attacking neural text detectors. ArXiv, abs/2002.11768, 2020. — [arXiv:2002.11768](https://arxiv.org/abs/2002.11768) find
  44. Vinu Sankar Sadasivan, Aounon Kumar, S. Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? ArXiv, abs/2303.11156, 2023.
  45. Souradip Chakraborty, Amrit Singh Bedi, Sicheng Zhu, Bang An, Dinesh Manocha, and Furong Huang. On the possibilities of ai-generated text detection. arXiv preprint arXiv:2304.04736, 2023. — [arXiv:2304.04736](https://arxiv.org/abs/2304.04736) find
  46. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485–5551, 2020.
  47. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007. find
  48. Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Algorithmic Learning Theory, pages 421–457. PMLR, 2021. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhao-2023-provable-robust-watermarking-ai-generated/