\section{Relevant Background on Language Generation} \label{app:overview-generation} Motivated by the recent success of large language models, the study of \emph{language generation in the limit} builds on the classical theory of \emph{language identification from positive data}, initiated by \citet{gold1967language} and characterized by \citet{angluin1980inductive}. While that line of work showed that identifying an unknown language is possible only under restrictive conditions, \citet{kleinberg2024language} showed that the weaker task of eventually generating new valid strings is possible for every countable language class. This striking contrast has since sparked a growing line of follow-up work on the learning-theoretic foundations of generation \citep{li2024generation,charikar2024exploring,kalavasis2025limits,hanneke2025union}. Here, we summarize the prior work most relevant to our paper by first introducing the main definitions and then recalling the key results for each notion of generatability. \Cref{tab:gen-with-without-replay} provides a side-by-side comparison with our results. \looseness=-1 \begin{table}[H] \centering \caption{Generatability with and without replay.} \label{tab:gen-with-without-replay} {\begin{tabular}{@{}lll@{}} \toprule \textbf{Generation notion} & \textbf{Without replay} & \textbf{With replay} \\ \midrule \addlinespace[0.65em] Uniform & \Cref{thm:characterization-uniform-gen}$^\dagger$ & \Cref{thm:uniform_with_replay}$^*$ \\ \addlinespace[0.65em] Non-uniform & \Cref{thm:characterization-non-uniform-gen}$^\dagger$, \Cref{thm:lb-non-unif-mq-only}$^\dagger$ & \Cref{thm:hardness-non-unif}$^*$ \\ \addlinespace[0.65em] In the limit & \Cref{thm:mq-only-gen-in-the-lim}$^\dagger$ & \Cref{thm:limit_replay_mq_only}$^*$, \Cref{thm:separation-lim-with-replay}$^*$ \\ \addlinespace[0.65em] Proper in the limit & \Cref{thm:proper-gen-in-the-lim}$^\dagger$, \Cref{thm:lower-bound-proper}$^*$ & \Cref{thm:hardness-proper-replay}$^*$ \\ \bottomrule \end{tabular}\par} \vspace{0.35em} {\footnotesize $^\dagger$ Prior work. \quad $^*$ New in this paper. \par} \vskip -0.1in \end{table} \subsection{Definitions} Let \(\cX\) be any infinite countable domain representing the space of possible outputs, such as text, images, or molecules, and let \(\cH\subseteq\{0,1\}^\cX\) be a binary hypothesis class. Each hypothesis \(h\in\cH\) can be identified with its support \(\supp{h} \coloneqq \bc{x\in\cX\colon h(x)=1}\), which represents the set of valid outputs according to \(h\). For instance, in the context of text generation, \(\cX\) can be the set of all possible sentences, and each \(h\in\cH\) can be thought of as a language, with \(\supp{h}\) being the set of admissible sentences. \looseness=-1 The language generation game takes place over infinite rounds between an adversary and a generator. The generator is defined as follows.\looseness=-1 \begin{definition}[Generator] A \emph{generator} is a map that takes as input any finite sequence\footnote{In the replay setting, the specific \emph{order} of the inputs matters since the adversary can present previous (potentially erroneous) outputs of the generator. For instance, let \(x_2 = \cG(x_1)\); the example sequences \(\br{x_1, x_2}\) and \(\br{x_2, x_1}\) may in principle contain different information in the replay setting.} $x_{1:t} \coloneqq (x_1, \ldots, x_t) \in \cX^t$ of any length $t \in \bN$ and outputs an element $o_t \in \cX$. \end{definition} We first give an informal description of the game, which will be made formal in the definitions that follow. At the beginning of the game, the adversary chooses a target hypothesis \(h^\star\in\cH\) and a sequence of examples \(x_1,x_2,\ldots\) such that \(\bc{x_1,x_2,\ldots}\subseteq\supp{h^\star}\). At each round \(t\), the generator receives the prefix \(x_{1:t}\) and produces an output \(o_t\). The goal of the generator is to eventually produce an output that is \emph{valid}, meaning that it belongs to \(\supp{h^\star}\), and \emph{novel}, meaning that it is not among the examples \(x_1,\ldots,x_t\) seen so far. For this to be possible, the target hypothesis \(h^\star\) must have infinite support, and hence we will only consider classes \(\cH\) that satisfy the following property. \begin{definition}[Uniformly unbounded support, UUS] \label{def:uus} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfies the \emph{uniformly unbounded support (UUS)} property if \(\left|\supp{h} \right| = \infty\) for all \(h \in \cH\). \end{definition} We can now formally introduce the three main notions of generatability: \emph{uniform}, \emph{non-uniform}, and \emph{in the limit}. As illustrated by~\Cref{tab:notions}, these notions differ on the restrictions placed on the success time~\(t^\star\) after which the generator must produce valid and novel outputs. We begin with the strongest notion, uniform generatability, where \(t^\star\) is allowed to depend only on the hypothesis class \(\cH\), and therefore must hold uniformly over all hypotheses and example sequences. \looseness=-1 \begin{definition}[Uniform generatability, \citealt{kleinberg2024language,li2024generation}] \label{def:uniform-gen} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is \emph{uniformly generatable} if there exist a generator \(\cG\) and \(d^\star\in\bN\) such that, for every \(h\in\cH\) and any sequence \(x_1,x_2,\ldots\) with \(\bc{x_1,x_2,\ldots} \subseteq \supp{h}\), if there exists \(t^\star\in\bN\) with \(\abs{\bc{x_1,\dots,x_{t^\star}}}=d^\star\), then \(\cG\br{x_{1:s}}\in\supp{h}\setminus\bc{x_1,\dots,x_s}\) for all \(s\ge t^\star\). \end{definition} \noindent For a given generator \(\cG\), its \emph{uniform generation sample complexity} \(d^\star_\cG\) is defined as the smallest such \(d^\star\), or \(\infty\) if no such value exists. Non-uniform generatability relaxes the uniformity requirement by allowing \(t^\star\) to depend on the target hypothesis, but not on the example sequence. \looseness=-1 \begin{definition}[Non-uniform generatability, \citealt{li2024generation}] \label{def:non-uniform-gen} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is \emph{non-uniformly generatable} 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 \(x_1,x_2,\ldots\) with \(\bc{x_1,x_2,\ldots} \subseteq \supp{h}\), if there exists \(t^\star\in\bN\) with \(\abs{\bc{x_1,\dots,x_{t^\star}}}=d^\star_h\), then \(\cG\br{x_{1:s}}\in\supp{h}\setminus\bc{x_1,\dots,x_s}\) for all \(s\ge t^\star\). \end{definition} \noindent For a given generator \(\cG\) and for any hypothesis \(h\in\cH\), the \emph{non-uniform generation sample complexity} \(d^\star_{\cG,h}\) is defined as the smallest such \(d^\star_h\), or \(\infty\) if no such value exists. Finally, generatability in the limit is the weakest notion, where \(t^\star\) is allowed to depend on the target hypothesis and on the example sequence. \looseness=-1 \begin{definition}[Generatability in the limit, \citealt{kleinberg2024language}] \label{def:gen-in-the-lim} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is \emph{generatable in the limit} if there exists a generator \(\cG\) such that, for every \(h\in\cH\) and any \emph{enumeration}\footnote{An infinite sequence \(\br{x_t}_{t\ge 1}\) is an enumeration of \(\supp{h}\) if for every \(x\in\supp{h}\) there exists \(t\in\bN\) such that \(x_t=x\).} \(\br{x_t}_{t\ge 1}\) of \(\supp{h}\), there exists \(t^\star\in\bN\) such that \(\cG\br{x_{1:s}}\in\supp{h}\setminus\bc{x_1,\dots,x_s}\) for all \(s\ge t^\star\). \end{definition} \noindent For any class $\cH$, uniformly generatable $\implies$ non-uniformly generatable $\implies$ generatable in the limit.\looseness=-1 \begin{table}[H] \centering \caption{What is the success time $t^\star$ allowed to depend on?} \label{tab:notions} {\begin{tabular}{@{}lccc@{}} \toprule \textbf{Generation notion} & \textbf{Class} \(\cH\) & \textbf{Hypothesis} \(h^\star\) & \textbf{Sequence} \(\br{x_t}_{t\geq 1}\)\\ \midrule Uniform & Yes & No & No\\ \addlinespace[0.4em] Non-uniform & Yes & Yes & No \\ \addlinespace[0.4em] In the limit & Yes & Yes & Yes\\ \bottomrule \end{tabular} \par} \end{table} Next, we describe the \emph{proper} setting of generation, where, borrowing from the PAC learning vocabulary~\citep{shalev2014understanding}, the algorithm is required to output a hypothesis \(\hat{h}_t\in\cH\) at each round \(t\). In the terminology of the language generation literature~\citep{kleinberg2025density,mehrotra2025language}, \emph{proper} generation corresponds to \emph{index-based} generation (at least for countable classes), while \emph{improper} generation corresponds to \emph{element-based} generation, though in this work we will often simply refer to the latter as \emph{generation}. \looseness=-1 \begin{definition}[Proper generator, \citealt{kleinberg2025density}] \label{def:proper-generator} A \emph{proper generator} is a map that takes as input any finite sequence \(x_{1:t} \coloneqq (x_1, \ldots, x_t) \in \mathcal{X}^t\) of any length \(t \in \mathbb{N}\) and outputs a hypothesis \(\hat{h}_t \in \cH\). \end{definition} \begin{definition}[Proper generatability in the limit, \citealt{kleinberg2025density}] \label{def:proper-gen-in-the-lim} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is \emph{properly generatable in the limit} if there exists a proper generator \(\cG\) such that, for all \(h \in \cH\) and for any enumeration \((x_t)_{t \ge 1}\) of \(\supp{h}\), there exists \(t^\star \in \mathbb{N}\) such that \(\supp{\hat{h}_s} \subseteq \supp{h}\) for all \(s \geq t^\star\). \end{definition} \noindent Clearly, for any class $\cH$, proper generatability $\implies$ (improper) generatability. \subsection{Results} We now recall the standard guarantees against which our replay results will be compared, as illustrated by~\Cref{tab:gen-with-without-replay}. We begin by recalling a combinatorial dimension that, for generatability, plays a role analogous to the VC dimension in PAC learning~\citep{vapnik2015uniform} and the Littlestone dimension in online learning~\citep{littlestone1988learning}. \begin{definition}[Closure dimension, \citealt{li2024generation}] \label{def:closure-dim} The \emph{Closure dimension} of a binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\), denoted by \(\cC(\cH)\), is the largest \(d\in\bN\) for which there exist distinct \(x_1, \ldots, x_d \in \cX\) such that there exists \(h\in\cH\) with \(\bc{x_1,\ldots,x_d}\subseteq \supp{h}\) and \[\abs{\bigcap_{h\in\cH\br{x_{1:d}}} \supp{h}} < \infty,\] where \(\cH\br{x_{1:d}} \coloneqq \bc{h\in\cH\colon \bc{x_1,\ldots,x_d}\subseteq \supp{h}}\) denotes the version space. If this holds for any \(d\in\bN\), we say that \(\cC(\cH)=\infty\); if it fails for \(d=1\), we say that \(\cC(\cH)=0\). \end{definition} \begin{theorem}[Characterization of uniform generatability, \citealt{li2024generation}] \label{thm:characterization-uniform-gen} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is uniformly generatable if and only if \(\cC\br{\cH}<\infty\). \end{theorem} \noindent This leads to the following corollary for finite classes, which was first proved by \citet{kleinberg2024language}. \begin{corollary} \label{cor:unif-finite} All finite hypothesis classes are uniformly generatable. \end{corollary} The Closure dimension can also be used to characterize non-uniformly generatable classes, in a way that is reminiscent of how the VC dimension relates to non-uniform PAC learnability. \begin{theorem}[Characterization of non-uniform generatability, \citealt{li2024generation}] \label{thm:characterization-non-uniform-gen} A binary hypothesis class \(\cH \subseteq \{0,1\}^\cX\) satisfying the UUS property is non-uniformly generatable if and only if there exists a non-decreasing sequence of classes \(\cH_1\subseteq\cH_2,\ldots\) such that \(\cH = \bigcup_{i=1}^\infty\cH_i\) and \(\cC\br{\cH_i}<\infty\) for every \(i\in\bN\). \end{theorem} \noindent This immediately yields the following corollary for countable classes. \begin{corollary} \label{cor:non-unif-countable} All countable hypothesis classes are non-uniformly generatable. \end{corollary} \noindent However, although all countable classes are non-uniformly generatable, there is an insurmountable computational barrier. \begin{theorem} [Non-uniform generation requires more than just membership queries, \citealt{charikar2024exploring}] \label{thm:lb-non-unif-mq-only} A (deterministic) algorithm that non-uniformly generates all countable classes cannot be implemented using membership queries alone. \end{theorem} The situation changes under generatability in the limit, where the following positive result holds for countable classes. \begin{theorem}[All countable classes are generatable in the limit using only membership queries, \citealt{kleinberg2024language}] \label{thm:mq-only-gen-in-the-lim} There exists a generator that generates all countable classes in the limit using only membership queries. \end{theorem} Finally, in the \emph{proper} setting, augmenting the same algorithm with subset queries yields the following result. \begin{theorem}[All countable classes are properly generatable in the limit, \citealt{kleinberg2024language}] \label{thm:proper-gen-in-the-lim} There exists a proper generator that properly generates all countable classes in the limit using membership queries and subset queries. \end{theorem}