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 α , and reduces the probability of sampling other tokens by β while remaining in the ε parameter f -divergence budget, Df(Qt∗∥Qt)≤ε , and samples from the watermarked distribution Qt∗ . 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∣V∣r)
O(n(∣V∣+2b))
BiMark
O(d∣V∣)
O(nd+b)
StealthInk
O(∣V∣)
O(n∣V∣+(b/c)2c)
MC 2 Mark
O(m∣V∣+m(n′/2n′)n′)
O(nmn′+b)
QuantileMark
O(∣V∣log∣V∣+M)
O(n(∣V∣log∣V∣+M)+(b/m′)M)†
MirrorMark
O(L∣V∣)
O(n(b/c+2cL))
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 ∣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′ : segment length in bits for MC 2 Mark ( Cui et al., 2026 ) ( m=10 ; n′ 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=2m′ with m′ 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 ( ε=0.05 , αmax=1500 )
278
112
33
8
SimpleMark KL ( ε=0.05 , α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 ε=0.05 , cap α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 ε -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 ε∈{0.05,0.1,0.15} . The SimpleMark decoding capabilities outperform the current SOTA at ε=0.15, and remain competitive with lower, more practical ε budgets.
Figure 5: Message recovery for a variable length prefix of a 500-1000 token sequence at various ε budgets.
Scheme
GSM8K ( n=300 )
GPQA-D ( n=198 )
LCB ( n=300 )
3-bit payload
SimpleMark TV ( ε=0.05 , αmax=1500 )
253
58
62
SimpleMark KL ( ε=0.05 , α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 × 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 ε=0.05 , cap αmax=1500 ), BiMark, ArcMark, and no watermark.
Figure 6: Substitution for a variable percentage of tokens in a 300 token sequence. For ε∈{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 ε 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 αmax .
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.
Paweł Batorski, Przemysław Spurek, Paul Swoboda
Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute
With LLM watermarking already being deployed commercially, practical applications increasingly require multibit watermarks that encode more complex payloads, such as user IDs or timestamps, into the generated text. In this work, we propose a fundamentally new approach for multibit watermarking: introducing binomial encoding to directly encode every bit of the payload at every token position. We complement our approach with a stateful encoder that during generation dynamically redirects encoding pressure toward underencoded bits. Our evaluation against 8 baselines on up to 64-bit payloads shows that our scheme achieves superior message accuracy and robustness, with the gap to baseline methods widening in more relevant settings (i.e., large payloads and low-distortion regimes). At the same time, we challenge prior works' evaluation metrics, highlighting their lack of practical insights, and introduce per-bit confidence scoring as a practically relevant metric for evaluating multibit LLM watermarks.
Recent multi-bit watermarking methods for large language models (LLMs) prioritize capacity over reliability, often conflating decoding with detection. Our analysis reveals that existing ECC-based extractors suffer from catastrophic false positive rates (FPR), and applying rejection thresholds merely collapses detection sensitivity (TPR) to random guessing. To resolve this structural limitation, we propose BREW (Block-wise Reliable Embedding for Watermarking), a framework shifting the paradigm to designated verification. BREW employs a two-stage mechanism: (i) blind message estimation via independent block voting, followed by (ii) window-shifting verification that rigorously validates the payload against local edits. Experiments demonstrate that BREW achieves a TPR of 0.965 with an FPR of 0.02 under 10% synonym substitution, demonstrating that the high-FPR issue is not an inherent trade-off of multi-bit watermarking, but a solvable structural flaw of prior decoding-centric designs. Our framework is model-agnostic and theoretically grounded, providing a scalable solution for reliable forensic deployment.
Joeun Kim, HoEun Kim, Dongsup Jin +1
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