Tree of Thoughts: Deliberate Problem Solving with Large Language Models

ArXiv: 2305.10601

🎯 Pitch

Standard chain-of-thought reasoning forces language models into rigid left-to-right generation, but this paper shows that allowing models to build, evaluate, and backtrack across branching thought trees—using classic AI search algorithms—catapults GPT-4’s success on a hard math game from 4% to a stunning 74%.

1. Executive Summary

This paper introduces the Tree of Thoughts (ToT) framework, a new paradigm for language model inference that enables deliberate problem solving by exploring multiple reasoning paths over coherent units of text called “thoughts” — intermediate steps such as candidate equations in a math puzzle, short writing plans for creative text generation, or individual word guesses in a crossword — rather than committing to a single left-to-right token sequence. Experiments with GPT-4 on three novel tasks — Game of 24, Creative Writing, and Mini Crosswords — demonstrate that ToT with explicit search algorithms (breadth-first search with pruning and depth-first search with backtracking) dramatically outperforms standard prompting: on Game of 24, ToT achieves a 74% success rate compared to 4% for chain-of-thought prompting, while on Crosswords it improves word-level success from under 16% to 60%. The framework’s modular decomposition into thought generation, state evaluation via LM self-assessment, and pluggable search algorithms generalizes existing methods — IO, CoT, CoT-SC, and self-refinement all emerge as special cases — establishing that deliberate tree search over semantic units is a powerful augmentation to the associative “System 1” default of LMs only when tasks require non-trivial planning, lookahead, or backtracking rather than straightforward left-to-right reasoning.

2. Context and Motivation

The Core Problem: Language Models Cannot Deliberate

The fundamental gap this paper identifies is that language models, despite their increasingly impressive reasoning capabilities, are still constrained by a token-level, left-to-right generation process during inference. When GPT-4 solves a math problem or writes a creative passage, it produces text one token at a time, with each token conditioned on all previous tokens in a strictly sequential, forward-moving chain. There is no mechanism for the model to say "wait, this approach isn't working — let me back up and try a different strategy," or "let me explore two possible next steps, evaluate which is more promising, and only then commit." The model's inference procedure is, as the authors characterize it, purely associative — it always picks the most likely next token based on what has come before, without any capacity for the kind of strategic exploration, lookahead, or backtracking that characterizes deliberate human reasoning.

The paper articulates this as a dual-process gap (Section 1). Drawing on the psychology literature's distinction between System 1 (fast, automatic, unconscious) and System 2 (slow, deliberate, conscious) modes of thought, the authors argue that current LM inference operates entirely in a System 1 mode. The model generates tokens through a well-trained but fundamentally reactive process — it does not maintain and compare alternative hypotheses, does not step back to evaluate whether its current trajectory is promising, and cannot backtrack when it realizes it has made a poor early decision that cascades into failure. In reinforcement learning terms, this is the distinction between model-free (associative, habitual) and model-based (deliberative, planning-oriented) decision-making — and LMs, as deployed during inference, are purely model-free.

This gap manifests concretely in tasks where early decisions are pivotal. Consider the Game of 24: given four numbers like 4, 9, 10, 13, the model must find an arithmetic expression equaling 24. A chain-of-thought approach generates a sequence of intermediate equations, but if the model's first step is poorly chosen (e.g., "4 + 9 = 13"), it is essentially doomed — it will continue generating from that bad premise, unable to reconsider. The paper's error analysis (Figure 3b) confirms this: approximately 60% of CoT samples on Game of 24 fail after generating just the first step, or equivalently, just "the first three words." The left-to-right decoding process makes one local, greedy choice at the outset, and that choice determines the entire downstream trajectory with no mechanism for recovery.

Why This Matters: Beyond Single-Path Reasoning

This limitation is not merely an academic curiosity — it has direct practical and theoretical significance because it defines a class of problems that resist current prompting methods even with state-of-the-art models. The paper explicitly constructs three tasks (Section 4) that are deliberately designed to challenge standard approaches:

• Game of 24 requires mathematical reasoning where the search space of possible arithmetic combinations is combinatorial, and no single chain-of-thought is likely to stumble upon the correct sequence without exploration. Even best-of-100 CoT sampling achieves only 49% success — meaning that in over half of cases, 100 independent attempts all fail.

• Creative Writing requires high-level planning: given four ending sentences, the model must construct a coherent four-paragraph passage where each paragraph ends with the specified sentence. This demands global coherence — decisions about the first paragraph's theme and content constrain what can be written in subsequent paragraphs. A purely left-to-right approach lacks the ability to plan the overall structure before committing to prose.

• Mini Crosswords is an even harder search problem involving natural language constraints. Filling in a 5×5 grid requires satisfying intersecting horizontal and vertical word clues simultaneously. Early word choices tightly constrain later options, and a wrong early guess may only reveal itself as impossible several steps later — precisely the scenario where backtracking is essential.

The broader significance is that as LMs are deployed for increasingly complex, real-world decision-making tasks — coding, data analysis, robotics, scientific reasoning — the fraction of problems requiring exploration, planning, and backtracking will grow. The paper's framing anticipates this: "the simple associative token-level choices of LMs... might benefit from augmentation by a more deliberate 'System 2' planning process." If this gap cannot be closed, LMs will hit a capability ceiling on precisely the kind of non-trivial reasoning tasks that represent the next frontier for AI systems.

Furthermore, the paper's approach connects LMs to a rich intellectual tradition in AI and cognitive science — the conception of problem-solving as search through a combinatorial problem space, formalized by Newell, Shaw, and Simon starting in the 1950s. These classical AI insights about heuristic-guided search, tree-structured problem spaces, and the role of evaluation functions in directing exploration have been largely absent from the modern LM paradigm, which has focused almost exclusively on scaling model size and training data rather than on inference-time reasoning architectures. The paper argues that these classical ideas are not obsolete — they address a dimension of intelligence (deliberate search) that scaling alone does not provide, and their integration with modern LMs could unlock capabilities that neither approach achieves independently.

Where Prior Approaches Fall Short

The paper identifies specific limitations in each of the main existing paradigms for LM-based problem solving (Section 2, elaborated throughout Section 4):

Input-Output (IO) prompting is the simplest approach: wrap the input with task instructions and few-shot examples, then sample the output directly. This collapses all reasoning into a single forward pass. On tasks requiring multi-step inference, IO fails catastrophically — 7.3% on Game of 24, 38.7% letter accuracy on Crosswords. The model has no opportunity to externalize intermediate reasoning, and the mapping from input to output is too complex to learn from a handful of examples.

Chain-of-Thought (CoT) prompting addresses IO's limitation by introducing intermediate reasoning steps (thoughts) between input and output. However, CoT has two critical structural weaknesses:

1. No local exploration within a thought process: CoT samples a single chain of thoughts sequentially — each thought is generated conditioned on the previous ones, and there is no branching to explore alternative continuations at any step. The model commits to each thought as it is generated, with no mechanism to say "actually, let me consider three different ways to approach this step and pick the best one." This is the "branches of the tree" problem the paper identifies.

2. No global planning, lookahead, or backtracking: CoT provides no mechanism for the model to step back and evaluate whether the overall trajectory is promising, to look ahead at the consequences of current choices, or to backtrack when a dead end is reached. If the chain takes a wrong turn at step 2, steps 3 through 10 are wasted computation pursuing an unfixable error. The model never asks "is this actually working?" in a global sense.

These weaknesses are not merely hypothetical — they produce stark empirical failures. On Game of 24, CoT achieves only 4.0% success (actually worse than IO's 7.3%, likely because the intermediate equations create more opportunities for arithmetic errors). On Crosswords, CoT achieves only 15.6% word-level success. The fundamental issue is that CoT samples from a distribution over complete reasoning paths, but this distribution may assign negligible probability to the correct path for problems requiring non-obvious intermediate choices.

Self-Consistency with CoT (CoT-SC) attempts to mitigate CoT's fragility by sampling multiple independent chains and taking a majority vote over final answers. This improves robustness because different chains may explore different reasoning strategies, and the correct answer may emerge from the consensus. However, CoT-SC inherits CoT's fundamental limitation: within each individual chain, there is still no local exploration of alternative thought steps. Each chain is independently sampled from the same left-to-right process, so if the base CoT distribution rarely produces correct chains, aggregating many of them doesn't help — the "most frequent" heuristic only works when the output space is limited and the correct answer already has non-trivial probability mass. On Game of 24, CoT-SC at k=100 achieves only 9.0% — better than single CoT, but still abysmal. On Crosswords, the output space (25 letters) is too large and interdependent for majority voting over complete boards to be meaningful.

Iterative refinement (self-refine) approaches condition the model on its own previous (incorrect) output and prompt it to generate an improved version. The paper tests this on Game of 24 (up to 10 refinement iterations with ground-truth correctness feedback) and Creative Writing (up to 5 iterations with self-assessed coherence). On Game of 24, IO+refine achieves 27% — a meaningful improvement over base IO (7.3%) but far below what search achieves (74%). The limitation is that refinement is a form of local hill-climbing: the model starts from one initial guess and tries to improve it incrementally, but if the initial guess is in the wrong region of the solution space, no amount of local refinement will find the correct answer. Refinement lacks the breadth to explore fundamentally different approaches — it deepens one path rather than branching to try alternatives.

Critically, all of these prior approaches can be seen as special cases of tree search with severely restricted structure. The paper makes this explicit (Section 3, Figure 1): IO is a tree of depth 0 (no intermediate thoughts), CoT is a tree of depth >0 but breadth 1 (a single chain with no branching), CoT-SC is a tree with breadth k but no interaction between branches (k independent chains evaluated only at the leaves), and self-refinement is a tree where each node has exactly one child (a linear sequence of revisions). None of them implement the full tree-structured exploration — with branching, pruning, lookahead, and backtracking — that characterizes classical problem-solving search.

How This Paper Positions Itself

The paper positions the Tree of Thoughts framework as a generalization that subsumes prior methods while enabling qualitatively new capabilities. The key conceptual move is to reframe LM-based problem solving not as generating a single answer (IO) or generating a single reasoning chain (CoT), but as search over a tree of thoughts — where each node represents a partial solution, branches represent alternative next steps, and the search process is guided by heuristics that evaluate states and decide where to explore.

This reframing is not merely cosmetic. It introduces four design dimensions that prior methods collapse or ignore (Section 3):

1. Thought decomposition: How should the intermediate reasoning process be broken into units? The answer depends on the problem: a thought could be an arithmetic equation (Game of 24), a writing plan paragraph (Creative Writing), or a single word guess (Crosswords). Prior methods either don't decompose at all (IO) or decompose implicitly without problem-specific design (CoT).

2. Thought generation: How should candidate next thoughts be produced? The paper identifies two strategies: i.i.d. sampling from a CoT prompt (when the thought space is rich and diversity matters, as in Creative Writing) and sequential "proposal" generation (when the thought space is constrained and duplication should be avoided, as in Game of 24 and Crosswords). Prior methods only use i.i.d. sampling.

3. State evaluation: How should partial solutions be assessed for promise? The paper proposes using the LM itself as a heuristic evaluator — either by prompting it to assign scalar values to individual states or by prompting it to vote among competing states. This is a novel contribution: classical AI systems used either programmed heuristics (hand-crafted by experts) or learned heuristics (trained on large amounts of data), whereas ToT uses the LM's pre-existing reasoning capabilities to perform evaluation through natural language deliberation. The LM can use commonsense ("1, 2, 3 are too small to reach 24"), lookahead simulation ("quickly confirm that 5, 5, 14 can reach 24 via 5+5+14"), and constraint reasoning ("no word can start with 'tzxc'") — all expressed in natural language rather than encoded in rules or learned parameters.

4. Search algorithm: How should the tree be explored? The paper demonstrates breadth-first search (BFS) with pruning for shallower tasks (Game of 24, Creative Writing) and depth-first search (DFS) with backtracking for deeper tasks (Crosswords), emphasizing that the framework is modular — different search algorithms can be plugged in depending on the problem structure and resource constraints.

The paper explicitly positions ToT as being simpler and more modular than concurrent work on MCTS-based language model reasoning (RAP), while handling more challenging tasks (creative writing, which RAP's code-based thought representation cannot easily accommodate). It also distinguishes itself from program-guided generation approaches (PAL, LLM+P) that represent thoughts as code or delegate planning to external symbolic solvers — ToT keeps all reasoning in natural language, making it more flexible and general-purpose, at the cost of not leveraging the precision of formal execution.

Perhaps most importantly, the paper positions ToT as a framework that is compatible with existing LMs without any fine-tuning. This is a deliberate choice that makes the approach immediately applicable — no training pipeline, no curated dataset, no model modification. The same GPT-4 model that achieves 4% on Game of 24 with CoT prompting achieves 74% when embedded in the ToT framework, purely through changes to the inference procedure. This demonstrates that the model already possesses the relevant capabilities (generating candidate equations, evaluating partial solutions, detecting dead ends) — they are simply not engaged by standard left-to-right decoding. The ToT framework provides the scaffolding that elicits these latent capabilities and organizes them into a deliberate search process, much as CoT elicits latent reasoning capabilities that IO does not.

This framing — ToT as a way to organize and direct existing model capabilities rather than create new ones — is both a strength (practical, immediately deployable) and a limitation (it cannot give the model capabilities it fundamentally lacks, as the paper acknowledges when discussing Crosswords games that ToT cannot solve). It sets up a natural research trajectory: if current LMs can benefit from deliberate search structure at inference time, future LMs that are explicitly trained for tree-structured reasoning — perhaps through fine-tuning on search trajectories or reinforcement learning over thought-space navigation — might benefit even more. The paper's final paragraph hints at this direction: "fine-tuning LMs using a ToT-style high-level counterfactual decision making... might present opportunities to enhance the problem-solving capabilities of LMs."

3. Technical Approach

3.1 Reader Orientation

The Tree of Thoughts (ToT) is an inference-time framework that wraps a frozen language model in an explicit tree-search algorithm, allowing the model to explore multiple reasoning paths, evaluate the promise of partial solutions, and backtrack from dead ends — all through structured natural-language prompting rather than any model retraining. It solves the problem of premature commitment: standard left-to-right decoding forces the LM to pick one next token (and thus one reasoning trajectory) at each step with no ability to compare alternatives or recover from early mistakes, which causes catastrophic failure on tasks where the correct path is unlikely to be found by a single greedy or sampled chain. The shape of the solution is a modular, four-component architecture — thought decomposition, thought generation, state evaluation, and search algorithm — that can be configured per-task and treats the LM as both a proposal engine (generating candidate next steps) and a heuristic evaluator (judging which partial solutions are worth pursuing).

3.2 Big-Picture Architecture (Diagram in Words)

The ToT system has four major components that are configured per task:

1. Thought Decomposer — defines what a "thought" is (e.g., one arithmetic equation, one paragraph plan, one word guess) and how many thought steps are needed. This is a design choice made by the human, not learned.

2. Thought Generator $G(p_\theta, s, k)$ — given the current state $s$ (the input plus all thoughts generated so far), produces $k$ candidate next thoughts. Implemented by prompting the frozen LM, either sampling i.i.d. from a CoT-style prompt or using a "propose prompt" that generates multiple candidates in one call.

3. State Evaluator $V(p_\theta, S)$ — given a set of states $S$ (each representing a partial solution with different thought histories), produces scores or rankings that serve as a heuristic for the search algorithm. Implemented by prompting the LM to reason about each state's prospects, either independently (assigning scalar values like sure/likely/impossible) or comparatively (voting among alternatives).

4. Search Algorithm — controls which states to explore and in what order, using the evaluator's scores to prune unpromising branches. The paper demonstrates BFS with beam-width pruning for shallow tasks (Game of 24, Creative Writing) and DFS with backtracking for deeper tasks (Mini Crosswords), but the framework is modular — different algorithms can be swapped in.

Information flow for a single task: The input enters → the thought decomposer determines the granularity and maximum number of steps → at each step, the thought generator produces $k$ candidates from the current state → the state evaluator scores the resulting new states → the search algorithm selects which states to keep exploring and which to prune → the process repeats until a complete solution is reached or the budget is exhausted → the final output is read from the deepest (or highest-scoring) state.

Crucially, the LM is called in multiple roles — as generator, as evaluator, and sometimes as voter — but it is the same frozen model throughout. The intelligence comes from how the framework orchestrates these calls, not from training or fine-tuning.

3.3 Roadmap for the Deep Dive

• First, the formal problem statement — how ToT frames any task as tree search, what a "state" is, and the four questions every ToT instantiation must answer. This establishes the unifying abstraction before we dive into specifics.

• Second, thought decomposition — how to choose the right granularity for intermediate steps, with examples from the three tasks showing how the same principle (small enough to evaluate, big enough to be coherent) leads to different concrete choices.

• Third, thought generation — the two strategies (i.i.d. sampling vs. sequential proposal) and when each applies, including the exact prompt structures and how diversity or constraint-satisfaction guides the choice.

• Fourth, state evaluation — the paper's most novel component: using the LM as a heuristic function through deliberate natural-language reasoning. We'll cover independent value assignment, comparative voting, and how multiple samples are aggregated for robustness.

• Fifth, search algorithms — BFS with pruning (Algorithms 1) and DFS with backtracking (Algorithm 2), including the specific parameters chosen per task and why.

• Sixth, how the existing baselines (IO, CoT, CoT-SC, refinement) emerge as special cases — this connects the framework back to prior work and clarifies what ToT adds structurally.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a framework paper whose core idea is that language model problem-solving can be recast as tree search over semantic units (thoughts), with the LM itself serving as both the proposal distribution and the heuristic evaluation function through structured prompting. The contribution is not a single trained model but a modular inference architecture and a demonstration that it dramatically improves performance on tasks requiring exploration, planning, or backtracking.

Formal Problem Statement: Problem-Solving as Tree Search

The paper frames any problem as a search over a tree where each node is a state $s = [x, z_{1 \cdots i}]$ — the original input $x$ concatenated with the sequence of $i$ thoughts generated so far. The root is $s_0 = [x]$ (the input with no thoughts yet). The edges are candidate next thoughts $z_{i+1}$ that extend the partial solution. A leaf is a state where the thought sequence constitutes a complete solution (e.g., three equations that use all four numbers and produce 24, or ten filled words that satisfy all crossword constraints). The goal is to find a path from root to a leaf that satisfies the problem's success criterion.

A specific instantiation of ToT requires answering four design questions (Section 3, enumerated list):

1. How to decompose the intermediate process into thought steps — what is the granularity and structure of a single thought for this problem?

2. How to generate potential thoughts from each state — given a partial solution, how do we produce $k$ candidates for the next thought?

3. How to heuristically evaluate states — given a set of partial solutions, how do we score or rank them to guide search?

4. What search algorithm to use — how do we navigate the tree, deciding which nodes to expand and in what order?

These four questions are answered differently for each of the three tasks (Game of 24, Creative Writing, Mini Crosswords), demonstrating the framework's modularity and adaptability. The rest of this section walks through each component in detail.

Thought Decomposition: Choosing the Right Semantic Unit

The paper argues that thought granularity is a Goldilocks problem: a thought must be "small enough" that the LM can generate diverse, promising candidates (generating "a whole book" is too big to be coherent), yet "big enough" that the LM can meaningfully evaluate its progress toward solving the problem (generating "one token" is too small to assess). The right granularity depends on the problem structure and the LM's capabilities.

For Game of 24, a thought is one intermediate arithmetic equation operating on two of the remaining numbers. For example, given input "4 9 10 13," the three thoughts in a complete solution path might be:

"13 - 9 = 4 (left: 4 4 10)" "10 - 4 = 6 (left: 4 6)" "4 * 6 = 24 (left: 24)"

Each thought reduces the set of available numbers by one (consuming two numbers to produce one result), and exactly three thoughts are needed to go from four input numbers to a single number (the target, 24). The tree depth is therefore fixed at $T = 3$. This decomposition is natural because it mirrors how a human solves the game — combining pairs of numbers step-by-step — and creates states that the LM can evaluate by checking whether the remaining numbers can plausibly reach 24.

For Creative Writing, a thought is a short writing plan — a paragraph-length description of the overall structure and content for the passage. With the example from Figure 4, given four ending sentences (about a book connecting people, a self-help book, a woman avoiding attention by using sign language, and different perceptions of others), a thought might be:

"Introduce a book that connects two strangers on a flight, setting the stage for a self-help book's theme of human connection. Then transition to a woman who uses sign language to avoid unwanted attention, highlighting the different ways people communicate."

The tree depth is $T = 2$ (one planning step, one writing step). This is "bigger" than the Game of 24 thoughts because creative writing requires global coherence — the plan must orchestrate how four independently-specified ending sentences fit into a single coherent narrative — and a word-by-word or sentence-by-sentence decomposition would not allow the LM to evaluate whether the overall structure works before committing to prose.

For Mini Crosswords, a thought is a single word guess for one clue (e.g., "h2. motor" or "v5. naled"). Each thought fills in one of the 10 words (5 horizontal, 5 vertical) in the 5×5 grid. The tree depth is variable, up to $T = 10$ (all words filled). This decomposition is natural because each word is an atomic decision that constrains intersecting words through shared letters — a wrong guess for one word may make an intersecting word impossible to fill, which can only be detected by evaluating the resulting letter constraints. The thought granularity is "small" enough that individual guesses can be easily generated from clues plus current letter constraints, yet "big" enough that evaluating a state means checking whether all remaining clues are still fillable given the letters committed so far.

Design principle across all three tasks: the thought unit corresponds to the natural decision granularity of the problem — the level at which a human solver would say "I need to try a different approach here." This is not a learned or optimized property; it is a design choice the human experimenter makes when configuring ToT for a new task, based on understanding the problem structure.

Thought Generation: Two Strategies for Producing Candidates

Given a state $s = [x, z_{1 \cdots i}]$, the thought generator $G(p_\theta, s, k)$ produces $k$ candidates for the next thought $z_{i+1}$. The paper identifies two generation strategies, chosen based on whether the thought space is rich (many valid continuations, where diversity matters) or constrained (a limited set of valid next steps, where avoiding duplicates matters).

Strategy (a): I.I.D. Sampling from a CoT Prompt

This strategy samples each candidate independently:

$z^{(j)} \sim p_\theta^{\text{CoT}}(z_{i+1} \mid s) = p_\theta^{\text{CoT}}(z_{i+1} \mid x, z_{1 \cdots i}) \quad \text{for } j = 1 \cdots k$

where $p_\theta^{\text{CoT}}$ is the LM conditioned on a CoT-style prompt that includes the input, the thought history, and an instruction to generate the next thought, and $k$ is the branching factor (number of candidates to generate). Each candidate is sampled independently at the model's sampling temperature (0.7 in all experiments), so they naturally diverge.

When it applies: the paper uses this strategy for Creative Writing, where the thought space (possible writing plans) is rich and open-ended. Each plan can be a substantively different approach to the same input constraints, and i.i.d. sampling naturally produces diversity because the LM's distribution over plans has high entropy. There is no concern about generating duplicate plans, because the space is large enough that independent samples are almost certainly different.

Strategy (b): Sequential Proposal Generation

Instead of sampling independently, this strategy prompts the LM to generate all $k$ candidates in a single call:

$[z^{(1)}, \cdots, z^{(k)}] \sim p_\theta^{\text{propose}}(z_{i+1}^{(1 \cdots k)} \mid s)$

where $p_\theta^{\text{propose}}$ is the LM conditioned on a "propose prompt" that explicitly asks for multiple distinct next steps in one response. The LM sees its own previous proposals within the same context, which helps it avoid generating duplicates.

When it applies: the paper uses this strategy for Game of 24 and Mini Crosswords, where the thought space is more constrained. In Game of 24, given remaining numbers like {4, 4, 10}, there are only a few meaningful arithmetic operations to propose (e.g., 4+4=8, 4×4=16, 10−4=6, 10÷4=2.5, etc.), and independent sampling would frequently produce the same candidate multiple times, wasting the generation budget. Sequential proposal lets the LM see "I've already proposed 4+4=8" and generate "10−4=6" as a distinct alternative. Similarly, in Crosswords, given letter constraints for a clue, there may be only a handful of words that fit — sequential proposal prevents the LM from suggesting the same word repeatedly.

The exact prompt for Game of 24 thought generation (Figure 2a) is a 1-shot propose prompt that shows one example of generating multiple candidate next steps from remaining numbers, then asks the LM to do the same for the current state. For Crosswords (Figure 6a), the propose prompt includes the current grid state translated into letter constraints for each remaining clue, and asks the LM to propose candidates for the next word to fill along with confidence levels.

Why two strategies rather than one unified approach? The paper's implicit argument is that the generation strategy should match the entropy of the thought distribution. When entropy is high (many good options), independent sampling is fine and simpler. When entropy is low (few good options), independent sampling wastes compute on duplicates, and sequential proposal within a single context is a lightweight way to enforce diversity without needing a separate deduplication mechanism. This is a practical engineering choice, not a theoretical claim — the framework could accommodate other generation strategies (e.g., constrained decoding, retrieval-augmented generation) without changing the surrounding search structure.

State Evaluation: The LM as a Heuristic Function

The state evaluator $V(p_\theta, S)$ is the most conceptually novel component of ToT. In classical AI search, the heuristic function that estimates how promising a state is must be either programmed (hand-crafted rules, as in DeepBlue) or learned (trained on large amounts of game outcomes, as in AlphaGo). The paper proposes a third alternative: use the LM itself to reason about states in natural language, treating its pre-trained reasoning capabilities as a heuristic. The key insight is that LMs already possess the commonsense, mathematical, and constraint-reasoning abilities needed to assess partial solutions — they just need to be prompted to apply these abilities to the specific state at hand.

The paper distinguishes two evaluation strategies, chosen based on whether states can be meaningfully assessed in isolation or are better compared against each other.

Strategy (a): Independent Value Assignment

Each state $s \in S$ is evaluated independently:

$V(p_\theta, S)(s) \sim p_\theta^{\text{value}}(v \mid s)$

where $p_\theta^{\text{value}}$ is the LM conditioned on a "value prompt" that asks it to reason about state $s$ and produce a scalar value $v$ or a classification that can be heuristically mapped to a value. The paper explores two forms of output:

• Scalar scores (e.g., 1–10) for Creative Writing, where coherence is a continuous quality.
• Categorical judgments (sure/likely/impossible) for Game of 24, where the question is whether the remaining numbers can possibly reach 24. These are heuristically mapped to numeric values for the search algorithm.

What the LM reasons about during evaluation. The paper describes two sources of evaluative knowledge that the LM draws upon (Section 3, item 3a):

1. Few lookahead simulations: The LM can mentally simulate a completion of the partial solution to check if it works. For example, given remaining numbers {5, 5, 14} in Game of 24, the LM can confirm reachability by noting "5 + 5 + 14 = 24." For Crosswords, given letter constraints like "h2. motor" already filled, the LM can check whether a candidate word for a crossing clue is compatible with the committed letters.

2. Commonsense pruning: The LM can eliminate states based on general knowledge. For Game of 24, it knows that {1, 2, 3} cannot reach 24 because even the maximum possible result (1×2×3 = 6) is too small. For Crosswords, it knows that no English word starts with "tzxc," so any state producing that letter constraint is impossible.

Crucially, the paper acknowledges that these valuations do not need to be perfect — they only need to be "approximately helpful for decision making." The search algorithm is robust to noisy heuristics because it maintains multiple candidates (via BFS beam width) or can backtrack (in DFS). An imperfect heuristic that is right 80% of the time is still enormously valuable compared to no heuristic at all (random search).

Aggregating multiple evaluation samples. For both value and vote strategies, the LM can be prompted multiple times and the results aggregated:

"we could prompt the LM multiple times to aggregate the value or vote results to trade time/resource/cost for more faithful/robust heuristics."

For Game of 24, the paper samples 3 value judgments per thought candidate and aggregates them (presumably by majority vote for the sure/maybe/impossible classification). For Creative Writing, 5 scalar scores are sampled and averaged. The paper reports that these 5 scores are "usually consistent, with a standard deviation of around 0.56 on average" — evidence that the LM's evaluative judgments are reasonably calibrated.

Strategy (b): Comparative Voting Across States

Instead of evaluating states independently, this strategy has the LM compare multiple states and vote for the best one:

$V(p_\theta, S)(s) = \mathbb{1}[s = s^*]$

where $s^* \sim p_\theta^{\text{vote}}(s^* \mid S)$ is the state voted as most promising from the set $S$, and the value is 1 for the winning state and 0 for all others (or equivalently, states are ranked by vote count). The "vote prompt" presents the LM with multiple candidate states and asks it to "analyze choices below, then conclude which is most promising for the instruction."

When voting is preferred over independent valuation. The paper argues that voting is more natural "when problem success is harder to directly value" — for Creative Writing, assessing the coherence of a single plan in absolute terms (is this a 7 or an 8?) is harder than comparing two plans and deciding which is better. Voting is described as "similar in spirit to a 'step-wise' self-consistency strategy" — it reframes state selection as a multi-choice QA problem and uses multiple LM samples to vote.

For Creative Writing (Figure 4), the voting procedure at the plan step works as follows: the thought generator produces $k = 5$ candidate plans, the vote prompt presents all 5, the LM is sampled 5 times to produce 5 votes, and the plan receiving the most votes is selected. The same procedure is repeated at the passage-generation step: $k = 5$ candidate passages are generated based on the winning plan, 5 votes are sampled, and the winning passage is the final output.

Why use the LM as a heuristic at all? The paper explicitly contrasts this with the two traditional approaches:

• Programmed heuristics: would require hand-crafting evaluation rules for each new task, which is brittle and labor-intensive. For Creative Writing, what would a programmed coherence heuristic even look like?
• Learned heuristics: would require training a separate model on large amounts of outcome data, which is sample-inefficient and task-specific. The LM already encodes relevant evaluation knowledge from pretraining; prompting elicits it without any additional data.

By using the LM as both generator and evaluator, ToT creates a self-contained reasoning loop where the same model proposes candidates and judges their quality — a form of deliberative reasoning implemented entirely through structured prompting.

Search Algorithms: BFS with Pruning and DFS with Backtracking

The final component of ToT is the search algorithm that uses the thought generator and state evaluator to systematically explore the tree. The paper presents two algorithms and selects between them based on the tree's depth and branching characteristics.

Algorithm 1: Breadth-First Search with Beam Pruning (ToT-BFS)

S_0 ← {x}
for t = 1, ..., T do
    S'_t ← {[s, z] | s ∈ S_{t-1}, z_t ∈ G(p_θ, s, k)}
    V_t ← V(p_θ, S'_t)
    S_t ← arg max_{S ⊂ S'_t, |S| = b} Σ_{s∈S} V_t(s)
end for
return G(p_θ, arg max_{s∈S_T} V_T(s), 1)

This algorithm works as follows:

1. Initialization: Start with $S_0$ containing only the root state (the input with no thoughts).

2. Expansion (step $t$): For each state $s$ in the current frontier $S_{t-1}$, use the thought generator to produce $k$ candidate next thoughts. Collect all resulting new states into $S'_t$. If there are $b$ states at step $t-1$ and $k$ candidates per state, then $S'_t$ contains $b \times k$ states.

3. Evaluation: Score all states in $S'_t$ using the state evaluator.

4. Pruning: Keep only the $b$ highest-scoring states, where $b$ is the breadth limit. This is the beam: it prevents exponential growth of the frontier while retaining multiple promising candidates.

5. Iteration: Repeat steps 2–4 for $T$ steps.

6. Output: At the final step, select the single highest-scoring state and generate one final thought from it (the $G(p_\theta, \cdot, 1)$ call) to produce the complete output.

Where BFS is used. The paper applies BFS to Game of 24 and Creative Writing, both of which have shallow trees:

• Game of 24: $T = 3$ (three intermediate equations), $b = 5$ (keep top 5 states per step), $k$ is determined by the propose prompt (the LM generates as many candidates as it can, up to the prompt's output length limit). The evaluation at each step uses the sure/likely/impossible classification with 3 samples aggregated per candidate.

• Creative Writing: $T = 2$ (plan step, then write step), $b = 1$ (only one state is kept per step — effectively greedy selection after evaluation), $k = 5$ (5 candidate plans, then 5 candidate passages). The evaluation uses 5-sample voting at each step.

Why BFS with beam pruning? BFS is appropriate when the tree is shallow because it explores all candidates at a given depth before moving deeper, ensuring that good early choices are not missed. The beam pruning (keeping only $b$ states) prevents the search from becoming too expensive — without pruning, the tree would grow as $k^T$, which for $k \approx 5$ and $T = 3$ would be 125 states (still manageable) but for larger trees would be intractable. The beam introduces a exploration-exploitation tradeoff: larger $b$ explores more diverse paths but costs more compute (more states to evaluate and expand). The paper sweeps $b = 1$ through $b = 5$ for Game of 24 and finds that $b = 1$ already achieves 45% (vs. 4% for CoT), while $b = 5$ achieves 74%, showing that breadth provides substantial additional gains.

Algorithm 2: Depth-First Search with Backtracking (ToT-DFS)

DFS(s, t):
    if t > T: record output G(p_θ, s, 1); return
    for s' ∈ sorted(G(p_θ, s, k)):     // candidates, most promising first
        if V(p_θ, {s'})(s) > v_th:     // pruning check
            DFS(s', t+1)

This algorithm works as follows:

1. Base case: If the current step $t$ exceeds the maximum depth $T$, the current state is a complete solution — generate a final output from it and record it.

2. Candidate generation and sorting: Generate $k$ candidate next thoughts from the current state. Sort them by some measure of promise (in the Crosswords implementation, this is the LM's self-reported confidence level, aggregated across multiple proposals).

3. Pruning check: For each candidate (in sorted order), evaluate the resulting state. If the evaluator's score $V(p_\theta, \{s'\})(s)$ is below a threshold $v_{\text{th}}$, prune this subtree — do not explore it further. This is the backtracking trigger: the algorithm abandons this branch and moves to the next candidate.

4. Recursive exploration: If the candidate passes the pruning check, recursively call DFS on the new state at depth $t+1$, continuing down the most promising branch.

5. Backtracking: If a recursive call returns (either because it reached a solution, hit the depth limit, or all its candidates were pruned), the algorithm returns to the parent state and tries the next most promising candidate — this is the backtracking step that distinguishes DFS from greedy search.

Where DFS is used. The paper applies DFS to Mini Crosswords, which has a deeper tree (up to $T = 10$ words to fill) and where wrong early choices frequently only reveal themselves as problems several steps later. The key parameters:

• Thought generation: The propose prompt generates candidates for the next word to fill, along with confidence levels. These are aggregated across multiple proposal calls to produce a sorted list.

• State evaluation: Each remaining clue is evaluated independently for fillability given current letter constraints. If any remaining clue is deemed "impossible" to fill (e.g., "v1. To heap: tm_s_" — no valid English word fits), the state is pruned. This is a conjunctive evaluation: all clues must be possible for the state to survive.

• Threshold $v_{\text{th}}$: The paper operationalizes this as the "impossible" judgment — if any clue is deemed impossible, the state's value is effectively 0 and the subtree is pruned. The threshold is binary (possible vs. impossible) rather than a continuous value.

• Step limit: DFS is limited to 100 total search steps (node expansions). The deepest explored state is rendered as the final output.

Why DFS with backtracking? DFS is appropriate for deeper trees where BFS's memory requirements would be prohibitive (BFS stores the entire frontier, which grows exponentially with depth). DFS explores one path deeply before trying alternatives, which is efficient when the tree is deep and evaluation at each step can reliably detect dead ends. The backtracking mechanism is essential because in Crosswords, a word choice that seems fine at step 3 may make a crossing word impossible to fill at step 7 — DFS needs to be able to unwind those decisions and try different words at step 3. Without backtracking (as the paper's ablation "-backtrack" demonstrates), the algorithm is equivalent to greedy search and achieves only 20% word-level success — less than half of DFS with backtracking's 60%.

The relationship between search algorithm and tree structure. The paper's choice of BFS vs. DFS is not arbitrary — it reflects a deeper principle about matching the search strategy to the problem's dependency structure:

• In Game of 24 and Creative Writing, decisions at each step are relatively independent. A good first equation doesn't guarantee success, but it doesn't preclude it either — the remaining numbers can still be combined in many ways. BFS with a moderate beam width works because keeping multiple options alive at each step hedges against evaluation errors.

• In Crosswords, decisions have strong long-range dependencies. Filling "h2. motor" constrains "v3" (which crosses at position 3 with 't') and "v5" (which crosses at position 5 with 'r'), and those constraints cascade to other words. A choice that looks fine locally may be globally impossible. DFS with backtracking is necessary because it can follow a commitment deeply until it either succeeds or provably fails, then unwind.

This match between algorithm and dependency structure is a design insight that the paper demonstrates through the task-specific instantiations but does not formalize as a general principle — it remains implicit in the engineering choices.

How Prior Methods Emerge as Special Cases of ToT

The paper explicitly positions ToT as a unifying framework by showing how existing prompting methods correspond to trees with restricted structures (Section 3, Figure 1):

Input-Output (IO) prompting is a tree of depth 0 — there are no intermediate thoughts. The input maps directly to the output with no exploration. Formally: $T = 0$, $G(p_\theta, s_0, 1)$ directly produces the output $y$.

Chain-of-Thought (CoT) prompting is a tree of depth $T > 0$ but breadth $b = 1$ — a single chain of thoughts with no branching. At each step, exactly one candidate is generated ($k = 1$), there is no state evaluation (you always take the one candidate), and there is no pruning or backtracking. Formally: $G(p_\theta, s, 1)$ is called sequentially $T$ times, each time producing exactly one next thought, and the final thought chain produces the output.

Self-Consistency with CoT (CoT-SC) is a tree where $k > 1$ independent chains are sampled (breadth at the root), but there is no interaction between branches and no branching within a chain. All states are evaluated only at the leaves (final answers), where a majority vote selects the output. Formally: $G(p_\theta, s_0, k)$ produces $k$ independent chains, each chain is $T$ steps deep with $b = 1$, and $V$ is applied only at depth $T$ as majority voting over final answers. There is no local exploration — each chain makes irrevocable commitments at each step.

Iterative refinement (self-refine) is a tree where each node has exactly one child — it is a linear sequence of revisions rather than a branching tree. At each step, the model conditions on its previous output and generates a refined version. Formally: $T$ is the number of refinement iterations, $G(p_\theta, s, 1)$ produces a single refinement, and the state evaluator is implicit (the refinement prompt itself encodes the judgment that the previous output was inadequate). There is no branching and no backtracking — the model always moves forward, never sideways or backward.

What ToT adds structurally relative to these special cases:

• Relative to CoT: ToT adds branching ($k > 1$ candidates at each step) and pruning (state evaluation eliminates unpromising paths). This means the model is no longer forced to commit to its first thought — it can generate multiple options and select the best, which is precisely what addresses the "60% of CoT samples fail at step 1" problem in Game of 24.

• Relative to CoT-SC: ToT adds local exploration within each chain (branching at intermediate steps, not just at the root) and structured interaction between branches (state evaluation at each depth, not just majority voting at the leaves). This means the model can explore different continuations of a promising partial solution, rather than treating each chain as an independent monolithic unit.

• Relative to iterative refinement: ToT adds breadth (trying different approaches, not just refining one approach) and backtracking (abandoning a path that isn't working, rather than trying to fix it incrementally). Refinement is a form of local hill-climbing; ToT is a form of global search.

The paper's claim that ToT "generalizes" these methods is technically accurate — they are all special cases of the tree-search framework with specific parameter settings — but the more important point is that ToT enables configurations (branching with pruning, DFS with backtracking, intermediate state evaluation) that are impossible to express in any of the prior paradigms. This is not just a taxonomic exercise; it identifies the specific structural limitation (no branching, no local evaluation, no backtracking) that causes prior methods to fail on the tasks the paper introduces.

Summary of Design Choices and Their Justifications

The following table synthesizes the key design choices across the three task instantiations and the rationale for each:

Why no fine-tuning? The paper deliberately uses a frozen GPT-4 model throughout. This is both a strength (the framework is immediately applicable to any sufficiently capable LM, with no training pipeline or curated dataset required) and a conscious methodological choice: it isolates the contribution of the search architecture from the contribution of improved model capabilities. If the paper had fine-tuned a model specifically for tree search, it would be unclear whether the gains came from the tree structure or from the additional training data. By using the exact same GPT-4 model that achieves 4% with CoT and 7.3% with IO on Game of 24, and showing that the same model achieves 74% when embedded in ToT, the paper cleanly demonstrates that the inference-time search structure is the causal factor — the capabilities were latent in the model all along.

Why temperature 0.7? The paper uses a sampling temperature of 0.7 for all experiments. This is a standard choice that provides a balance between diversity (needed for generating distinct candidate thoughts) and quality (higher temperatures would produce more diverse but lower-quality candidates). The paper does not ablate temperature, so it is an implicit design choice rather than a tuned parameter.

4. Key Insights and Innovations

Innovation 1: Reframing LM Problem-Solving as Tree Search Over Semantic Units

The paper's most fundamental intellectual move is not proposing a particular search algorithm or prompt design, but rather reconceptualizing what it means for a language model to "solve a problem" during inference. Prior to this work, the dominant paradigm — whether IO prompting, chain-of-thought, or self-consistency — implicitly treated problem-solving as generation from a distribution: the model produces text (possibly with intermediate steps), and the quality of the solution depends on how much probability mass the model assigns to correct reasoning paths. Under this view, improving performance means either making the model better (training) or sampling more aggressively from the existing distribution (best-of-N, majority voting).

ToT fundamentally reframes the activity as search through a combinatorial space. The model is no longer a distribution to sample from, but a proposal engine that suggests candidate next steps and an evaluation engine that judges their promise — two roles that are deployed iteratively within a search algorithm that systematically explores a tree of partial solutions. This is a category shift: it moves the intellectual center of gravity from statistical generation to heuristic search, connecting modern LMs to the classical AI tradition of Newell, Shaw, and Simon (1959) that has been largely absent from the deep learning era's focus on scaling.

Why is this more than a terminology change? Because it changes what interventions are possible. In the generation-from-distribution view, the only knobs are temperature, number of samples, and prompt engineering. In the search view, the experimenter can independently design (a) the granularity of decision steps (thought decomposition), (b) how alternatives are proposed (generation strategy), (c) how partial solutions are evaluated (heuristic design), and (d) the exploration strategy (BFS, DFS, A*, MCTS). Each of these is a separate axis of innovation that is invisible in the generation paradigm. The paper demonstrates this by configuring all four axes differently for Game of 24, Creative Writing, and Crosswords — something that would be impossible to express in a CoT or self-consistency framework.

The fact that IO, CoT, CoT-SC, and iterative refinement all emerge as special cases of ToT (trees with specific depth/breadth/evaluation constraints) is not just taxonomic elegance — it diagnoses exactly what structural limitation makes each prior method fail on the paper's three tasks. CoT fails not because the model lacks mathematical ability, but because the tree is restricted to breadth 1 (no alternative exploration at any step) and has no evaluation mechanism to detect dead ends. CoT-SC adds breadth at the root but still lacks local branching within chains and has no mechanism for intermediate pruning. The paper's error analysis (Figure 3b) operationalizes this diagnosis: ~60% of CoT samples on Game of 24 fail at the first step — a failure mode that is structurally guaranteed by breadth-1 search (you get one first thought, and if it's bad, the entire chain is wasted) and structurally addressed by ToT (you generate multiple first thoughts and evaluate which are promising before committing).

This reframing is a fundamental conceptual advance rather than an incremental improvement, because it opens a design space that was previously invisible. It says: the problem is not that LMs lack reasoning capability (GPT-4 clearly knows arithmetic and can evaluate partial equations), but that the inference procedure does not engage these capabilities in a deliberate, search-structured way. The 4% → 74% jump on Game of 24 is not primarily a story about better prompts — it is a story about a better organizing architecture for the same prompts used within a search loop.

Innovation 2: The Language Model Itself as a Learned Heuristic Function

Classical AI search requires a heuristic function $h(s)$ that estimates how promising a state $s$ is — the distance to a goal, the probability of success, or a relative ranking compared to alternatives. Historically, heuristics have come from exactly two sources: programmed rules hand-crafted by human experts (DeepBlue's chess evaluation, A* pathfinding heuristics) or learned models trained on massive amounts of outcome data (AlphaGo's value network, trained on millions of self-play games). The paper introduces a genuine third category: prompting a pretrained language model to deliberate about a state in natural language and produce a heuristic judgment.

This is conceptually striking because it violates the usual assumption that heuristics must be either simple (so humans can encode them) or trained (so machines can learn them from data). The LM-as-heuristic approach leverages a third resource: the commonsense, mathematical, and linguistic knowledge already embedded in the model's parameters from pretraining, which can be elicited through natural-language reasoning prompts without any task-specific training. The LM can perform few-shot lookahead simulation ("can 5, 5, 14 reach 24? 5+5+14=24, yes"), apply commonsense constraints ("1, 2, 3 are too small to ever reach 24"), and reason about linguistic constraints ("no English word starts with 'tzxc'") — all expressed in the same natural language the model uses for generation.

Why does this matter beyond "it works"? Because it decouples heuristic quality from task-specific engineering effort. Programmed heuristics require the human designer to anticipate all relevant evaluation criteria for each new task — possible for chess or the Game of 24, but essentially impossible for Creative Writing (what is the rule-based heuristic for "coherence of a writing plan"?). Learned heuristics require large training datasets of state-outcome pairs — feasible for games with simulators, but expensive or impossible for open-ended reasoning tasks. The LM-as-heuristic approach requires only a natural-language prompt describing the evaluation criteria, making it general-purpose in a way that neither programmed nor learned heuristics can match across diverse tasks.

The paper also demonstrates a key robustness property: the heuristic does not need to be perfect. The state evaluator makes mistakes — the Crosswords evaluator sometimes deems solvable states as "impossible" (pruning states that actually lead to solutions) and sometimes fails to prune genuinely impossible states. But the surrounding search architecture (beam width, backtracking) is designed to tolerate heuristic noise. BFS with $b = 5$ keeps multiple candidates alive, so an evaluation error that incorrectly prunes one good state leaves four others. DFS with backtracking can recover from following a false-positive (an "impossible" state that was mistakenly judged possible) by eventually hitting a dead end and backtracking. This graceful degradation under heuristic error is a property that classical A* search also possesses, but the paper demonstrates it in a setting where the heuristic is a black-box LM call rather than an $\epsilon$-admissible mathematical function.

The comparative voting strategy (used for Creative Writing) is a particularly elegant instantiation of the LM-as-heuristic idea. Rather than asking the LM to produce an absolute coherence score for each plan — a hard calibration problem — the paper reframes state selection as a multi-choice QA task: "here are 5 candidate plans, which is most promising?" The LM's relative judgments are likely more reliable than its absolute judgments, and the voting mechanism (5 independent LM calls, majority wins) provides a simple form of ensembling that increases robustness. This is a practical insight about LM psychology disguised as an architectural choice: the paper is exploiting the fact that LMs are better at comparison than absolute assessment, a property that has been observed in other contexts (e.g., RLHF preference comparisons vs. scalar reward prediction) but is here deployed as a search heuristic.

This innovation is fundamental rather than incremental because it establishes a new category of heuristic design that did not previously exist in either classical AI or modern ML. It is not "using an LM to evaluate text" (which is common) — it is using an LM as a search control mechanism embedded within a tree exploration algorithm, making decisions about which branches of a reasoning process to pursue and which to abandon. The fact that this can be done with a frozen, off-the-shelf model — no fine-tuning, no reward modeling, no outcome data — makes it a uniquely accessible form of heuristic that lowers the barrier to applying deliberate search to arbitrary reasoning problems.

Innovation 3: Diagnosing the Failure Mode of Left-to-Right Decoding as Premature Commitment

The paper's error analysis on Game of 24 (Figure 3b) is one of those rare experiments that seems obvious in retrospect but crystallizes a problem that the field had been living with without explicitly naming. The finding is stark: approximately 60% of CoT samples fail after generating only the first step — or equivalently, after producing just the first three words of their reasoning chain. This is not a story about insufficient model knowledge (the model clearly knows arithmetic) or insufficient sampling (best-of-100 CoT only reaches 49%). It is a story about premature commitment: the left-to-right decoding process makes an irrevocable local decision at step 1, and if that decision is poor, the entire downstream trajectory is wasted computation that cannot recover.

This diagnosis is intellectually significant because it identifies the specific structural mechanism by which standard prompting fails, rather than just observing that it fails. The failure is not that the model generates bad solutions — it is that the model has no opportunity to reconsider a bad first step. In a tree-search framework, a bad first thought is simply one branch among many — the evaluator can recognize it as unpromising and prune it, while other branches with different first thoughts continue to be explored. The paper's scaling analysis (Figure 3a) visualizes this dramatically: CoT (best-of-k) improves with more samples but plateaus, while ToT with increasing beam width continues to improve because it is spending compute on exploring different first steps rather than repeatedly sampling from the same flawed distribution.

This concept of premature commitment as a failure mode generalizes beyond Game of 24. It explains why CoT underperforms on any task where the correct reasoning path requires an early decision that is unlikely under the model's default distribution — which includes essentially all problems requiring non-obvious insights, unconventional approaches, or exploration of multiple hypotheses. The Crosswords results tell the same story in a different structure: early word choices cascade into constraints that may only reveal themselves as impossible several steps later, and without backtracking (which DFS provides), the model is stuck with its early commitments. The paper's ablation removing backtracking from Crosswords ("-backtrack" in Table 3) drops word-level success from 60% to 20%, directly quantifying the cost of premature commitment in a domain with long-range dependencies.

This is a diagnostic innovation — it gives the field a precise vocabulary and measurement methodology for understanding why tasks resist current methods — rather than a methodological one. But diagnostic concepts can be as impactful as new methods: the Chinchilla scaling laws were fundamentally a diagnostic insight ("we're training models that are too big for their data budget") that reoriented an entire subfield's resource allocation. Similarly, "premature commitment as the bottleneck" suggests a clear research agenda: for any task where LMs struggle, measure at which step failures concentrate. If failures concentrate early (as in Game of 24), the solution is branching and evaluation at those early steps — exactly what ToT provides. If failures are distributed uniformly, the bottleneck may be fundamental capability rather than search structure, and more test-time compute won't help (this connects directly to the findings of the compute-optimal scaling paper by Snell et al., 2024, which showed that test-time compute is ineffective on problems where the base model's pass@1 is near zero).

The paper is making an implicit claim about the nature of LM reasoning errors: they are often not deep failures of understanding, but rather local, recoverable mistakes that cascade because the inference procedure has no error-correction mechanism. This is a more optimistic diagnosis than "the model doesn't understand the task" because it implies that better inference-time architectures can unlock capabilities that are already latent in the model — which is precisely what the 4% → 74% jump demonstrates. It also has practical implications for where to invest effort: improving the model's first-step accuracy (through fine-tuning) versus improving the inference procedure's ability to recover from first-step errors (through search) are different interventions with different costs, and the paper provides evidence that the latter can be remarkably effective.

Innovation 4: Modularity as a Design Principle Rather Than an Afterthought

Many papers propose a new method and, almost as an afterthought, note that it is "flexible" or "can be adapted to different settings." What distinguishes ToT is that modularity is the core contribution, not a secondary property. The paper explicitly decomposes the framework into four independent axes — thought decomposition, thought generation, state evaluation, and search algorithm — and argues that progress on any one axis can be combined with arbitrary choices on the others. This is not the usual "our method has hyperparameters you can tune" claim; it is a deliberate architecture for composable innovation.

The evidence for this being a genuine insight rather than a truism is the paper's demonstration that different tasks require different configurations of the same components, and that these configurations can be chosen based on task properties (thought space richness, tree depth, dependency structure) rather than discovered through expensive hyperparameter search. The generation strategy choice (i.i.d. vs. sequential proposal) follows from whether the thought space is rich or constrained. The evaluator choice (independent value vs. comparative voting) follows from whether states can be meaningfully assessed in isolation. The search algorithm choice (BFS vs. DFS) follows from tree depth and dependency structure. These are principled design decisions rather than arbitrary choices, and the paper provides the conceptual vocabulary for making them.

This modularity also means that each component can be improved independently as the underlying technology evolves. If better LMs become available, they can be swapped in as the generator or evaluator without changing the search architecture. If someone invents a better search algorithm (A*, MCTS), it can be plugged into the ToT framework without changing how thoughts are generated or evaluated. If someone develops a more sample-efficient way to evaluate states (perhaps a small fine-tuned verifier model), it can replace the prompted evaluator while keeping the same search structure. This is the same design philosophy that made deep reinforcement learning composable — separate the policy, value function, and environment dynamics so each can be studied and improved independently — applied to LM-based reasoning.

The paper also demonstrates that this modularity enables straightforward ablation studies that isolate contributions. The "oracle and ablation studies" in Section 4.3 for Crosswords — comparing full ToT, ToT without pruning ("-prune"), and ToT without backtracking ("-backtrack") — cleanly separates the contribution of each component. The finding that removing pruning slightly hurts overall performance but actually solves 3 games that pruning misses (because the evaluator incorrectly pruned them) reveals a nuanced tradeoff between exploration and exploitation that would be invisible in a monolithic system. Similarly, removing backtracking causes a catastrophic drop from 60% to 20% word-level success, directly quantifying the value of the ability to unwind bad commitments.

This is best understood as a meta-contribution about how to organize research on LM reasoning. Rather than proposing "the" method (which would quickly become obsolete as base models improve), the paper proposes a framework within which many methods can be expressed, compared, and combined. The framework's generality — the fact that IO, CoT, CoT-SC, self-refinement, and self-eval guided decoding are all special cases — means it provides a common language for describing and relating approaches that previously appeared disparate. This taxonomic function may ultimately be more impactful than any specific task performance number, because it helps the field understand what dimensions matter for inference-time reasoning and how to think about new methods in relation to existing ones.

The modularity insight is fundamental in its implications for how the field should approach LM reasoning, but the paper's instantiation of it is incremental in the sense that the specific components (BFS, DFS, voting, value prompting) are individually simple. The contribution is the architecture, not the components — much like the Transformer's contribution was the attention-based architecture, not the individual operations of matrix multiplication and softmax that it composes.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper uses three custom-constructed task datasets, not a standard benchmark suite. Game of 24: scraped from 4nums.com, which contains 1,362 games sorted from easy to hard by human solving time; the paper uses "a subset of relatively hard games indexed 901-1,000" for testing, yielding 100 test games (Section 4.1). Creative Writing: 100 inputs constructed by sampling 4 random sentences each from randomwordgenerator.com; there is no groundtruth passage since the task is open-ended (Section 4.2). Mini Crosswords: scraped from GooBix, containing 156 games of 5×5 mini crosswords; 20 games with indices 1, 6, ..., 91, 96 are used for testing, and 5 games (136, 141, 146, 151, 156) are held out for few-shot prompting (Section 4.3). No explicit training/validation/test split is described beyond this; the framework uses a frozen model with no training, so the concept of a training set applies only to the few-shot examples in prompts, not to model fitting.

• Base model(s). All main experiments use GPT-4 in Chat Completion mode, accessed between May 5-16, 2023, with a sampling temperature of 0.7 unless otherwise stated (Section 4, opening paragraph). The paper does not specify which exact GPT-4 checkpoint (e.g., gpt-4-0314 vs. a later version), but the date range constrains it to an early 2023 release. The choice of GPT-4 is motivated implicitly: the paper aims to test whether deliberate search helps even when the base model is already highly capable. Additional experiments in Appendix B.2 run GPT-3.5-turbo on Game of 24 and Creative Writing to test generalization to weaker models, and find the "ToT > CoT > IO" ordering holds (Game of 24: GPT-3.5 + ToT achieves 19% vs. GPT-4 + ToT's 74%; Creative Writing: GPT-3.5 + ToT achieves 6.62 average coherence score vs. 5.16 for CoT). A cross-model experiment where GPT-4 generates thoughts and GPT-3.5 evaluates them (achieving 64% on Game of 24, vs. 31% for the reverse configuration) is used to diagnose whether generation or evaluation is the bottleneck.

• Metrics. The paper uses task-specific success metrics, not a uniform accuracy measure. Game of 24: success rate (%) — the fraction of 100 test games for which the model outputs a valid equation that equals 24 and uses each input number exactly once (Section 4.1). Creative Writing: GPT-4 zero-shot coherency score on a 1-10 scale (5 scores sampled per output and averaged; the paper reports a standard deviation of ~0.56 across the 5 scores, indicating reasonable consistency) and human pairwise preference judgments from a blind study where a subset of authors compared CoT vs. ToT passage pairs with order randomized over 100 inputs; three outcomes are possible: CoT preferred, ToT preferred, or "similarly coherent" (Section 4.2). Mini Crosswords: three granularities of success — letter-level accuracy (fraction of 25 letters per board correct, averaged over 20 games), word-level accuracy (fraction of 10 words per board correct), and game-level accuracy (fraction of 20 games fully solved) (Section 4.3). The grading for Game of 24 checks both equation validity and the constraint that each input number appears exactly once; for Crosswords, correctness is measured against the ground-truth board from GooBix. For Creative Writing, there is no ground truth — evaluation is purely based on coherence judgments.

• Baselines. Four baselines are evaluated across tasks, with variations per task:

  1. Input-Output (IO) prompting: the model receives task instructions and few-shot input-output examples, then directly generates the final output with no intermediate reasoning steps. For Game of 24: 5-shot prompt with in-context examples; for Creative Writing: zero-shot (given the open-ended nature); for Crosswords: 5-shot prompt with example boards.
  2. Chain-of-Thought (CoT) prompting (Wei et al., 2022): the model generates intermediate reasoning steps before the final output. For Game of 24: each example includes 3 intermediate equations decomposing the arithmetic; for Creative Writing: zero-shot with a prompt to "first make a brief plan then write the passage"; for Crosswords: intermediate words are listed in order h1..5 then v1..5.
  3. CoT with Self-Consistency (CoT-SC) (Wang et al., 2022): k = 100 independent CoT chains are sampled, with the majority final answer selected. Evaluated only on Game of 24 (9.0% success); not applied to Creative Writing (output space is continuous passages, majority voting is undefined) or Crosswords (output space is 25-letter boards, too large and interdependent for simple majority voting).
  4. Iterative refinement (self-refine): the model conditions on its previous output and generates a refined version. For Game of 24: up to 10 iterations with ground-truth correctness feedback ("reflect on your mistakes and generate a refined answer" if the output is incorrect — note this uses oracle feedback, making it an upper bound on practical refinement approaches). For Creative Writing: up to k = 5 iterations where the LM decides if the passage is "perfectly coherent" and if not, generates a refined one.

  Additionally, oracle upper bounds are computed for IO and CoT on Game of 24 by taking the best of k samples for k \in [1, 100] and reporting the success rate as if an oracle selected the correct answer when it exists in the sample set. This establishes the performance ceiling for sampling-based approaches without search.

• Generation budget / compute accounting. The paper measures cost in three ways, all reported in Appendix B.3: (a) completion tokens (tokens generated by the model), (b) prompt tokens (tokens in the input context), and (c) API dollar cost at then-current GPT-4 pricing. For Game of 24 (Table 7): ToT costs 5.5k completion tokens and $0.74 per case, compared to 6.7k tokens and$0.47 for CoT best-of-100, and 1.8k tokens and $0.13 for IO best-of-100. The paper explicitly notes that ToT's cost is comparable to ~100 CoT trials while achieving substantially higher success (74$0.32 per case vs. ~0.9k tokens and $0.07 for CoT — roughly a 4-5× cost multiplier. A key omitted accounting: the paper does not report token counts or costs for Crosswords, nor does it amortize the cost of DFS across the variable number of search steps (the 100-step DFS limit means worst-case cost is substantially higher than best-case). The total experiment cost is estimated at roughly$106 for Game of 24 (100 tasks × $0.74) +$32 for Creative Writing (100 tasks × $0.32) + "within$100" for Crosswords.

• Cross-validation / statistical protocol. The paper does not employ cross-validation or statistical significance testing in the conventional sense. For Game of 24 and Crosswords, there is no model training, so no need to separate train/test. The test sets are fixed: 100 games for Game of 24, 100 inputs for Creative Writing, 20 games for Crosswords — these are relatively small test sets, particularly Crosswords (n = 20). No confidence intervals, standard errors, or significance tests are reported for any result. For Creative Writing, the human evaluation uses a blind pairwise comparison protocol with randomized order over 100 passage pairs, which is a reasonably rigorous subjective evaluation. The 5-sample scoring for GPT-4 coherency scores reports a standard deviation (~0.56) as a measure of within-output rating consistency, but no between-output or between-method statistical comparisons are provided. The oracle and ablation studies for Crosswords (Table 3) report point estimates on the same 20 games with no uncertainty quantification, making it difficult to assess whether differences (e.g., 60% vs. 65.4% for "-prune") are statistically meaningful or noise at this small sample size.

Main Quantitative Results

Game of 24: BFS Search Transforms Near-Zero Performance to Near-Ceiling

The headline result appears in Table 2: ToT with breadth b = 5 achieves 74% success on the 100-game test set, compared to 4.0% for CoT, 7.3% for IO, and 9.0% for CoT-SC with k = 100. The absolute gap is enormous — a ~70 percentage point improvement over the best non-ToT method (CoT-SC at 9%) and a ~18.5× relative improvement over CoT.

Breaking down the ToT scaling behavior (Figure 3a, Table 2): at b = 1 (no beam — only the single best-evaluated thought is kept at each step), ToT achieves 45%, already ~11× better than CoT. Increasing breadth to b = 5 yields 74%, demonstrating that maintaining multiple candidates is valuable — the evaluator is imperfect, and keeping alternatives alive hedges against evaluation errors. Figure 3a plots ToT success rate against "nodes visited" (tree nodes expanded during search) and overlays IO and CoT "best of k" curves, where k is mapped to nodes visited in a bandit analogy. The key finding: ToT at any given node budget substantially outperforms the equivalent number of independent samples. At ~20 nodes visited, ToT achieves roughly 50-60% while best-of-20 CoT achieves approximately 30%. At the rightmost point (~100+ nodes for ToT b=5, though the exact mapping depends on beam size), ToT reaches 74% while best-of-100 CoT reaches only 49%. This is the core evidence that structured search over a tree is more sample-efficient than independent parallel sampling — nodes in a tree share computation (evaluations at early steps inform multiple downstream paths) rather than being independent.

The oracle analysis in Table 2 contextualizes these gains: "IO (best of 100)" achieves 33% and "CoT (best of 100)" achieves 49%. These numbers represent the maximum possible performance if an oracle could perfectly select the correct answer whenever it exists in 100 independent samples. The fact that ToT (74%) far exceeds even the oracle upper bound for CoT (49%) means that ToT is not merely selecting better among already-generated solutions — it is generating solutions that would not appear in 100 independent CoT samples at all. The search process, by evaluating and pruning intermediate steps, guides generation into regions of the solution space that random sampling rarely visits. This is a stronger claim than "ToT is a better reranker" — it is a better generator because the generation at each step is conditioned on a state that survived evaluation, which is a different distribution than unconditional CoT sampling.

The error analysis in Figure 3b operationalizes why. It shows, for each of the 3 thought steps, the fraction of samples where CoT or ToT fails at that step (i.e., produces an invalid or dead-end intermediate equation). For CoT, approximately 60% of samples fail at step 1 — meaning the first intermediate equation is already unrecoverable. For ToT (b = 5), the step-1 failure rate is roughly 25%. Since ToT evaluates and prunes after step 1, it filters out most of these early failures before they consume downstream computation. The step-2 failure rate is also lower for ToT (~30% cumulative failures by step 2 vs. ~85% for CoT), and by step 3 the cumulative failure rates are roughly 26% for ToT vs. 96% for CoT (consistent with the final success rates of 74% and 4%). This directly visualizes the "premature commitment" failure mode: CoT commits to a bad first step in 60% of attempts and never recovers; ToT generates multiple first steps, evaluates them, and prunes the bad ones.

The iterative refinement baseline (IO + Refine, k = 10) achieves 27% — better than base IO (7.3%) but far below ToT (74%). This quantifies the gap between local hill-climbing (start from one answer, iteratively improve it) and global search (explore fundamentally different approaches from the beginning). Refinement is limited by the quality of the initial guess — if the initial IO output is far from correct, refinement can only make local improvements, not discover a completely different solution strategy. ToT's branching at the first step allows it to explore fundamentally different arithmetic decompositions.

Creative Writing: Coherence Gains Measured by Both Automated and Human Evaluation

Figure 5a shows average GPT-4 coherency scores (1-10 scale, 5 samples averaged per output, 100 tasks): ToT achieves 7.56, compared to 6.93 for CoT and 6.19 for IO. The absolute gain over CoT is 0.63 points — modest but consistent. More importantly, Figure 5b shows the human pairwise comparison: out of 100 passage pairs evaluated blindly, humans prefer ToT over CoT in 41 pairs, prefer CoT over ToT in 21 pairs, and judge them "similarly coherent" in 38 pairs. This is a statistically meaningful preference (roughly 2:1 in favor of ToT among pairs with a discernible difference, or 41% vs. 21% overall), confirming that the automated metric's preference for ToT is not an artifact of GPT-4 favoring its own generation style.

The iterative refinement baselines demonstrate that refinement is more effective on this natural language task than on Game of 24: IO + refine improves the IO score from 6.19 to 7.67 (surpassing ToT's 7.56), and ToT + refine improves ToT's score from 7.56 to 7.91. The paper interprets this as refinement being "a third approach to thought generation in the ToT framework, where new thoughts can arise from refining old thoughts instead of i.i.d. or sequentially generated" — suggesting that search and refinement are complementary rather than competing approaches, and the framework can accommodate both.

A nuance: the automated coherency scoring is performed by GPT-4 itself, which introduces a potential self-assessment bias. The paper partially mitigates this concern with the human evaluation (Figure 5b), which confirms the direction of the effect. However, the absolute scores (7.56 vs. 7.91) should be interpreted cautiously — they reflect GPT-4's own coherence standards, which may not align perfectly with human judgments of literary quality. The paper does not report human absolute quality scores, only pairwise preferences, so we cannot calibrate the GPT-4 scores against a human baseline.

The Creative Writing task structure (ToT with depth 2, breadth b = 1, k = 5 plans then k = 5 passages) means the search is quite limited compared to Game of 24 — it is essentially a two-stage generate-and-vote pipeline rather than a deep exploration. The gains come primarily from (a) generating diverse plans and selecting the best via voting, and (b) generating diverse passages from the best plan and selecting the best. This is closer to "best-of-5 with an intermediate planning step" than to the kind of combinatorial search seen in Game of 24. The paper's claim that ToT enables "deliberate decision making" is less strongly demonstrated here — the deliberation is compressed into a single plan-selection step.

Mini Crosswords: DFS with Backtracking Enables Recovery from Dead Ends

Table 3 presents results at three granularities for the 20-game test set:

ToT achieves 60% word-level success, compared to 15.6% for CoT — a roughly 3.8× relative improvement. At the letter level, ToT reaches 78% (vs. 40.6% for CoT). At the most stringent game-level metric, ToT solves 4 out of 20 games completely, while CoT solves only 1.

The oracle analysis ("+best state") reveals that the DFS search process discovers correct solutions for 7 out of 20 games — but the heuristic output selection (simply taking the deepest explored state) only surfaces 4 of these. This gap (7 vs. 4) indicates that the state evaluator sometimes assigns higher scores to incorrect states than to the correct one, or that the search explores the correct solution but does not reach sufficient depth to output it within the 100-step limit. The paper acknowledges this: "our simple output heuristics can be readily improved."

The pruning ablation ("−prune") removes the state evaluation step entirely — DFS explores without pruning any states as impossible. This drops word-level success from 60% to 41.5%, confirming that the evaluator's pruning decisions are net beneficial. However, the pruned version actually finds correct solutions for 4 games (vs. full ToT's 4, but 3 of these are different games that full ToT cannot solve within 100 steps because it prunes them prematurely). This is the most nuanced finding in the paper: the state evaluator is simultaneously too aggressive (it prunes some solvable states, causing full ToT to miss 3 games that unpruned search finds) and net beneficial (overall performance is higher with pruning because it focuses computation on promising branches). The paper attributes the false-negative pruning to GPT-4's limited vocabulary — "5×5 crosswords by design have some rare or obsolete words that GPT-4 cannot recognize" (e.g., "agend" as an obsolete form of "agendum," which GPT-4 deems a typo for "agenda" and therefore judges the state impossible). This reveals that the heuristic's quality is bottlenecked by the LM's knowledge limitations, not just its reasoning capabilities.

The backtracking ablation ("−backtrack") replaces DFS with a greedy approach: always fill the most promising clue, without backtracking, allowing overwrites of previously filled words. This drops word-level success to 20% (from 60%) and solves only 1 game — essentially reducing performance to CoT levels. This is the cleanest demonstration of backtracking's value: in a constraint satisfaction problem where early choices cascade, the ability to unwind bad commitments and try alternatives is essential, and greedy forward progress is barely better than random.

Table 3 also notes that the "-prune" variant, despite lower overall performance, actually finds the correct solution for 4 games (and outputs 1 via heuristic), with 3 of these being games that full ToT cannot solve within 100 steps. This implies that a more sophisticated evaluation heuristic — one that could recognize obscure words or rare letter patterns — would both improve pruning accuracy (eliminating false negatives) and unlock the solutions found by unpruned search. The paper does not explore hybrid strategies (e.g., pruning conservatively, or adaptively relaxing pruning when search stalls), which is a natural next step.

Ablation Studies and Robustness Checks

Breadth limit (b) in BFS for Game of 24 (Figure 3a): Increasing b from 1 to 5 monotonically improves success rate, with b = 1 achieving 45% and b = 5 achieving 74%. The curve in Figure 3a shows diminishing returns — the jump from b = 1 to b = 2 is larger than from b = 4 to b = 5 — suggesting that the marginal value of additional breadth decreases as the beam already captures the most promising candidates. No b > 5 is tested, leaving open whether further breadth would yield additional gains or plateau.

Number of evaluation samples (implicit): For Game of 24, the paper samples 3 value judgments per thought candidate and aggregates them. No ablation varying the number of evaluation samples (e.g., 1 vs. 3 vs. 5 vs. 10) is reported, so the sensitivity of performance to evaluation budget is unknown. For Creative Writing, 5 votes are sampled at each step; no ablation on vote count is reported.

Generation strategy cross-task applicability: The paper uses i.i.d. sampling for Creative Writing and sequential proposal for Game of 24 and Crosswords, motivated by thought-space richness. However, it does not test the alternative strategy on each task (e.g., would sequential proposal work better for Creative Writing? Would i.i.d. sampling work for Game of 24 with deduplication?). This leaves open whether the strategy choice is genuinely important or merely incidental.

GPT-3.5 vs. GPT-4 for Game of 24 (Appendix B.2, Table 5): GPT-3.5 + ToT achieves 19% success, compared to GPT-4 + ToT's 74%. The gap between models is much larger for ToT (74% vs. 19%) than for CoT (GPT-4: 4.0% vs. GPT-3.5: 3%) or IO (GPT-4: 7.3% vs. GPT-3.5: 6%). This suggests that ToT amplifies the underlying model's capabilities — a stronger base model benefits disproportionately from search structure. Performance also depends on few-shot prompt design: for GPT-3.5, the Game of 24 proposal prompt was changed from 1-shot to 3-shot "to make it work," indicating sensitivity to prompt engineering that is not explored systematically.

Cross-model generation and evaluation for Game of 24 (Appendix B.2): Using GPT-4 for thought generation and GPT-3.5 for evaluation achieves 64%, while the reverse (GPT-3.5 generation + GPT-4 evaluation) achieves only 31%. This demonstrates that thought generation quality is the primary bottleneck — a strong evaluator cannot compensate for a weak generator — and that generation and evaluation can be performed by different models, which is relevant for cost optimization (GPT-3.5 is substantially cheaper than GPT-4).

GPT-3.5 for Creative Writing (Appendix B.2, Table 6): GPT-3.5 + ToT achieves a coherency score of 6.62, exceeding GPT-4 + IO (6.19) and approaching GPT-4 + CoT (6.93). This is a notable result: a weaker model with search structure can match or exceed a stronger model without it, on at least one metric. The paper does not perform the corresponding human evaluation for GPT-3.5, so it's unclear whether the automated score advantage reflects genuine quality improvement or GPT-4's scoring bias.

Extension to standard NLP tasks (Appendix B.1, Table 4): A simple zero-shot ToT-BFS configuration (sample 5 strategies, vote for best; sample 5 solutions from best strategy, vote for best) is applied to GSM8K (math word problems) and StrategyQA (multi-hop reasoning questions requiring external knowledge). On GSM8K, ToT achieves 90% vs. CoT's 86% and IO's 51%. On StrategyQA, ToT achieves 83% vs. CoT's 82% and IO's 73%. The gains are modest (4 points on GSM8K, 1 point on StrategyQA) compared to the enormous jumps on Game of 24 and Crosswords. This is consistent with the paper's framing: ToT is most valuable when tasks require exploration, planning, or backtracking. GSM8K and StrategyQA, while requiring reasoning, are more amenable to single-path CoT solutions — the correct reasoning path, once found, is linear and does not require branching or backtracking. The paper acknowledges this: "it is more suitable to try smaller LLMs + ToT for traditional NLP tasks, or GPT-4 + ToT for hard tasks that challenge GPT-4 + CoT's reasoning."

Cost and efficiency analysis (Appendix B.3, Tables 7-8): ToT requires 5-100× more generated tokens than CoT depending on the configuration. For Game of 24, ToT's $0.74 per case is comparable to CoT best-of-100's$0.47 while achieving substantially higher success (74% vs. 49%), making it cost-effective in a success-per-dollar sense. For Creative Writing, ToT's $0.32 per case is ~4.6× CoT's$0.07 — a larger relative cost multiplier for a smaller absolute performance gain (0.63 points on the 1-10 scale). The paper does not provide a cost-normalized comparison (e.g., how many CoT samples could be purchased for the cost of one ToT run, and what performance would that achieve?), which would be the fairest way to assess whether ToT's overhead is justified by its gains.

Ablations not performed (notable absences):

• Temperature sensitivity: all experiments use temperature 0.7. No ablation varies temperature to test whether ToT's gains depend on stochastic generation or would hold with greedy decoding.
• Prompt sensitivity: the prompts for thought generation and evaluation are presumably hand-tuned, but no ablation tests robustness to prompt variations (e.g., different wording of the proposal prompt, different format for the value prompt).
• Thought granularity: the paper argues that thought size should be "small enough to generate diverse samples, big enough to evaluate," but does not test alternative granularities for the same task (e.g., what if Game of 24 thoughts were pairs of equations instead of single equations? What if Creative Writing plans were sentence-level rather than paragraph-level?).
• Search algorithm alternatives: only BFS and DFS are tested. No comparison to A*, MCTS, or simpler strategies like random sampling with pruning. The paper acknowledges this as future work but the omission means we cannot assess whether the specific algorithms chosen are optimal or merely sufficient to demonstrate the broader point.
• Interaction between beam width and evaluation quality: does ToT with b = 5 and noisy evaluation outperform ToT with b = 1 and perfect evaluation? The oracle and ablation studies on Crosswords hint at this tradeoff but do not systematically explore it.

Critical Assessment

Central Claim 1: "ToT significantly enhances language models' problem-solving abilities" (Abstract, Section 4). This claim is strongly supported for the three tasks tested, with the crucial qualification that the magnitude of enhancement varies dramatically by task. On Game of 24, the improvement is transformative (4% → 74%). On Crosswords, it is substantial (15.6% → 60% word-level). On Creative Writing, it is modest (6.93 → 7.56 automated score, 41% vs. 21% human preference). The claim's generality is limited by the fact that all three tasks were specifically constructed by the authors to be hard for existing methods — the paper itself argues that "deliberate search such as ToT might not be necessary for many existing tasks that GPT-4 already excels at" (Section 6). The GSM8K and StrategyQA results (Appendix B.1) confirm this: gains over CoT are small (4 and 1 percentage points respectively) because CoT already performs well. The claim should therefore be understood as: ToT significantly enhances problem-solving on tasks that require exploration, planning, or backtracking — and the paper has demonstrated this on three tasks it designed to have those properties, but has not established where the boundary lies between "tasks that benefit from search" and "tasks that don't."

Central Claim 2: "ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices" (Abstract). This claim is supported in mechanism but incomplete in demonstration. The paper clearly shows that ToT considers multiple paths (via branching at each step) and self-evaluates choices (via the value/vote prompts). However, the paper does not demonstrate that the self-evaluation is deliberate in a meaningful sense — the LM is prompted to produce an evaluation, and that evaluation guides search, but whether this constitutes genuine "deliberation" (as opposed to, say, the LM producing a superficially plausible evaluation that happens to correlate with correctness) is not established. The ablation showing that pruning helps on average but occasionally prunes correct solutions (Crosswords) suggests that evaluation is imperfect and sometimes non-deliberate (e.g., rejecting "agend" as a typo is a failure of knowledge, not reasoning). The paper uses the psychological language of dual-process theory heavily in its framing, but the experiments do not test whether the LM's evaluation process exhibits properties associated with deliberate (System 2) cognition — effortful, serial, sensitive to justification — as opposed to fast, pattern-based judgments that happen to be elicited by evaluation prompts.

Central Claim 3: "IO, CoT, CoT-SC, and self-refinement can be seen as special cases of ToT" (Section 3, Figure 1). This is a taxonomic claim that is accurate but its significance is overstated. It is true that these methods correspond to trees with specific structural constraints (breadth = 1, depth = 0, etc.), but this is more of a unifying mathematical description than an empirical finding. The more substantive claim — that the additional degrees of freedom ToT introduces (branching, intermediate evaluation, backtracking) are causally responsible for the performance gains — is supported by the ablation studies that remove these components and observe performance drops (particularly the "-backtrack" ablation in Crosswords, where removing backtracking reduces word-level success from 60% to 20%). However, the claim that prior methods "are" special cases could be misinterpreted as implying that prior method developers should have seen their work as constrained tree search, which is a retrospective reframing rather than a discovery.

Central Claim 4: "The integration between thought sampling and value feedback organically integrates planning and decision-making mechanisms" (Section 5). This claim is supported in architecture but its "organic" nature is assumed rather than tested. The integration works as follows: thought generation produces candidates; evaluation scores them; search uses scores to decide what to explore next. This is a standard generate-evaluate-select loop that has been used in AI planning for decades. The paper's innovation is implementing it with LM prompting rather than programmed or learned components. Whether this integration is "organic" (as opposed to "effective but mechanical") is a philosophical claim the experiments do not address.

Genuine weaknesses in the experimental design:

1. Small test sets with no uncertainty quantification. The Crosswords test uses only 20 games, the Game of 24 test uses 100 games, and the Creative Writing test uses 100 inputs. For Game of 24, the 74% vs. 4% gap is large enough that statistical testing is arguably unnecessary — but for the finer-grained comparisons (e.g., ToT vs. ToT-prune on Crosswords: 60% vs. 41.5% word-level on 20 games), the absence of confidence intervals or significance tests makes it impossible to distinguish genuine differences from sampling noise. With 20 Crosswords games, a single additional solved game changes the game-level success rate by 5 percentage points.

2. Single model family (GPT-4). All main experiments use GPT-4. The GPT-3.5 results in Appendix B.2 are suggestive (ToT helps GPT-3.5 too) but incomplete — Creative Writing only reports automated scores, not human evaluation, and Crosswords is not tested with GPT-3.5 at all. We cannot assess whether ToT's benefits generalize across model architectures, scales, or training paradigms. The paper's claim that "this model is representative" (Section 4) is an assertion, not an empirical finding. A particularly important missing experiment: do open-source models (LLaMA, etc.) benefit similarly from ToT, or does the approach depend on GPT-4's specific strengths in instruction-following and self-evaluation?

3. Prompt engineering is black-box and potentially brittle. The specific prompts used for thought generation, value assessment, and voting are critical to ToT's performance, but the paper provides no ablation or sensitivity analysis for prompt variations. The fact that GPT-3.5 required a change from 1-shot to 3-shot proposal prompts for Game of 24 "to make it work" indicates that prompt design choices matter. Without systematic prompt ablation, it is unclear whether ToT's gains reflect the search architecture or the carefully crafted prompts that enable that architecture — and whether the approach would transfer to a new task without similar prompt engineering effort.

4. No comparison to stronger sampling-based baselines at equal cost. The paper compares ToT to CoT-SC with k=100, but does not compute a cost-normalized comparison. ToT at b = 5 costs $0.74 per Game of 24 case (Table 7), while CoT best-of-100 costs$0.47. How many CoT samples could be purchased for $0.74, and what performance would that achieve? An extrapolation of the CoT best-of-k curve (Figure 3a) suggests best-of-100 reaches 49$0.94 might not reach 74%. But this comparison is not made explicit, and for Creative Writing, where ToT's gain is modest (0.63 points on the 1-10 scale) and cost is 4.6× higher, the cost-normalized comparison might be less favorable.

5. The difficulty of the test problems is not calibrated or benchmarked. For Game of 24, the paper uses problems indexed 901-1000, which it describes as "relatively hard games" based on human solving time from 4nums.com. No baseline human performance or existing algorithmic solver performance is reported, so we cannot assess whether 74% is near-ceiling (if the hardest problems are genuinely difficult), moderate (if humans or specialized solvers achieve >95%), or something else. Similarly for Crosswords, the paper states that "more general crosswords can be readily solved with specialized NLP pipelines" and that the goal is "not just to solve the task" — but then reports task performance as the primary metric, without benchmarking against those specialized pipelines to establish an upper bound.

6. The automated evaluation for Creative Writing uses the same model being evaluated. GPT-4 both generates the passages and scores their coherence. The paper partially addresses this with human evaluation (Figure 5b), which confirms the preference direction but does not provide absolute quality scores, making it impossible to calibrate the automated metric. More importantly, the human evaluation only compares ToT vs. CoT — it does not compare ToT vs. IO, or ToT vs. iterative refinement, or any method vs. human-written passages. The claim that ToT produces "more coherent" passages is supported for the ToT-vs-CoT comparison, but the absolute quality of either method's output is unknown.

7. The Crosswords oracle experiment reveals a fundamental evaluator limitation that is not explored. The finding that GPT-4 fails to recognize valid but obscure words ("agend") and therefore prunes solvable states is a specific, diagnosable failure mode of the LM-as-heuristic approach. The paper notes this but does not explore mitigations — would providing a dictionary or allowing web retrieval fix the issue? Would ensembling multiple evaluation prompts reduce false negatives? This is a missed opportunity to characterize the failure modes of LM-based heuristics more systematically.

8. No analysis of failure modes on Creative Writing. For Game of 24, Figure 3b provides a detailed step-by-step error analysis. For Crosswords, the pruning and backtracking ablations provide insight into where search succeeds and fails. For Creative Writing, there is no error analysis at all — we don't know whether ToT's plans are genuinely better than CoT's, whether the voting mechanism selects the best plan, or whether the gains come primarily from the planning step vs. the passage-generation step. This is a significant gap given that Creative Writing is the task where ToT's gains are most modest and most expensive.

Experiments that would have strengthened the paper:

• A systematic difficulty analysis. For Game of 24, breaking down ToT performance by problem difficulty (the 4nums.com difficulty ranking) would reveal whether ToT helps uniformly or primarily on problems of certain difficulty — analogous to the difficulty-bin analysis in the compute-optimal scaling paper. Does ToT mainly help on problems where the base model has a non-trivial chance of generating correct intermediate steps? Does it fail entirely on the hardest problems? This would connect ToT to the broader test-time compute scaling literature.

• A latency and wall-clock time analysis. ToT's tree search involves sequential LM calls (evaluation must complete before the next expansion step), which introduces latency that independent parallel sampling (CoT-SC) avoids. For deployment-relevant metrics, total wall-clock time may matter more than total token cost. The paper provides token counts and dollar costs but no timing measurements.

• A systematic comparison to MCTS-based alternatives. The paper mentions RAP (Hao et al., 2023) as concurrent work using MCTS, but does not implement or compare against MCTS within the ToT framework. Given that MCTS is the dominant search algorithm in modern game-playing AI and has principled exploration-exploitation balancing via UCB, its absence as a baseline is notable.

• Experiments on tasks where ToT should NOT help (to establish boundary conditions). The paper's Appendix B.1 tests GSM8K and StrategyQA and finds small gains, but these are still reasoning tasks. What about tasks that are purely knowledge-dependent (trivia QA), purely stylistic (translation), or purely generative with no correctness criterion? Demonstrating that ToT provides zero or negative benefit on such tasks would sharpen the claim about when deliberate search is valuable versus when it is unnecessary overhead.

Conditional validity of claims:

The paper's central claim — that tree search over semantic units dramatically improves LM problem-solving — holds for the specific tasks, model, and configurations tested, with the magnitude of improvement varying from enormous (Game of 24: 18.5× relative) to modest (Creative Writing: 9% relative automated score improvement). The claim that ToT represents a general framework is supported by the diversity of task configurations (different thought granularities, generation strategies, evaluation strategies, and search algorithms), but the generalization to arbitrary new tasks is not demonstrated — each new task requires human design of all four ToT components, and there is no evidence that this design process is straightforward or robust. The claim that LMs can serve as effective heuristics for their own search processes is supported with the important caveat, demonstrated by the Crosswords pruning failures, that this heuristic is limited by the LM's knowledge and will make systematic errors on rare or out-of-distribution cases. The claim that ToT is cost-effective is supported for Game of 24 (where the performance gain far outstrips the cost increase) but is questionable for Creative Writing (where a 4.6× cost increase buys a 0.63-point improvement that iterative refinement achieves more cheaply).

6. Limitations and Trade-offs

6.1 The Framework's Effectiveness Is Fundamentally Bounded by the Base Model's Capabilities

The assumption or constraint. ToT assumes that the underlying LM possesses the relevant capabilities — generating plausible candidate thoughts, evaluating partial solutions, detecting dead ends — and that these capabilities are merely unorganized by standard left-to-right decoding rather than absent. The paper makes this assumption explicit through its framing: the LM is used as both generator and evaluator without any fine-tuning, meaning the framework can only elicit and organize capabilities that are already latent in the pretrained model. As the authors acknowledge (Section 6):

"this work focuses on using an off-the-shelf LM, and fine-tuning LMs using a ToT-style high-level counterfactual decision making... might present opportunities to enhance the problem-solving capabilities of LMs."

The consequence. This creates a hard capability ceiling: if the base model cannot generate a correct thought at some step, or cannot recognize a valid partial solution when evaluating, no amount of search structure can compensate. The Game of 24 error analysis (Figure 3b) demonstrates this implicitly — even with ToT at b = 5, roughly 25% of samples still fail at step 1, meaning the model cannot produce a valid first equation for a quarter of problems. The Crosswords oracle experiment (Table 3, "+best state") establishes the ceiling more directly: even when an oracle selects the best DFS state explored, only 7 out of 20 games (35%) are solved, and 13 remain unsolved — meaning the search process never generates correct solutions for those 13 games regardless of backtracking, pruning, or evaluation quality. The model simply does not produce correct word guesses that satisfy all constraints, and no amount of search over incorrect guesses will find a correct board.

The GPT-3.5 vs. GPT-4 comparison on Game of 24 (Appendix B.2, Table 5) operationalizes this bound: GPT-3.5 + ToT achieves 19% vs. GPT-4 + ToT's 74%. The gap between models is far larger for ToT (55 percentage points) than for CoT (1 percentage point), because ToT amplifies whatever capabilities the base model possesses — a weak base model's limited generation and evaluation capabilities constrain the search process fundamentally. The cross-model experiment (GPT-4 generation + GPT-3.5 evaluation achieves 64%, while the reverse achieves only 31%) further reveals that generation quality is the primary bottleneck. If the model cannot produce correct intermediate steps, no search algorithm can find them.

What evidence exists in the paper. The error analysis (Figure 3b) shows persisting step-1 failures even with ToT. The Crosswords "+best state" oracle result shows a 35% game-level ceiling. The GPT-3.5 results (Table 5) show dramatic degradation. The paper does not systematically analyze what properties of a problem determine whether the base model's capabilities are sufficient for ToT to help — it only observes the post-hoc outcomes.

Mitigation status. The paper acknowledges the limitation in its discussion (Section 6): "search methods like ToT requires more resources... in order to improve task performances," and suggests fine-tuning as a future direction. No mitigation is attempted within the paper — the framework is purely an inference-time architecture with a frozen model. The limitation is fundamental to the approach: it is a capability amplifier, not a capability creator, and cannot help on problems where the base model's pass@1 on the correct intermediate steps is near zero.

6.2 Each New Task Requires Substantial Human Design of All Four ToT Components

The assumption or constraint. The paper presents ToT as a general framework, but each instantiation requires a human experimenter to answer four design questions: what constitutes a thought, how to generate candidate thoughts, how to evaluate states, and what search algorithm to use (Section 3, enumerated list). The answers to these questions are task-specific and non-trivial. The thought decomposition must respect a Goldilocks constraint (small enough to generate diverse samples, big enough to evaluate meaningfully). The generation strategy (i.i.d. vs. sequential proposal) depends on whether the thought space is rich or constrained — a property that must be judged by the human designer. The evaluation prompt must encode domain-appropriate criteria: lookahead simulation for arithmetic, commonsense pruning for constraint satisfaction, comparative voting for open-ended coherence. The search algorithm choice (BFS vs. DFS) depends on tree depth and dependency structure.

The paper does not provide a systematic methodology for making these choices — it demonstrates them by example on three tasks that the authors themselves constructed. Section 4 describes the ToT Setup for each task as a bespoke configuration: Game of 24 uses 3-step BFS with b = 5, sure/maybe/impossible evaluation with 3 samples, and sequential proposal; Creative Writing uses 2-step BFS with b = 1, 5-sample voting, and i.i.d. sampling; Crosswords uses variable-depth DFS with per-clue possibility evaluation, confidence-sorted proposal, and backtracking on impossibility. Each configuration reflects the authors' understanding of the task structure, not an automated or principled selection procedure.

The consequence. The practical barrier to applying ToT to a new task is high: a practitioner must (a) understand the task's structure well enough to decompose it into thought steps at the right granularity, (b) design effective generation and evaluation prompts — which the paper shows require task-specific content (e.g., arithmetic lookahead for Game of 24, letter-constraint reasoning for Crosswords, coherence assessment for Creative Writing), (c) select and tune a search algorithm with appropriate parameters (beam width, depth limit, evaluation threshold), and (d) validate that the design choices work, potentially through expensive trial-and-error. The paper provides no guidance on how much prompt engineering effort was required to achieve the reported results — the Appendix B.2 note that GPT-3.5 required changing the Game of 24 proposal prompt from 1-shot to 3-shot "to make it work" hints at non-trivial prompt sensitivity, but this is not explored systematically.

Furthermore, there is no evidence that the design choices made for these three tasks would transfer to other tasks in the same domain (e.g., would the Game of 24 configuration work for other arithmetic puzzles? Would the Creative Writing configuration work for other open-ended generation tasks?). The framework's generality is architectural — the four-component decomposition is general — but the instantiation of each component is task-specific in ways that may require significant expertise and iteration.

What evidence exists in the paper. The three task-specific ToT setups (Sections 4.1, 4.2, 4.3) implicitly demonstrate the design burden: each task required different choices on all four dimensions. The Appendix B.1 extension to GSM8K and StrategyQA uses a simplified zero-shot ToT-BFS configuration that is substantially less tailored, and achieves only modest gains (4 and 1 percentage points over CoT, respectively). This suggests that the large gains on Game of 24 and Crosswords depend on the specific, carefully-designed task configurations, and that a generic ToT instantiation without task-specific tuning provides limited benefit. The GPT-3.5 prompt modification (changing from 1-shot to 3-shot) is mentioned but not analyzed as a systematic sensitivity.

Mitigation status. The paper does not address this as a limitation or propose methods for automating the design choices. The modularity of the framework is presented as a strength (Section 3: "Modularity. The base LM, as well as the thought decomposition, generation, evaluation, and search procedures can all be varied independently."), but the complement of modularity — that you must vary and configure all components — is not discussed as a cost. Future work on automating thought decomposition, learning evaluation prompts, or adaptively selecting search strategies would address this gap, but the paper does not pursue these directions.

6.3 The Cost of Search Is Not Amortized or Normalized Against Simpler Baselines

The assumption or constraint. The paper reports ToT's performance gains without always providing a cost-normalized comparison against the strongest sampling-based baselines at equivalent compute budgets. Table 7 (Appendix B.3) provides cost data for Game of 24: ToT costs $0.74 per case (5.5k completion tokens) vs. CoT best-of-100 costing$0.47 (6.7k tokens). The paper notes that ToT outperforms CoT best-of-100 (74% vs. 49%) while costing only 1.6× more, which is a favorable cost-effectiveness ratio. However, for Creative Writing (Table 8), ToT costs $0.32 per case (4k completion tokens + 2.9k prompt tokens) vs. CoT's$0.07 (0.9k + 0.4k tokens) — a ~4.6× cost multiplier. The performance gain is 7.56 vs. 6.93 on the automated 1-10 scale (a 9% relative improvement), and human evaluation shows a 41% vs. 21% preference (with 38% judged similar). The paper does not compute whether the same $0.32 budget spent on additional CoT samples (roughly 4.6× more, or about 46 samples per case instead of the baseline's single sample) would close or exceed the gap.

For Crosswords, no cost data is reported at all (Appendix B.3 only estimates "should be also within 100 dollars" in total). The DFS algorithm's cost is variable depending on how many nodes are expanded before finding a solution or hitting the 100-step limit, making cost-per-task comparisons more complex, but the omission means we cannot assess whether the 60% word-level success represents good value relative to, say, running many more independent CoT samples (which at 15.6% success might achieve comparable or better performance at equivalent cost through ensembling, majority voting, or best-of-N selection).

The consequence. The headline performance numbers (74% vs. 4%, 60% vs. 15.6%) compare ToT against single CoT samples, not against CoT with an equivalent compute budget. This is a standard practice in methods papers, but it inflates the apparent advantage because ToT inherently uses more compute. The fair comparison — what accuracy does CoT achieve when given the same dollar or token budget as ToT? — is partially answered for Game of 24 (CoT best-of-100 at $0.47 achieves 49$0.74, so ToT wins even when CoT is given comparable resources), but is not answered for Creative Writing or Crosswords.

For Creative Writing specifically, the iterative refinement baseline (IO + refine) achieves a coherency score of 7.67 — higher than ToT's 7.56 — and ToT + refine achieves 7.91. The cost of refinement is not reported, so we cannot assess whether the 7.67 score is cheaper or more expensive than ToT's 7.56. A practitioner choosing between ToT and iterative refinement for Creative Writing has no cost data to inform the decision. More broadly, the paper's claim that ToT enables "deliberate decision making" must be weighed against whether the same deliberation budget spent on simpler methods (more samples, refinement iterations, or best-of-N selection with a verifier) would achieve comparable results at lower implementation complexity.

What evidence exists in the paper. Appendix B.3 (Tables 7-8) provides token counts and dollar costs for Game of 24 and Creative Writing, but these are presented as informational rather than as the basis for a systematic cost-normalized comparison. Figure 3a plots ToT success rate against "nodes visited" and overlays IO/CoT "best of k" curves where k is treated as nodes visited in a bandit analogy, which is a form of compute-normalized comparison — but the mapping between ToT nodes and CoT samples is not exactly equivalent (a ToT node involves generation + evaluation, which is more expensive per node than a single CoT sample), and this comparison is only provided for Game of 24. No equivalent analysis exists for Creative Writing or Crosswords.

Mitigation status. The paper partially addresses cost concerns in Appendix B.3, acknowledging that "ToT requires 5-100× more generated tokens than CoT" and providing actionable suggestions for performance-cost tradeoffs (changing beam size, vote number, or using cheaper models for evaluation). However, it does not compute cost-normalized baselines for Creative Writing or Crosswords, and does not discuss the fact that the 5-100× token multiplier may be prohibitive for latency-sensitive or high-throughput applications regardless of accuracy gains. The suggestion to use GPT-3.5 for evaluation (Section B.2: GPT-4 generation + GPT-3.5 evaluation achieves 64% on Game of 24) is a partial mitigation that reduces cost, but this cross-model configuration is not explored for the other tasks or analyzed for cost-effectiveness.

6.4 the LM-Based State Evaluator Produces Systematic Errors That the Search Algorithm Cannot Fully Compensate For

The assumption or constraint. ToT relies on the LM to evaluate the promise of partial solutions through prompted reasoning — for Game of 24, classifying each intermediate state as sure/maybe/impossible; for Crosswords, judging whether each remaining clue can be filled given current letter constraints; for Creative Writing, voting for the best plan or passage. The paper explicitly acknowledges that these evaluations "do not need to be perfect, and only need to be approximately helpful for decision making" (Section 3, item 3a). The underlying assumption is that the search algorithm's beam width or backtracking can tolerate evaluation noise — if the evaluator incorrectly prunes 20% of good states, keeping b = 5 candidates alive ensures that some good states survive; if it fails to prune 20% of bad states, DFS will eventually hit a dead end and backtrack.

The consequence. Two distinct failure modes emerge, both demonstrated in the paper:

False negatives (incorrectly pruning good states). The Crosswords pruning ablation (Table 3) reveals that the full ToT with pruning solves 4 games, while ToT without pruning ("-prune") finds correct solutions for 4 games — but 3 of these are different games that full ToT misses because the evaluator incorrectly prunes them. The paper attributes this to the LM's limited vocabulary: "5×5 crosswords by design have some rare or obsolete words that GPT-4 cannot recognize" (Section 4.3, footnote). The evaluator judges a state as "impossible" when it actually is solvable because the LM doesn't know that a particular obscure word is valid. This means the evaluator's quality is bottlenecked by the LM's knowledge coverage — and on tasks involving rare or domain-specific knowledge, the evaluator may be systematically unreliable in ways that search cannot recover from, because once a state is pruned, it is permanently removed from consideration (in BFS or with pruning thresholds in DFS).

False positives (failing to prune bad states). The Game of 24 error analysis (Figure 3b) shows that even with ToT and evaluation, roughly 26% of samples still fail by step 3. Some of these failures represent states that the evaluator should have pruned but did not — partial solutions that were judged "maybe" or even "sure" but actually lead to dead ends. These states consume search budget (beam slots, DFS steps) that could have been spent exploring genuinely promising alternatives.

The fundamental tension is that the evaluator must be conservative enough to avoid false negatives (don't prune something that might work) but aggressive enough to provide meaningful pruning (don't waste compute on dead ends). The paper does not explore this tradeoff systematically — the evaluation thresholds (sure/maybe/impossible classification for Game of 24, the binary possible/impossible judgment for Crosswords) are fixed and not tuned. The finding that the unpruned DFS finds solutions that pruning misses, but overall performs worse (41.5% vs. 60% word-level), indicates that the current pruning threshold is net beneficial but far from optimal — a more knowledgeable evaluator, or an adaptive threshold, could potentially recover the missed solutions without sacrificing the pruning benefits.

What evidence exists in the paper. The Crosswords ablation study (Table 3, comparing ToT vs. ToT-prune) provides the clearest evidence of systematic evaluation errors. The Game of 24 error analysis (Figure 3b, showing persisting failures at all steps even with evaluation) provides indirect evidence of false positives. The paper does not systematically categorize evaluator errors (false positive vs. false negative rates), does not analyze how evaluator accuracy varies by problem difficulty or step depth, and does not explore whether evaluation errors are random or systematic (e.g., does the evaluator consistently fail on certain types of partial solutions?).

Mitigation status. The paper acknowledges the limitation in the Crosswords analysis: "better heuristics for DFS pruning are critical for problem solving in this case" (Section 4.3). It suggests external retrieval or web interaction as a possible remedy for knowledge gaps ("External retrieval or web interaction could augment LM for problem solving under knowledge uncertainty," Section 4.3 footnote), but does not implement this. The suggestion to use multiple evaluation samples and aggregate them (3 samples for Game of 24, 5 votes for Creative Writing) is a form of mitigation through ensembling, but it addresses random noise rather than systematic errors — if all 3 samples share the same knowledge gap (not knowing that "agend" is a valid word), aggregation doesn't help. The paper does not explore more sophisticated mitigations such as confidence calibration, adaptive pruning thresholds, or combining the LM evaluator with external knowledge sources.

6.5 Generalization Claims Rest on Three Custom-Designed Tasks with Small Test Sets and a Single Model Family

The assumption or constraint. All main experimental results use GPT-4 on three tasks that were specifically constructed by the authors to be challenging for existing methods (Section 4: "We propose three tasks that are hard even when sampling from the state-of-the-art language model, GPT-4"). The test sets are small: 100 games for Game of 24, 100 inputs for Creative Writing, and only 20 games for Mini Crosswords (Section 4.1-4.3). The paper's claims about ToT's effectiveness are therefore based on performance on a total of 220 test instances across three tasks, all evaluated with a single model (GPT-4), on problems that were deliberately selected or constructed to be difficult for the baselines.

The Crosswords test set is particularly concerning: 20 games total, with 5 held-out games used for few-shot prompting and the remaining 156 (minus 20 test, minus 5 prompt) unused — the selection criterion for the test games (indices 1, 6, ..., 91, 96) is described but not justified, and the small sample size means that a single additional solved or unsolved game changes the game-level success rate by 5 percentage points. The comparison between full ToT (4/20 games solved) and ToT-prune (5/20 games solved, if we interpret "actually find the correct solution for 4/20 games" as games solved by the search process even if not output) could easily be noise rather than a genuine difference.

The GPT-3.5 results in Appendix B.2 provide the only cross-model evidence: Game of 24 (19% for GPT-3.5 + ToT vs. 74% for GPT-4 + ToT) and Creative Writing (automated score 6.62 vs. 7.56). Crosswords is not tested with GPT-3.5. No other model families (Claude, LLaMA, PaLM, etc.) are evaluated. The paper's claim in Section 4 that the model is "representative" is asserted without evidence — we do not know whether ToT's effectiveness depends on GPT-4's specific instruction-following capabilities, its scale, its training data, or its RLHF fine-tuning, all of which could affect both generation quality and self-evaluation reliability (which the paper shows is the primary bottleneck).

The consequence. A practitioner considering ToT for a different task, domain, or model cannot estimate, from the evidence provided, whether the framework will provide large gains (as in Game of 24), modest gains (as in Creative Writing), or negligible gains (as in GSM8K/StrategyQA). The three tasks span mathematical reasoning, creative generation, and constraint satisfaction — a reasonable diversity — but they are all tasks where (a) the authors had the opportunity to iteratively design and tune the ToT configuration, (b) the task structure is well-understood and amenable to decomposition into thought steps, and (c) evaluation criteria are relatively clear (arithmetic correctness, coherence, letter-grid consistency). Tasks where thought decomposition is less obvious (e.g., multi-step moral reasoning, strategic negotiation, long-horizon planning with vague goals) may not benefit, or may require substantially more design effort than the paper suggests.

The small test sets mean that the reported performance numbers have unknown variance. For Game of 24 (100 games), the 74% success rate has a binomial standard error of approximately 4.4 percentage points — a 95% confidence interval of roughly 65-83%, which still clearly separates from CoT's 4%. For Crosswords (20 games), the game-level success rate of 20% has a standard error of approximately 8.9 percentage points — a 95% confidence interval of roughly 2-38%, which overlaps substantially with the "-prune" variant's 25% and even with CoT's 5% (1 game). The word-level success rate (60%, or 120 out of 200 words) has smaller relative variance but still no reported confidence interval. Without uncertainty quantification, the finer-grained comparisons (ToT vs. ToT-prune, ToT vs. ToT-backtrack) are suggestive rather than conclusive.

What evidence exists in the paper. The test set sizes are stated explicitly in Sections 4.1-4.3. The GPT-3.5 results are in Appendix B.2 (Tables 5-6). The GSM8K/StrategyQA results are in Appendix B.1 (Table 4), showing small gains. The paper does not report confidence intervals, standard errors, or statistical significance tests for any result. The human evaluation for Creative Writing (Figure 5b) provides some statistical rigor (100 pairs, binomial test implicit in the 41 vs. 21 preference), but no formal test is reported.

Mitigation status. The paper does not address the small test set or single-model limitation as a concern. The discussion (Section 6) acknowledges that "as an initial step this work only explores three relatively simple tasks that challenges GPT-4" and suggests that "as we begin to deploy LMs for more real-world decision making applications... more complex tasks could emerge." This is forward-looking but does not mitigate the current evidence gap. No power analysis, sample size justification, or uncertainty quantification is provided. The fact that the tasks were custom-designed by the authors raises an implicit concern about positive-result bias (tasks where ToT didn't work would not appear in the paper), though this is inherent to methods papers that introduce new tasks. A systematic benchmark on existing diverse reasoning datasets with preregistered ToT configurations would address this limitation, but the paper does not conduct such an evaluation.

6.6 Latency and Serial Dependencies Make ToT Impractical for Interactive or Real-Time Applications

The assumption or constraint. ToT's search algorithms introduce sequential dependencies that are absent from parallel sampling methods like CoT-SC. In BFS (Algorithm 1), each depth step requires: (a) generating k candidate thoughts from each of b states (these can be parallelized across states but not across depths), (b) evaluating all b × k resulting states (fully parallelizable), and (c) pruning to the top b. Step (a) cannot begin for depth t+1 until step (c) completes for depth t, because the generation at depth t+1 depends on which states survive pruning at depth t. This creates a hard serial bottleneck: the total wall-clock time is proportional to the tree depth T times the per-step generation latency, regardless of how much parallel compute is available.

In DFS (Algorithm 2), the dependency is even stricter: the algorithm explores one path deeply, and the decision of which candidate to explore next at a given node depends on the outcome of the entire subtree explored for the previous candidate. This means DFS is essentially serial — you cannot parallelize across branches because you don't know which branch to explore next until the current one completes or is pruned.

In contrast, CoT-SC with k samples is embarrassingly parallel: all k chains can be generated simultaneously, and the only serial step is the final majority voting, which is cheap. CoT-SC wall-clock time is roughly one CoT generation latency (plus voting), regardless of k, assuming sufficient parallel compute. ToT wall-clock time is T × (generation latency + evaluation latency) in the best case for BFS, and potentially much longer for DFS depending on the number of backtracks.

The consequence. In latency-sensitive applications — interactive assistants, real-time decision-making, any setting where a user is waiting for a response — ToT may be prohibitively slow even when its total FLOP or dollar cost is acceptable. A user waiting 5 seconds for a CoT response might wait 15-30 seconds for a ToT response (3 depth steps × 5-10 seconds per generation + evaluation cycle), which may be unacceptable regardless of accuracy gains. The paper provides token counts and dollar costs (Appendix B.3) but no latency measurements, making it impossible for a practitioner to assess the wall-clock time implications.

The latency issue is compounded by the fact that each LM API call in the search loop has variable latency (depending on API load, output length, etc.), and the search cannot proceed until the slowest call in each batch completes. If one of the k = 5 generations at a given step takes unusually long (a tail-latency event), the entire search pipeline stalls. This variability is not captured by average token counts.

For Creative Writing specifically, where the gain over CoT is modest (0.63 points on the 1-10 scale, or a 41% vs. 21% human preference with 38% ties), the latency cost may be particularly hard to justify — a 4.6× cost multiplier combined with a ~2× latency multiplier (2 depth steps) for a relatively small quality improvement.

What evidence exists in the paper. The paper provides cost data in tokens and dollars (Appendix B.3, Tables 7-8) but no wall-clock time measurements. The BFS and DFS algorithms (Algorithms 1-2) make the serial dependencies explicit in pseudocode. The paper does not discuss latency as a consideration or tradeoff.

Mitigation status. Not addressed. The paper's suggestions for reducing cost (smaller beam width, fewer votes, cheaper evaluation models) would also reduce latency somewhat, but the fundamental serial dependency of tree search remains. Potential mitigations not explored in the paper include: (a) speculative execution (generate candidates for the next depth speculatively before pruning completes), (b) asynchronous search algorithms that don't block on the slowest evaluation, (c) early stopping when a sufficiently good solution is found rather than completing the full depth, (d) using smaller/faster models for evaluation while reserving the large model for generation (the GPT-4 generation + GPT-3.5 evaluation result in Appendix B.2 is a step in this direction but is not analyzed for latency). The paper's framing of ToT as a framework for "deliberate" (System 2) reasoning implicitly accepts that deliberation takes time, but does not help practitioners decide when the additional latency is worth the accuracy gain.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper instigates a paradigm shift in how the field conceptualizes language model inference — from generation to search. Prior to ToT, the dominant mental model for LM problem-solving was sampling from a distribution: you prompt the model, it produces text (possibly with intermediate reasoning steps), and the quality of the output depends on how much probability mass the model assigns to correct reasoning paths. Under this view, improving performance means either making the model better (scaling, training) or drawing more aggressively from the existing distribution (best-of-N, majority voting, temperature tuning). The intellectual toolkit was fundamentally statistical.

ToT reframes the activity as heuristic search through a combinatorial space of reasoning paths, where the LM serves dual roles as a proposal engine and an evaluation function. This is a category shift with far-reaching consequences. It means the experimenter can now independently design (a) the granularity of decision steps, (b) how alternatives are proposed, (c) how partial solutions are evaluated, and (d) the exploration strategy — four separate axes of innovation that are invisible in the generation-from-distribution paradigm. The paper demonstrates this by configuring all four axes differently for Game of 24, Creative Writing, and Crosswords, showing that the same frozen GPT-4 model can exhibit dramatically different capabilities when embedded in different search architectures.

The magnitude of the shift is clearest in the Game of 24 results (Table 2): the same model that achieves 4% with CoT prompting achieves 74% with ToT — an 18.5× relative improvement that does not come from any change to the model itself. This is not an incremental accuracy bump from a clever prompt; it is a qualitative transformation in what the system can do, enabled purely by inference-time architecture. The fact that ToT (74%) far exceeds even the oracle best-of-100 CoT (49%) — meaning CoT cannot find the correct solution in 100 independent attempts, while ToT finds it through structured exploration — proves that search is not merely selecting better among already-generated solutions; it is generating solutions that random sampling would rarely or never produce.

The paper's reframing also resolves a latent tension in the LM reasoning literature. Prior to ToT, the field had two competing narratives: on one hand, chain-of-thought prompting (Wei et al., 2022) and self-consistency (Wang et al., 2022) showed that LMs can reason through multi-step problems; on the other hand, these methods catastrophically failed on certain tasks for reasons that were poorly understood. The Game of 24 results make the failure mode starkly visible through the error analysis in Figure 3b: ~60% of CoT samples fail at the very first step — the model commits to a bad first intermediate equation and never recovers. ToT's diagnosis — that left-to-right decoding forces premature commitment without any mechanism for reconsideration — provides a precise structural explanation for when and why CoT fails, and a structural remedy (branching + evaluation at intermediate steps) that directly addresses the failure. This shifts the conversation from "do LMs reason well?" (an ill-posed question) to "under what inference architecture do LMs reason well?" — a question with clear engineering consequences.

The paper also reorients research priorities around the relationship between model capabilities and inference architecture. The finding that ToT amplifies GPT-4's Game of 24 performance from 4% to 74% but only amplifies GPT-3.5's from 3% to 19% (Appendix B.2, Table 5) reveals that the gains from search structure are multiplicative with base model quality — a stronger base model benefits disproportionately from deliberate search. This suggests a complementary relationship between scaling and search: rather than being substitutes (you can either scale the model or search at inference time), they may be synergistic, with each increment of model capability unlocking larger gains from inference-time architecture. Practically, this means that as base models continue to improve, the return on investment in inference-time search architectures will likely increase, not decrease — the opposite of what one would predict if search were merely compensating for model weakness.

The broader intellectual contribution is reconnecting modern LMs to the classical AI tradition of heuristic search (Newell, Shaw, and Simon, 1959) that had been largely absent from the deep learning era. This is not nostalgia — it is the recognition that a dimension of intelligence (deliberate, combinatorial exploration with backtracking and evaluation) that was central to classical AI is not provided by scaling alone, and that integrating it with modern LMs can unlock capabilities that neither approach achieves independently. The paper's explicit dual-process framing (System 1 as associative generation, System 2 as deliberate search) provides a conceptual vocabulary for thinking about this integration, and the modular ToT architecture provides a practical template for implementing it. This makes several research directions newly attractive that were previously difficult to motivate:

• Inference-time architecture design becomes a first-class research area alongside model training, with its own design dimensions (thought granularity, evaluation strategies, search algorithms) and scaling properties.
• LM self-evaluation — the ability of models to judge their own partial outputs — becomes a critical capability to study and improve, since it is the bottleneck for search efficiency (as demonstrated by the Crosswords pruning failures).
• Training models specifically for tree-structured reasoning becomes a natural next step: if frozen models benefit this much from search structure at inference time, models explicitly trained to generate and evaluate thoughts within a search process might benefit even more.

Conversely, the paper makes certain research directions less attractive. The results suggest that further incremental improvements to single-path prompting (better CoT prompts, more few-shot examples, different persona instructions) are unlikely to close the gap on tasks requiring exploration or backtracking — the limitation is structural, not prompt-engineering-related. Similarly, pure scaling of model size without corresponding improvements in inference architecture may yield diminishing returns on tasks where the bottleneck is search rather than knowledge or local reasoning capability.

Follow-Up Research This Work Enables

Training LMs explicitly for tree-structured reasoning through fine-tuning on search trajectories. The paper uses a frozen GPT-4 model, but the search process itself generates rich training data: which partial solutions were evaluated as promising vs. impossible? Which branches led to success vs. dead ends? Which backtracks were necessary? A natural extension is to fine-tune a model on the trajectories produced by ToT search — teaching it not just to generate individual thoughts, but to internalize the process of generating alternatives, evaluating them, and backtracking when necessary. The finding that ToT + refine improves Creative Writing scores (7.56 → 7.91, Section 4.2) suggests that the model can benefit from iterative improvement; explicit training on search trajectories might bake this capability into the model weights, reducing the need for expensive inference-time search. A concrete experiment: fine-tune GPT-3.5 on successful ToT trajectories from Game of 24 (where GPT-4 + ToT achieves 74%), then evaluate whether the fine-tuned GPT-3.5 can achieve substantially higher than its current 19% ToT performance, potentially approaching GPT-4 levels through learned search strategies rather than raw capability.

Systematic characterization of LM evaluator failure modes and mitigation strategies. The Crosswords experiment reveals a specific, diagnostic failure: the evaluator prunes solvable states because it doesn't recognize obscure words like "agend" (Section 4.3). This is a knowledge-limitation failure, not a reasoning failure. But what other failure modes exist? Does the evaluator exhibit systematic biases — overconfidence on certain problem types, underconfidence on others, sensitivity to irrelevant features of the partial solution? A systematic study would: (a) categorize evaluator errors (false positive vs. false negative) across multiple tasks and difficulty levels, (b) measure whether errors are random or systematic (does the evaluator consistently fail on partial solutions with certain properties?), and (c) test mitigation strategies: retrieval augmentation (giving the evaluator access to a dictionary or knowledge base), calibration techniques (prompting the evaluator to express uncertainty rather than binary judgments), and ensemble methods (aggregating evaluations from multiple independently prompted calls, potentially with different wording). The finding that GPT-4 generation + GPT-3.5 evaluation achieves 64% on Game of 24 (vs. 31% for the reverse) already demonstrates that generation quality matters more than evaluation quality; understanding when and why the evaluator fails would enable cost-optimized deployments (cheap evaluator, expensive generator).

Adaptive search strategies that dynamically adjust beam width, evaluation depth, and algorithm choice based on problem difficulty. The paper uses fixed search parameters per task (b = 5 for Game of 24 BFS, 100-step limit for Crosswords DFS) with no adaptation to individual problem instances. Yet the error analysis (Figure 3b) shows that problem difficulty varies enormously — some Game of 24 problems are solved at b = 1 while others require b = 5. A compute-optimal strategy would estimate problem difficulty after a small initial computation budget and allocate remaining budget accordingly — easy problems get shallow search with narrow beams, hard problems get deeper or wider search. This connects directly to the compute-optimal test-time scaling framework (Snell et al., 2024), which showed that optimal allocation depends on prompt difficulty. A concrete experiment: on Game of 24, use the first few generated candidate thoughts to estimate whether the problem is easy (multiple strong candidates with high evaluator confidence) or hard (few candidates, low confidence), then dynamically set b and the number of evaluation samples per problem. Compare the cost-performance Pareto frontier against fixed-parameter ToT.

Integration of ToT with process reward models (PRMs) for more sample-efficient evaluation. The paper uses prompted LM self-evaluation as a heuristic, which is flexible but expensive (each evaluation requires a full LM call) and noisy (the Crosswords pruning failures). Process reward models — trained to predict the correctness of intermediate steps from Monte Carlo rollouts, as in Lightman et al. (2023) and the compute-optimal scaling paper — could replace or augment prompted evaluation with faster, potentially more calibrated scoring. The key question: does a trained PRM make different (fewer) errors than prompted self-evaluation on the same tasks? The Crosswords finding that the prompted evaluator fails on obscure vocabulary suggests that a PRM trained on domain-specific data might capture rare words better, reducing false-negative pruning. Conversely, a PRM might overfit to the base model's output distribution and fail to generalize to the diverse candidate thoughts generated during search. A concrete experiment: train a PRM on Game of 24 solution steps using the Monte Carlo rollout procedure, then compare ToT with PRM-based evaluation against ToT with prompted evaluation, measuring both success rate and computational cost (PRM calls are cheaper than full LM evaluations).

Stress-testing ToT on tasks where the thought structure is ambiguous or the evaluation criteria are subjective. The paper's three tasks have relatively clear thought decompositions: arithmetic equations, writing plans, word guesses. But many real-world reasoning problems lack this clean structure. What happens when ToT is applied to tasks where the "right" thought granularity is unclear — multi-step moral reasoning, strategic negotiation, long-horizon planning with vague goals? Does performance degrade gracefully as the thought decomposition becomes less natural, or does it collapse entirely? The Creative Writing results hint at the challenge: even with a relatively clean decomposition (plan then write), the gain over CoT is modest (0.63 points on a 1-10 scale) and is matched by iterative refinement. A systematic study would test ToT on a diverse set of reasoning tasks with varying degrees of structural clarity, measuring both absolute performance and the sensitivity to thought granularity choices. Negative results — tasks where ToT provides zero or negative benefit despite reasonable design effort — would be as informative as positive ones, establishing the boundary conditions for when tree search over semantic units is helpful versus when it adds overhead without benefit.

Combining ToT's search architecture with explicit verifiers or external tools for the Crosswords knowledge bottleneck. The Crosswords pruning failures are explicitly attributed to the LM's limited vocabulary — a correct but obscure word like "agend" is judged impossible because GPT-4 doesn't recognize it. This is a solvable problem: give the LM access to a dictionary or word-completion tool during evaluation. A concrete experiment: augment the Crosswords state evaluator with a simple word-completion function — given letter constraints like "tm_s_", query a dictionary for all matching words and return the count. If the count is zero, prune; if non-zero, allow exploration. This would eliminate the false-negative pruning caused by vocabulary gaps while retaining the LM's ability to reason about more complex constraints (e.g., semantic consistency between intersecting words). The question: does tool-augmented evaluation close the gap between full ToT (60% word-level) and the unpruned oracle (which finds solutions for 7 games, 3 of which pruning missed), and does it do so without the computational cost of unpruned search?

Practical Applications and Downstream Use Cases

Automated math tutoring and problem generation. Game of 24 is a specific instance of a broader class of mathematical reasoning problems where students need to explore multiple solution strategies and learn to recognize dead ends. ToT's architecture — generating candidate next steps, evaluating which are promising, and backtracking when necessary — mirrors the problem-solving process that effective math tutors model for students. A tutoring system built on ToT could not only solve problems but also explain its search process to students, showing why certain approaches work and others don't, because the tree of thoughts is an explicit, interpretable record of the reasoning process. The 74% success rate on Game of 24 (Table 2) compared to 4% for standard approaches means the system can reliably generate correct solutions and their derivation paths for a large fraction of problems — sufficient for a tutoring application where incorrect solutions can be filtered out. Moreover, the system could explicitly surface alternative solution paths from the tree (different branches that both reach the correct answer), which is pedagogically valuable for showing students that there are multiple valid approaches.

Interactive creative writing assistants with explicit planning support. The Creative Writing results demonstrate that ToT can improve passage coherence by first generating and selecting among multiple plans before committing to prose (Section 4.2, Figure 4, Figure 5). This maps directly onto the workflow of human writers who outline before drafting. A writing assistant built on ToT could: (a) generate multiple high-level outlines for a given set of constraints (ending sentences, themes, characters), (b) present the outlines to the user for selection or hybrid combination — making the planning process collaborative rather than automated — and (c) generate multiple prose realizations of the selected plan, again allowing user selection and iterative refinement. The human evaluation results (41% preference for ToT over CoT, Figure 5b) provide evidence that the structured planning approach produces noticeably more coherent output even when the final selection is automated; human-in-the-loop selection would likely amplify this advantage. The modularity of ToT means the system could also support partial automation: the user provides the plan and the model generates prose, or vice versa.

Constrained puzzle generation and solving as an LM capability benchmark. The Mini Crosswords task (Section 4.3) demonstrates that LMs can engage in constrained combinatorial search over natural language — a capability that generalizes well beyond crosswords to any task requiring simultaneous satisfaction of intersecting constraints (scheduling with natural-language preferences, multi-step procedural planning, interactive fiction where player choices constrain narrative possibilities). A practical application is automated generation of new puzzles (not just solving existing ones): the same DFS with backtracking architecture can be run in reverse, starting from a desired solution and working backward to generate clues that uniquely determine it. More broadly, the three tasks in this paper — mathematical search, constrained generation, and constraint satisfaction — establish a useful benchmark suite for evaluating inference-time reasoning architectures. The fact that GPT-4 performance varies from 74% (Game of 24) to 20% (Crosswords games solved) on these tasks means they provide meaningful signal for comparing search strategies, evaluation methods, and model capabilities in a way that saturated benchmarks (where GPT-4 already achieves >90%) cannot.

Self-improving systems that generate their own training data through search. The paper demonstrates that ToT can find correct solutions to problems that random sampling cannot (e.g., Game of 24 solutions that don't appear in 100 independent CoT samples). This makes ToT a powerful data generation engine for self-improvement loops: use ToT to solve many instances of a task, then fine-tune the base model on the successful search trajectories — essentially distilling the search process into the model weights. This is particularly relevant for the "easy-to-medium difficulty" problems identified in the compute-optimal scaling paper (Snell et al., 2024) where test-time compute is most effective. ToT's explicit tree structure provides richer training data than simple input-output pairs or linear chains — the model can learn not just what the correct answer is, but how to explore the solution space, including which dead ends to avoid (negative examples from pruned branches) and how to evaluate partial progress. The practical benefit is that after fine-tuning, the model may require less search at inference time — it has internalized the search strategy, reducing the cost of deployment while retaining the accuracy gains.

When to Prefer This Method

The paper explicitly positions ToT as a framework most valuable when tasks require exploration, planning, or backtracking — and provides evidence that it adds limited value on tasks where single-path reasoning already suffices (GSM8K: +4 percentage points over CoT; StrategyQA: +1 point; Appendix B.1). The decision rule emerging from the results is:

• Prefer ToT when the task has a combinatorial solution space where early decisions constrain later options (Game of 24, Crosswords) — the 18.5× improvement on Game of 24 and 3.8× improvement on Crosswords word-level success make the case decisively. The key indicator is whether CoT samples fail early and irrecoverably: if a significant fraction of failures occur at the first reasoning step (as in Figure 3b's ~60% step-1 failure rate for CoT on Game of 24), branching and evaluation at that step is essential.

• Prefer CoT or iterative refinement when the task requires linear reasoning or local improvement rather than global search (GSM8K, StrategyQA, Creative Writing refinement). On Creative Writing, iterative refinement (IO + refine: 7.67, ToT + refine: 7.91) matches or exceeds ToT alone (7.56) while being architecturally simpler. The key indicator is whether the reasoning path, once found, is a single chain: for math word problems (GSM8K) where step-by-step deduction from premises to conclusion is sufficient, CoT already achieves 86% and ToT adds only 4 points at substantially higher cost.

• Prefer ToT with DFS and backtracking over ToT with BFS when decisions have long-range dependencies that may only reveal themselves as incorrect several steps later (Crosswords). BFS works well for shallow trees where evaluation at each step reliably predicts downstream success (Game of 24, depth 3). DFS is necessary when a choice at step 3 may create an impossible constraint at step 7 — the "-backtrack" ablation (Table 3) shows that greedy forward search without backtracking collapses from 60% to 20% word-level success, proving that the ability to unwind commitments is not merely helpful but essential for constraint satisfaction problems.

• Consider the cost-latency-accuracy tradeoff explicitly rather than defaulting to the highest-performing configuration. ToT costs 4.6× more than CoT on Creative Writing ($0.32 vs.$0.07 per case, Appendix B.3) for a 0.63-point coherence improvement; iterative refinement achieves a larger improvement (6.19 → 7.67, +1.48 points) with unreported but likely lower cost. On Game of 24, ToT's cost premium is justified (74% vs. 49% for comparably-priced CoT best-of-100), but the cost-benefit calculus depends on the deployment context. For batch evaluation where latency is irrelevant, maximizing accuracy per dollar favors ToT on tasks with large performance gaps. For interactive applications, the serial dependencies of tree search (each depth step waits for the previous step's evaluations) may make ToT unacceptably slow regardless of dollar cost — a consideration the paper does not quantify but which practitioners must weigh.