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

• URL: http://arxiv.org/abs/2606.05464v1
• Date: Wed, 03 Jun 2026 21:43:38 GMT
• Title: Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces
• Abstract summary: OPT* is a family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning.<n>Each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels.<n>We show that training on OPT* improves step-by-step optimization-like reasoning.
• Score: 63.82675722580452
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• APEX-Searcher: Augmenting LLMs' Search Capabilities through Agentic Planning and Execution [10.643859464982071]
  APEX-Searcher is a novel Agentic Planning and Execution framework to augment large language models (LLMs) search capabilities.<n>It first employs RL with decomposition-specific rewards to optimize strategic planning.<n>It then applies supervised fine-tuning on high-quality multi-hop trajectories to equip the model with robust iterative sub-task execution capabilities.
  arXiv  Detail & Related papers  (2026-03-14T09:17:12Z)
• OPT-BENCH: Evaluating LLM Agent on Large-Scale Search Spaces Optimization Problems [19.586884180343038]
  OPT-BENCH is a benchmark designed to evaluate Large Language Models (LLMs) on large-scale search space optimization problems.<n> OPT-Agent emulates human reasoning when tackling complex problems by generating, validating, and iteratively improving solutions through historical feedback.
  arXiv  Detail & Related papers  (2025-06-12T14:46:41Z)
• Iterative Self-Incentivization Empowers Large Language Models as Agentic Searchers [74.17516978246152]
  Large language models (LLMs) have been widely integrated into information retrieval to advance traditional techniques.<n>We propose EXSEARCH, an agentic search framework, where the LLM learns to retrieve useful information as the reasoning unfolds.<n>Experiments on four knowledge-intensive benchmarks show that EXSEARCH substantially outperforms baselines.
  arXiv  Detail & Related papers  (2025-05-26T15:27:55Z)
• StepSearch: Igniting LLMs Search Ability via Step-Wise Proximal Policy Optimization [14.931231544839687]
  StepSearch is a framework for search LLMs that trained with step-wise proximal policy optimization method.<n>It consists of richer and more detailed intermediate search rewards and token-level process supervision based on information gain and redundancy penalties.<n>On standard multi-hop QA benchmarks, it significantly outperforms global-reward baselines, achieving 11.2% and 4.2% absolute improvements for 3B and 7B models.
  arXiv  Detail & Related papers  (2025-05-21T05:01:31Z)
• Offline Reinforcement Learning for LLM Multi-Step Reasoning [15.687002884103537]
  OREO (Offline Reasoning Optimization) is an offline reinforcement learning method for enhancing multi-step reasoning.<n>It reduces the need to collect pairwise data and enables better credit assignment.<n>It surpasses existing offline learning methods on multi-step reasoning benchmarks.
  arXiv  Detail & Related papers  (2024-12-20T18:49:45Z)
• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  This paper approaches the problem of $textitautoformulation$: the automated creation of solver-ready optimization models from natural language problem descriptions.<n>We identify three core challenges of autoformulation: $textit(1)$ the vast, problem-dependent hypothesis space, and $textit(2)$ efficient and diverse exploration of this space under uncertainty.<n>We present a novel method leveraging $textitLarge Language Models$ with $textitMonte-Carlo Tree Search$, exploiting the hierarchical nature of optimization modeling to generate and systematically explore possible formulations
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• Efficient Budget Allocation for Large-Scale LLM-Enabled Virtual Screening [0.9558392439655016]
  We consider an LLM-as-human-evaluator approach for conducting screening virtually, thereby reducing the cost burden.<n>We propose using a top-$m$ greedy evaluation mechanism, and design the explore-first top-$m$ greedy (EFG-$m$) algorithm.<n>Surprisingly, we uncover a bonus ranking effect, where the algorithm naturally induces an indifference-based ranking within the selected subset.
  arXiv  Detail & Related papers  (2024-08-18T16:44:41Z)
• Query-Dependent Prompt Evaluation and Optimization with Offline Inverse RL [62.824464372594576]
  We aim to enhance arithmetic reasoning ability of Large Language Models (LLMs) through zero-shot prompt optimization. We identify a previously overlooked objective of query dependency in such optimization. We introduce Prompt-OIRL, which harnesses offline inverse reinforcement learning to draw insights from offline prompting demonstration data.
  arXiv  Detail & Related papers  (2023-09-13T01:12:52Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)
• Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization [42.92248233465095]
  We propose a simple but effective method, called symmetric replay training (SRT), which can be easily integrated into various Deep reinforcement learning (DRL) methods. Our method leverages high-reward samples to encourage exploration of symmetric regions without additional online interactions - free. Experimental results demonstrate the consistent improvement of our method in sample efficiency across diverse DRL methods applied to real-world tasks.
  arXiv  Detail & Related papers  (2023-06-02T05:34:01Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX. textttMEX integrates estimation and planning components while balancing exploration exploitation automatically. It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
  arXiv  Detail & Related papers  (2023-05-29T17:25:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.