The paper introduces CertMark, a multi-bit watermarking method for language models that preserves the original text distribution by using the embedded message to seed an exact Gumbel-max sampler. Unlike prior methods that bias token probabilities, CertMark distorts neither the sampling process nor text quality. Two decoders are proposed: a text-only decoder that works without model access and a model-aware decoder that leverages the original next-token distributions for stronger recovery, both providing certified abstention with bounds on the probability of returning an incorrect message.
Experiments on text completion, summarization, and story generation show that CertMark matches the perplexity of unwatermarked text while reliably recovering multi-bit messages. The model-aware decoder achieves higher bit accuracy than probability-biasing baselines, and both decoders maintain their certified guarantees in practice. The method is evaluated on two model families (Qwen3.5-4B and Llama-3.1-8B) across standard benchmarks.
CertMark is notable as the first distortion-free multi-bit watermark with certified recovery. It removes the trade-off between message detection and text quality, and the certified decoder provides mathematical guarantees that strengthen accountability in deployment.