Universally Optimal Watermarking Schemes for LLMs: from Theory to Practice

3. Usage scenario of Theorem 2: We address the problem of identifying whether a sentence is generated by an LLM using watermarking. Thus, there is no restriction on the information to be embedded into the text, as long as it enables reliable watermark detection. In our problem setup, we propose a generic framework that can be specialized to any of the existing in-process watermarking schemes. The optimal solution to the generic framework turns out to be seemingly "naive" where the embedded information, i.e., the auxiliary sequence, is either a token index or a null message. However, for the sole purpose of determining whether a text is watermarked, decoding this embedded information is sufficient when the shared key is available.

4. Extension to robust watermarking against broad attacks: In Section 6, we show that this framework can be further generalized to the scenarios with semantic-invariant attacks. We prove the theoretical optimal and robust design, which also provides valuable insights into designing practical and robust semantic-based watermarking algorithms.

5. Clarification on the watermarking scheme with uniform $\zeta_1^T$: In Line 368, since the uniform distribution is not the optimal marginal $P_{\zeta_1^T}^*$, there exists a theoretical detection performance loss, as we have discussed in Appendix E. Our experimental explorations confirm that the loss is non-negligible in practice, as demonstrated by a detection performance of only 0.602 TPR@1% FPR when using Llama2-13B—a result significantly lower than that achieved by our current algorithm. That is why we propose the practical token-level optimal watermarking scheme by allowing the sampling distribution of $\zeta_t$ to adapt to NTP distributions in Sections 4 and 5.

6. Impact of surrogate language model (SLM): To investigate the impact of the approximate distribution from the surrogate SLM on our detection performance, we conducted experiments to compare detection performance with and without prompts attached to the watermarked text during the detection process. Moreover, we conducted experiments using both the original watermarking LLM and prompts during the detection process to evaluate detection performance under conditions where we could precisely reconstruct $P_{\zeta}$. These experiments were performed using LLama2-13B on the C4 dataset, both with and without adversarial attacks. The sampling temperature is set to $0.8$. The results are presented in the following tables. Notably, even when prompts are absent and the surrogate model cannot perfectly reconstruct the same $P_{\zeta}$​ as in the generation process, detection performance remains unaffected. This demonstrates the robustness of our watermarking method, regardless of whether a prompt is included during the detection phase. As discussed in our manuscript, being prompt- and model-agnostic is a highly practical and valuable property of a watermarking method. The observed detection performance loss of approximately $0.1$% to achieve this agnostic capability is minimal and represents a worthwhile trade-off for improved practicality.

Without attack:

With token replacement attack:

We thank the reviewer for the insightful comments. We have addressed all the concerns as follows and made corresponding edits (highlighted in blue) in the revised manuscript.

To-W1&Q1. Is this watermarking?

We would like to address this question from the following aspects. Additionally, there seems to be an incomplete sentence at the end of W1, and we kindly request the reviewer to provide some clarification.

1. Problem setup: Distinct from traditional post-process watermarking schemes that embed watermarks after text generation, we explore in-process watermarking that embeds watermarks during generation. To make full use of LLMs, this embedding process evolves from a functional operation to modifying the next-token prediction (NTP) distribution using auxiliary random variables (i.e., the watermark information). In this procedure, given a LLM (i.e., $Q_{X_1^T}$), we have degrees of freedom in designing (1) the joint distribution $P_{X_1^T, \zeta_1^T}$ (including $P_{X_1^T}$, $P_{\zeta_1^T}$ and $P_{X_1^T|\zeta_1^T}$), and (2) the detector. This framework deviates from the classical settings where the embedded auxiliary sequence $\zeta_1^T$ is fixed or sampled from a fixed distribution. It also differs from existing in-process watermarking schemes, which assume a fixed uniform distribution $P_{\zeta_1^T}$ and fail to fully leverage the capabilities of the LLM. By harnessing the flexibility of our framework, we derive watermarking schemes that adapt to the original LLM $Q_{X_1^T}$, optimizing the tradeoff between detection accuracy, text quality, and robustness.

   To clarify that our framework does not break the causality between $X_1^T$ and $\zeta_1^T$, we modify Figure 1 to better illustrate the generic framework for LLM watermarking and detection: https://anonymous.4open.science/r/ICLR_rebuttal-5581/watermark_framework.pdf. At each position $t$, the auxiliary variable $\zeta_t$ is sampled from a designed distribution using a shared secret $\mathsf{key}$, which is usually but not necessarily dependent on the previous tokens and prompt. The token $X_t$ is then sampled from the watermarked NTP distribution $P_{X_t|x_1^{t-1},\zeta_t}$. Thus, the watermarking process maintains the causal relationship between the watermark and the text. In the end, we obtain a pair of dependent sequences $(X_1^T,\zeta_1^T)$ that follows the joint distribution $P_{X_1^T,\zeta_1^T}$, which actually characterizes the entire watermark generation process. On the detector side, it only receives the text $X_1^T$ and the shared $\mathsf{key}$, which can be used to recover the auxiliary sequence $\zeta_1^T$. In theory, our goal is to jointly optimize $P_{X_1^T,\zeta_1^T}$ and the detector $\gamma$ that minimizes the Type-II error under the constraint of worst-case Type-I error.

2. Practical implications: The main contribution of the theoretically optimal results is to provide valuable guidelines for designing near-optimal and implementable algorithms. Note that this is a more systematic approach compared to existing heuristic designs. In Theorem 2, we prove that the optimal watermarking scheme $P_{X_1^T, \zeta_1^T}^*$ should adapt to the LLM $Q$. This result explains why other approaches, such as green/red list watermarking and Gumbel-Max watermarking, which sample $\zeta_t$ from a fixed distribution, are suboptimal. Building on this theoretical result, we design algorithms that address two practical concerns: adapting to variable-length text generation and recovering the auxiliary sequences at the model-agnostic detector side. In Section 4, we propose a token-level optimal detector and watermarking scheme based on our sequence-level optimal result. This approach effectively adapts to variable-length text generation while maintaining strong performance guarantees. In Section 5, we propose decomposing the sampling procedure of the auxiliary sequence $\zeta_t$ using the Gumbel-max trick, enabling the Gumbel noise (generated from fixed distribution) to be shared with the detector via a secret key. For watermark detection, a surrogate language model (SLM) is used to approximate the NTP distribution $Q$, and combined with the Gumbel-max trick to extract $\zeta_1^T$ from the text (illustrated in https://anonymous.4open.science/r/ICLR_rebuttal-5581/watermark_practice.pdf). Guided by the theoretical framework, experimental results show that our algorithm achieves excellent detection performance and robustness, even with the approximated auxiliary sequence $\zeta_1^T$.

   Therefore, we believe that the proposed theoretical framework and the derived optimality are useful and insightful in practice.

W4. Minor comments

• line 107: We thank the reviewer for guiding us to the references. We have added the citations in "Other Related Literature". Merhav and Sabbag (2008) consider the text sequence $X_1^T$ is generated i.i.d. from a known distribution $P_X$ and the watermark embedder (i.e., watermarking scheme) is a function of $X_1^T$ and $\zeta_1^T$. They consider the cases where $\zeta_1^T$ is fixed or independently generated from a fixed distribution. By considering a given set of test statistics, they derive the asymptotically optimal detector and watermark embedder. Merhav and Ordentlich (2006) consider adopting causal codes for joint lossy source coding and watermark embedding. The encoder takes input as the previously generated symbols and watermarks and varies with time. The compressed watermark variable is uniformly distributed on $\{0,1\}^r$ for some constant $r$. They explore the tradeoffs among the distortion between the watermarked text and the original text, the text compression rate, and the watermark compression rate.

  Both papers offer valuable insights that can inform future extensions of our work.

• line 136: Since the unwatermarked-LLM-generated text is barely distinguishable from the human-generated one. In Section 2 above Figure 1, we state that we assume that the unwatermarked LLM distribution $Q$ is identical to that of humans. In the detection phase, the detector is model-agnostic, and $Q$ is unknown to the detector under both hypotheses. The unwatermarked LLM distribution $Q$ is only available in the watermark generation phase.

• line 404: Thank you. We have corrected the typo.

• Alg 2. line 3,4: Thank you. We have corrected the notation.

• line 809: We thank you for your meticulous reading. We have corrected the typo. Yes the TV is defined as $\mathsf{D}_\mathsf{TV}(\mu,\nu)\coloneqq\int \frac{1}{2}| \frac{d \mu}{ d \nu}-1| d \nu$

• line 831, line 885: Sorry for some typos in the proof. In line 831, this is part of the proof for Example 2, where we aim to show an example of suboptimal detector $\gamma(X_1^T,\zeta_1^T)= \mathbf{1}\lbrace f(X_1^T)=\zeta_1^T \rbrace$, for some surjective function $f:\mathcal{V}^T \to \mathcal{S}$ and $\mathcal{S}\subseteq \mathcal{Z}^T$. However, in line 885, this is part of the proof for Theorem 2 which presents the optimal type detectors and watermarking schemes. The optimal detector takes the form $\gamma(X_1^T,\zeta_1^T)= \mathbf{1} \lbrace X_1^T=g(\zeta_1^T) \rbrace$ for some surjective function $g: \mathcal{Z}^T \to \mathcal{S}$ and $\mathcal{S}\supset \mathcal{V}^T$. $\mathcal{S}$ is used for different purposes in the two proofs.

• line 1040: Right. The special case considers $\epsilon=0$.

• line 1056: Thank you. We have corrected the typo.

• line 1353: Thank you. Indeed, it is more consistent to use $P$ not $\tilde{Q}$. We have corrected the notation.

Q2. Efficient watermarking scheme

• line 399, 406, 411: Thank you for pointing out this confusion. We do not need to compute $h^{-1}$ in practice. Since the vocabulary is fixed, given a key and a $\zeta$, what we do is to search the vocabulary table to find the corresponding $x$ such that $h_{key}(x)=\zeta$.

  To demonstrate the efficiency of our watermarking method, we conducted experiments measuring the average generation time for both un-watermarked and watermarked text. For these experiments, we employed LLaMA2-13B and the C4 dataset, setting the text length to 200 tokens in both scenarios. The results, presented in the following table, indicate that the difference in generation time between un-watermarked and watermarked text is less than $0.5$ seconds. This minimal difference confirms that our watermarking method has a negligible impact on generation speed, ensuring practical applicability.

  Language Model	Watermark	Avg Generation Time/s
  Llama2-13B	Un-watermarked	9.110s
  Llama2-13B	Watermarked	9.386s

Q4. Technical detail

• line 777: Thanks for the question. We have added a detailed proof in the Appendix B:

$\sum_{x_1^T:P^\*_{X_1^T}(x_1^T)\geq \alpha}\epsilon^\*(x_1^T)$

$= \sum_{x_1^T:P^\*_{X_1^T}(x_1^T)\geq \alpha, \epsilon^\*(x_1^T) \geq 0}\epsilon^*(x_1^T)$

$+\underbrace{\sum_{x_1^T:P^*_{X_1^T}(x_1^T)\geq \alpha, \epsilon^*(x_1^T) \leq 0}\epsilon^\*(x_1^T)}_{\leq 0}$

$\leq \sum_{x_1^T:P^\*_{X_1^T}(x_1^T)\geq \alpha, \epsilon^*(x_1^T) \geq 0}\epsilon^\*(x_1^T)$

$=\sum_{x_1^T:P^*_{X_1^T}(x_1^T)\geq \alpha, Q_{X_1^T}(x_1^T)\geq P^*_{X_1^T}(x_1^T) }\epsilon^\*(x_1^T)$

$\leq \sum_{x_1^T:Q_{X_1^T}(x_1^T)\geq P^\*_{X_1^T}(x_1^T)}\epsilon^\*(x_1^T)\leq\epsilon$

To new Q2

We thank the reviewer for trying out our scheme. We kindly request your clarification or result about ``it just does not work at low FPR (below 10^-4)”.

We also thank you for referring us to the WaterMax paper, which we will add into the related works and consider comparisons with it in the future.

Our theoretical result presents an upper bound on the true FPR (cf. Lemma 3), which we acknowledge is not tight. However, by suitably setting the token-level false alarm $\eta$, we can effectively control this upper bound, which should consequently yield an even smaller true FPR on the sentence.

To new Q1

We acknowledge that our proposed framework differs from the classical watermarking paradigm, which relies on fixed watermarks or a fixed watermark distribution. However, we view this as a generalized watermarking framework—a “relaxation,” as you mentioned. This approach, particularly well-suited for large language models (LLMs), allows the watermark distribution to adapt dynamically to the LLM and enables detection through innovative methods, such as leveraging a surrogate language model.

From a theoretical perspective, we believe it is reasonable to assume that watermark variables can be recovered by the detector, as this assumption facilitates a focused exploration of the fundamental limits of watermarking. The primary challenge lies in the practical realization of such recovery, which we recognize as an important consideration but not a theoretical limitation.

While we respect and understand the reviewers’ perspective, we hope to keep our broader definition of watermarking, as it aligns with the goals and nuances of our framework.

Ok. I will raise my score. How will it be implemented in the revised paper?

We sincerely appreciate the reviewer’s insightful suggestions and the upgraded score. We will add the following clarifications in the revised manuscript:

• After line 60: “...jointly optimize both the watermarking scheme and the detector, achieving universal optimality. In contrast to the classical watermarking paradigm with fixed watermark messages or distributions, this study explores a broader definition of watermarking where watermarks can be dynamically adapted to the LLM and its output texts....”
• In the first point of our contribution summary: “...More importantly, within our framework, we characterize the complete class of universally optimal detectors and watermarking schemes, meaning no other type can achieve the same performance.”

We thank the reviewer for thoroughly reading our manuscript and providing constructive feedback. We have carefully considered the reviewer’s comments and provided the following responses.

W1. This method is a modification based on Gumbel-Max. The choice of the surrogate model may affect the effectiveness of the proposed watermarking method, which may limit the algorithm’s applicability.

1. Our watermarking method is fundamentally different from the Gumbel-Max watermarking approach. What we use is the Gumbel-Max trick, a method to draw a sample from a categorical distribution. As detailed in Algorithms 1 and 2, one important component of our optimal watermarking method is the construction of sampling distribution $P_{\zeta_t|x_1^{t-1}}$ of auxiliary $\zeta_t$ based on the original Next Token Prediction (NTP) distribution. After constructing $P_{\zeta_t|x_1^{t-1}}$, we sample $\zeta$ from it​ to watermark the next token. However, directly sending $\zeta$ from the generator to the detector is impractical due to its dependence on the NTP distribution. To address this challenge, we utilize a surrogate model and employ the Gumbel-Max trick to sample $\zeta$ from the approximated $P_{\zeta_t|x_1^{t-1}}$. Therefore, the Gumbel-Max trick is a way to help us sample the $\zeta_t$ during the detection process. In contrast, the Gumbel-Max watermark method directly samples the next token from the original NTP distribution using a Gumbel variable drawn from a uniform distribution. Furthermore, compared to the Gumbel-Max watermarking method, our approach is adaptive, leveraging the information from the original NTP distribution. We want to emphasize that the design of such an adaptive watermarking scheme is driven by our theoretical analysis of universally optimal watermarking, which is different from the existing heuristic watermarking designs.

2. The selection of the surrogate model is primarily based on its vocabulary or tokenizer rather than the specific language model within the same family. This choice is critical because, during detection, the text must be tokenized exactly using the same tokenizer as the watermarking model to ensure accurate token recovery. As a result, any language model that employs the same tokenizer can function effectively as the surrogate model.

   To validate our approach, we add a new experiment by applying our watermarking algorithm to GPT-J-6B (a model with 6 billion parameters) and using GPT-2 Large (774 million parameters) as the surrogate model. Despite differences in developers, training data, architecture, and training methods, these two models share the same tokenizer, making them compatible for this task. We conduct experiments using the C4 dataset, and the results are presented in the tables below. The results demonstrate the effectiveness of our proposed watermarking method with or without attack even when using a surrogate model from a different family than the watermarking language model. Notably, the surrogate model, despite having fewer parameters and lower overall capability compared to the watermarking language model, does not compromise the watermarking performance.

   Moreover, we believe that training a small surrogate model with fewer parameters is neither a particularly challenging nor a resource-intensive task for LLM developers. Techniques such as retraining or knowledge distillation can be employed to efficiently create such a model, making it a practical solution.

Without attack:

With token replacement attack:

Dear reviewer 3q3R,

We sincerely appreciate your time and effort in reviewing our submission and providing valuable suggestions. While we hope to have addressed your concerns adequately, we understand there may still be areas requiring further clarification or discussion. We are fully prepared to address your outstanding issues. Should our responses have successfully addressed all your questions, we would be deeply grateful if you could consider enhancing the score to further support our submission. Thank you very much for your thoughtful review.

Best Regards,

Paper12990 Authors

We thank the reviewer for providing additional constructive feedback. We have carefully considered the reviewer’s comments and provided the following responses. We are trying our best to solve the reviewer's problem, and we would greatly appreciate it if the reviewer could kindly reconsider the score to further support our work.

Q1. Do you have the prompt information for the results reported in Table 1 and Table 2?

During the watermark generation process, we use the first two sentences of each text in the dataset as a prompt. It is also stated in the “Experiment settings”.

During the watermark detection process, we don’t have access to the prompts.

Q2. Clarify how to get the perplexity results.

For the experiment setting, we conduct experiments on Llama2-13B. We set the temperature to be 0.8 for all methods. The perplexity is computed using GPT-3. Moreover, some prior works have shown that both Gumbel-Max and EXP-Edit exhibit higher perplexity compared to unwatermarked text, e.g. as shown in Table 4 of [1]. We kindly request the reviewer to share the references mentioned that present differing results.

[1] Leyi Pan, Aiwei Liu, Zhiwei He, Zitian Gao, Xuandong Zhao, Yijian Lu, Binglin Zhou, Shuliang Liu, Xuming Hu, Lijie Wen, et al. Markllm: An open-source toolkit for llm watermarking. arXiv preprint arXiv:2405.10051, 2024a.

Q3. BLEU score on machine translation task.

We conduct new experiments on the machine translation task. We use the WMT19 dataset and MBART Model. It can be observed that our scheme achieves a higher BLEU score than the baseline schemes and is close to the unwatermarked BLEU score.

Q4. Show the results with FPR=0.1%, 0.01% and 0.001%

We conduct new experiments on 100k sentences from the Wikipedia dataset. The following table shows that our watermarking scheme achieves higher TPR even when FPR $= 10^{-5}$.

Furthermore, we also compare the empirical FPR with the corresponding theoretical, which is presented in the following table.

This table above shows that our theoretical upper bound effectively controls the empirical FPR even when it is $<=10^{-4}$.

Dear reviewer 3q3R,

We sincerely appreciate your time and constructive feedback, which helps us further improve the quality of our submission. We have made every effort to answer your insightful questions by modifying the manuscript and writing rebuttals. Considering today (Dec 2) is the deadline for the author's response, we hope our responses have addressed the reviewer's concerns, but if not, we are available to address any outstanding issues. In case we have addressed all your questions, we truly appreciate your feedback and reconsider your score for further support.

Best Regards,

Paper12990 Authors

Q2. Compare the proposed method with robustness-enhanced algorithms such as SIR.

We conducted experiments using the SIR watermark and compared its detection performance and perplexity with our watermarking method, both with and without attack. The results of these comparisons are presented in the following tables. For detection performance without attack, our watermarking method is comparable to SIR. Under token replacement attacks, SIR demonstrates better robustness due to its design as a semantic-invariant watermark. Despite this advantage, SIR introduces biases in the next token prediction distributions, resulting in a relatively high perplexity. In contrast, our watermarking method is distortion-free, achieving significantly lower perplexity, which minimizes its impact on the generated text quality of the LLM.

Without attack

With token replacement attack

We thank the reviewer for thoroughly reading our manuscript and providing constructive feedback. We have carefully considered the reviewer’s comments and provided the following responses.

Q1. The significance of the proposed method is not sufficiently demonstrated in the paper.

1. Theoretical Contribution First of all, to better illustrate our proposed generic framework of watermarking LLM and watermark detection, which can be specialized to any existing in-process watermarking schemes, we improve our Figure 1 as follows: https://anonymous.4open.science/r/ICLR_rebuttal-5581/watermark_framework.pdf. This shows a more detailed and readable process of watermark generation and detection. Specifically, the LLM watermarking process can be exactly characterized by the joint distribution $P_{X_1^T, \zeta_1^T}$. Second, given this watermarking process, we observe that the detection problem boils down to the independence testing problem between the received text $X_1^T$ and the recovered auxiliary sequence $\zeta_1^T$ (i.e., watermark information). Within the hypothesis testing framework, we aim to jointly optimize the watermarking scheme, denoted by the joint distribution $P_{X_1^T, \zeta_1^T}$, and the model-agnostic detector $\gamma$ that minimizes the Type-II error (false negative) under the $\alpha$-constrained worst-case Type-I error (false positive). We formulate the optimization problem in (OPT-O). The optimal objective value is thus the universally minimum Type-II error, as the Type-I error is under control for all possible text distributions (Theorem 1). The optimizer identifies the optimal class of detector-watermarking scheme pairs. Additionally, we prove that detectors within this optimal class, denoted as $\Gamma^*$, are universally optimal. Specifically, for any detector $\gamma \notin \Gamma^*$, there always exists a text distribution $Q$ and a distortion level $\epsilon$ such that no watermarking scheme can achieve the universally minimum Type-II error. It suggests that to guarantee the construction of an optimal watermarking scheme for any arbitrary LLM, the detector must be selected from the set $\Gamma^*$.

2. Practical implications: The main contribution of the theoretically optimal results is to provide valuable guidelines for designing near-optimal and implementable algorithms. Note that this is a more systematic approach compared to existing heuristic designs. In Theorem 2, we prove that the optimal watermarking scheme $P_{X_1^T, \zeta_1^T}^*$ should adapt to the LLM $Q$. This result explains why other approaches, such as green/red list watermarking and Gumbel-Max watermarking, which sample $\zeta_t$ from a fixed distribution, are suboptimal. Building on this theoretical result, we design algorithms that address two practical concerns: adapting to variable-length text generation and recovering the auxiliary sequences at the model-agnostic detector side. In Section 4, we propose a token-level optimal detector and watermarking scheme based on our sequence-level optimal result. This approach effectively adapts to variable-length text generation while maintaining strong performance guarantees. In Section 5, we propose decomposing the sampling procedure of the auxiliary sequence $\zeta_t$ using the Gumbel-max trick, enabling the Gumbel noise (generated from fixed distribution) to be shared with the detector via a secret key. For watermark detection, a surrogate language model (SLM) is used to approximate the NTP distribution $Q$, and combined with the Gumbel-max trick to extract $\zeta_1^T$ from the text (illustrated in https://anonymous.4open.science/r/ICLR_rebuttal-5581/watermark_practice.pdf). Guided by the theoretical framework, experimental results show that our algorithm achieves excellent detection performance and robustness, even with the approximated auxiliary sequence $\zeta_1^T$.

Therefore, we believe that the proposed theoretical framework and the derived optimality are useful and insightful in practice.

3. Extension to robust watermarking against broad attacks: In Section 6, we show that this framework can be further generalized to the scenarios with semantic-invariant attacks. We prove the theoretical optimal and robust design, which also provides valuable insights into designing practical and robust semantic-based watermarking algorithms.

Dear reviewer BdQu,

We sincerely appreciate your time and effort in reviewing our submission and providing valuable suggestions. While we hope to have addressed your concerns adequately, we understand there may still be areas requiring further clarification or discussion. We are fully prepared to address your outstanding issues. Should our responses have successfully addressed all your questions, we would be deeply grateful if you could consider enhancing the score to further support our submission. Thank you very much for your thoughtful review.

Best Regards,

Paper12990 Authors

Dear reviewer BdQu,

We sincerely appreciate your time and constructive feedback, which helps us further improve the quality of our submission. We have made every effort to answer your insightful questions by modifying the manuscript and writing rebuttals. Considering today (Dec 2) is the deadline for the author's response, we hope our responses have addressed the reviewer's concerns, but if not, we are available to address any outstanding issues. In case we have addressed all your questions, we truly appreciate your feedback and reconsider your score for further support.

Best Regards,

Paper12990 Authors

Q6. The description of the Kuditipudi et al. watermarking scheme appears to be completely unrelated to the scheme presented in their paper. Their scheme is not hash-based at all.

Our proposed framework in Section 2 is generic for any in-process watermarking scheme. In the problem formulation, we do not assume that the hash function will be used during watermark generation and detection. The auxiliary sequence $\zeta_1^T$ can be sampled using arbitrary methods. Example 3 presents some existing watermarking schemes, which, to the best of our knowledge, may all be seen as special cases of this formulation. In Appendix A, we are sorry for the description error about Kuditipudi et al. watermarking scheme. We have corrected the error, and it still can be seen as a special case of this formulation.

The corrected version:

• In the inverse transform watermarking scheme \citep{kuditipudi2023robust}, the vocabulary $\mathcal{V}$ is considered as $[|\mathcal{V}|]$ and the combination of the uniform random variable and the randomly permuted index vector is the auxiliary variable $\zeta_t$.

• Use key as a seed to uniformly and independently sample $\lbrace U_t \rbrace_{t=1}^T$ from $[0,1]$, and $\lbrace \pi_t \rbrace_{t=1}^T$ from the space of permutations over $[|\mathcal{V}|]$. Let the auxiliary variable $\zeta_t=(U_t,\pi_t)$, for $t=1,2,\ldots,T$.

• Sample $X_t$ as follows

$X_t=\pi_t^{-1}(\min\{i\in[|\mathcal{V}|]: \sum_{x\in[|\mathcal{V}|]}(Q_{X_t|x_1^{t-1}}(x)\mathbb{1}\lbrace \pi_t(x)\leq i \rbrace \big) \geq U_t \}),$

where $\pi_t^{-1}$ denotes the inverse permutation.

We thank the reviewer for thoroughly reading our manuscript and providing constructive feedback. We have carefully considered the reviewer’s comments and provided the following responses.

Q1. Described formally, but without any equations, what precisely you are claiming about optimality.

First of all, to better illustrate our proposed generic framework of watermarking LLM and watermark detection, which can be specialized to any existing in-process watermarking schemes, we improve our Figure 1 as follows: https://anonymous.4open.science/r/ICLR_rebuttal-5581/watermark_framework.pdf. This shows a more detailed and readable process of watermark generation and detection. Specifically, the LLM watermarking process can be exactly characterized by the joint distribution $P_{X_1^T, \zeta_1^T}$.

Second, given this watermarking process, we observe that the detection problem boils down to the independence testing problem between the received text $X_1^T$ and the recovered auxiliary sequence $\zeta_1^T$ (i.e., watermark information). Within the hypothesis testing framework, we aim to jointly optimize the watermarking scheme, denoted by the joint distribution $P_{X_1^T, \zeta_1^T}$, and the model-agnostic detector $\gamma$ that minimizes the Type-II error (false negative) under the $\alpha$-constrained worst-case Type-I error (false positive). We formulate the optimization problem in (OPT-O). The optimal objective value is thus the universally minimum Type-II error, as the Type-I error is under control for all possible text distributions (Theorem 1). The optimizer identifies the optimal class of detector-watermarking scheme pairs. Additionally, we prove that detectors within this optimal class, denoted as $\Gamma^*$, are universally optimal. Specifically, for any detector $\gamma \notin \Gamma^*$, there always exists a text distribution $Q$ and a distortion level $\epsilon$ such that no watermarking scheme can achieve the universally minimum Type-II error. It suggests that to guarantee the construction of an optimal watermarking scheme for any arbitrary LLM, the detector must be selected from the set $\Gamma^*$. For clarity, we restate Theorem 2 as follows:

Optimal type of detectors and watermarking schemes. Since we have established the universally minimum Type-II error, a natural question arises: what is the optimal type of detectors and watermarking schemes that achieve this universal minimum (for all $Q_{X_1^T}$ and $\epsilon$)? Let $\Pi^*(Q_{X_1^T},\alpha,\epsilon)$ denote the set of all solutions $(\gamma^*,P_{X_1^T,\zeta_1^T}^*)$ that achieve $\beta_1^*(Q_{X_1^T},\alpha, \epsilon)$.

Theorem 2 ((Informal Statement) Optimal type of detectors and watermarking schemes) The optimal type of detector is given by $\Gamma^*\coloneqq \lbrace \gamma\mid \gamma(X_1^T,\zeta_1^T)= \mathbb{1}\lbrace X_1^T=g(\zeta_1^T)\rbrace, \text{ for some surjective } g:\mathcal{Z}^T\to \mathcal{S} \supset \mathcal{V}^T \rbrace.$ For any $\gamma^* \in \Gamma^*$ and any $(Q_{X_1^T},\epsilon)$, the corresponding optimal $\epsilon$-distorted watermarking scheme $P_{X_1^T,\zeta_1^T}^*$ is provided in Appendix D, i.e., $(\gamma^*,P_{X_1^T,\zeta_1^T}^*)\in \Pi^*(Q_{X_1^T},\alpha,\epsilon)$.

Corollary 3 (Universal optimality of detectors $\Gamma^\*$) For any $\gamma \notin \Gamma^\*$, there exists $(\tilde{Q}_{X_1 ^T}$, $\tilde{\epsilon})$ such that no $\tilde{\epsilon}$ distorted watermarking scheme $P _{X_1^T, \zeta_1^T}$ satisfies $(\gamma$, $P _{X_1^T,\zeta_1^T})$ $\in$ $\Pi^*(\tilde{Q} _{X_1^T},\alpha,\tilde{\epsilon})$.

Theorem 2 and Corollary 3 suggest that to guarantee the construction of an optimal watermarking scheme for any arbitrary LLM, the detector must be selected from the set $\Gamma^*$.

Q2. Shown results for variable-length generation.

Under our framework, we consider the detection performance given a generated sequence. Thus, our Theorems 1 and 2 hold for fixed-length generation cases. The theoretical analyses for variable-length generation cases would be an interesting future direction. However, although we do not provide theoretical optimality for variable-length generation, we provide a practical scheme that considers variable-length watermark generation and detection in Sections 4 and 5. In Section 4, we propose a token-level optimal detector and watermarking scheme based on our sequence-level optimal result. This approach effectively adapts to variable-length text generation while maintaining strong performance guarantees, as stated in Lemma 4 in the revised manuscript. In Section 5, experimental results show that our algorithm achieves excellent detection performance and robustness.

Q3. Whether constructed optimal watermarking scheme requires knowledge of LLM distributions. If so, is it possible to compute the scheme's parameters efficiently, either practically or within polynomial time?

Yes, as outlined in Algorithm 1 of our manuscript, our optimal watermarking scheme depends on the Next Token Prediction (NTP) distribution of the LLM. However, the computation of our watermarking scheme remains highly time-efficient, with complexity scaling linearly with the vocabulary size. To demonstrate the efficiency of our watermarking method, we conducted experiments measuring the average generation time for both un-watermarked and watermarked text. For these experiments, we employed LLaMA2-13B and the C4 dataset, setting the text length to 200 tokens in both scenarios. The results, presented in the following table, indicate that the difference in generation time between un-watermarked and watermarked text is less than $0.5$ seconds. This minimal difference confirms that our watermarking method has a negligible impact on generation speed, ensuring practical applicability.

Q4. Can you say anything about the optimality of your detector for generations that are not of a fixed length?

In our response to Q1, we clarify that the optimal type of detectors and watermarking schemes are jointly optimal, meaning that $(\gamma^*, P_{X_1^T,\zeta_1^T}^*)$ is optimal in pair. Therefore, given a $\gamma^*$ within the optimal class, it is not necessarily optimal for an arbitrary watermarking scheme. However, building on our theoretically optimal result, we propose a token-level optimal detector and watermarking scheme in Section 4, which adapts to variable-length generation. This approach ensures optimality at each token while maintaining strong detection performance across the entire sequence.

Q5. Describe the set of optimal detectors $\Gamma^\*$ in simpler terms. (It appears that you're saying that, for any fixed watermarked text generation algorithm of the form you consider, the optimal detector simply tests whether the entire generation is exactly equal to some string computed as a function of \zeta. However, this is clearly false: If \zeta is just a collection of red/green lists for each token position, then the detector should accept many possible texts. I think that what you're trying to say is that there exists a watermarking algorithm such that this detector is optimal, but this is not what appears to be stated in Theorem 2.)

We are sorry for the confusion. In our response to Q1, we restated Theorem 2 for clarity. The optimal solution to our optimization problem (OPT-O) identifies the optimal class of detector-watermarking scheme pairs. Additionally, we prove that detectors within this optimal class, denoted as $\Gamma^*$, are universally optimal. Specifically, for any detector $\gamma \notin \Gamma^\*$, there always exists a text distribution $Q$ and a distortion level $\epsilon$ such that no watermarking scheme can achieve the universal minimum Type-II error. It suggests that to guarantee the construction of an optimal watermarking scheme for any arbitrary LLM, the detector must be selected from the set $\Gamma^*$. Therefore, for any detector in the optimal set $\Gamma^*$, it only achieves the optimal performance when paired with its corresponding optimal watermarking scheme (construction detail in Appendix D)。

Dear reviewer mxQq,

We sincerely appreciate your time and effort in reviewing our submission and providing valuable suggestions. While we hope to have addressed your concerns adequately, we understand there may still be areas requiring further clarification or discussion. We are fully prepared to address your outstanding issues. Should our responses have successfully addressed all your questions, we would be deeply grateful if you could consider enhancing the score to further support our submission. Thank you very much for your thoughtful review.

Best Regards,

Paper12990 Authors

Dear reviewer mxQq,

We sincerely appreciate your time and constructive feedback, which helps us further improve the quality of our submission. We have made every effort to answer your insightful questions by modifying the manuscript and writing rebuttals. Considering today (Dec 2) is the deadline for the author's response, we hope our responses have addressed the reviewer's concerns, but if not, we are available to address any outstanding issues. In case we have addressed all your questions, we truly appreciate your feedback and reconsider your score for further support.

Best Regards,

Paper12990 Authors