LLM最短提示复杂度：衡量生成目标文本所需最少提示

背景

随着大语言模型（LLM）的广泛应用，提示工程（prompt engineering）已成为影响模型输出质量的关键技术。然而，一个根本性问题始终悬而未决：对于给定的指令微调模型，到底需要多短的提示（prompt）才能可靠地生成一段特定文本？这个问题本质上类似于计算理论中的 Kolmogorov 复杂度，但传统的 Kolmogorov 复杂度定义在通用图灵机之上，而 LLM 的行为高度依赖其参数、训练数据和解码规则。因此，研究者需要一种针对具体模型的、可计算的复杂度度量，以形式化描述提示长度与目标输出之间的资源约束关系。本文正是从这一角度出发，提出了“提示复杂度”（prompting complexity）的概念，并围绕它构建了一个新的理论框架与研究议程。

核心内容

本文定义的核心概念是prompting complexity：对于一个固定的指令微调语言模型（instruction-tuned LM），使确定性解码（deterministic decoding）产生目标文本所需的最短合理提示（plausible prompt）的长度。这是一个与资源受限的 Kolmogorov 复杂度（resource-bounded Kolmogorov complexity）相对应的 LM 版本。在经典 Kolmogorov 复杂度中，程序作为输入在通用解释器上运行产生输出；这里，提示（prompt）充当“程序”，模型接口充当“解释器”，而提示中省略的信息由模型权重、训练数据分布、分词器（tokenizer）、模板和解码规则共同提供。

与经典 Kolmogorov 复杂度不同，该度量故意设计为非通用的（intentionally non-universal）。也就是说，它并不假设存在一个独立于模型的 invariance theorem 来保证不同模型之间的一致性。同一段文本对于一个模型可能是“廉价”的（只需极短提示即可生成），而对另一个模型则可能完全不可达或需要极长的提示。这种非通用性恰恰反映了现实世界中不同模型内部知识表征与推理能力的差异。

在有限上下文设定下，prompting complexity 可以通过枚举所有候选提示来计算（因为搜索空间有限）。但为了与实际的提示工程实践保持一致，本文将候选程序限制为“合理的人类可读文本”，而非任意的 token 字符串（arbitrary token strings）。这意味着提示必须是自然语言形式的、可在实际使用中由人写出的句子，而不是经过特殊编码的 token 序列。

本文还将精确的 prompting complexity 定义扩展到了软提示复杂度（soft prompting complexity），用于处理近似输出（approximate outputs）。这相当于一种有损的模型相对文本压缩（lossy model-relative text compression），也为提示优化提供了一个形式化的优化目标。此外，作者定义了提示距离（prompting distance），通过比较不同文本的最短生成提示来量化它们之间的语义或行为距离。最后，文章提出了行为提示复杂度（behavioral prompting complexity），用于衡量通过提示使模型输出满足某种规范（specification）所需的最短提示长度。

基于这些形式化定义，作者提出了一项研究议程，目标是实证探索在固定 LM 接口下，哪些文本和行为可以通过短而合理的提示被访问，哪些则需要更长或更复杂的提示。

关键要点

• prompting complexity 是 LLM 版本的资源受限 Kolmogorov 复杂度：提示是程序，模型是解释器，模型参数和训练数据充当隐藏的先验知识。
• 该度量是非通用的：不同模型对同一文本的 prompting complexity 可能差异巨大，不存在跨模型的 invariance theorem。
• 有限上下文下可通过枚举计算，但搜索空间被限制为“人类可读的合理提示”，而非任意 token 序列，以贴近实际提示工程。
• 扩展了软提示复杂度（soft prompting complexity）以处理近似输出，开启了有损压缩视角下的提示优化形式化目标。
• 定义了提示距离（prompting distance）和行为提示复杂度（behavioral prompting complexity），分别用于衡量文本间关系以及满足规范的行为可达性。
• 基于该框架提出研究议程：实证探索哪些文本/行为可通过短提示实现，哪些则需要更长提示，从而揭示模型的知识分布与能力边界。

意义与影响

本文为提示工程提供了一个严格的形式化基础。过去，提示设计多依赖经验法则和试错，缺乏理论指导。prompting complexity 的提出使得“最短提示”问题成为可计算、可比较的量化指标，有助于：

1. 优化提示效率：通过形式化目标（最小化提示长度同时保持输出质量），可以指导自动提示搜索算法（如基于枚举或梯度的方法）的设计。
2. 理解模型内部知识：不同模型对同一文本的 prompting complexity 差异，反映了其训练数据、架构和微调策略带来的知识偏差。短提示可达的文本表明该知识在模型中高度内化，而长提示或不可达的文本则揭示了知识盲区。
3. 跨模型比较：虽然度量是非通用的，但可以在同一任务上比较不同模型的 prompting complexity 分布，从而量化模型的“易用性”或“可提示性”。
4. 行为可控性：行为提示复杂度为评估模型能否通过短提示实现特定行为（如遵循指令、避免有害输出）提供了工具，有助于安全性与对齐研究。
5. 连接理论计算机科学：该工作将 Kolmogorov 复杂度的思想引入 LLM 领域，建立了模型相对信息论与自然语言处理之间的桥梁，可能激发更多关于“程序-解释器”视角下语言模型的形式化研究。

总之，本文提出的 prompting complexity 框架不仅填补了 LLM 提示工程理论化的空白，也为实证研究提供了一条清晰、可操作的路径，有望推动提示优化、模型评估和可解释性等方向的进展。