Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search

Xinzhe Li · 2025

Read Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search by Xinzhe Li (2025) 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-2509-25835.txt.

Introduction

Xinzhe Li trims the cost of tree search in language model reasoning, in work from 2025. Searching many branches at test time lifts scores on long tasks, but it burns vast compute. The plug-in frame, Chain-in-Tree, asks at each step whether a branch is truly needed before growing one.

Two light checks make that call: one asks the model point-blank, and one votes across its own tries. Plugged into three known search frames, the direct check cut tokens, calls, and time by three quarters or more on math sets, with near no score loss. The voting check saved as much but wobbled in a few settings. Code is public.

Catalog record

CREATORXinzhe Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-25835

Browse the full library · About the Tower of Babel

Full text

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

Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search Xinzhe Li Abstract Test-time scaling enables large language models (LLMs) to improve performance on long-horizon reasoning tasks by allocating additional compute at inference. Tree-search–based approaches achieve state-of-the-art results in this setting, but they are notoriously inefficient—often at least an order of magnitude slower than simpler iterative methods. We introduce Chain-in-Tree (CiT) , a plug-in framework that adaptively decides when to branch during search rather than branching at every step. CiT relies on lightweight Branching Necessity (BN) evaluation methods: BN-DP (Direct Prompting), where an auxiliary LLM directly judges whether a step requires branching, and BN-SC (Self-Consistency), which clusters multiple candidate actions to estimate agreement. We integrate CiT into three representative LLM-in-the-loop tree search (LITS) frameworks—Tree of Thoughts (ToT-BS), ReST-MCTS, and RAP—and evaluate across GSM8K and Math500. Our results show that: 1) BN-DP consistently reduces token generation, model invocations, and runtime by 75–85% across all settings, with negligible accuracy loss and in some cases accuracy gains; 2) BN-SC typically yields substantial savings (up to 80%) generally but shows instability in 1–4 out of 14 settings, caused by a small subset of examples that produce extremely long reasoning steps; 3) the quality of auxiliary LLMs is critical—not only the BN evaluator in BN-DP, but also the auxiliary models used in BN-SC for clustering (aggregator) and for pairwise equivalence checks. When these roles are filled by smaller LLMs (e.g., LLaMA-3-8B), performance degrades substantially. Importantly, BN-SC does not require LLMs at all in domains with deterministic action spaces (e.g., board games), where clustering can be performed with programmatic rules. Finally, we provide a theoretical guarantee that BN-DP never increases invocations relative to the baseline and release a unified implementation of CiT across ToT-BS, ReST-MCTS*, and RAP with modular LLM-profiled roles to facilitate reproducibility and extension. This version contains modified/additional content not included in the ICLR submission, which is marked in red. 1 Introduction Large language models (LLMs) excel at tasks such as mathematical and commonsense reasoning, but their performance often improves further when additional test-time compute is allocated. Recent work has shown that test-time scaling enables LLMs to explore multiple reasoning paths, thereby making better use of knowledge they already possess ( Sprague et al. 2025 ) . Among test-time scaling methods, tree-search–based approaches have achieved state-of-the-art results on benchmarks like GSM8K and Math500, by treating reasoning as sequential decision-making and exploring multiple candidate trajectories ( Zhang et al. 2024a ; Yao et al. 2023a ) . Such approaches naturally align with planning-style problems ( Valmeekam et al. 2023 ) . However, tree-search–based frameworks are highly inefficient: compared to simpler iterative prompting methods, they are often 10–20 times slower ( Chen et al. 2024 ) . A central limitation is that they operate at a fixed granularity of reasoning steps. In some cases, this granularity is enforced explicitly, for example by treating each sub-question–answer pair as a node ( Hao et al. 2023 ) . Other approaches, such as MCTS with free-form thoughts ( Zhang et al. 2024a ; Yao et al. 2023a ) , allow more flexibility but still assume that every generated thought must branch independently. In practice, however, a reasoning step in mathematics may correspond to a single operation or a tightly coupled set of operations, while in domains with deterministic action spaces (e.g., board games) the step granularity is even more strictly defined. This rigidity forces branching even on trivial steps, resulting in excessive LLM calls during both expansion and simulation. We address this limitation by proposing Chain-in-Tree (CiT) , a plug-in for LLM-in-the-loop tree search that adaptively decides when branching is necessary. The key idea is to introduce continuous nodes chained together: steps deemed confident or routine by the model are chained sequentially, while branching is reserved only for uncertain points where exploration is valuable. This reduces unnecessary expansion, lowers inference costs, and preserves the search capacity of existing frameworks. Contributions. Our contributions are as follows: • We formulate the decision of when to branch as a new component in tree search and propose two lightweight Branching Necessity (BN) evaluation methods : Direct Prompting (BN-DP) and Self-Consistency (BN-SC). These methods allow LLMs to autonomously determine whether branching is needed at each step. • We provide a theoretical guarantee that BN-DP never increases runtime relative to the baseline, thereby ensuring efficiency by design. • We conduct a comprehensive empirical study across 14 settings: two mathematical reasoning benchmarks (GSM8K, Math500), two base LLMs (Qwen3-32B, LLaMA3-8B) serving either as search policies or BN evaluators, and three representative LITS frameworks (ToT-BS, ReST-MCTS, RAP). • Our experiments show that BN-DP consistently reduces runtime by 75–85% across all settings with negligible accuracy loss and in some cases improved accuracy , confirming its reliability. In contrast, BN-SC achieves substantial savings in most settings but exhibits instability in a few cases . Finally, we demonstrate that the overall effectiveness of CiT strongly depends on the accuracy of BN evaluation. • We release a unified implementation of ToT-BS, RAP, and ReST-MCTS with modular LLM-profiled roles, enabling consistent comparison across frameworks and simplifying extension of CiT to future LITS variants. 2 Related Work We situate our method within a unified view of LLM inference via tree search (LITS), showing how our plug-and-play module can be applied across different frameworks. In addition, we discuss two related lines of work that share a similar high-level motivation—reducing unnecessary branching—but operate in different settings and with distinct mechanisms. LLM Inference via Tree Search (LITS). A growing line of work has explored performing LLM inference through tree-search (LITS) ( Hao et al. 2023 ; Yao et al. 2023a ) . Following the unified view of Li 2025 , these frameworks can be cast into a Markov Decision Process (MDP), where backbone LLMs are profiled into three main roles: (1) Policy : generative LLMs produce candidate actions a_{t} (e.g., reasoning steps) given a state s_{t} (e.g., the task with prior steps). This usage traces back to the ReAct paradigm ( Yao et al. 2023b ) ; (2) Reward model : either using generative LLMs to score candidate steps ( Yao et al. 2023a ; Hao et al. 2023 ) or employing dedicated non-generative/fine-tuned models ( Dai et al. 2025 ; Luo et al. 2025 ) ; (3) Transition model : explicitly predicting the next state s_{t+1} and its confidence r_{\text{conf}} when a_{t} is executed (e.g., RAP ( Hao et al. 2023 ) ), or more commonly, updating the state by concatenating new thoughts (e.g., ToT ( Yao et al. 2023a ) , ReST-MCTS ( Zhang et al. 2024a ) ), in which case r_{\text{conf}}=1 . Our experiments span both types of reward models and both explicit and concatenation-based transition models, demonstrating that CiT is broadly compatible across frameworks. Reducing Redundant Branching. Our chaining mechanism is conceptually related to prior ideas that aim to reduce search complexity by avoiding unnecessary branching. Our chaining mechanism is conceptually related to macro-operators in automated planning, which collapse sequences of primitive operators into a single higher-level action ( Chrpa & Vallati 2022 ) . Another concurrent work is Li et al. 2025 , who proposed branching-on-demand in beam search decoding based on entropy over token-level probability distributions. While the high-level motivation is

Read the complete text