AlgoBench：代码生成中算法适应的基准测试

HumanEval 和 LiveCodeBench 等既定编程基准的高通过率并不总是表明模型是否可以推理算法。许多固定基准最终通过发布的问题陈述、社论和生成的解决方案成为公共训练生态系统的一部分，从而允许后来的模型通过曝光而不是通过更强的算法能力来部分改进。我们引入了 ALGOBENCH，这是一个框架，可以通过结构化的约束转移转换，从已知的竞争性编程问题中自动构建新颖的算法问题。每个接受的 ALGOBENCH 变体都可以追溯到源问题，但必须使原始参考算法失败。除了 pass@$k$ 之外，我们还引入了复杂性感知指标——包括 OPTT、OPTS、TRAPRATE、GAPT 和 CONSENS——来测试解决方案是否不仅在功能上正确，而且渐近适合生成的问题。跨多个 LLM 和提示策略的实验表明，ALGOBENCH 变体的性能急剧下降，检索可以增加旧算法的重用，并且许多看起来正确的解决方案无法满足所需的复杂性。错误分析表明，失败主要是算法层面的，而不是实现层面的，这表明 ALGOBENCH 评估的适应性超出了功能正确性。