PathFinder: Guided Search over Multi-Step Reasoning Paths

• URL: http://arxiv.org/abs/2312.05180v2
• Date: Tue, 12 Dec 2023 16:06:32 GMT
• Title: PathFinder: Guided Search over Multi-Step Reasoning Paths
• Authors: Olga Golovneva, Sean O'Brien, Ramakanth Pasunuru, Tianlu Wang, Luke Zettlemoyer, Maryam Fazel-Zarandi, Asli Celikyilmaz
• Abstract summary: We propose PathFinder, a tree-search-based reasoning path generation approach. It enhances diverse branching and multi-hop reasoning through the integration of dynamic decoding. Our model generalizes well to longer, unseen reasoning chains, reflecting similar complexities to beam search with large branching factors.
• Score: 80.56102301441899
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With recent advancements in large language models, methods like chain-of-thought prompting to elicit reasoning chains have been shown to improve results on reasoning tasks. However, tasks that require multiple steps of reasoning still pose significant challenges to state-of-the-art models. Drawing inspiration from the beam search algorithm, we propose PathFinder, a tree-search-based reasoning path generation approach. It enhances diverse branching and multi-hop reasoning through the integration of dynamic decoding, enabled by varying sampling methods and parameters. Using constrained reasoning, PathFinder integrates novel quality constraints, pruning, and exploration methods to enhance the efficiency and the quality of generation. Moreover, it includes scoring and ranking features to improve candidate selection. Our approach outperforms competitive baselines on three complex arithmetic and commonsense reasoning tasks by 6% on average. Our model generalizes well to longer, unseen reasoning chains, reflecting similar complexities to beam search with large branching factors.

Related papers

• GRITHopper: Decomposition-Free Multi-Hop Dense Retrieval [52.47514434103737]
  We introduce GRITHopper-7B, a novel multi-hop dense retrieval model that achieves state-of-the-art performance. GRITHopper combines generative and representational instruction tuning by integrating causal language modeling with dense retrieval training. We find that incorporating additional context after the retrieval process, referred to as post-retrieval language modeling, enhances dense retrieval performance.
  arXiv  Detail & Related papers  (2025-03-10T16:42:48Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree. We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference. Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• Policy Guided Tree Search for Enhanced LLM Reasoning [3.090041654375235]
  Policy-Guided Tree Search (PGTS) is a framework that combines reinforcement learning with structured tree exploration to efficiently navigate reasoning paths. Our key innovation is a learned policy that dynamically decides between expanding, branching, backtracking, or terminating exploration, eliminating the need for manuals or exhaustive search.
  arXiv  Detail & Related papers  (2025-02-04T22:08:20Z)
• Semantic Exploration with Adaptive Gating for Efficient Problem Solving with Language Models [8.295475330195993]
  We propose Semantic Exploration with Adaptive Gating (SEAG) to explore semantically identical paths. SEAG significantly improves accuracy by 4.3% on average while requiring only 31% of computational costs. Our experiments demonstrate that SEAG significantly improves accuracy by 4.3% on average while requiring only 31% of computational costs.
  arXiv  Detail & Related papers  (2025-01-10T07:02:43Z)
• Technical Report: Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research. We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• Reasoning Paths Optimization: Learning to Reason and Explore From Diverse Paths [69.39559168050923]
  We introduce Reasoning Paths Optimization (RPO), which enables learning to reason and explore from diverse paths. Our approach encourages favorable branches at each reasoning step while penalizing unfavorable ones, enhancing the model's overall problem-solving performance. We focus on multi-step reasoning tasks, such as math word problems and science-based exam questions.
  arXiv  Detail & Related papers  (2024-10-07T06:37:25Z)
• Guided Stream of Search: Learning to Better Search with Language Models via Optimal Path Guidance [17.28280896937486]
  We show how to leverage optimal solutions to enhance the search and planning abilities of language models. Our approach significantly enhances the search and planning abilities of language models on Countdown, a simple yet challenging mathematical reasoning task.
  arXiv  Detail & Related papers  (2024-10-03T21:07:59Z)
• What Matters in Hierarchical Search for Combinatorial Reasoning Problems? [0.0]
  Recent efforts have sought to enhance planning by incorporating hierarchical high-level search strategies, known as subgoal methods. While promising, their performance against traditional low-level planners is inconsistent, raising questions about their application contexts. We identify the attributes pivotal for leveraging the advantages of high-level search: hard-to-learn value functions, complex action spaces, presence of dead ends in the environment, or using data collected from diverse experts.
  arXiv  Detail & Related papers  (2024-06-05T15:14:58Z)
• FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering [46.41364317172677]
  We propose a retrieval augmented reasoning method, FiDeLiS, which enhances knowledge graph question answering. FiDeLiS uses a keyword-enhanced retrieval mechanism that fetches relevant entities and relations from a vector-based index of KGs. A distinctive feature of our approach is its blend of natural language planning with beam search to optimize the selection of reasoning paths.
  arXiv  Detail & Related papers  (2024-05-22T17:56:53Z)
• Tree-of-Mixed-Thought: Combining Fast and Slow Thinking for Multi-hop Visual Reasoning [16.495754104540605]
  Large language models (LLMs) can generate code-like plans for complex inference tasks such as visual reasoning. We propose a hierarchical plan-searching algorithm that integrates the one-stop reasoning (fast) and the Tree-of-thought (slow)
  arXiv  Detail & Related papers  (2023-08-18T16:21:40Z)
• Self-Polish: Enhance Reasoning in Large Language Models via Problem Refinement [50.62461749446111]
  Self-Polish (SP) is a novel method that facilitates the model's reasoning by guiding it to progressively refine the given problems to be more comprehensible and solvable. SP is to all other prompting methods of answer/reasoning side like CoT, allowing for seamless integration with state-of-the-art techniques for further improvement.
  arXiv  Detail & Related papers  (2023-05-23T19:58:30Z)
• Learning to Reason With Relational Abstractions [65.89553417442049]
  We study how to build stronger reasoning capability in language models using the idea of relational abstractions. We find that models that are supplied with such sequences as prompts can solve tasks with a significantly higher accuracy.
  arXiv  Detail & Related papers  (2022-10-06T00:27:50Z)
• Complexity-Based Prompting for Multi-Step Reasoning [72.0057198610614]
  We study the task of prompting large-scale language models to perform multi-step reasoning. A central question is which reasoning examples make the most effective prompts. We propose complexity-based prompting, a simple and effective example selection scheme for multi-step reasoning.
  arXiv  Detail & Related papers  (2022-10-03T05:33:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.