# A Continuous Relaxation of Beam Search for End-to-end Training of Neural Sequence Models

arXiv: https://arxiv.org/abs/1708.00111 · HTML: https://mlsanity.com/paper/1708.00111/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2017.

## Built on by (most cited first, 10 of 10)

- [Text Generation by Learning from Demonstrations](https://mlsanity.com/paper/2009.07839/) (2020)
- [Monotonic Differentiable Sorting Networks](https://mlsanity.com/paper/2203.09630/) (2022)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [Learning Beam Search Policies via Imitation Learning](https://mlsanity.com/paper/1811.00512/) (2018)
- [Incremental Beam Manipulation for Natural Language Generation](https://mlsanity.com/paper/2102.02574/) (2021)
- [Beam Tree Recursive Cells](https://mlsanity.com/paper/2305.19999/) (2023)
- [Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms](https://mlsanity.com/paper/2410.19055/) (2024)
- [Spend Search Where It Pays: Value-Guided Structured Sampling and Optimization for Generative Recommendation](https://mlsanity.com/paper/2602.10699/) (2026)
- [Learning to Summarize Videos by Contrasting Clips](https://mlsanity.com/paper/2301.05213/) (2023)
- [Learning Energy-Based Approximate Inference Networks for Structured Applications in NLP](https://mlsanity.com/paper/2108.12522/) (2021)

## Abstract (arXiv)

Beam search is a desirable choice of test-time decoding algorithm for neural sequence models because it potentially avoids search errors made by simpler greedy methods. However, typical cross entropy training procedures for these models do not directly consider the behaviour of the final decoding method. As a result, for cross-entropy trained models, beam decoding can sometimes yield reduced test performance when compared with greedy decoding. In order to train models that can more effectively make use of beam search, we propose a new training procedure that focuses on the final loss metric (e.g. Hamming loss) evaluated on the output of beam search. While well-defined, this "direct loss" objective is itself discontinuous and thus difficult to optimize. Hence, in our approach, we form a sub-differentiable surrogate objective by introducing a novel continuous approximation of the beam search decoding procedure. In experiments, we show that optimizing this new training objective yields substantially better results on two sequence tasks (Named Entity Recognition and CCG Supertagging) when compared with both cross entropy trained greedy decoding and cross entropy trained beam decoding baselines.