PIVOT: Distribution-Preserving Multi-BitWatermarking with Minimax-Optimal Scoring
As LLM-generated content becomes increasingly widespread, reliable attribution calls for multi-bit watermarks that embed recoverable messages without distorting the output distribution. We introduce PIVOT, a multi-bit watermark with model-free verification based on mirrored rank-interval sampling. At each generation step, PIVOT uses a keyed pseudorandom scalar and a secret permutation of the vocabulary. The message bit determines whether next-token probability intervals are arranged in forward or reverse secret-rank order. Sampling from these mirrored layouts preserves every token probability exactly while inducing an opposite-signed dependence between the scalar and the sampled token's secret rank. This dependence yields a pivotal rank statistic whose null distribution is invariant to the unknown next-token law, enabling model-free calibration and decoding. We formulate joint watermark detection and message recovery as a multiple-hypothesis testing problem, derive a moment-robust minimax-optimal detection score over a relaxed moment class, and establish finite-sample recovery guarantees. Extensive experiments on two representative large language models validate the effectiveness of PIVOT, demonstrating reliable watermark detection and message recovery while preserving the generator's output distribution.
Authors
- Kaiyi Pang (ORCID: https://orcid.org/0000-0003-0248-171X)
- Minhao Bai (ORCID: https://orcid.org/0009-0000-9069-6053)
- Shuyu Gan
- Liping Zhu
- Wen Zhang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24109
- Primary Topic
- Advanced Steganography and Watermarking Techniques
- Type
- preprint