# SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with Backtracking

**Authors:** Chris Cundy, Stefano Ermon  
**arXiv:** [2306.05426](https://arxiv.org/abs/2306.05426)  
**Date:** 2023-06-08  
**Summary page:** https://www.summarizepaper.com/en/paper/2306.05426v1/

## Key points

- The paper introduces a method called SequenceMatch to address compounding errors in autoregressive sequence generation.
- Autoregressive models often achieve low log-likelihood on predicting the next observation, which does not align with generating high-quality sequences.
- Maximum-likelihood objective weights sequences based on their frequency under the data distribution, leading to compounding errors during generation.
- SequenceMatch formulates sequence generation as an imitation learning (IL) problem to minimize divergences between autoregressive model-generated sequences and dataset sequences, including out-of-distribution (OOD) generated sequences.
- The IL framework incorporates backtracking by introducing a backspace action into the generation process, allowing the model to revert a sampled token if it takes the sequence OOD.
- SequenceMatch can be implemented without adversarial training or major architectural changes.
- SequenceMatch-$\chi^2$ divergence is identified as a more suitable training objective for autoregressive models used for generation.
- Empirical results show that SequenceMatch training improves text generation with language models compared to maximum likelihood estimation (MLE).
- The authors represent sequence modeling as a Markov decision process (MDP) and use averaging loss over each example's length to estimate consistency.

## Summary

The paper introduces a method called SequenceMatch, which addresses the problem of compounding error in autoregressive sequence generation. Autoregressive models often achieve low log-likelihood on the task of predicting the next observation, but this objective does not necessarily align with generating high-quality sequences. The maximum-likelihood objective weights sequences based on their frequency under the data distribution, without considering out-of-distribution (OOD) behavior. This leads to compounding errors during generation. To mitigate this issue, the authors propose formulating sequence generation as an imitation learning (IL) problem. This allows them to minimize divergences between sequences generated by an autoregressive model and sequences from a dataset, including OOD generated sequences. The IL framework also incorporates backtracking by introducing a backspace action into the generation process. This enables the model to revert a sampled token if it takes the sequence OOD. The resulting method, SequenceMatch, can be implemented without adversarial training or major architectural changes. The authors identify the SequenceMatch-$\chi^2$ divergence as a more suitable training objective for autoregressive models used for generation. They empirically show that SequenceMatch training leads to improvements over maximum likelihood estimation (MLE) on text generation with language models. In terms of methodology, the authors represent sequence modeling as a Markov decision process (MDP), where state and action spaces are defined along with dynamics and reward functions. They use averaging loss over each example's length to estimate consistency. Overall, SequenceMatch offers a solution to address compounding errors in autoregressive sequence generation by incorporating imitation learning and backtracking techniques. Empirical results demonstrate its effectiveness compared to traditional MLE approaches in text generation tasks with language models.