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

arXiv:2508.05995 · cs.LG · Submitted 2025-08-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization".

Jane: Here's the gist of the paper. The gist: MCTS-OPS, a novel neural-symbolic framework, formulates prompt selection as a sequential decision process guided by Monte Carlo Tree Search to optimize multi-step prompt sequences for improving code generation quality and enhancing LLMs in general optimization.

Tom: (Page 1) Problem Context and Motivation Large language models often struggle with complex tasks requiring consistent multi-step reasoning and structured output, such as planning and optimization problems, because they operate in a one-shot or few-shot mode, leading to logically inconsistent or suboptimal solutions when tasks require long-horizon decisionmaking (Page 1).

Jane: Existing approaches primarily focus on generating heuristic-based code for optimization or target simpler tasks where correctness alone is sufficient (Page 2).

Tom: The paper tackles the challenging setting of using LLMs to synthesize code that solves numerical optimization problems with constraints, treating prompt generation itself as a search problem (Page 2).

Title and authors: Tom: Let's talk about the title itself, "Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization." It tells you exactly what they're trying to do—optimize sequences, use MCTS, and target optimization tasks.

Jane: And the authors are from George Washington University. It’s a solid team of researchers who seem focused on combining the strengths of different AI techniques to tackle these planning problems.

Lu: What’s interesting is that they aren't just looking at prompt engineering as a single step; they are framing it as a search problem where each prompt is a decision point in a larger sequence.

Meng: So, instead of one big instruction, they’re building something piece by piece? That sounds like it could be very brittle if the early pieces aren't good.

Lalam: The paper suggests that poor early choices can seriously mess up the rest of the generated code, which makes sense when you're dealing with constraints and optimization.

The paper's summary: Tom: Basically, they introduce MCTS-OPS as a framework that integrates LLMs with Monte Carlo Tree Search to optimize prompt sequences for code generation quality and general problem-solving in optimization.

Jane: They are saying that current methods often fail because they rely on fixed or heuristic templates, but this new approach lets the AI explore the space of different prompts systematically to find the best path.

Lu: The core idea is decomposition first, then scoring each resulting prompt based on how clear and relevant it is using another LLM, and then using MCTS to navigate that space efficiently.

Meng: So, there's an LLM decomposing the problem into sentences, and then another LLM judging those sentences before the code generation even starts? That sounds like a lot of overhead to run.

Lalam: The paper describes how they store these prompt-score pairs in the MCTS tree to manage variability while keeping track of what works well.

The paper's improvements: Tom: One big improvement is how they use Monte Carlo Tree Search with the Upper Confidence Bounds applied to Trees, or UCT formula, which balances exploring new prompts against using the ones that have performed best so far.

Jane: That’s clever because it stops them from just getting stuck on one good idea and forces the system to keep looking for better ways to structure those prompts.

Lu: They also have this optional iterative feedback loop built in; if the reward score of a generated script is below a certain threshold, they prompt the LLM to revise and re-evaluate until they hit a convergence point or run out of tries.

Meng: Iterative refinement sounds like it’s trying to fix the inevitable small mistakes that happen when you're generating long programs automatically, which is something I see all the time in production.

Lalam: The results show significant gains: on easy settings, they improved execution success rate from seventy-two percent up to ninety-eight percent, and nearly doubled the average optimization reward.

Conclusion: Tom: So, to wrap it up, this paper shows that combining classical planning algorithms like MCTS with generative models can really help LLMs tackle complex optimization tasks by optimizing the way they are prompted.

Jane: It moves beyond just getting a correct answer and aims for structured code that satisfies constraints, which is much closer to real engineering work.

Lu: The implication is that we might see more planning-aware LLMs where the model learns not just what to say, but how to structure the entire reasoning process step by step.

Meng: For deployment, the key seems to be that this search mechanism provides a systematic way to find robust prompts without you having to manually craft every single instruction from scratch.

Lalam: The paper on "Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization" shows that MCTS-OPS significantly outperforms standard LLM baselines in terms of success rate, reward quality, stability, and optimality.

Tom: That’s the essence of it—a systematic way to make those multi-step generations much more reliable and high quality.

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

George Washington University · United States Military Academy

cs.LG

Submitted: 2025-08-08

Updated: 2026-10-18

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist: MCTS-OPS, a novel neural-symbolic framework, formulates prompt selection as a sequential decision process guided by Monte Carlo Tree Search to optimize multi-step prompt sequences for

Key concepts

MCTS-OPS Framework: This is a novel system that combines Large Language Models (LLMs) with Monte Carlo Tree Search (MCTS). It treats the process of choosing the right sequence of prompts as a search problem, allowing the system to explore many prompt possibilities efficiently to find the best path for generating correct code.
Prompt Generation and Scoring: The system takes a natural language problem and decomposes it into sentences. Each sentence is turned into a prompt, which is then scored by another LLM based on clarity and relevance. These prompt-score pairs form the nodes in the MCTS tree, helping the search balance exploring new ideas with using known good prompts.
Backpropagation of Reward: After generating code from a selected prompt sequence, it runs the script to get a numerical reward score (0-10). This score is used to update the MCTS tree. High rewards reinforce those paths, guiding future searches toward prompt sequences that lead to better, more correct optimization solutions.
UCT Formula: The Upper Confidence Bounds applied to Trees (UCT) formula is the search strategy used by MCTS. It helps decide which prompt sequence to try next by balancing two goals: exploring less-tried prompts and exploiting those that have already yielded high reward scores, ensuring thorough searching.

Terminology

LLMs with Monte Carlo Tree Search — 1× in this paper
Large Language Models (LLMs) — 1× in this paper · explained in 9 episodes
Monte Carlo Tree Search (MCTS) — 1× in this paper · explained in 3 episodes
Structured Reasoning — 1× in this paper · explained in 3 episodes

Summary

The gist: MCTS-OPS, a novel neural-symbolic framework, formulates prompt selection as a sequential decision process guided by Monte Carlo Tree Search to optimize multi-step prompt sequences for improving code generation quality and enhancing LLMs in general optimization. (Page 1)

Problem Context and Motivation

Large language models often struggle with complex tasks requiring consistent multi-step reasoning and structured output, such as planning and optimization problems, because they operate in a one-shot or few-shot mode, leading to logically inconsistent or suboptimal solutions when tasks require long-horizon decisionmaking (Page 1). Existing approaches primarily focus on generating heuristic-based code for optimization or target simpler tasks where correctness alone is sufficient (Page 2). The paper tackles the challenging setting of using LLMs to synthesize code that solves numerical optimization problems with constraints, treating prompt generation itself as a search problem (Page 2).

MCTS-OPS Framework

The MCTS-OPS framework integrates LLMs with MCTS to optimize prompt sequences for code generation (Page 2). The process involves several interconnected steps:

Decomposition: Given a natural language description of an optimization problem, the LLM is prompted to decompose it into a sequence of concise, semantically meaningful sentences (Page 3).
Prompt Generation and Scoring: Each sentence is transformed into a prompt that is then scored via an LLM-based evaluation to reflect its clarity, relevance, and coherence (Page 3). Nodes in the MCTS tree are stored as prompt-score pairs to manage variability while ensuring semantic equivalence (Page 3).
Code Generation: Once a node is selected, the LLM generates Python code using that prompt, incorporating all previously generated code segments along the path to maintain logical consistency (Page 4).
Evaluation and Backpropagation: The fully generated script is executed in a Python environment, and its output is passed to an evaluator LLM which returns a numerical reward score (ranging from 0 to 10) capturing executability, correctness, constraint satisfaction, and optimality (Page 3). This reward signal is backpropagated through the tree to inform future prompt selection (Page 4).

Search Strategy and Refinement

The framework utilizes Monte Carlo Tree Search for Prompt Sequence Optimization (MCTS-OPS) by employing the Upper confidence Bounds applied to Trees (UCT) formula to balance exploration and exploitation of high-performing prompts (Page 3). The MCTS follows the standard four-phase cycle: selection, expansion, simulation, and backpropagation (Page 4). Furthermore, an optional iterative feedback loop is included where if the reward score falls below a predefined threshold, the system initiates a revision process by prompting the LLM to revise and re-evaluate the code until convergence or maximum retries are reached (Page 5).

Performance Results

Experiments on network optimization tasks involving power allocation under SINR and interference constraints show significant improvements over baselines (Page 2). Compared to standard LLM models like GPT-3.5-turbo and GPT-4, MCTS-OPS shows substantial gains in both robustness and performance (Page 2). Specifically, 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 (Page 6). Under hard settings, it raises the success rate from 0% to 70% and achieves a tenfold increase in the probability of reaching the ground truth optimal solution (Page 6). The framework is shown to be essential for achieving high success rates, average reward, and attainment of optimality, as demonstrated by ablation studies showing that both MCTS-based exploration and feedback-driven refinement are complementary components (Page 10).

Conclusion

MCTS-OPS successfully demonstrates the potential of integrating classical planning algorithms with generative models for complex problem-solving and planning (Page 5). The results show that MCTS-OPS significantly outperforms strong LLM baselines in terms of success rate, reward quality, stability, and optimality (Page 7). The study highlights new opportunities for research on planning-aware LLMs and interpretable prompt generation (Page 7).

Limitations

The current evaluation focuses on network optimization problems with corresponding objectives and constraints (Page 6). Future work may explore its applicability to a broader class of optimization tasks, including combinatorial optimization, decision-making under uncertainty, and real-world planning domains to further assess its generalization capabilities across diverse problem types (Page 10).

References

[1] Juyong Jiang, Fan Wang, Jiasi Shen, Sungju Kim, and Sunghun Kim. A survey on large language models for code generation, 2024. URL https://arxiv.org/abs/2406.00515 (Page 13)

[2] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume. Competition-level code generation with alphacode. Science (Page 13)

[3] Amr Almorsi, Mohanned Ahmed, and Walid Gomaa. Guided code generation with llms: A multi-agent framework for complex code tasks, 2025. URL https://arxiv.org/abs/2501.06625 (Page 13)

[4] Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. Monte-carlo tree search: A new framework for game ai. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 4(1):216–217 (Page 13)

[5] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam. Mastering the game of Go with deep neural networks and tree search. Nature (Page 13)

[6] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad. Gpt-4 technical report (Page 13)

[7] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac. Gemini: A family of highly capable multimodal models (Page 13)

[8] Zuyuan Zhang, Hanhan Zhou, Mahdi Imani, Taeyoung Lee. Learning to collaborate with unknown agents in the absence of reward (Page 13)

[9] Amirhossein Ravari, Guangyu Jiang, Zuyuan Zhang, Mahdi Imani. Adversarial inverse learning of defense policies conditioned on human factor models. In 2024 58th Asilomar Conference on Signals, Systems, and Computers (Page 13)

[10] Zuyuan Zhang, Mahdi Imani, and Tian Lan. Modeling other players with bayesian beliefs for games with incomplete information. arXiv preprint arXiv:2405.14122 (Page 13)

[11] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan. Evaluating large language models trained on code (Page 13)

[12] Erik Nijkamp, Bo Pang, Hiroaki Hayashi. Codegen: An open large language model for code with multi-turn program synthesis (Page 13)

[13] Eric Zelikman, Yuhuai Wu, Jesse Mu, Noah D. Goodman. Star: Bootstrapping reasoning with reasoning (Page 13)

[14] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan. Self-refine: Iterative refinement with self-feedback (Page 13)

[15] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma. Chain-of-thought prompting elicits reasoning in large language models (Page 13)

[16] Zuyuan Zhang, Vaneet Aggarwal, Tian Lan. Network diffuser for placing-scheduling service function chains with inverse demonstration. In IEEE INFOCOM 2025-IEEE Conference on Computer Communications (Page 13)

[17] Pranab Sahoo, Ayush Kumar Singh, Sriparna Saha, Vinija Jain. A systematic survey of prompt engineering in large language models: Techniques and applications (Page 13)

[18] Shubham Vatsal and Harsh Dubey. A survey of prompt engineering methods in large language models for different nlp tasks (Page 13)

[19] Di Zhang, Xiaoshui Huang, Dongzhan Zhou, Yuqiang Li, Wanli Ouyang. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b (Page 13)

[20] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, Jie Tang. Rest-mcts: Llm self-training via process reward guided tree search (Page 13)

[21] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang. Monte carlo tree search for comprehensive exploration in llm-based automatic heuristic design (Page 13)

[22] Qingyao Li, Wei Xia, Kounianhua Du, Xinyi Dai.

Improvements for AI systems

MCTS-OPS can optimize multi-step prompt sequences for structured code generation by treating prompt selection as a sequential decision process guided by Monte Carlo Tree Search (MCTS). This allows the system to explore the prompt space efficiently, moving beyond fixed or heuristic templates.
The improved system can solve numerical optimization problems with constraints, such as those in wireless network optimization, with significantly higher success rates and better solution quality than current baselines. Specifically, it shows a 3× lower standard deviation in reward for easy tasks and achieves a tenfold increase in the probability of reaching the ground truth optimal solution on hard problems.
The system incorporates an optional iterative feedback loop for code refinement, which helps recover from minor issues by prompting the LLM to revise and re-evaluate code if the initial execution score is below a threshold. This mechanism significantly improves robustness and success rate by addressing common LLM failures like syntax errors.
By using UCT formula (UCT(v) = Q(v) / N(v) + c · s log N(p) / N(v)), the system balances exploration of new prompts with exploitation of high-performing ones in the prompt space. This ensures that the search for optimal prompt sequences is both thorough and focused on promising strategies.
The framework can dynamically construct context-aware Python code by recursively generating segments based on selected prompts, where each segment incorporates all previously generated code to maintain logical consistency. This contextualized generation avoids errors like redefining variables, inconsistent logic, or disjoint syntax.

Abstract

Mathematical optimization is a core tool in engineering, operations research, and data science, but modeling real problems remains difficult and time-consuming. In practice, an expert must work with clients to translate informal domain descriptions into precise objectives, constraints, and solver-ready code; small mistakes in this process can lead to infeasible, nonconvex, or suboptimal formulations, and the iterative process is often slow. Large language models (LLMs) could automate this translation from natural language to optimization code, but standard prompting often fails on realistic tasks: it struggles with long, structured task descriptions, mishandles constraints, and produces infeasible, non-convex, or non-executable programs. We introduce Monte Carlo Tree Search for Reasoning Decomposition Plans (MCTS-RDP), which performs pre-hoc test-time scaling by searching over decomposition plans and their resulting programs before committing to the final output. MCTS-RDP treats plan construction as a sequential decision problem: given a problem description, it decomposes the task descriptions into logical components and generates candidate plan steps for each component. Monte Carlo Tree Search (MCTS) then explores and refines Reasoning Decomposition Plans (RDPs) prior to code synthesis, balancing exploration and exploitation across alternative plan sequences. Each candidate plan is rolled out into executable code, executed, and scored with an execution-grounded evaluator measuring executability, constraint satisfaction, and solution quality; this feedback is backpropagated through the search tree to guide subsequent search. Across wireless optimization tasks and the NL4OPT and NLP4LP benchmarks, MCTS-RDP consistently outperforms strong baselines, improving execution success, reward, stability, and optimality attainment.