- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes CertMark, a distortion-free multi-bit watermarking framework with certified decoding. It uses message-dependent Gumbel-max sampling to preserve the original token distribution and introduces model-agnostic and model-aware decoders with statistical error guarantees. Experiments demonstrate competitive recovery performance across different models and tasks.
Critical strengths
Clear methodological presentation with a well-structured embedding and decoding pipeline, supported by theoretical analysis. Comprehensive experiments across multiple models, tasks, and attack settings, demonstrating competitive recovery performance while preserving text quality.
Critical weaknesses
Limited methodological novelty. The core embedding framework closely resembles existing distortion-free multi-bit watermarking approaches, such as MirrorMark, which already encode messages through sampling randomness. The additional statistical guarantees, while useful, largely follow from standard distributional analysis and hypothesis-testing techniques. Insufficient evidence for the practical advantage of certified decoding. Although MirrorMark is included in Appendix F, the comparison remains limited and does not clearly isolate CertMark's contributions. Moreover, most main results report bit accuracy without abstention, while Table 5 shows considerable abstention rates under strict certification thresholds.
Questions for authors
Could the proposed certified decoding framework be adapted to existing distortion-free multi-bit watermarking methods? Can the authors clarify whether the proposed encoding design offers additional advantages in embedding efficiency, computational overhead, or robustness, beyond facilitating certified decoding? What are the fundamental differences between CertMark's Gumbel-max sampling and existing approaches?
4 comments
Response 2/3
Q1 Could the proposed certified decoding framework be adapted to existing distortion-free multi-bit watermarking methods?
Not without changing how they form their candidate messages, and once that change is made one has CertMark's encoder. The certificate needs one property: conditional on the text, every wrong candidate's decoding score has a known law (Theorem 2), so that a union bound over the wrong candidates is valid. CertMark obtains it by making the message an input of the pseudorandom function, so a wrong candidate reads values the encoder never evaluated and its score is exactly Gamma-distributed on any text. The existing distortion-free schemes lack it: MirrorMark, Three Bricks and DISC derive all candidates from one shared uniform by mirroring or shifting it, so a wrong candidate's value is a deterministic function of the true one, BiMark and StealthInk decode each bit from a keyed count whose null depends on the text's entropy and has no closed form.
In the revised manuscript this argument is in Appendix G, right after the comparison of distortion-free schemes in Table 13, and the simulation is Table 7 in Section 5. All changes are marked in blue.
Q2 Can the authors clarify whether the proposed encoding design offers additional advantages in embedding efficiency, computational overhead, or robustness, beyond facilitating certified decoding?
Yes, in all three respects.
Embedding efficiency. CertMark decodes a whole chunk of 8–16 bits at once, by comparing all its possible values, instead of deciding each bit separately. This uses the evidence in the text more efficiently: Theorem 7 shows that each extra bit costs a fixed amount of evidence, whereas bit-by-bit decoders have to share the same tokens among all bits, so each bit gets less as the message grows. On summarization the text-only decoder reaches 98.8% bit accuracy against 92.7 for MirrorMark, 93.3 for BiMark and 81.6 for StealthInk, the gap widens with longer messages (Figure 2), and under light paraphrase CertMark recovers the complete 16-bit message for 62% of texts against at most 10% for any baseline.
Computational overhead. Encoding is as fast as plain sampling: 20.1 ms per token against 19.1 unwatermarked and 54.9 for XMark (one H100, Qwen3.5-4B). The text-only decoder is the fastest we tested, 0.01 s per user against 0.03 for MPAC, 0.18 for StealthInk, 0.28 for XMark and 2.18 for RSBH. The model-aware decoder needs one extra forward pass of the model, 0.42 s per user (runtime appendix).
Robustness CertMark is the most robust method under copy-paste of unwatermarked spans and under 10% token substitution, deletion and insertion (Figure 3, and Figure 4 of the submission, Figure 5 in the revision), and it pays nothing in text quality because the model's distribution is never changed.
We rewrote every method's watermarked texts with a paraphrasing model (DIPPER [1]) at three strengths, light, moderate and strong, and let each method decode the rewritten text with its own detector (text completion, 16-bit messages, 300-token texts, Qwen3.5-4B, CertMark with the certified model-agnostic decoder at ). Under light paraphrase CertMark recovers the complete 16-bit message for 62% of texts against at most 10% for any baseline, because it decodes the whole message at once. Under strong paraphrase no method recovers the message [2, 3], but CertMark is the only one that abstains: its certificate stays valid on edited text, so it abstains, while every baseline returns a wrong identifier for almost every text. Over 1 200 paraphrased chunks at , only 0.25% were certified wrongly.
| paraphrase strength | method | exact message | returned & correct | returned & wrong | abstained |
|---|---|---|---|---|---|
| light | CertMark | 62% | 48% | 0% | 52% |
| light | BiMark | 8% | 8% | 92% | 0% |
| light | MPAC | 6% | 6% | 94% | 0% |
| light | XMark | 10% | 10% | 90% | 0% |
| light | MirrorMark | 2% | 2% | 98% | 0% |
| moderate | CertMark | 28% | 10% | 2% | 88% |
| moderate | MPAC | 6% | 6% | 94% | 0% |
| moderate | BiMark | 0% | 0% | 100% | 0% |
| moderate | XMark | 2% | 2% | 98% | 0% |
| moderate | MirrorMark | 0% | 0% | 100% | 0% |
| strong | CertMark | 6% | 2% | 0% | 98% |
| strong | MPAC | 0% | 0% | 100% | 0% |
| strong | BiMark | 0% | 0% | 100% | 0% |
| strong | XMark | 0% | 0% | 100% | 0% |
| strong | MirrorMark | 0% | 0% | 100% | 0% |
Response 3/3
Q3 What are the fundamental differences between CertMark's Gumbel-max sampling and existing approaches?
All distortion-free schemes keep the model's next-token law, they differ in where the message lives and in what the decoder can therefore assume. Biased schemes (XMark, MPAC) move the message into the law and pay in quality. Reweighting schemes (StealthInk, BiMark) keep the law only on average over the key and decode bit by bit. The Gumbel-max family (Aaronson, Three Bricks, MirrorMark, CertMark) keeps the law exactly at every step and moves the message into the sampling randomness. Within that family CertMark makes two choices. First, the message is an argument of the pseudorandom function rather than a mirror or shift of one shared uniform, so every candidate message reads independent randomness. This is what gives the exact wrong-candidate null (Theorem 2), the certificate, joint decoding of wide chunks, and the law behind the model-aware likelihood-ratio decoder (Theorems 2–5). Second, a repeated context draws fresh uniforms at the encoder, so Theorem 1 holds exactly for a single generation with no caveat on repetition.
In the revised manuscript this positioning is given at the start of Appendix G, before the comparison in Table 13. All changes are marked in blue.
References
[1] Krishna, Kalpesh, et al. "Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense." NeurIPS 2023.
[2] Zhang, Hanlin, et al. "Watermarks in the sand: Impossibility of strong watermarking for generative models." ICML 2024.
[3] Jovanović, Nikola, Robin Staab, and Martin Vechev. "Watermark stealing in large language models." ICML 2024.
I appreciate the author's detailed responses and additional experiments. I still feel that the overall methodological novelty and analysis could be further strengthened. I will therefore maintain my original rating.
Response 1/3
We would like to thank the reviwer for the constructive feedback. We address reviewer's questions below:
We agree that several technical components of our encoder are shared with existing distortion-free schemes. Gumbel-max sampling seeded by a keyed PRF, placing the message in the sampling randomness, and enumerating candidate messages at the decoder appear in Three Bricks [1], DISC [2] and MirrorMark [3]. However, while our method shares these components with prior work, our method overall is strictly different. Most importantly, our decoder abstains whenever the probability of returning a wrong message is to large. No existing distortion-free scheme provides this. Second, our method is empirically more effective, as shown in the experimental section, showing that we leverage these components in our scheme significantly more effectively.
We argue that we provide in the experimental section ample evidence for the practical advantage of certified decoding. Generally, our decoder can obtain much higher accuracy. In particular, certified decoding can abstain, when unsure, which is preferable to returning a wrong recovered message. We measure this in Table 5.
While both methods use distortion-free sampling, their candidate constructions, theoretical objectives, and decoding guarantees differ fundamentally. We clarify these differences below.
1. Different candidate construction. MirrorMark obtains candidate messages by mirroring the same pseudorandom values around message-dependent pivots. Consequently, candidate scores are statistically dependent. CertMark instead includes the candidate message in the PRF input. Every incorrect candidate therefore reads independent pseudorandom values that the encoder never used.
2. Fundamentally different theoretical guarantees.
Crucially, MirrorMark's distortion-freeness and asymptotic EER analysis do not imply a guarantee on returning an incorrect message. CertMark provides precisely this guarantee, for arbitrary finite token budgets. The same construction additionally enables our exact model-aware likelihood-ratio decoder and certified robustness extensions (Thms. 5–6).
3. Experimental separation. We provide both a controlled simulation isolating candidate construction and direct method comparisons:
The controlled simulation changes the candidate construction while keeping the token probabilities and sampler fixed. The full-method comparisons additionally include differences in scheduling and decoding, and are therefore not presented as single-component ablations.
4. Reliable attribution. Under strong paraphrasing, both methods lose substantial recovery accuracy. However, MirrorMark returns an incorrect identifier on all evaluated texts, whereas CertMark abstains on 98% and returns no incorrect identifiers in this experiment. Unlike a conventional detector, CertMark can therefore explicitly distinguish insufficient evidence from a reliably recovered identifier.
We have strengthened this comparison in Appendix G (Table 13) and added targeted component comparisons in Appendix H (Table 15) and Section 5 (Table 7). The central novelty is an independently constructed candidate space that makes certified multi-bit attribution possible.
We report results in Table 2, 3 and 4 to evaluate the underlying decoding accuracy and enable direct comparisons with existing methods that do not provide certificates. To address this concern, we added Table 6 to the main text, reporting correct recovery, incorrect recovery, and abstention for CertMark and the baselines, while Appendix F further analyzes the trade-off across certification thresholds and token budgets. These results show that certification prevents unreliable attribution through abstention, while the model-aware decoder substantially reduces abstention.