BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?
Pierre Chambon, Baptiste Roziere, Benoit Sagot, Gabriel Synnaeve
cs.CL, cs.AI, cs.CC
2025-03-19
BigO(Bench) tags 3,105 problems and 1.19M solutions with profiled Big-O. Qwen3 scores 6.5% All@1 generating to a target time class; R1 Llama 70B gets 41.4% All@1 on prediction.
HumanEval and MBPP already sit at 90% to 95% pass@1 on short functions. SWE-Bench moved the target to repo-level patches. Interviews and production failures still hinge on a skill those boards barely measure: name the time and extra-space class of a snippet, then emit another passing solution that actually hits a stated, feasible Big-O.
Older sets mostly classify into five time classes (CoRCoD, TASTY, CodeComplex). RACE uses about 100 tests and scores how close wall-clock time is to a human reference. Absolute runtime is glued to hardware and to the tests you happen to run. BigO(Bench), from FAIR at Meta and Inria, turns the question into three executable tasks: predict the complexity of a given solution, generate a solution that passes public, private, and generated tests under a feasible constraint, and, inside the same class, beat human submissions on the fitted curve coefficient.
DeepSeek-R1 clears 70% pass@1 on CodeForces and drops to 4.8% when the prompt also names a complexity. On prediction it is only 6.8 points above Llama 4 Maverick. Passing tests and controlling complexity are different skills.
Labels are not textbook proofs. They are worst-case growth on CPython. The framework takes a Python snippet and one example input, grows each argument alone or together with random, copy, and identity strategies, and runs the jobs in Bubblewrap sandboxes. Cprofiler records time, tracemalloc records memory, and non-negative least squares fits O(1), O(n), O(n log n), O(n²), and multi-argument classes. The class with the lowest residual, plus a simplicity bias, becomes the label. The same fit keeps a leading coefficient, so two O(n) solutions can still be ranked.
Against human theoretical labels the match is 84% for time and 82% for space (125 items each). Twenty reruns agree 91.9% / 89.1% of the time. About 84% of problems fail on under 30% of solutions; 4.5% fail on more than 90%, usually from a bad input parser or an uncovered edge. One measurement replica over the full input range costs a tenth of the compute and still reproduces 96.6% of the released time labels.
The data starts from correct Python submissions in Code Contests: 8,139 problems and 1,485,888 solutions, filtered to 3,105 problems and 1,190,250 solutions. The time test set has 311 problems, 640 solutions, 11 classes; the space set has 308 problems, 636 solutions, 5 classes; 63 problems overlap. Linear time is 38% of all solutions, constant time 20%. Space is more skewed: O(n) 47%, O(1) 25%. Parsing raw stdin into scalable fields needs a dataclass; Llama 3.1 405B reaches 58.1% BckTr@10 (parse then print must round-trip), and multiple solutions per problem raise coverage to 82%.
Metrics are macro-averaged first by class, then by problem. Pass@k scores each class on its own. Best@k keeps only the most optimized class. All@k requires every class of a problem at once. All@1 exists to stop models from skating by on memorized optimal templates. Humans find suboptimal solutions easier. Models cling to the optimal class and rarely insert a dummy sort to turn O(n) into O(n log n).
Fourteen instruct models, zero-shot. Empty o1-mini replies were dropped, so that row is an optimistic bound. Distilled R1 used about 2× nodes, 5× wall time, and 16× generated tokens.
| Model | Task | Metric | Score |
| Qwen3 32B | time-complexity generation | All@1 | 6.5% |
| DeepSeek-R1 Llama 70B | time-complexity prediction | All@1 | 41.4% |
| DeepSeek-R1 Llama 70B | time-complexity generation | All@1 | 4.8% |
| Llama 3.1 Nemotron-Ultra | space-complexity generation | All@1 | 5.6% |
| Top models | time pred / time gen | pass@1 | 64.2% / 33.5% |
| Qwen2.5-Coder 32B | space-complexity prediction | All@1 | 12.6% |
| o1-mini / R1 Llama / Nemotron | space-complexity prediction | All@1 | 8.1% / 10.4% / 10.3% |
Prediction beats a dummy that always answers O(n). Generation is compared with Llama 3.1 70B on the same problems with the complexity clause stripped. Adding a request to optimize while still meeting the constraint cuts time-generation All@1 by 12% on average, and by about 30% for GPT-4o and o1-mini. Ranked by curve coefficient against humans in the same class, Qwen3 sits at the 44.0th percentile on the full time set, and 79.6 on the intersection where every starred model produced at least one passing solution.
On space prediction, Qwen2.5-Coder beats several reasoning models. Those models misread extra space even when the prompt defines it. They can list every class of a problem, then refuse to emit the slower ones.
Fine-tuning Llama 3.1 70B for 10 epochs on 2,000 problems and 20k solutions (about 22M tokens for generation, 18-19M for prediction) barely moves prediction and slightly hurts unconstrained synthesis. Ordinary SFT does not buy this skill. Reasoning models open a gap on plain coding; on complexity they bunch up.
The board is harder than pass@1 and cheap enough to run in sandboxes, unlike repo-level agent evals. Code, data, and a leaderboard are public.
For assistants that must bound latency or memory, the finding is narrow: models that write their reasoning into tokens can dominate contest correctness, and still miss a target Big-O if that constraint was never a training reward.
This is a benchmark, not a new optimizer. Related work already uses it as an eval bed (SwiftSolve). The authors flag PPO with execution feedback as future work and do not run it here.
The framework is wrong sometimes. A pathological input can dominate, CPU timers are noisy, and the authors suggest virtual cores might help. Labels are empirical curves, not proofs. Everything is Python contest code; C++ and Java constant factors are untested.
Code Contests predates most evaluated models. The authors call contamination a real risk. The test sets ignore the official split because that split is too weak and lacks multi-class problems. There is no multi-turn prompting. The full run cost about 12,000 GPU hours and 180,000 CPU hours.
Failed fine-tuning shows that more of the same data is not enough. It does not show that RL would fix it. That experiment is absent.