Learning to Improve Code Efficiency
Authors: Binghong Chen
Daniel Tarlow
Kevin Swersky
Martin Maas
Pablo Heiber
Ashish V Naik
Milad Hashemi
Parthasarathy Ranganathan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Machine Learning for Code
Program Synthesis
Program Optimization

Abstract: Improvements in the performance of computing systems, driven by Moore’s Law, have transformed society. As such hardware-driven gains slow down, it becomes even more important for software developers to focus on performance and efficiency during development. While several studies have demonstrated the potential from such improved code efficiency (e.g., 2x better generational improvements compared to hardware), unlocking these gains in practice has been challenging. Reasoning about algorithmic complexity and the interaction of coding patterns on hardware can be challenging for the average programmer, especially when combined with pragmatic constraints around development velocity and multi-person development.

This paper seeks to address this problem. We analyze a large competitive programming dataset from the Google Code Jam competition and find that efficient code is indeed rare, with a 2x runtime difference between the median and the 90th percentile of solutions. We propose using machine learning to automatically provide prescriptive feedback in the form of hints, to guide programmers towards writing high-performance code. To automatically learn these hints from the dataset, we propose a novel discrete variational auto-encoder, where each discrete latent variable represents a different learned category of code-edit that increases performance. We show that this method represents the multi-modal space of code efficiency edits better than a sequence-to-sequence baseline and generates a distribution of more efficient solutions.

Under review as a conference paper at ICLR 2023
LEARNING TO IMPROVE CODE EFFICIENCY
Anonymous authors Paper under double-blind review
ABSTRACT
Improvements in the performance of computing systems, driven by Moore's Law, have transformed society. As such hardware-driven gains slow down, it becomes even more important for software developers to focus performance and efficiency during development. While several studies have demonstrated the potential from such improved code efficiency (e.g., 2x better generational improvements compared to hardware), unlocking these gains in practice has been challenging. Reasoning about algorithmic complexity and the interaction of coding patterns hardware can be challenging for the average programmer, especially when combined with pragmatic constraints around development velocity and multi-person development. This paper seeks address this problem. We analyze a large competitive pro- gramming dataset from the Google Code Jam competition (Google Code-Jam) and find that efficient code is indeed rare, with a 2x runtime difference between the median and the 90th percentile of solutions. We propose using machine learning to automatically provide prescriptive feedback the form hints, to guide program- mers towards writing rege-performacce code. To automatically learn these hints from the dataset, we propose a novel discrete variational auto-encoder, where each discrete latent variable represents different learned category of code-edit that increases performance. We show that this method represents the multi-modal space of code efficiency edits better than aequence-to-sequenee baseline and generates a distribution of more efficient solutions.
INTRODUCTION
The computational efficiency of code is often front-and-center in any computer science curriculum. While there are many ways to solve a particular problem, there often wide variance the runtime of different implementations. This variance is often attributed to many different factors: the algorithmic complexity of the code in question, the data structures that are used, the libraries that are called, and lower-level execution effects like efficient caching or memory usage.
Similarly, computational efficiency is a critical component of professional software development. The computing industry as a whole has relied the automatic performance increases of Moore's Law to scale massive warehouse computing systems to meet the internet requirements of the world. As these automatic performance increases slow down, the burden of reducing computational cost and carbon footprint now falls on writing herh-peeformance code (Patterson et al. (221))
Writing efficient code is challenging, even for experienced programmers, as it requires understanding computational complexity as well as the underlying hardware. Lower-level performance optimizations therefore automated by compilers which automatically apply small set of known, sound low- level program transformations to an already written program to increase its efficiency. However, compilers and current tooling have more difficulty identifying higher-level optimizations, such as more efficient algorithms for the same problem. So far, these types of optimizations could only be identified by humans. We hypothesize that machine learning can be used to guide humans towards such optimizations, by suggesting edits that optimize code efficiency.
To study this problem, we examine a competitive programming dataset where tens of thousands of developers have submitted answers to about 180 different questions. Studying these solutions, we find wide variance in computational cost: the runtime difference between a median solution and the 90th percentile is over two-fold. The scarcity of nigh-performance solutions highlights the difficulty of our task. Therefore, we aim to provide prescriptive feedback to developers to guide them towards writing perf-pereormance code.

---

Under review as a conference paper at ICLR 2023
We develop framework to apply multiple categorical transformations to single program using novel discrete variational autoencoder where different vectors in the latent dictionary lead to different code transformations. We find that these learned categories latent variable may control the data structure that is used for a particular problem or for-loop vs. a while-loop), and that by applying these transformations the program, more efficient computational efficiency category vs. the code that the developer wrote.
often consistent (e.g., . particular
move solutions into
This paper makes the following contributions:
We frame code efficiency optimization as a generative problem.
Using the Google Code Jam competitive programming dataset (Google Code-Jam), we analyze the distribution and characteristics of high-performance solutions. We find that high-performance solutions uncommon and consist of combination of many distinct optimizations. We then derive a canonicalized program-edits dataset to train models to improve code efficiency.
We propose a novel discrete generative latent-variable model of program edits to model a distribution of fast programs, conditioned their slower counterparts. We find that this model outperforms a sequencc-f0--eqquene baseline along three different axes: correctness, efficiency, and diversity.
We qualitatively demonstrate that the learned discrete latent variables represent different edits, and that the edits that are assigned to one latent variable are generally consistent. As side-effect, we learn an interpretable program embedding space.
We believe that these results are a promising step towards automating the process of identifying and applying higher-level performance optimizations, which would fundamentally increase the capabilities of current developer tools while reducing the carbon footprint of computing.
BACKGROUND
2.1
PROBLEM FORMULATION
There are many different ways to implement particular algorithm. For algorithms like matrix multiplication, small syntactic changes like loop reordering have a dramatic impact on execution cost (Leiserson et al. (2020). From low-level hardware effects like caching and branch prediction, to higher-level code choices like data structures, termination conditions, and loops navigating the space of implementation options is key element of software engineering.
We find many of these performance archetypes when looking at competitive programming solutions. Figure [T shows three example programs the left and faster versions of those programs the right. The first example showcases using a more efficient datastructure (a heap), which then enables early termination of the main loop. The second example highlights performance bug, where fewer API calls can accomplish the same task. The third example highlights how using built-in libraries can be faster than writing bespoke implementations. These examples represent just three of the many discrete design choices that developers make while coding their solutions. We hypothesize that these discrete choices can learned, such that a generative model can suggest different code transformations that developer could leverage to increase code efficiency.
2.2 PROGRAM EDIT DATASET
To study this problem, we use the dataset from the Google Code Jam international competitive programming competition (Google Code-Jam). Each question consists of problem description, along with up to three test cases - inputs and desired outputs - of increasing complexity. For each question, the dataset contains solutions from competition participants. If the submission passes each test, is labeled as correct and annotated with run-time, otherwise is marked as incorrect.
For our study, focus the solutions that written in Python. As aim study execution complexity, we focus only on correct submissions and consider the run-time of the largest test case. This distribution of run-times is shown in Figure [
Even for this constrained competitive programming task (with a natural focus on efficient solutions), Figure 2 a) illustrates wide distribution in run-time- supporting our hypothesis that writing efficient
2

---

Under review as a conference paper at ICLR 2023
Version Rumbime-nmm000
VersioniRuniiime2222 Speedup)
(nn(Urpan))
Iepart kwlp
for
Etarto) Lowers- *]]
"("(Ceutte))
touse [tot0) for trpott)appitt" ')]
Thtx la atl you sest for nost Ridutartt problono.
(e((ee))))
tiee
Lotege
Algorithmic Difference: heap ewiy
for resgecs t- 23)
prices [LotE) teputO appttt"
readt
eall tr (ucl)
prtost"Case #g: (? formatts reautt))
houss
abile arices and bapp.hhaappprrrooo
ane bese
prtee("Case #t:: (2" -ormatts, touses))
Slow Version (Runtime=0.5e
Fast Version (Runtime=0. 14::: Speedup)
(et(ivpntO)
reseltiee))
(anee()))
rargel casse) pithitopat))
(ec(tapunt)
pacs pach retaaettte (1e1
multill I also efficien upproach
pets aeth www.tttttcce (91)
Far to rappicasee):
smappling two characters, using four calls "repiaca" instead three.
src.apped((irs)
privst Gae #1,24, "_and]3.copu=")
rycethemartt replacat (T)
resilts espeniinepath))
prtectitase tr,,,, ooge))
[Runtime-0223g)
[Runtime=0.155 Speedup)
welies (
prie (etcleputE)
Algorithiic Difference: bulliin of ofreiiplemmnningg
teput()
atr(teput())
path (rpat()
cutpee
efficently Nigh
path aick.rettacstt""" "e"),reptas"""", *))pppp))))
rage(Tenfaath)) pebiis) 'S'x
privtt"Casx ()" ('*/ammets,
stoe:
estpet
te reepecloncurtent:
Lf wrtpet)scee)) aethloces1]:
prtntt"Cese KQ) ('" formatciel, outooat))
Figure 1: Examples from the program pair dataset. Each row corresponds to data point, containing the input (slow) submission and the output (fast) submission.
1002
15000
4320
23000
.003
10003
2000
42000
1000
203
400
200
100
1000
accondh)
Length
Palacios improvmmen rankime
(a) Program runtime
Program length
(c) Pairwise relative runtime
Figure 2: Dataset statistics.
code difficult problem. We observe solutions with run-times that are fractions second. as well as those that time-out after 5 seconds. High-performance solutions are rare. Additionally, Figure b)) indicates that the data is multi-modal with wide textual distribution of solutions. Solutions are short handful of lines of code and stretch patterns these solutions that lead to efficient code, so that we can provide hints to programmers to improve performance.
thousand. We aim to discover the common
We frame this task as a -oeenncce----uuunceee problem: given an input code sequence, output a more efficient version of the code. While sequence-to- eeequuece--ssequence modeling is often posed as one-to-on problem, our task is a one-to-many problem, as there are an overwhelmingly large number of such solutions single problem. Trivially, could simply rename variables change syntax. We
3

---

Under review as a conference paper at ICLR 2023
would like focus substantive changes, deal with this in two ways: first, canonicalize the code submissions by renaming variables, function names, and strings with generic tokens. Next, we construct dataset of inputs and outputs by pairing programs according their similarity. Specifically, we use the ROUGE-8 metric to score the similarity hetween all pairs of canonicalized submissions. Similar programs with significant run-time difference (we choose 1 1.2x speedup or larger) are added to the dataset. Figure 2[c) shows the relative runtime difference between the slow/fast pairs in the dataset. Consistent with 2 a), we observe a broad distribution of run-time differentials.
We find that this canonicalization approach enables the model to learn on this dataset, but also means that we lose the ability execute the edited program to evaluate run run-time. However, even in canonical form, edits are qualitatively sufficient to identify optimizations. Section 4.3 describes the quantitative metries that we use to further evaluate the quality of these edits.
METHOD
3.1 MOTIVATION
Our goal is create a model that can condition on given program and help developers identify more computationally efficient variants of that program. There are three factors that we use to drive our modeling choices and evaluation. 1) The resultant hints should be syntactically coherent. As the model provides suggestions, the suggested changes do not need to be perfect, but still need to make sense. 2) The changes suggested by the model should lead to more computationally efficient code. To quantify efficiency,
rely textual similarity to other known correct code in the data-set that is more efficient. 3) For given source program, there are multitude of discrete transformations that could lead to more efficient code (that is, the problem one-to-many). For example, more efficient code versions could change the data structures involved, wrap/unwrap code in functions, or adjust loop bounds. These edits are not known priori, so the model should automatically learn which transformations increase efficiency, and then communicate those choices to developers. Therefore, an ideal model would be able to generate many different distinct hints, so we consider code diversity as an auxiliary objective. The criteria mentioned above (efficiency, correctness, diversity) inform our we describe specific metrics quantify each of these criteria.
modeling choices. In Section 4.3
3.2 NOTATION
We denote an input sequence x = [21, T2, TT. and an output sequence y = [y), U2...., yrome where Tis Vj tokens in vocabulary V. We will represent the encoder as f-)-) and the decoder as (-), where f and & are the parameters of the networks. As is standard sequence modeling, we embed tokens using an embedding function e(-) and add positional encodings PE. Unless is informative to say so, we will assume that this is done implicitly.
3.3 BASELINE MODEL: TRANSFORMER
Prior work in program optimization often operates at the compiler or assembly-code level (Schkufza al. 2013). As we aim to provide much higher-level natural language hints to edit source code instead,
a state-of-the -fate-of-the-art the-art natural language model as baseline (Vaswani et al. 2017). The baseline Transformer is trained in a sgquence-to-eqqenne fashion, where given a pair of programs with runtimes Tslow and Trasts use the slower program the input x, and the faster program the output y. We encode the input program using fx) and decode the output program using Ie (f)))). We train the network to minimize cross entropy loss. To generate different programs given input program, we simply randomly sample outputs.
3.4 DISCRETE VARIATIONAL AUTO- EITOOENNODERS
As an alternative to a fully black-box solution, we propose solving the problem with a more explicit and interpretable model. Since we observe in the dataset that there are many discrete categories of efficiency-improving code transformations, we propose using discrete variational auto-encoder to learn these categories in an unsupervised way. Furthermore, we are interested in learning fine-grained edits of code, where each category of learned edit ideally represents single conceptual or localized change. Towards that end, we encode
4

---

Under review as a conference paper at ICLR 2023
Transformer Encoder
cpp
Dictionary
Training
Transformer Decoder
Fedt Zy 2g
app
Transformer Encoder
Generation
app
F Prior Samplex
recon loss commi tment
loss
Figure 3: Conditional program edit VQ-VAE.
Program
lodonicalzodd Program
Proposed Edit.
Manually Apply Changes
Orignss Program
Effccincy idia This greddy tosooaet inplemeentiinn diA
Optimaed Programyt Exr Truttrt
lo
Elitto lavato uatuec "y
the euliin wnli leag mewape sontis part astualy victt
cada
Edit Sugesppittionn (Canonicalloo Program)
(etto for aot
test
leao belieets
Telly) (rgan)) sprit (hiee))
breek
Wirt Taa AMCO sargo)
powit CION Aommatt,
Seall Auneeyyy 41)
Figure 4: An end-to-end example of the model's output and its intended use by a programmer. The model directionally suggests a code efficiency optimization for the programmer to consider.
and y into latent vectors Aast and Velow and take their difference Zedit. Fast Zolow capture the necessary information to edit x into y. This two-tower encoding approach with tied encoders allows the model to learn relative edit encoding, which we find helps training stability. We find that code canonicalization aids in learning this relative encoding, as it removes semantic differences between the input and output programs. The embedding vectors Ztast and Zylow computed using multi-headed attention layer between the encoded outputs from fa and a learned query vector c. This form of pooling has been found in other works well (Lee et al., 2019).
To capture the one-to-many relationship of code edits, and to further emphasize the idea of broad and interpretable edit categories, choose VQVAE quantize Zedit. (Van Den Oord al., (017)) This allows us to train generative model of K discrete edit types. Each type, when applied to a piece of code, produces a different result. This also has the advantage of preventing posterior collapse, pervasive issue with variational auto-encoders, especially with respect to discrete sequence modeling.
Specifically, we learn a dictionary of embedding vectors Z [21, Z2..... ... Zk]. When encoding the difference vector, we set Zedit argmin,, || (.el (y) fe ll. Our Edit- VQVAE model is illustrated in Figure and our forward and decoding procedure outlined Algorithms and in the Appendix. To support this model, we modify the decoder to take Zedit as auxiliary input. The total input to the decoder is therefore the sum of the token embeddings, positional encodings, and difference vector: e(x) + PE + Zedit
EVALUATION
4.1 METHODOLOGY
The primary utility our model is to provide hints to programmers that identify improvement opportunities for their code. This means that changes suggested by the model do not need to be
5

---

Under review as a conference paper at ICLR 2023
perfect; they just need point programmers in the right direction. We evaluate these hints first qualitatively in Section 4.2 then quantitatively in Section 4.3
Experimental setting. The program pair dataset for training and evaluating program optimization tasks is constructed from the raw dataset following the procedures described in Section 2.2 After processing the raw program submission dataset into program pairs, randomly split the program pairs into training, validation and testing set. The training/validation sets contain 806, 041/1, 458 program pairs. The program pair runtime distribution is illustrated in Figure c).
contains 100 input programs that are not visible during training. The
We implemented all models in Jax (Bradbury al. 2018), and trained the models using peak learning rate of 0.01 with both warmup and decay schedules. All models were trained with a batch size of 16 for 100 epochs, using distributed data parallel training on 64 Google Cloud TPU cores and 16 host machines. We performed rudimentary hyperparameter tuning for all models. For all Transformer blocks, we set the dropout rate to Puropout 0.1, the attention layer embedding size to dmodel = 128, and the feed-forward inner layer size to da 512. We use 6 Transformer layers, each with attention heads, for both encoders and decoders. The VAVE has K = 64 latents. quantitative evaluation, we randomly sample N = 64 programs from each model for evaluation. The Edit- VQVAE generates program per latent.
4.2 EDIT VQ-VAE QUALITATIVE ANALYSIS
One of the main benefits of a discrete latent variable model is an interpretable latent space that we can to visualize the learned efficiency archetypes. After training and during generation, we remove the encoder and directly feed the canonicalized program into the decoder along with categorical variable that selects one of 64 discrete latent edits. A real learned example of this is shown in Figure 4 The canonicalized program is edited by the decoder to increase performance (in this case the model suggests heap). We find that these edits expose the key optimization idea that can then be translated back into code by the programmer.
We often find that each of the discrete latents is responsible for a single syntactic change (adding a heap data structure, changing for-loop to a while-loop and vice versa, adding functions, etc.) and that we can take different transformations on the same program by varying the latent code provided to the VQ-VAE. The model learns many different efficiency archetypes (Table 2 including those discussed in Section 2
We can visualize the effect that the transformations have on different program pairs through PCA decomposition as well (shown in the Appendix). If the latent variable has learned to apply a similar edit to its input programs, one would expect that the slow programs would be collectively moved to faster region of latent space. We observe this behavior in Figure
4.3 QUANTITATIVE RESULTS
Beyond the qualitative analysis in Section 4.2 by the Edit VQ-VAE vs. a vanilla sequence-to-sequene Transformer on three axes: correctness, efficiency, and diversity.
we quantitatively evaluate the suggestions provided
Evaluation metries. We use syntactic program similarity as tool to measure model performance. Program similarity is computed between the generated programs and a set of reference programs, where the reference programs are programs in the dataset that solve the same question more efficiently than the original input program. For each input program or in the test set, we construct its reference program set as follows,
R(x) = (y E Dy, rruntim(y)) < runtime(x) and ROUGE_ < <1),
where D3= E D the subset program submissions in the dataset D that solves the same question Ou as input program æ, and t > 0 is threshold for the program neighborhood. We propose the axis-specific metrics below, which are built upon conventional text similarity metrics such as the BLEU score (Papineni al. 2002) and the ABLEU score (Galley et al. 2015).
Correctness Delta, i.e., similarity between the generated program and an existing solution to the same question as the input program. We adopt the BLEU score here surrogate. For any

---

Under review as a conference paper at ICLR 2023
Average results (64 Samples)
Maximum results
Corr.
Effi. -aad
ssft
Corr.
haad
Effi.-soft
Diversity
Edit- VVAI-VQVAE
0.760
0.059
0.765
0.867
0.359
0.875
0.807
VQVAE
Edi
0.785
0,027
0.789
Transformer 0.572
0.006
0.608
0.733
0.125
0.769
0.655
Transformer* 0.575
0.015
0.611
0.769
0.242
0.808
0.684
Table I: Performance of the proposed model and baselines measured by correctness (Corr.), efficiency (Effi.), and diversity metrics. Numbers are between and 1, higher is better. The best result is bolded. The numbers from the first three columns obtained by taking the average over the metric scores of all N samples, the middle three columns by taking the maximum. The last column is computed based on all N samples. The VQVAE does converge and thus results in poor performance (denoted by a +");; Edit- VAE suffers from severe posterior collapse, so there is only one sample generated from the model. Hard metries require exact matches while soft metries use ABLEU.
generated program y, the correctness score is defined as,
Sc x) BLEU(candidate = references = R(x)).
(2)
Sc gives a score in [0. 1]. a score of indicates there is a perfect overlap between á and the reference programs in R()), while score of 0 means there is overlap. A higher S. score indicates that the generated program is more similar to the reference programs, implying less programmer effort translate the suggestion into correct program.
Efficiency Delta, i.e., similarity between the generated program and an existing more efficient solution to the same question as the input program. There are two considerations: 1) how much more efficient an alternative program is compared to the input, and 2) how different this alternative program to the suggestion. We adopt two metrics for efficiency, a hard metric using an exact match, and soft metric using ABLEU.
If the generated program ý has exact match with one of the reference programs in R(x), we can directly use its runtime to compute the efficiency for ÿ. The exact match score is defined as,
min y VER()) runtime(s/)
SEH
A max [ v) yER(z)
runtime(y)
SEH gives a score in [0, 1], score of 1 indicates an exact match with the most efficient program in the reference set, while score of 0 means exact match.
Requiring generated programs to be exactly the same as a reference program will undervalue good suggestions that are close to an efficient solution, but not exactly the same. Therefore we also employ the ABLEU score as a soft version for efficiency. ABLEU a variant of BLEU where each reference can be assigned with unique weight indicating the quality of the reference. The score is defined as,
SEs(ū.x) & ABLEU(J, R(x), weight(y) ming runtime(y'),
(4)
runtime(y)
A reference program is assigned a higher weight if it is more efficient. SEs is in [0, 1], score of indicates a perfect overlap between Ò and more efficient reference program. As with correctness, this approximates how much additional work would be required to transform the suggestion into an efficient solution.
Diversity, i.e., whether the model can generate diverse efficient programs given one input program. We define diversity as the model's ability to recover the of reference programs using the J. The diversity score is defined as,
generated programs ((x) {vi.
Sp
Σ
max BLEU v).
(5)
R((x)
(E)(2)
(ER(()
Sp is in (0, 1). A score of indicates perfect recovering of the reference
7

---

Under review as a conference paper at ICLR 2023
Our results are summarized in Table I For metrics correctness and efficiency, we show both average and maximum performance over the N samples. We find that Edit- VQVAE outperforms sequence Transformer baseline by large margin all metries. As one-to-many model, the Edit- Maee-QQVAE is able to learn the program edit distribution from program pairs that share the same input programs in the training dataset. Conversely, requence-to-sequenee better when learning a one-to-one mapping with a single mode, but do not guarantee the quality of multiple random samples. This is supported by our data showing that the gap between the Transformer baseline and the Edit- VQVAE is smaller on the maximum results than on the average results.
the sequence-to-sene Segueenceto-seqqeenceeeeeeeee
models perform
The Transformer baseline is trained using all the program pairs in the same training set as the Edit- VOVAE. What if the Transformer baseline is only trained on the program pairs with the largest relative performance? Would its maximum results outperform Edit- aatt-V Interestingly, the answer is no. For program pairs that share the same input program in the training set, we only keep the pair with maximum runtime improvement. This filtered dataset is used to train another Transformer model, denoted as Transformer*. Transformer significantly outperforms Transformer on the maximum metries, but it still underperforms EQVAE.
To understand the effect of the design decisions in Edit- VVVE,, we perform ablation study by removing the discrete and adit-baset structure in the model. This results in two ablated models: 1) VQVAE without the edit structure, and 2) Edit- VAE. In the VQVAE, the latent is obtained by directly feeding the concatenation of the program pairs into the Transformer encoder, leading to a model with 4x parameters. In the Edit-VAE, the discrete latent space is replaced by the original continuous Gaussian latent space. Empirically, we found that it is difficult for VQVAE to converge. We hypothesize this due to the fact that is hard control the scale of the output of Transformer encoder block. The edit-based structure instead uses relative encoding, which potentially controls the scale of the encoder output, and helps stabilize training. Additionally, we found that the Edit- -AE model suffers from posterior collapse and is not able to generate more than one program during test time. Edit-VQVaa VQVAE is more robust to posterior collapse due to a discrete latent space (Van Den Oord et al. 2017).
RELATED WORK
Program Synthesis Program synthesis involves automatically writing code from a program spec-
ification. Many deep learning approaches have been proposed in recent years (Balog et al. 2016
Bunel et al. 2018 Devlin et al. 2017b Kalyan et al., 2018 Devlin et al. 2017at Lee et al. 2013 Nye et al. 2019 Odena & Sutton 2020 Parisotto et al. 2016). However, these works generally focused on writing code to satisty a given specification without regard for its efficiency. There are neural (Zhao et al., 2018) and non-neural (Meng et al., 2011) models that edit code, but these used for different applications such as fixing errors
(Yasunaga & Liang 2020 Chen et al., 2021b).
Language models and large-scale program synthesis Large language models (LLMs) built on Transformers (Vaswani et al.] (2017) and trained with massive amounts of data have begun to yield significant improvements in many natural language tasks (Chowdhery et al., (022).. These break- throughs have been ported over to program synthesis where LLMs have demonstrated an impressive
ability solve coding challenge problems (Austin et al. 202T Chen et al., 2021a). These approaches
have been concerned with generating a program from high-level specification, as opposed to editing an existing program to make it faster.
Other forms of optimization Program optimization has been applied to efficiency-related areas: Query optimization (e.g., using deep learning (Krishnan et al.] 2018: Marcus et al. (2019) seeks to optimize query execution plans for database systems. Stochastic superoptinization (Schkufza et al.) 2013) uses random search to optimize x86 assembly code. Assembly and queries are both highly structured languages and the programs are loop-free and quite small. We aim to optimize higher-level source code, which translates to vastly larger assembly programs, using a generative approach.
Discrete representations Many real-world problems are discrete, and discrete representations can often be more composable and interpretable. Learning discrete representations using generative modeling is challenging due to the lack of gradients, necessitating the of gradient estimators like the Gumbel- (Jang et al., 2016; Maddison et al.) (016) and REINFORCE (Williams) 1992). The VQ-VAE ( (Van Den Oord al. 2017) avoids this by using vector quantization and treating
8

---

Under review as a conference paper at ICLR 2023
(a) A transformation that adds early termination to while loop. We see that the model also applies other semantics preeeervig transformations that can be safely ignored.
setoo for to (swet) wolee) Eirtoeeciee w01r033
a letto teaet)) wiine Tesebwatioe teentt velta010
4) Ltatomactee trwet) sotte())
(reett) selent
e'SRDGs. fommettr 1),
Sreal
F) ('SSRD"" furattte 4) 1 flud tria)
(b) A notable change this transformation identified replace a [] operator with custom lambda using map operation with builtin, which indeed pattern that should lead to speed-ups.
Original
Edit #1
Edit 92
reseciattieeee CDt tentreectet. inpett antinca
Toettneteer (rputt) aoithrr2
Heite
(tretx) for to feent) aptted) turtomptinn, (px0)))
aaaee) Lity
TLT 3/NN
(c) In the first sample, the model identified an optimization to expressing loop condition. In the second example. identified different way express integer division (note that it even added the required mat h import).
Original
Edit
(2)
No. 45s
Iepart
fu a) (oodto (elnt)--elit)))
akili Io
I +
a (Dx 24 wil vieb
manert. destcleent) 130- Evelio for tepeO wet601
Or 10 (tetoo for ta treeD sitsO]
apxt shiae: FMV) 'ST2N01 1000 10
EECC STRDI + PVV) (STGK"" + fttly V.. 10330
Table Generated edits (middle and right column) for given input programs (left column) in the test set. Strings, variables and function names are canonicalized.
these latent codes targets. It has shown tremendous success in generative modeling for images, and largely avoids the posterior collapse issue that is prevalent in continuous VAEs (Kingma & Welling 2013). We are therefore able to use VQ-VAEs with powerful Tranformer-base encoders and decoders, thus reaping the benefits of both large language models and discrete representations.
6 CONCLUSION
In this work, we apply discrete categorical transformations source code. These transformations are aimed at increasing code efficiency, but could be useful for a variety of natural language tasks or discrete structures such as molecules or graphs.
We take one step towards learned models that improve code efficiency by demonstrating that discrete transformations can be learned from a supervised dataset and that the VQ-VAE provides one archi- tecture for doing so. To move beyond this paper and enable automatic optimization, canonicalization the first challenge that needs to be solved. There are many potential solutions, like using specialized pointer networks for variables using Transformer pre-trained
very large code corpus.
As we move towards building more ML models that can write code, it is critical that we also consider computational efficiency. Code that is run in datacenters across the world today contributes to not only cost, but also the carbon footprint of machines. We believe that optimizing this footprint is an exciting application of deep learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoe Le, al. Program synthesis with large language models. arXiv preprint arXiv:2108.0771
2021.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning write programs. International Conference on Learning Representations, 2016.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milnn and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://githbb.com/ggggl//a
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. International Conference on Learning Representations, 2018.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph. Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021a.
Zimin Chen, Vincent J Hellendoorn, Pascal Lamblin, Petros Maniatis, Pierre-Antoine Manzagol, Daniel Tarlow, and Subhodeep Moitra. Plur: A unifying, graph-based view of program learning, understanding, and repair. Advances Neural Information Processing Systems, 34:23089-23101, 2021b.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.023111 2022.
Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-inductton. Advances in Neural Information Processing Systems, 2017a
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, 2017b.
Michel Galley, Chris Brockett, Alessandro Sordoni, Yangfeng Ji, Michael Auli, Chris Quirk, Margaret Mitchell, Jianfeng Gao, and Bill Dolan. deltableu: A discriminative metric for generation tasks with intrinsically diverse targets. arXiv preprint arXiv:/506.0686) 2015.
Google Code-Jam. jam competition archive.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 1e..v::6611.014444 144, 2016.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guidae deductive search for real-time program synthesis from examples. International Conference on Learning Representations, 2018.
Diederik P Kingma and Max Welling. arXiv:1312.6114, 2013.
Auto-encoding variational bayes.
arXiv preprint
Sanjay Krishnan. Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and lon Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint 1xXi::180.003190 2018.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: framework for attention- based permutation invarriant neural networks. In International Conference Machine Learning, pp.
PMLR, 2019.
10

---

Under review as a conference paper at ICLR 2023
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices, 53(4):436 449, 2018.
Charles E Leiserson, Neil C Thompson, Joel S Emer, Bradley C Kuszmaul, Butler W Lampson, Daniel Sanchez, and Tao Schardl. There's plenty of room the top: What will drive computer performance after moore's ' law? Science, 368(6495)caamm7744 2020.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.0077 2016.
Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska,
Olga Papaemmanouil, and Nesime Tatbul. Neo: A learned query optimizer. arXiv preprint ArXiv: 2019.
Na Meng, Miryung Kim, and Kathryn S McKiinley Systematic editing: generating program transfor- mations from an example. ACM SIGPLAN Notices, 46(6):329-342, 2011.
Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama Learning to infer program sketches. In International Conference Machine Learning, 2019.
Augustus Odena and Charles Sutton. Learning represent programs with property signatures. International Conference on Learning Representations, 2020.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318 2002.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint 1rXiv:161..0185. 1.01555, 2016.
David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang. Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint ar /04. 10350, 2021.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. ACM SIGARCH Computer Architecture News, 41(1):305-316 2013.
Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-25) 1992.
Michihiro Yasunaga and Percy Liang. Graph-based, self-supervised program repair from diagnostic feedback. International Conference on Machine Learning, pp. 10799-10808. PMLR, 2020.
Rui Zhao, David Bieber, Kevin Swersky, and Daniel Tarlow. Neural networks for modeling source code (201). arXiv preprint arXiv: arXiv:/904.0220 /904.0281... 2018.
11

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 EDIT-VQVAE PSEUDOCODE
Algorithm Forward pass of Edit-VQVA. VQVAE
Require: Input sequence output sequence encoder fo(-), decoder go(:), embedding dictionary Z. positional encodings PE
1: Zfast f [x(x)
2: Zelow f (z)
3: k < argmnin& Btast Zslow ||?
4: Zedit & Zk
5: return J6(x PE Zedit)
Algorithm Generating from Edit- EQVA-V
Require: Input sequence output sequence encoder fo(-), decoder g+(.), embedding dictionary Z. positional encodings PE
1: Zfast f fx(x)
2: Zslow t- (z)
3: k < argminn |iaast Zalow 1|
4: Zedit < Zk
5: return [x PF Zedit)
A.2 ADDITIONAL FIGURES
12

---

Under review as a conference paper at ICLR 2023
15
10
05
00
-05
-10
0
-10_5
0
-10
-10
10
-15
10
-1
5
10
20
(a)
Figure 5: 3D PCA visualization of the program pairs assigned to the same learned latent variable. (a)/(b)/(c) are program pair samples from latent #8/#20/#40, respectively. The blue dots represent input (slow) programs. Upon making the edit, the programs move become the green dots, the corresponding output (fast) programs. We observe that the fast programs belong to a different region of latent space than the slow programs and that within each latent category, the programs tend to move together- demonstrating that the edits that each latent applies tend to be coherent (or similar).
Original
Suggested Edit
int((nput())
int(input())
while v: (v, v) rap(iat, input split()) Listirap(tnt, (aputt).ppltt())
for v ia range(v)
(v, v) nap(int, input ().plit()
List(rap(tnt, (nput().pptt()))
v.sort()
v. v.sort()
Original
Suggested Edit
(ne((nput()
int(input())
v while (v 9):
for in (v) List(rap(tnt, (nput((.split(()) =
().split))
nap(iat, input ().split())
List(rap(int, (oputt).spli(()))
= v.sort()
v.sort()
Original
Suggested Edit
def (v. v): v.sort()
(nt(Input())
v=1);
(v, v) = (ne(v) for (nput()..pit()
for ia
v = I int(v) for v in split() v.sort()
v (nt((tnuut)) for ta range (1, ved): (nt(v) for in toput(). (nt(v) (aput().sptttt))
for in range (V):
forsst,,, v))
rCr SSTEENGVSSTRENNEEVW v))
that the edits that the latent proposes tend to similar. In the first two examples, while loop is turned into a ranged for loop. In the third, more complex edit proposed. The function call is inlined into the original loop body and the for loop argument is changed to a range statement. For the other latents pictured Figure latent #8 proposes using map data structure and latent #40 factors code into functions.
Figure 6: Sampling programs from latent #20 above,
13

---

Under review as a conference paper at ICLR 2023
-10
Figure 7: 2D UMAP visualization of the learned latent space. The programs are colored by runtime interpolated between 0.01 seconds (yellow) and 5 seconds (green). The yellow/green dots tend to cluster together. This color pattern exists locally, instead of globally.
14

---

Under review as a conference paper at ICLR 2023
ranget tapetO ")]
priatt Cuse str()) atr(n)
Manually Apply Changes
Optimized Program(
Lnt(apet)
breat
Lnyort
Correciness Detta
(tet(v) tapet) catte STAENC STRING
olements from list in intreas ng order until we run out of spare. sartad has sort the entre list while heaplfy hhpppop only sont the part we actnnly visi.
print print "STENNG" fornatiy V)
Proposed Edit
Edit Sugges tio (Canonical alized Programi
For rempecod:
(f v- Bi
knapaaak implementtaion
(tastv)
break
etaz:
Model
Cs v) = (tatt)) for v in topant 3. sptttttt salteersssenne STEEE ))
(Let0) for ln (epet() splis STEEN )]
Canonicalized Program
+>)
Efficiency
for in reneect. v 311
witte v tei())
V Lestupptt)
if voeet
voxl) md
F(O
elae:
Canonicalize
-oDtptttee ((at(oor) Uipot sptitc" ")]
prtent"CCa 0 formettt. (.houes))
Program
Original
(
tn respCl
15

---

Under review as a conference paper at ICLR 2023
for ranse()) for in splteO -ist(napp(itt (npeCO spitx())
(v. v) - ((et()) for v la (rpur() (ptt10
(iet()) (nous(.
v= (f. floorrr v v 1)) vv[l
List(mup(iat, (nlite))))) (olikt))
v (tst(v) for u to (ont().sspee)))) spli:0) 'SRENGG
Edit #2
Edit #2
"STENG')
forst((y v)
Edit
rengett, (e 1));
f('smnnG forratt..
for in ((range(v))
v
vs int(((mprt))
(nr((opuut)
for (nt((trput))
vitte (v 0)
v.sort() for iffe --v
v.sortg
v.
return
Irport
v
For in compe(aa((ippeee) tat(v) for inpet() sp33t(
range(s, (int(trpurE) in irput() (mput(--1nitt)))) mn)st))
FCEEC'S f()) "STRONC' (())))
< List(mattnn: ((puz) (pitt())
(r. v) = (int() anlt))
(imt()) for in inpet spiskO f(v .)
range (or =pttt)
Edit
Edit #1
(v. v) - raptiat: topet) )
Edit
-(((v v -vv
f(r STRING $))STRENG())
idC <- v):
Wastrannit v.sort())
breck
0):
ttt STRENG')
for v:
(lento)
For v in tf(vv
break
v.sort()
def f(v, v):
retirn
v 8
otae:
T0:
for v te range((n 1) int(v) for impet() sptte) Hettmmpitt
(v. v) - [tat(>) for v to toput() tiput(.cplteE) =ppt=0]]] Listisaptint tspot() (p(tz())
(v. v) (iat()) Ssput() =ppi=00
FCCC FCCCC'STII STRTNN' f(2)) "STRING' F(O)))
v- (Unt(v) for in inwu()) (nwut).sptte)) satte(] v ((range(ten())))
Original
Original
Original
re'STRaNd fomatt(o 5) v))
def FQ (trt(Gaaun()
R'STRING' (owr) v))
iffv v):
sf(F . 'STmnG')
in vz
v.sortt)
for v vs
y.s0rt()
iffs
=
1o
16


Reviews:
[{"review_id": "srj0D8chuRO", "reviewer": "Reviewer_hCSu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper addresses the task of improving the efficiency of code, by providing feedback hints. The authors curated a dataset from the Google Code Jam competition, and trained a VQ-VAE model to automatically provide feedback on how to improve the runtime efficiency of the solutions. ", "summary_of_the_review": "The paper addresses an important problem using a clever source of data.\nHowever, it suffers from a major evaluation weakness, since the main claim of \"improving efficiency\" could not be measured.\nThus, I must vote for rejection at this time, but I hope to see the paper's evaluation improved in the future.\n\nI **will increase my score** if the evaluation could show an actual convincing improvement in runtime.", "strength_and_weaknesses": "## Strengths \n* The task of improving code efficiency is important and exciting\n* The application of improving code efficiency is novel, as far as I know.\n* The idea of curating a dataset of code competition solutions is clever, since these solutions can be executed and their runtime can be measured, and this runtime can serve as a signal for training.\n* The proposed VQVAE model is interesting and performs better than the straightforward transformer (although not a contribution of this paper).\n\n## Weaknesses\n* Evaluation - The main weakness is evaluation. To train the model, the authors canonicalize the solutions in a way that does not allow to execute the edited programs anymore. That is, there is no way to measure whether the generated \"improved\" programs actually run faster than their original versions.\nInstead, the authors use varieties of BLEU to measure whether the prediction is lexically similar to the reference. This measure is problematic, since lexical similarity does not guarantee faster execution. In fact, the solutions were clustered using lexical similarity initially (ROUGE-8), so the \"slow\" program and the \"fast\" reference program are already supposed to be quite lexically similar.\n\nThere is no need to generate executable programs in all papers; however in this paper, since it focuses on improving the efficiency of programs, demonstrating that the generated programs are indeed more efficient is crucial.\n\n* Confusing terminology - some claims in the introduction are very confusing, and might not necessarily be correct.\nConcretely, I think that the authors confuse \"long runtime\" with \"low performance\", and assume that every solution that takes a lot of time to run must be low-performance. For example, the introduction says `we find wide variance in computational cost: the runtime difference between a median solution and the 90th percentile solution is over two-fold`. But why are solutions to different problems comparable? This variance might stem from simply the variance in the questions, instead of the variance in the solutions, as the authors imply.\n\nFor example, an extremely inefficient solution for \"binary search over 100 numbers\", implemented in `O(n)` instead of `O(log(n))`, might run much faster than a super-efficient solution for \"Bellman-Ford algorithm over a clique of 1000 nodes\", but the inefficient solution might still run faster than the efficient solution, if we compare their absolute runtimes.\n\nThe paper concludes that `The scarcity of high-performance solutions highlight the difficulty of our task`, and `high-performance solutions are uncommon`. However, I was not convinced that high-performance solutions are scarce or uncommon. A solution may be high-performance - *but still have a long runtime*, because the problem it is solving requires polynomial time complexity, or its test inputs are longer, for example. In other words,\n**a solution to a problem that requires polynomial time complexity is not necessarily inefficient** compared to the other potential implementations of the same problem.\n\n* Analysis -  Since the VQ-VAE model is not the straightforward transformer, and the authors claim that `each discrete latent variable represents a different learned category of code-edit`, it would be nice to see some analysis of the learned latent variables and what have they captured, to understand why does the VQ-VAE perform so much better than the transformer.\n\n## Additional Questions\n1. The introduction says that `compilers and current tooling have more difficulty identifying higher-level optimizations, such as more efficient algorithms to the same problem`. Does the proposed model actually find \"more efficient algorithms to the same problem\"?\n2. Why are Figures 2(a), 2(b) and 2(c) meaningful? Why is it meaningful to compare solutions of different problems? The variance in program length or runtime might be natural and stem from the variance in the questions. For example, one question might have logarithmic complexity and another question might have exponential complexity. Why should we compare their solutions' runtime, and conclude that the exponential one is \"not high-performance\"?\n3. Does clustering of the submissions according to ROUGE-8 **really** find solutions to the same problem? Did the authors perform any manual annotation to verify that this is indeed the case? I can imagine examples where inter-problem solution similarity might be higher than intra-problem solutions. That is, solutions to different problems might be almost identical to each other, while different solutions to the same problem will be very different.\n4. Section 4.3 say that `We use **syntactic** program similarity as a tool to measure model performance`. But in fact, all the metrics that are described below are variations of BLEU. Why is this *syntactic* similarity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "HwGZRKfYd3", "reviewer": "Reviewer_39mZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "\nThe paper presents an approach to suggesting code changes that improve the performance of programs.\nThe paper first analyzes the distribution of (correct) solutions to competitive programming problems, finding a large gap between the efficiency of median-performance and top-quantile-performance solutions.\nThe paper proposes a generative approach to suggesting these code changes, based on a discrete VAE style approach.\nTo train, the approach uses Transformer encoders to encode a program and a corresponding optimized version of that program, takes the difference between the embeddings to generate an edit vector, discretizes the edit vector, and then decodes a new program using that discretized edit vector.\nAt evaluation time, the approach selects a random edit vector from a dictionary of trained edit vectors (representing different possible program edits), then decodes that using the original slow program to produce a new program with that edit applied.\nThe authors find that this approach qualitatively results in programs with optimizations applied, and quantitatively results in programs becoming more similar to semantically equivalent, optimized programs.\n", "summary_of_the_review": "Weak reject.\nThough the paper shows promise, the near complete lack of a qualitative evaluation means that the paper does not rise to the level of acceptance.\nI would be willing to raise the score if the authors provide any of the following:\n* A user study demonstrating that the suggested edits lead to better code performance (while maintaining correctness)\n* A significantly more thorough analysis of the different $z_i$, showing the extent to which they consistently lead to the same proposed types of edits (on the same original programs and across different programs), the extent to which they encode semantically different types of edits with different $z_i$,\n* Generally, more detailed case studies of proposed edits\n", "strength_and_weaknesses": "\nStrengths:\n* Interesting problem under study, interesting and novel solution to the problem\n* Very clearly described approach\n* Strong quantitative evaluation of the results\n\nWeaknesses:\n* Weak qualitative evaluation of the results (see \"Quality\" below)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ESIjqFk-i8_", "reviewer": "Reviewer_SDKK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors propose a variational auto encoder that suggests code edits to improve performance of programs. The system is trained using programs from a Google Code Jam competition. Data also contains the performance of the solutions. Authors show improvement of their VAE model vs sequence-to-sequence baseline model.", "summary_of_the_review": "I think that the paper introduces interesting and well performing approach using VQ-VAE to provide hints/changes to improve efficiency of programs.\nI think that some additional work like comparing the approach to using LMMs would improve this paper.\nIdeally, it would be interesting if hints/changes could be translated back to pre-cannonicalized program form and programs evaluated there. Alternatively it would be good if authors did a user study and evaluation of providing the hints/changes.", "strength_and_weaknesses": "Strengths:\n\n- Improved hint/change generation results by using proposed VQ-VAE instead of Transformer model\n- In experiments the VQ-VAE performs better on hard efficiency metric that may indicate transformations that are correct and more efficient\n- Ablation study of Edit VQ-VAE vs VQ-VAE and Edit-VAE\n\nWeaknesses:\n\n- Does not compare proposed VQ-VAE to results achievable from large language models (LLMs)\n- Due to canonicalization of the code, authors cannot check if provided hints generate a correct and efficient program. Instead they use similarity metric to determine if program with changes/hints is correct and more efficient. This shortcut may be problematic if changes/hints only seem to be correct and more efficient, but in practice are not. This needs to be solved for more accurate evaluation in the future.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject