Shiki

论文标题：Evaluating and Improving LLM-based Competitive Program Generation
期刊/会议：Information and Software Technology

研究背景与动机

该论文主要解决大语言模型在竞争性编程生成任务中的性能评估与提升问题。竞争性编程要求模型具备强大的算法推理能力、复杂逻辑实现能力，并严格遵守输入/输出格式与资源限制，被认为是当前LLM代码生成中最具挑战性的任务。然而，现有研究存在三个关键局限性：

1. 缺乏任务特定的提示设计：现有方法通常使用简单提示，导致生成的解决方案在正确性、效率或问题约束遵循方面存在不足
2. 数据泄露问题严重：主流基准测试(如HumanEval、MBPP)中的问题可能在LLM预训练阶段已被见过，难以区分模型是真正解决问题还是回忆记忆数据
3. 问题类型和难度多样性不足：现有数据集很少包含真实竞赛问题，导致评估无法全面反映LLM在不同难度级别和问题类型上的表现

基于这些局限性，研究旨在通过构建高质量基准、系统评估LLM表现、构建错误分类法并提出针对性改进框架，来提升LLM在竞争性编程任务中的表现。

论文核心方法和步骤

![[Pasted image 20250928163621.png]]

基准构建

从2024年举办的5个ICPC亚洲区域赛和4个CCPC区域赛中收集117个问题，通过4个过滤标准构建包含80个问题的基准：

• 过滤1：排除”金牌级”高难度问题
• 过滤2：排除包含视觉图像的几何问题
• 过滤3：排除包含难以处理内容(如过多表格、过长背景故事)的问题
• 过滤4：排除因平台限制无法提交的问题

最终基准包含13个热身问题、36个铜牌级问题和31个银牌级问题，覆盖9种算法类型。

评估方法

使用DeepSeek-R1作为代表模型，设计包含三个组件的基础提示：

1. 自然语言部分：角色扮演指令和任务指令
2. 问题主干部分：问题背景、输入输出规范
3. 测试用例部分：示例输入输出对

通过在线评测平台(VJudge、Codeforces)评估生成程序，状态包括：AC(接受)、WA(错误答案)、RE(运行时错误)、TLE(超时)、CE(编译错误)。

错误分类法构建

采用开放编码程序，由两名算法竞赛团队成员手动分析60个错误程序(开发集)，构建包含两大类的层次化错误分类法：

通用错误(63.3%)：

• 设计相关错误(28.6%)：错误算法选择(12.4%)、误解问题需求(10.6%)等
• 边界相关错误(15.5%)：边缘情况处理不当、差一错误等
• 条件相关错误(8.7%)：布尔表达式错误、逻辑运算符误用等
• 数据类型错误：溢出、精度损失、隐式类型转换等
• 语法错误：编译错误、语言特定语法误用
• 输入输出错误：格式处理不当

算法特定错误(36.7%)：

• 数学问题相关错误(8.1%)
• 贪心算法错误(5.0%)
• 图论错误(4.3%)
• 递归与分治错误(4.3%)
• 动态规划错误(4.3%)
• 搜索算法错误(3.7%)

使用Cohen’s Kappa评估标注者间一致性，得分0.86，表明优秀的可靠性。

改进框架

提出三阶段改进框架：
![[Pasted image 20250928164352.png]]
阶段1：错误诊断
通过结构化工作流程识别错误根本原因，包括：

• 检查基本功能性和极端值处理
• 验证核心算法和时间/空间复杂度
• 将错误映射到分类法中

阶段2：基于多轮对话的修复
根据错误类型动态选择7种修复策略：

• 完整算法重构
• 逻辑补全
• 提示级澄清
• I/O格式修复
• 语法级修复
• 计算精度/内存安全增强
• 终止保证

阶段3：信息增强的重新生成
对于阶段2无法修复的程序，使用结构化提示模板重新生成，包含：

• 问题建模
• 算法目标
• 算法思想
• 实现细节
• 约束条件

该框架模拟参赛者的推理过程，系统化地提升LLM生成的竞争性程序的质量。

实验结果与结论

基础提示评估结果

使用基础提示时，DeepSeek-R1在80个问题中仅解决5个(6.25%)：

• 63个WA(错误答案)
• 5个TLE(超时)
• 7个CE(编译错误)

按难度级别分析：

• 热身问题：4/13 AC(30.8%)
• 铜牌级问题：0/36 AC(0%)
• 银牌级问题：1/31 AC(3.2%)

按问题类型分析：

• 单算法问题：4/49 AC(8.2%)
• 多算法问题：1/31 AC(3.2%)

结果表明LLM在低难度和单算法问题上表现较好，但在高难度和需要多算法集成的问题上表现显著下降。

改进框架效果

应用改进框架后，AC解决方案从5个大幅增加到46个(57.5%)：

• WA从63个减少到30个
• TLE从5个减少到3个
• CE从7个减少到1个

按难度级别的改进：

• 热身问题：从4AC增加到11AC(84.6%)
• 铜牌级问题：从0AC增加到27AC(75%)
• 银牌级问题：从1AC增加到8AC(25.8%)

按问题类型的改进：

• 单算法问题：从4AC增加到33AC(67.3%)
• 多算法问题：从1AC增加到13AC(41.9%)

研究意义与结论

该研究的主要贡献和意义包括：

1. 构建了高质量的竞争性编程基准，有效缓解数据泄露问题，提供更可靠的评估环境
2. 系统揭示了LLM在竞争性编程中的局限性，特别是在高难度和多算法问题上的表现瓶颈
3. 建立了全面的错误分类法，为理解LLM失败模式提供了结构化框架
4. 提出了有效的改进框架，证明通过系统化错误诊断和针对性修复可以显著提升LLM表现

研究结果表明，当前LLM在竞争性编程任务中仍有很大提升空间，而基于错误分类法的系统化改进策略是有效的提升途径。这为未来LLM在复杂代码生成任务中的研究提供了重要参考，特别是在算法推理和错误修复方向。