Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers
作者: Soheyl Massoudi, Gabriel Apaza, Milad Habibi, Mark Fuge
分类: cs.LG, cs.AI
发布日期: 2026-05-18
💡 一句话要点
利用强化学习合成可复用求解器，提升LLM在组合优化问题上的效率
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 强化学习 大型语言模型 组合优化 代码生成 可复用求解器
📋 核心要点
- 现有LLM解决组合优化问题时，通常采用推理时搜索，效率较低，且难以泛化到整个问题族。
- 本文提出利用强化学习训练LLM，使其能够合成可复用的求解器，将推理成本转移到模型权重中。
- 实验表明，该方法在协同依赖选择问题上显著优于传统方法，并具有一定的跨领域泛化能力。
📝 摘要（中文）
大型语言模型（LLMs）通常将组合优化问题视为推理时过程，通过采样、搜索或重复提示来单独解决每个实例。本文探讨了是否可以通过强化学习将部分推理成本转移到代码LLM的权重中，从而使模型能够为整个问题族合成可复用的求解器。研究对象是协同依赖选择（SDS），这是一种受约束二次背包的变体，旨在暴露一种特定的失效模式：局部信号和严格的可行性约束使得贪婪启发式算法具有吸引力但不可靠。在相同的支架下，Best-of-64基础模型采样的性能饱和在距离全局虚拟最佳求解器（VBS）约28.7%的差距。代码审计表明，基础模型经常检索模拟退火模板，但错误地实现了Metropolis接受规则。使用可行性门控奖励和轻量级结构支架，对Qwen2.5-Coder-14B-Instruct进行Group Relative Policy Optimization (GRPO)微调。由此产生的策略在99.8%的可行SDS输出中收敛到约束感知的模拟退火模板，实现了与VBS的5.0%差距，并且在生成后执行/搜索成本方面比累积Best-of-64评估便宜91倍。编译一次的检查表明，每个种子的一个最佳冻结求解器在整个SDS测试集中重复使用时仍然具有很强的竞争力，而作业车间调度上的额外领域评估提供了更窄但积极的证据，表明该支架可以转移到SDS之外。负面消融实验揭示了该方法的局限性：标准稳定器会降低性能，软可行性门控会失败，并且结果仍然对奖励归一化和特定于领域的设计选择敏感。
🔬 方法详解
问题定义：论文旨在解决大型语言模型在组合优化问题求解上的效率瓶颈。现有方法，如采样、搜索或重复提示，通常将每个问题实例视为独立事件，缺乏对问题结构的利用，导致推理成本高昂且难以泛化。特别是在具有局部信号和严格可行性约束的问题中，贪婪启发式算法容易陷入局部最优，而LLM难以正确实现复杂的优化算法。
核心思路：论文的核心思路是利用强化学习训练LLM，使其能够学习并合成可复用的求解器。通过将部分推理成本转移到模型的权重中，使得模型能够针对整个问题族生成高效的优化策略。这种方法旨在克服传统推理时搜索的局限性，提高求解效率和泛化能力。
技术框架：整体框架包括以下几个主要步骤：1）选择一个合适的代码LLM作为基础模型；2）构建一个强化学习环境，包括问题生成器、奖励函数和状态表示；3）使用Group Relative Policy Optimization (GRPO)算法对LLM进行微调，使其能够生成满足约束条件且优化目标函数的代码；4）对训练好的模型进行评估，包括在相同问题族上的泛化能力和在不同问题上的迁移能力。
关键创新：最重要的技术创新点在于利用强化学习来引导LLM学习并合成可复用的求解器。与传统的推理时搜索方法相比，该方法能够更好地利用问题结构，提高求解效率和泛化能力。此外，使用可行性门控奖励函数能够有效地引导模型生成满足约束条件的代码。
关键设计：关键设计包括：1）使用Qwen2.5-Coder-14B-Instruct作为基础模型；2）设计一个可行性门控奖励函数，只有当生成的代码满足约束条件时才给予奖励；3）使用Group Relative Policy Optimization (GRPO)算法进行微调，该算法能够有效地处理强化学习中的探索-利用平衡问题；4）使用轻量级结构支架，以减少对领域知识的依赖。
🖼️ 关键图片
📊 实验亮点
实验结果表明，使用强化学习微调后的LLM在协同依赖选择（SDS）问题上取得了显著的性能提升，与全局虚拟最佳求解器（VBS）的差距从28.7%降低到5.0%。此外，生成后执行/搜索成本降低了91倍。编译一次的检查表明，每个种子的一个最佳冻结求解器在整个SDS测试集中重复使用时仍然具有很强的竞争力。在作业车间调度问题上的评估也显示出一定的迁移能力。
🎯 应用场景
该研究成果可应用于各种组合优化问题，如资源调度、路径规划、电路设计等。通过训练LLM合成可复用的求解器，可以显著提高这些问题的求解效率，降低计算成本，并为自动化问题求解提供新的思路。未来，该方法有望扩展到更广泛的领域，例如机器人控制、金融建模等。
📄 摘要（原文）
Large language models (LLMs) typically approach combinatorial optimization as an inference-time procedure, solving each instance separately through sampling, search, or repeated prompting. We ask whether reinforcement learning can instead shift part of this reasoning cost into the weights of a code LLM, so that the model synthesizes a reusable solver for an entire problem family. We study this question on Synergistic Dependency Selection (SDS), a controlled variant of constrained Quadratic Knapsack designed to expose a specific failure mode: local signals and strict feasibility constraints make greedy heuristics attractive but unreliable. Under identical scaffolding, Best-of-64 base-model sampling saturates at an approximately 28.7% gap to the global Virtual Best Solver (VBS); code audits show that the base model often retrieves Simulated Annealing templates but misimplements the Metropolis acceptance rule. We fine-tune Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization (GRPO) using a feasibility-gated reward and light structural scaffolding. The resulting policy converges to a constraint-aware Simulated Annealing template in 99.8% of feasible SDS outputs, achieves a 5.0% gap to that VBS, and is 91 times cheaper in post-generation execution/search cost than cumulative Best-of-64 evaluation. A compile-once check shows that one best frozen solver per seed remains highly competitive when reused unchanged across the SDS test set, while an additional-domain evaluation on Job Shop Scheduling provides narrower but positive evidence that the scaffold transfers beyond SDS. Negative ablations reveal the limits of this recipe: standard stabilizers degrade performance, a soft feasibility gate fails, and results remain sensitive to reward normalization and domain-specific design choices.