Majority Bit-Aware Watermarking For Large Language Models
Jiahao Xu, Rui Hu, Zikai Zhang · 2025
Read Majority Bit-Aware Watermarking For Large Language Models by Jiahao Xu, Rui Hu, Zikai Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03829.txt.
Introduction
Jiahao Xu and co-authors loosen a knot in watermarking language models. Multi-bit marks hidden in generated text let owners trace misuse, but strong marks have meant shrinking the set of favored words, which dulls the writing. Weak marks protect quality yet fail to decode. Their fix makes the encoding aware of the message's majority bit.
By tying signal strength to that majority rather than to the favored set's size, a large favored set can still carry a clear mark. Two versions follow: MajorMark, and MajorMark+ tuned for long messages. Tests on current top models show higher decoding accuracy and better text quality than earlier methods at once, breaking the old trade-off.
Catalog record
| CREATOR | Jiahao Xu, Rui Hu, Zikai Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-03829
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Majority Bit-Aware Watermarking For Large Language Models Jiahao Xu, Rui Hu, Zikai Zhang Abstract The growing deployment of Large Language Models (LLMs) in real-world applications has raised concerns about their potential misuse in generating harmful or deceptive content. To address this issue, watermarking techniques have emerged as a promising solution by embedding identifiable binary messages into generated text for origin verification and misuse tracing. While recent efforts have explored multi-bit watermarking schemes capable of embedding rich information such as user identifiers, they typically suffer from the fundamental trade-off between text quality and decoding accuracy: to ensure reliable message decoding, they have to restrict the size of preferred token sets during encoding, yet such restrictions reduce the quality of the generated content. In this work, we propose MajorMark, a novel watermarking method that improves this trade-off through majority bit-aware encoding. MajorMark selects preferred token sets based on the majority bit of the message, enabling a larger and more flexible sampling of tokens. In contrast to prior methods that rely on token frequency analysis for decoding, MajorMark employs a clustering-based decoding strategy, which maintains high decoding accuracy even when the preferred token set is large, thus preserving both content quality and decoding accuracy. We further introduce MajorMark + , which partitions the message into multiple blocks to independently encode and deterministically decode each block, thereby further enhancing the quality of watermarked text and improving decoding accuracy. Extensive experiments on state-of-the-art LLMs demonstrate that our methods significantly enhance both decoding accuracy and text generation quality, outperforming prior multi-bit watermarking baselines. 1 Introduction The rapid advancement and widespread deployment of Large Language Models (LLMs) have fundamentally reshaped numerous domains, from education and customer support to sophisticated content generation, owing to their capacity for highly fluent and contextually relevant text. However, this powerful generative capability simultaneously introduces considerable security and ethical challenges. Malicious users can leverage LLMs to produce harmful content, such as fake news, phishing emails, and fraudulent reviews ( Qu et al. 2024 ) . To mitigate these risks, developing watermarking techniques is essential. By embedding an imperceptible yet verifiable signal within generated text, watermarking enables effective origin tracing and attribution of misuse ( Liu et al. 2024b ; Wu et al. 2025 ; Pan et al. 2024 ) . A typical text watermarking method comprises an encoder that embeds a specific message (such as a yes/no signal) into the generated content and a corresponding decoder designed to extract this message. This work focuses on a common watermarking scenario ( Yoo, Ahn, and Kwak 2024 ; Li, Bai, and Cheng 2024 ; Qu et al. 2024 ) , where a cloud-based LLM-as-a-Service provider adopts a watermarking mechanism to uniquely mark each LLM-generated output for a user prompt. The decoder can then be applied to potentially unverified text to recover the embedded message. The key of watermarking is to ensure high decoding accuracy while preserving the utility of the generated content. The first LLM watermarking scheme, KGW ( Kirchenbauer et al. 2023 ) , was designed to encode a zero-bit message–a yes/no signal indicating that an LLM generated the text. During encoding, at each LLM token generation step, KGW pseudo-randomly selects a green list \mathcal{G} of tokens from the vocabulary \mathcal{V} and then strategically boosts their logits to increase their sampling probability for the current token being generated. During decoding, KGW reconstructs the green list for each token within the target text and computes the proportion of tokens that fall into their respective green lists. If this proportion is statistically significant (measured via a z -test), the target text is verified as watermarked and, consequently, generated by an LLM. A series of subsequent studies have extended this method to design zero-bit watermarking schemes with enhanced decoding accuracy ( Kuditipudi et al. 2024 ; Kirchenbauer et al. 2024 ; Wang et al. 2025 ; Lee et al. 2024 ) . However, zero-bit watermarking methods are inherently limited when the service providers need to embed more complex information, such as user identifiers, model versions, or other metadata. To address this, recent studies ( Yoo, Ahn, and Kwak 2024 ; Li, Bai, and Cheng 2024 ; Wang et al. 2024 ; Fernandez et al. 2023 ; Qu et al. 2024 ; Jiang et al. 2024 ; Yoo et al. 2023 ) have explored multi-bit watermarking, designed to embed a binary message \mathbf{m} of length b\geq 2 . In some such schemes ( Li, Bai, and Cheng 2024 ; Wang et al. 2024 ; Fernandez et al. 2023 ) , a unique watermark pattern is designed for each of the 2^{b} possible messages. This necessitates a brute-force search across all 2^{b} message candidates during decoding to determine which, if any, was embedded, a process that quickly becomes computationally infeasible as message length b increases. To improve decoding efficiency, advanced methods such as MPAC ( Yoo, Ahn, and Kwak 2024 ) and RSBH ( Qu et al. 2024 ) divide the message into smaller blocks, each of which is independently encoded into the text. During decoding, only the candidate message for each block needs to be identified, thereby reducing the overall search space. However, existing multi-bit watermarking literature has primarily focused on decoding accuracy and efficiency, while the utility of watermarked text in encoding is less discussed. There are two key factors that determine the utility of watermarked text: the green list ratio, defined as \gamma=|\mathcal{G}|/|\mathcal{V}| , and the watermarking bias for boosting green lists’ logits. These are typically treated as hyperparameters in existing methods. In this work, we focus on studying the impact of the green list ratio \gamma and leave the investigation of the latter factor as future work. We find that, for existing methods, a larger \gamma leads to improved utility of the watermarked text, as a broader green list offers more choices for contextually suitable tokens during generation. In the extreme case where \gamma=1.0 (i.e., the entire vocabulary constitutes the green list), the logit distribution remains unchanged after boosting. Conversely, a larger \gamma undesirably leads to reduced decoding accuracy. This is because the decoding process in existing methods relies on counting the frequency of tokens that appear in their green lists. As a result, a larger green list provides a weaker statistical signal above random chance, making it harder to distinguish watermarked text reliably. Based on this observation, we propose a novel watermarking paradigm that (1) eliminates the need for tuning the green list ratio \gamma , (2) improves the utility of watermarked text, and (3) enhances decoding accuracy. Specifically, our method leverages the inherent dominant occurrence of the majority bit in the message to guide the construction of the green list \mathcal{G} , ensuring a guaranteed green list ratio of \gamma\geq 0.5 . Unlike existing approaches that rely on counting how frequently generated tokens fall into \mathcal{G} for decoding, we avoid such frequency-based heuristics. Instead, we recover the embedded message by analyzing the occurrence of tokens across predefined vocabulary shards, enabling more accurate decoding. Our key contributions are summarized as follows: • We propose a major ity bit-aware water mark ing method, MajorMark, which leverages the majority bit in the b -bit binary message to generate the green list. This design guarantees that \gamma\geq