PaperlayerView exact revision on arXiv

Source-linked AI summary

EffiBench: Benchmarking the Efficiency of Automatically Generated Code

Dong Huang, Yuhao Qing, Weiyi Shang, Heming Cui, Jie M. Zhang

arXiv:2402.02037v6cs.SEcs.CL

TL;DR

Research on generated-code correctness has paid less attention to efficiency, despite its relevance to resource use and sustainability. EffiBench evaluates code from 42 LLMs on 1,000 efficiency-critical problems against canonical solutions. Generated code was generally less efficient, with GPT-4 averaging 3.12 times the canonical solutions’ execution time.

  • Problem

    The efficiency of LLM-generated code is less studied than its correctness, although efficiency affects execution speed, memory use, and sustainability.

    Source: §1 · p. 2

  • Method

    EffiBench evaluates generated code on 1,000 efficiency-critical LeetCode problems paired with executable canonical solutions and measures execution time and memory use.

    Source: §1 · p. 3

  • Results

    Across 42 LLMs, generated code was generally less efficient than canonical solutions; GPT-4 averaged 3.12 times their execution time.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Higher pass@1 does not necessarily mean more efficient code: GPT-4-turbo-preview scored higher than GPT-4 on pass@1 but was less efficient.

    Source: §1 · p. 3

Abstract

from arXiv · show

Code generation models have increasingly become integral to aiding software development. Although current research has thoroughly examined the correctness of the code produced by code generation models, a vital aspect that plays a pivotal role in green computing and sustainability efforts has often been neglected. This paper presents EffiBench, a benchmark with 1,000 efficiency-critical coding problems to assess the efficiency of code generated by code generation models. EffiBench contains a diverse set of LeetCode coding problems. Each problem is paired with an executable human-written canonical solution, which obtains the SOTA efficiency on the LeetCode solution leaderboard. With EffiBench, we empirically examine the ability of 42 large language models (35 open-source and 7 closed-source) to generate efficient code. Our evaluation results demonstrate that the efficiency of the code generated by LLMs is generally worse than the efficiency of human-written canonical solutions. For example, GPT-4 generated code has an average \textbf{3.12} times execution time that of the human-written canonical solutions. In the most extreme cases, the execution time and total memory usage of GPT-4 generated code are \textbf{13.89} and \textbf{43.92} times that of the canonical solutions. The source code of EffiBench is released on https://github.com/huangd1999/EffiBench. We also provide the LeaderBoard at https://huggingface.co/spaces/EffiBench/effibench-leaderboard.

1 Introduction

The introduction argues that code efficiency is underexamined despite its importance for execution speed, memory use, and sustainability. It presents EffiBench to measure generated-code efficiency and reports that even strong models lag behind human-written canonical solutions.

1 Introduction

  • Efficiency matters for execution speed and memory use, particularly in resource-constrained settings, and is linked to scalable, sustainable software.The paper also connects efficient code with reduced energy consumption and carbon footprint.Source: §1 · p. 2
  • For merging two sorted arrays, Copilot’s bubble-sort approach has O((n + m)^2) time complexity, while GPT-4’s single-pass merge has O(n + m) time complexity.Both approaches use O(n + m) space.Source: §1 · p. 2, Figure 1 · p. 2
  • Existing correctness-focused benchmarks often use simple tasks and lack diverse, comprehensive test cases, limiting their ability to distinguish efficiency.The paper also notes that many tasks are not inherently efficiency-critical.Source: §1 · pp. 2–3
  • EffiBench introduces a benchmark of 1,000 efficiency-critical coding problems, each paired with an executable human-written canonical solution.It also provides generated test cases and measures execution time, maximum memory, and total memory usage.Source: §1 · p. 3
  • Across 42 LLMs, generated code was generally less efficient than canonical solutions; GPT-4 averaged 3.12 times their execution time.In the most extreme cases, GPT-4 code used 13.89 times the execution time and 43.92 times the total memory of canonical solutions.Source: §1 · p. 3

2 Related Work

Related work reviews the evolution and uses of code-focused LLMs, then surveys code-generation benchmarks and the emerging attention to efficiency.

2.1 LLMs for Code

  • Code-focused LLMs span pretrained and fine-tuned models and support tasks including repair, testing, translation, type prediction, and summarization.Examples include AlphaCode, CodeGen, Codex, CodeLLaMA, WizardCoder, and Phi-3.Source: §2.1 · p. 3

2.2 Code Generation Benchmarks

  • Benchmark extensions add improved tests or altered prompts, while others broaden language coverage or target data science and software-engineering tasks.Examples include HumanEval+ and ReCode, as well as HumanEval-X, DS-1000, APIBench, and SWE-Bench.Source: §2.2 · pp. 3–4
  • Prior studies report that LLM-generated code tends to use more execution time and memory than canonical solutions, motivating EFFIBENCH’s efficiency focus.The paper distinguishes its dataset-construction and efficiency-benchmarking focus from work centered on task collection and reliable assessment.Source: §2.2 · p. 4

3 Benchmark Construction

EffiBench selects efficiency-critical LeetCode problems, pairs them with executable canonical solutions, supplies diverse test cases, and evaluates code with execution-time and memory metrics.

3.1 Efficiency-critical Problem Collection

  • The collection process narrows 2,605 LeetCode candidates to 1,146 problems tagged with widely covered textbook algorithms.Candidates are drawn from frequently appearing problems; the algorithm-topic mapping uses LeetCode tags.Source: §3.1 · p. 4

3.2 Canonical Solution Construction

  • The final dataset contains 1,000 problems with executable canonical solutions collected from top-starred LeetCode discussions and manually adapted for non-LeetCode execution.Solutions requiring specialized LeetCode-only packages are removed.Source: §3.2 · p. 4

3.3 Test Case Generation

  • A per-problem test generator produces cases varying input size, data distribution, and edge cases; 100 tests are provided for the paper’s evaluation.Users can choose how many tests to generate.Source: §3.3 · pp. 4–5

3.4 Efficiency Metrics

  • Execution-time metrics compare generated-code runtime with canonical runtime, while maximum-memory metrics compare generated-code peaks with the canonical baseline.The benchmark includes raw and normalized execution-time and maximum-memory measures.Source: §3.4 · p. 5
  • Total Memory Usage captures memory consumption over time by integrating a recorded memory profile, and its normalized form compares generated and canonical solutions.A lower TMU indicates greater memory efficiency.Source: §3.4 · p. 6

4 Benchmark Statistics

The benchmark statistics describe problem difficulty and algorithm coverage, and compare EffiBench’s efficiency focus with existing code-generation datasets.

4 Benchmark Statistics

  • EffiBench contains 171 easy, 589 medium, and 240 hard problems, using LeetCode’s difficulty definitions.A problem may belong to more than one algorithm class, so algorithm counts can sum to more than the dataset total.Source: §4 · p. 6
  • The dataset spans multiple algorithm categories, including 277 dynamic-programming problems, 243 greedy problems, and 48 backtracking problems.It also averages 212.0 words per problem description and 14.6 lines per canonical solution.Source: §4 · p. 6
  • Unlike datasets focused on whether code passes tests, EffiBench also analyzes efficiency during execution while remaining usable for correctness evaluation.The comparison covers HumanEval, MBPP, APPS, DSP, and DS-1000.Source: §4 · p. 6

5 Evaluation

EFFIBENCH evaluates code efficiency across 42 language models, measuring execution time and memory alongside correctness. Generated code generally incurs more overhead than canonical solutions, with results varying across models, tasks, and algorithm subsets.

5 Evaluation

  • Under MBPP-style prompts, efficiency is measured only for outputs passing all tests, using a fixed edge-server setup where model rankings remain stable across tested environments.The prompt includes a task description, examples, and an assertion specifying the function signature and input/output format.Source: §5 · pp. 6–7

5.1 End2End Results

  • StarCoder2-15B, the most efficient open-source model, still required 2.59x execution time, 1.71x maximum memory, and 4.83x total memory versus canonical solutions.The authors suggest canonical optimal solutions are relatively rare in training data; lower-pass@1 models also tend to be more efficient because they solve relatively simple problems correctly.Source: §5.1 · p. 7
  • All evaluated models’ correct code used more resources than canonical solutions; GPT-4 averaged 3.12x execution time and 6.36x total memory usage.The table reports code-efficiency metrics for the evaluated LLMs.Source: §5.1 · p. 7, Table 3 · p. 8
  • 23 of 35 open-source models had pass@1 below 10%; GPT-3.5-turbo’s pass@1 rose from 42.3% to 49.3% as execution time rose from 3.18x to 3.40x.Efficiency rankings across basic metrics were generally consistent; GPT-4 was most efficient on most closed-source metrics and close to the leaders on others.Source: §5.1 · pp. 8–9

5.2 Results with Identical Coding Problems

  • On 210 problems solved by every closed-source model, GPT models outperformed Claude models in code efficiency, with GPT-4 highest on most metrics.Results on this shared-problem subset differed slightly from the broader Table 3 results.Source: Table 4 · p. 8, §5.2 · p. 9

5.3 Results for Different Algorithms

  • Efficiency varied across algorithm subsets: GPT-3.5-turbo-0301 required 7.73x total memory for dynamic programming, versus 5.68x and 5.83x NTMU for DFS and binary search.The authors attribute subset differences to training-data availability, while noting that a task’s assigned algorithm may differ from the algorithm generated code uses.Source: §5.3 · p. 9

5.4 Worst Case Analysis

  • Among GPT-3.5-turbo-0301’s ten most inefficient snippets, dynamic programming and backtracking appeared most often, especially for NTMU.The analysis groups the top ten inefficient code examples by algorithm for each of NET, NMU, and NTMU.Source: §5.4 · p. 10, Table 6 · p. 10
  • A GPT-3.5-turbo-0301 dynamic-programming example used 70.62x the canonical solution’s memory; its full matrix used O(n × k) space rather than O(k) rolling storage.The canonical solution maintains two lists, reducing memory overhead when n and k are large.Source: §5.4 · p. 10

6 Conclusion and Future work

EFFIBENCH provides 1,000 problems across 11 algorithmic subsets to evaluate generated code’s execution time and memory use. The authors also provide a Hugging Face evaluation server and identify additional programming languages as future extensions.

6 Conclusion and Future work

  • EFFIBENCH contains 1,000 problems across 11 algorithmic subsets and evaluates generated code using execution-time and memory-usage analysis.The benchmark is designed to evaluate code generated by code-generation models.Source: §6 · p. 10
  • A Hugging Face server lets researchers evaluate methods using the same hardware and software.The paper states that the benchmark aims to encourage attention to code efficiency and sustainability alongside correctness.Source: §6 · p. 10
  • The authors identify C++, Java, JavaScript, and Go as possible languages for future EFFIBENCH extensions.Source: §6 · p. 10

A.1 Limiations

EffiBench is limited to Python and LeetCode’s primarily algorithmic problems, while results may also vary across hardware and software environments.

A.1 Limiations

  • EffiBench covers only Python, limiting evaluation across different language paradigms.The authors state this prevents a comprehensive understanding of efficiency across those paradigms.Source: §A.1 · p. 18
  • EffiBench focuses on LeetCode’s primarily algorithmic problems, excluding real-world applications and coding scenarios with different efficiency considerations.Source: §A.1 · p. 18
  • Efficiency results may vary across hardware and software environments, motivating standardized testing conditions.The authors provide a leaderboard request link that uses the same testing environment.Source: §A.1 · p. 18

A.2 Improvement Strategies

The authors propose expanding language and dataset coverage and standardizing testing environments to address EffiBench’s limitations.

A.2 Improvement Strategies

  • The authors plan to broaden the benchmark beyond Python to cover more programming languages and language paradigms.Source: §A.2 · p. 18
  • They plan to incorporate more diverse datasets, while their framework can already be used with datasets such as HumanEval and MBPP.They identify real-world applications and other coding contexts as areas for broader coverage.Source: §A.2 · p. 18
  • They provide a leaderboard request link using the same testing environment and plan a server for standardized efficiency testing.The proposed server would let developers automatically obtain efficiency metrics for LLM-generated code.Source: §A.2 · p. 18

A.3 Broader Impacts

The paper describes potential positive and negative societal impacts of improving the efficiency of LLM-generated code, including software, environmental, and workforce considerations.

A.3 Broader Impacts

  • More efficient code can run faster and consume less memory and processing power, potentially improving responsiveness, operational costs, and user experience.Source: §A.3 · p. 18
  • More efficient code can reduce energy consumption, support sustainability, and help software handle larger volumes of data and users.Source: §A.3 · pp. 18–19
  • LLMs can augment developer productivity by generating code snippets and recommendations, freeing time for more complex tasks.Source: §A.3 · p. 18
  • The paper identifies potential job displacement, over-reliance on AI, and security risks as negative impacts of LLM use in code generation.It notes risks including reduced understanding of generated code and vulnerabilities that malicious actors could exploit.Source: §A.3 · p. 19
  • LLM-generated code may fall short in readability, maintainability, or coding standards, potentially complicating long-term maintenance and development.Source: §A.3 · p. 19

A.4 Efficiency Metrics

EffiBench evaluates execution time and memory use with absolute and canonical-solution-relative metrics, including total memory use over time.

A.4 Efficiency Metrics

  • Execution Time (ET) measures average code execution time, while Max Memory Usage (MU) measures average maximum memory consumption.The paper notes MU is relevant to resource efficiency where maximum memory capacity is limited.Source: §A.4 · p. 19
  • Normalized Execution Time (NET) compares generated-code execution time with the canonical solution; values above 1 indicate slower code, and values below 1 indicate faster code.Source: §A.4 · p. 19
  • Normalized Max Memory Usage (NMU) compares generated-code maximum memory use with the canonical solution’s, with values below 1 indicating greater memory efficiency.Source: §A.4 · pp. 19–20
  • The paper evaluates normalized efficiency metrics at the task level rather than by aggregating all generated code and canonical solutions.The authors also provide scripts for the alternative calculation strategy.Source: §A.4 · p. 19
  • Total Memory Usage (TMU) integrates a sampled memory-usage profile over execution time, and lower values indicate greater memory efficiency.Source: §A.4 · p. 20
  • Normalized Total Memory Usage (NTMU) compares generated-code TMU with canonical-solution TMU; values above 1 indicate less efficient dynamic-memory management.Source: §A.4 · p. 20

A.5 Model

The evaluation covers a broad range of open- and closed-source code-generation models, assessing efficiency only for solutions that pass all provided tests.

A.5 Model

  • The open-source cohort spans CodeLlama, DeepSeek-Coder, StarCoder, WizardCoder, Yi, and other models; closed-source models include GPT-3.5, GPT-4, and Claude 3.Source: §A.5 · p. 20
  • For each model, the authors measure efficiency only on generated solutions that pass every test case provided by the dataset.Source: §A.5 · p. 20

A.6 Generalizability for other Benchmarks

This section examines EffiBench’s application to HumanEval+ and MBPP+ and details evaluation choices and supporting processes, including test-generation accuracy, overhead, and test-generation procedures.

A.7 Efficiency metrics distribution

  • Only 0.23% of Claude-3-sonnet’s correct code is more efficient than canonical code, while 99.77% has NET at least 1; most GPT-3.5-turbo-0301 code is also less efficient.The authors suggest training data that prioritizes correctness over efficiency may contribute to this pattern.Source: §A.7 · p. 22, Table 9 · p. 22, §A.13 · p. 28

A.8 Case illustration for worst case

  • GPT-3.5-turbo-0301’s BFS case uses 50.1 MB*seconds versus 7.5 MB*seconds for the canonical solution, which uses bidirectional BFS to reduce the search breadth.The generated solution uses a list-based queue and visited-state sets; the canonical solution searches from both ends with dictionaries and deques.Source: §A.8 · pp. 23, 25, Figure 4 · p. 24
  • GPT-3.5-turbo-0301’s backtracking code uses 34.36 times more memory than the canonical solution, which prunes invalid paths earlier and manages temporary segments dynamically.The generated code recursively checks possible segment combinations, retaining stack and path state.Source: §A.8 · p. 25, Figure 5 · p. 25

A.6 Generalizability for other Benchmarks

  • On HumanEval+, OpenCodeInterpreter-DS-1.3B has NET 0.86, and results on HumanEval+ and MBPP+ show code close to or sometimes more efficient than canonical solutions.The paper reports that EFFIBENCH’s framework can integrate with other benchmarks.Source: Table 8 · p. 21, §A.6 · p. 21, Table 10 · p. 26

A.14 Efficiency of Code with different number of tests

  • For GPT-3.5-turbo-0301, increasing tests from 10 to 1,000 raises NTMU from 4.75 to 10.08; increasing tests from 100 to 1,000 raises TMU from 8.84 MB*s to 340.51 MB*s.More tests cover additional edge cases but increase evaluation resource costs, so the experiments and leaderboard use 100 tests.Source: §A.14 · pp. 28–29, §A.21 · p. 33

A.15 Randomness

  • Across five runs, GPT-3.5-turbo-0301’s mean ET is 0.39 s with standard deviation 0, while its efficiency-testing overhead is 32 s.Efficiency changes slightly across local environments; the paper offers a request-based evaluation and a server for users to submit code. Open-source models have very low pass@1 across difficulty settings.Source: §A.15 · p. 29, §A.16 · p. 29, §A.22 · p. 33

A.17 Discussion on Time and Space Complexity

  • The authors use direct execution-time and memory measurements rather than complexity classes alone because identical complexity labels can conceal performance differences, and manual or predicted complexity assessments can be unreliable.Direct measurements are presented as more objective and practical for automated, large-scale efficiency evaluation.Source: §A.17 · pp. 30–31

A.12 Calculating the normalized metrics with task level

  • Dataset-level normalization lowers GPT-3.5-turbo-0301’s execution-time ratio from 3.18x to 2.92x but can mask poor performance on individual tasks.The authors caution that aggregated metrics can average poor task results against better ones and give a potentially misleading overall impression.Source: §A.12 · p. 28, §A.19 · p. 32, Table 23 · p. 33

A.23 Randomness

  • Efficiency changes slightly across local environments, so EffiBench offers a request form and an upload server to evaluate models in a common execution environment.The server runs each model’s evaluation in less than one minute.Source: §A.23 · p. 34, Table 26 · p. 34

A.24 Overhead

  • Less than 1 minute is required to test each closed-source model’s efficiency.The paper reports this overhead for the closed-source models.Source: §A.24 · p. 34, Table 30 · p. 36

A.25 Discussion on Time and Space Complexity

  • Direct execution-time and memory measurements avoid complexity classes’ inability to capture implementation-level performance and the subjectivity and error risks of manual or model-based complexity estimates.The authors chose these measurements as a more objective and practical assessment of generated code’s real-world efficiency.Source: §A.25 · pp. 34, 36

A.26 Discussion Automatically-generated Test Cases

  • Below 15% accuracy for test cases generated by four closed-source LLMs motivates EffiBench’s use of its own verified test-case generators.The authors describe modifying each problem’s generator to ensure its generated test cases are correct.Source: §A.26 · p. 37, Table 31 · p. 37

A.27 Case illustration of test case generator

  • The case illustration shows a generator creating 100 tests for lengthOfLongestSubstring by randomly generating inputs and passing them to the canonical solution for outputs.Figure 9 depicts this process.Source: §A.27 · p. 37, Figure 9 · p. 40

Checklist

  • The paper states that code, data, and reproduction instructions are released, and that EffiBench is available as a new asset.These statements appear in the reproducibility and asset checklist.Source: Checklist · p. 41
Loading 2402.02037v6…