# AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing

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

## Key facts

- Cited by 1 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 50 of its 62 references that are in the map.
- First posted on arXiv 28 May 2026.

## 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, 30 of 50)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Gemma 3 Technical Report](https://mlsanity.com/paper/2503.19786/) (2025)
- [Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection](https://mlsanity.com/paper/2302.12173/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [PEGASUS: Pre-training with Extracted Gap-sentences for Abstractive Summarization](https://mlsanity.com/paper/1912.08777/) (2019)
- [OpenAI GPT-5 System Card](https://mlsanity.com/paper/2601.03267/) (2025)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [BookSum: A Collection of Datasets for Long-form Narrative Summarization](https://mlsanity.com/paper/2105.08209/) (2021)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [MarkLLM: An Open-Source Toolkit for LLM Watermarking](https://mlsanity.com/paper/2405.10051/) (2024)
- [Text-to-Image Diffusion Models can be Easily Backdoored through Multimodal Data Poisoning](https://mlsanity.com/paper/2305.04175/) (2023)
- [Three Bricks to Consolidate Watermarks for Large Language Models](https://mlsanity.com/paper/2308.00113/) (2023)
- [A Robust Semantics-based Watermark for Large Language Model against Paraphrasing](https://mlsanity.com/paper/2311.08721/) (2023)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [An Entropy-based Text Watermarking Detection Method](https://mlsanity.com/paper/2403.13485/) (2024)
- [Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents](https://mlsanity.com/paper/2505.02077/) (2025)
- [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)
- [k-SemStamp: A Clustering-Based Semantic Watermark for Detection of Machine-Generated Text](https://mlsanity.com/paper/2402.11399/) (2024)
- [Watermarking Conditional Text Generation for AI Detection: Unveiling Challenges and a Semantic-Aware Watermark Remedy](https://mlsanity.com/paper/2307.13808/) (2023)
- [Provably Robust Multi-bit Watermarking for AI-generated Text](https://mlsanity.com/paper/2401.16820/) (2024)

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

- [ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models](https://mlsanity.com/paper/2610.14427/) (2026)

## Abstract (arXiv)

Existing sentence-level watermarking methods enhance robustness to paraphrasing by anchoring watermarks in sentence semantics. However, their prefix-based designs remain vulnerable to structural perturbations, such as sentence splitting and merging, which commonly arise under strong paraphrasers like DIPPER and GPT-3.5. To mitigate this issue, we propose AliMark, a framework that reformulates sentence-level watermarking as a bit sequence encoding and alignment problem between a potentially watermarked text and a secret bit sequence. Notably, our approach adopts a two-stage detection strategy: we generate multiple restructured text variants and adaptively align their extracted bit sequences with the secret bit sequence to minimize alignment cost. This multi-candidate alignment design naturally improves robustness to sentence merges and splits. Extensive experiments demonstrate that AliMark substantially outperforms state-of-the-art baselines under diverse paraphrasing attacks.