\documentclass[11pt,letterpaper]{article}

\usepackage[margin=1.2in]{geometry}
\usepackage[skip=6pt]{parskip}

\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{booktabs}
\usepackage{xcolor}

\definecolor{paperblue}{rgb}{0,0.10,0.45}
\usepackage[
    colorlinks=true,
    linkcolor=paperblue,
    citecolor=paperblue,
    urlcolor=paperblue
]{hyperref}

\newcommand{\theHalgorithm}{\arabic{algorithm}}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}

\usepackage[capitalize,noabbrev]{cleveref}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\Crefname{definition}{Definition}{Definitions}

\newtheorem{claim}{Claim}
\newtheorem{condition}{Condition}
\newtheorem*{definition*}{Definition} 

\usepackage{thm-restate}
\usepackage{enumitem}
\usepackage{tabularx}
\usepackage{tikz}

\input{macros}

\RequirePackage{algorithm}
\RequirePackage{algpseudocodex}
\RequirePackage{natbib}
\RequirePackage{eso-pic}
\RequirePackage{forloop}
\RequirePackage{url}
\RequirePackage{caption}


\title{Language Generation with Replay:\\A Learning-Theoretic View of Model Collapse}
\author{
    Giorgio Racca\\
    University of Copenhagen\\
    \texttt{g.racca@di.ku.dk}
    \and
    Michal Valko\\
    Isara Labs\\
    \texttt{michal@isara.io}
    \and
    Amartya Sanyal\\
    University of Copenhagen\\
    \texttt{amsa@di.ku.dk}
}
\date{}


\begin{document}
\maketitle

\begin{abstract}
As scaling laws push the training of frontier large language models (LLMs) toward ever-growing data requirements, training pipelines are approaching a regime where much of the publicly available online text may be consumed.
At the same time, widespread LLM usage increases the volume of machine-generated content on the web; together, these trends raise the likelihood of generated text re-entering future training corpora, increasing the associated risk of performance degradation often called \emph{model collapse}.
In practice, model developers address this concern through data cleaning, watermarking, synthetic-data policies, or, in some cases, blissful ignorance. %
However, the problem of model collapse in generative models has not been examined from a learning-theoretic perspective: we study it through the theoretical lens of the \emph{language generation in the limit} framework, introducing a \emph{replay} adversary that augments the example stream with the generator's own past outputs.
Our main contribution is a fine-grained learning-theoretic characterization of when replay fundamentally limits generation: while replay is benign for the strongest notion of uniform generation, it provably creates separations for the weaker notions of non-uniform generation and generation in the limit.
Interestingly, our positive results mirror heuristics widely used in practice, such as data cleaning, watermarking, and output filtering, while our separations show when these ideas can fail.%
\end{abstract}

\input{sections/01-intro}
\input{sections/02-related-work.tex}
\input{sections/03-setup-results}
\input{sections/04-uniform-with-replay}
\input{sections/05-non-uniform-with-replay}
\input{sections/06-in-the-limit-with-replay}
\input{sections/07-proper}
\input{sections/08-discussion}

\section*{Acknowledgements}
GR and AS acknowledge the Novo Nordisk Foundation for support via the Startup grant (NNF\allowbreak24OC0087820); AS additionally acknowledges support from VILLUM FONDEN via the Young Investigator program (VIL72069).
The authors also thank Carolin Heinzler for helpful feedback, as well as the anonymous reviewers for their constructive comments.

\begingroup
\setlength{\bibsep}{5.85pt plus 0.3pt}
\bibliographystyle{plainnat}
\bibliography{ref}
\endgroup

\newpage
\appendix
\onecolumn

\input{appendix/A-overview-generation}

\end{document}