Beyond Correctness: Benchmarking LLMs for Algorithmic Program Optimization
Abstract
AbstractLarge language models (LLMs) can generate functionally correct code, but their ability to optimize programs is underexplored. We introduce OEISPerf, a code-to-code benchmark for algorithmic program optimization built from alternative implementations of integer sequences in the On-Line Encyclopedia of Integer Sequences. For each sequence we mine multiple mathematical formulations, synthesize and validate Python implementations, and pair a substantially slower program with the fastest validated reference found by our construction pipeline, producing instances that often require substantial structural transformations and can yield substantial speedups. Evaluating 15 open-source and closed-source LLMs shows that even the strongest evaluated setting, Gemini-3-Flash with its thinking mode enabled, matches the reference efficiency on only 67.9% of test instances. Across LLMs, we observe both incorrect “optimizations” that break correctness and superficial refactorings that preserve suboptimal complexity. Finally, we fine-tune Qwen2.5-Coder-3B-Instruct via reinforcement learning, markedly improving reference attainment on OEISPerf while slightly improving performance on standard code-generation benchmarks.