Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy

📄 arXiv: 2603.21567v1 📥 PDF

作者: Andrii Shportko

分类: cs.LG

发布日期: 2026-03-23

💡 一句话要点

提出基于柯尔莫哥洛夫复杂度的LLM隐写术理论界限及基于困惑度的检测代理。

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

关键词: LLM隐写术 柯尔莫哥洛夫复杂度 困惑度 信息论 AI安全

📋 核心要点

  1. 现有方法难以有效检测LLM隐写术，对AI对齐监控构成挑战。
  2. 论文提出基于柯尔莫哥洛夫复杂度的理论界限，揭示隐写术的信息论成本。
  3. 实验表明，基于困惑度的代理指标能有效检测LLM隐写，验证了理论预测。

📝 摘要（中文）

大型语言模型（LLM）能够通过改写文本来嵌入隐藏的有效载荷，同时保持表面含义不变。这种能力为合作AI系统之间开辟了隐蔽通道，并对对齐监控提出了挑战。本文研究了这种嵌入的信息论成本。主要结果表明，任何在将有效载荷P编码到隐写文本M2中，同时保持覆盖文本M1的语义负载的隐写方案，都必须满足K(M2) >= K(M1) + K(P) - O(log n)，其中K表示柯尔莫哥洛夫复杂度，n是组合消息长度。由此可得，任何非平凡的有效载荷都会强制增加隐写文本的复杂度，无论编码器如何巧妙地分配信号。由于柯尔莫哥洛夫复杂度是不可计算的，本文探讨了实际代理是否可以检测到这种预测的增加。借鉴无损压缩和柯尔莫哥洛夫复杂度之间的经典对应关系，本文认为语言模型困惑度在概率机制中扮演着类似的角色，并提出了Binoculars困惑度比率评分作为一种代理。基于颜色的LLM隐写方案的初步实验支持了理论预测：对300个样本进行的配对t检验产生t = 5.11，p < 10^{-6}。

🔬 方法详解

问题定义：论文旨在解决大型语言模型（LLM）隐写术的检测问题。现有的检测方法难以有效识别LLM通过细微修改文本嵌入隐藏信息的情况，这使得恶意行为者可以利用LLM进行秘密通信，对AI安全和对齐构成潜在威胁。现有的检测方法通常依赖于统计特征或规则，难以捕捉LLM生成文本的复杂性和多样性。

核心思路：论文的核心思路是利用柯尔莫哥洛夫复杂度来量化隐写术的信息论成本。论文证明，任何有效的隐写方案都会增加隐写文本的柯尔莫哥洛夫复杂度。由于柯尔莫哥洛夫复杂度不可计算，论文进一步提出使用语言模型的困惑度作为其代理指标。困惑度反映了语言模型对文本的预测能力，复杂度高的文本通常具有更高的困惑度。

技术框架：论文的技术框架主要包含两个部分：理论分析和实验验证。理论分析部分，论文推导了LLM隐写术的柯尔莫哥洛夫复杂度下界，证明了隐写文本的复杂度必然高于原始文本和隐藏信息的复杂度之和。实验验证部分，论文设计了一种基于颜色的LLM隐写方案，并使用Binoculars困惑度比率评分来检测隐写文本。

关键创新：论文最重要的技术创新在于将柯尔莫哥洛夫复杂度引入LLM隐写术的分析中，并证明了隐写术的信息论成本。此外，论文提出了使用困惑度作为柯尔莫哥洛夫复杂度的代理指标，为实际检测LLM隐写术提供了可行的方案。与现有方法相比，该方法不依赖于特定的统计特征或规则，具有更强的通用性和鲁棒性。

关键设计：论文的关键设计包括：1) 柯尔莫哥洛夫复杂度下界的推导，使用了信息论的基本原理和柯尔莫哥洛夫复杂度的定义。2) Binoculars困惑度比率评分的定义，该评分通过比较原始文本和隐写文本的困惑度来判断是否存在隐写行为。3) 基于颜色的LLM隐写方案的设计，该方案通过控制LLM生成文本中特定颜色的词语来嵌入隐藏信息。实验中使用了GPT-2模型来计算困惑度，并使用配对t检验来评估检测效果。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，基于困惑度的检测代理能够有效检测LLM隐写术。对300个样本进行的配对t检验显示，t值为5.11，p值小于10^{-6}，表明隐写文本的困惑度显著高于原始文本，验证了理论预测。该结果为实际应用中检测LLM隐写术提供了有力的支持。

🎯 应用场景

该研究成果可应用于检测和防御基于LLM的隐蔽通信，例如防止恶意软件通过LLM传递指令，或检测AI系统之间的秘密协作。此外，该研究为评估LLM的安全性提供了新的理论工具，有助于提升AI系统的可信度和可靠性，并促进负责任的AI发展。

📄 摘要（原文）

Large language models can rewrite text to embed hidden payloads while preserving surface-level meaning, a capability that opens covert channels between cooperating AI systems and poses challenges for alignment monitoring. We study the information-theoretic cost of such embedding. Our main result is that any steganographic scheme that preserves the semantic load of a covertext~$M_1$ while encoding a payload~$P$ into a stegotext~$M_2$ must satisfy $K(M_2) \geq K(M_1) + K(P) - O(\log n)$, where $K$ denotes Kolmogorov complexity and $n$ is the combined message length. A corollary is that any non-trivial payload forces a strict complexity increase in the stegotext, regardless of how cleverly the encoder distributes the signal. Because Kolmogorov complexity is uncomputable, we ask whether practical proxies can detect this predicted increase. Drawing on the classical correspondence between lossless compression and Kolmogorov complexity, we argue that language-model perplexity occupies an analogous role in the probabilistic regime and propose the Binoculars perplexity-ratio score as one such proxy. Preliminary experiments with a color-based LLM steganographic scheme support the theoretical prediction: a paired $t$-test over 300 samples yields $t = 5.11$, $p < 10^{-6}$.