ReaComp：将LLM推理编译为符号求解器以实现高效程序合成

# ReaComp：将 LLM 推理编译为符号求解器，实现高效程序合成  
来源：https://arxiv.org/html/2605.05485  
Atharva Naik† Yash Mathur♣ Prakam♣ Carolyn Rose† David Mortensen†  
†卡内基梅隆大学，♣独立研究员  
\{arnaik,cprose,dmortens\}@cs.cmu.edu [email protected]  

###### 摘要  

LLM 能解决程序合成任务，但在需要大规模组合搜索的困难实例上仍然低效且不可靠。给定少量推理轨迹，我们使用编码代理将其编译为受约束 DSL 上的可复用符号程序合成器。所得求解器在测试时无需任何 LLM 调用，且是强大的独立系统：符号求解器集成在 PBEBench-Lite 上达到 91.3% 的准确率，在 PBEBench-Hard 上达到 84.7%，在后者上以零 LLM 推理成本比采用测试时扩展的 LLM 高出 +16.3 个百分点。它们还补充了 LLM 搜索，将 PBEBench-Hard 准确率从 68.4% 提高到 85.8%，同时报告 token 使用量减少 78%，并在神经符号混合设置中将 SLR-Bench 困难级别的准确率从 34.4% 提高到 58.0%。与直接使用编码代理作为每个实例的求解器相比，诱导求解器在帕累托效率上显著更优，将一次性的小构建成本摊销到多次零 token 执行中。最后，大多数求解器零样本迁移到真实历史语言学任务——预测自然语言数据中的音变——在集成下达到 80.1% 的准确率，并恢复了一些合理的语言学规则。这些结果共同表明，推理轨迹可以被编译为可复用的符号求解器，这些求解器能直接解决许多任务，在困难案例上补充 LLM 推理，并提供一条可扩展的领域通用求解器归纳路径。我们发布代码和数据以支持可复现性¹¹¹https://github.com/cmu-llab/ReaComp  

参照图注  
图 1：ReaComp：离线求解器归纳将 LLM 推理轨迹编译为可复用的符号求解器；测试时推理直接应用求解器（零 LLM 成本），仅在未解决情况下回退到 LLM 搜索。  

## 1 引言  

“基于示例编程”（PBE）范式（Gulwani, 2011 (https://arxiv.org/html/2605.05485#bib.bib9)）为研究结构化推理和组合泛化提供了一个受控环境，其应用涵盖代码转换、数据整理、文本处理和历时语言学。近期研究表明，当与 Best-of-KK 采样和迭代优化等扩展策略结合时，大型语言模型（LLM）能在 PBE 任务上取得强劲性能（Li and Ellis, 2024 (https://arxiv.org/html/2605.05485#bib.bib12); Naik et al., 2025b (https://arxiv.org/html/2605.05485#bib.bib15)）。特别是，先前的工作如 PBEBench (Naik et al., 2025b (https://arxiv.org/html/2605.05485#bib.bib15)) 表明，足够强大的推理模型配合这些扩展策略，可以在没有显式符号结构的情况下在 PBE 任务上取得高准确率。然而，这种性能伴随着巨大的计算成本。通过对推理轨迹和扩展行为的分析，我们发现困难实例需要不成比例地更多的尝试次数和 token 使用量（图 3 (https://arxiv.org/html/2605.05485#A1.F3)），这通常是由于组合泛化的失败和低效的搜索。即使是像 gpt-oss-120b 这样强大的推理模型也表现出不稳定的行为，包括单次尝试内的循环以及在迭代优化设置中跨尝试的冗余探索。此外，我们观察到基于 LLM 的搜索在短小、简单的程序上表现良好，但在更长、更具组合性的转换上性能显著下降。这些模式表明，尽管 LLM 能力强大，但它们缺乏显式的机制来结构化候选程序上的搜索，导致在困难任务上浪费计算，尤其是当解决方案长度增加时。  

一种自然的做法是用工具或学习到的库来增强 LLM，包括从经验中诱导可复用抽象的方法（Wang et al., 2024b (https://arxiv.org/html/2605.05485#bib.bib24); Stengel-Eskin et al., 2024 (https://arxiv.org/html/2605.05485#bib.bib20); Yue et al., 2025 (https://arxiv.org/html/2605.05485#bib.bib27)）。虽然这些方法表明 LLM 可以获取有用的结构，但它们通常依赖于推理时的迭代推理和工具调用，因此仍然对计算预算敏感。在计算匹配的评估下，它们的增益主要来自推理时计算的增加，而不是所学工具的有效复用，且工具跨实例一致复用的证据有限（Sesterhenn et al., 2025 (https://arxiv.org/html/2605.05485#bib.bib17)）。因此，它们仍然在解空间上进行基本无结构的搜索。  

在这项工作中，我们提出 ReaComp：我们不改进推理时的推理，而是将其*编译*为可复用的符号结构。我们的方法包括两个阶段：**离线求解器归纳**和**测试时推理**。在离线阶段，我们直接从 LLM 推理轨迹中诱导*符号求解器*，使用编码代理将反复出现的策略和失败模式提炼为受约束 DSL 上的独立程序合成器。这些求解器在测试时无需任何 LLM 调用，可以直接解决大部分任务，通常在困难实例上与 LLM 搜索匹配甚至超越。在测试时，求解器提供一个廉价、结构化的第一轮处理，LLM 仅在未解决的情况下作为回退被调用（Zhang and Park, 2025 (https://arxiv.org/html/2605.05485#bib.bib28)）。  

我们在近期具有挑战性的基准 PBEBench (Naik et al., 2025b (https://arxiv.org/html/2605.05485#bib.bib15)) 和 SLR-Bench (Helff et al., 2025 (https://arxiv.org/html/2605.05485#bib.bib10)) 上评估 ReaComp，结果表明诱导的符号求解器在实现强大独立性能的同时显著提高了推理效率。符号求解器集成在 PBEBench-Lite 上达到 91.3% 的准确率，在 PBEBench-Hard 上达到 84.7%，以零 LLM 推理成本在 Hard 上比采用测试时扩展的 LLM 基线高出 +16.3 个百分点（pp）。在 SLR-Bench 上，符号求解器在最困难级别上与前沿 LLM 持平，当与直接反馈结合时，将困难级别准确率从 34.4% 提高到 58.0%。混合推理将 token 使用量减少高达 78%。通过将一次性的小构建成本摊销到多次零 token 执行中，诱导求解器在帕累托意义上优于将同一编码代理直接应用于每个任务的方法。最后，大多数求解器零样本迁移到历时语言学中的正向重构——预测相关语言之间声音如何变化——在集成下达到 80.1% 的准确率，并恢复了合理的音变规则。  

**贡献**。我们提出 ReaComp，贡献如下：(1) 一种通过编码代理从 LLM 推理轨迹中诱导可复用符号求解器的方法；(2) 证据表明诱导的求解器是强大的独立系统，以零每任务 LLM 推理成本在困难实例上超越 LLM 测试时扩展；(3) 一个神经符号混合流水线，在帕累托意义上优于每任务代理努力，将 token 使用量减少高达 78%，同时取得最先进的结果；(4) 一个实证，表明大多数诱导求解器在分布外零样本泛化，以及在历时语言学正向重构上的案例研究。  

## 2 方法  

#### 问题形式化。  
令 X 和 Y 分别表示输入和输出空间。一个 PBE 任务是一个有限的示例集 D = \{(x_i, y_i)\}_{i=1}^n。目标是从 DSL P 中推断出一个程序 p ∈ P，使得对于所有示例 p(x_i) = y_i。我们使用一个任务级奖励 R(p; D) ∈ [0,1]，其中 R=1 表示完全正确的解。  

我们提出 ReaComp，一个两阶段方法，它 (1) 将 LLM 推理轨迹编译为符号求解器，并且 (2) 在混合推理流水线中将这些求解器与基于 LLM 的搜索结合使用。  

### 2.1 LLM 搜索过程  

LLM 定义了一个条件分布 p ∼ π_θ(·∣D)。我们考虑两种标准的测试时扩展策略，都选择 p^* = arg max_{p∈C} R(p; D)：  

- **Best-of-KK (BoK)**。独立采样 KK 个程序，选择得分最高的候选：C = \{p_k\}_{k=1}^K。  
- **Direct Feedback (DF)**。通过条件化验证器反馈的迭代优化生成轨迹 \{p^{(t)}\}_{t=1}^T：C = \{p^{(t)}\}_{t=1}^T。  

两者在 R=1 时应用提前停止。两者都定义了用于我们混合推理的候选集 C。  

### 2.2 离线求解器归纳  

求解器归纳是一次性的离线过程，将推理轨迹编译为一个独立的符号程序合成器。给定训练任务 \{D_j\}_{j=1}^m 和对应的轨迹 \{τ_j\}_{j=1}^m，我们通过一个编码代理诱导求解器 S_φ: D ↦ P，该代理近似最大化 ∑_j R(S_φ(D_j); D_j)，并从轨迹中提炼可复用结构和失败模式。  

**轨迹数据集**。  
我们构建一个数据集 T = \{(D_j, τ_j)\}_{j=1}^m，包含由 LLM（例如 gpt-oss-120b）生成的推理轨迹，并按任务难度和成功/失败平衡采样。每个轨迹包含中间推理步骤、候选程序和结果。归纳任务是基准任务的一个小子集；归纳过程中不访问真实程序。编码代理仅观察任何求解器在测试时可用的输入-输出示例。  

**基于编码代理的归纳**。  
我们使用一个编码代理 A_ψ 迭代地构建求解器实现。该代理在一个沙箱化容器中运行，该容器包含轨迹数据集和验证器代码（只读访问，以避免篡改验证器）。对验证器的访问允许代理测试候选求解器并迭代调试或优化它们。在每一步，代理提出对工作区的编辑、执行代码，并根据在 T 上的表现优化求解器。最终输出是一个独立的 Python 求解器文件 SOLVER.py 以及相应的算法描述文件 (SOLVER_ALGORITHM.md)。  

我们实验了两种求解器归纳的编码代理：(i) **Claude Code (CC)**，使用 claude-sonnet-4-6 在无约束交互会话中运行；(ii) **Qwen + OpenHands (QO)**，使用 Qwen3.6-35B-A3B 并限制轨迹（每次运行最多 500 步），以模拟资源受限的环境。对于这两个代理，我们为每个基准（PBEBench 和 SLR-Bench）构建了大约 100 个示例的轨迹数据集，按任务难度和结果（成功 vs. 失败）平衡采样，使代理能够学习有效策略和常见失败模式。我们还使用 QO 在 PBEBench 上进行了消融实验，以研究推理轨迹（CoT 与无 CoT）、轨迹数据集大小（100、48、12）的影响，以及在相同轨迹数据集下三次独立归纳轨迹上的求解器算法方差。  

### 2.3 高效的混合推理  

在测试时，求解器提出一个候选集 C_S = S_φ(D) 并选择最佳 p_S = arg max_{p∈C_S} R(p; D)；如果 R(p_S; D) = 1，则以零 LLM 成本接受。否则，我们回退到 LLM 搜索（BoK 或 DF）并返回 arg max_{p∈C_L} R(p; D)，其中 C_L 是 LLM 候选集。这将求解器的构建成本摊销到多次零 token 执行中：S_φ 直接处理大多数任务，而 LLM 搜索保留给更困难的剩余案例。提示构建、求解器接口和代理配置在附录 D.1 (https://arxiv.org/html/2605.05485#A4.SS1) 中提供。我们还将描述的步骤形式化为算法 1 (https://arxiv.org/html/2605.05485#alg1) 和算法 2 (https://arxiv.org/html/2605.05485#alg2)。  

w_t 表示不断演化的代码沙箱，a_t 是一个编码代理动作（例如编辑、执行或文件写入），A_ψ 是动作上的代理策略。ExtractSolver 在工作区中存在有效实现（例如 SOLVER.py）时将其解析为可执行求解器 S_φ_t。q_t 通过验证器在轨迹数据集上测量求解器质量，有效捕获求解器在训练轨迹数据集上的拟合程度。  

**算法 1** 基于编码代理的离线求解器归纳  

1: 轨迹 LLM π_θ, 验证器 R, 任务 \{D_j\}_{j=1}^m, 编码代理 A_ψ, 步骤预算 N  
2: τ_j ← Trace(π_θ, R, D_j) 对于 j=1,...,m  
3: T ← \{(D_j, τ_j)\}_{j=1}^m  
4: 初始化工作区 w_0（空代码库）  
5: 对于 t=0,...,N-1 进行  
6:   a_t ∼ A_ψ(·∣w_t, T, R)  
7:   w_{t+1} ← Apply(w_t, a_t)  
8:   S_φ_t ← ExtractSolver(w_{t+1})  
9:   如果 S_φ_t 有效则  
10:      q_t ← ∑_{j=1}^m R(S_φ_t(D_j); D_j)  
11:   结束如果  
12:   如果 Done(a_t) 则  
13:      break  
14:   结束如果  
15: 结束循环  
16: t^* ← arg max_t q_t  
17: 返回求解器 S_φ ← S_φ_{t^*}  

在实践中，t^* 对应代理在终止时最终承诺的求解器状态；代理在运行过程中在线对 T 进行自我评估以指导优化，而不是通过事后在所有步骤中选择检查点。  

**算法 2** 混合测试时推理  

1: 任务 D, 求解器 S_φ, 验证器 R, LLM 策略 π_θ, 模式 M  
2: C_S ← S_φ(D) ⊳ 可能返回多个候选  
3: p_S ← arg max_{p∈C_S} R(p; D)  
4: 如果 R(p_S; D) = 1 则  
5:   返回 p_S  
6: 结束如果  
7: C_L ← LLMSearch(π_θ, R, D, M)  
8: 返回 arg max_{p∈C_L} R(p; D)  

## 3 实验设置  

我们评估是否可以将 LLM 推理轨迹编译为可复用的符号求解器，从而提高困难组合程序归纳任务上的准确性、效率和性能。实验涵盖两个领域：基于示例编程（PBE）字符串转换和可扩展逻辑推理（SLR）。  

**基准与指标**。  
我们在 PBEBench Naik et al. (2025b (https://arxiv.org/html/2605.05485#bib.bib15))（PBEBench-Lite 和 PBEBench-Hard）以及 SLR-Bench Helff et al. (2025 (https://arxiv.org/html/2605.05485#bib.bib10)) 上进行评估。PBEBench 要求根据输入输出示例合成有序串重写程序级联。