CS Paper Radar

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

Yaofei Wang, Jinyang Guo, Shuchao Du, Chao Wang, Qiyi Yao, Donghui Hu, Weiming Zhang, Nenghai Yu, Kejiang Chen

cs.CR ·submitted 2026-08-23 04:44 UTC · v2
top venuecode/data

Abstract

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

Comment
Accepted to ACM CCS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CR cs.AIcs.IT ·2026-10-05 ·Benjamin D. Kim, Wanrong Zhang, Weitong Ruan, Lav R. Varshney, Daniel Alabi
similarity 0.76
Abstract · 39 pages, 10 figures

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.

0.42

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.74
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.49

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.72
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

ClockMark: Adaptive and Host-Dependent Watermarking for Large Language Models

cs.LG cs.CL ·2026-10-19 ·Yupeng Qiu, Han Fang, Ee-Chien Chang
theory similarity 0.72
Abstract

Large language model (LLM) watermarking operates on the next-token distribution that evolves during generation. In streaming generation, each sampled token becomes part of the text and affects subsequent distributions. Embedding therefore proceeds with a changing host, unlike classical watermarking, which adapts embedding to an existing host signal. To accommodate this difference, we formulate a novel embedding framework for LLM watermarking based on two principles. We first argue that embedding should be adaptive, retaining the state of previous sampling decisions to better guide subsequent choices. We further argue that embedding should be host-dependent, using the current LLM distribution to constrain both token selection and state updates. Guided by these principles and the two requirements of distribution preservation and robustness to text editing, we propose ClockMark. It combines adaptive and host-dependent embedding with message spreading, embedding the full payload in each watermarked token. Theoretically, we prove that ClockMark preserves the original LLM sequence distribution, thereby maintaining generation quality. Empirically, extensive experiments against 12 baselines demonstrate improved robustness to text editing, with gains of up to 16.08 percentage points in bit accuracy over the strongest tested baseline.

0.05

PIVOT: Distribution-Preserving Multi-BitWatermarking with Minimax-Optimal Scoring

cs.CR stat.AP ·2026-11-18 ·Wen Zhang, Kaiyi Pang, Minhao Bai, Shuyu Gan, Liping Zhu
similarity 0.71
Abstract

As LLM-generated content becomes increasingly widespread, reliable attribution calls for multi-bit watermarks that embed recoverable messages without distorting the output distribution. We introduce PIVOT, a multi-bit watermark with model-free verification based on mirrored rank-interval sampling. At each generation step, PIVOT uses a keyed pseudorandom scalar and a secret permutation of the vocabulary. The message bit determines whether next-token probability intervals are arranged in forward or reverse secret-rank order. Sampling from these mirrored layouts preserves every token probability exactly while inducing an opposite-signed dependence between the scalar and the sampled token's secret rank. This dependence yields a pivotal rank statistic whose null distribution is invariant to the unknown next-token law, enabling model-free calibration and decoding. We formulate joint watermark detection and message recovery as a multiple-hypothesis testing problem, derive a moment-robust minimax-optimal detection score over a relaxed moment class, and establish finite-sample recovery guarantees. Extensive experiments on two representative large language models validate the effectiveness of PIVOT, demonstrating reliable watermark detection and message recovery while preserving the generator's output distribution.

0.32

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.70
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

Attack-Resilient Multi-Bit Image Watermarking Framework via Latent Coordinate Sign Clamping

cs.CR ·2026-10-29 ·Marjan Beheshti, Ronghua Xu
similarity 0.70
Abstract

Watermarking is essential for image copyright protection and attribution, yet existing methods suffer from fundamental trade-offs among post-hoc applicability to pre-existing images, multi-bit capacity, training-free deployment, and adversarial resilience. To address these limitations, we propose a training-free watermarking framework that exploits the overcompleteness of diffusion latent spaces to embed multi-bit payloads into arbitrary images while preserving high visual quality. Additionally, we develop a three-layer decoding pipeline that combines magnitude-weighted majority voting, BCH, and Chase decoding to maximize message-extraction accuracy in the presence of channel noise. To counter active adversaries, our framework integrates a steganalysis-resistant noise camouflage layer and a dual-layer forgery defense that combines perceptual hashing with a Reed-Solomon fuzzy commitment scheme over CLIP features. Empirical evaluations demonstrate that our method applies to both natural and AI-generated images with a scalable $32\text{--}128$-bit capacity. Furthermore, it effectively mitigates advanced removal vectors ($94.6\%$ decode rate against CtrlRegen+ regeneration attacks) and secures robust forgery detection ($98.8\%$ accuracy via joint CLIP and RS fuzzy commitment mechanism).

0.04

Anchor-ECC: Local Integrity Checking for Watermarked LLM Outputs via Error-Correcting Codes

cs.CR cs.CL ·2026-09-30 ·Zewei Deng, Muhammad Siddeek, Liyan Xie, Mohamed Seif, Mengdi Wang +2 more
similarity 0.69
Abstract · 18 pages, including references and appendices; 1 figure and 11 tables

LLM watermarking has become an effective approach to distinguishing AI-generated text from human-written text by embedding detectable patterns during generation. However, a small post-generation edit may change the meaning of the text without removing its overall watermark signal, creating a risk that the modified content is still attributed to the original model. We propose Anchor-ECC, which incorporates the error-correcting code (ECC) constraints and explicit boundary anchors into the watermark structure and pairs them with a dynamic-programming decoder to detect and localize post-generation edits. Across Qwen3-8B, Mistral-7B-Instruct-v0.3, and OPT-125M, the approximate-hard setting achieves about 99.7% block-level true positive rate (TPR) with at most 7.6% false alarm rate (FAR) for edit detection under mixed insertions, deletions, and substitutions, while preserving the distinction between watermarked outputs and unwatermarked text. Additional quality experiments identify lower-perplexity configurations that retain strong edit-detection performance. Together, these results extend LLM watermarking from source identification to local integrity verification while supporting configurable trade-offs between detection reliability and generation quality.

0.52