# Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 27 of its 36 references that are in the map.
- First posted on arXiv 9 Apr 2026.

## 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, 27 of 27)

- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [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)
- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [On the Learnability of Watermarks for Language Models](https://mlsanity.com/paper/2312.04469/) (2023)
- [Adaptive Text Watermark for Large Language Models](https://mlsanity.com/paper/2401.13927/) (2024)
- [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)
- [Towards Codable Watermarking for Injecting Multi-bits Information to LLMs](https://mlsanity.com/paper/2307.15992/) (2023)
- [CodeMark: Imperceptible Watermarking for Code Datasets against Neural Code Completion Models](https://mlsanity.com/paper/2308.14401/) (2023)
- [Optimizing watermarks for large language models](https://mlsanity.com/paper/2312.17295/) (2023)
- [DeepTextMark: A Deep Learning-Driven Text Watermarking Approach for Identifying Large Language Model Generated Text](https://mlsanity.com/paper/2305.05773/) (2023)
- [Learning to Watermark LLM-generated Text via Reinforcement Learning](https://mlsanity.com/paper/2403.10553/) (2024)
- [Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach](https://mlsanity.com/paper/2410.02890/) (2024)
- [Necessary and Sufficient Watermark for Large Language Models](https://mlsanity.com/paper/2310.00833/) (2023)
- [Improved Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2502.11268/) (2025)
- [StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models](https://mlsanity.com/paper/2506.05502/) (2025)
- [Multi-Bit Distortion-Free Watermarking for Large Language Models](https://mlsanity.com/paper/2402.16578/) (2024)
- [Duwak: Dual Watermarks in Large Language Models](https://mlsanity.com/paper/2403.13000/) (2024)
- [Watermarking Language Models with Error Correcting Codes](https://mlsanity.com/paper/2406.10281/) (2024)
- [Optimized Couplings for Watermarking Large Language Models](https://mlsanity.com/paper/2505.08878/) (2025)
- [A Reinforcement Learning Framework for Robust and Secure LLM Watermarking](https://mlsanity.com/paper/2510.21053/) (2025)
- [Deep Learning-based Dual Watermarking for Image Copyright Protection and Authentication](https://mlsanity.com/paper/2502.18501/) (2025)

## Abstract (arXiv)

This paper considers the problem of multi-bit generative watermarking for large language models under a worst-case false-alarm constraint. Prior work established a lower bound on the achievable miss-detection probability in the finite-token regime and proposed a scheme claimed to achieve this bound. We show, however, that the proposed scheme is in fact suboptimal. We then develop two new encoding-decoding constructions that attain the previously established lower bound, thereby completely characterizing the optimal multi-bit watermarking performance. Our approach formulates the watermark design problem as a linear program and derives the structural conditions under which optimality can be achieved. In addition, we identify the failure mechanism of the previous construction and compare the tradeoffs between the two proposed schemes.