acceptodds
Under review as a conference paper at ICLR 2027

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

16 views

Abstract

We introduce a framework for multi-bit text watermarking with security defined directly through -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 -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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Multi-bit Text Watermark, $f$-divergences

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_pjxNOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper designs a new multi-bits LLM watermark method named SimpleMark that explicitly controls per-key distributional distortion using ff-divergence constraints. It combines LDPC coding, simplex-based token mapping, and divergence-constrained probability reweighting for watermark embedding, along with maximum-likelihood decoding for message recovery. The paper also investigates the trade-off between embedding capacity, recovery reliability, and statistical detectability.

Critical strengths
  1. Clear motivation. The paper highlights the limitations of average-key distortion-freeness and introduces explicit per-key divergence constraints.

  2. Simple and theoretically grounded design. The proposed probability reweighting admits an efficient solution under TV and KL divergence constraints, supported by theoretical analysis.

  3. Comprehensive quality evaluation. Experiments on two LLMs demonstrate competitive message recovery while maintaining low distributional distortion, perplexity, and reasoning performance.

Critical weaknesses
  1. Restrictive decoding assumptions. The decoding method requires access to both the original LLM and the generation prompt, limiting its practicality for practical commercial LLMs.

  2. Limited comparisons with recent work. The experimental baselines are limited to BiMark and ArcMark. Several recent methods, including PURA [1], EBEW [2], MC²Mark [3], MirrorMark [4], StealthInk [5], QuantileMark [6], and XMark [7], are not evaluated. In particular, PURA [1] also considers model-assisted verification using smaller surrogate LLMs, making it a relevant baseline.

  3. Insufficient robustness evaluation. Robustness is a crucial property of text watermarking, yet it receives limited attention in this paper. The evaluation is restricted to random token substitution and is presented only in the appendix. Other common attacks, such as token insertion, deletion, and LLM paraphrasing, are not considered.

  4. Limited payload scalability. The maximum evaluated payload is only 16 bits, substantially smaller than those considered in several recent works (e.g., 64 bits in EBEW [2]). Moreover, the exhaustive ML decoder has exponential complexity in the payload length, while no runtime comparisons are provided to demonstrate its scalability.

[1] Wang et al. (2026). PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution. ACM CCS 2026.

[2] Gloaguen et al. (2026). Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark. NeurIPS 2026.

[3] Cui et al. (2026). MC²Mark: Distortion-Free Multi-Bit Watermarking for Long Messages.

[4] Jiang et al. (2026). MirrorMark: Generalizable Mirrored Sampling for Multi-bit LLM Watermarking.

[5] Jiang et al. (2025). StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models. ICML 2025.

[6] Zhu et al. (2026). QuantileMark: A Message-Symmetric Multi-bit Watermark for LLMs. ACL 2026.

[7] Xu et al. (2026). XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts. ACL 2026.

Questions for authors
  1. Practical decoding performance. Could the authors evaluate decoding with surrogate LLMs of different sizes or architectures, as well as without the original prompt? Would the proposed method remain effective under these more realistic settings?

  2. Selection of baselines. Why are BiMark and ArcMark selected as the only experimental baselines? Could the authors include comparisons with more recent methods [1–7], particularly PURA [1] and QuantileMark [6], which also consider model-assisted verification?

  3. Novelty of the distortion analysis. Prior work [8] has also discussed the limitations of marginal distortion-freeness (distribution preservation averaged over secret keys), as well as KL divergence and perplexity as distortion measures. Could the authors clarify what new theoretical insights their per-key formulation provides beyond this prior work?

[8] Cai et al. (2026). Towards Better Statistical Understanding of Watermarking LLMs. Journal of the American Statistical Association (JASA), 121(553), 247–258. https://doi.org/10.1080/01621459.2026.2618290

1 comment
AuthorsOpenReview ↗

Review acknowledgement

Thank you for your review. Please find a brief response addressing your concerns.

Due to our limited distribution shift from our f-divergence security definition, we require more information and parameters in general to perform decoding. Other definitions of distortion freeness are able to shift the distribution more (over an average for example) and bias towards singular desired tokens more frequently. As solved for in this paper, this leads to more per step distortion and larger capacity.

In practice, from discussions it seems commercial LLMs are also focused on embedding overhead and distortion freeness, rather than decoding or detecting watermarks

Also, thank you for pointing us towards additional relevant work. In our manuscript we mention that we benchmark against watermarks that have publicly available implementations and are distortion free to some respect. Other watermarking papers include 2-3 baselines. We apologize since we could not realistically benchmark seven multibit watermarks in this discussion period.

We include fundamental differences between watermarks’ distortion guarantee and other literature requested below.

[1] establishes computational indistinguishability over only a randomly sampled key for a single generation.

[2] is distribution preserving in expectation over messages.

[3] optimizes the KL distortion measure for average zero bit detection constraints with asymptotic guarantees.

In our work we have an explicit per key ff-divergence guarantee that holds for every realized key and message in a multi-bit watermarking setting. As mentioned above, the properties in [1][2] allow for more distortion at each individual step and larger capacity.

Thank you again for your review. We hope we are able to clarify fundamental concerns you may have.

References

[1] Wang et al. PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution. ACM CCS 2026.

[2] Zhu et al. QuantileMark: A Message-Symmetric Multi-bit Watermark for LLMs. ACL 2026.

[3] Cai et al. Towards Better Statistical Understanding of Watermarking LLMs. Journal of the American Statistical Association 2026

Reviewer_TD9oOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes SIMPLEMARK, a multi-bit text watermarking method that constrains the divergence between the watermarked and reference next-token distributions for each realized key and message. It combines a qq-ary LDPC code with a keyed target-token assignment and increases the target token’s probability subject to a TV or KL budget. Message recovery uses likelihood-based decoding with replay of the base language model. The analysis establishes channel collapse under exact per-key distortion-freeness and develops rate bounds under simplified memoryless assumptions.

Experiments compare SIMPLEMARK with BiMark and ArcMark on Qwen3.5 and Llama3.1, measuring next-token distributional deviation, message recovery, perplexity, and reasoning performance. Further experiments examine longer outputs, token substitutions, zero-bit detection, and different field sizes. The reported results suggest that the method reduces local distributional distortion while retaining useful message-recovery performance.

Critical strengths

The reduction in Eqs. (2)–(3) provides a transparent way to maximize the target-token probability while enforcing a prescribed TV or KL distortion budget during generation.

Critical weaknesses
  1. The distinction between average-key and per-key distortion-freeness is mathematically valid, but does not by itself show that an adversary without the secret key can exploit the reported deviations. The detector in Appendix C.1 is explicitly given the key, so the construction separates two distributional definitions rather than demonstrating an attack when the key is unavailable. Likewise, Section 4.2 estimates fixed-prompt next-token distributions instead of evaluating a specified adversary on complete generated texts. Comparative security conclusions require a clear distinction between knowing the key, obtaining repeated samples from the keyed distribution, and observing a single output.

  2. Appendix B.3 addresses composition, but its sequence-level guarantee is

dTV(P1:n,Q1:n)≤1−(1−ε)n.d_{\mathrm{TV}}(P_{1:n},Q_{1:n})\leq 1-(1-\varepsilon)^n.

At ε=0.05\varepsilon=0.05 and n=300n=300, this upper bound is approximately 0.99999980.9999998, providing essentially no useful sequence-level security guarantee even under the appendix’s assumptions. This does not show that the actual sequence-level distance is large; it shows that the stated bound cannot substantiate strong conclusions about full-output indistinguishability at that operating point. The demonstrated contribution is local distortion control, while the broader security advantage remains insufficiently established.

  1. Algorithm 2 reconstructs a truncated, renormalized top-qq distribution and scores complete candidate codewords under it. A substituted token can fall outside the reconstructed support, in which case every candidate message assigns that token probability zero and every full-sequence log-likelihood becomes −∞-\infty. The recovery results in Figure 6 therefore require an additional rule, such as erasure handling, smoothing, an explicit corruption model, or a different decoder. The brief reference to a plurality decoder does not identify which procedure produced the results or explain how out-of-support tokens are handled. Without this information, the reported substitution robustness cannot be reproduced or clearly attributed to the described method.

  2. Figure 7 reports zero-bit detection performance at false-positive rates as low as 10−1210^{-12}, but the detection statistic, acceptance threshold, and justification of the null-tail calibration are not provided. Algorithm 2 always returns a message and does not define a watermark-presence decision. The stated default of 300 trials per point cannot by itself validate such small false-positive probabilities. An analytical guarantee or another clearly documented calibration procedure is needed to assess these claims.

Questions for authors
  1. What information and query access does the adversary possess? Does it know the key or message, or obtain repeated samples under the same key and context? Under this model, what informative full-sequence guarantee or experimental result supports the security comparison with BiMark and ArcMark at the evaluated lengths and budgets?

  2. Which decoder produced Figure 6? Please provide the exact scoring rule when an observed token falls outside the replayed top-qq support, including any erasure handling, probability smoothing, corruption model, or alternative decoding procedure.

  3. What statistic and threshold produce Figure 7, and what establishes the stated false-positive rates down to 10−1210^{-12}? Are these rates analytically bounded or empirically estimated, and how does the calibration account for searching over candidate messages, where applicable?

These requests concern clarification and validation of the submitted results, rather than future extensions.

1 comment
AuthorsOpenReview ↗

Review acknowledgement

Thank you for your review on our paper. We briefly respond to concerns below.

Our results don't demonstrate a practical attack, instead a worst case per-key security guarantee with bounds distinguishability for every key and every message that holds even when the adversary knows the key.

The security definition is per step. As seen in our experiments, no other multi-bit watermark properly composes under bounded per step distortion freeness under their measured per step TV distance even under a similar step.

We use MLE decoding with any token outside the reconstructed top-qq is just treated as an erasure and adds the same likelihood odds to every codeword. In the experiment simplemark’s FPR is bounded with a 256-fold multiple-testing penalty from searching all possible messages, BiMark and ArcMark are given the true embedded message. This makes the comparison conservative against SimpleMark.

To briefly answer the questions: We introduce a stronger security guarantee statistically bounding the distortion freeness, and the MLE decoder scoring rule is above.

We appreciate your review and thank you for improving our manuscript.

Reviewer_fvCyOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies multi-bit text watermarking under explicit per-token distributional constraints that hold for every realized key and embedded message. SimpleMark combines q-ary LDPC encoding with a divergence-constrained probability tilt that increases the probability of a designated target token. The embedding optimization reduces to two probability masses, yielding an explicit solution for total variation and a scalar equation for KL divergence. Recovery uses likelihood-based decoding with model replay.

The theoretical analysis distinguishes average-key from per-key distortion guarantees, establishes zero capacity under exact per-key distortion-freeness, and provides rate bounds under idealized channel assumptions. Experiments across Qwen and Llama models evaluate distributional deviation, message recovery, perplexity, and downstream reasoning. The appendices additionally examine longer texts, token substitutions, zero-bit detection, and parameter sensitivity. The results support a useful operating regime with controlled local distortion and competitive message recovery.

Critical strengths

A meaningful design objective with a simple, enforceable guarantee.The paper makes distributional deviation an explicit resource constraint for each realized key and message, rather than relying solely on preservation after averaging over shared randomness. This is a consequential change in the design objective. A coherent empirical investigation that supports a useful operating regime.

Critical weaknesses

The security statement exceeds the existing guarantees: the paper only measures token-wise distinguishability, but the actual adversary can observe the entire sequence; the combinatorial bound in the appendix provides almost no information under typical parameters, and the separation result assumes that the adversary already knows the key. These limitations should more consistently constrain the security statements in the main text. Quality and recovery were not jointly verified at the same operational point: the likelihood ratio constraint was effective on approximately 91% of the inference tokens, resulting in actual watermark strength deviating from the nominal budget; task performance and recovery rate were evaluated under different settings, and the baseline was not compared at the matching distortion level, weakening the persuasiveness of the joint trade-off.

Questions for authors

Please clarify the adversary's knowledge and observation scope (whether the key is visible, single/multiple sequences), as well as which statements are limited to token-by-token detection and which are applicable to sequence-level hidden key detection. Please report the recovery accuracy and actual TV/KL divergence on the inference outputs of Tables 2–3, and explain how the quality degradation in Figure 10 limits the conclusion of "no degradation in inference performance". Is BiMark/ArcMark evaluated at the distortion or restoration level that matches SimpleMark? If not, please clarify the scope of application of the empirical statement.

1 comment
AuthorsOpenReview ↗

Review acknowledgement

Thank you for your review. Please find a short answer to your concerns and questions below.

Our security guarantee is per-token and per-key, against an adversary who may hold the key and see a next token sample. Each next token distribution is within ε\varepsilon of the base model.

BiMark and ArcMark are evaluated under their own definitions of distortion freeness, averaged over the secret key. As shown in our paper, that leads to higher empirical total variance and worst case distinguishability.

Thank you again for your feedback and time, we appreciate it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.