💬 NLP

Majority Bit-Aware Watermarking For Large Language Models

This paper introduces "Majority Bit-Aware Watermarking," a novel encoding paradigm with two instantiations (MajorMark and MajorMark $^{+}$ ) that resolves the trade-off between text quality and decoding accuracy in LLM watermarking by preserving strong watermark signals even with large green lists.

Original authors: Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine Large Language Models (LLMs) as incredibly talented chefs who can cook up almost any dish (text) you ask for. The problem is, sometimes bad actors use these chefs to cook up "poisoned" meals—fake news, scams, or harmful content. To catch them, we need a way to tag the food so we know exactly which chef made it. This tag is called a watermark.

However, there's a catch. In the past, putting a watermark on the text was like putting a heavy, clunky stamp on a delicate piece of paper. The more visible the stamp (to make it easy to find later), the more it ruined the paper's texture (the quality of the writing). If the stamp was too small to ruin the paper, it was too faint to be found.

This paper introduces a new way to watermark text called MajorMark and MajorMark+. It solves the "quality vs. detectability" problem using a clever trick involving majority rules and shards.

Here is how it works, broken down into simple concepts:

1. The Old Way: The "Small Green List" Problem

Think of the AI's vocabulary (all the words it can use) as a giant bag of marbles.

The Old Method: To hide a secret message, the AI was forced to pick its next word only from a very small handful of "green" marbles (maybe 25% of the bag). It ignored the rest.
The Trade-off: If the green list was too small, the AI was forced to pick weird, unnatural words just to fit the rule, making the story sound robotic. If the green list was big (to keep the story natural), the secret message became so faint that it was impossible to find later.

2. The New Idea: The "Majority Bit" Strategy

The authors realized they didn't need to restrict the AI to a tiny list. Instead, they used a voting system.

Imagine the secret message is a long string of 0s and 1s (like 110111).

The Trick: The system looks at the message and asks, "Which number appears more often?" In 110111, the number 1 is the "Majority Bit."
The Green List: Instead of picking a tiny list, the AI is allowed to pick from any word that corresponds to a "1" in the message. Since the "1" is the majority, this green list is huge (at least 50% of all words!).
The Result: Because the AI has so many natural-sounding words to choose from, the text sounds perfect. But because the AI is still slightly nudged toward the "1" words, the secret message is still there, just hidden in the statistical pattern of which words were chosen.

3. MajorMark: The "Cluster Detective"

MajorMark uses this majority strategy.

Encoding: The AI writes the text, nudging it slightly toward words that match the majority bit of the secret message.
Decoding: To read the message back, a detective (the decoder) looks at the text and counts how many times words from different "groups" (shards) appeared.
The Analogy: Imagine the words are sorted into two bins. If the secret message was "1", the bin for "1" will have slightly more marbles than the bin for "0". The decoder uses a simple clustering tool (like sorting marbles by color) to see which bin is heavier. If one bin is clearly heavier, it knows the secret message was "1".

4. MajorMark+: The "Block-by-Block" Upgrade

What if the secret message is super long? The "Majority Bit" might not be as obvious, making the signal weaker.

The Solution: MajorMark+ chops the long message into smaller blocks (like cutting a long rope into shorter segments).
How it works: It applies the "Majority Bit" rule to each small block independently.
The Benefit: This keeps the "green list" large for every single block, ensuring the text stays high-quality even for very long messages. It also uses a more precise "counting" method to find the message, making it harder to miss.

Why This Matters (According to the Paper)

The authors tested this on top AI models and found:

Better Quality: The watermarked text sounds much more natural (lower "perplexity") than previous methods because the AI isn't forced to pick from a tiny, restrictive list.
Better Detection: Despite the text sounding natural, the secret message is actually easier to find and decode accurately than with older methods.
Robustness: Even if someone tries to edit the text (like cutting and pasting parts or rephrasing sentences), the watermark usually survives because the statistical "heaviness" of the majority bits remains detectable.

In summary: The paper proposes a new way to tag AI text that stops the AI from having to choose between sounding human and being traceable. By using a "majority vote" system to select which words get a tiny boost, they allow the AI to write naturally while still embedding a strong, recoverable secret message.

Technical Summary: Majority Bit-Aware Watermarking for Large Language Models

Problem Statement

The widespread deployment of Large Language Models (LLMs) has introduced significant security and ethical challenges, including the generation of harmful or deceptive content. While watermarking techniques have been proposed to trace the origin of generated text, existing multi-bit watermarking methods face a fundamental trade-off between text quality and decoding accuracy.

Current perturbation-based methods (e.g., MPAC, RSBH) rely on counting the frequency of tokens that fall within a "green list" (a subset of the vocabulary) to decode embedded messages. To ensure a strong watermark signal for accurate decoding, these methods typically restrict the size of the green list (green list ratio $\gamma$ ). However, a smaller $\gamma$ forces the model to select from a narrower set of contextually suitable tokens, degrading the fluency and quality of the generated text. Conversely, increasing $\gamma$ to preserve text quality weakens the watermark signal, reducing decoding accuracy. The paper identifies this empirical trade-off as a critical bottleneck in current multi-bit watermarking.

Methodology

The authors propose a novel encoding paradigm called Majority Bit-Aware Encoding, which decouples watermark signal strength from the strict constraints of green list size.

Core Concept: Majority Bit-Aware Encoding

Instead of mapping specific message bits to specific token subsets, the method leverages the statistical property of the message's majority bit ( $\lambda$ ).

Vocabulary Partitioning: The vocabulary $V$ is partitioned into $b$ disjoint shards, where each shard corresponds to a specific bit position in the $b$ -bit message.
Green List Construction: The green list $G$ is constructed as the union of all shards corresponding to the message's majority bit. If the majority bit is 1, $G$ includes all shards for bits where $m_i=1$ ; if 0, it includes all shards where $m_i=0$ .
Signal Preservation: Since the majority bit appears at least $\lceil b/2 \rceil$ times, this strategy guarantees a green list ratio of $\gamma \ge 0.5$ . This allows for a large green list (preserving text quality) while still maintaining a strong, detectable signal because the decoding objective shifts from counting token frequencies to inferring which specific shards were boosted.

Proposed Methods

The authors instantiate this paradigm into two methods:

MajorMark:
- Encoding: Applies majority bit-aware encoding directly to the entire $b$ -bit message. Theoretical analysis shows the expected green list ratio is $E_m[\gamma] \approx 0.5 + 1/\sqrt{2\pi b}$ .
- Decoding: Uses a clustering-based decoder. It reconstructs the token-to-shard mapping for each token and aggregates shard-wise token counts. A clustering algorithm (e.g., K-Means) partitions the shards into two groups based on occurrence frequency. The group with the higher average count corresponds to the majority bit, allowing the recovery of the full message.
- Hash Function: To prevent repetitive green lists caused by frequent words, the hash seed incorporates the previous two tokens ( $x_{t-1}, x_{t-2}$ ) and the majority bit $\lambda$ .
MajorMark+:
- Optimization: Designed to improve performance for longer messages where the gain in $\gamma$ from MajorMark diminishes as $b \to \infty$ .
- Block-Wise Encoding: The message is divided into $r$ blocks. Majority bit-aware encoding is applied independently to each block. This yields a larger expected green list ratio: $E_m[\gamma] \approx 0.5 + 1/\sqrt{2\pi(b/r)}$ .
- Deterministic Decoding: Replaces the clustering approach with a deterministic decoding method. Instead of relying on unsupervised clustering, the decoder exhaustively enumerates possible combinations of the majority bit and its occurrence count for each block. It selects the configuration that produces the most skewed shard-wise token distribution. This eliminates sensitivity to clustering boundaries and improves accuracy, particularly under weak watermark biases.

Key Contributions

Novel Encoding Strategy: The paper introduces majority bit-aware encoding, which relaxes the dependency of watermark detectability on a small green list size, effectively breaking the quality-accuracy trade-off.
Two New Methods: The authors present MajorMark and MajorMark+, both utilizing the new encoding strategy. MajorMark+ specifically addresses the scalability of the method for long messages through block-wise processing and deterministic decoding.
Theoretical Guarantees: The paper provides theoretical proofs demonstrating that both methods guarantee a green list ratio of $\gamma \ge 0.5$ , with expected ratios strictly greater than 0.5 for finite message lengths.
Comprehensive Evaluation: Extensive experiments on state-of-the-art LLMs (e.g., LLaMA-2, Qwen, Gemma) across various tasks (text completion, story generation, summarization) and datasets (C4, Essays, OpenGen) validate the approach.

Experimental Results

The authors evaluated their methods against state-of-the-art baselines (DepthW, CycleShift, MPAC, RSBH) using metrics for Bit Accuracy (BA), Perplexity (PPL) (as a proxy for text quality), and Top-5 Hit Rate.

Superior Trade-off: MajorMark and MajorMark+ consistently achieved higher decoding accuracy and lower perplexity (better text quality) than existing methods. For instance, with a message length $b=64$ , MajorMark+ achieved a BA of 94.82% and PPL of 6.29, outperforming RSBH (BA 89.74%, PPL 6.85).
Robustness: The methods demonstrated robustness against post-generation editing attacks, including Copy-Paste and Paraphrase attacks. While all methods suffered under Paraphrase attacks, MajorMark and MajorMark+ maintained competitive performance compared to baselines.
Efficiency: The decoding complexity of MajorMark+ is linear in the number of blocks ( $b/r - 1$ ), making it significantly more efficient than exponential-time enumeration methods (like CycleShift) and faster than RSBH.
Generalization: The methods showed strong generalization across different model architectures (LLaMA, Qwen, Gemma) and downstream tasks.

Significance and Claims

The paper claims that the proposed Majority Bit-Aware Encoding paradigm fundamentally improves the viability of multi-bit watermarking for LLMs. By shifting the decoding objective from token frequency counting to shard selection inference, the method allows for the use of large green lists without sacrificing decoding accuracy.

The authors emphasize that their methods enable service providers to embed complex metadata (such as user identifiers or model versions) into generated text while maintaining high text utility. This addresses a critical gap in current watermarking research, where high-quality text generation has often been compromised by the need for strong watermark signals. The work suggests that MajorMark and MajorMark+ are practical candidates for real-world deployment in LLM-as-a-Service scenarios, offering a balanced solution for origin tracing and misuse investigation.