PaperlayerView exact revision on arXiv

Source-linked AI summary

BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?

Pierre Chambon, Baptiste Roziere, Benoit Sagot, Gabriel Synnaeve

arXiv:2503.15242v3cs.CLcs.AIcs.CC

TL;DR

Existing evaluations often overlook whether models understand and generate code under time and space complexity constraints. BigO(Bench) combines a profiling-based Python complexity framework with a large annotated coding benchmark and evaluates leading models. Reasoning models achieve strong contest correctness but remain weak at constrained complexity generation, and fine-tuning yields only marginal gains on prediction tasks.

  • Problem

    Many code-generation evaluations do not test whether models can understand and produce code constrained by computational complexity.

    Source: §1 · p. 2

  • Method

    BigO(Bench) pairs 3,105 Code Contests problems and 1,190,250 solutions with inferred complexity labels and profiling data, using a dynamic framework to evaluate 14 models.

    Source: §1 · p. 2, §3 · p. 4, §7 · p. 12

  • Results

    Current top generation scores reach 6.5% All@1 on time-complexity generation and 5.6% on space-complexity generation, while fine-tuning increases performance only marginally and only on prediction tasks.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    The benchmark provides a way to assess model understanding of coding abstractions beyond pure code generation.

    Source: §7 · p. 12

    Because the public dataset predates most evaluated models, contamination is possible, and repeated leaderboard testing risks overfitting to released test sets.

    Source: Broader Impact Statement · p. 12

Abstract

from arXiv · show

We introduce BigO(Bench), a novel coding benchmark designed to evaluate the capabilities of generative language models in understanding and generating code with specified time and space complexities. This benchmark addresses the gap in current evaluations that often overlook the ability of models to comprehend and produce code constrained by computational complexity. BigO(Bench) includes tooling to infer the algorithmic complexity of any Python function from profiling measurements, including human- or LLM-generated solutions. BigO(Bench) also includes of set of 3,105 coding problems and 1,190,250 solutions from Code Contests annotated with inferred (synthetic) time and space complexity labels from the complexity framework, as well as corresponding runtime and memory footprint values for a large set of input sizes. We present results from evaluating multiple state-of-the-art language models on this benchmark, highlighting their strengths and weaknesses in handling complexity requirements. In particular, token-space reasoning models are unrivaled in code generation but not in complexity understanding, hinting that they may not generalize well to tasks for which no reward was given at training time.

1 Introduction

BigO(Bench) targets the gap between functional code generation and reasoning about time and space complexity. The paper introduces a benchmark and a dynamic complexity framework, then evaluates models on complexity prediction and generation.

1 Introduction

  • Reasoning models exceed 70% pass@1 on CodeForces but reach 4.8% when generating solutions under specified complexity constraints.The introduction also reports that DeepSeek R1 is only 6.8% better than Llama 4 Maverick on complexity prediction.Source: §1 · p. 2
  • BigO(Bench) covers 3,105 coding problems and 1,190,250 Code Contests solutions, with runtime and memory profiling measurements.It evaluates complexity prediction, constrained code generation, and ranking against human solutions of the same challenge and complexity.Source: §1 · p. 2
  • The rule-based framework infers Python time and space complexity through fuzzing, profiling, and regression, matching human annotations on 84% and 82% of time and space test cases.Its labels are statistically significant empirical performance profiles, not theoretical complexities.Source: §1 · p. 2
  • Across 14 models, DeepSeek-R1 Llama70B leads time-complexity prediction at 41.4% All@1, while Qwen3 32B leads time-complexity generation at 6.5% and Llama 3.1 Nemotron-Ultra leads space-complexity generation at 5.6%.The evaluation also includes fine-tuned models.Source: §1 · p. 2

2 Related Work

Prior code-generation benchmarks have focused on functional correctness or runtime efficiency, while complexity-focused work has generally covered narrower tasks. BigO(Bench) combines time and space complexity with open-ended constrained generation and evaluation of model performance.

2 Related Work

  • HumanEval and MBPP became saturated, while broader software-development benchmarks such as SWE-Bench and AssistantBench entail substantial evaluation time and compute costs.HumanEval+ and HumanEvalPack instead extend tests, tasks, or languages.Source: §2 · pp. 2–3
  • Earlier complexity benchmarks largely use classification, limited languages or classes, smaller models, or runtime similarity rather than broad complexity-aware generation.CoRCoD [Sikka et al., 2019], TASTY [Moudgalya et al., 2023], CodeComplex [Baik et al., 2024], and RACE illustrate these scope limits.Source: §2 · p. 3
  • Absolute runtime and resource benchmarks measure code under fixed execution settings, whereas complexity characterizes algorithmic structure and asymptotic performance across input growth.The cited work also includes multi-language efficiency, synthesized constraints, repository optimization, and execution-feedback methods.Source: §2 · p. 3
  • BigO(Bench) specifically tests whether models can predict, generate, and rank solutions under explicit asymptotic constraints; related work studies complementary forms of code difficulty and execution behavior.The paper notes DynaCode's structural and call-graph complexity focus and SwiftSolve's use of this benchmark setting.Source: §2 · p. 3
  • BigO(Bench) covers both time and space complexity across an unconstrained set of classes and adds open-framed generation to classification.The generation task models designing a solution for a target complexity.Source: §2 · p. 3

3 Dynamic Complexity Inference Framework

The framework estimates Python functions’ time and space complexity by running them on expanded inputs and fitting measured runtime and memory behavior. It aggregates per-input estimates into a global complexity and returns curve coefficients that can rank solutions within a class.

3 Dynamic Complexity Inference Framework

  • Complexity is treated as worst-case input growth, but the framework returns empirical estimates rather than proofs and studies Python alone.Natural-language input constraints may be ignored when seeking worst-case behavior, provided the program runs without failing.Source: §3 · pp. 3–4
  • The framework expands example inputs independently or jointly, runs the resulting synthetic inputs in sandboxes, and measures runtime and memory before fitting per-input and global complexity.The returned complexity is the global time and space estimate across the tested inputs.Source: Figure 2 · p. 4
  • Measurements come from Python executions using Cprofiler for runtime and tracemalloc for memory, isolated in Bubblewrap sandboxes to prevent harmful side effects.Multi-argument inputs may be expanded independently or together to capture interdependencies.Source: §3 · p. 4
  • Non-negative least-squares curve fitting selects classes by residuals with a simplicity bias, then ensemble aggregation combines estimates across argument subsets and expansion methods.The framework also returns fitted coefficients for the elected classes, which can rank solutions within the same complexity class.Source: §3 · pp. 4–5
  • The framework’s parameters target accuracy, coverage, and self-consistency across repeated runs and compute instances.The study separately measures how parameter choices affect released labels and how far compute budgets can be reduced before labels degrade.Source: §3 · p. 5

4 Benchmark Data Release

BigO(Bench) is built from filtered, correct Python solutions in Code Contests and links complexity classes to profiling data. The release also measures dataclass-generation performance and evaluates the complexity framework’s accuracy, coverage, and repeatability.

4.1 Composition

  • The final dataset contains 3,105 problems and 1,190,250 annotated solutions after filtering Code Contests to correct Python solutions and removing unsuitable problems.The original pool contained 8,139 problems and 1,485,888 solutions; the release characterizes problems by difficulty, algorithmic notions, and input types.Source: §4.1 · p. 5
  • Each solution links time and space classes to fitted coefficients and the runtime and memory measurements used to infer them.Problems may have multiple complexity classes, with solutions in a class differing in optimization coefficients.Source: §4.1 · p. 5
  • The complexity test sets are filtered for diverse classes, performance, and framework stability, and they do not use the official Code Contests splits.Time and space test sets have distinct problem supports, overlapping on 63 problems.Source: §4.1 · p. 6
  • The time test set covers 311 problems and 11 classes, while the space test set covers 308 problems and five classes; both complexity distributions are imbalanced and heavily tailed.Linear and constant time account for 38% and 20% of solutions; linear and constant space account for 47% and 25%, respectively.Source: §4.1 · p. 6

4.2 Dataclass Generation

  • Problem-specific dataclasses let the framework parse inputs and expand arguments for rerunning solutions at new scales, but problems without a correct dataclass cannot be analyzed dynamically.The table compares models generating these dataclasses for Code Contests problems.Source: §4.2 · p. 6, Table 1 · p. 6
  • Llama 3.1 405B Instruct achieves 58.1% correct backtranslation with one dataclass attempt per problem, rising to 82% of problems when multiple solutions are tried.The backtranslation result is reported for the dataclass-generation task.Source: §4.2 · p. 7

4.3 Complexity Framework Performance

  • The framework matches human labels on 84% of time and 82% of space test-set samples.The human review uses 125 samples per split; section C examines how this error rate may affect model comparisons.Source: §4.3 · p. 7
  • About 84% of problems have framework failure rates below 30%, while 4.5% exceed a 0.9 failure rate.Reported causes include incorrect generated dataclasses and edge cases outside the framework’s test range.Source: §4.3 · p. 7

5 Evaluation

The evaluation tests models on complexity prediction, constrained code generation, and ranking generated solutions against human solutions, alongside program synthesis and fine-tuning experiments. It evaluates popular coding and reasoning models using task-specific metrics.

5 Evaluation

  • The evaluation covers popular coding and reasoning models, mostly in instruct variants and zero-shot settings, with results macro-averaged across complexity classes and problems.Pure program synthesis is assessed on the same test splits using public, private, and generated tests.Source: §5 · p. 7

5.1 Time-Space Complexity Prediction

  • Complexity Prediction asks models to infer time and space complexity from a problem description and human solution, using always-O(n) as the baseline.Outputs are parsed and compared with framework-inferred ground truth; All@k requires correct output across all complexity classes for a problem.Source: §5.1 · pp. 7–8

5.2 Time-Space Complexity Code Generation

  • Complexity Generation requires a correct solution that meets a feasible time or space complexity requirement, with correctness checked against public, private, and generated tests.The baseline is Llama 3.1 70B queried without the complexity requirement; Pass@k measures solutions that are correct and meet the required complexity.Source: §5.2 · p. 8

5.3 Time-Space Complexity Coefficient Percentile Ranking

  • Complexity Coefficient Percentile Ranking compares generated code with human solutions for the same problem and complexity class, using the measured complexity-curve coefficient.Lower coefficients indicate flatter curves; percentile scores indicate the share of human solutions with worse coefficients.Source: §5.3 · p. 9, Table 3 · p. 9

5.4 Prediction and Generation Fine-Tuning

  • Llama 3.1 70B is fine-tuned for prediction and generation using 2,000 problems and 20,000 code solutions, with 10 human examples per problem and complexity class.The models are fine-tuned for 10 epochs in instruct format.Source: §5.4 · p. 9

6 Quantitative Analysis

Models perform worse on combined complexity-constrained generation than on the individual synthesis and prediction tasks, and optimization prompts further reduce time-generation performance. The analysis also identifies difficulty with non-optimal complexity classes and reports limitations in the framework and benchmark scope.

Understanding time-space complexity

  • 12% average loss in time generation All@1 occurs when models are asked to optimize while respecting the complexity requirement, reaching 30% for GPT-4o and o1-mini.Across tasks, reasoning models remain top performers, though space-prediction differences are smaller and less clear.Source: §6 · p. 10
  • Models underperform on non-optimal complexity classes; Qwen3 32B achieves only 6.5 All@1 on time generation.All@1 evaluates optimized and non-optimized solutions uniformly; models may otherwise return a right-complexity solution by reproducing familiar optimized code patterns.Source: §6 · p. 10
  • The Code Contests splits include solutions across complexity classes for problems already seen by models, a qualification relevant to interpreting the results.Source: §6 · p. 10

Token-space reasoning models

  • Qwen2.5-Coder scores 12.6 All@1 on space-complexity prediction, compared with 8.1 for o1-mini, 10.4 for DeepSeek-R1, and 10.3 for Llama Nemotron-Ultra.The authors suggest reasoning models may overthink extra-space complexity and report that they favor optimal solutions when generating less-optimized classes.Source: §6 · pp. 10–11

Developing challenging reasoning benchmarks

  • Complexity fine-tuning barely improves prediction on the same task, while generation fine-tuning slightly hurts performance, suggesting standard fine-tuning may not capture these reasoning tasks effectively.The benchmark is described as robust to fine-tuning.Source: §6 · p. 11

Limitations

  • Framework labels can be affected by worst-case edge cases and noisy measurements based on real CPU runtimes; the benchmark and framework are limited to Python.The authors note that virtual CPU cores could improve measurement reliability and propose adding languages such as C++ and Java to examine cross-language optimization.Source: §6 · p. 11

7 Conclusion

The conclusion summarizes BigO(Bench)’s evaluation of LLMs’ complexity-constrained code generation and prediction, including its empirically profiled time- and space-complexity labels and their measurement caveats. It also reports model results and examines how label errors affect robustness findings.

7 Conclusion

  • BigO(Bench) combines three tasks, 3,105 coding problems, 1,190,250 Code Contests solutions, and a framework that infers time-space complexity from code profiling.The tasks are complexity prediction, generating solutions that meet requested complexity, and optimizing the complexity coefficient relative to human solutions.Source: §7 · pp. 11–12
  • Top reasoning models reached up to 6.5% and 5.6% All@1 on time-space complexity generation tasks, while fine-tuning Llama 3.1 70B improved performance only marginally on prediction.The benchmark evaluated 14 LLMs; the authors describe it as challenging and aim for it to guide work on models’ understanding of coding abstractions beyond code generation.Source: §7 · p. 12

Broader Impact Statement

  • Reproduction requires substantial compute, public-data contamination and leaderboard overfitting are risks, and a single-replica framework setting uses a tenth of the compute while reproducing 96.6% of time-complexity labels.The paper reports approximately 12,000 GPU hours and 180,000 CPU hours; it also provides sandboxing, usage guidelines, and reporting channels for safety concerns.Source: Broader Impact Statement · p. 12

A.1 Dataclass Generation Metrics

  • Dataclass generation is assessed with Corr for executability of both methods and BckTr for round-trip consistency, approximated under a fixed sampling budget.The estimates use equally sampled problems and the first human solution; Corr@k and BckTr@k estimate the chance that at least one of k attempts passes.Source: §A.1 · p. 21

A.2.1 Complexity Prediction Metrics

  • Complexity Prediction uses Pass@k for correctness averaged across classes and problems, Best@k for each problem’s most optimized class, and All@k for joint correctness across classes.Source: §A.2.1 · p. 22

A.2.2 Complexity Generation Metrics

  • Complexity Generation measures correct solutions meeting complexity requirements with Pass@k, Best@k, and All@k; correctness and complexity-class compliance are evaluated separately.A solution can satisfy a complexity requirement without solving the coding challenge, so generation metrics combine the correctness and class-compliance indicators.Source: §A.2.2 · p. 24

A.2.3 Complexity Ranking Metrics

  • Complexity Ranking adds optimization to correct, complexity-compliant generation; COEFF compares the best of 20 samples with human solutions, while COEFFintersect restricts comparison to shared viable problem-class pairs.COEFF ranks the generated coefficient against human solutions for the same problem and complexity class; the intersect variant limits the set to cases where each starred model yields a valid sample.Source: §A.2.3 · pp. 25–26

B Time and Space Complexity: Definitions and Conventions

  • 84% agreement with human annotation on time complexity and 82% on space; the framework estimates labels by fitting runtime and memory measurements from finite executions.It runs solutions over a range of input sizes and fits observed curves to candidate growth functions, without static analysis of source code.Source: B Time and Space Complexity:… · p. 27

B.1 Big-O in Mathematics and Algorithmics

  • A running case scales designated arguments from an example input with a size parameter, making program cost a function to which asymptotic bounds apply; BigO(Bench) uses the worst running case.The generated input must grow without bound, and the generator need only be defined for an infinite set of sizes.Source: §B.1 · pp. 27–28

B.2 Commonly Assumed Big-O Definitions in Programming

  • BigO(Bench) follows programming practice by using big-O for the tightest upper bound on a running case, matching the way complexity questions are commonly posed.The prompts explicitly ask for the tightest possible upper bound so that arbitrarily loose labels such as O(n!) cannot pass.Source: §B.2 · p. 29

B.3 Multi-Variable Complexity

  • For multivariable inputs, the framework measures selected arguments separately and jointly, then combines the fits to distinguish terms such as n × m from n + m.Growing variables together reveals interactions, such as loops nested over two arguments, that separate measurements miss.Source: §B.3 · p. 29

B.4 Asymptotic Complexity Versus Code Competition Constraints

  • BigO(Bench) drops contest timeouts and input bounds, evaluates solutions at multiple complexity levels, and distinguishes accepted but asymptotically slower solutions from more efficient ones.A correct O(n2) solution can be valid for generation even when the original contest intended O(n · log(n)); the framework grows inputs beyond published bounds, up to 3000× the original input size.Source: §B.4 · p. 30

B.5 The Space of Possible Complexity Labels in BigO(Bench)

  • Labels are selected from a finite class set, so programs whose true growth is outside that set receive the nearest representable class; the test sets cover 11 time classes and 5 space classes.Predictions are normalized before comparison so differences in variable names, order, or notation do not affect matching.Source: §B.5 · p. 31

B.6 What a BigO(Bench) Label Is

  • Measured labels are lower bounds on true worst-case complexity because the framework samples only implemented running cases; space means peak extra memory, excluding input storage.The framework also returns a fitted coefficient, which the ranking task uses to compare solutions within a complexity class; memory is measured with tracemalloc and printed output counts.Source: §B.6 · pp. 31–32

B.7 Examples

  • Graph examples show why labels can depend on multiple input sizes and distinguish time from space: traversal may be O(n + m), while adjacency-matrix storage is O(n2) and adjacency-list storage is O(n + m).Different graph growth patterns can make a two-variable traversal appear linear or quadratic when measured along only one running case.Source: §B.7 · p. 32
  • CPython can make repeated string concatenation linear when it resizes in place, but a second live reference disables that optimization and makes the loop quadratic.A bitset subset-sum loop that looks O(n) instead costs O(nW/64), while list membership versus set membership can make the same expression quadratic or linear.Source: §B.7 · p. 33
  • A breadth-first search using list.pop(0) costs O(n2 +m), while adversarial integer-hash collisions can make set insertion quadratic instead of linear on average.Union-find’s amortized O(m · α(n)) cannot be distinguished from O(m) by curve fitting at feasible input sizes; arbitrary-precision multiplication also makes arithmetic nonconstant-time.Source: §B.7 · p. 33

C Robustness of the Evaluation to Label Error

C.1 Label Error in Benchmarks

  • Imperfect labels are common, and BigO(Bench) limits test-set exposure to faulty Code Contests tests by retaining problems with at least 50 passing human solutions.The authors also note that measured complexity can diverge from theoretical worst-case complexity, so disagreement with human annotation may reflect different targets rather than error.Source: §C.1 · pp. 35–36

C.2 What the Error Rate Actually Is

  • Across 12,800 repeated attempts, replicate pairs agreed on complexity class 96.7%–97.1% of the time, and verdict noise shifted Pass@1 by about 0.05 points.The three replicates scored Pass@1 15.2 / 15.1 / 15.2, Best@1 17.7 / 17.8 / 17.6, and All@1 1.8 / 1.8 / 1.8; disagreements clustered in adjacent classes or variable permutations.Source: §C.2 · p. 36, Table 7 · p. 36

C.3 Ranking Stability Under Simulated Systematic Label Corruption

  • In 11 of 12 corruption cells, model-score spread was at most 2.3 pp; inversions were rare except for space prediction under optimistic error, where 9 of 66 pairs inverted.At a 15% target corruption rate on generation, no cell had more than 3 inverting pairs out of 66.Source: §C.3 · p. 37, Table 8 · p. 37, Table 9 · p. 38
  • Space prediction under 15% optimistic corruption is the exception: Llama 4 Scout gains as weaker models benefit from O(n) collapsing to O(1), so this task’s ranking warrants more caution.The best and worst models, Qwen3 32B at 47.7 and Llama 4 Scout at 37.4 Pass@1, are 27% apart, but middle models score 43.2–45.6 and become hard to distinguish.Source: §C.3 · pp. 38–39, Table 10 · p. 39

C.4 Sharing Label Errors Across Model Evaluations

C.4 argues that shared label errors largely cancel in model comparisons, so per-label error rates overstate ranking uncertainty. C.5 finds label noise smaller than finite test-set variability on generation and still smaller on prediction under a conservative corruption rate; the prompt variants specify different analysis and code-generation instructions.

C.4 Sharing Label Errors Across Model Evaluations

  • Shared framework and label errors largely cancel in pairwise model comparisons, so per-label error rates overstate ranking uncertainty.Under independent per-model corruption, score-difference variability is inflated by 1.8 to 3.0 times; generation labels are not literally shared, but framework biases are.Source: §C.4 · pp. 39–40, Table 11 · p. 40

C.5 Putting Together All Sources of Variance

  • Generation label noise contributes about one seventeenth of finite-test-set variability at 3% corruption and one eighth at 15%.On prediction, label noise is 0.58 of problem-sampling variability on time and 0.72 on space at 15%; up to 20% corruption inverted at most 3 of 66 model pairs.Source: Table 12 · p. 40, §C.5 · pp. 40–41

D.1 Original BigOBench Prompt - Time Complexity Prediction

  • The original prediction prompt asks for worst-case time complexity under valid input types, while discounting stated size constraints and counting operations and output memory.It also asks models to account for Python-specific behavior.Source: §D.1 · p. 42

D.2 Big-Theta Variant - Time Complexity Prediction

  • The Big-Theta prediction variant keeps the worst-case setup but requests a Big-Theta time-complexity answer instead of Big-O.It retains the instruction to ignore stated input-size constraints.Source: §D.2 · p. 42

D.3 Detailed Big-O variant - Time Complexity Prediction

  • The detailed Big-O variant requests the tightest worst-case upper bound and explicitly warns against loose bounds such as O(n^2) for an O(nlogn) case.It also directs models to ignore stated input-size constraints.Source: §D.3 · pp. 42–43

D.4 COT Big-O variant - Time Complexity Prediction

  • The COT Big-O prediction prompt asks models to analyze loops, operations, memory costs, and adversarial cases before returning the tightest upper bound.It specifies ten analysis instructions and requires the final Big-O answer.Source: §D.4 · p. 43

D.5 Original BigOBench Prompt - Time Complexity Ranking

  • The original ranking prompt asks for Python code that solves the problem, meets the target time complexity, and optimizes runtime within that constraint.It also gives worst-case and Python-specific evaluation assumptions.Source: §D.5 · pp. 43–44

D.6 Python Specifications Big-O variant - Time Complexity Ranking

  • The Python-specifications ranking variant adds Python 3.10 compatibility, library guidance, memory-use preferences, and edge-case assumptions.It still requires code to meet the target complexity and minimize unnecessary operations.Source: §D.6 · p. 44

D.7 Ablation Results

Prompt ablations produced different outcomes for reasoning and non-reasoning models across prediction and generation. More detailed prompts lowered the reasoning model’s prediction score but improved its generation result, while Python specifications yielded only a marginal ranking improvement.

D.7 Ablation Results

  • 31.8 All@1 for the reasoning model under COT prompting, versus 40.4 on the main Time Complexity Prediction prompt.The non-reasoning model improved with detailed and COT variants, reaching 36.1 All@1, but remained below the reasoning model.Source: §D.7 · pp. 44–45, Table 13 · p. 45
  • 11.7 All@1 for the reasoning model with the Big-Theta Time Complexity Generation prompt, versus its 9.6 base score; the non-reasoning model saw no prompt-variant improvement.The non-reasoning model’s base score was 3.3 All@1; the authors suggest added detail helps focus on complexity rather than correctness without prompting overthinking.Source: §D.7 · p. 45, Table 13 · p. 45
  • Python specifications yielded a marginal ranking improvement, up to +2 coeffFULL for Qwen QwQ.Table 14 reports the prompt-variation results for Complexity Ranking.Source: §D.7 · p. 45, Table 14 · p. 46

E Multi-sample Results Scores

Multi-sample evaluation shows that leading models improve with larger generation budgets, especially on All@k and the harder space-complexity task. Yet all models remain below 10 All@1 on time-space complexity generation, and the gains become more marginal as k grows for Pass@k.

E Multi-sample Results Scores

  • Complexity Prediction is reported only at @1 because its small, fixed classification output space makes repeated sampling a poor measure of exploration.The multi-sample estimates are used for prediction, generation, and ranking metrics as appropriate.Source: E Multi-sample Results Scores · p. 47
  • 26.1 All@10 for Qwen3 32B on time-complexity generation and 23.7 All@10 for Llama 3.1 Nemotron-Ultra 253B on space-complexity generation.They also led at All@1 with 6.5 and 5.6, respectively.Source: E Multi-sample Results Scores · p. 48
  • Higher sampling budgets generally preserve model ordering, though Gemma 3 shows less return; reasoning models benefit more, especially on time-complexity generation.Figure 9 compares Pass@k and All@k gains across models.Source: E Multi-sample Results Scores · p. 48, Figure 9 · p. 49
  • Across models, time-complexity generation rose 100% from Pass@1 to Pass@10 and 275% from All@1 to All@10; space-complexity generation rose 110% and up to 450%, respectively.Gains at higher k were larger for All@k than Pass@k and for space than time generation.Source: E Multi-sample Results Scores · p. 48
  • For time generation, average Pass@5 is 70% above Pass@1, while Pass@10 is 15% above Pass@5; All@5 is 160% above All@1, and All@10 is 40% above All@5.Between k=9 and k=10, All@k still grows twice as fast as Pass@k.Source: E Multi-sample Results Scores · p. 49
  • All models remain below 10 All@1 on time-space complexity generation, but doubling the sampling budget already yields substantial gains.The score tables report multiple @k estimators; Pass@k averages over complexity classes, while All@k requires all classes to be correct or generated simultaneously.Source: Table 15 · p. 47, Table 16 · p. 48, E Multi-sample Results Scores · p. 49

F Fine-Tuning Experiments More Results

The fine-tuning appendix expands the Llama 3.1 70B experiments across four prediction and generation training variants and evaluates them on time- and space-complexity tasks. It reports multiple sampling-budget estimators and summarizes generation gains across model variants visually.

F Fine-Tuning Experiments More Results

G Tasks Correlations

Across models, program synthesis scores correlate most strongly with complexity generation, while prediction and generation are nearly independent for individual problems. The following analysis separates generation failures by correctness and complexity-class match.

G Tasks Correlations

  • Program synthesis correlates with complexity generation at 0.81 for time and 0.76 for space, the strongest task correlations across models in the appendix sweep.Time prediction correlates 0.56 with time generation, while space prediction correlates only 0.1 with space generation.Source: G Tasks Correlations · p. 54
  • Space prediction correlates 0.5 with time prediction but only 0.1 with space generation; time prediction correlates more with time generation than with space prediction.Time and space generation correlate more strongly with each other than with their respective prediction tasks.Source: G Tasks Correlations · p. 54

H Where Do the Differences in Complexity Prediction and Generation Come From

  • The next analysis separates generation attempts by whether code passes tests and whether its measured complexity matches the request, distinguishing types of failure.The section notes an existing gap between prediction and generation scores and examines what generation failures consist of.Source: H Where Do the Differences in… · p. 55

H.1 What Generation Failures Are Made Of

Generation failures often involve working code in the wrong complexity class, especially when the requested target is suboptimal; models tend to overshoot toward faster code. At the individual-problem level, prediction and generation are nearly separate skills, while the accompanying framework estimates complexity through profiled executions and curve fitting.

H.1 What Generation Failures Are Made Of

  • Working programs in the wrong complexity class make up 14% of Codestral 22B’s failures and 70% of Llama 3.1 Nemotron-Ultra 253B’s, and this share rises with program-synthesis ability.The same pattern appears on space complexity, where working-code failures range from 17% to 68%; comparisons are qualified because stronger models solve harder problems.Source: §H.1 · p. 55, Table 21 · p. 55
  • For Nemotron-Ultra, success falls from 51.8% to 15.6% on suboptimal targets, while working-code failures rise from 58.0% to 76.5%.The findings hold across every model; models continue producing correct programs but miss the requested class.Source: §H.1 · pp. 55–56, Table 22 · p. 56

H.2 Which Way Models Miss

  • On failing suboptimal requests, models produce faster-than-requested classes in 61%–94% of attempts, versus 0.4%–12% slower, across models and both axes.The faster-to-slower miss ratio ranges from 5:1 to over 200:1; the text notes models do not generally add redundant work to meet slower targets.Source: §H.2 · p. 56, Figure 14 · p. 58

H.3 Prediction and Generation Performance Discrepancies at the Item Level

  • All 20 within-model correlations between per-problem complexity prediction and generation fall between +0.04 and +0.26, indicating little correspondence between the skills.Prediction scores cluster at 0 or 100 while generation scores span the range; the table covers 640 time and 636 space problem-class points per model.Source: §H.3 · p. 56, Table 23 · p. 57, Figure 15 · p. 58

I.1 General Framework Outline

  • The framework takes a Python function and example inputs, expands input sizes, profiles runtime and memory, then fits candidate complexity curves and aggregates results across input expansions.It uses non-negative least-squares fitting, selects classes by residuals with a simplicity bias, and can return curve coefficients for ranking solutions within a class.Source: §I.1 · p. 60

I.2 Complexity Framework Inputs

  • For I/O-based snippets, an external dataclass specifies how to parse concatenated inputs into arguments; call-based snippets already expose their argument structure.The framework supports both formats, although the paper’s datasets and results use the dataclass format.Source: §I.2 · pp. 60–61

I.3 Fuzzing and Worst Running Cases

  • Worst-case estimates come from fuzzing edge-case inputs across sizes and argument-growth strategies, then fitting curves to the worst observed execution and memory profiles.On 250 human-reviewed samples, framework accuracy is 84% for time and 82% for space; self-consistency is 91.9% and 89.1%, respectively.Source: §I.3 · p. 62

I.4 Variance Reduction Techniques

  • Repeating measurements R times and aggregating them reduces noise; minimum aggregation improved framework accuracy by 3.5% over median and 19% over maximum aggregation.The production setting uses R = 10; the authors attribute high runtime outliers to external factors that inflate measurements.Source: §I.4 · p. 62

I.6 Sensitivity to Complexity Framework Parameters

The parameter sensitivity study changes one fitting-stage parameter at a time and measures agreement with the released time-complexity labels. Two settings dominate the observed sensitivity, but agreement is maximized at the production configuration by construction.

I.6 Sensitivity to Complexity Framework Parameters

  • The sensitivity study measures agreement with released labels, which is maximized at the production configuration by construction and does not establish that another configuration would be worse in general.Differences below about 0.5 points are within run-to-run nondeterminism.Source: §I.6 · p. 63, Table 24 · p. 64
  • Zeroing the first measured point moves 39.6 points of labels, while collapsing negligible fitted terms moves 20.9; other settings move at most 11 points.The first setting removes the interpreter warm-up sample; the second can reduce a fit such as n^2 + n to O(n^2) when the n term’s coefficient is negligible.Source: §I.6 · pp. 63–64, Figure 17 · p. 64
  • Max-aggregation is the worst tested aggregation at −8.9; the production aggregator uses the minimum and falls back when the resulting curve is not monotone.The paper attributes the max result to runtime noise inflating measurements; differences below 0.5 points are near fitting noise.Source: §I.6 · pp. 64–65

I.7 Compute Budget Versus Label Quality

The compute-budget sweep varies measurement replicas and the maximum input multiplier while holding generators fixed. It finds that reducing replicas preserves label agreement far better than truncating the input range.

I.7 Compute Budget Versus Label Quality

  • In a 5 × 6 sweep of replica counts and multiplier caps, every Pareto-frontier configuration kept the full input range, including R=1 at full range and R=10 capped at 32×.The sweep held generators fixed and used 640 time-complexity test solutions.Source: §I.7 · p. 65
  • A single replica over the full range uses one tenth of the compute and retains 96.6% label agreement, with at least 80.6% accuracy against human annotations.Capping the range at 32× costs 96 times less but retains only 40.6% of labels; reported cost excludes sandbox and framework overhead.Source: §I.7 · pp. 65–66, Table 25 · p. 65

I.8 Implementation Limitations and Future Directions

The complexity inference framework is presented as a proof of concept, with reliability, noise, complexity coverage, and performance identified as improvement areas.

I.8 Implementation Limitations and Future Directions

  • The framework is a proof of concept, and its performance is limited, making measurement and improvement priorities.The authors also propose refactoring and more stable measurement methods.Source: §I.8 · pp. 66–67
  • Alternative fuzzers, including LLM-based approaches, could be tested for their effects on bias, coverage, and complexity-evaluation accuracy.The authors also suggest investigating LLM-generated input edge cases.Source: §I.8 · p. 66
  • Profiler noise can make complexity fitting difficult, while deterministic CPU operations, post-processing, and variance reduction are proposed for more stable results.The authors cite the Hodges-Lehmann estimator as one possible variance-reduction technique.Source: §I.8 · p. 66
  • The framework combines base curve-fitting functions with addition and multiplication, but its current complexity assumptions may not match widely used definitions.The authors note that current assumptions may be inaccurate or inconsistent with broader definitions of code complexity.Source: §I.8 · p. 66
  • The framework fits only functions represented by defined curve classes; currently, classes for x → x^3 log x and x → (log x)^6 are absent.The authors recommend testing labeled examples when adding a function class because similar behavior over input sizes 1–10,000 and profiler noise can challenge fitting.Source: §I.8 · pp. 66–67

J Benchmark Experimental Setup

The section documents the compute and statistical setup, then illustrates the benchmark’s prediction and complexity-constrained generation prompts with example model responses.

J Benchmark Experimental Setup

  • The full experiments used 12,000 GPU hours and 180,000 CPU hours; a single-replica configuration costs one-tenth as much and reproduces 96.6% of released time-complexity labels.The authors caution that larger compute reductions come at a real cost in label quality and are not recommended.Source: J Benchmark Experimental Setup · p. 68
  • Model comparisons use one-tailed paired t-tests over 1,000 bootstrap samples, and each @k metric uses an unbiased estimator based on 20 samples.The tests assume approximately normally distributed performance differences and preserve paired task results through resampling; only DeepSeek-R1 distilled models are reported.Source: J Benchmark Experimental Setup · p. 68

K Licenses

  • Table 26 lists the licenses for code repositories, datasets, and models used in the study.The table also includes licenses for locally downloaded and run models.Source: K Licenses · p. 70, Table 26 · p. 70

L Complexity Prediction Example

  • The prediction example gives a programming problem and human solution, then asks the model to return only the worst-case time complexity.The illustrated response identifies the solution’s time complexity as O(n log n), attributing the dominant term to sorting.Source: L Complexity Prediction Example · p. 71, §L.1 · p. 72, §L.2 · p. 73

L.1 Example of query

  • The prediction query specifies input and measurement assumptions, including that inputs need not satisfy problem constraints and printed output counts toward memory.It asks for worst-case big-O time complexity as if inputs could be as large as possible.Source: §L.1 · pp. 71–72

L.2 Example of response from DeepSeek-R1 Llama 70B

  • In the example response, DeepSeek-R1 Llama 70B gives O(n log n), based on sorting two lists and treating list membership as O(n).The response identifies sorting as the dominant term.Source: §L.2 · p. 73

M Complexity Generation Example

  • The generation example distinguishes solving the problem from meeting its requested complexity: the code is correct but is classified as faster than requested O(n log n).That mismatch counts as a failure for the complexity-constrained generation metric.Source: M Complexity Generation Example · p. 74

M.1 Example of query

  • The generation query asks for Python code solving the segment-intersection problem with time complexity O(n.log(n)).The prompt also specifies input and runtime-measurement assumptions, including that printed output contributes to memory.Source: §M.1 · pp. 74–75

M.2 Example of response from DeepSeek-R1 Llama 70B

This part presents DeepSeek-R1 Llama 70B’s segment-removal solution, which uses prefix and suffix extrema to find intersections efficiently, and discusses how the correct solution misses its required complexity target. It also describes complexity distributions across algorithmic categories and difficulty levels.

M.2 Example of response from DeepSeek-R1 Llama 70B

  • For each removed segment, the remaining intersection runs from the maximum left endpoint to the minimum right endpoint, with its length clamped at zero.The model seeks the removal yielding the greatest such length.Source: §M.2 · pp. 75–76
  • Prefix and suffix maxima of left endpoints and minima of right endpoints let the model compute each removal’s intersection from the elements on either side.For the first or last segment, it uses only the suffix or prefix, respectively.Source: §M.2 · pp. 76–77
  • The model checks its approach on examples, obtaining maximum intersection lengths of 1 and 7 before proceeding to implementation.It later also reports a maximum of 0 for another test case.Source: §M.2 · pp. 77, 79
  • The model estimates O(n) time overall: it builds the prefix and suffix arrays in linear time, then evaluates each removal with O(1) operations.It notes this is acceptable for n up to 3e5.Source: §M.2 · pp. 75, 79
  • The example solution uses prefix and suffix arrays to compute each remaining-segment intersection and track the maximum length in O(n) time.The approach was described as suitable for inputs of up to 300,000 segments.Source: §M.2 · p. 81

M.3 Note on the LLM solution

  • The LLM solution passed public and private tests but ran in O(n), failing the required O(n.log(n)) time complexity.Source: §M.3 · p. 81

N Repartition of Complexity Classes per Algorithmic Notions

O LLM Usage

  • LLMs assisted with proofreading, rewriting, formatting formulas in LaTeX, explaining implementations, and academic writing structure, while the authors retained the research contributions.Source: O LLM Usage · p. 85
Loading 2503.15242v3…