Statistical Text Watermarking via Vocabulary Partitioning

39 concepts33 papers1 proposal

As large language models (LLMs) generate text that is increasingly indistinguishable from human writing, identifying the provenance of text has become a high-stakes challenge. Traditional "reactive" detection methods attempt to classify text after it has been generated, creating an ongoing arms race between increasingly sophisticated generators and detectors (Ghosal et al.).

An alternative, proactive approach is generative watermarking. Instead of guessing whether a completed document is AI-generated, developers can embed an imperceptible statistical signature directly into the text during the model's decoding process (Chen et al.; Cao). The most prominent mechanism for achieving this is vocabulary partitioning.

The Core Intuition: Hiding a Signal in Plain Sight

To understand how vocabulary partitioning works, imagine a game where you must write a paragraph, but a secret rule gently nudges you to prefer words starting with the letters A through M over words starting with N through Z. If you write naturally, you will naturally use words from both halves of the alphabet. However, if you subtly bias your choices toward the first half whenever possible, a reader who knows the secret rule can count your word choices. If 80% of your words come from the first half of the alphabet, the reader can mathematically prove that you were following the rule, even if the paragraph reads completely naturally.

In LLM watermarking, this alphabet split is replaced by a mathematically rigorous division of the model's entire token vocabulary into "green lists" (preferred tokens) and "red lists" (restricted tokens) (Yang et al.).

Standard Generation:
[Token Logits] ---> [Softmax] ---> [Probability Distribution] ---> Sample Token

Watermarked Generation:
[Token Logits] ---> Add Bias to Green List Tokens ---> [Softmax] ---> Sample Token

The Step-by-Step Mechanism

The watermarking process alters how an autoregressive model selects the next token without changing the underlying model weights.

1. Dynamic Partitioning

At each generation step, the vocabulary must be divided into green and red lists. To ensure the watermark cannot be easily reverse-engineered or stripped away, this partitioning is typically dynamic. Kirchenbauer et al. and Zhu et al. demonstrate that a cryptographic hash of the preceding tokens can serve as a pseudo-random seed to split the vocabulary. Because the split depends on the context, the green list changes at every token position. Alternatively, for simpler or more robust implementations, a fixed, context-independent partitioning scheme can be used (Zhao et al.).

2. Logit Biasing

Once the vocabulary is split, the system modifies the raw prediction scores (logits) generated by the model. A constant scalar value—the logit bias—is added to the scores of all tokens on the green list (Zhao et al.; Lalai et al.).

When these modified logits are passed through the softmax layer, the probabilities of the green tokens are artificially inflated. Crucially, because the same constant is added to all green tokens, the relative rank-order of the model's natural preferences within that list is preserved (Zhao et al.). The model still chooses the most contextually appropriate word, but it is heavily encouraged to pick a green one.

3. Statistical Verification

To verify if a piece of text is watermarked, a detector with access to the same secret hashing key retraces the generation steps. At each token position, the detector computes the hash of the preceding tokens to reconstruct that step's green list. It then counts how many tokens in the text actually belong to their respective green lists.

If the text was written by a human or an unwatermarked model, the proportion of green tokens will hover around random chance (e.g., 50% if the vocabulary is split evenly). If the text is watermarked, the green token count will be significantly higher. This allows the detector to calculate a rigorous $p$-value representing the probability that such a high concentration of green tokens occurred by pure chance (Xie et al.).

The Entropy Problem: Balancing Quality and Detectability

The primary challenge of vocabulary partitioning is maintaining text quality. If the logit bias is too high, the model may force a green token even when a red token is the only grammatically or logically correct choice, severely degrading the model's ability to follow instructions (Tu et al.).

This tension depends heavily on entropy—the model's natural uncertainty at any given step:

  • High-Entropy Contexts: When a model is writing a creative essay, there are many valid choices for the next word. Biasing the model toward a green synonym (e.g., choosing "huge" over "large") does not hurt the text's fluency or meaning.
  • Low-Entropy Contexts: When a model is generating structured text, such as computer code or mathematical proofs, there is often only one correct token (e.g., a specific keyword or variable name). Forcing a green token here can break the code's syntax or logic.

To overcome this, the authors of Selective WatErmarking via Entropy Thresholding (SWEET) proposed applying the logit bias only when the model's natural prediction entropy exceeds a specific threshold. Similarly, advanced detection methods like Entropy-based Text Watermarking Detection (EWD) improve accuracy by giving more statistical weight to tokens chosen in high-entropy steps, where the watermark's influence was actually responsible for the model's choice (Lu et al.).

Vulnerabilities and the Limits of Robustness

While vocabulary partitioning provides a mathematically elegant solution for tracking AI-generated content, it is not infallible.

The most common threat is a paraphrasing attack, where an adversary rewrites the text or modifies variable names in code to "wash away" the watermark signal (Niess et al.; Suresh et al.). Because dynamic partitioning relies on the exact sequence of preceding tokens, changing even a single word alters the hash for all subsequent steps, breaking the detector's ability to reconstruct the original green lists.

Furthermore, as watermarking becomes more common, systems face the risk of watermark collision (Luo et al.). If a piece of text is processed or translated by multiple models, each applying its own logit-biasing scheme, the underlying probability distributions become tangled, effectively erasing the original provenance signal. Conversely, bad actors might attempt to spoof a watermark to falsely attribute malicious text to a specific model provider, though research shows these attempts usually leave behind distinct statistical artifacts that alert defenders to the forgery (Gloaguen et al.).

Key Foundational Work

Baselines for Identifying Watermarked Large Language Models (2023) — contributed 2 concept elements to this direction.
A Survey of Text Watermarking in the Era of Large Language Models (2023) — contributed 1 concept elements to this direction.
Combating Misinformation in the Age of LLMs: Opportunities and Challenges (2023) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_vocabulary_partitioning_8beffd25,
  title = {vocabulary partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/vocabulary-partitioning/rdr_8beffd259cc24468a12f099df07a3e5b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_vocabulary_partitioning_8beffd25_v1,
  title = {vocabulary partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/vocabulary-partitioning/rdr_8beffd259cc24468a12f099df07a3e5b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake