---
title: "Neuro-Symbolic Program Synthesis — Parisotto 2016"
description: "Besides a plain bidirectional LSTM encoder, the authors propose a cross correlation I/O network that… 31 references, cited by 60 papers here."
authors: ["Emilio Parisotto", "Abdel-rahman Mohamed", "Rishabh Singh", "Lihong Li", "Dengyong Zhou", "Pushmeet Kohli"]
year: 2016
venue: "arXiv:1611.01855"
source: "https://arxiv.org/abs/1611.01855"
doi: "10.48550/arxiv.1611.01855"
arxiv: "1611.01855"
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/parisotto-2016-neuro-symbolic-program-synthesis/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/parisotto-2016-neuro-symbolic-program-synthesis/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2016](https://md.research.elamur.ai/free/en/papers/2016/page/3/) / Neuro-Symbolic Program Synthesis

# Neuro-Symbolic Program Synthesis

**Authors:** Emilio Parisotto, Abdel-rahman Mohamed, [Rishabh Singh](https://md.research.elamur.ai/free/en/authors/rishabh-singh/), [Lihong Li](https://md.research.elamur.ai/free/en/authors/lihong-li/), Dengyong Zhou and [Pushmeet Kohli](https://md.research.elamur.ai/free/en/authors/pushmeet-kohli/) · **Year:** 2016 · **Venue:** arXiv:1611.01855 · **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/1611.01855) · [PDF](https://arxiv.org/pdf/1611.01855) · [DOI 10.48550/arxiv.1611.01855](https://doi.org/10.48550/arxiv.1611.01855) · [arXiv 1611.01855](https://arxiv.org/abs/1611.01855) · [OpenAlex](https://openalex.org/W2550120381)

**Citations:** 92 citations (OpenAlex, 2026-10-14) · [60](https://md.research.elamur.ai/free/en/papers/parisotto-2016-neuro-symbolic-program-synthesis/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Neural program-induction models usually learn an opaque mapping. They are expensive to train and need a separate model for every task. This paper instead addresses program synthesis: from a few input-output examples, it produces an explicit program in a domain-specific language (DSL) that reproduces them. A single model serves many tasks, and no hand-crafted search heuristics are needed.

The method has two neural parts. An encoder compresses the example set into a vector. Besides a plain bidirectional LSTM encoder, the authors propose a cross correlation I/O network that correlates LSTM representations of inputs and outputs. The Recursive-Reverse-Recursive Neural Network (R3NN) then builds a parse tree of the DSL grammar step by step. At each step it chooses which non-terminal to expand and which rule to apply, and every node's representation reflects the whole partial tree. Training data comes from randomly sampled programs, rule-generated inputs and the outputs obtained by running those programs.

On FlashFill-style regex string transformations, the system finds correct programs even for tasks unseen in training. This suggests that learned synthesis can be both interpretable and general.

## Key points
- The DSL is a large subset of the FlashFill language (Microsoft Excel 2013) without conditionals. It is built from Concat, ConstStr, SubStr and position logic, and uses 8 predefined regex token classes.
- R3NN encodes a partial program tree in two passes: a recursive pass up to the root, then a reverse-recursive pass back down to every node.
- With a single sample, the system solves 63% of tasks not seen during training. This rises to 94% when 100 program samples are drawn.
- It solves 38% of 238 real-world FlashFill benchmarks.
- Two I/O encoders were compared: an LSTM-concatenation encoder and the cross correlation encoder.

*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

- [Microsoft](https://md.research.elamur.ai/free/en/companies/microsoft/) — Company, Redmond, United States · 378 works · 161,630 citations
- [University of Toronto](https://md.research.elamur.ai/free/en/universities/university-of-toronto/) — University, Toronto, Canada · 110 works · 179,062 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 321 works · [🖥️ Computer Science Applications](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-science-applications/) · 131 works

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

## Cite

Cite as: Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou and Pushmeet Kohli. 2016. Neuro-Symbolic Program Synthesis. arXiv:1611.01855.

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

```bibtex
@misc{parisotto2016neuro,
  title = {{Neuro-Symbolic Program Synthesis}},
  author = {Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou and Pushmeet Kohli},
  year = {2016},
  doi = {10.48550/arxiv.1611.01855},
  eprint = {1611.01855},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1611.01855}
}
```

- [← previous Generation from Abstract Meaning Representation using Tree Transducers](https://md.research.elamur.ai/free/en/papers/flanigan-2016-generation-abstract-meaning-representation-tree/)
- [next → Discourse Parsing with Attention-based Hierarchical Neural Networks](https://md.research.elamur.ai/free/en/papers/li-2016-discourse-parsing-attention-based-hierarchical/)
- [↑ back to papers of 2016](https://md.research.elamur.ai/free/en/papers/2016/page/3/)

## References

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

1. Alur, Rajeev, Bodı́k, Rastislav, Dallal, Eric, Fisman, Dana, Garg, Pranav, Juniwal, Garvit, Kress-Gazit, Hadas, Madhusudan, P., Martin, Milo M. K., Raghothaman, Mukund, Saha, Shamwaditya, Seshia, Sanjit A., Singh, Rishabh, Solar-Lezama, Armando, Torlak, Emina, and Udupa, Abhishek. Syntax-guided synt… [find](https://scholar.google.com/scholar?q=Alur%2C+Rajeev%2C+Bod%C4%B1%CC%81k%2C+Rastislav%2C+Dallal%2C+Eric%2C+Fisman%2C+Dana%2C+Garg%2C+Pranav%2C+Juniwal%2C+Garvit%2C+Kress%2DGazit%2C+Hadas%2C+Madhusudan%2C+P%2E%2C+Martin%2C+Milo+M%2E+K%2E%2C+Raghothaman%2C+Mukund%2C+Saha%2C+Shamwaditya%2C+Seshia%2C+Sanj)
2. Bielik, Pavol, Raychev, Veselin, and Vechev, Martin T. PHOG: probabilistic model for code. In ICML, pp. 2933–2942, 2016. [find](https://scholar.google.com/scholar?q=Bielik%2C+Pavol%2C+Raychev%2C+Veselin%2C+and+Vechev%2C+Martin+T%2E+PHOG%3A+probabilistic+model+for+code%2E+In+ICML%2C+pp%2E+2933%E2%80%932942%2C+2016%2E)
3. Biermann, Alan W. The inference of regular lisp programs from examples. IEEE transactions on Systems, Man, and Cybernetics, 8(8):585–600, 1978. [find](https://scholar.google.com/scholar?q=Biermann%2C+Alan+W%2E+The+inference+of+regular+lisp+programs+from+examples%2E+IEEE+transactions+on+Systems%2C+Man%2C+and+Cybernetics%2C+8%288%29%3A585%E2%80%93600%2C+1978%2E)
4. Bunel, Rudy, Desmaison, Alban, Kohli, Pushmeet, Torr, Philip H. S., and Kumar, M. Pawan. Adaptive neural compilation. CoRR, abs/1605.07969, 2016. URL http://arxiv.org/abs/1605.07969. — [arXiv:1605.07969](https://arxiv.org/abs/1605.07969) [↗](http://arxiv.org/abs/1605.07969)
5. Gaunt, Alexander L, Brockschmidt, Marc, Singh, Rishabh, Kushman, Nate, Kohli, Pushmeet, Taylor, Jonathan, and Tarlow, Daniel. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv:1608.04428, 2016. [find](https://scholar.google.com/scholar?q=Gaunt%2C+Alexander+L%2C+Brockschmidt%2C+Marc%2C+Singh%2C+Rishabh%2C+Kushman%2C+Nate%2C+Kohli%2C+Pushmeet%2C+Taylor%2C+Jonathan%2C+and+Tarlow%2C+Daniel%2E+Terpret%3A+A+probabilistic+programming+language+for+program+induction%2E+arXiv)
6. Graves, Alex, Wayne, Greg, and Danihelka, Ivo. arXiv:1410.5401, 2014. [find](https://scholar.google.com/scholar?q=Graves%2C+Alex%2C+Wayne%2C+Greg%2C+and+Danihelka%2C+Ivo%2E+arXiv%3A1410%2E5401%2C+2014%2E)
7. Gulwani, Sumit. [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 POPL, pp. 317–330, 2011.
8. Gulwani, Sumit, Jha, Susmit, Tiwari, Ashish, and Venkatesan, Ramarathnam. Synthesis of loop-free programs. In PLDI, pp. 62–73, 2011. [find](https://scholar.google.com/scholar?q=Gulwani%2C+Sumit%2C+Jha%2C+Susmit%2C+Tiwari%2C+Ashish%2C+and+Venkatesan%2C+Ramarathnam%2E+Synthesis+of+loop%2Dfree+programs%2E+In+PLDI%2C+pp%2E+62%E2%80%9373%2C+2011%2E)
9. Gulwani, Sumit, Harris, William, and Singh, Rishabh. Spreadsheet data manipulation using examples. Communications of the ACM, Aug 2012. [find](https://scholar.google.com/scholar?q=Gulwani%2C+Sumit%2C+Harris%2C+William%2C+and+Singh%2C+Rishabh%2E+Spreadsheet+data+manipulation+using+examples%2E+Communications+of+the+ACM%2C+Aug+2012%2E)
10. Hindle, Abram, Barr, Earl T., Gabel, Mark, Su, Zhendong, and Devanbu, Premkumar T. On the naturalness of software. Commun. ACM, 59(5):122–131, 2016. [find](https://scholar.google.com/scholar?q=Hindle%2C+Abram%2C+Barr%2C+Earl+T%2E%2C+Gabel%2C+Mark%2C+Su%2C+Zhendong%2C+and+Devanbu%2C+Premkumar+T%2E+On+the+naturalness+of+software%2E+Commun%2E+ACM%2C+59%285%29%3A122%E2%80%93131%2C+2016%2E)
11. Irsoy, Orzan and Cardie, Claire. Bidirectional recursive neural networks for token-level labeling with structure. In NIPS Deep Learning Workshop, 2013. [find](https://scholar.google.com/scholar?q=Irsoy%2C+Orzan+and+Cardie%2C+Claire%2E+Bidirectional+recursive+neural+networks+for+token%2Dlevel+labeling+with+structure%2E+In+NIPS+Deep+Learning+Workshop%2C+2013%2E)
12. Neural turing machines. arXiv preprint Joulin, Armand and Mikolov, Tomas. Inferring algorithmic patterns with stack-augmented recurrent nets. In NIPS, pp. 190–198, 2015. [find](https://scholar.google.com/scholar?q=Neural+turing+machines%2E+arXiv+preprint+Joulin%2C+Armand+and+Mikolov%2C+Tomas%2E+Inferring+algorithmic+patterns+with+stack%2Daugmented+recurrent+nets%2E+In+NIPS%2C+pp%2E+190%E2%80%93198%2C+2015%2E)
13. Kurach, Karol, Andrychowicz, Marcin, and Sutskever, Ilya. Neural random-access machines. arXiv preprint arXiv:1511.06392, 2015. [find](https://scholar.google.com/scholar?q=Kurach%2C+Karol%2C+Andrychowicz%2C+Marcin%2C+and+Sutskever%2C+Ilya%2E+Neural+random%2Daccess+machines%2E+arXiv+preprint+arXiv%3A1511%2E06392%2C+2015%2E)
14. Le, Phong and Zuidema, Willem. The inside-outside recursive neural network model for dependency parsing. In EMNLP, pp. 729–739, 2014. [find](https://scholar.google.com/scholar?q=Le%2C+Phong+and+Zuidema%2C+Willem%2E+The+inside%2Doutside+recursive+neural+network+model+for+dependency+parsing%2E+In+EMNLP%2C+pp%2E+729%E2%80%93739%2C+2014%2E)
15. Liang, Percy, Jordan, Michael I., and Klein, Dan. Learning programs: A hierarchical Bayesian approach. In ICML, pp. 639–646, 2010. [find](https://scholar.google.com/scholar?q=Liang%2C+Percy%2C+Jordan%2C+Michael+I%2E%2C+and+Klein%2C+Dan%2E+Learning+programs%3A+A+hierarchical+Bayesian+approach%2E+In+ICML%2C+pp%2E+639%E2%80%93646%2C+2010%2E)
16. Maddison, Chris J and Tarlow, Daniel. Structured generative models of natural source code. In ICML, pp. 649–657, 2014. [find](https://scholar.google.com/scholar?q=Maddison%2C+Chris+J+and+Tarlow%2C+Daniel%2E+Structured+generative+models+of+natural+source+code%2E+In+ICML%2C+pp%2E+649%E2%80%93657%2C+2014%2E)
17. Menon, Aditya Krishna, Tamuz, Omer, Gulwani, Sumit, Lampson, Butler W., and Kalai, Adam. A machine learning framework for programming by example. In ICML, pp. 187–195, 2013. [find](https://scholar.google.com/scholar?q=Menon%2C+Aditya+Krishna%2C+Tamuz%2C+Omer%2C+Gulwani%2C+Sumit%2C+Lampson%2C+Butler+W%2E%2C+and+Kalai%2C+Adam%2E+A+machine+learning+framework+for+programming+by+example%2E+In+ICML%2C+pp%2E+187%E2%80%93195%2C+2013%2E)
18. Neelakantan, Arvind, Le, Quoc V, and Sutskever, Ilya. Neural programmer: Inducing latent programs with gradient descent. arXiv preprint arXiv:1511.04834, 2015. [find](https://scholar.google.com/scholar?q=Neelakantan%2C+Arvind%2C+Le%2C+Quoc+V%2C+and+Sutskever%2C+Ilya%2E+Neural+programmer%3A+Inducing+latent+programs+with+gradient+descent%2E+arXiv+preprint+arXiv%3A1511%2E04834%2C+2015%2E)
19. Paulus, Romain, Socher, Richard, and Manning, Christopher D. Global belief recursive neural networks. pp. 2888–2896, 2014. [find](https://scholar.google.com/scholar?q=Paulus%2C+Romain%2C+Socher%2C+Richard%2C+and+Manning%2C+Christopher+D%2E+Global+belief+recursive+neural+networks%2E+pp%2E+2888%E2%80%932896%2C+2014%2E)
20. Raychev, Veselin, Vechev, Martin T., and Krause, Andreas. Predicting program properties from ”big code”. In POPL, pp. 111–124, 2015. [find](https://scholar.google.com/scholar?q=Raychev%2C+Veselin%2C+Vechev%2C+Martin+T%2E%2C+and+Krause%2C+Andreas%2E+Predicting+program+properties+from+%E2%80%9Dbig+code%E2%80%9D%2E+In+POPL%2C+pp%2E+111%E2%80%93124%2C+2015%2E)
21. Reed, Scott and de Freitas, Nando. arXiv:1511.06279, 2015. [find](https://scholar.google.com/scholar?q=Reed%2C+Scott+and+de+Freitas%2C+Nando%2E+arXiv%3A1511%2E06279%2C+2015%2E)
22. Riedel, Sebastian, Bosnjak, Matko, and Rocktäschel, Tim. Programming with a differentiable forth interpreter. CoRR, abs/1605.06640, 2016. URL http://arxiv.org/abs/1605.06640. [↗](http://arxiv.org/abs/1605.06640)
23. Schkufza, Eric, Sharma, Rahul, and Aiken, Alex. Stochastic superoptimization. In ASPLOS, pp. 305–316, 2013. [find](https://scholar.google.com/scholar?q=Schkufza%2C+Eric%2C+Sharma%2C+Rahul%2C+and+Aiken%2C+Alex%2E+Stochastic+superoptimization%2E+In+ASPLOS%2C+pp%2E+305%E2%80%93316%2C+2013%2E)
24. Singh, Rishabh and Solar-Lezama, Armando. Synthesizing data structure manipulations from storyboards. In SIGSOFT FSE, pp. 289–299, 2011. [find](https://scholar.google.com/scholar?q=Singh%2C+Rishabh+and+Solar%2DLezama%2C+Armando%2E+Synthesizing+data+structure+manipulations+from+storyboards%2E+In+SIGSOFT+FSE%2C+pp%2E+289%E2%80%93299%2C+2011%2E)
25. Singh, Rishabh, Gulwani, Sumit, and Solar-Lezama, Armando. Automated feedback generation for introductory programming assignments. In PLDI, pp. 15–26, 2013. [find](https://scholar.google.com/scholar?q=Singh%2C+Rishabh%2C+Gulwani%2C+Sumit%2C+and+Solar%2DLezama%2C+Armando%2E+Automated+feedback+generation+for+introductory+programming+assignments%2E+In+PLDI%2C+pp%2E+15%E2%80%9326%2C+2013%2E)
26. Solar-Lezama, Armando. Program Synthesis By Sketching. PhD thesis, EECS Dept., UC Berkeley, 2008. [find](https://scholar.google.com/scholar?q=Solar%2DLezama%2C+Armando%2E+Program+Synthesis+By+Sketching%2E+PhD+thesis%2C+EECS+Dept%2E%2C+UC+Berkeley%2C+2008%2E)
27. Solar-Lezama, Armando, Rabbah, Rodric, Bodik, Rastislav, and Ebcioglu, Kemal. Programming by sketching for bit-streaming programs. In PLDI, 2005. [find](https://scholar.google.com/scholar?q=Solar%2DLezama%2C+Armando%2C+Rabbah%2C+Rodric%2C+Bodik%2C+Rastislav%2C+and+Ebcioglu%2C+Kemal%2E+Programming+by+sketching+for+bit%2Dstreaming+programs%2E+In+PLDI%2C+2005%2E)
28. Summers, Phillip D. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):161–175, 1977. [find](https://scholar.google.com/scholar?q=Summers%2C+Phillip+D%2E+A+methodology+for+lisp+program+construction+from+examples%2E+Journal+of+the+ACM+%28JACM%29%2C+24%281%29%3A161%E2%80%93175%2C+1977%2E)
29. Udupa, Abhishek, Raghavan, Arun, Deshmukh, Jyotirmoy V., Mador-Haim, Sela, Martin, Milo M. K., and Alur, Rajeev. TRANSIT: specifying protocols with concolic snippets. In PLDI, pp. 287–296, 2013. [find](https://scholar.google.com/scholar?q=Udupa%2C+Abhishek%2C+Raghavan%2C+Arun%2C+Deshmukh%2C+Jyotirmoy+V%2E%2C+Mador%2DHaim%2C+Sela%2C+Martin%2C+Milo+M%2E+K%2E%2C+and+Alur%2C+Rajeev%2E+TRANSIT%3A+specifying+protocols+with+concolic+snippets%2E+In+PLDI%2C+pp%2E+287%E2%80%93296%2C+2013%2E)
30. Vinyals, Oriol, Kaiser, Lukasz, Koo, Terry, Petrov, Slav, Sutskever, Ilya, and Hinton, Geoffrey. Grammar as a foreign language. In ICLR, 2015. [find](https://scholar.google.com/scholar?q=Vinyals%2C+Oriol%2C+Kaiser%2C+Lukasz%2C+Koo%2C+Terry%2C+Petrov%2C+Slav%2C+Sutskever%2C+Ilya%2C+and+Hinton%2C+Geoffrey%2E+Grammar+as+a+foreign+language%2E+In+ICLR%2C+2015%2E)
31. Neural programmer-interpreters. arXiv preprint JConcat(f 1 , · · · , f n )K v JConstStr(s)K v JSubStr(v, p l , p r )K v JConstPos(k)K v J(r, k, Start)K v J(r, k, End)K v Figure 7: The semantics of the DSL for string transformations. [find](https://scholar.google.com/scholar?q=Neural+programmer%2Dinterpreters%2E+arXiv+preprint+JConcat%28f+1+%2C+%C2%B7+%C2%B7+%C2%B7+%2C+f+n+%29K+v+JConstStr%28s%29K+v+JSubStr%28v%2C+p+l+%2C+p+r+%29K+v+JConstPos%28k%29K+v+J%28r%2C+k%2C+Start%29K+v+J%28r%2C+k%2C+End%29K+v+Figure+7%3A+The+semantics+of+the)

*Updated 2 November 2026*