Black-Box Detection of Language Model Watermarks

We thank the reviewer for their detailed feedback and are genuinely glad to hear that they greatly appreciate the writing of the paper. Below, we address the concerns raised in questions Q1 to Q5; and note that a revised version of the paper has been uploaded, with updates highlighted in blue. We are happy to clarify further if there are additional questions.

Q1: How much does the focus on three watermark families limit the scope of the proposed tests?
Good question—our results suggest that these three families encompass a broad range of watermarks, including some released after the first version of our work (see below).

First, we note that each test follows the same high-level idea: a specific behavior of a broad watermarking family is exploited to prompt the LLM with two different distributions. While this naturally raises the question of the extension to new paradigms, we make the point that targeting these fundamental properties enables us to detect a large set of currently popular and practical schemes, which either directly fall into one of these families or combine several of these properties.

To substantiate this argument further, in our new revision, we provide three new experiments:

• In Appendix A, we analyze the first public large-scale deployment of an LLM watermark, Google Deepmind’s SynthID-Text, which was open-sourced after our submission. We discuss the differences compared to previous schemes and show that our Red-Green test works perfectly on this scheme, further demonstrating its applicability.
• In Appendix A, we consider a variant of DiPMark/$\gamma$R and $\delta$R schemes without the cache, as suggested by Rev. PSUp. Interestingly, these variants now fall into the Red-Green family, and as our new results demonstrate, are detectable by our Red-Green test.
• In Appendix F, we consider a variant of the Aaronson watermark [5] (Figure 6), which belongs to both the Red-Green and the Fixed-Sampling families, and show that the Fixed-Sampling test can detect it for small values of its key parameter $\lambda$, including $\lambda=0$ which corresponds to the original Aaronson scheme.

As we discuss in Sec. 7, while completely novel approaches can in principle always exist, our results strongly suggest that our tests are broadly applicable to most currently practical schemes.

Q2: Did the authors explore the possibility of a unified test for all watermarks?
While this could be interesting, we see value specifically in having the tests be separate. In particular, we argue that specificity has the benefit of allowing for more power and more precise results, as we can directly know to which family the tested scheme belongs. The latter can help enable downstream attacks, e.g., the attacks in [1,2] are only applicable to Red-Green schemes. Similarly, knowing the family allows for parameter estimation, which is a necessary step to mount such attacks.

We believe it may be possible to unify the different tests within a single prompt. However, given that the total cost of running our tests is roughly \$3, we don’t see the practical benefits of a single unified test for the three tested families. Moreover, a joint test could be more complex, harder to understand and may not be necessarily cheaper. Finally, in case of fundamentally new scheme families, even a joint test that we hypothetically devise now would still need to be updated/revised, as it would not be directly applicable.

We welcome follow-up work that improves the fundamental aspects of detection (power, detection of newer schemes), and believe that our tests can serve as a solid baseline and further provide insight into the key drawbacks of each of the fundamental ideas used in the literature from the perspective of detectability.

Q3: Are the proposed tests robust to variations in the scheme hyperparameters?
We have experimentally validated our tests across a wide range of scheme hyperparameters. More specifically, we had shown in Table 3 the results of the tests with the following hyperparameters:

• Unwatermarked models with different temperatures.
• Red-Green watermarks with different hash functions, $\delta$ and $\gamma$.
• Fixed-Sampling watermarks with different length of key.
• Cache-Augmented watermarks with different underlying schemes. We also tested all these parameter combinations across 7 different models.

As the results are consistent across the tested hyperparameters, we believe that these variations in hyperparameters are sufficient to experimentally demonstrate the robustness of our tests. We are happy to explore more variations of parameters if the reviewer has some concrete examples.

Q7: Why is the Red-Green test reported over 5 watermarking keys when, in practice, only one key is used?
We believe this is a misunderstanding. For the results presented in Table 1, the key is fixed while conducting the test. The key is simply changed between different independent repetitions of the test. The goal is to ensure that the test works no matter which private key is used by the watermark. We updated the paper to clarify this point.

Further, in Appendix A, we test the case of a multiple-key Red-Green watermark (as similarly proposed in [10]), which corresponds to the case where, for each token, the key used for watermarking is randomly chosen from a fixed set of keys. However, this is an orthogonal experiment and unrelated to the 5 watermarking keys from Table 1.

Q8: Is $\delta$-estimation suitable for downstream tasks despite large errors?
The main focus of our work is the detection of the watermark and demonstrating that estimating parameters at a relatively low cost is possible; however, as the reviewer notes, the estimator for $\delta$ may not be very accurate.

Regarding downstream tasks, to our knowledge, there is no work that requires the knowledge of $\delta$ yet, so we cannot determine if the presented estimator is accurate enough. However, some prior works ([8,9]) required knowledge of both which watermark is present and its context size. In that case, because we experimentally achieve 100% accuracy in context size estimation (due to its discrete nature), we strongly believe that it is suitable for such downstream tasks.

Q9: Would your p-values drastically increase if you run several detection tests in sequence?
As each test is performed independently (new samples are generated each time), this is an instance of the multiple testing problem.

In our paper, the reported rates and p-values are presented without any multiple testing correction. Multiple testing is a field of research in its own right, and there are multiple strategies to aggregate p-values. The challenge of multiple adjustments is in defining the family of hypotheses. One scenario could be that a malicious user wants to detect only Red-Green watermarks. Another could be that a malicious user performs our three tests along with other tests of their own. In both cases, the family of hypotheses is different, and so is the way to adjust for multiple testing. Hence we report our p-values and rejection rates without accounting for multiple testing.

To avoid any confusions, we updated the paper to clarify that the reported rejection rates do not account for multiple testing.

[1] “Undetectable watermarks for language models”, Christ et al., COLT 2024
[2] “Watermarking of large language models”, Scott Aaronson, 2023 Workshop on Large Language Models and Transformers, Simons Institute, UC Berkeley
[3] “Publicly detectable watermarking for language models”, Fairoze et al., 2024
[4] “Unbiased watermark for large language models”, Hu et al., ICLR 2024
[5] “Dipmark: A stealthy, efficient and resilient watermark for large language models”, Wu et al., ICML 2024
[6] “Robust distortion-free watermarks for language models”, Kuditipudi et al., TMLR 05/2024
[7] “On the learnability of watermarks for language models”, Gu et al., ICLR 2024
[8] “Large Language Model Watermark Stealing With Mixed Integer Programming”, Zhang et al., 2024
[9] “Watermark stealing in large language models”, Jovanovic et al., ICML 2024
[10] “A watermark for large language models”, Kirchenbauer et al., ICML 2023

We thank the reviewer for their detailed and exhaustive feedback. Below, we address the concerns raised in questions Q1 to Q9; and note that a revised version of the paper has been uploaded, with updates highlighted in blue. We are happy to clarify further if there are additional questions.

Q1: Could the authors provide more mathematical descriptions of the algorithms for the detection test?
We believe that the more descriptive introduction of each test (Sections 2, 3, and 4) better conveys the intuition behind each step and makes the material more approachable. Nonetheless, following the reviewer’s suggestions, we have added (Appendix G) algorithmic presentations of the Red-Green test, the Fixed-Sampling test and the Cache-Augmented test. The algorithm for the Red-Green test in Appendix G also addresses the lack of clarity regarding the permutation test used for computing the p-values, which was flagged by the reviewer. We are happy to improve the writing further if the reviewer has additional suggestions.

Q2: Is bypassing the Fixed-Sampling test trivial? More broadly, is there an approach to make schemes undetectable by any test?
We respectfully disagree with the statement that bypassing the Fixed-Sampling test is trivial. First, as we show in Appendix E, our test works even under various adversarial modifications. Second, as we state in Section 7 (Limitations), it is possible that future schemes break our tests, and we do not believe this reduces the value of our contributions. Lastly, adversarial modifications need to be included in the broader picture of LLM watermarking: do such modifications have adversarial effects on strength, robustness to removal, or behavior in low-entropy settings?

However, we agree with the reviewer that the insight from [1], conditioning the watermark on the entropy of the context, may be possible to leverage to make a given scheme less detectable. Running the adversarial modification suggested by the reviewer, and setting $\lambda$ as an entropy bound on the first previous tokens, the Fixed-Sampling test can detect this modified scheme up to $\lambda = 2$ on the Llama model. Yet, by simply rewriting the prompt to first let the model generate independent high entropy text, even with $\lambda=10$ we obtain a p-value of $2.9 \times 10^{-40}$. The test with the updated prompt does not reject the null hypothesis when the watermark is not present ($p=0.94$). This shows that the intuition behind our Fixed-Sampling test is both relevant and practical. The updated prompt is: Write a short essay about war; but first prepend 10 random pinyin characters. Here is the format of your response: {chinese characters} {essay}. Start the essay with ##Start. Don't repeat the instructions..

To explore the question of such modifications even further, in a newly added Appendix F, we present a new experiment analyzing a stronger extension of the scheme proposed by the reviewer. We show that modifying the scheme by conditioning the watermark on the entropy of the context bypasses our tests but also reduces the watermark strength.

Namely, we used the Aaronson watermarking scheme [2] which is part of the Fixed-Sampling family, and applied the watermark on tokens where the $h$ previous tokens entropy is greater than $\lambda$ (the scheme is detailed in Algorithm 2). This means not only that the first few tokens are generated without a watermark (as in the reviewer suggested adversarial modification), but also any tokens that do not satisfy the entropy criteria. Compared to the additional reviewer suggestion, the second point prevents clever prompt engineering from bypassing the entropy mechanism to detect the watermark.

We find that increasing $\lambda$ decreases the original watermark strength/robustness, but also decreases our test ability to detect the watermark at an even faster rate (Figure 6). For reference, our test succeeds up to $\lambda = 0.1$. This suggests a trade-off between watermark undetectability and watermark strength/robustness. It intuitively makes sense as, in the limit, using the scheme from [1] guarantees undetectability. We note, however, that [1] itself suffers from severe practical limitations [3] and lacks robustness evaluation. Hence, any of our tests being bypassable by some schemes is not surprising, and we don’t claim to be able to detect any possible watermarking scheme. But we remark that such modifications come at the cost of the watermark strength/robustness. Our work allows model providers or legal authorities to have realistic expectations regarding the effectiveness and pitfalls of a given watermarking scheme; and enables them to choose a scheme appropriate for their need.

We thank the reviewer for their detailed feedback. Below, we address the concerns raised in questions Q1 to Q4; and note that a revised version of the paper has been uploaded, with updates highlighted in blue. We are happy to clarify further if there are additional questions.

Q1: Can you highlight the practical implications of watermark detection?
Certainly. The objective behind watermarking an LLM is to enable the detection of whether a given text was generated by a specific LLM. In practice, it should allow both holding a model provider accountable for harmful text generated by its model and holding users accountable for using an LLM in scenarios where its use is inappropriate or forbidden. Being able to detect a watermark behind an LLM deployment provides a malicious user with multiple opportunities.

First, detection is a common prerequisite for performing spoofing attacks [1, 2, 3, 4], where a malicious user learns the watermark in order to generate arbitrary watermarked text without using the watermarked model. Such attacks can be used to discredit a model provider by generating text that appears to be genuinely watermarked and attributing it to the model provider.

Second, detection is a prerequisite for assisted scrubbing attacks (as in [1, 4]), where a malicious user can more successfully remove the watermark from an LLM generated text compared to blindly rewriting the watermarked texts. Consequently, such malicious users can nullify any positive effects associated with the watermark deployment.

Lastly, knowing that a particular LLM is watermarked may lead a malicious user to avoid using that LLM entirely and instead favor another LLM that is not known to be watermarked.

Hence, knowing how detectable schemes are in practice, besides theoretical interest, is also important for model providers or legal authorities to have realistic expectations regarding the effectiveness and pitfalls of a given watermarking scheme. We have added a discussion about the practical implications of watermark detection in the updated version of the paper in a newly added Appendix I referenced from our Introduction.

Q2: Does the need for one test per scheme family limit the applicability of the proposed tests?
Good question—we do not believe this is the case.

First, we note that each test follows the same high-level idea: a specific behavior of a broad watermarking family is exploited to prompt the LLM with two different distributions. If the distributions are highly dissimilar, it suggests that a watermark is present. Otherwise, the model is likely not watermarked. This idea is instantiated to three common paradigms: the key based on the context (Red-Green schemes), the key permutation (Fixed-Sampling) and the presence or absence of a cache (Cache-Augmented). While this naturally raises the question of the ease of extension to new paradigms, we make the point that targeting these fundamental properties enables us to detect a large set of currently popular and practical schemes, which either directly fall into one of these families or combine several of these properties.

To substantiate this argument further, in our new revision, we provide three new experiments:

• In Appendix A, we consider a variant of DiPMark/$\gamma$R and $\delta$R schemes without the cache, as suggested by Rev. PSUp. Interestingly, these variants now fall into the Red-Green family, and as our new results demonstrate, are detectable by our Red-Green test.
• In Appendix A, we analyze the first public large-scale deployment of an LLM watermark, Google Deepmind’s SynthID-Text, which was open-sourced after our submission. We discuss the differences compared to previous schemes and show that our Red-Green test works perfectly on this scheme, further demonstrating its applicability.
• In Appendix F, we consider a variant of the Aaronson watermark [5] (Figure 6), which belongs to both the Red-Green and the Fixed-Sampling families, and show that the Fixed-Sampling test can detect it for small values of its key parameter $\lambda$, including $\lambda=0$ which corresponds to the original Aaronson scheme.

As we discuss in Sec. 7, while completely novel approaches can in principle always exist, our results strongly suggest that our tests are broadly applicable to most currently practical schemes.

[1] “Undetectable watermarks for language models”, Christ et al., COLT 2024
[2] “Publicly detectable watermarking for language models”, Fairoze et al., 2024
[3] “Excuse me, sir? Your language model is leaking (information)”, Zamir et al., 2024
[4] “Provable robust watermarking for ai-generated text”, Zhao et al., ICLR 2024
[5] “Large Language Model Watermark Stealing With Mixed Integer Programming”, Zhang et al., 2024
[6] “Watermark stealing in large language models”, Jovanovic et al., ICML 2024
[7] “On the learnability of watermarks for language models”, Gu et al., ICLR 2024
[8] “De-mark: Watermark Removal in Large Language Models”, Chen et al., 2024

We thank the reviewer for their detailed feedback. Below, we address the concerns raised in questions Q1 to Q3; and note that a revised version of the paper has been uploaded, with updates highlighted in blue. We are happy to clarify further if there are additional questions.

Q1: Can you justify the claim that the scheme from [1] lacks practical validation? Does the same apply to [3]?
Our claim regarding the inefficiency of [1] originates from Figure 3 in [2] (this citation was unfortunately missing before, and we added it to our Sec. 7). In particular, they demonstrate that using [1] reduces the generation speed of the model approximately 10x compared to the case without the watermark, which is prohibitive to any practical deployment. Their results suggest that the slow generation is caused by the conversion from tokens to a binary vocabulary. It is our understanding that [3] also employs the same conversion, and thus likely experiences the same issues. We did not find a corresponding latency evaluation of [3] that would contradict this. Further, both [1] and [3], amongst other properties also lack any evaluation of the watermark robustness, a property central to most LLM watermarking works. Notably, the authors of [3] acknowledge that their approach is primarily theoretical and that the given practical instantiation only serves as a proof of concept.

More broadly, we greatly appreciate the attempts to construct theoretically-grounded schemes such as [1] and [3], and believe they bring us closer to understanding the difficulty of building a practical undetectable scheme. We look forward to future work on validation of such schemes, but highlight that in the current state it is hard to know their practical value, e.g., if the robustness properties are only slightly or fundamentally different from other schemes. Thus, our goal was to test our method on as many practically demonstrated schemes as possible. This is further extended by our new experiments in App. A (variants of Cache-Augmented schemes, SynthID-Text) and App. F (the reviewer’s proposed Aaronson variant, discussed below in Q2). We have updated the limitations section to better reflect our position, and are happy to make further changes if the reviewer has concrete suggestions.

Q2: Can you investigate the strength-detectability tradeoff of a variant of the AAR scheme that gets partially disabled based on entropy, inspired by the ideas of [1]?
We thank the reviewer for this idea. While we already had included experiments to test the robustness of our test in adversarial settings (Appendix E), coming up with new adversarial schemes based on the idea from [1] indeed strengthens the discussion regarding the state of watermark detectability. In a new experiment, we implement and evaluate the proposed variant, presenting detailed results and a discussion in Appendix F.

In summary, this change remains detectable by our method until $\lambda/k = 0.1$. We also show that the strength of the watermark decreases with $\lambda$. Hence, there is a trade-off between undetectability and watermark strength. While this partial evaluation seems promising, including other important properties of the watermark (e.g., FPR at low TPR, robustness to different entropy settings, dependence on text length, robustness to watermark removal) may reduce the viable range of parameters further, as is generally the case for LLM watermark evaluations. On the other hand, more targeted detection methods may be more effective against this variant.

We included a summary of the consequences of this new finding in our Sec. 7 as a pointer for future work on finding practical undetectable schemes, and we are happy to adapt the message there further.

Q3: Can your parameter estimation techniques be used to learn the private key of the watermark?
No—this is a much harder problem that was explored in prior work. While learning the exact key is effectively not possible for the schemes we consider, learning the full effect of the key has been shown to be possible in some instances. For example, for the Unigram scheme proposed in [4] (a Red-Green scheme with a fixed Red and Green vocabulary independent of the context), [5] proposes a method to almost perfectly recover the Red/Green partition.

More generally, the field of watermark spoofing studies how to generate watermarked text without knowledge of the private key. Such spoofing attacks [6, 7, 8] only need to acquire partial knowledge of the effect of the watermark (for instance, partial knowledge of the Red/Green partition given a context) to be successful. Hence, most attacks on watermarking schemes do not rely on having full knowledge of the private key. However, as they often require some knowledge of the scheme parameters (e.g., context size), they could benefit from our parameter estimation as the first step in a more elaborate exploit of a scheme [6, 8]; chaining of attacks is an interesting future work item.