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

AI summary

Overview

• Research area: Large language models applied to mathematical optimization — specifically automatic problem formulation (natural language to solver-ready code), combining test-time scaling with Monte Carlo Tree Search.
• Technical level: Advanced (assumes familiarity with MCTS, LLM inference, and optimization solvers such as Gurobi or Pyomo).
• Scope: A training-free, inference-time framework for turning natural-language optimization problems into mathematical formulations and executable solver code, evaluated on six benchmark datasets.

What This Paper Is About

Solving an optimization problem normally has three stages: formulating the natural-language description into variables, constraints, and an objective; translating that model into code; and executing it with a solver. The formulation stage demands both domain and mathematical-programming expertise, which limits automation. Existing LLM approaches either rely on carefully engineered prompts and agent roles (which generalize poorly) or require costly supervised fine-tuning on curated problem–solution pairs. SolverLLM's goal is to solve diverse optimization problems at inference time, with no task-specific training, by searching over possible formulations with an LLM-guided MCTS procedure.

Key Contributions

1. SolverLLM, a training-free framework that uses a test-time scaling strategy — spending extra computation during inference — to solve diverse optimization problems without fine-tuning.
2. Three modifications to classical MCTS: (i) dynamic expansion, letting the LLM incrementally add or refine variables and constraints, including at non-leaf nodes; (ii) prompt backpropagation, which feeds layer-specific reasoning signals and solver feedback back through the tree to steer subsequent prompt edits; and (iii) uncertainty backpropagation, which incorporates reward variance to down-weight unreliable evaluations and improve search efficiency.
3. A six-element formulation schema — Type, Sets, Parameters, Variables, Objective, and Constraints — extending the five-element abstraction used in prior work (sets, parameters, objective, variables, constraints) by adding a high-level Type element that classifies the problem category (for example, linear programming or integer programming) and supplies global guidance.
4. Extensive experiments on six standard benchmark datasets showing SolverLLM outperforms prompt-based and learning-based baselines, with a reported 10% improvement over the state-of-the-art.

Main Findings

• Outperformance over prompt-based methods (SA): SolverLLM reached 97.0% on NL4Opt, 87.0% on NLP4LP, and 77.8% on ComplexOR, versus OptiMUS at 78.8%, 72.0%, and 66.7%; Chain-of-Experts at 64.2%, 53.1%, and 38.1%; Reflexion at 53.0%, 46.3%, and 19.1%; GPT-4 directly at 47.3%, 35.8%, and 9.5%; and GPT-4o directly at 81.0%, 32.4%, and 27.3%. The paper reports improvements exceeding 10% in all datasets.
• Outperformance over learning-based methods (SA): SolverLLM scored 96.0% on MamoEasy, 97.0% on NL4Opt, 76.0% on MamoComplex, and 56.0% on IndustryOR, compared with LLMOPT at 97.0%, 93.0%, 68.0%, and 46.0%. On MamoComplex and IndustryOR it surpasses LLMOPT by 8 and 10 percentage points respectively. ORLM variants (Mistral, Deepseek, LLaMa3) scored 81.4%–82.3% on MamoEasy, 84.4%–86.5% on NL4Opt, 32.0%–37.9% on MamoComplex, and 27.0%–38.0% on IndustryOR.
• Comparison with another test-time scaling method: Against AutoFormulation (an MCTS-based method using a four-element formulation), SolverLLM achieved higher SA on both simple and complex datasets, and higher ER — with almost all code executing successfully, attributed to error backpropagation during code generation.
• Dynamic expansion (prompt backpropagation) matters most on hard problems: Removing PB dropped SA to 90.0 (MamoEasy), 93.0 (NL4Opt), 81.0 (NLP4LP), 66.7 (ComplexOR), 69.0 (MamoComplex), and 46.0 (IndustryOR), and lowered ER on the harder sets (94.4% on both ComplexOR and NLP4LP variants). In a TSP case study, the w/o PB variant failed because it missed constraints on the sequence variable range, causing subtour elimination to fail.
• Uncertainty backpropagation improves efficiency: SolverLLM and w/o UB produced similar SA and ER, but SolverLLM was notably faster on complex datasets — for example, AGT of 4.34 minutes (w/o UB) versus 3.85 minutes on MamoComplex, and 3.68 versus 3.28 on IndustryOR. UB prunes low-quality nodes earlier, simplifying the search tree.
• The Type element helps, particularly on hard data: Removing TE lowered SA to 92.0 (MamoEasy), 96.0 (NL4Opt), 82.0 (NLP4LP), 72.2 (ComplexOR), 59.0 (MamoComplex), and 48.0 (IndustryOR) versus 96.0, 97.0, 87.0, 77.8, 76.0, and 56.0 for full SolverLLM. In a simple integer programming case study, the w/o TE variant modeled a variable as floating-point and produced an incorrect result. The authors also note TE is particularly effective for graph-related problems.
• Token efficiency: On MamoComplex at 10 search iterations, SolverLLM used 32,790 tokens for 69.0% SA versus AutoFormulation's 35,911 tokens for 34.0% SA; at 50 iterations, 66,312 tokens for 78.0% SA versus 70,245 tokens for 40.0% SA. SolverLLM had higher accuracy at lower token cost at every budget from 10 to 50 iterations.
• Execution Rate: Full SolverLLM reached 100.0% ER on MamoEasy, NL4Opt, NLP4LP, and ComplexOR, 99.0% on MamoComplex, and 98.0% on IndustryOR.

Methodology in Plain English

Instead of asking an LLM to output an answer directly, SolverLLM treats building the mathematical formulation as a search problem and explores many candidate formulations.

• Breaking the problem into six parts: Every formulation is built from six elements — Type, Sets, Parameters, Variables, Objective, and Constraints. Each node in the search tree holds a partial formulation, and a full path from root defines a complete model. The Type element acts as upfront global guidance, telling the model what kind of problem it is before the details are filled in.
• Searching with MCTS: The tree is built through selection, dynamic expansion, simulation, and backpropagation. Selection uses the standard UCT rule, balancing high-reward nodes against less-visited ones with an exploration constant c. Each node tracks a visit count and an average reward.
• Dynamic expansion: Because valid optimization formulations are open-ended rather than a fixed action set, the LLM proposes new child nodes tailored to the current partial formulation. Expansion is allowed on non-leaf nodes, not just leaves, so earlier decisions (such as variables or constraints) can be revisited and refined as feedback arrives.
• Simulation and reward: Each complete formulation is translated into code and run through a numerical solver. The reward is a weighted sum of a feasibility indicator, an LLM-judged objective score, and a penalty for solver or code errors. The LLM also acts as a lightweight "judger" of solution quality, which helps when no ground truth or reference objective is available.
• Reasoning signals: Evaluation also produces a per-layer triplet — a trigger indicating whether a node is activated, an explanation of whether the node is appropriate, and layer-level prompt guidance for revision. These signals are stored in a per-layer knowledge base and reused in later prompts.
• Prompt backpropagation: Reasoning signals are propagated back along the path to the root. If the trigger is present and the local uncertainty (computed by predictive entropy over the explanation text) exceeds a threshold, the node is activated for further expansion and its guidance is added to the layer's knowledge base.
• Uncertainty backpropagation: Because LLM reward judgments are noisy, the objective score is sampled repeatedly to estimate semantic uncertainty. The reward update uses an uncertainty-weighted average, with the trade-off factor set to the exponential of the negative global uncertainty, so confident evaluations propagate strongly and noisy ones barely move the tree statistics.

Why This Matters

• Research impact: The paper argues that a training-free, inference-time search can match or beat methods that require supervised data and fine-tuning, positioning test-time scaling as a viable alternative for structured reasoning domains. It also shows that MCTS can be extended beyond scalar rewards by propagating natural-language feedback and uncertainty estimates.
• Real-world applications:
  • Operations research and supply-chain planning, where natural-language requirements must become solvable optimization models.
  • Energy management scheduling and engineering design decisions, both listed among the domains where optimization grounds decision-making.
  • Economics and healthcare planning, also cited as application areas for optimization-based decisions.
  • Any workflow that currently requires an expert to hand-write a model and solver code from a written problem description.
• Industry relevance: The approach works with existing solvers such as Gurobi or Pyomo and needs no labeled training data, which lowers the barrier to automating formulation. The paper's token-budget analysis directly addresses deployment cost — SolverLLM achieved higher accuracy with fewer tokens than the compared test-time scaling method at every budget tested. Its stated limitation is inference time: the test-time search makes it slower than learning-based methods, and LLM-based reward estimation remains noisy and subjective.

Future Directions

• Extending the framework to more complex optimization settings beyond the six benchmarks studied.
• Combining test-time search with other inference paradigms in hybrid setups, which the conclusion names as an open avenue.
• Further reducing inference cost, since the authors identify computational inefficiency and longer inference time relative to learning-based methods as a limitation.
• Improving the reliability of LLM-based reward estimation, which the paper flags as noisy and subjective and currently handles only through uncertainty-aware propagation.
• Investigating the observation that the Type element is especially effective for graph-related problems, which the authors examine in an appendix case study.

Target Audience

Researchers in machine learning and operations research who work on LLM reasoning, test-time scaling, or automated optimization modeling; practitioners who want to turn natural-language business problems into solver-ready models without training a model; and readers interested in how classical search algorithms like MCTS can be augmented with language-model feedback and uncertainty estimates.

Authors’ abstract

Large Language Models (LLMs) offer promising capabilities for tackling complex reasoning tasks, including optimization problems. However, existing methods either rely on prompt engineering, which leads to poor generalization across problem types, or require costly supervised training. We introduce SolverLLM, a training-free framework that leverages test-time scaling to solve diverse optimization problems. Rather than solving directly, SolverLLM generates mathematical formulations and translates them into solver-ready code, guided by a novel Monte Carlo Tree Search (MCTS) strategy. To enhance the search process, we modify classical MCTS with (1) dynamic expansion for adaptive formulation generation, (2) prompt backpropagation to guide exploration via outcome-driven feedback, and (3) uncertainty backpropagation to incorporate reward reliability into decision-making. Experiments on six standard benchmark datasets demonstrate that SolverLLM outperforms both prompt-based and learning-based baselines, achieving strong generalization without additional training.