Watermarking using Semantic-aware Speculative Sampling: from Theory to Practice

Thank you for your feedback. Please find our detailed responses below.

If different texts are used as seeds, the resulting pseudo-random numbers will differ, leading to different secret keys as in Fig.2 and making it impossible to complete the watermark detection.

This is a thoughtful argument: you point out the fundamental difficulty of statistical watermarking, that the (pseudo-)randomness source can be distorted by attack. We would like to clarify that our contribution to statistical watermarking is orthogonal to the challenge in (pseudo-)randomness source as you pointed out. Specifically, our work focuses on improving the statistical aspect, i.e. the distribution of the random seeds and the coupling between the random seed and the next token.

Previous works address this challenge by setting the secret keys as keyed hash of the sliding window (usually size <= 6) of past tokens or minimum of keyed hash applied to each previous token in the sliding window. In our experiments, we set the sliding window size to 1, and so the secret keys keep the same given that the latest tokens are not changed. Empirically, we find that despite paraphrasing, SEAL can still detect nearly half of the watermarked texts (q.v. Table 2). Therefore, it is still possible to complete the watermark detection even if different texts are used as seeds.

The paper's discussion does not consider the impact of an attacker modifying the text. Even slight changes to the text by an attacker could affect the extraction of semantic information, which in turn would impact the watermark detection.

As we clarified above, we experimentally demonstrated that SEAL can still detect nearly half of the watermarked texts under paraphrasing attack.

In our theoretical treatments, we also studied the statistical limits of watermarking under attacks. Specifically, Appendix C.5 shows that the optimal robust Type II error is governed by a linear program whose constraints correspond to the attacks.

It is reasonable to expect that a statistical watermark would fail if an attacker significantly modifies the text to the extent that it becomes more reflective of their own work than that of the LLM. If such modifications alter the semantic meaning of the text, the watermark detection is naturally expected to be impacted.

In summary, the ability of an attacker to invalidate watermark detection by substantially altering the text is not a weakness of our approach but an inherent property of any watermarking system. Our paper addresses these challenges both theoretically and experimentally, making this critique not a flaw of our work.

The writing in the paper is not clear enough, as the embedding and extraction of the watermark are not explicitly expressed in algorithmic form, making it difficult to understand the construction details.

Due to space constraints, algorithm pseudocodes are provided in Appendix D.

The embedding and extraction of watermark are discussed in Section 3.1.2 and 3.1.3, simply put, we embed watermark via speculative sampling on a proposal model and extract watermark by checking if the true tokens collide with the tokens from the proposal model.

If the extracted semantic information is not completely consistent, will it result in watermark inconsistency? Will it affect the watermark detection?

If an attacker changes the semantic information, then our scheme might not detect the watermark. However, as we discussed above, it is fair to expect any watermark to fail if an attacker significantly modifies the text to the extent that it becomes more reflective of their own work than that of the LLM.

On page 6, h_i is a hash function, and in the subsequent description, there is an expression h_i^{-1}(A) . What does h_i^{-1} mean? This form is generally considered an inverse function, but hash functions typically do not have inverse functions.

The preimage of a function is the set of all elements of the domain that are mapped into a given subset of the codomain, which is well-defined for hash functions that are not injective. More precisely, $h_i^{-1}(A) = \{x: h(x) \in A\}$. The preimage (which maps a subset to a subset) can be viewed as a “generalization” of the inverse function (which maps an element to an element).

Can the authors make a more careful comparison with the "green-red" list approach along this line?

When the proposal LLM is the target LLM, the hash function is identity mapping, and the attention window K is infinite, SEAL reduces to the statistically optimal watermark in Theorem 2.1. Only when the proposal LLM is uniform distribution (i.e. infinite temperature) and $\Omega_h = \{0,1\}$, SEAL would reduce to the "green-red" list scheme in Kirchenbauer et al. (2023). In all our experiments, SEAL uses a nontrivial proposal LLM with normal temperature and outperforms the "green-red" list approach.

What is the most essential component of SEAL that contributes to its statistical efficiency and robustness?

SEAL enhances efficiency because its random seeds come from a proposal LLM rather than a fixed distribution. In one extreme, when the proposal LLM is the target LLM, the hash function is the identity mapping, and the attention window K is infinite, SEAL reduces to the statistically optimal watermark in Theorem 2.1. In the other extreme when the proposal LLM is uniform distribution (i.e. infinite temperature) and $\Omega_h = \{0,1\}$, SEAL would reduce to the "green-red" list scheme in Kirchenbauer et al. (2023). Therefore, SEAL serves as an interpolation between the statistically-optimal watermarking and the "green-red" list scheme, enjoying both statistical efficiency and practicality.

SEAL enhances robustness because its random seeds depend on semantic information in preceding texts, which is more robust to paraphrasing. For example, the proposal model might generate the same next token despite the preceding tokens being paraphrased, thus resulting in the same random seed which enables successful detection.

Given that SEAL is constructed based on maximum coupling, does it enjoy certain theoretical optimality regarding power/Type II error?

When the proposal LLM is the target LLM, the hash function is identity mapping, and the attention window K is infinite, SEAL reduces to the statistically optimal watermark in Theorem 2.1, therefore enjoys statistical optimality. In practice, SEAL cannot achieve optimality because the target LLM and the prompt is inaccessible to the detector. However, it still improves statistical efficiency upon existing works.

Please comment on the sensitivity of SEAL to the tuning parameters such as K, Ωh, and the hash function.

In experiments we find that a suitable value of K lies between 10 and 20 and further increasing K will only reduce efficiency (because SEAL needs K tokens to warm-up). SEAL is observed to perform well when $\Omega_h$ is less than 5. The hash function has little influence on SEAL’s performance.

Thank you for your feedback. Please find our detailed responses below.

Practical relevance of theoretical results

Theorem C.2 and Theorem 2.3 focuses on theoretical study where the main target is to characterize the statistical rates of watermarking a random source. In response to your concern, our result Theorem 2.4 deals with the practical setting where the tokens are non-iid, which improves theoretical understanding on the number of tokens and the empirical entropy required to detect the watermark (compared with existing bounds such as Christ et al. (2023)).

Theoretical results ignore the prompts' impacts

All of our results hold universally for any arbitrary prompt. The prompt influences the rates through the entropy h (or empirical entropy $\hat H$) of the text distribution: for questions such as ‘1+1 = ?’ the entropy is low and so our rates indicate that more tokens are required to watermark responses to such prompts, and for open-ended questions the entropy could be high and the number of required tokens becomes lower according to our rates. Therefore, our rates are influenced by the prompts and our theoretical results do NOT ignore the prompts' impacts.

The proposed SEAL method's rationale and novelty

The inspiration comes from Theorem 2.1, where we showed that best efficiency is achieved by generating random seeds from the same watermarked model and maximally coupling the seeds with next tokens. However in practice, the watermarked model is unknown to detectors, so we adopt a proposal model which is close to all language models since they are all trained to fit the human language distribution. In this way, the random seeds become adaptive to the semantic information in preceding texts, as opposed to fixed distributions in previous works.

The major novelty of SEAL is introducing speculative sampling into watermarking, which enables the random seeds to capture semantic information with provable type-I error and distortion guarantees. To our knowledge, our work is the first to use proposal LLMs and speculative sampling in watermarking LLMs.

While there are existing works on semantic-aware watermarking, the major difference is that existing semantic-aware schemes do not have formal Type I error guarantees while our watermarks have provable type I error bound. For example, Fu et al. (2023) add some semantically-similar tokens into the green list, which makes the green list not fully (pseudo)-random; Hou et al. (2023) performs rejection sampling to sample the sentences conditional on certain green region in the semantic space, which significantly increases the probability that a human-generated token falls into the green list; Ren et al. (2023) uses a trained MLP to generate semantic values, which lacks theoretical control. In summary, we have yet seen any formal Type I error or distortion-free statements in these works, possibly due to the heuristic design. In comparison, our algorithm enjoys clear Type I error guarantee by introducing speculative sampling techniques into watermarking.

The role of the proposal LLM in their framework and how its quality affects SEAL's performance?

We tested the impact of the proposal LLM to SEAL's performance, summarized in the following table. We observe that the proposal model has very marginal impacts on SEAL's performance. We hypothesize that this is because in SEAL the proposal model only attends to the last K tokens, and so the fixed context window size can reduce the vibration of the next token probability among different proposal models.

Thank you for your feedback. Please find our detailed responses below.

the paper assumes knowledge of the watermarked language model (either directly or via a proxy proposal LLM) during detection, which prior work does not

In our theoretical results, we distinguish between two scenarios: instance-dependent and minimax. In the instance-dependent case, we derive tight rates that depend on the specific watermarked model. In the minimax case, we derive tight rates that depend on the model class to which the watermarked model belongs. Importantly, in both scenarios, our results hold universally for any arbitrary watermarked model or model class. Consequently, our findings do not rely on assumptions about the models themselves but instead highlight the dependency of rates on certain complexity parameters. Many prior works such as Aaronson (2022) and Zhao et al. (2023) also exhibit such complexity-dependency.

In practical results, our algorithm is based on certain knowledge of the watermarked language model, but we think that this is a strength rather than a weakness. SEAL exploits the fact that language models mimic the distribution of human language instead of some arbitrary distribution. Since the proposal model and the watermarked model are both trained to fit the language distribution, they should be reasonably close. This knowledge helps us address the problem of watermarking LLMs.

what trade-offs exist between their method versus prior work (both theoretically and empirically)

Theoretically, our method takes no more than 2X compute compared to standard generation because we simply add another language model for inference. Since our method couples the proposal model and the watermarked model using speculative sampling, many techniques in speculative decoding can be applied to further speed up our method, which might even end up being faster than standard generation due to parallel verification in speculative decoding. This would be an interesting future work to study.

Are there any guarantees regarding the difference in the joint distribution over multiple samples of original versus watermarked text from the watermark proposed in the paper?

If the pseudo-randomness sources are considered as independent from a true random oracle, then multiple samples of watermarked texts are independent of each other and then the joint distribution is also distortion-free.

Our watermarking scheme is amenable to any design of pseudo-randomness sources, and our scheme enjoys the cryptographical indistinguishability of whatever randomness sources it uses. For experiments we use text-dependent (embedded) randomness, same as many previous works such as Aaronson and Kirchner (2022) and Kirchenbauer et al. (2023). If different private keys are used, then it is computationally intractable to distinguish the joint distribution over multiple watermarked samples from the original ones.

Capture semantic information

We call a watermarking method semantic-aware if its random seed’s distribution is dependent on the previous texts. In SEAL, the random seed is the hashing of the proposal model’s next-token prediction, and so depends on previous texts. In comparison, Kirchenbauer et al. (2023)’s random seeds (green lists) are uniformly random subsets of the vocabulary, Aaronson (2022b)’s random seeds follow uniform distribution, Christ et al. (2023)’s random seeds are Bernoulli random variables, all following fixed distributions. Therefore, we say that SEAL is semantic-aware as opposed to baseline schemes.

Why is SEAL considered model-agnostic

According to Problem B.4, SEAL is model-agnostic because the random seed’s distribution (derived from the proposal model) is independent of the particular watermarked model. SEAL uses the same proposal model in generation and detection: if one use M1 as proposal model in generation and M2 in detection then they would likely not detect any watermark.

Type II error theoretical analysis of SEAL

When the proposal LLM is the target LLM, the hash function is identity mapping, and the attention window K is infinite, SEAL reduces to the statistically optimal watermark in Theorem 2.1, therefore enjoys statistical optimality. In practice, SEAL cannot achieve optimality because the target LLM and the prompt is inaccessible to the detector. However, it still improves statistical efficiency upon existing works.

Hash function

As discussed above, SEAL’s semantic awareness is not attributed to the random hashing function.

Similar to Kirchenbaur et al. (2023), we select a small hash code space in SEAL. This means that the hash function is not injective. If the hash function is injective, the generation process is equivalent to speculative sampling. But we empirically found that the performance wouldn’t be stronger with injective hash function.

The hash function increases the probability of hash collision and thus enhances robustness. We empirically found that the SEAL works best when the hash code space size is small (<= 5).

Thank you for your feedback. Please find our responses below.

Comparison with related semantic-aware watermarking methods

We cited some semantic-aware watermarking methods and discussed our differences in Section 1.1. While there are existing works on semantic-aware watermarking, the major difference is that existing semantic-aware schemes do not have formal Type I error guarantees while our watermarks have provable type I error bound. For example, Fu et al. (2023) add some semantically-similar tokens into the green list, which makes the green list not fully (pseudo)-random; Hou et al. (2023) performs rejection sampling to sample the sentences conditional on certain green region in the semantic space, which significantly increases the probability that a human-generated token falls into the green list; Ren et al. (2023) uses a trained MLP to generate semantic values, which lacks theoretical control. In summary, we have yet to see any formal Type I error statements in these works, possibly due to the heuristic design. In comparison, our algorithm enjoys clear Type I error guarantee by introducing speculative sampling techniques into watermarking.

Proofs of theorems

In Theorem C.2, $\geq$ should be $\gtrsim$ and the sufficient condition more precisely is $|\Omega| \geq (2+\epsilon)/\alpha$. Indeed, if the desired inequality is not satisfied then $1 \geq \sum_{x:\rho(x) < \alpha} \rho(x) > \alpha \cdot (|\Omega| - 1/\alpha) - \epsilon \geq 1$, a contradiction.

In Theorem C.14, $\kappa_0$ should be defined as $\kappa_0 = \alpha/\log \frac{1}{\beta}$, and what we need are $\kappa := e^{-\widehat H} \lesssim \kappa_0$ and $m := |\Omega| = |\Omega_0|^n \gtrsim 1/\kappa_0$. Line 1893 is guaranteed by the definition of $\eta^*$ and does not apply the result of Theorem C.6. Line 1912 holds with the corrected definition of $\kappa_0 = \alpha/\log \frac{1}{\beta}$. In the revision, we have fixed the typos and added necessary explanations to each step.

In line 1242, the Bernoulli random variables are indeed independent because we are at the detection phase under H_0. We understand your point that at the generation phase $\xi_j$’s are generated autoregressively and should be defined on filtrations. However, at the detection phase under H_0, the token sequence $y$ is fixed and the randomness comes solely from the proposal model’s output. As shown in Algorithm 4 line 5, the distributions $\rho_j$’s are independent of each other, and so are $\xi_j$’s.

In Theorem G.5, we change the statement to ‘For any fixed (sub-)sequence $y$’, which matches more precisely with our definition of Type I error in Problem B.1.

Log likelihood ratio (LLR) test and other model non-agnostic methods

The UMP watermark in Table 5 is equivalent to the Log likelihood ratio test. As clarified in lines 1389-1391, Table 5 only serves to exhibit optimal rates rather than comparison. We have made these points clearer in revision.

Experimental details

We conducted more experiments with varying secret keys. The error bars of SEAL are shown in the following table:

The numbers of baseline schemes are retrieved directly from the benchmark of Piet et al. (2023). We conducted experiments with the provided parameters and found that the quality of baseline schemes is around 0.89, closer to SEAL. We hypothesized that it is due to Piet et al. (2023) performing some hyperparameter search to optimize the quality metric.

In experiments, we use the biased version of SEAL with nonzero $\delta$. The hyperparameter details can be found in Appendix E. Therefore, it is reasonable that SEAL exhibits certain quality degradation.

Connection between the theoretical and algorithmic contributions

The pushforward of the token distribution onto the same measure space is $\eta^*\left(p\left(W \cap (U \times 2^\Omega)\right)\right)$ in Eq.(13).

SEAL is inspired from Theorem 2.1, where we showed that the best efficiency is achieved by generating random seeds from the same watermarked model and maximally coupling the seeds with the next tokens. However, in practice, the watermarked model is unknown to detectors, so we adopt a proposal model that is close to all language models since they are all trained to fit the human language distribution. In this way, the random seeds become adaptive to the semantic information in preceding texts, as opposed to fixed distributions in previous works. The random seed is the hashing of the proposal model’s next-token prediction. To couple the random seed and the true next token, we use ideas from Theorem C.6.

Thank you for engaging in the discussion and providing your thoughtful feedback. We appreciate your detailed comments, which have helped us further refine our manuscript. Below, we address each of your points:

Comparison with related semantic-aware watermarking methods

We have clarified that: (i) Related semantic-aware watermarking methods are already discussed in Section 1.1. (ii) The previous semantic-aware schemes belong to a different domain as they lack formal Type I error guarantees. It is important to emphasize that our work specifically focuses on statistical watermarking with formal guarantees, which distinguishes it from existing semantic-aware methods. These points have been further elaborated in the revised manuscript.

Experimental baselines

As noted, existing semantic-aware methods fall outside the scope of our study. Our focus is on statistical watermarking methods with formal guarantees, and while there are numerous watermarking approaches (q.v. the review of Tang et al. (2023)), it is infeasible to compare against all of them.

We also reiterate that the UMP test described in Theorem 2.1 is essentially a likelihood ratio (LLR) test, and we are unaware of other model-nonagnostic methods (Hu et al. (2023)'s watermark is detectable in a likelihood-agnostic way, which makes it not model-nonagnostic). Furthermore, as noted below Table 5, the results in Table 5 are intended to demonstrate statistical limits in Type I/II errors, rather than serve as comparison or advocate for the superiority of a particular watermarking approach.

Difference in quality between unbiased methods

As we clarified in responses, the numbers of baselines in table 1 come directly from the benchmark report (which according to their report are tuned specifically for quality metric) and our own further experiments demonstrate that the quality of baseline schemes is approximately 0.89, close to SEAL. This suggests there is no significant quality difference between SEAL and baseline methods.

Additionally, we have clarified that we employ a biased version of SEAL with nonzero $\delta$. Therefore, it is incorrect to say that "When comparing exponential and SEAL, both are unbiased (distortion-free) in token distribution but the plotted quality differs a lot. If there are no implementation errors, this suggests a large variance that the authors should have clearly plotted."

Why SEAL is considered model-agnostic

As noted in Problem B.4, a watermarking scheme is considered model-agnostic if the distribution of the random seed (derived from the proposal model) is independent of the particular watermarked model. SEAL adheres to this definition and is therefore classified as model-agnostic.

Our definition aligns with Kuditipudi et al. (2023)'s original definition of model-agnosticity, where they defined as 'agnostic—it should be detectable without the language model and/or prompt'. The term "the language model" in their definition refers specifically to the watermarked model, not to any arbitrary language model. Consequently, a method is model-agnostic even if it utilizes another language model for watermark generation or detection.

SEAL's approach leverages another language model for this purpose because all language models are trained on human language distributions, which ensures reasonable similarity. This stems from the nature of the problem rather than an additional assumption: we aim to watermark outputs of language models, not arbitrary sequences.

Writing issues and theorem proofs

Thank you for your feedback. In the revision, we have changed the notation $\eta$ in the main body to avoid conflicts and we have updated the proof of Theorem C.2.

Adding a bias δ to the logits is in the maximal coupling step. This is clear as the "Bootstrapping efficiency with logits bias" paragraph is under Section 3.1.2: Maximal Coupling Construction. Thus, there is no inconsistency between the algorithm and figure.

In line 812, $L_G$ has been defined in the step above: "Randomly partition $V$ into a green list $L_G$ of size $\gamma |V|$, and a red list $L_R$ of size $(1 - \gamma)|V|$."

Line 825: $C$ is the threshold for the z-test, as referenced in Eq. (2) of Kirchenbaur et al. (2023). We have clarified this parameter in the revision.

Thank you again for your constructive input. We hope these responses address your concerns and look forward to your further insights.