A Theoretical Analysis of the Repetition Problem in Text Generation

Zihao Fu, Wai Lam, Anthony Man-Cho So, Bei Shi

Abstract

Text generation tasks have seen rapid growth, yet the "repetition problem" persists across models, undermining performance. This paper proposes a theoretical framework to analyze this phenomenon. We define Average Repetition Probability (ARP) to quantify repetition and analyze Markov generation models to derive upper bounds for ARP. Our analysis reveals that repetition is largely caused by "high inflow" words—common words that many others predict with high probability. We propose Rebalanced Encoding (RE), a preprocessing method that alleviates this problem by merging high-inflow word pairs. Experimental results on NMT and LM tasks demonstrate that RE significantly reduces repetition while maintaining generation quality.

Introduction: The Repetition Loop

A common failure mode in modern AI text generators is the sudden onset of repetitive loops, such as "I like it and I like it and I..." indefinitely. While heuristic "band-aid" solutions like Top-k or Nucleus sampling exist, a fundamental theoretical understanding of why these loops occur has been missing.

Examples of repetition loops in text generation.

This research moves beyond empirical observations to provide a rigorous mathematical explanation for the repetition problem, identifying it as a structural property of language itself rather than just a model flaw.

Theoretical Framework and Methodology

The authors model text generation as a Markov process to derive mathematical bounds on the likelihood of repetition.

  1. Average Repetition Probability (ARP): A new metric introduced to quantify the probability of a model entering a repeating sequence.
  2. Markov Analysis: By simplifying generation to Markov chains, the researchers proved that repetition is driven by the variance of transition probabilities and the "high inflow" of specific tokens.
  3. Rebalanced Encoding (RE): Instead of modifying the decoding algorithm, RE addresses the problem at the encoding stage. It identifies word pairs with excessively high transition probabilities and merges them into a single token (e.g., "involved" + "in" becomes "involved==in"). This "flattens" the probability distribution, lowering the theoretical upper bound for ARP.

Key Insight: The "High Inflow" Problem

The core discovery is the "high inflow" problem. In natural language, many different words often converge on a small set of common words with high probability. These "bottleneck" words act like statistical sinks; once the model generates one, it becomes highly likely to return to a previous state, forming a loop.

The high inflow problem: many words (e.g., 'shop', 'story', 'color') predict the same subsequent word ('I') with high probability, creating a bottleneck that facilitates repetition.

This theory also explains why greedy decoding is particularly prone to repetition: it maximizes the variance of the transition matrix (setting one probability to 1 and others to 0), which causes the ARP to explode.

Experimental Results

The researchers evaluated Rebalanced Encoding (RE) on two major benchmarks: IWSLT’14 (English-German) for translation and Wiki-103 for language modeling.

  • Quantitative Performance: In NMT tasks, RE reduced word-level repetition by over 50% compared to greedy decoding while maintaining competitive BLEU scores. In LM tasks, RE achieved the lowest repetition scores among all tested methods while keeping perplexity close to human-written text.
  • Human Evaluation: Blind human tests confirmed the theoretical findings, with RE-generated text receiving higher ratings for both overall quality and repetition avoidance compared to standard Nucleus or Greedy sampling.

Conclusion

The repetition problem is a fundamental challenge rooted in the "high inflow" nature of language. By providing a theoretical framework and the ARP metric, this work allows for a more principled approach to text generation. The proposed Rebalanced Encoding method demonstrates that addressing the problem at the data representation level can be more effective than post-hoc decoding tweaks. Future work will look into extending these bounds to non-Markovian, long-range dependencies in Transformer architectures.

Summary updated

Abstract

Text generation tasks, including translation, summarization, language models, and etc. see rapid growth during recent years. Despite the remarkable achievements, the repetition problem has been observed in nearly all text generation models undermining the generation performance extensively. To solve the repetition problem, many methods have been proposed, but there is no existing theoretical analysis to show why this problem happens and how it is resolved. In this paper, we propose a new framework for theoretical analysis for the repetition problem. We first define the Average Repetition Probability (ARP) to characterize the repetition problem quantitatively. Then, we conduct an extensive analysis of the Markov generation model and derive several upper bounds of the average repetition probability with intuitive understanding. We show that most of the existing methods are essentially minimizing the upper bounds explicitly or implicitly. Grounded on our theory, we show that the repetition problem is, unfortunately, caused by the traits of our language itself. One major reason is attributed to the fact that there exist too many words predicting the same word as the subsequent word with high probability. Consequently, it is easy to go back to that word and form repetitions and we dub it as the high inflow problem. Furthermore, we derive a concentration bound of the average repetition probability for a general generation model. Finally, based on the theoretical upper bounds, we propose a novel rebalanced encoding approach to alleviate the high inflow problem. The experimental results show that our theoretical framework is applicable in general generation models and our proposed rebalanced encoding approach alleviates the repetition problem significantly. The source code of this paper can be obtained from https://github.com/fuzihaofzh/repetition-problem-nlg.
BibTeX
@inproceedings{fu2021theoretical,
  author = {Zihao Fu and Wai Lam and Anthony Man-Cho So and Bei Shi},
  title = {{A Theoretical Analysis of the Repetition Problem in Text Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17520},
}
Figure