How efficient is LLM-generated code? A rigorous & high-standard benchmark
Under review as a conference paper at ICLR 2025

HOW EFFICIENT IS LLM-GENERATED CODE?
A RIGOROUS & HIGH-STANDARD BENCHMARK

Anonymous authors
Paper under double-blind review

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 frame-
works 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 al-
gorithms 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 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 de-
ficiency is because current LLMs struggle in designing advanced algorithms and
are barely aware of implementation optimization. To ensure anonymity, we will
publish our benchmark upon acceptance of this paper.

1

INTRODUCTION

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

Apart from correctness, however, efficiency is another important measure of code quality and has
been overlooked in existing evaluations. Code efficiency is crucial in real-world applications
for boosting system throughput, improving algorithm latency, and reducing energy consumption.
Nonetheless, not until very recently have a 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-generated code,
and a number of fundamental challenges remain uncharted and open:

(C1) Right-censored execution time. When code execution is early terminated due to time
limit, its actual execution time is unknown; this is right censoring in statistics (Bang &
Tsiatis, 2000). For instance, if the generated code contains an infinite loop, the right-

1

000
001

002
003
004
005
006
007

008
009
010
011
012
013

014
015
016
017
018

019
020
021
022
023
024

025
026
027
028
029
030

031
032
033
034
035
036

037
038
039
040
041

042
043
044
045
046
047

048
049
050
051
052
053

Under review as a conference paper at ICLR 2025

054
055

056
057
058
059
060
061

062
063
064
065
066
067

068
069
070
071
072

073
074
075
076
077
078

079
080
081
082
083
084

085
086
087
088
089
090

091
092
093
094
095

096
097
098
099
100
101

102
103
104
105
106
107

Figure 1: Illustration of our ENAMEL framework with HumanEval problem #55 (computing the
n-th Fibonacci number). Our level-based evaluation clearly differentiates the three algorithms: (i) a
na¨ıve algorithm that needs 2Θ(n) recursions, (ii) a dynamic programming algorithm that needs Θ(n)
iterations, and (iii) an efficient doubling algorithm that needs only Θ(log n) iterations.

censored execution time will be clipped to 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., 2021) to characterize the efficiency given sample sizes k. Existing work either uses
only one code sample (Niu et al., 2024) or averages the efficiency scores of code samples
(Huang et al., 2024; Du et al., 2024); therefore, they fall short in capturing the relationship
between code efficiency and the sample size k.

(C3) Algorithm design & implementation optimization. A good reference of efficiency
should be the most efficient code, which often needs advanced algorithms and implementa-
tion optimization that can be highly non-trivial even for human programmers. Prior works
either use existing canonical solutions provided in the dataset as the reference (Niu et al.,
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 is the Fermat primality
test, which is known to have nontrivial counterexamples (Carmichael, 1912). Thus, we
need to use strong test cases to filter out wrong code and evaluate efficiency only with
correct code. Niu et al. (2024) rely on existing test cases provided by the dataset, but Liu
et al. (2023) have shown that those tests are not strong enough to fully detect wrong code.

(C5) Worst-case efficiency. Some suboptimal algorithms can appear efficient on random inputs
despite their inefficiency on strong inputs. For example, if we search for a length-m sub-
string in a length-n string, a brute-force algorithm takes only Θ(n + 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), a 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., 2023), excluding trivial problems with Θ(1) time com-
plexity. With a wide spectrum of easy to hard problems, we are able to comprehensively evaluate
how capable the LLM is to generate efficient code for various problems. Our main contributions are
as follows:

• Efficiency metric & its unbiased, variance-reduced estimator. We propose a new ef-
ficiency metric called eff@k, which generalizes the pass@k metric from correctness to

2

deffib(n):ifn == 0:return0ifn == 1:return1returnfib(n -1) + fib(n -2)HumanEval:2Θ(n)recursionsdeffib(n):a, b = 0, 1for_ inrange(n):a, b = b, a + breturnaGPT-4Turbo:Θ(n)iterationsdeffib(n):ifn == 0: return0a, b = 0, 1forn inbin(n)[3:]:a, b = a * a + b * b, b * (a * 2+ b)ifn == '1':a, b = b, a + breturnbOurs:Θ(logn)iterationsLevel0✓✓✓✓✓✓✓✓Level1✓✓✓✓Level2✓✓✓✓Level3✓✓✓✓Level0✓✓✓✓✓✓✓✓Level1✓✓✓✓Level2✗Level3Level0✓✓✓✓✓✓✓✓Level1✗Level2Level3Testcaseskipped✓Testcasepassed✗Timelimitexceededei,j=0.0Scoreei,j=0.3Scoreei,j=1.0ScoreUnder review as a conference paper at ICLR 2025

108
109

110
111
112
113
114
115

116
117
118
119
120
121

122
123
124
125
126

127
128
129
130
131
132

133
134
135
136
137
138

139
140
141
142
143
144

145
146
147
148
149

150
151
152
153
154
155

156
157
158
159
160
161

efficiency. Our eff@k metric properly handles right-censored execution time (C1) and pre-
cisely characterizes the efficiency under different sample sizes k (C2). Furthermore, we
derive an unbiased, variance-reduced estimator of our eff@k via Rao–Blackwellization,
and provide a numerically stable implementation of our estimator.

• Efficient reference solutions. To set a high-standard for efficiency evaluation, we employ
a human expert to design best algorithms and implementations as our reference solutions of
efficiency (C3). Many of our reference solutions are much more efficient than the canonical
solutions in HumanEval and HumanEval+. For example, the canonical solution of comput-
ing the n-th Fibonacci number in HumanEval+ needs Θ(n) iterations while our reference
solution needs only Θ(log n) iterations.

• Strong test case generators. To ensure a rigorous evaluation, we employ a human expert
to curate strong test case generators that cover both corner cases to filter out wrong code
(C4) and worst cases to differentiate suboptimal algorithms (C5). Under our generated
strong test cases, 11 canonical solutions in HumanEval and 4 in HumanEval+ are found
wrong, and 34 in HumanEval and 27 in HumanEval+ exceed the time limit.

• Rigorous & high-standard benchmark. We open-source ENAMEL, a rigorous and high-
standard benchmark for evaluating the capability of LLMs in generating efficient code. An
extensive study across 30 popular LLMs using our benchmark ENAMEL shows that LLMs
still fall short of generating expert-level efficient code. Benchmarked with our expert-
written reference solutions, the strongest commercial LLM GPT-4 has low eff@1=0.454
despite its high pass@1=0.831. Furthermore, using two subsets of our problem set, we
show that their deficiency is because LLMs struggle in designing advanced algorithms and
are barely aware of implementation optimization.

2 EVALUATION FRAMEWORK

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

2.1 LEVEL-BASED EVALUATION

To achieve a fine-grained evaluation of efficiency, we aim not only to let the most efficient code pass
but also to give a continuous score for less efficient code generated by LLMs. A na¨ıve idea is to
time each code under large-scale inputs. However, because we have to set a time limit per test case
to prevent unacceptably long execution time, if we used only large-scale inputs to evaluate every
code, most of the less efficient code would time out, making it impossible to distinguish different
efficiencies. For example, for the problem and code samples in Fig. 1, if we used large-scale inputs
that allow only the code with Θ(log n) iterations to pass, then we would not be able to give different
scores for the code with 2Θ(n) 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 Ti while the input scale increases with the level l (i.e., the L-th level has the largest input scale).
Input scales are carefully designed by a human expert so that algorithms with different efficiencies
can pass different numbers of levels. Besides levels 1, . . . , L, we use an additional level 0 to filter
out wrong code using small strong inputs. For each problem i, each level l = 0, 1, . . . , L has Ml test
cases. If the output of the code does not match the expected output in any test case or does not pass
level 0, we will not count it into the pass@k metric. If the code passes level 0 but exceeds the time
limit in some level l ≥ 1, we will still count it into the pass@k metric but will skip the remaining
levels (i.e., we assume that it will also exceed the time limit for the remaining levels because the
input scale increases with the level l). Finally, we compute its efficiency score according to §2.2.

Example. Fig. 1 illustrates our evaluation framework via HumanEval problem #55 (computing
the n-th Fibonacci number). Level 0 has n ≤ 10 so that the na¨ıve recursive algorithm (in 2Θ(n)
recursions) can pass; level 1 has n ≤ 30 so that the dynamic programming algorithm (in Θ(n)
iterations) can pass; level 2 has n ≤ 9000 so that the matrix exponentiation algorithm (in Θ(log n)
iterations by repeated squaring) can pass; level 3 has n ≤ 10000 so that the doubling algorithm (still

3

Under review as a conference paper at ICLR 2025

in Θ(log n) iterations yet with a 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 t and only know that t ≥ T . For instance, if the generated code contains an infinite loop,
the right-censored execution time will be clipped to the time limit while the actual execution time
should be infinity. Existing evaluations (Niu et al., 2024; 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,j of problem i and for each level l, if the code ci,j is correct, we
define the efficiency score fi,j,l by

fi,j,l :=

(Ti − max{ti,j,l,m}Ml
i,l,m}Ml

Ti − max{t∗

m=1

m=1)+

,

(1)

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

Finally, since each level has a distinct hardness, we define the efficiency score ei,j of a code sample
ci,j of problem i by a weighted average over levels 1, . . . , L:

ei,j :=

(cid:40) (cid:80)L

l=1 hl·fi,j,l
(cid:80)L
l=1 hl

0,

,

if code ci,j is correct;
otherwise.

(2)

where hyperparameters hl > 0 represent the hardness of each level l.

2.3 EFFICIENCY METRIC FOR AN LLM

The pass@k metric (Chen et al., 2021) is the standard metric in correctness evaluation, which means
the probability that at least one among k generated code samples is correct. Meanwhile, existing
efficiency evaluations (Niu et al., 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.

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

passi@k =

P
ci,1,...,ci,k∼LLM(zi)

{∃1 ≤ j ≤ k : gi,j = 1} =

P
ci,1,...,ci,k∼LLM(zi)

(cid:110) k

max
j=1

(cid:111)

gi,j = 1

=

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)

.

gi,j

4

(3)

(4)

162
163

164
165
166
167
168
169

170
171
172
173
174
175

176
177
178
179
180

181
182
183
184
185
186

187
188
189
190
191
192

193
194
195
196
197
198

199
200
201
202
203

204
205
206
207
208
209

210
211
212
213
214
215

Under review as a conference paper at ICLR 2025

Algorithm 1 Numerically stable (cid:99)effi@k
Input: score list [ei,1, . . . , ei,n]; the target k
Output: the estimated (cid:99)effi@k
1: λn ← k
n
2: for r ← n − 1, n − 2, . . . , k do
λr ← λr+1 · (cid:0)1 − k−1
3:
4: end for
5: [ei,(1), . . . , ei,(n)] ← sort([ei,1, . . . , ei,n])
6: return (cid:80)n

r=k λrei,(r)

(cid:1)

r

This equivalent formula in Eq. equation 4 no longer relies on the Boolean nature of code correctness
and naturally extends to our continuous efficiency score. Hence, we define our efficiency metric
effi@k by the expected maximum efficiency score of k independent code samples:

effi@k :=

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)
,

ei,j

(5)

where ei,j denotes the efficiency score of code ci,j defined in §2.2. Our metric effi@k precisely
characterizes the relation between code efficiency and sample size k via the maximum over k code
samples while the metric in previous works (Niu et al., 2024; Huang et al., 2024) is simply an
average over code samples and cannot describe its relation with sample size k.

However, estimating effi@k na¨ıvely by generating k code samples and calculating their maxi-
mum ei,j can have high variance (Chen et al., 2021). To reduce the variance of effi@k esti-
mation, we employ two advanced variance reduction techniques: (i) bootstrap (Efron, 1979) and
(ii) Rao–Blackwellization (Casella & Robert, 1996). Specifically, for n ≥ k i.i.d. code samples
ci,1, . . . , ci,n ∼ LLM(zi), the bootstrap estimator is the average of maxj∈J ei,j over multiple ran-
dom subsets J ⊆ {1, . . . , n} with |J| = k, and we obtain our final estimator (cid:99)effi@k by Rao–
Blackwellizing the boostrap estimator (i.e., taking expectation over the random subset J):

(cid:99)effi@k :=

(cid:104)
max
j∈J

(cid:105)

=

ei,j

E
J⊆{1,...,n}
|J|=k

n
(cid:88)

r=k

(cid:1)
(cid:1) ei,(r).

(cid:0)r−1
k−1
(cid:0)n
k

(6)

(cid:1) denotes the binomial
where ei,(r) denotes the r-th smallest score among ei,1, . . . , ei,n, and (cid:0)n
coefficient. Furthermore, we show in Theorem 1 that our Rao–Blackwellized bootstrap estimator
(cid:99)effi@k is unbiased and does reduce variance.
Theorem 1. Suppose that problem i has time limit Ti < ∞ and reference execution times t∗
Ti. Under the randomness of code generation and execution, for n ≥ k, we have:

i,l,m <

k

• Unbiasedness:

E
ci,1,...,ci,n∼LLM(zi)

(cid:20) n
(cid:88)

r=k

(cid:21)

(cid:1)
(cid:1) ei,(r)

(cid:0)r−1
k−1
(cid:0)n
k

=

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)
;

ei,j

(7)

• Variance reduction:

Var
ci,1,...,ci,n∼LLM(zi)

(cid:20) n
(cid:88)

r=k

(cid:21)

(cid:1)
(cid:1) ei,(r)

(cid:0)r−1
k−1
(cid:0)n
k

≤

k
n

·

Var
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)
.

ei,j

(8)

Proof is in §A. Due to unbiasedness, we will use effi@k and (cid:99)effi@k interchangeably from now on.
As a remark, na¨ıvely computing the coefficients (cid:0)r−1
(cid:1) in (cid:99)effi@k can result in numerical insta-
bility. Instead, we propose a numerically stable implementation of (cid:99)effi@k, presented in Algorithm 1.
Finally, we define our efficiency metric eff@k by averaging effi@k over all problems i.

(cid:1)/(cid:0)n

k−1

k

5

216
217

218
219
220
221
222
223

224
225
226
227
228
229

230
231
232
233
234

235
236
237
238
239
240

241
242
243
244
245
246

247
248
249
250
251
252

253
254
255
256
257

258
259
260
261
262
263

264
265
266
267
268
269

Under review as a conference paper at ICLR 2025

270
271

272
273
274
275
276
277

278
279
280
281
282
283

284
285
286
287
288

289
290
291
292
293
294

295
296
297
298
299
300

301
302
303
304
305
306

307
308
309
310
311

312
313
314
315
316
317

318
319
320
321
322
323

Table 1: A sample of hard problems in our problemset. Our expert-written reference solutions are
much more efficient than HumanEval+ canonical solutions. (See Appendix E for code.)

ID

Problem Description

#10

#36

#40

#109

#154

Find the shortest palindrome that
begins with a given string S

Count digit 7’s in positive integers
< n that are divisible by 11 or 13

Check if a list l has three distinct
elements that sum to 0

Check if a list a can be made non-
decreasing using only rotations

Check if any rotation of a string b is
a substring of a string a

HumanEval+ Solution
O(|S|2): Enumerate suffixes
and check palindromicity

Θ(n log n): Enumerate inte-
gers < n and count the digits
O(|l|3): Enumerate triples in
l and check their sums
O(|a|2): Enumerate the rota-
tions of a and check
O(|b|2|a|): Enumerate rota-
tions and run string matching

Our Expert Solution

Θ(|S|): Use Knuth–Morris–
Pratt w.r.t. reversed S plus S

Θ(log n): Design a dynamic
programming over digits
O(|l|2): Use a hash set and
enumerate pairs in l

O(|a|): Check if the list a
has at most one inversion

O(|a| + |b|): Run the suffix
automaton of a w.r.t. b + b

3 BENCHMARK DEVELOPMENT

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

3.1 PROBLEM SELECTION

To achieve a comprehensive evaluation of efficiency, we aim to create a problemset that contains
high-quality problems with a broad range of difficulties. Thus, following HumanEval+ (Liu et al.,
2023), we re-use the problems from the HumanEval dataset (Chen et al., 2021) due to their high
quality and diverse difficulties. We remark that even seemingly easy problems can become hard
if the input scale increases. Although most HumanEval problems seem easy, we find that quite
a number of them become hard and require advanced algorithms under large-scale inputs. For
instance, although the common algorithm for problem #55 (computing the n-th Fibonacci number)
is dynamic programming with Θ(n) iterations, a large n requires an advanced doubling algorithm
that needs only Θ(log n) iterations based on a 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 a wide spectrum of easy to hard problems, thus enabling a comprehensive
evaluation of how capable the LLM is in generating efficient code under various difficulties. Table 1
exhibits a sample of hard problems in our problemset.

3.2 EFFICIENT REFERENCE SOLUTIONS

An ideal reference of efficiency should be the most efficient code, which often needs advanced 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 our algorithm design stage and implementation optimization stage below.

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 an efficient deterministic algorithm exists. Our reference solutions
involve many advanced algorithms (such as automata, data structures, and dynamic programming)

6

Under review as a conference paper at ICLR 2025

324
325

326
327
328
329
330
331

332
333
334
335
336
337

338
339
340
341
342

343
344
345
346
347
348

349
350
351
352
353
354

355
356
357
358
359
360

361
362
363
364
365

366
367
368
369
370
371

372
373
374
375
376
377

and a wide range of mathematical knowledge (including number theory, combinatorics, and linear
algebra). See Table 1 for a sample of hard problems and our reference solutions.

Implementation optimization. Even a single algorithm can have multiple functionally equivalent
implementations with different efficiencies. Implementation optimization is to improve code 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., 2023), 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 a remark, we only use absolutely
valid corner cases and try our best to avoid those whose validity is unclear due to the ambiguity in
problem description.

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

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 B.1 for experi-
mental setting.

4.1 MAIN RESULTS & ANALYSIS

Name

eff@1

pass@1

HumanEval
HumanEval+

ENAMEL (ours)

0.455
0.513

1.000

0.908
0.972

1.000

Table 3 shows pass@k 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>0.5,
and most LLMs cannot even reach eff@1>0.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 on code correctness while overlooking code efficiency,
partially due to the lack of a rigorous evaluation framework for code efficiency. Surprisingly, LLMs
that are good at generating correct code are not always equally good at generating efficient code. For
instance, GPT-4 Turbo has higher eff@1 than GPT-4 although GPT-4 has higher pass@1 than GPT-4
Turbo. A possible reason is that na¨ıve algorithms are easier to be generated correctly but are less
efficient than advanced algorithms. Besides that, we see that the performance gap between open-
source and commercial models are closing in terms of generating efficient code. For example, Phind
Code Llama V2 achieves eff@100=0.723, which is even higher than eff@100=0.690 of ChatGPT.

7

Under review 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.

Model

GPT-4 Turbo
GPT-4
Llama 3 70B Instruct
Llama 3 8B Instruct
Mixtral 8x22B Instruct
Mixtral 8x7B Instruct
Claude 3 Opus
Claude 3 Sonnet
Claude 3 Haiku
Phind Code Llama V2
ChatGPT
Code Llama 70B Python
Code Llama 34B Python
Code Llama 13B Python
Code Llama 7B Python
StarCoder
CodeGen 16B
CodeGen 6B
CodeGen 2B
CodeT5+ 16B
Mistral 7B
Vicuna 13B
Vicuna 7B
SantaCoder
Incoder 6B
Incoder 1B
GPT-J
GPT-Neo 2B
PolyCoder
StableLM 7B

Greedy

Sampling

eff@1

pass@1

eff@1

pass@1

eff@10

pass@10

eff@100

pass@100

0.470
0.454
0.421
0.344
0.408
0.266
0.401
0.345
0.386
0.394
0.364
0.264
0.268
0.216
0.247
0.195
0.169
0.193
0.153
0.160
0.152
0.123
0.061
0.100
0.091
0.066
0.083
0.043
0.037
0.020

0.796
0.831
0.746
0.592
0.746
0.444
0.789
0.662
0.739
0.683
0.683
0.500
0.458
0.408
0.373
0.352
0.310
0.296
0.254
0.317
0.275
0.176
0.099
0.141
0.127
0.092
0.106
0.056
0.049
0.021

—
—
0.438
0.345
0.407
0.279
—
0.365
0.382
0.372
0.374
0.082
0.226
0.204
0.180
0.134
0.122
0.111
0.098
0.130
0.116
0.080
0.054
0.088
0.054
0.031
0.039
0.019
0.021
0.007

—
—
0.747
0.564
0.721
0.456
—
0.677
0.730
0.638
0.673
0.177
0.405
0.372
0.320
0.236
0.219
0.188
0.168
0.250
0.222
0.125
0.081
0.126
0.078
0.043
0.058
0.027
0.029
0.010

—
—
0.526
0.500
0.575
0.436
—
0.498
0.478
0.584
0.557
0.326
0.511
0.487
0.432
0.355
0.326
0.298
0.264
0.343
0.335
0.188
0.149
0.204
0.164
0.100
0.119
0.069
0.067
0.039

—
—
0.836
0.770
0.870
0.689
—
0.814
0.831
0.862
0.847
0.610
0.786
0.732
0.663
0.557
0.512
0.455
0.389
0.551
0.541
0.310
0.231
0.298
0.242
0.139
0.166
0.096
0.084
0.048

—
—
0.575
0.595
0.704
0.542
—
0.594
0.529
0.723
0.690
0.614
0.711
0.714
0.643
0.542
0.536
0.491
0.421
0.551
0.557
0.319
0.283
0.349
0.319
0.191
0.221
0.127
0.121
0.097

—
—
0.880
0.874
0.923
0.810
—
0.887
0.861
0.935
0.937
0.908
0.934
0.899
0.837
0.787
0.761
0.694
0.602
0.785
0.791
0.537
0.423
0.470
0.439
0.241
0.331
0.181
0.155
0.123

Table 4: Evaluation on two subsets of problems. LLMs struggle in designing advanced algorithms
and are largely unaware of implementation optimization. (See Appendix B.2 for the complete table.)

Model

eff@1

pass@1

Llama 3 70B Instruct
Llama 3 8B Instruct
Mixtral 8x22B Instruct
Mixtral 8x7B Instruct
Claude 3 Sonnet
Claude 3 Haiku
Phind Code Llama V2
ChatGPT
Code Llama 70B Python
Code Llama 34B Python
Code Llama 13B Python
Code Llama 7B Python

0.246
0.201
0.225
0.124
0.184
0.149
0.185
0.120
0.018
0.071
0.058
0.068

0.660
0.518
0.635
0.391
0.577
0.692
0.554
0.488
0.100
0.293
0.212
0.202

Algorithm Design Subset
eff@10

pass@10

eff@100

pass@100

eff@1

Implementation Optimization Subset
eff@100

pass@10

eff@10

pass@1

0.306
0.303
0.363
0.244
0.328
0.208
0.353
0.304
0.129
0.271
0.276
0.231

0.749
0.724
0.837
0.681
0.804
0.752
0.789
0.799
0.519
0.713
0.665
0.589

0.359
0.367
0.470
0.344
0.450
0.266
0.401
0.483
0.402
0.425
0.478
0.393

0.750
0.849
0.900
0.850
0.950
0.775
0.849
0.950
0.950
0.881
0.844
0.761

0.404
0.313
0.376
0.248
0.358
0.360
0.351
0.337
0.076
0.197
0.176
0.165

0.791
0.582
0.783
0.473
0.723
0.772
0.712
0.715
0.181
0.415
0.405
0.349

0.497
0.468
0.556
0.411
0.475
0.465
0.567
0.508
0.294
0.473
0.476
0.417

0.869
0.806
0.914
0.699
0.846
0.889
0.901
0.864
0.627
0.804
0.784
0.703

0.551
0.571
0.686
0.515
0.548
0.513
0.732
0.633
0.589
0.687
0.715
0.620

pass@100

0.920
0.906
0.947
0.827
0.893
0.923
0.968
0.949
0.920
0.949
0.928
0.863

4.2 ANALYSIS ON ALGORITHM DESIGN & IMPLEMENTATION OPTIMIZATION

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

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

Implementation optimization. We use a subset of 75 problems to evaluate the capability in imple-
mentation optimization. For these problems, the optimized implementation can have much higher
efficiency than na¨ıve implementations. Table 4 shows that the generated code has low efficiency
when the sample size is small although the efficiency improves a lot as the sample size increases.

8

378
379

380
381
382
383
384
385

386
387
388
389
390
391

392
393
394
395
396

397
398
399
400
401
402

403
404
405
406
407
408

409
410
411
412
413
414

415
416
417
418
419

420
421
422
423
424
425

426
427
428
429
430
431

Under review as a conference paper at ICLR 2025

432
433

434
435
436
437
438
439

440
441
442
443
444
445

446
447
448
449
450

451
452
453
454
455
456

457
458
459
460
461
462

463
464
465
466
467
468

469
470
471
472
473

474
475
476
477
478
479

480
481
482
483
484
485

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

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 is 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 passi@1 and effi@1 (av-
eraged over LLMs under greedy generation) in Fig. 2, where passi@1 represents the difficulty of
straightforward implementation, and effi@1 represents the difficulty of efficient implementation.
Fig. 2 demonstrates that our problemset comprises a wide spectrum of easy to hard problems, thus
enabling a comprehensive evaluation of capability of LLMs under various difficulties. Notably, some
problems i have high passi@1 but low effi@1 because they have a seemingly easy task with a non-
trivial efficient algorithm / implementation. For example, problem #98 (counting uppercase vowels
at even indices) has high passi@1=0.50 but low effi@1=0.03 because an efficient implementation
for #98 needs a clever use of builtin functions rather than straightforward counting.

5 RELATED WORK

Most of existing benchmarks for LLM-based code generation, including Spider (Yu et al., 2018), Hu-
manEval (Chen et al., 2021), MBPP (Austin et al., 2021), APPS (Hendrycks et al., 2021), MultiPL-E
(Cassano et al., 2022), DS-1000 (Lai et al., 2023), HumanEval-X (Zheng et al., 2023), EvalPlus (Liu
et al., 2023), and so on, focus on code correctness. Not until very recently have a few benchmarks
(Nichols et al., 2024; Niu et al., 2024; Huang et al., 2024; Du et al., 2024) been proposed to evaluate
code efficiency, and a number of fundamental challenges still remain uncharted and open which this
work aims to address, including how to rigorously handle right-censored execution time, sample
size, algorithm/implementation optimization, correctness, and worst-case efficiency. For instance,
classic efficiency metrics such as speedup (see, e.g., Amdahl, 1967; Touati, 2009) are not designed
for right-censored execution time and thus overestimates efficiency when an execution times out.

Please refer to Appendix C for related work on code generation.

6 CONCLUSION

We have developed a rigorous and high-standard benchmark ENAMEL for evaluating the 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 LLMs still fall short of generating expert-level efficient code. We hope LLM developers
pay more attention to efficiency of generated code and build more powerful LLMs to reach expert
level in the future. Please refer to Appendix D for limitations and future work.

9

Problem i (sorted by effi@1)0.00.20.40.60.81.0Metric Valuepassi@1effi@1Under review as a conference paper at ICLR 2025

486
487

488
489
490
491
492
493

494
495
496
497
498
499

500
501
502
503
504

505
506
507
508
509
510

511
512
513
514
515
516

517
518
519
520
521
522

523
524
525
526
527

528
529
530
531
532
533

534
535
536
537
538
539

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
In Proceedings of the April 18-20, 1967, spring Joint Computer Conference, pp.

capabilities.
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:2108.07732, 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,
In Advances in
Ilya Sutskever, and Dario Amodei. Language models are few-shot learners.
Neural Information Processing Systems, volume 33, pp. 1877–1901, 2020.

Robert D. Carmichael. On composite numbers p which satisfy the Fermat congruence ap−1 ≡ 1

(mod p). The American Mathematical Monthly, 19(2):22–27, 1912.

George Casella and Christian P. Robert. Rao-Blackwellisation of sampling schemes. Biometrika,

83(1):81–94, 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.

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 on code. arXiv:2107.03374, 2021.

Mingzhe Du, Anh Tuan Luu, Bin Ji, and See-Kiong Ng. Mercury: An efficiency benchmark for

LLM code synthesis. arXiv:2402.07844, 2024.

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.

10

Under review as a conference paper at ICLR 2025

540
541

542
543
544
545
546
547

548
549
550
551
552
553

554
555
556
557
558

559
560
561
562
563
564

565
566
567
568
569
570

571
572
573
574
575
576

577
578
579
580
581

582
583
584
585
586
587

588
589
590
591
592
593

Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program Synthesis, volume 4. Now Pub-

lishers, Inc., 2017. In Foundations and Trends® in Programming Languages.

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–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´elio Renard Lavaud, Lucile Saulnier, Marie-
Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le
Scao, Th´eophile Gervet, Thibaut Lavril, Thomas Wang, Timoth´ee 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:2403.08604, 2024.

Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao
Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii,
Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj, Joel Lamy-Poirier, Jo˜ao
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,
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˜noz Ferrandis, Sean Hughes,
Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. StarCoder: May the source
be with you! arXiv:2305.06161, 2023.

Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, R´emi 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, 378(6624):1092–1097, 2022.

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, 2023.

11

Under review as a conference paper at ICLR 2025

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.com/blog/meta-llama-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 High-Performance
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 on Learning Representations, 2023.

Changan Niu, Ting Zhang, Chuanyi Li, Bin Luo, and Vincent Ng. On evaluating the efficiency of
source code generated by LLMs. In AI Foundation Models and Software Engineering (FORGE
’24), 2024.

OpenAI. GPT-4 technical report. arXiv:2303.08774, 2023.

Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi
Adi, Jingyu Liu, Tal Remez, J´er´emy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton,
Manish Bhatt, Cristian Canton Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre D´efossez,
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-
In International Joint Conference on Artificial Intelligence, volume 75, pp. 260–267,

amples.
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, 32(3):652–686, 1985.

Sid-Ahmed-Ali Touati. Towards a statistical methodology to evaluate program speedups and their

optimisation techniques. arXiv:0902.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 Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic,
Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models.
arXiv:2307.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.

12

594
595

596
597
598
599
600
601

602
603
604
605
606
607

608
609
610
611
612

613
614
615
616
617
618

619
620
621
622
623
624

625
626
627
628
629
630

631
632
633
634
635

636
637
638
639
640
641

642
643
644
645
646
647

Under review as a conference paper at ICLR 2025

Yue Wang, Hung Le, Akhilesh Gotmare, Nghi Bui, Junnan Li, and Steven Hoi. CodeT5+: 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, 2023.

Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V. Le, Denny
Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. In Advances
in Neural Information Processing Systems, volume 35, pp. 24824–24837, 2022.

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
human-labeled 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.

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.

13

648
649

650
651
652
653
654
655

656
657
658
659
660
661

662
663
664
665
666

667
668
669
670
671
672

673
674
675
676
677
678

679
680
681
682
683
684

685
686
687
688
689

690
691
692
693
694
695

696
697
698
699
700
701

Under review as a conference paper at ICLR 2025

Table 5: Nomenclature.

Symbol Description

k, n
L

zi
ci,j
gi,j
ti,j,l,m
fi,j,l
ei,j
ei,(r)
t∗
i,l,m
Ti
hl
Ml
α
R

sample sizes
number of levels

prompt of problem i
j-th code sample for problem i
correctness of code ci,j
execution time of code ci,j for the m-th test case at level l
efficiency score of code ci,j at level l
efficiency score of code ci,j
r-th smallest efficiency score among ei,1, . . . , ei,n

reference execution time for the m-th test case at level l
time limit of problem i
hardness of level l
number of test cases in level l
timeout factor
number of repeats per test case

APPENDIX

A Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.1 Proof of unbiasedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.2 Proof of variance reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
B Evaluation (continued) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.1 Experimental setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.2 Analysis on algorithm design & implementation optimization (continued) . . . . . . . . 16
B.3 Comparison of efficiency metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.4 Comparison with random test cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
B.5 Analysis of hyperparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
B.6 Analysis of Rao–Blackwellization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
B.7 Evaluation under prompting engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
C Related work (continued) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
D Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
D.1 Scalability of benchmark development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
D.2 Other limitations & future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
E Code of example problems in Table 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
E.1 HumanEval problem #10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
E.2 HumanEval problem #36 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
E.3 HumanEval problem #40 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
E.4 HumanEval problem #109 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
E.5 HumanEval problem #154 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

A PROOF OF THEOREM 1

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

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

14

702
703

704
705
706
707
708
709

710
711
712
713
714
715

716
717
718
719
720

721
722
723
724
725
726

727
728
729
730
731
732

733
734
735
736
737
738

739
740
741
742
743

744
745
746
747
748
749

750
751
752
753
754
755

Under review as a conference paper at ICLR 2025

A.1 PROOF OF UNBIASEDNESS

First, recall that every efficiency score ei,j depends only on the corresponding code sample ci,j.
Since ci,1, . . . , ci,n are independent, then given any size-k subset J = {j1, . . . , jk} ⊆ {1, . . . , n},

E
ci,1,...,ci,n∼LLM(zi)

(cid:104)
max
j∈J

(cid:105)

ei,j

=

=

=

=

E
ci,1,...,ci,n∼LLM(zi)
E
ci,1,...,ci,n∼LLM(zi)

[max{ei,j1 , . . . , ei,jk }]

[max{ei,1, . . . , ei,k}]

E
ci,1,...,ci,n∼LLM(zi)

(cid:104) k
max
j=1

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)

ei,j

(cid:105)

.

ei,j

(9)

(10)

(11)

(12)

Next, recall that probability measures are finite (and thus σ-finite). Since efficiency scores ei,j are
nonnegative, then by the Fubini–Tonelli theorem and Eq. equation 12,
(cid:1)
(cid:0)r−1
k−1
(cid:1) ei,(r)
(cid:0)n
k

E
ci,1,...,ci,n∼LLM(zi)

E
ci,1,...,ci,n∼LLM(zi)

max
j∈J

(cid:20) n
(cid:88)

(13)

ei,j

(cid:105)(cid:21)

=

(cid:21)

(cid:20)

(cid:104)

r=k

E
J⊆{1,...,n}
|J|=k

=

=

=

(cid:104)

(cid:104)

E
J⊆{1,...,n}
|J|=k

E
J⊆{1,...,n}
|J|=k

E
ci,1,...,ci,n∼LLM(zi)

(cid:104)

(cid:105)(cid:105)

max
j∈J

ei,j

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)(cid:105)

ei,j

E
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)
.

ei,j

A.2 PROOF OF VARIANCE REDUCTION

Note that efficiency scores ei,j ≥ 0 are bounded random variables:

ei,j ≤

(cid:80)L

l=1 hl · fi,j,l
(cid:80)L
l=1 hl

≤

L
max
l=1

fi,j,l

=

L
max
l=1

≤

L
max
l=1

(Ti − ti,j,l,m)+
i,l,m}Ml

m=1

Ti − max{t∗
Ti − 0
Ti − max{t∗

i,l,m}Ml

m=1

< ∞.

This implies that

Var
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)

ei,j

< ∞.

Furthermore, note that (cid:99)effi@k can be expressed as a U-statistic (Hoeffding, 1948):

n
(cid:88)

r=k

(cid:1)
(cid:0)r−1
k−1
(cid:1) ei,(r) =
(cid:0)n
k

1
(cid:1)
(cid:0)n
k

(cid:88)

J⊆{1,...,n}
|J|=k

max
j∈J

ei,j.

Therefore, by Theorem 5.2 of Hoeffding (1948),

Var
ci,1,...,ci,n∼LLM(zi)

(cid:20) n
(cid:88)

r=k

(cid:21)

(cid:1)
(cid:0)r−1
k−1
(cid:1) ei,(r)
(cid:0)n
k

=

Var
ci,1,...,ci,n∼LLM(zi)

(cid:20) 1
(cid:1)
(cid:0)n
k

(cid:21)

max
j∈J

ei,j

(cid:88)

J⊆{1,...,n}
|J|=k

≤

k
n

·

Var
ci,1,...,ci,k∼LLM(zi)

(cid:104) k
max
j=1

(cid:105)

.

ei,j

15

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

756
757

758
759
760
761
762
763

764
765
766
767
768
769

770
771
772
773
774

775
776
777
778
779
780

781
782
783
784
785
786

787
788
789
790
791
792

793
794
795
796
797

798
799
800
801
802
803

804
805
806
807
808
809

Under review as a conference paper at ICLR 2025

Table 6: Complete evaluation results on two subsets of problems.

Model

eff@1

pass@1

Llama 3 70B Instruct
Llama 3 8B Instruct
Mixtral 8x22B Instruct
Mixtral 8x7B Instruct
Claude 3 Sonnet
Claude 3 Haiku
Phind Code Llama V2
ChatGPT
Code Llama 70B Python
Code Llama 34B Python
Code Llama 13B Python
Code Llama 7B Python
StarCoder
CodeGen 16B
CodeGen 6B
CodeGen 2B
CodeT5+ 16B
Mistral 7B
Vicuna 13B
Vicuna 7B
SantaCoder
Incoder 6B
Incoder 1B
GPT-J
GPT-Neo 2B
PolyCoder
StableLM 7B

0.246
0.201
0.225
0.124
0.184
0.149
0.185
0.120
0.018
0.071
0.058
0.068
0.047
0.031
0.023
0.036
0.043
0.030
0.008
0.019
0.037
0.010
0.003
0.021
0.003
0.002
0.001

0.660
0.518
0.635
0.391
0.577
0.692
0.554
0.488
0.100
0.293
0.212
0.202
0.161
0.133
0.091
0.131
0.192
0.152
0.072
0.071
0.102
0.050
0.023
0.051
0.019
0.010
0.005

Algorithm Design Subset
eff@10

pass@10

eff@100

pass@100

eff@1

Implementation Optimization Subset
eff@100

pass@10

eff@10

pass@1

0.306
0.303
0.363
0.244
0.328
0.208
0.353
0.304
0.129
0.271
0.276
0.231
0.156
0.146
0.106
0.121
0.173
0.157
0.033
0.083
0.101
0.062
0.021
0.063
0.015
0.018
0.010

0.749
0.724
0.837
0.681
0.804
0.752
0.789
0.799
0.519
0.713
0.665
0.589
0.485
0.451
0.372
0.387
0.509
0.516
0.269
0.241
0.316
0.203
0.110
0.146
0.098
0.070
0.039

0.359
0.367
0.470
0.344
0.450
0.266
0.401
0.483
0.402
0.425
0.478
0.393
0.257
0.292
0.235
0.193
0.321
0.319
0.076
0.113
0.203
0.112
0.071
0.081
0.032
0.050
0.033

0.750
0.849
0.900
0.850
0.950
0.775
0.849
0.950
0.950
0.881
0.844
0.761
0.709
0.684
0.612
0.644
0.673
0.737
0.449
0.300
0.493
0.325
0.200
0.243
0.172
0.163
0.099

0.404
0.313
0.376
0.248
0.358
0.360
0.351
0.337
0.076
0.197
0.176
0.165
0.112
0.099
0.090
0.081
0.106
0.100
0.056
0.031
0.069
0.037
0.018
0.025
0.007
0.004
0.002

0.791
0.582
0.783
0.473
0.723
0.772
0.712
0.715
0.181
0.415
0.405
0.349
0.247
0.220
0.188
0.160
0.257
0.227
0.096
0.061
0.114
0.062
0.030
0.043
0.014
0.007
0.003

0.497
0.468
0.556
0.411
0.475
0.465
0.567
0.508
0.294
0.473
0.476
0.417
0.332
0.303
0.285
0.256
0.313
0.327
0.168
0.121
0.203
0.152
0.080
0.110
0.050
0.034
0.016

0.869
0.806
0.914
0.699
0.846
0.889
0.901
0.864
0.627
0.804
0.784
0.703
0.598
0.541
0.478
0.400
0.581
0.574
0.288
0.215
0.308
0.252
0.129
0.167
0.084
0.051
0.025

0.551
0.571
0.686
0.515
0.548
0.513
0.732
0.633
0.589
0.687
0.715
0.620
0.514
0.531
0.483
0.410
0.536
0.565
0.316
0.260
0.357
0.320
0.172
0.221
0.113
0.092
0.074

pass@100

0.920
0.906
0.947
0.827
0.893
0.923
0.968
0.949
0.920
0.949
0.928
0.863
0.802
0.801
0.731
0.610
0.845
0.821
0.569
0.439
0.488
0.477
0.232
0.354
0.184
0.122
0.099

B EVALUATION (CONTINUED)

B.1 EXPERIMENTAL SETTING

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

Code evaluation. We use α = 2, R = 6, h1 = h2 = 3, h3 = 4, M0 = 8, M1 = M2 = M3 = 4.
To minimize server workload fluctuations, we run evaluation on virtualized cloud servers hosted by
Google Cloud (Ubuntu 20.04.6 LTS; Intel Xeon CPU @ 2.20GHz; Python 3.10.12). We use the
reference time on the slowest test case for each problem to further calibrate the execution time of
generated code.

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

B.2 ANALYSIS ON ALGORITHM DESIGN & IMPLEMENTATION OPTIMIZATION (CONTINUED)

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

B.3 COMPARISON OF EFFICIENCY METRICS

To demonstrate that our proposed eff@k metric can rigorously handle right-censored execution
times, we empirically compare our eff@k with a classic metric called speedup (Amdahl, 1967).
The speedup metric is originally defined as the execution time t∗
i,l,m of the reference solution di-
vided by the true execution time ti,j,l,m of the generated code. Nonetheless, since generated code
can exceed the time limit Ti in our evaluation, the actual definition of speedup is

t∗
i,l,m
min{ti,j,l,m,Ti}

16

810
811

812
813
814
815
816
817

818
819
820
821
822
823

824
825
826
827
828

829
830
831
832
833
834

835
836
837
838
839
840

841
842
843
844
845
846

847
848
849
850
851

852
853
854
855
856
857

858
859
860
861
862
863

Under review 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 3
70B Instruct even seems to outperform GPT-4.

Rank

eff@1 (ours)

speedup

1
2
3
4
5
6
7
8
9
10
11
12

GPT-4 Turbo
GPT-4
Llama 3 70B Instruct
Mixtral 8x22B Instruct
Claude 3 Opus
Phind Code Llama V2
Claude 3 Haiku
ChatGPT
Claude 3 Sonnet
Llama 3 8B Instruct
Code Llama 34B Python Mixtral 8x7B Instruct
Mixtral 8x7B Instruct

GPT-4 Turbo
Mixtral 8x22B Instruct
Llama 3 70B Instruct
GPT-4
Claude 3 Opus
Phind Code Llama V2
ChatGPT
Claude 3 Haiku
Claude 3 Sonnet
Llama 3 8B 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 are 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
Expert (ours)

0.91
0.17

1.25
0.00

instead, which overestimates efficiency when ti,j,l,m > Ti. We average the speedup score over all
test cases in each level, and we use the same hardnesses h1, h2, h3 to weigh the levels.

Table 7 shows rankings of LLMs with greedy decoding under our eff@1 metric and the speedup
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 3
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), as we discussed above. Therefore, it is necessary to
propose our eff@k metric to more rigorously handle right-censored execution time.

B.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 test case generator for the problem #31 (de-
ciding if a number n is prime). We investigate the following two solutions: (i) Na¨ıve: the O(n)-
time factorization algorithm, which is 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 the random generator and our test case generator, respectively. Results are shown in
Table 8. We can see that random test cases cannot assess true correctness or true efficiency while our
test case generator can. This demonstrates the strength of our expert-written test case generators.

B.5 ANALYSIS OF HYPERPARAMETERS

Our benchmark has timeout factor α and hardnesses h1, h2, h3 as hyperparameters. Regarding the
timeout factor α, it represents the tolerance to execution timeout because the execution time limit
is proportional to α. Thus, if one wants to tolerate less efficient code, then they can use a larger α.
Regarding hardnesses h1, h2, h3, 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 to focus more on harder levels, they
should use a larger h3. We encourage users to stick to our default hyperparameters α = 2, h1 = 3,

17

864
865

866
867
868
869
870
871

872
873
874
875
876
877

878
879
880
881
882

883
884
885
886
887
888

889
890
891
892
893
894

895
896
897
898
899
900

901
902
903
904
905

906
907
908
909
910
911

912
913
914
915
916
917

Under review as a conference paper at ICLR 2025

Table 9: Analysis of timeout factor α and hardnesses h1, h2, h3 on GPT-4 Turbo.
(a) Timeout factor α.

α

1.5

2.0

2.5

3.0

3.5

eff@1

0.421

0.470

0.502

0.525

0.541

(b) Level-1 hardness h1.

h1
eff@1

h2
eff@1

h3
eff@1

1

2

3

4

5

0.428

0.451

0.470

0.486

0.498

(c) Level-2 hardness h2.

1

2

3

4

5

0.474

0.472

0.470

0.469

0.467

(d) Level-3 hardness h3.

1

2

3

4

5

0.520

0.499

0.483

0.470

0.460

Table 10: Comparison of the standard deviations of the vanilla eff@k estimator and our Rao–
Blackwellized eff@k estimator. Better results are marked in bold font. Our Rao–Blackwellized
estimator achieves significantly lower standard deviation than the vanilla estimator.

Estimator

k = 1

k = 10

Vanilla
Rao–Blackwellized

0.20
0.02

0.25
0.08

h2 = 3, h3 = 4 to 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 α and h1, h2, h3, we report the eff@1 of GPT-4
Turbo with greedy decoding under different α, h1, h2, and h3. Results are shown in Table 9. We
can see that eff@1 increases as α increases (because alpha represents the tolerance to less efficient
code), that eff@1 increases as h1 increases (because we weigh more on an easier level), and that
eff@1 decreases as h2 or h3 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.

B.6 ANALYSIS OF RAO–BLACKWELLIZATION

To demonstrate that Rao–Blackwellization does reduce the variance of the eff@k estimator, we
empirically compute the standard deviation of the vanilla eff@k estimator Eq. (5) and our Rao–
Blackwellized eff@k estimator using the Llama 3 70B Instruct model. We randomly sample 1000
subsets of size k from the 100 generated samples to estimate the standard deviation of the vanilla
eff@k estimator. Results are shown in Table 10. We can see that the Rao–Blackwellized esti-
mator achieves much lower standard deviation than the vanilla estimator. Therefore, our Rao–
Blackwellized estimator empirically ensures a more accurate estimation of eff@k.

B.7 EVALUATION UNDER PROMPTING ENGINEERING

To investigate how prompt engineering affects evaluation results, we provide the following two
experiments on prompt engineering.

18

918
919

920
921
922
923
924
925

926
927
928
929
930
931

932
933
934
935
936

937
938
939
940
941
942

943
944
945
946
947
948

949
950
951
952
953
954

955
956
957
958
959

960
961
962
963
964
965

966
967
968
969
970
971

Under review as a conference paper at ICLR 2025

Table 11: 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 3 70B Instruct.

(b) Mixtral 8x22B Instruct.

Prompt

eff@1

pass@1

Prompt

eff@1

pass@1

Basic
Encouraging

0.421
0.418

0.746
0.746

Basic
Encouraging

0.408
0.426

0.746
0.732

Table 12: Results of Self-Refine prompting (Madaan et al., 2024) for problem #36. Both LLMs are
unable to come up with the efficient algorithm on their own.

(a) Initial code by Llama 3 70B Instruct.

count = 0
for i in range(n):

if i % 11 == 0 or i % 13 == 0:
count += str(i).count(’7’)

return count

(b) Self-Refined code by Llama 3 70B Instruct.

import math
return sum(str(i).count(’7’) for i in range(n) if math
.gcd(i, 11 * 13) in (11, 13))

(c) Initial code by Mixtral 8x22B Instruct.

count = 0
for i in range(11, n, 1):

if i % 11 == 0 or i % 13 == 0:
count += str(i).count(’7’)

return count

(d) Self-Refined code by Mixtral 8x22B Instruct.

count = 0
for i in range(11, n, 11):

count += str(i).count(’7’)

for i in range(13, n, 13):

if i % 11 != 0:

# to avoid double counting

numbers that are divisible by both 11 and 13
count += str(i).count(’7’)

return count

1

2

3

4

5

1

2

1

2

3

4

5

1

2

3

4

5

6

7

Experiment I: encouraging efficiency. We use the two strongest open-source LLMs Llama 3 70B
Instruct and Mixtral 8x22B Instruct (according to Table 3). 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 11. The results show that this prompt engineering cannot enhance code efficiency much, even
for such strong LLMs. The eff@1 of Mixtral 8x22B Instruct increases a little bit but is still far from
the expert level. Interestingly, the eff@1 of Llama 3 70B Instruct even drops a little bit while the
pass@1 does not change. This suggests that even such strong LLMs lack a 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 LLMs—efficient algorithms can be so non-trivial that existing LLMs do not understand them
well. To demonstrate this, we further conduct a case study for a 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 a dynamic programming over digits in
O(log n) time; see Appendix E.2).

19

972
973

974
975
976
977
978
979

980
981
982
983
984
985

986
987
988
989
990

991
992
993
994
995
996

997
998
999
1000
1001
1002

1003
1004
1005
1006
1007
1008

1009
1010
1011
1012
1013

1014
1015
1016
1017
1018
1019

1020
1021
1022
1023
1024
1025

Under review as a conference paper at ICLR 2025

1026
1027

1028
1029
1030
1031
1032
1033

1034
1035
1036
1037
1038
1039

1040
1041
1042
1043
1044

1045
1046
1047
1048
1049
1050

1051
1052
1053
1054
1055
1056

1057
1058
1059
1060
1061
1062

1063
1064
1065
1066
1067

1068
1069
1070
1071
1072
1073

1074
1075
1076
1077
1078
1079

Table 13: Raw output of Llama 3 70B Instruct when we reveal the efficient algorithm in 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 i % 13 == 0:
count += str(i).count(’7’)

return count

‘‘‘
Here’s an explanation of 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 we want

to consider integers less than ‘n‘).

3. For each integer ‘i‘ in the range, we check if it is divisible by 11

or 13 using the modulo operator (‘%‘). If it is, we proceed to the
next step.

4. We convert the integer ‘i‘ to a string using the ‘str()‘ function, and

then use the ‘count()‘ method to count the number of occurrences of

the digit ’7’ in the string.

5. We add the count of digit 7 appearances in the current integer to the

overall ‘count‘ variable.

6. Finally, we return the total ‘count‘ at the end of the function.

This function has a time complexity of O(n), where n is the input integer
, since we iterate over the range of integers from 0 to ‘n-1‘. The
space complexity is O(1) since we only use a single variable to store

the count.

You can test the function with the provided examples to verify that it

produces the correct output:

‘‘‘python
print(fizz_buzz(50))
print(fizz_buzz(78))
print(fizz_buzz(79))
‘‘‘

# 0
# 2
# 3

For Self-Refine, following Niu et al. (2024), we ask the LLM to “give a potential strategy to improve
the efficiency of the code” and finally to “give the optimized version of the same code with the
strategy mentioned above.” Outputs before and after Self-Refine are shown in Table 12. Before Self-
Refine, both Llama 3 70B Instruct and Mixtral 8x22B Instruct generate the brute-force algorithm
that runs in O(n) time. After Self-Refine, both LLMs apply a small improvement to the generated
code, but the time complexity is still O(n), significantly slower than the efficient algorithm that runs
in O(log n) time. This suggests that both LLMs are unable to come up with the efficient algorithm
on their own.

To further investigate whether LLMs can generate the dynamic programming algorithm here, we
explicitly reveal the efficient algorithm in the prompt. Specifically, we use “Complete the following
function with a dynamic programming over digits” for both LLMs. Raw outputs are shown in
Tables 13 & 14. Llama 3 70B Instruct fails to use dynamic programming; Mixtral 8x22B Instruct
uses a 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(log n)
algorithm to them. This suggests that they do not have a good understanding of this non-trivial
dynamic programming.

From the two case studies above, we can see that, no matter whether we use (i) or (ii), the generated
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 a capability limitation of existing LLMs,

20

Under review as a conference paper at ICLR 2025

Table 14: 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:

‘‘‘python
def fizz_buzz(n: int):

"""Return the number of times the digit 7 appears in integers less
than n which are divisible by 11 or 13.
"""
# Initialize a list to store the count of 7s in each number
dp = [0] * n

# Base case: the number of 7s in 0 is 0
dp[0] = 0

# Iterate over the range of numbers
for i in range(1, n):

# If the current number is divisible by 11 or 13
if i % 11 == 0 or i % 13 == 0:

# If the last digit of the current number is 7
if i % 10 == 7:

# Add 1 to the count of 7s in the current number
dp[i] = dp[i - 1] + 1

else:

# Otherwise, the count of 7s in the current number is the

same as the previous number

dp[i] = dp[i - 1]

else:

# If the current number is not divisible by 11 or 13, the

count of 7s is the same as the previous number

dp[i] = dp[i - 1]

# Return the count of 7s in numbers less than n
return dp[n - 1]

‘‘‘

This function works by iterating over the range of numbers from 1 to n-1

and checking if each number is divisible by 11 or 13. If it is, the
function checks if the last digit of the number is 7. If it is, the
function adds 1 to the count of 7s in the current number. Otherwise,
the count of 7s in the current number is the same as the previous
number. The function then returns the count of 7s in numbers less
than n.

Here are the test cases:

‘‘‘python
print(fizz_buzz(50))
print(fizz_buzz(78))
print(fizz_buzz(79))
‘‘‘

# Output: 0
# Output: 2
# Output: 3

and therefore we do not expect it to be easily addressed merely via prompting techniques. This
is also our core motivation for developing this benchmark to 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 to this limitation and try to address it in
future work.

21

1080
1081

1082
1083
1084
1085
1086
1087

1088
1089
1090
1091
1092
1093

1094
1095
1096
1097
1098

1099
1100
1101
1102
1103
1104

1105
1106
1107
1108
1109
1110

1111
1112
1113
1114
1115
1116

1117
1118
1119
1120
1121

1122
1123
1124
1125
1126
1127

1128
1129
1130
1131
1132
1133

Under review as a conference paper at ICLR 2025

1134
1135

1136
1137
1138
1139
1140
1141

1142
1143
1144
1145
1146
1147

1148
1149
1150
1151
1152

1153
1154
1155
1156
1157
1158

1159
1160
1161
1162
1163
1164

1165
1166
1167
1168
1169
1170

1171
1172
1173
1174
1175

1176
1177
1178
1179
1180
1181

1182
1183
1184
1185
1186
1187

C RELATED WORK (CONTINUED)

Code generation (a.k.a. program synthesis) is a long-standing problem in computer science (Si-
mon, 1963). Many classic code generation methods have been proposed over the past few decades
(Gulwani et al., 2017), including deductive (Waldinger & Lee, 1969; Manna & Waldinger, 1971;
Green, 1981), inductive (Shaw et al., 1975; Gulwani, 2011), and neural-guided approaches (Kalyan
et al., 2018; Yu et al., 2023). More recently, many code LLMs have been developed, including
Codex (Chen et al., 2021), AlphaCode (Li et al., 2022), CodeGen (Nijkamp et al., 2023), Star-
Coder (Li et al., 2023), Code Llama (Roziere et al., 2023), CodeT5+ (Wang et al., 2023), and so on.
Some general LLMs such as GPT (OpenAI, 2023), Llama (Meta, 2024), Claude (Anthropic, 2024),
Gemini (Google, 2024), and Mixtral (Jiang et al., 2024) also exhibit promising capabilities in code
generation.

D CONCLUDING 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 a high-standard and rigorous benchmark.
For example, as shown in Table 2, compared with our expert solutions, HumanEval canonical solu-
tions achieve only eff@1=0.455, and HumanEval+ canonical solutions achieve only eff@1=0.513.
This shows that their canonical solutions are far less efficient than our expert-written reference solu-
tions. In fact, we have excluded a few options when designing the benchmark development method-
ology:

• We did not use problems or solutions from online judges (like LeetCode or Codeforces)
because their public solutions are already in LLMs’ pretraining corpuses. For example,
DeepMind’s AlphaCode (Li et al., 2022) has been trained on many online judges includ-
ing Codeforces, CodeChef, HackerEarth, AtCoder, and Aizu.
If we evaluate LLMs on
these public online judges, then the evaluation results may fail to reflect the LLMs’ true
capabilities due to test set leakage.

• 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., 2021) is a popular crowd-
sourced benchmark, but it is known to be easier than HumanEval (Roziere et al., 2023).
• We did not use LLM-generated reference solutions because LLM-generated code are still

far from expert-level efficiency, as demonstrated in Table 3.

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

• As shown in Figure 2, our benchmark problems have diverse difficulties. For example,
75 seemingly easy problems require non-trivial implementation optimization, and 20 hard
problems require advanced algorithms.

• As discussed in Section 3.2, our problemset covers a 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).

That said, we still believe that addressing scalability of benchmark development is an important
future direction. A possible solution is 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 be addressed in future work:

22

Under review as a conference paper at ICLR 2025

• 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., 2024).

• Although we have used the known best algorithms as our reference solutions, it is hard to
theoretically guarantee their optimality. Thus, the efficiency score can be greater than 1 if
the benchmarked code is more efficient than our reference solution. Addressing this issue
in future work will provide a solid ground for efficiency evaluation.

• This work focuses on benchmarking code efficiency without more advanced prompting
techniques. Future work can explore how to design prompts to improve the efficiency
of LLM-generated code. A possible solution is to guide the LLM to analyze the time
complexity in the chain of thought (Wei et al., 2022) when generating the code.

• While our current benchmark focuses on evaluating time efficiency, we believe that evaluat-
ing the space efficiency would be a very interesting and important future research direction.
For example, EffiBench (Huang et al., 2024) is a time–space joint evaluation benchmark
for LLM-generated code. A potential challenge is how to evaluate the time–space trade-off.
Since many time-efficient algorithms trade space for time (e.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 to measure the time complexity will also be a 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
a 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 a so-
phisticated analysis by the authors shows that it actually has O(log n) time complexity per
operation. (ii) Fitting a time curve: Another possible approach is to fit a curve of the run-
ning time v.s. the input size to help decide the time complexity. However, we believe that
this is in general difficult because it is practically infeasible to distinguish a high-degree
polynomial from an exponential function. For example, the Agrawal–Kayal–Saxena pri-
mality test (Agrawal et al., 2004) runs in ˜O((log n)12) time, so the curve of its running time
v.s. n looks extremely like an exponential function for most practical n.

E CODE OF EXAMPLE PROBLEMS IN TABLE 1

E.1 HUMANEVAL PROBLEM #10

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

HumanEval+ canonical solution: Enumerate suffixes and check palindromicity. The time com-
plexity is O(|S|2).

return string == string[::-1]

1 def is_palindrome(string: str) -> bool:
2
3 if is_palindrome(string):
4
5 for i in range(len(string)):
6

if is_palindrome(string[i:]):

return string

7

return string + string[i-1::-1]

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

1 if not string:
2
3 reversed_s = string[:: -1]

return string

23

1188
1189
1190
1191
1192

1193
1194
1195
1196
1197
1198

1199
1200
1201
1202
1203
1204

1205
1206
1207
1208
1209
1210

1211
1212
1213
1214
1215

1216
1217
1218
1219
1220
1221

1222
1223
1224
1225
1226
1227

1228
1229
1230
1231
1232
1233

1234
1235
1236
1237
1238

1239
1240
1241

Under review as a conference paper at ICLR 2025

4 pattern = reversed_s + ’\x00’ + string
5 m = len(pattern)
6 # Knuth--Morris--Pratt
7 fail = [0] * (m + 1)
8 j = 0
9 for i in range(1, m):
c = pattern[i]
10
while j > 0 and pattern[j] != c:

11

12

13

14

j = fail[j]

if j > 0 or pattern[0] == c:

j += 1

fail[i + 1] = j

15
16 return string[: len(string) - fail[-1]] + reversed_s

E.2 HUMANEVAL PROBLEM #36

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

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

1 cnt = 0
2 for i in range(n):
3

if i % 11 == 0 or i % 13 == 0:

cnt += len(list(filter(lambda c: c == "7", str(i))))

4
5 return cnt

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

1 a = []
2 while n > 0:
3

n, u = divmod(n, 10)
a.append(u)

4
5 m = len(a)
6 b = [[1, 1]] # [10 ** i % 11, 10 ** i % 13]
7 for i in range(m - 1):
8
9 f = [[[[[0, 0] for w in range(10)] for v in range(13)] for u in range
(11)] for i in range(m)] # [i-th][mod 11, mod 13][digit]: [number of
valid numbers, number of 7’s in valid numbers]

b.append([(b[i][0] * 10) % 11, (b[i][1] * 10) % 13])

10 for u in range(10):
11

f[0][u][u] = [[int(w >= u), int(u == 7 and w >= 7)] for w in range
(10)]

12 for i in range(1, m):
for u in range(11):
13

for v in range(13):

f0 = f[i - 1][u][v][9]
for w in range(10):

f1 = f[i][(u + b[i][0] * w) % 11][(v + b[i][1] * w) % 13][w]
f1[0] += f0[0]
f1[1] += f0[1] + f0[0] * int(w == 7)

for u in range(11):

for v in range(13):
f1 = f[i][u][v]
for w in range(1, 10):

14

15

16

17

18

19

20

21

22

23

24

e[i - 1] = [(e[i][0] + b[i][0] * a[i]) % 11, (e[i][1] + b[i][1] * a[i
]) % 13, e[i][2] + int(a[i] == 7)]

f1[w][0] += f1[w - 1][0]
f1[w][1] += f1[w - 1][1]

25
26 e = [[0, 0, 0] for i in range(m)]
27 for i in range(m - 1, 0, -1):
28

29 ans = 0
30 for i in range(m):

24

1242
1243
1244
1245
1246

1247
1248
1249
1250
1251
1252

1253
1254
1255
1256
1257
1258

1259
1260
1261
1262
1263
1264

1265
1266
1267
1268
1269

1270
1271
1272
1273
1274
1275

1276
1277
1278
1279
1280
1281

1282
1283
1284
1285
1286
1287

1288
1289
1290
1291
1292

1293
1294
1295

Under review as a conference paper at ICLR 2025

31

32

33

34

35

36

37

38

39

40

41

if a[i]:

w = a[i] - 1
u = (-e[i][0]) % 11
for v in range(13):

f1 = f[i][u][v][w]
ans += f1[1] + f1[0] * e[i][2]

u0 = u
v = (-e[i][1]) % 13
for u in range(11):

if u != u0:

f1 = f[i][u][v][w]
ans += f1[1] + f1[0] * e[i][2]

42
43 return ans

E.3 HUMANEVAL PROBLEM #40

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

HumanEval+ canonical solution: Enumerate triples in l and check their sums. The time complex-
ity is O(|l|3).

1 for i in range(len(l)):
2

for j in range(len(l)):

3

4

for k in range(len(l)):

if i != j and i != k and j != k and l[i] + l[j] + l[k] == 0:

5
6 return False

return True

Our expert-written solution: Note that li + lj + lk = 0 is equivalent to lk = −li − lj, so we
can enumerate li, lj, store −li − lj in a hash set, and check whether lk is in the hash set. The time
complexity is O(|l|2).

1 n = len(l)
2 if n < 3:
3
4 for i, x in enumerate(l[: n - 2]):
5

return False

buf = set()
for y in l[i + 1 :]:

6

7

8

if y in buf:

return True
buf.add(-x - y)

9
10 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 a and check if it is sorted. The time
complexity is O(|a|2).

1 sorted_arr = sorted(arr)
2 if arr == sorted_arr: return True
3 for i in range(1, len(arr)):
4

if arr[i:] + arr[:i] == sorted_arr:

return True

5
6 return False

Our expert-written solution: Note that the desired condition is equivalent to the condition that
there is at most 0 ≤ i < |a| with ai > a(i+1) mod n, so we can enumerate i and check this equivalent
condition. The time complexity is O(|a|).

1 if len(arr) <= 2:
return True
2

25

1296
1297
1298
1299
1300

1301
1302
1303
1304
1305
1306

1307
1308
1309
1310
1311
1312

1313
1314
1315
1316
1317
1318

1319
1320
1321
1322
1323

1324
1325
1326
1327
1328
1329

1330
1331
1332
1333
1334
1335

1336
1337
1338
1339
1340
1341

1342
1343
1344
1345
1346

1347
1348
1349

Under review as a conference paper at ICLR 2025

3 cnt = int(arr[-1] > arr[0])
4 for a, b in zip(arr[: -1], arr[1 :]):
5

if a > b:

6

7

cnt += 1
if cnt > 1:

8
9 return True

return False

E.5 HUMANEVAL PROBLEM #154

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

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

return True

1 if a == b:
2
3 if b == "":
4
5 for i in range(0, len(b)):
6

if b[i:] + b[:i] in a:

return True

return True

7
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 is at least |b|. Thus, we can run the suffix automaton of a
w.r.t. b + b to compute their longest common substring. Since the suffix automaton of a can be built
within Θ(|a|) time, the overall time complexity is O(|a| + |b|).

1 from copy import deepcopy
2 class State:
3

def __init__(self, len = 0, link = 0, next = None):

4

5

self.len = len
self.link = link
self.next = dict() if next is None else deepcopy(next)

6
7 st = [State(len = 0, link = -1)]
8 last = 0
9 def sam_extend(c, last): # to build the suffix automaton
10

cur = len(st)
st.append(State(len = st[last].len + 1))
p = last
while p != -1 and c not in st[p].next:

st[p].next[c] = cur
p = st[p].link

if p == -1:

st[cur].link = 0

else:

q = st[p].next[c]
if st[p].len + 1 == st[q].len:

st[cur].link = q

else:

clone = len(st)
st.append(State(len = st[p].len + 1, link = st[q].link, next = st

[q].next))

while p != -1 and st[p].next[c] == q:

st[p].next[c] = clone
p = st[p].link

st[q].link = st[cur].link = clone

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

last = cur
return last

30
31 for c in a:
32
33 v = 0
34 l = 0

last = sam_extend(c, last)

26

1350
1351
1352
1353
1354

1355
1356
1357
1358
1359
1360

1361
1362
1363
1364
1365
1366

1367
1368
1369
1370
1371
1372

1373
1374
1375
1376
1377

1378
1379
1380
1381
1382
1383

1384
1385
1386
1387
1388
1389

1390
1391
1392
1393
1394
1395

1396
1397
1398
1399
1400

1401
1402
1403

Under review as a conference paper at ICLR 2025

35 for c in b + b:
36

while v and c not in st[v].next:

37

38

39

40

41

42

v = st[v].link
l = st[v].len

if c in st[v].next:
v = st[v].next[c]
l += 1

if l >= len(b):
return True

43
44 return False

27

1404
1405

1406
1407
1408
1409
1410
1411

1412
1413
1414
1415
1416
1417

1418
1419
1420
1421
1422

1423
1424
1425
1426
1427
1428

1429
1430
1431
1432
1433
1434

1435
1436
1437
1438
1439
1440

1441
1442
1443
1444
1445

1446
1447
1448
1449
1450
1451

1452
1453
1454
1455
1456
1457

