WorksComputer Science
Scaling Makes It Possible: How Large Models Master Impossible Languages
Abstract
While language models (LMs) excel in natural language tasks, their ability to learn impossible languages–those that violate the structural, cognitive, or logical constraints that make human languages learnable and functional–remains debatable. This controversy is further fueled by a divide between linguistic theorists and empirical researchers working with small-scale LMs. To address this controversy, we introduce semantic coherence. This concept measures how effectively semantic information is expressed in language structures and examines the learning capabilities of LMs across multiple scales. By fine-tuning billion-parameter LMs on impossible language samples, we demonstrate that larger LMs achieve similar performance on impossible and possible languages, whereas million-parameter LMs exhibit significant degradation when trained on impossible languages. This performance gap widens as semantic complexity increases. We further show that scaling up the LM size fundamentally shifts the learning focus from grammatical rules to semantic understanding, with billion-scale LMs exhibiting a threefold reduction in sensitivity to low-level linguistic perturbations while maintaining stable performance under high-level semantic perturbations.
pnas_main.pdf
Significance Statement We investigate how language models (LMs) learn impossible languages that defy human linguistic constraints. Our findings reveal that as the model scale increases, LMs shift from syntactic reliance to semantic abstraction, enabling them to master impossible languages. Billion-scale models exhibit reduced sensitivity to syntactic perturbations and enhanced semantic understanding, challenging traditional linguistic theories prioritizing syntax. This highlights a fundamental difference between human and LM language learning mechanisms. By bridging linguistic theory and computational modeling, our study provides new insights into how LMs generalize beyond conventional language structures, reshaping our understanding of their cognitive and computational capabilities.
Language models (LMs) excel at various large-scale natural language tasks, such as text generation [1], machine translation [2], and question answering [3], demonstrating a clear proficiency in human-learnable, rule-based structures known as possible languages. However, it remains debated whether LMs can also learn impossible languages, which violate structural or cognitive constraints that define human language. Linguistic theorists like Chomsky argue that LMs lack mechanisms to distinguish possible from impossible languages, suggesting that both should be equally learnable (4–6). Conversely, recent empirical studies have challenged this view by systematically constructing impossible languages and showing that small-scale LMs struggle to learn them as effectively as possible languages (7).
These empirical studies primarily utilize small-scale models such as GPT-2 (with millions of parameters) trained from scratch to assess their learning boundaries [1] [7]. They found that GPT-2 learns possible languages more efficiently and is notably sensitive to grammatical rules, indicating a strong syntactic bias. However, we argue that such findings might not generalize to larger-scale models, which are known to better capture semantic information.
Traditional linguistic theory emphasizes grammar as essential for systematically encoding and communicating semantic content through transformational rules (8, 9). Possible languages adhere to cognitive and grammatical constraints, enabling structured semantic encoding and efficient learning. Impossible languages violate these constraints, resulting in structures that are unnatural or challenging for human cognition.
Nevertheless, human languages with limited grammatical structure, such as Pirahã spoken by indigenous Amazonian communities (10), or symbolic systems such as Nigeria’s Nsibidi (11), Ghana’s Adinkra symbols (12), and Angola’s Lusona/Sona geometric notation (13), demonstrate effective semantic communication without traditional grammar. This suggests that semantic information alone, irrespective of syntactic complexity, can facilitate language acquisition. To quantify this idea, we introduce semantic coherence, defined as the ease with which semantic information is conveyed within a linguistic structure. We hypothesize that larger-scale LMs are better equipped to comprehend semantic coherence, thus enabling more efficient learning of impossible languages.
Interestingly, our findings at larger scales diverge from recent empirical results with smaller models (7) and align more closely with theoretical claims by linguistic theorists (4). Specifically, we show: i) Billion-scale LMs such as Llama3.2 and Qwen2.5 significantly outperform smaller GPT-2 models in learning impossible languages, especially those with low-
YJ and CZ designed and conducted the experiments, analyzed data, and wrote the manuscript. CM contributed to experimental design, interpreted results, and provided theoretical support. SV supervised the entire research, conceptualized the project, guided analysis and interpretation, and revised the manuscript critically for important intellectual content. All authors read, provided critical feedback, and approved the manuscript. level perturbations. ii) Smaller models (e.g., GPT-2) emphasize grammatical structures, limiting their semantic understanding under syntactic perturbations. Conversely, larger models prioritize high-level semantic comprehension and thus exhibit reduced sensitivity to low-level syntactic disruptions. iii) Our proposed Lipschitz-Optimizer further improves LMs’ performance and convergence on impossible languages, without necessitating architectural modifications.
Overall, we argue that large LMs’ capacity to learn impossible languages primarily stems from their enhanced ability to comprehend and utilize semantic information. When semantic content is sufficiently coherent, large-scale LMs can effectively master languages irrespective of their syntactic complexity (or even impossibility).
Results
To explore LMs’ capability boundary of learning possible and impossible languages, we examine LMs across different scales and languages with different possibilities. We construct a series of impossible languages based on the impossibility continuum proposed by Mission (7) and classify them into different categories based on the preservation of linguistic information, as shown in Table 1 and Figure 1. The table evaluates each type of impossible language in terms of semantic retention, syntactic structure, and overall coherence. To illustrate this classification, we provide a detailed explanation in Figure 2.
Figure 1. Effects of language perturbations on syntactic and semantic information preservation. SC (semantic coherence) is categorized into three levels: SC = 0 (languages with complete syntax and semantics), SC = -1 (languages with incomplete syntax but complete semantics), and SC = -2 (languages with both incomplete syntax and semantics). Based on their perturbation functions, impossible languages are classified into three types: Shuffle Languages (EvenOddShuffle, LocalShuffle(w), DeterministicShuffle(s), FullReverse, PartialReverse, Tokens4Hop, Words4Hop), Reverse Languages (FullReverse and PartialReverse), and Hop Languages (Tokens4Hop and Words4Hop). For control groups, NoShuffle, NoReverse, and NoHop represent natural languages corresponding to each class of impossible languages.
Figure 2. Illustration of complete and incomplete syntax and semantic information retention. This figure presents a hierarchical flow demonstrating how perturbation functions impact language structures and influence their learnability. On the left, an example sentence with complete syntax retention, The earth revolves around the sun, is shown. When perturbation functions are applied, the sentence undergoes syntactic transformations, resulting in an altered structure, The sun revolves around the earth, which leads to incomplete syntax retention. The middle section illustrates changes in syntax tree structures under perturbations, highlighting how these transformations contribute to syntactic incompleteness. The right side categorizes semantic retention into two possible outcomes: complete semantic retention occurs when syntax transformation rules are completely random, non-deterministic, and irreversible, preventing LMs from learning these rules. In contrast, incomplete semantic retention arises when these rules are deterministic and reversible, allowing LMs to learn them. Additionally, the figure provides key linguistic components, including S (Sentence), N (Noun), V (Verb), NP (Noun Phrase), PP (Prepositional Phrase), VP (Verb Phrase), and Det (Determiner), as references for interpreting the syntax tree structures.
For semantic retention, applying perturbation functions to natural languages alters their syntactic structure, meaning the perturbed languages exhibit incomplete syntactic retention. However, suppose LMs can learn the syntactic transformation rules. In that case, the perturbed language effectively becomes a structured transformation of the original, allowing it to retain complete semantic information and remain semantically intact. Among the various perturbations, only NonDeterministicShuffle is entirely random, making it impossible for LMs to learn any consistent transformation rule. As a result, the corresponding perturbed language fails to retain complete semantic meaning. For instance, given the perturbed sentence The sun revolves around the earth, LMs cannot reliably recover its intended meaning, The earth revolves around the sun, rendering this type of language semantically incomplete.
| PL | Perturbation | Semantic | Syntactic | SC |
| High | NoShuffle | ✓ | ✓ | 0 |
| EvenOddShuffle | ✓ | ✗ | −1 | |
| LocalShuffle(w) | ✓ | ✗ | −1 | |
| DeterministicShuffle(s) | ✓ | ✗ | −1 | |
| NonDeterministicShuffle | ✗ | ✗ | −2 | |
| Low | NoReverse | ✓ | ✓ | 0 |
| FullReverse | ✓ | ✗ | −1 | |
| PartialReverse | ✓ | ✗ | −1 | |
| NoHop | ✓ | ✓ | 0 | |
| Tokens4Hop | ✓ | ✗ | −1 | |
| Words4Hop | ✓ | ✗ | −1 |
Table 1. Table 1. Impact of language perturbations on linguistic information preservation. The table categorizes perturbations by Perturbation Level (PL: High or Low) and Semantic Coherence (SC: 0, -1, -2). A checkmark (✓) indicates complete retention of semantic or syntactic information, while a cross (✗) indicates incomplete retention. See Appendix A for more cases about different perturbations.
In our experiments, we choose GPT-2 [1], Llama3.2 (14, 15), and Qwen2.5 (16) language models and train them on the original BabyLM dataset (17). Through these experiments, we validate LLMs’ learnability from four different views: (1) Different impossible languages are learnable if they retain semantics; (2) Scaling LM makes learning impossible languages possible; (3) Scaling reduce LMs’ sensitivity to structural linguistic Features; (4) Lipschitz-Optimizer enhances LMs’ learnability of impossible Languages.
Different Impossible Languages are All Learnable
Our study demonstrates that LLMs can learn impossible languages altered by structural changes, artificial variants of natural language perturbed by systematic transformations. By fine-tuning Llama3.2-3B on these variants, we show that semantic coherence governs LLMs’ ability to master impossible languages. Our experiments reveal that despite significant syntactic alterations, LLM successfully learns these impossible languages when semantic information remains complete, indicating that semantic coherence outweighs syntactic fidelity in language learning processes.
Impossible languages are categorized into shuffle, reverse, and hop types based on their perturbation functions, as detailed in Materials and Methods. These different impossible languages present varying degrees of semantic coherence, which correlates with their difficulty for language models. We measure the learnability of LLMs for these impossible languages by their perplexity on corresponding test datasets (Figure 3). Our analysis reveals two key phenomena: (a) The learnability varies significantly across impossible language types, with shuffle languages generally exhibiting the highest perplexities (most of them are around 6), followed by hop languages (perplexities approach 5 or lower), and then reverse languages (perplexities are all below 5); (b) Remarkably, LLMs learn most of these languages effectively (perplexities are all below 5), except for NondeterministicShuffle languages (perplexity approaches 9). Even more surprisingly, for FullReverse and Tokens4Hop variants, LLMs demonstrate better learning performance (lower perplexity) than unperturbed languages.
From these phenomena, we conclude that semantic coherence determines the difficulty of learning languages, while semantic integrity governs whether languages can be mastered as efficiently as natural languages. Regarding phenomenon (a), the varying degrees of semantic coherence across language types directly correlate with their learnability: shuffle languages, having the lowest semantic coherence, are the most challenging to learn, while reverse and hop languages with higher semantic coherence are comparatively easier to master. For phenomenon (b), NondeterministicShuffle languages lack complete semantic information, making them the most difficult to learn. Conversely, FullReverse and Tokens4Hop languages maintain high semantic coherence and complete semantic information, enabling LLMs to learn these languages efficiently—even more efficiently than natural languages in some cases.
Scaling LM Makes Learning Possible
Previous research has established that LM performance scales predictably with parameter count (18). Building on this foundation, our findings demonstrate that model scale is also a critical determinant of an LM’s capacity to learn impossible languages, extending the scaling law paradigm to these structurally perturbed language variants. As LM scale increases, we observe two key phenomena: first, the capability to learn impossible languages improves dramatically; second, the performance gap between impossible and natural languages progressively narrows. This scaling effect reveals that larger LMs can effectively master various impossible languages, transforming what was previously considered unlearnable into achievable learning tasks.
Figure 3. Perplexities vary with training steps across different impossible languages on the test data. Lower perplexities indicate a better understanding of these languages by the language models. From left to right, perturbation functions are Shuffle, Reverse, and Hop, respectively. NoShuffle, NoReverse, and NoHop are controls, denoting unperturbed languages. All results are based on Llama3.2-3B.
The differences in LM scales—spanning smaller architectures to larger ones—are quantified across three dimensions: parameter counts, training token volumes, and computational costs (measured in ZettaFLOPs), as summarized in Table 5. This systematic comparison demonstrates how impossible language learning capabilities scale predictably with model size, revealing a fundamental relationship between scale and linguistic adaptability. To investigate the relationship between model scale and impossible language learning, we employed a diverse range of LMs, including GPT-2 (117M), Llama3.2 (1B-3B), and Qwen2.5 (0.5B-14B). Table 2 and Table 3 reveal two key phenomena: (a) shuffle languages consistently exhibit higher perplexities (10%–60% higher) and substantially larger perplexity gaps (5-15 time greater) compared to reverse and hop languages, confirming their greater learning difficulty; (b) as model scale increases, perplexities decrease substantially, with particularly dramatic improvements observed when scaling from GPT-2 (117M) to Llama3.2 (1B), where perplexities on Llama3.2 (1B) are approximately 1/5 of those on GPT-2 (117M). Additionally, perplexity gaps approach zero, especially for reverse languages and hop languages, with their perplexity gaps on Qwen2.5-14B falling below 3%; however, for all LMs, perplexity gaps of NondeterministicShuffle languages increase gradually as scale increases. Generally, these findings suggest that larger LMs not only learn impossible languages more effectively but also become increasingly insensitive to linguistic perturbations.
| Perturbation | GPT-2 (114M) | Llama3.2 (1B) | Llama3.2 (3B) |
| NoShuffle(Baseline) | 23.24 | 4.58 | 4.40 |
| EvenOddShuffle | 30.28 (+30.3%) | 5.36 (+17.0%) | 5.06 (+15.0%) |
| DeterministicShuffle | 36.79 (+58.3%) | 6.38 (+39.3%) | 6.01 (+36.6%) |
| NondeterministicShuffle | 42.73 (+83.9%) | 8.62 (+88.2%) | 8.44 (+91.8%) |
| NoReverse(Baseline) | 21.00 | 4.36 | 4.20 |
| FullReverse | 21.24 (+1.1%) | 4.34 (-0.5%) | 4.18 (-0.5%) |
| PartialReverse | 23.08 (+9.9%) | 4.69 (+7.6%) | 4.49 (+6.9%) |
| NoHop(Baseline) | 24.26 | 4.69 | 4.48 |
| Tokens4Hop | 26.22 (+8.1%) | 4.71 (+0.4%) | 4.49 (+0.2%) |
| Words4Hop | 32.14 (+32.9%) | 5.37 (+14.5%) | 5.07 (+13.2%) |
Table 2. Perplexity varies under input perturbations across GPT-2 and Llama3.2 model scales. Values show perplexities on each perturbation; the percentage in brackets indicates the perplexity gap, which is the percentage increase in the model’s perplexity on the impossible language and the corresponding natural language. NoShuffle, NoReverse, and NoHop are controls, as baseline. A smaller gap indicates a better understanding of impossible languages.
| Perturbation | Qwen2.5 (0.5B) | Qwen2.5 (1.5B) | Qwen2.5 (3B) | Qwen2.5 (7B) | Qwen2.5 (14B) |
| NoShuffle(Baseline) | 2.71 | 2.64 | 2.59 | 2.49 | 2.47 |
| EvenOddShuffle | 3.07 (+13.3%) | 2.98 (+12.9%) | 2.92 (+12.7%) | 2.79 (+12.1%) | 2.72 (+10.1%) |
| DeterministicShuffle | 3.30 (+21.8%) | 3.23 (+22.3%) | 3.17 (+22.4%) | 3.05 (+22.5%) | 2.89 (+17.0%) |
| NondeterministicShuffle | 3.62 (+33.6%) | 3.57 (+35.2%) | 3.54 (+36.7%) | 3.47 (+39.4%) | 3.44 (+39.3%) |
| NoReverse(Baseline) | 2.55 | 2.49 | 2.44 | 2.36 | 2.33 |
| PartialReverse | 2.69 (+5.5%) | 2.62 (+5.2%) | 2.57 (+5.3%) | 2.47 (+4.7%) | 2.40 (+2.9%) |
| NoHop(Baseline) | 2.76 | 2.68 | 2.63 | 2.51 | 2.47 |
| Words4Hop | 2.82 (+2.2%) | 2.74 (+2.2%) | 2.68 (+1.9%) | 2.56 (+2.0%) | 2.50 (+1.2%) |
Table 3. Perplexity varies under input perturbations across Qwen2.5 model scales. Values show perplexities on each perturbation; the percentage in brackets indicates the perplexity gap, which is the percentage increase in the model’s perplexity on the impossible language and the corresponding natural language. NoShuffle, NoReverse, and NoHop are controls, as baseline. A smaller gap indicates a better understanding of impossible languages.
| Model | Parameter (B) | Tokens (B) | ZettaFLOPs | Optimizer |
| GPT-2 | ||||
| 117M | 0.117 | (1, 3) | 0.007 | Adam |
| Llama-3.2 | ||||
| 1B | 1.0 | 9,000 | 54 | AdamW |
| 3B | 3.0 | 9,000 | 162 | AdamW |
| Qwen-2.5 | ||||
| 0.5B | 0.5 | 18,000 | 54 | AdamW |
| 1.5B | 1.5 | 18,000 | 162 | AdamW |
| 2.5B | 2.5 | 18,000 | 270 | AdamW |
| 3.0B | 3.0 | 18,000 | 324 | AdamW |
| 7.0B | 7.0 | 18,000 | 756 | AdamW |
| 14.0B | 14.0 | 18,000 | 1,512 | AdamW |
Table 5. Model scaling specifications across three architectures (GPT-2, Llama-3.2, and Qwen-2.5). The parameters number (unit is billion) and training tokens number (unit is billion) are referred from official reports [1] [14, 15, 16], with computation measured in ZettaFLOPs. Computational costs are estimated using the heuristic FLOPs ≈ 6ND, where N denotes parameters and D denotes tokens [18, 57].
Phenomenon (a) can be attributed to shuffling languages having reduced semantic coherence and more severely disrupted syntactic structures, further validating our hypothesis that semantic coherence determines language learning difficulty. Regarding phenomenon (b), scaling substantially enhances LMs’ ability to learn impossible languages by enabling larger models to transcend syntactic perturbations and access the underlying semantic information preserved in these languages. The abnormal trend for NondeterministicShuffle languages occurs because these languages are semantically incomplete, making it increasingly difficult for LMs to capture sufficient semantic information compared to natural language as the model scale increases. Consequently, as LM scale increases, the learnability gap between impossible and natural languages diminishes, particularly for impossible languages that maintain complete semantic information despite their syntactic alterations.
Scaling Reduce Structural Linguistic Sensitivity
Our analysis demonstrates that larger LMs exhibit superior capability in learning impossible languages. To elucidate this phenomenon, we dissect their language learning mechanisms through three key findings: (a) Structural-to-semantic shift: Scaling reduces LMs’ reliance on structural linguistic features, prioritizing semantic abstraction in impossible language processing; (b) Layer-specific specialization: Lower layers primarily capture syntactic structures, whereas higher layers emphasize semantic abstraction, aligning with findings from previous studies (19–21). Scaling amplifies higher layers’ semantic encoding capacity; (c) Generalization resilience: Enhanced semantic processing enables robust performance across both natural and impossible languages, enhancing their resilience to linguistic perturbations.
To investigate these findings, we conduct two complementary experiments: (1) layer-wise masking to probe semantic representations and (2) layer-wise noise injection to assess syntactic and grammatical encoding.
Figure 4 reveals several key phenomena: (i) Masking FFN layers yields significantly higher values (2-10× greater) than masking ATTN modules across perturbations. Notably, scaling reduces the gap between FFN and ATTN: on smaller LMs, the gap narrows progressively with model size, collapsing to < 0.5 for all languages at the 14B scale. This demonstrates that FFN components dominate over attention mechanisms in impossible language acquisition, while scaling attenuates their functional divergence. (ii) Masking higher layers generally yields 2-3× higher values than masking lower layers (except Qwen2.5-14B showing the inverse trend), demonstrating that higher layers are more critical for LMs to master impossible languages. (iii) As the model scale increases, the values of the lower layer stabilize () while the higher layer values decrease sharply (7 → 0.5). Currently, the gaps between the impossible and natural languages decrease - consistent with previous findings - indicating that scaling reduces the sensitivity to semantic perturbations, yet preserves the syntactic sensitivity and enhances the learnability of the LMs of impossible languages.
Figure 4. Perplexity shift () measures a layer’s contribution to language processing, defined as , where is the perplexity before masking and is the perplexity after masking. A higher indicates greater importance. This figure shows across layers under layer-wise masking for three types of impossible languages (NonterministicShuffle, PartialReverse, and Words4Hop, shown in blue) and their corresponding control groups (NoShuffle, NoReverse, and NoHop, shown in red). Results are presented for four model scales: GPT-2, Qwen2.5-3B, Qwen2.5-7B, and Qwen2.5-14B (top to bottom). Bold lines represent for feed-forward network (FFN) module masking, while dashed lines indicate for attention network (ATTN) module masking.
Figure Figure 5 demonstrates a complementary phenomenon: (iv) values monotonically decrease with layer depth, with lower-layer consistently surpassing higher-layer values. This demonstrates stronger noise sensitivity in lower layers, combined with (c), further validating findings (a) and (b). (v) For low-level perturbations (reverse/hop), gaps between impossible and natural languages approach zero in Qwen models (e.g., < 0.001 for Qwen-14B). For high-level perturbations, gaps remain pronounced but diminish with scaling across all layers (maximum : 0.03→0.004 on shuffled languages), indicating that scaling reduces divergence
Figure 5. Perplexity shift () measures a layer’s sensitivity to noise when processing languages, defined as , where is the model’s perplexity before noise injection and is the perplexity afterwards. A lower indicates greater stability. The figure shows across layers under layer-wise noise injection for impossible languages (NonterministicShuffle, PartialReverse, and Words4Hop, shown in blue bold lines) and their corresponding control groups (NoShuffle, NoReverse, and NoHop, shown in light reddish brown dashed lines). Results are presented for four model scales: GPT-2, Qwen2.5-3B, Qwen2.5-7B, and Qwen2.5-14B (top to bottom).
between linguistic types and enhances LMs’ overall stability for structural perturbations.
The phenomenon (i) can be attributed to the fundamental roles of different types of modules: FFN layers are primarily responsible for encoding syntactic and semantic properties (22–26), while attention modules primarily facilitate token selection and relationship modeling (23, 27–29). This functional distinction makes FFN layers substantially more critical for learning impossible languages. Additionally, as models scale, these FFN modules develop enhanced capabilities for capturing both syntactic and semantic information, resulting in greater resilience to information absence during masking experiments. Regarding phenomenon (ii), lower layers predominantly capture syntactic structure, whereas higher layers focus on semantic modeling (19–21), and semantic information proves more crucial for language acquisition. For phenomenon (iii), scaling enhances LMs’ ability to capture semantic information while producing relatively minor improvements in syntactic and grammatical processing. This indicates that larger LMs’ improved language understanding stems primarily from enhanced semantic processing rather than syntactic comprehension. Phenomenon (iv) occurs because syntactic and structural features are more vulnerable to noise than semantic information; since lower layers are responsible for encoding these syntactic features, they exhibit greater sensitivity to noise perturbations. Finally, phenomenon (v) demonstrates that scaling enhances LMs’ language understanding by improving their semantic processing capabilities while reducing reliance on syntactic information, thereby making them less sensitive to noise. Overall, as the model scale increases, LMs’ semantic processing abilities improve substantially, rendering them more robust to syntactic perturbations such as noise injection.
Lipschitz-Optimizer Enhance Learnability of Impossible Languages
We find that by adjusting the optimizers, even without changing the model design itself, LM convergence is slightly accelerated, and stability to perturbed languages is improved, ultimately improving the learnability of LMs on impossible languages.
The Lipschitz constant, defined as the maximum change in output space corresponding to a variation in input space for neural networks, has been widely applied across diverse domains. These applications include closed-loop system stability analysis (30, 31), stability verification (32), fairness guarantees (33), and stability metrics for various architectures (34–38). Additional applications extend to reachability analysis (39), guaranteed generalization bounds (40), and invertible neural networks (41). By constraining the Lipschitz constant of parameters during optimization, we can enhance parameter convergence speed and improve LMs’ stability when processing impossible languages. Table 4 and Figure 6 reveal two significant phenomena: (a) Lipschitz-Optimizer dramatically accelerates convergence, achieving in 200 steps what the original optimizer requires 500 steps to accomplish; (b) Lipschitz-Optimizer reduces both losses and perplexities by 3%-5% across all impossible language types, indicating enhanced language comprehension capabilities. Notably, for languages with lower-level perturbations (reverse and hop variants), LMs optimized with our approach outperform their performance in natural languages, demonstrating exceptional versatility and stability across diverse linguistic challenges.
Figure 6. Validation losses on Llama3.2-3B across training steps for impossible languages (Shuffle, Reverse, and Hop, from left to right). Results compare training with the Lipschitz Optimizer to those using the original optimizer.
| Shuffle Setting | Perplexity | Reverse Setting | Perplexity | Hop Setting | Perplexity |
| NoShuffle | 5.26 | NoReverse | 5.00 | NoHop | 5.32 |
| DeterministicShuffle(s=84) | 7.37 | PartialReverse | 5.47 | Tokens4Hop | 5.35 |
| NondeterministicShuffle | 9.38 | FullReverse | 5.07 | Words4Hop | 6.11 |
| DeterministicShuffle(s=84)(+Lip) | 6.97 | PartialReverse(+Lip) | 5.11 | Tokens4Hop(+Lip) | 5.02 |
| NondeterministicShuffle(+Lip) | 9.02 | FullReverse(+Lip) | 4.81 | Words4Hop(+Lip) | 5.73 |
Table 4. Perplexities for Shuffle, Reverse, and Hop languages. (+Lip) denotes training process with Lipschitz-Optimizer on perturbed languages. Bold values indicate the Perplexity with Lipschitz-Optimizer.
The accelerated convergence observed in phenomenon (a) can be attributed to the Lipschitz constraint that promotes parameter smoothness, which streamlines the optimization trajectory during training. Regarding phenomenon (b), Lipschitz-Optimizer effectively reduces LMs’ sensitivity to syntactic perturbations while enhancing their ability to extract preserved semantic information from impossible languages. This dual mechanism enables LMs to develop more robust representations of linguistic content despite structural alterations, ultimately improving comprehension of impossible languages across various perturbation types.
Discussion
Our study demonstrates that LM scaling fundamentally enhances the ability to learn impossible languages through a transition from syntactic dependency to semantic abstraction. By introducing the concept of semantic coherence, which quantifies how linguistic inputs preserve meaning despite structural perturbations, we find that larger LMs more effectively extract semantic information compared to smaller models. Consequently, models such as Qwen2.5-14B achieve performance on impossible languages nearly equivalent to natural languages, provided semantic completeness remains intact. These findings, from the perspective of impossible languages, align closely with known scaling laws established on natural languages(18), showing that sufficiently large LMs develop adaptive mechanisms for semantic generalization beyond structural linguistic constraints.
Our experiments identifies three primary mechanisms facilitating this scaling effect that scaled LMs generalize effectively to impossible languages: (i) structural-to-semantic shift: Larger models increasingly depend on semantic abstraction rather than low-level syntactic features, reducing the impact of structural perturbations. Deeper layers primarily encode semantic abstractions rather than syntactic constraints, explaining why structural impossible perturbations have minimal impact on LM performance; (ii) layer-specific specialization: FFN layers become more crucial than attention layers for semantic representation in larger LMs, gradually shifting their role from syntactic processing to semantic abstraction; (iii) generalization resilience: larger LMs exhibit increasing resilience to linguistic perturbations, particularly in the presence of NondeterministicShuffle perturbations. While small-scale LMs are highly sensitive to syntactic disruptions, billion-scale LMs maintain stable perplexities across different impossible languages, suggesting a fundamental shift toward semantic generalization.
These findings challenge classical linguistic theories and current perspectives on language learning. Classical linguistic theories emphasize hierarchical syntax as fundamental to human language acquisition (9, 42–45), categorizing languages that disrupt conventional syntactic structures as inherently unlearnable. Building upon these theoretical foundations, recent LM research predominantly focuses on syntactic and grammatical learning mechanisms, seeking parallels between human and machine language acquisition, particularly emphasizing hierarchical syntactic structures (46–50). Some studies propose that explicitly pre-training LMs on syntactic and semantic constraints can improve their natural language capabilities (51). Although semantic learning has also been explored (22, 25, 52–54), these investigations typically concentrate on isolated, single-model architectures, examining layers or modules independently without considering how learning strategies evolve with scaling.
In contrast, our study uniquely emphasizes the transformative influence of scaling on language acquisition strategies. By systematically perturbing natural languages, we simultaneously evaluate syntactic and semantic learning mechanisms across a range of model sizes. Our results illustrate a fundamental shift: smaller LMs predominantly rely on syntactic rules, whereas billion-parameter LMs increasingly transcend structural constraints, prioritizing semantic abstraction. This scale-dependent semantic shift enables larger models to comprehend impossible languages, even amid significant syntactic disruptions. Ultimately, our findings endorse the perspective that language’s essential nature lies not solely in hierarchical structures, but rather in its semantic capacity to represent diverse meanings, encompassing external reality and internal cognition (55). These insights considerably refine our understanding of language processing in latest AI systems.
Furthermore, these results bear practical implications for the development of AI models in low-resource and synthetic language settings. If semantic information alone is sufficient for effective learning, then explicitly grammatical scaffolding may not be necessary for training robust models. This raises questions about the cruciality of formal linguistic structure in LM pretraining and whether similar shifts occur in multilingual or non-Indo-European languages. Our study elicits several open questions:
Are LMs truly understanding the meaning of language itself? The decreased reliance on syntactic structures suggests that models prioritize semantic coherence, but whether this corresponds to genuine understanding or statistical pattern recognition remains an open debate.
Impact on generalization to natural languages: While our results indicate improved learnability of impossible languages, the consequences of reduced syntactic sensitivity for generalization to human-like linguistic reasoning require further investigation, especially considering that some minority languages worldwide share characteristics with impossible languages [10, 56]. These languages are valuable for further systematic academic collection and research replication.
Effects on Low-Resource and Compositional Generalization: If larger LMs rely less on structural rules, will this limit their ability to generalize in low-data regimes or for tasks requiring strong compositional reasoning?
Materials and Methods
Datasets We conduct experiments on a series of impossible languages generated by applying various perturbation functions (7) to the original BabyLM dataset (17). The BabyLM dataset is an English-language corpus containing approximately 100 million words, designed to simulate the linguistic input available to an English-speaking child. In our experiments, we utilize the text-only version of the BabyLM dataset, containing approximately 10 million words, which includes six sub-corpora: bnc_spoken, childes, gutenberg, open_subtitles, simple_wiki, and switchboard.
Models We select GPT-2, Llama3.2, and Qwen2.5 as our experimental LMs and display the scaling trends of these LMs, as shown in Table 5. This comparison reveals how learning behaviors and capabilities evolve with increases in model parameters, training tokens, and computational resources.
Metric We use perplexity as a metric for assessing language learning. Perplexity quantifies how effectively a language model predicts a set of words, being formally defined as the exponential of the entropy of the distribution. In practice, a lower perplexity score signifies a more accurate predictive model, indicating that the model is less ”perplexed” by the data it encounters.
Impossible Languages Construction Impossible languages can be constructed through a series of perturbation functions that map English input sentences to modified token sequences. By defining different perturbation functions, we create various languages spanning the impossibility continuum. These functions fall into three categories: Shuffle, Reverse, and Hop, each defining a distinct class of impossible languages.
Shuffle languages examine how word order perturbations affect semantic and structural information preservation. Reverse languages evaluate the impact of partial or complete word order reversals on meaning capture and adaptation to non-natural linguistic structures. Hop languages analyze how long-distance dependencies and grammatical markers influence a model’s ability to capture syntax and structure.
Shuffle languages, specifically, are generated by applying various reordering functions to sentence words. These are classified into five types based on the degree of structural perturbation introduced.
NonDeterministicShuffle: The input sentence is tokenized and then randomly shuffled, which results in a completely unordered sequence. This process introduces full randomness, making the transformation irreversible and linguistically incoherent.
DeterministicShuffle(s): The tokenized sentence is shuffled in a deterministic manner based on the token sequence length. This transformation is reversible but removes any recognizable linguistic structure.
LocalShuffle(w): The sentence is tokenized and shuffled within fixed-size local windows of width . This introduces localized perturbations in word order while maintaining some structural coherence.
EvenOddShuffle: After tokenization, the sentence is reordered such that all tokens at even indices precede those at odd indices. This retains partial linear structures, but introduces long-range reordering.
NoShuffle: The input sentence is tokenized, and the token sequence remains unchanged, serving as the control group.
Reverse languages are languages in which the word order within sentences is partially or completely reversed, and they are categorized into the following three types:
NoReverse: The input sentence is tokenized, and a special marker is inserted at a random position in the token list, serving as the control group.
PartialReverse: Similar to NoReverse, but all tokens following the marker are reversed.
FullReverse: The input sentence is tokenized, a marker is inserted randomly in the token list, and the entire token sequence is reversed.
Hop languages are created based on counting rules, and these languages are classified into three types:
NoHop: Add particular markers after all third-person present-tense verbs. Singular verbs are marked with , and plural verbs with . NOHOP retains the control group.
Tokens4Hop: Similar to NoHop, but makers are placed 4 tokens after the verb.
Words4Hop: Similar to NoHop, but makers are placed 4 words after the verb.
Lipschitz-Optimizer Implementation To enhance LLMs’ stability when processing linguistically implausible inputs, we introduce a Lipschitz-constrained optimization framework that accelerates convergence and improves model stability. Our supplementary materials thoroughly examine LLM stability through Lipschitz continuity, establishing theoretical foundations for spectral norm regularization during training.
This framework comprises five key components: Initial Update (init_update), Frobenius Norm Regularization (frobenius_reg), Spectral Norm Clipping (spectral_clip), Projection Radius Update (radius_update), and Weight Projection (weight_proj). init_update drives the model toward the loss function minimum through adaptive gradient optimization, providing reliable estimates for subsequent stability constraints. frobenius_reg penalizes weight matrices’ energy growth, preventing excessive parameter-space expansion, suppressing divergence in high-dimensional optimization trajectories, and enhancing generalization. spectral_clip constrains the maximum gain coefficient of neural network layers by dynamically truncating singular values, ensuring controllable input-output scaling ratios and blocking gradient explosion propagation. radius_update functions as a stability regulator, dynamically calibrating the feasible parameter region’s radius based on real-time training feedback, balancing flexibility and stability. weight_proj projects weight vectors into a controlled neighborhood anchored at initialization, preserving gradient directional information while restricting parameter drift magnitude. Detailed formula descriptions and derivations are available in the supplementary materials.
We refer to this framework as the Lipschitz-Optimizer, with its detailed implementation provided in Algorithm 1. It significantly enhances the stability of LLMs and accelerates their convergence speed.
| Algorithm 1 Implementation of Lipschitz-Optimizer |
def lipschitz_optimizer(W_init, T, tau, mu): |
""" |
Args: |
W_init: Initial weights |
T: Number of iterations |
tau: Spectral clipping threshold |
mu: Frobenius regularization factor |
Returns: |
W[T]: Optimized weights after T iterations |
""" |
W = [W_init] + [None] * T |
radius = [0] * (T + 1) |
for t in range(1, T + 1): |
# Initial adaptive gradient update |
W_grad = init_update(W[t-1]) |
# Frobenius norm regularization |
W_frob = frobenius_reg(W_grad, mu) |
# Spectral norm clipping |
W_clip = spectral_clip(W_frob, tau) |
# Update projection radius |
if t == 1: |
radius[t] = 1e-8 |
else: |
radius[t] = radius_update(radius[t-1], |
W_clip, W |
[0]) |
# Project weights towards initialization |
W_proj = weight_proj(W_clip, W[0], radius[ |
t]) |
# Final spectral clipping |
W[t] = spectral_clip(W_proj, tau) |
return W[T] |
Table 1 (PDF p. 10).
sup_main.pdf
This PDF file includes:
| Class | Language | Example 1 | Example 2 |
| Shuffle | NoShuffle | He packs his very heavy suit ca se . | They pack his very heavy suit ca se . |
| NondeterministicShuffle | heavy suit his ca very . se He packs | his . very ca They heavy se suit pack | |
| DeterministicShuffle(s=21) | packs He heavy suit ca se very . his | pack They heavy suit ca se very . his | |
| DeterministicShuffle(s=57) | packs his He heavy . ca very se suit | pack his They heavy . ca very se suit | |
| DeterministicShuffle(s=84) | He heavy . se his very suit packs ca | They heavy . se his very suit pack ca | |
| LocalShuffle(w=3) | his He packs suit very heavy . ca se | his They pack suit very heavy . ca se | |
| LocalShuffle(w=5) | his heavy very He packs se suit ca . | his heavy very They pack se suit ca . | |
| LocalShuffle(w=10) | heavy suit his ca very . se He packs | heavy suit his ca very . se They pack | |
| EvenOddShuffle | He his heavy ca . packs very suit se | They his heavy ca . pack very suit se | |
| Reverse | NoReverse | He packs his very heavy suit R ca se . | They pack his R very heavy suit ca se . |
| PartialReverse | He packs his very heavy suit R . se ca | They pack his R . se ca suit heavy very | |
| FullReverse | . se ca R suit heavy very his packs He | . se ca suit heavy very R his pack They | |
| Hop | NoHop | He pack S his very heavy suit ca se . | They pack P his very heavy suit ca se . |
| Tokens4Hop | He pack his very heavy suit S ca se . | They pack his very heavy suit P ca se . | |
| Words4Hop | He pack his very heavy suit ca se S . | They pack his very heavy suit ca se P . |
Table S1. Examples of impossible languages across three perturbation types: Shuffle, Reverse, and Hop. Different colors highlight distinct sentence components. S and R denote markers in Reverse and Hop settings, respectively.
Figure S1. These examples compare various unconventional linguistic and symbolic systems that emphasize semantic meaning over syntax rules. From left to right, it features: Pirahã Language (source: https://images.app.goo.gl/rAtsj2G61iH6DDWs8), Nsibidi Symbols (source: https://images.app.goo.gl/Abvv764nE3MrB4HH6), Lusona Ideographs (source: https://images.app.goo.gl/T382r9TNi217LMqs7), and Adinkra Symbols (source: www.kentecloth.net/kente-cloth-adinkra-symbols-meaning).
Supporting Information Text
Supplemental Theory
Impossible Language Construction and Classification
Impossible Language Examples
We conduct a series of experiments based on impossible languages. For clarity, we provide two sentence examples and their corresponding variants across Shuffle, Reverse, and Hop language types in Table S1. These examples refer to Kallini et al. [1], providing a clear approach for constructing impossible languages.
Unconventional Languages and Symbol Systems Beyond Grammar
We present several unconventional linguistic and symbolic systems, as shown in Figure S1, including four types:
Pirahã Language: A table showcasing pronouns in the Pirahã language, spoken by the Pirahã people of the Amazon. It is notable for its lack of recursion and unique approach to linguistic expression, emphasizing direct experience rather than complex grammatical structures.
Nsibidi Symbols: An ideographic writing system from southeastern Nigeria and Cameroon, historically used by the Ekpe secret society and other groups to convey complex ideas, emotions, and social status. Nsibidi symbols function as a visual language rather than a conventional alphabet.
Lusona Ideographs: A collection of symbolic designs originating from the Lunda and Chokwe people of Central Africa. These ideographs are traditionally drawn in the sand and serve as mnemonic devices, conveying oral stories, philosophical concepts, and mathematical ideas.
Adinkra Symbols: A set of visual symbols from the Akan people of Ghana, used to represent proverbs, historical events, and moral values. Each symbol carries deep cultural significance and is commonly found in textiles, pottery, and architectural designs.
These linguistic systems prioritize semantics over syntactic rules, meaning that semantic meaning plays a key role in communication rather than syntactic rules. This further supports our argument: a language can be learned by language models (LMs) as long as it possesses complete semantic. Scaling LMs enhances their semantic understanding, enabling them to learn even so-called "impossible" languages.
Sematic Coherence Explanation
We introduce semantic coherence (SC) in our paper as a measure of how effectively semantic information is conveyed through language structures. SC is categorized into three levels: 0, −1, and −2, which we refer to as , , and . Each level represents a different degree of syntactic and semantic retention:
: Languages that fully preserve both syntactic and semantic structures.
: Languages that retain complete semantic information but exhibit partial syntactic loss.
: Languages that have incomplete retention of both syntactic and semantic structures.
The retention of syntactic information in a language depends on whether the natural language syntax has been perturbed. If any perturbation is applied, the language is considered to have incomplete syntactic retention. Therefore, except for natural languages, which serve as control groups, all other languages exhibit incomplete syntactic retention. Similarly, for semantic information retention, if the perturbation function is deterministic, the perturbed language can be fully recovered into a natural language. In this case, we say the language has complete semantic retention. Otherwise, if recovery is not possible, the language has incomplete semantic retention. Among all perturbation functions, only NondeterministicShuffle is entirely random, making the corresponding languages unrecoverable. Therefore, it is the only function that results in incomplete semantic retention.
Lipschitz Perspective on LLM Stability
Why does the Lipschitz constraint improve the performance of LLMs in learning impossible languages? The Lipschitz-optimizer is designed with this principle in mind. Here we explore this question, starting with the formal definition of the Lipschitz constant.
A function is considered to be Lipschitz continuous on an input set if there exists a bound such that for all , satisfies:
The smallest possible in Equation (1) is referred to as the Lipschitz constant of . When represents a neural network, the essentially quantifies the maximum change in the output space corresponding to a variation in the input space. It reflects the network’s sensitivity to variations or perturbations in its input features, making the Lipschitz constant an important metric for evaluating the stability of a neural network.
Stability for Fine-Tuned models
We analyze the stability of fully fine-tuned LLMs through the lens of Lipschitz continuity, focusing on how controlled Lipschitz constants mitigate sensitivity to input perturbations. Our analysis begins with foundational definitions and builds to actionable stability guarantees.
Let the input space be a compact set equipped with norm , and let denote a mapping function with output norm . Given two input vectors , we define the fine-tuning difference as , where and represent the pre-trained and fine-tuned models respectively.
Three critical assumptions ground our analysis: (i) The pre-trained model and fine-tuned model are both Lipschitz continuous over the input space , with respective constants and ; (ii) All activation functions (e.g., ReLU, softmax) in and are Lipschitz continuous, excluding non-smooth operations; (iii) The input space is compact, ensuring the existence of global Lipschitz bounds for compositional mappings. Under these assumptions, the fine-tuning difference inherits Lipschitz continuity with constant . This leads to two fundamental inequalities:
Combining these through the triangle inequality reveals the composite Lipschitz bound governing stability:
Thus, the stability of the fine-tuned model depends on the combined Lipschitz constant . During full fine-tuning, minimizing (the Lipschitz constant of the fine-tuning difference) directly enhances stability, as remains fixed for the pre-trained model.
Stability for Impossible Languages
Impossible languages can be considered as natural languages augmented with perturbations, which aligns with the definition of impossible languages presented in this paper. Let denote natural languages, and represent impossible languages. Then, Eq. (4) can be expressed as:
where represents the imposed perturbation on natural languages, with a larger indicating a higher position on the impossibility continuum. From this, it follows that the Lipschitz constant and perturbation are closely related to the stability of LLMs. When is fixed, a smaller Lipschitz constant implies that the model is less influenced by perturbations in the output space, thereby exhibiting better performance and stability.
Correlation Between Linear Module Stability and LLM Stability
The compositional nature of LLMs allows us to characterize their stability through a Lipschitz analysis of constituent modules. While direct computation of exact Lipschitz constants for full LLMs remains computationally prohibitive, we establish an upper bound by the following Lemma.
Lemma 1. Consider an LLM composed of linear layers and nonlinear activation functions . The global Lipschitz constant of this model satisfies:
where denotes the spectral norm of the weight matrix , and the activation Lipschitz constants for standard activations (e.g., ReLU: , softmax with temperature : ).
Proof. Let be the composite function representing the LLM:
where each is a linear transformation and each is a nonlinear activation function. The bound (Eq. (6)) follows directly from the sequential application of Lipschitz continuity properties: first, each linear layer amplifies the norm of differences by at most its spectral norm ; second, nonlinear activations are standard and thus non-expansive (); third, residual connections, if present, add perturbations linearly rather than multiplicatively, thus not increasing the Lipschitz constant beyond multiplicative bounds already established. By iteratively applying these properties, we have:
Hence, Eq. (6) holds directly.
Spectral Dominance Mechanism. The Lipschitz constant of the linear module is given by the spectral norm of its weight matrix. For example, for linear module , its Lipschitz constant can be obtained as follow:
where is max singular value of and denotes the largest eigenvalue of . Combining Eq. (6) and Eq. (9), we conclude that during the full fine-tuning process, constraining the Lipschitz constants of linear modules in LLMs can significantly enhance their stability.
Spectral-Constrained Optimization for Stable Training
The training of modern LLMs often encounters instability issues due to the presence of unstable gradients. To tackle this, we propose various methods for controlling spectral norms, which provide mathematical guarantees for stability.
Initial Update
The first step of the optimization updates the weights via adaptive stochastic optimization. For , the -th iteration is:
where is the mini-batch loss, and denotes the AdamW optimizer [2] with decoupled weight decay. C.2. Spectral Norm Clipping. For a linear module’s weight matrix , we perform singular value decomposition (SVD):
The spectral norm clipping operation constrains each singular value:
Reconstructing the modified weight matrix:
This guarantees the spectral norm bound:
where denotes the spectral norm. The procedure effectively prevents excessive growth of spectral norms during training while preserving the original parameter structure.
Frobenius Norm Regularization
In addition to spectral norm clipping, we propose Frobenius norm regularization for indirect spectral control. For weight matrix , the Frobenius norm is defined as:
where are singular values. This establishes the inequality:
indicating that Frobenius Norm Regularization inherently constrains spectral norms. The regularized loss function becomes:
where is the regularization coefficient. The gradient update rule derives as:
Therefore, in optimizer, for , it can be written as during -th update:
where is the learning rate. This formulation enables seamless integration with standard optimizers like SGD and Adam.
Weight Projection
We employ a weight projection mechanism anchored to initialization to stabilize parameter updates while preserving model plasticity. Given initial weight and current weight at step , the projected weight is computed as:
where controls the projection radius. It ensures the preservation of the directional information of weight updates, limits the magnitude of deviation from the initial values, and maintains the gradient flow through normalized scaling. Together, these factors enhance both the stability and effectiveness of the training process.
Theorem 1. Let with residual matrix . Then the spectral norm satisfies:
Proof. The bound follows from norm subadditivity and the inequality . Applying this stepwise, we obtain:
Hence, the inequality holds as claimed. As shown in Theorem 1, the projection mechanism enforces control over spectral norms via , while automatically adapting to the intrinsic dimensionality of parameter updates via .
Projection Update
The Lipschitz constant of the weight matrix is principally governed by the projection radius in Theorem 1. To adaptively optimize this critical parameter, we formulate as a learnable variable updated via:
where denotes the AdamUpdate optimizer (3). The projection update mechanism achieves layer-wise adaptive control of Lipschitz constants through dynamically adjusting the projection radius , while preserving gradient directional consistency and reducing computational overhead via decoupled optimization strategies, ultimately achieving an efficient and robust training process.
References
- [1]J Kallini, I Papadimitriou, R Futrell, K Mahowald, C Potts, Mission: Impossible language models in Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). (2024).
- [2]I Loshchilov, Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101 (2017).arxiv.org/abs/1711.05101
- [3]J Tian, YC Liu, JS Smith, Z Kira, Fast trainable projection for robust fine-tuning. Adv. Neural Inf. Process. Syst. (2024).arxiv.org/abs/2310.19182






