ML//inference//extended thinking//tree search

Tree search is a reasoning strategy in which the model explores multiple reasoning branches, evaluates them and chooses the best, much as a person considers several options. It goes beyond linear thinking, which follows one path with no backtracking.

Tree search is a reasoning strategy in which the model explores multiple reasoning branches, evaluates them and chooses the best, much as a person considers several options. It goes beyond linear thinking, which follows one path with no backtracking.

Linear thinking1Token 12Token 23Token 34Answer

Tree search1Generate NNN branches2Evaluate each3Select the best4Continue from there

Exploring branches multiplies compute, which is what makes it expensive: it is active search among multiple reasoning chains, not just more thinking tokens. o3 likely uses it, which would explain both its accuracy leap and its high cost.

Branches can be evaluated with a PRM (the natural evaluator, scoring each step so the most valid path can be chosen), self-evaluation (RLAIF), voting (generating NNN answers and picking the most frequent) or external verification (for math and code).

It suffers from a self-consistency bias: the model tends to prefer branches consistent with its own pretraining biases, not necessarily the most correct ones, so it judges its own work with its own blind spots.

In reasoning models it is trained, scaled and RL-optimized. Tree of thought was the idea, branching reasoning at the level of the prompt; tree search in reasoning models is its implementation, trained with RL and built into inference.