Tree of Thoughts in Large Language Models: How Search Trees, State Evaluation, and Backtracking Expand Deliberate Reasoning
Standard autoregressive large language models generate text sequentially from left to right. At each step $t$, the network samples the next token according to a conditional probability distribution over the vocabulary: P(w_t | w_1, w_2, ..., w_{t-1}) While Chain-of-Thought (CoT) prompting (Wei et al., 2022) encourages models to output intermediate reasoning steps, the underlying computational process remains a linear path through token space. If the model makes an early logical error or choose
1 min