Lune

EMNLP Findings2023

Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions

Shulin Cao, Jiajie Zhang, Jiaxin Shi, Xin Lv, Zijun Yao, Qi Tian, Lei Hou, Juanzi Li

Abstract

Large language models (LLMs) are capable of answering knowledge-intensive complex questions with chain-of-thought (CoT) reasoning. However, they tend to generate factually incorrect reasoning steps when the required knowledge is not available or up-to-date in models' parameters. Recent works turn to retrieving external knowledge to augment CoT reasoning. Despite being promising, these chain-based methods suffer from: 1) Negative retrieval. Unnecessary or incorrect retrieval may mislead the reasoning; 2) Limited sight. Lacking the ability to look backward or forward, a local error in one step will propagate along the chain.

In this paper, we propose a novel approach: Probabilistic Tree-of-thought Reasoning (ProbTree). First, LLMs translate a complex question into a query tree, in which each non-root node denotes a sub-question of its parent node. Then, probabilistic reasoning is conducted over the tree, by solving questions from leaf to root considering the confidence of both question decomposing and answering. During reasoning, for leaf nodes, LLMs choose a more confident answer from Closed-book QA that employs parametric knowledge and Openbook QA that employs retrieved external knowledge, thus eliminating the negative retrieval problem. For non-leaf nodes, with the hierarchical structure, LLMs have broader sights and are able to globally reason with the information from child nodes, thus recovering from local errors. The experiments on three Complex QA datasets under the open-domain setting show that our approach outperforms SOTA methods significantly, demonstrating the effect of probabilistic tree-of-thought reasoning.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

14 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Language Models are Few-Shot Learners
  • Tree of Thoughts: Deliberate Problem Solving with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • AtomR: Atomic Operator-Empowered Large Language Models for Heterogeneous Knowledge Reasoning cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
  • AtomR: Atomic Operator-Empowered Large Language Models for Heterogeneous Knowledge Reasoning cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
  • Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future cites Large Language Models are Zero-Shot Reasoners
  • Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future cites Language Models are Few-Shot Learners
  • Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Analytica: Soft Propositional Reasoning for Robust and Scalable LLM-Driven Analysis cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • PruneRAG: Confidence-Guided Query Decomposition Trees for Efficient Retrieval-Augmented Generation cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
  • PruneRAG: Confidence-Guided Query Decomposition Trees for Efficient Retrieval-Augmented Generation cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Large Language Models are Zero-Shot Reasoners cites Language Models are Few-Shot Learners
  • Large Language Models are Zero-Shot Reasoners cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • Large Language Models are Zero-Shot Reasoners cites Training language models to follow instructions with human feedback
  • BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering cites Tree of Thoughts: Deliberate Problem Solving with Large Language Models
  • BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering cites Large Language Models are Zero-Shot Reasoners
  • BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering cites Language Models are Few-Shot Learners
  • BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
  • BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question Answering cites Training language models to follow instructions with human feedback
  • Chain-of-Thought Prompting Elicits Reasoning in Large Language Models cites Training language models to follow instructions with human feedback
  • Training language models to follow instructions with human feedback cites Language Models are Few-Shot Learners
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers14

  1. Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and FutureZheng Chu, Jingchang Chen, Qianglong Chen, Weijiang Yu et al.ACL 2024 · 36 citations
  2. BeamAggR: Beam Aggregation Reasoning over Multi-source Knowledge for Multi-hop Question AnsweringZheng Chu, Jingchang Chen, Qianglong Chen, Haotian Wang et al.ACL 2024 · 8 citations
  3. Analytica: Soft Propositional Reasoning for Robust and Scalable LLM-Driven AnalysisJunyan Cheng, Kyle Richardson, Peter ChinICLR 2026 · 4 citations
  4. PruneRAG: Confidence-Guided Query Decomposition Trees for Efficient Retrieval-Augmented GenerationShuguang Jiao, Xinyu Xiao, Yunfan Wei, Shuhan Qi et al.WWW 2026 · 2 citations
  5. AtomR: Atomic Operator-Empowered Large Language Models for Heterogeneous Knowledge ReasoningAmy Xin, Jinxin Liu, Zijun Yao, Zhicheng Lee et al.KDD 2025 · 1 citation

Builds on15

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
  2. Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
  3. Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
  4. Large Language Models are Zero-Shot ReasonersTakeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo et al.NeurIPS 2022 · 8,168 citations
  5. Tree of Thoughts: Deliberate Problem Solving with Large Language ModelsShunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran et al.NeurIPS 2023 · 5,068 citations

Related papers

  1. Tree-of-Reasoning Question Decomposition for Complex Question Answering with Large Language ModelsKun Zhang, Jiali Zeng, Fandong Meng, Yuanzhuo Wang et al.AAAI 2024 · 14 citations
  2. Unveiling Factual Recall Behaviors of Large Language Models through Knowledge NeuronsYifei Wang, Yuheng Chen, Wanting Wen, Yu Sheng et al.EMNLP 2024 · 3 citations
  3. Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM ReasoningZhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang et al.ICML 2025
  4. DeCoT: Debiasing Chain-of-Thought for Knowledge-Intensive Tasks in Large Language Models via Causal InterventionJunda Wu, Tong Yu, Xiang Chen, Haoliang Wang et al.ACL 2024
  5. ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge GraphsMinbae Park, Hyemin Yang, Jeonghyun Kim, Kunsoo Park et al.AAAI 2026
Dusk over the sea between two cliffs drawn in fine vertical lines