# A Simple Baseline for Beam Search Reranking

Lior Vassertail Omer Levy
The Blavatnik School of Computer Science
Tel Aviv University

###### Abstract

Reranking methods in machine translation aim to close the gap between common
evaluation metrics (e.g. BLEU) and maximum likelihood learning and decoding
algorithms. Prior works address this challenge by training models to rerank
beam search candidates according to their predicted BLEU scores, building upon
large models pretrained on massive monolingual corpora – a privilege that was
never made available to the baseline translation model. In this work, we
examine a simple approach for training rerankers to predict translation
candidates’ BLEU scores without introducing additional data or parameters. Our
approach can be used as a clean baseline, decoupled from external factors, for
future research in this area.

##  1 Introduction

Neural machine translation typically uses beam search decoding to generate
multiple candidate translations from an underlying conditional language model.
These candidates are then reranked using an alternative metric, usually their
token-averaged log-probability, to select the output. Previous works Fernandes
et al. (2022); Bhattacharyya et al. (2021); Lee et al. (2021) show that
training a reranking model to predict evaluation metrics scores such as BLEU
Papineni et al. (2002) can improve performance with respect to that metric.
However, these approaches provide the reranker with monolingual pretraining,
back-translated data, or more parameters – none of which are given to the
baseline model. This work proposes a simple method to train machine
translation rerankers without introducing new data or enlarging the model.

We take the simple approach of fine-tuning the baseline translation model to
predict the BLEU score of its own translations. We sample training-set
translations from the model’s distribution using greedy search, beam search,
top-$k$ sampling Fan et al. (2018), nucleus (top-$p$) sampling Holtzman et al.
(2020), and the ground truth to create training examples for the reranker. We
study the effect of training the reranker on increasing sample sizes, across
four datasets of varying languages and sizes: IWSLT’14 English to German,
Arabic, and Russian Cettolo et al. (2015); WMT’16 Romanian to English Bojar et
al. (2016).

Experiments show that rerankers trained to predict BLEU, in our setting,
perform only slightly better than the baseline token-averaged log-probability
reranker. Achieving this level of performance requires a reranking training
set with dozens of generated translations for every source sentence. When
interpolating with the baseline reranking method, only a few generated
translations are needed for the reranking training set to exceed the
baseline’s performance, but further enlarging the dataset yields only limited
gains. Further correlation analysis shows that even though the reranker’s top
choice results in minor improvements, it is significantly better than the
baseline at ranking the entire list.

To the best of our knowledge, our work is the first to explore BLEU-driven
beam search reranking in a controlled setting, without adding training data,
model parameters, or other factors beyond the objective of predicting BLEU
scores. A natural question following to our findings is whether the
information available from BLEU scores may be sufficient on its own to train
rerankers that are substantially better than the standard token-averaged log-
probability heuristic. To test this hypothesis and identify the main factors
leading to reranking improvements, we recommend using our BLEU-only approach
as a baseline in future studies.

##  2 Background: Reranking

The current practice in machine translation is to use beam search to generate
$k$ high-probability candidates from a conditional language model. During
search, each candidate prefix is scored according to its cumulative log-
probability, i.e. the sum of log-probabilities that the model assigned to each
decoded token: $\sum_{i}^{|y|}\log P_{t}(y_{i}|x,y_{<i})$, where $P_{t}$
denotes the translation model.

A priori, higher scores should correlate with better candidates. In practice,
this metric is biased towards shorter sequences, since each additional token
adds a negative number to the score. The standard approach therefore reranks
the final $k$ candidates produced by beam search according to their token-
averaged log probability: $\frac{1}{|y|}\sum_{i}^{|y|}\log
P_{t}(y_{i}|x,y_{<i})$. While the token-averaged reranking heuristic typically
selects better translations, it is still misaligned with the final evaluation
metrics used in machine translation (e.g. BLEU) Papineni et al. (2002). In
this work, we investigate whether one can train a model to predict the target
evaluation metric and use it to rerank candidate translations, without adding
external data or extra parameters to the reranker, in addition to the basic
translation model.

##  3 Method

We describe a simple method, BLEUR (BLEU Reranking), for training a reranker
without introducing new training data or increasing the model’s size. Given a
trained translation model, the main idea is to sample its translations of its
own training set, compute each translation’s evaluation score (e.g. BLEU), and
then fine-tune a copy of the translation model to predict the evaluation score
given the source and model-generated translation. At inference time, the
reranker scores each candidate translation produced by the original
translation model, and selects the best option. We also discuss a hybrid model
that interpolates between the trained reranker’s predicted score and the
original translation model’s average log-probability.

### Objective

We assume that the reranking model $P_{r}$ predicts a probability score
$P_{r}(y|x)$ given the source $x$ and the candidate translation $y$. For
example, when predicting a translation’s BLEU score, a prediction of 0.473
would be equivalent to predicting 47.3 BLEU. While other rerankers optimize
for relative scores Lee et al. (2021), our experiments focus on predicting the
absolute score.

To optimize the reranker, we use KL divergence as follows, where $p$ denotes
the ground truth probability score:

$\displaystyle\ell=$ $\displaystyle-\left[p\log
P_{r}(y|x)+(1-p)\log(1-P_{r}(y|x))\right]$ $\displaystyle+\left[p\log
p+(1-p)\log(1-p)\right]$

The first row of the objective is a soft generalization of the cross-entropy
loss over two classes, and the second row (whose derivative is zero) subtracts
the optimal cross-entropy loss given the ground truth $p$ from the objective
function.

### Architecture

To control the effects of model size, we use a copy of the original
translation model to train the reranker. In this work, we use encoder-decoder
transformers Vaswani et al. (2017). We implement the reranker’s probability
score by taking $\vec{y}_{eos}$, the transformer’s decoder-side
$d$-dimensional representation of the last token in the sequence (EOS),
passing it through a $d\times 2$ linear layer, and then applying softmax
between the two logits. The first probability is considered the predicted
probability $P_{r}(y|x)$ and the second is its complement.

### Training Data

To train the reranker, we expand the original training set by producing
additional model-generated translations. Specifically, we collect a set of
translations $Y$ for each source sentence $x$ using the following decoding
algorithms: (1) the ground truth, (2) greedy decoding, (3) beam search
(retaining only the top beam), (4) a sample of $n$ translations using top-$k$
sampling Fan et al. (2018), and (5) a sample of $n$ translations using top-$p$
(nucleus) sampling Holtzman et al. (2020). This may amount to a maximum of
$2n+3$ translations per source, but there are also some overlaps in practice.
Each translation $y\in Y$ is then scored against the reference using the
evaluation metric (e.g. BLEU), producing the target score $p$.

### Pretraining

In our experiments, we initialize the reranking model using the original
translation model’s parameters. In other words, we pretrain the reranker on
the translation task. The only parameters that require initialization are in
the $d\times 2$ linear prediction head.

### Hybrid Model

We also experiment with a hybrid model that combines the translation model’s
probabilities with the reranking model’s predictions. Specifically, we
interpolate the translator’s average log-probability with the reranker’s log-
probability, denoting $\alpha$ as the interpolation weight:

$\displaystyle\frac{1-\alpha}{|y|}\sum_{i}\log
P_{t}(y_{i}|x,y_{<i})+\alpha\log P_{r}(y|x)$

##  4 Experiment Setup

### Datasets

We use the IWSLT2014 datasets Cettolo et al. (2015) of English TED talks
translated into German, Arabic, and Russian, as well as the WMT2016 Romanian
to English dataset Bojar et al. (2016). All datasets are tokenized into
subwords with BPE Sennrich et al. (2016).

### Model

We use fairseq’s Ott et al. (2019) implementation of encoder-decoder
transformers Vaswani et al. (2017) for translation and reranking models. We
use $6$ encoder and decoder layers, $4$ attention heads, a hidden dimension of
$512$, and a feed-forward dimension of $1024$. Vocabularies and embeddings are
shared across source and target.

### Hyperparameters

We optimize with Adam Kingma and Ba (2015), using a learning rate of $5e-4$
for translation models and $1e-4$ for rerankers, warmup of $1000$ steps,
weight decay of $1e-4$, dropout of $0.3$, and for the translation models we
use label smoothing of $0.1$. We train each model until convergence: a maximum
of 40k steps for translation models, and 60k steps for rerankers. We set the
batch size according to a maximum of 75k tokens for translation models, and
100k tokens for each reranker.

### Model Selection

To select the best checkpoint, we evaluate all models with BLEU Papineni et
al. (2002) on the development set. Reranker evaluation simulates the inference
environment by providing the reranker with the top $k=5$ beam search
candidates, and then computing BLEU for the top-scoring solution. Translation
models are evaluated every epoch, and rerankers are checked every $200$ steps.
For the hybrid reranker model, we also tune the reranker’s interpolation
weight during the validation process using the values $0.1,0.2,\ldots,0.9$.

### Reranking Data

For every translation dataset we generate new reranker scoring datasets as
described in Section 3. We always use $k=10$ for top-$k$ sampling and $p=0.99$
for nucleus (top-$p$) sampling. A temperature of $\tau=3$ is used in top-$k$
sampling to increase output diversity. We experiment with 5 different dataset
sizes by controlling $n$, the number of translations from the stochastic
generation algorithms; specifically, we use $n=1,3,10,32,100$ to approximate
the powers of $\sqrt{10}$.

### Inference

The translation candidates in all of our experiments are generated by beam
search with a beam size of $b=5$.

##  5 Results

(a) IWSLT’14 EN-DE

(b) IWSLT’14 EN-RU

(c) IWSLT’14 EN-AR

(d) WMT’16 RO-EN

Figure 1: Test results (BLEU) for every translation dataset, using either the
baseline reranker (token-averaged log-probability), BLEUR, or the hybrid
reranker. The horizontal axis is the number of randomly sampled translations
per source sentence (using both top-k and nucleus sampling), reflecting the
size of the trained reranker’s dataset.

Figure 1 shows the performance of the baseline model and reranker, compared to
the proposed BLEUR reranking model and their interpolation, the hybrid model.
When compared to the baseline, performance is largely comparable, with some
small improvements of up to 0.58 BLEU. Individually, BLEUR’s performance
increases within a typical range of $1$ BLEU as the reranking training set
grows, reaching saturation at around $64$ ($n=32$) random samples per source.
Furthermore, we observe that the hybrid model consistently reaches better
performance compared to BLEUR, and was able to outperform the baseline model
with a smaller training set. Overall, these improvements are minor when
compared to the full reranking potential as seen in Table 1.

Since the main performance metric only reflects the reranker’s ability to
assign the top score to a good candidate, we further analyze the correlations
between the reranker’s scores and the actual BLEU. Specifically, we compute
Pearson correlation for each example’s beam search candidates, and average it
across the test set. Figure 2 shows that, with sufficient training examples,
the reranker’s scores correlate better with the target BLEU scores than the
baseline, demonstrating the potential of our simple approach as a baseline in
future studies.

It would seems that the performance demonstrated in our setting is somewhat
underwhelming when compared to recent literature on BLEU-based reranking Lee
et al. (2021); Bhattacharyya et al. (2021). However, those experiments are not
comparable to ours as they train rerankers with additional data and parameters
that were not available to the original translation models.

| IWSLT’14 | WMT’16
---|---|---
| EN-DE | EN-AR | EN-RU | RO-EN
Baseline | $28.23$ | $14.56$ | $17.92$ | $33.48$
BLEUR | $28.51$ | $14.71$ | $17.91$ | $33.96$
Hybrid | $28.69$ | $14.75$ | $18.09$ | $34.06$
Oracle | $32.93$ | $17.71$ | $21.25$ | $37.50$
Table 1: Reranking test results (BLEU) when given the maximal amount of
training data ($n=200$), compared to the baseline reranker and the oracle
reranker. Figure 2: Average Pearson correlation between reranker scores and
real BLEU scores of beam search candidates in WMT’16 RO-EN, as a function of
the number of randomly sampled translation per source sentence.

##  6 Related Work

Recent work on reranking in machine translation includes both absolute scorers
and relative rerankers. Fernandes et al. (2022) propose ensembling a variety
of pretrained quality estimation metrics (including the translation model’s
log-probability) to predict an absolute score for each candidate. This method
effectively introduces more data and parameters into the system by running
inference on external pretrained language models. In addition, our work
assumes only a simple setting with 5 beam search candidates, whereas Fernandes
et al. (2022) experiment with up to 200 candidates, as well as slower decoding
methods such as MBR Eikema and Aziz (2020); Zhang et al. (2022) also explore
reranking in an MBR decoding setting.

Both energy-based reranking Bhattacharyya et al. (2021) and discriminative
reranking Lee et al. (2021) use a comparative softmax to induce relative
scores among the candidates. Both works use pretrained models that are larger
than the original translation model to train the reranker, thus introducing
more parameters and monolingual data into the system. Lee et al. (2021) also
use back-translated data to train the reranker; when this data is ablated,
gains from reranking are more modest. In contrast, our experiments control for
additional pretraining, data, and parameters, and examine the effect of the
reranking mechanism alone.

##  7 Limitations

Our work provides a simple baselines for research on machine translation
reranking. Although we raise the hypothesis that previous studies were able to
reach significant gains by injecting external factors into the rerankers, we
do not attempt to prove this rigorously; that would require running additional
experiments on relative reranking models in our controlled setting. Moreover,
our work is limited to relatively small datasets, and investigating our
approach using another evaluation metric (e.g. COMET), was also left for
future work.

## References

  * Bhattacharyya et al. (2021) Sumanta Bhattacharyya, Amirmohammad Rooshenas, Subhajit Naskar, Simeng Sun, Mohit Iyyer, and Andrew McCallum. 2021.  Energy-based reranking: Improving neural machine translation using energy-based models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4528–4537, Online. Association for Computational Linguistics.
  * Bojar et al. (2016) Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana Neves, Martin Popel, Matt Post, Raphael Rubino, Carolina Scarton, Lucia Specia, Marco Turchi, Karin Verspoor, and Marcos Zampieri. 2016.  Findings of the 2016 conference on machine translation.  In _Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers_ , pages 131–198, Berlin, Germany. Association for Computational Linguistics.
  * Cettolo et al. (2015) M. Cettolo, J. Niehues, S. Stüker, L. Bentivogli, and Marcello Federico. 2015\.  Report on the 11th iwslt evaluation campaign, iwslt 2014.
  * Eikema and Aziz (2020) Bryan Eikema and Wilker Aziz. 2020.  Is MAP decoding all you need? the inadequacy of the mode in neural machine translation.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 4506–4520, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Fan et al. (2018) Angela Fan, Mike Lewis, and Yann Dauphin. 2018.  Hierarchical neural story generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 889–898, Melbourne, Australia. Association for Computational Linguistics.
  * Fernandes et al. (2022) Patrick Fernandes, António Farinhas, Ricardo Rei, José De Souza, Perez Ogayo, Graham Neubig, and Andre Martins. 2022.  Quality-aware decoding for neural machine translation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1396–1412, Seattle, United States. Association for Computational Linguistics.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  _ArXiv_ , abs/1904.09751.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  _CoRR_ , abs/1412.6980.
  * Lee et al. (2021) Ann Lee, Michael Auli, and Marc’Aurelio Ranzato. 2021.  Discriminative reranking for neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 7250–7264, Online. Association for Computational Linguistics.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _ArXiv_ , abs/1706.03762.
  * Zhang et al. (2022) Yidan Zhang, Yu Wan, Dayiheng Liu, Baosong Yang, and Zhenan He. 2022.  Rmbr: A regularized minimum bayes risk reranking framework for machine translation.  _arXiv_ , abs/2203.00201.