How Language Models Learn Context-Free Grammars

More Detail Needed About cfg3

The paper uses a family called cfg3 to benchmark transformers, but surprisingly little is said about this family in the main paper. Even if many of the details are relegated to the appendix, it is crucial to say in the main paper what this particular family of CFG is at a high level and why it was chosen, especially because there are many other more canonical CFLs that have been investigated in previous work such as Dyck languages (Ebrahimi et al.) or hardest CFG (DuSell).

The authors should explain in text or ideally even with a figure example what cfg3 looks like and what the variants are. They should also ideally say something about why they chose cfg3 and how cfg3 compares to more standard CFLs like Dyck languages (in terms of the types of strings it generates, complexity, etc.).

Unclear What the Authors Mean by "Challenging" CFGs

The authors remark that some of their CFG's are "quite challenging" in the abstract, and later state that the different CFGs within their cfg3 family are ranked by increasing difficulty. Yet, it is not clear what notion of difficulty they mean (this is especially problematic given the lack of detail about cfg3 mentioned above). Presumably, the authors are hinting that these languages are challenging to suggest that the results should be representative for the ability of transformers to learn other CFGs as well. But there is no formal sense presented in which these CFGs are hard or any guarantee or argument about why we should expect results on these languages to transfer to other CFGs.

I would like the authors to either expand on why the languages they chose are challenging or remove any informal claims about them being challenging. Additionally, they should qualify the abstract the indicate that they are studying a particular class of CFGs (cfg3) or else explain why they think the results will translate to other CFGs.

Regarding this point, note that there are canonical examples of hard CFGs like the Dyck languages or "hardest CFG" mentioned above. One other way to address this concern would be to run experiments with these languages as well where there is more of a reason to think the languages in question are "challenging".

Issues in Probing Results Presentation

Figure 4 should be made larger so it's easier to see the probing results.

Moreover, the results presented in Figure 5 do not fully support the claim in 4.2 that NT ancestor information is locally encoded at NT boundaries and not elsewhere. This is because the plot only shows the results when probing from NT boundaries; I would like to also see a similar plot from other positions in the string where the probing accuracy is much lower.

nit: Claim about Probing

The authors claim the following about the attention patterns in a transformer:

If it does encode the NT information after pretraining, it means that the model can both generate and certify sentences in the CFG language

This statement is a bit ambiguous, but one reading is that if a model correctly encodes NT boundaries, it will necessarily be able to generate and certify the CFG. This is actually a fallacy: it has been pointed out many times in the NLP literature that we cannot conclude a model is using some grammatical feature correctly just because it is representing it correctly (cf. Elazar et al.). In the case of formal language tasks, it may be more unlikely that a model represents a feature it does not use, but in principle the same fallacy still applies. I thus would like the authors to remove or modify this sentence.

• It is not clearly discussed the hyperparameter selection of the probing and LMs for the study.
• It is not clearly described the implication of using synthetic data on the findings.
• An extra contribution could be to present a statistical significance test or uncertainty estimates of the results.

• The definition of CFGs and generation therefrom, using layers of non-terminals and whatnot, are somewhat nonstandard. This makes it a bit hard to follow and digest (e.g. why some grammars are more complex than others). There also was a related under-description of the grammars that were actually used in the experiments and how, e.g., they relate to more commonly known classes of CFGs like dyck-n.
• There are so many experiments and details that the results and their implications are often under-described (e.g. just "As figure X shows", with a pointer to a complex figure). This makes it hard for the reader to follow, and easy to lose the forest for the trees.

Terminology

There are some imprecise or inaccurate uses of terminology. For example:

• "GPT" is used to refer to the GPT-2 architecture (which is randomly initialized in the experiments), when typically this term is supposed to refer to the pre-trained models. (The GPT-2 architecture is just a typical Transformer decoder.)
• "Dynamic Programming" seems to just refer to any method for CFG parsing that involves keeping track of nonterminal symbols and boundaries. By that logic it's unclear what parsing algorithm would not count as dynamic programming, since it's hard to imagine how to parse without that information.

Intuitions

There are a lot of intuitive claims here that are not justified. For example:

• Under "The cfg3 synthetic CFG family" (p. 3), the text refers to "hard" and "easy" datasets without saying what makes them easy or hard. There is a sentence saying "Typically, the learning difficulty of CFGs inversely scales with the number of NT/T symbols" with a reference to Figure 3, but Figure 3 contradicts this by saying, "Less ambiguous CFGs (... as they have fewer NT/T symbols [emphasis added]) are easier to learn [emphasis added]."
• The "Why Such CFGs" section (p. 3) says, "The probability of a random string belonging to this language is nearly zero," but the paper presents no evidence, citation, or theoretical justification for this.
• The paper refers to "highly ambiguous" and "less ambiguous" CFGs without saying how they measure ambiguity. The Figure 3 caption suggests that "less ambiguous" means "fewer nonterminals," but it's not immediately obvious that this would be the case (e.g., consider a rule like $A \to A$).

Methodology

• The main experiments have no baseline. Although the entropy experiment has a "ground truth" value, it's still not clear how easy or hard the task is.
• I'm somewhat unconvinced by the probing experiment. It seems to me that in theory, the nonterminal label and boundary information should be fully recoverable from the next token distribution alone. Therefore if the language model really does generate competently from the CFL, then probing for this information should be trivial.

Presentation and Framing

• The paper makes many references to the "how" of "learning": for example, the title is How [emphasis added] Language Models Learn [emphasis added] Context-Free Grammars. However, the paper never actually addresses the question of how the models learn; it only analyzes models after learning is complete.
• The paper is overly reliant on the appendix. The appendix should be reserved for implementation details and proofs of mathematical claims, and it shouldn't be essential to a typical reader's understanding of the paper.
• Some of the notations and definitions are overly cumbersome. For example, the description of the generation algorithm and the notation for boundaries could be greatly simplified.