# Learning to Reason via Program Generation, Emulation, and Search

arXiv: https://arxiv.org/abs/2405.16337 · HTML: https://mlsanity.com/paper/2405.16337/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 37 of its 45 references that are in the map.
- First posted on arXiv 25 May 2024.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 30 of 37)

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Neural Network Acceptability Judgments](https://mlsanity.com/paper/1805.12471/) (2018)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Are NLP Models really able to Solve Simple Math Word Problems?](https://mlsanity.com/paper/2103.07191/) (2021)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Instruction Tuning with GPT-4](https://mlsanity.com/paper/2304.03277/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Active Example Selection for In-Context Learning](https://mlsanity.com/paper/2211.04486/) (2022)
- [Instruction Induction: From Few Examples to Natural Language Task Descriptions](https://mlsanity.com/paper/2205.10782/) (2022)
- [Compositional Exemplars for In-context Learning](https://mlsanity.com/paper/2302.05698/) (2023)
- [GrIPS: Gradient-free, Edit-based Instruction Search for Prompting Large Language Models](https://mlsanity.com/paper/2203.07281/) (2022)
- [Chain of Code: Reasoning with a Language Model-Augmented Code Emulator](https://mlsanity.com/paper/2312.04474/) (2023)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Coverage-based Example Selection for In-Context Learning](https://mlsanity.com/paper/2305.14907/) (2023)
- [Prompt Engineering a Prompt Engineer](https://mlsanity.com/paper/2311.05661/) (2023)
- [Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models](https://mlsanity.com/paper/2404.02575/) (2024)
- [Few-shot Reranking for Multi-hop QA via Language Model Prompting](https://mlsanity.com/paper/2205.12650/) (2022)

## Built on by (most cited first, 10 of 10)

- [A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systems](https://mlsanity.com/paper/2504.09037/) (2025)
- [Code to Think, Think to Code: A Survey on Code-Enhanced Reasoning and Reasoning-Driven Code Intelligence in LLMs](https://mlsanity.com/paper/2502.19411/) (2025)
- [ARM: Adaptive Reasoning Model](https://mlsanity.com/paper/2505.20258/) (2025)
- [Steering Large Language Models between Code Execution and Textual Reasoning](https://mlsanity.com/paper/2410.03524/) (2024)
- [R1-Code-Interpreter: LLMs Reason with Code via Supervised and Multi-stage Reinforcement Learning](https://mlsanity.com/paper/2505.21668/) (2025)
- [TUMIX: Multi-Agent Test-Time Scaling with Tool-Use Mixture](https://mlsanity.com/paper/2510.01279/) (2025)
- [CodeSteer: Symbolic-Augmented Language Models via Code/Text Guidance](https://mlsanity.com/paper/2502.04350/) (2025)
- [Watch Your Steps: Observable and Modular Chains of Thought](https://mlsanity.com/paper/2409.15359/) (2024)
- [Semi-structured LLM Reasoners Can Be Rigorously Audited](https://mlsanity.com/paper/2505.24217/) (2025)
- [Representation-Aligned Auxiliary Supervision for Language Model Adaptation](https://mlsanity.com/paper/2610.04098/) (2026)

## Abstract (arXiv)

Program synthesis with language models (LMs) has unlocked a large set of reasoning abilities; code-tuned LMs have proven adept at generating programs that solve a wide variety of algorithmic symbolic manipulation tasks (e.g. word concatenation). However, not all reasoning tasks are easily expressible as code, e.g. tasks involving commonsense reasoning, moral decision-making, and sarcasm understanding. Our goal is to extend an LM's program synthesis skills to such tasks and evaluate the results via pseudo-programs, namely Python programs where some leaf function calls are left undefined. To that end, we propose, Code Generation and Emulated EXecution (CoGEX). CoGEX works by (1) training LMs to generate pseudo-programs, (2) teaching them to emulate their generated program's execution, including those leaf functions, allowing the LM's knowledge to fill in the execution gaps; and (3) using them to search over many programs to find an optimal one. To adapt the CoGEX model to a new task, we introduce a method for performing program search to find a single program whose pseudo-execution yields optimal performance when applied to all the instances of a given dataset. We show that our approach yields large improvements compared to standard in-context learning approaches on a battery of tasks, both algorithmic and soft reasoning. This result thus demonstrates that code synthesis can be applied to a much broader class of problems than previously considered. Our released dataset, fine-tuned models, and implementation can be found at urlhttps://github.com/nweir127/CoGEX.