PaperlayerView exact revision on arXiv

Source-linked AI summary

PAL: Program-aided Language Models

Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, Graham Neubig

arXiv:2211.10435v2cs.CLcs.AI

TL;DR

LLMs can decompose reasoning problems but may err when solving their intermediate steps. PAL generates executable programs for those steps and delegates solving to a Python interpreter, outperforming larger chain-of-thought models across 13 tasks, including a 15% absolute top-1 gain on GSM8K.

  • Problem

    LLMs can decompose natural-language problems but often make logical and arithmetic mistakes while solving the resulting steps.

  • Method

    PAL uses an LLM to generate interleaved natural-language and programming-language reasoning steps, then delegates solution execution to a Python interpreter.

  • Results

    Across 13 arithmetic and symbolic reasoning tasks, PAL using Codex outperforms larger chain-of-thought models; on GSM8K, it surpasses PaLM-540B by 15% absolute top-1 accuracy.

  • Takeaways & Limitations

    PAL separates problem decomposition from solving, using a neural language model for the former and a symbolic interpreter for the latter.

Abstract

from arXiv · show

Large language models (LLMs) have recently demonstrated an impressive ability to perform arithmetic and symbolic reasoning tasks, when provided with a few examples at test time ("few-shot prompting"). Much of this success can be attributed to prompting methods such as "chain-of-thought'', which employ LLMs for both understanding the problem description by decomposing it into steps, as well as solving each step of the problem. While LLMs seem to be adept at this sort of step-by-step decomposition, LLMs often make logical and arithmetic mistakes in the solution part, even when the problem is decomposed correctly. In this paper, we present Program-Aided Language models (PAL): a novel approach that uses the LLM to read natural language problems and generate programs as the intermediate reasoning steps, but offloads the solution step to a runtime such as a Python interpreter. With PAL, decomposing the natural language problem into runnable steps remains the only learning task for the LLM, while solving is delegated to the interpreter. We demonstrate this synergy between a neural LLM and a symbolic interpreter across 13 mathematical, symbolic, and algorithmic reasoning tasks from BIG-Bench Hard and other benchmarks. In all these natural language reasoning tasks, generating code using an LLM and reasoning using a Python interpreter leads to more accurate results than much larger models. For example, PAL using Codex achieves state-of-the-art few-shot accuracy on the GSM8K benchmark of math word problems, surpassing PaLM-540B which uses chain-of-thought by absolute 15% top-1. Our code and data are publicly available at http://reasonwithpal.com/ .

1. Introduction

Few-shot prompting and chain-of-thought have improved LLM reasoning, but models still make arithmetic and logical errors during solution. PAL addresses this by generating programmatic reasoning steps and delegating execution to a Python interpreter, achieving stronger results across reasoning tasks.

  • Few-shot prompting has enabled LLM success across commonsense, mathematical, and symbolic reasoning tasks.
  • Chain-of-thought prompting asks LLMs to decompose problems into explicit intermediate steps before producing answers.
  • LLM performance falls on complex arithmetic and large numbers, even when models can decompose problems into steps.
  • PAL generates programs as reasoning steps while offloading solution execution to a Python interpreter.
  • 13 tasks: PAL using Codex outperforms much larger PaLM-540B models using chain-of-thought; on GSM8K, it gains 15% absolute top-1 accuracy.

2. Background: Few-shot Prompting

Few-shot prompting supplies demonstrations at test time, while chain-of-thought augments those demonstrations with natural-language reasoning steps. At inference, the LLM generates both the reasoning process and final answer for a new question.

  • Few-shot prompting provides a small set of input-output examples as part of the test-time prompt without modifying the underlying LLM.
  • Each few-shot example pairs an input x_i with an output y_i, and examples are concatenated into a prompt before inference.
  • Chain-of-thought adds natural-language intermediate steps t_i to each in-context input-output example.
  • During inference, the model generates both the new thought sequence t_test and final answer y_test.

3. Program-aided Language Models

PAL represents reasoning as interleaved natural-language and programming-language statements, then executes the generated program to obtain the answer. Its prompts adapt existing examples with programming constructs and meaningful variable names, and the approach also extends to least-to-most prompting.

  • Program-aided Language Models: PAL represents thoughts as interleaved natural-language and programming-language statements rather than providing final answers in demonstrations.
  • Program-aided Language Models: For a test instance, the language model generates intermediate steps together with corresponding programmatic statements.
  • Program-aided Language Models: PAL augments each natural-language step with code so the generated program, rather than the LLM, performs the calculation.
  • Program-aided Language Models: The generated program is run by a solver to produce the final result; this work uses a standard Python interpreter, though other solvers are possible.
  • Prompt design: PAL prompts use programming constructs and meaningful variable names, which the paper reports as critical in its experiments.
  • Related prompting methods: PAL also improves least-to-most prompts, which decompose questions into sub-questions.

4. Experimental Setup

The experiments evaluate PAL across mathematical, symbolic, and algorithmic reasoning tasks using few-shot prompting and Codex-based comparisons with established prompting strategies and models. The setup includes standard and large-number mathematical benchmarks, symbolic object-and-concept tasks, and algorithmic tasks requiring deterministic procedures.

  • Task coverage: Experiments cover mathematical, symbolic, and algorithmic reasoning tasks from multiple benchmarks, including BIG-Bench Hard.The mathematical suite includes GSM8K, SVAMP, ASDIV, and MAWPS; symbolic and algorithmic tasks come from BIG-Bench Hard.
  • Baselines and evaluation: Comparisons include DIRECT, chain-of-thought, and PAL prompting, primarily using CODEX with greedy decoding at temperature 0.For available tasks, PAL and COT use the same in-context examples; PAL results are averaged over three benchmark runs.
  • Mathematical reasoning: PAL is evaluated on eight mathematical word problem datasets containing grade-school algebra problems.The setup uses explicit natural-language intermediate steps only when they benefit performance; for these tasks, prompts retain meaningful variable names.
  • Mathematical reasoning: GSM-HARD replaces one GSM8K number with a random integer of up to 7 digits to test reasoning with larger values.The dataset is designed to examine generalization beyond the small numbers common in GSM8K.
  • Symbolic reasoning: The symbolic suite includes COLORED OBJECTS, PENGUINS, and DATE, covering object attributes, object dynamics, and date computation.COLORED OBJECTS requires tracking relative and absolute positions and colors; PENGUINS additionally allows penguins to be added or removed.
  • Algorithmic reasoning: Algorithmic evaluation uses OBJECT COUNTING and REPEAT COPY, which require deterministic counting or sequence generation from instructions.OBJECT COUNTING asks for the number of objects of a specified type, while REPEAT COPY generates word sequences according to instructions.

5. Results

PAL consistently outperforms chain-of-thought and larger models across mathematical, symbolic, and algorithmic reasoning tasks, while remaining more robust to large-number inputs and question complexity.

  • PAL using Codex sets a new few-shot state-of-the-art top-1 result across all evaluated datasets, outperforming larger chain-of-thought baselines.
  • 61.5% accuracy is retained by PAL on GSM-HARD, a 14.3% drop compared with COT’s decline from 65.6% to 20.1%.
  • 80.4% GSM8K accuracy results from PAL with majority@40, exceeding Minerva-540B by 1.9% with the same number of samples.
  • 96.7% accuracy on OBJECT COUNTING improves over COT by 23.7% absolute, while PAL improves over COT by 21.8% on REPEAT COPY.
  • PAL remains close to 100% across COLORED OBJECTS input lengths, whereas COT accuracy becomes unstable and drops as object count increases.

6. Analysis

Analysis shows that PAL depends on the language model’s coding ability and meaningful variable names, while interpreter execution—not merely Python-style prompting—drives its gains.

  • PAL’s relative improvement over COT remains consistent with weaker code models, despite their lower absolute accuracies.
  • PAL outperforms COT with text-davinci-002 and text-davinci-003, but COT performs better with text-davinci-001.
  • 72.0 solve rate for PAL on GSM8K exceeds the 23.2 rate from generating and internally executing Python code without an interpreter.
  • Removing comments slightly reduces accuracy but remains above COT, whereas removing meaningful variable names further decreases accuracy and performs worse than COT.

7. Related Work

Related work situates PAL among few-shot reasoning, tool-augmented language models, and semantic parsing, emphasizing its free-form code generation and broader task coverage.

  • Prompting: Chain-of-thought and related prompting methods improve reasoning but previous approaches suffer from arithmetic inaccuracy and incorrect reasoning.
  • LMs with external tools: Unlike specialized-module approaches, PAL generates Python code for external execution without specialized pretraining.
  • Related programmatic prompting: PAL differs from program-of-thought prompting by demonstrating gains on symbolic and algorithmic benchmarks as well as mathematical problems.
  • Semantic parsing: PAL can be viewed as general semantic parsing into free-form Python rather than a constrained domain-specific language.

8. Conclusion

PAL uses programs as intermediate reasoning steps and delegates solving to a Python interpreter, achieving accurate results across broad reasoning tasks when the programmatic steps are correct.

  • PAL offloads solving and calculating from the LLM to an external Python interpreter instead of using the LLM for both understanding and solving.
  • PAL’s final answer is guaranteed accurate given correctly predicted programmatic steps.
  • The method is demonstrated across 13 mathematical, symbolic, and algorithmic tasks and outperforms larger chain-of-thought models.
  • 71.8% average performance falls to 59% when informative variable names are replaced with single letters, while COT achieves a 63% solve rate.

B. Additional analysis on Arithmetic Reasoning

Additional arithmetic analyses test whether PAL’s gains depend on prompt construction, multi-step code, runtime execution, or the underlying model family. The results favor code-based reasoning with external execution over simply improving COT examples or asking the model to execute its own reasoning.

  • GSM-HARD with hard prompts: Larger-number prompts provide only modest COT gains, so better few-shot examples alone do not reproduce code-based reasoning improvements.The modified prompts match GSM-HARD’s larger-number distribution.
  • Succinct Code: Single-line PAL expressions reduce performance to the level of direct prompting, showing that the multi-step breakdown matters.The ablation is reported in Table 6, fourth row.
  • Generating the answer directly: Forcing the LLM to generate the answer after its code-based reasoning drops solve rates to near DIRECT levels.This variant simulates runtime execution within the language model rather than using the Python runtime.
  • Text-based models: PAL also applies beyond Codex, with additional experiments indicating that the approach is not restricted to code-specialized language models.The passage reports experiments with text-based language models but is truncated before giving their detailed results.

D. Analyzing the Effect of Increasing Number of Samples on PAL

PAL remains competitive as the number of sampled solutions increases from 1 to 40. The comparison uses interpolated baseline solve rates and reports minimal variation across prompt orderings for the math tasks.

  • Sample scaling: PAL outperforms strong baselines for both a single sample and 40 samples with majority voting.Figure 12 shows trends across intermediate sample counts.
  • Sample scaling: PAL remains competitive throughout sample counts from 1 to 40, while baseline curves are estimated by logistic interpolation.The interpolated baselines are PaLM, COT, and Minerva.
  • Run variation: Three random prompt orderings produce minimal standard deviation across the math reasoning datasets.The corresponding results are summarized in Table 7.

F. PAL Beyond Benchmarks

PAL-style reasoning is illustrated on user-posted symbolic questions beyond the benchmark evaluations. These examples show how executable programs can preserve object attributes, branch correctly, and perform exact symbolic operations where COT produces incorrect answers.

  • Scope of examples: The paper uses ChatGPT demonstrations to argue that symbolic reasoning is relevant even for tasks that do not initially appear to require programs.These demonstrations are delivered through user utterances rather than the main paper’s in-context-learning setup.
  • ChatGPT examples: In a color-object example, COT reaches a wrong final answer despite a correct reasoning chain, whereas PAL extracts attributes and generates branching code for the correct answer.The comparison is presented in Figure 13.
  • ChatGPT examples: For counting letters in “intriguing,” explicit step-by-step reasoning still yields the wrong answer, while PAL uses a few lines of code to obtain the correct result.The example appears in Figure 14.
  • Token-level analysis: Token-level analysis of 20 COLORED OBJECTS questions finds lower COT confidence for numbers, spatial positions, colors, and object nouns.The reported counts are seven, six, two, and six examples, respectively.
  • Token-level analysis: PAL typically expresses these concepts with confident, reusable list operations and indexing, such as len(objects) and objects[-1].The analysis contrasts PAL’s consistent expressions with context-dependent COT descriptions.

H. Datasets

The paper evaluates PAL across datasets covering mathematical reasoning, everyday objects and concepts, and algorithmic problems, and provides prompts and generated code examples. These materials illustrate PAL’s use of lists, filtering, arithmetic, and calendar operations for structured reasoning.

  • Dataset coverage: The considered datasets include reasoning about everyday objects and concepts, algorithmic problems, and mathematical questions with differing question lengths.GSM8K averages 47 words per question, SINGLEOP 21 words, and other listed datasets approximately 30 words.
  • Mathematical datasets: GSM8K and GSM-HARD analyses report that 16 of 25 manually examined thoughts were identical or nearly identical across datasets.The analysis attributes the larger-number performance reduction primarily to arithmetic failure.
  • Prompt variants: PAL is combined with LEAST-TO-MOST decomposition on GSM8K and SVAMP to use problem reduction alongside Python-runtime arithmetic.The reported experiments use subsets of 500 examples.
  • Prompt examples: A colored-object prompt constructs an ordered list of objects and retrieves the color of the item directly right of the stress ball.The generated code identifies the stress-ball index and accesses the next object’s color.
  • Algorithmic prompts: PAL’s object-counting examples represent target categories in dictionaries or lists and compute counts with sums or len operations.Examples count vegetables and filter crayons from non-pink objects.
  • Illustrative failure modes: PAL is described as handling object ordering, attributes, filtering, state changes, and calendar arithmetic in examples where COT exhibits tracking or date errors.The examples include filtering out Bernard and correctly handling a month boundary.
Loading 2211.10435v2…