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

## Abstract

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 𝑘 k italic_k , which generalizes the pass@ k 𝑘 k italic_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 𝑘 k italic_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.
Our benchmark is publicly available at https://github.com/q-rz/enamel .

## 1 Introduction

The emergence of large language models (LLMs; Brown et al., ; Touvron et al., ) has driven the frontiers of program synthesis (Simon, ; Gulwani et al., ) with the help of large open codebases for pretraining. A number of code LLMs have been released (Chen et al., ; Li et al., ; Nijkamp et al., ; Roziere et al., ). They autoregressively generate code from a prompt that describes the requirement (e.g., in the form of a function signature and a docstring). Advancement of LLM-based program synthesis in turn calls for a thorough evaluation of LLM-generated code. Most of the existing evaluation frameworks (Chen et al., ; Austin et al., ; Hendrycks et al., ; Cassano et al., ; Lai et al., ; Liu et al., ) focus on the *(functional) correctness* of generated code. Each framework has a collection of programming problems along with test cases, which are used to evaluate the correctness of generated codes.

Apart from correctness, however, *efficiency* is another important measure of code quality and has been overlooked in existing evaluations. Code efficiency is crucial in real-world applications for boosting system throughput, improving algorithm latency, and reducing energy consumption. Nonetheless, not until very recently have some sporadic attempts (Niu et al., ; Huang et al., ; Du et al., ) been made to evaluate the efficiency of LLM-generated code, and a number of fundamental challenges remain uncharted and open:

- (C1)
Right-censored execution time. When code execution is early terminated due to time limit, its actual execution time is unknown; this is *right censoring* in statistics (Bang and Tsiatis, ). For instance, if the generated code contains an infinite loop, the right-censored execution time will be clipped to the time limit while the actual execution time should be infinity. Existing works (Niu et al., ; Huang et al., ) use the execution time without coping with right censoring and thus *overestimate* the efficiency.
- (C2)
Efficiency v.s. sample size. Different code samples generated from LLMs for the same problem could have different execution times. We generalize the pass@$k$ metric (Chen et al., ) to characterize the efficiency given sample sizes $k$. Existing work either uses only one code sample (Niu et al., ) or averages the efficiency scores of code samples (Huang et al., ; Du et al., ); therefore, they fall short in capturing the relationship between code efficiency and the sample size $k$.
- (C3)
Algorithm design & implementation optimization. A good reference of efficiency should be the most efficient code, which often needs advanced algorithms and implementation optimization that can be highly non-trivial even for human programmers. Prior works either use existing canonical solutions provided in the dataset as the reference (Niu et al., ; Huang et al., ) or use solutions collected online (Du et al., ), but our evaluation reveals that many of the non-expert solutions themselves are inefficient and thus are not suitable references for efficiency.
- (C4)
Correctness filter. Wrong code can be efficient, but such code is useless. For example, an efficient yet wrong algorithm for deciding the primality of an integer is the Fermat primality test, which is known to have nontrivial counterexamples (Carmichael, ). Thus, we need to use strong test cases to filter out wrong code and evaluate efficiency only with correct code. Niu et al. () rely on existing test cases provided by the dataset, but Liu et al. () have shown that those tests are not strong enough to fully detect wrong code.
- (C5)
Worst-case efficiency. Some suboptimal algorithms can appear efficient on random inputs despite their inefficiency on strong inputs. For example, if we search for a length-$m$ substring in a length-$n$ string, a brute-force algorithm takes only $\Theta(n+m)$ time on random strings but requires $\Theta(nm)$ time in the worst case. Huang et al. () and Du et al. () use GPT to produce test case generators, but we found that their test cases are mostly random and thus cannot differentiate such suboptimal algorithms.

Figure: Figure 1: Illustration of our ENAMEL framework with HumanEval problem #55 (computing the $n$-th Fibonacci number). Our level-based evaluation clearly differentiates the three algorithms: (i) a naïve algorithm that needs $2^{\Theta(n)}$ recursions, (ii) a dynamic programming algorithm that needs $\Theta(n)$ iterations, and (iii) an efficient doubling algorithm that needs only $\Theta(\log n)$ iterations.
Refer to caption: x1.png

To collectively address the aforementioned challenges, we develop ENAMEL (EfficieNcy AutoMatic EvaLuator), a high-quality benchmark to rigorously evaluate the capability of LLMs in generating efficient code. We carefully select 142 problems out of the 164 problems in HumanEval (Chen et al., ) and HumanEval+ (Liu et al., ), excluding trivial problems with $\Theta(1)$ time complexity. With a wide spectrum of easy to hard problems, we are able to comprehensively evaluate how capable the LLM is to generate efficient code for various problems. Our main contributions are as follows:

- •
Efficiency metric & its unbiased, variance-reduced estimator. We propose a new efficiency metric called $\textnormal{eff@}k$, which generalizes the pass@$k$ metric from correctness to efficiency. Our $\textnormal{eff@}k$ metric properly handles right-censored execution time (C1) and precisely characterizes the efficiency under different sample sizes $k$ (C2). Furthermore, we derive an unbiased, variance-reduced estimator of our $\textnormal{eff@}k$ via Rao–Blackwellization, and provide a numerically stable implementation of our estimator.
- •
Efficient reference solutions. 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 (C3). Many of our reference solutions are much more efficient than the canonical solutions in HumanEval and HumanEval+. For example, the canonical solution of computing the $n$-th Fibonacci number in HumanEval+ needs $\Theta(n)$ iterations while our reference solution needs only $\Theta(\log n)$ iterations.
- •
Strong test case generators. To ensure a rigorous evaluation, we employ a human expert to curate strong test case generators that cover both corner cases to filter out wrong code (C4) and worst cases to differentiate suboptimal algorithms (C5). Under our generated strong test cases, 11 canonical solutions in HumanEval and 4 in HumanEval+ are found wrong, and 34 in HumanEval and 27 in HumanEval+ exceed the time limit.
- •
Rigorous & high-standard benchmark. We open-source ENAMEL, a rigorous and high-standard benchmark for evaluating the capability of LLMs in generating efficient code.
An extensive study across 30 popular LLMs using our benchmark ENAMEL shows that LLMs still fall short of generating expert-level efficient code. Benchmarked with our expert-written reference solutions, the strongest commercial LLM GPT-4 has low eff@1=0.454 despite its high pass@1=0.831. Furthermore, using two subsets of our problem set, we show that their deficiency is because LLMs struggle in designing advanced algorithms and are barely aware of implementation optimization.

## 2 Evaluation Framework

Here, we describe our evaluation framework (§2.1), our new efficiency score of a code sample (§2.2), and our new efficiency metric $\textnormal{eff@}k$ of an LLM with an unbiased, variance-reduced estimator (§2.3). The main notations used in this paper are summarized in Table 5.

### 2.1 Level-Based Evaluation

To achieve a fine-grained evaluation of efficiency, we aim not only to let the most efficient code pass but also to give a continuous score for less efficient code generated by LLMs. A naïve idea is to time each code under large-scale inputs. However, because we have to set a time limit per test case to prevent unacceptably long execution time, if we used only large-scale inputs to evaluate every code, most of the less efficient code would time out, making it impossible to distinguish different efficiencies. For example, for the problem and code samples in Fig. 1, if we used large-scale inputs that allow only the code with $\Theta(\log n)$ iterations to pass, then we would not be able to give different scores for the code with $2^{\Theta(n)}$ recursions and the code with $\Theta(n)$ iterations.

To address this issue, we propose to use multiple levels $1,\dots,L$ of test cases where each level has a different input scale (i.e., the size of the input). For each problem $i$, all levels share the same time limit $T_{i}$ while the input scale increases with the level $l$ (i.e., the $L$-th level has the largest input scale). Input scales are carefully designed by a human expert so that algorithms with different efficiencies can pass different numbers of levels. Besides levels $1,\dots,L$, we use an additional level 0 0 to filter out wrong code using small strong inputs. For each problem $i$, each level $l=0,1,\dots,L$ has $M_{l}$ test cases. If the output of the code does not match the expected output in any test case or does not pass level 0 0, we will not count it into the pass@$k$ metric. If the code passes level 0 0 but exceeds the time limit in some level $l\geq 1$, we will still count it into the pass@$k$ metric but will skip the remaining levels (i.e., we assume that it will also exceed the time limit for the remaining levels because the input scale increases with the level $l$). Finally, we compute its efficiency score according to §2.2.

Example. Fig. 1 illustrates our evaluation framework via HumanEval problem #55 (computing the $n$-th Fibonacci number). Level 0 0 has $n\leq 10$ so that the naïve recursive algorithm (in $2^{\Theta(n)}$ recursions) can pass; level $1$ has $n\leq 30$ so that the dynamic programming algorithm (in $\Theta(n)$ iterations) can pass; level $2$ has $n\leq 9000$ so that the matrix exponentiation algorithm (in $\Theta(\log n)$ iterations by repeated squaring) can pass; level $3$ has $n\leq 10000$ so that the doubling algorithm (still in $\Theta(\log n)$ iterations yet with a smaller hidden constant in $\Theta$) can pass. These carefully designed levels enable us to differentiate code samples that have different efficiencies.

### 2.2 Efficiency Score of a Code Sample

A unique challenge in efficiency evaluation is *right-censored* (Bang and Tsiatis, ) execution time: when an execution is killed due to exceeding the time limit $T$, we cannot know its actual execution time $t$ and only know that $t\geq T$. For instance, if the generated code contains an infinite loop, the right-censored execution time will be clipped to the time limit while the actual execution time should be infinity. Existing evaluations (Niu et al., ; Huang et al., ) use the execution time without coping with right censoring and thus overestimate the efficiency.

To appropriately handle right-censored execution time, we aim to propose an efficiency score whose dependence on the execution time vanishes whenever the execution time exceeds the time limit. Thus, for the $j$-th code sample $c_{i,j}$ of problem $i$ and for each level $l$, if the code $c_{i,j}$ is correct, we define the efficiency score $f_{i,j,l}$ by

$$ $\displaystyle f_{i,j,l}:=\frac{(T_{i}-\max\{t_{i,j,l,m}\}_{m=1}^{M_{l}})^{+}}{ T_{i}-\max\{t^{*}_{i,l,m}\}_{m=1}^{M_{l}}},$ (1) $$

where $t_{i,j,l,m}$ is the execution time of code $c_{i,j}$ for the $m$-th test case in level $l$; $t^{*}_{i,l,m}$ is the execution time of our reference solution for the $m$-th test case in level $l$; $T_{i}$ is the time limit of problem $i$; and $(\cdot)^{+}:=\max\{\cdot,0\}$. Here, we use $\max\{t_{i,j,l,m}\}_{m=1}^{M_{l}}$ in $e_{i,j}$ to characterize the worst-case efficiency since our expert-written input generators produce various types of test cases that cover the worst cases of various algorithms. Our efficiency score $f_{i,j,l}$ is not affected by right-censored execution time because whenever $\max\{t_{i,j,l,m}\}_{m=1}^{M_{l}}\geq T_{i}$, our score $f_{i,j,l}$ will have the same value zero regardless of the exact value of $\max\{t_{i,j,l,m}\}_{m=1}^{M_{l}}$. Also, we normalize our efficiency score $e_{i,j}$ using our reference solution so that the scale of the score does not differ across problems. For the time limit, we use $T_{i}:=\alpha\max\{t^{*}_{i,l,m}\}_{l,m}$, where $\alpha>1$ is a hyperparameter. Besides that, to reduce the variance of the execution time caused by hardware performance fluctuations, we repeat each test case $R$ times and estimate the execution time $t_{i,j,l,m}$ via the Hodges–Lehmann estimator (Hodges Jr. and Lehmann, ) because of its robustness against outliers as well as its high statistical efficiency.

Finally, since each level has a distinct hardness, we define the efficiency score $e_{i,j}$ of a code sample $c_{i,j}$ of problem $i$ by a weighted average over levels $1,\dots,L$:

$$ $\displaystyle e_{i,j}:=\begin{cases}\frac{\sum_{l=1}^{L}h_{l}\cdot f_{i,j,l}}{ \sum_{l=1}^{L}h_{l}},&\text{if code }c_{i,j}\text{ is correct};\\ 0,&\text{otherwise}.\end{cases}$ (2) $$

where hyperparameters $h_{l}>0$ represent the hardness of each level $l$.

### 2.3 Efficiency Metric for an LLM

The pass@$k$ metric (Chen et al., ) is the standard metric in correctness evaluation, which means the probability that at least one among $k$ generated code samples is correct. Meanwhile, existing efficiency evaluations (Niu et al., ; Huang et al., ) use the average execution time as the metric and thus fall short of describing the relationship between code efficiency and sample size $k$.

To overcome this limitation and evaluate the capability of an LLM in generating efficient code w.r.t. the sample size $k$, we aim to generalize the pass@$k$ metric from correctness to our continuous efficiency score. Let $z_{i}$ denote the prompt of problem $i$; let $c_{i,j}\sim\text{LLM}(z_{i})$ denote the generated code samples for problem $i$; let $g_{i,j}\in\{0,1\}$ denote the correctness of code $c_{i,j}$; and let $\text{pass}_{i}\text{@}k$ denote the pass@$k$ metric w.r.t problem $i$. The original definition of pass@$k$ relies on the Boolean nature of code correctness and thus cannot be directly generalized to our continuous efficiency score. To address this, we equivalently express $\text{pass}_{i}\text{@}k$ as an expectation:

$$ $\displaystyle\text{pass}_{i}\text{@}k={\operatorname*{\mathbb{P}}_{c_{i,1}, \dots,c_{i,k}\sim\text{LLM}(z_{i})}}\{\exists 1\leq j\leq k:g_{i,j}=1\}$ $\displaystyle={\operatorname*{\mathbb{P}}_{c_{i,1},\dots,c_{i,k}\sim\text{LLM} (z_{i})}}\Big{\{}{\max_{j=1}^{k}g_{i,j}}=1\Big{\}}$ (3) $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}g_{i,j}}\Big{]}.$ (4) $$

This equivalent formula in Eq. (4) no longer relies on the Boolean nature of code correctness and naturally extends to our continuous efficiency score. Hence, we define our efficiency metric $\textnormal{eff}_{i}\textnormal{@}k$ by the expected maximum efficiency score of $k$ independent code samples:

$$ $\displaystyle\textnormal{eff}_{i}\textnormal{@}k$ $\displaystyle:={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]},$ (5) $$

where $e_{i,j}$ denotes the efficiency score of code $c_{i,j}$ defined in §2.2. Our metric $\textnormal{eff}_{i}\textnormal{@}k$ precisely characterizes the relation between code efficiency and sample size $k$ via the maximum over $k$ code samples while the metric in previous works (Niu et al., ; Huang et al., ) is simply an average over code samples and cannot describe its relation with sample size $k$.

However, estimating $\textnormal{eff}_{i}\textnormal{@}k$ naïvely by generating $k$ code samples and calculating their maximum $e_{i,j}$ can have high variance (Chen et al., ). To reduce the variance of $\textnormal{eff}_{i}\textnormal{@}k$ estimation, we employ two advanced variance reduction techniques: (i) bootstrap (Efron, ) and (ii) Rao–Blackwellization (Casella and Robert, ). Specifically, for $n\geq k$ i.i.d. code samples $c_{i,1},\dots,c_{i,n}\sim\text{LLM}(z_{i})$, the bootstrap estimator is the average of $\max_{j\in J}e_{i,j}$ over multiple random subsets $J\subseteq\{1,\dots,n\}$ with $|J|=k$,
and we obtain our final estimator $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$ by Rao–Blackwellizing the boostrap estimator (i.e., taking expectation over the random subset $J$):

$$ $\displaystyle\widehat{\textnormal{eff}}_{i}\textnormal{@}k:={\operatorname*{ \mathbb{E}}_{\begin{subarray}{c}J\subseteq\{1,\dots,n\}\\ |J|=k\end{subarray}}}\Big{[}{\max_{j\in J}e_{i,j}}\Big{]}=\sum_{r=k}^{n}\frac{ \binom{r-1}{k-1}}{\binom{n}{k}}e_{i,(r)}.$ (6) $$

where $e_{i,(r)}$ denotes the $r$-th smallest score among $e_{i,1},\dots,e_{i,n}$, and $\binom{n}{k}$ denotes the binomial coefficient.
Furthermore, we show in Theorem 1 that our Rao–Blackwellized bootstrap estimator $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$ is unbiased and does reduce variance.

###### Theorem 1 .

Suppose that problem $i$ has time limit $T_{i}<\infty$ and reference execution times $t^{*}_{i,l,m}<T_{i}$. Under the randomness of code generation and execution, for $n\geq k$, we have:

- •
Unbiasedness:
$\displaystyle{\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim\textnormal
{LLM}(z_{i})}}\bigg{[}{\sum_{r=k}^{n}\frac{\binom{r-1}{k-1}}{\binom{n}{k}}e_{i
,(r)}}\bigg{]}={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k}\sim
\textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]};$
(7)
- •
Variance reduction:
$\displaystyle{\operatorname*{\operatorname{Var}}_{c_{i,1},\dots,c_{i,n}\sim
\textnormal{LLM}(z_{i})}}\bigg{[}{\sum_{r=k}^{n}\frac{\binom{r-1}{k-1}}{\binom
{n}{k}}e_{i,(r)}}\bigg{]}\leq\frac{k}{n}\cdot{\operatorname*{\operatorname{Var
}}_{c_{i,1},\dots,c_{i,k}\sim\textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_
{i,j}}\Big{]}.$
(8)

Proof is in §A. Due to unbiasedness, we will use $\textnormal{eff}_{i}\textnormal{@}k$ and $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$ interchangeably from now on.

Table: Algorithm 1 Numerically stable $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$

As a remark, naïvely computing the coefficients $\binom{r-1}{k-1}/\binom{n}{k}$ in $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$ can result in numerical instability. Instead, we propose a numerically stable implementation of $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$, presented in Algorithm 1.

Finally, we define our efficiency metric $\textnormal{eff@}k$ by averaging $\textnormal{eff}_{i}\textnormal{@}k$ over all problems $i$.

###### Theorem 1 .

## 3 Benchmark Development

In this section, we detail our methodology for selecting our problemset (§3.1), implementing our efficient reference solutions (§3.2), and curating our strong test case generators (§3.3).

### 3.1 Problem Selection

To achieve a comprehensive evaluation of efficiency, we aim to create a problemset that contains high-quality problems with a broad range of difficulties. Thus, following HumanEval+ (Liu et al., ), we re-use the problems from the HumanEval dataset (Chen et al., ) due to their high quality and diverse difficulties. We remark that even seemingly easy problems can become hard if the input scale increases. Although most HumanEval problems *seem* easy, we find that quite a number of them become hard and require advanced algorithms under large-scale inputs. For instance, although the common algorithm for problem #55 (computing the $n$-th Fibonacci number) is dynamic programming with $\Theta(n)$ iterations, a large $n$ requires an advanced doubling algorithm that needs only $\Theta(\log n)$ iterations based on a non-trivial identity of Fibonacci numbers.

Meanwhile, we find that some problems in HumanEval with $\Theta(1)$ time complexity are unsuitable for efficiency evaluation due to the following two reasons. First, their execution time is too short and is thus mainly affected by hardware performance fluctuations, making their execution time uninformative about the true efficiency of the code. Second, since all LLMs do well in these trivial problems, evaluation with these problems hardly differentiates the capabilities of different LLMs. Hence, we exclude these trivial problems and use the remaining 142 problems as our problemset.

Our problemset comprises a wide spectrum of easy to hard problems, thus enabling a comprehensive evaluation of how capable the LLM is in generating efficient code under various difficulties. Table 1 exhibits a sample of hard problems in our problemset.

### 3.2 Efficient Reference Solutions

An ideal reference of efficiency should be the most efficient code, which often needs advanced algorithms and implementation optimization that can be highly non-trivial even for human programmers. Thus, we employ a human expert to write reference solutions. For each problem, our expert first designs the best algorithm and next optimizes the implementation of the algorithm. Our expert-written reference solutions enable us to evaluate how LLMs compare with human experts in writing efficient code. We introduce our algorithm design stage and implementation optimization stage below.

**Table 1: A sample of hard problems in our problemset. Our expert-written reference solutions are much more efficient than HumanEval+ canonical solutions. (See Appendix E for code.)**
| ID | Problem Description | HumanEval+ Solution | Our Expert Solution |
| --- | --- | --- | --- |
| #10 | Find the shortest palindrome that begins with a given string $S$ | $\mathrm{O}(|S|^{2})$: Enumerate suffixes and check palindromicity | $\Theta(|S|)$: Use Knuth–Morris–Pratt w.r.t. reversed $S$ plus $S$ |
| #36 | Count digit 7’s in positive integers $<n$ that are divisible by 11 or 13 | $\Theta(n\log n)$: Enumerate integers $<n$ and count the digits | $\Theta(\log n)$: Design a dynamic programming over digits |
| #40 | Check if a list $l$ has three distinct elements that sum to 0 | $\mathrm{O}(|l|^{3})$: Enumerate triples in $l$ and check their sums | $\mathrm{O}(|l|^{2})$: Use a hash set and enumerate pairs in $l$ |
| #109 | Check if a list $a$ can be made non-decreasing using only rotations | $\mathrm{O}(|a|^{2})$: Enumerate the rotations of $a$ and check | $\mathrm{O}(|a|)$: Check if the list $a$ has at most one inversion |
| #154 | Check if any rotation of a string $b$ is a substring of a string $a$ | $\mathrm{O}(|b|^{2}|a|)$: Enumerate rotations and run string matching | $\mathrm{O}(|a|+|b|)$: Run the suffix automaton of $a$ w.r.t. $b+b$ |

Algorithm design. The goal of algorithm design is to optimize time complexity. It may involve advanced algorithms and non-trivial reformulations, which can be challenging even for human programmers. Thanks to the strong expertise of our human expert, we are able to design the best algorithm as our reference solutions for all problems. We remark that we try our best to avoid randomized algorithms whenever an efficient deterministic algorithm exists. Our reference solutions involve many advanced algorithms (such as automata, data structures, and dynamic programming) and a wide range of mathematical knowledge (including number theory, combinatorics, and linear algebra). See Table 1 for a sample of hard problems and our reference solutions.

Implementation optimization. Even a single algorithm can have multiple functionally equivalent implementations with different efficiencies. Implementation optimization is to improve code efficiency by exercising best practices and exploiting programming language features, some of which are barely known to non-expert programmers. For example, for problem #98 (counting uppercase vowels at even indices), an efficient Python implementation needs a clever use of the builtin function str.translate rather than straightforward counting. To this end, we employ a human expert to find the most efficient implementations as our reference solutions. For each problem, our human expert writes and executes multiple implementations and keeps the most efficient one. Many of our reference solutions are much more efficient than those in HumanEval and HumanEval+ (see Table 2).

### 3.3 Strong Test Case Generators

Previous works either rely on existing HumanEval test cases (Niu et al., ), which are known to be not strong enough (Liu et al., ), or use ChatGPT-generated test case generators (Huang et al., ), which are mostly random and thus may not differentiate suboptimal algorithms. To address these limitations, we employ a human expert to curate strong test case generators that cover both corner cases to filter out wrong code and worst cases to differentiate suboptimal algorithms. For each problem, our human expert first creates an initial version of the test case generator via ChatGPT and next decides if the problem has corner cases and/or non-random worst cases. If so, then our human expert will strengthen the test case generator by adding such corner cases and/or worst cases. Some corner cases can be non-trivial for non-experts: for example, for problem #31 (deciding if a number is prime), the Fermat primality test is an efficient yet wrong algorithm with only a few non-trivial counterexamples (Carmichael, ). As a remark, we only use absolutely valid corner cases and try our best to avoid those whose validity is unclear due to the ambiguity in problem description.

Our expert-written test case generators set a strict and high standard for both correctness and efficiency. For example, 11 canonical solutions in HumanEval and 4 in HumanEval+ are found wrong, and 34 in HumanEval and 27 in HumanEval+ exceed the time limit (see Table 2 for a comparison).

**Table 2: Comparison with existing benchmarks.**
| Name | eff@1 | pass@1 |
| --- | --- | --- |
| HumanEval | 0.455 | 0.908 |
| HumanEval+ | 0.513 | 0.972 |
| ENAMEL (ours) | 1.000 | 1.000 |

**Table 3: Evaluation results under our benchmark. (Greedy: selecting the next token with the highest logit. Sampling: selecting the next token with probability proportional to the softmax of logits.) Existing LLMs fall short of generating expert-level efficient code.**
| Model | Greedy | Sampling |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| eff@1 | pass@1 | eff@1 | pass@1 | eff@10 | pass@10 | eff@100 | pass@100 |  |
| GPT-4 Turbo | 0.470 | 0.796 | — | — | — | — | — | — |
| GPT-4 | 0.454 | 0.831 | — | — | — | — | — | — |
| Llama 3 70B Instruct | 0.421 | 0.746 | 0.438 | 0.747 | 0.526 | 0.836 | 0.575 | 0.880 |
| Llama 3 8B Instruct | 0.344 | 0.592 | 0.345 | 0.564 | 0.500 | 0.770 | 0.595 | 0.874 |
| Mixtral 8x22B Instruct | 0.408 | 0.746 | 0.407 | 0.721 | 0.575 | 0.870 | 0.704 | 0.923 |
| Mixtral 8x7B Instruct | 0.266 | 0.444 | 0.279 | 0.456 | 0.436 | 0.689 | 0.542 | 0.810 |
| Claude 3 Opus | 0.401 | 0.789 | — | — | — | — | — | — |
| Claude 3 Sonnet | 0.345 | 0.662 | 0.365 | 0.677 | 0.498 | 0.814 | 0.594 | 0.887 |
| Claude 3 Haiku | 0.386 | 0.739 | 0.382 | 0.730 | 0.478 | 0.831 | 0.529 | 0.861 |
| Phind Code Llama V2 | 0.394 | 0.683 | 0.372 | 0.638 | 0.584 | 0.862 | 0.723 | 0.935 |
| ChatGPT | 0.364 | 0.683 | 0.374 | 0.673 | 0.557 | 0.847 | 0.690 | 0.937 |
| Code Llama 70B Python | 0.264 | 0.500 | 0.082 | 0.177 | 0.326 | 0.610 | 0.614 | 0.908 |
| Code Llama 34B Python | 0.268 | 0.458 | 0.226 | 0.405 | 0.511 | 0.786 | 0.711 | 0.934 |
| Code Llama 13B Python | 0.216 | 0.408 | 0.204 | 0.372 | 0.487 | 0.732 | 0.714 | 0.899 |
| Code Llama 7B Python | 0.247 | 0.373 | 0.180 | 0.320 | 0.432 | 0.663 | 0.643 | 0.837 |
| StarCoder | 0.195 | 0.352 | 0.134 | 0.236 | 0.355 | 0.557 | 0.542 | 0.787 |
| CodeGen 16B | 0.169 | 0.310 | 0.122 | 0.219 | 0.326 | 0.512 | 0.536 | 0.761 |
| CodeGen 6B | 0.193 | 0.296 | 0.111 | 0.188 | 0.298 | 0.455 | 0.491 | 0.694 |
| CodeGen 2B | 0.153 | 0.254 | 0.098 | 0.168 | 0.264 | 0.389 | 0.421 | 0.602 |
| CodeT5+ 16B | 0.160 | 0.317 | 0.130 | 0.250 | 0.343 | 0.551 | 0.551 | 0.785 |
| Mistral 7B | 0.152 | 0.275 | 0.116 | 0.222 | 0.335 | 0.541 | 0.557 | 0.791 |
| Vicuna 13B | 0.123 | 0.176 | 0.080 | 0.125 | 0.188 | 0.310 | 0.319 | 0.537 |
| Vicuna 7B | 0.061 | 0.099 | 0.054 | 0.081 | 0.149 | 0.231 | 0.283 | 0.423 |
| SantaCoder | 0.100 | 0.141 | 0.088 | 0.126 | 0.204 | 0.298 | 0.349 | 0.470 |
| Incoder 6B | 0.091 | 0.127 | 0.054 | 0.078 | 0.164 | 0.242 | 0.319 | 0.439 |
| Incoder 1B | 0.066 | 0.092 | 0.031 | 0.043 | 0.100 | 0.139 | 0.191 | 0.241 |
| GPT-J | 0.083 | 0.106 | 0.039 | 0.058 | 0.119 | 0.166 | 0.221 | 0.331 |
| GPT-Neo 2B | 0.043 | 0.056 | 0.019 | 0.027 | 0.069 | 0.096 | 0.127 | 0.181 |
| PolyCoder | 0.037 | 0.049 | 0.021 | 0.029 | 0.067 | 0.084 | 0.121 | 0.155 |
| StableLM 7B | 0.020 | 0.021 | 0.007 | 0.010 | 0.039 | 0.048 | 0.097 | 0.123 |

**Table 4: Evaluation on two subsets of problems. LLMs struggle in designing advanced algorithms and are largely unaware of implementation optimization. (See Appendix B.2 for the complete table.)**
| Model | Algorithm Design Subset | Implementation Optimization Subset |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| eff@1 | pass@1 | eff@10 | pass@10 | eff@100 | pass@100 | eff@1 | pass@1 | eff@10 | pass@10 | eff@100 | pass@100 |  |
| Llama 3 70B Instruct | 0.246 | 0.660 | 0.306 | 0.749 | 0.359 | 0.750 | 0.404 | 0.791 | 0.497 | 0.869 | 0.551 | 0.920 |
| Llama 3 8B Instruct | 0.201 | 0.518 | 0.303 | 0.724 | 0.367 | 0.849 | 0.313 | 0.582 | 0.468 | 0.806 | 0.571 | 0.906 |
| Mixtral 8x22B Instruct | 0.225 | 0.635 | 0.363 | 0.837 | 0.470 | 0.900 | 0.376 | 0.783 | 0.556 | 0.914 | 0.686 | 0.947 |
| Mixtral 8x7B Instruct | 0.124 | 0.391 | 0.244 | 0.681 | 0.344 | 0.850 | 0.248 | 0.473 | 0.411 | 0.699 | 0.515 | 0.827 |
| Claude 3 Sonnet | 0.184 | 0.577 | 0.328 | 0.804 | 0.450 | 0.950 | 0.358 | 0.723 | 0.475 | 0.846 | 0.548 | 0.893 |
| Claude 3 Haiku | 0.149 | 0.692 | 0.208 | 0.752 | 0.266 | 0.775 | 0.360 | 0.772 | 0.465 | 0.889 | 0.513 | 0.923 |
| Phind Code Llama V2 | 0.185 | 0.554 | 0.353 | 0.789 | 0.401 | 0.849 | 0.351 | 0.712 | 0.567 | 0.901 | 0.732 | 0.968 |
| ChatGPT | 0.120 | 0.488 | 0.304 | 0.799 | 0.483 | 0.950 | 0.337 | 0.715 | 0.508 | 0.864 | 0.633 | 0.949 |
| Code Llama 70B Python | 0.018 | 0.100 | 0.129 | 0.519 | 0.402 | 0.950 | 0.076 | 0.181 | 0.294 | 0.627 | 0.589 | 0.920 |
| Code Llama 34B Python | 0.071 | 0.293 | 0.271 | 0.713 | 0.425 | 0.881 | 0.197 | 0.415 | 0.473 | 0.804 | 0.687 | 0.949 |
| Code Llama 13B Python | 0.058 | 0.212 | 0.276 | 0.665 | 0.478 | 0.844 | 0.176 | 0.405 | 0.476 | 0.784 | 0.715 | 0.928 |
| Code Llama 7B Python | 0.068 | 0.202 | 0.231 | 0.589 | 0.393 | 0.761 | 0.165 | 0.349 | 0.417 | 0.703 | 0.620 | 0.863 |

## 4 Evaluation

We comprehensively evaluate 30 popular LLMs with our ENAMEL benchmark. Due to the space limit, see Appendix B.1 for experimental setting.

### 4.1 Main Results & Analysis

Table 3 shows $\textnormal{pass@}k$ and $\textnormal{eff@}k$ of 30 LLMs under our benchmark. Overall, our results suggest that LLMs still fall short of generating expert-level efficient code. Benchmarked with our expert-written reference solutions, even the strongest commercial LLM GPT-4 cannot achieve eff@1>0.5, and most LLMs cannot even reach eff@1>0.3.
We also observe that $\textnormal{eff@}k$ is *consistently* much lower than $\textnormal{pass@}k$ across all LLMs, model sizes, and sample sizes $k$. This stems from the fact that existing research has been primarily focusing on code correctness while overlooking code efficiency, partially due to the lack of a rigorous evaluation framework for code efficiency. Surprisingly, LLMs that are good at generating correct code are not always equally good at generating efficient code. For instance, GPT-4 Turbo has higher eff@1 than GPT-4 although GPT-4 has higher pass@1 than GPT-4 Turbo. A possible reason is that naïve algorithms are easier to be generated correctly but are less efficient than advanced algorithms.
Besides that, we see that the performance gap between open-source and commercial models are closing in terms of generating efficient code. For example, Phind Code Llama V2 achieves eff@100=0.723, which is even higher than eff@100=0.690 of ChatGPT.

### 4.2 Analysis on Algorithm Design & Implementation Optimization

For a more thorough analysis, we further evaluate LLMs on two subsets of our dataset to investigate capabilities in algorithm design and implementation optimization, respectively.

Algorithm design. We use a subset consisting of 20 hard problems to evaluate capability in algorithm design. For these problems, the optimal algorithm can have significantly lower time complexity than suboptimal algorithms (see Table 1 for a sample of these problems). Table 4 shows that even when generating 100 samples per problem, the generated code still has low efficiency. For instance, ChatGPT has eff@100=0.483 on this subset, still below 0.5. This suggests that existing LLMs struggle in designing advanced algorithms.

Implementation optimization. We use a subset consisting of 75 problems to evaluate capability in implementation optimization. For these problems, the optimized implementation can have much higher efficiency than naïve implementations. Table 4 shows that the generated code has low efficiency when the sample size is small although the efficiency improves a lot as the sample size increases. For example, Phind Code Llama V2 has good eff@100=0.732 but low eff@1=0.351 over this subset. This suggests that existing LLMs are barely aware of implementation optimization, and the improvement is mainly because random sampling generates multiple equivalent implementations.

Figure: Figure 2: Distribution of problem difficulties (best viewed in color). High passi@1 but low effi@1 means problem $i$ has a seemingly easy task but a non-trivial efficient algorithm / implementation.
Refer to caption: x2.png

### 4.3 Distribution of Problem Difficulties

To investigate the difficulty distribution of our problems, we plot their passi@1 and effi@1 (averaged over LLMs under greedy generation) in Fig. 2, where passi@1 represents the difficulty of straightforward implementation, and effi@1 represents the difficulty of efficient implementation. Fig. 2 demonstrates that our problemset comprises a wide spectrum of easy to hard problems, thus enabling a comprehensive evaluation of capability of LLMs under various difficulties. Notably, some problems $i$ have high passi@1 but low effi@1 because they have a seemingly easy task with a non-trivial efficient algorithm / implementation. For example, problem #98 (counting uppercase vowels at even indices) has high passi@1=0.50 but low effi@1=0.03 because an efficient implementation for #98 needs a clever use of the builtin function str.translate rather than straightforward counting.

## 5 Related Work

Most of existing benchmarks for LLM-based code generation, including Spider (Yu et al., ),
HumanEval (Chen et al., ), MBPP (Austin et al., ), APPS (Hendrycks et al., ),
MultiPL-E (Cassano et al., ), DS-1000 (Lai et al., ),
HumanEval-X (Zheng et al., ), EvalPlus (Liu et al., ), and so on, focus on code correctness. Not until very recently have some sporadic attempts (Niu et al., ; Huang et al., ; Du et al., ) been made to evaluate code efficiency, and a number of fundamental challenges still remain uncharted and open which this work aims to address, including how to rigorously handle right-censored execution time, sample size, algorithm/implementation optimization, correctness, and worst-case efficiency. Due to the space limit, please refer to Appendix C for related work on code generation.

## 6 Conclusion

We have developed a rigorous and high-standard benchmark ENAMEL for evaluating the capability of LLMs in generating *efficient* code, which includes a new metric $\textnormal{eff@}k$ (with an unbiased, variance-reduced estimator), expert-written efficient reference solutions for our selected 142 problems, and expert-written strong test case generators. Our extensive evaluation has demonstrated that existing LLMs still fall short of generating expert-level efficient code.
We hope LLM developers pay more attention to efficiency of generated code and
build more powerful LLMs to reach expert level in the future.
Due to the space limit, please refer to Appendix D for limitations and future work.

## Contents

- A
LABEL:app:thm::nameA
A.1
LABEL:app:unbias::nameA.1
A.2
LABEL:app:var-reduc::nameA.2
- B
LABEL:app:eval::nameB
B.1
LABEL:app:exp-setting::nameB.1
B.2
LABEL:app:exp-subsets::nameB.2
- C
LABEL:app:related::nameC
- D
LABEL:app:lims::nameD
- E
LABEL:app:problems::nameE
E.1
LABEL:app:p10::nameE.1
E.2
LABEL:app:p36::nameE.2
E.3
LABEL:app:p40::nameE.3
E.4
LABEL:app:p109::nameE.4
E.5
LABEL:app:p154::nameE.5

Table: Table 5: Nomenclature.

## Appendix A Proof of Theorem 1

In this section, we provide the proofs of unbiasedness and variance reduction, respectively.

For reference, the main notations used in this paper are summarized in Table 5.

### A.1 Proof of Unbiasedness

First, recall that every efficiency score $e_{i,j}$ depends only on the corresponding code sample $c_{i,j}$. Since $c_{i,1},\dots,c_{i,n}$ are independent, then given any size-$k$ subset $J=\{j_{1},\dots,j_{k}\}\subseteq\{1,\dots,n\}$,

$$ $\displaystyle{\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim\textnormal {LLM}(z_{i})}}\Big{[}{\max_{j\in J}e_{i,j}}\Big{]}$ $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}[\max\{e_{i,j_{1}},\dots,e_{i,j_{k}}\}]$ (9) $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}[\max\{e_{i,1},\dots,e_{i,k}\}]$ (10) $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}$ (11) $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}.$ (12) $$

Next, recall that probability measures are finite (and thus $\sigma$-finite). Since efficiency scores $e_{i,j}$ are nonnegative, then by the Fubini–Tonelli theorem and Eq. (12),

$$ $\displaystyle{\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim\textnormal {LLM}(z_{i})}}\bigg{[}{\sum_{r=k}^{n}\frac{\binom{r-1}{k-1}}{\binom{n}{k}}e_{i ,(r)}}\bigg{]}$ $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}\bigg{[}{\operatorname*{\mathbb{E}}_{\begin{subarray} {c}J\subseteq\{1,\dots,n\}\\ |J|=k\end{subarray}}}\Big{[}{\max_{j\in J}e_{i,j}}\Big{]}\bigg{]}$ (13) $\displaystyle={\operatorname*{\mathbb{E}}_{\begin{subarray}{c}J\subseteq\{1, \dots,n\}\\ |J|=k\end{subarray}}}\Big{[}{\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,n} \sim\textnormal{LLM}(z_{i})}}\Big{[}{\max_{j\in J}e_{i,j}}\Big{]}\Big{]}$ (14) $\displaystyle={\operatorname*{\mathbb{E}}_{\begin{subarray}{c}J\subseteq\{1, \dots,n\}\\ |J|=k\end{subarray}}}\Big{[}{\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k} \sim\textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}\Big{]}$ (15) $\displaystyle={\operatorname*{\mathbb{E}}_{c_{i,1},\dots,c_{i,k}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}.$ (16) $$

### A.2 Proof of Variance Reduction

Note that efficiency scores $e_{i,j}\geq 0$ are bounded random variables:

$$ $\displaystyle e_{i,j}$ $\displaystyle\leq\frac{\sum_{l=1}^{L}h_{l}\cdot f_{i,j,l}}{\sum_{l=1}^{L}h_{l} }\leq\max_{l=1}^{L}f_{i,j,l}$ (17) $\displaystyle=\max_{l=1}^{L}\frac{(T_{i}-t_{i,j,l,m})^{+}}{T_{i}-\max\{t^{*}_{ i,l,m}\}_{m=1}^{M_{l}}}$ (18) $\displaystyle\leq\max_{l=1}^{L}\frac{T_{i}-0}{T_{i}-\max\{t^{*}_{i,l,m}\}_{m=1 }^{M_{l}}}<\infty.$ (19) $$

This implies that

$$ $\displaystyle{\operatorname*{\operatorname{Var}}_{c_{i,1},\dots,c_{i,k}\sim \textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}<\infty.$ (20) $$

Furthermore, note that $\widehat{\textnormal{eff}}_{i}\textnormal{@}k$ can be expressed as a U-statistic [Hoeffding, ]:

$$ $\displaystyle\sum_{r=k}^{n}\frac{\binom{r-1}{k-1}}{\binom{n}{k}}e_{i,(r)}= \frac{1}{\binom{n}{k}}{\sum_{\begin{subarray}{c}J\subseteq\{1,\dots,n\}\\ |J|=k\end{subarray}}{\max_{j\in J}e_{i,j}}}.$ (21) $$

Therefore, by Theorem 5.2 of Hoeffding [],

$$ $\displaystyle{\operatorname*{\operatorname{Var}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}\bigg{[}{\sum_{r=k}^{n}\frac{\binom{r-1}{k-1}}{\binom {n}{k}}e_{i,(r)}}\bigg{]}$ $\displaystyle={\operatorname*{\operatorname{Var}}_{c_{i,1},\dots,c_{i,n}\sim \textnormal{LLM}(z_{i})}}\bigg{[}\frac{1}{\binom{n}{k}}{\sum_{\begin{subarray} {c}J\subseteq\{1,\dots,n\}\\ |J|=k\end{subarray}}\max_{j\in J}e_{i,j}}\bigg{]}$ (22) $\displaystyle\leq\frac{k}{n}\cdot{\operatorname*{\operatorname{Var}}_{c_{i,1}, \dots,c_{i,k}\sim\textnormal{LLM}(z_{i})}}\Big{[}{\max_{j=1}^{k}e_{i,j}}\Big{]}.$ (23) $$

## Appendix B Evaluation (Continued)

### B.1 Experimental Setting

Code generation. For models that are included in Liu et al. [], we re-use their generated code samples. For other open-source models, we use temperature 0.8 and top_p 0.95 for sampling on a server with 8 NVIDIA A100 80GB GPUs. For Claude 3 models, we use the API provided by Anthropic with temperature 0.8 for sampling. Due to financial and computational constraints, for relatively smaller models, we generate 200 code samples per problem under sampling; for larger models, we generate 100 code samples per problem under sampling; for largest commercial models, we only use greedy decoding. In our experiments, Claude 3 Opus corresponds to claude-3-opus-20240229; Claude 3 Sonnet corresponds to claude-3-sonnet-20240229; Claude 3 Haiku corresponds to claude-3-haiku-20240307; GPT-4 Turbo corresponds to gpt-4-1106-preview; GPT-4 corresponds to gpt-4-0613.

Code evaluation. We use $\alpha=2$, $R=6$, $h_{1}=h_{2}=3$, $h_{3}=4$, $M_{0}=8$, $M_{1}=M_{2}=M_{3}=4$. To minimize server workload fluctuations, we run evaluation on virtualized cloud servers hosted by Google Cloud (Ubuntu 20.04.6 LTS; Intel Xeon CPU @ 2.20GHz; Python 3.10.12). We use the reference time on the slowest test case for each problem to further calibrate the execution time of generated code. Our benchmark is publicly available at [https://github.com/q-rz/enamel](https://github.com/q-rz/enamel).

Use of existing assets. Our benchmark partially uses problems from HumanEval (Chen et al., ; MIT License) and prompts from HumanEval+ (Liu et al., ; Apache License). Some reference solutions are modified based on the canonical solutions in HumanEval and HumanEval+.

**Table 6: Complete evaluation results on two subsets of problems.**
| Model | Algorithm Design Subset | Implementation Optimization Subset |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| eff@1 | pass@1 | eff@10 | pass@10 | eff@100 | pass@100 | eff@1 | pass@1 | eff@10 | pass@10 | eff@100 | pass@100 |  |
| Llama 3 70B Instruct | 0.246 | 0.660 | 0.306 | 0.749 | 0.359 | 0.750 | 0.404 | 0.791 | 0.497 | 0.869 | 0.551 | 0.920 |
| Llama 3 8B Instruct | 0.201 | 0.518 | 0.303 | 0.724 | 0.367 | 0.849 | 0.313 | 0.582 | 0.468 | 0.806 | 0.571 | 0.906 |
| Mixtral 8x22B Instruct | 0.225 | 0.635 | 0.363 | 0.837 | 0.470 | 0.900 | 0.376 | 0.783 | 0.556 | 0.914 | 0.686 | 0.947 |
| Mixtral 8x7B Instruct | 0.124 | 0.391 | 0.244 | 0.681 | 0.344 | 0.850 | 0.248 | 0.473 | 0.411 | 0.699 | 0.515 | 0.827 |
| Claude 3 Sonnet | 0.184 | 0.577 | 0.328 | 0.804 | 0.450 | 0.950 | 0.358 | 0.723 | 0.475 | 0.846 | 0.548 | 0.893 |
| Claude 3 Haiku | 0.149 | 0.692 | 0.208 | 0.752 | 0.266 | 0.775 | 0.360 | 0.772 | 0.465 | 0.889 | 0.513 | 0.923 |
| Phind Code Llama V2 | 0.185 | 0.554 | 0.353 | 0.789 | 0.401 | 0.849 | 0.351 | 0.712 | 0.567 | 0.901 | 0.732 | 0.968 |
| ChatGPT | 0.120 | 0.488 | 0.304 | 0.799 | 0.483 | 0.950 | 0.337 | 0.715 | 0.508 | 0.864 | 0.633 | 0.949 |
| Code Llama 70B Python | 0.018 | 0.100 | 0.129 | 0.519 | 0.402 | 0.950 | 0.076 | 0.181 | 0.294 | 0.627 | 0.589 | 0.920 |
| Code Llama 34B Python | 0.071 | 0.293 | 0.271 | 0.713 | 0.425 | 0.881 | 0.197 | 0.415 | 0.473 | 0.804 | 0.687 | 0.949 |
| Code Llama 13B Python | 0.058 | 0.212 | 0.276 | 0.665 | 0.478 | 0.844 | 0.176 | 0.405 | 0.476 | 0.784 | 0.715 | 0.928 |
| Code Llama 7B Python | 0.068 | 0.202 | 0.231 | 0.589 | 0.393 | 0.761 | 0.165 | 0.349 | 0.417 | 0.703 | 0.620 | 0.863 |
| StarCoder | 0.047 | 0.161 | 0.156 | 0.485 | 0.257 | 0.709 | 0.112 | 0.247 | 0.332 | 0.598 | 0.514 | 0.802 |
| CodeGen 16B | 0.031 | 0.133 | 0.146 | 0.451 | 0.292 | 0.684 | 0.099 | 0.220 | 0.303 | 0.541 | 0.531 | 0.801 |
| CodeGen 6B | 0.023 | 0.091 | 0.106 | 0.372 | 0.235 | 0.612 | 0.090 | 0.188 | 0.285 | 0.478 | 0.483 | 0.731 |
| CodeGen 2B | 0.036 | 0.131 | 0.121 | 0.387 | 0.193 | 0.644 | 0.081 | 0.160 | 0.256 | 0.400 | 0.410 | 0.610 |
| CodeT5+ 16B | 0.043 | 0.192 | 0.173 | 0.509 | 0.321 | 0.673 | 0.106 | 0.257 | 0.313 | 0.581 | 0.536 | 0.845 |
| Mistral 7B | 0.030 | 0.152 | 0.157 | 0.516 | 0.319 | 0.737 | 0.100 | 0.227 | 0.327 | 0.574 | 0.565 | 0.821 |
| Vicuna 13B | 0.008 | 0.072 | 0.033 | 0.269 | 0.076 | 0.449 | 0.056 | 0.096 | 0.168 | 0.288 | 0.316 | 0.569 |
| Vicuna 7B | 0.019 | 0.071 | 0.083 | 0.241 | 0.113 | 0.300 | 0.031 | 0.061 | 0.121 | 0.215 | 0.260 | 0.439 |
| SantaCoder | 0.037 | 0.102 | 0.101 | 0.316 | 0.203 | 0.493 | 0.069 | 0.114 | 0.203 | 0.308 | 0.357 | 0.488 |
| Incoder 6B | 0.010 | 0.050 | 0.062 | 0.203 | 0.112 | 0.325 | 0.037 | 0.062 | 0.152 | 0.252 | 0.320 | 0.477 |
| Incoder 1B | 0.003 | 0.023 | 0.021 | 0.110 | 0.071 | 0.200 | 0.018 | 0.030 | 0.080 | 0.129 | 0.172 | 0.232 |
| GPT-J | 0.021 | 0.051 | 0.063 | 0.146 | 0.081 | 0.243 | 0.025 | 0.043 | 0.110 | 0.167 | 0.221 | 0.354 |
| GPT-Neo 2B | 0.003 | 0.019 | 0.015 | 0.098 | 0.032 | 0.172 | 0.007 | 0.014 | 0.050 | 0.084 | 0.113 | 0.184 |
| PolyCoder | 0.002 | 0.010 | 0.018 | 0.070 | 0.050 | 0.163 | 0.004 | 0.007 | 0.034 | 0.051 | 0.092 | 0.122 |
| StableLM 7B | 0.001 | 0.005 | 0.010 | 0.039 | 0.033 | 0.099 | 0.002 | 0.003 | 0.016 | 0.025 | 0.074 | 0.099 |

### B.2 Analysis on Algorithm Design & Implementation Optimization (Continued)

The complete version of Table 4 is shown in Table 6. We can see that observations for Table 6 are similar with those for Table 4.

## Appendix C Related Work (Continued)

Code generation (a.k.a. program synthesis) is a long-standing problem in computer science [Simon, ]. Many classic code generation methods have been proposed over the past few decades [Gulwani et al., ], including deductive [Waldinger and Lee, , Manna and Waldinger, , Green, ], inductive [Shaw et al., , Gulwani, ], and neural-guided approaches [Kalyan et al., , Yu et al., ]. More recently, many code LLMs have been developed, including Codex [Chen et al., ], AlphaCode [Li et al., ], CodeGen [Nijkamp et al., ], StarCoder [Li et al., ], Code Llama [Roziere et al., ], CodeT5+ [Wang et al., ], and so on. Some general LLMs such as GPT [OpenAI, ], Llama [Meta, ], Claude [Anthropic, ], Gemini [Google, ], and Mixtral [Jiang et al., ] also exhibit promising capabilities in code generation.

## Appendix D Limitations & Future Work

The following are limitations of this work that we wish to be addressed in future work:

- •
This work employs human experts to develop high-quality reference solutions in order to set up a high standard for efficiency evaluation, and test case generators based on the relatively small HumanEval problemset. How to enable high-standard efficiency evaluation with larger problemsets is an interesting open challenge. A possible solution is crowdsourcing or automating the development of reference solutions and test case generators.
- •
This work considers standalone programming problems. Meanwhile, real-world software development typically involves complex dependencies among files. Thus, it is worth studying how to generalize our methodology to more complex code generation datasets such as DevBench [Li et al., ].
- •
Although we have used the known best algorithms as our reference solutions, it is hard to theoretically guarantee their optimality. Thus, the efficiency score can be greater than 1 if the benchmarked code is more efficient than our reference solution. Addressing this issue in future work will provide a solid ground for efficiency evaluation.
- •
This work focuses on benchmarking code efficiency without advanced prompting techniques. Future work can explore how to design prompts to improve the efficiency of LLM-generated code. A possible solution is to guide the LLM to analyze the time complexity in the chain of thought [Wei et al., ] when generating the code.

## Appendix E Code for Example Problems in Table 1

### E.1 HumanEval Problem #10

Problem description: Find the shortest palindrome that begins with a given string ($S$).

HumanEval+ canonical solution: Enumerate suffixes and check palindromicity. The time complexity is $\mathrm{O}(|S|^{2})$.

Our expert-written solution: Note that the answer is the concatenation of the *border* of reversed $S$ plus $S$ and reversed $S$, so we can use the Knuth–Morris–Pratt algorithm to compute the border of reversed $S$ plus $S$. The time complexity is $\Theta(|S|)$.

### E.2 HumanEval Problem #36

Problem description: Count digit 7’s in positive integers $<n$ that are divisible by 11 or 13.

HumanEval+ canonical solution: Enumerate integers $<n$ and count the digits. Since the length of the integer $n$ is $\Theta(\log n)$, the time complexity is $\Theta(n\log n)$.

Our expert-written solution: Design a dynamic programming over digits. Since 10, 11, and 13 are constants, the time complexity is $\Theta(\log n)$, the length of the integer $n$.

### E.3 HumanEval Problem #40

Problem description: Check if a list $l$ has three distinct elements that sum to 0.

HumanEval+ canonical solution: Enumerate triples in $l$ and check their sums. The time complexity is $\mathrm{O}(|l|^{3})$.

Our expert-written solution: Note that $l_{i}+l_{j}+l_{k}=0$ is equivalent to $l_{k}=-l_{i}-l_{j}$, so we can enumerate $l_{i},l_{j}$, store $-l_{i}-l_{j}$ in a hash set, and check whether $l_{k}$ is in the hash set. The time complexity is $\mathrm{O}(|l|^{2})$.

### E.4 HumanEval Problem #109

Problem description: Check if a list arr ($a$) can be made non-decreasing using only rotations.

HumanEval+ canonical solution: Enumerate the rotations of $a$ and check if it is sorted. The time complexity is $\mathrm{O}(|a|^{2})$.

Our expert-written solution: Note that the desired condition is equivalent to the condition that there is at most $0\leq i<|a|$ with $a_{i}>a_{(i+1)\bmod n}$, so we can enumerate $i$ and check this equivalent condition. The time complexity is $\mathrm{O}(|a|)$.

### E.5 HumanEval Problem #154

Problem description: Check if any rotation of a string $b$ is a substring of a string $a$.

HumanEval+ canonical solution: Enumerate rotations and run brute-force string matching. The time complexity is $\mathrm{O}(|b|^{2}|a|)$.

Our expert-written solution: Note that the desired condition is equivalent to the condition that the longest common substring of $a$ and $b+b$ is at least $|b|$. Thus, we can run the suffix automaton of $a$ w.r.t. $b+b$ to compute their longest common substring. Since the suffix automaton of $a$ can be built within $\Theta(|a|)$ time, the overall time complexity is $\mathrm{O}(|a|+|b|)$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
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)$.
soundness: 4
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
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.
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

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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.
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 4
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.
soundness: 3
strengths: 1. Clear and fluent presentation. The metric is carefully designed.
2. The evaluation is convincing and indicative.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 2
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.
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.
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.

Meta-review: 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.

Decision: Accept (Poster)