LLM-First Search: Self-Guided Exploration of the Solution Space

2025/06/05 by Nathan Herr, Tim Rocktäschel, Herr, Nathan +3 · 2 citations
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Computation and Language (cs.CL) #FOS: Computer and information sciences #Multimodal Machine Learning Applications

paper · pdf · doi:10.48550/arxiv.2506.05213

openalex publication_date 2025/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Large Language Models (LLMs) have demonstrated remarkable improvements in reasoning and planning through increased test-time compute, often by framing problem-solving as a search process. While methods like Monte Carlo Tree Search (MCTS) have proven effective in some domains, their reliance on fixed exploration hyperparameters limits their adaptability across tasks of varying difficulty, rendering them impractical or expensive in certain settings. In this paper, we propose LLM-First Search (LFS), a novel LLM Self-Guided Search method that removes the need for pre-defined search strategies by empowering the LLM to autonomously control the search process via self-guided exploration. Rather than relying on external heuristics or hardcoded policies, the LLM evaluates whether to pursue the current search path or explore alternative branches based on its internal scoring mechanisms. This enables more flexible and context-sensitive reasoning without requiring manual tuning or task-specific adaptation. We evaluate LFS on Countdown and Sudoku against three classic widely-used search algorithms, Tree-of-Thoughts' Breadth First Search (ToT-BFS), Best First Search (BestFS), and MCTS, each of which have been used to achieve SotA results on a range of challenging reasoning tasks. We found that LFS (1) performs better on more challenging tasks without additional tuning, (2) is more computationally efficient compared to the other methods, especially when powered by a stronger model, (3) scales better with stronger models, due to its LLM-First design, and (4) scales better with increased compute budget. Our code is publicly available at \hrefhttps://github.com/NathanHerr/LLM-First-SearchLLM-First-Search.

Citations

• Reward Is Enough: LLMs Are In-Context Reinforcement Learners
• Exploring the System 1 Thinking Capability of Large Reasoning Models
• Debate Only When Necessary: Adaptive Multiagent Collaboration for Efficient LLM Reasoning
• Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search
• Chain of Draft: Thinking Faster by Writing Less
• MLGym: A New Framework and Benchmark for Advancing AI Research Agents
• On the Emergence of Thinking in LLMs I: Searching for the Right Intuition
• s1: Simple test-time scaling
• Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning
• Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning
• EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration
• ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning
• Interpretable Contrastive Monte Carlo Tree Search Reasoning
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation
• Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers
• Tree Search for Language Model Agents
• Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B
• Stream of Search (SoS): Learning to Search in Language
• AIOS: LLM Agent Operating System
• Chain-of-Thought Reasoning Without Prompting
• Understanding the planning of LLM agents: A survey
• Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models
• Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models
• Graph of Thoughts: Solving Elaborate Problems with Large Language Models
• Autonomous Tester Agent Benchmark
• REX: Rapid Exploration and eXploitation for AI Agents
• OMNI: Open-endedness via Models of human Notions of Interestingness
• Voyager: An Open-Ended Embodied Agent with Large Language Models
• Reasoning with Language Model is Planning with World Model
• Improving Factuality and Reasoning in Language Models through Multiagent Debate
• Meta-in-context learning in large language models
• Tree of Thoughts: Deliberate Problem Solving with Large Language Models
• Self-Evaluation Guided Beam Search for Reasoning
• Self-Refine: Iterative Refinement with Self-Feedback
• Reflexion: Language Agents with Verbal Reinforcement Learning
• Automatic Chain of Thought Prompting in Large Language Models
• Distributing Accountability, Not Capability: Phase Separation and the LLM Workflow Quadrant in Autonomous AI Agent Architectures
• Large Language Models are Zero-Shot Reasoners
• Self-Consistency Improves Chain of Thought Reasoning in Language Models
• A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges
• PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms
• On the Dangers of Stochastic Parrots
• Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification
• Benchmarking Optimization Software with Performance Profiles
• Benchmarking optimization software with performance profiles
• Probable Inference, the Law of Succession, and Statistical Inference
• A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoning
• VisualWebArena: Evaluating Multimodal Agents on Realistic Visual Web Tasks

Cited by

• How Does RL Post-training Induce Skill Composition? A Case Study on Countdown
• Learning the ARTS of Search for Automated Discovery

Related

• Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems
• Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey
• Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls
• Autonomous Tree-search Ability of Large Language Models