Parallel Iterative Edit Models for Local Sequence Transduction

Abhijeet Awasthi, Sunita Sarawagi, Rasna Goyal, Sabyasachi Ghosh, Vihari Piratla

Abstract: Abhijeet Awasthi, Sunita Sarawagi, Rasna Goyal, Sabyasachi Ghosh, Vihari Piratla. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).

2019.

Introduction: The Bottleneck of Sequential Generation

Most sequence-to-sequence (seq2seq) tasks, such as Grammatical Error Correction (GEC) and machine translation, have traditionally relied on auto-regressive Encoder-Decoder (ED) architectures. These models generate output tokens one by one, where each prediction depends on all previously generated words. While this approach captures complex dependencies, it creates a significant computational bottleneck, particularly as sentence length increases.

For Local Sequence Transduction (LST) tasks—where the input and output sequences are largely similar and well-aligned—generating an entire sentence from scratch is often inefficient. The Parallel Iterative Edit (PIE) model addresses this by reimagining transduction as a parallel sequence labeling problem, achieving massive speedups without sacrificing accuracy.

Methodology: Transduction as Labeling

The PIE model shifts the paradigm from generation to labeling. Instead of producing a new sequence, it assigns an edit label to every token in the input. This approach utilizes several key innovations:

  1. Edit-Based Vocabulary: Rather than a massive word-level vocabulary, PIE predicts from a compact set of edit operations: Copy, Delete, Append(word), Replace(word), and Transform (e.g., changing "go" to "went"). This reduces the output search space and improves generalization for structural patterns.
  2. Parallel Decoding with BERT: PIE employs a bidirectional BERT encoder to process the entire sentence simultaneously. To handle insertions and substitutions effectively, the model uses a factorized logit architecture, leveraging pre-trained word embeddings to "warm-start" specific word predictions.
  3. Iterative Refinement: To compensate for the lack of sequential dependencies in parallel decoding, PIE feeds its own output back into the encoder for multiple rounds (typically 2-4). This allows the model to resolve dependencies that emerge after initial corrections, such as adjusting a preposition after a verb tense change.

Performance and Efficiency

The primary advantage of the PIE framework is its efficiency. Because it decodes in parallel, its latency remains relatively flat even as sentence length increases. This results in a model that is 5x to 15x faster than competitive Transformer-based models.

Decoding time (ms) on a log scale vs. average sentence length. PIE models exhibit sub-linear scaling compared to the linear growth of auto-regressive Transformer models.

Despite the shift to a non-autoregressive architecture, PIE maintains high accuracy across various benchmarks. On the CoNLL-2014 GEC task, PIE achieved an $F_{0.5}$ score of 59.7, placing it on par with the state-of-the-art sequential models of its time.

Comparison of PIE against state-of-the-art models on CoNLL-2014 and JFLEG datasets. PIE achieves competitive F0.5 scores while maintaining significantly higher inference speeds.

Key Insights and Results

  • Iterative Gains: The iterative process is crucial for accuracy. The first round of editing provides the baseline correction, while the second round significantly boosts the $F_{0.5}$ score (from 57.9 to 59.5), proving that iteration successfully captures word dependencies.
  • Robust Generalization: Beyond GEC, PIE outperformed specialized models on OCR and spell-correction tasks, demonstrating its versatility as a general-purpose engine for local transduction.
  • Scaling: As shown in the decoding time analysis, PIE’s sub-linear scaling makes it ideal for real-time applications where low latency is critical.

Limitations and Future Work

While PIE excels at local fixes, it may occasionally miss "global" stylistic fluency compared to sequential decoders, as reflected in slightly lower GLEU scores. Furthermore, the current architecture is designed for local changes and is not yet suited for tasks requiring massive word reordering, such as translation between languages with vastly different syntax. Future research may explore incorporating limited reordering capabilities into the PIE framework to tackle more complex transduction tasks.

Summary updated

BibTeX
@inproceedings{awasthi2019parallel,
  author = {Abhijeet Awasthi and Sunita Sarawagi and Rasna Goyal and Sabyasachi Ghosh and Vihari Piratla},
  title = {{Parallel Iterative Edit Models for Local Sequence Transduction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=QGxV_TerwfX},
}
Figure