Program synthesis

Overview

Program synthesis here means that the model answers a question by writing a program, and the program's output is the answer. The model does not write the answer in prose. The invariant is that the answer comes from running code, so its correctness can be checked against a reference 2112.15594 § Methods. This page currently rests on one paper card.

Variants

Zero-shot program generation

The question goes into a Python docstring with an instruction to write a program. The model is a code-trained engine (Codex, code-davinci-002), and the generated program is run to get the answer. With no examples, it solved 71.1% of 175 course questions and 72.2% of 90 MATH-benchmark questions 2112.15594 § Results. Card: Drori et al., Codex on university maths.

Few-shot retry with retrieved solved examples

Only the questions that failed zero-shot are retried. For each one, the other questions in the same course are ranked by embedding similarity. Up to five solved neighbours, most similar first, are placed before the target question. This raised the course score to 81.1% and the MATH score to 81.1% 2112.15594 § Methods 2112.15594 § Results. In the per-course table, the courses with the lowest zero-shot scores gained most; 6.042 rose from 48% to 68% 2112.15594 § Results.

Explain and generate (side uses)

The same model can explain a program line by line, with a 150-token limit, and can write new questions from a list of 25 solved human questions 2112.15594 § Methods. The authors judged generated questions in a student survey of 15 people. Generated and human questions were rated similarly hard, but human questions were more often identified as human-written 2112.15594 § Results. The question-generation code is not in the release 2112.15594 § Paper vs code.

When to use which

Results come from one model family and one author group. The gains are author-reported, and the MATH set has 90 questions.

Implementation sketch

The core is the same in both variants. The few-shot variant adds one retrieval step before the second call. The code in the release is the reference 2112.15594 § Methods.

# Zero-shot: the question goes in a docstring with a "write a program" cue
# [arxiv:2112.15594 § Methods]
def solve_zero_shot(question, model):
    prompt = make_docstring_prompt(question, 'write a program')
    # Deterministic decoding, temperature 0 and top-p 0  [arxiv:2112.15594 § Implementation Details]
    program = model.complete(prompt, temperature=0, top_p=0)
    # Run in a sandbox; the printed or returned value is the answer
    answer = run_in_sandbox(program)
    return program, answer

# Few-shot retry, only for questions that failed zero-shot  [arxiv:2112.15594 § Methods]
def solve_few_shot(target, pool, solved, embed):
    # Rank same-course questions by cosine similarity of their embeddings
    ranked = sort_by_cosine(embed(target), [q for q in pool if q != target])
    # Keep up to five solved neighbours, most similar first
    shots = [q for q in ranked if solved[q]][:5]
    # Each example is its prompt followed by its program; target goes last
    prefix = ''.join(prompt_of(q) + program_of(q) + '\n\n' for q in shots)
    program = model.complete(prefix + make_docstring_prompt(target))
    return program, run_in_sandbox(program)

Two details matter when porting this. First, solved[q] must come from a checked answer, not from a model. Second, the paper and the release place the examples in the order shown here, so the most similar example sits furthest from the target. The paper does not justify this order 2112.15594 § Pitfalls.

Contradictions

• How "automatic" the labels are. The paper calls the solve rates automatic 2112.15594 § Results. The release expects a person to run each program and enter 1 or 0 in the zero-shot column 2112.15594 § Paper vs code. The few-shot selection depends on those labels.
• GPT-3 chain-of-thought baseline. The paper reports 30.8% on the course set and 42.2% on MATH for GPT-3 with chain-of-thought 2112.15594 § Results. The paper describes few-shot examples before the reasoning phrase 2112.15594 § Implementation Details. The released few-shot code uses one example for every question, solved or not 2112.15594 § Paper vs code. The two descriptions of this baseline do not match.
• Library hints. The paper says package hints, such as SymPy, are added automatically 2112.15594 § Methods. The released zero-shot code defines the hints but uses only the first one 2112.15594 § Paper vs code.
• "Human level". The paper calls the result human level. Its comparison is with typical student performance on the same problem sets, which it does not measure directly 2112.15594 § Results.

Papers

• Drori et al., Codex on university maths: Codex writes a Python program per maths question and runs it. Few-shot retry with same-course solved examples reaches 81.1% on 175 course questions and 90 MATH questions.