<!DOCTYPE html><html lang="en">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>[2402.10890] When is Tree Search Useful for LLM Planning? It Depends on the Discriminator</title><meta property="og:description" content="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 pract…">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="When is Tree Search Useful for LLM Planning? It Depends on the Discriminator">
<meta name="twitter:image:src" content="https://ar5iv.labs.arxiv.org/assets/ar5iv_card.png">
<meta name="twitter:image:alt" content="ar5iv logo">
<meta property="og:title" content="When is Tree Search Useful for LLM Planning? It Depends on the Discriminator">
<meta property="og:site_name" content="ar5iv">
<meta property="og:image" content="https://ar5iv.labs.arxiv.org/assets/ar5iv_card.png">
<meta property="og:type" content="article">
<meta property="og:url" content="https://ar5iv.labs.arxiv.org/html/2402.10890">

<!--Generated on Tue Mar  5 16:00:06 2024 by LaTeXML (version 0.8.8) http://dlmf.nist.gov/LaTeXML/.-->
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">

<script>
  function detectColorScheme(){
    var theme="light";
    var current_theme = localStorage.getItem("ar5iv_theme");
    if(current_theme){
      if(current_theme == "dark"){
        theme = "dark";
      } }
    else if(!window.matchMedia) { return false; }
    else if(window.matchMedia("(prefers-color-scheme: dark)").matches) {
      theme = "dark"; }
    if (theme=="dark") {
      document.documentElement.setAttribute("data-theme", "dark");
    } else {
      document.documentElement.setAttribute("data-theme", "light"); } }

  detectColorScheme();

  function toggleColorScheme(){
    var current_theme = localStorage.getItem("ar5iv_theme");
    if (current_theme) {
      if (current_theme == "light") {
        localStorage.setItem("ar5iv_theme", "dark"); }
      else {
        localStorage.setItem("ar5iv_theme", "light"); } }
    else {
        localStorage.setItem("ar5iv_theme", "dark"); }
    detectColorScheme(); }
</script>
<link media="all" rel="stylesheet" href="/assets/ar5iv-fonts.0.7.9.min.css"><link media="all" rel="stylesheet" href="/assets/ar5iv.0.7.9.min.css"><link media="all" rel="stylesheet" href="/assets/ar5iv-site.0.2.2.css">
</head>
<body>
<div class="ltx_page_main">
<div class="ltx_page_content">
<article class="ltx_document">
<h1 class="ltx_title ltx_title_document">When is Tree Search Useful for LLM Planning?
<br class="ltx_break">It Depends on the Discriminator</h1>
<div class="ltx_authors">
<span class="ltx_creator ltx_role_author">
<span class="ltx_personname">Ziru Chen<sup id="id10.10.id1" class="ltx_sup">1</sup>, Michael White<sup id="id11.11.id2" class="ltx_sup">1</sup>, Raymond Mooney<sup id="id12.12.id3" class="ltx_sup">2</sup>, Ali Payani<sup id="id13.13.id4" class="ltx_sup">3</sup>, Yu Su<sup id="id14.14.id5" class="ltx_sup">1</sup>, Huan Sun<sup id="id15.15.id6" class="ltx_sup">1</sup> 
<br class="ltx_break"><sup id="id16.16.id7" class="ltx_sup">1</sup>The Ohio State University  <sup id="id17.17.id8" class="ltx_sup">2</sup>The University of Texas at Austin  <sup id="id18.18.id9" class="ltx_sup">3</sup>Cisco Research
<br class="ltx_break"><span id="id19.19.id10" class="ltx_text ltx_font_typewriter">{chen.8336, white.1240, su.809, sun.397}@osu.edu</span> 
<br class="ltx_break"><span id="id20.20.id11" class="ltx_text ltx_font_typewriter">mooney@cs.utexas.edu</span>  <span id="id21.21.id12" class="ltx_text ltx_font_typewriter">apayani@cisco.com</span> 
<br class="ltx_break">
</span></span>
</div>

<div class="ltx_abstract">
<h6 class="ltx_title ltx_title_abstract">Abstract</h6>
<p id="id22.id1" class="ltx_p">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.<span id="footnote1" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">1</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">1</sup><span class="ltx_tag ltx_tag_note">1</span>Code and data will be released at <a target="_blank" href="https://github.com/OSU-NLP-Group/llm-planning-eval" title="" class="ltx_ref ltx_url ltx_font_typewriter">https://github.com/OSU-NLP-Group/llm-planning-eval</a>.</span></span></span></p>
</div>
<div id="p1" class="ltx_para ltx_noindent">
<div id="p1.9" class="ltx_block ltx_align_bottom">
<p id="p1.9.10" class="ltx_p"><span id="p1.9.10.1" class="ltx_text ltx_font_bold">When is Tree Search Useful for LLM Planning?
<br class="ltx_break">It Depends on the Discriminator</span></p>
<br class="ltx_break ltx_centering">
<p id="p1.9.9" class="ltx_p ltx_align_center" style="width:433.6pt;"><span id="p1.9.9.9" class="ltx_text ltx_inline-block" style="width:0.0pt;">

<span id="p1.9.9.9.9" class="ltx_tabular ltx_align_top">
<span id="p1.6.6.6.6.6" class="ltx_tr">
<span id="p1.6.6.6.6.6.6" class="ltx_td ltx_align_center"><span id="p1.6.6.6.6.6.6.6" class="ltx_text ltx_font_bold">Ziru Chen<sup id="p1.6.6.6.6.6.6.6.1" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.1.1" class="ltx_text ltx_font_medium">1</span></sup>, Michael White<sup id="p1.6.6.6.6.6.6.6.2" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.2.1" class="ltx_text ltx_font_medium">1</span></sup>, Raymond Mooney<sup id="p1.6.6.6.6.6.6.6.3" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.3.1" class="ltx_text ltx_font_medium">2</span></sup>, Ali Payani<sup id="p1.6.6.6.6.6.6.6.4" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.4.1" class="ltx_text ltx_font_medium">3</span></sup>, Yu Su<sup id="p1.6.6.6.6.6.6.6.5" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.5.1" class="ltx_text ltx_font_medium">1</span></sup>, Huan Sun<sup id="p1.6.6.6.6.6.6.6.6" class="ltx_sup"><span id="p1.6.6.6.6.6.6.6.6.1" class="ltx_text ltx_font_medium">1</span></sup></span></span></span>
<span id="p1.9.9.9.9.9" class="ltx_tr">
<span id="p1.9.9.9.9.9.3" class="ltx_td ltx_align_center"><sup id="p1.9.9.9.9.9.3.1" class="ltx_sup">1</sup>The Ohio State University  <sup id="p1.9.9.9.9.9.3.2" class="ltx_sup">2</sup>The University of Texas at Austin  <sup id="p1.9.9.9.9.9.3.3" class="ltx_sup">3</sup>Cisco Research</span></span>
<span id="p1.9.9.9.9.10" class="ltx_tr">
<span id="p1.9.9.9.9.10.1" class="ltx_td ltx_align_center"><span id="p1.9.9.9.9.10.1.1" class="ltx_text ltx_font_typewriter">{chen.8336, white.1240, su.809, sun.397}@osu.edu</span></span></span>
<span id="p1.9.9.9.9.11" class="ltx_tr">
<span id="p1.9.9.9.9.11.1" class="ltx_td ltx_align_center"><span id="p1.9.9.9.9.11.1.1" class="ltx_text ltx_font_typewriter">mooney@cs.utexas.edu</span>  <span id="p1.9.9.9.9.11.1.2" class="ltx_text ltx_font_typewriter">apayani@cisco.com</span></span></span>
</span></span></p>
<br class="ltx_break ltx_centering">
</div>
</div>
<section id="S1" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">1 </span>Introduction</h2>

<div id="S1.p1" class="ltx_para">
<p id="S1.p1.1" class="ltx_p">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 <cite class="ltx_cite ltx_citemacro_citep">(Newell and Simon, <a href="#bib.bib21" title="" class="ltx_ref">1956</a>; Russell and Norvig, <a href="#bib.bib28" title="" class="ltx_ref">2010</a>)</cite>.
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 <cite class="ltx_cite ltx_citemacro_citep">(Russell and Norvig, <a href="#bib.bib28" title="" class="ltx_ref">2010</a>; Mattar and Lengyel, <a href="#bib.bib19" title="" class="ltx_ref">2022</a>)</cite>.
This procedure shares common traits with how large language models (LLMs) solve multi-step tasks, including mathematical reasoning <cite class="ltx_cite ltx_citemacro_citep">(Wei et al., <a href="#bib.bib35" title="" class="ltx_ref">2022</a>)</cite>, multi-hop question answering <cite class="ltx_cite ltx_citemacro_citep">(Yao et al., <a href="#bib.bib40" title="" class="ltx_ref">2023b</a>)</cite>, and code generation <cite class="ltx_cite ltx_citemacro_citep">(Yang et al., <a href="#bib.bib38" title="" class="ltx_ref">2023</a>)</cite>.
At each step, an LLM searches for possible next actions and generates their language representations (<span id="S1.p1.1.1" class="ltx_text ltx_font_italic">generation</span>).
To evaluate the actions, the LLM utilizes itself or another LLM to predict the outcomes of actions, in the form of rewards or correctness (<span id="S1.p1.1.2" class="ltx_text ltx_font_italic">discrimination</span>).
Afterwards, it incorporates the outcomes into its problem-solving process with some strategy to find the best action sequence (<span id="S1.p1.1.3" class="ltx_text ltx_font_italic">planning</span>).</p>
</div>
<figure id="S1.F1" class="ltx_figure"><img src="/html/2402.10890/assets/figures/overview.png" id="S1.F1.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="509" height="289" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 1: </span>A generator-discriminator framework of language agents, where planning methods control the interaction between a generator and a discriminator, both of which are usually instantiated by some LLM.
</figcaption>
</figure>
<div id="S1.p2" class="ltx_para">
<p id="S1.p2.1" class="ltx_p">Motivated by the similarity, we critically examine how LLMs solve multi-step tasks from a language-agent view.
We unify different problem-solving procedures of LLMs into an agent framework (Figure <a href="#S1.F1" title="Figure 1 ‣ 1 Introduction ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a>) 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:
<span id="S1.p2.1.1" class="ltx_text ltx_font_bold">(RQ1)</span> <span id="S1.p2.1.2" class="ltx_text ltx_font_italic">How does discrimination accuracy affect the performance of language agents using different planning methods?</span>
<span id="S1.p2.1.3" class="ltx_text ltx_font_bold">(RQ2)</span> <span id="S1.p2.1.4" class="ltx_text ltx_font_italic">Can LLM-based discriminators correctly assess language agents’ actions in practical settings?</span></p>
</div>
<div id="S1.p3" class="ltx_para">
<p id="S1.p3.1" class="ltx_p">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 open-source, closed-source, 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 end-to-end evaluations of the discriminators and planning methods to verify and strengthen our findings.
In summary, our experiments show that:</p>
</div>
<div id="S1.p4" class="ltx_para ltx_noindent">
<p id="S1.p4.1" class="ltx_p"><span id="S1.p4.1.1" class="ltx_text ltx_font_bold">(1)</span> Advanced planning methods, i.e., iterative correction and tree search, demand highly accurate discriminators (<math id="S1.p4.1.m1.1" class="ltx_Math" alttext="\geq 90\%" display="inline"><semantics id="S1.p4.1.m1.1a"><mrow id="S1.p4.1.m1.1.1" xref="S1.p4.1.m1.1.1.cmml"><mi id="S1.p4.1.m1.1.1.2" xref="S1.p4.1.m1.1.1.2.cmml"></mi><mo id="S1.p4.1.m1.1.1.1" xref="S1.p4.1.m1.1.1.1.cmml">≥</mo><mrow id="S1.p4.1.m1.1.1.3" xref="S1.p4.1.m1.1.1.3.cmml"><mn id="S1.p4.1.m1.1.1.3.2" xref="S1.p4.1.m1.1.1.3.2.cmml">90</mn><mo id="S1.p4.1.m1.1.1.3.1" xref="S1.p4.1.m1.1.1.3.1.cmml">%</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S1.p4.1.m1.1b"><apply id="S1.p4.1.m1.1.1.cmml" xref="S1.p4.1.m1.1.1"><geq id="S1.p4.1.m1.1.1.1.cmml" xref="S1.p4.1.m1.1.1.1"></geq><csymbol cd="latexml" id="S1.p4.1.m1.1.1.2.cmml" xref="S1.p4.1.m1.1.1.2">absent</csymbol><apply id="S1.p4.1.m1.1.1.3.cmml" xref="S1.p4.1.m1.1.1.3"><csymbol cd="latexml" id="S1.p4.1.m1.1.1.3.1.cmml" xref="S1.p4.1.m1.1.1.3.1">percent</csymbol><cn type="integer" id="S1.p4.1.m1.1.1.3.2.cmml" xref="S1.p4.1.m1.1.1.3.2">90</cn></apply></apply></annotation-xml><annotation encoding="application/x-tex" id="S1.p4.1.m1.1c">\geq 90\%</annotation></semantics></math> accuracy) to achieve decent improvements over the simpler method, re-ranking.</p>
</div>
<div id="S1.p5" class="ltx_para ltx_noindent">
<p id="S1.p5.1" class="ltx_p"><span id="S1.p5.1.1" class="ltx_text ltx_font_bold">(2)</span> Using environmental feedback, we improve the discrimination accuracy of LLMs by up to 30.2 and 8.4 absolute points on text-to-SQL parsing and mathematical reasoning, respectively.
Yet, our end-to-end evaluations suggest they have barely met the need for advanced planning methods to show significant improvements over re-ranking.</p>
</div>
<div id="S1.p6" class="ltx_para ltx_noindent">
<p id="S1.p6.1" class="ltx_p"><span id="S1.p6.1.1" class="ltx_text ltx_font_bold">(3)</span> Meanwhile, advanced planning methods may not adequately balance accuracy and efficiency when using LLM-based discriminators.
In our experiments, compared to the other two methods, tree search is at least 10–20 times slower but leads to negligible performance gains.
This accuracy-efficiency trade-off can impede the deployment of tree search in real-world applications.</p>
</div>
</section>
<section id="S2" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">2 </span>Related Work</h2>

<div id="S2.p1" class="ltx_para">
<p id="S2.p1.1" class="ltx_p">A lot of recent research efforts have focused on advanced planning methods for improving the multi-step problem-solving abilities of LLMs (<cite class="ltx_cite ltx_citemacro_citet">Li et al. <a href="#bib.bib17" title="" class="ltx_ref">2023b</a>; Madaan et al. <a href="#bib.bib18" title="" class="ltx_ref">2023</a>; Wang et al. <a href="#bib.bib34" title="" class="ltx_ref">2023b</a>; Yao et al. <a href="#bib.bib39" title="" class="ltx_ref">2023a</a>, <a href="#bib.bib40" title="" class="ltx_ref">b</a>; Zhou et al. <a href="#bib.bib43" title="" class="ltx_ref">2023</a></cite>, <span id="S2.p1.1.1" class="ltx_text ltx_font_italic">inter alia</span>).
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 <cite class="ltx_cite ltx_citemacro_citep">(Mattar and Lengyel, <a href="#bib.bib19" title="" class="ltx_ref">2022</a>)</cite>.</p>
</div>
<div id="S2.p2" class="ltx_para">
<p id="S2.p2.1" class="ltx_p">While it is commonly believed that discrimination is easier than generation for human and AI agents <cite class="ltx_cite ltx_citemacro_citep">(Gu et al., <a href="#bib.bib12" title="" class="ltx_ref">2023</a>)</cite>, <cite class="ltx_cite ltx_citemacro_citet">West et al. (<a href="#bib.bib36" title="" class="ltx_ref">2024</a>)</cite> 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 <cite class="ltx_cite ltx_citemacro_citet">Huang et al. (<a href="#bib.bib13" title="" class="ltx_ref">2024</a>)</cite> and <cite class="ltx_cite ltx_citemacro_citet">Wang et al. (<a href="#bib.bib33" title="" class="ltx_ref">2023a</a>)</cite> that, without any external feedback or with obviously absurd feedback, LLMs may recognize some of their self-generated correct plans as wrong.
<cite class="ltx_cite ltx_citemacro_citet">Huang et al. (<a href="#bib.bib13" title="" class="ltx_ref">2024</a>)</cite> also note that the performance gains of self-correction, 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.</p>
</div>
<div id="S2.p3" class="ltx_para">
<p id="S2.p3.1" class="ltx_p">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.</p>
</div>
</section>
<section id="S3" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">3 </span>Our Framework</h2>

<figure id="S3.F2" class="ltx_figure">
<div class="ltx_flex_figure">
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S3.F2.1" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:138.8pt;"><img src="/html/2402.10890/assets/figures/rr.png" id="S3.F2.1.g1" class="ltx_graphics ltx_img_landscape" width="598" height="353" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(a) </span>Re-ranking.</figcaption>
</figure>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S3.F2.2" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:138.8pt;"><img src="/html/2402.10890/assets/figures/ic.png" id="S3.F2.2.g1" class="ltx_graphics ltx_img_landscape" width="598" height="353" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(b) </span>Iterative Correction.</figcaption>
</figure>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S3.F2.3" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:138.8pt;"><img src="/html/2402.10890/assets/figures/ts.png" id="S3.F2.3.g1" class="ltx_graphics ltx_img_landscape" width="598" height="353" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(c) </span>Tree Search.</figcaption>
</figure>
</div>
</div>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 2: </span>Illustration of three categories of planning methods examined in our unified generator-evaluator framework. </figcaption>
</figure>
<div id="S3.p1" class="ltx_para">
<p id="S3.p1.1" class="ltx_p">As shown in Figure <a href="#S1.F1" title="Figure 1 ‣ 1 Introduction ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a>, we systematically analyze different planning methods in a unified generator-discriminator 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 <a href="#S4.SS1" title="4.1 Tasks and Datasets ‣ 4 Experimental Setup ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4.1</span></a>).</p>
</div>
<section id="S3.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">3.1 </span>Generator</h3>

<div id="S3.SS1.p1" class="ltx_para">
<p id="S3.SS1.p1.1" class="ltx_p">For each planning step, we prompt the generator to sample action sequences (SQL queries or Python programs for math reasoning).
For text-to-SQL parsing, we use 1-shot prompting, where the example is retrieved from the training sets using BM25 <cite class="ltx_cite ltx_citemacro_citep">(Robertson and Zaragoza, <a href="#bib.bib26" title="" class="ltx_ref">2009</a>)</cite>.
For math reasoning, we use a fixed 2-shot prompt adapted from <cite class="ltx_cite ltx_citemacro_citet">Ni et al. (<a href="#bib.bib23" title="" class="ltx_ref">2023b</a>)</cite>.
See prompts in Appendix <a href="#A3" title="Appendix C Prompt Examples ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">C</span></a>.</p>
</div>
</section>
<section id="S3.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">3.2 </span>Discriminator</h3>

<div id="S3.SS2.p1" class="ltx_para">
<p id="S3.SS2.p1.1" class="ltx_p">Given some (partial) action sequences, we formulate the discrimination task as binary question answering <cite class="ltx_cite ltx_citemacro_citep">(Kadavath et al., <a href="#bib.bib14" title="" class="ltx_ref">2022</a>; Ke et al., <a href="#bib.bib15" title="" class="ltx_ref">2023</a>)</cite>.
The discrimination score of each tested example is the probability of “Yes” being generated as the next token.
Specifically, we prompt the LLMs with the question “Is the SQL/python program correct given the utterance/problem?” to generate one single token with its probability as the score.
With this formulation, we evaluate three types of LLMs in our experiments (Section <a href="#S4.SS2" title="4.2 Models ‣ 4 Experimental Setup ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4.2</span></a>).
Similar to the generator, we use 1-shot prompting with BM25 retrieval for text-to-SQL parsing and a fixed 2-shot prompt for math reasoning.
Details are in Appendix <a href="#A1" title="Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A</span></a>.</p>
</div>
</section>
<section id="S3.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">3.3 </span>Planning Methods</h3>

<div id="S3.SS3.p1" class="ltx_para ltx_noindent">
<p id="S3.SS3.p1.1" class="ltx_p"><span id="S3.SS3.p1.1.1" class="ltx_text ltx_font_bold">Re-ranking.</span>
Re-ranking is a straightforward planning method.
After sampling a few complete action sequences from the generator, it uses the discriminator to score them and return the highest-scoring plan (Figure <a href="#S3.F2" title="Figure 2 ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">2</span></a>).
Although simple, it is commonly used for code generation <cite class="ltx_cite ltx_citemacro_citep">(Ni et al., <a href="#bib.bib22" title="" class="ltx_ref">2023a</a>)</cite> and mathematical reasoning tasks <cite class="ltx_cite ltx_citemacro_citep">(Wang et al., <a href="#bib.bib34" title="" class="ltx_ref">2023b</a>; Li et al., <a href="#bib.bib17" title="" class="ltx_ref">2023b</a>)</cite>.
We consider re-ranking as a baseline planning method for more advanced ones.</p>
</div>
<div id="S3.SS3.p2" class="ltx_para ltx_noindent">
<p id="S3.SS3.p2.1" class="ltx_p"><span id="S3.SS3.p2.1.1" class="ltx_text ltx_font_bold">Iterative correction.</span>
Like re-ranking, iterative correction starts with the generator proposing a complete action sequence.
Then it leverages multiple rounds of revision to improve the initial plan based on the discriminator’s feedback (Figure <a href="#S3.F2" title="Figure 2 ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">2</span></a>).
When the generator and the discriminator are the same LLM, it becomes a prevalent planning method, self-correction <cite class="ltx_cite ltx_citemacro_citep">(Madaan et al., <a href="#bib.bib18" title="" class="ltx_ref">2023</a>; Shinn et al., <a href="#bib.bib29" title="" class="ltx_ref">2023</a>; Yao et al., <a href="#bib.bib40" title="" class="ltx_ref">2023b</a>; Chen et al., <a href="#bib.bib7" title="" class="ltx_ref">2024</a>)</cite>.</p>
</div>
<div id="S3.SS3.p3" class="ltx_para">
<p id="S3.SS3.p3.1" class="ltx_p">While some work uses greedy generation, our implementation samples the same number of action sequences as other planning methods for fair comparison.
Then, it uses the discriminator to select the best-scoring one for the next round’s revision.
We allow up to 10 rounds of corrections, with early exiting when the best plan meets a threshold of discrimination score (<math id="S3.SS3.p3.1.m1.1" class="ltx_Math" alttext="&gt;0.99" display="inline"><semantics id="S3.SS3.p3.1.m1.1a"><mrow id="S3.SS3.p3.1.m1.1.1" xref="S3.SS3.p3.1.m1.1.1.cmml"><mi id="S3.SS3.p3.1.m1.1.1.2" xref="S3.SS3.p3.1.m1.1.1.2.cmml"></mi><mo id="S3.SS3.p3.1.m1.1.1.1" xref="S3.SS3.p3.1.m1.1.1.1.cmml">&gt;</mo><mn id="S3.SS3.p3.1.m1.1.1.3" xref="S3.SS3.p3.1.m1.1.1.3.cmml">0.99</mn></mrow><annotation-xml encoding="MathML-Content" id="S3.SS3.p3.1.m1.1b"><apply id="S3.SS3.p3.1.m1.1.1.cmml" xref="S3.SS3.p3.1.m1.1.1"><gt id="S3.SS3.p3.1.m1.1.1.1.cmml" xref="S3.SS3.p3.1.m1.1.1.1"></gt><csymbol cd="latexml" id="S3.SS3.p3.1.m1.1.1.2.cmml" xref="S3.SS3.p3.1.m1.1.1.2">absent</csymbol><cn type="float" id="S3.SS3.p3.1.m1.1.1.3.cmml" xref="S3.SS3.p3.1.m1.1.1.3">0.99</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S3.SS3.p3.1.m1.1c">&gt;0.99</annotation></semantics></math>), or the score is not improved for 3 consecutive iterations.
For fair comparison, we prompt the generator to revise plans with 0-shot instruction following (Appendix <a href="#A3" title="Appendix C Prompt Examples ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">C</span></a>) instead of few-shot, since in-context examples may introduce additional information.</p>
</div>
<div id="S3.SS3.p4" class="ltx_para ltx_noindent">
<p id="S3.SS3.p4.1" class="ltx_p"><span id="S3.SS3.p4.1.1" class="ltx_text ltx_font_bold">Tree Search.</span>
Tree search is another popular planning method for language agents, such as Monte-Carlo Tree Search <cite class="ltx_cite ltx_citemacro_citep">(Chaffin et al., <a href="#bib.bib4" title="" class="ltx_ref">2022</a>)</cite>, Pangu <cite class="ltx_cite ltx_citemacro_citep">(Gu et al., <a href="#bib.bib12" title="" class="ltx_ref">2023</a>)</cite>, Tree of Thoughts <cite class="ltx_cite ltx_citemacro_citep">(Yao et al., <a href="#bib.bib39" title="" class="ltx_ref">2023a</a>)</cite>, and Language Agent Tree Search <cite class="ltx_cite ltx_citemacro_citep">(Zhou et al., <a href="#bib.bib43" title="" class="ltx_ref">2023</a>)</cite>.
It uses a memory structure (e.g., a heap) to store observed partial action sequences and their scores.
For each iteration, it prompts the generator for possible next steps for the current best partial plan, calls the discriminator to evaluate the steps, and updates the memory with new plans and scores (Figure <a href="#S3.F2" title="Figure 2 ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">2</span></a>).
Our tree search implementation is a kind of MCTS <cite class="ltx_cite ltx_citemacro_citep">(Zhang et al., <a href="#bib.bib42" title="" class="ltx_ref">2023</a>)</cite>:</p>
</div>
<div id="S3.SS3.p5" class="ltx_para ltx_noindent">
<p id="S3.SS3.p5.1" class="ltx_p"><span id="S3.SS3.p5.1.1" class="ltx_text ltx_font_bold">(1)</span> <span id="S3.SS3.p5.1.2" class="ltx_text ltx_font_italic">Selection</span>: Find the highest scoring partial plan in the memory, implemented as a heap structure.</p>
</div>
<div id="S3.SS3.p6" class="ltx_para ltx_noindent">
<p id="S3.SS3.p6.1" class="ltx_p"><span id="S3.SS3.p6.1.1" class="ltx_text ltx_font_bold">(2)</span> <span id="S3.SS3.p6.1.2" class="ltx_text ltx_font_italic">Expansion</span>: Prompt the generator for the next step of this partial plan.
We follow recent work to define a step to be a SQL clause <cite class="ltx_cite ltx_citemacro_citep">(Chen et al., <a href="#bib.bib8" title="" class="ltx_ref">2023c</a>)</cite> or one line of Python code <cite class="ltx_cite ltx_citemacro_citep">(Bui et al., <a href="#bib.bib2" title="" class="ltx_ref">2022</a>)</cite>, which is semantically more meaningful.</p>
</div>
<div id="S3.SS3.p7" class="ltx_para ltx_noindent">
<p id="S3.SS3.p7.1" class="ltx_p"><span id="S3.SS3.p7.1.1" class="ltx_text ltx_font_bold">(3)</span> <span id="S3.SS3.p7.1.2" class="ltx_text ltx_font_italic">Simulation</span>: Reuse the generator to complete the partial plans as Monte-Carlo simulations.</p>
</div>
<div id="S3.SS3.p8" class="ltx_para ltx_noindent">
<p id="S3.SS3.p8.1" class="ltx_p"><span id="S3.SS3.p8.1.1" class="ltx_text ltx_font_bold">(4)</span> <span id="S3.SS3.p8.1.2" class="ltx_text ltx_font_italic">Evaluation</span>: Evaluate the simulations with the discriminator.
The score for each new step is the maximum score of all simulations starting from it.</p>
</div>
<div id="S3.SS3.p9" class="ltx_para ltx_noindent">
<p id="S3.SS3.p9.1" class="ltx_p"><span id="S3.SS3.p9.1.1" class="ltx_text ltx_font_bold">(5)</span> <span id="S3.SS3.p9.1.2" class="ltx_text ltx_font_italic">Backpropagation</span>: Update the partial plan with the new step and score (if higher) and insert them into the heap memory.
After the update, if there is a complete plan in the heap memory, we terminate the tree search and return this plan.</p>
</div>
</section>
</section>
<section id="S4" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">4 </span>Experimental Setup</h2>

<section id="S4.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.1 </span>Tasks and Datasets</h3>

<div id="S4.SS1.p1" class="ltx_para ltx_noindent">
<p id="S4.SS1.p1.1" class="ltx_p"><span id="S4.SS1.p1.1.1" class="ltx_text ltx_font_bold">Text-to-SQL Parsing.</span>
Text-to-SQL parsing is a code generation task of mapping natural language utterances to SQL queries.
It requires agents to ground utterances to database environment and generate multi-step plans as SQL queries, making it an appropriate testbed in our study.
To evaluate language agents’ potential for text-to-SQL parsing, we adapt two widely used datasets, Spider <cite class="ltx_cite ltx_citemacro_citep">(Yu et al., <a href="#bib.bib41" title="" class="ltx_ref">2018</a>)</cite> and Bird <cite class="ltx_cite ltx_citemacro_citep">(Li et al., <a href="#bib.bib16" title="" class="ltx_ref">2023a</a>)</cite>.</p>
</div>
<div id="S4.SS1.p2" class="ltx_para">
<p id="S4.SS1.p2.1" class="ltx_p">We use the entire training split in each dataset to prompt or fine-tune LLMs.<span id="footnote2" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">2</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">2</sup><span class="ltx_tag ltx_tag_note">2</span>In Bird, we exclude training examples for one database, <span id="footnote2.1" class="ltx_text ltx_font_typewriter">retail_world</span>, due to annotation errors.</span></span></span>
For evaluation, due to resource and budget constraints, we randomly select 400 and 300 development set examples in Spider and Bird, respectively.
We also note that model performance may be lower on our evaluation sets because we uniformly sampled examples from each difficulty level, while the original development sets have skewed distributions towards easier examples (Appendix <a href="#A1.SS1" title="A.1 Text-to-SQL Parsing Evaluation Sets ‣ Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A.1</span></a>).</p>
</div>
<div id="S4.SS1.p3" class="ltx_para ltx_noindent">
<p id="S4.SS1.p3.1" class="ltx_p"><span id="S4.SS1.p3.1.1" class="ltx_text ltx_font_bold">Mathematical Reasoning.</span>
Mathematical reasoning is a common task for evaluating language agents’ multi-step reasoning and planning capabilities.
With 500 random examples from GSM8K’s development set <cite class="ltx_cite ltx_citemacro_citep">(Cobbe et al., <a href="#bib.bib9" title="" class="ltx_ref">2021</a>)</cite>, we follow program of thoughts <cite class="ltx_cite ltx_citemacro_citep">(Chen et al., <a href="#bib.bib6" title="" class="ltx_ref">2023b</a>)</cite> to test the agents’ ability to plan in Python programs and solve these grade school math word problems.</p>
</div>
</section>
<section id="S4.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.2 </span>Models</h3>

<div id="S4.SS2.p1" class="ltx_para">
<p id="S4.SS2.p1.1" class="ltx_p">In all experiments, we use CodeLlama-13B-Instruct as the generator in our framework.
We also evaluate three kinds of LLMs as the discriminator:
<span id="S4.SS2.p1.1.1" class="ltx_text ltx_font_bold">(1)</span> <span id="S4.SS2.p1.1.2" class="ltx_text ltx_font_italic">open-source LLMs</span>: CodeLlama-7B-Instruct and CodeLlama-13B-Instruct <cite class="ltx_cite ltx_citemacro_citep">(Rozière et al., <a href="#bib.bib27" title="" class="ltx_ref">2024</a>)</cite>,
<span id="S4.SS2.p1.1.3" class="ltx_text ltx_font_bold">(2)</span> <span id="S4.SS2.p1.1.4" class="ltx_text ltx_font_italic">closed-source LLMs</span>: GPT-3.5-Turbo <cite class="ltx_cite ltx_citemacro_citep">(OpenAI, <a href="#bib.bib24" title="" class="ltx_ref">2022</a>)</cite> and GPT-4-Turbo <cite class="ltx_cite ltx_citemacro_citep">(OpenAI, <a href="#bib.bib25" title="" class="ltx_ref">2023</a>)</cite>, and
<span id="S4.SS2.p1.1.5" class="ltx_text ltx_font_bold">(3)</span> <span id="S4.SS2.p1.1.6" class="ltx_text ltx_font_italic">fine-tuned LLMs</span>: CodeLlama-7B-Instruct-FT and CodeLlama-13B-Instruct-FT.
Their implementation details are in Appendix <a href="#A1.SS3" title="A.3 Prompting and Training LLMs ‣ Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A.3</span></a>.
For brevity, we will omit “Instruct” in model names.</p>
</div>
</section>
<section id="S4.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">4.3 </span>Evaluation</h3>

<div id="S4.SS3.p1" class="ltx_para ltx_noindent">
<p id="S4.SS3.p1.1" class="ltx_p"><span id="S4.SS3.p1.1.1" class="ltx_text ltx_font_bold">Intrinsic Evaluation.</span>
We measure the discrimination abilities of LLMs with four intrinsic metrics.
<span id="S4.SS3.p1.1.2" class="ltx_text ltx_font_bold">(1)</span> Discrimination accuracy (<span id="S4.SS3.p1.1.3" class="ltx_text ltx_font_bold">Acc</span>): Given a pair of correct and wrong programs, we calculate the percentage where the correct program obtains a higher discrimination score than the wrong one <cite class="ltx_cite ltx_citemacro_citep">(Bai et al., <a href="#bib.bib1" title="" class="ltx_ref">2022</a>; Touvron et al., <a href="#bib.bib31" title="" class="ltx_ref">2023</a>)</cite>.
<span id="S4.SS3.p1.1.4" class="ltx_text ltx_font_bold">(2)</span> Classification macro F1 (<span id="S4.SS3.p1.1.5" class="ltx_text ltx_font_bold">F1</span>): We treat “correct” and “wrong” as two classes and compute the macro average of F1 scores on these two labels.
<span id="S4.SS3.p1.1.6" class="ltx_text ltx_font_bold">(3)</span> Hit@1 (<span id="S4.SS3.p1.1.7" class="ltx_text ltx_font_bold">H@1</span>): Given a batch of candidate programs, we calculate the percentage where the highest scoring candidate is correct.
<span id="S4.SS3.p1.1.8" class="ltx_text ltx_font_bold">(4)</span> Mean reciprocal rank (<span id="S4.SS3.p1.1.9" class="ltx_text ltx_font_bold">MRR</span>): We compute the standard MRR score by the highest-ranking correct program in the batches.</p>
</div>
<div id="S4.SS3.p2" class="ltx_para ltx_noindent">
<p id="S4.SS3.p2.1" class="ltx_p"><span id="S4.SS3.p2.1.1" class="ltx_text ltx_font_bold">End-to-End Evaluation.</span>
To show the impact of discriminators, we evaluate language agents’ end-to-end performance using our three planning methods, with execution accuracy for text-to-SQL parsing and answer accuracy for math reasoning.</p>
</div>
</section>
</section>
<section id="S5" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">5 </span>Simulation Experiments with Oracle</h2>

<figure id="S5.F3" class="ltx_figure">
<div class="ltx_flex_figure">
<div class="ltx_flex_cell ltx_flex_size_3">
<div id="S5.F3.1" class="ltx_block ltx_figure_panel ltx_minipage ltx_align_middle" style="width:143.1pt;">
<img src="/html/2402.10890/assets/figures/oracle_spider.png" id="S5.F3.1.g1" class="ltx_graphics ltx_img_landscape" width="598" height="461" alt="Refer to caption">
</div>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<div id="S5.F3.2" class="ltx_block ltx_figure_panel ltx_minipage ltx_align_middle" style="width:143.1pt;">
<img src="/html/2402.10890/assets/figures/oracle_bird.png" id="S5.F3.2.g1" class="ltx_graphics ltx_img_landscape" width="598" height="461" alt="Refer to caption">
</div>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<div id="S5.F3.3" class="ltx_block ltx_figure_panel ltx_minipage ltx_align_middle" style="width:143.1pt;">
<img src="/html/2402.10890/assets/figures/oracle_gsm8k.png" id="S5.F3.3.g1" class="ltx_graphics ltx_img_landscape" width="598" height="461" alt="Refer to caption">
</div>
</div>
<div class="ltx_flex_break"></div>
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S5.F3.4" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:143.1pt;"><img src="/html/2402.10890/assets/figures/oracle_spider_time.png" id="S5.F3.4.g1" class="ltx_graphics ltx_img_landscape" width="598" height="463" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(a) </span>Spider.</figcaption>
</figure>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S5.F3.5" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:143.1pt;"><img src="/html/2402.10890/assets/figures/oracle_bird_time.png" id="S5.F3.5.g1" class="ltx_graphics ltx_centering ltx_img_landscape" width="598" height="463" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(b) </span>Bird.</figcaption>
</figure>
</div>
<div class="ltx_flex_cell ltx_flex_size_3">
<figure id="S5.F3.6" class="ltx_figure ltx_figure_panel ltx_minipage ltx_align_center ltx_align_middle" style="width:143.1pt;"><img src="/html/2402.10890/assets/figures/oracle_gsm8k_time.png" id="S5.F3.6.g1" class="ltx_graphics ltx_img_landscape" width="598" height="463" alt="Refer to caption">
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">(c) </span>GSM8K.</figcaption>
</figure>
</div>
</div>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_figure">Figure 3: </span>End-to-end evaluation results (the first row) and average inference time in log scale (the second row) of our simulation experiments with oracle.
</figcaption>
</figure>
<section id="S5.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">5.1 </span>Oracle-Based Discriminator</h3>

<div id="S5.SS1.p1" class="ltx_para">
<p id="S5.SS1.p1.1" class="ltx_p">To investigate how discrimination accuracy affects the overall performance of language agents using different planning methods (<span id="S5.SS1.p1.1.1" class="ltx_text ltx_font_italic">RQ1</span>), we utilize oracle environmental feedback to simulate a discriminator with controllable accuracy.
For text-to-SQL parsing, we compare the first five rows in the execution results of predicted and gold SQL queries and calculate their table cell overlaps (Appendix <a href="#A1.SS4" title="A.4 Implemendation of Oracle Discriminator ‣ Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A.4</span></a>). For mathematical reasoning, we compare the predicted Python programs’ answers with the ground truth.</p>
</div>
<div id="S5.SS1.p2" class="ltx_para">
<p id="S5.SS1.p2.7" class="ltx_p">We use a probability-based threshold <math id="S5.SS1.p2.1.m1.1" class="ltx_Math" alttext="\tau" display="inline"><semantics id="S5.SS1.p2.1.m1.1a"><mi id="S5.SS1.p2.1.m1.1.1" xref="S5.SS1.p2.1.m1.1.1.cmml">τ</mi><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.1.m1.1b"><ci id="S5.SS1.p2.1.m1.1.1.cmml" xref="S5.SS1.p2.1.m1.1.1">𝜏</ci></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.1.m1.1c">\tau</annotation></semantics></math> to control the accuracy of each simulated discriminator <cite class="ltx_cite ltx_citemacro_citep">(Gao et al., <a href="#bib.bib11" title="" class="ltx_ref">2022</a>)</cite>.
When evaluating each plan, the discriminator first computes a score <math id="S5.SS1.p2.2.m2.1" class="ltx_Math" alttext="s" display="inline"><semantics id="S5.SS1.p2.2.m2.1a"><mi id="S5.SS1.p2.2.m2.1.1" xref="S5.SS1.p2.2.m2.1.1.cmml">s</mi><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.2.m2.1b"><ci id="S5.SS1.p2.2.m2.1.1.cmml" xref="S5.SS1.p2.2.m2.1.1">𝑠</ci></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.2.m2.1c">s</annotation></semantics></math> with oracle information.
Then, it uses a random function to generate a number <math id="S5.SS1.p2.3.m3.2" class="ltx_Math" alttext="p\in[0,1)" display="inline"><semantics id="S5.SS1.p2.3.m3.2a"><mrow id="S5.SS1.p2.3.m3.2.3" xref="S5.SS1.p2.3.m3.2.3.cmml"><mi id="S5.SS1.p2.3.m3.2.3.2" xref="S5.SS1.p2.3.m3.2.3.2.cmml">p</mi><mo id="S5.SS1.p2.3.m3.2.3.1" xref="S5.SS1.p2.3.m3.2.3.1.cmml">∈</mo><mrow id="S5.SS1.p2.3.m3.2.3.3.2" xref="S5.SS1.p2.3.m3.2.3.3.1.cmml"><mo stretchy="false" id="S5.SS1.p2.3.m3.2.3.3.2.1" xref="S5.SS1.p2.3.m3.2.3.3.1.cmml">[</mo><mn id="S5.SS1.p2.3.m3.1.1" xref="S5.SS1.p2.3.m3.1.1.cmml">0</mn><mo id="S5.SS1.p2.3.m3.2.3.3.2.2" xref="S5.SS1.p2.3.m3.2.3.3.1.cmml">,</mo><mn id="S5.SS1.p2.3.m3.2.2" xref="S5.SS1.p2.3.m3.2.2.cmml">1</mn><mo stretchy="false" id="S5.SS1.p2.3.m3.2.3.3.2.3" xref="S5.SS1.p2.3.m3.2.3.3.1.cmml">)</mo></mrow></mrow><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.3.m3.2b"><apply id="S5.SS1.p2.3.m3.2.3.cmml" xref="S5.SS1.p2.3.m3.2.3"><in id="S5.SS1.p2.3.m3.2.3.1.cmml" xref="S5.SS1.p2.3.m3.2.3.1"></in><ci id="S5.SS1.p2.3.m3.2.3.2.cmml" xref="S5.SS1.p2.3.m3.2.3.2">𝑝</ci><interval closure="closed-open" id="S5.SS1.p2.3.m3.2.3.3.1.cmml" xref="S5.SS1.p2.3.m3.2.3.3.2"><cn type="integer" id="S5.SS1.p2.3.m3.1.1.cmml" xref="S5.SS1.p2.3.m3.1.1">0</cn><cn type="integer" id="S5.SS1.p2.3.m3.2.2.cmml" xref="S5.SS1.p2.3.m3.2.2">1</cn></interval></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.3.m3.2c">p\in[0,1)</annotation></semantics></math>.
If <math id="S5.SS1.p2.4.m4.1" class="ltx_Math" alttext="p&lt;\tau" display="inline"><semantics id="S5.SS1.p2.4.m4.1a"><mrow id="S5.SS1.p2.4.m4.1.1" xref="S5.SS1.p2.4.m4.1.1.cmml"><mi id="S5.SS1.p2.4.m4.1.1.2" xref="S5.SS1.p2.4.m4.1.1.2.cmml">p</mi><mo id="S5.SS1.p2.4.m4.1.1.1" xref="S5.SS1.p2.4.m4.1.1.1.cmml">&lt;</mo><mi id="S5.SS1.p2.4.m4.1.1.3" xref="S5.SS1.p2.4.m4.1.1.3.cmml">τ</mi></mrow><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.4.m4.1b"><apply id="S5.SS1.p2.4.m4.1.1.cmml" xref="S5.SS1.p2.4.m4.1.1"><lt id="S5.SS1.p2.4.m4.1.1.1.cmml" xref="S5.SS1.p2.4.m4.1.1.1"></lt><ci id="S5.SS1.p2.4.m4.1.1.2.cmml" xref="S5.SS1.p2.4.m4.1.1.2">𝑝</ci><ci id="S5.SS1.p2.4.m4.1.1.3.cmml" xref="S5.SS1.p2.4.m4.1.1.3">𝜏</ci></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.4.m4.1c">p&lt;\tau</annotation></semantics></math>, the discriminator returns the score <math id="S5.SS1.p2.5.m5.1" class="ltx_Math" alttext="s" display="inline"><semantics id="S5.SS1.p2.5.m5.1a"><mi id="S5.SS1.p2.5.m5.1.1" xref="S5.SS1.p2.5.m5.1.1.cmml">s</mi><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.5.m5.1b"><ci id="S5.SS1.p2.5.m5.1.1.cmml" xref="S5.SS1.p2.5.m5.1.1">𝑠</ci></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.5.m5.1c">s</annotation></semantics></math>.
Otherwise, it returns an inverted score <math id="S5.SS1.p2.6.m6.1" class="ltx_Math" alttext="1-s" display="inline"><semantics id="S5.SS1.p2.6.m6.1a"><mrow id="S5.SS1.p2.6.m6.1.1" xref="S5.SS1.p2.6.m6.1.1.cmml"><mn id="S5.SS1.p2.6.m6.1.1.2" xref="S5.SS1.p2.6.m6.1.1.2.cmml">1</mn><mo id="S5.SS1.p2.6.m6.1.1.1" xref="S5.SS1.p2.6.m6.1.1.1.cmml">−</mo><mi id="S5.SS1.p2.6.m6.1.1.3" xref="S5.SS1.p2.6.m6.1.1.3.cmml">s</mi></mrow><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.6.m6.1b"><apply id="S5.SS1.p2.6.m6.1.1.cmml" xref="S5.SS1.p2.6.m6.1.1"><minus id="S5.SS1.p2.6.m6.1.1.1.cmml" xref="S5.SS1.p2.6.m6.1.1.1"></minus><cn type="integer" id="S5.SS1.p2.6.m6.1.1.2.cmml" xref="S5.SS1.p2.6.m6.1.1.2">1</cn><ci id="S5.SS1.p2.6.m6.1.1.3.cmml" xref="S5.SS1.p2.6.m6.1.1.3">𝑠</ci></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.6.m6.1c">1-s</annotation></semantics></math>.
In this way, we ensure that the discriminator’s accuracy is at most <math id="S5.SS1.p2.7.m7.1" class="ltx_Math" alttext="\tau" display="inline"><semantics id="S5.SS1.p2.7.m7.1a"><mi id="S5.SS1.p2.7.m7.1.1" xref="S5.SS1.p2.7.m7.1.1.cmml">τ</mi><annotation-xml encoding="MathML-Content" id="S5.SS1.p2.7.m7.1b"><ci id="S5.SS1.p2.7.m7.1.1.cmml" xref="S5.SS1.p2.7.m7.1.1">𝜏</ci></annotation-xml><annotation encoding="application/x-tex" id="S5.SS1.p2.7.m7.1c">\tau</annotation></semantics></math>.</p>
</div>
</section>
<section id="S5.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">5.2 </span>Results and Analysis</h3>

<div id="S5.SS2.p1" class="ltx_para">
<p id="S5.SS2.p1.1" class="ltx_p">As shown in Figure <a href="#S5.F3" title="Figure 3 ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>, discrimination accuracy closely correlates with the performance of agents on all three datasets, no matter which planning method is used.
For instance, the performance of re-ranking agents improves linearly as we increase the discrimination accuracy threshold, setting up a strong baseline for agents using other planning methods.
We also note that it takes around <math id="S5.SS2.p1.1.m1.1" class="ltx_Math" alttext="80\%" display="inline"><semantics id="S5.SS2.p1.1.m1.1a"><mrow id="S5.SS2.p1.1.m1.1.1" xref="S5.SS2.p1.1.m1.1.1.cmml"><mn id="S5.SS2.p1.1.m1.1.1.2" xref="S5.SS2.p1.1.m1.1.1.2.cmml">80</mn><mo id="S5.SS2.p1.1.m1.1.1.1" xref="S5.SS2.p1.1.m1.1.1.1.cmml">%</mo></mrow><annotation-xml encoding="MathML-Content" id="S5.SS2.p1.1.m1.1b"><apply id="S5.SS2.p1.1.m1.1.1.cmml" xref="S5.SS2.p1.1.m1.1.1"><csymbol cd="latexml" id="S5.SS2.p1.1.m1.1.1.1.cmml" xref="S5.SS2.p1.1.m1.1.1.1">percent</csymbol><cn type="integer" id="S5.SS2.p1.1.m1.1.1.2.cmml" xref="S5.SS2.p1.1.m1.1.1.2">80</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p1.1.m1.1c">80\%</annotation></semantics></math> discrimination accuracy for all agents to outperform greedy generation on text-to-SQL parsing, demonstrating the task’s difficulty.
To answer <span id="S5.SS2.p1.1.1" class="ltx_text ltx_font_italic">RQ1</span>, we further analyze the performance of agents using iterative correction and tree search as follows:</p>
</div>
<div id="S5.SS2.p2" class="ltx_para">
<p id="S5.SS2.p2.3" class="ltx_p"><span id="S5.SS2.p2.3.1" class="ltx_text ltx_font_bold">Advanced planning methods demand highly accurate discriminators.</span>
For iterative correction agents, their performance usually cannot distinguish from the re-ranking baselines until we maximize the threshold <math id="S5.SS2.p2.1.m1.1" class="ltx_Math" alttext="\tau=1.0" display="inline"><semantics id="S5.SS2.p2.1.m1.1a"><mrow id="S5.SS2.p2.1.m1.1.1" xref="S5.SS2.p2.1.m1.1.1.cmml"><mi id="S5.SS2.p2.1.m1.1.1.2" xref="S5.SS2.p2.1.m1.1.1.2.cmml">τ</mi><mo id="S5.SS2.p2.1.m1.1.1.1" xref="S5.SS2.p2.1.m1.1.1.1.cmml">=</mo><mn id="S5.SS2.p2.1.m1.1.1.3" xref="S5.SS2.p2.1.m1.1.1.3.cmml">1.0</mn></mrow><annotation-xml encoding="MathML-Content" id="S5.SS2.p2.1.m1.1b"><apply id="S5.SS2.p2.1.m1.1.1.cmml" xref="S5.SS2.p2.1.m1.1.1"><eq id="S5.SS2.p2.1.m1.1.1.1.cmml" xref="S5.SS2.p2.1.m1.1.1.1"></eq><ci id="S5.SS2.p2.1.m1.1.1.2.cmml" xref="S5.SS2.p2.1.m1.1.1.2">𝜏</ci><cn type="float" id="S5.SS2.p2.1.m1.1.1.3.cmml" xref="S5.SS2.p2.1.m1.1.1.3">1.0</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p2.1.m1.1c">\tau=1.0</annotation></semantics></math> (Figure <a href="#S5.F3" title="Figure 3 ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>).
This finding resonates with <cite class="ltx_cite ltx_citemacro_citet">Huang et al. (<a href="#bib.bib13" title="" class="ltx_ref">2024</a>)</cite> that high-quality feedback may be the key to the success of iterative correction.
More interestingly, tree search agents consistently underperform the other two when the discrimination accuracy threshold <math id="S5.SS2.p2.2.m2.1" class="ltx_Math" alttext="\tau\leq 0.8" display="inline"><semantics id="S5.SS2.p2.2.m2.1a"><mrow id="S5.SS2.p2.2.m2.1.1" xref="S5.SS2.p2.2.m2.1.1.cmml"><mi id="S5.SS2.p2.2.m2.1.1.2" xref="S5.SS2.p2.2.m2.1.1.2.cmml">τ</mi><mo id="S5.SS2.p2.2.m2.1.1.1" xref="S5.SS2.p2.2.m2.1.1.1.cmml">≤</mo><mn id="S5.SS2.p2.2.m2.1.1.3" xref="S5.SS2.p2.2.m2.1.1.3.cmml">0.8</mn></mrow><annotation-xml encoding="MathML-Content" id="S5.SS2.p2.2.m2.1b"><apply id="S5.SS2.p2.2.m2.1.1.cmml" xref="S5.SS2.p2.2.m2.1.1"><leq id="S5.SS2.p2.2.m2.1.1.1.cmml" xref="S5.SS2.p2.2.m2.1.1.1"></leq><ci id="S5.SS2.p2.2.m2.1.1.2.cmml" xref="S5.SS2.p2.2.m2.1.1.2">𝜏</ci><cn type="float" id="S5.SS2.p2.2.m2.1.1.3.cmml" xref="S5.SS2.p2.2.m2.1.1.3">0.8</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p2.2.m2.1c">\tau\leq 0.8</annotation></semantics></math>.
Moreover, when raising the threshold to <math id="S5.SS2.p2.3.m3.1" class="ltx_Math" alttext="0.9" display="inline"><semantics id="S5.SS2.p2.3.m3.1a"><mn id="S5.SS2.p2.3.m3.1.1" xref="S5.SS2.p2.3.m3.1.1.cmml">0.9</mn><annotation-xml encoding="MathML-Content" id="S5.SS2.p2.3.m3.1b"><cn type="float" id="S5.SS2.p2.3.m3.1.1.cmml" xref="S5.SS2.p2.3.m3.1.1">0.9</cn></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p2.3.m3.1c">0.9</annotation></semantics></math>, we observe a sharp increase of their performance, with which they start to beat other kinds of agents.</p>
</div>
<div id="S5.SS2.p3" class="ltx_para">
<p id="S5.SS2.p3.2" class="ltx_p"><span id="S5.SS2.p3.2.1" class="ltx_text ltx_font_bold">Advanced planning methods may not adequately balance accuracy and efficiency.</span>
By calculating the average inference time per example (Figure <a href="#S5.F3" title="Figure 3 ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>), we find that our implementation of tree search is at least <math id="S5.SS2.p3.1.m1.1" class="ltx_Math" alttext="10" display="inline"><semantics id="S5.SS2.p3.1.m1.1a"><mn id="S5.SS2.p3.1.m1.1.1" xref="S5.SS2.p3.1.m1.1.1.cmml">10</mn><annotation-xml encoding="MathML-Content" id="S5.SS2.p3.1.m1.1b"><cn type="integer" id="S5.SS2.p3.1.m1.1.1.cmml" xref="S5.SS2.p3.1.m1.1.1">10</cn></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p3.1.m1.1c">10</annotation></semantics></math>–<math id="S5.SS2.p3.2.m2.1" class="ltx_Math" alttext="20" display="inline"><semantics id="S5.SS2.p3.2.m2.1a"><mn id="S5.SS2.p3.2.m2.1.1" xref="S5.SS2.p3.2.m2.1.1.cmml">20</mn><annotation-xml encoding="MathML-Content" id="S5.SS2.p3.2.m2.1b"><cn type="integer" id="S5.SS2.p3.2.m2.1.1.cmml" xref="S5.SS2.p3.2.m2.1.1">20</cn></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p3.2.m2.1c">20</annotation></semantics></math> times slower than the other two planning methods, mainly due to frequent generation of Monte-Carlo simulations <cite class="ltx_cite ltx_citemacro_citep">(Zhang et al., <a href="#bib.bib42" title="" class="ltx_ref">2023</a>)</cite>.
While we can remove the simulations to be more efficient and evaluate partial plans, in our preliminary study, we find LLMs would struggle in this setting. This accuracy-efficiency trade-off may hinder real-world applications of tree search methods.
Meanwhile, the inference time for iterative correction increases as the accuracy threshold is raised, suggesting more iterations are required to derive a correct answer.
This indicates that developing efficient and accurate planning methods remains a key problem for AI agents.
</p>
</div>
<div id="S5.SS2.p4" class="ltx_para">
<p id="S5.SS2.p4.1" class="ltx_p"><span id="S5.SS2.p4.1.1" class="ltx_text ltx_font_bold">Monte-Carlo tree search can be unstable, especially in the early stages.</span>
We observe that iterative correction outperforms tree search on Bird (Figure <a href="#S5.F3" title="Figure 3 ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>) when the accuracy threshold is 1.0.
This observation may be caused by the instability of Monte-Carlo tree search.
We first note that McNemar’s test finds no difference between iterative correction and tree search (<math id="S5.SS2.p4.1.m1.1" class="ltx_Math" alttext="p&gt;0.05" display="inline"><semantics id="S5.SS2.p4.1.m1.1a"><mrow id="S5.SS2.p4.1.m1.1.1" xref="S5.SS2.p4.1.m1.1.1.cmml"><mi id="S5.SS2.p4.1.m1.1.1.2" xref="S5.SS2.p4.1.m1.1.1.2.cmml">p</mi><mo id="S5.SS2.p4.1.m1.1.1.1" xref="S5.SS2.p4.1.m1.1.1.1.cmml">&gt;</mo><mn id="S5.SS2.p4.1.m1.1.1.3" xref="S5.SS2.p4.1.m1.1.1.3.cmml">0.05</mn></mrow><annotation-xml encoding="MathML-Content" id="S5.SS2.p4.1.m1.1b"><apply id="S5.SS2.p4.1.m1.1.1.cmml" xref="S5.SS2.p4.1.m1.1.1"><gt id="S5.SS2.p4.1.m1.1.1.1.cmml" xref="S5.SS2.p4.1.m1.1.1.1"></gt><ci id="S5.SS2.p4.1.m1.1.1.2.cmml" xref="S5.SS2.p4.1.m1.1.1.2">𝑝</ci><cn type="float" id="S5.SS2.p4.1.m1.1.1.3.cmml" xref="S5.SS2.p4.1.m1.1.1.3">0.05</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S5.SS2.p4.1.m1.1c">p&gt;0.05</annotation></semantics></math>), despite their performance gap (29.3 vs 32.7).
The rationales are discussed in Appendix <a href="#A2" title="Appendix B McNemar’s Test for Statistical Significance ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">B</span></a>.
Furthermore, we analyze all 25 examples of which iterative correction derives the correct answer but tree search fails.
In 12 out of the 25 examples (48%), tree search fails to select the correct partial plan when the discrimination scores are the same.
Especially, this can happen in the early stages of tree search, where a correct program has not yet been discovered and all the steps receive a score of 0 from the oracle discriminator.
Thus, we consider this underperformance a consequence of search instability.
</p>
</div>
</section>
</section>
<section id="S6" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">6 </span>LLM-Based Discriminators</h2>

<figure id="S6.T1" class="ltx_table">
<table id="S6.T1.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S6.T1.1.1" class="ltx_tr">
<td id="S6.T1.1.1.2" class="ltx_td ltx_align_left ltx_border_tt" rowspan="2"><span id="S6.T1.1.1.2.1" class="ltx_text ltx_font_bold">Models</span></td>
<td id="S6.T1.1.1.3" class="ltx_td ltx_align_center ltx_border_tt" colspan="4"><span id="S6.T1.1.1.3.1" class="ltx_text ltx_font_bold">Spider</span></td>
<td id="S6.T1.1.1.4" class="ltx_td ltx_align_center ltx_border_tt" colspan="4"><span id="S6.T1.1.1.4.1" class="ltx_text ltx_font_bold">Bird</span></td>
<td id="S6.T1.1.1.1" class="ltx_td ltx_align_center ltx_border_tt" colspan="4"><span id="S6.T1.1.1.1.1" class="ltx_text ltx_font_bold">GSM8K<sup id="S6.T1.1.1.1.1.1" class="ltx_sup"><span id="S6.T1.1.1.1.1.1.1" class="ltx_text ltx_font_medium ltx_font_italic">‡</span></sup></span></td>
</tr>
<tr id="S6.T1.1.2" class="ltx_tr">
<td id="S6.T1.1.2.1" class="ltx_td ltx_align_center ltx_border_t">Acc</td>
<td id="S6.T1.1.2.2" class="ltx_td ltx_align_center ltx_border_t">F1</td>
<td id="S6.T1.1.2.3" class="ltx_td ltx_align_center ltx_border_t">H@1</td>
<td id="S6.T1.1.2.4" class="ltx_td ltx_align_center ltx_border_t">MRR</td>
<td id="S6.T1.1.2.5" class="ltx_td ltx_align_center ltx_border_t">Acc</td>
<td id="S6.T1.1.2.6" class="ltx_td ltx_align_center ltx_border_t">F1</td>
<td id="S6.T1.1.2.7" class="ltx_td ltx_align_center ltx_border_t">H@1</td>
<td id="S6.T1.1.2.8" class="ltx_td ltx_align_center ltx_border_t">MRR</td>
<td id="S6.T1.1.2.9" class="ltx_td ltx_align_center ltx_border_t">Acc</td>
<td id="S6.T1.1.2.10" class="ltx_td ltx_align_center ltx_border_t">F1</td>
<td id="S6.T1.1.2.11" class="ltx_td ltx_align_center ltx_border_t">H@1</td>
<td id="S6.T1.1.2.12" class="ltx_td ltx_align_center ltx_border_t">MRR</td>
</tr>
<tr id="S6.T1.1.3" class="ltx_tr">
<td id="S6.T1.1.3.1" class="ltx_td ltx_align_left ltx_border_t">CodeLlama-7B</td>
<td id="S6.T1.1.3.2" class="ltx_td ltx_align_center ltx_border_t">54.0</td>
<td id="S6.T1.1.3.3" class="ltx_td ltx_align_center ltx_border_t">37.1</td>
<td id="S6.T1.1.3.4" class="ltx_td ltx_align_center ltx_border_t">56.0</td>
<td id="S6.T1.1.3.5" class="ltx_td ltx_align_center ltx_border_t">62.3</td>
<td id="S6.T1.1.3.6" class="ltx_td ltx_align_center ltx_border_t">44.6</td>
<td id="S6.T1.1.3.7" class="ltx_td ltx_align_center ltx_border_t"><span id="S6.T1.1.3.7.1" class="ltx_text ltx_font_bold">46.7</span></td>
<td id="S6.T1.1.3.8" class="ltx_td ltx_align_center ltx_border_t">13.0</td>
<td id="S6.T1.1.3.9" class="ltx_td ltx_align_center ltx_border_t">18.0</td>
<td id="S6.T1.1.3.10" class="ltx_td ltx_align_center ltx_border_t">48.6</td>
<td id="S6.T1.1.3.11" class="ltx_td ltx_align_center ltx_border_t"><span id="S6.T1.1.3.11.1" class="ltx_text ltx_font_bold">38.7</span></td>
<td id="S6.T1.1.3.12" class="ltx_td ltx_align_center ltx_border_t">36.2</td>
<td id="S6.T1.1.3.13" class="ltx_td ltx_align_center ltx_border_t">46.9</td>
</tr>
<tr id="S6.T1.1.4" class="ltx_tr">
<td id="S6.T1.1.4.1" class="ltx_td ltx_align_left">CodeLlama-13B</td>
<td id="S6.T1.1.4.2" class="ltx_td ltx_align_center">58.2</td>
<td id="S6.T1.1.4.3" class="ltx_td ltx_align_center">37.1</td>
<td id="S6.T1.1.4.4" class="ltx_td ltx_align_center">57.0</td>
<td id="S6.T1.1.4.5" class="ltx_td ltx_align_center">63.1</td>
<td id="S6.T1.1.4.6" class="ltx_td ltx_align_center">49.4</td>
<td id="S6.T1.1.4.7" class="ltx_td ltx_align_center"><span id="S6.T1.1.4.7.1" class="ltx_text ltx_font_bold">46.7</span></td>
<td id="S6.T1.1.4.8" class="ltx_td ltx_align_center">12.7</td>
<td id="S6.T1.1.4.9" class="ltx_td ltx_align_center">18.3</td>
<td id="S6.T1.1.4.10" class="ltx_td ltx_align_center"><span id="S6.T1.1.4.10.1" class="ltx_text ltx_font_bold">62.2</span></td>
<td id="S6.T1.1.4.11" class="ltx_td ltx_align_center"><span id="S6.T1.1.4.11.1" class="ltx_text ltx_font_bold">38.7</span></td>
<td id="S6.T1.1.4.12" class="ltx_td ltx_align_center"><span id="S6.T1.1.4.12.1" class="ltx_text ltx_font_bold">41.8</span></td>
<td id="S6.T1.1.4.13" class="ltx_td ltx_align_center"><span id="S6.T1.1.4.13.1" class="ltx_text ltx_font_bold">51.0</span></td>
</tr>
<tr id="S6.T1.1.5" class="ltx_tr">
<td id="S6.T1.1.5.1" class="ltx_td ltx_align_left">CodeLlama-7B-FT</td>
<td id="S6.T1.1.5.2" class="ltx_td ltx_align_center">62.4</td>
<td id="S6.T1.1.5.3" class="ltx_td ltx_align_center">60.3</td>
<td id="S6.T1.1.5.4" class="ltx_td ltx_align_center">59.5</td>
<td id="S6.T1.1.5.5" class="ltx_td ltx_align_center">64.6</td>
<td id="S6.T1.1.5.6" class="ltx_td ltx_align_center">52.4</td>
<td id="S6.T1.1.5.7" class="ltx_td ltx_align_center"><span id="S6.T1.1.5.7.1" class="ltx_text ltx_font_bold">46.7</span></td>
<td id="S6.T1.1.5.8" class="ltx_td ltx_align_center">14.3</td>
<td id="S6.T1.1.5.9" class="ltx_td ltx_align_center">19.1</td>
<td id="S6.T1.1.5.10" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.5.11" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.5.12" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.5.13" class="ltx_td ltx_align_center">-</td>
</tr>
<tr id="S6.T1.1.6" class="ltx_tr">
<td id="S6.T1.1.6.1" class="ltx_td ltx_align_left">CodeLlama-13B-FT</td>
<td id="S6.T1.1.6.2" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.2.1" class="ltx_text ltx_font_bold">69.7</span></td>
<td id="S6.T1.1.6.3" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.3.1" class="ltx_text ltx_font_bold">67.2</span></td>
<td id="S6.T1.1.6.4" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.4.1" class="ltx_text ltx_font_bold">61.3</span></td>
<td id="S6.T1.1.6.5" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.5.1" class="ltx_text ltx_font_bold">65.7</span></td>
<td id="S6.T1.1.6.6" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.6.1" class="ltx_text ltx_font_bold">62.1</span></td>
<td id="S6.T1.1.6.7" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.7.1" class="ltx_text ltx_font_bold">46.7</span></td>
<td id="S6.T1.1.6.8" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.8.1" class="ltx_text ltx_font_bold">16.0</span></td>
<td id="S6.T1.1.6.9" class="ltx_td ltx_align_center"><span id="S6.T1.1.6.9.1" class="ltx_text ltx_font_bold">20.5</span></td>
<td id="S6.T1.1.6.10" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.6.11" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.6.12" class="ltx_td ltx_align_center">-</td>
<td id="S6.T1.1.6.13" class="ltx_td ltx_align_center">-</td>
</tr>
<tr id="S6.T1.1.7" class="ltx_tr">
<td id="S6.T1.1.7.1" class="ltx_td ltx_align_left ltx_border_t">GPT-3.5-Turbo</td>
<td id="S6.T1.1.7.2" class="ltx_td ltx_align_center ltx_border_t">67.0</td>
<td id="S6.T1.1.7.3" class="ltx_td ltx_align_center ltx_border_t">47.3</td>
<td id="S6.T1.1.7.4" class="ltx_td ltx_align_center ltx_border_t">59.0</td>
<td id="S6.T1.1.7.5" class="ltx_td ltx_align_center ltx_border_t">64.3</td>
<td id="S6.T1.1.7.6" class="ltx_td ltx_align_center ltx_border_t">64.3</td>
<td id="S6.T1.1.7.7" class="ltx_td ltx_align_center ltx_border_t">35.7</td>
<td id="S6.T1.1.7.8" class="ltx_td ltx_align_center ltx_border_t">16.0</td>
<td id="S6.T1.1.7.9" class="ltx_td ltx_align_center ltx_border_t">20.5</td>
<td id="S6.T1.1.7.10" class="ltx_td ltx_align_center ltx_border_t">72.1</td>
<td id="S6.T1.1.7.11" class="ltx_td ltx_align_center ltx_border_t">49.1</td>
<td id="S6.T1.1.7.12" class="ltx_td ltx_align_center ltx_border_t">46.6</td>
<td id="S6.T1.1.7.13" class="ltx_td ltx_align_center ltx_border_t">54.0</td>
</tr>
<tr id="S6.T1.1.8" class="ltx_tr">
<td id="S6.T1.1.8.1" class="ltx_td ltx_align_left ltx_border_bb">GPT-4-Turbo</td>
<td id="S6.T1.1.8.2" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.2.1" class="ltx_text ltx_font_bold">76.5</span></td>
<td id="S6.T1.1.8.3" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.3.1" class="ltx_text ltx_font_bold">54.9</span></td>
<td id="S6.T1.1.8.4" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.4.1" class="ltx_text ltx_font_bold">63.0</span></td>
<td id="S6.T1.1.8.5" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.5.1" class="ltx_text ltx_font_bold">66.7</span></td>
<td id="S6.T1.1.8.6" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.6.1" class="ltx_text ltx_font_bold">76.2</span></td>
<td id="S6.T1.1.8.7" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.7.1" class="ltx_text ltx_font_bold">50.1</span></td>
<td id="S6.T1.1.8.8" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.8.1" class="ltx_text ltx_font_bold">20.3</span></td>
<td id="S6.T1.1.8.9" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.9.1" class="ltx_text ltx_font_bold">23.0</span></td>
<td id="S6.T1.1.8.10" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.10.1" class="ltx_text ltx_font_bold">93.8</span></td>
<td id="S6.T1.1.8.11" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.11.1" class="ltx_text ltx_font_bold">91.1</span></td>
<td id="S6.T1.1.8.12" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.12.1" class="ltx_text ltx_font_bold">59.8</span></td>
<td id="S6.T1.1.8.13" class="ltx_td ltx_align_center ltx_border_bb"><span id="S6.T1.1.8.13.1" class="ltx_text ltx_font_bold">61.6</span></td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table 1: </span>
Intrinsic evaluation results of naive LLMs’ discrimination abilities. The <span id="S6.T1.6.1" class="ltx_text ltx_font_bold">best performance</span> is in bold for open-source and closed-source LLMs. <sup id="S6.T1.7.2" class="ltx_sup"><span id="S6.T1.7.2.1" class="ltx_text ltx_font_italic">‡</span></sup>Since GSM8K’s training set does not have program of thoughts annotated for fine-tuning, we have only evaluated the models with in-context learning.
</figcaption>
</figure>
<figure id="S6.T2" class="ltx_table">
<table id="S6.T2.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S6.T2.1.1" class="ltx_tr">
<td id="S6.T2.1.1.1" class="ltx_td ltx_border_tt"></td>
<td id="S6.T2.1.1.2" class="ltx_td ltx_align_center ltx_border_tt" colspan="3"><span id="S6.T2.1.1.2.1" class="ltx_text ltx_font_bold">CodeLlama-13B</span></td>
<td id="S6.T2.1.1.3" class="ltx_td ltx_align_center ltx_border_tt" colspan="3"><span id="S6.T2.1.1.3.1" class="ltx_text ltx_font_bold">GPT-3.5-Turbo</span></td>
<td id="S6.T2.1.1.4" class="ltx_td ltx_align_center ltx_border_tt" colspan="2"><span id="S6.T2.1.1.4.1" class="ltx_text ltx_font_bold">CodeLlama-13B-FT</span></td>
</tr>
<tr id="S6.T2.1.2" class="ltx_tr">
<td id="S6.T2.1.2.1" class="ltx_td"></td>
<td id="S6.T2.1.2.2" class="ltx_td ltx_align_center ltx_border_t">Spider</td>
<td id="S6.T2.1.2.3" class="ltx_td ltx_align_center ltx_border_t">Bird</td>
<td id="S6.T2.1.2.4" class="ltx_td ltx_align_center ltx_border_t">GSM8K</td>
<td id="S6.T2.1.2.5" class="ltx_td ltx_align_center ltx_border_t">Spider</td>
<td id="S6.T2.1.2.6" class="ltx_td ltx_align_center ltx_border_t">Bird</td>
<td id="S6.T2.1.2.7" class="ltx_td ltx_align_center ltx_border_t">GSM8K</td>
<td id="S6.T2.1.2.8" class="ltx_td ltx_align_center ltx_border_t">   Spider</td>
<td id="S6.T2.1.2.9" class="ltx_td ltx_align_center ltx_border_t">   Bird</td>
</tr>
<tr id="S6.T2.1.3" class="ltx_tr">
<td id="S6.T2.1.3.1" class="ltx_td ltx_align_left ltx_border_t">Naive Discriminator</td>
<td id="S6.T2.1.3.2" class="ltx_td ltx_align_center ltx_border_t">58.2</td>
<td id="S6.T2.1.3.3" class="ltx_td ltx_align_center ltx_border_t">49.4</td>
<td id="S6.T2.1.3.4" class="ltx_td ltx_align_center ltx_border_t">62.2</td>
<td id="S6.T2.1.3.5" class="ltx_td ltx_align_center ltx_border_t">67.0</td>
<td id="S6.T2.1.3.6" class="ltx_td ltx_align_center ltx_border_t">64.3</td>
<td id="S6.T2.1.3.7" class="ltx_td ltx_align_center ltx_border_t">72.1</td>
<td id="S6.T2.1.3.8" class="ltx_td ltx_align_center ltx_border_t">69.7</td>
<td id="S6.T2.1.3.9" class="ltx_td ltx_align_center ltx_border_t">62.1</td>
</tr>
<tr id="S6.T2.1.4" class="ltx_tr">
<td id="S6.T2.1.4.1" class="ltx_td ltx_align_left ltx_border_t">+ Executability Check</td>
<td id="S6.T2.1.4.2" class="ltx_td ltx_align_center ltx_border_t">78.7</td>
<td id="S6.T2.1.4.3" class="ltx_td ltx_align_center ltx_border_t">78.8</td>
<td id="S6.T2.1.4.4" class="ltx_td ltx_align_center ltx_border_t">64.5</td>
<td id="S6.T2.1.4.5" class="ltx_td ltx_align_center ltx_border_t">84.8</td>
<td id="S6.T2.1.4.6" class="ltx_td ltx_align_center ltx_border_t">86.3</td>
<td id="S6.T2.1.4.7" class="ltx_td ltx_align_center ltx_border_t">73.2</td>
<td id="S6.T2.1.4.8" class="ltx_td ltx_align_center ltx_border_t">83.6</td>
<td id="S6.T2.1.4.9" class="ltx_td ltx_align_center ltx_border_t">82.2</td>
</tr>
<tr id="S6.T2.1.5" class="ltx_tr">
<td id="S6.T2.1.5.1" class="ltx_td ltx_align_left">++ Execution Result</td>
<td id="S6.T2.1.5.2" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.2.1" class="ltx_text ltx_font_bold">83.6</span></td>
<td id="S6.T2.1.5.3" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.3.1" class="ltx_text ltx_font_bold">79.6</span></td>
<td id="S6.T2.1.5.4" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.4.1" class="ltx_text ltx_font_bold">70.6</span></td>
<td id="S6.T2.1.5.5" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.5.1" class="ltx_text ltx_font_bold">90.0</span></td>
<td id="S6.T2.1.5.6" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.6.1" class="ltx_text ltx_font_bold">89.2</span></td>
<td id="S6.T2.1.5.7" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.7.1" class="ltx_text ltx_font_bold">76.5</span></td>
<td id="S6.T2.1.5.8" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.8.1" class="ltx_text ltx_font_bold">88.5</span></td>
<td id="S6.T2.1.5.9" class="ltx_td ltx_align_center"><span id="S6.T2.1.5.9.1" class="ltx_text ltx_font_bold">85.1</span></td>
</tr>
<tr id="S6.T2.1.6" class="ltx_tr">
<td id="S6.T2.1.6.1" class="ltx_td ltx_align_left ltx_border_bb ltx_border_t">Improvement</td>
<td id="S6.T2.1.6.2" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t"><span id="S6.T2.1.6.2.1" class="ltx_text ltx_framed ltx_framed_underline">25.4</span></td>
<td id="S6.T2.1.6.3" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t"><span id="S6.T2.1.6.3.1" class="ltx_text ltx_framed ltx_framed_underline">30.2</span></td>
<td id="S6.T2.1.6.4" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t"><span id="S6.T2.1.6.4.1" class="ltx_text ltx_framed ltx_framed_underline">8.4</span></td>
<td id="S6.T2.1.6.5" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">23.0</td>
<td id="S6.T2.1.6.6" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">24.9</td>
<td id="S6.T2.1.6.7" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">4.4</td>
<td id="S6.T2.1.6.8" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">18.8</td>
<td id="S6.T2.1.6.9" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">23.0</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table 2: </span>
Discrimination accuracy of observation-enhanced LLMs. The <span id="S6.T2.4.1" class="ltx_text ltx_font_bold">best performance</span> (in bold) is achieved using both kinds of environmental observations. We also underline the <span id="S6.T2.5.2" class="ltx_text ltx_framed ltx_framed_underline">largest improvement</span> for each dataset.
</figcaption>
</figure>
<div id="S6.p1" class="ltx_para">
<p id="S6.p1.1" class="ltx_p">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 (<span id="S6.p1.1.1" class="ltx_text ltx_font_italic">RQ2</span>).
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 href="#A1.SS2" title="A.2 Intrinsic Evaluation Data ‣ Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A.2</span></a>).</p>
</div>
<section id="S6.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">6.1 </span>Naive Discriminators</h3>

<div id="S6.SS1.p1" class="ltx_para">
<p id="S6.SS1.p1.1" class="ltx_p">As Table <a href="#S6.T1" title="Table 1 ‣ 6 LLM-Based Discriminators ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a> shows, most open-source LLMs have mediocre discrimination abilities.
After fine-tuning, CodeLlama-13B-FT could reach the same level of performance as GPT-3.5.
In comparison, closed-source LLMs exhibit stronger discrimination abilities, with GPT-4 achieving the best performance across all three datasets.
Although GPT-4 has 93.8 discrimination accuracy on GSM8K and is also better than GPT-3.5 on text-to-SQL parsing, due to its high cost, we will use GPT-3.5 in our experiments.</p>
</div>
</section>
<section id="S6.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">6.2 </span>Observation-Enhanced Discriminators</h3>

<div id="S6.SS2.p1" class="ltx_para">
<p id="S6.SS2.p1.1" class="ltx_p">To improve LLMs’ discrimination abilities, we conduct an error analysis for CodeLlama-13B on its worst-performing intrinsic evaluation set, Bird.
We sample 50 pairs of SQL queries from the Bird intrinsic evaluation set with incorrect predictions.
In 25 of the 50 pairs (50%), CodeLlama-13B assigns a higher score to non-executable SQL queries.
Consequently, no matter using which planning method, language agents could hardly perform well with such discriminators.</p>
</div>
<div id="S6.SS2.p2" class="ltx_para">
<p id="S6.SS2.p2.1" class="ltx_p">Motivated by our error analysis, we first propose to add a program executability check as a safeguard for LLMs.
If a program is non-executable, our discriminator would discard LLMs’ score and return 0.
Otherwise, it returns the original LLM score.
Besides executability check, we incorporate the execution results of predicted programs (first 5 table rows of SQL queries or answer of Python program) into the in-context examples and fine-tuning data <cite class="ltx_cite ltx_citemacro_citep">(Ni et al., <a href="#bib.bib22" title="" class="ltx_ref">2023a</a>)</cite>.
If a program is non-executable, we use <span id="S6.SS2.p2.1.1" class="ltx_text ltx_font_typewriter">ERROR</span> to represent its execution result.</p>
</div>
<div id="S6.SS2.p3" class="ltx_para">
<p id="S6.SS2.p3.1" class="ltx_p">Evaluation results (Table <a href="#S6.T2" title="Table 2 ‣ 6 LLM-Based Discriminators ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">2</span></a>) show that these two non-oracle environmental observations can effectively improve LLMs’ discrimination accuracy.
Enhanced with environmental observations, CodeLlama-13B can obtain up to 25.4, 30.2, and 8.4 points absolute accuracy gain on Spider, Bird, and GSM8K, respectively.
For the other two models, we also observe significant gains compared to the naive discriminator baseline.
Such notable improvements also highlight the importance of filtering out non-executable programs, or invalid plans, during planning.</p>
</div>
</section>
</section>
<section id="S7" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">7 </span>End-to-End Evaluation</h2>

<figure id="S7.T3" class="ltx_table">
<table id="S7.T3.7" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S7.T3.7.8" class="ltx_tr">
<td id="S7.T3.7.8.1" class="ltx_td ltx_align_left ltx_border_tt" rowspan="2"><span id="S7.T3.7.8.1.1" class="ltx_text ltx_font_bold">Discriminators</span></td>
<td id="S7.T3.7.8.2" class="ltx_td ltx_align_center ltx_border_tt" colspan="3"><span id="S7.T3.7.8.2.1" class="ltx_text ltx_font_bold">Spider (Greedy Gen = 62.3)</span></td>
<td id="S7.T3.7.8.3" class="ltx_td ltx_align_center ltx_border_tt" colspan="3"><span id="S7.T3.7.8.3.1" class="ltx_text ltx_font_bold">Bird (Greedy Gen = 16.0)</span></td>
</tr>
<tr id="S7.T3.7.9" class="ltx_tr">
<td id="S7.T3.7.9.1" class="ltx_td ltx_align_center ltx_border_t">Re-ranking</td>
<td id="S7.T3.7.9.2" class="ltx_td ltx_align_center ltx_border_t">Iter. Correct.</td>
<td id="S7.T3.7.9.3" class="ltx_td ltx_align_center ltx_border_t">Tree Search</td>
<td id="S7.T3.7.9.4" class="ltx_td ltx_align_center ltx_border_t">Re-ranking</td>
<td id="S7.T3.7.9.5" class="ltx_td ltx_align_center ltx_border_t">Iter. Correct.</td>
<td id="S7.T3.7.9.6" class="ltx_td ltx_align_center ltx_border_t">Tree Search</td>
</tr>
<tr id="S7.T3.7.10" class="ltx_tr">
<td id="S7.T3.7.10.1" class="ltx_td ltx_align_left ltx_border_t">CodeLlama-13B</td>
<td id="S7.T3.7.10.2" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.7.10.2.1" class="ltx_text ltx_font_bold">57.5</span></td>
<td id="S7.T3.7.10.3" class="ltx_td ltx_align_center ltx_border_t">51.7</td>
<td id="S7.T3.7.10.4" class="ltx_td ltx_align_center ltx_border_t">55.5</td>
<td id="S7.T3.7.10.5" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.7.10.5.1" class="ltx_text ltx_font_bold">13.3</span></td>
<td id="S7.T3.7.10.6" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.7.10.6.1" class="ltx_text ltx_font_bold">13.3</span></td>
<td id="S7.T3.7.10.7" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.7.10.7.1" class="ltx_text ltx_font_bold">13.3</span></td>
</tr>
<tr id="S7.T3.7.11" class="ltx_tr">
<td id="S7.T3.7.11.1" class="ltx_td ltx_align_left">GPT-3.5-Turbo</td>
<td id="S7.T3.7.11.2" class="ltx_td ltx_align_center"><span id="S7.T3.7.11.2.1" class="ltx_text ltx_font_bold">58.3</span></td>
<td id="S7.T3.7.11.3" class="ltx_td ltx_align_center">52.7</td>
<td id="S7.T3.7.11.4" class="ltx_td ltx_align_center">56.2</td>
<td id="S7.T3.7.11.5" class="ltx_td ltx_align_center"><span id="S7.T3.7.11.5.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">18.0</span></td>
<td id="S7.T3.7.11.6" class="ltx_td ltx_align_center">17.3</td>
<td id="S7.T3.7.11.7" class="ltx_td ltx_align_center">14.0</td>
</tr>
<tr id="S7.T3.7.12" class="ltx_tr">
<td id="S7.T3.7.12.1" class="ltx_td ltx_align_left">CodeLlama-13B-FT</td>
<td id="S7.T3.7.12.2" class="ltx_td ltx_align_center"><span id="S7.T3.7.12.2.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">61.5</span></td>
<td id="S7.T3.7.12.3" class="ltx_td ltx_align_center">51.7</td>
<td id="S7.T3.7.12.4" class="ltx_td ltx_align_center">56.0</td>
<td id="S7.T3.7.12.5" class="ltx_td ltx_align_center"><span id="S7.T3.7.12.5.1" class="ltx_text ltx_font_bold">14.3</span></td>
<td id="S7.T3.7.12.6" class="ltx_td ltx_align_center">13.0</td>
<td id="S7.T3.7.12.7" class="ltx_td ltx_align_center">13.0</td>
</tr>
<tr id="S7.T3.1.1" class="ltx_tr">
<td id="S7.T3.1.1.1" class="ltx_td ltx_align_left ltx_border_t">CodeLlama-13B<sup id="S7.T3.1.1.1.1" class="ltx_sup"><span id="S7.T3.1.1.1.1.1" class="ltx_text ltx_font_italic">E</span></sup>
</td>
<td id="S7.T3.1.1.2" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.1.1.2.1" class="ltx_text ltx_font_bold">65.5</span></td>
<td id="S7.T3.1.1.3" class="ltx_td ltx_align_center ltx_border_t">62.0</td>
<td id="S7.T3.1.1.4" class="ltx_td ltx_align_center ltx_border_t">62.5</td>
<td id="S7.T3.1.1.5" class="ltx_td ltx_align_center ltx_border_t">21.0</td>
<td id="S7.T3.1.1.6" class="ltx_td ltx_align_center ltx_border_t"><span id="S7.T3.1.1.6.1" class="ltx_text ltx_font_bold">24.3</span></td>
<td id="S7.T3.1.1.7" class="ltx_td ltx_align_center ltx_border_t">22.7</td>
</tr>
<tr id="S7.T3.2.2" class="ltx_tr">
<td id="S7.T3.2.2.1" class="ltx_td ltx_align_left">GPT-3.5-Turbo<sup id="S7.T3.2.2.1.1" class="ltx_sup"><span id="S7.T3.2.2.1.1.1" class="ltx_text ltx_font_italic">E</span></sup>
</td>
<td id="S7.T3.2.2.2" class="ltx_td ltx_align_center">67.0</td>
<td id="S7.T3.2.2.3" class="ltx_td ltx_align_center"><span id="S7.T3.2.2.3.1" class="ltx_text ltx_font_bold">67.5</span></td>
<td id="S7.T3.2.2.4" class="ltx_td ltx_align_center">66.0</td>
<td id="S7.T3.2.2.5" class="ltx_td ltx_align_center">22.3</td>
<td id="S7.T3.2.2.6" class="ltx_td ltx_align_center"><span id="S7.T3.2.2.6.1" class="ltx_text ltx_font_bold">25.0</span></td>
<td id="S7.T3.2.2.7" class="ltx_td ltx_align_center">22.7</td>
</tr>
<tr id="S7.T3.3.3" class="ltx_tr">
<td id="S7.T3.3.3.1" class="ltx_td ltx_align_left">CodeLlama-13B-FT<sup id="S7.T3.3.3.1.1" class="ltx_sup"><span id="S7.T3.3.3.1.1.1" class="ltx_text ltx_font_italic">E</span></sup>
</td>
<td id="S7.T3.3.3.2" class="ltx_td ltx_align_center"><span id="S7.T3.3.3.2.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">70.3</span></td>
<td id="S7.T3.3.3.3" class="ltx_td ltx_align_center">68.0</td>
<td id="S7.T3.3.3.4" class="ltx_td ltx_align_center">67.5</td>
<td id="S7.T3.3.3.5" class="ltx_td ltx_align_center">23.7</td>
<td id="S7.T3.3.3.6" class="ltx_td ltx_align_center"><span id="S7.T3.3.3.6.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">26.3</span></td>
<td id="S7.T3.3.3.7" class="ltx_td ltx_align_center">21.7</td>
</tr>
<tr id="S7.T3.7.7" class="ltx_tr">
<td id="S7.T3.4.4.1" class="ltx_td ltx_align_left ltx_border_bb ltx_border_t">Oracle Simulation (<math id="S7.T3.4.4.1.m1.1" class="ltx_Math" alttext="\tau=1.0" display="inline"><semantics id="S7.T3.4.4.1.m1.1a"><mrow id="S7.T3.4.4.1.m1.1.1" xref="S7.T3.4.4.1.m1.1.1.cmml"><mi id="S7.T3.4.4.1.m1.1.1.2" xref="S7.T3.4.4.1.m1.1.1.2.cmml">τ</mi><mo id="S7.T3.4.4.1.m1.1.1.1" xref="S7.T3.4.4.1.m1.1.1.1.cmml">=</mo><mn id="S7.T3.4.4.1.m1.1.1.3" xref="S7.T3.4.4.1.m1.1.1.3.cmml">1.0</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.T3.4.4.1.m1.1b"><apply id="S7.T3.4.4.1.m1.1.1.cmml" xref="S7.T3.4.4.1.m1.1.1"><eq id="S7.T3.4.4.1.m1.1.1.1.cmml" xref="S7.T3.4.4.1.m1.1.1.1"></eq><ci id="S7.T3.4.4.1.m1.1.1.2.cmml" xref="S7.T3.4.4.1.m1.1.1.2">𝜏</ci><cn type="float" id="S7.T3.4.4.1.m1.1.1.3.cmml" xref="S7.T3.4.4.1.m1.1.1.3">1.0</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.T3.4.4.1.m1.1c">\tau=1.0</annotation></semantics></math>)</td>
<td id="S7.T3.7.7.5" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">71.0</td>
<td id="S7.T3.5.5.2" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">76.0<sup id="S7.T3.5.5.2.1" class="ltx_sup">∗</sup>
</td>
<td id="S7.T3.6.6.3" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">76.2<sup id="S7.T3.6.6.3.1" class="ltx_sup">∗</sup>
</td>
<td id="S7.T3.7.7.6" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">27.0</td>
<td id="S7.T3.7.7.4" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">32.7<sup id="S7.T3.7.7.4.1" class="ltx_sup">∗</sup>
</td>
<td id="S7.T3.7.7.7" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">29.3</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table 3: </span>
End-to-end execution accuracy on text-to-SQL parsing. The <span id="S7.T3.18.1" class="ltx_text ltx_font_bold">best performance</span> for each discriminator is in bold. The <span id="S7.T3.19.2" class="ltx_text ltx_framed ltx_framed_underline">overall best performance</span> for naive and enhanced discriminators on each dataset is underlined. <sup id="S7.T3.20.3" class="ltx_sup"><span id="S7.T3.20.3.1" class="ltx_text ltx_font_italic">E</span></sup>Observation-enhanced discriminators. <sup id="S7.T3.21.4" class="ltx_sup">∗</sup>Statistically significant (<math id="S7.T3.13.m3.1" class="ltx_Math" alttext="p&lt;0.05" display="inline"><semantics id="S7.T3.13.m3.1b"><mrow id="S7.T3.13.m3.1.1" xref="S7.T3.13.m3.1.1.cmml"><mi id="S7.T3.13.m3.1.1.2" xref="S7.T3.13.m3.1.1.2.cmml">p</mi><mo id="S7.T3.13.m3.1.1.1" xref="S7.T3.13.m3.1.1.1.cmml">&lt;</mo><mn id="S7.T3.13.m3.1.1.3" xref="S7.T3.13.m3.1.1.3.cmml">0.05</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.T3.13.m3.1c"><apply id="S7.T3.13.m3.1.1.cmml" xref="S7.T3.13.m3.1.1"><lt id="S7.T3.13.m3.1.1.1.cmml" xref="S7.T3.13.m3.1.1.1"></lt><ci id="S7.T3.13.m3.1.1.2.cmml" xref="S7.T3.13.m3.1.1.2">𝑝</ci><cn type="float" id="S7.T3.13.m3.1.1.3.cmml" xref="S7.T3.13.m3.1.1.3">0.05</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.T3.13.m3.1d">p&lt;0.05</annotation></semantics></math>; McNemar’s) compared to re-ranking with the same discriminator on each dataset. We only observe such improvement with the oracle discriminator.
</figcaption>
</figure>
<div id="S7.p1" class="ltx_para">
<p id="S7.p1.1" class="ltx_p">While we have evaluated their discrimination abilities with a fixed test set, to answer <span id="S7.p1.1.1" class="ltx_text ltx_font_italic">RQ2</span>, 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.</p>
</div>
<section id="S7.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">7.1 </span>Text-to-SQL Parsing</h3>

<div id="S7.SS1.p1" class="ltx_para">
<p id="S7.SS1.p1.1" class="ltx_p">As shown in Table <a href="#S7.T3" title="Table 3 ‣ 7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>, agents using naive LLM-based discriminators do not perform well on text-to-SQL parsing.
On Spider, the re-ranking agent using CodeLlama-13B-FT has the best accuracy (61.5), which is still lower than greedy generation (62.3) that requires no planning and is more efficient.
On Bird, GPT-3.5-Turbo and re-ranking show an accuracy of 18.0, which is slightly higher than greedy generation (16.0).
In addition to the mediocre performance, we find that when using naive discriminators, iterative correction and tree search consistently show worse or the same performance as re-ranking.
These results mostly agree with our findings in previous experiments that
<span id="S7.SS1.p1.1.1" class="ltx_text ltx_font_bold">(1)</span> advanced planning methods need strong discriminators, and
<span id="S7.SS1.p1.1.2" class="ltx_text ltx_font_bold">(2)</span> naive LLM-based discriminators are not accurate enough.</p>
</div>
<div id="S7.SS1.p2" class="ltx_para">
<p id="S7.SS1.p2.1" class="ltx_p">After enhancing the discriminators with two environmental observations (Section <a href="#S6.SS2" title="6.2 Observation-Enhanced Discriminators ‣ 6 LLM-Based Discriminators ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">6.2</span></a>), we effectively improve the agents’ performance without any modifications to the generator or the planning methods.
In 5 of the 6 experiments, CodeLlama-13B-FT<sup id="S7.SS1.p2.1.1" class="ltx_sup"><span id="S7.SS1.p2.1.1.1" class="ltx_text ltx_font_italic">E</span></sup> results in the best execution accuracy among all discriminators.
It also leads to the overall best performance on Spider with re-ranking (70.3) and on Bird with iterative correction (26.3), showing the effectiveness of fine-tuning LLMs for discrimination and using environmental observations.</p>
</div>
</section>
<section id="S7.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">7.2 </span>Mathematical Reasoning</h3>

<div id="S7.SS2.p1" class="ltx_para">
<p id="S7.SS2.p1.1" class="ltx_p">The most interesting result in mathematical reasoning evaluation (Table <a href="#S7.T4" title="Table 4 ‣ 7.2 Mathematical Reasoning ‣ 7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4</span></a>) is the failure of iterative correction with naive discriminators.
When prompting the generator CodeLlama-13B for 0-shot correction, it would disregard the instruction to “generate a fixed python program” (Appendix <a href="#A3" title="Appendix C Prompt Examples ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">C</span></a>), copy the program to be modified, and generate explanations and correction steps in natural language.
Such natural language steps, usually having some lexical overlap with the math problem, would increase the discrimination score of LLMs while being non-executable.
As a result, our iterative correction agent only has 10.2 answer accuracy when using CodeLlama-13B to evaluate its own generation.
While this issue also exists when using GPT-3.5-Turbo as the discriminator, it is less severe because GPT would sometimes assign a high score (<math id="S7.SS2.p1.1.m1.1" class="ltx_Math" alttext="&gt;0.99" display="inline"><semantics id="S7.SS2.p1.1.m1.1a"><mrow id="S7.SS2.p1.1.m1.1.1" xref="S7.SS2.p1.1.m1.1.1.cmml"><mi id="S7.SS2.p1.1.m1.1.1.2" xref="S7.SS2.p1.1.m1.1.1.2.cmml"></mi><mo id="S7.SS2.p1.1.m1.1.1.1" xref="S7.SS2.p1.1.m1.1.1.1.cmml">&gt;</mo><mn id="S7.SS2.p1.1.m1.1.1.3" xref="S7.SS2.p1.1.m1.1.1.3.cmml">0.99</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.SS2.p1.1.m1.1b"><apply id="S7.SS2.p1.1.m1.1.1.cmml" xref="S7.SS2.p1.1.m1.1.1"><gt id="S7.SS2.p1.1.m1.1.1.1.cmml" xref="S7.SS2.p1.1.m1.1.1.1"></gt><csymbol cd="latexml" id="S7.SS2.p1.1.m1.1.1.2.cmml" xref="S7.SS2.p1.1.m1.1.1.2">absent</csymbol><cn type="float" id="S7.SS2.p1.1.m1.1.1.3.cmml" xref="S7.SS2.p1.1.m1.1.1.3">0.99</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.SS2.p1.1.m1.1c">&gt;0.99</annotation></semantics></math>) to the initial Python program.
These scores trigger an early exit condition in iterative correction (Section <a href="#S3.SS3" title="3.3 Planning Methods ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3.3</span></a>) and stop the agent from calling the generator to add any natural language, thus avoiding the issue.
These findings echo related analysis on self-correction <cite class="ltx_cite ltx_citemacro_citep">(Stechly et al., <a href="#bib.bib30" title="" class="ltx_ref">2023</a>; Valmeekam et al., <a href="#bib.bib32" title="" class="ltx_ref">2023</a>; Huang et al., <a href="#bib.bib13" title="" class="ltx_ref">2024</a>)</cite>.</p>
</div>
<figure id="S7.T4" class="ltx_table">
<table id="S7.T4.4" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S7.T4.1.1" class="ltx_tr">
<td id="S7.T4.1.1.2" class="ltx_td ltx_align_left ltx_border_tt"><span id="S7.T4.1.1.2.1" class="ltx_text ltx_font_bold">Discriminators</span></td>
<td id="S7.T4.1.1.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_tt"><span id="S7.T4.1.1.3.1" class="ltx_text ltx_font_bold">Re-ranking</span></td>
<td id="S7.T4.1.1.4" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_tt"><span id="S7.T4.1.1.4.1" class="ltx_text ltx_font_bold">Iter. Correct.</span></td>
<td id="S7.T4.1.1.1" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_tt"><span id="S7.T4.1.1.1.1" class="ltx_text ltx_font_bold">Tree Search<sup id="S7.T4.1.1.1.1.1" class="ltx_sup"><span id="S7.T4.1.1.1.1.1.1" class="ltx_text ltx_font_medium ltx_font_italic">‡</span></sup></span></td>
</tr>
<tr id="S7.T4.4.5" class="ltx_tr">
<td id="S7.T4.4.5.1" class="ltx_td ltx_align_left ltx_border_t">CodeLlama-13B</td>
<td id="S7.T4.4.5.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">39.7</td>
<td id="S7.T4.4.5.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">10.2</td>
<td id="S7.T4.4.5.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_t"><span id="S7.T4.4.5.4.1" class="ltx_text ltx_font_bold">41.0</span></td>
</tr>
<tr id="S7.T4.4.6" class="ltx_tr">
<td id="S7.T4.4.6.1" class="ltx_td ltx_align_left">GPT-3.5-Turbo</td>
<td id="S7.T4.4.6.2" class="ltx_td ltx_nopad_l ltx_align_center">47.0</td>
<td id="S7.T4.4.6.3" class="ltx_td ltx_nopad_l ltx_align_center">37.0</td>
<td id="S7.T4.4.6.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center"><span id="S7.T4.4.6.4.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">50.0</span></td>
</tr>
<tr id="S7.T4.2.2" class="ltx_tr">
<td id="S7.T4.2.2.1" class="ltx_td ltx_align_left ltx_border_t">CodeLlama-13B<sup id="S7.T4.2.2.1.1" class="ltx_sup"><span id="S7.T4.2.2.1.1.1" class="ltx_text ltx_font_italic">E</span></sup>
</td>
<td id="S7.T4.2.2.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">42.8</td>
<td id="S7.T4.2.2.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">42.2</td>
<td id="S7.T4.2.2.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_t"><span id="S7.T4.2.2.4.1" class="ltx_text ltx_font_bold">46.0</span></td>
</tr>
<tr id="S7.T4.3.3" class="ltx_tr">
<td id="S7.T4.3.3.1" class="ltx_td ltx_align_left">GPT-3.5-Turbo<sup id="S7.T4.3.3.1.1" class="ltx_sup"><span id="S7.T4.3.3.1.1.1" class="ltx_text ltx_font_italic">E</span></sup>
</td>
<td id="S7.T4.3.3.2" class="ltx_td ltx_nopad_l ltx_align_center">47.6</td>
<td id="S7.T4.3.3.3" class="ltx_td ltx_nopad_l ltx_align_center">48.4</td>
<td id="S7.T4.3.3.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center"><span id="S7.T4.3.3.4.1" class="ltx_text ltx_font_bold ltx_framed ltx_framed_underline">51.0</span></td>
</tr>
<tr id="S7.T4.4.7" class="ltx_tr">
<td id="S7.T4.4.7.1" class="ltx_td ltx_align_left ltx_border_t">Oracle Simulation</td>
<td id="S7.T4.4.7.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_bb ltx_border_t" rowspan="2"><span id="S7.T4.4.7.2.1" class="ltx_text">64.1</span></td>
<td id="S7.T4.4.7.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_bb ltx_border_t" rowspan="2"><span id="S7.T4.4.7.3.1" class="ltx_text">66.0</span></td>
<td id="S7.T4.4.7.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_bb ltx_border_t" rowspan="2"><span id="S7.T4.4.7.4.1" class="ltx_text">73.0</span></td>
</tr>
<tr id="S7.T4.4.4" class="ltx_tr">
<td id="S7.T4.4.4.1" class="ltx_td ltx_align_left ltx_border_bb">(<math id="S7.T4.4.4.1.m1.1" class="ltx_Math" alttext="\tau=1.0" display="inline"><semantics id="S7.T4.4.4.1.m1.1a"><mrow id="S7.T4.4.4.1.m1.1.1" xref="S7.T4.4.4.1.m1.1.1.cmml"><mi id="S7.T4.4.4.1.m1.1.1.2" xref="S7.T4.4.4.1.m1.1.1.2.cmml">τ</mi><mo id="S7.T4.4.4.1.m1.1.1.1" xref="S7.T4.4.4.1.m1.1.1.1.cmml">=</mo><mn id="S7.T4.4.4.1.m1.1.1.3" xref="S7.T4.4.4.1.m1.1.1.3.cmml">1.0</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.T4.4.4.1.m1.1b"><apply id="S7.T4.4.4.1.m1.1.1.cmml" xref="S7.T4.4.4.1.m1.1.1"><eq id="S7.T4.4.4.1.m1.1.1.1.cmml" xref="S7.T4.4.4.1.m1.1.1.1"></eq><ci id="S7.T4.4.4.1.m1.1.1.2.cmml" xref="S7.T4.4.4.1.m1.1.1.2">𝜏</ci><cn type="float" id="S7.T4.4.4.1.m1.1.1.3.cmml" xref="S7.T4.4.4.1.m1.1.1.3">1.0</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.T4.4.4.1.m1.1c">\tau=1.0</annotation></semantics></math>)</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table 4: </span>
End-to-end answer accuracy on GSM8K (Greedy Gen = 39.4). Notations have the same meaning as in Table <a href="#S7.T3" title="Table 3 ‣ 7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>. McNemar’s does not find difference between methods on GSM8K. <sup id="S7.T4.8.1" class="ltx_sup"><span id="S7.T4.8.1.1" class="ltx_text ltx_font_italic">‡</span></sup>Tree search is evaluated on 100 randomly selected examples from the 500 evaluation examples due to slow inference speed (Figure <a href="#S5.F3" title="Figure 3 ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>). For McNemar’s, we compare tree search results with those of re-ranking on the same 100 examples.
</figcaption>
</figure>
<figure id="S7.T5" class="ltx_table">
<table id="S7.T5.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="S7.T5.1.1" class="ltx_tr">
<td id="S7.T5.1.1.1" class="ltx_td ltx_align_left ltx_border_tt" rowspan="2"><span id="S7.T5.1.1.1.1" class="ltx_text ltx_font_bold">Error Type</span></td>
<td id="S7.T5.1.1.2" class="ltx_td ltx_align_center ltx_border_tt" colspan="2"><span id="S7.T5.1.1.2.1" class="ltx_text ltx_font_bold">Spider</span></td>
<td id="S7.T5.1.1.3" class="ltx_td ltx_align_center ltx_border_tt" colspan="2"><span id="S7.T5.1.1.3.1" class="ltx_text ltx_font_bold">Bird</span></td>
<td id="S7.T5.1.1.4" class="ltx_td ltx_align_center ltx_border_tt" colspan="2"><span id="S7.T5.1.1.4.1" class="ltx_text ltx_font_bold">GSM8K</span></td>
</tr>
<tr id="S7.T5.1.2" class="ltx_tr">
<td id="S7.T5.1.2.1" class="ltx_td ltx_align_center ltx_border_t">Iter. Correct.</td>
<td id="S7.T5.1.2.2" class="ltx_td ltx_align_center ltx_border_t">Tree Search</td>
<td id="S7.T5.1.2.3" class="ltx_td ltx_align_center ltx_border_t">Iter. Correct.</td>
<td id="S7.T5.1.2.4" class="ltx_td ltx_align_center ltx_border_t">Tree Search</td>
<td id="S7.T5.1.2.5" class="ltx_td ltx_align_center ltx_border_t">Iter. Correct.</td>
<td id="S7.T5.1.2.6" class="ltx_td ltx_align_center ltx_border_t">Tree Search</td>
</tr>
<tr id="S7.T5.1.3" class="ltx_tr">
<td id="S7.T5.1.3.1" class="ltx_td ltx_align_left ltx_border_t">Discrimination</td>
<td id="S7.T5.1.3.2" class="ltx_td ltx_align_center ltx_border_t">29 (78.4%)</td>
<td id="S7.T5.1.3.3" class="ltx_td ltx_align_center ltx_border_t">17 (60.7%)</td>
<td id="S7.T5.1.3.4" class="ltx_td ltx_align_center ltx_border_t">9 (52.9%)</td>
<td id="S7.T5.1.3.5" class="ltx_td ltx_align_center ltx_border_t">12 (50.0%)</td>
<td id="S7.T5.1.3.6" class="ltx_td ltx_align_center ltx_border_t">30 (62.5%)</td>
<td id="S7.T5.1.3.7" class="ltx_td ltx_align_center ltx_border_t">6 (66.7%)</td>
</tr>
<tr id="S7.T5.1.4" class="ltx_tr">
<td id="S7.T5.1.4.1" class="ltx_td ltx_align_left">Exploration</td>
<td id="S7.T5.1.4.2" class="ltx_td ltx_align_center">8 (21.6%)</td>
<td id="S7.T5.1.4.3" class="ltx_td ltx_align_center">11 (39.3%)</td>
<td id="S7.T5.1.4.4" class="ltx_td ltx_align_center">8 (47.1%)</td>
<td id="S7.T5.1.4.5" class="ltx_td ltx_align_center">12 (50.0%)</td>
<td id="S7.T5.1.4.6" class="ltx_td ltx_align_center">18 (37.5%)</td>
<td id="S7.T5.1.4.7" class="ltx_td ltx_align_center">3 (33.3%)</td>
</tr>
<tr id="S7.T5.1.5" class="ltx_tr">
<td id="S7.T5.1.5.1" class="ltx_td ltx_align_left ltx_border_bb ltx_border_t">Total</td>
<td id="S7.T5.1.5.2" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">37</td>
<td id="S7.T5.1.5.3" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">28</td>
<td id="S7.T5.1.5.4" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">17</td>
<td id="S7.T5.1.5.5" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">24</td>
<td id="S7.T5.1.5.6" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">48</td>
<td id="S7.T5.1.5.7" class="ltx_td ltx_align_center ltx_border_bb ltx_border_t">9</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table 5: </span>
Error analysis of examples where re-ranking outperforms advanced planning methods. We list the actual number of error cases and their percentages in parenthesis for each dataset and planning method.
</figcaption>
</figure>
<div id="S7.SS2.p2" class="ltx_para">
<p id="S7.SS2.p2.2" class="ltx_p">With an executability check, enhanced discriminators help mitigate this issue in iterative correction, which now achieves better performance (42.2 and 48.4) than greedy generation (39.4).
Overall, the tree search agent using GPT-3.5-Turbo<sup id="S7.SS2.p2.2.1" class="ltx_sup"><span id="S7.SS2.p2.2.1.1" class="ltx_text ltx_font_italic">E</span></sup> achieves the best answer accuracy. Nevertheless, McNemar’s test finds no difference (<math id="S7.SS2.p2.2.m2.1" class="ltx_Math" alttext="p&gt;0.05" display="inline"><semantics id="S7.SS2.p2.2.m2.1a"><mrow id="S7.SS2.p2.2.m2.1.1" xref="S7.SS2.p2.2.m2.1.1.cmml"><mi id="S7.SS2.p2.2.m2.1.1.2" xref="S7.SS2.p2.2.m2.1.1.2.cmml">p</mi><mo id="S7.SS2.p2.2.m2.1.1.1" xref="S7.SS2.p2.2.m2.1.1.1.cmml">&gt;</mo><mn id="S7.SS2.p2.2.m2.1.1.3" xref="S7.SS2.p2.2.m2.1.1.3.cmml">0.05</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.SS2.p2.2.m2.1b"><apply id="S7.SS2.p2.2.m2.1.1.cmml" xref="S7.SS2.p2.2.m2.1.1"><gt id="S7.SS2.p2.2.m2.1.1.1.cmml" xref="S7.SS2.p2.2.m2.1.1.1"></gt><ci id="S7.SS2.p2.2.m2.1.1.2.cmml" xref="S7.SS2.p2.2.m2.1.1.2">𝑝</ci><cn type="float" id="S7.SS2.p2.2.m2.1.1.3.cmml" xref="S7.SS2.p2.2.m2.1.1.3">0.05</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.SS2.p2.2.m2.1c">p&gt;0.05</annotation></semantics></math>) between the performance of re-ranking (47.6) and that of iterative correction (48.4) or tree search (51.0).</p>
</div>
</section>
<section id="S7.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">7.3 </span>Analysis</h3>

<div id="S7.SS3.p1" class="ltx_para">
<p id="S7.SS3.p1.2" class="ltx_p">To better understand the end-to-end evaluation results, we conduct an in-depth analysis of examples where re-ranking returns the correct program, but iterative correction or tree search does not (Table <a href="#S7.T5" title="Table 5 ‣ 7.2 Mathematical Reasoning ‣ 7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">5</span></a>).
Specifically, we analyze cases of the strongest discriminators, CodeLlama-13B-FT<sup id="S7.SS3.p1.2.1" class="ltx_sup"><span id="S7.SS3.p1.2.1.1" class="ltx_text ltx_font_italic">E</span></sup> for text-to-SQL parsing and GPT-3.5-Turbo<sup id="S7.SS3.p1.2.2" class="ltx_sup"><span id="S7.SS3.p1.2.2.1" class="ltx_text ltx_font_italic">E</span></sup> for mathematical reasoning, and divide them into two kinds of errors.
<span id="S7.SS3.p1.2.3" class="ltx_text ltx_font_bold">(1)</span> <span id="S7.SS3.p1.2.4" class="ltx_text ltx_font_italic">Discrimination error</span>: The discriminator assigns a higher score for wrong programs than correct ones, which is not recoverable by any planning method.
<span id="S7.SS3.p1.2.5" class="ltx_text ltx_font_bold">(2)</span> <span id="S7.SS3.p1.2.6" class="ltx_text ltx_font_italic">Exploration error</span>: The planning method has not found the correct program before termination.
Our analysis suggests that:</p>
</div>
<div id="S7.SS3.p2" class="ltx_para">
<p id="S7.SS3.p2.1" class="ltx_p"><span id="S7.SS3.p2.1.1" class="ltx_text ltx_font_bold">LLM-based discriminators have not yet met the needs of advanced planning methods.</span>
Across all datasets, 50% or more discrimination errors are observed in each planning method.
On Spider, the number of such errors in iterative correction is as large as 29 out of 37 (78.4%).
In fact, among the 29 errors, iterative correction has already found the correct SQL queries for 15 (40.5% of the total 37 errors) of them.
However, not only does the discriminator fail to trigger early exits, but it also assigns a higher score for wrong SQL queries in new iterations.
Consequently, these erroneous SQL queries override the originally correct ones, leading to an overall performance drop.
The same issue is also serious in tree search.
When an incorrect partial program receives a high discrimination score, tree search will commit to it and hardly explore other possibilities, including the correct partial programs.
Such discrimination errors usually cannot be recovered by the planning methods themselves, unless they find another correct program with even higher scores.
This finding also demonstrates that determining early exits using oracle information in iterative correction may introduce a larger benefit than previously thought <cite class="ltx_cite ltx_citemacro_citep">(Huang et al., <a href="#bib.bib13" title="" class="ltx_ref">2024</a>)</cite>.</p>
</div>
<div id="S7.SS3.p3" class="ltx_para">
<p id="S7.SS3.p3.1" class="ltx_p"><span id="S7.SS3.p3.1.1" class="ltx_text ltx_font_bold">Advanced planning methods need more thorough exploration.</span>
For the remaining cases, we observe that advanced planning methods have not found a correct program before terminating, which we call exploration errors.
This kind of error circles our discussion back to the accuracy-efficiency trade-off mentioned in our simulation experiments with oracle (Section <a href="#S5.SS2" title="5.2 Results and Analysis ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">5.2</span></a>).
Indeed, we can extend the exploration of planning methods in various ways, such as loosening termination conditions, increasing the number of generation samples for each step, and adjusting some hyperparameters for more diverse program samples.
Yet, all these adjustments can slow down the planning methods and reduce the language agents’ efficiency.
Additionally, we note that these strategies may not always result in better performance, as the discriminators may give unseen wrong programs a higher score.</p>
</div>
<div id="S7.SS3.p4" class="ltx_para">
<p id="S7.SS3.p4.2" class="ltx_p">For these reasons, <span id="S7.SS3.p4.2.1" class="ltx_text ltx_font_bold">iterative correction and tree search cannot gain decent improvement</span> over re-ranking with the same LLM-based discriminator.
On text-to-SQL parsing, tree search even shows worse performance than re-ranking when using CodeLlama-13B-FT<sup id="S7.SS3.p4.2.2" class="ltx_sup"><span id="S7.SS3.p4.2.2.1" class="ltx_text ltx_font_italic">E</span></sup> (Table <a href="#S7.T3" title="Table 3 ‣ 7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3</span></a>: 67.5 vs 70.3 on Spider; 21.7 vs 23.7 on Bird).
More surprisingly, on GSM8K, advanced planning methods may not perform much better than re-ranking even with the oracle discriminator (<math id="S7.SS3.p4.2.m2.1" class="ltx_Math" alttext="p&gt;0.05" display="inline"><semantics id="S7.SS3.p4.2.m2.1a"><mrow id="S7.SS3.p4.2.m2.1.1" xref="S7.SS3.p4.2.m2.1.1.cmml"><mi id="S7.SS3.p4.2.m2.1.1.2" xref="S7.SS3.p4.2.m2.1.1.2.cmml">p</mi><mo id="S7.SS3.p4.2.m2.1.1.1" xref="S7.SS3.p4.2.m2.1.1.1.cmml">&gt;</mo><mn id="S7.SS3.p4.2.m2.1.1.3" xref="S7.SS3.p4.2.m2.1.1.3.cmml">0.05</mn></mrow><annotation-xml encoding="MathML-Content" id="S7.SS3.p4.2.m2.1b"><apply id="S7.SS3.p4.2.m2.1.1.cmml" xref="S7.SS3.p4.2.m2.1.1"><gt id="S7.SS3.p4.2.m2.1.1.1.cmml" xref="S7.SS3.p4.2.m2.1.1.1"></gt><ci id="S7.SS3.p4.2.m2.1.1.2.cmml" xref="S7.SS3.p4.2.m2.1.1.2">𝑝</ci><cn type="float" id="S7.SS3.p4.2.m2.1.1.3.cmml" xref="S7.SS3.p4.2.m2.1.1.3">0.05</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="S7.SS3.p4.2.m2.1c">p&gt;0.05</annotation></semantics></math>; McNemar’s).
Admittedly, some of the performance gains appear considerable, but McNemar’s tells us there are still decent chances of the simpler agent outperforming a more complex one (Appendix <a href="#A2" title="Appendix B McNemar’s Test for Statistical Significance ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">B</span></a>).</p>
</div>
</section>
</section>
<section id="S8" class="ltx_section">
<h2 class="ltx_title ltx_title_section">
<span class="ltx_tag ltx_tag_section">8 </span>Conclusions</h2>

<div id="S8.p1" class="ltx_para">
<p id="S8.p1.1" class="ltx_p">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 (<span id="S8.p1.1.1" class="ltx_text ltx_font_italic">answer to RQ1</span>).
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 (<span id="S8.p1.1.2" class="ltx_text ltx_font_italic">answer to RQ2</span>).
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.</p>
</div>
</section>
<section id="Sx1" class="ltx_section">
<h2 class="ltx_title ltx_title_section">Limitations</h2>

<div id="Sx1.p1" class="ltx_para ltx_noindent">
<p id="Sx1.p1.1" class="ltx_p"><span id="Sx1.p1.1.1" class="ltx_text ltx_font_bold">Experiments with Other Models.</span>
In this study, we focus on studying the generation and discrimination of instruction-tuned LLMs that have seen code data during pre-training.
This consideration is because:
<span id="Sx1.p1.1.2" class="ltx_text ltx_font_bold">(a)</span> They may have better in-context learning performance on our two tasks, text-to-SQL parsing and mathematical reasoning with program-of-thought <cite class="ltx_cite ltx_citemacro_citep">(Ni et al., <a href="#bib.bib23" title="" class="ltx_ref">2023b</a>)</cite>;
<span id="Sx1.p1.1.3" class="ltx_text ltx_font_bold">(b)</span> We want to leverage their 0-shot instruction following capabilities in iterative correction for fair comparisons with other planning methods;
<span id="Sx1.p1.1.4" class="ltx_text ltx_font_bold">(c)</span> For GSM8K problems, LLMs tend to generate natural language plans instead of programs with 2-shot prompting, and some instructions other than in-context examples help to mitigate this issue.
Future research may extend our study to other LLMs of code and conduct an ablation study of instruction-tuning’s impact on models’ discrimination accuracy.</p>
</div>
<div id="Sx1.p2" class="ltx_para ltx_noindent">
<p id="Sx1.p2.1" class="ltx_p"><span id="Sx1.p2.1.1" class="ltx_text ltx_font_bold">Experiments with Natural Language Plans.</span>
Our study focuses on the generation and discrimination of formal language plans, i.e., programs, as they can directly interact with the environment.
Although feasible for mathematical reasoning <cite class="ltx_cite ltx_citemacro_citep">(Wei et al., <a href="#bib.bib35" title="" class="ltx_ref">2022</a>)</cite>, natural language plans require another semantic parsing step to convert them into actions defined in the corresponding environment, which may introduce intermediate errors and add noise to our analysis.
Therefore, we conduct the experiments with formal language plans using LLMs trained on code data.
As a future direction, it would be interesting to extend our study to natural language plans and see how the intermediate semantic parsing step would affect the overall performance of agents for mathematical reasoning.</p>
</div>
<div id="Sx1.p3" class="ltx_para ltx_noindent">
<p id="Sx1.p3.1" class="ltx_p"><span id="Sx1.p3.1.1" class="ltx_text ltx_font_bold">Impact of Generators on Planning Methods.</span>
While our work focuses on studying the relationship between different discriminators and planning methods, we acknowledge that the generator can also actively affect different planning methods.
For example, we can transform the generator’s perplexity into a probability and multiply it by the discriminator’s score.
We exclude such uses of the generator because in our preliminary experiments, we find that incorporating its perplexity leads to mixed results.
These results make it even harder to analyze how language agents behave when using different planning methods. Thus, we exclude the generator to have a clear picture of how discriminators can affect planning methods. Nevertheless, it is worth studying the generator’s impact on planning methods in future work.</p>
</div>
</section>
<section id="Sx2" class="ltx_section">
<h2 class="ltx_title ltx_title_section">Acknowledgements</h2>

<div id="Sx2.p1" class="ltx_para">
<p id="Sx2.p1.1" class="ltx_p">We would like to thank colleagues from the OSU NLP group for their thoughtful comments.
This research was supported in part by a sponsored award from Cisco Research, NSF IIS-1815674, NSF CAREER #1942980, NSF OAC-2112606, and Ohio Supercomputer Center <cite class="ltx_cite ltx_citemacro_citep">(Center, <a href="#bib.bib3" title="" class="ltx_ref">1987</a>)</cite>.
The views and conclusions contained herein are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. government.
The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notice herein.</p>
</div>
</section>
<section id="bib" class="ltx_bibliography">
<h2 class="ltx_title ltx_title_bibliography">References</h2>

<ul class="ltx_biblist">
<li id="bib.bib1" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Bai et al. (2022)</span>
<span class="ltx_bibblock">
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, Ben Mann, and Jared Kaplan. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2204.05862" title="" class="ltx_ref ltx_href">Training a helpful and harmless assistant with reinforcement learning from human feedback</a>.

</span>
</li>
<li id="bib.bib2" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Bui et al. (2022)</span>
<span class="ltx_bibblock">
Nghi Bui, Yue Wang, and Steven C.H. Hoi. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2022.findings-emnlp.57" title="" class="ltx_ref ltx_href">Detect-localize-repair: A unified framework for learning to debug with CodeT5</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib2.1.1" class="ltx_emph ltx_font_italic">Findings of the Association for Computational Linguistics: EMNLP 2022</em>, pages 812–823, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib3" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Center (1987)</span>
<span class="ltx_bibblock">
Ohio Supercomputer Center. 1987.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://osc.edu/ark:/19495/f5s1ph73" title="" class="ltx_ref ltx_href">Ohio supercomputer center</a>.

</span>
</li>
<li id="bib.bib4" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chaffin et al. (2022)</span>
<span class="ltx_bibblock">
Antoine Chaffin, Vincent Claveau, and Ewa Kijak. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2022.naacl-main.215" title="" class="ltx_ref ltx_href">PPL-MCTS: Constrained textual generation through discriminator-guided MCTS decoding</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib4.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies</em>, pages 2953–2967, Seattle, United States. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib5" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chen et al. (2023a)</span>
<span class="ltx_bibblock">
Shijie Chen, Ziru Chen, Huan Sun, and Yu Su. 2023a.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.findings-emnlp.785" title="" class="ltx_ref ltx_href">Error detection for text-to-SQL semantic parsing</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib5.1.1" class="ltx_emph ltx_font_italic">Findings of the Association for Computational Linguistics: EMNLP 2023</em>, pages 11730–11743, Singapore. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib6" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chen et al. (2023b)</span>
<span class="ltx_bibblock">
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2023b.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=YfZ4ZPt8zd" title="" class="ltx_ref ltx_href">Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks</a>.

</span>
<span class="ltx_bibblock"><em id="bib.bib6.1.1" class="ltx_emph ltx_font_italic">Transactions on Machine Learning Research</em>.

</span>
</li>
<li id="bib.bib7" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chen et al. (2024)</span>
<span class="ltx_bibblock">
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2024.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=KuPixIqPiq" title="" class="ltx_ref ltx_href">Teaching large language models to self-debug</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib7.1.1" class="ltx_emph ltx_font_italic">The Twelfth International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib8" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Chen et al. (2023c)</span>
<span class="ltx_bibblock">
Ziru Chen, Shijie Chen, Michael White, Raymond Mooney, Ali Payani, Jayanth Srinivasa, Yu Su, and Huan Sun. 2023c.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.acl-short.117" title="" class="ltx_ref ltx_href">Text-to-SQL error correction with language models of code</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib8.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)</em>, pages 1359–1372, Toronto, Canada. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib9" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Cobbe et al. (2021)</span>
<span class="ltx_bibblock">
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2110.14168" title="" class="ltx_ref ltx_href">Training verifiers to solve math word problems</a>.

</span>
</li>
<li id="bib.bib10" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Edwards (1948)</span>
<span class="ltx_bibblock">
Allen L. Edwards. 1948.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.1007/BF02289261" title="" class="ltx_ref ltx_href">Note on the “correction for continuity” in testing the significance of the difference between correlated proportions</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib10.1.1" class="ltx_emph ltx_font_italic">Psychometrika</em>, volume 13, page 185–187.

</span>
</li>
<li id="bib.bib11" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Gao et al. (2022)</span>
<span class="ltx_bibblock">
Ge Gao, Eunsol Choi, and Yoav Artzi. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2022.acl-long.355" title="" class="ltx_ref ltx_href">Simulating bandit learning from user feedback for extractive question answering</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib11.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</em>, pages 5167–5179, Dublin, Ireland. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib12" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Gu et al. (2023)</span>
<span class="ltx_bibblock">
Yu Gu, Xiang Deng, and Yu Su. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.acl-long.270" title="" class="ltx_ref ltx_href">Don’t generate, discriminate: A proposal for grounding language models to real-world environments</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib12.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</em>, pages 4928–4949, Toronto, Canada. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib13" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Huang et al. (2024)</span>
<span class="ltx_bibblock">
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. 2024.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=IkmD3fKBPQ" title="" class="ltx_ref ltx_href">Large language models cannot self-correct reasoning yet</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib13.1.1" class="ltx_emph ltx_font_italic">The Twelfth International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib14" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Kadavath et al. (2022)</span>
<span class="ltx_bibblock">
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2207.05221" title="" class="ltx_ref ltx_href">Language models (mostly) know what they know</a>.

</span>
</li>
<li id="bib.bib15" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ke et al. (2023)</span>
<span class="ltx_bibblock">
Pei Ke, Fei Huang, Fei Mi, Yasheng Wang, Qun Liu, Xiaoyan Zhu, and Minlie Huang. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.acl-long.539" title="" class="ltx_ref ltx_href">DecompEval: Evaluating generated texts as unsupervised decomposed question answering</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib15.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</em>, pages 9676–9691, Toronto, Canada. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib16" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Li et al. (2023a)</span>
<span class="ltx_bibblock">
Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin Chang, Fei Huang, Reynold Cheng, and Yongbin Li. 2023a.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=dI4wzAE6uV" title="" class="ltx_ref ltx_href">Can LLM already serve as a database interface? a BIg bench for large-scale database grounded text-to-SQLs</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib16.1.1" class="ltx_emph ltx_font_italic">Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track</em>.

</span>
</li>
<li id="bib.bib17" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Li et al. (2023b)</span>
<span class="ltx_bibblock">
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2023b.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.acl-long.291" title="" class="ltx_ref ltx_href">Making language models better reasoners with step-aware verifier</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib17.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</em>, pages 5315–5333, Toronto, Canada. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib18" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Madaan et al. (2023)</span>
<span class="ltx_bibblock">
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=S37hOerQLB" title="" class="ltx_ref ltx_href">Self-refine: Iterative refinement with self-feedback</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib18.1.1" class="ltx_emph ltx_font_italic">Thirty-seventh Conference on Neural Information Processing Systems</em>.

</span>
</li>
<li id="bib.bib19" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Mattar and Lengyel (2022)</span>
<span class="ltx_bibblock">
Marcelo G. Mattar and Máté Lengyel. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/https://doi.org/10.1016/j.neuron.2021.12.018" title="" class="ltx_ref ltx_href">Planning in the brain</a>.

</span>
<span class="ltx_bibblock"><em id="bib.bib19.1.1" class="ltx_emph ltx_font_italic">Neuron</em>, 110(6):914–934.

</span>
</li>
<li id="bib.bib20" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">McNemar (1947)</span>
<span class="ltx_bibblock">
Quinn McNemar. 1947.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.1007/BF02295996" title="" class="ltx_ref ltx_href">Note on the sampling error of the difference between correlated proportions or percentages</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib20.1.1" class="ltx_emph ltx_font_italic">Psychometrika</em>, volume 12, page 153–157.

</span>
</li>
<li id="bib.bib21" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Newell and Simon (1956)</span>
<span class="ltx_bibblock">
A. Newell and H. Simon. 1956.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.1109/TIT.1956.1056797" title="" class="ltx_ref ltx_href">The logic theory machine–a complex information processing system</a>.

</span>
<span class="ltx_bibblock"><em id="bib.bib21.1.1" class="ltx_emph ltx_font_italic">IRE Transactions on Information Theory</em>, 2(3):61–79.

</span>
</li>
<li id="bib.bib22" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ni et al. (2023a)</span>
<span class="ltx_bibblock">
Ansong Ni, Srini Iyer, Dragomir Radev, Veselin Stoyanov, Wen-Tau Yih, Sida Wang, and Xi Victoria Lin. 2023a.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://proceedings.mlr.press/v202/ni23b.html" title="" class="ltx_ref ltx_href">LEVER: Learning to verify language-to-code generation with execution</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib22.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 40th International Conference on Machine Learning</em>, volume 202 of <em id="bib.bib22.2.2" class="ltx_emph ltx_font_italic">Proceedings of Machine Learning Research</em>, pages 26106–26128. PMLR.

</span>
</li>
<li id="bib.bib23" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Ni et al. (2023b)</span>
<span class="ltx_bibblock">
Ansong Ni, Pengcheng Yin, Yilun Zhao, Martin Riddell, Troy Feng, Rui Shen, Stephen Yin, Ye Liu, Semih Yavuz, Caiming Xiong, Shafiq Joty, Yingbo Zhou, Dragomir Radev, and Arman Cohan. 2023b.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2309.17446" title="" class="ltx_ref ltx_href">L2ceval: Evaluating language-to-code generation capabilities of large language models</a>.

</span>
</li>
<li id="bib.bib24" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">OpenAI (2022)</span>
<span class="ltx_bibblock">
OpenAI. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openai.com/blog/chatgpt" title="" class="ltx_ref ltx_href">Chatgpt</a>.

</span>
</li>
<li id="bib.bib25" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">OpenAI (2023)</span>
<span class="ltx_bibblock">
OpenAI. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2303.08774" title="" class="ltx_ref ltx_href">Gpt-4 technical report</a>.

</span>
</li>
<li id="bib.bib26" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Robertson and Zaragoza (2009)</span>
<span class="ltx_bibblock">
Stephen Robertson and Hugo Zaragoza. 2009.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.1561/1500000019" title="" class="ltx_ref ltx_href">The probabilistic relevance framework: Bm25 and beyond</a>.

</span>
<span class="ltx_bibblock"><em id="bib.bib26.1.1" class="ltx_emph ltx_font_italic">Found. Trends Inf. Retr.</em>, 3(4):333–389.

</span>
</li>
<li id="bib.bib27" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Rozière et al. (2024)</span>
<span class="ltx_bibblock">
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. 2024.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2308.12950" title="" class="ltx_ref ltx_href">Code llama: Open foundation models for code</a>.

</span>
</li>
<li id="bib.bib28" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Russell and Norvig (2010)</span>
<span class="ltx_bibblock">
Stuart Russell and Peter Norvig. 2010.

</span>
<span class="ltx_bibblock"><em id="bib.bib28.1.1" class="ltx_emph ltx_font_italic">Artificial Intelligence: A Modern Approach</em>, 3 edition.

</span>
<span class="ltx_bibblock">Prentice Hall.

</span>
</li>
<li id="bib.bib29" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Shinn et al. (2023)</span>
<span class="ltx_bibblock">
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=vAElhFcKW6" title="" class="ltx_ref ltx_href">Reflexion: language agents with verbal reinforcement learning</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib29.1.1" class="ltx_emph ltx_font_italic">Thirty-seventh Conference on Neural Information Processing Systems</em>.

</span>
</li>
<li id="bib.bib30" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Stechly et al. (2023)</span>
<span class="ltx_bibblock">
Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=PMtZjDYB68" title="" class="ltx_ref ltx_href">GPT-4 doesn’t know it’s wrong: An analysis of iterative prompting for reasoning problems</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib30.1.1" class="ltx_emph ltx_font_italic">NeurIPS 2023 Foundation Models for Decision Making Workshop</em>.

</span>
</li>
<li id="bib.bib31" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Touvron et al. (2023)</span>
<span class="ltx_bibblock">
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas
Scialom. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2307.09288" title="" class="ltx_ref ltx_href">Llama 2: Open foundation and fine-tuned chat models</a>.

</span>
</li>
<li id="bib.bib32" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Valmeekam et al. (2023)</span>
<span class="ltx_bibblock">
Karthik Valmeekam, Matthew Marquez, and Subbarao Kambhampati. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=gGQfkyb0KL" title="" class="ltx_ref ltx_href">Investigating the effectiveness of self-critiquing in LLMs solving planning tasks</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib32.1.1" class="ltx_emph ltx_font_italic">NeurIPS 2023 Foundation Models for Decision Making Workshop</em>.

</span>
</li>
<li id="bib.bib33" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Wang et al. (2023a)</span>
<span class="ltx_bibblock">
Boshi Wang, Xiang Yue, and Huan Sun. 2023a.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2023.findings-emnlp.795" title="" class="ltx_ref ltx_href">Can ChatGPT defend its belief in truth? evaluating LLM reasoning via debate</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib33.1.1" class="ltx_emph ltx_font_italic">Findings of the Association for Computational Linguistics: EMNLP 2023</em>, pages 11865–11881, Singapore. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib34" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Wang et al. (2023b)</span>
<span class="ltx_bibblock">
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023b.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=1PL1NIMMrw" title="" class="ltx_ref ltx_href">Self-consistency improves chain of thought reasoning in language models</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib34.1.1" class="ltx_emph ltx_font_italic">The Eleventh International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib35" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Wei et al. (2022)</span>
<span class="ltx_bibblock">
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://proceedings.neurips.cc/paper_files/paper/2022/file/9d5609613524ecf4f15af0f7b31abca4-Paper-Conference.pdf" title="" class="ltx_ref ltx_href">Chain-of-thought prompting elicits reasoning in large language models</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib35.1.1" class="ltx_emph ltx_font_italic">Advances in Neural Information Processing Systems</em>, volume 35, pages 24824–24837. Curran Associates, Inc.

</span>
</li>
<li id="bib.bib36" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">West et al. (2024)</span>
<span class="ltx_bibblock">
Peter West, Ximing Lu, Nouha Dziri, Faeze Brahman, Linjie Li, Jena D. Hwang, Liwei Jiang, Jillian Fisher, Abhilasha Ravichander, Khyathi Chandu, Benjamin Newman, Pang Wei Koh, Allyson Ettinger, and Yejin Choi. 2024.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=CF8H8MS5P8" title="" class="ltx_ref ltx_href">The generative AI paradox: “what it can create, it may not understand”</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib36.1.1" class="ltx_emph ltx_font_italic">The Twelfth International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib37" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Wolf et al. (2020)</span>
<span class="ltx_bibblock">
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/2020.emnlp-demos.6" title="" class="ltx_ref ltx_href">Transformers: State-of-the-art natural language processing</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib37.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations</em>, pages 38–45, Online. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib38" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Yang et al. (2023)</span>
<span class="ltx_bibblock">
John Yang, Akshara Prabhakar, Karthik R Narasimhan, and Shunyu Yao. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=fvKaLF1ns8" title="" class="ltx_ref ltx_href">Intercode: Standardizing and benchmarking interactive coding with execution feedback</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib38.1.1" class="ltx_emph ltx_font_italic">Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track</em>.

</span>
</li>
<li id="bib.bib39" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Yao et al. (2023a)</span>
<span class="ltx_bibblock">
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. 2023a.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=5Xc1ecxO1h" title="" class="ltx_ref ltx_href">Tree of thoughts: Deliberate problem solving with large language models</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib39.1.1" class="ltx_emph ltx_font_italic">Thirty-seventh Conference on Neural Information Processing Systems</em>.

</span>
</li>
<li id="bib.bib40" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Yao et al. (2023b)</span>
<span class="ltx_bibblock">
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2023b.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=WE_vluYUL-X" title="" class="ltx_ref ltx_href">React: Synergizing reasoning and acting in language models</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib40.1.1" class="ltx_emph ltx_font_italic">The Eleventh International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib41" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Yu et al. (2018)</span>
<span class="ltx_bibblock">
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://doi.org/10.18653/v1/D18-1425" title="" class="ltx_ref ltx_href">Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib41.1.1" class="ltx_emph ltx_font_italic">Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing</em>, pages 3911–3921, Brussels, Belgium. Association for Computational Linguistics.

</span>
</li>
<li id="bib.bib42" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Zhang et al. (2023)</span>
<span class="ltx_bibblock">
Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="https://openreview.net/forum?id=Lr8cOOtYbfL" title="" class="ltx_ref ltx_href">Planning with large language models for code generation</a>.

</span>
<span class="ltx_bibblock">In <em id="bib.bib42.1.1" class="ltx_emph ltx_font_italic">The Eleventh International Conference on Learning Representations</em>.

</span>
</li>
<li id="bib.bib43" class="ltx_bibitem">
<span class="ltx_tag ltx_role_refnum ltx_tag_bibitem">Zhou et al. (2023)</span>
<span class="ltx_bibblock">
Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. 2023.

</span>
<span class="ltx_bibblock"><a target="_blank" href="http://arxiv.org/abs/2310.04406" title="" class="ltx_ref ltx_href">Language agent tree search unifies reasoning acting and planning in language models</a>.

</span>
</li>
</ul>
</section>
<section id="A1" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix A </span>Implementation Details</h2>

<section id="A1.SS1" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">A.1 </span>Text-to-SQL Parsing Evaluation Sets</h3>

<div id="A1.SS1.p1" class="ltx_para">
<p id="A1.SS1.p1.1" class="ltx_p">For text-to-SQL parsing, we sub-sample the development splits of each dataset, Spider and Bird, following three steps:
<span id="A1.SS1.p1.1.1" class="ltx_text ltx_font_bold">(1)</span> categorize development set examples by difficulty levels defined in each dataset,
<span id="A1.SS1.p1.1.2" class="ltx_text ltx_font_bold">(2)</span> randomly select a database and choose one associated example, and
<span id="A1.SS1.p1.1.3" class="ltx_text ltx_font_bold">(3)</span> repeat step 2 until we have 100 samples for each difficulty level.
In this way, we ensure a uniform distribution across different difficulty levels and database.
Since there are four and three difficulty levels in Spider and Bird, respectively, our evaluation sets have 400 and 300 examples for each dataset.</p>
</div>
<div id="A1.SS1.p2" class="ltx_para">
<p id="A1.SS1.p2.1" class="ltx_p">Text-to-SQL parsing models, including LLMs, may show lower performance on our evaluation sets because of their uniformly distributed difficulty (100 examples per level).
In comparison, the original datasets have skewed distributions towards easier examples.
Spider’s development set has 248 (24.0%) examples at easy level and 446 (43.1%) examples at medium level, while the hard and extra hard examples only sum up to 32.9 % of the 1,034 examples.
In Bird, 925 out of the 1,534 (60.3%) development set examples are at simple level, 465 examples (30.3%) are at moderate level, and only 144 examples (9.4%) are at challenging level.
Our evaluation sets normalize these skewed distributions and make the macro averages of model performance less biased (Section <a href="#S4.SS1" title="4.1 Tasks and Datasets ‣ 4 Experimental Setup ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">4.1</span></a>).</p>
</div>
</section>
<section id="A1.SS2" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">A.2 </span>Intrinsic Evaluation Data</h3>

<div id="A1.SS2.p1" class="ltx_para ltx_noindent">
<p id="A1.SS2.p1.1" class="ltx_p">To evaluate LLMs’ discrimination performance, we reuse the generation results from our oracle-simulation experiments (Section <a href="#S6" title="6 LLM-Based Discriminators ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">6</span></a>).
Specifically, we use the evaluation scripts to re-label the generated programs in simulated re-ranking experiments (accuracy threshold <math id="A1.SS2.p1.1.m1.1" class="ltx_Math" alttext="\tau=1.0" display="inline"><semantics id="A1.SS2.p1.1.m1.1a"><mrow id="A1.SS2.p1.1.m1.1.1" xref="A1.SS2.p1.1.m1.1.1.cmml"><mi id="A1.SS2.p1.1.m1.1.1.2" xref="A1.SS2.p1.1.m1.1.1.2.cmml">τ</mi><mo id="A1.SS2.p1.1.m1.1.1.1" xref="A1.SS2.p1.1.m1.1.1.1.cmml">=</mo><mn id="A1.SS2.p1.1.m1.1.1.3" xref="A1.SS2.p1.1.m1.1.1.3.cmml">1.0</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS2.p1.1.m1.1b"><apply id="A1.SS2.p1.1.m1.1.1.cmml" xref="A1.SS2.p1.1.m1.1.1"><eq id="A1.SS2.p1.1.m1.1.1.1.cmml" xref="A1.SS2.p1.1.m1.1.1.1"></eq><ci id="A1.SS2.p1.1.m1.1.1.2.cmml" xref="A1.SS2.p1.1.m1.1.1.2">𝜏</ci><cn type="float" id="A1.SS2.p1.1.m1.1.1.3.cmml" xref="A1.SS2.p1.1.m1.1.1.3">1.0</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS2.p1.1.m1.1c">\tau=1.0</annotation></semantics></math>).
Then, we construct our intrinsic evaluation sets based on the relabeled programs (Table <a href="#A1.T1" title="Table A.1 ‣ A.2 Intrinsic Evaluation Data ‣ Appendix A Implementation Details ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">A.1</span></a>).
Intuitively, the number of program batches for each dataset is the same as the end-to-end evaluation examples we have, and the the number of programs is all unique programs we can get from the batches.
To pair the programs and calculate discrimination accuracy, we iterate through each batch and enumerate combinations of correct and wrong programs within the batch.
We do not include cross-batch pairs, as those do not align with our end-to-end evaluation settings.</p>
</div>
<div id="A1.SS2.p2" class="ltx_para">
<p id="A1.SS2.p2.1" class="ltx_p">For discrimination accuracy, we enumerate pairs of correct and wrong programs and ask LLMs to select the better one.
For classification F1, we let LLMs predict the correctness of each individual program.
For Hit@1 and MRR, we use LLMs to score the batches of programs in simulation experiments.</p>
</div>
<figure id="A1.T1" class="ltx_table">
<table id="A1.T1.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A1.T1.1.1" class="ltx_tr">
<td id="A1.T1.1.1.1" class="ltx_td ltx_border_tt"></td>
<td id="A1.T1.1.1.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_tt"><span id="A1.T1.1.1.2.1" class="ltx_text ltx_font_bold">Spider</span></td>
<td id="A1.T1.1.1.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_tt"><span id="A1.T1.1.1.3.1" class="ltx_text ltx_font_bold">Bird</span></td>
<td id="A1.T1.1.1.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_tt"><span id="A1.T1.1.1.4.1" class="ltx_text ltx_font_bold">GSM8K</span></td>
</tr>
<tr id="A1.T1.1.2" class="ltx_tr">
<td id="A1.T1.1.2.1" class="ltx_td ltx_align_left ltx_border_t">Number of Programs</td>
<td id="A1.T1.1.2.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">1,221</td>
<td id="A1.T1.1.2.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_t">1,291</td>
<td id="A1.T1.1.2.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_t">2,453</td>
</tr>
<tr id="A1.T1.1.3" class="ltx_tr">
<td id="A1.T1.1.3.1" class="ltx_td ltx_align_left">Number of Program Pairs</td>
<td id="A1.T1.1.3.2" class="ltx_td ltx_nopad_l ltx_align_center">409</td>
<td id="A1.T1.1.3.3" class="ltx_td ltx_nopad_l ltx_align_center">269</td>
<td id="A1.T1.1.3.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center">1,238</td>
</tr>
<tr id="A1.T1.1.4" class="ltx_tr">
<td id="A1.T1.1.4.1" class="ltx_td ltx_align_left ltx_border_bb">Number of Program Batches</td>
<td id="A1.T1.1.4.2" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_bb">400</td>
<td id="A1.T1.1.4.3" class="ltx_td ltx_nopad_l ltx_align_center ltx_border_bb">300</td>
<td id="A1.T1.1.4.4" class="ltx_td ltx_nopad_l ltx_nopad_r ltx_align_center ltx_border_bb">500</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table A.1: </span>
Statistics of our intrinsic evaluation sets.
</figcaption>
</figure>
</section>
<section id="A1.SS3" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">A.3 </span>Prompting and Training LLMs</h3>

<div id="A1.SS3.p1" class="ltx_para ltx_noindent">
<p id="A1.SS3.p1.3" class="ltx_p"><span id="A1.SS3.p1.3.1" class="ltx_text ltx_font_bold">Prompting the Generator LM.</span>
We prompt our generator LM, CodeLlama-13B-Instruct, with temperature-based sampling for different program suggestions (Section <a href="#S3.SS1" title="3.1 Generator ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3.1</span></a>).
We use the model checkpoint and generation function implemented by Hugging Face <cite class="ltx_cite ltx_citemacro_citep">(Wolf et al., <a href="#bib.bib37" title="" class="ltx_ref">2020</a>)</cite>.
We set the maximum generation length <math id="A1.SS3.p1.1.m1.1" class="ltx_Math" alttext="\mathtt{max\_length}=300" display="inline"><semantics id="A1.SS3.p1.1.m1.1a"><mrow id="A1.SS3.p1.1.m1.1.1" xref="A1.SS3.p1.1.m1.1.1.cmml"><mrow id="A1.SS3.p1.1.m1.1.1.2" xref="A1.SS3.p1.1.m1.1.1.2.cmml"><mi id="A1.SS3.p1.1.m1.1.1.2.2" xref="A1.SS3.p1.1.m1.1.1.2.2.cmml">𝚖𝚊𝚡</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.1.m1.1.1.2.1" xref="A1.SS3.p1.1.m1.1.1.2.1.cmml">​</mo><mi mathvariant="normal" id="A1.SS3.p1.1.m1.1.1.2.3" xref="A1.SS3.p1.1.m1.1.1.2.3.cmml">_</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.1.m1.1.1.2.1a" xref="A1.SS3.p1.1.m1.1.1.2.1.cmml">​</mo><mi id="A1.SS3.p1.1.m1.1.1.2.4" xref="A1.SS3.p1.1.m1.1.1.2.4.cmml">𝚕𝚎𝚗𝚐𝚝𝚑</mi></mrow><mo id="A1.SS3.p1.1.m1.1.1.1" xref="A1.SS3.p1.1.m1.1.1.1.cmml">=</mo><mn id="A1.SS3.p1.1.m1.1.1.3" xref="A1.SS3.p1.1.m1.1.1.3.cmml">300</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS3.p1.1.m1.1b"><apply id="A1.SS3.p1.1.m1.1.1.cmml" xref="A1.SS3.p1.1.m1.1.1"><eq id="A1.SS3.p1.1.m1.1.1.1.cmml" xref="A1.SS3.p1.1.m1.1.1.1"></eq><apply id="A1.SS3.p1.1.m1.1.1.2.cmml" xref="A1.SS3.p1.1.m1.1.1.2"><times id="A1.SS3.p1.1.m1.1.1.2.1.cmml" xref="A1.SS3.p1.1.m1.1.1.2.1"></times><ci id="A1.SS3.p1.1.m1.1.1.2.2.cmml" xref="A1.SS3.p1.1.m1.1.1.2.2">𝚖𝚊𝚡</ci><ci id="A1.SS3.p1.1.m1.1.1.2.3.cmml" xref="A1.SS3.p1.1.m1.1.1.2.3">_</ci><ci id="A1.SS3.p1.1.m1.1.1.2.4.cmml" xref="A1.SS3.p1.1.m1.1.1.2.4">𝚕𝚎𝚗𝚐𝚝𝚑</ci></apply><cn type="integer" id="A1.SS3.p1.1.m1.1.1.3.cmml" xref="A1.SS3.p1.1.m1.1.1.3">300</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS3.p1.1.m1.1c">\mathtt{max\_length}=300</annotation></semantics></math>, temperature <math id="A1.SS3.p1.2.m2.1" class="ltx_Math" alttext="\mathtt{temperature}=0.6" display="inline"><semantics id="A1.SS3.p1.2.m2.1a"><mrow id="A1.SS3.p1.2.m2.1.1" xref="A1.SS3.p1.2.m2.1.1.cmml"><mi id="A1.SS3.p1.2.m2.1.1.2" xref="A1.SS3.p1.2.m2.1.1.2.cmml">𝚝𝚎𝚖𝚙𝚎𝚛𝚊𝚝𝚞𝚛𝚎</mi><mo id="A1.SS3.p1.2.m2.1.1.1" xref="A1.SS3.p1.2.m2.1.1.1.cmml">=</mo><mn id="A1.SS3.p1.2.m2.1.1.3" xref="A1.SS3.p1.2.m2.1.1.3.cmml">0.6</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS3.p1.2.m2.1b"><apply id="A1.SS3.p1.2.m2.1.1.cmml" xref="A1.SS3.p1.2.m2.1.1"><eq id="A1.SS3.p1.2.m2.1.1.1.cmml" xref="A1.SS3.p1.2.m2.1.1.1"></eq><ci id="A1.SS3.p1.2.m2.1.1.2.cmml" xref="A1.SS3.p1.2.m2.1.1.2">𝚝𝚎𝚖𝚙𝚎𝚛𝚊𝚝𝚞𝚛𝚎</ci><cn type="float" id="A1.SS3.p1.2.m2.1.1.3.cmml" xref="A1.SS3.p1.2.m2.1.1.3">0.6</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS3.p1.2.m2.1c">\mathtt{temperature}=0.6</annotation></semantics></math> and number of samples <math id="A1.SS3.p1.3.m3.1" class="ltx_Math" alttext="\mathtt{num\_return\_sequences}=5" display="inline"><semantics id="A1.SS3.p1.3.m3.1a"><mrow id="A1.SS3.p1.3.m3.1.1" xref="A1.SS3.p1.3.m3.1.1.cmml"><mrow id="A1.SS3.p1.3.m3.1.1.2" xref="A1.SS3.p1.3.m3.1.1.2.cmml"><mi id="A1.SS3.p1.3.m3.1.1.2.2" xref="A1.SS3.p1.3.m3.1.1.2.2.cmml">𝚗𝚞𝚖</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.3.m3.1.1.2.1" xref="A1.SS3.p1.3.m3.1.1.2.1.cmml">​</mo><mi mathvariant="normal" id="A1.SS3.p1.3.m3.1.1.2.3" xref="A1.SS3.p1.3.m3.1.1.2.3.cmml">_</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.3.m3.1.1.2.1a" xref="A1.SS3.p1.3.m3.1.1.2.1.cmml">​</mo><mi id="A1.SS3.p1.3.m3.1.1.2.4" xref="A1.SS3.p1.3.m3.1.1.2.4.cmml">𝚛𝚎𝚝𝚞𝚛𝚗</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.3.m3.1.1.2.1b" xref="A1.SS3.p1.3.m3.1.1.2.1.cmml">​</mo><mi mathvariant="normal" id="A1.SS3.p1.3.m3.1.1.2.5" xref="A1.SS3.p1.3.m3.1.1.2.5.cmml">_</mi><mo lspace="0em" rspace="0em" id="A1.SS3.p1.3.m3.1.1.2.1c" xref="A1.SS3.p1.3.m3.1.1.2.1.cmml">​</mo><mi id="A1.SS3.p1.3.m3.1.1.2.6" xref="A1.SS3.p1.3.m3.1.1.2.6.cmml">𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎𝚜</mi></mrow><mo id="A1.SS3.p1.3.m3.1.1.1" xref="A1.SS3.p1.3.m3.1.1.1.cmml">=</mo><mn id="A1.SS3.p1.3.m3.1.1.3" xref="A1.SS3.p1.3.m3.1.1.3.cmml">5</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS3.p1.3.m3.1b"><apply id="A1.SS3.p1.3.m3.1.1.cmml" xref="A1.SS3.p1.3.m3.1.1"><eq id="A1.SS3.p1.3.m3.1.1.1.cmml" xref="A1.SS3.p1.3.m3.1.1.1"></eq><apply id="A1.SS3.p1.3.m3.1.1.2.cmml" xref="A1.SS3.p1.3.m3.1.1.2"><times id="A1.SS3.p1.3.m3.1.1.2.1.cmml" xref="A1.SS3.p1.3.m3.1.1.2.1"></times><ci id="A1.SS3.p1.3.m3.1.1.2.2.cmml" xref="A1.SS3.p1.3.m3.1.1.2.2">𝚗𝚞𝚖</ci><ci id="A1.SS3.p1.3.m3.1.1.2.3.cmml" xref="A1.SS3.p1.3.m3.1.1.2.3">_</ci><ci id="A1.SS3.p1.3.m3.1.1.2.4.cmml" xref="A1.SS3.p1.3.m3.1.1.2.4">𝚛𝚎𝚝𝚞𝚛𝚗</ci><ci id="A1.SS3.p1.3.m3.1.1.2.5.cmml" xref="A1.SS3.p1.3.m3.1.1.2.5">_</ci><ci id="A1.SS3.p1.3.m3.1.1.2.6.cmml" xref="A1.SS3.p1.3.m3.1.1.2.6">𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎𝚜</ci></apply><cn type="integer" id="A1.SS3.p1.3.m3.1.1.3.cmml" xref="A1.SS3.p1.3.m3.1.1.3">5</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS3.p1.3.m3.1c">\mathtt{num\_return\_sequences}=5</annotation></semantics></math>.</p>
</div>
<div id="A1.SS3.p2" class="ltx_para ltx_noindent">
<p id="A1.SS3.p2.1" class="ltx_p"><span id="A1.SS3.p2.1.1" class="ltx_text ltx_font_bold">Data for Discriminator LMs.</span>
For text-to-SQL parsing, we perform 2-fold cross-validation on the training sets to synthesize incorrect SQL queries for each example <cite class="ltx_cite ltx_citemacro_citep">(Chen et al., <a href="#bib.bib5" title="" class="ltx_ref">2023a</a>)</cite>.
We prompt the LM using one pair of correct and wrong SQL queries (labeled with “Yes” and “No”), also retrieved by BM25 (Section <a href="#S3.SS2" title="3.2 Discriminator ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3.2</span></a>).
Alternatively, we fine-tune the LM on the entire training set with ground-truth and synthesized SQL queries to generate “Yes” or “No.”
For mathematical reasoning, we annotate two incorrect python programs for the two examples used in generator.
Similar to text-to-SQL parsing, we use the two program pairs to prompt LMs for binary question answering.
Since the training set of GSM8K is not annotated with program of thoughts, we are not able to fine-tune LMs on this dataset.</p>
</div>
<div id="A1.SS3.p3" class="ltx_para ltx_noindent">
<p id="A1.SS3.p3.1" class="ltx_p"><span id="A1.SS3.p3.1.1" class="ltx_text ltx_font_bold">Prompting Discriminator LMs.</span>
For CodeLlama-7B-Instruct and CodeLlama-13B-Instruct (Section <a href="#S3.SS2" title="3.2 Discriminator ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3.2</span></a>), we simply feed the input prompt to the models to get the last logit’s values, which give us the token-level probability after applying the softmax function.</p>
</div>
<div id="A1.SS3.p4" class="ltx_para">
<p id="A1.SS3.p4.2" class="ltx_p">For GPT-3.5-Turbo and GPT-4-Turbo, we access them through the API of <cite class="ltx_cite ltx_citemacro_citep">(OpenAI, <a href="#bib.bib24" title="" class="ltx_ref">2022</a>, <a href="#bib.bib25" title="" class="ltx_ref">2023</a>)</cite>.
The specific model versions are <span id="A1.SS3.p4.2.1" class="ltx_text ltx_font_typewriter">gpt-3.5-turbo-1106</span> and <span id="A1.SS3.p4.2.2" class="ltx_text ltx_font_typewriter">gpt-4-1106-preview</span>, respectively.
We prompt the LLMs to generate one token and leverage the <span id="A1.SS3.p4.2.3" class="ltx_text ltx_font_typewriter">top_logprobs</span> request to check the top-5 tokens and their probabilities<span id="footnote3" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">3</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">3</sup><span class="ltx_tag ltx_tag_note">3</span><a target="_blank" href="https://platform.openai.com/docs/api-reference/chat/create#chat-create-top_logprobs" title="" class="ltx_ref ltx_url ltx_font_typewriter">https://platform.openai.com/docs/api-reference/chat/create#chat-create-top_logprobs</a></span></span></span>.
If “Yes” appears as one of the top-5 tokens, we take its probability <math id="A1.SS3.p4.1.m1.1" class="ltx_Math" alttext="p" display="inline"><semantics id="A1.SS3.p4.1.m1.1a"><mi id="A1.SS3.p4.1.m1.1.1" xref="A1.SS3.p4.1.m1.1.1.cmml">p</mi><annotation-xml encoding="MathML-Content" id="A1.SS3.p4.1.m1.1b"><ci id="A1.SS3.p4.1.m1.1.1.cmml" xref="A1.SS3.p4.1.m1.1.1">𝑝</ci></annotation-xml><annotation encoding="application/x-tex" id="A1.SS3.p4.1.m1.1c">p</annotation></semantics></math> without any modifications.
If “Yes” is missing and “No” appears as one of the top-5 tokens, we inverse its probability <math id="A1.SS3.p4.2.m2.1" class="ltx_Math" alttext="1-p" display="inline"><semantics id="A1.SS3.p4.2.m2.1a"><mrow id="A1.SS3.p4.2.m2.1.1" xref="A1.SS3.p4.2.m2.1.1.cmml"><mn id="A1.SS3.p4.2.m2.1.1.2" xref="A1.SS3.p4.2.m2.1.1.2.cmml">1</mn><mo id="A1.SS3.p4.2.m2.1.1.1" xref="A1.SS3.p4.2.m2.1.1.1.cmml">−</mo><mi id="A1.SS3.p4.2.m2.1.1.3" xref="A1.SS3.p4.2.m2.1.1.3.cmml">p</mi></mrow><annotation-xml encoding="MathML-Content" id="A1.SS3.p4.2.m2.1b"><apply id="A1.SS3.p4.2.m2.1.1.cmml" xref="A1.SS3.p4.2.m2.1.1"><minus id="A1.SS3.p4.2.m2.1.1.1.cmml" xref="A1.SS3.p4.2.m2.1.1.1"></minus><cn type="integer" id="A1.SS3.p4.2.m2.1.1.2.cmml" xref="A1.SS3.p4.2.m2.1.1.2">1</cn><ci id="A1.SS3.p4.2.m2.1.1.3.cmml" xref="A1.SS3.p4.2.m2.1.1.3">𝑝</ci></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS3.p4.2.m2.1c">1-p</annotation></semantics></math> as the score.
Otherwise, our implementation returns 0 if both tokens are missing, though this case should be rare or even does not happen in our experiments.</p>
</div>
<div id="A1.SS3.p5" class="ltx_para ltx_noindent">
<p id="A1.SS3.p5.1" class="ltx_p"><span id="A1.SS3.p5.1.1" class="ltx_text ltx_font_bold">Training Discriminator LMs.</span>
To get CodeLlama-7B-Instruct-FT and CodeLlama-13B-Instruct-FT (Section <a href="#S3.SS2" title="3.2 Discriminator ‣ 3 Our Framework ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">3.2</span></a>), we again use the checkpoints and trainer implemented by Hugging Face.
We fine-tune the models to generate the next token (“Yes” or “No”) base on the input prompts using the following hyperparameters:</p>
<ul id="A1.I1" class="ltx_itemize">
<li id="A1.I1.i1" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_item">•</span> 
<div id="A1.I1.i1.p1" class="ltx_para">
<p id="A1.I1.i1.p1.1" class="ltx_p">Number of epochs: 1</p>
</div>
</li>
<li id="A1.I1.i2" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_item">•</span> 
<div id="A1.I1.i2.p1" class="ltx_para">
<p id="A1.I1.i2.p1.1" class="ltx_p">Batch size: 128</p>
</div>
</li>
<li id="A1.I1.i3" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_item">•</span> 
<div id="A1.I1.i3.p1" class="ltx_para">
<p id="A1.I1.i3.p1.1" class="ltx_p">Learning rate: 1e-5</p>
</div>
</li>
<li id="A1.I1.i4" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_item">•</span> 
<div id="A1.I1.i4.p1" class="ltx_para">
<p id="A1.I1.i4.p1.1" class="ltx_p">Warmup ratio: 3%</p>
</div>
</li>
<li id="A1.I1.i5" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_item">•</span> 
<div id="A1.I1.i5.p1" class="ltx_para">
<p id="A1.I1.i5.p1.1" class="ltx_p">Scheduler: cosine</p>
</div>
</li>
</ul>
<p id="A1.SS3.p5.2" class="ltx_p">The inference procedure of fine-tuned models is the same as how we prompt the original LLMs, but without using any in-context example.</p>
</div>
<div id="A1.SS3.p6" class="ltx_para ltx_noindent">
<p id="A1.SS3.p6.1" class="ltx_p"><span id="A1.SS3.p6.1.1" class="ltx_text ltx_font_bold">Computing Resources.</span> All of our experiments on Spider and GSM8K use up to four NVIDIA RTX A6000 GPU (48GB).
Experiments on Bird use up to four NVIDIA A100 Tensor Core GPU (80GB).</p>
</div>
</section>
<section id="A1.SS4" class="ltx_subsection">
<h3 class="ltx_title ltx_title_subsection">
<span class="ltx_tag ltx_tag_subsection">A.4 </span>Implemendation of Oracle Discriminator</h3>

<div id="A1.SS4.p1" class="ltx_para">
<p id="A1.SS4.p1.1" class="ltx_p">For text-to-SQL parsing, our oracle uses the first five rows in execution results of the predicted and gold SQL query and calculate the table cell overlap.
More specifically, the calculation is similar to span F1 in machine reading comprehension.
Our oracle function first compares each row in the execution results head-to-head under a strong assumption that the rows are ordered.
Although strict, this assumption is helpful for evaluating the correctness of SQL queries with an <span id="A1.SS4.p1.1.1" class="ltx_text ltx_font_typewriter">ORDER BY</span> clause.
Then, the function count how many table cells overlap with each other in an unordered manner.
We divide the number of overlapping cells by the total number of cells in execution results of the gold SQL query (precision) and the predicted one (recall).
Finally, we compute the harmonic mean of these two numbers to get the oracle score (F1).</p>
</div>
<div id="A1.SS4.p2" class="ltx_para">
<p id="A1.SS4.p2.2" class="ltx_p">For instance, given “– countryid: 1, 2, 4, 5 – countryname: usa, germany, japan, italy” as the gold execution result and “– countryid: 1, 4, 6 – countryname: usa, japan, japan” as the result of predicted SQL query.
We compare (1, usa), (4, japan), and (6, japan) the first, second, and third row in the gold result, respectively.
They have 2, 0, and 1 overlapping table cells, respectively.
Thus, we have our precision to be <math id="A1.SS4.p2.1.m1.1" class="ltx_Math" alttext="3/8=0.375" display="inline"><semantics id="A1.SS4.p2.1.m1.1a"><mrow id="A1.SS4.p2.1.m1.1.1" xref="A1.SS4.p2.1.m1.1.1.cmml"><mrow id="A1.SS4.p2.1.m1.1.1.2" xref="A1.SS4.p2.1.m1.1.1.2.cmml"><mn id="A1.SS4.p2.1.m1.1.1.2.2" xref="A1.SS4.p2.1.m1.1.1.2.2.cmml">3</mn><mo id="A1.SS4.p2.1.m1.1.1.2.1" xref="A1.SS4.p2.1.m1.1.1.2.1.cmml">/</mo><mn id="A1.SS4.p2.1.m1.1.1.2.3" xref="A1.SS4.p2.1.m1.1.1.2.3.cmml">8</mn></mrow><mo id="A1.SS4.p2.1.m1.1.1.1" xref="A1.SS4.p2.1.m1.1.1.1.cmml">=</mo><mn id="A1.SS4.p2.1.m1.1.1.3" xref="A1.SS4.p2.1.m1.1.1.3.cmml">0.375</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS4.p2.1.m1.1b"><apply id="A1.SS4.p2.1.m1.1.1.cmml" xref="A1.SS4.p2.1.m1.1.1"><eq id="A1.SS4.p2.1.m1.1.1.1.cmml" xref="A1.SS4.p2.1.m1.1.1.1"></eq><apply id="A1.SS4.p2.1.m1.1.1.2.cmml" xref="A1.SS4.p2.1.m1.1.1.2"><divide id="A1.SS4.p2.1.m1.1.1.2.1.cmml" xref="A1.SS4.p2.1.m1.1.1.2.1"></divide><cn type="integer" id="A1.SS4.p2.1.m1.1.1.2.2.cmml" xref="A1.SS4.p2.1.m1.1.1.2.2">3</cn><cn type="integer" id="A1.SS4.p2.1.m1.1.1.2.3.cmml" xref="A1.SS4.p2.1.m1.1.1.2.3">8</cn></apply><cn type="float" id="A1.SS4.p2.1.m1.1.1.3.cmml" xref="A1.SS4.p2.1.m1.1.1.3">0.375</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS4.p2.1.m1.1c">3/8=0.375</annotation></semantics></math> and recall to be <math id="A1.SS4.p2.2.m2.1" class="ltx_Math" alttext="3/6=0.5" display="inline"><semantics id="A1.SS4.p2.2.m2.1a"><mrow id="A1.SS4.p2.2.m2.1.1" xref="A1.SS4.p2.2.m2.1.1.cmml"><mrow id="A1.SS4.p2.2.m2.1.1.2" xref="A1.SS4.p2.2.m2.1.1.2.cmml"><mn id="A1.SS4.p2.2.m2.1.1.2.2" xref="A1.SS4.p2.2.m2.1.1.2.2.cmml">3</mn><mo id="A1.SS4.p2.2.m2.1.1.2.1" xref="A1.SS4.p2.2.m2.1.1.2.1.cmml">/</mo><mn id="A1.SS4.p2.2.m2.1.1.2.3" xref="A1.SS4.p2.2.m2.1.1.2.3.cmml">6</mn></mrow><mo id="A1.SS4.p2.2.m2.1.1.1" xref="A1.SS4.p2.2.m2.1.1.1.cmml">=</mo><mn id="A1.SS4.p2.2.m2.1.1.3" xref="A1.SS4.p2.2.m2.1.1.3.cmml">0.5</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.SS4.p2.2.m2.1b"><apply id="A1.SS4.p2.2.m2.1.1.cmml" xref="A1.SS4.p2.2.m2.1.1"><eq id="A1.SS4.p2.2.m2.1.1.1.cmml" xref="A1.SS4.p2.2.m2.1.1.1"></eq><apply id="A1.SS4.p2.2.m2.1.1.2.cmml" xref="A1.SS4.p2.2.m2.1.1.2"><divide id="A1.SS4.p2.2.m2.1.1.2.1.cmml" xref="A1.SS4.p2.2.m2.1.1.2.1"></divide><cn type="integer" id="A1.SS4.p2.2.m2.1.1.2.2.cmml" xref="A1.SS4.p2.2.m2.1.1.2.2">3</cn><cn type="integer" id="A1.SS4.p2.2.m2.1.1.2.3.cmml" xref="A1.SS4.p2.2.m2.1.1.2.3">6</cn></apply><cn type="float" id="A1.SS4.p2.2.m2.1.1.3.cmml" xref="A1.SS4.p2.2.m2.1.1.3">0.5</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.SS4.p2.2.m2.1c">3/6=0.5</annotation></semantics></math>.
The oracle’s score would be:</p>
<table id="A1.Ex1" class="ltx_equation ltx_eqn_table">

<tbody><tr class="ltx_equation ltx_eqn_row ltx_align_baseline">
<td class="ltx_eqn_cell ltx_eqn_center_padleft"></td>
<td class="ltx_eqn_cell ltx_align_center"><math id="A1.Ex1.m1.1" class="ltx_Math" alttext="\frac{2\cdot 0.375\cdot 0.5}{0.375+0.5}=0.43" display="block"><semantics id="A1.Ex1.m1.1a"><mrow id="A1.Ex1.m1.1.1" xref="A1.Ex1.m1.1.1.cmml"><mfrac id="A1.Ex1.m1.1.1.2" xref="A1.Ex1.m1.1.1.2.cmml"><mrow id="A1.Ex1.m1.1.1.2.2" xref="A1.Ex1.m1.1.1.2.2.cmml"><mn id="A1.Ex1.m1.1.1.2.2.2" xref="A1.Ex1.m1.1.1.2.2.2.cmml">2</mn><mo lspace="0.222em" rspace="0.222em" id="A1.Ex1.m1.1.1.2.2.1" xref="A1.Ex1.m1.1.1.2.2.1.cmml">⋅</mo><mn id="A1.Ex1.m1.1.1.2.2.3" xref="A1.Ex1.m1.1.1.2.2.3.cmml">0.375</mn><mo lspace="0.222em" rspace="0.222em" id="A1.Ex1.m1.1.1.2.2.1a" xref="A1.Ex1.m1.1.1.2.2.1.cmml">⋅</mo><mn id="A1.Ex1.m1.1.1.2.2.4" xref="A1.Ex1.m1.1.1.2.2.4.cmml">0.5</mn></mrow><mrow id="A1.Ex1.m1.1.1.2.3" xref="A1.Ex1.m1.1.1.2.3.cmml"><mn id="A1.Ex1.m1.1.1.2.3.2" xref="A1.Ex1.m1.1.1.2.3.2.cmml">0.375</mn><mo id="A1.Ex1.m1.1.1.2.3.1" xref="A1.Ex1.m1.1.1.2.3.1.cmml">+</mo><mn id="A1.Ex1.m1.1.1.2.3.3" xref="A1.Ex1.m1.1.1.2.3.3.cmml">0.5</mn></mrow></mfrac><mo id="A1.Ex1.m1.1.1.1" xref="A1.Ex1.m1.1.1.1.cmml">=</mo><mn id="A1.Ex1.m1.1.1.3" xref="A1.Ex1.m1.1.1.3.cmml">0.43</mn></mrow><annotation-xml encoding="MathML-Content" id="A1.Ex1.m1.1b"><apply id="A1.Ex1.m1.1.1.cmml" xref="A1.Ex1.m1.1.1"><eq id="A1.Ex1.m1.1.1.1.cmml" xref="A1.Ex1.m1.1.1.1"></eq><apply id="A1.Ex1.m1.1.1.2.cmml" xref="A1.Ex1.m1.1.1.2"><divide id="A1.Ex1.m1.1.1.2.1.cmml" xref="A1.Ex1.m1.1.1.2"></divide><apply id="A1.Ex1.m1.1.1.2.2.cmml" xref="A1.Ex1.m1.1.1.2.2"><ci id="A1.Ex1.m1.1.1.2.2.1.cmml" xref="A1.Ex1.m1.1.1.2.2.1">⋅</ci><cn type="integer" id="A1.Ex1.m1.1.1.2.2.2.cmml" xref="A1.Ex1.m1.1.1.2.2.2">2</cn><cn type="float" id="A1.Ex1.m1.1.1.2.2.3.cmml" xref="A1.Ex1.m1.1.1.2.2.3">0.375</cn><cn type="float" id="A1.Ex1.m1.1.1.2.2.4.cmml" xref="A1.Ex1.m1.1.1.2.2.4">0.5</cn></apply><apply id="A1.Ex1.m1.1.1.2.3.cmml" xref="A1.Ex1.m1.1.1.2.3"><plus id="A1.Ex1.m1.1.1.2.3.1.cmml" xref="A1.Ex1.m1.1.1.2.3.1"></plus><cn type="float" id="A1.Ex1.m1.1.1.2.3.2.cmml" xref="A1.Ex1.m1.1.1.2.3.2">0.375</cn><cn type="float" id="A1.Ex1.m1.1.1.2.3.3.cmml" xref="A1.Ex1.m1.1.1.2.3.3">0.5</cn></apply></apply><cn type="float" id="A1.Ex1.m1.1.1.3.cmml" xref="A1.Ex1.m1.1.1.3">0.43</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A1.Ex1.m1.1c">\frac{2\cdot 0.375\cdot 0.5}{0.375+0.5}=0.43</annotation></semantics></math></td>
<td class="ltx_eqn_cell ltx_eqn_center_padright"></td>
</tr></tbody>
</table>
</div>
<div id="A1.SS4.p3" class="ltx_para ltx_noindent">
<p id="A1.SS4.p3.1" class="ltx_p">For mathematical reasoning, our oracle directly checks if the predicted answer equals to the ground-truth.
If the answer is <span id="A1.SS4.p3.1.1" class="ltx_text ltx_font_typewriter">None</span> (non-executable program) or does not equal to the ground-truth, it returns 0.
Otherwise, it returns 1.</p>
</div>
</section>
</section>
<section id="A2" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix B </span>McNemar’s Test for Statistical Significance</h2>

<div id="A2.p1" class="ltx_para ltx_noindent">
<p id="A2.p1.1" class="ltx_p">We measure the statistical significance of performance gains using the exact McNemar’s Test<span id="footnote4" class="ltx_note ltx_role_footnote"><sup class="ltx_note_mark">4</sup><span class="ltx_note_outer"><span class="ltx_note_content"><sup class="ltx_note_mark">4</sup><span class="ltx_tag ltx_tag_note">4</span><a target="_blank" href="https://www.statsmodels.org/dev/generated/statsmodels.stats.contingency_tables.mcnemar.html" title="" class="ltx_ref ltx_url ltx_font_typewriter">https://www.statsmodels.org/dev/generated/statsmodels.stats.contingency_tables.mcnemar.html</a></span></span></span> <cite class="ltx_cite ltx_citemacro_citep">(McNemar, <a href="#bib.bib20" title="" class="ltx_ref">1947</a>)</cite>.
We choose the test’s exact binomial version because our sample sizes are relatively small <cite class="ltx_cite ltx_citemacro_citep">(Edwards, <a href="#bib.bib10" title="" class="ltx_ref">1948</a>)</cite>, and the first two significant digits of <math id="A2.p1.1.m1.1" class="ltx_Math" alttext="p" display="inline"><semantics id="A2.p1.1.m1.1a"><mi id="A2.p1.1.m1.1.1" xref="A2.p1.1.m1.1.1.cmml">p</mi><annotation-xml encoding="MathML-Content" id="A2.p1.1.m1.1b"><ci id="A2.p1.1.m1.1.1.cmml" xref="A2.p1.1.m1.1.1">𝑝</ci></annotation-xml><annotation encoding="application/x-tex" id="A2.p1.1.m1.1c">p</annotation></semantics></math>-values are the same for this binomial version and the original chi-square version in our tests.
Intuitively, this test measures how likely the weaker method can still outperform the stronger one.</p>
</div>
<div id="A2.p2" class="ltx_para">
<p id="A2.p2.3" class="ltx_p">For example, we consider the comparison between tree search and iterative correction on Bird when using CodeLlama-13B-FT<sup id="A2.p2.3.1" class="ltx_sup"><span id="A2.p2.3.1.1" class="ltx_text ltx_font_italic">E</span></sup> as the discriminator (Section <a href="#S5.SS2" title="5.2 Results and Analysis ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">5.2</span></a>).
By computing a <math id="A2.p2.2.m2.1" class="ltx_Math" alttext="2\times 2" display="inline"><semantics id="A2.p2.2.m2.1a"><mrow id="A2.p2.2.m2.1.1" xref="A2.p2.2.m2.1.1.cmml"><mn id="A2.p2.2.m2.1.1.2" xref="A2.p2.2.m2.1.1.2.cmml">2</mn><mo lspace="0.222em" rspace="0.222em" id="A2.p2.2.m2.1.1.1" xref="A2.p2.2.m2.1.1.1.cmml">×</mo><mn id="A2.p2.2.m2.1.1.3" xref="A2.p2.2.m2.1.1.3.cmml">2</mn></mrow><annotation-xml encoding="MathML-Content" id="A2.p2.2.m2.1b"><apply id="A2.p2.2.m2.1.1.cmml" xref="A2.p2.2.m2.1.1"><times id="A2.p2.2.m2.1.1.1.cmml" xref="A2.p2.2.m2.1.1.1"></times><cn type="integer" id="A2.p2.2.m2.1.1.2.cmml" xref="A2.p2.2.m2.1.1.2">2</cn><cn type="integer" id="A2.p2.2.m2.1.1.3.cmml" xref="A2.p2.2.m2.1.1.3">2</cn></apply></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.2.m2.1c">2\times 2</annotation></semantics></math> contingency table (Table <a href="#A2.T1" title="Table B.1 ‣ Appendix B McNemar’s Test for Statistical Significance ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">B.1</span></a>), McNemar’s Test focuses on the 40 examples where only one of the two method have predicted correctly.
Specifically, there are 25 examples that iterative correction finds the correct answer, but tree search does not, which is the source of performance gain.
Also, there are 15 examples that iterative correction fails, but tree search succeeds.
According to McNemar’s Test, these 15 (37.5% of the total 40) examples result in a <math id="A2.p2.3.m3.1" class="ltx_Math" alttext="p" display="inline"><semantics id="A2.p2.3.m3.1a"><mi id="A2.p2.3.m3.1.1" xref="A2.p2.3.m3.1.1.cmml">p</mi><annotation-xml encoding="MathML-Content" id="A2.p2.3.m3.1b"><ci id="A2.p2.3.m3.1.1.cmml" xref="A2.p2.3.m3.1.1">𝑝</ci></annotation-xml><annotation encoding="application/x-tex" id="A2.p2.3.m3.1c">p</annotation></semantics></math>-value of 0.15, meaning there is still some chance for tree search to outperform iterative correction.</p>
</div>
<div id="A2.p3" class="ltx_para">
<p id="A2.p3.1" class="ltx_p">In contrast, suppose there are only 10 examples that iterative correction finds the correct answer, but tree search does not.
Meanwhile, there are no examples that iterative correction fails, but tree search succeeds.
Then, we can still observe the same number of accuracy gain, but it is now statistically different because it is almost impossible for tree search to outperform iterative correction (0 out of 10).
The same rationale also applies to the results of other tests in Section <a href="#S7" title="7 End-to-End Evaluation ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">7</span></a>.</p>
</div>
<figure id="A2.T1" class="ltx_table">
<table id="A2.T1.3" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A2.T1.3.1" class="ltx_tr">
<td id="A2.T1.3.1.1" class="ltx_td ltx_border_tt"></td>
<td id="A2.T1.3.1.2" class="ltx_td ltx_align_center ltx_border_tt">IC Correct</td>
<td id="A2.T1.3.1.3" class="ltx_td ltx_align_center ltx_border_tt">IC Wrong</td>
</tr>
<tr id="A2.T1.3.2" class="ltx_tr">
<td id="A2.T1.3.2.1" class="ltx_td ltx_align_left ltx_border_t">TS Correct</td>
<td id="A2.T1.3.2.2" class="ltx_td ltx_align_center ltx_border_t">73</td>
<td id="A2.T1.3.2.3" class="ltx_td ltx_align_center ltx_border_t">15</td>
</tr>
<tr id="A2.T1.3.3" class="ltx_tr">
<td id="A2.T1.3.3.1" class="ltx_td ltx_align_left ltx_border_bb">TS Wrong</td>
<td id="A2.T1.3.3.2" class="ltx_td ltx_align_center ltx_border_bb">25</td>
<td id="A2.T1.3.3.3" class="ltx_td ltx_align_center ltx_border_bb">187</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table B.1: </span>
Contingency table for tree search (TS) and iterative correction (IC) on Bird, using CodeLlama-13B-FT<sup id="A2.T1.5.1" class="ltx_sup"><span id="A2.T1.5.1.1" class="ltx_text ltx_font_italic">E</span></sup> as the discriminator (Section <a href="#S5.SS2" title="5.2 Results and Analysis ‣ 5 Simulation Experiments with Oracle ‣ When is Tree Search Useful for LLM Planning? It Depends on the Discriminator" class="ltx_ref"><span class="ltx_text ltx_ref_tag">5.2</span></a>).
</figcaption>
</figure>
<div class="ltx_pagination ltx_role_newpage"></div>
</section>
<section id="A3" class="ltx_appendix">
<h2 class="ltx_title ltx_title_appendix">
<span class="ltx_tag ltx_tag_appendix">Appendix C </span>Prompt Examples</h2>

<figure id="A3.T1" class="ltx_table">
<table id="A3.T1.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T1.1.1" class="ltx_tr">
<td id="A3.T1.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T1.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T1.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T1.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">Given database schema and a question in natural language, generate the corresponding SQL query.
<br class="ltx_break">
<br class="ltx_break">-- Database climbing: 
<br class="ltx_break">-- Table mountain: mountain_id, name, height, prominence, range, country 
<br class="ltx_break">-- Table climber: climber_id, name, country, time, points, mountain_id 
<br class="ltx_break">-- Question: How many distinct countries are the climbers from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT COUNT(DISTINCT country) FROM climber; 
<br class="ltx_break">
<br class="ltx_break">-- Database concert_singer: 
<br class="ltx_break">-- Table stadium: stadium_id, location, name, capacity, highest, lowest, average 
<br class="ltx_break">-- Table singer: singer_id, name, country, song_name, song_release_year, age, is_male 
<br class="ltx_break">-- Table concert: concert_id, concert_name, theme, stadium_id, year 
<br class="ltx_break">-- Table singer_in_concert: concert_id, singer_id 
<br class="ltx_break">-- Question: What are all distinct countries where singers above age 20 are from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.1: </span>
An example prompt for 1-shot generation (text-to-SQL parsing).
</figcaption>
</figure>
<figure id="A3.T2" class="ltx_table">
<table id="A3.T2.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T2.1.1" class="ltx_tr">
<td id="A3.T2.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T2.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T2.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T2.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">Given database schema and a question in natural language, correct the buggy SQL query and generate a fixed SQL query.
<br class="ltx_break">
<br class="ltx_break">-- Database concert_singer: 
<br class="ltx_break">-- Table stadium: stadium_id, location, name, capacity, highest, lowest, average 
<br class="ltx_break">-- Table singer: singer_id, name, country, song_name, song_release_year, age, is_male 
<br class="ltx_break">-- Table concert: concert_id, concert_name, theme, stadium_id, year 
<br class="ltx_break">-- Table singer_in_concert: concert_id, singer_id 
<br class="ltx_break">-- Question: What are all distinct countries where singers above age 20 are from? 
<br class="ltx_break">-- Buggy SQL: 
<br class="ltx_break">SELECT DISTINCT country FROM singer WHERE age &gt; 20; 
<br class="ltx_break">-- Fixed SQL: 
<br class="ltx_break">SELECT</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.2: </span>
An example prompt for 0-shot iterative correction (text-to-SQL parsing).
</figcaption>
</figure>
<div class="ltx_pagination ltx_role_newpage"></div>
<figure id="A3.T3" class="ltx_table">
<table id="A3.T3.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T3.1.1" class="ltx_tr">
<td id="A3.T3.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T3.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T3.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T3.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">Answer the following Yes/No question: Is the SQL correct given the utterance? 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: How many different countries are all the swimmers from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT COUNT(DISTINCT nationality) FROM swimmer; 
<br class="ltx_break">-- Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: How many different countries are all the swimmers from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT DISTINCT country FROM swimmer; 
<br class="ltx_break">-- Answer: No 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: What are all distinct countries where singers above age 20 are from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT DISTINCT country FROM singer WHERE age &gt; 20; 
<br class="ltx_break">-- Answer:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.3: </span>
An example prompt for 1-shot discrimination (text-to-SQL parsing). For discrimination, each in-context example has a pair of correct and wrong programs.
</figcaption>
</figure>
<figure id="A3.T4" class="ltx_table">
<table id="A3.T4.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T4.1.1" class="ltx_tr">
<td id="A3.T4.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T4.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T4.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T4.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">Answer the following Yes/No question: Is the SQL correct given the utterance and its result? 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: How many different countries are all the swimmers from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT COUNT(DISTINCT nationality) FROM swimmer; 
<br class="ltx_break">-- Result: 
<br class="ltx_break">-- count(distinct nationality): 7 
<br class="ltx_break">-- Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: How many different countries are all the swimmers from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT DISTINCT country FROM swimmer; 
<br class="ltx_break">-- Result: 
<br class="ltx_break">ERROR 
<br class="ltx_break">-- Answer: No 
<br class="ltx_break">
<br class="ltx_break">-- Utterance: What are all distinct countries where singers above age 20 are from? 
<br class="ltx_break">-- SQL: 
<br class="ltx_break">SELECT DISTINCT country FROM singer WHERE age &gt; 20; 
<br class="ltx_break">-- Result: 
<br class="ltx_break">-- country: Netherlands, United States, France 
<br class="ltx_break">-- Answer:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.4: </span>
An example prompt for 1-shot discrimination with execution results (text-to-SQL parsing). For discrimination, each in-context example has a pair of correct and wrong programs.
</figcaption>
</figure>
<div class="ltx_pagination ltx_role_newpage"></div>
<figure id="A3.T5" class="ltx_table">
<table id="A3.T5.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T5.1.1" class="ltx_tr">
<td id="A3.T5.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T5.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T5.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T5.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">## Given questions in the comment, use python programs to produce the correct answers with the ’answer’ variable. 
<br class="ltx_break">
<br class="ltx_break">## James takes 2 Tylenol tablets that are 375 mg each, every 6 hours. How many mg does he take a day? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">mg_tylenol_per_tablet = 375 
<br class="ltx_break">mg_tylenol_taken_each_time = 2 * mg_tylenol_per_tablet 
<br class="ltx_break">hours_per_day = 24 
<br class="ltx_break">times_per_day = hours_per_day / 6 
<br class="ltx_break">mg_each_day = mg_tylenol_taken_each_time * times_per_day 
<br class="ltx_break">answer = mg_each_day 
<br class="ltx_break">
<br class="ltx_break">## There were 63 Easter eggs in the yard. Hannah found twice as many as Helen. How many Easter eggs did Hannah find? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">n_easter_eggs = 63 
<br class="ltx_break">unit_times = 2 
<br class="ltx_break">total_units = unit_times + 1 
<br class="ltx_break">n_easter_eggs_per_unit = n_easter_eggs / total_units 
<br class="ltx_break">n_easter_eggs_helen = n_easter_eggs_per_unit * 1 
<br class="ltx_break">n_easter_eggs_hannah = n_easter_eggs_per_unit * 2 
<br class="ltx_break">answer = n_easter_eggs_hannah 
<br class="ltx_break">
<br class="ltx_break">## Gloria is shoe shopping when she comes across a pair of boots that fit her shoe budget. However, she has to choose between the boots and two pairs of high heels that together cost five dollars less than the boots. If one pair of heels costs $33 and the other costs twice as much, how many dollars are the boots? 
<br class="ltx_break">## Python Program:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.5: </span>
An example prompt for 2-shot generation (mathematical reasoning).
</figcaption>
</figure>
<figure id="A3.T6" class="ltx_table">
<table id="A3.T6.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T6.1.1" class="ltx_tr">
<td id="A3.T6.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T6.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T6.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T6.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">## Given the question in the comment, correct the buggy python program and generate a fixed python program to produce the correct answer with the ’answer’ variable. 
<br class="ltx_break">
<br class="ltx_break">## Gloria is shoe shopping when she comes across a pair of boots that fit her shoe budget. However, she has to choose between the boots and two pairs of high heels that together cost five dollars less than the boots. If one pair of heels costs $33 and the other costs twice as much, how many dollars are the boots? 
<br class="ltx_break">## Buggy Python Program: 
<br class="ltx_break">price_boots = 50 
<br class="ltx_break">price_heels = 33 
<br class="ltx_break">price_heels_twice = 2 * price_heels 
<br class="ltx_break">price_heels_total = price_heels + price_heels_twice 
<br class="ltx_break">price_boots_difference = price_boots - price_heels_total 
<br class="ltx_break">answer = price_boots_difference 
<br class="ltx_break">## Fixed Python Program:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.6: </span>
An example prompt for 0-shot iterative correction (mathematical reasoning).
</figcaption>
</figure>
<div class="ltx_pagination ltx_role_newpage"></div>
<figure id="A3.T7" class="ltx_table">
<table id="A3.T7.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T7.1.1" class="ltx_tr">
<td id="A3.T7.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T7.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T7.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T7.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">## Answer the following Yes/No question: Is the python program correct given the problem in the comment? 
<br class="ltx_break">
<br class="ltx_break">## James takes 2 Tylenol tablets that are 375 mg each, every 6 hours. How many mg does he take a day? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">mg_tylenol_per_tablet = 375 
<br class="ltx_break">mg_tylenol_taken_each_time = 2 * mg_tylenol_per_tablet 
<br class="ltx_break">hours_per_day = 24 
<br class="ltx_break">times_per_day = hours_per_day / 6 
<br class="ltx_break">mg_each_day = mg_tylenol_taken_each_time * times_per_day 
<br class="ltx_break">answer = mg_each_day 
<br class="ltx_break">## Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">## James takes 2 Tylenol tablets that are 375 mg each, every 6 hours. How many mg does he take a day? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">mg_per_tablet = 375 
<br class="ltx_break">n_tablets_per_day = 2 
<br class="ltx_break">n_tablets_per_6hrs = n_tablets_per_day / 6 
<br class="ltx_break">mg_per_6hrs = mg_per_tablet * n_tablets_per_6hrs 
<br class="ltx_break">answer = mg_per_6hrs 
<br class="ltx_break">## Answer: No 
<br class="ltx_break">
<br class="ltx_break">## There were 63 Easter eggs in the yard. Hannah found twice as many as Helen. How many Easter eggs did Hannah find? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">n_easter_eggs = 63 
<br class="ltx_break">unit_times = 2 
<br class="ltx_break">total_units = unit_times + 1 
<br class="ltx_break">n_easter_eggs_per_unit = n_easter_eggs / total_units 
<br class="ltx_break">n_easter_eggs_helen = n_easter_eggs_per_unit * 1 
<br class="ltx_break">n_easter_eggs_hannah = n_easter_eggs_per_unit * 2 
<br class="ltx_break">answer = n_easter_eggs_hannah 
<br class="ltx_break">## Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">## There were 63 Easter eggs in the yard. Hannah found twice as many as Helen. How many Easter eggs did Hannah find? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">eggs_in_yard = 63 
<br class="ltx_break">eggs_found_by_hannah = 2 * eggs_in_yard 
<br class="ltx_break">eggs_found_by_helen = eggs_found_by_hannah / 2 
<br class="ltx_break">answer = eggs_found_by_hannah 
<br class="ltx_break">## Answer: No 
<br class="ltx_break">
<br class="ltx_break">## Gloria is shoe shopping when she comes across a pair of boots that fit her shoe budget. However, she has to choose between the boots and two pairs of high heels that together cost five dollars less than the boots. If one pair of heels costs $33 and the other costs twice as much, how many dollars are the boots? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">price_boots = 50 
<br class="ltx_break">price_heels = 33 
<br class="ltx_break">price_heels_twice = 2 * price_heels 
<br class="ltx_break">price_heels_total = price_heels + price_heels_twice 
<br class="ltx_break">price_boots_difference = price_boots - price_heels_total 
<br class="ltx_break">answer = price_boots_difference 
<br class="ltx_break">## Answer:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.7: </span>
An example prompt for 2-shot discrimination (mathematical reasoning). For discrimination, each in-context example has a pair of correct and wrong programs.
</figcaption>
</figure>
<div class="ltx_pagination ltx_role_newpage"></div>
<figure id="A3.T8" class="ltx_table">
<table id="A3.T8.1" class="ltx_tabular ltx_centering ltx_align_middle">
<tr id="A3.T8.1.1" class="ltx_tr">
<td id="A3.T8.1.1.1" class="ltx_td ltx_align_justify ltx_align_top ltx_border_bb ltx_border_tt">
<span id="A3.T8.1.1.1.1" class="ltx_inline-block ltx_align_top">
<span id="A3.T8.1.1.1.1.1" class="ltx_p" style="width:390.3pt;"><span id="A3.T8.1.1.1.1.1.1" class="ltx_text ltx_font_typewriter">## Answer the following Yes/No question: Is the python program correct given its result and the problem in the comment? 
<br class="ltx_break">
<br class="ltx_break">## James takes 2 Tylenol tablets that are 375 mg each, every 6 hours. How many mg does he take a day? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">mg_tylenol_per_tablet = 375 
<br class="ltx_break">mg_tylenol_taken_each_time = 2 * mg_tylenol_per_tablet 
<br class="ltx_break">hours_per_day = 24 
<br class="ltx_break">times_per_day = hours_per_day / 6 
<br class="ltx_break">mg_each_day = mg_tylenol_taken_each_time * times_per_day 
<br class="ltx_break">answer = mg_each_day 
<br class="ltx_break">## Result: 3000.0 
<br class="ltx_break">## Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">## James takes 2 Tylenol tablets that are 375 mg each, every 6 hours. How many mg does he take a day? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">mg_per_tablet = 375 
<br class="ltx_break">n_tablets_per_day = 2 
<br class="ltx_break">n_tablets_per_6hrs = n_tablets_per_day / 6 
<br class="ltx_break">mg_per_6hrs = mg_per_tablet * n_tablets_per_6hrs 
<br class="ltx_break">answer = mg_per_6hrs 
<br class="ltx_break">## Result: 125.0 
<br class="ltx_break">## Answer: No 
<br class="ltx_break">
<br class="ltx_break">## There were 63 Easter eggs in the yard. Hannah found twice as many as Helen. How many Easter eggs did Hannah find? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">n_easter_eggs = 63 
<br class="ltx_break">unit_times = 2 
<br class="ltx_break">total_units = unit_times + 1 
<br class="ltx_break">n_easter_eggs_per_unit = n_easter_eggs / total_units 
<br class="ltx_break">n_easter_eggs_helen = n_easter_eggs_per_unit * 1 
<br class="ltx_break">n_easter_eggs_hannah = n_easter_eggs_per_unit * 2 
<br class="ltx_break">answer = n_easter_eggs_hannah 
<br class="ltx_break">## Result: 42 
<br class="ltx_break">## Answer: Yes 
<br class="ltx_break">
<br class="ltx_break">## There were 63 Easter eggs in the yard. Hannah found twice as many as Helen. How many Easter eggs did Hannah find? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">eggs_in_yard = 63 
<br class="ltx_break">eggs_found_by_hannah = 2 * eggs_in_yard 
<br class="ltx_break">eggs_found_by_helen = eggs_found_by_hannah / 2 
<br class="ltx_break">answer = eggs_found_by_hannah 
<br class="ltx_break">## Result: 126 
<br class="ltx_break">## Answer: No 
<br class="ltx_break">
<br class="ltx_break">## Gloria is shoe shopping when she comes across a pair of boots that fit her shoe budget. However, she has to choose between the boots and two pairs of high heels that together cost five dollars less than the boots. If one pair of heels costs $33 and the other costs twice as much, how many dollars are the boots? 
<br class="ltx_break">## Python Program: 
<br class="ltx_break">price_boots = 50 
<br class="ltx_break">price_heels = 33 
<br class="ltx_break">price_heels_twice = 2 * price_heels 
<br class="ltx_break">price_heels_total = price_heels + price_heels_twice 
<br class="ltx_break">price_boots_difference = price_boots - price_heels_total 
<br class="ltx_break">answer = price_boots_difference 
<br class="ltx_break">## Result: -49 
<br class="ltx_break">## Answer:</span></span>
</span>
</td>
</tr>
</table>
<figcaption class="ltx_caption ltx_centering"><span class="ltx_tag ltx_tag_table">Table C.8: </span>
An example prompt for 2-shot discrimination with execution results (mathematical reasoning). For discrimination, each in-context example has a pair of correct and wrong programs.
</figcaption>
</figure>
</section>
</article>
</div>
<div class="ar5iv-footer"><a href="/html/2402.10889" class="ar5iv-nav-button ar5iv-nav-button-prev">◄</a>
    <a class="ar5iv-home-button" href="/"><img height="40" alt="ar5iv homepage" src="/assets/ar5iv.png"></a>
    <a href="/feeling_lucky" class="ar5iv-text-button">Feeling<br>lucky?</a>
    <a href="/log/2402.10890" class="ar5iv-text-button ar5iv-severity-warning">Conversion<br>report</a>
    <a class="ar5iv-text-button" target="_blank" href="https://github.com/dginev/ar5iv/issues/new?template=improve-article--arxiv-id-.md&title=Improve+article+2402.10890">Report<br>an issue</a>
    <a href="https://arxiv.org/abs/2402.10890" class="ar5iv-text-button arxiv-ui-theme">View&nbsp;original<br>on&nbsp;arXiv</a><a href="/html/2402.10891" class="ar5iv-nav-button ar5iv-nav-button-next">►</a>
</div><footer class="ltx_page_footer">
<a class="ar5iv-toggle-color-scheme" href="javascript:toggleColorScheme()" title="Toggle ar5iv color scheme"><span class="color-scheme-icon"></span></a>
<a class="ar5iv-footer-button" href="https://arxiv.org/help/license" target="_blank">Copyright</a>
<a class="ar5iv-footer-button" href="https://arxiv.org/help/policies/privacy_policy" target="_blank">Privacy Policy</a>

<div class="ltx_page_logo">Generated  on Tue Mar  5 16:00:06 2024 by <a target="_blank" href="http://dlmf.nist.gov/LaTeXML/" class="ltx_LaTeXML_logo"><span style="letter-spacing:-0.2em; margin-right:0.1em;">L<span class="ltx_font_smallcaps" style="position:relative; bottom:2.2pt;">a</span>T<span class="ltx_font_smallcaps" style="font-size:120%;position:relative; bottom:-0.2ex;">e</span></span><span style="font-size:90%; position:relative; bottom:-0.2ex;">XML</span><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAAOCAYAAAD5YeaVAAAAAXNSR0IArs4c6QAAAAZiS0dEAP8A/wD/oL2nkwAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9wKExQZLWTEaOUAAAAddEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIFRoZSBHSU1Q72QlbgAAAdpJREFUKM9tkL+L2nAARz9fPZNCKFapUn8kyI0e4iRHSR1Kb8ng0lJw6FYHFwv2LwhOpcWxTjeUunYqOmqd6hEoRDhtDWdA8ApRYsSUCDHNt5ul13vz4w0vWCgUnnEc975arX6ORqN3VqtVZbfbTQC4uEHANM3jSqXymFI6yWazP2KxWAXAL9zCUa1Wy2tXVxheKA9YNoR8Pt+aTqe4FVVVvz05O6MBhqUIBGk8Hn8HAOVy+T+XLJfLS4ZhTiRJgqIoVBRFIoric47jPnmeB1mW/9rr9ZpSSn3Lsmir1fJZlqWlUonKsvwWwD8ymc/nXwVBeLjf7xEKhdBut9Hr9WgmkyGEkJwsy5eHG5vN5g0AKIoCAEgkEkin0wQAfN9/cXPdheu6P33fBwB4ngcAcByHJpPJl+fn54mD3Gg0NrquXxeLRQAAwzAYj8cwTZPwPH9/sVg8PXweDAauqqr2cDjEer1GJBLBZDJBs9mE4zjwfZ85lAGg2+06hmGgXq+j3+/DsixYlgVN03a9Xu8jgCNCyIegIAgx13Vfd7vdu+FweG8YRkjXdWy329+dTgeSJD3ieZ7RNO0VAXAPwDEAO5VKndi2fWrb9jWl9Esul6PZbDY9Go1OZ7PZ9z/lyuD3OozU2wAAAABJRU5ErkJggg==" alt="Mascot Sammy"></a>
</div></footer>
</div>

    <script>
      var canMathML = typeof(MathMLElement) == "function";
      if (!canMathML) {
        var body = document.querySelector("body");
        body.firstElementChild.setAttribute('style', 'opacity: 0;');
        var loading = document.createElement("div");
        loading.setAttribute("id", "mathjax-loading-spinner");
        var message = document.createElement("div");
        message.setAttribute("id", "mathjax-loading-message");
        message.innerText = "Typesetting Equations...";
        body.prepend(loading);
        body.prepend(message);

        var el = document.createElement("script");
        el.src = "https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js";
        document.querySelector("head").appendChild(el);

        window.MathJax = {
          startup: {
            pageReady: () => {
              return MathJax.startup.defaultPageReady().then(() => {
                body.removeChild(loading);
                body.removeChild(message);
                body.firstElementChild.removeAttribute('style');
              }); } } };
      }
    </script>
    <script>
    // Auxiliary function, building the preview feature when
    // an inline citation is clicked
    function clicked_cite(e) {
      e.preventDefault();
      let cite = this.closest('.ltx_cite');
      let next = cite.nextSibling;
      if (next && next.nodeType == Node.ELEMENT_NODE && next.getAttribute('class') == "ar5iv-bibitem-preview") {
        next.remove();
        return; }
      // Before adding a preview modal,
      // cleanup older previews, in case they're still open
      document.querySelectorAll('span.ar5iv-bibitem-preview').forEach(function(node) {
        node.remove();
      })

      // Create the preview
      preview = document.createElement('span');
      preview.setAttribute('class','ar5iv-bibitem-preview');
      let target = document.getElementById(this.getAttribute('href').slice(1));
      target.childNodes.forEach(function (child) {
        preview.append(child.cloneNode(true));
      });
      let close_x = document.createElement('button');
      close_x.setAttribute("aria-label","Close modal for bibliography item preview");
      close_x.textContent = "×";
      close_x.setAttribute('class', 'ar5iv-button-close-preview');
      close_x.setAttribute('onclick','this.parentNode.remove()');
      preview.append(close_x);
      preview.querySelectorAll('.ltx_tag_bibitem').forEach(function(node) {
        node.remove();
      });
      cite.parentNode.insertBefore(preview, cite.nextSibling);
      return;
    }
    // Global Document initialization:
    // - assign the preview feature to all inline citation links
    document.querySelectorAll(".ltx_cite .ltx_ref").forEach(function (link) {
      link.addEventListener("click", clicked_cite);
    });
    </script>
    </body>
</html>

2402.10890
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.111Code and data will be released athttps://github.com/OSU-NLP-Group/llm-planning-eval.
abstract
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
Abstract
2402.10890
1IntroductionPlanning 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.
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.
This procedure shares common traits with how large language models (LLMs)  solve multi-step tasks, including mathematical reasoning, multi-hop question answering, and code generation.
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) .Figure 1:A generator-discriminator framework of language agents, where planning methods control the interaction between a generator and a discriminator, both of which are usually instantiated by some LLM.Motivated by the similarity, we critically examine how LLMs solve multi-step tasks from a language-agent view.
We unify different problem-solving procedures of LLMs into an agent framework (Figure1)  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 open-source, closed-source, 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 end-to-end evaluations of the discriminators and planning methods to verify and strengthen our findings.
In summary, our experiments show that:(1) Advanced planning methods, i.e., iterative correction and tree search, demand highly accurate discriminators (accuracy)  to achieve decent improvements over the simpler method, re-ranking.(2) Using environmental feedback, we improve the discrimination accuracy of LLMs by up to 30.2 and 8.4 absolute points on text-to-SQL parsing and mathematical reasoning, respectively.
Yet, our end-to-end evaluations suggest they have barely met the need for advanced planning methods to show significant improvements over re-ranking.(3) Meanwhile, advanced planning methods may not adequately balance accuracy and efficiency when using LLM-based discriminators.
In our experiments, compared to the other two methods, tree search is at least 10–20 times slower but leads to negligible performance gains.
This accuracy-efficiency trade-off can impede the deployment of tree search in real-world applications.
introduction
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
1Introduction
2402.10890
2Related WorkA lot of recent research efforts have focused on advanced planning methods for improving the multi-step problem-solving abilities of LLMs (,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.While it is commonly believed that discrimination is easier than generation for human and AI agents,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 ofandthat, without any external feedback or with obviously absurd feedback, LLMs may recognize some of their self-generated correct plans as wrong.also note that the performance gains of self-correction, 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.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
2Related Work
2402.10890
3Our Framework(a) Re-ranking.(b) Iterative Correction.(c) Tree Search.Figure 2:Illustration of three categories of planning methods examined in our unified generator-evaluator framework.As shown in Figure1, we systematically analyze different planning methods in a unified generator-discriminator 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 (Section4.1) .3.1GeneratorFor each planning step, we prompt the generator to sample action sequences (SQL queries or Python programs for math reasoning) .
For text-to-SQL parsing, we use 1-shot prompting, where the example is retrieved from the training sets using BM25.
For math reasoning, we use a fixed 2-shot prompt adapted from.
See prompts in AppendixC.3.2DiscriminatorGiven some (partial)  action sequences, we formulate the discrimination task as binary question answering.
The discrimination score of each tested example is the probability of “Yes” being generated as the next token.
Specifically, we prompt the LLMs with the question “Is the SQL/python program correct given the utterance/problem?” to generate one single token with its probability as the score.
With this formulation, we evaluate three types of LLMs in our experiments (Section4.2) .
Similar to the generator, we use 1-shot prompting with BM25 retrieval for text-to-SQL parsing and a fixed 2-shot prompt for math reasoning.
Details are in AppendixA.3.3Planning MethodsRe-ranking.Re-ranking is a straightforward planning method.
After sampling a few complete action sequences from the generator, it uses the discriminator to score them and return the highest-scoring plan (Figure2) .
Although simple, it is commonly used for code generationand mathematical reasoning tasks.
We consider re-ranking as a baseline planning method for more advanced ones.Iterative correction.Like re-ranking, iterative correction starts with the generator proposing a complete action sequence.
Then it leverages multiple rounds of revision to improve the initial plan based on the discriminator’s feedback (Figure2) .
When the generator and the discriminator are the same LLM, it becomes a prevalent planning method, self-correction.While some work uses greedy generation, our implementation samples the same number of action sequences as other planning methods for fair comparison.
Then, it uses the discriminator to select the best-scoring one for the next round’s revision.
We allow up to 10 rounds of corrections, with early exiting when the best plan meets a threshold of discrimination score () , or the score is not improved for 3 consecutive iterations.
For fair comparison, we prompt the generator to revise plans with 0-shot instruction following (AppendixC)  instead of few-shot, since in-context examples may introduce additional information.Tree Search.Tree search is another popular planning method for language agents, such as Monte-Carlo Tree Search, Pangu, Tree of Thoughts, and Language Agent Tree Search.
It uses a memory structure (e.g., a heap)  to store observed partial action sequences and their scores.
For each iteration, it prompts the generator for possible next steps for the current best partial plan, calls the discriminator to evaluate the steps, and updates the memory with new plans and scores (Figure2) .
Our tree search implementation is a kind of MCTS:(1) Selection: Find the highest scoring partial plan in the memory, implemented as a heap structure.(2) Expansion: Prompt the generator for the next step of this partial plan.
We follow recent work to define a step to be a SQL clauseor one line of Python code, which is semantically more meaningful.(3) Simulation: Reuse the generator to complete the partial plans as Monte-Carlo simulations.(4) Evaluation: Evaluate the simulations with the discriminator.
The score for each new step is the maximum score of all simulations starting from it.(5) Backpropagation: Update the partial plan with the new step and score (if higher)  and insert them into the heap memory.
After the update, if there is a complete plan in the heap memory, we terminate the tree search and return this plan.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
3Our Framework
2402.10890
4Experimental Setup4.1Tasks and DatasetsText-to-SQL Parsing.Text-to-SQL parsing is a code generation task of mapping natural language utterances to SQL queries.
It requires agents to ground utterances to database environment and generate multi-step plans as SQL queries, making it an appropriate testbed in our study.
To evaluate language agents’ potential for text-to-SQL parsing, we adapt two widely used datasets, Spiderand Bird.We use the entire training split in each dataset to prompt or fine-tune LLMs.222In Bird, we exclude training examples for one database,retail_world, due to annotation errors.For evaluation, due to resource and budget constraints, we randomly select 400 and 300 development set examples in Spider and Bird, respectively.
We also note that model performance may be lower on our evaluation sets because we uniformly sampled examples from each difficulty level, while the original development sets have skewed distributions towards easier examples (AppendixA.1) .Mathematical Reasoning.Mathematical reasoning is a common task for evaluating language agents’ multi-step reasoning and planning capabilities.
With 500 random examples from GSM8K’s development set, we follow program of thoughtsto test the agents’ ability to plan in Python programs and solve these grade school math word problems.4.2ModelsIn all experiments, we use CodeLlama-13B-Instruct as the generator in our framework.
We also evaluate three kinds of LLMs as the discriminator:(1) open-source LLMs: CodeLlama-7B-Instruct and CodeLlama-13B-Instruct,(2) closed-source LLMs: GPT-3.5-Turboand GPT-4-Turbo, and(3) fine-tuned LLMs: CodeLlama-7B-Instruct-FT and CodeLlama-13B-Instruct-FT.
Their implementation details are in AppendixA.3.
For brevity, we will omit “Instruct” in model names.4.3EvaluationIntrinsic Evaluation.We measure the discrimination abilities of LLMs with four intrinsic metrics.(1) Discrimination accuracy (Acc) : Given a pair of correct and wrong programs, we calculate the percentage where the correct program obtains a higher discrimination score than the wrong one.(2) Classification macro F1 (F1) : We treat “correct” and “wrong” as two classes and compute the macro average of F1 scores on these two labels.(3) Hit@1 (H@1) : Given a batch of candidate programs, we calculate the percentage where the highest scoring candidate is correct.(4) Mean reciprocal rank (MRR) : We compute the standard MRR score by the highest-ranking correct program in the batches.End-to-End Evaluation.To show the impact of discriminators, we evaluate language agents’ end-to-end performance using our three planning methods, with execution accuracy for text-to-SQL parsing and answer accuracy for math reasoning.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
4Experimental Setup
2402.10890
5Simulation Experiments with Oracle(a) Spider.(b) Bird.(c) GSM8K.Figure 3:End-to-end evaluation results (the first row)  and average inference time in log scale (the second row)  of our simulation experiments with oracle.5.1Oracle-Based DiscriminatorTo investigate how discrimination accuracy affects the overall performance of language agents using different planning methods (RQ1) , we utilize oracle environmental feedback to simulate a discriminator with controllable accuracy.
For text-to-SQL parsing, we compare the first five rows in the execution results of predicted and gold SQL queries and calculate their table cell overlaps (AppendixA.4) . For mathematical reasoning, we compare the predicted Python programs’ answers with the ground truth.We use a probability-based thresholdto control the accuracy of each simulated discriminator.
When evaluating each plan, the discriminator first computes a scorewith oracle information.
Then, it uses a random function to generate a number.
If, the discriminator returns the score.
Otherwise, it returns an inverted score.
In this way, we ensure that the discriminator’s accuracy is at most.5.2Results and AnalysisAs shown in Figure3, discrimination accuracy closely correlates with the performance of agents on all three datasets, no matter which planning method is used.
For instance, the performance of re-ranking agents improves linearly as we increase the discrimination accuracy threshold, setting up a strong baseline for agents using other planning methods.
We also note that it takes arounddiscrimination accuracy for all agents to outperform greedy generation on text-to-SQL parsing, demonstrating the task’s difficulty.
To answerRQ1, we further analyze the performance of agents using iterative correction and tree search as follows:Advanced planning methods demand highly accurate discriminators.For iterative correction agents, their performance usually cannot distinguish from the re-ranking baselines until we maximize the threshold(Figure3) .
This finding resonates withthat high-quality feedback may be the key to the success of iterative correction.
More interestingly, tree search agents consistently underperform the other two when the discrimination accuracy threshold.
Moreover, when raising the threshold to, we observe a sharp increase of their performance, with which they start to beat other kinds of agents.Advanced planning methods may not adequately balance accuracy and efficiency.By calculating the average inference time per example (Figure3) , we find that our implementation of tree search is at least–times slower than the other two planning methods, mainly due to frequent generation of Monte-Carlo simulations.
While we can remove the simulations to be more efficient and evaluate partial plans, in our preliminary study, we find LLMs would struggle in this setting. This accuracy-efficiency trade-off may hinder real-world applications of tree search methods.
Meanwhile, the inference time for iterative correction increases as the accuracy threshold is raised, suggesting more iterations are required to derive a correct answer.
This indicates that developing efficient and accurate planning methods remains a key problem for AI agents.Monte-Carlo tree search can be unstable, especially in the early stages.We observe that iterative correction outperforms tree search on Bird (Figure3)  when the accuracy threshold is 1.0.
This observation may be caused by the instability of Monte-Carlo tree search.
We first note that McNemar’s test finds no difference between iterative correction and tree search () , despite their performance gap (29.3 vs 32.7) .
The rationales are discussed in AppendixB.
Furthermore, we analyze all 25 examples of which iterative correction derives the correct answer but tree search fails.
In 12 out of the 25 examples (48%) , tree search fails to select the correct partial plan when the discrimination scores are the same.
Especially, this can happen in the early stages of tree search, where a correct program has not yet been discovered and all the steps receive a score of 0 from the oracle discriminator.
Thus, we consider this underperformance a consequence of search instability.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
5Simulation Experiments with Oracle
2402.10890
6LLM-Based DiscriminatorsModelsSpiderBirdGSM8K‡AccF1H@1MRRAccF1H@1MRRAccF1H@1MRRCodeLlama-7B54.037.156.062.344.646.713.018.048.638.736.246.9CodeLlama-13B58.237.157.063.149.446.712.718.362.238.741.851.0CodeLlama-7B-FT62.460.359.564.652.446.714.319.1----CodeLlama-13B-FT69.767.261.365.762.146.716.020.5----GPT-3.5-Turbo67.047.359.064.364.335.716.020.572.149.146.654.0GPT-4-Turbo76.554.963.066.776.250.120.323.093.891.159.861.6Table 1:Intrinsic evaluation results of naive LLMs’ discrimination abilities. Thebest performanceis in bold for open-source and closed-source LLMs.‡Since GSM8K’s training set does not have program of thoughts annotated for fine-tuning, we have only evaluated the models with in-context learning.CodeLlama-13BGPT-3.5-TurboCodeLlama-13B-FTSpiderBirdGSM8KSpiderBirdGSM8KSpiderBirdNaive Discriminator58.249.462.267.064.372.169.762.1+ Executability Check78.778.864.584.886.373.283.682.2++ Execution Result83.679.670.690.089.276.588.585.1Improvement25.430.28.423.024.94.418.823.0Table 2:Discrimination accuracy of observation-enhanced LLMs. Thebest performance(in bold)  is achieved using both kinds of environmental observations. We also underline thelargest improvementfor each dataset.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 (AppendixA.2) .6.1Naive DiscriminatorsAs Table1shows, most open-source LLMs have mediocre discrimination abilities.
After fine-tuning, CodeLlama-13B-FT could reach the same level of performance as GPT-3.5.
In comparison, closed-source LLMs exhibit stronger discrimination abilities, with GPT-4 achieving the best performance across all three datasets.
Although GPT-4 has 93.8 discrimination accuracy on GSM8K and is also better than GPT-3.5 on text-to-SQL parsing, due to its high cost, we will use GPT-3.5 in our experiments.6.2Observation-Enhanced DiscriminatorsTo improve LLMs’ discrimination abilities, we conduct an error analysis for CodeLlama-13B on its worst-performing intrinsic evaluation set, Bird.
We sample 50 pairs of SQL queries from the Bird intrinsic evaluation set with incorrect predictions.
In 25 of the 50 pairs (50%) , CodeLlama-13B assigns a higher score to non-executable SQL queries.
Consequently, no matter using which planning method, language agents could hardly perform well with such discriminators.Motivated by our error analysis, we first propose to add a program executability check as a safeguard for LLMs.
If a program is non-executable, our discriminator would discard LLMs’ score and return 0.
Otherwise, it returns the original LLM score.
Besides executability check, we incorporate the execution results of predicted programs (first 5 table rows of SQL queries or answer of Python program)  into the in-context examples and fine-tuning data.
If a program is non-executable, we useERRORto represent its execution result.Evaluation results (Table2)  show that these two non-oracle environmental observations can effectively improve LLMs’ discrimination accuracy.
Enhanced with environmental observations, CodeLlama-13B can obtain up to 25.4, 30.2, and 8.4 points absolute accuracy gain on Spider, Bird, and GSM8K, respectively.
For the other two models, we also observe significant gains compared to the naive discriminator baseline.
Such notable improvements also highlight the importance of filtering out non-executable programs, or invalid plans, during planning.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
6LLM-Based Discriminators
2402.10890
7End-to-End EvaluationDiscriminatorsSpider (Greedy Gen = 62.3) Bird (Greedy Gen = 16.0) Re-rankingIter. Correct.Tree SearchRe-rankingIter. Correct.Tree SearchCodeLlama-13B57.551.755.513.313.313.3GPT-3.5-Turbo58.352.756.218.017.314.0CodeLlama-13B-FT61.551.756.014.313.013.0CodeLlama-13BE65.562.062.521.024.322.7GPT-3.5-TurboE67.067.566.022.325.022.7CodeLlama-13B-FTE70.368.067.523.726.321.7Oracle Simulation () 71.076.0∗76.2∗27.032.7∗29.3Table 3:End-to-end execution accuracy on text-to-SQL parsing. Thebest performancefor each discriminator is in bold. Theoverall best performancefor naive and enhanced discriminators on each dataset is underlined.EObservation-enhanced discriminators.∗Statistically significant (; McNemar’s)  compared to re-ranking with the same discriminator on each dataset. We only observe such improvement with the oracle discriminator.While we have evaluated their discrimination abilities with a fixed test set, to answerRQ2, 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.7.1Text-to-SQL ParsingAs shown in Table3, agents using naive LLM-based discriminators do not perform well on text-to-SQL parsing.
On Spider, the re-ranking agent using CodeLlama-13B-FT has the best accuracy (61.5) , which is still lower than greedy generation (62.3)  that requires no planning and is more efficient.
On Bird, GPT-3.5-Turbo and re-ranking show an accuracy of 18.0, which is slightly higher than greedy generation (16.0) .
In addition to the mediocre performance, we find that when using naive discriminators, iterative correction and tree search consistently show worse or the same performance as re-ranking.
These results mostly agree with our findings in previous experiments that(1) advanced planning methods need strong discriminators, and(2) naive LLM-based discriminators are not accurate enough.After enhancing the discriminators with two environmental observations (Section6.2) , we effectively improve the agents’ performance without any modifications to the generator or the planning methods.
In 5 of the 6 experiments, CodeLlama-13B-FTEresults in the best execution accuracy among all discriminators.
It also leads to the overall best performance on Spider with re-ranking (70.3)  and on Bird with iterative correction (26.3) , showing the effectiveness of fine-tuning LLMs for discrimination and using environmental observations.7.2Mathematical ReasoningThe most interesting result in mathematical reasoning evaluation (Table4)  is the failure of iterative correction with naive discriminators.
When prompting the generator CodeLlama-13B for 0-shot correction, it would disregard the instruction to “generate a fixed python program” (AppendixC) , copy the program to be modified, and generate explanations and correction steps in natural language.
Such natural language steps, usually having some lexical overlap with the math problem, would increase the discrimination score of LLMs while being non-executable.
As a result, our iterative correction agent only has 10.2 answer accuracy when using CodeLlama-13B to evaluate its own generation.
While this issue also exists when using GPT-3.5-Turbo as the discriminator, it is less severe because GPT would sometimes assign a high score ()  to the initial Python program.
These scores trigger an early exit condition in iterative correction (Section3.3)  and stop the agent from calling the generator to add any natural language, thus avoiding the issue.
These findings echo related analysis on self-correction.DiscriminatorsRe-rankingIter. Correct.Tree Search‡CodeLlama-13B39.710.241.0GPT-3.5-Turbo47.037.050.0CodeLlama-13BE42.842.246.0GPT-3.5-TurboE47.648.451.0Oracle Simulation64.166.073.0() Table 4:End-to-end answer accuracy on GSM8K (Greedy Gen = 39.4) . Notations have the same meaning as in Table3. McNemar’s does not find difference between methods on GSM8K.‡Tree search is evaluated on 100 randomly selected examples from the 500 evaluation examples due to slow inference speed (Figure3) . For McNemar’s, we compare tree search results with those of re-ranking on the same 100 examples.Error TypeSpiderBirdGSM8KIter. Correct.Tree SearchIter. Correct.Tree SearchIter. Correct.Tree SearchDiscrimination29 (78.4%) 17 (60.7%) 9 (52.9%) 12 (50.0%) 30 (62.5%) 6 (66.7%) Exploration8 (21.6%) 11 (39.3%) 8 (47.1%) 12 (50.0%) 18 (37.5%) 3 (33.3%) Total37281724489Table 5:Error analysis of examples where re-ranking outperforms advanced planning methods. We list the actual number of error cases and their percentages in parenthesis for each dataset and planning method.With an executability check, enhanced discriminators help mitigate this issue in iterative correction, which now achieves better performance (42.2 and 48.4)  than greedy generation (39.4) .
Overall, the tree search agent using GPT-3.5-TurboEachieves the best answer accuracy. Nevertheless, McNemar’s test finds no difference ()  between the performance of re-ranking (47.6)  and that of iterative correction (48.4)  or tree search (51.0) .7.3AnalysisTo better understand the end-to-end evaluation results, we conduct an in-depth analysis of examples where re-ranking returns the correct program, but iterative correction or tree search does not (Table5) .
Specifically, we analyze cases of the strongest discriminators, CodeLlama-13B-FTEfor text-to-SQL parsing and GPT-3.5-TurboEfor mathematical reasoning, and divide them into two kinds of errors.(1) Discrimination error: The discriminator assigns a higher score for wrong programs than correct ones, which is not recoverable by any planning method.(2) Exploration error: The planning method has not found the correct program before termination.
Our analysis suggests that:LLM-based discriminators have not yet met the needs of advanced planning methods.Across all datasets, 50% or more discrimination errors are observed in each planning method.
On Spider, the number of such errors in iterative correction is as large as 29 out of 37 (78.4%) .
In fact, among the 29 errors, iterative correction has already found the correct SQL queries for 15 (40.5% of the total 37 errors)  of them.
However, not only does the discriminator fail to trigger early exits, but it also assigns a higher score for wrong SQL queries in new iterations.
Consequently, these erroneous SQL queries override the originally correct ones, leading to an overall performance drop.
The same issue is also serious in tree search.
When an incorrect partial program receives a high discrimination score, tree search will commit to it and hardly explore other possibilities, including the correct partial programs.
Such discrimination errors usually cannot be recovered by the planning methods themselves, unless they find another correct program with even higher scores.
This finding also demonstrates that determining early exits using oracle information in iterative correction may introduce a larger benefit than previously thought.Advanced planning methods need more thorough exploration.For the remaining cases, we observe that advanced planning methods have not found a correct program before terminating, which we call exploration errors.
This kind of error circles our discussion back to the accuracy-efficiency trade-off mentioned in our simulation experiments with oracle (Section5.2) .
Indeed, we can extend the exploration of planning methods in various ways, such as loosening termination conditions, increasing the number of generation samples for each step, and adjusting some hyperparameters for more diverse program samples.
Yet, all these adjustments can slow down the planning methods and reduce the language agents’ efficiency.
Additionally, we note that these strategies may not always result in better performance, as the discriminators may give unseen wrong programs a higher score.For these reasons,iterative correction and tree search cannot gain decent improvementover re-ranking with the same LLM-based discriminator.
On text-to-SQL parsing, tree search even shows worse performance than re-ranking when using CodeLlama-13B-FTE(Table3: 67.5 vs 70.3 on Spider; 21.7 vs 23.7 on Bird) .
More surprisingly, on GSM8K, advanced planning methods may not perform much better than re-ranking even with the oracle discriminator (; McNemar’s) .
Admittedly, some of the performance gains appear considerable, but McNemar’s tells us there are still decent chances of the simpler agent outperforming a more complex one (AppendixB) .
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
7End-to-End Evaluation
2402.10890
8ConclusionsThis 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.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
8Conclusions
2402.10890
LimitationsExperiments with Other Models.In this study, we focus on studying the generation and discrimination of instruction-tuned LLMs that have seen code data during pre-training.
This consideration is because:(a) They may have better in-context learning performance on our two tasks, text-to-SQL parsing and mathematical reasoning with program-of-thought;(b) We want to leverage their 0-shot instruction following capabilities in iterative correction for fair comparisons with other planning methods;(c) For GSM8K problems, LLMs tend to generate natural language plans instead of programs with 2-shot prompting, and some instructions other than in-context examples help to mitigate this issue.
Future research may extend our study to other LLMs of code and conduct an ablation study of instruction-tuning’s impact on models’ discrimination accuracy.Experiments with Natural Language Plans.Our study focuses on the generation and discrimination of formal language plans, i.e., programs, as they can directly interact with the environment.
Although feasible for mathematical reasoning, natural language plans require another semantic parsing step to convert them into actions defined in the corresponding environment, which may introduce intermediate errors and add noise to our analysis.
Therefore, we conduct the experiments with formal language plans using LLMs trained on code data.
As a future direction, it would be interesting to extend our study to natural language plans and see how the intermediate semantic parsing step would affect the overall performance of agents for mathematical reasoning.Impact of Generators on Planning Methods.While our work focuses on studying the relationship between different discriminators and planning methods, we acknowledge that the generator can also actively affect different planning methods.
For example, we can transform the generator’s perplexity into a probability and multiply it by the discriminator’s score.
We exclude such uses of the generator because in our preliminary experiments, we find that incorporating its perplexity leads to mixed results.
These results make it even harder to analyze how language agents behave when using different planning methods. Thus, we exclude the generator to have a clear picture of how discriminators can affect planning methods. Nevertheless, it is worth studying the generator’s impact on planning methods in future work.
body
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
Limitations
2402.10890
AcknowledgementsWe would like to thank colleagues from the OSU NLP group for their thoughtful comments.
This research was supported in part by a sponsored award from Cisco Research, NSF IIS-1815674, NSF CAREER #1942980, NSF OAC-2112606, and Ohio Supercomputer Center.
The views and conclusions contained herein are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. government.
The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notice herein.
conclusion
When is Tree Search Useful for LLM Planning?It Depends on the Discriminator
Acknowledgements