  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.
