让大模型在不断扩大的搜索空间中逐步优化决策，提升复杂任务求解能力。
Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces
- 设计可扩展的优化类任务框架OPT*，支持自动评估与反馈。
- 训练后模型在复杂搜索空间中表现显著提升，验证了渐进式推理有效性。
- 适合研究大模型决策优化、强化学习与自动规划的学者参考。
可验证奖励训练已提升数学与编程推理能力，但这些领域仅涵盖部分逐步决策场景。许多真实任务需在众多有效方案中寻找高价值可行解。我们提出OPT*，一个可扩展的优化类任务族，用于训练和评估大模型在复杂度轴上的逐步优化式推理：每项任务提供可行性检查器与评估器，复杂度参数扩展搜索空间，无需新增人工标注。该设定推动研究两种范式：(i) 求解器引导的在线策略优化，利用求解器作为部分状态的价值查询，通过排名奖励重塑强化更优下一步；(ii) 当求解器不可用时采用基于搜索的离线强化学习。理论上，我们建立成功解决大规模搜索空间与单位搜索预算下推理者提取信息量之间的关联。实验上，我们剖析了提升搜索效率的关键要素，并证明在OPT*上训练能显著改善大模型的逐步优化式推理能力。
原文摘要 · Abstract (English)
Verifiable reward training has improved mathematical and coding reasoning, but these domains capture only part of step-by-step decision making. Many real-world tasks require finding a high-value feasible plan among many valid alternatives. We introduce OPT*, a scalable family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning along a complexity axis: each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels. This motivates studying these tasks in two regimes: (i) solver-guided online policy optimization, which uses a solver as a value oracle for partial states and applies rank-based reward shaping to reinforce better next steps, and (ii) search-based offline RL when such solvers are unavailable. Theoretically, we relate success in large search spaces to the information a reasoner extracts per unit of search budget. Empirically, we ablate the ingredients that make search efficient on OPT* and show that training on OPT* improves step-by-step optimization-like reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。