# Deductive Beam Search: Decoding Deducible Rationale for Chain-of-Thought Reasoning

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 37 of its 54 references that are in the map.
- First posted on arXiv 31 Jan 2024.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 37)

- [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)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [DeBERTaV3: Improving DeBERTa using ELECTRA-Style Pre-Training with Gradient-Disentangled Embedding Sharing](https://mlsanity.com/paper/2111.09543/) (2021)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [Solving General Arithmetic Word Problems](https://mlsanity.com/paper/1608.01413/) (2016)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [How Language Model Hallucinations Can Snowball](https://mlsanity.com/paper/2305.13534/) (2023)
- [Large Language Models are Better Reasoners with Self-Verification](https://mlsanity.com/paper/2212.09561/) (2022)
- [Faithful Chain-of-Thought Reasoning](https://mlsanity.com/paper/2301.13379/) (2023)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [REFINER: Reasoning Feedback on Intermediate Representations](https://mlsanity.com/paper/2304.01904/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning](https://mlsanity.com/paper/2308.00436/) (2023)
- [Minimizing the Accumulated Trajectory Error to Improve Dataset Distillation](https://mlsanity.com/paper/2211.11004/) (2022)
- [Deductive Verification of Chain-of-Thought Reasoning](https://mlsanity.com/paper/2306.03872/) (2023)

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

- [Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing](https://mlsanity.com/paper/2404.12253/) (2024)
- [AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2509.08755/) (2025)
- [Evaluating Step-by-step Reasoning Traces: A Survey](https://mlsanity.com/paper/2502.12289/) (2025)
- [Theoretical Benefit and Limitation of Diffusion Language Model](https://mlsanity.com/paper/2502.09622/) (2025)
- [How Easily do Irrelevant Inputs Skew the Responses of Large Language Models?](https://mlsanity.com/paper/2404.03302/) (2024)
- [LiteSearch: Efficacious Tree Search for LLM](https://mlsanity.com/paper/2407.00320/) (2024)
- [Thinking Machines: A Survey of LLM based Reasoning Strategies](https://mlsanity.com/paper/2503.10814/) (2025)
- [Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMs](https://mlsanity.com/paper/2502.02362/) (2025)
- [Revealing the Barriers of Language Agents in Planning](https://mlsanity.com/paper/2410.12409/) (2024)
- [Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls](https://mlsanity.com/paper/2502.11183/) (2025)
- [A Survey on Feedback-based Multi-step Reasoning for Large Language Models on Mathematics](https://mlsanity.com/paper/2502.14333/) (2025)
- [Video Models Can Reason with Verifiable Rewards](https://mlsanity.com/paper/2605.15458/) (2026)
- [Reflection-Window Decoding: Text Generation with Selective Refinement](https://mlsanity.com/paper/2502.03678/) (2025)
- [Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey](https://mlsanity.com/paper/2510.01925/) (2025)
- [Unraveling Misinformation Propagation in LLM Reasoning](https://mlsanity.com/paper/2505.18555/) (2025)
- [Beyond In-Distribution Success: Scaling Curves of CoT Granularity for Language Model Generalization](https://mlsanity.com/paper/2502.18273/) (2025)
- [Learning Adaptive Reasoning Paths for Efficient Visual Reasoning](https://mlsanity.com/paper/2604.14568/) (2026)
- [Stepwise Informativeness Search for Efficient and Effective LLM Reasoning](https://mlsanity.com/paper/2502.15335/) (2025)
- [Towards Reasoning for PDE Foundation Models: A Reward-Model-Driven Inference-Time-Scaling Algorithm](https://mlsanity.com/paper/2509.02846/) (2025)
- [Pyramid-Driven Alignment: Pyramid Principle Guided Integration of Large Language Models and Knowledge Graphs](https://mlsanity.com/paper/2410.12298/) (2024)
- [Think Twice Before You Write -- an Entropy-based Decoding Strategy to Enhance LLM Reasoning](https://mlsanity.com/paper/2604.00018/) (2026)
- [CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction](https://mlsanity.com/paper/2509.04733/) (2025)
- [Beyond Tokens: A Survey on Decoding Methods for Large Language and Vision-Language Models](https://mlsanity.com/paper/2608.14797/) (2026)
- [Provable Test-Time Scaling for Beam Search in LLM Reasoning](https://mlsanity.com/paper/2609.38672/) (2026)

## Abstract (arXiv)

Recent advancements have significantly augmented the reasoning capabilities of Large Language Models (LLMs) through various methodologies, especially chain-of-thought (CoT) reasoning. However, previous methods fail to address reasoning errors in intermediate steps, leading to accumulative errors. In this paper, we propose Deductive Beam Search (DBS), which seamlessly integrates CoT and deductive reasoning with step-wise beam search for LLMs. Our approach deploys a verifier, verifying the deducibility of a reasoning step and its premises, thus alleviating the error accumulation. Furthermore, we introduce a scalable and labor-free data construction method to amplify our model's verification capabilities. Extensive experiments demonstrate that our approach significantly enhances the base performance of LLMs of various scales (7B, 13B, 70B, and ChatGPT) across 8 reasoning datasets from 3 diverse reasoning genres, including arithmetic, commonsense, and symbolic. Moreover, our analysis proves DBS's capability of detecting diverse and subtle reasoning errors and robustness on different model scales.