Elamur Research
☰
home / papers / 2022 / Competition-Level Code Generation with AlphaCode

Competition-Level Code Generation with AlphaCode

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2203.07814

Summary

Large language models can already write short code snippets. Full competitive programming problems are much harder: the model has to read a long problem statement, choose an algorithm and write a complete program that passes hidden tests. AlphaCode, from DeepMind, tackles this setting. Transformer models are pre-trained on a selection of GitHub code and then fine-tuned on CodeContests, a new competitive programming dataset the authors release. CodeContests is split by time so that every evaluation problem was published after the training data, and it adds generated tests so that wrong programs are much less likely to be accepted. For each problem the system generates a very large number of candidate programs. It discards those that fail the example tests in the statement, then groups the survivors by how they behave and submits at most 10. In simulated Codeforces contests AlphaCode placed around the median human competitor. It is the first strong evidence that code generation can handle problems needing real algorithmic reasoning, and the paper also shows that careful dataset design is essential for honest evaluation.

Key points

  • Across 10 simulated Codeforces contests, each with over 5,000 participants, AlphaCode placed on average in the top 54.3%. This gives an estimated rating of 1238, which puts it in the top 28% of users active in the previous 6 months.
  • On held-out CodeContests problems, the best model solves 34.2% with at most 10 submissions per problem. Earlier reported solve rates on existing benchmarks such as APPS were roughly 1–5%.
  • In existing datasets, 30–60% of programs that pass all tests are actually incorrect. The extra tests in CodeContests cut this false positive rate to about 4%.
  • The authors name three components as critical: the clean CodeContests dataset, large transformer models that are efficient to sample from, and massive sampling followed by filtering and clustering.
  • Analysis found no evidence that AlphaCode copies key parts of solutions from its training data. A stripped-down version of the model performs about as well as Codex.

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: Computing & GPUs

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1126/science.abq1158 · arXiv 2203.07814

@misc{li2022competition,
  title = {{Competition-Level Code Generation with AlphaCode}},
  author = {Li, Yujia and Choi, David and Chung, Junyoung and Kushman, Nate and Schrittwieser, Julian and Leblond, Rémi and Eccles, Tom and Keeling, James and Gimeno, Felix and Lago, Agustin Dal and Hubert, Thomas and Choy, Peter and d'Autume, Cyprien de Masson and Babuschkin, Igor and Chen, Xinyun and Huang, Po-Sen and Welbl, Johannes and Gowal, Sven and Cherepanov, Alexey and Molloy, James and Mankowitz, Daniel J. and Robson, Esme Sutherland and Kohli, Pushmeet and Freitas, Nando de and Kavukcuoglu, Koray and Vinyals, Oriol},
  year = {2022},
  doi = {10.1126/science.abq1158},
  eprint = {2203.07814},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1126/science.abq1158}
}

References

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

  1. Albert Ziegler. Research recitation: A first look at rote learning in GitHub Copilot suggestions. https://docs.github.com/en/github/copilot/research-recitation , 2021. Accessed: 2022-01-13. ↗
  2. M. Allamanis. The adverse effects of code duplication in machine learning models of code. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, pages 143–153, 2019. find
  3. J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. find our card
  4. G. A. Aye, S. Kim, and H. Li. Learning autocompletion from real-world datasets. In 2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), pages 131–139. find
  5. M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow. DeepCoder: Learning to write programs. arXiv preprint arXiv:1611.01989, 2016. find
  6. S. Borgeaud, A. Mensch, J. Hoffmann, T. Cai, E. Rutherford, K. Millican, G. van den Driessche, J.-B. Lespiau, B. Damoc, A. Clark, D. de Las Casas, A. Guy, J. Menick, R. Ring, T. Hennigan, S. Huang, L. Maggiore, C. Jones, A. Cassirer, A. Brock, M. Paganini, G. Irving, O. Vinyals, S. Osindero, K. Simo… find
  7. J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/google/jax . ↗
  8. T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005.14165, 2020. find
  9. M. Bruch, M. Monperrus, and M. Mezini. Learning from examples to improve code completion systems. In Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering, pages 213–222, 2009. \#\# 14 Work conducte… find
  10. E. Caballero, OpenAI, and I. Sutskever. Description2Code Dataset, 8 2016. URL https://github. com/ethancaballero/description2code . find
  11. N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650, 2021. find our card
  12. M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. find our card
  13. C. B. Clement, D. Drain, J. Timcheck, A. Svyatkovskiy, and N. Sundaresan. PyMT5: multi-mode translation of natural language and Python code with transformers. arXiv preprint arXiv:2010.03150, 2020. find
  14. K. Cobbe, V. Kosaraju, M. Bavarian, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. find our card
  15. R. Dabre and A. Fujita. Softmax tempering for training neural machine translation models. arXiv prepring arXiv:2009.09372, 2020. — [arXiv:2009.09372](https://arxiv.org/abs/2009.09372) find
  16. J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A.-r. Mohamed, and P. Kohli. RobustFill: Neural program learning under noisy I/O. In International conference on machine learning, pages 990–998. PMLR, 2017. find
  17. J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018. find
  18. I. Drori and N. Verma. Solving linear algebra by program synthesis. arXiv preprint arXiv:2111.08171, 2021. — [arXiv:2111.08171](https://arxiv.org/abs/2111.08171) find
  19. A. Ebtekar. How to interpret contest ratings. https://codeforces.com/blog/entry/68288 , 2021. Accessed: 2021-12-04. ↗
  20. S. Edunov, M. Ott, M. Auli, and D. Grangier. Understanding back-translation at scale. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 489–500, Brussels, Belgium, Oct.-Nov. 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18-1045. URL… find
  21. Facebook Hacker Cup. Facebook hacker cup. https://www.facebook.com/ codingcompetitions/hacker-cup , 2021. Accessed: 2021-12-09. ↗
  22. A. Fan, M. Lewis, and Y. Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2018. find
  23. Z. Feng, D. Guo, D. Tang, N. Duan, X. Feng, M. Gong, L. Shou, B. Qin, T. Liu, D. Jiang, et al. CodeBERT: a pre-trained model for programming and natural languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings, pages 1536–1547, 2020. find our card
  24. J. Ganitkevitch, B. Van Durme, and C. Callison-Burch. PPDB: The paraphrase database. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 758–764, Atlanta, Georgia, June 2013. Association for Computat… find our card
  25. D. gal Gershgorn. ground. GitHub’s automatic coding tool rests on untested le-https://www.theverge.com/2021/7/7/22561180/ github-copilot-legal-copyright-fair-use-public-code , 2021. Accessed: 2022-01-10. find
  26. Google Code Jam. Google Code Jam. codejam , 2021. Accessed: 2021-12-09. https://codingcompetitions.withgoogle.com/ ↗
  27. C. C. Green. Application of theorem proving to problem solving. In IJCAI, 1969. find
  28. S. Gulwani. Automating string processing in spreadsheets using input-output examples. ACM Sigplan Notices, 46(1):317–330, 2011. find
  29. S. Gulwani, O. Polozov, R. Singh, et al. Program synthesis. Foundations and Trends® in Programming Languages, 4(1-2):1–119, 2017. find
  30. D. Guo, A. Svyatkovskiy, J. Yin, N. Duan, M. Brockschmidt, and M. Allamanis. Learning to generate code sketches. arXiv preprint arXiv:2106.10158, 2021. — [arXiv:2106.10158](https://arxiv.org/abs/2106.10158) find
  31. D. Hendrycks, S. Basart, S. Kadavath, M. Mazeika, A. Arora, E. Guo, C. Burns, S. Puranik, H. He, D. Song, et al. Measuring coding challenge competence with APPS. arXiv preprint arXiv:2105.09938, 2021. find our card
  32. T. Hennigan, T. Cai, T. Norman, and I. Babuschkin. Haiku: Sonnet for JAX, 2020. URL http: //github.com/deepmind/dm-haiku . find
  33. A. Hindle, E. T. Barr, Z. Su, M. Gabel, and P. Devanbu. On the naturalness of software. In Proceedings of the 34th International Conference on Software Engineering, pages 837–847, 2012. find
  34. A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. In Proceedings of the 7 𝑡ℎ International Conference on Learning Representations (ICLR), 2019. find