LLM-ERM: Sample-Efficient Program Learning via LLM-Guided Search

• ArXiv URL: http://arxiv.org/abs/2510.14331v1

• 作者: Tomer Galanti; Shivam Singhal; Eran Malach; Tomaso Poggio

• 发布机构: Harvard University; MIT; Texas A&M University

---

TL;DR

本文提出了一种名为 LLM-ERM 的新型程序学习算法，该算法通过大型语言模型（LLM）引导的搜索来高效地最小化经验风险，从而仅需极少量（例如1-2个）的输入输出样例就能成功合成正确的程序。

关键定义

本文主要建立在现有概念之上，并将其创新性地结合，核心概念如下：

1. 程序综合 (Program Synthesis)：指根据给定的高级规约（Specification），自动生成满足该规约的计算机程序的过程。在本文中，规约特指一组输入输出样例。
2. 经验风险最小化 (Empirical Risk Minimization, ERM)：机器学习中的一个核心原则。其目标是在所有可能的模型（在这里是程序）中，找到一个能在给定的训练数据集（在这里是输入输出样例）上实现最小化平均误差（即“经验风险”）的模型。本文将找到完全满足所有样例的程序视为一个经验风险为零的特例。

3. LLM 提议分布 (LLM Proposal Distribution)：在本文的搜索算法中，LLM 扮演的角色。它根据当前程序、任务描述以及失败的样例，生成一个修正后的新候选程序。这个过程被建模为一个从当前程序到新程序的概率分布 $$Q(p’

   p)$$，LLM 的生成能力为这个分布提供了强大的先验知识。

相关工作

程序综合领域长期致力于从用户意图中自动生成代码。传统方法，如基于枚举或约束求解的合成器，虽然具有形式保证，但通常面临组合爆炸问题，计算成本高昂。

近年来，大型语言模型（LLM）在代码生成方面展现了巨大潜力，可以直接根据自然语言描述或少量示例生成程序。然而，LLM 生成的程序往往缺乏严格的正确性保证，在需要精确逻辑的复杂任务上，仅靠几次提示（few-shot prompting）很难直接生成满足所有测试样例的完美程序。为了解决这个问题，研究者们尝试了多种方法，包括让 LLM 自我修正或结合外部验证器进行搜索，但这些方法在样本效率 (sample efficiency) 方面仍有很大提升空间——即它们通常需要较多的输入输出样例才能找到正确解。

本文旨在解决的核心问题正是程序综合中的样本效率瓶颈：如何在仅提供极少数（例如，仅一个）输入输出样例的情况下，高效、可靠地合成出正确的程序。

本文方法

本文提出的方法名为 LLM-ERM，它将程序学习问题巧妙地形式化为一个在庞大程序空间中进行经验风险最小化（ERM）的搜索问题，并利用 LLM 来高效地指导这一搜索过程。

方法本质

LLM-ERM 的核心思想是执行一个迭代的局部搜索（具体实现为贪心爬山算法），以找到一个能够正确处理所有给定输入输出样例的程序 \(p*\)。在搜索的每一步，算法都试图从当前程序 \(p_t\) 移动到一个“更好”的程序 \(p_{t+1}\)，而“更好”的衡量标准就是新程序是否能正确解决更多样例（即降低经验风险）。

算法流程如下：

1. 初始化：通过 LLM 直接生成一个初始程序 \(p_0\)。
2. 评估：计算当前程序 \(p_t\) 在所有样例上的经验风险 \(L(p_t)\)，即失败样例的比例。如果风险为零，则搜索成功，返回 \(p_t\)。

3. 提议：将当前程序 \(p_t\)、任务描述、所有输入输出样例、以及 \(p_t\) 具体在哪几个样例上失败的信息，一同输入给 LLM。LLM 被要求“修正”这个程序，并生成一个新候选程序 \(p'\)。这一步利用了 LLM 强大的代码理解和生成能力，充当了一个智能的“提议分布” $$Q(p’

   p_t)$$。

4. 决策：比较新程序 \(p'\) 和当前程序 \(p_t\) 的风险。采用贪心策略，如果新程序的风险 \(L(p')\) 低于当前程序的风险 \(L(p_t)\)，则接受新程序，即 \(p_{t+1} = p'\)。否则，保留原程序，\(p_{t+1} = p_t\)。
5. 迭代：重复步骤 2-4，直到找到风险为零的程序或达到最大迭代次数。

创新点

LLM-ERM 与以往方法最本质的区别在于，它将 LLM 的生成能力与经典的 ERM 优化框架进行了原则性地结合。它不是简单地让 LLM 一次性生成最终答案，也不是盲目地搜索，而是：

• 结构化的迭代改进：通过一个清晰的“评估-提议-决策”循环，将复杂的程序生成任务分解为一系列更简单的代码修正任务。LLM 在每一步都获得了关于当前解的明确、具体的反馈（即失败的样例），使其能够进行有针对性的改进。
• 高效的搜索空间探索：LLM 强大的代码先验知识极大地压缩了搜索空间。它不会像传统方法那样盲目尝试，而是直接提出最有可能正确的修改方案。这使得搜索过程能够以极高的效率收敛到正确解，从而实现了前所未有的样本效率。
• 框架的简洁与通用性：LLM-ERM 框架本身非常简洁，不依赖于特定领域的语言（DSL）或复杂的梯度计算。它只需要一个能够执行程序的“黑盒”验证器，因此具备很强的通用性，可以应用于各种不同的程序综合任务。

实验结论

本文在一系列具有挑战性的程序综合基准（包括字符串变换和文本编辑任务）上进行了广泛实验，以验证 LLM-ERM 的有效性。

关键结果

• 极高的样本效率：LLM-ERM 展现了最核心的优势。如下图所示，在仅提供1个输入输出样例的情况下，LLM-ERM 的成功率远超所有基准方法，包括直接用 LLM 生成 (\(LLM-GEN\)) 和经典的程序综合方法。随着样例数量增加到2或3个，其性能优势进一步扩大，迅速接近饱和。

  

• 性能显著超越基准：在所有测试的数据集上，LLM-ERM 的综合性能（求解率）均大幅领先于现有最先进的模型。例如，在 \(STRINGS\) 数据集上，仅用一个样例，LLM-ERM 的成功率达到 62.7%，而强基准 \(LLM-GEN\) 仅为 34.0%。

  方法	样例数=1	样例数=2	样例数=3
  BPL	10.7	12.0	12.0
  RobustFill	12.0	25.3	25.3
  LLM-GEN	34.0	44.7	45.3
  LLM-ERM (本文)	62.7	70.7	70.7

  表：在 STRINGS 基准上的成功率 (%)

• 搜索过程的必要性：消融实验证明，LLM-ERM 的成功并非仅仅源于使用了强大的 LLM，其核心的迭代搜索机制至关重要。与仅依赖初始生成或一次修正的方法相比，多步迭代搜索显著提高了找到正确程序的概率。

结论

实验结果有力地证明，将程序学习问题构建为由 LLM 引导的经验风险最小化问题，是一种极其有效且样本高效的范式。LLM-ERM 能够在仅依赖一两个样例的条件下，解决以往方法需要更多数据才能处理的复杂程序综合任务。这表明，结合 LLM 的强大先验和形式化的搜索算法，是推动自动编程和人机交互向前发展的关键方向。