Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

📄 arXiv: 2604.08759v1 📥 PDF

作者: Yu-Shin Huang, Chao Tian, Krishna Narayanan

分类: cs.IT, cs.CL

发布日期: 2026-04-09

备注: 41 pages, 8 tables

💡 一句话要点

针对大语言模型，提出在最坏情况误报约束下的最优多比特生成式水印方案

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 生成式水印 大语言模型 线性规划 最坏情况误报 信息安全

📋 核心要点

  1. 现有生成式水印方案在最坏情况误报约束下存在次优性，无法达到理论最优的漏检概率下界。
  2. 论文将水印设计问题转化为线性规划，通过求解线性规划得到最优的编码-解码结构，实现最优水印性能。
  3. 论文提出了两种新的水印方案，并分析了先前方案的失效原因，比较了新方案的优劣。

📝 摘要（中文）

本文研究了在大语言模型中，在最坏情况误报约束下的多比特生成式水印问题。先前的工作建立了在有限token机制下可实现的漏检概率的下界，并提出了一种声称可以达到这个下界的方案。然而，我们证明了该方案实际上并非最优。随后，我们开发了两种新的编码-解码结构，它们达到了先前建立的下界，从而完全表征了最优多比特水印性能。我们的方法将水印设计问题形式化为一个线性规划，并推导出可以实现最优性的结构条件。此外，我们还确定了先前构造的失败机制，并比较了两种提出的方案之间的权衡。

🔬 方法详解

问题定义：论文旨在解决大语言模型中多比特生成式水印的最优化问题，特别是在最坏情况误报约束下。现有的水印方案，虽然声称达到了理论上的漏检概率下界，但实际上是次优的，这意味着在相同的误报率要求下，其漏检概率仍然有下降空间。

核心思路：论文的核心思路是将水印设计问题建模为一个线性规划问题。通过求解这个线性规划，可以得到最优的编码和解码策略，从而在满足最坏情况误报约束的前提下，最小化漏检概率。这种方法允许系统性地找到最优解，而不是依赖于启发式方法或次优的近似。

技术框架：论文的技术框架主要包括以下几个阶段：1) 问题建模：将多比特水印问题形式化为线性规划问题，明确目标函数（最小化漏检概率）和约束条件（最坏情况误报约束）。2) 理论分析：推导最优解存在的结构性条件，为后续的方案设计提供理论指导。3) 方案设计：基于理论分析，设计两种新的编码-解码方案。4) 性能评估：通过理论分析和实验验证，证明所提出的方案达到了最优性能。

关键创新：论文最重要的技术创新在于将水印设计问题转化为线性规划问题，并找到了最优解存在的结构性条件。与现有方法相比，这种方法不再依赖于启发式算法，而是通过求解优化问题来直接获得最优的水印方案。此外，论文还分析了现有方案的失效机制，为水印方案的设计提供了新的视角。

关键设计：论文的关键设计包括：1) 线性规划的构建：精确定义目标函数和约束条件，确保能够准确地描述水印设计问题。2) 编码和解码策略的设计：基于线性规划的解，设计具体的编码和解码算法，实现水印的嵌入和提取。3) 最坏情况误报约束的建模：准确地建模最坏情况下的误报概率，确保水印方案的鲁棒性。

📊 实验亮点

论文证明了先前声称最优的水印方案实际上是次优的，并提出了两种新的水印方案，达到了理论上的漏检概率下界，从而完全表征了最优多比特水印性能。通过将水印设计问题形式化为线性规划，论文提供了一种系统性的方法来设计最优的水印方案。

🎯 应用场景

该研究成果可应用于保护大型语言模型的知识产权，防止未经授权的复制和传播。通过嵌入水印，可以追踪模型的来源，验证模型的真实性，并为模型的商业化应用提供安全保障。此外，该技术还可以用于内容溯源、版权保护等领域。

📄 摘要（原文）

This paper considers the problem of multi-bit generative watermarking for large language models under a worst-case false-alarm constraint. Prior work established a lower bound on the achievable miss-detection probability in the finite-token regime and proposed a scheme claimed to achieve this bound. We show, however, that the proposed scheme is in fact suboptimal. We then develop two new encoding-decoding constructions that attain the previously established lower bound, thereby completely characterizing the optimal multi-bit watermarking performance. Our approach formulates the watermark design problem as a linear program and derives the structural conditions under which optimality can be achieved. In addition, we identify the failure mechanism of the previous construction and compare the tradeoffs between the two proposed schemes.