# STOC-TOT: Stochastic Tree-of-Thought with Constrained Decoding for Complex Reasoning in Multi-Hop Question Answering

arXiv: https://arxiv.org/abs/2407.03687 · HTML: https://mlsanity.com/paper/2407.03687/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 4 Jul 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 5 of 5)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Retrieving and Reading: A Comprehensive Survey on Open-domain Question Answering](https://mlsanity.com/paper/2101.00774/) (2021)
- [End-to-End Beam Retrieval for Multi-Hop Question Answering](https://mlsanity.com/paper/2308.08973/) (2023)

## Built on by (most cited first, 5 of 5)

- [OPTAGENT: Optimizing Multi-Agent LLM Interactions Through Verbal Reinforcement Learning for Enhanced Reasoning](https://mlsanity.com/paper/2510.18032/) (2025)
- [Bridging Literature and the Universe Via A Multi-Agent Large Language Model System](https://mlsanity.com/paper/2507.08958/) (2025)
- [JudgeBoard: Benchmarking and Enhancing Small Language Models for Reasoning Evaluation](https://mlsanity.com/paper/2511.15958/) (2025)
- [Do Large Language Models Truly Grasp Mathematics? An Empirical Exploration From Cognitive Psychology](https://mlsanity.com/paper/2410.14979/) (2024)
- [Rosetta Memory: Adaptive Memory for Cross-LLM Agents](https://mlsanity.com/paper/2606.07711/) (2026)

## Abstract (arXiv)

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 two MHQA datasets and five large language models showed that our framework outperforms other reasoning prompts by a significant margin.