Uncertainty-Aware Test-Time Search for Optimization Problem Solving

Publication Date: 7/7/2026

Event: The 64th Annual Meeting of the Association for Computational Linguistics (ACL 2026)

Reference: pp. 42658–42669

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

Abstract: Automatically solving optimization problems from natural language descriptions with both efficiency and reliability is highly desirable but remains challenging. Language model hallucinations and the limited availability of labeled datasets often result in misaligned formulations, code errors, and feasibility failures. We pro-pose UMCTS, an Uncertainty-aware Monte Carlo Tree Search framework that combines the language understanding capability of large language models with the reliability of well-established solvers. UMCTS structures the solution process into four stages: global instruction, assumptions, mathematical formulation, and solver code generation. It employs Monte Carlo Tree Search with semantic-equivalence pruning, prior-guided exploration, and solver-based feasibility checks. An LLM judge provides numerical reward signals, qualtative error information, and uncertainty estimates. These signals are backpropagated to guide the search and flag unreliable out-puts. Across six public benchmarks, UMCTS achieves state-of-the-art solution accuracy and improves efficiency by reducing token usage.

Publication Link: https://aclanthology.org/2026.acl-long.1975/