💬 NLP

Language Generation: Complexity Barriers and Implications for Learning

This paper demonstrates that while language generation is theoretically possible in the limit for various formal language classes, it is computationally infeasible due to prohibitive sample complexity requirements, even for relatively simple classes like regular and context-free languages.

Original authors: Marcelo Arenas, Pablo Barceló, Luis Cofré, Alexander Kozachinskiy

Published 2026-01-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Marcelo Arenas, Pablo Barceló, Luis Cofré, Alexander Kozachinskiy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Can You Learn to "Fake It" Forever?

Imagine you are trying to learn a secret code by watching someone else use it. You see a stream of messages (positive examples) and you want to eventually start sending your own messages that look exactly like the real ones, even if you've never seen those specific messages before.

In the world of computer science, researchers Kleinberg and Mullainathan previously proved that yes, this is always possible in theory. If you have enough time and enough examples, you can eventually learn to generate perfect fake data for any language, no matter how complex.

But this paper asks a different question: Just because you can do it in theory, does it mean you can do it in practice? How many examples do you actually need before you can start faking it successfully?

The authors (Arenas, Barceló, Cofrė, and Kozachinskiy) say: "For many common types of languages, the answer is 'too many to count' or 'impossible to calculate.' It is theoretically possible, but computationally impossible."

The Analogy: The "Secret Club" Game

To understand their findings, imagine a game with several Secret Clubs. Each club has a specific rule for who can join (the "language"). You are a detective trying to figure out the rules of a specific club just by watching who is currently inside.

Your goal isn't to guess the rule perfectly; your goal is to generate a new member that the club would accept, even if you haven't seen that specific person before.

The paper tests four different types of clubs to see how many people you need to watch before you can successfully generate a new member.

1. The "Context-Free" Clubs (The Complex Rules)

What they are: These are like clubs with nested, complex rules (e.g., "For every 'if' there must be a 'then'"). They are very common in computer programming.
The Finding: The authors found that for some of these clubs, there is no number you can write down that guarantees you'll succeed.
The Metaphor: Imagine trying to guess the password to a safe. The paper proves that for certain complex clubs, the number of people you need to watch before you can guess a new valid member is so huge that no computer can even calculate the number. It's like asking, "How many grains of sand are in the universe?" but the answer changes depending on a puzzle that might never be solved.
Result: Impossible to compute.

2. The "Regular" Clubs (The Simple Rules)

What they are: These are clubs with simpler, repetitive rules (e.g., "You must have an even number of red shirts"). These are the foundation of basic computer logic.
The Finding: Here, a number does exist, but it is astronomically large.
The Metaphor: Imagine you need to fill a swimming pool with water. For these clubs, the number of examples you need is like filling the pool with water, then filling the pool with water again, and then doing that process over and over again until the water reaches the moon.
Result: Double-Exponential. The number of examples needed grows so fast that even for a small group of clubs, you would need more examples than there are atoms in the universe. It's theoretically possible, but practically useless.

3. The "LTT" Clubs (The Local Rules)

What they are: These are a special, stricter type of "Regular" club. They only care about what happens in the immediate neighborhood of a word (e.g., "You can't have two 'A's next to each other").
The Finding: This is a "better" club, but the problem is still huge.
The Metaphor: If the "Regular" clubs required a pool of water reaching the moon, these "LTT" clubs only require a pool reaching the top of Mount Everest. It's a massive improvement, but Mount Everest is still too high to climb if you are trying to do it in a single day.
Result: Single-Exponential. Still too big to be practical.

4. The "Pattern" Clubs (The Shape-Shifting Rules)

What they are: These clubs use variables (like "X") that must be replaced by non-empty words. They are famous in learning theory because they are usually easy to identify (guess the rule).
The Finding: Even though these are famous for being easy to learn, they are hard to generate.
The Metaphor: Imagine a club where the rule is "The word must look like a palindrome." It's easy to spot the pattern, but the paper shows that to generate a new valid member, you might need to watch an exponential number of people first.
Result: Exponential. Still too many examples to be feasible.

The Core Conclusion

The paper draws a sharp line between Existence and Feasibility.

Existence: "Yes, if you wait forever and see infinite examples, you can eventually learn to generate the language." (This was already known).
Feasibility: "No, because the number of examples required to get there is so massive that you will never reach it in the lifetime of the universe."

The "Gap":
The authors show that for many standard types of languages (like those used in programming or basic logic), the "sample complexity" (the number of examples needed) is a barrier. It's like having a key that opens a door, but the key is made of a material that takes a billion years to forge.

Why This Matters (According to the Paper)

The paper suggests that while Large Language Models (LLMs) seem to learn languages easily, they might be getting lucky. They are working with language structures where these "impossible" intersections don't happen as often, or where the "Secret Club" rules are simpler than the worst-case scenarios the authors tested.

However, the paper warns us: Just because a computer can generate text doesn't mean it has "learned" the underlying rules in a way that is computationally efficient. For many theoretical language classes, the gap between "possible" and "practical" is unbridgeable.

In short: You can always learn to mimic a language eventually, but for many types of languages, the cost in data is so high that it might as well be impossible.

Technical Summary: Language Generation in the Limit: Complexity Barriers and Implications for Learning

Problem Statement
The paper investigates the computational feasibility of "language generation in the limit," a concept introduced by Kleinberg and Mullainathan (2024). While it is established that any countable family of languages is generatable in the limit at the level of computability (i.e., a generator can eventually produce strings indistinguishable from a target language given infinite positive examples), this existential result does not address feasibility. The central problem is to determine the sample complexity required for uniform generation: specifically, how many examples are needed before a generator can reliably produce a new string from a target language, uniformly across a finite family of languages. The authors aim to identify whether severe feasibility barriers exist for canonical classes of formal languages, even those known to be learnable or structurally simple.

Methodology and Framework
The authors analyze the sample complexity of uniform generation for finite families of languages. They distinguish this from "generation in the limit" (which allows convergence time to depend arbitrarily on the target and example ordering) and "non-uniform generation" (where convergence depends on the target but not the ordering).

The core theoretical tool is Proposition 2.3, which characterizes the impossibility of $m$ -generation. A family $\mathcal{F}$ is not $m$ -generatable if and only if there exists a non-empty subset $S \subseteq \mathcal{F}$ such that the intersection $\bigcap_{L \in S} L$ is finite and has a size of at least $m$ . Consequently, the sample complexity is directly governed by the size of the largest finite intersection of languages within the family. The authors construct specific families of languages within various classes (Context-Free, Regular, Locally Threshold Testable, and Pattern Languages) to derive lower and upper bounds on these intersection sizes, thereby establishing bounds on the required sample complexity.

Key Contributions and Results

Context-Free Languages (CFLs):
The authors demonstrate that for families of context-free languages, the sample complexity is non-computable. Even for a family consisting of only two infinite languages specified by Context-Free Grammars (CFGs) or Pushdown Automata (PDAs), no algorithm can compute a bound $m$ that guarantees $m$ -generatability. This result is proven via a reduction from the Halting Problem, showing that determining the size of the intersection of two infinite CFLs is undecidable. This holds even for deterministic PDAs, indicating that non-computability arises from the structural properties of the class rather than non-determinism.
Regular Languages:
For finite families of regular languages (specified by DFAs, NFAs, or regular expressions), the problem becomes computable but incurs a double-exponential sample complexity.
- Upper Bound: The family is $a^{s|\mathcal{F}|}$ -generatable, where $s$ is the number of states in the automata and $|\mathcal{F}|$ is the family size.
- Lower Bound: The authors construct a family of binary regular languages where the required sample size is at least $2^{\Omega(s)}$ . This establishes that the double-exponential barrier is intrinsic to the class of regular languages, regardless of the representation (automata or expressions).
Locally Threshold Testable (LTT) Languages:
LTT languages are a robust subclass of regular languages defined by local counting conditions on substrings. Restricting the family to LTT languages reduces the complexity from double-exponential to single-exponential.
- Upper Bound: The sample complexity is bounded by $a^{3s|\mathcal{F}|((s|\mathcal{F}|)^2+1)^2}$ .
- Lower Bound: The authors prove a lower bound of $2^n$ for families of two LTT languages over an alphabet of size $n$ .
  While this represents a strict improvement over general regular languages, the authors note that single-exponential complexity remains computationally infeasible for practical purposes.
Non-Erasing Pattern Languages:
These languages, generated by patterns with non-empty variable substitutions, are known to be identifiable in the limit under Gold's model. However, the authors show they face an exponential lower bound on sample complexity for generation. They construct a family of two patterns where the intersection size is $2^n$ , implying that $2^n$ examples are necessary for uniform generation. This highlights that favorable properties for identification do not necessarily translate to feasible generation.

Significance and Implications
The paper establishes a clear and fundamental gap between the theoretical possibility of language generation in the limit and its computational feasibility. The authors argue that while generation is always possible in principle, the sample complexity for canonical language classes (including regular and context-free) is prohibitively high or even non-computable.

The results suggest that the feasibility of generation in practical settings (such as Large Language Models) likely depends on the specific structural properties of the language families encountered in practice. If the intersections of the underlying language structures are small, efficient generation may be possible; however, for general formal language classes, the "poverty of the stimulus" is not the primary barrier—rather, the combinatorial explosion of finite intersections creates insurmountable sample complexity barriers. The work connects language generation to classical problems in formal language theory, specifically the complexity of deciding the non-emptiness and size of language intersections, offering a new lens through which to view the complexity of generalization.