Elamur Research⌕
☰
home / papers / 2023 / ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers

ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers

Paper · 2023 · Kexun Zhang, Danqing Wang, Jingtao Xia et al.

Summary

LLMs handle code generation well when a task spells out exactly what to implement. They do much worse on competitive-programming problems, where the model must first choose an efficient algorithm, and their output still needs human checking. ALGO tackles both issues. It builds on an observation: writing a slow, exhaustive brute-force solution is far easier for an LLM than writing an efficient one. A "verifier" LLM is therefore prompted to enumerate all relevant variable combinations, yielding a reference oracle that is likely correct but may be slow. A separate "coder", which can be any code generation model or search strategy, proposes faster candidates. Each candidate's outputs on generated test inputs are compared with the oracle's outputs. Mismatching cases are fed back to the coder for refinement. Evaluated on CodeContests and a set of recent LeetCode problems, this model-agnostic setup substantially raises one-submission pass rates for several existing systems. It also gives interpretable, execution-based verification rather than opaque confidence scores.

Key points

  • On ChatGPT, brute-force solutions succeed far more often than efficient ones on LeetCode (88.5% vs 41.2%) and CodeContests (72.0% vs 7.90%). On HumanEval the two rates are similar (70.1% vs 72.5%), which motivates separating algorithm synthesis from functionality synthesis.
  • The LLM-generated reference oracles were judged correct for 88.5% of benchmark problems.
  • The oracles' verdicts on candidate programs matched the online judge's verdicts about 75% of the time.
  • Gains in one-submission pass rate with ALGO:
    • Codex: 8×
    • CodeT: 2.6×
    • PG-TD: 1.5×
    • ChatGPT Code Interpreter: 1.3×
  • The problem set, prompts, verifier and solution programs, and generated test cases are released at github.com/zkx06111/ALGO (NeurIPS 2023).

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

🎓Carnegie Mellon UniversityPittsburgh · United States539 works · 179,533 citations🎓University of California, Santa BarbaraSanta Barbara · United States57 works · 9,752 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksInformation Systems · 1,437 worksSoftware · 92 worksComputer Science Applications · 102 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Kexun Zhang, Danqing Wang, Jingtao Xia, William Yang Wang and Lei Li. 2023. ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers. arXiv:2305.14591.

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

@misc{zhang2023algo,
  title = {{ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers}},
  author = {Kexun Zhang, Danqing Wang, Jingtao Xia, William Yang Wang and Lei Li},
  year = {2023},
  doi = {10.48550/arxiv.2305.14591},
  eprint = {2305.14591},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2305.14591}
}

References

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

  1. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021.
  2. Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow, March 2021. URL https://doi.org/10.5281/zenodo.5297715. If you use this software, please cite it using these metadata. — [doi:10.5281/zenodo.5297715](https://doi.org/10.5281/zenodo.5297715) ↗
  3. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712, 2023.
  4. Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. Codet: Code generation with generated tests. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id= ktrw68Cmu9c. ↗
  5. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
  6. Qiaochu Chen, Shankara Pailoor, Celeste Barnaby, Abby Criswell, Chenglong Wang, Greg Durrett, and Işil Dillig. Type-directed synthesis of visualizations from natural language queries. Proceedings of the ACM on Programming Languages, 6(OOPSLA2):532–559, 2022. find
  7. Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128, 2023. find
  8. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. find
  9. Elizabeth Dinella, Gabriel Ryan, Todd Mytkowicz, and Shuvendu K Lahiri. Toga: a neural method for test oracle generation. In Proceedings of the 44th International Conference on Software Engineering, pp. 2130–2141, 2022. find
  10. Alex Gu, Tamara Mitrovska, Daniela Velez, Jacob Andreas, and Armando Solar-Lezama. Obsynth: An interactive synthesis system for generating object models from natural language specifications. arXiv preprint arXiv:2210.11468, 2022. — [arXiv:2210.11468](https://arxiv.org/abs/2210.11468) find
  11. Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with apps. NeurIPS, 2021.
  12. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve. arXiv preprint arXiv:2210.11610, 2022.
  13. Jeevana Priya Inala, Chenglong Wang, Mei Yang, Andres Codas, Mark Encarnación, Shuvendu Lahiri, Madanlal Musuvathi, and Jianfeng Gao. Fault-aware neural code rankers. Advances in Neural Information Processing Systems, 35:13419–13432, 2022. find
  14. Susmit Jha and Sanjit A Seshia. A theory of formal synthesis via inductive learning. Acta Informatica, 54:693–726, 2017. find
  15. Darren Key, Wen-Ding Li, and Kevin Ellis. I speak, you verify: Toward trustworthy neural program synthesis. arXiv preprint arXiv:2210.00848, 2022. — [arXiv:2210.00848](https://arxiv.org/abs/2210.00848) find
  16. Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy S Liang. Spoc: Search-based pseudocode to code. Advances in Neural Information Processing Systems, 32, 2019. find
  17. Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624):1092–1097, 2022.
  18. Shaoying Liu and Shin Nakajima. Automatic test case and test oracle generation based on functional scenarios in formal specifications for conformance testing. IEEE Transactions on Software Engineering, 48(2):691–712, 2020. find
  19. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651, 2023. find
  20. Zohar Manna and Richard Waldinger. A deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems (TOPLAS), 2(1):90–121, 1980. find
  21. Hussein Mozannar, Gagan Bansal, Adam Fourney, and Eric Horvitz. Reading between the lines: Modeling user behavior and costs in ai assisted programming. arXiv preprint arXiv:2210.14306, 2022. — [arXiv:2210.14306](https://arxiv.org/abs/2210.14306) find
  22. Ansong Ni, Srini Iyer, Dragomir Radev, Veselin Stoyanov, Wen-tau Yih, Sida Wang, and Xi Victoria Lin. Lever: Learning to verify language-to-code generation with execution. In International Conference on Machine Learning, pp. 26106–26128. PMLR, 2023.
  23. Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?… ↗
  24. Lin Padgham, Zhiyong Zhang, John Thangarajah, and Tim Miller. Model-based test oracle generation for automated unit testing of agent systems. IEEE Transactions on Software Engineering, 39(9):1230–1244, 2013. find
  25. Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 107–126, 2015. find
  26. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. find
  27. Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I Wang. Natural language to code translation with execution. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 3533–3546, 2022. find
  28. Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. From program verification to program synthesis. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’10, pp. 313–326, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9… — [doi:10.1145/1706299.1706337](https://doi.org/10.1145/1706299.1706337) find
  29. Saurabh Srivastava, Sumit Gulwani, and Jeffrey Foster. Template-based program verification and program synthesis. International Journal on Software Tools for Technology Transfer, 15, 04 2013. doi: 10.1007/s10009-012-0223-4. — [doi:10.1007/s10009-012-0223-4](https://doi.org/10.1007/s10009-012-0223-4) find
  30. Danqing Wang and Lei Li. Learn from mistakes through cooperative interaction with study assistant. The 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP) 2022, 2023. find
  31. Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B. Tenenbaum, and Chuang Gan. Planning with large language models for code generation. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum? id=Lr8cOOtYbfL. ↗
  32. Tianyi Zhang, Tao Yu, Tatsunori Hashimoto, Mike Lewis, Wen-tau Yih, Daniel Fried, and Sida Wang. Coder reviewer reranking for code generation. In International Conference on Machine Learning, pp. 41832–41846. PMLR, 2023. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2023-algo-synthesizing-algorithmic-programs-llm/