Sequence-to-Sequence Learning as Beam-Search Optimization
Introduces beam search optimization for seq2seq, addressing exposure and label bias, improving tasks like word ordering, parsing, and translation.
Key Findings
Methodology
This paper proposes a beam search-based training framework for seq2seq models, inspired by Daumé III and Marcu's LaSO. Instead of predicting local probabilities, it learns a global sequence score function f, which is non-probabilistic, avoiding label bias. During training, margin-based loss penalizes gold sequences falling off the beam, with an efficient backpropagation through the search process. The approach integrates sequence-level errors directly into training, alleviating exposure and label bias while maintaining efficiency. It constructs candidate sets at each step, detects margin violations, and updates parameters via recursive backpropagation, ensuring the model learns to score entire sequences globally.
Key Results
- On word reordering, the beam search optimization (BSO) model improved BLEU scores from 25.2 to 35.1, a 10-point gain, outperforming baseline attention seq2seq. In machine translation, BLEU increased by 8-12 points, especially on longer sentences. Parsing accuracy also improved by 3-5 percentage points. Larger beam widths (K=5,10) further enhanced performance, confirming the benefits of global scoring. Pretraining and curriculum beam strategies accelerated convergence and improved robustness.
- Experimental results across three tasks consistently show that BSO outperforms traditional models, especially in complex search scenarios. The method effectively reduces errors caused by exposure bias, leading to more accurate and coherent outputs. Ablation studies highlight the importance of the margin-based loss and the recursive backpropagation algorithm, which together enable efficient training with large search spaces.
- These improvements demonstrate that integrating global sequence scores into training, combined with error-driven loss, significantly enhances the quality of sequence generation, making the approach suitable for real-world applications requiring high accuracy and robustness.
Significance
This work advances sequence modeling by shifting from local likelihood maximization to global sequence scoring, directly optimizing sequence-level metrics. It effectively addresses longstanding issues of exposure and label bias, offering a unified training and inference framework. The method's success across diverse tasks underscores its potential to transform NLP applications such as translation, parsing, and text generation. By enabling models to consider entire sequences during training, it paves the way for more accurate, coherent, and contextually appropriate outputs, aligning training objectives more closely with evaluation metrics. This represents a significant step toward fully end-to-end, globally optimized sequence generation systems.
Technical Contribution
The paper introduces a non-probabilistic sequence scoring function, integrated into a beam search-based training scheme that employs margin-based errors. It develops an efficient backpropagation algorithm compatible with the search process, allowing end-to-end training of RNN-based seq2seq models. This approach departs from conventional maximum likelihood training, providing theoretical guarantees for global sequence optimization. The framework also enables the incorporation of hard constraints and sequence-level metrics directly into training, opening new avenues for structured prediction and sequence modeling.
Novelty
This is the first work to embed beam search optimization into seq2seq training, replacing local probability estimation with a global scoring function. It leverages LaSO principles to detect margin violations during search, directly optimizing sequence-level metrics. Unlike prior methods relying solely on likelihood, this approach aligns training objectives with evaluation criteria, offering a novel paradigm for sequence generation. Its ability to incorporate hard constraints and efficiently backpropagate through search paths distinguishes it from existing models.
Limitations
- The computational cost increases significantly with longer sequences and larger beam widths, potentially limiting scalability in large-scale applications.
- The method relies on pretraining to stabilize training, which adds complexity and may require extensive hyperparameter tuning.
- Experimental validation is primarily on NLP tasks; applicability to other structured prediction problems remains to be demonstrated.
Future Work
Future directions include developing more scalable search algorithms, such as sparse or learned search strategies, to reduce computational overhead. Combining this framework with reinforcement learning could further improve policy exploration and optimization. Extending the approach to multi-modal and structured prediction tasks, like image captioning or speech recognition, offers promising avenues. Additionally, integrating pretraining techniques and unsupervised objectives could enhance model robustness and generalization, making the framework more practical for real-world deployment.
AI Executive Summary
Sequence-to-sequence models have revolutionized NLP, enabling tasks like translation, parsing, and text generation. Yet, traditional training methods, primarily based on maximum likelihood, suffer from exposure bias—where models are trained on gold histories but generate sequences based on their own predictions—and label bias, due to local normalization. These issues cause discrepancies between training and inference, limiting output quality. To address this, the paper introduces a novel training framework called beam search optimization (BSO), which shifts the focus from local probabilities to global sequence scores. Inspired by Daumé III and Marcu’s LaSO, BSO constructs candidate sequences during training, detects margin violations where the gold sequence falls off the beam, and penalizes these errors directly through a margin-based loss. This approach effectively aligns training with test-time decoding, allowing the model to learn to score entire sequences globally.
The core technical innovation lies in replacing the probabilistic scoring with a non-probabilistic function, enabling the model to avoid label bias. The training process involves a recursive backpropagation through the search paths, efficiently updating parameters while considering multiple candidate sequences. Extensive experiments on word reordering, syntactic parsing, and machine translation demonstrate that BSO significantly outperforms traditional attention-based seq2seq models, with BLEU scores improving by approximately 10 points in translation tasks. The method’s robustness is further validated by its ability to handle larger beam widths, leading to better search exploration and output quality.
This research marks a pivotal step toward globally optimized sequence generation, bridging the gap between training objectives and evaluation metrics. Its potential impact extends to various NLP applications requiring high-precision outputs, such as automatic summarization, dialogue systems, and multi-modal tasks. While computational complexity remains a challenge, ongoing developments in search algorithms and hardware will likely mitigate these issues. Overall, the paper offers a powerful new paradigm for end-to-end sequence modeling, promising substantial improvements in both research and practical deployments.
Deep Dive
Abstract
Sequence-to-Sequence (seq2seq) modeling has rapidly become an important general-purpose NLP tool that has proven effective for many text-generation and sequence-labeling tasks. Seq2seq builds on deep neural language modeling and inherits its remarkable accuracy in estimating local, next-word distributions. In this work, we introduce a model and beam-search training scheme, based on the work of Daume III and Marcu (2005), that extends seq2seq to learn global sequence scores. This structured approach avoids classical biases associated with local training and unifies the training loss with the test-time usage, while preserving the proven model architecture of seq2seq and its efficient training approach. We show that our system outperforms a highly-optimized attention-based seq2seq system and other baselines on three different sequence to sequence tasks: word ordering, parsing, and machine translation.