Watermarking of Large Language Models

Topics covered

The attribution problem

The fundamental challenge: nearly all near-term misuses of LLMs involve concealing that an AI system was involved.

• Homework plagiarism via ChatGPT (documented across US universities)
• Spam and propaganda (e.g., pro-Putin talking points in comment sections)
• Impersonation and false identity assumption
• Training-data pollution: if the internet increasingly contains LLM output, future models train on degraded data (biting their own tail)
• White House commitment (as of 2023) to watermark audio-visual content, though text remains undefined

Proposed solutions and their limitations

1. Manual/stylistic detection

• Some submissions contain dead giveaways ("as a large language model trained by OpenAI")
• Can sometimes eyeball suspicious text due to characteristic phrasing
• Unreliable and labor-intensive

2. Metadata approach

• Attach origin information to files (common for images/video)
• Fails for text: metadata is trivially removable; can't prove authorship if metadata is stripped

3. Database/hash-table approach

• Store all generated text in an encrypted hash table; users query to detect known outputs
• Problems: (a) false positives on deterministic outputs (e.g., Declaration of Independence); (b) impossible to guarantee privacy—clever queries could leak information about past conversations

4. Discriminator models (e.g., GPTZero, DetectGPT)

• Train a separate model to distinguish AI-generated from human text
• Fails in practice: high false-positive rates (flagged Shakespeare, Bible as AI-generated); students already falsely accused of cheating
• Accuracy insufficient for deployment

The watermarking approach

Core insight: Leverage probability distributions from the LLM during generation to embed a signal that doesn't degrade output quality.

The scheme (Gumbel-Softmax):

• Model outputs probabilities p_t,i over tokens for position t
• Introduce a pseudorandom function f that maps c-grams (context windows of c tokens) to pseudorandom values r_t,i ∈ [0,1]
• Selection rule: Choose token i that maximizes r_t,i^(1/p_t,i) (deterministic)
• Intuition: Low-probability tokens require r_t,i very close to 1 to be selected (unlikely). High-probability tokens have lower threshold. This encodes a signal without biasing away from the true distribution.

Detection:

• Compute the sum of log(1/(1 - r_t,i)) over all tokens
• If sum exceeds a threshold, declare watermark present
• Threshold controls false-positive/false-negative trade-off

Key properties:

• No degradation in output quality (the distribution remains unchanged—output is indistinguishable from normal LLM output except to someone who can distinguish the pseudorandom function from true randomness)
• Computational overhead: negligible (just the LLM cost + rounding error)
• Robustness: survives word changes, reordering, deletion as long as enough c-grams are preserved
• Can be applied as a wrapper to any LLM without white-box access

Mathematical foundations

Tokens required for detection (given tolerable error rate δ):

• Number of tokens needed: O(1/α² × log(1/δ))
• α = average entropy per token (conditional on previous tokens)
• For real text with α ~ 1 bit, hundreds of tokens suffice for 99.9% confidence
• In practice, a few hundred tokens for reasonable text, a few thousand for very high confidence

Why Gumbel-Softmax works: If r_t,i are uniform random, then log(1/(1 - r_t,i)) follows an exponential distribution with mean 1/p_t,i. Minimizing the sum (choosing token i) correctly samples from the original distribution.

Attacks and limitations

Simple attacks that destroy the watermark:

• Translation: Translate to French → Google Translate back → completely removes watermark (different c-grams)
• Paraphrasing: Ask LLM to insert "pineapple between each word"—changes all c-grams
• Summarization: Major edits remove watermark signal

Current defenses:

• Treat as a cat-and-mouse game (similar to SEO vs. Google): monitor for watermark-evasion prompts, block them server-side
• Raise effort required to misuse (doesn't prevent all attacks, just makes them harder)

Future direction: Semantic watermarking

• Current approach is token-level (syntactic); robust detection requires watermarking at semantic level (ideas rather than word sequences)
• Requires going inside the model to modify internal representations
• Challenge: must be detectable if you know what to look for but not detectable if you don't
• No current solution; marked as open research problem

Deployment challenges

Technical:

• Will quality degrade? (No, but customers may distrust it)
• Coordination: Can Anthropic, Google, OpenAI agree to deploy simultaneously? (Prevents user migration)
• Fairness: ESL speakers using LLM to improve English would be watermarked; is this fair?
• Access control: Who gets the detection key?
• Public access helps catch cheating but gives cheaters the tool to evade
• Restricted access (universities, journalists, verified services) requires gatekeeping
• Private access (keep to yourself) minimizes evasion but limits detection

Conceptual:

• What is the formal attack model? (Aaronson admits unsolved after a year of thought)
• When does watermarking provide defense? (Only when there is entropy; deterministic outputs cannot be watermarked)

Change-point detection for mixed documents

If a long document contains both watermarked (GPT) and non-watermarked (human) sections:

• View watermark scores as a random walk with regions of bias
• Use dynamic programming to find most-likely biased regions
• Avoids assuming Markov structure (which would bias accusation)
• Quadratic time algorithm; O(n^1.5) approximation exists

Notes

This talk bridges theory and practice. The mathematical framework is rigorous (based on properties of exponential distributions and pseudorandom functions) and the scheme achieves the stated goal of marking LLM output without quality degradation. The talk's strength is candid discussion of attack vectors and deployment barriers—Aaronson clearly lays out that robustness at the token level has fundamental limits and that a more principled defense (semantic watermarking) remains unsolved.

One overlooked challenge: the talk assumes a threat model where you want to catch deliberate evasion, but the fairness questions (ESL learners, legitimate private use) are harder to resolve. The observation that watermark strength vs. robustness trades off (via the c-gram parameter) is important: larger c means fewer tokens needed but easier to attack.

The scheme has not been deployed at OpenAI as of the talk date (2023), though a prototype was built by Hendrik Kirchner. Subsequent academic work (e.g., by Kirchenbauer et al.) published similar ideas independently and explored green/red-list approaches in parallel.