PURA: a provably unbiased and robust multi-bit watermarking method for tracing AI-generated text

The researchers propose PURA, a provably unbiased and robust multi-bit watermarking method for tracing and auditing AI-generated text. The method does not directly perturb token probabilities; instead, it embeds a payload in the latent sampling space via keyed inverse transform sampling, then aggregates the observed tokens as soft interval evidence across the sequence to recover the information, thereby exactly preserving the base generation distribution and significantly improving recovery stability under editing and channel perturbations. The paper also establishes a unified robustness analysis, proving that under bounded attack strength the per-bit error probability decays exponentially with sequence length. Experiments show that when embedding 36 bit in 200 token, PURA achieves a 91.7% message match rate, more than three times that of the strongest unbiased baseline, while maintaining text quality statistically close to unwatermarked text, with verification overhead of only milliseconds. The authors have also released the code.