A Theoretical Analysis of the Repetition Problem in Text Generation

1 Introduction

• Repetition affects nearly all generation systems and undermines quality, yet its cause remains unknown and lacks a quantitative theoretical explanation.Prior conjectures and successful decoding methods have not supplied a convincing explanation.Source: §1 · p. 1
• The paper defines ARP and analyzes a Markov generation model to derive upper bounds, showing that most existing methods explicitly or implicitly minimize them.Source: §1 · pp. 1–2
• The analysis attributes repetition partly to high inflow: many words predict the same next word, making it easy to return to that word and repeat.It also derives a concentration bound extending the ARP analysis to general generation models.Source: §1 · p. 2
• Rebalanced encoding merges high-inflow pairs to reduce high-inflow probability; experiments on NMT and LM report significantly less repetition and better performance than prevalent out-of-the-box methods.Experiments also test the theory’s applicability to NMT and LM.Source: §1 · p. 2

2.1 Definitions

• The general generation model conditions each word on the full history and input, while the Markov model simplifies prediction to the immediately previous word.A loop starts and ends with the same word; a repetition subsequence repeats a continuous segment, and a sequence has one if it contains adjacent identical loops.Source: §2.1 · p. 2
• ARP is defined for a Markov generation model and provides a quantitative measure of repetition, with higher values corresponding to more frequent repetition.The definition uses the model's sub-transition matrix and non-zero probability.Source: §2.1 · p. 3

2.2 Average Repetition Probability Upper Bounds

• The bounds relate lower ARP to lower transition-probability variance and larger EOS-transition mass, while Top-k/Nucleus truncation alone can increase variance and worsen repetition.At fixed temperature, Top-k/Nucleus sampling can make repetition worse; the paper frames truncation as addressing the long-tail problem when paired with stochastic or temperature sampling.Source: §2.2 · p. 4
• High inflow, rather than word frequency itself, is identified as magnifying the ARP upper bound and motivating rebalanced encoding to reduce high-inflow words.The paper distinguishes words that often occur from words that receive high probability mass from many preceding words.Source: §2.2 · p. 4

2.3 Extension to General Generation Model

• When each step's transition matrix does not deviate much from the Markov model's, the deviation of ARP is bounded with high probability.The theorem's bound depends on the perturbations' mean and variance, regardless of their specific value constraint.Source: §2.3 · p. 4

3 Rebalanced Encoding

• RE merges high-inflow pairs into single words, reducing both the inflow term and the variance of transition matrix B.Theoretical upper bounds decrease as either quantity decreases.Source: §3 · p. 4
• Unlike methods that post-edit probability distributions, RE changes the encoding so the model can predict a good distribution directly.Source: §3 · p. 4
• RE first applies BPE, then repeatedly merges word pairs whose transition probability exceeds threshold γ and rebuilds the transition matrix.Pairs split by BPE are joined without BPE tags; other pairs are joined with a “==” tag.Source: §3 · p. 5

4.1 Experimental Settings

• The NMT experiments use IWSLT’14 English-German with 160K sentence pairs, 10,000 subword units per language, and BLEU and ROUGEL for translation performance.Repetition is also evaluated with rep-w, rep-n, and rep-r.Source: §4.1 · p. 5
• The language-modeling experiments use Wiki-103 and a Transformer decoder, with ppl-c used to compare perplexity across encoding approaches.Models are tuned toward ppl-c 1.0, and repetition is measured with rep-w, rep-n, and rep-r.Source: §4.1 · pp. 5–6

4.2 Experimental Results

• RE alleviates repetition and significantly outperforms existing methods in NMT and language modeling.The NMT results are in Table 1 and the language-modeling results in Table 2.Source: Table 1 · p. 5, Table 2 · p. 5, §4.2 · p. 6
• Human helpers rated RE above comparison methods for both repetition reduction and overall performance.The evaluation sampled 120 language-model outputs per model.Source: §4.2 · p. 6, Table 3 · p. 6
• RE controls inflow while length penalty controls outflow; both methods alleviate repetition by limiting the ARP upper bound.The reported performance metrics may worsen slightly as repetition falls, and the authors note their limited sensitivity to repetition.Source: §4.2 · p. 6
• At matched performance scores, RE has the lowest repetition scores in both NMT and language modeling.The experiments varied temperature to compare repetition at different BLEU or ppl-c levels.Source: §4.2 · pp. 6–7, Figure 3 · p. 6
• As ARP increases, all evaluated repetition metrics increase, supporting ARP as a well-defined measure.This relationship was tested on a Markov model whose transition matrix was estimated from Wiki-103.Source: Figure 4 · p. 6, §4.2 · p. 7
• Sentences with more high-inflow pairs are more likely to have higher repetition scores.The relationship was examined in the NMT task.Source: Figure 5 · p. 6, §4.2 · p. 7

5 Related Works

• Sequence-to-sequence systems are used for translation, summarization, and data-to-text generation, while language models serve open-ended generation.The section names GPT as an example of language-model-based systems (Radford et al. 2018, 2019; Brown et al. 2020).Source: §5 · p. 7
• Empirical out-of-the-box methods address repetition by replacing greedy sampling with alternative sampling methods.The passage cites (Ott et al. 2019).Source: §5 · p. 7
• Unlikelihood training is presented as an approach that adds new components to address the limitations of likelihood training.The passage attributes this approach to Welleck et al. (2020).Source: §5 · p. 7

6 Conclusions

• The paper concludes that many high-inflow words make it easier to return to the same words and increase repetition probability.This is presented as a language-level cause of the repetition problem.Source: §6 · p. 7
• The authors interpret most existing methods as explicitly or implicitly minimizing ARP upper bounds.Source: §6 · p. 7
• Rebalanced encoding reduces high-inflow terms, and the experiments support its effectiveness against repetition.Source: §6 · p. 7

A.1 Proof of Theorem 1

• σn is defined as the smallest singular value.Source: §A.1 · p. 10
• The passage defines ρ(·) as the spectral radius and I as the identity matrix.Source: §A.1 · p. 10
• The displayed expression includes the nuclear norm of B2.Source: §A.1 · p. 10

• n is the mean of each row of B.Source: §A.2 · p. 10
• The Frobenius norm is submultiplicative, and b_i denotes the ith element of b.Source: §A.2 · p. 10

• The proof begins with Johnson’s lemma, which gives a lower bound on the smallest singular value of an n-by-n matrix.Source: §A.3 · p. 10
• For sub-stochastic B, the excerpt states that ζ_nI − B² has positive diagonal entries and negative off-diagonal entries.Source: §A.3 · p. 10

A.4 Proof of Theorem 2

• Lemma 2 assumes independently drawn T_p,T_q from Definition 2.4’s same distribution and sub-stochastic B with sum_{i=1}^n B_ij^2 < 1; later passages invoke Lemma 2 and Chebyshev’s inequality.Theorem 2’s fragment includes ζ_n > 4 and quantifies over every constant a > 0, but does not supply its full statement.Source: §A.4 · p. 11

A.5 Human Evaluation Questionnaire

• The human questionnaire asks raters to score sentence quality and repetition on a 1–5 scale.Quality is rated from incoherent to coherent; repetition is rated from always repeating to never repeating.Source: §A.5 · p. 11

A.6 Hyper-Parameters Tunning

• NMT model selection uses BLEU among models with lower repetition scores than greedy sampling; the proposed RE method needs no temperature tuning.Other sampling temperatures are grid-searched on the validation set.Source: §A.6 · pp. 11–12
• For language modeling, models are selected by ppl-c closeness to 1.0, with sampling temperatures, β, and RE settings tuned.The passage states that human-written language has ppl-c of 1.0.Source: §A.6 · p. 12