acceptodds
Under review as a conference paper at ICLR 2027

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

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 furter achieves higher bit accuracy than probability-biasing baselines.

Primary area:
foundation or frontier models, including LLMs
Keywords:
language model watermarking, multi-bit payload, certified detection

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_TLhyOpenReview ↗
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
AuthorsOpenReview ↗

Response 1/3

We would like to thank the reviwer for the constructive feedback. We address reviewer's questions below:

W1 Limited methodological novelty.

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.

W2 Insufficient evidence for the practical advantage of certified decoding.

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.

W3 Although MirrorMark is included in Appendix F, the comparison remains limited and does not clearly isolate CertMark's contributions

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.

PropertyMirrorMarkCertMark
Main theoretical analysisAsymptotic equal-error rateExact finite-sample error control
Wrong-candidate scoreDependent on shared randomnessExactly Gamma-distributed (Thm. 2)
Incorrect message probabilityNo certified boundAt most δ (Thm. 4)
False-positive controlDetection threshold calibrated empiricallyAnalytical bound ≈ δ (Cor. 1)
DecodingScore maximization and separate watermark detectionCertified decoding with abstention

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:

ExperimentMirrorMarkCertMark
8-bit symbol error, 70 tokens (controlled simulation)42.2%2.8%
Summarization bit accuracy, Qwen3.5-4B92.7%98.8%
Exact 16-bit recovery, light paraphrasing2%62%

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.

W4 most main results report bit accuracy without abstention, while Table 5 shows considerable abstention rates under strict certification thresholds.

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.

AuthorsOpenReview ↗

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 δ=0.01\delta=0.01). 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 δ=0.01\delta=0.01, only 0.25% were certified wrongly.

paraphrase strengthmethodexact messagereturned & correctreturned & wrongabstained
lightCertMark62%48%0%52%
lightBiMark8%8%92%0%
lightMPAC6%6%94%0%
lightXMark10%10%90%0%
lightMirrorMark2%2%98%0%
moderateCertMark28%10%2%88%
moderateMPAC6%6%94%0%
moderateBiMark0%0%100%0%
moderateXMark2%2%98%0%
moderateMirrorMark0%0%100%0%
strongCertMark6%2%0%98%
strongMPAC0%0%100%0%
strongBiMark0%0%100%0%
strongXMark0%0%100%0%
strongMirrorMark0%0%100%0%
AuthorsOpenReview ↗

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 Beta(1/pt,1)\mathrm{Beta}(1/p_t,1) 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.

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

This work proposes CertMark, a multi-bit watermarking method that provides distortion-free message encoding and certified decoding. CertMark leverages Gumbel-max sampling to preserve the original token sampling distribution while embedding message chunks into the randomness generated by a pseudorandom function. At each token position, the pseudorandom function takes as input a fixed domain-separation tag, the preceding token context, a message chunk, and a candidate token. The paper proposes two decoding strategies, including a model-agnostic decoder that is more practical because it does not require access to the original prompt or model. The decoding procedure also provides a statistical certificate that controls the probability of returning an incorrect message. Experimental results show that CertMark achieves strong decoding accuracy while preserving text quality.

Critical strengths
  1. The topic is timely and important. The proposed CertMark method provides distortion-free multi-bit message encoding together with certified message decoding.
  2. The methodology is technically sound. The distortion-free property is achieved by using Gumbel-max sampling during token generation, which preserves the original next-token distribution. The certified decoding mechanism further builds on the statistical properties induced by Gumbel-max sampling to derive a known null distribution for incorrect message candidates, enabling bounded decoding error with abstention when the evidence is insufficient. The experimental results validate the effectiveness of the proposed method.
Critical weaknesses
  1. The certification guarantee of the model-agnostic decoder under text-editing attacks is not sufficiently studied. Although the paper evaluates decoding accuracy under copy-paste, substitution, and deletion attacks, these experiments disable certification. It remains unclear whether the guarantee in Theorem 4 still holds after such edits, and the paper does not report certified error or abstention rates under attack.

  2. The manuscript considers only relatively simple token-level editing attacks, such as token substitution and deletion, while lacking evaluation against stronger semantic-preserving attacks such as paraphrasing.

Questions for authors
  1. Does the certification guarantee of the model-agnostic decoder still hold under text-editing attacks?

  2. How does CertMark perform under stronger text transformations such as paraphrasing?

  3. CertMark skips message encoding when a context has appeared previously in the same generation. How frequently does this occur in practice, and how does skipping these positions affect encoding capacity and decoding performance?

4 comments
AuthorsOpenReview ↗

Response 1/3

We would like to thank the reviewer for the constructive and positive assessment of our paper.

Q1 Does the certification guarantee of the model-agnostic decoder still hold under text-editing attacks?

Yes, and this is a property of the construction. The certificate rests on Theorem 2: for every wrong candidate message, the uniforms the decoder reads are values the encoder never evaluated, so they are i.i.d. U(0,1)U(0,1) conditional on the text, whatever that text is and however it was produced. Editing a watermarked text therefore leaves the wrong candidates' score distribution unchanged and can only remove evidence for the correct candidate. Consequently the probability of returning a wrong message stays below δ\delta (Theorem 4) and the false-positive rate on edited unwatermarked text stays at δ\delta.

We verified it on the four edit attacks of our attack appendix (copy-paste of unwatermarked spans, random-token substitution, deletion, insertion at 10/20/30%) applied to the L=8L=8 generations of both models on completion and summarization at T∈{150,300}T\in\{150,300\}, decoded with the model-agnostic decoder at δ=0.01\delta=0.01.

pooled over all 96 edit settingsreturned & wrong (bound 1%1\%)Type-I on edited unwatermarked text (bound ≈1%\approx 1\%)
copy-paste0.25%1.1%
substitution0.17%1.0%
deletion0.83%0.8%
insertion0.58%0.4%
all0.46%0.8%

No cell exceeds two wrong returns in 50 chunks, and in the setting below no wrong message was returned at all. The table gives the share of users (%) whose message the certified decoder still returned, correctly and with a certificate, after a fixed fraction of the tokens of every text was edited. Every user not counted here received an abstention, never a wrong message. Completion, T=300T=300, δ=0.01\delta=0.01, 50 users per cell.

modelattack10% correct10% wrong10% abstain20% correct20% wrong20% abstain30% correct30% wrong30% abstain
Qwen3.5-4Bcopy-paste1000098029802
Qwen3.5-4Bsubstitution9802920848052
Qwen3.5-4Bdeletion10000920852048
Qwen3.5-4Binsertion9802960472028
Llama-3.1-8Bcopy-paste10000100009406
Llama-3.1-8Bsubstitution96047003012088
Llama-3.1-8Bdeletion100007202830070
Llama-3.1-8Binsertion96048601442058

At 30% substitution the uncertified argmax has already fallen to 91% bit accuracy on Qwen, the regime in which the baselines of the token-edit figure (Figure 4 of the submission, Figure 5 in the revision) return wrong messages. The certified decoder abstains on those texts instead. Under paraphrase, the strongest edit (reply to W3), the pooled certified-wrong rate over 1 200 chunks is 0.25%.

In the revised manuscript this analysis is in Appendix I, with the pooled certificate check as Table 16 and the coverage under edits as Table 17. All changes are marked in blue.

AuthorsOpenReview ↗

Response 2/3

Q2 How does CertMark perform under stronger text transformations such as paraphrasing?

As the reviewer asked, we evaluated CertMark and all baselines under a paraphrasing attack: every watermarked text is rewritten sentence by sentence by a paraphrasing model (DIPPER [1]), and each method then decodes the rewritten text with its own detector. We control the strength of the attack through the paraphraser's lexical diversity, the share of the wording it is asked to change, and use three levels: 20 (light paraphrase, most words kept), 40 (moderate) and 60 (strong, the majority of the wording replaced). The setting is text completion with 16-bit messages and 300-token texts on Qwen3.5-4B, for CertMark we report the certified model-agnostic decoder at δ=0.01\delta=0.01 (new Table R3). Three findings.

1. Strong paraphrase defeats message recovery for every token-level scheme, ours included. At lexical diversity 60, bit accuracy falls to 52–71% for all methods (chance is 50%) and no method recovers the exact 16-bit message for more than 6% of texts. This is the expected behaviour of any scheme keyed to local token context [2, 3].

2. Under moderate paraphrase, CertMark recovers far more messages than any baseline. Bit accuracy is similar across methods at lexical diversity 20 (78–83%), but CertMark decodes the whole 16-bit message jointly, so when it succeeds all bits are right: it recovers the exact message for 62% of paraphrased texts against at most 10% for the baselines, whose bit errors are spread across every message. The same holds at lexical diversity 40 (28% against at most 6%). For attribution the exact identifier is what matters.

3. CertMark is the only method that reports when the evidence is gone. The certificate holds on any text (Theorem 2), so on paraphrased text the decoder abstains rather than guessing, every baseline returns an identifier for every text, wrong in 90–100% of cases at the two stronger levels, with no indication.

lexical diversitymethodexact messagereturned & correctreturned & wrongabstained
20 (light)CertMark62%48%0%52%
20BiMark8%8%92%0%
20MPAC6%6%94%0%
20XMark10%10%90%0%
20MirrorMark2%2%98%0%
40CertMark28%10%2%88%
40MPAC6%6%94%0%
40BiMark0%0%100%0%
40XMark2%2%98%0%
40MirrorMark0%0%100%0%
60 (strong)CertMark6%2%0%98%
60MPAC0%0%100%0%
60BiMark0%0%100%0%
60XMark0%0%100%0%
60MirrorMark0%0%100%0%

In the revised manuscript this evaluation is in Appendix I, with the full comparison as Table 18. All changes are marked in blue.

AuthorsOpenReview ↗

Response 3/3

Q3 CertMark skips message encoding when a context has appeared previously in the same generation. How frequently does this occur in practice, and how does skipping these positions affect encoding capacity and decoding performance?

This is a very good question. The rule in question is the following: at a step whose context (the previous h=3h=3 tokens) already occurred earlier in the same generation, the encoder draws its uniforms from a position-indexed tuple instead of the message tuple, so that step carries no message bits. It exists because re-using the uniforms of the earlier occurrence would make the second draw depend on the first, which would break both the exact distortion-freeness of Theorem 1 and the Gamma null of Theorem 2. Fernandez et al. and SynthID deduplicate repeated contexts for the same reason.

How often it occurs. We counted, in the saved generations of both models, the fraction of positions whose 3-token context had already occurred in the same text, for the watermarked texts and for the paired unwatermarked texts (new Table R8):

taskT=150T=150, watermarkedT=150T=150, unwatermarkedT=300T=300, watermarkedT=300T=300, unwatermarked
completion (C4), Qwen3.5-4B2.7%2.5%5.4%5.3%
completion (C4), Llama-3.1-8B2.7%2.3%4.8%4.7%
summarization, Qwen3.5-4B0.4%0.3%1.7%1.7%
summarization, Llama-3.1-8B0.4%0.2%1.9%1.3%
story, Qwen3.5-4B0.1%0.2%0.6%0.6%
story, Llama-3.1-8B0.5%0.3%0.8%0.9%

Repeated contexts are rare: less than 2% of positions in summarization and story generation, 2.7% in 150-token text completions and about 5% in 300-token completions, where repeated phrases are common. The rate is the same in the unwatermarked texts of the same prompts, which confirms that the rule does not make the text more repetitive, as Theorem 1 requires.

Effect on capacity. Each skipped position is one token fewer for the decoder to score, so a text in which 5% of the contexts repeat loses 5% of its scored positions. How much evidence that removes depends on how informative those positions were, and repeated phrases tend to be predictable ones. Our reply to Q2 shows that a loss of this size is immaterial at these lengths: on completion the certified decoder recovers 98% to 100% of messages at T=150T=150 and 100% at T=300T=300, so 5% fewer scored tokens leaves recovery essentially unchanged.

Effect on decoding. None beyond the lost positions: the decoder skips exactly the same positions by the same rule, computed from the text and the key alone, so encoder and decoder always agree on which positions carry the message, and the null of Theorem 2 is stated over the scored positions and holds whatever their number. In the revised manuscript this explanation is Appendix K, with the measured rates as Table 19. 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 response, which answered my questions. I therefore maintain my positive evaluation of this manuscript.

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

This paper proposes CertMark, a distortion-free multi-bit watermarking method with certified decoding. The method uses the embedded message and a secret key to determine the pseudorandomness in Gumbel-max sampling, preserving the original token distribution while enabling message recovery. The authors introduce model-agnostic and model-aware decoders and establish theoretical bounds on the probability of returning an incorrect message. Experiments show competitive performance in terms of message recovery and text quality.

Critical strengths
  • The paper aims to address an important problem in multi-bit watermarking, particularly the trade-off between watermark recoverability and text quality.
  • The certified decoding framework provides a mathematically meaningful guarantee on the probability of incorrect message recovery, which is potentially useful.
Critical weaknesses
  • The main technical insight and novelty are not sufficiently clear. While the paper combines distortion-free generation, multi-bit watermarking, and certified decoding, the key technical insight behind the proposed method is not clearly articulated. Prior works have already explored distortion-free watermarking and established various theoretical guarantees. It is therefore important to explain precisely which limitations of existing approaches are being addressed and what fundamentally new understanding or technique enables the proposed improvement. In particular, the paper emphasizes certified decoding as its main contribution, but it is unclear to what extent this represents a new watermarking mechanism versus an additional statistical decision rule applied to the decoding scores. A more careful comparison with existing theoretical frameworks would help establish the novelty and significance of the contribution.
  • Theorem 4 provides a mathematically meaningful guarantee: under the stated assumptions, the probability that the certified decoder outputs an incorrect message chunk rather than abstaining is bounded by a specified threshold. However, it is unclear how this guarantee relates to the fundamental objectives of watermarking, particularly detectability, Type-I errors (false positives), and Type-II errors (false negatives). More specifically, bounding the probability of incorrect message recovery with an abstention option is not equivalent to guaranteeing reliable watermark detection or successful message recovery. A small error bound may coexist with a high abstention rate, potentially limiting the practical usefulness of the watermark. Indeed, Table 5 shows substantial abstention rates in some settings, even when the certified error probability is very small.
  • The experiments report strong message recovery performance compared with several baselines. However, it remains unclear why the proposed approach achieves these improvements and which components are primarily responsible. For example, how much of the improvement comes from message-dependent Gumbel-max sampling, the particular scoring function, the chunking strategy, or the use of model probabilities in the model-aware decoder? While the likelihood-ratio formulation provides some theoretical motivation for the model-aware decoder, the paper does not sufficiently explain why the overall construction should outperform existing distortion-free multi-bit watermarking approaches.
  • The presentation of the method is sometimes difficult to follow. For example, after Equation (3), the authors state: "E consumes no randomness of its own but replaces it deterministically by the message m and key κ." This statement is potentially confusing. Although the construction uses a pseudorandom function to emulate independent random samples, the encoder is deterministic for a fixed message, key, and generation context. The paper should more clearly distinguish deterministic pseudorandom generation from truly independent sampling and explain the assumptions under which the claimed distribution-preservation guarantee holds. Importantly, deterministic sampling does not necessarily imply leakage of the watermark key, provided the pseudorandom function is secure. Nevertheless, it raises questions about the security and statistical behavior of the construction when the same key is reused across multiple generations. The authors acknowledge that repeated prompts can produce identical generations and that generations sharing contexts may be correlated under key reuse. However, the main distribution-preservation theorem concerns a single generation, with probability taken over the idealized key randomness. It does not directly establish that multiple generations under a reused key are jointly indistinguishable from independent unwatermarked samples. Could these correlations be exploited by an adversary to distinguish watermarked generations, infer information about the embedded message, or weaken the security of the watermarking mechanism?
Questions for authors
  • What is the central technical insight of CertMark beyond combining distortion-free sampling with a certified decoding rule? How do the theoretical guarantees differ fundamentally from those in existing watermarking methods?
  • How does the certified decoding error bound relate to standard watermark detectability and Type-I/Type-II errors? Can the authors formally characterize the trade-off between certification confidence, successful recovery, and abstention?
  • What specifically explains the improvement over previous methods, particularly existing distortion-free multi-bit watermarking schemes? Can the authors provide theoretical intuition and targeted ablations to isolate the contributions of the individual components?
  • While deterministic pseudorandom sampling does not inherently reveal the secret key, could observing multiple generations under the same key reveal exploitable correlations? What guarantees hold against adversaries who can observe repeated or related prompts, and how does the proposed nonce extension affect watermark recovery and security?
6 comments
AuthorsOpenReview ↗

Response 1/5

We thank the reviewer for the detailed review. Before addressing each point, we note that the reviewer’s assessment of presentation, soundness and novelty differs markedly from that of the other two reviewers. Reviewer Gs7r (confidence 4) rates the presentation as “Clear and easy to follow”, states that “the methodology is technically sound”, and notes that the certified decoder derives “a known null distribution for incorrect message candidates, enabling bounded decoding error with abstention when the evidence is insufficient.” Reviewer TLhy highlights a “clear methodological presentation with a well-structured embedding and decoding pipeline, supported by theoretical analysis” and “comprehensive experiments across multiple models, tasks, and attack settings.” The reviewer also acknowledges that our certified decoding “provides a mathematically meaningful guarantee on the probability of incorrect message recovery.”

We believe each of the reviewer’s concerns can be resolved directly, and we answer them with new theory and experiments.

W1. Clarification of deterministic sampling and distribution-preservation assumptions.

The deterministic/random question was stated precisely in the submission. Theorem 1 is formulated over a uniformly random key, with the PRF modelled as a random function. This is the standard setting for PRF-seeded distortion-free samplers [4, 5]. However, we agree that we can still improve the presentation and we thank the reviewer for pointing it out. We will clarify that the encoder is a deterministic function for a fixed key, message and context. What it reads from the pseudorandom function are deterministic stand-ins for independent uniforms, not random draws, and the distribution-preservation claim is a statement over the key. We have made this explicit in the main text:

  • The sentence after Equation (3) in Section 3 now says that the encoder draws no fresh randomness, that it is deterministic for a fixed key, message and context, and that the values it reads stand in for independent uniforms. Lemma 1 applies when they are independent uniforms, and Theorem 1 states when that holds.
  • The paragraph after Theorem 1 (page 5) now lists the three assumptions behind the guarantee. (i) The key is drawn uniformly and kept secret. (ii) The PRF is idealised as a random function, in which case Equation (7) is exact. With a keyed cryptographic PRF the guarantee holds up to the distinguishing advantage of the PRF, so no efficient observer without the key can tell the watermarked law from the unwatermarked one. This is a computational guarantee, the same one that every PRF-seeded distortion-free sampler carries [Kuditipudi et al. 2024, Christ et al. 2024]. Our experiments instantiate the PRF with SplitMix64, a fast non-cryptographic hash (Appendix L). This supports the statistical guarantees the experiments measure, since the null certification rates track δ\delta in Tables 5 and 10, but not the computational guarantee, which requires a keyed cryptographic PRF. The revision says so after Theorem 1 and in Appendix L. (iii) Within one generation every step reads the PRF at a new argument, which the fresh tuple in Equation (5) enforces when a context recurs. Theorem 1 itself is unchanged: it was already stated over a uniformly random key with the PRF treated as a random function. The changes make the assumptions visible where the encoder is introduced rather than only in the theorem statement and in Appendix L.
  • The paragraph also states that the guarantee is for a single generation. The deployment remark that follows already explains that under one key the encoder is deterministic in the prompt and message, so repeated generations are not independent, and Appendix U gives the nonce that restores independence and measures its cost.
AuthorsOpenReview ↗

Response 2/5

Q1 What is the central technical insight of CertMark beyond combining distortion-free sampling with a certified decoding rule? How do the theoretical guarantees differ fundamentally from those in existing watermarking methods?

Our main contribution is certified decoding: The decoder either returns a message or abstains, and the probability that it returns a wrong message is bounded by a chosen δ\delta, exactly and in finite samples. This is a bound on the probability of returning an incorrect message, not a conditional error probability given acceptance. No existing distortion-free scheme provides this, and none can obtain it with its current candidate construction, which is precisely where our encoder departs from [1–3]. 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.

We summarize the differences between CertMark and other distortion-free multi-bit schemes in the following table. Bit accuracy is the average over token budgets on CNN/DailyMail summarization with Qwen3.5-4B.

MethodCandidate constructionLaw of a wrong candidate's scoreGuarantee on returning a wrong messageAbstentionModel-aware and edit-robust decodingBA, summarization
MirrorMark [3]Mirror images of one uniform around message pivots.A deterministic function of the true value. The authors note the candidate statistics are dependent.None. An asymptotic equal-error-rate and an empirically set threshold.No.No. The scheduler tolerates edits without a guarantee.92.7
StealthInk [7]Keyed reweighting of the next-token law.Depends on the entropy of the text, no closed form.None.No.No.81.6
BiMark [8]Keyed reweighting with per-bit majority votes.Depends on the entropy of the text, no closed form.None.No.No.93.3
CertMarkIndependent PRF uniforms for every candidate.Exactly Γ(nc,1)\Gamma(n_c,1) for every text (Thm. 2).Pr⁡[returns a wrong message]≤δ\Pr[\text{returns a wrong message}]\le\delta, exact and finite-sample (Thm. 4), verified in Table 5.Yes, certified.Exact likelihood-ratio decoder with an exact null and a contamination-robust score, both certified (Thms. 5–6).98.8 text-only, 100.0 model-aware

Thm. 4 bounds the probability of returning a wrong chunk by a chosen δ\delta, exactly, for any model, prompt or edited text (Table 5). It needs one fact: a wrong candidate's uniforms are i.i.d. U(0,1)U(0,1) conditional on the text (Thm. 2). Hashing the chunk value into the PRF argument gives every candidate independent, never-evaluated uniforms, so this holds. In [1–3] a wrong candidate is a deterministic function of the true value, so it cannot. Independence also lets 8–16-bit chunks be decoded jointly, where mirrored candidates collapse.

Our reply to Q3 complements this with a component ablation that isolates the contribution of each of these design choices.

The revised manuscript contains this comparison as Table 13 in Appendix G, preceded by a paragraph explaining why no existing distortion-free scheme can obtain the certificate with its current candidate construction. We also state after Theorem 4 that the bound is on the probability of returning an incorrect chunk and not on the conditional error given that a chunk was returned, and we use this wording in the introduction and related work. All changes in the revision are marked in blue.

AuthorsOpenReview ↗

Response 3/5

Q2 How does the certified decoding error bound relate to standard watermark detectability and Type-I/Type-II errors? Can the authors formally characterize the trade-off between certification confidence, successful recovery, and abstention?

This is a very good question and the right thing to ask of a certificate, and we answer it separately for the two error types.

Definitions. Let H0H_0 be the hypothesis that the text is independent of the key κ\kappa (no watermark) and H1H_1 that it was generated by CertMark with message mm. For a chunk cc, the certified decoder DδD_\delta returns either a value m^c\hat m_c or ⊥\bot. Its Type-I error is the probability of returning any message on unwatermarked text, α=Pr⁡κ[Dδ(Y)≠⊥∣H0]\alpha=\Pr_\kappa[D_\delta(Y)\neq\bot\mid H_0], and its Type-II error is the probability of abstaining on watermarked text, β=Pr⁡κ[Dδ(Y)=⊥∣H1]\beta=\Pr_\kappa[D_\delta(Y)=\bot\mid H_1]. Theorem 4 bounds a third quantity, the probability of returning a wrong message under H1H_1, by δ\delta.

Type-I error (false positives)

The proof of Theorem 4, together with Theorem 2, directly yields a Type-I error bound as a corollary. Theorem 2 holds for any text: the scored uniforms of a wrong candidate are i.i.d. U(0,1)U(0,1) conditional on the text. Under H0H_0 every one of the 2kc2^{k_c} candidates is a wrong candidate, so the same union bound gives

α = Pr⁡κ[Dδ(Y)≠⊥∣H0] ≤ 2kc2kc−1 δ,\alpha\,=\,\Pr_\kappa\bigl[D_\delta(Y)\neq\bot\mid H_0\bigr]\,\le\,\tfrac{2^{k_c}}{2^{k_c}-1}\,\delta ,

i.e. "the certified decoder returns a message" is a watermark detector with false-positive rate essentially δ\delta, and decoding the CC chunks of a message at level δ/C\delta/C bounds it by 2kc2kc−1 δ\tfrac{2^{k_c}}{2^{k_c}-1}\,\delta for the whole message. One parameter therefore controls both false detection and false attribution. We will state this as Corollary 1. The paper already measures α\alpha as the "null cert. rate" row of Table 5. The new sweep over token budgets confirms it on 600 unwatermarked chunks per row (3 tasks ×\times 4 budgets ×\times 50 users, L=8L=8):

Type-I rate α\alphaδ=10−4\delta=10^{-4}10−310^{-3}10−210^{-2}0.050.05
Qwen3.5-4B, text-only.000.000.002.042
Qwen3.5-4B, model-aware.000.002.010.058
Llama-3.1-8B, text-only.000.000.008.037
Llama-3.1-8B, model-aware.000.003.013.043

Type-II error (false negatives) and abstention

An unconditional bound on β\beta is not possible, for CertMark or for any other scheme: β\beta depends on the entropy the sampler had when it produced the text, and a text generated at zero entropy carries no watermark at all, so no decoder can be forced to accept it. We therefore evaluate β\beta experimentally, as a function of the evidence available to the decoder.

Table 5 reports the worst case by construction: it pools T=150T=150 only with LL up to 32, so that 16-bit chunks are decoded from about 70 tokens. On the main-benchmark setting, L=8L=8, abstention at δ=0.01\delta=0.01 versus T=150/200/250/300T=150/200/250/300 is (new Figure R1):

abstention β\beta (%) at δ=0.01\delta=0.01completionsummarizationstory
Qwen3.5-4B, text-only0 / 2 / 0 / 032 / 12 / 6 / 02 / 0 / 0 / 0
Qwen3.5-4B, model-aware0 / 0 / 0 / 00 / 0 / 0 / 00 / 0 / 0 / 0
Llama-3.1-8B, text-only2 / 0 / 0 / 0100 / 98 / 80 / 7080 / 62 / 56 / 42
Llama-3.1-8B, model-aware0 / 0 / 0 / 014 / 2 / 0 / 00 / 0 / 0 / 0

In these experiments the text-only decoder abstains mainly on low-entropy text, and the rate falls as tokens accumulate. It also rises with payload length, with the strength of an edit and with smaller δ\delta (Tables R5 and R7). The model-aware decoder, provided for the low-entropy regime, has near-zero Type-II error everywhere. Abstention does not cost usefulness either: per user on Qwen3.5-4B summarization at T=150T=150 and δ=0.01\delta=0.01, CertMark returns a correct / wrong / no message for 68 / 0 / 32% of users (text-only) and 100 / 0 / 0% (model-aware), against 62 / 38 / 0% for XMark and 32 / 68 / 0% for MPAC, and on the users where CertMark abstains the baselines are wrong on 31% to 94% of them (full per-user comparison in the new Table R2). Abstention therefore concentrates on the texts where the baselines are also most often wrong, 31% to 94% of them, instead of returning a wrong identifier there.

In the revised manuscript, the Type-I bound is stated as Corollary 1 directly after Theorem 4, and Appendix F reports the Type-I and Type-II rates against the token budget (Tables 10 and 11, Figure 4), and the per-user comparison against the baselines is Table 6 in Section 5. All changes are marked in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.