# Automated Code Editing with Search-Generate-Modify

Changshu Liu, Pelin Cetin∗, Yogesh Patodia∗, Saikat Chakraborty, Yangruibo
Ding, Baishakhi Ray Changshu Liu, Pelin Cetin, Yogesh Patodia, Baishakhi Ray
and Yangruibo Ding are affiliated with Department of Computer Science,
Columbia University, New York, NY USA.
Email: {cl4062@, pc2807@, yp2607<EMAIL_ADDRESS><EMAIL_ADDRESS>Chakraborty is affiliated with Microsoft Research Redmond, WA, USA.
Email<EMAIL_ADDRESS>Manuscript received June 7, 2023; revised August
16, 2021.

###### Abstract

Code editing is essential in evolving software development. Many automated
code editing tools have been proposed that leverage both Information
Retrieval-based techniques and Machine Learning-based code generation and code
editing models. Each technique comes with its own promises and perils, and
they are often used together to complement their strengths and compensate for
their weaknesses. This paper proposes a hybrid approach to better synthesize
code edits by leveraging the power of code search, generation, and
modification.

Our key observation is that a patch obtained by search and retrieval, even if
imperfect, can provide helpful guidance to a code generation model. However, a
retrieval-guided patch produced by a code generation model can still be a few
tokens off from the intended patch. Such generated patches can be slightly
modified to create the intended patches. SarGaM is a novel tool designed to
mimic a real developer’s code editing behavior. Given an original code
version, the developer may search for related patches, generate or write the
code, and then modify the generated code to adapt it to the right context. Our
evaluation of SarGaM on edit generation shows superior performance with
respect to current state-of-the-art techniques. SarGaM also shows great
effectiveness on automated program repair tasks.

###### Index Terms:

Bug fixing, Automated Program Repair, Edit-based Neural Network

††publicationid: pubid: 0000–0000/00$00.00 © 2021 IEEE

##  I Introduction

In a rapidly-evolving software development environment, developers often edit
code to add features, optimize performance, or fix bugs. This process can be
complex and requires a deep understanding of the underlying programming
language, as well as expertise in the relevant domain. To facilitate code
editing, developers often search existing codebases [1, 2, 3] or online
resources [4] for relevant code. They may also leverage automated code
generation tools such as GitHub
Copilot111https://github.com/features/copilot/. However, the search results
[5, 6] or generated code may not always be ideal, necessitating developers to
customize it for the given situation [7]. Therefore, developers may have to
further modify the generated code to achieve the desired outcome.

In the past, various tools and techniques have been proposed to reduce the
manual effort needed for code editing [8, 9, 10, 11]. These techniques can be
broadly classified into three categories:

Search, Generate, and Modify.

Search. Searching is a popular information retrieval-based approach to suggest
edits that were previously applied to similar code contexts [1, 2, 12, 13].
However, each retrieval-based technique relies on its perceived definition of
code similarity (e.g., token, tree, or graph-based similarity) and fails to
produce patches with a slight variation of that definition. As a result, these
methods tend to have limited applicability to diverse editing contexts.

Generate. In recent years, the most promising approach is perhaps Large
Language Model (LLM)-based code generation models where code is generated
based on developers’ intent and surrounding code context. Open-source code-
specific LLMs such as PLBART [14], CodeGPT-2 [15], CodeT5 [16], and NatGen
[17] have shown significant potential in code generation. Additionally,
industry-scale LLMs like GPT-3 [18] and Codex [19] have become widely popular
for generating source code and are used as the backbone of commercial code
generation software such as GitHub Copilot${}^{\text{\ref{copilot}}}$.

There is a subtle difference between edit generation and code generation.
Developers generate edits by transforming the original code version into a new
version, often by deleting and adding lines. Edit generation can thus be
thought of as a conditional probability distribution, generating new lines of
code by conditioning on the old lines. Existing LLM-based code generation
approaches do not capture granular edit operations: which tokens will be
deleted, which tokens will be inserted, and in particular, where the new
tokens will be inserted.

Edit. Many previous works [20, 21, 22, 23] designated special outputs to
represent edit operations. Recently CoditT5 [23] proposed an edit-specific
LLM. Given an original code version, CoditT5 first comes up with an edit plan
in terms of deletion, insertion, substitution. It then generates the edits in
an auto-regressive manner by conditioning on the edit plan. CoditT5 shows
promise in generating edits over vanilla code generation.

The goal of this work is to produce higher-quality code edits by harnessing
the power of all three techniques. Each approach offers unique ingredients
that can contribute to better edit generation.

Our Insight. Code search can retrieve relevant patches that provide more
guidance to a code generation model, leading to better patch generation.
However, most of the time, the patches generated with code search are off by a
few tokens from the intended patch—even random permutations and combinations
of the generated tokens could lead to an intended patch [24]. A more
systematic approach would involve using an edit-generation model that
specifically targets the generated tokens that require further modifications
(such as deletion, insertion, etc.).

This approach enables more focused and precise modifications of the code
generated in the previous step and finally outputs the intended patch.

Proposed Approach. We propose a framework, SarGaM, leveraging both code
generation augmented by search and modification to generate code edits. SarGaM
emulates a developer’s typical code editing practice where given an edit
location and context, she might search for related code, write the retrieved
code (i.e., generation) to the target location, and modify it to
contextualize. SarGaM contains three steps: (i) Search: An information
retrieval-based technique to retrieve candidate patches from a database of
previous edits that may fit the edit context, (ii) Generation: An off-the-
shelf code generation model that takes input from the edit location, edit
context, and the retrieved patches, and outputs a token sequence corresponding
to the edited code, and (iii) Modification: A novel code editing model
slightly modifying the token sequence from the previous step and outputting
granular edit operations in terms of deleted and inserted tokens

Existing edit-generation models [23] which aim to generate the edit operations
directly from the original version. We instead let a generation model generate
the token sequence first and then modify it further to produce the final
patch. We observe that a granular edit model generally performs better for
generating smaller edits. If a generation model already produces a
sufficiently accurate patch, applying edits on top of it can enhance the
efficacy of the edit-generation model.

Results. We evaluate our approach on two tasks: code editing and program
repair. For code editing, we examine SarGaM on two different datasets. SarGaM
improves $top1$ patch generation accuracy over state-of-the-art patch
generation models (PLBART, NatGen, and CoditT5) from 4.82% to 22.42% in
different settings. For program repair, we compare SarGaM with recent deep
learning-based techniques on Defects4J1.2, Defects4J2.0, and QuixBugs datasets
and report state-of-the-art performance. Additionally, we conduct extensive
ablation studies to justify our different design choices. In particular, we
investigate the three components, search, generate, and modify, individually
and prove that SarGaM can benefit from each one of them.

In summary, our key contributions are:

  * •

We prototype a code editing model, SarGaM, built on top of off-the-shelf pre-
trained code generation models augmented with the generation with code search
and code modification.

  * •

We propose a new code modification model that involves generating granular
edit operations (i.e., deletion and insertion operations at token granularity
as opposed to generating token sequences).

  * •

We demonstrate SarGaM’s ability to generate patches for general-purpose code
edits and bug fixes. Across most of the settings, SarGaM achieves state-of-
the-art performances. We present a detailed ablation study to justify our
different design choices.

  * •

We release our prototype tool at
https://github.com/SarGAMTEAM/SarGAM.git.

(a) Encoder-Decoder

(b) Decoder (Only)

(c) Levenshtein Transformer

Figure 1: Different Types of Transformer-based Generative Models

##  II Background: Code Generation Models

Machine Learning-based Code Generation has gained significant attention in
recent years, where code is generated given a Natural Language (NL)
description or code context. Different types of Sequence-to-Sequence
($seq2seq$) models play a significant role in achieving this success [25, 26].
The input to a $seq2seq$ model is a sequence of tokens
($X=x_{1},x_{2},...,x_{n}$), and the output is a token sequence
($Y=y_{1},y_{2},...,y_{m})$, where the model learns conditional probability
distribution $P(Y|X)$.

Recurrent Neural Networks (RNN) and Long Short Term Memory (LSTM)-based models
[27] once held a dominant role in code generation [28, 11, 29, 30]. RNNs and
LSTMs take a piece of code token-by-token in a sequential manner and try to
predict the next token by conditioning on the immediately preceding tokens in
the sequence. Both types of models largely depend on the tokens in close
vicinity and tend to suffer from not capturing the long-range dependencies
[31].

###  II-A Transformer for Code Generation

Transformer-based models [32] have recently outperformed alternative
architectures for code generation due to the introduction of self-attention
mechanisms. Transformers process the entire input token sequence as a complete
graph 222https://en.wikipedia.org/wiki/Complete_graph. Each token corresponds
to a vertex in the graph, and an edge connecting two vertices corresponds to
the ?attention? between connected tokens. Attention is the relative influence
of a token on the representation of other tokens in the sequence. Attention
weights signify the importance of a token in making the final prediction for a
particular task [33, 34]. The model learns the attention weights depending on
the task during the training process. The Transformer also encodes the
relative position of each token in the input sequence (positional encoding).

The attention mechanism and positional encoding allow Transformers to capture
more long-range dependencies. The self-attention mechanism enables parallel
processing of input sequence that leads to significant speedup during training
[32]. Many previous works use Transformers for code generation problems (e.g.,
patching, code editing, and program repair) due to their success. [35, 36, 37,
17]. Transformer-based models roughly fall into two categories: encoder-
decoder and decoder-only.

Encoder-decoder. As shown in Figure 1(a), an encoder-decoder model has a
Transformer encoder and an auto-regressive Transformer decoder. The encoder is
trained to extract features from the input sequence. The decoder generates the
next token by reasoning about the feature extracted by the Transformer encoder
and previously generated tokens. Thus, an encoder-decoder model can be used to
understand and generate code simultaneously. PLBART [14], CodeT5 [16], and
NatGen [17] are examples of encoder-decoder models trained on code corpora
with denoising pre-training. CoditT5 [23] further presents a custom pre-
trained model for code editing tasks using the same architecture as CodeT5.
MODIT [37], on the other hand, fine-tunes PLBART for code editing tasks.

Decoder-only. Decoder-only models only have an auto-regressive Transformer
decoder (shown in Figure 1(b)). Since there is no encoder, decoder-only is a
?generate-only? architecture. Such models are pre-trained in an unsupervised
fashion with large corpora to build Generative Pre-trained Transformer models
(GPT). Jiang _et al._ [38] show the effectiveness of GPT for the task of
source code patching. Other representative decoder-only code generation models
include Ploycoder [39], OpenAI’s Codex[19], GPT-3 [18], etc. Decoder-only
models are suitable for open-ended code generation, where a prompt describing
the functionality is passed to the model.

###  II-B Levenshtein Transformer

The Transformers usually generate outputs from scratch. When there is much
overlap between input and output token sequences (e.g., automatic text editing
where only a few tokens are changed, keeping most of the text as it is),
Transformers tend to struggle [40] to preserve the unchanged tokens.
Levenshtein Transformers (LevTs) [40] show promise in such cases, as they use
basic edit operations such as _insertion_ and _deletion_ to implement granular
sequence transformations. Levenshtein Distance [41] between the ground truth
and the output token sequence is measured during training after each deletion
or insertion. The predicted operation is chosen for the next interaction if
the distance reduces.

Figure 1(a) and Figure 1(c) show architectural differences between a vanilla
Transformer and a LevT. Although both share the same encoder and decoder
blocks, the vanilla Transformer uses a linear layer and softmax upon stacks of
decoder layers to predict the next token, while LevT uses three additional
classifiers to apply edit operations. In LevT, the output of the last
Transformer decoder block (e.g. $h=\\{h_{0},h_{1},\cdots,h_{n}\\}$) is passed
to following classifiers:

  1. 1.

Deletion Classifier: for each token in the sequence, this binary classifier
predicts whether it should be deleted(=1) or kept(=0).
$\pi_{\theta}^{\mathrm{del}}(h_{i})=softmax(W_{del}h_{i})$, where $W_{del}$ is
the weight matrix of the deletion classifier.

  2. 2.

Placeholder Classifier: predicts how many place holders should be inserted
between any consecutive token pairs in the whole sequence.
$\pi_{\theta}^{\mathrm{plh}}(<h_{i},h_{i+1}>)=softmax(W_{plh}\cdot
concat(h_{i},h_{i+1}))$ ,where $W_{plh}$ is the weight matrix of the
placeholder classifier.

  3. 3.

Insertion Classifier: for each placeholder we inserted in the last step, the
insertion classifier predicts which token should be inserted in this position:
$\pi_{\theta}^{\mathrm{ins}}(h_{i})=softmax(W_{ins}h_{i})$ ,where $W_{ins}$ is
the weight matrix of the insertion classifier.

We choose various Transformer-based code generation models to generate patches
and use a novel LevT-based edit generation model to further edit the generated
patches.

##  III SarGaM Approach

Figure 2: Overview of the SarGaM Pipeline and a Motivating Example of a bug
fixing patch taken from Defects4J1.2 dataset. Here, inside a for loop, the
loop counter initialization and loop condition ( int i=0; i¡weights.length )
are buggy and (int i=begin; i¡begin+length) is the expected fix. After the
Search (Step 1), SarGaM retrieves a similar patch (int i=begin; i¡n), the
retrieval of begin token benefits Generation (Step 2). The generated patch is
close to the ground truth: (int i=begin; i¡weights.length), yet not correct.
Finally, the Modification model (Step 3) further modifies the generated patch
by deleting weights. and inserting begin+.

We introduce SarGaM, a tool to synthesize source code edits (i.e., patches). A
patch is a set of edits to the source code used to update, fix, or improve the
code. Throughout the paper, we use code edits and patches interchangeably.
More formally,

###### Definition III.1

A program patch, $p:=\Delta(v^{0},v^{1})$, is the set of syntactic differences
that update a program version $v^{0}$ to $v^{1}$. Each change is a token that
is either deleted from $v^{0}$ or inserted to $v^{1}$.

We have designed SarGaM to mimic a real developer’s behavior while patching
source code. Given $v^{0}$, the developer may (i) search for the related
patches, (ii) generate or write the code, and (iii) further modify the
generated code to adapt it to the right context. To this end, we design SarGaM
to have these three steps: Search, Generate, and Modify. An overview of SarGaM
’s workflow is shown in Figure 2.

###  III-A Overview

SarGaM takes the following as input: $v^{0}$, the exact edit location (can be
captured using the current cursor location), and optional edit intent in the
form of Natural Language. SarGaM goes through the Search, Generate, and Modify
steps and outputs the final code version, $v^{1}$.

  * •

Step 1. Search: Given the input as a query, SarGaM searches a database of
patches to find similar patches applied previously in a similar context. This
step is similar to a search-based patch recommendation engine [1]. Each
retrieved patch is concatenated with the original input and passed to the next
step (see Figure 3). In the motivating example in Figure 2, given the buggy
code as query, the search retrieves a similar patch from the code base: for
(int i=begin; i¡n; i++). Although the retrieved patch is not perfect, the
introduction of the ¡begin¿ token facilitates the final result.

  * •

Step 2. Generate. This step takes the search augmented input and outputs a
token sequence to generate the patched code. We use off-the-shelf $seq2seq$
models [14, 37, 17], as discussed in Section II-A, to generate code. Figure 2
shows the generation step produces a token sequence for (int i=begin;
i¡weights.length; i++), which is close to the intended patch.

  * •

Step 3. Modify. However, the generated patch can still be incorrect, as shown
in our running example — often, they are quite close to the intended edit
(i.e., low edit distance), nevertheless, incorrect [42]. Developers still need
to modify the generated patch here and there to get the intended output. In
this step, we aim to capture such small modifications by explicitly modeling
them as deleted and added operations. Our key insight is, as there is a
significant overlap between the source and target token sequences, learning
fine-grained edit operations can be beneficial. In particular, we use LevT, as
described in Section II-B, to explicitly model the edits as a sequence of
deleted and added tokens. In the case of Figure 2, this step explicitly
deletes weights. and adds token sequence begin+, resulting in the correct
patch.

In this work, we implemented our own Search and Edit Models on top of existing
generation models [14, 37, 17, 23]. The rest of this section elaborates each
part in detail.

###  III-B Input Processing

While pre-processing the inputs, following MODIT [37], we create a multi-modal
input capturing (i) exact patch location, (ii) patch context, and (iii)
developers’ intent or guidance in the form of natural text. Figure 3 provides
an example input. Following some recent code editing and program repair
techniques [38, 43, 37, 44], we assume that the developer knows the exact
patch location. We realize the localization with a tree-based parser GumTree
[45]. Patch context is the whole function body where the patch will be applied
(including both the context before and after the patch location). The third
modality (intent) is optional and approximated from the patch commit message.
We further augment each input with a token sequence retrieved from the search
step as discussed below. Each modality is separated by a special token <s>.

For code editing tasks, the input of each modality is a list of tokens. We
tokenize the input with the tokenizer which is compatible with the backbone
generation model.

###  III-C Search

Figure 3: Search Augmented Input Modalities of SarGaM

We maintain a database $P$ of previous patches, where each patch can be stored
as tuple ($v^{0}$,$v^{1}$). In this step, given the original code version as a
query, say $v^{0}_{q}$, SarGaM retrieves the potential edits from the database
that were applied before within a similar code context. In particular, SarGaM
computes edit distances between $v^{0}_{q}$ and all the instances of $v^{0}$
in the database and creates a ranked list based on the similarity scores.
SarGaM then retrieves $top\ k$ similar $v^{0}$s and fetches their
corresponding patches ($v^{1}$s). Each retrieved patch is finally augmented
with the original input, as shown in Figure 3.

Data:

1\. A query $v^{0}_{q}$ as an original code version to be patched,

2\. Patch database
$P=\\{(v^{0}_{1},v^{1}_{1}),..(v^{0}_{i},v^{1}_{i}),(v^{0}_{N},v^{1}_{N})\\}$,
stored with embedding of each $v^{0}_{i}$ : $\mathcal{E}(v^{0}_{i})$

3\. Number of patches to be retrieved $k$;

Result: Retrieved Patches

1 $retreivedP$ = [] ;

2 for  _p in P_ do

3 d = Distance($\mathcal{E}(v^{0}_{q})$, $\mathcal{E}(v^{0}_{p})$);

4 $retreivedP$.append( {patch:$v^{1}_{p}$, distance:d}) ;

5

6 end for

7Sort $retreivedP$ using distance ;

return $retreivedP[:k]$

Algorithm 1 Pseudo Code of Search

Algorithm 1 shows the pseudo-code for our technique. As inputs, the algorithm
takes an original code version that needs to be patched ($v^{0}_{q}$), a
database of previous patches $P$, and how many patches we want to retrieve
($top$ $k$). For each original version of a patch $v^{0}_{p}$ in the database,
we compute its edit distance from $v^{0}_{q}$. We compute the edit distance in
the embedded space to facilitate the computation. Thus, all the original code
versions in the patch database are stored in its embedded form
$\mathcal{E}(v^{0})$ and the query is also embedded. We use PLBART [14] to get
such embeddings. The edit distance is computed using cosine similarity–for any
two pieces of embedded code $x$ and $y$, we compute:

$d=1-\frac{\mathbf{x}\cdot\mathbf{y}}{\|\mathbf{x}\|\|\mathbf{y}\|}=1-\frac{\sum_{i=1}^{N}x_{i}y_{i}}{\sqrt{\sum_{i=1}^{N}x_{i}^{2}}\sqrt{\sum_{i=1}^{N}y_{i}^{2}}}$
(1)

For each candidate p in the database, the computed distance along with the
retrieved patch ($v^{1}_{p}$) is stored in a list (line 4). The final list is
further sorted in descending order by distance to the query (line 6), and the
algorithm returns the $top$ $k$ closest entries to the query (line 7).

Such similarity measurements simulate the real-life situation where the
developer looks for use cases on the internet and chooses the problem
statement most similar to their scenario.

###  III-D Generation Model

Here we use three state-of-the-art edit generation models: PLBART [14, 37],
CoditT5 [23], and NatGen [17]. The output of this step is a token sequence
corresponding to the generated patch. For PLBART and NatGen, the output
formats are identical to the expected patch format, and no more post-
processing is needed. However, CoditT5’s [23] is an edit generation model; its
output sequence is of the format: _Edit Operations_ ¡s¿ _fixed code_. Thus, we
further post-process them to create a sequence of tokens corresponding to the
generated patch.

###  III-E Modification Model

Figure 4: Example modification steps generated by Levenshtein Transformer
corresponding to the motivating example. The encoder takes patch location,
context, and optional developer’s intent as input and outputs hidden state
$H=\\{h_{1},h_{2},\cdots,h_{N}\\}$, where N refers to the length of the input
sequence. LevT decoder takes $H$ and patch location, and after some
Transformer decoder layers, outputs $(z_{1},z_{2},\cdots,z_{M})$. It is passed
to three classifiers (deletion, placeholder, insertion) to perform the edits.

Here, generated code, e.g. $v_{gen}$, from the previous step is further
modified. We describe two basic edit operations on $v_{gen}$:

  * •

delete token $d$ from $v_{gen}$.

  * •

insert token $i$ at location $l$ in $v_{gen}$.

Any other code change operation, e.g., replacement, move, etc., can be
expressed in terms of delete and insert [13, 12]. Multiple modifications can
further be expressed as a sequence of token deletion and insertion operations,
resulting in the final patched code. To capture such insertion-deletion
operations, we use LevT, as discussed in Section II-B. Figure 4 illustrates
this step w.r.t. our motivating example (see Figure 2).

Modeling Edits. Given a token sequence representing
$T=(t_{1},t_{2},...,t_{n})$, the two edit operations, deletion and insertion,
are consecutively applied to generate the final output. As discussed in
Section II-B, LevT decoder has three classification heads: Insertion,
Deletion, and Placeholder. We model the code edit operations using these three
classifiers, as follows:

Token Deletion. LevT reads the input sequence $T$, and for every token
$t_{i}\in T$, the deletion classifier makes the binary decision of 1 (delete
the token) or 0 (keep the token). The output of the deletion head is
$T^{\prime}$. Figure 4 shows that the deletion classifier identifies the
tokens weights and . for deletion (marked in red).

Token Insertion. On $T^{\prime}$, the insertion operation is realized in two
phases: predicting locations to insert the token and then predicting the
tokens to be inserted. First, among all the possible locations where a new
token can be inserted, _i.e.,_ $(t^{\prime}_{i},t^{\prime}_{i+1})\in
T^{\prime}$, the Placeholder head of LevT predicts how many placeholders can
be added. Next, the insertion head of LevT replaces each placeholder with a
token chosen from the vocabulary.

For instance, in Figure 4, the Placeholder Classifier predicts two placeholder
positions between tokens < and length, as marked by [PLH] [PLH] (_i.e.,_ i ¡
[PLH] [PLH] length). Next, the Insertion Classifier focuses only on the two
placeholders and predicts begin and + respectively. Finally, we get the
intended patch int i = begin , i < begin + length , i++ ;.

##  IV Experimental Design

###  IV-A Datasets

TABLE I: Studied Code Editing & Bug-fixing Datasets Dataset | #Train | #Eval | #Test
---|---|---|---
Bug2Fix small ($B2F_{s}$) | 46628 | 5828 | 5831
Bug2Fix medium ($B2F_{m}$) | 53324 | 6542 | 6538
Java 2006 | 2593572 | 324196 | -
Defects4J1.2 | - | - | 75
Defects4J2.0 | - | - | 82
QuixBugs | - | - | 40

Table I summarizes the dataset we use for our study.

#### Code Editing Data

The accuracy of the code editing task of SarGaM is evaluated by utilizing the
Bug2Fix dataset [46] similar to [37, 23] (including $B2F_{s}$ and $B2F_{m}$).
$B2F_{s}$ contains shorter methods with a maximum token length 50, and
$B2F_{m}$ contains longer methods with up to 100 token length.

#### Bug Fixing Data

The effectiveness of the pipeline is measured with Defects4j [47] and
QuixBugs[48]. The Generate and Edit parts of the pipeline are trained with
Java 2006 [43], which has over two million samples in the training set. After
training, we test our pipeline on (1) 75 single-line bugs in Defects4J1.2 and
(2) 85 single line bugs in Defects4J2.0 and (3) 40 bugs in QuixBugs.

###  IV-B Baselines

We fine-tune three large-scale pre-trained language generation models: PLBART
[14], CoditT5 [23] and NatGen [17] on each dataset and consider them as our
baselines. CoditT5 is an edit-generation model that generates edits in terms
of token addition, deletion, and replacement operations. In contrast, NatGen
and PLBART are code-generation models that generate a sequence of tokens.
Another edit generation model, MODIT [37] studied several information
modalities on top of PLBART. We use MODIT’s recommendation to select the input
modalities and report results on the different baselines. We compare SarGaM
with the following deep learning-based baselines for the bug-fixing task:
CocoNut [43], CURE [38], KNOD [35], and AlphaRepair [36].

###  IV-C Training

For training LevT, we followed [40] and trained on 4 GeForce RTX3090 Ti GPU
with 64,000 tokens batch size. We use the same dual-policy learning objective
[40] during training and stopped once the performance on the validation set
did not improve for 5 consecutive epochs.

On code editing task, we fine-tune three pre-trained generation models. With
respect to PLBART, we followed [37] and train with a learning rate of
$5e^{-5}$ and batch size of 16\. Following [23], we fine-tune CoditT5 and
NatGen with a learning rate of $5e^{-5}$ and batch size of 48. In the fine-
tuning stage, we adopt the same early stopping strategy that we use for
training LevT.

###  IV-D Evaluation Metric

When a synthesized patch is exactly identical to the expected patch, _i.e.,_
it is an ?exact match? of the expected patch, we declare the synthesized patch
to be correct. We use accuracy (exact match) to evaluate the results on both
code editing and program repair. For code editing tasks, we report $top1$ and
$top5$ accuracies. Given a retrieval augmented input, we let the code
generation model output up to top 5 patches; modify each of the generated
patches once and produce up to 5 final candidate patches.

In the case of our program repair tool, we generate and evaluate up to the top
1250 patches. We made this choice in consideration of other APR tools, which
often evaluate up to the top 5000 patches. We believe that reporting accuracy
at the top 1250 is a reasonable and fair choice, particularly because our APR
approach includes test cases to validate the generated patches.

##  V Results and Analysis

In this section, we present empirical results as answers to the following
research questions:

  1. RQ1.

How effective is SarGaM for code editing?

  2. RQ2.

What are the contributions of different design choices?

    1. 1.

Importance of input modalities.

    2. 2.

Effectiveness of a Levenshtein transformer over a vanilla transformer for
patch modification.

  3. RQ3.

How effective is SarGaM for automated program repair?

###  V-A RQ1. SarGaM for code editing

####  V-A1 Motivation

Here we investigate the core functionality of SarGaM, i.e., generating code
edits. We evaluate it on popular code editing benchmarks $B2F_{s}$ and
$B2F_{m}$.

####  V-A2 Experimental Setup

We compare SarGaM’s performance with three state-of-the-art pre-trained code
generation models that show effectiveness for code editing tasks: PLBART [14],
CoditT5 [23], and NatGen [17]. We fine-tune all three pre-trained models on
the same dataset ($B2F_{s}$ or $B2F_{m}$). While comparing with a code
generation model, we incorporate the same model in SarGaM’s pipeline. In that
way, it shows how much SarGaM can improve compared to the corresponding
generation-only setting.

In the search step, we search for similar edits from the training sets of
$B2F_{s}$ or $B2F_{m}$. The retrieved patch from the training sets of
$B2F_{s}$ or $B2F_{m}$ are added to the input. The generation and edit models
are fine-tuned on the search augmented input. For a given retrieval augmented
input, we take $top1$ and $top5$ outputs from the generation step and further
modify them to produce the final patches. The reported numbers in Table II
present the accuracy of the final patches.

TABLE II: Experiment results of SarGaM for code editing. Models in () are the off-the-shelf generative models used by SarGaM.  Tool | $B2F_{s}$ | $B2F_{m}$ | $B2F_{s}$ | $B2F_{m}$
---|---|---|---|---
Top1 | Top5
PLBART | 29.99 | 23.03 | 47.08 | 36.51
SarGaM (PLBART) | 35.77 | 27.58 | 52.43 | 37.81
NatGen | 36.55 | 28.53 | 52.39 | 42.99
SarGaM (NatGen) | 38.31 | 29.32 | 57.31 | 45.31
CoditT5 | 37.52 | 28.33 | 54.99 | 42.32
SarGaM (CoditT5) | 39.54 | 30.12 | 57.46 | 44.20

####  V-A3 Results

We find that SarGaM can always outperform its pure generation counterpart by a
considerable margin. SarGaM improves upon baseline PLBART, NatGen, and CoditT5
by 15.61%, 3.80% and 5.85% in terms of $top1$ exact match, respectively. When
we consider $top5$ accuracy, SarGaM improves upon three baseline models by
7.46%, 7.40% and 4.47%, respectively.

(a)

(b)

Figure 5: Example correct patches generated by SarGaM. Inputs are presented in
light brown boxes, and synthesised patches are presented in light green boxes.

Figure 5(a) shows the progress each step makes towards the synthesis of the
correct patch. Given the previous code as input, we retrieve a patch that is
very similar to the ground truth from the code base. The Levenshtein distance
between the retrieved patch and the ground truth is 2 while that between
previous code and ground truth is 14. The generation model (NatGen) utilizes
the retrieved patch and generates a patch based on the code context. This step
brings the generated patch one step closer to the correct patch, which is only
one step away from our goal. Finally, the modification model completes the
last step by deleting isSoftStopCondition and inserting true.

Figure 5(b) shows another example which can prove the robustness of SarGaM.
The presence of ”by using infinite reconnection loop” in the commit message
suggests that stop() should be removed from the previous code. Although the
retrieved patch is not even close to the ground truth, the generation model
(CoditT5 in this case) still recognizes part of the developer’s intent and
removes stop(). Based on the output of generation model, the editing model
further deletes another statement m_loadFailure = true; and finally returns
reportNode (t.getMessage()); , which proves to be the correct patch.

Figure 6: Ablation Study of the steps of SarGaM on $B2F_{s}$

Figure 6 further shows the effectiveness of each step (search, generate,
modify): for all the three off-the-shelf code generation models, introducing
search can improve the patch generation, and modifying the generated patch can
further improve the performance. On $B2F_{s}$ retrieved edits can improve the
$top1$ exact match of PLBART by $3.97\%$, and the modifying step further
improves it with another $1.81\%$. Such an improvement can also be found on
$B2F_{m}$.

Result 1: SarGaM can generate better patches than generation-only or edit-only
models. On average SarGaM can improve upon three baseline models by 8.42% and
6.44%, in terms of $top1$ accuracy and $top5$ accuracy, respectively.

###  V-B RQ2. Analyzing Design Choices

####  V-B1 Motivation

The success of the search and modification steps depends on different design
choices. In particular, we investigate:

  1. 1.

During search, which input modalities (edit location, context, and user
intent) and their combinations matter for a successful patch generation.

  2. 2.

How LevT outperforms a vanilla Transformer-based model for patch modification.

### RQ2.1: Impact of Input Modalities on Search

####  V-B2 Experimental Setup.

Here, the search query is formed with different combinations of three types of
inputs: patch location, patch context, and developer intent. Each modality is
matched with a similar modality during retrieval. We report the results both
for search+generate and search+generate+modification as shown in Table III.
Note that we do not compare the impact of different modalities for the
generation step, as Chakraborty _et al._. [37] on the same dataset has
conclusively shown that all three modalities do matter.

TABLE III: Impact of Different Input Modalities in Search Query

Patch |  | Commit | Search+Generate | Search+Generate+Modify
---|---|---|---|---
Location | Context | Message | $B2F_{s}$ | $B2F_{m}$ | $B2F_{s}$ | $B2F_{m}$
- | - | - | 29.99 | 23.02 | 31.03 | 24.33
- | - |  | 31.97 | 23.81 | 32.02 | 24.26
- |  | - | 31.92 | 24.49 | 32.43 | 25.92
- |  |  | 33.96 | 24.43 | 35.60 | 26.49
| - | - | 31.50 | 24.72 | 32.77 | 27.58
| - |  | 32.82 | 25.27 | 34.01 | 25.67
|  | - | 31.85 | 25.01 | 33.29 | 26.11
|  |  | 33.63 | 24.33 | 35.77 | 26.39

####  V-B3 Results

Table III shows the results of SarGaM on $B2F_{s}$ and $B2F_{m}$ with
different combinations of retrieved patches as an additional modality. The
results show that the retrieved patches improve the performance of the
generation model (PLBART) across all combinations. On $B2F_{s}$, the best
result is achieved when we use both the patches retrieved with context and
those retrieved with commit messages. In this case, we improve the performance
of PLBART by 13.24%. However, on $B2F_{m}$, PLBART, achieves its best
performance when patches retrieved with patch location and patches retrieved
with commit message are passed to the input and it finally improves baseline
PLBART by 9.77%.

The improvement that the retrieved patches bring to the generation model still
holds after further modification. On $B2F_{s}$, using patches retrieved with
all the three types of queries achieves the highest accuracy, which is
actually the second best combination in the ”Search+Generation” setting. On
$B2F_{m}$, patch location & commit message is still the best combination.

### RQ2.2. LevT vs Vanilla Transformer for patch modification

####  V-B4 Experimental Setup

In this section, we follow the experimental setup in Section V-A and use LevT
and the vanilla Transformer to modify the output of code-generation models,
which have been augmented with search results. For fairness, both LevT and the
vanilla Transformer are trained on the same dataset ($B2F_{s}$ and $B2F_{m}$).

TABLE IV: Performance of LevT and vanilla Transformer (vT) for modification

Dataset |  Gen. Models | Top1 | Top5
---|---|---|---
| Before
---
Edit
| vT
---
| LevT
---
| Before
---
Edit
| vT
---
| LevT
---
small | PLBART | 33.63 | 34.85 | 35.78 | 51.15 | 51.91 | 52.43
NatGen | 38.29 | 39.23 | 39.44 | 56.58 | 57.13 | 57.31
CoditT5 | 38.38 | 39.04 | 39.55 | 57.01 | 57.37 | 57.47
medium | PLBART | 25.27 | 26.32 | 27.82 | 37.57 | 37.98 | 38.82
NatGen | 27.73 | 28.47 | 29.32 | 44.23 | 44.41 | 45.31
CoditT5 | 29.29 | 30.03 | 30.12 | 43.53 | 43.68 | 44.20

(a) PLBART $B2F_{s}$

(b) NatGen $B2F_{s}$

(c) CoditT5 $B2F_{s}$

(d) PLBART $B2F_{m}$

(e) NatGen $B2F_{m}$

(f) CoditT5 $B2F_{m}$

Figure 7: Venn diagrams of the numbers of correct modifications made by LevT
and Transformer

####  V-B5 Results

In Table IV we report the performance of using vanilla Transformer and LevT
for editing. Across all the different settings, LevT always achieves a higher
exact match (accuracy) of the generated edit. In addition, we present the
exact numbers of overlapped and unique correct edits produced by Transformer
and LevT in Figure 7. On PLBART $B2F_{m}$ and PLBART $B2F_{s}$, LevT
complements Transformer by producing 110 and 59 more correct patches,
respectively. Similarly, by modifying NatGen’s output, LevT can produce 29 and
67 more unique patches over vanilla Transformer for $B2F_{s}$ and $B2F_{m}$
respectively. Even when we consider CoditT5, which is an edit generation
model, LevT produces 37 and 3 more unique patches over a vanilla Transformer
for $B2F_{s}$ and $B2F_{m}$ respectively. These results show LevT is a better
design choice for patch modification over a vanilla Transformer.

Result 2 Experiments reveal that the combinations of edit location, context,
and developer’s intent during patch retrieval can improve PLBART by up to
13.24%. Meanwhile, LevT-based patch modification model outperforms the vanilla
Transformer by modeling fine-grained edit operations explicitly.

###  V-C RQ3. SarGaM for Bug Fixing

TABLE V: Experiment Results of SarGaM for Bug Fixing.

Tool | Defect4j1.2 | Defects4j2.0 | QuixBugs
---|---|---|---
CocoNut | - | - | 13
CURE | - | - | 26
KNOD | 48 | 34 | 25
AlphaRepair | 45 | 36 | 28
Codex | 33 | 38 | 31
SarGaM | 40 | 42 | 34
(Search+Codex+Modify) |  |  |

####  V-C1 Motivation

We want to check SarGaM’s applicability for program repair, which is a special
class of code editing task. For bug fixing, the plausibility of the generated
edits can be estimated by the passing and failing of test cases.

####  V-C2 Experimental Setup

Following Jiang el al. [49]’s findings that LLMs tend to outperform all the
other DL-based repair-only models, here we choose OpenAI’s Codex [19] (at
zero-shot setting), one of the largest code generation models at the time of
writing the paper. In particular, for bug fixing, we use Codex as our off-the-
shelf code generation model and build the rest of the steps on top of it. Our
motivation is to investigate, whether the search and modification steps can
provide any additional benefits when using Codex.

To provide input to Codex, we design a prompt that combines code and natural
language. Our prompt is inspired by several previous works [50, 51, 52]. The
prompt consists of the following components (see Figure 8):

  * •

Describing Task. The comment at the beginning of the prompt (?fix the bug in
the following method?) describes the task to be carried out by Codex.

  * •

Specifying Bug Location. The buggy code snippet that needs to be repaired is
marked with a comment ?buggy line is here?.

  * •

Retrieved Patch. The retrieved patch is augmented with comment ?A possible
patch for buggy line?.

  * •

Context. The context before the buggy line is further highlighted with a
comment: ?change the buggy line to fix the bug:?.

To obtain the patch, we take the first line generated by Codex.

Figure 8: An example prompt (Codec-17) including the buggy code (green lines),
buggy line (red line), retrieved patch (yellow line), and the context before
the buggy line (pink lines).

Here, we perform the search step in a larger training set: Java 2006. In the
search step, we retrieve up to 25 similar patches, and in the generation step,
we generate top50 possible patches. Hence at the inference stage, we obtain up
to ($50*25=1250$) candidate patches for every single bug. This number of
candidate patches is still relatively small compared to the settings in some
previous works [38, 28, 36], which can generate up to 5,000 patches. Here, we
use the Defects4J test suite to validate patches after each step. Following
previous work [43], we call patches synthesized by SarGaM ?candidate patches?.
After validating these candidate patches with the corresponding test suite, we
report only the correct patches that are exactly the same as the patches
provided by the developers.

####  V-C3 Results

Table V shows the results of SarGaM and other APR baselines on three
benchmarks under the condition of perfect bug localization. SarGaM can fix
more bugs than Codex in all the settings, showing that even if a really large
high-capacity code generation model is used, search and modification steps
still add significant value on top of it.

Overall, SarGaM fixes 42 single line bugs, outperforming all the other
baselines on Defects4J2.0, and produces 6 and 8 more correct patches than the
latest APR tools AlphaRepair and KNOD, respectively. On Defects4J1.2, SarGaM
outperforms most of the deep learning baselines, but it is worse than KNOD and
AlphaRepair. Note that we report accuracies based on the top 1250 patches,
whereas KNOD and AlphaRepair use 5000 patches. We believe that given similar
resources, we will perform comparably in this setting. Table V also presents
the effectiveness of the proposed method on QuixBugs, where it outperforms all
the other baselines.

(a) Defects4j1.2

(b) Defects4j2.0

Figure 9: Unique fixes of SarGaM, AlphaRepair and KNOD.

Figure 9 presents the relationship of bugs that can be fixed by SarGaM,
AlphaRepair, and KNOD. Figure 9(a) indicates that SarGaM complements
AlphaRepair and KNOD by fixing 10 and 9 more bugs respectively on
Defects4J1.2. Similarly, on Defects4j 2.0 SarGaM can also improve AlphaRepair
and KNOD by fixing 17 bugs and 20 additional bugs. LABEL:fig:unique_bugs shows
three examples of bugs only fixed by SarGaM. Math-96 (Figure
LABEL:fig:math-96) is a hard bug because all the Double.doubleToRawLongBits
need to be deleted from the original sequence. Csv-12(LABEL:fig:csv-12) is
also not an easy one because a new api .withAllowMissingColumnNames(true) is
called in the correct fix, which does not appear in the context. However,
SarGaM is still able to fix both examples with the help of patch search and
patch editing. Another example is JSoup-26(Figure LABEL:fig:jsoup-26), which
indicates that SarGaM is able to insert a new line into the buggy code.

Result 3: SarGaM is capable of fixing bugs — on a real-world Java bug dataset,
SarGaM can synthesize 6 and 8 more bugs than most recent AlphaRepair and KNOD.

##  VI Related Work

Code Repair Models.  Seq2Seq models have been studied by many researchers to
repair code. Tufano _et al._ [53] introduced the encoder-decoder architecture
to fix bugs. SequenceR [28] further combined a copy mechanism with the
$seq2seq$ model to overcome the unlimited vocabulary problem. CocoNut [43]
used ensemble learning for this purpose, while some other works use
tree/graph-based models [11, 35, 54]. SimFix [55] claimed that both existing
patches and similar code could be helpful in APR. Their findings motivated us
to explore if patches retrieved from the existing code base can provide more
information to $seq2seq$ models and further improve their performance.

LLMs like CodeBERT [56], PLBART [14, 37], CodeT5 [16], and NatGen [17] have
shown very promising results on APR. Fu _et al._ [57] proposed VulRepair, a
T5-based vulnerability repair approach, to solve the limitations of previous
work: VRepair [58]. A new trend in recent research works is zero-shot use of
LLMs for program repair, which means that no extra training or fine-tuning is
involved. Xia _et al._ [36] directly leverage pre-trained CodeBERT to build a
cloze-style APR tool. Jiang _et al._ [49] systematically evaluated 10 LLMs for
APR with and without fine-tuning. [50] and [51] designed prompts for Codex to
convert code repair into code generation.

Our proposed approach complements this line of work as we show the potential
for taking any off-the-shelf APR tools and composing them with retrieval and
modification steps, improving the overall patch generation performance.

Code Editing Models Recent studies explore if DL models can learn explicit
edit operations. Ding _et al._ [26] confirmed this claim. Chen _et al._ [21]
proposed to pair a graph encoder with a Transformer decoder to generate Tocopo
sequence [20], which is used to represent a code edit. Similarly, Hephaestus
[22] used an LSTM $seq2seq$ model to learn edit operations via the
introduction of Levenshtein edit operations and their condensed forms: basic,
strict, and loose compound operations. Zhang _et al._ [23] designed a pre-
trained model CoditT5 [23] for editing tasks. Unlike these previous code
editing models, we do not output an edit sequence directly; rather, our
approach slowly and carefully guides the tool towards generating the intended
edit in multiple steps.

Many previous works [20, 21, 22, 23] designed special outputs to represent
edit operations. For example, in the inference stage CoditT5 [23] first
generates an edit plan which explicitly edit operations, then it auto-
regressively generated the edited target sequence. In their open source
implementation, since the output is composed of two parts, extra post-
processing (decoding) is needed. However, LevT does not focus on output design
and directly applies explicit edit operations within the decoder.

##  VII Threats To Validity

External Validity. Our evaluation of edit generation is based on two datasets:
$B2F_{s}$ and $B2F_{m}$. These datasets focus on small to medium-sized edits
and, therefore, may not capture diverse edit characteristics. Additionally,
the commit messages that we use as edit intents may contain noise. However,
these datasets are based on real developers’ commits and, thus, provide a
valuable reflection of actual development scenarios. To minimize this issue,
we further assess the performance of SarGaM on fixing bugs from three other
datasets widely studied in the APR literature. This additional evaluation
ensures that the results are robust and generalize well to diverse types of
edit generation scenarios.

Construct Validity. SarGaM requires precise edit location for input. While
developers’ cursors can simulate the edit location during edit generation,
determining a bug’s exact location can be more challenging. To address this
issue, we delegate bug-finding to other tools and assume that once the buggy
line is identified, SarGaM can be used to generate a fix for the bug. By doing
so, we focus on the strengths of SarGaM in generating high-quality patches and
avoid potential issues that may arise from inaccurate bug identification.

Internal Validity. It is worth noting that our reported results may be
influenced by hyperparameter choices (_e.g.,_ learning rate, batch size,
etc.). To address this concern, we plan to release our tool as an open-source
project. By doing so, other researchers and practitioners could evaluate our
approach in a wider range of settings, which will help to validate our
findings further and minimize this potential threat.

##  VIII Conclusion

We propose SarGaM, a novel approach to improve pre-trained code generation
models by incorporating patch search, generation, and modification. Our goal
is to mimic the behavior of a developer while editing, who first searches for
a related patch, sketches out a rough draft of a patch, and then modifies it
to produce a final patch for integration with the rest of the code. To this
end, we propose a novel patch modification model based on Levenshtein
Transformer, which generates fine-grained edit operations to achieve patch
modification. We evaluate our approach on two tasks: code editing and
automated program repair. Our results demonstrate that SarGaM is highly
effective for both tasks and outperforms state-of-the-art methods in the
majority of settings.

##  IX Acknowledgements

We would like to thank Matthew H. Retchin for his extensive feedback on this
paper.

## References

  * [1] B. Ray, M. Nagappan, C. Bird, N. Nagappan, and T. Zimmermann, “The uniqueness of changes: Characteristics and applications,” ser. MSR ’15. ACM, 2015.
  * [2] H. A. Nguyen, A. T. Nguyen, T. T. Nguyen, T. N. Nguyen, and H. Rajan, “A study of repetitiveness of code changes in software evolution,” in _Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering_. IEEE Press, 2013, pp. 180–190.
  * [3] M. Gharehyazie, B. Ray, and V. Filkov, “Some from here, some from there: Cross-project code reuse in github,” in _2017 IEEE/ACM 14th International Conference on Mining Software Repositories (MSR)_. IEEE, 2017, pp. 291–301.
  * [4] M. M. Rahman, J. Barson, S. Paul, J. Kayani, F. A. Lois, S. F. Quezada, C. Parnin, K. T. Stolee, and B. Ray, “Evaluating how developers use general-purpose web-search for code retrieval,” in _Proceedings of the 15th International Conference on Mining Software Repositories_ , 2018, pp. 465–475.
  * [5] T. Zhang, G. Upadhyaya, A. Reinhardt, H. Rajan, and M. Kim, “Are code examples on an online q&a forum reliable? a study of api misuse on stack overflow,” in _Proceedings of the 40th international conference on software engineering_ , 2018, pp. 886–896.
  * [6] B. Ray, M. Kim, S. Person, and N. Rungta, “Detecting and characterizing semantic inconsistencies in ported code,” in _Automated Software Engineering (ASE), 2013 IEEE/ACM 28th International Conference on_. IEEE, 2013, pp. 367–377.
  * [7] S. Barke, M. B. James, and N. Polikarpova, “Grounded copilot: How programmers interact with code-generating models,” _arXiv preprint arXiv:2206.15000_ , 2022.
  * [8] M. Boshernitsan, S. L. Graham, and M. A. Hearst, “Aligning development tools with the way programmers think about code changes,” in _Proceedings of the SIGCHI conference on Human factors in computing systems_. ACM, 2007, pp. 567–576.
  * [9] R. Robbes and M. Lanza, “Example-based program transformation,” in _International Conference on Model Driven Engineering Languages and Systems_. Springer, 2008, pp. 174–188.
  * [10] M. Tufano, J. Pantiuchina, C. Watson, G. Bavota, and D. Poshyvanyk, “On learning meaningful code changes via neural machine translation,” _arXiv preprint arXiv:1901.09102_ , 2019.
  * [11] S. Chakraborty, Y. Ding, M. Allamanis, and B. Ray, “Codit: Code editing with tree-based neural models,” _IEEE Transactions on Software Engineering_ , vol. 1, pp. 1–1, 2020.
  * [12] N. Meng, M. Kim, and K. S. McKinley, “Lase: Locating and applying systematic edits by learning from examples,” _In Proceedings of 35th International Conference on Software Engineering (ICSE)_ , pp. 502–511, 2013.
  * [13] ——, “Systematic editing: generating program transformations from an example,” _ACM SIGPLAN Notices_ , vol. 46, no. 6, pp. 329–342, 2011.
  * [14] W. U. Ahmad, S. Chakraborty, B. Ray, and K.-W. Chang, “Unified pre-training for program understanding and generation,” in _2021 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL)_ , 2021.
  * [15] S. Lu, D. Guo, S. Ren, J. Huang, A. Svyatkovskiy, A. Blanco, C. Clement, D. Drain, D. Jiang, D. Tang _et al._ , “Codexglue: A machine learning benchmark dataset for code understanding and generation,” _arXiv preprint arXiv:2102.04664_ , 2021. [Online]. Available: https://arxiv.org/abs/2102.04664
  * [16] Y. Wang, W. Wang, S. Joty, and S. C. Hoi, “Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation,” _arXiv preprint arXiv:2109.00859_ , 2021.
  * [17] S. Chakraborty, T. Ahmed, Y. Ding, P. T. Devanbu, and B. Ray, “Natgen: generative pre-training by “naturalizing” source code,” in _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2022, pp. 18–30.
  * [18] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language models are few-shot learners,” 2020.
  * [19] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba, “Evaluating large language models trained on code,” 2021.
  * [20] D. Tarlow, S. Moitra, A. Rice, Z. Chen, P.-A. Manzagol, C. Sutton, and E. Aftandilian, “Learning to fix build errors with graph2diff neural networks,” in _Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops_ , 2020, pp. 19–20.
  * [21] Z. Chen, V. J. Hellendoorn, P. Lamblin, P. Maniatis, P.-A. Manzagol, D. Tarlow, and S. Moitra, “Plur: A unifying, graph-based view of program learning, understanding, and repair,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 23 089–23 101, 2021.
  * [22] A. Connor, A. Harris, N. Cooper, and D. Poshyvanyk, “Can we automatically fix bugs by learning edit operations?” 2022.
  * [23] J. Zhang, S. Panthaplackel, P. Nie, J. J. Li, and M. Gligoric, “Coditt5: Pretraining for source code and natural language editing,” in _37th IEEE/ACM International Conference on Automated Software Engineering_ , 2022, pp. 1–12.
  * [24] N. Jain, S. Vaidyanath, A. Iyer, N. Natarajan, S. Parthasarathy, S. Rajamani, and R. Sharma, “Jigsaw: Large language models meet program synthesis,” 2022\.
  * [25] M. Pradel and S. Chandra, “Neural software analysis,” _Communications of the ACM_ , vol. 65, no. 1, pp. 86–96, 2021.
  * [26] Y. Ding, B. Ray, P. Devanbu, and V. J. Hellendoorn, “Patching as translation: the data and the metaphor,” in _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2020, pp. 275–286.
  * [27] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [28] Z. Chen, S. J. Kommrusch, M. Tufano, L.-N. Pouchet, D. Poshyvanyk, and M. Monperrus, “Sequencer: Sequence-to-sequence learning for end-to-end program repair,” _IEEE Transactions on Software Engineering_ , 2019.
  * [29] D. Nam, B. Ray, S. Kim, X. Qu, and S. Chandra, “Predictive synthesis of api-centric code,” in _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_ , 2022, pp. 40–49.
  * [30] P. Yin, G. Neubig, M. Allamanis, M. Brockschmidt, and A. L. Gaunt, “Learning to represent edits,” _arXiv preprint arXiv:1810.13337_ , 2018.
  * [31] J. Zhao, F. Huang, J. Lv, Y. Duan, Z. Qin, G. Li, and G. Tian, “Do rnn and lstm have long memory?” in _International Conference on Machine Learning_. PMLR, 2020, pp. 11 365–11 375.
  * [32] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems 30_ , 2017, pp. 5998–6008.
  * [33] G. Kobayashi, T. Kuribayashi, S. Yokoi, and K. Inui, “Attention is not only a weight: Analyzing transformers with vector norms,” _arXiv preprint arXiv:2004.10102_ , 2020.
  * [34] S. Abnar and W. Zuidema, “Quantifying attention flow in transformers,” _arXiv preprint arXiv:2005.00928_ , 2020.
  * [35] N. Jiang, T. Lutellier, Y. Lou, L. Tan, D. Goldwasser, and X. Zhang, “Knod: Domain knowledge distilled tree decoder for automated program repair,” _arXiv preprint arXiv:2302.01857_ , 2023.
  * [36] C. S. Xia and L. Zhang, “Less training, more repairing please: revisiting automated program repair via zero-shot learning,” in _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2022, pp. 959–971.
  * [37] S. Chakraborty and B. Ray, “On multi-modal learning of editing source code,” in _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2021, pp. 443–455.
  * [38] N. Jiang, T. Lutellier, and L. Tan, “Cure: Code-aware neural machine translation for automatic program repair,” _arXiv preprint arXiv:2103.00073_ , 2021.
  * [39] F. F. Xu, U. Alon, G. Neubig, and V. J. Hellendoorn, “A systematic evaluation of large language models of code,” _arXiv preprint arXiv:2202.13169_ , 2022\.
  * [40] J. Gu, C. Wang, and J. Zhao, “Levenshtein transformer,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [41] V. I. Levenshtein _et al._ , “Binary codes capable of correcting deletions, insertions, and reversals,” in _Soviet physics doklady_ , vol. 10, no. 8. Soviet Union, 1966, pp. 707–710.
  * [42] N. Jain, S. Vaidyanath, A. Iyer, N. Natarajan, S. Parthasarathy, S. Rajamani, and R. Sharma, “Jigsaw: Large language models meet program synthesis,” in _Proceedings of the 44th International Conference on Software Engineering_ , 2022, pp. 1219–1231.
  * [43] T. Lutellier, H. V. Pham, L. Pang, Y. Li, M. Wei, and L. Tan, “Coconut: combining context-aware neural translation models using ensemble for program repair,” in _Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2020, pp. 101–114.
  * [44] Q. Zhu, Z. Sun, Y.-a. Xiao, W. Zhang, K. Yuan, Y. Xiong, and L. Zhang, “A syntax-guided edit decoder for neural program repair,” in _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2021, pp. 341–353.
  * [45] J.-R. Falleri, F. Morandat, X. Blanc, M. Martinez, and M. Monperrus, “Fine-grained and accurate source code differencing,” in _Proceedings of the 29th ACM/IEEE international conference on Automated software engineering_. ACM, 2014, pp. 313–324.
  * [46] M. Tufano, C. Watson, G. Bavota, M. Di Penta, M. White, and D. Poshyvanyk, “An empirical investigation into learning bug-fixing patches in the wild via neural machine translation,” in _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_ , 2018, pp. 832–837.
  * [47] R. Just, D. Jalali, and M. D. Ernst, “Defects4J: A database of existing faults to enable controlled testing studies for java programs,” in _Proceedings of the 2014 International Symposium on Software Testing and Analysis_. ACM, 2014, pp. 437–440.
  * [48] D. Lin, J. Koppel, A. Chen, and A. Solar-Lezama, “Quixbugs: A multi-lingual program repair benchmark set based on the quixey challenge,” in _Proceedings Companion of the 2017 ACM SIGPLAN international conference on systems, programming, languages, and applications: software for humanity_ , 2017, pp. 55–56.
  * [49] N. Jiang, K. Liu, T. Lutellier, and L. Tan, “Impact of code language models on automated program repair,” _ICSE_ , 2023.
  * [50] J. A. Prenner and R. Robbes, “Automatic program repair with openai’s codex: Evaluating quixbugs,” _arXiv preprint arXiv:2111.03922_ , 2021.
  * [51] H. Joshi, J. Cambronero, S. Gulwani, V. Le, I. Radicek, and G. Verbruggen, “Repair is nearly generation: Multilingual program repair with llms,” _arXiv preprint arXiv:2208.11640_ , 2022.
  * [52] Z. Fan, X. Gao, A. Roychoudhury, and S. H. Tan, “Improving automatically generated code from codex via automated program repair,” _arXiv preprint arXiv:2205.10583_ , 2022.
  * [53] M. Tufano, C. Watson, G. Bavota, M. D. Penta, M. White, and D. Poshyvanyk, “An empirical study on learning bug-fixing patches in the wild via neural machine translation,” _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 28, no. 4, pp. 1–29, 2019.
  * [54] E. Dinella, H. Dai, Z. Li, M. Naik, L. Song, and K. Wang, “Hoppity: Learning graph transformations to detect and fix bugs in programs,” in _International Conference on Learning Representations_ , 2019.
  * [55] J. Jiang, Y. Xiong, H. Zhang, Q. Gao, and X. Chen, “Shaping program repair space with existing patches and similar code,” in _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_. ACM, 2018, pp. 298–309.
  * [56] Z. Feng, D. Guo, D. Tang, N. Duan, X. Feng, M. Gong, L. Shou, B. Qin, T. Liu, D. Jiang, and M. Zhou, “CodeBERT: A pre-trained model for programming and natural languages,” in _Findings of the Association for Computational Linguistics: EMNLP 2020_ , Nov. 2020, pp. 1536–1547.
  * [57] M. Fu, C. Tantithamthavorn, T. Le, V. Nguyen, and D. Phung, “Vulrepair: a t5-based automated software vulnerability repair,” in _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2022, pp. 935–947.
  * [58] Z. Chen, S. Kommrusch, and M. Monperrus, “Neural transfer learning for repairing security vulnerabilities in c code,” _arXiv preprint arXiv:2104.08308_ , 2021.