CS Paper Radar

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

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

cs.CR cs.AIcs.IT ·submitted 2026-10-05 02:51 UTC · v1

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.

Comment
39 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Look It Up: Multi-bit LLM Watermarking via Codebook Search

cs.CR cs.AIcs.CL ·2026-11-12 ·Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk
code/data similarity 0.81
Abstract · 16 pages, 8 figures, 6 tables. Submitted to IEEE Transactions on Information Forensics and Security. Code: https://github.com/jaroslawjanas/…

Attributing short LLM-generated texts to a specific source remains challenging for existing multi-bit watermarking methods, which often require long generations or costly decoding to recover payloads reliably. We propose a codebook-based watermarking scheme that maps an $n$-bit payload to a longer $u$-bit codeword and embeds it during generation through token-level logit biasing. During extraction, the received bit sequence is matched to the nearest codeword in a precomputed secret codebook using Hamming or Levenshtein distance. Experiments show that our method achieves near-perfect recovery for 16-24 bit payloads on 200-token generations and strong performance on 127-token generations for base models. Results are weaker on some instruction-tuned models with very short texts, where low-entropy output distributions reduce embedding reliability. We also study a BCH-based variant that avoids codebook storage but generally reduces robustness. The Levenshtein variant improves resilience to deletions and light paraphrasing, while insertions and stronger rewrites remain challenging. We analyze collision probability, codeword separation, extraction time, tokenization consistency, and text quality, highlighting both the practicality and limitations of codebook-based watermarking for short-form attribution.

0.32

TTMark: Pairwise Distortion-Free Watermarking Beyond Single-Token Entropy

cs.CR cs.CL ·2026-09-28 ·Ruibo Chen, Zhengmian Hu, Donghang Lu, Xuehao Cui, Georgios Milis +3 more
similarity 0.80
Abstract

Distortion-free watermarking enables reliable attribution of machine-generated text while preserving output distribution. However, existing methods operate independently on each generated token, making their detection capability fundamentally constrained by the entropy of the next-token distribution. We present Tandem Token WaterMark (TTMARK), a general pairwise watermarking framework that extends distortion-free watermarking from individual tokens to adjacent token pairs. By watermarking the joint distribution of consecutive tokens, TTMARK enlarges the effective watermarking alphabet from V to $V^2$, allowing the detector to exploit both token entropy and conditional entropy while preserving distortion-freeness over the joint distribution. We further introduce a branch-isolating concatenated tandem generation algorithm that efficiently constructs the joint distribution in a single forward pass. Theoretically, we show that pairwise watermarking achieves better expected detection strength in low-entropy regimes. Extensive experiments across multiple language models, datasets, and three representative distortion-free watermarking schemes demonstrate that TTMARK consistently improves detectability without degrading generation quality, while also improving robustness to edits and substantially enhancing localized watermark detection.

0.22

WeaveMark: Robust and Scalable Multi-bit LLM Watermarking via Coded Payload Spreading

cs.CR cs.LG ·2026-09-02 ·Gang-Hyun Park, Ju-Hyeong Lee, Hee-Youl Kwak, Dae-Young Yun
code/data similarity 0.78
Abstract · 22 pages, 11 figures, 16 tables. v2: added extended comparisons (payload scalability, generalization across model families), additional robu…

Multi-bit watermarking for large language models enables content source tracing by embedding user-identifiable messages into generated text. Existing methods face a fundamental trade-off among extraction accuracy, text quality, and payload capacity. We propose WeaveMark, a robust and scalable multi-bit LLM watermarking scheme based on coded payload spreading. WeaveMark shifts this trade-off frontier by improving payload capacity through multi-bit-per-token spreading (weaving), improving extraction accuracy through soft-decision error-correcting codes, and preserving text quality through unbiased multilayer reweighting. It further introduces dedicated zero-bit layers for reliable watermark presence detection. Extensive experiments demonstrate substantial gains in extraction performance, especially for long messages and edited text, without degrading text quality. WeaveMark achieves an 89.8% match rate for 32-bit messages at 200 tokens, compared with 20.8% for BiMark. Under 10% substitution attacks on 16-bit messages at 200 tokens, it maintains 86.0% versus 30.7%. Code is available at https://anonymous.4open.science/r/WeaveMark-ED6F.

0.59

ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models

cs.CR cs.LGstat.ML ·2026-10-10 ·Xiaopu Wang, Runze Li
similarity 0.78
Abstract

As watermarking of LLM-generated text enters deployment, users increasingly need to check text whose source is unknown. Existing detectors read the watermark through a specific tokenizer or embedding pipeline, and even if all providers adopted the same watermarking method, differences in these representations would leave their watermarks incompatible, and the text alone does not reveal which representation produced it. We propose ByteMark, a unified watermarking scheme that defines its signal on the UTF-8 bytes of published text. Models with different tokenizers embed this signal under one public specification and key, and a single detector verifies the text from the text and key alone. When the tokenizer or embedding model of a baseline detector is replaced, its detection degrades sharply, whereas ByteMark, which uses neither, retains its detection rate; ByteMark also remains detectable when participating models continue or rewrite the text.

0.19

PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution

cs.CR ·2026-08-23 ·Yaofei Wang, Jinyang Guo, Shuchao Du, Chao Wang, Qiyi Yao +4 more
top venuecode/data similarity 0.76
Abstract · Accepted to ACM CCS 2026

Fine-grained attribution of AI-generated text is becoming increasingly important for accountability and auditing, yet existing multi-bit watermarking methods still struggle to simultaneously preserve the base generation distribution, support high-capacity payloads, and remain recoverable after editing. We present PURA, a provably unbiased and robust multi-bit watermarking method for text attribution. Instead of perturbing token probabilities directly, PURA embeds payloads in the latent sampling space via keyed inverse transform sampling, and recovers them by treating observed tokens as soft interval evidence and aggregating such evidence across the sequence. This design preserves the base generation distribution exactly while substantially improving recovery stability under post-editing and channel perturbations. Building on this recovery paradigm, we further develop a unified robustness analysis and show that, under bounded attack strength, the per-bit error probability decays exponentially with sequence length. Extensive experiments show that PURA substantially outperforms existing unbiased baselines in the high-payload regime. For example, when embedding 36 bits in 200 tokens, PURA achieves a 91.7\% message match rate, more than three times that of the strongest unbiased baseline, while preserving text quality and remaining statistically close to unwatermarked text, and incurring only millisecond-level verification overhead. Our code is available at

0.57

A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models

cs.CR cs.AI ·2026-10-20 ·Romina Omidi, Nima Naderloui, Yuan Hong, Binghui Wang
theory similarity 0.76
Abstract · Correct the affiliation information and add a link to the source code

Watermarking has emerged as a key tool for identifying text generated by large language models (LLMs), with current schemes embedding statistical signals into the generation process to enable later detection. In this work, we identify a shared weakness across a broad class of popular LLM watermarking methods, including KGW (and its variants), GumbelSoft, DipMark, ITS, and SynthID. We show that these schemes exhibit a fundamental link between their detection scores and the token probability shifts they introduce during generation. This link, which we call score-ratio alignment, allows an attacker with only black-box query access to the model--and no knowledge of secret keys or model weights--to produce text that evades detection while remaining fluent and natural. We prove that the resulting attack is optimal across all covered watermark families, and show that the weakness is intrinsic: any watermark designed to maximize statistical detection power necessarily induces the very structure that attackers can exploit. We evaluate our attack on seven popular generative LLM watermarking schemes, three LLMs, and tasks, which reduce detection rates to at most 0.05 across all settings while preserving text quality. Our findings show that current watermarking methods can be reliably defeated under realistic attack conditions, highlighting the need for fundamentally different watermarking designs that decouple detection scores from token probability shifts.

0.13

Fundamental Limits of Statistical Watermarking for LLMs with Fixed and Optimizable Common Randomness

cs.IT cs.CR ·2026-11-14 ·Haiyun He, Yepeng Liu, Zhuoer Shen, Ziqiao Wang, Yongyi Mao +1 more
similarity 0.75
Abstract

Watermarking has emerged as an important technique for distinguishing AI-generated text from human-written text. However, most existing work is primarily empirical, relies on ad hoc watermarking designs, and lacks a fundamental understanding of the performance limits. In this paper, we propose a unified theoretical framework for statistical watermarking of large language models (LLMs), casting the problem as an independence test between generated text and common randomness and jointly designing the watermarking embedder and the detector. Our objective is to maximize detection power while controlling the worst-case false positive rate (FPR) and limiting distortion to text quality. A central focus of our framework is the design of the common randomness, which plays a critical role in both watermark embedding and detection. We characterize the fundamental limits of statistical watermarking under both fixed and optimizable common randomness. Our results show that optimizing the common randomness does not improve the fundamental limits: the best achievable performance is the same as that with fixed common randomness. Nevertheless, common randomness design remains highly important because it can substantially simplify detector design. In particular, with optimizable common randomness, a fixed, deterministic, and model-agnostic detector can achieve optimal performance. We further study a practical setting with fixed uniform common randomness and a fixed deterministic detector, and characterize its performance gap relative to the optimizable case, thereby demonstrating the practical value of optimizable common randomness.

0.07

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

cs.CL ·2026-09-27 ·Paweł Batorski, Przemysław Spurek, Paul Swoboda
code/data similarity 0.75
Abstract

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.

0.50