mlsanityData to 7 Oct 2026

Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces

arXiv 2606.05464 ↗First posted 3 Jun 2026cs.AIcited by 0

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 29 of its 54 references that are in the map. First posted on arXiv 3 Jun 2026.

Builds on

29 of 54 references.

Closest ancestors · 8

Same direction, newest first

  1. 2025InternBootcamp: Boosting LLM Reasoning with Verifiable Task Scaling12 Aug
  2. 2025LogicPuzzleRL: Cultivating Robust Mathematical Reasoning in LLMs via Reinforcement Learning5 Jun
  3. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scale18 Mar
  4. 2025Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Models24 Feb
  5. 2024ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search6 Jun
  6. 2024Improve Mathematical Reasoning in Language Models by Automated Process Supervision5 Jun
  7. 2024AlphaMath Almost Zero: Process Supervision without Process6 May
  8. 2017Proximal Policy Optimization Algorithms20 Jul

Other references · 21

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  2. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  3. 2024Qwen2.5 Technical Reportcited by 4,713
  4. 2021Program Synthesis with Large Language Modelscited by 3,509
  5. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  6. 2023Teaching Large Language Models to Self-Debugcited by 963
  7. 2021Measuring Coding Challenge Competence With APPScited by 879
  8. 2025Group Sequence Policy Optimizationcited by 788
  9. 2023Scaling Relationship on Learning Mathematical Reasoning with Large Language Modelscited by 417
  10. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 331
  11. 2023Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Modelscited by 325
  12. 2025rStar-Math: Small LLMs Can Master Math Reasoning with Self-Evolved Deep Thinkingcited by 308
9 more
  1. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Trainingcited by 291
  2. 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learningcited by 238
  3. 2024Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8Bcited by 156
  4. 2025REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewardscited by 121
  5. 2025Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzlescited by 53
  6. 2025SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulascited by 30
  7. 2025AutoLogi: Automated Generation of Logic Puzzles for Evaluating Reasoning Abilities of Large Language Modelscited by 29
  8. 2025Bridging Offline and Online Reinforcement Learning for LLMscited by 25
  9. 2025How to Get Your LLM to Generate Challenging Problems for Evaluationcited by 11

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026OPT-Engine: Benchmarking the Limits of LLMs in Optimization Modeling via Complexity Scaling
  2. 2025SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search
  3. 2025OptiMind: Teaching LLMs to Think Like Optimization Experts
  4. 2026MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources
  5. 2025Genius: A Generalizable and Purely Unsupervised Self-Training Framework For Advanced Reasoning
  6. 2026Execution-Verified Reinforcement Learning for Optimization Modeling
  7. 2026Grad2Reward: From Sparse Judgment to Dense Rewards for Improving Open-Ended LLM Reasoning
  8. 2025Unearthing Gems from Stones: Policy Optimization with Negative Sample Augmentation for LLM Reasoning