A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Language
Authors: Ekdeep Singh Lubana
Kyogo Kawaguchi
Robert P. Dick
Hidenori Tanaka
Venue: ICLR 2025 Poster (2025)
Keywords: Emergence
Percolation
Formal languages
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Increase in data, size, or compute can lead to sudden learning of specific capabilities by a neural network---a phenomenon often called "emergence". Beyond scientific understanding, establishing the causal factors underlying such emergent capabilities is crucial to enable risk regulation frameworks for AI. In this work, we seek inspiration from study of emergent properties in other fields and propose a phenomenological definition for the concept in the context of neural networks. Our definition implicates the acquisition of general regularities underlying the data-generating process as a cause of sudden performance growth for specific, narrower tasks. We empirically investigate this definition by proposing an experimental system grounded in a context-sensitive formal language, and find that Transformers trained to perform tasks on top of strings from this language indeed exhibit emergent capabilities. Specifically, we show that once the language's underlying grammar and context-sensitivity inducing regularities are learned by the model, performance on narrower tasks suddenly begins to improve. We then analogize our network's learning dynamics with the process of percolation on a bipartite graph, establishing a formal phase transition model that predicts the shift in the point of emergence observed in our experiments when intervening on the data regularities. Overall, our experimental and theoretical frameworks yield a step towards better defining, characterizing, and predicting emergence in neural networks.

Published as a conference paper at ICLR 2025
A PERCOLATION MODEL OF EMERGENCE: ANALYZING TRANSFORMERS TRAINED ON A FORMAL LANGUAGE
Ekdeep Singh Lubana 11 Kyogo Kawaguchi Robert P. Dick Hidenori Tanaka 1.6
CBB-NTT Program in Physics of Intelligence, Harvard University
Nonnequilirrium Physics of Living Matter RIKEN Hakubi Research Team,
RIKEN Center for Biosystems Dynamics Research
RIKENN Cluster for Pioneering Research
Instiituee for Physics of Intelligence, Department of Physics, The University of Tokyo 'EECS Department, University of Michigan, Ann Arbor
Phyyiccs& & Informatics Laboratories, NTT Research, Inc., Sunnyvale, CA
ABSTRACT
Increase in data, size, compute can lead to sudden learning of specific capa- bilities by a neural network-a phenomenon phenookeno often called "emergence". Beyond scientific understanding, establishing the causal factors underlying such emergent capabilities is crucial to enable risk regulation frameworks for Al. In this work, we seek inspiration from study of emergent properties in other fields and propose a phenomenological definition for the concept in the context of neural networks. Our definition implicates the acquisition of general regularities underlying the data- generating process as cause of sudden performance growth for specific, narrower tasks. We empirically investigate this definition by proposing an experimental system grounded in mentext-sensitivg formal language, and find that Transform- ers trained to perform tasks on top of strings from this language indeed exhibit emergent capabilities. Specifically, show that once the language's 's underlying grammar and context-sensitivity inducing regularities are learned by the model, performance on narrower tasks suddenly begins improve. We then analogize our network's 's learning dynamics with the process of percolation on a bipartite graph, establishing a formal phase transition model that predicts the shift in the point of emergence observed in our experiments when intervening on the data regularities. Overall, our experimental and theoretical frameworks yield a step towards better defining, characterizing, and predicting emergence in neural networks.
INTRODUCTION
Modern neural networks, e.g., large language models (LLMs) (Gemini Team 2023 OpenAl 2023
Anthropic 2023 Touvron et al. 2023), exhibit a broad spectrum capabilities, allowing them to serve the "foundation" for downstream, application-specffic systems (Bommasani et al. 2022 Ahn et al. 2022 Driess et al., 2023 Schick et al., 2024). As these models scale, either via addition of more data, parameters, or compute, an intriguing behavior is times observed: until a certain critical
scale is reached, there are capabilities that the model does not exhibit; however, beyond this point,
such capabilities suddenly "emerge" (Wei al. 2022 Srivastava et al. 2022 Brown al. 2020 Yu
let al. [2022] Steinbardi
[023] Pan et al. 2022 Anil et al. 2023] Kirsch et al. [022]] He et al.) [024]] Elhage al. [202]] Tigges et al. (204)). More specifically, the performance of the model on task or benchmark meant to evaluate said capabilities witnesses substantial growth in performance, even though the overall training loss undergoes minimal, if any, improvements (Arora Goyal 2023]
Du et al. 2024). Empirical evidence in fact suggests that, at times, several capabilities can emerge simultaneously (Wei et al. 2022 Wei 2022).
Beyond developing better scientific understanding of neural networks, understanding emergent capabilities is crucial to enable risk-centric regulation frameworks for AI, which assume a system's 's capabilities can be preemptively conjectured (NIST) 2023 EU Council 2024 OSTP 2023 Kaminski
2023). To this end, recent work has made attempts at identifying factors that decide whether a
"Equal contribution. Code httpa//twa/////ocooocooaaaaaaaaa

---

Published as a conference paper at ICLR 2025
capability will emerge. For example, Okawa al. 2023 and Arora & Goyal (2023) implicate the underlying compositional structure of a capability as the cause for its sudden learning. Hoffmann et al. (2023) argue capabilities that involve interactions between specialized components within model are likely to yield sudden performance improvements once the correct interaction mechanism is learned; e.g., the interaction between the previous token and copy attention heads enable in-context learning (Elhage et al. [021] |ingh et al., 2024 Reddy] (023). Meanwhile, /Schaeffer et al. (2023) argue emergent abilities are an artifact of poorly defined, discontinuous evaluation metries, claiming that models undergo continuous, persistent improvements during training. Recent work has however demonstrated that even continuous metrics can witness sudden improvements, with such changes co-occurring with the model's learning of new capability (Chen et al. [024 Du et al. 2024). This undermines the claim that emergent capabilities are merely an artifact of evaluation protocols.
Taken together, the orthogonal explanations and disparate results above have resulted in emergence becoming an unclear phenomenon machine learning. At its core, however, we claim that the concept has never been defined in prior work (see App. B for a detailed related work). This has arguably led to distinct mechanisms causing sudden changes in model performance to all be labeled as "emergence". What is the phenomenology that this term is meant capture in the context of neural networks? Is it merely a sudden increase in performance with scale, or broader than that? Given reasonable definition, can we show, even if in simplified system, that emergent capabilities are commonplace? Can we use this simplicity to better understand what drives their sudden learning?
This work. To address the questions above, we pro- pose a phenomenological definition for emergence and try to understand what drives it in a toy task of learning formal languages (Chomsky 1956 Cagnetta
Phose: Solid phase 4.-
Liquid phose (1.0)
Gas phose
(L.))
& Wyart 2024; Liu 2023al Wen et al. [2023] Liu et al. 2022a]] Friedman et al. [203] Jain et al. 2023 Merrill et al., 2023). Specifically, we argue
Bend
Tarppanatore
three characteristics should be observed to claim a
Phase: Inltalzation
Capability learned Capabiliy learned
capability is emergent (see Def. [T]: beyond (i) sud- den performance improvement for specific task, we claim emergence is more likely to represent a meaningful concept if (ii) performance tasks improves simultaneously and (iii) there are pre- cise regularities underlying the data-generating pro- cess learned by the model at the point of emergence. The intuition, borrowed from the study of emergence in other fields (see Fig. D. is that if multiple tasks witness improvement in performance, there likely some shared structure to them and the model learns this structure at the point of emergence. For exam- ple, when in-context learning emerges in LLMs, the model learns that past context helps disambiguate the regularity present in natural language. This leads to in in-parallel improvement in several downstream tasks' perfor- mance (Wei et al. 2002) Weil 2022; Lu et al. (003); thus, in-context learning can be deemed an emergent capability under the scope of our definition. In this sense, understanding emergence can be formalized as a study of identifying which dataaregul the model learns at the point of sudden learning of set of capabilities, and understanding why those regular- ities are relevant to said capabilities. Adopting this perspective, make the following contributions.
(6,eg) - (00)
(1.0)
(LB
several
Capabiltyy 1
Capabiliyy 2
Data, Modal, Optiizationn Scale
Emergence as phases of learn- ing. Emergence is cell-charattrrized phe- nomenon in natural sciences (Anderson 1972. Newman et al. 2001 Newman] (003) and deeply entangled with the notion of phase changes, i.e., when change in some control variable (e.g., temperature) yields systematic changes in a system's 's underlying regularities (e.g., formation of hexagonal configurations in a crystal) and simultaneously affects sev- eral of its properties. We argue for a simi- lar characterization of emergence in machine learning: identifying systematic changes in model's behavior that influence its down- stream abilities and lead to sudden perfor- mance improvements. For example, learning language's 's syntax will affect all downstream capabilities where coherent, grammatically correct generations are necessary.
Figure 1:
next token better (Elhage et al., 2021
Formal Languages
Experimental System for Studying Emergence. We define a proba- bilistic context-sensitive grammar (PCSG) with type constraints that allow an entity or a subject in a sentence (e.g., man) to be seen in the context of only predefined set of properties (e.g., wa 1 k).
2

---

Published as a conference paper at ICLR 2025
We train models perform minimalistic reasoning tasks samples of this language and find their data scaling curves simultancously show sudden learning across several metrics.
Learning of general data regularities underlies simultaneous jumps in specific metrics. We find points of sudden change for metrics evaluating individual tasks correlate with the model learning two relevant regularities that underlie our formal language: grammatical rules and type constraints. Despite the simplicity of our setup, claim learning of such ragularguss is what leads to sudden growth in the performance of narrower tasks in large-scale models.
percolation model predicts the scaling of when capabilities emerge. We propose a formal model grounded in the theory of graph percolation (Cohen et al. (002) that captures our experimen- tal observations, and show that if we can describe the regularities the model is learning at the point of emergence, predictive theory for sudden learning can (at times) be -naaloogoo- to theories of phase transitions in physics; see Fig.
A PHENOMENOLOGICA DEFINITION OF EMERGENCE
To analyze emergence, we first establish what we mean by the term for the purpose this work. Specifically, define emergence in phenomenological manner, i.c., by assembling the characteristic properties associated with scaling curves claimed to depict emergent learning. We emphasize our definition is merely definition for emergence, and does not necessarily represent all possible perspectives (Luccioni & Rogers 2023).
Definition 1. (Emergence of a capability.) We say a capability C. is emergent with scaling along relevant axis (e.g., amount of data, compute, parameters) if:
discontinuous improvement occurs in the performance of task where C is required; multiple tasks simultaneously show discontinuous performance improvement; and the model learns regularities underlying the data generating process such that discontinuous progress in C's learning directly correlates with the learning of said regularities.
The definition above assigns broader meaning emergence than mere sudden performance im- provement on a narrow task: it argues there should be precise regularities underlying the data that learned by the model, yielding downstream effects on several capabilities and hence sudden im- provements in performance of several tasks. Note that we intentionally leave the notion of 'regularity' informal in the definition. The salient property of regularity is that if a model learns it, downstream tasks should become easier to perform. For example, a fine-grained notion of data regularity can be learning of context- sensitiviiy, which can aid in-context learning (Reddy 2023 Edelman et al.. 2024, Olsson et al.) 2022); a more coarse- grained regularity can include the model learning the syntactical rules language that help it with generation of coherent language and hence with any task where coherence is important (Chen et al.) 2024). In this sense, what is emergent is the learning of a regularity, and what observed a change in the model's s capabilities. Hypothesizing what this regularity is by identifying shared characteristics of set of tasks that simultancously show sudden learning, one can likely develop an evaluation meant to precisely gauge learning of the corresponding regularity and hence infer at what point independent training run will show sudden improvements.
We note the intuition for Def. I comes from prior work in the fields of complex systems and physics (Anderson 1972 Newman et al. 2001 Newman 2003). from where the term has sought its inspiration in recent machine learning literature (Steinhardt, 2023 Wei et al., 2022). Therein, emergence describes the scenario where rapid changes occur in a system's properties as some control parameter is varied. A range where the system's 's properties change relatively smoothly is called a phase, and a change of phase with change in the control variable is called a phase transition. A crucial step in studying emergence in phy sics is identifying an order parameter-4 measure that captures the formation of some specific regularity in the system such that the development of this regularity is what alters the system's 's properties and drives phase transition. For example, in Fig. [Tp, a system of particles transitions through phases (solid, liquid, gas) as the temperature is changed; the formation of crystalline structure with the decrease in temperature can be identified by analyzing the cond-orientation order parameter, while the liquid-to-ge transition can be described by a jump in particle density. We argue that we must similarly define order parameters for studying emergence in neural networks as well, i.c., we must develop evaluation measures that are focused towards detecting the learning of specific data regularities that are generally of use several downstream capabilities.
3

---

Published as a conference paper at ICLR 2025
(4)
(b)
[c]
ball
S -+ NP VP
Women
walk
VP
4 Adj
Laneyer
mat
NP 4
Doctir
jump
VP
NP
NP NP Conj. NP
VP V
Table
wooden
vintage
Adj
N
Adj
N
VP 4. VP Conj.
Sola
antiqque
Tall
man
slowly walked to small libeary
4 VP NP
Tall sandy walkerd enall library
Kichen
foldalale
Incompatible type!
Figure 2: Grammar and type constraints to define our formal language. (a) We use PCFG to define our language's grammar (shown rules are examples; see App. E33 for precise details). The grammar's terminals be populated by tokens from the language's vocabulary. (b) Akin to natural language, wherein properties of entity constrain sentences seen in a dataset corresponding to that entity, we define constraints (called type constraints) on our language that restrict which tokens can be seen together in sentence. These constraints map entities to descriptive or relative properties, hence restricting which descriptive adjectives and verbs are valid for an entity, (c) Once symbolic sentence is sampled from the grammar, we populate it with tokens from the language while respecting the type constraints. Training on string from this language in fact shows that the model deems sentences that do not respect type constraints to be extremely unlikely (see App. F22
surts-of-speech from English and yield symbolic sentences that can
3 FORMAL LANGUAGES AS AN EXPERIMENTAL SYSTEM FOR EMERGENCE
Having defined our perspective on emergence, we now define a toy experimental system that allows us to precisely study the concept in controlled setting. We note that our focus will be on emergence under data scaling in an online learning scenario (i.e., a sample is unlikely to be seen multiple times). To this end, we follow recent work on understanding language modeling and use formal languages to define our experimental setup (Allen-ZMe Zhu & Li, [023] Jain et al. [2023] Murty et al. 2023 Valvoda al. 2022 Liu al. 2023a 2022a). As discussed in detail next, the formal language we use in this work is (minimally) context-sensitive, with underlying syntactical rules defined using a probabilistic context-free grammar (PCFG) and sensxi--ensitivity enabled through posthoc rype constraints. The grammar and type constraints serve two regularities that underlie our language, and, as we show in Sec. 5 their learning bottlenecks learning of other, narrower capabilities.
Definition 2. (Grammar.) A PCFG, denoted G, is randomized process that generates strings using two sets of symbols: terminals (T) and non-terminals (NT). J. A string a is a sequence of terminals, ending with a special end-of-string symbol (EOS), e.g., a 1112... EOS. The grammar includes production rules (denoted R), which define how non-terminals can be expanded. Specifically, rule has the form A + a, where A E NT (the left- left-hand side) and a (the right-hand side) is a sequence of symbols from T U NT. The process begins with a special start symbol (S E NT). To generate string, the PCFG repeutedly applies production rules: a non-terminal is replaced by the sequence on the right-hand side of a randomly chosen rule with that non-terminal on the left-hand side. This process continues until all non terminemmaals are replaced by terminals, producing a string a. The set of all strings the grammar can generate is denoted E. A string a is called grammatical if E.
See Fig. (a) for a visualization and App. C.1 The terminal symbols used in our work include standard parts-of-speech from English, specifically: subjects, objects, verbs, adjectives, adverbs, conjunctions, determiners, and prepositions. Multiple short phrases can be combined together via conjunctions and verbs to form longer sentences (e.g., a verb can connect subject phrase and an object phrase). Overall, the grammar G yields symbolic strings that are solely comprised of parts of speech (see Fig. (a)); e.g., our grammar might yield symbolic string like ad i i ve sub ject adverb verb preposi i tion ad jectiiv ive object. We next map these strings to our language.
C.T for a more detailed treatment of PCFGs in general.
Let V denote the vocabulary of our language L. Each token E 1/ has part-of-speech ł part(v) associated with it. Thus, one can define a context-free language by simply sampling a symbolic string from G, and then replacing symbols therein with tokens from the vocabulary that match the sampled parts (e.g., a sub ject symbol may be replaced by the token man). For example, the example string above can be resolved as Tall man slowly walked to short building natural language is rich with constraints defined by the physical properties of an entity, which thereby restrict which tokens seen in the context of which other tokens, hence yielding context-sene sensiivise
However,
4

---

Published as a conference paper at ICLR 2025
For example, one does not expect to see sentence Tall telephone slowly walked to short building, since the entity telephone is neither expected to be tall nor the ability to walk. We develop an abstraction for such constraints by representing them as bipartite graph (see Fig. 2 (b,c)). In the following, we often use the term 'entities' to jointly refer to subjects and objects. We also use the term "descriptors' to refer adjectives that modify entities, reserving the term "adjectives" for ones that do not.
Definition 3. (Type Constraints Graph.) Let a property k be a binary variable; the set of all properties is denoted K. Properties can be either descriptive (used to define descriptors; e.g. tall) or relative (used define verbs; e.g, walk). A concept class C is defined via the set Ke denotes which properties are valid for that class. When the properties in Ke take values, we get an entity e from the class, denoted as e E The set of all possible entities denoted E. The type constraints graph G := (E, K, I) is a bipartite graph over entilies and properties in the language whose edges denote whether an entity e E E possesses property k E K.
that
As an example, consider the class of Humans, which includes entities connected to properties like etc.; an entity from Humans will be assigned a subset of these properties. When sampling sentences from our formal language, the type constraints will restrict which tokens can be seen together, i.c., which descriptors and verbs go with an entity, hence yielding context- sensitivity and making L probabilistic context-sensitive language. Given two randomly sampled entities from the same class, they can be expected to share a subset of properties, giving a signal to the model trained L that these entities are related (i.e., they belong to the same class).
tall,
LEARNING TASKS AND EXPERIMENTAL SETUP
Having described our language L, now briefly discuss our experimen- tal setup (see App. E for details). We train GPT architecture model (An- drej Karpathy (2033) with the stan- dard autoregressive language model- ing objective. Data is sampled "on- line", i.e., we sample a fresh batch of strings every iteration from L. Un- less mentioned otherwise, L is con- stituted of [B| 900 entities and K|| = 18000 properties, equally and disjointly distributed over |C| 10 classes, and with edges connecting en- tities to p- 0.15 fraction valid properties of a class in uniformly random manner; results ablating these settings are in [pp. Before being fed into the model for training or evaluation, strings sampled from the language are restructured into format that enables the specification of particular tasks (see Fig.
Tank
Ieput
Output
Free:
[nall]
"tall man slowly walked to small library""
Unscramble:
[lbrary, walked,
slowy) "tall man slowly walked small library"
Conditional: Iman, wakked]
"tall man slowly walked to small library."
Task definitions. Our model is trained and evalu- ated on three types of tasks. (i) Free generation: the model generates sentences with correct grammar. (ii) Unscrambling: the model is provided with a set of words and must reorder them to form valid sentences. (iii) Conditional generation: model is given set of entities or properties and must gen- erate valid sentences using them. Note that examples in the figure are merely indicative. See App. C. for details.
Figure 3:
Specifically, we train the model to learn the following tasks with 80/10/109/ splits.
Free generation: Produce a valid string, i.e., one that respects the grammar and type constraints. Unscrambling: A string is sampled from C and randomly permuted; the model is expected to unscramble it. This task is known to show sudden learning in LLMs (Wei et al. (022).
Conditional Generation: set of tokens corresponding to entities or properties are shown to the model, which is expected to generate string combining these tokens in valid manner.
Evaluation Protocols.
Given an input .r, which may correspond to any of the three tasks above, if its input is
denote the model output as f(x) Let 1.) be an indicator variable that evaluates logically true. We often decompose evaluations according to strings of two types: (i) descriptive, i.e. ones that describe that an entity possesses a descriptive property, and (ii) relative, i.e., ones that demonstrate subject, object, and verb can be combined to create a valid sentence. We track several metrics throughout training to avoid confounding from discontinuous scores (Schaeffer et al. 2023).
Grammaticality/Type Check. Grammaticality involves checking whether model output follows the underlying grammar G, ie.. 1(f(x) Σ); several other evaluations stress-testing how ac- curately the model learns the grammar, e.g., by assessing likelihoods of invalid sentences (see App. E3 R.5). Type checks involve first extracting subjects, objects, and properties from the
5

---

Published as a conference paper at ICLR 2025
sentence and then evaluating whether this set of tokens is allowed in the context of each other. We decompose type checks as descriptive (do entities and descriptors match), relative (do subject, object, and verb match), and all (product of all constraints, including adjectives and adverbs). Exact Match / Per Token Accuracy. Used for evaluating unscrambling. Assume the ground-truth unscrambled sentence y has tokens. We compare whether the model output exactly matches the ground-truth (II (1: = fx)))) or the per-token match ratio (1/) E' (1i = f())))
Conditions Satisfied. Used for evaluating conditional generation. If the model is expected to produce sentence with m conditioning tokens (Ve, ..... Vem. I. we analyze how many of those tokens are present in [(x), i.e., we evaluate 1/m > [ E fz)).
Average Probability of Valid Tokens. Used for evaluating descriptive type constraints in free generation and unscrambling. Specifically, we sample a sentence from L that remarks on an entity possessing property (i.e., a descriptive sentence), and then evaluate the probability of the property being the next token when this sentence is inputted to the model. For example, let (rr where -- denotes the sentence up to the last token and f(z)1 denotes the first token predicted by the model.
x The fi fire was large. We evaluate Pr (1 (f()))
Other Evaluations. We perform several other evaluations, e.g., analyzing likelihoods of sentences that do not follow grammar or type constraints to check how well the model follows our language; comparing the distribution of lengths and parse tree depth for model's generations with the language's s; analyzing grammaticality and type check accuracy for unscrambling and conditional generation; rank of property predictions; and the evolution of attention maps across time. See App. Ffro these results.
RESULTS: EMERGENT CAPABILITIES IN FORMAL LANGUAGE LEARNING
We now evaluate (i) whether our setup demonstrates emergence (see Def. D. and (ii) whether we can extract insights into the mechanisms of what leads to emergence (all results are averaged over 3 seeds). While experiments below are for specific setup, in App. F we show that our claims consistently generalize to an extremely broad array of setups and metries. In the following, we often use the terms "phase" and "phase change"; see discussion around Def. T for context these terms.
5.1 PHASES OF LANGUAGE AND CAPABILITIES ACQUISITION
We plot the model's performance as function of training iterations. Since we are in an online learning, constant stepsize setting, this analysis corresponds to studying the effects of data scaling. Results are reported in Fig. 4 and show there are three phases to the learning dynamies.
Phase 1: Grammar acquisition. We find the model first learns to produce grammatically correct sentences, as measured by the grammaticality measure defined in Sec. This process is relatively rapid, as we see the model starts generating grammatically accurate sentences in short period of approximately 100 iterations; attention heads also rapidly evolve and reflect the parse structure of a sentence (see App. (F5) In this regime, however, the narrower tasks of unserambling and conditional generation exhibit poor performance. However, precisely when grammaticality improves, we find that per-token accuracy starts to improve. This indicates that the model learning broad regularity underlying the data (i.e., grammar) impacts learning of narrower capabilities.
Phase Acquisition of relative type constraints. At around 1000 iterations, we find there is a sudden increase in the model's performance on relative types from essentially zero to perfect accuracy; precisely at this point, we find the loss for all tasks, especially free generation, shows a sudden drop. Interestingly, we find this sudden improvement occurs precisely at the point where the model reaches its maximum performance on grammaticality for the first time. That is, as soon as the first regularity underlying the data is learned, the model rapidly learns the next relevant regularity of relative type constraints. Improvement occurs in descriptive constraints as well (and hence the overall Type Check performance), but hovers around slightly above 0.1. This is expected, since with |C| = 10 classes, if model produces grammatically correct sentences, it will achieve a random performance of 1/ICI 0.1 descriptive type checks. This also implies that the model is primarily relying on its syntactical knowledge and does not respect descriptive type constraints much.
During this phase. we that shortly after the phase change, there is sudden increase in performance for both unscrambling and conditional generation, across all metrics. These tasks' losses also show another loss drop occurs this point; though the drop seems smoother in the total loss, likely due

---

Published as a conference paper at ICLR 2025
(a)
(b)
(c)
1.00
Eeact Match
Condh, aeti
Gronnor Tape
9.8-
624
Me
20
Eayg Nate
Perthann Are
25-
0.0
0.00
6.89
10000
0.00
30
16
13
15x
15
10
15
30
(d)
Total
Free generation
Unscrambling
Cond. generation
00
9.35
3.M
0.50
0--
4.
0.30
(e)
Type (Desc.)
Unscramble (Desc.)
Type Check (Rell
Unscramb (Rel.)
5.50
seed 0
0.3
02
0.4
631
615
0.0
0.0
0.81
150
32a
377
12a 30'
15'
201
lterations
terations
lterations
Iterations
Figure 4: Learning of regularities in the data drives emergent capabilities. For detailed discus- sion, see main text. (a) Grammaticality and Type Check evaluations as function of iterations (or, equivalently, data). We see phases in the learning dynamics corresponding to emergent acquisition of regularities underlying our language: grammar, relative type constraints, and descriptive type constraints, shaded gray, pink, and green respectively. (b, e) Performance on Unscrambling and Conditional Generation. After a slight delay from phase boundaries, we see sudden improvements in the performance of individual tasks. (d) Learning curves. Loss also shows sudden changes at phase boundaries corresponding to the learning of regularities present in the data. (e) Performance on descriptive/relative sentences. Decomposing by sentence type, we find a sublinear growth in descriptive type checks drives performance boost on descriptive sentences for the unscrambling task.
to averaging effects (Michaud al. 2023). As shown in Fig. 4.. we find that this performance improvement is driven by sentences that require primarily correctness of grammar and relative type constraints, i.e., knowledge of which descriptors are associated with an entity is not necessary to perform well on these sentences. This also explains the loss drop seen in Fig, once grammar and relative type constraints are learned, the model learns to use them solve inputs that do not require knowledge of descriptive properties, leading to sudden improvement in both loss and accuracy.
Phase 3: Learning of descriptive type constraints, During Phase 2, we find that the model's per- formance on descriptive type checks witnesses minimal improvement. However, as training proceeds, the model enters a third phase at whose boundary we see sudden change of slope from a saturation region to approximately proportional growth in the performance of descriptive type checks with log-amount of data/iterations (i.e., sublinear growth). With a slight delay, we see a similar effect kicks in for the unserambling and condition generation tasks as well, which start to show approximately linear improvement with log- amount of data/iterations. Zooming in at this point (see inset plots in Fig. we see there is in fact small, but nevertheless noticeable. loss drop in the unscrambling and condition generation tasks. We emphasize that since the model has seen merely an order of 10 iterations up to this point, if we assume the model can perfectly learn in only few observations that some entity and a property can be seen together in a sentence, then our experimental setting can on average see only up to 15% performance (which matches the observed performance) and 20% at best (see App. E. the argument is that only a subset of pairs is shown during training, restricting maximum performance). However, as the model enters and progresses through the third phase, it shows much larger rate of improvement and reaches ~30-35% performance, indicating it is generalizing beyond the pairs of entities and properties it has seen together during training. If the model were simply relying on memorized knowledge, the observed performance would be infeasible.
We thus claim that the model is implicitly inferring, based on the regularity of type constraints that underlies our data, which properties and entities constitute valid context. This suggests memorization effect is at play during Phase 2, and the end of this phase corresponds to a transition from memorizing to generalizing solution.
7

---

Published as a conference paper at ICLR 2025
14800
18000 19600
21203
24420
27683
30500
34000
37200
16400
22503
26030
29209
32400
35600
38800
Type Check (Desc.)
Unsoramble (Desc.)
Type Check (Rol.)
Unscramble (Ral.)
0.25
1.0
0.75-
0.20
3,4
11
0.20
5.0
3.0
3.0
167
135 107
10P
139
337
104
169 1.07
144
167
Iterations
Iterations
Iterations
Iterations
Figure 5: Effect of Scaling number of descriptive properties. Scaling descriptive properties in our language, we find relative type checks and unscrambling performance for relative sentences are essentially unaffected by the number of properties. Meanwhile, both descriptive type checks and unscrambling performance for descriptive sentences show a change in performance and delay in transition points. Interestingly, we find the geometry of performance curves extremely consistent; for descriptive type checks, this geometry indicates a memorization to generalization picture.
5.2 EFFECT OF NUMBER OF DESCRIPTIVE PROPERTIES ON LANGUAGE ACQUISITION
Given the above picture of model's learning dynamics, we next ask how the phase boundaries change with an increase in the number of properties |K (see Fig. 5 We intentionally scale only the number of descriptive properties and hypothesize the learning of both grammar and relative type constraints to not be affected by this change. We relegate grammar learning to appendix (see App. F.2. which, expected, is not affected by |K] since it is an entirely independent data-regularity from type constraints. However, we see that even relative type constraints' learning is not affected by the increase in descriptive properties, indicating the model deems them (jutifiably) to be independent regularities. Focusing on descriptive type constraints then, we see performance curves for descriptive type checks and unscrambling performance on descriptive sentences are indeed affected, achieving higher values for fewer properties (i.e., the easier task). We further make two more interesting observations. (i) The point of transition from memorization to generalization is delayed as we increase the number of properties. This is most prominently seen in the delay in the transition point where the ability to unscramble descriptive sentences emerges. (ii) We find the geometry of these performance curves are extremely similar to the geometry we observed for our buse setting studied in Sec. 5.7 indicating despite the increase in difficulty of the task, the same learning dynamics are at play. We devote the next section to formulate hypothesis justifying these observations.
6 EMERGENCE AS PERCOLATION
(a)
(b)
WA
30090
We next propose a framework for modeling the emergence of capabilities that require model to compose unseen entities and descriptive prop- erties, e.g., learning descriptive type constraints, which, beyond allowing a model to produce accu- rate free generations, will aid with narrower tasks like conditional generation and unscrambling. We argue the relevant ragulrrgyl to analyze for this purpose is the concept class: if a model un- derstands what entities and properties belong to concept class, regardless of whether they have been seen together in a string, it will deem their co-occurrence valid. We thus develop abstrac- tion for concept classes as bipartite graphs, casting their learning problem of percolation such graphs (see also App. D.I.
21.
Figure 6: Casting the ability to compose un- seen entities and properties as percolation on a bipartite graph. (a) When only a fraction of the concept classes are included in the dataset and the edge density is low, nodes (e.g., en- tities and properties) form many disconnected clusters, indicated by different colors (left). As more concept classes are added (dashed edges) to the bipartite graph. the small clusters begin to merge (middle). With a sufficient number of edges, a macroscopic number of nodes be- come connected, forming a single cluster (right). (b) Our formalism establishes this transition as second-order phase transition, where the size of the largest cluster increases non-linearly as the fraction of connected node pairs is scaled. Shown curves are from simulations on bipartite graphs with the number of nodes equal to the number of entities and properties in our formal language experiments (see Sec. oor App. B
6.1 MATRIX REPRESENTATION OF DATA
Recall that concept class is defined as a set of entities that are expected to have shared properties (see Def. 3. The question is whether upon sub- sampling pairs of entities and properties from a concept class, can the model learn that, in fact, all
8

---

Published as a conference paper at ICLR 2025
pairs of entities and properties are valid and compose the concept class. For instance, in the case of concept class such as human, the set of entities can include humans with different genders (e.g. man) entities such
as well as for the human concept class will be, for example, walk, k, jump, tall. 1. A man, being human, n, is expected to have all these properties, although strings specifying these properties for 1 lawyer may be rare or even absent in the training data. We are interested in the case where the data, such as strings, includes examples of these pairs of entities and properties. We can represent this by a matrix whose rows and columns represent the entities and the properties, and the matrix values indicate the quantity or density of data available for each composition, e.g., an entiiy-deseriptor pairing.
lawyer (see Fig. 2 The corresponding properties
Definition 4. (Concept Density Matrix.) Let D be an |E] x K matrix with real-valued entries between O and I, inclusive. Each entry DeE represents the density for the entity and property pair (e, k) (e.g, the amount of data that represents the specific composition), where E {1,..., [E]] and E [1,..,,Kk [K]} are the indices of the entities and properties, respectively.
For example, consider the case where there are three values of entities and properties (EE) K| = 3), with entities (rows) being [Man, Lawyer, Tel Telephone, ), and properties (columns) being [Walk. Stoic, Ring]. The corresponding D can be: A common composition such Man walking will lead to a value of at the intersection of Man and Walk, i.... Doo = 1, where Dig denotes element row-i and column-jj. Conversely, highly unlikely composition like Lawyer r ringi i ng will be absent in the dataset, and will be represented by a zero at the respective matrix position, i.e., D12 = O. We can also assume for example that Man ringing ng or Telephone walking are rare, which yields D13 D31 = O. We next introduce the concept propagation matrix to model the inference of novel entity- feature combinations from the incomplete data represented in D.
Definition 5. Concept Propagation Matrix. An n-th order concept propagation matrix (n 2 0) is defined as T(x) (DD")" Ct D, where C == DDT.
The concept propagation matrix can be intuitively understood using a bipartite graph, as shown in Fa. A bipartite graph in this case is a sub-graph of the type constraints graph (see Def. and and
Fig. 2) where one set of nodes represents entities while the other represents properties, and edges indicate the presence of entity-feature pairings in the training data. The strength of connectivity of the graph directly corresponds to the values in the concept composition propagation matrix, T(,), Specifically, if two concepts are connected by a path of minimal length 2k + (i.e., the shortest path between them alternates between the two sets times), the corresponding entry in T(n) becomes non-zero only for 2 k. That is, the number of propagation steps n required for the object and feature pair to be associated is determined by the minimal number of hops needed to connect the two nodes in the graph. Conversely, if two nodes belong to disconneeted regions of the graph, their composition remains fundamentally unlearnable, regardless of the order of propagation. This is reflected by the corresponding entry in (())) remaining zero for all n. In the bipartite graph, this amounts to having two distinct clusters that are connected within themselves but not across each other. For example, in the case where the concepts represented by the first and third rows belong to disconnected regions of the graph, and consequently, their composition (e.g., Lawyer zinging) cannot be achieved even after an infinite number of hops between nodes. We call such a situation learning of a concept class: the system understands that Man and Laywer r are both humans, whereas Telephone is not. Our experiments show that the model deems sentences composing entities and properties from incorrect classes to be much less likely than the correct ones (see Fig. F.3 i.c., the model indeed learns the structure of concept classes.
6.2 PERCOLATION TRANSITION ON DESCRIPTIVE CONSTRAINTS
Using the bipartite graph framework, the generalization, or the learning of the concept class, can be defined as the situation where large cluster of entity-property connected pairs arises despite the sparse concept density matrix. A critical aspect to examine is the proportion of the inference matrix values where ( is non-zero, out of the total possible pairs EE| x KK] This particular scenario aligns with the bond percolation problem on a bipartite graph. In bond percolation, we investigate how the largest connected cluster's size varies with the probability p of each edge (bond) being present. In a typical setting, there exists a critical threshold value, p = Pc, called the percolation threshold. Below this threshold (p < Pe), the graph typically exhibits a disconnected phase characterized by the absence of extensively connected clusters, with most nodes either isolated or part of smaller clusters. Above this threshold (p > pc), the graph transitions to a connected phase, significantly increasing

---

Published as a conference paper at ICLR 2025
14800
18200
21200
24400
27000
32800
34000
37200
16400
19000
22800
28000
29200
32400
35600
38000
Avg. Prob. (Freegen) 18)-5 Ty. Check (Desc.) x [K]S
Avg. Prob. (Unscmb) x 1A7 Ex. Match (Unscmbb |K(20
700
40-
93-
800
0.3-
502
30-
02-
0.2-
25
402
01
0.1-
20
100
0.0
30:
10"0
10
10-3
10"2
Iterations/ / [K]S5
Iterations/ / |K70.
Iterations/ / 1K7Ls
Iterations / [K]
Figure 7: Scaling of point of emergence matches with our theory. We replot the result from Fig. S by rescaling the x-axis with a power of the number of descriptive properties; see App. App. for further discussion on the intuition underlying this visualization. For Average probability of generating valid descriptive property given some object in context under free generation and descriptive type check accuracy, we see 0.5 exponent scaling yields a collapse of the transition point-this matches the toy model of percolation posited in Sec. Sec.[6.2 We also see a very clear scaling of the point where the ability to unseramble descriptive sentences starts to emerge, but with an exponent of 1.5.
the likelihood of a vast connected component spanning a large portion of the graph. This shift from a predominantly disconnected state one with a macroscopic cluster is defining characteristic of the percolation process, and this transition sharpens as the number of components in the system increases. (see Fig. 6 for schematic). In a setting where connecting edges are selected randomly on the graph with probability p. the percolation threshold is obtained as Pe / E K| for large [E]
and [K] (see App. D.2 for a derivation). This means that when around / [E] ||| edges are connected, there is a qualitative change in the growth of the cluster size. For p Pe. the number of nodes included in the connected cluster becomes macroscopic, i.e., the probability a randomly selected pair of entity and property are connected becomes finite. We posit that the percolation threshold corresponds to the point at which our Transformer generalizes from the sparse learning of pairs to a complete representation of concept classes. Since increasing the iterations through online learning should amount to increasing (i.e., seeing more combinations in data), the iteration at which the transition occurs in the model performance should be proportional to E When the number of seen pairs surpasses this threshold, the model can infer novel compositions, even for peiit-proopety pairs not explicitly present in the training data.
We next check whether the theoretically posited scaling manifests in our experiments. Specifically, we plot again the various performances of the model as a function of iterations divided by the square root of the number of properties (i.e., number of entities is kept constant). See Fig. 7 for results. We find that indeed there is growth trend in the descriptive type check metric and the average probability scores of free generation of descriptive sentences that occur at iterations proportional to VKK. This is in contrast to the first large growth that is observed in these evaluations, which seems to be occurring at iteration numbers that do not depend on |K| (see Fig. and Fig. 53). likely because this step corresponds to the point where the model learns about syntax, which requires a constant amount of data irrespective of the number of properties (see Fig. [8]. We also analyzed the scaling of the transition point for the narrower task of unscrambling upon change in the number of properties.
Here, we found a different scaling of |x|3/2_ While we leave explaining this scaling for future work, since the task involves the composition of entities and properties, we expect transition and scaling effect to occur for it as well; however, learning the precise circuit to perform unscrambling over the learned grammar and type constraints will yield delay (as was seen in experiments) that likely has some interaction with the complexity of the language.
CONCLUSION
In this work, we propose phenomenological definition for emergence that implicates learning of general regularities underlying the data process as the source of rapid performance improvements on narrower tasks. We then use formal language that involves two precisely defined regularities grammar and type constraints-ant a set of narrowly defined tasks on its strings. We define "order parameters" for these regularities and find (i) precise phases in the learning dynamics of Transformer trained on the language and (ii) the model suddenly acquiring capabilities corresponding to the narrower scope tasks close to said phases' boundaries. To explain these results, propose model that analogizes learning of type constraints to the problem of graph percolation, finding a strong qualitative match with this hypothesis.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors thank Intelligent Systems group at Harvard, especially Maya Okawa, Core Francisco Park, and Leni Shor for feedback on the project and contributions predecessors of this work. ESL thanks Gautam Reddy, Naomi Saphra, Pulkit Gopalani, Wei Hu, and Yonatav Belinkov for fruitful conversations. ESL's time University of Michigan was supported by NSF under award CNS- 2211509 and at Harvard by the CBS-NTT Physics of Intelligence program. KK acknowledges support from JSPS KAKENHI Grant Numbers JP JP19H05795, JP IP19H05275, JP21H01007, and JP23H00095.
REFERENCES
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, .... and Andy Zeng. Do As I Can and Not As I Say: Grounding Language in Robotic Affordances. In arXiv preprint wrXiv:2204.01691 2022.
Zeyuan Allen Ahl and Yuanzhi Li. Physics of Language Models: Part arXiv preprint 1.XXi:23305.3377.7 2023.
Context-Free Grammar.
Shun-Ichi Amari. A universal theorem on learning curves. Neural networks, 6(2):161-166, 1993.
Philip W Anderson. More is different: Broken symmetry and the nature of the hierarchical structure of science. Science, 177(4047):393-396, 1972.
Andrej Karpathy. nanoGPT, 2023.
Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent EI Shafey, Yanping Huang, Kathy Meier-Hellstern, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin Robinson, .... and Yonghui Wu. PaLM 2 Technical Report, 2023.
Anthropic. Introducing Claude, 2023, https: http::/www..ttttt wtwp:/tt...pp...ccc// cttp:/i..coo..ccoooooomm.....t.t index/
Introducing-claude Accessed on: June 21, 2023.
Sanjeev Arora and Anirudh Goyal. theory for emergence of complex skills in language models. arXiv preprint arXiv:2307.15988 2023.
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang, Hidden progress in deep learning: SGD learns parities near the computational limit. Advances Neural Information Processing Systems, 35:21 35:21750-21764 2022.
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430. Pmlr, 2023.
Steven Bird, Ewan Klein, and Edward Loper. Natural language processing with Python: analyzing text with the natural language toolkit. O' O'Reilly Media, Inc.", 2009.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the Shenik-Chervonenniss dimension. Journal of the ACM (JACM), 36(4):929 1989.
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quiney Davis. Dora Demszky, ... and Percy Liang. On the Opportunities and Risks of Foun- dation Models, jul 2022. URL / [es].
http//awivv.ggg..o....oo... abs
2108. 07258 arXiv:2108.0725
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 532-541, 2021.
11

---

Published as a conference paper at ICLR 2025
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:
1877-1901, 2020. URL
1457c0d6bfcb4996 www.aac14222
Francesco Cagnetta and Matthieu Wyart. Towards theory of how the structure of language is acquired by deep neural networks. arXiv preprint arXiv:2406.00045. 2024.
Angelica Chen, Ravid Shwartz-Ziv, Kyunghyun Cho, Matthew L. Leavitt, and Naomi Saphra.
Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs. In The Twelfth International Conference on Learning Representations, 2024. URL https?
//openreview net. Lteeee/oooommm1d005PP000
Noam Chomsky. Three models for the description of language. IRE Transactions information theory, 233):113-124, 1956.
Reuven Cohen, Daniel Ben-Avraham, and Shlomo Havlin. Percolation critical exponents in scale-free networks. Physical Review E, 66(3):0361 13, 2002.
Michael Collins. Probabilistic context-free grammars (pefgs), Lecture Notes, 2013.
Hugo Cui, Freya Behrens, Florent Krzakala, and Lenka Zdeborová. A phase transition between positional and semantic learning in solvable model of dot-product attention. arXiv preprint arXiv:2402.03902, 2024.
Danny Driess, Fei Xia, Mehdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. Palm-e: An embodied multimodal language model. arXiv preprint arXiv:2303.0333 2023.
Zhengxiao Du, Aohan Zeng, Yuxiao Dong, and Jie Tang. Understanding emergent abilities of language models from the loss perspective. arXiv preprint 24Xi::2403.15796, 2024.
Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Pareto frontiers in neural feature learning: Data, compute, width, and luck. arXiv preprint arXiv:2309.0380 2023.
Benjamin Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains. arXiv preprint 24Xi:24022.10044 2024.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dddds Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, and Chris Olah. A Mathematical Framework for Transformer Cireuits. Transformer Circuits Thread, 2021. https:/ttansSommeeccrruiit http://ii..u///01//foooooooo//nd
EU Council. Proposal for a Regulation of the European Parliament and of the Council on Artificial Intelligence (Artificial Intelligence Act), 2024. https:///eet http://aaaaccooo 1 lium. europa. eu/
S doc/ foc//docuentt/ SSeet//T-5556 2014- - a/dd
Dan Friedman, Alexander Wettig, and Danqi Chen. Learning Transformer Programs. arXiv preprint
arXiv:2306.01128, 2023.
Gemini Team. Gemini: family of highly capable multimodal models. arXiv preprint arXiv:2312.11800 2023.
Shreyas Gokhale. The semantic landscape paradigm for neural networks. arXiv preprint arXiv:2307.09550, 2023.
Pulkit Gopalani, Ekdeep Singh Lubana, and Wei Hu, Abrupt learning in transformers: A case study matrix completion. arXiv preprint 2rXiv:2410.22244 2024.
David Haussler, H Sebastian Seung, Michael Kearns, and Naftali Tishby. Rigorous learning curve bounds from statistical mechanics. In Proceedings of the seventh annual conference on Computa- fional learning theory, pp. 76-87 87, 1994.
12

---

Published as a conference paper at ICLR 2025
Tianyu He, Darshil Doshi, Aritra Das, and Andrey Gromov. Learning to grok: Emergence of in-context learning and skill composition in modular arithmetic tasks. arXiv preprint arXiv:2406.02550, 2024.
David T Hoffmann, Simon Schrodi, Nadine Behrmann, Volker Fischer, and Thomas Brox. Eureka- moments in transformers: Multi-step tasks reveal softmax induced optimization problems. arXiv preprint arXiv:2310. 2023.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. An empirical analysis of compute-optimal large language model training. Advances in Neural Information Processing Systems, 35:30016-30030, 2022.
Dieuwke Hupkes, Verma Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Samyak Jain, Robert Kirk, Ekdeep Singh Lubana, Robert P. Dick, Hidenori Tanaka, Edward Grefen- stette, Tim Rocktäschel, and David Scott Krueger. Mechanistically analyzing the effects of fine-tuning on procedurally defined tasks, 2023.
Margot Kaminski. Regulating the Risks of Al. Boston University Law Review, 103:1347, 2023.
Louis Kirsch, James Harrison, Jascha Sohl-Dickstein, and Luke Metz. General-purpose in-context learning by meta-learning transformers. arXiv preprint arXiv:2212.044455 2022.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXi::2210. 2022a, 2022a.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing Attention Glitches with Flip-Flop Language Modeling. arXiv preprint 2rXiv:2306.000% 2023a.
Ziming Liu, Ouail Kitouni, Niklas Nolte, Eric J. Michaud, Max Tegmark, and Mike Williams. Towards Understanding Grokking: An Effective Theory of Representation Learning, October 2022b.
Ziming Liu, Eric J. Michaud, and Max Tegmark. Omnigrok: Grokking Beyond Algorithmic Data, March 2023b.
Sheng Lu, Irina Bigoulaeva, Rachneet Sachdeva, Harish Tayyar Madabushi, and Iryna Gurevych. Are Emergent Abilities in Large Language Models just In-Context Learning? arXiv preprint arXiv:2309.01800 008,,,99,,,,,,, 2023.
Yue M Lu, Mary Letey, Jacob A Zavatone- Veth, Anindita Maiti, and Cengiz Pehlevan. Asymptotic theory of in-context learning by linear attention. arXiv preprint arXiv:2405.1172 2024.
Alexandra Sasha Luccioni and Anna Rogers. Mind your language (model): Fact-checking Ilms and their role nlp research and practice. arXiv preprint arXiv:2308 07120, 2023.
William Merrill, Nikolaos Tsilivis, and Aman Shukla. A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks. arXiv preprint arXiv:2303. 1873, 2023.
Eric J Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. arXiv preprint 230.:2333333006 2023.
Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D Manning. Grokking of hierarchical structure in vanilla transformers. arXiv preprint arXiv:2305./888 2023.
Yoonsoo Nam, Nayara Fonseca, Seok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws. arXiv preprint arXiv:2404.17563 2024.
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. The Eleventh International Conference on Learning Representations, sep 2022.
http::/pppe/r//eee ew net ntt/ 6= 9XF
13

---

Published as a conference paper at ICLR 2025
Neel Nanda, Andrew Lee, and Martin Wattenberg. Emergent Linear Representations in World Models of Supervised Sequence Models, sep 2023. URL http://arx..v.rr///ba
2309. 00941 arXiv:2309.0094 [cs].
M. E. Newman. The Structure and Function of Complex Networks. SIAM Review, 45(2):167-256. January 2003. ISSN 0036-1445, 1095-7200.
Mark EJ Newman, Steven H Strogatz, and Duncan Watts. Random graphs with arbitrary degree distributions and their applications. Physical review E, 64(2):0261 18, 2001.
NIST. Artificial Intelligence Risk Management Framework (AI RMF 1.0), 2023.
Maya Okawa, Ekdeep Singh Lubana, Robert P Dick, and Hidenori Tanaka. Compositional abil- ities emerge multiplicativel: Exploring diffusion models on synthetic task. arXiv preprint trxiv:2310.09336. 2023.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, and Chris Olah. In-context Learning and Induction Heads. Transformer Circuits Thread, 2022.
OpenAL. Gpt-4, 2023. 2023.
attpss//openaal.com//reeeeeeeeee
Accessed on: June 21,
The White House OSTP. Blueprint for an Al Bill of Rights, 2023.
Alexander Pan, Kush Bhatia, and Jacob Steinhardt. The effects of reward misspecification: Mapping and mitigating misaligned models. arXiv preprint arXiv:2201.03544 2022.
Core Francisco Park, Maya Okawa, Andrew Lee, Ekdeep Singh Lubana, and Hidenori Tanaka. Emergence of hidden capabilities: Exploring learning dynamics in concept space. arXiv preprint arXiv:2406. / 19370, 2024.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gen- cralization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177, 2022.
Gautam Reddy. The mechanistic basis of data dependence and abrupt learning in in-context classification task. arXiv preprint arXiv:2312.03002, 2023.
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of Large Language Models mirage? arXiv preprint arXiv:2304.15004 2023.
Rylan Schaeffer, Hailey Schoelkopf, Brando Miranda, Gabriel Mukobi, Varun Madan, Adam Ibrahim, Herbie Bradley, Stella Biderman, and Sanmi Koyejo. Why has predicting downstream capabilities of frontier ai models with scale remained elusive? arXiv preprint 240.:22406.043// 2024.
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to tools. Advances in Neural Information Processing Systems, 36, 2024.
Hyunjune Sebastian Seung, Haim Sompolinsky, and Naftali Tishby. Statistical mechanics of learning from examples. Physical review A, 45(8):6056, 1992.
Aaditya Singh, Ted Moskovitz, Felix Hill, Stephanic CY Chan, and Andrew M Saxe. What needs to go right for induction head? mechanistic study of in-context learning circuits and their formation. arXiv preprint axXiv:2404.07122, 2024.
Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1)277-29, 1996.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro. Aditya Gupta, Adrià Murria--Alnnse et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206. 04615, 2022.
14

---

Published as a conference paper at ICLR 2025
Jacob Steinhardt. Emergent Deception and Emergent Optimization, feb 2023. URL https //bounded-regzet.. iomoost.io/emn htt.:///wm......eeceeeeeeoooooaa
Curt Tigges, Michael Hanna, Qinan Yu, and Stella Biderman. Llm circuit analyses are consistent across training and scale. arXiv preprint wrXiv22477.0822) 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fermandes, Jeremy Fu, Wenyin Fu, ... and Thomas Scialom. Llama 2: Open Foundation and Fine-Tuned Chat Models, 2023.
Josef Valvoda, Naomi Saphra, Jonathan Rawski, Adina Williams, and Ryan Cotterell. Benchmarking compositionality with formal languages. arXiv preprint arXiv:2208.08// 2022.
Tom Viering and Marco Loog. The shape of learning curves: a review, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Timothy LH Watkin, Albrecht Rau, and Michael Biehl. The statistical mechanics of learning rule. Reviews of Modern Physics, 65(2):499, 1993.
Jason Wei. 137 emergent abilities of large language models, 2022. htttps://wet jasonwei net/blog/ htt:///mrrggnccee Accessed on: October 20, 2023.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206. 220.00082...00. 2022.
Kaiyue Wen, Yuchen Li, Bingbin Liu, and Andrej Risteski. (Un)interpretabbiity of Transformers: case study with Dyck grammars. 2023.
Dingli Yu, Simran Kaur, Arushi Gupta, Jonah Brown-Cohen, Anirudh Goyal, and Sanjeev Arora. Skill-Mix: A flexible and expandable family of evaluations for Al models. arXiv preprint arXiv:2310. 17567, 2023.
Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfci Yang, Burcu Karagol Ayan, et al. Scaling autoregressive models for content- rich text-to-image generation. arXiv preprint arXiv:2206. 10789, 2(3):5, 2022.
Bojan Žunkovië and Enej Ilievski. Grokking phase transitions in learning local rules with gradient descent, October 2022.
15

---

Published as a conference paper at ICLR 2025
A FURTHER DISCUSSION AND FUTURE WORK
In this work, take inspiration from other fields (e.g., physics and complex systems) and propose a phenomenological definition for emergence of capabilities in neural networks. Specifically, the definition argues that the point of emergence, the model learns general regularities underlying the data-generating process which are instrumental to the learning of specific, narrower capabilities; acquisition of such regularities then leads sudden performance improvement on several tasks (often with some delay). While relatively informal, this definition brings the notion of emergence in the context of neural networks closer to its meaning in physics, wherein the formation of systematic regularities is known to drive phase changes that involve sudden changes in the system's 's properties. Characterizing these phase changes requires hypothesizing what the regularity is, and defining an "order parameter" that can help gauge its change. Drawing on this definition and perspective, we then propose an experimental setup that involves learning of a formal language with two precisely defined regularities in the data-grat grammar and type constraints (what properties are valid in the context of what entities) and a set of narrowly defined tasks. Defining order parameters for these regularities (grammaticality and type checks), we find there indeed are phases in the model's learning dynamics, and the model suddenly acquires capabilities corresponding to the narrower scope tasks (unscrambling and conditional generation) close to these phase boundaries. Interestingly, the learning curves show rather distinct geometry that remains consistent as we alter the number of properties in our language.
To explain these results, we propose a model that analogizes learning of type constraints in the formal language learning task to the problem of graph percolation. Drawing on the theory of percolation on bipartite graphs, which shows phase transitions in the formation of connected components on graph, we argue this problem similar to learning of concepts classes or type constraints in our setting, and hence should show scaling of the point of emergence where the model starts to follow descriptive type constraints that is of the order of /IE KK] Our results show a strong qualitative match with this hypothesis. We also find an extremely clean scaling for other tasks' transition point, e.g., for unscrambling's 's results on descriptive sentences; explaining these results is left for future work.
While our goal in this work was primarily demonstrative, i.e., to develop bridge with other fields studying emergence, we believe several exciting avenues now open up. For example, given that the whole point of the theory of phase transitions is that we can predict the point of emergence, can we draw on this rich literature propose models for explaining and predicting emergent capabilities in neural networks? Can we go beyond the toy task of formal language learning studied in this work and analyze more naturalistic setting? For example, can identify data-regularities underlying emergent capabilities in open-source models, e.g., Pythia checkpoints (Biderman et al. (202)), and demonstrate that our proposed perspective enables prediction of when capabilities emerge in L.LMs? To begin, we can perhaps focus on capabilities that require similar knowledge acquisition and its compositional generalization on downstream task.
B RELATED WORK
Explaining emergence. Focusing on the sudden learning characteristic of emergent capabilities, few recent works have tried to explain the factors driving this phenomenon. For example, compositionality has been implicated for having a "multiplicative" effect on model's s performance, where the argument is that a model cannot perform well on compositional task until the abilities needed to perform individual tasks involved in that composition are acquired (Okawa et al. 2023 Arora & Goyal 2023
Yu et al. 2023 Srivastava et al. 2022 Wei et al.] 2022, Hoffmann et al.) 20222 Gokhale 2023):
when they are acquired, performance suddenly grows. A few papers have also shown that learning of
specific capabilities (i.c., ones not compositional in nature) can be sudden (Chen et al. 2024 Nam
cet al. 2024. Kirsch et al., 2022 He et al. 2024 Michaud et al. 2023 Cui et al.) 2024).
Grokking vs. Emergence. We focus the effect of data scaling on model's capabilities; often called 'learning curve' or 'data scaling' analysis (Viering & Loog 2022 Blumer et 1989 Bousquet
et al. 2021 (Seung al. 1992 Watkin et al.) 1993) Amari 1993 Haussler et al.]] 1994). On surface,
this might look similar to the seemingly related phenomenon of grokking (Power et al. 2022 Liu
et al. 2023b Zunkovič & llievski 2022 Murty et al. 2023 Barak et al. 2022 Edelman et al. 2023
Nanda al. 2022), wherein model's performance on task rapidly improves long after has fit the
16

---

Published as a conference paper at ICLR 2025
training data. However, we emphasize that we focus on online learning setting in our experiments, ie., a given sample is unlikely to be seen multiple times during training. Emergence is generally studied in such online learning scenarios. Since there is no distinction between train versus test data in such a setting, we argue mechanistic explanations of grokking identified in past work that involve perfect training data memorization phase (Nanda al. 2023 Liu al.) 2022b) are unlikely to help explain our results of emergence under data scaling in an online learning scenario.
B.1 Is EMERGENCE A MIRAGE, EXPLAINED VIA USE OF POOR METRICS?
Schaeffer et al. (0023 argue emergent sealing curves are a consequence of poorly defined, discontin- evaluation metrics, and the seemingly sudden learning goes away once partial, continuous credit is given to the model. While a credible claim, we provide three arguments below to demonstrate it is certainly not the complete story.
Emergence with continuous metrics. There is significant evidence for emergent abilities in neural networks that does not rely on use of discrete metrics at all. For example, in a recent work, Gopalani et al. (2024) show a sudden performance increase in regression setting with an entirely continuous metric metric-specinnn cericc-speifically.. mean square error. Phase transitions and corresponding emergent abilities have been formally discussed in other relevant works, e.g., by Lu et al. (2024) in regards to in-context learning and by Cui et al. (2024) in regards to positional code learning in a histogram computation task. Meanwhile, Chen et al. (2024) show sudden loss drop in BERT training, which, again, is not a continuous metric. Similarly, Okawa et al.) (2023) have shown task compositionality can drive emergent abilities, with their follow-up work using continuous metrics to demonstrate learning to compose yields emergent learning curves (Park et al. 2024). Overall, given this substantial evidence, we believe the argument by |Schaeffer et al. (2023) is narrower in scope than what is claimed by the authors it undermines and ignores legitimate cases of emergence in neural network training.
Relation to our work. In our work, we show performance improvements co-occur with loss drops (Fig. 4) i..., a continuous metric. Thus, confounded by Schaeffer et al.'s argument that poorly defined metrics drive emergence. In fact, we mention in Sec. 4 we also report several other (both continuous and discrete) metrics that show sudden improvements, further providing evidence that our results are not confounded by use of poorly defined metrics.
comfortably say our results not
Assumption on per-token power law scaling. To develop their claim, Schaeffer et al. (2023) propose a toy theoretical model that involves the assumption that an individual token's 's loss follows power-law scaling. This assumption is too strong: the loss, when averaged across a large number of tokens, indeed follows a power law (as popularly shown in literature scaling laws); however, individual token dynamics are in general drastically different, and in general extremely unlikely follow power law scaling. In fact, this point was most recently demonstrated by Schaeffer et a (2024) themselves! In this follow-up work, the authors show that learning dynamics of individual tokens corresponding to task output locations can show discontinuous progress. For further evidence in this vein, see the papers by Michaad et al. (2023) and Du et al. (2024). We thus believe that beyond the scope of their argument being narrower than original presented in the paper, the underlying rationale behind Schaeffer et al.'s argument also involves very strong assumption.
Relation to our work. In our work, we can concretely show Schaeffer et al.'s 's assumption does not hold: e.g., in Figure 4, we show loss curves for individual tasks, finding that learning dynamics of tokens corresponding to just these individual tasks (a subset of the overall tokens in a sentence) does not follow a power law! Thus, Schaffer et al.' 's's assumption, which was too strong to begin with, does not hold in our setting and hence their claims cannot explain our results.
again comfortably conclude that
A "metric" must at least gauge progress towards learning of task. To demonstrate their claim empirically, /chaefffer et al. (023) propose several alternative metrics that turn discontinuous learning curve into a continuous one. However, we emphasize a metric is only useful it captures progress towards learning of the task. For example, if the structure of a task is ignored, it is certainly easy to define arbitrary continuous metrics for a task; however, such metrics are unlikely help measure progress toward learning task. As precise example, consider the addition of
17

---

Published as a conference paper at ICLR 2025
two numbers, say 10 and 11, and the metric called token edit distance (Schaeffer et al. 2023 that assesses the average distance between digits the model's 's output, denoted xy. from the ground truth of 21; that is, (1x-2)+1s-11//) For both xy 22 and xy 11, this metric equals 1; however, clearly 22 is a better approximation for the ground truth 21. That is, once we account for the structure of the task, i.e., the fact that error in the most significant digit should be penalized more than error in the least significant one, we see limitations in token edit distance as metric for assessing model's ability add numbers. We argue claims relating emergence sensitivity of metrics can be confounded by use of metrics that do not respect the structure of the task, but give the impression of continuous learning.
Relation our work. As stress-test of our claims, we intentionally evaluate metrics that do not respect the structure of the task; e.g., in our unscrambling task, we evaluate the metric of per-token accuracy. This metric can be deemed equivalent the token edit distance metric proposed by |Schaeffer et al. (2023). since it does not respect sentence order. Intriguingly, we find that even this metric demonstrates sudden improvements our experiments. The first sudden improvement, corresponding syntax acquisition, is easily visible; the latter sudden improvement, corresponding to learning of type constraints, only visible when zoomed. This possibly indicates that even metrics that do not respect task structure show sudden improvements, but the improvement is relatively marginal and hence not easily visible.
C DATA-GENERATING PROCESS: DEFINING OUR FORMAL LANGUAGE
Our aata-generating process involves defining formal language, sampling sentences from this language, and then defining tasks be performed upon these sentences (specifically, free generation, unscrambling, conditional generation). In this section, discuss the precise details of how the language is implemented.
C.I DEFINING A GRAMMAR USING PCFGS
To define grammar for our language, we use the framework of Probabilistic Context-Frec Grammars (PCFGs). To keep the paper self-contained we provide short primer PCFGs below and then discuss our precise version of it in detail. For a more thorough discussion on PCFGs, we refer the reader one of the several well-written tutorials (Collins) 2013) and books (Sipser 1996).
C.1.1 SHORT PRIMER ON PCFGS
Broadly, a PCFG is defined via a 5-tuple G (NT, T, R, S,P), where:
NT is finite set of non-terminal symbols.
T is finite set of terminal symbols, disjoint from NT.
R is finite set of production rules, each of the form A - a3, where A NT and
or, B E (MT TT.
S E NT is the start symbol.
P is a function P - [0, 1]. such that for each A E NT,
P(A a.) =
To generate a sentence from a PCFG, the following process is used. Pseudocode for this generation process is provided in Algo. [
1. Start with string consisting of the start symbol S.
2. While the string contains non-terminal symbols, randomly select non-terminal A from the string. Choose production rule A - a:3 from R according to the probability distribution P(A + a).
3. Replace the chosen non-terminal A in the string with a, the right- side of the production rule.
4. Repeat the production rule selection and expansion steps until the string contains only terminal symbols (i.e., non-terminals remain).
18

---

Published as a conference paper at ICLR 2025
5. The resulting string, consisting entirely of terminal symbols, is a sentence sampled from the grammar.
Algorithm Pseudocode for generating sentence from a PCEG: Process sample sentence from a given PCFG G.
def generate sentence (G)
Initialize the string with the start symbol
string = [3]
While the string contains non-terminal symbols while any (is (syter) for symbel in string)
Select non-terni nal A from the string
A = Aalect_nonterminal (string)
$ Choose a product on rule A - according to P rule sample CuPP
Replace A in the string with
string = apply_rule rule (string, A, rule)
Return the generated sentence composed of terminal symbols return string
C.1.2 INSTANTIATING THE GRAMMAR UNDERLYING OUR LANGUAGE
While generally one directly samples sentences from grammar, in this work, we define grammar that operates over symbols, i.e., whose terminals are variables that are not yet populated by any specific values from the language's vocabulary. We emphasize this is unconventional manner for defining a PCFG, as one would generally use a standard vocabulary of the language to directly define terminal symbols. However, enforce type constraints, making the implementation easier. Specifically, one can simply sample an entirely symbolic sentence, and then enforce type constraints at the step when these symbols have be populated.
find this unconventional format aids in
Overall, our grammar, denoted G, is defined using the following.
Terminal symbols: (Subj, Obj, Verb, Conj, 1Verb, Desc, eAdj, dAdj, Adv, Prep].
Here, Subj is symbol for a subject, Obj for an object, Verb for verbs, Conj for conjunctions, 1 1Verb for linking verb, Desc for descriptors, eAdj for adjectives used for entities, dAdj for adjectives used for descriptors, Adv for adverbs, and Prep for prepositions.
Non-terminal symbols: NT {S, sNP, ST, oNP, OT, VP, vT, descT).
Here, S denotes the start symbol, sNP be interpreted noun phrase with subject in it, sT as the immediate ancestor of the subject symbol, oNP as a noun phrase with an object in it, oT as the immediate ancestor before the object symbol, VP verb phrase, vT as the immediate ancestor of the verb symbol, and descT as the immediate ancestor of descriptor symbol.
Production rules R:
S sNP VP [1.0]
sNP + sT [0.8] sNP Conj sNP [0.2]
VP 1Verb descT [0.4] Verb Prep oNP [0.4] VP Conj VP [0.2)
oNP + oT [0.7] oT Conj oNP [0.3]
eAdj Subj [0.8] Subj [0.2]
oT + eAdj Obj [0.8] Obj [0.2]
descT dAdj Desc [0.8] Desc [0.2]
Note that since non-terminals can appear on both left and right hand side rule, there recursion possible in our grammar and hence sentences get very long. We restrict sentence lengths to 75, yielding language where sentence lengths vary from 45 tokens. Probability over rules was partially adapted from prior work by (Hupkes et al. 2020
19

---

Published as a conference paper at ICLR 2025
Given the above, we now sample symbolic sentences such as Subj 1Verb Desc. We will populate these symbols with tokens from our vocabulary V. As noted above, while in general this population step would be performed as the final step of the grammar, to enforce type constraints and enable context-sensitivity. we separate it from the grammar.
Implementation. To implement the grammar, provides an easy interface to define PCFGs. Moreover, the package provides pre-implemented parsers that help perform grammaticality checks, i.e., if model produces sentence f(x) for some input I, we can simply use the parser to check whether f(x) is grammatically correct.
the NLTK package (Bird al. 2009). which
C.2 TYPE CONSTRAINTS
As described in the main paper, we instantiate a minimal notion of context sensitivity by constraining when entity is seen in the context of a property verb. There subtle ways in which such constraints will affect the generated sentences.
Constraining properties. When a symbolic sentence with descriptor sampled, the descriptor symbol will be populated with property that is valid for the relevant entity in the sentence.
Constraining subjects and objects. Subjects and objects broadly distinguish entities (or, to be precise, nouns) in a sentence. For properties that help define verbs (e.g., Wa 1 k), we instantiate a notion of directionality that determines whether the entity can take the action suggested by the verb corresponding to the property whether the action can be taken upon it. Accordingly, when verb is selected, only a subset subjects and objects that can take and have the action of verb be taken upon them are left valid to form sentence.
Overall, then, say we have symbolic sentence, We populate the symbols in the sentence as follows.
Check if there is a verb to populate. If so:
1. Randomly sample verb from the vocabulary and fill it in.
2. Sample required number of entities that can occur the right side of the verb, i.e., can populate objects
3. Sample required number of entities that can occur on the left side of the verb, i.e., can populate subjects
Check if there descriptor to populate. If so:
1. If the entities not populated yet, populate them.
Use the parse for the symbolic sentence to identify property which entity should populate the descriptor.
3. Randomly sample descriptor from the valid properties of said entity.
Check if there are adjectives to populate. If so:
1. Identify whether the adjective corresponds to an entity or property
2. Populate the adjective with valid adjective from the group of adjectives reserved for entities versus properties
Check there are adverbs, link verbs, prepositions, or conjunctions to populate. If so:
Sample an adverb, link verb, preposition, or conjunction from the vocabulary. We intentionally do not make these parts contextseensitve, since the remaining parts are sufficient induce centext-sensitivity and enable our experiments.
Pseudocode describing the process above detailed Algo
C.3 DEFINING THE OVERALL CONTEXT-SENSIIN LANGUAGE
Our language L is defined by first instantiating the underlying grammar described in App. C1 and then the type constraints in App.[Co C.2 We note that since the grammar is a randomized process and token roles are randomly filled by using the type constraints graph, the odds of seeing the same
20

---

Published as a conference paper at ICLR 2025
Algorithm 2: Pseudocode for populating a symbolic sentence: Fills in symbols while respect- ing the type constraints.
def populate sentence ():
Check if there is a verb to populate
if has_ :as_verb():
Sample verb from the vocabulary and fill it in verb sample sample_verbbveeeeeeeeeeeeeeeeeee verb(vocabulary) populate_verbl (verb)
Sample entities for the right side (objects)
objects sample_ente aerplll__nitieerrgghhe
Sample entities for the left side (subjects)
subjects sample_ (
Check if there are descriptors to populate if has (ssdescrippoos():
Populate entities if not alroady populated if not entities_ populaaedpppll populate_entiie entities()
# Use parse tree to identify which entity's property to populate entity
Sample descriptor from the valid properties
descriptor sample_ wttpppoooovviiiddpeeeeeee.e decliaateedderrpttttoooo (descriptoz)
Check it there are adjectives to populate
if has mas_adjectives(:
Identify if the adjective corresponds an entity or
property
role = (eaetify__ole(tokee)))
$ Sample valid adjective based the role
adjective sample adjective(role)
(adjective)
Check if there are adverbs, 1ink verbs, prepositions, or con conjuniionns to populate
i f has caaverbe_ete())
Sample an adverb, link verb, preposition, on conjunction from the vocabulary
word = sample word(vocabulary)
populate word (word)
21

---

Published as a conference paper at ICLR 2025
Iters
Iters 1000
Iters 5000
Iters = 10000
Iters 50000
Iters 100000
Entitles
Properties
Properties
Properties
Properties
Properties
Properties
Figure 8: Adjacency matrix with time. As the model undergoes training, entities are seen in the
context of more properties. Recording whether pair of object and property have been seen together, we can get the adjacency matrix for a bipartite graph corresponding to entities and properties that constitute the data generating process, as shown in the plots. The red-dotted lines indicate class boundaries. This matrix can be deemed as the adjacency matrix representation of the empirical type constraints graph, and, as training goes on, it will get closer to the ground truth graph. Note that several entities and properties will never be seen together, however, other entities from the class may be paired with a property, allowing the model a signal to infer that the entities likely belong to the same class.
sample multiple times are exceedingly low. Primary hyperparameters for defining L. include number of entities and number of properties, denoted |E] and |K], respectively. Unless mentioned explicitly, we fix these hyperparameters to 900 and 18000 respectively. In several experiments we do vary these variables though. Thus, we also note that we are slightly abusing notations here and using to refer to single language. In actuality, however, what we have is a family of languages with the same grammar, but varying number entities and properties. The vocabulary consists of entities (subjects and objects), descriptors, verbs, adjectives, adverbs, prepositions, and conjunctions. All languages we analyze have the same number verbs (= 200), linking verbs (= 2), adjectives (= 20), adverbs (= 20), prepositions (= 3), and conjunctions (= 2).
We also note that the type constraints graph merely describes which properties are valid for a class. For specific entity, only fraction of these entities might be visible during training. Specifically, constrain the sampling process such that only 15% of valid properties of a class are actually associated with entity. However, as training occurs, the model gets to several entities in the context of several properties. Even though certain pairs will never be seen together due to the restriction discussed above, two randomly sampled entities will still have a non-zero proportion of properties in whose context they have both been seen, hence giving the model some signal that the entities have shared characteristics (see Fig. B). This likely what leads the percolation-lit process we observe in the main paper to come into play, and hence yields 0.5 power law scaling for the transition point where model's performance on generating sentences with descriptors or performing reasoning tasks on sentences with descriptors starts to improve.
Note that there are large number of symbolic sentences possible; we merely report two of these to provide intuition. We also reemphasize that naturalistic sentences used as examples the main paper were to merely analogize the structures language is trying to capture. It is not difficult to that the sentences in the examples provided here have a similar structure and constraints as those naturalistic examples.
few example sentences from the language are reported in Figs 10
22

---

Published as a conference paper at ICLR 2025
Task: free generation
Input: null
Output: eAdj19 subj5 has pAdj7 descriptor1499 1496
Task: unscrambling
Input: has eAdj19 descriptor149e pAdj7 subj5
Output: eAdj19 subj5 has pAdj7 descriptor1499 1496
Task: conditional generation
Input: subj5 descriptor149)
Output: eAdj19 subj5 has pAdj7 1escriptor1496
Figure 9:
Exemplars where an entity's properties are deseribed. Each box represents different task; specifically, free generation, unscrambling, and conditional generation.
Task: free generation
Input: null
Output: eAdj16 subj102 adv9 verb64 in cAdjl obj41
Task: unscrambling
Input: eAdj16 subj102 adv9 verb64 in eAdjl obj41 Output: eAdj16 subj102 adv9 verb64 in eAdjl obj41
Task: conditional generation
Input: verb64 obj41
Output: eAdj16 16 subj102 adv9 verb64 in eAdjl obj41
Exemplars where a subject and object are bound via a verb. Each box represents different task; specifically, free generation, unscrambling, and conditional generation.
Figure 10:
23

---

Published as a conference paper at ICLR 2025
Man
Wakk
Man
Walt
Wak
Man
Walk
Woman
Talk
Woman
Talk
Woman
Tal
Woman
Twlk
Lowyer
Lawyer
Lawyer
Lawyer
Student
Student
Student
Eat
Student
Eat
Doctor
Doctor Jump
Doctor
Doctor
Jump
(a)
(b)
(c)
(d)
Figure 11: Viewing learning of descriptive type constraints as the problem of percolation on bipartite graph. Imagine entities and properties of class represented as nodes of bipartite graph. As training proceeds (marked using large gray arrows in the figure), edges are added to this graph denote the model has seen sentences containing nodes connected by the edge, i.c., an entity and property. (a) At initialization, there will be no edges in the graph. (b) However, with time, edges begin get added (bold, colored edges). (c) With time, the model will see the same properties being used for the different entities (dotted, colored edges). For ex., it may see that both Woman and Student can Eat. This leads to path of edges that connect entities and properties which have not been seen by the model in shared context (e.g., the model may be able to infer in panel (c) that a Woman can Jump). (d) If enough properties are shared between different entities, the model can infer that in fact all such entities belong to the same class and hence can be seen in the context of any property that is valid for the class. This will yield the learning of the broader concept class structure, as indicated by evolution of color of nodes and edges: from left to right, color is increasingly red, indicating there is path of edges that connects all entities and properties to each other. We analogize this overall process execution of the process of percolation on bipartite graph: as edges are added, we can define the existence of valid path between two nodes to suggest that there is enough information available to believe these nodes are related to each other; with enough edges, there is a sudden transition that leads to the emergence of a large connected component in the graph, indicating enough information is available to learn the structure of the class. This can enable generalization to unseen combinations of entities and properties.
D LEARNING OF DESCRIPTIVE TYPE CONSTRAINTS AS PERCOLATION ON BIPARTITE GRAPH
We analogize learning of type constraints function of time the addition of edges bipartite graph whose nodes denote entities and properties; an edge denotes a given combination of entity and property has been seen by the model during training. Consequently, as time goes on, more edges added to this graph, yiclding percolation phase transition once critical edge density necessary for achieving the transition met. This transition leads the emergence of large connected component. We claim this percolation process captures the dynamics of our model learning type constraints. Below, we first discuss the analogy between percolation and learning of type constraints in some detail (App. D.II) and then derive the scaling of the critical edge density needed for the percolation phase transition (App. D.2). Latter forms the basis our experiments Sec. 6.2
D. MORE DISCUSSION OF THE ANALOGY
Below, we discuss steps involved in the reasoning that help analogize learning of type constraints with the problem of percolation phase transition bipartite graph. See Fig. I1 for visualization.
Step 1: Defining the type constraints graph. Imagine a bipartite graph whose nodes on one side are entities of a class (e.g., Man, Woman, Lawyer, Doctor: etc. forming the class of Humans); meanwhile, the other set of nodes is the properties these entities can have (e.g., Walk, Talk, Eat, Jump, etc. for class of Humans). We call this graph the type constraints graph (see also Figure 2b). When sampling a sentence from our language to train our models, we use the type constraints graph to constrain which entities and properties can be seen together in sentence. While all entity-property
24

---

Published as a conference paper at ICLR 2025
combinations of class form valid sentences, given the combinatorially many combinations, at given point of time, the model is unlikely to have seen (and hence learned) all possible combinations. We can however test whether the model "knows" that unseen combination of entities and properties can form a valid sentence: if it does, the model has learned to combine an unseen entity and property belonging the same class.
Step 2: Analogizing what the model knows to percolation on a bipartite graph. At initialization, the model does not know that an entity of a class can possess properties of that class. For example, the model does not know that the entity Man can have the property of being Tall. As the model undergoes training, it will see sentences connecting entities properties valid for them; e.g,, seeing the sentence "That man is very tall" can lead to the model learning that the entity Man can be Tall. We define the concept density matrix (Definition 4) to capture this dynamic any given time. The matrix entry corresponding to a pair of entities and properties is assigned the value of 1 at given time/ if the model has seen this pair of entity and property in a sentence, This matrix can be deemed as the adjacency matrix of bipartite graph whose nodes, again, are entities and properties of class, and whose edges denote whether the model has the knowledge that an entity-property combination can produce valid sentence. As the model undergoes training, more edges are added to this graph (see Figure 6, left panel). We argue this is reminiscent of the problem of bond percolation on a bipartite graph, wherein edges are added the graph one-by-one, and, at some critical edge density, there is a phase transition that yields a large connected component covering a large proportion of the graph. That is, there is the sudden emergence of path between any two randomly selected nodes of the graph. Beyond the point of transition, the rate of growth of this connected component is approximately log-linear in edges added.
Step 3: Percolation as a model for predicting unseen combinations of entity-property pairs can be composed to form valid sentence. If the percolation analogy is correct, we expect the transition point in our empirical results where the model starts to learn descriptive constraints in log-linear manner with respect to time to scale as a power-law of exponent 0.5 in the number of node As results in Figure 7 show, this is indeed the case!
combinations of the graph (i.e., X ||El |
D.2 PERCOLATION THRESHOLD IN THE BIPARTITE GRAPH SETUP
For general bipartite graphs that are uncorrelated, meaning that they completely described by the degree distributions Pi (A:) and (k) for the entities and properties, respectively, the percolation threshold is
(k) (k)2
Pe V (k:k 1)) (k(K 1))²
Here, (-)x denotes the expected value with respect (k),, and we require [k))) = | (k)) for consistency. The case of randomly selecting connecting edges as demonstrated in the main text will correspond to starting from complete bipartite graph, which case Pi (i(k) = ]g and
P2(k) 1 leading to Pe VI/(EE 1)(i - 1)
[K].
To derive Eq. ① we use the generating function as explained in (Newman et al. 2001). Firstly, we introduce the generating function for the degree distribution of two concepts, i
1,2:
Gx)
P:(k)a
k=
The generating function can be used calculate moments of the probability distribution, such as the mean and variance, by taking derivatives:
(x) dx
Σ
kP,(k) = (k));
(3)
x==1
k=0
d' (x) dx
k(k 1)),(()))=
Σ k(k - 1)P:(() = (k<k 1)); (4)
k=U
==1
K=
Here denoted the average over the degree distribution of concept as (-).
25

---

Published as a conference paper at ICLR 2025
Another useful property of generating functions is that the generating function of the sum of the degrees can be described by the power of generating functions. For example, the distribution of the sum of degrees from two randomly selected nodes from sets and j. denoted by (sy(k), will satisty
Σ
(x)))))
(5)
With these properties in mind, we further introduce the generating function for the distribution of outgoing edges from node that we arrive at by following a randomly chosen edge:
Ex=o (k) Ex
G (x)
(x)
(6)
(k)
which can be obtained by noticing that the probability of the degree of a node arrived from randomly chosen edge is proportional to (k). The decreased power of a by one in the numerator exclude the originally chosen edge.
We further introduce the generating function for the distribution of the number of concepts in i that can be reached from a node in the concept j(* i) that is connected randomly chosen edge as Gt (zr), and the same when randomly choosing a node in concept j. G (x). These functions satisfy
(x) (()(()))
(x) = (z)
(8)
We also introduce the generating function for the distribution of the sizes of components in concept i that are reached by choosing edge, (x)), and the same when choosing node in concept i, (x)). These satisfy
H+) :H) (z)
(x) = (H)
(10)
Here, the key assumption is that there is no closed loop of edges in the network, which holds if the fraction of connection is low and there is no cluster (i.e., sub-critical regime).
The average cluster size of concept i, i.e., the number of nodes in i that are connected with each other, is then (S.) H.' (1), which is
(S.) = 1+ G (1)
(1I)
(1)
using the derivatives of Eqs. 9 I0]. term of Eq. (IT) becomes zero, so
The percolation threshold is when the denominator in the second
ã.¹² (1) = - (1)G) (1) G (1)G9" (1) (R:Ah: - 1)) (k<k 1))²
(12)
(k)) (k)2
(k)((k)
Now, when the connection of each a probability connection p associated with each bond on top of the original graph, the generating function of the degrees will become
()
Pi(n)
11 1:
21
-**
(13)
k=
Σ
-1p) -== G.. (1+ (x 1)p).
-1-
(14)
==0
From the first line to the second line, we used Exe D0c -nn Ei
We can then rewrite
Eq. [12 as
(K(A: 1))P(K(K- - 1))2
- (k(k (kkkk-1)k) ()) -1)12 =
(15)
(K))(K)22
(k)2
from which we obtain Eq. ( Here we used (k(k- 1 G.¹² (1:p) =p" (1) -> -1) and (R){ Gp' (1:p) pG (1) p(k);-
26

---

Published as a conference paper at ICLR 2025
D.2.1 EXPONENT IN THE CLUSTER SIZE
The critical exponent associated with the number of nodes the cluster for p > Pe: S (p- pc) is determined to be = when there is no specific structure in the graph. To see this, let us consider included finite size cluster (i.e., not the large
that u = (1) the probability that a node connected cluster). Recall that (1) was the generating function of the number of nodes in concept i included in the cluster the subcritical regime (p Pc): we are here assuming that the statistics will not change even in the supercritical regime (p > P.) when neglecting the large cluster. Then, from Eqs. 10). we have
(²( =u = -
(16)
()) f(u)
(17)
which is self-consistent equation.
By writing e, we have f(1 c, =1 c1. 2 (1, p)/2... where the derivative is taken for u. Noticing that f Pl) 1, we obtain the relation
8²
(p-Pe)
f(u,p)
f(u,
+ o(p Pe) o(E) (18)
dudp
2 0u-0p
u=1.pppc
u=lppp.
~ - Pp-
(19)
indicating B =.
As an interesting generalization, a classic result (Cohen et al. 2002) shows that even for the situation where Pe > 0, the power 3 can deviate from one. This corresponds when the differential coefficients in Eq. (8) diverge, corresponding cases where the second or third moment being ill-defined. For the case of (kk) k with 7 4, we can show that B 1/(7 -)) 3).
D.2.2 TRANSITION BEHAVIOR FOR FINITE INFERENCE STEPS
The mapping of the inference scheme to the percolation problem becomes precise only in the context of infinite inference steps. For finite number of steps, denoted as the pertinent question is the number of node pairs across the sets connected within 2n edges. Using the average degrees (k) and (l)) respectively. node the first set can reach upproximately ( (Ie) nodes after 2n + 1 steps. Hence, the approximate fraction of connected edges within 2n + steps [|) [(())++ (k)z
27

---

Published as a conference paper at ICLR 2025
E EXPERIMENTAL DETAILS
Model architecture. We train a two-block Transformer based on the nanoGPT architecture (Andrej Karpathy 2023) using the standard autoregressive language modeling objective, i.c., next token prediction. Each block contains two attention heads, an MLP, GELU activation, and processes / produces 128 dimension representations. Both token and position embeddings are learned during training.
Optimization setting. Models are trained using the Adam optimizer with 10-3 stepsize, batch-size of 128, and 10-4 weight decay for 10 iterations (or until the run collapses due to cluster challenges; e.g., power outages). Gradient clipping at norm of is applied. No learning rate schedule is used. Unless stated otherwise, results are averaged over three seeds.
Data configuration. Sentences are sampled "online", i... we sample a fresh batch of data every iteration by following the rules of the language. The language has M entities and N properties uniformly distributed over classes, with edges connecting properties sparsely and randomly distributed over valid properties for given object (specifically, only 15% connections are made). We slightly abuse notations by using L to refer to our language, since in actuality we have family of languages with the same grammar, but varying number of entities and properties. We note that since the grammar is a randomized process and token roles are randomly filled by using the type constraints graph, the odds of seeing the same sample multiple times are exceedingly low.
Tokenization. We use a one-hot, manually defined tokenization scheme wherein each token is associated with unique token ID.
E.0.1 PERFORMANCE OF A MEMORIZING SOLUTION ON DESCRIPTIVE SENTENCES
As the model undergoes training, its accuracy at getting descriptive constraints right at max, be the following: Acc = 0.1 + f max (1. 0.25 where f is fraction of pairs from the type [E]K]
constraints graph the model can see during training, 0.25 approximately the proportion of randomly sampled sentences that are descriptive in nature, B is batch-size, / is number of iterations, and R number of repetitions needed internalize that an entity and property constitute a valid context. Since we see the third phase in a regime where ~ 10 assuming at least 4 repetitions are necessary for internalizing a pair, we have Acc 0.15.
28

---

Published as a conference paper at ICLR 2025
F FURTHER RESULTS: ROBUSTNESS ACROSS SETTINGS AND EVALUATIONS
In this section, we report several more metrics relevant to assess how well the model has internalized the language and how well is able perform tasks top of strings from the language. We report results across several configurations as well. Rarely, but certainly sometimes, runs crashed due to cluster issues. These configurations are not reported, or reported until the point of crash if sufficient time had passed in training.
Base setting: This is the setting used throughout the paper, i.e., with 10 classes and 900 entities.
Varying number of properties: ranging from 14800-38800, increments of 1600.
Different class setting: change number of classes to 2 and repeat all evaluations in this setting.
Different entities setting: we change number of entities to 1800 and repeat evaluations in this setting.
We specifically report the following results. Both in the main paper and in the results below, evaluation metrics are averaged over 1000 randomly sampled strings.
Loss learning curves under different settings: App.
Grammaticality and type checks under different settings: App. F.2
Negative log likelihoods of sentences from the langauge and their perturbed versions (e.g.. where type constraints are not correct): App. F3
How well does the model follow our language, where we analyze NLLs of sentences generated by the model, distribution of length, and parse tree depth: App. F.4
Evolution of Attention maps: App. F.5
Further results on unscrambling: App. F6
Further results on Conditional Generation: App. Conditional generation evaluations turn out to be extremely time-expensive, with single run taking approximately 4 days to finish when conditional generation is evaluated (compared likely result of model generating extremely long sentences compose conditioning tokens that can involve multiple subjects, objects, and properties. We thus primarily focus on free generation and unscrambling in the results reported in this section. We do provide results for conditional generation in one more setting with 27600 properties to demonstrate that our findings from the main paper (i.e., in the 18000 properties setting) generalize.
hours without). This is
29

---

Published as a conference paper at ICLR 2025
F.1 LEARNING CURVES
We plot learning curves for different settings in this section. Results are reported for varying number of properties, averaged over seeds, and results for the base setting used in the main paper where number of properties is fixed to be 18000. For the latter setting, we show the average run alongside individual runs.
F.1.1 BASE SETTING WITH VARYING NUMBER OF PROPERTIES
14800
18000
21200
24400
27600
30800
34000
-37200
16400
19600
22800
29200
32400
35600
Total
Free generation
Unscrambling
Conditional generation
10
3.8 x 10
0 x
306 1
7 x00-
Loss
5x10
3-
3.2 x
10
x000
40
10
10
10a
10a
10
10a
107
10a
207
107
10a
10t
Iterations
Iterations
Iterations
Iterations
Figure 12: Learning curves with varying number of properties (base setting). As number of properties varied, can see sudden learning. For example, in free generation, we see a sudden loss drop. This point is precisely when the model learns produce grammatically correct sentences. Very slightly after this point, both tasks of unscrambling and conditional generation see improvement as well. There is second change of slope for these tasks between 10 to 10 iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
the overall loss is substantially more continuous, but individual tasks
Total
Free generation
Unscrambling
Conditional generation
5x10
seed
3.6 20
5x19-1
seed Werage
3x-0-
Loss
6x-0--
32x
4x10-1
4x
3x-1
2.511--
4x
10
10*
10a
133
10
10a
10a
lterations
Reeationn
Iterations
Iterations
Figure 13: Learning curves for setting with 18000 properties (base setting). We report this plot to zoom into a specific configuration. As can be seen, there some minimal variance across runs, but mostly points of transition are in a similar range.
30

---

Published as a conference paper at ICLR 2025
F.1.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER PROPERTIES
We change the number of entities 1800 (compared base setting of 900) and report learning curves under varying number of properties. See Figs.
15
14800
21200
24400
30800
34000
16400
19600
22800
26000
29200
32400
35600
38800
Total
Free generation
Unscrambling
Conditional generation
x10
8 x
6x
7 x00-
5x
Loss
5 10
4 10
10a
Iterations
Iterations
Iterations
Iterations
Figure 14: Learning curves with varying number of properties (1800 entities). As number of properties are varied, we see the overall loss is substantially more continuous, but individual tasks see sudden learning. For example, in free generation, see sudden loss drop. This point is precisely when the model learns to produce grammatically correct sentences. Very slightly after this point, both tasks of unscrambling and conditional generation second change slope for these tasks between 10 to 7 10 iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
improvement well. There is
Total
Free generation
Unscrambling
Conditional generation generraion
seed
6x
3,6 10-
1x
5x10-
Weraae
Loss
5x
10-1
32 x10-1
5x10-1
k10-
10a Iterations
Reerations
Iterations
Iteratinn
Figure 15: Learning curves for setting with 18000 properties (1800 entities). We report this plot to zoom into specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in a similar range.
31

---

Published as a conference paper at ICLR 2025
F.1.3 CHANGING TO CLASSES AND VARYING NUMBER OF PROPERTIES
We change the number of classes divide entities and properties over 2 (compared base setting of 10) and report learning curves under varying number of properties. See Figs, 16 17
14800
21200
30800
34000
37200
38800
16400
19600
24400
29200
32400
35600
Total
Free generation
Unscrambling
Conditional generation
3.5 10
10
3,4X
x0-3
10
Loss
3.2 1
6x
4x-10-
30
4x10
10
2 10-3
Iterations
Iterationn
Iterations
Iterations
Figure 16: Learning curves with varying number of properties (2 classes). As number of properties are varied, we see the overall loss is substantially more continuous, but individual tasks can see sudden learning. For example, in free generation, see sudden loss drop. This point is precisely when the model learns to produce grammatically correct sentences. Very slightly after this point, both tasks of unscrambling and conditional generation see improvement well. There is second change slope for these tasks between 10 to 7 10 iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
Total
Free generation
Unscrambling
Conditional conertionalgeeeraaiion
seed 0
344 10
7x
x10
3.3xx 10
4.5 10
5x
Average
6:
425 x0
Loss
311x 10
4x
5x.10
5x10--
4x000-
2. 10
3.5 10:1
20
325x10-4
4x10-1
Iterations
Iterations
Iterations
Iterations
Figure 17: Learning curves for setting with 18000 properties (2 classes). We report this plot to zoom into a specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in a similar range.
32

---

Published as a conference paper at ICLR 2025
F.2 GRAMMATICALITY AND TYPE CHECKS
As the model learns rules of our language, we can track how grammatical its sentences are and whether they satisfy type constraints, as done in the main paper. We report similar results for different settings this section. Specifically, we report results for varying number of properties, averaged over seeds, and for the base setting used in the main paper where number of classes is fixed be 18000. For the latter setting, we show the average run alongside individual runs.
For grammaticality, merely use the NLTK parser to check whether the generated sentences by the model under free generation are grammatically valid, i.e., they follow the rules of the grammar.
For Type Checks, we extract the subjects, objects, and any properties in the sentence to checks whether they are valid under the type constraints graph (see Def. 3).
F.2.1
BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting. See
Figs.
18
19
14800
18000
24400
27600
30800
34000
37200
16400
19600
22800
26000
29200
32400
35600
38800
Grammaticality
Type Check (Descriptive) Type Check (Relative)
Type Check (All)
109
10"
10
10:
6:
2
10-1
10a2
10-1
10
10
6 10-
10
10
10a
10*
10a
10
10
10
10f
10.
10
10t
10"
Iterations
Iterations
Iterations
Iterations
Figure 18: Grammaticality and Type Checks with varying number of properties (base setting). As number of properties varied, ie., grammar learning invariant to number properties (as also seen in learning curves). For type check, see leading to a boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints a transition this point well, but then after a period of saturation (akin saddle point), start to improve at an approximately linear rate (on log-log scale) until saturating again. These results match the base setting shown in paper.
the grammar is learned around broadly the same time,
grammaticality reaches its maximum, relative constraints quickly improve,
Grammaticality
Type Check (Descriptive)
Type Check (Relative)
Type Check (All)
10a
102
3200
6x10-1
seed 2
10
Average
10
3x30-)
20-1
2x10-1
10-4
10>
20
10a
10a
15t
10
107
10*
107
10a lterations
10t
16
Iterations
lterations
Iterations
Figure 19: Grammaticality and Type Checks with 18000 properties (base setting). We report this plot to zoom into a specific configuration, in particular the one used in main paper. As can be seen, there is some minimal variance across runs, but mostly points of transition are in similar range.
33

---

Published as a conference paper at ICLR 2025
F.2.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER PROPERTIES
We change the number of entities to 1800 (compared base setting of 900) and report results under
varying number of properties. See Figs. 20
14800
18000
21200
24400
27600
30800
34000
37200
19600
29200
32400
Grammaticality
Type Check (Descriptive) Type Check (Relative)
Type Check (All)
100
10
10
60-1 x
40-
10-
10
2x
10
10
10a
104
10a
102
10
10a
10a
102
20
Iterations
Iterations
Iterations
Iterations
Figure 20: Grammaticality and Type Checks with varying number of properties (1800 entities). To demonstrate robustness results, we increase number of entities in this experiment. We again find that number of properties varied, the grammar is learned around broadly the same time, ie., grammar learning invariant to number properties (as also seen in learning curves). For type check,
grammaticality reaches its maximum, relative constraints quickly improve, leading to boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints a transition this point well, but then after a period of saturation (akin saddle point), start to improve at an approximately linear rate (on log- log scale) until saturating again. These results match the base setting shown in paper.
Grammaticality
Type Check (Descriptive)
Type Check (Relative)
Type Check (All)
10a
10t
10
seed 2 Average
10:1
10-t
3x
10
2
10a
10->
102
10"
10F
10"
10
10f
106
10P
10F
Iterations
Iterations
Iterations
Iterations
Figure 21: Grammaticality and Type Checks with 18000 properties (1800 entities), We report this plot to zoom into a specific configuration. As can be seen, there some minimal variance across runs, but mostly points of transition are in similar range.
34

---

Published as a conference paper at ICLR 2025
F.2.3 CHANGING TO CLASSES AND VARYING NUMBER OF PROPERTIES
We change the number of classes divide entities and properties over 2 (compared base setting
of 10) and report results under varying number of properties. See Figs. 22 23
14800
18000
21200
27600
30800
34000
37200
38800
19600
32400
35600
Grammaticality
Type Check (Descriptive) Type Check (Relative)
Type Check (All)
10a
10a
6 10-1
10
1
40-0
6x 10-1
2 10
10-1
-0
20
10-1
10a
104
10a
102
10#
10a
10a
10a
10
Iterations
Iterations
Iterations
Iterations
Figure 22: Grammaticality and Type Checks with varying number of properties (2 classes). To demonstrate robustness of results, we increase fewer classes in this experiment. We again find that as number of properties varied, the grammar is learned around broadly the same time, i.e., grammar learning is invariant to number of properties (as also seen in learning curves). For type check, we soon grammaticality reaches its maximum, relative constraints quickly improve, leading to boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints see transition at this point well, but then after period of saturation (akin saddle point), start to improve at approximately linear rate (on log-log scale) until saturating again. The results are less prominent for this setting, but zooming (see figure below) shows the claims do follows the base setting shown in paper.
Grammaticality
Type (Descriptive)
Type Check (Relative)
Type (All)
10a
xx10
10a
seed 1
6x10
Average
4x11-
4x30
3
4x10-
10*
104
Iterations
Iterations
Iterations
Iterations
Figure 23: Grammaticality and Type Checks with 18000 properties (2 classes). We report this plot to zoom into specific configuration. As be seen, there is some minimal variance across runs, but mostly points of transition are in a similar range.
35

---

Published as a conference paper at ICLR 2025
F.3 NEGATIVE LOG LIKELIHOOD OF SENTENCES FROM LANGUAGE AND THEIR PERTURBED VERSIONS
In this section, report negative log-likelihoods (NLL) assigned by the model to randomly sampled sentences from the language during the course of training. To check how well the model is learning the language. and not perhaps overfitting to some specific samples (we note this is unlikely to occur in online learning, so this evaluation is just sanity check but not crucial). To this end, we evaluate the model assigned NLLs for following settings.
Seen. This is essentially the training distribution. We define valid sentences from the language by using the part the type constraints graph that has connections between entities and properties, and evaluate the model NLLs.
Uniform. Since only fraction of valid connections are shown to the model during training, it is not necessary for it to generalize to other valid connections. To assess whether the model can make such inferences, in this evaluation, we allow any valid connection between entities and properties to be uniformly sampled. This is also the primary evaluation setting for most experiments conducted in this work.
Randomize values. Arguably, the model overly generalize and even start deeming sentences that do not satisfy the type constraints to be valid. To assess this, in this evaluation, ensure the sentence remains grammatically correct, but intentionally use entities and properties that yield a sentence that does not follow type constraints.
Randomize grammar. We simply sample sentence and permute it to break the grammati- cal rules, while, technically speaking, preserving type constraints since tokens seen in the sentence are allowed to in the same context.
Results are reported for varying number of properties, averaged over 3 seeds, and for the base setting used in the main paper where number of classes is fixed to be 18000. For the latter setting, we show the average run alongside individual runs. Broadly, our results show the following process is underway as the model undergoes training.
1. First the model learns the grammar. At this point, Seen, Uniform, and Randomize Values all see improved NLL. This what we expect. Since a grammatically correct sentence does have to satisfy type constraints, in this first phase, the model is bound to show improved NLL for sentences that respect vs. do not respect type constraints.
2. Then, there is sudden improvement in NLL for both Seen and Uniform evaluations. At precisely this point, the Randomize values evaluation hugely degrades. This implies that once the model learns type constraints, it does deem likely sentences that do not respect them.
3. For the most part, the model never deems grammatically incorrect sentences to be likely. However, there is sudden, large degradation in NLLs for grammatically incorrect sentences later in training.
36

---

Published as a conference paper at ICLR 2025
F.3.1
BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting. See Figs.
25
16400
19600
22800
26000
29200
32400
35600
38800
Seen
Uniform
Randomize Values
Randomize Grammar
6 10*
4.6
4.6% 10
x 10
4.4x.10
4.4 10
10
402
4.2x
x00
xx 10*
10
x.8x
3.8 x
10'
10!
107
Iterations
Iterations
Iterations
Iterations
Figure 24: NLL of sentences with different perturbations and varying number of properties (base setting). See text in App. F3 for detailed discussion. Broadly, we see NLL. Seen evaluation very slightly better than Uniform.
Seen
Uniform
Randomize Values
Randomize Grammar
6x
134
seed seed 2
4.4 16
Average
1x
1x
10
38x u
18l
16x
16x
3,4
10
10P
105
Iterations
Iterations
iterations
Iterations
Figure 25: NLL of sentences with different perturbations for setting with 18000 properties (base setting). We report this plot to zoom into a specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in similar range.
37

---

Published as a conference paper at ICLR 2025
F.3.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER PROPERTIES
We change the number of entities 1800 (compared base setting of 900) and report results under
varying number of properties. See Figs. 26
14800
16400
19600
22800
26000
29200
32400
35600
38800
Seen
Uniform
Randomize Values
Randomize Grammar
5 k0
5 10!
10t
10
x00
NLL
101
10
1o
10a
10
10a
101
10
10a
10a
10
10a
10a
10"
10'
Iterations
Iterations
Iterations
Iterations
Figure 26: NLL of sentences with different perturbations and varying number of properties (1800 entities). See text in App. F3 for detailed discussion. Broadly, these plots show results with fewer classes show similar behavior as the base setting.
Seen
Uniform
Randomize Values
Randomize Grammar
$x10
4.8 10
seed 0
6x 10t
10
466
Average
x07
42
4x100
10a
30
16
107
109
167
121
100
10
10t
107
104
10
Iterations
Iterations
iterations
Iterations
Figure 27: NLL of sentences with different perturbations for setting with 18000 properties (1800 entities). We report this plot to zoom into specific configuration. can be seen, there some minimal variance across but mostly points of transition are in similar range.
38

---

Published as a conference paper at ICLR 2025
F.3.3 CHANGING TO CLASSES AND VARYING NUMBER OF PROPERTIES
We change the number classes divide entities and properties over (compared base setting of 10) and report results under varying number of properties. See Figs. 28 29
16400
19600
24400
29200
32400
35600
Seen
Uniform
Randomize Values
Randomize Grammar
4.4x
4.4X 10
100
100
10
4x 10
10
3.8
107-
3.6x 10
x 10a
104
Iterations
Iterations
Iterations
Iterations
Figure 28: NLL of sentences with different perturbations and varying number of properties (2 classes). See text in App. F.3 for a detailed discussion. Broadly, these plots show results with fewer classes show similar behavior the base setting.
Seen
Uniform
Randomize Values
Randomize Grammar
42x10
seed
10
4x
1x106
seed 2
10
30
1.8 161
10
2x
366
34x101
3.4
10a
10P
103
Iterations
Iterations
Iterations
Iterations
Figure 29: NLL of sentences with different perturbations for setting with 18000 properties (2 classes), We report this plot to zoom into a specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in similar range.
39

---

Published as a conference paper at ICLR 2025
F.4 HOw WELL DOES THE MODEL FOLLOW THE GRAMMAR: DISTRIBUTION OF NLLS, DEPTHS, AND LENGTHS
In this section, analyze how well the model learns our language. Specifically, we let model produce a sentence and then use the data-generating process (PCFG and our type constraints graph) to analyze the max, min, and mean values of metrics listed below. Note that in the following, we restrict evaluations to grammatically valid sentences only, i.c., only model generations that are grammatically valid are used for this evaluation (else the NLL will be infinity). Since the model produces grammatically sentences -990-95% of the time (see App. F.2 this conditioning leads to filtering of only a very minimal number generations.
NLL. We analyze how likely the sentences generated by the model are under the data- generating process.
Note that if sentences from the grammar were used itself for this evaluation, min, max, and mean values over batch of 1000 sentences turn out to be 1.0, 7.63, and 68.2 for the base setting; evaluations of model's generations are within these ranges as well.
Parse Tree Depth. We use the NLTK parser to compute the parse tree underlying our model's generated sentences and the tree's 's depth.
Note that if sentences from the grammar were used itself for this evaluation, min, max, and mean values over batch of 1000 sentences turns out to be 3, 4.78, and 15; evaluations of model's generations are within these ranges well.
Lengths. We compute the number of tokens in model's generated sentences.
Note that if sentences from the grammar were used itself for this evaluation, min, max, and mean values over batch of 1000 sentences turns out to be 4, 10, and 107; evaluations of model's generations are within these ranges as well.
F.4.1
BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number properties with the base experimental setting. See Fig. 30
14800
18000
21200
24400
27600
30800
34000
37200
164000
19600
22800
26000
29200
32400
35600
38800
NLL
Parse Tree Depth
Lengths
10a
10a
10:
max
mean
10a
10
10
10
10*
10"
10a
10a
10*
10s
Iterations
Iterations
Iterations
Figure 30: Grammar characteristics of model generation number of properties varied (base setting), See App. F.4 for a detailed discussion. Broadly, model generated sentences are in a similar range our language's.
40

---

Published as a conference paper at ICLR 2025
F.4.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER OF PROPERTIES
We change the number of entities to 1800 (compared to base setting of 900) and report results under varying number of properties, See Fig.
24400
37200
16-100
19600
22800
26000
29200
35600
38800
NLL
Parse Tree Depth
Lengths
10a
10
max
mean min
10
10'
101
10
Iterations
Iterations
Iterations
Figure 31: Grammar characteristies of model generation number of properties varied (1800 entities), See App. similar range as our language's.
F.4 for a detailed discussion. Broadly, model generated sentences are in
F.4.3 CHANGING TO CLASSES AND VARYING NUMBER OF PROPERTIES
We change the number of classes divide entities and properties over 2 (compared base setting of 10) and report results under varying number of properties. See Fig. 32
14800
18000
21200
27600
30800
34000
37200
3880D
16-400
19600
24400
29200
32400
35600
NLL
Parse Tree Depth
Lengths
101_
10
10
max
mean
10a
min
10a
10f
10a
10a
Iterations
Iterations
Iterations
Figure 32: Grammar characteristics of model generation number of properties varied (2 classes), See App. a detailed discussion. Broadly, model generated sentences are in a similar range as our language's.
41

---

Published as a conference paper at ICLR 2025
F.5 EVOLUTION OF ATTENTION MAPS
As the model acquires the grammar, we expect to attend to specific parts of the context to predict the token. Given the simplicity of model, can expect the attention maps be semantically meaningful, especially after the points of emergence. To assess this, every 1000 iterations of training, we record model'' attention maps the base experimental setting on 100 sentences that are either descriptive or relative in nature. Specifically, we define a symbolic sentence that define the grammatical configuration of the sentence, and then sample values for individual tokens according to their roles a 100 times. The attention maps are then recorded and averaged.
F.5.1 DESCRIPTIVE SENTENCES
Due to space constraints, we only report attention maps at iterations [0, 1000, 10000, 30000, 50000]. The primary motivation here that around iteration 1000 is when the model first seems learn the grammar. Similarly, between 1000-10000, it starts to learn type constraints. Then, between 10000-50000, starts to learn about descriptive properties.
(a) Initialization
(b) 1000 iterations
(c) 5000 iterations
(d) 10000 iterations
(e) 30000 iterations
(I) 50000 iterations
Figure 33: Evolution of attention maps for descriptive sentences. Since visualizing the evolution across time is difficult, we pick a few salient points according to region identified as different phase according learning curves and visualize them. We find that indeed the first time the model a sparse attention structure around 1000 iterations of training, i.e., when it becomes accurate at producing grammatically correct sentences. From 5-30000 iterations, the model learns focus on subject when producing next token, but the link verb and descriptive property do not pay substantial attention to subject. However, there point after 30000 iterations post which the attention on subject substantially increases: this is the range where other evaluation show a change in performance as well.
42

---

Published as a conference paper at ICLR 2025
F.5.2 RELATIVE SENTENCES
Due to space constraints, we only report attention maps at iterations [0, 1000, 10000, 30000, 50000]. The primary motivation here is that around iteration 1000 is when the model first seems to learn the grammar. Similarly, between 1000-10000, it starts to learn relative type constraints. We expect after this range, the attention pattern to not change much- is basically improving the sharpness of its attention map (pay more attention to tokens that were already being attended).
indeed what happens. We see the model
(a) Initialization
(b) 1000 iterations
(c) 5000 iterations
Bach beatt
Burh
(d) 10000 iterations
(e) 30000 iterations
(f) 50000 iterations
Figure 34: Evolution attention maps for relative sentences. Since visualizing the evolution
across time is difficult, pick few salient points according region identified as different phase according to learning curves and visualize them. We find that indeed the first time the model sees sparse attention structure is around 1000 iterations of training, i.e., when it becomes accurate producing grammatically correct sentences. Once the model learns relative type constraints (around 5000 iterations generally), much; albeit, it does get sharper (more attention to the tokens that were already being attended). Interestingly, we see object tokens paying large attention verbs, i.c., objects being selected by analyzing which verbs came before them. We see some non-trivial dependence between verb and the adverb preceding it, which itself solely attends to the subject token (i.e., it copies that token's representation); this could suffice to ensure the model gets verbs right for subject.
the attention patterns essentially stabilizes and does not change
43

---

Published as a conference paper at ICLR 2025
F.6 MORE RESULTS ON UNSCRAMBLING
In this section, we report several more results evaluating our models' performance on unserambling under varying number of properties for the base setting, setting with increased number of entities, and with only 2 classes to divide entities and properties over. We report results for the following metrics.
Exact Match. Accuracy of the model for getting every token of the scrambled sentence into
its right position in the unscrambled version.
Per Token Accuracy. This metric can be thought of as a smoother version of Exact Match, i.e., provides partial credit the model as learns to solve the task.
Accuracy Descriptive Sentences. In this evaluation, accuracy for sentences that are descriptive in nature, i.c., sentences wherein claims are made about an entity possessing property.
compute the exact match
We note that the precise way this evaluation is done is by restricting the sentence length to the shortest sentences (S tokens). This range primarily constituted of sentences that are descriptive in nature (s994%).
Accuracy Relative Sentences. In this evaluation, we compute the exact match accuracy for sentences that are primarily relative in nature, i.e., sentences wherein claims are made about subject relating to object via verb.
We note that the precise way this evaluation is done is by restricting the sentence length to the range of (7-9 tokens). This range is primarily constituted of sentences that are relative in nature (=:85)).
Grammaticality. Given the output generated by the model when it is fed in scrambled input, we evaluate whether the output is grammatically correct not.
Type Check. Given the output generated by the model when is fed in scrambled input, we evaluate whether the output follows type constraints or not. We measure accuracy over all constraints, i.e. we do not decompose this evaluation over descriptive / relative properties.
44

---

Published as a conference paper at ICLR 2025
F.
BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting. See
Figs. 35
36
14800
18000 19600
27600 29200
30800
34000
37200
16400
22800
26000
32400
35600
38800
Exact Match
Per Token Accuracy
Descriptive Sentences
0.25
0.40
0.35
0.20
0.30
0.25
0.20
0.15
0.10
0.00
0.00
10
Relative Sentences
Grammaticality
Type Check
0.35
0.9
0.8
0.25
0.7
0.5-
0.20
0.4
0.19
0.09
10'
10
20
10'
10
10
30 10
10
Iterations
Iterations
Iterations
Figure 35: Results on unscrambling task as number of properties are varied (Base setting). See App. F.4 for detailed discussion on metrics used. Broadly, we see the results presented in the main paper are consistent across varying number of properties: the model first witnesses improvement in exact match because relative sentences start to improve, i.e., the grammar is learned, performance then saturates, and then it finally starts improving again once descriptive sentences' accuracy starts to improve. We emphasize metrics assigning partial credit also show sudden changes, i.e., our results are not sensitive to metrics used.
Exact Match
Per Taken Accuracy
Descriptive Sentences
0.50
0.25
0.6-
0.20
Average
0.5
0.4
02
0.30
02-
0.00
01
0.00
0.0
20'
122
10"
12
201
Relative Sentences
Grammaticality
Type Check
0.40
0.25
08-
07-
0.30
0.25
0.6
055
0.20
0.15
0.-
0.5
0.30
0.65
0.1
0.00
10
10"
30'
Iterations
Iterations
Iterations
Figure 36: Results on the unscrambling task for setting with 18000 properties (base setting). We report this plot to zoom into specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in a similar range.
45

---

Published as a conference paper at ICLR 2025
F.6.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER OF PROPERTIES
We change the number of entities to 1800 (compared to base setting of 900) and report results under
varying number of properties, See Figs, 37
38
14800
18000
27600 29200
37200 30800
34000 32400
16400
19600
22800
26000
35600
38800
Exact Match
Per Taken Accuracy
Descriptive Sentences
0.4
0.5
0.5-
0.3-
0.15-
0.2
0.05
0.1
0.00
10
Relative Sentences
Grammaticality
Type Check
0.30
0.7-
0.25
0.6
0.15
0.5
0.4
0.10
0.4
0.3
0.3
0.05
0.-
0.09
10'
10
20
10a
10
10
30
10
10
Iterations
Iterations
Iterations
Figure 37: Results on unscrambling task as number of properties are varied (1800 entities). See App. F.4 for a detailed discussion on metries used. Broadly, we see the results presented in the main paper are consistent across varying number of properties and larger number of entities compared to the base setting: the model first witnesses improvement in exact match because relative sentences start to improve, i.e., the grammar is learned, performance then saturates, and then it finally starts improving again once descriptive sentences' accuracy starts to improve. We emphasize metrics assigning partial credit also show sudden changes, i.e., our results are not sensitive to metries used.
Exact Match
Per Taken Accuracy
Descriptive Sentences
0.5
0.25
0.6-
0.4
Average
0.5
0.3-
0.15
0.2-
0.05
0.2
0.3
0.00
0.0
10'
10'
10a
10'
20t
20a
20'
20a
30
Relative Sentences
Grammaticalliy
Type Check
0.40
0.35
0.
0.7
0.30
0.25
0.5-
0.5-
0.20
0.4
0.15
0.4
0.30
0.05
0.00
0.3-
20'
10
10'
10
20
20'
10t
201
Iterations
Iterations
Iterations
Figure 38: Results on the unserambling task for setting with 18000 properties (1800 entities). We report this plot to zoom into a specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are a similar range.
46

---

Published as a conference paper at ICLR 2025
F.6.3
CHANGING TO 2 CLASSES AND VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting. See
Figs. 39
40
14800 16400
18000
21200
34000 Per Taken Accuracy
27600
30800 32400
37200
38800
19600
24400
29200
35600
Exact Match
Descriptive Sentences
0,5
0.25
0.4
0.5
0.3
0.10
0.05
0.00
30
30
Relative Sentences
Grammaticality
Type Check
0.9
0.9
0.30
0.8-
0.20
0.25
0.7
0.6-
0.7
0.5
0.4
8.05
0.09
10'
10
10
10a
10
10
30
10
10
Iterations
Iterations
Iterations
Figure 39: Results on unscrambling task as number of properties are varied (Base setting). See App. F.4 for detailed discussion on metrics used. Broadly, we see the results presented in the main paper are consistent across varying number of properties and fewer classes than the base setting: the model first witnesses improvement in exact match because relative sentences start to improve, i.e., the grammar is learned, performance then saturates, and then finally starts improving again once descriptive sentences' accuracy starts to improve. We emphasize metrics assigning partial credit also show sudden changes, i.e., our results are not sensitive to metrics used.
Exact Match
Per Taken Accuracy
Descriptive Sentences
0.50
0.25
0.20
Average
0.5
0.4
0.-
0.30
0.00
011
0.00
0.-
20'
10
122
10"
12
201
300
Relative Sentences
Grammaticality
Type Check
10
0.
0.6
0.7
0.4
0.6
307
10"
30'
Iterations
Iterations
Iterations
Figure 40: Results on the unscrambling task for setting with 18000 properties (2 classes). We report this plot to zoom into specific configuration. As can be seen, there is some minimal variance across runs, but mostly points of transition are in a similar range.
47

---

Published as a conference paper at ICLR 2025
F.7 ANOTHER SET RESULTS WITH CONDITIONAL GENERATION
As mentioned before, Conditional generation evaluations turn out to be extremely time-expensive, with single taking approximately days finish when conditional generation is evaluated (compared to 12 hours without). This is likely result of model generating extremely long sentences compose conditioning tokens that can involve multiple subjects, objects, and properties.
While we focus solely on free generation and unscrambling in the results reported in the sections above, to demonstrate that our findings from the main paper (i.c., in the 18000 properties setting) generalize to another setting, we provide results for similar to Fig. 5 in another setting with 27600 properties. Shown Fig. 41 we can see our findings perfectly align with results from the main paper and other results shown the appendix: the model first learns the grammar, then type constraints, and witnesses improvements on unscrambling and conditional generation tasks as these relevant data-regularities are learned.
P1
P2
P3
(b)
P1
P2
P3
(c)
P1
P2
P3
Gremmer
Exact Match
Gonds salisfied
0
0.26-
Per
Dest: A Typcs
0 50
Conds satiifed
0.4+
0.2
08
25
0.1
107
12
10"
16
107
101
102
1.0
10"
seed
seed
s000
Average
Total
Free generation
Unscramb ing
Cond. generation
0.60
0.38
0:5-
0.55
0.36
2.50
0.34
0.45
0.32
0.40-
107
30*
103
10
10a
10F
10:
10a
10
102
10*
305
Iterations
Iterations
Iterations
Iterations
Figure 41: Demonstration (27600 properties). We report this plot to zoom into a specific configura- tion. As can be seen, there is minimal variance across runs, but mostly points of transition in similar range.
48

---

Published as a conference paper at ICLR 2025
G SCALING OF POINT OF EMERGENCE (AKA TRANSITION POINT)
In this section, we repeat experiments from the main paper for different settings analyze how the point of emergence (interchangeably called transition point phase transition here) scales with increase in number of properties in the language. We again report results for both unscrambling and free generation tasks and also add several more metrics not reported in the main paper.
Before proceeding however, we fürther discuss our evaluation protocol wherein we rescale x-axis by some power of number of properties in the language by connecting it back to the notion of phase transitions and emergence in physics. We also clarify why we might times need to rescale the y-axis.
G.1 COLLAPSED CURVES HELP DEMONSTRATE SCALING OF THE TRANSITION POINT
Assume S denotes control variable (e.g., edge density in bipartite graph). Assume change in S induces a phase transition in our system (e.g.. the bipartite graph), as measured by sudden change in the value of some order parameter M (e.g., ratio of largest cluster size to graph size). Further, say the transition point S. depends on some other property of the system v (e.g., number of nodes in the bipartite graph) via power law relationship. That is, have
S. x Da.
Accordingly, if we tracked M as changed, we would find its value rapidly starts change as 8/1- + 1. As we change the value of v, assume the value of M at the point of transition is some constant value. Thus, if we plot M as a function of S/v², we would find the results "collapse" onto each other at the point of transition. This is the intuition behind our experiments in the main paper: as we expect a square-root dependence on the number of properties, if we divide the control variable (training iterations) by / /KK,, we should see the curves corresponding to languages with different number of properties collapse onto each other. This argument however assumes the perfect order parameter with respect to which theory is defined. This need not be the case, as discussed in the next section.
tracking
G.2 WHAT METRICS MAKE SENSE?
Note that the theory of percolation bipartite graph and its corresponding phase transition focuses on the ratio of size of largest cluster in the graph to the overall graph size. That is, the theory of gauging which nodes member of the largest cluster and how do this metric increase with scaling of edge density. By itself, however, standard metrics one would evaluate in tasks defined in this work, c.g., accuracy, need not linearly correlate with the cluster size. This can affect the collapse visualization discussed in App. G.I To claborate further, we build on the toy setup from above.
Say, the order parameter M is difficult to experimentally gauge-this is in fact the case for our work, where describing and evaluating notion of membership within largest cluster is difficult. Accordingly, we must define alternative metrics that we expect to correlate with M. Denote this alternative parameter as M' and say M' == .M x v² i.e., another dependence on gets involved in our experiments as we go from M to M'. Accordingly, we track M' as the rescaled control variable $/6" is varied, we will find that instead of collapsing onto constant value, systems with different values have a different value for M'. However, importantly, we will see that the value of M' this point itself follows power law relationship M' v². Accordingly, if rescaled the y-axis by dividing by 2 we would see the curves collapse onto each other again; that is, we will that
S yo
M' D + 0(1)
as
+
we have
Thus, when using alternative metrics that are meant to correlate with the gold stan-standard metric (e.g., M' instead of M in the discussion above), rescaling of the y-axis according to property of the system may be needed to help induce a collapse of different experimental curves. As discussed in the next section, this subtlety turns out to be extremely crucial for our work.
49

---

Published as a conference paper at ICLR 2025
G.3 EVALUATION METRICS FOR EVALUATING EMERGENCE IN OUR WORK
We find artifacts of the toy problem discussed in sections above in our experiments. Specifically, the theory of percolation on bipartite graph focuses on largest cluster size as an order parameter. However, it can be difficult to define a cheaply calculable metric that captures a notion of 'largest cluster' and evaluates membership of properties and entities to the cluster in the context of neural network being trained on some data distribution. To circumvent this, we define several alternative metrics that approximate the notion of largest cluster to an extent, but are not necessarily expected to show perfect collapse of experimental curves when the x-axis rescaled by some power of the number of properties. However, if a mere rescaling of the y-axis by an independent variable (e.g., the control in this experiment, i.c., number of properties) induces a collapse of experimental curves, then can be confident the transition point follows expected scaling.
Evaluation Metrics. Having discussed the subtleties above, we now discuss the set of evaluation metrics used in this paper evaluate how the point of emergence (i.e., transition point) scales with increase in number of properties. We analyze the following two tasks in this section: unscrambling and free generation. We use some metries which are specific a given task and another batch that common to both, as discussed next.
Unscrambling, Following metrics are reported solely for unscrambling and gauge model's accu- racy on the task. As the model learns which properties belong to which entities, we can expect to exploit that knowledge to reduce the hypothesis space for next-token predictions and get more accurate on unscrambling. Hence, we expect accuracy to suddenly start increasing or at least for its rate of increase to change once the model undergoes a percolation transition.
Exact Match: Evaluate whether the model's s unscrambled sentence perfectly matches the ground-truth.
Per-Token Accuracy: Evaluate how many of the tokens from model's unscrambled sentence match the ground-truth.
DDescriptive Sentences Accuracy:
Exact match accuracy for solely sentences that descriptive in nature. Similar to prior experiments, we simply filter sentences for length and use ones with < 6 tokens for this evaluation, since 94% such sentences are descriptive in nature and this allows for easier batching and fast evaluation.
Free Generation. Following metrics are reported solely for free generation. Similar to unscram- bling, these metries evaluate a model's performance on the task of free generation, wherein the goal is to produce sentence that is grammatically valid and respect type constraints. We specifically focus on type constraints in this section. Specifically, as the model learns which properties belong to which entities, we can expect Type Check corresponding to descriptive sentences (see below) will start to improve substantially. In contrast, for Type Checks of relative properties (i.c., validity of verbs), we do not expect to see any effect of how many descriptive properties are there in the language.
Type Check (Descriptive): A type check evaluation, discussed in main paper, that checks whether descriptive properties associated with an entity by the model are in fact valid. We expect the percolation phase change to affect this evaluation, yielding close to 0.5 scaling with number of properties.
-Type Check (Relative): A type check evaluation, as discussed main paper, that checks whether relative properties associated with an entity by the model are in fact valid. We expect the percolation phase change to not affect this evaluation, since relies solely on the grammar, and hence there should be no clear effect of scaling number of properties on this metric
Type Check (AlI): A type check evaluation, as discussed main paper, that checks whether all properties and corresponding entities in a given sentence are allowed to be seen in each other's context. We expect the percolation phase change to affect this evaluation, since, unless the model gets descriptive constraints right, this metric will be zero. However, there will be non-trivial proportion of sentences that do not have any descriptor tokens within them; we expect improvement on these sentences to increase the overall metric, leading saturation phase until the percolation transition kicks in and the model starts inferring which properties are associated with which entity.
50

---

Published as a conference paper at ICLR 2025
Common metrics. Following metrics reported for both the unscrambling and free generation tasks. These metrics assess whether the model deems given property and an entity belong to each other, regardless of whether it has them together as part of the same context. In this sense, these metrics test minimal notion of cluster membership, where the cluster is defined by classes dividing the bipartite graph.
Average Probability of Valid Tokens. Used for evaluating descriptive type constraints in free generation and unscrambling. Specifically, we sample a sentence from L that remarks on entity possessing a property, and then evaluate probability of this property being the next token when the sentence is inputted to the model. For example, let x = The fire was large, we evaluate Pr (x) large) x where x denotes the sentence up the last token and f((x) denotes the first token predicted by the model. The result is averaged over 1000 sentences.
Negative Log-Liikelihodd of Valid Sentences. For free generation, we sample a descriptive sentence from the language and evaluate how likely the model deems this sentence, reporting as negative log-likelihood (NLL), Similarly, for unscrambling, we sample a random descriptive sentence, scramble it, and then evaluate how likely the model deems the ground- truth unscrambled version.
This evaluation is similar to the average probability evaluation above. However, we now compute the rank of randomly sampled descriptor token instead of the probabilitty associated by the model to this token. If the model knows which properties go with an entity, the rank tokens associated to said entity's 's properties will be low, indicating they are highly likely to be sampled. This metric scales function of vocabulary size; hence, we divide by the number of properties |K] and called that normalized rank.
Normalized Rank of Valid Tokens.
Percent Top-K. Similar the rank metric above, this metric merely checks whether the rank is less than some threshold; if so, it returns True, indicating the model understands that the property being evaluated valid for the given entity. We the threshold be equal to number of properties associated with a class, i.e. KK/C.
G.4 EXPERIMENTAL SETTINGS
We analyze the following settings, sweeping the number of properties the range 14800- -3880, in increments of 1600.
Base setting: This is the setting used throughout the paper, i.e., with 10 classes and 900 entities.
Different class setting: change number of classes 2 and repeat all evaluations in this setting.
Different entities setting: we change number of entities to 1800 and repeat all evaluations in this setting.
51

---

Published as a conference paper at ICLR 2025
G.5 SCALING IN THE UNSCRAMBLING TASK
G.5.1 BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting first. See Fig- for metrics specific to unscrambling, Fig. 43 for the common metrics that more closely capture notion of cluster membership, and Fig. 44 for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.
14800
24400
30800
34000
37200
29200
32400
35600
38800
Exact Match
Per Token Acc.
Descriptive Sentences Acc.
0.40
0.35
0.20
0.25
0.20
0.15
0.3
0.2
0.09
0.00
10
10-1
30-7
10-1
10-2
10
10-1
10-1
Iterations/
[K]
Iterations |K]25
Iterations / [K
Figure 42: Results on metries specific to unscrambling (Base setting). We see a collapse of all metrics under 1.5 scaling exponent.
21200
22800
35600
Avg. Probability
NLL x (K000
[K]
Percent Top-K (All) x IR|22
1.4
0.20
0.55
6.21
6.30
20: Iter Rerations/ JKP2
kerations [KQ25
Iterations [K]20
Iterations / [K]05
Figure 43: Results on metrics designed to approximate cluster membership (Base setting). We see an approximate collapse of inflection points in the normalized rank and percent top-K metrics under a 0.5 scaling exponent. Average probability is expected to follow accuracy curves, yielding 1.5 scaling exponent. Interestingly, NLL has scaling exponent of 2.0.
14800
18300
21200
24400
27000
30000
34000
37200
15420
19500
22800
20020
29200
32400
35600
38500
Avg. Probability
Avg. Probability
Avg. Probability
Aug. Probability
25
0.2
0.20
0.2
0.25
0.15
0.15
0:00
0.20
0.10
0.10
0.25
0:00
0.00
0.00
Iterations/ 1K
Iterations/ [K:10
Iterations/ [K]13
Iterations/ [K]20
Figure 44: Average probability curves for different x-axis rescalings (Base setting). An exponent of 1.5 induces the best collapse of experimental curves. Inset plots zoom in near transition point.
52

---

Published as a conference paper at ICLR 2025
G.5.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER OF PROPERTIES
We change the number of entities to 1800 (compared to base setting of 900) and report results under varying number of properties. See Fig. 45 for metrics specific to unscrambling, Fig. 46 for the common metries that more closely capture notion of cluster membership, and Fig. 47 for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.
14800
18000
21200
24400
27600
30800
34000
37200
16400
19600
26000
29200
32400
35600
38800
Exact Match
Per Token Acc.
Descriptive Sentences Acc.
0.20
0.15
0.05
0.2
0.00
0.0
10
10
Iterations/ |K]2-0
Iterations / |K]
Iterations / [K]2.0
Figure 45: Results on unscrambling task as number of properties are varied (1800 entities). We
collapse of all metrics under 2.0 scaling exponent, indicating an effect of number of entities possibly on the transition point. Arguably, this is expected since unscrambling is affected by both number of entities and properties involved in the language.
18300
21200
26400
30000
34000
37250
19660
22800
20000
25200
12400
35600
38850
Avg. Probability
NLL x [K| (-206
Norm.
[K]
Porcent Top-K (All) x 1K|22
0.40
7.0
1.4-
6.
6.20
0.35
3.3
4.5
0.25
6.30
1044
20:
kerations/ IK]2.
Iterations [K]20
Iterations// / [K]05
Iterations / [K(S.
Figure 46: Results on unscrambling task as number of properties are varied (1800 entities). We see an approximate collapse of inflection points in the normalized rank and percent top-K K metrics with a 0.5 scaling exponent. Average probability is expected to follow accuracy curves, yielding a 2.0 scaling exponent. NLL again shows scaling exponent of 2.0, similar to base setting.
14800
18000
21200
24420
27500
30000
34000
$7200
19400
19800
22500
20000
19200
52400
35600
28500
Avg. Probability
Avg. Probability
Avg. Probabilliy Ity
Aug. Probability ity
6.10-
40
0.40
0.40
95
035
25
0.2
6.20
30
0.20
0.20
0:3-
155
0.35
0.
0.00
0.20
6:00
0.00
0.00
0100
127
12
16-
Iterations/ 1K
Iterations/ |K[2-
Iterations [K]1a
Iterations/ / (K]22
Figure 47: Average probability curves for different x-axis rescalings (1800 entities). An exponent between 1.5-2.0 induces the best collapse of experimental curves, similar base setting. Inset plots zoom in near transition point.
53

---

Published as a conference paper at ICLR 2025
G.5.3 CHANGING TO 2 CLASSES AND VARYING NUMBER OF PROPERTIES
We change the number of classes to 2 (compared to base setting of 10) and report results under varying number of properties. See Fig. 44 for metrics specific to unscrambling, Fig. 46 for the common metrics that more closely capture notion of cluster membership, and Fig, [47 for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.
14800
18000
21200
27600
30800
34000
37200
38900
16400
19600
24400
29200
32400
35600
Exact Match
Per Token Acc.
Descriptive Sentences Acc.
0.25
0.6-
0.4
0.20
0.5
0.4
0.1
10
30
10
10
10
Iterations/ / LK]
Iterations / |K]
Iterations / |K]
Figure 48: Results on unscrambling task as number of properties are varied (2 classes). We see a collapse of all metrics under a 1.5 scaling exponent.
14800
18000
21200
27600
30803
34000
37200
38600
16400
19600
24460
29200
32403
35600
Norm. Rank x [K] -1
Avq. Probability
NLL 1K0-
Percent Top-K (8]22
7.5-
0.4
15.
144
60-
13-
6.-
12
50-
0.2
13
1224
23
10:4
20
10
251
231
137
10'
Iterations/ / 1K
Iterations |K]20
Iterations [K]2.
Iteeraions/ 15]25
Figure 49: Results on unscrambling task as number of properties are varied (2 classes). We see an approximate collapse of inflection points in the normalized rank and percent top-K metrics with a 0.5 scaling exponent. Average probability is expected to follow accuracy curves, yielding 1.5 scaling exponent. NLL again shows a scaling exponent of 2.0, similar to other settings.
34800
18000
21200
27300
30800
34000
37200
30000
15400
19600
20400
29203
32400
33503
Avg. Probability
Avg. Probability
Avg. Probability Ity
Avg. Probability
0.4
04
0.4
0.3
0.3
0.3
2.3
0.2
0.2
03
0.0
0.0
20a4
10t
Iterations/ / 25
Iterations/ / |K]10
Iterations
/Kg23
Iterations/ [K]2
Figure 50: Average probability curves for different x-axis rescalings (2 classes) An exponent of 1.5 induces a perfect collapse of experimental curves, similar base setting. Inset plots zoom in near transition point.
54

---

Published as a conference paper at ICLR 2025
G.6 SCALING IN THE FREE GENERATION TASK
G.6.1 BASE SETTING WITH VARYING NUMBER OF PROPERTIES
We report results under varying number of properties with the base experimental setting first. See Fig. [ for metrics specific to free generation, Fig. 52 for the common metrics that more closely capture notion of cluster membership, Fig. |3 for different x-axis rescalings for the average proba- bility curves that demonstrate validity of claimed scaling of the transition point and its corresponding variant in Fig. 54 where the y-axis not rescaled demonstrate the transition points align better with our claimed scaling exponent.
14800
18000
21200
24400
27600
30800
34000
37200
16400
19600
22800
26000
29200
32400
35600
38800
Type Check (Desc.) x IK)05
Type Check (Rel.) |K]0
Type Check (All) [K]05
1.0
40-
35
35-
0.0
30-
25-
25
20
0.4
20
10
15-
10-
0.0
10
102
10a
100
10F
Iterations/ |K]0.5
Iterations/ / |k|00
Iterations/ / |K]0.5
Figure 51: Results on metrics specific to unscrambling (Base setting). We see a collapse of descriptive and all constraints metrics under a 0.5 scaling exponent; relative constraints are clearly invariant to number of properties.
19500
Aug. Probability pp2
NLL x 187- as
Norm, Rank 187-35
Percent Top-K japss
420
2.44
0.040
70-
350
1.42
300
1.43
0.655
00-
30
40
200
1.30-
0.020
350
1.32
0.015
20
16
16:
160
107
107
161
13F
367
304
36'
101
1311
Iterations |K]05
Iterations [K
Iterations/ / [K25
Iterations [K]00
Figure 52: Results on metries designed to approximate cluster membership (Base setting). We see all metrics show an approximate collapse under a 0.5 scaling exponent. Collapse is in the inflection points for the normalized rank and percent top-K metrics.
14000
10000
21200
24400
27600 29230
30800
34000
37209 35620
16400
15600
22500
26200
32400
36800
Avg. Probability x 1Kp3
Avg. Probebility x 1KP3
Avg. Probability x 1M75
Avg. Probebility x pK2
120
300
750
200-
300
300
530
532
10'
10
202
10
Iterations/ / [K
Iterations/ / jxjs
Iterations/ [K]10
Iterations / [K]L5
Figure 53: Average probability curves for different x-axis rescalings (Base setting). An exponent between 0.5-1.0 can be expected to induce the best collapse for the metric of average probability; results in Fig, 54 show the exponent is closer to 0.5.
55

---

Published as a conference paper at ICLR 2025
14800 16400
18009 19609
21200 22500
24400
27500
30800
34000
37203
25000
29200
32400
35600
38503
Avg. Probability
Avg. Probability
2e-4 Avg. Probability
2e.4 Avg. Probabilit
2.43
2.5
2.3
2:5
1.75
1.75
175
177
1.0
1.50
150
150
1.50-
0.75
0.75
0.15
0.15
0.5-
0.2
0.25
105
16
Iterations 17|00
Iterations/ jy
Iterations/ / |K]2a
Iterations [K]
Figure 54: Average probability curves for different x-axis rescalings (Base setting), An exponent of 0.5 better aligns the transition points.
G.6.2 CHANGING TO 1800 ENTITIES AND VARYING NUMBER OF PROPERTIES
We change the number of entities to 1 1800 (compared to base setting of 900) and report results under varying number of properties. See Fig. 55 for metries specific to free generation, Fig. [6 for the common metrics that more closely capture a notion of cluster membership, Fig. 57 for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point and its corresponding variant in Fig. 58 where the y-axis is not rescaled to demonstrate the transition points align better with our claimed scaling exponent.
18000
21200
27600
30000 32400
34000
37200
16400
19600
22800
26000
29200
35600
38800
Type Check (Desc.) 1
Type Check (Rel.) o
Type Check (AIl) 1K]
35
35-
30
0.8
30
25
0.6
20
20
15
15
0.2
10
0.0
10a
30a
10'
10'
10"
10a
10'
10a
10
Iterations/ IKT..
Iterations/ / Ik]0.0
Iterations / [K]os
Figure 55: Results on metries specific to unscrambling (1800 entities). We see a collapse of descriptive and all constraints metrics under a 0.5 scaling exponent: relative constraints are clearly invariant to number of properties.
38000
23200
24400
27600
20600
34000
37230
16150
19000
22800
26000
25200
12460
26000
38800
Avg. Probabiitty R
NLL x [X] iM)-na
Norm, Rank (8)-35
Percent Top K. 1K]"
20
400-
2:43
350
1.40-
0.000
300
2.41
250
0.030
200
1.40
150
1.50
0.020
30
100
1.35
0.535
12-
Iterations/
Iterations / [K]
Iterations/ / [Kg
Iterations/ / /K]05
Figure 56: Results on metrics designed to approximate cluster membership (1800 entities). We see all metrics show an approximate collapse under a 0.5 scaling exponent. Collapse is in the inflection points for the normalized rank and percent top-K metrics.
56

---

Published as a conference paper at ICLR 2025
14800
18000 19610
21300
24400
27600
50500
54000
57209
16400
22500
26200
23200
32400
356.00
36509
Avg. Probability IKp-
Avg. Probabiliy |R]
Avg. Probability 1X22
Avg. Probability x pc22
720-
300
730
302-
620
630
420
400
430
432
300
300
320
332
10
10-1
10-1
Iterations/ [K|2
iterations/ jK]
Iterations/ [K]
Iterations
[K]
Figure 57: Average probability curves for different x-axis rescalings (1800 entities). An exponent between 0.5-1.0 can be expected to induce the best collapse for the metric of average probability; results in Fig. 588 show the exponent is closer to 0.5.
14850
18500
21200
24400
27703
30000
14000
17203
16420
19500
22800
25000
24200
32400
35600
38802
Avg. Probability
Avg. Probability
Avg. Probabil
Avg. Probability
2.5-
1.75
1:75
1/5
50
0.7
0.75
0.75
0:75
0.90
Iterations/ / 1K)
Iterations/ [K(55
Iterations/ / [K]2a
Iterations/ / [K]
Figure 58: Average probability curves for different x-axis rescalings (1800 entities). An exponent 0.5 better aligns the transition points.
G.6.3 CHANGING TO 1800 ENTITIES AND VARYING NUMBER OF PROPERTIES
We change the number of classes to 2 (compared to base setting of 10) and report results under varying number of properties. See Fig. 59 for metries specific to free generation, Fig. 60 for the common metrics that more closely capture a notion of cluster membership, Fig. 61 for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point and its corresponding variant in Fig. 62 where the y-axis is not rescaled to demonstrate the transition points align better with our claimed scaling exponent.
14800
18000
21200
27600
30800
34000
37200
38800
16400
19600
24400
29200
32400
35600
Type Check (Desc.) |
Type Check (Rel.) 1K]00
Type Check (All) [K]2_
1.0
144
344
0.7
10-
12
0.8
0.5
10
0.4
10:
10a
107
101
107
10
10>
Iterations / [K]05
Iterations / 1k]000
Iterations [k|os
Figure 59: Results on metries specific to unscrambling (2 classes). We see a collapse of descriptive and all constraints metries under a 0.5 scaling exponent; relative constraints are clearly invariant to number of properties.
57

---

Published as a conference paper at ICLR 2025
14800
30000
21250
27800
55820
54202
37220
30100
15400
29500
24420
29200
32420
23,00
Avg. Probability rpa
NIL [M] -1.64
Norm. Rank (K)-22
Percent Top-K JK.
1445
0.6
34-
:24
0.7
0.6
25-
25-
0.5
0.4
13
1.38
0.2
0.3
-0-
Iterations/ / [K)0
Iterations/ / 14
Iterations [K)
Iterations / IKP
Figure 60: Results on metries designed to approximate cluster membership (2 classes). We see all metries show an approximate collapse under 0.5 scaling exponent. Collapse is in the inflection points for the normalized rank and percent top-K metrics.
14800
18020
21200
27802
15400
19620
24400
29200
32400
Avg. Probability
Avg. Probability Kq
Avg. Probability [K]
Avg. Probability pq
3.-
23
20
2.0
155
15-
15
15
200
20th
10
20-3
Iterations [K]
Iteraioon 1gjo.
Iterations [K]
Iterations/ [K]
Figure 61: Average probability curves for different x-axis rescalings (2 classes), An exponent between 0.5-1.0 can be expected to induce the best collapse for the metric of average probability; results in Fig. show the exponent is closer to 0.5.
Avg. Probability
14 Avg. Probability
14 Aug. Probability
14 Avg. Probability
12-""
12-"" 12- "Ip-1" "Te""
Iterations/ / P.
Iterationn//
IK]s5
Iterations/ 1ip0
Iterations/ jKIts
Figure 62: Average probability curves for different x-axis rescalings (2 classes), An exponent of 0.5 better aligns the transition points.
58

---

Published as a conference paper at ICLR 2025
Dam
12043.0
K:3-
Baratorn
laradona
(a) 14800 properties
(b) 18000 properties
(c) 21200 properties
0.44
0.3
34330-0 43
43982:52
47685.37
0.0
040
(d) 27600 properties
(e) 32400 properties
38800 properties
Figure 63: Bilinear Spline Fits. Working with the hypothesis that the model's accuracy on unseram- bling descriptive sentences undergoes first saturation regime at low performance, before suddenly changing slope and rapidly improving in performance, we fit bilinear splines to maximally explain these results. The breakpoint identified using these fits is used to define the transition point scaling curve Fig. 64 One can easily see in these curves that the breakpoint is moving rightwards as the number of properties are increased.
H ALTERNATIVE ANALYSIS OF SCALING OF TRANSITION POINT
more conventional analysis of how the transition points scales involves simply identifying the transition point for different experiments, collating the results, and fitting a curve to the identified transition points. We chose the collapse of experimental curves protocol over this method- ology since, except for unscrambling, defining an algo- rithmic objective for curve fitting is difficult. However, at least for unscrambling, we can follow the more usual pipeline and get the curve fits to see if they align with our alternative protocol of collapse of experimental curves.
Transition Point Sealing (wveraged across 3 runs]
Transition point
2x10"
Setup. One can easily see that when the x-axis is log- scaled, both average probability and descriptive sentences accuracy show a scaling curve wherein there is first a saturation low performance, and then sudden (approx- imately) linear growth. Exploiting this pattern, we can simply fit bilinear spline to minimize the mean square error from the data and use the breakpoint of this spline as an approximation to the transition point.
2x50' Number properties
3=20
4xio!
Figure 64: Transition point scaling. Working with the hypothesis that the model's 's accuracy on unscrambling de- scriptive sentences undergoes first satu- ration regime at low performance, before suddenly changing slope and rapidly im- proving performance, we fit bilinear splines to maximally explain these re- sults. The breakpoint identified using these fits is used to define the transition point scaling curve.
Results. We find power law with an exponent of 1.4 explains the data fairly well (see Fig, 644.. That is, the tran- power
sition point, according to this method, scales law in number of properties with an exponent of 1.4. This exponent is fairly close the one identified using the collapse protocol, i.e., 1.5.
For completeness, we also show few of the Bilinear spline fits for descriptive sentences' accuracy as a function of data scaling in Fig. 63
59


Reviews:
[{"review_id": "XfEoujJ4Kt", "reviewer": "Reviewer_dr5M", "summary": "The paper studies emergent capabilities in transformers via two case studies. In the first study, they look at learning of formal languages (in particular, a language generated via a PCFG). For this setting, they train GPT-2 sized models from scratch for:\n-  left-to-right auto-regressive language modeling\n- an unscrambling task that requires the model to take a set of words and convert it into a valid string\n- a conditional generation task that requires the model to generate a sentence that has certain words in it.\n\nAs the model trains they track grammaticality (as measured by whether model generates strings that the PCFG accepts), and if the generated strings follow type constraints. They break down learning into 3 phases, and find that these phases correspond to jumps in the downstream performance (either exact match acc for unscrambling, or loss for language modeling). \n\nIn the second study, they study concept acquisition where entities are associated with types. In particular, they model a concept matrix where row i corresponds to the ith entity, and column j corresponds to the jth type, and the ij entry in the matrix is the probability with which these are seen together. They then define a concept propagation matrix, and use connectedness properties of this propagation matrix to define phase changes. They find that analytic values of these connectedness properties correlate with whether the transformer learns specific concepts.", "questions": "- Do you see similar phase transitions for language learning with smaller models or bigger models? In general, do architecture tweaks change the dynamics in non-trivial ways?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- The paper is extremely well written, and focuses on clearly understanding the phenomenon of emergence (albeit in the limited setting of language modeling of formal languages).\n- Explores a new setting of learning entity type relationship, as percolation on a bipartite graph. I believe such a setting has not been explored before (though i'm not sure how it connects to emergence of skills / behaviors in transformers)", "weaknesses": "Phases of learning: I’m not convinced with the learning dynamics story here. Just because the model can generate accurate sentences does not mean that it has acquired grammar. Understanding whether the model has acquired grammar has been studied previously in NLP: a better method to do this would be to create minimal pairs with one grammatical and one ungrammatical sentence, and check if the model assigns a higher prob to the grammatical sentence. Ofcourse, the design of the minimal pair needs to be well thought-of, to eliminate shortcuts. Here is an example of a minimal pair that checks if a model can produce the correct number for a verb:\n\nS1: The man who likes apples is here\n\nS2: The man who likes apples are here\n\nNot clear what is the point of the percolation model: This seems less about emergence of structure in the model, and more about how at a specific data setting, generalization can happen. I’m not sure what the analogy is between learning type constraints (which is a function of training time), and graph percolation (which is a function of the data properties |E| and |K|). But if the authors can clarify this, i'm happy to increase my score.\n\n\n\nNot clear what are new findings in this paper: \n- Many of the conclusions from this paper are also in Murty et al. 2024, who also train transformer language models on formal languages, and find emergence of the correct learning rule, with extended training. They also find that such emergence happens alongside the emergence of tree-structures in transformers.\n\t\t\n- Similarly, Chen et al. also have a very similar setting but with masked language models, and show that grammar is abruptly acquired, and such grammar acquisition has a causal relationship with downstream performance. \n- There’s also other work by Allen-Zhu et al, who train transformers on formal languages, and find evidence of learnability under some constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "taTcTxx4OB", "reviewer": "Reviewer_NVjv", "summary": "The paper studies the emergence of abilities over the course of training in a transformer language model trained on a formal language. The authors identify distinct phases where different abilities emerge. They also study the point at which one of the abilities transitions from memorization to generalization, and show that this point empirically follows a scaling law that matches the theoretical scaling of bond percolation in a bipartite graph.", "questions": "Is the specific task (free generation/unscrambling/conditional generation) specified to the model somehow, e.g. with a special token?\n\nFor the unscrambling task, is the solution necessarily unique? If not, what's the justification for using exact match/average probability of valid tokens?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The phenomenon of emergence of model abilities with scale, and how suddenly this can occur, is of both scientific and societal importance, together with related questions about the transition from memorization to generalization. The paper studies these using a toy setup that is both similar enough to realistic setups to be interesting, but simple enough to be able to isolate and study both of these phenomena. The theoretical explanation using bond percolation is insightful and deserving of follow-up work.", "weaknesses": "The paper makes claims about \"structures learned by the model\" (in Definition 1 and Section 5.1 Phase 1), but I do not think that these are really justified by the evidence in the main body of the paper, which only look at performance metrics. There is some analysis of attention maps in Appendix F.6. However, the main evidence given there seems to be that there is increased sparsity at partially-trained checkpoints compared to initialization, and other qualitative claims that are hard to read off from the plots. It would be easier to tell if these were quantified, but my impression is that this evidence is rather weak. I also think that if this evidence were stronger, it should be in the main body of the paper, since it would be necessary to justify this prominent claim.\n\nThat being said, I think there is enough interesting material in the paper without looking at model internals, so my suggestion would be to remove or significantly de-emphasize these claims/this aspect of the paper.\n\nMore broadly, I found some of the opening discussion and the definition given in Section 2 a little unnecessary, and took up space that would have been better devoted to explaining the experimental setup and results more clearly, and perhaps covering more results that only made it into appendices. In my opinion it would have been enough to give the high-level motivation, instead of couching it in terms of a new definition that doesn't really add much (especially if the claim about structure in the model is removed).\n\nI also found that at times the presentation got too bogged down in formal details (e.g. Definition 2), and would have preferred to have seen a more accessible, plain-language explanation of things and simple examples, with formal details relegated to appendices for reference if necessary. At other times I found the exposition too rambling (e.g. Section 5.1 Phase 3), and it would have been easier to follow if the main points had been separated out and made concisely (e.g. using bullet points / short headings).\n\nMore minor points:\n- In definition 1 (if you are keeping it), \"nonlinear\" could be confusing (e.g. quadratics are non-linear but still change gradually). Maybe you mean \"discontinuous\"? Or I would perhaps argue that the relevant thing is how gradual the change is (steepness of slope, even if it is locally linear).\n- In definition 2, I would have found it a bit clearer to say that S is a non-terminal symbol, and just say you start from S, instead of treating it as a special case and saying you first map S to other non-terminal symbols – like the definition in Appendix C. (Also, the definition in Appendix C looks messed up, you seem to be swapping between N and NT / Sigma and T, unless I am misunderstanding something.)\n- I found definition 3 hard to follow. E.g. \"Entities have unique identifiers associated with them to help define subjects and objects in a sentence\" - do you mean e.g. \"John\" will have certain attributes like \"tall\", \"brown-eyed\" etc.? Consider using plainer language and an example.\n- Line 227 \"Humans\" vs line 228 \"humans\" - inconsistent capitalization could cause confusion (I assume these are the same thing).\n- Line 260: For the indicator variable, maybe consider \\mathbbm{1} (from package bbm) instead of \\delta (though this is maybe just personal preference)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u2IbhIAH7y", "reviewer": "Reviewer_SNGk", "summary": "This paper  investigates the phenomenon of \"emergence\" in neural networks, where a model suddenly acquires certain capabilities after reaching a critical data or computational threshold. The authors propose a new definition of emergence in neural networks, linking it to the acquisition of general structures within the data that drive sudden performance improvements in specific tasks. The authors experiment with Transformers trained on a context-sensitive formal language and observe that once the underlying grammar and context-sensitivity structures are learned, performance on various tasks improves dramatically. This phase transition in model learning is likened to percolation on a bipartite graph, where learning dynamics mirror phase changes. Their results suggest that emergence can be theoretically predicted by understanding the structure of the data-generating process, offering insights for regulating and anticipating the behavior of AI models.", "questions": "Please refer to the weakness part:\n\n1. Please justify the relationship with previous paper, and the reason why we can still believe the current LLMs have emergence. If the definition is different, please justify the reason why the new definition is equal or a proper approximation of previous ones.\n\n2. Please justify the use of formal languages, and what will happen if we do not train on well-typed formal languages. \n\n3. Please provide more physics intuation of current emergence model. For example, during the freezing of water, the Gibbs free energy of water molecules changes, thereby affecting the intermolecular distance and, on a macroscopic level, the volume. We consider this process to be a phase transition.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Generally, this paper builds a bridge between the LLM and the Physics complex system. The paper uses the phase transition from complex system theory to analyze the emergence of LLMs. This paper has the following strengths:\n\n1. This paper provides a clear definition of emergence, which is slightly differently from previous paper, but it is more formal and general. Also, this definition helps further research the measurement of emergence.\n\n2. This paper trained the LLM from formal languages, which generated from a strict grammar with type check. It aligns with current research.\n\n3. he paper’s findings on emergence and phase transitions are potentially generalizable to other neural network models, not just Transformers trained on formal languages.", "weaknesses": "1. Previous paper[1] has already claimed that the emergence abilities is mirage. The paper does not clearly address contradictions with previous work: why does the phenomenon of emergence still occur in this study?\n\n2. The selection of formal language, though it is very popular in recent researches, but the situation is that the models not trained on formal languages still shows good performance. The observation is not convincing for such situations. \n\n3. In graph theory, diminishing marginal effects are quite common; however, there is no clear evidence linking this to the percolation model proposed in this paper. Many graph-theoretic functions exhibit properties such as submodularity, which is one of the reasons behind these phenomena. The final emergence modeling presented in this paper is not entirely intuitive.\n\n[1]Schaeffer R, Miranda B, Koyejo S. Are emergent abilities of large language models a mirage?[J]. Advances in Neural Information Processing Systems, 2024, 36.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z1Kiaj17s1", "reviewer": "Reviewer_Wp3H", "summary": "This paper studies emergence of structure and capabilities of a small transformer throughout training on a formal language dataset.\nThey identify certain phase transitions correlate with the emergence of capabilities to do specific tasks.\nThey then propose a formulation to predict phase transitions where emergent capabilities, and find that it aligns well with the formal language toy setting.", "questions": "There was a discussion about order parameters early on in the introduction, but this was then ignored until the last paragraph of the conclusion. Can you clarify how your definition of order parameters are different than/related to \"progress measures\" that others have proposed to study phase transitions (e.g. [3,4])?\n\n___\n[3] Barak, et al. Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit. 2022. (https://openreview.net/forum?id=8XWP2ewX-im)\n\n[4] Nanda, et al. Progress measures for grokking via mechanistic interpretability. 2023. (https://openreview.net/forum?id=9XFSbDPmdW)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and a pleasure to read. The paper seems to be also placed well in the context of previous and current related work on emergence. Emergence is an interesting topic for the community, and this paper provides a nice background and definition for studying it in terms of training data. And, while the setting studied is simple, the findings are well supported by their experiments, and the appendix has well-detailed additional evidence.", "weaknesses": "There are other aspects of emergence that are not investigated here that need further study. This paper studies emergence over training data scaling, but they mention other axes (e.g. compute or parameter size) that I feel are also important to make more general claims regarding emergence. While the results in this paper are reasonable for the chosen setting, it is unclear whether they will hold in other settings and data choices.\n\nI also wanted to point out a few (recent) papers there are missing from related work, but seemed relevant. The first is Singh, et al.'s [1] work that studies phase transitions of learning subcircuits for in-context learning tasks. The second is Tigges, et al. [2]'s work, which studies how known circuits evolve in the Pythia suite of models over the course of training.\n___\n[1] Singh, et al. What needs to go right for an induction head? A mechanistic study of in-context learning circuits and their formation. 2024. (https://proceedings.mlr.press/v235/singh24c.html).\n\n[2] Tigges, et al. LLM Circuit Analyses Are Consistent Across Training and Scale. 2024. (https://openreview.net/forum?id=1WeLXvaNJP)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)