Mario Michelessa

The Expressivity Limits of Transformers

We study the fundamental expressivity limits of transformer models by formalizing the notion of accessible sequences---those that a transformer can produce for some prompt---and characterizing how accessibility depends on prompt length and model parameters. Our analysis provides a theoretical explan…