acceptodds
Under review as a conference paper at ICLR 2027

PRESENCE BEFORE PAYLOAD: FALSE-POSITIVE- CONTROLLED MULTI-BIT LLM WATERMARKING

Abstract

Multi-bit LLM watermarking involves two conceptually distinct tasks: detecting whether a watermark is present and, only if so, recovering the payload it encodes. In several existing methods, however, the two decisions are conflated: watermark presence is inferred from the same search-and-decoding procedure used to recover the payload. This can cause unwatermarked text to be accepted whenever payload search or decoding produces a plausible candidate, making nominal false-positive rate (FPR) guarantees unreliable, especially when the assumed null distribution does not match real unwatermarked text. We introduce PIPER, a presence-before-payload watermark that separates the two decisions by design. PIPER partitions the vocabulary into two keyed levels so that the same token observations support both decisions: a coarse level provides payload-independent evidence for presence testing, while a finer level carries payload information for recovery. Presence is decided by an exact binomial test over deduplicated effective contexts, and the payload is decoded only if this test accepts. Under the standard random-key model with an idealized PRF, we prove finite-sample FPR control for a presence test whose statistic and threshold are independent of payload size and decoder choice. We evaluate PIPER across generation lengths from \(T=100\) to \(T=1000\). At the representative \(T=300\) setting and a nominal \(1%\) FPR, PIPER requires no held-out threshold fitting under the stated null model and achieves empirical FPRs of \(0.86%\) and \(0.92%\) on model-generated and natural-text nulls, respectively, with \(98.7%\)–\(99.0%\) presence TPR across 8- and 16-bit payloads.Code is available at [this URL](https://anonymous.4open.science/r/PIPER-F6B3/).

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM watermarking, multi-bit watermarking, statistical hypothesis testing, false-positive control, payload recovery

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_ehCoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how to detect a multi-bit watermark before trying to recover its embedded message. PIPER uses a two-level vocabulary partition so that the same tokens support both tasks. It first tests watermark presence using an exact binomial test over distinct contexts, then recovers the message through voting and error correction. The paper proves false-positive control under a random-key model with an idealized pseudorandom function, and evaluates detection, message recovery, text quality, and robustness across several models and datasets.

Critical strengths
  1. The paper addresses a useful problem. Searching over possible messages can increase false positives if the full search procedure is not properly calibrated. PIPER provides a clear way to keep the presence decision independent of this search.

  2. The method has a clear statistical basis. The two-level partition lets the same tokens support both detection and message recovery. Under the stated random-key assumptions, context deduplication supports an exact binomial test whose false-positive guarantee does not depend on the decoder.

  3. The experiments show strong detection performance and examine its limits. At 300 tokens and a nominal 1% false-positive rate, the 8-bit setting achieves 98.7% detection and 95.0% correct acceptance and message recovery. Additional tests cover different models, text domains, fixed keys, and text edits.

Critical weaknesses
  1. Reliability for a fixed deployment key remains uncertain. The guarantee averages over random keys, while Table 4 reports an OpenGen false-positive rate of 0.333% at a target of 0.1% for one fixed key. Although the paper acknowledges this limitation, it matters for applications that keep the same key.

  2. The gain from shared evidence becomes smaller when text quality is considered. The main comparison fixes the generation bias, while the roughly quality-matched results in Table 13 show only a small CAR gain at 100 tokens. At 200 and 300 tokens, the tuned 25/75 disjoint baseline has higher CAR, although it also has slightly higher perplexity.

  3. Message recovery is weak after substantial text changes. Table 15 reports CAR of only 35.9% after mixing equal amounts of watermarked and unwatermarked text, and 10.3% after T5 paraphrasing. These results limit the method's value for recovering source information from edited text, even when watermark presence remains detectable.

Questions for authors
  1. Reliability across fixed keys. How much does the false-positive rate vary across individual keys, particularly on OpenGen? How often does it exceed the target level?

  2. Comparison at similar error rates and text quality. Do the gains over CTWL and tuned disjoint allocation remain when both the actual false-positive rate and text quality are matched? Please explain the small or reversed CAR differences in Table 13.

  3. Message recovery after edits. Can you report the stronger editing and mixing settings already evaluated but omitted from the tables, and compare message recovery with a strong baseline under the same attacks?

4 comments
AuthorsOpenReview ↗

False-Positive Rates Across Fixed Deployment Keys (W1, Q1)

As you correctly pointed out, our current theoretical analysis is conducted under the random-key setting, whereas practical deployment typically relies on a fixed key. This assumption is also commonly adopted in existing multi-bit watermarking methods. Extending our theoretical guarantees to the fixed-key setting is an important direction for future work. Interestingly, our additional experiments comparing a single fixed key with 100 independently sampled keys demonstrate that PIPER maintains reliable performance even under the fixed-key setting. The detailed results are presented in the following table.

Table: Fixed-key false-positive rates on large evaluation sets.

Evaluation setNominal FPRFixed key FPRMean across 100 sampled keysRange across 100 sampled keys
OpenGen (100K supplement)1.0%0.804%0.833%0.765%–0.915%
OpenGen (1M supplement)0.1%0.0761%0.0758%0.0673%–0.0840%
AuthorsOpenReview ↗

Comparisons at Matched False-Positive Rates and Text Quality (W2, Q2)

To more clearly demonstrate the advantages of PIPER over CTWL and Disjoint under comparable text quality, we conducted additional experiments with (T=300). Admittedly, while PIPER achieves strong performance in watermark presence detection, its message decoding accuracy is somewhat lower. To address this limitation, we further improved the decoding mechanism while preserving our two-stage detect-then-decode framework. Specifically, the original approach randomly partitions the vocabulary into four disjoint subsets and increases the probabilities of tokens in the subset corresponding to the target symbol. In contrast, our improved approach employs two independent random permutations, each excluding a designated partition, and applies a positive bias only to the intersection of the two remaining token sets. This modification enables a minimum-based selection among candidate symbols at each watermark position during decoding, effectively improving message recovery accuracy for short texts.

We note that CTWL faces a significant scalability limitation with increasing payload length, since its decoding procedure requires exhaustive evaluation of all possible candidate messages. For a 32-bit payload, the candidate space grows to 2322^{32} ,making exhaustive decoding computationally impractical. In contrast, PIPER avoids such exhaustive message enumeration. Furthermore, as the text length increases, more decoding evidence can be accumulated for each payload position,which is expected to substantially improve PIPER’s message recovery accuracy. The following table presents the detailed experimental results under comparable text quality.

Table: Performance comparison for 8-bit and 16-bit payloads under comparable text quality.

MethodBias δ8-bit PPL ↓8-bit TPR (%) ↑8-bit CAR (%) ↑16-bit PPL ↓16-bit TPR (%) ↑16-bit CAR (%) ↑
PIPER2.08.8298.7095.008.7899.0077.50
PIPER (Improved)2.08.721498.7097.908.756298.9093.60
CTWL3.08.688698.2098.208.797998.1098.10
Disjoint 25/752.28.711497.7094.608.943197.6786.33
Disjoint 50/502.28.859299.0089.808.725798.6760.33
Disjoint 75/252.28.876899.2052.209.0031100.0016.67

explain the small or reversed CAR differences in Table 13: This is primarily because PIPER can utilize only half of the original vocabulary for payload embedding, whereas Disjoint 25/75 can leverage the entire vocabulary to embed payload information at 75% of token positions. Consequently, PIPER accumulates less effective evidence for payload decoding, which partly explains its lower message recovery accuracy. Nevertheless, our subsequent improvements to PIPER effectively mitigate this limitation, achieving better decoding performance than Disjoint 25/75 in our experiments.

AuthorsOpenReview ↗

Payload Recovery under Text Editing and Mixing (W3, Q3)

Thank you for asking us to report stronger attack settings and compare message recovery with other multi-bit watermarks. PIPER is designed to support multi-bit attribution while controlling the false-positive rate of watermark detection. Editing and paraphrasing can alter the tokens and local contexts that carry watermark evidence, and mixing reduces the amount of watermarked text available to the detector and decoder.

The following table compares the performance of PIPER and other methods under identical attack settings. PIPER demonstrates strong watermark detection performance under most attacks. However, under more challenging attacks, such as T5-based paraphrasing, 30% token replacement, and truncation from 300 to 100 tokens, existing multi-bit watermarking methods generally suffer substantial performance degradation. Improving robustness against such severe attacks remains an important direction for future work. In particular, we aim to build upon our two-stage detect-then-decode framework to develop a more robust multi-bit watermarking scheme.

Table: Robustness comparison under different attacks. Each entry reports TPR@1% FPR / CAR (both in percentages). CAR denotes the joint correct acceptance-and-recovery rate. The best TPR and CAR for each attack setting are highlighted separately in bold.

AttackSettingPIPERMPACBREWCTWL
CleanNo attack99.50 / 97.2897.00 / 90.0063.33 / 63.3395.67 / 95.67
Token-preserving synonym edits5%99.00 / 90.7093.67 / 80.6748.33 / 48.3392.33 / 92.33
Token-preserving synonym edits10%96.80 / 72.1091.00 / 74.0034.67 / 34.6781.33 / 81.33
Token-preserving synonym edits20%67.80 / 17.0069.33 / 42.0013.67 / 13.6749.00 / 49.00
Token-preserving synonym edits30%26.70 / 1.9036.33 / 15.674.33 / 4.3319.33 / 19.00
Token-increasing synonym edits5%99.00 / 89.1092.67 / 81.000.00 / 0.0091.67 / 91.67
Mixing50% watermarked83.60 / 35.9026.33 / 10.0018.67 / 18.6719.33 / 19.33
Truncation200 tokens retained99.10 / 90.1087.33 / 71.3359.67 / 59.6782.33 / 82.33
Truncation100 tokens retained93.00 / 48.2026.33 / 20.0096.33 / 41.004.33 / 4.33
ParaphrasingT559.70 / 10.3013.67 / 8.6781.00 / 4.001.67 / 1.67

Thank you for the detailed response. The new results address much of my concern about fixed-key false positives. I still have concerns about whether the gains hold at comparable false-positive rates and how reliably the method recovers messages after substantial edits. I am keeping my original rating.

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

This paper proposes a new approach and metric for detection of multibit watermark: first detect if there is a payload embedded, and then decode the payload. Given this new metric, they propose a new method, PIPER, to encode multibit watermarks. PIPER build on Red-Green watermarks and MPAC (position allocation) with two vocabulary splits, one to detect the presence, and one to encode the payload. The experimental evaluation shows that this approach outperforms prior works.

Critical strengths
  • Discussion on which metric matters when evaluating multibit watermark is relevant. As pointed out by the authors (Section 3) prior works often implicitly use the distribution of the max under the null, and very few works mention it explicitly.
Critical weaknesses
  • The contribution is limited. The content of the paper is very sparse and some entire sections are mostly a reformulation of prior works. For instance, section 5 either contains trivial results, restate equations from prior sections (e.g. corollary 5.1 is the same as equation 8), or contains results that lack motivation (what does the average parent level signal condition mean in practice? What does the epsilon in equation 22 correspond to in practice? Why is there no experimental evaluation of those results?). The PIPER method is a small iterative improvement on MPAC, with a design that is not well motivated (e.g. the choice of hyperparameters are not ablated).
  • The experimental section is very sparse, and the writing only describe the values in Tables/Figures instead of giving takeaways. Only a single model is evaluated (OPT-1.3B) which is a small and very old model. Similarly, the watermark is evaluated on a completion task C4 whereas nowadays chat completion tasks are more relevant (and are what is evaluated in more recent watermarking works). There are very few baselines evaluated (e.g. why the different schemes mentioned in the appendix are not evaluated as baselines?).

Writing issues: The writing of the paper is poor and feels heavily AI-written (especially the appendix). Below is a non-exhaustive list of oddities in the paper:

  • Caption of Table 1 mentions the MC "keyword" but it never appears in the table
  • Appendix feels heavily AI-written and is very hard to parse (e.g. L-1333 "These results diagnose a mismatch between the native reference threshold and the deployed statistic in this configuration; they neither establish that MPAC cannot be calibrated nor characterize the held-out-calibrated MPAC rows in Table 1. A controlled-FPR comparison must calibrate or otherwise validate the complete verification rule on independent null data.")
Questions for authors
  • Q: Can the authors motivate better the design of PIPER? Why is it better than e.g. doing a two-sided binomial test with MPAC + aggregating p-values? Or compare to other schemes like [1]? The authors mention that in their case the statistic does not depend on the payload dimension (unlike the 2 approaches I suggest), why would this be a desirable property? (in their evaluation the authors always use a fix payload dimension)
  • Q: I think distortion-free schemes are more preferable in practice (e.g. SynthID is distortion-free and used by Google and Anthropic, the recently releases TextGrain is distortion-free and used by OpenAI). Is the PIPER idea applicable to a distortion-free scheme?

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

6 comments
AuthorsOpenReview ↗

Response to Weakness1

Our main contribution: We propose a shared-token hierarchical watermarking framework, in which the parent level is responsible for watermark presence detection, while the child level handles payload decoding. This design enables a two-stage detect-then-decode procedure: we first determine whether a watermark is present and then attempt to recover the embedded message. In contrast, many existing multi-bit watermarking methods either assume that the input text is already watermarked and focus solely on message decoding, or rely on payload-decoding signals to determine watermark presence.

The key advantage of our approach is that watermark presence is determined by a dedicated, payload-independent detection signal rather than the decoding signal. For methods that rely on decoding statistics for presence detection, reliable false-positive rate (FPR) control often requires empirical threshold calibration using held-out negative samples under specific experimental configurations. Such calibration can be inconvenient for practical deployment, particularly when models or generation settings change. In contrast, PIPER employs a parent-level statistic with an analytically characterized null distribution, enabling theoretically controlled FPR without requiring held-out data for threshold calibration under our stated assumptions.

Furthermore, our hierarchical design preserves the shared-token mechanism while separating presence detection from payload recovery. This modular structure allows us to incorporate more effective decoding strategies from existing multi-bit watermarking methods into the child level, potentially improving message recovery accuracy while retaining the independent parent-level presence test and its statistical guarantees.

Some content of the paper is redundant We agree that the false-attribution statement in Corollary 5.1 follows directly from the gating relation in Eq. (8). We will consolidate this material and present it more concisely as a consequence of the verifier design.

What does the average parent level signal condition mean in practice? The condition characterizes the average strength of the watermark presence signal across eligible token positions. Specifically, let $ Y_i$ indicate whether the i−thi-th eligible token belongs to its corresponding parent set, and let μi=Pr⁡(Yi=1∣Fi−1)\mu_i=\Pr(Y_i=1\mid\mathcal F_{i-1}) denote its conditional parent-hit probability under watermarked generation. Our assumption is $ \frac{1}{N}\sum_{i=1}^{N}\mu_i\geq\gamma+\epsilon, $ where γ=0.5\gamma=0.5 is the null parent-hit probability and ϵ>0\epsilon>0 represents the average signal advantage introduced by watermarking.

What does the epsilon in equation 22 correspond to in practice? In Eq. (20), epsilon is an assumed lower bound on the average conditional parent-hit probability above gamma, conditional on the effective sample size and preceding hit observations. For example, if gamma=0.5 and the assumed condition guarantees an average conditional hit probability of at least 0.6, one may take epsilon=0.1.

Under this condition, Eq. (22) characterizes the relationship between effective text length and detection reliability: for fixed false-positive and miss-probability targets, the sufficient length scales as $ 1/\epsilon^2$.

Hyperparameter and Experimental Setting Ablations We conducted extensive ablation studies in the appendix across different language models, datasets, text lengths, and watermark strengths (δ\delta). Based on these evaluations, we adopted T=300T=300, OPT-1.3B, the C4 dataset, and δ=2.0\delta=2.0 as the representative default configuration for our main experimental comparisons.

AuthorsOpenReview ↗

Response to Weakness2

We sincerely thank you for highlighting the issues in our experimental section. We have carefully revised this section to improve its clarity and presentation. To further evaluate the performance of our watermarking method in realistic chat-completion scenarios, we conducted additional experiments using Qwen2.5-7B-Instruct on 500 shared questions from the ELI5-Category test split, following a single-turn long-form question answering (LFQA) setting. Both watermarking methods were evaluated with an 8-bit payload and a generation budget of 200–300 new tokens, ensuring a consistent experimental setup. The detailed results are presented in the following table.

Table: Performance comparison of MPAC and PIPER using Qwen2.5-7B-Instruct.

MethodTPR @ 1% FPR ↑CAR ↑PPL ↓
PIPER91.8%38.4%2.7257
MPAC47.4%18.4%2.7118
Unwatermarked----2.3479

These results demonstrate that PIPER continues to achieve strong watermark presence detection performance in this setting. Although its payload recovery accuracy decreases , it still outperforms MPAC. We believe this degradation is primarily attributable to the relatively low entropy of the next-token distributions in this setting, where the probability mass is concentrated on a small number of tokens. Such concentrated distributions make effective watermark embedding and reliable payload recovery considerably more challenging. Indeed, low-entropy generation presents a fundamental challenge for existing watermarking methods. Improving watermark reliability under such conditions is therefore an important direction for our future research.

AuthorsOpenReview ↗

Response to Writing Issues:

We have noted writing issues and have rewritten the relevant sections of the appendix. We have also carefully reviewed the main text and revised passages that were potentially unclear to improve the overall clarity and readability of the paper.

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

PIPER is a multi-bit LLM watermark that biases only one child within a keyed parent vocab set, so the same tokens give presence evidence at the parent level and payload evidence at the child level. Presence is decided by an exact binomial test over deduplicated contexts, and the payload is decoded only after this test passes, which gives finite-sample FPR control under a random-key / ideal-PRF null. Experiments compare against MPAC, CTWL and BREW, and add a fixed-key null, a shared vs disjoint ablation and robustness tests.

Critical strengths

(1) Separating presence from payload is a clean design and easy to audit: the presence decision does not change with the decoder or payload size, and as the payload grows the FPR stays flat while CAR drops.

(2) The paper is fairly honest about the limits of its guarantee: it reports that the fixed-key FPR exceeds the nominal level on OpenGen, and it states that stronger edit settings were omitted.

Critical weaknesses

(1) The shared-evidence advantage depends on the quality budget and disjoint allocation. Table 11 uses fixed bias, where PIPER also has higher PPL than the balanced split. In the approximately quality-matched comparison in Table 13, the payload-leaning split has slightly higher CAR at intermediate lengths, still with somewhat higher PPL cost, while PIPER has higher CAR at the shortest and longest tested lengths. These results support a tradeoff rather than a uniform advantage at matched quality.

(2) I would like a clearer account of the gain from the shared hierarchical construction beyond the binomial testing and deduplication discussed in Appendix A.1. Table 1 shows that CTWL has higher CAR and lower PPL at the larger payload, although PIPER has higher presence TPR. PIPER's lack of held-out threshold fitting under its stated null is a useful distinction; the remaining question is how much practical benefit it offers over calibrated alternatives at comparable quality cost.

(3) The selected operating point incurs substantial relative PPL increases in Tables 8 and 10. The appendix includes additional models, domains and lengths, but the full comparison against competing methods in Table 1 is confined to OPT-1.3B at one generation length. Extending that comparison would help assess whether the quality-reliability tradeoff remains favorable elsewhere.

Questions for authors

See Weaknesses.

4 comments
AuthorsOpenReview ↗

Quality-Matched Comparisons (weakness1,weakness2)

To more clearly demonstrate the advantages of PIPER over CTWL and Disjoint under comparable text quality, we conducted additional experiments with (T=300). Admittedly, while PIPER achieves strong performance in watermark presence detection, its message decoding accuracy is slightly lower. In the revised version, we address this limitation by improving the decoding mechanism while preserving our two-stage detect-then-decode framework. Specifically, the original approach randomly partitions the vocabulary into four disjoint subsets and increases the probabilities of tokens in the subset corresponding to the target symbol. In contrast, our improved approach employs two independent random permutations, each excluding a designated partition, and applies a positive bias only to the intersection of the two remaining token sets. This modification enables a minimum-based selection among candidate symbols at each watermark position during decoding, effectively improving message recovery accuracy for short texts.

We would like to point out that CTWL faces a significant scalability limitation as the payload length in-creases, since its decoding procedure requires exhaustive evaluation of all possible candidate messages. For a 32-bit payload, the candidate space grows to$2^{32}$,making exhaustive decoding computationally impractical. In contrast, PIPER avoids such exhaustive message enumeration. Furthermore, longer text allows more decoding evidence to be accumulated for each payload position, which is expected to substantially improve PIPER’s message recovery accuracy. Detailed experimental results under comparable text quality are presented in the following table.

Table: Performance comparison for 8-bit and 16-bit payloads under comparable text quality.

MethodBias δ8-bit PPL ↓8-bit TPR (%) ↑8-bit CAR (%) ↑16-bit PPL ↓16-bit TPR (%) ↑16-bit CAR (%) ↑
PIPER2.08.8298.7095.008.7899.0077.50
PIPER (improvement)2.08.721498.7097.908.756298.9093.60
CTWL3.08.688698.2098.208.797998.1098.10
Disjoint 25/752.28.711497.7094.608.943197.6786.33
Disjoint 50/502.28.859299.0089.808.725798.6760.33
Disjoint 75/252.28.876899.2052.209.0031100.0016.67
AuthorsOpenReview ↗

The Gain of Shared Hierarchical Construction(weankness2)

By sharing the hierarchical construction, watermark presence detection and payload decoding can draw on evidence from the same token sequence, thus using the available text length efficiently. This also eliminates the need to optimize the allocation of tokens between presence detection and payload recovery. More importantly, our two-stage detect-then-decode framework relies on a payload-independent signal for watermark presence detection, enabling reliable false-positive rate control under the stated theoretical assumptions, regardless of the payload length.

AuthorsOpenReview ↗

Extended Experiments(weakness3)

As you correctly noted, we have already conducted extensive ablation studies across different models, datasets, and text lengths in the appendix. Accordingly, we selected a representative experimental setting with T = 300, OPT-1.3B, and the C4 dataset for our main comparisons, which is also commonly adopted in existing multi-bit watermarking studies. To further investigate whether PIPER’s advantages generalize to other language models, we conducted additional comparative experiments on Qwen2.5-3B. The results demonstrate that PIPER continues to exhibit competitive advantages over existing methods on this model, further supporting the generalizability of our approach. The detailed results are presented in the following table.

Table: Performance comparison for 8-bit payloads using Qwen2.5-3B.

MethodFPR (model / natural) ↓TPR ↑CAR ↑Corpus PPL ↓
MPAC1.00% / 1.00%99.00%86.33%10.78
CTWL0.67% / 1.33%89.67%89.67%7.54
BREW1.00% / 1.67%73.00%73.00%9.84
PIPER0.33% / 1.00%99.33%96.00%9.21

Thank you for the detailed response. The quality-matched comparison with the improved decoder helps with my main concern. The new Qwen2.5-3B results also help with the single-model setup. I will keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.