Tree of Thoughts (ToT): Searching and Backtracking Across Multiple Intermediate Solutions

When a model generates step by step, each step takes the previously written token as its prefix. A linear Chain of Thought (CoT) is exactly such a process: once an early choice is generated, it is fixed into the prefix, and all subsequent tokens can only continue under that precondition. The problem then arises—if an earlier step was wrong, can later generation repair it? The answer is that it is very difficult. Linear generation has no return channel: the model can smooth things over later, remedy the situation, and even verbally contradict the earlier text, but the already-written prefix is not replaced, and the repair itself can only proceed along the same path. The wrong choice is treated as an established premise, and the path is locked in from that moment.

Tree of Thoughts (ToT) targets precisely this kind of path locking. Its approach is to take intermediate results out of a continuous text and externalize them as multiple parallel candidate states: each step does not keep only one current answer, but saves multiple candidates while recording the parent-child relationships between them—which state was expanded from which state. If a branch reaches a dead end, the system can return to the nearest fork and take a different candidate branch. This ability to turn back when a dead end is discovered makes it suitable for planning, puzzle solving, program repair, and combinatorial search—tasks whose common feature is many intermediate steps, and where early decisions often only reveal their errors many steps later.

The key difference here is not the amount of text. Writing longer reasoning is still linear generation; what truly changes the nature are two things. First, the system saves the candidates that were not selected, rather than discarding the rest after generating one; second, the system maintains parent-child relationships between states and can call an evaluator to decide which one to expand next. With these two points, the expansion order is no longer uniquely determined by "what the previous step generated," but is controlled by an external search state. Conversely, if all candidates are still concatenated into a single text and generated in one go, then even if the text says "Plan A doesn't work, switch to Plan B," there is no real backtracking—A and B are not states that the system can independently retain and switch between; they are merely sentences that appear one after another in the text.

Displaying the interface of the Tree of Thoughts makes this clearer. Its inputs include: the current problem state, candidate expansion methods (how to generate several child states from a state), an evaluator (judging how valuable a state is), and a search budget (how many steps are allowed to explore). Its output is a search tree with parent-child relationships, in which each state is either retained for further expansion or pruned and discarded, and it must also indicate which states have passed validation and reached a terminal state. With this input-output structure, the system can return to a fork and retry when an early choice goes wrong, instead of continuing to generate down the same prefix.

The boundary is equally clear: if no alternative states are saved, if there is no true backtracking action, but only thinking written as multiple paragraphs of text, then it does not constitute a Tree of Thoughts. The criterion is not the length of the text, but whether the search is controlled by an external state machine: whether candidates are explicitly stored, whether the expansion order can be changed by the evaluator, and whether failed branches are truly discarded and can be rolled back to. Writing more text only makes the linear path longer; what truly enables search is the externalization of states and parent-child relationships.

To turn "thinking while searching" into a searchable process, we first need to answer a question: what counts as a searchable "line of thought"? A line of thought cannot be an arbitrary idea; it must be modeled as an operable state. Modeling requires four things: state representation, expansion operations, value or feasibility scoring, and termination conditions. All four are indispensable; missing any one of them causes search to degenerate into unstructured trial and error.

State representation determines "where we stand after one step". The state contains only the facts and artifacts that affect subsequent decisions—confirmed facts, verified intermediate results, and the constraints these facts impose on future choices. Content unrelated to subsequent decisions never enters the state; otherwise the state space will be inflated by noise, and search will repeatedly jump between meaningless differences.

Expansion operations define "where we can go next from here". Each expansion step must produce a valid candidate: it may be executing a valid action, or it may be proposing a new causal hypothesis. The expanded candidate must be executable, not a rhetorical wish; it must be verifiable, comparable, or able to be further expanded.

The scoring step estimates feasibility, benefit, risk, and remaining cost for each candidate. Feasibility answers "Can this candidate actually be done?", benefit answers "How much of the problem will be solved if it succeeds?", and risk and remaining cost answer "Is continued investment worthwhile?". The purpose of scoring is not to give the final answer, but to let the search preferentially expand the most promising branches within limited resources.

Termination conditions are determined by an external completion predicate, not by the search process declaring success on its own. By external, we mean there is an independent judgment criterion that is not part of the search itself: for example, all tests pass, the diagnosis matches the symptoms, or the artifact passes inspection by an independent verifier. Search cannot grant itself a diploma, otherwise it can easily convince itself on the wrong branch.

The granularity of the four elements directly determines the success or failure of the search. If the granularity is too fine, every tiny difference becomes a new state, the number of branches explodes, and the search becomes unaffordable in cost; if the granularity is too coarse, situations with different natures are mixed into the same state, making it impossible both to locate the specific link where the error occurred and to identify and reuse truly identical substates.

The state in the cache case is an intuitive example. It should not be a prose sentence like "I think it might be a cache problem"—such a sentence cannot be compared, cannot be deduplicated, and cannot be verified. The correct state is a structured collection of facts: which tests have already been run, what the current code diff is, which causal hypotheses are still alive, and how much budget remains. Only such a state can be hashed for deduplication, replayed, and handed to an independent verifier for inspection.

From a modeling perspective, the inputs to search are task facts, verified artifacts, valid actions, scoring dimensions, and a completion predicate; the output is a complete definition of the four elements: state representation, expansion operations, value evaluation, and termination conditions. The state retains only facts that affect subsequent decisions, expansion produces executable candidates, scoring separates hard feasibility from soft value, and the terminal state is confirmed by external conditions. Too fine a granularity leads to explosion; too coarse a granularity masks errors and hinders deduplication; the appropriate granularity is to let "the same situation fall into the same state".

After the four elements—state, expansion, scoring, and termination—are determined, the next question is whether to go deeper first or spread wider first under a limited budget. Three classic traversal orders give three different answers: breadth-first search (BFS), depth-first search (DFS), and beam search.

BFS's rule is to cover the same level first, expand all sibling nodes at the current depth, and then move to the next level. Its advantage is that if a shallow solution exists, BFS will definitely find it first, and the solution it finds is shortest in depth. The cost is memory—all states at the same level must be stored simultaneously; the deeper the level, the more states are alive at the same time, and memory pressure rises rapidly with width.

DFS's rule is the opposite: choose one branch and drill all the way down to the bottom, backtracking when a dead end is encountered. Its memory footprint is small, needing only to store the states on the current path; at the same time, it can produce a deep solution most quickly, allowing people to first see a "complete solution with a beginning and an end". But DFS's risk is that the budget may be entirely consumed on the wrong first branch—if the first choice is a dead end, the deep exploration produces no usable results, and after backtracking there may be no budget left to expand the truly promising branches.

beam search is a compromise between quality and cost: at each level, keep only the b highest-scoring candidate states and prune all the rest. b is the beam width. It combines BFS's "fully spread out at each level" and "filter by score", using a fixed-size beam to control memory and expansion cost, at the cost of possibly pruning branches that are temporarily low-scoring but ultimately lead to the optimal solution.

Whichever order is chosen, pruning is not optional but a mathematical necessity. Let the branching factor be k and the depth be d; then the number of leaves at depth d is kᵈ, and the total number of nodes in the whole tree is (k^(d+1)−1)/(k−1). This means the number of nodes grows exponentially with k and d: with a slightly larger branching factor or slightly deeper depth, the node count of full enumeration becomes too large to bear. Any realistic-scale search must prune somewhere; the only questions are where to prune and by what criterion.

Which strategy to choose should match the verification cost. If verifying a candidate is cheap—for example, a single static rule can rule out obvious errors—then broad search can be used, quickly spreading out with cheap evidence and eliminating many branches. If verification is expensive—for example, you must actually execute a task to know the result—then you should first use static evidence to filter out a few candidates, and then invest in expensive execution verification. Conversely, using expensive verification to spread out every level, or using cheap verification only for a single path, causes a mismatch in cost.

Strategy scores have another insurmountable boundary: they cannot bypass the permission and real-execution gates for high-risk actions. No matter how high a branch scores, as long as it involves high-risk actions, it cannot be executed directly based solely on the score; it must go through permission checks and real execution confirmation. Scores are a ranking tool, not an authorization tool.

Summarize the input and output of this layer: the inputs are branching factor k, depth d, beam width b, memory constraints, and verification cost; the outputs are the traversal order and candidate limit of BFS, DFS, or beam. BFS spreads the same level first, DFS goes deep first, beam keeps only b high-scoring states per level; the number of nodes in the complete tree grows exponentially with k and d, so pruning is unavoidable; and no strategy score can bypass the permission gate and real execution gate for high-risk actions.

At every level of the search tree, the same question keeps coming up: What should be pruned? The evaluator answers this question. The evaluator's reliability determines the quality of the entire tree—if it gives promising branches low scores, pruning becomes self-destruction.

There are many implementation options for the evaluator. It can be deterministic rule checking: for example, syntax checking, permission checking, constraint validation; it can be environment execution: actually run the candidate and let the results speak; it can be a separate, independent model that scores; it can also be multiple votes to reach consensus. These approaches are not equally reliable.

Having the generator model score itself has two systematic problems. The first is confidence bias: the generator tends to overestimate the content it has just written, because the generation process itself is an implicit form of self-approval. The second is shared blind spots: if the evaluator and the generator are the same model or share the same training distribution, they will share the same knowledge gaps and the same error patterns, so errors missed by the generator are often invisible to the evaluator. Therefore, for verifiable tasks, deterministic checks—tests, rules, execution results—should be preferred over model self-evaluation. Only for dimensions that truly cannot be verified should one fall back to model judgment.

Scoring must also distinguish two things with completely different natures: hard constraints and soft value. Hard constraints are the elimination line: states that violate permissions, violate syntax, or violate non-negotiable constraints are eliminated directly no matter how good they look otherwise, with no room for negotiation. Soft value is the basis for ranking: states that have not yet been verified but have potential should retain their uncertainty and be ranked by estimated benefit, risk, and remaining cost, rather than being arbitrarily zeroed out. Compressing these two into a single number is dangerous—a seemingly precise 0.73 score can express neither "violates permissions, so must be eliminated" nor "not yet verified, so merely promising". Hard elimination uses rules; soft ranking uses scores; the two cannot be mixed on a single scale.

The evaluator itself also needs calibration; otherwise the scores it gives are meaningless. The way to calibrate is: for each score interval, count the actual terminal success rate—of candidates scored 0.8 to 0.9, what proportion actually succeed in the end? If the actual success rate in high-score intervals is far lower than the level implied by the scores, the evaluator is systematically overestimating. At the same time, check whether the evaluator has hidden preferences: whether it systematically favors longer text, familiar high-frequency wording, or a particular generation position (for example, always giving higher scores to candidates at the end of a list). These preferences have nothing to do with the candidates' true quality, yet they will steadily distort the ranking.

Viewed in terms of inputs and outputs: the evaluator receives candidate states, hard constraints, evidence, estimated benefit, risk, remaining cost, and real verification results, and outputs one of four possible actions—eliminate, retain, adjust priority, or confirm terminal state. Candidates that violate permissions or syntax are eliminated directly; states with insufficient evidence but potential retain their uncertainty; executable tasks are preferentially verified with tests and rules. The core boundary is: self-evaluation shares the generator's blind spots; scores are ranking tools, not truth values, and a 0.73 score cannot be disguised as objective fact.

Search is not free. It expands the exploration space but does not guarantee gains; every layer it opens up consumes budget. The question for this section is: When are more branches no longer worth it?

First, look at what cost consists of. Every state expansion, every candidate scoring, every tool call, and every token consumed is a cost. There are also two easily overlooked types of costs: one is wall-clock latency—state serialization and real tool calls increase overall latency, and serial waiting time does not disappear due to pruning; the other is pruned candidates—they do not make it into the final result, but generation and scoring have already cost money. The cost of search comes not only from leaves ultimately kept; dead branches are also billed.

Therefore, budget control requires explicit stopping conditions. It can stop by value difference: when the improvement brought by new branches falls below a threshold, stop expanding; by lack of progress: when several consecutive rounds of expansion have not made the best candidate better; by depth: when a set depth is exceeded, go no deeper; or by total budget: when tokens, call count, or wall-clock time are exhausted, stop. Search without stopping conditions is simply burning money without limit.

Enabling search itself should also be layered. First use a router to judge task difficulty, enable search only on difficult slices, and still generate directly for simple tasks. Applying search to simple tasks only turns something that could be done in one step into an expensive enumeration with no benefit.

The quantitative way to judge "whether to continue" is to compare marginal benefit with unit cost: the success-rate gain from each additional candidate versus its cost. For example, increasing the beam width from 2 to 4 improves success rate by only 1 percentage point, but generation and scoring calls double—this trade-off is clearly not worthwhile. The saved budget should be redirected to the verifier (to make evaluation more accurate) or to constructing a better initial state (to bring the search starting point closer to the solution). The same money spent on validation and the starting point often yields higher returns than spending it on a wider beam.

The inputs to budget control are the costs of each generation, scoring, tool execution, token, and wall-clock time, the marginal success gain, and the various stopping upper limits; the output is to continue expanding, prune, backtrack, or stop. Core conclusion: record all consumption including pruned candidates, enable search only on difficult slices, and redirect budget to the verifier or a better initial state when marginal gain falls below unit cost. Search expands the exploration space but does not guarantee gains.

Is Tree of Thoughts search equivalent to a real-world AI Agent? The answer is: no. ToT can search only in text state, while AI Agent planning additionally requires tool feedback, permissions, and a dynamic environment; the two are different things.

ToT's search space can be purely imagined: the model generates multiple intermediate plans in text, scores them, prunes, and backtracks, and the entire process can be completely without contact with the external world. The value of this search lies in quickly exploring reasoning paths, but its boundary is also clear—an imagined state cannot replace actual execution observation. The model can "imagine" in text that a test passed, or "imagine" that a tool returned the expected result, but an imagined receipt is not a receipt. Actual execution returns information beyond imagination: the environment changed, permissions are insufficient, the return format differs from expected, new dependencies appear. An AI Agent must actually call tools to obtain new facts, and replan after the environment changes; ToT's text state search does not have this hard requirement.

The second boundary is: search does not create missing knowledge. All branches share the same model and the same context boundary. If a fact is simply not within the model's context or capability range, no matter how many branches are expanded, it will not be found—what each branch can think of comes from the same knowledge pool. Search amplifies the ability to "combine and select", not the ability to "acquire new knowledge"; acquiring new knowledge requires external tools, which is exactly the part that an AI Agent has over pure ToT.

From the input-output perspective: an AI Agent's boundary inputs are imagined states in text, real tool observations, current permissions, and a dynamic environment; outputs are candidates for planning only, as well as executable authorized actions. ToT's output is reasoning candidates; an AI Agent's output must include truly executable actions, and these actions are constrained by current permissions—actions that can be done in imagination may not be executable within the permission scope.

Connecting the two: ToT is a component of AI Agent planning, responsible for generating and filtering candidates in text space; an AI Agent also needs real tool feedback to correct plans, permission gates to constrain execution, and a dynamic environment model to support replanning. An AI Agent that only does ToT without connecting real feedback will remain in imagination; a system that only executes without planning lacks the ability to select among multi-step plans. The boundary is clear: imagining a test passing cannot replace an actual receipt, and search will not create knowledge missing from the model's context.

Use a concrete failure to tie together the abstract mechanisms from the previous layers: a cache isolation failure. The symptom is that a "string value" does not match expectations, and it could come from any of three places: cache key, namespace, or serialization. The real constraint is: how to explore these three causes within a limited budget, rather than changing all three places at once—changing them simultaneously would make validation meaningless, because you would not know which one fixed it.

The initial state S0 contains the current string value, the tests that have been run, and the surviving cause hypotheses. Expansion produces three cause branches: A is a cache key missing user_id, B is namespace cross-talk, and C is object reuse causing the string value to be shared. This is what a "thought" looks like concretely—not a sentence like "maybe it's a cache problem", but a combination of cause hypothesis and executable verification: each branch can be mapped to a specific check and modification action.

Next is the choice of visit order. The budget is assumed to be at most 4 visited nodes, and three strategies produce three trajectories:

DFS goes straight down along A, reaching the concrete patch at the A1 level fastest, but if A is the wrong first branch, the depth is wasted. BFS first spreads out and compares the three causes A, B, and C, but the budget of 4 nodes is only enough to look at one level, not enough to verify any patch. beam=2 keeps 2 high-scoring states at each level: first compare and keep A and C, then expand A further to obtain A1. It balances alternatives and depth, but the ranking quality is entirely staked on the scorer.

In this example, deterministic tests update the state value, and pruning is based on evidence rather than how plausible the wording sounds: the tests prune B (namespace cross-talk) and prioritize expanding A; A1 produces a composite key patch, the tests pass 4/4, and it becomes a terminal state. If A1 fails, backtrack to the retained C and continue verification.

The necessity of search can be calculated with numbers. For a complete tree with branching factor k=3 and depth d=4, the total number of nodes is 1+3+9+27+81=121, not just the 81 leaves—intermediate nodes must also be generated and scored. If each node requires 800 tokens, a complete search requires about 96,800 tokens. beam=2 keeps and expands at most two states per level, so the rough upper bound drops to 1+4×(2×3)=25 candidate evaluations, a cost reduction of an order of magnitude. Note that this is only an estimate for generation and scoring; real tool execution (actually changing code and running tests) still needs to be billed separately.

Another line of defense is state deduplication. If two text branches both lead to the same code diff and test results, they should be merged into the same state—they are essentially the same situation. If they are not merged, synonymous rewrites will fake the diversity of the search: the tree looks luxuriant, but in reality it is spending budget repeatedly to verify the same thing.

The input at this layer is the initial string-value state S0, three cause branches, a budget of at most four nodes, and test evidence; the output is the search trajectory, the patch terminal state, and the backtracking point. For a complete tree with branching factor k=3 and search depth d=4, the total number of nodes is Nnodes=121; this number shows why pruning is necessary: the total node count of a complete k-ary tree grows as (k^(d+1)−1)/(k−1), and the budget can never keep up with it.

Search expands the candidate space, but it also hands greater power to the evaluator. The generator proposes possibilities; the evaluator decides where the compute budget flows. With a single generation, an evaluation mistake affects only one answer; with search, evaluation mistakes accumulate at every layer—this is why a weak evaluator can be more dangerous than single generation.

If the evaluator has systematic biases—favoring detailed wording, favoring short patches, favoring branches similar to its own views—beam will steadily eliminate the true solution at every layer. When the first layer gives it a low score, it gets pruned; after pruning, no matter how the second layer expands, it will no longer appear. Search amplifies the evaluator's bias rather than canceling it.

The countermeasure is to split the scoring dimensions, rather than output a single blended total score. Scoring should be separated into five items—hard feasibility, evidence support, expected benefit, risk, and verification cost—each judged independently. When tests can be run, prefer tests—deterministic verification is more reliable than any model judgment; when verification is not possible, preserve uncertainty rather than fabricating a precise score. A branch without evidence should get "unknown", not "0.43".

The specific failure modes can be listed in five categories by symptom and mitigation:

Premature pruning is caused by evidence timing differences: the correct branch often has not yet accumulated enough verification evidence in the early stage, and if scoring only considers the current amount of evidence, it will be eliminated by a low score. The mitigation is to reserve a quota for exploration, or set an uncertainty upper bound for branches with insufficient evidence, letting them survive a few more rounds.

Score leakage is input contamination of the evaluator: if the evaluator can access the wording of a reference answer, the score it gives measures not solution quality but textual similarity to the answer. Isolating evaluation data and hiding the validation set is the standard practice.

Branch homogenization is the counterpart of state deduplication: multiple candidates differ in text but are completely identical in state or action; they are just splitting the budget and creating false diversity. Deduplicate by state and action differences, and merge paraphrased rewrites.

Treating simulation as fact is treating an imagined receipt as a receipt: the model imagines "the test passed" and marks the node as terminal. The terminal state must be verified in the real environment—the test must be run in the real environment and the passing result actually returned before it counts as reaching the endpoint.

Cyclic backtracking is a failure of the backtracking mechanism: the visit history is unclear, and it repeatedly switches between two states, exhausting the budget in a loop. A visited set, depth, budget, and no-progress—four types of termination conditions—together provide a fallback.

Write out these attributions completely: the inputs to evaluator failure analysis are the scores of each branch, the pruning order, state differences, real tests, and visit history; the outputs are attributions to premature pruning, score leakage, homogeneous branches, treating simulation as fact, or cyclic backtracking. The mitigation is to split hard feasibility, evidence, benefit, risk, and cost into five dimensions, and retain an exploration quota and a visited set; terminal states must be verified by the environment.

Finally, the applicable boundary: ToT is not suitable for every task. When the answer can be verified in one step, when the action space is fixed and traditional algorithms can be used, or when each real execution is irreversible and expensive, blindly expanding branches only increases cost and risk—on such tasks the search tree amplifies both evaluation errors and real cost simultaneously, and single generation is actually a more rational choice.

Connect the links, and the operating logic of Tree of Thoughts (ToT) search is a six-step causal chain.

First, represent the problem as a state. The state retains only the facts and artifacts that affect subsequent decisions: confirmed evidence, verified intermediate results, still-active causal hypotheses, and remaining budget. This step determines the space in which every subsequent step operates; if the granularity is wrong, everything that follows will be wrong.

Second, generate multiple candidate expansions. Each expansion must produce executable candidates—legal actions or causal hypotheses—not rhetorical ideas. Candidates must differ substantively; paraphrases do not increase exploration capability.

Third, evaluate feasibility and value. Separate hard feasibility from soft value: candidates that violate permissions, syntax, or non-negotiable constraints are eliminated immediately; the remaining candidates are ranked by evidence support, expected benefit, risk, and verification cost. For deterministically verifiable dimensions, prioritize tests and rules; do not let model self-evaluation masquerade as fact.

Fourth, retain candidates according to BFS, DFS, or beam. BFS expands the same level first, DFS goes deep first, and beam keeps only b high-scoring states per level; the choice depends on verification cost and memory budget. Regardless of the strategy, the number of nodes in a complete k-ary tree grows exponentially as (k^(d+1)−1)/(k−1), so pruning is unavoidable.

Fifth, on failure, backtrack or continue expanding. Backtracking must be constrained by four types of termination conditions—visited set, depth, budget, and lack of progress—to prevent looping idly between two states. After backtracking, prefer returning to the retained alternative branches rather than starting over from scratch.

Sixth, verify the terminal state and compare search costs. The terminal state must be verified in a real environment—imagined receipts do not count. At the same time, include the cost of search and the cost of pruned candidates, and compare them with the marginal success gain: if increasing beam from 2 to 4 brings only a 1 percentage point improvement while doubling calls, the budget should be redirected to the verifier or to better initial states, not to a wider beam.

These six steps form a closed loop: state representation limits branch quality, the evaluator determines budget flow, visit order determines which gets verified first, backtracking and termination prevent budget idling, terminal-state verification prevents simulation from being treated as fact, and cost comparison determines whether the search itself is worthwhile. If any link fails, search degrades from "expanding the probability of correct choices" to "expensively amplifying the same error". Search expands the exploration space but does not guarantee benefits—only when every step is constrained by evidence, permissions, and cost is it truly superior to a single generation.