SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with Backtracking

2023/06/08 by Chris Cundy, Stefano Ermon, Cundy, Chris +1 · 4 voices · 7 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Autoregressive model #Backtracking #Computer science #Divergence (linguistics) #Explainable Artificial Intelligence (XAI) #Machine learning #Mathematics #Natural Language Processing Techniques #Security token #Sequence (biology) #Statistics #Topic Modeling #cs.AI #cs.LG

paper · pdf · doi:10.48550/arxiv.2306.05426

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2023/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 architectural changes. We identify the SequenceMatch-χ² 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.

Cited by

• ERGO: Entropy-guided Resetting for Generation Optimization in Multi-turn Language Models
• Implicit Reward as the Bridge: A Unified View of SFT and DPO Connections
• Learning Safety Constraints for Large Language Models
• Structured Agent Distillation for Large Language Model
• The Bridge-Garden Dilemma in LLM Distillation: Why Mixing Hard and Soft Labels Works
• Thoughtful, Confused, or Untrustworthy: How Text Presentation Influences Perceptions of AI Writing Tools
• LLMs are Greedy Agents: Effects of RL Fine-tuning on Decision-Making Abilities

Discussions

• Giving LLM’s a <Backspace> Token [hn, 82 points, 25 comments]
• arxiv.org/abs/2306.05426 [bsky, 6 points, 0 comments]
• SequenceMatch - Imitation Learning for Autoregressive Sequence Modelling with Backtracking [lemmy, 4 points, 0 comments]
• Kinda reminds me of this from a while back— wonder if they cite it “The IL framework also allows us to incorporate backtracking by introducing a backspace action” arxiv.org/abs/2306.05426 [bsky, 0 points, 0 comments]

Related

• Autoregressive Knowledge Distillation through Imitation Learning
• Approximate Distribution Matching for Sequence-to-Sequence Learning
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
• Unifying Autoregressive and Diffusion-Based Sequence Generation
• An Imitation Learning Curriculum for Text Editing with Non-Autoregressive Models