A Watermark for Order-Agnostic Language Models
Authors: Ruibo Chen
Yihan Wu
Yanshuo Chen
Chenxi Liu
Junfeng Guo
Heng Huang
Venue: ICLR 2025 Poster (2025)
Keywords: language model watermarking; generative model;
Primary area: generative models

Abstract: Statistical watermarking techniques are well-established for sequentially decoded language models (LMs). However, these techniques cannot be directly applied to order-agnostic LMs, as the tokens in order-agnostic LMs are not generated sequentially. In this work, we introduce PATTERN-MARK, a pattern-based watermarking framework specifically designed for order-agnostic LMs. We develop a
Markov-chain-based watermark generator that produces watermark key sequences with high-frequency key patterns. Correspondingly, we propose a statistical pattern-based detection algorithm that recovers the key sequence during detection and conducts statistical tests based on the count of high-frequency patterns. Our extensive evaluations on order-agnostic LMs, such as ProteinMPNN and CMLM, demonstrate PATTERN-MARK’s enhanced detection efficiency, generation quality, and robustness, positioning it as a superior watermarking technique for order-agnostic LMs.

Published as a conference paper at ICLR 2025
A WATERMARK FOR ORDER-AGNOSTIC LANGUAGE MODELS
Ruibo Chen, Yihan Wu', Yanshuo Chen, Chenxi Liu, Junfeng Guo, Heng Huang! Department of Computer Science University of Maryland, College Park, MD, USA (rbchen, ywu42, eys, cx cxliu539, F2023, heng (emdddddde edu
ABSTRACT
Statistical watermarking techniques are well-established for sequentially decoded language models (L.Ms). However, these techniques cannot be directly applied to order-agnostic LMs, as the tokens in order-agnostic LMs not generated sequentially. In this work, we introduce PATTERN-MANE MARK, a pattern-based water- marking framework specifically designed for order-agnostic LMs. We develop a Markov-chaie ww----hbaseedddd watermark generator that produces watermark key sequences with high-frequency key patterns. Correspondingly, we propose statistical pattern- based detection algorithm that recovers the key sequence during detection and conducts statistical tests based the count of high-frequency patterns. Our ex- tensive evaluations on order-agnostic LMs, such as ProteinMPNN and CMLM, demonstrate PATTERN-MARE 's enhanced detection efficiency, generation quality, and robustness, positioning it as superior watermarking technique for order- agnostic LMs.
INTRODUCTION
With the rapid advancement in language models' capabilities and their increasing adoption, re- searchers and regulators have expressed growing concerns regarding their potential misuse in generat- ing harmful content. Distinguishing between numan-generated" and Al-generated text has become
significant area of research. Statistical watermarking (Aaronson) 2022 Kirchenbauer et al.) 2023a
Christ al. 2023 Zhao al. 2023 Liu al., 2023a] Zhang 20,4 Huo et al. [2024] Chen et al. 2024b) offers a promising solution for identifying text produced by sequential LLMs (Brown
2020 Touvron et al. 2023). This technique embeds covert statistical signal into the generated content using a pseudo-random generator, which can later be detected through statistical hypothesis
test.
Order-agnostic LMs, where content is not generated in left-to-right sequence (see Figure
have
promising applications fields such as protein generation (Dauparas et al. 2022 Alamdari et al..
2023), machine translation (Ghazvininejad et al. 2019 Kasai et al.) 2020 Huang al.
2022), speech
generation (Chen et al. 2020 Peng et al. 2020). and time series forecasting (Chen et al. 2021 Tang &
Matteson| 2021). ). Although watermarking techniques have proven successful in sequentially decoded
LMs, most of these methods cannot be directly applied to order-agnostic LMs. This limitation arises because watermark generation and detection typically rely on previously generated context (n-gram), which is not consistently available in order-agnostic LMs.
In our work, we propose PATTERN-MARK, pattern-based watermarking framework for order- agnostic language models (LMs). Our approach consists of a Markov-chain-basee watermark generator and a rigorous statistical, pattern-based detection algorithm. The intuition of using Markov chain is in order to enable recovery during detection, the pseudo-rand randommessss of the watermark must be derived from the context, and the Markov chain is well-suited for establishing the dependencies within the context. Specifically, in the watermark generator, we utilize Markov chain to generate a key sequence of length n, which is equal the output content length. Each generated key is
* Equual Contributions
1 This work was partially supported by NSF IIS 2347592, 2348169, DBI 2405416, CCF 2348306, CNS
2347617.

---

Published as a conference paper at ICLR 2025
Malt
generation
generation stops
Mani
Sequentially decoding
Order-Agnostic decoding
Figure I: Sequentially decoding vs. Order-agnostic decoding. Sequentially decoded text, follows fixed, left-to-right construction while order-agnostic decoding generates text by filling in words without adherence to traditional reading order. Most of current watermarking methods typically rely on previously generated context (n-gram), which not consistently available in order-agnostic LMs.
then used as a random seed modify the output distribution at the corresponding time step. This key sequence generation ensures a higher occurrence of certain key patterns compared to non-wald non-watermarked models. During detection, the key sequence can be recovered from the given content, allowing the use of a hypothesis test on the occurrence of specific key patterns to guarantee a controlled theoretical false positive rate.
Our contributions can be summarized
We propose PATTERN-MAN MARK, a pattern- -based watermarking framework specifically designed for order-agnostic LMs. Our approach introduces novel Markov-chain based key sequence generation method and a rigorous statistical pattern-based watermark detection technique. To the best of knowledge, this is the first work explore watermarking for order-agnostic LMs, which are popular architectures in diverse real-world applications including machine translation, protein synthesis, speech generation, and time series forecasting.
Through comprehensive experiments on two popular order-agnostic LMs. Protein- MPNN (Dauparas et al. 2022) and CMLM (Ghazvininejad et al., 2019), we demonstrate the superiority of PATTERN-MAKE in terms of detection efficiency, generation quality, and robustness compared to baseline methods.
2 RELATED WORK
Statistical watermarks. Aaronson (2022) proposed the first statistical watermarking algorithm via Gumbel sampling. Kirchenbauer al. (2023a) extended the statistical watermarking framework by splitting the model's tokens into red and green lists and promoting the use of green tokens. Huo et al. (2024) further improved the detectability of the red-green list watermark by employing learnable networks to optimize the separation of the red-green lists and the increment of green list logits. Zhao et al. (2023) introduced the unigram watermark, which enhances the robustness of statistical watermarking by leveraging one-gram hashing to generate watermark keys. Liu al. (2023b) also contributed to the robustness of statistical watermarking by incorporating the semantics of the generated content as watermark keys. Liu et al. (2023)) proposed an unforgeable watermarking scheme that utilizes neural networks to modify token distributions. [Christ et al. (2023); Kuditipudi et al. 2023); Hu et al. (2023a); Wu et al. (2023b) focused distortion-free watermarking. which aims to preserve the original language model distribution. We will demonstrate that achieving distortion-free watermarking order-agnostic LMs is not feasible using their approaches.
Order-agnostic language models. Order-agnostic LMs have gained significant attention in machine translation and other NLP tasks due to their ability improve inference efficiency by generating multiple tokens simultaneously rather than sequentially. The pioneering work by Gu et al. (2017) introduced a non-sequential decoding approach through knowledge distillation, reducing machine translation latency and accelerating generation without sacrificing quality. Following this, Mask- Predict by Ghazvininejad al.) (2019) further advanced order-agnostic LMs by introducing masked language model that iteratively refines predictions. Kasai et al. (2020) explored parallel decoding with a disentangled context transformer to achieve faster translation, focusing on improving both speed and quality. Other works, such as Chen et al. (2020) Peng et al. (2020) adapted the non-autoregressive transformer to accelerate speech generation tasks, and Chen et al. (202 ) Tang & Matteson (2021) used spatial-temporal transformer and probabilistic-basee transformer to improve the performance of time-series forecasting. Moreover, in the recent seminal work, Dauparas et al. (2022) proposed an order-agnostic language model for protein design. During generation, the decoding order is randomly
2

---

Published as a conference paper at ICLR 2025
Target pattern set
(by big, kykk)
quinly
P Porellii
Recover
I V.
[cV.
[cy
1c%
lc%
generation steps
Number pation pocurience:
pivalueitlcc postive rate):
Σ
Pral0)= (. 0.5
Patter-mark generator
Patter--ark detector
Figure 2: Illustration of PATTERN-MARK The watermark generation process begins with a Markov thain-based key generator that produces a key sequence. This sequence is then used to modify token probabilities during language model sampling. In the watermark detection phase, the key sequence is recovered from the generated content, and the false positive rate is calculated by counting the occurrences of specific patterns within the key sequence.
sampled from the set of all possible permutations, then the protein sequence is generated from the given order. Order-agnostic decoding enables design in cases where, for example, the middle of the protein sequence is fixed and the rest needs to be designed, as in protein binder design where the larget sequence is known.
3 PATTERN-MARK: A PATTERN-BASED WATERMARKING FRAMEWORK
3.1 PRELIMINARY
Notations. Let V = ..,....,,)) denote the vocabulary (or token) set of language model, with N = = representing its size. Define V as the set of sequences, including those of length zero. We use PM to denote the distribution of language model and Pw to denote the distribution of the watermarked language model. A sequentially decoded language model generates a token sequence conditioned on given prompt. At any step in this process. the probability of generating the next token In E V, conditioned on the preceding tokens from 21 to Tn-1, is denoted by (2 21, .......... 1n) In order-agnostic LMs, the model does not have access the full preceding sequence @ 11 but it may have access to tokens from other positions. Therefore, we use ax represent all tokens that the order-agnostic LM can observe when generating the n-th token. Under this setting, the probability of generating the next token I2 E V for order-agnostic LMs is given by Par(a, (I, x=a)) In our watermarking framework, we will have a key set K, and the set of all key sequences is denoted by K We denote [1 n) as key sequence of length
Watermarking problem. A language model service provider aims to watermark the generated content such that all other users can verify if the content is generated by the LM without needing access to the LM or the original prompt. watermark framework primarily consists of two components: watermark generator and a watermark detector. The watermark generator embeds a watermark into the text through a pseudo-random sampling strategy seeded by watermark keys. The watermark detector, the other hand, detects the presence of the watermark within the content using a statistical hypothesis test.
Discussion Why current watermarking schemes not be adapted to order-agnostic LMs.
Most of the current watermarking schemes (Kirchenbauer et al, 2023a Liu et al. 2023b Huo et al.. 2024) rely on previously generated content as part of the watermark key for producing the next token. During detection, the previously generated content is extracted and used to verify the watermark. This approach works well in sequentially decoded LMs, where both generation and detection follow a left-to-right sequence. However, in order-agnostic LMs, content is generated in a non-sequential manner, and the detector does not know the order in which the tokens were generated. making impossible to use previously generated content for watermark detection. For example, if we apply the Soft-waterd wifermarermak scheme (Kirchenbauer al., (023a) to order-agnostic LMs, when generating the n-th token, the watermark key is derived from the hash of the previous i tokens. However, in order-agnostic LMs, some these previous tokens may not yet be generated, resulting in missing or empty tokens. During detection, all previous tokens are expected to be present, and the absence of those tokens during generation causes a mismatch, making it impossible to retrieve the correct watermark key and thus failing to detect the watermark. To the best of our knowledge, the only watermarking scheme that can be applied to order- aeddo-ignnsticc LMs is the Unigram (Zhao et al. 2023) (which is very similar SelfHash Kirchenbauer et al. (202bb) without left tokens). However, /hao
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 PATTERN-MARK generator
Input: secret key sk, prompt æ m::0 generate length N, key space K, key space dimension
1, transition matrix A E 10, 1] initial distribution Q, generation order
2: First generate key sequence
K" sample [ from the initial key distribution Q
3: for 2- ................................ do
4:
Sample k(i] from Pr(. 4)
5: for i -= l.......
n. do
6:
Calculate the LM distribution for generating the o,-th token Par(- 2 mm:0+ Fo
7:
Calculate watermarked distribution [- 2o k(il) via Eq.
8: Sample the next token To; using distribution (. x Tm 2o,
9: return 1:30
Algorithm 2 PATTERN-MAN MARK detector
1: Input: key space K {ki,.. kr), input sequence {II,.... In), vocabulary split
(Vi..... Ví}. FPR threshold f. pattern length m, target patterns C K", pattern occurrence probability Pr,n
2: Initialize the pattern occurrence number: c 0.
3: Initialize empty key sequence: k.
4: for i 1,..., n do
5:
Recover the i-th key based on the current token 2y; if x4 E Vo, k[i] ke.
6: for = ...... 72 do
7: if k m 1: ii)
then
8: C 1+1
9: Calculating Pr. from Alg. 3
N R-m++1
10: Calculating the false positive probability for the input text FPR =
Σ
(r,((i)
==c
if FPR f then
12: Return: æ is watermarked by PATTERN-MARE
else
14: Return: æ is not watermarked by WENTERN-MARE
al. 2023) uses fixed red-green list split the vocabulary and consistently promote the probability of green tokens, which will hurt the generation quality across the entire generation process.
watermarking schemes not be adapted order-agnostic LMs. We claim that the current distortion- free scheme cannot be applied to order-agnostie LMs. There are two primary reasons for this: 1) The distortion-free property relies on the autoregressive nature of
Discussion Why distortion-
LMs. According to Christ et al. 22033) Hu et al. (2023)) ; Wu et al, (2024), a distortion- free watermark k, ) for every token n. However, some order-agnostic LMs are non- aoneautoregrsssvve. For example, In-1 and Fn are generated simultaneously from joint distribution Pw (Xi, In- 1 Kn, -1) This makes it impossible to maintain independent Pw 2e kn) for each 2) The distortion-free property also requires non-repeating watermark keys during generation. In sequentially decoded LMs, the watermark key space can be expanded using n-gr a-gram hashing. However, this approach is not feasible in order-agnostic LMs because some tokens in the n-gram may not yet be generated, making it impossible to fully reconstruct the n n-gram during watermark detection.
requires independent probabilities Pw ( x
3.2 PATTERN-BAN WATERMARKING FRAMEWORK
In this work, propose pattern- based Watermarking framework, specifically designed for order- agnostic LMs (see Figure for a detailed illustration). Given keys K := (k1, h2,.... kr we
partition the vocabulary unique key pattern. During the generation process, we first produce sequence of keys k == ks, .e....., ..... ki,, where n is the length of the generated content. When generating the j-th token, we will promote the probability of tokens within V,,. We follow the probability promotion strategy in Kirchenbauer al. (2023a). Specifically, given initial LM token probability Par (t) and key
into distinet parts V1, V2,..., Vi, where each part corresponds to a
4

---

Published as a conference paper at ICLR 2025
Algorithm 3 Compute pattern occurrence probability under the null hypothesis
Input: key space K, input sequence length n, pattern length m, m target patterns T Km
key space dimension /
2:
Output: pattern occurrence probability Pr.
3: Initialize the status probability distribution P, (C, S), where C' E fo...., n m + 1} represents
the number occurrences of patterns, S Km-1 represents the last m keys in a key sequence.
4: Initialize P,(C = c, ==
Vi,c,
5: Pm-1(C' = 0, =s) (+)=
6: for ........ .
7:
for Vss E Km-1 do
8: s' = kh 81mm22
9:
for 0, ..., m11 do
10:
P.(C = S, -)
Σ kEK (k,aT
P-- = S, =')
11:
for lrc==1.....f -m do Pi(C= S 8)+
12:
E
Pi-I(C = c = =
13:
(r,n(c)= Pa(C c, ==
sEKm-
return Pr..-
k, the watermarked probability for the token, denoted by Pw (t), is formulated as:
e' PM)(() Ever Pxi(t)) Even Pa
te V2
(t ki)
(I)
PM Engy, (M)( Erev, PM)
t V;;
During detection, we analyze the generated sequence to uncover regular patterns in the key sequence, verifying the presence of the watermark by identifying these patterns.
Markov-chain-basee key sequence generation. During watermark detection, we do not have access the entire key sequence used in watermarking. To address this, we propose Markov-chain-basee key sequence generation method, which generates a key sequence with high-frequency patterns (i.e., subsequences). This allows us to focus on detecting specific patterns.
A Markov process is stochastic process that describes sequence of events, where the probability of each event depends only on the state of the previous event. Given a transition matrix A := (asy 1xi+ where diy denotes the transition probability from state k; kj, we define the Markov-chain based key sequence generation as follows:
Definition 3.1 (Markov-chain based key sequence generation). Let X, be the random variable representing the t-th position of the sequence, A = (az))xxi the transition matrix, and Q (91, .... 91 the initial probability. The key sequence generated according to the rule Pr(X, = k;) = 9j and Pr(X++1 kj X, k.) 0ij,
0.3
0.7
For example, if 2 (i.e., we have two keys) and the transition matrix is A
i.e. the
0.7
0.3
next state has probability of 0.3 to remain the same and 0.7 to switch to the other state. Then the number of patterns like ki k2 and k2nk will be significantly higher than patterns like k and k2 in the generated Markov chain. This enables us to build statistical detection algorithm based on the difference in the frequency of patterns between watermarked and non-watee conermatrrrreed content.
Besides, the self-transition probabilities a and a22 E [0, 1] (0.3 in the example above) control the frequency of patterns in the generated key sequences. When 411 and 022 increase, patterns k kı and kgk2 are more likely appear in the generated key sequence. Conversely, when 011 and a22 decrease, we are more likely to observe patterns k K2 and k2kj. Therefore, to improve detection efficiency, typically select either extremely large small values for an and d22- However, with
5

---

Published as a conference paper at ICLR 2025
large values of 011 and d2g, the sequence may mainly consist of single key, which could negatively impact generation quality. Hence, we generally select smaller values of d11 and 022 for key sequence generation.
Statistical pattern-based detection. During watermark detection, we recover a key sequence from the generated content. We use hypothesis test conduct watermark detection, where the null hypothesis Ho states that the text is not watermarked with PATTERN-MARK, Under the null hypothesis, the recovered key sequence should follow Markov chain with uniform transition probabilities (i.e.. A = (a.j 1/0)xxt).
Given set of patterns T C. K", let ST(K) := أز=1 -m which represents the number of selected patterns in T that appear in the key sequence k E K" We can compute its probability density function Pr,n = Pr(S)(k))) = i), where & random key sequence selected from K". Given observed pattern count c, the p-value (false positive rate, a.k.a. FPR) for this hypothesis test is 500 == Pr. The detailed algorithms for watermark generation and detection are provided in Alg. and Alg. In Alg. provide the algorithm we used to calculate the probability density function Pr.--
3.3 PT.m CALCULATION.
In this part, we provide a detailed analysis and explanation of the algorithm (Alg. B designed to compute the probability distribution of pattern occurrences in sequences generated by Markov chain. The algorithm calculates the probability Pr, (c) that a set of target patterns T C K"m occurs exactly e times sequence of length n over a key space K.
Overview. Our algorithm employs dynamic programming to efficiently compute the probability distribution by tracking the number of pattern occurrences and the last m 1 keys in the sequence. The key components including the key space K, sequence Length n, pattern length m, target patterns T TC km.
State Representation. At each position in the sequence, the algorithm maintains probability distribution over states. E {0..... n m + } The number of occurrences of the target patterns so far. S E Km-11 The last - keys in the current sequence. The state probability distribution at position is denoted as P.(C c, = s) (r(Sr(k[1 il) = c, kli m + 2: =s)), s), where a random key sequence.
Initialization.
Vi, ei 8, and Pm- (C- = S = 8) = ( Vs = [..,..., 8m- E K km Here, Pm. Pm-1 0, s) represents the probability of starting with sequence s without any occurrences of the target patterns.
8) The algorithm initializes the state probabilities with P:(C -
Dynamic programming iteration. For each position i from to and each possible sequence s = [21,52,... ....... mm-1] E km11, the algorithm updates the state probabilities through the following step: Construct the previous sequence s' by shifting left and adding
key k E K: s'
[k. $1, $2 5m-2). Case 1: [s', sm-1] $ T (no new occurrence of a target pattern). update for 0 to i m: PC c, S 8)+ P
S 8'). Case 2: If [s' 8m- 1] T (new occurrence of a target pattern), update for c = 1 to m 1: P.CC c - 1,5 s').
8) PC
Final Probability Computation. After completing the iterations up to position n, the total prob- ability for each count e is calculated by summing over all possible sequences S: Pr,,(c) = EoEkm (C = c, S= 8). The time complexity of this algorithm is O(n2pm) and the memory complexity is (m-)m
4 EXPERIMENTS
Our experimental section consists three parts. In the first part, we compare the detection efficiency of PATTERN-MARK with the baseline. In the second part, we evaluate the generation quality of PATTERN- In the third part, we assess the robustness of the PATTERN-MA MARK when subjected to random token modification and paraphrasing attacks. We focus two seq2seq tasks in our experiments: machine translation with CMLM model (Ghazvininejad et al. 2019), and protein generation with ProteinMPNN (Dauparas et al. 2022).

---

Published as a conference paper at ICLR 2025
Table I: Empirical true positive rate (TPR) for watermark detection protein generation, each row is averaged over around 800 generated protein sequences. We report the TPR under {10%, 1%, 0.1%, 0.01% %. 0.001%) } theoretical FPR. more detailed comparison can be found in Table
TPR @FRP
Protein generation
PLDDT
10%
1%
0.1%
0.01%
0.001%
No Watermark
85.46
Soft watermark($ 1.50)
84.30
12.99
2.68
0.80
0.13
0.00
Multikey(o 1.50)
84.20
67.20
33.87
14.32
6.96
2.68
Unigram(6 = 1.50)
83.58
96.12
92.10
85.14
77.51
69.75
ANTTERN-MRK(( = 0.50)
85.42
47.26
17.94
6.29
2.54
0.67
PATTERN- MARKI 0.75)
85.05
81.79
51.00
30.66
17.80
9.37
PATTERN-MARK( = 1.00)
84.74
97.46
88.35
68.27
50.87
38.02
PATTERN-MARK( = 1.25)
84.50
99.87
98.80
96.12
87.28
77.24
6ATTERN-MARK( 1.50)
84.02
100.00
100.00
99.87
99.06
96.39
Table 2: Empirical positive rate (TPR) for watermark detection on machine translation, each row is averaged over around 1000 generated sequences. We report the TPR under {10%, 1%, 0.1%, 0.01% %, 0.001 % theoretical FPR. more detailed comparison can be found in Table
TPR @ FPR=
Machine translation
BLEU
10%
1%
0.1%
0.01%
0.001%
No Watermark
32.85
Soft watermark(f 5)
25.58
97.91
85.04
60.22
36.89
20.44
Multikey(ō =
27.82
89.93
60.52
32.00
13.66
5.38
Unigram(5 = 5)
22.23
99.90
99.20
95.41
88.53
78.07
MNTTERN-MARK( 1)
33.02
19.74
4.59
0.50
0.10
0.00
MATTERN-MAR(( 2)
32.60
57.33
28.41
13,96
8.47
4.39
PATTERN-MARK() 3)
31.67
86.04
65.70
46.86
33.30
24.73
PATTERN-MARK(ó 29.43
98.21
89.53
79.16
67.00
56,83
PATTERN-MARK(Ó 5)
24.23
100.00
99.80
98.01
95,41
91.13
4.1 EXPERIMENTAL SETTINGS
In this part, we provide a general introduction of our experimental settings, a more detailed version can be found at Appendix B
Since there are generally no watermarking methods specifically designed for agder-agnostic LMs, we mainly compare PATTERN MARK with three baseline methods adapted from existing approaches: the Soft watermark Kirchenbauer et al. (2023a), Unigram iZhao et al. (202)), and Multikey wa- termark Kirchenbauer et al. (2023a). We mainly three metrics to measure the quality of the generated content. Specifically, we use pLDDT (Jumper et al.) [2021) and protein diversity to measure the quality of the protein generation task, and BLEU (Papineni et al. 2002) to measure the quality of the machine translation task.
Protein generation task
Machine transistion task
1.00
Patte mark
Pattem mark
TPR@FFR=0
0.75
Unigram
TPR@FPR-0.15
Unigram
Soff
0.50
Multkey
0.50
Mullikay
0.25
0.25
0.00
0.00
0.835
0.840
0.845
0.850
24
28
PLDDT
BLEU
Figure 3: Comparison of the trade-off between TPR and generalization quality on protein generation and machine translation tasks. Left. TPR OPR=FPR=0.15 1 vs. pLDDT on protein generation task. Right. TPR @ FPR=0.194 % vs. BLEU on machine translation task.

---

Published as a conference paper at ICLR 2025
Table 3: Empirical true positive rate of different watermarks under random token modification with attack strength on protein generation task. Each row is averaged over around 800 generated protein sequences. We report TPR under 0.1 FPR.
Protein generation
= 0
0.05
= 0.1
0.2
0.3
Soft (atermark(0 = 1.50)
0.80
0.54
0.27
0.13
0.00
Multikey(O = 1.50)
14.32
10.84
9.24
5.22
2.01
Unigram(6 = 1.50)
85.14
82.73
78.05
68.41
54.08
PATTERN BATTERN-MARK(6 0.50)
6.29
5.09
4.02
2.14
1.07
PATTERN-MARK(0 0.75)
30.66
24.63
19.01
11.24
5.22
MARKIO 1.00)
68.27
60.78
51.41
31.46
16.73
PATTERN-MARK(6 1.25)
96.12
90.09
83.13
64.79
39.63
WITERN-MARKIG -1500)
99.87
98.66
97.05
87.82
65.73
Table 4: Empirical true positive rate different watermarks under ChatGPT paraphrasing attack with attack strength on machine translation task. Each is averaged over around 1000 generated sequences. We report TPR under 0, % FPR.
Machine translation
0.05
0.1
0.2
0.3
Soft watermark($ 5)
60.22
48.26
38.38
28.22
19.04
Multikey(5 = 5)
32.00
19.74
13.76
8.67
4.99
unigram(6 = 5)
95.41
90.03
87.14
77.27
64.01
PATTERN PATEER--MARK( 1)
0.50
0.80
0.50
0.30
0.40
WITTERN-MARK(C 6- 2)
13.96
13.26
11.57
9.97
7.38
PATTERN MARKK 3)
46.86
42.47
38.88
34.20
29.41
PATTERN-MARK( 4)
79.16
74.68
72.58
64.81
58.13
PATTERN-MARKE 5)
98.01
97.10
95.81
93.32
89.53
Watermark settings. In SAITERN-MARY we select the key set = ( k2 the Markov-chain
transition matrix A [[0, 1], [1, O]]. and the initial distribution Q [0.5, 0.5]. The key patterns defined as T = {ki k2 ki k2 ....., where kj and ki appear alternately, T K Under this configuration, the probability Pr,, be calculated with Algorithm 4 which optimizes the process described in Algorithm
3
The computational complexity is reduced from Onn²2m) to On²m)..
4.2 DETECTION EFFICIENCY
We evaluate the detectability of our watermark machine translation and protein generation. For protein generation tasks, the generated content length is around 300-500, and for machine translation tasks, the generated content length is around 50-100. We select 8 E {0.5, 0.75, 1.0, 1.25, 1.5) for protein generation task, and 5 E {1, 2, 3, 4, 5} for machine translation task. We report the true positive rate at the theoretical false positive rate (TPR @ @FPR with 10%, 1 1%, 0.1%, 0.01 % and 0.001% % FPR. In Appendix Table 5 and Table 6 we present the more detailed results.
The results are presented in Table and Table As shown, under the same probability promotion level ò, our method consistently outperforms the baseline methods. Additionally, we include the average PLDDT and BLEU scores in Table Table When 5 1.25, PATTERN- MATTERN-MRRK surpasses all baselines in both generation quality and detectability in the protein generation task. Moreover, when 4, ANTTERN-ARK outperforms the Soft watermark in both generation quality and detectability in the machine translation task, and at å = 5, PATTERN-MARK surpasses the Unigram method on both metries for the same task.
4.3 QUALITY-DETREE SAALIY-DETECTABILITYY TRADE-OFF
We examine the trade-off between watermark detection efficiency and generation quality of our method across two tasks: for the protein generation task, utilize pLDDT quality metric, while for the machine translation task, we employ the BLEU score. We also made additional quality comparisons in Appendix C.I
Figure 3 illlstrraes the trade-off between watermark detectability and generalization quality across both tasks. Each point in the figure corresponds experiment with specific ó, where the values
8

---

Published as a conference paper at ICLR 2025
Protein generation task
Machine transtation task
T 0.1%
1.00
Model:
1.00
Model:
6 0.50
0.75
6 2
0.50
1.00
0.50
6 3
6 1.25
0.25
6 1.50
6= 5
0.00
2
Pattern length m
Pattem length m
Figure 4: Evaluation of the effect of pattern length m on the detection efficiency of WETTERN-MARK Left. Protein generation task. Right. Machine translation task.
Protein generation lask
Machine translation task
Model:
Model:
6- 0.50
PLDDT
0.850
5 0.75
1.00
=
0.845
6 125
6 1.50
24
0.0
0.1
0.2
0.5
0.1
0.2
0.5
Transition matrix ass
Transition matrix a11
Figure 5: Evaluation of the effect of transition matrix probability on the generation quality of PATTERN-MARK. Left. Protein generation task. Right. Machine translation task.
of are determined according to Sec. 4.2 The results indicate that our method achieves a generally superior trade-off compared to all baselines.
4.4 ROBUSTNESS
We compare the robustness of PATTERN-MARE against the baselines on both the protein generation and machine translation tasks. For the protein generation task, we employ random token modifica- tion attack, while for the machine translation task, Unfortunately, we are unable to evaluate paraphrase attacks on protein generation due to the absence of suitable rephrasing model. To perform the robustness experiment, reuse the generated content from Sec. 4.2 The results of these experiments are presented Table and Table From these tables, is evident that PATTERN-MARE consistently outperforms the baselines across both tasks.
paraphrase attack generated via ChatGPT.
4.5 ABLATION STUDY
We present ablation study check the effect of pattern length m and the transition matrix on the detectability and the quality of our watermark.
Pattern Length m. We analyzed the detection efficiency of PATTERN-MARE across various pattern lengths m in protein and language contexts. As shown in Figure 4 the efficiency initially improves with an increase in m then subsequently declines. Specifically, for protein generation tasks, the optimal detection performance is attained at m = 5. In contrast, for machine translation tasks, the best performance achieved with 4.
Generally, increasing the pattern length m leads to improved detection efficiency to some extent. This improvement can be attributed that longer patterns are less likely to appear in randomly generated key sequence. However, excessively long patterns also introduce a higher sensitivity to errors during key sequence recovery. Consequently, while longer patterns enhance detection, they also risk increasing the false positive rate due to their sensitivity to minor errors. This trade-off results in the observed decline in detection efficiency for excessively long patterns.
Transition matrix. We evaluated the quality of content generated using various configurations of
the transition matrix A = a11
1
1- a11
According to Figure 5, the quality of the generated
aj1
Q11
content remains consistent across different values of a11- Consequently, select a 0, which corresponds to the strongest watermarking signal, as it does not compromise the quality while enhancing the watermark's detectability.

---

Published as a conference paper at ICLR 2025
5 CONCLUSION
In conclusion, PATTERN- MARK presents significant advancement in language model watermarking. specifically addressing the challenges posed by watermarking order-agnostic LMs. By innovatively leveraging Markov-chain-basee key sequence generation and statistical pattern-based detection algorithm, this framework effectively embeds and detects statistical watermarks in non-sequentially generated text. Through comprehensive evaluation of prominent non-sequential models like Pro- teinMPNN and CMLM, PATTERN- -ARKK has proven to be superior in terms of detection accuracy and reliability compared to traditional watermarking techniques, providing novel approach for watermarking the order-agnostic LMs.
REFERENCES
Scott Aaronson. My Al safety lecture for UT effective altruism,. 2022. URL
https://
scottaarenson wwwgg/pp-6222
Sarah Alamdari, Nitya Thakkar, Rianne van den Berg, Alex Xijie Lu, Nicolo Fusi, Ava Pardis Amini, and Kevin K Yang. Protein generation with evolutionary diffusion: sequence is all you need. bioRxiv, pp. 2023-09, 2023.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005 2020.
Zhanrui Cai, Changcheng Li, Jiawei Wen, and Songshan Yang. Asset splitting algorithm for ultrahigh dimensional portfolio selection and its theoretical property. Journal of Econometrics, pp. 105291, 2022.
Supriyo Chakraborty, Seraphin Bernard Calo, and Jiawei Wen. Using disentangled learning to train an interpretable deep learning model, June 23 2022. US Patent App. 17/133,437.
Kai Chen, Guang Chen, Dan Xu, Lijun Zhang, Yuyao Huang, and Alois Knoll. Nast: Non-autoreereessvee spatial-temporal transformer for time series forecasting. arXiv preprint arXiv:2102.05624, 2021.
Nanxin Chen, Shinji Watanabe, Jesús Villalba, Piotr Zelasko, and Najim Dehak. Non-autoregressive transformer for speech recognition. IEEE Signal Processing Letters, 28: 121-125, 2020.
Ruibo Chen, Yihan Wu, Lichang Chen, Guodong Liu, Qi He, Tianyi Xiong, Chenxi Liu, Junfeng Guo, and Heng Huang. Your vision-language model itself is strong filter: Towards high-quality instruction tuning with data selection. arXiv preprint arXiv:2402. 12501, 2024a.
Yanshuo Chen, Zhengmian Hu, Yihan Wu, Ruibo Chen, Yongrui Jin, Wei Chen, and Heng Huang. Enhancing biosecurity with watermarked protein design. bioRxiv, pp. 2024-05, 2024b.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint ar 1XX1:22306009144 2023.
Justas Dauparas, Ivan Anishchenko, Nathaniel Bennett, Hua Bai, Robert Ragotte, Lukas F Milles, Basile IM Wicky, Alexis Courbet, Rob de Haas, Neville Bethel, et al. Robust deep learning-based protein sequence design using proteinmpnn. Science, 378(6615):49 56, 2022.
Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-predict: Parallel decoding of conditional masked language models. arXiv preprint arXiv:1904.09322. 2019..
Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher. Non-autoregressive neural machine translation. arXiv preprint arXiv: /7| 1 /.02281, 2017.
Ziming Hong. Zhenyi Wang, Li Shen, Yu Yao, Zhuo Huang, Shiming Chen, Chuanwu Yang, Mingming Gong, and Tongliang Liu. Improving non-transferable representation learning by harnessing content and style. In The Twelfth International Conference on Learning Representations, 2024.
Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. arXiv preprint arXiv:2310. 10.11669, 2023a.
10

---

Published as a conference paper at ICLR 2025
Zixuan Hu, Li Shen, Zhenyi Wang. Baoyuan Wu, Chun Yuan, and Dacheng Tao. Learning to learn from APIs: Black-bos box data-free meta-leamning In Proceedings of the 40th International Conference Machine Learning, pp. 13610-13627. PMLR, 2023b.
Xiao Shi Huang, Felipe Perez, and Maksims Volkovs. Improving non-auloregressive translation models without distillation. International Conference on Learning Representations, 2022.
Mingjia Huo, Sai Ashish Somayajula, Youwei Liang, Ruisi Zhang, Farinaz Koushanfar, and Pengtao Xie. Token-specific watermarking with enhanced detectability and semantic coherence for large language models. arXiv preprint arXiv:2402. 2024.
John Jumper. Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. nature, 596(7873):583- 2021.
Jungo Kasai, James Cross, Marjan Ghazvininejad, and Jiatao Gu. Non-autoregressive machine translation with disentangled context transformer. In International conference on machine learning. pp. 5144-5155. PMLR, 2020.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. watermark for large language models. arXiv preprint 1rXiv:2301.10220 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. arXiv preprint S..i::2306.0463344 2023b.
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593 2023.
Aiwei Liu, Leyi Pan, Xuming Hu, Shu' ang Li, Lijie Wen, Irwin King, and Philip S Yu. An unforgeable publicly verifiable watermark for large language models. arXiv preprint arXiv:2307. 16230, 2023a.
Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijic Wen. A semantic invariant robust watermark for large language models. arXiv preprint arXiv:2310.06356, 2023b.
Chenxi Liu, Zhenyi Wang, Tianyi Xiong, Ruibo Chen, Yihan Wu, Junfeng Guo, and Heng Huang. Few-shot class incremental learning with attention-aware self-adaptive prompt. arXiv preprint arXiv:2403.09857, 2024.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Kainan Peng, Wei Ping, Zhao Song, and Kexin Zhao Non-autoregressive neural text-to-speech. In International conference on machine learning, pp. 7586-7598. PMLR, 2020.
Binh Tang and David S Matteson. Probabilistic transformer for time series analysis. Advances in Neural Information Processing Systems, 34:23592- -26698, 2021.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Zhenyi Wang, Li Shen, Tiehang Duan, Qiuling Suo, Le Fang, Wei Liu, and Mingchen Gao. Dis- tributionally robust memory evolution with generalized divergence for continual learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023a.
Zhenyi Wang, Li Shen, Tongliang Liu, Tichang Duan, Yanjun Zhu, Donglin Zhan, David Doermann, and Mingchen Gao. Defending against data-free model extraction by distributionally robust defensive training. In Thirty-seventh Conference on Neural Information Processing Systems, 20236.
Jaawei Wen, Songshan Yang, Christina Dan Wang, Yifan Jiang, and Runze Li. Feature-splitinn algorithms for ultrahigh dimensional quantile regression. Journal of Econometrics, pp. 105426, 2023.
11

---

Published as a conference paper at ICLR 2025
Jiawei Wen, Songshan Yang. and Delin Zhao. Nonconvex dantzig selector and its parallel computing algorithm. Statistics and Computing. 34(6):180, 2024.
Yihan Wu, Hongyang Zhang, and Heng Huang, Retrievalguard: Provably robust 1-nearest neighbor image retrieval. In International Conference on Machine Learning, pp. 24266-24279, PMLR, 2022.
Yihan Wu, Aleksandar Bojchevski, and Heng Huang. Adversarial weight perturbation improves generalization graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10417-10425, 2023a.
Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: A stealthy, efficient and resilient watermark for large language models. arXiv preprint arXiv:2310.07710, 2023b.
Yihan Wu, Heng Huang, and Hongyang Zhang, A law of robustness beyond isoperimetry. In International Conference on Machine Learning, pp. 37439-37455. PMLR, 2023c.
Yihan Wu, Ruibo Chen, Zhengmian Hu, Yanshuo Chen, Junfeng Guo, Hongyang Zhang, and Heng Huang. fist watermarks are not truly distortion-free under watermark key collisions. arXiv preprint www.iv:2406.026/00 2024.
Zhiwei Xu and Chundian Li. Low-entropy cloud computing systems. Scientia Sinica Informationis, 47(9):1149-1166 -163, 2017.
Songshan Yang, Jiawei Wen, Xiang Zhan, and Daniel Kifer. Et-lasso: new efficient tuning of lasso-type regularization for high-dimensional data. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 607-616, 2019.
Songshan Yang, Jiawei Wen, Scott Eckert, Yaqun Wang, Dajiang Liu, Rongling Wu, Runze Li, and Xiang Zhan. Prioritizing genetic variants in gwas with lasso using permutation-assistee tuning. Bioinformatics, 36( 36(12):3811 1-3817, 2020.
Ruisi Zhang, Shehzeen Samarah Hussain, Paarth Neekhara, and Farinaz Koushanfar. (REMARK- LLM): A robust and efficient watermarking framework for generative large language models. In 33rd USENIX Security Symposium (USENIX Security 24), pp. 1813-1830, 2024.
Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xi Xiang Wang. Provable robust watermarking for ai- generrtede text. arXiv preprint arXiv:2306. /7439, 2023.
12

---

Published as a conference paper at ICLR 2025
A
ALGORITHMS FOR CALCULATING PATTERN OCCURRENCE PROBABILITY
In Alg. 4 show the exact algorithm used for calculating the pattern occurrence probabilities.
Algorithm Compute pattern occurrence probability under the null hypothesis
1: Input: key space K = {ki, k.2, input sequence length n, pattern length m > 2, target patterns Tm
kk K2ki ( Km (k1,22 appear alternately), initial key distribution
length
length
Q = 0.5).
2: Output: pattern occurrence probability Pr,,,
3: Initialize the status probability distribution P, (C, where C E (0...., m + 1) rep- resents the number of occurrences of patterns, given the current key sequence k. M min(arg max (
-1] E Tw/,, 1) represents the longest tail sequence (at most m m- 1) where 11 and k2 appear alternately.
4: Initialize P,(C = c, M = m²) = 0, Vi, c.
5: PC M, = 1
6: for i = 2...:,.....
1 do
7: Pi(C = M
M - -1) = m/=1
Σ P:- -0- = mm')
8:
for m' = 2, ,, do
9:
P.(C 0, m') PP - mm
0,
10:
for i= =m..... do
for .,....f m do
m-1 P:(C c, M 1) 1) = Σ (C =m)
m'=1
13:
for m 2, .....
do
14:
M = 11) P-(C = M = m = 2 P (C = C
for c= 1...,,, 1
16:
P2(C = c, M = ====---- 1- 1)+ 1 Pi (C =c 1,M =m mm-
17:
Pr, (c) Σ (C M c=m
m/=1
18: return Pr.--
B EXPERIMENTAL SETTINGS
Baseline. Since there generally watermarking methods specifically designed for order-agnostic LMs, we mainly compare PATTERN-MARE with three baseline methods adapted from existing approaches: the Soft watermark Kirchenbauer et al. (2023a). Unigram /Zhao et al. (2023). and Multikey watermark Kirchenbauer et al. (2023a). For Unigram, we adhere to the configurations as originally specified the literature. In the case of the Soft watermark, we utilize 1-gram tokens as watermark keys. When this I-gram token is an empty token, we just use this empty token directly as the seed for watermark embedding. The Multikey watermark method modifies the Soft watermark approach by substituting the gram watermark keys with two predetermined keys, randomly selecting one to seed the watermarking process at each generation step.
We mainly use three metrics to measure the quality of the generated content. Specifically, we use DDD and protein diversity measure the quality of the protein generation task, and BLEU to measure the quality of the machine translation task.
Metrics.
PLDDT. The PLDDT (Jumper et al. 2021 metric is crucial evaluation tool in the field of computational biology, particularly in protein structure prediction. This metric quantitatively assesses the confidence in the predicted local structure of proteins at the residue level. Developed as part of the AlphaFold2 architecture by DeepMind, PLDDT has become a standard for evaluating the reliability of predicted protein structures.
13

---

Published as a conference paper at ICLR 2025
Protein diversity, Protein diversity is entropy-basee metric to quantify the diversity of amino acid sequences within a set of proteins, where a higher entropy value indicates a greater variety of amino acids at each position in the sequence, indicating higher protein diversity.
BLEU score. For the machine translation task, we utilize the BLEU score (Papineni et al. 2002) to evaluate the lexical similarity between translations produced by the machine and those generated by humans.
Settings. In our experiments, we adhere to the default parameters set for ProteinMPNN (Dauparas) cet al.) 2022) and CMLM (Ghazvininejad et al., 2019). ProteinMPNN is specifically developed for protein redesign tasks, requiring the generation of protein sequence from given 3D protein backbone structure. It employs an encoder-decoder architecture, enabling order-agnostic sequence generation. This is facilitated by the encoded structural context which guides the subsequent decoding steps. We utilize the v 48 020 model checkpoint for ProteinMPNN.
The CMLM operates under encoder-encoder framework. During inference, the model processes in fixed steps, simultaneously generating multiple tokens at each step irrespective of their sequential positions. Tokens with lower probabilities identified for regeneration in subsequent steps. For the CMLM, we apply it to a Romanian- Romanian-English translation task using the available pre-trained checkpoint.
Dataset. For CMLM, use the data collected from news craw news. 10..5..ro.shue ro.shuffled whose length is larger than 128 to encourage longer generation. The filtered dataset has 1003 samples.
For ProteinMPPNN, we the protein features from PCSB Protein Data Bank which is published from 2020 Jan. 1st to 2023 Dec. 3stt We limit the number of polymer residues per deposited model between 400 and 500. The filtered dataset has 747 samples.
In PATTERN-MARK, we select the key set K = {ki, k2). the Markov-chain transition matrix 0 and the initial distribution Q = [0.5, 0.5]. The key patterns are defined as T
A
(kikgl .... bogg where 1 and 12 appear alternately, T Λmm Under this configuration, the probability Pr,. can be calculated using Algorithm 4 which optimizes the process described in Algorithm Algorithm
The computational complexity of Algorithm On)2), compared to O(n22T)) for
we present an ablation study to evaluate the effects of different transition matrices A and various lengths of key patterns m on detection accuracy.
In Section 4.5
C ADDITIONAL EXPERIMENTS
In this part, we show additional experiments about the detection efficiency comparison between PATTERN-MANE and baselines on protein generation and machine translation tasks. We select (0.5, 0.75, 1.0, 1.25, 1.5] for protein generation task, and ô E {1, 2, 3, 5} for machine translation task.
The results are presented in Table 5 and Table 6 As shown, under the same probability promotion level our method consistently outperforms the baseline methods.
C.I QUALITY EVALUATION
We compare the performance of our method across two tasks: for the protein generation task, we utilize PLDDT quality metric and protein diversity as measure of diversity, while for the machine translation task, we employ the BLEU score. Additionally, we examine the trade-off between watermark detection efficiency and generation quality.
'https///data. http://daaaa.ttttmoooogg////sss/ wwwp.ttrr////cwsrww/// httpp://www.resb.org/
14

---

Published as a conference paper at ICLR 2025
Table 5: Empirical true positive rate (TPR) for watermark detection protein generation, each row averaged over around 1000 generated protein sequences. We report the TPR under {10%, 1%, 0.1%, %, 0.01% %, 0.001% % theoretical FPR.
TPR @PR@FPR=
pLDDT
10%
1%
0.1%
0.01%
0.001 %
No Watermark
85.46
Soft watermark($ = 0.50)
85.46
6.83
1.07
0.54
0.13
0.00
Soft watermark(Ō 0.75)
85.18
9.24
1.74
0.13
0.13
0.00
Soft watermark(6 = -1.00)
84.99
11.24
1.87
0.54
0.00
0,00
Soft watermark(6 -1.25)
84.67
12.58
2.28
0.54
0.13
0.00
Soft watermark($ = 1.50)
84.30
12.99
2.68
0.80
0.13
0.00
Multikey(& 0.50)
85.59
1.20
0.53
0.13
0.13
0.13
Multikey(o 0.75)
85.51
4.95
1.07
0.67
0.40
0.13
Multikey(& -1.00)
85.27
16.47
4.69
1.74
0.54
Multikey(ō 1.25)
84.75
44.18
13.79
6.02
2.28
1.07
Multikey(d 1.50)
84.20
67.20
33.87
14.32
6.96
2.68
Unigram(6 8 0.50)
85.43
10.58
5.09
3.35
2.54
1.34
Unigram 0.75)
84.80
33.33
18.21
11.65
8.17
5.76
Unigram(5 1.00)
84.54
68.54
44.44
31.86
21.55
17.27
Unigram & 1.25)
84.00
88.09
78.05
63.59
47.79
37.22
Unigram 6 1.50)
83.58
96.12
92.10
85.14
77.51
69.75
PATTERN PATTERN-MARK(S 0.50)
85.42
47.26
17.94
6.29
2.54
0.67
PATTERN-MARK( 0.75)
85.05
81.79
51.00
30.66
17.80
9.37
PATTERN-MARK(6 1.00)
84.74
97.46
88.35
68.27
50.87
38.02
PATTERN-MARK(Ō 1.25)
84.50
99.87
98.80
96.12
87.28
77.24
PATTERN-MARKE = 1.50)
84.02
100.00
100.00
99.87
99.06
96.39
Table 6: Empirical true positive rate (TPR) for watermark detection on machine translation, each row averaged over around 1000 generated sequences. We report the TPR under (10%, 1%, 0. %, 0.01% %0 0.001% thcoretical FPR.
TPR @FR@FPR-
BLEU
10%
1%
0.1%
0.01%
0.001 %
No Watermark
32.85
Soft watermark($ = 1)
32.96
54.94
23.13
7.48
2.59
0.70
Soft watermark(S 2)
32.66
79.46
45.36
22.83
10.67
4.39
Soft watermark(8 3)
31.63
87.74
61.91
37.69
18.25
7.38
Soft watermark($ 4)
29.86
93.82
75.17
48.45
27.12
12.66
Soft watermark(5 5)
25.58
97.91
85.04
60.22
36.89
20.44
Multikey(8- 11
32.92
5.08
0.80
0.20
0.10
0.00
Multikey(8 2)
32.86
14.46
2.49
1.00
0.50
0.50
Multikey(5 3)
32.05
34.30
8.87
2.59
1.00
0.60
Multikey(d 4)
30.70
60.62
25.42
9.37
3.49
1.40
Multikey(ō 5)
27.82
89.93
60.52
32.00
13.66
5.38
Unigram(6 1)
32.89
2.79
0.50
0.00
0.00
0.00
Unigram(6 2)
32.59
17.65
4.89
1.30
0.50
0.20
Unigram(5 3)
31.75
56.73
26.02
10.47
4.29
1.99
Unigram 4)
28.64
91.03
72.28
50.55
31.01
18.94
Unigram(6 5)
22.23
99.90
99.20
95.41
88.53
78.07
PATTERN MATTERN-MARK(S 1)
33.02
19.74
4.59
0.50
0.10
0.00
PATTERN-MARK( 2)
32.60
57.33
28.41
13.96
8.47
4.39
PATTERN-MARK(3 3)
31.67
86.04
65.70
46.86
33.30
24.73
PATTERN-MARK(O 4)
29.43
98.21
89.53
79.16
67.00
56.83
PATTERN-MARK
24.23
100.00
99.80
98.01
95.41
91.13
15

---

Published as a conference paper at ICLR 2025
0.9
Statemmark
Pattern-marki 0.50)
Puttern-mar al5 0.75)
Paternmmukis
F 1251
Figure 6: Comparison the pLDDT of the protein generated from PATTERN- MARTER--MARK with the non- watermarked model.
Table Comparison of the protein diversity of the protein generated from different watermarking approaches.
1-gram entropy
2-gram entropy
3-gram entropy
No Watermark
4.091
8.019
11.830
Soft watermark($ = 1.50)
4.024
7.828
11.554
Multikey(d 1.50)
4.034
7.912
11.700
Unigram(6 1.50)
3.934
7.708
11.371
PATTERN-MARK() 1.50)
4.105
7.998
11.763
In Figure 6 and Table we compare the quality of protein generation between PATTERN-MARK and the non-watermarked model. It is evident that under the same our method consistently produces proteins of high quality and diversity.
16

---

Published as a conference paper at ICLR 2025
D BROADER IMPACT STATEMENT
Machine learning models have profound impacts across various domains, demonstrating significant
potential both enhancing efficiencies and addressing complex challenges (Yang et al. 2020 2019
Wen et al. 2023
Chakraborty et al. 2022 Cai et al. 2022 Chen et al. 2024a Xu & Li 2017
Liu et al.
2024, Wen al. 2024) However, alongside these positive impacts. there are concerns
about the integrity and security of machine learning applications (Hong et al. 2024] Hu et al.) 2023b]
Wang et al.
2023b aj Wu et al. 2022, 2023a c). Watermarking emerges as pivotal technique in
this context. It ensures the authenticity and ownership of digital media, and also can help people to
distinguish Al-generated content.
This paper presents new watermarking technique, SUTTERN-MARK, specifically designed for order-agnostic LMs. This advancement addresses the critical challenge of embedding and detecting watermarks in LMs that do not generate content sequentially, such as those used in protein design and machine translation. The introduction of PATTERN- MARK could significantly enhance the security and integrity of generated content across various fields, fostering trust in Al Al-generated content and enabling robust detection of Al authorship. Such a watermarking approach is pivotal for regulatory compliance, intellectual property protection, and preventing the misuse of generative models, espe- cially in sensitive applications like medical research and international communication. Additionally, PATTERN- -MRK''s ' ability to maintain high generation quality while ensuring robust watermark detection contributes to the practical deployment of secure, order-agnostic LMs in commercial and research settings, promoting broader acceptance and integration of these advanced Al technologies.
17


Reviews:
[{"review_id": "4qq9hGW2YL", "reviewer": "Reviewer_h65u", "summary": "The paper presents a watermarking method tailored for order-agnostic language models (LMs), which generate content in a non-sequential manner. The approach utilizes a Markov-chain-based key sequence to embed identifiable patterns within the generated content, enabling effective watermarking. Additionally, a statistical, pattern-based detection algorithm is employed for watermark verification. The authors also introduce a dynamic programming algorithm that optimizes the detection process by reducing its time complexity, enhancing the method's practical efficiency.", "questions": "1. The authors should provide a detailed justification for why using an alternated vocabulary splitting strategy (the proposed method) offers advantages over a global vocabulary splitting approach (e.g., Unigram) in terms of output quality and watermark robustness in order-agnostic LMs, given that both methods are context-independent?\n2. In Table 4, what does the term \"attack strength ε\" represent in the context of the ChatGPT paraphrasing attack? Additionally, how is this attack strength controlled or quantified during the experiments?\n3. Could the authors clarify the mathematical meaning of \\( e^\\delta \\) in Equation (1)? \n4. The method is described as Markov-chain-based due to its key sequence generation process; however, the paper’s use of an alternating key sequence (e.g., a fixed pattern like \\( k_1, k_2, k_1, k_2 \\)) does not appear to leverage the stochastic properties of Markov chains. This seems potentially misleading, as the approach is more akin to an alternated 0/1 key sequence than a Markov-chain-based generation. \n5. The proposed method employs fixed vocabulary splitting, which resembles the Unigram approach and may be easier to detect. What justification do the authors provide for the detectability and resilience of the proposed watermark against adversarial attempts to identify or remove it?", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "1. The paper effectively addresses the challenge of watermarking order-agnostic language models (LMs) by introducing a Markov-chain-based key sequence approach that overcomes the limitations inherent in traditional sequential watermarking methods.\n2. The inclusion of a dynamic programming algorithm to optimize the detection process by significantly reduces the time complexity, thereby improving the practical feasibility of the proposed approach.\n3. The proposed method enhanced detection accuracy and robustness, as well as the LMs output quality, in comparison to baseline methods.", "weaknesses": "1. The reliance on an alternating key sequence pattern introduces a potential vulnerability, as it may be more easily detected and disrupted by adversaries. Should the specific pattern structure (e.g., alternating keys) be identified, adversaries could develop targeted strategies to either erase or replicate the watermark. Incorporating more complex or adaptive key sequence strategies could enhance the method's robustness against such targeted disruptions.\n2. The paper lacks a thorough discussion on why the proposed method, which utilizes alternating vocabulary splitting based on key sequences, outperforms global vocabulary splitting (e.g., the Unigram method) for watermarking order-agnostic LMs. Given that Unigram serves as a strong baseline, a detailed comparative analysis is needed to explain why the proposed approach achieves superior detection accuracy, robustness, and output quality despite both methods being context-independent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "YmCqabOtkw", "reviewer": "Reviewer_gkea", "summary": "This paper proposes a watermarking scheme for order-agnostic language models based on the proposed pattern-mark and hypothesis test. The method generates key sequences through a Markov-chain-based key generator, improves the probability of sampling from the sub-vocabulary corresponding to each key, and detects key sequences of specific patterns to calculate the false positive rate using hypothesis test. Compared with other watermarking methods, the method proposed in this paper shows superiority in protein generation and machine translation.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper is well-organized and well-written.\n2.\tThe discussion part of the paper provides a good explanation of the motivation for the method.", "weaknesses": "1.\tThe paper does not detail how the vocabulary set is divided. Splitting the vocabulary will inevitably affect the original probability distribution, resulting in a decrease in output quality. In addition, improper vocabulary segmentation may lead to grammatical errors in the generated sentences, such as incorrectly connecting the verb after the preposition. Is the part of speech considered when dividing the vocabulary?\n2.\tThe probability outputs of language models often exhibit high probabilities for certain tokens while other tokens have much smaller probabilities, sometimes approaching zero. Although the factor used in Equation (1) aims to increase the probabilities of tokens in the sub-vocabulary, this amplification factor does not seem sufficient to bridge the gap between low-probability and high-probability tokens. In other words, if the vocabulary segmentation is not reasonable, it may not effectively enhance the sampling probability for specific sub-vocabularies. Particularly, when there are many sub-vocabularies, they may consist entirely of low-probability tokens. Was the original probability output considered when segmenting the vocabulary?\n3.\tThe paper does not provide detailed explanations on how to obtain the set of target patterns. The target patterns should accurately reflect the characteristics of the specific key sequence.\n4.\tThe comparative experiments in the experimental part of the paper are insufficient. This paper only compares the methods of two papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "YdD1Av6u3L", "reviewer": "Reviewer_cxkP", "summary": "This paper proposes PATTERN-MARK, a watermarking method to label the output of order-agnostic language models (LMs). The authors developed a Markov-chain-based watermark generator to produce watermark key sequences, then assigned the keys one by one to the generated tokens to adjust their sampling probabilities. During detection, they first recover the key sequence from the suspected text and verify the watermark through hypothesis testing.", "questions": "For the translation task, how can we identify whether a given text is generated by order-agnostic LMs or sequential LMs? This is critical for accurate detection.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+） This paper is well-written and presents its ideas clearly.\n\n+）This paper focuses on watermarking order-agnostic LMs, which, to the best of my knowledge, has not been considered in the existing literature.\n\n+) This paper proposes an effective strategy to watermark order-agnostic LMs by embedding watermarks within the relationships between adjacent words.", "weaknesses": "-）I think the protein generation task is not suitable for experiments, as it may not be able to identify important unknown protein architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "1KIM6Styf6", "reviewer": "Reviewer_4ffB", "summary": "This paper proposes a method for generating and detecting watermarks in ordered-agnostic language models (LMs). At a high level, the method is an extension of the red-green list approach in which the vocabulary is divided into two sets: the \"green\" list and the \"red\" list. The detector counts the number of tokens in the green list as a statistic for detection. The current method takes a more sophisticated approach to generating patterns in the key sequence by utilizing a Markov model during the text generation process. Detection is based on the number of patterns that appear in the key sequence, which are reconstructed from the text and the vocabulary partitions. The authors demonstrate that this method is more effective in terms of detectability and text quality than other existing watermarking schemes.", "questions": "1. My main question is why the Markov model is suitable for order-agnostic language models (LMs). Order-agnostic LMs do not generate tokens from left to right, while Markov models create sequences in a left-to-right manner. This presents a discrepancy between the order-agnostic nature of the LMs and the order-dependent nature of Markov models. It is unclear why Markov models would be particularly appropriate for order-agnostic LMs. Additionally, the discussions in Section 3.2, central to the proposed procedure, are vague and require more careful explanations. \n\n2. The discussion regarding why distortion-free watermarking schemes cannot be adapted to order-agnostic LMs is misleading. For instance, on page 3, line 196, it states, “A distortion-free watermark requires independent probabilities…” The term “independent probabilities” is unclear in this context. Distortion-free refers to $P_W(x_n|\\mathbf{x}_n^{oa},k_n) = P_M(x_n|\\mathbf{x}_n^{oa},k_n)$. Additionally, the assertion that “The distortion-free property also requires non-repeating watermark keys during generation” lacks clarity. The authors should be cautious with such an impossibility claim, as it requires a proper justification.\n\n3. The Markov structure seems to introduce another factor (in addition to $\\delta$), which could cause the distribution of the watermarked language model to differ from that of the original model. I wonder if there is any way to quantify the distortion caused by the Markov model.\n\n4. A potential drawback of the current approach is its time complexity. Could the authors report the computational time compared to other methods?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper presents a thorough investigation of watermarking for order-agnostic language models, a topic that appears to be less explored in the existing literature. The proposed method introduces several new ideas, including using Markov models to generate more complex patterns, setting it apart from previous approaches. The new approach shows promising performance when compared to existing methods. Additionally, the authors have explored the impact of various parameters on the method's effectiveness.", "weaknesses": "The assertion that \"this is the first work to explore watermarking for order-agnostic language models\" is somewhat exaggerated. The same problem can be addressed using existing methods, even though they may not be specifically tailored for order-agnostic settings (e.g., Zhao et al., 2023). \n\nAdditionally, the proposed method is more computationally intensive compared to the red-green list approach. Furthermore, the Markov structure seems to introduce another factor (in addition to $\\delta$), which could cause the distribution of the watermarked language model to differ from that of the original model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)