Enabling Arbitrary Translation Objectives with Adaptive Tree Search
Authors: Wang Ling
Wojciech Stokowiec
Domenic Donato
Chris Dyer
Lei Yu
Laurent Sartran
Austin Matthews
Venue: ICLR 2022 Poster (2022)
Keywords: Machine Translation
Decoding
MCTS
Beam Search

Abstract: We introduce an adaptive tree search algorithm, which is a deterministic variant of Monte Carlo tree search, that can find high-scoring outputs under translation models that make no assumptions about the form or structure of the search objective. This algorithm enables the exploration of new kinds of models that are unencumbered by constraints imposed to make decoding tractable, such as autoregressivity or conditional independence assumptions. When applied to autoregressive models, our algorithm has different biases than beam search has, which enables a new analysis of the role of decoding bias in autoregressive models. Empirically, we show that our adaptive tree search algorithm finds outputs with substantially better model scores compared to beam search in autoregressive models, and compared to reranking techniques in models whose scores do not decompose additively with respect to the words in the output. We also characterise the correlation of several translation model objectives with respect to BLEU. We find that while some standard models are poorly calibrated and benefit from the beam search bias, other often more robust models (autoregressive models tuned to maximize expected automatic metric scores, the noisy channel model and a newly proposed objective) benefit from increasing amounts of search using our proposed decoder, whereas the beam search bias limits the improvements obtained from such objectives. Thus, we argue that as models improve, the improvements may be masked by over-reliance on beam search or reranking based methods.

Published as a conference paper at ICLR 2022
ENABLING ARBITRARY TRANSLATION OBJECTIVES WITH ADAPTIVE TREE SEARCH
Wang Ling*t Talka, Inc.
Wojciech Stokowiec', Domenic Donato, Laurent Sartran, Lei Yu & Chris Dyer
1 inggangetalka..i
DeepMind, Ltd.
{wstokowi ec, comenicd, 1sartran, lei adyer} @deepmind, com
Austin Matthews
A Amazon.com
t naus@amazon, com
ABSTRACT
We introduce adaptive tree search algorithm, which is deterministic variant of Monte Carlo tree search, that can find high-scoring outputs under translation models that make no assumptions about the form structure of the search objective. This algorithm enables the exploration of new kinds of models that are unencumbered by constraints imposed to make decoding tractable, such as autoregressivity conditional independence assumptions. When applied to autoregressive models, our algorithm has different biases than beam search has, which enables new analysis of the role of decoding bias in autoregressive models. Empirically, we show that our adaptive tree search algorithm finds outputs with substantially better model scores compared to beam search in autoregressive models, and compared to reranking techniques in models whose scores do not decompose additively with respect to the words in the output. We also characterise the correlation of several translation model objectives with respect to BLEU. We find that while some standard models are poorly calibrated and benefit from the beam search bias, other often more robust models (autoregressive models tuned to maximize expected automatic metric scores, the noisy channel model and newly proposed objective) benefit from increasing amounts of search using our proposed decoder, whereas the beam search bias limits the improvements obtained from such objectives. Thus, we argue that as models improve, the improvements may be masked by over-reliance on beam search or reranking based methods.
INTRODUCTION
Conditional text generation tasks, such as machine translation, consist of two parts: a model that assigns scores to candidate outputs, and a search component that interacts with the model in order to find an output that maximizes the score assigned by the model. This search problem is a hard combinatorial optimization problem, and as a result, constraints are frequently imposed on the structure of the model to make solving or approximating the search problem easier. In neural machine translation, an autoregressive factorization of the output probability distribution is widely used (Kalchbrenner & Blunsom 2013 Sutskever et al.] 2014 Vaswani et al. (017)), and variety of conditional independence assumptions are made in other model classes from statistical translation models (Brown et al. 1993; Koehn al. 2003) 2018). Although these assumptions enable fast and accurate approximations to the search problem with simple and efficient algorithms (e.g., beam search), which can be crucial for efficient production applications, they limit the form of the models and thereby restricting the kinds of architectures that can be used address observed model failures.
-on-auuoreeressive neural models (Lee al.)
Authors contributed equally.
Work carried out while Wang Ling was DeepMind.

---

Published as a conference paper at ICLR 2022
Despite the algorithmic benefits that beam search provides, we argue that it is poor foundation for long-term scientific progress toward an accurate and reliable translation model whose scores adequately predict translation quality. First, it can only be applied to autoregressive models, which have well-known length calibration problems due to a tendency to drop or "hallucinate" content, and this tendency has been remarkably resistant to remedy across variety of different autoregressive architectures (Kochn & Knowles [017]] Lin et al. (2220). The existing heuristic solutions- non- local corrections to the search objective at decoding time, or global statistics about the population of per-word probabilities (Wu et al.
et al. 2020) -oonn to non- non-autoregressiv components in the search objective as necessary parts of the solution! We therefore would like to directly work with model classes that contain these solutions, rather than being dependent on limited heuristics that are imposed after the fact. Second, beam search is strongly biased towards translations that yield high initial scores due to the heuristic used to score partial translations (Stahlberg & Byrne 2019) Meister et al. 2020). While this feature provides short term translation quality gains as it addresses many of the calibration issues in autoregressive models, it is undesirable in the longer term as it masks many modeling issues that need addressing. More importantly, as scientific progress drives better correlations between model scores and translation quality, search errors caused by this bias will inevitably have a negative impact on both model scores and translation quality.
To address these shortcomings, we introduce the beam adaptíve tree search (BATS) algorithm, which is based on Monte Carlo tree search (Coulom 2006 Browne et al.) 2012). Like MCTS, BATS estimates the value of internal nodes (i.e.. partial translations) in the search tree with estimates from an expected-outcome model based on playouts from an auxiliary model, and these estimates are refined as the search progresses. Because BATS guided from the start by the true objective-wwetherr autoregressive or not, and due to the refinement of initial score estimates, the BATS decoder exhibits fewer biases as the search budget increases than beam search or reranking algorithms.
Our experimental section aims to characterise the impact of decoding mechanisms on both non- autoregressive and autoregressive models. For autoregressive models, we show that the calibration issues in autoregressive models can be addressed by adding a non-autoregressive component that augments the autoregressive sequence score with the lowest scoring produced token in the autore- gressive decomposition of the sequence, which we name max rank. We further show that existing non-autoregressive approaches, such as the "noisy channel" model (Yu et al. 2017 Yee et al. 2019 Ng et al. 2019 Yu et al., 2020b a Liu et al. (021). which factorize the translation probability according to Bayes rule and have been argued to be better calibrated, are (1) poorly optimized by standard reranking-basee approaches, and (2) ultimately have similar calibration failures as neural autoregressive models have. Incorporating the max rank component to existing objectives benefits both beam search and BATS, but the latter yields both the best translation and model scores. Crucially, we show that our decoder can search substantially longer and achieve higher model scores before BLEU starts to deteriorate, which suggests a negative impact of the search bias in beam search. Finally, we show that once autoregressive models become robust enough to address the calibration issues, this bias has an equally negative impact on translation quality. By fine-tuning an autoregressive model to better correlate with BLEU using minimum risk training (Shen et al. 2016), we show that BATS can achieve higher translation quality and a better model score compared to beam search.
2 BACKGROUND
2.1 BEAM SEARCH
Translation tasks operate on the space of possible translations y Σ* (FOS) where Σ is finite vocabulary, and BOS is a symbol represents the end of a sequence. Elements in y correspond to full sentences y = ..,.... In with n 1 tokens, where yn EOS (end of sentence). Each translation is conditioned on a source sentence æ and is assigned score s(x. y), which measures how well x translates to y. Decoding algorithms aim to find the best hypothesis y E y under the search objective s(x y). While autoregressive models may assign scores to prefixes of translations, we
'In this paper, we will use the term non-autoregressive to refer to any model whose scores do not decompose additively with the words in the output sequence. These include models that make conditional independence assumptions and generate each word independent of the others (Lee et al.) 2018). but also energy based models that require complete translation hypothesis to compute score, and models that make Bayes' rule decomposition of the translation probability.
2

---

Published as a conference paper at ICLR 2022
only assume that is well defined for full translations, y E V. In the particular case of machine translation under standard autoregressive models, the search objective is defined as the conditional log probability:
lvl
SAR(Z, v) = log m) log V1.-.., 11-1,)))
As autoregressive models have probability emissions at the token level, the search problem can be cast into shortest path problem for weighted graphs, where each node p is identified by sequence y(P), Nodes define an additional space )" including J' as well as partial translations in Σ" that do not terminate with a EOS token. Each node contains |Σ] + edges, each appending different word y4 E 2 U { to y generating a new node o yr. Edge weights are given by the emission log probability log y æ)) according to the autoregressive model. Search starts from the root node with an empty sequence and nodes that generate the EOS token have a single edged with weight O that lead to a single shared terminal node. One solution to this problem is A search (Hart) ctt 1968), which is a best-first algorithm that iteratively searches nodes p with the highest value ((p) = c() + fp)) where c(p) is the sum of weights of all edges from e to p. and ('( is a heuristic function that attempts estimate the sum of the edges on the highest scoring path from p to the terminal node.
Although theoretically appealing, good A" heuristics are difficult to obtain, and search can be extremely expensive with poor heuristics. To remedy this, beam search introduces approximations. Rather than best-first traversal, beam search proceeds iteratively along frontier a certain depth. Exploration is limited to b nodes at each depth, where b is selected as a hyperparameter that trades search accuracy (in terms of model score) for speed. From depth 0 composed of just root node e until a maximum depth limit Y is reached, or another stopping criteria is reached (Klein et al. 2017]. beam search progressively scores all children of the nodes at the current depth and prunes all generated nodes except for the top scoring b nodes. Beam search scores each node with only the current cost {(p) = c(p), and, in the case of neural machine translation, setting (() = O. Discarding the future cost biases search towards nodes with high scores without regard to whether they lead to a good path to the terminal state. Thus, a large space of potentially good translations with low initial scores is never explored. Examples include re-orderings that place high- high-entropy words at the start of the sentence or shorter sentence constructions (e.g. "Help me" vs. "Lend me a hand").
Interestingly, autoregressive models tend overestimate the probability of short and ungrammatical translations that do not translate the entirety of the source sentence, which are pruned by this scoring heuristic (Stahlberg & Byrne, 2019) Hootzman et al.) 2011)). Thus, while may be set low to increase speed, it is often set low to improve translation quality. However, we believe that model changes evaluated with beam search's biases may be obscured. We seek to propose modeling improvements to mitigate degenerate solutions, such that search quality and model quality are aligned.
2.2 MONTE CARLO TREE SEARCH
In Monte Carlo tree search (Coulom 2006 MCTS), the Monte Carlo method replaces the heuristically driven measure of value ((p) for a node with an expected-outcome model based on random game playouts. For instance, given a node representing a state of a game, one can assign a value to p by randomly playing from that state certain number of times and computing the average from the playouts. Thus, no burden is placed on the form of the objective function, allowing the definition of arbitrary complex objectives (e.g. winner of chess game). Additionally, each playout yields a possible terminal state, both current c(p) and future costs f() are naturally embedded within the obtained estimate. Unlike beam search and A* search, where the search direction is determined by value ūp)). MCTS diversifies the search space by allocating budget to less explored areas in the search space (Kocsis& & Szepesvári 2006), and continually refines value estimates.
obtained
ADAPTIVE TREE SEARCH FOR TEXT GENERATION
While MCTS (Coulom 2006) can be directly applied to decode arbitrary translation objectives, the heuristics defined in MCTS are optimised for environments where the computational cost of the scoring function s(x. y) is low. For instance, the playout heuristic è in the game of go (Silver et al.
3

---

Published as a conference paper at ICLR 2022
2016) runs hundreds of thousands of playouts, which can be computed in less than second. In neural text generation the scoring function frequently requires the computation of neural network forward step, such as a log-pro probability computed using an autoregressive model, rendering these practices prohibitive. One option is to rely on a heuristic to generate samples to train a neural network that estimates é (Leblond et al. (021). However this has been shown to be challenging as model scores are difficult to estimate. Instead, we describe a variant of MCTS optimised on decoding text generation.
3.1 DETERMINISTIC PLAYOUT HEURISTIC
We start by establishing our playout function o(p), which is used as an initializer for node values. While the Monte Carlo method effective at accurately estimating the value of given sequence by performing multiple random playouts, such practice is infeasible as each of the playouts needs to scored using the scoring function s(x. y). which we expect will be prohibitively expensive. Furthermore, chances that grammatical translations are sampled using this process are extremely low due to the sparsity of high-quality translations in V. Thus, rather than multiple random playouts, we estimate the cost of given node using single informed playout, which is guided by greedy decoding using an autoregressive model. Therefore, given a node with prefix y(P), we compute i(p) by recursively selecting the highest probability token y according to an autoregressive model ply 81") ......J. y,") .)), and scoring the translation using the objective function s(x, y).
This also implies our approach does not employ the Monte Carlo estimates and the decoding method is fully deterministic. The progression of the value estimates relies only on the refinement of the initial value estimates performed as the tree expands introduced in MCTS. Therefore, we will refer to our algorithm as an adaptive tree search (ATS) algorithm.
3.2 ADAPTIVE TREE SEARCH WITH A MODIFIED UCT CRITERIA
ATS operates on search trees instead of weighted graphs. search tree covers the space of all possible full and partial translations y", and each node encodes particular sequence y(P), Nodes have |-]| + 1 children, each appending new word y E Σ {BOS} to the sequence y (P)), We denote the child resulting from concatenating to as p y. The child of node that selects the EOS symbol is a terminal node, which is associated with element in Σ", and therefore, can be scored using the objective s(x y). Each node stores the number of visits (P) and its current value estimate u(P), which can be reassigned during search. Nodes that have not been inserted in the tree have (p(P) and estimate for (P))
Search starts with the root node with visit count (=) = and value ((()) = ((e), which corresponds to the score obtained by translating with greedy decoding. Afterwards the tree expands in an iterative manner, where each iteration expands the search tree and updates its statistics.
Similar to the selection and expansion steps in ATS, we traverse the instantiated tree, starting from 8 on the basis of the current estimated values v. together with confidence about the quality of the estimates. We recursively traverse the tree and select the child p y with the highest score according to the continuous upper confidence tree criterion (Auger et al. 2013):
(p())
UCT(p, v) 6(p o v) + C
1 n(Poy] ( (Pl),
(1)
where C' is a hyperparameter weighting two terms. The first term u(p y) encourages exploitation Vn(i)
of nodes with known high value. The second term [4mtroyy (1
()()) encourages the algorithm to explore nodes with low visit counts more thoroughly. Here, we specify the policy as the log- probability obtained from an autoregressive model (( y(()) p(y (P()),
x). The value of a node
determined by its current estimate ö(p o y) = (((o)) n (Pog) > 0. For nodes not yet inserted in the tree, which have no value estimates, we compute estimated value as:
(Poo))
arg max V oo
g(poy) v(poy") ( (p)) T y(m))
(2)
4

---

Published as a conference paper at ICLR 2022
where estimate g(Poy) by assuming that the ratio between policies between po y and the highest value node p o y" is the same as the ratio between their values V.
The traversal terminates when node with (P 0 terminal node is reached. In the former case, the node p is inserted into the tree, setting its visit count (P) = 1 and estimating its value v(e) f(p) as done in the simulation step in MCTS. We note here an important difference to many other formulations of MCTS, where selection terminates at leaf nodes (node where all Σ have n(()) > 0), which is followed by the expansion step that inserts new child prior to simulation. Expanding all children of node is generally considered efficient domains with a small and low playout cost ö(p), and the standard MCTS algorithm does not attempt to optimise the subset that needs to be expanded. In the text domain, most words in the vocabulary are not applicable as they do fit the context (P)) and correspond to the content the source sentence æ, and can be excluded using the value estimate described in Equation 2
Next, we ascend from the selected node p o y, updating visit counts and value estimates:
(p) <- ((() +
(P) + max(u()) w((ow)),
where each parent p increases its visit count (p()) and updates its value estimate v(P) to the child's value if a new best translation is found. Thus, v(P) represents the best translation obtained in the subtree represented by Starting from the score obtained using greedy decoding when e(P) is initialised, each new traversal that passes through p has a chance refine this initial estimate with the newly found translation.
3.3 BEAM ADAPTIVE TREE SEARCH
standard way to guarantee progression in MCTS is run an instance of MCTS per word. Here, we would run an ATS instance (e, k) with & iterations starting from root e. Then, we set <- E o vi- where yr arg max (F is the child with the highest value estimate and repeat this process until y EOS.
However, it has been found that in text generation tasks restricting search to set of high value nodes rather than a single one allows such games to be solved at a faster rate (Baier & Winands 2012). Thus, we modify our selection step as follows:
UCT(P, v)
d(roy) dmin otherwise
UCT construined (p. y, dminn)
-00
where d(oo)) is initialised as É(p o y). function that counts the number of edges required to reach the root node from (p o y). Then, the following update rule is added to ensure that the d(r) stores that depth of the deepest node achievable from p::
d(r) + max (d(r), (d()))((ee)))
where we update each node so that d(x) stores the value of the deepest node that is accessible from Thus, in Equation 3 condition d(woy) > dmin tests whether p contains a node deeper than dmin-
We define BATS(E, k) as Beam ATS instance that runs ATS starting from the root node with the selection criteria UCT constrained with dmin = and gradually increasing dmin by 1 every l: iterations. Search stops when no node satisfies dipoo) > dmai or until maximum depth dmax-
OBJECTIVES
As decoding with a decoder on vanilla autoregressive models is unlikely to yield translations with quality superior to beam search, as the beam search bias is essential to overcoming the calibration issues in these models, propose modeling improvements in order to address these shortcomings.
4.1
MAX RANK
Decoding in autoregressive models generally optimises a normalised log probability (Wu et al. 2016). (log p(y) x)) (7. )", which combines the sum of the token level log- probabilities (when 0)
5

---

Published as a conference paper at ICLR 2022
and length- based adjustment, which approximates the mean of the pre-robbbblities the length yy] grows (when a = 1).
Similar to normalised log- probabilities, consider metric that characterizes translation by their minimum token level log- log-probability. The intuition here is that the quality of the translation is represented by the worst decision made in the sequence. In practice, many degenerate cases in autoregressive models are created by making a single bad decision, such as generating a EOS token prematurely or omitting translations, which can be understood in terms of uniform information density (Meister et al. 2020).
However, the issue with the minimum of the token level log-probability is that log-probability ranges tend to vary depending on the context and number of translation options that are available. Thus, they are not very reflective on the quality of the choice made as the best choice given timestamp could still be the worst decision in the sequence. Instead, we optimise the normalised rank:
r(ys V1...... 1, Eyes Ó(p(ya VI.... 1;-1, x) p(u Ui..... Vi- V1-1. x))
Σ
where we count the number of actions in E with lower log- probability than y/- By using the rank instead of the log-probability we can compare values within the same range at the cost of loss in relative precision. Thus, name our metric max rank (MR), which is computed as follows:
(R y) max log r(ya 91.-.. : 1, 2:).
Finally, unlike the mean and sum of pogg--rbbbbbiiies.. the max of sequence of log-probabilities is not autoregressive, so beam search is not applicable.
4.2 NOISY CHANNEL MODEL
The noisy channel model uses the Bayes rule decomposition in order to decompose the probability p(zly)p(() where the channel model p(æly) can be trained as
of a sentence p(y|æz into p(y|æ) =
p(a)
translation model trained in the reverse direction and p(y) is language model. Finally, the prior p(x) can be ignored in the context of a maximization problem. Since the reverse model is not
autoregressive in the space D", it can bypass many of the degenerative cases in autoregressive models.
4.3 MINIMUM RISK TRAINED AUTOREGRESSII MODELS
In order to show that BATS can be an attractive alternative to beam search under autoregressive models, we need to improve the model that the search bias is no longer crucial preserving the translation quality of the generated text. To this end, we fine-tune our models using minimum risk training (Shen al. 2016 MRT). The MRT training objective is designed to minimize the empirical risk r(y.y y') by minimizing it in a subset of Σ* obtained by sampling n translations. This allows the model mitigate degenerate cases caused by optimising the likelihood objective by fine-tuning the model on downstream metrics, such as BLEU (Papineni et al. 2002).
5 EXPERIMENTS
5.1
SETUP
We conduct our experiments on the Chinese-Englin and Pashto Pushto-English tasks from WMT2020 (Bar rault et al.) 2020), and German- English from WMT2014 (Bojar et al., 2014), following the same training, development and test splits. Our autoregressive model transformer baseline uses the multi- query attention model (Shazeer 2019). It uses the standard architecture with 6 encoder and decoder layers with 512 hidden units, 2048 sized tied embeddings for both source and target word projections and 8 attention heads. We tokenize the data with byte-pair encoding (Sennrich et al. 2016 with 32K merges and set a maximum sentence size of Y = 128. Translation quality evaluation is performed using sacreBLEU (Post 2018). We choose the checkpoint that yields the highest BLEU in the validation set using beam search with the normalisation constant a = 0.8 and beam size 6. We also compare variant fine-tuned using MRT according to the procedure described in Appendix A.3

---

Published as a conference paper at ICLR 2022
For the noisy channel model, train the channel model by simply swapping the translation direction of the autoregressive model with the same hyperparameters. For the language model prior, we employ the TransformerXL architecture (Dai et al. 2019) trained on 1 billion words (Chelba et al. 2013). On non-autoregressive objectives, we use beam search as a proxy to generate translations candidates which are rescored using the non-autoregressive metric (Yee al. 2019] Yu et al. 2020a). For BATS, we simply set hyperparameter C = 1. While optimising C' could lead to more efficient optimisation of the model score, our goal is to study how model scores are correlated with translation quality in
different objectives.
The translation budget (beam size for beam search and iterations for BATS) is swept by doubling its value starting from to 256. We combine different objective components under a log-linear model, where the weights the components are tuned with MERT (Och 2003). order for model scores to be comparable, all weights are tuned on pool of 256 translations using beam search 2
5.2 RESULTS
Table illustrates the translation quality results using BATS and beam search on the normalised autoregressive model baseline and the optimal model (Column "System") for each language pair (Column "Language Pair"). We perform a grid search over the following decisions: (1) Whether to use Max Rank (Column "MR"), (2) Whether to use the Noisy Channel Model (Column "NC"), (3) Whether to tune the autoregressive model using MRT (Column "MRT"), (4) Whether to use beam search or BATS (5) The translation budget of each decoder. The combination with the highest BLEU on the validation set is used to decode on the test set and the BLEU scores obtained using beam search and Bats are reported (Columns "Beam Search" and "BATS"), We observe that for all pairs decoding with BATS can yield gains over decoding with beam search when using the combination of objectives with the highest BLEU on the validation set. As expected, due to the search bias in beam search, it does comparatively better some language pairs, such Chinese-Englist and Pashto-English.
In terms of modeling, we note that proposed metric, Max Rank, and the MRT method combined yield the best results for Mandarin and German. The noisy channel model only yields improvements in Pashto-English, when used with Max Rank and MRT the training data small (500k parallel sentences) and the model relies on the large sized language model to provide accurate predictions.
Language Pair System
MR
NC
MRT
Beam Search
BATS
Baseline
No
No
No
24.7
24.2
Mhinese-English Optimal
Yes
No
Yes
28.6
29.0
Baseline
No
No
No
7.5
7.3
Pashto-English
Optimal
Yes
Yes
Yes
8.1
9.1
Baseline
No
No
No
30.0
30.0
Gennan-English
Optimal
Yes
No
Yes
30.3
31.1
Table 1: Comparison between the BLEU scores obtained using beam search and BATS. Pairs of describes the results obtained using the vanilla autoregressive model with normalisation and the best combination of models (Max Rank, Noisy Channel and Minimum Risk Training), tuned on the validation set. The translation budget is also tuned for each method for maximum BLEU
5.3 BEAM SEARCH AND BATS
We now provide more in-depth analysis the Chinese-Engliss language pair, where believe results are more informative. Table iillustrasss the results obtained using some models that were explored in our grid search (Column sa,, y)) For each model, we illustrate the best BLEU obtained on the test set (Column "BLEU"), the beam size (Column "Beam") or number of iterations (Column "Iter"), where the best BLEU was obtained on the validation set and the percentage improvement between results obtained using beam search and BATS (Column "Delta") Finally, autoregressive and atorersrreee models are marked with A R with N AR, respectively. It is also important to
Tuunng À using BATS to genererate candidates yields similar weights.
TThe optimal models with the highest BLEU the validation for Beam Search and BATS are the same.
7

---

Published as a conference paper at ICLR 2022
refer that the number of iterations in BATS and beam in beam search are not comparable point-wise, instead we analyse the overall behavior of the model score and BLEU curves.
When to use Beam Search? In the models where beam search outperforms BATS(Rows "Log Probability (a = 0)" and "Log Probability44 (a = 0.8)"), we notice that the search budget in both cases is always low, Figure Plots the evolution of the BLEU (Top) and model score (Bottom) of both decoders as translation budget is increased. For the normalised log-probability (Column "Log Probability (a 0.8)"), the model scores obtained for BLEU search and BATS are very similar. However, we an observe large gap between the BLEU scores obtained at the same model score. This shows that the beam search bias is filtering the set of candidates in beam search so that they are of higher quality, even though the model score is failing to discriminate them. Additionally, we observe the standard BLEU curve (Stahlberg & Byrne 2019). where after set of initial iterations BLEU deteriorates rapidly, which renders elaborate decoding mechanisms unneeded. Furthermore, BATS and other MCTS-based methods are not ideal for low search budget scenarios as they depend on high node visit counts to accumulate enough statistics to make informed decisions. We see in all objectives that model scores for BATS do not outperform Beam Search until a large budget is allocated. In conclusion, if the model cannot support high search budgets, beam search is the preferred alternative, especially if the modeling issues can be addressed with the search bias.
When to use BATS? With the addition of the noisy channel model (Row "Log Probability (a 0.8) + NC and Max Rank (Row "Log Probability (a = 0.8) + MR N A ") the search budget until BLEU deteriorates for both decoders is increased. Here, we observe that BATS is the decoding option that yields higher BLEU and that the delta is higher when BATS can employ more iterations.
Figure T shows that the evolution of BLEU is considerably more stable with the noisy channel model (Column 'Log Probability (a = 0.8) + NC") and when Max Rank is applied (Column "Log Probability (a = 0.8) + MR"). For these non-autoregressive models BATS yields significantly better model scores than reranking. More interestingly, comparing the behavior of Beam Search and BATS, similar model scores between the two methods do not yield similar BLEU scores. In the noisy channel model, we observe that at 16 iterations and beam size 16, both decoders yield similar model scores and BLEU scores. However, as the model score increases beyond that point, the degeneration in beam search the score increases is significant, while BATS observes almost no deterioration. This suggests that the beam search bias has a negative impact in translation quality at high values of 6 by filtering good translations from the search space. Using Max Rank, we observe that not only BATS can achieve considerably higher model scores as it is optimising the non-autoregressive model directly, it also yields considerably higher BLEU scores. beam search, BLEU stops improving at 32 iterations even though model score keeps increasing due to the search bias.
Finally, we observe that the search bias issue is also present when using beam search to decode from an autoregressive model fine-tuned with MRT ( ('Table 2 Row "Log Probability MRT (a = 0.8) D.8). Figure T shows that once MRT applied (Column "Log Probability MRT (a = 0.8)"), not only BATS can find significantly better model scores, but they are are associated with better BLEU scores. Additionally, beam search stagnates after 8 iterations.
In conclusion, as translation models become more robust, there is growing need of better decoding mechanisms, such as BATS, in order to maximize translation quality. We perceive that in both autoregressive and -ooreeetreeeesevvve models, there is limit to both model and BLEU scores that can be obtained using beam search, which is partially attributed to the fact that its search is strongly biased due to the lack of future costs.
We believe that future research will drive models to extents where translation quality nearly perfectly matches with model scores. In oracle setup, where the objective is the sentence level BLEU by peeking at the reference (Row "Oracle BLEU"), we hypothesise that the delta between beam search and BATS would grow vastly, and observe that delta of 39.19%.
CONCLUSION
This paper proposes adaptive tree search algorithm designed to optimise arbitrary metrics. It uses rollouts from an auxiliary autoregressive model to obtain estimates for the value estimates of internal nodes. This allows the decoder to optimise arbitrary objectives and avoid the search biases of
8

---

Published as a conference paper at ICLR 2022
Beam Search
BATS
s(.. y)
BLEU
Beam
BLEU
Iter
Delta
Log Probability(a 0)aH
24.7
2
24.2
-2.0%
Log Probability(a = 0.8)
25.0
24.7
-1.2%
Log Probability (a: 0.8) NCWAR
25.2
25.4
0.6%
Log Probability (a: 0.8) MR
26.8
32
27.4
128
2.5%
Log Probability (a: 0.8) MR NC
26.7
32
27.4
128
2.6%
Log Probability MRT (a 0.8)
28.2
64
28.7
256
1.8%
Log Probability MRT (a = 0.8) + +MRNAR
28.6
29.0
256
1.7%
Oracle BLEU
38.6
256
53.7
256
39.2%
Table 2: Comparison between BS and MCTS on the WMT2020 Chinese-English test set. Pairs of cells denote BLEU scores and the iteration budget achieving the best BLEU on the validation set.
Probulility
Probubility
Produbillly (o= Rank
Probobelity MRT
25.0
250
350
24.9
34.0
240
24h
00.00
23.0
230
210
23.0
23.0
22.0
26.4
21.0
13. 64 10 255
26.0
16
St.
66 12 356
21.0
1h
52 44 128-256
10
52
44
296
-165
-050
-0.64
-0.56
-500.0
-32
-50
BATS
Search
-002
BATS
Search
0..0
0.52
BATS
Search
180
118
BATS
Search
-1050
18 64
08 255
6. 128 206
52 44
206
22
64
298
Decoding budgee.
Figure 1: Comparison of BATS and beam search over different translation budgets under different translation objectives on the WMT2020 Chinese-Englise test set. Each column illustrates the BLEU (top) and the model score (bottom) obtained using the two decoders on a different objective.
manually defined heuristics, such partial translation probability in autoregressive models. BATS is particularly useful when models are robust enough to allow for higher search budget. As many existing objectives
found be poorly correlated with translation quality, we propose new metric named max rank and use existing methods, such as the noisy channel model and minimum error rate training, address the failure modes of vanilla autoregressive models. Results on three language pairs are favourable to BATS when using our proposed augmentations of the autoregressive model. Additionally, we find that the gap in translation quality between beam search and BATS increases as more robust models are employed. More importantly. we observe that the search bias prevents beam search from achieving high-quality translations as filters good translations that are unfavoured by the search heuristic. Thereby, the model score increases, but BLEU decreases. This shows that beam search limits the potential of many models by establishing translation quality ceilings unrelated to the robustness of the model, but to the topology of the search space they establish. This suggests that as scientific progress drives more robust models, exploring more robust decoding methods, such as BATS, is fundamental for advancing the field of text generation.
ACKNOWLEDGMENTS
We thank Rémi Leblond and Phil Blunsom for useful feedback throughout the different stages of this project.

---

Published as a conference paper at ICLR 2022
REFERENCES
David Auger, Adrien Couêtoux, and Olivier Teytaud. Continuous upper confidence trees with polynomial exploration consistency. In Hendrik Blockeel, Kristian Kersting, Siegfried Ni- jssen, and Filip Zelezný (eds.), Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I, volume 8188 of Lecture Notes in Computer Science, pp. 194-209 Springer, 2013. doi: 10.1007/978-3-642-40000 978-3-643 40988-2
13. URL https: //o::////ooo.o// org.
Hendrik Baier and Mark H. M. Winands. Beam monte-carlo tree search. In 2012 IEEE Conference on Computational Intelligence and Games (CIG), pp. 227-233, United States, September 2012.
IEEE. doi: 10.1 109/CIG.2012.633777 2012.6374160.
Loie Barrault, Ondiej Bojar, Fethi Bougares, Rajen Chatterjee, Marta R. Costa-jussà, Christian Feder- mann, Mark Fishel, Alexander Fraser, Yvette Graham, Paco Guzman, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Kochn, André Martins, Makoto Morishita, Christof Monz, Masaaki Nagata, Toshiaki Nakazawa, and Matteo Negri (eds.). Proceedings of the Fifth Conference on Machine Translation. Association for Computational Linguistics, Online, November 2020.
URL https: //www//wwwww//.. a c www.. org/ arggonthologyy//// 2020 wnt
Ondiej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Level- ing, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Ales Tamchyna. Findings of the 2014 workshop on statistical machine translation. In Proceed- ings of the Ninth Workshop on Statistical Machine Translation, pp. 12-58, Baltimore, Maryland, URL
USA, June 2014. Association for Computational Linguistics. doi:
http:::/aclannhooooyy..o
3302
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L.. Mercer. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):633311, 1993. URL httt::::/www..ccle org. htt.://www...rtatttooooo//////// anthology/J93
2003
Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4(1), Mar 2012.
Ciprian Chelba, Tomás Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, and Phillipp Koehn. One billion word benchmark for measuring progress in statistical language modeling. CoRR, abs/1312.3005, 2013. URL htt.:/tt.///axii.or///////////
Rémi Coulom.
Efficient Selectivity and Backup Operators Monte-Carlo Tree Search. In Paolo Ciancarini and H. Jaap van den Herik (eds.). 5th International Conference on Computer and Games, Turin, Italy, May 2006. URLhtttp:://bal inria. st/iniia-0011650
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. CoRR, abs/1901 1008600 2019. URL
org.org//aaooooo aabs///////// / 1901. C2860
Peter Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 402) 1968. doi: 10. 10.1109/ssc..198..30000
URL https:://ci. http:::://ooo.ooo100.11110. 1tt.:11..199tttse
300136
Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. The curious case of neural text degenera- tion. CoRR, abs/1904.09751, 2019,
09751
Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. Proceedings of
the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1700-1709, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL
https: / wwww://wwww/////////////////wwww a web. www.::/wwww/wwwaaaeoooo.e..o http:r/////nnoooooo//11111111
10

---

Published as a conference paper at ICLR 2022
Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M. Rush. Opennmt: Open-source toolkit for neural machine translation. CoRR, htss1770.028100 2017. :
//taxxi.orggaaaaaaaaaaaaaaaaaaaa wwtp://orgaabbaaaaa.a ab1/ 02810
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Proceedings of the Seventeenth European Con- ference on Machine Learning (ECML 2006), volume 4212 of Lecture Notes in Computer Sci- ence, pp. 282-293, Berlin/Heidelberg, Germany, 2006. Springer. ISBN 3-540-45375-X. URL http:// wwww sztaki www.taa....sssaaaaaaaaaae www.saaa//ppprss/ecmmmm/
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. Proceedings of the First Workshop on Neural Machine Translation, pp. 28-39, Vancouver, August 2017. Association for Computational Linguistics. doi: 10. 1111653/11/W17-32000 URL BtLLhtts::///
aclweb. wwtp:oorg//ttooo www.eb.orgg/atthooooooooo
W17 7- 3204
Philipp Koehn, Franz Och, and Daniel Marcu. Statistical phrase-basee translation. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pp. 127-133, 2003. URL hhttps://weet ac wweb org/ ogy NN03-111111
Rémi Leblond, Jean-Baptiste Alayrac, Laurent Sifre, Miruna Pislar, Jean-Baptiste Lespiau, Ioannis Antonoglou, Karen Simonyan, and Oriol Vinyals. Machine translation decoding beyond beam search. CoRR, abs/2104.05336, 2021. URL
aatp:///bb//200400/0/ 2204. 05336
Jason Lee, Elman Mansimov, and Kyunghyun Cho. Deterministic non-autoregressive neural sequence modeling by iterative refinement. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1173-1182, Brussels, Belgium, October-November 2018.
Association for Computational Linguistics. doi: 10.18653/v 1-
URL https://
aclanthology org -
Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner. Autoregressive modeling is misspecified for some sequence distributions. CoRR, abs/2010.11999 2020. URL https:://arxie hwwgg///b///00/
11939
Qi Liu, Lei Yu, Laura Rimell, and Phil Blunsom and. Pretraining the noisy channel model for task-oriented dialogue. Trans. Assoc. Comput. Linguistics, 2021.
Clara Meister, Tim Vieira, and Ryan Cotterell. If beam search is the answer, what was the question? 02650
CoRR, abs/2010.02650, 2020. /RR/attpss/arxxv.oor///aa
Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. Facebook fair's WMT19 news translation task submission. In Ondrej Bojar, Rajen Chatterjee, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno -imeno-Yepes, Philipp Koehn, André Martins, Christof Monz, Matteo Negri. Aurélie Névéol, Mariana L. Neves, Matt Post, Marco Turchi, and Karin Verspoor (eds.), Proceedings WMT, 2019.
Franz Josef Och. Minimum error rate training in statistical machine translation. In Proceedings of the 4sst Annual Meeting of the Association for Computational Linguistics, pp. 160-167, Sapporo, Japan, July 2003, Association for Computational Linguistics. doi: (.3111/1175509610755111 URL https: / www. acl org/
http://www......o/////taaaoolaaa http//annoooooyPP---31 1021
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic the Association for
evaluation of machine translation. In Proceedings of the 40th Annual Meeting the
Computational Linguistics, pp. 311-318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/1073083.0077 1073315.. URL https:: /www aclweb
wwwttnooogyyyplooooooo 1040
Maja Popović. chrF: character n-gram F-score for automatic MT evaluation. In Proceedings of the
Tenth Workshop on Statistical Machine Translation, pp. 392-395, Lisbon, Portugal. September 2015. Association for Computational Linguistics. doi: 10.18653/v1/WI1 3049. URL (thhts
7/aclantho ogy. ogy. 3049
11

---

Published as a conference paper at ICLR 2022
Matt Post. A call for clarity in reporting BLEU scores. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 186-191, Brussels, Belgium. October 2018. Association for Computational Linguistics. doi: 10. 10.18653/1/W11--31199 URL https://
ac mellanhholgg ogy. org/ollglll... B- 8-6319 6319
Rico Sennrich, Barry Haddow, and Alexandra Birch. 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), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguisties. doi: 10. 101186/611/111-1162. URL httpt:ts////.m www. ac web
artg/antholooy//ll-111
Noam Shazeer. Fast transformer decodigg One write-head is all you need. CoRR, abs/1911.021555 abs/ 1911 C2150
2019. bttp://tt////xxivv..t
Shiqi Shen, Yong Cheng. Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volune 1: Long Papers), pp. 1683-1692. Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 10.1886//1//I1-1111
URL https: ac acl.atoonnnntotooccccca org/P16 1159
David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittiesse,, Ioannis Antonoglou, Veda Pannecrshelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 503, 2016. URL http: 7 /twp/taaateeeeeeeeeeeeea 6961 html
www. nature com nww www.trre//oorrr///aa3
Felix Stahlberg and Bill Byrne. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNL)), pp. 1366,, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v1/D19 1331. URL httph: www. a aclweb. orq/ htttaoooo///D---13/133
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neu- ral networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Wein- berger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL htttpss://ppccceeiinggeoooo http://ceeaaaa....oooooooo//ra/a papeee
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.037622 2017. URL
http:/ //a http//xxvvvo. orgo waaorg//b/////// abs////6. 03762
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. Google's 's neural machine translation system: Bridging the gap between human and machine translation. CoRR. abs/1609, (0669098144.0 44, 2016. URL //tp::://axivv org/ abs/ 100.. 08144
Kyra Yee, Yann N. Dauphin, and Michael Auli. Simple and effective noisy channel modeling for neural machine translation. In Kentaro Inui, Jing Jiang, Vincent Ng. and Xiaojun Wan (eds.), Proceedings of EMNLP, 2019.
Lei Yu, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Tomás Kocisky. The neural noisy channel. In Proceedings of ICLR, 2017.
Lei Yu, Laurent Sartran, Po-Sen Huang. Wojciech Stokowiee, Domenic Donato, Srivatsan Srinivasan, Alek Andreev, Wang Ling, Sona Mokra. Agustin Dal Lago, Yotam Doron, Susannah Young, Phil Blunsom, and Chris Dyer. The DeepMind Chinese- Chinese-English document translation system at WMT2020. In Proceedings of the Fifth Conference on Machine Translation, 2020a.
12

---

Published as a conference paper at ICLR 2022
Lei Yu, Laurent Sartran, Wojeiech Stokowiec, Wang Ling. Lingpeng Kong, Phil Blunsom, and Chris Dyer. Better document-level machine translation with bayes' rule. Trans. Assoc. Comput. Linguistics, 8:346-360, 2020b.
A APPENDIX
A.1 BATS VS. ATS
The advantage of the beam variant of MCTS (Baier & Winands 2012) is that the search algorithm does not have to commit to single branch every k iterations. As often occurs during translations, multiple valid translation exist and correspond to different branches in the tree and only after furthering the search tree can the optimal translation be filtered out. In ATS, once the EOS is chosen, search ends immediately, with chance for the decoder explore other branches, which accentuate issues where degenerate solutions are chosen (c.g. prematurely ending a translation). A comparison between ATS and BATS on our WMT2020 Chinese-Engiin validation using autoregressive models is shown in Table 3 where we observe that ATS has both bias towards degenerate cases and yields worse model scores and BLEU.
BATS
ATS
Log Probability (a 0.8)
Iter
( y)
BLEU
s(x, y)
BLEU
1
-5.2
21.9
-5.23
21.9
2
-5.00
22.9
-4.2
21.3
4
-4.81
23.1
4.90
20.9
8
4474
23.1
-4.00
20.8
16
-4.69
22.9
4478
20.7
-50
32
-4.55
22.9
-.75
20.7
RAIS
64
-4.61
22.5
-4.73
20.4
8T8
128
-4.59
22.2
-.772
20.2
32
64
128
256
16
32
256
-4.57
21.7
-4.72
20.0
fterations
Table 3: Comparison between BATS and ATS on our WMT2020 Chinese-English validation set, with Log Probability (a 0.8) as the search objective.
A.2 MIN PROB VS. MAX RANK
The most nenight-forward approach to select the worst decision in translation is select the lowest log-prod probabiiiit in the sentence. However, log pog-prbbabilities are not a good indicator of whether decision is good bad some word translations valid translations). Thus, we decided to use the maximum rank instead. Trovidss a comparison between the Min Prob (Row "Log Probability (a 0.8) MP") and the Max Rank objective (Row "Log Probability (a 0.8) + MR"). We observe that while Min Prob yields a relatively small improvement, it significantly smaller than Max Rank's improvement over the baseline (Row "Log Probability(a = 0.8)"). Additionally, it clearly does not address the degenerate solutions problem in autoregressive models.
inherently low probability (words with many
Beam Search
BATS
s(x. y) Log Probability(a: 0.8)
BLEU
Beam
BLEU
Iter
Delta
25.0
8
24.6
-1.2%
Log Probability (a = 0.8) + MRNAR
24.8
24.7
16
-0.3%
Log Probability (a 0.8) MR NAR
NAR
26.8
27.4
128
2.5%
Table 4: Comparison between Min Prob and Max Rank in our WMT2020 Chinese-English test set. The number of iterations is tuned the validation set.
13

---

Published as a conference paper at ICLR 2022
A.3 MINIMUM RISK TRAINING WITH CHRF AND BLEU
While BLEU (Papineni
2002 is the downstream translation metric used in most MT evaluations, its sentence level predictions tend to be sparse and inaccurate. Thereby, training quickly overfits before optimal translation quality is reached. With sentence level ChrF (Popović 2015) training is more stable, and a better optimal translation quality can be obtained.
We use sample size of translations per sentence, and these are generated via temperature sam- pling with temperature 0.8. Finally, we set the risk r(y. y') = ( y') ChrFF(y, y'), where ( the sentence level sacreBLEU (Post 2018 and ChrF(-) the sentence level Chrl (Popović 2013). We used the average of BLEU and Chrl because BLEU was designed as corpus level metric, and ChrF provides a better estimate of translation quality with sparser matches against a reference for single sentence.
Table 5 compares the results obtained using only bleu(-), chr and their combinations, using Beam Search with beam 6, the validation set in the WMT2020 Shinese-Englisee dataset. Here, we can observe that a combination of both scores yields the optimal translation quality.
bleu(-)
chrf(.)
BLEU
23.1
23.8
0
24.4
1 2
24.7
2
Table 5: BLEU obtained on the WMT2020 Chinese-Englsib validation set using different metrics as risk r(y. y'). Columns "bleu(-)" and "chrf(-)", denote the weights applied and Column "BLEU" denote the BLEU obtained. The first row illustrates the BLEU score obtained prior to MRT.
A.4 COMPUTATIONAL COST OF BATS
For Beam Search with beam size b and max sentence length Y, beam search requires b Y x A operations, where A is transformer+soffumax block. Additionally, for reranking, the model score s(x, v) needs to be computed for each of the translations and has computational cost of B. Thus, the total cost x (Y x A + B). In BATS, computation is proportional to the number of expanded nodes, when the playout heuristic is applied. Each playout requires the computation of greedy decoding, followed by the scoring function s<x, y). Thus, each rollout requires Y x A + B computations. Finally, all nodes that follow the path used in greedy decoding will have the same value v, which means that the first node that is expanded, which corresponds to this path will have no cost, with the exception of the root node. Thus, the cost of BATS is (1 2) (Y A + B), where is the number of non-root nodes expanded more than once. As Y x A + B is a common denominator for both methods, we define it as the a computational unit.
Table 6 shows the results obtained for max rank objective (row "Log Probability (a = 0.8) +M Rt" in Table The "Cost" column represents the number of computational units, and we observe that BATS is considerably more expensive to run than Beam Search. However, observe the model scores (Column "Score"), we notice that Beam Search gradually decreases the rate which model score gains are observed (Column "Gain") even though the cost doubles at each row. For BATS, we observe that while the cost extremely high initially (73.049 at 2 iterations), the cost increases notice considerable gains even with high
linear
rate with the number of iterations. More importantly, numbers iterations (1 1.182 at 128 iterations). Finally, at beam 256, we notice that the cost of Beam Search is comparable the cost of running 16 BATS iterations, which achieves similar model scores.
is important to also refer that cost efficiency is not the goal of this work, but to expose the need for better decoders that devoid of the beam search bias. Many improvements to MCTS based methods can be made to improve efficiency, such as training value and policy networks iteratively (Silver et al. 2016).
14

---

Published as a conference paper at ICLR 2022
Beam Search
BATS
Beam/Iter
Cost
( y
Gain
Cost
8 a y
Gain
1
-0.84
-0.84
2
2
-0.81
0.0296
73.0
-0.81
0.0240
4
-0.79
0.0169
146.4
-0.77
0.0394
8
8
-0.79
0.0030
217.5
-0.77
0.0032
16
16
-0.78
0.0059
315.7
-0.75
0.0151
32
32
-0.78
0.0048
421.9
-0.74
0.0072
64
64
-0.77
0,0043
584.3
-0.74
0,0002
128
128
-0.77
0.0035
641.9
-0.73
0.0118
256
256
-0.76
0.0032
846.3
-0.73
0.0068
Table 6: Comparison between BS and MCTS in terms of computational cost using the normalised autoregressive model in the WMT2020 Chinese-English validation set. Cells denote the computational cost, model score obtained and the gain on score obtained relative the row above.
A.5 EXAMPLE TRANSLATIONS AND SEARCH ERRORS
We compare the translated sentences using an a MRT tuned autoregressive model for Chinese-Engee English, where BATS and beam search yield similar BLEU but where BATS achieves significantly lower model scores. 7
three example translations from the test set obtained using beam 64 for beam search (row "Beam Search") and 256 iterations for BATS (row "BATS"), which is the setup that obtained optimal results in the validation set. The first example shows that beam search tends to prolong sentences by using longer expressions ("many" vs. "there are also many") in order to get short term value gains, but lower overall score, also slightly shifting tone the sentence. Figure 2 illustrates this issue, we observe that by using the expression "there generation of the word "technological" for three timestamps, leading to the higher score -0. 0.78729 (left path) compared to the alternative 1 1.20077 (right path) in the same timestamp. While this score regularizes to -1 1.58682 once the word "technological" is generated, its likely that the alternative translation is pruned by beam search.
also many", it delays the
In the second example, we observe that beam search prefers to reorder the original sentence, so that higher scoring terms ("U.S. destroyer USS Decatur") in the sentence are inserted first. However, as one can observe from the final score, this decision is only favorable in the short term as the final score of the sentence is substantially lower than the translation found using BATS, which respects the order of the original sentence. In the last sentence, we observe that in the final portion of the translation, the decoder makes a set of individually high scoring decisions that lead to an ungrammatical translation as all grammatical options have been filtered from the beam.
15

---

Published as a conference paper at ICLR 2022
root
0
-0.05161
Similarly
-0.05160
-..00033
-0.04555
-1.01806
-0.58858
-0.84979
there
many
0.50860
-0.01926
-1.02065
-0.78729
are
technological
-1.20077
-0.42737
-0.10722
-1.00766
also
entreprises
-1.17496
-0.25355
-0.02138
-1.08980
many
that
-1.10187
-0.99295
-0.27380
-1.58682
technological
have
-1.18503
Figure 2: Illustration of the issue with the search bias in beam search where the decoder can delay the generation of low probability words, in this case the word "technological" in order to generate high initial scores. Edges scores correspond to the token level log probability log p(y: 9/...., Wi-1, 1,-1, x) and nodes scores correspond the value that is assigned to the state using the normalised partial
sum of probabilities Σ,s, log p(z) [y 911 with = 0.8. This example is obtained from the WMT2020 test set.
16

---

Published as a conference paper at ICLR 2022
s(x, y)
Source
3 E T
Reference
Similarly, many technology companies have encountered numerous infringements crisis in patent technology licensing and patent technology use.
Beam Search
Similarly, there are also many technological enterprises that have en- countered great infringing waves in the licensing of patented technology and the use of patented technology.
-2.097
BATS
Similarly, many technological enterprises have encountered great infring- ing waves in the licensing of patented technology and the use of patented technology.
-1.740
Source
# 94
UUSU Decatur TH Te (1 T0
(Gaven Reef) HT
(Johnson Reef)
Reference
According the comprehensive foreign reports of the Central News Agency, the U.S. official who requested anonymity revealed that the United States Navy destroyer, USS Decatur, cruised into the 12 nautical mile territorial limit of Gaven Reef and Johnson Reef of the Nansha Islands.
Beam Search
U.S. destroyer USS Decatur sailed into the Gaven Reef and Johnson Reef 12 nautical miles (12 nautical miles) of the Southern Sand Islands, according Central Intelligence Agency's Comprehensive Outreach
-2.722
News on 30.
BATS
According to Central News Agency's s comprehensive external telecom- munications report on 30 June, U.S. officials who requested anonymity, the USS Decatur sailed into the Gaven Reef and Johnson Reef of the Southern Sand Islands within 12 nautical miles.
-2.288
Source
8 The aim of Italian Eurosceptic government was that the budget deficit equivalent to 2.4% of gross domestic product (GDP) in the next three years, suggesting that there was no debt reduction despite deficit reduction requirements.
(GGD %
Reference
Beam search
The Italian Euroskeptic government's 's goal is to have a budget deficit equivalent to 2.4% of gross domestic product over the next three years, suggesting that only facing deficit reduction requirements has not yet been debt reduction.
-1.647
BATS
The Italian Euroskeptic government's goal is to have a budget deficit equivalent to 2.4% of gross domestic product over the next three years, indicating only that there is no debt reduction required to reduce the deficit.
-1.542
Table Examples translation obtained using beam search and BATS on the Chinese-Englics test set using MRT tuned autoregressive models.
17


Reviews:
[{"review_id": "Yowo_iJqlKJ", "reviewer": "Reviewer_26JG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies an important problem, the text generation/decoding algorithm for models. In my view, the paper has two main contributions: utilizing an autoregressive model as the value network to enable MCTS, and proposing a new metric that is not limited to autoregressive decoding. The proposed method achieves better results than beam search as shown in experiments.\n\nI have several concerns:\n- The writing of the paper can be largely improved. I find the paper very hard to follow, and some important technical details are missing. For example, about the autoregressive model used as the value network, what is its architecture/training details/datasets/latency when scoring? In equ (3), what is d() and how is it computed? In section 4.1, what are \"other actions\"? Many notations are not defined, I suggest the authors add a problem definition/notation table at the front of section 3. The proposed method would be easier to understand if an algorithm/(pseudo) code is provided.\n- In experiments, what is the exact model and decoding method utilized in the baseline AR/NAR model? Usually NAR models perform worse than AR models, but the conclusion is opposite regarding Table 2. Any explanations? And do you use knowledge distillation to train the NAR model? In NAR models, how the token probability is computed? Still follow the equ in sec 4.1 that uses previous tokens to predict the current one?\n- It seems that the proposed method is time-consuming as an AR model is utilized. Have you compared the decoding speed with baseline methods? \n\nSome typos:\n- a iterative manner -> an iterative manner\n- a set of nodes high value nodes -> a set of high value nodes\n- we an observe -> we can observe\n\nThis is not a complete list. Seems that the paper is written in a hurry. Please have a carefully check and improve the writing.\n\n=================\n\nI still have the following concerns after reading the rebuttal.\n\n- The incorrect usage of terms and inconsistent claims make the paper hard to follow. I'm still a bit confused regarding the term \"non-autoregressive\" in the paper. If I understand correctly, in the rebuttal, the authors claim that the \"AR/NAR\" in Table 2 refers to different objectives such as NC and MR, which means that the backbone models of AR/NAR are the same, and different objectives result in different models. While in the abstract, the authors claim \n\"Empirically, we show that our adaptive tree search algorithm finds outputs with substantially better model scores compared to beam search in autoregressive models, and compared to reranking techniques in non-autoregressive models.\" \nBut NC and MR are not \"reranking techniques in non-autoregressive models\". Usually used techniques include NPD in Gu et.al., 2018/re-ranking by AT model in Ghazvininejad et.al., 2019. Consider adding comparisons with these techniques?\n- The comparison with beam search is unfair. Usually, we set beam=5-6 in practice, which is 20-30 times faster than BATS according to Table 6, while the performance gain is around 1~2%. The price is heavy to achieve marginal gains. The authors claim that they address the issue that the translation quality drops when increasing the beam size in beam search, but in Table 6 BATS also suffers from this issue as the best performance is achieved when iter=2. I'm not sure I understood correctly but I suggest adding further discussions.\n- It is surprising that there still exist many typos after \"multiple passes over the paper\". As pointed above, there exist inconsistent claims over the paper (e.g., the non-autoregressive model or ranking method or objective, the BATS addresses an issue while Table 6 shows opposite results), which makes the paper hard to follow.\n\nTherefore, I'll keep my score and vote for rejection.", "summary_of_the_paper": "The paper proposes an adaptive tree search algorithm for text generation. It uses an autoregressive model as the value network to produce the playout for each node. While decoding, the paper proposes a metric called max rank to address the shortcomings of utilizing the sum of token level log-probability. Results are conducted on several machine translation datasets, and the proposed method outperforms beam search in most cases.", "summary_of_the_review": "The paper studies an important problem and proposes a new decoding algorithm based on adaptive tree search, which outperforms beam search in experiments. But the paper writing is poor, some technical details are missed, which hinders the reader from understanding the method. Some metrics are missed in experiments. Therefore I suggest a rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SGU3M0E0HiX", "reviewer": "Reviewer_XcaS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n**Strengths**\n\n1. The motivation is novel and clear. \n2. Empirical results verify the efficacy of the method. The findings of the limits of beam search are inspiring. The proposed decoding algorithm could potentially boost the advance of text generation.\n\n\n\n**Weaknesses**\n\n1. Despite promising accuracy BATS could achieve, it brings more computational overhead due to rollouts for each node for several iterations. As efficiency is also an important factor to evaluate a translation system, the authors should provide more analyses on this.\n2. This experiment part could be further improved in terms of presentation and more clear organization. \n\n\n\n**Questions**\n\n1. Page 6, first equation of r. \"where we count the number of other actions with lower log-probability than y_i\" conflicts with the equation of r where you count the actions that are more probable than y_i. If I am not wrong, you should change \"lower\" to \"larger\" in the referred text.\n\n2. The paper claims to generalize among autoregressive and non-autoregressive models. However, I did not find the results of non-autoregressive models or I might be wrong. What do you mean when mentioning a non-autoregressive model? I thought it was that from [Gu+2017] generating a whole sentence in parallel. ", "summary_of_the_paper": "**Summary**\n\nThis paper proposes an adaptive tree search algorithm BATS, an MCTS variant, for NMT that could optimize any desired objectives/metrics (e.g. BLEU). The algorithm values each internal node by scoring a greedy searched rollout (instead of that of authentic MCTS) with an autoregressive model, which avoids search biases caused by other heuristics (e.g., beam search would be biased towards shorter translations or incomplete partial generations). Plus, a new objective Max Rank is proposed with a better correlation with translation quality. Experiments show that BART works well in comparison with beam search, which is also shown to bound the progress of more robust modeling in NMT.  \n\n", "summary_of_the_review": "This paper inspects the biases of commonly-used decoding heuristics and provides a variant of MCTS algorithm for better decoding in NMT with empirical verification. Overall, I feel like the submission is a good one and would give a concrete contribution to the community. However, the authors should address some of the issues I stated above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7rpQ_YOSNXL", "reviewer": "Reviewer_9nVZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. This paper proposes a new beam search algorithm based on  Monte Carlo tree search and compares some methods about modeling improvements to address beam search bias.\n\n2. The baselines are strong and the proposed approach also yields BLEU improvements when the model score correlates well with BLEU. \n\nMinor weakness:\n1. The paper does not intensively analyze the running efficiency of the proposed BATS algorithm. Additionally, it would be better to discuss some ways to improve the its efficiency, which is helpful to make it practical in future. \n2. In the paper, max rank is claimed to be a contribution but it does not conduct an ablation study to highlight its individual contribution. For example, in Table 1, it would be better to add one row by setting MR=Yes whereas NC and MRT are No. \n3. It shows the BLEU comparison for standard beam search and BATS, but it does not show the comparison in terms of model score. For example, in the line 1 of Table 1, does BATS obtains better model score than Beam search even if its BLEU is worse?\n\nTypo:\n1. we an observe a large gap between =》 we can observe ... \n\n", "summary_of_the_paper": "This paper proposes an adaptive tree search algorithm for NMT models. One advantage of this algorithm is that it does not make any assumptions about search objectives, and this enables the proposed algorithm to be applied on top of more general search objectives. In addition, it studies the issue of beam search bias and revisits some tricks to alleviate it as well as a new tricks. Combined with these tricks, the proposed algorithm delivers clear BLEU improvements over a strong baseline. \n", "summary_of_the_review": "This paper proposes an adaptive tree search algorithm for NMT models, and the proposed algorithm yields BLEU improvements when the model score correlates well with BLEU. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-ismHS8gvK", "reviewer": "Reviewer_i2pz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The paper is well-structured and easy-to-follow even for someone who does not regularly follow latest research on MCTS.\n+ The introduced depth control strategy of BATS is interesting and makes it easier to control for search budget compared to vanilla ATS.\n\nWeaknesses:\n+ My main complaint for this paper is that it did not cite an immediate related work of this paper (https://arxiv.org/pdf/2004.12527.pdf), which also applies MCTS to NMT and mentioned some similar ideas such as informed playouts, Although I realize that these two papers have some differences, I think it's more appropriate to cite it and clearly state the differences.\n+ The gain brought by the proposed BATS method is overall very small (<=1 BLEU).\n+ The evaluations miss some important details, and I have some doubts whether evaluations were presented in a way such that it unfairly favors BATS. For example, Table 1 only presented \"the best combination of models... tuned on validation set\", which I assume is tuned to optimize performance for BATS. Hence, this cannot be generalized as \"BATS yields gains over beam search\" -- I would rather see comparison of results from other configurations as well.\n+ Since the author mentioned that the search budgets of BATS and beam search is not point-wise comparable, it'll be interesting to see a discussion on the computation time of BATS in the experiments, which is missing for now.\n\nMore detailed feedback:\n+ More citation suggestions -- there were several SMT papers that should be cited in the discussion about beam search. Och et al. 2001 (https://aclanthology.org/W01-1408.pdf) should be cited for using A* search for MT. Koehn et al. 2003 (https://aclanthology.org/N03-1017.pdf) should be cited when discussing future cost of decoding for MT. Also, on MCTS, Kumagai et al. 2016 (https://aclanthology.org/W16-5502.pdf) is another paper that deployed MCTS to NLG.\n+ Some missing details about evaluation: (1) I don't think the paper mentioned what non-autoregressive models were used for the experiments. (2) Using sacrebleu without including the signature is not helpful at all for future reproduction of results, and I would strongly urge the authors to include them in the paper. (3) Significance tests on translation quality differences will be helpful especially given the small diff in BLEU.\n+ Some presentation suggestions: (1) It will be helpful to clarify the meaning of \"true objective\" and \"s(x, y)\" earlier on, as I have been wondering what objective is used for the search until section 4. (2) It took me a while to understand what \"iteration\" means in section 3.3. I would try to connect this with the notion of \"traverse\" in section 3.2.\n+ Some minor stylistic comments: (1) Abstract: \"than beam search has\" -- remove \"has\"; (2) Page 2: I cannot parse the sentence starting with \"For autoregressive models, we show that...\"; (3) Page 3, first sentence of Section 3 \"applied decode\" -> \"applied to decode\"; (4) I cannot parse the sentence below equation 2; (5) Page 5, \"update its value estimate $v^{(p)}$ to the child's value...\" -- missing a \"when\" after this?", "summary_of_the_paper": "This paper presents a novel algorithm called beam adaptive tree search (BATS) to enable the incorporation of search objectives that cannot be easily factorized. Unlike the regular Monte Carlo tree search algorithms that relies on a large number of playouts to update the value function, BATS relies on \"informed playout\", which is guided by the greedy decoding of the autoregressive models. To further constrain the search space, the paper also proposed a constrained node expansion criterion that gradually increases the lower limit of the node depth $d_{min}$, and allows for expanding $k$ nodes for each depth limit $d_{min}$.\n\nAside from the search algorithm, the paper also explored a couple of model changes to counteract the calibration issues, including two modified search objectives and using MRT-trained autoregressive models. Experiments show that while beam search performs better for the weaker models, BATS does improve the translation quality of the hypotheses when stronger MT models are used. Analysis on different beam size also show that unlike beam search, BATS can operate at large search budget without performance degradation under stronger models.", "summary_of_the_review": "Nicely presented paper with some interesting proposals, but the novelty is not as significant as it seems due to some similar but missing related work. The small performance gain, together with doubts on evaluation soundness and/or real-world applicability, would probably also limit its impact.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an adaptive tree search algorithm for NMT models with non-decomposable metrics and shows its efficacy against strong baselines. This is an interesting contribution towards overcoming the performance caps introduced by the uncontrolled-for biases of beam search, and it speaks to a growing community interested in decoding beyond greedy surprisal minimisation.

The initial reviews brought to light a number of concerns that in my view are well addressed in the rebuttal and in the current version of the manuscript. One of the key issues was a confusion caused by the use of the term 'non-autoregressive' to refer to the intractability of the metric / objective function of certain models. This use clashed with the more standard use in MT, which refers to a tractable factorisation of a joint probability by means of strong conditional independence assumptions. 

The confusion is easy to address and in no way compromises the thoroughness of the empirical section. The authors are aware of the confusion and how to resolve it, and they have acknowledged the need to pick a less ambiguous term. 

I'd like to recommend this for acceptance, but I urge that the authors do not ignore the confusion caused by 'auto/non-auto regressive' and the missing literature that came up in the discussion with reviewer i2pz (I understand the discussion happened too late for the manuscript to be updated, but I trust this can be done for the final version).
Decision: Accept (Poster)