🔢 mathematics

LLM-Text Watermarking based on Lagrange Interpolation

本文提出了一种基于拉格朗日插值的大语言模型文本水印方案，通过仅在文本中嵌入由哈希函数生成的伪随机点对应的函数值，利用最大共线点问题的高效求解，实现了在文本遭受严重恶意删减后仍能恢复多比特作者身份。

原作者： Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

发布于 2026-02-27

📖 1 分钟阅读🧠 深度阅读

原作者： Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文提出了一种给大语言模型（LLM）生成的文本“盖隐形印章”的新方法。简单来说，就是如何在 AI 写的文章里藏入一个只有特定的人才能发现的“签名”，用来证明这篇文章到底是谁写的，或者是不是 AI 生成的。

我们可以把这个过程想象成**“在茫茫人海中寻找一条完美的直线”**。

1. 核心故事：藏宝图与直线

想象一下，你（作为 AI 的开发者）想在 AI 写的一篇文章里藏一个秘密信息（比如“这篇文章由模型 X 生成”）。

传统的做法：像是在文章里埋一颗颗独立的“地雷”，敌人只要挖掉几个，秘密就没了。
这篇论文的做法：像是在一张巨大的坐标纸上，撒下许多点。这些点看似杂乱无章，但实际上它们都严格地排列在一条看不见的直线上。

这条直线就是“水印”。
直线的方程是 $y = ax + b $。这里的$ a $和$ b$ 就是我们要藏的秘密信息（比如“我是模型 A"）。

2. 具体是怎么操作的？

第一步：埋点（嵌入水印）

当 AI 开始写文章时，它每写几个字，我们就会偷偷做一件事：

算坐标：根据前一个词和一把“秘密钥匙”（密钥），算出一个 $x$ 坐标。
找直线：用我们要藏的秘密（ $a$ 和 $b$ ）算出对应的 $y$ 坐标。
微调选择：AI 本来有很多词可选。我们会悄悄“推”一把，让 AI 更倾向于选择那些能代表正确 $y$ $y$ 坐标的词。
- 比喻：就像你在选路时，稍微把通往“正确方向”的路修得稍微平坦一点，AI 走起来更顺手，但它自己感觉不到，依然觉得是自己在自由发挥。

这样，AI 生成的每一个词，其实都在悄悄记录一个点 $(x, y)$ 。如果一切顺利，这些点连起来就是一条完美的直线。

第二步：找线（提取水印）

当有人拿到这篇文章，想验证它是不是 AI 写的时：

还原点：他拿着同样的“秘密钥匙”，把文章里的词重新翻译回坐标点。
面对混乱：
- 因为 AI 生成文字本身有随机性（有时候它可能没选那个“平坦”的路），有些点会偏离直线。
- 如果坏人故意删改文章（比如删掉几个词，或者换个词），更多的点会乱跑，甚至变成“假点”。
寻找直线（MCP 问题）：
- 这时候，验证者面临一个数学难题：在一大堆乱七八糟的点里，找出哪一条直线穿过的点最多。
- 比喻：想象在一个满是乱画的黑板上，有人用粉笔偷偷画了一条直线，但被橡皮擦擦掉了一部分，还画了很多杂乱的干扰线。你的任务就是找出那条穿过最多粉笔痕迹的直线。
破解密码：一旦找到了这条“穿过最多点”的直线，算出它的方程，就能读出 $a$ 和 $b$ ，也就是还原出了原始的秘密信息。

3. 为什么这个方法很厉害？

抗干扰能力强：
即使坏人删掉了文章的一半，或者改了很多词，只要剩下的点里，属于那条真直线的点比随机乱跑的假点多，我们就能通过数学方法（拉格朗日插值法）把那条直线重新画出来。
- 比喻：就像即使你撕掉了一张拼图的一半，只要剩下的碎片里，属于“蓝天”的部分比属于“草地”的碎片多，你依然能认出那是蓝天。
不需要重新训练 AI：
这个方法不需要去修改 AI 的大脑（模型权重），只需要在 AI 说话（生成文本）的时候，稍微“推”它一把（调整概率）。这就像给 AI 戴了一副隐形眼镜，而不是给 AI 做手术。
能藏更多信息：
以前的水印可能只能藏“是/否”（二进制），这个方法可以藏一串复杂的数字（多比特水印），比如具体的用户 ID 或时间戳。

4. 它的弱点是什么？

虽然它很聪明，但也不是无敌的：

怕“大挪移”：如果坏人把文章里的词顺序打乱，或者大段插入、删除，导致原本连成直线的点彻底错位，那就找不出来了。
- 比喻：如果坏人把拼图里的“蓝天”碎片全部换到了“草地”的位置，你就很难拼出原来的直线了。
计算量：要在成千上万个点里找直线，需要一定的计算能力，不过现在的电脑处理起来很快。

总结

这篇论文提出了一种**“用数学直线对抗混乱”**的巧妙方法。它把水印藏在了 AI 生成文本的统计规律里，即使文章被修改、被篡改，只要核心的“直线”没被完全破坏，我们就能像侦探一样，通过寻找“穿过最多点的直线”来揪出 AI 的踪迹，从而防止假新闻和抄袭。

这就好比在 AI 生成的文字海洋里，埋下了一根看不见的“直线鱼竿”，无论水面怎么波动，只要鱼竿还在，我们就能钓出真相。

基于拉格朗日插值的 LLM 文本水印技术总结

1. 研究背景与问题定义

随着大型语言模型（LLM）的快速发展，生成式 AI 在文本创作、对话交互等领域展现出巨大潜力。然而，这也带来了严峻挑战：如何准确归因 LLM 生成的文本？

核心问题：需要一种机制来区分人类文本与机器生成文本，识别具体的生成模型或提示者，以应对虚假信息、剽窃、冒充作者及恶意传播等问题。
现有局限：传统的数字水印技术难以直接应用于 LLM 生成的自然语言文本。现有的 LLM 水印方案（如训练阶段修改或 Logit 级别扰动）往往在对抗性编辑（如文本修改、删除、插入）下鲁棒性不足，或者难以嵌入多比特信息。

2. 核心方法论

本文提出了一种基于有限域（GF(2^n)）上拉格朗日插值的 LLM 文本水印方案。该方法无需重新训练模型，具有模型无关性（Model-agnostic），且能嵌入多比特水印。

2.1 核心思想

将水印编码为有限域上的一条直线（或多项式）的系数。

水印表示：水印 $W$ 被编码为线性函数 $f(x) = a_1x + a_0$ 的系数，其中 $a_0, a_1 \in GF(2^n)$ 。
嵌入过程：
1. 根据秘密密钥 $K$ 和当前生成的 token，伪随机生成一系列 $x$ 坐标。
2. 计算对应的 $y = f(x)$ 值，将其转换为二进制位序列。
3. 利用类似“绿/红 Token"（Green/Red Tokens）的机制，根据 $y$ 值的每一位，对 LLM 的 Logit 分布进行有偏采样（Biasing），将信息嵌入到生成的 token 流中。
提取过程：
1. 从文本中恢复出 $(x, y)$ 点对。由于生成过程的随机性和潜在的对抗性篡改，恢复出的点包含大量噪声（错误点）。
2. 将问题转化为最大共线点问题（Maximum Collinear Points, MCP）：在二维平面上寻找穿过最多点的直线。
3. 利用拉格朗日插值法，基于找到的共线点重构直线方程，从而提取出系数 $a_0$ 和 $a_1$ ，即原始水印。

2.2 关键技术组件

有限域算术：在 $GF(2^n)$ 上进行运算，利用其代数结构保证水印的数学性质。
MCP 算法：采用基于哈希的 $O(N^2)$ 算法高效求解最大共线点集，即使存在大量噪声点也能准确识别出真正的直线。
位纠错机制（Bit Correction）：在提取阶段，允许对恢复出的 $y$ 值进行小范围的汉明距离（Hamming radius）内的翻转尝试，以对抗采样噪声和局部编辑，提高恢复率。

3. 主要贡献

训练无关的轻量级方案：提出了一种无需修改模型权重或训练数据的后处理水印方案，适用于任何 LLM。
多比特水印嵌入：突破了传统二进制水印（仅区分“有/无”）的限制，能够嵌入包含具体标识信息的长水印（如 16-32 位）。
鲁棒性理论分析：
- 提供了在 $GF(2^n)^2$ 空间中随机点共线概率的理论上界（Theorem 1），为参数设计（如域大小 $n$ 和阈值 $\tau$ ）提供了数学依据。
- 证明了即使部分点被篡改，只要剩余的有效点足够多，仍能通过 MCP 算法恢复水印。
抗干扰设计：通过引入位纠错步骤，显著提升了在随机采样噪声下的提取成功率。

4. 实验结果

作者在 Llama 2-7B、Llama 3.2 和 Mistral 等模型上进行了广泛实验，并与当前最先进的方法（如 KGW, GumbelSoft 等）进行了对比。

匹配率（Match Rate）：
- 在 16 位水印长度下，该方法达到了 98.6% 的匹配率，与顶尖方法（如 Qu et al., 2024 的 98.0%）相当。
- 随着水印长度增加（32 位），匹配率保持在 85.9%，表现出良好的可扩展性。
- 相比之下，部分现有方法在长水印下性能急剧下降或无法提取（NA）。
提取效率：
- 提取时间极短（毫秒级），仅占文本生成时间的一小部分，且计算复杂度随文本长度呈线性或常数增长（通过固定窗口优化）。
对抗攻击鲁棒性：
- 替换攻击（Substitution）：表现最佳，因为不破坏 Token 序列的同步性，水印恢复率下降缓慢。
- 插入/删除攻击（Insertion/Deletion）：由于会导致分块错位（Desynchronization），对水印破坏较大。但在 10% 的篡改预算下，方案仍表现出一定的容忍度。
文本质量：
- 使用 $\delta=6$ 的 Logit 偏置，Perplexity（困惑度）变化极小，人类评估认为文本质量无明显下降。

5. 意义与局限性

意义

归因与问责：为 LLM 生成内容提供了可靠的“数字指纹”，有助于打击虚假信息、识别剽窃和明确责任归属。
代数结构的新范式：将密码学中的拉格朗日插值和有限域理论引入 NLP 水印领域，提供了一种基于代数结构而非单纯统计特征的新思路。
实用性强：方案轻量、无需重训、提取速度快，易于集成到现有的 LLM 部署流程中。

局限性与未来工作

同步性依赖：方案对插入/删除攻击较为敏感，因为这类攻击会破坏 Token 块的同步，导致后续所有点坐标错误。未来需结合更复杂的同步机制。
参数权衡：需要在域大小（ $n$ ）、块长度和纠错能力之间进行精细权衡，以平衡鲁棒性和误报率。
高阶扩展：目前主要验证了线性函数（直线），未来可探索更高阶多项式（Maximum Co-Polynomial Points 问题）以承载更复杂的水印信息，但这会增加计算复杂度。

总结

该论文提出了一种基于拉格朗日插值和最大共线点问题的创新 LLM 水印方案。它巧妙地利用代数结构将水印隐藏在文本生成的统计偏差中，并通过高效的几何算法从噪声中提取。实验表明，该方法在保持高文本质量的同时，实现了高鲁棒性的多比特水印嵌入，为 AI 生成内容的溯源和版权保护提供了强有力的技术支撑。