W at ME : Towards Lossless Watermarking Through Lexical Redundancy (2024)

Abstract: Text watermarking has emerged as a pivotal technique for identifying machine-generated text. However, existing methods often rely on arbitrary vocabulary partitioning during decoding to embed watermarks, which compromises the availability of suitable tokens and significantly degrades the quality of responses. This study assesses the impact of watermarking on different capabilities of large language models (LLMs) from a cognitive science lens. Our finding highlights a significant disparity; knowledge recall and logical reasoning are more adversely affected than language generation. These results suggest a more profound effect of watermarking on LLMs than previously understood. To address these challenges, we introduce Watermarking with Mutual Exclusion (WatME), a novel approach leveraging linguistic prior knowledge of inherent lexical redundancy in LLM vocabularies to seamlessly integrate watermarks. Specifically, WatME dynamically optimizes token usage during the decoding process by applying a mutually exclusive rule to the identified lexical redundancies. This strategy effectively prevents the unavailability of appropriate tokens and preserves the expressive power of LLMs. We provide both theoretical analysis and empirical evidence showing that WatME effectively preserves the diverse capabilities of LLMs while ensuring watermark detectability.

## introduction the advent of large language models @xcite with human-level generative capabilities presents tremendous opportunities across diverse domains @xcite @xcite . however, their ability to synthesize high-quality text also raises widespread concerns about potential misuse, including the dissemination of misinformation @xcite figure 1 : an illustration of watme's advantage for lossless watermarking. the left panel depicts a vanilla lm with all words available during generation. the middle panel exposes the flaw in vanilla watermarking, which may assign all suitable tokens (e.g., 'ocean' and 'sea') to the red list, diminishing text quality. the right panel underlines how watme exploits lexical redundancy by applying a mutual exclusion rule between such words, ensuring at least one suitable word remains on the green list, thereby improving text quality. @xcite and the facilitation of academic dishonesty @xcite . this necessitates developing techniques to reliably attribute generated text to ai systems. existing approaches typically fall into two main paradigms. the first type attempts to distinguish machine-generated text by hunting for inductive statistical or linguistic patterns @xcite @xcite , employing methods that span from basic manual feature engineering to the intricate training of complex classifiers. however, as generative models continue improving, their outputs increasingly resemble the pattern of human writing, rendering statistical detectors ineffective @xcite @xcite . the second paradigm promotes a more proactive approach, advocating for direct intervention in the generative process to actively watermark model outputs @xcite @xcite . this strategy embeds identifiable fingerprints within machine-generated text, enabling provenance verification. as llms' capabilities continue to grow, this approach is more effective in detecting llm-generated text @xcite . however, introducing watermarks during text generation can significantly impact output quality, which has been a consistent challenge for model developers -how to effectively watermark while preserving text quality. recent studies have attempted to improve text quality by ensuring unbiased output distributions in watermarking @xcite , while employing pseudorandomness-guided perturbations or reweighting to adjust the original output distributions of llms. however, an unbiased distribution in expectation does not guarantee high text quality, and the use of these techniques reduces the effectiveness of watermark detection, especially in models that have undergone alignment training @xcite , thereby diminishing the practical utility of these methods. in this paper, we introduce a novel approach to text watermarking by leveraging engineered lexical redundancy during the decoding phase of language generation. our method utilizes the comprehensive set of tokens available to a language model, clustering them based on overlapping semantic or syntactic functionalities to create sets of interchangeable tokens. this process simulates redundancy within the lexical space, akin to the surplus pixels in images that facilitate watermarking in multimodal data @xcite . the motivation for this strategy arises from the challenge of applying traditional watermarking techniques to textual data. in contrast to the inherent redundancy found in images, the discrete and succinct nature of textual data offers little to no native redundancy, making it challenging to exploit redundancy in the textual space @xcite . by engineering lexical redundancy, our method not only surmounts the limitations imposed by the inherent properties of natural language but also paves the way for secure and efficient text watermarking. after exploring these redundancies, we exploit them via our novel algorithm, watme, which en-hances text quality by integrating a mutual exclusivity rule within the context of lexical redundancy during the watermarking process. specifically, watme refines the decoding process by explicitly assigning words within each redundant cluster to distinct 'green' or 'red' teams, ensuring that no single cluster is wholly allocated to one team. our approach confers two main advantages: (1) it enables the 'green' team to capture a broader array of semantics, thereby boosting the model's expressive power; and (2) it increases the probability that the llm selects the most appropriate word at each decoding step, e.g., in figure 1 , vanilla watermarking can assign all suitable words to the 'red' list, thus severely impairing performance. in contrast, our approach guarantees the presence of at least one appropriate word, thus preserving the model's expressiveness. building on these methodological advances, extensive theoretical and empirical evidence supports their effectiveness without compromising detection capabilities. these improvements significantly bolster the emergent abilities of large models under watermarks, surpassing the performance of baseline methods. our main contributions are as follows: ## related work early works on ai-generated text detection develop post-hoc detection methods to analyze machinegenerated text by treating the problem as a binary classification task @xcite @xcite . for instance, ope-nai has fine-tuned roberta @xcite to distinguish between human and gpt-2 generated texts (openai, 2019). however, existing detectors are found to be fragile against adversarial attacks @xcite and biased towards non-native english writers @xcite . moreover, as llms continue to advance, their generated outputs more closely resemble human-written text, rendering these methods progressively less effective. on the other side, watermarking, traditionally a copyright marking method @xcite , involves developers, users, and regulatory entities. developers choose an algorithm to subtly embed hidden modifications into data, which can be altered during user transmission. regulatory bodies can later extract this information to trace and regulate ai-generated content @xcite @xcite . in the context of natural languages, watermarking typically involves modifying content or structure. for example, rule-based methods @xcite or carefully designed neural encoders @xcite encrypt messages into text, which are then extracted using the corresponding rules and neural decoder. the discrete nature of natural language, however, presents a considerable challenge to this approach, as modifications can unintentionally degrade text quality or alter its intended meaning. for the detection of llm-generated texts, a pioneering watermarking technique @xcite partitions tokens into 'green' and 'red' lists, biases output distribution towards 'green' tokens, and creates patterns that are detectable yet imperceptible to humans. nevertheless, while yielding promising detection results, these methods may still degrade the textual quality and be vulnerable to the paraphrase attack. current efforts @xcite @xcite in this field aim to develop more robust watermarking methods capable of defending various user attacks. apart from improving robustness, a few studies have recognized the importance of enhancing the quality of text produced by watermarked llms. @xcite utilizes gumbel softmax to incorporate pseudorandomness-based randomness into the output distribution of language models. while this technique alters the probability distribution, the gumbel softmax ensures that the expected distribution remains approximately unchanged, thus rendering the watermarking process unbiased. recent work @xcite also shares a similar philosophy of employing reweighting technology for unbiased output distribution transformations, preserving the expected distribution unbiased. however, unbiased distribution can not guarantee unaffected text quality. furthermore, these methodologies have shown a marked decrease in detection performance, particularly for aligned llms @xcite . addressing these shortcomings, our research introduces a novel paradigm that exploits the intrinsic redundancy in the text generation process of llms to create more lossless watermarks, with a special emphasis on llms' emergent capabilities, thereby offering a watermarking solution that is both lossless and consistently detectable. ## method in this section, we begin by providing a summary of the preliminaries related to text watermarking. subsequently, we delve into an investigation of redundancy in the lexical space and demonstrate how this redundancy can be leveraged to develop a watermarking algorithm that achieves a higher degree of losslessness for large language models. finally, we employ mathematical analysis to elucidate the benefits of our proposed method. ## impact on emergent abilities the majority of research on text watermarking utilizes the c4 dataset @xcite as a basis for testing perplexity (ppl). however, watermarking not only impacts the fluency of text generation but also holds the potential to influence llms on a broader scale, such as emergent abilities. these unique abilities intrinsic to llms garner significant interest from users and stimulate curiosity within the research community. however, they are often overlooked in the field of text watermarking. although a consensus definition is lacking, emergent abilities are typically characterized in many studies @xcite @xcite as a model's capacity to perform specific tasks without training. in light of this, we propose to test and compare the performance of watme and vanilla watermark algorithms on different tasks using prompting technologies. to comprehensively test the impact of watermarking on these abilities, we attempt to categorize it into different scenarios for a more exhaustive examination. specifically, we draw upon cattell's cognitive theory @xcite , which bifurcates intelligence into crystallized and fluid intelligence. crystallized intelligence corresponds to the model's utilization of learned knowledge and experience, while fluid intelligence involves logical thinking and solving problems. correspondingly, we propose to examine crystallized intelligence through an assessment of the model's knowledge capabilities, and fluid intelligence through its ability to reason and solve mathematical problems. ## conclusion this study explores the impact of watermarking on the emergent abilities of llms-an aspect often neglected in the field. our findings highlight the considerable adverse effects of traditional watermarking methods on llms' emergent abilities, including knowledge recall and logical reasoning. in response, we introduced watme-a novel watermarking approach that leverages lexical redundancy. theoretical analysis and comprehensive empirical results indicate watme consistently preserves the expressive power of llms without compromising detection performance, enabling developers to encode watermarks with less disruption to user experience. the advancements with watme mark a stride in lossless watermarking, enabling developers to encode watermarks with less disruption to user experience. we hope to promote a better equilibrium between regulatory compliance and user satisfaction in llm development.