Watermarks for Language Models via Probabilistic Automata

• URL: http://arxiv.org/abs/2512.10185v1
• Date: Thu, 11 Dec 2025 00:49:06 GMT
• Title: Watermarks for Language Models via Probabilistic Automata
• Authors: Yangkun Wang, Jingbo Shang,
• Abstract summary: We introduce a new class of watermarking schemes constructed through probabilistic automata.<n>We present two instantiations: (i) a practical scheme with exponential generation diversity and computational efficiency, and (ii) a theoretical construction with formal undetectability guarantees under cryptographic assumptions.
• Score: 54.687037560547765
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent watermarking scheme for language models achieves distortion-free embedding and robustness to edit-distance attacks. However, it suffers from limited generation diversity and high detection overhead. In parallel, recent research has focused on undetectability, a property ensuring that watermarks remain difficult for adversaries to detect and spoof. In this work, we introduce a new class of watermarking schemes constructed through probabilistic automata. We present two instantiations: (i) a practical scheme with exponential generation diversity and computational efficiency, and (ii) a theoretical construction with formal undetectability guarantees under cryptographic assumptions. Extensive experiments on LLaMA-3B and Mistral-7B validate the superior performance of our scheme in terms of robustness and efficiency.

Related papers

• An Ensemble Framework for Unbiased Language Model Watermarking [60.99969104552168]
  We propose ENS, a novel ensemble framework that enhances the detectability and robustness of unbiased watermarks.<n>ENS sequentially composes multiple independent watermark instances, each governed by a distinct key, to amplify the watermark signal.<n> Empirical evaluations show that ENS substantially reduces the number of tokens needed for reliable detection and increases resistance to smoothing and paraphrasing attacks.
  arXiv  Detail & Related papers  (2025-09-28T19:37:44Z)
• Character-Level Perturbations Disrupt LLM Watermarks [64.60090923837701]
  We formalize the system model for Large Language Model (LLM) watermarking.<n>We characterize two realistic threat models constrained on limited access to the watermark detector.<n>We demonstrate character-level perturbations are significantly more effective for watermark removal under the most restrictive threat model.<n> Experiments confirm the superiority of character-level perturbations and the effectiveness of the Genetic Algorithm (GA) in removing watermarks under realistic constraints.
  arXiv  Detail & Related papers  (2025-09-11T02:50:07Z)
• Improving Detection of Watermarked Language Models [31.772364827073808]
  We investigate whether detection can be improved by combining watermark detectors with non-watermark ones.<n>In this work, we investigate whether detection can be improved by combining watermark detectors with non-watermark ones.
  arXiv  Detail & Related papers  (2025-08-18T17:43:06Z)
• Entropy-Guided Watermarking for LLMs: A Test-Time Framework for Robust and Traceable Text Generation [58.85645136534301]
  Existing watermarking schemes for sampled text often face trade-offs between maintaining text quality and ensuring robust detection against various attacks.<n>We propose a novel watermarking scheme that improves both detectability and text quality by introducing a cumulative watermark entropy threshold.
  arXiv  Detail & Related papers  (2025-04-16T14:16:38Z)
• GaussMark: A Practical Approach for Structural Watermarking of Language Models [61.84270985214254]
  GaussMark is a simple, efficient, and relatively robust scheme for watermarking large language models.<n>We show that GaussMark is reliable, efficient, and relatively robust to corruptions such as insertions, deletions, substitutions, and roundtrip translations.
  arXiv  Detail & Related papers  (2025-01-17T22:30:08Z)
• Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach [53.32564762183639]
  We introduce a novel, unified theoretical framework for watermarking Large Language Models (LLMs)<n>Our approach aims to maximize detection performance while maintaining control over the worst-case false positive rate (FPR) and distortion on text quality.<n>We propose a distortion-free, distribution-adaptive watermarking algorithm (DAWA) that leverages a surrogate model for model-agnosticism and efficiency.
  arXiv  Detail & Related papers  (2024-10-03T18:28:10Z)
• Three Bricks to Consolidate Watermarks for Large Language Models [13.559357913735122]
  This research consolidates watermarks for large language models based on three theoretical and empirical considerations. First, we introduce new statistical tests that offer robust theoretical guarantees which remain valid even at low false-positive rates. Second, we compare the effectiveness of watermarks using classical benchmarks in the field of natural language processing, gaining insights into their real-world applicability.
  arXiv  Detail & Related papers  (2023-07-26T17:56:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.