Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey

Deliberative tree search is a cornerstone of modern Large Language Model (LLM) research, driving the pivot from brute-force scaling toward algorithmic efficiency. This single paradigm unifies two critical frontiers: $\mathbf{\text{Test-Time}}\mathbf{\text{Scaling}}\mathbf{\text{(TTS)}}$, which deploys on-demand computation to solve hard problems, and $\mathbf{\text{Self-Improvement}}$, which uses search-generated data to durably enhance model parameters. However, this burgeoning field is fragmented and lacks a common formalism, particularly concerning the ambiguous role of the reward signal – is it a transient heuristic or a durable learning target? This paper resolves this ambiguity by introducing a unified framework that deconstructs search algorithms into three core components: the \emph{Search Mechanism}, \emph{Reward Formulation}, and \emph{Transition Function}. We establish a formal distinction between transient $\mathbf{\text{Search}}\mathbf{\text{Guidance}}$ for TTS and durable $\mathbf{\text{Parametric}}\mathbf{\text{Reward}}\mathbf{\text{Modeling}}$ for Self-Improvement. Building on this formalism, we introduce a component-centric taxonomy, synthesize the state-of-the-art, and chart a research roadmap toward more systematic progress in creating autonomous, self-improving agents.