Semantic Exploration with Adaptive Gating for Efficient Problem Solving with Language Models

• URL: http://arxiv.org/abs/2501.05752v1
• Date: Fri, 10 Jan 2025 07:02:43 GMT
• Title: Semantic Exploration with Adaptive Gating for Efficient Problem Solving with Language Models
• Authors: Sungjae Lee, Hyejin Park, Jaechang Kim, Jungseul Ok,
• Abstract summary: 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.
• Score: 8.295475330195993
• License:
• Abstract: Recent advancements in large language models (LLMs) have shown remarkable potential in various complex tasks requiring multi-step reasoning methods like tree search to explore diverse reasoning paths. However, existing methods often suffer from computational inefficiency and redundancy. First, they overlook the diversity of task difficulties, leading to unnecessarily extensive searches even for easy tasks. Second, they neglect the semantics of reasoning paths, resulting in redundant exploration of semantically identical paths. To address these limitations, we propose Semantic Exploration with Adaptive Gating (SEAG), a computationally efficient method. SEAG employs an adaptive gating mechanism that dynamically decides whether to conduct a tree search, based on the confidence level of answers from a preceding simple reasoning method. Furthermore, its tree-based exploration consolidates semantically identical reasoning steps, reducing redundant explorations while maintaining or even improving accuracy. Our extensive experiments demonstrate that SEAG significantly improves accuracy by 4.3% on average while requiring only 31% of computational costs compared to existing tree search-based methods on complex reasoning benchmarks including GSM8K and ARC with diverse language models such as Llama2, Llama3, and Mistral.

Related papers

• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs) Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs) We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring. We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• 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)
• DeepRAG: Thinking to Retrieval Step by Step for Large Language Models [92.87532210660456]
  We propose DeepRAG, a framework that models retrieval-augmented reasoning as a Markov Decision Process (MDP) By iteratively decomposing queries, DeepRAG dynamically determines whether to retrieve external knowledge or rely on parametric reasoning at each step. Experiments show that DeepRAG improves retrieval efficiency while improving answer accuracy by 21.99%, demonstrating its effectiveness in optimizing retrieval-augmented reasoning.
  arXiv  Detail & Related papers  (2025-02-03T08:22:45Z)
• 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)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
  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.
  arXiv  Detail & Related papers  (2023-12-08T17:05:47Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques. Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks. We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
  arXiv  Detail & Related papers  (2023-10-14T14:14:38Z)
• 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)

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.