How to Deal with the ``Never-Ending'' Problem in Seq2Seq?

Deterministic Decoding

Deterministic decoding algorithms ensure that 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 a special case of Beam Search, so we only need to discuss the latter.

In Beam Search, we fix a “beam size” k and decode tokens one by one from left to right, keeping only the k sequences with the highest total scores at each step. For example, if k=2 and the token space is V=\{a,b,c,d\}, the decoding process might look like this:

Step 1: Calculate p(y_1|y_0,x) (y_0 is the fixed start tag <bos>), then keep the two largest, e.g., \{a,b\}, and record their scores (log-probabilities).

Step 2: Calculate 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. Keep the two with the highest total scores (current token score plus the score of a or b itself), e.g., \{(a,c),(b,d)\}, and record their total scores.

Step 3: Calculate p(y_3|y_0,a,c,x) and p(y_3|y_0,b,d,x). There are again k \times |V| = 8 candidate sequences. Keep the two with the highest total scores, e.g., \{(a,c,d),(a,c,c)\}, and record their total scores.

...

By parity of reasoning, each sequence stops when <eos> appears. Finally, the best one is selected from the k completed sequences. There are generally two choices: outputting the one with the highest total score, or the one with the highest average score (divided by the number of tokens). Sometimes, length penalties are added based on actual needs.

Stochastic Decoding

Stochastic decoding algorithms, as the name suggests, mean that even if the input text is fixed, the decoded output is not. For example, random sampling from a trained language model is such an algorithm (refer to “Playing with Chinese GPT2 using Keras”). For Seq2Seq, we often want deterministic results, so Beam Search is used in most scenarios. However, Beam Search results may be too generic (e.g., “Okay,” “I don’t know,” “Thank you”), or sometimes we want to increase output diversity (e.g., the SimBERT model we open-sourced for similarity sentence generation). In these cases, stochastic decoding is needed, which includes three types: Pure Random Sampling, Top-k Sampling, and Nucleus Sampling.

Pure Random Sampling is simple: at each step, a token is randomly sampled according to its probability. For example, step one calculates p(y_1|y_0,x) and samples a token, say c; step two calculates p(y_2|y_0,c,x) and samples a; step three calculates p(y_3|y_0,c,a,x), and so on, until <eos> is sampled.

Top-k Sampling comes from the paper “Hierarchical Neural Story Generation”. It adds a truncation to pure random sampling: at each step, only the k tokens with the highest probabilities are kept, and then sampling is performed after re-normalization. This aims to strike a balance between “high score” and “diversity.” Obviously, when k=1, it is equivalent to Greedy Search.

Nucleus Sampling comes from the paper “The Curious Case of Neural Text Degeneration”. Similar to top-k, it truncates the sampling space: fix p \in (0, 1), and keep only the top tokens whose cumulative probability just exceeds p. This is also called top-p sampling.

Besides top-k and top-p, there are adaptive truncation methods. For example, the paper “Sparse Sequence-to-Sequence Models” replaces the softmax function with a sparse version, which automatically sets the probability of most impossible tokens to 0 without needing to manually choose k or p.

Bounded Hidden Vectors

The classic way to model the probability in \eqref{eq:p} is: p(y_t|y_{< t}, x)=\text{softmax}(Wh_t+b),\quad h_t=f(y_{< t}, x) That is, a hidden vector h_t is calculated, followed by a fully connected layer and softmax activation. In this form, the original paper states:

If \|h_t\| is bounded for any t, then pure random sampling can “know when to stop.”

This sounds like a very strong and practical conclusion, doesn’t it? Making \|h_t\| bounded is easy—for example, by adding Layer Norm. Does this mean adding Layer Norm solves everything? Not quite. The conclusion is theoretically correct, and the reasoning is: because \|h_t\| is bounded, for any t and any token, p(y_t|y_{< t}, x) has a positive lower bound (since Wh_t won’t be infinitely large, e^{Wh_t} won’t be infinitely large, and after normalization, it won’t be infinitely close to 0). This means there exists an \epsilon > 0 such that p(\text{\texttt{<eos>}}|y_{< t}, x) \geq \epsilon. Since the probability is a positive constant, as long as you sample enough steps, you will eventually sample <eos>, so it won’t run forever.

Isn’t this reasoning a bit laughable? Yes, it can stop, but it might require sampling a huge number of steps. It’s like saying “as long as you buy enough lottery tickets, you will eventually win the jackpot”—it lacks practical value. By the time it stops after many steps, the looping or repeating tokens might have already appeared many times. Even if it stops, the output might be meaningless, perhaps even worse than simple length truncation.

Actively Adding <eos>

Note that the above conclusion only holds for pure random sampling. For top-k and Nucleus sampling, it doesn’t necessarily hold because <eos> might not appear in the truncated sampling space. Of course, we can manually add <eos> back into the sampling space, leading to the following conclusion:

If \|h_t\| is bounded for any t, and we add <eos> to the sampling space, then top-k and Nucleus sampling can “know when to stop.”

However, this feels a bit like a truism...

Self-Truncating Design

Note that the two conclusions above only apply to stochastic decoding. For deterministic decoding, since there is no randomness, we cannot guarantee hitting <eos>. To this end, the original paper proposes a self-truncating design: find a way to make p(\text{\texttt{<eos>}}|y_{< t}, x) have a positive lower bound that increases with t and eventually approaches 1.

This self-truncating design is not complicated. It defines p(\text{\texttt{<eos>}}|y_{< t}, x) = 1 - \alpha(h_t), where: \begin{aligned} \alpha(h_0)=&\,\sigma\left(w_{\text{\texttt{<eos>}}}^{\top} h_0 + b_{\text{\texttt{<eos>}}}\right) \\ \alpha(h_t)=&\,\sigma\left(w_{\text{\texttt{<eos>}}}^{\top} h_t + b_{\text{\texttt{<eos>}}}\right)\left[1 - p(\text{\texttt{<eos>}}|y_{< {t-1}}, x)\right] \end{aligned} Here \sigma(\cdot) maps \mathbb{R} to [0, 1-\epsilon]; for example, one could use \sigma(\cdot)=(1-\epsilon)\text{sigmoid}(\cdot). After designing p(\text{\texttt{<eos>}}|y_{< t}, x), the probabilities of the remaining tokens are calculated using the original softmax and then multiplied by \alpha(h_t).

Now we have: \begin{aligned} p(\text{\texttt{<eos>}}|y_{< t}, x)=&\,1 - \sigma\left(w_{\text{\texttt{<eos>}}}^{\top} h_t + b_{\text{\texttt{<eos>}}}\right)\left[1 - p(\text{\texttt{<eos>}}|y_{< {t-1}}, x)\right]\\ =&\,1 - \prod_{i=0}^t\sigma\left(w_{\text{\texttt{<eos>}}}^{\top} h_i + b_{\text{\texttt{<eos>}}}\right)\\ \geq&\, 1 - (1 - \epsilon)^{t+1} \end{aligned} Clearly, as long as t > -\ln 2/\ln (1-\epsilon), p(\text{\texttt{<eos>}}|y_{< t}, x) > 0.5. This means Greedy Search must stop within -\ln 2/\ln (1-\epsilon) steps. As p(\text{\texttt{<eos>}}|y_{< t}, x) approaches 1, Beam Search will also stop within finite steps.