Tree-of-Thoughts & Search¶

Agentic AI · L-ToT

Classical search — BFS, DFS, best-first — over a tree whose nodes are LLM-generated thoughts and whose heuristic is an LLM judge.

Learning Objectives¶

1. Formalise the ladder IO → CoT → CoT-SC in the notation of Yao et al. (2023), and state what each rung leaves open — the ambiguous decomposition of a chain into steps, and the majority vote's need for a small output space.
2. State the Tree-of-Thoughts framework: a state is the problem input together with the thoughts produced so far, and every instantiation answers four design questions — thought decomposition, the generator, the evaluator, and the search algorithm.
3. Choose a generator (i.i.d. samples vs. propose prompt) and an evaluator (value vs. vote) for a given task, arguing from how rich the thought space is.
4. Execute ToT-BFS and ToT-DFS by hand — breadth limit, pruning threshold, backtracking — and read ToT's own ablations for what each mechanism is worth.
5. Relate the search to its classical originals — BFS, DFS, best-first / $A^*$, and MCTS by name — and say precisely which guarantee survives an LLM heuristic and which does not.
6. Explain why the evaluator, not the search algorithm, is the bottleneck, place the verifier (at every node · at the end · nowhere), and decide when deliberate search is worth its 5–100× token bill.

Overview¶

Tree-of-Thoughts is classical search over a tree whose nodes are thoughts — intermediate reasoning steps written by a language model — and whose heuristic is an evaluation by the same model. Part I states why a single chain of thoughts is insufficient for a combinatorial problem, Part II which prompting strategies precede the tree, Part III which four design decisions define the framework, Part IV which search algorithms operate on the tree, Part V what the search gains and costs, Part VI how a graph generalises the tree, and Part VII where the search is executed:

Part I — The Case for Deliberate Search¶

A left-to-right decoder commits to one continuation and can never revisit it. The argument for the alternative is made before any machinery: problem solving is classically search through a combinatorial space, and the two things such a search needs — branches at a decision point and a heuristic that judges them — are exactly the two an autoregressive chain lacks. Length and breadth are different resources, and only breadth requires a evaluator to compare the alternative paths.

From a Chain to a Tree¶

"It is perhaps surprising that underlying all this progress is still the original autoregressive mechanism for generating text, which makes token-level decisions one by one and in a left-to-right fashion. Is such a simple mechanism sufficient for a LM to be built toward a general problem solver? If not, what problems would challenge the current paradigm, and what should be alternative mechanisms?" — Yao et al. (2023), §1

System 1 and System 2. Yao et al. answer their own question from dual-process theory (Kahneman, 2011): people engage a decision in a fast, automatic, unconscious mode — System 1 — or a slow, deliberate, conscious one — System 2. Token-level autoregressive decoding is the System-1 analogue: associative, left to right, one pass, no alternatives held open. The tree is the System-2 augmentation — maintain several candidates, evaluate them, and only then commit. Hence the paper's subtitle: Deliberate Problem Solving.

• CoT / ReAct follow one line of reasoning, left to right.
• CoT-SC samples $k$ whole chains independently and takes the majority answer — breadth at the root, and nowhere else.
• Tree-of-Thoughts branches at every step: generate several candidate "thoughts" (branching via temperature sampling, → L-ReAct), score them, and search the resulting tree for a good path.

The Combinatorial Problem Space¶

"A genuine problem-solving process involves the repeated use of available information to initiate exploration, which discloses, in turn, more information until a way to attain the solution is finally discovered." — Newell et al. (1959), quoted in Yao et al. (2023), §3

Research on human problem solving describes it as search through a combinatorial problem space (Newell & Simon, 1972): the nodes are partial solutions, the branches are operators that extend them, and which branch to take is decided by a heuristic that guides the solver towards a solution.

Read against that picture, a left-to-right decoder is missing both halves (Yao et al., 2023, §3):

The whole week is the repair of those two — branches, and a heuristic to judge them. The second is the hard half.

Just-in-Time Selection and Deliberate Search¶

A ReAct agent chooses its next action just in time: it looks at the current observation, picks one action, and commits — the choice is made at the moment it is needed, with no alternatives held open. Plan-and-solve moves the choosing forward in time, into an explicit plan. ToT moves it sideways: several candidate next steps exist simultaneously, are scored against one another, and only then is one committed to — and the commitment can be undone.

Read that way, "just-in-time" and "deliberate" are not opposites: ToT is also just-in-time — it decides step $i$ only when it gets there. What it adds is breadth at the decision point and the ability to return to it.

Search and decomposition sit at different levels, and compose. ToT is a modification of CoT: the same object — one reasoning trace towards one answer — with several continuations sampled and searched instead of a single one taken. Decomposition (→ L-Decomp) works one level up: the task is split into sub-tasks, and each sub-task is handed to an executor that itself reasons — with CoT for straight sequential logic, with ReAct where it must call tools, or with ToT where that one sub-step needs genuine exploration. So the question is never "plan or search?": planning decides what the steps are, search decides how one hard step is solved.

Part II — The Ladder from IO to CoT-SC¶

Three prompting strategies precede the tree, and each leaves a defect the next repairs. They are stated in the notation of Yao et al. (2023), because the same symbols carry the framework that follows: one model $p_\theta$ under several prompts, a thought $z_i$, and a state $s = [x, z_{1\cdots i}]$ ($x$ is the full initial prompt context, including system instructions and loaded files). The ladder ends at two limits a chain cannot repair — a decomposition into steps that is left ambiguous, and a majority vote that needs a small output space.

Notation for Thoughts and States¶

This week is written in the notation of Yao et al. (2023), §2. Four conventions, then the bridge to ours.

• $p_\theta$ — a pre-trained language model with parameters $\theta$. Every generator and every evaluator below is a call to this one model; only the prompt differs.
• Lowercase $x, y, z, s$ denote a language sequence — not a single symbol. A sequence is written $x = (x[1], \dots, x[n])$ where each $x[i]$ is one token, so that $$p_\theta(x) \;=\; \prod_{i=1}^{n} p_\theta\big(x[i] \mid x[1], \cdots , x[i-1]\big).$$ Square brackets index tokens, subscripts index thoughts: $x[i]$ is the $i$-th token of $x$, while $z_i$ is the $i$-th thought — itself a whole sequence of tokens.
• Uppercase $S$ denotes a collection of sequences — a set of states, e.g. the search frontier.
• Prompt abbreviation. $p_\theta^{\text{prompt}}(\text{out} \mid \text{in}) = p_\theta\big(\text{out} \mid \text{prompt}(\text{in})\big)$: the wrapper that turns an input into an actual prompt (instructions, few-shot examples) is folded into the superscript. So $p_\theta^{\mathrm{IO}}$, $p_\theta^{\mathrm{CoT}}$, $p_\theta^{\mathrm{propose}}$, $p_\theta^{\mathrm{value}}$ and $p_\theta^{\mathrm{vote}}$ are all one model under five prompts, not five models.

Every symbol this week uses, introduced here and used from The Tree-of-Thoughts Framework on:

The bridge to our notation. The course writes a token sequence as random variables $W_{1:T}$ with values $w_{1:T}$; the paper's $x$, $y$, $z$ are exactly such values, and $p_\theta(x)$ above is the same chain rule as $P(W_{1:T}) = \prod_t P(W_t \mid W_{1:t-1})$. A thought $z_i$ is a contiguous sub-sequence of that token stream — which is why the two indices differ. And a state is a context. $s=[x,z_{1\cdots i}]$ is precisely the context $c_k$ of the agent loop — everything the model conditions on at that node — grown by the thought update $c_{k+1}=(c_k,\hat a_k)$, with no observation because a thought returns none (the context $c_k$). ToT is therefore a search over contexts: an edge appends one thought, and what the tree adds to a single chain is keeping several contexts alive at once.

⚠️ Four collisions, kept on purpose. The paper's letters clash with symbols the course already uses. They never occur in the same expression, but read them deliberately:

| Symbol | Here | Elsewhere in the course | |---|---|---| | $V$ | the state evaluator $V(p_\theta, S)$ | the vocabulary $V$, of size $\lvert V \rvert$ | | $z$ | a thought $z_i$, a language sequence | logits $\mathbf{z} \in \mathbb{R}^{\lvert V\rvert}$ (bold) | | $s$ | a ToT state | a parser/FSM state $s_t \in Q$ (constrained decoding) | | $T$ | the step limit | sequence length $W_{1:T}$; sampling temperature |

And one deliberate break with the house rule: $S$ here is a set, not a random variable. Capital letters mean random variables everywhere else in this course; in this week's source they mean collection of sequences. We keep the paper's letters so that the lecture and the paper can be read side by side.

Input–Output Prompting and Chain-of-Thought¶

IO prompting is the bare case: wrap the input in instructions, read off the answer.

$$y \sim p_\theta^{\mathrm{IO}}(y \mid x)$$

Chain-of-Thought (Wei et al., 2022) addresses the case where the map from $x$ to $y$ is non-trivial — $x$ a maths question, $y$ a single number. It introduces a chain of thoughts $z_1, \dots, z_n$ to bridge $x$ and $y$, each $z_i$ "a coherent language sequence that serves as a meaningful intermediate step toward problem solving" (Yao et al., 2023, §2) — for maths QA, one intermediate equation. The thoughts are sampled in sequence, then the answer:

$$z_i \sim p_\theta^{\mathrm{CoT}}\big(z_i \mid x, z_{1 \cdots i-1}\big), \qquad y \sim p_\theta^{\mathrm{CoT}}\big(y \mid x, z_{1\cdots n}\big)$$

What CoT leaves open — and it is the opening ToT walks through. In practice nobody samples the $z_i$ one at a time: the whole thing is drawn as one continuous sequence, $[z_{1\cdots n}, y] \sim p_\theta^{\mathrm{CoT}}(z_{1\cdots n}, y \mid x)$, and "the decomposition of thoughts (e.g. is each $z_i$ a phrase, a sentence, or a paragraph) is left ambiguous" (Yao et al., 2023, §2). CoT therefore has the $z_i$ in its formalism but no step boundary in its mechanism — nothing to branch at, nothing to score, nothing to return to.

What the CoT primary actually established (Wei et al., 2022), because the formalism above hides it. The method is a change to the exemplars, not to the instruction: each becomes a triple $\langle x, z, y\rangle$ instead of a pair $\langle x, y\rangle$ — eight hand-written chains, greedy decoding (temperature $T=0$), no fine-tuning. PaLM 540B on GSM8K — grade-school mathematics word problems — goes 17.9 → 56.9. Two findings matter for this week. First, a four-way ablation rules out the cheap explanations: prompting for the equation only ≈ the baseline, putting the chain after the answer ≈ the baseline, and — the interesting one — variable compute only, emitting a run of dots as long as the equation needed, also ≈ the baseline. Extra token positions are not the mechanism; what the intermediate steps carry is. Second, CoT is an emergent ability of scale — no benefit below ~100 B parameters and an active loss below ~10 B, where models produce "fluent but illogical chains of thought." And their own stated limitation is this week's premise: "there is no guarantee of correct reasoning paths."

⚠ Few-shot CoT is this paper; the zero-shot trigger "Let's think step by step" is Kojima et al. (2022) — a different result, and not what is formalised above.

Self-Consistency with Chain-of-Thought¶

CoT-SC (Wang et al., 2023) is an ensemble over chains: sample $k$ of them i.i.d., return the most frequent answer.

$$\big[z^{(i)}_{1\cdots n},\, y^{(i)}\big] \sim p_\theta^{\mathrm{CoT}}\big(z_{1\cdots n}, y \mid x\big), \quad i = 1 \cdots k \qquad\Longrightarrow\qquad \hat{y} \;=\; \arg\max_{y} \; \#\{\, i \mid y^{(i)} = y \,\}$$

The notation $\#\{\dots\}$ counts the set of indices where the condition holds, and $\arg\max_y$ acts on this count function to select the candidate answer with the highest tally — the voted answer $\hat{y}$.

It improves on CoT because there are generally different thought processes for the same problem — different ways to prove the same theorem — so a decision taken across many of them rests on a richer set of thoughts than any single chain can offer.

Marginalization via Sampling¶

To find the true marginal probability of an answer $y$, one would have to sum $p_\theta^{\mathrm{CoT}}(z_{1\cdots n}, y \mid x)$ across all infinitely many possible thought sequences $z_{1\cdots n} \in \mathcal{Z}$:

$$p_\theta^{\mathrm{CoT}}(y \mid x) = \sum_{z_{1\cdots n} \in \mathcal{Z}} p_\theta^{\mathrm{CoT}}(z_{1\cdots n}, y \mid x)$$

Because summing over all $z_{1\cdots n} \in \mathcal{Z}$ is intractable, Monte Carlo integration is used instead. By drawing $k$ finite i.i.d. samples $\big[z^{(i)}_{1\cdots n},\, y^{(i)}\big] \sim p_\theta^{\mathrm{CoT}}\big(z_{1\cdots n}, y \mid x\big)$, the marginal distribution is approximated empirically:

$$p_\theta^{\mathrm{CoT}}(y \mid x) \;\approx\; \frac{1}{k} \#\Big\{\, i \;\mid\; y^{(i)} = y \,\Big\}$$

Selecting the answer $\hat{y}$ that maximizes this empirical probability directly yields the majority vote:

$$\hat{y} \;=\; \arg\max_{y} \; \#\Big\{\, i \;\mid\; y^{(i)} = y \,\Big\}$$

Two limits, and each one names a piece of what comes next (Yao et al., 2023, §2):

A tree and an evaluator: that is Tree-of-Thoughts, and the rest of the lecture is what each one costs.

Self-Consistency: Aggregation, Diversity and Cost¶

Why the plain vote, and not the model's own probability. One could weight each sampled pair by its likelihood. Measured on PaLM-540B / GSM8K, the unweighted majority scores 74.4, a length-normalised weighted sum 74.1, an unnormalised weighted sum 59.9, and a weighted average 22.1. The reason Wang et al. (2023) give for the tie at the top is the teaching point: the sampled paths' normalised probabilities are nearly equal, because the model "is not well calibrated and thus cannot distinguish well between correct solutions and wrong solutions" (their fn. 2) — which is precisely why Cobbe et al. (2021) had to train a verifier. The count carries information the likelihood does not. That is this week's "the evaluator is the bottleneck" thesis arriving from the other side: here the model's own score is the thing you must not trust, and counting independent draws is what replaces it.

The Majority-Vote Guarantee — Condorcet's Jury Theorem¶

Majority voting guarantees higher accuracy only under two strict conditions:

• each vote must be made independently, and
• each individual voter must have a probability $p > 1/2$ of being correct.

To see why, we can derive it directly:

Write $y^*$ for the correct answer, as distinct from the voted answer $\hat{y}$ the procedure returns; the vote succeeds exactly when $\hat{y} = y^*$. Let $N$ chains be sampled, each reaching $y^*$ independently with the same probability $p$, and let the random variable $K$ denote how many of them do.

The probability that exactly $k$ chains are correct is given by the Binominal Distribution:

$$P(K = k) = \binom{N}{k} p^k (1-p)^{N-k}$$

A majority vote yields the correct answer if and only if strictly more than half of the $N$ chains are correct ($K > N/2$).

Since $K$ must be an integer, the smallest possible integer greater than $N/2$ is the ceiling $\lceil N/2 \rceil$ (or $\frac{N}{2} + 1$ if $N$ is even, or $\frac{N+1}{2}$ if $N$ is odd).

Because these outcomes ($K = \lceil N/2 \rceil, K = \lceil N/2 \rceil + 1, \dots, K = N$) are mutually exclusive, we add their individual probabilities

$$P(\text{majority correct}) = P(K > N/2) = \sum_{k=\lceil N/2 \rceil}^{N} \binom{N}{k} p^k (1-p)^{N-k}$$

To evaluate the limit as $N \to \infty$, we express $K$ as the sum of $N$ independent indicator variables:$$K = X_1 + X_2 + \dots + X_N$$where each $X_i = 1$ if chain $i$ is correct, and $X_i = 0$ otherwise.

• The sample average is $\overline{X}_N = \frac{K}{N}$.
• The expected value of each $X_i$ is $E[X_i] = p$.

By the Weak Law of Large Numbers, as $N \to \infty$, the sample average $\overline{X}_N$ converges in probability to the true mean $p$:

$$\lim_{N \to \infty} P\left(\left\vert{} \frac{K}{N} - p \right\vert{} < \epsilon\right) = 1 \quad \text{for any } \epsilon > 0$$

Now, rewrite the majority condition $\frac{K}{N} > \frac{1}{2}$ relative to $p$:

$$\frac{K}{N} > \frac{1}{2} \iff \frac{K}{N} - p > \frac{1}{2} - p$$

• Case 1: $p > \frac{1}{2}$: Here, $\frac{1}{2} - p$ is negative ($-\delta$ where $\delta > 0$). As $N \to \infty$, $\frac{K}{N}$ concentrates tightly around $p$. The probability that $\frac{K}{N}$ falls above $\frac{1}{2}$ approaches $1$: $$\lim_{N \to \infty} P\left(\frac{K}{N} > \frac{1}{2}\right) = 1$$
• Case 2: $p < \frac{1}{2}$Here, $\frac{1}{2} - p$ is positive ($\delta > 0$). As $N \to \infty$, $\frac{K}{N}$ concentrates around $p$, which is strictly below $\frac{1}{2}$. The probability that $\frac{K}{N}$ exceeds $\frac{1}{2}$ approaches $0$: $$\lim_{N \to \infty} P\left(\frac{K}{N} > \frac{1}{2}\right) = 0$$

The majority is correct exactly for case 1, i.e. if $p > 1/2$:

$$\lim_{N \to \infty} P(\text{majority correct}) = \begin{cases} 1 & \text{if } p > \frac{1}{2} \\ 0 & \text{if } p < \frac{1}{2} \end{cases}$$

This is Condorcet's jury theorem (1785), and it earns its place three times:

1. It states why the vote works, instead of asserting that it does.
2. It makes the threshold explicit. At $p < 1/2$ the same sum tends to zero — more samples make the answer worse, monotonically. Sampling more is neither free nor always an improvement.
3. It separates the two assumptions, and shows which of them a sampling run actually violates. Drawing $N$ chains from one model at a fixed temperature does satisfy independence — the decoder is memoryless, so the draws are i.i.d. given the parameters $\theta$ and the prompt $x$. What is not given is $p > 1/2$: that probability is $p_\theta^{\mathrm{CoT}}(y^* \mid x)$, a property of this model on this input. The vote therefore removes sampling variance and nothing else.

This creates a direct contrast with the $p^n$ decay seen in multi-step reasoning. In a sequential chain of $n$ steps, overall success requires every step to succeed, causing reliability to collapse exponentially as $p^n$.Parallel voting works in the opposite direction: by aggregating $N$ independent samples using the Binomial distribution, reliability concentrates toward 1 (provided $p > 0.5$). Chain sequentially and errors compound; vote in parallel and agreement concentrates.

Cost. $k\times$ the inference of a single chain, but accuracy saturates — the authors' own advice is 5–10 paths for most of the gain. Compare the bill for full tree search later in this lecture: 5–100× CoT's generated tokens.

Where it fails. Nothing in the method contradicts the majority, so a model that is consistently wrong is reinforced rather than detected — high agreement is compatible with a shared bias (Turpin et al., 2023). And the vote is over answers only: Wang et al.'s own example on StrategyQA — yes/no questions whose reasoning steps are left implicit — reaches the correct conclusion through incorrect population figures. Agreement is evidence about the answer, never about the narration.

Mitigating Correlation through Prompt Variation¶

Sampling $k$ chains from one model under one prompt can only average out sampling noise: the probability of drawing the correct answer, $p_\theta^{\mathrm{CoT}}(y^* \mid x)$, is fixed by the parameters $\theta$ and the prompt $x$ together. With $\theta$ fixed, the remaining variable is $x$. Sampling under a family of prompts $\{x_1, \dots, x_k\}$ — paraphrases, a different persona, a reordered few-shot set — replaces one conditional distribution by several, $p_\theta^{\mathrm{CoT}}(y \mid x_i)$, so a bias that lives in the phrasing rather than in the parameters no longer affects every draw. An instance on which the original wording gives $p_\theta^{\mathrm{CoT}}(y^* \mid x) < 1/2$ may sit above the threshold under a different wording.

Unequal voters change the statement of the theorem. One prompt per vote leaves the $X_i$ independent but no longer identically distributed, and the limit is then governed by the mean $\bar p = \frac{1}{k} \sum_i p_\theta^{\mathrm{CoT}}(y^* \mid x_i)$: the majority is correct in the limit while $\bar p$ stays above $1/2$. A variant earns its place only if it raises $\bar p$, or fails on different instances than the others do.

That is the caveat on varying the reasoning structure. Demanding a bare answer, an explicit chain, and a program to execute decorrelates far more than paraphrase does, since the three read the problem through different mechanisms — but they are not equally accurate. Prompting for the answer alone lowers $p$ on precisely the multi-step tasks self-consistency is used for (Wei et al., 2022), so mixing it into the pool pulls $\bar p$ down and the vote can end up below the best single variant. Diversity is free only among variants of comparable strength, which is why the structural variant worth having is the one that is also grounded: a program whose result enters the vote is scored by execution rather than by the same parameters. Grounding a model's judgement in an execution result is measured to be worth more than a larger model in the neighbouring task of scoring candidates (Chen et al., 2024).

The boundary is unchanged. Every variant queries the same $\theta$. Where the model lacks the knowledge or the capability outright, $p_\theta^{\mathrm{CoT}}(y^* \mid x_i) < 1/2$ for all $i$, $\bar p$ stays below the threshold, and no rephrasing rescues the vote. A prompt-bound error is within reach of prompt variation; a parameter-bound one requires different parameters.

Mitigating Correlation through Model Variation¶

Varying $x$ leaves the parameters in place, so it cannot repair an error that lives in them. The remaining variable is $\theta$ itself: draw the votes from different models — different checkpoints, different families, different training data — so that the pool is $p_{\theta_1}, \dots, p_{\theta_m}$ rather than one distribution in $m$ costumes. This is the classical ensemble, and it is the only one of the three moves that changes the parameters an error lives in rather than the phrasing around them.

$$y^{(i,j)} \sim p_{\theta_j}^{\mathrm{CoT}}\big(y \mid x_i\big), \qquad \hat{y} \;=\; \arg\max_{y} \; \#\big\{\, (i,j) \;\mid\; y^{(i,j)} = y \,\big\}$$

Three things to weigh before paying for it:

• It removes shared bias only to the extent that the models do not share it. Nominally distinct weights can still fail identically — through shared training data, a shared benchmark, or one model having been distilled from another — so independence of weights must never be read as independence of errors. It is a property to measure on the task, not to assume from the model list.
• It raises $\bar p$ only if the added models are comparable in strength. The unequal-voter argument above applies unchanged: a weak model in the pool pulls the mean down and can leave the vote below the best single model.
• It costs the worst of every option. Each provider is paid, prompted and parsed separately, and the slowest one sets the latency of the whole vote.

The ordering that follows is the practical one. Resample to remove sampling noise; rephrase to remove a phrasing-bound error; re-model to remove a parameter-bound one — rising in cost, and falling in how often the cheaper move would already have sufficed.

Revise instead of resample¶

Self-consistency spends its budget in parallel — $k$ independent chains, one vote, no chain ever reading another. The alternative spends it sequentially: produce one answer, criticise it, and produce the next answer conditioned on that criticism. It is the last thing a single chain can do before branching, and it introduces the component the rest of the lecture turns on — a critic whose judgement steers generation. The two cells below state the canonical forms in the notation of this lecture. Both return in Refinement as a Third Thought Generator, where the same loop is read as a way of producing the next node of a tree.

Reflection¶

Reflexion (Shinn et al., 2023) for self-awareness across trails splits the loop into three roles and lets them be three different things.

Fig. 2 of (Shinn et al., 2023)

Written with this lecture's prompt superscripts — one model $p_\theta$ under several prompts:

That sentence is appended to a memory $\mathrm{mem}$ holding one to three of them — one to three because the context window bounds it — and the next attempt is conditioned on it. The loop repeats until the evaluator passes or a trial budget is exhausted. The update is text, not a gradient: nothing about $\theta$ changes, and what improves between attempts is the context the actor is given. Shinn et al. write this by folding the memory into the policy's parameters, $\pi_\theta(a \mid s)$ with $\theta = \{M_a, \mathrm{mem}\}$ — their $\theta$, which is not the model weights this lecture writes $\theta$ for.

Reflection is suitable for tasks where the cost per attempt is low and therefore multiple attempts are acceptable, such as code generation against a test suite (clear evaluation signal and stopping signal).

Self-Refine (Madaan et al., 2023) is the same loop with the three roles collapsed onto one model under three prompts, which the lecture's superscript convention writes directly (with $\mathrm{fb}$=feedback):

$$y_0 \sim p_\theta^{\mathrm{gen}}(y \mid x), \qquad \mathrm{fb}_t \sim p_\theta^{\mathrm{fb}}(\mathrm{fb} \mid x, y_t), \qquad y_{t+1} \sim p_\theta^{\mathrm{refine}}\big(y \mid x,\, y_0, \mathrm{fb}_0, \dots, y_t, \mathrm{fb}_t\big)$$

Three things follow from the third expression. The refine step is conditioned on the whole history of drafts and critiques rather than on the last pair alone, so a correction already made is not made twice — and the context grows with every iteration, which is what makes the loop expensive. All three prompts are few-shot: the behaviour is demonstrated by examples, not described by instructions. And the loop stops either at a fixed cap on $t$ or on a stop indicator the feedback itself emits, so the critic also decides when it is finished. Across seven tasks this is worth roughly 20 points over a single generation by the same model, with no training and no external signal.

Its two negative results are the ones this lecture needs.

• The critique is the loop, not a detail of it. Replacing actionable, specific feedback by generic feedback costs most of the gain, and removing it costs all of it — on Sentiment Reversal, 43.2 with real feedback, 31.2 with generic feedback, 0 with none.
• Mathematical reasoning barely moves, and the reason is the critic reading its own chain: "a consistent-looking reasoning chain can deceive LLMs to think that 'everything looks good'" — which is literally the feedback returned for 94 % of instances. Gains appear only once an external source can say that the current answer is wrong.

Read as a thought generator, refinement therefore inherits the problem of the whole lecture: it is a proposal mechanism whose direction is set by a critique, and a critique of a reasoning chain is the case in which a model judge is measurably at its worst.

Part III — The Four Design Questions¶

Tree-of-Thoughts is a framework, not one algorithm. This part first states the classical search problem it instantiates, then takes its four questions in turn — what one thought is, how candidates are generated, how a partial state is scored, and which search algorithm walks the tree — and closes by reading the earlier prompting strategies back as degenerate trees, collapsed in depth or in breadth.

Problem Solving by Search¶

Classical search does not require the graph to exist in memory. A search problem is given by five parts (Russell & Norvig, 2021, §3.1):

Together they define a state space: a directed graph whose vertices are states and whose edges are actions. It is generated on demand — $\text{Actions}$ and $\text{Result}$ are the adjacency list, computed when a node is expanded — so the graph may be far larger than any machine could store, and the search tree built over it (whose nodes are paths) may be infinite where the state space is finite.

Heuristic $h$¶

The five parts above say what the moves are; they say nothing about which move is worth trying. A heuristic $h(s)$ supplies that: a cheap, fallible estimate of the cost of getting from $s$ to a goal — cheap because it is consulted at every expansion, fallible because computing the true remaining cost $h^*(s)$ would mean solving the problem. It orders the frontier and decides nothing irrevocably.

Together with $g$ it splits one path at the node under consideration:

Straight-line distance is the standard example: on a road map $g$ is the kilometres already driven and $h$ the distance as the crow flies, which no route can beat and most routes exceed. Over thoughts neither quantity is given — $g$ has to be invented and $h$ is asked of a language model — and what that costs is the subject of Search Algorithms over Thoughts.

Search Tree¶

While the underlying state space is a graph (where multiple paths can lead to the same state), classical search algorithms navigate this space by building an explicit search tree rooted at the initial state $s_0$. In this tree, every node represents a unique path through the state space graph rather than just a state itself.

The pseudocode below demonstrates this translation in practice: it dynamically expands the implicit graph into a search tree on the fly, generating path nodes on demand without ever needing to construct or store the full graph in memory.

$$ \begin{array}{l} \textbf{Tree-Search}(s_0, \text{Actions}, \text{Result}, \text{StepCost}, \text{IsGoal}, h) \\ \hline \textbf{Input: } \text{initial state } s_0 \text{; the problem functions; a heuristic } h \\ \textbf{Output: } \text{a node holding a goal state, or } \textit{failure} \\ \hline 1: \quad n_0 \gets \text{Node}(\text{State} = s_0,\; \text{Parent} = \text{null},\; \text{Action} = \text{null},\; \text{PathCost} = 0) \\ 2: \quad \textit{frontier} \gets \{\, n_0 \,\} \\ 3: \quad \textbf{while } \textit{frontier} \neq \emptyset \textbf{ do} \\ 4: \quad \qquad n \gets \text{Remove}(\textit{frontier}) \qquad \text{// the strategy — the only line that differs} \\ 5: \quad \qquad \textbf{if } \text{IsGoal}(n.\text{State}) \textbf{ then return } n \\ 6: \quad \qquad \textbf{for each } a \in \text{Actions}(n.\text{State}) \textbf{ do} \\ 7: \quad \qquad \qquad s' \gets \text{Result}(n.\text{State}, a) \\ 8: \quad \qquad \qquad g' \gets n.\text{PathCost} + \text{StepCost}(n.\text{State}, a, s') \\ 9: \quad \qquad \qquad n' \gets \text{Node}(\text{State} = s',\; \text{Parent} = n,\; \text{Action} = a,\; \text{PathCost} = g') \\ 10: \quad \qquad \qquad \text{Insert}(n',\, \textit{frontier}) \\ 11: \quad \textbf{return } \textit{failure} \\ \hline \end{array} $$

Three names in the box are used for the rest of the week. The frontier is the set of nodes that have been generated but not yet expanded — the search's own to-do list, and the object written $S$ once the states are thoughts. $\text{PathCost}$ carries $g(n)$, the cost accumulated from the root, and $h$ estimates the cost still to come. Breadth-first and depth-first search use neither: they read only the shape of the tree, so for them $\text{StepCost}$ and $h$ drop out of the signature. One box therefore covers the whole family, informed algorithms included — what distinguishes them is whether line 4 consults $g$ and $h$.

Line 4 alone decides the algorithm (Russell & Norvig, 2021, §§3.3–3.5):

Path Reconstruction

The parent reference (or backpointer) links each child node directly to the node that generated it. Because the search algorithm explores forward from the initial state to the goal, storing parent pointers creates a linked chain pointing backward toward the root.

Markov Decision Process¶

A Markov decision process (MDP) is a search problem in which an action has an uncertain outcome and the task is stated as a reward. Russell & Norvig (2021, §16.1) call it "a stochastic generalization of the search problems of Chapter 3". The MDP keeps the states, $s_0$ and $\text{Actions}(s)$ of the search problem and replaces two of its parts:

Four quantities describe how an agent behaves in an MDP (Sutton & Barto, 2018, §§3.1–3.5):

• A policy $\pi(a\mid s)$ is the probability of choosing action $a$ in state $s$. The policy $\pi(a_k\mid c_k)$ of the agent loop is a policy in this sense, with the context as its state.
• A trajectory $\tau = (s_0, a_0, r_1, s_1, a_1, r_2, \dots, s_n)$ is one run of the agent, written out as the sequence of states, actions and rewards.
• The return $G = r_1 + r_2 + \dots + r_n$ is the sum of the rewards of one trajectory.
• The value $v_\pi(s) = \mathbb{E}_\pi[\,G \mid \text{the run starts in } s\,]$ is the expected return of the trajectories that start in $s$ and follow $\pi$.

A partially observable MDP (POMDP) adds a sensor model. Where the agent does not see the state, it receives an observation $o$ with probability $O(o\mid s)$, the sensor model (also called observation or emission model) (Russell & Norvig, 2021, §16.4). An LLM agent is in this case: its context holds the observations, not the state of the environment.

Reward misspecification. The reward is the specification of the task: an agent raises the reward that was written down, not the goal that was meant by it. Agreement between the objective given to a machine and the true preferences of its user is the value alignment problem (Russell & Norvig, 2021, §1.1.5); a reward that can be raised without reaching the goal is misspecified, and a model-based scorer that is optimised against (see Evaluator Quality as the Limiting Factor) is an instance. The MDP formalism itself — the dynamics, discounting and the POMDP that agent benchmarks specify — is the subject of the extended course (→ L-MDP).

The Tree-of-Thoughts Framework¶

ToT instantiates exactly that search problem, over a tree in which each node is a state

$$s \;=\; [\,x,\; z_{1\cdots i}\,]$$

— "a partial solution with the input and the sequence of thoughts so far" (Yao et al., 2023, §3). The root is $s_0 = [x]$, an edge appends one thought, and a leaf is a candidate answer. Two parts of the classical problem are replaced, and both are LLM calls:

That is the whole idea; everything difficult about this week lives in the second row.

A specific instantiation of ToT answers exactly four questions (Yao et al., 2023, §3):

Thought decomposition.¶

CoT samples thoughts coherently with no explicit decomposition; ToT uses the problem's own structure to fix what one thought is — a couple of words (crosswords), one line of equation (Game of 24), a whole paragraph of writing plan (creative writing).

Sizing a thought is a two-sided constraint (Yao et al., 2023, §3). A thought must be small enough that the model can sample promising and diverse candidates — "generating a whole book is usually too 'big' to be coherent" — yet big enough that the model can evaluate its prospects — "generating one token is usually too 'small' to evaluate". Making the decomposition explicit is what turns a chain into a searchable tree.

Thought Generation¶

Thought generator $G(p_\theta, s, k)$. Given a state $s = [x, z_{1\cdots i}]$, produce $k$ candidates for the next thought $z_{i+1}$. Two strategies, chosen by how rich the thought space is:

The trade is diversity against duplication. Independent draws from a narrow space keep returning the same handful of thoughts — $k$ calls paid for one distinct candidate — while a single propose prompt sees what it has already suggested and is therefore forced to vary. Both are the same model; only the prompt and the number of calls differ. And the candidates come out of the decoder: a model pinned to greedy decoding offers a search nothing to explore, so temperature and top-$p$ are a precondition, not an unrelated setting.

Refinement as a Third Thought Generator¶

ToT's creative-writing task supplies a third strategy. An iterative-refine pass on top of the ToT output raises the coherency score from 7.56 to 7.91, which the authors read structurally:

"We believe it could be thought of as 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." — Yao et al. (2023), §4.2

So a critique-and-revise loop — Self-Refine (Madaan et al., 2023) is the canonical one — is not a rival to search: it is another way of producing the next node, and it inherits the dependency every node-producing step has — it is only as good as the critique driving it. (The loop itself — execute, critique, refine, iterate — and the producer–critic split are the Reflection pattern.)

State Evaluation¶

State evaluator $V(p_\theta, S)$ — the heuristic, computed by the model itself. It is curried: $V(p_\theta, S)$ takes the model and a frontier and returns a scoring function, which applied to one state yields that state's score.

What is scored is the state's prospect, not its prose. $V$ is asked how likely a solution is to be reachable from $s$ — the question a classical $h$ asks, put as a success likelihood instead of a remaining cost (Sharon, 2026). The paper's own mechanism says as much: the value prompt performs "a few lookahead simulations" (5, 5, 14 reaches 24 via 5+5+14) and commonsense elimination (1, 2, 3 are too small to reach 24), and both are claims about the goal rather than about the elegance of the step just taken (Yao et al., 2023, §3). A locally impeccable thought that leaves an unreachable state must score low. What the model actually returns is the plausibility of the text in front of it, and the distance between the two is where this week's failures live.

Either strategy can be sampled several times and aggregated, trading tokens for a steadier heuristic.

Prompting Strategies as Degenerate Trees¶

ToT is not a competitor to the earlier prompting patterns — they are special cases of it, with the tree collapsed in one direction or the other (Yao et al., 2023, §3):

The axis that matters is not "which prompting trick", but where the verifier sits. Self-consistency needs none at all — the vote marginalises the reasoning path away (Wang et al., 2023), which is legal only where the answer set is small and an equality test exists. Best-of-$N$ needs one at the end, where a complete answer is much easier to score than a half-finished thought. Tree search needs one at every node. Cost rises in that order, and so does exposure to a bad evaluator.

Part IV — Search Algorithms over Thoughts¶

The fourth design question, worked out. With $G$ as the successor function and $V$ as the heuristic, the algorithms are the classical ones — the tree is new, the search is not:

• BFS under a width limit — for shallow trees ($T \le 3$) whose early states already prune well ($b \le 5$).
• DFS with pruning and backtracking — for deep trees: logic puzzles, crosswords (up to 10 steps), code.

Those two are what Yao et al. (2023) implement and measure; best-first / $A^*$ and MCTS they name and explicitly leave to future work (§3.4). Both are constructed here anyway, because what breaks in them is the instructive part: which classical guarantee survives when the heuristic is an LLM judgement.

Beam Search over Tokens¶

Beam search is breadth-first search whose frontier is limited to the $b$ best nodes: it keeps "only the k nodes with the best f-scores, discarding any other expanded nodes", which makes it "incomplete and suboptimal" but bounded in memory (Russell & Norvig, 2021, §3.5.5). Applied to a language model, a node is a partial output $y = (w_1, \dots, w_t)$ and its score is the log-probability of the whole sequence,

$$ s(y) = \sum_{i=1}^{t} \log p_\theta(w_i \mid x, w_{<i}), $$

where $\mathcal{V}$ denotes the vocabulary (written $V$ elsewhere in the course; in this lecture $V$ is the state evaluator) and $\langle\text{eos}\rangle$ the end-of-sequence token. A sequence that does not yet end in $\langle\text{eos}\rangle$ is called open.

$$ \begin{array}{l} \textbf{BeamSearch}(x, p_\theta, b, T_{\max}) \\ \hline \textbf{Input: } \text{prompt } x \text{, LM } p_\theta \text{, beam width } b \text{, length limit } T_{\max} \\ \textbf{Output: } \text{the highest-scoring sequence found} \\ \hline 1: \quad B_0 \gets \{\, () \,\} \\ 2: \quad \textbf{for } t = 1, \dots, T_{\max} \textbf{ do} \\ 3: \quad \qquad C_t \gets \{\, y \in B_{t-1} \mid y \text{ ends in } \langle\text{eos}\rangle \,\} \cup \{\, [y, w] \mid y \in B_{t-1} \text{ open},\; w \in \mathcal{V} \,\} \\ 4: \quad \qquad B_t \gets \text{the } b \text{ elements of } C_t \text{ with the largest } s(y) \\ 5: \quad \qquad \textbf{if } \text{no } y \in B_t \text{ is open} \textbf{ then break} \\ 6: \quad \textbf{return } \arg\max_{y \in B_t} s(y) \\ \hline \end{array} $$

Greedy search is the case $b = 1$. Line 4 is where the two differ: greedy search commits to the most probable next token and cannot revise the choice, whereas the beam retains $b - 1$ prefixes whose last token was less probable but whose continuation may be more probable. In Russell & Norvig's example, translating The front door is red into Spanish, greedy search emits La entrada, because entrada is the most probable second word; every continuation of it is improbable, and with $b = 2$ the prefix La puerta is still in the beam when La entrada is discarded (Russell & Norvig, 2021, §25.3.2). The price is $b$ forward passes per step instead of one, and the result is the most probable sequence within the beam, not the most probable sequence overall.

Code generation. A program has a single correctness criterion and can fail on one wrong token, so the objective is the most probable whole program rather than the most probable next token — which is the quantity beam search maximises. The effect is measured: on HumanEval-X, the HumanEval programming problems with their unit tests translated into Java, Python, JavaScript and Go, beam search with $b = 3$ raises Pass@1 — the share of problems whose single generated program passes all tests — above greedy search in all four languages, for Go from 5.5 % to 14.0 % (Fedrushkov et al., 2024); on HumanEval, $b = 3$ raises accuracy from 0.60 to 0.65 for Llama-3.1-8B (Chan et al., 2025). A wider beam is not automatically better: at $b = 8$, Java and Python return to the greedy value or fall below it, an effect the source reports without explaining.

Where tests exist, likelihood is the wrong objective. Beam search never executes the program. With the same budget of 256 generations on the APPS programming benchmark, sampling programs and keeping the one that passes most public tests more than doubles the pass rate of beam search (25.19 % against 11.95 %; Zhang et al., 2023).

Improved methods.

• Parsing search parses every beam during generation and replaces beams that contain a syntax error (Fedrushkov et al., 2024).
• Planning-guided decoding (PG-TD) runs Monte-Carlo tree search over tokens, completes each partial program by beam search and scores it by the public tests (Zhang et al., 2023).
• Trie-based beam search stores the prefix the beams share only once in the key–value cache of the attention layers, producing the same output with 4–8× less memory (Chan et al., 2025).

ToT-BFS¶

Breadth-first search under a breadth limit $b$: expand the whole frontier, score it, keep the best $b$. It is a beam search whose beams are thoughts and whose score is an LLM judgement rather than a token log-probability.

$$ \begin{array}{l} \textbf{ToT-BFS}(x, p_\theta, G, k, V, T, b) \\ \hline \textbf{Input: } \text{input } x \text{, LM } p_\theta \text{, generator } G \text{ with size limit } k \text{, evaluator } V \text{, step limit } T \text{, breadth limit } b \\ \textbf{Output: } \text{one final answer} \\ \hline 1: \quad S_0 \gets \{x\} \\ 2: \quad \textbf{for } t = 1, \dots, T \textbf{ do} \\ 3: \quad \qquad S_t' \gets \{\, [s, z_t] \mid s \in S_{t-1},\; z_t \in G(p_\theta, s, k) \,\} \\ 4: \quad \qquad V_t \gets V(p_\theta, S_t') \\ 5: \quad \qquad S_t \gets \arg\max_{S \subset S_t',\, |S| = b} \sum_{s \in S} V_t(s) \\ 6: \quad \textbf{return } G(p_\theta, \arg\max_{s \in S_T} V_T(s), 1) \\ \hline \end{array} $$

Line 3 expands every state of the frontier by every candidate thought; line 5 is the beam — the $b$-subset of highest total value; line 6 takes the best surviving state and asks the generator for the answer itself. Cost is explicit in the parameters: $O(b\,k\,T)$ LLM calls, each a full forward pass over a growing prompt.

ToT-DFS and Backtracking¶

Depth-first search that explores the most promising child first, prunes on the evaluator's verdict, and backtracks. Called on the root as $\textbf{ToT-DFS}([x],\, 1,\, \dots)$.

$$ \begin{array}{l} \textbf{ToT-DFS}(s, t, p_\theta, G, k, V, T, v_{th}) \\ \hline \textbf{Input: } \text{state } s \text{, step } t \text{, LM } p_\theta \text{, generator } G \text{ with size limit } k \text{, evaluator } V \text{, step limit } T \text{, threshold } v_{th} \\ \textbf{Output: } \text{outputs recorded at depth } T \text{ — the search continues past each one} \\ \hline 1: \quad \textbf{if } t > T \textbf{ then record } G(p_\theta, s, 1) \qquad \text{// a leaf, not a return} \\ 2: \quad \textbf{for each } s' \in G(p_\theta, s, k) \textbf{ do} \qquad \text{// best-valued candidate first} \\ 3: \quad \qquad \textbf{if } V(p_\theta, \{s'\})(s') > v_{th} \textbf{ then} \\ 4: \quad \qquad \qquad \textbf{ToT-DFS}(s', t+1, p_\theta, G, k, V, T, v_{th}) \\ 5: \quad \qquad \textbf{else prune } s' \text{ and continue with the next sibling} \\ \hline \end{array} $$

Line 1 records, it does not return — reaching depth $T$ yields one candidate output and the recursion carries on, so a run collects several. Line 2's ordering is a priority queue: candidates are scored as they are proposed and kept sorted, so the search descends into the most promising child first (Yao et al., 2023, Fig. 6a) — the heuristic controls the order here, where in ToT-BFS it controls the survivors.

ToT-DFS adds the two things a chain cannot do: prune a state the evaluator calls hopeless ($V \le v_{th}$), trading exploration for exploitation, and backtrack to its parent.

Solution Handling & Yield in ToT-DFS

• Output Collection: Because Line 1 records without returning, ToT-DFS produces a variable candidate set of solutions (bounded theoretically by $k^T$, but kept small in practice via aggressive pruning at $v_{th}$).
• Terminal Selection: After search completes, a single final answer is selected—either via external verification (stopping at the first valid leaf, e.g., in Game of 24) or majority consensus/ranking over all recorded leaf outputs (e.g., in Creative Writing or Crosswords).

What backtracking actually is. Line 4 returns, and line 2 continues with the next sibling — that is the whole mechanism. There is no "undo" operation: DFS gets backtracking for free from the call stack, which is why it costs no LLM call to go back (the state is already stored; what is sunk is the tokens spent in the abandoned subtree).

And that is exactly what a chain cannot have. Backtracking needs the earlier state to still exist somewhere. A generation only ever grows — a token cannot be un-appended — so a chain that goes wrong at step 1 carries its mistake in the context for every step after it. Storing the tree outside the generation is what buys the return. ToT-BFS holds $b$ states simultaneously and pays in frontier memory; ToT-DFS holds them implicitly on the stack and pays by revisiting a parent later — the classical space/revisit trade-off, with LLM calls as the cost unit.

Worked Example — Game of 24¶

Input $x =$ 4 9 10 13; reach $24$ using each number exactly once with $+\;-\;\times\;\div$. One thought is one equation, written together with the numbers it leaves behind, so a state is readable at a glance. Depth $T = 3$, because three binary operations consume four numbers.

Read it as a ToT-DFS trace; the circled numbers are the order in which the lines of the algorithm execute, and the row a node sits in is its depth $t$.

• The root is $s_0 = [x]$ — no thoughts yet. Its three children come from a single propose call $G(p_\theta, s_0, k)$; each appends one equation, so the leftmost child is $[x, z_1]$ with $z_1 = $ 4+9=13. The parenthesised numbers are the state made legible — they are what the next propose prompt is conditioned on.
• A dashed red node was scored and rejected, and the label on its incoming edge says at which line. 4+9=13 (left: 10 13 13) is generated, valued impossible — a short lookahead finds no route to 24 from three numbers that large — and so fails line 3 and is never recursed into: not one generator call is spent inside its subtree. The pruning happens at the node, not on the way out of it.
• A dashed edge pointing back up is the recursion returning, and it costs no LLM call. At 13-10=3 (left: 3 5) two numbers reach only $8$, $2$, $15$ or $3/5$, never $24$; line 4 returns into $B$'s own loop (④), $B$'s remaining candidates fail in the same way, and only then does the recursion return to the root (⑤), which continues with 13-9=4.
• The leaf 4*6=24 ✓ sits at depth $3$ and is checkable exactly. That is what makes Game of 24 the paper's cleanest task: the final verifier is arithmetic, and only the intermediate heuristic is a model's opinion.

Best-First Search over Thoughts¶

Search algorithms differ in a single decision — which node leaves the frontier next — and the classification follows from what that decision is permitted to look at.

• Uninformed search reads only the shape of the tree: depth-first takes the newest node, breadth-first the oldest. Nothing about a node's content enters the choice.
• Best-first search orders the frontier by an evaluation function $f(s)$ and expands the minimum. The frontier becomes a priority queue, and the whole tree competes at once instead of one branch or one level at a time.
• $A^*$ is the instance of best-first with $f(s) = g(s) + h(s)$ — the cost paid to reach $s$ plus an estimate of the cost remaining from it (Hart, Nilsson & Raphael, 1968). It is the algorithm the ToT paper compares itself to, and constructing it over thoughts is what makes the comparison precise.

$A^*$ against Dijkstra¶

Both expand a min-heap; they differ in what they minimise, and therefore in when they may stop.

$A^*$ is Dijkstra plus a bias towards the goal: adding $h$ re-orders the heap so that nodes pointing at the goal come off it earlier, which is why the two coincide at $h \equiv 0$. With an admissible $h$ neither returns a worse path than the other; the saving is entirely in expansions, which over thoughts means the saving is in LLM calls.

The bias is safe only under two conditions on $h$ (Russell & Norvig, 2021, §3.5.2):

• Admissibility — $h(s) \le h^*(s)$ for every $s$, where $h^*(s)$ is the true remaining cost: the estimate never over-states what is left. An optimistic $h$ may misorder the heap and cost work, but it cannot hide the optimum, because a node on an optimal path then satisfies $f(s) \le f^*$ and is extracted before any suboptimal goal.
• Consistency — $h(s) \le \text{Cost}(s,a,s') + h(s')$ for every edge, the triangle inequality, under which $f$ never decreases along a path. Consistency implies admissibility, and it is what makes a node settled the first time it is extracted, so that no node is expanded twice.

Over-estimation is the failure that matters. A single node whose $h$ is too large pushes a genuinely optimal branch behind a worse one, and the search returns the worse one — one node suffices, and the heuristic need not be wrong on average.

The ToT paper explicitly compares itself to this family of classical search:

"Our approach can be treated as a modern rendition of classical search methods … it can be considered as a heuristic search algorithm like $A^$, in which the heuristic at each search node is provided by the LM's self-assessment."* — Yao et al. (2023), §5

ToT-BFS and ToT-DFS as Degenerate Best-First Search¶

Constructing the search over thoughts makes that reading precise. Line 4 of $\textbf{Tree-Search}$ becomes an ExtractMin on a global min-heap ordered by $f(s) = g(s) + h(s)$ — global being the operative word: the heap holds every unexpanded node of the entire tree, so the search may jump between branches, where DFS is confined to one stack frame and BFS to one level.

The heuristic is the easy half: it is the evaluator, $h(s) = 1 - V(p_\theta, S)(s)$ as a first approximation; the type conversion that complement glosses over is taken up below. $g$ is the problem. A thought edge has no given length, so $g$ must be chosen, and the natural choices are the resources the search consumes:

That last row places the two published algorithms. ToT-DFS's "best-valued candidate first" is greedy best-first restricted to one branch, and ToT-BFS is greedy best-first restricted to one level at a time. Both use $h$; neither tracks $g$ — so neither is able to prefer a cheap mediocre state to an expensive promising one, which is the comparison $f = g + h$ exists to make.

The control flow transfers; the optimality proof does not. An LLM judge is neither admissible nor consistent, and it is not even deterministic — re-scoring the same state can return a different number, so $h$ is not a function of the state at all. It has no access to $h^{*}$ either: it scores the plausibility of a piece of text on a scale it invented, unrelated to the number of steps still needed (Hart, Nilsson & Raphael, 1968; Russell & Norvig, 2021, §3.5.2). Best-first search over thoughts is therefore a heuristic that usually helps, never a shortest path.

And before admissibility even comes up, the types do not match. $g$ is minimised; the ToT heuristic is a success likelihood, which is maximised. So $f = g + h$ is not well-formed until $h$ is inverted into a cost — $-\log h_{\text{success}}$ being the principled choice, since it makes the scale additive like $g$. Sharon (2026) makes this the first step of his formalisation.

Monte-Carlo Tree Search over Thoughts¶

Monte-Carlo tree search (MCTS) covers the case none of the algorithms above does: no usable heuristic exists, and the only thing that can be said about a state is what the continuations sampled from it achieve. It estimates the value of a state by sampling one such continuation to a finished outcome — a roll-out — averaging that outcome into every state on the path back to the root, and spending the next sample where the average is either the highest or the least certain. No evaluation function is ever written down: the value of a state is collected rather than designed.

Transferred to thoughts, an expansion samples one further thought, and the roll-out either continues to an answer or asks the evaluator once. What this adds over ToT-BFS and ToT-DFS is a revisable judgement: both score a state once and never correct that score, whereas an average over repeated visits lets evidence found deep in a subtree correct a shallow judgement made earlier. What it costs is breadth — the budget is spent revisiting states instead of generating new ones.

Yao et al. (2023, §3.4) name the method as future work, and it has not become standard. Two of its preconditions fail here. The space branches over sampled text rather than over the legal moves of a game, so any affordable budget covers a vanishing fraction of it; and a half-finished thought has no unambiguous outcome to average — a game ends in a win or a loss, a chain of reasoning ends in whatever the model wrote, so the number a roll-out returns is itself a judgement. DeepSeek-AI (2025) report abandoning the method for exactly these two reasons. That is the diagnosis this lecture reaches from the algorithms' side as well: the heuristic is the hard part, not the algorithm.

Part V — Evidence, Cost and the Evaluator¶

The evaluator limits deliberate search, not the choice of search rule. ToT's own ablations price the mechanisms separately — pruning and backtracking each carry a measurable share of the gain — and the bill for them is 5–100× the tokens of a single chain. The paper's failure cases and the independent measurements then converge on one component: wherever the search underperforms, the evaluator is what is wrong.

One line is missing from every box in this lecture. $\textbf{Tree-Search}$ stops at a goal test and ToT-DFS records a candidate at $t > T$, but neither ends the run on having found a solution: ToT-BFS walks $T$ levels, ToT-DFS exhausts its unpruned candidates. The stopping rule belongs to the instance, and this part closes by putting it there.

The Tasks and Benchmarks¶

This part draws on seven tasks — the three designed for the Tree-of-Thoughts paper, and four taken from the existing literature:

The first three are the paper's own, chosen because GPT-4 fails at them with straight prompting. The remaining four are where the evaluator rather than the search is measured: GSM8K and StrategyQA in Yao et al. (2023), and Spider, Bird and GSM8K in Chen et al. (2024).

Task Results and Search Ablations¶

Game of 24 — three thought steps, one equation each; a propose prompt as the generator, ToT-BFS as the search algorithm, and a value prompt returning sure / maybe / impossible, sampled 3× per state, as the evaluator:

~60 % of the CoT samples had already failed after their first step — after roughly three words, e.g. "4 + 9". Nothing in a left-to-right decoder notices, and nothing can go back.

5×5 crosswords (DFS, up to 10 steps) supplies the ablation that isolates which part pays:

What the ablation isolates is the ability to un-commit. Take backtracking away — the same generator, the same evaluator, just no return to a parent — and DFS is back near CoT. Breadth does the same job in the other algorithm: ToT-BFS never backtracks, it simply keeps $b$ states alive at once, which is why $b=5$ beats $b=1$ by 29 points. Holding alternatives is the point; simultaneously (BFS) and on the stack (DFS) are two ways to pay for it. What never works is committing to the first step and hoping.

Costs and Failure Modes of Deliberate Search¶

Yao et al. (2023) are unusually explicit about the bill, and about where their own heuristic breaks.

• 5–100× the generated tokens of CoT. Game of 24: $0.74 per case for ToT vs $0.47 for best-of-100 CoT and $0.13 for best-of-100 IO — ToT wins on quality (74 % vs 49 %) at ~1.6× the money of the strongest sampling baseline, not for free.
• The evaluator prunes correct states. In crosswords it sometimes declares a solved board impossible, because a 5×5 grid contains rare words ("agend") the model reads as typos — three games solvable without pruning become unreachable with it. Pruning still wins on average.
• The output heuristic is lossy too. The search visits many states, and one of them has to be chosen to answer from; ToT leaves that choice to the same evaluator. Giving it instead to an oracle — the ground truth selecting the best of the states the search actually visited — lifts the crosswords games solved from 4/20 to 7/20: three of the twenty had a solved board somewhere in the tree that the evaluator declined to return.
• Unnecessary where CoT already works. A generic zero-shot ToT-BFS — sample five strategies, vote, sample five solutions, vote — moves GSM8K 86 → 90 and StrategyQA 82 → 83, and the bottleneck of the latter is external knowledge, not reasoning.
• Which half is the bottleneck is a per-task question. On Game of 24, GPT-4 generating with GPT-3.5 evaluating scores 64 %; GPT-3.5 generating with GPT-4 evaluating scores 31 %. Here generation limits the system — so the cheap model belongs in the evaluator.

The rule the authors give. Use deliberate search on tasks that require it and on which CoT struggles. Everywhere else it is an expensive way to get the same answer.

Evaluator Quality as the Limiting Factor¶

Every algorithm this week — ToT-BFS's beam, ToT-DFS's threshold, $A^*$'s $h$, MCTS's roll-out value — assumes a cheap, trustworthy evaluation of a partial solution. That assumption, and not the choice of search rule, is the weak point:

• Scoring a partial step is ill-posed. "It is challenging to explicitly define a fine-grain step in general reasoning" (DeepSeek-AI, 2025) — outside narrow domains it is unclear what unit the judge should even be scoring.
• A model-based scorer is optimised against rather than obeyed. A process reward model (PRM) is a scorer trained to grade a single reasoning step — the trained counterpart of an LLM judge scoring a branch. Because the search maximises whatever the scorer returns, it finds the states the scorer mis-grades: "once a model-based PRM is introduced, it inevitably leads to reward hacking" (DeepSeek-AI, 2025), that is, to raising the judge's number without solving the task. What the search then optimises is the judge's flaws instead of the problem — an instance of the LLM-as-a-judge caveat.
• ToT's own evaluator prunes solved boards — the crosswords failure on the previous slide is this same point, measured.

So: where a deterministic, cheap check exists (tests pass, a proof checks, the game is won), search over thoughts works well and is worth its cost. Where the only scorer is a model judging a half-finished thought, expect much less — and measure it rather than assuming it.

The Discrimination-Accuracy Threshold¶

That claim has been measured. Chen et al. (2024) factor a language agent into a generator, a discriminator and a planning method, freeze the generator, and vary only the discriminator — sweeping its accuracy by corrupting an oracle on purpose: compute the true score by executing the candidate, and return it with probability $\tau$, the inverted score otherwise.

Their baseline is re-ranking, the method that does not search: sample $k$ complete candidate solutions, score each finished candidate once, and return the best-scored one. It evaluates no partial state and revises no decision, and it is the bar tree search has to clear.

Re-ranking improves linearly in $\tau$ throughout; the sophisticated methods commit to a highly-scored branch, so a wrong score is propagated rather than averaged away — which is why their ranking inverts as the evaluator degrades. And no LLM discriminator tested clears the bar. Pairwise discrimination accuracy — the share of (correct, incorrect) candidate pairs in which the correct candidate is given the higher score, so that 50 % is chance — reads, on the two text-to-SQL benchmarks and the mathematics one: CodeLlama-13B 58.2 / 49.4 / 62.2, GPT-3.5-Turbo 67.0 / 64.3 / 72.1, GPT-4-Turbo 76.5 / 76.2 / 93.8 (Spider / Bird / GSM8K respectively).

The rule this hands you. Before building a search or a refinement loop, measure the scorer you plan to put inside it: below ~90 % pairwise accuracy the loop is expected to be worse than sampling a handful of candidates and keeping the best-scored one, and much more expensive. The fix is not a bigger model but a grounded one — refusing to score a program that does not run and putting its execution result into the scorer's prompt moves discrimination accuracy by +25.4 (Spider), +30.2 (Bird) and +8.4 (GSM8K), enough for a 13B open-weight scorer to beat naive GPT-4. Grounding the judge bought more than ten times the model did.

Adaptive Stopping: a Per-Instance Search Budget¶

Every procedure this week spends a constant: ToT-BFS runs $T$ levels keeping $b$ states, ToT-DFS recurses to depth $T$, the crosswords search caps itself at 100 steps, self-consistency draws a fixed $k$ chains. A constant is wrong in both directions at once — it overspends on the instance that was easy and gives up on the one that needed more — and which kind an instance is is not known before the run starts.

The alternative is to let the evaluator decide when the run is over. Liang et al. (2024) measure that in a two-agent debate whose judge is asked after every round whether a solution has been reached (an adaptive break): forcing an answer at a fixed round is worse at every value of that round, most instances finish after one, and the ones consuming more are measurably the harder ones.

So the budget is a variable the evaluator sets per instance, not a hyper-parameter tuned once over a benchmark. ToT owns half the machinery already — $v_{th}$ is a stopping rule for a branch; what the pseudocode has no line for is a stopping rule for the run. Webb et al. (2025) price that omission, justifying a dedicated goal-test module against a ToT baseline that "was able to solve each of the … problems on at least one attempt … but was not able to do so reliably", because it "had no method for reliably determining when a goal had been achieved." Best-of-$k$ that cannot recognise its own success is a sampler, not a search: the answer is in the tree and the procedure walks past it.

Part VI — Beyond the Tree¶

A tree node has one parent, so branches can be compared and abandoned but never combined. Graph-of-Thoughts lifts that restriction and models reasoning as an arbitrary directed graph — at the price of the search itself: the graph is written down in advance rather than explored.

Graph-of-Thoughts¶

Graph-of-Thoughts (Besta et al., 2024) takes the last structural step: drop the tree and model reasoning as an arbitrary directed graph. A thought is a vertex; an edge $(t_1, t_2)$ means $t_2$ was produced with $t_1$ in its prompt — "by explicitly instructing the LLM to use $t_1$ for generating $t_2$" (§3.1). A reasoning step is then a graph rewrite: it adds vertices and edges (and may delete some, to free context). Three of them; only the first needs a shape a tree cannot draw:

In-degree is the whole argument. A tree node has one parent, so ToT can compare branches and abandon them — but never combine two. A partial result computed in one branch is unreachable from every other, and backtracking discards the work instead of reusing it. Aggregation keeps it. That is the same DAG vocabulary as a task-decomposition plan graph, now over thoughts rather than tasks.

The Graph of Operations¶

The graph is not searched — it is written down in advance. The user authors a static Graph of Operations (GoO) — which transformations apply to which thoughts, in what order — and execution keeps a Graph Reasoning State, the thoughts so far with their validity and scores, which a controller walks (Generate, Aggregate, Score, Validate, KeepBest, Repeat). The paper's worked example is merge sort over digits the model cannot sort in one pass: split the input into blocks, sort each one ($k$ candidates, scored, KeepBest(1)), then merge the sorted blocks pairwise by Aggregate. The LLM does the comparisons; merge sort supplies the control flow — KeepBest prunes inside a fixed plan, it does not decide where to look next. GoT therefore sits outside the search family this week is about: a plan DAG with an LLM in each node, with no backtracking, since a bad subresult is merged upward.

Why the graph pays, argued graph-theoretically rather than by benchmark. The volume of a thought $t$ is the number of thoughts with a directed path to $t$ — how much of the reasoning could have influenced it — and its latency is the number of hops to the final thought. At a fixed budget of $\Theta(N)$ thoughts:

Branching bought ToT depth in parallel, but a leaf's ancestry is only its own root-path, so most of the work done in the tree cannot reach the answer; GoT's second half is a reduction tree, in which every intermediate thought has a path to the final one. Measured on sorting 128 digits: median error ≈62 % below ToT at >31 % lower cost.

Where this leaves the ladder. IO → CoT → CoT-SC → ToT adds breadth and a verifier; GoT adds reuse — and pays for it by giving up search. Choose by the task: a fixed decomposition you can name in advance is a GoO; a space you must explore is a tree.

Part VII — Deliberation in the Harness¶

Where the deliberation lives is an architectural decision rather than a prompting one. Search can sit in the runtime, as an explicit tree the harness expands, or in the weights, as a habit trained into a reasoning model. Read that way the course's three planning paradigms — ReAct, plan-then-execute and deliberate search — are one control structure with three fillings, and what distinguishes them is who decides and what stops the loop.

Search in the Runtime vs. Search in the Weights¶

ToT and MCTS put the search in the runtime: an explicit tree, expanded by an algorithm, backtracking by returning to a stored node. Today's reasoning models put it in the weights: RL against an outcome reward produces one long chain of thought that checks and corrects itself, backtracking in text — no tree, no value model, one generation. Same word, different machinery. Every technique this course teaches as a prompt has made that migration — chain of thought, self-consistency, reflection, tool calling — which relocates the bug: a bad chain in the prompt is a harness problem, a bad chain in the weights is a model-selection problem (→ L-Eval).

Which part of the runtime. Runtime here is the agent architecture of → L-Intro, which deliberate search leaves unchanged. That architecture is the common shape of an agent runtime and not a law — a simple agent discharges several of its duties in one place — but wherever the components are separate, the placement is this: the search algorithm and the tree of states are data structures of Agent Control, and the model is called twice per node in two roles — as the generator $G$ and as the evaluator $V$. The tool gateway still executes every tool and is still the security boundary (→ L-Gateway). Nothing architectural distinguishes a ToT agent from the ReAct loop; what moved is where the deliberation lives — out of the model's context, through a plan object in the agent loop, to a search procedure in the agent loop.

Planning Paradigms¶

The agent loop is a control structure, not a reasoning method. Written with the deliberation factored out, it commits to nothing — it is the classical agent program of Russell & Norvig (2021, §2.4), a persistent state updated from percepts with one action selected per cycle (see L-Intro):

$$ \begin{array}{l} \textbf{Agent-Loop}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; a runtime providing the tools; a step budget } B \\ \textbf{Output: } \text{the result} \\ \hline 1: \quad \textit{state} \gets \text{Init}(\textit{goal}) \\ 2: \quad \textbf{while } \neg\,\text{Done}(\textit{state}) \textbf{ and } \text{steps} < B \textbf{ do} \\ 3: \quad \qquad a \gets \text{Decide}(\textit{state}) \qquad \text{// the only line a strategy changes} \\ 4: \quad \qquad o \gets \text{Execute}(a) \qquad \text{// the runtime acts; the model never does} \\ 5: \quad \qquad \textit{state} \gets \text{Update}(\textit{state}, a, o) \\ 6: \quad \textbf{return } \text{Result}(\textit{state}) \\ \hline \end{array} $$

Three names carry everything a paradigm decides: what state is, how Decide picks, and what makes Done true. The picture and the table below fill them in — same loop, three strategies.

The three paradigms as one picture. The skeleton is the same in all three — decide, execute, update, test for termination; what differs is who decides and what stops the loop.

Only (c) has more than one state alive at the top of its loop; (a) and (b) carry a single committed trace through theirs. The diamond is where they differ again: in (a) the model decides it, in (b) and (c) the runtime does — a counter against $N$ resp. $T$.

Reading the Three Loops¶

The first three rows are the skeleton's three slots — state, Decide, Done:

Two rows carry the whole lecture arc. Decide moves out of the model and into the harness, one week at a time — from a turn of generation (a), to a data structure (b), to a search procedure (c). And can un-commit is the capability none of the earlier weeks had: (a) cannot un-append a token, (b) can only throw the plan away and write a new one.

Choosing a Paradigm¶

• Implicit planning — ReAct (Yao et al., ReAct, 2023). Interleaved thought, action, observation in one loop; the next step is chosen from the latest observation. Use when the environment is uncertain and the steps cannot be known in advance. Costs: compounding errors, loops, and drift away from the global goal on long horizons.
• Explicit plan generation — plan-then-execute (least-to-most, Zhou et al., 2023). A complete plan — a list, or a DAG whose edges are dependencies — is produced before any tool call. Use when the structure is knowable up front and the horizon is long: the plan is inspectable, schedulable and approvable. Costs: a loss on short tasks, stale at the first contradicting observation, and only as good as the decomposition.
• Search-based planning — ToT / MCTS (this week). Several candidate steps exist at once, are scored by a heuristic, and one is committed to reversibly. Use when the first path taken is often wrong and progress can be evaluated part-way — puzzles, proofs, code with tests. Costs: 5–100× the tokens of a chain, and only as good as the evaluator.

The decision rule is the same one as for decomposition. Autonomy is not a virtue: if the how is already known, fix the workflow; if it must be discovered, ask how expensive a wrong step is. Search is what you buy when a wrong step is expensive and detectable — never the default.

In Practice / This Week's Lab¶

lecture-ToT-exercises.ipynb — by hand: trace ToT-BFS and ToT-DFS (pruning, backtracking, the threshold), break $A^*$'s optimality with an inadmissible LLM heuristic, choose a generator and an evaluator per task, and compute the cost per solved task.

lecture-ToT-lab.ipynb: build a ToT explorer from scratch — a propose prompt, a value prompt, and ToT-BFS over the states — then add a refinement step and a producer–critic loop as the third thought generator.

Summary¶

• The ladder. IO → CoT → CoT-SC → ToT, each rung added to fix the one below. CoT bridges $x$ to $y$ with thoughts $z_i$ but leaves their decomposition ambiguous; CoT-SC adds breadth at the root only and votes, which needs a small output space. ToT fixes the decomposition, branches at every step, and replaces the vote with a score on a partial state.
• The framework. A state $s = [x, z_{1\cdots i}]$; four design choices — decomposition, generator $G(p_\theta,s,k)$ (i.i.d. vs. propose), evaluator $V(p_\theta,S)$ (value vs. vote), and the search algorithm (Yao et al., 2023). IO, CoT, CoT-SC and self-refine are degenerate cases — the tree collapsed in depth or in breadth.
• The search is the classical one. A search problem is $(s_0, \text{Actions}, \text{Result}, \text{IsGoal}, \text{Cost})$ whose state space is generated on demand, and a single line of $\textbf{Tree-Search}$ — which state leaves the frontier — decides whether it is BFS, DFS or best-first (Russell & Norvig, 2021). ToT replaces the successor function by an LLM generator and the heuristic by an LLM evaluator; the control structure is untouched. ToT-BFS is beam search with an LLM scorer, ToT-DFS adds threshold pruning and backtracking, and best-first is $f = g + h$ with a $g$ that must be chosen — but $h$ is neither admissible, nor consistent, nor even deterministic, so the control flow transfers and the optimality theorem does not.
• What search buys is the ability to un-commit — held on the stack (DFS backtracking) or in the frontier (BFS breadth). Remove backtracking from ToT's crosswords run and word success falls 60 % → 20 %; remove pruning and it falls to 41.5 %. In Game of 24, ToT scores 74 % where CoT scores 4 % — and ~60 % of CoT samples are already dead after their first step. A chain can do neither: its context only grows, so a wrong first step is carried to the end.
• Search quality = verifier quality, and where the verifier sits is the axis behind candidate selection: at every node (tree search), at the end (best-of-$N$), or nowhere (self-consistency) — cost and exposure rising in that order. ToT's own evaluator prunes solved boards; model-based step-scorers get reward-hacked (DeepSeek-AI, 2025); below ~90 % pairwise discrimination accuracy the advanced planners lose to plain re-ranking, and grounding the judge in an execution result buys more than a larger model does (Chen et al., 2024).
• It costs 5–100× CoT's tokens, so it is for tasks that need deliberate reasoning and on which CoT struggles — never a default. And a search needs three things where the pseudocode supplies two: a way to produce candidates, a way to rank them, and a way to stop — the budget belonging to the instance, set by the evaluator.
• Graph-of-Thoughts drops the tree (Besta et al., 2024): thoughts as an arbitrary DAG, whose new transformation is aggregation — in-degree > 1, merging thoughts or whole chains, which a tree cannot express (a leaf's ancestry — its volume — is $O(\log_k N)$ against $N$). The price is that the graph is a hand-written Graph of Operations, not a searched frontier.
• One loop, three fillings. The agent loop is a control structure — state, Decide, Execute, Update, Done (Russell & Norvig, 2021, §2.4) — and ReAct, plan-then-execute (least-to-most, Zhou et al., 2023) and deliberate search differ only in the first three. Decide migrates out of the model and into the harness: a turn of generation, then a data structure, then a search procedure. Only search can un-commit a step.
• Awareness: search can live in the runtime (an explicit tree) or in the weights (RL-trained reasoning models that backtrack in text) — same word, different machinery (→ L-Outlook).

References¶

Peer-reviewed papers

• Besta, Maciej, et al. "Graph of Thoughts: Solving Elaborate Problems with Large Language Models." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 2024. arXiv:2308.09687. — thoughts as an arbitrary graph: the three transformations (aggregation, refining, generation) in §3, the Graph of Operations / Graph Reasoning State architecture in §4, the merge-sort decomposition in §5.1, the volume vs. latency table in §6, and the decomposition rule in §7.3.
• Chen, Ziru, et al. "When is Tree Search Useful for LLM Planning? It Depends on the Discriminator." Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024, pp. 13659–13678. — the generator / discriminator / planning-method factorisation, the oracle-corrupted sweep of discrimination accuracy $\tau$ and the ~90 % threshold, the intrinsic accuracies of real LLM discriminators, and the executability-check and execution-result enhancement (+30.2 on Bird).
• Fedrushkov, Dmitriy, et al. "Beam Search for Improvement of Code Generation in Answering Programming Questions with Code." Parallel Computational Technologies. Communications in Computer and Information Science, Vol. 2241. Springer, 2024, pp. 194–208. doi:10.1007/978-3-031-73372-7_14. — beam search against greedy search on HumanEval-X; parsing search.
• Hart, Peter E., et al. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968, pp. 100–107. — $A^*$, $f = g + h$, and the admissibility condition an LLM judge does not satisfy.
• Kocsis, Levente, and Csaba Szepesvári. "Bandit Based Monte-Carlo Planning." European Conference on Machine Learning. Vol. 4212. 2006, pp. 282–293. — UCT: one bandit per internal node, the drift of payoffs inside a growing tree that makes UCB1's i.i.d. analysis inapplicable, and Thm. 6's $O(\log n / n)$ bias for a finite-horizon MDP with a generative model.
• Kojima, Takeshi, et al. "Large Language Models are Zero-Shot Reasoners." Advances in Neural Information Processing Systems. Vol. 35. 2022. arXiv:2205.11916. — the zero-shot trigger, and that it is a two-stage pipeline (reasoning extraction, then answer extraction); Tab. 2's comparison with few-shot CoT and Tab. 4's template ablation, in which a truncated trigger costs 21 points and a misleading one falls below the no-trigger baseline.
• Liang, Tian, et al. "Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate." Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. Vol. 2024. 2024, pp. 17889–17904. arXiv:2305.19118. — the adaptive break: a judge deciding each round whether to stop beats every fixed round count, most instances finish in one round, and the harder ones consume more.
• Madaan, Aman, et al. "Self-Refine: Iterative Refinement with Self-Feedback." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2303.17651. (Further reading — refinement as a thought generator.)
• Merrill, William, and Ashish Sabharwal. "The Expressive Power of Transformers with Chain of Thought." International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2310.07923. And: Merrill, William, and Ashish Sabharwal. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." Transactions of the Association for Computational Linguistics, vol. 11, 2023. arXiv:2207.00729. — chain length as serial computation, distinct from search breadth.
• Newell, Allen, et al. "Report on a General Problem Solving Program." Proceedings of the International Conference on Information Processing. UNESCO, 1959. — the epigraph ToT opens §3 with.
• Sharon, Guni. "Tree of Thoughts as a Classical Heuristic Search Problem: Formal Foundations and Design Patterns." International Symposium on Combinatorial Search. Vol. 19. 2026. arXiv:2605.28566. — the formalisation of ToT as a $(s_0, O, G)$ search problem, and in particular the $h_{\text{success}}$ vs. $h_{\text{cost}}$ type distinction that $f = g + h$ needs before admissibility can even be discussed. (The rest of the formalisation — proposal mechanisms, pruning rules, the $g$/$h$ taxonomies and the design patterns read off twelve published systems — is in the extensions companion.)
• Shinn, Noah, et al. "Reflexion: Language Agents with Verbal Reinforcement Learning." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2303.11366. (Further reading — refinement as a thought generator.)
• Turpin, Miles, et al. "Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.04388. — high agreement is compatible with a shared bias, so a majority vote is evidence about the answer and not about the narration.
• Wang, Xuezhi, et al. "Self-Consistency Improves Chain of Thought Reasoning in Language Models." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2203.11171. — CoT-SC: $k$ i.i.d. chains and a majority vote; the reasoning path as a marginalised latent variable; Tab. 1's aggregation ablation and fn. 2 on calibration.
• Webb, Taylor, et al. "A brain-inspired agentic architecture to improve planning with LLMs." Nature Communications, vol. 16, 2025, p. 8633. — the ToT comparison this week takes from it: a baseline that solves problems "on at least one attempt" but not reliably, for want of a test that a goal has been reached.
• Wei, Jason, et al. "Chain-of-Thought Prompting Elicits Reasoning in Large Language Models." Advances in Neural Information Processing Systems. Vol. 35. 2022. arXiv:2201.11903. — the chain $z_1,\dots,z_n$ bridging $x$ and $y$, whose decomposition ToT makes explicit; the four-way ablation and the emergence threshold.
• Yao, Shunyu, et al. "ReAct: Synergizing Reasoning and Acting in Language Models." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2210.03629. — the just-in-time loop of paradigm (a): one candidate per turn, committed immediately.
• Yao, Shunyu, et al. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.10601. — the primary source for this week: the IO/CoT/CoT-SC formalisation (§2), the four design questions and ToT-BFS / ToT-DFS (§3), the Game-of-24 / creative-writing / crosswords results and ablations (§4), and the reading of ToT as $A^*$-like heuristic search (§5).
• Zhang, Shun, et al. "Planning with Large Language Models for Code Generation." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2303.05510. — PG-TD; beam search against sampling with test filtering at an equal budget.
• Zhou, Denny, et al. "Least-to-Most Prompting Enables Complex Reasoning in Large Language Models." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2205.10625. — paradigm (b), the multi-call form: decompose in one call, then solve each subproblem in its own call with the previous answers in the prompt.

Preprints & other non-peer-reviewed papers

• Chan, Brian J., et al. "Efficient Beam Search for LLMs Using Trie-Based Decoding." arXiv preprint arXiv:2502.00085 (2025). — one shared key–value cache for all beams; beam against greedy search on HumanEval.
• Cobbe, Karl, et al. "Training Verifiers to Solve Math Word Problems." arXiv preprint arXiv:2110.14168 (2021). — the trained verifier / re-ranker that best-of-$N$ needs, and the baseline self-consistency dispenses with.
• DeepSeek-AI, et al. "DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning." arXiv preprint arXiv:2501.12948 (2025). §Unsuccessful Attempts. — why MCTS and process reward models were abandoned: token-space branching, a value model that is hard to train, and reward hacking. (A negative result from one lab at one time — not proof that search over thoughts cannot work.)
• Kumar, Aviral, et al. "Training Language Models to Self-Correct via Reinforcement Learning." arXiv preprint arXiv:2409.12917 (2024). (Further reading — refinement as a thought generator.)
• Li, Jiwei, and Dan Jurafsky. "Mutual Information and Diverse Decoding Improve Neural Machine Translation." arXiv preprint arXiv:1601.00372 (2016). — beam search yields low output diversity, which is why sampling beats it as a candidate generator.

Textbooks & monographs

• Gulli, Antonio. Agentic Design Patterns, Ch. 4 — Reflection. Springer Nature, 2025. (Further reading — refinement as a thought generator.)
• Kahneman, Daniel. Thinking, Fast and Slow. Macmillan, 2011. — System 1 / System 2: the dual-process framing ToT adopts; token-level decoding as the associative mode, deliberate search as the reflective one.
• Newell, Allen, and Herbert A. Simon. Human Problem Solving. Prentice-Hall, 1972. — problem solving as search through a combinatorial problem space; the tree ToT borrows.
• Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach. 4th ed., Pearson, 2021. — §3.1 the five parts of a search problem and the state space it defines; §§3.3–3.5 the frontier, the generic search loop and what the removal strategy makes of it (breadth-first, depth-first, uniform-cost, $A^*$), including admissibility and consistency; §2.4 the structure of agents — the agent program as a persistent state updated from percepts, one action selected per cycle, which is the deliberation-free skeleton of Planning Paradigms; §3.5.5 beam search as memory-bounded search; §25.3.2 beam search for sequence decoding and the greedy-search failure; §1.1.5 the value alignment problem; §16.1 the MDP as a stochastic generalisation of the search problem and §16.4 the POMDP and its sensor model (Global Edition; US edition §§17.1, 17.4).
• Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd ed., MIT Press, 2018. — §§3.1–3.5: the agent–environment interface, the trajectory, the reward, the return and the value of a policy.