StarOR: 协同树搜索与测试时强化学习的优化建模

# StarOR：协同树搜索与测试时强化学习的优化建模方法  
来源：https://arxiv.org/html/2606.15197  
Yu Ding¹，Shisi Guan²，Ran Hou¹，Wanyuan Wang¹,\*  
¹东南大学计算机科学与工程学院  
²西北农林科技大学  
\*通讯作者。E-mail: [email protected]  

###### 摘要  

优化建模本质上具有层次性，需要精确的符号承诺序列。传统的基于学习的自动优化建模方法通过大规模标注或策划的训练数据来改进建模策略，但适应新问题分布的成本高昂。同时，单次生成在层次建模中仍然脆弱，早期的符号错误可能传播为无效的公式。测试时扩展提供了一种有前景的替代方案，通过额外的实例级计算实现结构化探索；然而，现有的基于搜索的方法通常依赖固定策略，导致重复的 rollout 继承相似的建模偏差，并且对中间决策的信用分配有限。为了解决这些限制，我们提出了 StarOR，一个协同搜索与自适应框架，将 MCTS 与测试时强化学习相结合，用于优化建模。StarOR 将建模过程分解为四个阶段，并在每个非终结点通过 GRPO 更新瞬态 LoRA 适配器。通过使用 MCTS 生成的兄弟节点作为局部比较集，StarOR 将搜索时的探索转化为实例特定的策略细化。此外，无监督的多方面奖励系统为中间公式决策提供细粒度反馈，无需真实标签。在五个优化基准上的实验表明，即使使用 4B 骨干网络，StarOR 也达到了最先进的性能，优于现有方法和前沿大语言模型。代码可在 StarOR (https://github.com/Liwow/StarOR) 获取。  

## 1 引言  

在各类工业中，决策挑战通常用自然语言表述——从复杂的工程设计 (Belegundu and Chandrupatla,2019 (https://arxiv.org/html/2606.15197#bib.bib33)) 到大规模能源管理 (Krishnamurthy et al.,2018 (https://arxiv.org/html/2606.15197#bib.bib35); Singh,2012 (https://arxiv.org/html/2606.15197#bib.bib34))。虽然现代求解器非常稳健，但它们需要精确的数学公式才能运行，这就造成了关键的翻译瓶颈。这个过程需要精确的逻辑承诺序列：分类优化类型，定义集合和参数，并将约束映射为可执行代码。因此，问题描述与其正式公式之间的语义差距仍然是主要障碍，阻止非专家利用先进运筹学工具 (Ramamonjison et al.,2022a (https://arxiv.org/html/2606.15197#bib.bib13),b (https://arxiv.org/html/2606.15197#bib.bib14); Ahmed and Choudhury,2024 (https://arxiv.org/html/2606.15197#bib.bib15))。  

大语言模型 (LLMs) 使自动优化建模变得越来越可行。最近的系统已经能够将自然语言翻译为结构化公式或可执行程序 (Xiao et al.,2024 (https://arxiv.org/html/2606.15197#bib.bib25); Huang et al.,2024a (https://arxiv.org/html/2606.15197#bib.bib1); Jiang et al.,2024 (https://arxiv.org/html/2606.15197#bib.bib2); Chen et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib4); Wu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib16); Wang et al.,2025c (https://arxiv.org/html/2606.15197#bib.bib17))。然而，优化建模对微小错误高度敏感；一个索引或约束方向上的静默错误就可能导致整个模型无效 (Zhang et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib38); Lian et al.,2026 (https://arxiv.org/html/2606.15197#bib.bib37))。这种敏感性源于任务的层次结构：早期对集合和类型的定义支配着所有后续符号，因此变量中的错误不可避免地传播到最终目标。将建模视为平面端到端任务忽略了这些依赖关系，导致结果脆弱且难以修复。  

当前研究试图通过各种方法论范式缓解这些问题，但每种范式都面临结构严谨性与自适应推理之间的根本权衡。具体来说，使用强大前沿模型的基于模型的方法依赖于扩展到巨大参数规模，这在工业环境中往往带来高昂成本和隐私风险。相比之下，基于学习的方法 (Huang et al.,2024a (https://arxiv.org/html/2606.15197#bib.bib1); Jiang et al.,2024 (https://arxiv.org/html/2606.15197#bib.bib2); Lu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib3); Chen et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib4)) 侧重于离线细化策略；然而，它们经常在工业场景的组合复杂性面前挣扎，并且缺乏快速实例特定迭代的机制。最近，基于搜索的方法 (Astorga et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib6); Li et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib5); Liu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib7); Wang et al.,2025a (https://arxiv.org/html/2606.15197#bib.bib18)) 通过在推理时探索多个候选方案来增强可靠性。然而，虽然搜索可以指导遍历或候选选择，但底层生成器仍然是固定的。因此，该过程受到原始提议分布的约束：系统性的建模错误往往在分支间重复出现，额外的 rollout 产生递减的边际收益——这是纯测试时扩展固有的瓶颈。  

参见图注  
Figure 1: (a) 单次优化建模是脆弱的，因为早期静默错误可能使整个程序无效。 (b) 具有固定策略的基于搜索的方法不断重复相同的失败。 (c) StarOR 在当前实例中搜索并调整策略。 (d) 结果实证展示了搜索-自适应范式的有效性。  

如图 1 (https://arxiv.org/html/2606.15197#S1.F1) 所示，现有范式的局限性暗示了一个有前景的方向：将结构化探索与实例特定的在线自适应结合起来。这种权衡尤其适用于运筹学建模，其中高价值的工业应用往往优先考虑公式正确性而非实时生成，并且当能提高可靠性时，额外的测试时计算是可以接受的。然而，实现这种结合面临两个关键挑战。  
首先，它需要一个统一框架，其中离散的搜索步骤可以作为连续策略细化的高质量信号。  
其次，它需要细粒度的评估来解决信用分配问题：由于执行反馈只有在将部分公式完成到代码后才能获得，并且测试时没有真实标签，框架必须推断哪些中间承诺导致了成功或失败。  

为了应对这些挑战，我们提出了 StarOR，一个将优化建模视为跨四个层次的结构化承诺轨迹的框架。通过将多方面奖励系统锚定到中间公式节点，StarOR 使每个搜索步骤既能探索公式空间，又能提供细粒度反馈以将策略适应当前实例。这将优化建模从静态生成转变为动态演化。本文的主要贡献如下：  

- • 协同搜索-自适应框架。我们引入了 StarOR，这是首个将层次化 MCTS 与测试时训练相结合的结构，实现了优化建模过程中的在线策略演化。  
- • 运筹学特定奖励设计。我们提出了一种无监督的多奖励系统，用于在没有真实标签的情况下评估公式质量。  
- • 最先进的性能：StarOR 持续超越先前方法论，在五个优化建模基准上平均准确率达到 65.0%，取得了最先进的结果。  

## 2 相关工作  

##### 基于学习的优化建模方法。  
基于 LLM 的优化建模已经从基准构建 (Ramamonjison et al.,2022a (https://arxiv.org/html/2606.15197#bib.bib13),b (https://arxiv.org/html/2606.15197#bib.bib14); Ahmed and Choudhury,2024 (https://arxiv.org/html/2606.15197#bib.bib15)) 发展到使用合成公式和求解器反馈训练的系统。ORLM 和 OptMATH 构建了大规模合成流程 (Huang et al.,2024a (https://arxiv.org/html/2606.15197#bib.bib1); Lu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib3))，LLMOPT 研究了标准化公式表示 (Jiang et al.,2024 (https://arxiv.org/html/2606.15197#bib.bib2))，SIRL 使用求解器信息奖励进行可执行建模 (Chen et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib4))。最近的系统如 Step-Opt-Instruct 和 ORMind 进一步强调了结构化验证和迭代推理 (Wu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib16); Wang et al.,2025c (https://arxiv.org/html/2606.15197#bib.bib17))。这些方法改进了基础建模先验，但它们仍然主要是离线的：适应新的工业约束通常需要额外的数据、重新训练或更强的专有模型。  

##### 基于搜索的优化建模方法。  
基于搜索的推理通过探索多个公式轨迹来解决单次生成的脆弱性。受“思维树” (Yao et al.,2023 (https://arxiv.org/html/2606.15197#bib.bib21)) 启发，运筹学特定方法使用结构化搜索来改进候选选择：AutoFormulation 将 MCTS 与符号剪枝结合 (Astorga et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib6))，SolverLLM 使用反馈引导的动态扩展 (Li et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib5))，OptiTree 及类似方法通过层次化搜索分解建模 (Liu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib7); Wang et al.,2025a (https://arxiv.org/html/2606.15197#bib.bib18))。然而，这些方法保持策略固定。搜索可以过滤或重新排序候选，但它不会内化探索中遇到的反馈，因此建模偏差可能在分支间重复出现。  

##### 测试时自适应与强化学习。  
测试时训练和强化学习在推理期间更新模型或轻量级适配器，允许当前实例的反馈塑造后续预测 (Akyürek et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib39); Zuo et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib8); Hu et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib45))。相关工作通过工具验证、瞬态策略自适应和在线发现强化了这一思想 (Liao et al.,2026 (https://arxiv.org/html/2606.15197#bib.bib40); Jiao et al.,2026 (https://arxiv.org/html/2606.15197#bib.bib9); Wang et al.,2025b (https://arxiv.org/html/2606.15197#bib.bib42); Yuksekgonul et al.,2026 (https://arxiv.org/html/2606.15197#bib.bib43))。在运筹学中，OR-R1 应用组相对策略优化来在测试时改进建模输出 (Ding et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib11))。StarOR 遵循这一方向，但改变了自适应的粒度：它不是仅从完整输出中学习，而是将可执行、语义和结构奖励附加到中间 MCTS 节点，从而在公式搜索期间实现实例特定的策略细化。  

## 3 方法  

### 3.1 问题形式化  

给定自然语言优化问题 \(x\)，我们的目标是生成可执行、忠实且数学上合理的 Python 代码 \(c\)。遵循 (Jiang et al.,2024 (https://arxiv.org/html/2606.15197#bib.bib2); Li et al.,2025 (https://arxiv.org/html/2606.15197#bib.bib5))，我们将建模过程分解为六个元素——*类型、集合、参数、变量、目标* 和 *约束*——组织为一个四阶段轨迹 \(\tau=(z^{(1)},z^{(2)},z^{(3)},z^{(4)})\)。这些阶段分别代表：(1) 集合和类型，(2) 参数和变量，(3) 目标和约束，(4) 最终可执行代码。任何前缀 \(\tau_{\leq s}\)（\(s<4\)）表示一个 *部分公式*。我们将这个序列形式化为一个马尔可夫决策过程 (MDP)，定义为 \((\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R})\)：  

- • 状态 \(\mathcal{S}\)：状态 \(\sigma_t=(x,\tau_{\leq t})\) 将问题描述 \(x\) 与到目前为止生成的部分公式 \(\tau_{\leq t}\) 配对。  
- • 动作 \(\mathcal{A}\)：动作 \(a_t\) 对应于生成下一阶段的承诺 \(z^{(t+1)}\)。  
- • 转移 \(\mathcal{P}\)：转移是确定性的，定义为 \(\sigma_{t+1}=(x,\tau_{\leq t+1})\)，其中 \(\tau_{\leq t+1}\) 是将 \(a_t\) 附加到 \(\tau_{\leq t}\) 的结果。  
- • 奖励 \(\mathcal{R}\)：任务级奖励定义在 \(\sigma_4\) 处完成的代码上。StarOR 通过完成每个部分轨迹并评估它来估计节点级奖励（见 3.2.1 (https://arxiv.org/html/2606.15197#S3.SS2.SSS1.Px2) 节）。  

参见图注  
Figure 2: StarOR 框架概览。(a) 整体框架：StarOR 在树搜索、代码执行、多方面奖励评估和基于 GRPO 的瞬态 LoRA 自适应之间形成闭环。(b) 搜索与自适应：StarOR 在四个公式阶段上进行搜索，并使用执行反馈来在探索期间自适应局部策略。(c) 多方面奖励：一个无监督奖励为树搜索和策略演化提供节点级反馈。  

### 3.2 StarOR：用于建模的在线优化与树搜索  

我们提出了 StarOR，一个将优化建模转化为蒙特卡洛树搜索 (MCTS) 与在线策略优化协同过程的框架。与传统的静态生成不同，StarOR 将每个建模阶段视为一个搜索-自适应的局部任务。图 2 (https://arxiv.org/html/2606.15197#S3.F2) 展示了 StarOR 用于优化建模流程的概览。在每次迭代 \(t\) 中，MCTS 识别出一个部分公式 \(\tau_{\leq s-1}\) 并处理一个局部子问题：确定在任务 \(x\) 和先前建模决策条件下最优的下一阶段组件 \(z^{(s)}\)。正式地，对于阶段 \(s\)，我们采样一个候选集：  

\[
z_i^{(s)} \sim \pi_{\phi+\Delta\phi}\left(\cdot \mid x, \tau_{\leq s-1}, s\right), \quad i=1,\dots,K,
\]  

其中 \(\phi\) 表示基础策略，\(\Delta\phi\) 表示一个专为当前测试实例维护的瞬态 LoRA 适配器。这种集成促进了自我演化的搜索过程：MCTS 促进建模假设的结构化探索，同时在线优化将执行反馈提炼以细化瞬态适配器 \(\Delta\phi\)。在这个双重目的的循环中，采样的候选同时扩展搜索树并作为测试时自适应的训练批次。因此，该框架识别关键决策点并立即针对特定建模实例锐化局部策略。  

本节的其余部分组织如下：第 3.2.1 (https://arxiv.org/html/2606.15197#S3.SS2.SSS1) 节描述我们的节点级在线