\section{Setup and Results}
\label{sec:setup}

This section introduces the \emph{language generation with replay} framework, formalizes the key notions of \emph{generatability with replay}, and informally states our main results for each such notion. \looseness=-1

\subsection{Problem Setup}
\label{subsec:setup}

Let \(\cX\) be a countable domain and let \(\cH \subseteq
\{0,1\}^{\cX}\) be a binary hypothesis class. For \(h\in\cH\), write
\(\supp{h}\coloneqq \{x\in\cX : h(x)=1\}\). As a concrete instantiation, 
the domain \(\cX\) may be taken to be the set of all tokens, or of all finite strings over
a finite alphabet, with each hypothesis \(h\) representing the language
consisting of the strings in \(\supp{h}\). Throughout, we assume
\(\supp{h}\) is infinite for every \(h\in\cH\), since the goal is to
output infinitely many distinct valid elements. This is often called
the \textit{uniformly unbounded support}~(UUS) property~\citep{li2024generation}. \looseness=-1

Our starting point is the language generation game introduced by \citet{kleinberg2024language}.
The game proceeds over infinitely many rounds between an adversary and a (possibly computationally unbounded) \emph{generator}, defined as a function \(\cG\) that maps each finite sequence \(x_{1:t} \coloneqq \br{x_1,\ldots,x_t} \in \cX^t\) to an output \(o_t \coloneqq \cG(x_{1:t}) \in \cX\).
At the start of the game, the adversary fixes a hidden
target \(h^\star\in\cH\). In each round \(t\), the adversary reveals an example
\(x_t\in\supp{h^\star}\), and the generator outputs \(o_t=\cG(x_{1:t})\). The
generator \emph{succeeds} if there exists a time \(t^\star \in \bN\) such that
for all \(t\ge t^\star\),
\(
o_t \in \supp{h^\star}\setminus\bc{x_1,\dots,x_t}
\).
That is, the generator must eventually only output elements that are both \emph{valid} and \emph{novel}.
No restriction is imposed on outputs before \(t^\star\).\looseness=-1

Different notions of generatability arise by varying what the success time \(t^\star\) is allowed to depend upon.
Under \emph{uniform} generatability~\citep{kleinberg2024language}, \(t^\star\) must be fixed across all \(h \in \cH\); under \emph{non-uniform} generatability~\citep{li2024generation}, it may depend on the particular target hypothesis \(h^\star\); and under generatability \emph{in the limit}~\citep{kleinberg2024language}, it may further depend on the specific sequence \(\br{x_t}_{t \geq 1}\).
For reference, relevant definitions and results from the standard setting are summarized in Appendix~\ref{app:overview-generation}; in particular, \Cref{tab:notions} contrasts the above three notions of generatability.

In this work, we introduce a minimal modification to the standard language generation game to capture the recursive feedback dynamics at the core of model collapse.
While in the standard setting the adversary must reveal \(x_t\in\supp{h^\star}\) in every round, in our replay setting the adversary may also reveal previous generator outputs, potentially including invalid/hallucinated ones.
We refer to this variant of the standard language generation game as \emph{language generation with replay}. \looseness=-1

\gamebox{Language Generation with Replay}{%
\setlength{\baselineskip}{15pt}%
\textbf{Setup.} Hypothesis class $\cH\subseteq\bc{0,1}^{\cX}$ satisfying the UUS property.\\
\textbf{Game.} The adversary secretly picks $h^\star\in\cH$.\\
For $t=1,2,\dots$
\begin{enumerate}[label=(\roman*), nosep]
    \item The adversary reveals an example \(x_t\) such that \(x_t\in\supp{h^\star} \cup \bc{o_s\colon s<t}\).
    \item The generator outputs $o_t\in\cX$.
\end{enumerate}
\textbf{Success.} There exists a finite time \(t^\star \in \bN\) such that \(o_t\in\supp{h^\star}\setminus\bc{x_1,\dots,x_t}\) for all \(t\ge t^\star\).%
}


\subsection{Main Definitions and Results}
\label{subsec:main-results}

The following definition formalizes the notion of adversarial sequences of examples \emph{with replay} and forms the basis for subsequent notions of generation with replay.

\begin{definition}[Sequence with replay for a hypothesis and a generator]
\label{def:replay-seq}
Fix a hypothesis \(h\) and a generator \(\cG\). An infinite sequence
\(\br{x_t}_{t\ge1}\) is a \emph{replay sequence for \(h\) and \(\cG\)}
if, for every \(t\ge1\),
\[
x_t \in \supp{h}\quad \text{or}\quad x_t \in \bc{ \cG\br{x_{1:s}} : s<t}.
\]
\end{definition} 

\subsubsection{Uniform Generation with Replay}
We begin with the
most restrictive setting, where the generator must succeed after
seeing a fixed number of samples \(d^\star\), independent of the
target \(h\).

\begin{definition}[Uniform generatability with replay]
\label{def:unif-gen-replay}
A class \(\cH\) is \emph{uniformly generatable with replay} if there
exist a generator \(\cG\) and \(d^\star\in\bN\) such that for every
\(h\in\cH\) and every replay sequence \(\br{x_t}_{t\ge1}\) for \(h\)
and \(\cG\), if there exists \(t\) with
\(\abs{\bc{x_1,\dots,x_t}}=d^\star\), then
\(\cG\br{x_{1:s}}\in\supp{h}\setminus\bc{x_1,\dots,x_s}\) for all \(s\ge
t\).
\end{definition}
\noindent Given a generator \(\cG\), we define its \emph{uniform generation with
replay sample complexity} \(d^\star_\cG\) as the smallest such
\(d^\star\), or \(\infty\) if no such value exists.
\contribbox{Contribution 1.}{
  In \Cref{thm:uniform_with_replay}, we prove that \(\cH\) is uniformly generatable with replay if and only if it is uniformly generatable in the standard setting. Moreover, the sample complexity \(d^\star\) remains unchanged.
}

\noindent Our proof proceeds by a black-box reduction from a uniform generator in the standard setting to one in the replay setting, showing how to make uniform generators sufficiently robust to absorb the noise introduced by replay.

\subsubsection{Non-Uniform Generation with Replay}
In this notion of generatability, the sample complexity \(d^\star_h\) is allowed to depend on the target \(h\) but not on the specific sequence of examples \(\br{x_t}_{t\geq 1}\).

\begin{definition}[Non-uniform generatability with replay]
\label{def:non-unif-replay-double} 
    A class \(\cH\) is \emph{non-uniformly
    generatable with replay} if there exists a generator \(\cG\) such
    that for every \(h \in \cH\) there exists \(d^\star_h \in \bN\)
    such that, for any sequence with replay \(\br{x_t}_{t \geq 1}\)
    for \(h\) and \(\cG\), if there exists \(t^\star_h \in \bN\) such
    that \(\abs{\bc{x_1, \dots, x_{t^\star_h}}} = d^\star_h\),
    then \(\cG(x_{1:s}) \in \supp h \setminus \bc{x_1,\ldots,x_s}\) for all \(s \geq t^\star_h\).
\end{definition}

\contribbox{Contribution 2.}{%
In \Cref{thm:hardness-non-unif}, we construct a
  \emph{countable} hypothesis class that is non-uniformly generatable
  in the standard setting but is \emph{not} non-uniformly
  generatable with replay.}

\noindent In the standard setting, every countable
class is non-uniformly generatable~\citep{li2024generation,charikar2024exploring}. Thus, our result creates a strong
separation in the non-uniform generation setting.

\subsubsection{Generation in the Limit with Replay}
This setting
requires success only on example streams that eventually enumerate the entire
support of the target hypothesis~(possibly interleaved with replay examples), with no
pre-computed bound on the sample complexity.

\begin{definition} [Generatability in the limit with replay]
    An infinite replay sequence \(\br{x_t}_{t\geq 1}\) is an \emph{enumeration
    with replay} if it eventually reveals every \(x \in \supp{h}\).\footnote{
      That is, for every $x\in\supp{h}$ there exists a finite $t\in\bN$ such that $x_t=x$.
    }
    A class \(\cH\) is \emph{generatable in the limit with replay} if
    there exists a generator \(\cG\) such that, for every \(h \in
    \cH\) and every enumeration with replay \(\br{x_t}_{t\geq 1}\), there exists
    \(t^\star\in\bN\) such that \(\cG(x_{1:s}) \in \supp h \setminus
    \bc{x_1,\ldots,x_s}\) for all \(s \geq t^\star\).
\end{definition}

\noindent Crucially, to meet the requirement of enumerating the full support of \(h^\star\), the adversary can reveal an instance \emph{after} it has been output by the generator.
This increases the hardness of generation, as the generator must carefully select its outputs, knowing that replayed instances cannot be trusted.

\contribbox{Contribution 3.1.}{%
In \Cref{thm:separation-lim-with-replay}, we prove that there exists
an (uncountable) class \(\cH\) that is generatable in the limit
without replay but is \emph{not} generatable in the limit with replay.}

This separation shows that the replay model can fundamentally limit the power of generation over general hypothesis classes.
This naturally raises the question of whether a similar separation holds for \emph{countable} classes.
For this specific case, we provide a positive result.

\contribbox{Contribution 3.2.}{%
  In~\Cref{thm:limit_replay_mq_only}, we provide an algorithm that generates in the limit under replay any countable class using only membership queries.
} 

\noindent By \emph{membership queries} we mean oracle access to the predicate ``\(x\in\supp{h}\)'' for any \(h\in\cH\) and any \(x\in\cX\).\footnote{
  Equivalently, we assume that \(h(x)\) is computable for all \(h\in\cH\) and \(x\in\cX\).
}
We note that this access model is, in a sense, minimal, as any reasonable generator should at least be able to evaluate whether any given \(h\in\cH\) is consistent with the example stream.
\citet{kleinberg2024language} showed that, in the standard setting, every countable class is generatable in the limit using only membership queries. 
Thus, our result shows that, for countable classes, generation in the limit remains equally possible under replay using the same access model.

\subsubsection{Proper Generation with and without Replay}
Finally, we study \emph{proper} generation, where at each round the generator must output a hypothesis \(\hat h_t \in \cH\), rather than an element \(o_t\in\cX\), and the success criterion requires \[\supp{\hat h_t}\subseteq\supp{h^\star}\] for all sufficiently large \(t\). 
We refer to the setting where the generator outputs elements of $\cX$ simply as \emph{generation}, and occasionally as \emph{improper} generation when a contrast with the proper setting is needed.\footnote{
  In the literature, \emph{improper} and \emph{proper} generation are also referred to as \emph{element-based} and \emph{index-based} generation, respectively~\citep{kleinberg2025density}.
  The term \emph{index-based}, however, presumes that \(\cH\) is countable and thus admits an indexing.
}

The replay adversary may now reveal \emph{any} element from the support of any previously output hypothesis.
This formalizes unconstrained downstream reuse of deployed generative models, where each \(\hat{h}_t\) represents a specific version of a model previously deployed and accessible to downstream users for content generation.\looseness=-1

\begin{definition}[Proper generatability in the limit with replay]
\label{def:proper-limit-replay}
A class \(\cH\) is \emph{properly generatable in the limit with replay} if there exists a proper generator \(\cG\) such that, for every \(h\in\cH\) and every sequence \(\br{x_t}_{t\ge1}\) satisfying 
\begin{enumerate}[nosep]
  \item \(x_t\in\supp{h}\) or \(x_t\in\supp{\hat h_s}\) for some \(s<t\), and
  \item \(\br{x_t}_{t\ge1}\) enumerates every element of \(\supp{h}\), 
\end{enumerate}
there exists \(t^\star\) such that \(\supp{\hat h_t}\subseteq\supp{h}\)  for all \(t\ge t^\star\).\looseness=-1
\end{definition}

\contribbox{Contribution 4.1.}{%
In \Cref{thm:hardness-proper-replay}, we show that there exists a
\emph{finite} class \(\cH\) that is properly generatable in the limit
in the standard setting, but \emph{not} in the replay setting.\looseness=-1
}

\noindent\Cref{tab:replay-separation-classes} summarizes the results described so far, highlighting whether replay affects the guarantees of the standard setting for each notion of generatability.

We also show that, even without replay, proper generation in the limit
can be strictly harder than improper generation in a computational sense.

\contribbox{Contribution 4.2.}{%
In~\Cref{thm:lower-bound-proper}, we show that proper generation in the
limit may require stronger computational primitives than membership
queries alone.\looseness=-1
}

\noindent \citet{kleinberg2024language} showed that, in the standard setting, all countable classes are properly generatable in the limit using membership queries and subset queries.\footnote{By \emph{subset queries} we mean queries of the kind ``\(\supp{h_i} \subseteq \supp{h_j}\)?'' for any \(h_i, h_j \in \cH\).}
\Cref{thm:lower-bound-proper}~establishes a computational lower bound for the algorithm of~\citet{kleinberg2024language}, showing that access to some additional computational primitive (such as subset queries) is necessary in general.
This result is of independent interest beyond generation with replay.