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

Yuexin Li, Wenjie Qu, Linyu Wu, Yulin Chen, Yufei He, Tri Cao, Bryan Hooi, Jiaheng Zhang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:69520-69541, 2026.

Abstract

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. Our code is available at https://github.com/imethanlee/AliMark.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-li26ex, title = {{A}li{M}ark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing}, author = {Li, Yuexin and Qu, Wenjie and Wu, Linyu and Chen, Yulin and He, Yufei and Cao, Tri and Hooi, Bryan and Zhang, Jiaheng}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {69520--69541}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/li26ex/li26ex.pdf}, url = {https://proceedings.mlr.press/v306/li26ex.html}, abstract = {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. Our code is available at https://github.com/imethanlee/AliMark.} }
Endnote
%0 Conference Paper %T AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing %A Yuexin Li %A Wenjie Qu %A Linyu Wu %A Yulin Chen %A Yufei He %A Tri Cao %A Bryan Hooi %A Jiaheng Zhang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-li26ex %I PMLR %P 69520--69541 %U https://proceedings.mlr.press/v306/li26ex.html %V 306 %X 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. Our code is available at https://github.com/imethanlee/AliMark.
APA
Li, Y., Qu, W., Wu, L., Chen, Y., He, Y., Cao, T., Hooi, B. & Zhang, J.. (2026). AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:69520-69541 Available from https://proceedings.mlr.press/v306/li26ex.html.

Related Material