PaperlayerView exact revision on arXiv

Source-linked AI summary

Competition-Level Code Generation with AlphaCode

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'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

arXiv:2203.07814v1cs.PLcs.AIcs.LG

TL;DR

Complex, unseen competitive-programming problems remain difficult for code-generation models because they require deeper algorithmic reasoning. AlphaCode combines large transformer models, extensive sampling, behavioral filtering, and candidate clustering, achieving an average ranking in the top 54.3% on recent Codeforces contests with over 5,000 participants.

  • Problem

    Code-generation models perform poorly on unseen competitive-programming problems requiring algorithmic understanding, efficient solutions, and complex natural-language comprehension.

  • Method

    AlphaCode fine-tunes large transformer models on curated competitive-programming data, then samples, filters, and clusters programs into a small submission set.

  • Results

    Top 54.3% was AlphaCode’s average ranking across 10 recent Codeforces contests with over 5,000 participants each.

  • Takeaways & Limitations

    Massive sampling with filtering and clustering, sampling-efficient architectures, and clean evaluation data were essential to AlphaCode’s performance.

  • Takeaways & Limitations

    The paper notes unresolved intellectual-property concerns surrounding large code-generation training corpora and the use and crediting of publicly available code.

Abstract

from arXiv · show

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. In simulated evaluations on recent programming competitions on the Codeforces platform, AlphaCode achieved on average a ranking of top 54.3% in 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.

1. Introduction

Competitive programming exposes the gap between generating short code snippets and solving unseen problems that require natural-language understanding, algorithmic reasoning, and precise implementation. AlphaCode addresses this gap with curated data, large transformer models, behavioral filtering, and large-scale sampling, achieving top-54.3% average ranking in simulated Codeforces contests.

  • Motivation: Generating complete programs remains difficult because the program space is huge, rewards are sparse, and small edits can radically change behavior.Judging whether partial or incorrect programs are useful is also challenging.
  • AlphaCode system: AlphaCode combines large transformer models, pre-training on selected GitHub code, fine-tuning on curated competitive-programming problems, large-scale sampling, and execution-based filtering.Remaining samples are clustered into a small set of submissions.
  • Evaluation: CodeContests1 supports rigorous evaluation by combining multiple data sources, temporally separating training and evaluation problems, and adding generated tests.The temporal split ensures evaluation problems postdate all training data.
  • Results: 54.3% average ranking was achieved by AlphaCode among participants in 10 recent Codeforces contests with over 5,000 participants each.The system’s estimated Codeforces rating was 1238, within the top 28% of users who participated during the last 6 months.
  • Analysis: AlphaCode creates original solutions rather than duplicating training-data code and relies heavily on natural-language problem descriptions.The analysis also examines solvable and unsolvable problem types and finds validation loss is a poor proxy for solve rate.

2. Problem setup

Competitive programming requires transforming natural-language problem descriptions into efficient algorithms and precise implementations that pass specified tests and constraints. AlphaCode is evaluated with a proxy metric that measures solving problems from sampled and filtered candidate submissions against hidden tests.

  • Problem-solving requirements: Solving competitive programming problems requires understanding the problem, reasoning about algorithms and data structures, and designing an efficient algorithm for stated input sizes and time limits.These requirements distinguish the task from prior work that explicitly specified what to implement.
  • Problem-solving requirements: Implementation must satisfy execution-time constraints, handle subtle edge cases, and express the solution in potentially over a hundred lines of precise code.Participants use small example test cases to debug, fix, and rerun candidate submissions before official submission.
  • Proxy evaluation: The evaluation metric measures the percentage of problems solved using n submissions from k samples, with a problem solved when any evaluated sample passes all hidden tests.Filtering may use only information available to competitors, such as example tests, rather than hidden tests.
  • Proxy evaluation: Limiting submissions to n models penalties for incorrect submissions, while fixing k enables comparisons and bootstrapping estimates n@k from a larger set of K≫k samples.Performance increases with the number of samples, motivating a fixed sample budget for evaluation.
  • Proxy evaluation: The competition setting uses 10@𝑘, while pass@k is the solve rate with k samples and an upper bound because it assumes all samples can be evaluated.The paper compares solve rates across different k values because low-budget and high-budget performance need not correlate.

3. Datasets

AlphaCode used broad GitHub code for pre-training and a curated CodeContests dataset for competitive-programming fine-tuning and evaluation. CodeContests strengthened test coverage through generated tests and filtering, reducing false positives from 62% to 4%.

  • Pre-training data: The pre-training corpus is a 2021/07/14 snapshot of selected public GitHub repositories spanning 12 programming languages.Files larger than 1MB or containing lines longer than 1000 characters were removed, as were whitespace-insensitive duplicate files.
  • Domain adaptation: Fine-tuning on a dedicated competitive-programming dataset was critical because GitHub-pretrained models solved few competitive-programming problems.GitHub pre-training still enabled good code generation and simple problem solving.
  • CodeContests dataset: CodeContests combines newly scraped Codeforces problems, solutions, and test cases with existing public datasets, including Description2Code and CodeNet.The dataset was created to facilitate fine-tuning and evaluation.
  • Test coverage: Generated tests and filtering reduced CodeContests’ false positive rate from 62% to 4%.Additional tests were created by mutating existing inputs, verifying mutations with 30 correct solutions, and retaining validation and test problems with at least 5 hidden or generated tests producing at least 2 outputs.

4. Approach

AlphaCode addresses competitive-programming code generation as search through a huge program space with sparse rewards and limited training examples. Its approach combines transformer pre-training and fine-tuning with large-scale sampling, behavioral filtering, and submission selection under a 10-submission limit.

  • Approach: AlphaCode pre-trains a transformer language model on GitHub code, then fine-tunes it on competitive-programming data to progressively reduce the program search space.Fine-tuning uses GOLD with tempering and compensates for the limited amount of competitive-programming data.
  • Sampling: Large-scale sampling followed by filtering is distinctive to AlphaCode and greatly improves problem solve rate, motivating design choices focused on efficient sampling.Multi-query attention reduces memory usage and cache-update costs, enabling larger sampling batches.
  • Architecture: The encoder-decoder transformer maps a natural-language problem description X to a programming-language solution Y, modeling p(Y|X) and sampling code autoregressively.The encoder receives the tokenized description, while the decoder generates tokens until an end-of-code token.
  • Fine-tuning: T = 0.2 tempering helps avoid fine-tuning overfitting by sharpening the training distribution and smoothing the inference distribution.Tempering divides output logits by a scalar temperature before softmax.
  • Candidate selection: 10 submissions per problem are selected after filtering removes approximately 99% of samples that fail the example tests.The limit applies regardless of how many samples are drawn, and filtering can still leave tens of thousands of candidates.
  • Candidate selection: Selecting one solution from each behavioral cluster, ordered from largest to smallest, performed best because correct solutions tend to share behavior and form larger clusters.When fewer than 10 clusters are available, selection repeats from the first cluster while skipping already selected samples.

5. Results

AlphaCode achieved competitive performance on Codeforces and solved substantial fractions of unseen CodeContests problems through large-scale sampling, with larger models, clustering, and targeted pre-training improving results. Performance scaled log-linearly with sampling and training compute, while architectural and filtering enhancements improved sampling efficiency and solution quality.

  • Codeforces: 54.3% was AlphaCode’s average top ranking across 10 Codeforces competitions when limited to 10 submissions per problem.The corresponding estimated Codeforces rating was 1238, within the top 28% of recent contest participants.
  • Codeforces: 48.8% was AlphaCode’s average top ranking when more than 10 submissions per problem were allowed.This setting used an actual average of 28.8 submissions for each problem solved, compared with 2.4 under the 10-submission limit.
  • CodeContests: 34.2% of unseen validation problems were solved with up to one million samples, while 100,000 samples solved 31.8% of validation and 29.6% of test problems.The validation and test sets were temporally disjoint from training, and the 41B model consistently outperformed the 9B model while clustering improved results.
  • Scaling: Solve rates scaled approximately log-linearly with sample count, training compute, and sampling compute, although higher solve rates required exponentially more samples.Larger models had higher scaling slopes and could reach the same solve rate with exponentially fewer samples than worse models.
  • Model design: The encoder-decoder model with multi-query attention significantly increased sampling speed while maintaining sample quality, and full multilingual GitHub pre-training outperformed Python-only or MassiveText pre-training.Any pre-training improved results over training from scratch on CodeContests.

6. AlphaCode’s capabilities & limitations

AlphaCode’s analysis suggests that it generates novel solutions, responds to problem descriptions and metadata, and has characteristic strengths and weaknesses across program correctness and problem types. Validation loss can also misrepresent performance because solve rate may continue improving despite worsening validation loss.

  • Novelty and copying: The models do not appear to solve unseen problems by copying training solutions or exploiting obvious task-structure weaknesses.Qualitative analysis found no evidence that model-generated solutions copied core logic from training data.
  • Novelty and copying: Model and human solutions share training-data substrings at similar rates, with model overlaps mostly consisting of boilerplate input-parsing code rather than key solution logic.On CodeContests, approximately 3% of human solutions and less than 1% of model solutions had substrings longer than 600 characters.
  • Solution characteristics: AlphaCode tends to produce mostly syntactically correct Python programs, while C++ syntax is harder to master, and it generates dead code in its solutions.Dead code includes unused imports, functions, and classes removed using formatting and Python AST analysis.
  • Problem types: Solve rates improve with model scale, with relative strengths on bitmasks, sorting, mathematics, and greedy algorithms but weaknesses on dynamic programming and constructive algorithms.The comparison uses problem tags and reports overall improvement across tags as models become larger.
  • Conditioning sensitivity: The model uses problem descriptions and conditioning metadata: related but different problems sharply reduce solve rate, while tags change the algorithms it generates.The model is largely unaffected by changes that do not alter the underlying problem, and random tags with CORRECT conditioning are preferred when metadata is unavailable.
  • Conditioning sensitivity: 29 instead of 9 solutions were found with the “number theory” tag, while perfect loop-free solutions occurred 12 instead of 3 times.The comparison comes from 2048 samples and illustrates that tag conditioning can materially affect solve behavior.
  • Evaluation limitations: Solve rate continued improving well past 50k steps even as validation loss increased after about 50k steps, indicating validation loss is an unreliable performance proxy.The increasing validation loss normally suggests overfitting, but the target solve-rate metric continued to improve.

7. Related work

Related work spans classic program-synthesis methods, deep-learning and transformer-based code generation, and code completion. AlphaCode addresses the persistent challenge of scaling these approaches to complex competitive-programming problems, supported by suitable datasets and correctness-oriented evaluation.

  • Program synthesis: Classic program synthesis expresses tasks through natural language, input/output examples, or constraints, using deductive, example-based, and sketch-based approaches.Deductive synthesis uses theorem proving, input/output methods include FlashFill, and sketches constrain the target program’s structure.
  • Program synthesis: Deep-learning systems have mapped text to syntax trees and code, generated structured programs, guided search, produced sketches, translated pseudocode, and directly generated programs.These systems also generate programmatic policies in reinforcement-learning settings.
  • Code generation and completion: Scaling remains difficult because prior systems generally generated single-line suggestions, short programs, or narrow-domain code, increasing both search depth and width.Large transformers have advanced code retrieval, translation, and generation, while Codex showed strong completion of hand-specified Python functions from signatures and docstrings.
  • Competitive programming: Competitive-programming tasks are substantially more involved than prior code-generation benchmarks: median descriptions are 1,628 characters and solutions 606 characters, versus 396 and 148.5 for HumanEval.The supplied passage characterizes the HumanEval descriptions and solutions as about 4 times shorter.
  • Datasets and evaluation: Competitive-programming progress depends on datasets containing problems and solutions, including collections with multiple languages, correctness labels, and rich metadata.Earlier datasets contained a few thousand problems, while another converted solutions to an intermediate language that complicates use with pretrained models.

8. Broader impact

AlphaCode-like code generation could improve programming productivity, accessibility, education, and trust, but its broader impact also includes risks involving misuse, bias, security, environmental cost, intellectual property, automation, and advanced AI. Many proposed applications require future work, while safeguards remain necessary because positive intent alone does not mitigate harm.

  • Benefits: Human-readable code generation could improve developer productivity, programming accessibility, and education, although many real-world applications require future work.Potential applications include extended code completion, code optimization, alternative implementations, code-to-documentation tools, and natural-language programming.
  • Risks: Code generation could help bad actors create malware, amplify malicious coding productivity, and produce exploitable vulnerabilities, while also enabling threat defenders.Risks include outdated-code vulnerabilities and intentional weaknesses injected into training data.
  • Benefits: Generated code is relatively interpretable and can be analyzed for correctness, bias, and decisions using traditional methods, supporting safer and fairer deployment.Code itself is easier to inspect than neural-network behavior; sufficient testing can also support generalization to out-of-distribution inputs.
  • Risks: Training-data biases can reproduce stereotypes, reduce code quality, perpetuate bugs or outdated APIs, and disproportionately affect marginalized communities.These effects can also create performance and security issues and discourage adoption of newer libraries or programming languages.
  • Risks: Training and sampling large transformer-based models required hundreds of petaFLOPS days, creating substantial environmental costs despite cheap execution of synthesized programs.Once synthesized, programs can generally run cheaply on ordinary computers rather than requiring neural-network accelerators.
  • Risks: Broader deployment raises unresolved intellectual-property and programmer-automation concerns, while advanced coding systems could contribute to recursively self-improving AI risks.AlphaCode filters its dataset by licenses, but questions remain about crediting people’s code and possible changes in programmer demand.

9. Conclusion … A.2. Program judging

AlphaCode generates novel solutions to unseen competitive-programming problems and performs roughly at the median Codeforces competitor level. Its performance depends on large-scale sampling with filtering and clustering, while program judging uses execution-based checks with permissive handling of output formats and multiple-output cases.

  • 9. Conclusion: AlphaCode generates novel solutions to unseen competitive-programming problems and performs roughly at the level of the median Codeforces competitor.The system was evaluated on Codeforces.
  • 9. Conclusion: Massively scaling sampling, then filtering and clustering samples, is essential to AlphaCode’s performance alongside sampling-efficient transformer architectures.The architectures support large-scale sampling.
  • A.1. Hidden tests: Hidden test cases are held out from participants and are substantially longer and more demanding than the example tests used within AlphaCode.They are used to evaluate solution correctness.
  • A.2. Program judging: Programs are judged by executing them on test cases and comparing their outputs with expected correct outputs.This judging system is used both for final submissions and filtering, and is intended to emulate Codeforces judging within CodeContests.
  • A.2. Program judging: Program correctness can depend on case sensitivity, whitespace, formatting, floating-point precision, multiple valid outputs, and interactive inputs.These problem-specific rules make judging more difficult than exact output matching.
  • A.2. Program judging: Floating-point values within 10^-5 are treated as equivalent, string comparison is case insensitive, and whitespace differences are ignored.This permissive judging does not exactly match problem-specified formats, but the authors found the differences were not significant.
  • A.2. Program judging: About 1/4 of validation problems are classified heuristically as multiple-output problems and are judged against a single majority-human-solution output.These problems use the same permissive formatting rules.
  • A.2. Program judging: Interactive problems are not explicitly handled, potentially causing false negatives or false positives, although no interactive false positives were found.Interactive problems are substantially rarer than multiple-output problems.

A.3. Evaluation metrics … B.2. Dataset cleaning

The paper evaluates performance with n@k solve rates, estimated through sampling procedures and bootstrap confidence intervals, while using specialized handling for clustering results. Its datasets are cleaned through deduplication, code normalization, and execution-based filtering, and the GitHub pre-training corpus contains 715GB of code.

  • A.3. Evaluation metrics: n@k measures the fraction of problems solved when a model generates k samples but submits only n for evaluation.
  • A.3. Evaluation metrics: The single-model n@k estimate averages solve rates across S subsamples of size k drawn without replacement from K≥k samples.
  • A.3. Evaluation metrics: Scaling curves calculate n@k for different k values using the same set of K samples.
  • A.3. Evaluation metrics: 95% confidence intervals for ablation results use bootstrap re-sampling of trained models and their samples, reporting the 2.5th and 97.5th percentiles.
  • A.3. Evaluation metrics: Clustering results use five subsamples per k for each model, averaging the resulting five data points across trained models.
  • B.1. GitHub dataset composition: 715GB of code across multiple programming languages comprise the GitHub pre-training dataset.
  • B.2. Dataset cleaning: Dataset cleaning removes duplicate problems and submissions, normalizes C++ code, and executes Python and C++ solutions to filter nonfunctional or low-coverage data.

B.3. Data leakage and temporal split · C. Approach and Results

The section identifies training–evaluation leakage as a major concern in code-generation benchmarks and uses a strict temporal split to ensure training data reflects information available to competition participants. It also reports that ensemble quality varies: effective ensembles can outperform their components, whereas poor ensembles can underperform individual components.

  • B.3. Data leakage and temporal split: Internet-scale language models may copy text verbatim from their training data, creating a downstream evaluation concern.The passage notes that such copying can sometimes be beneficial.
  • B.3. Data leakage and temporal split: Code-generation benchmarks are especially vulnerable to leakage and duplication between training and evaluation sets.Many competition participants publish their solutions online after competitions.
  • B.3. Data leakage and temporal split: A strict temporal split prevents leakage by limiting training data to information available before a typical competition participant would compete.This safeguard is applied to the datasets used in the study.
  • B.3. Data leakage and temporal split: 4.1% solve rate was achieved by evaluating one solution from each training problem on validation problems with a random split, versus 0% with a temporal split.This baseline was used to verify the fine-tuning dataset’s temporal split.
  • B.3. Data leakage and temporal split: Ensembles can outperform all individual components when their components are combined effectively.The appendix figure presents this as one observed ensemble-performance pattern.
  • B.3. Data leakage and temporal split: Poorly constructed ensembles can perform worse than an individual component.The appendix figure contrasts this outcome with stronger ensemble combinations.

C.1. Ensembling · C.2. Metadata conditioning · C.3. GOLD

The paper improves program-space search through selective ensembling and sampled metadata conditioning, while GOLD shifts training toward finding at least one correct solution. Ensembling helps modestly on validation but does not improve over the 41B model on test, and combining GOLD with tempering requires an intermediate transition phase.

  • C.1. Ensembling: Ensembling pools samples from multiple models before filtering and clustering to increase sample diversity, but weaker models can waste the sample budget.Different model strengths can improve search coverage, while substantially worse components may hurt good models.
  • C.1. Ensembling: When individual-run performance differs greatly, ensembles are typically slightly worse than the better run; with smaller differences, they are more likely to improve search coverage.The ensemble tends to be dominated by the better run when performance gaps are large.
  • C.1. Ensembling: 32% solve rate was achieved by the 41B + 9B ensemble with 1 million samples per problem and 10 submissions, rising to 35.5% with clustering on validation.The ensemble used equal amounts of samples from each model and was selected for Codeforces evaluation.
  • C.1. Ensembling: On the test set, the 41B + 9B ensemble was slightly worse, or at least no better, than the 41B model alone.This regression was consistent with the ensemble’s small validation improvement.
  • C.2. Metadata conditioning: Solve rates improved when sampling ratings from 800 to 3500 in increments of 100, tag sets from the 50 most popular combinations, and language uniformly between C++ and Python.The actual metadata are unavailable during competitions, so the model conditions on sampled values to diversify outputs.
  • C.2. Metadata conditioning: The sampled metadata values are added as a prefix to the natural-language prompt during conditioning.This implementation is illustrated in Figures 5 and F.
  • C.3. GOLD: GOLD modifies maximum-likelihood training with an off-policy importance weight so the model emphasizes precision and increases its chance of producing at least one correct sample.The method is a variation of δ-reward GOLD, an offline reinforcement-learning algorithm.
  • C.3. GOLD: Combining GOLD with tempering requires an intermediate training phase that applies tempering without GOLD before fine-tuning.This phase transitions the pre-trained distribution to a smoother one, enabling the tempered distribution to be used for both the log-loss term and importance weight.

C.4. Additional results for filtering and clustering … C.8. Scaling with dataset size

The appendix shows that filtering difficulty varies substantially across problems, while sampling temperature, dataset composition, and model architecture materially affect performance. It also documents evaluation-specific data handling and fixed clustering settings used in the reported experiments.

  • C.4. Additional results for filtering and clustering: Just over 1/3 of validation problems have example-test pass probabilities significantly above zero, and these probabilities vary substantially across problems.The distribution is far from uniform and is sorted by the 41B model’s p_pass example test in Figure A3.
  • C.4. Additional results for filtering and clustering: 50 test inputs and 8192 model samples were used for clustering because increasing either hyperparameter no longer improved performance.The clustering test inputs may be invalid or insufficiently discriminative, producing ambiguous clusters containing correct and incorrect samples.
  • C.5. HumanEval comparison: Decoder-only baselines achieved HumanEval solve rates within about 1–3% of comparable Codex models for most settings, while encoder-decoder models performed significantly worse.The authors attribute this difference to encoder-decoders’ alignment with competition programming but not with HumanEval.
  • C.6. APPS dataset settings: CodeContests overlaps nontrivially with the APPS test set, so it cannot be used for training when evaluating on APPS.This overlap is an evaluation constraint for the APPS benchmark.
  • C.6. APPS dataset settings: Example tests were parsed for APPS because the dataset did not provide parsed tests, and the extraction failed on fewer than 2% of test problems.APPS problems may contain 0, 1, 2, or 3 example pairs, so the procedure parses fewer than three when necessary.
  • C.7. Best settings for sampling: T=0.25 works across a wide range of sample budgets, while top-k and nucleus sampling are no better than simple temperature sampling.Sampling temperature affects solve rate, which matters because AlphaCode generates at least 1M samples per problem.
  • C.8. Scaling with dataset size: Model performance scales with dataset size, and increasing the number of problems has a larger positive impact than increasing solutions per problem.This scaling complements previously reported scaling with model size, compute, and number of samples.

D. Codeforces contest evaluation … E.1. Model sample statistics

AlphaCode’s Codeforces evaluation simulated contest-time sampling, clustering, submission, and scoring while accounting for contest penalties, and repeated evaluations to assess variance. Additional analyses examined sampling strategies, dataset scaling, and sample syntactic correctness, while noting important simulation limitations.

  • E. Additional analysis of AlphaCode’s capabilities and limitations: Lower temperatures helped small sample budgets, higher temperatures helped large budgets, and top-k or nucleus sampling did not significantly outperform temperature sampling.The model tolerated a wide temperature range; nucleus-sampling performance increased with nucleus size.
  • E.1. Model sample statistics: Increasing the number of finetuning problems improved solve rate more than increasing the number of solutions, while sample statistics measured syntactic correctness for C++ and Python.Syntactic correctness meant compiling for C++ and avoiding SyntaxError for Python.
  • D.1. Simulation: The evaluation scored submissions using solved problems, solve timing, and incorrect-submission penalties.The procedure incorporated all three components of Codeforces contest scoring.
  • D.1. Simulation: 3,750 TPUv4 and 3,750 TPUv4i chips simulated live contests by continuously sampling, testing, clustering, and submitting up to 10 samples per problem at scheduled points.Submission points depended on contest time remaining or the relative number of samples passing example tests.
  • D.1. Simulation: The evaluation was conducted after contests ended, so it incompletely represented hacking and used consensus human outputs to filter multiple-output problems.The consensus-output change affected approximately five problems AlphaCode solved.
  • D.2. Multiple evaluations: Repeated evaluations varied sample ordering, clustering inputs, and cluster-selection seeds, but did not retrain or resample models because of compute limits.These choices targeted variance from sample ordering and clustering rather than from trained models or newly sampled sets.
  • D.3. Results: The researchers computed penalty-inclusive contest scores and scoreboard placements, finding that some problems were solved only with many samples.The second and third evaluations submitted more than 10 submissions per problem.
  • D.3. Results: The estimated Elo largely matched Codeforces Elo, differing by < 15 points, but remained an estimate because the system did not compete live.The estimate reproduced the Codeforces Elo method and was checked against other participants’ scores.

E.2. Solve rate for different problem difficulty ratings … E.3.3. Capturing variables and their relations

AlphaCode solves substantially more low-rated than high-rated problems, although high-difficulty solve rates are affected by small buckets and a 46% slow positive rate. Sensitivity experiments show that descriptions, simplification, rewording, and variable relationships materially influence performance, especially as model size increases.

  • E.2. Solve rate for different problem difficulty ratings: The difficulty-bucket evaluation reports 10@100k solve rates for 9B and 41B models across validation and test sets.The validation and test sets contain 117 and 165 problems, respectively, and bucket counts can be small, causing large variance.
  • E.2. Solve rate for different problem difficulty ratings: Solve rates are significantly higher for low-difficulty problems and quickly degrade as difficulty increases.High solve rates in difficult buckets are partly attributed to a 46% slow positive rate and small bucket sizes.
  • E.3. Sensitivity to the problem descriptions: AlphaCode strongly conditions on problem descriptions rather than simply brute-forcing possible solutions.Most analyses use the 10@1024 solve rate, defined as the solve rate from 10 submissions selected from 1024 samples.
  • E.3.1. Simplification of problem descriptions: Simplifying descriptions to make the required algorithm more explicit significantly improves performance.For the base 1B parameter model on one problem, solve rate increased from 12% to 55%.
  • E.3.2. Incorrect or irrelevant rewordings: Rewording results indicate that the model parses algorithm descriptions from symbols or natural language and can ignore irrelevant explanations.The model performs better with more language-heavy descriptions, possibly because the training distribution is verbose.
  • E.3.3. Capturing variables and their relations: Consistent variable renaming affects larger models less, whereas inconsistent renaming causes increasingly pronounced performance drops as model size grows.The results suggest that larger models increasingly capture relevant relationships between variables in problem formulations.

E.3.4. Sensitivity to word-level changes … Appendix Figure A10 | Solve rates under different word-level change regimes.

AlphaCode is relatively robust to type-word substitutions, synonym changes, and low levels of word deletion or swapping, but typos and stronger word-level noise reduce solve rates. Removing problem-description sections harms performance, while easier ratings generally help and solution-correctness conditioning improves performance.

  • E.3.4. Sensitivity to word-level changes: Replacing integer, array, and string with generic type terms produces no significant differences in solve rates.The substitutions were integer→number, array→sequence, and string→sequence of characters.
  • E.3.4. Sensitivity to word-level changes: Solve rate deteriorates roughly linearly with the number of introduced typos.Typos were created by swapping adjacent characters in randomly chosen English words.
  • E.3.4. Sensitivity to word-level changes: Synonym substitutions cause very little degradation in solve rate as their number increases.The substitutions used synonym pairs from Huang et al. (2019) relying on the PPDB database.
  • E.3.4. Sensitivity to word-level changes: Stronger word-level noise negatively impacts performance, but the model remains relatively robust to deletion probability p=0.05 and swapping distance N=2.Words were randomly permuted no more than N positions apart or deleted with probability p.
  • E.3.5. Description section ablations: Removing any task-description section impacts performance, with IO examples least harmful, description next, and specification most harmful.Different section orderings have only a small impact on solve rates, while specification removal is especially damaging because parsing the input becomes difficult.
  • E.4.1. Problem ratings: Specifying an easier problem rating is generally better than specifying a harder one, while harder ratings are relatively better for more difficult problems.For easier problems, conditioning on a harder rating has a larger negative impact.
  • E.4.2. Solution correctness: Value conditioning improves performance, and removing the CORRECT SOLUTION tag hurts both metrics, although not significantly.The comparison supplies the INCORRECT SOLUTION tag or no tag instead of CORRECT SOLUTION; the pass@k metric may increase solutions passing examples but not hidden tests.

F. Complete prompt and model examples

The appendix presents complete AlphaCode-generated C++ and Python solutions, then illustrates solution decompositions, long common subsequences with training data, and simplified rewordings of programming problems. The examples and human solutions are sourced from Codeforces.

  • F. Complete prompt and model examples: The displayed competitive-programming problems and human solutions are sourced from Codeforces.The examples include a circular-town singer problem paired with complete model code.
  • F. Complete prompt and model examples: Complete model examples include C++ and Python solutions, with problem tags, ratings, and languages sampled randomly at test time.The appendix directs readers to the AlphaCode website for more examples.
  • F.1.1. Solution decompositions: Example figures decompose human and model solutions to ‘Digits Sum’ and ‘Pizzaforces’ into substrings from the finetuning dataset.Colors identify substrings, but repeated colors and matching colors across solutions do not imply meaningful relationships.
  • F.1.2. Very long common subsequences between human solutions and finetuning data: Human validation solutions for ‘The Miracle and the Sleeper’ and ‘Integers Have Friends’ contain very long common subsequences with finetuning data.The reported LCS lengths are 914 and 666, respectively, while the remaining solution parts contain much smaller substrings.
  • F.2.1. Simplified rewordings: A simplified Nim statement explains heap reduction, optimal play, and outputting which player wins.It specifies n heaps with integer values a_1, ..., a_n and reducing some a_i to a value between zero and a_i - 1.
  • F.2.1. Simplified rewordings: Simplified rewordings restate binary-string counting and XOR-based winner problems with explicit input bounds and outputs.The binary-string task asks for strings without consecutive zeros, while the XOR task maps zero XOR to output 2 and nonzero XOR to output 1.
  • F.2.1. Simplified rewordings: The simplified ‘1554A Cherry’ formulation asks for the maximum product of adjacent values a_l and a_{l+1}.It applies for an integer l satisfying 1 <= l < n.
Loading 2203.07814v1…