S to C - TOT : Stochastic Tree-of-Thought with Constrained Decoding for Complex Reasoning in Multi-Hop Question Answering (2025)

Abstract: Multi-hop question answering (MHQA) requires a model to retrieve and integrate information from multiple passages to answer a complex question. Recent systems leverage the power of large language models and integrate evidence retrieval with reasoning prompts (e.g., chain-of-thought reasoning) for the MHQA task. However, the complexities in the question types (bridge v.s. comparison questions) and the reasoning types (sequential v.s. parallel reasonings) require more novel and fine-grained prompting methods to enhance the performance of MHQA under the zero-shot setting.In this paper, we propose StoC-ToT, a stochastic tree-of-thought reasoning prompting method with constrained decoding for MHQA and conduct a detailed comparison with other reasoning prompts on different question types and reasoning types. Specifically, we construct a tree-like reasoning structure by prompting the model to break down the original question into smaller sub-questions to form different reasoning paths. In addition, we prompt the model to provide a probability estimation for each reasoning path at each reasoning step. At answer time, we conduct constrained decoding on the model to generate more grounded answers and reduce hallucination. Experiments comparing StoC-ToT with on two MHQA datasets and five large language models showed that outperforms other reasoning prompts by a significant margin.

## introduction question answering (qa) is a fundamental task in natural language processing (nlp) that involves designing systems capable of understanding human language questions and providing accurate and relevant answers. with the recent advancement of large language models (llms) that demonstrated superior reasoning ability @xcite , researchers have been focusing more on complex qa tasks, such as multi-hop question answering figure 1 : an example of the mhqa question. this question has two hops that require the model to reason about before answering the final question. state-of-the-art methods for mhqa are fullysupervised methods that often follow a retrieveand-read framework, including a passage retrieving module that gathers relative evidence from documents and a reading comprehension module to reason about the evidence @xcite . other methods include beam-search @xcite and label-smoothing @xcite . however, these methods often require extensive pre-training or fine-tuning and do not generalize well to other datasets. large language models (llms), on the other hand, show remarkable reasoning ability and rich knowledge of general-domain questions. many llms can answer simple and straightforward questions that do not require complex reasoning without any supervision involved but often fail to deal with complex questions requiring multiple reasoning steps. to tackle the problem, researchers have developed many prompting techniques to improve llm's reasoning ability, such as chain-of-thought (cot) @xcite , self-consistency cot (sc-cot) @xcite , and tree-of-thought (tot) prompting @xcite . cot has been shown effective across tasks requiring extensive, step-by-step reasoning, such as math calculation and reading comprehension. however, there could be various possible reasoning paths for many complex multi-hop questions, and cot models cannot "turn back" when they have made a mistake along their reasoning paths. sc-cot further improves on cot by proposing different chains of thought, thus expanding the reasoning space. however, there is no local reasoning expansion within each chain, and the "majority voting" strategy often fails in open-domain tasks where the output space is unlimited. tot, designed to maintain different reasoning paths along its reasoning process, is more suitable for dealing with complex question types. however, the intermediate reasoning steps in nlp generation tasks are much less constrained and require more than a simple rulebased evaluation. the complexities in the question types (bridge v.s. comparison questions in to tackle the challenges and design a more reliable reasoning method for open-domain nlp tasks, we propose stoc-tot, a stochastic tot-based framework that instructs the model to generate different reasoning paths from the same question and assign probability scores to reasoning paths to effectively avoid reasoning dead-ends. to the best of our knowledge, our work is the first to adapt the tree-of-thought reasoning prompting to natural language tasks that require complex reasoning, such as mhqa. we provide an example overview of our framework in figure 2 . specifically, we construct a tree-like reasoning structure by prompting the model to break down the original question into smaller sub-questions to form different reasoning paths. we evaluate the validity of each reasoning path on three levels of aspects and arrive at a model-given probability score. at answer time, we innovatively propose to use constrained decoding in the answering process to reduce hallucination by forcing the model to generate grounded answers from evidence and letting models give concise and exact answers. ultimately, we arrive at the best answer by choosing the path with the highest aggregated probability score. experiments on two benchmarking mhqa datasets demonstrate that stoc-tot significantly improves the reasoning ability of llms in complex reasoning scenarios, especially with gpt-4, improving exact match accuracy by 7%, and f1 score by 7.8 points on the hotpotqa dataset over the original tree-of-thought prompting. our contributions are as follows: reasoning prompting of llms various prompt engineering methods have been developed @xcite @xcite @xcite , aiming to improve large language models' reasoning ability across various tasks and domains. chain-of-thought (cot) prompting @xcite prompts the large language models (llms) to divide their reasoning process into smaller evidence: 1. ice cube is an american singer and actor who... 2. jackie chan is an actor... who received the 2016 academy honorary award... 3. ... vocabulary bank actor, academy, honorary, award, ice, cube, jackie, chan, ... constrained decoding from vocabulary bank paraphrase detection evidence retrieval and ranking prompt: is the subquestion asking the same thing as the original question? evidence selected: 3, 6 and 17 answer: jackie chan original question: the actor who received the 2016 academy honorary award co-starred which movie with chris tucker? question breakdown and generation thought: i could first..., or... sub-question 1: which actor received the 2016 academy honorary award? sub-question 2: which star co-starred a movie with chris tucker? validity evaluation (stochastic tree-building) evidence retrieval and ranking evidence selected: 1, 3 and 5 answer: ice cube, charlie sheen, jackie chan paraphrase detection prompt: is the subquestion asking the same thing as the original question? prompt: what is your evaluation on the reasoning paths? your answer should be based on three metrics: question-level, reasoninglevel, and answer-level. answer: left probability: 70% right probability: 30% evidence list vocabulary bank constrained decoding from vocabulary bank original question answer: jackie chan prob: 70% 3 answers prob: 30% answer: rush hour prob: 100% agg. prob: 70% answer: friday prob: 30% agg. prob: 9% answer: money talks prob: 30% agg. prob: 12% answer: rush hour prob: 40% agg. prob: 12% steps when solving a question, forming a chain of thoughts. chain-of-thought self-consistency prompting @xcite improves on the cot method by proposing different reasoning chains and ensembles on the final result. tree-of-thought (tot) prompting method @xcite actively maintains a tree of thoughts, where each thought is a coherent language sequence that serves as an intermediate step toward problem-solving. graph-of-thought @xcite further improves tot by constructing a directed graph instead of a tree. llms can loop over a thought to refine it and aggregate thoughts or chains. constrained decoding constrained decoding is the technique that asks the models to generate outputs following a given set of rules. the most common way of conducting constrained generation uses beam search (och and ney, 2004) in decoding time. before the llm era, works on constrained decoding focused on task-specific sequence-tosequence models that span across many fields, such as machine translation @xcite , named entity recognition @xcite , and dialogue generation @xcite . recently, microsoft introduced guidance 1 , which allows users of various 1 https://github.com/guidance-ai/guidance large language models to control their outputs given a human-defined vocabulary or rules. ## experimental setup dataset we compare stoc-tot with baseline methods on the hotpotqa dataset @xcite and the musique dataset @xcite , both of which are widely used mhqa datasets across state-of-the-art mhqa baselines. the experiments are conducted under the distractor setting, where we provide the model with an evidence pool containing both golden and irrelevant evidence. the model needs to find the golden evidence to answer the question correctly. we randomly selected 200 examples from each dataset as our evaluation set. baselines we included three baselines: we only provide the model with questions and evidence and instruct it to output the answer. we recognize that there are llm-based retrieval augmented generation frameworks @xcite @xcite ) that were also evaluated on hotpotqa. however, we excluded them from our baselines as they used outside knowledge bases, which are under a different testing scenario. ## conclusion this paper proposes stoc-tot, a stochastic tree-of-thought reasoning framework with constrained generation for multi-hop question answering. stoc-tot is specialized in dealing with complex reasoning scenarios in natural language tasks. experiments on two benchmark datasets show that our framework outperforms previous reasoning prompting techniques with multiple large language models. detailed analysis shows that our framework is capable of building a robust reasoning process given different types of questions. further research can aim to enhance the reliability of our framework by proposing better validity evaluation schemes and more effective methods for improving groundedness and preventing hallucination.