SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with Backtracking
Authors: Chris Cundy
Stefano Ermon
Venue: ICLR 2024 poster (2024)
Keywords: Sequence Modelling
Imitiation Learning
Language Modelling
Primary area: generative models
TL;DR: We formulate sequence modelling as an imitation learning problem, allowing use of alternative losses and backspace characters to improve OOD behavior

Abstract: In many domains, autoregressive models can attain high likelihood on the task of predicting the next observation. However, this maximum-likelihood (MLE) objective does not necessarily match a downstream use-case of autoregressively generating high-quality sequences. The MLE objective weights sequences proportionally to their frequency under the data distribution, with no guidance for the model's behaviour out of distribution (OOD): leading to compounding error during autoregressive generation. In order to address this compounding error problem, we formulate sequence generation as an imitation learning (IL) problem. This allows us to minimize a variety of divergences between the distribution of sequences generated by an autoregressive model and sequences from a dataset, including divergences with weight on OOD generated sequences. The IL framework also allows us to incorporate backtracking by introducing a backspace action into the generation process. This further mitigates the compounding error problem by allowing the model to revert a sampled token if it takes the sequence OOD. Our resulting method, SequenceMatch, can be implemented without adversarial training or major architectural changes. We identify the SequenceMatch-χ2 divergence as a more suitable training objective for autoregressive models which are used for generation. We show that empirically, SequenceMatch training leads to improvements over MLE on text generation with language models and arithmetic

SEQUENCEMATCH: AUTOREGRESSIVE BACKTRACKING
IMITATION LEARNING FOR SEQUENCE MODELLING WITH
Chris Cundy" Stefano Ermon
Department of Computer Science, Stanford University {cundy, ermon)êcs stanford.edu
ABSTRACT
In many domains, autoregressive models can attain high likelihood on the task of predicting the next observation. However, this objective does not necessarily match a downstream use-case of autoregressively generating high-quality sequences. The MLE objective weights sequences pro- portionally to their frequency under the data distribution, with no guidance for the model's behaviour out of distribution (OOD): leading compounding error dur- ing autoregressive generation. In order to address this compounding error prob- lem, we formulate sequence generation as an imitation learning (II.) problem. This allows us to minimize variety of divergences between the distribution of sequences generated by an autoregressive model and sequences from a dataset, including divergences with weight on OOD generated sequences. The IL frame- work also allows us to incorporate backtracking by introducing a ba backspace action into the generation process. This further mitigates the compounding error problem by allowing the model to revert a sampled token if it takes the sequence OOD. Our resulting method, SequenceMatch, can be implemented without adver- sarial training or architectural changes. We identify the SequenceMatch-xx diver- gence as a more suitable training objective for autoregressive models which are used for generation. We show that empirically, SequenceMatch training leads to improvements over MLE on text generation with language models and arithmetic.
(MLE)
INTRODUCTION
Autoregressive models such the GPT series of causally masked transformers (Brown al. 2020) Radford et al., (2088) are able to perform a variety of downstream tasks such as question-answering translation, and summarization, after simply training on a large corpus of text with the objective of predicting the next token given the previous tokens. However, autoregressive language models suf- fer from a variety pathological behavior when deployed on the task of free-form text generation (Holtzman et al. 2019 Welleck et al., 2019), particularly at lower generation temperatures with smaller models. These include generating the same token or series of token repeatedly, or generating gibberish outputs. This problem of neural text degeneration has been linked to the training objective for LLMs, which trains a conditional distribution for the next token given a (partial) sentence (Fu al. 2021). When deployed in an autoregressive fashion, the model has its own outputs inputs, resulting in a compounding error problem that rapidly takes the model out of distribution (OOD). This compounding eиror problem also key issue in the imitation learning subfield of reinforce- ment learning, where the goal is to leam a policy (a distribution over next actions given the past) which results trajectories similar a set of expert trajectories. The approach of directly matching the expert's actions leads to compounding error (Ross et al.) 2011). which has led to several works proposing to address this problem by minimizing alternative divergences (Arora et al.) 2022 Shi al. 2018). These alternative divergences encourage the policy to return to expert states if the gen- erated trajectory starts to diverge from them. We argue that two key issues can prevent autoregressive models trained with maximum- maximum-iikelihood likelihood from generating fluent sequences at evaluation time. First the divergence measure used to evaluate the difference between the model and the data distribu- tion. Because the MLE E loss does not have any contribution from OOD sequences, the behavior of

---

Pancal
O =
Prodde
1=
DiLL modeel
-11 log
Dic mondell Pantal 0
D Dyal mooder Panta (() e)r
toy model of an autoregressive generation problem, such as language modelling. Our task is to learn set of conditional distributions that continue the sequence similarly to those se- quences in the dataset (green arrows), and avoid incorrect next tokens (red arrows). Our method trains against divergences that more heavily punish citoo--distribution sequences. We additionally introduce a backspace action which can backtrack from an erroneous token (dashed purple arrows).
Figure 1:
the model on OOD sequences is unconstrained. We address this by minimizing the x² diverrgene between mixture of the data and autoregressively generated sequences. This divergence is known to perform much better than MLE in imitation learning (Garg et al. 2021 Al-Hafez et al. 2023).
Secondly, if model generates OOD token, there may be natural continuation which is sim- ilar to sequences from the data distribution, and so the model may be unable to return to the data distribution even our diveerneee encourages this. To address this, augment the genera- tion process with backspace action <bkspc>, which deletes the previous token, and allows the model correct for erroneous generations. By incorporating recent work in anversrrsali imita- tion learning (Garg et al. 2021), our method, SequenceMatch, is able to train autoregressive models against alternative divergences such as the 2mmixture divergence while augmenting the policy with a backspace action. The SequenceMatch loss is fully supervised loss without adversarial training, and can applied on top of pretrained models as a finetuning step. To summarize our contributions:
We formulate the sequence generation problem as an imitation learning (II.) problem, and formulate general non-adverarial objective for minimizing divergences between occu- pancy measures based on (Garg et al. 2021). handling (among others) the forward and reverse KL-divergence, IS-divergence, and divergence.
We develop a novel masking scheme allowing training of a transformer- based autoregres- sive model with a backspace action with no additional overhead MLE.
Finally we evaluate the empirical performance of SequenceMatch- trained models, show- ing improved performance over the maximum likelihood objective in text generation and arithmetic.
PRELIMINARIES: TRAINING OBJECTIVES FOR AUTOREGRESSIVE MODELS
2.1 KL-DIVERGENCE
Typically, autoregressive models are trained against maximum-likelihoue objective. This ob- jective can be motivated by treating our dataset as consisting of sequences of random vari- ables (x1,.... N, with a corresponding probability distribution Pama( ... NNN, with fixed length N. The goal is to learn a parameterized model Po(2),...,,z that is close to Past- The KL-divergence between the data distribution and the model has useful decomposition:
DRL. (Parnll PPa) -E Potii~-PP Pan ΣN log (o + C. where C is constant that does not Pam depend on For dataset D { of sequences drawn i..dd from Panas this can be approx- C'. Hence, minimizing
imated with an estimator DRI. data P New. Σ3 ΣN log Po (o( the Kl--divergence is equivalent to maximizing the model's (log-) likelihood of the next element in
2

---

the sequence given the previous elements. The (typically unknown) density under the data distribu- tion Pdata is not required. In some domains, the length of the sequences ny differs in each example j. which can be incorporated by choosing effective length N = max f2,, and treating all sequences shorter than N as having a sequence of padding tokens appended" In the sequel with some abuse of notation we will write Psaa((n)) for Σ: log Po (==)) for partial sequences that may not terminate until after nt, and dana (2|ss) to signify the probability of the next token given a partial sequence.
2.1.1 LIMITATIONS OF THE KL-DIVERGENCE
However, while it is clear that minimizing the KL-divergence will result in Po = Panta (for a suf- ficiently flexible parameterization Po). it is not obvious what the behaviour is of models which approximately minimize the KL-divergence. In figure [] a chain distribution is shown, with se- quences of length N. The model Pe has an error on each conditional, where an error leads to an OOD sequence which has no support under the data distribution. This leads to an error in the KI. metric of order ne. However, the probability of getting to the end of the chain before an incorrect token is picked is 1 - (1 - e)", and so the value of the KL-divergence is not a good metric if our main quantity of interest is how often generated sequences are in-distribution. Furthermore, the KL-divergence weights the loss by the frequency under the data distribution, leaving the model's behavior out-of- distribbuttnnn from the data essentially undetermined.
In non-autoregressive generative modelling, several different divergences commonly used, such as the Wasserstein distance (Arjovsky et al., 2017) and Fisher divergence (Song & Ermon 2019).
Particularly interesting is the x" divergence xxa( (oo Pama) = Pa-Pa (P) Pdata (x) 1)
Indeed, figure 1 shows that the x² ddvdieegee in this case is equal to the squared probability of staying in the data distribution of sequences. We can further penalize out-of-distribution behavior by considering the divergence between mixtures 2² (Po. (Pama + Po)/2), as we do in our practical algorithm. However, it is difficult in practice to compute any divergence involving the density of the data, which must be substituted for with an approximation from a discriminator.
In reinforcement learning, there are several methods which can minimize diverse divergences be- tween the distribution of trajectories from an expert and learned policy. The approaches are non- adversarial, even with unknown expert density (Garg et al. [02T]] Swany et al., 2021 [Barde et al.) 2020 Al-Hafez et al., 2023). A key feature of these methods is that they operate on occupancy measures instead joint distributions, a concept which we describe in the next section.
3
METHOD
3.1
SEQURNCE MODELLING AS MARKOV DECISION PROCESS
We consider a sequence modelling problem represented as Markov decision process (MDP), de- fined by tuple (S,A, P,r,7). with state and action spaces S,A, dynamics P(s'|s, (s a), reward function r(s, a). and discount factor y E (0. 1). In our case, the state space S is the set of all se- quences (of all lengths) with elements in a finite set X, the vocabulary. The action set A a finite set. For concreteness, we can assume that X C A (i.e. we have an insert--eeee tooen action for each token), as well as an additional backspace action <bkspc>, In our case, the initial state given by special <bos> token, while the dynamics for an insert-token action in state (sequence) leads deterministically to the sequence s' consisting of s with the given token appended.
Combined with policy (a)ss), the MDP defines distribution over (possibly infinite-length) se- quences, following the generative process of sampling an action a ~ Po(-Is), then sampling the next state s' ~ P(s') |s, a), etc. Finally, we assume that special end of sequence token <eos> induces a terminal state: in a state s with <eos> as the final element, all actions cause a self-transition to s. This probabilistic process reduces exactly to the autoregressive formulation of sequence modelling when the action set is the same as the vocabulary. A backspace action in a state s deterministically transitions to a state s' with the final token in the sequence removed An example of the states and actions can be seen in figure 2 The MDP framework formalizes the intuitive picture in figure language modelling can viewed as the traversal of a tree where the nodes are (partial) sequences.
Some care is required, as averaging the loss of each example over its length gives an inconsistent estimator. In the of <bos> and <bkspo> used, s' <bos> also
3

---

A central quantity of interest is the occupancy measure. We denote by st the random variable con- sisting of the state at time under a policy p(a]s) and the MDP defined above. Then, the occupancy measure p(s, a) S x A + [o. 1] is the (discounted) probability of observing particular sentence 8 at time l and taking action a given that sentence:
p(s, a) (1 - r)p(als) E)
(1)
In other words, the occupancy measure is proportional to the observed frequency of particular (sentence, next-action) pair occurring. with occurrances discounted in time by a factor of 7. In the absence of editing actions, A = X and the occupancy measure is discounted probability over (partial) sequences: for sequence 8n, of length n. Palma x) = (1 - -- the sequence obtained by appending æ to s. Given editing actions which can reduce the length of a sequence, the occupancy measure becomes more complicated, as the same sequence can occur at multiple time indices. For a function r, the expectation with respect to p has the usual meaning: ((x,a)~p [r(s, a)] = Es.A p(s, a)r(s, a), with sum over the discrete action space and (countably infinite) state space. Occupancy measures provide an alternative way of modelling sequences, al- lowing us to impose a measure over all sequences, even in the presence of editing actions. The next section illustrates that we can non-ad non-adversarially minimize large variety of divergences between oc- cupancy measures, compared to only the KL divergence in the typical joint probability formulation.
(s'), Panaaad
where s' is
3.2 MINIMIZING OCCUPANCY DIVERGENCES
Our aim is to learn policy (a(a))) which induces an occupancy measure pa such that it is close to the data occupancy measure Pdat- We define the data occupancy measure by forming the data policy Pdna (ala(a))) corresponding to the conditionals Pasu (r](s)))) (r)]s.) and setting the probability of editing actions to zero It is known that matching occupancy measures implies matching policies: if po = Pdata for a valid occupancy pa. then the corresponding (als)) Panta (als) (Syed et al. 2008). Therefore, is reasonable to minimize divergences between occupancy measures. We extend the derivations in state space. We consider distances between occupancy divergences parameterized by the following form:
Garg et al. (2021) to the case with
(p,, Pdama = sup ((c,a)<po [r(s,a) -(e,a)>pum [r(s,a)] - (b(), FER
(2)
where Y is a convex regularizer. The critic r picks out differences between the occupancies, while Pa Pdata. the difference in expectations will be zero for any r. This family of divergences includes all f-divergences such as the KI. and JS-divergence, as well as the Wasserstein distance and MMD, as described in the appendix. The problem can be made tractable by adding an entropy term:
inf (po Pdata) ald (po].
with the entropy H [po] = -B [lg (8, a)), and a chosen regularization strength. Sub- stituting in the definition of dig. we obtain the min-max problem inf sup, L(0, r) inf sup, r-
(po Pdata - ((() a [po]. We prove in the appendix that the saddle-point property in Ho & EErmon (2016) extends to our deinite-dimensiona case, so inf sup, L(0,r) = sup, inf L(B, r). finding critic (LeCun et al. 2006) for sequences and actions 8, a such that the model has high values on examples from the dataset and low values on the examples from the learned model. The inner minimization over 0 is an entropy-regularized mini- mization of the KL-divergence between Pe and r. Approaching this directly by explicitly learning and Pg. would lead to objective similar to GAN (Goodfellow et al., 2014). This is known to be difficult to train (Jabbar et al. 2020). Instead, we can solve the problem with optimization over single variable by transformation of variables. In the following section, we recover objective I which is equivalent to the objective in equation 3 but only involves optimization over the logits of policy. For ease of exposition, a 1 in the next section.
We can interpret the outer maximization
3.2.1 REFORMUL THE OCCUPANCY DIVERGENCE MINIMIZATION PROBLEM
We first introduce the fuunction, corresponding to the discounted rewards obtained in state s by taking action a. Formally, it is the unique fixed point of the soft Bellman opera- tor B where (s, r(s,a) + 7BBaP((,a) [V'(')]. for the value function (*(
4

---

Ba-po(-1s) [Q(s.a) - log (a]]s)) The inverse Bellman operator T is the inverse of this operator, given by (T))) a) a( -Psss' [v' For fixed policy 9, there one-to- one correspondence between r and Q via the Bellman and inverse Bellman operators (proved in the appendix). Crucially, for the unique occupancy p which solves maxg Es [r(s, a)] Hpo] the optimal policy logp" (als) corresponding to p" is proportional to the corresponding Q-values
Q": log (a|s) = Q* a) ~ (s) Q* (s, a)
log La' e A exp Q (s, a'). The key idea of
the following derivations that the optimal policy is uniquely determined by the optimal Q- Q-values, while the reward is determined by the Q-values. This allows to optimize solely over Q-values.
Proposition 3.1.
The following equalities hold for the loss:
inf du (po. Pdataa [po] = supp inf E Paie [r(s, a)] - Epo [r(s, a)] - H (r),,
sup inf I
[T - Epp [(T8)) - H H 1(T Q):
Plaso
sup inf LE
[T - (1 - Ep, [v9)))] - (TT
0
Paass
inf TE, [+(((s,a) ->Ep [VO (1 Br) [V" (5o)]
sup
Q
sup inf E Paue ()(((sa)) - ~Bp (V - -Ep (V)(s) - ~~V (s')
Q
sup E. pap. (Q(s,a)) -Ep (V R., (V(s) >V('))
where ó is concave, Eps. denotes expectations over sampled states and actions s, a, Ep denotes an expectation over successor states s',, and B. denotes an expectation over sampled states and suc- cessor states s', for any occupancy p. V(8) (without 0) is given by V(s) = log Ew'E exp Q(s a').
Proof. The full proof is given in the appendix. As sketch, the first equality holds from the previous section. The second is obtained by replacing r with T and verifying that the two optimization problems are equal. The third line is via a telescoping sum argument first described in (Kostrikov et al. 2019p. the fourth line we replace (²r) with a simpler regularizer Eggao [g(r(s, a) where g(r)
6(r) if r Ωt and infinity otherwise. The fifth line follows from expanding the telescoping sum in a different way, incorporating samples from any policy. In the final line we
parameterize the policy from the Q-values, setting log PQ (a(ss) Q(s, a) log Ea'eA exp Q(s,a')) We then show that the optimization problem over (Q, PQ) has the same optimum the optimization over (Q, f), so we can optimize solely over Q.
We relabel Q as to to make the connection to logits clearer, resulting in the fully supervised objective over logits lo: T(Eo) EEan [o(alo(als) (s') _ (V(s) vV(')) E (v(s) (V(''),, where (s, (s.a.'')
corresponds to sampling s, a from p and from log ENEA exp (a()sss) Minimizing this objective is equivalent to ming (Pe, Paana) - H [ps), where (b, Q) supren Ex~P [ø(r(x)) -( [r(z)]. By choos- ing Ω and é, we can recover f f-divergences, including KL, and x² divergences, and additionally the Wasserstein and MMD distances. The corresponding choices are given in the appendix.
a()(s,a), and (ss)
4 PRACTICAL OCCUPANCY MATCHING WITH AUTOREGRESSIVE MODELS
In practice we wish to train a parameterized model po (a|s) which can serve as a policy, emit- ting probability distribution over the next action given a partially completed sequence A typical choice is a transformer (Vaswani et al., 2017): with parameters 0 it gives a distribu- tion over the next token v; given the previous tokens Tei parameterized unnormalized log- its Eg. Thus the MLE loss, with complete sequence TI:N. can be written as (MLE(Co) IN ((1g) - log Ex'x expé(a'
or (MLE(Eo) = EN {(xg)1<)) - V(zcs).
To form estimator for the loss derived in the previous section, samples from Pa required. We obtain these samples by sampling complete sequences from the policy autoregressively and weighting the partial sequence time by factor of x We similarly sample sequences from Paata
5

---

by sampling complete sequences from Paata and weighting. So, for length-N sequence of states S1:N from a dataset, corresponding actions d1:N and a generated length- M sequence U1:as of states from the model, we can form estimator for the loss from the previous section:
I(6o)= = Σ - - (alllll))ss) a
Σ r' (V(s)) - (V(+t1l
Penalized difference from action logit Lo nexi statee value
State, Deat state value difference under data
Σ 2 2 [V(u.)-
M
g.V a(1 a(11 0 -011-))(a(11- ((((1-)))(x)))))-->>--))))))())) 2 V(ON) - 2 V(uM),
2
State, next state value differenee under model
Loss from completed sequences
The separate treatment of the <eos> tokens arises from taking the sum over the infinite timesteps in equation in the terminal states. As shown in the appendix, the estimator is unbiased and consistent for finite Φ. It has also been shown (Al-Hafez et 2023) that minimizing the mixture divergence Dx= (Pdata: (Pama + (o) /2) is more effective than simply minimizing the x² di-vieereence between model and data. This can be implemented by calcu- lating the loss for the x ?-divergence (with <6xx) = 1 2=² and adding an additional regularization
exp and V(s) log expoae lg('ls)
term E E' ((alo(aas)) - (sV)) We show in the appendix that with no backspace actions, lima->0 The DKL, (aamallll)) reduces to a 7-reweighted MLE objective.
4.1 EFFICIENT TRAINING
Editing actions which can delete previous parts of the input are challenging to implement while retain- ing the fast training of transformer-biie based autoregres- sive models. For instance, the sequence of actions [a; b; <bkspe>] cannot be fed directly into a policy network po(als), since it contains actions, not states. The sequence [a; b; <bkspc>] is not a valid state: the corresponding state is [<bos> a]. In order to convert this into form where we can compute the relevant logits using masked atten- tion, we must pre-process the sequence of actions into corresponding inputs, labels, masks and posi- tion IDs using algorithm A in the appendix. The preprocessing is illustrated in figure 2 On the other hand, generation with backspace actions is straight- forward: we already keep previous key-value cached values for generation with transformers. When <bkspc> is sampled, we simply roll back the state of the key-value cache and position id with negligible overhead. Additionally, the loss requires sam- pling from the model during training, which is typically slow. However, the sequences do not need to be exactly sampled from the current policy. Since any policy can be used, sequences generated from the policy at previous training steps are stored in replay buffer (Mnih et al., (013)) and reused. We give an empirical analysis of the overhead when using SequenceMatch in the appendix.
States:
ppegts-eentencee
seegie-eentencee Apples
Toggor
sbogie sontenece Apoles ore
sbegis-eentence Ago lec are
Applec are blue <hackspacen green
sbogin sontenece Apples arc grean
Irput Tokana: -bogin certencer
Apples
6rd
blue
preen
Apples
blin
charkopates
green
A/A
Posstion IDa:
Macks:
Figure 2: Transforming states and actions to single-pass inputs for parallel training.
4.2 AUGMENTING EXPERT SEQUENCES WITH BACKSPACE
To provide the policy with examples of how the <bkspc> action should be used, we augment the data sequences as follows: with (small) probability n,, we replace sequence ... 1;-1, Ti, Fs+1.... with 2;,1, 2/,, <bkspc>, 1i+1,..., where x² is chosen randomly from the vocabulary. However, we keep the action at position i as Wi+1, with the result that the overall MDP is augmented with a stochastic dynamics: with probability 7) random token is inserted, instead of the chosen action. This is also applied to sequences which exceed the context length: the action is kept the same but the next token is forced to be the <eos> token. This introduces bias, the policy learns to match the data distribution under a slightly different MDP than generation takes place in. In practice however, it leads to improved performance compared the policy learning with examples of <bk <bkspe>.

---

Algorithm 1: Training an autoregressive model against a SequenceMatch objective
Input: Dataset D of data sequences, gradient-based optimizer step, number of train steps Mamin
parameters a, 99, 7, d) sampling interval kample. fixed context length
Add noise and process data sequences with algorithm A to form new effective trajectorics
Initialize buffer B of model sequences; Initialize autoregressive policy (a(-)s)
for k in Terain do mod Keompie 0 then Populate 1 with trajectories T Pracess added sequences with algorithm Remove oldest model sequences from B
if k
end
Sample dataset trajectories Tem DD and model trajectories Tmadel B
Compute = VoJ (Eo, at, 7/ Tasm: Tmodel) and update 0 via a step using gradient g
end
5 RELATED WORK
Text Degeneration in Large Language Models
In natural language processing the phenomenon of text degeneration can occur, when language model produces repetitive or nonsensical sequences (Holtzman et al. 2019). Many explanations
have been proposed to explain this phenomenon (Fu al.) 2021 Welleck al. 2019); a leading theory is that the large vocabulary size induces the model to over-estimate the probability of OOD tokens. Once these tokens are sampled, the model's context is now -ii---ffddsttittionn. Measures to mitigate this problem include top-k sampling [Fan et al. 2018), restricting generations to the k most likely tokens, and top-p sampling (Holtzman et al. 2019). 9), an adaptive variant of top-k sampling. In addition, alternative training measures have been proposed to reduce the probability of the model producing OOD tokens. Unlikelihood training (Welleck et al.] (2019) is discussed in detail in the appendix, while contrastive methods have also been proposed (Jiang et al.) 2022), which force the representations of repetitive text to be far from the representations of correct text.
Matching Divergences in Imitation Learning
In the imitation learning(Ng & Russell (2000) subfield of RI., the objective is to learn policy giving a distribution over actions in each state, such that the distribution over trajectories is close to distribution of provided expert trajectories. A simple approach is behavioral cloning (Esmaili al. 1995), which maximizes the likelihood of the expert's chosen actions, on average over the states that the expert is in. However, it has been shown (Ross al., (011) that this approach results in compounding error problem, where the further the trained model gets from the typical expert states, worse the model performs, incurring increasing error. Ho & Ermon (2016) show that minimizing the occupancy divergence between the expert and a learned policy could be written as two-variable saddle-poin problem. This more sophisticated method can take the dynamics the problem into account. learning policy which can return to the typical expert states if erroncously leaves them. In Garg et al. (202T), this was further developed via a change variables to only require a non- adversarial optimization over variable. We view approach specialization of the IQ-Learn algorithm in Garg et al. (2021) to autoregressive sequence models.
EXPERIMENTS
In this section we demonstrate that SequenceMatch can be used with large, state-of-the-art art models, and that it can be useful for downstream applications. The experiments also allow some insight into the relative importance of the different components of SequenceMatch, namely the <bkspc> token and the alternative loss. The first experiment shows that SequenceMatch can improve accuracy downstream task, and that it can detect OOD states. The second experiment shows that Sequence- Match training can generate sequences with higher similarity to the data compared to variety of baselines. In the appendix, section G we describe three additional experiments, on translation, multiplication, and prime factorization. In all experiments,
finetune Llama2-7b (Touvron et al.) 2023), using quantized low-rank adapters (Dettmers et al.) (0023). In addition to the adapters, a row added to the unembedding layer for the <bkspc> token, and the unembedding layer is trained.

---

6.1 ARITHMETIC
We first examine the potential for SequenceMatch to improve the performance on downstream tasks. The dataset is the arithmetic add-or-sub-inn-asee sub-task of the math-datased (Saxton et al. 2018). consisting of questions such as In base 7, what is -1240 - - -1156 56?. We compare a maximum-likelihood model, behavioral cloning model, and a SequenceMatch model, with varying levels and types of noise. 'Random noise' is generated by sampling a token at random from the vocabulary, and hence is not very likely to be a common mistake made when solving the problem. 'Ground-trull truun noise' is generated by sampling token from the set {0...., - 1}. where b is the base in the question. The latter type of noise is expected to generate sequences that are far closer to the type of inaccuracies that model (or human) might make while solving the problem. However, the random noise is generic to all tasks, while the ground-truth noise must be constructed for a given task manually. Both types of noise are only added to the solution digits, not the question digits. We use a small dataset of only 5,000 questions, to demonstrate the improved generalization abilities of SequenceMatch. The prompts for the SequenceMatch generations are taken from the training dataset and truncated at the end of the question. The accuracy is computed over a held-out test set of 200 questions, and error bars obtained by training two models with different random seed.
SeouerceMatchh, Grund-Th.tn Nobe
0.90
Bel avioral Cloring, Ground-Puuh hosse
MLE (No Notsel
SeouenceMatch, Random
Accuncy
0.85
0.80
0.000
0.025
0,075
0,100
0.125
0.175
0.200
Figure 3: Accuracy on the arithmetic task against noise level (frequency with which noise tokens are added), for ground-tren truth noise consisting of digits and random noise consisting of random tokens. The ground-trute noise improves accuracy for the behavioral cloning and SequenceMatch models. The random noise does improve performance for the behavioral cloning model, but does some- what for the SequenceMatch model, likely helping the model to learn the dynamics of <bkspc>.
6.1.1 RESULTS
The results are shown in figure It clear that the models trained under the SequenceMatch loss outperform both the behavioral cloning (BC) and MLE baselines. With zero added noise, the improvement small, as the model is not able to learn the backspace dynamics with no demon- strations from the expert. However, with a small amount of added noise, the SequenceMatch model has demonstrations of the use of <bkspe> and can start learning the dynamics through sampling. The BC model improves performance at higher levels of ground-truth noise, as the high level of noise acts as strong data augmentation. Indeed, this improved performance seems roughly propor- tional to the amount of added noise, as expected. Similarly, while random noise is useful to the SequenceMatch model due to the dynamics information, it does not help the BC model.
Qualitatively, the SequenceMatcc--rraine accurately. In [able[[the the best-performing Sequence.Match model is prompted with partial solutions which are incorrect (the first four in the test set with added random digit tokens). In each case is able to detect the OOD case and return closely to the correct answer.
model is able to detect when is
very
6.2 TEXT GENERATION
We the same model and architecture as the previous section. Sequences drawn from the open- webtext " an open-sourced dataset similar to the training set for GPT-2 (Radford et al. 2018).
8

---

Ground Truth QA
Prompt with Mistake
Completion Actions
Final State
In base 2, what is
In base 2, what is -1010111100 01101100000010000010011100011100
-1101111011000010
0110011111101110 100 101007 Soluticn: -110111011111000
101007
1101111 <bkkps>100 1000000110
Solutions -1011
<cos>
base 8, what is 4354 337 base 8, what is 4354 337 <bkagox441
4417
Bolution: 4607
Bolution:
In base 8, what is -4
In base 8, what is -4
-576126
-5761227 Solution: -575125
-5761227
Solution: -374
576126<605>
is
in
<bkapex <bkspe>
3311111
33111217 Solutions -33:11:1 33111217
Solution: -31
Table 1: cisttke--ooniitiond completions for the arithmetic task. We add random set of digit tokens to the prompt and generate from the SequenceMatch-traiieed model. The SequenceMatch model correctly deletes the initial tokens in all cases and eventually generates the correct solution in three of four cases.
Model
MLE
MLE+ + C.S
MLE+ ULK
MLE + <bkapc>
SequenceMatch
MAUVE (1)
0.85 0.03
0.86
0.03
0.89 + 0.02
0.84 0.02
0.91 0.02
n-gram H (f)
4.57 0.02
4.43 + 0.02
4.57 10.01
4.59 1 0.01
4.60 + 0.01
Diversity (f)
0,56 + 0.02
0.35 + 0.03
0.57 + 0.01
0.56 + 0.01
0,56 + 0.01
Perplexity (4)
6.99 0.02
N/A
7.10 + 0.02
7.02 1 0.02
7.13 +: 0.03
Table 2: A Llama-2-7b model fine-tuned on the openwebtext dataset with different training and sampling regimes. Error bars are over two draws of 1000 evaluation samples. C.S. and ULK contrastive sampling and unlikelihood loss training, respectively. The SequenceMatch model achieves the highest MAUVE score and n-gram entropy, with diversity very close to the best value from the MLE unlikelihood training.
with 1024-length context window, truncating sequences that are longer. The model-generaan tra- jectories are generated from examples from the training dataset, with a prompt length randomly chosen with maximum of 256. The generated sequences have max length of 512 (although they may terminate earlier). We compare a SequuenceMacch-triinee model against several baselines: a model trained against the typical MLE objective, and a behavioral cloning model trained with in- jected noise and <bkspc> labels. We also test MLE C.S.. which is MLE with contrastive with the unlikelihood token loss (Welleck et al.] 2019). We train for 5,000 gradient steps. The SequenceMatch parameters are set a 0.01, n 0.001 and 7 0.998. Our main metric for quality of generations is the MAUVE score (Pillutla et al. 2022). a non-parametric method for evaluating the quality of generative model. The MAUVE score is formed by taking a low-dimensional PCA of an embedding of the generated sequences. The score is a mixture of forward and reverse KI.s between data and model-generated sequences, between zero and one (higher is better). Additionally we report the
sampling @Jiag et al., 2022). Finally, MLE ULK is Maximuu--ikellhenn
n-gram entropy and the diversity metric (Jiang et al. 2022). given by II (1.0
rep _oo") where
rep-n = 100 x 1.0
unique n-grams [+)] for a generation a. [total n-grams (#)]
6.2.1
RESULTS
Table 2 shows that the DequuenceMatch-traimee model is able to achieve higher MAUVE score com- pared to the baselines. It also improves with respect to the n-gram entropy. On the diversity metric, all models are similar, except the contrastive sampling model. The SequenceMatch-rraiee model is outperformed the perplexity metric by the BC and MLE-trained methods. This is expected, the training objective for BC and MLE is exactly the log-perplexity. However, on the MAUVE score, only unlikelihood and SequenceMatch offer a substantial improvement MLE. Of course, unlike- lihood relies on a heuristic to penalize repetitions: heuristic not appropriate in e.g. arithmetic.
7 CONCLUSION
We address the compounding error problem in autoregressive sequence generation by formulating the problem in the imitation learning framework, deriving general non-adversarial objective for minimizing divergences between occupancy measures induced by a learned model and the data dis- tribution. We develop a novel masking scheme to train transformer-basee autoregressive model with a backspace action with small overhead vs MLE, further reducing compounding error by al- lowing backtracking. Empirically, the SequenceMatch objective leads improvements over MLE at text generation and arithmetic. Future work could investigate how qualities of generations change with choice of divergence, find methods reduce the overhead of the SequenceMatch objective.

---

8 ACKNOWLEDGEMENTS
This research was supported by funding from the following: Stanford HAI, NSF(#1651565), ARO (W91INF-21-1-0122 ONR (N00014-33-1-2159) and the CZ Biohub. We thank Anuj Nagpal, Div Garg and Andy Shih for valuable discussions and feedback on this research direction.
REFERENCES
Firas AI-Hafez, Davide Tateo, Oleg Arenz, Guoping Zhao, and Jan Peters. LS-IQ: Implicit reward regularization for inverse reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223. PMLR, 2017.
Kushal Arora, Layla El Asri, Hareesh Bahuleyan, and Jackie Chi Kit Cheung. Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 700-710, 2022.
Paul Barde, Julien Roy, Wonseok Jeon, Joelle Pineau, Chris Pal, and Derek Nowrouzezahrai. Ad- versarial soft advantage fitting: Imitation learning without policy optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 12334-12344, 2020.
Tom B. Brown, Benjamin Mann, Nick Ryder. Melanic Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners. arXiv:2005. 14166 [cs], July 2020.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. arXiv preprint arXhv:2305.14314. 2023.
Nasser Esmaili, Claude Sammut, and GM Shirazi. Behavioural cloning in control of dynamic system. In 1995 IEEE International Conference Systems, Man and Cybernetics. Intelligent Systems for the 21 Century, volume 3, pp. 2909.2909. IEEE, 1995.
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 889-898, 2018
Zihao Fu, Wai Lam, Anthony Man-Cho So, and Bei Shi. A theoretical analysis of the repetition problem in text generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12848-12856, 2021.
Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon. IQ-Leamn Inverse soft-Q learning for imitation. In NeurlPS, 2021.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Neural Information Pro- cessing Systems (NeurIPS), 2014.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint 1oXiv:1606.08e 2016.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case neural text degeneration. In International Conference Learning Representations, 2019.
10

---

Abdul Jabbar, Xi Li, and Bourahla Omar. A Survey Generative Adversarial Networks: Variants, Applications, and Training. 2XXi::2006005122 [cs], June 2020.
Shaojie Jiang, Ruqing Zhang, Svitlana Vakulenko, and Maarten de Rijke. A simple contrastive learn-
ing objective for alleviating neural text degeneration. arXiv preprint arXiv:2205.02517, 2022.
Iya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching, In International Conference on Learning Reprexentations, 2019.
Dohyun Kwon, Yeoneung Kim, Guido Montúfar, and Insoon Yang. Training Wasserstein GANs
without gradient penalties. arXiv:2110.1444 14111500 [cs, math), October 2021.
Yann LeCun, Sumit Chopra, Raia Hadsell, Marc Aurelio Ranzato, and Fu Jie Huang. A Tutorial on Energy-Based Learning, 2006.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning, 2013.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proc. 17th International Conf. on Machine Learning. Citeseer, 2000.
Krishna Pillutla, Lang Liu, John Thickstun, Sean Welleck, Swabha Swayamdipta, Rowan Zellers, Sewoong Oh, Yejin Choi, and Zaid Harchaoui. MAUVE scores for generative models: Theory and practice. arXiv preprint arXiv:2212. 14578, 2022.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners, 2018.
Douglas Rizzolo and Francis Edward Su. A fixed point theorem for the infinite-dimensionn simplex. Journal of mathematical analysis and applications, 332(2):1063-1070, 2007.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to no-regret online learning. In AISTATS, pp. 627-635, 2011.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical rea- soning abilities of neural models. In International Conference on Learning Representations, 2018.
Zhan Shi, Xinchi Chen, Xipeng Qiu, and Xuanjing Huang. Toward Diverse Text Generation with Inverse Reinforcement Learning. arXiv: 1258 [cs, stat], June 2018
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(4):171-176, 1958.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, volume 32, 2019.
Gokul Swamy, Sanjiban Choudhury, Zhiwci Steven Wu, and J. Andrew Bagnell. Of Moments and Matching: Trade-offs and Treatments in Imitation Learning. a:Xiv:2103.03236 [cs, stat), March 2021.
Umar Syed, Michael Bowling, and Robert E Schapire. Apprenticeship learning using linear pro- gramming. In Proceedings of the 25th International Conference on Machine Learning, pp. 1032- 1039, 2008
Shichang Tang. Lessons Learned from the Training of GANs on Artificial Datasets. vrXiv:2007.0644 {es, stat], July 2020.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint drXiv:2307.09288 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, volume 30, 2017.
Sean Welleck. Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. Neural text generation with unlikelihood training. In International Conference on Learning Rep- resentations, 2019.
11

---

A ALGORITHM A
Algorithm 2:
Algorithm A: Pseudocode for converting action sequences to masked inputs
Input: : Sequence of action inputs d1:L
output: Sequence of labels, inputs, masks, position ids
yE [V | [VL,, m E {0, 1] Lx P [4]
Initialize y, m. to zero.
Initialize x to a.
Initialize 0
// Copy Pointer // Deletion Pointer
Initialize for i ..... do
m|i] + mmmmmmmmm. (i - 0,]
if a <<bkspo> then
m|i.c +- 0
m t 0
m +
x/i] x|c]
pl1 + plc
d
+ element of last nonzero element in m/i, 0 c]. else 0.
end else
mli +
d d +1
c c element of first nonzero element mliic 1 LJ. else 0.
p|i] pld 1] +1 end if then
- 0
// Special cases for initial steps
d
end
then
c -
d 1
end
end
In algorithm A give method to convert sequence of actions into masked sequence of inputs and corresponding labels, masks and position ids. Although it can also be implemented in a stack- based fashion, write it imperative algorithm it be compiled with the jit operation in JAX or the compil. le operation in PyTTorc. Recall that the idea is to replace a sequence of actions with sequence of inputs and corresponding labels, masks and position ids. The input sequence at position & should correspond to the state at position & (when the corresponding mask is applied) and the label at position + 1 is the action taken at position that the inputs should never include a <bkspc> token. The main idea is that if we have sequence of actions [. ...., a, b, <bkspo>, , ..... the corresponding inputs are [..., a, b, a, 1, while the masks for the second onwards mask out the first b. However, the possibility of multiple backspaces introduces some complexity.
A consequence of this is
The approach of the algorithm is to keep running copy pointer and deletion pointer. The dele- tion pointer points to the cell of the mask that must be zeroed out for subsequent positions in the sequence, while the copy pointer points to the position that must be copied to the current cell of the input (and also zeroed out in the mask). When a backspace occurs, the deletion pointer is set to the current index, and the copy pointer is sent backwards to the last non-deleted position. When a backspace doesn't t occur, the deletion pointer is incremented by and the copy pointer is moved forwards to the first non-deleted position.
12

---

B MOTIVATING EXAMPLE ALGEBRA
We consider the case of length- n. Markov chain with an additional node coming from each node. These nodes correspond to the dashed nodes in figure We write the dashed nodes as Ziem- As in the figure, we have duta (Irerm = O, model the two distributions.
(oddel(Terml) (Tterm) = e. We wish to compute the divergence between
B.1 KL-DIVERGENCE
We have
DxL(PI1Q) = Eeup [lo P(x) log Q(x)] = -n log Q(1 c).
B.2 REVERSE KL-DIVERGENCE
We have
DKL(Q112 = Exr~ [log Q(z) - log P(x)] 00.
since P( = 0) and (Jierm) of O.
B.3 X DIVERGEENC
We have
D2= Exn (p(z) -
27
C PROOFS FOR SECTION 3.2
C.I PROOF FOR SADDLE POINT THEOREM
We wish show that
inf sup L(0,r) = sup inf L(O, r).
Now, the set D of occupancy measures stemming from conditionals compact and con- vex, since it is formed from linear constraints: firstly P 2 O, and secondly E. p(s. a) E p(s', P(sss' a). Vs, Because D closed subset of the infinite-dimeniioaal simplex Ag which is compact (Rizzolo & Su, 2007). DD is also compact. The set R. is convex, since it consists of all sequences. Since the inner function is convex in po and concave r, we can apply Sion's 's minimax theorem (Sion 1958) to swap the inner inf and sup.
C.2 PROOF FOR BIJECTION BETWEEN AND
Recall that we define the Bellman operator as B where (s, = r(s,a) + (lE.))((s.a)) [s)] for the value function (s) = Ea-pu()))) [Q(s, log The in- verse Bellman operator T is defined as (T" = Q(s,a) - [V')')).
Theorem C.I. For fixed policy 0, the inverse soft Bellman operator T is bijective, and for any 1 is the unique fixed point of the Bellman operator B"-
r E Q == -1r
Proof. The proof very similar to the proof of lemma 3.2 in Garg et al. (202T) We construct an infinite matrix pe E (SSxx))((xxA) where (P² (s, (ss a)
ass.)s [f(s', d')]. The matrix po corresponds to the transition matrix for the given MDP and the policy 0. We then have r T for any Q. Then, Q 7 yp*) (r - Po) + log We can do this since P b < if < 1, and so - 7 is invertible, even in this
log pa). Rearranging, we get Q (1
setting. We also that Q has a unique vector expansion Q = p (Q logPa) Pa). Since this is the (unique) vector expansion of 13, we have Q = (T")r
B&Q
13

---

C.3 TELESCOPING SUM PROOFS
In this section we prove various theorems related to telescoping sums and value functions. These mostly follow from Kostrikov et al. (2019) and Garg et al. (2021).
Proposition C.2. For policy pe. initial state distribution Pu. value function (s)
E--po(-1s) [Q(s, a) - log Palls) the following identities hold:
Eg Q) a)] H[p
(1 7) (so)
(5)
= - (s) >V
(6)
where is any occupancy measure, and 8, 8 ~ p denotes sampling 8, from and s' from P(a, 8).
Proof. We have
Bg [(T))((s,a) + H [pa] = E, amp [Q(a,s) - -BBu)P(ssa) [V* - log (7)
s'pp (s) -V
(8)
By the definition of the occupancy measure and expanding, have
Ex.s'~po (V))))(((6))) (1 - 7) [[E[V >E[V (s1)]] + [s]] -E [s2)] + ...
(9)
= -11 - (+) (so)]-
(10)
Because so does not depend on p. we can expand the sum in the opposite direction show that Exaapp ((T))((s a)) + H [pa] = E' (v) (V")s' for any occupancy p.
C.4 PROOF OF EQUIVALENCE OF SOLUTIONS OF J AND L
We now reproduce a proposition from Garg et al. 202T
Proposition C.3. the Q-policy space, there exists a unique saddle point (Pg- Q"), that optimizes J. That is, Q" = arg maxqes minp,& I (pe, Q) and more, Pa and
mrgmin,, maxqeo J (po, Q). Further- TP Q* are the solution to the inverse RI. objective L(po,r). This is proposition
3.4 in Garg et al. (2027).
Proof. See Garg et al. 2021 for the complete proof. The proof given applies directly to our case.
C.5 PROOF FOR THEOREM 3.1
We prove main result
Proposition C.4. With quantities defined in the main text, the following equalities hold for the loss:
inf (po, Pdata)
H [po] sup inf Ex pam [r(s, a)] Eg [r(s, a)] - [ -b(r),
0
sup inf E a..arPP Paas [(T)Q)(s, - Ex ( (T),)) H -
(TT
sup inf E. Pam [d(Q(s,a) - 7,, BBNNP(LaN [v)]] (1 E [v- (so)
[(T)))(s, a)] - - -(1-7) Beu [v) (TT
0
inf E. aa sup Q
sup inf E, Pm [o(Q(s, a) >B, -P()) - [v (s'))) - -Es,s' (V((s) - (s))
Q 0
sup [Q) sup E, Ea (o(Q(s, a) -BB-P( [V(s'))) E,,s' (V(s) - VV('))
Proof. The first equality is proven in section C.I The second line follows from sections C.2 and
C.4
The first section shows that the objectives I (Q,0) and T(0,, r) are the same, by the bijective
14

---

property of T. The second section proves that the (unique) saddle points of the objectives correspond to the same solutions.
The third line follows from the telescoping sum given in section The fourth line follows from the substitution of a general (r) with a simpler regularizer Es [g(r(s, s, a))l, where g(r) = r- -()(r) if r S2, and infinity otherwise. This allows to ground out the divergence minimization directly to concrete divergences such as the KL-divergence, JS-divergence, divdirerge,ce, etc. We discuss this more extensively in section D.I In the fifth line expand the telescoping sum in different way using the result in section C.3 This allows us to incorporate samples from any policy, in order decrease variance.
In the final line we parameterize the policy from the Q-values, setting log (als) Q a) log Ea'EA exp Q(s, a'). The fact that supq infe I (pe. Q) = sup I [pQ, Q) follows from the fact that there is unique saddle point for [pe, Q), the fact that J (pQ, Q) concave in Q. and that the saddle point for I (pq. Q) has a supremum in Q where = 0", with log Pă (a|s) [ Q* a)
log Ex' exp (s, a') and Q* the corresponding supremum Q. This allows elimination of from the optimization process entirely, and completes the proof.
C.6 PROPERTIES OF THE PLUG-IN ESTIMATOR
The plug-in estimator J unbiased from the linearity of expectation. Under the assumption that the expected loss is finite, the plug-in estimator is also consistent. This follows from the law of large numbers. We can ensure that the expected loss finite with the X²-divergence by bounding the logits within some large range.
D CHOICES OF DIVERGENCE MEASURES
D.1 f-DIVERGENCES
We recall that for any f-divergence with (), = E (f(P(z)/((z)) we have the varia- tional form
()( = sup {EEDP [o(x)] - Eunq If (6(x)))
with the convex conjugate (") sup, fx.y-- y f(x))) and discriminator Φ X' R. Opti- mizing a model against an f-divergence other than the KI.-divergence typically involves a difficult min-max optimization problem where simultaneously improve the model and improve the dis-
criminator é. This is subject to unstable training (Kwon et al. 2021 Jabbar et al. 2020 Tang 2020
Goodfellow al. 2014).
In the main paper, we explain that we require a divergence
des (po, Pttaa) = "po Paata)
With our choice of vé, we get that
dy (p, Pdata)
max E pe. (o(r(s,a)) - E, [ r
We can readily connect these to f-divergences. Recall that the variational formulation of the f- divergence is
()( sup (Earr [g(x)] - Enn (g(x)))
(11)
g
so we can see that the function ø we need is simply -f
D.2 KL-DIVERGENCE
Note that we define our divergence in the reverse fashion to the usual convention, so to obtain the typical forward KI. under the expectation of the data, must the reverse-KI. f-divergence,
15

---

with f(x) x log This gives 6(x) -e- (x+1)) However, since always shift f- divergence's 's f by a constant multiple of (z -1 1) without changing the divergence (which should be clear from observing cancellations in the definition of the f divergence), shift by -1 and (after working through the derivations) have a simpler (0(x) = -
If we take the objective from equation 4 and observe the limit as -> O,, we have lima-0 Tte eex(=axx -1 r. Examining the terms in (Eo), we can combine the two value sums into single sum over the data sequence. Then, we can cancel the 7V (s;-1) 1) terms from the first and second sum. This leaves the term Σ; ('(co(a)ss)) (s:)). This is precisely a weighted variant of the typical maximum-likelihood loss.
DKL (Ptasal Pa). This is because lim
D.3 JENSON-SHANNON DIVERGENCE
The Jenson-Shannen divergence has f(z) (xx 1) log( =11) + log This leads to ((x) log(2 e =)) This is an interesting ó because it is equal to -0o for < log Since the x in this case is the value of obtained from the model's logits, it is certainly possible that the value may be less than log 2. In practice, could replace & with sharply descending quadratic for all close to log 2 and below. This gives penalizing effect on small r, while not causing (too many) numerical issues.
D.4 X² --IVERGEENCE AND X2 -MIITURE DIVERGENCE
For the diverenge,,,, we have ((x) = ((1 - 1)3), leading to <(x) = (s x2/4)-
As described in AI-Hafez al. (023), we add regularization term by computing (r) BelE [r(s, a) (1 3)cBBp [r(s, }) In other words, instead of computing the r² term on the expert trajectories only, we also compute this for the policy trajectories as well. We set e = 0.5 and | 0.5. This results in an even mixture of regularization contributions from the expert and policy. Although this was introduced in Garg et al. (2021) heuristically, it was shown in Al-Hafez al. (2023) that this has a well-motivated derivation as a result of the divergence between the data occupancy and the mixture between the data occupancy and the policy occupancy:
2x" 2x2(Paaal || Pdata + P0 = sup Epmm (r(s, a)] Eprin
[((..)) +
-76,) r(s.a)p)
2
4
Paix
sup Pe (r(8, a)] - Ep [r(0, a)) - camR.pm -c1]) -a) (r(s.u)?
In practice, we find this method leads to better quality generations.
D.S BACKSPACES ARE THE ONLY EFFICIENT MDPs FOR AUTOREGRESSIVE MODELS
We introduced the backspace as an additional action that we could take that we do not view autoregressive generation as necessarily modelling probability distribution. However, we can show that it is fairly principled choice of action. In fact, with autoregressive model, the only actions which can be implemented without requiring recomputation of preceding actions are the actions which generate new token, or do an n-step backspace.
To see this, we will first deal with the case of a purely autoregressive model, such as an recurrent neural network (RNN), where processing sequence s; (I1, T2, ...,,........................... 2;) requires sequential pro- cessing of every token T; However, we will assume we keep a buffer of the previous hidden states (hı,...h,) h1)) so we can revert these under backspace. Then, given a current sequence 8 and an action which causes a transition to another sequence s', and s' must differ in at least one token. If differs first a token at location i < |s] then we must revert the hidden states to h; and recompute the next tokens from i to (s'). If |s'l i, then this only requires one pass. This includes the case where no reversion takes place, and is s with an additional token appended (i.e. the traditional appending token case). In the case where s' is longer than by i tokens, must compute & forward passes. Therefore, the only actions which require one forward pass are those that add a token, or that solely remove number of tokens.
16

---

In the case of transformer model, the logic is very similar. However, while analysis is the same as preceding in terms of floating point operations, it is not the same for the latency. As the transformer model can compute a forward pass over multiple imput tokens in parallel, MDP with an action mapping a sequence & to s' could be implemented with relatively low latency, even if s and s' were very different. Whether floating point operations or latency are the main bottleneck will depend on the particular set-up.
E ADDITIONAL TRAINING DETAILS
We train each model on four A4000 GPUs with 16GB VRAM each. We keep the batch size at 32 for all models. We use a QLORA r of 64 for all experiments, and an a of 16. Gradient checkpointing and reduced precision was used to reduce memory requirements. For all models, we add an addi- tional row to the unembedding layer of the transformer, corresponding to the logits for the <bkspa> action. For the SequenceMatch models, we first train against the BC objective alone for k gradient steps, and then train against a convex combination of the SM loss: Lioal = BCBC + (1 CsM. where B is annealed from 1 to 0.2 linearly over 2,000 gradient steps. For the arithmetic task h is 10,000. For the text generation task & is 1,000. We use learning rate scheme consisting of a linear warmup from 0 to 2000 steps, followed by cosine decay. For the extra logits offset head, we use two-layer MLP with Gelu (Hendrycks & Gimpel| (016)) nonlinearities and hidden size equal to 8. The inputs to the layer are the position id and the hidden values at the current position. The output of the layer is added directly to the logits. For SequenceMatch, we keep replay buffer of past gener- ated sequences. The replay buffer is firs-in-last-out with the oldest sequences being replaced once the size of the buffer is reached. The size of the replay buffer is 1,000. We specify how many times each sequence in the replay buffer will appear the training data before it is replaced (on average), and from that (and the generation batch size) calculate how frequently generation step must take place during training. We set the times each sequence will be seen in training to 8. For the text- generation evaluation, we set the prompt length at 256. We then generate sequences of length 256. For the generation, we set the temperature to and the top-p sampling to 1, with no top-k sampling. Since the on- on-policy regularization term needs the input to be generated from the current policy, mask the prompt when calculating the regularization for the generated sequences. For the arithmetic task, we mask out the prompt when computing the MLE loss, this generally leads to more accu- rate responses (Dettmers et al. 2023). In the arithmetic task, the dataset sequences are constructed (solution] For the arithmetic task with 'ground-truie truut''truth'' noise,
as {question] Solution. we add in tokens after the position of the Solution on token, of digits in the range O.... b - 1 for base-b question. Because the Llama2 tokenizer has separate tokens for combinations of letters such as a, ab, etc, while having no tokens for combinations of numbers, it would be difficult to construet the ground-truth noise in the bases higher than 10. Therefore, we filter out questions with a base higher than 10. We do not add any noise to the problem statement.
F OVERHEAD
In this section we discuss the relative overhead of using the SequenceMatch training objective. We have additional overhead due to the necessity of sampling completions from the model. In addition, the actual loss has some additional complexity compared the typical MLE loss, as we must extract the terminal values and compute a telescoping sum. Additionally, the on-policy reward regularization term requires computing logits with respect to the generated batch in addition the data batch. Due to the fact that we use a batch of masks with a complex masking patterns, some GPU kernels that are specialized for causal masking cannot be utilized.
However, we note that it's not necessary to sample at every gradient step, since we can accumulate old trajectories in a replay buffer and re-use them. Furthermore, we can typically sample using a higher batch size than the gradient step batch size, so requiring fewer sampling steps per gradient step. In tables 3 and 4 we show the breakdown of times necessary for a gradient step for each method, in the arithmetic and text modelling cases. We see that the loss computation and gradient step typically takes around two or three times as long for the SequenceMatch objective than the MLE objective, due to the additional computation specified above. The sampling adds additional overhead, depending largely on the length of the sequence that is sampled. We note that the bot- tleneck from sampling could in principle be completely removed by adding separate of GPUs
17

---

Training Procedure
Gradient Step
Sampling Time
Grad Steps per Sample
Total Amortized Time
MLE
1.5 + 0.1
N/A 50 + 10
N/A 16
1.5 = 0.1
SequenceMatch
5.3 + 0.5
8.1 + 0.2
Table 3: Execution time of various parts of the training loop for the different models for the 1024 context length, x2 objective with model rollouts regularization, with the Llama-2-7b model and 4-bit quantized low-rank training. We show the raw time to sample a batch of trajectories, as well as the time for sampling once amortized due to the fact that we not sample every training step, and that the training. Because of the unequal memory constraints during quantized low-rank training, we are able to use a large batch size comparatively when generating, allowing us to generate infrequently. Note this is for batch size per GPU of 1, so each optimization step takes eight times long for minibatch size of 32 and GPUs
Training Procedure Gradient Step
Sampling Time
Grad Steps per Sample
Total Amortized Time
MLE SequenceMatch
1.2 + 0.1
N/A 2 = 0.1
N/A 32
1.5 = 0.1 2.16 + 0.1
2.1 + 0.5
Table 4: Execution time of various parts of the training loop for the different models for the arith- metic task, x2 objective with model rollouts regularization, with the Llama-2-7b model and 4-bit quantized low-rank training. We show the raw time to sample a batch of trajectories, as well as the time for sampling once amortized due to the fact that we do not sample every training step, and that the training. Because of the unequal memory constraints during quantized low-rank training. we are able to use much larger batch size comparatively when generating, allowing us to generate infrequently. This table is for a batch size per GPU of
which independently generate sequences given the latest parameters and write to a buffer which is polled by the main training thread. Due to time constraints and the additional complexity of syn- chronizing separate processes, we did not implement this additional distributed training approach.
G ADDITIONAL EXPERIMENTS
G.1 DIFFERENT DIVERGENCES
We briefly experiment with the Aisson-Shannon divergence described in section D.3 As discussed, the main issue is that the function is not defined for inputs less than - log 2, and asymptotically approaches - 00 as the input approaches - log 2. We replace the function & with a linear surrogate for < 10--lo log 2+6, with å = 0.01. The linear surrogate was chosen to be continuous, differentiable extension of the function ó from the point log 5.
We kept all the hyperparameters the same in the experiments with x² divergence. For both the noise settings considered in the main paper, the JS-divergence was only able to achieve 60% accuracy, compared 85-90% for the x² diviergeneee. There were frequent spikes in the gradient norm compared to the x² divergence.
G.2 OPUS_BOOKS EN-FR
This translation task was implemented similarly to the arithmetic task in the main paper. The prompt was the English 'question' and the completion being the French 'answer'. We use random noise tokens, with noise level 0.2. The BLEU scores were computed using the sacrebleu package. We used a subset of the data consisting and the answer was less than 64 tokens long. This was still majority of the examples in the dataset.
examples where the question was less than 64 tokens long
The BLEU scores are shown in table S We see that the SequenceMatch model is able to achieve small increase in BLEU score compared to the MLE and BC models, although the results have quite high variance. Similarly to the arithmetic experiment, we notice that the backspace is used in generations correct mistakes, such as the following completion:
18

---

English: If he only set two to-day... He would go back to his desk and notice the absence of Meaulnes.
Generation: Si c' était deux qu'il faisait... Il call<bkspe> rentrait dans bureaut<bbssp>>au, déplorant l'absence de Meaulnes.
We expect that the performance could be improved by using targeted noise tokens, such common incorrect French translations from a pretrained language model.
Method
7/ 0.02
1/ 0.2
MLE
31 - 2
31 + 2
BC
32 -
34 2
SM
37 +
36 + 4
Table 5: BLEU scores obtained by the MLE model, the Behavioral Cloning model, and the Se- quenceMatch model on the en-fr translation task.
G.3 ARITHMETIC_
This task was implemented exactly for the arithmetic addition task, with the same number of training examples. We used only bespoke noise for this experiment. We report the accuracies in table As in the previous experiments, we see an improvement for SequenceMatch, although in this case the behavioral cloning objective does not lead to a significant increase from MI.E.
Method
= 0.02
1) = 0.2
MIEE
0.49 + 0.04
0.49 + 0.04
BC
0.51 + 0.02
0.5 + 0.03
SM
0.53 0.03
0.56 + 0.04
Table 6: Accuracies obtained by the MLE model, the Behavioral Cloning model, and the Sequence- Match model on the Arithmetic mul task.
G.4 NUMBERS LIST PRIME FACTORS
For this task, we initially used 5,000 training data as in the arithmetic tasks. However, we found that all models had very poor performance, with less than 1% accuracy rates. We increased the number of training data to 50,000 and found performance increased. However, the models still had relatively rate of accuracy and noisy evaluation, so this experiment may not be very informative. We used bespoke noise at two different levels. The results are shown in table
Method
= 0.02
7) = 0.2
MLE
0.04 + 0.03
0.04 + 0.03
BC
0.07 + 0.02
0.06 = 0.03
SM
0.06 + 0.04
0.08 = 0.04
Table 7: Accuracies obtained by the MLE model, the Behavioral Cloning model, and the Sequence- Match model on the Numbers__list.prime factors task.
H ADDITIONAL RELATED WORK
H.1 REGULARIZATION TERMS
Due to the disadvantages of the KL-divergence discussed in the first section, several additional training objectives have been proposed which take into account the model's generated sequences.
19

---

Particularly popular is the (sequence-level) unlikelihood loss (Welleck et al. 2019). At step t, this given by
C+N Σ k=t+1eECH
(P Po
Σ Po(clss)
where C* is set of problematic outputs, such as repeated n-grams. The loss considers an N-step sequence generated from the model from 8, and penalizes repetitions. Although this regularization term performs well in practice, it relies on a heuristic that repetitive text unnatural, which does necessarily hold universally.
However, the idea of sampling a sequence from the model and including that sequence the loss is incorporated in SequenceMatch.
I EXAMPLES
In this section give the first few samples from the evaluation set, with cherry-picking, for the openwehtext task and the SequenceMatch objective. Note that we strip newlines in the examples page. Furthermore, several unicode characters
and generations in order present them were generated as random tokens that we cannot represent in the snippet. We label them (U+308A). Cyrillic characters were generated that also cannot be represented, label them [ctre] and [nasa] in the samples.
In these examples, we take the prompt sequence and change the last token random token drawn from the dataset. We see that the SequenceMatch model is able to utilize the <bkspc> token immediately to remove the spurious token. The only case where this does not happen for the prompt
recount is not automa tic, c, operat ons, where the random token does make semantic sense, and the model continues by attributing this to a quote from an operations manager.
20

---

Table 8: Model Prompts and Completions for the SequenceMatch trained model. We add a random token at the end of the prompt and observe the behavior of the generated sequences.
Prompt
Completion
<bes? Port-ac-Princo, Baiti (CHN) -- Eartheuske victina, weithing in pain and grasping life, watched dostors and nurses salk awey from field hespitel Priday nagh. after Belgian aedical Lean evacualed the area, saying it was concerrad about security. The daciaisa left CMN Chiof Hodical correspandant Sanjay Supta ax the only dector at the hospical to get the pet ienta through nigh.. em initially seported, based conversal iona with doctors, that the United Nations ordezed the Beigian First Aid and Support Tean to evanmate. Hoveuut, Belgian thisf Cooedinatio Geert Gige, a docsor who was at the hespital with 60 Belgian medical persunnel, seld it his decision to pull the tean ouz for the aight. Gifa sald ha zequasted U.N. security parsonnal to staff the huspital avernight, but sax told that peacekeepers would only be wble to evacuate the Lean. Be said it was "Lough deciaion" but that he accested the U.N. offer to evacuste after Canadian nedical tean, also at the hospitall tal with Canadiar secucityasore
takape>torcaa made a sinilas deciaton. Be sald the military reaponse to the eart'iguake had been except ionel and be was proud to have worked with then. Bija had proniaed Lhe mayar of Post au Pu-nei a secund lield huspital for Friday
nicht. His medical team ataffed the hespital fron 6 p.a. until about 10 p.o. Friday. But no one cane Friday night and there wannt even semurity tean at the alle when the nedical Lean left. Sone palienta showed sigus of serious Laturian that wara left untreated and an eldarly wanan is basely conseicus. The hospital was in the wurst hit area of the city, and its inhabicants are spending the night in the zubble in the aame area. the were cold Chat thay canl protuct sure they could protect the patients. And
of the
" di's said. "Thay werent some sere, you know, just barely slive as this stage and they walk out and Lawy are actacked, thwy would never kaow what happaned. " Gi Gija, describing the lout "grief," said he had hoped to do sonething aboot getting the
<bee> Forner secretary of state Hillary Clinten mosts voters at campaign rally In St. louls on Saturday. (Kelina Mara/The Kashingten Posti Denocratic trent-runcer Hillazy Cliatea was shoad by slin nargin in Missorei on Modnasday, but the Sen. Barnie Sandezs of Vermon would aesk seccunt. The delay postpaned definitive ansver to whetacr Clinton had made a clean sweap of five big prinariva on Tueaday night. Even if she does nut pewaail in Missouri, has otlar victorias push her claser to the Democratic presidential aonination even the considerably weakened Sanders voxed to press cn with his insurgent campaign.
manager Michael Helaughlin caid. Sanders must ciret tile a sequest for one with the atate elections hoard. The requeats mast be filed by noon Friday and paid for by the and of the day on Hoaday, The Rissouri razo will linger as a sign of Sanders's politics. vianility even atter his latest losses. Sanders did much better than polls had predicted in Missouri, whare Clinton maintaina glose ties to the Hissouri Denccratic Party aptablistment and retzias the leyalty of mach of the atacels aupezdellgaale e electorate. Clinten's a perfermene Friday in connecticus, where she breathing roon it needs to start proparing for the general election. [Clinton gcuiasa to bey wina in four large atates; Both Clinton and Sanders arqued that the latest contests showed that Tuesday night's results merely addad to their delegste lead and they dida't provids game-changing test. The largs contests in the South, East and Kidwast auggesied that Sandera still has a shance co compete racionally, while Cliaton can mobilige qreater suppozt as she zurna to canpaigning in noow stales with
remained in Limbo pencing werd whether rival
double digits, may have civen her campaign the
Clinton von big in Plosida, North Caroline and this, while claining a nes nercowes victory in illinois. In Hissouri, with 100 parcant of preciacta reporting, clinton was ahead 210, 502 votes to 309,07., With disfarence of less than percent, state officiala hold off calling the race. A recouat is not autonatic, operations
<bos> The opinicns expressed colunnists their and not represent the viexs at Townhall .com. You have to give Fresident Baraes obama credit tor one thing: consistency. Nothing is aver his fault. Nothing will ever ba his rault. Faulting Fox News and the american people, on the otaer tand, now that's s ditterent story. Do you rementer when obana traipsed stound the country and dosperasely pisaded with imericans to vosc for Hillary Clinzon bocause his sgenda and his logscy vere or the ballot? He made a siniler pitch bofore the laeklag his pacty took in the 2014 congressional electione. Yet did he with
<akepe> American people. Be didet recognire the failures his big-rovernmont policies. so far so good for Dhanad legacy, his progeny, this last presidentia. election have aot mad: their way into the Oval ofeice. "Thi election was a turning point, a cocisive monent, determined noment tast nears xe cant go back the policier that got here. Its time turn the page, " ha said in an intervicw wish Arablyad Yahya Al-faliuti. note-to-selt nemo, Osama wrote: "Mtllary Clinton lost the election because of me, " when pressed about how American votersdesize for polieies that are more line with his aig-geverament presideney, Obana blamed taeir intormation tran roslization, a Trunp- indured convarsion. noment, think aqain, It4 been part and parcel at the leftd Nerldview ever since polls vare first profected on than
tar the lessone
scknewlodes after this 2014 failing that had anything he ow up to his Leading role in last nonth's presisential election? Lotts rewind the cape further, to Obana's ss reaction to his pasty's atuaring dafeat in the 2010 congressional elections, whith was largely about onanacare. He dide't acknowlesge any persoral culpacility ter viciting that monstrosity the (U+3032)
Jocs
people who "rigne-wing mecia." and it you think this is a sudson
toothall rield sereen
<boss RIGRANG is one of those musical tiee that transcende language. It's one of those rase groupa that both innovates and defines the direction ion a genre takes, Covering sound that includes hip hop, RSB and electronic dance, RTCHANG and
Cokepc> strenned in with RIGHANG snuggie shirts and shirts featuring an, "OP, Tamyarg and Daesung. It was no surpeise that the ine jorityy of the masic being played outside venue agent most of
BIGBAM3' hits well covers G-Dragon's night standing
solo acts (G-Bragor, T.O.P, "seyang, Seungri have left a mesical imprint that has atteeted the global music nacket. In ract, ever. Dipio, household name in 808, worked with G-Dragon and T.0.P tor their rap albun, So when the band announced its world tour to pronote the release ot its third toll-longsh studio sibun MADS atter 3 yeaz histus, tans lost their minds 1 including myselt. in tast, tickets for each ot BIGBANS' s North American lags aold out, Ay a result, was lucky enough to vitness this larget-than-lite Korean pop group perforn ceuple Saturday sights ago oct. 10 the Prudential Center Newark, NJ. As I waited in Line so enter the venue wich ny friende, moha of fans [ctre]
feesung)
solo releases.
main floor nusic permested the crowds. While other ssags were being played, the main tocus was on BIGBAMe's ow masic. I tound nyselt noving in time to the dance noves that flowed in smooth, provocat ive sexual choreography that found 3-Dregon snapping regel
his tingers and exeeging his knees while TOP remeined stationary stance in a white blush blush jacket. As Baesung appeared on stage, the tloor broke into a shriet of chants: ADae dee! hae dae!" As the nement passed and heesung climbed a scattolding with blue 1ight backorop, the crowd screaned again, Arae dae! Bae dse!" As the chantss echoed over and over again,
<boss 1977 I know. That's what you' se seying right row. WWHATP! STSNEY BAB A DONUT SUNDAE AND I DIDN'T KRCK aBour 1921* Bon do I know you' su that? Recsuse that's exentlly what
<akapu> and fresh topping or twal, the house made vanilla ins crean and the Baicksedbodle Milkahakke The $7.00 Donu, Sundae aest a Lousernade vanilla icw crean topped with chocolate covered flaces, chopped bits of fudge, salnata fon think), a generous anoant of shipged crean, the choice of mini or janbo donat, and chocolate or steamberry sysup drizele. And did I nencion CuncoATe. COVERRD PLAKE5712! Be prepared to shell out between $7 and 58 for this nega Donut Sundam. But you'll probably find yourself licking your fingers of that heavenly shocolate flake as you down the treat, so I'd say itfa worth it. At least oace. Vep, there it is on the fee crean Parlor neno nex. My nouth is watwring, just cemetbering all shose anaxing chouclate flakes! Do you love chocolste tlakes? who will the tirst give this sundse a try?
saying when Tirs tel anssing nPR photoogagg ographer who's fringing swescne) spotied this at the Dlaza Iow Crean Parlor in the Magic Kingdon this wosk! Sut it's 08. Iefa brand new I not even on the meno yet I so dide't maas out on too much of the nonot Sundan 1: feepan, And long ane! The Main Strees Plase Ice Crean Main Street USA and Fonozroxland, just before you get to Cinderella Rest le. And the sundae joins a feu other must havw Lreals the Yoe Crwan Parlor's awnu. including the house nade iow crean canckich (preterably ordered with a cnissled sauce(sess]
hoping that Lifespan
Parlor can be found at the intersection


Reviews:
[{"review_id": "w7p4l7GDRA", "reviewer": "Reviewer_TvsS", "summary": "This paper introduces SequenceMatch - a novel minimization objective for training autoregressive models.  The proposed approach trains using the chi^2 divergence rather than the standard KL maximum likelihood (ML) objective.  An estimator for the loss is defined and a training algorithm is given.  A backspace token is added additionally to account for the model generating more OOD sequences given the changed objective.Results are provided for fine-tuning on a math dataset and OpenWebText generation", "questions": "* Can the authors clarify the Figure 1 example? My intuition is that the MLE should come from KL(p_{data} | p_{model}), which is defined in the example whereas the reverse KL(p_{model} | p_{data}) is not.  Isn't this suggesting the reverse KL is desired?\n* There is an implicit assumption in this work that the KL divergence is not a good metric because what we desire is for the model not to generate when the true data distribution has probability 0.  The work does not discuss the opposite, however where the data distribution has non-zero mass, KL minimization will encourage the model to always try to match the distribution - an explicit advantage of KL.  Without minimizing KL my concern is that we do not cover the full data distribution.  Explicitly, to address the main metric of interest in 2.1.1, implicitly the reverse KL would be a good choice to optimize.  This can be a problem especially for a large model or small data.\n* Given that the new metric may not cover the full distribution as well as KL minimization evaluation on retrieval or Q/A tasks where information is needed - will further improve the paper.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The proposed work tackles an important problem in the generation on OOD sequences and proposes a new approach which the authors derive and give a practical estimator for.  The ideas were studied in prior VI and generative model literature but appear to be new for language models - the application in this work.\n* It is appreciated that the authors have suggested a novel theoretical approach demonstrating that one does not need to do any variational bound, nor adversarial training to compute the loss.  This makes the proposed approach easier to implement and use.  The authors also derived an empirical estimator for practical purpose.  The idea of using the backspace to handle the generation of more OOD sequences is also good, which although the proposed approach introduces a new problem of more diverse generations, the additional backspace helps address this.\n* Overall the paper is well-written and motivates itself well from prior literature in imitation learning.", "weaknesses": "* The authors propose using the chi-sq divergence but do not motivate using the chi-sq over other f-divergences only citing its use in prior works.  A more natural divergence based on f-divergences and shortcomings of KL is the Jensen-Shannon (JSD), which also has the benefit of being symmetric and adds the reverse KL.  Why have the authors not compared with other divergences or why did these divergences not perform well?\n* The proposed work provides an estimator but does not show any properties of the new estimator (consistency, unbiasedness, etc.).  Historically, the MLE has been nice properties, but it is unclear whether Eq (4) has any nice properties with relation to the true divergence. \n* Performance of the proposed approach does not perform much better than the MLE except for MAUVE, when the data does not appear to be OOD (OpenWebText).  Additional experiments on OOD datasets (would artifical noise)   would supplement the results and show better performance potentially.\n* The SequenceMatch approach is relatively slow taking 1.5-8x the training time.  Due to the number of gradient updates, it may also be prohibitively expensive for full-finetuning.  However, this is not discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OIIpZgSQ5U", "reviewer": "Reviewer_n9EH", "summary": "This paper formulates autoregressive sequence generation as an imitation learning (IL) problem. To tackle the compounding error issue brought by the original MLE objective, it minimizes the occupancy divergence between the sampled sequences from the model and the data distributions. The paper further proposes a masking scheme that allows generation with a backspace action.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper offers a novel perspective for sequence modeling by formulating it as an IL problem. It tackles the error compounding issue, a significant drawback of sequence modeling, by adopting a divergence minimization approach.\n2. The backspace action is novel for sequence modeling. Allowing backtracking during decoding may greatly benefit tasks in reasoning and planning.\n3. The experiments demonstrate using backspace improves the accuracy and detects OOD cases.", "weaknesses": "1. The authors only present results on two tasks. It would be more convincing to add more results on, e.g., summarization, translation, and more complicated reasoning tasks.\n2. The method induces nonnegligible training overhead due to sampling trajectories and using a complex loss objective. Also, using backspace introduces some inference overhead -- is the case of rolling back a long segment very unlikely?\n3. The proposed formulation in Sec 3 seems to be an application of Garg et al. (2021) to the case of sequence modeling. May authors elaborate the technical novelties w.r.t. Garg et al. (2021)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1yeImbvzww", "reviewer": "Reviewer_roYx", "summary": "The paper addresses the problem of learning autoregressive models for (discrete) sequence modeling. It identifies two drawbacks of traditional maximum likelihood approaches: Firstly, such techniques, like behavioral cloning, allocate weights to sequences based on their prevalence in the training set. They do not consider the problem of guiding the autoregressive model when it starts to be out-of-distribution. To tackle this issue, the authors draw inspiration from Garg et al. 2021 and put forth a non-adversarial objective aimed at minimizing multiple divergences. A distinguishing feature from Garg et al. 2021 is their extension of the methodology to infinite-dimensional state spaces. The second drawback is that classical auto-regressive methods can go OOD by predicting bad tokens. To address this, the authors introduce an innovative approach of incorporating a \"backspace\" token, which has the capability to erase the preceding token. To facilitate the model in learning when to generate this backspace token, the authors suggest the introduction of noise into the training sequences. They then enhance these sequences with the backspace token, employing the modified sequences as training data. Additionally, they present a systematic method to process the backspace tokens in transformers using masking. This ensures that the renowned high-speed learning capabilities of transformer models on GPUs remain uncompromised.\n\nThey compare their approach with classical approaches on an arithmetic task, and on text generation, with positive results showing the effectiveness of the two components.", "questions": "* Please better identify what is the contribution w.r.t Garg et al. 2021", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and addresses a significant and relevant issue. It offers a solution designed to minimize various divergences associated with sequence generation. Notably, the authors introduce the innovative concept of a \"backspace\" token, alongside presenting a proficient method to seamlessly incorporate this token into the training set. Furthermore, the experimental outcomes presented are both compelling and convincing. The contributions may be of the interest of a large audience.", "weaknesses": "The paper proposes two distinct contributions. Firstly, it extends the work of Garg et al. 2021 to handle an infinite-dimensional state space. However, based on my understanding, this extension doesn't seem particularly pertinent to the problems explored in the experimental section. While I'm somewhat familiar with Garg et al.'s work (having read it for this review), the nuances differentiating the two papers aren't immediately clear to me. I'd encourage the authors to better identify these differences more explicitly. While Garg et al. 2021 delves into reinforcement learning, the authors of the current paper narrow their focus to sequence generation, which can be seen as a simpler challenge than the broader realm of RL. The originality of this contribution remains somewhat ambiguous to me.\n\nThe paper's second contribution (introducing backspace) is more algorithmic and makes sense, especially given the efficient implementation strategy the authors have introduced. However, this contribution stands independent of the first, resulting in a paper that seems to amalgamate two separate ideas. While the combined nature of these contributions makes the proposed model efficient, it also emphasizes that individually these contributions are not so strong. \n\n(Small remark: bibliography is in the supplementary material and has to be moved back to the main paper)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HaiQU2IBS3", "reviewer": "Reviewer_aeRK", "summary": "This paper introduces SequenceMatch to alleviate the compounding error problem in large language model generation.\nFirst, it introduces a backspace action token to delete the inappropriate token generated in the last step. Second, it introduces a new training objective that minimizes the occupancy divergence between the dataset and the learned model, instead of simply maximizing the likelihood of the ground truth next tokens in the output distribution. Experimental results show that SequenceMatch can improve the accuracy in the arithmetic add-or-sub-in-base sub-task of the match dataset, and improve the mauve score in the openwebtext dataset.", "questions": "Does the method affect the combinational generalization? Given the famous avocado armchair as an example. Assume we have a training dataset that contains avocados, and different types of armchairs but doesn’t contain avocado armchairs. Does the method discourage the model from combinationally generalizing to avocado armchairs, as it is not included in the training set?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The motivation is convincing\n- The method is novel\n- The paper writes well", "weaknesses": "- The experiment section is not so convincing. The method is evaluated mainly in two settings. In the first setting, the method shows a significant improvement on a subtask of the math dataset. But how about the other sub-tasks? We don’t know if the method can generalize well on other tasks. In the second method, the method has a slightly better mauve score, but the perplexity score drops by a large margin. How can we know that this method indeed improves the model generation?\n- The method relies on negative sampling, but there is no reasonable negative sampling strategy provided for open language tasks. This paper provides two negative sampling strategies: random noise and ground-truth noise. As the authors also mentioned in Sec. 6.1, the ground-truth noise needs to be manually constructed for different tasks. The random noise simply samples other tokens in the vocabulary. Both strategies look hard to generalize to open tasks, as it is almost impossible to design ground-truth noise for all the tasks in the world, and the vocabulary for open tasks is too large (the whole token codebook) for the random noise to get meaningful negative samples easily. Thinking about applying SeqenceMatch to the pretraining of LLMs like Llama2, what negative sampling strategy should be used?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)