arXiv:2607.00062cs.SEcs.AI2026-07

新基准测试揭露代码模型真算法能力,避免因记忆旧题而虚高得分。

AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation

论文配图:AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation
图 1 · 摘自论文原文
  • 通过结构化变换生成新算法题,让旧解法失效。
  • 多模型在新题上表现骤降,复杂度达标率不足半数。
  • 适合评估模型真实算法适配能力,非仅功能正确性。

现有编程评测如HumanEval和LiveCodeBench的高通过率未必反映模型真正的算法推理能力。由于题库内容被广泛传播,后续模型可能通过记忆而非真正理解提升表现。我们提出ALGOBENCH框架,通过结构化约束转换,从已知竞赛题自动生成新颖算法题,每个新题均源自原始问题但需使原参考算法失效。除传统pass@$k$外,引入复杂度感知指标:OPTT、OPTS、TRAPRATE、GAPT和CONSENS,以检验解法是否在时间/空间复杂度上满足要求。多轮实验表明,主流LLM在新题上性能显著下降,检索机制导致旧算法复用,许多看似正确的解法实际不满足渐进复杂度要求。错误分析显示失败主要源于算法设计缺陷,而非实现错误,证明ALGOBENCH能有效评估模型超越功能正确的算法适应能力。

原文摘要 · Abstract (English)

High pass rates on established programming benchmarks such as HumanEval and LiveCodeBench do not always show whether a model can reason about algorithms. Many fixed benchmarks eventually become part of the public training ecosystem through released problem statements, editorials, and generated solutions, allowing later models to improve partly by exposure rather than by stronger algorithmic ability. We introduce ALGOBENCH, a framework that automatically builds novel algorithmic problems from known competitive-programming problems through structured constraint-shifting transformations. Each accepted ALGOBENCH variant is traceable to a source problem, but must make the original reference algorithm fail. Beyond pass@$k$, we introduce complexity-aware metrics -- including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS -- to test whether a solution is not only functionally correct but also asymptotically suitable for the generated problem. Experiments across multiple LLMs and prompting strategies show that performance drops sharply on ALGOBENCH variants, retrieval can increase reuse of the old algorithm, and many correct-looking solutions fail to meet the required complexity. Error analysis shows that failures are mainly algorithmic rather than implementation-level, suggesting that ALGOBENCH evaluates adaptation beyond functional correctness.

代码生成算法评估基准测试

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。