Novelty-based Tree-of-Thought Search for LLM Reasoning and Planning
Leon Hamm, Zlatan Ajanovic · 2026
Read Novelty-based Tree-of-Thought Search for LLM Reasoning and Planning by Leon Hamm, Zlatan Ajanovic (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-2605-06040.txt.
Introduction
Leon Hamm and Zlatan Ajanovic adapt an idea from automated planning, novelty, to guide language model reasoning. Tree of thought search builds paths of linked ideas by prompting a model again and again. The method is brittle and costly, since weak branches consume time and tokens before they are dropped.
The authors define a measurable novelty score for each new thought, judged against nodes already in the search tree. A language model estimates that score using knowledge from its pretraining. Branches with low novelty get pruned early, which shrinks the tree and can lower total token cost despite extra prompts per state. Tests on planning and reasoning benchmarks compare the approach with standard search variants.
Catalog record
| CREATOR | Leon Hamm, Zlatan Ajanovic |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06040
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Novelty-based Tree-of-Thought Search for LLM Reasoning and Planning Leon Hamm, Zlatan Ajanovic Abstract Although advances such as chain-of-thought, tree-of-thought or reinforcement learning have improved the performance of LLMs in reasoning and planning tasks, they are still brittle and have not achieved human-level performance in many domains, and often suffer from high time and token costs. Inspired by the success of width-based search in planning, we explore how the concept of novelty can be transferred to language domains and how it can improve tree-of-thought reasoning. A tree of thoughts relies on building possible “paths” of consecutive ideas or thoughts. These are generated by repeatedly prompting an LLM. In our paper, a measurable concept of novelty is proposed that describes the uniqueness of a new node (thought) in comparison to nodes previously seen in the search tree. Novelty is estimated by prompting an LLM and making use of embedded general knowledge from pre-training. This metric can then be used to prune branches and reduce the scope of the search. Although this method introduces more prompts per state, the overall token cost can be reduced by pruning and reducing the overall tree size. This procedure is tested and compared using several benchmarks in language-based planning and general reasoning. Introduction Large language models (LLMs) have attracted considerable attention for their performance across a wide range of language-based tasks, including exams and coding ( 25 ; 37 ) , and even display limited reasoning capabilities ( 21 ; 22 ; 36 ) . However, these models struggle with complex reasoning and long-term planning when used naively ( 32 ; 42 ) . More structured approaches such as Tree of Thoughts (ToT) ( 41 ) partially address this, but suffer from exponential runtime and token costs due to branching search ( 16 ) . Training-based alternatives such as reinforcement learning from human feedback require expensive fine-tuning ( 17 ; 7 ) , and overly long chains of thought can even degrade performance ( 39 ) . Classical planning algorithms, by contrast, have long handled such problems efficiently. Iterative Width (IW) ( 18 ; 19 ) achieves strong performance by pruning states according to a novelty measure, with runtime exponential only in the problem’s width. Since many problem domains have been shown to have low width, this is highly effective in practice. We hypothesize that the same holds for language-based planning tasks, but defining an analogous notion of novelty in the language domain remains an open challenge. Classical planners also typically require problems to be formalized in a rigid structure, limiting their applicability to natural language settings. In this work, we apply novelty-based pruning within a ToT framework for planning and reasoning tasks. We define a planning algorithm comprising four sub-tasks: action generation, successor state mapping, plan verification, and novelty estimation. Each sub-task and the overall algorithm are evaluated using a setup inspired by the PlanBench ( 31 ) benchmark, enabling direct comparison with classical planners. All code, prompts, and results are available in the accompanying GitHub repository 1 1 1 github.com/anonymous/redacted . Background Classical Planning Classical planning is an important framework for reasoning about actions ( 38 ) , originating in the 1970s with the introduction of STRIPS ( 8 ) . The field has been continuously researched since, with a notable milestone being the composition of the Planning Domain Definition Language (PDDL) ( 23 ) in 1998, a community standard whose variants remain in use to this day. The general approach assumes a state-based representation of the world, where states are characterized by a collection of atoms. We adopt the notation and problem schema of 18 . The set of all possible states is denoted S , with an initial state s_{0}\in S serving as the starting point. An agent may choose from a set of actions O that transition the current state s\in S , subject to constraints A(s)\subseteq O that restrict which actions are admissible in a given state. Any action a\in A(s) transforms the current state according to a successor function s^{\prime}=f(a,s) . The goal S_{G}\subseteq S is defined as the set of states satisfying certain target conditions. The planning problem then consists of finding a sequence of admissible actions a_{1},\ldots,a_{m} , called a plan, that maps the initial state to a goal state: the actions induce a series of states s_{0},s_{1},\ldots,s_{m} where a_{i}\in A(s_{i}) , s_{i+1}=f(a_{i},s_{i}) , and s_{m}\in S_{G} . Such a plan may additionally be optimal with respect to criteria such as length. The planning problem can thus be expressed as a tuple \langle S,s_{0},S_{G},A,f\rangle . Most classical planners, such as Fast Forward ( 11 ) and Fast Downward ( 9 ) , employ heuristic search to find such optimal plans. Width-Based Planning Lipovetzky and Geffner introduced a novel framework for characterizing the complexity and hardness of planning problems ( 18 ; 19 ) . Their approach defines a notion of width that bounds the complexity of a problem, built on the concept of state novelty. Each state s is represented as a subset of boolean features \Phi(s)\subseteq F , where F denotes the set of all features defined by the problem. Planning is then modeled as a tree search over the graph induced by the initial state s_{0} and its possible successors. The novelty w(s) of a state is defined as the size of the smallest subset of features that are true in s but not collectively true in any previously visited state S^{-}_{s} : \displaystyle w(s)=\min_{\begin{subarray}{c}\phi\subseteq\Phi(s),\,\phi\nsubseteq\Phi(s^{\prime}),s^{\prime}\in S^{-}_{s}\end{subarray}}|\phi|\text{.} (1) Width-based planners exploit this notion by pruning any state whose novelty exceeds a specified threshold k . The width w(P) of a planning problem is then defined as the minimum novelty required to solve it via breadth-first search under this pruning scheme. A width-based planner such as IW can find an optimal plan for a problem of width k in O(|F|^{k}) . Notably, most problems with a single goal fluent have width at most two, yielding quadratic or even linear runtimes. Combined with problem serialization, this provides an efficient planner capable of quickly and optimally solving problems across a wide range of domains. Large Language Models Natural language processing has been an active research area since the 1950s and 60s ( 5 ) , but has advanced substantially with the adoption of deep learning and neural networks over classical statistical modeling. The introduction of pre-trained models based on the scalable transformer architecture ( 33 ) has greatly accelerated progress, with sufficiently large models exhibiting emergent abilities not seen in smaller counterparts ( 35 ) . These models, now the subject of extensive research ( 43 ) , are known as large language models (LLMs). Beyond excelling at tasks such as conversation and exams, LLMs can learn in-context, adapting to new problems using information provided at test time rather than relying solely on training data. Research has further shown that how a model is prompted can severely impact performance ( 4 ; 36 ) , giving rise to the field of prompt engineering. We adopt a notation close to that of Yao et al. (2023). A pre-trained language model p with frozen parameters receives a sequence of prompt tokens x=x[1],\ldots,x[n] and autoregressively predicts subsequent tokens by sampling from a conditional