Combining LLMs with Logic-Based Framework to Explain MCTS Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA <<OpenReview submission id>>
Ziyan An, Xia Wang, Hendrik Baier, Zirong Chen, Abhishek Dubey, Taylor T. Johnson, Jonathan Sprinkle, Ayan Mukhopadhyay, Meiyi Ma · 2025
Read Combining LLMs with Logic-Based Framework to Explain MCTS Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA <<OpenReview submission id>> by Ziyan An, Xia Wang, Hendrik Baier, Zirong Chen, Abhishek Dubey, Taylor T. Johnson, Jonathan Sprinkle, Ayan Mukhopadhyay, Meiyi Ma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00610.txt.
Introduction
Monte Carlo Tree Search plans well but its huge search trees are hard to explain, which limits trust in AI planning. Ziyan An and co-authors build a framework that answers free-form questions about a search in plain language. A large language model drafts the explanation, while a logic layer based on Computational Tree Logic keeps it honest.
User questions are translated into logic statements, and evidence is pulled from the actual search tree. That design keeps answers consistent with the real environment dynamics and its constraints. Rigorous tests showed strong accuracy and factual consistency. The authors argue the pairing of language models with formal logic can make planning systems explainable without letting the explainer invent facts.
Catalog record
| CREATOR | Ziyan An, Xia Wang, Hendrik Baier, Zirong Chen, Abhishek Dubey, Taylor T. Johnson, Jonathan Sprinkle, Ayan Mukhopadhyay, Meiyi Ma |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 10 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00610
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Combining LLMs with Logic-Based Framework to Explain MCTS Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA <<OpenReview submission id>> Ziyan An, Xia Wang, Hendrik Baier, Zirong Chen, Abhishek Dubey, Taylor T. Johnson, Jonathan Sprinkle, Ayan Mukhopadhyay, Meiyi Ma Abstract . In response to the lack of trust in Artificial Intelligence (AI) for sequential planning, we design a Computational Tree Logic-guided large language model (LLM)-based natural language explanation framework designed for the Monte Carlo Tree Search (MCTS) algorithm. MCTS is often considered challenging to interpret due to the complexity of its search trees, but our framework is flexible enough to handle a wide range of free-form post-hoc queries and knowledge-based inquiries centered around MCTS and the Markov Decision Process (MDP) of the application domain. By transforming user queries into logic and variable statements, our framework ensures that the evidence obtained from the search tree remains factually consistent with the underlying environmental dynamics and any constraints in the actual stochastic control process. We evaluate the framework rigorously through quantitative assessments, where it demonstrates strong performance in terms of accuracy and factual consistency. Y. Vorobeychik, S. Das, A. Nowe (eds.) Extended Abstract Figure 1. We explain sequential planning by combining domain knowledge, search process, and logical reasoning. 1. Introduction Artificial Intelligence (AI) algorithms often operate as black-box systems, offering little to no insight into the reasoning behind their outputs. As a result, domain experts hesitate to deploy these algorithms in real-world settings due to concerns over transparency, understandability, and accountability, leaving them without a clear understanding of the implications or rationale behind the decisions made by these AI models ( Ma et al. 2020 ; Ma et al. 2021 ; Lundberg and Lee 2017 ; Ribeiro et al. 2016 ; Baier and Kaisers 2021 ; Marques-Silva and Ignatiev 2022 ) . One family of such AI approaches that is widely used in complex sequential planning problems such as manufacture engineering ( Saqlain et al. 2023 ) and transit route planning ( Weng et al. 2020 ) is Monte Carlo Tree Search (MCTS) ( Kocsis and Szepesvári 2006 ) . Understanding the results and decisions of MCTS is challenging even for experts due to the large, sampling-based search trees from which they are derived ( Baier and Kaisers 2020 ; An et al. 2024a ) . Therefore, we develop a logic-enabled large language models (LLMs) framework that integrates knowledge and symbolic reasoning with natural language, creating a robust yet expressive xAI system for explaining planning algorithms like MCTS (Figure 1 ). Aiming to address a flexible range of free-form user queries, our framework leverages advanced LLMs, which enables the development of xAI systems based on natural language ( Guha et al. 2024 ; Chen et al. 2024 ; Welleck et al. 2021 ) . More specifically, it offers broad flexibility in handling queries by converting natural language inquiries submitted via a chat interface into parameterized variables and logic expressions. It then evaluates the search tree based on the criteria specified by these logic expressions, and the results are presented in the final explanation, once again expressed in natural language. The framework also enables an unlimited number of follow-up queries, facilitating an interactive, back-and-forth communication with the user. 2. Method Background As the testbed for our framework, we use a paratransit planning scenario formulated as a Markov Decision Process (MDP). We define the state space, action space, constraints, and reward of the MDP. State transitions are driven by a simulated demand model for paratransit trip requests. We leverage MCTS to generate vehicle assignment decisions, which is initiated at each “decision epoch” ( Joe and Lau 2020 ) . Query Categories and Types The first category of queries, called post-hoc queries , seeks explanations for the returned plan after the algorithm has completed its execution and focuses on explaining specific MCTS decisions. The second category, called background knowledge-based queries , focuses on the MCTS decision-making process in general. After the user submits a query, and a Query-Classification LLM component interprets the new query and attempts to classify its intent to one of two categories. User queries are not restricted in terms of content or narration. However, to strategically address these queries, we pre-define 26 specific query types based on the user’s underlying intentions for the first category. In contrast, for the second category, queries answerable with background knowledge, there are no specific types, as one piece of knowledge can address multiple queries. Logic Generator and Parser Each pre-defined query type is associated with a few-shot prompt, containing example pairs of input queries and output logic. After a new query is classified into a specific query type, the corresponding prompt is used to guide the logic generation LLM component in formulating a logic statement for the query. We categorize all user questions based on the type of evidence required to answer them: those that can be addressed with base-level evidence, referring to information directly extracted from a tree node; those that rely on derived evidence, requiring consideration of multiple nodes across different depths or branches; and those that require logic comparison evidence, involving both multi-level calculations and comparisons between two branches using Computation Tree Logic (CTL) ( Clarke and Emerson 1981 ) . The variables are organized into a three-level hierarchical structure, where each level builds upon the variables and logic defined in the previous level. Logic Scorer To obtain both quantitative and qualitative evidence, we define scorer functions that take the MCTS tree including states and actions as input and return either numerical or boolean values based on the evaluation of specific criteria ( An et al. 2024b ) . For base-level variables, the result is obtained by identifying the target node corresponding to the variable through tree traversal. For derived evidence variables, we further define formulas to calculate the overall averaged quantitative result across all relevant nodes in the search tree. Lastly, we utilize CTL model checking algorithms to obtain logic comparison evidence, where the input is the MCTS tree. Knowledge Retrieval To provide domain knowledge-informed explanations for category two queries, we prepared a lightweight knowledge base containing approximately 3,000 words, divided into 34 chunks. This knowledge base covers background information on paratransit services and the MCTS algorithm, as well as detailed components of the MDP, including predefined constraints, algorithm objectives, and reward functions. We leverage the RAG technique with the OpenAI text-embedding-3-small model to obtain the top k results, passing information chunks to the LLM only if their relatedness scores exceed a predefined threshold. Generating Explanations Once the list of calculated evidence or retrieved domain knowledge is obtained, the framework engages with a Question-Answering LLM to generate the final response. Key pieces of information provided to the LLM include the original user query, the evidence variables used, the result from the scorer function obtained in the previous step, and the retrieved knowledge. Table 1. Quantitative evaluation results. Method Metric @ 1 \uparrow @ 3 \uparrow Llama3.1 FactCC / BERT 25.77% / 06.15% 34.62% / 12.31% Ours (Llama) FactCC / BERT 67.88% / 86.54% 83.27% / 97.50% GPT-4o FactCC / BERT 42.31% / 40.00% 51.15% / 55.77% Ours (GPT) FactCC