---
title: "ALGO — paper by Zhang et al. (2023) — summary and ideas"
description: "It builds on an observation: writing a slow, exhaustive brute-force solution is far easier for an LLM… 32 references, cited by 17 papers here."
authors: ["Kexun Zhang", "Danqing Wang", "Jingtao Xia", "William Yang Wang", "Lei Li"]
year: 2023
venue: "arXiv:2305.14591"
source: "https://arxiv.org/abs/2305.14591"
doi: "10.48550/arxiv.2305.14591"
arxiv: "2305.14591"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/zhang-2023-algo-synthesizing-algorithmic-programs-llm/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/zhang-2023-algo-synthesizing-algorithmic-programs-llm/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/) / ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers

# ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers

**Authors:** Kexun Zhang, [Danqing Wang](https://md.research.elamur.ai/free/en/authors/danqing-wang/), Jingtao Xia, [William Yang Wang](https://md.research.elamur.ai/free/en/authors/william-yang-wang/) and [Lei Li](https://md.research.elamur.ai/free/en/authors/lei-li/) · **Year:** 2023 · **Venue:** arXiv:2305.14591 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

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

**Citations:** 2 citations (OpenAlex, 2026-10-14) · [17](https://md.research.elamur.ai/free/en/papers/zhang-2023-algo-synthesizing-algorithmic-programs-llm/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 University](https://md.research.elamur.ai/free/en/universities/carnegie-mellon-university/) — University, Pittsburgh, United States · 539 works · 179,533 citations
- [University of California, Santa Barbara](https://md.research.elamur.ai/free/en/universities/university-of-california-santa-barbara/) — University, Santa Barbara, United States · 57 works · 9,752 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🗄️ Information Systems](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) · 1,437 works · [💻 Software](https://md.research.elamur.ai/free/en/shelves/computer-science/software/) · 92 works · [🖥️ Computer Science Applications](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-science-applications/) · 102 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 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.

```bibtex
@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}
}
```

- [← previous VoxArabica: A Robust Dialect-Aware Arabic Speech Recognition System](https://md.research.elamur.ai/free/en/papers/waheed-2023-voxarabica-robust-dialect-aware-arabic/)
- [next → An Empirical Study of Metrics to Measure Representational Harms in Pre-Trained Language Models](https://md.research.elamur.ai/free/en/papers/hosseini-2023-empirical-study-metrics-measure-representational/)
- [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/)

## 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](https://md.research.elamur.ai/free/en/papers/austin-2021-program-synthesis-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) [↗](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](https://md.research.elamur.ai/free/en/papers/bubeck-2023-sparks-artificial-general-intelligence-early/). 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=](https://openreview.net/forum?id=) ktrw68Cmu9c. [↗](https://openreview.net/forum?id=)
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](https://md.research.elamur.ai/free/en/papers/chen-2021-evaluating-large-language-models-trained/). 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](https://scholar.google.com/scholar?q=Qiaochu+Chen%2C+Shankara+Pailoor%2C+Celeste+Barnaby%2C+Abby+Criswell%2C+Chenglong+Wang%2C+Greg+Durrett%2C+and+Is%CC%A7il+Dillig%2E+Type%2Ddirected+synthesis+of+visualizations+from+natural+language+queries%2E+Proceedings+of+)
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](https://scholar.google.com/scholar?q=Xinyun+Chen%2C+Maxwell+Lin%2C+Nathanael+Sch%C3%A4rli%2C+and+Denny+Zhou%2E+Teaching+large+language+models+to+self%2Ddebug%2E+arXiv+preprint+arXiv%3A2304%2E05128%2C+2023%2E)
8. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022. [find](https://scholar.google.com/scholar?q=Thomas+H+Cormen%2C+Charles+E+Leiserson%2C+Ronald+L+Rivest%2C+and+Clifford+Stein%2E+Introduction+to+algorithms%2E+MIT+press%2C+2022%2E)
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](https://scholar.google.com/scholar?q=Elizabeth+Dinella%2C+Gabriel+Ryan%2C+Todd+Mytkowicz%2C+and+Shuvendu+K+Lahiri%2E+Toga%3A+a+neural+method+for+test+oracle+generation%2E+In+Proceedings+of+the+44th+International+Conference+on+Software+Engineering%2C+p)
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](https://scholar.google.com/scholar?q=Alex+Gu%2C+Tamara+Mitrovska%2C+Daniela+Velez%2C+Jacob+Andreas%2C+and+Armando+Solar%2DLezama%2E+Obsynth%3A+An+interactive+synthesis+system+for+generating+object+models+from+natural+language+specifications%2E+arXiv+pre)
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](https://md.research.elamur.ai/free/en/papers/hendrycks-2021-measuring-coding-challenge-competence-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](https://md.research.elamur.ai/free/en/papers/huang-2023-large-language-models-can-self/). 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](https://scholar.google.com/scholar?q=Jeevana+Priya+Inala%2C+Chenglong+Wang%2C+Mei+Yang%2C+Andres+Codas%2C+Mark+Encarnaci%C3%B3n%2C+Shuvendu+Lahiri%2C+Madanlal+Musuvathi%2C+and+Jianfeng+Gao%2E+Fault%2Daware+neural+code+rankers%2E+Advances+in+Neural+Information+Pr)
14. Susmit Jha and Sanjit A Seshia. A theory of formal synthesis via inductive learning. Acta Informatica, 54:693–726, 2017. [find](https://scholar.google.com/scholar?q=Susmit+Jha+and+Sanjit+A+Seshia%2E+A+theory+of+formal+synthesis+via+inductive+learning%2E+Acta+Informatica%2C+54%3A693%E2%80%93726%2C+2017%2E)
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](https://scholar.google.com/scholar?q=Darren+Key%2C+Wen%2DDing+Li%2C+and+Kevin+Ellis%2E+I+speak%2C+you+verify%3A+Toward+trustworthy+neural+program+synthesis%2E+arXiv+preprint+arXiv%3A2210%2E00848%2C+2022%2E+%E2%80%94+%5BarXiv%3A2210%2E00848%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2210%2E00848)
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](https://scholar.google.com/scholar?q=Sumith+Kulal%2C+Panupong+Pasupat%2C+Kartik+Chandra%2C+Mina+Lee%2C+Oded+Padon%2C+Alex+Aiken%2C+and+Percy+S+Liang%2E+Spoc%3A+Search%2Dbased+pseudocode+to+code%2E+Advances+in+Neural+Information+Processing+Systems%2C+32%2C+2019%2E)
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](https://md.research.elamur.ai/free/en/papers/li-2022-competition-level-code-generation-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](https://scholar.google.com/scholar?q=Shaoying+Liu+and+Shin+Nakajima%2E+Automatic+test+case+and+test+oracle+generation+based+on+functional+scenarios+in+formal+specifications+for+conformance+testing%2E+IEEE+Transactions+on+Software+Engineering)
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](https://scholar.google.com/scholar?q=Aman+Madaan%2C+Niket+Tandon%2C+Prakhar+Gupta%2C+Skyler+Hallinan%2C+Luyu+Gao%2C+Sarah+Wiegreffe%2C+Uri+Alon%2C+Nouha+Dziri%2C+Shrimai+Prabhumoye%2C+Yiming+Yang%2C+et+al%2E+Self%2Drefine%3A+Iterative+refinement+with+self%2Dfeedbac)
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](https://scholar.google.com/scholar?q=Zohar+Manna+and+Richard+Waldinger%2E+A+deductive+approach+to+program+synthesis%2E+ACM+Transactions+on+Programming+Languages+and+Systems+%28TOPLAS%29%2C+2%281%29%3A90%E2%80%93121%2C+1980%2E)
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](https://scholar.google.com/scholar?q=Hussein+Mozannar%2C+Gagan+Bansal%2C+Adam+Fourney%2C+and+Eric+Horvitz%2E+Reading+between+the+lines%3A+Modeling+user+behavior+and+costs+in+ai+assisted+programming%2E+arXiv+preprint+arXiv%3A2210%2E14306%2C+2022%2E+%E2%80%94+%5BarXiv%3A)
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](https://md.research.elamur.ai/free/en/papers/ni-2023-lever-learning-verify-language-code/). 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?…](https://openreview.net/forum?…) [↗](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](https://scholar.google.com/scholar?q=Lin+Padgham%2C+Zhiyong+Zhang%2C+John+Thangarajah%2C+and+Tim+Miller%2E+Model%2Dbased+test+oracle+generation+for+automated+unit+testing+of+agent+systems%2E+IEEE+Transactions+on+Software+Engineering%2C+39%289%29%3A1230%E2%80%931244)
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](https://scholar.google.com/scholar?q=Oleksandr+Polozov+and+Sumit+Gulwani%2E+Flashmeta%3A+A+framework+for+inductive+program+synthesis%2E+In+Proceedings+of+the+2015+ACM+SIGPLAN+International+Conference+on+Object%2DOriented+Programming%2C+Systems%2C+La)
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](https://scholar.google.com/scholar?q=Alec+Radford%2C+Jeffrey+Wu%2C+Rewon+Child%2C+David+Luan%2C+Dario+Amodei%2C+Ilya+Sutskever%2C+et+al%2E+Language+models+are+unsupervised+multitask+learners%2E+OpenAI+blog%2C+1%288%29%3A9%2C+2019%2E)
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](https://scholar.google.com/scholar?q=Freda+Shi%2C+Daniel+Fried%2C+Marjan+Ghazvininejad%2C+Luke+Zettlemoyer%2C+and+Sida+I+Wang%2E+Natural+language+to+code+translation+with+execution%2E+In+Proceedings+of+the+2022+Conference+on+Empirical+Methods+in+Nat)
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](https://scholar.google.com/scholar?q=Saurabh+Srivastava%2C+Sumit+Gulwani%2C+and+Jeffrey+S%2E+Foster%2E+From+program+verification+to+program+synthesis%2E+In+Proceedings+of+the+37th+Annual+ACM+SIGPLAN%2DSIGACT+Symposium+on+Principles+of+Programming+La)
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](https://scholar.google.com/scholar?q=Saurabh+Srivastava%2C+Sumit+Gulwani%2C+and+Jeffrey+Foster%2E+Template%2Dbased+program+verification+and+program+synthesis%2E+International+Journal+on+Software+Tools+for+Technology+Transfer%2C+15%2C+04+2013%2E+doi%3A+10%2E)
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](https://scholar.google.com/scholar?q=Danqing+Wang+and+Lei+Li%2E+Learn+from+mistakes+through+cooperative+interaction+with+study+assistant%2E+The+2023+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29+2022%2C+2023%2E)
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?](https://openreview.net/forum?) id=Lr8cOOtYbfL. [↗](https://openreview.net/forum?)
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](https://scholar.google.com/scholar?q=Tianyi+Zhang%2C+Tao+Yu%2C+Tatsunori+Hashimoto%2C+Mike+Lewis%2C+Wen%2Dtau+Yih%2C+Daniel+Fried%2C+and+Sida+Wang%2E+Coder+reviewer+reranking+for+code+generation%2E+In+International+Conference+on+Machine+Learning%2C+pp%2E+4183)

*Updated 31 October 2026*