Duwak: Dual Watermarks in Large Language Models (2024)

Abstract: As large language models (LLM) are increasingly used for text generation tasks, it is critical to audit their usages, govern their applications, and mitigate their potential harms. Existing watermark techniques are shown effective in embedding single human-imperceptible and machine-detectable patterns without significantly affecting generated text quality and semantics. However, the efficiency in detecting watermarks, i.e., the minimum number of tokens required to assert detection with significance and robustness against post-editing, is still debatable. In this paper, we propose, Duwak, to fundamentally enhance the efficiency and quality of watermarking by embedding dual secret patterns in both token probability distribution and sampling schemes. To mitigate expression degradation caused by biasing toward certain tokens, we design a contrastive search to watermark the sampling scheme, which minimizes the token repetition and enhances the diversity. We theoretically explain the interdependency of the two watermarks within Duwak. We evaluate Duwak extensively on Llama2 and Vicuna under various post-editing attacks, against four state-of-the-art watermarking techniques and combinations of them. Our results show that Duwak marked text achieves the highest watermarked text quality at the lowest required token count for detection, up to 70% tokens less than existing approaches, especially under post paraphrasing.

## introduction large language models (llms) are widely adapted for natural language tasks, including copywriting @xcite , machine-translation @xcite , questioning and answering @xcite , and code generation @xcite . while llms achieve remarkable and human-like performance, there are increasing risks of abusing llm's @xcite to produce incorrect and adversarial content on social media and to commit fraud in academic rights. watermarking llm content is one of the essential solutions to govern the llm applications and guardrail their misuse and harm to the society, even requested by the governmental policies @xcite . much like physical watermarks, embedding watermark signals on llm-generated text provides the means to trace content to their generator as well as the llm models that constantly evolve. key criteria for watermarking generative language models are multiple folds: having minimal degradation of the generated content quality, imperceptible to humans for avoiding alteration, detectable by machines for rigorous auditing, and robust against post-text editing. recent studies show that a single watermark pattern can be hidden in generated text through either altering the underlying token probability distribution @xcite @xcite or modifying the sampling strategy @xcite @xcite . while the existing watermarks achieve multiple criteria, their practicability on short texts and post-edited text is limited, as the minimum number of tokens required for successful detection, e.g., low false positive rate, under those scenarios is high. in this paper, we propose a dual watermarking approach, duwak, which improves the watermark detection efficiency and text quality by embedding two independent secret patterns into the token probability distribution and sampling scheme. to detect the watermark, duwak searches for the union of these two watermarks-the enabler for efficient detection with a low token count. under duwak, we first modify the pre-activation logits of pseudo-randomly selected tokens seeded by a function (i.e., hash) of a prior token sequence and a secret key, similar to green-red list watermarking approaches @xcite @xcite . consecutively, we randomly split the token into the normal and watermark sampling set, which embeds an additional random number sequence seeded by a second secret key. the challenge lies in efficiently detecting watermarks without degrading quality. it is known that watermarking activation signals inevitably degrade the text quality due to the bias term on a pseudorandom selection of tokens @xcite . to counteract this degradation, we advocate the use of a quality aware sampling scheme-the contrastive search, which limits token sampling to top-k tokens resulting in the lowest similarity w.r.t. previous generated tokens. unlike the popular cryptographic sampling, the contrastive search marks sampling patterns, thereby improving the text expression, improving the diversity of token selection and thus the watermarked text quality @xcite . our contributions are summarized in the following: improving watermark efficiency, through duwak's joint dual watermarks patterns in the token probability distribution and sampling scheme. increasing generation diversity and robustness, by avoiding expression degradation of watermarked text. duwak includes a novel quality-aware sampling scheme based on the contrastive search. empirical evaluation showing the effectiveness of duwak against existing watermark solutions under nine post-editing attacks. thereby showing the minimum number of tokens required to reach detection accuracy is up to 70% lower than related work, with nearly the best text quality and diversity. the second step is to sample the token based on the estimated probability distribution. common sampling schemes differ in their objectives and complexity: greedy search, beam-search, topk sampling @xcite , nucleus-sampling (top-p) @xcite , multinomial (random) sampling, and contrastive search @xcite . watermarking llm watermarks are typically embedded in the process of next-token generation through altering: (i) the logit and probability @xcite @xcite and (ii) the sampling scheme @xcite @xcite . to change the probability distribution, the key idea is to split the vocabulary tokens into a green (preferred) and red list, @xmath0, via a random number that is hashed from a secret key and an aggregate of previous h tokens. the number of green tokens is controlled by hyper-parameter γ by taking |g| = γ|v|. the logit values of green tokens receive a bias δ, thereby increasing their probability estimates, thus increasing the likelihood of them being selected. the sampling scheme can remain the same as the original llm. consequently, watermarked text is expected to have an increase in the number of green tokens. in contrast, sampling-based approaches are deterministic while keeping the model's next token probability estimate untouched. @xcite propose an exponential scheme and choose the token detecting watermarking detecting watermarks requires inspecting a sequence of n tokens and computing their watermark likelihood score, s n . the exact score computation depends on watermarking methods. in the case of logit modification through the green-red list @xcite , every token is classified into the green or red list based on the random split, conditioned on the random number sequence seeded by prior tokens and secret key. the total number of green tokens is the score. as for the sampling approach, e.g., @xcite , computes a pre-determined threshold is exceeded by negative summation of @xmath1. here the intuition lies in the fact that a token with low p i would require an r i arbitrarily close to 1, thus limiting their contribution to the computed score. this metric essentially measures the aggregate deviation from the expected distribution of tokens under the manipulation of random number vector r. watermarking measures there are multiple measures for watermarking algorithms: text quality, detection efficiency, and robustness. in terms of quality, perplexity @xcite @xcite ) metrics, rating from another (larger) llm @xcite , and diversity @xcite are used to assess the (watermarked) llm text. as for detection efficiency and robustness, it measures the number of n tokens needed to achieve significant detection tests under differentattacks, e.g., insertion, deletion, and paraphrasing @xcite . z-statistic and p-value @xcite are commonly used to evaluate the signifi-cance of the detection test, assuming the detection scores follow the normal distribution with a mean of µ and standard deviation of σ. the null hypothesis of the detection test is that h 0 : the text is unwatermarked. the z-statistics represents the normalized observed score value, which is subtracted by the estimated mean and standard deviation. and, its corresponding p-value represents the probability of having a normalized score higher than observed z under the h 0 , i.e., the text is not watermarked. ## duwak: dual watermarking the objective of duwak is to maintain the watermarked text quality while keeping high detection efficiency, i.e., high detection confidence by inspecting a low number of tokens. duwak embeds two secret watermark signals sequentially in the token probability distribution and token sampling scheme as shown in fig. 1 . to mitigate the text distortion caused by modifying the token probability, we design a contrastive search sampling scheme that increases the diversity via selecting tokens with low similarity among the top-k ones. we elucidate the interdependency through the joint watermarking scheme of duwak, demonstrating that the two watermarks can be integrated efficiently with an efficiency guarantee. ## evaluation in this section, we first detail the evaluation setup on the llm prompts and evaluation tasks. the evaluation metrics are the quality of watermarked text and the token count needed to achieve certain detection p values under normal conditions and various post-editing attacks. we compare duwak against existing single watermark techniques and combinations thereof. ## related studies prior single watermark solutions embed the watermark signal at the token level with a modification of the generation process by modifying either the token probability distribution @xcite @xcite or sampling scheme @xcite @xcite . watermark in token probability distribution. @xcite design the very first single-bit watermark method for llm text generation, splitting tokens into a green and red list using a cryptographic key. to further improve the text quality and robustness, subsequent studies modify the criteria of green-red splits. @xcite prove that global red-green splits improve robustness against post-editing attacks, whereas @xcite propose to use the minimum hashed token to determine the red-green list. furthermore, to improve the governance of watermarks and provide additional information, e.g., copyright and timestamp, multi-bit watermarks @xcite @xcite are proposed, introducing messagespecific red-green lists. we note that such watermarks split the text into multiple sections, each of which has only a single watermark in their token probability, whereas our solution embeds up to two watermarks into a single token. watermark in sampling binary watermark @xcite samples the token based on the comparison of the predicted probability and the pseudo-random presentation. because of the fixed length of pseudo-random numbers, the llm can end up generating the same text for the same prompt. @xcite propose the usage of longer pseudo-random number sequences than the generated text itself and randomly choose the insertion location in the text to add the watermark. @xcite resort to watermarking via sentence-level sampling, which iteratively performs sentence-level rejection sampling until the sampled sentence falls within the watermarked region. we note that orthogonal to watermark detection is more general detection of whether text is synthesized by llms @xcite @xcite . however, as traceability to specific models cannot be provided, these detection works are limited in their application for the governance of synthesized text. ## conclusion in this paper, we propose a dual watermark scheme for llm, duwak, which embeds human imperceptible and machine detectable watermarks in token probability distribution and sampling schemes. combining two watermarks significantly decreases the minimum number of tokens for detecting watermarks with a desirable false positive rate, especially when encountering post-editing attacks. to avoid text quality degradation due to watermarking token probabilities, we design a contrastive search sampling scheme that samples tokens with the lowest similarity. we show the effectiveness of duwak by providing a theoretical lower bound on the watermarked tokens and extensive empirical evaluation. compared against existing single watermark solutions and combinations thereof, duwak provides a better watermarked text quality. this is especially highlighted in terms of diversity, and robustness against nine post-editing attacks, using up to 70% less tokens for detection.