An Entropy-based Text Watermarking Detection Method (2024)

Abstract: Text watermarking algorithms for large language models (LLMs) can effectively identify machine-generated texts by embedding and detecting hidden features in the text. Although the current text watermarking algorithms perform well in most high-entropy scenarios, its performance in low-entropy scenarios still needs to be improved. In this work, we opine that the influence of token entropy should be fully considered in the watermark detection process, i.e. , the weight of each token during watermark detection should be customized according to its entropy, rather than setting the weights of all tokens to the same value as in previous methods. Specifically, we propose E ntropy-based Text W atermarking D etection ( EWD ) that gives higher-entropy tokens higher influence weights during watermark detection, so as to better reflect the degree of watermarking. Furthermore, the proposed detection process is training-free and fully automated. From the experiments, we demonstrate that our EWD can achieve better detection performance in low-entropy scenarios, and our method is also general and can be applied to texts with different entropy distributions. Our code and data is available. Additionally, our algorithm could be accessed through MarkLLM (CITATION).

## introduction the rapid advancements in large language models (llms) have enabled them to generate high-quality outputs indistinguishable from humans, and also achieve better performance on various real-world generation tasks. however, this gives rise to the potential risk of misuse. specifically, llm-generated assignments, including essays and codes, pose a threat to academic integrity. misusing llms to figure 1 : this figure shows that compared with watermarked texts with mostly high-entropy tokens, watermarked codes with mostly low-entropy tokens see significantly less green tokens, resulting in a small detection z-score. furthermore, on the bottom of the figure, we demonstrate that the green token ratio in tokens decreases as their entropy decreases. text watermarking algorithms can effectively alleviate the problem of llm misuse by embedding and detecting hidden features in llm-generated contents. for example, the watermarking algorithm proposed by @xcite (kgw) divides the llm's model vocabulary into two lists, green and red, and increases the logits value of tokens in the green list by a positive constant (watermark strength). the modified logits will bias the llm to sample most tokens from the green list. as a result, the watermarked text containing a dominant number of green tokens will be recognized by the watermark detector while human texts will not. however, the successful watermark generation is largely tied to the token entropy during text generation. under the watermark algorithm, the probability of sampling a token from the green list is proportional to its entropy, meaning that low-entropy tokens would produce far less green tokens than high-entropy tokens, as illustrated by figure 1 . in that case, green tokens will occupy only half of a watermarked low-entropy text, resulting in a smaller detection score and being mistakenly labeled as human-written. furthermore, to ensure the text quality of output contents, the watermark strength in the generator cannot be excessively enlarged to forcefully modify the logits and sample more tokens from the green list @xcite . consequently, a crucial problem is how to improve the watermark detector so that low-entropy watermarked texts with a limited number of green tokens can be successfully identified. @xcite propose a selective watermark detector named sweet to better reflect the watermark level in low-entropy texts. specifically, they only detect tokens that exceed a certain entropy threshold, thus excluding tokens that are difficult to be affected by the watermark generator. however, this method itself has three weaknesses. first, their method requires a manually-set entropy threshold by analyzing samples of code written by humans. second, their method also does not consider the distribution of token entropy, that is, their method treats all tokens that exceed the threshold as the same, while in fact the entropy of these tokens may vastly vary. third, the performance gain using the sweet detector is limited and there is still significant room for further advancement. to better address the low-entropy watermarking detection problem than previous methods, we introduce an entropy-based text watermark detection (ewd) algorithm to fully consider the role of entropy in the detection of a given text. specifically, we propose that the influence of a token during detection should be proportional to its entropy. furthermore, in order to fully reflect this positive relation between token entropy and detection influence, we utilize a monotonically-increasing and continuous function to generate influence weights from token entropy. by creating a gap between the weights of high entropy tokens and low entropy tokens, we ensure that if the watermark generation algorithm can hardly affect a low-entropy token, the state of that token will make minimal impact to the detection result. overall, our method has three major benefits. first, the method saves the trouble of altering the watermark generation process. second, compared to sweet, our method is more efficient as the acquisition of token weights is an independent and training-free process, avoiding the trouble of a human dataset or any manual operations. third, the proposed detection scheme can be applied to machine-generated texts of all entropy levels, not solely low-entropy texts. from the experiments, we demonstrate that the detection accuracy of ewd in low-entropy scenarios surpasses existing baselines. furthermore, ewd exhibits versatility in detecting texts of high entropy levels, as well as robustness against the back-translation watermark-removal attack. in summary, the contributions of our work are summarized as follows: in this section, we aim to review existing works on text watermarking algorithms. overall, text watermarking can be divided into two different categories: watermarking for existing texts and watermarking for llms @xcite . text watermarking for existing texts. watermark message can be embedded into existing text by performing a series of modifications, such as lexical substitutions @xcite @xcite @xcite . those methods typically replace words with their alternatives to place watermark. for example, @xcite used wordnet @xcite as his dictionary while munyer and zhong (2023) utilized a pretrained word2vec model to select the alternative words. to ensure that the repalced words would cause minimal changes to the text semantics, @xcite proposed a bert-based infill model to generate replacement with regard to the sentence meaning. to improve the robustness of the algorithm against possible corruptions, @xcite fine-tuned the infill model to generate consistent word distribution given several corrupted texts of the same origin. however, the level of modification to an existing text is often limited to protect text quality in the watermarked output. hence, watermarking for existing text is less favored due to its limited capacity and effectiveness. text watermarking for llms. watermark embedding can also be conducted during the llm generation phase, either by modifying the token sampling or model logits. @xcite introduced a technique that incorporates watermark message by predefining a random number sequence for sampling the tokens. to enhance resistance to text modifications, @xcite utilized the levenshtein distance in matching the text and numbers. for the latter, the most representative one that modifies the model logits is proposed by @xcite based on previous tokens during text generation. there are a number of works proposed on top of this algorithm with enhanced performance in payload @xcite , robustness @xcite @xcite @xcite and unforgeability @xcite . for example, @xcite extends the method to a multibit setting. wang et al. (2023) proposed to utilize a proxy llm for multi-bit message embedding. to increase robustness against editing attacks, zhao et al. (2023) proposed to set a universal green list during the generation process. liu et al. (2024b) proposed a different approach called sir which utilizes the semantic meaning of previous generated text to determine the green lists. inspired by liu et al. (2024b), he et al. (2024) firstly proposed the crosslingual watermark removal attack (cwra), then offered x-sir as a defense method against cwra. also, to enhance the unforgeability of text watermark, liu et al. (2024a) introduced a neural network for text generation and detection. in this work, we focus only on the detection of lowentropy texts. lee et al. (2023) designed a selective watermark generation and detection approach for low-entropy code generation. however, it requires a human code dataset to help manually determine the entropy threshold. to sum up, there lacks an effective method to improve the low-entropy detection problem. ## proposed method in this section, we will first explain the motivation by analysing the watermark generation effect on low-entropy tokens, then provide a detailed explanation of the proposed ewd. ## theoretical analysis in this section, we theoretically analyze the type-i and type-ii error of our proposed detection method. specifically, we compare ewd with two previous detection methods, kgw and sweet. to do so, we adopt the same steps as in kgw @xcite . each token in both watermarked and non-watermarked texts can either be green or red, so we can model it as a binomial distribution. while @xcite set the window size in the watermark generator as zero (one universal green list for all tokens) and exhibits major token dependence, i.e., the same tokens in the text are of the same color, in our case, where a nonzero window size is adopted, the token dependence is significantly weakened. for example, the same token with different prefix would exhibit different sampling result. therefore, to simplify and facilitate the process of theoretical analysis, we make the reasonable assumption that the sampling of each token is independent. hence, the sum of green tokens in the text can be approximated with a normal distribution n (µ, σ 2 ) with different sets of mean µ and variance σ 2 for different detection schemes. finally, we calculate and compare the probability of the sum surpassing or falling behind the detection threshold |s| g , which is the |s| g value in each detection function with a fixed z. ## experiments in this section, we first introduce the tasks and datasets used for watermarked text generation. then, we compare the performance of our ewd against several baselines on those datasets. next, we analyze the role of our proposed entropy-based weight and study the performance of ewd us-ing different weight computing functions. finally, we evaluate the detection performance without the original prompt, detection speed and robustness of our ewd. ## conclusion in this work, we propose a text watermark detection method called ewd that fully considers the influence of token entropy. we first establish the positive influence-entropy relation in the detection process, then utilize entropy for weight customization to fully reflect the proposed relation. we provide theoretical analysis on the detection properties of different methods in low-entropy scenarios. experiments validate the detection performance of our method in the low-entropy code generation task with a number of weight functions. furthermore, in high-entropy scenarios, our method would achieve similar performance as previous works in detection accuracy, detection speed and robustness.