On Union-Closedness of Language Generation

Thank you for your careful review. We are happy to see that you found the techniques clever and likely to be useful in the future. Please find our responses to your comments below.

Stringent model that demands eventual perfect generation.

While we agree that the model might initially seem stringent, there have been several surprising positive results in this model: [KM’24] showed that all countable collections are generatable, [RR’25] extended this to the “noisy” setting, and [PRR’25, KW’25] demonstrated that generation “with breadth” can be achieved in this model. Given these positive results, one might expect that finite unions of generatable classes are generatable, but our result shows that this is not the case. We believe this reveals a fundamental limitation that is relevant to the NeurIPS community, especially given the recent positive results on language generation published at NeurIPS and ICML.

[KM’24] Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Advances in Neural Information Processing Systems, Volume 37, 2024

[RR’25] Ananth Raman and Vinod Raman. Generation from noisy examples. In Forty-second International Conference on Machine Learning, 2025

[PRR’25] Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Forty-second International Conference on Machine Learning, 2025

[KW’25] Jon Kleinberg and Fan Wei. Density Measures for Language Generation. In IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS).

Whether the same pathology could occur for structured families like regular or context-free languages.

Exploring whether non-union closeness could occur for more structured families and understanding which properties of the language collections lead to closeness under unions is an interesting open question left by our work. That said, the complicated nature of the families in our lower bound is perhaps expected since the model of language generation gives generators substantial power: there are no computational restrictions and no bound on the amount of training data used by them. It is possible that once one places computational restrictions and bounds on the training data, then non-union closeness could be witnessed by simple families; and this is also an interesting open question.

Perfect-generation assumption.

Please see our response to the first question above.

Presentation … addressing these points would significantly strengthen … accessibility.

Thank you for the suggestions, we will fix the typos, referencing errors, and simplify notation in the final version.

In addition, while the authors motivate their study with the prospect of combining large language models, the perfect-generation assumption severs most practical connections, and the paper does not examine approximate or probabilistic ensemble strategies that practitioners actually use

A strength of the Kleinberg–Mullainathan model is that it places no assumptions on the generators – neither architectural nor computational. At this level of generality, theoretical results inevitably require assumptions like perfect-generation. Nevertheless, we believe our core insight that "merging" LLMs is fundamentally difficult could remain valid in practice: here, our result shows that unlike classification (where methods like XGBoost and Random Forests can divide tasks into simpler sub-problems), LLM training cannot always be decomposed this way. For instance, one might hope to train separate models on $\mathcal{L_1}$ and $\mathcal{L_2}$, then merge them to handle $\mathcal{L_1} \cup \mathcal{L_2}$ – but our result shows this approach is not feasible in general.

This, perhaps, offers a principled explanation for challenges in “merging” LLMs in practice. For instance, a recent survey [1] notes that "guaranteeing the performance of model merging remains challenging" and requires models to be "fine-tuned based on the same pre-trained model, with careful control over parameters." Even then, "there is still a significant gap between the merged and independent models.

[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao.

Thank you for the strong support of our paper. We are happy to see that you found the paper easy to read and significant. We respond to your specific comments and questions below and will include this information in the final version.

Typos.

Thank you for reading the paper carefully, we will fix all of them.

Does this apply to learning generators, e.g., training LLMs? Or does it have implications for things like ensembling pretrained LLMs at inference time?

Our view is that our result's main implication is for training LLMs: it shows that unlike classification, LLM training cannot always be divided into simpler sub-tasks where we train separate models and then combine them (as is possible with XGBoost and Random Forests in classification). For instance, to train a model for $\mathcal{L_1} \cup \mathcal{L_2}$, one might train two models in parallel – one for $\mathcal{L_1}$ and one for $\mathcal{L_2}$ – then merge them. Our result shows this approach isn't feasible in general.

Perhaps the most closely related practical instance involves challenges in "merging" LLMs. A recent survey [1] notes: "In practical settings, guaranteeing the performance of model merging remains challenging" and requires "[all models to be] fine-tuned based on the same pre-trained model, with careful control over [parameters]." Moreover, "[even after careful parameter selection] there is still a significant gap between the merged and independent models." Our results offer a principled explanation for these challenges.

[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao.

How this result shows how hard characterizing generatibility is.

Our results show that any characterization of generatability must ensure that generatability is not closed under finite unions. This prohibits one from using most of the existing characterizations/dimensions in statistical learning theory (e.g., the VC dimension, the Littlestone dimension, the recent DS dimension, and many others) or their variations because all of them ensure closure under finite unions.

Does this mean that generatability might not be…useful…because it has difficult properties? Or is it still useful…?

We believe generatability is a useful notion despite having difficult properties (e.g., not being closed under finite-unions) because:

• It arises from a simple and (arguably) natural definition (given a sequence of strings from a language, can the generator learn to generate valid and unseen strings?), and
• It turns out to have different properties than standard prediction tasks, which suggests that studying generatability could lead to new theoretical techniques that can have other applications.

The authors might include a section clarifying their views on how practically useful their results are.

Thanks for the suggestion, we will use the additional page provided in the final version to include this section; please see our response to ``Does this apply … inference time?’’ above.

Thank you for supporting our paper. We are very happy to see that you appreciated the depth and elegance of our techniques. We answer your specific questions below and hope you will strengthen your support for the paper.

While the theoretical contribution is strong…practical language generation systems (e.g., autoregressive LLMs)?

That is an excellent question. Since the Kleinberg–Mullainathan model places no restrictions on generators, our impossibility result applies to autoregressive LLMs and other language generation systems. While practical data is non-adversarial (so our results don't directly apply), LLM merging has proven challenging in practice. A recent survey [1] notes that "guaranteeing the performance of model merging remains challenging" and requires "[all models to be] fine-tuned based on the same pre-trained model, with careful control over parameters." Even then, "there is still a significant gap between the merged and independent models." Our results provide principled grounds for why merging LLMs is much more challenging than merging classifiers, where methods like XGBoost and random forests succeed and are supported by theoretical results showing classification is closed under finite unions. We will include these points in the final version.

[1] Model Merging in LLMs, MLLMs, and Beyond: Methods, Theories, Applications and Opportunities. Enneng Yang, Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, Dacheng Tao.

Would the authors consider including such a figure or pseudocode in the final version?

Thank you for the suggestion. We will add examples with figures and pseudocode illustrating how natural generators fail on the constructed union. Here's one example:

Majority-Vote Based Generator. A natural strategy for generating from $\mathcal{L}_1\cup \mathcal{L}_2$ is combining generators for $\mathcal{L}_1$ and $\mathcal{L}_2$, similar to how boosting combines weak learners in classification. This can be done in several ways. For instance, one approach is to run the generators independently and define a “scoring” function which is used as a proxy for which generator is “most successful” so far and using the output of the “most successful” generator. Since one generator makes infinitely many mistakes and the other only finitely many, one would hope that there exists a natural scoring function that will detect the one that makes finitely many mistakes. A concrete example of such a function is to count the number of (provably) correct generations a generator has made so far. Indeed, whenever a generator outputs a valid string, this string will appear at a finite time in the input stream, so we can compute such a function from data. Unfortunately, this scoring function and its natural variants failed. In fact, that result shows that no such scoring function could exist. We will include details on this (along with figures and pseudocode) in the final version.