# Tracing Text Provenance via Context-Aware Lexical Substitution

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 15 Dec 2021.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [A large annotated corpus for learning natural language inference](https://mlsanity.com/paper/1508.05326/) (2015)
- [HiDDeN: Hiding Data With Deep Networks](https://mlsanity.com/paper/1807.09937/) (2018)
- [StegaStamp: Invisible Hyperlinks in Physical Photographs](https://mlsanity.com/paper/1904.05343/) (2019)
- [Enhanced LSTM for Natural Language Inference](https://mlsanity.com/paper/1609.06038/) (2016)
- [BERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model](https://mlsanity.com/paper/1902.04094/) (2019)
- [Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding](https://mlsanity.com/paper/2009.03015/) (2020)
- [Model Watermarking for Image Processing Networks](https://mlsanity.com/paper/2002.11088/) (2020)
- [Fact-Enhanced Synthetic News Generation](https://mlsanity.com/paper/2012.04778/) (2020)
- [Swords: A Benchmark for Lexical Substitution with Improved Data Coverage and Quality](https://mlsanity.com/paper/2106.04102/) (2021)
- [Generating Long Financial Report using Conditional Variational Autoencoders with Knowledge Distillation](https://mlsanity.com/paper/2010.12188/) (2020)
- [FontCode: Embedding Information in Text Documents using Glyph Perturbation](https://mlsanity.com/paper/1707.09418/) (2017)

## Built on by (most cited first, 30 of 45)

- [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)
- [Who Wrote this Code? Watermarking for Code Generation](https://mlsanity.com/paper/2305.15060/) (2023)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [Robust Multi-bit Natural Language Watermarking through Invariant Features](https://mlsanity.com/paper/2305.01904/) (2023)
- [On the Learnability of Watermarks for Language Models](https://mlsanity.com/paper/2312.04469/) (2023)
- [Watermarking Text Generated by Black-Box Language Models](https://mlsanity.com/paper/2305.08883/) (2023)
- [Adaptive Text Watermark for Large Language Models](https://mlsanity.com/paper/2401.13927/) (2024)
- [Advancing Beyond Identification: Multi-bit Watermark for Large Language Models](https://mlsanity.com/paper/2308.00221/) (2023)
- [Towards Codable Watermarking for Injecting Multi-bits Information to LLMs](https://mlsanity.com/paper/2307.15992/) (2023)
- [Provably Robust Multi-bit Watermarking for AI-generated Text](https://mlsanity.com/paper/2401.16820/) (2024)
- [GumbelSoft: Diversified Language Model Watermarking via the GumbelMax-trick](https://mlsanity.com/paper/2402.12948/) (2024)
- [Towards Trustworthy Retrieval Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2502.06872/) (2025)
- [Towards Optimal Statistical Watermarking](https://mlsanity.com/paper/2312.07930/) (2023)
- [Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach](https://mlsanity.com/paper/2410.02890/) (2024)
- [BiMark: Unbiased Multilayer Watermarking for Large Language Models](https://mlsanity.com/paper/2506.21602/) (2025)
- [Debiasing Watermarks for Large Language Models via Maximal Coupling](https://mlsanity.com/paper/2411.11203/) (2024)
- [CoheMark: A Novel Sentence-Level Watermark for Enhanced Text Quality](https://mlsanity.com/paper/2504.17309/) (2025)
- [SoK: On the Role and Future of AIGC Watermarking in the Era of Gen-AI](https://mlsanity.com/paper/2411.11478/) (2024)
- [WAPITI: A Watermark for Finetuned Open-Source LLMs](https://mlsanity.com/paper/2410.06467/) (2024)
- [Detecting Stylistic Fingerprints of Large Language Models](https://mlsanity.com/paper/2503.01659/) (2025)
- [Defending LLM Watermarking Against Spoofing Attacks with Contrastive Representation Learning](https://mlsanity.com/paper/2504.06575/) (2025)
- [In-Context Watermarks for Large Language Models](https://mlsanity.com/paper/2505.16934/) (2025)
- [Unsupervised Lexical Substitution with Decontextualised Embeddings](https://mlsanity.com/paper/2209.08236/) (2022)
- [Inevitable Trade-off between Watermark Strength and Speculative Sampling Efficiency for Language Models](https://mlsanity.com/paper/2410.20418/) (2024)
- [Position: LLM Watermarking Should Align Stakeholders' Incentives for Practical Adoption](https://mlsanity.com/paper/2510.18333/) (2025)
- [Cross-Attention Watermarking of Large Language Models](https://mlsanity.com/paper/2401.06829/) (2024)
- [Survey on Plagiarism Detection in Large Language Models: The Impact of ChatGPT and Gemini on Academic Integrity](https://mlsanity.com/paper/2407.13105/) (2024)

## Abstract (arXiv)

Text content created by humans or language models is often stolen or misused by adversaries. Tracing text provenance can help claim the ownership of text content or identify the malicious users who distribute misleading content like machine-generated fake news. There have been some attempts to achieve this, mainly based on watermarking techniques. Specifically, traditional text watermarking methods embed watermarks by slightly altering text format like line spacing and font, which, however, are fragile to cross-media transmissions like OCR. Considering this, natural language watermarking methods represent watermarks by replacing words in original sentences with synonyms from handcrafted lexical resources (e.g., WordNet), but they do not consider the substitution's impact on the overall sentence's meaning. Recently, a transformer-based network was proposed to embed watermarks by modifying the unobtrusive words (e.g., function words), which also impair the sentence's logical and semantic coherence. Besides, one well-trained network fails on other different types of text content. To address the limitations mentioned above, we propose a natural language watermarking scheme based on context-aware lexical substitution (LS). Specifically, we employ BERT to suggest LS candidates by inferring the semantic relatedness between the candidates and the original sentence. Based on this, a selection strategy in terms of synchronicity and substitutability is further designed to test whether a word is exactly suitable for carrying the watermark signal. Extensive experiments demonstrate that, under both objective and subjective metrics, our watermarking scheme can well preserve the semantic integrity of original sentences and has a better transferability than existing methods. Besides, the proposed LS approach outperforms the state-of-the-art approach on the Stanford Word Substitution Benchmark.