使用推理代理的大规模反例引导学习

# 基于推理智能体的大规模反例引导学习  
**来源：** https://arxiv.org/html/2606.11521  

**Frederic Sala**  · 威斯康星大学麦迪逊分校计算机科学系  
**Thomas Reps**  · 威斯康星大学麦迪逊分校计算机科学系  
**Adithya Murali**  · 威斯康星大学麦迪逊分校计算机科学系  

###### 摘要  

LLM 及 LLM 智能体应在获得反馈后有所提升，但识别其是否具备这种能力却很困难：反馈具有异质性、领域特异性且难以控制。我们通过让 LLM 执行正则表达式归纳（一个经典的符号学习问题，其中存在以反例形式提供的精确反馈机制）来应对这一挑战。在反例引导学习中，学习器（LLM）根据正/负标签字符串提出候选正则表达式，而教师（验证器）则返回反例，展示候选语言与目标语言之间的差异。我们识别出能够实现有效正则表达式学习的新型反例引导优化策略，例如正则化和符号化反例聚类。我们还探索了反射和修复循环等智能体策略。实验发现，验证器反馈显著提高了具有挑战性的正则表达式归纳任务的样本效率，减少了所需标签示例的数量，并在标准提示失败的情况下实现了复杂目标表达式的学习。例如，在难度最高的任务组中，我们的反例引导框架将两个不同正则表达式领域的成功率分别从 3.2% 提升至 38.1%，以及从 38.9% 提升至 74.1%。这些结果表明，LLM 能够从丰富的反馈中受益，而非仅仅将其视为额外数据，这为基于 LLM 的程序合成和形式推理的稳健验证器引导方法打开了大门。  

## 1 引言  

模型、智能体和系统越来越多地需要从反馈中学习和适应。例如，编程智能体必须对错误和单元测试失败做出响应，使用工具的智能体在 API 调用失败后需要修订其计划，而个性化助手则需根据用户的纠正和偏好随时间调整其响应。尽管这一能力至关重要，但衡量模型利用反馈的效果却异常困难。反馈多样化、异质性强、通常与任务或领域紧密相关，且难以系统控制。是否存在一种简单可控的方式，来衡量模型和智能体利用反馈的能力？我们主张以*正则表达式归纳*作为衡量该能力的清晰测试平台。给定一组带标签的字符串，目标是通过从示例中泛化，以正则表达式的形式推断出底层语言的描述。该任务是符号学习中的一个经典问题，且极具挑战性：许多候选表达式都可能拟合一小组合标签的字符串，而简单的上下文内学习很容易过拟合到表层模式。在此设定下探索 LLM 的能力，是以现代视角重新审视自动机学习和程序合成领域的一系列长期工作。  

这个问题，乃至我们更大的目标，并未被现有工作完全解决。传统的神经序列模型（如 RNN）可以将正则表达式识别视为分类问题，但它们不自然地暴露符号假设，也不能明确地从仅基于反例的学习中获益。相反，LLM 可以生成显式的正则表达式，但目前的使用方式通常是提示驱动和启发式的，缺乏关于验证器反馈应如何在轮次间整合的结构化设计。现有工作也主要关注从自然语言描述合成正则表达式，而非纯粹基于示例的学习（Tang 等人，2026；Siddiq 等人，2024）。另一方面，尽管反例引导的方法在符号合成中已得到充分确立（Solar-Lezama，2013；Abate 等人，2018；Alur 等人，2013），但如何将其适应于现代基于 LLM 的推理，以实现样本高效、稳定且对过拟合具有鲁棒性，仍不清楚。此外，传统程序合成技术随着示例数量增加可能停滞不前。  

我们的工作贡献了两种方法之间急需的协同效应，将正则表达式归纳构建为一个由 oracle 引导的符号生成问题，其中模型通过验证器反馈（以（可能大量的）反例形式）迭代优化其假设。具体来说，在本文中，我们提出了一种基于 LLM 的正则表达式学习反例引导框架。我们的方法使用 LLM 和智能体从带标签字符串生成候选正则表达式，对照目标表达式进行检查，并从预测语言与目标语言的对称差中合成信息丰富的反例。我们进一步研究了：(a) 正则化策略，使模型倾向于更短、更简单、更合理的符号假设；(b) 反例的丰富变体，将具有共同失败信息的多个独立反例聚类；(c) 智能体策略，利用反射提取反例的结构含义，并通过修复循环迭代修正失败的正则表达式假设。  

实验发现，反例引导学习在符号生成设定下特别有帮助：在几个具有挑战性的正则表达式上，它显著减少了所需训练示例的数量，并且在某些情况下，能够在标准提示失败时成功恢复，如图1所示。  

**我们的贡献**。本文的主要贡献包括：  

- **LLM 正则表达式归纳的 oracle 引导形式化**：我们将基于 LLM 的正则表达式归纳建模为一个迭代的符号学习问题，其中候选正则表达式通过来自 oracle 的反例反馈进行优化。  
- **用于正则表达式归纳的基于 LLM 的主动学习方法**：为了构建有效的基于 LLM 的正则表达式归纳主动学习器，我们提升了经典的教师-学习器学习框架，采用基于 LLM 的学习器，并研究了诸如优先选择更简单假设的正则化以及符号化聚类反例等技术。  
- **大规模反例引导学习的智能体工作流**：我们构建了新颖的智能体框架，通过学习多个轮次中的反例进行推理，采用智能体反射和迭代表达式修复等技术来学习正则表达式。  
- **对带有验证器反馈的 LLM 学习动态的严格评估**：我们在两个正则表达式归纳数据集上研究了多种基于反例的学习器的性能。结果表明，我们的智能体框架在两个基准测试套件中最难的实例上，将学习性能从 3.2% 提升至 38.1%，以及从 38.9% 提升至 74.1%。我们进一步证明了我们的技术提高了样本效率，并且这些增益在不同基础模型系列中保持一致。我们还与基线进行了比较，并进行了消融研究，表明智能体框架的每个组件都贡献显著。  

![图1标题](https://arxiv.org/html/2606.11521#S1.F1)  
**图1：** 我们的智能体反例引导学习器（橙色）与无反例的标准提示（蓝色）的学习动态。随着示例数量增加，智能体学习器返回的假设更接近（距离通过差异比测量，即固定长度（图中为 32）的字符串中假设正则表达式与目标正则表达式不一致的比例，按任一正则表达式接受的字符串归一化）且更快地收敛到目标概念，展示了利用丰富反馈的价值。点表示平均距离，阴影区域表示变化范围。  

## 2 相关工作  

**正则语言学习或正则表达式归纳**。从示例和查询中学习正则语言在形式语言研究中有着悠久的历史。一个经典例子是 Angluin 的 L* 算法（Angluin, 1987），该算法通过成员查询和等价查询（带反例）学习正则集；这种 oracle 设定与我们的设定非常接近。除了基于查询的学习，先前的工作还研究了从示例直接推断正则表达式的方法，包括仅从正数据学习（Fernau, 2009）、基于搜索的从带标签示例合成（Lee 等人, 2016; Bartoli 等人, 2014），以及基于约束或优化的方法（Gao 和 Zhang, 2020）。在 LLM 出现之前，神经方法也探索了使用循环神经网络在带标签字符串上训练的正则语言学习，有时随后进行自动机提取或对所学有限状态结构的分析（Cohen 等人, 2018; Oliva 和 Lago-Fernández, 2021）。这些方法提供了重要的背景，但它们并未研究在以 LLM 为中心的设定下使用验证器引导优化的正则表达式生成。  

**反例引导的符号合成**。反例引导优化也是符号合成的核心。反例引导归纳合成（CEGIS）将候选生成与自动验证和反例生成相结合，在程序合成及相关符号推理任务中取得了巨大成功（Solar-Lezama, 2013; Abate 等人, 2018; Alur 等人, 2013）。除了程序生成，基于反例的监督也被用于符号学习问题，例如不变量合成（Garg 等人, 2014, 2016）和自动机相关推理（Weiss 等人, 2020），其中验证器反馈有助于暴露仅从正负示例中难以识别的错误。我们的工作与这一研究方向一致，但将其适应于以 LLM 为中心的设定，其中学习器不是符号搜索过程，而是一个必须解释反例并修正自身符号假设的语言模型。  

**LLM 用于符号推理、程序合成和正则表达式归纳**。近期研究表明，LLM 可以通过生成结构化输出（如代码、逻辑形式和符号规则）来支持符号推理和程序合成（Chen 等人, 2021; Austin 等人, 2021; Shin 等人, 2021）。在正则表达式相关任务中，先前工作表明语言模型可以从自然语言描述或提示中生成显式的正则表达式，通常结合示例、修复启发式或多模态和草图式合成机制，而非纯粹从带标签字符串进行归纳（Tang 等人, 2026; Siddiq 等人, 2024; Chen 等人, 2020; Ye 等人, 2020）。此外，LLM 越来越多地用于带有外部反馈的设定，包括验证中间推理步骤的过程监督方法（Lightman 等人, 2023）以及带有可验证奖励的强化学习（Liu 等人, 2025）。我们的工作与这些方向不同，我们研究的是从带标签字符串进行基于 LLM 的正则表达式归纳，并且我们不仅询问验证器提供的反馈是否有帮助，还研究如何整合这些反馈。  

## 3 问题陈述与动机  

我们的研究受到主动学习悠久历史的启发，其中学习器主动向教师索取反馈，并通过多轮交互利用反馈来“引导出”假设。具体来说，在符号学习/推理任务领域，LLM 的能力前沿可能参差不齐，对于如何很好地利用这些能力缺乏广泛共识。通过迭代反馈进行 oracle 感知学习的设定，为激发 LLM 的符号学习能力提供了更丰富的框架。同时，传统基于搜索的反例引导学习方法在面对复杂问题实例时，可能会因积累大量反例而性能下降，而基于机器学习的方法为解决这一问题提供了有吸引力的替代方案。这些事实共同推动了本文的高层研究问题：LLM 和智能体能为大规模反例引导学习带来什么？  

**Oracle 引导学习**。我们将研究的问题形式化为一个由 oracle/教师引导的主动学习问题。设 X 为元素域。我们将该域的子集称为*语言*。设 L* ⊆ X 为我们要学习的目标语言。学习器观察关于目标语言的有限证据（以域中带标签元素的形式），并合成一个候选语言。然后教师检查提出的候选，并以带标签元素的形式提供反馈，这些元素见证了候选的不正确性，即应该包含在目标语言中但未被候选语言包含的元素，反之亦然。请注意，在该框架的具体实现中，教师并不需要访问目标概念来提供此类反馈：它可以针对测试用例、约束或其他已知关于目标为真的属性来分析候选，并返回展示这些属性被违反的证人。  

**问题陈述：正则语言归纳**。我们将上述框架实例化用于正则语言归纳。实例空间 X 是有限字符串集 Σ*，其中 Σ 是有限字母表。我们研究的目标语言是那些可以用正则表达式（或等价地，有限状态自动机）表示的语言。给定一个正则表达式 r，我们用 L(r) 表示其语言。给定带标签的示例，学习器必须合成一个正则表达式 r̂，使得 L(r̂) 与目标语言 L* 匹配。该任务既是预测性的也是符号性的：输出必须正确分类字符串，同时还必须是可解释的表达式，能够被编译、验证并与目标进行比较。  

我们通过从对称差 L(r̂) △ L* 中采样来构建教师。我们之所以能在该设定中构建这样的教师，是因为正则语言在布尔运算下封闭，并且存在高效的现成库来构造对称差自动机（Romero, 2021）。  

## 4 用于反例引导归纳学习的推理智能体  

![图2标题](https://arxiv.org/html/2606.11521#S4.F2)  
**图2：** 我们提出的带有教师和学习器的迭代反例引导智能体优化框架概述。学习器使用智能体反