PAL: Program-aided Language Models

In plain words

Language models are good at breaking a word problem into steps, but they often get the arithmetic wrong, or they get the steps right and then miscalculate the final number. PAL changes who does the calculating. The model is shown a few solved examples, where each answer is a short Python program with a comment on each line explaining the step. For a new question, the model writes such a program, and an ordinary Python interpreter runs it to produce the answer. The model only has to understand the problem and write the steps; the computer does the sums, counts and date arithmetic. The authors report better scores than chain-of-thought prompting on math word problems and on several puzzle-like tasks, all with the same model and no training.

TL;DR

• PAL is few-shot prompting in which the model writes Python code as its reasoning, with comments in natural language, and the answer comes from running that code §3.
• Author-reported: with Codex (code-davinci-002), it beats chain-of-thought (CoT) prompting on all 13 tasks tested, including +6.4 points on GSM8K (72.0 vs 65.6) and a large gap on GSM-Hard §5.1, §5.2.
• Use it when the task has exact calculation, counting, or state tracking, and when you can run code. It depends on a code-capable model.

Problem

Chain-of-thought prompting makes the model write its reasoning in text, but the model also performs every calculation itself. Large numbers and multi-step arithmetic fail often, and reasoning chains can be correct while the final number is wrong §1. One prior system (Minerva) was fine-tuned on explicit mathematical content instead §1. This paper stays in a few-shot setting and relies on a model pretrained on both natural language and code §1, §4.

Method

Background. Few-shot prompting puts k input-output examples before the test question. Chain-of-thought adds a natural-language rationale to each example §2.

PAL. Each in-context example is a pair (question, t), where t is the reasoning. Here t is a sequence of statements, each either natural language or Python code. No final answer is given in the examples, because the interpreter produces it §3. The steps are as follows.

1. Build the prompt by concatenating the k examples and the new question §3.
2. The LM generates t for the test question: comment lines (#) carry the natural-language steps and ordinary lines carry the code §3 fig. 2.
3. The generated program runs once, after generation, in a standard Python interpreter. The value the program produces is the answer §3.

The paper uses one post-hoc execution per question for the reported results. Interleaved execution, where results are fed back to the model between steps, is described as possible but not used §3.

# PAL for one question  [§3]
# Input:  question (text); examples (k worked Q + program pairs)
# Output: answer, or None if no program produced a result

def pal_answer(question, examples, num_samples=1):
    # Append the new question to the fixed examples  [§3]
    prompt = build_prompt(examples, question)
    # Sample program text; greedy when num_samples is 1  [§4] [§5.1]
    programs = llm_generate(prompt, num_samples=num_samples)
    results = []
    # Run each program in an interpreter with a time limit  [§3]
    for program in programs:
        # Keep the value the program produces; drop programs that raise
        # [code: pal/core/interface.py#L131-L137]
        try:
            value = run_with_time_limit(program, seconds=10)
        except Exception:
            continue
        results.append(value)
    if not results:
        return None
    # Majority vote over the executed answers  [§5.1]
    # [code: pal/core/interface.py#L143-L144]
    return most_common(results)

Prompt design. The authors reuse the prompts of earlier work when those exist. Otherwise they randomly sample 3 to 6 examples and rewrite them in program form §3, "Crafting prompts". Variable names should describe their role, for example a variable for apples in a basket should be named for that §3. Section 6 shows that meaningful names matter.

Majority voting. Sample k=40 programs with nucleus sampling and take the most frequent answer §5.1.

Least-to-most variant. The reduction prompts stay in natural language, and only the solving prompts are rewritten as code app., Least-to-most.

Hyperparameters

Average over three random orderings of the prompt, reported as standard deviation: PAL on GSM8K 72.0 ± 0.16; CoT on GSM8K 65.6 ± 1.10 [app., "Standard Deviations"].

Results

Author-reported. Model: code-davinci-002 with greedy decoding for the main table §4. Baselines: Direct and PaLM-540B and Minerva numbers are taken from earlier papers; CoT with Codex is the authors' run §5.1, table caption.

Math (solve rate, %) §5.1

Majority voting, GSM8K (majority@40) §5.1

Symbolic and algorithmic tasks (solve rate, %) §5.2

Other results.

• Smaller Codex models on GSM8K, PAL vs CoT: cushman-001 21.7 vs 19.1; davinci-001 31.8 vs 26.0; davinci-002 72.0 vs 60.1 §6. The last CoT value differs from the main table (65.6).
• Natural-language models on GSM8K, CoT vs PAL: text-davinci-001 26.5 vs 8.6; text-davinci-002 46.9 vs 65.8; text-davinci-003 65.3 vs 69.8 §6.
• Ablations on GSM8K: Direct 19.7, CoT 65.6, PAL 72.0, PAL with single-line expression 47.8, model computing the answer from the program instead of an interpreter 23.2 app., "more ablations"; §6.
• Ablations of the prompt on GSM8K: CoT 63.1, PAL without meaningful variable names 59.0, PAL without names plus with comments 69.0, PAL 71.8 app., "Alternative Prompts".
• Least-to-most on 500-example subsets: GSM8K 67.2 to 72.8; SVAMP 75.2 to 78.2 app., "Least-to-Most".
• Colored Objects by number of objects: PAL stays between about 93% and 100% across size bins; CoT ranges from about 57% to 91% §5.2.

Paper vs code

Code: luyug/pal at f81ca2a9777f002f98a6b4d0f10b61bd5c8feb02, Apache-2.0. It is linked from the project page and is owned by the first author.

• Few-shot count: the text says 3 to 6 examples per benchmark §3. The math prompt in code has 8 examples math_prompts.py, and the appendix figures show the same 8. The object-counting prompt has 4 examples in code algorithmic_prompt.py; the appendix shows 3.
• Majority voting settings: the paper gives nucleus p = 0.95, k = 40, temperature 0.7 §5.1. The code has no defaults for these; they must be passed as flags, and the defaults are greedy gsm_eval.py.
• Majority rule: the code runs every sampled program, drops those that raise, and returns the most common result. Ties go to the first answer seen interface.py.
• Errors on math: the code scores a question with an exception as 0 with an empty answer gsm_eval.py. The paper does not say how failed programs are counted.
• Answer types: the math script evaluates solution() gsm_eval.py; the colored objects script reads the variable answer colored_object_eval.py. Each prompt must match its reader.
• Stop sequences and token limits are not in the paper; see the Hyperparameters table.
• The paper has no numbered equations or algorithm blocks §3, so the list above is the full set of differences found.

Pitfalls

• Code runs unsandboxed. Generated programs run with exec in the host process runtime.py. The time limit uses SIGALRM interface.py, which works on Unix only and only at whole seconds. Do not run it on untrusted inputs without isolation.
• Runtime globals. The date prompts use datetime and relativedelta, which are not builtins; they exist because DateRuntime injects them runtime.py. Generated code must match the runtime you build.
• Inconsistent GSM-Hard numbers. The text gives PAL 61.5% and CoT 20.1% §5.1. The table and appendix give PAL 61.2 and CoT 23.1 §5.1, app.. Use the table values and treat the gap as about 38 to 41 points.
• Ablation baselines differ from the main table. The ablation figure gives CoT on Colored Objects as 84.4, the main table 86.3 §6 vs §5.2. CoT on GSM8K is 60.1 in the model-scale figure and 65.6 in the main table §6.
• Date claim. The text says PAL's 11.4-point gain holds "over both" CoT Codex, PaLM and LaMDA §5.2. The table gives 11.4 over Codex, 10.9 over PaLM (65.3) and 49.4 over LaMDA-137B (26.8).
• Hidden cost. Each question resends the full few-shot prompt. Majority@40 means 40 completions per question §5.1.
• Dependence on the model. With text-davinci-001, PAL is far below CoT (8.6 vs 26.5) §6. PAL needs a model that can write correct code.
• Naming matters. Replacing meaningful variable names with single letters costs 12.8 points on GSM8K (71.8 to 59.0) app., "Alternative Prompts".
• Interpreter matters. When the model computes the program's result itself, the solve rate drops to 23.2 §6. The gain comes from the interpreter, not from the program text alone.
• Model deprecation. The code README anticipates the Codex API shutdown and points to a ChatGPT beta script for math README.md. The reported numbers are for code-davinci-002.
• Borrowed baselines. The Direct, PaLM, Minerva and LaMDA rows come from earlier papers §5.1, table caption; CoT with Codex is the authors' own run §4. Prompts for the borrowed rows may differ from the PAL prompts.
• Stochastic runs. Main-table PAL numbers come from greedy decoding (temperature 0). Only the std-dev table uses three prompt orderings app..

Lineage

• Builds on: chain-of-thought prompting (Wei et al., 2022), which PAL changes by moving the reasoning steps into code §2, §3.
• Uses: least-to-most prompting (Zhou et al., 2022) as a second prompt family app., "Least-to-Most".
• Compared against: Direct prompting, CoT with Codex, PaLM-540B, Minerva 540B and LaMDA-137B §5.1, §5.2.
• Related ideas: LLMs that call external tools (Related Work section) §7.