Elamur Research
☰
home / papers / 2023 / LEVER: Learning to Verify Language-to-Code Generation with Execution

LEVER: Learning to Verify Language-to-Code Generation with Execution

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 4.0 (arXiv)" does not allow redistributing the text itself. Original — arxiv.org/pdf/2302.08468v3

Summary

Code-oriented large language models can turn natural-language requests into programs, but their single best guess is often wrong. A larger pool of samples, however, frequently contains a correct answer. Existing ways of picking a candidate depend on test cases, which many real applications lack, or on shallow execution heuristics that ignore what the outputs actually look like. LEVER trains a small, separate verifier that reads the question, a candidate program and the result of running it, then estimates whether the program is right. Training labels are obtained automatically by executing sampled programs and comparing their outputs with the gold answer. At inference, each candidate's generation probability is multiplied by its verifier probability. These scores are then pooled across programs that produce the same execution result, and the highest-scoring result is returned. The authors tested the approach on text-to-SQL, table QA, math word problems and basic Python programming. It consistently outperformed strong baselines and set new state-of-the-art results on every benchmark. This shows that frozen code LLMs can be improved through cheap learned reranking rather than costly fine-tuning.

Key points

  • Benchmarks: Spider (SQL), WikiTableQuestions (WikiTQ, answered via SQL over tables), GSM8k (math solved with Python programs) and MBPP (basic Python).
  • With code-davinci-002 as the generator, LEVER gains 4.6% to 10.9% over baselines that only prune programs with execution errors. It reached state-of-the-art on all four datasets without task-specific architectures or prompting.
  • The verifier is a binary classifier (T5 and RoBERTa variants were tested) roughly 0.5% the size of the generator. It is trained with a negative log-likelihood loss normalized by the number of unique candidates per input.
  • Ablations show that execution results are essential to verification quality. The method also helps in low-resource and weakly-supervised settings and transfers across three different code LLMs.
  • Published at ICML 2023 (Yale University and Meta AI). The code is released at github.com/niansong1996/lever.

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

Fields: Mathematics & statistics

Cited by

100 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 92 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2302.08468 · arXiv 2302.08468

@misc{ni2023lever,
  title = {{LEVER: Learning to Verify Language-to-Code Generation with Execution}},
  author = {Ni, Ansong and Iyer, Srini and Radev, Dragomir and Stoyanov, Ves and Yih, Wen-tau and Wang, Sida I. and Lin, Xi Victoria},
  year = {2023},
  doi = {10.48550/arxiv.2302.08468},
  eprint = {2302.08468},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2302.08468}
}

References

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

  1. Agashe, R., Iyer, S., and Zettlemoyer, L. JuICe: A large scale distantly supervised dataset for open domain context-based code generation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processi… find
  2. Artzi, Y. and Zettlemoyer, L. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics, 1:49–62, 2013. find our card
  3. Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. find our card
  4. Berant, J., Chou, A., Frostig, R., and Liang, P. Semantic parsing on Freebase from question-answer pairs. In Empirical Methods in Natural Language Processing (EMNLP), 2013. find
  5. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877–1901, 2020. find
  6. Chen, B., Zhang, F., Nguyen, A., Zan, D., Lin, Z., Lou, J.-G., and Chen, W. Codet: Code generation with generated tests, 2022a. URL https://arxiv.org/abs/2207.10397. ↗
  7. Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021a. find our card
  8. Chen, W., Ma, X., Wang, X., and Cohen, W. W. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12588, 2022b. find our card
  9. Chen, X., Liu, C., and Song, D. Execution-guided neural program synthesis. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=H1gfOiAqYm. ↗
  10. Chen, X., Song, D., and Tian, Y. Latent execution for neural program synthesis beyond domain-specific languages. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Proces… find
  11. Cheng, J. and Lapata, M. Weakly-supervised neural semantic parsing with a generative ranker. In Proceedings of the 22nd Conference on Computational Natural Language Learning, pp. 356–367, 2018. find
  12. Cheng, Z., Xie, T., Shi, P., Li, C., Nadkarni, R., Hu, Y., Xiong, C., Radev, D., Ostendorf, M., Zettlemoyer, L., et al. Binding language models in symbolic languages. arXiv preprint arXiv:2210.02875, 2022. find our card
  13. Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022. find
  14. Cobbe, K., Kosaraju, V., Bavarian, M., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. find our card
  15. Collins, M. and Koo, T. Discriminative reranking for natural language parsing. Computational Linguistics, 31(1):25– 70, 2005. find our card
  16. Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for language understanding. In Burstein, J., Doran, C., and Solorio, T. (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: H… find
  17. Dong, L. and Lapata, M. Language to logical form with neural attention. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. The Association for Computer Linguistics, 2016. doi: 10.18653/v1/p1… find
  18. Fried, D., Aghajanyan, A., Lin, J., Wang, S., Wallace, E., Shi, F., Zhong, R., Yih, W.-t., Zettlemoyer, L., and Lewis, M. Incoder: A generative model for code infilling and synthesis. arXiv preprint arXiv:2204.05999, 2022. find
  19. Gao, L., Madaan, A., Zhou, S., Alon, U., Liu, P., Yang, Y., Callan, J., and Neubig, G. Pal: Program-aided language models. arXiv preprint arXiv:2211.10435, 2022. find
  20. Goldman, O., Latcinnik, V., Nave, E., Globerson, A., and Berant, J. Weakly supervised semantic parsing with abstract examples. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1809–1819, 2018. find
  21. Gulwani, S. and Marron, M. Nlyze: interactive programming by natural language for spreadsheet data analysis and manipulation. In Dyreson, C. E., Li, F., and Özsu, M. T. (eds.), International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, pp. 803–814. find
  22. ACM, 2014. doi: 10.1145/2588555.2612177. URL https://doi.org/10.1145/2588555.2612177. — [doi:10.1145/2588555.2612177](https://doi.org/10.1145/2588555.2612177) ↗
  23. Guu, K., Pasupat, P., Liu, E. Z., and Liang, P. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In Association for Computational Linguistics (ACL), 2017. find
  24. He, P., Liu, X., Gao, J., and Chen, W. Deberta: Decoding-enhanced bert with disentangled attention, 2020. URL https://arxiv.org/abs/2006.03654. ↗ our card
  25. Jiang, Z., Mao, Y., He, P., Neubig, G., and Chen, W. Omnitab: Pretraining with natural and synthetic data for few-shot table-based question answering. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp… find
  26. Kadavath, S., Conerly, T., Askell, A., Henighan, T., Drain, D., Perez, E., Schiefer, N., Hatfield-Dodds, Z., DasSarma, N., Tran-Johnson, E., Johnston, S., El-Showk, S., Jones, A., Elhage, N., Hume, T., Chen, A., Bai, Y., Bowman, S., Fort, S., Ganguli, D., Hernandez, D., Jacobson, J., Kernion, J., Kr… find
  27. Lai, Y., Li, C., Wang, Y., Zhang, T., Zhong, R., Zettlemoyer, L., Yih, S. W.-t., Fried, D., Wang, S., and Yu, T. Ds-1000: A natural and reliable benchmark for data science code generation. arXiv preprint arXiv:2211.11501, 2022. find
  28. Lee, A., Auli, M., and Ranzato, M. Discriminative reranking for neural machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 7250–7264, 20… find
  29. Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Lago, A. D., et al. Competition-level code generation with alphacode. arXiv preprint arXiv:2203.07814, 2022a. find our card
  30. Li, Y., Lin, Z., Zhang, S., Fu, Q., Chen, B., Lou, J.-G., and Chen, W. On the advance of making language models better reasoners. arXiv preprint arXiv:2206.02336, 2022b. — [arXiv:2206.02336](https://arxiv.org/abs/2206.02336) find
  31. Lin, X. V., Wang, C., Pang, D., Vu, K., Zettlemoyer, L., and Ernst, M. D. Program synthesis from natural language using recurrent neural networks. Technical Report UW-CSE-17-03-01, University of Washington Department of Computer Science and Engineering, Seattle, WA, USA, March 2017. find
  32. Lin, X. V., Wang, C., Zettlemoyer, L., and Ernst, M. D. 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), 7-12 May, 2018., 2018. find
  33. Liu, Q., Chen, B., Guo, J., Ziyadi, M., Lin, Z., Chen, W., and Lou, J.-G. Tapex: Table pre-training via learning a neural sql executor. In International Conference on Learning Representations, 2021. find our card
  34. Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/1907.11692, 2019. URL http://arxiv.org/abs/1907.11692. ↗
  35. Ni, A., Inala, J. P., Wang, C., Polozov, O., Meek, C., Radev, D., and Gao, J. Learning from self-sampled correct and partially-correct programs. arXiv preprint arXiv:2205.14318, 2022. find
  36. Nijkamp, E., Pang, B., Hayashi, H., Tu, L., Wang, H., Zhou, Y., Savarese, S., and Xiong, C. A conversational paradigm for program synthesis. arXiv preprint arXiv:2203.13474, 2022. find
  37. Olabiyi, O., Salimov, A., Khazane, A., and Mueller, E. T. Multi-turn dialogue response generation in an adversarial learning framework. CoRR, abs/1805.11752, 2018. URL http://arxiv.org/abs/1805.11752. ↗
  38. OpenAI. Chatgpt: Optimizing language models for dialogue, November 2022. URL https://openai. com/blog/chatgpt/. find
  39. Pasupat, P. and Liang, P. Compositional semantic parsing on semi-structured tables. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1470–1480, Beijing, Ch… find
  40. Qi, J., Tang, J., He, Z., Wan, X., Zhou, C., Wang, X., Zhang, Q., and Lin, Z. Rasat: Integrating relational structures into pretrained seq2seq model for text-to-sql. arXiv preprint arXiv:2205.06983, 2022. find
  41. Rabinovich, M., Stern, M., and Klein, D. Abstract syntax networks for code generation and semantic parsing. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1139–1149, Vancouver, Canada, July 2017. Association for Computational L… find
  42. Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21:140:1–140:67, 2020. URL http://jmlr.org/papers/v21/20-074. html. ↗
  43. Rajkumar, N., Li, R., and Bahdanau, D. Evaluating the text-to-sql capabilities of large language models. arXiv preprint arXiv:2204.00498, 2022. — [arXiv:2204.00498](https://arxiv.org/abs/2204.00498) find
  44. Scholak, T., Schucher, N., and Bahdanau, D. Picard: Parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 9895–9901, 2021. find
  45. Seligman, E., Schubert, T., and Kumar, M. V. A. K. Formal Verification: An Essential Toolkit for Modern VLSI Design. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2015. ISBN 9780128008157. find
  46. Shen, J., Yin, Y., Li, L., Shang, L., Jiang, X., Zhang, M., and Liu, Q. Generate & rank: A multi-task framework for math word problems. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 2269–2279, Punta Cana, Dominican Republic, November 2021. Association for Computationa… find
  47. Shen, L., Sarkar, A., and Och, F. J. Discriminative reranking for machine translation. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004, pp. 177–184, 2004. find
  48. Shi, F., Fried, D., Ghazvininejad, M., Zettlemoyer, L., and Wang, S. I. Natural language to code translation with execution. arXiv preprint arXiv:2204.11454, 2022. find
  49. Shi, T., Zhao, C., Boyd-Graber, J., Daumé III, H., and Lee, L. On the potential of lexico-logical alignments for semantic parsing to SQL queries. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 1849–1864, Online, November 2020. Association for Computational Linguistics… find
  50. Shridhar, M., Thomason, J., Gordon, D., Bisk, Y., Han, W., Mottaghi, R., Zettlemoyer, L., and Fox, D. Alfred: A benchmark for interpreting grounded instructions for everyday tasks. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10737– 10746. find our card
  51. Templeton, M. and Burger, J. D. Problems in natural-language interface to DSMS with examples from EU-FID. In 1st Applied Natural Language Processing Conference, ANLP 1983, Miramar-Sheraton Hotel, Santa Monica, California, USA, February 1-3, 1983, pp. 3– 16. find
  52. ACL, 1983. doi: 10.3115/974194.974197. URL https://aclanthology.org/A83-1002/. ↗
  53. Tufano, M., Drain, D., Svyatkovskiy, A., Deng, S. K., and Sundaresan, N. Unit test case generation with transformers. CoRR, abs/2009.05617, 2020. URL https: //arxiv.org/abs/2009.05617. — [arXiv:2009.05617](https://arxiv.org/abs/2009.05617) find
  54. Wan, X., Cao, Z., Wei, F., Li, S., and Zhou, M. Multi-document summarization via discriminative summary reranking. CoRR, abs/1507.02062, 2015. URL http: //arxiv.org/abs/1507.02062. — [arXiv:1507.02062](https://arxiv.org/abs/1507.02062) find
  55. Wang, B., Shin, R., Liu, X., Polozov, O., and Richardson, M. Rat-sql: Relation-aware schema encoding and linking for text-to-sql parsers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7567–7578, 2020. find
  56. Wang, C., Tatwawadi, K., Brockschmidt, M., Huang, P.-S., Mao, Y., Polozov, O., and Singh, R. Robust text-to-sql generation with execution-guided decoding, 2018. URL https://arxiv.org/abs/1807.03100. ↗
  57. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., and Zhou, D. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022. find our card
  58. Wang, Y., Wang, W., Joty, S., and Hoi, S. C. CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8696–8708, Online and Punta Cana, Dominican Republic,… find
  59. Wei, J., Bosma, M., Zhao, V., Guu, K., Yu, A. W., Lester, B., Du, N., Dai, A. M., and Le, Q. V. Finetuned language models are zero-shot learners. In International Conference on Learning Representations, 2021. find
  60. Welleck, S., Lu, X., West, P., Brahman, F., Shen, T., Khashabi, D., and Choi, Y. Generating sequences by learning to self-correct. arXiv preprint arXiv:2211.00053, 2022. find our card
  61. Woods, W. A. Progress in natural language understanding: an application to lunar geology. In American Federation of Information Processing Societies: 1973 National Computer Conference, 4-8 June 1973, New York, NY, USA, volume 42 of AFIPS Conference Proceedings, pp. 441–450. AFIPS Press/ACM, 1973. do… — [doi:10.1145/1499586.1499695](https://doi.org/10.1145/1499586.1499695) find
  62. Xiao, C., Dymetman, M., and Gardent, C. Sequence-based structured prediction for semantic parsing. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1341–1350, Berlin, Germany, August 2016. Association for Computational Linguistic… find
  63. Xie, T., Wu, C. H., Shi, P., Zhong, R., Scholak, T., Yasunaga, M., Wu, C.-S., Zhong, M., Yin, P., Wang, S. I., et al. Unifiedskg: Unifying and multi-tasking structured knowledge grounding with text-to-text language models. arXiv preprint arXiv:2201.05966, 2022. find our card
  64. Yin, P. and Neubig, G. Reranking for neural semantic parsing. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4553– 4559, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v1/P19-1447. URL https://aclanthology.org/P19… ↗
  65. Yu, T., Zhang, R., Yang, K., Yasunaga, M., Wang, D., Li, Z., Ma, J., Li, I., Yao, Q., Roman, S., Zhang, Z., and Radev, D. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task. In Proceedings of the 2018 Conference on Empirical Methods in Natu… find our card
  66. Zelle, J. M. and Mooney, R. J. Learning to parse database queries using inductive logic programming. In Clancey, W. J. and Weld, D. S. (eds.), Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 9… find
  67. Zettlemoyer, L. S. and Collins, M. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In UAI ’05, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005, pp. 658–666. find
  68. AUAI Press, 2005. URL https://dslpitt.org/uai/displayArticleDetails. jsp?mmnu=1&smnu=2&article\_id=1209& proceeding\_id=21. ↗
  69. Zhang, T., Yu, T., Hashimoto, T. B., Lewis, M., Yih, W.-t., Fried, D., and Wang, S. I. Coder reviewer reranking for code generation. arXiv preprint arXiv:2211.16490, 2022. find
  70. Zhong, V., Xiong, C., and Socher, R. Seq2sql: Generating structured queries from natural language using reinforcement learning. CoRR, abs/1709.00103, 2017. URL http://arxiv.org/abs/1709.00103. ↗
  71. Zhou, F., Hu, M., Dong, H., Cheng, Z., Han, S., and Zhang, D. Tacube: Pre-computing data cubes for answering numerical-reasoning questions over tabular data. arXiv preprint arXiv:2205.12682, 2022. find
  72. Zhou, S., Yin, P., and Neubig, G. Hierarchical control of situated agents through natural language. arXiv preprint arXiv:2109.08214, 2021. find