Can we Watermark Low-Entropy LLM Outputs?

1. Problem Statement

The paper addresses a critical limitation in existing Large Language Model (LLM) watermarking schemes: the entropy requirement.

• Context: Watermarking aims to embed a hidden, undetectable code in LLM outputs to prove AI generation. Recent works (Christ et al. [CG24], Golowich et al. [GM24]) have achieved "provably undetectable" watermarks (computationally indistinguishable from original output) that are robust against adversarial edits.
• The Gap: These existing schemes rely on strong assumptions about the empirical entropy of the LLM's output tokens.
  • [GM24] requires a constant fraction of tokens to have entropy $O(\log |T|)$, where $|T|$ is the token alphabet size.
  • [CG24] requires entropy $\Omega(\log |T|)$ for large alphabets (unless using specific Huffman encodings with strong distributional assumptions).
• The Challenge: In realistic LLM usage, many tokens (e.g., common words, deterministically generated phrases, or low-variability contexts) have low entropy (often close to 1 bit or even 0). If the entropy is too low, existing schemes cannot reliably embed a watermark without biasing the output distribution (violating undetectability) or failing to recover the watermark (violating robustness).
• Core Question: Can we construct an undetectable and robust watermarking scheme for LLMs with large token alphabets where the per-token entropy is merely a constant (independent of the alphabet size or security parameter)?

2. Methodology

The authors propose a novel framework that bridges the gap between binary watermarking schemes and large-alphabet LLMs without incurring high entropy costs.

Core Approach: Hashing and Block-Based Embedding

Instead of converting tokens to binary (which increases entropy requirements) or using large-alphabet Pseudorandom Codes (PRCs) (which also require high entropy), the authors use a binary PRC combined with token hashing.

1. Binary PRC Foundation: The scheme relies on a binary Pseudorandom Error-Correcting Code (PRC) that is robust against substitutions and deletions. The PRC generates a pseudorandom bit string (codeword).
2. Hashing Tokens: For each token $t$ generated by the LLM, the scheme applies a random hash function $h: T \to \{0, 1\}$.
3. Embedding Strategy:
   • The scheme samples two independent tokens $t_0, t_1$ from the LLM's distribution $D$.
   • If $h(t_0) \neq h(t_1)$ (a "success" case), the scheme outputs the token $t_b$ such that $h(t_b)$ matches the current bit of the PRC codeword. This embeds the bit without biasing the distribution.
   • If $h(t_0) = h(t_1)$ (a "failure" case), the scheme outputs a random token. This introduces an error (a bit flip in the embedded codeword) with probability $1/2$.
4. Block-Based Hashing: To handle deletions and insertions, the authors do not use a unique hash function for every token (which would break alignment after edits). Instead, they split the output into blocks, each corresponding to one PRC codeword. A single hash function is reused for all tokens within a block.
   • Benefit: If tokens are deleted, the detector can still identify which block they belonged to and use the correct hash function to decode.
   • Trade-off: Reusing the hash function introduces correlation between errors, requiring careful analysis to ensure robustness.

Key Technical Insights

• Entropy Requirement: The scheme only requires that a constant fraction of tokens in a sufficiently long substring have 1 bit of empirical entropy. This is significantly lower than the $O(\log |T|)$ required by prior work.
• Error Analysis:
  • The authors prove that for tokens with $\ge 1$ bit of entropy, the probability of a "failure" (where $h(t_0)=h(t_1)$) is bounded.
  • Crucially, they show that even under random substitutions (where an adversary replaces tokens with synonyms or other tokens), the expected error rate remains below $1/2$ as long as the substitution is "random" (modeled as a channel independent of the specific PRC bit).
  • For random deletions, the block-based structure allows the decoder to skip missing tokens and attempt to recover the codeword from the remaining bits.

3. Key Contributions and Results

The paper presents four main theorems (and corresponding corollaries) establishing watermarking schemes under different assumptions:

A. Robustness Against Random Substitutions

• Result: A watermarking scheme robust against a $(1/2 - \epsilon)$ fraction of random substitutions.
• Assumptions: Subexponential hardness of the Learning Parity with Noise (LPN) problem (same as [CG24]).
• Entropy: Requires only $O(1)$ empirical entropy per token (specifically, a constant fraction of tokens with 1 bit of entropy).
• Significance: This is the first scheme to achieve undetectable, robust watermarking for large-alphabet LLMs with constant entropy requirements.

B. Robustness Against Random Substitutions and Deletions (Heuristic)

• Result: A scheme robust against random substitutions and a $(1-\epsilon)$ fraction of random deletions.
• Assumptions: LPN hardness + a "Natural Prompt" / "Sufficiently Variable" heuristic. This assumes the errors introduced by the embedding process and subsequent random substitutions behave like a Binary Symmetric Channel (BSC).
• Entropy: $O(1)$.
• Note: The authors acknowledge this heuristic assumption is strong and may not hold for pathological cases (e.g., "emoji attacks" where deterministic tokens are inserted).

C. Robustness Against Random Substitutions and Deletions (Unconditional/Stronger PRC)

• Result: A scheme robust against random substitutions and deletions without the heuristic assumption.
• Assumptions: Requires a binary PRC robust against adversarial substitutions and random deletions.
• Status: No such binary PRC is currently known to exist with these specific parameters, but the paper shows that if one exists, the watermarking scheme follows immediately.

D. Robustness Against Adversarial Edits (Insertions, Deletions, Substitutions)

• Result: A scheme robust against a constant fraction of arbitrary adversarial edits.
• Assumptions: Based on the recent "Permuted Codes" construction by [CGG+25].
• Trade-off: While it removes the heuristic assumption, it requires a larger substring of the output to have sufficient entropy (a constant fraction of the entire output, not just a substring) to prevent an adversary from targeting low-entropy regions. The robustness parameter for edits is small ($\tilde{O}(\delta^4)$).

4. Comparison with Related Work

• Advantage over [CG24]: Works directly on large token alphabets without converting to binary (which would destroy token-level attack robustness).
• Advantage over [GM24]: Drastically reduces the entropy requirement from logarithmic to constant, making it applicable to low-entropy natural language.

5. Significance

1. Bridging the Entropy Gap: This work demonstrates that high-entropy outputs are not a prerequisite for undetectable watermarking. This is crucial for practical deployment, as LLMs frequently generate low-entropy text (e.g., code, structured data, common phrases).
2. Token-Level Robustness: By operating on the token level rather than a binary translation, the scheme remains robust against practical attacks like paraphrasing (replacing a word with a synonym) or redaction, which would break binary-based schemes.
3. Theoretical Foundation: It establishes a new paradigm for watermarking: using a binary PRC as a "backbone" while mapping large-alphabet tokens to it via hashing. This decouples the robustness of the code from the entropy of the source.
4. Open Problems: The paper highlights that achieving robustness against adversarial edits without heuristic assumptions for low-entropy outputs remains an open challenge, dependent on future constructions of binary PRCs with stronger robustness properties.

In summary, the paper provides the first provably undetectable and robust watermarking framework for LLMs that functions effectively even when the model's output has very low entropy, significantly expanding the practical applicability of AI watermarking.