PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, Huan Sun

arXiv:2402.10890v2cs.CLcs.AIcs.LG

TL;DR

The paper asks whether LLM discriminators can assess candidate actions accurately enough for advanced planning methods to outperform re-ranking. It evaluates discriminator accuracy and planning methods across text-to-SQL parsing and mathematical reasoning, finding that advanced methods need highly accurate discriminators but current LLM-based ones barely meet that need.

  • Problem

    The paper examines how discriminator accuracy affects language-agent performance across planning methods and whether LLM discriminators can correctly assess actions in practical settings.

    Source: §1 · p. 1

  • Method

    The paper evaluates re-ranking, iterative correction, and tree search on text-to-SQL parsing and mathematical reasoning, using oracle simulations and LLM-based discriminators.

    Source: §1 · p. 2, §3.3 · p. 3

  • Results

    Across two tasks, advanced planning methods need at least 90% discriminator accuracy for decent gains over re-ranking, while current LLM discriminators barely meet that need.

    Source: §1 · p. 2, §8 · p. 9

  • Takeaways & Limitations

    Tree search is at least 10–20 times slower than the other methods for negligible performance gains, a trade-off that may hinder real-world applications.

    Source: §1 · p. 2

    The study focuses on instruction-tuned LLMs with code data in pretraining and on formal-language plans such as programs.

    Source: Limitations · pp. 9–10

Abstract

from arXiv · show

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

1 Introduction

The paper frames multi-step LLM problem solving as interaction among a generator, discriminator, and planning method. It asks how discriminator accuracy affects planning performance and whether LLM discriminators can assess actions reliably in practice.

1 Introduction

  • The study compares re-ranking, iterative correction, and tree search within a generator-discriminator framework for multi-step LLM tasks.The framework treats generation, discrimination, and planning as separate components of problem solving.Source: §1 · pp. 1–2
  • The research questions ask how discrimination accuracy affects agents using different planning methods and whether LLM discriminators correctly assess actions in practical settings.The paper tests these questions through analysis of discrimination ability and its impact on agent performance.Source: §1 · pp. 1–2
  • Across text-to-SQL parsing and mathematical reasoning, advanced planning needs discriminators with at least 90% accuracy for decent gains over re-ranking.End-to-end evaluations suggest current LLM discriminators barely meet that need; tree search is at least 10–20 times slower than the other methods for negligible gains.Source: §1 · p. 2

2 Related Work

Prior work explores advanced planning for LLM problem solving, but this paper focuses on how discriminator quality relates to planning methods and on improving discrimination capability.

2 Related Work

  • Incorrect outcome predictions can lead to suboptimal plans, so discriminator quality may matter regardless of the planning method.The paper identifies this relationship as distinct from work centered on planning methods themselves.Source: §2 · p. 2
  • Prior findings suggest LLMs may misjudge their own correct plans without useful external feedback, while comprehensive test cases can be costly to annotate.External feedback such as ground-truth labels or test sets may support iterative correction, but such feedback is often unavailable for new problems.Source: §2 · p. 2
  • The paper advocates developing more accurate LLM-based discriminators to improve agents’ accuracy and efficiency with advanced planning methods.It also encourages evaluation with practical, non-oracle discriminators.Source: §2 · p. 2

3 Our Framework

The framework separates plan generation, plan evaluation, and the method that coordinates their interaction. It instantiates these components for text-to-SQL parsing and mathematical reasoning.

3 Our Framework

  • The framework’s generator proposes partial or complete action sequences, its discriminator evaluates outcomes, and its planning method ranks actions and manages model interaction.The components are instantiated on text-to-SQL parsing and mathematical reasoning.Source: §3 · p. 2

3.1 Generator

  • The generator samples SQL queries or Python programs as action sequences for the planning process.Text-to-SQL uses one retrieved training example, while mathematical reasoning uses a fixed two-example prompt.Source: §3.1 · pp. 2–3

3.2 Discriminator

  • The discriminator answers whether a partial action sequence is correct, using the probability of “Yes” as its score.The paper prompts LLMs with a binary question about whether the SQL or Python program is correct.Source: §3.2 · p. 3

3.3 Planning Methods

  • Re-ranking selects the highest-scoring complete sampled plan, while iterative correction revises a complete plan over multiple rounds using discriminator feedback.Iterative correction becomes self-correction when the generator and discriminator are the same LLM.Source: §3.3 · p. 3
  • Tree search stores partial plans and scores, expands the best-scoring partial plan, evaluates simulated completions, and updates the stored plans.The implementation uses Monte-Carlo simulations to complete partial plans before discriminator evaluation.Source: §3.3 · p. 3

4 Experimental Setup

The experiments evaluate language agents on text-to-SQL parsing and mathematical reasoning using a fixed generator and several classes of discriminators. The setup measures both discriminator quality and end-to-end task performance.

4.1 Tasks and Datasets

  • Text-to-SQL evaluation uses sampled development examples from Spider and Bird, while mathematical reasoning uses 500 GSM8K examples with Python programs.The evaluation samples 400 Spider and 300 Bird development examples, and the SQL sample is uniform across difficulty levels.Source: §4.1 · p. 4

4.2 Models

  • CodeLlama-13B-Instruct is the generator, and discriminators include open-source, proprietary, and fine-tuned LLMs.The tested discriminator families include CodeLlama, GPT-3.5-Turbo, GPT-4-Turbo, and fine-tuned CodeLlama models.Source: §4.2 · p. 4

4.3 Implementation Details

  • Fine-tuned discriminator models use one epoch, batch size 128, learning rate 1e-5, 3% warmup, and a cosine scheduler.Experiments use up to four RTX A6000 GPUs on Spider and GSM8K, and up to four A100 GPUs on Bird.Source: §4.3 · p. 4

4.4 Evaluation

  • Intrinsic evaluation uses discrimination accuracy, macro F1, Hit@1, and MRR, while end-to-end evaluation measures SQL execution accuracy and math answer accuracy.Figure 3 presents oracle simulation end-to-end results and average inference time in log scale.Source: §4.4 · pp. 4–5, Figure 3 · p. 5

5 Simulation Experiments with Oracle

Oracle-based simulations show that planning performance tracks discriminator accuracy, with advanced methods needing high accuracy to surpass simpler agents. Tree search’s gains come with a substantial inference-time cost and can be affected by early search instability.

5.1 Oracle-Based Discriminator

  • The simulations use oracle feedback to control discriminator accuracy, comparing SQL execution-result cell overlap or predicted Python answers with ground truth.A probability threshold τ determines whether the oracle score is returned or inverted, keeping accuracy at most τ.Source: §5.1 · p. 5

5.2 Results and Analysis

  • Discrimination accuracy closely correlates with performance across all three datasets and planning methods; re-ranking improves linearly as accuracy rises.On text-to-SQL, all agents need around 80% discrimination accuracy to outperform greedy generation.Source: §5.2 · p. 5
  • At τ=0.9, tree search sharply improves and begins outperforming other agent types, while iterative correction usually needs τ=1.0 to match re-ranking.Source: §5.2 · pp. 5–6
  • Tree search is at least 10–20 times slower than the other two methods, mainly because it frequently generates Monte-Carlo simulations.Removing simulations and evaluating partial plans may improve efficiency, but preliminary study found LLMs struggle in that setting.Source: §5.2 · p. 6
  • On Bird, early equal oracle scores can lead tree search to miss a correct partial plan, and the authors attribute this underperformance to search instability.This occurred in 12 of the 25 examples where iterative correction succeeded and tree search failed; McNemar’s test found no significant difference.Source: §5.2 · p. 6

6 LLM-Based Discriminators

The paper evaluates LLM-based discriminators and tests whether environmental observations improve their accuracy. Such observations raise discrimination accuracy, while the paper also reports model weaknesses and text-to-SQL execution comparisons.

6 LLM-Based Discriminators

  • The evaluation re-labels generator outputs with ground truth to measure whether LLM-based discriminators correctly assess agent actions.Source: §6 · p. 6

6.1 Naive Discriminators

  • Most open-source LLMs have mediocre discrimination ability; fine-tuning brings CodeLlama-13B-FT to GPT-3.5’s performance level, while GPT-4 performs best across all three datasets.Source: §6.1 · p. 6

6.2 Observation-Enhanced Discriminators

  • On Bird, CodeLlama-13B assigned higher scores to non-executable SQL in 25 of 50 incorrect-query pairs, motivating an executability-check safeguard.The proposed safeguard discards the LLM score for non-executable programs; execution results are also incorporated into examples and fine-tuning data.Source: §6.2 · pp. 6–7
  • Observation-enhanced discriminators improve accuracy by up to 25.4, 30.2, and 8.4 absolute points on Spider, Bird, and GSM8K, respectively.Source: Table 2 · p. 7, §6.2 · p. 7
  • Table 3 reports text-to-SQL execution accuracy; statistically significant gains over same-discriminator re-ranking appear only with the oracle discriminator.Source: Table 3 · p. 7

7 End-to-End Evaluation

The section evaluates language agents with LLM-based discriminators across three planning methods. Naive discriminators often leave advanced methods no better than re-ranking, while environmental observations can improve accuracy and efficiency.

7.1 Text-to-SQL Parsing

  • 61.5 accuracy on Spider with CodeLlama-13B-FT re-ranking remained below greedy generation (62.3), while Bird re-ranking with GPT-3.5-Turbo reached 18.0 versus greedy generation (16.0).With naive discriminators, iterative correction and tree search consistently performed no better than re-ranking.Source: §7.1 · p. 7
  • 5 of 6 text-to-SQL experiments had CodeLlama-13B-FTE achieve the best execution accuracy among discriminators, including overall best results on Spider with re-ranking (70.3) and Bird with iterative correction (26.3).The observation-enhanced discriminator improves performance without changing the generator or planning method.Source: §7.1 · p. 7
  • Environmental observations reduce end-to-end latency, especially for tree search, as executability checks quickly identify incorrect programs and prune the search space.Latency increased for iterative correction with GPT-3.5-TurboE and CodeLlama-13B-FTE because their stronger discrimination allowed more planning loops.Source: §7.1 · p. 8

7.2 Mathematical Reasoning

  • 10.2 answer accuracy resulted when CodeLlama-13B scored its own iterative-correction output, where non-executable natural-language corrections could receive higher scores.GPT-3.5-Turbo sometimes scored the initial Python program above 0.99, triggering an early exit that avoided this issue.Source: §7.2 · p. 8
  • 51.0 answer accuracy for tree search on GSM8K was not significantly different from re-ranking (47.6) or iterative correction (48.4).McNemar’s test found no difference between the methods; tree search was evaluated on 100 randomly selected examples because of slow inference.Source: Table 5 · p. 8, §7.2 · p. 8

7.3 Analysis

  • At least 50% of errors across datasets were discrimination errors, while exploration errors reflected failure to find a correct program before termination.More exploration can slow planning and may not improve performance if discriminators score unseen wrong programs higher.Source: §7.3 · p. 9
  • 67.5 versus 70.3 on Spider and 21.7 versus 23.7 on Bird show tree search underperforming re-ranking with CodeLlama-13B-FTE; on GSM8K, advanced methods also lacked significant gains over re-ranking even with an oracle discriminator.The GSM8K comparison was not significant by McNemar’s test (p > 0.05).Source: §7.3 · p. 9

8 Conclusions

The paper investigates how discriminator accuracy relates to planning performance in language agents. Across text-to-SQL parsing and mathematical reasoning, discriminator accuracy correlates with performance and affects efficiency, while LLM-based discriminators remain insufficiently accurate for advanced planning methods.

8 Conclusions

  • Experiments on text-to-SQL parsing and mathematical reasoning found that discriminator accuracy strongly correlates with language-agent performance and affects efficiency, while LLM-based discriminators remain insufficiently accurate for advanced planning methods.The authors call for more accurate discrimination models, including stronger grounded understanding of execution results beyond error signals.Source: §8 · p. 9

Limitations

The study’s scope and design constrain which settings its findings directly cover.

Limitations

  • The experiments focus on instruction-tuned LLMs that have seen code during pretraining.The authors suggest extending evaluation to other code models and studying instruction-tuning’s impact on discrimination accuracy.Source: Limitations · p. 9
  • The study evaluates formal-language plans, such as programs; natural-language plans would require semantic parsing that may introduce intermediate errors and noise.The authors identify extending the study to natural-language plans as future work.Source: Limitations · p. 10
  • Generator perplexity was excluded after preliminary experiments produced mixed results, leaving its influence on planning methods outside this analysis.The authors note that generator effects warrant future study.Source: Limitations · p. 10

A.1 Text-to-SQL Parsing Evaluation Sets

The text-to-SQL evaluation sets were subsampled to balance difficulty levels and databases, unlike the datasets’ original difficulty distributions.

A.1 Text-to-SQL Parsing Evaluation Sets

  • The evaluation sampled 100 examples per difficulty level, producing 400 Spider examples and 300 Bird examples through repeated database and example selection.Examples were categorized by dataset difficulty before sampling.Source: §A.1 · p. 13
  • The original Spider and Bird development sets skew toward easier examples, whereas the evaluation sets use uniform difficulty distributions.The paper notes that models may perform lower on the uniformly distributed evaluation sets.Source: §A.1 · p. 13
  • The balanced difficulty distributions make macro averages of model performance less biased.The evaluation also balances database representation through its sampling procedure.Source: §A.1 · p. 13

A.2 Intrinsic Evaluation Data

The appendix describes how the authors build intrinsic discriminator evaluations and task-specific discriminator data, define oracle correctness, and test whether method gains are statistically significant.

A.2 Intrinsic Evaluation Data

  • Intrinsic evaluation sets reuse oracle-simulation generations, relabel programs at τ = 1.0, and pair correct and incorrect programs within each batch.The evaluation also measures pairwise discrimination accuracy, per-program classification F1, and batch-ranking Hit@1 and MRR.Source: §A.2 · p. 13

A.3 Data for Discriminator LMs

  • Text-to-SQL discriminator data use synthesized incorrect queries and ground-truth examples, while GSM8K lacks program annotations for discriminator fine-tuning.For mathematical reasoning, the authors annotate two incorrect Python programs for the two generator examples and use them in binary-question prompts.Source: §A.3 · pp. 13–14

A.4 Implemendation of Oracle Discriminator

  • The SQL oracle scores predicted queries by F1 over overlapping result cells, comparing rows head-to-head under an ordered-row assumption before counting unordered cell overlaps.For mathematical reasoning, the oracle returns 1 only when the program executes and its answer equals the ground truth; otherwise it returns 0.Source: §A.4 · p. 14

B McNemar’s Test for Statistical Significance

  • Exact McNemar testing compares discordant examples; on Bird, 15 of 40 cases favoring tree search yield p = 0.15, while a 0-of-10 reverse count would be statistically different.The test uses the exact binomial version because sample sizes are relatively small.Source: B McNemar’s Test for Statistical… · p. 14

C More Analysis on Simulation Experiments with Oracle

With oracle discrimination, more accurate scoring can increase iterative-correction runtime because it prevents premature stopping and permits further revisions.

C More Analysis on Simulation Experiments with Oracle

  • At threshold 0.6, iterative correction averages 1.275 iterations and 21.5 seconds per example; at 1.0, it averages 1.725 iterations and 27.9 seconds.The latter is 1.35 times as many iterations and 1.29 times the inference time.Source: C More Analysis on Simulation… · p. 15
  • Accurate discrimination can keep correction running by avoiding mistaken early exits and recognizing small plan improvements, increasing inference time.The method exits when the best score exceeds 0.99 or fails to improve for three consecutive iterations.Source: C More Analysis on Simulation… · p. 15

D Prompt Examples

  • The appendix provides prompt examples for generation and iterative correction in SQL and mathematical reasoning, plus discrimination prompts with program pairs, sometimes alongside execution results.The examples include one-shot SQL generation and discrimination, and two-shot mathematical-reasoning generation and discrimination.Source: Table D.1 · p. 16, Table D.2 · p. 16, Table D.3 · p. 17
Loading 2402.10890v2…