How efficient is LLM-generated code? A rigorous & high-standard benchmark
Authors: Ruizhong Qiu
Weiliang Will Zeng
James Ezick
Christopher Lott
Hanghang Tong
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Model
Code Generation
Efficiency Evaluation
Primary area: datasets and benchmarks
TL;DR: We develop ENAMEL, a rigorous and high-standard benchmark to evaluate the capability of LLMs in generating efficient code.

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.

Published as a conference paper at ICLR 2025
How EFFICIENT IS LLM-GENERATED CODE? A RIGOROUS & HIGH-STANDARI BENCHMARK
Ruizhong Qiu! Weiliang Will Zeng! James Ezick! Christopher Lott & Hanghang Tong University of Illinois Urbana- Shaana-Champaign *Qualcomm Al Research (rq5, htong] illinois edu (wzeng, jezick, clott @qtti quallomme com
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 L.-M-generated code. Most evaluation frame- works focus the (functional) correctness of generated code; efficiency, important measure of code quality, has been overlooked in existing evaluations. In this work, we develop ENAMEL (EfficeNcy AutoMatic EvaLuator), rigorous and high-standard benchmark for evaluating the capability of LLMs in generating efficient code. Firstly, we propose a new efficiency metric called eff@ which generalizes the pass & 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- Rao-BBackwellizattonn we also provide a numerically stable implementation for the new estimator. Secondly, to set a high standard for efficiency evaluation, employ human expert design best al- gorithms and implementations as our reference solutions of efficiency. many which are much more efficient than existing canonical solutions in HumanEval and HumanEval+. Moreover, to ensure rigorous evaluation, we employ a human expert to curate strong test generators filter out wrong code and differenti- ate 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 because current LLMs struggle designing advanced algorithms and are barely aware of implementation optimization. Our benchmark is publicly available httttps: /tttts:://ithubi com/ q- r /eamme
INTRODUCTION
The emergence of large language models (LLMs; Brown et al. 2020 Touvron et al., 2023) has driven the frontiers of program synthesis SSion 1963) Gulwani et al. 2017) with the help of large open codebases for pretraining.
number of code LLMs have been released (Chen et al.,
2021 Li et al. 2022, Nijkamp et al.) 2023 Roziere et al. 2023). They autorcgressively generate code from prompt that describes the requirement (c.g., the form of function signature and docstring). Advancement of LLM-based program synthesis in turn calls for a thorough evaluation of LLM-ggeerated code. Most of the existing evaluation frameworks (Chen et al., 2021 Austin
et al. 2021] Hendrycks et al., [021] Cassano et al.) 2022: Lai et al., [2023] Liu et al. 2023a) focus
on the (functional) correciness of generated code. Each framework has collection of programming problems along with test cases, which are used to evaluate the correctness of generated codes.
Apart from correctness, however, efficiency 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 few benchmarks (Nichols et al. 2024 Niu et al. 2024
Huang et al. [2024] Du et al. (2024) been proposed to evaluate the efficiency of LLM L---eeeertted code,
and number of fundamental challenges remain uncharted and open:
Qualcomm AI Research is initiative of Qualcomm Technologies, Inc. All datasets were downloaded and evaluated at the University of Illinois Urbana- Champaagn..

---

Published as a conference paper at ICLR 2025
HumanEval: 2 recursions
GPT4 Turbo: G(n) iterations
Ours: G(log/) Itarations
def fib(n):
def rib(n):
fib(n):
for range(n):
9,
return h,
bin
=]
return
3,
return Fib(n 13 Fib(n
14 return
'2":
by
Level
Level X
Level
Level 1
Score
Level
Level
Level 2
Ory 0.0
Og F
Level
Level 3
Level 3
Test case pessed
Time limit exceeded
Test case skipped
Figure 1: Illustration of our ENAMEL framework with HumanFval problem #55 (computing the n-th Fibonacci number). Our level-based evaluation clearly differentiates the three algorithms: (i) naive algorithm that needs 28(n) recursions, (ii) a dynamic programming algorithm that needs (() iterations, and (iii) an efficient doubling algorithm that needs only @ n.) iterations.
(C1) Right-censored execution time. When code execution is early terminated due to time limit, its actual execution time unknown; this right censoring in statisties (Bang & Tsiatis 2000). For instance, if the generated code contains an infinite loop, the right- censored execution time will be clipped the time limit while the actual execution time should be infinity. Existing works (Niu et al., 2024 Huang et al. 2024) 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., (021) to characterize the efficiency given sample sizes k: Existing work either uses only code sample (Niu al. 2024) averages the efficiency
of code samples (Huang et al.) 2024 Du et al. 2024); therefore, they fall short 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 implementa- tion optimization that can highly non-trivial even for human programmers. Prior works either use existing canonical solutions provided in the dataset the reference (Niu et al.) 2024 Huang et al., 2024) or use solutions collected online (Du et al.) 2024), but our eval- uation 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 the Fermat primality test, which known to have nontrivial counterexamples (Carmichael) 1912). Thus, we need use strong test cases filter wrong code and evaluate efficiency only with correct code. Niu et al. (202)) rely on existing test cases provided by the dataset, but Liu et al.
(2023a) 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 strong inputs. For example, if we search for length-m sub- string length-n string, a brute-force algorithm takes only O(n r + m) time on random strings but requires (nm)) time in the worst case. Huang et al. 2024) and Du et al. (2024) use GPT to produce test case generators, but we found that their test cases are mostly ran- dom and thus cannot differentiate such suboptimal algorithms.
To collectively address the aforementioned challenges, we develop ENAMEL (EfficieNcy Auto- Matic EvaLuator), high-quality benchmark to rigorously evaluate the capability of LLMs in gener- ating efficient code. We carefully select 142 problems out of the 164 problems in HumanEval (Chen) et al., 2021) and HumanEval+ (Liu et al. 2023a). excluding trivial problems with O(1) time com- plexity. With wide spectrum of easy to hard problems, how capable the LLM to generate efficient code for various problems. Our main contributions are follows:
able to comprehensively evaluate
2

---

Published as a conference paper at ICLR 2025
Efficiency metric & its unbiased, variance-reduced estimator. We propose new ef- ficiency metric called eff@k, which generalizes the pass@ metric from correctness to efficiency. Our cff@ k metric properly handles right-censored execution time (C1) and pre- cisely characterizes the efficiency under different sample sizes k (C2). Furthermore, we derive unbiased, variance-reduced estimator of our eff@ k via Backkelizzllii,nnnnn, 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 design best algorithms and implementations 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 comput- ing the n-th Fibonacci number in HumanEval+ needs (nn) iterations while our reference solution needs only Oloog n) iterations.
Strong test case generators. To ensure rigorous evaluation, we employ 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, rigorous and high- standard benchmark for evaluating the capability of I.L.S 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=08331. 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 @ff@k of an LLM with an unbiased, variance-reduced estima- tor 2.3
The main notations used in this paper are summarized in Table
2.1 LEVEL-BASED EVALUATION
To achieve fine-grained evaluation of efficiency, we aim not only let the most efficient code pass but also to give 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 set 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. I if we used large-scale inputs that allow only the code with O(log n) iterations to pass, then we would not be able to give different scores for the code with 29(x) recursions and the code with ((n) iterations.
To address this issue, we propose to use multiple levels 1, ..... 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; while the input scale increases with the level (i.c., 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...., L. we use an additional level 0 to filter out wrong code using small strong inputs. For each problem i, each level = 0, 1,.... L has Mj test cases. If the output of the code does not match the expected output in any test case or does not pass level O, we will not count it into the pass @ k metric. If the code passes level 0 but exceeds the time limit in some level 1 2 1, we will still count it into the pass @ k metric but will skip the remaining levels (i.c., we assume that it will also exceed the time limit for the remaining levels because the input scale increases with the level (). Finally, we compute its efficiency score according 22.2
Example. Fig. D illustrates our evaluation framework via HumanEval problem #55 (computing the 1-th Fibonacci number). Level has n < 10 so that the naive recursive algorithm (in 2 recursions) can pass; level has n < 30 that the dynamic programming algorithm (in O(n)
3

---

Published as a conference paper at ICLR 2025
iterations) pass; level 2 has v 9000 so that the matrix exponentiation algorithm (in (log n) iterations by repeated squaring) can pass; level 3 has n S 10000 so that the doubling algorithm (still in (log n) iterations yet with smaller hidden constant in )) 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 & Tsiatis 2000) execution time: when an execution is killed due to exceeding the time limit T, we cannot know its actual execution time & and only know that & - 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 al. [024] Huang et al. (2024) 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 Ci of problem and for each level I, if the code C.yy is correct, we define the efficiency score figa by
Rig = (Ti max (li.j..m m=))
(1)
T, max 1mmmm m==1
where li.ji.m is the execution time of code caj for the m-th test case in level I; f/,. is the execution time of our reference solution for the m-th test case in level I; T; is the time limit of problem i; and (-)+ == ma Here, we use max(ts,fi.m Jm= 1 in figa 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ū.j. is not affected by right-censored execution time because whenever max 1M, m=1 2 T,, our score figj will have the same value zero regardless of the exact value of max (f.5..m...mm ) m=1-- Also, we normalize our efficiency score fij. using our reference solution so that the scale of the score does not differ across problems. For the time limit, we use T; == a ma. reduce the variance of the execution time caused by hardware performance fluctuations, we repeat each test case R times and estimate the execution time f.j.m. via the Medges-Lehmann estimator (Hodges & Lehmann 1963) because of its robustness against outliers as well as its high statistical efficiency.
where a > 1 is a hyperparameter. Besides that, to
Finally, since each level has a distinct hardness, we define the efficiency score eij of a code sample Ci2 of problem i by weighted average over levels 1, L:
Elen be-fai Elz ha
if code o. is correct;
Gi,j =
(2)
0,
otherwise.
where hyperparameters h4 >> 0 represent the hardness of each level I.
2.3 EFFICIENCY METRIC FOR LLM
The pass@k metric (Chen et al. the probability that at least one among k generated code samples is correct. Meanwhile, existing efficiency evaluations (Niu al. 2024 Huang et al.) 2024) use the average execution time as the metric and thus fall short of describing the relationship between code efficiency and sample size k.
202 the standard metric in correctness evaluation, which means
To overcome this limitation and evaluate the capability of an LLM in generating efficient code w.r.t. the sample size k, we aim generalize the pass @ & metric from correctness to our continuous efficiency score. Let 2; denote the prompt of problem i; let c, ~ LLM(2;) denote the generated code samples for problem é; let It.j {0, 1} denote the correctness of code Ca,y; and let pass, @k denote the pass @ & 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.
4

---

Published as a conference paper at ICLR 2025
To address this, we equivalently express pass, @ expectation:
pass, @k G (LLM
[31 S S k 9i.j = G LLMM()))
max Ji,j
A =
(3)
==1
E
max 9ij
(4)
This equivalent formula in Eq. 4 longer relies the Boolean nature of code correctness and naturally extends to our continuous efficiency score. Hence, we define our efficiency metric eff, @ by the expected maximum efficiency score of independent code samples:
k max e L
eff, @k :
E
(5)
where Gi,j denotes the efficiency score of code Ci2 defined in 2.2 Our metric eff, @ k precisely characterizes the relation between code efficiency and sample size & via the maximum over code samples while the metric in previous works (Niu et al., 2024 Huang et al. 2024) is simply an average over code samples and cannot describe relation with sample size k.
However, estimating eff, @+ naïvely by generating h code samples and calculating their maxi- mum 6ig can have high variance (Chen et al. 2021). To reduce the variance eff, @k esti- mation, we employ two advanced variance reduction techniques: (i) bootstrap (Efron 1979) and (ii) Rao- Blackwellization (Casella & Robert 1996). Specifically, for n 2 k i.i.d. code samples ci,1...., Ctn LLM(2)), the bootstrap estimator is the average of maxjeJ Ci,y over multiple dom subsets J S (1...., n} with |J] = k, and we obtain our final estimator eff, @ k by Rao- Blackwellizing the boostrap estimator (i.e., taking expectation over the random subset J):
eff, @k =
E
max C.j
(6)
m J
JEJ
where (i,(r) denotes the r-th smallest score among c,...... Ci.,s and (*) denotes the binomial coefficient. Furthermore, we show in Theorem [
that our Rao hhoo-Bacckweliieed bootstrap estimator
eff, @ k is unbiased and does reduce variance.
Theorem 1. Suppose that problem has time limit T, oo and reference execution times t.t.
T, Under the randomness of code generation and execution, for n 2 k; we have;
Unbiasedness:
E 04,1 C (
Σ
ci(r)
E C. M
max
Ci.j
Variance reduction:
Var C1.1 C M
Ci,(r)
S
Var LLM
max C..
(8)
L=1
Proof is in
B Due to unbiasedness, we will use eff; @h and eff, @k interchangeably from now on.
As remark, naïvely computing the coefficients (x=1)/(3 in eff, @k can result in numerical insta- bility. Instead, we propose numerically stable implementation of eff, @k, presented in Algorithm Finally, we define our efficiency metric eff@@ k by averaging eff, @k over all problems
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
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 Numerically stable eff, @k
Input: score list [ci,1:---, Ci,n]; ; the target h
Output: the estimated eff, @k
1: An <
2: for r f- n 1, 2. k: do
3: Ar f- Ar+1 (1 k=1
4: end for
5: (er(1)):.., t (eea c,,)))
6: return Dr= (rei,())
Table 1: sample of hard problems in our problemset. Our expert-writte 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
O(ls: Enumerate suffixes and check pulindromicity
@((S)): Use Knuth-Morris- Pratt wir.t. reversed plus
Count digit 7's in positive integers n that are divisible by 11 13
θ(n Boglog)): Enumerate inte- gers n and count the digits
(log x): Design a dynamic programming over digits
#33
Check a list has three distinct elements that to
O(llf):: Enumerate triples and check their sums
O(I1():: Use hash set and enumerate pairs in
#40
Check list a can be made non-
O(jaf)): Enumerate the rota- tions of and check
O(la]): Check the list a has most inversion
#109
decreasing using only rotations
Check if any rotation of a string is substring of string a
O(|b/*aa ):
Enumerate rota-
O[[a] + [B]] Run the suffix automaton of w.r.. b+
#154
tions and run string matching
3.1 PROBLEM SELECTION
To achieve a comprehensive evaluation of efficiency, we aim to create a problemset that contains high-quality problems with broad range of difficulties. Thus, following HumanEval+ (Liu al. 2023a), we re-use the problems from the HumanEval dataset (Chen et al. (021) 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 nith Fibonacci number) is dynamic programming with ((n) iterations, a large n requires an advanced doubling algorithm that needs only O(log n)) iterations based on non-trivial identity of Fibonacci numbers.
Meanwhile, we find that some problems in HumanEval with ((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 un- informative 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 evaluation of how capable the LLM is in generating efficient code under various difficulties. Table exhibits a sample of hard problems in our problemset.
wide spectrum of easy to hard problems, thus enabling a comprehensive
3.2 EFFICIENT REFERENCE SOLUTIONS
An ideal reference of efficiency should be the most efficient code, which often needs advanced algo- rithms 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 de- signs 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 algorithm design stage and implementation optimization stage below.

---

Published as a conference paper at ICLR 2025
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 pro- grammers. 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 ran- domized algorithms whenever 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 for 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 effi- ciency 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 hu- man 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., 2024), which are known to be not strong enough (Liu et al. 2023a), or use ChatGPT-generated test case generators (Huang et al. 2024), 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] 1912). As 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 deseription.
Our expert-written test case generators set strict and high standard for both correctness and effi- ciency. For example, 11 canonical solutions in HumanEval and in HumanEval+ are found wrong, and 34 in HumanEval and 27 in HumanEval+ exceed the time limit (see Table 2 for comparison).
4 EVALUATION
Table 2: Comparison with existing benchmarks.
We comprehensively evaluate 30 popular LLMs with our ENAMEL benchmark. Due to the space limit, see Appendix C.I for experi- mental setting.
Name
cff@
pass
HvmanEval
0.455
0.908
HumanEval+
0.513
0.972
ENAMEL (ours)
1,000
1.000
4.1 MAIN RESULTS& & ANALYSIS
Table 3 shows pass @ and 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>00.5, and most LLMS cannot even reach eff@ 100.3. We also observe that eff@ k is consistently much lower than pass@ k across all LLMs, model sizes, and sample sizes k. This stems from the fact that existing research has been primarily focusing 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 not always equally good at generating efficient code. For than GPT-4 although GPT-4 has higher pass @ than GPT-4 Turbo. A possible reason is that naive algorithms easier to be generated correctly but less
instance, GPT-4 Turbo has higher e

---

Published as a conference paper at ICLR 2025
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.
Greedy
Sampling pass
Model
eff@1
pass@
eff@1
pass
eff@
eff@ 100
pass 100
GPT-4 Turbo
0.470
0.796
GPT-4
0.454
0.831
Ilama 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 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 Jamma 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
CodeGien 6/s
0,193
0.296
0.111
0.188
0.248
0.455
0.491
0.694
CodeGen 2B
0,153
0.254
0.098
0.168
0.264
0.389
0.421
0.602
CodeTS+ 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 C.2 for the complete table.)
Model
eft@
Algorithm Design Sabset
etTer10
Pisee 10
efT 100
puss6 100
eTT
pass@
Implementation Optimization Sultset
efr@10
cIT@ 100
pise 100
Llama 3 Instruct
0:246
0.666)
0.306
0.749
0.359
0.750
0.404
0.497
(1.51
0.92)
5B
0.201
0.518
0.303
0.724
0.549
0.313
0.468
0.571
0.906
Mixtral 2x228 Instract
0:225
0.635
0.363
0,337
0.470
0.500
0.376
0.763
0.556
0.914
0.686
0.947
Mixiral 8x7B Instruct
0.124
0.391
0.244
0.681
0.344
0.850
0.245
0.473
0.411
0.689
0.515
0.827
Claude Sonaet
0.184
0,577
0.328
0.804
0.450
0.950
0.35%
0.725
0.475
0.846
0.548
0.93
Clande 3 Haiku
0.149
0.692
0.288
0.752
0.266
0.715
0,360
0,772
0.465
0.889
0.513
0.923
Phind Code Elaam V2
0.185
0.554
0.353
0.789
0.401
(1.49)
0.351
0.712
0.567
0.901
01732
0.688
ChaGPT
0.120
0.488
0.304
0.799
0.433
0.950
0.337
0,715
0.508
0.864
0.633
0.999
Code Lluna 708 Pythoo
0:018
0.100
0.119
0.950
0,0776
0.294
0.627
(1589
0.200
Code Liama Python
0.071
0.293
0.271
0.713
0.425
0.581
0.197
0.473
0.687
0.949
Code L.tam 138 Python
0:058
0.212
0.276
0.665
0.478
0.544
0.176
0.405
0.476
7844
0.715
0.228
Code Lhaaa 7B Pylhum
0.068
0.202
0.231
0.589
0.393
0.761
0.165
0.349
0.417
0.703
0.620
0.563
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 L.MMs 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 algo- rithm design. For these problems, the optimal algorithm can have significantly lower time complex- ity than suboptimal algorithms (see Table I for a sample of these problems). Table 4 shows that even when generating 100 samples per problem, the generated code still has low effciincc. For instance, ChatGPT has eff@ 100=0.483 on this subset, still below 0.5. This suggests that existing L.LMs struggle in designing advanced algorithms.
8

---

Published as a conference paper at ICLR 2025
1.0
pass:
0.8
eff
Metrie Value
0.6
0.4
0.2
0.0
Problem (sorted by effi@1))
Figure 2: Distribution of problem difficulties (best viewed in color). High pass; @1 but low eff, @) means problem has a seemingly easy task but non-trivial efficient algorithm/ / implementation.
Implementation optimization. We subset of 75 problems to evaluate the capability in imple- mentation optimization. For these problems, the optimized implementation can have much higher efficiency than naive 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 sub- set. This suggests that existing LLMs are barely aware of implementation optimization, and the improvement mainly because random sampling generates multiple equivalent implementations.
4.3 DISTRIBUTION OF PROBLEM DIFFICULTIES
To investigate the difficulty distribution of our problems, we plot their pass, @1 and eff, @1 (av- eraged over LLMs under greedy generation) in Fig. 2 where pass, @ represents the difficulty of straightforward implementation, and eff, @ represents the difficulty of efficient implementation. Fig. 2 demonstrates that our problemset comprises a wide spectrum easy to hard problems, thus enabling a comprehensive evaluation of capability of LLMs under various difficulties. Notably, some problems i have high pass; @1 I but low eff, @ 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 pass, @1 =0.50 but low eff, @ 100.03 because an efficient implementation for #98 needs clever use of builtin functions rather than straightforward counting.
5 RELATED WORK
Code generation. Code generation (a.k.a. program synthesis) is long-standing problem in com- puter science (Simon] 1963). Many classic code generation methods have been proposed over the past few decades (Gulwani et al., (007)), including deductive (Waldinger & Lee 1969: Manna & Waldinger 1971; Green 1981.. inductive (Shaw et al., 1975| Gulwani, (011). and neural-guided
approaches Kalyan al. 20188] Yu al. (002)). More recently, many code LLMs have been de- veloped, including Codex (Chen et al. 2021). AlphaCode (Li et al. 2022). CodeGen (Nijkamp) al. 2023), StarCoder (Li et al. 2023). Code Llama (Roziere et al.] 2023), CodeT5+ (Wang al.) 2023b), and so on. Some general LLMs such as GPT (OpenAl 2023). Llama (Meta) (2024). Claude
(Anthropic 2024), Gemini (Google 2024), and Mixtral (Jiang et 2024) also exhibit promising capabilities in code generation.
Benchmarks for L.M-- code generation. L.LMs have revolutionized machine learning Wei Xu et al., 2024a b; Chen et al.
et al. 2024a| b: 2023;
2024;
Liu et al.] 2024a b
2023b Qiu et al.)
2024b a 2023 2022
Qiu & Tong 2024
Zeng et al. 2024a b Lin et al. 2024a b Yoo et al. 2025
Li et al. 2024b Qi et al. 2023; Ban et al. (2221). Most of existing benchmarks for LLM based code generation, in-
2024 Chan et al.) 2024 Wu et al. 2024 He et al.)
2024a bi Wang et al. 2023a
cluding Spider (Yu et al. 2018), HumanEval (Chen et al.] 2021), MBPP (Austin et al. 2021), APPS
(Hendrycks et al.] 2021), MultiPL-E (Cassano et al. 2022). 1000000 (Lai et 2003). HumanEval-
X (Zheng et al. 2023), EvalPlus (Liu al. 2023a), and on, focus on code correctness. Not until

---

Published as a conference paper at ICLR 2025
very recently have few benchmarks (Nichols al. 2024 Niu et al. 2024 Huang al. 2024
Du et al. 2024) been proposed to evaluate code efficiency, and a number of fundamental chal lenges still remain uncharted and open, which this work aims address, including how rigorously han- optimization, correctness,
dle right-censored execution time, sample size, algorihn//mppementaaie and worst-case efficiency. For instance, classic efficiency metries such as speedup (see, e.g-- Am- dahl [9677; (ouuati 2009) are not designed for right-censored execution time and thus overestimates efficiency when an execution times out.
CONCLUSION
We have developed rigorous and high-standard benchmark ENAMEL for evaluating the capabil- ity of LLMs in generating efficient code, which includes a new metric eff@ k (with an unbiased, variance-reduced estimator), expert-written efficient reference solutions for our selected 142 prob- lems, and expert-written strong test case generators. Our extensive evaluation has demonstrated that existing I.LMs still fall short of generating expert-level efficient code. We hope L.LM developers pay more attention to efficiency of generated code and build more powerful LLMs to reach expert level in the future. Please see Appendix for limitations and future work.
ACKNOWLEDGMENTS
This work is supported by NSF (2134079), and NIFA (2020-67021-22799), and IBM-Illinois Dis- covery Accelerator Institute. The content of the information in this document does not necessarily reflect the position or the policy the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, pp- 781-793, 2004.
Gene M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the April 18-20, 1967, spring Joint Computer Conference, pp- 483-485, 1967.
Anthropic. The Claude 3 model family: Opus, Sonnet, Haiku, 2024.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models. arXiv,
2021.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-Net: Exploitation-explraaiio neural networks in contextual bandits. arXiv, 2110.03117, 2021.
Heejung Bang and Anastasios A. Tsiatis. Estimating medical costs with censored data. Biometrika,
87(2):329-343, 2000.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neurul Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Robert D. Carmichael. On composite numbers p which satisfy the Fermat congruence a=-! (mod p). The American Mathematical Monthly, 19(2):22-27, 1912.
George Casella and Christian P. Robert. Rao-Blackwellisation of sampling schemes. Biometrika, 83(())81194 1996.
Federico Cassano, John Gouwar, Daniel Nguyen, Sydney Nguyen, Luna Phipps-Costin, Donald Pinckney, Ming-Ho Yee. Yangtian Zi, Carolyn Jane Anderson, Molly Q. Feldman, Arjun Guha, Michael Greenberg, and Abhinav Jangda. MultiPL-E: A scalable and extensible approach to benchmarking neural code generation. arXiv, 2208.08227, 2022.
Eunice Chan, Zhining Liu, Ruizhong Qiu, Yuheng Zhang, Ross Maciejewski, and Hanghang Tong. Group fairness via group consensus. The 2024 ACM Conference on Fairness, Accountability, and Trunsparency, pp. 1788-1808, 2024.
Lingjie Chen, Ruizhong Qiu, Siyu Yuan, Zhining Liu, Tianxin Wei, Hyunsik Yoo, Zhichen Zeng, Deqing Yang. and Hanghang Tong. WAPITI: A watermark for finetuned open-source LLMs. arXiv, 2410.06467, 2024.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards. Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings. Matthias Plappert, Fo- tios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob Mc- Grew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained code. arXiv, 2107 2021.
Mingzhe Du, Anh Tuan Luu, Bin Ji, and See-Kiong Ng. Mercury: An efficiency benchmark for LLM code synthesis. arXiv, 2402.07844, 2024.

---

Published as a conference paper at ICLR 2025
Bradley Efron. Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7(1): 1-26, 1979.
Google. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context, 2024.
Cordell Green. Application of theorem proving to problem solving, In Readings in Artificial Intel- ligence, pp. 202-222. Elsevier, 1981.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. ACM SIGPLAN Notices, 46(1):317-330, 2011.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program Synthesis, volume 4 of Founda- tions and Trends@ in Programming Languages. Now Publishers, Inc., 2017.
Xinrui He, Yikun Ban, Jiaru Zou, Tianxin Wei, Curtiss B Cook, and Jingrui He. LLM-Forest: En- semble learning of LLMs with graph-augmented prompts for data imputation. arXiv, 2410.21520, 2024a.
Xinyu He, Jian Kang, Ruizhong Qiu, Fei Wang, Jose Sepulveda, and Hanghang Tong. On the sen- sitivity of individual fairness: Measures and robust algorithms. Proceedings of the 33rd ACM International Conference Information and Knowledge Management, pp. 829-838, 2024b.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, 2021.
Joseph L. Hodges Jr. and Erich L. Lehmann. Estimates of location based on rank tests. The Annals of Mathematical Statistics, 34:598 611, 1963.
Wassily Hoeffding. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics, pp. 293-2233330 325, 1948.
Dong Huang, Jie M. Zhang, Yuhao Qing, and Heming Cui. EffiBench: Benchmarking the efficiency of automatically generated code. arXiv, 2402.02037, 2024.
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gi- anna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie- Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mixtral of experts. arXiv, 2401.04088, 2024.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gul- wani. Neural-guided deductive search for real-time program synthesis from examples. In Inter- national Conference on Learning Representations, 2018.
Yuhang Lai, Chengxi Li, Yiming Wang, Tianyi Zhang, Ruiqi Zhong, Luke Zettlemoyer, Wen-tau Yih, Daniel Fried, Sida Wang, and Tao Yu. DS-1000: A natural and reliable benchmark for data science code generation. In Proceedings of the 40th International Conference on Machine Learning, pp. 18319-18345. PMLR, 2023.
Bowen Li. Wenhan Wu, Ziwei Tang, Lin Shi, John Yang, Jinyang Li, Shunyu Yao, Chen Qian, Binyuan Hui, Qicheng Zhang, et al. DevBench: A comprehensive benchmark for software devel- opment. arxiv, 086004 2024a.
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Mare Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang. Olivier Dehaene, Mishig Davaadorj. Joel Lamy-Poirier João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Yee. Lo- gesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey,
12

---

Published as a conference paper at ICLR 2025
Zhihan Zhang. Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luc- cioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. StarCoder: May the source be with you! arXiv, 2305.06160 2023.
Ting- Wei Li, Qiaozhu Mei, and Jiaqi Ma. A metadata-driven approach to understand graph neural networks. In Advances in Neural Information Processing Systems, volume 36, 2024b.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Push- meet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with AlphaCode. Science, 178(66624:10022-00999 2022.
Xiao Lin, Jian Kang, Weilin Cong, and Hanghang Tong. BeMap: Balanced message passing for fair graph neural network. In Learning on Graphs Conference, 2024a.
Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. BackTime: Backdoor attacks multivariate time series forecasting. In Advances in Neural Information Processing Systems, volume 37, 2024b.
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by ChatGPT really correct? Rigorous evaluation of large language models for code generation. In Advances in Neural Information Systems, volume 36, 2023a.
Lihui Liu, Zihao Wang, Ruizhong Qiu, Yikun Ban, Eunice Chan, Yangqiu Song, Jingrui He, and Hanghang Tong. Logic query of thoughts: Guiding large language models to answer complex logic queries with knowledge graphs. arXiv, 2404.04264, 2024a.
Zhining Liu, Zhichen Zeng, Ruizhong Qiu, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Topological augmentation for class-imbalanced node classification. arXiv, 2308. 14181, 2023b.
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Class-imbalance graph learning without class rebalancing. In Proceedings of the 41st International Conference on Machine Learning, 2024b.
Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Yada Zhu, Hendrik Hamann, and Hanghang Tong. AIM: Attributing, interpreting, mitigating data unfairness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2014-2025, 2024c.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder. Sean Welleck Katherine Hermann, Amir Yazdanbakhsh, and Peter Clark. Self-Refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems, volume 36, 2024.
Zohar Manna and Richard J. Waldinger. Toward automatic program synthesis. Communications of the ACM, 14(3):151-165, 1971.
Meta. Introducing Meta Llama 3: The most capable openly available LLM to date, 2024. URL https://ai. meta. a. www//blg///me
1lama 3/
Daniel Nichols, Joshua H. Davis, Zhaojun Xie, Arjun Rajaram, and Abhinav Bhatele. Can large language models write parallel code? In The 33rd International Symposium on Herf-Perforrmnce Parallel and Distributed Computing. 2024.
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. CodeGen: An open large language model for code with multi-turn program synthesis. In The Eleventh International Conference Learning Representations, 2023.
13

---

Published as a conference paper at ICLR 2025
Changan Niu, Ting Zhang, Chuanyi Li, Bin Luo, and Vincent Ng. On evaluating the efficiency of source code generated by LLMs. Al Foundation Models and Software Engineering (FORGE 24), 2024.
OpenAl. GPT-4 technical report. arXiv, 2303.08774, 2023.
Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1920-1931, 2023.
Ruizhong Qiu and Hanghang Tong. Gradient compressed sensing: query-efficient gradient esti- mator for high-ding sigh-dimensional zeroth-orde order optimization. In Proceedings of the 41st International Conference on Machine Learning. 2024.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combina- torial optimization problems. In Advances in Neural Information P Processing Systems, volume 35, pp. 1-5546,, 2022.
Ruizhong Qiu, Dingsu Wang, Lei Ying, H Vincent Poor, Yifang Zhang, and Hanghang Tong. Re- constructing graph diffusion history from a single snapshot. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1978-1988, 2023.
Ruizhong Qiu, Jun-Gi Jang, Xiao Lin, Lihui Liu, and Hanghang Tong. TUCKET: A tensor time series data structure for efficient and accurate factor analysis over time ranges. Proceedings of the VLDDB Endowment, 17(13), 2024a.
Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the Turing completeness of prompting. arXiv, 2411.01992, 2024b.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code Llama: Open foundation models for code. arXiv, 2308.12950, 2023.
David E. Shaw, William R. Swartout, and C. Cordell Green Inferring LISP programs from ex- amples. In International Joint Conference Artificial Intelligence, volume 75, pp. 260-267, 1975.
Herbert A. Simon. Experiments with a heuristic compiler. Journal of the ACM (JACM), 10(4): 493-506, 1963.
Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 326))652--66. 1985.
Sid-Ahmed-Ali Touati. Towards statistical methodology evaluate program speedups and their optimisation techniques. arXiv, 0932.1035, 2009.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel. Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull. David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux. Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kamhadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. arXiv, 2307. 500.09288, 2023.
Richard J. Waldinger and Richard CT Lee. PROW: A step toward automatic program writing. In Proceedings of the 1st International Joint Conference on Artificial Intelligence, pp. 241-252, 1969.
14

---

Published as a conference paper at ICLR 2025
Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hang- hang Tong. Networked time series imputation via position-avye aware graph enhanced variational autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2256-2268, 2023a.
Yue Wang, Hung Le, Akhilesh Gotmare, Nghi Bui, Junnan Li, and Steven Hoi. Code Open code large language models for code understanding and generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 1069-1088, 2023b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V. Le, Denny Zhou, al. Chain-of-thougg thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pp. 24824-24837, 2022.
Tianxin Wei, Zeming Guo, Yifan Chen, and Jingrui He. NTK-approximating MLP fusion for effi- cient language model fine-tuning, In Proceedings of the 40th International Conference on Ma- chine Learning, pp. 36821-686368 2023.
Tianxin Wei, Bowen Jin, Ruirui Li, Hansi Zeng, Zhengyang Wang. Jianhui Sun, Qingyu Yin. Han- qing Lu, Suhang Wang, Jingrui He, et al. Towards unified multi-modal personalization: Large vision-language models for generative recommendation and beyond. In The Twelfth International Conference on Learning Representations, 2024a.
Tianxin Wei, Ruizhong Qiu, Yifan Chen, Yunzhe Qi, Jiacheng Lin, Wenju Xu, Sreyashi Nag, Ruirui Li, Hanqing Lu, Zhengyang Wang, Chen Luo, Hui Liu, Suhang Wang. Jingrui He, Qi He, and Xianfeng Tang. Robust watermarking for diffusion models: A unified multi-dimensional recipe, 2024b. URL
Ziwei Wu, Lecheng Zheng, Yuancheng Yu, Ruizhong Qiu, John Birge, and Jingrui He. Fair anomaly detection for imbalanced groups arXiv, 2409,10951, 2024.
Zhe Xu, Kaveh Hassani, Si Zhang, Hanqing Zeng, Michihiro Yasunaga, Limei Wang, Donggi Fu, Ning Yao. Bo Long, and Hanghang Tong. Language models are graph learners. arXiv, 2410.02296, 2024a.
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph gener- ation. In Advances in Neural Information Processing Systems, volume 37, 2024b.
Hyunsik Yoo, Zhichen Zeng, Jian Kang, Ruizhong Qiu, David Zhou, Zhining Liu, Fei Wang, Charlie Xu, Eunice Chan, and Hanghang Tong. Ensuring user-side faimess in dynamic recommender systems. In Proceedings of the ACM on Web Conference 2024, pp. 3667-3678, 2024.
Hyunsik Yoo, Ruizhong Qiu, Charlie Xu, Fei Wang, and Hanghang Tong. Generalizable recom- mender system during temporal popularity distribution shifts. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale dataset for complex and cross-domain semantic parsing and text-to-SQL task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp- 3911-3921, 2018.
Zishun Yu, Yunzhe Tao, Liyu Chen, Tao Sun, and Hongxia Yang. B-coder: Value-based deep reinforcement learning for program synthesis. arXiv, 2310.03173, 2023.
Zhichen Zeng. Xiaolong Liu, Mengyue Hang, Xiaoyi Liu, Qinghai Zhou, Chaofei Yang, Yiqun Liu, Yichen Ruan, Laming Chen, Yuxin Chen, et al. InterFormer: Towards effective heterogeneous interaction learning for click rate prediction. arXiv, 2411.09852, 2024a.
Zhichen Zeng, Ruizhong Qiu. Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui He. and Hanghang Tong. Graph mixup approximate Cromov-Wassersten geodesics. In Proceedings of the 4/ International Conference on Machine Learning, 2024b.
Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Zihan Wang, Lei Shen, Andi Wang. Yang Li, Teng Su, Zhilin Yang, and Jie Tang. CodeGeeX: A pre-trained model for code generation with multilingual evaluations on Humaneval-X. arXiv, 2303. 17568, 2023.
15

---

Published as a conference paper at ICLR 2025
Table 5; Nomenclature.
Symbol
Description
k,n
sample sizes number of levels
prompt of problem i j-th code sample for problem correctness of code Ca execution time of code C.,, for the mith test case at level / efficiency score of code Ci2 at level efficiency score of code Cijj
ged
fega
ei
e,,0)
r-th smallest efficiency
among -i.1 6s,n
reference execution time for the mith test level Caam
limit problem
hg
hardness of level
Mi
number of test cases in level |
timcout factor
number of repeats per test
APPENDIX
Nomenclature.
Proof Theorem
B. 1
Proof of unbiasedness].
Proof of variance reduction
C
Evaluation (continued)...
Experimental setting
C.2
Analysis on algorithm design & implementation optimization (continued)
Comparison of efficiency metrics
Comparison with random test cases
19
Comparison with other benchmarks
19
C.6
6
Analysis of hyperparameters ................................
20
Analysis of Bao-Blaakwelllizee
20
8
Evaluation under prompting engineering
D
Concluding remarks).
Scalability benchmark development
22
D.2
Other limitations & future work
25
Code of example problems Table
25
E.
HumanEval problem #10
25
HumanEval problem #36
E
HumanEval problem #40
HumanEval problem #109
HumanEval problem #154
28
A NOMENCLATURE
For reference, the main notations used in this paper are summarized in Table
B PROOF OF THEOREM
In this section, we provide the proofs of unbiasedness and variance reduction, respectively.
16

---

Published as a conference paper at ICLR 2025
B.1 PROOF OF UNBIASEDNESS
First, recall that every efficiency score eij depends only on the corresponding code sample cij- Since c Ci are i.i.d., then given any size-k subset J (i.,...,Jss] n.)..,,,)
E
max eis JEJ
mmax (eis
Ci H
(9)
(2;)
(M)
max (ei,
[i,,
(10)
E
max CiN j=1
(11)
C LLM
E
max Ci,j _
(12)
G. -LMM
Next, recall that probability measures are finite (and thus o-finite). Since efficiency scores 6t, are nonnegative, then by the Fubini-Tonelli theorem and Eq. 12).
Σ
cr(())
E a a
max
City
(13)
(L)(2,)
LLM((s.)
u |
jEJ
E
E
max Eiu jEJ
(14)
m) ||
Ci LLM((z))
k
E
E
max Cij j=1
(15)
JC (L...... [J|=k
A (LM(())
k
E
max eij
(16)
4u G. (MM
B.2 PROOF OF VARIANCE REDUCTION
Note that efficiency scores Cij 2 0 are bounded random variables:
Ci -== h fied
< max feji [=1
(17)
1=1 hi
- -t.gdmmm
max
(18)
T: max (1,,,,m) J
T: T: max(t],, M < 00.
< máx [=1
(19)
This implies that
Var LLMM((
max ea, j=1 < oc.
(20)
Furthermore, note that eff, @h can be expressed as a U-statistic (Hoeffding 1948
1
C((r)
max Ci.j.
(21)
JEJ
JC (1 |J|=
n.....))
Therefore, by Theorem 5.2 of Hoeffding 1948)
Var Co LLM(
ei,rr)
Var
Σ
max Eigj JEJ
(22)
S LLM(())
(1)
JS(I...)) M
Var
max Ci.j 1=1
(23)
71
17

---

Published as a conference paper at ICLR 2025
Table 6: Complete evaluation results on two subsets of problems.
Model
elr@1
p
Algorithan
ef
pus- 10
Design Subset
| <IT@ 100
past@ 100
efr@e
pass8
Implementation Oycimization Subser
e
pass
elT@ 100
Pass 100
Llama 3 708 Inctruct
0.246
0.640
0.306
0.249
0.350
0.750
0.404
0.791
01407
(3880
0.551
0,920
Llama 3 SB Instract
0.201
0.518
0.305
0.724
0.367
0.849
0.313
0.582
0.465
0.806
0.571
0.906
Mistral 8x22B Instrnct
0.225
0.655
0.365
0.837
0.470
0.900
0.376
0.783
0.556
0.914
0.686
0.947
Mixtral Bx7B Instruct
0,124
0.291
0.244
0,681
0.344
0.850
0.248
0.473
0.411
0.699
0.827
Chande Sunmet
0.181
0.577
0.723
Clonde Haiku
0.149
0.692
0.208
0.252
0.775
0.360
0.772
0.889
0,223
Phind Cade lama
0.185
0.554
0.355
0.789
0.849
0.351
0.712
0.567
0.901
0.72
0.988
ChurGPT
0.12
01488
D.3014
0.799
0.483
0.950
0.387
0.715
0.503
0.864
0.633
0.49
Cude Llama 705 Fy tytn
0.018
0.100
0.129
0.519
0.402
0.930
0.076
0.181
0.294
0.627
0.589
0.920
Code Liama 34B Python
0.071
0.292
10.271
0.213
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.841
0.176
0.405
0.576
0.784
0,928
Code Llona 78 Pytlion
0.068
0.202
0.589
0.761
0.165
0.349
0.705
0,63
StrCoode
0.161
0.112
0.247
0,802
CadeGan
0.031
0.133
14146
0.451
0.644
0.099
0.220
0.541
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
CudeGen 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
5o 168
0,043
0.192
12.175
0.509
0.221
0.673
0.10
0.257
0.313
0
0.536
0.845
Mistral 78
0,030
0.152
0.157
0.516
0.319
0.737
0.100
0.327
0.327
0.574
0.565
0.821
Vicusa 138
0.008
0.072
0.056
0.096
0.569
Vicuna 7B
0,241
0,031
0.215
SantaCoder
0.037
0.102
0.101
0.216
0,493
0:069
0.114
0.201
0.308
0,357
0,488
Incoder 6l
0.010
0.050
0.062
0.203
0.112
0.325
0.037
0.062
0,152
0.252
0,320
0.477
Ineader 18
0.003
0.023
0.021
0.110
0.071
0.200
0.018
0.030
0,080
0.129
0.172
0.232
GPTJ
0.021
0.051
0.063
0,146
0.061
0.243
0.025
0.043
0.110
0.167
0.221
0.354
GPT-N 2R
0.063
0.019
0.015
0.098
0.013
0.172
0.007
0.014
0,850
0.084
0.113
0.184
Poly
0.002
0.010
0.018
0.070
0.050
0.163
0.004
0.007
0.034
0.051
0.092
0,122
SubblLM
0.001
0.005
0.039
0.099
0,002
0.003
0.016
0.025
0.074
0,089
C EVALUATION (CONTINUED)
C.I EXPERIMENTAL SETTING
Code generation. For models that are included in Liu al. (2023a), we re-use their gen- crated code samples. For other open-source models, we use temperature 0.8 and top-p 0.95 for sampling on a server with 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 un- der sampling; for largest commercial models, we only use greedy decoding. In our exper- iments, Claude 3 Opus refers to claude-3-opus 3--pps-------- 1aruuus-2222 222240229; Claude 3 Sonnet refers to 3aude-3-sonnee -20240229; Claude 3 Haiku refers to claude-3 GPT-4 Turbo refers to gpt-4-110c 10--11000pppreveee---- GPT- refers to gpt- 9pt-4-0613.
202440377
Code evaluation. We use a = 2, R = 6, h = h2 = 3, h2 = 4, M, = 8, M1 = M2 = M2 = 4. To minimize server workload fluctuations,
evaluation on virtualized cloud servers hosted by Google Cloud (Ubuntu 20.04.6 LTS; Intel Xeon CPU @ 2.20GHz; Python 1.). We use the reference time the slowest test case for each problem further calibrate the execution time of generated code.
Use of existing assets. Our benchmark partially uses problems from HumanEval (Chen al. 2021 MIT License) and prompts from HumanEval+ (Liu et al.) 2023a Apache License). Some reference solutions are modified based on the canonical solutions HumanEval and HumanEval+.
C.2 ANALYSIS ON ALGORITHM DESIGN & IMPLEMENTATION OPTIMIZATION (CONTINUED)
The complete version of Table is shown in Table 6 We can see that observations for Table 6 are similar with those for Table 4
C.3 COMPARISON OF EFFICIENCY METRICS
To demonstrate that our proposed eff@k k metric can rigorously handle right-censored execution times, we empirically compare our eff@k k with a classic metric called speedup (Amdahl 1967). The speedup metric originally defined as the execution time 4,,,, of the reference solution di- vided by the true execution time f. of the generated code. Nonetheless, since generated code
can exceed the time limit T. in our evaluation, the actual definition of speedup is min m.n.........77....
18

---

Published as a conference paper at ICLR 2025
Table 7: Comparison of our proposed efficiency metric and the classic speedup metric. Different rankings are marked in bold font. Under the speedup metric, Mixtral 8x22B Instruct and Llama 70B Instruct even seems to outperform GPT-4.
Rank
eff@@ (ours)
speedup
GPT-4 Turbo
GPT-4 Turbo
2
GPT-4
Mixtral 8x22B Instruct
Llama 70B Instruct
Llama 3 70B Instruct
4
Mixtral 8x22B Instruct
GPT-4
Claude 3 Opus
Claude 3 Opus
6
Phind Code Llama V2
Phind Code Llama V2
7
Claude 3 Haiku
ChatGPT
8
ChatGPT
Claude Haiku
9
Claude 3 Sonnet
Claude 3 Sonnet
10
Llama 8B Instruct
Llama 3 8B Instruct
11
Code Llama 34B Python
Mixtral 8x7B Instruct
12
Mixtral 8x7B Instruct
Code Llama 34B Python
Table 8: Comparison between the random test generator and our expert-written test case generator on problem #31. Better results marked in bold font. Random test cases cannot assess true correctness or true efficiency while our test case generator can.
Generator
Naïve
Fermat
Random
0.91
1.25
Expert (ours)
0.17
0.00
instead, which overestimates efficiency when t.j.d.m > T. We average the speedup test cases in each level, and we use the same hardnesses hn, h2, h3 to weigh the levels.
all
Table shows rankings of LLMs with greedy decoding under metric, respectively. We can see that eff@1 and speedup give very different rankings, especially for top-performing LLMs. In particular, under the speedup metric, Mixtral 8x22B Instruct and Llama 70B Instruct even seems to outperform GPT-4. The unreasonable ranking by the speedup metric is because the speedup metric overestimates efficiency in the presence of right-censored execution time (i.e.. when the program exceeds the time limit), we discussed above. Therefore, it is necessary to propose our eff@ k metric to more rigorously handle right-censored execution time.
eff@ I metric and the speedup
C.4 COMPARISON WITH RANDOM TEST CASES
To further demonstrate the strength of our expert-written test case generators. we provide a case study comparing our strong generator and the random case generator for the problem #31 (de- ciding if number n is prime). We investigate the following two solutions: (i) Naïve: the O(z)- time factorization algorithm, which correct but inefficient; (ii) Fermat: the Fermat primality test (Carmichael) 1912), which is efficient but wrong. We compare the eff@1 metrics of these two so- lutions under random generator and our test case generator, respectively. Results are shown in Table 8 We can see that random test cases cannot assess true correciness true efficiency while our test case generator can. This demonstrates the strength of our expert-written written test case generators.
C.5 COMPARISON WITH OTHER BENCHMARKS
To further demonstrate the difficulty of our problems, provide comparison of evaluation results between EffiBench, Mercury, and our benchamrk ENAMEL. Since Mercury did not evaluate GPT- compare the reported evaluation results of Code Llama 34B
4 or Code Llama 70B Python, Python. The results are shown in Table From the table, we can see that EffiBench's 's and Mercury's LeetCode problems are less challenging to L.MMs than benchmark. This is because LLMs (i)
19

---

Published as a conference paper at ICLR 2025
Table Comparison with other efficiency benchmarks. The most challenging benchmark is marked in bold font. Our benchmark ENAMEL is more challenging than EffiBench and Mercury.
Benchmark
Metric
Result
EffiBenchh
1/NET
0.336
Mercury
Beyond
0.424
ENAMEL (ours)
cff@ I
0.268
Table 10: Analysis of timeout factor a and hardnesses h1, h2, hy on GPT-4 Turbo.
(a) Timeout factor a.
1.5
2.0
2.5
3.0
3.5
e
0.421
0.470
0.502
0.525
0,541
(b) Level-1 hardness hn-
h1
1
2
eff@1
0.428
0.451
0.470
0.486
0.498
(c) Level-2 hardness lu2.
h/2
eff@1
0.474
0.472
0.470
0.469
0.467
(d) Level-3 hardness hg-
h3
2
ef
0.520
0.499
0.483
0.470
0.460
have seen the public solutions on LeetCode (editorials and community solutions) but (ii) have never seen our expert-written efficient solutions.
C.6 ANALYSIS OF HYPERPAAAMETERS
Our benchmark has timeout factor a and hardnesses h1, h22 hi hyperparameters. Regarding the timeout factor a, it represents the tolerance to execution timeout because the execution time limit proportional a. Thus, if one wants to tolerate less efficient code, then they can use larger a. Regarding hardnesses h1, h2, hgg it represents how we weigh each level. Thus, if one wants to focus more on easier levels, they should use a larger h1; if one wants foeus more on harder levels, they should use larger h3. We encourage users to stick to our default hyperparameters
2, hi 3, h2 = 3, h3 = ensure consistency across different test cases and different LLMs. We used these default hyperparameters throughout this work.
To further illustrate how eff@k is influenced by a and h1 h2, ha, we report the eff@ GPT-4 Turbo with greedy decoding under different h1s fiz, and hg. Results are shown in Table IO We can see that eff@ increases as a increases (because alpha represents the tolerance to less efficient hy increases (because weigh
code), that eff@1 increases eff@1 decreases as h2 or hy increases (because we weigh more on a harder levels). These empirical results are consistent with the aforementioned analysis. We hope these empirical results will help users decide hyperparameters based on their preferences about the tolerance to execution time and weights across different levels.
easier level), and that
C.7 ANALYSIS OF RAO- BLACKWELLIZATION
To demonstrate that Rao- Blackwellizztion does reduce the variance the eff@k estimator, we empirically compute the standard deviation of the vanilla eff@k k estimator Eq. and our Rao-
20

---

Published as a conference paper at ICLR 2025
Comparison of the standard deviations of the vanilla cff@k estimator and our Rao- Blackwellized eff@ k estimator. Better results are marked in bold font. Our Rao- Mao-Blackwellized estimator achieves significantly lower standard deviation than the vanilla estimator.
Table 11:
Estimator
k 10
Vanilla
0.20
0.25
Rao-Blackwellized
0.02
0.08
Table 12: Analysis of whether encouraging code efficiency by prompting can improve the efficiency of generated code or not. Results show that encouraging LLMs to generate "the most efficient algorithm" can barely enhance the efficiency of generated code.
(a) Llama 70B Instruct.
(b) Mixtral 8x22B Instruct.
Prompt
eff@1
pass @
Prompt
eff@ 1
pass @
1
Basic
0.421
0.746
Basic
0.408
0.746
Encouraging
0.418
0.746
Encouraging
0.426
0.732
Blackwellized eff@ estimator using the Llama 70B Instruct model. We randomly sample 1000
subsets of size from the 100 generated samples to estimate the standard deviation the vanilla eff@k k estimator. Results are shown in Table [1 We can see that the Rao-Blackwelliin esti- mator achieves much lower standard deviation than the vanilla estimator. Therefore, our Rao- Blackwellized estimator empirically ensures more accurate estimation of eff@k.
C.8 EVALUATION UNDER PROMPTING ENGINEERING
To investigate how prompt engineering affects evaluation results, we provide the following two experiments on prompt engineering.
Experiment I: encouraging efficiency. We use the two strongest open-source LLMs Llama 3 70B Instruct and Mixtral 8x22B Instruct (according to Table We ask the LLM to generate "the most efficient algorithm" and use greedy decoding to obtain outputs. The eff@ 1 results are presented in Table The results show that this prompt engineering cannot enhance code efficiency much, even for such strong LLMs. The eff@ of Mixtral 8x22B Instruct increases a little bit but is still far from the expert level. Interestingly, the cff@ of Llama 70B Instruct even drops a little bit while the pass @1 1 does not change. This suggests that even such strong LLMs lack good understanding of code efficiency.
Experiment II: adaptive prompting. We believe that prompting alone does not fully address the code efficiency issue because this is essentially a fundamental capability limitation of exist- ing I.LMs-effiiien algorithms be non-trivial that existing LLMSs do understand them well. To demonstrate this, we further conduct case study for hard problem #36 under the fol- lowing two settings: (i) Self-Refine prompting (Madaan et al. 2024) and (ii) revealing the efficient algorithm in the prompt. (The efficient algorithm for #36 is dynamic programming over digits in Olog n) time; see Appendix E.2).
For Self- Refine, following Niu et al. 2024) we ask the LLM to "give potential strategy to improve the efficiency of the code" and finally ly "give the optimized version of the same code with the strategy mentioned above." Outputs before and after Self-Refine are shown in Table Before Self- Refine, both Ilama 70B Instruct and Mixtral 8x22B Instruct generate the brute-force algorithm that runs in O(n) time. After Self-Refine both LLMs apply small improvement to the generated code, but the time complexity is still O(n), significantly slower than the efficient algorithm that runs in Ollog π) time. This suggests that both LLMs unable to come up with the efficient algorithm on their own.
To further investigate whether LLMs generate the dynamic programming algorithm here, the following
explicitly reveal the efficient algorithm in the prompt. Specifically, we use "Complete function with dynamic programming over digits" for both LLMss. Raw outputs are shown in
21

---

Published as a conference paper at ICLR 2025
Table 13:
Results of Self-Refine prompting (Madaan al. 2024) for problem #36. Both LLMs unable to come up with the efficient algorithm on their own.
(a) Initial code by Llama 3 70B Instruct.
count
2 for i in range (n)
if i 11 = or i 8 13 = 0: count += str ( count ('71)
return count (b) Self-Relined code by Llama 3 70B Instruct.
import math return sum (str count (1 (() for in range (n) if math .g, 11 13) in (11, 13)
(c) Initial code by Mixtral 8x22B Instruct.
count
2.
for i in range (11, 1):
if i $ 11 - 0 or i 13 -- 0: count str .ount (*) return count
(d) Gelf-RRefined code by Mixtral 8x22B Instruct.
count 0
2.
for i in range (11, n, 11):
count += (i) (tt.:i).cuoooooao count (17()
for i in range
13):
to avoid double counting numbers that are divisibie by potn 11 and count += str .co.tountt (*7*)
if
11
return count
Ilama 70B Instruct fails use dynamic programming: Mixtral 8x22B Instruct uses trivial dynamic programming that is not over digits. We can see that both LLMs still generate inefficient algorithms that run in O(n) time even though we have revealed the efficient O n) algorithm to them. This suggests that they do not have good understanding of this non-trivial dynamic programming.
Tables [4 & 15
From the two case studies above, codes are still inefficient algorithms in O(n) time, which are far from the efficient O(log n) time complexity. Therefore, the code inefficiency is essentially capability limitation of existing LLMs, and therefore we do not expect it to be easily addressed merely via prompting techniques. This also our core motivation for developing this benchmark compare LLMs with human experts. While how to address this capability limitation is beyond the scope of this work, we hope that our work will motivate LLM developers pay more attention this limitation and try to address it in future work.
that, matter whether use (i) (ii), the generated
D CONCLUDDING REMARKS
D.1 SCALABILITY OF BENCHMARK DEVELOPMENT
This work employs human expertise to develop high-quality reference solutions and test case genera- tors. We believe that human expert is necessary to develop high-standard and rigorous benchmark. For example, shown in Table 2 compared with our expert solutions, HumanEval canonical solu- tions achieve only e 1=0.455, and HumanEval+ canonical solutions achieve only eff@ 1=0.513. This shows that their canonical solutions far less efficient than expert-written reference solu- tions. In fact, we have excluded few options when designing the benchmark development method- ology:
22

---

Published as a conference paper at ICLR 2025
Table 14: Raw output of Llama 3 70B Instruct when we reveal the efficient algorithm the prompt.
Here is the Python function that uses dynamic programming over digits to solve the problem:
"python
def fizz_buzz (n: int):
count = 0
for i in range (n)
if i à 11 0 or 8
count +- str (i) count (*71)
return count
Here's s explanation the code:
1. We initialize a variable 'count' to 0, which will store the total count of digit 7 appearances.
2. We iterate over the range of integers from 0 to 'n-1' (since want consider integers less than 'n').
3. For each integer 'i' in the range, we check if it divisible by 11 or 13 using the modulo operator ('8).. If it is, we proceed to the next step.
4. We convert the integer 'i' to string using the ()tr() function, and then use the 'count method count the number of occurrences of the digit '7' in the string.
5. We add the count of digit appearances in the current integer to the overall 'count. variable.
6. Finally, we
the total 'ccunt' the end of the function.
This function has time complexity of ((n), where n is the input integer since we iterate over the range of integers from 0 to 'n-1', The space complexity is (1)) since only use single variable to store the count.
You can test the function with the provided examples to verify that it produces the correct output: "'ython
print (fizz (uzz (501) 0
print (fizz buzz buzz (781)
2
print (fizz_buzz (79)) $
We did not use problems or solutions from online judges (like LeetCode or Codeforces) because their public solutions already in LLMs' pretraining corpuses. For example, Deep AlphaCode (Li et al., (2022) has been trained on many online judges includ- ing Codeforces, CodeChef, HacherEarth, AtCoder, and Aizu. If we evaluate LLMSs these public online judges, then the evaluation results may fail to reflect the L.MSs' true capabilities due
leakage.
We did not crowd-source the benchmark because otherwise it would be hard to guarantee the quality of the benchmark. For example, MBPP (Austin et al. (222 is popular crowd- sourced benchmark, but is known to easier than EvaanEval (Roziere al. 2023).
We did not L.M--gerertedd reference solutions because LLM-generated code still far from expert-level efficiency, as demonstrated in Table
Despite the size 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 still far from generating expert-level efficient code (with eff@ below 0.5). We hope 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 because human expert has carefully verified the comprehensivenes, of the problemset:
23

---

Published as a conference paper at ICLR 2025
Table 15: Raw output of Mixtral 8x22B Instruct when we reveal the efficient algorithm in the prompt.
Here is a Python function that uses dynamic programming to solve the problem:
". ppython
def fizz_buzz (n: int):
"*"Return the number of times the digit appears in integers less than which are divisible by 11 or 13.
Initialize 1ist to store the count of 7s each number dp [0] * n
Base case: the number of 7s in 0 is 0 10
Iterate over the range of numbers for i in range n):
# If the current number is divisible by 11 or 13
if $ 11
i 13
# the last digit of the current number is if & 10 == 7:
# Add to the count of 7 in the current number dpli] dpli 11
else:
# Otherwise, the count of 7 the current number the same as the previous number
dpli] dpli
else:
# the current number is not divisible by or 13, the count of 78 is the sane as the previous number
dpli] = dpli- - 1]
Return the count of in numbers less than return dp(n- 1]
This function works by iterating
the range numbers from to n-1 is, the function checks if the last digit of the number is 7. If it is, the function adds 1 to the count of 78 in the current number. Otherwise, the count of 7s in the current number is the same the previous number. The function then returns the count of 7s in numbers less than n.
and cnecking if each nunber divisible by 11 or 13.
Here are the test cases:
"'python
print (fizz_buzz (50))
Output: 0
print (fizz_buzz )78))
Output: 2
print (fizz_buza (79)) 1
Output: 3
As shown in Figure 2 our benchmark problems have diverse difficulties. For example, seemingly easy problems require non-trivial implementation optimization, and 20 hard problems require advanced algorithms.
As discussed in Section 3.2 our problemset covers wide range of algorithmic knowl- edge (including data structures, dynamic programming. and automata) and a wide range of mathematical knowledge (including linear algebra, combinatorics, and number theory).
24

---

Published as a conference paper at ICLR 2025
That said, still believe that addressing scalability of benchmark development is an important future direction. A possible solution to collaborate with private programming competitions whose solutions are not publicly available.
D.2
OTHER LIMITATIONS & FUTURE WORK
The following are other limitations of this work that we also wish to addressed future work:
This work considers standalone programming problems. Meanwhile, real-world software development typically involves complex dependencies among files. Thus, it is worth study- ing how to generalize our methodology to more complex code generation datasets such as DevBench (Li et al., 2024a).
Although we have used the known best algorithms as reference solutions, it is hard to theoretically guarantee their optimality. Thus, the efficiency score can be greater than the benchmarked code is more efficient than reference solution. Addressing this issue in future work will provide a solid ground for efficiency evaluation.
This work focuses on benchmarking code efficiency without more advanced prompting techniques. Future work can explore how to design prompts to improve the efficiency of LLM -enerrtee code. A possible solution is guide the LLM to analyze the time complexity in the chain of thought (Wei et al. 2022) when generating the code.
While our current benchmark focuses on evaluating time efficiency, we believe that evaluat- ing the space efficiency would be very interesting and important future research direction. For example, EffiBench (Huang et al. 2024) is a time-space joint evaluation benchmark for LLn-erenrttedd code. A potential challenge is how evaluate the time sene-space trade-off. Since many time-efficient algorithms trade space for time (c.g., dynamic programming), a space-optimal algorithm may be less time-efficient, and vice versa. Hence, different refer- ence solutions might be needed for time evaluation and space evaluation, respectively.
How to developing an automatic method measure the time complexity will also be very interesting future direction. Although this might require an independent new study, there are two possible approaches (although both of them have limitations). (i) Time complex- ity prediction: A possible approach is to train an LLM to predict the time complexity of given code sample. However, existing time complexity analyzers (such as LeetCode's analyzer) are known to be inaccurate. We believe that time complexity prediction is in gen- eral difficult for LLMS (and even diffcult for non-expert humans). For example, the Splay tree (Sleator & Tarjan 1985) seems to have O(n) time complexity per operation, but phisticated analysis by the authors shows that it actually has O n) time complexity per operation. (ii) Fitting& time curve: Another possible approach is fit curve of the ning time v.s. the input size to help decide the time complexity. However, we believe that this is in general difficult because polynomial from an exponential function. For example, the Agrawal-Kayal mality test (Agrawal et al. 2004) runs in Ó((lg (logg))2 12) time, so the curve of its running time V.S. n looks extremely like an exponential function for most practical n.
practically infeasible to distinguish high-degree
pri-
E CODE OF EXAMPLE PROBLEMS IN TABLE 1
E. HUMANEVAL PROBLEM #10
Problem description: Find the shortest palindrome that begins with given string (S).
HumanEval+ canonical solution: Enumerate suffixes and check palindromicity. The time com- plexity is O((S)²).
def is return string string[::-1]
str) -> bool:
3 if Is_palindrome (string))
4 return string
5 for 1 in range (len (string)) )
if is_pal iis_palindrome indrone [t:ringi:]]==
return string + (ering(i-1::--
25

---

Published as a conference paper at ICLR 2025
Our expert-written solution: Note that the answer is the concatenation of the border of reversed plus and reversed S, so we can use the Knuth-Morris Prattis-Paatt algorithm to compute the border of reversed 8 plus S. The time complexity is @([S)).
if string:
2 return string
3 reversed_s = string[:: -1]
4 pattern = reversed_s + Ax000 + string
len (pattern)
$ Kntth--ooriss-Paatt
7 fail [0] * (m+1)
8 j =0 0
9 for i in range m):
patternlil
11 while > and pattern[j] et
12
j - fail[jl
13
if if or pattern[0] -- c:
j +-
failli +1
18
return stringl: (stringg Fail[-1]] reversed
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 and count the digits. Since the length of the integer n is (log n), the time complexity is O log n).
cnt 0
for i in range (n)
if 8 11 0 i 13
ent (1ist (filter (lambda c: c "7", si)()))))
5 return ent
Our expert-written solution: Design a dynamic programming over digits. Since 10, 11, and 13 are constants, the time complexity (llog n),, proportional the length of the integer
a
2 while n 0:
3 n, u- div (n, 10)
a.append (u)
len(a)
8 [[1, 111 120 ** 11, 10 131
7 for i in range (m 1):
8 ([(b())
10) $ 11, (b11][1) * 10) & 131)
f CICLEO, 0] for in range (10) for in range (13) for in range range (m) [i-th] [mod 11, mod 13] [digit]: [number
(11)1 for
valid numbers, number of 7's in valid numbers]
10 for u in range (10):
f[0] [u] [u] [[int (w > u), int (u = and w >= 7) for in range (10)
for in range (1, m):
13
for u in range (11):
14
for v in range (13)
fo fli [u] [v][
for
range (10):
17
f1 f(i] b[il[0] w) 11][(v + b[11[1] w) $ 13] [w]
18
#1[0] += 60[0]
f1[1] += [0[1] + æ0[0] int (w == 7)
for in range
21
for v in range (13):
22
fl = [ui] [v]
23
for w in range (1, 10)
[l[w] +- fllw 1]]0]]
[1] fllw 1][1]
26

---

Published as a conference paper at ICLR 2025
[[O, 0, for i in range (m)
for in range (m 1, 0, -1)
28
b[1][0] A alil) $ 11, (e[1)[1) + b[i] [1] - a 11 $ 13, c[1][2] int (a[i] = 7)]
c[i -1] = [[eli]
ans =
for in range (m):
31
if a[i]:
32
= == -
33
== (-elil101) 8 11
for in range (13):
fl [[]][]][]] ans +- f1(1] + f1[0] [[]][2]
36
37
un -
(-e[i][1]) 13
for in range (11):
40
if u0: fl = f[i] [u] [v] [w]
41
42
ans += fi[1] f1(0] e[i][2]
return
E.3 HUMANEVAL PROBLEM #40
Problem description: Check if a list has three distinct elements that sum to O.
HumanEval+ canonical solution: Enumerate triples in and check their sums. The time complex-
ity O(11)).
1 for i in range (len (1)) for in range (len (1)):
for in range (len (1)]
it != j and != k and and 114] return True
1151
L1k] 0:
5
return False
Our expert-written solution: Note that 4 + + equivalent to 4. = LJs so we can enumerate li, store -4; lj in hash set, and check whether la is in the hash set. The time complexity is O((()).
n (1)
2 if n < 3:
3 return False
for i, x in enumerate I: 21):
buf s)t
8 for y 1li + :1:
7 if y in buf:
8 return True
buf.add (-x y)
return False
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 and check if it is sorted. The time complexity is O((a(²).
sorted_ard arr = corted(ar))
if
sorted_arr: return True
3 for in range len (arr))
4 if arr[i:] arr arr[:i] = sorted
5 return True
return False
27

---

Published as a conference paper at ICLR 2025
Our expert-written solution: Note that the desired condition is equivalent to the condition that there is at most I i < la with a, > d((+1) so we can enumerate and check this equivalent condition. The time complexity is O(Jal).
if icn (arr) <= 2: return True 3 ent int (arr[-1) > arr[0])
for a, b zar(arr -1], arr :)):
5 if a b:
ent +-1 if ent 1:
8 return False
9 return True
E.5 HUMANEVAL PROBLEM #154
Problem description: Check any rotation of a string b a substring of string a.
Eval+ canonical solution: Enumerate rotations and brute-force string matching. The
time complexity is ([b[)
if b:
2 return Truc
3 if b "":
4 return True
5 for i in range len (b)):
if bli:] + bl:i] in
7 return True
8 return False
Our expert-written solution: Note that the desired condition is equivalent to the condition that the longest common substring of a and b + b at least [6]. Thus, we can run the suffix automaton w.r.t. b+ compute their longest common substring. Since the suffix automaton of can be built within O(la)) time, the overall time complexity is O[[a] + Bb).
from copy import deepcopy
2 class State: (self, len 0, link 0, next None)
3 def
4 self.len len
self.link link
self.next dict if next is None else deepcopy (next)
7 [State (len 0, link -1)]
8 last =
9 def sam_cxtend(e, last): to build the suffix automaton cur (st)
11 st ap.ep (Stato (len [last] len + 1))
p last
13
while !--1 -1 and not in st [p] next:
st st next [c] - cur
p stlpl. link
18
if p -1:
17
st/cur] else:
.iink I.ink
st next [s]
if st len
st
21
st/cur] link = q
22
else:
clone (st) ap.app (State (len st len 1, link [q] link, next next))
[q]
25
while != -1 and st next [c] = q:
28
st - st [ttpp.111
[c] clone
st [q] link st link clone
28

---

Published as a conference paper at ICLR 2025
last
30 return last
31 for с in a:
32 last = san_oxtendds, last)
= 0
35 for a in + b:
38
while v and c not in st [v] .extt:
37
= st sellv.ling stivl.ien
if in [t(x)neext:
40
v st ne]t [c]
41
1 +- 1
if >= >= len (b)
return True return False
29


Reviews:
[{"review_id": "hgO12ZNVe0", "reviewer": "Reviewer_xNv8", "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.", "questions": "- I understand the theoretical importance of Rao-Blackwellization in this case, but what is the empirical effect? \n\n- 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?\n\n- Does it make sense to also consider space complexity in your benchmarks? For example: \n\nYour optimized solution for #40: \n```\ndef has_triplet_sum_zero(l):\n\tn = len(l)\n\tif n < 3:\n\t\treturn False\n\tfor i, x in enumerate(l[: n - 2]):\n\t\tbuf = set()\n\t\tfor y in l[i + 1 :]:\n\t\t\tif y in buf:\n\t\t\t\treturn True\n\t\tbuf.add(-x - y)\n\treturn False\n```\n\nSuggested solution: \n```\ndef has_triplet_sum_zero(l):\n    l.sort()  # Sort the list first\n    n = len(l)\n    \n    for i in range(n - 2):\n        # Use two pointers to find if there's a pair with sum -l[i]\n        left, right = i + 1, n - 1\n        target = -l[i]\n        \n        while left < right:\n            current = l[left] + l[right]\n            if current == target:\n                return True\n            elif current < target:\n                left += 1\n            else:\n                right -= 1\n    \n    return False\n```\n\nUses two pointers, has the same time complexity, and reduces space complexity from $O(n)$ to $O(1)$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Very nice and clear presentation \n- A clear and rigorous technical treatment of evaluation timeout (right censoring)\n- Human expert solutions as an efficiency target \n- 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. \n- 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kHWFVdRlp4", "reviewer": "Reviewer_t6vW", "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.", "questions": "-\tCan 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?\n-\tFor 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.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-\tEvaluating 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.\n-\tThe 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.\n\nThe 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:\n\n       “Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques”, Sid Touati.\n\nIt 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PsYuFQkRR1", "reviewer": "Reviewer_2JoC", "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.", "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.\n2. 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. Clear and fluent presentation. The metric is carefully designed.\n2. The evaluation is convincing and indicative.", "weaknesses": "1. The method is very manual. It is hard to scale.\n2. 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.\n\nDespite the above, the dataset is still reasonably valuable due to its high quality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jYb7vkvXH5", "reviewer": "Reviewer_1vcL", "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.", "questions": "1. Why is the maximum efficiency value chosen in the eff@k metric, rather than the average efficiency value?\n2. Do the eff@k metric and the existing efficiency metrics give different efficiency rankings for the same LLM-generated code?\n3. How sensitive is the eff@k metric to the hyperparameters?\n4. What is the size of the ENAMEL benchmark suite?\n5. How does the ENAMEL benchmark perform on more competitive datasets, such as the CodeContests dataset?\n6. How does the eff@k metric perform on different test case generation strategies?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Human expert-provided reference implementations for the benchmark are of high quality.\n2. Evaluation provides insights into the efficiency of LLM-generated code.\n3. Clear presentation that is easy to follow.", "weaknesses": "1. The novelty of the proposed eff@k metric is not convincing.\n\nThe authors mention the insufficiencies of existing efficiency benchmarks in C1 and C2.\n\na) 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.\n\nb) 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.\n\n2. Lack of evaluation on different test case generation strategies.\n\nThe 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.\n\n3. Lack of guidance on setting the hyperparameters for the eff@k metric.\n\nThe 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.\n\n4. The benchmark suite is limited only to the HumanEval dataset.\n\nThis 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.\n\na) The authors should provide the size and proportion of the remaining tasks after filtering out the simple tasks.\n\nb) The authors can consider extending the benchmark suite to more competitive datasets, such as the CodeContests dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)