# WatME: Towards Lossless Watermarking Through Lexical Redundancy

arXiv: https://arxiv.org/abs/2311.09832 · HTML: https://mlsanity.com/paper/2311.09832/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 16 Nov 2023.

## Builds on (most cited first, 28 of 28)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [GLTR: Statistical Detection and Visualization of Generated Text](https://mlsanity.com/paper/1906.04043/) (2019)
- [Documenting Large Webtext Corpora: A Case Study on the Colossal Clean Crawled Corpus](https://mlsanity.com/paper/2104.08758/) (2021)
- [Can AI-Generated Text be Reliably Detected?](https://mlsanity.com/paper/2303.11156/) (2023)
- [Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring](https://mlsanity.com/paper/1802.04633/) (2018)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Generate rather than Retrieve: Large Language Models are Strong Context Generators](https://mlsanity.com/paper/2209.10063/) (2022)
- [GPT detectors are biased against non-native English writers](https://mlsanity.com/paper/2304.02819/) (2023)
- [Automatic Detection of Machine Generated Text: A Critical Survey](https://mlsanity.com/paper/2011.01314/) (2020)
- [Prompting and Evaluating Large Language Models for Proactive Dialogues: Clarification, Target-guided, and Non-collaboration](https://mlsanity.com/paper/2305.13626/) (2023)
- [Regulating ChatGPT and other Large Generative AI Models](https://mlsanity.com/paper/2302.02337/) (2023)
- [Chain-of-Thought Hub: A Continuous Effort to Measure Large Language Models' Reasoning Performance](https://mlsanity.com/paper/2305.17306/) (2023)
- [On the Possibilities of AI-Generated Text Detection](https://mlsanity.com/paper/2304.04736/) (2023)
- [Protecting Intellectual Property of Language Generation APIs with Lexical Watermark](https://mlsanity.com/paper/2112.02701/) (2021)
- [Beyond Factuality: A Comprehensive Evaluation of Large Language Models as Knowledge Generators](https://mlsanity.com/paper/2310.07289/) (2023)
- [Attacking Neural Text Detectors](https://mlsanity.com/paper/2002.11768/) (2020)
- [Frustratingly Easy Edit-based Linguistic Steganography with a Masked Language Model](https://mlsanity.com/paper/2104.09833/) (2021)
- [Towards Robust Personalized Dialogue Generation via Order-Insensitive Representation Regularization](https://mlsanity.com/paper/2305.12782/) (2023)

## Built on by (most cited first, 27 of 27)

- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [Copyright Protection for Large Language Models: A Survey of Methods, Challenges, and Trends](https://mlsanity.com/paper/2508.11548/) (2025)
- [CoheMark: A Novel Sentence-Level Watermark for Enhanced Text Quality](https://mlsanity.com/paper/2504.17309/) (2025)
- [Invisible Entropy: Towards Safe and Efficient Low-Entropy LLM Watermarking](https://mlsanity.com/paper/2505.14112/) (2025)
- [DITTO: A Spoofing Attack Framework on Watermarked LLMs via Knowledge Distillation](https://mlsanity.com/paper/2510.10987/) (2025)
- [WaterMod: Modular Token-Rank Partitioning for Probability-Balanced LLM Watermarking](https://mlsanity.com/paper/2511.07863/) (2025)
- [From Trade-off to Synergy: A Versatile Symbiotic Watermarking Framework for Large Language Models](https://mlsanity.com/paper/2505.09924/) (2025)
- [Paladin: Defending LLM-enabled Phishing Emails with a New Trigger-Tag Paradigm](https://mlsanity.com/paper/2509.07287/) (2025)
- [Enhancing Watermarking Quality for LLMs via Contextual Generation States Awareness](https://mlsanity.com/paper/2506.07403/) (2025)
- [CATMark: A Context-Aware Thresholding Framework for Robust Cross-Task Watermarking in Large Language Models](https://mlsanity.com/paper/2510.02342/) (2025)
- [Distilling the Thought, Watermarking the Answer: A Principle Semantic Guided Watermark for Large Reasoning Models](https://mlsanity.com/paper/2601.05144/) (2026)
- [A Visual Semantic Adaptive Watermark grounded by Prefix-Tuning for Large Vision-Language Model](https://mlsanity.com/paper/2601.07291/) (2026)
- [SoK: Are Watermarks in LLMs Ready for Deployment?](https://mlsanity.com/paper/2506.05594/) (2025)
- [A Linguistics-Aware LLM Watermarking via Syntactic Predictability](https://mlsanity.com/paper/2510.13829/) (2025)
- [Advancing Machine-Generated Text Detection from an Easy to Hard Supervision Perspective](https://mlsanity.com/paper/2511.00988/) (2025)
- [SSG: Logit-Balanced Vocabulary Partitioning for LLM Watermarking](https://mlsanity.com/paper/2604.22438/) (2026)
- [SAMark: A Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness](https://mlsanity.com/paper/2605.25796/) (2026)
- [Is Multilingual LLM Watermarking Truly Multilingual? Scaling Robustness to 100+ Languages via Back-Translation](https://mlsanity.com/paper/2510.18019/) (2025)
- [Robust LLM Watermarking with Minimal Semantic Distortion for IP Protection](https://mlsanity.com/paper/2605.23175/) (2026)
- [Watermarking Large Language Models in Europe: Interpreting the AI Act in Light of Technology](https://mlsanity.com/paper/2511.03641/) (2025)
- [Marking the Wrong Symptoms: Evaluating LLM Watermarks in Medical Texts](https://mlsanity.com/paper/2607.20462/) (2026)
- [Fighting Fire with Fire: On the Feasibility of Protecting Exercises Against AI Cheating](https://mlsanity.com/paper/2608.01112/) (2026)
- [DHMark: Public-Key Watermarking for LLM-Generated Text via Diffie-Hellman-Guided Rejection Sampling](https://mlsanity.com/paper/2608.03093/) (2026)
- [TrajMark: Ownership Attribution and Segment-Level Tamper Localization for Coding-Agent Trajectories](https://mlsanity.com/paper/2609.10416/) (2026)
- [TripPattern: A Pattern-based Text Watermarking Method for Large Language Models](https://mlsanity.com/paper/2609.12472/) (2026)
- [Language Model Fingerprinting Requires Rethinking Watermark Teachers](https://mlsanity.com/paper/2610.04169/) (2026)
- [Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key](https://mlsanity.com/paper/2610.18359/) (2026)

## Abstract (arXiv)

Text watermarking has emerged as a pivotal technique for identifying machine-generated text. However, existing methods often rely on arbitrary vocabulary partitioning during decoding to embed watermarks, which compromises the availability of suitable tokens and significantly degrades the quality of responses. This study assesses the impact of watermarking on different capabilities of large language models (LLMs) from a cognitive science lens. Our finding highlights a significant disparity; knowledge recall and logical reasoning are more adversely affected than language generation. These results suggest a more profound effect of watermarking on LLMs than previously understood. To address these challenges, we introduce Watermarking with Mutual Exclusion (WatME), a novel approach leveraging linguistic prior knowledge of inherent lexical redundancy in LLM vocabularies to seamlessly integrate watermarks. Specifically, WatME dynamically optimizes token usage during the decoding process by applying a mutually exclusive rule to the identified lexical redundancies. This strategy effectively prevents the unavailability of appropriate tokens and preserves the expressive power of LLMs. We provide both theoretical analysis and empirical evidence showing that WatME effectively preserves the diverse capabilities of LLMs while ensuring watermark detectability.