# Learning to Infer Program Sketches

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2019.

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

- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [Learning Performance-Improving Code Edits](https://mlsanity.com/paper/2302.07867/) (2023)
- [Execution-based Code Generation using Deep Reinforcement Learning](https://mlsanity.com/paper/2301.13816/) (2023)
- [CERT: Continual Pre-Training on Sketches for Library-Oriented Code Generation](https://mlsanity.com/paper/2206.06888/) (2022)
- [Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations](https://mlsanity.com/paper/2104.07478/) (2021)
- [LILO: Learning Interpretable Libraries by Compressing and Documenting Code](https://mlsanity.com/paper/2310.19791/) (2023)
- [Compilable Neural Code Generation with Compiler Feedback](https://mlsanity.com/paper/2203.05132/) (2022)
- [Leveraging Language to Learn Program Abstractions and Search Heuristics](https://mlsanity.com/paper/2106.11053/) (2021)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [A Survey on Neural-symbolic Learning Systems](https://mlsanity.com/paper/2111.08164/) (2021)
- [Communicating Natural Programs to Humans and Machines](https://mlsanity.com/paper/2106.07824/) (2021)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation](https://mlsanity.com/paper/2305.00909/) (2023)
- [Learning to Complete Code with Sketches](https://mlsanity.com/paper/2106.10158/) (2021)
- [Neural-guided, Bidirectional Program Search for Abstraction and Reasoning](https://mlsanity.com/paper/2110.11536/) (2021)
- [Deep Learning for Code Intelligence: Survey, Benchmark and Toolkit](https://mlsanity.com/paper/2401.00288/) (2023)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis](https://mlsanity.com/paper/2205.13728/) (2022)
- [What can we Learn Even From the Weakest? Learning Sketches for Programmatic Strategies](https://mlsanity.com/paper/2203.11912/) (2022)
- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [Toward Code Generation: A Survey and Lessons from Semantic Parsing](https://mlsanity.com/paper/2105.03317/) (2021)
- [Learning to Combine Per-Example Solutions for Neural Program Synthesis](https://mlsanity.com/paper/2106.07175/) (2021)
- [Compositional Generalization and Decomposition in Neural Program Synthesis](https://mlsanity.com/paper/2204.03758/) (2022)
- [LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas](https://mlsanity.com/paper/2306.02049/) (2023)
- [Learning of Generalizable and Interpretable Knowledge in Grid-Based Reinforcement Learning Environments](https://mlsanity.com/paper/2309.03651/) (2023)
- [Learning to Improve Code Efficiency](https://mlsanity.com/paper/2208.05297/) (2022)
- [On Adversarial Robustness of Synthetic Code Generation](https://mlsanity.com/paper/2106.11629/) (2021)
- [Neural Machine Translation for Code Generation](https://mlsanity.com/paper/2305.13504/) (2023)
- [Guess & Sketch: Language Model Guided Transpilation](https://mlsanity.com/paper/2309.14396/) (2023)

## Abstract (arXiv)

Our goal is to build systems which write code automatically from the kinds of specifications humans can most easily provide, such as examples and natural language instruction. The key idea of this work is that a flexible combination of pattern recognition and explicit reasoning can be used to solve these complex programming problems. We propose a method for dynamically integrating these types of information. Our novel intermediate representation and training algorithm allow a program synthesis system to learn, without direct supervision, when to rely on pattern recognition and when to perform symbolic search. Our model matches the memorization and generalization performance of neural synthesis and symbolic search, respectively, and achieves state-of-the-art performance on a dataset of simple English description-to-code programming problems.