Majority Bit-Aware Watermarking For Large Language Models

arXiv:2508.03829 · cs.CL, cs.CR · Submitted 2025-08-05 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Majority Bit-Aware Watermarking For Large Language Models".

Jane: The gist The proposed method introduces a novel majority bit-aware encoding paradigm, MajorMark and MajorMark+, to relax the watermark signal strength from green list size,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper right now titled "Majority Bit-Aware Watermarking For Large Language Models". The main thing here is that they’re tackling a problem with LLMs generating harmful or deceptive content by embedding identifiable multi-bit messages into the text.

Jane: That sounds like a really practical concern because we're seeing these models deployed everywhere, and tracing misuse becomes harder if you can't reliably find that hidden signal. So, what’s the core challenge they identified with existing methods?

Tom: Existing perturbation-based methods have this fundamental trade-off between text quality and decoding accuracy. Basically, to keep the watermark detectable during decoding, you have to restrict the size of your preferred token set, which they call the green list.

Jane: And restricting that green list size inevitably degrades how good the generated text actually is. So how do they try to fix that inherent conflict between making it traceable and making it high quality?

Lu: The authors propose a new message encoding paradigm called majority bit-aware encoding. This approach relaxes the restriction on the green list size, which should allow for a strong watermark signal to stay present even when using a large green list.

Meng: Relaxing the size of something that's supposed to be restrictive sounds like it’s going to mess up the detection side of things, right? How do you ensure you still get a reliable signal back?

Tom: The strategy involves partitioning the entire vocabulary into several disjoint shards, where each shard corresponds to a specific bit in the message they want to embed. Then, during encoding, they construct that green list by uniting all the shards that match the message’s majority bit.

Jane: So if you have a message of length b, and this process happens during encoding, what's the immediate benefit they claim from this majority bit-aware encoding?

Lu: This strategy inherently guarantees a green list ratio gamma greater than or equal to zero point five, which the authors say is critical for preserving text quality. They show that MajorMark directly leverages this and expects an average green list ratio Emgamma of approximately zero point five plus one over the square root of two times pi times b.

Paper summary: Meng: If you use a large green list, what's the actual downside they are mitigating here? Is it just that the signal gets weaker?

Tom: It’s more than just getting weaker; it’s about making sure that even with a larger green list, you still have a strong watermark signal to work with when you try to decode the text later. They introduce two versions of this paradigm: MajorMark and MajorMark+.

Jane: What makes the second version, MajorMark+, different from the first one? Is it just more optimized for a specific situation?

Lu: Yes, they introduced MajorMark+ which is specifically optimized for longer messages. And to enhance its decoding accuracy, they replace boundary-sensitive clustering with a deterministic decoding method. This deterministic approach lets them recover the correct values of lambda and their occurrences h lambda i in the message for each block with high reliability.

Meng: Deterministic decoding sounds like it’s trying to bypass some kind of uncertainty that comes from using a large green list, which is what I worry about when we're deploying this at scale. What does that actually mean for running the model?

Tom: It means they are making the recovery process more predictable and less reliant on exact alignment between tokens. The experiments show that these methods achieve higher decoding accuracy and superior text quality compared to prior baselines. For instance, when b is sixty-four, MajorMark+ achieves a bit accuracy of ninety-five point two one percent on the Essays dataset.

Jane: So they’re showing that this new encoding method actually wins in both utility and accuracy when you compare it to what was out there before? What does that mean for real-world deployment?

Lu: They also discuss robustness. Both MajorMark and MajorMark+ are robust to paraphrasing noise because the attacks just dilute the shard distribution without removing its core structure. The decoding mechanisms rely on separability rather than exact alignment, which helps with sentence shuffling and character-level perturbations too.

Meng: So, if a user tries to slightly rephrase their text, this method should still be able to catch it? That’s important for real use cases.

Jane: Exactly. And what about the limitations they mention? Where does this approach stop working or what can't it do perfectly?

Paper summary: Tom: The paper mentions that existing zero-bit watermarking methods are inherently limited because service providers often need to embed more complex information, like user identifiers, model versions, or other metadata. This paper focuses on multi-bit watermarking, but the authors point out that they primarily focus on perturbation-based methods because they tend to achieve higher decoding accuracy.

Lu: And the specific limitation regarding their methodology is that while MajorMark+ is robust to sentence shuffling and character-level perturbations, the decoding mechanism relies on correctly synchronized tokens providing enough evidence for recovering the block message.

Meng: So, it sounds like this isn't a perfect solution for every possible noise type yet. What's the big picture implication if we look at what they’re actually proposing?

Jane: It means that instead of just picking one way to watermark, we have this new majority bit-aware encoding strategy that seems to offer a much better balance between keeping the generated text high quality and making sure the embedded message can be reliably recovered.

Tom: The whole point is moving away from just restricting the green list size as the main control for signal strength. They’re using this encoding approach to preserve a strong watermark signal even when you are using a large green list.

Lu: Ultimately, they show that by adopting this majority bit-aware encoding, you get better decoding accuracy and superior text quality compared to previous methods in the field. This is what the Majority Bit-Aware Watermarking For Large Language Models paper is all about.

Jane: So to wrap up on "Majority Bit-Aware Watermarking For Large Language Models", what's the main thing we need to remember about this work?

Tom: It’s that they propose two versions, MajorMark and MajorMark+, which use a majority bit-aware encoding strategy. This strategy lets them preserve a strong watermark signal in generated texts even when using a large green list.

Lu: The key is relaxing the restriction on the green list size from the perspective of signal strength versus quality trade-off, which is what they achieve with this novel paradigm.

Meng: For deployment, it means we can aim for better traceability in LLM services because the method actually improves both text utility and decoding accuracy compared to prior work.

Jane: It's about finding a better balance between making text usable and keeping the watermark detectable, which is what this paper is all about.

Conclusion: Tom: So today we’re looking at this paper called "Majority Bit-Aware Watermarking For Large Language Models". It basically tackles how to put a traceable watermark into LLM text without ruining the quality of what the AI actually writes.

Jane: Right, so if I'm driving and I see a text from an AI that might be misleading me, I want to know if it’s fake, right? So this paper is trying to make that tracing process better.

Lu: The authors are focusing on a new way to encode the message into the text. They call it majority bit-aware encoding.

Meng: So what does that actually mean in simple terms for me when I'm thinking about deploying this stuff? What's the big picture here?

Tom: Well, they’re relaxing how strictly you have to pick your preferred words—the green list—during the encoding phase. This should let them keep a strong watermark signal even if you use a pretty big green list for quality.

Jane: So, instead of saying "if we keep the token set small for detection," they're trying to say something different about how the message is mapped into those tokens?

Lu: Exactly. They partition the vocabulary into shards, and they build that preferred list based on which bit is most common in your hidden message. This guarantees a minimum green list ratio of zero point five.

Meng: A fifty-percent chance of getting a good quality text, I see. But what about making sure the decoder can actually find the hidden bit if we use a really big vocabulary?

Tom: That’s where they introduce MajorMark and MajorMark+. These are two versions. MajorMark uses the basic idea, and MajorMark+ is specifically optimized for when you need to embed longer messages.

Jane: And what makes that second version, the plus sign, actually better? Is it just because it handles longer things?

Lu: It’s more than just length optimization. They swap out boundary-sensitive clustering for a deterministic decoding method. This makes the recovery of the message values much more reliable during decoding.

Meng: So if I'm running this at scale, does that deterministic part mean it runs faster or uses less memory than some other methods?

Tom: The experiments show that MajorMark and MajorMark+ consistently beat prior baselines in both text quality and the actual ability to decode the message. We saw a bit accuracy of ninety-five point two one percent when they used sixty-four shards.

Jane: So, what does this mean for someone just listening to this show? It means that for AI text, we might finally have a way to put in a reliable tag so we can actually trust what the machine is spitting out.

Lu: It’s about finding that sweet spot between making the output look good and making sure you can still pull the hidden message out reliably.

Meng: I just need to see if this deterministic part holds up when I feed it messy, real-world data instead of clean test sets. That's the big unknown for production use.

Tom: It’s definitely a complex approach, but the numbers they’re showing about accuracy versus quality are pretty compelling for this type of watermarking method.

Jane: So the main thing to remember is that they moved away from just shrinking your preferred list and instead used this majority bit-aware encoding to keep the signal strong. And it opens up new ways to think about trustworthy AI text generation.

Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

University of Nevada, Reno · Oak Ridge National Laboratory

cs.CL, cs.CR

Submitted: 2025-08-05

Updated: 2026-10-13

Comments: This work has been accepted for presentation at NeurIPS 2026

Code: https://github.com/JiiahaoXU/MajorMark

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: The gist The proposed method introduces a novel majority bit-aware encoding paradigm, MajorMark and MajorMark+, to relax the watermark signal strength from green list size, allowing for a strong

Key concepts

Green List: The green list is a restricted set of tokens allowed during the encoding process. In current methods, this set must be small to ensure the watermark signal remains detectable upon decoding. This restriction often forces a compromise between maintaining high-quality generated text and successfully extracting the hidden message.
Majority Bit-Aware Encoding: This is a novel strategy where vocabulary is split into shards, each corresponding to a specific bit of the message. The green list for encoding is then constructed using tokens belonging to the majority bit across all shards. This allows for a larger token set while still guaranteeing a high probability of preserving the watermark signal.
MajorMark and MajorMark+: These are two implementations of the proposed strategy. MajorMark uses the basic majority bit-aware encoding, while MajorMark+ is optimized for long messages by partitioning them into blocks and using a deterministic decoding method. This optimization significantly improves decoding accuracy without sacrificing text quality.

Terminology

Accuracy — 2× in this paper · explained in 1 episode
Large Language Models (LLMs) — 1× in this paper · explained in 8 episodes

Summary

The gist The proposed method introduces a novel majority bit-aware encoding paradigm, MajorMark and MajorMark+, to relax the watermark signal strength from green list size, allowing for a strong watermark signal to be preserved in generated texts even when using a large green list. This strategy is designed to improve the trade-off between text quality and decoding accuracy in multi-bit watermarking for LLMs.

Problem Formulation and Motivation

The problem formulation seeks to maximize Prh m′ = m′ = Dec(Enc(f, xp, m))i s.t. Quality(x′g xp) ≥ τ. Existing perturbation-based methods exhibit an empirical trade-off between watermarked text quality and message decoding accuracy, as shown in Section 3. Specifically, a smaller γ can degrade the quality of watermarked text.

How it works

The majority bit-aware encoding strategy partitions the vocabulary into b disjoint shards, where each shard corresponds to a specific bit in the message. During encoding, the green list is constructed by uniting all shards that correspond to the message’s majority bit. This strategy inherently guarantees a green list ratio of γ ≥ 0.5, which is critical for preserving text quality.

MajorMark directly leverages this majority bit-aware encoding yielding an expected green list ratio Em[γ] ≈ 0.5 + 1/√2πb. MajorMark+ partitions the message into r blocks and applies the majority bit-aware encoding to each block independently, yielding a larger expected green list ratio Em[γ] ≈ 0.5 + 1/p2π(b/r). The key intuition is that only the correct seed s can reproduce the token-to-shard mappings used during encoding. MajorMark+ enhances decoding accuracy by replacing boundary-sensitive clustering with a deterministic decoding method. The deterministic approach allows for the recovery of the correct values of λi and its occurrences hλi in the message for each block with high reliability.

Experimental Results

Extensive experiments on state-of-the-art LLMs demonstrate that our methods achieve higher decoding accuracy and superior text quality compared to prior baselines. For instance, when b = 64, MajorMark+ achieves a BA of 95.21% on the Essays dataset. These results confirm that MajorMark and MajorMark+ consistently outperform existing baselines in both text utility and decoding accuracy.

Robustness and Generalization

Both MajorMark and MajorMark+ are robust to paraphrasing noise because the attacks dilute the shard distribution without removing its core structure. The decoding mechanisms rely on separability rather than exact alignment. Furthermore, MajorMark+ is robust to sentence shuffling and character-level perturbation because the correctly synchronized tokens provide enough evidence for recovering the block message.

Conclusion

We find that existing perturbation-based multi-bit watermarking methods rely on counting how frequently generated tokens fall within the reconstructed green list to decode the embedded message. To address this, we propose MajorMark and MajorMark+, both of which employ a novel majority bit-aware encoding strategy. Extensive experiments demonstrate that MajorMark and MajorMark+ consistently outperform existing baselines in both text utility and decoding accuracy.

Broader Impacts

Our methods improve multi-bit watermarking for LLM-generated text by achieving a better balance between text quality and message decoding accuracy. This can support practical traceability in LLM services, where service providers may need to embed user identifiers, model versions, or other metadata into generated outputs. Responsible deployment should include clear disclosure, privacy-aware message design, and careful interpretation of detection results.

The paper is 2508.03829.

Improvements for AI systems

Bold header: Majority Bit-Aware Encoding for Robust Watermarking

This strategy relaxes the watermark signal strength from the green list size by partitioning the vocabulary into disjoint shards and constructing the green list by uniting all shards that correspond to the message’s majority bit, which inherently guarantees a green list ratio of γ ≥ 0.5, which is critical for preserving text quality. This allows for a strong watermark signal to be preserved in generated texts even when using a large green list.

Bold header: MajorMark's Clustering-Based Decoding

MajorMark employs a clustering-based decoding strategy that operates on shard-level occurrence statistics and uses KMeans to partition shards into two clusters, with the cluster with the higher average token count, denoted by C, interpreted as corresponding to the majority bit λ. This allows for fine-grained message decoding where the correct value of λ is determined by which configuration produces a more skewed occurrence distribution.

Bold header: MajorMark+'s Deterministic Decoding for Long Messages

MajorMark+ enhances decoding accuracy by replacing boundary-sensitive clustering with a deterministic method that exhaustively enumerates all possible combinations of λi and hλi to recover the majority bit and its occurrences for each block. This approach eliminates the reliance on clustering, thereby avoiding sensitivity to ambiguous token counts and requires only (b/r − 1) × x decoding operations, making it efficient for long messages.

Abstract

The growing deployment of Large Language Models (LLMs) has raised concerns about their misuse in generating harmful or deceptive content. To address this issue, watermarking methods have been proposed to embed identifiable multi-bit messages into generated text for misuse tracing. However, existing methods often suffer from a fundamental trade-off between text quality and decoding accuracy. In particular, they have to restrict the size of the preferred token set (i.e., green list) during encoding to maintain a detectable watermark signal for decoding, which inevitably degrades generation quality. To improve this trade-off, we propose a novel message encoding paradigm called majority bit-aware encoding, which relaxes the watermark signal strength from the green list size. This strategy allows for a strong watermark signal to be preserved in generated texts even when using a large green list. We introduce two instantiations of this paradigm: MajorMark and MajorMark+, where the latter is specifically optimized for long messages. Extensive experiments on state-of-the-art LLMs demonstrate that our methods achieve higher decoding accuracy and superior text quality compared to prior baselines. The code is at https://github.com/JiiahaoXU/MajorMark.