marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Improving Code Generation by Training with Natural Language Feedback

Angelica Chen 1  Jérémy Scheurer 1 2  Tomasz Korbak 1 2 3  Jon Ander Campos 1
4  Jun Shern Chan 1 2  Samuel R. Bowman 1  Kyunghyun Cho 1 5 6  Ethan Perez 1
2 7

††footnotetext:  1New York University 2FAR AI 3University of Sussex 4HiTZ
Center, University of the Basque Country UPV/EHU 5Genentech 6CIFAR LMB
7Anthropic. Correspondence to: Angelica Chen<EMAIL_ADDRESS>Ethan
Perez<EMAIL_ADDRESS>
###### Abstract

The potential for pre-trained large language models (LLMs) to use natural
language feedback at inference time has been an exciting recent development.
We build upon this observation by formalizing an algorithm for learning from
natural language feedback at training time instead, which we call Imitation
learning from Language Feedback (ILF). ILF requires only a small amount of
human-written feedback during training and does not require the same feedback
at test time, making it both user-friendly and sample-efficient. We further
show that ILF can be seen as a form of minimizing the KL divergence to the
ground truth distribution and demonstrate a proof-of-concept on a neural
program synthesis task. We use ILF to improve a Codegen-Mono 6.1B model’s
pass@1 rate by 38% relative (and 10% absolute) on the Mostly Basic Python
Problems (MBPP) benchmark, outperforming both fine-tuning on MBPP and fine-
tuning on repaired programs written by humans. Overall, our results suggest
that learning from human-written natural language feedback is both more
effective and sample-efficient than training exclusively on demonstrations for
improving an LLM’s performance on code generation tasks.

Figure 1: An overview of imitation learning from language feedback (ILF) for
code generation. Given an initial LLM $\pi_{\theta}$, we sample programs from
$\pi_{\theta}$ that do not pass unit tests (indicated by the red X). Human
annotators write natural language feedback for the incorrect program and a
model $\pi_{\text{Refine}}$ generates a _refinement_ \- _i.e._ an improved
version of the original program that incorporates the feedback and passes the
unit tests (indicated by the green checkmark). Finally, we fine-tune
$\pi_{\theta}$ on the refinements.

##  1 Introduction

An important task for the field of software engineering is program synthesis,
the automatic generation of computer programs from an input specification
(_e.g._ a natural language task description or a set of input-output examples)
(Manna & Waldinger, 1971). Effective program synthesis can not only improve
the efficiency of software developers (Ziegler et al., 2022), but also
increase the accessibility of writing code in general. Recently, pre-trained
large language models (LLMs) have demonstrated impressive success on program
synthesis (Chen et al., 2021; Li et al., 2022; Austin et al., 2021; Nijkamp et
al., 2022; Xu et al., 2022, inter alia) but still struggle to consistently
generate correct code, even with large-scale pre-training (Chen et al., 2021).

We hypothesize that these failures can be largely attributed to modern LLM
pre-training set-ups. For instance, code pre-training datasets consist mostly
of unfiltered code scraped from the Internet, which contains a significant
number of security vulnerabilities (Kang et al., 2022) and bugs (Chen et al.,
2021). This training signal also consists exclusively of offline
demonstrations, without any signal from trial-and-error or interactive
guidance that penalizes the model’s buggy outputs. As such, we hypothesize
that supervising LLMs with explicit human-written feedback on the model’s own
outputs can be more effective at training models to produce functionally
correct code.

In particular, an intuitive and rich form of feedback to provide to LLMs is
natural language feedback. We argue that LLMs are naturally able to
incorporate written feedback, which has been shown to significantly improve a
code generation model’s pass rates when the feedback is provided at test time
(Nijkamp et al., 2022; Austin et al., 2021). In our work, we build upon this
observation by exploring the use of natural language feedback during the
training process itself, rather than just during inference. We conjecture that
such feedback provides expressive and targeted information about a code
generation model’s current failings in a sample-efficient manner. More
broadly, this approach also represents a weak version of _scalable oversight_
(Bowman et al., 2022), in that model overseers can improve a model merely by
evaluating its outputs, without manually generating new demonstrations, in a
way that takes advantage of the capabilities that are being supervised.

To train LLMs with language feedback, we propose an algorithm called Imitation
learning from Language Feedback (ILF; Algorithm 1), which extends the work of
Scheurer et al. (2022), who study the impact of learning from language
feedback on text summarization models. Scheurer et al. (2022) improves a
summarization model by training the base model on improved summaries generated
from the model’s original summaries and human-written feedback. Our work
builds upon Scheurer et al. (2022) in a number of ways: (1) by formalizing the
algorithm and generalizing it into a form that can be applied to any task (our
ILF algorithm in Section 2.2), (2) by detailing how the reward function can be
adapted for code generation, and (3) by demonstrating a proof-of-concept of
ILF for code generation.111We open-source our code and annotated data at
https://github.com/nyu-mll/ILF-for-code-generation. ILF improves the
correctness of programs generated by a baseline code generation model
$\pi_{\theta}$ by training a separate model $\pi_{\text{Refine}}$ to use
language feedback to repair the incorrect $\pi_{\theta}$-generated programs.
(We refer to the repaired programs as _refinements_.) We then improve
$\pi_{\theta}$ by fine-tuning it on the $\pi_{\text{Refine}}$-generated
refinements that pass unit tests, yielding a final improved model
$\pi_{\theta^{*}}$. This procedure may be run iteratively to continue
improving the model, which we show can be seen as minimizing the expected KL
divergence from a target ground truth distribution (Section 2).

We demonstrate a proof of concept of ILF for code generation by showing that
it improves a CodeGen-Mono 6.1B model’s pass@1 rate on the Mostly Basic Python
Problems (MBPP) benchmark (Odena et al., 2021) by 38% relative (10% absolute)
over its zero-shot performance. It also outperforms fine-tuning on the MBPP-
provided code by 64% (14% absolute, see Section 3.2). We further find that the
refinements generated during ILF do indeed leverage the human-written feedback
(Section 3.1) – when the feedback is unhelpful or irrelevant, we observe steep
drops in code correctness. The quality of the feedback is also crucial – LLM-
generated feedback yields far lower final pass rates than human-written
feedback (Section 3.3). Despite the success of our approach, we still observe
concrete limitations – for instance, $\pi_{\text{Refine}}$ is less effective
at incorporating feedback when the feedback addresses multiple bugs (Section
3.5), which suggests headroom for future work or more capable LLMs to base
$\pi_{\text{Refine}}$ on. Overall, our results – as well as our additional
results on text summarization, using a similar technique in Scheurer et al.
(2023) – suggest that human-written feedback is a powerful, information-rich
form of supervision for LLMs.

##  2 Method

Algorithm 1 Imitation learning from natural language feedback for code
generation.

1:Input: Dataset $\mathcal{D}$, initial LLM $\pi_{\theta}$, unit test
verification function Eval, LLM $\pi_{\text{Refine}}:\mathcal{V}^{*}\to[0,1]$
trained to incorporate feedback into code

2:$C\leftarrow\\{(x_{0},t,u)\,|\,x_{0}\sim\pi_{\theta_{k}}(\cdot|t),\textsc{Eval}(x_{0},t)=0,(t,u)\in\mathcal{D}\\}$

3:$C_{\text{annotated}}\leftarrow\\{(x_{0},f,t)\,|\,(x_{0},t,u)\in C\\}$
$\triangleright$ Humans write feedback $f$ for $x_{0}\in C$.

4:$R\leftarrow\\{(t,x_{1})\sim\pi_{\text{Refine}}(\cdot\,|\,t,x_{0},f)\,|\,\textsc{Eval}(x_{1},t)=1,(x_{0},f,t)\in
C_{\text{annotated}}\\}$ $\triangleright$ $\pi_{\text{Refine}}$ generates
refinements $x_{1}$ that incorporate feedback $f$ into $x_{0}$.

5:$\pi_{\theta^{*}}\leftarrow\textsc{Finetune}(\pi_{\theta},R)$

###  2.1 Preliminaries

Here, we formally describe the problem we aim to tackle, before introducing
our algorithm. Suppose we start with vocabulary $\mathcal{V}$ and a pre-
trained language model $\pi_{\theta}$ parameterized by $\theta$.
$\pi_{\theta}:\mathcal{V^{*}}\to[0,1]$ is a probability distribution over
sequences of tokens $x\in\mathcal{V}^{*}$, where $\mathcal{V}^{*}$ is the
Kleene closure of $\mathcal{V}$. We also have a dataset of tasks
$\mathcal{D}=\\{(t,u)\\}$. A task $(t,u)$ consists of a task description
$t\in\mathcal{T}$ (_e.g._ “Write a function that computes the prime
factorization of an input integer.”) and a suite
$u=\textsc{UnitTests}(t)\in\mathcal{U}$ of unit tests associated with task
$t$. Finally, let $\textsc{Eval}:\mathcal{V}^{*}\times\mathcal{T}\to\\{0,1\\}$
be a unit test verification function that indicates whether a program
$x\sim\pi_{\theta}(\cdot\,|\,t)$ passes all the unit tests in
$\textsc{UnitTests}(t)$:

$\textsc{Eval}(x,t)\coloneqq\left\\{\begin{array}[]{ll}1,&\mbox{if }x\text{
passes test suite\ }\textsc{UnitTests}(t),\\\
0,&\mbox{otherwise}\end{array}\right.$ (1)

We also define a fine-tuning function
$\textsc{Finetune}(\pi_{\theta},\mathcal{D})$ that applies a gradient-based
optimization algorithm to $\pi_{\theta}$ using the associated loss objective
calculated over dataset $\mathcal{D}$.

###  2.2 Imitation Learning From Language Feedback

Our goal is to sample a diverse set of high-quality programs
$x_{1}\sim\pi_{\theta}(\cdot|t)$ for any given task $t$ sampled from the task
distribution $p(t)$. We do so by fitting an auto-regressive LLM $\pi_{\theta}$
to approximate a ground truth distribution $\pi_{t}^{*}(x_{1})$ that assigns a
probability to $x_{1}$ that is proportional to its quality, as measured by a
reward function $R$. Fitting $\pi_{\theta}$ to approximate $\pi_{t}^{*}$ can
be seen as minimizing the expected KL divergence from $\pi_{t}^{*}$ to
$\pi_{\theta}$ over the task distribution $p(t)$:

$\min_{\theta}\underset{t\sim
p(t)}{\mathbb{E}}\left[\mathrm{KL}(\pi_{t}^{*},\pi_{\theta}(\cdot\,|\,t))\right]$
(2)

where

$\pi_{t}^{*}(x_{1})\propto\exp\left(\beta R(x_{1},t)\right)$ (3)

In this work we use the unit test verification function Eval directly as our
reward function $R$, but $R$ can also be a function of any number of other
signals, such as stack traces or compiler outputs.

Minimizing the objective in Equation 2 is equivalent to supervised learning,
_i.e._ minimizing the cross-entropy loss:

$\mathcal{L}(\theta)=-\underset{t\sim
p(t)}{\mathbb{E}}\left[\mathcal{L}_{\theta}(t)\right],$ (4)

where

$\mathcal{L}_{\theta}(t)=\sum_{x_{1}}\pi_{t}^{*}(x_{1})\log\pi_{\theta}(x_{1}|t).$
(5)

Rather than computing this loss over the exponentially large space of all
possible $x_{1}$’s, we instead use Monte-Carlo sampling over a small set of
$x_{1}$’s drawn from $\pi_{t}^{*}$. However, this is still intractable because
we cannot sample directly from $\pi_{t}^{*}$. Instead, we approximate
$\pi_{t}^{*}$ using importance sampling with a proposal distribution
$q_{t}(x_{1})$:

$\mathcal{L}_{\theta}(t)=\sum_{x_{1}}q_{t}(x_{1})\frac{\pi_{t}^{*}(x_{1})}{q_{t}(x_{1})}\log\pi_{\theta}(x_{1}|t)$
(6)

which assigns higher weights to higher quality programs $x_{1}$.

###  2.3 Proposal Distribution $q$

Intuitively, we aim to design $q_{t}$ to be as close as possible to
$\pi_{t}^{*}$, which we accomplish by incorporating pieces of natural language
feedback $f$ that give information about how to transform a low-reward program
$x_{0}$ into a higher-reward program $x_{1}$. This can be achieved by (i)
identifying a program $x_{0}\sim\pi_{\theta}(\cdot|t)$ that does not currently
pass the test suite (_i.e._ $\textsc{Eval}(x_{0},t)=0$), (ii) asking for
natural language feedback $f$ about bugs in $x_{0}$, (iii) using $f$ to
transform the original program $x_{0}$ into a _refinement_ $x_{1}$ that
incorporates the feedback and passes the test suite (_i.e._
$\textsc{Eval}(x_{1},t)=1$), and (iv) assigning higher weight to $x_{1}$.

We can formalize this procedure as follows. Let $\pi_{\psi}(x_{1}|t,x_{0},f)$
be a distribution over programs $x_{1}$ that improve $x_{0}$ by incorporating
the feedback $f$ and $p_{\mathcal{F}}(f\,|\,t,x_{0},\textsc{Eval}(x_{0},t)=0)$
be the distribution of pieces of feedback $f$ for incorrect program $x_{0}$
and task $t$. We can then define our proposal distribution as:

$\displaystyle q_{t}(x_{1})=\sum_{x_{0},f}\ $
$\displaystyle\pi_{\theta}(x_{0}|t)\times\delta_{0}\left(\textsc{Eval}(x_{0},t)\,|\,x_{0},t)\right)$
$\displaystyle\times p_{\mathcal{F}}(f|t,x_{0},\textsc{Eval}(x_{0},t)=0)$
$\displaystyle\times\pi_{\psi}(x_{1}|t,x_{0},f)$
$\displaystyle\times\delta_{1}(\textsc{Eval}(x_{1},t)\,|\,t,x_{1}),$ (7)

where $\delta_{0}$ and $\delta_{1}$ are the Dirac delta distributions centered
at 0 and 1, respectively. Then this proposal distribution is guaranteed to
place higher probability mass on higher-quality programs (in terms of unit
test pass rate) than $\pi_{\theta}$ since the term
$\delta_{1}(\textsc{Eval}(x_{1},t)\,|\,t,x_{1})$ equals 0 for incorrect
programs $x_{1}$.

We approximate sampling from $q$ by considering each of the terms in Equation
7 in order:

  1. 1.

We first sample from
$\pi_{\theta}(x_{0}|t)\times\delta_{0}\left(\textsc{Eval}(x_{0},t)\,|\,x_{0},t)\right)$
by rejection sampling from $\pi_{\theta}$. In other words, we sample programs
$x_{0}$ from $\pi_{\theta}$ for task $t$ and only keep those that fail the
test suite (_i.e._ $\textsc{Eval}(x_{0},t)=0$; step 2 of Algorithm 1).

  2. 2.

We approximate sampling from
$p_{\mathcal{F}}(f|t,x_{0},\textsc{Eval}(x_{0},t)=0)$ by having humans
annotate programs $x_{0}$ (paired with their corresponding task descriptions
$t$ and test suites $u$) with natural language feedback (step 3 of Algorithm
1).

  3. 3.

We approximate sampling from $\pi_{\psi}(x_{1}|t,x_{0},f)$ by sampling from
$\pi_{\text{Refine}}$, a model capable of generating refinements given the
task description, original programs, and human-written feedback.

  4. 4.

Finally, the term $\delta_{1}(\textsc{Eval}(x_{1},t)\,|\,t,x_{1})$ corresponds
to another filter: we only keep refined programs $x_{1}$ that pass the test
suite.

Next, we consider more concrete details of how this sampling is accomplished.

#### Training $\pi_{\text{Refine}}$

ILF assumes the availability of feedback but not necessarily of the repaired
code/refinements, for a variety of reasons. We assume that program synthesis
may be a task for which writing high-level natural language feedback is often
less laborious than performing program repair. Although writing feedback
involves identifying at a high level what is wrong with the program and how it
should be fixed, program repair may involve the additional steps of
refactoring, looking through documentation, and testing. Moreover, past work
(Austin et al., 2021; Nijkamp et al., 2022) has indicated that certain large
LLMs can proficiently incorporate the feedback at inference time, assuming
access to accurate and high-quality feedback. As such, ILF assumes access to
some model $\pi_{\text{Refine}}$ that is capable of producing a refinement
given the original program and feedback.

$\pi_{\text{Refine}}$ can take a variety of forms, but we fine-tune a pre-
trained CodeGen-Mono 6.1B model as our $\pi_{\text{Refine}}$. We create a
training dataset for $\pi_{\text{Refine}}$ by further annotating a subset of
$C_{\text{annotated}}$ with refinements $x_{1}$ that repair incorrect programs
$x_{0}$ by incorporating feedback $f$, such that $\textsc{Eval}(x_{1},t)=1$
for $(x_{0},f,t)\in C_{\text{annotated}}$. Further details of our dataset and
annotation procedure are in Section 3.

Figure 2: An example of a zero-shot LLM prompt for repairing incorrect code
based on human-written feedback.

##  3 Experiments and Results

Having described our high-level approach, we now explain the experimental
setup we use to test ILF.

#### Dataset

We train and evaluate our models on the Mostly Basic Python Problems (MBPP)
dataset (Odena et al., 2021). MBPP contains 974 Python programming tasks
designed to be solvable by entry-level coders. Each task contains a natural
language task description $t$ (_e.g._ , “Write a function to return the prime
factorization of the input.”), a gold solution, and a suite $u$ of three unit
tests. Since the task descriptions are sometimes ambiguous, we include one
unit test in the task description. The addition of the unit test helps to
specify the input and output format of each task. We hold out the remaining
unit tests for the evaluation of our generated programs.

MBPP includes a designated prompt/training/validation/test split of the
dataset, but we re-split the dataset into the following splits:

  * •

MBPPRefine: These are tasks with IDs in the range 111-310 for which CodeGen-
Mono 6.1B did not generate any correct completions. This split is used to
train $\pi_{\text{Refine}}$.

  * •

MBPPTrain: These are tasks with IDs in the range 311-974 for which Codegen-
Mono 6.1B did not generate any correct completions. This split is first used
to evaluate the correctness of refinements generated by $\pi_{\text{Refine}}$.
Then, the correct refinements in this split are used to train $\pi_{\theta}$
to obtain $\pi_{\theta^{*}}$ (step 5 in Algorithm 1).

  * •

MBPPTest: These are tasks with IDs in the range 11-110 that we use to evaluate
the final performance of $\pi_{\theta^{*}}$. Unlike the previous two splits,
we use _all_ tasks in this split, rather than only the tasks for which
CodeGen-Mono 6.1B did not originally generate correct programs for. This
allows us to better compare the baseline performance of $\pi_{\theta}$ with
that of $\pi_{\theta^{*}}$.

We use this modified split so that a larger portion of the dataset can be used
to train the final model $\pi_{\theta^{*}}$, whereas smaller portions are
allocated for training $\pi_{\text{Refine}}$ and evaluating
$\pi_{\theta^{*}}$. We do not make use of the prompt split (IDs 1-10).

#### Models

Throughout this paper, we use a pre-trained CodeGen-Mono 6.1B model (Nijkamp
et al., 2022) as our $\pi_{\theta}$. It is pre-trained sequentially on ThePile
(Gao et al., 2020), BigQuery (Nijkamp et al., 2022), and BigPython (Nijkamp et
al., 2022). We selected this model because it is open-source, can be fine-
tuned on a single $4\times 100$ A100 (80 GB) node, and demonstrated pass@k
scores comparable to Codex-12B (Chen et al., 2021; Nijkamp et al., 2022).

To implement our algorithm, we independently fine-tune two separate instances
of CodeGen-Mono 6.1B to create $\pi_{\text{Refine}}$ and the final model
$\pi_{\theta^{*}}$. We train $\pi_{\text{Refine}}$ using pairs of incorrect
programs and human-written feedback as inputs, with human-written refinements
as targets (using the format in Figure 2). In contrast, we train
$\pi_{\theta^{*}}$ using natural language task descriptions from MBPP as the
inputs and $\pi_{\text{Refine}}$-generated refinements as the targets. Further
training details are in Appendix A.1.

#### Evaluation

We evaluate all code generations in this paper using the _pass@k_ metric
introduced in Kulal et al. (2019). It estimates the rate for which $\geq$1 of
$k$ model samples passes all the unit tests. We use the empirical estimate of
this quantity from Chen et al. (2021), an unbiased estimator given by:

$\text{pass@k}\coloneqq\mathbb{E}_{\text{task}}\left[1-\frac{\binom{n-c}{k}}{\binom{n}{k}}\right]$
(8)

for $n$ total programs (where $n\geq k$) and $c$ correct programs for the
given task.

#### Human Annotation

We hire annotators via Surge AI222www.surgehq.ai to write both natural
language feedback and refinements for incorrect programs generated by CodeGen-
Mono 6.1B. For each task that CodeGen-Mono 6.1B generated no correct programs
for, we ask the workers to first select one of the incorrect programs to write
feedback and refinement for. We specify that the workers should select a
sample that seems relatively easy to correct (_i.e._ could be minimally
corrected to pass the unit tests). Then, they are asked to write feedback that
describes what is wrong with the current code and how to fix it. For the
refinement, they are asked to copy over the original code and make the
_minimum number of edits necessary_ to incorporate the feedback and pass all
the unit tests. The full set of worker instructions can be found in Appendix
A.2.

We keep all annotations for which the refinement passes all tests in the
task’s test suite, the feedback is correct (as manually verified by the
authors), and the Levenshtein edit distance between the refinement and the
original program is less than 50% of
$\max(\mathrm{len}(\text{refinement}),\mathrm{len}(\text{original program}))$.
The final dataset consists of 195 triples of (incorrect program, human-written
feedback, human-written refinement). On average, workers are paid $23 per
annotated sample and take 27 minutes/sample, with a 10th percentile of 4
minutes and a 90th percentile of 43 minutes.

Although the ILF algorithm only requires the collection of human-written
feedback for the tasks in MBPPTrain (assuming access to some
$\pi_{\text{Refine}}$ that is already fine-tuned or can generate refinements
via few-shot prompting), we collect both human-written feedback and refinement
for all splits of the data so that we can conduct further analyses of our
method. For instance, this allows us to compare fine-tuning on
$\pi_{\text{Refine}}$-generated refinements with fine-tuning on human-written
refinements. When scaled to other pairs of model and task, ILF requires new
feedback annotations, but it is possible that using ILF on one dataset will
improve the model’s abilities on another dataset for a similar task. We leave
analyses of scaling ILF across different tasks and models to future work.

Table 1: Initial zero-shot CodeGen-Mono 6.1B performance on the entire MBPP dataset. “1+ Correct” refers to the percentage of tasks for which CodeGen-Mono 6.1B generated at least one program that passed all unit tests. Metric |  Zero-Shot CodeGen-Mono 6.1B
---|---
Pass@1 |  31%
Pass@10 |  63%
1+ Correct |  67%
Table 2: Evaluations of 1-shot refinements generated by CodeGen-Mono 6.1B (before ILF) given either related or unrelated text feedback in the prompt. Feedback is provided only for tasks on which CodeGen-Mono 6.1B previously did not output any correct programs. Prompt Type | CodeGen-Mono 6.1B
---|---
Pass@1 $\uparrow$ | Pass@10 $\uparrow$
Code + feedback | 2.0% | 13.8%
Code + unrelated feedback | 0.4% | 4.0%

###  3.1 CodeGen-Mono 6.1B Incorporates Feedback

We first verify that our baseline model can use feedback to repair incorrect
code, a pre-requisite for ILF to work. We evaluate CodeGen-Mono 6.1B’s ability
to generate refinements given pairs of (incorrect code, natural language
feedback), both in a few-shot manner and after fine-tuning. Feedback is only
required for tasks for which $\pi_{\theta}$ is initially unable to produce a
correct response, so we first evaluate CodeGen-Mono 6.1B zero-shot on all of
MBPP, generating 30 programs per task with temperature 0.8. Table 1 shows the
resulting pass rates. There were 321 tasks for which zero-shot CodeGen-Mono
6.1B yielded no correct samples (from Table 1: $(100\%-67\%)\times 974\text{
tasks}\approx 321$). We then annotate one incorrect program per task with both
feedback and refinement, as described in Section 3.

#### Few-Shot Feedback Incorporation

We use the human feedback annotations to create few-shot feedback prompts,
formatted as in Figure 2. We evaluate CodeGen-Mono 6.1B’s ability to produce
refinements that incorporate the feedback and pass the unit tests. However,
producing a refinement that passes the unit tests does not guarantee that the
feedback has been incorporated; there can be multiple solutions to a
programming task, including ones that are functional but completely different
and not using the feedback to improve upon the original code. Alternatively,
the model may already be able to repair programs without feedback. Thus, we
also evaluate the pass rate after shuffling the feedback samples in the
dataset, to evaluate if the model’s ability to repair code degrades when
presented with unrelated feedback.

The results are shown in Table 2. CodeGen-Mono 6.1B’s ability to incorporate
relevant feedback on this particular set of program is low, with pass@10
reaching only 13.8%. However, the gap in accuracy between CodeGen-Mono
6.1B-generated refinements on relevant versus irrelevant feedback is
significant, with pass@10 decreasing by 71% (relative; 13.8% $\rightarrow$
4.0%), indicating that the model is indeed using the feedback.

#### Training $\pi_{\text{Refine}}$

Next, we examine whether we can improve our ability to repair programs given
feedback by fine-tuning a separate model specifically to perform this task.
Our training examples consist of triples of incorrect program, human-written
feedback, and human-written refinement. We train the model to maximize the
likelihood of the refinement given the program and feedback. The incorrect
programs were generated by CodeGen-Mono 6.1B zero-shot on MBPP tasks, and the
feedback and refinements were written by human annotators, as discussed in
Section 3. We only included tasks for which none of CodeGen-Mono 6.1B’s
generated programs were correct, yielding 44 tasks in the training dataset
(forming the split MBPPRefine) and 128 tasks in the evaluation dataset
(forming the split MBPPTrain). We asked human annotators to write refinements
of the original code that incorporated their own previously written feedback,
passed the unit tests, and made only minimal edits to the code (see Section
3). The format of the training data also matched the few-shot prompt format
(Figure 2) but without the in-context examples of refinements. We denote this
model as $\pi_{\text{Refine}}$, as described in Section 2.3.

Table 3: Pass rates of $\pi_{\text{Refine}}$-generated refinements versus zero-shot CodeGen-Mono 6.1B programs for tasks in MBPPTrain. Metric |  $\pi_{\text{Refine}}$ |  Zero-shot CodeGen-Mono 6.1B
---|---|---
Pass@1 |  19% |  0%
Pass@10 |  47% |  0%
1+ correct |  61% |  0%

Table 3 shows the pass rates for $\pi_{\text{Refine}}$ on the evaluation
dataset, which were produced by sampling 30 refinements per task with
temperature 0.8. Fine-tuning significantly improves CodeGen-Mono 6.1B’s
ability to incorporate feedback compared to 1-shot refinement, increasing pass
rates more than three-fold (2$\rightarrow$19% pass@1, 13.8$\rightarrow$47%
pass@10, from Tables 2 and 3). Furthermore, 61% of tasks had at least one
correct refinement. This is particularly significant when considering the fact
that we selected only tasks for which a non-finetuned CodeGen-Mono 6.1B model
did not originally output any correct programs for (the rightmost column in
Table 3). For the 61% of validation tasks that $\pi_{\text{Refine}}$ generated
a correct refinement for, we randomly selected one such correct program for
each task to form the training dataset for our final model $\pi_{\theta^{*}}$,
yielding a final training dataset of 78 examples.

Table 4: Final performance of $\pi_{\theta^{*}}$ on MBPPTest, compared to other ablations and baselines. All results are calculated using 30 output samples with temperature 0.8. All the methods are built on the CodeGen-Mono 6.1B model. Method | Feedback Source | Fine-Tuning Data | Pass Rates of $\pi_{\theta^{*}}$
---|---|---|---
|  |  | Pass@1 | Pass@10
ILF | Humans |  $\pi_{\text{Refine}}$ Refinements | 36% | 68%
Ablations | 1-shot InstructGPT | 1-shot InstructGPT Refinements | 19% | 55%
2-shot InstructGPT | 2-shot InstructGPT Refinements | 25% | 59%
Gold Standards | - | MBPP Gold | 22% | 63%
- | Human Refinements | 33% | 68%
Baseline (zero-shot) | - | - | 26% | 59%

###  3.2 ILF Yields Pass Rates Higher Than Fine-Tuning on Gold Data or Human-
Written Programs Alone

Given that our refinements improve over the initial programs, we now fine-tune
on the refinements to improve our code generation model. As discussed earlier,
we use the correct refinements (as evaluated by the unit tests) that
$\pi_{\text{Refine}}$ generated for its evaluation dataset as the training
dataset for $\pi_{\theta^{*}}$. Since $\pi_{\theta^{*}}$ is meant to generate
code from a natural language task description (rather than to incorporate
feedback into a refinement), the inputs of our training dataset are the MBPP
prompts and the targets are the 78 $\pi_{\text{Refine}}$-generated refinements
described in the previous section. We also compare the performance of
$\pi_{\theta}^{*}$ against that of CodeGen-Mono 6.1B evaluated in a zero-shot
manner, CodeGen-Mono 6.1B fine-tuned on the gold programs from the MBPP
dataset, and CodeGen-Mono 6.1B fine-tuned on our human-written refinements.
For all fine-tuning experiments, we train on programs corresponding to the
same set of task IDs as the ones used in $\pi_{\theta^{*}}$’s training
dataset.

Additionally, we evaluate the impact of ablating the human annotations in our
algorithm by using an LLM in place of humans to generate the feedback and
refinements (replacing steps 3 and 4 in Algorithm 1). For the LLM, we use
GPT-3.5 fine-tuned with Feedback Made Easy (FeedME; text-davinci-002 on the
OpenAI API)333Details at beta.openai.com/docs/model-index-for-researchers. We
refer to this model as InstructGPT, which is the series of OpenAI models that
FeedME belongs to (OpenAI, 2022). We use InstructGPT to generate both the
feedback and refinements on the original programs. We then fine-tune CodeGen-
Mono 6.1B on the model-generated refinements.

The results of our ILF algorithm compared to the baselines and ablations are
shown in Table 4. ILF yields the highest pass@1 and pass@10 rates, despite how
few samples of feedback and refinements we use. The pass@1 rate in particular
shows a significant increase in improvement over the zero-shot baseline,
representing a 10% absolute increase (38% relative increase). Pass@1
improvements are especially helpful for assisting with software engineering,
where it is more helpful to suggest a single correct completion rather than 10
possible completions for the user to select from.

Compared to the gold standards, ILF outperforms both fine-tuning on MBPP gold
programs and human-written refinements on the pass@1 metric, yielding 14%
absolute (64% relative) and 3% absolute (9% relative) increases in pass@1
rates, respectively. However, training on human-written refinements yielded
comparable pass@10 rates as ILF, which is unsurprising since
$\pi_{\text{Refine}}$ was trained on human-written refinements. When human-
written feedback and $\pi_{\text{Refine}}$-generated refinements are ablated
(the “Ablations” section of Table 4), ILF also outperforms training on both
1-shot and 2-shot InstructGPT-generated refinements by 17% and 11% absolute
(89% and 44% relative), respectively.

Figure 3: Histogram of the perplexities of the various training data sources,
as measured using a pre-trained CodeGen-Mono 6.1B model.

Figure 4: Training dataset size versus CodeGen-Mono 6.1B pass rates on MBPP
tasks 11-111 after fine-tuning on InstructGPT-generated refinements, versus
the performance of $\pi_{\theta^{*}}$ (the model produced by our approach). X
marks the performance of $\pi_{\theta^{*}}$, whereas the solid lines plot the
performance of CodeGen-Mono 6.1B after fine-tuning on correct refinements
generated by InstructGPT, using feedback also generated by InstructGPT. The
dashed line indicates the zero-shot pass rate of a pre-trained CodeGen-Mono
6.1B model.

#### Analysis of Training Data Sources

However, we also note the surprising fact that merely training on a small
sample of the MBPP gold programs did not make a significant difference in
accuracy over zero-shot inference. We speculate that the gold programs from
the MBPP dataset may be somewhat out-of-distribution for CodeGen-Mono 6.1B. To
test this hypothesis, we computed the perplexity of the MBPP gold programs,
the $\pi_{\text{Refine}}$-generated refinements, and the human-written
refinements using the pre-trained CodeGen-Mono 6.1B model. The results are
shown in Figure 3. While the distributions of all three data sources look
similar, the MBPP dataset contains more high-perplexity programs (_i.e._
programs with perplexity $\geq 10^{2}$) than either the
$\pi_{\text{Refine}}$-generated refinements or the human-written refinements.
As a result, it is likely easier for CodeGen-Mono 6.1B to learn from the
latter two datasets, since they are closer to CodeGen-Mono 6.1B’s original
distribution while still being functionally correct.

Furthermore, ILF is particularly useful for settings where large amounts of
gold code are not available. In this setting, ILF can be thought of as a
method of not only generating more training data, but training data that is
closer to the model’s original outputs in data representation space and that
specifically repairs the kinds of bugs that the original model generates. As a
result, fine-tuning the model on $\pi_{\text{Refine}}$-generated refinements
does not require adjusting the weights as much as fine-tuning the model on the
MBPP gold programs would, even though both training datasets contain the same
number of functionally correct programs.

###  3.3 Scaling Up Model Feedback Does Not Offer the Same Benefits As Human
Feedback

Since high quality human feedback can be expensive to collect, we also
evaluated how much model feedback might yield the same benefit as our sample
of human-written feedback. To do so, we randomly select $k$ tasks from the set
of MBPP tasks for which CodeGen-Mono 6.1B did not originally output a correct
answer, and prompt InstructGPT to generate both the feedback and the
refinement. We then evaluate the refinements for correctness and train
CodeGen-Mono 6.1B on the correct refinements. We use $k\in\\{50,100,200\\}$
and generate 30 output samples at temperature 0.8 for all stages of the
experiment. We are limited to these $k$ values due to the small number of
tasks we have in MBPPTrain, but future work may investigate scaling up these
experiments by using larger datasets or automatically generating new tasks and
unit tests for the training dataset. Further training details are listed in
Appendix A.1.

The results are shown in Figure 4. Although increasing the quantity of
InstructGPT-generated feedback offers modest improvements in pass rates, these
improvements do not yield pass rates as high as those of $\pi_{\theta^{*}}$,
even though $\pi_{\theta^{*}}$ uses only a total of 122 pieces of feedback
throughout its training process (44 for training $\pi_{\text{Refine}}$ and 78
for generating refinements to train $\pi_{\theta^{*}}$ on). However, as pre-
trained large language models continue to improve dramatically in quality, we
expect that this gap between human- and model-written feedback will
increasingly narrow.

Table 5: The proportion of the feedback that addressed each type of bug, for feedback sourced from humans and InstructGPT. Each sample of feedback can be tagged with multiple categories, so the quantities in each column do not necessarily add up to 100%. Feedback Category | % of Feedback
---|---
Human | InstructGPT
Logic | 30% | 46%
Formatting | 36% | 14%
Missing step | 10% | 6%
Algebra | 10% | 8%
Recursion | 4% | 14%
Regex | 6% | 6%
Function semantics | 2% | 4%
Dynamic programming | 2% | 0%
Extra step | 0% | 12%
No feedback needed | 0% | 14%
Unrelated | 0% | 8%
Figure 5: The number of bugs addressed in the feedback versus the pass rate of $\pi_{\text{Refine}}$’s refinements. Table 6: Descriptive statistics for the human- versus InstructGPT-generated feedback. The * indicates that the metric was computed on the random sample of 50 that we manually inspected, whereas the other metrics are computed from the full dataset. | Source of Feedback
---|---
|  Human |  InstructGPT
Avg. num. of bugs addressed* |  1.8 |  1.1
Avg. num. of words |  $68.9\pm 48.2$ |  $24.2\pm 28.6$

###  3.4 Human Feedback Is More Informative Than InstructGPT Feedback

To better understand why human feedback produced greater improvements in pass
rate than InstructGPT feedback, we randomly selected 50 samples of feedback
for each source (_i.e._ human or InstructGPT) and annotated the number and
types of bugs that each feedback sample addressed. The results are shown in
Tables 5 and 6. We observed that InstructGPT often gave no feedback (_e.g._
“The code is correct” or “Great job!”), provided feedback that was irrelevant
or incorrect, or restated the task description instead of addressing what
should be repaired about the code. Despite this, InstructGPT’s refinements
were often correct even if the feedback itself wasn’t. Human-written feedback
addressed more bugs on average and never gave irrelevant feedback. We provide
further examples of the differences between human and InstructGPT feedback in
Appendix A.3.

###  3.5 $\pi_{\text{Refine}}$ Struggles To Incorporate Feedback Addressing
Many Bugs

Lastly, we explored whether the number of bugs addressed in the feedback
affected $\pi_{\text{Refine}}$’s ability to repair the original code sample.
The results are shown in Figure 5. The greater the number of bugs addressed,
the lower the average pass rate of $\pi_{\text{Refine}}$’s refinements. This
suggests that a promising direction for future work might consist of
automatically decomposing the feedback into multiple steps and having
$\pi_{\text{Refine}}$ incorporate the feedback one step at a time. Indeed,
Nijkamp et al. (2022) show that the CodeGen models are often more effective at
following instructions when the instructions are given across multiple turns,
and recent Chain-of-Thought work (Wei et al., 2022) illustrates a similar
prompting technique.

##  4 Related Work

#### LLMs for Program Synthesis

Our work builds on a large body of literature that explores the use of pre-
trained LLMs for neural program synthesis. Many general purpose LLMs, although
not pre-trained specifically for code generation, have demonstrated impressive
proficiency at solving code challenges since they are pre-trained on large
corpora of text such as The Pile (Gao et al., 2020) that contain a small
percentage of code content (Austin et al., 2021; Wang & Komatsuzaki, 2021;
Black et al., 2022; Nijkamp et al., 2022). Yet other recent LLMs for program
synthesis are trained on solely source code files (Wang et al., 2021; Zan et
al., 2022; Li et al., 2022; Xu et al., 2022), or on both text and source code
documents – sometimes either in succession (Chen et al., 2021; Nijkamp et al.,
2022; Bai et al., 2022a), in a mixed corpus (Workshop et al., 2022), or on
mixed natural language-programming language documents (Feng et al., 2020).

#### Learning from Human Feedback

Our algorithm is inspired by a number of past works that have trained models
to learn from feedback. A common technique is reinforcement learning from
human feedback (RLHF Ziegler et al., 2019; Stiennon et al., 2020; Ouyang et
al., 2022), which trains models to satisfy human preferences. However, our
algorithm is closer to works that use natural language feedback, rather than
comparisons between different choices. Elgohary et al. (2020); Austin et al.
(2021); Nijkamp et al. (2022) all demonstrate that code LLM performance
generally improves when prompted with natural language feedback, though
Nijkamp et al. (2022) observes that the feedback is more effective when it is
given one step at a time. Our work differs from these in that ILF learns from
the feedback at training time, not at inference time.

Bai et al. (2022a) also uses natural language feedback during the training
process, but as part of an RLHF algorithm instead where the feedback is used
to solicit different responses from the digital assistant, the responses are
ranked by crowdworkers, and the rankings are used to train the preference
model. However, they note that this form of learning from natural language
feedback does not measurably improve their code generation model more than
simply prompting.

Outside of program synthesis, we show in our other work (Scheurer et al.,
2023) that ILF is also effective for text summarization. In addition to re-
formulating the reward function $R(\cdot)$ for summarization, Scheurer et al.
(2023) additionally demonstrates that an instruction-finetuned LLM can
evaluate its own outputs and select the best one. Similar to our results on
code generation, Scheurer et al. (2023) shows that ILF outperforms all
supervised fine-tuning baselines on text summarization. This aligns with
numerous other works that have explored supervision via natural language in
other ways, such as via explanations (Camburu et al., 2018; Hase & Bansal,
2021; Pruthi et al., 2021; Lampinen et al., 2022, inter alia) and as part of
RL systems (Fidler et al., 2017; Luketina et al., 2019; Lin et al., 2020,
inter alia).

##  5 Conclusion

We have shown that ILF can significantly improve the quality of a code
generation model, even with just a small sample of human-written feedback and
refinements. This approach is theoretically justified as minimizing the
expected KL divergence between $\pi_{\theta}$ and a target ground-truth
distribution, where we acquire signal from the latter via human-written
natural language feedback.

This approach is also appealing because it is not model-specific (in the sense
that ILF can be used with any type of base model $\pi_{\theta}$, assuming the
existence of a sufficiently capable LLM to act as $\pi_{\text{Refine}}$), and
can be conducted in multiple rounds to continuously improve the model.
Furthermore, it is notable that our approach generates training data that is
not only correct, but targets the specific kinds of bugs that the model is
likely to output. In essence, it provides an _online_ training signal that is
missing from the offline pre-training set-up of modern LLMs. Our approach is
also remarkably sample-efficient, yielding 38% and 64% relative increases in
pass@1 rate over the zero-shot baseline and fine-tuning on MBPP data, despite
fine-tuning on only 78 examples.

Our work opens up multiple avenues for promising future work. For instance,
ILF can be applied iteratively over the course of multiple rounds whenever new
information arrives (_e.g._ new Python syntax) or new bugs are discovered. As
the pace of progress of modern LLM research continues to accelerate, it may
soon be feasible to partially or fully automate the generation of natural
language feedback (similar to ‘RL from AI feedback’ (RLAIF; Bai et al., 2022b)
and our experiments in Section 3.3), greatly reducing both the time and cost
necessary for collecting feedback. This direction of work is also particularly
appealing because the learning signal is _process-based_ rather than outcome-
based, which has been shown to mitigate reward hacking and improve the
correctness of intermediate reasoning steps (Uesato et al., 2022). Although
further work is required to extend our method, ILF represents an exciting step
forward in training LLMs with feedback that is rich, interactive, and sample-
efficient.

## Acknowledgements

We are grateful to Nitarshan Rajkumar, Jason Phang, Nat McAleese, Geoffrey
Irving, Jeff Wu, Jan Leike, Cathy Yeh, William Saunders, Jonathan Ward, Daniel
Ziegler, Seraphina Nix, Quintin Pope, Kay Kozaronek, Peter Hase, Talia Ringer,
Asa Cooper Stickland, Jacob Pfau, David Lindner, Lennart Heim, Kath Lumpante,
and Pablo Morena for helpful discussions and feedback about the design and
implementation of this work. We are additionally thankful to Scott Heiner and
Edwin Chen for extensive help with setting up our human annotation workflow
and interface. EP thanks the National Science Foundation and Open Philanthropy
for fellowship support. JAC is supported by a doctoral grant from the Spanish
MECD. AC, SB, and KC are supported by National Science Foundation Awards
1922658 and 2046556. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation. KC is
additionally supported by 42dot, Hyundai Motor Company (under the project
Uncertainty in Neural Sequence Modeling) and the Samsung Advanced Institute of
Technology (under the project Next Generation Deep Learning: From Pattern
Recognition to AI). This project has also benefited from financial support to
SB by Eric and Wendy Schmidt (made by recommendation of the Schmidt Futures
program), Open Philanthropy, and Apple. We also thank the NYU High-Performance
Computing Center for in-kind support and OpenAI for providing access to and
credits for their models via the API Academic Access Program.

## References

  * Austin et al. (2021) Austin, J., Odena, A., Nye, M. I., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C. J., Terry, M., Le, Q. V., and Sutton, C.  Program synthesis with large language models, 2021.  URL https://arxiv.org/abs/2108.07732.
  * Bai et al. (2022a) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T. J., Joseph, N., Kadavath, S., Kernion, J., Conerly, T., El-Showk, S., Elhage, N., Hatfield-Dodds, Z., Hernandez, D., Hume, T., Johnston, S., Kravec, S., Lovitt, L., Nanda, N., Olsson, C., Amodei, D., Brown, T. B., Clark, J., McCandlish, S., Olah, C., Mann, B., and Kaplan, J.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _ArXiv_ , abs/2204.05862, 2022a.
  * Bai et al. (2022b) Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., Chen, C., Olsson, C., Olah, C., Hernandez, D., Drain, D., Ganguli, D., Li, D., Tran-Johnson, E., Perez, E., Kerr, J., Mueller, J., Ladish, J., Landau, J., Ndousse, K., Lukosuite, K., Lovitt, L., Sellitto, M., Elhage, N., Schiefer, N., Mercado, N., DasSarma, N., Lasenby, R., Larson, R., Ringer, S., Johnston, S., Kravec, S., Showk, S. E., Fort, S., Lanham, T., Telleen-Lawton, T., Conerly, T., Henighan, T., Hume, T., Bowman, S. R., Hatfield-Dodds, Z., Mann, B., Amodei, D., Joseph, N., McCandlish, S., Brown, T., and Kaplan, J.  Constitutional ai: Harmlessness from ai feedback, 2022b.
  * Black et al. (2022) Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U. S., Purohit, S., Reynolds, L., Tow, J., Wang, B., and Weinbach, S.  GPT-NeoX-20B: An open-source autoregressive language model.  In _Proceedings of the ACL Workshop on Challenges & Perspectives in Creating Large Language Models_, 2022.  URL https://arxiv.org/abs/2204.06745.
  * Bowman et al. (2022) Bowman, S. R., Hyun, J., Perez, E., Chen, E., Pettit, C., Heiner, S., Lukošiūtė, K., Askell, A., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., Olah, C., Amodei, D., Amodei, D., Drain, D., Li, D., Tran-Johnson, E., Kernion, J., Kerr, J., Mueller, J., Ladish, J., Landau, J., Ndousse, K., Lovitt, L., Elhage, N., Schiefer, N., Joseph, N., Mercado, N., DasSarma, N., Larson, R., McCandlish, S., Kundu, S., Johnston, S., Kravec, S., Showk, S. E., Fort, S., Telleen-Lawton, T., Brown, T., Henighan, T., Hume, T., Bai, Y., Hatfield-Dodds, Z., Mann, B., and Kaplan, J.  Measuring progress on scalable oversight for large language models.  _ArXiv_ , abs/2211.03540, 2022.
  * Camburu et al. (2018) Camburu, O.-M., Rocktäschel, T., Lukasiewicz, T., and Blunsom, P.  e-snli: Natural language inference with natural language explanations.  _Advances in Neural Information Processing Systems_ , 31, 2018.  URL https://arxiv.org/pdf/1812.01193.pdf.
  * Chen et al. (2021) Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavarian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert-Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saunders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., McGrew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W.  Evaluating large language models trained on code, 2021.  URL https://arxiv.org/abs/2107.03374.
  * Elgohary et al. (2020) Elgohary, A., Hosseini, S., and Hassan Awadallah, A.  Speak to your parser: Interactive text-to-SQL with natural language feedback.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pp. 2065–2077, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.187.  URL https://aclanthology.org/2020.acl-main.187.
  * Feng et al. (2020) Feng, Z., Guo, D., Tang, D., Duan, N., Feng, X., Gong, M., Shou, L., Qin, B., Liu, T., Jiang, D., and Zhou, M.  CodeBERT: A pre-trained model for programming and natural languages.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 1536–1547, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.findings-emnlp.139.  URL https://aclanthology.org/2020.findings-emnlp.139.
  * Fidler et al. (2017) Fidler, S. et al.  Teaching machines to describe images with natural language feedback.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Gao et al. (2020) Gao, L., Biderman, S., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., Presser, S., and Leahy, C.  The Pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_ , 2020.
  * Hase & Bansal (2021) Hase, P. and Bansal, M.  When can models learn from explanations? a formal framework for understanding the roles of explanation data.  _arXiv preprint arXiv:2102.02201_ , 2021.  URL https://arxiv.org/pdf/2102.02201.pdf.
  * Kang et al. (2022) Kang, S., Yoon, J., and Yoo, S.  Large language models are few-shot testers: Exploring llm-based general bug reproduction, 2022.  URL https://arxiv.org/abs/2209.11515.
  * Kulal et al. (2019) Kulal, S., Pasupat, P., Chandra, K., Lee, M., Padon, O., Aiken, A., and Liang, P. S.  Spoc: Search-based pseudocode to code.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/7298332f04ac004a0ca44cc69ecf6f6b-Paper.pdf.
  * Lampinen et al. (2022) Lampinen, A. K., Dasgupta, I., Chan, S. C., Matthewson, K., Tessler, M. H., Creswell, A., McClelland, J. L., Wang, J. X., and Hill, F.  Can language models learn from explanations in context?  _arXiv preprint arXiv:2204.02329_ , 2022.
  * Lhoest et al. (2021) Lhoest, Q., Villanova del Moral, A., Jernite, Y., Thakur, A., von Platen, P., Patil, S., Chaumond, J., Drame, M., Plu, J., Tunstall, L., Davison, J., Šaško, M., Chhablani, G., Malik, B., Brandeis, S., Le Scao, T., Sanh, V., Xu, C., Patry, N., McMillan-Major, A., Schmid, P., Gugger, S., Delangue, C., Matussière, T., Debut, L., Bekman, S., Cistac, P., Goehringer, T., Mustar, V., Lagunas, F., Rush, A., and Wolf, T.  Datasets: A community library for natural language processing.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 175–184, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  URL https://aclanthology.org/2021.emnlp-demo.21.
  * Li et al. (2022) Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Lago, A. D., Hubert, T., Choy, P., de Masson d’Autume, C., Babuschkin, I., Chen, X., Huang, P.-S., Welbl, J., Gowal, S., Cherepanov, A., Molloy, J., Mankowitz, D. J., Robson, E. S., Kohli, P., de Freitas, N., Kavukcuoglu, K., and Vinyals, O.  Competition-level code generation with alphacode.  _Science_ , 378(6624):1092–1097, 2022.  doi: 10.1126/science.abq1158.  URL https://www.science.org/doi/abs/10.1126/science.abq1158.
  * Lin et al. (2020) Lin, J., Ma, Z., Gomez, R., Nakamura, K., He, B., and Li, G.  A review on interactive reinforcement learning from human social feedback.  _IEEE Access_ , 8:120757–120765, 2020.  doi: 10.1109/ACCESS.2020.3006254.
  * Luketina et al. (2019) Luketina, J., Nardelli, N., Farquhar, G., Foerster, J., Andreas, J., Grefenstette, E., Whiteson, S., and Rocktäschel, T.  A survey of reinforcement learning informed by natural language.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , pp. 6309–6317. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.  doi: 10.24963/ijcai.2019/880.  URL https://doi.org/10.24963/ijcai.2019/880.
  * Manna & Waldinger (1971) Manna, Z. and Waldinger, R. J.  Toward automatic program synthesis.  _Commun. ACM_ , 14(3):151–165, mar 1971.  ISSN 0001-0782.  doi: 10.1145/362566.362568.  URL https://doi.org/10.1145/362566.362568.
  * Nijkamp et al. (2022) Nijkamp, E., Pang, B., Hayashi, H., Tu, L., Wang, H., Zhou, Y., Savarese, S., and Xiong, C.  Codegen: An open large language model for code with multi-turn program synthesis.  _arXiv preprint_ , 2022.
  * Odena et al. (2021) Odena, A., Sutton, C., Dohan, D. M., Jiang, E., Michalewski, H., Austin, J., Bosma, M. P., Nye, M., Terry, M., and Le, Q. V.  Program synthesis with large language models.  In _n/a_ , pp. n/a, n/a, 2021.  n/a.
  * OpenAI (2022) OpenAI.  Model index for researchers, 2022.  URL https://platform.openai.com/docs/model-index-for-researchers.
  * Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R.  Training language models to follow instructions with human feedback.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=TG8KACxEON.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Pruthi et al. (2021) Pruthi, D., Bansal, R., Dhingra, B., Soares, L. B., Collins, M., Lipton, Z. C., Neubig, G., and Cohen, W. W.  Evaluating Explanations: How much do explanations from the teacher aid students?, 2021.
  * Scheurer et al. (2022) Scheurer, J., Campos, J. A., Chan, J. S., Chen, A., Cho, K., and Perez, E.  Training language models with language feedback.  _ACL Workshop on Learning with Natural Language Supervision_ , 2022\.  URL https://arxiv.org/abs/2204.14146.
  * Scheurer et al. (2023) Scheurer, J., Campos, J. A., Korbak, T., Chan, J. S., Chen, A., Cho, K., and Perez, E.  Training language models with language feedback at scale.  _Preprint_ , 2023.  URL https://drive.google.com/file/d/1tryv10CABT_FOF9Sn2OaWvfwqXF6iIec/view?usp=share_link.
  * Stiennon et al. (2020) Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F.  Learning to summarize with human feedback.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 3008–3021. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1f89885d556929e98d3ef9b86448f951-Paper.pdf.
  * Uesato et al. (2022) Uesato, J., Kushman, N., Kumar, R., Song, F., Siegel, N., Wang, L., Creswell, A., Irving, G., and Higgins, I.  Solving math word problems with process- and outcome-based feedback, 2022\.
  * Wang & Komatsuzaki (2021) Wang, B. and Komatsuzaki, A.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax, May 2021.
  * Wang et al. (2021) Wang, Y., Wang, W., Joty, S., and Hoi, S. C.  Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021_ , 2021.
  * Wei et al. (2022) Wei, J., Wang, X., Schuurmans, D., Bosma, M., brian ichter, Xia, F., Chi, E. H., Le, Q. V., and Zhou, D.  Chain of thought prompting elicits reasoning in large language models.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=_VjQlMeSB_J.
  * Wolf et al. (2020) Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Scao, T. L., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. M.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, October 2020. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * Workshop et al. (2022) Workshop, B., :, Scao, T. L., Fan, A., Akiki, C., Pavlick, E., Ilić, S., Hesslow, D., Castagné, R., Luccioni, A. S., Yvon, F., Gallé, M., Tow, J., Rush, A. M., Biderman, S., Webson, A., Ammanamanchi, P. S., Wang, T., Sagot, B., Muennighoff, N., del Moral, A. V., Ruwase, O., Bawden, R., Bekman, S., McMillan-Major, A., Beltagy, I., Nguyen, H., Saulnier, L., Tan, S., Suarez, P. O., Sanh, V., Laurençon, H., Jernite, Y., Launay, J., Mitchell, M., Raffel, C., Gokaslan, A., Simhi, A., Soroa, A., Aji, A. F., Alfassy, A., Rogers, A., Nitzav, A. K., Xu, C., Mou, C., Emezue, C., Klamm, C., Leong, C., van Strien, D., Adelani, D. I., Radev, D., Ponferrada, E. G., Levkovizh, E., Kim, E., Natan, E. B., De Toni, F., Dupont, G., Kruszewski, G., Pistilli, G., Elsahar, H., Benyamina, H., Tran, H., Yu, I., Abdulmumin, I., Johnson, I., Gonzalez-Dios, I., de la Rosa, J., Chim, J., Dodge, J., Zhu, J., Chang, J., Frohberg, J., Tobing, J., Bhattacharjee, J., Almubarak, K., Chen, K., Lo, K., Von Werra, L., Weber, L., Phan, L., allal, L. B., Tanguy, L., Dey, M., Muñoz, M. R., Masoud, M., Grandury, M., Šaško, M., Huang, M., Coavoux, M., Singh, M., Jiang, M. T.-J., Vu, M. C., Jauhar, M. A., Ghaleb, M., Subramani, N., Kassner, N., Khamis, N., Nguyen, O., Espejel, O., de Gibert, O., Villegas, P., Henderson, P., Colombo, P., Amuok, P., Lhoest, Q., Harliman, R., Bommasani, R., López, R. L., Ribeiro, R., Osei, S., Pyysalo, S., Nagel, S., Bose, S., Muhammad, S. H., Sharma, S., Longpre, S., Nikpoor, S., Silberberg, S., Pai, S., Zink, S., Torrent, T. T., Schick, T., Thrush, T., Danchev, V., Nikoulina, V., Laippala, V., Lepercq, V., Prabhu, V., Alyafeai, Z., Talat, Z., Raja, A., Heinzerling, B., Si, C., Taşar, D. E., Salesky, E., Mielke, S. J., Lee, W. Y., Sharma, A., Santilli, A., Chaffin, A., Stiegler, A., Datta, D., Szczechla, E., Chhablani, G., Wang, H., Pandey, H., Strobelt, H., Fries, J. A., Rozen, J., Gao, L., Sutawika, L., Bari, M. S., Al-shaibani, M. S., Manica, M., Nayak, N., Teehan, R., Albanie, S., Shen, S., Ben-David, S., Bach, S. H., Kim, T., Bers, T., Fevry, T., Neeraj, T., Thakker, U., Raunak, V., Tang, X., Yong, Z.-X., Sun, Z., Brody, S., Uri, Y., Tojarieh, H., Roberts, A., Chung, H. W., Tae, J., Phang, J., Press, O., Li, C., Narayanan, D., Bourfoune, H., Casper, J., Rasley, J., Ryabinin, M., Mishra, M., Zhang, M., Shoeybi, M., Peyrounette, M., Patry, N., Tazi, N., Sanseviero, O., von Platen, P., Cornette, P., Lavallée, P. F., Lacroix, R., Rajbhandari, S., Gandhi, S., Smith, S., Requena, S., Patil, S., Dettmers, T., Baruwa, A., Singh, A., Cheveleva, A., Ligozat, A.-L., Subramonian, A., Névéol, A., Lovering, C., Garrette, D., Tunuguntla, D., Reiter, E., Taktasheva, E., Voloshina, E., Bogdanov, E., Winata, G. I., Schoelkopf, H., Kalo, J.-C., Novikova, J., Forde, J. Z., Clive, J., Kasai, J., Kawamura, K., Hazan, L., Carpuat, M., Clinciu, M., Kim, N., Cheng, N., Serikov, O., Antverg, O., van der Wal, O., Zhang, R., Zhang, R., Gehrmann, S., Mirkin, S., Pais, S., Shavrina, T., Scialom, T., Yun, T., Limisiewicz, T., Rieser, V., Protasov, V., Mikhailov, V., Pruksachatkun, Y., Belinkov, Y., Bamberger, Z., Kasner, Z., Rueda, A., Pestana, A., Feizpour, A., Khan, A., Faranak, A., Santos, A., Hevia, A., Unldreaj, A., Aghagol, A., Abdollahi, A., Tammour, A., HajiHosseini, A., Behroozi, B., Ajibade, B., Saxena, B., Ferrandis, C. M., Contractor, D., Lansky, D., David, D., Kiela, D., Nguyen, D. A., Tan, E., Baylor, E., Ozoani, E., Mirza, F., Ononiwu, F., Rezanejad, H., Jones, H., Bhattacharya, I., Solaiman, I., Sedenko, I., Nejadgholi, I., Passmore, J., Seltzer, J., Sanz, J. B., Dutra, L., Samagaio, M., Elbadri, M., Mieskes, M., Gerchick, M., Akinlolu, M., McKenna, M., Qiu, M., Ghauri, M., Burynok, M., Abrar, N., Rajani, N., Elkott, N., Fahmy, N., Samuel, O., An, R., Kromann, R., Hao, R., Alizadeh, S., Shubber, S., Wang, S., Roy, S., Viguier, S., Le, T., Oyebade, T., Le, T., Yang, Y., Nguyen, Z., Kashyap, A. R., Palasciano, A., Callahan, A., Shukla, A., Miranda-Escalada, A., Singh, A., Beilharz, B., Wang, B., Brito, C., Zhou, C., Jain, C., Xu, C., Fourrier, C., Periñán, D. L., Molano, D., Yu, D., Manjavacas, E., Barth, F., Fuhrimann, F., Altay, G., Bayrak, G., Burns, G., Vrabec, H. U., Bello, I., Dash, I., Kang, J., Giorgi, J., Golde, J., Posada, J. D., Sivaraman, K. R., Bulchandani, L., Liu, L., Shinzato, L., de Bykhovetz, M. H., Takeuchi, M., Pàmies, M., Castillo, M. A., Nezhurina, M., Sänger, M., Samwald, M., Cullan, M., Weinberg, M., De Wolf, M., Mihaljcic, M., Liu, M., Freidank, M., Kang, M., Seelam, N., Dahlberg, N., Broad, N. M., Muellner, N., Fung, P., Haller, P., Chandrasekhar, R., Eisenberg, R., Martin, R., Canalli, R., Su, R., Su, R., Cahyawijaya, S., Garda, S., Deshmukh, S. S., Mishra, S., Kiblawi, S., Ott, S., Sang-aroonsiri, S., Kumar, S., Schweter, S., Bharati, S., Laud, T., Gigant, T., Kainuma, T., Kusa, W., Labrak, Y., Bajaj, Y. S., Venkatraman, Y., Xu, Y., Xu, Y., Xu, Y., Tan, Z., Xie, Z., Ye, Z., Bras, M., Belkada, Y., and Wolf, T.  Bloom: A 176b-parameter open-access multilingual language model, 2022\.  URL https://arxiv.org/abs/2211.05100.
  * Xu et al. (2022) Xu, F. F., Alon, U., Neubig, G., and Hellendoorn, V. J.  A systematic evaluation of large language models of code.  In _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_ , MAPS 2022, pp. 1–10, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392730.  doi: 10.1145/3520312.3534862.  URL https://doi.org/10.1145/3520312.3534862.
  * Zan et al. (2022) Zan, D., Chen, B., Yang, D., Lin, Z., Kim, M., Guan, B., Wang, Y., Chen, W., and Lou, J.-G.  CERT: Continual pre-training on sketches for library-oriented code generation.  In _The 2022 International Joint Conference on Artificial Intelligence_ , 2022.
  * Ziegler et al. (2022) Ziegler, A., Kalliamvakou, E., Li, X. A., Rice, A., Rifkin, D., Simister, S., Sittampalam, G., and Aftandilian, E.  Productivity assessment of neural code completion.  In _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_ , MAPS 2022, pp. 21–29, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392730.  doi: 10.1145/3520312.3534864.  URL https://doi.org/10.1145/3520312.3534864.
  * Ziegler et al. (2019) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G.  Fine-tuning language models from human preferences.  _arXiv preprint arXiv:1909.08593_ , 2019.  URL https://arxiv.org/abs/1909.08593.

##  Appendix A Appendix

###  A.1 Training Details

For the experiments in Section 3.2, we run a hyperparameter sweep for all
methods except for ILF. The hyperparameter value ranges that we sweep include
learning rate $\in\\{1.0^{-6},5.0^{-6},1.0^{-5}\\}$, batch size
$\in\\{32,64,128\\}$, and number of epochs $\in\\{1,2,5\\}$. The tasks for the
training and validation datasets are from MBPPTrain and MBPPRefine,
respectively, while the programs are sourced from the method (_e.g._
InstructGPT, MBPP, human-written, or zero-shot CodeGen-Mono 6.1B). For ILF, we
use the best hyperparameters obtained for the sweep over MBPP programs instead
of sweeping over ILF-generated programs, since the tasks in MBPPRefine are
already used to train $\pi_{\text{Refine}}$. All pass rates reported in Table
4 are obtained by evaluating each method on MBPPTest using the best
hyperparameters found during the sweep on MBPPRefine.

For the experiments in Section 3.3, we separately tune hyperparameters for
each size of dataset. As in our other experiments, we train and validate using
the tasks from MBPPTrain and MBPPRefine, respectively, coupled with the
refinements generated by InstructGPT that pass the unit test suites. We sweep
the same hyperparameter value ranges as the experiments in the previous
section (_i.e._ learning rate $\in\\{1.0^{-6},5.0^{-6},1.0^{-5}\\}$, batch
size $\in\\{32,64,128\\}$, and number of epochs $\in\\{1,2,5\\}$).

We implement all experimental pipelines with the HuggingFace transformers
(v4.12.5) (Wolf et al., 2020), Huggingface datasets (v2.7.1) (Lhoest et al.,
2021), and Pytorch (v1.11) (Paszke et al., 2019) libraries.

###  A.2 Annotator Instructions

Figure 6: An example of the instructions given to Surge annotators.

###  A.3 Examples of Human Versus InstructGPT Feedback

Table 7: Examples of natural language feedback written by humans versus InstructGPT for incorrect programs generated by CodeGen-Mono 61.B. Incorrect program generated by CodeGen-Mono 6.1B |  Human feedback |  InstructGPT feedback
---|---|---
⬇ """ Write a function to assign frequency to each tuple in the given tuple list. >>> Example: assign_freq([(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)] ) = ’[(6, 5, 8, 3), (2, 7, 2), (9, 1)]’ """ from collections import Counter def assign_freq(test_list): """ >>> assign_freq([(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)] ) = ’[(6, 5, 8, 3), (2, 7, 2), (9, 1)]’ """ counter = Counter(x for x in test_list) res = [] for key, val in counter.items(): temp = (key, val) res.append(temp) return str(res) |  “The only issue with this code is that it does not dereference the key. When you set temp = (key, val), the key is an entire tuple instead of the values in the tuple. Thus, you need the asterisks to get the values” |  “The function works as intended.”
⬇ """ Write a function to get the angle of a complex number. >>> Example: angle_complex(0,1j)=1.5707963267948966 """ import cmath def angle_complex(a,b): return cmath.phase(complex(a,b)) |  “Only one thing is wrong in the code that complex method can take the complex number as argument example complex(a+b) not like complex(a,b) we have to replace, by + and the code is fine.” |  “The code should use the atan2 function to get the angle of a complex number.”
⬇ """ Write a function to count the same pair in three given lists. >>> Example: count_samepair([1,2,3,4,5,6,7,8], [2,2,3,1,2,6,7,9], [2,1,3,1,2,6,7,9])=3 """ def count_samepair(list1,list2,list3): count = 0 for i in range(len(list1)): for j in range(len(list2)): if list1[i]==list2[j] and list2[j]==list3[i]: count+=1 return count |  “One extra for loop for list2 is causing the issue, it finds more matching elements between list1,2,3. The possible solution for the code is to remove the unnecessary for loop of list2 iteration, and check all the lists same index element at the time, and return the count of this element.” |  “The code above is very inefficient. It is checking every possible combination of pairs of elements in the three lists. It would be much more efficient to use a set to keep track of the pairs that have already been seen.”
⬇ """ Write a function to find number of lists present in the given tuple. >>> Example: find_lists(([1, 2, 3, 4], [5, 6, 7, 8])) = 2 """ def find_lists(Input): result = 0 for x in Input: if isinstance(x, list): result += 1 return result |  “The code works for tuples of more than one list, but not in case of one single list. Python goes one level down and reads the elements when given a single list and does not see an instance of list. I would just check for the case of ‘type(Input) == list’ and turn the input into a 1-sized list of lists in this case.” |  “The function find_lists needs to return the number of lists present in the given tuple, not the number of items in the tuple.”
⬇ """ Write a function to calculate magic square. >>> Example: magic_square_test([[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]])=True """ def magic_square_test(my_matrix): """ >>> magic_square_test([[7, 12, 1, 14], [2, 13, 8, 11], [16, 3, 10, 5], [9, 6, 15, 4]])=True """ def is_square(x): return x==x*x def is_magic_square(my_matrix): sides=[] for i in range(len(my_matrix)): sides.append(sum(my_matrix[i])) if not is_square(sum(sides)): return False sides=[] for i in range(len(my_matrix)): sides.append(sum([my_matrix[i][j] for j in range(len(my_matrix))])) if not is_square(sum(sides)): return False diagonals=[] for i in range(len(my_matrix)): diagonals.append(my_matrix[i][i]) if not is_square(sum(diagonals)): return False diagonals=[] for i in range(len(my_matrix)): diagonals.append(my_matrix[i][len(my_matrix)-1-i]) if not is_square(sum(diagonals)): return False return True return is_magic_square(my_matrix) |  “The logic behind checking whether the sum of rows, columns, and diagonals is a magic number or not is not correct, the code checks if the sum of squares of itself in the is_square method is wrong. Instead of checking all the sums of rows, columns, and diagonals at every point, the logic should be like saving all the sums for rows, columns, and diagonals in one array(sides) and then checking if there are all same values present in this array because for magic_square_test all the sums should be equal.” |  “The function magic_square_test should return whether my_matrix is a magic square.”
⬇ """ Write a python function to count characters at same position in a given string (lower and uppercase characters) as in english alphabet. >>> Example: count_char_position("xbcefg") = 2 """ def count_char_position(str1): counter = 0 for i in range(0, len(str1)): if str1[i] == str1[i].upper(): counter += 1 return counter |  “a) The first thing that the code sample gets incorrect is that it increments the counter when each character in the string is an upper case character. The prompt is asking for how many characters in str1 have the same numerical position as their respective alphabetic counterpart and the code does not check for this at all. b) The way to fix it would be to create a separate j variable that keeps track of the ordinal value that corresponds with the alphabetic character that we would expect to be compared to the respective character in str1. j and i would increment at the same time so that the code is both iterating through the alphabet AND iterating through str1 simultaneously. The other fix would be to automatically convert str1 to lowercase so that we don’t have to worry about checking the ordinal codes of both the lowercase and uppercase versions of the same alphabetic character.” |  “Great job!”


Ahana Deb∗1, Sayan Nag∗2, Ayan Mahapatra∗1, Soumitri Chattopadhyay∗1, Aritra
Marik∗1, Pijush Kanti Gayen1, Shankha Sanyal1, Archi Banerjee3, Samir
Karmakar1

#  BeAts: Bengali Speech Acts Recognition using Multimodal Attention Fusion

###### Abstract

Spoken languages often utilise intonation, rhythm, intensity, and structure,
to communicate intention, which can be interpreted differently depending on
the rhythm of speech of their utterance. These speech acts provide the
foundation of communication and are unique in expression to the language.
Recent advancements in attention-based models, demonstrating their ability to
learn powerful representations from multilingual datasets, have performed well
in speech tasks and are ideal to model specific tasks in low resource
languages. Here, we develop a novel multimodal approach combining two models,
wav2vec2.0 for audio and MarianMT for text translation, by using multimodal
attention fusion to predict speech acts in our prepared Bengali speech corpus.
We also show that our model BeAts (Bengali speech acts recognition using
Multimodal Attention Fusion) significantly outperforms both the unimodal
baseline using only speech data and a simpler bimodal fusion using both speech
and text data. Project page: https://soumitri2001.github.io/BeAts
Index Terms: speech act, multimodal fusion, transformer, low-resource language

$\ast$$\ast$footnotetext: Equal contribution

##  1 Introduction

According to the Speech Act theory[1], issuance and utterance of words, which
happens during the articulation of speech, provide the foundation of
communication between the speaker and the listener. In any communication
through spoken language, the listener is dependent on their own ability to
decode the explicit or implicit intention encoded in the speaker's delivery
for the communication to be successful. Every spoken language has its unique
set of morphemes, intonations, and sentence structures, that adds crucial
meaning to the message being conveyed. Unique arrangements of these building
blocks of speech can completely change the proper meaning intended by the
speaker. Thus, the same utterance of a sentence can be interpreted
differently, depending completely on the rhythm of speech of utterance.

Figure 1: BeAts performs better than unimodal wav2vec2.0 across all 3 speech
acts classes in both Precision (P) and Recall (R) scores, by learning rich
features utilizing multimodal attention fusion module.

Prior studies in speech act recognition relied on both linguistics and non-
linguistic aspects, like sequential context, physical context, adjacency pair,
etc [2, 3]. However one of the critical aspects of speech recognition in
multilayered speech act condition is prosody and intonation, and the
modulation of parameters of this prosody changes the meaning of the intended
communication. For instance, a simple statement like "The sun rises in the
east", can be interpreted as a statement, but also with a slight change by
raising the tone in the last phrase uttered, can imply that the speaker
intends it as a question. Therefore, with the same morpho-syntactic strings, a
difference in intonation allows the same sentence to be interpreted as a
question or an assertion. In this study we make an attempt to explore this
domain for Bengali (Bangla), a low-resource Indo-Aryan language.

Our contributions are: (i) preparing a corpus of speech acts in Bengali
111Dataset can be found in Project Page, (ii) proposing a novel multi-modal
architecture (baseline) and investigating its performance in classifying these
speech acts in a low-resource setting.

##  2 Related works

Initial works in processing and classification of speech data rely mostly on
classifying low level acoustic speech parameters and spectral features using
SVMs, and shallow NNs [4, 5, 6, 7, 8, 9]. Further, CNNs were used for emotion
recognition task in speech [10, 11]. For speech act classification task, Kipp,
1998 [12] trained an Elman/Jordan network on German speech. Furthermore,
another study [13] used neural network, parsing model, and a linguistic rule-
based classifier to classify speech acts of Assertion, WH-Question, Directive,
and Yes/No Questions.

To utilise the various aspects of human communication to decode the underlying
meaning, multimodal structures were introduced. Earlier works include [14]
which proposed the use of SVMs for classifying the acoustic features forming a
feature subspace, and manually defining emotional keywords for text analysis.
Subsequent works on multimodal analysis followed partial reliance on
manufactured features, using ConvNet structures to process both textual and
visual features [15]. Yue Gu et. al, 2017[16] presented a multimodal structure
consisting of two independent CNNs, processing speech and text data.

Recent success of transformers in sequence modeling tasks has seen a wide
application in automatic speech recognition, which completely eliminates the
need to create pre-defined features. In this regard, BERT-like [17] models
achieved a significant improvement on previous architectures. Following BERT,
subsequent architectures emerged for audio data modeling, such as the
wav2vec2.0 model[18]. During pre-training the model learns general
representations of speech phonemes and complex features, providing a good
starting point to be fine-tuned on other low resource languages, such as
Bengali, with labeled data, for speech acts classification task.

In our approach, we use pretrained wav2vec2.0, and fine-tune the model to
classify speech acts in Bengali speech audio. We further fine-tune Marian-
NMT[19], a neural machine translation framework pre-trained on multilingual
datasets[20], on Bengali text to English text transcription of the speech
data. We use a multimodal-modal attention fusion using two separate schemes,
firstly with optimal transport kernels[21] and secondly with multimodality
transformer. This facilitates a greater level of interconnectivity and fusion
between the two networks processing different data from different modalities.
Finally, we feed the output to a series of fully connected layers and a
decision softmax layer for prediction.

In contrast to several recent works on multimodal speech and text processing,
we use self-attention heads to learn both speech and text latent
representations, and feed them to a separate downstream model. We introduce a
novel architecture BeAts, and extend the work of classifying perceptually
understood speech acts into our prepared Bengali speech corpus, and we compare
our architectures with the individual unimodal and bimodal models evaluated on
the same dataset.

##  3 Experimental Setup

We prepared a dataset of 85 utterances, consisting of request, question, and
order, having 25,35, and 25 utterances in the class groups respectively. The
duration of the chosen utterances were approx 1300 ms and with 5 to 7 words
each recorded in 44.1 kHz sampling rate in a soundproof recording room. For
our experiment 2 male and 2 female (average age = 23 years, SD= 2,3 years) L1
Bengali native speakers were chosen. Prior to the experiment, the participants
were instructed to carefully read each of the sentence and comprehend their
meanings. The sentences for each individual category were recorded one after
another without providing any prior context. A standard amplitude
normalization protocol was used after the recording. Since the number of
samples in the dataset is small we resorted to using augmentations (to
increase effective sample size) as shown in Fig 2. Here we refrained from
doing any spectral augmentations in the audio dataset because that might have
an adverse effect on the data. Further, we did not augment Bengali text
because the parity between the audio and the text will be lost. However, we
carefully augmented the English samples so that it prevents the semantic
meaning upon translation.

Figure 2: Augmentations used in this study.

##  4 Methodology

Figure 3: BeAts takes in as input raw waveform, annotated with the speech act
class labels, and transcribed Bengali to English translation text input. The
data undergoes positional embedding and is fed as input to the transformer
architectures for sequence modeling task. The respective outputs are fed to a
multimodality fusion block comprising of two separate schemes (i) an optimal
transport kernel (OTK) based attention, and (ii) a multimodal fusion
transformer. The output of this fusion block is passed through fully connected
layers for classification task.

###  4.1 wav2vec2.0

Raw wave input, which is positionally encoded by a convolutional neural
network (CNN), GELU activation function[22] and layer normalised, is provided
as an input to the wav2vec2.0[18] transformer architecture as shown in Fig 3.
We use wav2vec2.0 which has been pre-trained on Librispeech and LibriVox
dataset using contrastive loss (CL). CL is obtained by computing the cosine
similarity between the context representation (obtained at the transformer
output) and the quantized representation (produced through choosing discrete
entries from codebooks). During finetuning this model on our audio dataset,
the final layer is modified to output probability scores of the classes, and a
binary cross-entropy loss is calculated for upgrading gradients.

###  4.2 Opus-MT

Here, we used contextual text representation obtained in Bengali to English
translation, as an additional input for the classification task. This is
motivated by the clear structural distinction in how requests are expressed
from orders in English, which is not observed in Bengali. For example, the
sentence “Ekta nodir naam bolo toh” has the same utterance for both question
and request in Bengali, however in English, it is expressed as “Can you tell
me the name of a river” when it is intended as a question, and as “Please tell
me the name of a river” when intended as a request. Our goal is to utilise
this difference in interjections in these two speech act classes in English,
to improve our performance on classifying speech acts in Bengali, by learning
a latent representation of translation from Bengali to English of this
transcribed text.

Figure 4: The same utterance can be interpreted as Request or Question in
Bengali, whereas the expressions are structurally different in English.

The Opus-MT model[20] utilises Marian-NMT(Neural Machine Translation)[19] as
its framework architecture, based on the standard transformer architecture.
The model is pre-trained on large bitext repository OPUS[23], and fine-tuned
on the contextually transcribed Bengali to English text of our Bengali speech
data set for the speech act classification task. The architecture follows the
base model described in [24]. Here, the latent representation is concatenated
with the latent speech representation obtained from the wav2vec2.0 model, and
fed to fully connected layers to output a softmax prediction over the
individual classes.

Figure 5: Ablation with F1 scores.

###  4.3 Multimodal Attention Fusion

To further better our model’s performance, instead of directly concatenating
the latent speech representation and text translation representation from the
two models, we feed them separately into a multimodality fusion block
consisting of two schemes, namely, an Optimal Transport Kernel (OTK) scheme,
and a multimodal fusion transformer scheme. In both these schemes, we use the
output of the multimodality fusion block and pass it through fully connected
layer. Furthermore, for training we introduce a joint loss combining three
weighted loss terms (Fig 3):

$L_{total}=\alpha L_{speech}+\beta L_{fused}+\gamma L_{text}$ (1)

Ablation studies on these weights are discussed in the following subsection.

Multimodal Fusion Transformer: Here, we propose a MultiModal Fusion
Transformer where we adapt transformers for fusion among the speech and text
modalities. We concatenate the features from respective modalities together
along with a special [CLS] token as the first feature vector of the agregated
sequence to be used as input to the multimodal transformer.

OTK: The intuition of choosing OTKs is their robustness which have been
clearly demonstrated over usual aggregation methods (mean/max pooling or
attention) in recent studies, in long sequences of varying sizes, with long
range dependencies. Furthermore a single layer of OTKs have also outperformed
multi-layer feed forward NNs and in some cases multi-layer CNNs too[21].
Learning representations from a large set of feature vectors with long range
interactions actively benefits from pooling to reduce the number of feature
vectors, and here the pooling rule is similar to that of self-attention as it
follows inductive bias, aggregating features based on similarity scores. Given
a set and a learned reference, alignment of these elements are done using
optimal transport protocol, and then using this similarity they are weighted
accordingly to be pooled, which produces the output embedding. Cross attention
is an intuitive multimodal fusion method in attentive modules where attention
masks from one modality (audio representations) are used to highlight the
extracted features in other modalities (text representations). This is
different from self-attention where attention masks from one modality (text)
are used to highlight it’s own features. We use a combination of both cross
attention (multimodal attentive fusion) and self-attention to facilitate a
greater level of interconnectivity and fusion between the two networks
processing different data from different modalities, while also preserving the
individual representations of the models via the respective self-attention
layers.

Model | Request | Question | Order
---|---|---|---
| P | R | P | R | P | R
wav2vec2.0 | 0.87 | 0.72 | 0.83 | 0.79 | 0.83 | 0.81
wav2vec2.0 |  |  |  |  |  |
+Opus-MT | 0.91 | 0.73 | 0.86 | 0.80 | 0.88 | 0.82
BeAts (Xformer) | 0.94 | 0.89 | 0.91 | 0.90 | 0.93 | 0.90
BeAts (OTK) | 0.94 | 0.86 | 0.92 | 0.89 | 0.93 | 0.91

Table 1: Precision (P) and Recall (R) scores of the respective speech act
classes.

##  5 Results

As a baseline, we initially performed unimodal classification with wav2vec2.0.
The Precision (P) and Recall (R) scores are reported in Table 1. Based on the
results, it is quite evident that the speech modality alone is not enough to
capture all the information. Therefore, given the assumption that Question-
Request speech act expression is structurally distinct in English and Bengali,
we further fine-tune Opus-MT transformer on our transcribed dataset, and
concatenate the two latent representations obtained from the models, and use
fully-connected layers to produce a softmax score. This bimodal approach
increased the overall performance as compared to the unimodal approach, as can
be ascertained from Table 1.

The experimental results for BeAts are listed in Fig 1. We extend our bimodal
approach by using multimodal attention fusion via OTKs and Multimodal
Transformers respectively. BeAts achieved a significant boost in performance
across all classes for both the schemes 1 indicating the impact of multimodal
fusion in the Bengali speech acts classification task.

Furthermore, we did ablation studies on the joint loss function (Eq. 1) used
for training the BeAts model. For simplicity, we have considered
$\alpha=\gamma$ and therefore, $\beta=1-2\alpha=1-2\gamma$. We have considered
$\alpha=\gamma=[0.1,0.15,0.20,0.25,0.30]$ and reported the F1 scores for both
OTK and Multimodal Transformer (Xformer) schemes for all the 3 classes (Fig
5). From our experiments, we have observed that the best performance is
obtained for a value of 0.15.

##  6 Conclusion

In this work we presented a novel multimodal approach for speech act
classification in Bengali utterances. We combine evidence from the intonations
of the utterances as well as the structural difference in speech act classes
in English, to obtain significantly better performance on our Bengal speech
corpus, compared to the individual unimodal and bimodal approaches. Here a
wav2vec2.0 transformer models multilingual speech data and a Marian-NMT
transformer models neural machine translation, and the combination of these
two significantly increases the accuracy of speech act classification from
just using a single wav2vec2.0 model using only audio data to classify.
Furthermore, the performance of multimodal attention fusion is proved to be
much better than solely using a fully-connected layer in combining latent
space representations. Both wav2vec2.0 based audio transformers and Marian-NMT
like text transformers are demonstrated as multilingual models, which after
being pre-trained in other widely used (or with availability of rich datasets)
languages, can be applied to more diverse and data/resource constrained
languages directly, without the loss of nuance.

Our novel method of using both learning from audio data and text data to
classify speech acts on our prepared Bengali speech corpus demonstrates the
usefulness and robustness of human-like multimodal approach to learning and
navigating specifically prosodic nuances and broadly any other language
specific spoken communication. Our future works will include further
improvements on this study by updating the dataset and applying novel
architectures. We are excited about the future of multimodal language
processing, especially in a low-resource setting, where a limited amount of
labeled data can improve the performance of a classification task, used to
produce more accurate translation, eliminate specific inherent biases taken in
from data.

## References

  * [1] J. L. Austin, ``How to do things with words,'' _Clarendon, Oxford_ , 1962.
  * [2] S. C. Levinson, ``Action formation and ascription,'' _T. S. Sidnell, The Handbook of Conversation Analysis, MA: WileyBlackwell._ , 2013.
  * [3] C. D. Gisladottir RS, ``Conversation electrified: Erp correlates of speech act recognition in underspecified utterances,'' _T PLoS ONE 10(3)_ , pp. 1,24, 2015.
  * [4] K. R. Scherer, ``Vocal affect expression: a review and a model for future research,'' _Psychol. Bull. 99_ , pp. 143–165, 1986.
  * [5] K. Scherer, ``Vocal communication of emotion: a review of research paradigms,'' _Speech Commun. 40_ , p. 227–256, 2003.
  * [6] J. A. Bachorovski and M. J. Owren, ``Vocal expression of emotion: acoustic properties of speech are associated with emotional intensity and context,'' _Psychol. Sci. 6_ , pp. 219–224, 1995.
  * [7] J. Tao and Y. Kang, ``Features importance analysis for emotional speech classification. in affective computing and intelligent interaction,'' _ACII 2005. Lecture Notes in Computer Science, Vol. 3784, eds J. Tao, T. Tan, and R. W. Picard (Berlin; Heidelberg: Springer)_ , p. 1–5, 2005.
  * [8] D. Ververidis and C. Kotropoulos, ``Emotional speech recognition: resources, features and methods,'' _Speech Commun. 48_ , p. 1162–1181, 2006.
  * [9] L. He, M. Lech, S. Memon, and N. Allen, ``Recognition of stress in speech using wavelet analysis and teager energy operator,'' _Interspeech (Brisbane, QLD)_ , pp. 1–5, 2008.
  * [10] Q. Mao, M. Dong, Z. Huang, and Y. Zhan, ``Learning salient features for speech emotion recognition using convolutional neural networks,'' _IEEE Trans. Multimedia 16_ , p. 2203–2213, 2014.
  * [11] H. M. Fayek, M. Lech, and L. Cavedon, ``Evaluating deep learning architectures for speech emotion recognition,'' _Neural Networks_ , vol. 92, pp. 60–68, 2017.
  * [12] M. Kipp, ``The neural path to dialogue acts,'' in _ECAI_ , 01 1998, pp. 175–179.
  * [13] J. Marineau, P. M. Wiemer-Hastings, D. Harter, B. A. Olde, P. Chipman, A. Karnavat, V. Pomeroy, S. Rajan, and A. C. Graesser, ``Classification of speech acts in tutorial dialog,'' in _Workshop on Modeling Human Teaching Tactics and Strategies of ITS 2000_ , 2000.
  * [14] Z.-J. Chuang and C.-H. Wu, ``Multi-modal emotion recognition from speech and text,'' in _International Journal of Computational Linguistics & Chinese Language Processing, Volume 9, Number 2, August 2004: Special Issue on New Trends of Speech and Language Processing_, Aug. 2004, pp. 45–62. [Online]. Available: https://aclanthology.org/O04-3004
  * [15] S. Poria, E. Cambria, and A. Gelbukh, ``Deep convolutional neural network textual features and multiple kernel learning for utterance-level multimodal sentiment analysis,'' in _Proceedings of the 2015 conference on empirical methods in natural language processing_ , 2015, pp. 2539–2544.
  * [16] Y. Gu, X. Li, S. Chen, J. Zhang, and I. Marsic, ``Speech intention classification with multimodal deep learning,'' in _Advances in Artificial Intelligence: 30th Canadian Conference on Artificial Intelligence, Canadian AI 2017, Edmonton, AB, Canada, May 16-19, 2017, Proceedings 30. Springer International Publishing, 2017_ , 04 2017, pp. 260–271.
  * [17] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, ``Bert: Pre-training of deep bidirectional transformers for language understanding,'' in _NAACL_ , 10 2018\.
  * [18] A. Baevski, H. Zhou, and M. Auli, ``wav2vec 2.0: A framework for self-supervised learning of speech representations,'' in _NeurIPS_ , 06 2020\.
  * [19] M. Junczys-Dowmunt, R. Grundkiewicz, T. Dwojak, H. Hoang, K. Heafield, T. Neckermann, F. Seide, U. Germann, A. Fikri Aji, N. Bogoychev, A. F. T. Martins, and A. Birch, ``Marian: Fast neural machine translation in C++,'' in _Proceedings of ACL 2018, System Demonstrations_. Melbourne, Australia: Association for Computational Linguistics, July 2018, pp. 116–121. [Online]. Available: http://www.aclweb.org/anthology/P18-4020
  * [20] J. Tiedemann and S. Thottingal, ``OPUS-MT – building open translation services for the world,'' in _Proceedings of the 22nd Annual Conference of the European Association for Machine Translation_. Lisboa, Portugal: European Association for Machine Translation, Nov. 2020, pp. 479–480. [Online]. Available: https://aclanthology.org/2020.eamt-1.61
  * [21] G. Mialon, D. Chen, A. d'Aspremont, and J. Mairal, ``A trainable optimal transport embedding for feature aggregation and its relationship to attention,'' in _International Conference on Learning Representations_ , 2021\. [Online]. Available: https://github.com/claying/OTK
  * [22] D. Hendrycks and K. Gimpel., ``Gaussian error linear units (gelus),'' _arXiv_ , 2016.
  * [23] J. Tiedemann, ``Parallel data, tools and interfaces in OPUS,'' in _Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC'12)_. Istanbul, Turkey: European Language Resources Association (ELRA), May 2012, pp. 2214–2218. [Online]. Available: http://www.lrec-conf.org/proceedings/lrec2012/pdf/463_Paper.pdf
  * [24] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, ``Attention is all you need,'' _Advances in neural information processing systems_ , vol. 30, 2017.


* [13] M. Kanovich, T. Ban Kirigin, V. Nigam, and A. Scedrov.  Bounded memory protocols and progressing collaborative systems.  In ESORICS, pages 309–326, 2013.
  * [14] M. Kanovich, T. Ban Kirigin, V. Nigam, and A. Scedrov.  Bounded memory dolev–yao adversaries in collaborative systems.  Information and Computation, 238:233–261, 2014.
  * [15] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, and C. Talcott.  Discrete vs. dense times in the analysis of cyber-physical security protocols.  In Principles of Security and Trust - 4th International Conference, POST, pages 259–279, 2015.
  * [16] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, and C. Talcott.  Timed multiset rewriting and the verification of time-sensitive distributed systems.  In 14th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS), 2016.
  * [17] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, and C. L. Talcott.  Timed multiset rewriting and the verification of time-sensitive distributed systems: Technical report.  Available at http://arxiv.org/abs/1606.07886, 2016.
  * [18] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, and C. L. Talcott.  Time, computational complexity, and probability in the analysis of distance-bounding protocols.  Journal of Computer Security, 25(6):585–630, 2017.
  * [19] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, C. L. Talcott, and R. Perovic.  A rewriting framework for activities subject to regulations.  In RTA, pages 305–322, 2012.
  * [20] M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, C. L. Talcott, and R. Perovic.  A rewriting framework and logic for activities subject to regulations.  Mathematical Structures in Computer Science, 27(3):332–375, 2017\.
  * [21] M. Kanovich, P. Rowe, and A. Scedrov.  Collaborative planning with confidentiality.  J. Autom. Reasoning, 46(3-4):389–421, 2011.
  * [22] R. Koymans.  Specifying real-time properties with metric temporal logic.  Real-time systems, 2(4):255–299, 1990.
  * [23] F. Laroussinie, P. Schnoebelen, and M. Turuani.  On the expressivity and complexity of quantitative branching-time temporal logics.  Theor. Comput. Sci., 297(1-3):297–315, 2003.
  * [24] C. Lutz, D. Walther, and F. Wolter.  Quantitative temporal logics: PSPACE and below.  In TIME, pages 138–146, 2005.
  * [25] P. C. Ölveczky and J. Meseguer.  Abstraction and completeness for real-time maude.  Electr. Notes Theor. Comput. Sci., 176(4):5–27, 2007.
  * [26] P. C. Ölveczky and J. Meseguer.  The real-time maude tool.  In TACAS 2008, pages 332–336, 2008.
  * [27] J. Ouaknine and J. Worrell.  Safety metric temporal logic is fully decidable.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 411–425. Springer, 2006.
  * [28] C. H. Papadimitriou.  Computational complexity.  Academic Internet Publ., 2007.
  * [29] W. J. Savitch.  Relationship between nondeterministic and deterministic tape classes.  Journal of Computer and System Sciences, 4:177–192, 1970.
  * [30] C. Talcott, F. Arbab, and M. Yadav.  Soft agents: Exploring soft constraints to model robust adaptive distributed cyber-physical agent systems.  In Software, Services, and Systems - Essays Dedicated to Martin Wirsing, pages 273–290, 2015.
  * [31] C. Talcott, V. Nigam, F. Arbab, and T. Kappé.  Formal specification and analysis of robust adaptive distributed cyber-physical systems.  In M. Bernardo, R. D. Nicola, and J. Hillston, editors, Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems, LNCS. 2016.  16th edition in the series of Schools on Formal Methods (SFM), Bertinoro (Italy), 20-24 June 2016.
  * [32] A. Urquiza, M. A. Alturki, T. Ban Kirigin, M. Kanovich, V. Nigam, A. Scedrov, and C. Talcott.  Resource and timing aspects of security protocols.  Journal of Computer Security, 29(3):299–340, 2021.
  * [33] A. Urquiza, M. A. AlTurki, M. Kanovich, T. Ban Kirigin, V. Nigam, A. Scedrov, and C. Talcott.  Resource-bounded intruders in denial of service attacks.  In 2019 IEEE 32nd Computer Security Foundations Symposium (CSF), pages 382–396. IEEE, 2019.