Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints
2026-04-09 • Information Theory
Information TheoryComputation and Language
AI summaryⓘ
The authors study how to hide multiple bits of information in text generated by large language models, making sure that false alarms are kept very low. They found that a previous method, which was thought to be the best, actually wasn't optimal. The authors then created two new methods that achieve the best possible performance for embedding watermarks in generated text. They also explain why the old method failed and how their new methods differ in tradeoffs.
multi-bit watermarkinglarge language modelsfalse-alarm constraintmiss-detection probabilitylinear programmingencoding-decoding schemesfinite-token regimeoptimality conditions
Authors
Yu-Shin Huang, Chao Tian, Krishna Narayanan
Abstract
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.