Elamur Research⌕
☰
home / papers / 2026 / XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts

XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts

Paper · 2026 · Jiahao Xu, Rui Hu, Olivera Kotevska et al.

Summary

Multi-bit watermarking hides a binary payload, such as a user ID or timestamp, inside LLM output so that misuse can later be traced to its source. Earlier approaches have three problems. Some must search exhaustively over candidate messages, which becomes infeasible for long payloads. Others give up text quality to gain recovery accuracy, or the reverse. All of them lose accuracy when the suspect text is short.

XMark extends MPAC's block-wise scheme. It uses k hash keys to produce k vocabulary permutations, each split into 2^d shards. In each permutation, every shard except the one indexed by the current message block becomes a green list (Leave-one-Shard-out, LoSo). The intersection of these lists, called the evergreen list, receives a logit bias. Because this list stays large, token sampling is only mildly distorted. On the decoding side, a constrained token–shard mapping matrix (cTMM) lets each token contribute up to k shard observations.

Experiments show higher bit accuracy than prior methods at similar perplexity, particularly when few tokens are available. This matters for attributing short real-world texts.

Key points

  • The evergreen list covers roughly (1 − 2^−d)^k of the vocabulary. The experiments fix d = 2.
  • Decoding is fast: about 0.08 s for XMark versus 0.06 s for MPAC. Enumeration-based DepthW and RSBH need 16.16 s and 8.45 s even at b = 8, while XMark reaches 98.75% bit accuracy.
  • An ablation on text completion with b = 32 shows bit accuracy rising with the number of keys k:
    • LoSo (k = 1) averages 77.72%, while XMark with k = 4 averages 88.16%.
    • Perplexity grows slightly, from 4.46 to 5.11.
    • Replacing cTMM with a plain TMM lowers accuracy.
  • Motivating experiments use LLaMA-2-7B on the C4 dataset. The code is released at github.com/JiiahaoXU/XMark.
  • The authors list several limitations:
    • Larger d hurts decoding.
    • k and δ require manual tuning.
    • The design includes no explicit defense against editing attacks.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬Oak Ridge National LaboratoryOak Ridge · United States6 works · 881 citations

Also on the byline: University of Nevada, Reno.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 worksHardware and Architecture · 167 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Jiahao Xu, Rui Hu, Olivera Kotevska and Zikai Zhang. 2026. XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.672

@inproceedings{xu2026xmark,
  title = {{XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts}},
  author = {Jiahao Xu, Rui Hu, Olivera Kotevska and Zikai Zhang},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.672},
  url = {https://doi.org/10.18653/v1/2026.acl-long.672}
}

References

42 references, 14 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Ondrej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Ale s Tamchyna. 2014. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the…
  2. Massieh Kordi Boroujeny, Ya Jiang, Kai Zeng, and Brian Mark. 2024. Multi-bit distortion-free watermarking for large language models. arXiv preprint arXiv:2402.16578. — [arXiv:2402.16578](https://arxiv.org/abs/2402.16578) find
  3. Yapei Chang, Kalpesh Krishna, Amir Houmansadr, John Frederick Wieting, and Mohit Iyyer. 2024. Post-Mark: A robust blackbox watermark for large language models. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 8969–8987, Miami, Florida, USA. Association… find
  4. Miranda Christ, Sam Gunn, and Or Zamir. 2024. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125–1139. PMLR. find
  5. Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, and 1 others. 2024. Scalable watermarking for identifying large language model outputs. Nature, 634(8035):818–823. find
  6. Angela Fan, Mike Lewis, and Yann Dauphin. 2018. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 889–898, Melbourne, Australia. Association for Computational Linguistics.
  7. Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. 2023. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1–6. IEEE. find
  8. Eva Giboulot and Teddy Furon. 2024. Watermax: breaking the llm watermark detectability-robustness-quality trade-off. Advances in Neural Information Processing Systems, 37:18848–18881. find
  9. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, and 1 others. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783.
  10. Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015. Teaching machines to read and comprehend. Advances in neural information processing systems, 28.
  11. Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. 2024. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations. find
  12. Ya Jiang, Chuxiong Wu, Massieh Kordi Boroujeny, Brian Mark, and Kai Zeng. 2025. StealthInk: A multi-bit and stealthy watermark for large language models. In Forty-second International Conference on Machine Learning. find
  13. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. 2023. A watermark for large language models. In International Conference on Machine Learning, pages 17061–17084. PMLR.
  14. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. 2024. On the reliability of watermarks for large language models. In The Twelfth International Conference on Learning Representations.
  15. Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. 2023. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. Advances in Neural Information Processing Systems, 36:27469–27500.
  16. Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. 2024. Robust distortion-free watermarks for language models. Transactions on Machine Learning Research.
  17. Liying Li, Yihan Bai, and Minhao Cheng. 2024. Where am I from? identifying origin of LLM-generated content. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 12218–12229, Miami, Florida, USA. Association for Computational Linguistics. find
  18. Chin-Yew Lin. 2004. ROUGE: A package for automatic evaluation of summaries. In Text summarization branches out, pages 74–81.
  19. Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. 2024a. A semantic invariant robust watermark for large language models. In The Twelfth International Conference on Learning Representations. find
  20. Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. 2024b. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1–36. find
  21. Minjia Mao, Dongjun Wei, Zeyu Chen, Xiao Fang, and Michael Chau. 2025. Watermarking large language models: An unbiased and low-risk method. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7939–7960, Vienna, Austria. Associatio… find
  22. Travis Munyer, Abdullah All Tanvir, Arjon Das, and Xin Zhong. 2024. Deeptextmark: a deep learning-driven text watermarking approach for identifying large language model generated text. IEEE ACCESS, 12:40508–40520. find
  23. Leyi Pan, Aiwei Liu, Zhiwei He, Zitian Gao, Xuandong Zhao, Yijian Lu, Binglin Zhou, Shuliang Liu, Xuming Hu, Lijie Wen, and 1 others. 2024. Markllm: An open-source toolkit for llm watermarking. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: System Demonstr… find
  24. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311–318.
  25. Mike Perkins. 2023. Academic integrity considerations of ai large language models in the post-pandemic era: Chatgpt and beyond. Journal of University Teaching and Learning Practice, 20(2):1–24. find
  26. Julien Piet, Chawin Sitawarin, Vivian Fang, Norman Mu, and David Wagner. 2025. Markmywords: Analyzing and evaluating language model watermarks. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 68–91. IEEE. find
  27. Wenjie Qu, Wengrui Zheng, Tianyang Tao, Dong Yin, Yanze Jiang, Zhihua Tian, Wei Zou, Jinyuan Jia, and Jiaheng Zhang. 2025. Provably robust multi-bit watermarking for AI-generated text. In 34th USENIX Security Symposium (USENIX Security 25), pages 201–220. find
  28. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1–67.
  29. Christoph Schuhmann. 2023. Essays with instructions dataset. https://huggingface.co/datasets/ChristophSchuhmann/ essays-with-instructions. Accessed: 2025-07-14. ↗
  30. John Schulman, Barret Zoph, Christina Kim, Jacob Hilton, Jacob Menick, Jiayi Weng, Juan Felipe Ceron Uribe, Liam Fedus, Luke Metz, Michael Pokorny, and 1 others. 2022. ChatGPT: Optimizing language models for dialogue. OpenAI blog, 2(4). find
  31. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, and 1 others. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.
  32. Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. 2024. Towards codable watermarking for injecting multi-bits information to llms. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. Open-Review.n… find
  33. Ruisi Zhang, Shehzeen Samarah Hussain, Paarth Neekhara, and Farinaz Koushanfar. 2024. REMARK-LLM: A robust and efficient watermarking framework for generative large language models. In 33rd USENIX Security Symposium (USENIX Security 24), pages 1813–1830. find
  34. Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020. Bertscore: Evaluating text generation with bert. In International Conference on Learning Representations. find
  35. Zhaoxi Zhang, Xiaomei Zhang, Yanjun Zhang, He Zhang, Shirui Pan, Bo Liu, Asif Qumer Gill, and Leo Yu Zhang. 2025. Character-level perturbations disrupt llm watermarks. arXiv preprint arXiv:2509.09112. — [arXiv:2509.09112](https://arxiv.org/abs/2509.09112) find
  36. Jiren Zhu, Russell Kaplan, Justin Johnson, and Li Fei-Fei. 2018. Hidden: Hiding data with deep networks. In Proceedings of the European conference on computer vision (ECCV), pages 657–672. find
  37. Zongqi Wang, Tianle Gu, Baoyuan Wu, and Yujiu Yang. 2025. Morphmark: Flexible adaptive watermarking for large language models. arXiv preprint arXiv:2505.11541.
  38. Junchao Wu, Shu Yang, Runzhe Zhan, Yulin Yuan, Lidia Sam Chao, and Derek Fai Wong. 2025. A survey on llm-generated text detection: Necessity, methods, and future directions. Computational Linguistics, 51(1):275–338.
  39. Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. 2024. A resilient and accessible distribution-preserving watermark for large language models. In Forty-first International Conference on Machine Learning. find
  40. Jiahao Xu, Rui Hu, and Zikai Zhang. 2025. Majority bit-aware watermarking for large language models. arXiv preprint arXiv:2508.03829. — [arXiv:2508.03829](https://arxiv.org/abs/2508.03829) find
  41. An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, and 40 others. 2024. Qwen2 technical report. arXiv preprint arXi… find
  42. KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. 2024. Advancing beyond identification: Multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pa… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xu-2026-xmark-reliable-multi-bit-watermarking/