Learning Performance-Improving Code Edits
Authors: Alexander G Shypula
Aman Madaan
Yimeng Zeng
Uri Alon
Jacob R. Gardner
Yiming Yang
Milad Hashemi
Graham Neubig
Parthasarathy Ranganathan
Osbert Bastani
Amir Yazdanbakhsh
Venue: ICLR 2024 spotlight (2024)
Keywords: Large Language Models
Retrieval Augmented Generation
Program Synthesis
Program Optimization
Fine-Tuning
Goal-Conditioning
Data Augmentation
Self-Play
Synthetic Dataset
Performance Optimization
Machine Learning for Code Optimization
Dataset
Primary area: datasets and benchmarks
TL;DR: We introduce a benchmark for reproducible research on neural program optimization, evaluate the capabilities of LLMs, and present three effective strategies for program optimization, achieving up to average 6.86X times speedup with our best model

Abstract: With the decline of Moore's law, optimizing program performance has become a major focus of software research. However, high-level optimizations such as API and algorithm changes remain elusive due to the difficulty of understanding the semantics of code. Simultaneously, pretrained large language models (LLMs) have demonstrated strong capabilities at solving a wide range of programming tasks. To that end, we introduce a framework for adapting LLMs to high-level program optimization. First, we curate a dataset of performance-improving edits made by human programmers of over 77,000 competitive C++ programming submission pairs, accompanied by extensive unit tests. A major challenge is the significant variability of measuring performance on commodity hardware, which can lead to spurious "improvements." To isolate and reliably evaluate the impact of program optimizations, we design an environment based on the gem5 full system simulator, the de facto simulator used in academia and industry. Next, we propose a broad range of adaptation strategies for code optimization; for prompting, these include retrieval-based few-shot prompting and chain-of-thought, and for finetuning, these include performance-conditioned generation and synthetic data augmentation based on self-play. A combination of these techniques achieves a mean speedup of 6.86$\times$ with eight generations, higher than average optimizations from individual programmers (3.66$\times$). Using our model's fastest generations, we set a new upper limit on the fastest speedup possible for our dataset at 9.64$\times$ compared to using the fastest human submissions available (9.56$\times$).

Published as a conference paper ICLR 2024
LEARNING PERFORMANCE-IMPROVIN CODE EDITS
Alexander Shypula'; Aman Madaan"; Yimeng Zeng', Uri Alon', Jacob Gardner', Milad Hashemi', Graham Neubig". Parthasarathy Ranganathan', Osbert Bastani', Amir Yazdanbakhsh*
'University of Pennsylvania, CCrnneii Mellon University, 'Google "Google DeepMind seapula@seas... upenn edu and ayazdan@google. com
ABSTRACT
With the waning of Moore's law, optimizing program performance has become a major focus of software research. However, high-level optimizations such as API and algorithm changes remain elusive due to the difficulty of understanding the semantics of code. Si- multaneously, pretrained large language models (LLMs) have demonstrated strong capa- bilities at solving wide range of programming tasks. To that end, we introduce a frame- work for adapting L.IMs to high-level program optimization. First, we curate a dataset of performance-improoing edits made by human programmers of over 77 K competitive C++ programming submission pairs, accompanied by extensive unit tests. A major challenge is the significant variability of measuring performance commodity hardware, which can lead to spurious "improvements". To isolate and reliably evaluate the impact of pro- design environment based the gem5 full system simulator, the de facto simulator used in academia and industry. Next, we propose broad range of adaptation strategies for code optimization; for prompting, these include retrieval-based few-shot prompting and thain-offthoouge conditioned generation and synthetic data augmentation based on self-play. A combination of these techniques achieves mean speedup of 6,86x with eight generations, higher than average optimizations from individual programmers (3.66x). Using our model's 's fastest generations, we set a new upper limit on the fastest speedup possible for our dataset at 9.64 x compared to using the fastest human submissions available (9.56x)
gram optimizations,
and for finetuning, these include performance-
1 INTRODUCTION
Despite the impressive progress of optimizing compilers and other tools for performance engineering (Aho (et al. 2007). programmers are still largely responsible for high-level performance considerations such as algorithms and API choices. Recent work has demonstrated the promise of deep learning for automating performance optimization (Garg et al. 2022, Mankowitz et al. (023). However, these techniques are either narrow or difficult to build on due the lack of open datasets and lack of reliable performance measure- ment techniques, which has stymied research in this direction. Recently, pre-trained large language models (LL.Ms) have demonstrated impressive performance at wide range of programming tasks (Chen et al.) 2021b Fried et al., 2022 Xu et al.) 20222 Nijkamp et al., 2022). Yet, the effectiveness of large, pre-trained LLMs for program optimization remains an open research question. We study whether such LLMs can be adapted for performance optimization. To this end, we introduce a novel benchmark for performance opti-
"Equal contribution.
Coode: https::/ pettps://pie4perf.co

---

Published as conference paper ICLR 2024
#inolude
using nanespace std;
Finclude <iostream using nanespace std;
int main!)
int
int main ()
int 0:
sin >> 17
cin nJ
ny s++)
return 0J
17
cour <s sum endl;
(a) Slower Code.
(b) Faster Code.
Figure 1: An example of program that solves the problem of "compute the sum of the numbers from N The program on the left runs in O (N), whereas the program on the right runs in constant time. The goal of PIE enable L.LMs to perform these kinds of program optimizations.
mization that addresses the key challenge of replicable performance measurement, and perform an extensive evaluation of wide range of adaptation techniques based on
First, we construct dataset of Performance Perfornance-mpproving Edits (PIE). We collect C++ programs written to solve competitive programming problems, where track a single programmer's s submissions as they evolve over time, filtering for sequences of edits that correspond to performance improvements.
Next, major challenge the significant variability of measuring performance on real hardware due to server workload and configuration issues. Indeed, we find that benchmarking on real hardware can lead to large, phantom performance "improvements" due only to random chance. To address this challenge, we evaluate performance using the gem5 CPU simulator (Binkert et al. 2201). the gold standard CPU simulator academia and industry, and models state-of-the-ard is entirely deterministic, ensuring both reliability and reproducibility.
processors. This evaluation strategy
Based on this benchmark, we evaluate a variety of techniques for adapting pre-trained code LLMs for per- formance optimization. First, consider baseline prompting approaches, including techniques such chain-of-thought (Wei et al.) 2022b) (CoT). We find that LLMs are limited in the challenging task of code optimization. Without data-driven methods that leverage PIE, our strongest baseline CoT only warrants 1.60x average speedup over 8 submissions vs. the 3.66x human reference. Next we consider a retrieval- based prompting approach where retrieval is used select examples most similar to the current
(Liu ct al.] 2021 Poesia et al., (202T). Lastly, we consider several finetuning strategies: these include using syn- thetic data generated via self-play (Haluptzok et al. 2022). where synthetic training examples are generated by an LLM without the need for direct human examples, as well as performance-conditionn generation, where we condition generation on the performance of the generated program.
We find that data-driven methods using PIE, like serievall-bsed few-shot prompting and fine-tuning, are highly effective achieving strong optimization abilities in LLMs. When allowing model to take 8 samples and filtering for correctness and execution time, our fine-tuned performance-conditioneed version of CODELLAMA 13B can achieve an average speedup 5.65x on our test set, and a fine-tuned version of GPT-3.5 augmented with synthetic data via self-play achieves average speedup of 6.86x, the average individual human sampled in our test set achieved an average speedup human submissions in the test set with higher sampling budget, GPT-3.5 achieved speedup of 9.64 and surpassed the best human submissions across all programmers with a speedup of 9.56x. In summary, our contributions are:
3.66x. Aggregating over all
2

---

Published as a conference paper ICLR 2024
We introduce new code dataset of more than 7 C++ program pairs, named PIE, with execution time annotations collected from the gem5 simulator. PIE enables reproducible evaluation of LLMs for program optimization and reliable performance annotations for training.
Enabled by our benchmark, we evaluate different prompting and fine-tuning approaches for adapting pre-trained LLMs to optimize programs. Our results indicate that pre-trained code LLMSs are limited in their ability to optimize code without dataset like PIE.
We develop three effective strategies for adapting LLMs for code optimization: retrieval-based prompt- ing, irfformancc-conditioninn thetic data obtained from self-play, achieves an average speedup of 6.86x, and optimizes 87.63% of the test set by at least 10%.
and self-play. Overall, our best model, GPT-3.5 augmented with syn-
2 PERFORMANCE IMPROVING EDITS (PIE) DATASET
We construct dataset targeted at adapting code LLMs to performance optimization, focusing on optimizing program execution time. Our dataset is constructed based on performance-impen human programmers in range of competitive programming tasks from CodeNet (Puri et al. 2021). We exclusively focus on C++ programs since it is a performance-oriente simulator. Given problem, programmers typically write an initial solution and iteratively improve it. Let Y = -/ :..] be a chronologically sorted series of programs, written by user u for problem æ. From Yo we remove programs that were not accepted by the automated system, eliminating incorrect programs (fail one or more unit tests) or take more than the allowed time to run, resulting in a trajectory of programs Y [ 12...... V.l--
edits (PIE) made by
language compatible with the gem5
For each trajectory Y we construct pairs IP = (31,82), (311 (32, ya).... and keep only pairs for which Lime(ys)
> 10% where time (y) is the measured latency of program y (i.e., the relative time improvement is more than 10%). The CodeNet dataset includes CPU time, but found the information be inconsistent (see Appendix A.99.. Thus, we relabel the execution time using gem5 as described below; to create these annotated runtimes, we performed over 42.8 million simulations in our gem5 environment.
We split the resulting dataset of pairs IP into train/validationntesss sets, ensuring that any particular competitive programming problem only appears in one of them. We obtain training set of 77.967 pairs from 1,474 problems, a validation set of 2,544 pairs from 77 problems, and a test set of 978 pairs from 41 problems. For each pair in the test set, we also record the fastest human submission execution time for that problem; Section we include this running time as a comparison point.
Test cases. Our goal is to improve performance while ensuring correctness. We evaluate correctness through unit tests; we reject the program if a single test fails. CodeNet includes an average of 4 test cases per problem. To improve coverage, we include additional test cases from AlphaCode (Li et al., 2022) generated with a fine-tuned I.M.. A small set of test cases would lead to substantial timeouts above 2 minutes in gem5; after excluding them, we obtain a median of 82.5 test cases per problem in our training set, 75 test cases per problem in our validation set, and 104 test cases per problem for our test set (Appendix A.5).
Performance measurement using gem5. Benchmarking program performance is notoriously difficult. For instance, code instrumentation introduces overhead, and there is substantial variance across executions due to factors such as server load and idiosyncrasies introduced by the operating system. If benchmarking is not performed carefully, it is easy mistakenly over-report program optimization results. With enough samples and variance, benchmarking the same exact program can easily lead us to report significant optimizations.
To illustrate the challenges, consider HYPERFINE (Peter 2023 Rust library designed precisely bench- mark binaries. We benchmarked 500 programs "pairs" where the "slow" and "fast" programs are identical. (i.e., the two programs have identical performance). However,
Ideally, we should have time
larget time
3

---

Published as a conference paper ICLR 2024
observed mean speedup of 1.12x, with standard deviation of 0.36, and the top 5% of pairs exhibited a speedup of x.91 These results underscore the significant challenges in performance measurement.
To address this challenge, we measure program performance using the gem5 (Binkert et al. (011)) full system simulator, which provides detailed microarchitectural emulation of modern processors. Executing deterministic programs in gem5 provides deterministie performance results. This enables reproducibility in research and denoised performance measurements 2 We use the Verbatin im configuration of the Intel Skylake architecture from gem5 An advantage of this approach is that our framework can be applied to other platforms like ARM or RISC-V without having access to hardware for those platforms.
3 ADAPTING CODE LLMS TO PROGRAM OPTIMIZATION
3.1 FEW-SHOT PROMPTING
Instruction-rrompting We use prompts instructing the LLM to improve the performance of the given
program, an approach commonly referred to as instruction prompting (Mishra et al. 2021 Gupta et al.
2022
Longpre et al. 2023); details on the prompt are in Figure 12 in Ap
Few-shot prompting. Next, we use few-shot prompting (Brown et al. 2020). In particular, we create a
prompt with the format "slow, - fast; slow2 - fasta lI Il...". A slow test set program appended to this prompt during inference and supplied to the model. We create the prompts by randomly sampling two (fast, slow) pairs from the training set (Examples of prompts in Figure 13 in Appendix(A.Il (A.1I].
Sfain-of-though prompting. Inspired by CoT (Wei et al. 2022b), we designed prompts that ask the LLM think about how optimize the program before actually producing the optimized program. This strategy is used in conjunction with few-shot prompting (Examples of prompts in Figure 14 in Appendix A1
Dynamic retrieval-based few-shot prompting. Recent work has demonstrated that retrieval-based mecha- nisms can improve language models for various tasks requiring factual or procedural knowledge (Liu et al.)
2021 Poesia et al. 2021 Rubin et al. 2022, Madaan et al., 2022] Shrivastava et al., 2023). Program opti-
mization is non-trivial task requiring knowledge of algorithms, data structures, and programming grounded in performance; thus, retrieving highly relevant examples may improve an LLM's optimization ability. For example, solution optimized for a knapsack problem in dynamic programming could inform strategies for the coin change problem. Through dynamic retrieval-based prompts, we aim to match tasks with analogous structures or challenges, allowing models to better harness the patterns in PIE. We use the CodeBertScore models trained for C++ (Zhou et al. 2023b) to embed both the program to be optimized and the programs in PIE. We use FAISS (Johnson et al. 2019) retrieve K closest programs from the training set; and construct a "slow, + fast, !I..." style prompt on the fly (See Figure 15 in Appendix
3.2 FINETUNING
We also consider fine-tuning to improve pretrained code LLMs using our PIE dataset. In addition to standard fine-tuning on the entire dataset, we describe additional strategies we used.
Dataset imbalance. While we have tens of thousands of slow-fast pairs in the PIE training dataset, these submissions target just 1,474 problems, which may limit the learned model's 's ability to generalize to new programs. Furthermore, submissions are not uniformly distributed across problems. To address this imbal- ance, we additionally lnnettne with a subset of 4,085 "high-quality" slow-fast pairs- in particular, we take
"This assumes gem5 terminates. Our experiments use a two minute timcout, which may introduce slight variability. Note that altering this timeout could change the results. https: : / //gitttuut com / haom///arcrr////mea. s
4

---

Published as conference paper ICLR 2024
examples with the highest speedup and disallow more than submission pairs per problem, for an average of 2.77 pairs per problem. Given the high costs of training models through the OpenAl API, we also use this dataset as a base for fine-tuning experiments with GPT-3.5.
generation. Programs can typically be written in many ways with different performance profiles. Consequently, when training a model predict performance-improving edits with a large dataset like PIE, it is trained a mix of large and small improvements, without any information on which improvements are more desirable than others. Inspired by recent prompting strategies (Zhang ct al. 2023) and offline-rl (Chen et al. 2021a), we introduce performance tags during training by associating each "Tast" program with tag indicating the optimal achievable performance across all solutions in the dataset. Specifically, the tag indicates how close that program is peak performance (1.2....,100 10}. We instantiate our tags by categorizing the top 10% of optimized solutions in the dataset for given task "10/10", the next 10% as "9/10", and on. These tags enable the model to discern the relationship between specific problem attributes and their corresponding high-performance solutions (Figure 2 left). During inference, we prompt the model with a test input and maximal score tag "10/10", directing it to generate highly-optimized solution (Figure2) right).
Performance-
binned-scale
This is a slow progran we want to optimize to score (score_tag//10.
This is a slow program we want to optimize to score 10/10.
BP Program: (arc_code)
## Program: (sre_codc)
### Optimized Version with score (score_tag//10:
### Optimized Version:
### Optimized Version: (fast_code)
Figure Training (left) and inference (right) prompts for Goal-Conditioned optimization with PIE.
Synthetic data. Given the high cost of obtaining human-written written programs, also augment dataset with synthetic examples through a multi-stage process. First, we prompt OpenAl's GPT-3.5 with examples from the PIE dataset, instructing it to produce novel competitive programming problems. After filtering programs with input/output behavior identical to those in PIE and tracking semantic duplicates among those generated, we obtain 3,314 unique synthetic programs and many thousand more duplicates. Using these novel programs, we then generate optimized version for each synthetic program using a GPT-3.5 model that has been fine-tuned on the original PIE dataset. Finally, we keep pairs where the optimized program is at least 5x faster and limit semantic duplicates to three, resulting in 1,485 optimized synthetic examples. This methodology aligns with self-play and self-instruct approachs neural program synthesis (Haluptzok et al. 2022 Rozière et al. 2023). We provide additional details on the generation process in Appendix A.6
4
EXPERIMENTS
Models. We evaluate and adapt models from the CODELLAMA models (Rozière et al. 2023) and models from OpenAl available through their API. We also used pretrained checkpoints of (Rozière et al. 2023): CODELLAMA 133,43B)3 obtained via HuggingFace Wolf et al. 2020). For the CODELLAMA family of models, we use the base set models that have not been instruction-tunnde as the authors of the paper note that instruction-tuning diminished the performance code generation. We provide training details
5

---

Published as conference paper ICLR 2024
Table 1: Summary of Results: This table reports our strongest performing models by SPEEDUP across different adaptation regimes covered in subsequent sections. We report results for Open-access CODELLAMA (O) and black-box or private OpenAl models (P). The highest number each column bolded and the second-highest is underscored.
Scenario
Model
%0pt
Speedup
% Corrrett
Human reference
100.00%
3.66x
100.00%
Prompt (0)
CODELLAMA 34B, CoT
19.63%
1.30x
78.73%
Prompt (P)
GPT-3.5, CoT
43.05%
1.60
91.72%
Retrieval (0)
CODELLAMA 34B
42.54%
2.43
73.62%
Retrieval (P)
GPT4
76.07%
3.93x
95.71 %
Fune (0)
CODELLAMA 13B-PC
66.56%
5.65x
70.96%
FineTTune (P)
GPT-3.5, SP
87.63%
6.86x
95.09%
We experiment with 3pt-335-turro-0661 by prompting the pre-trained model and using the fine-tuning API. We evaluate gpt-4-0613 by prompting the pre-trained model. During the drafting of this paper, fine-tuning GPT4 was available through the API.
in Appendix A.8
Metrics. To evaluate performance, we measure the following for functionally correct programs:
Percent Optimized [%OPT]: The fraction of programs in the test (out of 978 unseen samples) improved by a certain method. program must be at least 10% faster and correct to contribute.
Speedup (SPErdUp): the absolute improvement in running time. If and running times, then SPEEDUP(O. N) (+). A program must be correct to contribute.
the "old" and "new"
Percent Correct [%Correct]: The proportion of programs in the test set that are at least functionally equivalent the original program (included as a secondary outcome).
As described in Section we count program as functionally correct if it passes every test case in our dataset. Though correctness is not our primary focus, we include help interpret our results. In addition, we report our SPEEDUP as the average speedup across all test set examples. For generations that are either incorrect or slower than the original program, we use a speedup of 1.0 for that example, given that, in the worst case, the original program has speedup of 1.0. We benchmark performance using our gem5 environment and all test cases mentioned in Section 2 We compile all C++ programs with GCC version 9.3.0 and C++17 well the -03 optimization flag: therefore, any reported improvements would be those on top the optimizing compiler.
Decoding strategy. Code generation is known to benefit from sampling multiple candidate outputs for each input and choosing the best one (Li et al. 2022); in our case, "best" is the fastest program that passes all test cases. We BEST @ denote this strategy with & samples and temperature of 0.7. We present overview of our results in Table our baseline results in Table and retrieval- based few-shot prompting results in Table 3 We also calculated the upper limit for speedup for the test by aggregating the fastest submission across all submissions from CodeNet (1 (118,841 accepted solutions) versus the fastest generation from our fastest model when increasing samples 40 in Section 3.2
4.1 RESULTS FOR FEW-SHOT PROMPTING
Baseline few-shot prompting. Table 2 shows results on few-shot prompting techniques (Section 3.1
prompts in appendix A.III. We find that few-shot prompts often yield similar results compared to simple
6

---

Published as conference paper ICLR 2024
Table 2: Baselines: Results for baseline prompting strategies and models for Best@) I and @
Best@1 Speedup
@
Method
Model
%0pt
%Correct
%0pt
Speedup
*Correct
Instruction Only
CODELLAMA
0,92%
1.01
23.52%
5.21%
1.06x
68.30%
Instruction-
CODELLAMA 13B
0.41%
1.00
10.02%
2.45%
1.03x
40.49%
Instruction-One
CODELLAMA 34B
2.86%
1.05x
44.27%
18.92%
1.26x
84.97%
Instruction-Onil
GPT-3.5
16.26%
1.20
80.67%
39.16%
1.54
98.77%
Instruction-Only
GPT-4
8.49%
1.15x
93.25%
21.17%
1.31
98.77%
Few-Shot
CODELLAMA 7B
2.15%
1.02x
43.46%
9.51%
1.15x
85.07%
Few-Shot
CODELLAMA 13B
2.25%
1.02x
40.29%
13.70%
1.21
83.03%
Few-Shot
CODELLAMA 34B
2.66%
1.02x
43.97%
13.70%
1.16x
82.62%
Few-Shot
GPT-3.5
11.45%
1.13x
80.98%
29.04%
1.38x
95.91% %
Few-Shot
GPT-4
18.92%
1.25x
82.82%
36.40%
1,44x
98.98%
COT
CODELLAMA 7B
0.82%
1.01 X
27.40%
7.46%
1.13x
73.31
COT
CODELLAMA 13B
2.25%
1.04
32.92%
11.15%
1.20x
79.24%
COT
CODELLAMA 34B
3.99%
1.08
30.27%
19.63%
1.30x
78.73%
COT
GPT-3.5
21.37%
1.25x
65.95%
43.05%
1.60
91.72%
COT
GPT-4
26.99%
1.32
63.09%
42.74%
1.58x
84.87%
instruction-prompting. For instance, when prompted with instructions alone, both GPT-3.5 and CODEL- LAMA 34B demonstrated better %OPT and SPEEDUP metrics. This observation aligns with the findings of Zhao et al.] (202I), which highlighted that few-shot examples can sometimes bias the model and lead to an of the same fixed prompt might constrain the model to only apply optimization techniques present in the prompt, thereby resulting in sub-optimal performance. Finally, in line with the findings of Wei al. (2022a) that identified CoT prompting as an emergent capability, we observe improvements with this approach over both instruction- tuned and fixed prompt setups, but notably only for the larger CODELLAMA (13B and 34B) and GPT-3.5 models. For CoT prompting; we note that GPT-4 outperforms GPT-3.5 Best@) I and under-perfone GPT- 3.5 Best@8: this may demonstrate a lack of output diversity from GPT4 despite using the same sampling apper-parameters.
incorrect understanding of the task. In the context of study, the consistent
Retrieval-based few-shot prompting. Table (bottom) shows results using our dynamic retrieval-based few-shot prompting strategy, with preferable setting K retrieved prompts. Extended results for K E {1, 4} are detailed in Appendix A.7 The results show that dynamic few-shot prompting outperforms all the baseline variants, showing that PIE effectively adapts LLMs for program optimization in few-shot settings. We note that increased speedup may, however, come with some cost of correctness.
Table 3: Dynamic retrieval-based few-shot prompting: Results for dynamic retrieval-basee few-shot prompting across models for Best@1 and @.
Best@1
Best @8
Method
Model
%0pt
Speedup
&Correct
%Optt
Speedup
%CCorret
Dynamic Retrieval, K=4
CODELLAMA
6.34%
1.19x
23.11%
21.06%
1.66x
57.98%
Dynamic Retricval, K=4
CODELLAMA 13B
9.30%
1.29x
26.99%
28.12% 12%
2.04
62.58%
Dynamic Retrieval, K=4
CODELLAMA 34B
11.66%
1.34x
30.57%
42.54%
2.43x
73.62%
Dynamic Retricval, K=4
GPT-3.5
28.02%
1.55x
79.65
51.64%
2.19x
95.71 %
Dynamic Retrieval, K=4
GPT-4
51.02% %
2.53x
79.35%
76.07 %
3.93x
95.71 %
7

---

Published as conference paper ICLR 2024
4.2 RESULTS FOR FINETUNING
Fine-tuning with PIE substantially improves models. We fine-tune CODELLAMA and GPT-3.5 models on our PIE dataset. Due to the cost of fine-tuning and sampling models through the OpenAl API, we were only able to train GPT-3.5 on the smaller, high-quality dataset (HQ) in Section The top of Table all models. We see substantially stronger results when fine-tuning on
results for traditional fine-tuning the smaller, high-quality dataset. These results reflect the observation that to adapt LLMs, a small set of high-quality examples can elicit strong performance (Zhou et al. 2023a Chen et al. (023))
Performane- training outperforms fine-tuning, Table shows results for performance- conditioned (PERF-COND) generation (Section 3.2 Both fine-tuned CODELLAMA models (7B and 13B) show significant improvements in %OPT and SPREDUP. These gains highlight how the performance im- provement information (Figure enable models to distinguish optimal and sub-optimal solutions, lead- ing to more effective optimizations.
Synthetic data from self-play marginally improves generalization. Next, we fine-tuned both CODEL- LAMA and GPT-3.5 using our PIE dataset augmented with our synthetic examples. We show results at the bottom of Table For CODELLAMA and GPT-3.5, compared using no synthetic data, the additional data improves both OPT and often SPEEDUP, particularly with BEST @ I. We believe the small set of synthetic examples helped generalize the fine-tuned model, as evidenced by the higher %OPT.
Model vs. Human Fastest Possible Speedup. We compared the fastest human submissions in CodeNet for the test set with our model's fastest generation per problem. The comparison involved 39, 129 model gener- ations against 118,441 human accepted solutions (or 197,92, including incorrect or timed-out submissions). PIE dataset, the best human speedup achieved was 9.56x, while our model achieved slightly higher speedup of 9.64x, setting new upper limit.
Table 4: Fine- Tuning: Results for various models and dataset configurations.
Best@1
Best@8
Dataset
Model
%0ppt
Speedup
&Correct
%Opt
Speedup
&Correct
All
CODELLAMA 7B
9.20% 12.78%
1.31
55.21 % 55.42%
35.58%
2.21
74.03%
All
CODELLAMA 13B
1.52x
43.76%
2.71
75.46%
HQ
CODELLAMA 7B
10.33%
1.40x
76.38%
45.30%
3.14x
87.63%
HQ
CODELLAMA 13B
11.55%
1.43
70.55%
47.75%
3.43x
85.07%
HQ
GPT-3.5
38.55%
2.70x
59.10%
86.71%
6.74x
95.40 %
w/Perf-Cond All w/Perf-Con Cond
CODELLAMA
25.15% 32.00%
2.45
34.76%
56.95%
4.86x
63.91%
CODELLAMA 13B
2.95x
38.55%
66.56%
5.65 x
70.96%
HQ Self-Play
CODELLAMA 7B
15.34%
1.59
75.77%
46.22%
3.32
87.42%
HQ + Self-Play
CODELLAMA 13B
14.31% %
1.61
76.28%
49.69%
3.51
86.20%
HQ + Self-Play
GPT-3.5
45.50 %
3.02x
61.55%
87.63%
6.86x
95.09%
*For GPT-3.5, to be sure the increases came from the type of data and not the quantity of data, we performed an ablation by fine-tuning the top 5,793 examples from PIE with maximum of duplicates (instead of the 5,570 pairs that included synthetic programs), and BEST @ performance degrade
8

---

generation Published as a conference paper ICLR 2024
4.3 DISCUSSION AND KEY TAKEAWAYS
CODELLAMA vS. GPT-3.5 Our results demonstrate that openly available models such as CODELLAMA can be competitive with GPT-3.3. For prompting, CODELLAMA 34B with dynamic retrieval (42.54% % OPT, x SPEEDUP for BEST @ 8) roughly matched the performance of GPT-3.5 with dynamic retrieval (51 ..6% %OPT, 2.19x SPEEDUP for BEST @8). With fine-tuning, CODELLAMA 13B with performance-condiion generation (66.56% %OP, 5.65x SPEEDUP for BEST @ 8) approached the performance of GPT-3.5 with synthetic data (87.63% %OPT, 6.86x SPEEDUP for BEST@8); indeed, we may expect that fine-tuning CODELLAMA 34B using the same strategy would further bridge this gap. These results demonstrate that with the right adaptation strategies, open models can be competitive with private ones.
Prompting vs. fine-tuning, Our results demonstrate that while prompting be effective way adapt models (with retrieval), fine-tuning significantly outperforms prompting for models of the same size.
Effectiveness of retrieval-basee few-shot learning. Our results show that dynamic retrieval provides enor- mous gains over all other prompting approaches; for instance, it improved the performance of CODELLAMA 34B from 19.63 % OPP, x.30x SPEEDUP 34.25% OPT, 2.28x SPEEDUP for BEST@8.
generation. We find that performance-condition is incredibly effective for achieving good performance; in particular, it improved the performance of CODEL- LAMA 13B from 47. 47.75% %0P,, 3.43 SPEEDUP to 66.56% %OPT, 5.65x SPEEDUP for BEST @8.
Effectiveness of performance
5 RELATED WORK
Machine learning has been applied to improve performance by refactoring code
MMns & Tourwé 2004 Ag-
nihotri & Chug, 2020), identify compiler transformations (Bacon al. 1994 Talaashrafi (022). perform
parameter search (Hamadi) 2013; HHang et al.
2019:
Kaufman et al. [021]] Seshadri et al.) 2022 Kumar
lt al. 2022), auto- vectorize code (Nuzman al.
2006 Mendis al. al. 2019 optimize GPU code (I (l.iou et al.
2020 Cummins et al.) 202T), and automatically select algorithms (Kotthofi 2016: Kerschke et al. 2019).
and room at the top (Leiserson et al., 2020 Sherry & Thompson 2021). DeepPERF (Garg et al. 2022)
uses transformer-based model fine-tuned to generate performance improvement patches for C# applica- tions. Additionally, [hen et al. (2022) uses a discrete variational auto-encoder, each latent representation maps to a different category of code edits, and canonicalized code representations automatically suggest performance improvements, (Shypula et al. (2021) trains seq2seq models from scratch on optimization data superoptimize assembly programs after compilation. Shi et al. (2019) trains tree-LSTM from scratch with RL to superoptimize halide IR, and MAGPIE (Blot & Petke 2022) uses genetic algorithms for tasks includ- ing optimization. AlphaCode (Li al. 2022) leverages language models to generate solutions competitive programming problems in natural language, but it does not attempt to improve the performance of existing solutions. contrast, we focus on adapting pre-trained LLMSs (Chen al., 202Tb, Nijkamp et al., 2022
Tunstall et al. 2022 Xu et al. 2022 Fried et al. 2022) to performance optimization.
6 CONCLUSION
Our work is an initial step towards unlocking the potential of LLMs in leveraging the opportunities at the "top" of the computing stack. In particular, we improve algorithmic efficiency and, given a correctness oracle, enable automatic code optimization beyond optimizing compilers. Our results pave exciting path for improving computing efficiency post Moore's 's law.
9

---

Published as a conference paper ICLR 2024
ACKNOWLEDGEMENTS
We extend our gratitude towards Herman Schmit, Chandu Thekkath, James Laudon, Cliff Young, and Stella Aslibekyan for reviewing the paper and providing insightful feedback. We also thank the extended team at Google DeepMind who enabled and supported this research direction. This material is partly based research sponsored in part by the Air Force Research Laboratory (agreement number FA8750- 19-2-- 0200 and award W91 INF-20-1 1-0000.. The U.S. Govt. is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed implied, of the Air Force Research Laboratory or the U.S. Government.
REFERENCES
Mansi Agnihotri and Anuradha Chug. A Systematic Literature Survey of Software Metrics, Code Smells and Refactoring Techniques) Journal of Information Processing Systems, 2020.
Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman. Compilers: Principles, Techniques, and Tools, volume 2.
Addison-wesley Reading, 2007.
David F Bacon, Susan L Graham, and Oliver J Sharp. Compiler Transformations for High- Performaree Computing CSUR, 1994.
Nathan Binkert, Bradford Beckmann, Gabriel Black, Steven K. Reinhardt, Ali Saidi, Arkaprava Basu, Joel Hestness, Derek R. Hower, Tushar Krishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib, Nilay Vaish, Mark D. Hill, and David A. Wood. The gem5 Simulator SIGARCH Comput. Archit. News, 2011.
Aymeric Blot and Justyna Petke. MAGPIE: Machine Automated General Performance Improvement via Evolution of Software arXiv preprint arXiv:2208.028/// 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language Models are Few-shot Learn- ers NewrlPS, 2020.
Binghong Chen, Daniel Tarlow, Kevin Swersky, Martin Maas, Pablo Heiber, Ashish Naik, Milad Hashemi, and Parthasarathy Ranganathan, Learning to Improve Code Efficiency) arXiv preprint arXiv:2208. 05297,
2022.
Lichang Chen, Shiyang Li, Jun Yan, Hai Wang, Kalpa Gunaratna, Vikas Yadav, Zheng Tang, Vijay Srini- vasan, Tianyi Zhou, Heng Huang, et al. AlpaGasuss: Training A Better Alpaca with Fewer Datal arXiv preprint arXIv:2307.08701, 2023.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision Transformer: Reinforcement Learning via Sequence Modeling NeurlPS, 2021a.
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 Ry- der, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin,
10

---

Published as a conference paper at ICLR 2024
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 McGrew, Dario Amodei, Sam McCandlish, llya Sutskever, and Woj- ciech Zaremba. Evaluating Large Language Models Trained on Code ArXiv preprint, 2021b.
Chris Cummins, Zacharias V Fisches, Tal Ben-Nun, Torsten Hoefter, Michael FP O' Boyle, and Hugh Leather. ProGraML: A Graph-based Program Representation for Data Flow Analysis and Compiler Op- timizations] In ICLR, 2021.
Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. Incoder: A Generative Model for Code Infilling and Synthesis, arXiv preprint wrxxi::204.059999 2022.
Spandan Garg. Roshanak Zilouchian Moghaddam, Colin B. Clement, Neel Sundaresan, and Chen Wu. DecpPERF: A Deep Learning-Basee Based Approach For Improving Software Performance arXiv preprint 2rXiv:2206.1367, 2022.
Prakhar Gupta, Cathy Jiao, Yi-Ting Yeh, Shikib Mehri, Maxine Eskenazi, and Jeffrey Bigham. Instruct- Dial: Improving Zero and Few-shot Generalization in Dialogue through Instruction Tuning In EMNLP, 2022.
Patrick Haluptzok, Matthew Bowers, and Adam Tauman Kalai. Language Models can Teach Themselves to Program Better arXiv preprint 2xXi::2207.14502, 2022.
Youssef Hamadi. Combinatorial Search: From Algorithms to Systems Springer, 2013.
Junxian He, Chunting Zhou, Xuezhe Ma, Taylor Berg-Kirkpatrick, and Graham Neubig. Towards Unified
View of Earaieter-Efficiiet Transfer Learning arXiv preprint arXiv:2110.04366 2021.
Changwu Huang, Yuanxiang Li, and Xin Yao. A Survey of Automatic Parameter Tuning Methods for Metaheuristies IEEE transactions on evolutionary computation. 2019.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-Scale Similarity Search with GPUs IEEE Transac- lions on Big Data, 2019.
Sam Kaufman, Phitchaya Phothilimthana, Yanqi Zhou, Charith Mendis, Sudip Roy, Amit Sabne, and Mike Burrows. A Learned Performance Model for Tensor Processing Units MLSys, 2021.
Pascal Kerschke, Holger H Hoos, Frank Neumann, and Heike Trautmann. Automated Algorithm Selection: SSurvyy and Perspectives, Evolutionary computation, 2019.
Lars Kotthoff. Algorithm Selection for Combinatorial Search Problems: A Survey Data mining and con-
straint programming: Foundations of a cross cross-disciplinary approach, 2016.
Aviral Kumar, Amir Yazdanbakhsh, Milad Hashemi, Kevin Swersky, and Sergey Levine.
Of- Charles E Leiserson, Neil C Thompson, Joel S Emer, Bradley C Kuszmaul, Butler W Lampson, Daniel Sanchez, and Tao B Schardl. There's s Plenty of Room at the Top: What Will Drive Computer Performance after Moore's ' Law? Science, 2020.
fiine Optimization For Architecting Hardware Accelerators] In ICLR, 2022.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Ec- cles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Mas- son d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando
11

---

Published as a conference paper ICLR 2024
de Freitas, Koray Kavukeuoglu, and Oriol Vinyals. [Compeiition-level Code Generation with AlphaCode Science, 2022.
Jhe- Yu Liou, Xiaodong Wang, Stephanie Forrest, and Carole-Jean Wu. GEVO: GPU Code Optimization using Evolutionary Computation TACO, 2020.
Jiachang Liu. Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What Makes
Good In-Context Examples for GPT-3? arXiv preprini arXiv:2101.668 2021.
Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoe V Le, Barret Zoph, Jason Wei, et al. The Flan Collection: Designing Data and Methods for Effective Instruction
Tuning arXiv preprint arXiv:2301.73685 2023.
Ilya Loshchilov and Frank Hutter. arXiv:1711.05101, 2017.
Decoupled
Weight Decay Regularization
arXiv preprint
Aman Madaan, Niket Tandon, Peter Clark, and Yiming Yang. MemPrompt: Memory-assisted Prompt Edit- ing with User Feedback In EMNLP, 2022.
Daniel J Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Igbal, Lean-Baptiste Lespiau, Alex Ahern, et al. Faster Sorting Algorithms Discovered using Deep Reinforcement Learning. Nature, 2023.
Charith Mendis, Cambridge Yang, Yewen Pu, Dr Amarasinghe, Michael Carbin, et al. Compiler Auto- Vectorization with Imitation Learning NeurIPS, 2019.
Tom Mens and Tom Tourwé. A Survey of Software Refactoring IEEE Transactions on software engineering, 2004.
Swaroop Mishra, Daniel Khashabi, Chitta Baral, Yejin Choi, and Hannaneh Hajishirzi. Reframing Instruc- tional Prompts to GPTk's Language arXiv preprint arXiv:2109.078330 2021.
Artur Niederfahrenhorst, Kourosh Hakhamaneshi, and Rehaan Ahmad. Fine- LLMs: LoRA or Full- Parameter? An In-Depth Analysis with Llama 2. 2023. Blog post.
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 arXiv preprint arXiv:2203.13474, 2022.
Dorit Nuzman, Ira Rosen, and Ayal Zaks. Auto-vectorization of Interleaved Data for SIMD ACM SIGPIAN Notices, 2006.
David Peter. hyperfine 2023.
Gabriel Poesia,
Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gul- wani. Synchromesh: Reliable Code Generation from Pre-trained Language Models, In ICLR, 2021.
Ruchir Puri, David Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladmir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury. Lindsey Decker, Veronika Thost, Luca Buratti, Saurabh Pujar, Shyam Ramji, Ulrich Finkler, Susan Malaika, and Frederick Reiss. CodeNet: Large-Scale AI for Code Dataset for Learning Diversity of Coding Tasks arXiv preprint 11X.::22005.2655. 2021.
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code Llama: Open Foundation Models for Code, arXiv preprint 2008 /2950, 2023.
12

---

Published as a conference paper at ICLR 2024
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning To Retrieve Prompts for In-Context Learning In ACL, 2022.
Kiran Seshadri, Berkin Akin, James Laudon, Ravi Narayanaswami, and Amir Yazdanbakhsh, An Evaluation of Edge TPU Accelerators for Convolutional Neural Networks In IISWC, 2022.
Yash Sherry and Neil C. Thompson. How Fast Do Algorithms Improve? [Point of View the IEEE, 2021.
Proceedings of
Hui Shi, Yang Zhang, Xinyun Chen, Yuandong Tian, and Jishen Zhao. Deep Symbolic Superoptimization without Human Knowledge In ICLR, 2019.
Disha Shrivastava, Hugo Larochelle, and Daniel Tarlow. Repository-Level Prompt Generation for Large Language Models of Code In ICML, 2023.
Alex Shypula, Pengcheng Yin, Jeremy Lacomis, Claire Le Goues, Edward Schwartz, and Graham Neubig. Learning to Superoptimize Real-world Programs| arXiv preprint arXiv:2109. 13498, 2021.
Delaram Talaashrafi. Advances in the Automatic Delection of Optimization Opportunities in Computer Programs PhD thesis, Western University, 2022.
Lewis Tunstall, Leandro Von Werra, and Thomas Wolf. Natural Language Processing with Transformers "O'Reilly Media, Inc.", 2022.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emeegeet Abilities of Large Language Models arXiv preprint arXiv:2206.07662. 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. ofain-of-Thougeee Prompting Elicits Reasoning in Large Language Models NeurIPS, 2022b.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the- Natural Language Processing System Demonstrations, Online, 2020.
In EMNLP:
Frank Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn. A Systematic Evaluation of Large Language Models of Code In MAPS, 2022.
Tianjun Zhang, Fangchen Liu, Justin Wong. Pieter Abbeel, and Joseph E Gonzalez. The Wisdom of Hind-
sight Makes Language Models Better Instruction Followers] arXiv preprint arXiv:2302.055200 2023.
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate Before Use: Improving
Few Performance of Language Models In JCML, 2021.
Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, et al. LIMA: Less Is More for Alignment, arXiv preprint arXiv:2305. /206, 2023a.
Shuyan Zhou, Uri Alon, Sumit Agarwal, and Graham Neubig. CodeBERT Score: Evaluating Code Genera- tion with Pretrained Models of Code. arXiv preprint vxXiv:2302.05527, 2023b.
13

---

Published as a conference paper ICLR 2024
A APPENDIX
A.1 ADDITIONAL ANALYSIS OF GENERATED CODE EDITS
We study the kinds of edits LLMs make that lead to our performance gains, focusing on our best- tess-peforning model, GPT-3.5 3.5 fine-tuned with synthetic data. We manually analyze randomly sampled set of 120 (source, optimized) program pairs to understand the algorithmic and structural changes responsible for the perfor- mance gains. We find that the transformations can be broadly categorized into four kinds: Algorithmic changes, Input/Output operations (IO), Data Structure modifications, and Miscellaneous adjustments. Al- gorithmic changes (complex modifications, such changing recursive methods to dynamic programming. and unexpected ones, such as omitting Binary Indexed Trees for simpler constructs) are most common, com- prising -34. 15% of changes; Inpul/Output operations (e.g., changing 'cin/cout' to 'scanf/printf', efficiently reading strings) comprised -26.02%; Data Structures (e.g., switching from vectors to arrays) comprised -21.14%, and Miscellaneous (e.g., code cleanups and constant optimizations) comprised ~18.70% These findings show the LLM's capability to perform sophisticated optimizations while preserving functionality.
In Appendix A.2, we show several examples to demonstrate the nature of optimizations made by our model. In these examples, we highlight the removal of a wasteful nested loop (Figure 4 eliminating the need to sort (Figure 3) avoiding unnecessary precomputations (Figure 5), use of simple modular arithmetic properties for optimization (Figure 6). and restructuring loops to improve performance (Figure
Algorithmic Transformations (34.15%). The most dominant transformation, representing approximately 34.15% of the changes, is the Algorithmic category. Edits in this category exhibited sophisticated code re- structuring. A frequent transformation was the shift from recursive methodologies to dynamic programming approaches, which can significantly enhance running time for specific problem types. Other examples in- clude replacing Binary Indexed Trees with more straightforward constructs, removing redundant conditional checks, bit manipulations, and in some cases, using identities from number theory and algebra to replace complex computation with a formula.
Input/Output Operations (26.02%) The Input/Output operations category, accounting for roughly 26.02% of the changes, primarily centered on transitioning from C++ standard I/O methods ('cin/cout') to the faster C-standard methods ("scanf/printf'). Other examples include reading string character-by-characce vs. reading in one go, This transformation is particularly beneficial for problems dealing with extensive datasets, where 1/O operations can be a bottleneck.
Data Structure Modifications (21.14%). Changes in the Data Structures category, which constituted about 21. 14.14% of the transformations, showcased the model's adeptness in selecting optimal data structures for the task. A recurring modification was the transition from vectors to traditional arrays, leading to enhanced access times and reduced overhead, Additionally, the changes include removal of pointers in favor of direct access, and using hashmaps when appropriate.
Miscellaneous Optimizations (18.70%). The Miscellaneous category, encompassing approximately 18.70% of changes, captured a myriad of optimizations. These ranged from code cleanups, such as omitting unnecessary initializations, to replacing computationally intensive functions with predefined constants.
While our analysis showcases variety of optimizations, it is essential to address certain speedup sources that may be considered spurious. Specifically, in 10 out of the 120 cases we examined, the speedup stemmed from reducing the constants used to allocate arrays. These speedups might not always reflect genuine algorithmic improvements, and indicate that the test cases may not perfectly cover all the cases, an open problem in code synthesis (Li et al.) 2022). Thus, while they contribute to the overall speedup metrics, they should be interpreted with caution. Nevertheless, our analysis shows that the vast majority of speedups do not suffer from this issue, supporting strong empirical results.
14

---

Published as conference paper ICLR 2024
int main [ int
int maintl
a, 5, -1, min 189; scant ("ana sn, km)
veotorsint> V, v1;
for
m. 1+-)
cin >>
sc sa. 6b11
ifla max] max 67 iE(b min) min by
firtint 1 [++][
cin >> a >2 bj
v.puar [a]
vi.push_ (b)
(ane < 01
ans 0g
sort corttv. (e, v.end()) sort vl.end(1);
printE ans) return 0₃
(E(x) v][0])
cout << 0 <s eadi;
(h) Faster Code.
cout <s v1[0] v.back() + se ondl;
return 02
(a) Slower Code.
Figure 3: Comparison of two programs for determining the range between the maximum and minimum values from a set of input pairs. The faster code (right) generated by PIE directly computes the maximum start and minimum end of the ranges in single pass (On)), eliminating the need for sorting (O(n log
A.2 EXAMPLES OF OPTIMIZATIONS
We show several examples to demonstrate the nature of optimizations made by our model. these examples, we highlight the removal of wasteful nested loop (Figure(4) eliminating the need to sort (Figure 3. avoid- ing unnecessary precomputations (Figure 5), use of simple modular arithmetic properties for optimization (Figure 6), and restructuring loops improve performance (Figure 7)
int main()
int maint)) int k, x7 scanf ("ad 9d", 6k, ax) for (int i-x-ktl 1 (ioek--11))) printf ("Sd 1,1) return 0;
int X; cinssksox:
for (int 1-- 1--1000000::4410000111
(1=-x)
for [i-x coutee Zec" "
(b) Faster Code,
return 0;
(a) Slower Code.
Figure 4: Comparison of two code implementations for printing 2h: 1 consecutive numbers centered around the input æ. The faster code (right) optimizes the process by directly computing the range without efficient and concise solution. The red highlighted portion in
the need for nested loops, resulting in the slower code (left) indicates the wasteful nested loop that was eliminated in the optimized version. This loop unnecessarily iterates over large range of numbers, only to perform a meaningful operation for a tiny fraction of those iterations.
15

---

Published as conference paper ICLR 2024
int main()
long long a-1, mod-1eod-1 int int maint)
int 1, 02
long long num [um0_00005] 11,
for [1 = 2: <= 100004; S++) sum[i] (num[1 2] (180000030000)) ("Ed", an)7
scanf ("8d", in); (int i-1ziemarit>)
printf ('s1id)n", num pum return
o-(aA1) Smod;
(a) Slower Code.
(b) Faster Code.
Figure Comparison of two code implementations for computing factorial modulo +0" The slower code (left) precomputes the factorial for all numbers up to 10 storing them in an array. The faster code (right) computes the factorial only for the given input, resulting more memory-eficient and faster solution. The red highlighted portion in the slower code indicates the precomputation step that was eliminated in the optimized version.
int main()
int maint) 1)
int scanf ("kd &d. ad", SA, 68, 62)1
B, C;
scanf ("8d $d id", SA, 6B, sC);
bool istes felss)
bool is_yes falser
for (int 1 0: < 1000; 1++)
for lint 91 1 B: 1-+) {
(int 03 ] 1000; Joa)
if (1A 1) (3 3) C)
is_yes tzuer
true:
print ye_ YB3! "XO")
return 0;
printr ("8sAm", 1syes 7 "YPS* : "NO'13 return
(b) Optimized Code.
(a) Slower Code with Nested Loops.
Figure 6: Optimization of modular arithmetic problem. The slower code naively checks all possible combinations of and leading modular arithmetic, reducing the complexity to OBB. By directly computing the modulo operation for each i in the range [0, B 1], it efficiently determines if the condition (A i) mod B C is satisfied. Note that the example on the right is faster, but the generated code could have been even faster it included a break statement.
complexity of O(10)). The faster code leverages the property of
16

---

Published as conference paper ICLR 2024
int main()
int m
int n,
int 1, m;
scant (1ddad", (008d",.mp) 6m)
cinsensem;
for a+1;2<mpi- printe ",4)7
for mii---n-llimmmniie
coutssi;
if(il men-
coutes"
for 1- printr s)",
1 ('intE('\n") return 0;
(a) Slower Code.
(b) Optimized Code.
Figure 7: Comparison of the slower code (left) with its optimized version (right). The optimized code avoids an additional conditional check inside the loop by restructuring the loop.
A.3 CONVERGENCE OF GPT3.5
MODELS WITH ADDITIONAL GENERATIONS
The data in Section 4.2 shows that the gap between GPT-3.5 fine-tuned on HQ data and HQ Self-Play seems to diminish with more generations. Training with HQ data helps increase the model's coverage, allowing to optimize a large number of programs with just single greedy sample. However, as more samples are drawn, the performance of HQ and HQ Self-play gradually converge to similar level of performance. We include the plots of performance improvements as the number of samples gradually increases in Figure 8 and Figure 9
Additionally, there is a slight drop in correctness after training with Self-Play: however, the speedup and correctness increase from 6.74 + 6.86 and 86.71 - 87.63. This reveals precision-recall style trade-off: the model trained on synthetic data learns to try novel optimization strategies, but that comes at the cost of making more mistakes. We will add this analysis the revision.
% Opt Over Generations
Speedup Over Generations
90
7
80
6
70
Speedup
% Opt
5
60
4
50
% Opt Self-Play
Speedup Self-Play
40
% Opt HQ-Only
30
Speedup HQ-Only
2
3
4
7
1
3
4
5
6
7
8
Number of Generations
Number of Generations
Figure 8: Performance in % Opt over generations comparison of GPT-3.5 fine-tuned with HQ Data Only vs. HQ + Self-Play.
Figure 9: Speedup over generations comparison of GPT-3.5 fine-tuned with HQ Data Only vs. HQ Self-Play.
17

---

Published as conference paper ICLR 2024
Table 5: Error analysis of GPT-3.5 fine-tuned with synthetic data.
Result
Percentage
Failed compile (syntax/type errors)
12.51%
Compiled, but got [050 of test cases wrong Compiled, but got (75, 95%] of test cases wrong Compiled, but got (25, [%] of test cases wrong Compiled, but got (0-25%) of test cases wrong (at least test case was wrong)
27.59%
12.08%
10.84%
6.90%
Ran all test cases, but the program was slower than the original
9.93%
Ran all test cases, but the program was the same speed as the original
9,40%
Ran all test cases, the program was faster, but not 1.1 x speedup or higher 10.75%
A.4 ERROR ANALYSIS
We performed error analysis on the the GPT-3.5 fine-tuned with Self-Play. We analyzed the generated programs that it fails to optimize and the cause of each failure. Table shows that a large fraction ~600 of the failures happen because the proposed changes break unit test. In about 30% the cases, the model produces correct, but the generated program is either slower (10%) doesn't 't meet our threshold for speedup (10%). Finally, in about 10% of the cases, the generated program has a syntax error. Additionally, with test cases, find that when the model gets the program wrong, it seems to most often get it quite wrong by missing most test cases.
Additionally, conduct additional analysis investigate the properties of programs that PIE fails to op- timize. The results show a mild negative correlation between the problem description length and average accuracy (-0.15) and between the source program length and average accuracy (-0.26), suggesting longer inputs slightly reduce accuracy. Additionally, the average speedup has a mild negative correlation with both the problem description length (-0.16) and the source program length (-0.11), indicating minimal impact of length on speedup compared to correctness. Overall, this analysis reveals that language models struggle generate a correct program when faced with larger source programs and challenging problems, but their ability to optimize programs is minimally impacted. This motivates future work direction where techniques from program repair may be combined with PIE for better results.
Why does conditioning the model only to generate programs with a 10/10 optimization rate may constrain the num- ber of optimizations available for any given input. To investigate this, experimented using the first 6 generations from the 7b Performance-Conddiionn
Conditioning Degrade the Ability to Produce Correct Code? We believe that
model when conditioned on 10/10 versus combining the first 2 generations when conditioned on 10/10, 9/10, and 8/10 (i.e. comparing 6 total generations from one strategy vs. 6 total generations across difference strategies). When we did this, we saw %Correct increase from 59.95% 64.36%. These results support the explanation that performance labels may restrict the set of generated programs that are correct.
18

---

Published as conference paper ICLR 2024
A.5 PIE DATASET DETAILS
Dataset
Unique Problem IDs
Train
1.474
Val Test
77
41
Table 6: Number of unique problem ids.
Dataset
Pairs
Train
77,967
Val 2,544
Test
978
Table 7: Number of pairs.
Dataset
Mean sre
Mean tgt
Median sre
Median tgt
Train
675.00
616.44
417
372
Val Test
644.74
471.47
180
110
427.85
399.15
362
319
Table 8: GPT-2 Tokenizer lengths.
A.6 SELF-PLAY DATA GENERATION DETAILS
We use the template in Figure 10 for prompting GPT-3.5 in the self-play scenario. For the prompt, sample natural language descriptions of programming problems as well as accepted solutions to fill the template. For generation, we try attempt to take n = samples. We chose these samples after doing a sweep of 6 configurations of generation parameters, each attempting to generate 200 programs. We found this configuration to be the most cost-effective per new-sample with relatively promising rates of novelty.
temperature of 1.0 and use top-p sampling with p 0.9 For each prompt,
We found that after attempting generate 10,000 new programs through the prompting strategy, 6,553 were not in the training/validatiionness set of PIE. We keep track of equivalent programs of the ones generated, and of these 6,553 generations we found 3,314 equivalence sets. In total, this required executing over 1.4 million binary input pairs. Parallelized on 24-core Intel 13900k processor with 64GB of RAM, this took less than 72 hours complete.
A.7 ABLATION OF RETRIEVAL- BETSEED FEW-SHOT PROMPTING CONHIGURATION
For our retrieval-based prompting experiment we tried multiple configurations for the number of retrieved prompts where of K {1,2, 4} of the K closest retrieved prompts.
A.8 TRAINING DETAILS
We fine-tuned the 7B and 13B variants using the HuggingFace Transformers library with FSDP to distribute the training process across 8x 48GB GPUs (NVIDIA RTX A6000/NVIDIA L40). For high-quality
19

---

Published as conference paper ICLR 2024
Description 1: [description_]]
Code 1: (codc_1)
Description 2: [description_2)
Code 2: (code_2)
Now, can you generate a program that takes that same input as Code 2 in Code but produces different outputs? Write it to be as novel possible.
Code 3:
Figure 10: The prompt template used for prompting GPT-3.5 for generating synthetic data for self-play.
Table Retrieval-base few-shot prompting ablation over different K examples for retrieval and over vari- ous models.
Best@1 1
Best@8
Method
Model
%Ott
Speedup
%Correct
%Opt
Speedup
%Cooreett
Dynamic Retrieval, K=1
CODELLAMA 7B
3.27%
1.09x
16.67%
15 6.64%
1.50x
50.51%
Dynamic Retrieval, K=1
CODELLAMA 13B
5.32%
1.16x
21.68%
22.29%
1.72x
62.99%
Dynamic Retrieval, K=1
CODELLAMA
10.02%
1.25x
30.67%
34.25%
2.21
69.73%
Dynamic Retrieval, K=2
CODELLAMA
4.40%
1.13x
20.55%
16.87%
1.51
55.32%
Dynamic Retricval, K=2
CODELLAMA 13B
9.10%
1.35x
28.73%
28.02%
1.97 x
64.72%
Dynamic Retrieval, K=2
CODELLAMA 34B
10.22%
1.27x
25.87%
34.25%
2.28 x
63.19%
Dynamic Retrieval, K=2
GPT3.5
26.18%
1.58x
80.37%
48.06%
2.14x
97.85%
Dynamic Retrieval, K=2
GPT4
50.00%
2.61x
80.57 %
74.74%
3.95
97.85%
Dynamic Retrieval, K=4
CODELLAMA 7B
6.34%
1.19x
23.11%
21.06%
1.66x
57.98%
Dynamic Retrieval, K=4
CODELLAMA 13B
9.30%
1.29X
26.99%
28.12%
2.04x
62.58%
Dynamic Retrieval,
CODELLAMA
11.66%
1.34x
30.57%
42.54%
2.43x
73.62%
Dynamic Retrieval, K=
GPT-3.5
28.02%
1.55x
79.65%
51.64%
2.19x
95.71%
Dynamic Retrieval, K=4
GPT-4
51.02%
2.53X
79.35%
76.07%
3.93x
95.71%
dataset, which consists of approximately 4,000 examples, the models were fine-tuned until convergence was achieved, which be done under 12 hours with 8 GPUs. For tasks related to full data fine-tuning and performance-condinee the model of GPU used. All experiments 2017). For the 7B and 13B variants of CODELLAMA, we used a batch size of 32 and learning rate of 1e-5 for all of the experiments.
fine-tuning, we only train for 1 epoch, which takes 24 to 36 hours, depending on conducted using the AdamW optimizer (Loshchilov & Hutter
20

---

Published as conference paper ICLR 2024
A.9 EXAMPLE OF DUPLICATE CODE CODENET WITH DIFFERENT MEASURED RUNTIMES
Figure 11 contains an example of code we found duplicated across the Project Codenet Dataset with variance in the dataset's 's report of CPUT ime. For problem number p031 60 and between submission s s7668277 (1827700 7701 and s 64 782197 speedup of 2.44x is reported, despite the programs and environments being identical. We note that multiple submissions existed, because it was template code. For brevity, we remove the macros, imports, and comments.
using namespace std:
typedef long Long
inline void getInt (int* p) const int max:-1000010;
const int inf=0x3ESEffff;
f:
11 dp [maxn];
[maxn]
int main()
gbtb;
cinsens
repd
ci]>
dp[1]-0;
dp[0]=0; dp db(2)-aba(a(2)-o(())
repd 3,
(+ (p(1111))11)))))))1111111111) (a [1]-a[1-1]])
cout<<)((=); reture 0;
inline void get (int* p) [
char ch:
getcher())
while (ch --
ch -- (Aalls
*p - (geechar () 1D1);
while ((ch getchar (1) 10 66 ch <- 191) (
pp 10 101;
else
p 1
while (ch getchar 10" ch <- 191)
p p 10 + ch 101)
Figure 11: example C++ program we found multiple submissions for as it is template code. Across these submissions, found variance in the reported CPU runtime despite the code and competitive pro- gramming environment being identical.
21

---

Recent work has shown that the effectiveness of parameter-efffiient methods depends on the training data. Published as conference paper ICLR 2024
A.10 LORA RESULTS
We show results using low-rank adaptors for finetuning in Table 1O We hypothesize that this gap may be because performance optimization examples do not occur naturally the training data.
For example, He et al. (202T) find that "PEFT techniques are slower to converge than full tuning in luw/medium-resourre
scenarios," and Niederfahrenhorst et al. (2023) find that LoRA is least effective for challenging tasks like mathematical reasoning. Together, these works indicate that the performance of PEFT may be heavily dask-dependent. Our hypothesis is based the fact that LoRA only changes small subset the model's s parameters, and is likely most helpful when the base model has some proficiency for the task (due to pre-training), and LoRA help adapt the model of the task further. Given that LLMs generally struggled in program optimization without retrieval or full fine-tuning, we hypothesize that the challenging nature the problem and a potential lack of pre-trained proficiency pose challenges for LoRA.
Table 10: LoRA Experiments: Results for fine-tuning CODELLAMA with low rank adapters. A LoRA rank of 32 and LoRA alpha of 16 is used for all experiments listed.
Best@1
Best@8
Dataset
Model
%Opt
Speedup
%Correct
%0pt
Speedup
%Correct
All CODELLAMA 7B
1.12%
1.01 x
45.82%
9.57%
1.17x 1.15x
87.47% 90.94%
All
CODELLAMA 13B
0.41%
1.01
59.47%
9.67%
HQ
CODELLAMA 13B
0.92%
1.02
59.57%
10.69%
1.17x
91.04%
A.11 PROMPTS
Given the program below, improve its performance:
### Program: (sra_code)
### Optimized Version:
Instruction Instruction-prompiing for adapting LLMs. The model is provided with direct instructions to improve the performance of the given program.
Figure 12:
22

---

Published as conference paper ICLR 2024
slowl + fastl II slow2 fast2 fastN
slow3 fast3 II ... ||
slowN
### Program: (sre_coac)
### Optimized Version:
Few-shot prompting for in-context learning. The format "slow - fast" is used for adaptation. A test program is appended for inference.
Figure 13:
slower program:
(sra_code)
Give a potential ial ial strategy improving the program:
LLM reasoning: The current program calculates the sum of integers from I to n-1 using loop. This iterative approach results in a time complexity of O(n). The sum of the first n natural numbers follows an arithmetic progression, and by leveraging Gauss's ' formula, n(n-1)/2, we can compute the sum directly. This formula-based approach allows us to calculate sum constant time, O(1,, eliminating the need for iteration.
$8$ opt imized version of the same code with the strategy mentioned above:
LLM Response: optimized code
Figure 14: thoougt prompting. The model's intermediate response and final program are high- lighted in blue, indicating they are produced by the L.LM.
similar slowl > similar fastl II similar slow2 similar lar fast2 II + 11 similar_slow + similar_fasta
WV Program: (sre_code)
### Optimized Version:
Figure 15: Retrieval-based few-shot prompting. By dynamically retrieving analogous program structures challenges, the model is guided to better harness patterns in PIE.
23

---

Published as conference paper ICLR 2024
Below is program. Optimize the program and provide more efficient version.
Below progran. Optimize the program and provide a more efficient version.
### Program: (src_code)
IV Program: (sre_code)
### Optimized Version: (fast_codo)
### Optimized Version:
(b) Inference Prompt.
(a) Training Prompt.
Figure 16: Standard training and inference prompts with PIE.
24

---

Published as conference paper ICLR 2024
Retrieved i-nearest prompt,
Retrieved i-nearest promet,
src_code
Egt_code
#inciude <fostreamx
#fncluda sostdlex
#include <atack>
ueing namespace std;
int n, anst
char ch1, ch2?
stack-char>> 51
int main
int main()
acant ("8d", 6nl
int ni
ch1 getchar (1;
ein
ch1 getchar ans -1
for (int i =
nz ++2)
char
for lint
i-+)
atn >> ti (s. cm.py
ch2 - getchar ();
if
chi) anst-)
5. b.pushht)
ch1 ch2;
else
(: ()
printE anz);
else
s.push(t);
(b) Retrieved Fast.
cout s
return 0;
(a) Retrieved Slow,
Code for co be_ opt imized goes here
Finclude <bics/stdcc+..j
using namespace std;
int main() len;
cin >> N;
string 87
cin
len ()
(len
for (int len: 1 Ny 1--) E
s.pop_back ()
for (int -- 0; j 5+H { b.ck)
cout
else
cout 87
return 0,
(c) Program to be optimized.
Figure 17: Example of retrieval- prompting. To optimized the program in Figure 17(c) our dynamic prompting method retrieves the closest source program from the training set (Figure 17(a). where the simi- larity is measured using CodeBertScore (Zhou et 2023b). The slow program and the corresponding fast program (Figure 17(b) from the training set are used as prompts.
25


Reviews:
[{"review_id": "rgBN5tF6tF", "reviewer": "Reviewer_8KXu", "summary": "The paper proposes PIE dataset. Each sample in the dataset is basically a pair, showing a program and its optimized counterpart. \nThe impact of PIE dataset is further studied on several LLMs (both open and closed), including the family of CodeLlama and GPT3.5 and GPT-4. Moreover, a broad range of adaptations is used to improve the results of the LLMs, such as instruction, few shot, chain of thoughts, dynamic few shot, and fine-tuning. \nThe experimental results indicate that each adaptation strategy improves the results, with fine-tuning having the most significant improvement over the others.", "questions": "For detailed questions, please refer to the weakness section.\n\n- The authors have not discussed enough about the cases where the LLMs fail or why they fail. Could they add further experiments and clarify it?\n\n- In Table 2, why is the choice of models inconsistent across different methods? Like, there are no few shot learning or COT for GPT-4. \n\n- Why does Perf-Cond degrade the ability of the LLMs to produce the correct code? \n \n- How semantic similarity is conducted where semantic duplicates are tracked?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The problem of performance editing is important. Not only should the generated code be correct, but also it should be as efficient as possible. Therefore, the paper targets an important problem. \n\n+ The range of adaptations considered is wide, and the experimental results give the reader a clear image of how each adaptation strategy can be used to improve the results. \n\n+ The paper uses top closed-sourced (GPT3.5 and 4) and open-sourced (CodeLLama 7B, 13B, 34B) to study the impact of PIE dataset. It clearly shows the gap between closed and open LLMs and how different adaptations can narrow this gap.", "weaknesses": "- The study mostly focuses on the percentage of performance, and in cases where the runtime of the generated program is slower or the code is incorrect, speed up is considered one. This is not a good approach. In particular, a study is needed on what category of programs LLMs often fail to produce correct code or optimized code. In such a study, it will be easier to infer in which cases it is better not to use the LLMs. Or which category of programs needs to be further improved. \n\n- For synthetic data, it is mentioned that semantic duplicates are tracked, but no information is provided on how semantic similarity is conducted. Is it also based on CodeBertScore? \n\n- It is interesting to see that Perf-Cond has decreased the percentage of correctness. Any reason why Perf-Cond degrades the ability of the LLMs to produce the correct code? \n\n-  The presentation could be improved as an example, Table 1 is not referenced anywhere in the text, or in Table 2, it is better to group the Dynamic Retrievals together. The additional horizontal line is confusing. \n\n- In Table 2, why is the choice of models not consistent across different methods? Like, there is no few shots learning or COT for GPT-4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ieRhpxAzdk", "reviewer": "Reviewer_nenm", "summary": "This paper proposes a new benchmark for training and evaluating LLMs to generate performance-improving code edits given an existing unoptimized program as well as an evaluation of current and novel prompting/finetuning methods for adapting LLMs for this task. The benchmark is constructed from CodeNet tasks and the authors annotate the runtimes using the gem5 environment along with caveats that this performance measurement can be very difficult in other benchmarking setups. The authors show improvements over the human baselines on speedups with a variety of methods, and show a systematic ablation with various models, prompting, and retrieval schemes on both open-source and private large language models.", "questions": "Are the speedups reported only on edited programs that are verified to be correct?\nHow does the model generalization scale with the amount of synthetic data used?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The benchmark is an important artifact that the community will continue to build upon, especially as code-generating/editing large language models continue to be developed and deployed in research and production environments. The analysis and ablations are very thorough and further justify the benchmark and prompting strategies as important contributions.", "weaknesses": "The experiments are very thorough, but it seems that the correctness of the models degrades with introduced methods. While it seems that the paper's primary contribution is the dataset, further analysis of correctness (as opposed to just pure speedups/optimization %) would further solidify the adaptation methods sections of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vLeyg6r8nW", "reviewer": "Reviewer_VFMY", "summary": "This paper proposes a dataset called Performance-Improving Edits (PIE). It contains 77K pairs of C++ programs where one is a performance-improved version of the other, filtered from CodeNet. It also proposes to use gem5 simulator to simulate an Intel CPU as the runtime metric rather than running the programs and measuring wall time. The paper proposes a number of ways to use the PIE dataset to induce large language models to improve code performance, including prompt engineering, retrieval augmented generation, and fine-tuning. The best result is from fine-tuning GPT-3.5, with a surprising speedup of 6.86X, beating best human performance.", "questions": "The following are questions in addition to the weakness section.\n\nThe rationale of using gem5 simulation instead of measuring wall time makes sense but won't this run the risk of overly focused on a single CPU (Inter Skylake)? Also gem5 simulation still does not capture big O complexity which is often a goal in optimizing code.\n\nIt is counter-intuitive that Section 3.2 only uses 4K out of the 77K pairs in PIE to fine-tune GPT 3.5. Then 3K synthetic data are created and used. Could you explain the rationale of these choices? This seems to contradict the quality claim of the PIE dataset.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This work is well motivated and addresses a meaningful task. The construction process described in section 2 seems reasonable. The different methods to adapt models in section 3 cover most main stream methods.", "weaknesses": "The results are too good to be true. It's surprising to see that, for C++ competitive programming tasks, the fine-tuned GPT-3.5 beats the best human submission by a large margin: 6.86X speed up versus 4.06X speed up. So let's take a look at the examples in appendix A.1 which are code improvements generated by the model. Figure 3 of A.1 contains two programs that are functionally different. Figure 4(a) in A.1 is so bad that it seems unlikely in a C++ competition. Figure 5 contains two programs that are functionally different and also have different interfaces for execution (unclear how it passes correctness test). Figure 6 contains two programs that are functionally different and Figure 6(b) is missing an obvious break statement to help performance. Overall none of before-optimization examples seems plausible as competitive C++ programming submissions. By looking at these examples, I question the quality of the PIE dataset.\n\nI randomly looked at some entries in the supplementary material and they seem consistent with examples in appendix A.1 and not plausible for competitive C++ programming submissions.\n\nA side evidence for the issue can also be seen in Tables 1 and 2, where the correct percentages are high and indicate that the difficulty level of the programming tasks is low.\n\nIt is stated on page 6 that \"For generations that are either incorrect or slower than the original program, we use a speedup of 1.0 for that example, given that, in the worst case, the original program has a speedup of 1.0.\" This explains some of the 6.86X result: the evaluation setup is such that only good generations are considered in calculating the metric.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zNxhW6pwmc", "reviewer": "Reviewer_jit6", "summary": "This paper introduces a dataset for learning code performance improvements. Based on this dataset, the capabilities of both open-source (CodeLlama) and proprietary models (GPT3.5/GPT4) to optimize code were tested using various PROMOTING and FINETUNING methods. The effectiveness of different methods and the performance differences between open-source and proprietary models are analyzed based on the experimental data.", "questions": "1. How do you view the impact of training LLMs using synthetic data (generated either by the trained model itself or from other models)? Assuming synthetic data is generated by the trained model M and undergoes data filtering, how would the output distribution of M change?\n\n2. I noticed a statement regarding the comparison of LoRA training: \"We hypothesize that this gap may be because performance optimization examples do not occur naturally in the training data.\" Can you provide a clearer version of this statement, or offer a more specific explanation?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper conducts comprehensive experiments on the task of improving code performance using LLM, and offers a comparative analysis of the effectiveness of various recent methods. This work will contribute to aiding researchers in the domain to better enhance the capabilities of code generation models.", "weaknesses": "1. Regarding the experiment in Section 4.1: In Table 2, the performance of GPT-4 under the Few-Shot and CoT methods for code optimization was not tested.\n\n2. Data in Section 4.2 shows that after training on the synthetic dataset, there is a noticeable performance improvement in Best@1, but only a slight increase in Best@8. In fact, for the combination of < HQ+Self-Play, GPT-3.5 >, there is a minor performance decrease (95.42%->95.11%). The paper does not provide a convincing explanation for this.\n\n3. Different types of code have varying scopes and complexities for optimization. The paper does not clearly state the proportion of each language type in the training data nor in the test code.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)