Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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. 

main_review: Strength:
1. 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.

2. The baselines are strong and the proposed approach also yields BLEU improvements when the model score correlates well with BLEU. 

Minor weakness:
1. 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. 
2. 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. 
3. 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?

Typo:
1. we an observe a large gap between =》 we can observe ... 


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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

I have several concerns:
- 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.
- 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?
- It seems that the proposed method is time-consuming as an AR model is utilized. Have you compared the decoding speed with baseline methods? 

Some typos:
- a iterative manner -> an iterative manner
- a set of nodes high value nodes -> a set of high value nodes
- we an observe -> we can observe

This is not a complete list. Seems that the paper is written in a hurry. Please have a carefully check and improve the writing.

=================

I still have the following concerns after reading the rebuttal.

- 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 
"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." 
But 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?
- 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.
- 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.

Therefore, I'll keep my score and vote for rejection.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: **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.  


main_review: 

**Strengths**

1. The motivation is novel and clear. 
2. 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.



**Weaknesses**

1. 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.
2. This experiment part could be further improved in terms of presentation and more clear organization. 



**Questions**

1. 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.

2. 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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}$.

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.
main_review: Strengths:
+ The paper is well-structured and easy-to-follow even for someone who does not regularly follow latest research on MCTS.
+ The introduced depth control strategy of BATS is interesting and makes it easier to control for search budget compared to vanilla ATS.

Weaknesses:
+ 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.
+ The gain brought by the proposed BATS method is overall very small (<=1 BLEU).
+ 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.
+ 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.

More detailed feedback:
+ 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.
+ 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.
+ 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.
+ 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_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.
review_title: null

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)