Certmark enables reliable hidden messages without hurting text quality
CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding
Computation and Language
Summary
Watermarks are hidden messages that can be added to texts to prove where they came from, but usually changing the text to insert these messages can make the text worse or easier to spot. The authors introduce CertMark, which hides messages in a way that does not change the way a language model generates text, preserving its quality. They also created ways to decode these messages with strong guarantees that the decoded message is correct or to abstain when unsure. Their method works well for various types of text and recovers messages better than previous techniques without reducing text quality.
What this means in practice
- •For language model developers: Embed multi-bit watermarks that do not affect generated text quality while ensuring reliable message recovery with certified error bounds.
- •For content verification teams: Use certified decoders to verify embedded watermarks in generated texts and abstain when decoding confidence is low, reducing false detections.
Authors
Paweł Batorski, Przemysław Spurek, Paul Swoboda
Abstract
Leading multi-bit watermarking methods for language models encode messages by biasing the model's next-token probabilities, creating a trade-off between message recovery and text quality. Their decoders typically return the highest-scoring candidate from accumulated token-level evidence, without a certified abstention rule that bounds the probability of outputting an incorrect message. We introduce CertMark, a distribution-preserving multi-bit watermark with certified decoding. Rather than modifying probabilities, CertMark uses the embedded message to seed an exact Gumbel-max sampler, thereby preserving the model's original sampling distribution. We propose two scalable decoders: a model-agnostic, text-only decoder and a model-aware variant that leverages the original next-token distributions for stronger recovery. Both support certified abstention with mathematical bounds on the probability of returning an incorrect message. Across text completion, summarization, and story generation, CertMark matches the perplexity of unwatermarked text while reliably recovering multi-bit messages. The model-aware decoder further achieves higher bit accuracy than probability-biasing baselines. Our code is publicly available at https://github.com/Batorskq/CertMark.