Research map / Architectures and efficiency / Attention and transformers
How Transformers Learn Structured Data: Insights From Hierarchical Filtering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a filtered hierarchical tree-based data model with exact Belief Propagation inference and shows that encoder-only transformers trained on root classification and masked language modeling approximate BP, learning longer-range correlations sequentially and implementing BP-like computation across layers.
Problem
Understanding how transformers implement and learn optimal inference on hierarchically structured sequences, where correlations span different length scales.
Approach
A tunable filtered hierarchical tree model of sequences (log-normal transition tensor, filtering parameter k truncating hierarchy) gives access to exact BP marginals, allowing calibrated comparison of transformer outputs with the exact algorithm, attention-map analysis, and layer-wise probing of ancestor information.
Key results
- Transformers trained on root classification and MLM reach the exact BP accuracy in-sample and out-of-sample, including on mismatched filtered test data.
- KL divergence between transformer predictions and BP marginals goes to near zero, with the model aligning sequentially to BP_k for decreasing k during training (longer-range correlations learned later).
- Attention maps of MLM-trained models with n_L=ell=4 show hierarchical blocks mirroring the tree, and layer-wise probing recovers ancestors up to the probed layer's level.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train an encoder-only transformer on root classification | Vanilla encoder-only transformer · Root classification on hierarchical sequences | accuracy | Helped |
| Train an encoder-only transformer with masked language modeling | Vanilla encoder-only transformer · Masked language modeling on hierarchical sequences | accuracy | Helped |
| Use MLM pretraining before root-classification fine-tuning | Transformer encoder · Root classification on fully hierarchical data | labeled training samples required for optimal inference | Helped |
| Use more attention layers (ablation) | Transformer on root classification · Unfiltered hierarchical data | sample efficiency | Helped |
| Reduce attention layers from 4 to 3 (ablation) | Transformer on root classification · Unfiltered hierarchical data | accuracy | No clear effect |
| Reduce attention layers to 1 (ablation) | Transformer on root classification · Unfiltered hierarchical data | sample efficiency | Hurt |
| Use a single feed-forward layer instead of attention for fully filtered data (ablation) | Transformer on root classification · Fully filtered hierarchical data | inference accuracy | No clear effect |
| Train on full hierarchy and test on data with different filtering levels | Transformer trained on k_train=0 data · Root classification, filtered test data | accuracy | Mixed |
| Train on fully hierarchical data for longer | Transformer on root classification · Root classification during training | alignment with BP predictions | Helped |
| Train on fully hierarchical data for longer | Transformer on masked language modeling · Masked language modeling during training | alignment with BP predictions | Helped |
| Use fewer attention layers than tree depth (ablation) | Transformer on root classification · Unfiltered hierarchical data | accuracy | Mixed |
| Train the model on filtered rather than fully hierarchical data (ablation) | Transformer encoder · Attention maps on masked language modeling | alignment with the hierarchical correlation structure | Mixed |
Surprising findings
- A single-head transformer with ell blocks can implement BP despite the absence of a downward pass, using O(q^2) memory slots per token.
- Transformer logits are calibrated to BP marginals even for ambiguous filtered data trained with hard one-hot labels.
Limitations
- Fixed tree topology and non-overlapping transition tensors; variable-length, unknown-topology grammars left for future work.
- Results shown for a single grammar realization (q=4, sigma=1) in main text, with limited other-grammar checks in appendix.
- Existence proof of BP implementation is idealized; trained model not shown to exactly implement it.
Experimental setup
Datasets: synthetic hierarchical tree-generated sequences
Benchmarks: synthetic root classification accuracy synthetic masked language modeling accuracy
Metrics: accuracy Kullback-Leibler divergence Spearman correlation prediction match
Baselines: Belief Propagation oracle (BP_k)
Builds on: Random Hierarchy Model probabilistic context-free grammars inside-outside algorithm transformer encoder
Closest papers by meaning
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.88)
- How Transformers Learn Causal Structure with Gradient Descent (ICML 2024 · similarity 0.88)
- Banyan: Improved Representation Learning with Explicit Structure (ICML 2025 · similarity 0.88)
- Transformers Converge to Invariant Algorithmic Cores (NeurIPS 2026 · similarity 0.88)
- Distilling Sequential Computation in Transformer Language Models (NeurIPS 2026 · similarity 0.87)
- Selective Induction Heads: How Transformers Select Causal Structures in Context (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.