T ree S earch at S em E val-2025 Task 8: M onte C arlo Tree Search for Question-Answering over Tabular Data (2025)

Abstract: Large Language Models (LLMs) can answer diverse questions but often generate factually incorrect responses. SemEval-2025 Task 8 focuses on table-based question-answering, providing 65 real-world tabular datasets and 1,300 questions that require precise filtering and summarization of underlying tables.We approach this problem as a neuro-symbolic code generation task, translating natural language queries into executable Python code to ensure contextually relevant and factually accurate answers. We formulate LLM decoding as a Markov Decision Process, enabling Monte Carlo Tree Search (MCTS) as a lookahead-based planning algorithm while decoding from the underlying code-generating LLM, instead of standard beam search.Execution success on synthetic tests and real datasets serves as a reward signal, allowing MCTS to explore multiple code-generation paths, validate outcomes, assign value to partial solutions, and refine code iteratively rather than merely maximizing sequence likelihood in a single step. Our approach improves accuracy by 2.38x compared to standard decoding.

## introduction transformer-based llms @xcite excel at question answering (qa) @xcite but frequently generate plausible yet factually incorrect responses (hallucinations) @xcite . mitigating these errors is crucial for applications requiring precise, structured answers @xcite . one domain where factual consistency is critical is table-based qa, where answers must be derived from structured tabular data. semeval-2025 task 8 @xcite provides a benchmark for evaluating llms in this setting, requir-1 our code is available at: https://github.com/ huixinyang/semeval25-task8-adrianna-aakarsh-yang 2 full training dataset is available here. ## related work reinforcement learning (rl) planning, particularly monte carlo tree search (mcts) @xcite , has shown success in complex domains such as games and sql generation from natural language @xcite . while llms exhibit inherent reasoning capabilities (openai, 2024), incorporating explicit planning into their generation process is an active research area. approaches range from prompting strategies like chain-of-thought @xcite to models with dedicated search, reward, and reasoning components @xcite . ## our approach our approach applies planning-based transformer decoding @xcite to table-question answering. novel query program code synthesis is formulated as a markov decision process @xcite . a partial program along with its prompting description is considered to be a state s. the act of selecting a next-token from the underlying transformer vocabulary is considered an action a. thus transition function moves from one partial program to another by concatenating a selected token to one partial program to form another until a terminal token is appended. the reward for a program is a function of the validity of the program, along with the number of synthetic testcases the generated program passes. the aim is to use the llm to search for a path which maximizes expected future reward: n @xmath0, a t ). ## results as the mcts decoder does not rely on incontext learning, accuracy for both lite and base strategies is roughly equivalent. we note that the results requiring list outputs tend to have the worst performance. while boolean outputs have the highest accuracy level. ## conclusion we applied an mcts-based decoder @xcite for code generation in semeval-2025 task 8 table-qa. unlike conventional autoregressive methods that rely on greedy decoding or single-step chain-ofthought, our approach generates multiple candidate programs and refines them through look-ahead planning. experimental results show that mcts decoding achieves a substantial accuracy improvement (61.68% vs. 26% baseline decoding), demonstrating the effectiveness of search-based reasoning for code generation tasks. our techniques leverage strong open-source models to guide a smaller local model's decoding, enabling diverse solution generation. tree search with partial reward signals (e.g., passed tests, semantic type checks) refined solutions by balancing exploration and exploitation. experiments also revealed that list output types require more robust checks than atomic types, where rewards were better calibrated to accuracy. this work highlights tree-based planning's potential in code generation for table-centric qa, suggesting avenues for advanced reasoning techniques.