Reasoning Strategies: Self-Consistency, Tree of Thought

Chain of thought prompting, which we explored in the previous chapter, teaches language models to work through problems step by step. But chain of thought is just one approach in a broader set of reasoning strategies. Researchers have developed a family of techniques that address different failure modes: when a single reasoning path leads to the wrong answer, when problems need to be broken into sub-problems, or when complex tasks require systematic search through possible approaches.

This chapter covers four major reasoning strategies: self-consistency, tree of thought, least-to-most prompting, and decomposition strategies more broadly. Each addresses a distinct limitation of naive prompting and offers a different intuition about what "good reasoning" means for language models. Together, they represent the current state of the art in eliciting reliable, accurate reasoning from large language models without any additional training.

Understanding why these strategies work requires revisiting a fundamental property of language models: they are stochastic text generators. Given the same prompt, a model can produce different outputs depending on its sampling temperature. This stochasticity, which looks like a bug, turns out to be a feature. If you sample multiple completions from a model, you get diverse reasoning paths, and those paths contain different errors. The strategies in this chapter exploit that diversity in complementary ways.

The simplest chain of thought prompting generates one reasoning path and returns its answer. This is brittle. A single path can go wrong at any step, and there is no mechanism to detect or correct errors. Self-consistency fixes this by sampling many reasoning paths and selecting the most common answer.

The core intuition is straightforward: if you ask a human to solve a math problem and they get the same answer by three different methods, you should trust that answer more than an answer reached by only one method. Self-consistency applies this logic at scale. It does not require the model to become more accurate on any individual reasoning attempt; it requires only that correct answers cluster while errors scatter.

Self-consistency, introduced by Wang et al. (2022), replaces greedy decoding with a sample-then-aggregate approach. The procedure is:

1. Given a problem, sample $N$ diverse reasoning paths from the language model using temperature sampling (typically $T = 0.7$)
2. Extract the final answer from each reasoning path
3. Return the answer that appears most frequently across all $N$ paths

The key insight is that diverse reasoning paths tend to agree on correct answers and disagree on incorrect ones. Errors are idiosyncratic: one path might make an arithmetic mistake, another might misinterpret a condition, but correct answers tend to converge. Each error has its own unique signature. The correct answer, by contrast, has only one form: it is whatever the problem demands.

Formally, if $f(\mathbf{x})$ denotes the language model and $a_i$ is the answer extracted from the $i$-th sampled path, the self-consistent answer is:

where:

• $a^*$: the final answer returned by self-consistency
• $N$: the number of sampled reasoning paths
• $a_i$: the answer extracted from the $i$-th reasoning path
• $\mathbf{1}[a_i = a]$: an indicator function equal to 1 when the $i$-th answer matches candidate $a$

This is majority voting over answers, not over full reasoning paths. Two paths that reach the same answer by completely different routes both contribute to that answer's vote count. This is an important design choice: voting over full paths would require comparing free-form text, which is fragile and slow. Voting over extracted answers is simple and robust, provided the answers can be normalized into a canonical form.

The effectiveness of self-consistency rests on a probabilistic argument. Assume that the language model assigns higher probability to correct reasoning steps than to incorrect ones, but that this probability is not 1. Then a single path will occasionally err. Over $N$ paths, errors are distributed randomly across many possible wrong answers, while correct answers concentrate in one place.

The voting step exploits this asymmetry. If the correct answer $a^*$ appears in fraction $p$ of paths, and all wrong answers are distinct, the correct answer wins as long as $p > 1/k$ where $k$ is the number of distinct wrong answers. In practice, $k$ is large and diverse, so even modest $p$ (say 0.4) suffices for the correct answer to win the plurality.

This argument illustrates why the diversity of wrong answers matters as much as the accuracy of individual paths. If the model tends to make the same systematic error over and over, wrong answers will cluster just as strongly as correct ones, and voting will not help. The strategy works because language model errors tend to be distributed across many different wrong values, not concentrated on one wrong answer.

To see why errors scatter, consider what happens when a model makes a mistake in a multi-step arithmetic problem. In step 2 of 5, the model might misread "twice as many" as "half as many." The downstream arithmetic in steps 3 through 5 will then produce a wrong final answer, but one that is arithmetically consistent with the mistaken premise. A different error, misreading "5 fewer" as "5 more" in the same step 2, produces a different wrong answer through a different downstream chain. These two errors generate numerically distinct wrong answers that split the vote, while the correct reasoning path concentrates votes on the true answer.

Empirically, Wang et al. showed dramatic gains. On the GSM8K benchmark, chain of thought prompting with a 540B parameter model achieved 56.5% accuracy. Self-consistency with 40 samples raised this to 74.4%, an 18-point improvement, without any additional training. The gains were even larger on harder benchmarks, suggesting that the harder the problem, the more individual paths err, and the more aggregation helps.

Self-consistency trades compute for accuracy. Sampling 40 reasoning paths costs 40 times as much as sampling one, which is prohibitive in latency-sensitive applications. For a model that takes 2 seconds to generate a reasoning path, self-consistency with 40 samples takes 80 seconds, not 2. This is acceptable in asynchronous batch settings but unacceptable in interactive applications.

Several practical considerations govern the deployment of self-consistency:

• Number of samples: Gains plateau around $N = 20$ to $40$ for most tasks. Sampling more than 40 paths yields diminishing returns because the aggregate vote has already converged.
• Temperature: Use $T = 0.7$ to $T = 1.0$ for diversity. Greedy decoding ($T = 0$) produces nearly identical paths and defeats the purpose. If all paths are the same, you get zero benefit from voting.
• Answer extraction: The aggregation step requires extracting structured answers from free-form text. For math problems, this usually means finding numbers; for multiple-choice problems, it means finding a letter. Inconsistent extraction errors propagate directly to accuracy, so robust extraction is critical.
• When to use it: Self-consistency helps most on tasks with verifiable answers (math, logic, coding) where the model's reasoning is uncertain. It helps less on open-ended generation tasks where answers are not comparable, because there is no well-defined way to vote over free-form text.

One refinement is weighted self-consistency, where each reasoning path is weighted by the model's log-probability rather than counted equally. Paths the model is more confident about contribute more to the final vote. This can help when some paths are clearly stronger than others, but the improvement over uniform voting is often modest in practice.

Understanding when self-consistency breaks down is as important as understanding when it works. The strategy can fail in three ways.

First, if the model has a strong systematic bias toward a particular wrong answer, errors will concentrate rather than scatter. This can happen when a problem has a common confounding factor: a unit conversion error that most paths make, or a conditional that most paths misread. In these cases, the wrong answer wins the vote because it appears in more than half the paths. Self-consistency amplifies the model's biases rather than correcting them.

Second, if the problem requires rare or specialized knowledge that the model barely has, nearly all paths will produce wrong answers from different corners of the wrong-answer space. The correct answer may appear in very few paths, and some wrong answer will win by plurality. More samples help, but if the underlying per-path accuracy is very low (say, 10%), you would need hundreds of samples for reliable majority voting.

Third, answer extraction can become a bottleneck. For problems where the final answer is embedded in long reasoning text, inconsistent extraction can corrupt the vote. Two paths that arrive at the same numerical answer but express it differently ("\115$" vs "115 dollars") might count as different answers. Preprocessing to normalize answer formats is critical for reliable self-consistency.

Self-consistency improves accuracy by aggregating multiple complete reasoning paths. But it does not change how each path is generated: the model still reasons linearly, one token at a time, without backtracking. Tree of Thought (ToT), introduced by Yao et al. (2023), goes further by enabling explicit exploration of the search space.

The key insight is that expert human problem-solving is rarely linear. A chess player considers candidate moves, evaluates them, abandons bad ones, and backtracks. A mathematician tries a proof approach, gets stuck, and switches strategies. A programmer writes code, runs it, sees it fail, and revises the approach. All of these involve generating options, evaluating their promise, and pruning unpromising directions before committing to them. Standard chain of thought gives language models none of this infrastructure. Tree of Thought gives them an analogous ability to explore, evaluate, and backtrack.

The analogy to tree search from classical AI is intentional and deliberate. In game-playing AI like AlphaGo, a tree search algorithm evaluates candidate moves many steps ahead, prunes branches that look unpromising, and commits to the best-looking sequence. Tree of Thought applies the same architecture to open-ended language reasoning, but with the language model serving dual roles: as the generator that proposes candidate thoughts, and as the evaluator that scores their promise.

Tree of Thought treats the reasoning process as a tree search where each node is a "thought": a coherent unit of reasoning that represents an intermediate step toward a solution.

The first design decision is what counts as a thought. This depends on the problem:

• For mathematical word problems, a thought might be one equation or one inference step
• For writing tasks, a thought might be an outline point or a paragraph plan
• For puzzle solving, a thought might be the state after applying one rule

The key property is that a thought should be small enough to generate many candidates, but large enough to represent meaningful progress. Sentence-level thoughts work well for most language reasoning tasks. If thoughts are too fine-grained (single words), the branching factor becomes astronomically large and the search collapses under its own cost. If thoughts are too coarse (entire solution attempts), there is no room for the search to discover that a partial solution looks promising and deserves further exploration.

The granularity of thoughts defines the shape of the search space. Choosing well requires understanding the problem structure. For a math puzzle like Game of 24, where you combine four numbers using arithmetic operations, a thought might be one operation: "I'll multiply 3 and 4 to get 12." For a creative writing task, a thought might be one structural decision: "The story will open with the protagonist discovering the key." In both cases, the thought is specific enough to evaluate, general enough to leave multiple continuations open, and small enough to generate quickly.

Given a problem and a sequence of thoughts $t_1, t_2, \ldots, t_k$, the model can:

1. Generate: Produce $b$ candidate next thoughts from the current state
2. Evaluate: Score each candidate thought for how promising it looks
3. Search: Apply a search algorithm (breadth-first or depth-first) to navigate the tree

The evaluation step is what separates Tree of Thought from simple beam search. Rather than using the model's probability as the score, ToT uses the language model itself as a deliberate evaluator. The evaluator is prompted to assess whether a partial solution looks promising, typically producing a rating like "sure", "maybe", or "impossible". This prompting approach lets the evaluator reason about promise in a task-specific way, rather than just computing token probabilities.

Formally, let $s = (x, t_1, \ldots, t_k)$ be the current state: the original input $x$ plus $k$ thoughts taken so far. The tree is explored according to:

where:

• $V(p_\theta, s)$: the value function, which prompts the language model $p_\theta$ to evaluate state $s$
• $G(p_\theta, s, b)$: the generation function, which samples $b$ candidate thoughts from $p_\theta$ at state $s$
• $b$: the branching factor (number of candidates to generate at each node)

This formulation separates deliberate thinking (the evaluator) from creative generation (the generator), and both are implemented by the same underlying language model through different prompts. The generator is prompted to be creative and diverse. The evaluator is prompted to be analytical and critical. This dual-role architecture mirrors how expert problem-solvers think: generating ideas freely, then subjecting them to critical scrutiny.

Two search strategies apply naturally to the ToT framework:

Breadth-first search (BFS) maintains a frontier of $k$ most promising states at each tree depth. At each step, it generates $b$ children from each frontier state, evaluates all of them, and prunes to keep only the best $k$. BFS is appropriate when the search space is wide and you want to explore many partial solutions before committing. It guarantees that the retained frontier always contains the most promising options seen so far at each depth level.

Depth-first search (DFS) explores one path as deep as possible, then backtracks when the evaluator judges a state as "impossible". DFS uses less memory and finds solutions faster when solutions exist at deeper levels, but can get stuck exploring unproductive branches if the evaluator is imperfect. With a good evaluator, DFS terminates quickly on hard problems. With a poor evaluator, it can explore an entire subtree of wrong paths before backtracking.

For puzzles like Game of 24, where a complete solution requires exactly 4 steps, BFS with a small frontier ($k = 5$) works well. The problem has a fixed depth and you want to find the best path to that depth. For creative writing with many valid paths, DFS with backtracking is more efficient because you want to find one good solution, not the best among all solutions.

The choice between BFS and DFS interacts with the quality of the evaluation function. BFS is more forgiving of evaluator noise because it keeps multiple candidates at each level; even if the evaluator mis-scores one promising state, it is unlikely to mis-score all $b \times k$ candidates at that level. DFS is more sensitive to evaluator quality because it goes all-in on the highest-scored path at each step.

The Game of 24 is a classic test of ToT. Given four numbers, combine them using addition, subtraction, multiplication, and division to reach 24. Standard chain of thought achieves only 4% on this task because a single wrong step early in the reasoning often propagates forward. If you combine the wrong pair of numbers in your first operation, the remaining numbers make 24 nearly impossible to reach, and standard prompting cannot detect this dead end or backtrack.

ToT with BFS achieves 74% accuracy by:

1. Generating 3 candidate equations at each step ("5 + 5 = 10", "5 * 5 = 25", "5 - 5 = 0")
2. Evaluating each candidate: is it possible to reach 24 from the remaining numbers?
3. Keeping the top 5 candidates at each depth
4. Backtracking from "impossible" states

The evaluator is prompted with examples like: "Given remaining numbers [10, 3, 7], is it possible to reach 24?" The model learns to recognize promising vs. dead-end states from few-shot examples. For instance, [10, 3, 7] is promising because 10 + 7 = 17 and 17 + 3 = 20, or more directly 3 * 7 = 21 and 21 + 3 = 24. The evaluator catches cases where no combination of the remaining numbers can possibly reach 24.

This concrete 18-fold improvement (4% to 74%) from chain of thought to ToT demonstrates that the failure mode is not the model's arithmetic ability or language understanding. The model knows how to do arithmetic. What standard prompting lacks is the ability to abandon a partially constructed solution that has gone wrong and try a different approach.

The simulation confirms the structural advantage of ToT. By generating and evaluating multiple candidate steps, the search tree is far more likely to find a path through all three correct steps than a single linear chain. With 40% per-step accuracy, a linear chain of 3 steps succeeds only $0.4^3 = 6.4\%$ of the time. With branching factor 3, there are 9 candidates at depth 1, and at least one of them is likely to be a good step. The pruning step concentrates the frontier on good paths, compounding the advantage at each depth.

The value function determines whether Tree of Thought succeeds. Everything else: the generation, the search, the branching factor is secondary. If the evaluator cannot reliably distinguish promising states from dead ends, the entire search degrades into an expensive version of random search.

In the original ToT paper, the evaluation prompt was carefully designed for each task with few-shot examples of states labeled as "sure", "likely", or "impossible". This task-specific design effort is the price of the method's effectiveness. A generic evaluation prompt that works across all tasks is considerably harder to write, and the Yao et al. experiments did not demonstrate such a prompt.

This reveals a tension in ToT's design. The method achieves impressive results on the specific tasks it was designed and evaluated for. But applying it to a new task requires writing new decomposition prompts, new generation prompts, and new evaluation prompts, and verifying that they collectively produce a working search. This effort barrier means ToT is better suited to high-value problem types where engineering time is justified than to one-off problems where quick prompting suffices.

Tree of Thought is powerful but expensive. Generating and evaluating $b \times k$ candidate thoughts at each depth, across $d$ depths, costs $O(b \times k \times d)$ language model calls, compared to $O(1)$ for a single chain of thought pass. For a 3-depth problem with $b = 3$ and $k = 5$, this is roughly 45 model calls versus 1. The financial and latency costs scale accordingly.

A subtler limitation is that ToT assumes the search tree is well-defined: that thoughts are discrete units, that the problem has a clear depth, and that partial solutions can be evaluated reliably. Many real-world reasoning tasks have continuous or ill-defined structure. Open-ended conversation, creative writing, and abstract reasoning do not naturally decompose into discrete thought steps with evaluable partial states. For these tasks, the ToT framework requires significant adaptation or may not apply at all.

Self-consistency and tree of thought improve reasoning by changing how many paths are explored or how the search proceeds. Least-to-most prompting takes a different angle: it changes what gets reasoned about.

Many complex problems fail not because the model reasons incorrectly at each step, but because the problem is too complex to reason about in one step. The model sees a long, multi-conditional problem, tries to solve it directly, and makes errors because it is skipping implicit intermediate steps, conflating multiple facts, or exhausting its effective reasoning window. The failure is architectural, not just computational.

Least-to-most prompting, introduced by Zhou et al. (2022), addresses this by explicitly teaching the model to decompose problems before solving them. The name captures the ordering principle: sub-problems are identified and solved from least complex to most complex, with the answers to simpler problems feeding directly into the solutions of harder ones.

Least-to-most prompting follows a two-stage procedure. The key design insight is that decomposition and solution are separate cognitive acts that the model performs better when prompted to do them distinctly.

Stage 1: Decomposition. Given the problem, prompt the model to identify what sub-problems must be solved first. The prompt includes few-shot examples of decompositions, teaching the model to break complex problems into a sequence where each sub-problem is simpler than the original and earlier sub-problems do not depend on later ones. The decomposition step requires no arithmetic, no factual lookup, and no complex reasoning. It requires only structural understanding: what are the logical dependencies in this problem?

Stage 2: Sequential solving. Solve each sub-problem in order, carrying forward the result of each solution as context for the next. By the time the model reaches the final sub-problem, it has already solved all the prerequisites, making the final synthesis straightforward. Each individual solving step handles a problem that fits comfortably within the model's effective reasoning capability, even if the original problem did not.

The reason this works better than chain of thought on long problems is subtle. Chain of thought generates reasoning steps sequentially but does not distinguish between "figuring out what to compute" and "computing it." The model must simultaneously track the problem structure, identify what is needed next, and perform the needed calculation, all within a single forward pass that cannot backtrack. Least-to-most separates these concerns: first understand the structure (stage 1), then execute the steps (stage 2). Each stage has a narrower cognitive demand, and narrow demands are easier to satisfy.

The ordering principle is critical to the method's effectiveness. Consider a problem like: "John has twice as many apples as Mary. Mary has 5 fewer apples than Tom. Tom has 12 apples. How many apples does John have?"

Tackling this directly asks the model to track multiple relationships simultaneously, reason backward through a chain of dependencies, and synthesize the result. Decomposing it into "How many apples does Mary have?", then "How many apples does John have?" solves the easier sub-problems first and chains the answers naturally. Each sub-problem requires exactly one inference step from facts already established, rather than reasoning simultaneously across all conditions.

The ordering from least to most complex does something else valuable: it prevents the common failure mode where a model attempts to solve a hard sub-problem first, gets confused, and carries that confusion into simpler sub-problems. By solving simpler pieces first, the model builds a foundation of confirmed facts that constrain and guide the harder steps. It is the same principle that drives good mathematical proof strategy: establish the lemmas before proving the theorem.

This ordering also helps with a phenomenon called length generalization. Standard chain of thought prompting tends to fail on problems longer than those seen in the training distribution. When a model trained on 3-step math problems encounters a 10-step problem, performance degrades significantly, often producing answers that are arithmetically consistent but structurally incomplete. The model runs out of effective reasoning capacity before reaching the answer.

Least-to-most prompting provides a structural solution: if you can decompose a 10-step problem into a sequence of 2 to 3 step sub-problems, you apply the model's capability at a familiar complexity level repeatedly, rather than demanding it handle unfamiliar complexity in one shot. The model does not need to "reason longer"; it needs to reason repeatedly at its natural depth.

Zhou et al. demonstrated this concretely on the SCAN benchmark, which requires mapping natural language instructions to action sequences of varying lengths. Standard chain of thought achieved only 16% accuracy on long instructions (length $\geq 20$) while least-to-most prompting achieved 99.7%, near-perfect performance. The model was not failing because it could not understand the individual words or grammar; it was failing because 20-step instruction sequences exceeded its effective reasoning span. Decomposition solved this entirely.

The decomposition prompt is the key design decision in least-to-most prompting. A good decomposition prompt should:

• Show 3 to 5 examples of problems with their decompositions, covering a range of problem structures
• Demonstrate that sub-problems build on each other, with each one simpler than the original
• Teach the model to identify blocking dependencies: which facts does the final answer depend on, and which of those facts are themselves derived from other facts?
• Keep each sub-problem simpler than the original rather than restating part of it

The solution prompt then receives both the original problem and the list of sub-problems, and is prompted to solve them in sequence. Each solved sub-problem is appended to the context before the next one is presented, building up a complete solution step by step. This context-carry mechanism is what makes the stages "sequential" rather than independent: the context grows with each solved sub-problem, so later steps have access to all earlier results.

A common implementation failure is to design decompositions that look good but are no simpler than the original. If the original problem requires 3 inferential steps, splitting it into 3 sub-problems that each require 1 step is a valid decomposition. But splitting it into 2 sub-problems that each require 2 steps provides much less benefit and may confuse the model about what is "already solved."

The sub-problems build on each other: step 2 uses the result of step 1, and step 3 uses the result of step 2. By the time the model reaches the final answer, the hard work is done. No step requires holding more than one previous result in working memory simultaneously, and each step requires exactly one multiplication or division. A model that struggles to do three sequential arithmetic operations in one pass does each of them reliably in isolation.

It is worth pausing to understand precisely what makes least-to-most different from chain of thought, since they both involve sequential reasoning. Chain of thought generates a single continuous reasoning trace that interleaves problem analysis, decomposition, and computation. The model must reason about what to do and do it in the same cognitive act.

Least-to-most separates these explicitly. The decomposition stage produces a plan: an ordered list of sub-problems. The solution stage executes that plan, one item at a time, with the results of each step in context. This two-phase structure means the model never has to simultaneously figure out what to compute and compute it. Each stage has a single, well-defined objective.

In empirical terms, this distinction matters most when problems have long dependency chains. For short 2-step problems, the methods perform similarly. For long 8 to 10 step problems, least-to-most maintains accuracy while chain of thought degrades significantly. The decomposition stage essentially writes the reasoning plan in advance, freeing the solution stage to focus entirely on execution.

Least-to-most prompting is one instance of a broader family of decomposition strategies. The unifying theme is that complex reasoning tasks benefit from being broken into simpler components, but there are multiple ways to decompose a problem depending on its structure. Different problem types call for different decomposition styles.

The family includes approaches that decompose by logical dependency (least-to-most), by task type and tool availability (DECOMP), by shifting computation to an interpreter (Program-of-Thought), and by problem scale through recursive application. Each strategy addresses a specific structure in the problems it targets.

DECOMP, introduced by Khot et al. (2022), generalizes decomposition by allowing each sub-problem to be handled by a specialized sub-solver. The top-level model decomposes the problem and routes each piece to the appropriate handler.

In DECOMP, the language model is given a set of sub-task "tools" it can invoke:

• A search tool for retrieving facts from a knowledge source
• A QA tool for answering simple factual questions
• An arithmetic tool for numerical computation
• A sort tool for ordering items

The model decomposes the original problem into a sequence of sub-tasks, calling the appropriate tool for each. The results are chained together to produce the final answer.

This approach separates decomposition, which the language model is good at, from execution, which specialized tools are better at. Arithmetic tools make no rounding errors. Search tools retrieve accurate facts from authoritative sources. The language model provides the reasoning glue: understanding the problem, identifying what is needed, calling the right tools, and synthesizing the results. Each component does what it does best.

The DECOMP architecture foreshadows tool-use in modern language model systems, where models call web search APIs, execute code, query databases, and invoke domain-specific functions. The core insight is the same: language models are excellent at understanding, planning, and synthesizing, but unreliable at precise computation and factual recall. Routing those sub-tasks to tools that are reliable by construction allows the overall system to exceed the model's standalone capabilities.

A particularly effective decomposition strategy offloads computation to an interpreter. Program-of-Thought prompting (PoT) and Program-Aided Language models (PAL), both from 2022, share the same insight: generate a program instead of a prose answer, then execute the program to get the answer.

The language model's role shifts from computation to specification. Rather than computing "How many weeks does a 24-hour task take at 7 hours/day?", the model generates Python code:

The interpreter handles arithmetic exactly. The model handles the harder problem of setting up the right calculation: what quantities are needed, how they relate to each other, and how to express those relationships in code.

This decomposition is especially powerful for tasks that mix language understanding with computation, such as math word problems and data analysis. On the MathBench dataset, PAL outperformed standard chain of thought by 15 to 20 percentage points, with the gap widening for problems requiring more computation steps. The more computation a problem requires, the more arithmetic errors accumulate in prose reasoning, and the more the interpreter's exact arithmetic helps.

The generated code also serves a different purpose beyond correctness: it is more interpretable than prose reasoning. A chain of thought answer contains natural language steps that can be ambiguous or hard to verify. A program is precise, executable, and checkable. You can run it, inspect intermediate values, and verify that each step computes the right quantity. This interpretability has practical value in high-stakes applications.

Some problems have recursive structure: solving a complex instance requires solving simpler instances of the same problem type. Recursive decomposition, also called Recursive Reprompting and Revision (Re3) in the literature, applies the same decomposition prompt repeatedly until each piece is simple enough to solve directly.

For long document summarization, for example:

1. Split the document into sections
2. Summarize each section independently (simple sub-problem)
3. Combine section summaries into a document summary (simpler than summarizing the full document directly)

The key advantage is that each sub-problem fits comfortably within the model's effective reasoning window, even when the original problem does not. A model with a 4,000-token context can summarize a 40,000-token document by summarizing 10 sections of 4,000 tokens each, then combining the 10 short summaries into a final summary. Each step is within the model's capability even though the original task exceeds it.

The recursive structure also generalizes naturally. If 4,000-token sections are still too long, split them further. The recursion terminates when each piece is small enough to process directly. This hierarchical approach applies beyond summarization: hierarchical question answering, multi-document analysis, long-form reasoning chains, and systematic review all benefit from the same structure.

A related decomposition strategy interleaves reasoning with information retrieval. Standard chain of thought requires the model to rely entirely on parametric knowledge: what it learned during training. When problems require specific facts the model may not know reliably, or facts that change over time, this reliance on parametric knowledge creates errors. The model hallucinates specific details with confident-sounding prose, and without retrieval there is no mechanism to catch these errors.

Interleaved retrieval-augmented generation, referred to as IRCoT and related systems in the literature, decomposes the solving process into alternating steps:

1. Generate the next reasoning step based on what is currently known
2. Identify what fact is needed to continue
3. Retrieve that fact from an external source (a search engine, a knowledge base, or a document collection)
4. Continue reasoning with the retrieved fact appended to the context

Each retrieval is a sub-problem with a precisely defined form: what piece of information is needed at this step? This decomposition prevents the model from hallucinating facts while still using its language understanding for the non-factual reasoning steps. The language model handles the reasoning structure; the retrieval system handles the factual content. The combination outperforms either component alone on knowledge-intensive multi-hop reasoning tasks.

The interleaving structure also makes the system's reasoning process more auditable. You can see exactly which facts were retrieved, when they were retrieved, and how they influenced subsequent reasoning steps. This transparency is valuable in applications where users need to verify that reasoning is grounded in reliable sources.

These four strategies address different failure modes, and the right choice depends on the task. Understanding which strategy to apply requires diagnosing why simpler prompting is failing on your specific problem.

Self-consistency is the right tool when the model produces roughly correct reasoning on most attempts but fails enough of the time to be unreliable. If single-path accuracy is already 90%, self-consistency adds little. If it is 40 to 60%, self-consistency can push it above 80% with 20 to 40 samples. The prerequisite is that answers be normalizable: math answers, letter choices, classification labels, and similar discrete outputs work well. Free-form text answers do not.

Tree of Thought is the right tool when the problem requires exploration: when early decisions are hard to evaluate, when wrong turns must be detected and abandoned, and when the search space is too large for a single path to traverse reliably. The prerequisites are strong: you need a good evaluation function, a well-defined thought decomposition, and enough compute budget for the search. Without these, ToT degrades to expensive beam search with a noisy scorer.

Least-to-most is the right tool when problems are long but composed of simpler pieces. The prerequisite is that decompositions be learnable from few-shot examples and that sub-problems be simpler than the original. For problems where each "sub-problem" is as hard as the original, the method provides no benefit.

Decomposed prompting is the right tool when problems require capabilities the language model lacks: precise arithmetic, factual recall, sorting, or lookup. The prerequisite is that the needed tools be available and that the model can reliably route sub-tasks to the right tools from few-shot examples.

The four strategies are also complementary. Self-consistency can be applied on top of any of the others: run tree of thought or least-to-most multiple times and vote over the final answers. Decomposed prompting can incorporate retrieval as one of its specialized sub-solvers. In practice, state-of-the-art reasoning systems often combine multiple strategies. A production multi-hop question answering system might use DECOMP for task routing, PAL for the arithmetic sub-tasks, and self-consistency over the final answers to reduce variance. Each layer adds reliability at the cost of additional inference.

It is worth stepping back to consider why these strategies work from a cognitive science perspective. They are not random tricks; they reflect specific insights about how intelligent problem-solving proceeds.

Self-consistency mirrors the statistical intuition behind peer review and expert consensus. A single expert can be wrong, but the convergent judgment of multiple independent experts is more reliable. The key word is "independent": the value comes from diverse perspectives that fail in different ways, not from redundant agreement between identically-trained reviewers. Language model sampling at temperature $T > 0$ produces this independence by exploring different token choices at each step.

Tree of Thought mirrors the deliberate search process described by cognitive scientists studying expert problem-solvers. Kahneman's "thinking, fast and slow" framework distinguishes rapid intuitive responses (System 1) from slow deliberate reasoning (System 2). Standard language model generation is pure System 1: fast, fluent, and unreliable on hard problems. ToT adds a System 2 layer: slow, effortful evaluation that checks whether the fast responses are good. The language model's language understanding provides the intuitive generation; the evaluator provides the deliberate scrutiny.

Least-to-most prompting mirrors the cognitive strategy of problem reduction: converting a hard problem into a sequence of easier problems. This is the foundation of dynamic programming in computer science and of structured proof-writing in mathematics. The key insight is that problem difficulty is not an inherent property but a function of available resources. A 10-step problem is hard when you must hold all 10 steps in working memory simultaneously; it becomes easy when you can offload solved steps and focus on one at a time.

Decomposition strategies mirror the broader principle of modular problem-solving: breaking a complex task into components that can be handled by appropriate specialists. Human organizations work this way: accountants handle finance, engineers handle implementation, lawyers handle contracts. The coordination overhead is real, but the quality gain from specialist handling exceeds the cost. Language model decomposition strategies apply this organizational principle to single-model inference.

These reasoning strategies represent real progress, but they carry important limitations that practitioners must understand before deploying them.

The computational cost of advanced reasoning is substantial and often underappreciated. Tree of Thought and self-consistency require many more language model calls than standard prompting. At inference time, this translates to higher latency and cost. For applications where users wait for responses, generating 40 paths for self-consistency or exploring a ToT tree with depth 4 may be too slow. A user waiting 80 seconds for a self-consistent answer to a math question will not wait; they need a fast response that is occasionally wrong rather than a slow one that is usually right. The strategies that work best in research benchmarks are often impractical for real-time products without significant optimization.

Several approaches address the cost problem. Speculative consistency uses a small model to generate reasoning paths cheaply and a large model only for the final evaluation. Adaptive sampling reduces the number of samples dynamically: stop sampling early if a majority winner has emerged clearly, and sample more only when the vote is close. These heuristics can recover much of self-consistency's accuracy gain at a fraction of the compute cost.

Prompt sensitivity is a deeper challenge. The effectiveness of all these strategies depends heavily on the quality of the prompts: the few-shot decomposition examples for least-to-most, the evaluation prompts for tree of thought, the question format for self-consistency. Small changes to prompt wording can cause large swings in accuracy. This means the strategies require task-specific engineering effort and do not transfer reliably across domains without tuning.

This prompt sensitivity creates a paradox for researchers claiming benchmark improvements. A method that achieves 74% on Game of 24 with carefully engineered prompts may achieve only 50% with prompts from a different researcher who made slightly different choices about decomposition granularity or evaluation categories. The reported numbers reflect the method and the prompt engineering around it. Practitioners replicating these results should expect to invest comparable effort in prompt design.

Evaluating answer consistency is non-trivial for open-ended tasks. Self-consistency assumes answers can be normalized and compared, but for open-ended tasks, two correct answers might be phrased differently and count as disagreeing votes, while two wrong answers might be phrased similarly and incorrectly dominate. The aggregation step that looks trivial for math problems becomes ill-defined for free-form generation.

The evaluation quality problem for Tree of Thought is perhaps the most fundamental limitation. A ToT system is only as good as its value function. Designing an evaluation prompt that reliably distinguishes promising from dead-end states requires deep task understanding and careful prompt engineering. For tasks without clear intermediate checkpoints, this is nearly impossible, which is why ToT has been demonstrated primarily on puzzle-like tasks with objectively correct answers.

Despite these challenges, the practical impact of these strategies is clear. They have pushed language model reasoning to levels that were unachievable with direct prompting, closing much of the gap between model performance and human performance on challenging benchmarks. They have also informed how reasoning is built into newer models: techniques like chain of thought and decomposition are now trained into models directly, not just elicited at inference time. The next generation of reasoning-capable models trains on chain of thought traces, decomposed solutions, and program-of-thought examples, internalizing these strategies so that they emerge without elaborate prompting. We will explore this reasoning-focused training in upcoming chapters.

This chapter covered four reasoning strategies that improve language model performance beyond simple prompting:

• Self-consistency samples $N$ diverse reasoning paths and votes on the most common answer. It exploits the asymmetry between correct answers (which concentrate) and wrong answers (which scatter). It is effective on verifiable tasks and achieves large gains with 20 to 40 samples, at the cost of $N\times$ inference compute.
• Tree of Thought treats reasoning as a search problem, generating and evaluating multiple candidate thoughts at each step, then pruning unpromising branches. It enables explicit exploration and backtracking, dramatically improving performance on structured tasks like puzzles where early decisions determine later possibilities.
• Least-to-most prompting decomposes problems into a sequence of sub-problems from simplest to most complex, solving them in order and carrying results forward. It separates problem analysis (stage 1) from execution (stage 2), and is particularly powerful for tasks with long dependency chains and for overcoming length generalization failures.
• Decomposed prompting strategies generalize decomposition by routing sub-tasks to specialized solvers: tools for computation, retrievers for facts, interpreters for programs. They allow the language model to focus on reasoning and coordination while delegating computation and factual recall to systems that handle them exactly.

These strategies are complementary and often combined in practice. The underlying insight they share is that language models reason more reliably when the task is structured to match their strengths: generating coherent intermediate steps rather than leaping to conclusions, exploring alternatives rather than committing to a single path, and solving familiar sub-problems rather than novel complex ones at the limit of their reasoning capacity.

The broader lesson is that inference-time compute can substitute for model capability. A weaker model using self-consistency, ToT, or decomposition can match a stronger model using direct prompting, by spending more compute at inference time. This trade-off between model size and inference strategy is a recurring theme in modern language model deployment, and understanding it is essential for building systems that are both capable and efficient.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about reasoning strategies for language models.