A Watermark for Order-Agnostic Language Models

## Abstract

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.

## 1 Introduction

With the rapid advancement in language models’ capabilities and their increasing adoption, researchers and regulators have expressed growing concerns regarding their potential misuse in generating harmful content. Distinguishing between human-generated and AI-generated text has become a significant area of research. Statistical watermarking (Aaronson, ; Kirchenbauer et al., ; Christ et al., ; Zhao et al., ; Liu et al., ; Zhang et al., ; Huo et al., ; Chen et al., ) offers a promising solution for identifying text produced by sequential LLMs (Brown, ; Touvron et al., ). This technique embeds a covert statistical signal into the generated content using a pseudo-random generator, which can later be detected through a statistical hypothesis test.

Order-agnostic LMs, where content is not generated in a left-to-right sequence (see Figure 1), have promising applications in fields such as protein generation (Dauparas et al., ; Alamdari et al., ), machine translation (Ghazvininejad et al., ; Kasai et al., ; Huang et al., ), speech generation (Chen et al., ; Peng et al., ), and time series forecasting (Chen et al., ; Tang & Matteson, ). 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, a pattern-based watermarking framework for order-agnostic language models (LMs). Our approach consists of a Markov-chain-based watermark generator and a rigorous statistical, pattern-based detection algorithm. The intuition of using a Markov chain is in order to enable recovery during detection, the pseudo-randomness 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 a Markov chain to generate a key sequence of length $n$, which is equal to the output content length. Each generated key is then used as a random seed to modify the output distribution at the corresponding time step. This Markov-chain-based key sequence generation ensures a higher occurrence of certain key patterns compared to 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.

Figure: Figure 1: Sequentially decoding vs. Order-agnostic decoding. Sequentially decoded text, follows a 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 is not consistently available in order-agnostic LMs.
Refer to caption: x1.png

Our contributions can be summarized as:

- •
We propose pattern-mark, a pattern-based watermarking framework specifically designed for order-agnostic LMs. Our approach introduces a novel Markov-chain-based key sequence generation method and a rigorous statistical pattern-based watermark detection technique. To the best of our knowledge, this is the first work to 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, ProteinMPNN (Dauparas et al., ) and CMLM (Ghazvininejad et al., ), we demonstrate the superiority of pattern-mark  in terms of detection efficiency, generation quality, and robustness compared to baseline methods.

## 2 Related work

Statistical watermarks.
Aaronson () proposed the first statistical watermarking algorithm via Gumbel sampling. Kirchenbauer et al. () 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. () 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. () introduced the unigram watermark, which enhances the robustness of statistical watermarking by leveraging one-gram hashing to generate watermark keys. Liu et al. () also contributed to the robustness of statistical watermarking by incorporating the semantics of the generated content as watermark keys. Liu et al. () proposed an unforgeable watermarking scheme that utilizes neural networks to modify token distributions. Christ et al. (); Kuditipudi et al. (); Hu et al. (); Wu et al. () focused on distortion-free watermarking, which aims to preserve the original language model distribution. We will demonstrate that achieving distortion-free watermarking in 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 to improve inference efficiency by generating multiple tokens simultaneously rather than sequentially. The pioneering work by Gu et al. () 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 et al. () further advanced order-agnostic LMs by introducing a masked language model that iteratively refines predictions.
Kasai et al. () 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. (); Peng et al. () adapted the non-autoregressive transformer to accelerate speech generation tasks, and Chen et al. (); Tang & Matteson () used spatial-temporal transformer and probabilistic-based transformer to improve the performance of time-series forecasting.

Moreover, in the recent seminal work, Dauparas et al. () proposed an order-agnostic language model for protein design. During generation, the decoding order is randomly 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 target sequence is known.

Figure: Figure 2: Illustration of pattern-mark. The watermark generation process begins with a Markov chain-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.
Refer to caption: x2.png

## 3 pattern-mark : A Pattern-based watermarking framework

### 3.1 Preliminary

Notations.
Let $V:=\{t_{1},\dots,t_{N}\}$ denote the vocabulary (or token) set of a language model, with $N=|V|$ representing its size. Define $\mathcal{V}$ as the set of all sequences, including those of length zero. We use $P_{M}$ to denote the distribution of a language model and $P_{W}$ to denote the distribution of the watermarked language model. A sequentially decoded language model generates a token sequence conditioned on a given prompt. At any step in this process, the probability of generating the next token $x_{n}\in V$, conditioned on the preceding tokens from $x_{1}$ to $x_{n-1}$, is denoted by $P_{M}(x_{n}\mid x_{1},x_{2},\dots,x_{n-1})$.
In order-agnostic LMs, the model does not have access to the full preceding sequence $\bm{x}_{1:n-1}$, but it may have access to tokens from other positions. Therefore, we use $\bm{x}^{oa}_{n}$ to 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 $x_{n}\in V$ for order-agnostic LMs is given by $P_{M}(x_{n}\mid\bm{x}_{n}^{oa})$. In our watermarking framework, we will have a key set $K$, and the set of all key sequences is denoted by $K^{*}$. We denote $\bm{k}[1:n]$ as a key sequence of length $n$.

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. A watermark framework primarily consists of two components: a 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, on the other hand, detects the presence of the watermark within the content using a statistical hypothesis test.

Discussion – Why current watermarking schemes can not be adapted to order-agnostic LMs. Most of the current watermarking schemes (Kirchenbauer et al., ; Liu et al., ; Huo et al., ) 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 it impossible to use previously generated content for watermark detection. For example, if we apply the Soft-watermark scheme (Kirchenbauer et al., ) 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 of these previous $i$ tokens may not yet be generated, resulting in missing or empty tokens. During detection, all previous $i$ 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-agnostic LMs is the Unigram (Zhao et al., ) (which is very similar to SelfHash Kirchenbauer et al. () without left tokens). However, Zhao et al. () uses a fixed red-green list to split the vocabulary and consistently promote the probability of green tokens, which will hurt the generation quality across the entire generation process.

Discussion – Why distortion-free watermarking schemes can not be adapted to order-agnostic LMs.
We claim that the current distortion-free scheme cannot be applied to order-agnostic LMs. There are two primary reasons for this: 1) The distortion-free property relies on the autoregressive nature of LMs. According to Christ et al. (); Hu et al. (); Wu et al. (), a distortion-free watermark requires independent probabilities $P_{W}(x_{n}|\bm{x}_{n}^{oa},k_{n})$ for every token $n$. However, some order-agnostic LMs are non-autoregressive. For example, $x_{n-1}$ and $x_{n}$ are generated simultaneously from a joint distribution $P_{W}(x_{n},x_{n-1}|\bm{x}_{n}^{oa},k_{n},k_{n-1})$. This makes it impossible to maintain independent $P_{W}(x_{n}|\bm{x}_{n}^{oa},k_{n})$ for each $n$. 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-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-gram during watermark detection.

Figure: Algorithm 1 pattern-mark generator

Figure: Algorithm 2 pattern-mark detector

### 3.2 Pattern-based watermarking framework

In this work, we propose a pattern-based watermarking framework, specifically designed for order-agnostic LMs (see Figure 2 for a detailed illustration). Given $l$ keys $K:=\{k_{1},k_{2},\dots,k_{l}\}$, we partition the vocabulary $V$ into $l$ distinct parts $V_{1},V_{2},\dots,V_{l}$, where each part corresponds to a unique key pattern. During the generation process, we first produce a sequence of keys $\bm{k}_{i_{1:n}}:=k_{i_{1}},k_{i_{2}},\dots,k_{i_{n}}$, where $n$ is the length of the generated content. When generating the $j$-th token, we will promote the probability of tokens within $V_{i_{j}}$. We follow the probability promotion strategy in Kirchenbauer et al. ().
Specifically, given an initial LM token probability $P_{M}(t)$ and a key $k_{i}$, the watermarked probability for the token, denoted by $P_{W}(t)$, is formulated as:

$$ $P_{W}(t|k_{i})=\left\{\begin{aligned} &\frac{e^{\delta}P_{M}(t)}{\sum_{t^{ \prime}\notin V_{i}}P_{M}(t^{\prime})+\sum_{t^{\prime}\in V_{i}}e^{\delta}P_{M }(t^{\prime})},\quad t\in V_{i}\\ &\frac{P_{M}(t)}{\sum_{t^{\prime}\notin V_{i}}P_{M}(t^{\prime})+\sum_{t^{ \prime}\in V_{i}}e^{\delta}P_{M}(t^{\prime})},\quad t\notin V_{i};\end{aligned }\right.$ (1) $$

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.

Figure: Algorithm 3 Compute pattern occurrence probability under the null hypothesis

Markov-chain-based key sequence generation.
During watermark detection, we do not have access to the entire key sequence used in watermarking. To address this, we propose a Markov-chain-based 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 a stochastic process that describes a sequence of events, where the probability of each event depends only on the state of the previous event. Given a transition matrix $A:=(a_{ij})_{l\times l}$, where $a_{ij}$ denotes the transition probability from state $k_{i}$ to $k_{j}$, we define the Markov-chain-based key sequence generation as follows:

###### Definition 3.1 (Markov-chain based key sequence generation) .

Let $X_{t}$ be the random variable representing the $t$-th position of the sequence, $A=(a_{ij})_{l\times l}$ the transition matrix, and $Q=(q_{1},...,q_{l})$ the initial probability. The key sequence is generated according to the rule $\Pr(X_{1}=k_{j})=q_{j}$ and $\Pr(X_{t+1}=k_{j}\mid X_{t}=k_{i})=a_{ij},t\geq 1$.

For example, if $l=2$ (i.e., we have two keys) and the transition matrix is $A=\begin{bmatrix}0.3&0.7\\
0.7&0.3\end{bmatrix}$, i.e., the next state has a probability of $0.3$ to remain the same and $0.7$ to switch to the other state. Then the number of patterns like $k_{1}k_{2}$ and $k_{2}k_{1}$ will be significantly higher than patterns like $k_{1}k_{1}$ and $k_{2}k_{2}$ in the generated Markov chain. This enables us to build a statistical detection algorithm based on the difference in the frequency of patterns between watermarked and non-watermarked content.

Besides, the self-transition probabilities $a_{11}$ and $a_{22}\in[0,1]$ (0.3 in the example above) control the frequency of patterns in the generated key sequences. When $a_{11}$ and $a_{22}$ increase, patterns $k_{1}k_{1}$ and $k_{2}k_{2}$ are more likely to appear in the generated key sequence. Conversely, when $a_{11}$ and $a_{22}$ decrease, we are more likely to observe patterns $k_{1}k_{2}$ and $k_{2}k_{1}$. Therefore, to improve detection efficiency, we typically select either extremely large or small values for $a_{11}$ and $a_{22}$. However, with large values of $a_{11}$ and $a_{22}$, the sequence may mainly consist of a single key, which could negatively impact generation quality. Hence, we generally select smaller values of $a_{11}$ and $a_{22}$ for key sequence generation.

Statistical pattern-based detection.
During watermark detection, we recover a key sequence from the generated content. We use a hypothesis test to conduct watermark detection, where the null hypothesis $H_{0}$ states that the text is not watermarked with pattern-mark. Under the null hypothesis, the recovered key sequence should follow a Markov chain with uniform transition probabilities (i.e., $A=(a_{ij}=1/l)_{l\times l}$).

Given a set of patterns $T\subset K^{m}$, let $S_{T}(\bm{k}):=\sum_{j=1}^{n-m+1}\bm{1}_{\bm{k}[j:j+m-1]\in T}$, which represents the number of selected patterns in $T$ that appear in the key sequence $\bm{k}\in K^{n}$. We can compute its probability density function $P_{T,n}(i):=\Pr(S_{T}(\bm{k})=i)$, where $\bm{k}$ is a random key sequence selected from $K^{n}$. Given an observed pattern count $c$, the p-value (false positive rate, a.k.a. FPR) for this hypothesis test is $\sum_{i=c}^{\infty}P_{T,n}(i)$. The detailed algorithms for watermark generation and detection are provided in Alg. 1 and Alg. 2. In Alg. 3, we provide the algorithm we used to calculate the probability density function $P_{T,n}$.

###### Definition 3.1 (Markov-chain based key sequence generation) .

### 3.3 P T , n subscript 𝑃 𝑇 𝑛 P_{T,n} italic_P start_POSTSUBSCRIPT italic_T , italic_n end_POSTSUBSCRIPT calculation.

In this part, we provide a detailed analysis and explanation of the algorithm (Alg. 3) designed to compute the probability distribution of pattern occurrences in sequences generated by a Markov chain. The algorithm calculates the probability $P_{T,n}(c)$ that a set of target patterns $T\subseteq K^{m}$ occurs exactly $c$ times in a 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\subseteq K^{m}$.

State Representation.
At each position $i$ in the sequence, the algorithm maintains a probability distribution over states. $C\in\{0,\dots,n-m+1\}$: The number of occurrences of the target patterns so far. $\bm{S}\in K^{m-1}$: The last $m-1$ keys in the current sequence. The state probability distribution at position $i$ is denoted as $P_{i}(C=c,\bm{S}=\bm{s}):=\Pr(S_{T}(\bm{k}[1:i])=c,\bm{k}[i-m+2:i]=\bm{s})$, where $\bm{k}$ is a random key sequence.

Initialization.
The algorithm initializes the state probabilities with
$P_{i}(C=c,\bm{S}=\bm{s})=0,\quad\forall i,c,\bm{s}$, and $P_{m-1}(C=0,\bm{S}=\bm{s})=(\frac{1}{l})^{m-1},\forall\bm{s}=[s_{1},...,s_{m-1
}]\in K^{m-1}$. Here, $P_{m-1}(C=0,\bm{S}=\bm{s})$ represents the probability of starting with sequence $\bm{s}$ without any occurrences of the target patterns.

Dynamic programming iteration.
For each position $i$ from $m$ to $n$ and each possible sequence $\bm{s}=[s_{1},s_{2},\dots,s_{m-1}]\in K^{m-1}$, the algorithm updates the state probabilities through the following step:
Construct the previous sequence $\bm{s}^{\prime}$ by shifting $\bm{s}$ left and adding a new key $k\in K$:
$\bm{s}^{\prime}=[k,s_{1},s_{2},\dots,s_{m-2}]$.
Case 1: If $[\bm{s}^{\prime},s_{m-1}]\notin T$ (no new occurrence of a target pattern), update for $c=0$ to $i-m$:
$P_{i}(C=c,\bm{S}=\bm{s})+=\frac{1}{l}P_{i-1}(C=c,\bm{S}=\bm{s}^{\prime})$.
Case 2: If $[\bm{s}^{\prime},s_{m-1}]\in T$ (new occurrence of a target pattern), update for $c=1$ to $i-m+1$:
$P_{i}(C=c,\bm{S}=\bm{s})+=\frac{1}{l}P_{i-1}(C=c-1,\bm{S}=\bm{s}^{\prime})$.

Final Probability Computation.
After completing the iterations up to position $n$, the total probability for each count $c$ is calculated by summing over all possible sequences $\bm{S}$: $P_{T,n}(c)=\sum_{\bm{s}\in K^{m-1}}P_{n}(C=c,\bm{S}=\bm{s})$. The time complexity of this algorithm is $O(n^{2}l^{m})$ and the memory complexity is $O(n^{2}l^{m-1})$.

**Table 1: Empirical true positive rate (TPR) for watermark detection on 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. A more detailed comparison can be found in Table 5.**
| Protein generation | pLDDT | TPR@FPR= |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| 10% | 1% | 0.1% | 0.01% | 0.001% |  |  |
| No Watermark | 85.46 | - | - | - | - | - |
| Soft watermark($\delta=1.50$) | 84.30 | 12.99 | 2.68 | 0.80 | 0.13 | 0.00 |
| Multikey($\delta=1.50$) | 84.20 | 67.20 | 33.87 | 14.32 | 6.96 | 2.68 |
| Unigram($\delta=1.50$) | 83.58 | 96.12 | 92.10 | 85.14 | 77.51 | 69.75 |
| pattern-mark($\delta=0.50$) | 85.42 | 47.26 | 17.94 | 6.29 | 2.54 | 0.67 |
| pattern-mark($\delta=0.75$) | 85.05 | 81.79 | 51.00 | 30.66 | 17.80 | 9.37 |
| pattern-mark($\delta=1.00$) | 84.74 | 97.46 | 88.35 | 68.27 | 50.87 | 38.02 |
| pattern-mark($\delta=1.25$) | 84.50 | 99.87 | 98.80 | 96.12 | 87.28 | 77.24 |
| pattern-mark($\delta=1.50$) | 84.02 | 100.00 | 100.00 | 99.87 | 99.06 | 96.39 |

**Table 2: Empirical true 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. A more detailed comparison can be found in Table 6.**
| Machine translation | BLEU | TPR@FPR= |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| 10% | 1% | 0.1% | 0.01% | 0.001% |  |  |
| No Watermark | 32.85 | - | - | - | - | - |
| Soft watermark($\delta=5$) | 25.58 | 97.91 | 85.04 | 60.22 | 36.89 | 20.44 |
| Multikey($\delta=5$) | 27.82 | 89.93 | 60.52 | 32.00 | 13.66 | 5.38 |
| Unigram($\delta=5$) | 22.23 | 99.90 | 99.20 | 95.41 | 88.53 | 78.07 |
| pattern-mark($\delta=1$) | 33.02 | 19.74 | 4.59 | 0.50 | 0.10 | 0.00 |
| pattern-mark($\delta=2$) | 32.60 | 57.33 | 28.41 | 13.96 | 8.47 | 4.39 |
| pattern-mark($\delta=3$) | 31.67 | 86.04 | 65.70 | 46.86 | 33.30 | 24.73 |
| pattern-mark($\delta=4$) | 29.43 | 98.21 | 89.53 | 79.16 | 67.00 | 56.83 |
| pattern-mark($\delta=5$) | 24.23 | 100.00 | 99.80 | 98.01 | 95.41 | 91.13 |

Figure: Figure 3: Comparison of the trade-off between TPR and generalization quality on protein generation and machine translation tasks. Left. TPR@FPR=0.1% vs. pLDDT on protein generation task. Right. TPR@FPR=0.1% vs. BLEU on machine translation task.
Refer to caption: x3.png

## 4 Experiments

Our experimental section consists of 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-mark. In the third part, we assess the robustness of the pattern-mark when subjected to random token modification and paraphrasing attacks. We focus on two seq2seq tasks in our experiments: machine translation with CMLM model (Ghazvininejad et al., ), and protein generation with ProteinMPNN (Dauparas et al., ).

### 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 order-agnostic LMs, we mainly compare pattern-mark with three baseline methods adapted from existing approaches: the Soft watermark Kirchenbauer et al. (), Unigram Zhao et al. (), and Multikey watermark Kirchenbauer et al. (). We mainly use three metrics to measure the quality of the generated content. Specifically, we use pLDDT (Jumper et al., ) and protein diversity to measure the quality of the protein generation task, and BLEU (Papineni et al., ) to measure the quality of the machine translation task.

Watermark settings. In pattern-mark, we select the key set $K=\{k_{1},k_{2}\}$, the Markov-chain transition matrix
$A=[[0,1],[1,0]]$,
and the initial distribution $Q=[0.5,0.5]$. The key patterns are defined as $T=\{k_{1}k_{2}k_{1}\ldots,k_{2}k_{1}k_{2}\ldots\}$, where $k_{1}$ and $k_{2}$ appear alternately, $T\subset K^{m}$. Under this configuration, the probability $P_{T,n}$ can be calculated with Algorithm 4, which optimizes the process described in Algorithm 3. The computational complexity is reduced from $O(n^{2}2^{m})$ to $O(n^{2}m)$.

### 4.2 Detection efficiency

We evaluate the detectability of our watermark on 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 $\delta\in\{0.5,0.75,1.0,1.25,1.5\}$ for protein generation task, and $\delta\in\{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%, 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 1 and Table 2. As shown, under the same probability promotion level $\delta$, our method consistently outperforms the baseline methods. Additionally, we include the average pLDDT and BLEU scores in Table 1 and Table 2. When $\delta=1.25$, pattern-mark surpasses all baselines in both generation quality and detectability in the protein generation task. Moreover, when $\delta=4$, pattern-mark outperforms the Soft watermark in both generation quality and detectability in the machine translation task, and at $\delta=5$, pattern-mark surpasses the Unigram method on both metrics for the same task.

**Table 3: Empirical true positive rate of different watermarks under random token modification with attack strength $\epsilon$ on protein generation task. Each row is averaged over around 800 generated protein sequences. We report TPR under 0.1% FPR.**
| Protein generation | ${\epsilon}=0$ | ${\epsilon}=0.05$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ |
| --- | --- | --- | --- | --- | --- |
| Soft watermark($\delta=1.50$) | 0.80 | 0.54 | 0.27 | 0.13 | 0.00 |
| Multikey($\delta=1.50$) | 14.32 | 10.84 | 9.24 | 5.22 | 2.01 |
| Unigram($\delta=1.50$) | 85.14 | 82.73 | 78.05 | 68.41 | 54.08 |
| pattern-mark($\delta=0.50$) | 6.29 | 5.09 | 4.02 | 2.14 | 1.07 |
| pattern-mark($\delta=0.75$) | 30.66 | 24.63 | 19.01 | 11.24 | 5.22 |
| pattern-mark($\delta=1.00$) | 68.27 | 60.78 | 51.41 | 31.46 | 16.73 |
| pattern-mark($\delta=1.25$) | 96.12 | 90.09 | 83.13 | 64.79 | 39.63 |
| pattern-mark($\delta=1.50$) | 99.87 | 98.66 | 97.05 | 87.82 | 65.73 |

**Table 4: Empirical true positive rate of different watermarks under ChatGPT paraphrasing attack with attack strength $\epsilon$ on machine translation task. Each row is averaged over around 1000 generated sequences. We report TPR under 0.1% FPR.**
| Machine translation | ${\epsilon}=0$ | ${\epsilon}=0.05$ | ${\epsilon}=0.1$ | ${\epsilon}=0.2$ | ${\epsilon}=0.3$ |
| --- | --- | --- | --- | --- | --- |
| Soft watermark($\delta=5$) | 60.22 | 48.26 | 38.38 | 28.22 | 19.04 |
| Multikey($\delta=5$) | 32.00 | 19.74 | 13.76 | 8.67 | 4.99 |
| unigram($\delta=5$) | 95.41 | 90.03 | 87.14 | 77.27 | 64.01 |
| pattern-mark($\delta=1$) | 0.50 | 0.80 | 0.50 | 0.30 | 0.40 |
| pattern-mark($\delta=2$) | 13.96 | 13.26 | 11.57 | 9.97 | 7.38 |
| pattern-mark($\delta=3$) | 46.86 | 42.47 | 38.88 | 34.20 | 29.41 |
| pattern-mark($\delta=4$) | 79.16 | 74.68 | 72.58 | 64.81 | 58.13 |
| pattern-mark($\delta=5$) | 98.01 | 97.10 | 95.81 | 93.32 | 89.53 |

### 4.3 Quality-Detectability 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, we utilize pLDDT as a quality metric, while for the machine translation task, we employ the BLEU score. We also made additional quality comparisons in Appendix C.1.

Figure 3 illustrates the trade-off between watermark detectability and generalization quality across both tasks. Each point in the figure corresponds to an experiment with a specific $\delta$, where the values of $\delta$ 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-mark against the baselines on both the protein generation and machine translation tasks. For the protein generation task, we employ a random token modification attack, while for the machine translation task, we use a paraphrase attack generated via ChatGPT. Unfortunately, we are unable to evaluate paraphrase attacks on protein generation due to the absence of a suitable rephrasing model. To perform the robustness experiment, we reuse the generated content from Sec. 4.2.
The results of these experiments are presented in Table 3 and Table 4. From these tables, it is evident that pattern-mark consistently outperforms the baselines across both tasks.

### 4.5 Ablation study

We present an ablation study to 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-mark 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 is achieved with $m=4$.

Generally, increasing the pattern length $m$ leads to improved detection efficiency to some extent. This improvement can be attributed to that longer patterns are less likely to appear in a 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.

Figure: Figure 4: Evaluation of the effect of pattern length $m$ on the detection efficiency of pattern-mark. Left. Protein generation task. Right. Machine translation task.
Refer to caption: x5.png

Figure: 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.
Refer to caption: x7.png

Transition matrix. We evaluated the quality of content generated using various configurations of the transition matrix $A=\begin{bmatrix}a_{11}&1-a_{11}\\
1-a_{11}&a_{11}\end{bmatrix}$. According to Figure 5, the quality of the generated content remains consistent across different values of $a_{11}$. Consequently, we select $a_{11}=0$, which corresponds to the strongest watermarking signal, as it does not compromise the quality while enhancing the watermark’s detectability.

## 5 Conclusion

In conclusion, pattern-mark presents a significant advancement in language model watermarking, specifically addressing the challenges posed by watermarking order-agnostic LMs. By innovatively leveraging a Markov-chain-based key sequence generation and a 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 ProteinMPNN and CMLM, pattern-mark has proven to be superior in terms of detection accuracy and reliability compared to traditional watermarking techniques, providing a novel approach for watermarking the order-agnostic LMs.

## Appendix A Algorithms for calculating pattern occurrence probability

In Alg. 4, we show the exact algorithm we used for calculating the pattern occurrence probabilities.

Figure: Algorithm 4 Compute pattern occurrence probability under the null hypothesis

## Appendix B Experimental Settings

Baseline. Since there are generally no watermarking methods specifically designed for order-agnostic LMs, we mainly compare pattern-mark with three baseline methods adapted from existing approaches: the Soft watermark Kirchenbauer et al. (), Unigram Zhao et al. (), and Multikey watermark Kirchenbauer et al. (). For Unigram, we adhere to the configurations as originally specified in the literature. In the case of the Soft watermark, we utilize 1-gram tokens as watermark keys. When this 1-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 n-gram watermark keys with two predetermined keys, randomly selecting one to seed the watermarking process at each generation step.

Metrics.
We mainly use three metrics to measure the quality of the generated content. Specifically, we use pLDDT and protein diversity to measure the quality of the protein generation task, and BLEU to measure the quality of the machine translation task.

- •
pLDDT. The pLDDT (Jumper et al., ) metric is a 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.
- •
Protein diversity. Protein diversity is an entropy-based 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., ) 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 et al., ) and CMLM (Ghazvininejad et al., ). ProteinMPNN is specifically developed for protein redesign tasks, requiring the generation of a protein sequence from a 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 an 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 are identified for regeneration in subsequent steps. For the CMLM, we apply it to a Romanian-English translation task using the available pre-trained checkpoint.

Dataset.
For CMLM, we use the data collected from news crawl(^1^11https://data.statmt.org/news-crawl/) news.2015.ro.shuffled whose length is larger than 128 to encourage longer generation. The filtered dataset has 1003 samples.

For ProteinMPNN, we use the protein features from PCSB Protein Data Bank(^2^22https://www.rcsb.org/), which is published from 2020 Jan. 1st to 2023 Dec. 31st. We limit the number of polymer residues per deposited model to between 400 and 500. The filtered dataset has 747 samples.

In pattern-mark, we select the key set $K=\{k_{1},k_{2}\}$, the Markov-chain transition matrix $A=\begin{bmatrix}0&1\\
1&0\end{bmatrix}$, and the initial distribution $Q=[0.5,0.5]$. The key patterns are defined as $T=\{k_{1}k_{2}k_{1}\ldots,k_{2}k_{1}k_{2}\ldots\}$, where $k_{1}$ and $k_{2}$ appear alternately, $T\subset K^{m}$. Under this configuration, the probability $P_{T,n}$ can be calculated using Algorithm 4, which optimizes the process described in Algorithm 3. The computational complexity of Algorithm 4 is $O(n^{2}m)$, compared to $O(n^{2}2^{m})$ for Algorithm 3.

In Section 4.5, we present an ablation study to evaluate the effects of different transition matrices $A$ and various lengths of key patterns $m$ on detection accuracy.

## Appendix C Additional Experiments

In this part, we show additional experiments about the detection efficiency comparison between pattern-mark and baselines on protein generation and machine translation tasks.
We select $\delta\in\{0.5,0.75,1.0,1.25,1.5\}$ for protein generation task, and $\delta\in\{1,2,3,4,5\}$ for machine translation task.

The results are presented in Table 5 and Table 6. As shown, under the same probability promotion level $\delta$, our method consistently outperforms the baseline methods.

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

### C.1 Quality evaluation

We compare the performance of our method across two tasks: for the protein generation task, we utilize pLDDT as a quality metric and protein diversity as a 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.

In Figure 6 and Table 7, we compare the quality of protein generation between pattern-mark and the non-watermarked model. It is evident that under the same $\delta$, our method consistently produces proteins of high quality and diversity.

Figure: Figure 6: Comparison of the pLDDT of the protein generated from pattern-mark with the non-watermarked model.
Refer to caption: x9.png

**Table 7: 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($\delta=1.50$) | 4.024 | 7.828 | 11.554 |
| Multikey($\delta=1.50$) | 4.034 | 7.912 | 11.700 |
| Unigram($\delta=1.50$) | 3.934 | 7.708 | 11.371 |
| pattern-mark($\delta=1.50$) | 4.105 | 7.998 | 11.763 |

## Appendix D Broader Impact Statement

Machine learning models have profound impacts across various domains, demonstrating significant potential in both enhancing efficiencies and addressing complex challenges
(Yang et al., ; ; Wen et al., ; Chakraborty et al., ; Cai et al., ; Chen et al., ; Xu & Li, ; Liu et al., ; Wen et al., )
However, alongside these positive impacts, there are concerns about the integrity and security of machine learning applications (Hong et al., ; Hu et al., ; Wang et al., ; ; Wu et al., ; ; ). Watermarking emerges as a pivotal technique in this context. It ensures the authenticity and ownership of digital media, and also can help people to distinguish AI-generated content.

This paper presents a new watermarking technique, pattern-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 AI-generated content and enabling robust detection of AI authorship. Such a watermarking approach is pivotal for regulatory compliance, intellectual property protection, and preventing the misuse of generative models, especially in sensitive applications like medical research and international communication. Additionally, pattern-mark’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 AI technologies.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 5
presentation: 2
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?
2. 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?
3. Could the authors clarify the mathematical meaning of \( e^\delta \) in Equation (1)? 
4. 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. 
5. 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?
soundness: 3
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.
2. 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.
3. The proposed method enhanced detection accuracy and robustness, as well as the LMs output quality, in comparison to baseline methods.
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.
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.
2. 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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: NA
soundness: 2
strengths: 1.	This paper is well-organized and well-written.
2.	The discussion part of the paper provides a good explanation of the motivation for the method.
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.
weaknesses: 1.	The 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?
2.	The 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?
3.	The 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.
4.	The comparative experiments in the experimental part of the paper are insufficient. This paper only compares the methods of two papers.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
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.
soundness: 3
strengths: +） This paper is well-written and presents its ideas clearly.

+）This paper focuses on watermarking order-agnostic LMs, which, to the best of my knowledge, has not been considered in the existing literature.

+) This paper proposes an effective strategy to watermark order-agnostic LMs by embedding watermarks within the relationships between adjacent words.
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.
weaknesses: -）I think the protein generation task is not suitable for experiments, as it may not be able to identify important unknown protein architectures.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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. 

2. 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.

3. 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.

4. A potential drawback of the current approach is its time complexity. Could the authors report the computational time compared to other methods?
soundness: 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.
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.
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). 

Additionally, 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.

Meta-review: This paper proposes a watermark for order-agnostic LLMs. This was a borderline submission, with two reviewers suggesting "slightly above accept threshold" and two "slightly below". During the AC-reviewer discussion, we discussed the merits of the paper. The AC also read the paper and found that the issues raised by the reviewers are generally addressed in the work, including robustness to perturbations, improved performance compared to simple unigram methods, and improved security compared to baselines (random splits of the vocab appear to be more secure than fixed ones). Based on this, I can recommend acceptance.

Decision: Accept (Poster)