---
title: "Learning to Infer Program Sketches — paper by Nye et al. (2019)"
description: "The authors present SketchAdapt. 28 references, cited by 25 papers here. Among them: 28."
authors: ["Maxwell Nye", "Luke Hewitt", "Joshua Tenenbaum", "Armando Solar-Lezama"]
year: 2019
venue: "arXiv:1902.06349"
source: "https://arxiv.org/abs/1902.06349"
doi: "10.48550/arxiv.1902.06349"
arxiv: "1902.06349"
licence: "arXiv — non-exclusive licence to distribute"
licence_url: "https://arxiv.org/licenses/nonexclusive-distrib/1.0/license.html"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/nye-2019-learning-infer-program-sketches/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/nye-2019-learning-infer-program-sketches/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/page/6/) / Learning to Infer Program Sketches

# Learning to Infer Program Sketches

**Authors:** [Maxwell Nye](https://md.research.elamur.ai/free/en/authors/maxwell-nye/), [Luke Hewitt](https://md.research.elamur.ai/free/en/authors/luke-hewitt/), [Joshua Tenenbaum](https://md.research.elamur.ai/free/en/authors/joshua-b-tenenbaum/) and [Armando Solar-Lezama](https://md.research.elamur.ai/free/en/authors/armando-solar-lezama/) · **Year:** 2019 · **Venue:** arXiv:1902.06349 · **Licence:** [arXiv — non-exclusive licence to distribute](https://arxiv.org/licenses/nonexclusive-distrib/1.0/license.html)

**Links:** [Publisher's page](https://arxiv.org/abs/1902.06349) · [PDF](https://arxiv.org/pdf/1902.06349) · [DOI 10.48550/arxiv.1902.06349](https://doi.org/10.48550/arxiv.1902.06349) · [arXiv 1902.06349](https://arxiv.org/abs/1902.06349) · [OpenAlex](https://openalex.org/W2913613828)

**Citations:** 28 citations (OpenAlex, 2026-10-14) · [25](https://md.research.elamur.ai/free/en/papers/nye-2019-learning-infer-program-sketches/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
The paper addresses program synthesis from specifications that people find easy to give, namely input-output examples and natural-language descriptions. Earlier neuro-symbolic systems used fixed, hand-designed sketch grammars. In those systems, a neural network predicts a partial program and a symbolic search completes it, but the network cannot adjust how much of the program it fills in. The authors present SketchAdapt. It pairs a recurrent sequence-to-sequence sketch generator with an enumerative synthesizer. A sketch is any valid DSL program in which some subtrees are replaced by a \<HOLE> token. Training is self-supervised. In each step a search budget is sampled at random, and the generator learns to favour sketches that the synthesizer can complete within that budget. As a result, the model writes detailed sketches for familiar tasks and leaves more holes for unfamiliar ones. The system was evaluated on list processing, string editing and the AlgoLisp English-to-code dataset. It reached state-of-the-art results on AlgoLisp and generalized better than a pure RNN when training data was scarce or concepts were unseen. This supports combining learned pattern recognition with explicit search.

## Key points
- On AlgoLisp, with a 300-second limit per task and beam size 10, SketchAdapt reached 90.0% test accuracy on the full dataset and 95.8% on the filtered set. The previous systems SAPS and Seq2Tree+Search scored 85.2% and 85.8% on the full dataset.
- A "Generator only" RNN baseline was nearly as accurate as SketchAdapt on the full data (88.6% test). A "Synthesizer only" baseline reached only 7.3%. With smaller training subsets, SketchAdapt clearly outperformed the RNN baseline.
- In a held-out-concept test, the models were trained on 8000 programs that never contained the 'odd' lambda (x%2==1). SketchAdapt then solved 29.8% of the 635 'odd' test tasks and 34.4% of the 638 'even' tasks. According to the authors, the RNN baseline largely failed on 'odd'.
- Using only input-output examples on AlgoLisp gave just 8.3% test accuracy. The natural-language descriptions are therefore essential in this domain.
- The paper was published at ICML 2019 (PMLR 97) by authors from MIT and the MIT-IBM Watson AI Lab.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 274 works · 82,013 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🗄️ Information Systems](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) · 1,888 works · [🖥️ Computer Science Applications](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-science-applications/) · 184 works

🧭 Topics (1): [💻 Code & programming languages](https://md.research.elamur.ai/free/en/topics/code-and-programming/) · 194 works

## Cite

Cite as: Maxwell Nye, Luke Hewitt, Joshua Tenenbaum and Armando Solar-Lezama. 2019. Learning to Infer Program Sketches. arXiv:1902.06349.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{nye2019learning,
  title = {{Learning to Infer Program Sketches}},
  author = {Maxwell Nye, Luke Hewitt, Joshua Tenenbaum and Armando Solar-Lezama},
  year = {2019},
  doi = {10.48550/arxiv.1902.06349},
  eprint = {1902.06349},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1902.06349}
}
```

- [← previous Speech act attenuation in the history of English: The case of apologies](https://md.research.elamur.ai/free/en/papers/jucker-2019-speech-act-attenuation-history-english/)
- [next → Lost in Evaluation: Misleading Benchmarks for Bilingual Dictionary Induction](https://md.research.elamur.ai/free/en/papers/kementchedjhieva-2019-lost-in-evaluation/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/page/6/)

## References

28 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Alur, R., Fisman, D., Singh, R., and Solar-Lezama, A. Sygus-comp 2016: Results and analysis. arXiv preprint arXiv:1611.07627, 2016. — [arXiv:1611.07627](https://arxiv.org/abs/1611.07627) [find](https://scholar.google.com/scholar?q=Alur%2C+R%2E%2C+Fisman%2C+D%2E%2C+Singh%2C+R%2E%2C+and+Solar%2DLezama%2C+A%2E+Sygus%2Dcomp+2016%3A+Results+and+analysis%2E+arXiv+preprint+arXiv%3A1611%2E07627%2C+2016%2E+%E2%80%94+%5BarXiv%3A1611%2E07627%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1611%2E07627%29)
2. Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., and Tarlow, D. Deepcoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016. [find](https://scholar.google.com/scholar?q=Balog%2C+M%2E%2C+Gaunt%2C+A%2E+L%2E%2C+Brockschmidt%2C+M%2E%2C+Nowozin%2C+S%2E%2C+and+Tarlow%2C+D%2E+Deepcoder%3A+Learning+to+write+programs%2E+arXiv+preprint+arXiv%3A1611%2E01989%2C+2016%2E)
3. Bednarek, J., Piaskowski, K., and Krawiec, K. Ain’t nobody got time for coding: Structure-aware program synthesis from natural language. arXiv preprint arXiv:1810.09717, 2018. — [arXiv:1810.09717](https://arxiv.org/abs/1810.09717) [find](https://scholar.google.com/scholar?q=Bednarek%2C+J%2E%2C+Piaskowski%2C+K%2E%2C+and+Krawiec%2C+K%2E+Ain%E2%80%99t+nobody+got+time+for+coding%3A+Structure%2Daware+program+synthesis+from+natural+language%2E+arXiv+preprint+arXiv%3A1810%2E09717%2C+2018%2E+%E2%80%94+%5BarXiv%3A1810%2E09717%5D%28htt)
4. Bodik, R., Chandra, S., Galenson, J., Kimelman, D., Tung, N., Barman, S., and Rodarmor, C. Programming with angelic nondeterminism. In ACM Sigplan Notices, volume 45, pp. 339–352. ACM, 2010. [find](https://scholar.google.com/scholar?q=Bodik%2C+R%2E%2C+Chandra%2C+S%2E%2C+Galenson%2C+J%2E%2C+Kimelman%2C+D%2E%2C+Tung%2C+N%2E%2C+Barman%2C+S%2E%2C+and+Rodarmor%2C+C%2E+Programming+with+angelic+nondeterminism%2E+In+ACM+Sigplan+Notices%2C+volume+45%2C+pp%2E+339%E2%80%93352%2E+ACM%2C+2010%2E)
5. Bošnjak, M., Rocktäschel, T., Naradowsky, J., and Riedel, S. [Programming with a differentiable forth interpreter](https://md.research.elamur.ai/free/en/papers/bosnjak-2016-programming-differentiable-forth-interpreter/). In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 547–556. JMLR. org, 2017.
6. Bunel, R., Hausknecht, M., Devlin, J., Singh, R., and Kohli, P. [Leveraging grammar and reinforcement learning for neural program synthesis](https://md.research.elamur.ai/free/en/papers/bunel-2018-leveraging-grammar-reinforcement-learning-neural/). arXiv preprint arXiv:1805.04276, 2018.
7. Chen, X., Liu, C., and Song, D. Towards synthesizing complex programs from input-output examples. arXiv preprint arXiv:1706.01284, 2017. [find](https://scholar.google.com/scholar?q=Chen%2C+X%2E%2C+Liu%2C+C%2E%2C+and+Song%2C+D%2E+Towards+synthesizing+complex+programs+from+input%2Doutput+examples%2E+arXiv+preprint+arXiv%3A1706%2E01284%2C+2017%2E)
8. Dechter, E., Malmaud, J., Adams, R. P., and Tenenbaum, J. B. Bootstrap learning via modular concept discovery. In IJCAI, pp. 1302–1309, 2013. [find](https://scholar.google.com/scholar?q=Dechter%2C+E%2E%2C+Malmaud%2C+J%2E%2C+Adams%2C+R%2E+P%2E%2C+and+Tenenbaum%2C+J%2E+B%2E+Bootstrap+learning+via+modular+concept+discovery%2E+In+IJCAI%2C+pp%2E+1302%E2%80%931309%2C+2013%2E)
9. Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed, A.-r., and Kohli, P. Robustfill: Neural program learning under noisy i/o. arXiv preprint arXiv:1703.07469, 2017. [find](https://scholar.google.com/scholar?q=Devlin%2C+J%2E%2C+Uesato%2C+J%2E%2C+Bhupatiraju%2C+S%2E%2C+Singh%2C+R%2E%2C+Mohamed%2C+A%2E%2Dr%2E%2C+and+Kohli%2C+P%2E+Robustfill%3A+Neural+program+learning+under+noisy+i%2Fo%2E+arXiv+preprint+arXiv%3A1703%2E07469%2C+2017%2E)
10. Dong, L. and Lapata, M. Coarse-to-fine decoding for neural semantic parsing. arXiv preprint arXiv:1805.04793, 2018. [find](https://scholar.google.com/scholar?q=Dong%2C+L%2E+and+Lapata%2C+M%2E+Coarse%2Dto%2Dfine+decoding+for+neural+semantic+parsing%2E+arXiv+preprint+arXiv%3A1805%2E04793%2C+2018%2E)
11. Ellis, K., Morales, L., Sablé-Meyer, M., Solar-Lezama, A., and Tenenbaum, J. Learning libraries of subroutines for neurally–guided bayesian program learning. NIPS, 2018. [find](https://scholar.google.com/scholar?q=Ellis%2C+K%2E%2C+Morales%2C+L%2E%2C+Sable%CC%81%2DMeyer%2C+M%2E%2C+Solar%2DLezama%2C+A%2E%2C+and+Tenenbaum%2C+J%2E+Learning+libraries+of+subroutines+for+neurally%E2%80%93guided+bayesian+program+learning%2E+NIPS%2C+2018%2E)
12. Feser, J. K., Chaudhuri, S., and Dillig, I. Synthesizing data structure transformations from input-output examples. In ACM SIGPLAN Notices, volume 50, pp. 229–239. ACM, 2015. [find](https://scholar.google.com/scholar?q=Feser%2C+J%2E+K%2E%2C+Chaudhuri%2C+S%2E%2C+and+Dillig%2C+I%2E+Synthesizing+data+structure+transformations+from+input%2Doutput+examples%2E+In+ACM+SIGPLAN+Notices%2C+volume+50%2C+pp%2E+229%E2%80%93239%2E+ACM%2C+2015%2E)
13. Gulwani, S. [Automating string processing in spreadsheets using input-output examples](https://md.research.elamur.ai/free/en/papers/gulwani-2011-automating-string-processing-spreadsheets-input/). In ACM SIGPLAN Notices, volume 46, pp. 317–330. ACM, 2011.
14. Kalyan, A., Mohta, A., Polozov, O., Batra, D., Jain, P., and Gulwani, S. Neural-guided deductive search for real-time program synthesis from examples. 2018. [find](https://scholar.google.com/scholar?q=Kalyan%2C+A%2E%2C+Mohta%2C+A%2E%2C+Polozov%2C+O%2E%2C+Batra%2C+D%2E%2C+Jain%2C+P%2E%2C+and+Gulwani%2C+S%2E+Neural%2Dguided+deductive+search+for+real%2Dtime+program+synthesis+from+examples%2E+2018%2E)
15. Kingma, D. and Ba, J. [Adam: A method for stochastic optimization](https://md.research.elamur.ai/free/en/papers/kingma-2014-adam-method-stochastic-optimization/). arXiv preprint arXiv:1412.6980, 2014.
16. Lake, B. M., Salakhutdinov, R., and Tenenbaum, J. B. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338, 2015. [find](https://scholar.google.com/scholar?q=Lake%2C+B%2E+M%2E%2C+Salakhutdinov%2C+R%2E%2C+and+Tenenbaum%2C+J%2E+B%2E+Human%2Dlevel+concept+learning+through+probabilistic+program+induction%2E+Science%2C+350%286266%29%3A1332%E2%80%931338%2C+2015%2E)
17. Lake, B. M., Ullman, T. D., Tenenbaum, J. B., and Gershman, S. J. Building machines that learn and think like people. Behavioral and Brain Sciences, 40, 2017. [find](https://scholar.google.com/scholar?q=Lake%2C+B%2E+M%2E%2C+Ullman%2C+T%2E+D%2E%2C+Tenenbaum%2C+J%2E+B%2E%2C+and+Gershman%2C+S%2E+J%2E+Building+machines+that+learn+and+think+like+people%2E+Behavioral+and+Brain+Sciences%2C+40%2C+2017%2E)
18. Le, T. A., Baydin, A. G., and Wood, F. Inference compilation and universal probabilistic programming. arXiv preprint arXiv:1610.09900, 2016. — [arXiv:1610.09900](https://arxiv.org/abs/1610.09900) [find](https://scholar.google.com/scholar?q=Le%2C+T%2E+A%2E%2C+Baydin%2C+A%2E+G%2E%2C+and+Wood%2C+F%2E+Inference+compilation+and+universal+probabilistic+programming%2E+arXiv+preprint+arXiv%3A1610%2E09900%2C+2016%2E+%E2%80%94+%5BarXiv%3A1610%2E09900%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1610%2E09900%29)
19. Menon, A., Tamuz, O., Gulwani, S., Lampson, B., and Kalai, A. A machine learning framework for programming by example. In International Conference on Machine Learning, pp. 187–195, 2013. [find](https://scholar.google.com/scholar?q=Menon%2C+A%2E%2C+Tamuz%2C+O%2E%2C+Gulwani%2C+S%2E%2C+Lampson%2C+B%2E%2C+and+Kalai%2C+A%2E+A+machine+learning+framework+for+programming+by+example%2E+In+International+Conference+on+Machine+Learning%2C+pp%2E+187%E2%80%93195%2C+2013%2E)
20. Murali, V., Qi, L., Chaudhuri, S., and Jermaine, C. Neural sketch learning for conditional program generation. arXiv preprint arXiv:1703.05698, 2017. [find](https://scholar.google.com/scholar?q=Murali%2C+V%2E%2C+Qi%2C+L%2E%2C+Chaudhuri%2C+S%2E%2C+and+Jermaine%2C+C%2E+Neural+sketch+learning+for+conditional+program+generation%2E+arXiv+preprint+arXiv%3A1703%2E05698%2C+2017%2E)
21. Parisotto, E., Mohamed, A.-r., Singh, R., Li, L., Zhou, D., and Kohli, P. [Neuro-symbolic program synthesis](https://md.research.elamur.ai/free/en/papers/parisotto-2016-neuro-symbolic-program-synthesis/). arXiv preprint arXiv:1611.01855, 2016.
22. Polosukhin, I. and Skidanov, A. Neural program search: Solving programming tasks from description and examples. arXiv preprint arXiv:1802.04335, 2018. [find](https://scholar.google.com/scholar?q=Polosukhin%2C+I%2E+and+Skidanov%2C+A%2E+Neural+program+search%3A+Solving+programming+tasks+from+description+and+examples%2E+arXiv+preprint+arXiv%3A1802%2E04335%2C+2018%2E)
23. Polozov, O. and Gulwani, S. Flashmeta: a framework for inductive program synthesis. In ACM SIGPLAN Notices, volume 50, pp. 107–126. ACM, 2015. [find](https://scholar.google.com/scholar?q=Polozov%2C+O%2E+and+Gulwani%2C+S%2E+Flashmeta%3A+a+framework+for+inductive+program+synthesis%2E+In+ACM+SIGPLAN+Notices%2C+volume+50%2C+pp%2E+107%E2%80%93126%2E+ACM%2C+2015%2E)
24. Schkufza, E., Sharma, R., and Aiken, A. Stochastic program optimization. Communications of the ACM, 59(2):114– 122, 2016. [find](https://scholar.google.com/scholar?q=Schkufza%2C+E%2E%2C+Sharma%2C+R%2E%2C+and+Aiken%2C+A%2E+Stochastic+program+optimization%2E+Communications+of+the+ACM%2C+59%282%29%3A114%E2%80%93+122%2C+2016%2E)
25. Shin, R., Polosukhin, I., and Song, D. Improving neural program synthesis with inferred execution traces. In Advances in Neural Information Processing Systems, pp. 8931–8940, 2018. [find](https://scholar.google.com/scholar?q=Shin%2C+R%2E%2C+Polosukhin%2C+I%2E%2C+and+Song%2C+D%2E+Improving+neural+program+synthesis+with+inferred+execution+traces%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pp%2E+8931%E2%80%938940%2C+2018%2E)
26. Solar-Lezama, A. [Program synthesis by sketching](https://md.research.elamur.ai/free/en/papers/lezama-2008-program-synthesis-sketching/). PhD thesis, University of California, Berkeley, 2008.
27. Zhang, L., Rosenblatt, G., Fetaya, E., Liao, R., Byrd, W., Might, M., Urtasun, R., and Zemel, R. Neural guided constraint logic programming for program synthesis. In Advances in Neural Information Processing Systems, pp. 1744–1753, 2018. [find](https://scholar.google.com/scholar?q=Zhang%2C+L%2E%2C+Rosenblatt%2C+G%2E%2C+Fetaya%2C+E%2E%2C+Liao%2C+R%2E%2C+Byrd%2C+W%2E%2C+Might%2C+M%2E%2C+Urtasun%2C+R%2E%2C+and+Zemel%2C+R%2E+Neural+guided+constraint+logic+programming+for+program+synthesis%2E+In+Advances+in+Neural+Information+Pro)
28. Zohar, A. and Wolf, L. Automatic program synthesis of long programs with a learned garbage collector. In Advances in Neural Information Processing Systems, pp. 2098–2107, 2018. [find](https://scholar.google.com/scholar?q=Zohar%2C+A%2E+and+Wolf%2C+L%2E+Automatic+program+synthesis+of+long+programs+with+a+learned+garbage+collector%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+pp%2E+2098%E2%80%932107%2C+2018%2E)

*Updated 3 November 2026*