Skip to main content

Program-Aided Language Models (PAL): Code Reasoning

Program-Aided Language Models (PAL) split reasoning into two stages: the LLM generates a program (usually Python) that logically solves a problem, and a code interpreter executes it to produce a guaranteed-correct answer. This approach addresses a core LLM weakness—they are text predictors, not calculators—and improves accuracy on math, logic, and symbolic reasoning tasks by 40–60% versus pure language-based reasoning.

Why Language Alone Isn't Enough for Math​

Large language models excel at pattern completion and linguistic reasoning but fail on arithmetic and multi-step calculations. A model may "know" that 15 × 17 = 255 because similar arithmetic appears in training data, but it is not computing multiplication through logical rules—it is pattern-matching. This leads to subtle errors:

  • Arithmetic mistakes: Models regularly make off-by-one errors or lose track of intermediate results
  • Logical inconsistency: The model might commit to a reasoning path, then contradict itself mid-response
  • No verification: Unlike code, text output has no way to check correctness automatically

PAL solves this by converting the reasoning task (which the LLM does well) into a programming task (which a deterministic interpreter does perfectly).

The PAL Framework: Two-Stage Reasoning​

Stage 1: Language → Code: The LLM reads a natural-language problem and generates a program (Python, pseudocode, or similar) that solves it. The prompt includes examples showing how to structure reasoning as code.

Stage 2: Code → Answer: A code interpreter (Python runtime, sandbox environment) executes the generated program and returns the output—the final, correct answer.

Example: Bakery Pack Problem​

Problem: "A bakery sells cookies in packs of 3 or 5. How many packs of each type should a customer buy to get exactly 19 cookies?"

PAL Prompt (Few-Shot):

# Example:
# Q: I have 10 apples and eat 3, then buy 5 more. How many apples do I have?
# A:
apples = 10
apples = apples - 3
apples = apples + 5
print(apples)

---

# Q: A bakery sells cookies in packs of 3 or 5. How many packs of each should be bought for exactly 19 cookies?
# A:

LLM Output (Generated Code):

# Try different combinations of packs
for packs_of_3 in range(7):  # Max 6 packs of 3 is 18 cookies
    for packs_of_5 in range(4):  # Max 3 packs of 5 is 15 cookies
        total = 3 * packs_of_3 + 5 * packs_of_5
        if total == 19:
            print(f"Packs of 3: {packs_of_3}, Packs of 5: {packs_of_5}")

Interpreter Output:

Packs of 3: 3, Packs of 5: 2

Verification: 3 × 3 + 5 × 2 = 9 + 10 = 19. The answer is guaranteed correct because the interpreter executed deterministic logic, not probabilistic text generation.

Core Advantages of PAL​

Accuracy: Math problems solved with PAL show 40–60% higher accuracy than language-only approaches. On competition math (AIME), chain-of-thought reasoning achieves ~10% accuracy; PAL achieves 30%+ (Gao et al., 2023).

Transparency: The generated code is auditable—you can read it to understand exactly how the LLM decomposed the problem and can spot errors or inefficiencies.

Verification: Code has deterministic output; if the program runs without error, the arithmetic is correct. This eliminates hallucination on calculations.

Composability: Generated code can be integrated into larger systems—pipe one program's output into the next, call external APIs, query databases.

When to Use PAL​

PAL excels on problems that are:

  • Quantitative: Involve numbers, calculations, or measurable quantities (not subjective judgment)
  • Symbolic: Have clear logical rules or constraints (algebra, logic puzzles, optimization)
  • Deterministic: Have a single correct answer (not creative or exploratory tasks)
  • Expressible in Code: Can be written as a program in Python or pseudocode

Ideal use cases:

  • Math word problems and algebra
  • Financial calculations (interest, tax, compound growth)
  • Combinatorial problems (permutations, scheduling)
  • Physics problems with equations
  • Logic puzzles and constraint satisfaction
  • Data manipulation (sorting, filtering, aggregation)

Poor fits:

  • Open-ended creative writing
  • Subjective judgment (which design is better?)
  • Tasks requiring domain knowledge beyond code expressibility
  • Real-time interaction (code generation adds latency)

Implementation Patterns​

Basic PAL: Single Problem​

# Solve this step by step by writing Python code.

# Problem: {USER_PROBLEM}

# Python solution:

The LLM generates code; you execute it and return the output.

Instrumented PAL: Debugging​

Add print statements and comments to understand the model's reasoning:

# Solve this problem step by step. Add comments explaining each step.
# Use print() to show intermediate results so we can verify the logic.

# Problem: {USER_PROBLEM}

# Python solution:

Output includes both the final answer and intermediate debugging output, helping you spot reasoning errors.

PAL with Verification​

Generate code, execute it, then ask the LLM to verify the result:

# Your generated code returned: {RESULT}

# Does this answer make sense? Show your verification.

This catch errors in code generation (off-by-one errors, wrong loop bounds).

Performance Data​

On MATH dataset (challenging high-school competition math):

MethodAccuracy
GPT-3.5 language-only~3%
Chain-of-thought (language)~10%
PAL (code generation)~28%
PAL + verification loop~35%

On GSM8K (grade school math):

MethodAccuracy
Language-only~50%
PAL~90%

Code execution is not a silver bullet (LLMs still make reasoning mistakes in code generation), but it eliminates arithmetic errors and provides transparent, auditable logic.

Limitations and Failure Modes​

Code Generation Errors: The LLM might generate syntactically correct but logically flawed code (wrong algorithm, misunderstood constraints). Verification and human review catch these.

Latency: Generating and executing code is slower than single-pass text generation. Multi-step problems may require 5–15 seconds per query.

Safety Concerns: Executing untrusted code is risky. Always use sandboxed execution environments (AWS Lambda, isolated containers); never run generated code directly.

Scope Limitations: Code is most useful for well-defined, quantifiable problems. Fuzzy or subjective tasks (like writing) don't fit the PAL framework.

Advanced: Chaining Code Generation​

Combine PAL with prompt chaining: generate code for Step 1, run it, then feed its output into Step 2's code generation.

Step 1 LLM: "Here's a problem with data [DATA]. Generate Python to parse it."
→ Run Step 1 code → Output: parsed_result

Step 2 LLM: "Given parsed_result, generate code to solve [PROBLEM]."
→ Run Step 2 code → Final answer

This approach handles complex workflows requiring intermediate data transformation.

Key Takeaways​

  • PAL separates reasoning (LLM strength) from calculation (code strength)
  • Improves accuracy on math/logic tasks by 40–60% compared to language-only approaches
  • Generated code is transparent and auditable, eliminating hidden errors
  • Most effective on quantitative, deterministic, symbolically-expressible problems
  • Requires safe code execution environments (sandboxed interpreters)
  • Complements chain-of-thought and other reasoning patterns

Frequently Asked Questions​

Can PAL work with programming languages other than Python?​

Yes. Python is most common (safe, readable, widespread), but PAL works with any Turing-complete language that can be executed in a sandbox (JavaScript, Go, Rust). The LLM needs examples in your target language in the few-shot prompt.

What if the model generates incorrect code?​

This happens. The generated code might be syntactically valid but logically wrong (wrong algorithm, misunderstood problem, incorrect boundary conditions). Mitigation: run the code on test cases you verify manually; add a verification step where the LLM explains the answer; use an interpreter that provides detailed error messages to catch bugs.

Does PAL add significant latency?​

Yes. Code generation + execution typically adds 2–5 seconds per query (depending on code complexity). For interactive applications, this is noticeable. For batch/async tasks (report generation, data processing), it's acceptable for the accuracy gain.

How do I ensure the generated code is safe to execute?​

Use isolated sandboxes: AWS Lambda, Docker containers, or PyO3 interpreters with restricted permissions. Never execute generated code with full system access. Set execution timeouts (kill code that runs longer than 10 seconds) to prevent infinite loops.

Is PAL different from tool-use or function-calling?​

Related but distinct. Tool-use/function-calling lets the LLM call external APIs (search, calculator, database). PAL generates and runs its own code. You can combine them: PAL generates code that calls external tools.

When should I use PAL instead of asking the LLM for a text explanation?​

Use PAL when: the answer must be correct (not approximate or exploratory), the problem is quantitative, and you can verify code execution. Use text for subjective judgment, creative tasks, or when transparency of reasoning is more important than computational precision.

Further Reading​