New Benchmark Tests Whether AI Models Can Write Code Meeting Specific Performance Requirements

A new benchmark called BigO(Bench) examines a critical gap in how we evaluate code-generating AI systems: whether they understand and can produce code that meets specific time and space complexity requirements. The research, submitted to arXiv's computer science track, addresses an overlooked dimension of code quality that matters greatly in real-world applications.

What the Benchmark Measures#

The benchmark targets a fundamental skill in computer science—the ability to write algorithms that operate efficiently under constraints. Rather than simply checking whether generated code works, BigO(Bench) evaluates whether an LLM can craft solutions that satisfy explicit complexity demands, such as solving a problem in linear rather than quadratic time.

The benchmark includes:

• 3,105 coding problems sourced from competitive programming contests
• 1,190,250 solutions from human and AI sources
• Automated complexity inference tools that measure time and space complexity from profiling data
• Annotated complexity labels assigned to each solution through empirical measurement

How It Works#

The researchers built automated tooling to infer algorithmic complexity directly from runtime behavior on test inputs. This approach captures real-world performance metrics—execution time and memory usage—across varying problem sizes. Solutions are tagged with their inferred complexity characteristics, creating a training and evaluation resource.

Key Findings#

Testing multiple state-of-the-art language models revealed a striking pattern: while advanced reasoning-based models excel at code generation itself, they show weaker understanding of complexity constraints. According to the paper, token-space reasoning models "may not generalize well to tasks for which no reward was given at training time," suggesting these capabilities require explicit optimization during model training.

This hints that improving AI performance on complexity-aware code generation will likely demand targeted training objectives, not simply larger models or more data.