summaries: 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}$.  Aside 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. 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. 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.   **Summary**  This 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.    
abstractText: 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.
authors.name: Wang Ling
authors.name: Wojciech Stokowiec
authors.name: Domenic Donato
authors.name: Laurent Sartran
authors.name: Lei Yu
references.authors: David Auger Adrien Couëtoux Olivier Teytaud
references.title: Continuous upper confidence trees with polynomial exploration - consistency
references.venue: Proceedings, Part I,
references.authors: Hendrik Baier Mark H.M. Winands
references.title: Beam monte-carlo tree search
references.venue: IEEE Conference on Computational Intelligence and Games (CIG),
references.authors: Ondřej Bojar Christian Buck Christian Federmann Barry Haddow Philipp Koehn Johannes Leveling Christof Monz Pavel Pecina Matt Post Herve Saint-Amand Radu Soricut Lucia Specia Aleš Tamchyna
references.title: Findings of the 2014 workshop on statistical machine translation
references.venue: In Proceedings of the Ninth Workshop on Statistical Machine Translation,
references.authors: Peter F. Brown Stephen A. Della Pietra Vincent J. Della Pietra Robert L. Mercer
references.title: The mathematics of statistical machine translation: Parameter estimation
references.venue: Computational Linguistics,
references.authors: Cameron Browne Edward Powley Daniel Whitehouse Simon Lucas Peter I. Cowling Philipp Rohlfshagen Stephen Tavener Diego Perez Spyridon Samothrakis Simon Colton
references.title: A survey of monte carlo tree search methods
references.venue: IEEE Transactions on Computational Intelligence and AI in Games,
references.authors: Ciprian Chelba Tomás Mikolov Mike Schuster Qi Ge Thorsten Brants Phillipp Koehn
references.title: One billion word benchmark for measuring progress in statistical language modeling
references.venue: CoRR, abs/1312.3005,
references.authors: Rémi Coulom
references.title: Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search
references.venue: 5th International Conference on Computer and Games,
references.authors: Zihang Dai Zhilin Yang Yiming Yang Jaime G. Carbonell Quoc V. Le Ruslan Salakhutdinov
references.title: Transformer-xl: Attentive language models beyond a fixed-length context
references.venue: URL http://arxiv.org/abs/1901.02860
references.authors: Peter Hart Nils Nilsson Bertram Raphael
references.title: A formal basis for the heuristic determination of minimum cost paths
references.venue: IEEE Transactions on Systems Science and Cybernetics,
references.authors: Ari Holtzman Jan Buys Maxwell Forbes Yejin Choi
references.title: The curious case of neural text degeneration
references.venue: CoRR, abs/1904.09751,
references.authors: Nal Kalchbrenner Phil Blunsom
references.title: Recurrent continuous translation models
references.venue: In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,
references.authors: Guillaume Klein Yoon Kim Yuntian Deng Jean Senellart Alexander M. Rush
references.title: Opennmt: Open-source toolkit for neural machine translation
references.venue: CoRR, abs/1701.02810,
references.authors: Levente Kocsis Csaba Szepesvári
references.title: Bandit based monte-carlo planning
references.venue: Proceedings of the Seventeenth European Conference on Machine Learning (ECML 2006),
references.authors: Philipp Koehn Rebecca Knowles
references.title: Six challenges for neural machine translation
references.venue: In Proceedings of the First Workshop on Neural Machine Translation,
references.authors: Philipp Koehn Franz J. Och Daniel Marcu
references.title: Statistical phrase-based translation
references.venue: In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics,
references.authors: Rémi Leblond Jean-Baptiste Alayrac Laurent Sifre Miruna Pislar Jean-Baptiste Lespiau Ioannis Antonoglou Karen Simonyan Oriol Vinyals
references.title: Machine translation decoding beyond beam
references.venue: search. CoRR,
references.authors: Jason Lee Elman Mansimov Kyunghyun Cho
references.title: Deterministic non-autoregressive neural sequence modeling by iterative refinement
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Chu-Cheng Lin Aaron Jaech Xin Li Matthew R. Gormley Jason Eisner
references.title: Autoregressive modeling is misspecified for some sequence distributions
references.venue: CoRR, abs/2010.11939,
references.authors: Qi Liu Lei Yu Laura Rimell Phil Blunsom
references.title: Pretraining the noisy channel model for task-oriented dialogue
references.venue: Trans. Assoc. Comput. Linguistics,
references.authors: Clara Meister Tim Vieira Ryan Cotterell
references.title: If beam search is the answer, what was the question
references.venue: CoRR, abs/2010.02650,
references.authors: Nathan Ng Kyra Yee Alexei Baevski Myle Ott Michael Auli Sergey Edunov
references.title: Facebook fair’s WMT19 news translation task submission
references.venue: ProceedingsWMT,
references.authors: Franz Josef Och
references.title: Minimum error rate training in statistical machine translation
references.venue: In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics,
references.authors: Kishore Papineni Salim Roukos Todd Ward Wei-Jing Zhu
references.title: Bleu: a method for automatic evaluation of machine translation
references.venue: In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics,
references.authors: Maja Popović
references.title: chrF: character n-gram F-score for automatic MT evaluation
references.venue: In Proceedings of the Tenth Workshop on Statistical Machine Translation,
references.authors: Matt Post
references.title: A call for clarity in reporting BLEU scores
references.venue: In Proceedings of the Third Conference on Machine Translation: Research Papers,
references.authors: Rico Sennrich Barry Haddow Alexandra Birch
references.title: 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
references.venue: Association for Computational Linguistics. doi: 10.18653/v1/P16-1162. URL https://www.aclweb. org/anthology/P16-1162
references.authors: Noam Shazeer
references.title: Fast transformer decoding: One write-head is all you need
references.venue: CoRR, abs/1911.02150,
references.authors: Shiqi Shen Yong Cheng Zhongjun He Wei He Hua Wu Maosong Sun Yang Liu
references.title: Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
references.authors: David Silver Aja Huang Christopher J. Maddison Arthur Guez Laurent Sifre George van den Driessche Julian Schrittwieser Ioannis Antonoglou Veda Panneershelvam Marc Lanctot Sander Dieleman Dominik Grewe John Nham Nal Kalchbrenner Ilya Sutskever Timothy Lillicrap Madeleine Leach Koray Kavukcuoglu Thore Graepel Demis Hassabis
references.title: Mastering the game of go with deep neural networks and tree
references.venue: search. Nature,
references.authors: Felix Stahlberg Bill Byrne
references.title: On NMT search errors and model errors: Cat got your tongue
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: Ilya Sutskever Oriol Vinyals Quoc V Le
references.title: Sequence to sequence learning with neural networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N. Gomez Lukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: CoRR, abs/1706.03762,
references.authors: Kyra Yee Yann N. Dauphin Michael Auli
references.title: Simple and effective noisy channel modeling for neural machine translation
references.venue: Proceedings of EMNLP,
references.authors: Lei Yu Phil Blunsom Chris Dyer Edward Grefenstette Tomás Kociský
references.title: The neural noisy channel
references.venue: In Proceedings of ICLR,
references.authors: Lei Yu Laurent Sartran Po-Sen Huang Wojciech Stokowiec Domenic Donato Srivatsan Srinivasan Alek Andreev Wang Ling Sona Mokra Agustin Dal Lago Yotam Doron Susannah Young Phil Blunsom Chris Dyer
references.title: The DeepMind Chinese–English document translation system at WMT2020
references.venue: In Proceedings of the Fifth Conference on Machine Translation,
sections.heading: 1 INTRODUCTION
sections.text: 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., 2017), and a variety of conditional independence assumptions are made in other model classes from statistical translation models (Brown et al., 1993; Koehn et al., 2003) to non-autoregressive neural models (Lee et al., 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 to address observed model failures.
  ∗Authors contributed equally. †Work carried out while Wang Ling was at DeepMind.
  Despite the algorithmic benefits that beam search provides, we argue that it is a 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 a variety of different autoregressive architectures (Koehn & Knowles, 2017; Lin et al., 2020). The existing heuristic solutions—e.g., nonlocal corrections to the search objective at decoding time, or global statistics about the population of per-word probabilities (Wu et al., 2016; Meister et al., 2020)—point to non-autoregressive components in the search objective as necessary parts of the solution.1 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 adaptive 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 is guided from the start by the true objective—whether 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 nonautoregressive 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 autoregressive 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., 2021), which factorize the translation probability according to Bayes’ rule and have been argued to be better calibrated, are (1) poorly optimized by standard reranking-based 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.
sections.heading: 2 BACKGROUND
sections.heading: 2.1 BEAM SEARCH
sections.text: Translation tasks operate on the space of possible translations Y = Σ∗ ◦ {EOS} where Σ is a finite vocabulary, and EOS is a symbol represents the end of a sequence. Elements in Y correspond to full sentences y = y1, . . . , yn with n− 1 tokens, where yn = EOS (end of sentence). Each translation y is conditioned on a source sentence x and is assigned a score s(x,y), which measures how well x translates to y. Decoding algorithms aim to find the best hypothesis y∗ ∈ Y under the search objective s(x,y). While autoregressive models may assign scores to prefixes of translations, we
  1In 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 a complete translation hypothesis to compute a score, and models that make a Bayes’ rule decomposition of the translation probability.
  only assume that s is well defined for full translations, y ∈ Y . In the particular case of machine translation under standard autoregressive models, the search objective is defined as the conditional log probability:
  sAR(x,y) = log p(y | x) = |y|∑ i=1 log p(yi | y1, . . . , yi−1,x).
  As autoregressive models have probability emissions at the token level, the search problem can be cast into a shortest path problem for weighted graphs, where each node p is identified by a sequence y(p). Nodes define an additional space Y∗ including Y as well as partial translations in Σ∗ that do not terminate with a EOS token. Each node contains |Σ|+ 1 edges, each appending a different word yi ∈ Σ ∪ {EOS} to y(p) generating a new node p ◦ yi. Edge weights are given by the emission log probability log p(yi | y(p),x) 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 0 that lead to a single shared terminal node. One solution to this problem is A∗ search (Hart et al., 1968), which is a best-first algorithm that iteratively searches nodes p with the highest value v̂(p) = c(p) + f(p), where c(p) is the sum of weights of all edges from ε to p, and f(p) is a heuristic function that attempts to 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 a best-first traversal, beam search proceeds iteratively along a frontier at 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 ε 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 v̂(p) = c(p), and, in the case of neural machine translation, setting f(p) = 0. 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-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 to 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; Holtzman et al., 2019). Thus, while b 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.
sections.heading: 2.2 MONTE CARLO TREE SEARCH
sections.text: In Monte Carlo tree search (Coulom, 2006, MCTS), the Monte Carlo method replaces the heuristically driven measure of value v̂(p) for a node p with an expected-outcome model based on random game playouts. For instance, given a node p representing a state of a game, one can assign a value to p by randomly playing from that state a certain number of times and computing the average score obtained 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 a chess game). Additionally, as each playout yields a possible terminal state, both current c(p) and future costs f(p) are naturally embedded within the obtained estimate. Unlike beam search and A∗ search, where the search direction is determined by value v̂(p), MCTS diversifies the search space by allocating budget to less explored areas in the search space (Kocsis & Szepesvári, 2006), and continually refines value estimates.
sections.heading: 3 ADAPTIVE TREE SEARCH FOR TEXT GENERATION
sections.text: 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 v̂ in the game of go (Silver et al.,
  2016) runs hundreds of thousands of playouts, which can be computed in less than a second. In neural text generation the scoring function frequently requires the computation of a neural network forward step, such as a log-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 v̂ (Leblond et al., 2021). 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.
sections.heading: 3.1 DETERMINISTIC PLAYOUT HEURISTIC
sections.text: We start by establishing our playout function v̂(p), which is used as an initializer for node values. While the Monte Carlo method is effective at accurately estimating the value of a given sequence by performing multiple random playouts, such practice is infeasible as each of the playouts needs to be 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 Y . Thus, rather than multiple random playouts, we estimate the cost of a given node using a single informed playout, which is guided by greedy decoding using an autoregressive model. Therefore, given a node p with prefix y(p), we compute v̂(p) by recursively selecting the highest probability token y according to an autoregressive model p(y | y(p)1 , . . . , y (p) i ,x), 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.
sections.heading: 3.2 ADAPTIVE TREE SEARCH WITH A MODIFIED UCT CRITERIA
sections.text: ATS operates on search trees instead of weighted graphs. A search tree covers the space of all possible full and partial translations Y∗, and each node encodes a particular sequence y(p). Nodes have |Σ|+1 children, each appending a new word y ∈ Σ ∪ {EOS} to the sequence y(p). We denote the child resulting from concatenating y to p as p ◦ y. The child of a node that selects the EOS symbol is a terminal node, which is associated with a element in Σ∗, and therefore, can be scored using the objective s(x,y). Each node stores the number of visits n(p) and its current value estimate v(p), which can be reassigned during search. Nodes that have not been inserted in the tree have n(p) = 0 and no estimate for v(p).
  Search starts with the root node ε with visit count n(ε) = 1 and value v(ε) = v̂(ε), which corresponds to the score obtained by translating x 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 ε 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):
  UCT(p, y) = v̄(p ◦ y) + C √ n(p)
  1 + n(p◦y) π(y | y(p)), (1)
  where C is a hyperparameter weighting two terms. The first term v̄(p ◦ y) encourages exploitation of nodes with known high value. The second term √ n(p)
  1+n(p◦y) π(y | y(p)) encourages the algorithm
  to explore nodes with low visit counts more thoroughly. Here, we specify the policy as the logprobability obtained from an autoregressive model π(y | y(p)) = p(y | y(p),x). The value of a node is determined by its current estimate v̄(p ◦ y) = v(p◦y) if n(p◦y) > 0. For nodes not yet inserted in the tree, which have no value estimates, we compute an estimated value as:
  y∗ = arg max ∀y∈Σ,n(p◦y)>0 v(p◦y)
  v̄(p◦y) = v(p ◦ y∗) π(y | y (p))
  π(y∗ | y(p)) , (2)
  where we estimate v̄(p◦y) by assuming that the ratio between policies π between p ◦ y and the highest value node p ◦ y∗ is the same as the ratio between their values v̄. The traversal terminates when a node with n(p) = 0 or a terminal node is reached. In the former case, the node p is inserted into the tree, setting its visit count n(p) = 1 and estimating its value v(p) = v̂(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(p) > 0), which is followed by the expansion step that inserts a new child prior to simulation. Expanding all children of a node is generally considered efficient in domains with a small Σ and low playout cost v̂(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 not fit the context y(p) and correspond to the content in the source sentence x, and can be excluded using the value estimate described in Equation 2.
  Next, we ascend from the selected node p ◦ y, updating visit counts and value estimates: n(p) ← n(p) + 1 v(p) ← max{v(p), v(p◦y)},
  where each parent p increases its visit count n(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 p. Starting from the score obtained using greedy decoding when v(p) is initialised, each new traversal that passes through p has a chance to refine this initial estimate with the newly found translation.
sections.heading: 3.3 BEAM ADAPTIVE TREE SEARCH
sections.text: A standard way to guarantee progression in MCTS is to run an instance of MCTS per word. Here, we would run an ATS instance ATS(ε, k) with k iterations starting from root ε. Then, we set ε← ε ◦ y∗1 , where y∗1 = arg maxy∈Σ v
  (ε◦y) is the child with the highest value estimate and repeat this process until y∗i = EOS.
  However, it has been found that in text generation tasks restricting search to a 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:
  UCTconstrained(p, y, dmin) = { UCT(p, y) d(p◦y) > dmin −∞ otherwise (3)
  where d(p◦y) is initialised as `(p ◦ y), a function that counts the number of edges required to reach the root node from (p ◦ y). Then, the following update rule is added to ensure that the d(p) stores that depth of the deepest node achievable from p:
  d(p) ← max{d(p), d(p◦y)}, where we update each node so that d(p) stores the value of the deepest node that is accessible from p. Thus, in Equation 3, condition d(p◦y) > dmin tests whether p ◦ y contains a node deeper than dmin. We define BATS(ε, k) as a Beam ATS instance that runs ATS starting from the root node ε with the selection criteria UCTconstrained with dmin = 0 and gradually increasing dmin by 1 every k iterations. Search stops when no node satisfies d(p◦y) > dmin or until a maximum depth dmax.
sections.heading: 4 OBJECTIVES
sections.text: 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, we propose modeling improvements in order to address these shortcomings.
sections.heading: 4.1 MAX RANK
sections.text: Decoding in autoregressive models generally optimises a normalised log probability (Wu et al., 2016), (log p(y | x)) ( 65+|y| ) α, which combines the sum of the token level log-probabilities (when α = 0)
  and a length-based adjustment, which approximates the mean of the log-probabilities as the length |y| grows (when α = 1). Similar to normalised log-probabilities, we consider a metric that characterizes translation by their minimum token level 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 at a given timestamp could still be the worst decision in the sequence. Instead, we optimise the normalised rank:
  r(yi | y1, . . . , yi−1,x) = ∑ y∈Σ δ(p(yi | y1, . . . , yi−1,x) > p(y | y1, . . . , yi−1,x))
  |Σ| where we count the number of actions in Σ with lower log-probability than yi. By using the rank r instead of the log-probability p, we can compare values within the same range at the cost of a loss in relative precision. Thus, we name our metric max rank (MR), which is computed as follows:
  MR(x,y) = |y|
  max i=1
  log r(yi | y1, . . . , yi−1,x).
  Finally, unlike the mean and sum of log-probabilities, the max of a sequence of log-probabilities is not autoregressive, so beam search is not applicable.
sections.heading: 4.2 NOISY CHANNEL MODEL
sections.text: The noisy channel model uses the Bayes rule decomposition in order to decompose the probability of a sentence p(y|x) into p(y|x) = p(x|y)p(y)p(x) where the channel model p(x|y) can be trained as translation model trained in the reverse direction and p(y) is a 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 Σ∗, it can bypass many of the degenerative cases in autoregressive models.
sections.heading: 4.3 MINIMUM RISK TRAINED AUTOREGRESSIVE MODELS
sections.text: In order to show that BATS can be an attractive alternative to beam search under autoregressive models, we need to improve the model so that the search bias is no longer as crucial to preserving the translation quality of the generated text. To this end, we fine-tune our models using minimum risk training (Shen et al., 2016, MRT). The MRT training objective is designed to minimize the empirical risk r(y, y′) by minimizing it in a subset of Σ∗ obtained by sampling n translations. This allows the model to mitigate degenerate cases caused by optimising the likelihood objective by fine-tuning the model on downstream metrics, such as BLEU (Papineni et al., 2002).
sections.heading: 5 EXPERIMENTS
sections.heading: 5.1 SETUP
sections.text: We conduct our experiments on the Chinese–English and Pashto–English tasks from WMT2020 (Barrault 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 multiquery 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 α = 0.8 and beam size 6. We also compare a variant fine-tuned using MRT according to the procedure described in Appendix A.3.
  For the noisy channel model, we 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 et 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 1 to 256. We combine different objective components under a log-linear model, where the weights of the components are tuned with MERT (Och, 2003). In order for model scores to be comparable, all weights are tuned on a pool of 256 translations using beam search.2
sections.heading: 5.2 RESULTS
sections.text: Table 1 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”).3 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 on some language pairs, such as Chinese-English and Pashto-English.
  In terms of modeling, we note that our 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 as the training data is small (500k parallel sentences) and the model relies on the large sized language model to provide accurate predictions.
sections.heading: 5.3 BEAM SEARCH AND BATS
sections.text: We now provide a more in-depth analysis on the Chinese-English language pair, where we believe results are more informative. Table 2 illustrates the results obtained using some models that were explored in our grid search (Column s(x,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 non-autoregressive models are marked with AR with NAR, respectively. It is also important to
  2Tuning λ using BATS to genererate candidates yields similar weights. 3The optimal models with the highest BLEU on the validation for Beam Search and BATS are the same.
  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 ProbabilityAR (α = 0)” and “Log ProbabilityAR (α = 0.8)”), we notice that the search budget in both cases is always low. Figure 1 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 (α = 0.8)”), the model scores obtained for BLEU search and BATS are very similar. However, we an observe a 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 a 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 (α = 0.8) + NCNAR) and Max Rank (Row “Log Probability (α = 0.8) + MRNAR”), 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 1 shows that the evolution of BLEU is considerably more stable with the noisy channel model (Column “Log Probability (α = 0.8) + NC”) and when Max Rank is applied (Column “Log Probability (α = 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 as 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 b 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. In 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 (α = 0.8)AR”). Figure 1 shows that once MRT is applied (Column “Log Probability MRT (α = 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 a growing need of better decoding mechanisms, such as BATS, in order to maximize translation quality. We perceive that in both autoregressive and non-autoregressive models, there is a 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 an 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 a delta of 39.19%.
sections.heading: 6 CONCLUSION
sections.text: This paper proposes an 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
  Beam Search BATS s(x,y) BLEU Beam BLEU Iter Delta
  Log Probability(α = 0)AR 24.7 2 24.2 1 -2.0% Log Probability(α = 0.8)AR 25.0 8 24.7 8 -1.2% Log Probability (α = 0.8) + NCNAR 25.2 16 25.4 32 0.6% Log Probability (α = 0.8) + MRNAR 26.8 32 27.4 128 2.5% Log Probability (α = 0.8) + MR + NCNAR 26.7 32 27.4 128 2.6% Log Probability MRT (α = 0.8)AR 28.2 64 28.7 256 1.8% Log Probability MRT (α = 0.8) +MRNAR 28.6 8 29.0 256 1.7% Oracle BLEUNAR 38.6 256 53.7 256 39.2%
  Decoding budget
  Figure 1: Comparison of BATS and beam search over different translation budgets under different translation objectives on the WMT2020 Chinese–English 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 as partial translation probability in autoregressive models. BATS is particularly useful when models are robust enough to allow for a higher search budget. As many existing objectives are found to be poorly correlated with translation quality, we propose a new metric named max rank and use existing methods, such as the noisy channel model and minimum error rate training, to 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 it 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.
sections.heading: ACKNOWLEDGMENTS
sections.text: We thank Rémi Leblond and Phil Blunsom for useful feedback throughout the different stages of this project.
sections.heading: A APPENDIX
sections.text: 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 a 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 no chance for the decoder to explore other branches, which accentuate issues where degenerate solutions are chosen (e.g. prematurely ending a translation). A comparison between ATS and BATS on our WMT2020 Chinese-English validation set using autoregressive models is shown in Table 3, where we observe that ATS has both a bias towards degenerate cases and yields worse model scores and BLEU.
  A.2 MIN PROB VS. MAX RANK
  The most straight-forward approach to select the worst decision in a translation is to select the lowest log-probability in the sentence. However, log-probabilities are not a good indicator of whether a decision is good or bad as some word translations are inherently low probability (words with many valid translations). Thus, we decided to use the maximum rank instead. Table 4 provides a comparison between the Min Prob (Row “Log Probability (α = 0.8) + MP”) and the Max Rank objective (Row “Log Probability (α = 0.8) + MR”). We observe that while Min Prob yields a relatively small improvement, it is significantly smaller than Max Rank’s improvement over the baseline (Row “Log Probability(α = 0.8)”). Additionally, it clearly does not address the degenerate solutions problem in autoregressive models.
  A.3 MINIMUM RISK TRAINING WITH CHRF AND BLEU
  While BLEU (Papineni et al., 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 (Popović, 2015) training is more stable, and a better optimal translation quality can be obtained.
  We use a sample size of 8 translations per sentence, and these are generated via temperature sampling with temperature 0.8. Finally, we set the risk r(y, y′) = − 12 BLEU(y, y ′) − 12 ChrF(y, y ′), where BLEU(·) is the sentence level sacreBLEU (Post, 2018) and ChrF(·) is the sentence level ChrF (Popović, 2015). We used the average of BLEU and ChrF because BLEU was designed as a corpus level metric, and ChrF provides a better estimate of translation quality with sparser matches against a reference for a single sentence.
  Table 5 compares the results obtained using only bleu(·), chrf(·) and their combinations, using Beam Search with beam 6, on the validation set in the WMT2020 Chinese-English dataset. Here, we can observe that a combination of both scores yields the optimal translation quality.
  A.4 COMPUTATIONAL COST OF BATS
  For Beam Search with beam size b and a max sentence length Y , beam search requires b× Y ×A operations, where A is a transformer+softmax block. Additionally, for reranking, the model score s(x,y) needs to be computed for each of the b translations and has a computational cost of B. Thus, the total cost is b × (Y × 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 ×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 + z)× (Y ×A+B), where z is the number of non-root nodes expanded more than once. As Y ×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 (α = 0.8) +MR” in Table 2). 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 at which model score gains are observed (Column “Gain”) even though the cost doubles at each row. For BATS, we observe that while the cost is extremely high initially (73.049 at 2 iterations), the cost increases at a linear rate with the number of iterations. More importantly, we notice considerable gains even with high numbers of iterations (11.82 at 128 iterations). Finally, at beam 256, we notice that the cost of Beam Search is comparable to the cost of running 16 BATS iterations, which achieves similar model scores.
  It is important to also refer that cost efficiency is not the goal of this work, but to expose the need for better decoders that are 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).
  A.5 EXAMPLE TRANSLATIONS AND SEARCH ERRORS
  We compare the translated sentences using an a MRT tuned autoregressive model for Chinese-English, where BATS and beam search yield similar BLEU but where BATS achieves significantly lower model scores. Table 7 provides 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 of the sentence. Figure 2 illustrates this issue, we observe that by using the expression “there are also many”, it delays the generation of the word “technological” for three timestamps, leading to the higher score of −0.78729 (left path) compared to the alternative 1.20077 (right path) in the same timestamp. While this score regularizes to −1.58682 once the word “technological” is generated, its likely that the alternative translation is pruned by beam search.
  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.
  sum of probabilities
  ∑
  j≤i log p(yj |y1,...,yj−1,x)
  ( 5+i6 ) α with α = 0.8. This example is obtained from the WMT2020 test set.
title: ENABLING ARBITRARY TRANSLATION OBJECTIVES WITH ADAPTIVE TREE SEARCH