# When is Tree Search Useful for LLM Planning? It Depends on the Discriminator

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 16 Feb 2024.

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

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (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)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Can LLM Already Serve as A Database Interface? A BIg Bench for Large-Scale Database Grounded Text-to-SQLs](https://mlsanity.com/paper/2305.03111/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [LEVER: Learning to Verify Language-to-Code Generation with Execution](https://mlsanity.com/paper/2302.08468/) (2023)
- [InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedback](https://mlsanity.com/paper/2306.14898/) (2023)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [The Generative AI Paradox: "What It Can Create, It May Not Understand"](https://mlsanity.com/paper/2311.00059/) (2023)
- [Can ChatGPT Defend its Belief in Truth? Evaluating LLM Reasoning via Debate](https://mlsanity.com/paper/2305.13160/) (2023)
- [GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems](https://mlsanity.com/paper/2310.12397/) (2023)
- [Solving Math Word Problems via Cooperative Reasoning induced Language Models](https://mlsanity.com/paper/2210.16257/) (2022)
- [PPL-MCTS: Constrained Textual Generation Through Discriminator-Guided MCTS Decoding](https://mlsanity.com/paper/2109.13582/) (2021)
- [Text-to-SQL Error Correction with Language Models of Code](https://mlsanity.com/paper/2305.13073/) (2023)
- [Simulating Bandit Learning from User Feedback for Extractive Question Answering](https://mlsanity.com/paper/2203.10079/) (2022)
- [Error Detection for Text-to-SQL Semantic Parsing](https://mlsanity.com/paper/2305.13683/) (2023)
- [Detect-Localize-Repair: A Unified Framework for Learning to Debug with CodeT5](https://mlsanity.com/paper/2211.14875/) (2022)
- [DecompEval: Evaluating Generated Texts as Unsupervised Decomposed Question Answering](https://mlsanity.com/paper/2307.06869/) (2023)

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

- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [When Can LLMs Actually Correct Their Own Mistakes? A Critical Survey of Self-Correction of LLMs](https://mlsanity.com/paper/2406.01297/) (2024)
- [Magentic-One: A Generalist Multi-Agent System for Solving Complex Tasks](https://mlsanity.com/paper/2411.04468/) (2024)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [Process Reward Models That Think](https://mlsanity.com/paper/2504.16828/) (2025)
- [LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models](https://mlsanity.com/paper/2404.05221/) (2024)
- [Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?](https://mlsanity.com/paper/2502.12215/) (2025)
- [The Limits of Inference Scaling Through Resampling](https://mlsanity.com/paper/2411.17501/) (2024)
- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [A Theoretical Understanding of Self-Correction through In-context Alignment](https://mlsanity.com/paper/2405.18634/) (2024)
- [SciReplicate-Bench: Benchmarking LLMs in Agent-driven Algorithmic Reproduction from Research Papers](https://mlsanity.com/paper/2504.00255/) (2025)
- [Magentic-UI: Towards Human-in-the-loop Agentic Systems](https://mlsanity.com/paper/2507.22358/) (2025)
- [Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examples](https://mlsanity.com/paper/2406.05673/) (2024)
- [SELF-[IN]CORRECT: LLMs Struggle with Discriminating Self-Generated Responses](https://mlsanity.com/paper/2404.04298/) (2024)
- [Non-myopic Generation of Language Models for Reasoning and Planning](https://mlsanity.com/paper/2410.17195/) (2024)
- [Multi-Agent Large Language Models for Conversational Task-Solving](https://mlsanity.com/paper/2410.22932/) (2024)
- [Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Model](https://mlsanity.com/paper/2410.03136/) (2024)
- [A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks](https://mlsanity.com/paper/2501.10069/) (2025)
- [The Counterfeit Conundrum: Can Code Language Models Grasp the Nuances of Their Incorrect Generations?](https://mlsanity.com/paper/2402.19475/) (2024)
- [SQL-o1: A Self-Reward Heuristic Dynamic Search Method for Text-to-SQL](https://mlsanity.com/paper/2502.11741/) (2025)
- [On the Effect of Sampling Diversity in Scaling LLM Inference](https://mlsanity.com/paper/2502.11027/) (2025)
- [A Survey on Large Language Models for Automated Planning](https://mlsanity.com/paper/2502.12435/) (2025)
- [RoT: Enhancing Large Language Models with Reflection on Search Trees](https://mlsanity.com/paper/2404.05449/) (2024)
- [Plan*RAG: Efficient Test-Time Planning for Retrieval Augmented Generation](https://mlsanity.com/paper/2410.20753/) (2024)
- [Scattered Forest Search: Smarter Code Space Exploration with LLMs](https://mlsanity.com/paper/2411.05010/) (2024)
- [Iterative Deepening Sampling as Efficient Test-Time Scaling](https://mlsanity.com/paper/2502.05449/) (2025)
- [Trust but Verify! A Survey on Verification Design for Test-time Scaling](https://mlsanity.com/paper/2508.16665/) (2025)
- [System-2 Mathematical Reasoning via Enriched Instruction Tuning](https://mlsanity.com/paper/2412.16964/) (2024)
- [JoyAgent-JDGenie: Technical Report on the GAIA](https://mlsanity.com/paper/2510.00510/) (2025)

## Abstract (arXiv)

In this paper, we examine how large language models (LLMs) solve multi-step problems under a language agent framework with three components: a generator, a discriminator, and a planning method. We investigate the practical utility of two advanced planning methods, iterative correction and tree search. We present a comprehensive analysis of how discrimination accuracy affects the overall performance of agents when using these two methods or a simpler method, re-ranking. Experiments on two tasks, text-to-SQL parsing and mathematical reasoning, show that: (1) advanced planning methods demand discriminators with at least 90% accuracy to achieve significant improvements over re-ranking; (2) current LLMs' discrimination abilities have not met the needs of advanced planning methods to achieve such improvements; (3) with LLM-based discriminators, advanced planning methods may not adequately balance accuracy and efficiency. For example, compared to the other two methods, tree search is at least 10--20 times slower but leads to negligible performance gains, which hinders its real-world applications. Code and data are available at https://github.com/OSU-NLP-Group/llm-planning-eval.