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

We thank the reviewer for their feedback! We are glad they found the paper to be “a pleasure to read”, well contextualized with respect to past and current work on the topic, and that they liked our discussion of emergence in other fields, which directly motivates our formalization of the concept. We also appreciated their high scores on the contribution, presentation, and soundness of our paper! Below, we respond to specific comments raised by the reviewer.

---

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.

We completely agree that other scaling axes are extremely crucial to study! In fact, we are actively working on projects that explore the effects of parameter-size scaling and context-size scaling. Below, we give a high-level overview of our current directions on parameter-size scaling. As we discuss, the precise theoretical models to explain emergence with respect to other axes can be different from the one proposed in this work. In particular, we expect part of the emergent abilities seen with respect to parameter scaling can be explained by our proposed model, but there are also fundamentally new capabilities that parameter scaling unlocks and that data scaling, by itself, cannot. For such capabilities, we expect no theoretical model for data scaling (including ours) will generalize.

• Effects of scaling parameters: differences from data-scaling. First, we note that it is easy to see how emergent abilities with respect to parameter size scaling are already predicted by neural scaling laws. For example, if we take the Chinchilla scaling law and assume infinite data therein, we will get the minimum amount of loss achievable under infinite compute and a given model size (this operation assumes Chinchilla scaling perfectly explains model-size limited scaling regimes). We will thus find that the asymptotic compute loss for a follows a power law with the number of parameters in the model---larger models achieve a smaller asymptotic loss! This implies that to the extent loss is a good proxy for capabilities (see [1] for discussion on this), by merely scaling the model size, we can unlock new capabilities. Any theoretical model of emergence that does not account for the effects of number of parameters in a network, including the percolation model we propose in this paper, is unlikely to explain the learning dynamics of such capabilities.

• Effects of scaling parameters: possible equivalences with data-scaling. Consider the difference in asymptotic loss of a smaller model and the compute-optimal loss (following Chinchilla scaling) of a larger model. This loss difference is in effect the “speed benefit” of parameter scaling: larger models train faster, yielding more reduction in loss than smaller models. Now, assume a smaller model trained using infinite compute (i.e., using infinite data) achieves a similar loss as the larger model’s compute-optimal loss, hence demonstrating similar capabilities. In such a scenario, we can expect any novel capabilities seen in a larger model and not in a smaller model are a consequence of training under resource constraints. For such capabilities, we can expect our percolation model (and generally any model of emergence proposed for data scaling) to hold well, since scaling resources for a fixed model size primarily involves scaling data.

If the reviewer deems it useful, we are happy to summarize the discussion above in the final version of the paper.

[1] Understanding Emergent Abilities of Language Models from the Loss Perspective, Du et al. (NeurIPS 2024)

---

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.

Thank you for highlighting these papers! We have now added references to them.

---

---

[Continued below...]

---

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.

Thank you for your comment. The “diminishing marginal effects”, where the impact of adding edges decreases as the graph becomes denser, is indeed common in saturated regimes. However, our focus in this paper is emergence and its explanation via percolation phase transition before the saturated regime. In this regime, adding a small number of edges can have a disproportionate impact, such as the sudden formation of gigantic connected clusters of nodes. This distinction of regimes is central to our use of percolation theory to model emergence. Please let us know if further clarification would be helpful, and we will incorporate it into the paper.

---

---

Further questions

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.

Please see our (now further expanded) discussion on the Schaeffer et al. paper [1] in Appendix B.1, and our response above where we summarize why emergence should indeed be expected in LLMs’ training. We believe the claims by Schaeffer et al., though credible in some scenarios, are likely overly broad and hence undermine legitimate cases of emergent abilities. We also believe the assumption underlying their work, i.e., that individual tokens’ loss is governed by a power law scaling, is too strong. Finally, we note that comparing our definition of emergence with Schaeffer et al.’s paper is not possible, since the authors do not offer a formal definition in their work.

[1] Are emergent abilities of large language models a mirage?, Schaeffer et al. (NeurIPS 2024)

---

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

On use of formal languages. As noted in the paper (Section 3), our goal was to define a controlled system where we can run a rigorous set of experiments and demonstrate the sudden learning of capabilities by a neural network. To this end, we want to ensure the controlled system is sufficiently realistic such that its analysis can be expected to generalize to more naturalistic scenarios: as the reviewer noted in their comments, our use of a formal language setup is quite likely to enable this! More broadly, we note that this methodology is quite common in other scientific communities; e.g., in neuroscience, one often studies fruit flies for understanding human navigation abilities.

Consequences of using a not well-typed language. We have in fact run experiments on languages which lack type constraints! Our results show that the second transition, i.e., the one explainable via the problem of graph percolation, is removed in such a setting; however, the first transition corresponding to syntax acquisition continues to exist. This is expected, since the second transition is about the learning of type constraints---hence, lack thereof will remove the transition. We also refer the reviewer to a recent, very detailed investigation of untyped formal languages’ learning dynamics by Pandey [1].

[1] gzip Predicts Data-dependent Scaling Laws, Pandey (arXiv 2024).

---

• Schaeffer et al. make a very strong assumption. To develop their toy theoretical model that underlies the claim “emergence is a mirage”, Schaeffer et al. make the assumption that an individual token’s loss follows power-law scaling. This assumption is too strong and arguably incorrect: the loss, when averaged across a large number of tokens, follows a power law (as popularly shown in literature on scaling laws); however, individual token dynamics can in fact be wildly different, and in general unlikely to follow a power law scaling. In fact, empirical evidence of this point was demonstrated most recently by Schaeffer et al. [8] themselves! In their recent paper, the authors show that learning dynamics of individual answer tokens' loss can show discontinuous progress. For further evidence in this vein, see the paper by Michaud et al. [9] that shows sudden loss drops for individual task dynamics, but recreates scaling laws via an averaging of loss dynamics across several tasks. Du et al. [10] also demonstrate similar results for pretrained LLM checkpoints.

  • Relating to our work: In our work, we can concretely show Schaeffer et al.’s assumption does not hold: e.g., in Figure 4, we show loss curves for individual tasks, finding that learning dynamics of tokens corresponding to just these individual tasks (a subset of the overall tokens in a sentence) does not follow a power law! Thus, we can again comfortably conclude that Schaeffer et al.’s assumption, which was too strong to begin with, does not hold in our setting and hence their claims cannot explain our results.

Summary: Overall, we believe that the claim made by Schaeffer et al. is narrower in scope than what is claimed in the paper, and the underlying rationale behind their argument involves a rather strong assumption that is unlikely to hold for language model training (as shown by authors’ own follow-up work), and definitively does not hold in our setting (as shown by our results).

[1] Are emergent abilities of large language models a mirage?, Schaeffer et al. (NeurIPS 2023)

[2] Abrupt Learning in Transformers: A Case Study on Matrix Completion, Gopalani et al. (NeurIPS 2024)

[3] Asymptotic theory of in-context learning by linear attention, Lu et al. (arXiv 2024)

[4] A phase transition between positional and semantic learning in a solvable model of dot-product attention, Cui et al. (NeurIPS 2024)

[5] Sudden drops in the loss: Syntax acquisition, phase transitions, and simplicity bias in MLMs, Chen et al. (ICLR 2024)

[6] Compositional abilities emerge multiplicatively: Exploring diffusion models on a synthetic task, Okawa et al. (NeurIPS 2023)

[7] Emergence of hidden capabilities: Exploring learning dynamics in concept space, Park et al. (NeurIPS 2024)

[8] Why has predicting downstream capabilities of frontier ai models with scale remained elusive?, Schaeffer et al. (NeurIPS 2024)

[9] The quantization model of neural scaling, Michaud et al. (NeurIPS 2023)

[10] Understanding Emergent Abilities of Language Models from the Loss Perspective, Du et al. (NeurIPS 2024)

---

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.

Thank you for this question. Indeed, modern language models are primarily trained on “natural language” data, largely sourced from internet corpora. However, to achieve scientific progress, we have designed synthetic formal language data and reproduced the phenomenon of “emergent abilities in LLMs.” This controlled setup allows us to precisely characterize and understand the mechanisms behind emergence, which would be challenging to achieve with the complexities of natural language data. This approach is akin to using “model systems” in other scientific disciplines, such as medical research, where organisms like mice, marmosets, and macaques are studied to uncover biological mechanisms before translating findings to humans. Similarly, our use of formal languages as a model system has enabled us to uncover novel mechanisms underlying emergent behaviors in LLMs, providing a foundation for future investigations. While testing these claims directly on natural language pretraining dynamics is beyond the scope of the current paper, as the reviewer noted in their comments, our setup yields a sufficiently decent abstraction of natural language settings such that we can expect the results to generalize. We thus hope our insights will motivate further study of emergence from this lens, including an empirical study of in-the-wild LLMs.

---

[Continued below...]

We thank the reviewer for their feedback! We are glad to see they enjoyed our contribution bridging the study of emergence in neural networks and complex systems, found our formal definition can help instigate further work on the topic, and liked our formal languages setup and findings therein, expecting them to generalize to real systems. We also appreciated their high scores on the contribution, presentation, and soundness of our paper! Below, we respond to specific comments.

---

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?

First, we would like to clarify that (i) Schaeffer et al.’s work argued that a very specific type of emergence curve, under a strong set of assumptions, could be transformed into a smooth curve by redesigning the evaluation metric, and (ii) in the past year and a half since Schaeffer et al.’s work, numerous papers have been published that have refined the definition of emergence and reproduced emergent phenomena across diverse setups, further validating its robustness.

Building on this, we note that we discuss and contrast our results with the Schaeffer et al. work [1] at several points in our paper, including references in the intro, Section 4, and a detailed discussion in related work (Appendix B). For example, we mention in Section 4 (L262) that our motivation for reporting multiple metrics is to ensure our results are not confounded by Schaeffer et al.’s argument, i.e., that emergence is driven by use of poorly defined, discontinuous metrics. While we refer the reviewer to Appendix B.1 for a more detailed discussion, broadly, our argument is that Schaffer et al.’s claim is narrower in scope than what is claimed in their paper: we provide three precise arguments to demonstrate this in Appendix B.1, and, for brevity, summarize two of them below. These arguments clearly demonstrate that we see emergence in our setting because our setup is outside the scope of Schaeffer et al.’s claims.

• Several studies have shown emergent abilities with continuous metrics. There is significant evidence for emergent abilities in neural networks that does not rely on use of discrete metrics. For example, in a recent work, Gopalani et al. [2] show a sudden performance increase in a regression setting with an entirely continuous metric---specifically, mean square error. Similarly, phase transitions have been formally demonstrated in recent works, e.g., by Lu et al. [3] in regards to in-context linear regression and by Cui et al. [4] in regards to positional code learning in a histogram computation task. Meanwhile, Chen et al. [5] have shown a sudden loss drop in BERT training, which, again, is not a continuous metric. Overall, given this substantial evidence, we believe the argument by Schaeffer et al. is narrower in scope than what is claimed in their paper---there are legitimate cases of emergence in neural network training that occur without the use of discrete metrics.

  • Relating to our work: In our work, we show performance improvements co-occur with loss drops, i.e., a continuous metric. We can thus comfortably say our results are not confounded by Schaeffer et al.’s argument. In fact, as we mention in Section 4, we also report several other (both continuous and discrete) metrics that show sudden improvements, indicating our results are not confounded by the use of poorly defined metrics.

[Continued below...]

We thank the reviewer for their quick response and increased score!

Here I have another smaller question based on the author’s experiment on not well-typed language: Can these changes be linked to the concepts of first-order and second-order phase transitions? As the authors mentioned the Ising model, perhaps some connections will be behind.

This is an excellent point, and we do believe such a link is plausible! For example, given the sharpness of the transition corresponding to syntax acquisition, we believe it is possible there is a first-order transition at play here; meanwhile, the learning of type constraints, which is a more gradual change, seems likely to be a second-order transition. The latter is in fact inline with what we would expect from our theory of percolation phase transition: the percolation transition is a second-order transition, and hence we expect the progress curve to be continuous and smooth at the first-order derivative level, but there should be an undefined second-order derivative at the point of transition, which is clearly visible in our results (e.g., see Figure 4). This is also demonstrated very clearly in Figure 63, where we show that using a model of two linear fits with a discontinuity best explains the data, again indicating we are observing a second-order transition.

Building on the above, we also take this opportunity to highlight that our work is among the first to theoretically propose and empirically validate a "phase transition" model of emergence, creating a novel interdisciplinary bridge between the study of emergence in physics and AI---exactly the kind of conversation we are engaging in right now!

Minor points

(Paraphrased) In definition 1, "nonlinear" could be confusing. Maybe you mean "discontinuous"? ...

The reviewer is correct. We have replaced the term “nonlinear” with “discontinuous” now.

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

Thanks for pointing this out! We have fixed the typos in appendix C, which had messed up the definition, and have also accommodated S as a non-terminal symbol in Definition 2 now.

I found definition 3 hard to follow....

Thanks for raising this point! The quoted sentence that caused confusion is indeed a bit pedantic. The motivation behind having it was to create a delineation between a node and a token used to refer to that node (i.e., an identifier). This is useful for completeness, but arguably unnecessary for understanding either of the empirics or the theory. We have thus removed it from the definition.

Line 227 "Humans" vs line 228 "humans" - inconsistent capitalization...

Thanks for catching this! We have fixed the typo.

Line 260: For the indicator variable, maybe consider \mathbbm{1}...

We have switched to using \mathbbm{1}. Thanks for the recommendation!

---

---

Further questions

(Paraphrased) Is the specific task specified to the model somehow, e.g. with a special token?

Yes! There is a special token at the beginning of a sentence which conditions the model to perform one of the tasks.

For the unscrambling task, is the solution necessarily unique?

There are indeed sentences for which there is no unique solution, e.g., if there are multiple subjects present in a sentence and an adjective is valid for all of them, then its unscrambled version could have the adjective used for any of the subjects. Handling this ambiguity was noncritical since the percentage of sentences where this is a concern is relatively low (~10%).

---

---

Summary: We thank the reviewer for their detailed feedback that has helped us improve the legibility of the paper. Specifically, we have now updated Section 3 to focus more on the intuitive interpretation of definitions. Please let us know if there are any further concerns and we would be happy to address them!

We thank the reviewer for their detailed feedback! We are glad to see they found our contribution relating the problem of bond percolation to emergence insightful and deserving of follow-up work, while appreciating our proposed setup that enabled this connection. We also appreciated their high scores on the contribution and soundness of our paper! Below, we respond to specific comments.

---

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…

Thank you for this comment! We believe there is a misunderstanding because of poor phrasing on our end. Specifically, when we write “structures learned by the model”, we do not intend to suggest that the model has undergone some fundamental reorganization of, e.g., its neurons or representations. This can certainly happen, but it is not the central focus of our work. Instead, by “structure”, we mean an entirely data-centric concept: we mean to suggest there are regularities present in the data, learning of which will aid learning of downstream tasks. For example, syntax is a structure (i.e., a regularity) present in our formal language; when our model learns that structure, we claim and show there is a sudden improvement in performance of the narrower task of sentence unscrambling. This can certainly manifest a mechanistic reorganization in the model, but we do not aim to investigate it within the scope of this project (though we indeed are interested in it!).

To clarify that the notion of "structure" in this paper is intended to be data-centric, we initially used the term “data structure” in earlier parts of the paper (e.g., contribution 2 was titled “Learning of general data structures underlies simultaneous jumps in specific metrics”). However, given the reviewer’s comment, we understand that merely saying “data structure” is likely still ambiguous. To address this issue, we have now replaced the term “structure” with variants of “regularities underlying the data” throughout the paper. We hope this change helps address the reviewer's concerns!

---

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

Thank you for your thoughtful feedback. We agree that achieving a balance between introductory discussion and detailed results is important. However, we would like to highlight that our submission is a rather special case as it introduces one of the first “phase transition” models of emergence in LLMs, and is aimed at building a conceptual bridge to physics---a field that has been studying emergent phenomena for decades. We believe this interdisciplinary approach can inspire researchers from physics to engage with the study of emergence in neural networks while simultaneously bringing valuable concepts from physics into ML research.

To this end, we intentionally adopted a somewhat pedagogical writing style, even if it increases the length, as we believe it enhances accessibility and broadens the paper’s impact. Based on personal interactions and feedback, this approach has been serving its intended purpose effectively. That said, if there are specific parts of the introductory sections that the reviewer feels could be streamlined or adjusted, we are more than happy to consider revisions to address these concerns.

---

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… 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…

We thank the reviewer for this feedback and agree Definition 2 can be made more legible. We have attempted this in the updated draft: the definition, while still being formal, is now focused on solely emphasizing the relevant concepts that constitute a PCFG. The following discussion, i.e., the two paras after the definition, now discusses how these core concepts are instantiated in our work. For example, how terminal symbols in our work are usual parts-of-speech from English.

For Section 5, we note that while we do already decompose discussion according to phases, a more fine-grained itemization of observations in these individual phases is difficult to achieve because of space constraints. However, following reviewer’s suggestion, we have separated out the central takeaways of each phase now by boldfacing them. We hope this helps improve the legibility of that section!

---

---

[Continued below...]

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 ... Similarly, Chen et al. also have a very similar setting but with masked language models, and show that grammar is abruptly acquired ... There’s also other work by Allen-Zhu et al, who train transformers on formal languages ...

Thank you for highlighting the need to clarify the novelty of our contributions in relation to recent works. While the papers referenced by the reviewer are highly relevant to our work, we emphasize there are crucial differences that distinguish our contributions, as we summarize below.

• A percolation model of emergence. To our knowledge, we are the first to establish a connection between the theory of percolation on a bipartite graph and emergent abilities in neural networks, yielding a predictive estimate of the point of emergence. We note none of the papers referenced by the reviewers offer this contribution; in fact, the papers do not offer any predictive models for their studied setups. The closest result is perhaps the tree-structuredness metric by Murty et al. (2024); however, that metric merely correlates with their task of interest, i.e., it is not a predictive measure that can preemptively describe at how much amount of training, the model will possess their capability of interest.

• A novel formal language setup with context-sensitivity for studying neural networks. Prior works studying neural networks via formal languages primarily focus on context-free languages, which are fundamentally constrained in their richness: such languages only possess syntactic properties, thus offering a setup for studying merely syntax acquisition in neural networks. Further, learning such languages is relatively easy, which is likely the reason why model scaling or data scaling rarely has any effect on the transition point where syntax is learned. In contrast, we study context-sensitive languages in our work, which are a step towards capturing the richness of natural language, but still offer a controllable setup for performing a theoretical analysis. To our knowledge, we are in fact the first to define a context-sensitive language setup for studying modern neural networks’ learning dynamics. We expect this setup will be of interest to the community at large.

• A study of emergence. We also emphasize our work’s primary focus is the study of emergence---to this end, we offer a novel definition of the concept and make a connection to other disciplines (specifically, physics) that can yield insights for further study. However, except for Chen et al., the listed papers by the reviewer are not focused on studying emergent abilities. For example, the paper by Allen-Zhu et al. is merely focused on how neural networks trained on a PCFG learn to implement it. Similarly, the paper by Murty et al. on structural grokking, despite its title, does not exhibit sudden / emergent learning---in fact, the learning dynamics of their studied tasks are very smooth. While Chen et al. does share a similar motivation to ours, i.e., to analyze sudden drops in MLMs’ training loss, their focus is solely on syntax acquisition---an entirely context-free property. Meanwhile, we focus on an emergent ability that corresponds to a context-sensitive property (modeling of type constraints).

Overall, given the differences above, we believe the contributions of our work are entirely novel and not captured by prior works.

---

---

Further 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?

We did try to elicit effects of model size scaling by increasing both depth and width to twice their current values, but did not see any meaningful changes that could not be captured by our theory---primarily, the transition points seemed to occur earlier by a constant offset, which is expected since larger models are known to train faster. We believe this direction is worth exploring further, e.g., by defining a mixture of tasks similar to Michaud et al. [1], but since our current paper was focused on emergence via data-scaling, we did not push further on it.

[1] The quantization model of neural scaling, Michaud et al. (NeurIPS 2023)

---

---

Summary. We again thank the reviewer for their detailed feedback! Our updated paper now better emphasizes experiments stress-testing our models’ understanding of the formal language it is trained on (Section 4 & Appendix F), and has a longer discussion on the analogy between percolation and learning of type constraints (Appendix D.1). In case our answers and these changes help address the reviewer’s concerns, we hope they will consider increasing their score to support the acceptance of our paper.

2. Evaluating broader language statistics. In Appendix F.4, we report results on how accurately the model captures the statistics of our language. Specifically, we randomly sample 1000 sentences from the language at different checkpoints and report the min / mean / max value of (i) sentence NLL under the data-generating process (i.e., the language itself), (ii) parse tree depths, and (iii) sentence lengths. The latter two metrics, while crude, give an idea of whether random sampling from the model yields sentences that are relatively unlikely under the language itself (e.g., sentences with large tree depths or large lengths). As results show, the model’s distribution, as captured by min / max / mean values of these metrics, matches that of the ground truth language’s! For example, parse tree depths vary from 3–15 in both the ground truth language and the model generations.

3. Attention maps. We also report the attention maps at different points in training in Appendix F.5, finding the parse tree of a sentence is broadly represented in the attention maps themselves. This is especially clear for longer sentences, e.g., ones with relative type constraints.

---

Not clear what is the point of the percolation model: This seems less about emergence of structure in the model… I’m not sure what the analogy is between learning type constraints ... and graph percolation ...

Thank you for raising this question! We have now added a new figure and section in the appendix (see App. D.1) to better clarify the percolation analogy, while slightly rewording the exposition in the main paper and adding a reference to this new section for details. We provide a summary of the analogy below, but first clarify what structure means in our paper.

On the term “structure”: We note that our claims and results are not about the emergence of a “structure in the model”, i.e., we do not claim model neurons suddenly organize in some structured fashion at the point of emergence (as happens, say, in grokking). Instead, our claim is about the model learning the structure underlying the data. For example, we deem type constraints as a structure present in our language; these constraints define a set of rules that control which entities and properties can be seen together in a sentence, hence yielding context sensitivity in our language. By the phrase “model learns a structure”, we mean that the model identifies and learns a regularity in data. The analogy to the problem of percolation on a bipartite graph is meant to capture the learning of this data-regularity, giving us a predictive model of how the neural network learns to suddenly predict an unseen combination of entity and property that can be used to form a valid sentence.

Analogy between percolation and learning of type constraints. Broadly, we analogize a model’s learning of type constraints over time as the addition of edges to a bipartite graph that represents our neural network’s knowledge: this imagined graph represents which entity–property combination the network can possibly use to form a valid sentence. More specifically, consider a time-varying bipartite graph whose nodes denote entities (left side of the graph) and properties (right side of the graph) (see the newly added Figure 11a). As training proceeds, the model sees sentences that show a subset of these entities and properties can be combined to form a valid sentence; we thus put an edge between an entity and property nodes if the model has seen a sentence defined using them (see Figure 11b). Then, every training iteration, a new set of edges is added to the bipartite graph (see Figure 11c).

After enough time has passed, we will have added enough edges to the graph above such that for any randomly picked entity and property nodes, there exists a path on the graph that connects them (see Figure 11d). That is, from an entirely statistical perspective, the model will have been shown enough data to know that even an unseen combination of entity and property can be used to form a valid sentence. The critical edge density that leads to the existence of such paths, and hence assures information necessary to learn about which entities and properties can be combined to form a valid sentence has been seen, is exactly the problem of bond percolation on a bipartite graph: in that problem, we aim to identify the critical number of edges needed for the formation of a large connected component in the graph, i.e., for formation of paths between any random set of nodes from the graph. If this analogy is correct, we can expect the transition point of learning descriptive type constraints to follow the theory of bond percolation on a bipartite graph. Our results show this prediction checks out: we find the transition point scales in the same way as the percolation theory predicts.

---

[Continued below...]

We thank the reviewer for their feedback. We are glad they found our paper “extremely well written”, “focused on clearly understanding the phenomenon of emergence”, and the connection between learning of type constraints and percolation a novel result! Below, we respond to specific comments.

---

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 … create minimal pairs with one grammatical and one ungrammatical sentence, and check if the model assigns a higher prob to the grammatical sentence…

Those are great points, and we agree that mere generation of valid sentences is insufficient to claim the model has learned grammar. We’d like to highlight that this is precisely the reason why we reported in Appendices F.3–F.5 several experiments that stress-test or evaluate how accurately the model captures our formal language! This includes experiments that are inline with the one suggested by the reviewer, i.e., assessing whether valid sentences are assigned higher probabilities when compared to invalid ones (Appendix F.3), and experiments where we assess whether broader statistics of sentences (e.g., distribution of parse tree depths and sentence lengths) generated by our language versus our trained model are similar (Appendix F.4). We also report attention maps in Appendix F.5 at different points in training, finding they (partially) encode parse trees. Below, we briefly summarize these results. We also note that to reflect your valuable feedback, we have now edited Section 4 to better emphasize that experiments evaluating and stress-testing how accurately the model captures our formal language are available in the appendix.

1. Evaluating likelihoods of grammatically (in)valid sentences. In Appendix F.3, we generate valid sentences from our language and compute their negative log-likelihood (NLL) under the model. We then perturb these sentences (see list below), creating their invalid counterparts and comparing their NLL to the valid ones. We find that the precise point where the NLL of valid sentences suddenly improves, the NLL of invalid sentences suddenly degrades! This first occurs at the point where we claim the model acquires syntax, then the point where it learns which subject-object pairs can be seen in the same context, and finally at the point where it starts to accurately learn which adjectives can be assigned to an entity. This one-to-one match gives credence to the idea that, at these points, the model is learning the rules underlying our language, since these points are precisely where it starts to associate a much worse NLL to sentences that are invalid under our language!

   • Perturbation 1: Randomize grammar. Herein, we randomly permute tokens from a valid sentence, hence breaking its grammatical structure. While this is an extremely strong intervention, we note the tokens constituting the sentence themselves are allowed to be seen in the same context, i.e., they follow type constraints. As we show in Figure 23d and 24d, the NLL of such sentences is much higher than the valid sentences (the latter is reported in Figure 23a and 24a). Thus, the model deems the perturbed sentences to be severely less probable than the valid ones.

   • Perturbation 2: Randomize values. This perturbation is similar to the one suggested by the reviewer. Specifically, we alter sentences to randomize specific parts of speech, e.g., we use either incorrect adjectives or incorrect subject-objects pairs to form a sentence. As an example, consider a valid sentence such as “Tall man walked on road”. Our perturbation may replace the object herein to create an invalid sentence such as “Tall man walked on water”, or replace the adjective to create a sentence such as “Plastic man walked on water”. We perform one such perturbation per sentence. Results again show that the model assigns higher NLL to such perturbed sentences (Figure 23c and 24c) than it does to valid ones (Figure 23a and 24a)---that is, it deems perturbed sentences to be much less probable than the valid ones.

[Continued below...]