Inductive Biases and Variable Creation in Self-Attention Mechanisms
  Self-attention, an architectural motif designed to model long-range
interactions in sequential data, has driven numerous recent breakthroughs in
natural language processing and beyond. This work provides a theoretical
analysis of the inductive biases of self-attention modules, where our focus is
to rigorously establish which functions and long-range dependencies
self-attention blocks prefer to represent. Our main result shows that
bounded-norm Transformer layers create sparse variables: they can represent
sparse functions of the input sequence, with sample complexity scaling only
logarithmically with the context length. Furthermore, we propose new
experimental protocols to support this analysis and to guide the practice of
training Transformers, built around the large body of work on provably learning
sparse Boolean functions.
