技术摘要：ALGOBENCH

问题陈述

当前用于代码生成的语言大模型（LLM）基准测试（如 HumanEval 和 LiveCodeBench）往往呈现出较高的通过率，但这并不一定反映真实的算法推理能力。一个主要的局限性是数据污染：既定的问题陈述、题解和参考解答已广泛存在于公开的训练语料库中。因此，模型可能通过回忆记忆中的解题模式而非根据约束条件推导算法来获得高分。虽然近期的基准测试试图通过使用更新或更难的问题（例如 LiveCodeBench、ProBench、HLCE）来缓解这一问题，但这些基准仍然是静态的。一旦发布，其问题陈述和模型生成的解决方案不可避免地会进入训练数据，使得未来的模型可以通过暴露在这些数据中而非通过增强推理能力来获得提升。因此，需要一种能够动态生成问题的基准测试，使记忆源解法变得不再奏效，从而迫使模型调整其算法策略。

方法论

核心框架：ALGOBENCH

作者提出了 ALGOBENCH，这是一个从已知的竞赛编程来源自动构建新颖算法问题的框架。其核心理念是约束偏移变换（constraint-shifting transformation）：修改源问题，使得原始的参考算法失效，从而需要一种新的算法方法或不同的渐近复杂度。

1. 变换算子
该框架采用十种基于规则的变换算子，从源问题 ($q$) 生成变体 ($q'$)。这些算子包括：

• 约束缩放 (CS)： 增加输入规模（例如，$N \le 2000 \to N \le 2 \times 10^5$）。
• 静态转动态 (SD)： 将静态问题转换为动态问题（例如，添加更新操作）。
• 目标扰动 (OP)： 改变优化目标。
• 贪心陷阱注入 (GT)： 引入使贪心启发式算法失效的约束，从而需要动态规划。
• 其他算子包括约束耦合、边界情况扩展、输出要求变更，以及更广泛的变换如现实世界包装（Real-World Wrapping）和图结构变化。

2. 质量门控
为确保有效性并防止问题过于简单，生成的题目必须通过四个自动化门控：

• 门控 1（旧解拒绝）： 原始参考解 ($a^*$) 必须在处理新问题时失败（产生 WA、TLE 或 MLE）。
• 门控 2（新解验证）： 必须通过在小规模输入上的暴力破解（brute-force）正交程序来验证新的参考解 ($\hat{a}^*$)。
• 门控 3（非改写）： 生成的陈述必须与源问题有显著区别（TextSim $< \tau_{text}$）。
• 门控 4（复杂度认证）： 新解必须满足目标时间和空间复杂度。

3. 确定性复杂度验证器
一个三层验证器用于评估提交的解法，以区分功能正确性和算法最优性：

• 第一层（静态 AST 分析）： 解析代码，根据循环嵌套、递归和数据结构来估算时间/空间复杂度。
• 第二层（算法标签验证）： 检查是否存在预期算法的结构性证据（例如，线段树的懒惰传播），并检查是否存在禁止使用的算法。
• 第三层（校准运行时缩放）： 在不断增加的输入规模上运行解法，以拟合运行时模型 $T(n) = cn^\alpha (\log n)^\gamma$。如果拟合出的指数超过目标值 0.15 以上，则会对解法进行惩罚。

评估指标

除了标准的 pass@k，ALGOBENCH 还引入了感知复杂度的指标：

• OPTT/OPTS： 正确且满足目标时间/空间复杂度的提交率。
• TRAPRATE（陷阱率）： 结构化地复用了源算法的错误提交所占的比例（表明存在“旧解陷阱”）。
• GAPT（效率差距）： 衡量拟合的运行时指数与目标指数之间的差距。
• CONSENS（一致性）： 衡量性能随约束强度增加而下降的情况。
• $\Delta_{gen}$： 从源问题到生成变体的性能下降值。

核心贡献

1. 框架： 引入了 ALGOBENCH，一个用于生成具有可追溯性但算法逻辑截然不同的问题的自动化流水线。
2. 变换与验证： 设计了十种变换算子和一个四门控质量控制系统，确保生成的题目能拒绝旧解并要求新的复杂度。
3. 基准数据集： 构建了一个包含 598 个被接受的变体（其中 420 个用于主要实验）的基准测试集，这些变体衍生自 300 个源问题（来自 Codeforces、AtCoder、Kattis、LeetCode Hard），并配有元数据、参考解和暴力破解正交程序。
4. 指标： 提出了评估渐近适用性而非仅仅是功能正确性的指标（OPTT、OPTS、TRAPRATE、GAPT、CONSENS）。
5. 实证发现： 对七种 LLM 在六种提示策略下的表现进行了评估，结果表明，在面对生成的变体时，性能显著下降，并且许多“正确”的解法未能满足复杂度要求。

实验结果

性能下降与适应性

• 泛化差距： 模型在从源问题转向 ALGOBENCH 变体时表现出剧烈的性能下滑。旧模型从源问题的平均 85.1% pass@1 下降到了变体的 53.6%。即使是最新的前沿模型（GPT-5.4, Claude Opus 4.5）也下降了 33.3%。
• 复杂度错位： pass@k 与 OPTT 之间存在显著差距。例如，GPT-4o 的 pass@5 为 72.7%，但 OPTT 仅为 63.6%，这表明许多通过测试的解法使用了次优算法。
• 检索风险： 使用源问题作为上下文的检索增强生成（RAG）往往会增加 TRAPRATE。对于 Gemini 2.5 Flash，RAG 使陷阱率从 3.6% 上升到了 30.0%，这表明检索会将模型锚定在原始的（现已失效的）解法上。

错误分析

对 400 个失败提交的分析显示，失败主要是算法层面而非实现层面的：

• 旧解陷阱 (42.3%)： 模型实现了源算法，通过了公开示例，但在隐藏的陷阱测试中失败。
• 速度过慢 (21.8%)： 模型识别出了正确的路径，但未能进行必要的优化（例如，未能从 $O(N^2)$ 切换到 $O(N \log N)$）。
• 实现错误 (Implementation Bugs)： 仅占失败原因的 9.0%。

敏感性与污染

• 约束敏感性： 随着输入规模的增加（例如，$N=10K \to 50K$），性能急剧下降，这正是二次方复杂度解法超时的地方。
• 污染效应： 模型在处理较旧的源问题（2020年）时表现明显优于处理较新的问题（2024年），这表明存在记忆现象。然而，这种差距在 ALGOBENCH 变体中缩小了，变体无论源问题的发布年份如何，都保持了持续的难度。

意义与主张

本文声称 ALGOBENCH 评估了一种不同于标准代码基准测试的能力：即将算法推理适应于新颖约束的能力，而非依赖记忆模板。

• 超越功能正确性： 该基准测试证明，静态数据集上的高通过率并不保证渐近适用性。许多模型生成的解法在功能上是正确的，但在算法上是低效的。
• 对记忆的鲁棒性： 通过自动生成使源解法失效的问题，ALGOBENCH 减轻了训练数据污染的风险，提供了衡量真实算法推理能力的更可靠度量。
• 诊断价值： 该框架识别了特定的失败模式（例如，无法从贪心转向动态规划，或无法处理动态更新），这些模式在传统基准测试中会被掩盖。

作者总结道，当前的 LLM 在熟悉的模板不再适用时会表现挣扎，未来的算法推理进展需要那些要求真正适应能力而非模式匹配的基准测试。