Evaluating Language Models for Efficient Code Generation

Summary

This work proposes a methodology for evaluating efficiency of a given LLM-based code generation technique (model + prompting). It takes a selection of Python tasks from HumanEval and MBPP datasets along with a sample of reference solutions from different LLMs, and builds a benchmark by clustering these solutions on LLM-generated inputs. Crucially, the inputs to elicit different complexity clusters are generated by task-specific _programs_, themselves LLM-generated for every task. The performance score of a code-generation technique is then the average percentile of performance of its generated solutions among the clustered reference solutions for each task. The authors evaluate five families of open-weight and proprietary LLMs and demonstrate that high code correctness does not necessarily correlate with performance.

Rating

6

Confidence

4

Ethics flag

1

Reasons to accept

# Strengths * Important property to study and quantify. * The proposed approach is general enough to apply across programming languages and architectures, provided a dataset of tasks to instrument. * Exhaustive evaluation on many different LLMs, albeit with mixed results. * Using LLMs to generate input-exercising programs instead of test inputs themselves is clever and novel. Similar techniques are used in programming competitions to create challenging inputs for contestants' solutions, but to my knowledge have not been used for exercising AI-generated code.

Reasons to reject

# Weaknesses and Questions Most importantly, the proposed benchmark does not show a scaling signal, which is often a red flag for its predictive power. When scaling the model (e.g., among the tiers of CodeLlama) one would expect the efficiency of generated code to increase **if explicitly instructed to do so** (i.e., in "perf-prompted" settings). However, it actually drops according to the paper's metric even as code correctness increases - and that can be seen for almost all LLM families. The paper provides no rationale or qualitative evaluation for these observations, which in turn makes it difficult to attribute the misalignment to the evaluated models or to the benchmark methodology itself. I would expect some qualitative evaluation of examples to analyze when more powerful models generate slower code. The simple tasks of HumanEval/MBPP make such analysis possible. The input-generating technique is useful and novel, thus should be evaluated as an independent component. 1. Does the `scale` parameter actually correlate with "challenge" of the generated inputs? Do bigger values of `scale` lead to slower reference times across all tasks? 2. How do the methodology change if we simply asked for test generators parameterized with a random `seed`? Might it still elicit a useful distribution of challenging inputs?

Questions to authors

# Minor p2, line 1: "tp perform" => "performs"

Summary

This paper proposes a new framework to evaluate the efficiency of code that large language models generate. I believe the authors' vision towards improving the efficiency of LLM-generated code is good and important: as LLMs generate more code, they should generate efficient code rather than slower code. In addition, the authors evaluate almost all the recent high-performing code LMs and give a very comprehensive evaluation of these models. On the other hand, the domain of problems considered in this paper is relatively simple Python natural language to code programs. There are many more domains of programs that are optimized in real-world software engineering (such as code in different languages and performance-critical programs) that are not covered in this benchmark, which somewhat limits the scope of the work. The paper, however, is relatively well-written and easy to follow. I would be more inclined to recommend acceptance of this work if it covered a wider variety of performance improvements and/or a more detailed analysis that revealed more insights of performance features of LLM generated code.

Rating

5

Confidence

4

Ethics flag

1

Reasons to accept

- The paper focuses on a new angle in the evaluation of LLMs for code, namely program efficiency. Given that there are very few works looking at program efficiency, this benchmark could provide a valuable signal as more of these techniques appear. - The authors do a comprehensive study of a variety of models consisting of different sizes, both open and closed source models, which provides information on the effectiveness of different classes of models in generating optimized code. - The DPS technique is relatively general and can be applied to all sorts of coding problems.

Reasons to reject

- The size of EvalPerf is small, and there is no analysis of the variance of model scores on the benchmark. For example, it is hard to determine whether differences in the benchmark are statistically significant. - While the paper uses prompt-based methods to try and evaluate the abilities of current language models, a more thorough attempt at asking models to generate efficient code would have been helpful. - Scores on the benchmark are relatively high (e.g. in the 90s). The authors, however, note that DPS is a general technique that can be applied to other problems. However, the authors do not show any application of DPS to problems other than HumanEval and MBPP, which are relatively simple and already mostly saturated by the best models. - There is no qualitative analysis

Questions to authors

- To me, there are two types of efficiency: algorithmic efficiency (e.g. O(n^2) to O(n) optimizations) and smaller, code-level optimizations (e.g. changing the order of for loops in matrix multiplication). The first is more focused from an algorithmic level, while the second is generally done after writing a piece of code and profiling it. Why do you decide to unify both of these under one benchmark? - Can you more clearly differentiate the contributions of your benchmark from those of PIE (Shypula et al. 2023)? What insights do you believe your benchmark reveals that theirs does not?

Summary

This paper attempts to create a benchmark for performance evaluation of generated programs by utilizing existing sets of programs and seeing how well the model performs with respect to these. Overall, I definitely liked the paper and think that it could potentially be a good contribution to the conference.

Rating

7

Confidence

4

Ethics flag

1

Reasons to accept

The paper is tackling a problem that has not gotten enough attention in the literature. The "Synthesizing a Synthesizer" framework is clever, I like it! Overall, the methodology and evaluation both are pretty solid. This was definitely the most well-done paper in my batch of reviews at COLM in this regard.

Reasons to reject

I still like this paper and think it should be accepted, but I did have a few concerns. --- Major comments One major concern that I had with the methodology, however, is that it seems that performance is only measured on programs where the answer is correct? If tht is the case, doesn't that introduce a major confounding factor that weaker models may generate answers to only the simpler programming problems, which are also easy to generate efficient solutions for? It seems that in order to rigorously compare two models with respect to their performance, the models would have to be compared across the same set of programs (so probably take the intersection of the sets of correct programs generated by the two models). I wonder if the authors Another concern is that I found the methodology complex and pretty difficult to follow -- I hope that the clarity of the paper could be improved before it is finally published. Specifically, I found sections 2.4 and 2.5 pretty hard to follow due to their completxity and brief description. I was able to mostly understand them after a careful reading, but I would definitely encourage the authors to re-read these sections and try to make them clearer. Specific comments: - Adding an illustrative example (e.g. to Figure 3) of the time1d, rdiff, and splitters values would be helpful to better understand. - "mean execution time" is referenced in 2.4 before it is explained in 2.5, which made it confusing. - Is "base" a typo for "bias"? - Unless I missed it, it seems "cumulative ratio" is not defined anywhere? This is an important concept, and it was a bit hard for me to understand the methodology without knowing what this means. --- Minor comments But one possible issue with it is that it tries to generate inputs that would test the efficiency of the ground-truth solution (since the ground-truth solution is provided in the prompt). Programs other than the ground truth solution may be slow in different ways, and it is not guaranteed that this method would find inputs that exercise these other programs. Did you consider also generating programs that exercise the LLM-generated solutions instead? One limitation of this work is that it only uses HumanEval and MBPP as inputs, which use the Python standard library only. It is not clear if this framework would scale up to testing more complex programs that rely on external libraries (like numpy or or PyTorch). It'd be good to at least mention this fact in the paper.

Questions to authors

--- Small typo fix suggestions which is pervasively available on most platforms -> which is available on most platforms the new solution (in the green box) matchs -> the new solution (in the green box) matches improving the the worst case scenario -> improving the worst case scenario There is a place that says "Compared to software profilers such as architecture simulators, hardware counters provides low overhead (Wikipedia, 2024)", but I would suggest a reference other than Wikipedia, as Wikipedia is generally a secondary source rather than a primary authoritative source. There is a place where you say "It is worth noting that our scoring mechanism is agnostic to different efficiency measurements." in section 5. It is not clear what this means -- don't the results of your method vary depending on the architecture used for measurment (in section 4.2)? Maybe instead of "agnostic", "robust" would be a more appropriate word?

Summary

This paper introduces Differential Performance Evaluation (DPE), a framework for assessing the efficiency of code generated by LLMs. Unlike traditional benchmarks, DPE focuses on real-world efficiency-demanding tasks and provides a reliable metric for evaluation. By transforming coding tasks and creating the EVALPERF benchmark, the authors highlight insights into the impact of model sizes, instruction tuning, and prompting on code efficiency. The paper's evaluation underscores DPE's simplicity, speed, and cross-platform reliability, marking a significant advancement in code generation evaluation.

Rating

7

Confidence

3

Ethics flag

1

Reasons to accept

1. The paper considers an interesting and important problem. 2. The paper proposes a novel framework for assessing the efficiency of code generated by LLMs. 3. The paper presents EVALPERF, including 121 performance-exercising programming tasks and test inputs.

Reasons to reject

1. The paper could potentially benefit from a more extensive comparison of EVALPERF Benchmarks across different open-source LLMs. 2. To enhance the paper, releasing the code used to reproduce the results would be beneficial.

Questions to authors

n/a

Thank you for the reply

Thank you for the reply, I appreciate the additional details and think adding them to the paper could be useful.