A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks
Authors: Xinzhe Li
Venue: Accepted by TMLR ()

Abstract: LLM test-time compute (or LLM inference) via search has emerged as a promising research area with rapid developments. However, current frameworks often adopt distinct perspectives on three key aspects—task definition, LLM profiling, and search procedures—making direct comparisons challenging. Moreover, the search algorithms employed often diverge from standard implementations, and their specific characteristics are not thoroughly specified. This survey aims to provide a comprehensive but integrated technical review on existing LIS frameworks. Specifically, we unify task definitions under Markov Decision Process (MDP) and provides modular definitions of LLM profiling and search procedures. The definitions enable precise comparisons of various LLM inference frameworks while highlighting their departures from conventional search algorithms. We also discuss the applicability, performance, and efficiency of these methods. For ongoing paper updates, please refer to our GitHub repository: https://github.com/xinzhel/LLM-Search.

Published in Transactions on Machine Learning Research (04/2025)
A Survey on LLM Test- Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks
Xinzhe Li
Reviewed on OpenReview: https: // openreveew. net/ forum? id=
Abstract
LLM test-time compute (or LLM inference) via search has emerged as a promising research area with rapid developments. However, current frameworks often adopt distinct perspec- lives on three key aspects: lask definition, LLM profiling, and search procedures, making direct comparisons challenging. Moreover, the search algorithms employed often diverge from standard implementations, and their specific characteristics are not thoroughly spec- ified. This survey aims to provide a comprehensive but integrated lechnical review on existing LIS frameworks. Specifically, we unify task definitions under Markov Decision Pro- cess (MDP) and provides modular definitions LLM profiling and search procedures. The definitions enable precise comparisons of various LLM inference frameworks while highlight- ing their departures from conventional search algorithms. We also discuss the applicability, performance, and efficiency of these methods. For ongoing paper updates, please refer to our GitHub repository: https://github.com http://hhb...co//ccheee/////aaa
1 Introduction
Auto-regressive Large Language Models (LLMs) such as GPT-4 (Achiam et al. 2023 have achieved impres-
sive performance across range of tasks using few-shot prompting (Radford ct al. 2019 Brown et al. 2020 or even zero-shot prompling (Kojima et al. 2022). They demonsttate broad world anowledge commonsense,
and human-like reasoning for problem solving (Santurkar et al. 2023 Wang et al. 2022 Zhong et al. 2022
2023). Nonctheless, those models still struggle with complex tasks that require long-horizon planning and deep reasoning. This limitation motivates extending sequential decoding with search methods (Yao et al. 2023a:
Hao et al. 2023), an approach we refer to as LLM Inference via Search (LIS) this survey.
To clarify the specific reasoning and planning tasks that challenge LLMs, we distinguish between two general categories:
1. Language Reasoning Tasks: These tasks align closely with typical Natural Language Processing (NLP) problems but require multi-step reasoning, such as solving math word problems (Cobbe et al. 2021). Some prior works classify language reasoning as a form of planning (Huang et al.
2024). Anyway, LLMs frequently achiove near-saturation performance on these tasks, especially when explicitly prompted to generate intermediate steps using methods like Chain-of-Thousg Wei et al. 2022b. Valmeekam et al. (2023a) argue that the reason for such high performance that the solutions and reasoning paths for these tasks are likely included world knowledge and commonsense in the LLM training corpus. To more rigorously evaluate reasoning capabilities, Valmeekam et al. (2023a) introduce problem sets that involve multi-step reasoning beyond traditional NLP contexts, leading to the second category.
(CoT)
2. Non-NLP Tasks:
These tasks typically involve simple decision-making environments (such games) and dynamic real-world scenarios (such as houschold or logistics tasks) traditionally ad- dressed by reinforcement learning and classical planning algorithms. Current stale-of-the-art LLMs
While related, frameworks discussed in Section are not categorized under L.S.

---

Published in Transactions on Machine Learning Research (04/2025)
show significantly lower performance compared to humans benchmarks in these domains, includ- ing PlanBench (Valmeekam et. al. 2023a b) and SearchBench (Borazjanizadeh et al. 2024
Importantly, survey not only addresses the challenging scenarios of planning but also systematically explores all tasks that can be formulated within LIS frameworks, including language reasoning, sequential decision- decision-making tasks like robotics (Putta et al. 2024) and graph- graph-traversal tasks such as path finding (Meng eet al. 2024). The following two subsections highlight the unique perspectives and novel contributions offered by this survey.
1.1 Existing Surveys
Current reviews on LLM search are limited from the following perspectives.
No dedicated, Detailed Survey Current surveys only contain paragraphs or sections to roughly touch both technical aspects and their practical applicability, summarized in Table
Limited Mention on LLM-Side Design Specifically, most of existing surveys (Hang et al. 2024 Wang et al. 2024b) mention little or a few implementations and dimensions for LLM profiling, which is not suitable for all the frameworks. Besides, the lack of examples hinders understanding.
Limited Mention on Scarch Li (2024) give more detail regarding LLM profiling but lack details on
search processes. Nonthelessness,, most. of existing surveys (Huang et al. 2024 Wang et al.) 2024b) give a general sense of the computation process by mentioning which classical search algorithms the frameworks are built upon (e.g,, depth-first search). However, details should be given because of their nuanced differences. Besides, many untypical twists to classic search algorithms are hidden. The deviations are not friendly for newcomers in the newly-developed area, e.g., those computer science graduates educated with typical search algorithmss
Table 1: Comparisons with other surveys related to LLM inference via search (LIS). " "Coverage" indicates the number of related papers, "Sections" refers to the sections of the survey manuscripts that discuss LLM inference via search, and "Def." is the abbreviation for Definition. The URLs for the reference versions are given the footnotes. "Mentioned" refers to the mention of the LLM function, while "Limited" means that a formal definition is given without specific distinctions. The numerical values correspond to the number of implementations (impl.) or dimensions (dim.) identified for LLM-Profiled Roles (LMPRs); different dimensions may lead to a combinatorial number of implementations. "254 represents the number of papers detailed in Sections and excluding those used solely for benchmarking, analysis, or from related domains.
Coverage
Sections
Task Def.
Search Algorithms
LLM Profiling
Details
Deviations
Policy
Value
Transition
Huang
($4)
x
X
1 impl.
impl.
ct
2024)
Wang of
(52.1.3)
X
Mentioned
2024b)
T. (2244)
8
($4.3)
X
Limited
X
2 impl.
2 dim.
NA
Ours
25+
All
8 impl.
dim.;
2 impl.
14 impl.
2

---

Published in Transactions on Machine Learning Research (04/2025)
1.2 Survey Structure
To solve the above limitations, we provide unified task definitions and decouple the LLM-specific design (mainly prompting) from the control program (search procedures/ate prooedure//agooritmmms) /algorithms). There exists a hierarchical structure between them: the low-level definitions provide a unified interface for the high-level components. The overall structure, accompanied by illustrative examples, is presented in Figure [
Tusk
Dotails in Table 2
Definitions
Low-level
Policy (33.1
Details in Table
Modules:
Transition (.2
LLM-
Profiled
Roles (43
Emihutor ($3.3
Details in Table
Mid-level
Modules:
Sourch
Details Tahle
Procedures
E.g.. Beam-LLMM Xie et al
2023
PathFinder Golooveva al
2023
Beam Soarch
Thinic-on-Grapl (Smn 2014
Think-on-Ghne 20 Mi
2025
M" (Beam) (Kang ot al.
BFS (broathh)
E.g.. Tol Yao et al.
202
DFS
B.g., ToT
Yao
2023a
LTS (LLM
Inferrnce vin
(Best)
E.g., Best- LLM!
Koh et al.
2024
M1 (Best)
Kanng es
al.
2014
LLM Soarch
Sowrch)
Frameworkss
A+
E.g., LLM-A* Mong et al.
2024
Q+ Wang et al.
2012ta
TootChain
Zhoang et al 2024
MCTS
F-g.- RAP
Hao ot ml.
2023
LATS Zhon ot ml.
2024n
L.M-MCTS
Thao et al. 2023
rStar
(Qi et a. 2025
DML
Shi ct ml
G-MTSS
E.g.. PG-TD
Zhang et al.
2123
ZERO Yu et al.
2028
TS- Wan et al.
2024
ReST-MCTS
Zioang et al.
212
LLM for World Modeling Search
E.g.. Guan es al.
2023 LLM+P
Liu es al.
2023
Dainese et al.
2024
Others Including LLM
Meta-Search for High-TLvel Surategies
E.g., AF'low Zhang al.
2025
DOTS
Yue et al.
2025
Strategist Light
2125
Inference
Zheng et al. 2026
and Search (5
Exolutionary Search
F.g., ExsPrompting Chen al.
2023
Wang
2025b
LLM fine-tuning for LMPRs
Egg., CPO Zhang 2024b
TS-LLM Wan
2024
MCTS
Zhing al. 20
Agent
Putta et
Scarch with Mudti-Modal LLMs
Reluted Work
E.g., Mulberry Yao
2024
Branching withont Search
E.g. Thee-Planner ml.
2024
(GoT)
et al.
Re-Hanking
E.g., LEVER
Ni et
2023
Self consistency
Wang et al. 2023 DiVeRSe
al. 2023
Frameworlcs
Self-refine Maduan
202
Figure 1: Survey structure. This table shows a selected subset of the works reviewed. Here are two notes: 1) To avoid duplication, comprehensive lists of related work for Task Definitions and LLM-Profiled Roles are provided in the refered tables; 2) Framework names marked with a sword symbol (f) denote those devised by the authors of this survey, rather than being directly drawn from existing literature.
Introducing a Unified Task Definition Based on MDPs (S ( Our definition standardizes different tasks in MDP structure. While MDPs naturally align with AI domains like robotics, special attention is given to adapting this definition for tasks traditionally not modeled as MDPs, such as graph traversal, reasoning, dialogue systems, and code generation. Notably, this MDP-baasd definition is also applicable to other LLM inference frameworks beyond search, including works like Li et al. (2022), Zhao et al. (2023). and Hu et al. 22024..
3

---

Published in Transactions on Machine Learning Research (04/2025)
Comprehensively Summarizing LLM Profiling and Implementations ($ The design and imple- mentation of LLM profiling and prompting can be modularized into components commonly used in solving MDPs (Sutton & Barto 2018): policies, value functions, and transition models. Correspondingly, 3 types of LLM-Profiled Roles (LMPRs) are defined.
Defining Modular Scarch Procedures ($ Rather than directly showcasing individual scarch-basod frameworks for LLM inference, we locus on modular and reusable components to reduce redundancy and en- able more straightforward comparisons across frameworks, This approach promotes flexibility and minimizes overhcad when adapting or extending search methods.
Reviewing Individual Framoworks (S Based on the unified task and LMPR interface, we provide a comprehensive review of individual frameworks, organized by the search algorithuss they are built upon. Our analysis highlights how LLM integration either diverges from or enhances traditional search algorithms. We identify and clearly present 11 frameworks, summarized in Table 7 This count exclusively includes frameworks that focus test-time computation through search detailed in Section 5 Note that our im- plementations may differ from the specific approach described in the original manuscripi, our goal is to provide a unified interface that facilitates easier comparison among various methods. Nevertheless, they are functionally equivalent. For example, whereas Koh et al. (2024) implement Best-first search using a priority queue, we achieve the same oulcome by employing a lop-k selection procedure that is common to MCTS and other search algorithms.
Comparisons with Other Test-Time Frameworks Additionally, we highlight other test-time frame- works that function as components within scarch processes, such as ReAct (Yao et al., (023b), CoT (Wei et al.
2022 and Self-Consistency (Wang al., 2023), along with those discussed in Section
Analyzing Key Perspectives of LIS Frameworks ($ We critically examine these mothods from four key perspectives: deviation, applicability, performance, and efficiency. For deviations, we compare the structural and functional differences between search procedures in LIS frameworks and standard search algorithms as described in foundational texts such Russell & Norvig (2010) and (Sutton & Bartt (2018). This analysis highlights how LLMs modify or enhance traditional search processes, providing deeper understanding of their impact and potential.
Other LLM Inference + Search Directions G This survey primarily focuses on LLM inference via search, where downstream tasks are formulated as sequential Docision-making problems, and LLMs serve as integral components. This focus allows us to present a detailed, concise, and systematic analysis. However, confining our discussion solely to these frameworks might give the impression that the title overstates our scope. Hence, Section f covers additional research directions that also involve LLM inference and search.
1.3 Intended Audience and Use Cases
Reviewed Venues Our goal is to provide comprehensive overview of the latest research from active venues. To this end, we systematically search high-quality conferences that publish work on LLM inference via search, including ICLR, ICML, and NeurIPS from 2023 to 202:8] and we pay special attention to ACL, EMNLP, and NAACL conferences. We acknowledge, however, that the rapid pace of advancements in the field means that some Torthcoming papers (that are under review or available as preprints) may not be covered. Nonetheless, this survey offers curated collection of classical and reusable implementations that serve solid foundation for future research and development.
Support for Reviewers and Rescarchers This survey intended to help reviewers and rescarchers more effectively assess the novelty of their contributions relative to prior work. After reviewing papers and evaluating the reviews of papers on OpenReview, we have observed that some claims of novelty in existing research may be inadvertently inaccurate due to the rapid pace of developments and the entanglement of
EExcluding 1CM1.2025 and NeurIPS2025, which have not yet. heen released.
4

---

Published in Transactions on Machine Learning Research (04/2025)
task novelty and technical novelty in this area. Rescarchers and reviewers from the venues specify above might have additional interests.
For Research Engineers To support practical implementation, search procedures (Section 4 are pre- sented in an Object-Oriented Programming (OOP) style, promoting modularity and ease of integration for research engineers.
Anchoring Purpose Our work serves as valuable reference in two key ways: 1) Incorporating Novel Designs with Minimal Adjustments: During the development of this survey, we seamlessly integrated emerging methods with minor modifications. For example, separated single-step simulation from path simulation in MCTS to accommodate LATS (Zhou et al.) 2024a) and decoupled value-based selection from LMPE+ or state-based evaluation to allow specialized ways to assign values, egg.. using parents' states for evaluation Koh et al. (2024). 2) Expanding with Additional Details: Our structured presentation of search control flows serves as a stable anchor for integrating such complex components. Although many of these design elements are non-trivial, our framework simplifies readers' understanding of their integration by using existing search process as guiding anchor.
1.4 Limitations
We adopt Markov Decision Process (MDP) definitions unify and compare various methods due to their comprehensive nature. However, this formalism may feel excessive for readers focused on specific frameworks tasks where transition and action definitions unnecessary. For instance, the Treo-of-Thoughe (Yao et al. 2023a approach could be more intuitively understood without relying MDP foundations.
2 Task (Re)formulation
Tasks solved by LLM-integrated search are inherited from both the "LLM" side (human language tasks) and the "search" side (structured tasks): 1) language reasoning: LLMs are naturally applied to reasoning tasks in language (Wei et al. 2022). 2) structured tasks: On the other hand, search algorithms are more conventionally utilized for structured tasks, such as web navigation, robotic navigation, gaming, and graph traversal (Russell & Norvig 2010 Sutton & Barto 2018). The convergent nature that all of them belongs sequential decision-making, c.g., reasoning often involves generating and evaluating sequences of logical steps or decisions to arrive a conclusion.
A MDP-Like Formulation To enable a clear comparison across different frameworks, this section for- mulates the tasks in Markov Decision Processes (MDPs) (S, A, T, Rt.. In addition, observations O are often considered in Partially Observable Markov Decision Processes (POMDPs) (Li et al. 2022 Zhao et al. 2023
Hu et al. 2024):
A set of states S, including the goal state 8gi
A set of observations O, where o, is the partial observations of the state s, at time step
A set of actions A, where a E A is the action on 85
Transitions T (St+1 st, az), which define the dynamics from state another after exccuting
action;
Rewards R: A rewards evaluate the "quality" of state or a trajectory towards the desired outcomes or goals. They can be delivered in two ways: outcome rewards are provided at the end of an episode to assoss the overall quality of the final state, whercas process rewards are given throughout the episode to reflect the quality of the agent's 's behavior as it progresses.
Before introducing concrete tasks in the subsections, some necessary highlights can facilitate the understand- ing:
5

---

Published in Transactions on Machine Learning Research (04/2025)
Table 2: unification of various tasks for LLM Inference via Search (LIS). A single benchmark may configured for different tasks. Therefore, the "Benchmark" column specifies each task's benchmark alongside the corresponding adapting frameworks (listed in parentheses).
Tasks
Actions
States / Ob-
Transitions
Rewards
Action
Re-
Benchmarks (Used by)
versible??
Embodied Tasks
Discrete, constrained, heterogeneous,
Discrete
Normally determinis- tic
Baefaute the achleved
1
Maybe
VirtualHome
Puig
2018
Planner
Jericho
Hauskuecht
dependent
2020
(MC-DDL)
Combinatorial Tasks
Discrete, constrained,
Discrete
Deterministic
Raetant
Maybe
Game-of-24 (Yao al.
2023a
(T TS-LL.
Wan
2021
dependent
TTS 1-3-L.20 LLM
Web tions
Naviga-
Discrete, constrained, heterogencous
Discrete, infinite
Dynamic Determinis-
Raefaule
Maybe
WebShop
Yao et al.
2022
(Agent Q. LATS)
Web
Zhou al. (Best-LLM)
2024h
Graph traversal
Discrete, Discrete, finite (com- monly)
Deterministic lifSEG
Maybe
GridMap (Meng al. (LLM-X*)
constrained, homogeneous
Reasoning
(T Open (A
Open,
Deterministic if the (Concate- nating)
GSM8K
Gobbe
al
via Concatena- tion)
thought cec- pressed known one more tokens)
until (Problem description concatenated
final results ground- truth
2021
(Q*
M
RaST MCTS*)
Hendrycks
al.
2021
(Q)
REST.
MCTS
HotpoeQA
thoughts)
Yang
ot al. 2018
CPO, vStar)
Writing
Yao et al.
2023a
(T6T)
Reasoning via Open QAs
Open, known reached
un-- until
Dynamic (Question answering then
the final results
Hotpot QA Yang et al.
2018) (nStor), GSMsK
= ground- truth
Cobbe et al 2021
(RAP)
catenating Q&&)
Reasoning (T Open via.
Open,
the Maybe known until (Coneate- final results mating); dynamic determin- istic (tool invocation)
un---
Deterministic
HotpotQA Yang et al. 2018 (LAT3)
tious and tool Invocation)
reached
ground-
Reasoning Over Knowledge Graph
Discrete, constrained, heterogeneons
Open thoughts discrete and fnite entity-relation triplets
Deterministic (Concate- nating)
the final results ground- truth
WebQSP
2016 (Think-on- Cruph, Graph 2.0)
Tool-based tasks
Discrete, constrrained, heterogeneous
Problem scription concatenated actions
Deterministic (Concate- nating)
the Maybe
GSM8K
task is com- pleted
2021
(ToiCChain
Bench
Xu et al.
2023
TooiCham
Code tion
Genera-
Open gle token)
Open, known reached (Problem description concatenated tokens)
Deterministic
E.g. pass rate of the complete program
MBPP
Austin
until
2021
LATS.
Hendrycks
2021
(GG-TD)
Goal-oriented Dialog
Discrete, con- A sequence intents,
Dynamic
if the X conversa- tional goal is achieved
Persuasion
strained [An intent)
Wang et
2019
agent/use /use utterances
CDDPZero
Tasks (this section) vs. search agents (The following sections): This section only discuss task elements that external to agents and exist independently of how agents operate learn.

---

Published in Transactions on Machine Learning Research (04/2025)
We will see in the next section how the POMDP setting fits in LMPRs and agent definitions, where the Markovian assumption is broke.
MDPs for both concrete and abstract domains: MDP settings are purely conceptual. They do not need to mirror real-world states such as sensor readings, a robot's position, or a digital image snapshot. They also do not have to replicate actual actions like a robot arm lifting an object, a self-driving car navigating interscctions, or selecting a digital advertisement. Similarly, the foodback mechanisms for reward shaping can differ from those in the real world, such as thermometer's continuous reading binary success /faccss/failure ffaluure indicator. Therefore, concrete and abstract domains:
categorize the tasks into
Concrete domains: In tasks like recycling robot, gridworld, and chess, actions and states are always naturally defined. They are always modeled as MDPs in the study of Reinforcement Learning (RI) (Sutton & Barto 2018), intelligent agents, and control theory. Commonly, physical environment or rule set defines a discrete and finite action space. And states are commonly finite and can be enumerated, e.g., all the possible configurations of chess board or the grid areas robot can travel.
Abstract domains: However, others, e.g., graph traversal and reasoning lasks, are not commonly formalized as MDPs until the emergent of LLseb agents. In particular, the MDP elements in graph traversal and reasoning tasks are not explicit. The rest of this section mainly discusses how the these tasks fit the following MDP notations, as summarized in Table 2
We highlight this to prevent readers from unnecessary confusion because some task settings seem counterintuitive.
2.1 Embodied Tasks in Text
Embodied tasks involve simulating physical interactions and spatial relationships analogous to those in the real world. In these tasks, agents must navigate through environments, manipulate objects, and perform other complex physical activities that result in observable changes. The simulated environments can range from realistic household settings (e.g., AlfWorld (Shridhar el al. 2021). VirtualHome (Puig et al. 2018)) to
realms inspired by Interactive Fiction (IF) games (e.g., Minecraft (Fan et al. 2022). Jericho (Hausknecht
et al. 2020
States: A state caplures the current physical configuration of the enviromment, detailing the posi- tions and conditions of both objects and the agent.
Actions: The action space is dynamic and varies based on the current state of the enviromment. While identifying valid actions can be part the agent's job, existing benchmarks often provide a predefined set of valid actions for each state.
Transitions: State transitions represent the physical changes occurring in the environment, which are typically discernible through common sense in dinglepplyee setting.
Default Rewards:
Rewards typically assigned when the agent reaches goal state g. The default reward function Reiefaut (s) follows binary scheme: R(s) = 1 if G (i.e., is goal state), and R(s) O otherwisc.
2.2 Combinatorial Tasks in Text
Combinatorial tasks focus on strategic reasoning and decision-makee making within abstract, rule- gole-govenee en- vironments. In these tasks, agents must explore discrete state spaces, evaluate possible moves, and plan sequences of actions to achieve desired outcome. The environments are defined by clear, deterministic rules and often involve well-known games puzzles, such as chess and the game of 24.
States: state encapsulates the current configuration of the game or puzzle. For example, chess, the state is defined by the positions of all the pieces on the board, while in the game of 24, it represents the current arrangement of numbers and operations available.

---

Published in Transactions on Machine Learning Research (04/2025)
Actions are the discrete moves operations that alter the state. In chess, these the legal moves of the pieces, and in the game of 24, they are the mathematical operations (addition, subtraction, multiplication, division) used to combine numbers.
Actions:
Transitions describe the evolution of the state following an action, adhering strictly to the game's rules. These transitions are doterministic, meaning that the same action in given state will always yield the samee new stale, as seen in the systematic progressions in chess or the arithmetic rules in the game of 24.
Transitions:
Default Rewards: Rewards are typically associated with achieving specific goals, such as winning game or solving the puzzle. For instance, in chess, a reward might be assigned upon checkmate, whereas in the game of 24, the reward is granted when the target number is correctly reached.
2.3 Web Navigation
Another type of tasks is to navigate on websites for shopping and retrieving information Zhou et al. 2024b)
States /laates/bssevvatios:: A state//bberrvtion normally web page. For example, the beginning state can be the homepage. The transition is governed by deterministic transition function. The state is not always accessible to the agent. For example, "s, may include private information such as database entries of the site" (Koh et al. 2024
Transitions occur when the agent interacts with webpage elements such as clicking links, filling forms, or selecting memu options- to move from one page (state) to another. These transitions are governed by deterministic function, meaning that specific action reliably leads to the same subsequent state, although dynamic content or session-specifie data might occasionally influence the exact presentation of the resulting page.
Transitions:
Reward: A default reward function, Rdefault, is frequently employed; for example, goal state might be defined successfully ordering desired product website.
2.4 Graph Traversal MDPs
A graph traversal problem, e.g., robotic navigation, is represented as a graph = (V, where is a set of vertices (or nodes), and S V V represents the transitions between them. However, this definition is the common task settings for uninformed and informed search. However, these algorithms integrated with LLMs can be generalized beyond this definition. This is why recent work Yao et al. 2023a) that uses these search algorithms along with LLM often uses MDP terminology, but does not include formal unification. Hence, we propose conceptual framework that views graph traversal as a simplified, deterministic form of an MDP, where actions and transitions are predefined by the graph structure. This framework can be described as follows:
States: Each node E V is state.
Actions: Actions are represented by edges E. The action space gencrally considered homogencous because the type of action uniform, such as "MOVE(arg]", where "[arg]" represents parameters like direction or target node.
Transitions: Following an edge from a node & via an action (edge) (s, E always leads to the same node 8'. Hence, the transitions T are deterministic.
Besides the default one, an estimated cost-to-go from node to goal node g G can be defined for process rewards in the MDP formulation. This is explicitly defined in A as a heuristic guiding the search
Rewards:
As best know, this conceptualization is not explicitly stated in any peer-reviewed literature.
8

---

Published in Transactions on Machine Learning Research (04/2025)
2.5 Language Reasoning in MDP
The formulations of language reasoning tasks more diverse and creative. Although not exhaustive, the following paragraphs summarize forms that are particularly used in the current study of I.M-integrated search.
Reasoning (T via Concatenation) A reasoning process can be concretized as Chain of Thoughts (CoT) T2,.. (Wei et al. 2022), each expressed as a sequence of tokens via LLM generation. Reasoning steps can evolve naturally, ranging from a single word to a full sentence (Zhang et al. 2024a). However, ensuring clear semantics for each step remains a. challenge. Alternatively, these steps can be explicitly defined. For instance, in creative writing, the first step can be specified planning, and the second step is to generate according to the plan (Yao el al. 2023b). Following previous work LLi 2024 2024a), the MDP formulation includes:
Wang et. al.
Actions: An action is a thought consisting of several tokens, i.c., 41 = Tı.
The initial state 81 is defined by the task information, c.g., a user query, a problem descrip- tion or the goal. The following states are defined as the concatenation of the following thoughts:
States:
3t = (5t-1,a1-1) = ($1, a1. ........-11))
(1)
Apparcntly, directly concatnenating open actions leads to the open state space. When the reasoning is naturally evolved, the final state 8y comes when the final thought T, or the entire chain expresses a valid response. It can be known in which step Sg is reached for deliberate reasoning steps.
Transition:
The deterministic state transition defined for reasoning tasks. The next state 8141 equal to the concatenation of s; and de.
Rewards: An outcome reward is given when the final answer matches the ground truth and fits in human preference.
Reasoning via QAs Some other works deliberately formulate an action space. given task is decomposed into soquentially dependent subtasks (actions) requiring an Execute function, which relies on LLMs to solve. In other words, LLMs can be considered as transitions. Recent work on LLM search formulates a subtask question and use LLMs to answer the question. These subtasks (i.e., actions) can be generated all once (Zhou et al., 2023) or in sequential order (Hao et al. 2023), each can be defined an action a,. is the concatenation of the task information So and all the questions already answered with their answers: question,, answwrr,........................ qu..tiuuus..n..... answer,.
Reasoning (T via Concatenation and Tool Invocations) Once tool definitions are given to LLMs. During reasoning, LLMs can generate specific tokens to invoke tools. This integration of tool invocation into reasoning is firstly proposed by ReAct Yao et al. (2023b) and recently adapted to the LIS framework (Zhou et al. 2024a). Based on the definitions for Reasoning (T via Concalenation), the following things are added:
Actions: Tool-related actions are commonly discrete and constrained. For example, when Wikipedia is used, the possible actions include search(arg), lookup(arg]. Although not always, most works on LLM tool use only include the reading-only actions, the actions are reversible.
Transitions: Duc to the change of the action space, the transitions can be cither dynamic or deterministic, depending on the tools.
States: a state now concatenates not only the LLM generation but also tool responses. More- over, LLM generation is not only about the direct thoughts for tasks but also the actions for tool invocations.
8t (81, (81,01, a1 01, .......... at 0t-1)
(2)

---

Published in Transactions on Machine Learning Research (04/2025)
Reasoning Over Knowledge Graph Before defining reasoning knowledge graph, clarify why this task is distinct from both graph traversal and reasoning under tool invocations.
Not Tool Invocation: reasoning under tool invocations, LLMs autonomously decide whether to use external tools. In contrast, knowledge graph is an integral part of the task environment on which the LLM agent operates.
Different from Graph Traversal: In typical graph traversal tasks, the graph directly models a visible or observable world. A knowledge graph, however, is carefully designed structure that captures heterogencous semantic relationships between entitics or concopts.
We now define the task of reasoning knowledge graph:
States: In graph traversal, each node v E V represents a state. In this context, the state is composed of all explored nodes (entities) and their interrelationships, which collectively inform subsequent decisions and the final outcome. Additionally, any relevant I.L.-generated knowledge that contributes these decisions is incorporated into the state.
The action space consists of exploring new relations and entities within the knowledge graph, as well generating new knowledge through LLM outputs.
Actions:
Transitions: transition deterministically concatenates the new information (e.g., discovered relation or entity) with the existing state, reflecting the edge (s, E between the current state and the new information.
Rewards: Raefauit is used by default.
2.6 Tool-Based Tasks in MDP
Unlike language reasoning under tool invocations, where tools are optionally provided and agents au- tonomously decide whether to use them, this kind of tasks inherently requires tool invocation. For example, an agent may need to clean a room using APIs designed for robotic arm or send an email using an email API.
Actions: An action is formalized using predicates and arguments, e.g., Pick Up/Applej. Since predicates can have various definitions, the action space is both discrete and heterogeneous.
The definitions of state and transition remain the same as in language reasoning (T via concatenation), while the properties of actions different,, Specifically, the initial state 81 the given task description, and subsequent states obtained by concatenating 81 with actions from previous steps, expressed in Equation
States and Transitions:
Rewards: Raefault is normally used by default.
2.7 Code Generation in MDP
This is similar language reasoning under Deterministic T via Concatenation. The only difference is that action is token in the vocabulary set of the LLM (rather than thought consisting of several tokens). Such definition is originally proposed by Zhang et al. (2023). Under their definition, "the reward of state is the pass rate of the program on the public test cases. The reward of partial program is always 0."
2.8
Dialog MDP
Previous work (ang et al. 2020) frames goal-oriented dialog as MDP, Yu et al. (2023) begin using such formulation for L.M--interrated search. The formulation demonstrated below.
10

---

Published in Transactions on Machine Learning Research (04/2025)
Actions: An action E A indicates the intent, which is predefined. For example, the intent to convince the Persuadee using reasoning and factual evidence is defined as *Logical Appeal". This is commonly termed "dialog act" (Wang et al. 2020
States: 8t is defined as the dialogue history of previous turns, containing dialog act and agent/user utterances
(a) agent
a 11 In
agent
usr
agent
agent usr 11
where up agent u are the utterances of the agent and user, respectively at the i-th turn.
Transitions: The state is updated according to stochastic responses from the user u,"" (Wang et al. 2020)
Rewards: it represents the immediate feedback of a desired conversational outcome, such as in- process, success, or failure of persuading a user to donate to a charity
2.9 Discussion
Accessibility of Action-State Transition In environments under deterministic transitions (e.g., dialog, code generation), the next state s' can be directly derived basod on the selected action. In a dynamic environment, 5' can be either sampled over the probability distribution generated from Impr Section 4 will demonstrate how this property affects search procedures.
Overhead of Using MDP Definition Although the comprehensive definition provides a unified interface to discuss LIS frameworks, it increases the overhead when applied to graph traversal tasks, since several defining characteristics of an MDP are not necessary, e.g., state transitions and explicit definitions of actions.
Why Is There No Previous Work Defining Reasoning Tasks as MDPs? Typical MDPs are often defined for decision-makee making models which can only handle the tasks whose action space is constrained and finite. However, general-purpose models like LLMs naturally deal with infinite or arand hard-to-define action space, since LLMs can infer plausible actions with world knowledge and commonsense.
Do Tasks Enable Action Undoing and State Back-Up? Some environments allow going back up earlier step after executing sequence of actions (e-g., reasoning tasks), while other tasks may not (such robotic tasks). This property is particularly important to discuss the applicability of LLM-integrated search methods. For enviromments under such property, the LIS agent can feel free to simulate future states for planning without worrying that the change of environments is irreversible. Details will be discussed in
3 LLM-Profiled Roles
Following standard reinforcement learning terminology (Sutton Barto 2018 an agent designed to solve Markov Decision Processes (MDPs) typically incorporates the following components:
Policy T(a st): Determines the action 0r to take given the current state St.
Value Function V*(s) H R: Estimates the expected return of state under policy æ.
Transition Model T(s++1 8t, 4:): Represents the dynamics of the environment, predicting the next state 8t-1 given the current state 8t and action a;-
These definitions are broadly applicable across different agent designs. In this work, we adapt them LLM-based search and focus how to profile LLMs to work as/for these agentic components.
11

---

Published in Transactions on Machine Learning Research (04/2025)
Background of LLM-Profiled Policy, Evaluator and Transition Model This section outlines the implementation of the three core components using three types of LMPRs. These roles are defined by Li (2024) as the LLM-profiled policy (Imprpolicy): evaluator (Impreval): and transition model (Impr For brevity, these notations are commonly adopted throughout this work.
While prior studies such as Spiegel et al. 2024) and Feng al. (2024) explored these LMPRs primarily in theoretical contexts and toy environments for reinforcement learning, this section extends these ideas by presenting detailed implementations in real-world tasks.
Presentation of Prompting Examples To illustrate how LLMs are configured for different LMPR roles, we provide prompting examples throughout the paper. Model outputs visually distinguished using shadow boxes for clarity. For example:
An output from LMPR
To maintain brevity, placeholders enclosed in angle brackets (e.g., <demos> for few-shot demonstrations and <task desc.> > for task descriptions) are used to represent verbal components within prompts.
Table 3: Types of L.MM-pofilled policy. Note that what really require is only de- N: sample size; T:
length of action sequence.
Type
Outputs
Example Works
Deterministic
at
Xie et al.
2023
ReAct Yao et al.
2023bb
Batch
at. Rt.o.......
Yao
2023a
2024)
Stochastic
Probability bution
Distri-
MC-DML.
Shi al.
2025
all the actions E Acxadidate
3.1 LLM-Profiled Policy (LMPP)
This section introduces three types of LMPPs. A deterministic policy maps each state directly to a specific action, while stochastic policy assigns a probability distribution over actions E Acandidates where Acandidate may be fixed or change based on the current state 8t. Lastly, a batch policy produces multiple candidato actions each time step. While various types of information be provided in the LLM prompt, the verbalized observation o, is always mandatory.
Deterministic LMPP This paragraph introduces three types of deterministic LMPPs:
Naive LMPP (ImpPnatve): An LLM is directly prompted to generate the next action Oz-
Reasoning LMPP (ImpPrassoning)) To generate ae, the LLM first produces a complete reasoning path that explains or justifics the generation of a, The reasoning path serves as an explicit interme- diate step, enhancing interpretability and illuminating the decision-makinn process for a, Finally, a, extracted and parsed.
ReAct LMPP (ImpPreact): In contrast to Imppreasoning> ImpPreaet separates the reasoning step and the action-generation step into distinct LLM inference passes. Each pass corresponds to an un- interrupted generation session. The reasoning text may include a planning path (e.g., de+1,...,ār) but only ă used for search. Another distinguishing feature is the more autonomous behavior of this policy, which does not strictly adhere to fixed reasoning-then thanaatithh---nnnggggg sequence. Instcad, it can dynamically alternate between reasoning and acting steps, such as reasoning-acting-actinn acting-acting. For example:
12

---

Published in Transactions on Machine Learning Research (04/2025)
Your task is to: put cool tomato in microwave.
think:
To solve the task, need to find tomato, then cool it with the fridge, and finally put it in the microwave. <more thoughts>>
OK.
go to countertop
<observation>>
> go to countertop
Prompting Example
The term "react" is attributed to the work of ReAct Yao et al. 2023b However, in their formula- tion, each thought is not explicitly treated as an action; instead, only lool invocations are considered actions in reasoning tasks. This distinction highlights the broader applicability of ImpPreact in our definition.
Stochastic LMPP (Impp")
Logit-based LMPP (Imppiogu): Leveraging model logits capture uncertainty is long- established technique in machine learning (e-g., logistic regression). In language models, the logits the vocabulary be converted into probability distribution
sct of verbalized actions.
Verbalized LMPP (ImpPverbalteea:: As shown by Lin et al. (0022) LLMs can "learn to express uncertainty about its own answers in natural language," enabling the probability distribution to be directly generated through prompting.
Self- celfisoonss (Impp*c): This approach involves sampling multiple trajectories from an LLM and computing self-consistency scores (Wang et al. 2023) by counting the frequency of each outcome, which is then normalized to form a probability distribution.
Batch LMPP (ImpPbatch) A batch LMPP generates multiple actions simultaneously.
1. ImpPhatch1' In this variant, inference generates multiple candidate actions in text form, with candidates separated by special token for subsequent extraction. As noted by Yao et al. (2023a) this avoids duplication in constrained action spaces, such as selecting word in crossword puzzle. By leveraging a global view of the action space, ImpPbatchl improves efficiency LLM inference and coherence tasks.
2. ImpPhatch2: This variant leverages stochastic LMPP to generate probability distribution across set of candidates. Actions are then sampled directly from this distribution.
3.2 LLM-Profiled Transition Model (LMPT)
Transition models are especially beneficial in dynamic environments, while in deterministic settings, where transitions are predictable or actions easily reversible, their utility is limited. Impr predicts outcomes according LLMs' internal knowledge. The profiling can be categorized as generating: 1) Full state: The final goal is to return full state/observant at the current step, as exemplified in Example from Hao
et al. 2023
13

---

Published in Transactions on Machine Learning Research (04/2025)
<profile information>>
ISTATE 0) I have that, the white block is clear, the cyan block is clear, <more detail> AACTION] Pick up the brown block. [CHAGEE]
The hand was empty and is now holding the brown block, the brown block was on the table and is now in the hand, and the brown block is no longer clear. [STATE 1] have that, the white block clear, the cyan block is clear, <more detail>
Prompting Example 2
2) Partial observation: The partial observation would be further processed to form the full state. One obvious lask reasoning via QAs.
Given a question, please decompose it into sub-questions. For each sub-question, please answer it in a complete sentence, ending with "The answer is". When the original question answerable, please start the subquestion with 'Now we can answer the question: <few shot demos>
Question James writes a 3-page letter 2 diffcrent friends twice week. How many pages does he write year?
Question 1.1: How many pages does he write every week?
Answer 1.1: James writes a 3-page letter to different. friends twice a week, so he writes * 2 12 pages every week. The answer is 12.
Prompting Example
3.3 LLM-Profiled Evaluator (LMPE)
LLMs can serve flexible evaluators (LMPEs) by leveraging their generative and probabilistic capabilities. We propose categorizing these evaluators along three key dimensions:
Task Formulation:
Whether the evaluation is a binary classification, multi-choice QA, a free- form judgment. influences how the LLM's output logits be interpreted. These tasks always formulated in LLMs system-level prompts.
State vs. Action vs. Episode Evaluation: This is analogous to state/action-state value func- tions in reinforcement learning. Depending on whether the evaluator assessing a static state 8; or transition (s), the LLM must parse different context inputs to provide a valid judgment. Another evaluation target is the cross-trial episode (i.e., a sequence of actions leading to terminal
state) ) SShinn et al. 2023
Shi al. 2025
Output Types: Unlike Impp or Impt, the output of an evaluator Impe can produce not only text-based outputs (contimuous text or discrete labels or free-form text) but also raw logits and self-consistency scores. This flexibility allows for nuanced scoring and confidence measurement. that can be mapped discrete classes or continuous values.
Use of Reasoning: As LMPPs, some reasoning techniques can be generalized to LMPEs.
As summarized Table 4 various works have shown that LLMs configurod under these dimensions can support diverse evaluation goals. The paragraphs below illustrate the four dimensions through concrete prompts and output examples.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Table 4: LLM-profiled evaluators Impe. The columns "V?" and "Q?" indicate whether the LMPE configuration can work state value function and action value function, respectively.
Prompting Tasks
Outputs
V?
Q?
Example Works
Impel
Binary/ /Multi-
Discrete mapped by LLM
values
RAP
Hao et al. 2023) ToT Yao
class
et al.
2023a). Koh et al.
20244
Classification
generations
LATS
Zhou et al. 2024a
Impo2
Binary/multi-
Logits of LLM genera- tions
RAP
Hao ct al. 2023
Tree-
class tion
Classifica-
BeamSearch
(Xie et al.
2023
Impe'
Multi-choice QA
Choices top-N sc- tions
Toll' Yao et al.
2023a Think-on-
Graph (Sun al.
2024
Impo4
Classification (Imu- plicit)
Logits of given contin- uation
RAP Hao et al.
2023
Impe5
Multi-choice QA
Logits of given contin- uation (choices)
x
Kadavath et al.
2022
Xie et al.
2023
Impe6
Scoring
Generated continuous scores
Think-on-Graph Sun et al.
2024
Imprpolley
Logits of policy gener- ations
RAP Hao et al.
2023 Tre--
BeamSearch (iie ct al.
2023
lepayerbalize
Episode
Fvalua-
Free-form text.
NA
NA
Reflexion Shinn et al.
2023
MC-
tion
DML Shi et al. 2025
Impr kovlyy
NA
Logits of policy gener- ations
RAP Hao et al. 2023
Tree-
BeamSearch (Xie ct al.
2023
Imprpolicy poliey &eval2
Self-consistency scores
LATS Zhou et al.
2024a
rStar
policy generations
QQI et al. 2025
Tool ToolChain
ZZhanng eb 2024
Imprpolley keval8
Consistency policy- generated steps and a candidate plan
LLM-A* Meng et
2024
Impr impppoliey &evals
NA
Q-Values based strong lmpp
Q Wang al.
2024a
ImpPPeeanittoonkeealll NA
Logits of Impt genera- tions
x
RAP Hao et al.
2023
ImpFtransttionncens
Logits of Impt genera- tions
Three types are commonly used for evaluation. 1) Binary/Multi-clan Classifi- cation: As shown below, a prompt can explicitly request a binary judgment, e.g, yes/no or failure/success:
Task Formulations
<prompt>>
Status: "failure"
Prompting Example 4
In some cascs, more fine-grained judgments required with multiple labels. For example, the "status" tag is defined for LMPE to indicate partial successes in Koh el al. (024):
<prompt>>
15

---

Published in Transactions on Machine Learning Research (04/2025)
Status: "failure"
On the right track to success: "yes"
Prompling Example. 5
This can be considered multi-class classification, where "yes" yields an intermediate class. A more direct multi-class classification is specified in the example below, where the prompt assesses whether given set of numbers can reach 24:
Evaluate if given numbers can reach 24 (sure Saure/ikely/impossbbbee
10 14
10 + 14 24 sure
1 3 3
1 1*3*3== 31+ * 3 12
3 all too small impossible
Prompting Example
2) Multi-choice QA: This is often advantagcous when directly scoring an action action/state /state is difficult to compute in contrast comparing multiple candidates. For example, it is difficult judge whether give passage is coherent, while it is easy to judge whether Passage A more less coherent than Passage B. Another way is to implicitly compare different solutions via voting through self-consistency scores of Impp, which belongs to the next formulation type. 3) Scoring: A continuous score is given for each candidate option. Example 7 demonstrates how to prompt LLMs for scoring in the task of reasoning over a knowledge graph
Please rate thee contribution of the relations on a scale from 0 to 1 (the sum of the scores of the relations is 1)
Q: <u<ury
Topic Entity: <Toppcc Entity>
Relations: <list of relations>
Prompting Fxample
4) No Explicit Evaluator Definition: Evaluation can be inferred from the Impp's generative process itself. In such cases, separate system-level prompt is required for task formulation. Likewise, Impt be used for evaluation. This LLM-based evaluation will be detailed from the perspective of output types.
State vs. State-Action Function its input to produce a judgment:
1) State- Evaluator: A state-based evaluator accepts as
discrete judge = Impe(s:)
(4)
Example of the example. 2) Stato-Action Evaluator: the evaluator assesses whether taking action a, is appropriate at the current state 8c:
discrete judge = Impo(s;; o:)
(5)
This sctup is excmplified in Example 10 where the new sub-question (a,)'s usefulness depends on the prior state (st). Below is another example of BlocksWorke (Slaney & Thiebaux 2001
[TATE
As initial conditions I have that, the blue block is clear, the orange block is in the hand,
16

---

Published in Transactions on Machine Learning Research (04/2025)
the red block is clear, the hand is holding the orange block, the red block is top of the yellow block, the blue block is on the table, and the yellow block is on the table. My goal is to have have that the red block is on top of the yellow block and the orange block is on top of the blue block. [ACTION] stack the orange block on top of the red block
[EVALUATION]
bad
Prompling Example 8
The prompting format is adapted from Hao et al. 2023
Outputs Finally, the putp of Impe can take one of several forms, depending on how we wish to interpret or utilize the evaluator's opinion:
1. Mapping Impe generation to discrete values: For instance, "impossible" or "Yes" may be mapped to numeric scores (0 or 1) in Quotes and 10
2. Using logits of Impe: The probability of generating a specific token (c.g., "impossible") can serve as the confidence score.
3. Using logits of given continuations: Rather than having the LLM generate the evaluation tokens, one can provide the exact sequence to be evaluated (c.g., "good" in Quote g or "(A) good"). The log probability of each token is then summed to indicate how well (i.e., how confidently) the model "accepts" that evaluation in the given context. A higher cumulative log-likelihood suggests that the LLM finds the provided evaluation more plausible. Moreover, multiple predefined options (e.g., "(A) Correct " vs. "(B) Incorrect") can be separately fed as contimuations. The log probabilitios of
each option can then be compared as sell-evaluation scores (Xie et al. 2023 Kadavath el. al., 2022)
Using logits from Impp or Impt: Alternatively, the evaluation can be derived from the policy or transition model'ss token probabilities. This method can avoid additional inference steps by reusing existing logits. However, the fundamental flaw is that when multiple plausible answers exist, individual logits can be low even if overall confidence in the correct answer set is high (Lin et al. 2022).
5. Using self-consistency scores based on Impp or Impt:
By sampling multiple trajectories (or states) from an LMPP (or LMPT) via self-consistency (Wang et al. 2023), one can gauge confidence via how often a particular action (or state) appears. More frequent outcomes can be assumed more likely (or better). One challenge is how to distinguish different outcomes. For example, ZZhuan al.) (2024) fine-tune natural language inference (NLI) model to distinguish the generated actions. Note that the logits from the LMPP or the self-consistency scores based on the LMPP ultimately converges to the probability distribution of stochastic LMPP.
6. Comparing consistency of Impp-generated steps and candidate states: The actions /plan generated by actions can be compared to the candidate for evaluation. This is suitable for lasks with limited successor states.
Comparing Consistency of Impp-Generated Steps and Candidate States: The actions plans produced by the policy can be compared against candidate states to assess consistency. This approach is particularly suitable for tasks with limited number of successor states, e.g., sovling a maze (Meng et al. 2024).
Using a Stronger Impp as a Proxy Optimal Policy to Approximate Q-Valuss: When rewards are only obtained at the terminal state, the Q-value can be approximated by discounting the rewards along the path. This approach assumes that all subsequent actions are optimal, which necessitates the of more robust Impp as proxy for the optimal policy.
17

---

Published in Transactions on Machine Learning Research (04/2025)
Use of Reasoning Similar to ImpPressouing' reasoning process can be required before generating the final judgment. This reasoning process provides a logical justification to augment. the evaluation. For example:
<
<prompt>
Thoughts:
<your thoughts and reasoning process> Status: "failure"
Prompting Example
3.4
Discussion
Inference Cost of Impp In practice, the overall computational cost follows the pattern
ImpPreact ImpPressoning
ImpP
The gap between ImpPreasoning and ImpPusive arises from the additional output tokens produced for reasoning, More importantly, when commercial API used, ImpPreact exhibits even higher cost. because each seporale reasoning action-generation pass is effectively stateless with respect to the cached K-V pairs from previous passes, thereby preventing token-reuse optimizations.
Applicability of ImpPreact- A central requirement for ReAct-style prompting (ImpPreact) is the avail- ability of step-wise observations after each action. This imposes two prevalent scenarios:
Tasks relying on simulators: When direct interaction with the real environment is impractical (e.g,, actions on tasks are irreversible), simulator can be substituted to generate the observation following each action. For instance, LLM-based simulator (Impt) might commonsense knowl- edge to model environmental responses (e.g., turning water tap in sealed sink). However, such simulators are unsuitable for tasks involving external or private data-like querying proprictary databases or relrieving up-lo-dale information since an LLM's internal knowledge typically cannot replicate these data sources.
2. Action-reversible tasks. Certain problems can be retried or backtracked, allowing the agent to iteratively act, observe, and refine its actions, as discussed in Section 2 In Section 5 for exam- ple, LLM-based search frameworks such as LATS (Zhou et al.] (024a) leverage this property when interacting with real environments across multiple search steps perform monte-carlo simulation.
Risk of Impe Although Impe can effectively evaluate state or action quality, two challenges stand out:
1. Mediocre discrimination abilities: As shown by Chen et al.
2024b/ using logits as dense re- wards (e.g., in Impr policykvaal or Imprrrausition&eew/ can reveal that many open-source LLMs struggle to reliably distinguish "good" from "bad" examples 0
2. In-Context Reward Hacking (ICRH): According to Pan et al. (0224). an LLM evaluator (Impe) may attempt to "cxplain away" negative feedback by globally altering its reasoning and actions, polentially violating constraints. For example, fix an CRUPPICIENT BLANCEEEAA might suggest unauthorized money transfers from other accounts, thus compromising safety or policy compliance.
the LLM
Not All Generation with "Reasoning" is Truly Augmented. By design, LLMs generate tokens in an auto-regressive manner, meaning earlier tokens are not influenced by later ungenerated tokens. Hence, although reasoning tokens after actions (or evaluation) can make the model outputs more interpretable, they do not always alter subsequent decisions or evaluations. Tn Xie et al. (023), , for instance, a chain of thoughts
at 0z+1 ÜT
3GPT-4 turbo was the advanced model the time of evaluation.
18

---

Published in Transactions on Machine Learning Research (04/2025)
is produced, where "4+1:-..,,0 &r are "unrecorded" actions. Crucially, a, is unaffected by any future à tokens, making this effectively naive policy rather than a true reasoning-augmentee approach.
Similarly, consider the evaluator in Example 10:
Given question and some sub-questions, determine whether the last sub-question is useful to answer the question. Output 'Yes' or 'No', and reason. Question 1: Four years ago, Kody was only half as old as Mohamed. Tf Mohamed is currently twice as 30 years old, how old is Kody?
Question 1.1: How old is Mohamed?
Question 1.2: How old was Mohamed four years ago?
New question 1.3: How old was Kody four years ago? Is the new question useful?
Yes. We need the answer to calculate how old is Kody now.
Prompling Ezample 10
Although the model's output includes a short "reason," that intermediate reasoning does not necessarily inform the generation of 'Yes' 'No'.
Table 5: Examples of combining LLM-Profiled Evaluators with heuristics. ||s = 88 indicate whether the agent reaches the goal state at s.
Task
Value
Reasoning- QA in RAP (Hao et al. 2023)
Impel
Game (Blockworld) in RAP Hao et al.
2023
Imped + Impe2 + ||s = 8yll (weights ig- nored)
Graph traversal in LLM-A* (Meng et al.
2024
Euclidean distance to the next state Ilme Impe5 + Impr policy&evall
Reasoning in Xie et al. (2023
Reasoning- QA/ Code Gen/Web Nav. in LATS Impe + Impr Inpppalicykeval2 Zhou et al. 2024a)
4 Search Procedures
This section presents the reusable search procedures applied across various frameworks, including both non- LMPR-specific and LMPR-based procedures. Unlike Scction 3 which focused on configuring LMPRs, here we demonstrate how these LMPRs integrated into the operational processes. However, some content may overlap slightly for coherence. Table 6 summarizes the dependencies between these search procedures and the LMPR components.
Integrating States, Action, and Rewards In this section, we shift our focus to search and clarify how the fundamental search "node" is defined with respect to states and actions. Some methods (e.g., ToT (Yao et al. 2023a)) treat a node as a particular state in a search tree, with transitions determined by the actions taken. To ensure generality, we unify states, actions, and even their estimated values (or rewards) single node structure (o.g., RAP (Hao et al.) 2023)), facilitating partial expansions or multi- step lookahead. To align with object-oriented design, we represent node as with attributes n.action, n.state, n.parent, and v.val. representing the action, state, parent node, and value, respectively.
Search Nodes:
19

---

Published in Transactions on Machine Learning Research (04/2025)
Table 6: Overview dependencies search procedures. Sampl.: Sampling; Exp.: Expansion; Eval.:
Evaluation; Sel.: Selection; Sim.: Simulation; Backprop.: Backpropagation.
(a) Dependency of first-order procedures on LMPRs.
LMPP
LMPE
LMPT
LMPP Sampl.
X
LMPE+ Eval.
X
J
X
LMPT Sim.
X
X
Multi-Choic LMPE Sel.
X
V
X
Single-Step UCT Sel.
X
X
X
Single-Step PUCT Sel.
maybe
X
Exhaustive Action Retricval
X
X
X
(b) Dependency of higher-order procedures LMPR-based, first-order procedures.
LMPP Sampl.
LMPE+ Eval.
LMPT Sim.
Value-Based Sel.
maybe
LMPP Exp.
X
maybe
Path Sim.
maybe
maybe
MCTS Sel.
X
X
X
MCTS Backprop.
4.1 First-Order Procedures
First-order procedures operate independently, without relying other procedures. They serve the foun- dational components upon which more complex procedures are built, ensuring a modular and scalable frame- work for LLM-based search operations. The first three are based on LLM-Profiled Policy (LMPP), evaluator (LMPE), and transition model (LMPT), respectively, while others not necessarily depend on LMPRs.
LMPP Sampling The sampling procedure involves generating multiple actions (assuming actions) for given stale &t. Generally, there are two approaches sampling actions: one based on generaling actions sequentially using the single-action policy (lmpp), and another based on generating all actions simultaneously using the batch policy (ImpPbateh). These approaches detailed in Procedures and 2 respectively.
Procedure LMPP Sampling: Sample Actions One at Time
procedure SAMPLE, LMPP_ _ONE_ AT_ A PAsss(ss N)
2: ar 1e++) (
3: for iE N)) do
4: a, ~ Impp (a st)
a: ta [a:]
6: end for
return a;
8: end procedure
Procedure 2 LMPP Sampling: Sample All Actions at Once
1: procedure SAMPLE LMPP ALL AT ONCEE(s,, N)
2: a, ImpPbateb (a st, N)
3: return a,
end procedure
20

---

Published in Transactions on Machine Learning Research (04/2025)
LMPE+ Evaluation LMPEs can be used to estimate the value (or reward) of state. The evaluator's output-whether whether in textual numerical form-can then be combined with rule-based heuristics to refine the overall assessment. For instance, Table 5 illustrates how numeric outputs from LMPEs are incorporated into a hcuristic that balances both LLM-based scoring and domain-specific constraints. Such integrated approaches are particularly relevant. when neither pure heuristic nor pure LLM-based evaluation alone is sufficient for robust decision-making. Based on the input, the procedure can be defined as EvAL for taking state input and EVAL for taking both state and an action as input.
Multi-Choice LMPE Selection Impe5 (an LLM profiled for multiple-choice tasks) can be leveraged for top-k selection to directly select K nodes.
Procedure 3 Topk Selection via Impe5
procedure TorK SELECT LMC_((,MMMM[)N)
2: + [n.action n E ]
b Extract actions from each node in Select the top & actions from A b Return nodes corresponding to the selected actions
A" Impe5(A,
4: N + {m E N n.action E A"}
return N*
6: end procedure
Single-Step UCT Selection The objective of Upper Confidence Tree (UCT) selection choose an action that balances exploitation and exploration. This is captured by the UCT formula:
In N(s) UCT = Q(s,a) + ev N(c(s,a))
(6)
where e is constant controlling exploration, N(s) is the number of times state has been visited, and N(s. a) is the number of times action a has been selected under A related variant, Predictor Upper Confidence Tree (PUCT), incorporates the prior probability P(s.a) into the exploration term to further guide the action selection. P(s,a) can be implemented by a stochastic LMPP.
(s)
PUCT(s, = (s, ((
(8,a)
P(s, a) is normally a domain-specific predictor. Based on the two estimates, the procedure is just to iterate over the given actions A, along with their values Q, and extract the one with the highest value, as summarized in Procedure
Procedure Sinple-Step UCT Selection
procedure SECT__SELET((_,,_ A)
2: a = arg m [UCT(s,
end procedure
4: procedure PUCT SIICT_SELEC(S,,. A)
arg maxaed (PU 6: end procedure
LMPT Simulation This procedure is straightforward: given the current state s, and action a,, the LMPT directly outputs the next state 8t-1- Unlike LMPP sampling (which may loop through multiple actions) or LMPE+ Evaluation (which may incorporate additional heuristies), no further processing or components are involved.
Exhaustive Action Retricval When the action space small and well-defined (o.g., in BlockWorld), all possible actions can be retrieved exhanstively. This procedure is primarily used facilitate the subsequent expansion simulation steps.
21

---

Published in Transactions on Machine Learning Research (04/2025)
4.2 Higher-Orde Order Procedures
Value- BaseeBBaedd Selection The first type is top-k selection. The top h states or actions are picked from a large pool of candidates based their estimated values. A stato-value function V(s') action-value function (s) is used to generate values. Commonly, they are implemented by LMPE+ evaluation. The detail is illustrated in Procedures 5
Procedure 5 Value-Based TopK Selection
1: procedure ToPK BerK__SSLECT([] k, ValueFunc = NA) for each node n' E N" do if ValueFunc & NA and n'.va is uninitialized then n'val + ValueFunc(r''s state)
3:
5: end if
6: end for
7:
N argtopa ( va'vll In' E E
return N²
9:
end procedure
Once = 1, the arg topx vn/.val | n' E N'} reduces to arg e n' val. Note that the if statement for value assignment also allows specializod ways to assign values without necessarily relying on n' statte This is particularly prepared for Carlo Tree Search (MCTS), where Q values are accunulated during backpropagation.
Another type is threshold-based selection. Here, the procedure repeatedly samples one action from the current node's state, simulates the new state, and evaluates its value. If the value surpasses a threshold 0, the procedure returns the newly created node; otherwise, contimues sampling.
Procedure 6 Value-Based Threshold Selection
procedure ThnusHOLLSSHLRCCT....
2: while true do
3:
< Sample Actioennnttiontssttt a' Simulate(n.state,d)) a)
4:
5:
ValueFunc(s")
6:
if then
Value exceeds threshold; accept this node
7:
Instantiate a new node n' state s-s' n' n'.action <- n' +- return n'
9:
11:
end
D Otherwise, continue sampling another action
13: end while
end procedure
LMPP Expansion This expansion procedure adds one more child nodes under the given leaf node(s), typically visualized at the next depth level in tree search. The procedure is based the following components:
LMPP Sampling: This step provides the n.action attribute for each node, while leaving n.state and n.val uninitialized.
Simulating States Based on Sampled Actions: To enable further expansion, the node's state (n.state) must be generated. This can be accomplished via simulators (e.g., using LMPT simulation), direct action execution, hard-coded methods (e.g., simply concatenating actions).
22

---

Published in Transactions on Machine Learning Research (04/2025)
3. (Optional) Expanding Multiple Nodes Simultancously: In many search strategies (such as beam search with beam size greater than or breadth-first search), multiple leaf nodes are expanded concurrently.
A general form of the expansion procedure is specified in Procedure
Procedure 7 Expansion
1: procedure EXPAND LMPP(N.)
2: Nr+1 +- 0
3: for each node nu E N, do
A. SAMPLE LMPP(n..tate,,
5:
for each action as E Ag do
node T4+1 with ne+1 actton dg Statstate + SIMULATE(M:,state,, at)
Instantiate
7:
No+1 + No
9: end for
end for
11: return No+1
12:
end procedure
Here, SAMPLE LMPP refers Procodure 1 or Procedure 2 The total number of No+1 equals the product of the number of nodes in N₁ and the number of actions & sampled per node.
Path Simulation
Sampling: At each step, actions Acandidate are sampled from the current state using either LMPP sampling or random sampling method or uniform sampling (Shi et al. 2025). We denote by M the size of Acandidate in this paragraph. After sampling, there are different scenarios: Tn the standard MCTS framework (Sutton & Barto 2018), basic policy is used to select an action random during each simulation step. Additionally, LMPP can be employed to roll out path until either a goal state or a terminal state encountered. We refer to these two approaches as Greedy- Random and Greedy-LMPP, respectively, noting that more sophisticated implementations exist. Evaluste-SSlledt-rrnsi (EST) or evaluations and transition, while the latter requires M transitions and M evaluations.
(TES). The former requires M
Evaluate-SSleed-TTanss (EST): 1) Evaluate: reward model (RM) is instantiated by LMPE+ evaluation to evaluate M pairs (st, where a Acandidate- The generated reward is denoted as r. Afterwards, a function named createNode initializes M nodes with each St, a, and r for node attributes:
,state, .action, amd .vl.
SELECT is then applied with only the highest-valuce node preserved (i.c., k 1). Finally, the next state 8141 is generated by Transition Model (TM). This model can be implemented in one of three ways: through LMPT simulation, by using domain-specific simulators, or by directly executing the selected action in the environment to obtain the following state (or observation). For brevity, we refer to these implementations as TM-LMPT, TM-Sim, and TM-Env, respectively.
2) Seleet:
3) Transit:
Trausit-Evaluate-SSke (TES): 1) Transit: The Transition Model (TM) is applied to e
Acandidate-
2) Evaluate: The reward model (RM) is instantiated evaluate cach 8t+1. generating reward The function createNode be applied with 8t, 8141, a, and corresponding to node altributes: .tate, -parent, aaction, .val.
3) Select: ToPK_ SELECT is then applied with only the highest-valued node preserved (i.e., k = 1).
Procedure g demonstrates general path simulation process.
23

---

Published in Transactions on Machine Learning Research (04/2025)
Procedure 8 Path Simulation
procedure SIMULATEF(Re: RM, heuristic NA)
2: path +- (
while st.ttate is terminal do
4:
$: R2..tttte
A SAMPLE (cttoo(
6:
if heuristic == NA then
b. Random action sampling (M=1)
7:
8i:1 +- A)
8:
end if
9:
if heuristic == eval first then
b Evalnate-SSlect- Transit.
10:
Neew [createNode(sr, RM(ss, a Acanidate))
11:
n + ToPK SELECT(NNew:)
s1+1 TM( action)) (action))))))))
13:
end if
if heuristic transit first then
Transit-Evaluate Evaluate-Seledt
15:
Nnew + (createNode(ss RM(ss, o), TM(st, | Acandidate
TorK SELECT(NNeW,,
17:
end if path + path
19:
nt.state si41
20:
end while
21:
return path
22:
end procedure
MCTS Selection However, during MCTS for planning, before going to the expansion phase, Procedure 4
(One-slep UCT Selection) should be used multiple times to traverse from so to a leaf node Steaf-
MCTS Backpropagation Value Update After each simulation returns a reward т, update the Q
value as:
r Qold Count
Quew
(8)
Count
r, depending on the task, can be a reward at the terminal state. In some cases,it can be an aggregated one, if cach simulation step yiclds reward. Specifically, rewards r, are discountod by y, then the final sample reward for backpropagation is:
T-1
r= G = Σ TT.
E=
In many implementations (e.g,, RAP Hao et al. 2023 ), the step-wise rewards are obtained via LMPE+ or a heuristic evaluation during path simulation. These rewards from simulated nodes are then employed update the Q values for non-simulated nodes, including the leaf nodes and those
above.
Qold are the previous Q-value.
Countnew is the total visit count after the current update.
During some implementations Hao et al. 2023 each reward Reum propagating from the terminal node can be stored in list R..m and average them when used. The procedure of value estimate, as summarized in Table 5] provides the initialized values for new actions or resulting states.
MCTS Backpropagation Visit Update Except for the estimated value Q(s, a), the backpropagation also updates the visit count for every state on the path from the root the leaf and cach edge (s, a) along that path, denoted as Count (s:) and Count (st, Q411), respectively. The increase in Count(s, a) (the action- level visit count) reduces the exploration bonus for in future selections, thus making (s slightly less
24

---

Published in Transactions on Machine Learning Research (04/2025)
likely to be chosen purely for exploration next time, assuming the same lower estimated value. Assuming Count (8t: 0t++1 > Count (s++1) in some deterministic environments, only Count (8++1) is tracked. For the same reason, Q values can be attached as an attribute of the state node. An example is the implementation of RAP (Hao ct al. 2023
Table 7: search-based frameworks for LLM inference. We use "*" to indicate workshop publication. EAR means Exhaustive Action Retrieval. Sel. indicates selection methods used select from multiple candidate actions/nodes to create branches in tree, which can be UCT PUCT, Multi-choice LMPE, Value- based TopK (V-TopK), and threshold selection. Many MCTS-specific procedures are excluded, except for path simulation (Sim.) to distinguish three types of Transition Models (TMs) and processes (Proc.).
Resemble
Expansion
LMPE+
Sel.
Sim.
Published
Eval.
Date
LMPP Exp.
EAR
TM
Proc.
Beam- Beam-LLMM
Xie
Beam Search
V-Topk
May 2023
et al.
2023
(NIPS2023)
Path Finder
Beam
X
X
V-TopK
x
Dec (NeuiIPS2023*)
2023
(Golovneva
et al.
Search
2028)
Think-on-Grapp
Beam
Multi-Choice
Jul 2023
Sun et al 2021
Search
LMPE
(ICLR2024)
Think-on- Graph
2.0
Beam
x
Multi-Choice
Jul 2024
Ma et 2025
Search
LMPE
(ICLR2025)
ToT
Yao et al
BFS
V-TopK for BFS; Threshold
May 2023
(B for
(NIPS2023)
Breath):
for DFS
DFS
B Koh el
BFS
X
V-TopK
Jul 2024
2021
(B
Beat)
LLM-A
Meng
A
V-TopK
Jun
2021
al.
2024
(EMNLP2024)
Q+
Wang et al
A
X
optional
V-TopK
X
X
Jun 2024
20248
TooIChain Zhuang
A
V-TopK
Oct
2023
al.
2024
(ICLR2024)
RAP
Hao
MCTS
UCT
LMPT
EST
May
2023
2023
(EMNL.20023)
LATS
Zhou
MCTS
UCT
Env
TES
Oct
2023
2024a
(ICM1.2024)
LLM-MMTS
Z Zhao
MCTS
PUCT
Simulator
Greedy
May
2023
2023
(NTPS2023)
rStar
Q
al.
MCTS
UCT
LMPT
Greedy
Aug
2024
2025
(ICLR2002)
MC-DML
Shi
MCTS
PUCT
Simulator /Env
Greedy
2025:
para
5.6
PG-TD
hang
PUCT
Mar
2023
<t al.
2023
MCTS
(ICLR2023)
PERO
Yu
PUCT
X
X
Oct 2023
MCTS
(EMNLP2003))
TS-LLM
Wan
a
UCT
Sep
2023
al.
2024
MCTS
(ICML2024)
RGST-MCTS
UCT
X
X
Jun
2024
Zhang
al
MCTS
(NIPS2024)
2024m
httpp:://giii httph///htoooaaiiicrrrrreeeoooer
multimodal
fine-tuning
25

---

Published in Transactions on Machine Learning Research (04/2025)
5 Frameworks Based on Search Algorithms
This section summarizes how different frameworks utilize scarch algorithms, leveraging the LMPRs and search procedures introduced in Table 7 Note that, some MCTS-specific procedures (e.g., MCTS selection, and MCTS backpropagation) are not elaborated in the table. UCT selection is highlighted to distinguish between PUCT and UCT variants; simulation is included to clarify whether LMPT or environment- based simulation or simulator is used. Below, we discuss perspectives that are not fully captured in Table
5.1 Beam Search
Beam-LLM ( et al. 2023 and PathFinder (Golovneva et al. 2023 adapt beam search for reasoning via concatenation, while Think-on-Graph (Sun al. 2024) and Think-on-Grapi 2.0 (Ma et al. 2025) are applied for reasoning over knowledge graph. Generally, Expansion and TopK-Based Selection always alternate itcratively until reaching terminal state.
Beam- Deam-LLM Xie et al. 2023
LMPP Expansion: Each set of beam nodes N₂ is passed the LMPP expansion proce- dure. Internally, SAMPLE LMPP calls either SAMPLE ACTIONS ONE Ar A PASS SAM- PLE AATTION_BBATTTIT
while SIMULATE can be a simple concatenation transition: each node ne E N₂ has its parent state n4-parent expressed tion assigned to ncaccion,, and the new node's state (nt.state) as "0.....,411..4 The resulting set of expanded nodes is denoted N, sample
sequence of actions (01,...,44 Q-11), an ac-
TopK-Based Selection: From N value-based selection procedure is applied to pick the top-k nodes (the beam size). This subset is returned as N₁. Specifically, it uses a value function implemented by Impe5 + Impr pollcy
PathFinder (Golovneva et al., 2023) This framework also applies LMPP Expansion and Value- Based TopK Selection iteratively. However, it computes a summed similarity score as the value for each candidate node, comparing its state with those of other beams ssample The similarity function can be as simple as n-gram overlap.
Think-on-Graph (Sun et al., 2024) In the graph traversal tasks described in Scction 2 the search space is derived directly from explicit task specifications. In contrast, when searching over knowledge graph, the search space is constructed from the graph itself.
Step Entity Initialization: An LLM prompted twice to extract the topic entities in the question, and select the top-K entities (Procedure 3), where K is the beam size. The resulting entities E form the initial paths.
Step 2: Expansion via SPARQL Queries for Candidate Relations: Unlike previous two frameworks, LMPP expansion and sampling are not necessary because neighboring nodes Ncandidate can be identified via simple SPARQL queries, along with candidate relations, i.e., Exhaustive Action Retricval is applied. The relation set can be denoted as Reatity; where topic E & entity/n (tate-ttte.tail
E N.-1). The queries are run for each tail entity E E,-1 to get candidate relations. The size of ε equals to beam size B.
Step 3: TopK Selection from Candidate Relations: Procedure the top K relations from candidates for each entity E Note that both K here is not necessarily the beam size B B divided by K, since the final path will be formed after the following entity expansion and selection phases.
3 is applied to directly select
Step Expansion via SPARQL Queries for Candidate Entities: Candidate entities are selected via SPARQL queries for each selected relations in the last step.
26

---

Published in Transactions on Machine Learning Research (04/2025)
Step 5: TopK Selection from Candidate Entities: To finish each triple tailed by the K relations selected above.Impet would be used to score each triple regarding their contributions to solve the given question. This defines ValueFunc in Procedure 5 Note that the & here is the beam size.
Step 6: LLM Reasoning for Terminal States: At the end of each iteration, the LLM is prompted to judge whether terminal state is reached, where the knowledge is enough to reach the final answer.
Think-on-Graph 2.0 (Ma et al., 2025) Think-on-Grain Granhh 2.0 (Ma et al. 2025 differs from Think-on- Graph in the following perspectives.
Entity Initialization: The initial entities &g are initialized and linked to the knowledge graph via an entity linking method.
Context Retrieval: A dense retrieval model (DRM) is used to retrieve context with &n as input.
LLM Reasoning for Terminal States: Same as Step 6 in Think-on-Graph.
Relation Identification: This basically identical Step 2-3 in Think-on-Graph. One differ-
ence in Step that Procedure and the LMPE in Step will evaluate the candidate relations of all the entities EL1 in one LLM inference.
Entity Identification:
This corresponds Step 4-5 in Think-on-Graphe Step still locates potential
entities knowledge graph F The main difference is that the the pruning process is based context retrieval process over unstructured documents.
LLM Reasoning for Terminal States: Similar as Step The only difference is that the retrieved context for each entity is added for prompting.
5.2 Breadth-First Search
Tree-of-Thoughts (ToT) (Yao et al., 2023a)
Similar beam search, breadth-first search (BFS) is performed by iteratively applying LMPP Expansion and TopK Sclection.
key difference that, BFS, all nodes at depth undergo the same number of actions before expanding further levels. This enforces uniform depths across expansions.
5.3 Depth-First Search
Treo-of-Thoughts (ToT) (Yao et al., 2023a Yao al. (2023a) also apply depth-first search (DFS) for LLM inference, relying the LMPP Expansion and Threshold-Basee Selection. Key points include:
Threshold Selection: One action (node) is sampled at time, but is not compared with other nodes. Instead, once its value is evaluated by whether it surpasses threshold, that path is followed to its conclusion.
LMPE Evaluation for Deadend: The system uses deadend judgment to halt exploration of unpromising paths, which can be considered as another LMPE evaluation.
Backtracking: Upon reaching a deadend, the system reverts to an earlier node and continues exploring other previously expanded but untried branches.
Path Maintenance: Because of backtracking, the framework must track partial paths, whereas BFS or beam search only needs maintain the selected nodes each depth.
Forr Step2, they explicitly specify SPARQL implementations. 6still, they do explicitly specify SPARQL implementations.
27

---

Published in Transactions on Machine Learning Research (04/2025)
5.4 Best-Firss First Search
Best-first search typically uses heuristic function h(s) to estimate how promising a state will reach the
goal.
Best-LLM Koh et al., 2024)
Uses LMPP Expansion for the selected node the initial root node, where actions executed
in the environment (web interface) to simulate the next states. The generated nodes are saved in N.
Employs TOPK_SELECT SELECT (k=1) through LMPE+ evaluation on each node in saved nodes n e N. The node value val is derived from evaluating its parent's state.
Continues until either the search tree reaches a specified budget or the state value exceeds a threshold
5.5 A*
A* is similar to best-first search but augments the heuristic h(s) with the accumulated cost/ut /uttuitttyyy g(s) to reach a node from the start. The evaluation function
f(s,) = g(xx) + Ah(s;)
(9)
where À balances the two terms. Table summarizes how two frameworks implement this formula differently:
Table 8: LMPE+ Evaluation for LLM-A* and Q*. dist(..-) represents the actual distance between two points, while ||. denotes the Euclidean norm. 80, 8n, 8g. 811m represent. the initial, current, neighbor, goal, LMPP-gene geeerrreeee states, respectively.
(())
M(())
Use of LMPE
Agg
R(s)/Cost(s) dist(so.*n)
LLM-A*
|| -gll + || 8tmml
Impr polley (for h(s))
Meng et al.
2024
Q+
min max Σ Last
Human feedback, ground-truth, rules, LLM logits
maxa; E.A Q" (st, at)
Impr kowley (for h(s))
Waan et al
2024a
TooIChain
Σ
Self-consistency scores, Longest Common Sub- sequence scores
Consistency scores,
Impr poltcy &ceval2 (for g(s)}, Impr polley
Zhuang et al.
relative position scores
2024
(for h(s))
LLM-A* (Meng et al. 2024
Designed for path-finding tasks (e.g., mazes).
g(st:: Computed incrementally the path cost from so to st. Formally,
g(s)) Σ Cost(s:).
(10)
h(s) under LMPE+ evaluation: The main modification beyond the typical A is to integrate a LMPE the h(s). Specifically, imprpolieydee (see Table 4 is applied to evaluate the Euclidean distance from s, back the recently visited Summ E Impp, along with the typical Euclidean distance between 8, (expanded neighbour node) and 8g-
28

---

Published in Transactions on Machine Learning Research (04/2025)
Q*
WWag et al. 2024a
Targets reasoning and code-generation lasks.
g(s)): Aggregates rewards via
((s)) Agg (R(s),,...... R(s)))
(11)
where Agg {min, max, E, Last). Under this definition, R (+) in g(*r) can be calculated as human feodback, ground-truth, rules or LMPE+ evaluation, depending on tasks.
h(s) optionally under LMPE+ evaluation: It initialized as the optimal Q-value of 8 over all the possible actions:
max Q" (st, at) o,E.A
(12)
Optionally, polpyyyyeyeevall introduces stronger LMPP to approximate optimal policy.
ToolChain
(Zhuang et al. 2024
Designed for tool- based tasks but can be generalized to language reasoning tasks (T via concatena- tion).
(st): Aggregated from two terms:
1. Self-consistency scores: Impr policy is used to calculate self-consistency scores, normal- ized by the mumber distinct actions.
2. Longest Common Subsequence (LCS) scores: The LCS score between the current gen- erated path and each completed path in the memory is computed and normalized by the length of the shorter path (m or st). Among the scores obtained for each memory path, only the maximum score is used for (8t).
h(s)): Also aggregated from two terms:
1. Consistency scores based on Imprpolicykeeall.
2. Relative position scores: Similar to the LCS scores in g(s;), this metric also based on memory. computes the average relative position a candidate action appearing in memory examples.
5.6 Monte Carlo Tree Search
Monte Carlo Tree Search typically involves MCTS Selection, expansion (LMPP Expansion or Exhaus- tive Action Retrieval), Path Simulation, and MCTS Backpropagation, including both value and visit update. Most frameworks under review adhere these steps, except where noted in the highlights that follow.
The details of each framework are specified in Table 7 Note that ReST-MCTS* (Zhang et al. 2024a and AiphaZero-Like Tree Search (Wan et al. 2024) feature a search process that is entangled with LLM fino-tuning. In contrast, we docouple the integration of training from the MCTS search, with the training component detailed in Section 7.2
Solution Selection After MCTS completes its allotted iterations (or reaches its time/resouree limit), a tree left where each child of the root has associated statistics. The standard practice is to pick the move corresponding to the child node with the highest visit count. The reasoning is that more visits generally indicate a move that has been explored more thoroughly and statistically more promising. In frameworks where final selection strategies are not specified, assume this default approach.
29

---

Published in Transactions on Machine Learning Research (04/2025)
RAP
Hao et al,, 2023
Applicable to Blolks Crosswords, and other reasoning tasks.
LMPP Expansion vs. Exhaustive Action Retrieval: The method of sampling actions depends on whether the action space finite and predefined (e.g., BlocksWorld, where exhaustive retrieval used) open-ended (e.g., Crosswords, where LMPP sampling used).
LATS
Zhou et al. 2024a)
Targets tasks with reversible actions (c.g., certain reasoning problems, web navigation).
Path Simulation: Exccutes actions in the actual environment during path simulation, requiring actions to be reversible to allow repeated trials.
Solution Selection:
Besides reaching allotted iterations, the search is terminated when task is completed successfully. The corresponding path is given as the solution.
LLM-MCTS (Zhao et al. 2023
Designed for robotic tasks.
Path Simulation: Uses random sampling and domain-specific simulator for path simulation, producing next stales and rewards.
MCTS Selection: Adopts a domain-specifie P(s, a) in PUCT, which is derived from LMPP sam pling to form an action distribution.
rStar QQi et al. 2025
Designed for reasoning tasks. However, more heterogencous set of actions is defined, including proposing an intermediate thought, generating multiple thoughts until reaching a terminal state, or rephrasing the original question and questions.
Acknowledging the limitations of small language models (SLMs) in serving direct evaluators, it employs self-consistency scores derived from multiple simulation samples (i.e., Impr (mpepoliekkeval)))
Solution Selection: Instead of selecting only the next action at the root node, the framework selects an entire trajectory from all rollout trajectories. To verify candidates, the selected trajectory is pruned to assess whether another SLM would generate the same subsequent steps.
MC-DML
Shi et al. 2025
Targets at embodied tasks. Specifically, they experiment Interactive Friction (IF) gamos, where reward, state and observation given by the game environnent/sinulaton
MCTS Selection: Besides Impplagas it also uses another two types of Impp" in the case of black-box LLMs, e-g.; OpenAl ChalGPT.
This phase integrated with the selection phase, where only Impp" generates prior distribution. If the action chose by the PUCT selection leads to leaf node, the environment transits it the next state, followed by the path simulation phase, where the uniform sampling will be applied.
LMPP Expansion:
LMPE+ Evaluation: Impeverbalize is used to generate reflection on history failed episodes during the simulation (i.e., cross-tria information) phrase. We denote the pair of an episode and its reflection as reps,.rt)
30

---

Published in Transactions on Machine Learning Research (04/2025)
Cross-trial Information for LMPP Generation: Besides the previous steps along the current path (i.e., in-trial information), (eps,,r;) are also added the prompt of the LMPP. It reminds of cross- trial information within Reflexion (Shinn et al, 2023). However, MC-DML is first used within a LIS framework.
5.7 AlphaZero-Like MCTS (a-MCTS)
In traditional MCTS, after expanding a node, a path simulation is run to the end of the game to estimate the outcome. However, many modern implementations (like in AlphaGo/ AlphaZero) skip the full simulation and instead use direct evaluation function or Process Reward Model (PRM) to estimate the reward immediately after expansion rather than roll out the entire episode for a reward. This approach can significantly speed up the process and provide more accurate evaluations the evaluation function is well-tuned. summary, the following phases are iteratively performed: Selection, Expansion, Evaluation (replacing path simulation), and paoo-propaggttin.
PG-TD (Zhang al. 2023)
Specializes in code generation.
MCTS Selection: Treats the prior distribution P(a s) in PUCT as the LMPP token probabilitics for the next. token (i.e., Impploga); given the partial program.
Evaluation: Rather than direct evaluation, the phase consists of the following processes: 1) Uses LMPT simulation to generate the rest of the program, but internally adopts beam search for trans- former decoding to complete the program; 2) Generates a reward by running the program on the lest cases.
GDP-ZERO
Yuu et al., 2023)
Designed for goal-oriented dialogue.
LMPP Expansion: An LMPT is configured for transition, i.e., two inference calls performed to simulate both the system and user responses. The pairs of responses are stored in the memory Mresponse for each state. Hence, if the maximum number of responses for state s are reached, the transition is sampled from Mresponse
Evaluation: LMPE Evaluation is performed. particular, Impe2 serves the PRM, generating reward signal for MCTS backpropagation after expansion. Its profiling is similar to simulator, who is prompted to indicate their willingness to
wherein the LLM is configured to emulate perform a specific action (c.g., making donation). However, different from the LMPT, a set of five choices is provided for rating, each corresponding to a different reward.
Tree Search (TS)-LLM (Wan et al., 2024
Target Tasks: TS-LLM is designed for both combinatorial tasks (e.g., chess, Game-of-24) and reasoning tasks via concatenation, where each action treated as a sentence. They also define each action as a token for general language reasoning for Reinforcement Learning from Hurnan Feedback (RLHF).
The original work briefly describes two ways to define the search space during expan- sion: one based on an exhaustive set of possible tokens and the other using candidates sampled by LMPP.
Expansion:
Evaluation: The LLM fine-tuned as RM evaluate intermediate states (sce details in Sec- tion 7.2
31

---

Published in Transactions on Machine Learning Research (04/2025)
Solution Selection:
The search is performed multiple times to generate candidate solutions. The final solution is chosen according to either the majority voting the sum of rewards, or the maximum reward, where ORM is used to generate rewards.
Solution Selection:
The search process is repeated multiple times to generate candidate solutions. The final solution is selected based on majority voting, the sum of rowards, or the maximum reward, with an ORM used lo produce the reward values.
ReST-MCTS* (Zhang et al., 2024a
Target Tasks: ReST-MCTS* is designed for reasoning lasks via concatenation, where each sentence treated as a discrete step.
Evaluation: Similar to TS-LLM, the LLM is fine-tuned PRM to evaluate intermediate states (sce Scction 7.2 for details). To estimate the value of the current state St, the rewards from the PRM are weighted by the estimated reasoning distances, analogous to the h(s)) term in A#.
Solution Selection: After the selection phase, if the value of the selected node meets exceeds a predefined threshold, the corresponding solution is returned.
6 LLM Inference + Search Beyond Sequential Decision Making
The previous focus is the work that the search process are coupled with the LLM's decoding process, where downstream tasks are formulated as sequential decision-making problems (as detailed in Section 2 and LLMs serve as integral components in search procedures. This section aims to explore all the other works that include both LLM inference and search methods. However, these approaches either optimize other elements (such as model selection or inference workflows) or do not fit in the MDP formulation or use search and LLMs separately. For example, the plans (commonly in the form of PDDL) are prepared by LLMs perform local search (Valmeekam al.) 2023b Guan al.) 2023 Valmeekam et al., 2023a)..
As result, the notions of actions and states do not exist, at least during LLM inference. This distinction leads to several fundamental differences. For instance, the roles of LMPP and LMPT are not applicable, which is why LLM sampling, rather than LMPP sampling, is introduced in the frameworks below. Furthermore, state simulation is never required.
LLM for World Modeling + Search In this paradigm, LLMs are employed to generate world models that serve as the basis for planning. In contrast, LLMs the LIS frameworks operate as world models (c.g., LMPEs and LMPTs). The world models can be represented by the Planning Domain Definition Language (PDDL) (McDermou 2000), which clearly defines action preconditions and effects, Python code. For example, Guan et al. 2023); Liu et al. (2023) utilize LLMs to generate PDDL-based world models and then apply classical search- based planners (e.g., LPG) to solve tasks. In contrast, Dainese et al. (2024) prompt LLMs to generate Python code for world modeling and then solve tasks via Monte-Cane Carlo Tree Search (MCTS).
Meta-Search for LLM-Inference Strategies for Problem Solving The frameworks in Section 5 directly search for (partial) solutions-using search itself as the strategy to reach solution. In contrast, this paragraph focuses on meta-search methods that identify the strategies reach a solution. For example, DOTS (Yue et al., 2025) investigate whether LMPE evaluation is necessary for given problem, while the LIS methods integrate LMPE evaluation into determining whether action is optimal for achieving the goal. Strategist (Light et al.) 2025) scarch for optimal high-level strategics that guide the generation of task solutions. Similarly, AFlow (Zhang et. al.) (0255) employs MCTS to search for optimal inference workflows for solving downstream tasks. However, the resulting solutions may not strictly conform to a search- based workflow. Essentially, this approach focuses on the structure and efficiency of the overall inference process. In contrast, the LIS frameworks directly concentrate on constructing search workflows for downstream tasks. Besides, Zheng al. (2025) conduct grid search over 6 reasoning strategies and 5 types of instructions.
32

---

Published in Transactions on Machine Learning Research (04/2025)
However, their grid search is used solely to evaluate the combinations, rather than as meta-search strategy for problem solving.
Equilibrium Search in a Two-Player Game Generally, a discriminator (a special LMPE) and a gen- erator (a special IMPP) are defined to engage in a game, where a correctness parameter for the generator is selected uniformly at random. Both the discriminator and the generator receive a payoff of when they agroe on the correctness parameter. This cquilibrium objective is regularized by the prior, i.c., the inital generation of large language models (T.LMss,; some equilibrium solutions may not align with commonsense reasoning. The final state is reached when the discriminator and the generator reconcile with each other. Unlike single-player games, two-player games involve theoretical frameworks under the umbrella of game theory and equlibrium analysis. While this aspect is beyond the scope of this survey, the fundamental steps of LLM sampling and LMPE evaluation remain essential prerequisites before executing equilibrium computations to achieve a regularized equilibrium.
LLM Sampling: An LLM is prompted for sampling in batch. While this is similar to Imprbatch pollcyy the LLM is prompted with the value of the correctness parameter, which is ei- ther "correct" or "incorrect".
LMPE Evaluation:
Corresponding to the values of the correctness parameter, the LMPE (or discriminator) generates binary predictions (i.e., "correct" or "incorrect"). Specifically, the LMPE is implemented as Imprevall-
Evolutionary Search EvoPrompting (Chen et al. 2023 employs evolutionary search to generate imple- mentation code for neural architectures, while Wang et al. (2025b) perform evolutionary search over chemical space, particularly for molecular discovery. Both re-define cross-over and mutation operations via LLMss. However, it is not defined for sequential dicsion making, where the next step is determined by the previous step(s). For example, the complete solution code is not required lo be decomposed into smaller components. This traces to the nature of cross-over and mutation operations requring the entire solution the input.
The key procedures in their algorithm are:
LLM Sampling: An LLM used during the cross-mutation phase to generate candidate codes.
The generation process is conditioned on randomly selected codes from the population.
Value-Based Top-K Selection: This method updates the population by selecting the top K candidates based on a value function. The ValueFunc is implemented by training a deep learning model with the generated code and evaluating validation accuracy.
Search over Solution Sketches for Code Generation PlanSearch (Wang et al. 2025a searches over solution sketches prior to generating code-that that is, operates on a natural language description of the correct program. Specifically, the model samples "observations" (small pieces of ideas or hints) which are then concatenated with the task description to prompt the LLM to generate subsequent observations. Each soquence of obscrvations at depth two is then used to prompt the LLM to formulate a comprehensive idca. The LLM is subsequently re-prompled to produce alternative another set of ideas by designating the initial set as incorrect. Finally, each idea is usd to prompt the LLM to generate code.
This framework is discussed the final section for two reasons: (1) The search space is not directly rolated to code generation. However, can be viewed as a form of language reasoning via concatenation, where each thought constitutes an observation; and (2) the framework does not employ traditional search algorithms (e.g., A MCTS).
7 Related Work
Although the primary focus of this survey is on test-time compute via search, several related directions fall outside our current scope.
33

---

Published in Transactions on Machine Learning Research (04/2025)
7.1 Other Frameworks for Test- Time Compute
Search with Multi-Modal LLMs. Some work extends tree-based exploration and action selection to multi-modal contexts by incorporating visual features alongside textual reasoning steps, e.g.. Mulberry Yao al. 2024
Branching without Scarch. Some frameworks utilize branching or treo-like expansions but do not incorporate a full-fledged search algorithm. Examples include Tree-Planner (Hu el al. 2024), Boost- of shouhhs (Chen et al. 2024a), and Trraph-of-Thougheee (GoT) (Besta et al. 2024). Although they adopt branching structures similar to traditional search, these methods rely on aggregation, sorting, or heuristics rather than explicit search procedures.
Re- Re-nknning Frameworks: these frameworks, LMPP is initially employed to sample multiple candidate solutions. However, unlike the LMPP sampling described in Section here it generates complete sequences of actions (i.e., plans) instead of just intermediate actions as seen in MDP-like settings. These two variants of LMPP are distinguished as "actors" and "planners" in Li (0024)
An evaluation function then is used to re-rank the plans by assigning the scores over plans/ linal answers. Notable examples include LEVER (Ni et al., 2023) for code generation and DiVeRSe (Li
et al. 2023) for language reasoning. It may be a normalized consistency function (Wang et al. 2023) or a learned model like a Process Reward Model (PRM) or Outcome Reward Model (ORM)
[Lihttman al. 2024).
Same as re-ranking methodss an evaluation function is applied to plans/ answers. However, this process can be iterative. Examples include Self-refine (Madaan al.) 2023a Table comparos re-ranking methods, sequential evaluation and scarch-based methods for LLM inference. Hence, it can be also defined as MDP process (Qu et al. 2024].
Sequential Revision:
7.2 LLM Fine-tuning for Tist-Time Compute
Recent methods adapt LLMs via fine-tuning or preference oplimization to enhance their roles in policy, evaluation, and transition modeling. For instance, in the TS-LLM framework (Wan et al. 2024], the LLM is finc-tuned as an Outcome Reward Model (ORM) or a Process Reward Model (PRM) that evaluates each reasoning step. ReST-MCTS* (Zhang et al. 2024a) fine-tunes LLMs to serve both as a policy model, generating reasoning traces, and as PRM. Although the paper does not explicitly state that both models start from the same checkpoint, the standard procedure implies that a pretrained LLM is duplicated into two copics. In DeePSeek-MCTS (Guo al., 2025), LLMs are iteratively fine-tuned for both policy and reward roles using question-ani answer pairs. In this framework, questions are collected, and answers are generated by MCTS guided by a pretrained value model. LLMs are also fine-tuned for other test-time compute tasks, For example, Recursive IntroSpEction (RISE) (Qu et al.) 2024) fine-tuncs LLMs as the LMPP for sequential revision, while the LMPE can be implemented using a stronger teacher model or via a self-consistency approach (i.c., imprpolicykovaal
Fine- Chne-Tuning LLMs for PRMs For all PRMs in the above work, except for DeepSock-MCTS the unembedding layer, which maps hidden states to vocabulary distribution, is replaced by MLP that outputs scalar values. This recalls how reward models are trained in Reinforcement Learning from Human Feodback (RLHF) for general-purpose alignment OOnang et al. 2022
8 Discussion
In this scction, we analyze how search frameworks for LLM inference deviate from traditional scarch algo- rithus, where they apply according to technical constraints, performance and efficiency.
Limited details provided the paper.
34

---

Published in Transactions on Machine Learning Research (04/2025)
Table 9: Comparisons of LLM inference via search and re-ranking. Here, A, denotes the set of candidate actions at step along path i, represents the candidate plans, and Piria_ denotes the candidate plans trial j. The term "Iterative?" indicates whether the sampling and evaluation processes are iteratively executed.
Sampling
Evaluation
LMPE?
Iterative?
Fine-tuning
LIS
actions
{a a
E
Often
/
TS-LLM
Wan et
A along path;)
2024
DeepSeck MCT
Guo et al. 2025
Re-Ranking
plans
(p PP
Rarely Always
X
Sequential
Re-
plans
{n polp Paria_))
/
RISE Quu et al.
2024
vision
8.1 Deviations from Typical Search Algorithms
Beyond Finite, Fixed Scarch Spaces Classical BFS or DFS typically requires cnumcrating all successors at each depth, which can lead massive memory usage in large or infinite search spaces. By contrast, LMPP sampling (based LLM priors) manage successor expansions more selectively, reducing the need to store every possibility at cach level. Also, it is possible to handle tasks with an open and infinite action space.
Making "Uninformed" Search Informed Traditionally, BFS and DFS are considered uninfformed, exploring the search space without heuristics. LLM-based frameworks labeled as BFS DFS often incor- porate LMPP sampling or LMPE+ evaluation, effectively introducing heuristic knowledge from the LLM. Moreover, anticipating dead ends in DFS is feasible with LLM-based heuristics. Classic DFS only identifies dead ends when it exhausts neighbor nodes. With an LLM, the search can backtrack early if the model predicts an unpromising or "dead-end" scenario.
Compromised Optimality in A A requires an admissible heuristic h(s) to guarantee optimality. However, if h(s) partially depends on a policy-generater state Sllm from Impr the heuristic may be overestimated. This breaks admissibility assumptions, meaning the final solution may no longer be strictly optimal.
Terminology Deviation for Heuristic Search: Cost vs. Return/Valus Many early applications of search algorithms, such as Best-First Search and A*, focused on minimizing quantities like distance, travel time, or energy expenditure. Generally, the cost-based evaluation can be considered as minimization objectives or climinating "bad" states (or unpromising actions). However, in modern applications involving LLM-integrated search, such as web navigation document retrieval, heuristics often reflect value eslimates (positive polarity), especially when LLMEs tend to be defined to reflect the relevance utility of states, which are better suited for maximization objectives or maintaining "good" states (or promising actions). We highlight this point for rigidity. However, these terms can be abstractly defined without indicating real-world semantics. For example, in game design, moving to a node which end up losing a life point can be given a negative reward, while a reward from gaining a key can be granted as a negative cost.
RL vs. LMPE-Based Value Functions In traditional RL, the value function rigorously defined via the Bellman equation the expected cumulative future reward (or cost) that one obtain starting from given state. This formulation inherently accounts for the uncertainty of future outcomes by computing a weighted average of rewards over all possible future trajectories (Sutton & Barto 2018
In contrast, when LLMs are used in tree search, the "value" assigned to a node is often generated based on the model's world knowledge and reasoning Yao al.) (023a).. This evaluation serves as houristic and is derived from the LLM's internalized representations rather than being computed from a strict, recursive future-reward formulation. As a result, while both the RL value and the L.MM-based evaluation score aim to
35

---

Published in Transactions on Machine Learning Research (04/2025)
measure the "goodness" or utility of state, the latter does not necessarily adhere to the Bellman property
[Bellman 1966 Watkins 1989..
8.2 Applicability
Extending Uninformed Search to Dynamic Decision-Making BFS and DFS were originally de- signed to explore predefined or casily generated state spaces (e.g., enumerating all children in graph). This can be: 1) No Need for Transition: Traditional implementations of DFS and BFS do not require an explicit, computed transition model because they inherently rely on the graph structure where edges already define state transitions. For example, one task to solve a maze. 2) Only Successor Function: In some applications, especially in implicit stato-space search, a minimal form of transition function (or successor function) is still required to generate successors when the full graph is not explicitly available.
However, when applied to LLM inference, they can be adapted for: 3) Tasks That Require Dynamic Decision-Making: These tasks are based on state-dependent actions (as seen in planning or reinforcement learning), e.g., solving the Game of 24 and completing crossword puzzles.
Open-Loop vs. Closed-Loop Frameworks This property is important to discuss the applicability of frameworks for planning. 1) Open-Loop (Offline): After executing ae, the open-loop agent does not adapt its future actions based on the actual new state. Instead, it continues to follow a pre-planned sequence of actions, which are based the simulated state during planning. For example, ToT-DFS and ToT-BFS (Yao et al. 2023ab produce a predefined sequence of actions based on a search through static search tree or graph. This sequence is intended to be executed exactly as planned. Ideally, open-loop planning requires that the environment will remain as anticipated throughout the execution. Such environments satisfies the following assumptions: a) environments are static, b) unforeseen events or changes will affect the execution (closed-world assumption), and c) deterministic transitions. 2) Closed-Loop (Online): In contrast, after the closed-loop agent executes an action a,, it observes the outcome in the real world (i.e., the resulting state) and can adjust its future action a++1 based on the new state S1+1- The plan evolves dynamically as new information becomes available. MCTS-based frameworks, except for LATS (Zhou et al. 2024a), can be open-loop because it generates a sequence of actions based on simulations and a static model of the environment at a given state. However, the agent can operale in a closed-loop manner if MCTS is re-run at each new state: after a plan is generated for St, only a is selected and executed. Instead of executing the rest at+1,...,, the agent re-runs MCTS from the new state 8t+1 to dotermine the next best action 1+ These frameworks are suitable for task execution in dynamic and interactive environments.
Many LIS Frameworks Requires Action Undoing In many LIS frameworks, the agent has to revisit carlier states, including backtracking to an ancestor node in DFS Yao et al.] 2023a), selecting the next best candidate in Best-first search (Koh et al. 2024), or retracing your steps after an environment-ben based simulation in MCTS (Zhou et al., 2024a). Each of these processes relies on being able to recover the state reached by previous actions. This limits their applicability to environments where undoing actions is viable, as specified in Table? 2
8.3 Performance
Scaling Lest-time compute via search has generally enhanced the LLMs' power to a new level on reasoning tasks. Nonetheless, there remain certain scenarios where performance is still suboptimal.
Search Frameworks Perform Worst in Multiple Scenarios Empirical studies by Parashar et al. (2025) also indicate that ToT and RAP perform even worse than CoT and self-consistency in various language reasoning tasks. Also, as demonstrated by [nell et al. (2025), ; if a base LLM can already produce reasonable answers for simple questions, then sequential revision suffices to ensure performance, offering an efficient alternative to more complex re-ranking methods and search methods.
MCTS May Degenerate in Early Stages Chen et al. (2024b) observe that if all candidate steps receive equal (or zero) scores initially, MCTS lacks clear basis for distinguishing among branches, potentially
36

---

Published in Transactions on Machine Learning Research (04/2025)
leading to suboptimal partial-plan selection. The performance is worse than iterative refinement MMadann
et al. 2023b)
8.4 Efficiency
Compute and Memory Efficiency As noted by Chen et al. (2024b), tree search can be 10-20 times slower than iterative refinement, especially if the evaluator (LMPE) has less than 90% discrimination accu- racy. High-accuracy LMPFs are essential to prune the search tree effectively, thereby reducing the number of iterations needed. Long-horizon tasks can become particularly expensive when each LLM inference call is exccuted independently, despite many calls sharing identical prefixes. By leveraging Key- Value (KV) caching, both computational and memory overhead in transformer-based LLMs can be significantly reduced. Yao et al. (025)) propose tree attention, which leverage tree topology to reduce memory 10 with tree- structured KV caches.
LMPP Expansion and Path Simulation with Memory Finally, maintaining memory of explored nodes can avoid repeated sampling and simulation. If a given state has already produced certain actions, those child nodes can be cached for subsequent expansions. Similarly, for simulation, previously simulated results can be stored for future simulation. By reusing these cached outcomes, the framework reduces redundant calls to LMPP or LMPT, thereby improving both inference cost.
Unnecessary LMPP Use in Some Cases Some tasks possess small, tractable action space (e.g., the Game of 24). In such scenarios, exhaustive action retrieval may be cheaper than performing multiple LMPP inferences. Designers must weigh the inference costs of LMPP against potential benefits, as LLM-basod sampling can be expensive relative to enumerating finite set of actions. The polential cost of the following LMPE+ evaluation should also be considered.
8.5 Future Work
Parallel Rescarch on LLMs' Competence and Test-Time Computation Rather than relying on intensive lest-time computation, optimization frameworks such as Chain of Preference Optimization (Zhang et al.) 2024b) have been proposed to train LLMs to develop tree-like reasoning, thereby reducing the need for real-time deliberation. In parallel with investigating the impact of base models and LMPRs on performance, further rescarch is needed to both enhance LLMs' capacity for autonomous multi-path thinking and identify complex lasks which most benefit from deliberate search during test-time computation.
Devising Frameworks for Handling Irreversible Actions Many prominent LIS frameworks do not incorporate mechanisms for managing irreversible actions. Instead, they circumvent this issue by working in simplified task environments where the effects of actions be virtually simulated. For example, Tree of Thoughts (ToT) (Yao et al., 2023ab focuses language reasoning, while Koh et al. (2024) studies web navigation scenarios that involve only reversible actions. This approach is in line with abstract search methods (e.g., DFS or Best-first search on a graph), where action outcomes are computed via deterministic transition functions, climinating the need to physically execute or reverse actions.
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Tgge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint (rXim:2303.08714 2023.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carric Cai, Michael Terry, Quoe Le, et al. Program synthesis with large language models. arXiv preprint ar Xiv:2108..0 07732, 2021.
Richard Bellman. Dynamic programming. science, 153(3331):34 37, 1966.
37

---

Published in Transactions on Machine Learning Research (04/2025)
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyezyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17682-17690, 2024.
Nasim Borazjanizadeh, Roci Herzig, Trevor Darrell, Rogerio Feris, and Lconid Karlinsky. Navigating the labyrinth: Evaluating and enhancing LLMs' ability to reason about search problems, 2024. URL https:
//openreview www.:eoooomidddddeeeeeeeeee
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Πlya Sutskever, and Dario Amodei. Lan- guage models are few-shot learners. In H. Larocholle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Cur- ran Associates, Inc., 2020. URL 24770116610444111111117771111111
neuripss.....r........m wwt.reeerrrippppppeeeeeeee.e wallee/paper/222////... pdf
Angelica Chen, David Dohan, and David So. Evoprompting: Language models for code-level neural ar- chitecture search. In shirty-seventh Conference on Neural Information Processing Systems, 2023. URL
htttss//oppnrevieww wtwpa/rrwwww..eeeoouu/uueaaaeeee -
Sijia Chen, Baochun Li, and Di Niu. Boosting of thoughts: Trial-an-erroo problem solving with large language models. In The Twelfth International Conference on Learning Representations, 2024a. URL
https://openreviers net peet/foruunid=qqLLAXe..
Ziru Chen, Michael White, Ray Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for LLM planning? it depends on the discriminator. In Lun-Wor Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeling of the Associalion for Computational Linguislics ( (Volume 1: Long Papers), pp. 13659 13678, Bangkok, Thailand, August 2024b. Association for Computational URL
Linguistics. doi: 10.18653/ 1t1/2222222cooong.....
org/2024 200224acl-1o0 acw-alng....0000 738.
Karl Cobbe, Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXim:2110.1 14168, 2021.
Nicola Dainese, Matteo Merler, Minttu Alakuijala, and Pekka. Marttinen. Generating code world models with large language models guided by monte carlo tree search. In The Thirty-eighth Annual Conference on Newral Information Processing Systems, 2024. URL httpss://openrevies www.:nee/foooeoo wtt.://www...e.oooorr///////oo/o
Linxi Fan, Guanzhi Wang, Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De- An Huang, Yuke Zhu, and Anima Anandkumar. Minedojo: Building open-ended embodied agents with internet-scale knowledge. In Thirty-sirth Conference on Newral Information Processing Systems Dalasels and Benchmarks Track, 2022. URL https:// http:////ppppeeeeeeeeeeee/r/r/a/ wttp:/ooom/dddddrro_._0..
Xidong Feng, Ziyu Wan, Haotian Fu, Bo Liu, Mengyue Yang, Girish A. Koushik, Zhiyuan Hu, Ying Wen, and Jun Wang. Natural language reinforcement learning, 2024. URL
org. abs/ 2411 14251
Olga Golovneva, Sean O' O'Brien, Ramakanth Pasunuru, Tianlu Wang, Luke Zettlemoyer, Maryam Fazel- Zarandi, and Asli Celikyilmaz. PATHFINDER: Guided search over multi-step reasoning paths. In Ro- FoMo:Robustness of Few-shot and Zero-shot Learning in Large Foundation Models, 2023. URL https: //openreview
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre-trained large language models to construct and utilize world models for model-basod task planning. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. URL https::/openreviess Forum?id==DbaSsccmm
38

---

Published in Transactions on Machine Learning Research (04/2025)
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXio preprint arXiv:2501.19448 2025.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model planning with world model. In Houda Bouamor, Juan Pino, and Kalika. Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8154-8173, Singapore, December 2023. Association for Computational Linguistics. URL https://aclantholoogyy org/2023. www.eemmnlppmmimmmmmmm
Matthew Hausknecht, Prithviraj Ammanabrolu, Marc-Alexandre Côté, and Xingdi Yuan. Interactive fiction games: A colossal adventure. Proceedings of the AAAT Conference on Artificial Intelligence, (4)) 7903 7910, Apr. 2020. doi: 10.1609 03000///aa..4405..22222 v34i05.6297. URL https://ojs. aaai oaraloorggiin /nde/indxx,aa/ phpppppppaa.. AAAI/
article/viee/62277
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. In Thirty-fifth Conference on Newral Information Processing Systems Datasets and Bench- marks Track (Round 2), 2021a. URL hattps://openreviee
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Thirly-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021b.
URL https:// http://rwwr...eeeeoooooo//////te
Mengkang Hu, Yao Mu, Xinmiao Chelsey Yu, Mingyu Ding, Shiguang Wu, Wenqi Shao, Qiguang Chen, Bin Wang, Yu Qiao, and Ping Luo. Tree-planner: Efficient close-loop task planming with large language models. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview.oo www.ee..ee/ooooo
Xu Huang, Weiwen Liu, Xiaolong Chen, Xingmei Wang, Hao Wang, Defu Lian, Yasheng Wang, Ruim- ing Tang, and Enhong Chen. Understanding the planning of 1m agents: A survey. arXiv preprinl XXXx:2402.02716, 2024.
Athul Paul Jacob, Yikang Shen, Gabriele Farina, and Jacob Andreas. The consensus game: Language model generation via equilibrium search. In The Twelfth International Conference on Learning Representations, 2024. URL
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El Showk, Andy Joncs, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Gan- guli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Josoph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know. CoRR, abs/2207. .05221, 2022. URL https:///oii http://di.oorrr///// /0g//10.oo 48550/ 111500/rxiv... 2207 220220522111212
Jikun Kang, Xin Zhe Li, Xi Chen, Amirreza Kazemi, Qianyi Sun, Boxing Chen, Dong Li, Xu He, Quan He, Feng Wen, Jianye Hao, and Jun Yao. Mindstar: Enhancing math reasoning in pre-trained Iims inference time, 2024. URL https:///arri: org/ abs 16265
Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents. arXiv preprint arXiu:2407001476 2024.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL id=e2TBb5y0yFf
39

---

Published in Transactions on Machine Learning Research (04/2025)
Shuang Li, Xavier Puig, Chris Paxton, Yilun Du, Clinton Wang, Linxi Fan, Tao Chen, De-An Huang, Ekin Akyürek, Anima Anandkumar, Jacob Andreas, Igor Mordatch, Antonio Torralba, and Yuke Zhu. Pre-trained language models for interactive decision-making, In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (ods.), Advances in Neural Information Processing Systems, 2022. URL
attps://openreviers wtwpeeeeeiieeeeeeerrrriiiiiiieee weet/foruun?dd-/WMYYYBess
Xinzhe Li. A review of prominent paradigms for
agents: Tool use (including rag), planning, and feedback learning. arXiv preprint arXiv:2406 05804, 2024.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guarg Tou, and Weizhu Chen. Making lan- guage models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Associalion for Compulational Linguistics Toronto, Canada, July 2023. Association for Computational Lin- guistics. doi: 10.18653/v v1 acl2..acl-oong URL https://aclantthooog orr.aaatoooooooooo//22233.3. acl mocl-looe -ong. 291/
(Volume 1: Long Papers), pp.
Jonathan Light, Min Cai, Weiqin Chen, Guanzhi Wang, Xiusi Chen, Wei Cheng, Yisong Yue, and Ziniu Hu. Strategist: Self-improvement of LLM decision making via bi-level tree search. In The Thirteenth International Conference on Learning Represenlations, 2025. URL httpps///openrreeee.eteeeeeeeeee gfIvv/
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike,
John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URL
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL https://openrrriew.nm
forum71d=-s882170122
Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Llm+ p: Empowering large language models with optimal planning proficiency. arXiv preprint 1r14::2304.11477, 2023.
Shengjie Ma, Chengjin Xu, Xuhui Jiang, Muzhi Li, Huaren Qu, Cehao Yang, Jiaxin Mao, and Jian Guo. Think-on-graph 2.0: Deep and faithful large language model reasoning with coowlege-guiide retrieval augmented generation. In The Thirteenth International Conference on Learning Representations, 2025. URL /ttps:///penrrevie: wttp://oorrrr//d///////////
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisatiwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In Thirby-seventh Conference on Neural Information Processing Systems, 2023a. URL https://oppnreviii
net wwt.rr/wwwwwnwtnneeeeeeeee metf/forum/idd-37/0rrr0
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Vang, et al. Self-refine: Tterative refinement with self-feedback. arxiv preprint ar XrXx:2300. 1 7651, 2023b.
Drew McDermott. The 1998 ai planning systems competition. AT Mag., 21 55, June 2000. ISSN 0738-4602. doi: 10.1609/aiman hatp:/aiiaaaa.....51.100 1506..1506. URL httpp:://oi..rgg//// 1609//.....1//// 10w.91109aaaamm
v2112. 1506
Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, and Kai-Wei Chang. Llm-a*: Large language model enhanced incremental heuristic search path planning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, December 2024.
Ansong Ni, Srini Tyer, Dragomir Radev, Ves Stoyanov, Wen-tan Yih, Sida I. Wang, and Xi Victoria Lin. Lever: learning to verify language-to-code generation with execution. In Proceedings of the 40th Interna- tional Conference on Machine Learning, ICML,22 223 JMr,. 2023.
40

---

Published in Transactions on Machine Learning Research (04/2025)
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL
https://openrevieu wwrpeerrwiie..nee/oouuuuttaeeeee
Alexander Pan, Erik Jones, Meena Jagadeesan, and Jacob Steinhardt, Feedback loops with language models drive in-context reward hacking. In Porty-forst International Conference on Machine Learning, 2024. URL
Shubham Parashar, Blake Olson, Sambhav Khurana, Eric Li, Hongyi Ling, James Caverlee, and Shuiwang Ji. Inference-timee computations for 11m reasoning and planning: A benchmark and insights, 2025. URL
attpp://arxxv.or///b///2222222
Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
2018.
Pranav Putta, Edmund Mills, Naman Garg, Sumeet Ramesh Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov. Agent q: Advanced reasoning and learning for autonomous ai agents. 2024. URL
https://app /t///pppsssaaaniccccllllaalaaaaa htt.r//icccccooooooooooooooooooa :t 271865516
Zhenting Qi, Mingyuan Ma, Jiahang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. Mutual reasoning makes smaller LLMs stronger problem-solver. In The Thirteenth International Conference on Learning Representations, 2025. URL httpps:/
Yuxiao Qu, Tianjun Zhang, Naman Garg, and Aviral Kumar. Recursive introspection: Teaching language model agents how to self-improve. In The Thirly-eighth Arnual Conference Neural Information Pro- cessing Systems, 2024. URL https:://peerrevier wttpearreeeee.ettttorriiiaaaaaaa wwtt://oruuiidddDcpp--...e
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and 1lya Sutskever. Language models are unsupervisod multitask learners. 2019.
Stuart J Russell and Peter Norvig. Artificial intelligence modern approach. London, 2010.
Shibani Santurkar, Esin Durmus, Faisal Ladhak, Cinoo Lee, Perey Liang, and Tatsunori Hashimoto. Whose opinions do language models reflect? arXiv preprind ur Nii:220331155,4 2023.
Zijing Shi, Meng Fang, and Ling Chen. Monte carlo planning with large language model for text-based games. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //openreview.c wttpeevvvwwinneteeeeeeeeee wett/forummid=rrrt met//formm//dd11appktt
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Cote, Yonatan Bisk, Adamn Trischler, and Matthew Hausknecht. (ALFW)orld: Aligning text and embodied environments for interactive learning. In In- ternational Conference on Learning Representations, 2021. URL httts::/ wttp:/iwwwinnneeeeeeeeeeeeeeeeee wwt.f fettfoormmidd cId
John Slaney and Sylvie Thiébaux. Blocks world revisited. Artificial Intelligence, 125(1):119 153, 2001. ISSN 0004-3702. doi: http:///aaaoooo//...oo.s/o000000
URL httpps:/wwwl http://wwwwccncncireetttttt
Charlic Victor Snell, Jachoon Loc, Kelvin Xu, and Aviral Kumar. Scaling test-time compute optimally can be more effective than scaling LLM parameters. In The Thirteenth International Conference on Learning Representations, 2025. URL http://ppp//gggaamiiaaeee//////p
41

---

Published in Transactions on Machine Learning Research (04/2025)
Benjamin Adin Spiegel, Ziyi Yang, William Jurayj, Katic Ta, Stefanic Tellex, and George Konidaris. In- forming reinforcement. learning agents by grounding natural language to markov decision processes, 2024.
URL https://openreevier wttp://eww.eeooooor///oooooooop
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung- Yeung Shum, and Jian Guo. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Conference Learning Representations, 2024. URL
https://openrevier
Richard S Sutton and Andrew G Barto. Reinfforcement learning: An introduction. MIT press, 2018
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In Thirly-seventh Conference on Newral Information Processing Systems Datasels and Benchmarks Track, 2023a. URL httpps://ppereviiee wttp://ww.....oooomomdoooooooo/o
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the plan- ning abilities of large language models critical investigation. In Thirty-seventhh Conference on Neural Information Processing Systems, 2023b. URL htttp::/ wtt.://eeeee/oort///--EEEEEEEE..
Ziyu Wan, Xidong Feng, Muning Wen, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training, 2024. URL sttp:::/ppemrrrrii..ntffffooo
EL09VaAb3B
Chaojie Wang, Yanchen Deng, Zhiyi Lv, Shuicheng Yan, and An Bo. Q*: Improving multi-step reasoning for IIms with deliberative planning. arXiv preprint Xrx:22206. 14289, 2024a.
Evan 7 Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, William Song, Vaskar Nath, Ziwen Han, Sean M. Hendryx, Summer Yue, and Hugh Zhang. Planning in natural language improves LLM search for code generation. In The Thirteenth International Conference on Learning Representations, 2025a. URL https://openreviie net net/ http///rrunnd-44////aaaa
Haorui Wang, Marta Skreta, Cher Tian Ser, Wenhao Gao, Lingkai Kong, Felix Strieth-Kalthon Chenru Duan, Yuchen Zhuang, Yue Yu, Yanqiao Zhu, Yuanqi Du, Alan Aspuru-Guzik, Kirill Neklyudov, and Chao Zhang, Efficient evolutionary search over chemical space with large language models. In The Thirteenth International Conference on Learning Representations, 2025b. URL https://openrevier:
Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey large language model based autonomous agents. Frontiers of Computer Science, 18(6):1 26, 2024b.
Sihan Wang, Kaijie Zhou, Kunfeng Lai, and Jianping Shen. Task-completion dialogue policy learning via Monte Carlo tree search with dueling network. Tn Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 3461-3471, Online, November 2020. Association for Computational Linguistics. doi: 10. http://1111222emmllmmm main.278. URL https:://cllatthtt www.:log...rgg/00..oo.o emnlpmmmllppmmm main. .78
Siyuan Wang, Zhongkun Liu, Wanjun Zhong, Ming Zhou, Zhongyu Wei, Zhumin Chen, and Nan Duan. From Isat: The progress and challenges of complex reasoning. TEEE/ACM ACM Trans. Audio, Speech and Lang. Proc 30:2201 2216, apr 2022. ISSN 2329-9290. doi: LLLLI0//TALLLP2222333666 (tbbii.org/11..110//AA/33/ http://TAASSPP.2.....22 3164218
URL https:
Xuewei Wang, Weiyan Shi, Richard Kim, Yoojung Oh, Sijia Yang, Jingwen Zhang, and Zhou Yu. Persuasion for good: Towards a personalized persuasive dialogue system for social good. In Anna Korhonen, David Traum, and Lluís Mårquez (ods.), Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics, pp.
Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. N0.18633/v1/199- 1566. URL httpaa///cclamthoooy.oooo
42

---

Published in Transactions on Machine Learning Research (04/2025)
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Fleventh International Conference on Learning Representations, 2023. URL https://openreviee..rt net.:/oumeettooooo 1PL1NIMMrW
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
Jason Wei, Xuczhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL ht
net/forummid= Vit.rruummiiiiiiiieeBii..3
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian Hc, and Qizhe Xic. Self-cvaluation guided beam search for reasoning. In Thirth-seventh Conference Newral Information Processing Systems, 2023. URL httpp:://pperrveee..eeeee 1o
Qiantong Xu, Fenglu Hong, Bo Li, Changran Hu, Zhengyu Chen, and Jian Zhang. On the tool manipulation capability of open-souree large language models. arXiv preprint arXiv:2005. 1ete9005.6544,, 16504, 2023.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christo- pher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun'ich Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369-2380, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: 10. (0.18688/11/D11-1255 URL https://aclaattiolog..ooog org./// 1259
Huanjin Yao, Jiaxing Huang, Wenhao Wi, Jingyi Zhang, Yibo Wang, Shunyu Liu, Yingjie Wang, Yuxin Song. Haocheng Feng, Li Shen, et al. Mulberry: Empowering milm with ol-like reasoning and reflection via collective monte carlo tree search. arXiv preprint arXiv:2412. 1et.122.1999 18319, 2024.
Jinwei Yao, Kaiqi Chen, Kexun Zhang, Jiaxuan You, Binhang Yuan, Zeke Wang, and Tao Lin. DcFT: Decod- ing with flash tree-attention for efficient tree-structured LLM inference. In The Thirleenth International Conference Learning Representations, 2025. URL https://openrrvviez pett//oorrumttddd2/7/ptpuuuu
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35: 20744 20757, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. Re- act: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023b. URL https:// http:rrrwo..tetttoto/iiiiiiei vluYUL-X.
Wen-tau Yih, Matthew Richardson, Chris Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 201-206, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/ v1/P16-2033 URL htttps://aclantholog.... wrgp:16-1///00000 2033/
Xiao Yu, Maximillian Chen, and Zhou Yu. trompt-based monte-carlo tree search for goal-oriented dialogue policy planning. In The 2023 Conference on Empérical Methods in Natural Language Processing, 2023.
URL https://openrevierr. wtw.e/reeee..eeeeooooooo///////a
Murong Yuc, Wenlin Yao, Haitao Mi, Dian Yu, Ziyu Yao, and Dong Yu. DOTS: Learning to reason dynamically in LLMs via optimal reasoning trajectories search. In The Thirteenth International Conference on Learning Representations, 2025. URI. http://///ppppeeeeeeeeee//////aa
43

---

Published in Transactions on Machine Learning Research (04/2025)
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. ReST-MCTS": LLM self-training via process reward guided tree search. In The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https://openreviers http:////ppauueeeeeeeeeeeeororrs wtt:foorrmi/1--1rFFFF00
Jiayi Zhang, Jinyu Xiang, Zhaoyang Yu, Fengwei Teng, Xionghui Chen, Jiaqi Chen, Mingchen Zhuge, Xin Cheng, Sirui Hong, Jinlin Wang, et al. AFlow: Automating agentic workflow gencration. In The Thirteenth International Conference on Learning Represenlations, 2025. URL htttps//ppennrevieeenntteeeeeeee www.:eeettfoorurne 25uVAKwmj1
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Eleventh International Conference on Learning Representations, 2023. URL https:///pearrevieww httppp///ppaaaeeeee.eeeee///oaaa
Xuan Zhang, Chao Du, Tianyu Pang, Qian Liu, Wei Gao, and Min Lin. Chain of preference optimiza- tion: Improving chain-of-Chought reasoning in LLMs. In The Thirly-eightt Annual Conference on Newral Information Processing Systems, 2024b. URL hattps://opente
net//forum211222200000
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large- scale task planning. In Thirty-serenth Conference on Neural Information Processing Systems, 2023. URL
Kunhao Zheng, Juliette Decugis, Jonas Gehring, Taco Cohen, benjamin negrevergne, and Gabriel Syn- naeve. What makes large language models reason in (multi-turn) code generation? In The Thirteenth International Conference on Learning Represenlations, 2025. URL https:://p/peeeeiier http://ppereeiee.neeefffrfmrm nww/teeummtttieee ZK9gu019NS
Wanjun Zhong, Siyuan Wang, Duyu Tang, Zenan Xu, Daya Guo, Yining Chen, Jiahai Wang, Jian Yin, Ming Zhou, and Nan Duan. Analytical reasoning of text. In Findings of the Association for Computational Linguislics: NAACL 2022, pp. 2306 2319, Seattle, United States, July 2022. Association for Compula- tional Linguistics. doi: 10.18653/v /v1 htt.1//....nmmi//.... findings--aaee na7cl.177 URL httpss///cccaathooooo.oorgg/////
Findings-naacl.17
Wanjun Zhong, Ruixiang Cui, Yiduo Guo, Yaobo Liang, Shuai Lu, Yanlin Wang, Amin Saied, Weizhu Chen, and Nan Duan. Agieval: A human-centric benchmark for evaluating foundation models. arXie preprint arXiv:2304.0630 2023.
Andy Zhou, Kai Yan, Michal Gilapentooh-Rottmmae Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models, 2024a. URL httts::/opeerreveer
net/forumPid--LLNTTIJ.J..
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Represenlations, 2023.
URL /ttpp::/
Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. Webarena: A realistic web environment for building autonomous agents. In The Twelfth International Conference on Learning Representations, 2024b. URL https://openrevier: net/forum fott/forrmmidddooneeeee oKn966ytx
Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Milra, Victor Bursslyn, Ryan A. Rossi, Somdeb Sarkhel, and Chao Zhang. Toolchain:: Efficient action space navigation in large language models with a search. In The Twelfth International Conference on Learning Representations, 2024. URL https://openrevize net/forum? Bidoouuuiid
44


Reviews:
[{"review_id": "PqO9ZUwVOL", "reviewer": "Reviewer_G9WE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The survey is comprehensive and sufficient. This work takes a sufficient and comprehensive survey for the test-time computation. There are enough papers are introduced in this work.\n* The paper is well-written with good structure. \n* The paper contains many tables to help readers understand the different areas of test-time computation. For each Table, the authors cite sufficient papers and give detailed introductions so that it it easy to understand. For the important algorithms, the authors also gives very detailed descriptions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work conduct a survey for test-time computation, including tasks, LLM profiling, search algorithms, and relevant frameworks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* The Introduction part is too short. Please give more description in the introduction part.\n* There is some red color text in the survey, while the text seems not special. Hence, this should be revised in the final version.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2jgo5L6qQ3", "reviewer": "Reviewer_G1yV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper researches on a large number of related works and provides an integrated view of the techniques used in LLM compute scaling studies.\n- The authors propose a unified framework.\n- The paper provides detailed tables and diagrams which is a good summary for readers to get familiar with this field.\n\nWeaknesses:\nAlthough the survey is comprehensive and provides an extensive review of existing literature, merely summarizing and unifying others’ work is not sufficient for a TMLR publication, especially given there have already been many surveys mentioned by this study. The authors should incorporate more original contributions. Additionally, the work lacks experimental validation, such as comparative analyses of different approaches, which diminishes its practical impact.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary:\n\nThis paper presents a survey on large language model test-time computing scaling with search. The authors call it LLM inference via Search (LIS). They propose to to use a unified formulation based on Markov Decision Processes and it covers a range of tasks. The survey contains three major parts: task definitions, LLM profiling, and modular search procedures. In addition, the paper compares over 25 frameworks and provide details tables and diagrams.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Including more original contributions like experimental validation and new insights.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Is23EXAcCw", "reviewer": "Reviewer_F53r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The reviewer is generally happy with the survey structure and feel it is well organized. \n2. The paper is clear to the reviewer and can be a reasonable survey / review paper to the community.\n\nWeakness:\n1. The reviewer is a bit surprised to see the number of references as a survey paper for such a topic (that is close to the hot topic on LLM agents), which looks small. There're ~30 references excluding generic surveys / books / paper (e.g., the old CoT paper). Can the authors justify the situation? To be clear, comparing with other papers in Table 1 is not convincing as those papers are not dedicated surveys, with just have one related section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a technical survey/review on LLM inference via search. The paper provides a unified view from task definition, LLM profiling, and search procedures. 11 frameworks are examined with moderate technical details. More specifically, the paper describes a unified MDP task definition and mapped major tasks in the definition. Then the paper discusses LLM-Profiled roles (policy, transition, etc). The structure decouples search procedure and search algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The major concern for this kind of work with such a fast moving field is timeliness. From Tables such as Table 7, it is relatively clear that there is a bias towards pre-2024 work. (to be clear, they should be discussed). I would request the authors at least discuss more recent work to the best effort during the revision period, for example, those will appear in ICLR this year. \n\nTable 3 has space issue.", "broader_impact_concerns": "This is a survey paper. I don't see concerning claims.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most reviewers find the survey comprehensive and sufficient for the specific topic of LLM inference via search.

One reviewer expressed concern about the narrower scope compared to broader topics such as general LLM inference or LLM agents. However, inference via search is a rapidly growing and important research area, and this survey offers a timely summary of relevant works for researchers new to the field.

Another main concern was that the submission merely summarizes others’ work and that there are already many surveys on the topic. It “lacks experimental validation, such as comparative analyses of different approaches”. Follow-up discussion clarified that this is a unique survey specifically focused on LLM inference via search. Furthermore, according to the TMLR Submission Guidelines, “surveys that … highlight trends … in an area” fall within scope.

Based on this reasoning, the submission meets the two acceptance criteria.
Decision: Accept (poster)