AlgoBench exposes LLM coding flaws with novel algorithmic tests

A new paper from researchers Song, Cai, and Zhao introduces AlgoBench, a benchmark framework designed to measure how well AI code generation models can adapt algorithms to novel variations. The authors argue that high pass rates on established benchmarks like HumanEval and LiveCodeBench don't truly indicate algorithmic reasoning, because these fixed problems often leak into training data through public solutions and editorials. AlgoBench solves this by automatically generating new problem variants from known competitive-programming problems using structured constraint-shifting transformations. Each variant is traceable to a source but requires a different algorithm to solve—making the original reference algorithm fail.

The benchmark goes beyond traditional pass@k metrics by introducing complexity-aware evaluation metrics including OPTT, OPTS, TRAPRATE, GAPT, and CONSENS. These test not just functional correctness but asymptotic suitability for the generated problem. Experiments across multiple LLMs and prompting strategies show performance drops sharply on AlgoBench variants. Retrieval-augmented generation actually increases reuse of the old, incorrect algorithm. Error analysis confirms that most failures are algorithmic rather than implementation-level, suggesting AlgoBench effectively measures adaptation beyond functional correctness. The paper is currently under review and available on arXiv.