# Watermarking Language Models for Many Adaptive Users

arXiv: https://arxiv.org/abs/2405.11109 · HTML: https://mlsanity.com/paper/2405.11109/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 17 May 2024.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 15 of 15)

- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [HiDDeN: Hiding Data With Deep Networks](https://mlsanity.com/paper/1807.09937/) (2018)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [Generating Steganographic Images via Adversarial Training](https://mlsanity.com/paper/1703.00371/) (2017)
- [A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules](https://mlsanity.com/paper/2404.01245/) (2024)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Learning to Watermark LLM-generated Text via Reinforcement Learning](https://mlsanity.com/paper/2403.10553/) (2024)
- [Towards Better Statistical Understanding of Watermarking LLMs](https://mlsanity.com/paper/2403.13027/) (2024)
- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)
- [Who Followed the Blueprint? Analyzing the Responses of U.S. Federal Agencies to the Blueprint for an AI Bill of Rights](https://mlsanity.com/paper/2404.19076/) (2024)

## Built on by (most cited first, 18 of 18)

- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [BiMark: Unbiased Multilayer Watermarking for Large Language Models](https://mlsanity.com/paper/2506.21602/) (2025)
- [Verifying LLM Inference to Detect Model Weight Exfiltration](https://mlsanity.com/paper/2511.02620/) (2025)
- [Multi-Designated Detector Watermarking for Language Models](https://mlsanity.com/paper/2409.17518/) (2024)
- [FDLLM: A Dedicated Detector for Black-Box LLMs Fingerprinting](https://mlsanity.com/paper/2501.16029/) (2025)
- [SAMark: A Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness](https://mlsanity.com/paper/2605.25796/) (2026)
- [LLM-Text Watermarking based on Lagrange Interpolation](https://mlsanity.com/paper/2505.05712/) (2025)
- [Ideal Attribution and Faithful Watermarks for Language Models](https://mlsanity.com/paper/2512.07038/) (2025)
- [AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing](https://mlsanity.com/paper/2605.29434/) (2026)
- [LLM Watermarking as Big Data Provenance: A Deployment-Oriented Systematization](https://mlsanity.com/paper/2607.10103/) (2026)
- [Watermark Forensics for Generative Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2607.13003/) (2026)
- [Watermark Smoothing Attacks against Language Models](https://mlsanity.com/paper/2407.14206/) (2024)
- [An LLM Framework For Cryptography Over Chat Channels](https://mlsanity.com/paper/2504.08871/) (2025)
- [WorldCup Sampling for Multi-bit LLM Watermarking](https://mlsanity.com/paper/2602.01752/) (2026)
- ["AI Watermarking": Bridging Policy Discourse and Technical Capabilities](https://mlsanity.com/paper/2606.28331/) (2026)
- [A Trustworthy Watermarking Framework for LLM-Generated Food Safety Content](https://mlsanity.com/paper/2609.06708/) (2026)
- [Who Is Behind the Harness? Fingerprinting LLMs through Agentic Behavior](https://mlsanity.com/paper/2609.28559/) (2026)
- [SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints](https://mlsanity.com/paper/2610.05712/) (2026)

## Abstract (arXiv)

We study watermarking schemes for language models with provable guarantees. As we show, prior works offer no robustness guarantees against adaptive prompting: when a user queries a language model more than once, as even benign users do. And with just a single exception (Christ and Gunn, 2024), prior works are restricted to zero-bit watermarking: machine-generated text can be detected as such, but no additional information can be extracted from the watermark. Unfortunately, merely detecting AI-generated text may not prevent future abuses. We introduce multi-user watermarks, which allow tracing model-generated text to individual users or to groups of colluding users, even in the face of adaptive prompting. We construct multi-user watermarking schemes from undetectable, adaptively robust, zero-bit watermarking schemes (and prove that the undetectable zero-bit scheme of Christ, Gunn, and Zamir (2024) is adaptively robust). Importantly, our scheme provides both zero-bit and multi-user assurances at the same time. It detects shorter snippets just as well as the original scheme, and traces longer excerpts to individuals. The main technical component is a construction of message-embedding watermarks from zero-bit watermarks. Ours is the first generic reduction between watermarking schemes for language models. A challenge for such reductions is the lack of a unified abstraction for robustness -- that marked text is detectable even after edits. We introduce a new unifying abstraction called AEB-robustness. AEB-robustness provides that the watermark is detectable whenever the edited text "approximates enough blocks" of model-generated output.