# Machine Translation Decoding beyond Beam Search

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 53 references that are in the map.
- First posted on arXiv 12 Apr 2021.

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [An Actor-Critic Algorithm for Sequence Prediction](https://mlsanity.com/paper/1607.07086/) (2016)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [If beam search is the answer, what was the question?](https://mlsanity.com/paper/2010.02650/) (2020)
- [Minimum Risk Training for Neural Machine Translation](https://mlsanity.com/paper/1512.02433/) (2015)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [On the Weaknesses of Reinforcement Learning for Neural Machine Translation](https://mlsanity.com/paper/1907.01752/) (2019)
- [Reward Augmented Maximum Likelihood for Neural Structured Prediction](https://mlsanity.com/paper/1609.00150/) (2016)
- [Classical Structured Prediction Losses for Sequence to Sequence Learning](https://mlsanity.com/paper/1711.04956/) (2017)
- [Non-Monotonic Sequential Text Generation](https://mlsanity.com/paper/1902.02192/) (2019)
- [Consistency of a Recurrent Language Model With Respect to Incomplete Decoding](https://mlsanity.com/paper/2002.02492/) (2020)
- [Energy-Based Reranking: Improving Neural Machine Translation Using Energy-Based Models](https://mlsanity.com/paper/2009.13267/) (2020)
- [Deep Reinforcement Learning-based Image Captioning with Embedding Reward](https://mlsanity.com/paper/1704.03899/) (2017)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [SEARNN: Training RNNs with Global-Local Losses](https://mlsanity.com/paper/1706.04499/) (2017)
- [Leveraging Sentence Similarity in Natural Language Generation: Improving Beam Search using Range Voting](https://mlsanity.com/paper/1908.06288/) (2019)
- [A Fully Differentiable Beam Search Decoder](https://mlsanity.com/paper/1902.06022/) (2019)
- [Investigating the Decoders of Maximum Likelihood Sequence Models: A Look-ahead Approach](https://mlsanity.com/paper/2003.03716/) (2020)

## Built on by (most cited first, 30 of 55)

- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Offline RL for Natural Language Generation with Implicit Language Q Learning](https://mlsanity.com/paper/2206.11871/) (2022)
- [Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding](https://mlsanity.com/paper/2408.08252/) (2024)
- [High Quality Rather than High Model Probability: Minimum Bayes Risk Decoding with Neural Metrics](https://mlsanity.com/paper/2111.09388/) (2021)
- [Inference-Time Alignment in Diffusion Models with Reward-Guided Generation: Tutorial and Review](https://mlsanity.com/paper/2501.09685/) (2025)
- [Transformer-based Planning for Symbolic Regression](https://mlsanity.com/paper/2303.06833/) (2023)
- [Factually Consistent Summarization via Reinforcement Learning with Textual Entailment Feedback](https://mlsanity.com/paper/2306.00186/) (2023)
- [Grounded Decoding: Guiding Text Generation with Grounded Models for Embodied Agents](https://mlsanity.com/paper/2303.00855/) (2023)
- [Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation](https://mlsanity.com/paper/2108.04718/) (2021)
- [Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding](https://mlsanity.com/paper/2309.15028/) (2023)
- [The Curious Case of Hallucinatory (Un)answerability: Finding Truths in the Hidden States of Over-Confident Large Language Models](https://mlsanity.com/paper/2310.11877/) (2023)
- [Quality-Aware Decoding for Neural Machine Translation](https://mlsanity.com/paper/2205.00978/) (2022)
- [MegaAgent: A Large-Scale Autonomous LLM-based Multi-Agent System Without Predefined SOPs](https://mlsanity.com/paper/2408.09955/) (2024)
- [KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection](https://mlsanity.com/paper/2310.09044/) (2023)
- [Tuning computer vision models with task rewards](https://mlsanity.com/paper/2302.08242/) (2023)
- [Dynamic Search for Inference-Time Alignment in Diffusion Models](https://mlsanity.com/paper/2503.02039/) (2025)
- [PPL-MCTS: Constrained Textual Generation Through Discriminator-Guided MCTS Decoding](https://mlsanity.com/paper/2109.13582/) (2021)
- [Faithful Question Answering with Monte-Carlo Planning](https://mlsanity.com/paper/2305.02556/) (2023)
- [Can Compressed LLMs Truly Act? An Empirical Evaluation of Agentic Capabilities in LLM Compression](https://mlsanity.com/paper/2505.19433/) (2025)
- [To Beam Or Not To Beam: That is a Question of Cooperation for Language GANs](https://mlsanity.com/paper/2106.06363/) (2021)
- [Don't Rank, Combine! Combining Machine Translation Hypotheses Using Quality Estimation](https://mlsanity.com/paper/2401.06688/) (2024)
- [Teacher Forcing Recovers Reward Functions for Text Generation](https://mlsanity.com/paper/2210.08708/) (2022)
- [Optimized Multi-Token Joint Decoding with Auxiliary Model for LLM Inference](https://mlsanity.com/paper/2407.09722/) (2024)
- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [Uncertainty Determines the Adequacy of the Mode and the Tractability of Decoding in Sequence-to-Sequence Models](https://mlsanity.com/paper/2204.00471/) (2022)
- [Selective Perception: Optimizing State Descriptions with Reinforcement Learning for Language Model Actors](https://mlsanity.com/paper/2307.11922/) (2023)
- [Generative Cooperative Networks for Natural Language Generation](https://mlsanity.com/paper/2201.12320/) (2022)

## Abstract (arXiv)

Beam search is the go-to method for decoding auto-regressive machine translation models. While it yields consistent improvements in terms of BLEU, it is only concerned with finding outputs with high model likelihood, and is thus agnostic to whatever end metric or score practitioners care about. Our aim is to establish whether beam search can be replaced by a more powerful metric-driven search technique. To this end, we explore numerous decoding algorithms, including some which rely on a value function parameterised by a neural network, and report results on a variety of metrics. Notably, we introduce a Monte-Carlo Tree Search (MCTS) based method and showcase its competitiveness. We provide a blueprint for how to use MCTS fruitfully in language applications, which opens promising future directions. We find that which algorithm is best heavily depends on the characteristics of the goal metric; we believe that our extensive experiments and analysis will inform further research in this area.