  While the successes of transformers across many domains are indisputable,
accurate understanding of the learning mechanics is still largely lacking.
Their capabilities have been probed on benchmarks which include a variety of
structured and reasoning tasks -- but mathematical understanding is lagging
substantially behind. Recent lines of work have begun studying representational
aspects of this question: that is, the size/depth/complexity of attention-based
networks to perform certain tasks. However, there is no guarantee the learning
dynamics will converge to the constructions proposed. In our paper, we provide
fine-grained mechanistic understanding of how transformers learn "semantic
structure", understood as capturing co-occurrence structure of words.
Precisely, we show, through a combination of mathematical analysis and
experiments on Wikipedia data and synthetic data modeled by Latent Dirichlet
Allocation (LDA), that the embedding layer and the self-attention layer encode
the topical structure. In the former case, this manifests as higher average
inner product of embeddings between same-topic words. In the latter, it
manifests as higher average pairwise attention between same-topic words. The
mathematical results involve several assumptions to make the analysis
tractable, which we verify on data, and might be of independent interest as
well.
