Natural Language to Code Translation with Execution
Open accessAbstract
Generative models of code, pretrained on large corpora of programs, have shown great success in translating natural language to code (Chen et al., 2021; Austin et al., 2021; Li et al., 2022, inter alia). While these models do not explicitly incorporate program semantics (i.e., execution results) during training, they are able to generate correct solutions for many problems. However, choosing a single correct program from a generated set for each problem remains challenging. In this work, we introduce execution result--based minimum Bayes risk decoding (MBR-EXEC) for program selection and show that it improves the few-shot performance of pretrained code models on natural-language-to-code tasks. We select output programs from a generated candidate set by marginalizing over program implementations that share the same semantics. Because exact equivalence is intractable, we execute each program on a small number of test inputs to approximate semantic equivalence. Across datasets, execution or simulated execution significantly outperforms the methods that do not involve program semantics. We find that MBR-EXEC consistently improves over all execution-unaware selection methods, suggesting it as an effective approach for natural language to code translation. We open-source our code at github.com/facebookresearch/mbr-exec and data at dl.fbaipublicfiles.com/mbr-exec/mbr-exec-release.zip
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Current literature on detecting and mitigating factual errors generated by machine learning models focuses predominantly on a single specific task.
“Current literature on detecting and mitigating factual errors generated by machine learning models focuses predominantly on a single specific task, for example, retrieval-augmented verification models for QA (Lewis et al., 2020), hallucination detection models for text summarization (Fabbri et al., 2022), and execution-based evaluation for code (Shi et al., 2022).”
From FacTool: Factuality Detection in Generative AI - A Tool Augmented Framework for Multi-Task and Multi-Domain Scenarios (2023) · cites this paper as Shi et al., 2022
For code generation tasks, code execution can be utilized to select the final prediction.
“In particular, for code generation tasks, we can utilize code execution to select the final prediction (Chen et al., 2019;Li et al., 2022;Shi et al., 2022;Zhang et al., 2022;Ni et al., 2023).”
From Teaching Large Language Models to Self-Debug (2023) · cites this paper as Shi et al., 2022
Decoding multiple samples can significantly improve the performance of large language models.
“Prior works demonstrate that decoding multiple samples can significantly improve the performance of large language models (Wang et al., 2023;Shi et al., 2022).”
From Teaching Large Language Models to Self-Debug (2023) · cites this paper as Shi et al., 2022
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 43
- Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732. · arXiv
- Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
- Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. · arXiv
- Li Dong and Mirella Lapata. 2018. Coarse-to-fine de- coding for neural semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 731-742, Melbourne, Australia. Association for Computational Linguistics. · DOI
- Bryan Eikema and Wilker Aziz. 2020. Is MAP decoding all you need? the inadequacy of the mode in neural machine translation. In Proceedings of the 28th Inter- national Conference on Computational Linguistics, pages 4506-4520, Barcelona, Spain (Online). Inter- national Committee on Computational Linguistics. · DOI
- Bryan Eikema and Wilker Aziz. 2021. Sampling-based minimum bayes risk decoding for neural machine translation. arXiv preprint arXiv:2108.04718. · arXiv
- Tianyu Gao, Adam Fisch, and Danqi Chen. 2021. Making pre-trained language models better few-shot learners. In Proceedings of the 59th Annual Meet- ing of the Association for Computational Linguistics and the 11th International Joint Conference on Natu- ral Language Processing (Volume 1: Long Papers), pages 3816-3830, Online. Association for Computa- tional Linguistics. · DOI · Paper page
- Vaibhava Goel and William J Byrne. 2000. Minimum bayes-risk automatic speech recognition. Computer Speech & Language, 14(2):115-135.
- Dan Hendrycks, Steven Basart, Saurav Kadavath, Man- tas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. 2021. Measuring coding challenge com- petence with APPS. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2).
- Zhengbao Jiang, Frank F. Xu, Jun Araki, and Graham Neubig. 2020. How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438. · DOI · Paper page
- Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Han- naneh Hajishirzi. 2020. UNIFIEDQA: Crossing for- mat boundaries with a single QA system. In Find- ings of the Association for Computational Linguistics: EMNLP 2020, pages 1896-1907, Online. Association for Computational Linguistics. · DOI · Paper page
- Shankar Kumar and William Byrne. 2004. Minimum Bayes-risk decoding for statistical machine transla- tion. In Proceedings of the Human Language Tech- nology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, pages 169-176, Boston, Mas- sachusetts, USA. Association for Computational Lin- guistics.
- Marie-Anne Lachaux, Baptiste Roziere, Marc Szafraniec, and Guillaume Lample. 2021. Dobf: A deobfuscation pre-training objective for program- ming languages. Advances in Neural Information Processing Systems, 34.
- Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power of scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3045-3059, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics. · DOI · Paper page
- Xiang Lisa Li and Percy Liang. 2021. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4582- 4597, Online. Association for Computational Lin- guistics. · DOI · Paper page
- Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022. Competition-level code generation with alphacode. arXiv preprint arXiv:2203.07814. · arXiv
- Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D. Ernst. 2018. NL2Bash: A corpus and semantic parser for natural language interface to the linux operating system. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018), Miyazaki, Japan. European Language Resources Association (ELRA).
- Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Fumin Wang, and Andrew Senior. 2016. Latent predictor networks for code generation. In Proceedings of the 54th An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 599-609, Berlin, Germany. Association for Computational Lin- guistics. · DOI · Paper page
- Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2021. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language processing. arXiv preprint arXiv:2107.13586. · arXiv
- Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, Ge Li, Li- dong Zhou, Linjun Shou, Long Zhou, Michele Tu- fano, MING GONG, Ming Zhou, Nan Duan, Neel Sundaresan, Shao Kun Deng, Shengyu Fu, and Shu- jie LIU. 2021. CodeXGLUE: A machine learning benchmark dataset for code understanding and gener- ation. In Thirty-fifth Conference on Neural Informa- tion Processing Systems Datasets and Benchmarks Track (Round 1).
- Antonio Valerio Miceli Barone and Rico Sennrich. 2017. A parallel corpus of python functions and documen- tation strings for automated code documentation and code generation. In Proceedings of the Eighth In- ternational Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 314- 319, Taipei, Taiwan. Asian Federation of Natural Language Processing.
- Sewon Min, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2021. Noisy channel language model prompting for few-shot text classification. arXiv preprint arXiv:2108.04106. · arXiv
- Maxim Rabinovich, Mitchell Stern, and Dan Klein. 2017. Abstract syntax networks for code generation and semantic parsing. In Proceedings of the 55th An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1139- 1149, Vancouver, Canada. Association for Computa- tional Linguistics. · DOI
- Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9.
- Torsten Scholak, Nathan Schucher, and Dzmitry Bah- danau. 2021. PICARD: Parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 9895-9901, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics. · DOI
- Haoyue Shi, Jiayuan Mao, Kevin Gimpel, and Karen Livescu. 2019. Visually grounded neural syntax ac- quisition. In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 1842-1861, Florence, Italy. Association for Computational Linguistics. · DOI
- Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. 2020. AutoPrompt: Elic- iting Knowledge from Language Models with Auto- matically Generated Prompts. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4222-4235, Online. Association for Computational Linguistics. · DOI · Paper page
- Alane Suhr, Srinivasan Iyer, and Yoav Artzi. 2018. Learning to map context-dependent sentences to exe- cutable formal queries. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 2238-2249, New Orleans, Louisiana. Associa- tion for Computational Linguistics. · DOI
- Roy Tromble, Shankar Kumar, Franz Och, and Wolf- gang Macherey. 2008. Lattice Minimum Bayes-Risk decoding for statistical machine translation. In Pro- ceedings of the 2008 Conference on Empirical Meth- ods in Natural Language Processing, pages 620-629, Honolulu, Hawaii. Association for Computational Linguistics.
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems, 30.
- Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. 2022. Self-consistency im- proves chain of thought reasoning in language mod- els. arXiv preprint arXiv:2203.11171. · arXiv
- Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903. · arXiv
- Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Di- nan, Kyunghyun Cho, and Jason Weston. 2020. Neu- ral text generation with unlikelihood training. In International Conference on Learning Representa- tions.
- Chunyang Xiao, Marc Dymetman, and Claire Gardent. 2016. Sequence-based structured prediction for se- mantic parsing. In Proceedings of the 54th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1341-1350, Berlin, Germany. Association for Computational Lin- guistics. · DOI
- Tianbao Xie, Chen Henry Wu, Peng Shi, Ruiqi Zhong, Torsten Scholak, Michihiro Yasunaga, Chien-Sheng Wu, Ming Zhong, Pengcheng Yin, Sida I Wang, et al. 2022. Unifiedskg: Unifying and multi-tasking structured knowledge grounding with text-to-text lan- guage models. arXiv preprint arXiv:2201.05966. · arXiv
- Frank F. Xu, Zhengbao Jiang, Pengcheng Yin, Bogdan Vasilescu, and Graham Neubig. 2020. Incorporating external knowledge through pre-training for natural language to code generation. In Proceedings of the 58th Annual Meeting of the Association for Compu- tational Linguistics, pages 6045-6052, Online. Asso- ciation for Computational Linguistics. · DOI
- Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu, and Graham Neubig. 2018. Learning to mine aligned code and natural language pairs from stack overflow. In 2018 IEEE/ACM 15th interna- tional conference on mining software repositories (MSR), pages 476-486. IEEE.
- Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingn- ing Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. 2018. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic pars- ing and text-to-SQL task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Lan- guage Processing, pages 3911-3921, Brussels, Bel- gium. Association for Computational Linguistics. · DOI · Paper page
- Weizhe Yuan, Graham Neubig, and Pengfei Liu. 2021. BARTScore: Evaluating generated text as text gener- ation. In Advances in Neural Information Processing Systems.
- Hao Zhang and Daniel Gildea. 2008. Efficient multi- pass decoding for synchronous context free gram- mars. In Proceedings of ACL-08: HLT, pages 209- 217, Columbus, Ohio. Association for Computational Linguistics.
- Yu Zhang, Zhenghua Li, and Min Zhang. 2020. Effi- cient second-order TreeCRF for neural dependency parsing. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pages 3295-3305, Online. Association for Computa- tional Linguistics. · DOI
- Ruiqi Zhong, Tao Yu, and Dan Klein. 2020. Semantic evaluation for text-to-SQL with distilled test suites. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 396-411, Online. Association for Computa- tional Linguistics. · DOI · Paper page
- Zexuan Zhong, Dan Friedman, and Danqi Chen. 2021. Factual probing is [MASK]: Learning vs. learning to recall. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 5017-5033, Online. Association for Computational Linguistics. · DOI · Paper page
Cited by
Sorted by citations
Self-Consistency Improves Chain of Thought Reasoning in Language Models
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., & Zhou, D. (2022) · arXiv · doi:10.48550/arxiv.2203.11171 · Cited by 829 · see citing works
“…sampling (Ackley et al., 1985; Ficler & Goldberg, 2017), top-k sampling (Fan et al., 2018; Holtzman et al., 2018; Radford et al., 2019), nucleus sampling (Holtzman et al., 2020), minimum Bayes risk decoding (Eikema & Aziz, 2020; Shi et al., 2022), and typical decoding (Meister et al., 2022).”
BackgroundLarge Language Models Can Be Easily Distracted by Irrelevant Context
Shi, F., Chen, X., Misra, K., Scales, N., Dohan, D., Chi, E., Schärli, N., & Zhou, D. (2023) · arXiv · doi:10.48550/arxiv.2302.00093 · Cited by 134 · see citing works
“Self-consistency (SC; Wang et al., 2022c; Shi et al., 2022a) may further boost the reasoning performance by marginal-izing over intermediate reasoning steps that share the same final result.”
BackgroundMethodInfluentialSelf-citationTeaching Large Language Models to Self-Debug
Chen, X., Lin, M., Schärli, N., & Zhou, D. (2023) · arXiv · doi:10.48550/arxiv.2304.05128 · Cited by 77 · see citing works
“Following prior work evaluating large language models for text-to-SQL generation (Rajkumar et al., 2022; Shi et al., 2022; Ni et al., 2023), we evaluate SELF-DEBUGGING on the development set of the Spider benchmark (Yu et al.”
BackgroundMethodInfluentialBigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions
Zhuo, T. Y., Vu, M. C., Chim, J., Hu, H., Yu, W., Widyasari, R., Yusuf, I. N. B., Zhan, H., He, J., Paul, I., et al. (2024) · arXiv · doi:10.48550/arxiv.2406.15877 · Cited by 29 · see citing works
Self-citationChern, I.-C., Chern, S., Chen, S., Yuan, W., Feng, K., Zhou, C., He, J., Neubig, G., & Liu, P. (2023) · arXiv · doi:10.48550/arxiv.2307.13528 · Cited by 29 · see citing works
“, 2022), and execution-based evaluation for code (Shi et al., 2022).”
BackgroundEvoR: Evolving Retrieval for Code Generation
Su, H., Jiang, S., Lai, Y., Wu, H., Shi, B., Liu, C., Liu, Q., & Yu, T. (2024) · Findings of the Association for Computational Linguistics: EMNLP 2024 · doi:10.18653/v1/2024.findings-emnlp.143 · Cited by 12 · see citing works
Jiang, J., Shen, J., Kim, S., Yoo, K. M., Kim, J., & Kim, S. (2026) · arXiv · doi:10.48550/arxiv.2603.05863
“These can be broadly categorized into three paradigms: (1) Re-ranking , which samples multiple candidates to select the best one (Shi et al., 2022; Li et al., 2022; Chen et al., 2022; Zhang et al., 2023b; Ni et al., 2023); (2) External Repairers , utilizing separate models to patch errors (Gupta et…”
- Authors
- Shi, F., Fried, D., Ghazvininejad, M., Zettlemoyer, L., & Wang, S. I.
- Affiliations
- Toyota Technological Institute at Chicago (US)
- Carnegie Mellon University (US)
- University of Washington (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2022
- Pages
- 3533-3546
- arXiv
- 2204.11454
- OpenAlex
- W4385572707
- Cited by
- 49
- References
- 0
- Citations by year
- 2026: 9 · 2025: 19 · 2024: 12 · 2023: 9
- FWCI
- 8.94
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Keywords
- natural language to code translation, program selection, minimum Bayes risk decoding, semantic equivalence, program semantics, few-shot learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
