# Latent Execution for Neural Program Synthesis

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 61 references that are in the map.
- First posted on arXiv 29 Jun 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [SPoC: Search-based Pseudocode to Code](https://mlsanity.com/paper/1906.04908/) (2019)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Learning to Infer and Execute 3D Shape Programs](https://mlsanity.com/paper/1901.02875/) (2019)
- [A Probabilistic End-To-End Task-Oriented Dialog Model with Latent Belief States towards Semi-Supervised Learning](https://mlsanity.com/paper/2009.08115/) (2020)
- [Learning to Infer Program Sketches](https://mlsanity.com/paper/1902.06349/) (2019)
- [Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimation using Deep Neural Networks](https://mlsanity.com/paper/1808.07412/) (2018)
- [Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples](https://mlsanity.com/paper/1804.01186/) (2018)
- [Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis](https://mlsanity.com/paper/2007.08095/) (2020)
- [Neural Execution Engines: Learning to Execute Subroutines](https://mlsanity.com/paper/2006.08084/) (2020)
- [Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks](https://mlsanity.com/paper/2010.12621/) (2020)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Automatic Program Synthesis of Long Programs with a Learned Garbage Collector](https://mlsanity.com/paper/1809.04682/) (2018)
- [Neural Program Meta-Induction](https://mlsanity.com/paper/1710.04157/) (2017)
- [Prospection: Interpretable Plans From Language By Predicting the Future](https://mlsanity.com/paper/1903.08309/) (2019)

## Built on by (most cited first, 30 of 35)

- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Large Language Models for Software Engineering: A Systematic Literature Review](https://mlsanity.com/paper/2308.10620/) (2023)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [LEVER: Learning to Verify Language-to-Code Generation with Execution](https://mlsanity.com/paper/2302.08468/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Execution-based Code Generation using Deep Reinforcement Learning](https://mlsanity.com/paper/2301.13816/) (2023)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutions](https://mlsanity.com/paper/2205.14318/) (2022)
- [Fault-Aware Neural Code Rankers](https://mlsanity.com/paper/2206.03865/) (2022)
- [AST-T5: Structure-Aware Pretraining for Code Generation and Understanding](https://mlsanity.com/paper/2401.03003/) (2024)
- [Fully Autonomous Programming with Large Language Models](https://mlsanity.com/paper/2304.10423/) (2023)
- [Tensor Program Optimization with Probabilistic Programs](https://mlsanity.com/paper/2205.13603/) (2022)
- [Emergent Representations of Program Semantics in Language Models Trained on Programs](https://mlsanity.com/paper/2305.11169/) (2023)
- [Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation](https://mlsanity.com/paper/2305.00909/) (2023)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [B-Coder: Value-Based Deep Reinforcement Learning for Program Synthesis](https://mlsanity.com/paper/2310.03173/) (2023)
- [Synthesizing Programmatic Reinforcement Learning Policies with Large Language Model Guided Search](https://mlsanity.com/paper/2405.16450/) (2024)
- [Towards Efficient Neurally-Guided Program Induction for ARC-AGI](https://mlsanity.com/paper/2411.17708/) (2024)
- [Grounding Data Science Code Generation with Input-Output Specifications](https://mlsanity.com/paper/2402.08073/) (2024)
- [E-MAPP: Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance](https://mlsanity.com/paper/2212.02064/) (2022)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [Natural Language Commanding via Program Synthesis](https://mlsanity.com/paper/2306.03460/) (2023)
- [Gradient-Based Program Repair: Fixing Bugs in Continuous Program Spaces](https://mlsanity.com/paper/2505.17703/) (2025)
- [Contextualized Data-Wrangling Code Generation in Computational Notebooks](https://mlsanity.com/paper/2409.13551/) (2024)
- [Fully Autonomous Programming using Iterative Multi-Agent Debugging with Large Language Models](https://mlsanity.com/paper/2503.07693/) (2025)
- [Pronunciation-Lexicon Free Training for Phoneme-based Crosslingual ASR via Joint Stochastic Approximation](https://mlsanity.com/paper/2507.06249/) (2025)

## Abstract (arXiv)

Program synthesis from input-output (IO) examples has been a long-standing challenge. While recent works demonstrated limited success on domain-specific languages (DSL), it remains highly challenging to apply them to real-world programming languages, such as C. Due to complicated syntax and token variation, there are three major challenges: (1) unlike many DSLs, programs in languages like C need to compile first and are not executed via interpreters; (2) the program search space grows exponentially when the syntax and semantics of the programming language become more complex; and (3) collecting a large-scale dataset of real-world programs is non-trivial. As a first step to address these challenges, we propose LaSynth and show its efficacy in a restricted-C domain. More specifically, LaSynth learns the latent representation to approximate the execution of partially generated programs, even if they are incomplete in syntax (addressing (1)). The learned execution significantly improves the performance of next token prediction over existing approaches, facilitating search (addressing (2)). Finally, once trained with randomly generated ground-truth programs and their IO pairs, LaSynth can synthesize more concise programs that resemble human-written code. Furthermore, retraining our model with these synthesized programs yields better performance with fewer samples for both Karel and C program synthesis, indicating the promise of leveraging the learned program synthesizer to improve the dataset quality for input-output program synthesis (addressing (3)). When evaluating on whether the program execution outputs match the IO pairs, LaSynth achieves 55.2% accuracy on generating simple C code with tens of tokens including loops and branches, outperforming existing approaches without executors by around 20%.