How to Deal with the "It Just Won't Stop" Problem in Seq2Seq?

如何应对Seq2Seq中的“根本停不下来”问题？ 苏剑林 · 2020-06-16 · Machine Learning language model text generation decoding

During Seq2Seq decoding, we generate tokens recursively one by one until an <eos> marker appears — this is the so-called "autoregressive" generative model. However, readers who have worked with Seq2Seq have probably noticed that this kind of autoregressive decoding occasionally exhibits a phenomenon where it "just won't stop": some segment keeps repeating over and over, like "the weather's nice today nice nice nice nice nice..." or "do you think I'm right or not not not not not not...", but the <eos> marker simply refuses to show up no matter what. The ICML 2020 paper Consistency of a Recurrent Language Model With Respect to Incomplete Decoding] discusses this phenomenon fairly systematically and proposes some countermeasures. This post gives a brief overview of the paper's main content.

Decoding Algorithms

For an autoregressive model, we build the following conditional language model

\begin{equation}p(y_t|y_{\lt t}, x)\label{eq:p}\end{equation}

The decoding algorithm, then, is what we use — given this model and given $x$ — to produce the corresponding output $y=(y_1,y_2,\dots,y_T)$. Decoding algorithms can broadly be split into two categories: deterministic decoding algorithms and stochastic decoding algorithms. The original paper discusses the "it just won't stop" problem separately for each of these two categories, so we need to first get familiar with both types of decoding algorithms. more

Deterministic Decoding

Deterministic decoding algorithms are ones where, once the input text is fixed, the decoded output text is also fixed. This category includes greedy search and beam search; in fact, greedy search is just a special case of beam search, so we only need to discuss beam search.

For beam search we need to fix a beam size $k$, and then decode token by token from left to right, keeping only the $k$ sequences with the highest total score at each step. For example, suppose $k=2$, and the token space is $V=\{a,b,c,d\}$. Then the decoding process looks something like this:

Step 1: compute $p(y_1|y_0,x)$ ($y_0$ is the fixed start token <bos>), then keep the top two, say $\{a,b\}$, and record their scores (log-probabilities);
Step 2: compute $p(y_2|y_0,a,x)$ and $p(y_2|y_0,b,x)$. At this point there are $k\times |V|=8$ candidate sequences in total; keep the two with the highest total score (i.e., the current token's score plus the score of $a$, $b$ themselves), say $\{(a,c),(b,d)\}$, and record their respective total scores;
Step 3: compute $p(y_3|y_0,a,c,x)$ and $p(y_3|y_0,b,d,x)$. At this point there are $k\times |V|=8$ candidate sequences in total; keep the two with the highest total score (i.e., the current token's score plus the score of $(a,c)$, $(b,d)$ themselves), say $\{(a,c,d),(a,c,c)\}$, and record their respective total scores;
...
And so on: each sequence stops once <eos> appears, and finally we pick the best among these $k$ completed, terminated sequences as the output. There are generally two ways to choose the best one: outputting the sequence with the highest total score, or the one with the highest average score (dividing by the respective token count); sometimes a length penalty or similar is added depending on the actual use case.

Stochastic Decoding

Stochastic decoding algorithms, as the name suggests, are ones where, even with a fixed input text, the decoded output text is not fixed. For example, randomly sampling from a trained language model is this kind of algorithm (see Playing with Chinese GPT2 Using Keras Now]). For Seq2Seq, we often want a deterministic result, so in most scenarios we use beam search. But beam search's output can end up being overly uniform (i.e., producing "safe" replies like "OK", "I don't know", "thanks"), or sometimes we want to increase the diversity of the output (as with our previously open-sourced SimBERT] model for generating similar sentences). In such cases we need stochastic decoding algorithms, which come in three flavors: plain stochastic decoding, top-k stochastic decoding, and nucleus stochastic decoding.

Plain stochastic decoding is simple: at each step we randomly sample a token according to its probability. For example, at step 1 we compute $p(y_1|y_0,x)$ and then randomly sample a token according to probability, say $c$; then at step 2 we compute $p(y_2|y_0,c,x)$ and again randomly sample a token according to probability, say $a$; then at step 3 we compute $p(y_3|y_0,c,a,x)$ and sample again; and so on, until we sample <eos> and stop.

Top-k stochastic decoding comes from the paper Hierarchical Neural Story Generation]. It's essentially plain stochastic decoding with a truncation added: at each step we keep only the $k$ tokens with the highest probability, renormalize, and then sample — the idea being to strike a balance between "high score" and "diversity." Clearly, when $k=1$, this is equivalent to greedy search.

Nucleus stochastic decoding comes from the paper The Curious Case of Neural Text Degeneration]. Similar to top-k decoding, it also truncates the sampling space, but the truncation rule is: fix $p\in(0, 1)$, and keep only the smallest set of highest-probability tokens whose cumulative probability just exceeds $p$ — hence it's also called top-p sampling.

Besides these two truncation strategies (top-k and top-p), there are also some adaptive truncation approaches. For example, the paper Sparse Sequence-to-Sequence Models] replaces the final softmax used for prediction with a sparse variant, which automatically zeroes out the probabilities of most impossible tokens without requiring us to manually choose $k$ or $p$.

Stopping When Appropriate

Looking at the design of Seq2Seq models and the decoding algorithms described above, there's no theoretical guarantee that decoding will ever stop — that is, nothing guarantees that <eos> will actually appear. This has to be learned by the model itself, and when the model hasn't learned it well enough, we get the "it just won't stop" phenomenon. The original paper analyzes different decoding algorithms and proposes corresponding strategies to make decoding "stop when appropriate."

Bounded Hidden Vectors

The classic way to model the probability $\eqref{eq:p}$ is

\begin{equation}p(y_t|y_{\lt t}, x)=softmax(Wh_t+b),\quad h_t=f(y_{\lt t}, x)\end{equation}

That is, we first compute a hidden vector $h_t$, then apply a fully connected layer, then a softmax activation. Under this formulation, the original paper states:

If $\Vert h_t\Vert$ is bounded for all $t$, then plain stochastic decoding can "stop when appropriate."

Sounds like a strong and useful conclusion, doesn't it? Making $\Vert h_t\Vert$ bounded is very easy — just add a layer norm, say. So does that mean adding a layer norm solves everything? Not quite. The conclusion above is theoretically correct, and the reasoning goes as follows: since $\Vert h_t\Vert$ is bounded, for any $t$ and any token, $p(y_t|y_{\lt t}, x)$ has a positive lower bound (because $Wh_t$ can't blow up to infinity, $e^{Wh_t}$ can't either, and after normalization the probability won't get arbitrarily close to 0 either). This means there exists a positive number $\epsilon > 0$ such that $p(\text{}|y_{\lt t}, x)\geq \epsilon$ always holds. Since a probability is a positive number, as long as you sample enough steps, you'll eventually have a chance of sampling <eos>, so it won't run forever.

Isn't this reasoning a bit laughable? Sure, it will eventually stop, but only after sampling "enough" steps — it's a bit like saying "you're guaranteed to win the jackpot as long as you buy enough lottery tickets." It doesn't really have much concrete practical value. By the time you've sampled enough steps, whatever token was going to loop or repeat has probably already repeated many times over; even if it eventually stops, the resulting output may no longer be meaningful — you might as well just truncate by length directly.

Actively Adding <eos>

Note that the conclusion above holds only for plain stochastic decoding, and not necessarily for top-k or nucleus stochastic decoding, because after truncation, <eos> might not even be in the sampling space anymore. Of course, we can manually add <eos> to the sampling space, which gives us the following conclusion:

If $\Vert h_t\Vert$ is bounded for all $t$, and we also add <eos> to the sampling space, then top-k and nucleus stochastic decoding can "stop when appropriate."

Except this is a bit of a tautology...

Self-Truncating Design

Note that the two conclusions above apply only to stochastic decoding. For deterministic decoding, since there's no randomness involved, we can't guarantee that <eos> will ever be hit. To address this, the original paper proposes a self-truncating design: try to make $p(\text{}|y_{\lt t}, x)$ have a positive lower bound that increases as $t$ increases, eventually approaching 1.

This self-truncating design isn't complicated either. It defines $p(\text{}|y_{\lt t}, x) = 1 - \alpha(h_t)$, where

\begin{equation}\begin{aligned} \alpha(h_0)=&\,\sigma\left(w_{\text{}}^{\top} h_0 + b_{\text{}}\right) \\ \alpha(h_t)=&\,\sigma\left(w_{\text{}}^{\top} h_t + b_{\text{}}\right)\left[1 - p(\text{}|y_{\lt {t-1}}, x)\right] \end{aligned}\end{equation}

Here $\sigma(\cdot)$ maps $\mathbb{R}$ to $[0, 1-\epsilon]$ — for example, $\sigma(\cdot)=(1-\epsilon)\text{sigmoid}(\cdot)$ could be used. Once $p(\text{}|y_{\lt t}, x)$ is defined, the remaining token probabilities are still computed the usual softmax way, and then multiplied by $\alpha(h_t)$.

Now we have

\begin{equation}\begin{aligned} p(\text{}|y_{\lt t}, x)=&\,1 - \sigma\left(w_{\text{}}^{\top} h_t + b_{\text{}}\right)\left[1 - p(\text{}|y_{\lt {t-1}}, x)\right]\\ =&\,1 - \prod_{i=0}^t\sigma\left(w_{\text{}}^{\top} h_i + b_{\text{}}\right)\\ \geq&\, 1 - (1 - \epsilon)^{t+1} \end{aligned}\end{equation}

Clearly, as long as $t > -\ln 2/\ln (1-\epsilon)$, $p(\text{}|y_{\lt t}, x) > 0.5$ — which means that greedy search is guaranteed to stop within $-\ln 2/\ln (1-\epsilon)$ steps. And since $p(\text{}|y_{\lt t}, x)$ gets closer and closer to 1, beam search will clearly also be able to stop within a finite number of steps.

My Take

That's essentially the main content of the original paper. On the whole, it does offer us some new insight into decoding algorithms, along with some effective strategies for mitigating the "it just won't stop" problem. However, as an ICML paper, I feel its perspective isn't particularly deep, and overall it comes across as somewhat shallow.

Most of the paper's length is spent re-formulating existing content in mathematical language — defining precisely what a decoding algorithm is, what top-k stochastic decoding is, what beam search is, what "it just won't stop" means, and so on. This isn't meaningless in itself, but it doesn't add much value to the actual problem the paper set out to address, and once you strip that part away, there isn't much content left. Second, the paper's conclusions are too weak: as already noted, the countermeasures for stochastic decoding are technically correct but essentially useless in practice; and the self-truncating design for deterministic decoding feels quite crude — more like a blunt truncation than an elegant solution.

The most important issue is that, when it comes to the "it just won't stop" problem, the paper spends its entirety answering "what is it" and "what can be done about it," without ever exploring "why" it happens. It offers no useful insight into the underlying nature of the phenomenon, and consequently fails to arrive at countermeasures that get closer to the root cause. This, to me, is the hardest part to accept.

Summary

This post introduced Seq2Seq decoding algorithms, discussed the "it just won't stop" phenomenon that can arise during decoding, and presented the countermeasures proposed in an ICML 2020 paper.