Intervention-Based Alignment of Code Search with Execution Feedback
Authors: Hojae Han
Minsoo Kim
seung-won hwang
Nan Duan
Shuai Lu
Venue: EMNLP 2023 Findings (2023)
Keywords: Code Search
Misalignment
Reinforcement Learning
Intervention
TL;DR: Reinforcement Learning with Code Intervention to Align Model Decision and Execution Feedback in Code Search

Abstract: One of the fundamental goals in code search is to retrieve a functionally correct code for a given natural language query. 
As annotating for correctness requires executing test cases (i.e. obtaining execution feedback), existing code search training datasets approximate text-code co-occurrences as positive execution feedback. However, this approximation may misalign models’ retrieval decisions from ground-truth correctness. 
To address such limitation, we propose Code Intervention-based Reinforcement Learning (CIRL) that perturbs training code to result in misalignment (i.e. code intervention), then tests models’ decisions and corrects them with the execution feedback by reinforcement learning. The first technical contribution of CIRL is to induce the execution feedback from perturbation, without actual execution. Secondly, CIRL introduces structural perturbations using abstract syntax trees, going beyond simple lexical changes. Experimental results on various datasets demonstrate the effectiveness of CIRL compared to conventional approaches.

Intervention-Basee Alignment of Code Search with Execution Feedback
Hojae Han Minsoo Kim A Seung-won Hwang Nan Duan", Shuai Lu
Scoul National University, {stovecat, minso09574, SeungwonhJ@snu. Microsoft Research Asia, [shuailu, Jenirroff com
Abstract
Query (q): Find the longest increasing subsequence (LIS) of given array.
One of the fundamental goals in code search is to retrieve a functionally correct code for given natural language query. As annotating for correctness requires executing test cases (i.e. obtaining exccution feedback), existing code search training datasets approximate text-code co-occurrences as positive execution feedback. However, this approximation may misalign models' retrieval decisions from ground-truth correctness. To address such limitation, we pro- Reinforcement pose Code Intervention-basee Learning (CIRL) that perturbs training code to result misalignment (i.e. code interven- tion), then tests models' decisions and corrects them with the execution feedback by reinforce- ment learning. The first technical contribution of CIRL is induce the execution feedback from perturbation, without actual execution. Secondly, CIRL introduces structural perturba- tions using abstract syntax trees, going beyond simple lexical changes. Experimental results on various datasets demonstrate the effectiveness of CIRL compared to conventional approaches.
Code (c):
from bi sect
import bisect_ left
def find LIS (array):
for num in array:
idx = bisect left (dp, num)
if idx == 1en (dp):
(npp)
else:
dp [idx] = num
return
le: (dp)
Rg =
(a) positive code to query & conventional dataset.
Code (c'): from bisect import bisect left
def find LIS (errey):
dp
for nur. in array: idx bisect Lettt__etttleee (dp, zum)
if idx -- len (dy):
dp. append (num)
return 1en (dg)
EF Rg 1
(b) A negative code with misaligned Ro with EF.
1 Introduction
Figure 1: Example code snippets with the execution feedback (EF) from running environment and the model's retrieval decisions (Rt) trained on a conven- tional code search dataset. The code line difference between the code pair is highlighted as blue.
Code search aims retrieve code snippets that most relevant to a given query. However, the notion relevance often falls short of capturing the ulti- mate goal of functional correctness, focusing on whether the code would execute the programmer intended (Ding et al., 2022). For instance, pro- grammers would prefer (in Figure la) over c' (in Figure lb), as the entire "else" clause is missing in d.
CodeSearchNer (CSN; Husain et al., 2019), collect data from GitHub by regarding commented text descriptions as queries then labeling code snippets by query-code co-occurrences. This collection pro- cess can introduce an observation bias of lexical dissimilarity between positive and negative train- ing snippets. Consequently, models learn such observation bias. resulting in misaligned retrieval decisions with EF of returning negative code with high lexical similarity as a false positive. For ex- ample, Figure 1b shows that a code search model
Ideally, ground truth labels for functional cor- rectness should obtained from execution feed- back, collected after executing each code with a sufficient amount of test cases for each query g. We denote such execution feedback as EF(gg, c).
However, conventional training datasets, such as
"Corresponding author.

---

0, trained from a conventional dataset, decides to retrieve d, or Rø(g,c) c') but this model deci- sion misaligned with the execution feedback, or EF(q, c) =.
tic validity while replacing subtrees, discourage exposures to trivial syntax errors.
We summarize our contributions as follows: First, we employ reinforcement learning with in- tervention that performs perturbation to simulate misaligned code without feedback from real code execution. Second, we propose CIRL, which uti- lizes AST information inject structural changes to code to alter EF while preserving model decision. Third, our experimental results on various datasets show that CTRL effectively contributes to aligning code search with EF.
The objective of this paper is to resolve the misalignment, i.e., Rg * EF. A straightforward solution is to expose models to misaligned code pairs and correct the model decisions by EF. In reinforcement learning (RL), this trial-and-error process is achieved by interacting with agents while perturbing input states, referred to as inter- vention (Lee and Bareinboim, 2020; Carta al., 2023). We employ this intervention technique by perturbing the positive training code e to gener- ate its negative counterpart c, where both code snippets yield the same model decision. Formally, Rø(g.e') c') = Ro(q, e) but EF(g, c) > EF(g, c'). However, obtaining EF to correct decisions for each d' is expensive, and make matters worse, there are infinite possible perturbations satisfying the above misalignment condition. To identify a representative d', existing solution known as coun- terfactual perturbation (Kaushik et al., 2020; Han et al., 2021; Choi et al., 2022; Chen et al., 2022), suggests to find c' that is lexically closest to c, but with different EF. However, adopting this strategy would expose models solely to trivial syntax errors, such omitting colon from Figure la, causing syntax error (and thus different EF). A realistic in- tervention, such as Figure to Figure 1b, induces a larger lexical change, such as removing the "else" clause.
All our implementation and datasets are publicly available' for future research purposes.
2 Preliminary
In this section, we will begin by defining the code search task and addressing the misalignment issue in existing supervised code search training.
2.1 Code Search
For a universe of queries Q and code snippets C. the ultimate goal of this task is to find functionally correct snippets for each query. The functional correctness between query q E Q and code E can be confirmed by execution feedback (EF) from an environment using a set of test cases TCy:
1, V(,,, 40) E TC2, c(ti)) = tor EF(q,c) 0. otherwise,
Our key technical contribution is a sample- efficient code intervention for RL. Our pro- posed approach, namely Code Intervention-baat Reinforcement Learning (CIRL), perturbs pos- itive code into negative with structural changes, which is designed to include the intuition of mini- mal lexical edit, but generalizes beyond enfold structural similarity.
where (ti, E TCg is a test input-output pair and c(4) signifies running by feeding 4, Our goal is to build code search model 0 making its retrieval decision Rg (0, 1} align with EF for any g and c, i.e. Vg O Ve E C, Ro(g,c) EF(g, c).
2.2 Supervised Baseline
Ideally, a training dataset D* should comprise query-code pairs along with EF as labels, encom- passing both positive and negative examples, i.c.. D* = (gg c, EF(q,c))lg E Q, E C}. However, building such a dataset at scale is nontrivial due to the high costs and efforts involved in manu- ally annotating test cases for each query, execut- ing the code with test cases, and creating a secure
Specifically. we leverage the abstract syntax tree (AST) representation of the code, treating subtrees such as statements, clauses and expressions, as units of structural changes. A structural pertur- bation is done by masking out subtree from positive code then filling it out unless model pre- diction changes. We stress that CIRL subsumes counterfactual perturbation (when subtree is leaf), and also adapts to the test distribution, by select- ing subtrees with a realistic granularity (c.g. "else" clause in Figure la). Further, we ensure syntac-
'https:/ //gi thub. com/stoovcat/CIIC "Although code search typically aims to retrieve relevant code snippets, pursuing functional correctness is valuable, e.g. in scenarios where generated codes are directly executed, as relevance is a subset of functional correctness.

---

Structural Code Perturbation
(ap. ap)
EXE-ENV.
...
Po (c
④
Sp+1 (r41
(q. (c,
(r:,7))
Pa (sg
Figure 2: Overview of our reinforcement learning framework with code intervention. ① Given a state 8, consists of query and of candidate code snippets, code search policy takes action a, retrieve code oa @ CIRL perturbs the retrieved code into & with Abstract Syntax Tree (AST) information. 3 CIRL intervenes the state S; to & by replacing e into 4 and makes 0 take another action of from 84 If e4 is not retrieved, we go hack to the second stage. 4 When de is retrieved by d, though expect to receive the EF from execution environment
as a reward-ryy T141 EF(q, 6.) and r/+1 EF(q. c)) CIRL can skip this costly stage by inducing the EF during perturbation. 5 8 updated align its decision with the
environment for possibly unsafe code when exe- cuted (Chen et al., 2021; Li et al., 2022c). Due to this reason, traditional training dataset such CodeSearchNet (CSN; Husain et al., 2019) is gathered from GitHub by assuming that each func- tion implementation e and its corresponding com- mented description q (i.e. c) 1) can sub- stitute EF: = [[g c, 1)]q Q. C, R(g.c) 1}.
abstraction enables to extend beyond these cases to situations where the RL-based model can choose to contradict (lesscr-effectivve) curriculum rules."
RL Formulation. In the process of retrieving positive code snippets from pool of M candidates in D by model 0, we regard 0 as policy and for- mulate code search Markov decision process, which consists of following elements:
In training time, negative code snippets for query are sampled from other queries' positive snip- pets. However, these sampled negative snippets both lexically and structurally dissimilar to posi- tive ones. To illustrate, we examine that 97% of positive-negative code pairs in CSN Python train- ing set score very low in lexical/structural similar- ity.² As a consequence, dataset / exhibits bias towards positive code, leading to functionally mis- aligned retrieval decisions by model 0 trained on D when comparing positive code to lexically similar negative code. Figure 1 is example of such betriveti both and e' despite their different EF due to a missing "else" clause.
Given a query q. the state 8 in time step t is defined as (g, Ct) where Co is the set of M candidate code snippets.
States:
Actions: A(s:) is a set of possible actions from the state 8t, and a, A(s,) is retrieval
decision of a code e E i.e. i.e. Rø(g, c.) = 1.
Reward: The reward of is defined as the EF of e, i.e. EF(g,c).
Transition: The transition from 8, to 81+1 by at is done by removing o from C.-
Discount factor: y E [0. 1] is discount fac- tor to estimate the current value of future re- wards, i.e., G,
3 Methodology
> > C++k).
3.1 Contribution I: Reinforcement Learning with Intervention
Code Intervention. To resolve the misalignment, we intervene a retrieved code a; in step t by replac- ing it into of such that Rø(g, c4) = Ro(g, ot) = 1 but EF c,) > EF <)) The overall process of our RL with code intervention is illustrated in Fig- ure 2. Formally, the pairwise policy gradient of 0 in step from two actions a, and of respectively
We employ RL with code intervention to resolve the misalignment of model decisions and EF. Al- though RL behavior may resemble supervised or curriculum learning in specific scenarios where nules align with model decisions, our proposed RL
0.3 CodeBL.E EU (Ren et al., 2020) scores, which con- siders both lexical and structural similarity.
"Refer to Appendix B for details.

---

retrieving code et and &4 is,
Try stmt
Try stmt
A0 (Gr G.) log pe (a, st)
stmm
If stmt
-V log pe d.]ss)),
(2)
Call stmt
Expr stmi
"False"
where po is the probability distribution of actions taken by 0, and s/ is the state after intervention by replacing e into 4- G2 and G2 is the cumulative re- wards starting from for at and df respectively. As
"Foo"
"()
try:
try: False:
if foo():
we replace the retrieved code c₁ into of to generate & from 8t, both states have the same next state, or, - G² EF(q, ct) EF(g, c).
Figure 3: CIRL replaces subtrees that share the same ancestor AST node sequence ("try" statement - "if" statement) to avoid syntax eπrоTs.
8t+1 = $(41 thus Gt
Then Eq (2) becomes,
A = (EF q. cx) - EF(g, 4)) log (a((e(s))
the perturbation to flip EF from 1 to O, we can la- bel EF== for the perturbed code without incurring actual exccution.
-V Po (d/l=/))
(3)
However, the counterfactual objective of mini- mizing lexical edits is too restrictive for composi- tional nature of code (Han al., 2022). To illus- trate, Figure and 1b are lexically rather distant, but semantically close, or, parse tree structure only c away.
This equation suggests that gradients can be cal- culated efficiently, in a single transition. Lastly, avoid directly comparing the policy gradients from different states 8; and s//. we approximate two states into a single virtual state 8 = (g, C o {4]). As 0 can take both and of in Bg we only need to maximize in Po:
Inspired, we propose to relax lexical minimiza- tion to train more realistic EF-contrastive pairs, with the following goals:
A = (EF(g, - EF(g, 4)) (o
A pair should be free of syntax errors. Using lexical perturbation often incurs syntax errors such as omitting semicolon.
(4)
From the perspective of Levine et al. (2020), our approach can be understood as an online off- pollyy RL, where of acts as an action produced by an off- policy and is the target policy. In this light, code intervention is akin to importance sampling that leverages predictions of the target policy to choose actions likely to be undertaken.
A pair must maintain contextual consistency. For example, when we change the if condition in Figure 3, lexical perturbation can break the context of 'try statement if statement'.
A pair should match the target distribution such as large lexical edits. Lexical perturba- tion with minimal edits results deviate from the desired distribution.
3.2 Contribution II: Structural Perturbation
However, computing AO in Eg (4) is still expensive, due to the following challenges: First, we need to compute BF(g,c) c') for each gradient calculation. Second, from the perspective of off-policy RL, we need to pursue sample efficiency, as the search space of & satisfying Ro(g, ct) = Ro(g, c.) = yet EF(q. c.) > EF(g, 4) is enormously broad. A conservative approach is applying minimal lexical edit, c.g., changing '+' operator to '-', to guarantee alter the EF, keeping RG unchanged two code snippets are lexically near-identical, which we denote as lexical counterfactual pertur- bation (Kaushik et al., 2020; Han et al., 2021; Choi et al., 2022; Chen et al., 2022). As we intended
Toward the goals, we propose subtree pertur- bation for augmenting pair, ensuring the above criteria:
Controlled Syntax and EF Error: We model code revisions utilizing Abstract Syntax Trees (ASTs), to consider subtrees like statements and clauses elements for perturbations."
'Empirical evidence suggests that less than 1% of the code snippets augmented by our method (sourced from the Codeforces training set) contain syntax emrrr and potential EF noises play negligible roles for our contrastive training objectives.

---

We consider two code search basclines our ex- periments. First baseline is GraRHCodeBERT (Guo et al., 2021), popular code search model that uses data flow, a graph structure for representing the Maintaining Contextual Consistency: As shown in Figure 3, the augmented code satis- fies contextual consistency by matching the ancestor nodes during subtree replacement.
uniformly sample names from the code e for vari- ables and functions in the injected subtrees. We ensure consistent replacements for repeated names. Finally, we convert the perturbed AST back into its code form, resulting in c'.
Target Distribution Matching: The newly inserted subtrees, being derived from actual code snippets, match the target distribution.
Experiments
4.1 Datasets
Note that we can avoid expensive EF(g, c') invoca- tion, as it subsumes counterfactual perturbation as special case where the subtree is a leaf node.
The evaluation is performed on three categories of benchmarks.
The first category involves large-scale public code competition datasets, namely Codeforces (Ca- ballero et al., 2016) and CodeNet (Puri et al.. 2021). These datascts consist of natural language descriptions paired with code submissions includ- ing Python. We use the cleansed version from CodeContests (Li et al., 2022c), filter examples not written in Python language, code/description longer than 512 tokens, and those which cannot be parsed into ASTs.? 7 We train on Codeforces and conduct evaluations on both sets. To see the perfor- mance across diverse difficulty, we split CodeNet into 10 subsets by accept-ratios (the number of answer code snippets among submissions) as an ad- ditional evaluation set, complement Codeforces that is relatively too easy (accept ratio mostly 0.5 or higher).
3.3 CIRL
We present CIRL by providing a summary of the steps involved in the code perturbation from the original code to d' We begin with posi- tive query-code pair (q. c) in the dataset D where (F(g,c) = 1. We initialize perturbation ratio 0 100%, which determines the number of nodes be changed. This ratio gradually increased through iterations using a schedule func- tion s. Note that a structural change magnitude c can lead to significant lexical modifications with a magnitude of 6, impacting multiple leaf nodes.
During each iteration, we perform the follow- ing two steps and verify whether the model's de- cision on code e is maintained for the perturbed code d, i.e., Ro(g, c) Ro(q, d'). If the deci- sion preserved, we calculate AO in Eq (4) using d, increase using the schedule function s, and proceed with another iteration using the updated 8. The iteration process terminates either when Ro(g, c) * Ro(g, c') is satisfied or when the maxi- number of iterations is reached.
The second category involves AdvTest (Lu et al., 2021), which evaluates the misalignment of pos- itive code snippets that are not retrieved by code search models. This dataset is created by perturb- ing variable and function names while preserving EF from the test of CodeSearchNet Python (CSN-Python; Husain et al., 2019).
The third category focuses on CSN benchmark, which includes six different programming lan- guages. The evaluation specifically examines the performance on the Python and Ruby subset of CSN, which is filtered from previous work (Guo et al., 2021).
Step 1: Subtree Removal. We convert c into its AST representation. Then, based on the node perturbation ratio 8, we randomly select a set of subtrees to remove. Each subtree's s root node is a statement, clause, expression. The total number of nodes for the selected subtrees is approximately equal 8% of the AST nodes for
Overall, these benchmark categories provide comprehensive evaluations of CIRL and its im- pact on aligning model decisions with EF across various datasets and scenarios.
Step 2: Subtree Insertion. For each removed subtree, we sample a new subtree from other code snippets in the dataset D. To maintain syntactic va- lidity, adopt conservative guideline: select a new subtree only if it shares the same ancestor AST node sequence with the removed subtree as depicted in Figure 3. To prevent name errors, we
4.2 Code Search Baselines
"Wo empirically tune to adapt to the test distribution. Please refer to Appendix C.2 for more details.
Detailed statistics are shown in Appendix D.

---

Metric: MRR
(g c)
High- struct. sim.
Codeforces
CodeNet
Method
Zero-cost
Neg.
Valid
Test
0-10
10-20
20-30
30-40
ContraCode
84.24
83.33
44.21
46.83
57.51
54.13
GraphCodeBERT
90.58
73.71
39.24
48.02
53.48
56.14
CI-ADV
75.65
74.54
34.54
42.79
48.18
49.58
CI-PLM
X
88.91
75.52
45.65
47.82
60.14
67.17
CI-HUMAN
X
/
93.48
76.40
44.68
60.17
62.31
68.84
CIRL
V
92.39
79.90
54.99
55.98
63.23
66.09
CI-HUMAN
X
96.74
79.02
56.99
57.86
68.36
71.04
Code Intervention
/
86.96
85.75
43.86
51.89
55.53
64.63
EF d)
High-
CodeNet
Method
Zero-cost
Neg.
struct. sim.
40-50
50-60
60-70
70-80
80-90
90-100
ContraCode
59.39
70.16
73.78
71.44
73.45
93.93
GraphCodeBERT
65.29
68.16
73.24
76.34
74.04
94.65
CI-ADY
X
56.27
66.15
68.25
73.19
70.98
93.67
CI-PLM
X
A
66.61
74.35
81.31
82.77
81.24
98.11
CI-HUMAN
X
/
77.34
77.77
83.26
86.59
85.54
96.86
CIRL
V
/
78.01
80.64
87.50
90.81
87.99
98.11
+ CCI-HUMN
79.32
82.44
87.75
90.94
89.79
99.06
Code Intervention
72.92
77.97
83.61
84.94
89.97
93.87
Table I: Results on Codeforces and CodeNet. Zero-cost and Neg. columns below BF(g, respectively stands for whether the method requires zero-cost obtain EF intervened data, and whether intervened codes receive negative EF, High-struct. sim. column signifies whether intervened codes share high structural similarity with original codes, where triangle for CI-PLM means that the high similarity is not ensured as language models are hard be fully controlled their generation process. '. Code Intervention' is an ablation study that employs simple curriculum contrastive learning instead of reinforcement learning with code intervention.
relation among iiriable-decllaationn assignment, usage, and removal. Second baseline Contra- Code (Jain et al., 2021), which conducts contrastive pretraining on conventional datasets. To minimize truncation, we use a bi-encoder for encoding the description and code separately, following Guo al. (2021) and Jain et al. (2021).8 We obtain the last layer's representation of the [CLS] token for each query and code, then compute the predic- tion score."
we compare CI-HUMAN and CI-PLM on Code- forces and CodeNet, because of the prerequisites in both baselines- the existence of test cases and human generated negative code snippets.
This baseline utilizes human efforts by generating additional code snippets that receive negative EF. Unlike conventional distribution such as CSN, Codeforces provides not only the set of positive code for each query, but also the set of negative code for each query. This approach addi- tionally utilizes the latter set for code intervention.
CI-HUMAN
4.3
Code Intervention Baselines
We compare CIRL with different code augmen- tation approaches as code intervention baselines instead of our structural perturbation." Note that
CI-PLM Following Inala et al. (2022), we can augment negative code snippets generated by code generation models instead of expensive human ef- forts. We GPT-Neo 2.7B (Black et al., 2021) finetuned on APPS (Hendrycks et al., 2021) dataset to generate snippets in Codeforces training set, then calculate the EF for each generated code.
*Note that CIRL. maintains model-agnosti nature, it acknowledges the potential enhancement of coss-en models by intervened data, such iteratively sampled hard negatives in dense text retrieval, demonstrated in Zhang et al. (2022).
"Refer to Appendix C.1 for implementation details. 1"Refer to Appendix C.2 for implementation details.

---

Metrie: MRR
Metrie: MRR
Maximum Train Epochs
Maximum Train Epochs
Model
AdvTest
Model
CSN-Python
ContraCode
10
22.2
ContraCode
10
59,9
CIRL
10
22.1
CIRL
10
62.2
GraphCodeBERT
2
35.2
GraphCodeBERT
10
69.2
GraPhCodeBERT
10
37.1
CI-ADV
10
64.1
CI-ADV
10
32.3
CIRL
10
68.3
CIRL
10
39.0
Table 3: Results on CSN-Python: All results were opti- mized with early stopping, tailored performance on the validation set. We have omitted C1-PLM and CI- HUMAN since CSN-Python lacks test and human annotations. The result for is reported in Guo et al. (2021).
Table Results on AdvTest: All results were optimized with early stopping, tailored to performance the vali- dation set. We have omitted CI-PLM and CI-HUMAN since the training set (CSN) lacks test cases and human annotations. The result for is reported in Wang et al. (2021).
Metrie: MRR
Maximum Train Epochs
CI-ADV Like in AdvTest, code intervention may tackle misaligned model decisions caused by pos- itive code that are not retrieved, by semantic- preserving perturbation of each positive code c from D to d' such that Rg(g, c) > Re(a, é') but c'( EF(g, c) 1. Following Bui et al. (2021) and Lu et al. (2022), heuristic rules such the replacement of variable and function names, the insertion of dead code lines can be seen as defining such adversarial perturbation.
Model
CSN-Ruby
GraphCodeBERT
10
70.3
CIRL
10
72.0
Table 4: Results on CSN-Ruby: All results were opti- mized with early stopping, tailored performance the validation set. The result for is reported in Guo et al. (2021).
CIRL can complement human efforts. Lastly, the Code Intervention' ablation replaced RL with a basic curriculum contrastive learning, following settings in Appendix B. Its underperformance com- pared to CIRL highlights our RL mechanism's 's effectiveness.
4.4
Main Results
For evaluation, we used Mean Reciprocal Rank (MRR), a standard code search metric from previ- ous studies (Feng et al., 2020; Guo al., 2021; Lu al., 2021; Wang et al., 2021), with respect to the ground-truit truth ranking the correct answer as the top.
To evaluate whether CIRL contributes to aligned model decisions for adversarially per- turbed positive code, we applied CIRL on CSN- Python training set and evaluate on AdvTest. The training epochs were increased from 2 to 10, resulting in improved GraphCodeBERT perfor- mance. The results in Table 2 confirm that ap- plying CIRL ContraCode maintained perfor- mance, while enhanced performance on Graph- Code indicating that CIRL is reliable and potentially beneficial for correcting misaligned de- cisions in adversarial positive code. In contrast, CI-ADV exhibited drop of approximately 5% compared to GraphCodeBERR, which is further discussed in Section 5.4.
AdyTest
Codeforces and CodeNet Table presents im- proved MRR scores for evaluating the alignment of model decisions with EF using different code in- tervention approaches. Among the low-cost meth- ods, CIRL outperformed ContraCode, GraphCode- BERT, and CI-ADV. Even when compared to the costly methods, CIRL still significantly out- performed CI-PLM and generally outperformed CI-HUMAN. Regarding the code difficulty, CI- Human enhanced MRR by over 2% in difficult CodeNet ranges (0-10 to 30-40), but less in casier ranges (40-50 to 90- 900) Conversely, CIRL con- sistently boosted MRR across all code difficulties, showcasing its widespread efficacy. Additionally, CIRL combined with CI-HUMAN, achieved the best performance, showing the augmentation from
The results on the conventional distribution, where observation bias is strongly correlated with the label, are presented in Table CIRL enhanced
CSN

---

Metric: MRR
CodeNet Structural Perturbation by CIRL
Model
0-10
10-20
20-30
30-40
40-50
ContraCode
37.32 -6.89
39.30 -7.53
44.99 -12.52
35.34 -18.99
38.40 -20.99
GraphCodeBERT
32.79 -6.45
38.99
.9.03
40.25
-13.23
41.60
-14.54
43.65 -2164
+CI-HUMAN
42.34 -2.34
57.30
-2.7
55.04
-7.27
60.82
-8.02
70.75 -6.59
CIRL
54.99 -0.00
55.98
-0.00
63.23
-0.00
66.09
-0.00
78.01 -0.00
+ CI-HUMAN
56.99 -0.00
57.86
00.00
68.36 -0.00
71.04 -0.00
79.32 -0.00
Table 5: Test time code augmentation by our structural perturbation to CodeNet. The red colored numbers are MRR drops after augmentation intervened codes by CIRL. Note that CIRL trained without the test set.
the MRR score ContraCode and showed only marginal decrease GraphCodeBERT. Addition- ally, Table demonstrates CIRL's effectiveness across programming languages, showcasing results on Ruby code snippets.
GrapbCod:BERT
COUNTERFACTUAL
CIRL
Crdeforces Valid
CodeNet 0.9-1.D
Codeforces Test
CodeNet 0.8
90%
CodeNet 0.0.0.1
5 Discussion
5.1 Is CIRL Perturbation Sample-efficiett?
CodeNet 0,7-0.8
70%
CodeNet 0.1-0.2
We conducted stress test by applying CIRL on 5 test subsets of CodeNet 10.0-0.1 0.4-0.5). The results in Table demonstrate that both Contra- Code and GraphCodeBERT experienced drops in MRR scores after augmenting the intervened code snippets, indicating confusion between intervened negative code and positive code. Although C1- HUMAN reduced this confusion, the model still suffered from MRR drops. However, applying CIRL successfully resolved this confusion and pre- vented MRR drops.
CodeNer 0.6-0.7
CodeNet 0.2-0.3
CodeNol 0.5-0.6
CodeNet 0.3-0.4
0.4-0.5
Figure Relative MRR performance to CIRL. COUN- TERFACTUAL approach which intervenes code with minimal lexical edit suboptimal.
5.3 Does CIRL. Generalize Over Different Programming Languages?
5.2 Does CIRL Generalize Over Counterfactual Perturbation?
Table 4 shows that CIRL successfully improved the MRR performance on CSN-Ruby. Though our AST perturbation mechanism may look more com- plex than lexical perturbation, it straightforwardly generalizes other languages, AST parser (e.g., tree-sitter) easily applies other languages for extracting a language-genett representation to per- turb.
We examined the impact of CIRL allowing for more structural changes, compared to counterfac- tual perturbation with minimal lexical changes. To ensure a fair comparison, we implemented a COUN- TERFACTUAL. baseline from CIRL by fixing the perturbation ratio 8 small value (6 2) to focus on small lexical changes. Figure presents a comparison of GraphCodeBERTT COUNTERFAC- TUAL, and CIRL. on Codeforces and CodeNet benchmarks. As expected, COUNTERFACTUAL exhibited lower MRR scores compared to CIRL, and even lower than GrRThCodeBERT in some test sets.
5.4 Can Augmentation Negatively Affect Performance?
may seem counter-intuitive that of the exist- ing augmentation approaches, C1-ADv, negatively affects the MRR scores throughout our experiments. We speculate that CI-ADV relies on heuristic rules for perturbation, which inherently have limitations
"Refer to Appendix C.3 for details.

---

in terms of the coverage of perturbations in order preserve EF. For instance, augmenting code per- turbation by variable renaming results in high lexi- cal and structural similarity with the original code. Consequently, this augmentation may amplify the observation bias from the original code, leading to more misaligned decisions in trained models.
Aligned Rg with EF 100%
80%
BI Positive Codes
Negative Codes (CI-HUMAN)
Negative Codes (CIRLRM)
60%
Negative Codes (CIRL)
5.5 Can LLMs Align better with EF?
40%
We explore whether general-purpose large lan- guage models, benefiting from enormous parameter scales, can detect misalignments. To confirm this. we use GPT-3.5 (OpenAl, 2022) to evaluate query- code pairs from CodeNet 0.0-0.1 I and determine whether the code is correct for the given query, in the following two settings: (1) zero-shot; (2) in-context learning (ICL) by providing a positive (q, c) and a negative pair (4, d') randomly sampled from the Codeforces training set."
20%
0%
Zero-shot
In-context Learning
Figure 5: Alignment accuracy (i.e. 100% if Rg EF for all Ry) of GPT-3.5 on CodeNet 0.0-0.1. For in- context learning, we additionally gave a query and positive-negative code snippets sampled from Code- forces training set.
Fail to Align Human Perturbations. GPT-3.5 inaccurately identified negative code snippets by CI-HUMAN as false positives, performing worse than random guessing of 50% (see the 'Negative Codes (CI-HUMAN) graphs in Figure 5).
Conclusion
This paper has explored the issue of misalignment of model decisions and EF due observation bias in traditional training datasets. To overcome this limitation, we have introduced a novel RL frame- work with code intervention called CIRL. The pri- mary contribution of CIRL is to expose models to misaligned code snippets, which can be sub- sequently corrected through EF. CIRL is sample efficient by utilizing ASTs simulate structural perturbations for code intervention, allowing us bypass actual execution for EF. Extensive experi- mental results on various datasets demonstrate that CIRL enhances the alignment of model decisions and EF in code search compared to conventional approaches.
Fail to Align Subtree Removals. To illustrate the weakness of GPT-3.5 for negative code with subtree removals, implemented CIRLRM doing the removal step only. GPT-3.5 failed to identify omitted implementations such handling edge 13 shown in Figure that 'Negative Codes (CIRLRM)' graphs were lower than random guess- ing (50%).
Succeed When Code Lines are Replaced. GPT- 3.5 showed 100% aligned decisions with EF for negative code snippets consisting of replaced sub- trees, shown as "Negative Codes (CIRL)' graphs in Figure 5. GPT-3.5 often explained the reason for its decision the presence of unnecessary or unrelated code lines."
Acknowledgement
This work was partially supported by Microsoft Research Asia, and Electronics and Telecommuni- cations Research Institute (ETRI) grant funded by ICT R&D program MSIT/IIT 20022-0-00955, Automated reliable source code generation from natural language descriptions).
In-Context Learning Fails. A naive solution of employing ICL with positive and negative exam- ples did not improve the alignment, contrasted by zero-shot and ICL groups in Figure 5. Against our expectation, even increased misalignment for negative code by CI-HUMAN and CIR CIRL We leave the alignment of LLMs' decisions with EF for future work.
Limitations
Despite our achievements. there are following lim- itations in this work. First, we mainly tackled Python language, appending with Ruby. Sccond, while CIRL is agdesssg, we applied it to
PRRfer to Appendix C.4 for details. 13 Example outputs are shown in Appendix F.

---

ContraCode and GraphCodeBERT, conducting pre- liminary analysis on LLMs, and leaving extensive application on LLMs for future work.
Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xi- aocheng Feng, Ming Gong, Linjun Shou, Bing Qin. Ting Liu, Daxin Jiang, and Ming Zhou. 2020. Code- BERT: pre-trained model for programming and natural languages. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1536-1547, Online. Association for Computational Linguistics.
References
Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. 2021. GPT-Neo: Large
Scale Autoregressive Language Modeling with Mesh- Tensorflow.
Xiaodong Gu, Hongyu Zhang, and Sunghun Kim. 2018. Deep code search. In 2018 IEEE/ACM 40th Interna- tional Conference on Software Engineering (ICSE). pages 933 944..944 IEEE
Nghi DQ Bui, Yijun Yu, and Lingxiao Jiang. 2021. Self- supervised contrastive learning for code retrieval and summarization via semantic- semantic-preservinng transforma- tions. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 511-521.
Daya Guo, Shuai Lu, Nan Duan, Yanlin Wang, Ming Zhou, and Jian Yin. 2022. UniXcoder: Unified cross- modal pre-training for code representation. In Pro- ceedings of the 60th Annual Meeting of the Associa- tion for Computational Linguistics (Volume I: Long Papers). pages 7212-7225, Dublin, Ireland. Associa- tion for Computational Linguistics.
Ethan Caballero. OpenAl, and Ilya Sutskever. 2016. Description2Code Dataset.
Nitay Calderon, Eyal David. Amir Feder, and Roi Reichart. 2022. DoCoGen: Domain counterfactual generation for low resource domain adaptation. In Proceedings of the 60th Annual Meeting of the As- sociation for Computational Linguistics (Volume I: Long Papers). pages 7727-7746, Dublin, Ireland. As- sociation for Computational Linguistics.
Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie LIU, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, Michele Tufano, Shao Kun Deng, Colin Clement, Dawn Drain, Neel Sundaresan, Jian Yin, Daxin Jiang, and Ming Zhou. 2021. Graphcode (bert):: Pre-training code represen- tations with data flow. In International Conference Learning Representations.
Thomas Carta, Clément Romac, Thomas Wolf, Sylvain Lamprier, Olivier Sigaud, and Pierre-Yves Oudeyer. 2023. Grounding large language models in interac- tive environments with ouline reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMr...rg.
Hojae Han, Seungtack Choi, Myeongho Jeong, Jin-woo Park, and Seung-won seung-won Hwang. 2021. Counterfac- tual generative smoothing for imbalanced natural lan- guage classification. In Proceedings of the 30th ACM International Conference on Information & Knowl- edge Management, pages
Hannah Chen, Yangfeng Ji, and David Evans. 2022. Balanced adversarial training: Balancing tradcoffs between fickleness and obstinacy in NLP models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 632- 647, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Hojae Han, Seung-won Hwang. Shuai Lu, Nan Duan, and Seungtaek Choi. 2022. Towards compositional generalization in code search. In Proceedings of the 2022 Conference on Empirical Methods in Natu- ral Language Processing, pages 10743-10750, Abu Dhabi, United Arab Emirates. Association for Com- putational Linguistics.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph. Greg Brockman, et al. 2021. Evaluating large language models trained on code. arXiv preprint S.Xiv22007.0337..
Dan Hendrycks, Steven Basart, Saurav Kadavath, Man- tas Mazeika, Akul Arora, Ethan Guo, Collin Burns. Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. 2021. Mcasuring coding challenge com- petence with APPS. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurlPS Datasets and Bench- marks 2021, December 2021, virtual.
Seungtaek Choi, Myeongho Jeong, Hojae Han, and Seung-wor won Hwang. 2022. C2I: Causally contrastive learning for robust text classification. Proceedings of the AAAI Conference on Artificial Intelligence.
Yangruibo Ding, Luca Buratti, Saurabh Pujar, Alessan- dro Morari, Baishakhi Ray, and Saikat Chakraborty. 2022. Towards learning (dis) similarity of source code from program contrasts. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 6300-631 12, Dublin, Ireland. Association for Compu- tational Linguistics.
Yujing Hu, Qing Da, Anxiang Zeng. Yang Yu, and Yinghui Xu. 2018. Reinforcement learning to rank in e-commerce search engine: Formalization, anal- ysis, and application. In Proceedings of the 24th ACM SIGKDD International Conference on Knowl- edge Discovery &amp; Data Mining, KDD '18, page 368-377, New York, NY, USA. Association for Com- puting Machinery.

---

Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Mare Brockschmidt. 2019. Code- searchnet challenge: Evaluating the state of semantic code search. arXiv preprint arXiv:
Yujia Li, David Choi, Junyoung Chung, Nate Kushman. Julian Schrittwieser, Rémi Leblond, Tom Eccles. James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022c. Competition-level code generation with alphacode. Science, 378(6224):0092-1000
Jeevana Priya Inala, Chenglong Wang, Mei Yang. An- dres Codas, Mark Encarnación, Shuvendu K Lahiri, Madanlal Musuvathi, and Jianfeng Gao. 2022. Fault- aware neural code rankers. In Advances in Neural Information Processing Systems.
Tie-Yan Liu. 2009. Learning to rank for information retrieval. Foundations and Trendy@ in Information Retrieval, 3(3):22--311
Shuai Lu, Nan Duan, Hojae Han, Daya Guo, Seung-
Paras Jain, Ajay Jain, Tianjun Zhang, Pieter Abbeel, Joseph Gonzalez, and Ton Stoica. 2021. Contrastive code representation learning. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 5954-5971, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
won Hwang. and Alexey Svyatkovskiy. 2022. Reace: A retrieval- -augmeeed code completion framework. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACI. 2022, Dublin, Ireland, May 22-27 2022. pages 0227-6240. Association for Com- putational Linguistics.
Akshita Jha and Chandan Reddy. 2023. Codeat- tack: Code- adversarial attacks for pre-trained programming language models. Proceedings of the AAAI Conference on Artificial Intelligence.
Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin B. Clement, Dawn Drain, Daxin Jiang. Duyu Tang. Ge Li, Li- dong Zhou, Linjun Shou, Long Zhou, Michele Tu- fano, Ming Gong, Ming Zhou, Nan Duan, Neel Sun- daresan, Shao Kun Deng, Shengyu Fu, and Shujie Liu. 2021. Codexglue: A machine learning bench- mark dataset for code understanding and generation. In Proceedings of the Neural Information Process- ing Systems Track on Datasets and Benchmarks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual.
Divyansh Kaushik, Eduard H. Hovy, and Zachary Chase Lipton. 2020. Learning the difference that makes A difference with counterfactually-eee aaanterrfattalll-aaggeeeeeddddd data. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. ReveReve.
Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Hoi. 2022. CodeRL: Master- ing code generation through pretrained models and deep reinforcement learning. Advances in Neural Information Processing Systems.
OpenAL. 2022. Chatgpt: Optimizing language models for dialogue. openai.
Bhargavi Paranjape, Matthew Lamm, and Ian Tenney. 2022. Retrieval-guided counterfactual generation for QA. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Vol- ume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 1670-1686. Association for Computational Linguisties.
Sanghack Lee and Elias Bareinboim. 2020. Character- izing optimal mixed policies: Where intervene and what to observe. In Advances in Neural Information Processing Systems, volume 33, pages 8565-8576. Curran Associates, Inc.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. 2020. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0166
Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladmir Zolotov, Ju- lian Dolby, Jie Chen, Mihir Choudhury. Lindsey Decker, et al. 2021. Project codenet: a large-scale ai for code dataset for learning a diversity of cod- ing tasks, ArXiv. Available at https://arxvv. org/abs. 2105.
Haochen Li, Chunyan Miao, Cyril Leung. Yanxian Huang, Yuan Huang, Hongyu Zhang, and Yanlin Wang. 2022a. Exploring representation-llvel aug- mentation for code search. In Proceedings of the 2022 Conference on Empirical Methods in Natu- ral Language Processing, pages 4924-4936, Abu Dhabi, United Arab Emirates. Association for Com- putational Linguistics.
Shuo Ren, Daya Guo, Shuai Lu, Long Zhou, Shujie Liu, Duyu Tang, Neel Sundaresan, Ming Zhou, Ambrosio Blanco, and Shuai Ma. 2020. Codebleu: a method for automatic evaluation of code synthesis. arXiv preprint a009::2009. 200.1977
Xiaonan Li, Yeyun Gong, Yelong Shen, Xipeng Qiu, Hang Zhang, Bolun Yao, Weizhen Qi, Daxin Jiang, Weizhu Chen, and Nan Duan. 2022b. CodeRetriever: large scale contrastive pre- pre-training method for code search. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2898-29188 1098-2910AAA00 Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Ensheng Shi, Yanlin Wang. Wenchao Gu, Lun Du, Hongyu Zhang, Shi Han, Dongmei Zhang, and Hong- bin Sun. 2023. Cocosoda: Effective contrastive lear- ing for code search. In Proceedings of the 45th Inter- national Conference on Softare Engineering, ICSE 223, page 2198-2210, IEEE Press.

---

Parshin Shojace, Aneesh Jain, Sindhu Tipimeni,, and Chandan K. Reddy. 2023. Execution-bee based code generation using deep reinforcement learning. Trans- actions Machine Learning Research.
Xin Wang, Fei Mi Yasheng Wang. Pingyi Zhou, Yao Wan, Xiao Liu, Li Li, Hao Wu, Jin Liu, and Xin Jiang. 2021. Syncobert: Syntax-guider multi-modal con- trastive ave-training for code representation. arXiv preprint arXiv:2108.0455:
Zeng Wei, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017. Reinforcement learning rank with markov decision process. In Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval, pages 945- 948.
Jun Xu, Zeng Wei, Long Xia, Yanyan Lan, Dawei Yin, Xueqi Cheng, and Ji-Rong Wen. 2020. Reinforce- ment learning rank with pairwise policy gradient. Proceedings of the 43rd International ACM SI- GIR Conference on Research and Development in Information Retrieval, pages 509-518
Zhou Yang, Jieke Shi, Junda He, and David Lo. 2022.
Natural attack for pre-trained models of code. In Proceedings of the 44th International Conference on Software Engineering, ICSE '22, page 1482- 1493, New York, NY, USA. Association for Computing Machinery.
Hang Zhang. Yeyun Gong, Yelong Shen, Jiancheng Lv, Nan Duan, and Weizhu Chen. 2022. Adversarial retriever-ranker for dense text retrieval. Interna- tional Conference on Learning Representations.
Xiangyu Zhao, Liang Zhang. Zhuoye Ding, Long Xia, Jiliang Tang, and Dawei Yin. 2018. Recommenda- tions with negative feedback via pairwise deep rein- forcement learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 1040-1048.

---

A Related Work
uses an actor-critic algorithm that gives rewards for policy gradients by a trained reward model. PPOCoder (Shojaee et al., 2023) utilizes Proximal Policy Optimization (PPO) to reduce syntax errors and improve functional correctness.
A.1 Deep Code Search Models
Recently, deep learning models have shown dra- matic improvements in the conventional code search task. Early approaches (Gu et al., 2018; Feng et al., 2020) directly mimic NLP archi- tectures and objectives. Later approaches addi- tionally utilize code specific information such as data flow (Guo et al., 2021), abstract syntax tree (AST; Wang et al., 2021; Guo et al., 2022, and tem- plate (Han et al., 2022). For pretraining, several approaches (Jain et al., 2021; Wang et al., 2021; Guo al., 2022; Li et al., 2022b) employ con- trastive learning of semantically related code-code and text-code pairs. Instead of random sampling. existing works (Li et al., 2022a; Shi et al., 2023) have proposed negative code sampling methods in expense of extensive model predictions or addi- tional memory usage.
Our distinction. Unlike IR, recommender sys- tem, and code generation domains, traditional code search training sets do not contain misaligned code pairs. Our distinction is to generate misalignment pairs with intervention, by perturbing a given pos- itive code to negative code while not changing model decision.
A.3 Synthetic Code Augmentation
To automatically supplement training code distri- bution, existing approaches (Bui et al., 2021; Yang et al., 2022) utilize semantic- preeeering perturba- tions by changing semantically ineffective lexi- cons (e.g., variable and function names). Other ap- proaches target software vulnerability by semantic- preserving perturbations to conduct adversarial at- tacks (Jha and Reddy, 2023), or learning to capture the semantics (Ding et al., 2022). Meanwhile, sev- eral approaches like CODERANKER (Inala et al., 2022) augment generated code snippets to train code search models.
Existing approaches trained by (self-)supervised learning in conventional datasets where execution feedback (EF) is approx- imated by text-code coocurrences, suffering from misalignment of model decisions with EF. Our dis- tinction is to employ reinforcement learning and intervene code to test and correct misaligned model decisions. Regarding negative code sampling, our approach plays similar role as hard negative min- ing, all while circumventing the need for extensive computational resources or memory usage.
Our distinction.
Our distinction. Unlike existing methods, we directly target code intervention in RL to align code search with EF, while managing both sample efficiency and zero-cost for EF calculation.
A.2 Reinforcement Learning in IR and Code Generation
A.4 Counterfactual Text Augmentation
Reinforcement Learning to Rank. In informa- tion retrieval (IR) and recommender system, which are related to code search, recent approaches have been applied reinforcement learning (RL), formu- lating document retrieval and item recommenda- tion markov decision process (MDP). In early approaches like PPG (Wei et al., 2017) policy estimates the absolute rank score of each candi- date (i.e. pointwise). Inspired by pairwise learn- ing to rank (Liu, 2009), later approaches (Zhao et al., 2018; Xu et al.. 2020; Hu et al., 2018) use pairwise loss between candidates sharing certain features with different feedback, improving sample efficiency.
In NLP, early approaches (Kaushik et al., 2020) pair each instance with its label-flipped augmentation, obtained from perturbing labels by human efforts with e lexical changes. Later approaches propose automatic syntheses to alleviate human efforts (Han et al., 2021; Paranjape et al., 2022; Choi et al., 2022; Calderon et al., 2022).
Our distinction. Applying e lexical changes to flip EF for code intervention is not sufficient as it only exposes to trivial lexical errors such as forget- ting colon from Figure la, thus fails to generalize in misaligned decisions over larger lexical changes like Figure 1b. Instead, we produce structural changes, which subsume c lexical changes as a special case of replacing a single Icaf node, thus broaden model exposures for generalization.
Reinforcement Learning on Code Generation. Several approaches have employed RL to gen- erate code snippets. CodeRL (Le et al., 2022)

---

Metric: MRR
Method
Rank Order
Contrastive Learning w/ Curriculum
NEGaff (Top NEGsim (Top 6) > POS (Top 7) POS (Top 1) > NEGaff (Top 7) NBG (Top 15)
CIRL
Table 6: The rank order of three code snippets for each method. Each code respectively shown in Table 7, 8, and
B Motivation of RL framework
target agent predictions. From the online off-policy RL perspective mentioned in Section 1, this data selection driven by the target agent enhance the quality of decisions made by the agent during testing.
Both supervised learning and curriculum learn- ing can be viewed as specific instances of the RL framework. Thus, it shouldn't 't be surprising that in certain fortuitous scenarios when Ro(q, c) = Rø(g, c') for every é', the RL framework may re- semble to them. However, this does not undermine the value of our RI. framework. To illustrate, cur- riculum learning utilizes predetermined rule for data selection during augmentation (like measur- ing AST perturbation levels). Our proposed RL framework encompasses such fortuitous scenarios where the rule strongly correlates with agent de- cision, making both RL and curriculum learning optimal.
C Implementation Detail
C.1 Code Search Baselines
GraphCodeBERT For all scenarios except CSN- Ruby, we finetuned the pretrained checkpoint of GraphCodeBERRT (Guo et al., 2021) the CSN (Guo et al., 2021) Python training set for 10 epochs using AdamW optimizer, a 2c-5 learning rate, max token lengths 128 (description) and 256 (code), max data flow length of 64, and a batch size of 32. The total training time was 1.5 days with 4 NVIDIA GeFFrce RTX 3090 (24GB) GPUs. In Codeforces (Caballero et al., 2016) training set, further fine-tuned GraphCodeBERT using 16 NVIDIA Tesla V100 (32GB) GPUs for 3 days with the following settings: using Adam optimizer, a 2e-5 learning rate, a batch size of 480, a max train- ing epoch of 10, max token lengths 512 for both description and code, and a max data flow length of 64.
However, our framework extends beyond these specific cases, into general scenarios when (a) agent disagrees with the rules from curriculum learning, contributing (b) disagreements gains:
(a) Agent-Curriculmm Disagreements. We sam- pled 100 positive code snippets from the Code- forces (Caballero et al., 2016) training set and corresponding generated negative snippets with five different perturbation ratios (same in Ap- pendix C.2). Spearman rank correlation analysis between selection orderings of these negative snip- pets by curriculum and by RL with intervention revealed that 17% of the rank correlations are be- low 0.5. This underscores that curriculum learning and RL-based intervention often have differing data selection preferences.
ContraCode We finetune the pretrained check- point of ContraCode (Jain et al., 2021) on Code- forces training set using 8 NVIDIA GeForce RTX 3090 (24GB) GPUs for 3 days with the same set- ting of GraphCodeBERT, except for the batch size of 96 and not using data flow. For CSN-Python and CSN-Ruby, we used the same setting of Graph- CodeBERT but not using data flow.
(b) Disagreements Contribute to Gains. An analysis of cases where curriculum learning fal- tered (i.e., top ranked code is negative) on the CodeNet (Puri et al., 2021) 0.0-0.1 test set revealed frequent rank discrepancies. For instance, the top ranked negative code typically shared only one line with the positive code, whereas the negative code with the most line overlaps had 19 lines in common with its positive counterpart. Table provides the qualitative evidence. Here, CIRL differs from the curriculum baseline by intervening code based on
C.2 Code Intervention Approaches
Throughout all approaches, we use GraphCode- BERT as a code search policy.
In Codeforees training set, CIRL inter- venes each positive code with maximum 5 iterations, where the initial perturbation ratio 8
CIRL

---

is initialized by 8 2 and updated by sched- ule function s(O, pa) 8 where μl [1. .... n| is the current iteration. The structural element one of the following AST subtrees: future import statement, import statement, import from statement, print statement, assert statement, expression state- ment, return statement, delete statement, raise state- ment, pass statement, break statement, continue statement, global statement, nonlocal statement, exec statement, if statement, for statement, while statement, try statement, with statement, function definition, class definition, decorated definition, elif clause, else clause, except clause, with clause, and block. In CSN training set, CIRL conducts a single intervention per code (n 1), where the perturbation ratio is set by 5 = 32. For other hy- the same values with Graph- CodeBERT, except for changing the batch size to 40 training with 8 NVIDIA GeForee RTX 3090 (24GB) GPUs for days on Codeforces training set.
C.4 Misalignment in LLMs
We use GPT-3.5-urbo-0613 (OpenAl, 2022)!$ with the top_p as and the temperature as for re- producibility, Appendix F shows examples of input prompts for both zero-shot and in-context learning settings.
CIRLRM For each code, we remove single structural element, where element is one of the following AST subtrees that do not incur syntax errors when removed: print statement, assert state- ment, if statement, for statement, while statement, try statement, with statement, function definition, class definition, else clause, except clause, and with clause.
perparameters,
CI-HUMAN We augment negative code for each positive code avoid overfitting, the size of negative code snippets is 30.70% of that of positive snippets in Codeforees training set.
CI-PLM We use GPT-Neo 2.7B (Black et al., 2021) finetuned on APPS (Hendrycks et al., 2021) dataset to generate 5 code snippets per problem description in Codeforces training set, then calcu- late the execution feedback (EF) for each synthetic code using the provided test cases from CodeCon- tests (Li al., 2022c). We train this baseline on the same setting with our approach, including the batch size 40.
CI-ADV To implement CI-ADV, available implementation from Lu et al. (2022) for variable/function renaming and and dead code in- sertion. In both Codeforces and CSN training sets, we augment the same number of iterations for each positive code, along with the same training config- uration.
the
C.3 Test Time Code Augmentation by CIRL
We intervene with a single iteration for each posi- tive code in CodeNet (Puri et al., 2021) subsets 10.0-0.1 0.4-0.5), where each the perturbation ratio 5, 15, 25, 35, and 45 is set by the average min-max accept ratio for each subset.
Shtpss//ilaiiaappp.icicmmmccccoe rescarchers

---

from sys import stdin from operator import attrgetter readline readline
def norm(a):
return a.real * a.real + a.imag a.imag
def closest_pair(p)) (en(p) <= I:
return float('inf"))
m len(p) //2
= min(closest, p0tpssss__p((ppp_mmm.. closest_ p
p = [pi for pi in if pim].imag pi.imag < <plm].imag + d]
return brute_force(p, d)
def brute_ forte_force(p... d=float('inf )):
p.sor((ky--atrreette 'real'))
for in (enge((1,ennp))
for j in reversed(range(()::
tmp pli] Plj]
if d tmp.real:
break tmp abs(tmp)
d tmp:
d= tmp
return d
def main():
int(rcadline()
p [map(float, readline(.splitt) for in range(n))
p + for x. y in
p.sor(key=aatrrgtter((mme))
print":.ff.formatccoeeees foomat((loossss_ppr(())) main()
Table 7: POS: A correct solution (EF=1) for test query in CodeNet 0.0-0.1.

---

from sys import stdin import operator
readline readliee
def norm(self): return abs(self)
def' closest closest_pair(p)::
0
d float('inf))
for i in range(1, len(p)):
for in reversed(range(m, i)):
tmp = plil pPi]
< tmp.real:
m=j+1
break
tmp abs(tmp)
if d tmp:
d tmp
return
from itertools import combinations
def forte_forcc(p:
return min(abs(pli) pīj)) for j. in combinations(rangellnni))) 2))
def main():
int(readline())
p [map(float, readline().spli() for in range(n)]
p [x + y * 1j for x, y in p]
# print( (:.6f) format(bbutteeooocceeee (rint((((:6f]] fooma((lossst__parr()))) main()
Table 8: NEG An incorrect solution (EF=0) for test query in CodeNet 0.0-0.1. 55.2% of code line overlaps with POS Table 7.

---

import numpy np int(input() p=
for in range(n):
d = []
min 999999999999
for in range(n-1):
for j in range(i+1,n):
if min: min a
printrouud(pppsqr((nnnn.11)))
Table 9: NEGaiff: An incorrect solution (EF=0) for a test query in CodeNet 0.0-0.1. 0% of code line overlaps with POS Table 7.

---

D
Dataset
No.
No. Wrong
Accept Ratho
Dataset Type
Dataset Name
No. Descriptions
Codes
Answer Codes
(Answers/Toal Candidates)
Trrining datasel
Codelorces (Train)
2,734
842,296
258,551
76.51%
Codeforces [Valid)
23
2.078
1,578
86.84%
Codeforces (Test)
34
2,336
1,914
54.96%
CodeNer 0.0-0.1
35
578
9,514
5.73%
CodeNet 0.1-0.2
58
17.127
87.466
16.37%
CodeNet 0.2-0.3
87
47.025
138,043
25 25,41%
CodeNet 0,3-0.4
115
88,936
167,185
34.72%
Evaluation dataset
CodeNet 0.4-0.5
151
132,689
161,173
15%15%
CodeNet 0,5-0.6
137
161,632
134,858
54.52%
CodeNet 0.6-0.7
159
235,737
126,197
65.13%
CodeNet 0.7-0.8
232
427,723
141,323
16.16%
CodeNet 0.8-0.9
169
317,505
61,476
83.78%
CodeNet 0,9-1.0
16,914
1,359
92.56%
Table Statistics for Codeforces and CodeNet.
E
CIRL: Case Study
1032_6. Personalized Cup
def print2d(a):
def printzd(a):
for range(len(al]:
print(" (ii((ss(maa(((ss a(ilm)))
for in rangel1, a+1]: = return
input()
inputt))
for in range[1, 5
fari in range(1, S 1/:
vst (le(sst)/// //i
vst len(st) //i
587_A. Duff and Weight Lifting
len[st]
int[1e6=100)
int(1e6+100)
min(ost, 1)
ifyst min(ast, 1] 20: break
intjinput(]
int(input(i)
continue
arr = list(map(int, input())splix)))
arr list/map(int, inputt).splittt))
[0]
ent [0]
for range(len(a)): for rangelvst):
for in range(lenta]): for in rangelvst]:
for in ent(i] +=
for
cntli] +
al] [ppend[(([())))) ind
alj] apjenddpnd()))
res, = 0,
res, s 0, range(N]:: -- cnt(l] res +- % res print(res)
in range(N)::
ost ost - 1 aljl pp(eddddst))))d) ind +=
oost 0: ost ost--1 applappend(st]in]]
-- entjil
res s %
5//=2 print(res)
True
887_ C. Solution for Cube
list/map(int, inputt).split())
inputi) trans
trans I
(1:5, 3: 5: 11, 22, 11: 12:1.1 14:44:33 3), [5:
[1:5, 9, 9:22 11:24, 24:
6),
17,17,4 4: 19, 10, 19:9, 941 10: 14: 16: 9),
3: 17,
17: 19: 9, 10: 16, 14:4, 16: 3),
def rotatelb, c= b[:] for | zip(s, t):
rotatelb, c=bli]
for I. in zipls. t): c(i-1]-bfp
c(i-1]
return for trans: chhcclrrotatea,, "zipl"".itern" iittems()))
return
i b map(s, input(]-spii(()) print('NO))
print[YES)
exit))
checkfrotate(a, "[listzip("kkitent httms//00smmmmm111pp print[Yes]]
exit()
print][NO")
Figure 6: Examples of original (left) and intervened (right) code snippets by CIRI.

---

F GPT-3.5: Case Study
Prompt
Please answer whether the following code is the correct implementation of the problem:
Problem: "Score: 700 points Problem Statement cells are arranged in a row. Some them may contain tokens. You are given string s that consists of O and the character of the i-th cell (from left) contains token. Otherwise, doesn't contain token. Smake
perform the following operation as many times as possible. In eoch operation, he chooses three consecutive cells. Let's call the cells X. Z from left to right. In order for the operation to valid, both and Z must contain tokens and must not contain token. Then, he romoves these two tokens and puts a new token Y. How many operations
perform he performs operations the optimal way?
Constraints
lsl =
Each choracter in is cither or 1.
Input
Input given from Standard Input the Following Formar:
Output
Print the answer.
Sample Input
1010101
Sample Outpet
example, can perform operationn in following way: Perform operation on last three cells, Now string Perform an operation the first three cells. Now the string that represents tokens becomme 0100010, Note that the choice of operations matters. For example, he chooses three cells the middle first, be can perform no more operations.
Sample Input
50
10101000010111100000000000000010 10U01001 10000101111 1101
Sumple Oulput
10"
'import
def updateed, k vy: if in max(d[k),
clse:
=
rep re.compile(((/2.))
ispul()
inpput)
for in re.ppliireep.erus...p s):
fs po.split('O))
Ifs len(is)
Ifss I:
= Listmmppeenn (s))
pl [[s[0]:00 0]
[b]1:]:
nl
for pc, in ittemm): updateinl. oc. if pe 0:
continue
if
update(al, 0, clsc:
update(al, 0,
updaretal, 1, 00-
updatetnl,
pl
ans maxppl.values())
print(ans)"
GPT335 Response
correct implementaiinn the problem, correctly solves the problem by finding the maximum of openatioss can be performed in the optimal The code regular expressions split the string inlo consecutive sequences of and ihen calculates the masimum number of operations that can be performed on each sequence. Finally, sums the maximum number of operations for all sequences and prints the result.
given
Table 11: A zero-shot example of aligned retrieval decision of GTP-3.5 with EF for positive code from CodeNet 0.0-0.1.

---

Prompt
Pleise answer whetler the following code the correct implenncttation the problem:
Problem: "Seore: 700 points Problem Statement colls are arranged in a row. Some of them may contain tokens. You are given string that consists of d contains
Otherwise,
contain
perform following
operation many times as possible, each operation, chooses three consecutive ccils. Let's call the cells X. Y. from left right. In order for the operation to valid, both and Z must contain tokens and Y must not contain token. Then, he removes these twa tokens and puts a new token on Y. perform performs operations the optimal way?
How many operations Constraints
N. 500,000
Each character in is either or 1.
Input
Inpur given from Standard Inpot following formar:
Output
Print the answer.
Sample Inpot
1010101
Sumple Oulpui
For example, can perform two operations in the fallowing way: Perform an operation on the last three cells, Now the string that Perfoom an operation on string represenis tokens the middle fiest, he can perfomm more operations.
three
the choice operations matters, For example, chooses three
Sumple Input
50
101010000100 101 10001001 100010001001111000000000000 Sample Oulput
10"
'import
def update(d,
if in d:
d[k] max(d[k), v)
else:
rep zeros co0pplee(((222))
input()
input().strp((0))
for in re.split(rep.zeross
6s ps.spitt(O)) (OO'
lentis)
if =u I:
continue
list(mapllen.
pl [Is[0]: 0]
ans 4= max(pi.vlluss())
print(ans)"
GPT-3.5 Response
the given code the correct implemeenatiioon of the problemi correctly counts number of operalions that can be performed in the optinnal way.
A zero-shot example of misaligned retrieval decision of GTP-3.5 with EF for negative code by CIRLAM removing the inner "for" statement from the positive code.
Table 12:

---

Prompt
Please answer whether the following code is the correct implementation of the problem: Problem: "During the research on propertiss of the greatest common divisor (GCD) set of numbers, Ilaar, famous mathematician, introduced brand
Code: 'import sye import math
stays.siiin
Reason: "The given code is the correct implementation of the problem because it follows the requirements and constmints stated the problem description.
Answer: Correct
whether following code cornett implementation problem: Problem: "During the research on properties of the greatest common divisor (GCD) of set of numbers, Iidar, famous mathematician, introduced hrand
Code: 'import sys import math
Emsys.stdin
Reason: "The code is not the correct implementation of the problem because it does not consider all possible cormbinations of pairs to find the weakened
Incorrect
Please answer whether the following code cornect implementaioon problem:
Problem: "Seare: points Problem Statement There N strings amanged known that, for any adjacent strings, the string left
Code: "N (nt(in))n()
listennptroo.iipuur)) int.pintttspppppi)(
A surtediA) and Ae == len(set(A)):
print())
exin(0)
def check(20::
= [D] Itr
for
ridx(-1]
six appennded()a)
Itrappend(U)
else:
while Trae:
while idxl-1]
idx pop()
IrppopO
if [ds]-1] t=
appendia) Itrappend())
if [dst-1] == return ltf
if [tr[1]] X:
break
idxf-11- 11-1
popt)
(op
[t]00 =
t- [1, N]
[01]-00]>11
mid = (Q[0) - /1D/22
([check(mid)) mid prini(([]])
GPT-3.5 Response
Reasoning: Thi given code is the correct inpilementationn of the problem.
The code reads the input values correctly. It takes the number of strings, the first input and then reads N integers, representing the lengths the strings.
The code first checks the given lengths the strings already sorted in ascending order and if all the lengths distinct. If this condition is sutisfied, means that each string has a different set of characters, so the minimum possible number of different characters is 1. The code prints I and exits.
If the condition step not satisfied, the code defines function called "check" check if possible have certain number of different characters in the strings. The function takes an integer X as input and returns Time if it is possible to have X different characters and False ocherwise.
The code then hased on the result of the "cheok" function. The binary search continues until the range is reduced to a single value. The code then prints the maximum value range, represents
seurch find minimum possible number of different characters. initializes range NI and iteratively updates the range
possible
Overall, the cnde comretly caleulates the minimum possible mumher of difforent characters contained in the strings and handles the case where the strings lengths.
Answer: Correct
Table 13: An ICL example of aligned retrieval decision of GTP-3.5 with EF for positive code.

---

Prompt
Please answer whether the following code is the correct implementation of the problem:
Problem: "During the reseanch on properties of the grealesi comunon divisor (GCD) of sei of numbers Ialar, a famocs muthematician, introduced brund
Code: 'import sys import muth feays.stdin
"The given correct implomentation problem hecouse follows the requitements constraints problem description.
Amswer: Correct
Please whether the following vode the correct impleneeniaiion the problem: Problem: 'During the research on propertes of the greatest common divisor (GCTD) of set of numhers, lldar, a famous mathematician, introduced brand
Code: "import import math
Jssys.sidin
Reason: "The code not correct implementation the problem because does not consider all possible combinations of paits to find the weakened
Answer:
Incorrect
correct implomentation problem: Problem: "Score: : 700 points Problem Statement There are N strings arranged row. is known that, for two adjacent strings, the string to the left
whether the following
Code: 'N int(input()
A listimoptint,nnpu (np...iputt) (split())
somed(A) and (s)(A) lo))sot(A)): peint(1)
int peintt)
checks(D):
idx [0]
Itr = [0]
if idx[-1]
adx.appendía)
lirappendrO)
for for rango(X-1)::
if [a int[tr]]= return Itf0] == for
len(trr
print(le)
Ite lnf0]
Inr hr(len(tr)-1]]
str(len((er)-2)
It Iee-tteltrr
print(Ir)
[0]
mid = (4J0] #2
([check(mid) - mid
prins(([]])"
GPT-3.5 Response
Reasoning: The givan code is not thé correct implciientationn of the problein.
The code starts reading the input values correctl. takes the number strings, N. the first input and then reads N integers, representing the lengths the strings.
The code then checks of the tist of longths, A, is already sorted ascending order and elements in are distinct. If both conditions truc, it prints and exits. However, this condition does not guarantee that the minimum possible number of different characters is being calculated correctly.
3. The code defines function, check(X), which takes an integer X input. Inside the function, it initializes two lists, idx and ltr, with initial values O. then iterates through each element, in A and checks if the last element in ids is less than a. it is. it appends to ids and appends to Itr. This part the code clear
have syntax errors.
TTee code then has nested loop, which not property indented has incorrect variable names, tries to compare elements in A clickk if they are in lexicographically increasing order, but logic incorrect.
The code has another loop that chocks longth of and prints the result accordingly. However, logic syntax part the code are incorreet.
Finally, the code has while loop that uses binary search to find the minimom possible number of different characters, However, the logic and syntax of also incomret.
part of
Overall, the code does not carrectly calculate the minimum possible mumber of different characters contained in the strings. has syntax errors, incorrect logic, incomplete implementation..
Answer: Incorrest
Table 14: An ICL example of aligned retrieval decision of GTP-3.5 with EF for negative code by CIRL.


Reviews:
[{"review_id": "odrgbUgHDn", "reviewer": "Reviewer_fqev", "summary": "", "questions": "* Why does ContraCode have lower validation loss but much higher test accuracy on Codeforces?\n* What is the relationship between code difficulty and effectiveness of augmentation?\n* The implementation of CIRL may be an obstacle to trying out the method and reproducing it – will it be made publicly available?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. \n\n**The approach is evaluated only on Python data with one code search method (GraphCodeBERT) – an advantage of lexical perturbation is the simplicity of implementation, whereas this approach seems to require a potentially complex implementation for each language. There should be some discussion around such tradeoffs**\n\nPerturbing Abstract Syntax Tree (AST) may look more complex than lexical perturbation, but straightforwardly generalizes to other languages, as AST parser (e.g. tree-sitter) easily applies to other languages for extracting a language-generic representation to perturb. We will revise to make this point more convincing and show such a generalization. See our response for reviewer 4Eqj with an additional experiment of CIRL on ruby language. \n\n**The LLM-based EF investigation is not thorough and this caveat should be clear — the prompt provides a correct and incorrect example, but does not format these the same as the instruction — for ICL, the in-context examples should be structured the same as the question. The zero-shot prompt is also grammatically incorrect: “Please answer that the following code is the correct implementation of the problem” should be “Please answer whether” — this study thus needs a caveat that it is small scale and incomplete.**\n\nWe corrected grammatical errors in prompt as suggested, but our results were not sensitive to\nsuch change: GPT-3.5 shows a higher accuracy in positive code and CIRL, and lower accuracy than random guessing (50%) in CI-Human and CIRL_RM. \n\n\n|shot | Positive Code | Negative Code (CI-Human) | Negative Code (CIRL_RM) | Negative Code (CIRL)|\n|------|---|---|---|---|\n|zero-shot | 82.86% | 34.29% | 48.57% | 100.00%|\n|ICL | 100.00% | 17.14% | 28.57% | 100.00%|\n**Updated Figure 4.**\n\nSpecifically, below is our new prompt:\n\nPlease answer whether the following code is the correct implementation of the problem:\n\nProblem: <problem description>\n\nCode: <code snippet>\n\nReasoning: <reasoning for the correctness>\n\nAnswer: <Correct or Incorrect>\n\n\nFor a correct code, few-shot examples for reasoning (<reasoning for the correctness>) were generated zero-shot using the following prompt:\n\nExplain why the following code is the correct implementation of the problem: \n\nProblem: <problem description> \n\nCode: <code snippet> \n\nReason: \n\nFor an incorrect code: \n\nExplain why the following code is not the correct implementation of the problem: \n\nProblem: <problem description> \n\nCode: <code snippet> \n\nReason:  \n\nRegarding the scale, we will extend to different datasets (e.g., other subsets of CodeNet, Codeforces) and models such as GPT-4. \n\n\n**What is the relationship between code difficulty and effectiveness of augmentation?**\n\nThough CIRL, with augmentation, significantly improves MRR scores regardless of code difficulty, CI-Human is effective particularly when code difficulty is high (about 2%+ of additional MRR gain in CodeNet 0-10 ~ 30-40, whereas  <2% of gain in CodeNet 40-50 ~ 90-100). \nThis generality over code difficulty indicates the effectiveness of augmentation.\n\n**The implementation of CIRL may be an obstacle to trying out the method and reproducing it – will it be made publicly available?**\n\nTo reduce the difficulty in reproduction, we will make all implementations publicly available.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* The approach provides an intuitive/well-motivated improvement over previous approaches to the problem\n* The approach is evaluated on multiple different benchmarks, with further breakdown by code difficulty\n* Extensive implementation details are provided (in the Appendix)", "reasons_to_reject": "* The approach is evaluated only on Python data with one code search method (GraphCodeBERT) – an advantage of lexical perturbation is the simplicity of implementation, whereas this approach seems to require a potentially complex implementation for each language. There should be some discussion around such tradeoffs and \n* The LLM-baed EF investigation is not thorough and this caveat should be clear — the prompt provide a correct and incorrect example, but does not format these the same as the instruction — for ICL, the in-context examples should be structured the same as the question. The zero-shot prompt is also grammatically incorrect: “Please answer that the following code is the correct implementation of the problem” should be “Please answer whether” — this study thus needs a caveat that it is small scale and incomplete.", "questions_to_authors": "* Why does ContraCode have lower validation loss but much higher test accuracy on Codeforces?\n* What is the relationship between code difficulty and effectiveness of augmentation?\n* The implementation of CIRL may be an obstacle to trying out the method and reproducing it – will it be made publicly available?", "paper_topic_and_main_contributions": "This work tackles the problem of code retrieval, specifically targeting the problem of distinguishing functionally correct code from incorrect code. They propose an approach called CIRL that introduces structural perturbations into code (e.g. replacing an entire node in the AST like an else block), where previous work used lexical changes (e.g. moving a semicolon). They apply this with a policy gradient-based RL formulation, noting that their approach allows for avoiding costly execution feedback while providing a larger edit than a simple lexical perturbation.\n\nThe paper evaluates on three categories of Python code datasets, building on GraphCodeBERT as a baseline. They demonstrate improvements in MRR over multiple code intervention baselines. Further analysis is conducted by examining the impact on retrievers after applying CIRL-based perturbations on existing test data. A small scale study is also conducted with GPT-3.5 to investigate the ability of LLMs to identify incorrect code.", "excitement": 3, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "* Codes -> code (code is a mass noun). Passages of code, code snippets, functions, programs…\n* Unnecessary comma examples\n    * 047 - remove comma\n    * 093 - remove comma\n    * 504 - remove comma\n    * 516 - remove comma\n* 046 - resulting -> resulting in, decision -> decisions\n* 230 - Lexical counterfactual perturbation is an existing baseline targeted for token sequences\n* 240 - \"a strategy\" and remove comma\n* Table 1 caption — fully controlled their generation -> fully controlled in their generation process\n* 515 - model decision -> model decisions\n* 520 - despite -> despite that"}}, {"review_id": "drzz68yRJw", "reviewer": "Reviewer_Xw4P", "summary": "", "questions": "A) In light of my comments above, could you provide some clarification on the motivation around functional correctness for code search?\n\nB) In light of my comments above, could you provide some clarification on why RL is needed and why a simple contrastive learning approach using the new subtree perturbation method is not sufficient?\n\nC) How does ContraCode compare to CIRL in Tables 1-4 and Figure 4? (It is only included in the first part of Table 1).\n\nD) In Tables 2-3, why are constraints placed relating to epochs, rather than using some early stopping mechanism that yields the optimal performance for each model on the validation set?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback.\n\n**I find the motivation of this work to be flawed in some ways. Namely, In Lines 119-121, the authors claim that the goal of code search is \"to find functionally correct codes for each query.\" In fact, retrieving functionally correct code is what motivates their approach based on \"execution feedback.\" However, I do not agree with this. Code search is generally defined as retrieving some code snippet that is relevant to the query. This is a retrieval task (i.e., retrieving a code snippet that already exists that is most relevant to the given query) rather than a generative one (i.e., generate a code snippet that implements the query). In a real-world setting, many times, it is unlikely that a code snippet that implements the exact same functionality that I am interested in exists. Nonetheless, a code snippet that does something similar or relevant (e.g., uses similar API calls) may be useful to me. In Lines 419-422, the authors claim that the performance drop for CodeSearchNet is because the dataset is flawed; however, I would argue that the dataset is defined for a different goal than what the authors are considering.**\n\nWe agree that the original goal of CodeSearchNet is different from our goal of functional correctness, and in some scenarios, the original goal is sufficient. It was thus not our intention to claim the dataset is flawed, but rather argue there are other scenarios, e.g., generated codes are directly executed, where an alternative goal of functional correctness is worth pursuing.\n\n**The use of \"execution feedback\" (including in the title and Figure 2) is misleading. No execution feedback signal is actually used in this work. Execution feedback is just approximated based on structural perturbations in the AST (i.e., static analysis). Based on Lines 233-238, it seems that the authors assume that any such perturbation results in a failure as execution feedback (EF = 0). In Equation 1, EF is defined in terms of whether or not the tests in a test suite pass. However, there is no guarantee that such perturbations will make the tests fail.**\n\nThough reviewer Xw4P is correct in that EF may not be 0 after perturbation, there is misunderstanding that we are assuming EF=0. We are following the convention of “pseudo-labeling”, allowing and tolerating some label noises, while our subtree replacement (Section 3.3) makes noisy labeling highly unlikely. We will clarify this point in the revised draft.\n\n**The need for having a RL-based intervention algorithm is not clear and not empirically validated. Using the same subtree perturbation method to generate hard negative examples, the authors could have considered a simple contrastive learning approach, similar to ContraCode. In fact, ContraCode performs the best on the test set for Codeforces in Table 1 (contrary to what is claimed in Lines 399-401), and ContraCode is excluded in all other tables. It is not clear whether CIRL outperforms ContraCode.**\n\nWe agree that a simple contrastive learning approach would behave similarly to RL-based intervention. This is not surprising, because our framework is similar to a contrastive objective if every c’ satisfies R_\\theta (q,c) = R_\\theta (q,c’). However, we respectfully disagree that this means RL-based framework is unnecessary—In our answer to reviewer 4Eqj, our RL-based scheduling can be replaced by a simpler curriculum learning, but RL-based approach, a principled RL approach outperforms simple heuristics. That is, the RL framework subsumes a heuristic in some setting, and also generalizes better in diverse tasks and settings.\n\n**How does ContraCode compare to CIRL in Tables 1-4 and Figure 4? (It is only included in the first part of Table 1).**\n\nCIRL outperforms ContraCode, validated in the following added evaluations on CSN, and Test time code augmentation by CIRL to CodeNet, while showing a comparable MRR score on AdvTest. \n\n\n**In Tables 2-3, why are constraints placed relating to epochs, rather than using some early stopping mechanism that yields the optimal performance for each model on the validation set?**\n\nWe are already using an early stopping mechanism yielding the optimal performance. Reported results show an increase of maximum training epoch from 2 to 10. \n\n**In Lines 425-426, it says that CIRL is applied to the test sets. However, CIRL involves training the underlying model. So does this mean the model is trained using the test sets?**\n\nOur model is NOT trained using a test set, but the perturbation proposed from ours is applied to the test set.\n\n**Lines 149-152 suggest that negative examples are always naively sampled. However, in light of ContraCode, it would be important to highlight that there is extensive work in finding hard negative examples for contrastive learning for a wide variety of retrieval tasks.**\n\nWe concur with your perspective concerning the significance of identifying challenging negative examples. In actuality, CIRL plays a similar role as\nhard negative mining, all while circumventing the need for extensive computational resources or memory usage.\nWe will clarify that there are extensive approaches for finding hard negative mining in contrastive learning in the revised draft.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The approach perturbing code snippets by manipulating AST subtrees is quite interesting and could have implications for a wide variety of code-related tasks.\n- The idea of using execution feedback (though not actually used in this paper) for code search is quite neat and novel. \n- Though not completely novel, using execution feedback as reward in RL frameworks is not as well-explored, so it was nice to see a task formulation around that, though this feedback is not actually used in this paper.\n- There are interesting code intervention baselines, particularly the CI-Human one, which might be an interesting set of results for the research community.", "reasons_to_reject": "- I find the motivation of this work to be flawed in some ways. Namely, In Lines 119-121, the authors claim that the goal of code search is \"to find functionally correct codes for each query.\" In fact, retrieving functionally correct code is what motivates their approach based on \"execution feedback.\" However, I do not agree with this. Code search is generally defined as retrieving some code snippet that is relevant to the query. This is a retrieval task (i.e., retrieving a code snippet that already exists that is most relevant to the given query) rather than a generative one (i.e., generate a code snippet that implements the query). In a real-world setting, many times, it is unlikely that a code snippet that implements the exact same functionality that I am interested in exists. Nonetheless, a code snippet that does something similar or relevant (e.g., uses similar API calls) may be useful to me.  In Lines 419-422, the authors claim that the performance drop for CodeSearchNet is because the dataset is flawed; however, I would argue that the dataset is defined for a different goal than what the authors are considering.\n- The use of \"execution feedback\" (including in the title and Figure 2) is misleading. No execution feedback signal is actually used in this work. Execution feedback is just approximated based on structural perturbations in the AST (i.e., static analysis). Based on Lines 233-238, it seems that the authors assume that any such perturbation results in a failure as execution feedback (EF = 0). In Equation 1, EF is defined in terms of whether or not the tests in a test suite pass. However, there is no guarantee that such perturbations will make the tests fail. \n- The need for having a RL-based intervention algorithm is not clear and not empirically validated. Using the same subtree perturbation method to generate hard negative examples, the authors could have considered a simple contrastive learning approach, similar to ContraCode. In fact, ContraCode performs the best on the test set for Codeforces in Table 1 (contrary to what is claimed in Lines 399-401), and ContraCode is excluded in all other tables. It is not clear whether CIRL outperforms ContraCode.", "questions_to_authors": "A) In light of my comments above, could you provide some clarification on the motivation around functional correctness for code search?\n\nB) In light of my comments above, could you provide some clarification on why RL is needed and why a simple contrastive learning approach using the new subtree perturbation method is not sufficient?\n\nC) How does ContraCode compare to CIRL in Tables 1-4 and Figure 4? (It is only included in the first part of Table 1).\n\nD) In Tables 2-3, why are constraints placed relating to epochs, rather than using some early stopping mechanism that yields the optimal performance for each model on the validation set?", "paper_topic_and_main_contributions": "This paper aims to retrieve functionally correct code for a given natural language query in code search. Oftentimes, code search models are trained with positive code snippets having high lexical overlap with the query and then random negative code snippets that are both lexically and structurally very different from the positive code snippets. For this reason, these models often learn surface features related to syntax and lexical overlap rather than features related to semantics and functionality. To address this issue, the authors use an RL-based approach to force a model to learn from hard negative examples in which subtrees of the ASTs corresponding to positive code snippets are iteratively perturbed in ways that alter the semantics and structure. They conduct experiments with three different datasets and compare against various baselines using various techniques for obtaining negative examples.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "- \"Execution-based Code Generation using Deep Reinforcement Learning\" (https://arxiv.org/abs/2301.13816)\n- \"CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning\" (https://arxiv.org/abs/2207.01780)", "Typos_Grammar_Style_and_Presentation_Improvements": "- In Lines 425-426, it says that CIRL is applied to the test sets. However, CIRL involves training the underlying model. So does this mean the model is trained using the test sets?\n- Lines 149-152 suggest that negative examples are always naively sampled. However, in light of ContraCode, it would be important to highlight that there is extensive work in finding hard negative examples for contrastive learning for a wide variety of retrieval tasks."}}, {"review_id": "lS4jdlN8U3", "reviewer": "Reviewer_4Eqj", "summary": "", "questions": "The following questions are minor questions that I think could make me clearer about the paper:\n1. Section 3.2 is quite confusing. Why could avoid computing $EF(q,c^\\prime)$? Why your proposed sub-tree replacing augmentation methods are more clever and non-trivial? \n2. In your experiments, you use intervened code snippets from ADV, PLM and HUMAN. Do you mean you directly take them as intervened code snippets instead of generating intervened code snippets by sub-tree replacement?\n3. In Table 4, what intervened code snippets do you use to test? HUMAN and sub-tree replacement intervened codes?\n4. In Table 3, I observe an MRR decrease on CSN-python. What does it mean? Does it mean that there are some wrong code snippets in CSN labeled as the true answer, and since your method could detect them hence not retrieving them, the MRR drops?\n\nOther comments:\nI think this paper has the potential to be a good work but still lacks some clarification, analysis and experiments. Besides, although I think evaluating your method on Python is enough, I strongly recommend you evaluate it on at least two other programming languages, which will make your work better.\nIf I find I misunderstand something, I will change my score after making it clear.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback.\n\n**The loop of re-generating intervened code snippets could also be considered as curriculum learning.**\n\nWe agree that at the surface-level the behavior of ours can be similar to curriculum learning, though ours, being based on an RL-based framework, outperforms such an approach (see Table A). \n\n|Method|Codeforces-valid|Codeforces-Test|CodeNet0-10| CodeNet10-20|CodeNet20-30|CodeNet30-40|\n|------|---|---|---|---|---|---|\n|Contrastive Learning w/ Simple Curriculum|86.96 |85.75 |43.86 |51.89 |55.53 |64.63|\n|CIRL|92.39|79.90|54.99 |55.98| 63.23 |66.09|\n|CIRL+CI-Human|96.74|79.02| 56.99 |57.86 |68.36 |71.04|\n\n|Method|CodeNet40-50|CodeNet50-60|CodeNet60-70|CodeNet70-80|CodeNet80-90|CodeNet90-100|\n|------|---|---|---|---|---|---|\n|Contrastive Learning w/ Simple Curriculum|72.92|77.97| 83.61 |84.94 |89.97| 93.87|\n|CIRL|78.01|80.64 |87.50 |90.81| 87.99 |98.11|\n|CIRL+CI-Human|79.32|82.44|87.75|90.94|89.79|99.06|\n**Table A. Comparison of CIRL and non-RL-based contrastive learning on Codeforces and CodeNet.**\n\n\n\n**As I mentioned in the paper summarization, the internal nature of this paper is proposing data augmentation methods. Then, there is a need to compare the proposed augmentation methods with previous works [1,2,3].**\n\nWe will report this comparison in the revised draft.\n\n**Although the authors state in the 'Limitations' that they only apply the proposed method on GraphCodeBERT, there is a need to evaluate it on other code search models since the proposed method is obviously a general augmentation approach.**\n\nWe agree with your point, and report the results of ContraCode+CIRL on CSN python and AdvTest. \nWe will add the results of ContraCode+CIRL on Codeforces and CodeNet in the revised draft. \n\n|Model|Max. Train Epochs|AdvTest|\n|------|---|---|\n|ContraCode|10|**22.2**|\n|ContraCode+CIRL|10|22.1|\n**Table B. ContraCode+CIRL on AdvTest.**\n\n|Model|Max. Train Epochs|CSN-python|\n|------|---|---|\n|ContraCode|10|59.9|\n|ContraCode+CIRL|10|**62.2**|\n**Table C. ContraCode+CIRL on CSN-python.**\n\n\n\n**In your experiments, you use intervened code snippets from ADV, PLM and HUMAN. Do you mean you directly take them as intervened code snippets instead of generating intervened code snippets by sub-tree replacement?**\n\nYour understanding is correct. \n\n**In Table 4, what intervened code snippets do you use to test? HUMAN and sub-tree replacement intervened codes?**\n\nFor the test time augmentation, we use sub-tree replacement intervened code snippets.\n\n**In Table 3, I observe an MRR decrease on CSN-python. What does it mean? Does it mean that there are some wrong code snippets in CSN labeled as the true answer, and since your method could detect them hence not retrieving them, the MRR drops?**\n\nOur conjecture is that the high lexical/structural dissimilarity between positive-negative code snippets incurs observation bias (lines 150-163) in CSN-python test set. \nThis bias can be reduced in another language with smaller biases, e.g., MRR increases on CSN-ruby (see our results Table D.)\nWe will add the discussion for this interesting phenomenon in the revised draft.\n\n**Other comments: I think this paper has the potential to be a good work but still lacks some clarification, analysis and experiments. Besides, although I think evaluating your method on Python is enough, I strongly recommend you evaluate it on at least two other programming languages, which will make your work better. If I find I misunderstand something, I will change my score after making it clear.**\n\nAgain, thanks for constructive feedback. \nThough we could not finish all languages in time for  the rebuttal, we will continue reporting new results, during discussion and revision.\n|Model|Max. Train Epochs|CSN-ruby|\n|------|---|---|\n|GraphCodeBERT|10|70.3|\n|GraphCodeBERT+CIRL|10|**72.0**|\n**Table D. CIRL on CSN-ruby**\n\nWe could address most of the requested evaluations and clarifications during the rebuttal and hope this can be reflected in your scoring.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Considering the correctness of retrieved code snippets in code search is a very interesting and novel point to me. The internal nature of this paper is actually studying data augmentation methods. However, different from previous data augmentation approaches that focus on generating different code snippets with similar looks or semantic-preserving code snippets with dissimilar looks, this paper addresses from another perspective, the correctness of the code snippets.\n2. The sub-tree replacement method for generating intervened code snippets seems quite novel.\n3. Authors conduct experiments based on recent popular LLMs, which could shed light on future works.", "reasons_to_reject": "1. The motivation for building the RL framework is not clear. As derived by the authors in Equation (4), the final policy update could be formulated as: $(EF(q,c_t)-EF(q,c_t^\\prime))\\partial \\log p_{theta}(a_t|\\hat{s_t})$. Instead of implementing an RL framework, the authors could directly optimize this loss function by just generating the intervened code snippets $c_t^\\prime$. Then, we could have both $EF(q,c_t)$ and $EF(q,c_t^\\prime)$. And we let the model $\\theta$ to decided which one is the correct answer among set $C_t$ combined with $c_t^\\prime$. The loop of re-generating intervened code snippets could also be considered as curriculum learning.\n2. As I mentioned in the paper summarization, the internal nature of this paper is proposing data augmentation methods. Then, there is a need to compare the proposed augmentation methods with previous works [1,2,3].\n3. Although the authors state in the 'Limitations' that they only apply the proposed method on GraphCodeBERT, there is a need to evaluate it on other code search models since the proposed method is obviously a general augmentation approach.\n\n[1] Ding, Yangruibo, et al. \"Towards learning (dis)-similarity of source code from program contrasts.\" arXiv preprint arXiv:2110.03868 (2021).\n\n[2] Li, Haochen, et al. \"Exploring Representation-Level Augmentation for Code Search.\" arXiv preprint arXiv:2210.12285 (2022).\n\n[3] Shi, Ensheng, et al. \"CoCoSoDa: Effective Contrastive Learning for Code Search.\" 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). IEEE, 2023.", "questions_to_authors": "The following questions are minor questions that I think could make me clearer about the paper:\n1. Section 3.2 is quite confusing. Why could avoid computing $EF(q,c^\\prime)$? Why your proposed sub-tree replacing augmentation methods are more clever and non-trivial? \n2. In your experiments, you use intervened code snippets from ADV, PLM and HUMAN. Do you mean you directly take them as intervened code snippets instead of generating intervened code snippets by sub-tree replacement?\n3. In Table 4, what intervened code snippets do you use to test? HUMAN and sub-tree replacement intervened codes?\n4. In Table 3, I observe an MRR decrease on CSN-python. What does it mean? Does it mean that there are some wrong code snippets in CSN labeled as the true answer, and since your method could detect them hence not retrieving them, the MRR drops?\n\nOther comments:\nI think this paper has the potential to be a good work but still lacks some clarification, analysis and experiments. Besides, although I think evaluating your method on Python is enough, I strongly recommend you evaluate it on at least two other programming languages, which will make your work better.\nIf I find I misunderstand something, I will change my score after making it clear.", "paper_topic_and_main_contributions": "This paper discusses the correctness of retrieved code snippets in code search. As discussed by the author, there are often seemingly correct code snippets retrieved since existing neural models often make decisions by token co-occurrence. To address this issue, the author proposes an RL framework to gradually change the code snippets to be wrong and consider it as a hard negative example. Besides, they propose a code intervention method by replacing sub-tress in ASTs. Experimental results on several datasets demonstrate the effectiveness of code interventions in code search.", "excitement": 3, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "NA", "Typos_Grammar_Style_and_Presentation_Improvements": "NA"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the task of code retrieval, specifically targeting the problem of distinguishing functionally correct code from incorrect code. While previous work used lexical changes in this context, this paper proposes an approach called CIRL that introduces iterative perturbations into subtrees within ASTs that alter the semantics and structure. The authors use an RL-based approach to force a model to learn from the hard negative examples created using such iterative perturbations. Experimental results on three Python code datasets demonstrate the effectiveness of code interventions in code search and show improvements in MRR over multiple code intervention baselines.

Reviewers consider this paper **overall technically sound** and identify the following **strengths** in this work:
1. *Approach*: Reviewer fqev highlights that the approach provides an intuitive and well-motivated improvement over previous approaches to the problem, and Reviewer Xw4P supports this view by adding that this approach could have implications for a wide variety of code-related tasks.
2. *Novelty*: In addition, reviewers Xw4P and 4Eqj highlight that the proposed idea and method are novel.
3. *Evaluation*: Reviewer fqev points out that the proposed approach is evaluated on multiple benchmarks, with further breakdown by code difficulty. In addition, Reviewer Xw4P notes that there are interesting code intervention baselines proposed in this work, which may be useful for the research community. Finally, Reviewer 4Eqj points out that authors conduct experiments based on recent popular LLMs, which could also be useful in future work.
4. *Level of detail*: Reviewer fqev mentions that extensive implementation details are provided in the Appendix.

At the same time, all reviewers have identified **a number of weaknesses** of the current submission and posed some clarifying questions for the authors. Specifically:
1. *Limitations to the proposed method*: As Reviewer fqev points out, the approach is evaluated only on Python data and with one code search method. In addition, the proposed approach may require a potentially complex implementation for each language (more so than the simpler lexical perturbation approach) but these aspects are not currently discussed in the paper. Reviewer 4Eqj agrees with this view and also suggests that the presented method be evaluated with other code search models and using other programming languages.
2. *Weaknesses related to the experiments with LLMs*: Reviewer fqev identifies several weaknesses in these experiments – for more details, see their review.
3. *Justification of certain methodological decisions*: Reviewer Xw4P poses a number of clarifying questions about implementation and methodological decisions – see their review. Reviewer 4Eqj supports this view by posing similar questions about the motivation behind using the RL framework.

In addition, all reviewers have provided further suggestions for improvements and identified some missing references. The authors did a good job addressing reviewers' feedback and acknowledged reviewers' suggestions. These will, hopefully, be reflected in the revised version of the paper.
Decision: Accept-Findings