How Transformers Represent Hierarchies: A Local-to-Global Mechanism

Large language models built on autoregressive Transformers excel at next-token prediction, but it is unclear how their internal computations capture the latent hierarchical dependencies that often underlie language. We study this question in a controlled formal-language setting based on probabilistic context-free grammars (PCFGs), where sequences are generated by a latent hierarchical process. Empirically, standard autoregressive Transformers can be trained to accurately match the grammar-induced next-token distribution. Using probing analyses, we find that Transformer hidden states contain information used by classical parsing algorithms. Moreover, this information emerges through a layer-wise progression, revealing a local-to-global mechanism: early layers accumulate local patterns, while later layers aggregate them into a compact summary for next-token prediction. Complementing these empirical findings, we provide an explicit construction of Transformers that can parse binary PCFGs with depth logarithmic in the grammar's sequence length. Surprisingly, trained Transformers in this setting exhibit prediction behavior and internal representations that closely mirror our construction. Together, our results offer a mechanistic account of how Transformers integrate hierarchical parsing with autoregressive generation, enabling them to closely approximate the grammar-induced next-token distribution.

Large language models like ChatGPT are remarkably good at predicting the next word in a sentence, but human language is full of nested structure — for example, a phrase inside a clause inside another clause, like a set of nesting dolls. Researchers still do not fully understand how these AI systems keep track of such hidden hierarchy while generating text one word at a time. We study this question in a controlled setting where the rules of the language are known exactly, allowing us to measure precisely what the model has learned. In this setting, we find that the model’s internal layers follow a local-to-global mechanism: early layers detect small, nearby patterns in the text, while later layers combine these patterns into a compact summary of the broader hierarchical context needed to predict what comes next. We also prove mathematically that Transformers can perform this kind of hierarchical reasoning efficiently. Remarkably, models trained from scratch spontaneously discover a similar structure, closely mirroring our theoretical construction. These findings provide a clearer window into how Transformer-based language systems process structure, and they support better tools for understanding and evaluating the language models that are increasingly used in real-world applications.