Reproduce “Optimal Detection for Language Watermarks with Pseudorandom Collision” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
T. Tony Cai, Xiang Li, Qi Long, Weijie J. Su, Garrett G. Wen
Researchers from the University of Pennsylvania and Yale University developed a statistical framework and optimal detection rules for language watermarks to address the challenge of pseudorandom collisions, which arise from text repetitions and invalidate standard independent and identically distributed assumptions. This work ensures rigorous Type I error control and maintains detection power for both Gumbel-max and inverse-transform watermarks in the presence of such collisions.
Key insights
- The hierarchical two-layer partition effectively models how pseudorandom collisions create structured dependencies, enabling the factorization of joint distributions into 'minimal units' that are conditionally independent.
- For Gumbel-max watermarks, the optimal detection rule depends only on the unique pivotal statistic within each minimal unit, providing a theoretical justification for the common heuristic of discarding repeated statistics.
- The minimax approach yields detection rules that are robust against uncertainty in next-token prediction distributions, showcasing a trichotomy of solutions for Gumbel-max watermarks based on the regularity parameter.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.