Advancing Beyond Identification: Multi-bit Watermark for Large Language Models (2024)

Abstract: We show the viability of tackling misuses of large language models beyond the identification of machine-generated text. While existing zero-bit watermark methods focus on detection only, some malicious misuses demand tracing the adversary user for counteracting them. To address this, we propose Multi-bit Watermark via Position Allocation, embedding traceable multi-bit information during language model generation. Through allocating tokens onto different parts of the messages, we embed longer messages in high corruption settings without added latency. By independently embedding sub-units of messages, the proposed method outperforms the existing works in terms of robustness and latency. Leveraging the benefits of zero-bit watermarking, our method enables robust extraction of the watermark without any model access, embedding and extraction of long messages ( \geq 32-bit) without finetuning, and maintaining text quality, while allowing zero-bit detection all at the same time.

## introduction how can we take a step further from merely identifying machine-generated text to proactively tackling misuses of large language models? the emergence of human-like language models and their easily accessible nature via web interface and apis have garnered unprecedented attention from the public and academia @xcite . the ability to follow complex instructions has boosted the productivity of various tasks such as programming, creative writing, and more. however, there have been increasing concerns about exploiting such language models to automate malicious activities such as spreading disinformation. this has necessitated the * corresponding author development of various methods to detect machinegenerated texts through techniques such as zeroshot detection, supervised training, watermarking, and more @xcite @xcite . these endeavors focus on the crucial task of identifying machine-generated content, which serves as a pivotal step in mitigating the potential harm caused by such text. however, when it comes to more pernicious misuses of large language models, such as the dissemination of misinformation and war propaganda on social media platforms for political or financial gains @xcite @xcite , the stakes are considerably higher, potentially leading to the erosion of social trust @xcite . in such circumstances, merely identifying the machinegenerated text may not suffice for the language model providers. instead, the ability to trace back to the adversary user responsible for generating the content becomes pivotal in counteracting such misuses. by doing so, the api providers can take a precursory measure to ban these users from their systems and allow media and social platforms, along with api providers, to collaborate with law enforcement authorities and take more decisive actions. all in all, watermarking the user information (or part thereof) can hold the adversary user accountable for potential harms facilitated through language model apis without having to store user queries @xcite , which would be prohibitively expensive and concern ordinary users who value privacy. all this can be achieved by embedding multibit information. recent works @xcite have achieved this by providing a distinct signal for each multi-bit message. while this is effective in low bit-width and low noise settings, maintaining the integrity of the watermark becomes increasingly difficult as the bitwidth increases due to the exponential number of possible messages. this is further aggravated in the presence of higher noise. in addition, having to consider all the possible messages also follows with the side effect of increased latency during encoding and/or decoding phase, the former of which degrading the end user experience. as opposed to this, our proposed method multibit watermark via position allocation (mpac) first allocates each token pseudo-randomly onto a subunit of the message to be embedded (fig. 1 ). the allocation of tokens onto different parts of the messages allows the embedding of longer messages without added generation latency and fares well in high corruption settings. then the message content at the allocated position determines the state to encode using a zero-bit watermarking scheme. for instance, when following the zero-bit watermarking scheme of @xcite , the message content decides which token subsets are biased. to increase load capacity, we can further partition the vocabulary into multiple "colored" lists instead of a single green list, effectively encoding multiple states for every token. our experiments show our method improves upon the runner-up baseline in terms of robustness of the @xmath0. ## related works watermarking has been studied in various types of multimedia such as image @xcite , video @xcite , audio @xcite , and natural language @xcite . following previous works @xcite , we use the term watermarking to denote embedding information into natural language in a manner that is robust against possible attacks given a watermarked text -in our case, this is the output generated by a language model given the prompt. this differs from steganography @xcite @xcite , which focuses more on the undetectability of a secret message that is embedded in the multimedia rather than robustness. for instance, @xcite sequentially encodes information via arithmetic coding every token. naively applying this deterministic encoding scheme makes the watermark extremely fragile to simple corruptions as shown in appendix fig. 7 . recently, methods relying on neural networks have shown progress in natural language watermarking, outperforming traditional methods that rely on rule-based watermarks @xcite . @xcite proposed an end-to-end framework where a decoder network predicts the encoded message. @xcite improved upon the quality of the watermarked text by using an algorithmic approach. building upon this, @xcite focused on robustness and capacity, outperforming previous works on both aspects. however, since the proposed method works at the sentence-level, any addition or removal of a sentence will fail to extract the watermark. moreover, these works cannot distinguish non-watermarked texts, making them unsuitable for distinguishing between machine text and human text. meanwhile, directly watermarking language models in a zero-bit manner during token generation has emerged as a promising approach for distinguishing language model outputs from human text @xcite while achieving robustness against realistic attacks @xcite . several works have improved upon @xcite , e.g., in low entropy generation tasks such as code generation @xcite , undetectability of the watermark @xcite , and its robustness @xcite . we focus on extending the prior work for a more proactive counteraction towards identifying malicious users of language models by embedding any information while maintaining the key advantages. concurrent to our work, fernandez et al. (2023a) and @xcite use the entire message to create a signal unique to each message. crucially, both works use the entire message content directly during embedding as input to the random seed generator, which leads to key differences in terms of robustness and latency. we further discuss their methodology in comparison with ours in the next section. aside from this, @xcite further utilize a proxy language model to enhance text quality. to give a rough estimate of the required message length for encoding a user id, consider the posix (group, 2018) standard used when creating usernames in operating systems. 65 characters (∼7 bits) are permitted by posix, meaning at least 35 bits are required to encode a username of 5 characters. accordingly, works in image watermarking embeds messages easily over 32-bits @xcite @xcite . our method makes this feasible by encoding each bit position independently. ## method we outline the multi-bit watermark protocol: ## discussions model bit acc. llama-2-7b .986 (.06) + chat .922 (.13) mistral-7b .987 (.06) + chat .977 (.08) opt-1.3b .982 (.07) to overestimating the statistics of non-watermarked human texts (fig. 8 ). this is because computing the statistics involved finding the maximum cell value for each position. one natural solution is to use a better statistic that models the maximum cell value of a multinomial distribution. empirically, we found that this performed on par or even slightly worse compared to the current approach, which may be due to the approximation error when using a small sample size. we give a more detailed discussion on this in appendix a.2. radix and colorlist proportion how do radix and colorlist proportion γ influence multi-bit watermark performance? for γ=.125, the benefits of enlarging r to 8 are saturated and show no statistical significance to @xmath3. while larger r allows more tokens to be assigned to each position by reducing the effective length of the message, it challenges the problem by increasing the number of possible answers (digits) per position. additionally, we observed that increasing radix trade-offs zero-bit performance for multi-bit performance. the observations are illustrated in fig. 6b . ## conclusion our findings demonstrate the effectiveness of embedding multi-bit message by allocating tokens to sub-units of the message. we show that this does not lead to quality degradation compared to its zerobit counterpart nor latency overhead as bit-width is increased. this unveils a novel prospect of counteracting high-stake misuse of large language models via api. we also analyze the trade-off between multi-bit watermark and the detection rate.