A Theoretical Analysis Attempt of the Repetition Problem in Seq2Seq Decoding
Last year I wrote a blog post How to Deal with the "Just Won't Stop" Problem in Seq2Seq], which described how a certain paper handled the phenomenon of Seq2Seq decoding failing to terminate, and pointed out that that paper only offered some strategies for dealing with the problem without providing any theoretical understanding of it. Recently, on Arxiv I came across an AAAI 2021 paper titled A Theoretical Analysis of the Repetition Problem in Text Generation], which analyzes the phenomenon of repetitive decoding in Seq2Seq from a theoretical standpoint. Fundamentally, repetitive decoding and failure to terminate decoding are really the same kind of issue, so this new paper fills in the gap left by the earlier one.
After studying it, I found that this paper does have quite a few noteworthy points, and it's worth reading. I've streamlined, corrected, and generalized parts of the original derivation, and recorded the results here for reference. Also, setting aside the specific problem background, readers can also treat this post as a linear algebra exercise session in matrix analysis—a nice opportunity to review some linear algebra. more
Basic Idea
By "repetitive decoding" we mean that the decoded output contains repeated segments—for example, if the decoded result is "A B C D B C D B C D E F", then "B C D" is a repeated segment, and we say this decoding result exhibits the repetition phenomenon. For simplicity, if during decoding a subsequence $s=[w_1,w_2,\cdots,w_n]$ is followed by the same subsequence $t=[w_1,w_2,\cdots,w_n,w_1]$, we call $[w_1,w_2,\cdots,w_n]$ a "repeated subsequence," and what we want to do now is analyze the probability of such repeated subsequences occurring during decoding.
Some readers might wonder: why does $t$ have an extra $w_1$ appended at the end? As will become clear later, this is purely for convenience of analysis, and there's nothing essential about it. What we want is a representative quantitative metric to measure this repetition problem, ideally one that also suggests some directions for improvement; the exact details of this metric need not concern us too much. Quantifying the research objective is very important—only once we've quantified the goal can we better identify directions for improvement, and can we properly compare the merits of different methods. Otherwise, no matter how heated the argument gets, we'll never arrive at a real conclusion.
To obtain such a metric, let's start with the simple case of binary decoding to get some representative results, and then see whether they generalize to general autoregressive decoders.
Binary Decoding
The general form of an autoregressive model is:
\begin{equation}p(\boldsymbol{y}|\boldsymbol{x}) = \prod_{t=1}^l p(y_t|\boldsymbol{y}_{< t}, \boldsymbol{x})\end{equation}
That is, the decoding at position $t$ depends not only on the input $\boldsymbol{x}$, but also on all the decoding results already obtained before $t$. For simplicity, let's first consider a simpler case, where we assume each decoding step depends only on the result at the immediately preceding time step, i.e.:
\begin{equation}p(\boldsymbol{y}|\boldsymbol{x}) = \prod_{t=1}^l p(y_t|y_{t-1}, \boldsymbol{x})\end{equation}
In this case, for a fixed input $\boldsymbol{x}$, the decoder is in fact just a $n\times n$ transition matrix $\boldsymbol{P}=(P_{i,j})$, where $P_{i,j}$ represents the probability of $j$ following $i$, and $n$ denotes the vocabulary size. This kind of decoder is called a bigram model, 2-gram model, Markov model, and so on. We also need a termination token <eos>—decoding stops upon encountering <eos>—so strictly speaking the transition matrix should be $(n+1)\times (n+1)$; but since we're only concerned with repetition before termination, we only need to consider the $n\times n$ portion excluding <eos>.
What we want to compute is the probability of a repeated subsequence occurring. Suppose $[i, j, k]$ is a length-3 repeated subsequence; then its occurrence probability is the probability of the sequence $[i, j, k, i, j, k, i]$ occurring:
\begin{equation}P_{i,j}P_{j,k}P_{k,i}P_{i,j}P_{j,k}P_{k,i}=P_{i,j}^2 P_{j,k}^2 P_{k,i}^2\end{equation}
Hence, the total probability over all length-3 repeated subsequences is
\begin{equation}\sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 = \text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^3\end{equation}
Here $\otimes$ denotes element-wise multiplication, and $\text{Tr}$ is the trace of the matrix, i.e., the sum of its diagonal elements. Finally, we sum the probabilities of repeated subsequences over all lengths:
\begin{equation}R = \sum_{k=1}^{\infty}\text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^k = \text{Tr}\,\left(\sum_{k=1}^{\infty}(\boldsymbol{P}\otimes\boldsymbol{P})^k\right)\label{eq:r}\end{equation}
This is the probability of repetitive decoding occurring in a binary decoder. Of course, at this point it's still only a theoretical formula, but it is our important starting point. We'll derive both an upper bound and a lower bound for it, in order to obtain more insightful results.
A Lower Bound
It's not easy to see much directly from equation $\eqref{eq:r}$, so let's first derive a more intuitive lower bound for it. Again taking length-3 repeated subsequences as an example, using the AM–GM inequality we obtain:
\begin{equation} \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 = n^3\times\frac{\sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2}{n^3}\geq n^3\times\left(\frac{\sum_{i,j,k} P_{i,j} P_{j,k} P_{k,i}}{n^3}\right)^2 = \frac{(\text{Tr}\, \boldsymbol{P}^3)^2}{n^3} \end{equation}
In fact, we can do even better. Suppose the matrix $\boldsymbol{P}$ has some elements equal to zero; then the number of nonzero elements in $P_{i,j}^2 P_{j,k}^2 P_{k,i}^2$ is no longer $n^3$. Suppose the number of nonzero elements is $N_3(\boldsymbol{P}) < n^3$; then, when applying the AM–GM inequality, we can restrict it to the nonzero elements only, giving a result where the above $n^3$ is replaced by $N_3(\boldsymbol{P})$:
\begin{equation} \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 \geq \frac{(\text{Tr}\, \boldsymbol{P}^3)^2}{N_3(\boldsymbol{P})} \end{equation}
Computing $N_3(\boldsymbol{P})$ directly is difficult, as there's no general closed-form expression, but we can make a simple estimate: let the proportion of nonzero elements in $\boldsymbol{P}$ be $\zeta$, i.e., the number of nonzero elements is $\zeta n^2$; then we may take the proportion of nonzero elements in $P_{i,j}^2 P_{j,k}^2 P_{k,i}^2$ to be approximately $\zeta^3$, while the total number of arrangements is $n^3$, so we may take $N_3(\boldsymbol{P})\sim \zeta^3 n^3$, or more generally $N_k(\boldsymbol{P})\sim \zeta^k n^k$. Note that one can construct examples showing this estimate is neither guaranteed to be an upper bound nor a lower bound, so once we replace $N_3(\boldsymbol{P})$ with $\zeta^3 n^3$, we can no longer guarantee that the above inequality still holds. Still, if we're willing to believe that $\zeta^3 n^3$ is a good enough approximation, we can (with a mixture of trepidation and conviction) write down
\begin{equation} \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 \geq \frac{(\text{Tr}\, \boldsymbol{P}^3)^2}{\zeta^3 n^3} \end{equation}
and
\begin{equation}R = \sum_{k=1}^{\infty}\text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^k \geq \sum_{k=1}^{\infty} \frac{(\text{Tr}\, \boldsymbol{P}^k)^2}{\zeta^k n^k}\label{eq:r-2}\end{equation}
Or we could simply stop worrying about the inequality sign altogether, and instead treat the rightmost expression as an estimate of $R$.
The Original Paper's Lower Bound
For readers who want to read the original paper alongside this post, this might be a bit confusing, since neither equation $\eqref{eq:r}$ nor equation $\eqref{eq:r-2}$ has a direct counterpart in the original paper. In fact, the original paper does not give the exact form of equation $\eqref{eq:r}$, nor does it give the estimate $\eqref{eq:r-2}$; instead it gives a different estimate, which can also be derived as a lower bound for equation $\eqref{eq:r}$.
Again using the AM–GM inequality, we have
\begin{equation}\begin{aligned} \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 =&\, \sum_{i} \sum_{j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2= \sum_{i} n^2\times\frac{\sum_{j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2}{n^2}\\ \geq&\, \sum_{i} n^2\times\left(\frac{\sum_{j,k} P_{i,j} P_{j,k} P_{k,i}}{n^2}\right)^2 = \frac{\text{Tr}\, (\boldsymbol{P}^3\otimes \boldsymbol{P}^3)}{n^2} \end{aligned}\end{equation}
Similarly, we can introduce the nonzero-element-count trick to improve the estimate's precision. The nonzero rate is still $\zeta^3$, but this time the total number being summed is $n^2$, so the number of nonzero arrangements is approximately $\zeta^3 n^2$, so we (again with trepidation and conviction) write down:
\begin{equation} \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 \geq \frac{\text{Tr}\, (\boldsymbol{P}^3\otimes \boldsymbol{P}^3)}{\zeta^3 n^2}\end{equation}
and
\begin{equation}R = \sum_{k=1}^{\infty}\text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^k \geq \sum_{k=1}^{\infty}\frac{\text{Tr}\, (\boldsymbol{P}^k\otimes \boldsymbol{P}^k)}{\zeta^k n^{k-1}}\label{eq:r-3}\end{equation}
This is basically "Definition 2.3" in the original paper. The differences from the original paper are:
1. The original paper computes the average per-token probability, so it needs to be further divided by $n$, hence its denominator is $n^k$;
2. The original paper takes the trace of $\boldsymbol{P}^{2k}$ rather than $\boldsymbol{P}^k\otimes \boldsymbol{P}^k$; in fact, this is an error in the original paper—during its derivation it mistakenly treats $(\boldsymbol{P}^k)_{i,i}^2$ as equal to $(\boldsymbol{P}^{2k})_{i,i}$, when in fact they are not equal. It is equation $\eqref{eq:r-3}$ in this post that gives the correct result.
Preliminary Conclusion
Whether we use equation $\eqref{eq:r-2}$ or equation $\eqref{eq:r-3}$, they have roughly the same form, and we can draw some conclusions from either. At this point, some readers might wonder: the probability distributions produced by the models we typically use all come from softmax, and softmax outputs are never exactly zero, so $\zeta$ should always equal 1 identically—so does introducing $\zeta$ have any value at all?
Not quite. It's true that softmax-produced probability distributions are never strictly zero, but our decoding algorithms often forcibly set them to zero! In the article How to Deal with the "Just Won't Stop" Problem in Seq2Seq] we listed the decoding algorithms commonly used for text generation, which mainly include random sampling and deterministic decoding. Random sampling is further divided into plain random sampling, top-k sampling, and top-p sampling, while deterministic decoding includes greedy search and beam search. Among these five decoding algorithms, all except the least commonly used plain random sampling forcibly retain only a handful of optimal candidates, which is effectively equivalent to truncating the transition matrix directly, greatly reducing the nonzero probability $\zeta$.
Take the most extreme case, greedy search: it's easy to show that it in fact corresponds to the smallest possible nonzero probability $\zeta=1/n$. Since $\zeta$ appears in the denominator, a decrease in $\zeta$ means an increase in the repetition rate $R$, which tells us that greedy search carries a fairly high risk of repetitive decoding. Although this conclusion has only been derived under the assumption of a binary decoding model, the repetitive decoding of greedy search is indeed a phenomenon we frequently observe in practice, so this conclusion and explanation are indeed representative.
An Upper Bound
Having a lower bound, how can we not also have an upper bound? The lower bound helps explain some experimental phenomena, while the upper bound can point us toward ideas for improvement.
To derive the upper bound, we use the following two facts:
1. The trace of a matrix equals the sum of all its eigenvalues;
2. If $\lambda_1(\boldsymbol{A})\geq\lambda_2(\boldsymbol{A})\geq\cdots\geq\lambda_n(\boldsymbol{A})$ are all the eigenvalues of matrix $\boldsymbol{A}$, then $\lambda_1^k(\boldsymbol{A})\geq\lambda_2^k(\boldsymbol{A})\geq\cdots\geq\lambda_n^k(\boldsymbol{A})$ are all the eigenvalues of matrix $\boldsymbol{A}^k$.
So, we can derive:
\begin{equation}\begin{aligned} R =&\, \sum_{k=1}^{\infty}\text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^k = \sum_{k=1}^{\infty}\sum_{i=1}^n\lambda_i\left((\boldsymbol{P}\otimes\boldsymbol{P})^k\right)\\ =&\, \sum_{k=1}^{\infty}\sum_{i=1}^n\lambda_i^k\left(\boldsymbol{P}\otimes\boldsymbol{P}\right) = \sum_{i=1}^n \sum_{k=1}^{\infty}\lambda_i^k\left(\boldsymbol{P}\otimes\boldsymbol{P}\right) \\ =&\, \sum_{i=1}^n \frac{\lambda_i \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}{1 - \lambda_i \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)} \end{aligned}\label{eq:r-4}\end{equation}
The above derivation uses the series $\frac{x}{1-x}=\sum_{k=1}^{\infty} x^k$, which converges only when $|x| < 1$. Conveniently, we can show that the absolute values of the eigenvalues of $\boldsymbol{P}\otimes\boldsymbol{P}$ are necessarily no greater than 1, and are typically strictly less than 1: since $\boldsymbol{P}$ is a transition matrix, each of its rows sums to 1, and hence each row of $\boldsymbol{P}\otimes\boldsymbol{P}$ sums to at most 1. Let $\lambda$ and $\boldsymbol{x}$ be an eigenvalue and its corresponding eigenvector; then $(\boldsymbol{P}\otimes\boldsymbol{P})\boldsymbol{x}=\lambda \boldsymbol{x}$. Without loss of generality, let the element of $\boldsymbol{x}$ with the largest absolute value be $x_1$, and let the corresponding row vector of $\boldsymbol{P}\otimes\boldsymbol{P}$ be $\boldsymbol{q}_1^{\top}$; then we have $|\lambda| |x_1| = |\boldsymbol{q}_1^{\top}\boldsymbol{x}| \leq |x_1|$, from which $|\lambda| \leq 1$ follows, and the conditions for equality to hold are fairly restrictive, so in general $|\lambda| < 1$.
Note that the function $\frac{x}{1-x}$ is monotonically increasing on the interval $[-1,1)$, so the dominant term in equation $\eqref{eq:r-4}$ is the first term $\frac{\lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}{1 - \lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}$. If we really insist on a single overall upper bound, it could be taken as $\frac{n \lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}{1 - \lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}$.
Conclusion, Revisited
This shows that, in order to reduce the repetition rate $R$, we need to find a way to reduce the largest eigenvalue of the matrix $\boldsymbol{P}\otimes\boldsymbol{P}$. Since $\boldsymbol{P}\otimes\boldsymbol{P}$ is a nonnegative matrix, by the "Frobenius intermediate value theorem" for nonnegative matrices, we have:
\begin{equation}\min_i \sum_j P_{i,j}^2 \leq \lambda_1 (\boldsymbol{P}\otimes\boldsymbol{P}) \leq \max_i \sum_j P_{i,j}^2\end{equation}
The Frobenius intermediate value theorem is covered in essentially every book on matrix analysis; it states that "the largest eigenvalue of a nonnegative matrix lies between the minimum and maximum of its row sums." Now we know that in order to reduce the largest eigenvalue of $\boldsymbol{P}\otimes\boldsymbol{P}$, we need to reduce its row sums, namely $\sum_j P_{i,j}^2$, and by the AM–GM inequality
\begin{equation}\sum_j P_{i,j}^2\geq n\left(\frac{\sum_j P_{i,j}}{n}\right)^2 = \frac{1}{n}\end{equation}
we know that its minimum value is $1/n$, attained when $P_{i,1}=P_{i,2}=\cdots=P_{i,n}$. Therefore, we finally arrive at the conclusion: to reduce the largest eigenvalue, we must make each row of the matrix $\boldsymbol{P}$ as uniform as possible—in other words, we must reduce the variance of each row of $\boldsymbol{P}$.
How do we reduce this variance? Quite simply, by avoiding excessively high probability values. For instance, if a given row is close to a one-hot form, then after squaring it will still be close to one-hot, and the sum will be close to 1, far greater than the theoretical minimum of $1/n$. Under what circumstances would we see such excessively high probability values? It's not hard to understand: this happens when a given token is almost always followed by very few—sometimes only one—candidate tokens. For example, in Chinese, "忐" (tǎn) is almost always followed by "忑" (tè), so $P_{i=\text{uneasy},j=\text{uneasy}}$ is quite high there; "矩" (jǔ) is usually followed by either "阵" (forming "矩阵", matrix) or "形" (forming "矩形", rectangle), so the row for "矩" also has non-negligible variance. So how can we avoid such excessively high probability values? Quite simply—merge the tokens with high transition probability into a single new token. For example, if we merge "忐忑" into a single word, then the row for "忐" no longer exists on its own, so its variance is no longer an issue. Likewise, "矩形" and "矩阵" should probably also be merged into single words.
So, in plain terms, this tells us that for text generation tasks, word-level tokenization is more reliable than character-level tokenization (i.e., it is less prone to repetitive decoding). Appropriately merging strongly correlated tokens into new vocabulary entries reduces the variance of the transition matrix, which helps lower the risk of repetitive decoding. The original paper even gave this operation a rather fancy name—the Rebalanced Encoding Algorithm—but that's essentially what it amounts to. Our earlier word-granularity WoBERT model performing better than character-granularity BERT on generation tasks can also be seen as a validation of this conclusion (see Faster Without Sacrificing Accuracy: Chinese WoBERT at Word Granularity]).
General Decoding
Is this derivation easy to generalize to general autoregressive models? Unfortunately, not really. For a general autoregressive model, the effective transition $\boldsymbol{P}$ is different at every step, so as long as the model's performance is good enough, repetitive decoding basically shouldn't occur. Indeed, generative models that have undergone sufficient pretraining rarely exhibit repetitive decoding. But we can nonetheless observe that even ordinary autoregressive decoding occasionally exhibits repetitive decoding, especially in models without pretraining—how should this be explained?
The preceding sections were based on the binary decoding model, and concluded that binary decoding models are indeed prone to repetitive decoding. So perhaps we can flip the reasoning around: perhaps the reason repetitive decoding appears in a general autoregressive model is that, at that particular moment, the model has degenerated into a binary decoding model? For inputs of high difficulty, the model might fail to finely capture the transition probability at each step, and thus effectively collapse the transition matrix down to binary decoding—this is plausible.
So how does the original paper handle this? Roughly along similar lines. The original paper assumes that the transition "matrix" of a general autoregressive model is simply the binary-decoding transition matrix $\boldsymbol{P}$ plus a time-step-specific perturbation $\tilde{\boldsymbol{P}}_t=\boldsymbol{P}+\boldsymbol{Q}_t$, and then points out that when $\boldsymbol{Q}_t$ is small enough, the gap from binary decoding is also small enough (which is a bit of a tautology). Hence, the results for binary decoding can also be taken as representative of the general autoregressive model. So, when it comes to general autoregressive models, we're admittedly on somewhat weak footing—this is about the closest connection we can draw.
Summary
This post has been an attempt at a theoretical analysis of the repetitive decoding phenomenon in Seq2Seq. Most of the space is devoted to deriving quantitative results for the binary decoding model, and we found that these results do indeed explain some observed phenomena and also suggest some directions for improvement. Finally, we somewhat "forcedly" connected the binary decoding model to general autoregressive models. The ideas in this post were inspired by the paper A Theoretical Analysis of the Repetition Problem in Text Generation], but the derivations here were worked out independently, and the formula definitions differ slightly from those in the original paper, though the overall conclusions are consistent. I'll leave it to readers to judge for themselves, and please do point out any errors.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.