One-sentence Summary

New York University researchers show that pre-pretraining transformers on formal languages capturing hierarchical dependencies before natural language pretraining allows a 1B-parameter model to achieve the same loss with 33% fewer tokens, with attention heads acquired during this phase remaining crucial for syntactic evaluations.

Key Contributions

• The paper introduces formal-language pre-pretraining, where transformers are trained on formal languages before natural language, and states a transfer hypothesis: formal languages should capture hierarchical dependencies while remaining within transformer computational limitations, as analyzed through C-RASP.

• Experiments show that pre-pretraining on formal languages with hierarchical dependency structures lowers natural language loss and improves linguistic generalization compared with other formal languages, with modest support for the hypothesis that effective transfer depends on the formal language remaining within C-RASP-level computational limits.

• For a 1B-parameter model trained on roughly 1.6B natural language tokens, pre-pretraining achieves the same loss and better linguistic generalization with a 33% smaller token budget, and attention heads acquired during pre-pretraining remain crucial for syntactic evaluation performance.

Introduction

Language models are extremely data-hungry, often requiring far more examples than humans to reach strong performance, which limits low-resource training, cognitive modeling of acquisition, and continued scaling once common web data is largely consumed. Prior work introduced formal language pre-pretraining as a way to teach useful inductive biases, showing that more expressive Chomsky-hierarchy classes can help, but the Chomsky hierarchy alone is an incomplete guide for transformers because some formally valid languages cannot be learned or length-generalized by them. The authors address this by proposing that effective pre-pretraining depends on the intersection of formal-language expressivity and transformer circuit complexity, using C-RASP to define languages that capture hierarchical dependencies while remaining learnable by transformers. They show that pre-pretraining on such languages can improve natural-language token efficiency, reuse learned attention mechanisms, and scale to a 1B-parameter model.

Dataset

• Sources and composition: The authors use synthetic formal-language corpora generated for pre-pretraining transformer language models. The dataset consists of four formal languages: 1-Dyck, k-Dyck, k-Shuffle Dyck, and COPY. The first three model nested hierarchical structure, while COPY uses a fixed first half to second half dependency.

• 1-Dyck: Single-type nested parentheses, context-free and C-RASP definable. Strings are generated by randomly opening or closing parentheses with probability 0.5, producing a harmonic depth distribution, and are truncated at 2048. Its depth distribution is matched across the Dyck variants.

• k-Dyck: k parentheses types, context-free and in FO(M), but not in C-RASP. The main setup uses k=64, giving 64 parenthesis pairs and 128 unique vocabulary tokens. It is constructed as an extension of 1-Dyck by replacing paired parentheses in valid 1-Dyck strings with new parenthesis pairs.

• k-Shuffle Dyck: k-Dyck with cross-serial dependencies, context-sensitive and C-RASP definable. It also uses k=64, 64 parenthesis pairs, and 128 unique vocabulary tokens. It can be viewed as interleaving several 1-Dyck sequences while keeping matched depth statistics with the other Dyck corpora.

• COPY: The copy language, context-sensitive and in FO(M), but not in C-RASP. It uses 128 unique vocabulary tokens and a fixed mapping that copies the first half of a string onto the second half. It contrasts with k-Shuffle Dyck because all its dependencies are cross-serial rather than nested.

• Filtering and cropping: The described generation rules include random parenthesis opening or closing, matching depth distributions across Dyck variants, vocabulary matching to 128 tokens where specified, and truncation at 2048 tokens. The text does not specify an overall corpus size, train split, validation split, or additional filtering rules.

• Usage: All models are pre-pretrained on the same number of tokens with sequence packing. The corpora are used to test whether hierarchically structured languages that are also definable in C-RASP provide a better inductive bias for learning longer strings.

Method

The authors leverage a two-stage training framework in which formal-language pre-pretraining is used to initialize a transformer language model before natural-language pretraining. At a high level, training is represented as an optimization procedure $\mathcal{A}(\mathcal{D}, t, \theta_{\mathrm{init}})$A(D,t,θinit​), which returns model parameters $\theta_t$θt​ after $t$t gradient updates on dataset $\mathcal{D}$D. The pipeline is blocked into two sequential phases. First, the model is pre-pretrained for $t_0$t0​ steps on a formal-language dataset $\mathcal{D}_{\mathrm{ppt}}$Dppt​, producing parameters $\theta_{t_0}$θt0​​. Second, those parameters are transferred directly into natural-language pretraining, where the model is trained for $t_1$t1​ steps on $\mathcal{D}_{\mathrm{pt}}$Dpt​, producing $\theta_{t_1}$θt1​​.

The downstream objective is fixed and independent of the pre-pretraining choice. The pretraining phase seeks parameters that minimize the expected language modeling loss on the natural-language pretraining data,

Because the pretraining dataset $\mathcal{D}_{\mathrm{pt}}$Dpt​, pretraining horizon $t_1$t1​, and optimizer hyperparameters are held fixed, the method treats the pre-pretraining dataset $\mathcal{D}_{\mathrm{ppt}}$Dppt​ and pre-pretraining duration $t_0$t0​ as the primary variables being studied. This makes the experimental design explicitly about whether a formal-language initialization can produce better starting weights than training naturally from the beginning.

The authors compare their proposed formal-language pre-pretraining against several baselines. One baseline removes pre-pretraining entirely by setting $t_0=0$t0​=0. Other baselines pre-pretrain on random binary strings or random strings of integers, with $t_0=500$t0​=500 steps in the reported comparisons. A final baseline pre-pretrains on unseen natural-language data $\mathcal{D}_{\mathrm{pt}}^{*}$Dpt∗​ drawn from the same distribution as the eventual pretraining corpus. The authors note that this natural-language pre-pretraining baseline is not equivalent to simply training on the union of $\mathcal{D}_{\mathrm{pt}}^{*}$Dpt∗​ and $\mathcal{D}_{\mathrm{pt}}$Dpt​ for a longer duration, because pre-pretraining followed by pretraining applies learning-rate warmup twice, once in each stage.

The choice of formal languages is guided by an expressivity hypothesis: a helpful pre-pretraining language should combine hierarchical structure similar to that of natural language with learnability by transformer-style circuits, especially when the learned structure should generalize to longer sequences than observed during training. To test this, the method evaluates formal languages from different positions in classical formal-language and circuit-complexity hierarchies. One case is 1-Dyck, the nested-parentheses language, which is context-free and definable in C-RASP. Another is $k$k-Dyck, which contains $k$k different types of parentheses; it is context-free and falls within first-order logic with majority quantifiers but outside C-RASP. A third case is $k$k-Shuffle Dyck, which introduces cross-serial dependencies and is context-sensitive while still being definable in C-RASP. Finally, the method evaluates the copy language, a context-sensitive language that belongs to the same logical circuit-adjacent family as $k$k-Dyck but not C-RASP.

These languages are intentionally related. The Dyck variants emphasize hierarchical nesting. The $k$k-Dyck language can be viewed as an extension of 1-Dyck where a single parenthesis type is replaced by multiple paired types, while $k$k-Shuffle Dyck can be viewed as an interleaving of several Dyck sequences with cross-serial dependencies. The copy language provides a contrast because its dependencies are strongly cross-serial and map the first half of a string onto the second half, rather than forming nested hierarchical patterns. This design allows the method to separate the effects of hierarchy, cross-serial structure, and circuit expressivity.

The formal-language corpora are constructed to keep comparisons controlled. For 1-Dyck, $k$k-Dyck, and $k$k-Shuffle Dyck, sequences are generated by randomly opening or closing parentheses with probability $p=0.5$p=0.5, producing a harmonic distribution over depths. The generated sequences are truncated at length 2048. The vocabulary size is also matched across relevant corpora. The $k$k-Dyck, $k$k-Shuffle Dyck, and copy-language corpora each use 128 unique vocabulary items. For the Dyck-based corpora, this corresponds to 64 unique parenthesis pairs, giving $k=64$k=64. All models are pre-pretrained on the same number of tokens with sequence packing, so differences in validation loss and downstream evaluation reflect the language structure and initialization effect rather than token count.

The evaluation design has three main components: validation loss, grammaticality judgments, and verbatim retrieval. Validation loss on the natural-language pretraining objective tests whether the formal-language initialization improves the model’s ability to predict the eventual pretraining target. For grammaticality, the model is evaluated using minimal pairs of sentences that differ only in grammaticality. The model is assessed on whether it assigns higher likelihood to the grammatical sentence than to the ungrammatical one. Accuracy is computed as the proportion of minimal pairs where this preference is correct. Verbatim retrieval evaluates whether the model can assign very high likelihood to a repeated list of words in the second occurrence of the list, with lower loss indicating stronger pattern reproduction. Together, these evaluations probe whether the model has learned to recognize and apply consistent patterns, a capability that formal-language pre-pretraining may strengthen.

The method also quantifies the computational efficiency of pre-pretraining through a marginal rate of substitution between formal-language steps and natural-language pretraining steps. The setup asks how many steps of natural-language-only training are displaced by a fixed number of formal-language pre-pretraining steps while achieving the same final loss. Let $x$x denote pre-pretraining steps and $y$y denote natural-language pretraining steps. If two training schedules achieve comparable loss, the marginal rate of substitution is

For example, if the schedules $(x,y)=(0,10000)$(x,y)=(0,10000) and $(x,y)=(500,6000)$(x,y)=(500,6000) reach the same loss, then

The corresponding token efficiency gain is

Thus, a desirable pre-pretraining language is one that lowers the loss achieved after natural-language pretraining while requiring a small number of pre-pretraining steps. The overall pipeline therefore couples a formal-language initialization phase, a fixed natural-language pretraining phase, and controlled evaluation metrics designed to measure both linguistic generalization and training efficiency.

Experiment

Experiments pretrain small transformer models on formal languages before natural language, comparing validation loss, grammaticality, subnetwork ablations, metamer controls, and scale-up runs to test what transfer properties matter. They find that formal languages with hierarchical dependencies, especially shuffle Dyck, improve natural language modeling and grammaticality more than comparable natural data or simpler non-hierarchical strings, while copy language and random strings are unhelpful or harmful. Mechanistic ablations show that attention heads selected after formal pretraining remain important after natural training, suggesting a reusable subnetwork for hierarchical structure, and the benefits persist at 1B parameters, with modest evidence for C-RASP expressivity.

The table shows examples of formal languages used for pre-pretraining, including nested bracket structures and repeated strings. Languages with hierarchical dependencies, especially the bracket-based Dyck languages, are associated with improved language modeling and linguistic generalization. By contrast, the repeated copy language lacks hierarchy and is associated with harmful effects when used for pre-pretraining. Examples include nested parentheses, mixed bracket sequences, and repeated strings. Hierarchical bracket languages tend to provide a stronger inductive bias than non-hierarchical string repetition. The shuffled bracket language performed strongly while requiring less pre-pretraining than other tested languages.

The experiments evaluate formal pre-pretraining languages, comparing hierarchical bracket structures with non-hierarchical repeated string patterns. Hierarchical Dyck-like bracket languages provide a stronger inductive bias and are associated with improved language modeling and linguistic generalization. In contrast, repeated copy data lacks hierarchical structure and can be harmful, while shuffled bracket language performs strongly and requires less pre-pretraining than other tested languages.