🤖 machine learning

LLM Priors for ERM over Programs

本文介绍了 \textsc{LLM-PV}，这是一个利用预训练大语言模型先验知识，在无需穷举枚举或梯度更新的情况下，高效地在离散程序类上执行经验风险最小化的“提议与验证”框架，从而在传统方法失效的算法任务上实现鲁棒的泛化。

原作者： Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

发布于 2026-07-03

📖 1 分钟阅读☕ 轻松阅读

原作者： Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

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

大问题：大海捞针

想象一下，你正试图教会计算机一个秘密规则。这个规则很简单，比如：“如果数字能被 3 整除，就说‘是’；否则，说‘否’。”但计算机并不知道这个规则，它只看到了几个数字示例及其对应的答案。

在计算机科学领域，有两种主要方法来尝试寻找这个规则：

“暴力破解”侦探： 这种方法试图把宇宙中所有可能的规则一个接一个地写下来，然后逐一检查是否符合示例。
- 问题在于： 如果规则稍微复杂一点（比如规则的总数多到像地球上所有沙滩上的沙粒一样），这种方法可能需要比宇宙年龄还要长的时间才能完成。它太慢了。
“梯度下降”学生： 这是现代 AI（比如你使用的聊天机器人）通常学习的方式。它从一个猜测开始，通过不断微调其内部的“旋钮”来做得更好，就像一个学生通过犯错并纠正错误来为考试做准备。
- 问题在于： 对于某些类型的逻辑规则（比如检查一个数字是否为质数或统计特定模式），这种“微调”方法会陷入困境。它可能会完美地背下练习题，但在面对一个新的、略有不同的问题时却彻底失败。这就像是一个背下了答案但并没有真正理解数学原理的学生。

新方案：LLM-PV（聪明的图书管理员）

作者提出了第三种方法，叫做 LLM-PV。你可以把它想象成雇佣了一位聪明的图书管理员来帮你寻找规则。

以下是该过程的逐步运作方式：

提议（图书管理员的猜测）： 你不是去检查图书馆里的每一本书（暴力破解），也不是试图从头重写整个图书馆（梯度下降），而是向这位聪明的图书管理员（一个预训练的大型语言模型）寻求几个建议。
- 神奇之处： 这位图书管理员读过数百万本书籍和代码片段。当你展示给它一些示例时，它并不会随机猜测。它利用自己的“直觉”（先验知识）来建议几个可能有效的、合理的规则。它将搜索范围从“所有可能的规则”缩小到了“少数几个可能的候选者”。
验证（试驾）： 图书管理员将这些规则写成实际的计算机代码。然后，你运行这些代码片段来检查它们是否符合你的示例。
- 关键点： 图书管理员不允许根据测试结果改变主意。它只负责提出建议。最终胜出者的筛选过程完全是通过严格检查代码与数据的匹配程度来完成的。
选择（优胜者）： 你挑选出那个能得出最多正确答案的代码片段。

为什么这很重要

论文表明，这种“聪明的图书管理员”方法效率极高。

它很快： 它不需要检查数十亿条规则，只需要检查少数几个聪明的猜测。
它很准确： 与那些在逻辑谜题上经常失败的“微调型”AI 方法不同，这种方法实际上能找到确切的数学规则（例如用于检查质数的 Miller-Rabin 素性检验）。
它具有泛化能力： 这是最令人印象深刻的部分。如果你用短数字（例如 10 位数）来教这个系统，它学到的是规则，而不只是数字本身。因此，当你要求它检查一个 100 位的数字时，它依然能完美运行。而“微调型”AI 通常会在这里失败，被更长的数字搞糊涂。

一个现实世界的类比：学习烘焙

想象一下，你想学习制作蛋糕的秘密配方。

暴力破解： 你尝试用每一种可能的食材组合（盐、糖、沙子、石头等）来烤蛋糕，直到其中一个味道对了为止。这要花上一辈子的时间。
梯度下降（标准 AI）： 你烤了一个蛋糕，尝了一下，说：“缺点糖。”你又烤了一次，“少点面粉。”你不断重复。最终，你可能做出一个味道和你要模仿的那款极其相似的蛋糕，但如果你改变了烤箱温度或面粉品牌，你的蛋糕就会垮掉，因为你只是学会了模仿那一次特定的批次，而不是学会了烘焙的原理。
LLM-PV： 你请教了一位看过无数食谱的大厨（LLM）。你给了他们一些关于这款蛋糕的线索。大厨说：“我猜这是一款带有特定香料组合的巧克力蛋糕。”他们写下了三份具体的配方。你烤了这三份。其中一份非常完美。你既不需要烤一百万个蛋糕，也不需要无休止地微调配方。你得到了适用于任何烤箱的实际配方。

核心结论

论文认为，我们不应该仅仅使用 AI 来直接预测答案，而应该将 AI 作为一种搜索工具，用来生成潜在的解决方案（程序），然后通过严格的测试来挑选出最好的一个。这结合了大型语言模型的“常识”与计算机程序的可靠性，使我们能够通过极少的示例学习复杂的规则。

技术摘要：LLM 先验用于程序集的经验风险最小化 (ERM)

问题陈述

本文探讨了在从标记数据中学习短且离散的程序描述（例如“Python 代码”）时，样本效率 (sample efficiency) 与 计算效率 (computational efficiency) 之间存在的根本矛盾。

经典学习理论（PAC 学习）表明，如果目标函数存在一个长度为 $L$ 、字母表为 $\Sigma$ 的短程序描述，则可以通过对程序类进行 经验风险最小化 (ERM)，仅需 $\tilde{O}(L \log |\Sigma|)$ 个样本即可完成学习。然而，实现 ERM 需要对候选程序进行 穷举枚举 (exhaustive enumeration)，其复杂度为 $\Theta(|\Sigma|^L)$ ，这使得即使对于中等长度的 $L$ ，在计算上也变得不可行。

相反，使用 随机梯度下降 (SGD) 处理高容量神经网络的现代深度学习方法避免了显式枚举，具有较高的计算效率。然而，统计查询 (SQ) 框架下的理论结果表明，基于梯度的算法在处理结构化的、“SQ 困难”的族（如奇偶校验函数和加密原语）时表现不佳。这些方法通常需要指数级的样本量才能成功，因为梯度接口与目标规则的离散结构不匹配，导致无法超越训练序列长度进行泛化。

核心问题是：我们能否在不付出全额穷举代价的前提下，恢复程序集 ERM 的样本效率？

方法论：LLM-PV

作者提出了 LLM-PV（LLM 提议与验证），该算法将预训练的大型语言模型 (LLM) 不仅仅视为一个预测器，而是将其视为 ERM 的一个 搜索先验 (search prior)。

算法流程

LLM-PV 将“提议”与“选择”的角色解耦：

提议（先验）： 使用预训练的 LLM，通过提示词 (prompting) 输入训练集 $S_{tr}$ ，从而诱导出关于候选程序的依赖于数据的分布。LLM 生成少量候选程序（或编辑后的程序），这些程序被假设能够解释数据。
验证（ERM 步骤）： 每个候选程序都会在留出的验证集 $S_{val}$ 上进行编译并执行。无法编译、无法停机或产生无效输出的程序将被丢弃。
选择： 算法选择验证误差最低的程序。至关重要的一点是，不对 LLM 进行任何梯度更新，且在搜索过程中不会利用验证反馈来调整 LLM 的采样分布。LLM 仅作为一种归纳偏置机制发挥作用。

理论框架

作者通过“提议与验证”保证来形式化 LLM-PV 的性能。如果 LLM 的提议分布在总体误差 $\le \epsilon$ 的程序上具有非零的概率质量 $p_\epsilon(S_{tr})$ ，那么找到一个良好假设所需的尝试次数 $k$ 规模为 $O(\log(1/\delta) / p_\epsilon(S_{tr}))$ 。这通过有效搜索空间大小 $1/p_\epsilon(S_{tr})$ 取代了指数级的搜索空间 $|\Sigma|^L$ 。

作者还提供了理论下界，证明对于植入的 $k$ -奇偶校验问题，有限精度的小批量坐标 SGD 需要 $\Omega(\sqrt{N}/2^b)$ 个新鲜样本（其中 $N$ 是可能的候选目标数），而枚举则需要 $\Theta(|\Sigma|^L)$ 的时间。这确立了一个既无法通过朴素枚举也无法通过标准梯度训练解决的区间，从而为 LLM-PV 方法提供了动机。

核心贡献

形式化计算与样本的张力： 本文隔离了一个特定的极小数据区间（植入的 $k$ -奇偶校验），在该区间内，有限类 ERM 具有样本效率但计算上难以实现，而基于梯度的训练虽然计算便捷，但由于 SQ 困难性而在样本效率上表现低下。
LLM-PV 算法： 引入了一个清晰的“提议与验证”流水线，该流水线严格将预训练 LLM 用作提议机制。这保留了 ERM 的可审计性和理论保证（基于留出误差进行选择），同时利用了 LLM 将搜索集中在合理假设上的能力。
规则恢复的实证证据： 在多种算法任务（奇偶校验变体、模式匹配、回文、Dyck-2、素性测试、细胞自动机和 SHA-256 奇偶校验）中的广泛实验表明，LLM-PV 通常能从仅 200 个标记样本中恢复出精确的底层规则。
长度泛化： 不同于经过 SGD 训练的 Transformer、微调模型或上下文学习 (ICL) 基准模型（这些模型往往会记忆训练分布并在更长的输入序列上失效），LLM-PV 经常能合成 维度不变的程序 (dimension-invariant programs)，从而在远超训练长度的输入上实现完美泛化。
可审计性： 该方法生成可执行、人类可读的代码以及完整的推理轨迹（一系列提议的程序及其验证误差），允许对学习过程进行直接的调试和机械化验证。

结果

作者将 LLM-PV 与广泛的基准模型进行了评估，包括经典机器学习（XGBoost、SVM、遗传算法）、SGD 训练模型（从头训练和微调）以及使用大型指令微调模型的上下文学习 (ICL)。

算法任务： 在 10-奇偶校验、细胞自动机奇偶校验和素性测试等任务上，标准基准模型（包括 30B+ 参数的 ICL 模型）在测试长度（ $n=100$ ）下的表现接近随机猜测（50% 准确率），即使在拥有 200 个样本的训练情况下也是如此。相比之下，LLM-PV 在相同的 200 个样本下实现了 100% 的测试准确率。
泛化能力： 当在短序列（ $n=10$ ）上训练并在长序列（ $n=100$ ）上测试时，基于 SGD 和微调的基准模型准确率降至随机水平。LLM-PV 则保持了高准确率，成功合成了对输入长度具有不变性的规则。
数据缩放： 增加基于 SGD 模型的训练集规模（最高达 10 万个样本）并未解决其在奇偶校验和细胞自动机任务上的泛化失败问题，这证实了这些任务对于基于梯度的学习器具有 SQ 困难的本质。
工具使用： 论文指出，虽然工具增强型 ICL（模型可以运行代码）比直接提示表现更好，但它仍无法可靠地恢复算法规则。LLM-PV 的成功归功于特定的 搜索目标（提议程序并根据验证误差进行选择），而非仅仅依靠工具访问权限。
表格数据： 在标准的表格基准测试中，LLM-PV 的表现与强大的表格学习器相当，表明该方法并不局限于合成序列任务。

意义与主张

本文声称，预训练 LLM 的先验可以作为 ERM 有效的搜索偏置，成功缩小了程序学习中统计效率与计算效率之间的差距。

其核心意义在于 角色的分离：LLM 仅用于提议假设，而学习目标仍然基于可执行的验证和留出误差。这种方法：

通过输出显式的、可验证的代码，避免了基于梯度的预测器的“黑盒”性质。
克服了基于梯度的方法在处理存在短描述的结构化、离散任务时的样本低效问题。
提供了一种实现 长度泛化 的机制，而标准的深度学习方法在算法任务上难以实现这一点。

作者对研究范围保持了审慎态度，承认该方法依赖于 LLM 能够在正确程序上放置足够质量的能力，并且目前该方法是针对结构化、低数据场景定制的，而非旨在取代处理非结构化数据的通用监督深度学习。该方法的成功取决于“提议者”是否足够强大，以及“验证”步骤是否足够稳健。