SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints
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.
Related
- Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach
- Reconciling fast Hepatitis B evolutionary rates with ancient co-divergence
- Optimal Fast Charging of All-Solid-State Batteries under Cathode Transport Constraints
- Fast Relax-and-Round Unit Commitment with Topological Constraints
- A general condition for fast rates in multi-group learning
BibTeX
@misc{kim2026simplemark,
title = {{SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints}},
author = {Benjamin D. Kim and Wanrong Zhang and Weitong Ruan and Lav R. Varshney and Daniel Alabi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05712},
eprint = {2610.05712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05712},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints
AU - Benjamin D. Kim
AU - Wanrong Zhang
AU - Weitong Ruan
AU - Lav R. Varshney
AU - Daniel Alabi
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05712
UR - https://arxiv.org/abs/2610.05712
AB - 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.
ER -