# How transformers learn structured data: insights from hierarchical filtering

arXiv: https://arxiv.org/abs/2408.15138 · HTML: https://mlsanity.com/paper/2408.15138/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 40 references that are in the map.
- First posted on arXiv 27 Aug 2024.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Curriculum learning for language modeling](https://mlsanity.com/paper/2108.02170/) (2021)
- [Deep Learning and Hierarchal Generative Models](https://mlsanity.com/paper/1612.09057/) (2016)
- [Mapping of attention mechanisms to a generalized Potts model](https://mlsanity.com/paper/2304.07235/) (2023)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [Sliding down the stairs: how correlated latent variables accelerate learning with neural networks](https://mlsanity.com/paper/2404.08602/) (2024)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (2024)
- [Emergence of order in random languages](https://mlsanity.com/paper/1902.07516/) (2019)
- [Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees](https://mlsanity.com/paper/2212.03362/) (2022)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)
- [Robustness of the Random Language Model](https://mlsanity.com/paper/2309.14913/) (2023)

## Built on by (most cited first, 18 of 18)

- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [Bigger Isn't Always Memorizing: Early Stopping Overparameterized Diffusion Models](https://mlsanity.com/paper/2505.16959/) (2025)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [A theory of learning data statistics in diffusion models, from easy to hard](https://mlsanity.com/paper/2603.12901/) (2026)
- [Biased Generalization in Diffusion Models](https://mlsanity.com/paper/2603.03469/) (2026)
- [Sampling Data with Chains of Forward-Backward Diffusion Steps](https://mlsanity.com/paper/2605.27006/) (2026)
- [Learn from your own latents and not from tokens: A sample-complexity theory](https://mlsanity.com/paper/2605.27734/) (2026)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [Towards Fundamental Language Models: Does Linguistic Competence Scale with Model Size?](https://mlsanity.com/paper/2509.02225/) (2025)
- [Distributional simplicity bias and effective convexity in Energy Based Models](https://mlsanity.com/paper/2605.07844/) (2026)
- [A Unified Framework for Critical Scaling of Inverse Temperature in Self-Attention](https://mlsanity.com/paper/2605.12697/) (2026)
- [A Fourier perspective on the learning dynamics of neural networks: from sample complexities to mechanistic insights](https://mlsanity.com/paper/2605.16913/) (2026)
- [Critical Percolation as a Synthetic Data Model for Interpretability](https://mlsanity.com/paper/2606.20347/) (2026)

## Abstract (arXiv)

Understanding the learning process and the embedded computation in transformers is becoming a central goal for the development of interpretable AI. In the present study, we introduce a hierarchical filtering procedure for data models of sequences on trees, allowing us to hand-tune the range of positional correlations in the data. Leveraging this controlled setting, we provide evidence that vanilla encoder-only transformers can approximate the exact inference algorithm when trained on root classification and masked language modeling tasks, and study how this computation is discovered and implemented. We find that correlations at larger distances, corresponding to increasing layers of the hierarchy, are sequentially included by the network during training. By comparing attention maps from models trained with varying degrees of filtering and by probing the different encoder levels, we find clear evidence of a reconstruction of correlations on successive length scales corresponding to the various levels of the hierarchy, which we relate to a plausible implementation of the exact inference algorithm within the same architecture.