Necessary and Sufficient Watermark for Large Language Models

1 Introduction

• LLMs can generate natural, fluent text that humans can hardly distinguish from human-written text.The cited GPT-3 evaluation focused on news articles.Source: §1 · p. 1
• As LLM performance improves across tasks, the risk of malicious use increases, including generating fake news, using bots to manipulate election campaigns, and generating academic papers (Zellers et al., 2019).Source: §1 · p. 1
• Watermarking inserts information that is imperceptible to humans but identifiable by algorithms, offering a way to distinguish LLM-written from human-written text.The introduction cites Venugopal et al. (2011), He et al. (2021; 2022), Zhao et al. (2023b; 2023a), Kuditipudi et al. (2023), Kirchenbauer et al. (2023a; b), and Christ et al. (2023).Source: §1 · p. 2
• The Hard/Soft-Watermark can distinguish generated text from human text almost perfectly, but its vocabulary restriction often lowers generated-text quality.Kirchenbauer et al. (2023a) is credited with the method and reported detection result.Source: §1 · p. 2
• NS-Watermark imposes minimum detection constraints and is reported to improve text quality and detection accuracy over Soft-Watermark, with up to 30 BLEU-score improvement in machine translation.The authors also report competitive BLEU scores against conventional decoding methods without watermarks.Source: §1 · p. 2

2 Background

• Hard-Watermark divides the vocabulary into green and red subsets, then generates text using only green words.The green subset has size γ|V|, with γ as a hyperparameter.Source: §2 · p. 2
• Because humans do not know the random green/red assignment, green words are expected with probability γ in human text, while Hard-Watermark text contains only green words.This difference supports statistical hypothesis testing.Source: §2 · p. 2
• Detection tests whether the text's green-word z-score exceeds threshold Z, using the human-text green-word count's binomial distribution.The null hypothesis sets the rate to γ; the alternative is a rate greater than γ.Source: §2 · p. 2
• The authors coined “Hard/Soft-Watermark” for the methods proposed by Kirchenbauer et al. (2023a).Source: §2 · p. 2
• Soft-Watermark adds an offset to increase green-word probabilities, allowing likely common phrases such as “Barack Obama” while producing higher-quality text than Hard-Watermark.The passage says Soft-Watermark still suffers from low-quality text in the authors' experiments.Source: §2 · p. 3

3.1 Necessary and Sufficient Watermark

• Figure 1 marks the table entries that must be calculated and the entries satisfying the constraint, with a red line showing the minimum green-word count required.In the middle and right panels, T[t][Gmax] represents texts with at least Gmax green words.Source: Figure 1 · p. 3
• The final NS-Watermark constraint is looser than the Hard-Watermark constraint yet guarantees a generated-text z-score at least Z, allowing more natural text without decreasing detection accuracy.For human text, the green-word proportion averages γ, so the constraint includes only the minimum margin needed for identification.Source: §3.1 · pp. 3–4

3.2 Naive Algorithm for Necessary and Sufficient Watermark

• The naive algorithm fills table T[t][g] with candidate texts and selects the highest-probability text satisfying the constraint; capping counts at Gmax reduces complexity to O(γkTmax^2).Once Gmax green words appear, later green-word counts need not be tracked.Source: §3.2 · p. 4

3.3 Linear Time Algorithm for Necessary and Sufficient Watermark

• The linear-time approximation estimates output length with unwatermarked beam search, encourages periodic green words, and reduces computation to O(αkTmax).The α-controlled approximation restricts which table entries need calculation; after Gmax green words appear, no further count is required.Source: §3.3 · pp. 5–6

3.4 Robustness to Post-editing Attack

• The robustness variant tightens the constraint so detection remains possible after up to β(T−1) green words are replaced with red words.The passage defines β as a robustness hyperparameter and says the constraint is minimal for a z-score above Z after 50β% of words are replaced.Source: §3.4 · p. 6

4.1 Comparison Methods

• The comparison includes Soft-Watermark, NS-Watermark, and a per-text-tuned Adaptive Soft-Watermark, but excludes Hard-Watermark and methods focused on undetectability.The authors identify combining quality preservation and undetectability as a direction for future watermark design.Source: §4.1 · pp. 6–7

4.2 Machine Translation

• Across WMT, NS-Watermark outperforms Soft-Watermark and Adaptive Soft-Watermark on quality and detection, beats Soft-Watermark by approximately 30 BLEU, and reaches 100.0% TPR.Its BLEU scores are competitive with conventional beam search without watermarks.Source: Table 1 · p. 7, §4.2 · p. 8
• As text length grows, Soft-Watermark's z-score rises, and Adaptive Soft-Watermark's still rises despite per-text tuning; NS-Watermark adapts green-word proportions and keeps its z-score from increasing.The authors attribute the difference to NS-Watermark imposing the minimum constraint needed to exceed Z (= 4).Source: Figure 2 · p. 7, §4.2 · p. 8
• BLEU rises with α when γ is large but changes little when γ is small; small α can therefore be used near the γ setting with the best BLEU score.The authors attribute the stronger effect at large γ to the need for more green words.Source: §4.2 · p. 8, Figure 4 · p. 8
• Runtime increases with α when γ is large but is nearly unchanged as α increases when γ is small.The authors attribute the small-γ pattern to a smaller Gmax and a table range that does not expand with α.Source: §4.2 · pp. 8–9

4.3 Natural Language Generation

• On LLaMA-7B with C4, NS-Watermark also outperforms Soft-Watermark and Adaptive Soft-Watermark in text quality and detection accuracy.The evaluation compares methods using perplexity and detection accuracy.Source: §4.3 · p. 9, Table 2 · p. 9

4.4 Robustness to Post-editing Attack

• At the same PPL, NS-Watermark achieves a smaller FNR than Soft-Watermark, with a better quality–robustness trade-off; the comparison with Adaptive Soft-Watermark also favors NS-Watermark.The post-editing test randomly replaces a proportion of generated words and measures the resulting increase in FNR.Source: §4.4 · p. 9

Watermarking Methods

• Language watermarking skews generated-text distributions, such as green-to-red word ratios, for statistical testing; it offers high detection accuracy and adjustable FPR but can degrade text quality.The paper says its experiments indicate that prior work underestimated this quality degradation.Source: §5 · pp. 9–10
• NS-Watermark is distinguished from prior watermarking work by aiming to minimize text-quality degradation while retaining watermark-based detection.The cited discussion frames this as a contrast with methods that modify generated texts.Source: §5 · p. 10

Post-hoc Detection Methods

• Post-hoc detectors avoid quality degradation by leaving texts unchanged, but are inferior to watermarking methods in detection accuracy.The passage names both trained detectors and a curvature-based approach that needs no additional training.Source: §5 · p. 10

• The NS-Watermark achieves a 0% false negative rate with negligible text-quality degradation across the reported tasks.Source: §6 · p. 10
• The method imposes the minimum constraint required to detect LLM-generated texts.Source: §6 · p. 10
• The NS-Watermark improves the quality-detectability trade-off for post-editing attacks.Source: §6 · p. 10

• The NS-Watermark minimizes text-quality degradation but has higher time complexity than the Soft-Watermark, despite approximation methods.Source: §7 · pp. 10–11
• Reducing the NS-Watermark's time complexity remains a promising research direction.Source: §7 · p. 11
• Combining undetectable watermarking with minimum text-quality degradation is proposed as a future research direction.Source: §7 · p. 11

• The Soft-Watermark's constraints are overly restrictive and insert too many green words for detection.Source: A Necessary and Sufficient Watermark… · p. 14
• The Soft-Watermark generates more green words than required with non-zero probability, even when δ is tuned for each text.Source: A Necessary and Sufficient Watermark… · p. 14
• The NS-Watermark uses dynamic programming to insert the minimum number of green words and can generate higher-quality text than Soft-Watermark variants.Source: A Necessary and Sufficient Watermark… · p. 14

B Proof of Theorem 1

• The proof assumes beam size one, sufficiently long texts, real-valued δ, sufficiently small γ, and i.i.d. logits with a strictly increasing cumulative distribution.Source: B Proof of Theorem 1 · p. 14
• With the minimum δ that makes the z-score exceed threshold Z, the Soft-Watermark produces two or more green words with probability 1 − log 2.Source: B Proof of Theorem 1 · p. 14

C Additional Visual Explanation

• Figure 6 marks the table ranges to calculate, the ranges satisfying Eq. (4), and the minimum green-word count required by the constraint.Source: Figure 6 · p. 16

D Hyperparameter Setting

• Tables 3–5 list hyperparameter settings for the NS-Watermark, Soft-Watermark, and Adaptive Soft-Watermark; experiments ran on an A100 GPU.Source: Table 3 · p. 17, Table 4 · p. 17, Table 5 · p. 17

E.1 Robustness to Post-editing Attack

• At the same β, NS-Watermark consistently outperforms Adaptive Soft-Watermark in PPL, yielding a better text-quality and post-editing-robustness trade-off.Table 6 reports the comparison across β settings.Source: Table 6 · p. 18, §E.1 · p. 18

E.2 Visualization

• Figures 7 and 8 relate text length to z-score and green-word count; Figure 7 uses WMT’16 En→De validation data and tunes δ to the smallest value with FNR below 5%.Figure 8 uses the experimental settings of Figure 2.Source: §E.2 · p. 18, Figure 7 · p. 19, Figure 8 · p. 19

E.3 Trade-off between Text Quality and Generation Time

• BLUE scores generally increase with generation time, but with small γ, NS-Watermark achieves its best performance without generation time increasing as α grows.Figure 9 presents the text-quality and generation-time trade-off for various α values.Source: §E.3 · p. 19, Figure 9 · p. 19

F Pseudo-codes

• The appendix labels Algorithm 2 a linear-time NS-Watermark algorithm and provides pseudo-code for Adaptive Soft-Watermark variants.The supplied algorithm descriptions include maximum text length, vocabulary, and beam size as inputs.Source: F Pseudo-codes · pp. 20–21

F.1 Examples of Generated Texts

• The appendix includes generated-text examples for NS-Watermark, Soft-Watermark, and Adaptive Soft-Watermark across WMT translation and C4 settings.It also includes beam-search examples on C4 with γ = 0.0001.Source: Table 10 · p. 23, Table 11 · p. 24, Table 12 · p. 24