从I/O到代码的发现智能体

# 从输入输出到代码：基于发现代理 来源：https://arxiv.org/html/2605.15334 Yihong Dong1,2, Jiaru Qian3, Haoran Zhang4, Peixu Wang5, Binhua Li2, Zhi Jin1,3 Yongbin Li2, Ge Li1, Xiaokang Yang6, Xue Jiang1,2 1School of Computer Science, Peking University2Tongyi Lab, Alibaba Group 3Wuhan University4Renmin University of China5National University of Singapore 6Shanghai Jiaotong University ###### 摘要 从任意形式的规约出发自动化合成程序被视为计算机科学的圣杯。在大语言模型的推动下，NL2Code 取得了巨大成功，但更具根本性挑战的任务——从输入输出行为合成程序（我们称之为 IO2Code）——仍未得到充分解决。NL2Code 可以利用预训练过程中获得自然语言与代码之间的语义对齐，而 IO2Code 则需要从具体的计算行为中恢复底层原理，在庞大且欠定的假设空间中进行导航。为解决这一问题，我们提出 DIO-Agent，一种用于 IO2Code 的发现代理。我们的方法将 IO2Code 形式化为离散程序空间上的进化搜索，其中 LLM 充当变异算子，而来自执行的具象错误信号则指导每次变异。为防止搜索陷入结构复杂但错误的死胡同，我们引入变换优先级前提（Transformation Priority Premise）作为变异先验，使 LLM 偏向于与当前证据一致的最简假设，仅在较简单结构不足以解释时逐步升级为常量、条件语句到迭代。为便于系统研究，我们还构建了涵盖多个难度级别的 IO2CodeBench。大量实验表明，DIO-Agent 在所有难度级别和各种 LLM 上一致优于传统的示例编程方法和最先进的进化代理基线，同时在使用相同采样预算的情况下显著超越测试时扩展策略。111我们的代码和数据集可在 https://github.com/JiaruQian/IO2Code 获取。 ## 1 引言 大语言模型（LLM）在代码生成方面取得了显著成功（Chen et al.,2021; Nijkamp et al.,2022; Jiang et al.,2024; Dong et al.,2024），这主要建立在 NL2Code 范式之上（Iyer et al.,2018; Lu et al.,2021; Austin et al.,2021），该范式将自然语言描述转换为可执行程序（Hendrycks et al.,2021）。然而，大量现实任务要求开发者和研究人员并非从自然语言描述出发，而是从计算行为出发进行工作。从迁移源码丢失的遗留系统和逆向工程黑盒 API，到从科学观察中推断算法以及通过输入输出演示捕获用户意图，这些场景涵盖了系统演化、科学发现和人机交互（Collie et al.,2020）。我们将这一类任务称为 IO2Code，其目标是从输入输出行为合成程序（Figure1 (https://arxiv.org/html/2605.15334#S1.F1)）。NL2Code 在很大程度上简化为组合和重用与自然语言描述对齐的代码模式，这些模式在预训练过程中学习得到（Zan et al.,2023; Feng et al.,2020; Wang et al.,2021）。相比之下，IO2Code 要求归纳和发现，模型必须从具体的计算行为中揭示潜在的算法结构，推断输入与输出之间的因果关系，并自主构建完整的程序逻辑。这需要从特殊到一般的溯因推理，使得在 NL2Code 中有效的组合和重用策略不再适用。此外，输入输出观察本质上是欠定的，因为多个程序可能与有限的示例集一致，这就要求代理在庞大的假设空间中导航，同时避免过拟合到虚假模式。为应对 IO2Code 的挑战，我们借鉴了软件工程中一个成熟的观察结果。在测试驱动开发（TDD）实践中，变换优先级前提（TPP）（Martin,2021）表明，程序员在按复杂度递增顺序应用变换时，能够最高效地构建通过所有测试的算法：从常量到变量，从无条件语句到条件语句，再从条件语句到循环或递归。违反这一顺序常常会导致僵局，需要进行昂贵的重写。我们观察到，TPP 可以被重新用作自主程序发现的结构性约束。在 IO2Code 中，除了输入输出行为之外不存在任何规约，这种复杂度排序提供了一种有原则的机制，强制搜索过程在考虑结构更复杂的假设之前穷举较简单的假设，从而防止过拟合表面模式以及在程序空间中无目的游荡。在本文中，我们提出 DIO-Agent，一种用于 IO2Code 的发现代理。我们的方法将任务形式化为进化搜索，其中 LLM 充当变异算子。在没有自然语言指导的离散程序空间中，允许模型盲目变异代码很容易使其陷入结构复杂但错误的死胡同。为解决此问题，我们引入 TPP 作为变异先验，使搜索首先偏向于最简单假设，仅在较简单假设无法解释观察到的行为时才升级到更具表达力的结构。这一进化过程被组织为难度递增的课程，来自执行的具象错误信号将每次变异基于调试证据，而非标量奖励。为促进研究，我们建立了 IO2CodeBench，涵盖从基本数据操作到复杂算法推理的多个难度级别。我们在 IO2CodeBench 上进行了涵盖所有难度级别的广泛实验。结果表明，DIO-Agent 在现有方法（包括传统的 PBE 方法和最先进的进化代理基线）上取得了一致的改进，同时在使用相同采样预算的情况下显著超越了测试时扩展策略。此外，DIO-Agent 在不同基础模型上均取得了稳定的性能提升，证实了其泛化能力。我们还通过全面的消融研究、超参数敏感性分析和说明性案例研究进一步验证了每个组件的有效性。 ## 2 动机示例 为说明 IO2Code 的挑战并引出我们的方法，考虑一个具体示例。假设代理接收到以下输入输出对，并被要求合成一个与所有示例一致的程序 f： f(1) = [] f(2) = [2] f(3) = [3] f(4) = [2, 2] f(6) = [2, 3] f(8) = [2, 2, 2] f(12) = [2, 2, 3] f(30) = [2, 3, 5] 对于受过数学训练的人来说，底层规则是可以识别的：f 计算其输入的质因数分解。但代理没有收到任何提示。它无法访问函数名、文档字符串或自然语言描述，必须仅从计算行为中恢复规则。 #### 过拟合陷阱 最直接的策略（也是无约束模型倾向于采用的策略）是直接记忆这些观察结果： def f(n): if n==1: return [] elif n==2: return [2] elif n==3: return [3] ... 该程序反映了测试而不是从中泛化。它是一个查找表，而不是算法。它将在合成过程中未见过的任何输入（例如 f(9) 或 f(100)）上失败。在 NL2Code 中，这种过拟合不太可能发生，因为自然语言规约（例如“计算 n 的质因数”）已经将模型约束为通用解决方案。在 IO2Code 中，不存在这样的约束，代理面临的是一个欠定的假设空间，其中记忆总是局部最优的。 #### 盲目变异陷阱 另一种策略是应用进化搜索，随机变异候选程序并选择能通过更多测试用例的程序。然而，在没有结构指导的情况下，这种搜索很快就会遇到另一种失败模式。代理可能产生语法复杂但语义错误的程序。例如，一个计算除数而非质因数的程序，或者一个输出长度正确但值错误的程序。这些候选程序占据了程序空间中难以通过进一步变异脱离的复杂区域，形成了结构死胡同。无约束离散程序空间的组合爆炸使得盲目搜索对于除最简单任务外的所有任务都变得不可行。 #### 从特殊到一般 两种失败模式都有一个共同根源：缺乏从简单到复杂导航假设空间的策略。TPP（Martin,2021）恰恰提供了这样一种策略。在测试驱动开发的背景下，当程序员按结构复杂度递增的顺序应用改变行为的变换时，正确的算法最可靠地出现。TPP 确定了一个优先级顺序，从返回常量到变量，到条件语句，到循环，最终到递归，并证明遵循这一顺序可以避免过早尝试复杂变换时遇到的困境。为了解这一原则如何应用于 IO2Code，考虑当要求代理在我们的运行示例中遵循此复杂度排序时会发生什么，逐步增加结构复杂度并在进入下一级别之前穷尽每个级别： #### 级别 1–2：常量和变量 代理从最简单的程序开始： def f(n): return [] def f(n): return [n] 常量 return [] 仅处理 f(1)。泛化为 return [n] 覆盖了 f(2) 和 f(3)，但在 f(1) = [] 上退步，并在 f(4) = [2, 2] 上失败。没有变量级别的程序能满足所有观察结果。这表明规则涉及分解 n，而不仅仅是返回 n。 #### 级别 3：条件语句 代理引入条件语句以分割执行路径： def f(n): factors = [] if n % 2 == 0: factors.append(2) n = n // 2 if n > 1: factors.append(n) return factors 这捕获了整除测试的思想，但只应用了一次。f(8) = [2, 2, 2] 的情况表明单一条件语句是不够的：该操作必须重复。 #### 级别 4：迭代 代理将内部的 if 转换为 while： def f(n): factors = [] d = 2 while d <= n: while n % d == 0: factors.append(d) n = n // d d += 1 return factors 从 if 到 while 的转换使得最终程序能够泛化到所有输入，包括合成过程中从未见过的输入。 该策略为 IO2Code 提供了三个好处。它通过强制代理在诉诸特定案例逻辑之前穷尽较简单的假设来防止过拟合；它将搜索空间组织成一系列嵌套且表达能力递增的子空间；它在每个阶段产生信息丰富的失败模式，揭示需要何种额外的结构复杂度，从而引导代理进入下一泛化级别。 ## 3 方法论 本节首先形式化 IO2Code 任务，然后描述 DIO-Agent 的概览，最后详细介绍其关键要素，包括课程式进化、变换优先级引导的变异和基于错误的反馈。 #### IO2Code 的形式化 传统的代码生成任务通常依赖于自然语言意图。相比之下，IO2Code 问题旨在严格从有限的输入输出（I/O）对集合中合成一个通用程序。形式上，IO2Code 任务由一组可见示例 D_vis = {(x_i, y_i)}_{i=1}^n 定义，其中每个 x_i 是一个输入（标量、列表、元组或嵌套结构），y_i 是由未知目标程序 p* 产生的对应输出。目标是合成一个程序 p̂，使得 p̂(x_i) = y_i 对所有可见示例成立，并且关键在于 p̂ 能泛化到代理在搜索过程中从未观察到的保留测试用例 D_test = {(x_j, y_j)}_{j=1}^m。可见集上的适应度定义为： f(p̂) = (1/n) Σ_{i=1}^n 1[p̂(x_i) = y_i], (1) 其中 1[·] 是指示函数。候选程序被视为一个解当且仅当其在可见集上 f(p̂)=1.0 并且额外