Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers (2025)

Abstract: Transformers trained on natural language data have been shown to exhibit hierarchical generalization without explicitly encoding any structural bias. In this work, we investigate sources of inductive bias in transformer models and their training that could cause such preference for hierarchical generalization. We extensively experiment with transformers trained on five synthetic, controlled datasets using several training objectives and show that, while objectives such as sequence-to-sequence modeling, classification, etc., often fail to lead to hierarchical generalization, the language modeling objective consistently leads to transformers generalizing hierarchically. We then study how different generalization behaviors emerge during the training by conducting pruning experiments that reveal the joint existence of subnetworks within the model implementing different generalizations. Finally, we take a Bayesian perspective to understand transformers’ preference for hierarchical generalization: We establish a correlation between whether transformers generalize hierarchically on a dataset and if the simplest explanation of that dataset is provided by a hierarchical grammar compared to regular grammars exhibiting linear generalization. Overall, our work presents new insights on the origins of hierarchical generalization in transformers and provides a theoretical framework for studying generalization in language models.

## introduction natural language is structured hierarchically: words are grouped into phrases or constituents, which can be further grouped to form higher-level phrases up to the full sentence. how well do neural networks trained on language data learn this hierarchical structure has been a subject of great interest @xcite @xcite . a useful tool to understand the model-and dataset-specific properties that results in aforementioned phenomenon is the test for hierarchical generalization, i.e., evaluating the capability of a model to generalize to novel syntactic forms, which were unseen during training. a classic problem to test for hierarchical generalization is question formation, where given a declarative sentence, e.g., my walrus does move the dogs that do wait., the task is to transform it into a question: does my walrus move the dogs that do wait? the task is accomplished by moving one auxiliary verb to the front. the correct choice to move does in this example (rather than do), is predicted both by a hierarchical rule based on the phrase-structure syntax of the sentence, and by a linear rule that prescribes moving the first auxiliary. hence, as a test for hierarchical generalization, we can ask: for neural networks trained from scratch on data consistent with both hierarchical and linear rules (ambiguous data), do they learn to generalize hierarchically or do they learn a linear rule? this question has been well studied in past work for different neural network architectures and it has been shown that rnn and transformer architectures, which lack explicit tree-structure encoding, fail to generalize hierarchically @xcite @xcite @xcite . however, @xcite showed that, surprisingly, when trained for a long time after attaining perfect training accuracy, transformers do start to generalize hierarchically, and named this phenomenon structural grokking. in this work, we ask: why do transformers show hierarchical generalization, despite lacking architectural biases towards hierarchical structure? we first explore if the choice of training objective can influence hierarchical generalization in transformers. specifically, we consider five objectives-language modeling, sequence-tosequence modeling, prefix language modeling, sequence classification and cloze completion-and study the generalization behavior of transformers trained from scratch 1 under five synthetic, controlled settings following prior work-english question formation (as described above), german question formation @xcite , tense-reinflection @xcite , passivization @xcite , and simple agreement, a task that we construct. we find that only the language modeling objective consistently obtains strong hierarchical generalization, while the other objectives often fail, implicating language modeling objective as a source of bias towards hierarchical generalization. further, to understand how hierarchical structure is learned and represented during training, we propose two new attention head pruning strategies to discover subnetworks corresponding to different generalizations. we find that both hierarchical and linear types of generalizations can be discovered as subnetworks in the trained model, and these subnetworks continue to coexist over the course of training, despite the overall model performing closer to one kind of generalization over the other. finally, we attempt to explain why language modeling results in a preference towards hierarchical structure using the bayesian framework from @xcite . specifically, we consider generative probabilistic grammars (pcfgs) to model the simple agreement task data by constructing hierarchical grammars consistent with the hierarchical rule as well as regular grammars consistent with the linear rule. we then compare their posterior probabilities to understand which grammar has a better trade-off for the goodness of fit (given by the likelihood) and simplicity (given by the prior on grammars). our analysis reveals a correlation between transformer lms generalizing hierarchically and hierarchical grammars having higher posterior, compared 1 since our aim is to understand hierarchical generalization in transformers in isolation, following prior work (e.g., @xcite , we train transformer models from scratch, without any pretraining, eliminating the possibility of these models having any hierarchical bias due to pretraining on language data @xcite . our contributions can be summarized as: to our knowledge, the present work is the first to show that language modeling objective is a source of inductive bias for hierarchical generalization and to use the bayesian perspective to explain hierarchical generalization in language models. notice that the task can be accomplished by moving one auxiliary verb to the front of the sentence. for sentences with two auxiliaries like 1a, as english speakers we know that the auxiliary to move is the one associated with the head verb in the sentence (i.e., does, which is associated with move, not do, which is associated with wait). modeling this rule requires understanding the phrase structure of the language. we call this the hierarchical rule. one can alternatively consider a much simpler explanation, the linear rule: moving the first auxiliary in the sentence to the beginning. however, if we consider sentences with a different syntax (relative clause attached to subject instead of object in this case, using the linear rule will result in an ungrammatical sentence, i.e., outputting 2b instead of 2c. we study the following question in our work: consider neural networks trained from scratch on data consistent with both hierarchical and linear rules (like example 1). when presented with sentences such as 2a do they generalize hierarchically (predicting 2c) or linearly (predicting 2b)? tasks and datasets. in our study, we consider five tasks, including the question formation task above. examples from all the tasks are provided in the training dataset has examples that are consistent with both hierarchical and linear rules. for evaluation, two variants of the test data are considered: an in-distribution test set, which follows the same distribution as the training data (i.e., also ambiguous with respect to the correct rule); and a generalization test set, which consists of examples which are only consistent with the hierarchical rule. for question formation, we use the dataset from @xcite . we also experiment with question formation in german with the dataset from @xcite . the dataset here consists of sentences with the modals können/kann (can) or auxiliaries haben/hat (have/has), together with infinitival or past participle main verbs as appropriate, which can be moved to the front similar to english to form questions. we also consider passivization from @xcite , where the task is to transform a sentence in active voice to passive, and tense reinflection @xcite , which involves converting a sentence in past tense to present. finally, we introduce a simplified version of the tense reinflection task, which we name simple agreement. unlike others, simple agreement is a single-sentence task where only the present-tense sentences from the tenseinflection are considered. in this task, we evaluate the model's ability to generate the correct inflection of the main verb based on the context. here, the hierarchical rule requires the verb to agree with the hierarchically determined subject and the linear rule requires it to agree with the most recent noun in the sequence. our motivation for introducing this new task is that it is much more straightforward to construct probabilistic grammars for single-sentence tasks, while for sentencetransformation tasks like question formation, it can be non-trivial. we make use of the underlying probabilistic grammars heavily in §5, where we try to provide a bayesian interpretation of hierarchical generalization in language models. for all tasks involving transformation of inputs (i.e., all except simple agreement), the datasets also include input identity pairs. for example, for question formation, the dataset is augmented with declarative-declarative pairs. importantly, the identity pairs in the training data also include input sentences whose corresponding outputs would disambiguate the data, i.e., are only satisfied by the hierarchical rule, although, such outputs are not present in the training data and hence the transformation task remains ambiguous. this choice was made in @xcite (and others) to familiarize the model with at least the input sentences for which the outputs remain unobserved. we provide full details of all the datasets in appendix §a.2. for all tasks excluding simple agreement, there are 100k training examples (50k transformation and 50k identity pairs) and 1k and 10k examples in in-distribution and generalization test sets, respectively. for simple agreement, we generate 50k training examples (and 1k/10k for test datasets). evaluation metrics. following prior work @xcite , for evaluating question formation (both english and german) we consider the first-word accuracy, i.e., given the declarative sentence as the input, evaluate whether the model predicts correct auxiliary for the first word in the generated question. for passivization, we evaluate using the object noun accuracy, which measures whether the correct noun was moved to the subject position. finally, for tense-reinflection and simpleagreement, we consider main-verb accuracy, by evaluating if the main-verb (in the present tense) has the correct inflection, i.e., appropriately singular or plural based on the context. when evaluated on the in-distribution test set we denote it as in-distribution accuracy and generalization accuracy for the generalization test set. ## discovering subnetworks with different generalization behaviors the results from @xcite show that the transformer lms obtain perfect in-domain accuracy much earlier during training, while generalization comes later. this suggests that the model might be implementing something like the linear rule early in training and eventually generalizes to the hierarchical rule. in this section, we explore whether these rules are implemented as subnetworks in the model and ask how these subnetworks evolve over the course of training. finding subnetworks. following merrill et al. ## a bayesian perspective on hierarchical generalization in transformer lms a useful tool for understanding generalization in neural networks has been ''the simplicity bias'', the inductive bias towards simpler functions @xcite has been suggested as an explanation for why neural networks tend to generalize instead of overfitting the training data @xcite . can we explain through ''simplicity'' the preference of the model towards hierarchical generalization over linear? our main argument is that, when considering transformers trained with the language modeling objective, because the underlying data-generation process to be modeled produces each token in the full sequence, modeling the dependencies between the tokens hierarchically as opposed to learning a linear rule for each dependency might be simpler. 3 we leverage the bayesian framework of @xcite , utilizing generative grammars to model data-generation processes corresponding to the hierarchical and linear rules, and operationalize the notion of simplicity and goodness of fit using the posterior probabilities of the grammars given the observed data. we then show a correlation between transformers' generalizing hierarchically and the training dataset being better explained using a hierarchical grammar than a grammar modeling the linear rule according to the posterior criterion. ## conclusion in our work, we studied when and why transformers exhibit hierarchical generalization when trained on an otherwise ambiguous data consistent with both linear and hierarchical rules. there are multiple directions that can be explored in the future. while our results suggest language modeling as a source of hierarchical bias, it still remains unclear why hierarchical generalization is delayed (i.e., grokking). while the experiments concerning our bayesian interpretation only involved the simple agreement tasks for which it was possible to construct cfgs, in future it would be interesting to explore methods to model the simplicity and goodness of fit for competing hypotheses for tasks involving transformation of an input sentence to output sentence. while we show a correlation between the bayesian interpretation and the behavior of transformer lms, future work can also look at establishing a causal connection between the two. figure 4 : robustness of negative results for non-language modeling objectives across different hyperparameter setting for the question formation task. for each experiment, we vary one hyperparameter while keeping the other two fixed to default values, i.e., 6 layers, 8 heads, and 512 embedding dimension. note that the language modeling objective achieves an average generalization accuracy of 0.76 with the default hyperparameters.