# Tree Search for Language Model Agents

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

## Key facts

- Cited by 151 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 45 of its 70 references that are in the map.
- First posted on arXiv 1 Jul 2024.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [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)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models](https://mlsanity.com/paper/2301.12597/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [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)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [The Dawn of LMMs: Preliminary Explorations with GPT-4V(ision)](https://mlsanity.com/paper/2309.17421/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [GPT-4V(ision) is a Generalist Web Agent, if Grounded](https://mlsanity.com/paper/2401.01614/) (2024)
- [AndroidWorld: A Dynamic Benchmarking Environment for Autonomous Agents](https://mlsanity.com/paper/2405.14573/) (2024)
- [Language Models can Solve Computer Tasks](https://mlsanity.com/paper/2303.17491/) (2023)
- [WorkArena: How Capable Are Web Agents at Solving Common Knowledge Work Tasks?](https://mlsanity.com/paper/2403.07718/) (2024)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Set-of-Mark Prompting Unleashes Extraordinary Visual Grounding in GPT-4V](https://mlsanity.com/paper/2310.11441/) (2023)
- [Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration](https://mlsanity.com/paper/1802.08802/) (2018)

## Built on by (most cited first, 30 of 151)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Aguvis: Unified Pure Vision Agents for Autonomous GUI Interaction](https://mlsanity.com/paper/2412.04454/) (2024)
- [Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks](https://mlsanity.com/paper/2503.09572/) (2025)
- [SkillWeaver: Web Agents can Self-Improve by Discovering and Honing Skills](https://mlsanity.com/paper/2504.07079/) (2025)
- [WebWalker: Benchmarking LLMs in Web Traversal](https://mlsanity.com/paper/2501.07572/) (2025)
- [An Illusion of Progress? Assessing the Current State of Web Agents](https://mlsanity.com/paper/2504.01382/) (2025)
- [Large Language Model-Brained GUI Agents: A Survey](https://mlsanity.com/paper/2411.18279/) (2024)
- [The BrowserGym Ecosystem for Web Agent Research](https://mlsanity.com/paper/2412.05467/) (2024)
- [Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents](https://mlsanity.com/paper/2411.06559/) (2024)
- [SWE-Search: Enhancing Software Agents with Monte Carlo Tree Search and Iterative Refinement](https://mlsanity.com/paper/2410.20285/) (2024)
- [Web Agents with World Models: Learning and Leveraging Environment Dynamics in Web Navigation](https://mlsanity.com/paper/2410.13232/) (2024)
- [MLGym: A New Framework and Benchmark for Advancing AI Research Agents](https://mlsanity.com/paper/2502.14499/) (2025)
- [AgentOccam: A Simple Yet Strong Baseline for LLM-Based Web Agents](https://mlsanity.com/paper/2410.13825/) (2024)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [GUI Agents: A Survey](https://mlsanity.com/paper/2412.13501/) (2024)
- [WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration](https://mlsanity.com/paper/2408.15978/) (2024)
- [A Survey of WebAgents: Towards Next-Generation AI Agents for Web Automation with Large Foundation Models](https://mlsanity.com/paper/2503.23350/) (2025)
- [Agent Learning via Early Experience](https://mlsanity.com/paper/2510.08558/) (2025)
- [Lifelong Learning of Large Language Model based Agents: A Roadmap](https://mlsanity.com/paper/2501.07278/) (2025)
- [Agent-R: Training Language Model Agents to Reflect via Iterative Self-Training](https://mlsanity.com/paper/2501.11425/) (2025)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [Mobile-Agent-v3.5: Multi-platform Fundamental GUI Agents](https://mlsanity.com/paper/2602.16855/) (2026)
- [Beyond Browsing: API-Based Web Agents](https://mlsanity.com/paper/2410.16464/) (2024)
- [LifelongAgentBench: Evaluating LLM Agents as Lifelong Learners](https://mlsanity.com/paper/2505.11942/) (2025)
- [AgentPRM: Process Reward Models for LLM Agents via Step-Wise Promise and Progress](https://mlsanity.com/paper/2511.08325/) (2025)
- [Efficient Test-Time Scaling via Self-Calibration](https://mlsanity.com/paper/2503.00031/) (2025)
- [Explorer: Scaling Exploration-driven Web Trajectory Synthesis for Multimodal Web Agents](https://mlsanity.com/paper/2502.11357/) (2025)
- [The Dawn of GUI Agent: A Preliminary Case Study with Claude 3.5 Computer Use](https://mlsanity.com/paper/2411.10323/) (2024)
- [Scaling Test-time Compute for LLM Agents](https://mlsanity.com/paper/2506.12928/) (2025)

## Abstract (arXiv)

Autonomous agents powered by language models (LMs) have demonstrated promise in their ability to perform decision-making tasks such as web automation. However, a key limitation remains: LMs, primarily optimized for natural language understanding and generation, struggle with multi-step reasoning, planning, and using environmental feedback when attempting to solve realistic computer tasks. Towards addressing this, we propose an inference-time search algorithm for LM agents to explicitly perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space, and is complementary with most existing state-of-the-art agents. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks. On the challenging VisualWebArena benchmark, applying our search algorithm on top of a GPT-4o agent yields a 39.7% relative increase in success rate compared to the same baseline without search, setting a state-of-the-art success rate of 26.4%. On WebArena, search also yields a 28.0% relative improvement over a baseline agent, setting a competitive success rate of 19.2%. Our experiments highlight the effectiveness of search for web agents, and we demonstrate that performance scales with increased test-time compute. We conduct a thorough analysis of our results to highlight improvements from search, limitations, and promising directions for future work. Our code and models are publicly released at https://jykoh.com/search-agents.