When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models

Motivation

• Test-Time Scaling allocates adaptive inference-time compute to navigate task-defined spaces of partial reasoning states from a fixed model prior.This shift responds to diminishing returns from parameter scaling (Kaplan et al., 2020) and treats inference as search rather than ordinary decoding (Brown et al., 2024).Source: §1 · p. 1
• Because single-trajectory Chain-of-Thought decoding limits recovery from early errors and exploration, search-based methods maintain partial-solution frontiers and reallocate compute using intermediate feedback (Wei et al., 2022; Yao et al., 2023; Hao et al., 2023a; Wang et al., 2022).These search-augmented methods constitute the algorithmic core of modern test-time reasoning.Source: §1 · p. 1

Scope

• Tree search has a dual role: it optimizes reasoning transiently at inference time and generates trajectories that can be distilled into training data or reward models (Gulcehre et al., 2023; Feng et al., 2023a; Guo et al., 2025).Search can therefore produce durable parametric knowledge through self-improvement.Source: §1 · p. 1

Contributions

• The survey addresses fragmented literature by connecting test-time scaling and self-improvement through a unified decomposition of search mechanisms, reward or value estimation, and transition dynamics (Wei et al., 2025b).It is a systematization rather than a proposal of new algorithms or benchmarks.Source: §1 · p. 1
• Its component-based taxonomy organizes methods by search strategy, evaluation signal, and application paradigm, while its synthesis identifies empirical insights and open challenges in scaling deliberative search and designing reward signals.The survey also targets more interpretable comparisons through compute reporting and discusses adaptive allocation and search-to-training distillation.Source: §1 · pp. 1–2

Uninformed and Informed Search

• Uninformed methods scale poorly, while A* and beam search reduce cost when reliable heuristics exist but require difficult domain-general heuristic design.BFS, DFS, and UCS serve as conceptual baselines; heuristic search uses h(n) to prioritize promising nodes.Source: §2 · p. 2, Figure 2 · p. 3

Monte Carlo Tree Search (MCTS)

• MCTS avoids explicit heuristic design by sampling rollouts, backpropagating outcomes, and balancing exploration with exploitation through accumulated statistics.This supports LLM reasoning when evaluators are noisy, sparse, or available only at terminal states.Source: §2 · p. 2, Figure 2 · p. 3

Reward as a Guiding Signal: Search vs. RL

• Search rewards guide one inference episode without changing model parameters, enabling task-specific optimization through non-differentiable verifiers or execution environments.These transient signals influence the current search trajectory and avoid risks such as policy degradation or catastrophic forgetting associated with RL.Source: §2 · p. 3
• RL rewards update πθ through gradient-based training, producing durable policy changes suited to learning reusable skills across related tasks.RL therefore uses rewards for long-term policy optimization, whereas search uses them for immediate, instance-level planning.Source: §2 · p. 3

3.1 Unified Problem Formulation

• MCTS for LLMs treats reasoning as deterministic planning over partial traces, where actions append steps and the objective is an optimal reasoning trace.This formulation distinguishes partial states from incremental actions and unifies methods including RAP, ReST-MCTS, AlphaLLM, rStar-Math, and LLaMA-Berry.Source: §3.1 · p. 4

3.2 Structuring the Search: Node Representation and Granularity

• Node granularity spans complete traces, state-action pairs, and terminal solutions, trading flexible guidance and precise feedback against branching, computation, and tree size.Trace nodes preserve full path context; state-action nodes localize evaluation; terminal nodes search among complete candidates rather than sequential paths.Source: §3.2 · p. 4

3.3 Designing the Evaluation Function

• Evaluation functions steer MCTS using process or outcome signals, with PRMs and value functions guiding intermediate traces while ORMs assess terminal correctness.Terminal rewards may come from majority voting, execution verification, or LLM judging, while hybrid methods combine PRM and ORM signals.Source: §3.3 · p. 4, §3.3.1 · pp. 4–5

3.3.2 Evaluator Architecture: External Models vs. Self-Evaluation

• Evaluators may be dedicated value, reward, or preference models, or the policy LLM itself, with self-evaluation reducing dependence on external data and model maintenance.RAP predicts states and rewards as a world model, while MCTSr uses robust resampling to score solutions.Source: §3.3.2 · p. 5

3.3.3 Multi-Critic and Composite Reward Functions

• Composite critics combine value, process, outcome, execution, or preference signals to balance local step quality, long-term potential, and final correctness.ALPHALLM uses weighted value, process-reward, and outcome-reward estimates; RethinkMCTS and LLaMA-Berry combine complementary signals.Source: §3.3.3 · p. 5

3.4 Adapting the MCTS Algorithm

• MCTS adaptations incorporate policy priors in selection, critique-and-rewrite operators in expansion, and stabilized value updates in backpropagation.PG-TD and rStar prioritize nodes favored by the base LLM; LLaMA-Berry and RethinkMCTS revise reasoning, while MCTSr combines current and best-child values.Source: §3.4 · p. 5

3.5 Advanced Topics and Hybrid Approaches

• Advanced approaches extend tree search through multi-agent coordination, process-supervised reward generation, adaptive search control, and test-time architectural changes to improve scalability.These directions target complex tasks, reduce reliance on sparse terminal feedback, and control cost through information-directed exploration, dynamic selection, abstraction, and architectural adaptation.Source: §3.5 · pp. 5–6

3.6 Applications of MCTS

• MCTS supports direct test-time enhancement and self-improvement via synthetic data generation across reasoning, mathematics, code, planning, retrieval, multimodal, alignment, safety, and scientific domains.Direct use explores alternative paths without parameter updates, whereas self-improvement generates trajectories for fine-tuning policies or reward models.Source: §3.6 · pp. 6–7

Overview

• Informed search replaces manually designed heuristics with guidance generated dynamically by the LLM or auxiliary signals.The survey organizes existing approaches into direct state evaluation and composite A* cost functions.Source: §4 · p. 8

Direct state evaluation

• Direct state evaluation uses the LLM as an on-the-fly heuristic, scoring candidate thoughts to guide beam search or pruned DFS.Tree-of-Thoughts (Yao et al., 2023) proposes multiple next-step candidates, retains the top-b states, or discards low-scoring branches.Source: §4 · p. 8

Composite A* cost functions

• Composite A* methods define f(n) = g(n) + h(n), combining path progress with estimated remaining cost to prioritize partial solutions.ToolChain* (Zhuang et al., 2024) and Q* (Wang et al., 2024b) derive these components from multiple LLM-relevant signals.Source: §4 · p. 8

Motivation and contribution

• SCRP standardizes reporting quantities without ranking methods or defining optimality, addressing crosspaper comparisons that conflate policy size, evaluation cost, verification overhead, and hardware assumptions.The protocol is descriptive rather than prescriptive.Source: §5 · p. 8

Resource decomposition

• SCRP represents inference-time resources as B = (Cpolicy, Ceval, Cverify, Twall), using a hardware-agnostic first-order approximation as a monotonic proxy rather than a systems-level model.The resource vector separates policy, evaluation, verification, and wall-clock costs.Source: §5 · p. 8

Compute-aware evaluation

• Reporting performance against compute budgets such as Pass@FLOPs or Tokens-per-Solved, alongside task metrics like accuracy, exposes trade-offs hidden by raw performance numbers.This complements task-specific metrics with compute-aware views of inference efficiency.Source: §5 · p. 8

• Tree search incurs substantial compute overhead, worsened by overthinking and limited parallelism, while concise chain-of-draft reasoning can preserve accuracy with fewer tokens.DRAFT-RL combines concise reasoning, multi-agent coordination, and reinforcement learning to reduce the token budget.Source: §6 · p. 8
• Future search procedures should adapt resource allocation selectively and apply aggressive pruning to reduce inference cost.Source: §6 · p. 9
• Imperfect reward models can misguide search and cause inverse inference scaling, while PRMs remain costly to annotate, narrow in automated coverage, and weaker than oracle verifiers.Symbolic sound-by-construction constraints and automatic specification learning offer alternatives or complements to learned rewards.Source: §6 · p. 9
• The survey unifies classical and MCTS-style approaches through node representation, reward design, and algorithmic adaptation, emphasizing lighter dynamics and scalable high-quality rewards.Source: §6 · p. 9

Limitation

• The study prioritizes a coherent framework and empirical analysis over exhaustive exploration of model variants, hyperparameters, and implementation choices.Source: Limitation · p. 9
• Search depth, evaluation signals, and compute allocation may change quantitative performance without altering the study’s central conclusions.Source: Limitation · p. 9

Appendix

• The experiments use commonly adopted benchmarks and controlled settings.Source: Limitation · p. 9

Limitation

• These benchmarks and settings may not capture the diversity, noise, and constraints of real-world applications.Source: Limitation · p. 9

Appendix

• The study does not exhaustively test broader tasks, larger model families, or more heterogeneous environments.Source: Limitation · p. 9
• Extending evaluation across broader tasks, model families, and heterogeneous environments remains future work.Source: Limitation · p. 9

A Organization of the Appendix

• The appendix unifies foundational concepts, methodological taxonomies, standardized evaluation, practitioner guidance, and open challenges to support coherent comparison and adoption of inference-time tree search.It uses visual taxonomies, comparative tables, and standardized abstractions to organize six interrelated modules.Source: A Organization of the Appendix · p. 23
• The appendix operationalizes comparison through unified MCTS notation, compute-reporting protocols, metrics such as Budgeted Accuracy and Tokens-per-Solved, and task-oriented templates spanning mathematics, code, retrieval, and planning.It also identifies overthinking, deep or wide search bottlenecks, and reliance on high-quality reward models as open challenges.Source: A Organization of the Appendix · pp. 23–24

B Foundational Search Paradigms in General AI

• Classical tree search provides a vocabulary for LLM reasoning, whose combinatorially vast, high-dimensional, semantically structured spaces make exhaustive exploration computationally infeasible.The appendix revisits uninformed search, informed search, and Monte Carlo-based search as paradigms for efficiently identifying reasoning paths.Source: A Organization of the Appendix · p. 23, B Foundational Search Paradigms in… · p. 24

B.1 Uninformed Search: Blind Exploration

• Uninformed methods such as BFS, DFS, and UCS explore using actions, path costs, and goal recognition, offering guarantees such as shortest-step or lowest-cost solutions without estimating remaining distance.DLS and IDS address memory limitations, so algorithm choice depends on problem characteristics and computational constraints.Source: §B.1 · p. 24

B.2 Informed Search: Heuristic-Guided Exploration

• Informed search uses a heuristic h(n) to prioritize promising paths, with effectiveness and guarantees depending on heuristic quality, admissibility, consistency, and the cost of computing it.A* with an admissible heuristic guarantees an optimal solution when one exists, while stronger heuristics can prune more effectively but may require greater computation.Source: §B.2 · pp. 24–25

B.3 Monte Carlo Tree Search: Learning from Experience

• Inference-time MCTS adapts adversarial MCTS into a single-agent search that uses selection, expansion, simulation, and backpropagation to balance exploration and exploitation through statistical sampling (Coulom (2006); Kocsis and Szepesvári (2006)).LLM-sampled reasoning steps expand the tree, and rollouts estimate domain-specific rewards rather than adversarial win/loss outcomes.Source: §B.3 · pp. 25–26

B.4 Comparison of Exploration Strategies

• MCTS dynamically learns values through sampling rather than relying on rigid topology or predefined heuristics, making it particularly suitable for vast, ill-defined LLM reasoning spaces.Its effectiveness still depends on managing computational resources and search depth.Source: §B.4 · p. 26, §B.3 · p. 26

C Test-time Scaling via Search

• Test-time scaling performs instance-specific optimization in a task-defined objective space, contrasting with training-time scaling that refines a global policy in latent parameter space.The appendix’s conceptual framework includes Prompt Space for algorithm and policy selection and Answer Space for solution generation, while distinguishing transient search guidance from persistent learning objectives.Source: A Organization of the Appendix · p. 23, C Test-time Scaling via Search · p. 26

C.1 A Tale of Two Optimizations for LLM Scaling: Training-Time vs. Test-Time

• Training optimizes parameters in latent space using loss gradients, whereas test-time scaling searches discrete reasoning traces in task-defined objective space under an inference compute budget.Training produces a static model policy, while inference uses rewards or values to allocate computation among candidate traces.Source: §C.1 · p. 27

C.2 Operationalizing Search in the Objective Space

• MCTS operationalizes test-time search by expanding partial reasoning traces and balancing exploitation of high-value paths with exploration using policy priors, visit counts, and an uncertainty bonus.Its control policy scales reasoning performance with the allocated inference compute budget.Source: §C.2 · p. 27

C.3 Decomposing the Objective Space: Prompt and Answer Spaces

• Test-time reasoning jointly searches Prompt Space for an algorithmic template and Answer Space for a solution trace, but most current methods search only the latter under a fixed template.A poor template can leave the answer space infeasible, making systematic prompt-space discovery an open challenge.Source: §C.3 · pp. 27–28

D Reward as a Unified Signal for RL and Search: One Objective, Two Optimizers

• Reward serves one objective through two optimizers: RL permanently updates model parameters for durable behavior, while search temporarily guides planning with fixed parameters for a specific task.This distinction is based on temporal scope and application rather than competing paradigms.Source: D Reward as a Unified Signal for RL… · p. 28, §D.1 · p. 29, §D.2 · p. 29

D.1 RL via Policy Shaping: Internalizing Rewards for Generalization

• RL internalizes rewards into a policy while regularizing deviation from a prior, shaping generalizable capabilities for unseen challenges.The KL constraint helps prevent reward hacking by preserving foundational principles such as fluency or safety.Source: §D.1 · p. 29

D.2 Search via Deliberative Planning: Externalizing Rewards for Specificity

• Test-time planning externalizes rewards to select a high-quality task-specific plan, combining external task feedback with frozen-model heuristics and complexity penalties.The feedback is discarded after completion, leaving the model parameters unchanged.Source: §D.2 · p. 29

D.3 A Symbiotic Framework

• Policy shaping and deliberative planning form a bi-level framework in which learning supplies reusable search heuristics and inner-loop planning adapts them to maximize true task reward.The outer loop optimizes policy parameters for the outcomes produced by search over a task distribution.Source: §D.3 · pp. 29–30

E.1 Unified Notation and Problem Formation

• The unified MCTS formulation represents reasoning as deterministic state transitions through a tree, classifies methods as goal-driven or step-driven, and centers value-function design as a critical challenge.Partial CoT traces carry estimated values and visit counts, while rewards may evaluate actions, resulting states, or state-action pairs.Source: §E.1 · pp. 32–33

E.2 Practitioner’s Guide: Task-oriented MCTS guide

• MCTS configurations should match task feedback: trace nodes, PRMs, and average/sum backups suit mathematical reasoning; terminal nodes, execution rewards, and max backups suit code generation.For retrieval-augmented tasks, state-action nodes separate retrieval from reasoning, hybrid PRM/ORM signals are aggregated by a weakest-link minimum; agents use state-action nodes, LLM world models, composite rewards, higher exploration, and max-of-averages backups.Source: §E.2 · p. 33

E.3 Advanced Topics and Hybrid Approaches for MCTS; E.3.1 Multi-Agent and Collaborative Search; E.3.2 Reward Model Design and Optimization

• Advanced MCTS research improves robustness by coordinating multiple specialized agents, refining reward models, and combining complementary or executable quality signals.Approaches include multi-agent debate and MOSA, PRMs and OVMs, hierarchical rewards, RL-learned process rewards, and dual execution-grounded critics.Source: §E.3.2 · pp. 34–35

E.3.3 Search Efficiency and Dynamics

• Search-efficiency methods reduce wasted computation through adaptive budgets, faster node selection, information-directed exploration, dynamic branching, inference-time architecture changes, and improved step-level guidance.These methods adapt search breadth, depth, resources, or model computation to task difficulty and time constraints.Source: §E.3.3 · p. 35

E.4 MCTS for Direct Test-Time Enhancement

• Direct test-time MCTS treats generation as sequential decision-making, using lookahead over reasoning steps or text segments to overcome greedy decoding through exploration and backtracking.These methods improve a fixed model without updating its weights.Source: §E.4 · p. 35

E.4.1 General Reasoning & Problem Solving

• General reasoning frameworks make MCTS more efficient, interpretable, and robust through dynamic resource allocation, reflection, reward-model analysis, associative memory, and external knowledge integration.Their effectiveness remains contingent on accurate evaluation of intermediate reasoning steps.Source: §E.4.1 · p. 36

E.4.2 Mathematical Reasoning

• Mathematical MCTS exploits verifiable solutions through self-refinement, trajectory preferences, compressed states, outcome-trained values, constrained actions, and lightweight path verification.These methods improve reasoning quality or reduce the annotation and computational costs of long-chain search.Source: §E.4.2 · p. 36

E.4.3 Code Generation & Software Engineering

• Execution-based supervision makes MCTS especially reliable for code, supporting reasoning refinement, formal verification, repository-scale coordination, automated repair, and code-correctness evaluation.RethinkMCTS uses execution feedback, VerMCTS verifies partial programs, and related methods search abstract plans; BoostAPR reinforces the same execution-grounded principle with dual reward models.Source: §E.4.3 · p. 36

E.4.4 LLM Agents & Interactive Environments

• For interactive agents, MCTS combines LLM world modeling and policy guidance with environmental feedback to plan action trajectories across web navigation, robotics, AutoML, dialogue, and embodied interaction.Learned world models and skills reduce the search space, while frameworks such as LATS integrate reasoning, acting, planning, and self-reflection.Source: §E.4.4 · pp. 36–37

E.4.5 Retrieval-Augmented Generation (RAG) & Knowledge-Intensive Tasks

• MCTS turns RAG into an iterative retrieve-and-verify loop that supports multi-hop reasoning, factual accuracy, hallucination mitigation, and retrieval without a separate retriever model.Frameworks such as SearChain, RAG-Star, and FREESON let search decide when and what to retrieve while incrementally correcting reasoning trajectories.Source: §E.4.5 · p. 37

E.4.6 Multimodal Reasoning

• In multimodal reasoning, MCTS grounds textual concepts in visual evidence by retrieving supporting insights, scaffolding solutions with thought cards, and collaboratively reranking reasoning paths.These methods aim to improve robustness for complex, multi-step vision-language reasoning without necessarily requiring extensive fine-tuning.Source: §E.4.6 · pp. 37–38

E.5.1 Foundational Self-Improvement Frameworks

• The cited discussion describes the model as developing robust recovery skills, supported by Kim et al. (2025) and Wang et al. (2024g).Source: §E.5.1 · p. 38

E.5.2 General Capabilities & Alignment

• MCTS-generated data supports prompt optimization, self-alignment, safety training, instruction tuning, and robust reflective behavior under helpfulness, harmlessness, and output constraints.Search trajectories can include successes and recoveries from failure, while discriminators or prior value models guide constraint adherence.Source: §E.5.2 · pp. 38–39

E.5.4 Multimodal Applications

• In multimodal applications, MCTS generates step-level annotations, critique data, and difficulty estimates that train stronger and more data-efficient vision-language reasoning systems.Pipelines can create process-reward supervision without human labeling, compare correct and incorrect paths, or select challenging examples for reinforcement fine-tuning.Source: §E.5.4 · p. 39

F Informed Search Based Method

• Informed search structures LLM problem-solving as heuristic-guided traversal of vast solution trees, extending sequential generation beyond a single reasoning path.Early frameworks adapt classical search, while later methods use A*-style costs incorporating memory, self-consistency, and learned value estimates.Source: F Informed Search Based Method · pp. 39–40

F.1 Informed BFS/DFS

• ToT (Yao et al., 2023) represents states as input-plus-thought sequences and combines problem structuring, thought generation, state evaluation, and search strategy.Its generator samples independent thoughts or proposes them sequentially, while the evaluator scores states independently or selects among them by voting.Source: §F.1 · p. 40
• ToT’s informed BFS maintains a beam of b states per depth, whereas informed DFS follows one path and prunes it when evaluation falls below a threshold.BFS limits exponential growth for fixed-depth problems, while DFS concentrates exploration along a single evaluated path.Source: §F.1 · p. 40
• Subsequent BFS-style approaches vary control and representation, including causal-discovery search, internal BFS in ATS, adaptive widening or deepening in LFS, latent-space reasoning in Coconut, and Best-First Search in BFS-Prover.These methods respectively use dynamic scoring and active learning, fixed prompts, model-controlled exploration, continuous thought, or DPO-refined expert iteration.Source: §F.1 · p. 40
• A*-based methods aim to reduce MCTS overhead by prioritizing nodes with f(n) = g(n) + h(n), combining accumulated path cost with estimated future cost.LLM-A* applies LLM-generated commonsense heuristics to robotic path planning, while ToolChain* (Zhuang et al., 2023) and Q* (Wang et al., 2024c) target general reasoning.Source: §F.1 · pp. 40–41

ToolChain*

• ToolChain* constructs cumulative costs from memory-based plan similarity and self-consistency, then estimates future cost using memory-derived action positions and LLM-imagined plans.Its memory starts from demonstrations and gains successful plans; the imagined-plan heuristic compares current and total ancestor-path lengths.Source: ToolChain* · p. 41
• Q* uses f(n) = g(n) + λh(n), aggregating process rewards for current and ancestor nodes while approximating future reward with top-k policy actions’ maximum Q-value.Proxy Q-values may come from offline reinforcement learning, MCTS rollouts, or stronger-LLM distillation, but limited generalization and uncertain savings remain concerns.Source: ToolChain* · p. 41

G Unified Evaluation and Compute Accounting for Tree-Search

• The unified evaluation framework studies tree-search TTS on GSM8K and MATH because deterministic mathematical success criteria enable fine-grained analysis of fragmented reporting and compute accounting.Although demonstrated in mathematics, the proposed standard is domain-agnostic and intended for reuse across tasks.Source: G Unified Evaluation and Compute… · p. 42

Infeasibility of Retrospective Comparison

• Fair retrospective normalization is infeasible because verifier token costs are often unreported, hardware differs substantially, and baselines range from approximately 7B to 70B+ parameters.These differences prevent reliable FLOPs or wall-clock comparisons and make simple step-based comparisons invalid.Source: §G.1 · p. 42
• An apples-to-apples ranking would require re-implementing and re-evaluating all surveyed methods, constituting a separate benchmarking study beyond this survey’s scope.The survey instead proposes a forward-looking protocol to resolve the literature’s fragmentation.Source: §G.1 · p. 42

Landscape of Mathematical Reasoning

• MCTSr and rStar-Math populate a Pareto frontier across GSM8K and MATH that dominates standard baselines, suggesting smaller models with search can rival larger static models.Figure 7 aggregates heterogeneous experimental setups, so it conveys qualitative state-of-the-art rather than a controlled isocompute ranking.Source: Figure 7 · p. 42, §G.1 · p. 42

• SCRP offers a minimal, actionable recipe for comparability without requiring retroactive adjustments to baseline data.Source: §G.2 · p. 43
• B = (C_policy, C_eval, C_verify, T_wall) separates policy generation, node evaluation, external verification, and wall-clock time, using FLOPs for hardware-agnostic comparison.For a dense transformer with P parameters, inference cost is approximated as C ≈2PT; T_policy and T_eval are cumulative token counts, while C_verify captures symbolic or execution-based verification.Source: §G.2 · p. 43
• Q(b) = E[Acc | C_total ≤b] defines Budgeted Accuracy (Pass@FLOPs), exposing the trade-off between search depth and accuracy.Source: §G.2 · p. 43
• SCRP also recommends Tokens-per-Solved (TpS) for search efficiency and Parallelism Efficiency for comparing theoretical FLOPs with realized wall-clock speedup.Together, these metrics support naturally comparable compute-performance curves and reduce reporting opacity.Source: §G.2 · p. 43

ReST-MCTS*

• ReST-MCTS∗ (Zhang et al., 2024a) combines MCTS with process rewards to generate high-quality reasoning traces and iteratively improve reward and policy models.It uses evaluator modeling, weighted step rewards, and self-critique during expansion, achieving superior performance on MATH, GPQA, and CEval against baselines without MCTS.Source: H Practitioner’s Guide with Unified… · p. 43

H Practitioner’s Guide with Unified Notation

• RAP (Hao et al., 2023c) uses one LLM as both reasoning policy and world model, combining state-transition simulation with per-step rewards for efficient goal-directed search.Its rewards combine action likelihood with task-specific progress, while MCTS selection uses the maximum average future reward and standard expansion and backpropagation.Source: H Practitioner’s Guide with Unified… · pp. 43–45

LLaMA-Berry

• LLaMA-Berry (Zhang et al., 2024d) builds trees whose nodes are complete terminal solutions, refining parent solutions through critique and rewriting.A pairwise preference reward model ranks solutions using local adjacency comparisons and global win-loss matrices, supporting robust self-refinement across explored paths.Source: LLaMA-Berry · p. 45, ALPHALLM (PRM) · pp. 46–47

ALPHALLM (PRM)

• The ALPHALLM (PRM) configuration uses a pretrained process reward model to evaluate intermediate node values, while LLaMA-Berry’s PPRM compares terminal solutions.The PPRM combines local neighbor comparisons with a global Enhanced Borda Count over pairwise win-loss scores.Source: ALPHALLM (PRM) · pp. 46–47

MCTSr

• MCTSr (Zhang et al., 2024c) represents each node as a terminal solution refined by iterative rewriting and evaluates it through repeated rewards combined by minimum and average values.It uses the same LLM for reasoning and evaluation, updates parent values from child nodes, and dynamically prunes unpromising solutions.Source: MCTSr · p. 47

TS-LLM (ORM)

• TS-LLM (Feng et al., 2023b) combines trajectory-level value evaluation for intermediate paths with an Outcome Reward Model for terminal solutions.The two evaluators are trained from MCTS rollout data, and dynamic pruning removes unpromising nodes using updated values and visit counts.Source: MCTSr · p. 48

ALPHALLM

• ALPHALLM combines AlphaZero-inspired MCTS with value, process, and outcome critics to evaluate intermediate reasoning and terminal solutions.PG-TD instead uses executable test-case pass rates with beam probabilities, P-UCB selection, top-k expansion, and caching; rStar uses generator–discriminator mutual agreement and diverse reasoning actions.Source: ALPHALLM · pp. 48–49

RethinkMCTS

• RethinkMCTS combines public-test pass rates with LLM self-evaluation, using verbal feedback and a rethink operation to repair failed reasoning paths.HiAR-ICL complements PRM, ORM, and Self-Consistency with hierarchical context construction and min-based or product-based reward backpropagation.Source: RethinkMCTS · pp. 50–51

Agent-R

• Agent-R uses MCTS for offline data collection, then self-critique localizes the first error and splices good suffixes onto failed prefixes to create revision trajectories.It relies on sparse terminal environment rewards and the actor model as critic rather than a dedicated evaluator, producing targeted self-correction examples.Source: Agent-R · p. 51

Retro-Search

• Retro-Search greedily revises thought-switch points without an explicit tree or UCB, replacing a path only when a shorter correct trajectory has strictly higher value.Its deterministic value function discounts later steps and verifies whether each continuation matches the ground-truth answer.Source: Retro-Search · pp. 51–52

MASTER

• MASTER removes MCTS simulation and derives rewards from confidence-aware LLM self-evaluation, retaining selection, expansion, and conditional backpropagation.Validation precedes scoring, confidence modulates reward and exploration, and failed terminal evaluations update ancestor values; computation shifts from repeated simulations to refined node-level assessments.Source: MASTER · p. 52

AB-MCTS

• AB-MCTS adaptively chooses between deepening existing children and generating new children through GEN nodes, using Bayesian posterior modeling and Thompson sampling.SELT likewise eliminates external reward models but uses semantic clustering and representative answers to ground intrinsic LLM scoring within a modified UCT search.Source: AB-MCTS · p. 53

TRANS-ZERO

• TRANS-ZERO selects the translation candidate with the highest cumulative utility after rewarding complete outputs through multi-step simulations.Rewards are assigned to complete translation candidates rather than intermediate steps, reflecting its goal-driven objective.Source: TRANS-ZERO · p. 54
• Its reward measures multilingual semantic consistency by maximizing BLEURT similarity between the source and reconstructions produced through randomly sampled pivot-language translations.The evaluator uses the base LLM for translation variations and an off-the-shelf BLEURT metric, avoiding a separately trained critic or reward model.Source: TRANS-ZERO · p. 54
• TRANS-ZERO’s G-MCTS expands complete translation candidates using Merge and Mutate operators to balance guided and creative exploration.Merge combines the best-utility and best-UCB nodes as few-shot examples, while Mutate translates a prior reconstruction rather than the original input.Source: TRANS-ZERO · p. 54
• CMCTS integrates partial-order rules requiring coherent action sequences, including beginning with understanding and ending with summarization, alongside reflection and depth-dependent coding constraints.The rules can operate independently or with the PRM within standard selection, expansion, simulation, and back-propagation phases.Source: TRANS-ZERO · p. 54
• CMCTS uses the Qwen2.5-Math-PRM to derive action and state values, combining them during back-propagation as r_t = Q(s_t−1, a_t) + V(s_t).The PRM evaluates intermediate reasoning quality through positive and negative logits, providing context-aware guidance independent of the base LLM.Source: TRANS-ZERO · pp. 54–55
• CMCTS constrains expansion to four disjoint action sets—A_understand, A_reflect, A_code, and A_summary—to promote diverse, semantically rich reasoning states.These constraints encourage self-correction and code-based verification while addressing state-space homogenization in LLM-based MCTS.Source: TRANS-ZERO · p. 55

• Tree search can require over 10 times greedy decoding’s resources in some cases, motivating dynamic control, policy–reward trade-offs, and pruning.Sequentially generating multiple solutions at each node, as in MCTSr and LLaMA-Berry, further increases resource demands.Source: I Challenges and Future of Tree-Search… · p. 55
• O1-like models may overanalyze simple queries, wasting computation, increasing delays, and potentially introducing errors instead of allocating reasoning effort by task complexity.Future methods should recognize straightforward queries quickly and dynamically distribute computation across problem types.Source: I Challenges and Future of Tree-Search… · p. 55
• Self-play between policy and reward models can internalize tree-search reasoning into CoT, improving sequential reasoning efficiency and mitigating parallelism limits.ReST-MCTS and rStar-Math generate traces for iterative policy and reward-model refinement, but optimizing this paradigm remains open.Source: I Challenges and Future of Tree-Search… · p. 55
• Process rewards provide finer-grained supervision than outcome rewards, but human annotation is costly and automated construction remains specialized to mathematics and programming.Scientific reasoning and complex problem-solving still often require human evaluation, making scalable high-quality reward generation an open challenge.Source: I Challenges and Future of Tree-Search… · pp. 55–56
• Imperfect learned PRMs can cause inverse inference scaling, including degraded best-of-n performance when expanding search under policy–reward distribution shift.Search guided by oracle verifiers is more efficient, while trained PRMs remain behind oracle PRMs even as complete-solution verification improves with more data.Source: I Challenges and Future of Tree-Search… · p. 56