# Provably Robust Multi-bit Watermarking for AI-generated Text

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

## Key facts

- Cited by 47 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 39 of its 75 references that are in the map.
- First posted on arXiv 30 Jan 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, 30 of 39)

- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [The Falcon Series of Open Language Models](https://mlsanity.com/paper/2311.16867/) (2023)
- [VideoPoet: A Large Language Model for Zero-Shot Video Generation](https://mlsanity.com/paper/2312.14125/) (2023)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (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)
- [Who Wrote this Code? Watermarking for Code Generation](https://mlsanity.com/paper/2305.15060/) (2023)
- [Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding](https://mlsanity.com/paper/2009.03015/) (2020)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [Distortion Agnostic Deep Watermarking](https://mlsanity.com/paper/2001.04580/) (2020)
- [Protecting Intellectual Property of Language Generation APIs with Lexical Watermark](https://mlsanity.com/paper/2112.02701/) (2021)
- [Three Bricks to Consolidate Watermarks for Large Language Models](https://mlsanity.com/paper/2308.00113/) (2023)
- [Robust Multi-bit Natural Language Watermarking through Invariant Features](https://mlsanity.com/paper/2305.01904/) (2023)
- [A Robust Semantics-based Watermark for Large Language Model against Paraphrasing](https://mlsanity.com/paper/2311.08721/) (2023)
- [REMARK-LLM: A Robust and Efficient Watermarking Framework for Generative Large Language Models](https://mlsanity.com/paper/2310.12362/) (2023)
- [CATER: Intellectual Property Protection on Text Generation APIs via Conditional Watermarks](https://mlsanity.com/paper/2209.08773/) (2022)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [Mark My Words: Analyzing and Evaluating Language Model Watermarks](https://mlsanity.com/paper/2312.00273/) (2023)
- [An Unforgeable Publicly Verifiable Watermark for Large Language Models](https://mlsanity.com/paper/2307.16230/) (2023)
- [Advancing Beyond Identification: Multi-bit Watermark for Large Language Models](https://mlsanity.com/paper/2308.00221/) (2023)
- [A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models](https://mlsanity.com/paper/2310.07710/) (2023)

## Built on by (most cited first, 30 of 47)

- [A Comprehensive Survey in LLM(-Agent) Full Stack Safety: Data, Training and Deployment](https://mlsanity.com/paper/2504.15585/) (2025)
- [PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints](https://mlsanity.com/paper/2509.21057/) (2025)
- [Towards Resilient Safety-driven Unlearning for Diffusion Models against Downstream Fine-tuning](https://mlsanity.com/paper/2507.16302/) (2025)
- [Topic-Based Watermarks for Large Language Models](https://mlsanity.com/paper/2404.02138/) (2024)
- [SAEMark: Steering Personalized Multilingual LLM Watermarks with Sparse Autoencoders](https://mlsanity.com/paper/2508.08211/) (2025)
- [Building Intelligence Identification System via Large Language Model Watermarking: A Survey and Beyond](https://mlsanity.com/paper/2407.11100/) (2024)
- [DREAM: Scalable Red Teaming for Text-to-Image Generative Systems via Distribution Modeling](https://mlsanity.com/paper/2507.16329/) (2025)
- [Multi-Designated Detector Watermarking for Language Models](https://mlsanity.com/paper/2409.17518/) (2024)
- [Majority Bit-Aware Watermarking For Large Language Models](https://mlsanity.com/paper/2508.03829/) (2025)
- [DMark: Order-Agnostic Watermarking for Diffusion Large Language Models](https://mlsanity.com/paper/2510.02902/) (2025)
- [iSeal: Encrypted Fingerprinting for Reliable LLM Ownership Verification](https://mlsanity.com/paper/2511.08905/) (2025)
- [MC2Mark: Distortion-Free Multi-Bit Watermarking for Long Messages](https://mlsanity.com/paper/2602.14030/) (2026)
- [Distilling the Thought, Watermarking the Answer: A Principle Semantic Guided Watermark for Large Reasoning Models](https://mlsanity.com/paper/2601.05144/) (2026)
- [A Visual Semantic Adaptive Watermark grounded by Prefix-Tuning for Large Vision-Language Model](https://mlsanity.com/paper/2601.07291/) (2026)
- [ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport](https://mlsanity.com/paper/2602.07235/) (2026)
- [XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts](https://mlsanity.com/paper/2604.05242/) (2026)
- [Verifiable Fine-Tuning for LLMs: Zero-Knowledge Training Proofs Bound to Data Provenance and Policy](https://mlsanity.com/paper/2510.16830/) (2025)
- [PVMark: Enabling Public Verifiability for LLM Watermarking Schemes](https://mlsanity.com/paper/2510.26274/) (2025)
- [Making Theft Useless: Adulteration-Based Protection of Proprietary Knowledge Graphs in GraphRAG Systems](https://mlsanity.com/paper/2601.00274/) (2026)
- [Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking](https://mlsanity.com/paper/2605.00348/) (2026)
- [IntraGuard: Committee-Side Defenses Against Review Outsourcing to Commercial Chatbots](https://mlsanity.com/paper/2605.05271/) (2026)
- [SAMark: A Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness](https://mlsanity.com/paper/2605.25796/) (2026)
- [MCGMark: An Encodable and Robust Online Watermark for Tracing LLM-Generated Malicious Code](https://mlsanity.com/paper/2408.01354/) (2024)
- [LLM-Text Watermarking based on Lagrange Interpolation](https://mlsanity.com/paper/2505.05712/) (2025)
- [On Representation Redundancy in Large-Scale Instruction Tuning Data Selection](https://mlsanity.com/paper/2602.13773/) (2026)
- [Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark](https://mlsanity.com/paper/2605.11653/) (2026)
- [Robust LLM Watermarking with Minimal Semantic Distortion for IP Protection](https://mlsanity.com/paper/2605.23175/) (2026)
- [AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing](https://mlsanity.com/paper/2605.29434/) (2026)
- [Geometric Reciprocity: Unlocking Self-Supervision for Stereoscopic Video Generation](https://mlsanity.com/paper/2607.05354/) (2026)
- [S2LM: Towards Semantic Steganography via Large Language Models](https://mlsanity.com/paper/2511.05319/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated remarkable capabilities of generating texts resembling human language. However, they can be misused by criminals to create deceptive content, such as fake news and phishing emails, which raises ethical concerns. Watermarking is a key technique to address these concerns, which embeds a message (e.g., a bit string) into a text generated by an LLM. By embedding the user ID (represented as a bit string) into generated texts, we can trace generated texts to the user, known as content source tracing. The major limitation of existing watermarking techniques is that they achieve sub-optimal performance for content source tracing in real-world scenarios. The reason is that they cannot accurately or efficiently extract a long message from a generated text. We aim to address the limitations. In this work, we introduce a new watermarking method for LLM-generated text grounded in pseudo-random segment assignment. We also propose multiple techniques to further enhance the robustness of our watermarking algorithm. We conduct extensive experiments to evaluate our method. Our experimental results show that our method substantially outperforms existing baselines in both accuracy and robustness on benchmark datasets. For instance, when embedding a message of length 20 into a 200-token generated text, our method achieves a match rate of 97.6%, while the state-of-the-art work Yoo et al. only achieves 49.2%. Additionally, we prove that our watermark can tolerate edits within an edit distance of 17 on average for each paragraph under the same setting.