Optimal Completion Distillation for Sequence Learning

Sara Sabour, William Chan, Mohammad Norouzi

TL;DR

Optimal Completion Distillation (OCD) is a novel training algorithm for sequence-to-sequence models that replaces standard Maximum Likelihood Estimation (MLE). By using dynamic programming to identify all possible "optimal paths" to a target from any given mistake, OCD eliminates exposure bias and directly optimizes for edit distance without requiring complex hyperparameter tuning or pretraining.

What Problem Does This Paper Address?

Most sequence-to-sequence (seq2seq) models—like those used in speech recognition or translation—are trained using Maximum Likelihood Estimation (MLE) with "teacher forcing." During training, the model is given the perfect ground-truth prefix and asked to predict the next token.

However, this creates two major issues:

  1. Exposure Bias: During actual use (inference), the model doesn't have a "teacher." If it makes one small mistake early on, it enters a state it never saw during training and often spirals into further errors.
  2. Loss-Metric Mismatch: We usually evaluate these models using metrics like Edit Distance (Word Error Rate), but we train them to maximize log-likelihood. A model might be penalized heavily for a synonym or a minor spelling error that doesn't actually hurt the final utility.

Existing solutions like Reinforcement Learning (RL) or Scheduled Sampling often require "warm-starting" with MLE, are notoriously unstable, or require tedious tuning of mixing ratios and learning rates.

Methods

The authors propose Optimal Completion Distillation (OCD), which treats training as a distillation problem. Instead of forcing the model to follow a single ground-truth path, OCD teaches the model how to reach the target optimally from wherever it currently is.

The process follows three steps:

  1. On-Policy Sampling: The model generates a sequence (prefix) based on its current parameters. It is allowed to make mistakes.
  2. Finding Optimal Suffixes: For every prefix the model generates, the authors use an efficient dynamic programming algorithm (an $O(nm)$ variation of the Levenshtein algorithm) to identify the set of all "optimal" next tokens that would minimize the remaining edit distance to the target.
  3. Distillation: The model is trained to match a target distribution that puts equal probability on all these "optimal" next tokens.
Edit Distance Table for OCD

Essentially, if the model takes a "wrong turn," OCD doesn't just tell it what the original path was; it calculates the new best route to the destination from the current location—much like a GPS rerouting.

Datasets

The researchers evaluated OCD on two gold-standard speech recognition benchmarks:

  • Wall Street Journal (WSJ): A classic dataset for speech-to-text.
  • Librispeech: A large-scale (960 hours) dataset of read English speech.

They focused on "end-to-end" performance, meaning they did not use a separate language model to "clean up" the results afterward, which highlights the strength of the acoustic/sequence model itself.

Key Insights and Ideas

  • The "GPS" Analogy: Traditional training is like a student memorizing a specific route. OCD is like a student learning the map. If the student gets lost, they know how to get back on track because they've been trained on "off-road" prefixes.
  • Hyperparameter-Free: Unlike RL-based methods that require careful reward shaping or Scheduled Sampling which needs a decay schedule, OCD has no specific hyperparameters. In the limit, the temperature $\tau \to 0$ creates a simple, hard target distribution.
  • Efficiency: While it sounds computationally expensive to run dynamic programming for every sample, the authors show it has the same asymptotic complexity as the standard cross-entropy loss used in MLE, making it highly scalable.
  • Robustness to Beam Size: Interestingly, the paper finds that OCD-trained models are much more robust to changes in beam search size during inference, whereas MLE models often see performance degrade if the beam size is too large (a known symptom of exposure bias).

Key Results

OCD achieved state-of-the-art results for end-to-end models (without language model rescoring) at the time of publication:

  • WSJ: Achieved a 9.3% Word Error Rate (WER) and 3.1% Character Error Rate (CER), significantly outperforming MLE (10.6% WER) and Scheduled Sampling (10.2% WER).
  • Librispeech: On the "test-clean" set, it reached 4.5% WER, a 21% relative improvement over their MLE baseline (5.7% WER).
  • Generalization: OCD models showed a much smaller gap between training and validation error compared to MLE, suggesting the method helps the model generalize better to unseen data.
Training vs Validation CER for OCD and MLE

Limitations and Future Work

  • Metric Specificity: OCD is specifically designed for metrics based on Edit Distance. While this is perfect for speech recognition and certain types of translation, it's less clear how to adapt it for metrics like BLEU or ROUGE, which are more common in natural language generation.
  • Vocabulary Scaling: While the $O(nm)$ complexity is fine for characters or subwords, the authors note that for extremely large vocabularies (e.g., full words in machine translation), the $O(|V| \cdot T)$ memory cost for storing Q-values could become a bottleneck.
  • Cold Start: While the paper says OCD can be trained from scratch, most experiments still involve standard neural architectures. Exploring how OCD interacts with newer Transformer-based architectures (which were just emerging in 2019) was left for future research.

Summary updated

Abstract

We present Optimal Completion Distillation (OCD), a training procedure for optimizing sequence to sequence models based on edit distance. OCD is efficient, has no hyper-parameters of its own, and does not require pretraining or joint optimization with conditional log-likelihood. Given a partial sequence generated by the model, we first identify the set of optimal suffixes that minimize the total edit distance, using an efficient dynamic programming algorithm. Then, for each position of the generated sequence, we use a target distribution that puts equal probability on the first token of all the optimal suffixes. OCD achieves the state-of-the-art performance on end-to-end speech recognition, on both Wall Street Journal and Librispeech datasets, achieving $9.3\%$ WER and $4.5\%$ WER respectively.
BibTeX
@inproceedings{sabour2019optimal,
  author = {Sara Sabour and William Chan and Mohammad Norouzi},
  title = {{Optimal Completion Distillation for Sequence Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
}
Figure