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

Thank you so much for your thorough review and interesting questions. We believe that your questions will greatly help to improve the quality and clarity of this paper. We answer your questions as follows.

W1 Part a: The novelty of the proposed eff@k metric is not convincing. The authors mention the insufficiencies of existing efficiency benchmarks in C1 and C2. (a) For C1, the authors mention that if the code execution exceeds the time limit, the actual efficiency is unknown. However, the authors do not demonstrate how frequently this happens in practice. If this is a rare case, then existing benchmarks are still useful. The authors should provide experimental evidence to demonstrate that existing works do give wrong efficiency measurements due to the presence of such cases.

Q2: Do the eff@k metric and the existing efficiency metrics give different efficiency rankings for the same LLM-generated code?

Thank you for the great suggestion. We have added an experiment to compare our eff metric and the most popular metric speedup [1] (i.e., execution time of reference solution / execution time of generated code). The table below shows rankings of LLMs under our eff metric and the speedup metric, respectively. We can see that eff and speedup give very different rankings. In particular, under the speedup metric, Mixtral and Llama 3 even seems to outperform GPT-4, which is inconsistent with commonsense knowledge.

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 in Challenge C1.

In fact, the time limits are exceeded very frequently in our evaluation, thanks to our high-quality reference solutions and challenging test cases. For example, even for GPT-4, 16% of its generated code exceeded the time limit in our evaluation; for Mixtral 8x22B Instruct, 23% of its generated code exceeded the time limit. Therefore, it is necessary to propose our eff metric to more rigorously handle right-censored execution time. We have added this experiment to Appendix B.

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

Q1: Why is the maximum efficiency value chosen in the eff@k metric, rather than the average efficiency value?

We are afraid this is a misunderstanding. In fact, the average efficiency value over n samples is exactly our proposed n-sample estimator for eff@1 (a special case of our Rao--Blackwellized eff@k). If one wants to find the average efficiency over n samples, then they can choose the n-sample estimator for eff@1; if one wants to find the expected best efficiency over k samples using n samples, then they can choose the n-sample estimator for eff@k.

W4 Part a: The benchmark suite is limited only to the HumanEval dataset. This concerns about the generalizability of ENAMEL. The HumanEval dataset contains many simple tasks that require time complexity. A potential concern is that the dataset after filtering out those simple tasks may not be large enough to provide a comprehensive evaluation of the efficiency of LLM-generated code. (a) The authors should provide the size and proportion of the remaining tasks after filtering out the simple tasks.

Q4: What is the size of the ENAMEL benchmark suite?

We would like to provide the following clarificaitons. As mentioned in Section 1 and Section 3.1, our benchmark has 142 problems, which is 87% size of HumanEval (164 problems). In fact, only 22 problems in HumanEval have O(1) time complexity; all other 142 problems have higher time complexities. In other words, our benchmark has a comparable size to HumanEval. Our human expert has manually inspected all these 142 problems. % which makes our benchmark a valuable resource for efficiency evaluation due to the following reasons.

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

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

Therefore, we believe that our 142 problems offer a comprehensive evaluation of LLMs' capability in generating efficient code.

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

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

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

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

Q6: How does the eff@k metric perform on different test case generation strategies?

Thank you for the great question. In fact, the strength of our test case generators have been ensured by our human expert. Even though worst cases might be hard to identify for real-world problems, it is not hard for our human expert to identify worst cases for HumanEval problems because these problems are well defined. As discussed in Section 3.3, our human expert will add worst cases for any possible algorithm, including non-trivial worst cases. For example, for problem #31 (deciding if a number is prime), the Fermat primality test (generated by Code Llama 13B Python) is an efficient yet wrong algorithm with only a few non-trivial counterexamples called Carmichael numbers (Carmichael, 1912).

To further demonstrate the strength of our expert-written test case generators, we provide a case study comparing our strong generator and the random generator for the problem #31 mentioned above. We compare the eff@1 metrics under our test case generator and the random generator for two solutions ((i) Factor: the naive factorization algorithm, which is correct but inefficient; (ii) Fermat: the Fermat primality test, which is efficient but wrong), respectively. The results are shown in the table below. 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. We have added this experiment to Appendix B.

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

Q3: How sensitive is the eff@k metric to the hyperparameters?

Thank you for the great question. Regarding alpha, alpha represents the tolerence to execution time (i.e., the execution time limit is proportional to alpha). Thus, if one wants to tolerate less efficient code, then they can use a larger alpha. Regarding h, 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 alpha=2, h1=3, 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 affected by alpha and h, we report the eff@1 of GPT-4 Turbo under different alpha, h1, h2, and h3. Results are shown in the tables below. We can see that eff@1 increases as alpha increases (because alpha represents the tolerence 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 in terms of the tolerance to execution time vs. weights across different levels. We have added this experiment to Appendix B.

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

Q5: How does the ENAMEL benchmark perform on more competitive datasets, such as the CodeContests dataset?

Thank you for the great question. As mentioned above, our main concern about using online judge datasets like CodeContests is that their public solutions are already in LLMs' pretraining corpuses. For example, DeepMind's AlphaCode (Li et al., 2022) has been trained on the CodeContests dataset. If we evaluate LLMs on these public online judges, then the evaluation results may fail to reflect the LLMs' true capabilities due to potential memorization.

To evaluate LLMs' true capabilities, we decided to employ human expert to manually write our reference solutions to ensure a rigorous evaluation. As a result, we have successfully revealed that even the strongest LLMs (e.g., GPT-4) still fall short of generating expert-level efficient solutions.

Nevertheless, we with the reviewer in that extending the benchmark suite to more competitive datasets will be a very interesting future direction. A possible workaround is to collaborate with competitions whose solutions are not publicly available. We have added a discussion to Appendix D.

---

References:

• Carmichael. On composite numbers p which satisfy the Fermat congruence. The American Mathematical Monthly, 19(2):22-27, 1912.
• Li et al. Competition-level code generation with AlphaCode. Science, 378(6624):1092-1097, 2022.
• Austin et al. Program synthesis with large language models. Google Research, 2021.
• Rozière et al. Code Llama: Open foundation models for code. Meta AI, 2023.

W3: Why didn't you consider problems from online judges like codeforces? There are plenty of problems with expert-level efficient solutions as a competition-oriented platform.

Thank you for the great question. As mentioned in W1, our main concern about using online judges is that their public solutions are already in LLMs' pretraining corpuses. For example, DeepMind's AlphaCode [1] has been trained on many online judges including Codeforces, CodeChef, HackerEarch, Aizu, and AtCoder. If we evaluate LLMs on these public online judges, then the evaluation results may fail to reflect the LLMs' true capabilities due to potential memorization.

To evaluate LLMs' true capabilities, we decided to employ human expert to manually write our reference solutions. As a result, we have successfully revealed that even the strongest LLMs (e.g., GPT-4) still fall short of generating expert-level efficient solutions.

Nevertheless, we still agree with the reviewer that extending the benchmark suite to more competitive datasets will be a very interesting future direction. As we mentioned in W1, a possible workaround is to collaborate with competitions whose solutions are not publicly available. We have added a discussion to Appendix D.

W4: Did you consider a more automatic way of measuring the complexity? It might not be hard to find out that multiple layers of input scale, simply considering log scales, polynomial scales, and exponential scales.

Thank you for the interesting question. In this work, we focus not only on time complexity but also on implementation optimization. Even though two solutions have the same complexity, the optimized implementation can sometimes significantly outperform the non-optimized one. 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. As shown in Table 4, LLMs still fall short of generating efficient code for seemingly easy problems (the Implementation Optimization Subset). Therefore, we did not use any approach to measure the time complexity only.

That said, we agree with the reviewer in that developing an automatic method to measure the time complexity will be a very intersting future work. Although this might require an indepdent new study, there are two possible approaches (although both of them have limitations):

• Time complexity 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 general difficult for LLMs (and even diffcult for non-expert humans). For example, the Splay tree [4] seems to have O(n) time complexity per operation, but a sophisticated analysis by the authors shows that it actually has O(log n) time complexity per operation.
• Fitting a time curve: Another possible approach is to fit a curve of the running time vs $n$ 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 AKS primality test [5] runs in $\tilde O((\log n)^{12})$ time, so the curve of its running time vs $n$ looks extremely like an exponential function for any practical $n$ (it cannot even decide whether $n=50$ is a prime number within reasonable time).

We have added a discussion on automatic measurement of time complexity into Appendix D.

---

References:

• [1] Li et al. Competition-level code generation with AlphaCode. Science. 378(6624):1092- 1097, 2022.
• [2] Austin et al. Program synthesis with large language models. Google Research, 2021.
• [3] Rozière et al. Code Llama: Open foundation models for code. Meta AI, 2023.
• [4] Sleator et al. Self-adjusting binary search trees. Journal of the ACM, 1985.
• [5] Agrawal et al. PRIMES is in P. Annals of Mathematics. 160(2):781–793, 2004.

Thank you so much for taking the time to provide such an insightful and inspiring review. We highly appreciate that you recognize the clear presentation of this paper, our rigorously design efficiency metric, and our convincing evaluation results. We believe that your comments will greatly improve the quality of this paper. We provide our response below.

W1: The method is very manual. It is hard to scale.

As discussed in Appendix D, we agree that our current expert-based approach has a scalability limitation because we primarily focus on ensuring a high-quality dataset. We believe that crafting the benchmark by human expert is necessary to develop a high-standard and rigorous benchmark. For example, as shown in Table 2, compared with our expert solutions, HumanEval canonical solutions achieve only eff@1=0.455, and HumanEvalPlus canonical solutions achieve only eff@1=0.513. This shows that their canonical solutions are far less efficient than our expert-written reference solutions.

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

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

W2: The dataset is small. Humaneval was a good metric several years ago at the early stage of code generation. But now, serious evaluation needs a larger scale dataset.

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

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

That said, we still agree with the reviewers that developing a larger benchmark is an important future direction. As we mentioned in W1, a possible solution is to collaborate with private programming competitions whose solutions are not publicly available. We have added a discussion to Appendix D. Thank you again for the great suggstion.

The following are results for Experiment II in W2.

(ii) Revealing the efficient algorithm in the prompt

In (i), we have shown that LLMs are unable to come up with the dynamic programming 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. The raw outputs are attached below for your reference. 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 the code inefficiency is essentially a capability limitation of existing LLMs, 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.

---

Output of Llama 3 70B Instruct:

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))  # 0
print(fizz_buzz(78))  # 2
print(fizz_buzz(79))  # 3
```

Output of Mixtral 8x22B Instruct:

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))  # Output: 0
print(fizz_buzz(78))  # Output: 2
print(fizz_buzz(79))  # Output: 3
```

The following are results for Experiment II in W2.

(i) Self-Refine prompting (Madaan et al., 2023)

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." The code before and after Self-Refine is attached below for your reference. 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.

---

Initial code by Llama 3 70B Instruct:

def fizz_buzz(n: int) -> int:
    """Return the number of times the digit 7 appears in integers less than n which are divisible by 11 or 13."""
    count = 0
    for i in range(n):
        if i % 11 == 0 or i % 13 == 0:
            count += str(i).count('7')
    return count

Refined code by Llama 3 70B Instruct:

import math

def fizz_buzz(n: int) -> int:
    """Return the number of times the digit 7 appears in integers less than n which are divisible by 11 or 13."""
    return sum(str(i).count('7') for i in range(n) if math.gcd(i, 11 * 13) in (11, 13))

Initial code by Mixtral 8x22B Instruct:

def fizz_buzz(n: int) -> int:
    count = 0
    for i in range(11, n, 1):
        if i % 11 == 0 or i % 13 == 0:
            count += str(i).count('7')
    return count

Refined code by Mixtral 8x22B Instruct:

def fizz_buzz(n: int) -> int:
    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

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

Thank you for the great question. This is due to a statistical consideration.

As LLMs' autoregressive generation is a random process, the eff@k metric is actually a random variable. If eff@k has a high variance, then the accuracy of the observed eff@k will not be guaranteed. To theoretically guarantee an accurate estimation, we need to reduce the variance of the eff@k estimator. Therefore, we employ Rao--Blackwellization to reduce the variance of the eff@k estimator. As shown in Theorem 1, if we use n code samples to estimate eff@k, then the variance of the Rao--Blackwellized estimator will be k/n times the variance of the original estimator. Hence, increasing n reduces the variance of the eff@k estimator and thus gives a more accurate estimate of LLMs' capabilities.

To demonstrate that Rao--Blackwellization does reduce the variance of the eff@k estimator, we empirically compute the standard deviation (i.e., sqrt of variance) of the vanilla eff@k estimator and our Rao--Blackwellized eff@k estimator (RB) using the Llama 3 70B Instruct model. Results are shown in the table below. We can see that the RB estimator achieves much lower standard deviation than the vanilla estimator. Therefore, our Rao--Blackwellized estimator empirically ensures a more accurate estimation of eff@k. We have added this experiment to Appendix B.

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

Thank you for pointing out this. By "sporadic" we just meant that the number of efficiency benchmarks (e.g., EffiBench, ENAMEL) is much fewer than the number of correctness benchmarks (e.g., HumanEval, HumanEval+, MBPP, APPS, DS-1000, MultiPL-E, CoNaLa, and many more). We agree with the reviewer that EffiBench is a nice large-scale benchmark for efficiency evaluation.

To clarify this, we have revised "sporadic attempts" into "a few benchmarks" in Section 1.

Q3: Does it make sense to also consider space complexity in your benchmarks? For example, ... a suggested solution uses two pointers, has the same time complexity, and reduces space complexity from O(n) to O(1).

Thank you for the great suggestion. While our current benchmark focuses on evaluating time efficiency, we believe that evaluating the space efficiency would be a very interesting and important future research direction. For example, EffiBench 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. We may need to provide different reference solutions for time evaluation and space evaluation. We have added a discussion to Appendix D.

Regarding your suggested solution, we chose the set-based solution because it is more time-efficient in Python (although it is a bit less space-efficient than the two-pointer solution). For instance, for $n=600$, our set-based solution runs in 6 ms while the two-pointer solution runs in 29 ms. As we discussed in Section 3.2, we care about not only time complexity but also implementation optimization. The set in Python is very efficient, so the set-based solution runs faster than the two-pointer solution in Python. This example also demonstrates why we employ human expert to develop this benchmark. (On the other hand, if our goal were to evaluate space efficiency, then the two-pointer solution would be a better reference solution.)

---

References:

• Amdahl. "Validity of the single processor approach to achieving large scale computing capabilities." Proceedings of the April 18-20, 1967, Spring Joint Computer Conference. 1967.
• Madaan et al. Self-Refine: Iterative refinement with self-feedback. 2023.
• Niu et al. On evaluating the efficiency of source code generated by LLMs. 2024.

Thank you so much for your time to provide a detailed and insightful review. We are delighted that you appreciate the clear presentation of this paper, our rigorous treatment of execution timeout, and our high-quality reference solutions and test case generators. Besides that, we believe that your questions will greatly help to improve this paper. We answer your questions as follows.

W1: I would appreciate a comparison with previous metrics, even the naive ones, to see whether the empirical effect of this new metric is that models/problems are given a different ranking.

Thank you for the great suggestion. Per reviewer's request, we have added an additional experiment to compare our eff metric and the most popular metric speedup (Amdahl, 1967; i.e., execution time of reference solution / execution time of generated code). The table below shows rankings of LLMs under our eff metric and the speedup metric, respectively. We can see that eff and speedup give very different rankings. In particular, under the speedup metric, Mixtral and Llama 3 even seems to outperform GPT-4, which is inconsistent with commonsense knowledge.

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 in Challenge C1.

In fact, the time limits are exceeded very frequently in our evaluation, thanks to our high-quality reference solutions and challenging test cases. For example, even for GPT-4, 16% of its generated code exceeded the time limit in our evaluation; for Mixtral 8x22B Instruct, 23% of its generated code exceeded the time limit. Therefore, it is necessary to propose our eff metric to more rigorously handle right-censored execution time. We have added this experiment to Appendix B.

W2: Not evaluated with a prompt that asks for an efficient solution, I suspect that a better prompt would make this entire suite too weak for being a competitive benchmark.

Thanks for this interesting suggestion. While thoroughly studying how to enhance efficiency is beyond the scope of this paper and probably requires another investigation, here we provide two experiments of prompt engineering as follows to better answer the reviewer's question.

Experiment I. We use the two strongest open-source LLMs Llama 3 70B Instruct and Mixtral 8x22B Instruct from our Table 3 (main results). We ask the LLM to generate "the most efficient algorithm" and use greedy decoding to obtain outputs. The evaluation results are presented below.

The results show that simple 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. We believe that prompting alone does not fully address the code efficiency issue because this is essentially a fundamental capability limitation of existing LLMs---the efficient algorithm can be highly non-trivial so that existing LLMs do not understand well. To demonstrate this, we have conducted a case study for a hard problem (#36) under the following two settings: (i) Self-Refine prompting (Madaan et al., 2023) 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). Since the outputs are too long, the complete outputs are attached at the end of our response. We can see that, no matter whether we use (i) or (ii), the generated code is an inefficient algorithms in $O(n)$ time, which is far from the optimal $O(\log n)$ time complexity.

We have added these two interesting experiments to Appendix B.

Thank you for your great suggestions. We are grateful that you appreciate the importance of efficiency evaluation, the comprehensiveness of our evaluation, and the high quality of our expert-written reference solutions. We believe that your suggestions will considerably improve the clarity of this paper. We provide our response below.

W1: While the proposed work is important, and while the results are interesting, I don’t believe the contribution and novelty of the work are strong enough. There is clearly a degree of novelty in this paper though, and the proposed benchmark is very valuable from a practical point of view. The problem of measuring the performance of code is well-studied in the compiler community. There are decades of work on the development of methods for automatic code optimization in compilers and methods to measure the success of such methods. Any paper about automatic code optimization. Here is one example of such work: “Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques”, Sid Touati. It would be interesting to include examples of such work in the related work section and also include a detailed discussion in the paper about why a simple metric such as “the speedup” (ratio between the execution time of the reference code over the execution time of the synthesized code) is not enough for this problem and a new metric needs to be proposed.

Q1: Can you please include a detailed discussion of why the the speedup metric classically used by the compiler community when evaluating automatic code optimization methods is not enough for your task?

Thanks for the great question. As we discussed in Challenge C1, when code execution is early terminated due to time limit, its actual execution time is unknown. For instance, if the generated code contains an infinite loop, the observed execution time will be clipped to the time limit, while the actual execution time should be infinity. We cannot use the actual execution time in the speedup metric here because the actual execution time is unknown. Meanwhile, if we directly use the clipped execution time in the speedup metric, it will overestimate the efficiency of the code. That is why we use our eff metric instead of speedup in our evaluation.

To empirically justify our eff metric, we further added an experiment to compare our eff metric and the speedup metric. The table below shows rankings of LLMs under our eff metric and the speedup metric, respectively. We can see that eff and speedup give very different rankings. In particular, under the speedup metric, Mixtral and Llama 3 even seems to outperform GPT-4, which is inconsistent with commonsense knowledge.

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 in Challenge C1.

In fact, the time limits are exceeded very frequently in our evaluation, thanks to our high-quality reference solutions and challenging test cases. For example, even for GPT-4, 16% of its generated code exceeded the time limit in our evaluation; for Mixtral 8x22B Instruct, 23% of its generated code exceeded the time limit. Therefore, it is necessary to propose our eff metric to more rigorously handle right-censored execution time. We have added this experiment to Appendix B.

Q2: For more completeness, can you also include a discussion of such work in the related work section? A starting point would be: “Towards a Statistical Methodology to Evaluate Program Speedups and their Optimisation Techniques”, Sid Touati.

Thank you for pointing out this interesting future work. We have added a discussion of this paper and related papers into Section 5.

Dear Reviewer t6vW,

Apologies for the follow-up reminder.

As today (Dec 2) is the last day for reviewers to post follow-up comments, we would like to confirm whether our responses have adequately addressed your concerns. Please let us know if you have any additional questions or require further clarifications—we would be very happy to answer them.

Thank you for your time and feedback.