Reproduce “How transformers learn structured data: insights from hierarchical filtering” on OpenResearch

About this paper

Jerome Garnier-Brun, Marc Mézard, Emanuele Moscato, Luca Saglietti

Researchers at Università Bocconi investigated how Transformer encoders process hierarchical data, demonstrating they approximate Belief Propagation, an exact inference algorithm, and exhibit sequential learning dynamics with attention maps reflecting the data's tree structure. The work shows Transformers achieve optimal performance and produce calibrated probabilities matching exact marginals, alongside revealing how self-supervised pre-training accelerates downstream task learning.

Key insights

• Transformers can achieve near-optimal performance and produce calibrated probabilistic predictions that closely match the exact marginals from the Belief Propagation oracle, suggesting algorithmic equivalence.
• The learning process is sequential, with Transformers progressively discovering and incorporating longer-range hierarchical correlations over time, showing a 'staircase' learning dynamic.
• Attention maps and internal layer representations within the Transformer reflect the hierarchical structure of the generative tree, consistent with a plausible message-passing implementation similar to Belief Propagation.

Summary by alphaXiv.