How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark

• Existing evaluations chiefly test correctness, although code efficiency matters for throughput, latency, and energy consumption.Source: §1 · p. 1
• ENAMEL evaluates 142 nontrivial HumanEval and HumanEval+ problems spanning easy to hard.Source: §1 · p. 2
• Across 30 LLMs, ENAMEL finds LLMs fall short of expert-level efficiency; GPT-4 has eff@1=0.454 despite pass@1=0.831.Source: §1 · p. 3
• eff@k extends pass@k to efficiency across sample sizes and handles right-censored execution times, with an unbiased, variance-reduced Rao–Blackwellized estimator.Source: §1 · pp. 2–3
• Human-expert reference solutions set a higher efficiency standard; for Fibonacci, the reference uses Θ(log n) iterations versus Θ(n) for the canonical solution.Source: §1 · pp. 2–3
• Strong generators cover corner and worst cases; they find 11 HumanEval and 4 HumanEval+ canonical solutions wrong, while 34 and 27 respectively exceed time limits.Source: §1 · pp. 2–3

2.1 LEVEL-BASED EVALUATION

• Multiple input-scale levels distinguish efficiencies while level 0 filters incorrect code and timed-out code skips the remaining, larger levels.Experts design the input scales so algorithms with different efficiencies pass different numbers of levels.Source: §2.1 · pp. 3–4

2.2 EFFICIENCY SCORE OF A CODE SAMPLE

• For correct code, the per-level score becomes zero when its maximum test-case runtime reaches the time limit, avoiding dependence on right-censored execution time.The score uses the maximum runtime across test cases to characterize worst-case efficiency.Source: §2.2 · p. 4
• The sample score normalizes against the reference solution, combines levels using hardness weights, and estimates runtimes with repeated tests and the Hodges–Lehmann estimator.The time limit is set as a factor of the maximum reference runtime; repeated measurements reduce hardware-fluctuation variance.Source: §2.2 · p. 4

2.3 EFFICIENCY METRIC FOR AN LLM

• eff@k generalizes pass@k by measuring the expected maximum efficiency score among k generated samples, capturing how efficiency relates to sample size.Earlier efficiency metrics used a single sample or averaged scores, which did not capture this relationship.Source: §2.3 · pp. 4–5
• A Rao–Blackwellized bootstrap estimator is unbiased and reduces variance; ENAMEL also supplies a numerically stable implementation.It averages maxima over random k-sized subsets of n independent samples and takes the expectation over the random subset.Source: §2.3 · p. 5

3 BENCHMARK DEVELOPMENT

• The benchmark section also presents a numerically stable estimated eff@k procedure that takes a score list and target k and returns an estimate.The procedure sorts the scores before returning a weighted sum.Source: §3 · p. 6

3.1 PROBLEM SELECTION

• The 142 selected problems exclude trivial Θ(1)-time tasks, whose short runtimes are hardware-sensitive and poorly distinguish LLM capabilities.The set reuses HumanEval problems and includes a broad range of difficulties.Source: §3.1 · p. 6

3.2 EFFICIENT REFERENCE SOLUTIONS

• For each problem, an expert designs the best algorithm, then optimizes its implementation to establish an efficiency reference.The references include advanced algorithms and mathematical techniques; implementations are tested and the most efficient one retained.Source: §3.2 · pp. 6–7

3.3 STRONG TEST CASE GENERATORS

• Expert-curated generators combine corner cases to filter wrong code with worst cases to distinguish suboptimal algorithms.The expert strengthens ChatGPT-generated initial generators where needed and uses only absolutely valid corner cases.Source: §3.3 · p. 7
• Expert test generators expose failures in canonical solutions: 11 HumanEval and 4 HumanEval+ solutions are wrong, while 34 and 27 exceed time limits, respectively.The generators target correctness and efficiency rather than relying only on random tests.Source: §3.3 · p. 7

4.1 MAIN RESULTS & ANALYSIS

• GPT-4 does not exceed eff@1=0.5, most models do not reach eff@1=0.3, and eff@k stays below pass@k across models and sample sizes.Phind Code Llama V2 reaches eff@100=0.723, above ChatGPT's eff@100=0.690.Source: §4.1 · pp. 7–8, Table 3 · p. 8

4.2 ANALYSIS ON ALGORITHM DESIGN & IMPLEMENTATION OPTIMIZATION

• On 20 hard algorithm-design problems, ChatGPT reaches only eff@100=0.483, indicating difficulty designing advanced algorithms even with 100 samples.The optimal algorithm can have substantially lower time complexity than suboptimal alternatives.Source: §4.2 · p. 8, Table 4 · p. 8
• On 75 implementation-optimization problems, Phind Code Llama V2 improves from eff@1=0.351 to eff@100=0.732, largely through sampling equivalent implementations.The authors interpret the low small-sample efficiency as evidence that models are barely aware of implementation optimization.Source: Table 4 · p. 8, §4.2 · p. 9

4.3 DISTRIBUTION OF PROBLEM DIFFICULTIES

• Problem #98 has passi@1=0.50 but effi@1=0.03 because efficient counting needs a clever builtin-function implementation rather than straightforward counting.The difficulty scores average over LLMs under greedy generation, and the benchmark spans easy to hard problems.Source: §4.3 · p. 9, Figure 2 · p. 9

Code generation

• Code generation includes deductive, inductive, and neural-guided approaches, alongside newer code-specific and general-purpose LLMs.The cited examples include Codex, AlphaCode, Code Llama, GPT, Llama, Claude, Gemini, and Mixtral.Source: §5 · p. 9

Benchmarks for LLM-based code generation

• Most established LLM code-generation benchmarks, including HumanEval and MBPP, focus on code correctness.Only recently have benchmarks begun evaluating code efficiency.Source: §5 · pp. 9–10
• Recent efficiency benchmarks leave open how to handle right-censored runtimes, sample size, optimization, correctness, and worst-case efficiency.Classic speedup metrics are not designed for right-censored execution times and can overestimate efficiency.Source: §5 · p. 10

6 CONCLUSION

• ENAMEL combines eff@k with an unbiased, variance-reduced estimator, expert-written references for 142 problems, and expert-written strong test generators.The authors report that their evaluation finds existing LLMs short of expert-level efficient code.Source: §6 · p. 10
• The authors conclude that current LLMs still fall short of generating expert-level efficient code.They encourage LLM developers to pay more attention to generated-code efficiency.Source: §6 · p. 10
• The conclusion points readers to Appendix D for limitations and future work.The supplied appendix contents identify sections on benchmark-development scalability and other limitations and future work.Source: §6 · p. 10, APPENDIX · p. 16

B.2 PROOF OF VARIANCE REDUCTION

• The proof identifies nonnegative efficiency scores as bounded random variables and expresses c effi@k as a U-statistic.It then invokes Theorem 5.2 of Hoeffding (1948).Source: §B.2 · p. 17

C.1 EXPERIMENTAL SETTING

• The experiments sample 200 outputs per problem for relatively smaller models, 100 for larger models, and use greedy decoding for the largest commercial models.Open-source sampling uses temperature 0.8 and top p 0.95; Claude 3 sampling uses temperature 0.8.Source: §C.1 · p. 18
• The evaluation uses the slowest test case’s reference time to calibrate generated-code execution time and runs on Google Cloud virtualized servers.The server setup is Ubuntu 20.04.6 LTS, Intel Xeon CPU @ 2.20GHz, and Python 3.10.12.Source: §C.1 · p. 18

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

• Table 6’s complete results for two problem subsets show observations similar to those in Table 4.The supplied passage does not specify the particular observations.Source: §C.2 · p. 18

C.3 COMPARISON OF EFFICIENCY METRICS

• Under speedup, Mixtral 8x22B Instruct and Llama 3 70B Instruct appear to outperform GPT-4, unlike under eff@1.The authors attribute the ranking difference to speedup overestimating efficiency for programs exceeding time limits.Source: Table 7 · p. 19, §C.3 · p. 19

C.4 COMPARISON WITH RANDOM TEST CASES

• Random test cases cannot assess true correctness or efficiency for the primality problem, while ENAMEL’s expert-written generator can.The case study compares a correct but inefficient O(n)-time factorization algorithm with the efficient but wrong Fermat primality test.Source: §C.4 · p. 19, Table 8 · p. 19

C.5 COMPARISON WITH OTHER BENCHMARKS

• ENAMEL is more challenging to LLMs than EffiBench and Mercury.The comparison uses Code Llama 34B Python because Mercury did not evaluate GPT-4 or Code Llama 70B Python; the authors note that LeetCode solutions are public, while ENAMEL’s expert-written efficient solutions were unseen.Source: §C.5 · pp. 19–20, Table 9 · p. 20

C.6 ANALYSIS OF HYPERPARAMETERS

• Increasing α or h1 raises GPT-4 Turbo’s eff@1, while increasing h2 or h3 lowers it.The authors link α to tolerance for less efficient code and the hardness weights to the emphasis on each problem level; they recommend defaults α = 2, h1 = 3, h2 = 3, h3 = 4.Source: §C.6 · p. 20, Table 10 · p. 20

C.7 ANALYSIS OF RAO–BLACKWELLIZATION

• The Rao–Blackwellized eff@k estimator achieves significantly lower standard deviation than the vanilla estimator.For Llama 3 70B Instruct, the authors estimated the vanilla estimator’s standard deviation by sampling 1000 subsets of size k from 100 generated samples.Source: §C.7 · pp. 20–21, Table 11 · p. 21

Experiment I: encouraging efficiency

• Asking Llama 3 70B Instruct and Mixtral 8x22B Instruct for “the most efficient algorithm” barely improves efficiency; Mixtral’s eff@1 rises a little, while Llama’s falls slightly without a pass@1 change.Mixtral remains far from the expert level.Source: §C.8 · p. 21

Experiment II: adaptive prompting

• The second adaptive-prompting setting explicitly reveals the O(log n) dynamic-programming algorithm over digits in the prompt.Both LLMs are tested with the instruction to complete the function using dynamic programming over digits.Source: §C.8 · p. 21
• In the Self-Refine case study, both models start with O(n) brute force and make only small improvements, remaining slower than the O(log n) algorithm.The authors conclude that neither model comes up with the efficient algorithm on its own.Source: §C.8 · p. 21, Table 13
• The prompt experiments compare initial and refined code, including loops over n and code that iterates by 11 and 13 while avoiding double counting.The displayed code illustrates the inefficient approaches discussed in the case studies.Source: §C.8 · p. 22
• Even after the algorithm is revealed, Llama 3 70B Instruct fails to use dynamic programming and Mixtral 8x22B Instruct uses a trivial version not over digits; both remain O(n).The authors say this suggests the models do not understand this non-trivial dynamic programming well.Source: §C.8 · p. 22

Evaluation under prompting engineering

• Across the two case studies, the outputs remain O(n) rather than O(log n), leading the authors to characterize inefficiency as a capability limitation not easily addressed merely by prompting.Addressing that limitation is beyond this work’s scope.Source: §C.8 · p. 22

D.1 SCALABILITY OF BENCHMARK DEVELOPMENT

• HumanEval canonical solutions achieve eff@1=0.455, and HumanEval+ canonical solutions achieve eff@1=0.513, both below the expert-written references.The authors use these comparisons to support human expertise in creating high-standard references.Source: §D.1 · p. 22
• The benchmark avoids online-judge problems because public solutions may leak through LLM pretraining, and avoids crowdsourcing or LLM-generated references over quality concerns.The authors note that crowdsourcing can make benchmark quality difficult to guarantee, while LLM-generated code remains far from expert-level efficiency.Source: §D.1 · p. 23
• GPT-4 Turbo remains below eff@1=0.5 across ENAMEL’s 142 problems, despite the benchmark revealing limited efficiency among all 30 evaluated LLMs.The authors attribute the benchmark’s effectiveness to expert verification of problem-set comprehensiveness.Source: §D.1 · p. 23
• The problem set spans diverse difficulty and knowledge: 75 seemingly easy problems require non-trivial implementation optimization, while 20 hard problems require advanced algorithms.Its coverage includes data structures, dynamic programming, automata, linear algebra, combinatorics, and number theory.Source: §D.1 · p. 24
• Collaborating with private programming competitions whose solutions are not public is proposed as a possible route to address benchmark-development scalability.Source: §D.1 · p. 25

D.2 OTHER LIMITATIONS & FUTURE WORK

• ENAMEL focuses on standalone problems and time efficiency, leaves advanced prompting unexplored, and cannot theoretically guarantee reference optimality; automatic time-complexity measurement is also future work.The authors note that measured efficiency can exceed 1 if benchmarked code outperforms a reference. They also identify time–space trade-offs as a challenge for extending evaluation to space efficiency, and describe limitations of both time-complexity prediction and curve fitting.Source: §D.2 · p. 25

E.1 HUMANEVAL PROBLEM #10

• For HumanEval #10, the expert solution uses KMP to achieve Θ(|S|), compared with the HumanEval+ canonical solution’s O(|S|^2) enumeration.Source: §E.1 · pp. 25–26

E.2 HUMANEVAL PROBLEM #36

• For HumanEval #36, expert digit dynamic programming runs in Θ(log n), versus Θ(n log n) for the canonical enumeration.Source: §E.2 · p. 26

E.3 HUMANEVAL PROBLEM #40

• For HumanEval #40, hashing pair sums yields an expert O(|l|^2) solution, versus O(|l|^3) for canonical triple enumeration.Source: §E.3 · p. 27

E.4 HUMANEVAL PROBLEM #109

• For HumanEval #109, checking the at-most-one-descent condition gives O(|a|), improving on enumerating rotations in O(|a|^2).Source: §E.4 · pp. 27–28

E.5 HUMANEVAL PROBLEM #154

• For HumanEval #154, a suffix automaton finds the longest common substring in O(|a| + |b|), versus O(|b|^2|a|) for canonical rotation enumeration.Source: §E.5 · p. 28