Search papers, labs, and topics across Lattice.
This paper introduces ALGOBENCH, a novel benchmarking framework designed to evaluate the algorithmic reasoning capabilities of code generation models by generating new algorithmic problems through structured transformations of existing competitive programming challenges. The framework not only tracks the source of each problem but also incorporates complexity-aware metrics to assess the suitability of solutions beyond mere functional correctness. Experiments reveal that while many models perform well on traditional benchmarks, they struggle significantly on ALGOBENCH variants, highlighting a critical gap in their algorithmic adaptation abilities.
Code generation models may excel at passing traditional benchmarks but falter dramatically when faced with novel algorithmic challenges, revealing a hidden weakness in their reasoning capabilities.
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.
