Necessary and Sufficient Watermark for Large Language Models
Authors: Yuki Takezawa
Ryoma Sato
Han Bao
Kenta Niwa
Makoto Yamada
Venue: Accepted by TMLR ()

Abstract: Large language models (LLMs) can now generate texts that are indistinguishable from those written by humans. Such remarkable performance of LLMs increases their risk of being used for malicious purposes. Thus, it is necessary to develop methods for distinguishing texts written by LLMs from those written by humans. Watermarking is one of the most powerful methods for achieving this. Although existing methods have successfully detected texts generated by LLMs, they inevitably degrade the text quality. In this study, we propose the Necessary and Sufficient Watermark (NS-Watermark) for inserting watermarks into generated texts with minimum text quality degradation. More specifically, we derive minimum constraints required to be imposed on the generated texts to distinguish whether LLMs or humans write the texts, and we formulate the NS-Watermark as a constrained optimization problem. Through the experiments, we demonstrate that the NS-Watermark can generate more natural texts than existing watermarking methods and distinguish more accurately between texts written by LLMs and those written by humans. Especially in machine translation tasks, the NS-Watermark can outperform the existing watermarking method by up to 30 BLEU scores.

Published in Transactions on Machine Learning Research (02/2025)
Necessary and Sufficient Watermark for Large Language Models
Yuki Takezawa Kyoto University, OIST
yull-tabesauoeem.kkt...koooo--
Ryoma Sato NII
rsato ac..pp
Han Bao
bao bao
Kyoto University, OIST
Kenta Niwa NTT Communication Science Laboratories
kenta. niwa. wl@hhco.tt..com
Makoto Yamada
makoto. @oist.jp
OIST
Reviewed on OpenReview:
https: openeviiee.. net/ forum? id= FcyHl2004k0
Abstract
Large language models (LLMs) can now generate texts that are indistinguishable from those written by humans. Such remarkable performance of LLMs increases their risk of being used for malicious purposes. Thus, it is necessary to develop methods for distinguishing texts written by LLMs from those written by humans. Watermarking is one of the most power- ful methods for achieving this. Although existing methods have successfully detected texts generated by LLMs, they inevitably degrade the text quality. In this study, we propose the Necessary and Sufficient Watermark (NS- Watermark) for inserting watermarks into gener- ated texts with minimum text quality degradation. More specifically, we derive minimum constraints required to be imposed on the generated lexts to distinguish whether LLMs or humans write the texts, and formulate the NS-Watermark problem. Through the experiments, we demonstrate that the NS-Watermark can generate more natural texts than existing watermarking methods and distinguish more accurately between texts written by LLMs and those written by humans. Especially in machine trans- lation tasks, the NS- Watermark can outperform the existing watermarking method by up to 30 BLEU scores.
constrained optimization
1 Introduction
Large language models (LLMs) have achieved remarkable performances in a wide range of NL.P tasks, including language generation (Chen al. 2021), question answering (Joshi al.) 2017 Kwiatkowski al. 2019), and reasoning tasks (Bisk al.] 2020 Kojima al. 2022). Recently, many pre-trained LLMs have been released (Brown al. 2020 Chung al. 2022 Zhang et al. 2022 Touvron et al. 2023), which can now generate natural and fluent texts that are indistinguishable from texts written by humans. For instance, Brown et al. (2020) evaluated the quality of the news articles generated by GPT-3, demonstrating that humans can hardly distinguish between news articles generated by GPT-3 and those written by humans.
As the performance L.LSs improves for various tasks, the risk that LLMs are used for malicious purposes, such as generating fake news, also increases [Zellers al.) 2019).. In addition fake news, it can be serious concern to use bots to try to manipulate election campaigns to LLMs to generate academic papers

---

Published in Transactions on Machine Learning Research (02/2025)
Kirchhnbaauer et al. 2023a Thus, it is crucial to develop methods to identify whether LLMs humans write texts. Watermarking is one of the powerful techniques for this purpose, which inserts information into texts such that the inserted information is imperceptible to humans and can be easily identified by some
algorithms Verugopal et al. 2011; He et al. 2021 2022 Zhao et al., 2023b Kuditipudi et al. 2023 Zhao
et al. 2023a; Kirchenbauer et al. 2023a b Christ. et al. 2023). Recently, Kirchenbauer el. al. (2023a) proposed
the Hard/SoftWattemarrk, Watermark, which inserts watermarks by generating text using only a subset of vocabulary
Texts generated by the watermarked LLMs consist only of a subset of vocabulary, whereas texts written by humans consist of an entire vocabulary. Thus, can identify whether LLMs humans write texts using statistical hypothesis testing. [Kirchenbauer et al. (2023a) demonstrated that texts generated by LLMs with the Hlard/Soft, Watermark can be distinguished from human-written texts almost perfectly. However, the generaled lexts are oflen low-quality because LLMs generate lexts with only a subset of vocabulary.
In this study, we propose a novel method for inserting watermarks into generated text without sacrificing both text quality and detection accuracy, which we refer to the Necessary and Sufficient Watermark WNS-Watermark). Our method is based on the observation that. the constraint imposed by the Hard/Solf Watermark is overly conservative for identifying LLM--generted texts, especially when the generated texts are long. Hence, we derive minimum constraints required to be imposed on the generated texts to detect LLM-generated texts. We find that the constraints on the generated text can be relaxed without decreasing the detection accuracy as the length of the generated text. increases. Based on this observation, we propose the NS- Watermark, which can change the constraints according to the length and impose minimum constraints on the generated text. Owing to the minimum constraints, the text generated with the NS- Watermark can be more natural than the text with the Hard/Soft- -Sott--aaterarr.. We experimentally evaluate the effectiveness of the NS-Watermarks and demonstrate that the XS-Watermark both text quality and detection accuracy. Particularly in the machine translation tasks, we demonstrate that the NS- Watermark can outperform the Soft- Watermark by up to 30 BLEU scores and achieve competitive BLEU scores compared to conventional decoding methods without watermarks.
outperform the Soft-Watermali in terms of
2 Background
In this section, we briefly describe the watermarking methods proposed by Kirchenbauer et al. Further discussions on related studies are deferred to Sec. 5
2023a
Hard- Watermake.,. Let Tprompe be prompt, be vocabulary, and 7 E (0, be a hyperparameter. Given a word F2, using Ia the sced value, we randomly split V into two disjoint subsets: green words V (1a) and red words Vred(z) V V (2x)) such that [Vgreem = >VV.. Then, the Hard- Watermaae generates
text as follows:
arg max P(ZETT xprompt) s.t. I+41 E V (x)) 1,2,, ... ,T-......-111. -1) ZIT.T
(1)
We randomly split vocabulary into red and green words, and humans do not know whether word is green or red. Thus, if humans write the text, the green words appear with probability 7, whereas texts written by LLMs consist of only green words. Thus, we can use statistical hypothesis testing to identify whether LLMs or humans write the text. Specifically, the null and alternative hypotheses are given as follows:
Ho: The green words appear in a text with probability y.
H1: The green words appear in a text with a probability greater than ?.
When the mull hypothesis is rejected, we conclude that the text is generated by LLMs. The number of green words follows a binomial distribution in texts written by humans. Thus, we can test this by checking whether the s-corre of text T1.7, defined below, exceeds given threshold Z.
- 11
2(Zir) =
(2)
()(1-))(T-1)
We coined the name "Hard/Soft- Saaanl//Sot-Wtterree Watermark" refer to the watermarking methods Kirchenbauer et al. 2023a
2

---

Published in Transactions on Machine Learning Research (02/2025)
where 11rrlG H #141 Vircen (xx)
Soft-Watermarke Although the Hard- Watermark is simple and efficient method for distinguishing LLM- generated texts from those written by humans, the generated texts are often of low quality, This is partly because the constraints of the Hard-Watermark may prevent the generation common phrases, e.g., "Barack Obama," even if the probabilities of these phrases are very high just because "Ohama" " not contained Vercen Vgreen ("Barack"). To mitigate this issue, Kirchenbauer et al. (2023a) also proposed the Soft- Watermark: instead of making all words contained in the generated text green words, the Soft-Watermark adds offset and increases the probability of generating green words. This relaxation allows the Soft- Srtt-Watrrmakk to generate "Barack Obama" when the probability that "Obama" appears after "Barack" is high, and the Soft- Sett-Waermarkk can generate higher-quality text than the Water-aa However, the Soft-Watens Watermark still suffers from low-quality text, as we demonstrate in the experiments.
3 Proposed Method
3.1 Necessary and Sufficient Watermark
In this section, we show that the constraints of the Bard/Soft-Wateneee are too restrictive and derive the minimum constraint identify whether LLMs or humans write the text. By rewriting Eq. [ the Hard- Watermark is reformulated follows:
T1.TGG 1.
arg max ((1iT Pprompt) s.t. uur.T
(3)
Let .1.T be the solution of Eq. 3 The z-score 2((1.T) is O(VT), and we can identify whether LLMs or humans write the text by testing whether the z-score exceeds the hyperparameter Z. However, the z- score 2((IT) increases with the length of the generated text T,, whereas the threshold Z remains constant. Therefore, the above formulation in Eq. g imposes too restrictive constraint the generated text, especially when ensuring =(x1T)) 2 Z for long texts.
199
199
199
Number of green words g
Number of green words
Number of green words
150
150
150
100
200
63
50
50
100 150
200
50
100
150
200
0
50 75
100 150
200
Number words t
Number of words
Number words
(a) Ilustrationn Alg.
(b) Illustraiinn of Alg.
Figure 1: Visualization of the table T[]] for Tmax = 200, 7 = T 75, a= 2, 7-4 4, and Gmax = 63. The areas colored in blue and light blue indicate the range in Tit]ig] where we need to calculate, and the areas colored in blue indicate the range that satisfics the constraint of Eq. 4 The red line indicates the minimum number of green words required to satisfy the constraint. Note that the middle and right figures, Gmax) does not denote the set of texts of length containing Gmax green words, but denotes the set of texts containing at least G green words. See Sec. C for figures with various 7.

---

Published in Transactions on Machine Learning Research (02/2025)
Alternatively, the following constraint is sufficient to ensure that the z-score of the generated text is greater than equal to the threshold Z:
FITIG T-1 27+ 2 T-1
(1-7)
arg max ((11T pprompt) s.t. #1T.I
(4)
If text 21.T is written by humans, the proportion of green words contained in text | is y on aver- T-1
age. Thus, the second term in the constraint is the minimum margin for identifying whether the texts are written by LLMs. We refer to the above problem as the Necessary and Sufficient Watermark (NS- Watermark). By comparing Eq. ( with Eq. 4 the constraint of the NS- NS-Watermark is looser than that in Eq. (3), although the z-score of the generated text is guaranteed to be greater than or equal to Z because of the constraint in Eq. 4 Thus, the NS-Watermark can generate higher quality and more natural texts than the Saard/Sof--aterrnen without decreasing detection accuracy. In the next section, we propose efficient algorithm for computing the NS- Watermark..
3.2 Naive Algorithm for Necessary and Sufficient Watermark
The Hard/Soff-Wateermart Watermark can be computed using the conventional beam search because the Hard- Watermark generates texts using only green words, and the Soft- Watermark just adds an offset to the probability that green words appear. However, the NS- NSS-Waermark needs to control the proportion of green words contained in generated lexts and needs to optimize where green words should be inserted. Moreover, the constraint in Eq. 4 depends on the length of the generated text T, which is unknown until the text is generated. This makes solving the NS-Watermark more challenging, which hinders the application of the conventional beam search to the NS-Watermark. In this section, propose algorithm to solve the NS- AS-Watermark.
Let k be the beam size. Let T[] be a set of k texts of length t containing, 9 green words. For simplicity, we explain the cases in which 1 S g and 1 t. Texts of length t + containing green words can be generated by adding a green word to texts of length t containing g 1 green words or adding a red word to texts of length containing g green words. Formally, we generate text of length t ++1 containing g green words follows:
X1 (Tra Fia T[4]g-- 1], Jz+1 E VVrreen (xx)),
X₂ = (I1s+1 Øig E T(tl[g), I2+1 E V (x))),
T + 1[[ = arg p(21:411 Eprompt).
Xx,X,XX,
By calculating [[][s] for all y and 1 and generating the text with the highest probability among the texts that satisfy the constraint in Eq. (4) we can solve Eq. 4
Let Tmax a hyperparameter that controls the maximum length generated texts. We need to fill the table Titl[g] for all (t.g) E ((t,g) E 2² < t < Taxx S g S - 1}, which requires the time complexity OKT ( (see the left figure in Fig. lap. However, if (= (T - + words appear after generating & words, it is not necessary to count the number of green words that appear in the remaining text because the constraint in Eq. 4 is satisfied regardless of the remaining text. Based on this observation, we can reduce the time complexity by changing [mt][G to store texts of length containing at least Gmax green words, instcad of texts containing exactly Guax green words. Owing to this modification, we do not need to count the number of green words after Gmax green words appear in texts and can reduce the time complexity to O(ykT?mmx) We provide a visual explanation in the figure on the right side of Fig. la and show the pscudo-code in Alg. I
- 1)]) green
3.3 Linear Time Algorithm for Necessary and Sufficient Watermark
Algorithm 1 in the previous section has the time complexity of ((ykTRax) which practically not suitable for LLMs with an extremely large number of parameters. We resort to an approximation and reduce the time complexity to linear.
4

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 1: Naive algorithm for the NS-Watermart
Input: Maximum number of words T Tmax, vocabulary V, beam size k, and hyperparameter 7, Z.
Gmax f mmx 1) + Z 7 ((([->)([Tmae)))
1)].
Let T be Tmax x mmax + 1) table and 5 be an empty set.
Function updale(X: feasible sel, l: the numbbrr of words g: the number of green words) is T[t][g] + 0.
while [Ttl[l]] < k do
6
T1:t = arg exx P(11a | Iprompt). if the last word de is EOS then
if 9 2 r(t 1) Z ZV>(1 7)(t -)
1) then
9
5 - SU
10
else
L [ - T[][g] U (xra).
11
12 Function feasible_setiee the number of words, g: the number of green words) is
13
if g = 0 then
X + {aiæ #1a-1 E T 1][g], 22 E V (2)-1))
14
clsc if g - then
16
X + {I1a F1:-- E T 1|lg 1).zt 22 Vereen (green(x))11) (x1-1)}
17
else if 1 S < Gmoz then
18
X - {Tia Tia-1 E T( - 1|[g 11 2t E Vireen (x;-1)
X ( F1a-1 E [ ||[g] vx (red
19
clsc if g Gmaz then
X - (r1a -na-1 E T( - 1|[g 1), Vireen (x=- 1)}.
21
22
X X (1i 1ia-- E T(t - 1|[9). 24 V}.
23
return X
T[1][0] arg top-k ÆEEV p(11 p.rompt).
for 1= 2. Tuu do 25
for g 0. ... min(t - 1, mmaz) do 28
27
x feasible set(t, (xtlate(Xtt,))
28
return arg max 2 ES. (Tmalll p( prrompt).
The major bottleneck of the quadratic time complexity in Tmax is that Alg, I requires us to fill the entire table [[][g] for all (t,g) E ((t,g) 1 1 Tmax, S S min(t- Gmax]) This allows generated texts to contain many green words locally because the constraint in Eq. ( only restricts the green words to appear above a certain number in generated texts. To reduce this computation, we additionally impose a constraint such that the green words appear periodically in generated texts. Technically, proportion of green words appearing in the generated text depends on its length T as Eq. (4) which is unknown & priori. For instance, generated text typically short for closed-ended question, and the proportion of green words needs to be large. By contrast, generated texts tend to be long for news articles, and the proportion of green words can be reduced. Thus, to make green words appear periodically in the generated text, we need to estimate the length of the generated text before generating it.
challenging because the
To estimate the text length, we leverage the observation that the length generated texts remains almost the same regardless watermarks because the text length is generally determined by the content of the generated texts, i.c., the prompt. Inspired by this observation, we propose generating the texts without watermarks using the conventional beam search, obtaining the length of generated text. T, and generating
5

---

Published in Transactions on Machine Learning Research (02/2025)
text with watermarks by solving the following problem:
arg maxp(aiir Fprompt) #1rr7
(5)
kirlG
111 7
s.t.
7 2
T-1
T-
k t-
min
1,7+ + 2 f-1
((1-7)
$ t-1
a or |21--16G 2 Gmax (t = 2, ... ,)),
where a 2 1 denotes a hyperparameter that controls the approximation rate. Intuitively, the second inequal- ity makes green words appear periodically and the last inequality verifies whether Gmax green words appear before the first 6 words. As explained in the previous section, if Gmax green words appear after generating - words, the number of green words added in the remaining texts needs not be counted anymore. Thus, we only need to impose the last inequality
the generated lext until Gmax green words appear. We show the visual explanation in Fig. lb Owing to this additional constraint, we do not need to fill the table [[] for all gt,g) E ((t,g) E N2 | istt maxx, 0 Σ g I min 1, Gmax] We only need to fill the table [ for (1.g) that satisfies the conditions Eq. 5 (i.e., the colored area in Fig, 1b Subsequently, the time complexity can be reduced to O(akTmax). We show the pseudo-code in Sec.
3.4 Robustness to Post-editing Attack
In the previous sections, we proposed the watermarking methods that impose the minimum constraint to detect LLM-generated texts. However, due the minimality of the constraint, the NS- NS-Watermark can be removed from the generated texts by replacing only one green word with a red word. To make the watermarks robust against such editing, we can tighten the constraint. follows:
7( (1-7)
arg max max p( (pprmpp) s.t. F1r.T
T T-1 2
Z
(6)
T-1
where 3 2 is a hyperparameter that controls the robustness. Owing to the constraint in Eq. 6 the z-score of the generated texts excoeds even if - green words are replaced with red words, and we can identify them as the lexts generated by LLMs. Moreover, the constraint in Eq. (6) is also the minimum constraint required to be imposed on the generated texts such that the z-score exceeds Z after 50,5% words are replaced. In Sec. 4.4. we experimentally evaluate the trade-off between text quality and robustness against the post-editing attack, demonstrating that the NS- Watermark can achieve the better trade-off than the Soft- Watermaarr..kk.
4 Experiments
4.1 Comparison Methods
In the following sections, we evaluate the following three methods: (1) The Soft- Watermark (Kirchenbauer let al. 2023a), which generates texts such that almost all words contained in the texts become green words by increasing the probability that green words appear. A hyperparameter d 2 0 a positive offset for the probability that green words appear. When 8 is set to a larger value, more green words appear in the generated texts. (2) The NS-Watermark, which generates texts containing the minimum number of green texts, unlike the Soft- watt-maarrr.kk.
words to detect ALM--genrrtte simple extension of the Natt-Watrrmark The original Soft- Watermark uses the same hyperparameter å for all texts, and the proportion of green words contained in a generated text is almost constant regardless of text length. Thus, the probability offset ó used by the Soft- Watermarkk increases the number of green words more than necessary to detect LLM-generated texts, especially for long texts. We improve the Soft- Watermark such that 5 is tuned for each text, which we refer to as the Adaptive Soft- Watermark. Specifically, the Adaptive Soft- Watermark finds by binary search and uses 8 such that the z-score is minimum and exceeds the threshold Z. We present the pseudo-code in Sec. Tn this section, we did not evaluate
(3) The Adaptive Soft-Watermark,

---

Published in Transactions on Machine Learning Research (02/2025)
Table 1: BLEU scores and detection accuracy with NLL.B-00-33333 and WMT. For the NS- NS-Watermark, we set to one and 3 to zero. The best values among the watermarking methods are highlighted in bold.
En + De
De En
BLEU
FNR 4 FPR 4
BLEU 1
FNR + FPR. 4
w/o Watermark
36.4
n.a. 0.4%
42.6
n.a. 0.5%
Soft- Watermark
5.2
3.0%
7.5
3.3%
Adaptive Noft-Watermark
20.5
0.0 % 2.6%
20.6
0.0 % 1.9%
NS- Watermark
32.7
0.0 % 0.3 %
38.2
0.0 %
0.0 %
En + Fr
Fr + En
BLEU t
FNR J FPR +
BLEU 1
FNR | FPR.
w/o Watermark
42.6
n.a. 5.4% 0.3 %
40.8
n.a. 0.6%
Soft- SittWWatrmmrk
9.6
7.6
3.6%
Adaplive Soft-Waternark
23.3
0.0 % 2.2%
19.5
0.0 % 2.8%
NS-Watte Watermark
38.8
0.0 % 0.3 %
36.8
0.0 % 0.1 %
since it has the very serious problem of being able to generate common phrases or proper nouns, e.g., Barack Obama, when Obama is red word. Furthermore, we did not evaluate existing watermarking methods that focused the "undeleclabilit focused on minimizing the text quality degradation caused by watermarking. These goals were orthogonal, and it is one of the interesting directions to design a novel watermarking method to achieve both properties.
of watermarks (Christ et al. 2023 Kuditipudi et al. 2023). Our paper
4.2 Machine Translation
Experimental Setting. We evaluate the effectiveness of the NS- NS-Watermark on machine translation tasks. We used NLLB-200-3.31 model (Team et al. 2022) with the test dataset of WMT French (Fr) + English (En) and 1M German (Dc) <> English (En). Following the prior work (Kichhenbauer et al. 2023a we set the hyperparameter to 4. For other hyperparameters, we split the data into the validation and test datasets with 10/90 ratio and used the validation dataset to tune. For the NS- Watermark, we selected y with the best BLEU score (Papineni al.] 2002) the validation dataset using grid scarch. The z-score of texts generated by the NS- Watermark is guaranteed to be greater than equal to Z, and the FNR of the NS- Watermark becomes exactly 0% for any hyperparameters. By contrast, the z-score of text generated by
y- 0.1
300
y-811
y-0.1
0.01
y=0.01
y=0.01
y
250
0.00
ym 0.001
40
y- 0,0001
7-Score
z-score
200
z-score
30
150
100
50
10
20
40
60
100
20
40
160
20
40
80
6b
100
Number of words
Number of words
Number of words
aa) NS-Watermark
(b) Soft- Soft-Watermark
(c) Adaptive Sattrmaarra
Figure 2: Relationships between z-score and the length of generated lexts. We used the validation datasets of WMT'16 En-+ee. For each 7, we tuned the hyperparameter 8 the Soft- Watermark by increasing 4, 6, 6,8.... and selecting the smallest value such that the FNR becomes less than 5%. We omit the results of the Soft- Watermark and Adaptive Soft- Watermark for 7 0.0001 because the z-scores become too large. Full results deferred to Sec. F.2

---

Published in Transactions on Machine Learning Research (02/2025)
y-
y-0.1
0.01
0.01
20
30
0.0001 SoftWWatermark
0.0001
Seconds
BLEU
0.1, a-
0.01, a=
10-
20-
0.001,
0.0001,
0
Figure 3: Time required to generate a Figure 4: Text quality when varying a. We used the validation text when varying a.
dataset of 1M En-
the Seet-Watrrmark and Adaptive Soft- Soft-Watermark is not guaranteed to be greater than or equal to Z. Thus, to fairly compare the NS-Watermark with the Soft- Soft-Watermark and Adaptive Soft- Watermark, we selected the hyperparameters of these methods with the best BLEU score while achieving more than 95% FNR in the validation datasct using a grid search. See Sec. for more detailed hyperparameter settings.
Results E Table 1 shows that the NS- Watermark outperforms the Soft- Watermark and Adaptive Soft- Watermark in terms of both text quality and detection accuracy. For all datasets, the Soft- Soft-Watermark significantly degraded the BLEU scores. The Adaptive Noft-Watermark improved the BLEU scores by tuning 8 for each lext, although it still achieved lower BLEU scores than the generated texts without watermarks. By contrast, the NS-We Watermark outperformed the Soft- Watermark by approximately 30 BLEU scores and achieved competitive BLEU scores with the conventional beam search without watermarks. Moreover, the NS- Watermark can achieve 100.0% TPR because the NS- Watermark is guaranteed to insert a sufficient number of green words into the generated texts.
Analysis of z-score and Length of Texts. Figure 2 shows the z-scores and length of generated texts. We also plot the relationship between the number of green words and the text length in Sec. E.2 In the Soft- Watermark, the z-score increased as generated texts became longer. As discussed in Sec. 3.3 the proportion of green words can be reduced as the length of generated texts increases. However, the Soft- Watermakr cannot change the proportion of green words adaptively to the text length, resulting in generaling texts with unnecessarily many green words for long texts. The Adaptive Soft- Watermark mitigates this problem by tuning 8 for each text, although its z-score still incrcases as the length increases. By contrast, the NS- Watermaakk can change the proportion of green words adaptively to the length, and the z-score does not increase even if the text length increases. Thus, the NS- IS-Watermark imposes the minimum constraint make the z-score of generated texts exceed the threshold Z(= 4) and can generate more natural and higher-quality texts than the Sett-Watemmark and Adaptive Soft- Watermark.
Analysis of Approximation Rate a. In the above experiments, we demonstrated that the NS- Watermark outperforms the Soft- Watermark and Adaptive Soft- Watermark when a is set to one. As we explained in Sec. 3.3 the text quality can be improved using the larger a. In this section, we analyze the sensitivity of a text quality. Figure shows the results when varying a. The results indicate that when y is large, the BLEU scores increase with a, but when 7 is small, the BLEU scores more green words need to be contained in the generated texts when y is large. Therefore, the larger 7, the greater the influence of the approximation, and we need to use large to generate high-quality texts. Fortunately, because the NS-Watermark achieved the best BLEU score when y was small, we can use the small a without degrading text quality much in practice.
almost the same. This is because
Running Time. Fig. 3 shows the running time when varying a. To measure the running time, used the validation datasct of 1M En- and reported the average running time. For 7
Note that Kirchenbauer 2023a) evaluated quality and detection accuracy with only consisting of approxi- mately 200 words, while evaluated them with generated texts, which contain both short and long
8

---

Published in Transactions on Machine Learning Research (02/2025)
Table 2: Text quality and detection accuracy with LLaMA-7B and C4 dataset. For the NS- Watermark, we set (ax, 3) = 01, The best values among the watermarking methods are shown in bold.
PPL 4
FNR 4 FPR
w/o Watermark
1.85
n.a. 2.8% / 0.1 %
Soft- Watermark
6.25
Adaptive Soft- Watermark
2.48
0.2% 0.8%
NS- Watermark
1.92
0.0 % / 0.3%
0.1, 0.01, 0.001, 0.0001, Gmax is 22, 5, 2, and 1, respectively. The results indicate that the running time in- creases as increases when y large. This result was consistent with the time complexity of Alg, 2 which discussed in Sec. 3.3 Then, when y was small, the rumning time was almost the same even if a increased. This is because when y is small, Gmax is small, and the range in the table [[]][]] where we need to fill in Alg. is small. Thus, the range in [[] where we need to calculate does not increase even if increases when y is small.
4.3 Natural Language Generation
Experimental Setting. Next, we compare the NS- VS-Wattrmark and the Soft-Watermark in terms perplex- ity (PPL). We used LLaMA-7B model (Tovrron et al. 2023 with the subsets of C4, realnews-like dataset (Raffel al., 2020). Based on the prior work (Kirchenbauer first 90% of words the prompt to infer the remaining 10% of words using LLMs. We regarded the last 10% of words contained in the data as the text written by humans and compared the NS-Watermart with the Solt-Watermark and Adaptive Soft-Walermark in terms of PPL and detection accuracy. Then, we set the hyperparameter Z to 4. To tune hyperparameters, we split the dataset into validation and test datasets with 10/90 ratio. As in the previous section, we selected the hyperparameters of the Soft- Watermark and Adaptive Soft- Watermark with the best PPL while achieving more than 95% FNR in the validation dataset using a grid search. See Sec. D for more detailed hyperparameter settings.
al., 2023a),, we split each text and used the
Results. The results are listed in Table 2 The results were consistent with those presented in Sec. 4.2 The NS- Wsttrrtrmakk outperform the Soft- Watermark and Adaptive Soft- Watermark in terms of text quality and detection accuracy.
4.4 Robustness to Post-editing Attack
In this section, analyze the trade-off between text quality degradation and robustness to post-editing, demonstrating that the NS- Watermark can achieve better trade-off than the Soft- Soft-Watermark.
Experimental Setting. To simulate the post-editing attack, we randomly select e% words in the generated texts and replace them with random words. We then analyzed how much FNR increases after the editing, We used LLaMA-7B model and the validation dataset of C4. For the NS- DS-Watermark, we showed the results when varying 8 {0, 0.05, 0.1, For other hyperparameters, we used the values shown in Sec. D
Results. Figure shows the relationship between text quality and robustness against post-editing of the NSteeraaakkk and Soft-Watermark with various hyperparameters. By comparing the results of the NS- Watermark and Soft-Watermark with the same level of PPL, we observe that the NS- a smaller FNR than the Soft-Waterrark. Thus, the NS-Watermark can achieve a better trade-off bet text quality and robustness than the Soft- Watermark. In Sec. E.I we also compared the NS- Watermark with the Adaptive Soft- Satt-matrmakk and demonstrated that the NS-Watermark can achieve a better trade-off than the Adaptive Soft-Watermark,
achieved
5 Related Work
Watermarking Methods. Watermarking methods detect LLM-generated texts by inserting imperceptible information into generated texts. Watermarking methods have been extensively studied for images and
9

---

Published in Transactions on Machine Learning Research (02/2025)
12
V
6-8
NS Watermark (y- 0.0001)
NS-Watermark (y= 0.001)
NS-Watermerk (y= 0.01)
10
NS-Watermark (y=0.1) 0.1]
8-022
B-02
Watermark (y- 0.0001)
8-
0.2
Ad =0
8-
=.2
Soft-Waterarkk (y= 0.001)
Soft Wateraar (y=
PPL
==0.2
PPL
#=02
Soft Watermark (y=
2-02
66=6
6
8=02
0=0.1
8=0.1
A- 0.2
8-00
4-
6-0.11
2-0.1 f-
0.00
8-
A
V6-4
# 0.05
6
0.05
6-4
2-
f=000
2
0.00
0.05
0.10
0.15
0.20
0.25
0.00
0.05
0.10
0.15
0.20
0.25
FNR
FNR
(a) 0.1
(b) 0.2
Figure 5: Trade-off between text quality and robustness against post-editing, To make the figure more readable, the results with FNR greater than 25% were omitted. The method with the point in the lower left corner is the superior method. Surprisingly, the NS- WStterrrmark is generally more robust against the post-editing than the Soft-Watermark even with a small offset B == 0.05.
audio (Luo al. 2020 Liu et al. 2023 However, due to the discrete structure of language, watermarking methods for natural language have been more challenging than those for images and audio. Recently, Kirchenbauer et al. (2023a) proposed the first practical watermarking method for LLMs. Kuditipudi et al. (2023) have exlended it and proposed methods that are robust against post-editing, and Christ et al. (2023) proposed undetectable methods. These methods skew the distributions of generated texts (e.g., the ratio of green and red words) and detect LLM-generated texts using statistical hypothesis testing. One advantage of watermarking methods their high detection accuracy. Furthermore, thanks statistical hypothesis testing, the FPR be explicitly adjusted by the hyperparameter. However, because watermarking methods need to modify generated texts, generated texts are often of low quality. Our experiments indicated that the existing methods underestimated text quality degradation caused by watermarking, and the NS-Watermark differs from them in that it aims to minimize text-quality degradation.
Post-hoc Detection Methods. As an altornative approach, post-hoc dctection methods have been pro- posed (Zellers et al., 2019 Gehrmann el al.) 2019 Tian & Cui 2023; Mitchell al.] 2023). Zellers et al. (2019h and Tian & Cuil (2023) proposed training additional models to detect LLM-generated texts. [ittheel] al. 2023) also found that LLM-generated texts tend to be texts at which the curvature of the LLMs log- likelihood becomes negative and demonstrated that those can be identified without training additional models. These post-hoc methods do not degrade text quality because they do not modify generated texts. However, post-hoc methods are inferior to watermarking methods in detection accuracy (Krishna et al. 2023
6 Conclusion
In this study, we proposed the NS-Watermark for inserting watermarks into generated texts with mini- mum text quality degradation. Specifically, we proposed the NS-Watermark that imposes the minimum constraint required to detect LLM-generated texts on generated texts. We conducted the experiments on various lasks, showing that the NS- XS-Watermark can achieve 0% false negative rale with negligible texl qual- ity degradation. Furthermore, the experimental results demonstrated that the NS Watermaakkk improves the dualityydeto tradc-off for post-editing attacks.
7 Limitations
The NS-Watermark can minimize text quality degradation, while increases the time complexity. We proposed the approximation methods to alleviate this issue, but its time complexity is still higher than that
10

---

Published in Transactions on Machine Learning Research (02/2025)
of the Sett-Watrrmak. Reducing the time complexity of the NS- WSs-aaermarkk is one of the promising rescarch directions. Besides the methods that minimize text quality degradation, several papers studied undetectable watermarking methods (Hu et al. 2024] Christ et al. (023). It is also a very promising research direction to study undctectable watermarking methods with minimum text quality degradation by extending our work.
References
Yonatan Bisk, Rowan Zellers, Ronan Le Bras, Jianfeng Gao, and Yejin Choi. PIQA: reasoning about physical commonsense in natural language. In AAAT Conference on Artificial Intelligence, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Nee- lakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christo- pher Berner, Sam McCandlish, Alec Radford, Ilya Sulskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harrison Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethca Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, David W. Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- William H. Guss, Alex Nichol, Igor Babuschkin, S. Arun Balaji, Shantanu Jain, Andrew Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matchew M. Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, llya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. In ArXi,, 2021.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In arXiv, 2023.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyum Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. Scaling instruction- instruction-finetuned language models. In arXiv, 2022.
Sebastian Gehrmann, Hendrik Strobelt, and Alexander Rush. GLTR: Statistical detection and visualization of generated text. In Annual Meeting of the Association for Computational Linguistics, 2019.
Xuanli He, Qiongkai Xu, L. Lyu, Fangzhao Wu, and Chenguang Wang. Protecting intellectual property of language generation apis with lexical watermark. In AAAI Conference on Artificial Intelligence, 2021.
Xuanli He, Qiongkai Xu, Yi Zeng, Lingjuan Lyu, Fangzhao Wu, Jiwei Li, and Ruoxi Jia. CATER: Intel- lectual property protection on text generation APIs via conditional watermarks. In Advances in Neural Information Processing Systems, 2022.
Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In International Conference on Learning Representations, 2024.
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge datasct for reading comprehension. In Annual Meeting of the Association for Computational Linguistics, 2017.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning, 2023a.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. In Xin 2023b.
11

---

Published in Transactions on Machine Learning Research (02/2025)
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, 2022.
Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit lyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. In arx,,, 2023.
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free water-
marks for language models. In arXiv, 2023.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wer Wei Chang, Audrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: A benchmark for question answering research. In Transactions of the Association for Computational Linguistics, 2019.
Chang Liu, Jie Zhang, Han Fang, Zehua Ma, Weiming Zhang, and Nenghai Yu. Dear: A deep-learning-basse audio re-recording resilient watermarking, In AAAI Conference on Artificial Intelligence, 2023.
Xiyang Luo, Ruohan Zhan, Huiwen Chang, Feng Yang, and Peyman Milanfar. Distortion agnostic deep watermarking. In IEEE/CVF Conference Computer Vision and Pattern Recognition, 2020.
Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D Manning, and Chelsea Finn. DetectGPT: Zero-shot machine-generater text detection using probability curvature. In International Conference on Machine Learning, 2023.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic evaluation of machine translation. In Annual Meeting on Association for Computational Linguistics, 2002.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. In Journal of Machine Learning Research, 2020.
NLLB Team, Marta R. Costa-jussà, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, Anna Sun, Skyler Wang, Guillaume Wenzek, Al Youngblood, Bapi Akula, Loic Barrault, Gabriel Mcjia Gonzalez, Prangthip Hansanti, John Hoffman, Semarley Jarrett, Kaushik Ram Sadagopan, Dirk Rowe, Shannon Spruit, Chau Tran, Pierre Andrews, Necip Fazil Ayan, Shruti Bhosale, Sergey Edunov, Angela Fan, Cynthia Gao, Vedanuj Goswami, Francisco Guzmán, Philipp Kochn, Alexandre Mourachko, Christophe Ropers, Safiyyah Saleem, Holger Schwenk, and Jeff Wang. No language left behind: Scaling human-centered machine translation. In arXiv, 2022.
Edward Tian and Alexander Cui. Gptzero: Towards detection of ai-generated text using zero-shot and supervised methods, 2023. URT htttps://ppterro .me]
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficiont foundation language models. In arXiv, 2023.
Ashish Venugopal, Jakob Uszkorcit, David Talbot, Franz Och, and Juri Ganitkevitch. Watermarking the oulputs of structured prediction with application in statistical machine translation. In Conference Empirical Methods in Natural Language Processing, 2011.
Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. In Aduances in Neural Information Processing Systems, 2019.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shustor, Danicl Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. OPT: Open pre-trained transformer language models. In Xiv, 2022.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai- generated text. In Xin, 2023a.
Xuandong Zhao, Yu- Yu-Xiang Wang, and Lei Li. Protecting language generation models via invisible water- marking. In International Conference on Machine Learning, 2023b.
13

---

Published in Transactions on Machine Learning Research (02/2025)
A Necessary and Sufficient Watermark is Provably Better than Soft-Watermark
In Sec. 4 we demonstrated that the Soft- Watermark imposes overly restrictive constraints on generated texts and inserts too many green words to detect LLM-generated texts. The Adaptive Soft-Watten Wa--Waatrrakkkk tunes for each text, but Sec. 4 showed that the Adaptive Soft- Watermark remains to insert too many green words into texts. We rigorously analyze this issue, providing the following theorem, which shows that no matter how well the hyperparameter is tuned for each text, the Soft- Watermark cannot precisely control the number of green words in generated texts and generates text that contains more than the required number of green words.
Theorem 1 (Informal). If we select minimam 6" E R such that the z-score of the text generated by the Soft- Watermark exceeds the threshold Z, the Soft- Watermark generates a text that contoins more than the required number of green words with non-zero probability.
The formal theorem and its proof are presented in Sec. Unlike the Soft Koft-Watermark and Adaptive Soft- Watermark, the NS- Watermark can insert the minimum mumber of green words into generated texts using dynamic programming and thus can generate higher-quality texts than these methods.
B Proof of Theorem
Assumption 1. The beam size is set to one.
Assumption 2. The length of generated terts is sufficiently long-
Assumption 3. =
Assumption The hyperpanameter y is sufficienthy small such that the text generated by the greedy search does not conlain green words, and terts conlaining single green word have z-score grealer than the threshold Z for any length T.
Assumption For any prompt prromps and generated text TYT, L((xiT), defined below, is an independent and identically distributed random variable that follows the distribution L((21:) p(-):
L((x1T)= = logit(xe 1:lc-1:ppoompp
max (EV
logit(<> F1a-1, 11 Froompt)
where logit(- 1-) is the output just before the last softmaz layer in LLMs. Furthermore, assume that its cumulative distribution function is strictly increasing.
Lemma Let F1. be the text generated by greedy search (i.e., text without watermarks). We then select the minimum 8t A such that the z-score of the text generated by the Soft- Watermark exceeds the threshold and 3 the selected hyperporameter 8* satisfies the following:
Z. Under Assumptions
8* = E min L((ra)))
Furthermore, under Assumption
8+ satisfies
8* = min [x(rrr).
Proof. 1f 8 min; (((rr)), the text generated by the Boft-Watermark is fir and does contain green words. 8 2 min, Le(rir), (min(t La(rir) S 5)) word becomes green word, and the text contains least one green word. Thus, we can obtain the statement.
Thcorem (Formal). We select the minimum 8* E such that the z-score of the text generated by the Soft- Watermark exceeds the threshold Z. Under Assumptions 0 Soft- Watermark with 5* contains two or more green words with probabilily log
2 3 4 and the text generated by the
14

---

Published in Transactions on Machine Learning Research (02/2025)
Proof. Let Fi. be the text generated by the greedy search. We define e(-) and Liin as follows:
c(a) = [ p())d;
Timn min (r(ri)).
From Lemma] | we have 8 min, Lo(rir)) and (== minft L((rir) 8))-th word becomes green word in the text generated by the Soft- Sett-Watermark Then, the probability that the remaining text has no green words is c(Lmin)T=e' Moreover, giving that the t* has equal probabilities for 2,3, ........ ,T the probability that the texts generated by the Soft-Watermark with 8 contain only one green word is given as
1 of L(mia)) T'
ol mmin) T-t
(7)
T
(T 1)(1 c c(runnn)
Next, we consider the distribution of Liin- Now, we have
Pr(Lmin 2a) c(a==(
Thus, by substituting a = ( )-)), we can get
Pr(Lmin 2 c
c (1 --1))
T-1
8 Pr( T - $1 cl (mmin) =
T
Defining Y= (T - c(Immn))), we obtain
Pr(Y =1 (1
T-11
T -
T-000 c
(8)
By substituting the definition of Y, we can rewrite Eq. 7 as follows:
T
1 (1
y T-1
Σ
o ((miiu)
T-1
T-1
T
Y
T+30 1 e-
(9)
Y
Combining Eqs.
8 and 9
can obtain the statement.
f indicates that single green word is sufficient to make the z-score exceed the threshold. However, Theorem D indicates that texts generated by the Soft-Watermark contain two or more green words with non-zero probability, even if we tune the hyperparameter for each text.
Assumption
15

---

Published in Transactions on Machine Learning Research (02/2025)
C
Additional Visual Explanation
199
Number of green words g
Number of green words
Number of green words
150
150
100
100
100
50
50
37
37
57
300
150
200
100
150
200
50
100
150
Number of words
Number of words t
Number of words
(a) Illustration of Alg.
with = 0.1.
(b) Illustration of Alg, with 7 0.1.
199
199
199
Number green words g
Number of green words
Number of green words
100
50
-3
23
23
100
150
200
100
150
200
300
Number of words
Number of words t
Number words
(c) Illustration of Alg.
1
with 7 0.05.
(d)
Illustration of Alg. with 7 0.05.
199
199
Number of green words
Number of green words
Number of green words
180
150
150
100
100
100
50
50
50
Number of words
Number of words t
Number of words
(e) Illustration of Alg. with 0.01.
(f) Illustration of Alg. with 7 0.01.
Figure 6: Visualization of the table T[t][g] for Tiaa 200, 7 75, 2, Z 4, and various 7. The areas colored in blue and light blue indicate the range in T[]][]] where need to calculate, and the areas colored in blue indicate the range that satisfies the constraint of Eq. ( The red line indicates the minimum number of green words required to satisfy the constraint. Note that in the middle and right figures, Gmx] does not denote the set of texts length t containing Gmax green words, but donotes the set of texts containing at least Gmax green words.
16

---

k Published in Transactions on Machine Learning Research (02/2025)
D Hyperparameter Setting
In our experiments, we set the hyperparameters as follows. All experiments were run with an A100 GPU.
Table 3: Hyperparameter settings for the NS- -S-Werermark.
Pre-trained model
NLLB-200 / LLaMA
k
T
max
100
y
Grid search over {0.1, 0.01, 0.001,
Table 4: Hyperparameter settings for the Sofl-Wadermark.
Pre-trained model
NLLB-200 / LLaMA
T maax
100
7
Grid search over {0.1, 0.01, 0.001, Grid search over (4, 8.8)
8
Table 5: Hyperparameter settings for the Adaptive Soft- Watermark.
Pre-trained model
NLLB-200/ / LLaMA
T maax
100
7
Grid search over 0.01, 0.001, 0.0001). (4, 6,8, 10, 12,
A
6
Binary search over A for each text.
17

---

Published in Transactions on Machine Learning Research (02/2025)
E
Additional Experimental Reuslts
E.1
Robustness to Post-editing Attack
In this section, we compare the NS-Watermark with the Adaptive Soft- Soft-Watermark regarding a tradc-off between lext quality and robustness. The Adaptive Soft-Walermark lunes the hyperparameter ó for each lext such that the z-score the minimum and exceeds the threshold Z. Thus, the Adaptive Soft- Watermark may be removed from the generated texts by replacing only one green word with a rod word. To fairly compare the modify the Adaplive Woft-Watermark
NS- AS-Watermark with the Adaptive Soft-Watermark, such that the z-score exceeds the threshold Z after replacing 50,3% words, where is the hyperparameter that controls the robustness against post-editing, The pseudo-code is presented in Alg, Then, compare the NS- Watermark with the Adaptive Soft- Watermark, demonstrating that the NS- Watermark can generate more natural lexts than the Adaptive Soft-Watermart when B is the same.
in Sec. [3.4
Table 6: Trade-off between text quality and the hyperparameter B. The best values are highlighted in bold.
Method
PPL 4
FNR / FPR 4
Adaptive Soft- Watermark
2.48
0.2% / 0.8%
0.0
NS-Watermark
1.92
0.0 % 0.3 %
Adaptive Soft- Wite-aatrmakk
3.43
0.2% / 0.8 %
0.05
NS- DS-Watermark
3.37
0.0 % / 0.8 %
Adaptive Soft- Watermark
4.28
0.1%
0.1 %
0.1
NS-Watermark
3.76
0.0 % 0.1 %
Adaptive Soft- Watermark
6.02
0.1%
0.1 %
0.2
NS- Watermarkk
5.42
0.0 % / 0.1 %
Experimental Setting. We used LLaMA-7B with C4 dataset. We set a to one for the NS- WS-Watermark and tuned the hyperparameter y using the validation dataset for the NS-Watermark and Adaptive Soft- Watermark. Then, we show the results when varying 3 (0,0.05, 0.1, 0.2}. See Sec D for more detailed hyperparameter settings.
Results. Table 6 lists the results. Comparing the PPL of the NS- WStermarakk and Adaptive Soft-Watermark with the same 8, the NS-Watermark consistently outperforms the Adaptive Soft- Seft-Watermark, Thus, the NS- Watermark achieves a better trade-off between text quality and robustness against post-editing than the Adaptive Soft- Watermark.
E.2 Visualization
Figures and S show the relationship between z-score and text length and that between the number of green words and text length, respectively.
18

---

Published in Transactions on Machine Learning Research (02/2025)
y-
1000
1000
P-0.1
y- 0.01
0.01
0.01
40
y- 0.001
0,0001
R00
0.001
820-
D.002
7-score
z-score
z-score
20
200
Number of words
Number of words
Number of words
(a) NS- Watermark
(b) Soft Watermark
(c) Adaptive Soft- Watermark
Figure 7: Relationships between z-score and the length of generated texts. We used the validation datasets of 16 En For each y, tuned the hyperparameter d of the Soft-Watermark by increasing
4, 4,6,8,... and selecting the smallest value such that the FNR becomes less than 5%.
y=
ym 0.1
Number of green words
Number of green words
y- 2.01
Number of green words
y 0.01
25
80-
0.001
80
0.001
y- 0.0003
35.
40-
20
20
100
20
40
60
80
100
40
60
80
100
Number words
Number words
Number words
(a) NS-Watermark
(b) Soft- SottWatermark
(c) Adaptive Soft- Satt-Watrraark
Figure 8: Relationships between the length of generated texts and the number of green words contained in generated texts. The experimental set sings are the same as in Fig.
E.3 Trade-off between Text Quality and Generation Time
Figure g shows the trade-off between text quality and generation time. In general, BLUE scores increase the generation time increases. However, discussed in Sec. 4.2 NS- US--Watrmark achieved the best performance when is small, and the generation time does not increase even if is large.
y= 0.1
30
0.001
y 0.0001
25
BLUB
15
10
5
10
15
20
25
Seconds
Figure 9: Relationships between text quality and time required to generate text with various e and
21,2,3 3, 4, 4,5). The experimental settings are the same as in Figs. 2
19

---

Published in Transactions on Machine Learning Research (02/2025)
F
Pseudo-codes
Algorithm 2: Linear time algorithm for the NS- 1S-Watermark.
Input:
Maximum number of words Tmax, vocabulary V, beam size k, the length of generated texts without watermarks T, hyperparameter y, Z, a.
Gmax max 1)+ / (Taxx 11]
I. min + 2 21-22 T-1
Let T be maax x Gmax table and S be an empty set.
[[] f- arg top-k p(ø1 xprompt).
for 1= 2.... Tmaz do
9min + min Gmax, max [L(t -
a]}
Jmax min mmax,
[tt + +
for g Ymin: Imar do
X + feasible set(t, update(X, t,
10
return arg T p Iprompt)
Algorithm 3: Adaptive Koft-Watermark.
Input: Maximum number of words Tmax, vocabulary V, beam size k, hyperparameter 7, Z, a, and set
A.
Let 81, 8/رl be the elements in A in ascending order. a + |A).
Amin, 8* 20, 8|/| do
while a S b 1
Generate a text using the Soft- Watermark with 8,. if the z-score of the generated text is greater than or equal to Z then c+ b
if the z-score less than 2min then
Store z-score in 2min. 8t db-
11
12
else
a b.
14 return the text generated by the Soft- Watermark with 8*.
20

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm 4: Adaptive Soft-Watrrmark with $. Input: Maximum number words Tmax, vocabulary V, beam size k, hyperparameter 7/ Z, a, B, and
set A.
Let 81, 8/رر be the elements in A in ascending order. a 1, |.
Amin, 8* 00, 6|/| while a S c do b+ =
Generate a text using the Soft-Waterman with &g-
Let t the length of generated text and 3ia the generated text.
+- V1(1-9(T-1)
if = > Z then
10
c b.
11
if 2 < 2mt then
12
t 2. Emin
13
8* 5b-
14
else
15
a
4-+
16 return the text generaled by the Soft- Watermark with 5*.
21

---

Published in Transactions on Machine Learning Research (02/2025)
F.1 Examples of Generated Texts
Table 7: Texts generated by the NS-Watermark on 16 Ge-=En.
Watermork
NS-Watermark
The the majority the staff
The and the majority: of staff from
Peilleuberg Schongau.
Peicocaberg to Schongau.
A Downing Street spoksrooma andd the text was likely from Cameron's is conetituency ey office.
A Downing Street spokswoman said himself that the text prohably came from Cameron's conetituency of- fine.
21.3
Accurnic rocueds the oarly yours could be pro- duced by the defendante.
Accunic indicators of the carly years could vided by the defendants.
For some products, such as velevisious and wooking wo- chinss, more than shird purchame are now made through online shops.
For some producto, such as televisious aad wooking tan- chines, more than third of purchnsns are now made mechanically via web shops.
17.9
Knowles snid that Prentias, who had dog named Lightning, had been accing Lamb for about three
Knowles suid himself that Prentian, who had dox nomed Lightning, had been sccing Lamb for about Uheee yours.
19.6
A 16-ycar-old giel Rhinchund-Pelale Pelatisato, who missing sinco Saturday, has the victim of
16-ycar-old girl from Rhincland Austiion Polatimate, has minsing since Saturday, has been, the
Phillip Cocu, the PSV coach, cald, "Ie's very bad injur"".
Phillip Cocaa, the PSV noach, said himsoln "It's a very bad injury"
21.8
Minieter Johanna Miki-Laitter sald Austina broadeaster Tueaday that would be bock Hungozy.
Mikl-Laitner Ausktian broudcaster ORF Tucsday eveuing apply repostiation Hungory.
Table 8: Texts generated by the Soft- Soft-Waterrark on IMT166 Ge-
w/o Watermark
Saft- Watermark
2-score
The esation and the majority of the stalf move from
The rodio factory and most of the ageuts moved from Peinenberg to Schongau.
11.4
Peiltemberg to Schongan.
Downing Street spokecwoman
likely
Downing Street spokeswonan Itkely
Cameron's conetituency office.
comstituency
Anturate recorde of the early years could not he pro- duced by the defencante.
Accurate logs cover previous years but come accusers cannoe clatm total facarevt-olre have returned.
35.1
Far products, third purchasns through online shops.
televistons and washing
producte, machines,
wasking
Knowles snid that Prentins, who had a doe named Lighttaing, bad been secing Loub for about three years.
Knowlea anid thantiantian, whoisposedyy adishen list- mallyedishea thathe leppoor weat dating lomb.
37.3
A 16-year-old from Rhinchand-Palatiaste who missing Suturday, has beea the violent crime.
16-ycur-old girl Saturday, However.
Rhineland- Chiaelaad-Pulltinnte Pulatinate missing
6.0
Phillip Cocu, the PSV coaoh, cald, "It's a very bad injur!!.
Phillip Cocu, the PSV coach, did pay,
5.5
Austrian Interlor Minister Johanna Miki-Leisnen told Auariaa broadcaster ORF on Tuesday evening that no one would be scut back to Hungary.
Austrian Commiseioner Johannes Lelner highlighted that perkeprotection mensures requieed prior investi- sation upen abduction occuredd. However.
31.8
22

---

Published in Transactions on Machine Learning Research (02/2025)
Table 9: Texts generated by the Adaptive Soft- Watermark on 16
w/o Waterwark
Adaptive Wofi-Woiernnrrk
avicure
The scation and the majority of the staff move from Peileaberg to Schongau.
The major part of the agents and office staff move from
21.1
Peileaberg to Schongon.
A Downing Street Comeron's constituency office.
asid the Iskely
Downing spokoreoman said
likely
developed Cameron's constitucncy office.
Accurate rocorda of the early years could not be pro- duced by the defeninats.
Accurate indicatora of the early years them? Lisiay impossible viorcia but historicula reports testing in- tegration be toals shis study eueminine stmple In- termitenen greet whether both thhing acss lest casse rcaliaution lister slow repaymeut barra -doclarishh program said demadet sularin something laana makes
250.5
serienx comment ob thoough
For some products, such ne televisions and washing ma- chiner, more than a third of purchases are now made through caline shops.
For some products, such as televisions and washing ma- chines, more than a third of purrhhase are now made through online shops.
5.8
had dog Lightting, been sccing Loub for about years.
Knowles
Pranctes,
Prentiee, who had, Lightaing, ub, been socing Leab for about theee
Knowles
A 16-year-old giel from Catheeload-Paaatinnnn who has been miesing since Saturday, has been the victim of violent crime.
16-year-old giel from Magdeburg, Laadsbazeeaa re- gional compre- ondensings previouely/ oucically miss- Inghtt hereso soeme thbing acte violence At url- ing Uneleughi ganglandh montblic for Murshud no Morc weekoud 635 buig treat Begnansa
200.5
balg teeut Bug- Bag-
Bagnsnas
Phillip Cocu, the PSV coach, cald, "It's very had injury"!
Phillip Cocu, the PSV coach, caid, "It's very bad shot"
6.9
Minieter Johanna Mikl-Laitserr sald
Mikl-Lattter Austiian broudeaster ORF Tuciday eveuing
Ausrina broadeaster Tueaday eveuing that would be bock Hungozy.
bock Haugory
Table 10: Texts generated by the NS-Watermark on 1MT'14 Fr-+En.
Watermark
NS-Watermark
The court, blocks ruling on the NYPD's search and policy.
The court blocks rullng on the NYPD's acurch initia-
Germany and a few of its satellite economies could keep the suro, but Prance and southern Europe would get their own currency back.
Germany and fow its satellite economies could keep the auro, but France and southern Europe would apply their own currenciea.
19.2
The sciense how child will develop sescual ideutity
The
spanning how child will develop uet very precise.
vary precis.
This loss of genatic heritage would be much more prob- lematio.
This loes of genetie Heritage would be much more prob- lematic.
27.7
We would welcome CASA the olectronio devices because really belleve that would we have (the in-flight entertainmnent system wing Wi- Fi techuology) on sircealt, spolesperson suid.
that would allow
thas would apply We would welcome CASA really beliove this wonld electronic devices
the enstomer experience that
the customer experience that we have (the in-flight entertainmeat syssem wsing Wi- Fi technology) on our nircrall, apekropesoon suid.
Vettel wearing spectal balmet in Abu Dhabi
Vettel wearing a spactallars balmet Abn Dhabi
30.1
Little by little, in small appearances by day or by night, little aby, little crazed, she scon came back to mind, evolving the took her place in the landecage of my thonght that thought Isself in mourning.
Little by little, smail appearances by day by night, litsle shv, little crwedd, she scon mind, evanescent as she took her place in the landecape of my thonght that thought itself to mourning.
13.3
back to my
given
hehavlor
given probshly take long derstand why their tails
probsbly won't long sometimes
why
and somettimes
23

---

Published in Transactions on Machine Learning Research (02/2025)
Table 11: Texts generated by the Soft-Watermark on WMT14 Fr.
w/o Watermark
Saft- Watermark
The blocks ruling the NYPD's search and
The couct... blocka recausideraa and inspection initindive... towards finalizing two plans for de- giving.
policy.
Germany and few of its satellite economies could keep the euro, but Prance and southern Europe would get their own currency back.
Germany and a few of satellite economies could kald onto the euro, but Itayand Algeris would call peaplefathering foreign cconomicc balsace debt ex- change
23.5
The science of how a child will develop secual ideutity in not vary precise.
The seicace of how socual ideutily develoys in child le not fimmly cursens today.
8.8
This loss genetic heritage would be much more prob- lesmatee.
This interesting.
genetic origin would be rather even more
We would welcome CASA review thas would allow the use of electronie devices becsuse we really believe that would improve the customer experience now that we have (Uhe ju-flghht catertainancal system wing Wi- technology) on our streraft, a spolespatsonn said.
We would welcome further review by CASA including the wagge of electronic devices us we believe it would really improve the custemer experience now that we have (scau, built-in entertainmenl system now using Wi-Fi technology) on our atreraft,
17.0
Vettel woneing special belact in Abu Dlabi
Vettel getting its
workout belmet cacried In Abu Dlubi yeaterday "Clored publicly/ /Oat
33.7
Little by little, in small appearancee by day or by night, my
Litsle by litsle, wallings midday and night ashes only ever look at au illunive vision, did 'the heroms arrive uniil bouts. However,
38.3
a litsle aloy a little crused, she scon came mind, croleing as she look, her place in the landucape of my thought that thought itel in mouraing.
However, given the case with which their behavior can be recorded, it probably won't take long before we un- derstand why their tails sometimes move to one side and sometimes to the other.
However, knowing it is to record behaviour should only ever provide theory of rossoning within large numbers of tumbocate".
29.3
Table 12: Texts generated by the Adaptive Solt-Waternark on WM Fr-SEn.
w/o Watermark
Adaptive Soft- Watermark
The coure blocks ruting the NYPD's search and policy.
The American precident closed the metro government below 20-zee syee. However, Jonathan Ketów fistebed talling teacherz truch finaly day passes. However, Jonathan Kotōw liaished tolling teachers trath finally day passes.
168.5
White Deedat
Germany few satellite economles keep euro, their currency back.
Germany and earo, wally gained
satellite economles wonld grad- right back into their
keep
Europe get
The sciencs of how a child will develop a secual idantity te not very precise.
The zcience of how a sexuaa idantity develops in a child le not very precsse.
7.3
lose genetic heritage would be much prob-
genetic Heritage would much lematic.
This
lemnatie.
We would welcome CASA review that would allow the use of electronic devices becsuse we really believe that would ld improvs the enstomer exparience now that we have (the in-flight entertainment syszem using Wi- technology) on our streraft, a spolesparson aaid.
We would welcome a CASA related novel reguiation leaving electronics allodial because we really believe an moderniration procedure would apply presently/ /now that we have web network turnelit here-aca -ss compo- nent consieting of application: [eruncated...
227.8
Vettel wearing special balmet Abu Dhabi
Vettel leading collegiate seat till 20:00 in Emitrttex gala wider than to modern Germany.
89.6
Litsle by little, in small appearancu day or by night, a little aky, a little craned, she scon came back my evolving thonght place monrning.
Litsle by little. small spota, day and night, little my landerape
8.3
shy, a little out focas, sle soon came
landecape
evolving thought
place mourning.
my thonght
my thinking
However, given the mase with which thetr behavior can be recorded, it probably won't take long before we un- derstand why their taile sometimeu move to one side and somatimes to the other.
Howwver, given the caze with which their behavior can be recordad, it probably won't take long before we un- derstand why their talla either move to one side or the other.
5.0
24

---

Published in Transactions on Machine Learning Research (02/2025)
Table 13: Texts generated by beam search on C4. We show the z-score for y 0.0001.
Prompt
w/o Watermark
[--]of polyester, but there ping, munufactaring, etc) shat I don't think it's really coatinmable which is greener /a0f course, not every child has pazens who can, or has time to, cus pat- tern, buy fabric, cut fabrie, fit, and sew a costume, definitely understand the appeal of just being able to buy one at Target and being g done. Storee also have
many vartabler (ship-
umer that, kids Lomemnde costumes are more of one-time use prod- jal do shink that it's shame that homemade cas- Lumce are being pusked out in favor of stores boughtt enes, though. I think that it's important to tench chil- dres about the value of craftsmanship and the joy of creating something with their own hande. think shat It's also important to teach childrenn shout
for your two, wheneae
-0.1
mare- post
...Jouher suicly cquipment, selling a rocord for "woot buildings cltmbed unaseteted" according to Guinners World Records.) (nn his webstte, Robert says, "Climb- ing my paseion, my philorophy life. Although out- up vertign, sithough
pusk beyoud them. You cun du it loo! Kobber,, G1, has basn climbing sinon 1982 and has sealed zome of the world'' la tallest buildings, including the Eiffel Tower. the Shanghal Towwer environman protection to promote importance spuces. (aWhat incredible
Borj Khalifa, eltsbinng to
dieshled "\alle limitss,
"We to
He truly
bui
[-.] strategic
An" There
include further
comeons March, has incrased abovs the level expected, which means. that will longer be able to mect our target of re- ducing leverage for the full yoar.A" "W" lave therefore coucluded that we must take immodiiii action to celerate the reduction in avarage net borrowing and are announcing compreheasiv programme of uras to addrees that, almed at generasing significant cashflow In
borrowing
markets and agraphiess, well revlow of the budiness and tal structure to optimise value for abarcholders We" also vaking stepo to addrew the deterioration. in cash llows on select number of cousts uction con- tracts. including the recognition of a contract provision of A&545m and the establisheent of
Ag125m
to
...Jmede up his mind This clectiou somon by asking himeelf whether was better off than he was in 2008. decided he was not. /nJeff Bodack, 54, a registered Democrat who has been voting for Repablicaas since wants Thomey Wash- Reaganeera, "change," becanee fel: "urgent." "HHarkiiy to Obama)
to, "You We Cua,"" Bodack ount be wants to scud a mes- sage Washington that "We Can Better "X""F; not happy with the way things are going." he said. "I) not happy with way things have been going long time
-0.1
Cazey (plommmeen Demorratic Tondday night, Mark Crite
Senator
campaign
publican challenger the
further [--jat decisions should be driven short-term ronelderations and should be made the FRR Instead, they proposed such decisions made by independent policy board the mnnittry of commurrc and aim roduce onti-ogpori bios, cost of produc- tson. tariffe on imported raw matorials and intermedt- ate goods, while eliminating the dustiaction betweun in- dustrial and commercin) importers and reform the SRO reginee (aThe
pegtin.
working The policy will Improving compesttvennss and reducing the cost of doing busi- uess. The policy will alw aim reduce the reliance on troditional matkets and explore new markets for Pakistani exports. The pollcy will also focus on im- proving the businesu environment. reducing bureau- cratie rod tape, and increasing transparency and pre- dietahility in
minstrr
polloy to booss focus promoting valneadddd
Table 14: Texts generated by the NS- US--aaermarr on C4.
Prompt
No-
a-score
[-.]af polyester, but there ping, manufacturing, etc) that I don't think It's realyy costirmable which is greener NaOr course, not every child has a parens who can, or has time to, cus pat- tern, buy fabric, cut fabric, fit, and sew a costume. definitely understand the appeal of just being able to buy one at Target and being done. Storee also have
many vartables (ship-
umar that loss thair appea! after Hallowenn, it's not like homemade contamee are the only opsion for quality, yal'm not sure what the answer in, bus I think it's worth conddering the environmontal impact of our choicen, even if it's just for our day a year. (akuna
12.0
bared nost
[o.lother safety equipment, setting a record for "most buildings climbed unnavisted" sccording to Guinneus World Recorda,) laOn his website, Robert says, "Climb- ing my passion, my philosephy life. Although out. vertigo, althengh
puch beyond our Fimits "ooRobert has climbee come the world''s most famous buildings, including the fel Tower, Burj Khalifa in Dubai, and the Shanghai Tower Chian AuHe cuthralled audieuses with his death-defying their
10.0
dieshled "VaHe "We ouselives limits, to alm higher,
ineptred many pureue
passione. (aooarre'' suffered been wishout danger. Injuries,
but are strong
the Annonnowment
We will undertake comprehenttve review of the buxinees and the capital strncture, with all options optimiee value for the benefit of sharcholder under comidder-- tion Wn"We are assuring our stakeholdete that we ate taking all necossary stape to address the ourrent chal- lenges and to pouition the Group for long-term suc- essa essa." "LaCarillion iss interim resulia for the six moutha to 30 Jane
that
March, has incraseed above the level expected, which means that will no louger be able to mcci our target of ro- ducing leverage for the fall year year-n" We" have therefore concluded that we must take Immediast action to ac- celerate the reduction in average net borrowing and are announcing compreinensive programme of meas uzes to addrees that, almed at generacing significant exch in
horrowing
[..]made up his mind this eleation ccon0m by aeking himself whether he was better off than he was in 2008. decided he was laleff Bodack, 54, registered Democrat who has been voling for Republicuss since Rengan-era, "change." Thomey Wash- fel: "urgont." "yoHorking to Obama) 's 2008 campaign
ra, Bodack said, "I want to hope and change, and I think Toomey can bring that "VVVoters at the polling placea exprossed a range of opinion on the candidates and lasnca, many shared aense disillusiommeat compaigne. In'Il
10.0
it''s negative campaigns negative." snid Petner. "I they would focus the and
trude polley decssione should not he driven short-term fis. cal conetderatione and should not be made the FBR. Instend, they propased much decisions indopendent policy board or the ministry of commercce and alm to roduce aati-oxport bine, cost. of produc- tion. tarifla on imported raw materiala and intermedi- ate gooda, while cimninuting the dissiacciion between in- dustrial and commerciia importers and reform the SRO regime. hhe
They further
addrem low exports, including the artahlisment of the Trade Pollcy 2015-20. which sims promote ducing tarifis and the creation of the Trado and Investmont Pollcy Framework, which alms to promote trade and Inveet- ment by zeducing the cost of doing businesa in Pal- istan. government has also taken steps to addrens the houe ultcusteteed caporters, including the cstab- Iichment
by materiale and intermediace gonds.
made by
25

---

able Published in Transactions on Machine Learning Research (02/2025)
Table 15: Texts generated by the Soft-Watermart on C4.
Prompt
Saft- Watermark
X-score
[-]off polyester, but there are so many vartabler (ship- ping, mannfacturing, etc) that I don't think it's realy coafiruable which la groencr)aoO couse, not every child pazeus
umar and character onacier with little to no sewing re- quired. So even with this recaosion/ /comumerries trend en largeted costumes, pareats could choose the green option. They sell costumes sewing reguired. So could choose the
20.1
can, or time to, cus pat- buy fabric, fabrle, and a able definitely underatand appeal Stores Target
character onesies
targeted option. They sell with little
and required. So
trend- beend-bared cost
character
with "ucllar""AAllin Robert, truly the human super kero! (Photo by AFP via BBC)
Eoolohher safety equipment, setting record for "most buildigs climbed unnanitedd according to Guinness World Records.)aOn lis website, Robert says, "Climb- ing passion, mg philesephy of life. Although ouf- for from vertign, alt althongh my accidante left ma disahled up to 65%, I have become the best solo climber." (eeerr.(n "\all encourages oouggge others by saying, "We set ourselves limito, but we are all strong enough to aim higher, to
0.8
I.. the stratggl prioritics we ses out in our 2010 re- enits annonnoemant
the years aleaad to 2018 and beyond yn heae heeee monsures will enable us to make meaningful progree lower our leverage to balow 2x pearing (EBITDA furter than had previouxly guided, by the and 2018 while main- taining our returning core operatious. They form major aspect enable repositionins the busiacs
15.1
March, average net horrowiing has incraseed abous the level we expected, which maans that we will no longer be able mest our target of ducing leverage for the full yoar We have therefore coseluded that the annsuating compreheasive addrems lant,
immediate action borrowing measuzes gencrosing significant caokflow
ongoing thorough review additional
sharehold- towards
mind this clection himaelf whether he was better off than was 2008. He decided he not- (nJeff Bodack, 54, registered Democaat who has been vosing for Repablicuus since the Ronald Reagan-rra, said he wants Thomsy in Wash- ington becames he wants "change," and said his vote fels "urgent." "AHHarinn to Obama) is 2008 campaign mont
I..lmade
aoking
fundament change American polities for posttive negative reasons bas some bearing Taee- day night elections outcome in this and next mid terms for presidency 2016. So doca Obams's policies popu- larity which was major factor in last mid terms for prectdency 2018. So dons Ohama's a polictes popularity which was a major factor in last mid terms for prest- doney 2018, So doe Obama's 's policies
20.8
[-.jar the trade pogime: An bay further strensed trade polley dectstone should not he driven by shortsterm condiderations and should not be made by the FBR. made by an ministay of commerce
soverament will do well to locur lew on juss eutting lan- ports via high import dustis which, by the way, have little impact on containing the widening CAD They suggest forgoing exports growth through an overly optimiatic forecust and policy framework centered on Gwadar port
20.3
Instead, they propased much dectsions
independent policy board and alm reduce anti-oxport bias, cost. produc- while
through in- hubris. They through forecaat policy framework Gwaddr port that
just
intermedi- dissiaction between dustrial commeriial importers reform SRO regime. Ja
Bows foolish
forgoing caporta
Table 16: Texts generated by the Adaptive Soft- Watermark on C4.
Prompi
Adaptive Soft- Warermark
a-acore
[--]of polyester, but there are so many wartablee (ship- ping, mannfactaring, etc) shat I don't think it's really confirmable which is aroencr-aa0f couse, not every child pazeus who can, or time to, cus pat- definitely understand appeal of
uier that are more realistie than the homemade kind, which, you're 're not a crstt person, may be more ap- pealing tal think the new Targel commercial well- made and funn, glad my and
6.1
also makes me little sad. I'm who
look my
bared cost
l..ler cquipment, scllink
raise to We immesdotely morkets
buildings climbed annosisted' according Guiuncas World Records.)nOn (nOn his webstte, Robert
"Climb ing passion, my ahilosephy of life. Although suf- for from vertign, al although my accidents left me disabled up to 65% I have hecome the beet solo climber."" "X "(ulle encourages others by saying. "We set ourselves limite, but we are all strong enough to sim higher, to
up to further Adc22m the next 12 montha to en- sure we have aufficient liquidity to meet our financial obilgations and to ensure we are well funded to take advancage of the new opporamitiiss that will arlie as we repocttion the bustneee. (n" are also annosncing plan to eucty out compreheaasie review of the busi- ness
the]the strategic priorities we set out in our 2016 re- euits onnonnommons has Incroseed shoes the level we expected, which maans. we will longer able mici our turget of ro- therefore
ra, Badack said. "I want to bape and change, and I think Toomay can bring change "(plde Peterson, 28, regletered indepindett, said her vate this year was driven by her desire casure thas hez children have better future. She voted for Democral Bob Casey U.S. Senate and Republican Chaclic Dent year
11.1
March, average net borrowinng
ducing leveruge for the full your.uu" bar We coseluded that we must the annouacing comprehensive programme measuzea aridrees that, almed generating significant floh
immediaie action ac- borrowing
driven her Peterson
mind this cloctina himeelf whether he was better off than He decided he not (nJeff Bodack, 54, registered Democrat who had been vosing for Repablicans since the Ronald Reaganerra, said he wants Thomey in Wash- tigton hecamen he wante "change," and sxid his vate felt "urgent." HHHarking to Obuma)) yss 2008 compaign moot
asking 200s.
push beyond outaelves. Rtohert, however. Some have crstictzed him for invad- private property and patting himaulf and others Nnnr much is known about Robert, other than he balls from Prance and has been doing this for over two decades. He has added seven, new buildings to his climbing list this your alone (uNot much is known u about Robert, i, other than le hails from France and has been doing this for over two decades.
[..]of the trade regliee They further streased trade pollcy dectstone should not he driven by short-term cul considerations and should not be made she FBR. Insicud, they propased such decisions made by an independent policy board the ministry of commerce and
government has Incroduced a serice of meaeures to sgar invetteent In the country, Including the new lnvset- ment policy that sims to atleact 310 billicn in Sereign investtmnat over next year. yoau,/aTTa TaThe government introduced serice meusures spur inveatment country, including the five The government Intro- duced series of meauure to spur invastment in the
15.2
produc- goodle while ellminating the distiiction between dustrial and commercisl importers and reform the SRO regime- AhThe
ants-export
billion foreign policy
26


Reviews:
[{"review_id": "5yUVbOLyMT", "reviewer": "Reviewer_Q348", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. The authors formulate the optimization of the watermark as an optimization problem and introduce an efficient dynamic programming method to address it.\n2. The necessary and sufficient conditions for watermarking are novel and contribute a solid theoretical foundation.\n3. The method achieves significant improvements in perplexity compared to prior watermarking techniques.\n## Weaknesses and Questions\n1. **Dataset and Settings**. The authors evaluate their method on machine translation and news datasets, which are relatively small-scale despite the method's stated focus on long text generation. Why were these specific datasets chosen? Both settings appear to rely on beam search as the primary generation method. However, in many real-world applications, LLMs no longer use beam search as the default. For instance, in story generation—a task characterized by relatively long outputs—top-p sampling and high-temperature decoding are commonly employed. How would the proposed method perform under such generation paradigm? In these scenarios, watermarking may incur higher computational costs, and the estimation of generation length could be less accurate, potentially undermining the efficiency and applicability of the linear-time algorithm\n2. **Figure 1b**. Figure 1b appears to demonstrate the best-case scenario for achieving linear time complexity. However, $\\gamma$ is set to 0.2, while the largest value used in the experiments is 0.1.\nIf I interpret Figure 4 correctly, when generation time does not increase with higher alpha values, it indicates that $G_{max}$ has been reached. It also indicates that the linear reduction is no longer needed. For larger $\\gamma$, $G_{max}$ is larger and the linear reduction is more effective. However, this figure depicts a scenario that appears more favorable to the linear reduction than the settings actually used in the experiments. This discrepancy raises questions about the generalizability of the results presented in Figure 1b to other settings.\n3. **More empirical attack**. The paper builds on Kirchenbauer et al. (2023a), who evaluated a wide range of empirical attacks. Why do the authors consider only random post-editing attacks in their experiments? How would more sophisticated attacks, such as the T5-based ones from Kirchenbauer et al., impact the performance of the NS Watermark compared to Hard and Soft Watermarks?\n4. **Figure Clarity**. \n- Figures 3 and 4 should use consistent colors for lines with the same hyperparameters to improve readability.\n- Figure 5 is difficult to interpret due to the use of multiple shapes and colors. Could the authors provide a full trade-off curve between $\\beta$ ($\\delta$), perplexity, and FNR? This would make it easier to determine whether NS consistently achieves a similar FNR with lower perplexity.\n5. **Parameter Selection**. Empirically, how should $\\gamma$ be set? Is a grid search the only viable method, or are there alternative heuristics?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the Necessary and Sufficient Watermark method as an advancement over prior Hard- and Soft-Watermark techniques. The proposed framework demonstrates that the effectiveness of the statistical test improves with longer text generation, allowing the watermark to be relaxed in these cases to enhance generation quality. By establishing the necessary and sufficient conditions for watermarking through hypothesis testing, the authors propose an efficient empirical method for generating watermarked text. The paper also evaluates the robustness of the method against post-edit attacks, specifically the attack with random word substitutions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Demonstrate the method’s performance beyond beam search.\n2. Include evaluations against a broader range of attacks, such as T5-based methods, to align with prior work and strengthen the robustness claims.\n3. Improve the clarity and consistency of figures", "broader_impact_concerns": "Watermarking is a safety-critical area, and including a Broader Impact statement would be highly beneficial. Could this method be misused to falsely attribute content to AI systems, thereby obscuring accountability? Could the watermarking green vocabulary be inferred with queries? Additionally, watermarking techniques might interact differently with content across diverse linguistic and cultural contexts. Are there any fairness concerns related to potential biases in watermark application or detection for such content?", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4EADdypsIT", "reviewer": "Reviewer_39rF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nLLM text detection/watermarking is an active field of research within the ML community and is of interest both scientifically and in practice. The paper clearly meets the \"Audience\" criterion.\n\nThe authors identify a shortcoming of an existing watermarking method and propose a reasonable fix to it. The intuition for why their proposed fix can lead to improved text generation quality is also clearly explained and strongly supported by their experiments. There is a concern of the additional computational cost needed to implement their method, but the authors also address this by proposing a further modification of their base method to avoid intractable computational cost, especially when LM inference costs are high (as is frequently the case with modern large models).\n\nThe paper is also clearly written and easy to follow.\n\n# Weaknesses\n\nSome of the modeling assumptions for the hypothesis testing framework are not explicitly stated. For instance, below equation (1), it is stated that \"If humans write the text, the green words appear with probability $\\gamma$.\" Later below the statement of the hypothesis test, it is stated that \"The number of green words follows a binomial distribution in texts written by humans.\" The first statement corresponds to the assumption that all words in the vocabulary are equally likely to be used by humans, while the second would require that words in the text are selected independently. Both of these assumptions are likely not literally true. As the later experiments show, the simplifications made by these assumptions seem to not hinder performance, as this hypothesis testing method can simultaneously obtain low FPR and FNR. Nevertheless, the assumptions should be stated explicitly.\n\nThe baseline for the post-editing attack could be improved. At the very least, rather than selecting a random subset of words and replacing them with random selections of new words, a random subset of the *red* words should be selected and replaced with a random subset of *green* words. An even more realistic attack would be to replace red words with green words that are (approximate) synonyms of these words.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a method for watermarking AI-generated text such that it is easily detectable with minimal degradation in terms of text quality. Their method, NS-Watermark, operates by modifying the beam search procedure to maximize the generated output while ensuring that the resulting test statistic (a z-score) for the generated text is guaranteed to stay above a rejection threshold, meaning that this hypothesis testing approach will correctly detect that the text is AI-generated. They compare against a more naive watermarking method proposed by Kirchenbauer et al. and obtain superior results in terms of the quality of generated text (measured by BLEU score in a translation task and perplexity in a generation task) vs. the previous approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please clarify the assumptions for the hypothesis testing detection framework.\n\n2. Please add improved editing attack baselines, or explain why the current baseline is reasonable.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GA6sIyUTgx", "reviewer": "Reviewer_BoLu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed framework (NS-Watermark) presents a novel method to optimize watermarking with minimal quality degradation, which is an improvement over existing techniques.\n\n2. The effectiveness of the proposal is evaluated through extensive experiments.\n\n3. The paper is well-written and well-structured.\n\n4. The code is included in the supplementary material - enhancing the reproducability.\n\nWeaknesses:\n\nSome parts of the paper are not clear and need to be addressed by either adding some clarification sentences or running additional experimental results. Please see the Requested Changes section for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes  a novel framework called the Necessary and Sufficient Watermark (NS-Watermark), which is a watermarking technique for text generated by large language models (LLMs). The aim of the method is to minimize the text quality degradation while maintaining high detection accuracy. The contributions are the following:\n\n1. The NS-Watermark is formulated as a constrained optimization problem and derives the minimal constraints necessary for distinguishing LLM-generated texts.\n\n2. Experimental evaluation demonstrates that NS-Watermark outperforms SOTA by up to 30 BLEU scores for machine translation tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested Changes:\n\n1. In the comparison results, there is comparison of NS-Watermark with Soft-Watermark and Adaptive Soft-Watermark but there is no comparison with Hard-Watermark. Could you please either explain why such comparison is omitted or add the corresponding results in Tables 1 and 2.\n\n2. The Adaptive Soft-Watermark seems to be an improvement of Soft-Watermark, proposed by this paper and demonstrates competitive results on FNR (Table 1). Could you please provide a reason or intuition why FPR results for Adaptive Soft-Watermark are higher than Soft-Watermark?\n\n3. Could you please plot the trade-off curve of the time required to generate a text and the text quality? This will help the reader to understand to complexity of the method as well as how feasible the proposal is in practice.\n\n4. Does figure 5 include comparison with works [1] and [2], which are mentioned in the related work section? Could you please include these comparisons?\n\n5. It would be helpful to have a table that compares the time complexity, PPL, FNR of the proposal and the SOTA methods (such as [1],[2] as well as Post-hoc Detection Methods). \n\n[1] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks\nfor language models\n\n[2] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models.\n\n\nMinor changes:\n\n1. In the introduction, the paper is motivated by saying that it is important to identify whether a text is generated by LLMs or humans and the detection of fake news is mentioned as an example. Could you please provide some more examples and add a few more sentences explaining why these examples are important.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a very interesting paper on a highly relevant topic. I think concerns of practicality or speed are worth noting but do not at all detract from the contribution, and the research fields should explore this trade-off. The remaining main concern is about the comparisons: the authors choose not to include hard watermarking in the results (citing that the method is not practical), and also do not include methods designed for undetectable watermarking. I find the reasoning of the authors convincing, certainly about hard watermarking, and to a large extent also about undetectable ones, but I would like a small revision performing one of the following
 - either (a) clarifying this choice of comparisons in the paper (using the argument from the discussion)
 - or (b) including some baselines for completeness, so that the paper would provide more context to readers: the implication is that undetectable-focused watermarks are expected to degrade more in generation quality than the present method, but it wouldn't hurt to confirm that.
Decision: Accept (poster)