Research map / Large language models / Agents, code and math
Learning to Reason via Program Generation, Emulation, and Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains Llama-2 7B/13B to generate Python pseudo-programs and emulate their execution (CoGEX), then uses a search procedure (CoTACS) to find one task-level program per dataset without weight updates.
Problem
Program-based reasoning has worked for algorithmic tasks, but softer reasoning tasks (commonsense, sentiment, moral judgment) are hard to express as executable code; the paper asks how to extend code synthesis to them.
Approach
Train LMs on Pythonic pseudo-programs with undefined leaf functions, have the LM emulate execution (filling in leaf functions from its knowledge) instead of running an interpreter, and search over candidate programs on a training set to pick one general program per task that is reapplied to all instances.
Key results
- CoTACS k=3 with Llama-2 13B (1000 training examples) averages 66.1 across 9 tasks vs 59.4 for 2-shot BM25 Llama-2 13B.
- Llama-2 7B CoTACS k=3 averages 60.8 vs 48.3 for 2-shot BM25 baseline, with gains of about 10-20 points on Sum and Coin flip.
- CoTACS with only 10 training examples already outperforms the 2-shot baselines on average (56.7 for 7B, 61.7 for 13B).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CoTACS with 1000 examples rather than the strongest baseline | CoGEX Llama-2 13B · Coin | accuracy: 63.8 -> 69.5 | Helped |
| Use CoTACS with 1000 examples rather than the strongest baseline | CoGEX Llama-2 13B · Sum | accuracy: 44.5 -> 63.9 | Helped |
| Use CoTACS with 1000 examples rather than the strongest baseline | CoGEX Llama-2 13B · SST | accuracy: 92.4 -> 92.1 | Hurt |
| Use CoTACS with 1000 examples rather than the strongest baseline | CoGEX Llama-2 13B · SVAMP | accuracy: 46.0 -> 50.3 | Helped |
| Retain top 3 programs instead of top 1 (ablation) | CoGEX Llama-2 7B with CoTACS, 1000 examples · Average across 9 tasks | accuracy: 60.0 -> 60.8 | Helped |
| Retain top 3 programs instead of top 1 (ablation) | CoGEX Llama-2 13B with CoTACS, 1000 examples · Average across 9 tasks | accuracy: 65.1 -> 66.1 | Helped |
| Use 10 rather than 1000 search examples (ablation) | CoGEX Llama-2 7B with CoTACS k=1 · Average across 9 tasks | accuracy: 56.7 -> 60.0 | Hurt |
| Use 10 rather than 1000 search examples (ablation) | CoGEX Llama-2 13B with CoTACS k=1 · Average across 9 tasks | accuracy: 61.7 -> 65.1 | Hurt |
| Generate only an NL plan instead of a Python program (ablation) | CoTACS · Coin, SVAMP, and Sum | accuracy | Hurt |
| Generate a separate program per instance instead of searching for reusable task programs (ablation) | CoGEX · Word Sorting and Sum | accuracy | No clear effect |
| Generate a separate program per instance instead of searching for reusable task programs (ablation) | CoGEX · Other evaluated tasks | accuracy | Hurt |
| Use zero-shot chain-of-thought prompting instead of CoTACS (ablation) | Alpaca models · SVAMP, Sum, and Coin | accuracy | Hurt |
Surprising findings
- Few-shot prompting of Alpaca models performed significantly worse than zero-shot, attributed to instruction tuning side effects.
- Code Llama-based CoGEX models were not consistently better than Llama-2 and were worse on coin flip and word sorting for both sizes.
Limitations
- LM emulation of execution is not guaranteed; the model sometimes produces results inconsistent with the emulated code.
- Emulating execution adds overhead compared with running a Python interpreter, and interpreters are preferable for precise algorithmic tasks.
- Results are single runs without error bars.
Experimental setup
Datasets: Alpaca CoLA Emotion SST-2 Coin flip Word Sorting (BIG-bench hard) SVAMP Large number sum CommonsenseQA Social IQa
Benchmarks: CoLA Emotion SST-2 Coin flip Word Sorting SVAMP Sum CommonsenseQA Social IQa AlpacaEval
Metrics: accuracy string-normalized exact match win rate
Baselines: Llama-2 2-shot BM25 in-context learning Alpaca zero-shot CoGEX end-to-end NL plan search zero-shot chain-of-thought Code Llama CoGEX fine-tuning
Builds on: Alpaca LoRA Llama-2 chain-of-thought BM25
Closest papers by meaning
- Once Upon an Input: Reasoning via Per-Instance Program Synthesis (NeurIPS 2025 · similarity 0.88)
- Chain of Code: Reasoning with a Language Model-Augmented Code Emulator (ICML 2024 · similarity 0.87)
- Scaling Code-Assisted Chain-of-Thoughts and Instructions for Model Reasoning (NeurIPS 2025 · similarity 0.87)
- CodeIO: Condensing Reasoning Patterns via Code Input-Output Prediction (ICML 2025 · similarity 0.87)
- BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions (ICLR 2025 · similarity 0.87)
- SemCoder: Training Code Language Models with Comprehensive Semantics Reasoning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.