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

• URL: http://arxiv.org/abs/2608.30395v1
• Date: Mon, 31 Aug 2026 07:49:56 GMT
• Title: When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
• Abstract summary: Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior.<n>This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding.
• Score: 92.71325249013535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Test-Time Scaling in Reasoning LLMs: Inference Regimes, Evaluation, and Reproducibility [7.838210213616623]
  We develop a systematic account of test-time scaling along three axes.<n>First, we formalize test-time scaling as budgeted inference over the implicit prefix tree of an autoregressive model.<n>Second, we treat the evaluated object as the entire inference system.
  arXiv  Detail & Related papers  (2026-08-04T17:57:20Z)
• Aligning Large Vision-Language Models at Test Time: A Trajectory-Guided Structured Sampling Approach [26.437913669133874]
  Post-training reinforcement learning algorithms are commonly used to align vision-language models with human intent.<n>Existing RL-based alignment methods are often resource-intensive and encounter mismatches between training objectives and inference-time distributions.<n>We propose a novel test-time alignment approach that leverages trajectory-guided structured sampling for dynamic inference-time refinement.
  arXiv  Detail & Related papers  (2026-08-04T06:47:08Z)
• TELLER: Non-intrusive Cross-Layer Root-Cause Analysis for LLM Inference [47.62941623025392]
  We present TELLER, a non-intrusive and Log-aware LLM inference Root-cause analysis framework.<n>TELLER collects NVTX/CUPTI traces and service logs without modifying model binaries.<n>It reconstructs per-request call-chain trees and aligns log lines with corresponding execution steps.<n>On top of these representations, TELLER combines numeric candidate localization with a multimodal root-cause model.
  arXiv  Detail & Related papers  (2026-08-03T09:39:11Z)
• When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning [9.841011897729338]
  Training large language models (LLMs) with extended reasoning has enabled in-context search.<n>We provide a theoretical analysis of incontext search by modeling it as approximate inference over reasoning traces.<n>We show that when reflections reliably localize early mistakes, incontext search can yield exponential improvements over the base model.
  arXiv  Detail & Related papers  (2026-07-07T18:36:04Z)
• Beyond Semantic Similarity: Rethinking Retrieval for Agentic Search via Direct Corpus Interaction [127.64173950476702]
  We study direct corpus interaction (DCI), where an agent searches the raw corpus directly with general-purpose terminal tools.<n>This approach requires no offline indexing and adapts naturally to evolving local corpora.<n>Across IR benchmarks and end-to-end agentic search tasks, this simple setup substantially outperforms strong sparse, dense, and reranking baselines.
  arXiv  Detail & Related papers  (2026-05-03T19:13:11Z)
• VAR: Visual Attention Reasoning via Structured Search and Backtracking [49.427842994857635]
  We introduce Visual Attention Reasoning, a framework that recasts grounded reasoning as a structured search.<n> VAR decomposes the reasoning process into two key stages: traceable evidence grounding and search-based chain-of-thought.<n>We show that our 7B model, VAR-7B, sets a new state-of-the-art on a comprehensive suite of hallucination and safety benchmarks.
  arXiv  Detail & Related papers  (2025-10-21T13:18:44Z)
• Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey [92.71325249013535]
  Deliberative tree search is a cornerstone of Large Language Model (LLM) research.<n>This paper introduces a unified framework that deconstructs search algorithms into three core components.
  arXiv  Detail & Related papers  (2025-10-11T03:29:18Z)
• Implicit Reasoning in Large Language Models: A Comprehensive Survey [67.53966514728383]
  Large Language Models (LLMs) have demonstrated strong generalization across a wide range of tasks.<n>Recent studies have shifted attention from explicit chain-of-thought prompting toward implicit reasoning.<n>This survey introduces a taxonomy centered on execution paradigms, shifting the focus from representational forms to computational strategies.
  arXiv  Detail & Related papers  (2025-09-02T14:16:02Z)
• Test-time Prompt Intervention [22.35022545068874]
  We propose PI, a novel framework for Test-time Prompt Intervention.<n> PI provides an interface to dynamically guide and regulate reasoning paths during inference.<n>This allows human problem-solving expertise and cognitive science principles to be seamlessly integrated into LLMs' reasoning processes.
  arXiv  Detail & Related papers  (2025-08-04T15:17:13Z)
• MCTS-RAG: Enhancing Retrieval-Augmented Generation with Monte Carlo Tree Search [61.11836311160951]
  We introduce MCTS-RAG, a novel approach that enhances the reasoning capabilities of small language models on knowledge-intensive tasks.<n>Unlike standard RAG methods, which typically retrieve information independently from reasoning, MCTS-RAG combines structured reasoning with adaptive retrieval.<n>This integrated approach enhances decision-making, reduces hallucinations, and ensures improved factual accuracy and response consistency.
  arXiv  Detail & Related papers  (2025-03-26T17:46:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.