Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization

Fei Xu Yu, Gina Adam, Nathaniel D. Bastian, Tian Lan · 2025

Read Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization by Fei Xu Yu, Gina Adam, Nathaniel D. Bastian, Tian Lan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05995.txt.

Introduction

Fei Xu Yu and co-authors wrote a paper from 2025 on using tree search to plan how a language model should attack a math optimization problem. Turning a client's loose description into solver-ready code is slow expert work, and small slips yield broken or poor formulations. Plain prompting often fails on long, structured tasks: it drops constraints or writes code that will not run. The team moved the planning step before the coding step.

Their method first breaks the task into logical parts and drafts plan steps for each. A Monte Carlo tree search then explores rival plan sequences, weighing new branches against proven ones. Each candidate plan is rolled out into code, run, and scored on whether it executes, obeys the constraints, and solves well. Scores flow back up the tree to steer the next round. Across wireless tasks and two benchmarks, the method beat strong baselines.

Catalog record

CREATORFei Xu Yu, Gina Adam, Nathaniel D. Bastian, Tian Lan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05995

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization Fei Xu Yu, Gina Adam, Nathaniel D. Bastian, Tian Lan Abstract Large language models (LLMs) have demonstrated remarkable capabilities in code generation and structured reasoning; however, their performance often degrades on complex tasks that require consistent multi-step planning. Recent work has explored combining LLMs with Monte Carlo Tree Search (MCTS), yet existing approaches primarily focus on generating heuristic-based code for optimization or target simpler tasks where correctness alone is sufficient. In this work, we propose MCTS-OPS, a novel neural-symbolic framework that formulates prompt selection as a sequential decision process guided by MCTS. Our method explores and refines multi-step prompt sequences for the goal of improving code generation quality and enhancing the problem-solving capabilities of LLMs in general optimization. Experiments on network optimization show significant improvement over the baselines, both in the success rate of executing the generated code and in the optimization results with the specified objective and constraints (2 ∼ \sim 4 × \times higher reward and 3 × \times lower standard deviation). Moreover, it improves the chance of attaining the optimal solution by about 10% of cases, compared to baseline methods in hard problems. These results highlight the promise of combining symbolic planning with LLMs for robust, high-quality code generation in complex domains. 1 Introduction Large language models (LLMs) have demonstrated strong capabilities in generating code from natural language [ 1 ] . As a result, they are being increasingly adopted to assist in solving real-world computational tasks. However, they often struggle to produce correct or complete programs for complex problems that require consistent multi-step reasoning and structured output, such as planning and optimization problems. A key limitation is that LLMs operate in a one-shot or few-shot mode, with each generation step in isolation. When tasked with problems that require long-horizon decision-making, the model may generate syntactically valid but logically inconsistent or suboptimal solutions. These errors are due to the autoregressive formulation and limited context modeling, which hinder the model’s ability to perform multi-step reasoning and maintain coherent representations over extended decision sequences [ 2 , 3 ] . To mitigate this, recent research has begun integrating LLMs with symbolic search and decision-making frameworks such as Monte Carlo Tree Search (MCTS) [ 4 ] . Tree search has been proven effective in applications like game playing and planning due to its ability to balance exploration and exploitation in high-dimensional action spaces [ 5 ] . In the context of LLMs, MCTS has been used to guide thought chains, refine solutions, and improve coherence. However, these works are primarily designed for tasks where generating a correct answer is sufficient, and rarely focus on generating structures, executable programs, where correctness must be accompanied by constraint satisfaction and objective optimization. In this paper, we tackle a more challenging setting: using LLMs to synthesize code that solves numerical optimization problems with constraints. This setting resembles many real-world engineering domains, such as wireless communication, operations research, and control. Unlike prior works that use fixed or heuristic prompt templates, we treat prompt generation itself as a search problem. Each prompt corresponds to a decision about how to decompose the optimization problem, how to express it to the language model, and how to structure the generated code. These decisions are interdependent, and poor early choices can render later code incorrect or incoherent. To address this, we introduce Monte Carlo Tree Search for Optimal Prompt Sequences Generation (MCTS-OPS), a neural-symbolic framework that integrates LLMs with MCTS to optimize prompt sequences for code generation. The use of MCTS enables efficient search in the prompt space and naturally handles the uncertainty of LLM outputs. Our framework works as follows: given a natural language description of an optimization problem, we first decompose it into logical components (e.g., context, objective, constraints) using the LLM. For each component, prompt candidates are generated and evaluated via LLM-based scoring. MCTS is used to select and refine prompt sequences that maximize the final reward, defined by the executability, correctness, and optimality of the generated code. The reward signal is obtained by executing the full script and interpreting the outputs using another LLM. The result is backpropagated through the tree to inform future prompt search. We evaluate MCTS-OPS on a variety of wireless network optimization tasks involving power allocation under SINR and interference constraints. These tasks require numerical reasoning, precise variable definitions, and constraint formulation, which make them a strong benchmark for code synthesis quality. Compared to standard LLM models (GPT-3.5-turbo and GPT-4) and LLM-based method baselines, MCTS-OPS shows substantial gains in both robustness and performance. Under the easy setting, MCTS-OPS improves the execution success rate from 72% to 98%, nearly doubles the average optimization reward, and reduces the reward standard deviation by over a factor of three. It improves attainment to optimality from 42% to 92%. Under the hard setting, it raises the success rate from 0% to 70% and achieves a tenfold increase in the probability of reaching the ground truth optimal solution. These results demonstrate the importance of treating prompt design as a planning problem and highlight the potential of integrating symbolic search with language reasoning. Our key contributions are as follows. First, we propose a novel framework, MCTS-OPS, that integrates MCTS with LLMs to optimize multi-step prompt sequences for structured code generation. For each given task, our solution effectively explores the prompt space using MCTS and identifies the optimal prompt sequence with the highest success rate. Second, we introduce a pipeline with decomposition, prompt scoring, code synthesis, and iterative evaluation via reward backpropagation to guide MCTS-OPS through exploration and exploitation. We validate our approach on constrained optimization tasks and demonstrate significant improvements over existing LLM baselines, including GPT-4, GPT-3.5-turbo, Chain-of-Thought, and Self-Refine, in success rate, reward, and stability. 2 Related Work Recent advances in large language models (LLMs) have enabled strong performance across a wide range of tasks, from natural language processing to code generation and high-level reasoning. However, applying LLMs to structured problem-solving, particularly tasks involving multi-step long-horizon planning and decision-making, remains a significant challenge. This has motivated research focused on improving LLM performance through better prompt design, integration with symbolic planning techniques, and hybrid frameworks that combine learning-based and search-based methods. In this section, we review related work across four key areas. 2.1 Large Language Models for Code Generation and Structured Problem Solving LLMs have evolved human-computer interaction by allowing more natural, context-aware communication. Studies have shown that LLMs can improve user productivity in domains such as software development, legal analysis, and scientific research by offering explanations and justifications that align with human reasoning [ 6 , 7 , 8 , 9 , 10 ] . In the context of code generation, LLMs have been widely applied to tasks such as synthesis, translation, and bug repair [ 11 , 12 ] . While LLMs can generate correct code snippets in constrained settings, they often struggle with multi-step reasoning tasks or problems requiring precise constraint satisfaction, such as numerical optimization. Several studies [ 13 , 14 , 15 , 16 ] have proposed methods to decompose problems into smaller subproblems or use natural language feedback to improve generation quality. However, these methods typically rely on hand-crafted chains of thought

Read the complete text