How efficient is LLM-generated code? A rigorous & high-standard benchmark

Authors: Ruizhong Qiu, Weiliang Will Zeng, James Ezick, Christopher Lott, Hanghang Tong
Primary area: datasets and benchmarks
Keywords: Large Language Model, Code Generation, Efficiency Evaluation

Abstract:
The emergence of large language models (LLMs) has significantly pushed the frontiers of program synthesis. Advancement of LLM-based program synthesis calls for a thorough evaluation of LLM-generated code. Most evaluation frameworks focus on the (functional) correctness of generated code; efficiency, as an important measure of code quality, has been overlooked in existing evaluations. In this work, we develop ENAMEL (EfficeNcy AutoMatic EvaLuator), a rigorous and high-standard benchmark for evaluating the capability of LLMs in generating efficient code. Firstly, we propose a new efficiency metric called eff@k, which generalizes the pass@k metric from correctness to efficiency and appropriately handles right-censored execution time. Furthermore, we derive an unbiased and variance-reduced estimator of eff@k via Rao–Blackwellization; we also provide a numerically stable implementation for the new estimator. Secondly, to set a high-standard for efficiency evaluation, we employ a human expert to design best algorithms and implementations as our reference solutions of efficiency, many of which are much more efficient than existing canonical solutions in HumanEval and HumanEval+. Moreover, to ensure a rigorous evaluation, we employ a human expert to curate strong test case generators to filter out wrong code and differentiate suboptimal algorithms. An extensive study across 30 popular LLMs using our benchmark ENAMEL shows that LLMs still fall short of generating expert-level efficient code. Using two subsets of our problem set, we demonstrate that such deficiency is because current LLMs struggle in designing advanced algorithms and are barely aware of implementation optimization.

Decision: accept (poster)
Reviewer scores: 6, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729939428508

thread_type:
official_review

<thread_object>
creator: reviewer_1vcl

<content>
summary:
This paper proposes a benchmark suite, named `ENAMEL`, to evaluate the efficiency of code generated by LLMs. The authors propose a novel metric eff@k that measures the efficiency of the generated code accounting for different input sizes. A human expert provides the reference implementation for each task in the benchmark suite. The evaluation with regard to the eff@k metric demonstrates the large gap between the LLM-generated code and the reference implementation.

strengths:
1. Human expert-provided reference implementations for the benchmark are of high quality.
2. Evaluation provides insights into the efficiency of LLM-generated code.
3. Clear presentation that is easy to follow.

weaknesses:
1. The novelty of the proposed eff@k metric is not convincing.

The authors mention the insufficiencies of existing efficiency benchmarks in C1 and C2.

a) For C1, the authors mention that if the code execution exceeds the time limit, the actual efficiency is unknown. However, the authors do not demonstrate how frequently this happens in practice. If this is a rare case, then existing benchmarks are still useful. The authors should provide experimental evidence to demonstrate that existing works do give wrong efficiency measurements due to the presence of such cases.

b) For C2, the authors argue that existing works fail to capture the relationship between code efficiency and the sample size k. By looking at Eq. (5), the proposed solution of ENAMEL is to take the maximum of the efficiency value, while the existing works take the average. The authors do not justify why taking the maximum is a better choice than taking the average. Such a difference in the metric definition seems to be a minor difference.

2. Lack of evaluation on different test case generation strategies.

The code efficiency can be affected by the testing inputs. Ideally, the efficiency should be measured against the worst-case inputs, which can be hard to define in practice. A practical approximation is to take the maximum execution time over a set of testing inputs. As such, the testing input generation is crucial for the efficiency evaluation. It is not clear how strong the test case generation strategy adopted in this paper is. The authors should evaluate the robustness of the proposed eff@k metric against different test case generation strategies.

3. Lack of guidance on setting the hyperparameters for the eff@k metric.

The eff@k metric has a set of hyperparameters, such as $\alpha$ and $h$. The value of these hyperparameters directly affects the efficiency measurement. Without guidance on how to set these hyperparameters, the practical usage of the eff@k metric is limited. It would be better if automatic hyperparameter selection methods were provided; or at least, empirical studies on how the eff@k metric is affected by different hyperparameters.

4. The benchmark suite is limited only to the HumanEval dataset.

This concerns about the generalizability of ENAMEL. The HumanEval dataset contains many simple tasks that require $\mathcal{O}(1)$ time complexity. A potential concern is that the dataset after filtering out those simple tasks may not be large enough to provide a comprehensive evaluation of the efficiency of LLM-generated code.

a) The authors should provide the size and proportion of the remaining tasks after filtering out the simple tasks.

b) The authors can consider extending the benchmark suite to more competitive datasets, such as the CodeContests dataset.

questions:
1. Why is the maximum efficiency value chosen in the eff@k metric, rather than the average efficiency value?
2. Do the eff@k metric and the existing efficiency metrics give different efficiency rankings for the same LLM-generated code?
3. How sensitive is the eff@k metric to the hyperparameters?
4. What is the size of the ENAMEL benchmark suite?
5. How does the ENAMEL benchmark perform on more competitive datasets, such as the CodeContests dataset?
6. How does the eff@k metric perform on different test case generation strategies?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619831078

thread_type:
official_review

<thread_object>
creator: reviewer_2joc

<content>
summary:
The paper presents ENAMEL, a benchmark for evaluating the efficiency of LLM-generated code, a quality largely overlooked in current assessments. ENAMEL introduces a new efficiency metric, eff@k, and includes expert-designed reference solutions and rigorous test cases to set high standards. Evaluating 30 popular LLMs, the authors find that while many models generate correct code, they fall short in efficiency, particularly with advanced algorithms and optimizations, underscoring the need for further improvements in LLM code synthesis.

strengths:
1. Clear and fluent presentation. The metric is carefully designed.
2. The evaluation is convincing and indicative.

weaknesses:
1. The method is very manual. It is hard to scale.
2. The dataset is small. Humaneval was a good metric several years ago at the early stage of code generation. But now, serious evaluation needs a larger scale dataset.

Despite the above, the dataset is still reasonably valuable due to its high quality.

questions:
1. Why didn't you consider problems from online judges like codeforces? There are plenty of problems with expert-level efficient solutions as a competition-oriented platform.
2. Did you consider a more automatic way of measuring the complexity? It might not be hard to find out that multiple layers of input scale, simply considering log scales, polynomial scales, and exponential scales.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730653278240

thread_type:
official_review

<thread_object>
creator: reviewer_t6vw

<content>
summary:
The paper proposes a new benchmark for evaluating the efficiency of code generated by LLMs. The authors select 142 problems out of the 164 problems in HumanEval and HumanEval+ (they excluded trivial problems with Θ(1) time complexity). They propose a metric that they call eff@k which is the equivalent for pass@k but adapted to the problem of evaluating the performance of code. They then evaluate 30 LLMs (closed and open-source LLMs) on their benchmark using the eff@k metric. They show that state-of-the-art LLMs achieve an eff@1 score of 0.47 and an eff@100 score of 0.575. They also propose a hand-optimized version of each of the 142 problems in their benchmark to set a new standard for LLMs.

strengths:
-	Evaluating whether LLMs can generate efficient code is an important problem, especially with the increasing amount of research on the topic of code synthesis using LLMs and the wide use of LLMs for coding.
-	The authors provide a comprehensive evaluation of 30 LLMs using the proposed benchmark and more importantly, provide a hand-optimized version of each one of the codes in their benchmark which opens the door for more research on the topic.

weaknesses:
While the proposed work is important, and while the results are interesting, I don’t believe the contribution and novelty of the work are strong enough. There is clearly a degree of novelty in this paper though, and the proposed benchmark is very valuable from a practical point of view.

The problem of measuring the performance of code is well-studied in the compiler community. There are decades of work on the development of methods for automatic code optimization in compilers and methods to measure the success of such methods. Any paper about automatic code optimization. Here is one example of such work:

       “Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques”, Sid Touati.

It would be interesting to include examples of such work in the related work section and also include a detailed discussion in the paper about why a simple metric such as “the speedup” (ratio between the execution time of the reference code over the execution time of the synthesized code) is not enough for this problem and a new metric needs to be proposed.

questions:
-	Can you please include a detailed discussion of why the the speedup metric classically used by the compiler community when evaluating automatic code optimization methods is not enough for your task?
-	For more completeness, can you also include a discussion of such work in the related work section? A starting point would be:  “Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques”, Sid Touati.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730656644191

thread_type:
official_review

<thread_object>
creator: reviewer_xnv8

<content>
summary:
The paper presents a systematic benchmark for efficiency of LLM generated code. The paper presents the eff@k metric, which captures efficiency of generated code (the expected maximum efficiency score of $k$ independent code sample). The presented metric is the first that can capture the relationship between code efficiency and the sample size k. Expert solutions and expert test cases make this benchmark a compelling baseline.

strengths:
- Very nice and clear presentation 
- A clear and rigorous technical treatment of evaluation timeout (right censoring)
- Human expert solutions as an efficiency target 
- Human expert test cases covering tricky corner cases

weaknesses:
- I would appreciate a comparison with previous metrics, even the naive ones, to see whether the empirical effect of this new metric is that models/problems are given a different ranking. 
- Not evaluated with a prompt that asks for an efficient solution, I suspect that a better prompt would make this entire suite too weak for being a competitive benchmark

questions:
- I understand the theoretical importance of Rao-Blackwellization in this case, but what is the empirical effect? 

- Effibench presented an efficiency-benchmark with 1,000 coding problems, where ach problem is paired with an executable human-written canonical solution, which obtains the SOTA efficiency on the LeetCode solution leaderboard. I would not classify it as a sporadic attempt, what makes you view it as such?

- Does it make sense to also consider space complexity in your benchmarks? For example: 

Your optimized solution for #40: 
```
def has_triplet_sum_zero(l):
	n = len(l)
	if n < 3:
		return False
	for i, x in enumerate(l[: n - 2]):
		buf = set()
		for y in l[i + 1 :]:
			if y in buf:
				return True
		buf.add(-x - y)
	return False
```

Suggested solution: 
```
def has_triplet_sum_zero(l):
    l.sort()  # Sort the list first
    n = len(l)
    
    for i in range(n - 2):
        # Use two pointers to find if there's a pair with sum -l[i]
        left, right = i + 1, n - 1
        target = -l[i]
        
        while left < right:
            current = l[left] + l[right]
            if current == target:
                return True
            elif current < target:
                left += 1
            else:
                right -= 1
    
    return False
```

Uses two pointers, has the same time complexity, and reduces space complexity from $O(n)$ to $O(1)$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732357063946

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all reviewers for their valuable time and thoughtful reviews. We appreciate reviewers' recognition that efficiency evaluation is an important problem (t6vW), that the benchmark provides high-quality reference solutions (xNv8, t6vW, 1vcL) and test cases (xNv8) are useful for future research (t6vW), that the evaluation metric is rigorously designed (xNv8, 2JoC), that the evaluation is comprehensive (t6vW) and insightful (2JoC, 1vcL), and that this paper has a clear presentation (2JoC, 1vcL) and is easy to follow (2JoC, 1vcL). We also thank reviewers for their constructive comments, which have inspired us to further improve the quality of the paper and will lead to interesting future research directions. 

Regarding why we craft this benchmark by human expert and regarding the size of our benchmark, we provide our response as follows.

Firstly, we believe that crafting the benchmark by **human expert is necessary** to develop a **high-standard and rigorous** benchmark. For example, as shown in Table 2, compared with our expert solutions, HumanEval canonical solutions achieve only eff@1=0.455, and HumanEvalPlus canonical solutions achieve only eff@1=0.513. This shows that their canonical solutions are **far less efficient than our expert-written reference solutions**. 

  - (i) We did not use problems/solutions from **online judges** (like LeetCode or Codeforces) because their **public solutions are already in LLMs' pretraining corpuses**. For example, DeepMind's AlphaCode [1] has been trained on many online judges including Codeforces, CodeChef, HackerEarth, AtCoder, and Aizu. If we evaluate LLMs on these public online judges, then the evaluation results may fail to reflect the LLMs’ true capabilities due to test set leakage / memorization.
  - (ii) We did not **crowd-source** the benchmark because otherwise it would be **hard to guarantee the quality** of the benchmark. For example, MBPP [2] is a popular crowd-sourced benchmark, but it is known to be easier than HumanEval [3]. 
  - (iii) We did not use **LLM-generate reference solutions** because LLM-generated code are still far from expert-level efficiency, as demonstrated in our evaluation. 

Secondly, despite the size of the benchmark, **our 142 problems has already revealed the limited capability** of all the 30 LLMs in generating efficient code. In particular, our benchmark shows that even the strongest LLM (GPT-4 Turbo) is still far from generating expert-level efficient code (eff@1 below 0.5). We hope our findings and benchmark will help LLM developers to realize this critical issue and further inspire them to develop stronger LLM code generators. The effectiveness of our benchmark is because **our human expert has carefully verified the comprehensiveness** of the problemset:

  - (i) As shown in Figure 2, our benchmark problems **have diverse difficulties**. For example, 75 seemingly easy problems require non-trivial implementation optimization, and 20 hard problems require advanced algorithms.
  - (ii) As discussed in Section 3.2, our problemset **covers a wide range of algorithmic knowledge** (including data structures, dynamic programming, and automata) and **a wide range of mathematical knowledge** (including linear algebra, combinatorics, and number theory).

That said, we still agree with the reviewers that addressing scalablity of benchmark development is an important future direction. A possible solution is to **collaborate with private programming competitions** whose solutions are not publicly available. Nevertheless, we believe that this will be an issue *only after* LLMs can generate efficient code on our benchmark but might not for now. We have added a discussion to Appendix D. 

For other questions, we provide our response below and have revised our paper accordingly. We warmly invite the reviewers for further discussion. 

-------------

References:

- [1] Li et al. Competition-level code generation with AlphaCode. Science. 378(6624):1092-
1097, 2022.
- [2] Austin et al. Program synthesis with large language models. Google Research, 2021.
- [3] Rozière et al. Code Llama: Open foundation models for code. Meta AI, 2023.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a new metric (and Monte Carlo estimator) for the expected performance of a program sampled from a language model. They use this new theoretical advance to then do a very broad evaluation of language models, and a very narrow evaluation of programming problems (the primary weakness). But this weakness is mostly because they need to hand write efficient solutions to various problems in order to normalize performance, so it is understandable. I think that both the problem as well as the theoretical result are important for the community, hence support acceptance.