Revisiting Unnaturalness for Automated Program Repair in the Era of Large Language Models
Aidan Z. H. Yang Sophia Kolak Vincent J. Hellendoorn Ruben Martins Claire Le Goues






Revisiting Unnaturalness for Automated Program Repair in the Era of Large Language Models
    
Aidan Z.H. Yang 1, Sophia Kolak 2, Vincent J. Hellendoorn 3, Ruben Martins 4, Claire Le Goues 5
Carnegie Mellon University 
 Pittsburgh United States

Email: 1aidan@cmu.edu, 2sdkolak@andrew.cmu.edu, 3vhellendoorn@cmu.edu, 4rubenm@cs.cmu.edu, 5clegoues@cs.cmu.edu
    Received xx; accepted xx
===========================================================================================================================================================================================================================================================================




  Language models have improved by orders of magnitude with the recent emergence
of Transformer-based Large Language Models (LLMs). LLMs have demonstrated their
ability to generate “natural” code that is highly similar to code written by
professional developers. One intermediate value an LLM can emit is entropy,
which measures the “naturalness” of a token of code. We hypothesize that
entropy can be used to improve the performance of Automated Program Repair (APR)
tasks. While much progress has been made in Automated Program Repair (APR),
fault localization techniques suffer from a lack of diversity in ranking scores,
patch generation tools tend to be inefficient as all tests need to run before
determining if a patch is likely to be correct, and patch ranking often suffers
from the test-suite over-fitting problem. However, using an LLM directly for APR
introduces concerns for training data leakage. In this work, we introduce a
novel way of using the entropy of LLMs in combination with prior APR tools to
improve all stages of APR. By using only the prefix and suffix context of a line
or block of code to describe “naturalness”, we can use LLMs to localize faults
and rank patches all while eliminating the dependency for test-suites. We show
that entropy is highly complementary with prior fault localization tools. Our
proposed re-ranking method achieves a 50% Top-5 score improvement over SBFL. We
propose a patch-naturalness measurement, entropy-delta, to improve the
efficiency of template-based repair techniques by ranking plausible patches
before undergoing testing. When using entropy-delta for patch ranking and
classification, our proposed method can rank correct patches more effectively
than state-of-the-art machine learning tools with an 49% improvement in Top-1.
Our work suggests that LLMs can be an effective addition to compliment prior APR
tasks while minimizing both the test-suite overfitting problem and the LLM data
leakage problem.










§ INTRODUCTION



The problem of software quality has motivated the development of a variety of
techniques for Automatic Program Repair (APR) <cit.>. At a high level, dynamic APR approaches
use test cases to define a defect to be repaired and functionality to retain,
and to localize the defect to a smaller set of program lines.  
APR techniques generate candidate patches in a variety of ways, such as by
heuristically instantiating pre-defined repair template <cit.>, or by customizing symbolic techniques to synthesize new
code <cit.>.  

Meanwhile, the recent advances in machine learning and AI, including
but by no means limited to advances in Transformer <cit.>
based language models, have produced orders of magnitude performance improvements over
previous ML techniques for code generation <cit.>. ML therefore
affords promising opportunities for program repair <cit.> and fault localization <cit.>.

The applicability of language models to the repair process makes sense:
these models are trained on large volumes of code in which defects are relatively
rare. Since their training objective encourages next-token prediction,
well-trained language models tend to simultaneously perceive faulty code as unlikely
(or “unnatural”) and to produce code that is correct, as correct code is more
“natural” <cit.>. The naturalness of code and unnaturalness of buggy 
code is now a well-established phenomenon <cit.>.
However, the bulk of prior research on this topic relied on relatively simple n-gram language
models <cit.>. Compared to present-day LLMs, these models provided a
very poor estimator of code predictability. The “unnaturalness” of
buggy lines was therefore mainly useful as an explanatory metric, but showed limited
utility for precisely localizing defects, let alone repairing programs.
The recent advancement of much larger and more sophisticated LLMs have decreased model
perplexities by multiple orders of magnitude.  
This makes them a much more accurate adjunct both for estimating naturalness and
for fault localization or correct patch identification <cit.>.

In this paper, we revisit the idea of (un)naturalness for program repair. The
fundamental idea behind using an LM alone — even a hypothetically optimal one
— for repair treats predictability as ultimately equivalent to correctness.
This assumption is specious: LLMs adopt preferences based on a corpus
with respect to training loss that rewards imitation. Beyond the fact that LLMs
necessarily train on buggy code, LLMs generate and score text one token at the
time. Given that, they may well prefer a subtly incorrect implementation spread
across several readable lines over a correct but difficult-to-understand one-line
solution, as the per-token surprisal of the former may be strictly lower than the
latter. Judgement of code correctness requires substantially more context than an
LLM has access to including, but not limited to, test cases test behavior, and
developer intent. Although some of this information could be provided as context,
it will lie outside the training distribution.

This implies that LLMs can only go so far on their own in reasoning about and
fixing buggy code. It moreover motivates the use of traditional tools, which
compress such information, as a complement to LLMs in repair, which has indeed
shown promising recent results for the patch generation stage in
particular <cit.> (acknowledging the risk of training data
leakage in any such experiment <cit.>). 



We go beyond prior work by interrogating the role of entropy as a complement to
traditional repair at every stage:



Fault localization (FL). End-to-end dynamic APR relies on fault
localization to narrow a bug to a smaller set of
source locations. Improving fault localization accuracy is key to improving 
repair efficiency <cit.>. 

Although FL accuracy is improving, both commonly-used <cit.>
and state-of-the-art ML-based techniques still suffer from the tendency to
assign the same FL score to large amounts of code.  
For example, we find that
Ochiai SBFL <cit.> assigns the same suspiciousness score to 1137
lines of code in the dataset (an average of 2.9 ties per bug), and
TransferFL <cit.> assigns the same suspiciousness score to 380 lines
of code in the same dataset (an average of 0.96 ties per bug). 

We show that by incorporating entropy into fault localization, the variance of
suspicious scores increase by 87% for Ochiai SBFL, and overall accuracy
increases as well (e.g., the Top-5 score improves from 94 to 145).


 
Plausible patch generation. APR approaches
typically generate multiple potential code changes in search of 
plausible patches that cause the program to pass all tests.
Executing tests (and to some extent, compiling programs to be tested) dominates
repair time: the template-based approach  <cit.> spends about 2% of
its total time creating patch templates, 6% generating patches from templates,
and 92% running tests on generated patches. Regardless of the patch generation method (e.g.,
symbolic techniques <cit.>, template instantiation <cit.>, or
machine learning models <cit.>) repair efficiency is best
approximated in terms of the number of patches that must be evaluated to find a
(good) repair <cit.>.

We show that entropy, when used to order candidate patches for evaluation, can
improve the efficiency of generic template-based repair by 24
tested patches per bug, on average.


 
Patch correctness assessment.
Plausible patches are not always correct, in that they can fail to generalize to
the desired behavior beyond what is tested in the provided test 
suite <cit.>.  Some recent work aims to address this in the form of a 
post-processing step that identifies (and filters) plausible-but-incorrect
patches, typically by combining program analysis and machine
learning <cit.>.  However, techniques to date
are typically trained on the same test suites used for patch generation,
imposing a project-specific training burden (and an expensive one, when dynamic
signals are required), and posing a significant risk of overfitting <cit.>.  

We show that entropy can rank correct patches 49% more effectively (in Top-1) than state-of-the-art patch ranker Shibboleth <cit.>, without using any project-specific training data.









In summary, we make the following contributions.

	
  * End-to-end entropy APR. We propose a technique that uses a combination
	of an LLM's inherent ability to detect “naturalness” (i.e., entropy) and
	an LLM's generation ability to predict faulty lines, rank untested patches,
	and classify tested but potentially incorrect patches.
	
	
	
	
	
	
	
  * Entropy-delta for efficient template-based patch generation. 
	We introduce entropy-delta as a
    patch-naturalness measure that can rank patches before running tests. We show
    that entropy-delta can be used to immediately filter out test-failing
    patches, and on average reduce running tests for 24 patches for each bug in
    our dataset. We combine entropy-delta patch ranking with a prior
    template-based program repair technique,  <cit.>, and release a
    more efficient version of for future research.
	
    
    
    
    
    

	
  * Artifact availability. Our data, tool, and results are
	available and will be released as open-source.[<https://zenodo.org/records/10851256>]






§ ILLUSTRATIVE EXAMPLE








style=javastyle













Consider the buggy and fixed versions of (Chart, 4) from
 <cit.>, shown in Figure <ref>. The
original buggy code is missing a null check, which the developer fixed by adding 
if(r != null) around the
implicated code at line 4493.   

The  <cit.> template-based program repair technique produces candidate
patches by repeatedly instantiating
applicable templates at program statements, ordered by Ochiai SBFL
suspiciousness score. 
For example, Figure <ref> a -generated patch that does
not cause the tests to pass, and so is discarded, and the search continues.
Given Chart's associated test suite, the Ochiai SBFL approach <cit.> assigns line 4473
the highest suspicious score in Chart of 0.52; line 4493, a suspiciousness score
of 0.49; and 0.03 to lines 4494 and onward. Using only SBFL for fault localization ranking, the actual faulty line at
line 4493 is ranked as 10th most suspicious. 
This does not prevent from considering it, but does cost time.  

can produce patches that pass all tests for this bug, such as the one shown in 
Figure <ref>.  In the interest of reasoning about
efficiency, we hold fault localization constant <cit.>; given that,
this is the 19th patch attempted.






However, although this patch prevents the null pointer exception, it does not
generalize beyond the provided tests to capture the apparent developer intent. Importantly, can
produce the correct patch (from Figure <ref>), if configured to execute beyond the  first
test-passing patch found — it is the 70th patch attempted, but only the second
that passes all tests.[Using SBFL fault localization, produces these patches at 1076 and 1127, respectively.] 

LLM-based entropy provides useful clues, here, however.
First, consider fault location: we use
 <cit.>,[When prompted
with the code and asked to fix the bug directly, does not produce a test-passing patch in few-shot setting. Note that GPT4 fixes the
bug correctly, and reports the git commit associated with the fix, implicating
data leakage.] to measure the entropy of every line in this file. Rank-ordering
them, line 4473 is ranked 8th-most-surprising.  This is better than the SBFL
technique on face.  However, their real utility appears to lie in
combination: re-ranking the lines receiving the Top-10 SBFL suspicious scores by
entropy values, puts line 4493 at rank 2. 
We investigate how entropy in conjunction with SBFL performs for fault localization across multiple bugs
and projects, as well as how different LLMs affect its performance.

We can also measure the naturalness of generated
patches, such as by calculating the change in entropy, which we call
entropy-delta (E),
between the original buggy line of code and the proposed patches. The E for the test-failing patch is -0.39; for the test-passing but
still-incorrect patch is -1.18; and for the correct patch is 0.25. 


The entropy-delta scores do not perfectly predict behavior (note that the
test-failing patch has a higher score than the test-passing-but-incorrect
patch), but it still suggests: 

    
  * Entropy-delta can improve efficiency by suggesting the order to test
    patches.  Test execution time is the dominant cost in program repair.  By using entropy to rank potential patches
    before testing them, to suggest the order in which to do so, both
    test-passing patches can be found within 6 attempts (improving on 19 to the
    first test-passing in the default mode, and 90 to find the second, correct
    patch).
    
  * Entropy-delta can potentially help disambiguate
    plausible-but-incorrect from genuinely correct patches.
 






We evaluate these relationships in detail in the rest of this work, showing how
entropy can usefully complement traditional approaches to automatic localization
and transformation in the context of program repair. 









§ APPROACH


















We ask and answer the following three research
questions about the utility of LLM-entropy for APR.

    
  * RQ1: How can entropy improve fault localization? We perform an
   empirical evaluation of prior state-of-the-art fault localization tools and
   observe whether and how they benefit from the use of entropy scores. 

    
  * RQ2: How can entropy improve patch generation efficiency? To
    measure how entropy can be used for patch generation efficiency, we use
    it to rank proposed patches generated by an APR technique before
    running tests.
    
  * RQ3: How well does entropy-deltas identify correct patches? We
    investigate if entropy-delta can differentiate plausible patches (patches
    that passes all tests) and correct patches (patches that correctly fix the
    bug).



This section describes how we use entropy for fault localization (Section <ref>);
 our development of entropy delta for evaluating patches
 (Section <ref>); and our modifications to to enable our
 study of improved patch efficiency (Section <ref>).  The next
 section describes datasets and metrics. 





 §.§ Entropy for fault localization



We integrate raw entropy scores into prior fault localization techniques.  
Figure <ref> overviews the approach.  We take suspiciousness scores
provided by a given prior FL tool for a given file. For consistency with prior
studies of fault localization, we focus on top-N identified lines (as developers
do not typically inspect more than 5
candidates <cit.>).  We choose 6 and 10 
for N, and name the two approaches 6-filter and 10-filter, as these are two
quantities near the Top-5 that can 
still significantly impact Top-5 scores. 

We then query an LLM for entropy scores for each line of code in that file. We
tokenize the entire file, iteratively masking each line, and querying the model
for each line's entropy. We used a sliding context window with 2048 tokens
(i.e., the maximum attention window of our smallest selected LLM) surrounding
the mask as suffix and prefix context. This allows us to assign entropy-based
scores for all code in a file, even those longer than a given LLM's context
window. 

We then re-rank the suspiciousness code identified by SBFL by entropy score, and
validate the ranked list according to the actual fault location in the dataset.

We incorporate entropy into three previous FL techniques: SBFL using the Ochiai
formula <cit.>, TransferFL <cit.> and LLMAO <cit.>.
Ochiai is a common formula in SBFL used in traditional APR practices (e.g.,
). TransferFL and LLMAO are the current state-of-the-art FL techniques using transfer-learning and LLMs, respectively.



 §.§ Entropy-Delta



To evaluate patch naturalness, which we use in both patch prioritization during
generation/evaluation and patch correctness prediction, we introduce the concept of an
“entropy-delta”. Entropy delta describes how code replacement changes the naturalness
of a block of code. Figure <ref> and
Figure <ref> give examples for our usage of entropy-delta
for assigning a ranking score for patches. Figure <ref>
shows the process of masking out a deleted line of code and querying the LLM for
the change in entropy using that mask (i.e., the change in entropy without the original line). Figure <ref> shows
the process of querying the LLM for the change in entropy if the tokens of the
original line of code is replaced with new tokens of patch code. If the patch is
an insertion of a blank new line, we query the entropy-delta between the “newline” token and the original line of code.
For the case of an insertion, we measure the entropy-delta between the new code line and the original blank line.

An entropy-delta is simply the change in entropy before and after a line in code
is replaced. For instance, if the line's original entropy is 1.0, and the
replacement line's entropy is 0.5, then the line has an entropy-delta of +0.5,
as in, replacing that line lowered entropy by 0.5. A significant reduction in
entropy (large, positive entropy-delta) means that the replacement code lowered
the entropy, implying both that the original statement may have been buggy and
that the patch is more natural for that region of code. A large, negative
entropy-delta means that the replacement code increased entropy, meaning that
the patch is less natural at that location. An entropy-delta of 0 means that the
patch has the exact same naturalness as the original code.







 §.§ Modified TBar



Our patch efficiency experiments ask how entropy can speed up patch generation
and evaluation.  We evaluate it in context of  <cit.>, the best-performing
template-based program repair technique in the existing literature.  We avoid
using ML-based APR techniques (even though some may outperform
 <cit.>) because our goal is a controlled evaluation of entropy without learned patterns from the test suite.  Evaluating based on a technique that otherwise also relies on trained ML
models fails to isolate the effect of entropy per se.

is a template-based patch generation technique
integrated with V1.2. Our experiments require several modifications to the
codebase.  First, we enable to continue seeking patches after the first
test-patching patch is found.  Second, we enable to generate patches, or
evaluate them in a customized order (such as one provided by an entropy-delta ranking).
Our extension also includes some refactoring for
modifiability/extensibility, as well as a more accurate patch caching mechanism
(caching the patched source code, rather than the patch alone).  We provide the
modified code with our replication package.



§ DATASETS AND METRICS


In this section, we describe the models we use for entropy
(Section <ref>), the bug and patch datasets considered
(Section <ref>), as well as evaluation metrics (Section <ref>).



 §.§ LLMs



We used  <cit.>, Starcoder <cit.>, and Code-Llama2
<cit.>. The three LLMs were trained on open-source code and are capable of
infilling with bidirectional context. The model <cit.> is a
large-scale decoder-only Transformer model with 6.7 billion parameters. The
model was trained on a dataset of code from public open-source repositories on
GitHub and GitLab, as well as from StackOverflow. 



was primarily trained for code infilling, which involves the insertion
of missing code snippets in existing code, using a causal-masked objective
during training. However, its versatility enables it to be utilized in a variety
of software engineering tasks, including automatic program repair. Starcoder and
Llama-2 were trained with a similar autoregressive plus causal-mask objective as
. Starcoder was trained with 15.5 billion parameters. Code-Llama2 have
three versions available: 7B, 13B and 34B. We choose the 7B version as it is
the closest in size to the other two models. Although the three LLMs were
not specifically trained for repair, their large architectures and training
objectives could imply that their entropy values on a particular region of code
could suggest code naturalness. For all experiments, we set the LLM temperature
to 0.5.



 §.§ Dataset









We use the  <cit.> dataset as the basis of our
experiments.  is a well-established set of documented historical bugs in Java
programs with associated tests and developer patches. It is commonly used in
APR, testing, and fault localization research. However, each research question requires a different subset of the
data. Table <ref> shows the number of bugs in each project that
have at least one patch passing tests (for analyzing patch efficiency) and a
developer fix (for analyzing patch correctness) along with plausible but
incorrect patches. In total, we analyze 72 bugs from V1.2 for patch
efficiency and 197 bugs from V2.0 for patch correctness.

We used V1.2 for the fault localization and patch generation experiments. 
We do this because off-the-shelf TBar, as well as prior fault localization tools' replication packages, are all only compatible with V1.2. The fault localization experiments consider all 395 bugs in V1.2.  
We choose not to use V2.0 for fault localization because prior tools' replication packages are only compatible with V1.2. 

For patch generation, the goal is to evaluate the degree to which entropy can improve repair efficiency; we therefore focus on the subset of V1.2 bugs on which vanilla succeeds at least once.




For patch correctness ranking, we use curated datasets from prior tools'
replication packages directly, namely, Shibboleth <cit.> and
Panther <cit.>. Shibboleth and Panther are both tools that leverage
static and dynamic heuristics from both test and source code to rank and
classify plausible patches, built on top of the updated V2.0 dataset. We
use a dataset of 1,290 plausible patches on V2.0 curated by Ghanbari et
al. <cit.>. For patch classification, we use a dataset of 2,147
plausible patches on V2.0 curated by Tian et al. <cit.>. The
patches from Tian et al. <cit.> were generated by seven different APR
techniques. Each bug in the data set has one correct patch and several plausible
(i.e., test passing) but incorrect ones. We calculate the change in entropy
between the section of code in the original (buggy) file and the patched
version. Note that both datasets only contain patches in projects Chart, Closure, Lang, Math, Mockito, and Time (6/17 of V2.0's total projects), to compare with prior work built on V1.2. Instead of the total number of bugs 835 in V2.0, we only consider the 434 bugs in the 6 projects included by Shibboleth <cit.> and
Panther <cit.> (shown in Table <ref>).



 §.§ Metrics



Fault localization and patch ranking. We measure the effectiveness of both fault localization ranking and patch
ranking by counting the number of correct faults or patches that appear in the
Top-N position. The Top-N measure has been widely used in APR
research <cit.>. Existing studies <cit.>
showed that over 70% of developers inspect only the Top-5 suggested elements.
We use Top-5, Top-3, and Top-1 for fault localization ranking. We only use Top-2
and Top-3 for patch ranking following Ghanbari et al. <cit.>, as some
bugs in our dataset only have 2 plausible patches available.

Patch generation efficiency. We measure the effect of
reranking generated potential patches in terms of the number of patch
evaluations saved by doing so.  Patch evaluations are established as a
hardware- and program-independent measure for APR efficiency <cit.>,
and a proxy for compute time. 

Patch correctness.
For patch classification tasks, we convert entropy-delta values into binary labels. We
label patches with a positive entropy-delta as “more natural” (i.e., more
likely to be correct), and patches with a negative entropy-delta “less
natural” (i.e., less likely to be correct). To measure entropy's ability to
isolate correct and incorrect patches, we use +recall and -recall. +Recall
measures to what extent correct patches are identified, while -recall measures to
what extent incorrect patches are filtered out.  We use accuracy, precision, and
F1 scores to assess classification effectiveness over the entire dataset. 




















§ RESULTS














  
In this section, we present results on the performance of entropy and entropy-delta on our three
research questions: 


    0em 
    
  RQ1: Can entropy improve fault localization?
    
  RQ2: Can entropy improve patch generation efficiency?
    
  RQ3: How well does entropy-deltas identify correct patches?




 §.§ RQ1: Can entropy improve fault localization?

In this research question, we compared 24 different configurations for fault
localization. Our analysis aims to determine the most effective approach for
identifying the buggy statement in a series of one line bugs. We first measure
entropy directly for fault localization with our three selected LLMs:
Code-Llama2, Starcoder, and . We then measure the fault localization
accuracy of three prior fault localization tools: SBFL <cit.>, TransferFL <cit.>, and LLMAO <cit.>.

Finally, we use entropy to re-rank prior fault localization tools and observe
that entropy re-ranking largely improves prior tools. Table <ref>
shows the Top-N scores (N = 1,3,5) on all configurations of our experiment. We
observe that the entropy of , the smallest LLM in our lineup, is
the most effective for fault localization. This is consistent with results
from Xia et al. <cit.>, who found
that , trained with an objective of predicting missing code from a
bidirectional context, is more effective at program repair tasks than larger
but purely causal generative LLMs.

SBFL. From Table <ref>, we observe an overall
decrease in Top-N scores using either Code-Llama2 or Starcoder entropy with a
10-filter. However, all Top-N scores improve with the 6-filter. In particular,
the Top-3 score of 84 for Llama2 entropy improves upon SBFL by 38%, and the
Top-3 score of 86 for Starcoder entropy improves upon SBFL by 41%. Using
entropy to re-rank SBFL  shows substantial improvements across all Top-N
and the two types of filters. entropy-SBFL with a 10-filter achieves a
Top-1 score of 50 (108% improvement), and 5-filter achieves a Top-1 score of 55
(129% improvement). Similarly, the Top-3 and Top-5 scores improve by 61% and
41%, respectively for entropy-SBFL with a 10-filter. The Top-3 and
Top-5 scores improve by 92% and 50% respectively for the 10-filter.


TransferFL. As seen in Table <ref>, we observe
an improvement from entropy on TransferFL's Top-3 and Top-5 scores using a
6-filter. In particular, 6-filter -entropy with TransferFL Top-3 is 156
(24% improvement), and 6-filter Llama2-entropy with TransferFL Top-5 is 184
(27% improvement). However, 6-filter -entropy with TransferFL yields a
Top-1 score of 57, which is a 17% decrease in performance than TransferFL by
itself. As compared to state-of-the-art machine learning based FL techniques, we
observe that entropy scores perform worse on Top-1.










LLMAO. Similar to the results of TransferFL, re-ranking with
entropy only improves fault localization results using the 6-filter.
Furthermore, only entropy calculated using shows an improvement over
LLMAO alone for Top-3 and Top-5, with a 8% and 1% improvement, respectively.
Since LLMAO is already an LLM based FL tool, LLM entropy re-ranking shows
marginal improvements as compared to prior non-LLM based FL tools. LLMAO
finetunes on CodeGen 16B <cit.>, which is a larger LLM than
our three chosen LLMs.


Our results indicated that SBFL benefits the most with 's entropy
re-ranking. Since SBFL has the most amount of tied suspicious scores (2.9 ties
per bug on average), the additional suspiciousness from entropy values helps to
break ties. 




TransferFL and LLMAO benefit from entropy
re-ranking mostly when using a 6-filter. These findings suggest that
incorporating entropy as a heuristic in fault localization can improve the
accuracy of identifying the buggy statement, particularly when used in
conjunction with SBFL. 


  [colback=white,colframe=black,arc=0pt,boxrule=0.5pt,title=RQ1
   Summary,boxsep=2pt,left=1pt,right=1pt,top=1pt,bottom=1pt,fonttitle=]
   We leverage entropy for fault localization in programs and show that,
   while entropy alone is only somewhat useful for finding defective lines, the
   measure is highly complementary when combined with prior fault localization
   tools, which highlights the importance of combining LLM-based methods with
   techniques from prior APR approaches.
  



 §.§ RQ2: Can entropy improve patch generation efficiency?









In this section, we discuss the observed relationship of entropy and
test-passing patches. We use entropy from , the most successful LLM in
RQ1's fault localization. We measure the impact of entropy-delta on patch
generation efficiency with two methods: (1) measuring each successful
(test-passing) patch's ranking as ranked by original and entropy-delta
re-ranked , and (2) incorporating entropy-delta into and measuring the
total number of  patches generated to pass all tests. 

We first configured to generate only 100 patches per each Defects4J bug,
assuming perfect fault localization. Of the patches we generated, 72
passed all tests contained in their bugs' respective repositories (e.g., all
tests written for project Chart). Finally, we calculated the entropy-delta score
for each patch, and the test-passing patch's original ranking according to
. As seen in Table <ref>, entropy-delta improves 60
out of the 72 rankings as compared to 's original ranking. On average, we
observed a mean rank decrease of 24, meaning that using entropy-delta to rank
the generated patches can reduce a mean of 24 full test iterations (i.e.,
each potential patch must run through all test cases in the repository before
knowing if it is a plausible patch). Liu et
al. <cit.> compared 16 APR techniques and found that exhibits one of the highest number of patches generated, but also the highest rate of bug fixing across .
We posit that entropy-delta's efficiency improvement over significantly boosts template-based APR's overall utility.

Figure <ref> compares the ranking
and entropy-delta ranking. Each bar represents the rank of test-passing patches
compared to all generated patches per project. A lower rank signifies a
more efficient repair process, as the repair process ends when a test-passing
patch is found. As seen in Figure <ref>, 's original
ranking for test-passing patches is higher than entropy-delta's ranking across
all projects. Entropy-delta shows a higher disparity on ranking between test
passing and test failing patches (i.e., a lower median rank for all test-passing
patches). In particular, patches from projects Chart and Time show the largest
improvement from re-ranking patches with entropy-delta. Successful patches in
Chart and Time typically require multi-line edits, and with a wider range of
templates to choose from, entropy-delta can make a greater impact in reducing
the number of patches tested.

We then configured to use entropy-delta ranked patches directly, and
measured the total number of patches required until a successful bug fix (i.e.,
passing all tests). Figure <ref> shows the median number
of patches tested per project before a successful patch using original
ranking and entropy-delta re-ranking. We observe that entropy-delta re-ranking
reduces the median number of patches tested across all projects except for
Mockito. Mockito has only three single line bugs that can fix. With a smaller total number of patches
to try on a single template (e.g., 11 total possible patches for Mockito-26),
entropy-delta re-ranking does not have as large of an impact on APR efficiency. 







  [colback=white,colframe=black,arc=0pt,boxrule=0.5pt,title=RQ2
 Summary,boxsep=2pt,left=1pt,right=1pt,top=1pt,bottom=1pt,fonttitle=]
 We show that entropy can be used to rank patches before going through the
 entire test-suite, thereby reducing the test overhead for template-based repair
 technique by a mean of 24 patches tested. Entropy-delta can both reduce
 the median number of patches tried before finding a fix, and consistently rank
 test patching patches higher than test-failing patches without any dependency
 on the test-suite. Entropy-delta is most useful for bugs that require
 multi-line patches.





 §.§ RQ3: How well does entropy-deltas identify correct patches?














In RQ2, we saw that entropy-delta can improve the efficiency of patch
generation by reducing number of patches tested. However, it is important to
note that a test-passing patch is not necessarily correct. To further explore
the issue of correctness, we investigated the ability of entropy-deltas to
distinguish between correct and incorrect patches, both of which are
test-passing.



  §.§.§ Patch ranking

We evaluate a dataset of 1,290 patches generated by 7 prior APR methods
collected by Ghanbari et al. <cit.>. For each bug, the data set
includes some number of plausible (i.e., test passing) patches, where exactly
one is correct, and the rest are incorrect. We attempt to isolate the true
correct patch from the incorrect patches. We then rank each patch according to
its entropy-delta, querying the model for the entropy of the entire patch region
before and after the replacement. Table <ref> shows the Top-1
and Top-2 results of our approach on the labeled dataset of 1,290 patches. We
see from Table <ref> that entropy-delta outperforms both SBFL
and Shibboleth <cit.> on Top-2 across all projects, and entropy-delta outperforms
Shibboleth on Top-1 across all projects but Chart (10 Top-1 as compared to
Shibboleth's 11 Top-1). Overall, we see that entropy-delta improves upon
Shibboleth by 49% for Top-1, and 27% for Top-2.

The difference in entropy reduction between correct and plausible but incorrect
patches is shown in greater detail in Figure <ref>. We see a
clear difference in entropy-delta across correct and incorrect patches. In
particular, the correct patches for all six projects have a median entropy-delta
value of above 0, and the incorrect patches for all six projects have a median
entropy-delta value of below 0. A correct patch tends to appear
more natural to the LLM as compared to its original buggy line. 


















  §.§.§ Patch classification


Table <ref> shows our classification results on a
labeled dataset of 2,147 plausible patches curated by Tian et al. <cit.>
for classifying patches as correct or incorrect. Entropy-delta 
improves upon the accuracy score of PATCH-SIM <cit.> and Panther <cit.>, but only slightly
improves +recall score over both PATCH-SIM and Panther. For -recall,
entropy-delta performs better than PATCH-SIM by 9%, but performs worse than
Panther by 10%. Entropy-delta slightly improves accuracy over Panther by 0.6%,
and 89% over PATCH-SIM. Entropy-delta improves precision over Panther by 18%,
and PATCH-SIM by 267%. Finally, entropy-delta performs better than both
PATCH-SIM and Panther on F1 score, by 118% and 10% respectively. As compared to the state-of-the-art, entropy improves classification performance on true positives more than true negatives. 



Our analysis focused on comparing the degree of entropy reduction between true
correct patches and plausible test-passing patches. As shown in
Table <ref>, Table <ref>, and
Figure <ref>, our results suggest that correct patches
tend to lower entropy (i.e., increase naturalness) more than incorrect patches. 
Specifically, entropy-delta ranks 49% more correct patches in the Top-1
than the state-of-the-art patch ranker Shibboleth, and entropy-delta can
classify correct patches with an 18% higher precision than the state-of-the-art
patch classifier Panther. These findings suggest that entropy-deltas can be a
valuable heuristic for distinguishing between correct and incorrect patches.


  [colback=white,colframe=black,arc=0pt,boxrule=0.5pt,title=RQ3
    Summary,boxsep=2pt,left=1pt,right=1pt,top=1pt,bottom=1pt,fonttitle=]
    The entropy-delta from an LLM distinguishes between correct and plausible
    (test-passing but incorrect) patches with
    higher precision and accuracy than state-of-the-art patch disambiguation tools.





§ RELATED WORK



We discuss in the following sections the most recent advances in LLM for code,
fault localization, and patch ranking.



 §.§ LLM for code

Language models have been used for code generation, bug detection, and patch
generation. Recent language models finetune on code as training data and can
perform code completion <cit.>, and generate code
based on natural language <cit.> with impressive results. Large
Language Models (LLMs), such as Codex <cit.>, GPT-Neo <cit.>, and
Llama-2 <cit.> have raised performance on these tasks by using more
trainable parameters and training data. Ray et al. <cit.> study the
relationship between bugginess and LLM-entropy. Ray et al. empirically showed
that n-gram models trained over a large corpus of code will find buggy
statements more surprising, as indicated by a high entropy score. Kolak et
al. <cit.> revisit the question of naturalness (i.e., the
human-readability) of patches in the era of large language models. Kolak et al.
experimented with models ranging from [160M to 12B] parameters, and measured the
similarly between LLM generated patches and developer written patches. Their
results show that larger models tend to generate test-passing lines at a higher
rate. Additionally, LLM generated patches tend to be more similar to the
human-written patch as model size increases. Xia et al. <cit.>
directly applied LLMs for APRs and found that LLMs can suggest multi-line fixes
with higher accuracy than state of the art APR tools. Our study performs an
empirical evaluation of how code naturalness (i.e., entropy) can improve prior
APR tools across three different stages of automated program repair: fault
localization, patch generation, and patch ranking.



 §.§ Fault localization

Prior fault localization tools use test output information, code semantics, and
naturalness of code to achieve a high degree of confidence on bug detection.
Spectrum-based Fault Localization (SBFL) <cit.> uses a ratio of passed and failed tests covering each line of
code to calculate its suspiciousness score, in which a higher suspiciousness
signifies a higher probability of being faulty. Recent advances in deep learning
created a spur of research on using graph neural networks (GNNs) <cit.> for
fault localization. GRACE <cit.>, DeepFL <cit.>, and
DEAR <cit.> encode the code AST and test coverage as graph representations
before training deep learning models for fault localization.
TransferFL <cit.> combined semantic features of code and the
transferred knowledge from open-source code data to improve the accuracy of
prior deep learning fault localization tools. LLMAO <cit.> finetuned
a light-weight bidirectional layer on top of code-tuned LLMs to show that LLMs
can detect both bugs and security vulnerabilities without the use of test cases.
Our work builds on top of the top-performing prior fault localization tools and
show that entropy can be used as a light weight re-ranking tool that improves
fault localization scores without a dependency on test cases.



 §.§ Patch correctness

Similarly to prior fault localization tools, prior patch disambiguation tools
leverage test output information and code information (both code syntax and code
semantics) for ranking or classifying patches. Qi et al. <cit.> analyzed the reported
bugs of three generate-and-validate APR tools: GenProg <cit.>,
RSRepair <cit.>, and AE <cit.> systems, to find that producing
correct results on a validation test suite is not enough to ensure patch
correctness. Smith et al. <cit.> performed
an experiment that interrogates whether or not automatically generated patches
are prone to overfitting to their test suite. Borrowing the concept of training
and test sets from machine learning, they found that automated program repair
(APR) typically used the same test-suite for both “training" (generating the
patch), and “testing" (validation). Smith et al. found that both the coverage
rate of the test-suite, as well as the assignment of test/train sets between the
two suites, impact the degree of overfitting in repair. To counteract the
overfitting problem, Ye et al. <cit.> proposed ODS (Overfitting
Detection System), a novel system to statically classify overfitting patches.
Xiong et al. <cit.> generated both execution traces of patched
programs and new tests to assess the correctness of patches. Ghanbari et
al. <cit.> used both the syntactic and semantic similarity between
original code and proposed patch, and code coverage of passing tests to rank
patches. Shibboleth <cit.> was able to rank the correct patch in
Top-1 and Top-2 positions in 66% of their curated dataset. Tian et
al. <cit.> proposed machine learning predictor with BERT
transformer-based learned embeddings for patch classification. Tian et al. found
that learned embeddings of code fragments with BERT <cit.>,
CC2Vec <cit.>, and Doc2Vec <cit.> yield similarity scores that,
given a buggy code, substantially differ between correctly-patched code and
incorrectly-patched one. 







The most relevant work to our study of patch correctness is Yang et al. <cit.>. Yang et
al. <cit.> found that state-of-the-art learning-based techniques
suffered from the dataset overfitting problem, and that naturalness-based
techniques outperformed traditional static techniques, in particular
Patch-Sim <cit.>. Our work uses 2,147 plausible patches collected in
2023 (past the LLM training data cutoff of all our chosen LLMs), which lowers
the risk of LLM training data leakage. Our work performs an empirical study on
entropy against the most recent state-of-the-art patch disambiguation techniques
Panther <cit.> and Shibboleth <cit.>, on top of
Patch-Sim <cit.>. Motivated by Liu et al. <cit.>, our work
is the first to use LLM entropy on plausible patches before undergoing testing
to achieve more efficient APR on prior template-based techniques. Finally, we
introduce a new naturalness measurement for patches, entropy-delta, which
achieves state-of-the-art results for plausible patch disambiguation without
depending on the test-suites of buggy programs, which lowers the risk of dataset
overfitting.





§ THREATS


External validity.
A threat to the external validity of our study is the potential selection bias
of our three selected LLMs. We chose a representative set of LLMs with a range
of trainable parameters. We chose the three based on their infill ability and 
built-in bidirectional attention mechanism. Much larger LLMs (> 20
billion parameters) might have a stronger ability to reason over faulty code
lines and patches, but require much larger computation power and time for
entropy calculation. Another threat to external validity is our usage of data
throughout our empirical evaluation. We chose for our target bugs for
fault localization and patch disambiguation due to the data available and the
aim to compare against related work in APR. Data leakage of as training
data for our selected LLMs is possible. We mitigate this risk by (1) using
entropy in combination with prior APR techniques instead of direct LLM prompting
for patch generation, and (2) applying entropy-delta on untested or plausible
patches that are not available online (i.e., recently generated and not used as
an official patch for bug fixing).

Internal validity.
An internal validity is the manual labeling of plausible patches. We used
manually labeled data released by prior works <cit.>, in
which the authors followed clear and reproducible decision criteria. Although
mistakes could still be made on which plausible patches are correct or
incorrect, we use the same labeling for all prior tools studied as well as
entropy to create a standardized baseline on patch classification.

Construct validity.
One source of construct validity is the measurements we chose for our empirical
evaluation. We used Top-N as a ranking measurement for both bugs and patches,
following prior APR work. To overcome some limitations of Top-N, we also use
multiple patch classification measurements (accuracy, precision, recall, and F1)
on a separate set of labeled patch data to strengthen generalizability.




§ CONCLUSION


In this work, we propose the use of “unnaturalness” of code for automated
program repair through the measurement of entropy generated by code-tuned LLMs.
We also introduce the term entropy-delta, which measures the difference in
entropy between a proposed code insert (i.e., a patch) and the original code.
Using three LLMs and three prior fault localization tools, we show that entropy
can improve Top-5, 3, and 1 scores after re-ranking the first 6 potential bug
localization. We use entropy-delta on untested patches to save an average of 24
test runs per bug for the template-based APR technique TBar. We show that
entropy-delta can improve upon state-of-the-art patch ranking by 49% for Top-1,
and classify plausible patches with a 18% higher precision. Our results
indicate that LLMs can be a powerful addition to state-of-the-art APR tools
without the dependency on tests, and the usage of LLM code-generation. The
reduction in both test suites and LLM code-generation results in the reduction
in model over-fitting and training data leakage.

IEEEtran


