PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiaqi Wei, Xiang Zhang, Yuejin Yang, Wenxuan Huang, Juntai Cao, Sheng Xu, Xiang Zhuang, Zhangyang Gao, Muhammad Abdul-Mageed, Laks VS Lakshmanan, Chenyu You, Wanli Ouyang, Siqi Sun

arXiv:2608.30395v1cs.CL

TL;DR

As pretraining scaling laws show diminishing returns and CoT commonly uses single trajectories, the survey examines search-based inference as adaptive optimization over partial reasoning states. It unifies existing methods across search mechanisms, evaluation signals, and transition dynamics, and concludes that lighter search and scalable reward signals are needed for broader use.

  • Problem

    Single-trajectory Chain-of-Thought decoding limits recovery from early errors and exploration, while the literature remains fragmented across search strategies, evaluation signals, and protocols.

  • Method

    The survey systematizes search-based reasoning through a unified formalism and taxonomy covering search mechanisms, reward/value estimation, transition dynamics, and MCTS-based planning notation.

  • Results

    Search methods routinely report 10–40% gains over greedy decoding on suitable tasks, while open-ended generation typically shows marginal improvements over strong decoding baselines.

  • Takeaways & Limitations

    The survey concludes that lighter-weight search dynamics and scalable, high-quality reward signals are needed to establish tree search as a general-purpose reasoning mechanism.

  • Takeaways & Limitations

    The experiments use commonly used benchmarks and controlled settings that may not capture the diversity, noise, and constraints of real-world applications.

Abstract

from arXiv · show

As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.

1 Introduction

Test-Time Scaling reframes reasoning as adaptive search over partial states, addressing the limited recovery and exploration of single-trajectory Chain-of-Thought decoding. This survey organizes fragmented search-based reasoning research through unified components, taxonomies, empirical synthesis, and reporting guidance.

  • Test-Time Scaling allocates adaptive inference-time compute to improve problem solving from a fixed model prior by navigating partial reasoning states.
  • Single-trajectory Chain-of-Thought decoding limits recovery from early errors and restricts exploration, motivating frontier-based tree search.
  • Tree search supports both transient inference-time optimization and generation of trajectories that can be distilled into training data or reward models.
  • The survey addresses fragmented search strategies, reward or value estimation, and evaluation protocols through a unified framework connecting test-time scaling and self-improvement.
  • Its contributions include a formal decomposition, a component-based taxonomy, and a synthesis of empirical insights and open challenges.

2 Search in General AI

Classical reasoning search spans uninformed, heuristic, and sampling-based paradigms, each allocating exploration differently. The survey distinguishes search rewards used for instance-level planning from reinforcement-learning rewards that update model parameters.

  • Uninformed and Informed Search: Uninformed methods such as BFS and DFS provide conceptual baselines but scale poorly in large reasoning spaces.
  • Uninformed and Informed Search: Heuristic methods such as A* and beam search reduce search cost when reliable heuristics exist, but accurate domain-general heuristics remain challenging for open-ended LLM reasoning.
  • Monte Carlo Tree Search: MCTS learns value estimates through sampling and balances exploration with exploitation, making it suitable for noisy, sparse, or terminal-only evaluators.
  • Reward as a Guiding Signal: Search vs. RL: In test-time search, external transient rewards influence the current trajectory without modifying parameters, enabling task-specific optimization without policy degradation or catastrophic forgetting.
  • Reward as a Guiding Signal: Search vs. RL: Search rewards guide planning for one problem instance, whereas reinforcement-learning rewards reshape model parameters through gradient-based updates across episodes.

3 MCTS for LLMs

MCTS-based LLM reasoning formulates inference as deterministic planning over partial reasoning traces, with node design and evaluation signals shaping search. Adaptations to selection, expansion, and backpropagation support diverse reasoning tasks, while gains are strongest when correctness is verifiable.

  • Search formulation: LLM planning treats the evolving text trace as a deterministic environment, with actions producing uniquely determined next reasoning states.The objective is to find an optimal reasoning trace for a problem.
  • Search formulation: Search trees use trace-based, state-action, or terminal-state nodes, trading finer feedback and flexibility against larger branching factors and higher cost.Trace-based nodes preserve full path context; state-action nodes localize evaluation; terminal-state nodes represent complete candidate solutions.
  • Evaluation signals: Evaluation functions assign node values or action rewards that steer exploration toward correct solutions or high-quality reasoning trajectories.PRMs and value functions score intermediate states, whereas ORMs typically evaluate terminal states using voting, execution, or LLM judging.
  • Evaluation signals: Reward generation may use dedicated evaluators, policy-LLM self-evaluation, or composite signals balancing step quality, long-term potential, and final correctness.Composite designs combine value estimates, process rewards, outcome rewards, preferences, or win–loss signals.
  • Algorithmic adaptations: MCTS adaptations modify selection, expansion, and backpropagation to incorporate policy priors, critique-and-rewrite refinement, verbal feedback, and smoother value propagation.These changes illustrate MCTS’s flexibility for generative reasoning.
  • Applicability: Search-based methods often report 10–40% gains over greedy decoding on verifiable reasoning tasks, but usually yield marginal improvements for open-ended generation.Search can also perform poorly when rewards are weakly correlated with correctness or when large budgets cause overthinking on easy instances.

4 Informed Search with LLM-Generated Heuristics

Informed search uses dynamically generated LLM heuristics or auxiliary signals to navigate large reasoning spaces. Existing methods primarily evaluate candidate states directly or construct composite A* costs.

  • Overview: Informed search dynamically generates heuristics with LLMs or auxiliary signals instead of relying on manually designed classical heuristics.The main paradigms are direct state evaluation and composite A* cost functions.
  • Direct state evaluation: Tree-of-Thoughts proposes multiple candidate thoughts, scores them with an LLM evaluator, and applies beam search or pruned DFS to retain promising branches.Beam search keeps the top-b states, while pruned DFS discards low-scoring branches.
  • Composite A* heuristics: ToolChain* and Q* use f(n) = g(n) + h(n), combining path progress with estimated remaining cost from multiple LLM-relevant signals.These composite heuristics prioritize partial solutions that appear closer to a goal.

5 Evaluation Framework

The evaluation framework addresses the difficulty of comparing tree-search results when compute expenditures are reported inconsistently. SCRP makes inference-time resources explicit and encourages performance reporting against compute budgets.

  • Motivation: Cross-paper comparisons are difficult because reported gains conflate policy size, evaluation cost, verification overhead, and hardware assumptions.Tree-structured decoding makes test-time compute an important scaling axis, but these factors obscure trade-offs.
  • SCRP: SCRP is a descriptive reporting abstraction that standardizes inference-time compute quantities without ranking methods or defining optimality.It is intended to make compute expenditures explicit and comparable.
  • SCRP: SCRP decomposes per-instance resources into B = (Cpolicy, Ceval, Cverify, Twall) and uses a first-order approximation as a monotonic proxy.The proxy is hardware-agnostic rather than a systems-level cost model.
  • Reporting recommendations: The framework encourages reporting performance as a function of compute budget, including Pass@FLOPs or Tokens-per-Solved alongside task-specific metrics such as accuracy.This presentation surfaces trade-offs that raw performance numbers can obscure.

6 Challenges, Future and Conclusion

Tree-search reasoning is limited by computational overhead and unreliable reward signals, motivating adaptive allocation, pruning, and lighter-weight search. The survey concludes that scalable rewards and efficient dynamics are needed for broader use.

  • Challenges: Search adds substantial overhead relative to greedy decoding, while strong models may overthink simple queries and structural constraints can slow distillation cycles.These bottlenecks affect both inference efficiency and search-to-training transfer.
  • Future directions: Adaptive, selectively activated search with dynamic resource allocation and aggressive pruning is proposed as a response to compute bottlenecks.The survey also highlights shortening reasoning traces as a complementary efficiency lever.
  • Challenges: PRMs provide finer-grained supervision than ORMs but depend on costly annotations, while automated approaches remain concentrated in narrow domains such as mathematics.Imperfect rewards can misguide search and cause inverse inference scaling, where additional rollouts reduce accuracy.
  • Conclusion: Tree search is unified around node representation, reward design, and algorithmic adaptation, with future progress depending on lighter search dynamics and scalable high-quality reward signals.The conclusion frames these requirements as central to making tree search a general-purpose reasoning mechanism.

Limitation

The study fixes a defined set of experimental assumptions rather than exhaustively varying models, hyperparameters, or implementations. These design choices may change quantitative performance without altering the central conclusions.

  • The analysis does not exhaustively explore model variants, hyperparameters, or alternative implementation choices.It instead presents a coherent framework and empirical analysis under fixed experimental assumptions.
  • Different search depths, evaluation signals, and compute-allocation strategies may produce quantitative performance variations.

A Organization of the Appendix

The appendix progresses from foundational search paradigms to methodological taxonomies, unified notation, evaluation standards, and open challenges. It connects classical search concepts with practical MCTS-based reasoning and standardized compute reporting.

  • Foundational Paradigms: The appendix begins with uninformed search, heuristic-guided search, and MCTS to establish shared primitives and computational trade-offs.
  • Theoretical Distinctions: Test-time optimization is framed as search in task-defined objective space, while reward is distinguished as transient guidance rather than persistent learning.
  • Methodological Taxonomy: The methodological core systematizes MCTS notation, evaluation loci, backup strategies, and heuristic-guided alternatives.
  • Standardized Evaluation Protocols: The appendix introduces hardware-agnostic test-time compute reporting, including FLOP estimation, wall-clock profiling, Budgeted Accuracy, and Tokens-per-Solved.
  • Practitioner’s Guide with Unified Notation: A practitioner guide normalizes states, actions, nodes, evaluation functions, and backup rules for side-by-side comparison.
  • Challenges and Future Directions: Open challenges include overthinking, efficiency bottlenecks in deep or wide search, and reliance on high-quality reward models.

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

The paper contrasts training-time optimization of model parameters with test-time search over reasoning traces for a fixed model. It then extends test-time search to jointly optimize reasoning structures and solutions, while distinguishing transient search rewards from durable learning signals.

  • Training-Time Scaling: Training-time scaling minimizes expected loss over a data distribution by updating parameters in a high-dimensional latent space.The resulting trained model is a static artifact representing a posterior distribution over solutions.
  • Test-Time Scaling: Test-time scaling searches a discrete solution space of reasoning traces for a specific problem using a fixed pretrained model and an inference compute budget.Scalar rewards or values evaluate traces, while intermediate feedback can redirect computation toward promising regions.
  • Tree Search as a Scalable Inference Optimizer: Tree search operationalizes inference optimization by balancing exploitation and exploration through policy priors, node values, visit counts, and uncertainty bonuses.
  • Prompt and Answer Spaces: Test-time search decomposes into Prompt Space, which selects reasoning structures, and Answer Space, which contains traces generated under each structure.Prompt templates function as algorithms and can substantially alter the complexity of the corresponding answer space.
  • Prompt and Answer Spaces: Many current methods search within a fixed answer space, leaving systematic exploration of the prompt space largely open.
  • Reward as Guidance vs. Learning Signal: Rewards in search provide transient, instance-specific guidance, whereas reinforcement learning uses rewards to update parameters and shape durable policies.

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

The guide maps search topology, evaluation signals, and backup dynamics to task characteristics such as error propagation, reward sparsity, and oracle availability. It also surveys efficiency improvements, reward-model developments, multi-agent extensions, and domain-specific MCTS applications.

  • General Principles: Optimal search configurations vary with node granularity, evaluation signals, and backpropagation logic, which reflect domain-specific reward and error properties.
  • Mathematical Reasoning: Mathematical reasoning benefits from trace-based nodes and process-level evaluation because a single logical error can invalidate later steps.Average or sum backups favor paths with consistently correct rollouts over lucky guesses.
  • Code Generation: Code generation can use terminal-state nodes, execution feedback, and max backups because compilers and tests provide binary pass/fail signals.
  • RAG & Knowledge Tasks: Knowledge-intensive tasks separate retrieval from reasoning actions and combine relevance and factual-consistency evaluation.This reflects the weakest-link requirement between document relevance and answer correctness.
  • Autonomous Agents: Agent planning uses MCTS as a lookahead planner with the LLM serving as a simulator in partially observable environments.
  • Emerging Directions: Recent directions include multi-agent collaboration, debate, specialized roles, process and outcome reward models, and hybrid reward designs.
  • Efficiency and Adaptation: Efficiency research dynamically allocates exploration budgets, improves node selection, and addresses the high computational cost of tree search.
  • Code Generation & Software Engineering: MCTS supports code reasoning and software engineering by exploiting compiler, test-suite, and formal-verifier feedback to refine or validate candidate implementations.

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

MCTS-based approaches extend reasoning by making retrieval dynamic and iterative, while search trajectories also support synthetic-data generation and self-improvement across text, multimodal, and specialized tasks.

  • RAG & Knowledge-Intensive Tasks: MCTS transforms static, one-shot retrieval into an iterative loop that decides when to query external knowledge and what to ask at each reasoning step.Retrieved information can verify facts, fill knowledge gaps, and correct reasoning as the solution is built incrementally.
  • Multimodal Tasks: MCTS-based multimodal methods explore interactions between images, video, and text by retrieving supporting insights during reasoning.AR-MCTS uses active retrieval from a hybrid-modal corpus at each reasoning step to support generated explanations.
  • Self-Improvement: MCTS generates high-quality reasoning trajectories that can become synthetic data for fine-tuning language models or reward models.This creates a self-improvement cycle in which search outputs are reused for training.
  • Self-Improvement: Self-training frameworks iteratively improve policy and value or reward models using verified rollouts, preference pairs, and methods such as DPO.rStar-Math and AlphaLLM use extensive MCTS rollouts to generate step-by-step reasoning data for training the LLM and process preference model.
  • Broader Applications: MCTS-based data generation extends to prompt optimization, instruction tuning, specialized domains, and multimodal process supervision.These pipelines can include successful reasoning, failure recovery, synthetic tabular data, multi-agent data, and step-level annotations for VLM training.

F Informed Search Based Method

Informed search structures LLM reasoning as heuristic-guided tree traversal, progressing from ToT’s BFS and DFS to A*-style methods that combine path costs with learned or LLM-derived estimates.

  • Overview: Informed search navigates large reasoning spaces with heuristic guidance rather than relying only on sequential generation.The approach treats problem-solving as tree traversal and prioritizes promising regions of the solution space.
  • Tree-of-Thoughts: Tree-of-Thoughts represents partial reasoning as states and combines problem structuring, thought generation, state evaluation, and search strategy.Each state contains the input and thoughts generated so far.
  • Tree-of-Thoughts: ToT generates candidate thoughts by either independently sampling them from a CoT prompt or proposing them sequentially with a propose prompt.These alternatives support different thought-generation settings, including expansive thought spaces.
  • Tree-of-Thoughts: ToT’s informed BFS maintains a beam of b states per depth, while its DFS follows one path until the evaluator value falls below a threshold.BFS limits exponential growth for fixed-depth problems; DFS truncates paths judged insufficiently promising.
  • A*-Based Search: A*-based methods prioritize nodes with f(n) = g(n) + h(n), combining accumulated path cost with estimated future cost.ToolChain* and Q* construct these costs from LLM-relevant signals, including memory, self-consistency, process rewards, and Q-values.
  • A*-Based Search: Q* approximates future reward with the maximum Q-value among top-k policy actions, but proxy-Q generalization and computational savings are not guaranteed.Proxy Q-values may be learned from offline reinforcement learning, MCTS rollouts, or distillation from a stronger LLM.
  • Evaluation Context: The survey examines mathematical reasoning because deterministic success criteria enable high-resolution analysis of tree-search test-time scaling.Its GSM8K and MATH case study also exposes broader fragmentation in reporting and compute accounting.

G.1 The Landscape of Mathematical Reasoning and the Infeasibility of Retrospective Comparison

On GSM8K and MATH, MCTS variants such as MCTSr and rStar-Math are reported on a Pareto frontier against standard baselines, but existing results cannot support a strictly compute-normalized ranking.

  • Landscape: MCTSr and rStar-Math populate a reported Pareto frontier that dominates standard baselines on the surveyed GSM8K and MATH landscape.The paper frames this pattern as model–search equivalence, where smaller models with search can rival larger static models.
  • Comparison Limitations: A fair retrospective compute-normalized comparison is infeasible because published tree-search studies use heterogeneous methods, hardware, verifier costs, and parameter scales.Opaque reward-model token overhead prevents complete FLOPs calculation, hardware differences invalidate wall-clock comparisons, and baselines range from roughly 7B to 70B+ parameters.
  • Comparison Limitations: An apples-to-apples ranking would require re-implementing and re-evaluating all surveyed methods from scratch, exceeding this survey’s scope.The paper therefore favors a forward-looking protocol over an imprecise retrofit of past results.

G.2 Proposed Protocol: A Universal Framework for Compute Accounting (SCRP)

SCRP offers a minimal reporting framework for making test-time compute explicit and comparable without retroactively adjusting prior baselines, using a unified resource vector and standardized metrics.

  • SCRP: SCRP provides an actionable recipe for future compute comparability without requiring retroactive adjustments to baseline data.It addresses the reporting fragmentation identified in the surveyed literature.
  • Resource Accounting: The unified budget vector B = (Cpolicy, Ceval, Cverify, Twall) separates policy generation, node evaluation, external verification, and wall-clock time.FLOPs serve as the primary hardware-agnostic independent variable, with dense-transformer inference approximated as C ≈2PT.
  • Standardized Metrics: SCRP recommends Budgeted Accuracy, Tokens-per-Solved, and Parallelism Efficiency to expose accuracy–compute trade-offs and search efficiency.Budgeted Accuracy is defined as Q(b) = E[Acc | Ctotal ≤b], while Parallelism Efficiency compares theoretical FLOPs with realized wall-clock speedup.

H Practitioner’s Guide with Unified Notation

The surveyed methods adapt tree search to LLM reasoning through different goals, evaluation signals, and search dynamics. Across examples, systems use process or outcome feedback, self-evaluation, refinement, and adaptive exploration to improve reasoning, code, translation, or agent recovery.

  • Step-driven reasoning: ReST-MCTS* discovers high-quality reasoning traces with process rewards and iteratively trains improved reward and policy models.It reports superior reasoning-trace quality on MATH, GPQA, and CEval versus baselines without MCTS.
  • Goal-driven planning: RAP uses the same LLM as reasoning policy and world model to simulate state transitions and provide per-step rewards during MCTS.This reduces reliance on pretraining or additional reward models while improving efficiency and accuracy across Blocksworld and logical reasoning tasks.
  • Solution refinement and feedback: LLaMA-Berry builds trees from complete solution nodes and ranks refinements with pairwise preference rewards, while RethinkMCTS corrects erroneous thoughts using execution feedback.LLaMA-Berry emphasizes solution refinement; RethinkMCTS reports notable gains on APPS and HumanEval.
  • Hybrid evaluation: HiAR-ICL combines hierarchical trajectory refinement with PRM, ORM, and self-consistency signals to support both intermediate and terminal evaluation.The hybrid design targets adaptability across reasoning and coding benchmarks.
  • Self-training and recovery: Agent-R converts complete-trajectory failures into corrective training examples, unlike RAP’s dense per-step world-model rewards.Its iterative self-training targets error recovery in interactive environments.
  • Search-control adaptations: MASTER removes MCTS simulation and derives rewards from LLM self-assessment, whereas AB-MCTS uses Thompson Sampling to choose between widening and deepening the tree.AB-MCTS introduces a GEN node for generating new children and supports theoretically unbounded branching.
  • Self-evaluation and specialized search: SELT eliminates external pretrained reward models through LLM self-evaluation, while G-MCTS expands translation trees with Merge and Mutate genetic operators.SELT decomposes problems into atomic subtasks and uses semantic clustering; G-MCTS represents complete translation candidates as nodes.

I Challenges and Future of Tree-Search Methods

Tree-search reasoning faces substantial computational, evaluation, and scalability challenges. Future work must improve search efficiency, avoid overthinking, strengthen reward models, and address limited parallelism through self-play and internalization.

  • Search Efficiency and Intelligence: Tree search can require more than 10 times the computational resources of greedy decoding in some cases, creating a barrier to practical deployment.Sequential generation of multiple solutions at each node can further increase resource demands.
  • Overthinking Issues in Simple Queries: Tree-search systems may overanalyze simple queries, wasting computation, causing delays, and potentially introducing errors.The paper calls for dynamic allocation that recognizes when straightforward questions need little reasoning.
  • Self-play Between Policy Models and Reward Models: Limited parallelism can constrain search speed, while self-play traces can refine policy and reward models and internalize tree-search reasoning into the policy.Embedding search-derived reasoning within a Chain-of-Thought framework may improve efficiency and scalability.
  • Reward Modeling and Reward Model Training: Automated process-reward construction remains concentrated in mathematics and programming, with broader scientific and complex reasoning domains still requiring human evaluation.The survey highlights the need for efficient fine-grained reward generation and scalable techniques.
  • Reward Model Quality and Its Effect on Search: Imperfect learned reward models can make expanding the search space reduce performance, producing inverse inference scaling and a persistent gap from oracle verifiers.The paper identifies bridging trained and oracle process-reward models as a pivotal challenge for large-scale search.
Loading 2608.30395v1…