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

🔼 The dynamic complexity inference framework analyzes code complexity. It starts with a code snippet and sample inputs. These inputs are systematically expanded using various methods (identity, random, etc.) creating a queue of test cases. Each test case runs in isolation within a sandboxed environment, capturing runtime and memory usage. The collected data reveals the relationship between input size and resource consumption. Curve fitting techniques determine time and space complexity for each individual test and these are combined for a final, overall complexity assessment.

read the caption

Figure 2: Outline of the dynamic complexity inference framework. The framework takes a code snippet and a single example of inputs to this code snippet. Then, it processes the code snippet and proceeds with extensive inputs generation, based on the provided example of inputs: inputs are independently or interdependently increased in size, using several expansion methods that can be the identity or random, among else. This forms a queue of synthetic inputs on which to execute the provided code snippet. These executions happen independently in sandboxes, where runtime and memory footprint measures are taken. Once all the measures are collected, the framework can model the code snippet time and space dependencies to the different inputs. Using curve fitting, the time and space complexity of the code is computed on each input separately and then altogether. The global time and space complexity over all inputs is what is being returned.

🔼 This figure visualizes the distribution of time and space complexity classes within the BigO(Bench) dataset, which comprises 3,105 coding problems. Each problem is represented if at least one solution exists matching a specific time-space complexity pair. The visualization highlights the prevalence of certain complexities: linear time complexity, O(n), accounts for 38% of the solutions, whereas constant space complexity, O(1), represents 25%. Complexities are ordered from most to least computationally efficient, with less frequent complexities grouped under the ‘other’ category. Problems where the complexity framework couldn’t determine either time or space complexity are excluded from this analysis.

read the caption

Figure 3: Distribution of time-space complexity classes across BigO(Bench) dataset of 3,105 coding problems. Each problem is included when at least one solution exists with that specific time-space complexity pair. Linear time O(n) represents 38% of solutions, while constant space O(1) accounts for 25%. The chart orders classes by computational efficiency, with less common classes grouped under “other”. Problems for which the framework can not infer a time complexity and/or a space complexity are not counted.

🔼 This figure analyzes the performance of the complexity inference framework. The top graph displays the distribution of problems with different failure rates, showing that 84% of problems have failure rates under 30%. The bottom heatmap provides a more detailed breakdown of failure rates based on the type and number of inputs used in each problem. This visualization highlights the framework’s robustness across various input configurations.

read the caption

Figure 4: Failure rate analysis of the complexity inference framework. The top plot shows the overall distribution of framework failures across all problems. The bottom heatmap breaks down failure rates by input type and number of distinct inputs. Approximately 84% of problems have failure rates below 30%, demonstrating robust performance across most input configurations.

🔼 This figure visualizes the performance of various Large Language Models (LLMs) on code generation tasks categorized by time complexity and algorithmic approaches. The x-axis represents different algorithmic categories used in the problems (e.g., graph algorithms, string manipulation, etc.). The y-axis represents the accuracy or success rate of the LLMs. Different colored bars represent the various LLMs included in the benchmark. The figure allows for a comparison of LLM performance across various problem types and complexities, highlighting strengths and weaknesses of different models in handling specific algorithmic challenges.

read the caption

Figure 5: LLM results aggregated by time complexity class and by algorithmic notions for all models part of BigO(Bench).

🔼 Figure 6 compares the performance of various large language models (LLMs) across four different coding benchmarks: HumanEval, MBPP, BigCodeBench, and BigO(Bench). HumanEval, MBPP, and BigCodeBench evaluate the models’ ability to generate correct code solutions to programming problems, using the Pass@1 metric which measures the percentage of problems for which the model produces the correct solution on its first try. In contrast, BigO(Bench) assesses not only the correctness but also the efficiency (time and space complexity) of the generated solutions. The BigO(Bench) results utilize the All@1 metric, indicating whether the model successfully generates correct code solutions for all problems while adhering to specific time and space constraints. The figure thus provides a comprehensive overview of LLM capabilities in terms of both code generation accuracy and algorithmic efficiency.

read the caption

Figure 6: Model performance per coding benchmarks: HumanEval, MBPP and BigCodeBench main metrics are all P⁢a⁢s⁢s⁢@⁢1𝑃𝑎𝑠𝑠@1Pass@1italic_P italic_a italic_s italic_s @ 1; for BigO(Bench), we display A⁢l⁢l⁢@⁢1𝐴𝑙𝑙@1All@1italic_A italic_l italic_l @ 1 results.

🔼 Table 2 presents the performance of various Large Language Models (LLMs) on BigO(Bench), a coding benchmark focusing on time and space complexity. The benchmark assesses LLMs across three key tasks: Program Synthesis (generating correct code), Complexity Prediction (identifying the time-space complexity of existing code), and Complexity Generation (creating code meeting specific time-space complexity constraints). The table shows the models’ accuracy (Pass@k, Best@k, All@k) for each task. Pass@k indicates the overall accuracy, considering each problem’s complexity class independently. Best@k focuses on accuracy only for a problem’s most efficient complexity class, while All@k measures whether all complexity classes within a problem are correctly identified.

read the caption

Table 2: BigO(Bench) benchmark results for popular LLMs. Program Synthesis checks correctness of model-generated solutions to given programming problems.Complexity Prediction measures whether a model can find the time-space complexity of a code snippet. Complexity Generation evaluates whether a model outputs a working code snippet to a given problem, that meets a time-space complexity requirement. P⁢a⁢s⁢s⁢@⁢k𝑃𝑎𝑠𝑠@𝑘Pass@kitalic_P italic_a italic_s italic_s @ italic_k treats all complexity classes of all problems independently, B⁢e⁢s⁢t⁢@⁢k𝐵𝑒𝑠𝑡@𝑘Best@kitalic_B italic_e italic_s italic_t @ italic_k only evaluates the most optimized complexity class of each problem, A⁢l⁢l⁢@⁢k𝐴𝑙𝑙@𝑘All@kitalic_A italic_l italic_l @ italic_k measures whether all complexity classes per problem are correct at once.

🔼 This table presents the results of ranking LLMs’ code generation performance against human-written code for the same problem, while considering time and space complexity requirements. The ranking uses the complexity framework described in the paper. The framework evaluates 20 attempts to measure complexity for each model, choosing the best coefficient to assess performance. This assessment considers both time and space complexity. A percentile-based ranking system is employed; for instance, a ranking score of ’n%’ signifies that ’n%’ of human-generated solutions performed worse regarding the complexity coefficient. If a model failed to produce a correct solution, its ranking is zero. The ‘Intersec’ subset highlights the models (marked with *) with at least one successful solution.

read the caption

Table 3: Using the complexity framework, the best measured coefficient of the complexity curve, out of 20 attempts, is used to rank LLM-generated code among human solutions from the same problem and time-space complexity class. Ranking is percentile based, n% ranking score amounts for n% human solutions having worse complexity coefficient. If no LLM solution passes correctness tests, ranking score is set to 0. Intersec is the subset where all starred (*) models have at least one successful solution.

🔼 This table presents the results of fine-tuning the Llama 3.1 70B language model on the BigO(Bench) benchmark for time and space complexity prediction and generation tasks. It shows the model’s performance across several metrics (Pass@1, Pass@10, Best@1, Best@10, All@1, All@10) before and after fine-tuning. These metrics evaluate the accuracy of the model in correctly predicting and generating code that meets specified time and space complexity requirements. The table also compares the performance of the fine-tuned model to its zero-shot and few-shot counterparts.

read the caption

Table 4: BigO(Bench) benchmark results for fine-tuned Llama 3.1 70B on the time-space prediction and generation tasks. Same metrics are reported as in Table 2.