TL;DR
While current LLM watermarking can tell you if a text was AI-generated, it usually can't tell you if a human (or another AI) has tampered with specific parts of it. This paper introduces Combinatorial Watermarking, a method that embeds specific repeating patterns into the text's vocabulary structure, allowing researchers to not only verify the source but precisely localize where insertions, deletions, or replacements have occurred.
What Problem Does This Paper Address?
As Large Language Models (LLMs) become ubiquitous, watermarking has emerged as the "gold standard" for provenance—proving that a specific block of text came from a specific model. However, most existing watermarks are global: they provide a single score for a whole document.
The authors identify a critical vulnerability: post-generation edits. If an adversary takes a watermarked AI output and changes a few key words to spread misinformation (a "spoofing attack"), a global detector might still flag the text as AI-generated, inadvertently "lending" the model's credibility to the tampered content. Currently, there is no standard way to identify exactly which spans of a watermarked text have been modified. This paper defines the new task of local post-generation edit detection and localization.
Methods
The core innovation is a move from simple "green-list" watermarking to Combinatorial Pattern-based Watermarking.
- Vocabulary Partitioning: The researchers divide the model's vocabulary into $r$ disjoint subsets (tags), labeled like $A, B, C, D$.
- Deterministic Patterns: During text generation, the model is forced to follow a specific cyclic pattern. For example, an "AB" pattern means the first token must come from set $A$, the second from $B$, the third from $A$, and so on. They also tested more complex patterns like "ACADBCBD."
- Logit Shifting: To enforce this, they apply a shift ($\delta$) to the logits of the tokens in the "correct" set for that position, making them much more likely to be sampled.
- Sliding Window Detection: To find edits, the detector slides a window (e.g., size $w=8$) over the text. It checks if the tokens in that window align with any cyclic shift of the original pattern.
- Local Statistics: If a window shows a "pattern violation," the local edit statistic drops. By aggregating these violations, the system can flag specific token indices as likely edits.
Datasets
The authors evaluated their method using:
- Base Models: LLaMA-2-7b, OPT-1.3b, and OPT-2.7b.
- Source Text: Prompts were sampled from the WikiText dataset.
- Simulated Edit Dataset: They constructed a dataset of 2,000 texts (average length 64 tokens) with edits uniformly distributed across three types: replacement, insertion, and deletion, with span lengths ranging from 1 to 6 tokens.
- Misinformation Attack Dataset: They used the Gemini API to realistically edit 139 watermarked texts, instructing it to introduce "clear misinformation" while changing 6 words or less.
Key Insights and Ideas
- Standard Watermarks are "Degenerate": The authors point out that existing methods like KGW (Kirchenbauer et al.) are essentially a repeating "AA" pattern. Because they don't care about the order of tokens relative to each other, they are notoriously bad at detecting deletions.
- The Power of Cyclic Order: By using a sequence (like $A \to B \to C$), a single deletion doesn't just remove a token; it breaks the entire chain for every overlapping window. This makes deletions—previously the hardest edit to find—highly detectable.
- Information Density vs. Quality: There is a fundamental trade-off. A more complex pattern (more tags) makes edits easier to find but restricts the model's choices more severely, which can increase perplexity (reducing text quality).
- Localization Tolerance: The authors introduce a "tolerance parameter" ($L$) for evaluation. Because a single edit can disrupt multiple surrounding windows, they count a detection as successful if it falls within $\pm L$ tokens of the true edit.
Key Results
- Superior Localization: The combinatorial patterns significantly outperformed baselines (KGW and Unigram). For example, on the OPT-1.3b model, the "ACADBCBD" pattern achieved 1.00 accuracy across almost all edit types and lengths, whereas the Unigram baseline dropped to 0.01 accuracy for 1-token deletions.
- Robustness to Real Attacks: In the Gemini-led misinformation test, the algorithm detected 1-token edits with 81.4% accuracy and 3-9 token edits with 91.7% accuracy, all while maintaining a low false alarm rate.
- Efficiency: The detection process is lightweight, taking less than one second to process a batch of 32 texts on a standard workstation GPU.
Limitations and Future Work
- Short Edit Sensitivity: While much better than previous methods, detecting very short edits (1-2 tokens) remains the most challenging scenario, especially when the watermarking strength ($\delta$) is low.
- Pattern Design Space: The study only explored patterns up to 4 unique tags. The authors suggest that longer or adaptive patterns might offer even better trade-offs between quality and detection.
- Black-box vs. White-box: The current detection is "black-box" (it only looks at the tokens). The authors note that if the detector had access to the model's logits (white-box), accuracy could be even higher.
- Text Quality: High-strength watermarking ($\delta > 5$) can noticeably impact the diversity and flow of the text, a hurdle for high-stakes creative writing.
Summary updated