A Theoretical Analysis Attempt of the Repetition Phenomenon in Seq2Seq

Basic Idea

Repetition decoding refers to the appearance of repeated fragments in the decoding result. For example, if the decoding result is "A B C D B C D B C D E F", then "B C D" is a repeated fragment. For simplicity, if a subsequence s=[w_1, w_2, \dots, w_n] is followed by t=[w_1, w_2, \dots, w_n, w_1] during decoding, we call [w_1, w_2, \dots, w_n] a "repetition subsequence." Our task now is to analyze the probability of such repetition subsequences appearing during the decoding process.

Some readers might wonder why an extra w_1 is added to the end of t. As we will see later, this is merely for analytical convenience and is not strictly necessary. What we want is a representative quantitative indicator to measure this repetition problem, ideally one that provides insights for improvement. As for the specific details of this indicator, we don’t need to worry too much. Quantifying the research objective is very important; only after quantification can we better grasp the direction of improvement and compare the pros and cons of different methods. Otherwise, even if we argue until we are red in the face, we will never reach a conclusion.

To obtain such an indicator, we will start with simple bigram decoding to derive some representative results and then see if they can be generalized to general autoregressive decoders.

Bigram Decoding

The general form of an autoregressive model is: p(\boldsymbol{y}|\boldsymbol{x}) = \prod_{t=1}^l p(y_t|\boldsymbol{y}_{< t}, \boldsymbol{x}) That is, the decoding at position t depends not only on the input \boldsymbol{x} but also on all previous decoding results before t. For simplicity, let’s first consider a simple case where each decoding step only depends on the result of the previous moment: p(\boldsymbol{y}|\boldsymbol{x}) = \prod_{t=1}^l p(y_t|y_{t-1}, \boldsymbol{x}) In this case, for a fixed input \boldsymbol{x}, the decoder is essentially just an n \times n transition matrix \boldsymbol{P}=(P_{i,j}), where P_{i,j} represents the probability of j following i, and n represents the vocabulary size. Such a decoder is called a bigram model, 2-gram model, or Markov model, etc. We also need a termination token <eos>; decoding stops when <eos> is encountered. So the transition matrix should actually be (n+1) \times (n+1), but since we consider repetition before termination, we only need to consider the n \times n part excluding <eos>.

We want to calculate the probability of a repetition subsequence appearing. If [i, j, k] is a trigram repetition subsequence, its probability of occurrence is the probability of the sequence [i, j, k, i, j, k, i] appearing: 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 Therefore, the probability of all trigram repetition subsequences is: \sum_{i,j,k} P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 = \text{Tr}\,(\boldsymbol{P}\otimes\boldsymbol{P})^3 Here \otimes denotes element-wise multiplication (Hadamard product), and \text{Tr} is the trace of the matrix, i.e., the sum of the diagonal elements. Finally, we sum the probabilities of repetition subsequences of all lengths: 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} This is the probability of repetition decoding occurring in a bigram decoder. While it is currently just a theoretical formula, it is our important starting point. We will derive its upper and lower bounds to obtain more instructive results.

A Lower Bound

It is difficult to see much directly from Equation [eq:r], so we can first derive a more intuitive lower bound. Taking the trigram repetition subsequence as an example, using the AM-GM inequality (specifically the power mean inequality), we get: \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} In fact, we can be more precise. Suppose some elements of matrix \boldsymbol{P} are 0, then the number of non-zero elements in P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 is not n^3. Let the number of non-zero elements be N_3(\boldsymbol{P}) < n^3. When using the inequality, we can apply it only to the non-zero elements, replacing n^3 with N_3(\boldsymbol{P}): \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})} Directly calculating N_3(\boldsymbol{P}) is difficult as there is no general formula, but we can make a simple estimate: let the ratio of non-zero elements in \boldsymbol{P} be \zeta, meaning the number of non-zero elements is \zeta n^2. Then we can assume the ratio of non-zero elements in P_{i,j}^2 P_{j,k}^2 P_{k,i}^2 is approximately \zeta^3, and the total number of permutations is n^3, so we can estimate N_3(\boldsymbol{P}) \sim \zeta^3 n^3, or generally N_k(\boldsymbol{P}) \sim \zeta^k n^k. Note that one could find examples where this estimate is neither a guaranteed upper bound nor a lower bound, so after replacing N_3(\boldsymbol{P}) with \zeta^3 n^3, we cannot strictly guarantee the inequality. However, if we believe \zeta^3 n^3 is a sufficiently good approximation, we can still (with a mix of trepidation and firm belief) write: \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} And: 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} Or we can simply stop worrying about the inequality sign and treat the rightmost result as an estimate of R.

The Original Paper’s Lower Bound

Readers wishing to compare this with the original paper might be confused, as neither Equation [eq:r] nor Equation [eq:r-2] appears there. In fact, the original paper does not provide the exact Equation [eq:r] or the estimate Equation [eq:r-2], but rather another estimate, which can also be derived as a lower bound of Equation [eq:r].

Using the AM-GM inequality again, we have: \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} Similarly, introducing the non-zero element count trick, the non-zero ratio is still \zeta^3, but this time the total sum is over n^2 elements, so the number of non-zero permutations is approximately \zeta^3 n^2. Thus we write: \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} And: 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} This is essentially "Definition 2.3" in the original paper. The differences are:

1. The original paper calculates the probability averaged per word, so it divides by an additional n, making its denominator n^k.

2. The original paper takes the trace of \boldsymbol{P}^{2k} instead of \boldsymbol{P}^k \otimes \boldsymbol{P}^k. This is actually an error in the original paper; in its derivation, it treated (\boldsymbol{P}^k)_{i,i}^2 as (\boldsymbol{P}^{2k})_{i,i}, which are not equal. Equation [eq:r-3] in this article is the correct result.

Preliminary Conclusion

Whether using Equation [eq:r-2] or Equation [eq:r-3], the forms are similar, and we can use them to draw conclusions. At this point, some readers might wonder: the probability distributions of the models we use are usually produced by softmax, and softmax results are never zero, so \zeta should always be 1. Does introducing \zeta have any value?

Not necessarily. Indeed, the probability distribution from softmax is never strictly zero, but our decoding algorithms often force them to be zero! In the article "How to Deal with the ’Never-Ending’ Problem in Seq2Seq?", we listed common decoding algorithms, mainly including random sampling and deterministic decoding. Random sampling includes direct sampling, Top-k sampling, and Top-p sampling, while deterministic decoding includes Greedy Search and Beam Search. Among these five, except for the rarely used direct random sampling, the other four force the retention of only a few optimal results as candidates. This is equivalent to directly truncating the transition matrix, greatly reducing the non-zero probability \zeta.

For example, in the most extreme case, Greedy Search, it is easy to see that it corresponds to the smallest non-zero probability \zeta=1/n. Since \zeta is in the denominator, a decrease in \zeta means an increase in the repetition rate R. This tells us that the risk of repetition decoding in Greedy Search is quite high. Although this conclusion is derived under the assumption of a bigram decoding model, repetition in Greedy Search is indeed a phenomenon we frequently observe, so this conclusion and explanation are already representative.

An Upper Bound

Since we have a lower bound, how can we not have an upper bound? Lower bounds help us explain experimental phenomena, while upper bounds provide ideas for improvement.

To derive the upper bound, we use the following two conclusions:

1. The trace of a matrix is equal to 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.

Thus, we can derive: \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} The above process uses the series \frac{x}{1-x}=\sum_{k=1}^{\infty} x^k, which only converges when |x| < 1. Coincidentally, we can prove that the absolute values of the eigenvalues of \boldsymbol{P}\otimes\boldsymbol{P} are never greater than 1 and are usually less than 1. Since \boldsymbol{P} is a transition matrix, the sum of each of its rows is 1. Therefore, the sum of each row of \boldsymbol{P}\otimes\boldsymbol{P} is less than or equal to 1. Let \lambda and \boldsymbol{x} be its eigenvalue and eigenvector, so (\boldsymbol{P}\otimes\boldsymbol{P})\boldsymbol{x}=\lambda \boldsymbol{x}. Without loss of generality, let x_1 be the element with the largest absolute value in \boldsymbol{x}, and let \boldsymbol{q}_1^{\top} be the first row vector of \boldsymbol{P}\otimes\boldsymbol{P}. Then we have |\lambda| |x_1| = |\boldsymbol{q}_1^{\top}\boldsymbol{x}| \leq |x_1|, hence |\lambda| \leq 1. The conditions for the equality to hold are quite strict, so usually |\lambda| < 1.

Note that the function \frac{x}{1-x} is monotonically increasing in the interval [-1, 1), so the dominant term in Equation [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 must provide an overall upper bound, it could be \frac{n \lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}{1 - \lambda_1 \left(\boldsymbol{P}\otimes\boldsymbol{P}\right)}.

Second Conclusion

It can be seen that if we want 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 non-negative matrix, according to the "Frobenius Inclusion Theorem", we have: \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 The Frobenius Inclusion Theorem is introduced in almost any matrix analysis book; it states that the largest eigenvalue of a non-negative matrix lies between the minimum and maximum row sums. Now we know that to reduce the largest eigenvalue of \boldsymbol{P}\otimes\boldsymbol{P}, we need to reduce its row sums, i.e., \sum_j P_{i,j}^2. According to the AM-GM inequality: \sum_j P_{i,j}^2 \geq n\left(\frac{\sum_j P_{i,j}}{n}\right)^2 = \frac{1}{n} The minimum value is 1/n, achieved when P_{i,1}=P_{i,2}=\cdots=P_{i,n}. Therefore, we conclude: To reduce the largest eigenvalue, the rows of matrix \boldsymbol{P} should be as uniform as possible; in other words, the variance of each row of \boldsymbol{P} should be reduced.

How do we reduce the variance? Simply put, we cannot have excessively high probability values. For example, if a row is close to a one-hot form, it will still be close to one-hot after squaring, and the sum will be close to 1, which is much larger than the theoretical minimum 1/n. Under what circumstances do excessively high probability values appear? It’s not hard to understand: it happens when there are very few words that can follow a certain word, perhaps even only one candidate. For example, in Chinese, the character "Tan" is almost always followed by "Te", so P_{i=\text{Tan}, j=\text{Te}} is very high. Similarly, "Ju" is likely followed by "Zhen" or "Xing", so the variance of the row for "Ju" is also not small. How can we avoid such high probability values? Simply merge the high-probability sequences and treat them as a new single word. For example, if "Tan-Te" is merged into one word, the row for "Tan" no longer exists, and the variance issue disappears. Similarly, "Ju-Xing" and "Ju-Zhen" should also be merged into single words.

So, in plain terms, this tells us that for text generation tasks, using words as units is more reliable than using characters (less likely to cause repetition decoding). Appropriately merging highly correlated words into new vocabulary entries to reduce the variance of the transition matrix helps reduce the risk of repetition decoding. The original paper gave this operation a high-sounding name: Rebalanced Encoding Algorithm. Our previous word-level WoBERT performed better on generation tasks than the character-level BERT, which can be seen as a verification of this conclusion (refer to "Speeding up without dropping points: Chinese WoBERT based on word granularity").

General Decoding

Is it easy to generalize this proof to general autoregressive models? Unfortunately, it is not. For a general autoregressive model, it is equivalent to having a different \boldsymbol{P} at each step. As long as the model’s performance is good enough, repetition decoding basically won’t occur. In fact, fully pre-trained generative models rarely exhibit repetition decoding. However, we can still observe that even general autoregressive decoding occasionally shows repetition, especially in models that haven’t been pre-trained. How can this be explained?

The previous sections were based on the bigram decoding model, concluding that bigram models are indeed prone to repetition. Perhaps we can think in reverse: does repetition in general autoregressive models occur because the model has degenerated into a bigram model at that moment? For difficult inputs, the model might fail to capture the fine-grained transition probabilities at each step, thus degenerating the transition matrix into a bigram-like state. This is possible.

How does the original paper handle this? It’s quite similar. The original paper assumes that the transition matrix of a general autoregressive model is just the bigram transition matrix \boldsymbol{P} plus a time-specific perturbation \tilde{\boldsymbol{P}}_t = \boldsymbol{P} + \boldsymbol{Q}_t. It then points out that when \boldsymbol{Q}_t is small enough, the difference from bigram decoding is small enough (which is almost a tautology), so the bigram results can represent general autoregressive models. Therefore, for general autoregressive models, we are indeed somewhat limited and can only use this idea to draw a connection.

Summary

This article is a theoretical analysis attempt of the Seq2Seq repetition decoding phenomenon. The main part focuses on deriving quantitative results for the bigram decoding model and finds that these results can explain certain phenomena and provide ideas for improvement. Finally, it "reluctantly" connects bigram decoding with general autoregressive models. The logic of this article was inspired by the paper "A Theoretical Analysis of the Repetition Problem in Text Generation", but the derivation process was developed independently. The formula definitions differ slightly from the original paper, but the overall conclusions are consistent. Readers are encouraged to discern for themselves, and corrections are welcome if there are any errors.