Elamur Research⌕
☰
home / papers / 2026 / Uncertainty-Aware Test-Time Search for Optimization Problem Solving

Uncertainty-Aware Test-Time Search for Optimization Problem Solving

Paper · 2026 · Linlin Yu, Xujiang Zhao, Dong Li et al.

Summary

The paper addresses the automatic translation of natural-language optimization problems into solver-ready models and code. LLMs alone often produce mismatched formulations, buggy code or infeasible programs, and fine-tuning is limited by scarce, noisy labeled data. The authors propose UMCTS, a training-free test-time search method built on Monte Carlo Tree Search. Each tree level corresponds to one of four stages: a problem-type-specific global instruction, explicit assumptions, the mathematical formulation, and Gurobi-style solver code. The search prunes semantically equivalent branches, uses prior-guided exploration and checks feasibility with the solver. An LLM judge returns a numeric reward, a description of errors and an epistemic uncertainty estimate, and all three are propagated back through the tree. This favours confident branches and helps reject unreliable outputs. Using GPT-4o-mini, UMCTS reports the best solution accuracy on six public benchmarks while consuming fewer tokens than the search-based Autoformulation. Most baseline scores, however, are taken from prior papers that used different LLMs. The work shows that cheap models combined with structured, uncertainty-guided search can rival fine-tuned systems.

Key points

  • On MamoComplex, UMCTS reaches 78% solution accuracy, compared with 62% for the strongest baseline, LLMOPT.

  • In the ablation with GPT-4o-mini, UMCTS is compared with Direct Ask and Sequential Ask:

    DatasetUMCTSDirect AskSequential Ask
    ComplexOR837867
    MamoComplex784836
    IndustryOR563935

  • Efficiency on MamoComplex: UMCTS uses about 64.4k tokens and costs about $0.019 per instance. Autoformulation with GPT-4 uses about 80.2k tokens and costs $0.320 per instance.

  • Turning off uncertainty backpropagation (plain MCTS) drops accuracy to 70%, though it uses fewer tokens (about 54.2k). The uncertainty signal also helps avoid "lazy" feasible-but-suboptimal solutions.

  • The authors report that at least 26% of IndustryOR problems are ill-defined or incomplete, and they release corrected benchmark versions on GitHub.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓The University of Texas at DallasRichardson · United States63 works · 5,710 citations🎓Baylor UniversityWaco · United States2 works · 450 citations🏢NEC (United States)Irving · United States10 works · 658 citations

Also on the byline: Augusta University.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,685 works

Cite

Cite as Linlin Yu, Xujiang Zhao, Dong Li, Yanchi Liu, Wei Cheng, Zhengzhang Chen, Chen Zhao, Feng Chen and Haifeng Chen. 2026. Uncertainty-Aware Test-Time Search for Optimization Problem Solving. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.1975

@inproceedings{yu2026uncertainty,
  title = {{Uncertainty-Aware Test-Time Search for Optimization Problem Solving}},
  author = {Linlin Yu, Xujiang Zhao, Dong Li, Yanchi Liu, Wei Cheng, Zhengzhang Chen, Chen Zhao, Feng Chen and Haifeng Chen},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.1975},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1975}
}

References

30 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Ali AhmadiTeshnizi, Wenzhi Gao, and Madeleine Udell. 2023. Optimus: Optimization modeling using mip solvers and large language models. arXiv preprint arXiv:2310.06116. — [arXiv:2310.06116](https://arxiv.org/abs/2310.06116) find
  2. Nicolás Astorga, Tennison Liu, Yuanzhang Xiao, and Mihaela van der Schaar. 2024. Autoformulation of mathematical optimization models using llms. arXiv preprint arXiv:2411.01679. — [arXiv:2411.01679](https://arxiv.org/abs/2411.01679) find
  3. Ashok D Belegundu and Tirupathi R Chandrupatla. 2019. Optimization concepts and applications in engineering. Cambridge University Press. find
  4. Yi Chen, Aimin Zhou, and Swagatam Das. 2021. Utilizing dependence among variables in evolutionary algorithms for mixed-integer programming: A case study on multi-objective constrained portfolio optimization. Swarm and Evolutionary Computation, 66:100928. find
  5. Erwin J Delgado, Xavier Cabezas, Carlos Martin-Barreiro, Víctor Leiva, and Fernando Rojas. 2022. An equity-based optimization model to solve the location problem for healthcare centers applied to hospital beds and covid-19 vaccination. Mathematics, 10(11):1825. find
  6. Sumanth Doddapaneni, Mohammed Safi Ur Rahman Khan, Sshubam Verma, and Mitesh M Khapra. 2024. Finding blind spots in evaluator llms with interpretable checklists. arXiv preprint arXiv:2406.13439. find
  7. Gurobi Optimization. 2024. State of mathematical optimization report. https://www.gurobi.com/resou rces/report-state-of-mathematical-optimiz ation-2024/. Accessed: Sep. 2025. ↗
  8. Xuhan Huang, Qingning Shen, Yan Hu, Anningzhe Gao, and Benyou Wang. 2024. Mamo: a mathematical modeling benchmark with solvers. arXiv preprint arXiv:2405.13144. find
  9. Xuhan Huang, Qingning Shen, Yan Hu, Anningzhe Gao, and Benyou Wang. 2025. Llms for mathematical modeling: Towards bridging the gap between natural and mathematical languages. In Findings of the Association for Computational Linguistics: NAACL 2025, pages 2678–2710. find
  10. Caigao Jiang, Xiang Shu, Hong Qian, Xingyu Lu, Jun Zhou, Aimin Zhou, and Yang Yu. 2024. Llmopt: Learning to define and solve general optimization problems from scratch. arXiv preprint arXiv:2410.13213. — [arXiv:2410.13213](https://arxiv.org/abs/2410.13213) find
  11. Beibin Li, Konstantina Mellou, Bo Zhang, Jeevan Pathuri, and Ishai Menache. 2023. Large language models for supply chain optimization. arXiv preprint arXiv:2307.03875. — [arXiv:2307.03875](https://arxiv.org/abs/2307.03875) find
  12. Hongliang Lu, Zhonglin Xie, Yaoyu Wu, Can Ren, Yuxuan Chen, and Zaiwen Wen. 2025. OptMATH: A scalable bidirectional data synthesis framework for optimization modeling. In Forty-second International Conference on Machine Learning. find
  13. Zeyuan Ma, Hongshu Guo, Jiacheng Chen, Guojun Peng, Zhiguang Cao, Yining Ma, and Yue-Jiao Gong. 2024. Llamoco: Instruction tuning of large language models for optimization code generation. arXiv preprint arXiv:2403.01131. — [arXiv:2403.01131](https://arxiv.org/abs/2403.01131) find
  14. Thomas M Moerland, Joost Broekens, Aske Plaat, and Catholijn M Jonker. 2020. The second type of uncertainty in monte carlo tree search. arXiv preprint arXiv:2005.09645. — [arXiv:2005.09645](https://arxiv.org/abs/2005.09645) find
  15. Brendan O’Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. 2018. The uncertainty bellman equation and exploration. In International conference on machine learning, pages 3836–3845. find
  16. Yaniv Oren, Villiam Vadocz, Matthijs TJ Spaan, and Wendelin Böhmer. 2022. Epistemic monte carlo tree search. arXiv preprint arXiv:2210.13455. — [arXiv:2210.13455](https://arxiv.org/abs/2210.13455) find
  17. Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. 2023. Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. arXiv preprint arXiv:2305.12295.
  18. Rindranirina Ramamonjison, Timothy Yu, Raymond Li, Haley Li, Giuseppe Carenini, Bissan Ghaddar, Shiqi He, Mahdi Mostajabdaveh, Amin Banitalebi-Dehkordi, Zirui Zhou, and Yong Zhang. 2022. Nl4opt competition: Formulating optimization problems based on their natural language descriptions. find
  19. In Proceedings of the NeurIPS 2022 Competitions Track, volume 220 of Proceedings of Machine Learning Research, pages 189–203. PMLR. find
  20. Christopher D Rosin. 2011. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203–230. find
  21. Zhengyang Tang, Chenyu Huang, Xin Zheng, Shixi Hu, Zizhuo Wang, Dongdong Ge, and Benyou Wang. 2024. Orlm: Training large language models for optimization modeling. arXiv preprint arXiv:2405.17743. — [arXiv:2405.17743](https://arxiv.org/abs/2405.17743) find
  22. Raghav Thind, Youran Sun, Ling Liang, and Haizhao Yang. 2025. Optimai: Optimization from natural language using llm-powered ai agents. arXiv preprint arXiv:2504.16918. — [arXiv:2504.16918](https://arxiv.org/abs/2504.16918) find
  23. Ziyang Xiao, Dongxiang Zhang, Yangjun Wu, Lilin Xu, Yuan Jessica Wang, Xiongwei Han, Xiaojin Fu, Tao Zhong, Jia Zeng, Mingli Song, and 1 others. 2023. Chain-of-experts: When llms meet complex operations research problems. In The twelfth international conference on learning representations. find
  24. Yusuke Yamauchi, Taro Yano, and Masafumi Oyamada. 2025. An empirical study of llm-as-a-judge: How design choices impact evaluation reliability. arXiv preprint arXiv:2506.13639.
  25. Zhicheng Yang, Yiwei Wang, Yinya Huang, Zhijiang Guo, Wei Shi, Xiongwei Han, Liang Feng, Linqi Song, Xiaodan Liang, and Jing Tang. 2025. Optibench meets resocratic: Measure and improve LLMs for optimization modeling. In The Thirteenth International Conference on Learning Representations. find
  26. Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi. 2024. The shift from models to compound ai systems. https://bair.b erkeley.edu/blog/2024/02/18/compound-ai-s ystems/. ↗
  27. Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Zhihan Guo, Yufei Wang, Irwin King, Xue Liu, and Chen Ma. 2025. What, how, where, and how well? a survey on test-time scaling in large language models. arXiv preprint arXiv:2503.24235.
  28. Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B Tenenbaum, and Chuang Gan. 2023. Planning with large language models for code generation. arXiv preprint arXiv:2303.05510.
  29. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, and 1 others. 2023. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in neural information processing systems, 36:46595–46623.
  30. Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. 2025. Monte carlo tree search for comprehensive exploration in llm-based automatic heuristic design. In Forty-second International Conference on Machine Learning. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yu-2026-uncertainty-aware-test-time-search/