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

Abstract: 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.

## introduction planning plays a crucial role in intelligent behaviors of human and ai agents. since the early stage of ai research, various methods have been proposed to build agents that can plan efficiently and accurately @xcite . the problem-solving procedure in these ai agents usually involves three steps: searching for possible action sequences, predicting their expected outcomes with an internal world model, and finding an action sequence to achieve the best expected outcome @xcite . this procedure shares common traits with how large language models (llms) solve multi-step tasks, including mathematical reasoning @xcite , multi-hop question answering @xcite , and code generation @xcite . at each step, an llm searches for possible next actions and generates their language representations (generation). to evaluate the actions, the llm utilizes itself or another llm to predict the outcomes of actions, in the form of rewards or correctness (discrimination). afterwards, it incorporates the outcomes into its problem-solving process with some strategy to find the best action sequence (planning). motivated by the similarity, we critically examine how llms solve multi-step tasks from a language-agent view. we unify different problemsolving procedures of llms into an agent framework (figure 1 ) consisting of a generator, a discriminator, and a planning method. under this framework, we investigate the practical utility of more advanced planning methods, such as tree search, in comparison with simpler methods (e.g. re-ranking). we hypothesize that the discriminator may be a deciding factor and systematically investigate two research questions: (rq1) how does discrimination accuracy affect the performance of language agents using different planning methods? (rq2) can llm-based discriminators correctly assess language agents' actions in practical settings? to this end, we analyze llms' discrimination abilities and their impact on three categories of planning methods: re-ranking, iterative correction, and tree search. we comprehensively evaluate these methods on two real-world tasks, text-to-sql parsing and mathematical reasoning, with opensource, proprietary, and fine-tuned llm discriminators. first, we use oracle environmental information to simulate discriminators with different levels of accuracy. the simulation experiments exhibit a strong correlation between discrimination accuracy and overall task performance among all three types of planning methods. then, in a non-oracle setting, we closely investigate the llm-based discriminators and show how environmental observations can effectively improve them. finally, we conduct endto-end evaluations of the discriminators and planning methods to verify and strengthen our findings. in summary, our experiments show that: ## related work a lot of recent research efforts have focused on advanced planning methods for improving the multistep problem-solving abilities of llms @xcite @xcite @xcite ; inter alia). despite different designs, all these methods use a discriminator to evaluate the agents' actions, or planning steps. in fact, instead of planning methods, an agent's discriminator could be the more critical component. since incorrect outcome predictions could lead to suboptimal plans, discriminators may decide the performance of an agent, regardless of its planning method @xcite . while it is commonly believed that discrimination is easier than generation for human and ai agents @xcite , @xcite pose the hypothesis that state-of-the-art generative ai models, including llms, may not have discrimination abilities matching their generation abilities. this hypothesis coincides with the findings of @xcite and @xcite that, without any external feedback or with obviously absurd feedback, llms may recognize some of their selfgenerated correct plans as wrong. huang et al. (2024) also note that the performance gains of selfcorrection, a kind of iterative correction method, may rely on some high-quality external feedback, such as checking ground-truth labels or test sets for planning loop termination. however, such external feedback usually does not exist in practical applications because solutions to new problems are unknown, and annotating comprehensive test cases can be nontrivial and costly. distinct from these existing studies, our work focuses on studying the relationship between discriminators and planning methods, including but not limited to self-correction, and attempts to improve llms' discrimination capability. our findings can provide useful guidelines for choosing planning methods and implementing language agents in practice. in light of our findings, we encourage future research to thoroughly evaluate language agents with various practical, non-oracle discriminators. we also advocate that improving llm-based discriminators is an important future direction to enhance agents' accuracy and efficiency when using advanced planning methods. ## our framework as shown in figure 1 , we systematically analyze different planning methods in a unified generatordiscriminator framework. our framework consists of a generator that proposes (partial) action sequences, a discriminator that evaluates the outcomes of these actions, and a planning method that ranks the actions according to their outcomes and manages the interaction between the two models. in this section, we describe each of the three components and how they are instantiated on text-to-sql parsing and mathematical reasoning (section 4.1). ## llm-based discriminators while we have shown that iterative correction and tree search work well with oracle discriminators, it remains unclear whether llm-based discriminators can correctly assess language agents' actions (rq2). to answer this question, we leverage generator outputs in the simulation experiments and re-label them with ground-truths to evaluate the llms' discrimination accuracy (appendix a.2). ## end-to-end evaluation while we have evaluated their discrimination abilities with a fixed test set, to answer rq2, we wonder if llms can correctly assess constantly changing sets of programs in actual planning processes. to this end, we evaluate the end-to-end performance of language agents with llm-based discriminators and the three planning methods. ## conclusions this paper presents a thorough investigation into the relationship between discrimination accuracy and performance of planning methods in language agents. through comprehensive experiments on text-to-sql parsing and mathematical reasoning, we find that: discrimination accuracy strongly correlates with the overall performance of language agents using different planning methods and also affects their efficiency (answer to rq1). llm-based discriminators can correctly assess a decent number of language agents' actions with their environmental observations, but they are still not accurate enough for advanced planning methods (answer to rq2). future research should investigate the development of more accurate discrimination models for language agents, e.g. by improving their grounded understanding of execution results beyond error signals.