Thanks for your insightful review. Similarly to reviewer TvsS, you touch on some very important points relating to the tradeoff between different divergences. We answer your specific questions below:

"In the second method, the method has a slightly better mauve score, but the perplexity score drops by a large margin."

• We agree that the behavior of the perplexity is counter-intuitive. However, in our setting the perplexity does not necessarily correspond to the probability of generating a sequence. We use the term perplexity in the usual way: to denote the exponential of the average negative log likelihood of the next action. Usually the perplexity on the train set directly corresponds to the probability of generating in-distribution sequences. However, in the case with a backspace token, this is not necessarily true, since the probability of generating a sequence must be computed by marginalizing over all the possible sequences of actions (including backtracking via the backspace) that could generate the sequence.
• As an example, if we consider a very simple language with tokens ‘A’ and ‘B’, where the dataset consists only of sequences ‘AAAAA…’, we can generate an in-distribution sequence by following a policy of sampling A,B uniformly, and then choosing <backspace> if we last sampled a B. We will eventually always generate ‘AAAAA…’, but the perplexity on the dataset is not 1, as it would be for a simple autoregressive model that always generated ‘AAAAA..’. Indeed, a drawback of our method is that we lose the ability to compute the probability of generating a sequence. However, in practice these probabilities do not tend to be very useful for e.g. anomaly detection, so we think it is a good trade-off for the ability to backtrack.

"There is no reasonable negative sampling strategy provided for open language tasks."

• One possible sampling strategy is the uniform random strategy. As seen in figure 3 and table 2, this has advantages over no added noise. Figure 3 also shows that problem-specific noise can be advantageous. For the problem of open language tasks, uniform noise would be the default, but potentially there could be ways to develop tailored noise, although these are speculative for the time being. For instance, if we assume access to an LLM of similar size, we could use it as an oracle to generate eg incorrect French words in a translation task. We could also use crowd workers to generate text and record the complete generative process, including any backspaces used by the workers.

"Thinking about applying SeqenceMatch to the pretraining of LLMs like Llama2, what negative sampling strategy should be used?"

• As mentioned above, the random uniform sampling is a baseline approach which gives some advantage. Other approaches could be investigated, including using other models to generate plausible (but incorrect) continuation tokens.

"Does the method discourage the model from combinationally generalizing to avocado armchairs, as it is not included in the training set?"

• This is a great question. Unfortunately, we don’t have a way to answer it theoretically; at least, we’re unaware of a mathematical formalism of the combinatorial generalization phenomenon. Intuitively, we think it’s likely that the loss encourages more mode-concentrating behavior in exchange for increased probability of staying in-distribution, as discussed in the response to reviewer TvsS. This would lead to decreased levels of ‘combinatorial generalization’. Of course, in the setting of language models, we could argue that hallucinations are an example of incorrect generalization, where a model is happy to continue generating details of events that did not happen. Perhaps in this setting, or settings such as question answering, it would be better if the level of generalization was lower.

Please let us know if there are any remaining questions; we would be happy to discuss them!

Thanks for your thoughtful and comprehensive review. Your main question was about the relation of the two contributions, and the novelty of the approach compared to Garg [2021]. We hope to have answered this question in the global response.

Please better identify what is the contribution w.r.t Garg et al. 2021

• See global response

Please let us know if there are any remaining questions or aspects of the questions we have not addressed, and we would be very happy to discuss them!

Thank you for your thoughtful and detailed review. You raise several excellent points which we answer here.

"Why have the authors not compared with other divergences or why did these divergences not perform well?"

• On prototyping iterations of the project, we tried different divergences and observed that they did not work as well as the $\chi^2$-divergence. In particular, we observed that the Q-values (logits) would become very large and training would be unstable for divergences other than $\chi^2$. Previous work showed that the $\chi^2$ divergence had the strongest performance in high-dimensional tasks (e.g. appendix B.2. in [Garg 2021]). Furthermore, other work such as [Al-Hafez et al 2023] has provided theoretical justification for this improved performance, namely the fact that the optimal Q-values are bounded.
• From a practical point of view, the reverse KL divergence and JS divergence pose algorithmic challenges, since the function $\phi(x)$ in equation 4 is $1 + \log x$ and $\log (2 - \exp(-x))$, which are only defined for $x > 0$ and $x > -\log 2$ respectively. This would require constraining $\ell(s,a) - \gamma V(s’)$ for all states, actions, next states $s,a,s’$. It’s not obvious how to algorithmically enforce such a constraint given that we are parameterizing $\ell$. Another option is to form a relaxation for $\phi$ with e.g. a very large negative value where $x$ is out of the domain of $\phi$, but this makes optimization very unstable. We are attempting ablations with different divergences, using the relaxation-based method, which we will hopefully have available by the end of the author-reviewer discussion period.

"Does not show any properties of the new estimator (consistency, unbiasedness, etc.)"

• Thank you for pointing this out. The estimator in equation 4 is a plug-in estimator for the population objective stated in the previous section. As such, under modest conditions it is unbiased and consistent, in the sense that the expected value of ${\hat J}(\ell_{\theta})$ is $J(\ell_{\theta})$ and ${\hat J}(\ell_{\theta})$ converges in probability to $J(\ell_\theta)$ as we increase the number of sequences used in the estimator. For simplicity in equation 4 we present the estimator using a single sequence. In practice we always average the loss over several sequences, with a batch size of 64 typical. Using conditions such as boundedness of the logits and $\phi = x^2 - x^2/4$ for the $\chi^2$-divergence, proof of unbiasedness follows from linearity of expectation, and consistency from the central limit theorem. We will include these proofs in the next version of the appendix.

[Continued in next reply]

Thanks for your helpful review. We answer your questions below.

"It would be more convincing to add more results on, e.g., summarization, translation, and more complicated reasoning tasks."

• See global response

"The method induces nonnegligible training overhead due to sampling trajectories and using a complex loss objective"

• We give some numerical details on the training overhead in the appendix, section F. The overhead of the loss itself is mainly due to the loss of specialized cuda kernels for causally-masked attention. The overhead of the sampling is fundamentally unavoidable, however. It can be amortized by keeping a replay buffer of previously-generated samples and using those stale replays during training. Since the loss approach is off-policy, using stale replays is valid. If this approach is deployed at a large scale during pre-training, we could also parallelize the generation during training--one machine or set of GPUs could be used to continuously generate sequences, and the parameters for the generation machine updated periodically.

"Also, using backspace introduces some inference overhead -- is the case of rolling back a long segment very unlikely?"

• Yes, it’s unlikely. In fact, even under high levels of noise, the generated sequences do not contain many backspaces. With 20% of tokens subject to additional noise, the rate of backspaces in the arithmetic task was around 1.5% of all actions for the SequenceMatch-trained model. It was rare to have more than one backspace in a row. On the other hand, we found that of the cases where backspace is used, it is around 90% accurate--it only removes a correct token 10% of the time.

"May authors elaborate the technical novelties w.r.t. Garg et al. (2021)?"

• See global response

If there are any remaining uncertainties, we are happy to answer them during the discussion phase.

The additional experiments are as follows, and will be included in the paper once we have more time to run additional hyperparameter sweeps and random seeds. Unfortunately we didn’t have time to do the non-bespoke noise experiments for the arithmetic tasks, although these will be included in the next version of the paper.

Opus_books en-fr

We implemented this translation task similarly to the arithmetic task in the main paper, with the prompt being the en ‘question’ and the completion being the fr ‘answer’. We use random noise tokens, with noise level 0.2. The BLEU scores were computed using the sacrebleu package. In the interests of getting the results before the deadline with our limited resources, we used a subset of the data consisting of examples where the en prompt was less than 64 tokens long and the fr completion was less than 64 tokens long. This was still a majority of the examples in the dataset. The BLEU scores were as follows:

MLE: $31 \pm 2$

BC: $34 \pm 2$

SM: $36 \pm 4$

We observe that the bkspc is used in generations to correct mistakes, such as in this completion:

en: 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<bkspc> rentrait dans son bureaut<bkspc>au, déplorant l’absence de Meaulnes.

Arithmetic__mul

This task was implemented exactly as for the arithmetic addition task. For bespoke noise, noise level 0.2, over two random seeds, the accuracies were:

MLE: $0.49 \pm 0.04$

BC: $0.5 \pm 0.03$

SM: $0.56 \pm 0.04$

As before, we see a significant improvement for SequenceMatch, although in this case the improvement for behavioral cloning from MLE is not very large.

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 a relatively low rate of accuracy, and so this experiment may not tell us very much. For bespoke noise, noise level 0.2, the accuracies were:

MLE: $0.04 \pm 0.03$

BC: $0.06 \pm 0.03$

SM: $0.08 \pm 0.04$

Additional changes

We updated the paper to include the bibliography. As pointed out by reviewer roYx, we had accidentally included this with the supplementary material in the original submission.