Toward Template-Free Explainability for Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2605.16524v2
• Date: Tue, 19 May 2026 21:16:55 GMT
• Title: Toward Template-Free Explainability for Monte Carlo Tree Search
• Abstract summary: Probabilistic search algorithms have proven very effective in solving sequential decision-making tasks under uncertainty.<n>We present a framework that enables large language models (LLMs) to generate evidence-grounded explanations of Monte Carlo Tree Search decisions.<n>Our framework maps natural-language questions to a structured set of intent categories, determines whether the existing tree contains sufficient evidence, triggers targeted expansion when needed, and generates explanations using tree statistics such as visit counts, value estimates, and risk information.
• Score: 7.879122162207435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic search algorithms, such as Monte Carlo Tree Search (MCTS), have proven very effective in solving sequential decision-making tasks under uncertainty. However, interpreting asymmetric search trees that incorporate bandit-based tree traversal and simulation-based value estimation is difficult for end users based solely on raw tree statistics. While prior work requires hand-crafted formal logic constraints that must be updated when the problem changes, we present a framework that enables large language models (LLMs) to generate evidence-grounded explanations of MCTS decisions from recorded search traces in an end-to-end manner. Our framework maps natural-language questions to a structured set of intent categories, determines whether the existing tree contains sufficient evidence, triggers targeted expansion when needed, and generates explanations using tree statistics such as visit counts, value estimates, and risk information. Experimental results provide the first evidence that LLMs can serve as end-to-end explainers for probabilistic search, without requiring intermediate formal representations.

Related papers

• When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models [92.71325249013535]
  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.
  arXiv  Detail & Related papers  (2026-08-31T07:49:56Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• Ensembling LLM-Induced Decision Trees for Explainable and Robust Error Detection [24.742137117129502]
  Error detection is important for ensuring data quality.<n>Recent state-of-the-art ED methods leverage the pre-trained knowledge and semantic capability embedded in large language models (LLMs) to directly label whether a cell is erroneous.<n>We propose an LLM-as-an-inducer framework that adopts LLM to induce the decision tree for ED (termed TreeED) and further ensembles multiple such trees for consensus detection (termed ForestED)<n>Our methods are accurate, explainable and robust, achieving an average F1-score improvement of 16.1% over the best baseline.
  arXiv  Detail & Related papers  (2025-12-08T07:40:48Z)
• Approximate Optimal Active Learning of Decision Trees [4.834817711255487]
  We consider the problem of actively learning an unknown binary decision tree using only membership queries.<n>We propose a symbolic method for active learning of decision trees, in which approximate model counting is used to estimate the reduction of the hypothesis space.<n> Experiments on decision trees show that the method reliably converges to the correct model using only a handful of queries.
  arXiv  Detail & Related papers  (2025-12-03T17:03:39Z)
• MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information [32.43291637979958]
  We propose Mutual Information Tree Search (MITS), a novel framework that guides reasoning with information-theoretic principles.<n>MITS introduces an effective scoring function based on pointwise mutual information (PMI), which enables step-wise evaluation of reasoning paths and search tree expansion.<n>For final prediction, MITS employs a weighted voting scheme that combines PMI scores with prediction consensus.
  arXiv  Detail & Related papers  (2025-10-04T02:30:40Z)
• Combining LLMs with Logic-Based Framework to Explain MCTS [13.276888833862447]
  We design a Computational Tree-guided large language model (LLM)-based natural language explanation framework for the Monte Carlo Tree Search (MCTS) algorithm.<n>By transforming user queries into logic and variable statements, our framework ensures that the evidence obtained from the search tree remains factually consistent.<n>We evaluate the framework rigorously through quantitative assessments, where it demonstrates strong performance in terms of accuracy and factual consistency.
  arXiv  Detail & Related papers  (2025-05-01T15:40:58Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data.<n>We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• Think&Cite: Improving Attributed Text Generation with Self-Guided Tree Search and Progress Reward Modeling [63.98194996746229]
  Large language models (LLMs) are prone to hallucination and producing factually incorrect information.<n>We propose a novel framework, called Think&Cite, and formulate attributed text generation as a multi-step reasoning problem integrated with search.
  arXiv  Detail & Related papers  (2024-12-19T13:55:48Z)
• Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models [56.32800938317095]
  Existing verifiers are sub-optimal for tree search techniques at test time.<n>We propose token-supervised value models (TVMs)<n>TVMs assign each token a probability that reflects the likelihood of reaching the correct final answer.
  arXiv  Detail & Related papers  (2024-07-12T13:16:50Z)
• Uncertainty-Guided Likelihood Tree Search [37.25859935454988]
  Tree search is a fundamental tool for planning, as many sequential decision-making problems can be framed as searching over tree-structured spaces.<n>We propose an uncertainty-guided tree search algorithm for settings where the reward function is a log-likelihood function of the paths.
  arXiv  Detail & Related papers  (2024-07-04T14:08:50Z)
• RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Trees [47.745218107037786]
  We propose RLET, a Reinforcement Learning based Entailment Tree generation framework. RLET iteratively performs single step reasoning with sentence selection and deduction generation modules. Experiments on three settings of the EntailmentBank dataset demonstrate the strength of using RL framework.
  arXiv  Detail & Related papers  (2022-10-31T06:45:05Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)

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.