Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces OPT★, a scalable family of auto-verifiable optimization tasks, and trains LLMs for step-by-step optimization-like reasoning via offline search-based RL (νMCTS/νBeamSearch distillation) and solver-guided online RL (νPO with rank-shaped rewards).

Problem

LLMs are brittle on constrained step-by-step decision making where many feasible solutions exist and the goal is a high-value one; verifiable-reward training works for math/code but scaling to optimization-like reasoning needs cheap verification and step-level signal.

Approach

Treat constrained optimization tasks as scalable verifiable environments with a feasibility checker and outcome evaluator, adding plug-and-play search components (checker pruning and duplicate-action merging) for offline RL and a solver-as-value-oracle rank-shaped reward for online policy optimization, plus an information-theoretic bound linking search-space size to required information per budget

Key results

• On Role Assignment with Qwen2.5-3B-Instruct, the trained model reaches 44.5% pass@1 at alpha1 versus 32.5% for the base model, and 31.1% vs 17.8% at alpha4.
• In offline search without training, nuMCTS with checker and deduplication reaches b_eff 15.04 and pass@16 88.9%, while the solver reference reaches pass@16 18.7% on the same metric.
• On QAP, nuMCTS achieves b_eff 24.27 and pass@16 85.1% versus a solver reference with b_eff 727.9 and pass@16 13.3%.

Surprising findings

• Training on MATH-500 or MBPP does not help optimization performance, roughly matching the base model.
• The solver reference, although faster when available, assigns little probability mass to epsilon-good natural-language trajectories (pass@16 below 20%).

Limitations

• Experiments use small instruction-tuned models (3B and 7B) and synthetic optimization tasks; only Qwen2.5-7B could bootstrap RL on polyomino.
• Offline RL experiments assume a solver can compute the optimum for analysis, and theory assumes finite effective solution spaces with uniform optima.

Experimental setup

Datasets: OPT★ generated optimization tasks (Role Assignment, MaxSAT, Knapsack, QAP, Scheduling, Polyomino) MATH-500 MBPP AMC'23 AIME'24 AIME'25

Benchmarks: OPT★ Role Assignment OPT★ MaxSAT (OOD) OPT★ Scheduling (OOD) OPT★ Knapsack OPT★ Polyomino MATH-500 MBPP AMC'23 AIME'24 AIME'25

Metrics: pass@1 pass@16 pass@8 good-terminal mass p_g effective branching factor b_eff k_90 terminal feasibility exact optimality

Baselines: MATH-500 domain training MBPP code domain training base model solver reference (DFS) sequential outcome-based search

Builds on: GRPO GSPO PPO verl MCTS

Closest papers by meaning

• SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search (NeurIPS 2025 · similarity 0.90)
• GLoRe: When, Where, and How to Improve LLM Reasoning via Global and Local Refinements (ICML 2024 · similarity 0.89)
• Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.89)
• Rectifying LLM Thought from Lens of Optimization (ICLR 2026 · similarity 0.89)
• Optimizing Test-Time Compute via Meta Reinforcement Finetuning (ICML 2025 · similarity 0.89)
• In-Token Rationality Optimization: Towards Accurate and Concise LLM Reasoning via Self-Feedback (AAAI 2026 · similarity 0.89)