Execution Guided Neural Program Synthesis

This direction is merged into another direction: combinatorial search space explosion (program synthesis search complexity). Its last version stays readable and citable here.

Version 1 of 119 papers31 conceptsfrozen 2026-10-04

Traditional program synthesis treats code generation as a translation problem: mapping a natural language description or a set of input-output examples directly into a sequence of code tokens. However, code is notoriously brittle. A single misplaced character can transform a functional program into a syntax error, and two programs that look entirely different might perform the same logical task.

The research direction emerging from recent work suggests that the key to robust synthesis is not to focus on the syntax of the code, but on its execution. By integrating interpreters, simulators, or latent execution models directly into the search process, models can "see" what their partial programs are doing, allowing them to prune dead ends and generalize to complex tasks that syntax-only models fail to solve.

The Problem with Top-Down Syntax

Most Large Language Models (LLMs) generate code top-down, predicting one token at a time. As Augustus Odena, Kensen Shi, and their colleagues point out in BUSTLE, this approach struggles to leverage intermediate results. Because a partial top-down program often contains "holes" or incomplete structures, it cannot be executed. The model is essentially flying blind, unable to verify if its current path is moving the input data closer to the desired output.

Bottom-Up Synthesis and Immediate Feedback

To solve this, researchers have pivoted toward bottom-up synthesis. In systems like BUSTLE and SmBoP (developed by Jonathan Berant and Ohad Rubin), the synthesizer builds small, valid sub-expressions first.

Because every sub-expression is a complete, runnable program, the system can execute it immediately on the provided input examples. This provides a "semantic signal." If a sub-expression produces a value that looks like a useful intermediate step toward the goal, the model prioritizes it. This mimics how human programmers often experiment with small snippets in a console to see if they work before integrating them into a larger script.

Thinking in Execution States

The most significant shift in this field is the move from predicting code to predicting execution states. In Write, Execute, Assess, Kevin Ellis, Maxwell Nye, and their team demonstrate a system that uses a REPL (Read-Eval-Print Loop). The model writes a line of code, executes it, observes the new state of the variables, and then decides what to write next.

This approach makes the search process far more resilient. As Nye et al. argue in Representing Partial Programs with Blended Abstract Semantics, training a policy on the semantic states of programs—rather than just their text—allows the synthesizer to recognize when two different pieces of code achieve the same goal.

Decomposition via Subgoals

For complex tasks, even a REPL isn't enough if the model doesn't know where it's going. Kensen Shi and Charles Sutton introduced ExeDec, which forces the model to predict the intermediate execution state (a subgoal) before it ever writes the code to reach it.

By decomposing a problem into a sequence of data transformations, the model achieves better "compositional generalization." It might not have seen a specific combination of operations before, but because it can reason about how the data should look at each step, it can bridge the gap between known concepts. This suggests that the "secret sauce" of synthesis is tracking the semantic impact of code rather than just its syntactic structure.

Synthesis Without Interpreters

A major hurdle for execution-guided synthesis is that many languages (like C) are difficult to execute incrementally or require complex environments. Xinyun Chen and Dawn Song addressed this with LaSynth, which learns to approximate execution in a latent space.

Instead of a formal symbolic interpreter, LaSynth uses a neural network to "imagine" what the data would look like after a partial program runs. This allows the model to benefit from execution-style guidance even when a real interpreter is unavailable, effectively learning the semantics of the language through observation.

Summary of Intuition

The core insight of this research area is that the execution space is more structured and less noisy than the syntax space. By grounding program generation in the concrete reality of data transformations—whether through real interpreters (MORPHEUS), REPLs (Write, Execute, Assess), or latent simulators (LaSynth)—we move from "guessing tokens" to "solving transformations."

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_execution_guided_neural_program_synthesi_11e6374d,
  title = {Execution Guided Neural Program Synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/execution-guided-neural-program-synthesis/rdr_11e6374da8cc4cbd8d31f81a6f90762a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_execution_guided_neural_program_synthesi_11e6374d_v1,
  title = {Execution Guided Neural Program Synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/execution-guided-neural-program-synthesis/rdr_11e6374da8cc4cbd8d31f81a6f90762a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}