CS Paper Radar

Minimax bounds for watermarked and masked recursive discrete distribution estimation

Millen Kanabar, Michael Gastpar

cs.IT cs.LGmath.ST ·submitted 2026-08-31 17:00 UTC · v1
theory

Abstract

Watermarking has been proposed as a way to identify synthetic samples in estimation settings where no metadata is available to distinguish them from real samples, but its precise effects remain unexplored. In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples. In this work, we study the minimax loss of such recursive discrete distribution estimation in the presence of watermarks in contrast to the unassisted and oracle-assisted losses. When the fraction of real samples vanishes asymptotically, we provide a lower bound that shows that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes. Additionally, we show that in most regimes, the worst-case losses of a sequence of simple deterministic estimators match the corresponding lower bounds up to constants. Finally, we propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap. We conjecture that a tighter lower bound argument can close this gap.

Comment
Shorter version to be published at the IEEE Information Theory Workshop 2026

Closest papers

Nearest neighbours by meaning across the whole index.

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
hot direction similarity 0.67
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

Watermark Evidence under Open-Weight LLM Modification: Exact Bounds for Low-Rank Output Watermarks

cs.CR cs.AIcs.CL ·2026-11-16 ·Prashant Shekhar, Dumindu Samaraweera, Caroline Howard
theorycode/data similarity 0.64
Abstract

Open-weight language models can continue generating after their released weights are modified, while a watermark verifier still scores outputs against the original base and marked models. We study how such modifications change the evidence available to an OpenStamp-style verifier. At each shared prefix, we represent the modification as a residual in the next-token logits. We derive an exact finite-vocabulary lower bound on the expected log-likelihood-ratio evidence under a residual-span constraint, along with a sharp span-only deviation bound. We also characterize the first-order evidence shift through a covariance term with an explicit second-order remainder, and determine the residual span needed to reach a target evidence level. For sequence-level detection, we derive an exact conditional exponential-moment bound and combine it with a supermartingale argument and a distribution-free order-statistic tolerance bound. This yields a high-confidence upper bound on miss probability after attack selection on calibration data and evaluation on independent certification continuations. In experiments with OpenStamp on Llama-2-7B and Mistral-7B-v0.3, INT8 quantization and 30% pruning retain test true-positive rates of 85.6-94.8%, while 500-step LoRA fine-tuning lowers them to 28.8% and 11.6%. The covariance prediction tracks the measured mean LoRA evidence drift on both models, with no remainder-bound violations across 160,000 test prefixes. Additionally, we observe zero false positives among 500 base-model continuations per model. Through these theoretical and empirical results, the current research provides a better understanding of watermark robustness to model-editing/tuning attacks.

0.47

Prevalence Bounds for Edited Watermarked Text: Power Envelopes and Calibration Sensitivity

cs.CL stat.MLcs.CRcs.LG ·2026-11-12 ·Kuancheng Ye
code/data similarity 0.60
Abstract · 31 pages, 3 figures, 8 tables. Code and results: https://github.com/YYKKCC-kevin/watermark-prevalence

Watermark detectors decide whether one document came from a watermarked language model. Auditors often need a different number: the share of a corpus that did. We study this share for Gumbel-max and green-list (KGW) watermarks when every document may have been edited by an unknown amount. Without restrictions on the edits, the upper end of the identified set is 1. Combining a known least-favourable next-token distribution with a sequential coupling, we derive a power envelope indexed by three budgets: a retention floor, an entropy budget, and a budget for in-place substitutions, which for Gumbel-max make edited positions look less watermarked than human text. The envelope gives an identified set that is sharp for the alternatives it dominates, finite-sample bounds on the realized share of a fixed corpus with either the exact null or a null calibrated on an independent human sample, and confidence sequences for streams. In Gumbel-max simulations where the envelope binds, the bounds cover, and the threshold that maximizes the gap between envelope and null is generally as tight as twelve thresholds. On text from OPT-1.3B and Qwen3-1.7B, 12,000 fresh human documents scored under three keys show no robust departure from the exact null, and all bounds covered in resampling trials from finite pools of documents with random edits, substitutions and paraphrases; at a share of 0.2 the exact-null bound is about [0.14,0.38]. These results are fragile in two ways we make precise. LLM-paraphrased KGW pools fall below the envelope, yet at 2000 documents the bounds still covered in these trials. A simulated null error of 0.01, comparable to the largest deviation we observed at our thresholds, is likewise harmless at 2000 documents but breaks exact-null coverage at 100,000; a null calibrated on an independent human sample keeps coverage there, but needs a large reference sample to stay narrow.

0.17

AutoMark: Enabling Autoresearch to Discover Better LLM Watermarks

cs.CR cs.LG ·2026-09-29 ·Thibaud Gloaguen, Robin Staab, Martin Vechev
code/data similarity 0.60
Abstract · 52 pages

With LLM watermarking being deployed commercially and now required by regulations, improving its reliability and effectiveness has become crucial. Yet, recent progress in the field of LLM watermarking has increasingly been driven by improving details of existing methods, an effort fundamentally limited by the pace of human researchers. In this work, we enable for the first time the autonomous discovery of new distortion-free state-of-the-art watermarking schemes. To enable this, we (i) establish strict criteria to ensure that watermarks are reliable (e.g., they do not have an unexpectedly high false positive rate), (ii) propose rigorous statistical tests to automatically evaluate whether a watermarking scheme satisfies our criteria, and (iii) design an evaluation suite to rank watermarks along three key dimensions: detectability, quality, and robustness. By running our framework with 3 frontier models (GPT-6 Astra, Opus 5, Gemini-3.8 Flash), we discover over 50 different watermarking schemes, including several that outperform prior works along all key dimensions. We complement this by a manual study of the discovered schemes, distilling the key ideas into smaller components, and individually studying the impact of each component across dimensions (detectability, quality, robustness) to better understand how the proposed schemes operate. Importantly, we find that the agents, on top of improving existing ideas, also discover fundamentally new ideas (e.g., aligning watermark scores with random per-request direction). Overall, our work establishes the first steps of fully autonomous watermarking research, enabling the discovery of more reliable and effective watermarks. Our code is available at https://github.com/eth-sri/automark, and a blogpost to visualize our results at https://www.sri.inf.ethz.ch/blog/automark.

0.68

textGrain watermarking is harder to detect: can sum-tests still do it optimally?

cs.IT stat.MLcs.LGmath.ST+1 ·2026-10-13 ·Swapnaneel Bhattacharyya, Soham Bonnerjee
similarity 0.60
Abstract · Working draft; comments are welcome

Watermarking embeds an imperceptible signal in text from large language models that is statistically detectable with a secret key. The recent textGrain watermark (Li et. al. (2026b)) calibrates this signal against the model's sampling entropy through an explicit entropy budget, combining the stochasticity of Red-Green and the unbiasedness of Gumbel-max watermarks, and its accompanying report proposes a detector that sums pivotal statistics. We study when, and how efficiently, textGrain can be detected after human edits, modeled as a sparse mixture in which a fraction $\varepsilon_n\asymp n^{-p}$ of positions retain the watermark and token uncertainty decays as $n^{-q}$. First, entropy calibration comes at a cost: the minimax detection boundary of textGrain is $p+q=1/2$, so its detectable region is strictly smaller than that of Gumbel-max and maximal-coupling watermarks, whose boundary is $2p+q=1$. This cost stems from textGrain's construction rather than from entropy calibration itself: an unbiased scheme with the same entropy loss remains detectable where textGrain is not. Second, perhaps surprisingly, this loss makes the sum detector optimal at the boundary when the number of transport columns is fixed, unlike for Gumbel-max. When the number of columns grows and the entropy budget does not vanish, the detectable region expands while that of the sum detector does not. Third, for a fixed edit fraction, we characterize the optimal exponential rate of type II error decay and show that the sum detector falls strictly short of it at every fixed alternative. Finally, we propose a weighted multiscale binomial scan, valid in finite samples and needing no knowledge of the next-token distributions, entropy budget, or edit fraction; it attains every detection boundary above and the optimal exponent.

0.19

SAMP: Self-Adaptive Margin Prioritization For Robust Diffusion Watermarking

cs.CV cs.AIcs.MM ·2026-10-15 ·Yuhao Xue, Jiuan Zhou, Yu Cheng, Zhaoxia Yin
similarity 0.60
Abstract

Diffusion models have made high-fidelity visual generation widely accessible, while also lowering the barrier to producing convincing visual forgeries and complicating content provenance. Existing watermarking methods typically use a fixed embedding strength throughout denoising or treat all watermark dimensions equally. As a result, they may introduce unnecessary distortion when some watermark dimensions are already reliable, while failing to sufficiently reinforce those that are more vulnerable to subsequent perturbations. Therefore, robust watermarking requires adapting both the embedding strength during denoising and the optimization priority across watermark dimensions. To address this problem, we present SAMP, a self-adaptive framework consisting of global margin regulation and vulnerability-sensitive allocation. Global margin regulation adjusts the embedding strength according to the separation between the target codeword and competing codewords, together with the estimated effects of common attacks. Vulnerability-sensitive allocation identifies watermark dimensions that are more easily weakened by local perturbations and gives them higher optimization priority. Experimental results demonstrate that SAMP achieves an average information recovery accuracy of 0.993. Compared with state-of-the-art methods, SAMP improves PSNR by 16.8% and reduces LPIPS by 47.1%. These results validate the effectiveness of SAMP for reliable and high-quality diffusion watermarking.

0.05

Provably Secure Diffusion Watermarking Against Removal Adversaries with Batched Detector Access

cs.CR ·2026-10-29 ·De Zhang Lee, Ee-Chien Chang
similarity 0.60
Abstract

Recent latent-based watermarking methods can embed undetectable watermarks into AI-generated content. However, these approaches are vulnerable to removal attacks as their watermark detection boundaries are exposed, prompting the use of secret long-term transformations to hide these boundaries. We show that such defenses are insecure under a stronger threat model motivated by publicly reachable detectors: an adversary with batched detector access can reconstruct the transformations, permanently re-exposing the decision boundary. To address this, we propose a watermarking scheme based on a hybrid of long-term and one-time secret transformations, which prevents the reuse of structure across samples and keeps the long-term secret hidden. Besides undetectability, we show that this scheme is provably secure against removal adversaries with batched detector access, in the sense that no probabilistic polynomial-time adversary can achieve a non-negligible advantage over an adversary restricted to adding isotropic white-noise with a $\sqrt{2}\times$ larger perturbation budget, and we show this $\sqrt{2}$ factor to be tight. Evaluations on Stable Diffusion 2.1 and XL demonstrate the attack against the existing defense, and show that our scheme preserves generation quality and withstands common perturbations and targeted removal attacks.

0.06

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