Competition-Level Code Generation with AlphaCode

Created by W.Langdon from gp-bibliography.bib Revision:1.7630

@TechReport{competition_level_code_generation_with_alphacode,

• author = "Yujia Li and David Choi and Junyoung Chung and Nate Kushman and Julian Schrittwieser and Remi Leblond and Tom Eccles and James Keeling and Felix Gimeno and Agustin Dal Lago and Thomas Hubert and Peter Choy and Cyprien de Masson d'Autume and Igor Babuschkin and Xinyun Chen and Po-Sen Huang and Johannes Welbl and Sven Gowal and Alexey Cherepanov and James Molloy and Daniel J. Mankowitz and Esme Sutherland Robson and Pushmeet Kohli and Nando de Freitas and Koray Kavukcuoglu and Oriol Vinyals",
• title = "Competition-Level Code Generation with {AlphaCode}",
• institution = "Google DeepMind",
• year = "2022",
• month = "2 " # feb,
• keywords = "genetic algorithms, genetic programming, C++, C#, Go, Java, JavaScript, Lua, PHP, Python, Ruby, Rust, Scala, TypeScript, GitHub, Codeforces, Description2Code, CodeNet, Jax, Haiku, TPUv4 (GPU), bloat16, SentencePiece tokenize, AdamW, Tempering regularization, GOLD, Clustering",
• URL = "https://storage.googleapis.com/deepmind-media/AlphaCode/competition_level_code_generation_with_alphacode.pdf",
• URL = "https://arxiv.org/abs/2203.07814",
• code_url = "https://github.com/deepmind/code_contests",
• size = "73 pages",
• 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, Alpha-Code achieved on average a ranking of top 54.3 percent in programming competitions with more than 5000 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.",
• notes = "NOT GP

  See also Li et al.,Science 378, 1092--1097 (2022) 9 December 2022 DOI: 10.1126/science.abq115

  pre-training dataset 715.1 GB of code

  p7 'Fine-tuning the model on a dedicated competitive programming dataset is critical for performance'

  'high-quality test cases are not readily available'

  '{"}slow positives{"} where correct but algorithmically inefficient'

  'We reduced the false positive rates of our dataset by generating additional test cases, created by mutating existing test inputs'

  sequence-to-sequence, eg NLP to Java, encoder(1536 tokens)-decoder(768 tokens) transformer architecture. AlphaCode 41B 41.1B parameters.

  CodeContests: train on both ok and bad answers.

  'perhaps because there are many ways solutions can be incorrect while correct solutions tend to behave the same and so are grouped into larger clusters' Anna Karenina (by Leo Tolstoy).

  p16 'Solve rates scale log-linearly with more samples.' 'Solve rates scale log-linearly with more compute.'

  p21 'boilerplate code for reading and parsing the input data format, rather than key logic for solving problems'.

  p22 'AlphaCode generates approximately the same amount of dead code as humans.'

  p29 'Improving human readable code generation'

  p30 'no knowledge of coding is required to create software.' 'Interpretability makes code generation safer for real-world environments and for fairer machine learning.' 'Generalization.' 'outdated APIs'

  'required hundreds of petaFLOPS days'

  p31 'Coding capabilities could lead to [Artificial Intelligence] systems that can recursively write and improve themselves, rapidly leading to more and more advanced [AI] systems.'

  ",

}

Genetic Programming entries for Yujia Li David Choi Junyoung Chung Nate Kushman Julian Schrittwieser Remi Leblond Tom Eccles James Keeling Felix Gimeno Agustin Dal Lago Thomas Hubert Peter Choy Cyprien de Masson d'Autume Igor Babuschkin Xinyun Chen Po-Sen Huang Johannes Welbl Sven Gowal Alexey Cherepanov James Molloy Daniel J Mankowitz Esme Sutherland Robson Pushmeet Kohli Nando de Freitas Koray Kavukcuoglu Oriol Vinyals

Citations