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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Kim, B. D., Zhang, W., Ruan, W., Varshney, L. R., & Alabi, D. (2026). SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints. https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints
MLA 9
Kim, Benjamin D., et al. "SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints." https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints.
Chicago (author–date)
Kim, Benjamin D., Wanrong Zhang, Weitong Ruan, Lav R. Varshney, and Daniel Alabi. 2026. "SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints." https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints.
Harvard
Kim, B. D., Zhang, W., Ruan, W., Varshney, L. R. and Alabi, D. (2026) 'SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints', Available at: https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints.
Vancouver
Kim BD, Zhang W, Ruan W, Varshney LR, Alabi D. SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints. https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints
IEEE
B. D. Kim, W. Zhang, W. Ruan, L. R. Varshney, and D. Alabi, "SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints," https://omanscience.com/en/articles/simplemark-fast-multi-bit-text-watermarking-under-f-divergence-constraints.