AlgoBench: Benchmarking Algorithmic Adaptation in Code Generation
For researchers evaluating code generation models, AlgoBench provides a more rigorous test of algorithmic adaptation, revealing that high pass rates on existing benchmarks may reflect memorization rather than true reasoning.
AlgoBench introduces a framework that transforms known competitive programming problems into novel variants to test whether LLMs can adapt algorithms rather than memorize solutions. Experiments show that model performance drops sharply on these variants, and many correct-looking solutions fail to meet required complexity, indicating that current benchmarks overestimate algorithmic reasoning.
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.