Elamur Research⌕
☰
home / papers / 2023 / Robust Distortion-free Watermarks for Language Models

Robust Distortion-free Watermarks for Language Models

Paper · 2023 · Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto et al.

Summary

The paper tackles provenance of LM-generated text. It seeks a watermark that leaves the model's output distribution unchanged (distortion-free), can be verified without access to the model or prompt (agnostic), and survives editing (robust). Earlier hashing-based schemes (Kirchenbauer et al., Aaronson, Christ et al.) fall short on at least one of these. In the proposed protocol, the provider and detector share a secret key that encodes a sequence of random numbers. Generation deterministically turns this sequence into a model sample, using either inverse transform sampling (ITS) or exponential minimum sampling (EXP). A shift wrapper starts from a random offset so that outputs vary across calls. Detection aligns a suspect text against the key sequence using robust sequence-alignment costs, which yields a p-value. Experiments cover OPT-1.3B, LLaMA-7B and Alpaca-7B. The EXP variant is the strongest, staying detectable from short passages even after heavy random edits. Detection is harder on low-entropy instruction responses. The work matters because it shows watermarking need not trade output quality for robustness, and the code is publicly released.

Key points

  • Robustness to edits: On OPT-1.3B and LLaMA-7B, 35 tokens suffice for detection at p ≤ 0.01, even with 40–50% of tokens randomly substituted, inserted or deleted.
  • Robustness to translation: Text paraphrased by round-trip translation through French or Russian remains detectable from about 50 tokens.
  • Alpaca-7B case study: Only about 25% of instruction responses (median length around 100 tokens) are detectable at p ≤ 0.01, and robustness to automated paraphrasing is weaker.
  • Detection runtimes: With key length n = 10,000 on an Apple M2 laptop, the test statistics take about 0.004 s (ITS), 0.60 s (ITS-edit), 2.20 s (EXP) and 3.21 s (EXP-edit).
  • Practical recommendations: A small key (n = 256) does not noticeably harm text quality. EXP-edit is advised when robustness matters, and ITS when high-throughput detection matters, since it reduces to maximum inner-product search. Code is at github.com/jthickstun/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.

 Institutions

🎓Stanford UniversityStanford · United States506 works · 330,052 citations

 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

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto and Percy Liang. 2023. Robust Distortion-free Watermarks for Language Models. arXiv:2307.15593.

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

@misc{kuditipudi2023robust,
  title = {{Robust Distortion-free Watermarks for Language Models}},
  author = {Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto and Percy Liang},
  year = {2023},
  doi = {10.48550/arxiv.2307.15593},
  eprint = {2307.15593},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2307.15593}
}

References

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

  1. S. Aaronson. ‘Reform’ AI Alignment with Scott Aaronson. AXRP - the AI X-risk Research Podcast, 2023. URL https://axrp.net/episode/2023/04/11/ episode-20-reform-ai-alignment-scott-aaronson.html. ↗
  2. S. Abdelnabi and M. Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In IEEE Symposium on Security and Privacy, 2021. find
  3. M. J. Atallah, V. Raskin, M. Crogan, C. Hempelmann, F. Kerschbaum, D. Mohamed, and S. Naik. Natural language watermarking: Design, analysis, and a proof-of-concept implementation. In Information Hiding: 4th International Workshop, IH 2001 Pittsburgh, PA, USA, April 25–27, 2001 Proceedings 4, pages 1… find
  4. T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems 33, 33:1877–1901, 2020.
  5. M. Christ, S. Gunn, and O. Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194, 2023. — [arXiv:2306.09194](https://arxiv.org/abs/2306.09194) find
  6. F. Dai and Z. Cai. Towards near-imperceptible steganographic text. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4303–4308, 2019. find
  7. G. Elfving, G. Birkhoff, and R. von Mises. Vol. 2. probability and statistics, General. In Selected Papers of Richard von Mises. American Mathematical Society, 1966. find
  8. X. He, Q. Xu, L. Lyu, F. Wu, and C. Wang. Protecting intellectual property of language generation APIs with lexical watermark. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022. find
  9. X. He, Q. Xu, Y. Zeng, L. Lyu, F. Wu, J. Li, and R. Jia. Cater: Intellectual property protection on text generation apis via conditional watermarks. In Advances in Neural Information Processing Systems 35, 2022. find
  10. G. Jawahar, M. Abdul-Mageed, and V. Laks Lakshmanan. Automatic detection of machine generated text: A critical survey. In International Conference on Computational Linguistics, 2020.
  11. N. S. Kamaruddin, A. Kamsin, L. Y. Por, and H. Rahman. A review of text watermarking: theory, methods, and applications. IEEE Access, 2018. find
  12. S. Katzenbeisser and F. Petitcolas. Digital watermarking. Artech House, London, 2:2, 2000. find
  13. J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein. A watermark for large language models. arXiv preprint arXiv:2301.10226, 2023.
  14. E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn. Detectgpt: Zero-shot machine-generated text detection using probability curvature. arXiv preprint arXiv:2301.11305, 2023.
  15. G. Papandreou and A. L. Yuille. Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. 2011 International Conference on Computer Vision, pages 193–200, 2011. find
  16. C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. 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.
  17. S. G. Rizzo, F. Bertini, and D. Montesi. Fine-grain watermarking for intellectual property protection. EURASIP Journal on Information Security, 2019. find
  18. J. Shen, H. Ji, and J. Han. Near-imperceptible neural linguistic steganography via self-adjusting arithmetic coding. In Proceedings of Empirical Methods for Natural Language Processing, pages 303–313, 2020. find
  19. R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto. Stanford alpaca: An instruction-following llama model. https://github.com/tatsu-lab/stanford_alpaca, 2023. ↗
  20. J. Tiedemann and S. Thottingal. OPUS-MT — Building open translation services for the World. In Proceedings of the 22nd Annual Conference of the European Association for Machine Translation, 2020. find
  21. J. Tiedemann, M. Aulamo, D. Bakshandaeva, M. Boggia, S.-A. Grönroos, T. Nieminen, A. Raganato, Y. Scherrer, R. Vazquez, and S. Virpioja. Democratizing machine translation with opus-mt. arXiv preprint arXiv:2212.01936, 2022. — [arXiv:2212.01936](https://arxiv.org/abs/2212.01936) find
  22. H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
  23. H. Ueoka, Y. Murawaki, and S. 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
  24. A. Venugopal, J. Uszkoreit, D. Talbot, F. J. Och, and J. Ganitkevitch. Watermarking the outputs of structured prediction with an application in statistical machine translation. In Proceedings of Empirical Methods for Natural Language Processing, 2011. find
  25. J. Vincent. AI-generated answers temporarily banned on coding Q&A site Stack Overflow. The Verge, 2022. URL https://www.theverge.com/2022/12/5/23493932/ chatgpt-ai-generated-answers-temporarily-banned-stack-overflow-llms-dangers. ↗
  26. M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. find
  27. X. Yang, J. Zhang, K. Chen, W. Zhang, Z. Ma, F. Wang, and N. Yu. Tracing text provenance via context-aware lexical substitution. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022. find
  28. S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022.
  29. X. Zhao, Y.-X. Wang, and L. Li. Protecting language generation models via invisible watermarking. arXiv preprint arXiv:2302.03162, 2023. — [arXiv:2302.03162](https://arxiv.org/abs/2302.03162) find
  30. Z. Ziegler, Y. Deng, and A. M. Rush. Neural linguistic steganography. In Proceedings of Empirical Methods for Natural Language Processing, pages 1210–1215, 2019. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kuditipudi-2023-robust-distortion-free-watermarks-language/