# How Far are LLMs from Real Search? A Comprehensive Study on Efficiency, Completeness, and Inherent Capabilities

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 25 Feb 2025.

## Builds on (most cited first, 23 of 23)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [GPT-Driver: Learning to Drive with GPT](https://mlsanity.com/paper/2310.01415/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [REFINER: Reasoning Feedback on Intermediate Representations](https://mlsanity.com/paper/2304.01904/) (2023)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [LiteSearch: Efficacious Tree Search for LLM](https://mlsanity.com/paper/2407.00320/) (2024)
- [LLM A*: Human in the Loop Large Language Models Enabled A* Search for Robotics](https://mlsanity.com/paper/2312.01797/) (2023)
- [Decoding Time Series with LLMs: A Multi-Agent Framework for Cross-Domain Annotation](https://mlsanity.com/paper/2410.17462/) (2024)
- [LLM and GNN are Complementary: Distilling LLM for Multimodal Graph Learning](https://mlsanity.com/paper/2406.01032/) (2024)
- [LanP: Rethinking the Impact of Language Priors in Large Vision-Language Models](https://mlsanity.com/paper/2502.12359/) (2025)
- [Automating Thought of Search: A Journey Towards Soundness and Completeness](https://mlsanity.com/paper/2408.11326/) (2024)
- [Advancing Real-time Pandemic Forecasting Using Large Language Models: A COVID-19 Case Study](https://mlsanity.com/paper/2404.06962/) (2024)

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

- [A Comprehensive Survey on Reinforcement Learning-based Agentic Search: Foundations, Roles, Optimizations, Evaluations, and Applications](https://mlsanity.com/paper/2510.16724/) (2025)
- [AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks](https://mlsanity.com/paper/2508.00890/) (2025)
- [Bradley-Terry and Multi-Objective Reward Modeling Are Complementary](https://mlsanity.com/paper/2507.07375/) (2025)
- [SUA: Stealthy Multimodal Large Language Model Unlearning Attack](https://mlsanity.com/paper/2506.17265/) (2025)

## Abstract (arXiv)

Search plays a fundamental role in problem-solving across various domains, with most real-world decision-making problems being solvable through systematic search. Drawing inspiration from recent discussions on search and learning, we systematically explore the complementary relationship between search and Large Language Models (LLMs) from three perspectives. First, we analyze how learning can enhance search efficiency and propose Search via Learning (SeaL), a framework that leverages LLMs for effective and efficient search. Second, we further extend SeaL to SeaL-C to ensure rigorous completeness during search. Our evaluation across three real-world planning tasks demonstrates that SeaL achieves near-perfect accuracy while reducing search spaces by up to 99.1% compared to traditional approaches. Finally, we explore how far LLMs are from real search by investigating whether they can develop search capabilities independently. Our analysis reveals that while current LLMs struggle with efficient search in complex problems, incorporating systematic search strategies significantly enhances their problem-solving capabilities. These findings not only validate the effectiveness of our approach but also highlight the need for improving LLMs' search abilities for real-world applications.