Distributional Information Embedding: A Framework for Multi-bit Watermarking
This addresses the need for robust watermarking in LLMs to prevent misuse, though it is incremental as it builds on existing information embedding concepts.
The paper tackles the problem of multi-bit watermarking for large language models by introducing a distributional information embedding framework, showing that the maximum achievable watermarking rate equals the entropy of the LLM's output distribution and increases with allowable distortion.
This paper introduces a novel problem, distributional information embedding, motivated by the practical demands of multi-bit watermarking for large language models (LLMs). Unlike traditional information embedding, which embeds information into a pre-existing host signal, LLM watermarking actively controls the text generation process--adjusting the token distribution--to embed a detectable signal. We develop an information-theoretic framework to analyze this distributional information embedding problem, characterizing the fundamental trade-offs among three critical performance metrics: text quality, detectability, and information rate. In the asymptotic regime, we demonstrate that the maximum achievable rate with vanishing error corresponds to the entropy of the LLM's output distribution and increases with higher allowable distortion. We also characterize the optimal watermarking scheme to achieve this rate. Extending the analysis to the finite-token case with non-i.i.d. tokens, we identify schemes that maximize detection probability while adhering to constraints on false alarm and distortion.