---
kind: concept
slug: program-synthesis
title: Program synthesis
summary: >-
  Ask a code-trained model to write a short program per question, run it and report its output. Retrying failures with up to five solved same-course examples, picked by embedding similarity, raised accuracy from 71.1% to 81.1% on 175 course questions (author-reported). Needs a sandbox and checkable answers. The paper's "automatic" labels were typed in by a person.
tags: [code-generation, few-shot, prompting, mathematical-reasoning]
papers: ["2112.15594"]
related: [few-shot-example-selection, chain-of-thought-prompting, in-context-learning, code-completion, program-repair, tool-use, text-embedding, neural-symbolic-integration]
status: draft
updated_at: 2026-11-09
---

## 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 [arxiv: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
[arxiv:2112.15594 § Results]. Card: [Drori et al., Codex on university maths](/papers/2112.15594).

### 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%
[arxiv:2112.15594 § Methods] [arxiv: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% [arxiv: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
[arxiv: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
[arxiv:2112.15594 § Results]. The question-generation code is not in the
release [arxiv:2112.15594 § Paper vs code].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Questions have a checkable answer, and a sandbox can run the code | Zero-shot program generation | Needs no labelled examples. The paper reports 71.1% on its course set [arxiv:2112.15594 § Results]. |
| You have solved examples from the same domain and can afford a second call for each failure | Few-shot retry with retrieved examples | Adds about 9 to 10 points on the paper's course and MATH sets [arxiv:2112.15594 § Results]. The examples come from the same pool being tested, so the gain is not held-out [arxiv:2112.15594 § Pitfalls]. |
| Questions include images, proofs or computationally intractable problems | Not stated | The paper names these as out of reach [arxiv:2112.15594 § Results]. It gives no alternative. |
| The task needs a stronger guarantee than a single run gives | Not stated | The paper runs each question once at temperature 0 and top-p 0 [arxiv:2112.15594 § Implementation Details]. It reports no variance across runs. |

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
[arxiv:2112.15594 § Methods].

```pseudocode
# 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
[arxiv:2112.15594 § Pitfalls].

## Contradictions

- **How "automatic" the labels are.** The paper calls the solve rates
  automatic [arxiv:2112.15594 § Results]. The release expects a person to run
  each program and enter 1 or 0 in the zero-shot column
  [arxiv: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
  [arxiv:2112.15594 § Results]. The paper describes few-shot examples before
  the reasoning phrase [arxiv:2112.15594 § Implementation Details]. The
  released few-shot code uses one example for every question, solved or not
  [arxiv: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 [arxiv:2112.15594 § Methods]. The released zero-shot code
  defines the hints but uses only the first one [arxiv: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 [arxiv:2112.15594 § Results].

## Papers

- [Drori et al., Codex on university maths](/papers/2112.15594): 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.