# CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 3 of its 53 references that are in the map.
- First posted on arXiv 27 Sep 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, 3 of 3)

- [Multi-Bit Distortion-Free Watermarking for Large Language Models](https://mlsanity.com/paper/2402.16578/) (2024)
- [Majority Bit-Aware Watermarking For Large Language Models](https://mlsanity.com/paper/2508.03829/) (2025)
- [MirrorMark: Generalizable Mirrored Sampling for Multi-bit LLM Watermarking](https://mlsanity.com/paper/2601.22246/) (2026)

## Built on by (most cited first, 1 of 1)

- [Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key](https://mlsanity.com/paper/2610.18359/) (2026)

## Abstract (arXiv)

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.