State of the art sequence-to-sequence models for large scale tasks perform a fixed number of computations for each input sequence regardless of whether it is easy or hard to process. In this paper, we train Transformer models which can make output predictions at different stages of the network and we investigate different ways to predict how much computation is required for a particular sequence. Unlike dynamic computation in Universal Transformers, which applies the same set of layers iteratively, we apply different layers at every step to adjust both the amount of computation as well as the model capacity. Experiments on machine translation benchmarks show that this approach can match the accuracy of a baseline Transformer while using only half the number of decoder layers.
[Post-reponse EDIT]: After reading the authors' response, and taking into account the other reviewers' opinions, I am willing to suggest acceptance of this paper on the condition that ***the authors will add the experimental results to address issue #7 and #8 of my original review (as they promised in their rebuttal)***. Before that, I'm keeping the current score, while noting that a more accurate rating should be "5 - Marginally below the acceptance threshold" (which is not available in ICLR this year). I want to thank the authors for addressing the other issues/questions I raised.
----------------------------------------- Original Review Below -----------------------------------------
Summary: The author proposes a new way to improve the supervision of training encoder-decoder Transformers so that it can make flexible, depth-adaptive predictions at inference time. The paper compares multiple dynamic computation schemes to investigate the effectiveness of these different approaches (e.g., at both sequence and token levels). Relatively extensive experiments were conducted in different settings (on a small and a large MT dataset).
While the dynamic halting on Transformers has been previously explored in the Universal Transformers paper, this technique has not been applied to standard (encoder-)decoder Transformers. I think this is an interesting and exciting topic to pursue, as the authors seem to demonstrate (at least on the small IWSLT'14 DE-EN dataset) that we may not need as many layers at the decoding phase as we thought (and thus # of FLOPs).  
However, I think the paper can be further improved in terms of both its organization/clarity and its experimental study (see details following).
--------------------------------------------
Questions/comments:
1. Please add a Related Work section. While using dynamic halting on standard Transformers may be novel, general dynamic routing on deep networks (which also aims to reduce the computation) is not. For example, SkipNet [1] uses an input-based dynamic skipping to bypass certain layers of a DNN. It's a good scholarship to give proper credit to prior related work(s).
2. I think Poisson binomial (PB) may be a misnomer for the second qt modeling technique. PB is a probability distribution on the __sum__ of N (unequal) Bernoulli trials [2], which doesn't make sense here. What you are looking for, I think, is a learned "coin flip" at every layer of the network to decide whether to continue to the next layer (i.e., you are looking for the first "head" in the coin flips, instead of the sum of heads). And indeed, in Eq. (9), the definition for qt(n|...) is a "geometric-alike" distribution with success probability \chi_{t,n} at the n^th flip. (Which brings to a side point: for the "otherwise" case in Eq. (9), I think you mean \prod_n (1-\chi_{t, n}); otherwise you can't guarantee \sum_n qt(n|...) = 1 :-) )
3. Why and how did you pick the exit threshold \chi_{t, n} > 0.5 for your experiments? According to your definition of \chi_{t,n} and q_t in Eq. (9), isn't the correct thing to do to sample from \chi_{t, n}? My major concern is that, given different \sigma (which you didn't specify, but I guess is something like a sigmoid), your \chi_{t, n} may land in very different ranges. What if you have the following case: \chi_{t, 1} = 0.501, \chi_{t, 2} = 0.1, \chi_{t,3} = 0.999, \chi_{t,4} = 0.95? Doesn't this mean it may worth it to stop at the 3rd layer instead? (Using the coin flip analogy, having a coin with head probability 0.501 doesn't necessarily mean you "must" get a "head" at the first flip.) Moreover, if I use $\sigma = sigmoid(x)/2 + 0.5$, won't I always get a \chi > 0.5?
4. In the token-specific likelihood-based method, you used an RBF kernel to model the influence of a time step t on its neighboring time steps. Two questions: 1) When you do \sum_{t'}, did you also include t'<t? 2) Have you tried any other kernels, and how does this choice affect the performance?
5. The aligned training is actually a type of intermediate auxiliary loss (or deep supervision, as the computer vision community probably more often calls it), which makes it not surprising that the unaligned Transformer could perform slightly better than the baseline. I find it interesting that the mixed training strategy doesn't work.
6. Why did you use different training schemes for WMT'14 and IWSLT'14 (e.g., freezing the parameters, etc.)?
7. One of the major concerns I have is that the empirical results don't seem that impressive. First, to demonstrate the effectiveness of the proposed adaptive depth estimation methodology, besides comparing to the baseline (black line) in Figures 3 & 4, you should also compare with the blue line (which adds these auxiliary losses to the baseline, but doesn't use the adaptive strategy that involves qt(n|...) at all) for fairness. From Figures 3 & 4, it seems that the adaptive-depth predictions are usually in the close neighborhood of the blue lines when at the same value of AE (instead of substantial, consistent improvement). In addition, while Tok-LL Poisson did well in Figure 4(b), it didn't seem to make a difference in Figure 4(a), which is where one is supposed to tune the hyperparameters on (such as \lambda, \sigma; see #8 below). This makes me a bit dubious about how much help the adaptive module brought, compared to just using the aligned model.
8. For the WMT'14 experiments (Figure 4), why is there only one run of the "Tok-LL Poisson"? My understanding is that, if you are to use the proposed approach on a new dataset, you would want to try different settings of (\sigma, \lambda) on the validation set and pick the best one to use for testing. In Figure 4(a), for instance, for Seq-LL I would probably pick the (\sigma, \lambda) setting corresponding to the top-right yellow square--- which turns out to be slightly worse than the blue line on the test set (Figure 4(b)). It'd be useful to plot more "red triangles" in Figure 4 to evaluate how much the adaptive-depth methodology contributes to the performance.
========================
Some minor errors that don't have much impact on the score:
9. The beginning sentence of the 4th paragraph of Section 1 is a bit strange (grammatically).
10. Not all equations are numbered! See section 2.
11. In the first equation of Section 2, do you mean h_{\leq t}^{n-1} rather than h_{< t}^{n-1}? I think h_t from the previous layer is also used?
12. In the 3rd equation of Eq. (12), you should have m somewhere within the summation.
13. Equation (7) missing a right parenthesis.
14. In Eq. (8) W_h is a matrix, whereas in Eq. (9) W_h is a vector (if I'm not mistaken)? Maybe use a lowercase w.
15. Inconsistent notations. For instance, as I described in #3 above, you didn't say in the paper what \sigma means in Eq. (9), but later re-used the same letter for a different meaning in Eq. (11) for the RBF kernel. Another example is the usage of \theta_n in the "Confidence thresholding" paragraph for the threshold value; you used the same letter again in the "Gradient scaling" section of the appendix but with a different meaning (learnable parameters). 
16. In the last sentence of the Likelihood-based token specific depth, I'd suggest \sigma \rightarrow 0 instead of \sigma=0, which would otherwise make \frac{...}{\sigma} in Eq. (11) undefined.
17. I don't think you specified the \theta_n used in your experiments (and how you tune them).
18. What is the FS in Appendix B? Also, for "ffn" in Table 4, it's best to write its full name before referring to it with acronyms.
19. Just curious: how did you implement the gradient scaling described in Appendix A (e.g., ensuring the \gamma_n only applies to block n, but not blocks < n)?
========================
I think the current shape of the paper is marginally below the acceptance threshold. (Note that while the rating is "3 - Weak reject", I don't mean the score, but only the "weak reject" part. I'm still excited about the idea of applying dynamic computation in Transformer.) But I'm happy to consider adjusting the score if my concerns above can be satisfactorily addressed.
[1] https://arxiv.org/abs/1711.09485
[2] https://en.wikipedia.org/wiki/Poisson_binomial_distribution