AlphaCode: 竞赛级别的代码生成.

• Competition-Level Code Generation with AlphaCode paper web

目前开发的代码生成系统通常受限于特定的编程语言和较短的代码片段，比如Codex可以实现python中的简单编程问题。而使用通用的编程语言从冗长的自然语言描述中生成完整的程序仍然具有挑战性。生成短代码片段类似于机器翻译问题，即将任务需求直接转换为代码；而生成复杂程序需要充分理解任务，并依赖更深入的算法推理。

国际知名的编程竞赛包括国际大学生程序设计竞赛ICPC和国际信息奥林匹克竞赛IOI等。这些竞赛需要理解复杂的自然语言描述，并通过算法和数据结构实现准确的解决方案，并在一些隐藏的测试用例上评估方法的准确率和运行速度。

本文介绍了AlphaCode，一个可以解决编程竞赛问题的代码生成系统。该系统由三个重要组件构成：（1）一个用于训练和评估的编程竞赛数据集；（2）一个基于transformer的大型高效结构；（3）大规模的模型采样和搜索空间。具体地，使用大型transformer语言模型来生成代码，在选定的GitHub代码上进行预训练，并在一个新的编程竞赛数据集上进行微调。对于每个问题，生成大量的程序样本，根据问题描述中的示例测试结果对它们进行过滤和聚类，以获得用于评估的一小组候选样本。在Codeforces平台上最近$10$场$5000$人以上的比赛中，AlphaCode平均排名在前$54.3\%$。

1. 问题建模

在一个编程竞赛中，参赛者需要在有限的时间内正确解决尽可能多的问题。针对每一个问题给出的程序提交会被发送到服务器上，服务器根据一组隐藏的测试用例评估程序。根据每个问题的错误提交次数和解决问题所花费的时间，会有相应的惩罚。提交程序可以用任何编程语言编写，其中c++和Python是目前最流行的。题目通常会根据难度进行评分，难度越大得分越高。

解决一个编程问题通常需要三个步骤。

1. 参赛者必须阅读并理解包含以下段落的自然语言描述：与问题无关的叙述性背景、理想解决方案的描述\输入和输出格式的规范、一个或多个输入/输出对测试样例。
2. 参赛者需要创建一个有效的算法来解决这个问题，该算法还必须足够高效，能够满足问题指定的输入大小和时间限制。
3. 参赛者需要实现该算法，需要考虑执行时间的限制和复杂的边界情况，并给出精确的代码。参赛者可以通过一些简单的测试用例调试代码，最后进行正式提交。

下图给出了一个编程问题的例子，该编程问题是指给出两个字符串，把一个字符串中的若干字符替换成回退符，能否与第二个字符串等价。

下图给出了AlphaCode生成的一种正确解决方案，其思路是将两个字符串从后往前进行比较。

在评估模型性能时采用解决率指标$n@k$，即对每个问题采样$k$个样本，将其排序后选择前$n$个进行提交，其中有一个程序能够通过测试则表明该问题已解决。

2. 数据集

（1）预训练数据集

预训练数据集能够帮助模型学习良好的代码表示并流利地生成代码。本文使用的预训练数据是从2021年7月14日的GitHub仓库中构造的，选择了几种流行语言的所有代码文件:c++、c#、Go、Java、JavaScript、Lua、PHP、Python、Ruby、Rust、Scala和TypeScript。过滤掉所有大于1MB或长于1000个字符的文件，删除了相同文件的副本。最终的预训练数据集总共包含715.1 GB的代码。

（2）微调数据集

微调数据集能够帮助模型适应编程竞赛的目标领域。作者收集了一个新的编程问题数据集CodeContests，包括Codeforces、Description2Code、CodeNet等平台的编程问题。该数据集的基本统计信息如下，包括数据集的划分、每个问题提供的平均测试样例、每个问题对应的不同编程语言的人工提交和平均正确率。

编程问题中大量的人工提交结果是假阳性的，即使它们能够通过测试用例，但也可能没有充分考虑所有情况，或不满足时间与内存限制。下表展示了不同数据集中存在的假阳性比例，通过人工生成额外的测试用例，CodeContests数据集减少了假阳性的比例，但仍然有很多测试正确但运行时间长的解决方案。

3. AlphaCode模型

AlphaCode模型的整体结构如图所示，包含以下过程：

1. 使用transformer语言模型在预训练数据集上训练，学习人类编程的表示空间；
2. 在CodeContests数据集上微调，使模型适应编程问题数据；
3. 为每个问题生成大量的程序样本；
4. 通过测试实例和聚类挑选样本，构造一小组候选提交，并进行评估。

（1）模型结构

AlphaCode模型的基本结构使用标准的transformer编码器-解码器结构。与只使用解码器结构的Codex相比，编码器可以双向提取复杂自然语言文本的表示。由于问题描述通常为解决程序的两倍，所以编码器的输入token长度也设置为解码器的两倍。解码器的层数设置为编码器的$6$-$7$倍。

为了降低模型的计算成本，采用了multi-query机制，即所有注意力头共享键和值向量。token采用SentencePiece，约有$8000$个词汇。

（2）预训练

编码器使用掩码语言建模，解码器对token预测使用交叉熵损失。对于最大的41B模型，受限于训练资源，采用了提前停止训练方法。优化器使用AdamW。

（3）微调

微调过程额外使用了三种改进方法：

⚪ Tempering

Tempering是一种正则化技术，通过将模型的输出除以一个标量温度，使得token预测的概率分布更加平滑或集中。本文使用较小的温度$T=0.2$，使得预测概率分布更平滑，有助于避免对微调数据集的过拟合。

⚪ Value conditioning & prediction

由于微调数据集中同时包含正确和错误的程序提交，作者使用conditioning和prediction区分这两种提交。

conditioning是指在问题描述时提供程序正确或错误的标注；prediction是指额外引入一个辅助分类器，用于区分该提交结果是否正确。

⚪ GOLD

同一个问题通常有许多种不同的解决方案，而模型只需要寻找到一个正确的解决方案即可。作者采用了一种离线的强化学习方法GOLD，当模型给出一个高置信度的正确程序时，会降低其他预测结果的权重，使模型专注于提高该程序的预测精度。

（4）采样

为了生成具有足够丰富程度的样本，作者采用了一些采样方法：（1）用Python和C++各随机生成一半的样本；（2）随机赋予问题相关标签和难度评级；（3）使用较高的采样温度。之后使用过滤和聚类方法从其中选择一个少量的候选提交结果。

过滤是指使用问题陈述中提供的测试用例检测程序，该过程会删除约$99\%$的程序样本，但仍然会剩下上万个候选样本。在$10\%$的问题上，过滤后无法找到任何一个满足的程序样本。

聚类是指额外训练一个与主要模型相同的结构，经过相同预训练后在所有测试用例上进行微调，用于创建新的测试输入。将这些额外的测试输入到过滤后的所有程序中，并将产生相同输出的程序分类到同一组中。在采样时每个组选择一个效果最好的程序。

4. 实验分析

（1）Codeforces平台上的评估

作者在Codeforces平台上2021年12月1日至28日的$10$场比赛中评估方法的实际性能。当每个问题限制提交$10$次时，模型平均评级$54.3\%$，实际每个问题平均提交$2.4$次。当不限制提交次数时，模型平均评级$48.8\%$，实际每个问题平均提交$28.8$次。

（2）CodeContests数据集上的评估

作者在CodeContests的验证集和测试集上评估模型。评估指标采用$n@k$指标，若每个问题生成一百万个样本，可以解决验证集中$34.2\%$的问题；若每个问题生成10万个样本，可以解决验证集中$31.8\%$及测试集中$29.6\%$的问题。

（3）CodeContests数据集上的消融

无论是否限制提交样本的次数，增加模型参数的数量或采样数量可以极大地提高模型性能：

下图给出了模型性能随训练时间和采样时间的变化：

上述结果表明：

• 采样数量与解决率呈对数线性关系：充分探索采样空间非常重要，然而增加采样样本量会成倍增加成本。
• 更好的模型在解决率曲线中具有更大的斜率：更大的模型往往具有更高的模型质量，能够有效地减少所需样本数量。
• 解决率与计算量呈对数线性关系：需要平衡模型大小与计算量。

下表给出了不同模型结构对应的解决率和采样速度。若只使用解码器结构或标准的多头自注意力，其解决率甚至会提高，但采样速度会大幅度下降，从而导致更高的时间成本。

下表对比在不同的预训练数据集上的训练表现，结果表明在使用所有语言的完整GitHub数据集上预训练能够获得最好的表现。

作者对方法的其他细节分别进行了消融实验：

下表展示了至少一个程序样本通过测试用例的问题占比以及通过测试用例的程序样本占比，结果显示生成结果中只有不到$1\%$的样本通过了测试用例，即使用测试用例会过滤掉$99\%$的样本。更大的模型生成的样本更有可能通过测试用例。

下图展示了进一步使用聚类的效果。通过过滤+聚类能够从数百万生成样本中筛选少量的高质量样本，从而获得更高的问题解决率。

（4）APPS数据集上的评估

作者进一步在APPS数据集上对比不同方法的表现，当增加采样数量时，AlphaCode模型的表现不断改进，这表明大规模采样的重要性：

5. 局限性讨论

为了判断模型是否简单地从训练集中记忆并复制代码，作者比较了模型生成的正确程序与整个训练集中的最长公共子串，并给出了这些匹配长度的分布情况。结果没有发现证据表明模型复制了训练数据中的核心逻辑，其公共子串大多包含用于读取和解析输入数据格式的样板代码。

在生成代码中存在一些死代码（即对程序功能没有影响的代码行），死代码的占比越高表明模型对生成内容的理解能力越差。下图对比了模型生成以及人工编程中去除死代码后的程序长度变化，结果表明模型的表现与人类大致相同。

下表给出了模型在不同类型问题中的解决率。结果表明模型在处理位掩码、排序、数学和贪婪算法的问题上相对较好，但在动态规划和构造性算法方面较差。

作者分析了模型对问题描述的敏感性，发现AlphaCode会对问题描述中的重要更改做出适当的响应，并利用其中的额外信息。当给出问题的简化描述时，模型的处理速度更快；当给定相关但不同的问题时，解决率会显著下降。模型几乎不受不重要信息(如同义词)的影响，但对输入规范的依赖性较大。

在采样时为了增加多样性，向模型随机提供了一些元数据，比如问题的标签类型、难度评分以及编程语言的指定。结果表明模型会受到这些元数据的影响，随机抽取标签和评分、提供采样正确的标记都能够提高模型的解决率。

作者进一步发现验证损失与模型的解决率是不匹配的，尽管验证损失在减少后会逐渐增加，但解决率一直在提高。这可能是因为随着训练次数增加，模型会产生更典型的解，尽管这使得验证损失变大，却有利于模型解决问题。