# PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 23 Aug 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, 20 of 20)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (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)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Neural Linguistic Steganography](https://mlsanity.com/paper/1909.01496/) (2019)
- [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)
- [Perfectly Secure Steganography Using Minimum Entropy Coupling](https://mlsanity.com/paper/2210.14889/) (2022)
- [Revealing Weaknesses in Text Watermarking Through Self-Information Rewrite Attacks](https://mlsanity.com/paper/2505.05190/) (2025)
- [Optimizing Adaptive Attacks against Watermarks for Language Models](https://mlsanity.com/paper/2410.02440/) (2024)
- [SparSamp: Efficient Provably Secure Steganography Based on Sparse Sampling](https://mlsanity.com/paper/2503.19499/) (2025)
- [Character-Level Perturbations Disrupt LLM Watermarks](https://mlsanity.com/paper/2509.09112/) (2025)
- [Provably Robust and Secure Steganography in Asymmetric Resource Scenario](https://mlsanity.com/paper/2407.13499/) (2024)
- [MC2Mark: Distortion-Free Multi-Bit Watermarking for Long Messages](https://mlsanity.com/paper/2602.14030/) (2026)

## Abstract (arXiv)

Fine-grained attribution of AI-generated text is becoming increasingly important for accountability and auditing, yet existing multi-bit watermarking methods still struggle to simultaneously preserve the base generation distribution, support high-capacity payloads, and remain recoverable after editing. We present PURA, a provably unbiased and robust multi-bit watermarking method for text attribution. Instead of perturbing token probabilities directly, PURA embeds payloads in the latent sampling space via keyed inverse transform sampling, and recovers them by treating observed tokens as soft interval evidence and aggregating such evidence across the sequence. This design preserves the base generation distribution exactly while substantially improving recovery stability under post-editing and channel perturbations. Building on this recovery paradigm, we further develop a unified robustness analysis and show that, under bounded attack strength, the per-bit error probability decays exponentially with sequence length. Extensive experiments show that PURA substantially outperforms existing unbiased baselines in the high-payload regime. For example, when embedding 36 bits in 200 tokens, PURA achieves a 91.7% message match rate, more than three times that of the strongest unbiased baseline, while preserving text quality and remaining statistically close to unwatermarked text, and incurring only millisecond-level verification overhead. Our code is available at