PaperlayerView exact revision on arXiv

Source-linked AI summary

Least-to-Most Prompting Enables Complex Reasoning in Large Language Models

Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, Ed Chi

arXiv:2205.10625v3cs.AIcs.CL

TL;DR

Chain-of-thought prompting often struggles when problems are harder than its exemplars, creating an easy-to-hard generalization gap. The paper introduces least-to-most prompting, which decomposes complex problems and solves the resulting subproblems sequentially using earlier answers. Across symbolic manipulation, compositional generalization, and math reasoning, it generalizes to harder problems and surpasses standard and chain-of-thought prompting, while decomposition prompts remain domain-sensitive.

  • Problem

    Chain-of-thought prompting often performs poorly when solving problems harder than the demonstration exemplars, especially in compositional generalization.

  • Method

    Least-to-most prompting decomposes a complex problem into simpler subproblems and sequentially solves them using answers to previously solved subproblems.

  • Results

    Least-to-most prompting significantly surpasses standard and chain-of-thought prompting across symbolic manipulation, compositional generalization, and mathematical reasoning.

  • Takeaways & Limitations

    Least-to-most prompting can generalize to problems harder than those demonstrated in prompts.

  • Takeaways & Limitations

    Decomposition prompts typically do not generalize well across different domains and can remain difficult to generalize even within the same domain.

Abstract

from arXiv · show

Chain-of-thought prompting has demonstrated remarkable performance on various natural language reasoning tasks. However, it tends to perform poorly on tasks which requires solving problems harder than the exemplars shown in the prompts. To overcome this challenge of easy-to-hard generalization, we propose a novel prompting strategy, least-to-most prompting. The key idea in this strategy is to break down a complex problem into a series of simpler subproblems and then solve them in sequence. Solving each subproblem is facilitated by the answers to previously solved subproblems. Our experimental results on tasks related to symbolic manipulation, compositional generalization, and math reasoning reveal that least-to-most prompting is capable of generalizing to more difficult problems than those seen in the prompts. A notable finding is that when the GPT-3 code-davinci-002 model is used with least-to-most prompting, it can solve the compositional generalization benchmark SCAN in any split (including length split) with an accuracy of at least 99% using just 14 exemplars, compared to only 16% accuracy with chain-of-thought prompting. This is particularly noteworthy because neural-symbolic models in the literature that specialize in solving SCAN are trained on the entire training set containing over 15,000 examples. We have included prompts for all the tasks in the Appendix.

1 INTRODUCTION

Machine learning still differs from human intelligence in few-shot learning, explainability, and generalizing to harder problems. Least-to-most prompting addresses easy-to-hard generalization by decomposing complex problems and sequentially solving their subproblems without training or finetuning.

  • Machine learning typically requires many labeled examples, whereas humans can learn new tasks from few demonstrations.
  • Chain-of-thought prompting improves difficult reasoning but often performs poorly when test problems are harder than the prompt exemplars.
  • Least-to-most prompting decomposes a complex problem into easier subproblems and solves them sequentially using previously obtained answers.
  • Both least-to-most stages use few-shot prompting, requiring neither training nor finetuning.
  • Empirical results across symbolic manipulation, compositional generalization, and math reasoning show generalization to problems harder than those demonstrated.

2 LEAST-TO-MOST PROMPTING

Least-to-most prompting uses two sequential stages: decompose a complex problem into simpler subproblems, then solve them while incorporating earlier answers. The stages can also be combined with other prompting techniques or merged into one pass for some tasks.

  • Decomposition: Decomposition prompts use constant examples followed by the specific question that should be broken into subproblems.
  • Subproblem solving: Subproblem-solving prompts combine constant solution examples, previously answered subquestions and solutions, and the next question.
  • Decomposition: In the illustrated math example, decomposition identifies “How long does each trip take?” as an intermediate subproblem.
  • Subproblem solving: The model solves subproblems sequentially, passing each generated answer into the next solving prompt.
  • Least-to-most prompting can be combined with chain-of-thought or self-consistency, and its stages can sometimes be merged into a single-pass prompt.

3 RESULTS

The paper evaluates least-to-most prompting against chain-of-thought and standard prompting on symbolic manipulation, compositional generalization, and math reasoning. Across these tasks, decomposing problems and using prior subproblem answers improves generalization to harder inputs, with especially strong results on SCAN.

  • Overview: Least-to-most prompting is evaluated on symbolic manipulation, compositional generalization, and math reasoning against chain-of-thought prompting.The experiments compare prompting methods across these three task areas.
  • Prompting strategy: Least-to-most prompting decomposes complex problems into simpler subproblems and solves them sequentially using answers from previously solved subproblems.Its solution prompts illustrate a base case and a recursive step, unlike independent chain-of-thought exemplars.
  • Symbolic manipulation: 74.0% accuracy was achieved by least-to-most prompting, compared with 31.8% for chain-of-thought prompting on the reported last-letter-concatenation comparison.Chain-of-thought performance also drops faster than least-to-most performance as testing-list length increases.
  • Compositional generalization: 99.7% accuracy was achieved by code-davinci-002 with least-to-most prompting on SCAN under the length split, and the solving rate remained the same across other splits and the full dataset.The SCAN setup uses command decomposition followed by command-to-action mapping.
  • Compositional generalization: 13 failures remained in the SCAN length-split test set, involving incorrect interpretations of “twice” or “thrice” after “around” and of “after” as “and”.These errors identify a concrete boundary for the otherwise high SCAN result.
  • Math reasoning: 62.39% accuracy was obtained by least-to-most prompting on the reported math-reasoning comparison, versus 60.97% for chain-of-thought prompting.For problems requiring at least 5 steps, performance increased from 39.07% to 45.23%; on DROP, least-to-most prompting outperformed chain-of-thought prompting by a large margin.

4 RELATED WORK

Prior work addresses compositional and easy-to-hard generalization through specialized architectures, grammar induction, and task decomposition. Least-to-most prompting differs by using sequentially dependent subproblems without training or finetuning.

  • SCAN evaluates compositional generalization, with its length split requiring models to handle test sequences longer than training sequences.
  • Neural-symbolic architectures and grammar induction techniques have achieved strong performance on SCAN.
  • Task decomposition methods have been used for multi-hop question answering by solving subquestions and aggregating their answers.
  • Unlike prior trained decomposition approaches, least-to-most prompting requires no training or finetuning and solves dependent subquestions sequentially.

5 LIMITATIONS

The method’s decomposition prompts have limited cross-domain transfer and can remain difficult to generalize even within mathematics. Its strongest results occur where decomposition is relatively straightforward.

  • Decomposition prompts typically do not generalize well across different domains and require domain-specific prompt demonstrations.
  • Within mathematics, accurate problem solving depends on receiving the correct decomposition, while generating that decomposition remains difficult.
  • The exceptional results on last-letter concatenation and SCAN are attributed to relatively straightforward decomposition in those tasks.

6 CONCLUSION AND DISCUSSION

The paper introduces least-to-most prompting as a two-stage strategy combining top-down decomposition with bottom-up solution generation. Across several reasoning settings, it surpasses standard and chain-of-thought prompting, while motivating more interactive approaches.

  • Least-to-most prompting combines top-down problem decomposition with bottom-up resolution generation.
  • Across symbolic manipulation, compositional generalization, and mathematical reasoning, least-to-most prompting significantly surpasses standard and chain-of-thought prompting.
  • Prompting is described as unidirectional communication that does not incorporate model feedback during instruction.
  • The discussion proposes fully bidirectional conversations as a potential way to provide immediate feedback and improve learning efficiency and effectiveness.

7 LAST-LETTER-CONCATENATION

The last-letter-concatenation task tests whether prompting methods generalize from short demonstrated lists to longer lists. Least-to-most prompting consistently outperforms chain-of-thought and is more data-efficient, though errors remain on long sequences.

  • Prompt context: 100% accuracy was achieved on lists up to size 12 with only one exemplar each for lists of sizes 2 and 3.This result used text-davinci-002 and covered the maximum tested list size.
  • Results: 74.0% versus 38.4% accuracy at L = 12 shows that 2-shot least-to-most outperforms 8-shot chain-of-thought on long sequences.The least-to-most prompt used 123 GPT3 tokens, compared with 573 for chain-of-thought.
  • Results: Least-to-most retains its accuracy advantage over chain-of-thought when both methods use the same examples.Chain-of-thought performs better with independent rather than dependent examples, but the comparison still favors least-to-most.
  • Model comparison: Code-davinci-002 handles increasing list lengths better than text-davinci-002, indicating an advantage for iteration and recursion.Text-davinci-002 accuracy drops faster on larger lists for both chain-of-thought and least-to-most prompting.
  • Model comparison: 19.6% versus 96% accuracy at L = 4 shows that code-davinci-001 performs much worse than code-davinci-002 under least-to-most prompting.The comparison indicates potential improvement from newer model generations using the same configuration.
  • Error analysis: Adding two more examples eliminates template errors, while concatenation errors increase from length 4 to length 12 with a 2-example prompt.Longer lists require more concatenations, whereas the number of base-template applications remains constant.

8 SCAN

SCAN experiments use least-to-most prompting to decompose commands into smaller components and then map those components to action sequences. The approach achieves strong results but still makes recurring interpretation errors.

  • Prompt contexts: SCAN command examples encode actions through repetition, concatenation, and directional mappings.For example, “turn opposite left” maps to “TURN LEFT” * 2, while “walk after run” maps to “RUN” + “WALK”.
  • Method: Least-to-most prompting uses separate command decomposition and command mapping contexts for SCAN.The decomposition context breaks long commands into short commands, while the mapping context translates commands into action sequences.
  • Error analysis: Text-davinci-002 made only two main mistake types: mishandling “twice” or “thrice” after “around” and interpreting “after” as “and”.These errors contrast with the broader error distribution observed for text-davinci-001.
  • Error analysis: Text-davinci-002 sometimes mis-translates “left” and “right” by dropping a command or inventing an action such as “LOOK LEFT”.These directional errors were not observed with the other models in the cited analysis.
  • Error analysis: Copy errors can cause “after” constructions to be treated like “and” and parentheses to be omitted when combining subexpressions.The cited example produces an incorrect translation despite correctly translating both connected subexpressions.

8.4 EXPANDING PYTHON EXPRESSIONS USING PROMPTING

The paper also evaluates prompting a language model to expand intermediate Python expressions into action sequences. This achieves high accuracy without requiring a Python executor.

  • Expansion results: 99.7% accuracy was achieved when prompting a language model to expand 1,000 generated Python expressions.The expressions were produced by code-davinci-002.
  • Expansion results: The combined method exceeds 99% accuracy for generating and expanding intermediate Python expressions without using the Python executor.Both generation and expansion are reported at 99.7% accuracy.
  • Expansion method: The expansion prompt rewrites repeated expressions such as “JUMP” * 3 into explicitly enumerated action sequences.It also handles concatenation and parenthesized repeated expressions.
  • Expansion method: The prompt simplifies nested multiplication before expansion, for example rewriting (“TURN LEFT” * 2) + (“TURN RIGHT” + “WALK”) * 4 * 2 as repeated terms.Numbers and parentheses are added to help the model track repetitions.

9 DROP

This section reports DROP numerical-reasoning evaluations across language models and prompting methods, alongside an analysis of least-to-most failures. The results also identify errors from problem solving, decomposition, and incorrect labels.

  • Evaluation: 500 randomly sampled DROP examples evaluate zero-shot and prompting methods with text-davinci-002.The evaluation covers non-football and football examples.
  • Model comparison: text-davinci-002 is consistently worse than code-davinci-002 on the numerical reasoning subset of DROP.
  • Error analysis: Chain-of-thought errors can arise from using an unrelated intermediate fact instead of the fact required by the question.The analyzed cases identify unrelated dates as the source of incorrect final answers.
  • Error analysis: 13 of 20 sampled least-to-most failures result from wrong problem solving, while 4 result from wrong decomposition and 3 from incorrect ground truth.
  • Error analysis: Least-to-most prompting can produce the correct answer even when the supplied label is wrong.One example has label 417, while the stated calculation yields 418.

10 GSM8K

The GSM8K experiments compare one-shot and engineered prompting methods, focusing on whether least-to-most prompting generalizes when problems require more reasoning steps than the demonstration. Results are reported for GPT-3 code-davinci-002 using accuracy comparisons across prompting variants.

  • One-shot prompts: Table 18 reports GSM8K accuracy by the number of reasoning steps required in the expected solution.Problems requiring 3 or more steps test generalization beyond the two-step demonstration example.
  • One-shot prompts: Least-to-most prompting significantly outperforms chain-of-thought prompting as the number of reasoning steps exceeds those illustrated in the prompt.Overall accuracy is only moderately higher, but the breakdown reveals a larger advantage on longer solutions.
  • Experimental setup: The experiments compare one-shot and engineered chain-of-thought and least-to-most prompts, alongside zero-shot and standard prompting baselines.The engineered comparisons also include variants using multiple in-domain GSM8K examples.
  • Engineered prompts: The one-shot chain-of-thought prompt achieves 60.87% accuracy versus 61.18% for the original eight-shot prompt.The authors use this similarity to characterize the one-shot prompt as a reasonable chain-of-thought baseline.
  • Engineered prompts: Additional prompt engineering with multiple in-domain GSM8K examples improves the overall accuracy of both chain-of-thought and least-to-most prompting.In this setting, least-to-most prompting does not improve overall accuracy over chain-of-thought because most test questions do not require more steps than the demonstrations.
  • Prompt contexts: The prompt templates include a decomposition request followed by a second request that uses the generated reply to produce the final answer.The least-to-most one-shot template begins by asking the model to break down the problem, then appends the initial reply before requesting the answer.
Loading 2205.10625v3…