SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints

Benjamin D. Kim; Wanrong Zhang; Weitong Ruan; Lav R. Varshney; Daniel Alabi

cs.CROct 5, 2026

SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints

Authors: Benjamin D. Kim, Wanrong Zhang, Weitong Ruan, Lav R. Varshney, Daniel Alabi

Organizations: Massachusetts Institute of Technology · Amazon · Stony Brook University · University of Illinois Urbana-Champaign

Abstract

We introduce a framework for multi-bit text watermarking with security defined directly through $f$ -divergence from the base language model distribution. Unlike prior approaches that focus on average-key distortion-freeness or a particular statistical distance, our formulation supports general $f$ -divergences, including total variation and KL divergence, and enforces the guarantee for each realized key and embedded message. We develop a coding-based watermarking scheme that optimally biases next-token distributions subject to a prescribed divergence budget, and characterize the resulting tradeoff between embedding rate, decoding reliability, and statistical security. Experimentally, we compare our method against prior multi-bit watermarking schemes across modern language models and payload regimes. Our approach achieves substantially lower watermark detectability while maintaining competitive message-recovery performance and generation quality. Our results provide a unified view of secure multi-bit watermarking and recover several commonly used security notions as special cases.

Figures & tables

Figure 1: Watermark encoding and embedding process for SimpleMark : the watermarker starts by truncating the language model support according to the top- $q$ , and places all the tokens on a $q-$ ary simplex. Using the message $M$ and the generator matrix $G$ to create a codeword $C$ , and computes the target vertex on the simplex, depicted in red in the diagram. The watermarker biases the watermarked distribution towards this token by $\alpha$ , and reduces the probability of sampling other tokens by $\beta$ while remaining in the $\varepsilon$ parameter $f$ -divergence budget, $D_{f}(Q_{t}^{*}\|Q_{t})\leq\varepsilon$ , and samples from the watermarked distribution $Q_{t}^{*}$ . The message can then be decoded with one of the decoders. A detailed procedure is in Section 3.1 .

Watermark	Per-token watermark- specific overhead	Decoding cost
ArcMark	$O(I\,\|\mathcal{V}\|\,r)$	$O\!\left(n(\|\mathcal{V}\|+2^{b})\right)$
BiMark	$O(d\,\|\mathcal{V}\|)$	$O(nd+b)$
StealthInk	$O(\|\mathcal{V}\|)$	$O\!\left(n\|\mathcal{V}\|+(b/c)2^{c}\right)$
MC 2 Mark	$O\!\left(m\|\mathcal{V}\|+m\tbinom{n^{\prime}}{n^{\prime}/2}n^{\prime}\right)$	$O(n\,m\,n^{\prime}+b)$
QuantileMark	$O(\|\mathcal{V}\|\log\|\mathcal{V}\|+M)$	$O\!\left(n(\|\mathcal{V}\|\log\|\mathcal{V}\|+M)+(b/m^{\prime})M\right)^{\dagger}$
MirrorMark	$O(L\,\|\mathcal{V}\|)$	$O\!\left(n(b/c+2^{c}L)\right)$

Table 1: Complexity comparison between SimpleMark and other known multi-bit watermark schemes. † Note the decoder requires a model replay. We assume

q=53

as a small constant. With respect to the complexities, the symbols can be defined as

|\mathcal{V}|

: vocabulary;

n

: text length;

b

: payload bits. Method-specific symbols:

r

: side-information resolution and

I

: Sinkhorn iteration count for ArcMark ( Gilani et al., 2026 ) ;

d

: reweighting layers for BiMark ( Feng et al., 2025 ) (

d{=}10

);

m

: channel layers and

n^{\prime}

: segment length in bits for MC 2 Mark ( Cui et al., 2026 ) (

m{=}10

;

n^{\prime}

unspecified in their experiments);

c

: bits per message chunk for StealthInk ( Jiang et al., 2025 ) and MirrorMark ( Jiang et al., 2026 ) (

c{=}1

and

c{=}2

respectively; both papers denote this

m

);

L

: tournament layers for MirrorMark (

L{=}30

M

: quantile bins per step for QuantileMark ( Zhu et al., 2026 ) (

M=2^{m^{\prime}}

with

m^{\prime}

bits per message symbol).

Figure 2: Empirical total variation distance and distinguishing bound from an unwatermarked output and a watermarked output for a baseline, SimpleMark , Bimark, and ArcMark . The full bars represent Qwen3.5-9B-Base and the dashed bars represent Llama3.1-8B-Instruct.

Scheme	GSM8K	GPQA-D	LCB	AIME 2024
(trials)	(300)	(198)	( $100$ )	( $30$ )
3-bit payload
SimpleMark TV ( $\varepsilon{=}0.05$ , $\alpha_{\max}{=}1500$ )	278	112	33	8
SimpleMark KL ( $\varepsilon{=}0.05$ , $\alpha_{\max}{=}1500$ )	274	108	40	9
BiMark	270	107	33	11
ArcMark	272	111	35	10

Table 2: Reasoning performance on tasks for Qwen3.5-9B (thinking mode, temperature 0.6) on GSM8K (300 problems), GPQA-Diamond (198 problems), LiveCodeBench (100 problems, graded on public test cases only, so counts are only comparable across schemes) and AIME 2024 (30 problems). We use identical tasks and datasets for every benchmark. We evaluate SimpleMark at two operating points (

q{=}53

, TV or KL

\varepsilon=0.05

, cap

\alpha_{\max}{=}1500

), BiMark, ArcMark, and no watermark.

Figure 3: Perplexity results for token outputs ranging from 50-300 tokens for SimpleMark , ArcMark , and Bimark. A low KL $\varepsilon$ -budget SimpleMark is consistently closest to that of the unwatermarked output.

Figure 4: Message recovery for a variable length prefix of a 300 token sequence. For $\varepsilon\in\{0.05,0.1,0.15\}$ . The SimpleMark decoding capabilities outperform the current SOTA at $\varepsilon=0.15,$ and remain competitive with lower, more practical $\varepsilon$ budgets.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

(V_{t},\sigma_{t})\leftarrow\mathrm{Hash}(K,\,X_{t-h:t-1}),

Appendix

Algorithm 1 Per-key divergence-constrained encoder

z_{t}(a)=(a+v_{t})\bmod q,\qquad B_{a}\leftarrow\sum_{x\,:\,\sigma_{t}(x)=z_{t}(a)}Q_{t}(x),

Appendix

Algorithm 2 Per-key divergence-constrained MLE Decoder

Figure 5: Message recovery for a variable length prefix of a 500-1000 token sequence at various $\varepsilon$ budgets.

Scheme	GSM8K ( $n{=}300$ )	GPQA-D ( $n{=}198$ )	LCB ( $n{=}300$ )
3-bit payload
SimpleMark TV ( $\varepsilon{=}0.05$ , $\alpha_{\max}{=}1500$ )	253	58	62
SimpleMark KL ( $\varepsilon{=}0.05$ , $\alpha_{\max}{=}1500$ )	249	42	54
BiMark	251	45	58
ArcMark	249	54	65
Unwatermarked	249	56	60

Appendix

Table 3: Reasoning performance on several tasks for Llama3.1-8B-Instruct (temperature 0.6) on GSM8K (300 problems

\times

2 independent generations), GPQA-Diamond (198 problems), and LiveCodeBench (300 problems, graded on public test cases only, so counts are only comparable across schemes). We use identical tasks and datasets for every benchmark. We evaluate SimpleMark at two operating points (

q{=}53

, TV or KL

\varepsilon=0.05

, cap

\alpha_{\max}{=}1500

), BiMark, ArcMark, and no watermark.

Figure 6: Substitution for a variable percentage of tokens in a 300 token sequence. For $\varepsilon\in\{0.05,0.15\}$ , and context hashing window $h=2,3$ . SimpleMark is decently robust to substitution edit attacks.

Figure 7: Zero-bit detection for SimpleMark , ArcMark , and Bimark at different FPR. At higher distortion budgets we see overall improvement on the baselines for detection rate. For lower distortion budgets we stay closer to the unwatermarked distribution, so naturally we see lower detection rates.

Figure 8: Message recovery for a variable length prefix of a 300 token sequence for $q=\{29,53\}$ at various $\varepsilon$ budgets.

Figure 9: Perplexity with different parameters for $q=\{29,53\}$ . Both remain close to the unwatermarked baselines.

Figure 10: Reasoning for SimpleMark under the different parameter sizes and $\alpha_{\max}$ .

Explore similar work

CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding
Sep 27, 2026Paweł Batorski, Przemysław Spurek, Paul SwobodaWatermarks Decoding
Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute
Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark
May 12, 2026Thibaud Gloaguen, Robin Staab, Mark Vero +1Large Language Model Watermarks Watermarks
ETH Zurich
Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking
May 1, 2026Joeun Kim, HoEun Kim, Dongsup Jin +1Large Language Model Watermarks Multi-Bit Watermarking
Department of AI, DGIST, Daegu, Republic of Korea · Department of ICT Convergence, University of Ulsan, Ulsan, Republic of Korea · Department of EECS, DGIST, Daegu, Republic of Korea

Sep 27, 2026, cs.CLJ/K move · Enter open · S save

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

Paweł Batorski, Przemysław Spurek, Paul Swoboda

Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute

Watermarks Decoding Next-Token Distribution

Open paper AskPDF 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.

Abstract

Explore similar work

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

Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark

Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking