A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Language

## Abstract

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 specific structures 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 structures 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 experiment when changing the data structure.
Overall, our experimental and theoretical frameworks yield a step towards better defining, characterizing, and predicting emergence in neural networks.

## 1 Introduction

Modern neural networks, e.g., large language models (LLMs) (Gemini Team, ; OpenAI, ; Anthropic, ; Touvron et al., ), exhibit a broad spectrum of capabilities, allowing them to serve as the “foundation” for downstream, application-specific systems (Bommasani et al., ; Ahn et al., ; Driess et al., ; Schick et al., ).
As these models scale, either via addition of more data, parameters, or compute, an intriguing behavior is at times observed: until a certain critical scale is reached, there are capabilities that the model does not exhibit; however, beyond this point, such capabilities can suddenly “emerge” (Wei et al., ; Srivastava et al., ; Brown et al., ; Yu et al., ; Steinhardt, ; Pan et al., ; Rae et al., ; Anil et al., ; Kirsch et al., ; He et al., ; Elhage et al., ).
More specifically, the performance of the model on a task or benchmark meant to evaluate said capabilities can witness substantial growth in performance, even though the overall training loss undergoes minimal, if any, improvements (Arora & Goyal, ; Du et al., ).
Empirical evidence in fact suggests that, at times, several capabilities can emerge simultaneously (Wei et al., ; Wei, ).

Beyond developing a better scientific understanding of neural networks, understanding emergent capabilities is crucial to enable risk-centric regulation frameworks for AI, which assume a system’s capabilities can be preemptively conjectured (AI, ; Council of the European Union, ; OSTP, ; Anwar et al., ; Kaminski, ; Ganguli et al., ).
To this end, recent work has made attempts at identifying factors that decide whether a capability will emerge.
For example, Okawa et al. () and Arora & Goyal () implicate the underlying compositional structure of a capability as the cause for its sudden learning.
Hoffmann et al. () argue capabilities that involve interactions between specialized components within a 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 to enable in-context learning (Elhage et al., ; Olsson et al., ; Reddy, ).
Meanwhile, Schaeffer et al. () argue emergent abilities are an artifact of poorly defined, discontinuous evaluation metrics, 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 a new capability (Chen et al., ; Du et al., ; Cui et al., ).
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 in machine learning.
At its core, however, we claim that the concept has never been defined in prior 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 to capture in the context of neural networks?
Is it merely a sudden increase in performance with scale, or broader than that?
Given a reasonable definition, can we show, even if in a simplified system, that emergent capabilities are commonplace and can we use the system’s simplicity to better understand what drives their sudden learning?

Figure: Figure 1: Emergence as phases of learning. Emergence is a well-characterized phenomenon in natural sciences (Anderson, ; Newman et al., ; Newman, ) and deeply entangled with the notion of phase changes: when a change in some control variable (e.g., temperature) yields systematic changes in a system’s underlying structure (e.g., hexagonal configurations in a crystal), simultaneously affecting several of its properties and necessitating study of each phase independently. We argue for a similar characterization of emergence in machine learning: identifying systematic changes in a model’s behavior that influence its downstream abilities and lead to sudden performance improvements. For example, learning a language’s syntax will affect all downstream capabilities where coherent, grammatically correct generations are necessary.
Refer to caption: /html/2408.12578/assets/x1.png

This work.
To address the questions above, we propose a phenomenological definition for emergence and try to understand what drives it in a toy task of learning formal languages (Chomsky, ; Allen-Zhu & Li, ; Cagnetta & Wyart, ; Liu et al., ; Wen et al., ; Liu et al., ; Friedman et al., ; Jain et al., ; Merrill et al., ).
Specifically, we argue three characteristics should be observed to claim a capability is emergent (see Def. [1](#Thmtheorem1)): beyond (i) sudden performance improvement for a specific task, we claim emergence is more likely to represent a meaningful concept if (ii) performance on several tasks improves simultaneously and (iii) there are precise structural changes in the model at the point of emergence.
The intuition, borrowed from the study of emergence in other fields (see Fig. [1](#S1.F1)), is that if multiple tasks witness improvement in performance, there is likely some shared structure to them and the model acquires this structure at the point of emergence.
For example, when in-context learning emerges in LLMs, precise context-sensitive structures emerge and interact with general-purpose capabilities, leading to in-parallel improvement in several downstream tasks’ performance (Wei, ; Wei et al., ; Lu et al., ; Guo et al., ; Hendel et al., ); 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 structures the model acquires at the point of sudden learning of a set of capabilities, and understanding why that structure is relevant to said capabilities.
Adopting this viewpoint, we make the following findings in our experiments.

- •
Formal Languages as an Experimental System for Studying Emergence.
We define a probabilistic 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 a predefined set of properties (e.g., walk). We train models to perform minimalistic reasoning tasks over samples of this language and find their data scaling curves simultaneously show sudden learning across several metrics.
- •
Learning of general data structures underlies simultaneous jumps in specific metrics.
We find points of sudden change for metrics evaluating individual tasks correlate with the model learning two relevant structures that underlie the language: grammatical rules and type constraints. Despite the simplicity of our setup, we claim learning of such general structures is what leads to sudden growth in the performance of narrower tasks where these structures are important.
- •
A percolation model predicts the scaling of when capabilities emerge.
We propose a formal model grounded in the theory of graph percolation (Cohen et al., ) that captures our experimental observations, and show that if we can describe the structure the model is learning at the point of emergence, a predictive theory for sudden learning can (at times) be constructed—analogous to theories of phase transitions in physics; see Fig. [1](#S1.F1).

## 2 Related work

Explaining emergence.
Focusing on the sudden learning characteristic of emergent capabilities, a few recent works have tried to explain the factors driving this phenomenon.
For example, compositionality has been implicated for having a “multiplicative” effect on a model’s performance, where the argument is that a model cannot perform well on a compositional task until the abilities needed to perform individual tasks involved in that composition are acquired (Okawa et al., ; Arora & Goyal, ; Yu et al., ; Srivastava et al., ; Wei et al., ; Hoffmann et al., ; Gokhale, ); when they are acquired, performance suddenly grows.
A few papers have also shown that learning of specific capabilities (i.e., ones not compositional in nature) can be sudden (Chen et al., ; Nam et al., ; Kirsch et al., ; He et al., ; Michaud et al., ).
In contrast, Schaeffer et al. () argue emergent scaling curves are a consequence of poorly defined, discontinuous evaluation metrics, and the seemingly sudden learning goes away once partial, continuous credit is given to the model.
We emphasize that 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 to help measure progress toward learning a task.
For example, consider the addition of two numbers, say $10$ and $11$, and the metric called token edit distance (Schaeffer et al., ) that assesses the average distance between digits in the model’s output, denoted $\mathtt{xy}$, from the ground truth, i.e., $\nicefrac{{\left(|\mathtt{x}-2|+|\mathtt{y}-1|\right)}}{{2}}$.
For both $\mathtt{xy}=22$ and $\mathtt{xy}=11$, this metric equals $1$; however, clearly $22$ is a better approximation for the ground truth ($21$).
Thus, 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 a metric for assessing a model’s ability to add numbers.
We argue claims relating emergence to sensitivity of metrics can be confounded by use of metrics that do not respect the structure of the task.

Grokking vs. Emergence. We focus on the effect of data scaling on a model’s capabilities; often called ‘learning curve’ or ‘data scaling’ analysis (Viering & Loog, ; Blumer et al., ; Bousquet et al., ; Seung et al., ; Watkin et al., ; Amari, ; Haussler et al., ).
On surface, this might look similar to the seemingly related phenomenon of grokking (Power et al., ; Liu et al., ; Žunkovič & Ilievski, ; Murty et al., ; Barak et al., ; Edelman et al., ; Nanda et al., ), wherein a model’s performance on a task rapidly improves long after it has fit the training data.
However, we emphasize that we focus on an online learning setting in our experiments, i.e., 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 (Nanda et al., ; Liu et al., ) are unlikely to help explain our results of emergence under data scaling.

## 3 A Phenomenological Definition of Emergence

To analyze emergence, we first establish what we mean by the term for the purpose of this work.
Specifically, we define emergence in a phenomenological manner, i.e., by assembling the characteristic properties associated with scaling curves claimed to depict emergent learning.
We emphasize our definition is merely a definition for emergence, and does not necessarily represent all possible perspectives (Luccioni & Rogers, ).
For example, often model capabilities that arise despite any explicit supervision are called emergent in self-supervised learning (Caron, ; Caron et al., ; Ziyin et al., ).
As our goal is to analyze the effects of scaling, regardless of supervision protocol used, we do not try to capture this property.

###### Definition 1 .

(Emergence of a capability.) We say a capability $\mathcal{C}$ is emergent with scaling along a relevant axis (e.g., amount of data, compute, parameters) if:

- •
P1: nonlinear improvement occurs in the performance of a task where $\mathcal{C}$ is required;
- •
P2: multiple tasks simultaneously show nonlinear performance improvement; and
- •
P3: the model undergoes a structural change that is instrumental to learning the capability $\mathcal{C}$, and nonlinear progress in $\mathcal{C}$’s learning directly correlates with the learning of said structure.

The definition above assigns a broader meaning to emergence than mere sudden performance improvement on a narrow task: it argues there should be precise structural changes in the model that have downstream effects on several capabilities, hence leading to sudden improvements in performance on several tasks.
Note that we intentionally leave the notion of ‘structure’ informal in the definition.
The salient property of a structure is that if a model learns it, downstream tasks should become easier to perform.
For example, a fine-grained notion of a structure can be previous token and copy attention heads that lead to in-context learning (Reddy, ; Edelman et al., ; Olsson et al., ); a more coarse-grained structure can include the model learning the syntactical rules of a language that help it with generation of coherent language and hence with any task where coherence is important (Chen et al., ).
In this sense, what is emergent is a structure, and what is observed is a change in the model’s capabilities.
Hypothesizing what this structure is by identifying shared characteristics of a set of tasks that simultaneously show sudden learning, one can develop an evaluation meant to precisely gauge learning of the corresponding structure and hence infer at what point an independent training run will show sudden improvements.

We note the intuition for Defn. [1](#Thmtheorem1) comes from prior work in the fields of complex systems and physics (Anderson, ; Newman et al., ; Newman, ), from where the term has sought its inspiration in recent machine learning literature (Steinhardt, ; Wei et al., ).
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 properties change relatively smoothly is called a phase, and a change of phase with a change in the control variable is called a phase transition.
A crucial step in studying emergence in physics is identifying an *order parameter*—a measure that captures the formation of some specific structure in the system such that the development of this structure is what alters the system’s properties and drives a phase transition.
For example, in Fig. [1](#S1.F1)a, a system of particles transitions through phases (solid, liquid, gas) as the temperature is changed; the formation of a crystalline structure with the decrease in temperature can be identified by analyzing the bond-orientation order parameter, while the liquid-to-gas 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.e., we must develop evaluation measures that are focused towards detecting the learning of specific, narrow structures that are generally of use to several downstream capabilities.

###### Definition 1 .

## 4 Formal Languages as an Experimental System for Emergence

Figure: Figure 2: Grammar and type constraints to define our formal language. (a) We use a PCFG to define our language’s grammar (shown rules are examples; see App. [D.3](#A4.SS3) for precise details). The grammar’s terminals are parts-of-speech from English and yield symbolic sentences that can be populated by tokens from the language’s vocabulary. (b) Akin to natural language, wherein properties of an 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 a sentence. These constraints map entities to descriptive or relative properties, hence restricting which descriptive adjectives and verbs are valid for an entity. (c) Once a 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. [D.2](#A4.SS2)).
Refer to caption: /html/2408.12578/assets/x2.png

Having established our perspective on emergence, we now define a toy experimental system that allows us to precisely study the concept in a 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-Zhu & Li, ; Jain et al., ; Allen-Zhu & Li, ; Valvoda et al., ; Liu et al., ; ).
As discussed in detail next, the formal language we use in this work is (minimally) context-sensitive, with underlying syntactical rules defined using a context-free grammar and context-sensitivity enabled through posthoc type constraints.
The grammar and type constraints serve as two structures that underlie our language, and, as we show in Sec. [7.2](#S7.SS2), their learning bottlenecks learning of other, narrower capabilities.

###### Definition 2 .

(Grammar.)
Consider a set of symbols $\mathtt{T}$ (also called terminals).
A symbolic string $\sigma$ is designed by chaining symbols from $t\in\mathtt{T}$; e.g., $\sigma=t_{1}t_{2}\dots\mathtt{EOS}$, where $\mathtt{EOS}$ is a special symbol that marks the end of string $\sigma$.
The set $\mathtt{T}^{*}$ denotes all possible strings defined using symbols from $\mathtt{T}\cup\mathtt{EOS}$.
Meanwhile, a set of symbols $\mathtt{NT}$ (also called non-terminals) define production rules $\mathtt{Q}$ of the grammar, represented as $A\to\alpha\beta$, where $A\in\mathtt{NT}\cup\mathtt{S}$ is called the LHS and $\alpha,\beta\in\mathtt{T}\cup\mathtt{NT}$ is called the RHS of the rule, and $\mathtt{S}$ denotes a special ‘start’ symbol.
A probabilistic context-free grammar $\mathtt{G}$ is defined as a randomized process that first maps $\mathtt{S}$ to a set of non-terminals according to rules $\mathtt{Q}$, and then repeats the process over these intermediate non-terminals by randomly sampling rules for which previously sampled non-terminals are the LHS.
The process continues until only terminal symbols constitute the RHS.
This yields a string $\sigma\in\Sigma$, where $\Sigma\subset\mathtt{T}^{*}$ denotes the set of all strings that can be sampled from $\mathtt{G}$.
We say a randomly sampled string $\sigma\in\mathtt{T}^{*}$ is grammatical if $\sigma\in\Sigma$.

For an overview, see Fig. [2](#S4.F2) (a) or App. [A.1](#A1.SS1). The terminal symbols used in our work include standard parts-of-speech from English, specifically: subjects, objects, verbs, adjectives, adverbs, conjunctions, determiners, and prepositions.
This implies multiple short phrases can be combined together via conjunctions and verbs (e.g., a verb can connect a subject phrase and an object phrase).
We often use the term ‘entities’ to jointly refer to subjects and objects.
We also distinguish between attributive and predicative adjectives, using the term adjectives to solely refer to adjectives that are attributive in nature and the term ‘descriptors’ to refer to adjectives that are predicative.
Overall, the grammar $\mathtt{G}$ yields symbolic strings that are solely comprised of parts of speech.
For example, our grammar might yield a string like adjective subject adverb verb preposition adjective object.
We next map these symbolic strings to our language.

Let $\mathcal{V}$ denote the vocabulary of our language $\mathcal{L}$. Each token $v\in\mathcal{V}$ has a symbolic role $t\coloneqq\mathtt{role}(v)$ associated with it. The set of possible roles is denoted $\mathtt{T}$, which is equal to the set of terminal nodes of grammar $\mathtt{G}$.
Thus, one can define a context-free language by simply sampling a string $\sigma$ from $\mathtt{G}$, and then replacing its terminals with tokens from the vocabulary that match the roles specified by symbols in $\sigma$.
For example, the example string above can be resolved as Tall man slowly walked to short building.
However, natural language is rich with constraints defined by the physical properties of an entity, which thereby restrict which tokens are seen in the context of which other tokens, hence yielding context-sensitivity.
For example, one does not expect to see a sentence Tall telephone slowly walked to short building, since the entity telephone is neither expected to be tall nor to walk.
We develop an abstraction for such constraints by representing them as a bipartite graph (see Fig. [2](#S4.F2) (b,c)).

###### Definition 3 .

(Type Constraints Graph.)
Let a property $\mathtt{k}$ be a binary variable; the set of all properties is denoted $\mathtt{K}$.
Properties can be either descriptive (used to define descriptors; e.g., tall) or relative (used to define verbs; e.g., walk).
A concept class $\mathtt{C}$ is defined via the set $\mathtt{K}_{\mathtt{C}}\subset\mathtt{K}$ that denotes which properties are valid for that class.
When the properties in $\mathtt{K}_{\mathtt{C}}$ take values, we get an entity $e$ from the class, denoted as $e\in\mathtt{C}$.
Entities have unique identifiers associated with them to help define subjects and objects in a sentence.
The set of all possible entities is denoted $\mathtt{E}$. The type constraints graph $\mathcal{G}:=(\mathtt{E},\mathtt{K},\mathtt{I})$ is a bipartite graph over entities and properties in the language whose edges $\mathtt{I}$ denote whether an entity $e\in\mathtt{E}$ possesses property $\mathtt{k}\in\mathtt{K}$.

As an example, consider the class of Humans, which includes entities connected to properties like tall, right-handed, 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.e., which descriptors and verbs go with an entity, hence yielding context-sensitivity and making $\mathcal{L}$ a probabilistic context-sensitive language.
Given two randomly sampled entities from the same class, they can be expected to share a subset of values, giving a signal to the model trained on $\mathcal{L}$ that these entities are related (i.e., they belong to the same class).

###### Definition 2 .

###### Definition 3 .

## 5 Learning Tasks and Experimental Setup

Figure: Figure 3: Task definitions. Our model is trained and evaluated 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 a set of entities or properties and must generate valid sentences using them. Note that examples in the figure are merely indicative. See App. [A.1](#A1.SS1) for details.
Refer to caption: /html/2408.12578/assets/x3.png

Having described our language $\mathcal{L}$, now we briefly discuss our experimental setup (see App. [C](#A3) for details).
We train a GPT architecture model (Andrej Karpathy, ) with the standard autoregressive language modeling objective.
Data is sampled “online”, i.e., we sample a fresh batch of strings every iteration from $\mathcal{L}$.
Unless mentioned otherwise, $\mathcal{L}$ is constituted of $|\mathtt{E}|=900$ entities and $|\mathtt{K}|=18000$ properties, equally and disjointly distributed over $|C|=10$ classes, and with edges connecting entities to $p=0.1$ fraction valid properties of a class in a uniformly random manner; results ablating these settings are in App. [D](#A4).
Before being fed into the model for training or evaluation, strings sampled from the language are restructured into a format that enables the specification of particular tasks (see Fig. [3](#S5.F3)).
Specifically, we train the model to learn the following tasks with 80/10/10% splits.

- •
Free generation: Produce a valid string, i.e., one that respects the grammar and type constraints.
- •
Unscrambling: A string is sampled from $\mathcal{L}$ and randomly permuted; the model is expected to unscramble it. This task is known to show sudden learning in LLMs (Wei et al., ).
- •
Conditional Generation: A set of tokens corresponding to entities or properties are shown to the model, which is expected to generate a string combining these tokens in a valid manner.

Evaluation Protocols.
Given an input $x$, which may correspond to any of the three tasks above, denote the model output as $f(x)$. Let $\delta(.)$ be an indicator variable that evaluates to $1$ if its input is true. We track several metrics throughout training, as described below. We often decompose these evaluations according to strings of two types: (i) descriptive, i.e., that describes that an entity possesses a descriptive property, and (ii) relative, i.e., that claims a subject, object, and verb can match each other to create a valid sentence. Unless noted otherwise, results are averaged over 3 seeds.

- •
Grammaticality/Type Check. Used for evaluating free generation. Grammaticality involves checking whether model output follows the underlying grammar $\mathtt{G}$, i.e., $f(x)\in\Sigma$. Type checks involve first extracting subjects, objects, and properties from the 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 $l$ tokens. We compare whether the model output exactly matches the ground-truth $\left(\Pi_{i=1}^{l}\delta(y_{i}=f(x)_{i})\right)$ or the per-token match ratio $\left(\nicefrac{{1}}{{l}}\sum_{i=1}^{l}\delta(y_{i}=f(x)_{i})\right)$.
- •
Conditions Satisfied. Used for evaluating conditional generation. If the model is expected to produce a sentence with $m$ conditioning tokens $\{v_{c_{1}},\dots,v_{c_{m}}\}$, we analyze how many of those tokens are present in $f(x)$, i.e., we evaluate $\nicefrac{{1}}{{m}}\sum_{i=1}^{m}\delta(v_{c_{i}}\in f(x))$.
- •
Average Probability of Valid Tokens. Used for evaluating descriptive type constraints in free generation and unscrambling. Specifically, we sample a sentence from $\mathcal{L}$ that remarks on an entity possessing a 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 $x=$ The fire was large. We evaluate $\mathtt{Pr}\left(\delta(f(x)_{1}=\mathtt{large})|x_{-1}\right)$, where $x_{-1}$ denotes the sentence up to the last token and $f(x)_{1}$ denotes the first token predicted by the model.

Miscellaneous Evaluations. We also perform several other evaluations (see App. [D](#A4)), e.g., computing log-likelihoods of valid versus adversarially perturbed 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; analyzing grammaticality and type check accuracy for unscrambling and conditional generation; rank of property predictions; and the evolution of attention maps across time.

## 6 Results: Emergent Capabilities in Formal Language Learning

We now evaluate (i) whether our setup demonstrates emergence (see Def. [1](#Thmtheorem1)), and (ii) whether we can extract insights into the mechanisms of what leads to emergence.
In the following, we often use the terms “phase” and “phase change”; see discussion around Def. [1](#Thmtheorem1) for context on these terms.

Figure: Figure 4: Learning of structures drives emergent capabilities. For a detailed discussion, see main text. (a) Grammaticality and Type Check evaluations as a function of iterations or data (iterations$\times$batch-size). We see phases in the learning dynamics corresponding to emergent acquisition of structures underlying our language: grammar (black), relative type constraints (pink), and descriptive type constraints (green), shaded gray, pink, and green respectively. (b, c) 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 acquisition of structures. (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.
Refer to caption: /html/2408.12578/assets/x4.png

### 6.1 Phases of Language and Capabilities Acquisition

We plot the model’s performance as a function of training iterations.
Since we are in an online learning, constant learning rate setting, this analysis corresponds to studying the effects of data scaling.
Results are reported in Fig. [4](#S6.F4) and show there are three phases to the learning dynamics.

Phase 1: Grammar acquisition. We find the model first learns to produce grammatically correct sentences, as measured by the grammaticality measure defined in Sec. [5](#S5).
This process is relatively rapid, as we see the model starts generating grammatically accurate sentences in a short period of approximately $100$ iterations; attention heads also rapidly evolve and reflect the parse structure of a sentence (see App. [D.6](#A4.SS6))
In this regime, however, the narrower tasks of unscrambling 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 a broad structure underlying the data (i.e., grammar) has an impact on the learning of other capabilities.

Phase 2: 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, show 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 structure underlying the data is acquired, the model rapidly learns the next relevant structure of relative type constraints.
Improvement occurs in descriptive constraints as well (and hence the overall Type Check performance), but hovers around slightly above random performance of $0.1$.
With $|C|$ classes, if a model produces grammatically correct sentences, it will achieve a random performance of $\nicefrac{{1}}{{|C|}}$ on descriptive type checks.
This however also implies that the model is primarily relying on its syntactical knowledge and does not respect descriptive type constraints much.

During this phase, we see that shortly after the phase change, there is a sudden increase in performance for both unscrambling and conditional generation, across all metrics.
These tasks’ losses also show another loss drop occurs at this point; though the drop seems smoother in the total loss, likely due to averaging effects (Michaud et al., ).
As shown in Fig. [4](#S6.F4)e, 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. [4](#S6.F4): once grammar and relative type constraints are learned, the model learns to use them to solve inputs that do not require knowledge of descriptive properties, leading to a sudden improvement in both loss and accuracy.

Phase 3: Learning of descriptive type constraints.
During Phase 2, we find that the model’s performance on descriptive type checks witnesses minimal improvement.
However, as training proceeds, the model enters a third phase at whose boundary we see a sudden change of slope from a saturation region to approximately linear 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 unscrambling 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. [4](#S6.F4)), we see there is in fact a 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^{4}$ iterations up to this point, if we assume the model can perfectly learn in only a 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. [C.0.1](#A3.SS0.SSS1); 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 a much larger rate of improvement and reaches $\sim$30–35% performance, indicating it is generalizing beyond the pairs of entities and objects it has seen together during training.
If the model were simply relying on memorized knowledge, the performance values we observed would not be feasible.
We thus claim that the model is implicitly inferring, based on the structure of the type constraints graph, which properties and entities constitute a valid context.
This suggests a memorization effect is at play during Phase 2, and the phase boundary corresponds to a transition from a memorizing to a generalizing solution.

Takeaways. While the results above are for a specific configuration, we find the claims consistently generalize to an extremely broad array of experimental settings (see App. [D](#A4)).
Specifically, we consistently see that the model first learns the two structures underlying our language (grammar and type constraints), and then witnesses performance improvements on narrower tasks in the data.
Drawing on the physics analogy before, we emphasize that in this sense grammaticality and type constraints serve as our order parameters (here order is the grammar and types), and are sufficient to approximately predict when sudden performance improvements will be seen for a task.
We also note that our results are not sensitive to specific choice of metrics, as shown by loss curves and several other metrics discussed in App. [D](#A4).

Figure: Figure 5: Effect of scaling number of descriptive properties. Scaling the number of descriptive properties in our language (see legend), we find relative type checks and unscrambling performance for relative sentences are essentially unaffected by the number of properties. Meanwhile, both type check and unscrambling performance for descriptive constraints and sentences show a change in performance and delay in transition points (most prominently seen for the delay in the emergence of unscrambling ability). Despite these effects, we find the geometry of performance curves is extremely consistent; for descriptive type checks, this geometry aligns indicates a memorization to generalization picture.
Refer to caption: /html/2408.12578/assets/x5.png

### 6.2 Effect of Number of Descriptive Properties on Language Acquisition

Given the above picture of a model’s learning dynamics, we next ask how the phase boundaries change with an increase in the number of properties $|\mathtt{K}|$ (see Fig. [5](#S6.F5)).
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. [D.2](#A4.SS2)), which, as expected, is not affected by $|\mathtt{K}|$ since it is an entirely independent structure from type constraints.
However, we see even relative type constraints’ learning is not affected by the increase in descriptive properties, indicating the model deems them (justifiably) to be independent structures whose learning does not interact with each other.
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 base setting studied in Sec. [6.1](#S6.SS1), indicating despite the increase in difficulty of the task, the same learning dynamics are at play. We devote the next section to formulate a hypothesis justifying these observations.

## 7 A Percolation Model of Emergence

We next propose a framework for modeling the emergence of capabilities that require a model to compose unseen entities and descriptive properties, e.g., learning descriptive type constraints, which, beyond allowing a model to produce accurate free generations, will aid with narrower tasks like conditional generation and unscrambling.
We argue the relevant structure to analyze for this purpose is the concept class: if a model understands what entities and properties belong to the same concept class, regardless of whether they have been seen together in a sentence, it will deem their co-occurrence to be valid.
We thus develop an abstraction for concept classes as bipartite graphs and cast their learning as a problem of percolation on a bipartite graph.

### 7.1 Matrix representation of data and learning compositions

Figure: Figure 6: Casting the ability to compose unseen concepts (e.g., 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., entities 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 can be connected, forming a single cluster (right). This suggests that a model can compositionally generalize to most concept classes with enough edges and inference steps. (c) Our formalism establishes this transition as a 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. [5](#S5) or App. [C](#A3)).
Refer to caption: /html/2408.12578/assets/x6.png

Recall that a concept class is defined as a set of entities that are expected to have shared properties (see Def. [3](#Thmtheorem3)).
The question is whether upon sub-sampling pairs of entities and properties from a concept class, can the model learn that, in fact, all pairs of entities and properties are valid and compose the concept class.
For instance, in the case of a concept class such as human, the set of entities can include humans with different genders (e.g., man) as well as human-associated entities such as a lawyer (see Fig. [2](#S4.F2)). The corresponding properties for the human concept class will be, for example, walk, jump, tall. A man, being human, is expected to have all these properties, although strings specifying these properties for a 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, such as an entity-descriptor pairing.
We call this matrix the concept density matrix.

###### Definition 4 .

(Concept Density Matrix.) Let $D$ be an $|\mathtt{E}|\times|\mathtt{K}|$ matrix with real-valued entries between 0 and 1, inclusive. Each entry $D_{ek}$ represents the density for the entity and property pair $(e,k)$ (e.g., the amount of data that represents the specific composition), where $e\in\{1,...,|\mathtt{E}|\}$ and $k\in\{1,...,|\mathtt{K}|\}$ are the indices of the entities and properties, respectively.

For example, consider the case where there are three values of entities and properties ($|\mathtt{E}|=|\mathtt{K}|=3$), with entities (rows) being {Man, Lawyer, Telephone}, and properties (columns) being {Walk, Stoic, Ring}. The corresponding $D$ can be:

$$ $\displaystyle D=\begin{pmatrix}1&1&0\\ 1&0&0\\ 0&0&1\end{pmatrix}.$ (1) $$

A common composition such as Man walking will lead to a value of 1 at the intersection of Man and Walk, i.e., $D_{00}=1$, where $D_{ij}$ denotes element at row-$i$ and column-$j$.
Conversely, a highly unlikely composition like Lawyer ringing will be absent in the dataset, and will be represented by a zero at the respective matrix position, i.e., $D_{12}=0$.
We can also assume for example that Man ringing or a Telephone walking are rare, which yields $D_{13}=D_{31}=0$.

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\geq 0$) is defined as $T^{(n)}=(DD^{T})^{n}D=C^{n}D$, where $C:=DD^{T}$.

The concept propagation matrix can be intuitively understood using a bipartite graph, as shown in Figure [6](#S7.F6)a. A bipartite graph in this case is a sub-graph of the type constraints graph (see Def. [3](#Thmtheorem3) and Fig. [2](#S4.F2)), where one set of nodes represents entities while the other represents properties, with edges indicating 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^{(n)}$.
Specifically, if two concepts are connected by a path of minimal length $2k+1$ (i.e., the shortest path between them alternates between the two sets $k$ times), the corresponding entry in $T^{(n)}$ becomes non-zero only for $n\geq 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 disconnected regions of the graph, their composition remains fundamentally unlearnable, regardless of the order of propagation, indicating that composition is not valid.
This is reflected by the corresponding entry in $T^{(n)}$ 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 ringing) 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 are both humans, whereas Telephone is not.
Our experiments in the formal language setup show that the model deems sentences composing entities and properties from incorrect classes to be much less likely than the correct ones (see Fig. [D.3](#A4.SS3)).

###### Definition 4 .

###### Definition 5 .

### 7.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 a 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 $T^{(\infty)}_{ek}$ is non-zero, out of the total possible pairs $|\mathtt{E}|\times|\mathtt{K}|$. 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=p_{c}$, called the percolation threshold. Below this threshold ($p<p_{c}$), 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>p_{c}$), the graph transitions to a connected phase, significantly increasing the likelihood of a vast connected component spanning a large portion of the graph. This shift from a predominantly disconnected state to one with a macroscopic cluster is a defining characteristic of the percolation process, and this transition sharpens as the number of components in the system increases. See Fig. [6](#S7.F6) for a schematic.

In a simple percolation scenario, where connecting edges are selected randomly on the graph with probability $p$, the percolation threshold is obtained as $p_{c}\simeq\sqrt{1/|\mathtt{E}||\mathtt{K}|}$ for large $|\mathtt{E}|$ and $|\mathtt{K}|$ (Newman et al., ), which means that when around $\sqrt{|\mathtt{E}||\mathtt{K}|}$ edges are connected (out of the total $|\mathtt{E}||\mathtt{K}|$) there is a qualitative change in the growth of the cluster size.
For $p>p_{c}$, the number of nodes included in the connected cluster will become macroscopic, meaning that the probability that a randomly selected pair of an object and a feature is connected will be finite.
We present in Appendix [B](#A2) the derivation of the percolation threshold for bipartite graphs that are uncorrelated, and how the cluster size (i.e., number of nodes in the largest connected graph) scales as $\sim(p-p_{c})^{\beta}$ with $\beta=1$ for usual cases.

We posit that the percolation threshold corresponds to the point at which our model generalizes from the sparse learning of pairs to a complete representation of the concept classes. When the number of edges surpasses the threshold, the model can infer novel compositions, even for entity-feature pairs that were not explicitly present in the training data.
The model should also start to be able to discriminate between distinct concept classes beyond this threshold; in the community detection problem, for example in the stochastic block model (Abbe, ; Decelle et al., ), the detection threshold for the partitions have the same scaling as $p_{c}$ Florescu & Perkins (). Since increasing the iterations through online learning should amount to increasing $p$ (i.e., seeing more combinations in data), the iteration point at which the transition occurs in the model performance should be proportional to $\sqrt{|\mathtt{E}||\mathtt{K}|}$.

To check whether such theoretically predicted scaling can be seen in our experiments with formal language learning, we plot again the various performances of the model as a function of iterations divided by the square root of the number of properties, since we keep the number of objects constant in these experiments.
Results are shown in Fig. [7](#S7.F7).
We find that indeed there is a 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 $\sqrt{|\mathtt{K}|}$.
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 $|\mathtt{K}|$ (see Fig. [5](#S6.F5) and Fig. [52](#A5.F52)), 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. [17](#A4.F17)).

Figure: Figure 7: Scaling of point of emergence matches with our theory. We replot the result from Fig. [5](#S6.F5) by rescaling the x-axis with a power of the number of descriptive properties; See App. [E.1](#A5.SS1) for further discussion on the intuition underlying this visualization. For Average probability of generating a valid descriptive property given some object in context under free generation and descriptive type check accuracy, we see a 0.5 exponent scaling yields a collapse of the transition point—this matches the toy model of percolation posited in Sec. [7.2](#S7.SS2). We also see a very clear scaling of the point where the ability to unscramble descriptive sentences starts to emerge, but with an exponent of 1.5.
Refer to caption: /html/2408.12578/assets/x7.png

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 $|\mathtt{K}|^{3/2}$.
We so far do not have an explanation for this scaling, but we assume it is likely due to the learning of other mechanisms, as it seems to be sensitive to other characteristics of the language; e.g., when we increased $|\mathtt{E}|$ from 900 to 1800, the exponent shifted from $3/2$ to close to $2$ (see Fig. [44](#A5.F44)), but remained $0.5$ for descriptive type checks (see Fig. [54](#A5.F54)).
Given the task involves the composition of entities and properties too, we expect a transition and scaling effect to occur for unscrambling as well; however, learning the precise circuit to perform unscrambling over the learned grammar and type constraints will yield a delay (as was seen in experiments) that likely has some interaction with the complexity of the language.
We leave explaining this scaling for future work.

## 8 Conclusion

In this work, we 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 at the point of emergence, the model acquires broad structures which are instrumental to the learning of specific, narrower capabilities; acquisition of such structures then leads to 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 acquisition of specific structures is known to drive phase changes that involve sudden changes in the system’s properties.
Characterizing these phase changes requires hypothesizing what the structure 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 structures—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 structures (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 a 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 a graph, we argue this problem is 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 $\sqrt{|\mathtt{E}||\mathtt{K}|}$.
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 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 a 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 and emergence is that we can predict the point of transition, can we draw on this rich literature to 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 a more naturalistic setting, e.g., can we identify structures underlying emergent capabilities in open-source models, e.g., Pythia variants (Biderman et al., ), and demonstrate that our proposed perspective enables prediction of when capabilities emerge in LLMs?
To begin, we can perhaps focus on capabilities that require similar knowledge acquisition and its compositional generalization on a downstream task.

## 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 to predecessors of this work. ESL thanks Gautam Reddy, Naomi Saphra, Pulkit Gopalani, Wei Hu, and Yonatav Belinkov for fruitful conversations. ESL’s time at 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 JP19H05795, JP19H05275, JP21H01007, and JP23H00095.

## Appendix A Data-Generating Process: Defining our formal language

Our data-generating process involves defining a formal language, sampling sentences from this language, and then defining tasks to be performed upon these sentences (specifically, free generation, unscrambling, or conditional generation).
In this section, we discuss the precise details of how the language is implemented.

### A.1 Defining a grammar using PCFGs

To define a grammar for our language, we use the framework of Probabilistic Context-Free Grammars (PCFGs).
To keep the paper self-contained, we provide a short primer on PCFGs below and then discuss our precise version of it in detail.
For a more thorough discussion on PCFGs, we refer the reader to one of the several well-written tutorials (Collins, ) and books (Sipser, ).

#### A.1.1 Short Primer on PCFGs

Broadly, a PCFG is defined via a 5-tuple $G=(N,\Sigma,R,S,P)$, where:

- •
$\mathtt{NT}$ is a finite set of non-terminal symbols.
- •
$\mathtt{T}$ is a finite set of terminal symbols, disjoint from $\mathtt{NT}$.
- •
$\mathtt{R}$ is a finite set of production rules, each of the form $A\rightarrow\alpha\beta$, where $A\in N$ and $\alpha,\beta\in(\mathtt{NT}\cup\mathtt{T})$.
- •
$S\in N$ is the start symbol.
- •
$P$ is a function $P:R\rightarrow[0,1]$, such that for each $A\in\mathtt{NT}$, $\sum_{\alpha:A\rightarrow\alpha\in R}P(A\rightarrow\alpha\beta)=1$.

To generate a sentence from a PCFG, the following process is used.
Pseudocode for this generation process is provided in Algo. [1](#algorithm1).

- 1.
Start with a string consisting of the start symbol $S$.
- 2.
While the string contains non-terminal symbols, randomly select a non-terminal $A$ from the string. Choose a production rule $A\rightarrow\alpha\beta$ from $R$ according to the probability distribution $P(A\rightarrow\alpha)$.
- 3.
Replace the chosen non-terminal $A$ in the string with $\alpha$, the right-hand side of the production rule.
- 4.
Repeat the production rule selection and expansion steps until the string contains only terminal symbols (i.e., no non-terminals remain).
- 5.
The resulting string, consisting entirely of terminal symbols, is a sentence sampled from the grammar.

Figure: Algorithm 1 Pseudocode for generating a sentence from a PCFG: Process to sample a sentence from a given PCFG $G$.

#### A.1.2 Instantiating the Grammar Underlying our Language

While generally one directly samples sentences from a grammar, in this work, we define a 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 an unconventional manner for defining a PCFG, as one would generally use a standard vocabulary of the language to directly define terminal symbols.
However, to enforce type constraints, we find this unconventional format aids in 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 to be populated.

Overall, our grammar, denoted $\mathtt{G}$, is defined using the following.

- •
Terminal symbols: $\mathtt{T}=\{\mathtt{Subj},\mathtt{Obj},\mathtt{Verb},\mathtt{Conj},\mathtt{lVerb},\mathtt{Desc},\mathtt{eAdj},\mathtt{dAdj},\mathtt{Adv},\mathtt{Prep}\}$.
–
Here, $\mathtt{Subj}$ is a symbol for a subject, $\mathtt{Obj}$ for an object, $\mathtt{Verb}$ for verbs, $\mathtt{Conj}$ for conjunctions, $\mathtt{lVerb}$ for a linking verb, $\mathtt{Desc}$ for descriptors, $\mathtt{eAdj}$ for adjectives used for entities, $\mathtt{dAdj}$ for adjectives used for descriptors, $\mathtt{Adv}$ for adverbs, and $\mathtt{Prep}$ for prepositions.
- •
Non-terminal symbols: $\mathtt{NT}=\{\mathtt{S},\mathtt{sNP},\mathtt{sT},\mathtt{oNP},\mathtt{oT},\mathtt{VP},\mathtt{vT},\mathtt{descT}\}$.
–
Here, $\mathtt{S}$ denotes the start symbol, $\mathtt{sNP}$ can be interpreted as a noun phrase with a subject in it, $\mathtt{sT}$ as the immediate ancestor of the subject symbol, $\mathtt{oNP}$ as a noun phrase with an object in it, $\mathtt{oT}$ as the immediate ancestor before the object symbol, $\mathtt{VP}$ as a verb phrase, $\mathtt{vT}$ as the immediate ancestor of the verb symbol, and $\mathtt{descT}$ as the immediate ancestor of a descriptor symbol.
- •
Production rules $R$:
$\displaystyle\mathtt{S}$
$\displaystyle\rightarrow\mathtt{sNP}\ \mathtt{VP}\,\,[1.0]$
$\displaystyle\mathtt{sNP}$
$\displaystyle\rightarrow\mathtt{sT}\,\,[0.8]\,\,\,|\,\,\,\mathtt{sNP}\ \mathtt{Conj}\ \mathtt{sNP}\,\,[0.2]$
$\displaystyle\mathtt{VP}$
$\displaystyle\rightarrow\mathtt{lVerb}\ \mathtt{descT}\,\,[0.4]\,\,\,|\,\,\,\mathtt{Verb}\ \mathtt{Prep}\ \mathtt{oNP}\,\,[0.4]\,\,\,|\,\,\,\mathtt{VP}\ \mathtt{Conj}\ \mathtt{VP}\,[0.2]$
$\displaystyle\mathtt{oNP}$
$\displaystyle\rightarrow\mathtt{oT}\,\,[0.7]\,\,\,|\,\,\,\mathtt{oT}\ \mathtt{Conj}\ \mathtt{oNP}\,\,[0.3]$
$\displaystyle\mathtt{sT}$
$\displaystyle\rightarrow\mathtt{eAdj}\ \mathtt{Subj}\,\,[0.8]\,\,\,|\,\,\,\mathtt{Subj}\,\,[0.2]$
$\displaystyle\mathtt{oT}$
$\displaystyle\rightarrow\mathtt{eAdj}\ \mathtt{Obj}\,\,[0.8]\,\,\,|\,\,\,\mathtt{Obj}\,\,[0.2]$
$\displaystyle\mathtt{descT}$
$\displaystyle\rightarrow\mathtt{dAdj}\ \mathtt{Desc}\,\,[0.8]\,\,\,|\,\,\,\mathtt{Desc}\,\,[0.2]$

Note that since non-terminals can appear on both left and right hand side of a rule, there is recursion possible in our grammar and hence sentences can get very long.
We restrict sentence lengths to 75, yielding a language where sentence lengths vary from 4–75 tokens.
Probability over rules was partially adapted from prior work by (Hupkes et al., ).

Given the above, we can now sample symbolic sentences such as $\mathtt{Subj\ lVerb\ Desc}$.
We will populate these symbols with tokens from our vocabulary $\mathcal{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, we use the NLTK package (Bird et al., ), which provides an easy interface to define PCFGs.
Moreover, the package provides pre-implemented parsers that help perform grammaticality checks, i.e., if our model produces a sentence $f(x)$ for some input $x$, we can simply use the parser to check whether $f(x)$ is grammatically correct.

### A.2 Type Constraints

As described in the main paper, we instantiate a minimal notion of context sensitivity by constraining when an entity is seen in the context of a property or verb.
There are two subtle ways in which such constraints will affect the generated sentences.

- •
Constraining properties. When a symbolic sentence with a descriptor is sampled, the descriptor symbol will be populated with a 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., Walk), we instantiate a notion of directionality that determines whether the entity can take the action suggested by the verb corresponding to the property or whether the action can be taken upon it. Accordingly, when a verb is selected, only a subset of subjects and objects that can take and have the action of verb be taken upon them are left valid to form a sentence.

Overall, then, say we have a symbolic sentence. We populate the symbols in the sentence as follows.

- •
Check if there is a verb to populate. If so:
1.
Randomly sample a verb from the vocabulary and fill it in.
2.
Sample required number of entities that can occur on 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 are descriptor to populate. If so:
1.
If the entities are not populated yet, populate them.
2.
Use the parse tree for the symbolic sentence to identify property of which entity should populate the descriptor.
3.
Randomly sample a 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 a property
2.
Populate the adjective with a valid adjective from the group of adjectives reserved for entities versus properties
- •
Check if there are adverbs, link verbs, prepositions, or conjunctions to populate. If so:
1.
Sample an adverb, link verb, preposition, or conjunction from the vocabulary. We intentionally do not make these parts context-sensitive, since the remaining parts are sufficient to induce context-sensitivity and enable our experiments.

Pseudocode describing the process above is detailed in Algo [2](#algorithm2).

Figure: Algorithm 2 Pseudocode for populating a symbolic sentence: Fills in symbols while respecting the type constraints.

### A.3 Defining the overall context-sensitive language

Our language $\mathcal{L}$ is defined by first instantiating the underlying grammar as described in App. [A.1](#A1.SS1) and then the type constraints in App. [A.2](#A1.SS2).
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.
Primary hyperparameters for defining $\mathcal{L}$ include number of entities and number of properties, denoted $|\mathtt{E}|$ and $|\mathtt{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 $\mathcal{L}$ to refer to a single language.
In actuality, however, what we have is a family of languages with the same grammar, but varying number of 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 of verbs ($=200$), linking verbs ($=2$), adjectives ($=20$), adverbs ($=20$), prepositions ($=3$), and conjunctions ($=2$).

Figure: Figure 8: Adjacency matrix with time. As the model undergoes training, objects are seen in the context of more properties. Recording whether a 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 objects and properties will never be seen together, however, other objects 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.
Refer to caption: /html/2408.12578/assets/x8.png

We also note that the type constraints graph merely describes which properties are valid for a class.
For a specific entity, only a fraction of these entities might be visible during training.
Specifically, we constrain the sampling process such that only 10% of valid properties of a class are actually associated with an entity.
However, as training occurs, the model gets to see 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. [8](#A1.F8)).
This is likely what leads to the percolation-like process we observe in the main paper to come into play, and hence yields us a $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.

A few example sentences from the language are reported in Figs [9](#A1.F9), [10](#A1.F10). Note that there are a large number of symbolic sentences possible; we merely report two of these to provide intuition. We also reemphasize that naturalistic sentences used as examples in the main paper were to merely analogize the structures our language is trying to capture. It is not difficult to see that the sentences in the examples provided here have a similar structure and constraints as those naturalistic examples.

Figure: Figure 9: Exemplars where an entity’s properties are described. Each box represents a different task; specifically, free generation, unscrambling, and conditional generation.

Figure: Figure 10: Exemplars where a subject and object are bound via a verb. Each box represents a different task; specifically, free generation, unscrambling, and conditional generation.

## Appendix B Percolation threshold in the bipartite graph setup

For general bipartite graphs that are uncorrelated, meaning that they are completely described by the degree distributions $P_{1}(k)$ and $P_{2}(k)$ for the objects and features, respectively, the percolation threshold is

$$ $\displaystyle p_{c}=\sqrt{\frac{\langle k\rangle_{1}\langle k\rangle_{2}}{\langle k(k-1)\rangle_{1}\langle k(k-1)\rangle_{2}}}.$ (2) $$

Here, $\langle\cdot\rangle_{i}$ denotes the expected value with respect to $P_{i}(k)$, and we require $|\mathtt{E}|\langle k\rangle_{1}=|\mathtt{K}|\langle k\rangle_{2}$ for consistency.
The case of randomly selecting connecting edges as demonstrated in the main text will correspond to starting from a complete bipartite graph, in which case $P_{1}(k)=\delta_{k,|\mathtt{K}|}$ and $P_{2}(k)=\delta_{k,|\mathtt{E}|}$, leading to $p_{c}=\sqrt{1/(|\mathtt{E}|-1)(|\mathtt{K}|-1)}\simeq\sqrt{1/|\mathtt{E}||\mathtt{K}|}$.

To derive Eq. ([2](#A2.E2)) we use the generating function as explained in (Newman et al., ).
Firstly, we introduce the generating function for the degree distribution of two concepts, $i=1,2$:

$$ $\displaystyle G^{0}_{i}(x)$ $\displaystyle:=$ $\displaystyle\sum_{k=0}^{\infty}P_{i}(k)x^{k}$ (3) $$

The generating function can be used to calculate moments of the probability distribution, such as the mean and variance, by taking derivatives:

$$ $\displaystyle\left.\frac{dG^{0}_{i}(x)}{dx}\right|_{x=1}$ $\displaystyle=$ $\displaystyle\left.\sum_{k=0}^{\infty}kP_{i}(k)x^{k-1}\right|_{x=1}=\sum_{k=0}^{\infty}kP_{i}(k)=\langle k\rangle_{i}$ (4) $\displaystyle\left.\frac{d^{2}G^{0}_{i}(x)}{dx^{2}}\right|_{x=1}$ $\displaystyle=$ $\displaystyle\left.\sum_{k=0}^{\infty}k(k-1)P_{i}(k)x^{k-2}\right|_{x=1}=\sum_{k=0}^{\infty}k(k-1)P_{i}(k)=\langle k(k-1)\rangle_{i}.$ (5) $$

Here we denoted the average over the degree distribution of concept $i$ as $\langle\cdot\rangle_{i}$.

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 $i$ and $j$, denoted by $\tilde{P}_{ij}(k)$, will satisfy

$$ $\displaystyle\sum_{k=0}^{\infty}\tilde{P}_{ij}(k)x^{k}=G^{0}_{i}(x)G^{0}_{j}(x).$ (6) $$

With these properties in mind, we further introduce the generating function for the distribution of outgoing edges from a node that we arrive at by following a randomly chosen edge:

$$ $\displaystyle G^{1}_{i}(x)$ $\displaystyle:=$ $\displaystyle\frac{\sum_{k=0}^{\infty}kP_{i}(k)x^{k-1}}{\sum_{k=0}^{\infty}kP_{i}(k)}=\frac{G^{0^{\prime}}_{i}(x)}{\langle k\rangle_{i}}.$ (7) $$

which can be obtained by noticing that the probability of the degree of a node arrived at from a randomly chosen edge is proportional to $kP_{i}(k)$. The decreased power of $x$ by one in the numerator is to 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(\neq i)$ that is connected to a randomly chosen edge as $\tilde{G}^{1}_{i}(x)$, and the same when randomly choosing a node in concept $j$, $\tilde{G}^{0}_{i}(x)$. These functions satisfy

$$ $\displaystyle\tilde{G}^{0}_{i}(x)$ $\displaystyle=$ $\displaystyle G^{0}_{i}(G^{1}_{j}(x))$ (8) $\displaystyle\tilde{G}^{1}_{i}(x)$ $\displaystyle=$ $\displaystyle G^{1}_{i}(G^{1}_{j}(x)).$ (9) $$

We also introduce the generating function for the distribution of the sizes of components in concept $i$ that are reached by choosing an edge, $H^{1}_{i}(x)$, and the same when choosing a node in concept $i$, $H^{0}_{i}(x)$. These satisfy

$$ $\displaystyle H^{0}_{i}(x)$ $\displaystyle=$ $\displaystyle x\tilde{G}^{0}_{i}(H^{1}_{j}(x))$ (10) $\displaystyle H^{1}_{i}(x)$ $\displaystyle=$ $\displaystyle x\tilde{G}^{1}_{i}(H^{1}_{j}(x)).$ (11) $$

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 $\langle S_{i}\rangle=H^{0^{\prime}}_{i}(1)$, which is

$$ $\displaystyle\langle S_{i}\rangle=1+\frac{\tilde{G}^{0^{\prime}}_{i}(1)}{1-\tilde{G}^{1^{\prime}}_{i}(1)},$ (12) $$

using the derivatives of Eqs. ([10](#A2.E10)),[11](#A2.E11)).
The percolation threshold is when the denominator in the second term of Eq. ([12](#A2.E12)) becomes zero, so

$$ $\displaystyle\tilde{G}^{1^{\prime}}_{i}(1)={G}^{1^{\prime}}_{i}(1){G}^{1^{\prime}}_{j}(1)=\frac{G^{0^{\prime\prime}}_{1}(1)G^{0^{\prime\prime}}_{2}(1)}{\langle k\rangle_{1}\langle k\rangle_{2}}=\frac{\langle k(k-1)\rangle_{1}\langle k(k-1)\rangle_{2}}{\langle k\rangle_{1}\langle k\rangle_{2}}=1$ (13) $$

Now, when the connection of each a probability of connection $p$ associated with each bond on top of the original graph, the generating function of the degrees will become

$$ $\displaystyle G_{i}^{0}(x;p)$ $\displaystyle=$ $\displaystyle\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}P_{i}(n)\binom{n}{k}p^{k}(1-p)^{n-k}x^{k}$ (14) $\displaystyle=$ $\displaystyle\sum_{n=0}^{\infty}P_{i}(n)(px+1-p)^{n}=G_{i}^{0}(1+(x-1)p).$ (15) $$

From the first line to the second line, we used $\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}=\sum_{n=0}^{\infty}\sum_{k=0}^{n}$. We can then rewrite Eq. ([13](#A2.E13)) as

$$ $\displaystyle\frac{\langle k(k-1)\rangle_{1}^{p}\langle k(k-1)\rangle_{2}^{p}}{\langle k\rangle_{1}^{p}\langle k\rangle_{2}^{p}}=p^{2}\frac{\langle k(k-1)\rangle_{1}\langle k(k-1)\rangle_{2}}{\langle k\rangle_{1}\langle k\rangle_{2}}=1,$ (16) $$

from which we obtain Eq. ([2](#A2.E2)). Here we used $\langle k(k-1)\rangle_{i}^{p}=G_{i}^{0^{\prime\prime}}(1;p)=p^{2}G_{i}^{0^{\prime\prime}}(1)=p^{2}\langle k(k-1)\rangle_{i}$ and $\langle k\rangle_{i}^{p}=G_{i}^{0^{\prime}}(1;p)=pG_{i}^{0^{\prime}}(1)=p\langle k\rangle_{i}$.

### B.1 Exponent in the cluster size

The critical exponent associated with the number of nodes in the cluster for $p>p_{c}$, $S\sim(p-p_{c})^{\beta}$, is determined to be $\beta=1$ when there is no specific structure in the graph. To see this, let us consider that $u=H^{0}_{i}(1)$ is the probability that a node in $i$ is included in a finite size cluster (i.e., not the large connected cluster). Recall that $H^{0}_{i}(1)$ was the generating function of the number of nodes in concept $i$ included in the cluster in the subcritical regime ($p<p_{c}$); we are here assuming that the statistics will not change even in the supercritical regime ($p>p_{c}$) when neglecting the large cluster. Then, from Eqs. ([10](#A2.E10),[11](#A2.E11)), we have

$$ $\displaystyle H^{0}_{i}(1)=u$ $\displaystyle=$ $\displaystyle\tilde{G}^{0}_{i}(H^{1}_{j}(1))=\tilde{G}^{0}_{i}(\tilde{G}^{1}_{j}(u))$ (17) $\displaystyle=$ $\displaystyle{G}^{0}_{i}({G}^{1}_{j}({G}^{0}_{j}({G}^{1}_{i}(u))))=:f(u)$ (18) $$

which is a self-consistent equation.

By writing $u=1-\epsilon$, we have $f(1-\epsilon,p)=1-\epsilon f^{\prime}(1,p)+\epsilon^{2}f^{\prime\prime}(1,p)/2...$, where the derivative is taken for $u$. Noticing that $f^{\prime}(1,p_{c})=1$, we obtain the relation

$$ $\displaystyle\epsilon$ $\displaystyle=$ $\displaystyle(p-p_{c})\left.\frac{\partial^{2}}{\partial u\partial p}f(u,p)\right|_{u=1,p=p_{c}}\left[\frac{1}{2}\left.\frac{\partial^{3}}{\partial u^{2}\partial p}f(u,p)\right|_{u=1,p=p_{c}}\right]+o(p-p_{c})+o(\epsilon)$ (19) $\displaystyle\sim$ $\displaystyle(p-p_{c}),$ (20) $$

indicating $\beta=1$

As an interesting generalization, a classic result (Cohen et al., ) shows that even for the situation where $p_{c}>0$, the power $\beta$ can deviate from one. This corresponds to when the differential coefficients in Eq. ([19](#A2.E19)) diverge, corresponding to cases where the second or third moment being ill-defined. For the case of $P_{i}(k)\sim k^{-\gamma}$ with $3<\gamma<4$, we can show that $\beta=1/(\gamma-3)$.

### B.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 a finite number of steps, denoted as $n$, the pertinent question is the number of node pairs across the sets connected within $2n+1$ edges. Using the average degrees $\langle k\rangle_{1}$ and $\langle k\rangle_{2}$ respectively, a node in the first set can reach approximately $\langle k\rangle_{1}^{n+1}\langle k\rangle_{2}^{n}$ nodes after $2n+1$ steps. Hence, the approximate fraction of connected edges within $2n+1$ steps is $|E|\langle k\rangle_{1}^{n+1}\langle k\rangle_{2}^{n}$.

## Appendix C Experimental details

Model architecture. We train a two-block Transformer based on the nanoGPT architecture (Andrej Karpathy, ) using the standard autoregressive language modeling objective, i.e., 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}$ learning rate, batch-size of $128$, and $10^{-4}$ weight decay for $10^{5}$ iterations (or until the run collapses due to cluster challenges; e.g., power outages). Gradient clipping at norm of $1$ is applied. No learning rate schedule is used. Unless stated otherwise, results are averaged over three seeds.

Data configuration. Sentences are sampled “online”, i.e., 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 $C$ classes, with edges connecting properties sparsely and randomly distributed over valid properties for a given object (specifically, only 10% connections are made). We slightly abuse notations by using $\mathcal{L}$ to refer to our language, since in actuality we have a 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 a unique token ID.

#### C.0.1 Performance of a memorizing solution on Descriptive sentences

As the model undergoes training, its accuracy at getting descriptive constraints right can, at max, be the following: $\mathtt{Acc}=0.1+f*\max\left(1,\frac{0.25Bt|C|}{|\mathtt{E}||\mathtt{K}|Rf}\right)$, where $f$ is fraction of pairs from the type constraints graph the model can see during training, $0.25$ is approximately the proportion of randomly sampled sentences that are descriptive in nature, $B$ is batch-size, $t$ is number of iterations, and $R$ is number of repetitions needed to internalize that an entity and property constitute a valid context. Since we see the third phase in a regime where $t\sim 10^{4}$, assuming at least $4$ repetitions are necessary for internalizing a pair, we have $\mathtt{Acc}\sim 0.15$.

## Appendix D 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 it is able to perform tasks on 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$, in increments of 1600.
- •
Different class setting: we 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 all 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. [D.1](#A4.SS1).
- •
Grammaticality and type checks under different settings: App. [D.2](#A4.SS2).
- •
Negative log likelihoods of sentences from the langauge and their perturbed versions (e.g., where type constraints are not correct): App. [D.3](#A4.SS3).
- •
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. [D.4](#A4.SS4).
- •
Further results on unscrambling: App. [D.5](#A4.SS5).
- •
Evolution of Attention maps: App. [D.6](#A4.SS6).
- •
Further results on Conditional Generation: App. [D.7](#A4.SS7). Conditional generation evaluations turn out to be extremely time-expensive, with a single run taking approximately 4 days to finish when conditional generation is evaluated (compared to 12 hours without). This is likely a result of model generating extremely long sentences to 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.

### D.1 Learning Curves

We plot learning curves for different settings in this section.
Results are reported for varying number of properties, averaged over 3 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.

#### D.1.1 Base setting with varying number of properties

Figure: Figure 11: Learning curves with varying number of properties (base setting). 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, we see a 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 as well. There is a second change of slope for these tasks between $10^{3}$ to $7\times 10^{3}$ iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
Refer to caption: /html/2408.12578/assets/x9.png

Figure: Figure 12: Learning curves 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 a similar range.
Refer to caption: /html/2408.12578/assets/x10.png

#### D.1.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report learning curves under varying number of properties. See Figs. [13](#A4.F13), [14](#A4.F14).

Figure: Figure 13: Learning curves with varying number of properties (1800 objects). 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, we see a 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 as well. There is a second change of slope for these tasks between $10^{3}$ to $7\times 10^{3}$ iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
Refer to caption: /html/2408.12578/assets/x11.png

Figure: Figure 14: Learning curves for setting with $18000$ properties (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x12.png

#### D.1.3 Changing to 2 classes and varying number of properties

We change the number of classes to divide objects and properties over to $2$ (compared to base setting of $10$) and report learning curves under varying number of properties. See Figs. [15](#A4.F15), [16](#A4.F16).

Figure: Figure 15: 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, we see a 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 as well. There is a second change of slope for these tasks between $10^{3}$ to $7\times 10^{3}$ iterations, depending on the number of properties. These points match match the moment where the model starts to improve in its Type Check performance.
Refer to caption: /html/2408.12578/assets/x13.png

Figure: Figure 16: 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.
Refer to caption: /html/2408.12578/assets/x14.png

### D.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 in this section.
Specifically, we report results 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.

For grammaticality, we 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](#Thmtheorem3)).

#### D.2.1 Base setting with varying number of properties

We report results under varying number of properties with the base experimental setting. See Figs. [17](#A4.F17), [18](#A4.F18).

Figure: Figure 17: Grammaticality and Type Checks with varying number of properties (base setting). As number of properties are varied, we see 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 see as soon as grammaticality reaches its maximum, relative constraints quickly improve, leading to a boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints see a transition at this point as well, but then after a period of saturation (akin to a 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.
Refer to caption: /html/2408.12578/assets/x15.png

Figure: Figure 18: 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 a similar range.
Refer to caption: /html/2408.12578/assets/x16.png

#### D.2.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Figs. [19](#A4.F19), [20](#A4.F20).

Figure: Figure 19: Grammaticality and Type Checks with varying number of properties (1800 objects). To demonstrate robustness of results, we increase number of objects in this experiment. We again find that as number of properties are 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 see as soon as grammaticality reaches its maximum, relative constraints quickly improve, leading to a boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints see a transition at this point as well, but then after a period of saturation (akin to a 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.
Refer to caption: /html/2408.12578/assets/x17.png

Figure: Figure 20: Grammaticality and Type Checks with 18000 properties (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x18.png

#### D.2.3 Changing to 2 classes and varying number of properties

We change the number of classes to divide objects and properties over to $2$ (compared to base setting of $10$) and report results under varying number of properties. See Figs. [21](#A4.F21), [22](#A4.F22).

Figure: Figure 21: 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 are 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 see as soon as grammaticality reaches its maximum, relative constraints quickly improve, leading to a boost in accuracy of all constraints evaluation (rightmost panel). Descriptive constraints see a transition at this point as well, but then after a period of saturation (akin to a saddle point), start to improve at an approximately linear rate (on log-log scale) until saturating again. The results are less prominent for this setting, but zooming in (see figure below) shows the claims do follows the base setting shown in paper.
Refer to caption: /html/2408.12578/assets/x19.png

Figure: Figure 22: Grammaticality and Type Checks 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.
Refer to caption: /html/2408.12578/assets/x20.png

### D.3 Negative Log Likelihood of Sentences from Language and their Perturbed Versions

In this section, we 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 a 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 of the type constraints graph that has connections between entities and properties, and evaluate the model NLLs.
- •
Uniform. Since only a 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 can overly generalize and even start deeming sentences that do not satisfy the type constraints to be valid. To assess this, in this evaluation, we 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 a sentence and permute it to break the grammatical rules, while, technically speaking, preserving type constraints since tokens seen in the sentence are allowed to be 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 is what we expect. Since a grammatically correct sentence does not 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 a 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 not 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 a sudden, large degradation in NLLs for grammatically incorrect sentences later in training.

#### D.3.1 Base setting with varying number of properties

We report results under varying number of properties with the base experimental setting. See Figs. [23](#A4.F23), [24](#A4.F24).

Figure: Figure 23: NLL of sentences with different perturbations and varying number of properties (base setting). See text in App. [D.3](#A4.SS3) for a detailed discussion. Broadly, we see NLL of Seen evaluation is very slightly better than Uniform.
Refer to caption: /html/2408.12578/assets/x21.png

Figure: Figure 24: 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 a similar range.
Refer to caption: /html/2408.12578/assets/x22.png

#### D.3.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Figs. [25](#A4.F25), [26](#A4.F26).

Figure: Figure 25: NLL of sentences with different perturbations and varying number of properties (1800 objects). See text in App. [D.3](#A4.SS3) for a detailed discussion. Broadly, these plots show results with fewer classes show similar behavior as the base setting.
Refer to caption: /html/2408.12578/assets/x23.png

Figure: Figure 26: NLL of sentences with different perturbations for setting with $18000$ properties (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x24.png

#### D.3.3 Changing to 2 classes and varying number of properties

We change the number of classes to divide objects and properties over to $2$ (compared to base setting of $10$) and report results under varying number of properties. See Figs. [27](#A4.F27), [28](#A4.F28).

Figure: Figure 27: NLL of sentences with different perturbations and varying number of properties (2 classes). See text in App. [D.3](#A4.SS3) for a detailed discussion. Broadly, these plots show results with fewer classes show similar behavior as the base setting.
Refer to caption: /html/2408.12578/assets/x25.png

Figure: Figure 28: 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 a similar range.
Refer to caption: /html/2408.12578/assets/x26.png

### D.4 How well does the model follow the grammar: distribution of NLLs, depths, and lengths

In this section, we 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.e., only model generations that are grammatically valid are used for this evaluation (else the NLL will be infinity).
Since the model produces grammatically sentences $\approx$90–95% of the time (see App. [D.2](#A4.SS2)), this conditioning leads to filtering of only a very minimal number of 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 a 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 depth.
–
Note that if sentences from the grammar were used itself for this evaluation, min, max, and mean values over a batch of $1000$ sentences turns out to be 2, 4.78, and 15; evaluations of model’s generations are within these ranges as 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 a batch of $1000$ sentences turns out to be 4, 10, and 107; evaluations of model’s generations are within these ranges as well.

#### D.4.1 Base setting with varying number of properties

We report results under varying number of properties with the base experimental setting. See Fig. [29](#A4.F29).

Figure: Figure 29: Grammar characteristics of model generation as number of properties are varied (base setting). See App. [D.4](#A4.SS4) for a detailed discussion. Broadly, model generated sentences are in a similar range as our language’s.
Refer to caption: /html/2408.12578/assets/x27.png

#### D.4.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Fig. [30](#A4.F30).

Figure: Figure 30: Grammar characteristics of model generation as number of properties are varied (1800 objects). See App. [D.4](#A4.SS4) for a detailed discussion. Broadly, model generated sentences are in a similar range as our language’s.
Refer to caption: /html/2408.12578/assets/x28.png

#### D.4.3 Changing to 2 classes and varying number of properties

We change the number of classes to divide objects and properties over to $2$ (compared to base setting of $10$) and report results under varying number of properties. See Fig. [31](#A4.F31).

Figure: Figure 31: Grammar characteristics of model generation as number of properties are varied (2 classes). See App. [D.4](#A4.SS4) for a detailed discussion. Broadly, model generated sentences are in a similar range as our language’s.
Refer to caption: /html/2408.12578/assets/x29.png

### D.5 More results on Unscrambling

In this section, we report several more results evaluating our models’ performance on unscrambling under varying number of properties for the base setting, setting with increased number of objects, 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., it provides partial credit to the model as it learns to solve the task.
- •
Accuracy on Descriptive Sentences. In this evaluation, we compute the exact match accuracy for sentences that are descriptive in nature, i.e., sentences wherein claims are made about an entity possessing a property.
–
We note that the precise way this evaluation is done is by restricting the sentence length to the shortest sentences ($\leq 6$ tokens). This range is primarily constituted of sentences that are descriptive in nature ($\approx$94%).
- •
Accuracy on 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 a subject relating to an object via a 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 ($\approx$85%).
- •
Grammaticality. Given the output generated by the model when it is fed in a scrambled input, we evaluate whether the output is grammatically correct or not.
- •
Type Check. Given the output generated by the model when it is fed in a 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.

#### D.5.1 Base setting with varying number of properties

We report results under varying number of properties with the base experimental setting. See Figs. [32](#A4.F32), [33](#A4.F33).

Figure: Figure 32: Results on unscrambling task as number of properties are varied (Base setting). See App. [D.4](#A4.SS4) for a 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.
Refer to caption: /html/2408.12578/assets/x30.png

Figure: Figure 33: Results on the unscrambling task 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 a similar range.
Refer to caption: /html/2408.12578/assets/x31.png

#### D.5.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Figs. [34](#A4.F34), [35](#A4.F35).

Figure: Figure 34: Results on unscrambling task as number of properties are varied (1800 objects). See App. [D.4](#A4.SS4) for a detailed discussion on metrics used. Broadly, we see the results presented in the main paper are consistent across varying number of properties and a larger number of objects 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 metrics used.
Refer to caption: /html/2408.12578/assets/x32.png

Figure: Figure 35: Results on the unscrambling task for setting with $18000$ properties (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x33.png

#### D.5.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. [36](#A4.F36), [37](#A4.F37).

Figure: Figure 36: Results on unscrambling task as number of properties are varied (Base setting). See App. [D.4](#A4.SS4) for a 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 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.
Refer to caption: /html/2408.12578/assets/x34.png

Figure: Figure 37: Results on the unscrambling task 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.
Refer to caption: /html/2408.12578/assets/x35.png

### D.6 Evolution of attention maps

As the model acquires the grammar, we expect it to attend to specific parts of the context to predict the next token.
Given the simplicity of our model, we can expect the attention maps to be semantically meaningful, especially after the points of emergence.
To assess this, every 1000 iterations of training, we record model’s attention maps in 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.

#### D.6.1 Descriptive sentences

Due to space constraints, we only report attention maps at iterations $\left[0,1000,10000,30000,50000\right]$.
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 type constraints.
Then, between $10000$–$50000$, it starts to learn about descriptive properties.

Figure: (a) Initialization
Refer to caption: /html/2408.12578/assets/x36.png

#### D.6.2 Relative Sentences

Figure: (a) Initialization
Refer to caption: /html/2408.12578/assets/x42.png

### D.7 Another set of results with Conditional generation

As mentioned before, Conditional generation evaluations turn out to be extremely time-expensive, with a single run taking approximately 4 days to finish when conditional generation is evaluated (compared to 12 hours without). This is likely a result of model generating extremely long sentences to 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.e., in the $18000$ properties setting) generalize to another setting, we provide results for similar to Fig. [5](#S6.F5) in another setting with $27600$ properties.
Shown in Fig. [40](#A4.F40), we can see our findings perfectly align with results from the main paper and other results shown in the appendix: the model first learns the grammar, then type constraints, and witnesses improvements on unscrambling and conditional generation tasks as these relevant structures are acquired.

Figure: Figure 40: Demonstration (27600 properties). 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.
Refer to caption: /html/2408.12578/assets/x48.png

## Appendix E Scaling of Point of Emergence (aka Transition Point)

In this section, we repeat experiments from the main paper for different settings to analyze how the point of emergence (interchangeably called transition point or 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 further 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 at times need to rescale the y-axis.

### E.1 Collapsed curves help demonstrate scaling of the transition point

Assume $\mathcal{S}$ denotes a control variable (e.g., edge density in our bipartite graph).
Assume change in $\mathcal{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 $\mathcal{M}$ (e.g., ratio of largest cluster size to graph size).
Further, say the transition point $\mathcal{S}_{c}$ depends on some other property of the system $\nu$ (e.g., number of nodes in the bipartite graph) via a power law relationship.
That is, we have

$$ $\mathcal{S}_{c}\propto\nu^{\alpha}.$ $$

Accordingly, if we tracked $\mathcal{M}$ as $\mathcal{S}$ is changed, we would find its value rapidly starts to change as $\nicefrac{{\mathcal{S}}}{{\nu^{\alpha}}}\to 1$.
As we change the value of $\nu$, assume the value of $\mathcal{M}$ at the point of transition is some constant value.
Thus, if we plot $\mathcal{M}$ as a function of $\nicefrac{{\mathcal{S}}}{{\nu^{\alpha}}}$, 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 $\sqrt{|\mathtt{K}|}$, we should see the curves corresponding to languages with different number of properties collapse onto each other.
This argument however assumes we are tracking the perfect order parameter with respect to which theory is defined.
This need not be the case, as discussed in the next section.

### E.2 What Metrics Make sense?

Note that the theory of percolation on a 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 are 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, e.g., accuracy, need not linearly correlate with the cluster size.
This can affect the collapse visualization discussed in App. [E.1](#A5.SS1).
To elaborate further, we build on the toy setup from above.

Say, the order parameter $\mathcal{M}$ is difficult to experimentally gauge—this is in fact the case for our work, where describing and evaluating a notion of membership within largest cluster is difficult.
Accordingly, we must define alternative metrics that we expect to correlate with $\mathcal{M}$.
Denote this alternative parameter as $\mathcal{M}^{\prime}$ and say $\mathcal{M}^{\prime}\coloneqq\mathcal{M}\times\nu^{\beta}$, i.e., another dependence on $\nu$ gets involved in our experiments as we go from $\mathcal{M}$ to $\mathcal{M}^{\prime}$.
Accordingly, if we track $\mathcal{M}^{\prime}$ as the rescaled control variable $\nicefrac{{\mathcal{S}}}{{\nu^{\alpha}}}$ is varied, we will find that instead of collapsing onto a constant value, systems with different values of $\nu$ have a different value for $\mathcal{M}^{\prime}$.
However, importantly, we will see that the value of $\mathcal{M}^{\prime}$ at this point itself follows a power law relationship $\mathcal{M}^{\prime}\propto\nu^{\beta}$.
Accordingly, if we rescaled the y-axis by dividing it by $\nu^{\beta}$, we would see the curves collapse onto each other again; that is, we will see that

$$ $\text{as }\quad\frac{\mathcal{S}}{\nu^{\alpha}}\to 1,\quad\text{we have}\quad\frac{\mathcal{M}^{\prime}}{\nu^{\beta}}\to\mathcal{O}(1).$ $$

Thus, when using alternative metrics that are meant to correlate with the gold-standard metric (e.g., $\mathcal{M}^{\prime}$ instead of $\mathcal{M}$ in the discussion above), a rescaling of the y-axis according to some 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.

### E.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 a 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 is 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.e., number of properties) induces a collapse of experimental curves, then we can be confident the transition point follows our expected scaling.

Evaluation Metrics. Having discussed the subtleties above, we now discuss the set of evaluation metrics used in this paper to 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 metrics which are specific to a given task and another batch that is common to both, as discussed next.

- •
Unscrambling. Following metrics are reported solely for unscrambling and gauge model’s accuracy on the task. As the model learns which properties belong to which entities, we can expect it 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 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.
–
Descriptive Sentences Accuracy: Exact match accuracy for solely sentences that are descriptive in nature. Similar to prior experiments, we simply filter sentences for length and use ones with $\leq 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 unscrambling, these metrics evaluate a model’s performance on the task of free generation, wherein the goal is to produce a 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.e., 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, as 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 in 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 it relies solely on the grammar, and hence there should be no clear effect of scaling number of properties on this metric.
–
Type Check (All): A type check evaluation, as discussed in 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 a 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 to a saturation phase until the percolation transition kicks in and the model starts inferring which properties are associated with which entity.
- •
Common metrics. Following metrics are reported for both the unscrambling and free generation tasks. These metrics assess whether the model deems a given property and an entity belong to each other, regardless of whether it has seen them together as part of the same context. In this sense, these metrics test a 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 $\mathcal{L}$ that remarks on an 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 $\mathtt{Pr}\left(\delta(f(x)_{1},\mathtt{large})|x_{-1}\right)$, where $x_{-}1$ denotes the sentence up to the last token and $f(x)_{1}$ denotes the first token predicted by the model. The result is averaged over $1000$ sentences.
–
Negative Log-Likelihood of Valid Sentences. For free generation, we sample a descriptive sentence from the language and evaluate how likely the model deems this sentence, reporting it 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.
–
Normalized Rank of Valid Tokens. This evaluation is similar to the average probability evaluation above. However, we now compute the rank of randomly sampled descriptor token instead of the probability associated by the model to this token. If the model knows which properties go with an entity, the rank of tokens associated to said entity’s properties will be low, indicating they are highly likely to be sampled. This metric scales as a function of vocabulary size; hence, we divide it by the number of properties $|\mathtt{K}|$ and called that the normalized rank.
–
Percent Top-K. Similar to 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 is valid for the given entity. We set the threshold to be equal to number of properties associated with a class, i.e., $\nicefrac{{|\mathtt{K}|}}{{C}}$.

### E.4 Experimental settings

We analyze the following settings, sweeping the number of properties in the range $14800$—$38800$, 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: we 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 all evaluations in this setting.

### E.5 Scaling in the Unscrambling Task

#### E.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. [41](#A5.F41) for metrics specific to unscrambling, Fig. [42](#A5.F42) for the common metrics that more closely capture a notion of cluster membership, and Fig. [43](#A5.F43) for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.

Figure: Figure 41: Results on metrics specific to unscrambling (Base setting). We see a collapse of all metrics under a 1.5 scaling exponent.
Refer to caption: /html/2408.12578/assets/x49.png

Figure: Figure 42: 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 a 1.5 scaling exponent. Interestingly, NLL has a scaling exponent of 2.0.
Refer to caption: /html/2408.12578/assets/x50.png

Figure: Figure 43: 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.
Refer to caption: /html/2408.12578/assets/x51.png

#### E.5.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Fig. [44](#A5.F44) for metrics specific to unscrambling, Fig. [45](#A5.F45) for the common metrics that more closely capture a notion of cluster membership, and Fig. [46](#A5.F46) for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.

Figure: Figure 44: Results on unscrambling task as number of properties are varied (1800 objects). We see a collapse of all metrics under a 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.
Refer to caption: /html/2408.12578/assets/x52.png

Figure: Figure 45: Results on unscrambling task as number of properties are varied (1800 objects). 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 a 2.0 scaling exponent. NLL again shows a scaling exponent of 2.0, similar to base setting.
Refer to caption: /html/2408.12578/assets/x53.png

Figure: Figure 46: Average probability curves for different x-axis rescalings (1800 objects). An exponent between 1.5–2.0 induces the best collapse of experimental curves, similar to base setting. Inset plots zoom in near transition point.
Refer to caption: /html/2408.12578/assets/x54.png

#### E.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](#A5.F44) for metrics specific to unscrambling, Fig. [45](#A5.F45) for the common metrics that more closely capture a notion of cluster membership, and Fig. [46](#A5.F46) for different x-axis rescalings for the average probability curves that demonstrate validity of claimed scaling of the transition point.

Figure: Figure 47: 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.
Refer to caption: /html/2408.12578/assets/x55.png

Figure: Figure 48: 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 a 1.5 scaling exponent. NLL again shows a scaling exponent of 2.0, similar to other settings.
Refer to caption: /html/2408.12578/assets/x56.png

Figure: Figure 49: Average probability curves for different x-axis rescalings (2 classes). An exponent of 1.5 induces a perfect collapse of experimental curves, similar to base setting. Inset plots zoom in near transition point.
Refer to caption: /html/2408.12578/assets/x57.png

### E.6 Scaling in the Free Generation Task

#### E.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. [50](#A5.F50) for metrics specific to free generation, Fig. [51](#A5.F51) for the common metrics that more closely capture a notion of cluster membership, Fig. [52](#A5.F52) 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. [53](#A5.F53) where the y-axis is not rescaled to demonstrate the transition points align better with our claimed scaling exponent.

Figure: Figure 50: 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.
Refer to caption: /html/2408.12578/assets/x58.png

Figure: Figure 51: Results on metrics 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.
Refer to caption: /html/2408.12578/assets/x59.png

Figure: Figure 52: 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. [53](#A5.F53) show the exponent is closer to 0.5.
Refer to caption: /html/2408.12578/assets/x60.png

Figure: Figure 53: Average probability curves for different x-axis rescalings (Base setting). An exponent of 0.5 better aligns the transition points.
Refer to caption: /html/2408.12578/assets/x61.png

#### E.6.2 Changing to 1800 objects and varying number of properties

We change the number of objects to $1800$ (compared to base setting of $900$) and report results under varying number of properties. See Fig. [54](#A5.F54) for metrics specific to free generation, Fig. [55](#A5.F55) for the common metrics that more closely capture a notion of cluster membership, Fig. [56](#A5.F56) 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. [57](#A5.F57) where the y-axis is not rescaled to demonstrate the transition points align better with our claimed scaling exponent.

Figure: Figure 54: Results on metrics specific to unscrambling (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x62.png

Figure: Figure 55: Results on metrics designed to approximate cluster membership (1800 objects). 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.
Refer to caption: /html/2408.12578/assets/x63.png

Figure: Figure 56: Average probability curves for different x-axis rescalings (1800 objects). An exponent between 0.5–1.0 can be expected to induce the best collapse for the metric of average probability; results in Fig. [57](#A5.F57) show the exponent is closer to 0.5.
Refer to caption: /html/2408.12578/assets/x64.png

Figure: Figure 57: Average probability curves for different x-axis rescalings (1800 objects). An exponent of 0.5 better aligns the transition points.
Refer to caption: /html/2408.12578/assets/x65.png

#### E.6.3 Changing to 1800 objects 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. [58](#A5.F58) for metrics specific to free generation, Fig. [59](#A5.F59) for the common metrics that more closely capture a notion of cluster membership, Fig. [60](#A5.F60) 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. [61](#A5.F61) where the y-axis is not rescaled to demonstrate the transition points align better with our claimed scaling exponent.

Figure: Figure 58: Results on metrics specific to unscrambling (2 classes). 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.
Refer to caption: /html/2408.12578/assets/x66.png

Figure: Figure 59: Results on metrics designed to approximate cluster membership (2 classes). 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.
Refer to caption: /html/2408.12578/assets/x67.png

Figure: Figure 60: 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. [61](#A5.F61) show the exponent is closer to 0.5.
Refer to caption: /html/2408.12578/assets/x68.png

Figure: Figure 61: Average probability curves for different x-axis rescalings (2 classes). An exponent of 0.5 better aligns the transition points.

## Appendix F Alternative Analysis of Scaling of Transition Point

Figure: (a) 14800 properties
Refer to caption: /html/2408.12578/assets/x70.png

Figure: Figure 63: Transition point scaling. Working with the hypothesis that the model’s accuracy on unscrambling descriptive sentences undergoes first a 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.
Refer to caption: /html/2408.12578/assets/x76.png

A 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 methodology since, except for unscrambling, defining an algorithmic 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.

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 at low performance, and then sudden (approximately) linear growth.
Exploiting this pattern, we can simply fit a 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.

Results. We find a power law with an exponent of $1.4$ explains the data fairly well (see Fig. [63](#A6.F63)). That is, the transition point, according to this method, scales as a power law in number of properties with an exponent of $1.4$. This exponent is fairly close to the one identified using the collapse protocol, i.e., $1.5$.

For completeness, we also show a few of the Bilinear spline fits for descriptive sentences’ accuracy as a function of data scaling in Fig. [62](#A6.F62).

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
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?
soundness: 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).
- 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)
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:
-  left-to-right auto-regressive language modeling
- an unscrambling task that requires the model to take a set of words and convert it into a valid string
- a conditional generation task that requires the model to generate a sentence that has certain words in it.

As 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). 

In 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.
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:

S1: The man who likes apples is here

S2: The man who likes apples are here

Not 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.



Not clear what are new findings in this paper: 
- 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.
		
- 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. 
- There’s also other work by Allen-Zhu et al, who train transformers on formal languages, and find evidence of learnability under some constraints.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Is the specific task (free generation/unscrambling/conditional generation) specified to the model somehow, e.g. with a special token?

For the unscrambling task, is the solution necessarily unique? If not, what's the justification for using exact match/average probability of valid tokens?
soundness: 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.
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.
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.

That 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.

More 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).

I 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).

More minor points:
- 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).
- 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.)
- 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.
- Line 227 "Humans" vs line 228 "humans" - inconsistent capitalization could cause confusion (I assume these are the same thing).
- Line 260: For the indicator variable, maybe consider \mathbbm{1} (from package bbm) instead of \delta (though this is maybe just personal preference)

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: Please refer to the weakness part:

1. 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.

2. Please justify the use of formal languages, and what will happen if we do not train on well-typed formal languages. 

3. 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.
soundness: 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:

1. 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.

2. This paper trained the LLM from formal languages, which generated from a strict grammar with type check. It aligns with current research.

3. he paper’s findings on emergence and phase transitions are potentially generalizable to other neural network models, not just Transformers trained on formal languages.
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.
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?

2. 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. 

3. 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.

[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.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
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])?

___
[3] Barak, et al. Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit. 2022. (https://openreview.net/forum?id=8XWP2ewX-im)

[4] Nanda, et al. Progress measures for grokking via mechanistic interpretability. 2023. (https://openreview.net/forum?id=9XFSbDPmdW)
soundness: 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.
summary: This paper studies emergence of structure and capabilities of a small transformer throughout training on a formal language dataset.
They identify certain phase transitions correlate with the emergence of capabilities to do specific tasks.
They then propose a formulation to predict phase transitions where emergent capabilities, and find that it aligns well with the formal language toy setting.
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.

I 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.
___
[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).

[2] Tigges, et al. LLM Circuit Analyses Are Consistent Across Training and Scale. 2024. (https://openreview.net/forum?id=1WeLXvaNJP)

Meta-review: This paper examines emergence in neural networks through the lens of percolation theory, using transformers trained on formal languages. The work provides a formal definition of emergence, demonstrates phase transitions in learning, and establishes theoretical connections to percolation on bipartite graphs. The reviewers were positive overall, with scores from 6 to 8, praising the paper's take on theory and clear presentation. While concerns were raised about the scope being limited to formal languages and its relationship to prior work on emergence, the authors provided responses that addressed these points. Though the generalizability of the theoretical framework to natural language itself is not yet made clear, this is a worthwhile toy model of a topical phenomenon that will be of interest at ICLR.

Decision: Accept (Poster)