Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries
Authors: Sumedh Pendurkar
Guni Sharon
Venue: Accepted by TMLR ()

Abstract: Recent studies explored integrating state-space search algorithms with Language Models (LM) to perform look-ahead on the token generation process, the ``Tree-of-Thoughts'' (ToT), generated by LMs, thereby improving performance on problem-solving tasks. However, the affiliated search algorithms often overlook the significant computational costs associated with LM inference, particularly in scenarios with constrained computational budgets. Consequently, we address the problem of improving LM performance on problem-solving tasks under limited computational budgets. We demonstrate how the probabilities assigned to thoughts by LMs can serve as a heuristic to guide search within the ToT framework, thereby reducing the number of thought evaluations. Building on this insight, we adapt a heuristic search algorithm, Levin Tree Search (LTS), to the ToT framework, which leverages LMs as policies to guide the tree exploration efficiently. We extend the theoretical results of LTS by showing that, for ToT (a pruned tree), LTS guarantees a bound on the number of states expanded, and consequently, on the number of thoughts generated. Additionally, we analyze the sensitivity of this bound to the temperature values commonly used in the final softmax layer of the LM. Empirical evaluation under a fixed LM query budget demonstrates that LTS consistently achieves comparable or higher accuracy than baseline search algorithms within the ToT framework, across three domains (Blocksworld, PrOntoQA, Array Sorting) and four distinct LMs. These findings highlight the efficacy of LTS on ToT, particularly in enabling cost-effective and time-efficient problem-solving, making it well-suited for latency-critical and resource-constrained applications.

Published in Transactions on Machine Learning Research (12/2025)
Policy-Guided Search on Tree-of-Thought, for Efficient Problem Solving with Bounded Language Model Queries
Sumedh Pendurkar
sumedhppendurkarrttmm..dl
Deportment of Computer Science & Engineering
Texas ABM University
Guni Sharon
gumni Gtama edu
Deportment of Computer Science & Engineering Texas ABM University
Reviewed on OpenReview: https: // openreveew. net/ met/ forum? id=
Abstract
Recent studies explored integrating state-space search algorithms with Language Models (LM) to perform look-ahead on the token generation process, the "Tree-ofTThoughts (ToT), generated by LMs, thereby improving performance on problem-solving lasks. However, the affiliated search algorithms often overlook the significant computational costs associated with LM inference, particularly in scenarios with constrained computational budgets. Con- sequently, we address the problem of improving LM performance on problem-solving tasks under limited computational budgets. We demonstrate how the probabilities assigned to thoughts by LMs serve as a heuristic to guide search within the ToT framework, thereby reducing the number of thought ovaluations. Building on this insight, we adapt heuristic search algorithm, Levin Tree Search (LTS), to the ToT framework, which leverages LMs as policies to guide the tree exploration efficiently. We extend the theoretical results of LTS by showing that, for ToT (a pruned tree), LTS guarantees a bound on the number of states expanded, and consequently, on the number of thoughts generated. Additionally, we analyze the sensitivity of this bound to the temperature values commonly used in the final softmax layer of the LM. Empirical evaluation under fixed LM query budget demonstrates that LTS consistently achieves comparable or higher accuracy than baseline search algo- rithms within the ToT framework, across three domains (Blocksworld, PrOntoQA, Array Sorting) and four distinct LMs. These findings highlight the efficacy LTS on ToT, par- licularly enabling cost-effective and time-efficient problem-solving, making well-suited for latency-critieat and resource-constrainnd applications.
1 Introduction
Language Models (LMs) have demonstrated promising performance across a wide range of natural language processing tasks (Brown et al. 2020 Chowdhery et al. 2023 Achiam et al. 2023). ). Although LMs are effective on wide range of language understanding and generation tasks, complex problem-solving tasks such as reasoning tasks remain challenging and often require additional techniques to improve performance. Recent prompting strategies, such as Chain-of- Thought (CoT) prompting (Wei al. 2022), improve performance such tasks by eliciting intermediate reasoning steps before producing final response. Building on this idca, methods such as Tree-of- Tree-of-Thouugh Thoughts (ToT) (Yao et al. 2023 (sce Figure 1 and Maassoning-andPlannnne (RAP) (ao el al. 2023) generate structured reasoning trajectories in the form of search trees. These trees are formed by exploring multiple coherent intermediate sequences of tokens, or thoughts, at each decision point. Furthermore, approaches like ToT and RAP employ state-space search (referred as "scarch") algorithms navigate the generated search trees and produce a final response. For instance, ToT (Yao et al. 2023) method proposed using depth first search (DFS) (Commen al. 2022 or beam search. (BS) (Sutskever al.

---

Published in Transactions on Machine Learning Research (12/2025)
2014] while RAP (Hao et al. 2023 used Monte-Care Tree Search (MCTS) (Kocsis & Szepesvári 2006)
the search algorithm. These approaches have demonstrated significant improvements on complex reasoning tasks compared to standard LM decoding methods that generate responses by greedily selecting tokens without additional exploration.
While these approaches can be effective, the im- provements come the cost of increased inference- time computation. Generating and evaluating mul- tiple reasoning paths requires repeated LM queries, which can be expensive, especially as the size of LMs increases, as highlighted in recent work (Snell et al.) 2024 Muennighoff et al. 2025). To address this is- sue, we focus on improving LM performance under a strictly constrained computational budget, where compute is measured by the number of generated thoughts. Since each thought consists of a sequence of tokens, minimizing the number of thoughts also reduces the total number of LM queries, assuming the average length of each thought remains approx- imately constant. To this end, we explore adapta- tions of search algorithms within the ToT framework to elicit better LM responses when the number of al- lowable thought gencrations limited.
Prompt x: 'Rubik's Cube puzzle with 6 laces Give slep by slep instruction to solve the problen"
Oter Thoughts
Theught
Thought Rooee
4o0se top race counter
kiod Face Counter
Thought
Plece
Though Fax Chachens
Thought Roaa Face
Thought Hoom Codocas
We begin with an observation: explicitly evaluating intermediate thoughts using LMs, commonly per- formed to rank and pick thoughts to expand, ra- quires additional LM queries. Given this under- standing, we propose using the LM as policy, map- ping from a partial sequence of thoughts (state) to distribution over next thoughts (neighboring states), thereby guiding the search without requiring addi- tional evaluation queries. Building on this obser- vation, we adapt Levin Tree Search (LTS) (Orsau et al. 2018) to the ToT framework, which directly leverages LM as a policy to effectively guide the search. Further, we extend the theoretical guarantee the number of state expansions, and consequently on the number of thoughts generated, from the orig- inal LTS formulation on generic scarch trees OOscau let al. 2018) to the ToT framework. Note that the original LTS theoretical expansion bound does not directly apply to the ToT framework due pruned structure. Moreover, we analyze the sensi-
Theugh Face deskk
Thegge Rersen Right
X
Response Face Rotate Clockwite."
Figure 1: Illustration of the Tree-of- Theough-T (ToT) framework applied Rubik's Cube domain. Cube states with red or green backgrounds represent termi- nal states determined by the LM, while gray indi- cates intermediate states. The green background de- notes goal state. States marked with cross repre- sent invalid states (not known during search) resulting from thoughts that are infeasible for the domain.
tivity of the bound on the number of thoughts generated, to the temperature parameter, commonly used in the final softmax layer of LMs. Experimental results three representative domains (Blocksworld, PrOn- toQA, Array Sorting) demonstrate that LTS consistently matches or exceeds the accuracy of guided DFS and beam search, search algorithms considered in the original ToT work (Yao et al. 2023). under tight computational budgets. Further, the results show that LTS is competitive or better than guided DFS across three domains and four different LMs.
1 See http for our code.
2

---

Published in Transactions on Machine Learning Research (12/2025)
2 Preliminaries
2.1 Problem Formulation
Let X' denote discrete space of all possible tokens, where a token refers to a basic unit of text such as word, subword, punctuation mark. The definition of a token is specific to the tokenizer of given language model (see for example (Grattafiori et al., 2024)). ). A single token is denoted with non-bold letter, e.g. x E X, while sequence of tokens is denoted with a bold letter, e.g., x = (2,, A language model (LM),, defines a probability distribution over a token given a sequence of previous tokens. Formally, + p:d"
A(2), where ((x) is the probability simplex over X' and n is the maximum context length 2 Given a language model p and an input sequence x = ALG, generates response y ALG(p, x). For example, this can be done in a greedy way by selecting p(y:(x) arg max p(3s U1, 122 ,- x)) In this paper, we assume access to an evaluator that determines whether response is valid not (see Section | for details). In our experiments, we consider a fixed sized lest set D (x1, X2....,.. ...). The decoding methods solve problem-solving lasks, represented by an input sequence x; by generating responses y; such that y, can be considered "valid" by the domain-specific evaluator.
In); an anloregressive decoding method,
We consider the Tree-of- Thoughhts (ToT) Yao et al. 2023) framework for decoding by generating a tree over thoughts. Following (Yao al. 2023), a sequence of tokens (t1,t,,...,44 is said to be a thought if it is coherent language sequence. The probability of thought being selected is given by p(t/x) I I (4..1,,,)).... A sequence of thoughts generated in an autoregressive manner, with the final thought being the end-of-sequence token, constitutes a response y. The original ToT framework suggests two ways of generating next thoughts, (1) sampling - by sampling from the distribution t, p(t,/t1, tt..,,tt............... x),, (2) propose-promphr - using specially designed prompts to generate multiple next thoughts in one go, for example, sequentially listing all actions by appending to output as part of the LM response. Initially, we consider an alternate strategy, where we consider all possible thoughts that could be generated given {t1, t2, x). This generates a tree, T, where each node, referred to as a state s E S, is a function of the input query x and the thoughts considered up to that point. The thoughts, t, are edges in T. The neighbor states of s are obtained by appending LM generated thoughts to s. s.thoughss, where s.hhoughts denotes the sequence of thoughts generated up to state 8. This process of generating the neighbors (thoughts) is referred to as expansion. Note, in T, each state commonly has very high out-degree (referred as branching factor). The sampling and propose-prompts based thought generation methods could reduce the branching factor and consequently the search space. We discuss the impact of such methods in Section 3 The descendants of a state in a tree are all states reachable by traversing one or more edges originating from that state. We denote the start state (root node) as 80 where so thoughts = o. The depth of a state in a tree T given by g(s) and we denote depth of the start state as O, that is, g(so) O. Let H S S be set of terminal states where the final thought generated consists solely of the end-of-sequence token. A subset of the terminal states Z C H are valid goal states where Vz E Z the final response, z.thoughts, is considered valid by the evaluator. The goal of the decoding method is to generate final response by finding start-to-goal path in tree T. See Figure [ for an example ToT.
Note, previous methods (Yao et al.) 2023 have considered generating multiple start-to-goal paths, and selecting one path (response) by using heuristic driven (LM based) scoring of responses. As we concerned with budget scenarios we only consider the case where the search algorithms return the first solution found as additional calls to LMs are expensive.
2.2 Background
Our proposed methods integrates and exlends prior work from the LM and heuristic search literature. As such, we discuss the relevant methods.
Prompt-Based and Search-Basee Problem Solving: Chain-of Thoughh (CoT) prompting and its vari-
ants Wei et al. 2022 Kojima et al. 2022) have shown that complex problem solving tasks such as reasoning
2IF the input given LM smaller than n the input padded.
3

---

Published in Transactions on Machine Learning Research (12/2025)
tasks can be more effectively solved by decomposing the solution process into sequence of intermediate thoughts. Since CoT selects the next thoughts greedily, it can get stuck in locally optimal paths. Self- Consistency (Wang et al. 2023) mitigates this by sampling multiple paths and selecting the final answer through majority voting. Least-to-Most prompting (Zhou et al.) 2023) decomposes the original question into simpler sub-questions, which are then answered sequentially to build up to the final solution. Tree- of- of-Thoughts (ToT) (Yao et al.) 2023) generalizes CoT by treating problem-solving as a tree search over thoughts, allowing backtracking and exploration of multiple paths over the tree using search algorithms, namely, deam search (BS) and guided Depth First Search (DFS). Guided Depth-First Search (referred to DFS henceforth) is variant of the standard DFS algorithm in which states are evaluated, and the top-ranked state, according to the evaluation function, is selected for expansion. Beam Search is a search algorithm that maintains a fixed number of lop-ranked states at each depth, and expands them in parallel. Both DFS and Beam Search use LM to evaluate the states. Reasoning- -anoooinng-an----e -aaaag---dd-Pll-aingg Planning (RAP) (Hao et al., 2023) further extends this line of work by using LMs as reward functions to evaluate partial reasoning chains, for Monte- Carlo Tree Search (MCTS) (Kocsis & Szepesvári 20066), enabling better performance. Our paper tackles problem-solving tasks similar to those addressed by the Ofee-of-Thoughe
(ToT) framework, but under a highly limited computational budget. Note, (Zhuang et al. 2024) also address the problem of efficient tree space navigation by leveraging the A scarch algorithm (Hart et al., 1968). However, their method assumes access to well-defined cost functions for evaluating states in the search tree. These cost functions are either task-specific or derived from heuristics built on demonstration memory and the LM itself. Thus, they could be hard to obtain for general LM problem-solving tasks. In contrast, our proposed approach relaxes this requirement by operating directly over the probabilistic structure induced by the LM (ToT), avoiding the need for handcrafted retrieved cost functions.
LMs for Planning Problems:
Given the recent advancements in LMs (Grattafiori et al. 2024 Achiam et al. 2023) and the integration of ML with planning problems (Orseau et al. 2018 Agostinelli et al. 2019: Pendurkar et al. 2024), recent work has examined integrating LMs and planning solvers. Examples of such
integration include (Singh et al. 2023 Ding et al. 2023 Liu et al. 2023 Katz et al. 2024). For instance, (Liu et al. 2023) translates natural language instructions into symbolic planning languages like Planning Domain Description Language (PDDL) MMeDrmott, 2000) and uses classical planning algorithms. Further, recent work (Koh et al. 2024 Zhou et al.) 2024), has explored using LMs to navigate the internet (web automation). However, such modh restrict the environment by enforcing structure on LM-generated actions (or thoughts) (Liu et al. 2023) or by using a fixed set of actions (Koh et al.) 2024) thereby reducing their applicability to domains such as mathematics and logical reasoning. In contrast, our method, built upon the ToT framework, imposes no such constraints, making it broadly applicable to domains where such representations may be infeasible.
Learning and Search-Based Problem Solving with LMs: Another line of work also supports the general idea of scaling test-time compute but relies on additional learning (Muennighoff et al., 2025 Li 2025)
For instance, the Policy-Guided Tree Search (PGTS) approach [Li] 2025) investigates using learned policy to navigate the rcasoning search space. However, their method requires additional training of the policy, which can be challenging in settings where supervised signals or reward functions are sparse or expensive to obtain. In contrast, our approach avoids such additional training overhead and remains applicable even in low-resource or inference only scenarios.
2.2.1 Levin Tree Search (LTS)
Levin Tree Search (LTS) OOseau et al. 2018) is a policy-guided search algorithm used to solve state-space search problems. LTS uses a policy π : S + A(S), that maps a state E S to a distribution over next possible states, as a heuristic to effectively navigate the search space. Note, this mapping can be viewed as a distribution over the actions (thoughts) following the original formulation (Orscau et al. 2018). LTS follows a breadth-first search or A (Hart et al. 1968) like structure where the priority of each state is given by min cs). Here, cost(s;) = a(s,) where (<x) is defined as the probability of being at state 8; where x(*)
7 (s:) M T(3 Sg. s1,,.,,,,,....... where (sp, $1,..., context. of state-space search literature, a search algorithm is said expand in best-first order with respect
......,,)] }t} } is the path from so to S in the tree. In the
4

---

Published in Transactions on Machine Learning Research (12/2025)
0.51
0.49
0.51
0.49
0.92
4.08
11.76
11.78
0.5
3.18
(a) DFS
(b) LTS
Figure 2: Comparison of states expanded by DFS and LTS. State denotes the starting state and the green state indicates a goal state. The values on edges denote the probability of the next state being selected given the previous state. DFS uses these probabilities rewards guide the search. The value inside each state for LTS represents cost g(s)/m(s). The blue and purple states represent the states expanded by DFS and LTS, respectively.
to cost function cost(8) if, for all states and 82, whenever cost(81) < cosl(s2), then is expanded before
The following results from Orseau et al. 2018 Theorem 2, Theorem 3) hold for any tree
Theorem 1. LTS expands states in best-first order.
Theorem 2. Given tree T and terminal states H, LTS with policy ensures that the number of state expansions N before reaching any of the terminal states is bounded by
N(T, H) S min g(8) sE (s))
2.2.2 Problems with Depth First Search on ToT
In this section, we present a case (with an illustrative example) that suggests DFS, although efficient in its use of LM queries, may not always be the most effective scarch algorithm for problem-solving tasks. Consider the simple instance depicted in Figure 2 with one goal state (and no additional lerminal states) highlighted in green. We restrict our attention to binary tree, where each state has exactly two successors. Here we assume that the probability values are used as rewards for DFS to select states for expansion. Since DES follows a greedy strategy, it commits to one (the left, without loss of generality) subtree first and ends up exploring the states in that subtree. Only after failing to find the goal state does backtrack and explore the right subtree, where it eventually finds the goal. Whereas for LTS, the successors of the root's left successor each have cosl of 3/(0.51
11.76, which is higher than right successor of root which has cost of 6.12 and the goal state with cost se 8.16. As result, LTS switches to exploring the right subtree, finding the goal state without ever exploring the remainder of the left subtree. Additionally, if we consider the case when all leaf states are terminal states, DFS will return the left most leaf state as the encountered terminal state, which not a goal state, thereby returning the incorrect solution. Whereas for LTS, the behavior remains unchanged from the previous case, and will find the goal state (though potentially requiring more exploration than DFS). This case is reflected our experimental findings (Section 4 where DFS might reach a terminal state more quickly than LTS but often fails to find the goal state, resulting in lower overall accuracy. We refer to this the comtrttenmmmmmment problem of DFS.
While the Theorem 2 holds more generally graphs with re-expansions, we here the context trees, which aligns with ToT framework.
5

---

Published in Transactions on Machine Learning Research (12/2025)
3 Levin Tree Search with ToT
Guided DFS has two main limitations (1) It requires additional LM queries to determine which state to expand further, and (2) the problem initial-commitment as discussed in Section 2.2.2 To overcome these limitations, we extend LTS to the ToT framework. We use the LM p as policy that provides distribution over possible next thoughts, conditioned on the previously generated token sequence, described in Section 2.1] In order to adapt to ToT, we propose the following changes. First, given the high vocabulary size of LMs (# tokens) I.c., high branching factor, thoughts t; p(t][t1, 12, 1, x), discussed by Yao el al. (2023). We sample total of bmax thoughts per expansion. Note that, since we use the LM to guide the search, methods are not applicable to LTS. This is bocause such methods generate thoughts sequentially (and not independenttly). As result, the probability values assigned by the LM during generation are conditioned on previously generated thoughts and, therefore, cannot be directly interpreted as independent heuristic scores. Second, following (Hao et al., 2023), we remove duplicate thoughts generated by sampling. We denote such a subtree of T T. Lastly, since LTS operates over tree (rather than graph), including state-cuts (Orseau et al. 2018 is not meaningful due to the absence of cycles and are, therefore, excluded. The adapted LTS algorithm hm is presented in Algorithm
the sampling technique to generate next
pappose-prompt-beee
thought generation
Algorithm Levin Tree Search
1: Input: Query budget b, start state so, LM p
2: Output: start-to-terminal state path so to E H Initialize F F {so}
b (sequence of tokens/LM response)
while F + and LM queries s b do
8 + arg min,eF g(s) 6: remove 8 from F
R(s)
7: is terminal state then
return path 8p end if
10: A < p(lls).sample()
> Generate Thoughts
11: Generate neighbor states C by applying E A to
12: F
13: end while
Sampling-based methods may expand states in T in an order that does not follow best-first order. This follows as sampling can potentially prune the best states (with respect to the cost function), and thus the state and its descendants might not be expanded. Therefore, Theorem and thus Theorem do not hold (as originally stated) for the ToT framework. Nevertheless, by following similar line of reasoning, derive an analogous bound in which the minimum is taken over the set of terminal states in the sampled subtree T,, rather than over H.
Proposition Given a tree T, as the terminal states of T, subtree generated by sampling, and H' C H as terminal states in T, LTS with a policy स ensures that the number of slate expansions N before reaching any of the terminal states in H' is bounded by
N(T, H') < min g(s) EE (T))
Proof. Let Te represent the partial search tree consisting only those states that have been expanded by the time the first terminal state 8, = arg min *(s) is expanded during the search process on T. Let C(T.) denote the leaves of the partial search tree To, Let min terminal state 8y is expanded, all other states expanded by LTS have lower cost than Thus g(n) S ((n)c
2(s) be the cost of 8g. When the first т(*)

---

Published in Transactions on Machine Learning Research (12/2025)
for all states Te expanded by LTS. Therefore,
a(n)e c= min g(s)
N()) RECITE)
Σ g(n)
E
sEff' (())
REC(T.)
Given Proposition 1 [and maximum branching factor bmax, the number of thoughts generated can be upper bounded as follows
Corollary 1. Given tree T, H as the terminal states of T, subtree T generated by sampling with buax branching factor, and H' S H as terminal states in T, LTS with policy ensures that the number of thoughts generaled, M, before reaching any of the terminal states in H' is bounded by
M(T, H²) S bmax min ((8
"EH' π (s)
Note on Renormalization: It might seem intuitive re-normalize the sampled thoughts using method like softmax. However, comparing cost of states with different parents (Line 6, Algorithm can be coun- terintuitive. For example, if the children of state have uniform probability distribution, after renormal- ization, each thought, would have 1/bmax probability of being selected. These values are overestimated when compared to other states where probability density is concentrated in top bmax thoughts (sorted with non-increasing probability). This overestimation can mislcad the search by making uniformly low confidence thoughts appear more favorable than genuinely high confidence thoughts from other parts of the tree.
3.1 Sensitivity Temperature Parameter
In this section, we analyze the sensitivity of the number of thought generations with respect to the tem- perature parameter in the final LM softmax layer. We consider a vocabulary of size V, where token i corresponds to the ęth index in the vocabulary. The probability of selecting yi, given the context (not shown for brevity), is given by
dilT
(+())
(1)
Ey-eeb/t
where f,....,ey by are the logits of the final layer for a vocabulary of size V.
We assume that we have single goal state 8g, and no other terminal states. For solution path (so...., Syh from 8o lo 8g, we define sulficiently accurate LM as Definition A language model (LM) said to be sufficiently accurate if the following condition holds for all tokens y Y9, where Y the sequence of tokens selected along the solution poth from so to sgi
v
-
for some non-negative scalar A 2 where the i-th index corresponds to token along the solution path.
Theorem 3. For sufficiently accurate LM with a fixed paromeler v, let the sampling distribution of lokens be specified by Equation Let each thought consist of at most tokens and assume that the state sg achieving the minimum for Corollary 1 unique. We have
0M H') < brna g( k
0T
T(sy)² 72

---

Published in Transactions on Machine Learning Research (12/2025)
Proof. We first consider the partial derivative of pr (36).
(E (2/ (E)
- -cal/t)
( Σ Or Ej=zes/1
(u))
θr
(= 8 clil
EE/=1 =305317
(Let S= Ej=1eh el/T)
S
d:lt
V
6//l
-b, Σ
Eg
725
j=1
(vi)
2 +
Σ
(1))
(Since p+(y)) c/1/7/8)
j=1
Pr (vi)
Σ pr (1s) -()
(Since Σn Pr (M() 1, use -4e -- -E (upr(1)))
Next, we consider the derivative for the probability of generating thought of at most k tokens, t "",,"""""" We have p+(t)= = =I (1)
0p-(t)
Op-(v")
Σ
II (T(('")
(Product rule)
Or
j=l
Öp (V')
U14y p(w:) S 1)
j=1
Now we analyze the derivative of number of thoughts generated with respect to temperature. Consider a state at depth g(s) and we have that ((s) = (s). Each state before this state consists of most g(s) thoughts, each containing at most i tokens. Since there is unique path to any state simply extending the calculation above, obtain
@T(s) dT
Opr(y")
<
(2)
d:
j=1
Note, we ignore indexing notation for the outer summation for brevity.
From Corollary M (T, H') < 6mxx min,eH Z
a(s)
Since we assume that the minimum is achieved at a unique
state 8g: using Danskin's 's theorem (Danskin
1969 we obtain
8

---

Published in Transactions on Machine Learning Research (12/2025)
0 (T, H)
θ (({g)
dmax θr π T
bmax -g(5g) 8 (sg) xs Ōr
Denoting token along solution path with you with 1th token the thought
-bmax g(sg)
(From Eq 2.)
T(3)) 1
84 j=1
mmax g($y)
(y
V
pr (v22)) (ti))())))
6.))
Σ
(i is the optimal token index)
T(80)² 2 84 j=l
x2
mmxx g(3μ)
Pr (yow) (-a+)
(From Definition 1)
T(80)²
j=l
g($y)
k
bmax
T(s))²
j=l
b g(8g)
h + ((5g
T(g))2
72
g 2
= bmax
TT T80))²
)2
72
The gradient depends inversely on the square of the probability of state Sg: that is, =(sg), and the temperature т. Based on this dependence, we note that the number of thought gencrations depend the values of =sg)) and т. Increasing 7 causes the probabilities to become more uniform and, in turn, decreases x(ss) when the path from so to sy is the most likely path. If the change is such that the product (sy)) 7 remains relatively stable, we can expect the number of expansions to be somewhat robust to a change in the temperature. The main inference that can be drawn is that the upper bound is non-negative number. This suggests that increasing T will lead to an increase in the number of LM queries, given that the LM is sufficiently accurate. In experiments we observed that it was often the case that the ToT had multiple goal nodes, as opposed to the thcoretical assumption. As such, the thcoretical results should be viewed as a general guidance for temperature tuning and not as strict bound.
Remark:
4 Experiments
This section aims compare the performance of LTS, DFS, and beam search across multiple domains under varying but constrained LM query budgets.
4.1 Setup
This work builds upon the implementation by Hao al. (002)). The thought generation temperature parameter 7 was set to 0.8. Top-k sampling (Fan et al. 2018 used with k=50. The maximum branching factor bmaz for all search algorithms was set to 3. Duplicate thoughts were removed, as duplication is possible during sampling. These hyperparameters were selected following the litcrature (Hao et al.) 2023 For LTS, the temperature for state evaluation (distinct from thought generation) was set to 1 unless staled herwiie.. A small value (~ 10 10-14) was added to the denominator of the cost function (to σ) in the LTS algorithm avoid division by All search algorithms were terminated when either (1) the first terminal state was expanded or (2) a predefined budget was exceeded. The budget measured as the number of thoughts generated, where each thought is counted twice if additional LM queries made for state evaluation.
9

---

Published in Transactions on Machine Learning Research (12/2025)
The budget was counted twice for DFS and beam search, it requires additional LM queries to evaluate the state. This assumes the cost of thought generation is similar to that of state-evaluation. Algorithms were terminated when the first terminal state was found, instead of expanding multiple terminal states and selecting the best, as done in (Hao et al. 2023), to avoid the additional computational overhead from extra LM queries. Our focus is on scenarios with highly limited compute budgets, such as edge-device deployments. Therefore, our experiments and comparisons are restricted to low-budget settings to evaluate performance under tightt-computational constraints. We use the Llama 3 instruct models (Grattafiori et al. 2024) (IB, 3B, and 8B), as well as Qwen 2 models (7B) (Team et al. 2024) as LMs in our experiments for two main reasons. First, we aim to evaluate our method under constrained inference settings, and smaller models allow us to rigorously assess test-time compute efficiency in compute-limited scenarios, which is a core focus of this work. Second, Llama and Qwen models are open-weight, high-quality LMs that offer competitive performance (Grattafiori et al., 2024). We note that our method is general and agnostic to the choice of LM, and we expect our findings to extend to other small-scale models beyond Llama models.
4.2 Domains
We selected benchmarks following established practices in the ToT literature (Yao et al. 2023 Hao et al. 2023), using PrOntoQA, Blocksworld and a novel Sort as our primary evaluation domains. We did not evaluate all domains from prior work due to practical constraints with small LMs. Specifically, domains such as Game of 24 and Crosswords were excluded because preliminary experiments with Llama-3.2-1D showed high rates of invalid action generation (>40% for Game of 24), where the model produced syntactically incorrect operations or malformed outputs. Since our focus is evaluating search algorithms rather than action validity mechanisms, domains where the base model cannot reliably generate valid actions prevent meaningful algorithmic comparison. StrategyQA was excluded following Yao et al. (2023), who noted that "CoT already very good on such tasks, and Strategy QA's bottleneck is external knowledge, not reasoning." Creative writing was not included as involves relatively shallow scarch trees, limiting our ability to study the effectiveness of search algorithms.
Blocksworid (BW):
commonly used We consider the Blocksworld domain Valmeekam et al, 2022 2023
in hcuristic scarch literature (Pendurkar et al., 2022; 2023), which involves arranging blocks on an infinite table. Given start and goal configurations, the task is to perform a sequence of actions (represented as thoughts) that transition the system from the start to the goal arrangement. The prompt specifies the available actions, which include stack, unstack, put, and pickup, each potentially taking block names as arguments depending on the action. A state is said to be terminal if the most recent thought starts with [PLAN END] the max search depth has reached. We follow the same instance grouping strategy as (Hao et al. (023).. where BW (step 2) denotes instances solvable with a search depth of 2. We evaluate depths 2, 4, 6, 8, 10, and 12 in our experiments.
PrOntoQA: We consider the PrOntoQA (Saparov & He 2023) domain and follow the same setup as in Hao et al. 2023). Specifically, we adopt the 'true' ontology setting and the 'random' ordering of rules, and merge examples requiring to reasoning hops. state is terminal the most recent thought begins with The answer is. We use the same 500 sampled instances Hao et al. (2023), generated using the script provided by (Saparo&& & He (2023). The maximum search depth was set to 10.
Array Sorting (Sort): We consider the task of sorting array with fixed size of 5 elements, referred to as the Sort domain. The input prompt instructs the LM to perform the sorting using only pairwise swaps, i.c., each thought involves swapping exactly two elements. The array elements may be negative or positive and can include a single decimal point. A terminal state is a state where the most recent thought begins with Answer: The prompt includes rustiins so LM is properly instructed. The dataset consists of 100 instances, with the numbers randomly generated. The maximum search depth was set to 10.
4.3 Baselines
We consider DFS and beam scarch as the primary basclines for our experiments. The self-evaluation strategy used guide DFS and beam search follows Hao et al.] (2023) for both the BW and PrOntoQA domains. In these domains, the reward for each generated thought is computed by combining two components: (1) the
10

---

Published in Transactions on Machine Learning Research (12/2025)
log probability assigned by the LM to the thought, and (2) self-evaluation score derived from secondary LM prompt that explicitly asks whether the current thought, as an intermediate thought, is valid, using yes/no candidates. For the Sort domain, we rely solely on the LM log probabilities to guide DFS. As a result, each thought is counted as one toward the budget in this setting, since no additional LM queries are required for state evaluation. The bean size used for the beam search algorithm was set to 3, as we observed it offered the best performance for the budgets considered. That is, a higher beam size made beam search sample-inefiicintt, while a lower beam size acted greedily, similar to DFS.
We exclude MCTS discussed in Hao et al 2023) due to its known sample inefficiency (Borges & Oliveira, 2021). Furthermore, we do not compare against the approach of Zhuang et al. (2024), which applics the A search algorithm, because it assumes access to well-defined cost functions that are either handcrafted or derived from demonstrations and heuristics. In contrast, we only consider algorithms that operate directly on the probabilistic structure induced by the LM (ToT), without assuming access to any domain-specific cost functions, as discussed in Section 2.2.1 Consequently, such methods cannot be compared directly to approaches requiring cost, functions that are lypically unavailable in most domains.
4.4 Evaluation
We consider accuracy (success rate) as a metric of evaluation. To determine the correctness of the solution, we assume access to an evaluator, specific to each domain. Note, we do not assume access to an evaluator in real-life scenarios- we select domains where evaluators are accessible to verify the performance of the methods following the literature (Hao et al. 2023 Yao et al. 2023).
BW: The generated sequence of thoughts is validated as a plan using a PDDL planner (Valmeekam et al. 2022 If the plan reaches the specified goal configuration, the terminal state is considered a goal state.
For evaluation, we compare the entire sequence of thoughts against the ground truth answer (with intermediate thoughts) provided in the dataset (Saparov & He 2023), following the 'entire proof evaluation proposed by Hao et al. (2023).
PrOntoQA:
Sort:
The evaluator parses the generated sequence of thoughts to retrieve the sorted array. The evaluator further checks if this array is a sorted version of the input. If the resultant array is sorted, the state is considcred a goal state.
4.5 Results: Comparison with Increasing LM Query Budget
In this section, we compare the performance of LTS, DFS, and beam search on the ToT framework with increasing budgets. We focus on three representative settings: BW (step 2), BW (step 4), and PrOntoQA (first 100 instances) using the LLaMA 3.2 3B Instruct model. We include BW (step 4) instead of the Sort domain, as the Sort domain typically requires very few thoughts to be generated, making performance trends difficult to observe. The results are presented in Figure 3
As expected, accuracy increases with the budget and eventually stagnates. The stagnation is clearly seen for all algorithms for BW (step 2), and for DFS for (step 4). Initially, higher budgets allow the algorithm to solve problem instances that were previously unsolved. Once all instances reach their respective terminal states, additional budget does not yield further improvements. For instance, in BW (step 2), accuracy increases until it plateaus at a budget of 15. We observe that LTS generally outperforms DFS across the settings considered, highlighting the advantages of LTS under both low and high budget regimes. The improvement in the high budget regime can be altributed to the issues with DFS outlined in Section 2.2.2 that is, commimmettmmmmm Further, the improvement in the low budget regime can be attributed to two factors: initial-commimment and DFS typically requiring additional LM queries for state evaluation. These results suggest that LTS generally performs better than DFS across varying LM query budgets.
An exception occurs at intermediate budget ranges, specifically BW (step 4) at a budget of 15, where DFS slightly outperforms LTS. This can be explained by the greedy nature of DFS, which favors deeper expansions and is more likely to reach a terminal state earlier. If the LM is accurate, DFS may solve instances with fewer state expansions than LTS. It is also worth noting that LTS with temperature parameter of zero
11

---

Published in Transactions on Machine Learning Research (12/2025)
Blockswerld (Step
Blocksworld (Step 4)
PrÖntoQA
0.150
0.30
0.125
0.123
0.23
0.100
0.100
0.22
0.275
0.13
0.50
0.500
0.19
0.025
0.025
0.000
0.000
Suddet
Budget
(a) Step 2
(b) Step 4
(c) PrOntoQA (100 instances)
Figure 3: Comparison of accuracy of LTS, DFS, and beam search with increasing budgets across different settings.
(used during search) can emulate DFS behavior if a stability term added at each level and ties in cost are broken in favor higher g(s) values. LTS can thus offer flexibility across different regimes by interpolating between greedy and balanced exploration ToT.
On the other hand, when comparing with the performance of beam search, we can that for BW (step 2) the accuracy higher than DFS (comparable to LTS) suggesting that exploration helps beam search. However, states expanded at each depth, beam search requires significant budget for search especially with increasing complexity resulting in poor accuracy.
In summary, the results suggest that LTS outperforms or matches DFS across varying LMM query budgets. This advantage likely stems from LTS avoiding initial-commitment and incurring fewer LM queries. While beam search performs reasonably well on easier instances (c.g., BW step 2), its performance tends to degrade harder problems due to sample inefficiency.
4.6
Results: Comparison with Increasing Time Budget
Step
BW Scep
PrOnLO
0.4
09
0.10
Rocurety
0.00
0.10
0.09
0.2
0.1
0.00
20
23
30
35
10
20
20
30
25
20
Budger sexonds)
Budget secords)
Tire Budge:
(a) Step
(b) Step
(c) PrOntoQA (100 instances)
Figure 4: Comparison of accuracy of LTS, DFS, and beam search with increasing time budgets across 3 different settings.
In this section, we compare the performance of LTS and DFS using wall-clock time for LM queries (thought generation and evaluation) as the budget metric, rather than the number LM queries.
Figure presents the accuracy of LTS, DFS, and beam scarch across three settings: BW (step 2), BW (step 4), and PrOntoQA (first 100 instances) using the LLaMA 3.2 3B Instruct model. The time budget is measured in seconds.
The results show trends similar to those observed with query-based budgets (Section 4.5 achieves comparable or higher accuracy than DFS across different time budgets. For BW (step 4) and PrOntoQA, LTS demonstrates consistent improvements over DFS. In BW (step 2), we observe that DFS achieves slightly higher accuracy at certain intermediate time budgets, which aligns with the query-basod results and can be attributed DFS's greedy exploration strategy reaching terminal states more quickly when the LM provides accurate guidance.
LTS generally
12

---

Published in Transactions on Machine Learning Research (12/2025)
Table Accuracy (%) of LTS and DFS across different domain settings and models.
Task
Model
Size
LTS
Accuracy
DFS Accuracy
BW (step 2)
Llama 3.2 Instruct
1B
8.9%
8.9%
BW (step 4)
Llama 3.2 Instruct
1B
2.4%
2.4%
BW (step 2)
Llama 3.2 Instruct
3B
15.5%
11.1%
BW (step 4)
Llama 3.2 Instruct
3B
14.3%
9.5%
BW (step 6)
Llama 3.2 Instruct
3B
3.9%
3.3%
BW (step 8)
Llama 3.2 Instruct
3B
1.3%
0.0%
BW (step 10)
Llama 3.2 Instruct
3B
0.0%
0.0%
BW (step 12)
Llama 3.2 Instruct
3B
0.0%
0.0%
BW (step 2)
Llama 3.1 Instruct
8B
33.3%
20.0%
BW (step 4)
Llama 3.1 Instruct
8B
28.6%
19.0%
BW (step 6)
Llama 3.1 Instruct
8B
17.8%
9.2%
BW (step 8)
Llama 3.1 Instruct
8B
10.6%
4.6%
BW (step 10)
Llama 3.1 Instruct
8B
8.0%
7.1%
BW (step 12)
Llama 3.1 Instruct
8B
6.5%
0.0%
BW (step 2)
Qwen 2
7B
31.1%
26.7%
BW (step 4)
Qwen 2
7B
11.9%
10.7%
BW (step 6)
Qwen 2
7B
6.6%
2.0%
BW (step 8)
Qwen 2
7B
2.6%
2.6%
BW (step 10)
Qwen 2
7B
1.8%
0.9%
BW (step 12)
Qwen 2
7B
0.0%
0.0%
Sort
Llama 3.2 Instruct
1B
5.0%
2.0%
Sort
Llama 3.2 Instruct
3B
20.0%
15.0%
Sort
Llama 3.1 Instruct
8B
47.0%
47.0%
Sort
Qwen 2 Instruct
7B
26.0%
22.0%
PrOntoQA
Llama 3.2 Instruct
1B
18.6%
15.6%
PrOntoQA
Llama 3.2 Instruct
3B
27.8%
18.8%
PrOntoQA
Llama 3.1 Instruct
8B
70.4%
49.0%
PrOntoQA
Qwen Instruct
7B
21.6%
12.8%
These findings confirm that the advantages of LTS over DFS extend beyond query efficiency to practical wall-clock time constraints, making it well-suited for latency-oritical applications.
4.7 Results: Comparison when DFS can reach terminal state
In this section, we compare the performance of DFS and LTS across all domain settings and the four LMs considered. We do not consider beam search due to its sample inefficiency, as discussed in previous section. The budget for each domain-IM pair was configured such that DFS could reach a terminal state for every instance. In other words, the budget was tuned to maximize DFS performance, but not for LTS, LTS typically stagnates later than DES (see Figure 3bb. The results higher-step settings in BW with the 1B and 3B LMs are omitted, as both algorithms achieved 0% accuracy, Overall, LTS performed comparably to or better than DFS in all settings. The largest improvement was observed on PrOntoQA and Llama 3.1 8B, with a 21.4% gain in accuracy. Note, since the proposed method is purely inference-only, its performance is inherently constrained by the quality of the heuristic provided by the underlying LM. Consequently, when the LM heuristic weak, we do not expect dramatic improvements in absolute accuracy across tasks. These findings suggest that LTS generally more effective than DFS under constrained budgets and can offer further benefits the budget increases.
summarized in Table [ Results for
13

---

Published in Transactions on Machine Learning Research (12/2025)
4.8 Results: Sensitivity of LTS to Temperature
Figure 5 presents the performance of LTS across different temperature values for the cost func- tion (T 0.5, 1.0, 1.5, 2.0))
function of time budget on Blocksworld Step 4 using Llama 3.2 3B Instruct. Note that the same temperature (r 0.8) was used for thought genera- tion across all experiments; the varied temperature parameter applics only to the cost function computation in LTS (Line 6, Algorithm I alfecting which states are prioritized for expansion. The results reveal three distinct behavioral regimes. Low Temper- ature (T = 0.01): At very low temperature, LT'S exhibits behav- ior similar DFS. The cost function becomes highly sensitive probability differences, causing the algorithm to strongly commit to high high-probabilityy paths. This results in good performance at low bud- gets (4.5% at 5 seconds), but accuracy plateaus early and reaches only ~8.5% at 20 seconds. This plateau occurs due to the initial- commitment problem. Intermediate Temperature (r = 0.5-1.5): At moderate temperatures, LTS demonstrates improved exploration- exploitation balance. These configurations show relatively poor per- formance at lower budgets (3.5 (3.5-3.8% 3.8% at seconds) but steadily im- prove as budget increases, ultimately achieving the highest accura- cies (10.5 12% at 20 seconds). The initial performance deficit occurs because intermediate temperatures encourage broader exploration rather than immediate commitment to high-probability paths. However, this exploratory behavior enables discovery of superior solutions that low-temperature search misses, resulting in continued accuracy improve- ments across the entire budget range. High Temperature (r 2.0): At very high lemperature, LTS exhibits breadth-first search (BFS)-like behavior. The flattened probability distribution causes the algorithm ex- plore states more uniformly, with minimal preference for high-probability paths. This results in the poorest performance at low budgets and modest final accuracy (~2.1% at 20 seconds). While this temperature could eventually achieve competitive performance, it requires substantially more computational budget to reach accuracy levels that intermediate temperatures achieve more efficiently.
BW Step
0.10
0.08
0.04
0.02
0.00
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Time Budget seconds)
Figure 5: LTS performance with vary- ing temperature 7 values.
These results suggest that temperature selection involves a trade-off between early performance and ultimate solution quality. In this domain, т z 0.5-1.0 offers reasonable early performance while maintaining capacity for continued improvement under budget constraints. When maximizing final accuracy is prioritized over early results, 7 se 0.5-1.5 shows promise, though optimal values may slightly vary based domain under consideration.
5
Summary
This work addresses the challenge of improving Language Model (LM) performance on problem-solving tasks under strict LM query constraints. Specifically, focuses on the Troughf-Thoughts (ToT) framework, where search tree generated with edges representing sequences of tokens, thoughts. The paper adapts Levin Tree Search (LTS), policy-guided search algorithm, to this framework. It also extends the theoretical guarantees of LTS to ToT by bounding the number of state expansions and, consequently, the number of LM generated thoughts. Empirical results suggest that LTS achieves accuracy that is comparable to or better than guided depth first search (DFS) and beam search, which were originally proposed by Yao et al. (2023) Further, the results across three domains and four different LMs show that LTS achieves accuracy that is comparable to or better than guided DFS under tight computational budgets. These findings highlight the effectiveness of LTS within the ToT framework and its applicability cost-sensitive and time-sensitive settings.
14

---

Published in Transactions on Machine Learning Research (12/2025)
Acknowledgments
The authors would like to thank Prathamesh Dharangutte for early discussions about this work. The research was conducted in the PiStar Al and Optimization Lab at Texas A&M University. PiStar is supported in part by the NSF (IIS-2236) 2238979....
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Nlee Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.065 088777 2023.
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 188):356 363, 2019.
Alexandre Borges and Arlindo Oliveira. Combining off and on-policy training in model-based reinforcement learning. arXiv preprint 2rXiv:2002.12194, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neolakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neurol information processing systems, 33:1877-1901, 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Thomas Cormen, Charles E. Leiserson, Ronald L, Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
John M Danskin. The theory of max-min min and application weapons allocation problems. New York: Springer, 1969.
Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang. Task and motion planning with large language models for object rearrangement. In 2023 IEFE/RS. International Conference on Intelligent Robots and Systems (IROS), pp. 2086 2092. IEEE, 2023.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 889-898, 2018.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al- Dahle, Aiesha Letmaa, Akhil Mathur, Alan Schelten, Alex Vaughan, al. The llama 3 herd of models. arXiv preprint ar 0rx.c:2407.11783 2024.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang. and Zhiting Hu. Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, pp. 8154 8173, 2023.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
Michael Katz, Harsha Kokel, Kavitha Srinivas, and Shirin Sohrabi Araghi. Thought of search: Planning with language models through the lens of efficiency. Advances in Neural Information Processing Systems, 37:138491-13885 138568, 2024.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp.
Springer, 2006.
Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents. Xiu preprint ar 077::2407.01476, 2024.
15

---

Published in Transactions on Machine Learning Research (12/2025)
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are vero-shot reasoners. Advances in neural information processing systems, 35:22199-2223 2022.
Yang Li. Policy guided tree search for enhanced Ilm reasoning. arXiv preprint arXiv:2502.0681 2025.
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 preprinl arXiv:2304.114 11477, 2023.
Drew M McDermott. The 1998 AI planning systems competition. Al magazine, 21(2):35-35, 2000.
Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettle- moyer, Percy Liang Emmanuel Candès, and Tatsunori Hashimoto. s1: Simple test-time scaling. arXiv preprint ar Xiv:2500. 19393, 2025.
Laurent Orseau, Levi Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 31, 2018.
Sumedh Pendurkar, Taoan Huang, Sven Koenig, and Guni Sharon. discussion on the scalability of heuristic approximators. In Proceedings of the International Symposium on Combinatorial Search, volume 15, pp. 311 313, 2022.
Sumedh Pendurkar, Taoan Huang, Brendan Juba, Jiapeng Zhang, Sven Koenig, and Guni Sharon. The (un) scalability informed hcuristic function estimation in np-hard scarch problems. Transactions on Machine Learning Research, 2023.
Sumodh Pendurkar, Levi HS Lelis, Nathan R Sturtevant, and Guni Sharon. Curriculu generation for learning guiding functions in state-space search algorithms. In Proceedings of the International Symposium on Combinatorial Search, volume 17, pp. 91-99, 2024.
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In The Fleventh International Conference Learning Representations, 2023.
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In 2023 IEEE International Conference Robotics and Automation (ICRA), pp. 11523-11530. IEEE, 2023.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arxiv:2408.00 033114 2024.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Qwen Team et al. Qwen2 technical report. arXiv preprint arXiv:2407.10671 2(3). 2024.
Karthik Valmockam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large language mod- els still can't plan (a benchmark for 1lms on planning and reasoning about change). In NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022.
Karthik Valmeckam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances Neural Information Processing Systems, 36:75993 76005, 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Sclf-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Represenlations, 2023.
Jason Wei, Xuczhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, al. Chain-of thought prompting clicits reasoning in large language models. Advances in neural information processing systems, 35:24824 248337, 2022.
16

---

Published in Transactions on Machine Learning Research (12/2025)
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36:11809 11822, 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Lc, et al. Lcast-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference Learning Represenlations, 2023.
Shuyan Zhou, Frank Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishck Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Webarena: A realistic web environment for building autonomous agents. In The Twelfth International Conference Learning Representations, 2024.
Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, 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 Learning Represenlations, 2024.
17


Reviews:
[{"review_id": "jbHIUMQRb8", "reviewer": "Reviewer_GpBr", "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": "", "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 of Contributions**: This paper proposes Levin Tree Search (LTS) as a principled alternative to standard search strategies such as DFS and Beam Search in Tree-of-Thought (ToT) reasoning with large language models.  The authors adapt theoretical guarantees from LTS to demonstrate bounded expansion complexity and report minor yet consistent improvements over DFS on three symbolic reasoning benchmarks (BlocksWorld, PrOntoQA, and Sort). Overall, the paper provides a clear theoretical framework of ToT as policy-guided search, although its empirical scope and practical validation remain limited.\n\n**Strengths**\n- [**S1**] - **Motivation**: This paper presents a timely and well-motivated approach to decoding in the context of LMs for reasoning tasks.  Overall, the idea of leveraging more sophisticated tree-search algorithms, especially within the limited budget regimes, is excellent.  \n- [**S2**] - **Computation Results**: Overall, there is a relatively consistent trend in improvements over DFS and beam search, so there is some promise to the computational results.  That said, there are some limitations that I will discuss in the weaknesses.  \n\n**Weaknesses**\n- [**W1**] - **Experimental Depth**: The empirical evaluation is limited to three toy benchmarks (BlocksWorld, PrOntoQA, Sort).  While these tasks provide reasonable environments for algorithmic comparison, they do not convincingly demonstrate the method’s generality or robustness in more complex reasoning tasks. The absence of larger, semantically rich benchmarks (e.g., StrategyQA) makes it difficult to assess whether the observed improvements of Levin Tree Search (LTS) over DFS or beam search would hold under more realistic reasoning settings.  Additionally, it would be beneficial to include comparisons with non-budget-limited methods to demonstrate the trade-off in terms of time/budget/quality.  Moreover, with only three tasks and very marginal gains over DFS, I do not find the results strongly convincing.  In addition, the authors consistently report results within a limited budget of prompts; however, including the times would also be informative. \n- [**W2**] - **Ablation**: The paper does not include essential ablation analyses for hyperparameters that strongly influence search behavior and computational efficiency.  Specifically, the branching factor $b_{\\max}$, the temperature $\\tau$ in the LM sampling policy, and the top-$k$ sampling cutoff. Each of these parameters directly affects the trade-off between exploration and exploitation and thereby the total query cost. For example, Section 3.1 presents a theoretical dependence of search cost on $\\tau$, but this relationship is never empirically validated. Similarly, the choices of $b_{\\max}$ and $k$ are fixed without justification or sensitivity analysis, leaving unclear how significantly these parameters affect the trade-off between solution quality and computational burden.  Including these ablations would substantially strengthen the motivation for these parameters, while also providing practical guidance on the trade-offs associated with the proposed method. \n- [**W3**] - **Clarity**: I find this submission to suffer from a lack of clarity.  The abstract is overly jargon-heavy.  The theory is presented with little to no explanation of how these choices impact practicality in this setting, and there is even less empirical justification for it.  While the authors illustrate a DFS failure case, similar counterexamples likely exist for the proposed method, suggesting an unavoidable no-free-lunch trade-off in exploration efficiency.  As such, I don't find this section to be compelling.  Additionally, a brief section on the specific contributions should be included.", "claims_and_evidence_yn": "No", "claims_explanation": "Overall, most of the claims have some evidence.  However, as pointed out in **W1/2** some claims could be strengthened with more robust experimentation.", "audience_yn": "Yes", "audience_explanation": "This paper presents a a policy-guided approach for bounded LM queries, making it a good fit for TMLR.", "requested_changes": "Overall, the authors definiteily need to include ablation on key parameters of their approach **W2** and improve the clarity of the writing **W3**.  Additionally, improvement in the direction of **W1** would strengthen the work.", "broader_impact_concerns": "None.", "additional_comments": "I do not research LMs and have relatively limited experience.  I believe my weaknesses and suggestions for improvement are reasonable, regardless of this.  However, having a reviewer more familiar with the literature, existing baselines, and benchmarks would be helpful in thoroughly assessing the work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pvFxr7xID4", "reviewer": "Reviewer_sEzZ", "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": "", "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 adapts Levin Tree Search (LTS) to the Tree-of-Thoughts (ToT) setting, using LM token/thought probabilities as a policy to prioritize expansions without additional self-evaluation queries; it extends LTS guarantees to pruned, sampling-induced ToT subtrees (Proposition 1, Corollary 1) and analyzes sensitivity to softmax temperature (Theorem 3). 2) Empirically, under fixed query budgets across Blocksworld (multiple depths), PrOntoQA, and a 5-element array-sorting task with Llama-3 (1B/3B/8B), LTS generally matches or exceeds guided DFS and is more budget-efficient than beam search; results include accuracy vs. budget curves and a table tuned so DFS can reach a terminal state. Strengths: principled policy-guided search with budget awareness; a clear theoretical bound adapted to ToT; simple, training-free drop-in replacement for DFS; consistent gains on harder settings. Weaknesses: budgets are counted asymmetrically (DFS incurs double counting when self-evaluating), potentially biasing comparisons; wall-clock/tokencost latency is not reported; accuracy levels on several BW depths remain low; evaluation stops at the first terminal (not necessarily goal) state; experiments exclude stronger/alternative planners (e.g., A*-style ToT variants) and larger LMs; the “sufficiently accurate LM” assumption and uniqueness conditions limit the generality of the temperature analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The adaptation of LTS to ToT is clearly stated with Algorithm 1 and a bound replacing \\min_{s\\in H} by \\min_{s\\in H’} over sampled subtrees; the DFS failure mode is illustrated, and the temperature analysis supplies an interpretable comparative-statics result. 2) Yet the experiments count DFS thoughts twice when using self-evaluation, terminate upon the first terminal rather than the best terminal, and omit latency/token-cost reporting—each choice can tilt the cost-efficiency comparison; accuracy remains modest for many BW depths, and beam search is dismissed as “sample-inefficient” without equalized compute tuning across tasks. 3) The domains (BW, PrOntoQA, toy sorting) and small LMs are a reasonable starting point but limit external validity; ablations on b_{\\max}, k, temperature, and sampling randomness are lite, and comparisons to A*-style ToT methods are only discussed, not executed. Collectively, these choices support the core idea but fall short of a fully convincing case across settings.", "audience_yn": "Yes", "audience_explanation": "Readers working on controllable inference costs, reasoning with small/edge LMs, or routing/planning for agents will find actionable ideas and a baseline worth adding to their stacks. 2) While the scope is limited (small models, synthetic/controlled tasks), the method’s simplicity, theoretical clarity, and noted wins over DFS under tight budgets make it a useful reference and a plausible component in future ToT toolkits.", "requested_changes": "1. Fairness and Budget Accounting (Critical): The paper’s comparison between LTS and DFS is weakened by inconsistent budget definitions—DFS is penalized by double-counting self-evaluations while LTS is not. The authors should re-run experiments with matched. 2. Stopping Criterion Bias (Critical): Current evaluations stop at the first terminal state rather than the best terminal state, unfairly disadvantaging depth-first methods. The authors should modify this to “best-found terminal within budget” or report both variants, clarifying how this affects success rates and search efficiency. 3.The experiments cover only synthetic or simplified reasoning tasks (Blocksworld, PrOntoQA, array sorting) and small models (≤8B). Adding at least one real-world or tool-assisted reasoning benchmark, and testing on a stronger LM or open-weight alternative, would significantly strengthen the empirical claims and generality of findings.", "broader_impact_concerns": "Policy-guided search that favors high-probability continuations risks entrenching LM prior biases (e.g., stereotyping or unsafe defaults) when used in user-facing agents; budget-driven pruning may systematically ignore low-probability but correct branches in safety-critical contexts. 2) If deployed to reduce inference cost at scale, selection pressure toward “cheap but confident” reasoning could degrade deliberative quality unless paired with risk controls; the paper should add guidance on domains requiring fail-safes, human-in-the-loop escalation, and audits for bias amplification under policy-guided pruning.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tNFd71l7bL", "reviewer": "Reviewer_Y3EJ", "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": "", "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": "This work presents an algorithm for inference with LLMs using tree search over potential reasoning chains under a fixed and limited compute budget. The authors extend Levin tree search (LTS) to the LLM inference-time search domain by applying it to tree-of-thought, and present a number of theoretical results that bound the compute used by the algorithm as well as its sensitivity to the temperature parameter on LLM sampling. Empirically, the authors evaluate their method on blocksworld, PrOntoQA, and array sorting on 3 sizes of the Llama 3 instruct family. Baselines compared against are DFS and beam search. In general, their method outperforms baselines, especially for lower compute budgets.", "claims_and_evidence_yn": "No", "claims_explanation": "The compute budget is measured by number of thoughts, where each thought is a sequence with a variable number of tokens. Therefore, k thoughts in one tree may not have the same actual compute used as in another method, making this not a good way of measuring compute budgets. Perhaps in the three domains evaluated this is mitigated by the fact that thoughts are likely quite short and structured and similar at each node in the tree, but more generally this will not hold and even so it's unclear now how much of an issue this is. Moreover, assuming cost of generation is the same as cost of evaluation is also not true, as evaluation of a sequence can be done in parallel over the sequence dimension, whereas generation has to be done autoregressively. \n\nOnly the llama models are used for experiments, but these models behave differently from other models like Qwen as shown in this paper https://arxiv.org/abs/2503.01307. At expect the results when proposing a general method for inference to be validated on at least on other model family such as Qwen or Olmo.", "audience_yn": "Yes", "audience_explanation": "Efficient LLM inference-time search for reasoning is of interest to many in the field.", "requested_changes": "Required for acceptance:    \n- Change the compute budget measure to actually measure compute used instead of the something that varies per method\n- Evaluate on another model family\n\nWould strengthen the work:\n- Ablate the aspects of the method that make it work\n- Present results for multiple hyperparameter settings\n- Compare against other SotA inference-time search methods\n- Evaluate on reasoning models, which are the main models used for reasoning on the types of tasks used in this paper.", "broader_impact_concerns": "N.A.", "additional_comments": "Nit: consider explicitly mentioning the domains you evaluate on in the abstract and intro", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)