Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisions
<|reference_start|>Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisions: Language model (LM) watermarking techniques inject a statistical signal into LM-generated content by substituting the random sampling process with pseudo-random sampling, using watermark keys as the random seed. Among these statistical watermarking approaches, distortion-free watermarks are particularly crucial because they embed watermarks into LM-generated content without compromising generation quality. However, one notable limitation of pseudo-random sampling compared to true-random sampling is that, under the same watermark keys (i.e., key collision), the results of pseudo-random sampling exhibit correlations. This limitation could potentially undermine the distortion-free property. Our studies reveal that key collisions are inevitable due to the limited availability of watermark keys, and existing distortion-free watermarks exhibit a significant distribution bias toward the original LM distribution in the presence of key collisions. Moreover, achieving a perfect distortion-free watermark is impossible as no statistical signal can be embedded under key collisions. To reduce the distribution bias caused by key collisions, we introduce a new family of distortion-free watermarks--beta-watermark. Experimental results support that the beta-watermark can effectively reduce the distribution bias under key collisions.<|reference_end|>
@article{wu2024distortion-free,
    title={Distortion-free Watermarks are not Truly Distortion-free under Watermark
  Key Collisions},
    author={Yihan Wu, Ruibo Chen, Zhengmian Hu, Yanshuo Chen, Junfeng Guo,
  Hongyang Zhang, Heng Huang},
    journal={arXiv preprint arXiv:2406.02603},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02603},
    primaryClass={cs.CR cs.LG}
}