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

Publication Date: 12/7/2025

Event: The Thirty-ninth Annual Conference on Neural Information Processing Systems (NeurIPS 2025)

Reference: pp. 1-31, 2025

Authors: Dong Li, Baylor University; Xujiang Zhao, NEC Laboratories America, Inc.; Linlin Yu, University of Texas at Dallas; Yanchi Liu, NEC Laboratories America, Inc.; Wei Cheng, NEC Laboratories America, Inc.; Zhengzhang Chen, NEC Laboratories America, Inc.; Feng Chen, University of Texas at Dallas; Zhong Chen, Southern Illinois University; Chen Zhao, Baylor University; Haifeng Chen, NEC Laboratories America, Inc.

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.

Publication Link: