Competition-Level Code Generation with AlphaCode (Paper Review)

#ai #alphacode #deepmind

AlphaCode is an automated system that can solve competitive programing exercises. The authors found an interesting combination of language models, large-scale sampling, and clever techniques to filter and subsequently cluster the resulting programs, which lets the system perform on the level of an average competitor in real competitions. In this video, we take a deep dive into AlphaCode's design, architecture, and experimental evaluation. The paper is very well structured and the empirical results are super interesting!

OUTLINE: 0:00 - Intro 2:10 - Paper Overview 3:30 - An example problem from competitive programming 8:00 - AlphaCode system overview 14:00 - Filtering out wrong solutions 17:15 - Clustering equivalent generated programs 21:50 - Model configurations & engineering choices 24:30 - Adding privileged information to the input & more tricks 28:15 - Experimental Results (very interesting!)

Paper: https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf Code: https://github.com/deepmind/code_contests

Abstract: Programming is a powerful and ubiquitous problem-solving tool. Developing systems that can assist programmers or even generate programs independently could make programming more productive and accessible, yet so far incorporating innovations in AI has proven challenging. Recent large-scale language models have demonstrated an impressive ability to generate code, and are now able to complete simple programming tasks. However, these models still perform poorly when evaluated on more complex, unseen problems that require problem-solving skills beyond simply translating instructions into code. For example, competitive programming problems which require an understanding of algorithms and complex natural language remain extremely challenging. To address this gap, we introduce AlphaCode, a system for code generation that can create novel solutions to these problems that require deeper reasoning. Evaluated on recent programming competitions on the Codeforces platform, AlphaCode achieved on average a ranking of top 54.3% in programming competitions with more than 5,000 participants. We found that three key components were critical to achieve good and reliable performance: (1) an extensive and clean competitive programming dataset for training and evaluation, (2) large and efficient-to-sample transformer-based architectures, and (3) large-scale model sampling to explore the search space, followed by filtering based on program behavior to a small set of submissions.

Authors: Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’ ... https://www.youtube.com/watch?v=s9UAOmyah1A