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

SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search

NeurIPS 2025 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 1 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.

Proposes SolverLLM, a training-free MCTS framework that generates six-element optimization formulations with an LLM and converts them to Pyomo code, adding dynamic expansion, prompt backpropagation, and uncertainty backpropagation.

Problem

Translating natural-language optimization problems into solver-ready formulations and code generalizes poorly under prompt-based methods and requires costly fine-tuning for learning-based methods.

Approach

Treat optimization formulation as a tree search over a six-element schema (Type, Sets, Parameters, Variables, Objective, Constraints) with LLM-driven dynamic expansion at any node, feedback from solver execution and LLM reasoning propagated backward as prompts, and reward uncertainty (semantic entropy) used to down-weight noisy rewards.

Key results

• SolverLLM with GPT-4o reaches 97.0% SA on NL4Opt, 87.0% on NLP4LP, and 77.8% on ComplexOR, outperforming OptiMUS (78.8%, 72.0%, 66.7%) on those datasets where OptiMUS is shown.
• On MamoComplex and IndustryOR, SolverLLM achieves 76.0% and 56.0% SA, exceeding LLMOPT by 8 and 10 points as reported in the paper.
• Ablation: removing prompt backpropagation drops MamoComplex SA from 76.0% to 69.0% and IndustryOR from 56.0% to 46.0%.

Measured effects reported in the paper

Surprising findings

• With GPT-4o-mini as the backend, SolverLLM still reaches 94.0% SA on MamoEasy and 94.0% on NL4Opt, showing limited degradation from a smaller model.
• The paper reports SolverLLM underperforms LLMOPT on MamoEasy (96.0% vs 97.0%), so it does not dominate all datasets.

Limitations

• Test-time search makes inference slower and more expensive than learning-based methods.
• LLM-based reward (objective score) is subjective and may be noisy.
• Evaluated only on six benchmarks with a single closed-source backbone family (GPT-4o).

Experimental setup

Datasets: NL4Opt MamoEasy MamoComplex NLP4LP ComplexOR IndustryOR

Benchmarks: NL4Opt MamoEasy MamoComplex NLP4LP ComplexOR IndustryOR

Metrics: solving accuracy execution rate average generation time

Baselines: GPT-4 GPT-4o Reflexion Chain-of-Experts OptiMUS AutoFormulation ORLM LLMOPT

Builds on: Monte Carlo Tree Search UCT Chain-of-Experts LLMOPT semantic entropy AutoFormulation

Closest papers by meaning

• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces (NeurIPS 2026 · similarity 0.90)
• Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.90)
• Provable Test-Time Scaling for Beam Search in LLM Reasoning (NeurIPS 2026 · similarity 0.89)
• LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch (ICLR 2025 · similarity 0.89)
• REASONING COMPILER: LLM-Guided Optimizations for Efficient Model Serving (NeurIPS 2025 · similarity 0.88)
• SCALE: Selective Resource Allocation for Overcoming Performance Bottlenecks in Mathematical Test-time Scaling (AAAI 2026 · similarity 0.88)