1 of 21

Competition-Level Code Generation with AlphaCode

by Deepmind, 2022

Presented by Yuheng Wang

2 of 21

Motivation

Recent large-scale transformer-based language models have successfully generated code that solves simple programming problems in Python, e.g. Codex
However, problems used in Codex consists of simple descriptions with short solutions - far from the full complexity of real-world programming

Short code snippets: translating the task specification directly into code
Entire program: understanding the task and figuring out how to accomplish it, which requires deeper algorithmic reasoning

3 of 21

Competitive programming

Typical Examples: ACM International Collegiate Programming Competition (ICPC), International Olympiad in Informatics (IOI)
Represents a significant step towards real-world programming, and requires

Understanding complex natural language descriptions
Reasoning about previously unseen problems
Mastering a wide range of algorithms and data structures
Precisely implementing solution that can span hundreds of lines

4 of 21

Competitive programming

The popular Codeforces platform, used throughout the paper, has more than 500,000 active users and holds weekly competitions with tens of thousands of participants

Implementation efficiency matters
Rankings with human competitors

5 of 21

Seq2seq machine translation model based on Transformer

Time1

Encoder

Input: I love you.
Output: relevant vectors for I love you.

Decoder

input: <empty>
Output: 我

Time2

Encoder

Input: I love you.
Output: relevant vectors for I love you.

Decoder

Input: 我
Output: 我爱

6 of 21

Seq2seq machine translation model based on Transformer

Time3

Encoder

Input: I love you.
Output: relevant vectors for I love you.

Decoder

Input: 我爱
Output: 我爱你

Time4

Encoder

Input: I love you.
Output: relevant vectors for I love you.

Decoder

Input: 我爱你
Output: 我爱你。

7 of 21

Datasets for AlphaCode

Dataset for encoder and decoder pre-training

Open-source code from Github

Dataset for fine-tuning

CodeContests

9 of 21

CodeContests data

Scraped from Codeforces

10 of 21

CodeContests

Positive examples

The solutions that pass all the hidden test cases

High false positive rate problem

Hidden test cases can not cover all possible situations

Solution to high false positive rate problem

Generating additional test cases

mutating existing test inputs (flipping binary input, randomly incrementing or decrementing integers)
Run 30 correct programs on those mutated inputs, and use the inputs that have 30 identical outputs

11 of 21

The AlphaCode framework

Pre-train a transformer-based language model on GitHub code
Fine-tune the model on CodeContests
Generate a very large number of samples from the models for each problem
Filter the samples to obtain a small set of candidate submissions, to be evaluated on the hidden test cases

12 of 21

Encoder pre-training

13 of 21

Decoder pre-training

Harry

fantasy

14 of 21

Fine-tuning

Dataset

CodeContests

Encoder

Natural language description

Decoder

Program solution

15 of 21

Fine-tuning

Metadata conditioning and prediction

CodeContests contains both correct and incorrect submissions. Also, difficulty ratings, language used, and what kind of algorithms may be used for the problem are included
Add these types information to the head of problem descriptions
Through these auxiliary tasks, the model is able to better discriminate between correct submissions and incorrect ones, between python and C++, between dynamic programming and depth-first search

Masked word prediction

Correctness Prediction

Language Type Prediction

16 of 21

Large scale sampling

It is not in the training phase any more
At sampling time, we are not able to access all of the metadata, so we randomly generate metadata to guide the model to generate various samples
This means, in the sampling phase, if we

Randomly generate a rating (e.g. 1,200), a tag combination (e.g. dp and implementation), a language (e.g. Python), and add such info to the head, plus a line of “CORRECT SOLUTION”

Then, the model will tends to generate a correct dp program written in Python with similar difficulty of 1200

17 of 21

Filtering

Even though we have a large number of samples now, only 10 submissions are allowed for one problem to mimic real competition environment
Filtering out a large portion of samples is necessary
Idea

Only keep those that pass the example tests

18 of 21

Clustering

Filtering can still leave thousands of program samples per problem
Another discovery

Many program samples are syntactically different but semantically equivalent

Method

Trained a separate test input generator (same arch as the main model)
This generator predicts test input from problem descriptions and example/hidden/generated test inputs

Clustering

Predicted input [1,2,3]
Outputs after running sample1, sample2, sample3: [3,2,1], [3,2,1], [3,1,2]
Result: cluster1: (sample1, sample2), cluster2: (sample3)

Select one solution from each cluster from largest to smallest

Final submission: sample2, sample3

19 of 21

Evaluation

On CodeContests

pass@k: the percentage of problems solved when we take k samples from the model and submit all of them for evaluation on the hidden tests. If any solution in the specified sample budge solves a problem, the problem is counted as solved. This metric measures mostly the search aspect of the sampling process
n@k: the percentage of problems solved when we take k samples from the model for each problem but can only submit n=10 of them for evaluation on the hidden tests. This measures factors including the filtering process and how models behave at a very large number of samples

20 of 21