Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries

Sumedh Pendurkar [email protected], Guni Sharon [email protected] · 2026

Read Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries by Sumedh Pendurkar [email protected], Guni Sharon [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03606.txt.

Introduction

Sumedh Pendurkar and Guni Sharon work on making language models solve problems by searching a Tree-of-Thoughts, a branching set of partial ideas. Search with look-ahead improves answers, but each extra model call costs money and time, which matters under tight budgets. Their insight is that the probabilities a model assigns to its own thoughts can guide the search toward promising branches.

They adapt Levin Tree Search, a heuristic method from classical search, to this setting and extend its theory. For the pruned trees used here, they prove a bound on the model queries needed. The result is a principled way to spend a limited query budget where it helps most. Anyone deploying reasoning models at scale faces exactly this trade between answer quality and inference cost.

Catalog record

CREATORSumedh Pendurkar [email protected], Guni Sharon [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03606

Browse the full library · About the Tower of Babel

Full text

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

Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries Sumedh Pendurkar [email protected], Guni Sharon [email protected] 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. 1 Introduction Language Models (LMs) have demonstrated promising performance across a wide range of natural language processing tasks ( 4 ; 5 ; 1 ) . Although LMs are effective on a 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 ( 33 ) , improve performance on such tasks by eliciting intermediate reasoning steps before producing a final response. Building on this idea, methods such as Tree-of-Thoughts (ToT) ( 34 ) (see Figure 1 ) and Reasoning-and-Planning (RAP) ( 11 ) 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 to as “search”) algorithms to navigate the generated search trees and produce a final response. For instance, ToT ( 34 ) method proposed using depth first search (DFS) ( 6 ) or beam search (BS) ( 28 ) while RAP ( 11 ) used Monte-Carlo Tree Search (MCTS) ( 14 ) as 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. Figure 1 : Illustration of the Tree-of-Thoughts (ToT) framework applied to a Rubik’s Cube domain. Cube states with red or green backgrounds represent terminal states as determined by the LM, while gray indicates intermediate states. The green background denotes a goal state. States marked with a cross represent invalid states (not known during search) resulting from thoughts that are infeasible for the domain. While these approaches can be effective, the improvements come at the cost of increased inference-time computation. Generating and evaluating multiple reasoning paths requires repeated LM queries, which can be expensive, especially as the size of LMs increases, as highlighted in recent work ( 27 ; 20 ) . To address this issue, 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 approximately constant. To this end, we explore adaptations of search algorithms within the ToT framework to elicit better LM responses when the number of allowable thought generations is limited. We begin with an observation: explicitly evaluating intermediate thoughts using LMs, commonly performed to rank and pick thoughts to expand, requires additional LM queries. Given this understanding, we propose using the LM as a policy, mapping from a partial sequence of thoughts (state) to a distribution over next thoughts (neighboring states), thereby guiding the search without requiring additional evaluation queries. Building on this observation, we adapt Levin Tree Search (LTS) ( 21 ) to the ToT framework, which directly leverages LM as a policy to effectively guide the search. Further, we extend the theoretical guarantee on the number of state expansions, and consequently on the number of thoughts generated, from the original LTS formulation on generic search trees ( 21 ) to the ToT framework. Note that the original LTS theoretical expansion bound does not directly apply to the ToT framework due to its pruned structure. Moreover, we analyze the sensitivity of the bound on the number of thoughts generated, to the temperature parameter, commonly used in the final softmax layer of LMs. Experimental results on three representative domains (Blocksworld, PrOntoQA, 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 ( 34 ) , 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 1 1 See https://github.com/sumedhpendurkar/Search-LLM-inference for our code. 2 Preliminaries 2.1 Problem Formulation Let \mathcal{X} denote a discrete space of all possible tokens , where a token refers to a basic unit of text such as a word, subword, or punctuation mark. The definition of a token is specific to the tokenizer of a given language model (see for example ( 10 ) ). A single token is denoted with a non-bold letter, e.g. x\in\mathcal{X} , while a sequence of tokens is denoted with a bold letter, e.g., \textbf{x}=(x_{1},x_{2},\dots,x_{n}) . A language model (LM) , p , defines a probability distribution over a token given a sequence of previous tokens. Formally, p:\mathcal{X}^{n}\mapsto\Delta(\mathcal{X}) , where \Delta(\mathcal{X}) is the probability simplex over \mathcal{X} and n is the maximum context length. 2 2 2 If the input to a given LM is smaller than n the input is padded. Given a language model p and an input sequence \textbf{x}=(x_{1},x_{2},\dots,x_{n}) , an autoregressive decoding method , ALG , generates a response \textbf{y}=ALG(p,\textbf{x}) . For example, this can be done in a greedy way by selecting p(y_{i}|\textbf{x})=\argmax p(y_{i}|y_{1},y_{2}\dots y_{i-1},\textbf{x}) . In this paper, we assume an access to an evaluator that determines whether a response is valid or not (see Section 4 for details). In our experiments, we consider a fixed sized test set D=\{\textbf{x}_{1},\textbf{x}_{2},\dots,\textbf{x}_{n}\} . The decoding methods solve problem-solving tasks, represented by an input sequence \textbf{x}_{i} , by generating responses \textbf{y}_{i} such that \textbf{y}_{i} can be considered “valid” by the domain-specific evaluator. We consider the Tree-of-Thoughts (ToT) ( 34 ) framework for decoding by generating a tree over thoughts . Following ( 34 ) , a sequence of tokens (t_{1},t_{2},\dots,t_{n}) is said to be a

Read the complete text