mlsanityData to 14 Oct 2026

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

arXiv 2402.10890 ↗First posted 16 Feb 2024cs.CL cs.AI cs.LGcited by 47

Not on the map. Why?

Cited by 26 in LLM reasoning, but placed by its own abstract, which didn’t fit.

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.

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

29 of 48 references.

References · 29

  1. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  2. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  3. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  4. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  5. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  6. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,442
  7. 2023Code Llama: Open Foundation Models for Codecited by 2,139
  8. 2022Language Models (Mostly) Know What They Knowcited by 1,856
  9. 2018Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Taskcited by 1,139
  10. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,076
  11. 2023Large Language Models Cannot Self-Correct Reasoning Yetcited by 1,017
  12. 2023Teaching Large Language Models to Self-Debugcited by 988
17 more
  1. 2023Reasoning with Language Model is Planning with World Modelcited by 861
  2. 2023Can LLM Already Serve as A Database Interface? A BIg Bench for Large-Scale Database Grounded Text-to-SQLscited by 688
  3. 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Modelscited by 574
  4. 2023LEVER: Learning to Verify Language-to-Code Generation with Executioncited by 239
  5. 2023InterCode: Standardizing and Benchmarking Interactive Coding with Execution Feedbackcited by 238
  6. 2022Making Large Language Models Better Reasoners with Step-Aware Verifiercited by 233
  7. 2023Planning with Large Language Models for Code Generationcited by 182
  8. 2023The Generative AI Paradox: "What It Can Create, It May Not Understand"cited by 98
  9. 2023Can ChatGPT Defend its Belief in Truth? Evaluating LLM Reasoning via Debatecited by 94
  10. 2023GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problemscited by 89
  11. 2022Solving Math Word Problems via Cooperative Reasoning induced Language Modelscited by 77
  12. 2021PPL-MCTS: Constrained Textual Generation Through Discriminator-Guided MCTS Decodingcited by 33
  13. 2023Text-to-SQL Error Correction with Language Models of Codecited by 21
  14. 2022Simulating Bandit Learning from User Feedback for Extractive Question Answeringcited by 14
  15. 2023Error Detection for Text-to-SQL Semantic Parsingcited by 12
  16. 2022Detect-Localize-Repair: A Unified Framework for Learning to Debug with CodeT5cited by 10
  17. 2023DecompEval: Evaluating Generated Texts as Unsupervised Decomposed Question Answeringcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 21; 2025: 20; 2026: 6.

47 papers.

Sort:

By area:

  1. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Modelscited by 290
  2. 2024When Can LLMs Actually Correct Their Own Mistakes? A Critical Survey of Self-Correction of LLMscited by 240
  3. 2024Magentic-One: A Generalist Multi-Agent System for Solving Complex Taskscited by 232
  4. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?cited by 223
  5. 2024Tree Search for Language Model Agentscited by 151
  6. 2025Process Reward Models That Thinkcited by 118
  7. 2024LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Modelscited by 70
  8. 2025Revisiting the Test-Time Scaling of o1-like Models: Do they Truly Possess Test-Time Scaling Capabilities?cited by 70
  9. 2024The Limits of Inference Scaling Through Resamplingcited by 53
  10. 2026A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agentscited by 50
  11. 2024A Theoretical Understanding of Self-Correction through In-context Alignmentcited by 44
  12. 2025SciReplicate-Bench: Benchmarking LLMs in Agent-driven Algorithmic Reproduction from Research Paperscited by 43
35 more
  1. 2025Magentic-UI: Towards Human-in-the-loop Agentic Systemscited by 43
  2. 2024Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examplescited by 30
  3. 2024SELF-[IN]CORRECT: LLMs Struggle with Discriminating Self-Generated Responsescited by 26
  4. 2024Non-myopic Generation of Language Models for Reasoning and Planningcited by 26
  5. 2024Multi-Agent Large Language Models for Conversational Task-Solvingcited by 24
  6. 2024Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Modelcited by 23
  7. 2025A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworkscited by 21
  8. 2024The Counterfeit Conundrum: Can Code Language Models Grasp the Nuances of Their Incorrect Generations?cited by 20
  9. 2025SQL-o1: A Self-Reward Heuristic Dynamic Search Method for Text-to-SQLcited by 19
  10. 2025On the Effect of Sampling Diversity in Scaling LLM Inferencecited by 18
  11. 2025A Survey on Large Language Models for Automated Planningcited by 17
  12. 2024RoT: Enhancing Large Language Models with Reflection on Search Treescited by 12
  13. 2024Plan*RAG: Efficient Test-Time Planning for Retrieval Augmented Generationcited by 11
  14. 2024Scattered Forest Search: Smarter Code Space Exploration with LLMscited by 10
  15. 2025Iterative Deepening Sampling as Efficient Test-Time Scalingcited by 8
  16. 2025Trust but Verify! A Survey on Verification Design for Test-time Scalingcited by 8
  17. 2024System-2 Mathematical Reasoning via Enriched Instruction Tuningcited by 7
  18. 2025JoyAgent-JDGenie: Technical Report on the GAIAcited by 7
  19. 2026Reward Modeling for Reinforcement Learning-Based LLM Reasoning: Design, Challenges, and Evaluationcited by 7
  20. 2025When Can Model-Free Reinforcement Learning be Enough for Thinking?cited by 6
  21. 2024Optimizing Instruction Synthesis: Effective Exploration of Evolutionary Space with Tree Searchcited by 5
  22. 2025From Chaos to Order: The Atomic Reasoner Framework for Fine-grained Reasoning in Large Language Modelscited by 5
  23. 2026Adaptive Test-Time Compute Allocation via Learned Heuristics over Categorical Structurecited by 5
  24. 2025Language Models can Self-Improve at State-Value Estimation for Better Searchcited by 4
  25. 2025Offline Learning and Forgetting for Reasoning with Large Language Modelscited by 4
  26. 2025Agentic AutoSurvey: Let LLMs Survey LLMscited by 4
  27. 2024Understanding When Tree of Thoughts Succeeds: Larger Models Excel in Generation, Not Discriminationcited by 2
  28. 2024AUTONODE: A Neuro-Graphic Self-Learnable Engine for Cognitive GUI Automationcited by 1
  29. 2024A Training Data Recipe to Accelerate A* Search with Language Modelscited by 1
  30. 2025From Harm to Help: Turning Reasoning In-Context Demos into Assets for Reasoning LMscited by 1
  31. 2025Mini Amusement Parks (MAPs): A Testbed for Modelling Business Decisionscited by 1
  32. 2026One-Token Verification for Reasoning Correctness Estimationcited by 1
  33. 2025SWI: Speaking with Intent in Large Language Modelscited by 0
  34. 2026OS-SPEAR: A Toolkit for the Safety, Performance,Efficiency, and Robustness Analysis of OS Agentscited by 0
  35. 2026When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Modelscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Query-Efficient Planning with Language Models
  2. 2024Thought of Search: Planning with Language Models Through The Lens of Efficiency
  3. 2023Tree-Planner: Efficient Close-loop Task Planning with Large Language Models
  4. 2025Cost-Awareness in Tree-Search LLM Planning: A Systematic Study
  5. 2024Understanding the planning of LLM agents: A survey
  6. 2023Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning
  7. 2025Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey
  8. 2023On the Planning Abilities of Large Language Models : A Critical Investigation