Overcoming a Theoretical Limitation of Self-Attention

Understand

Although transformers are remarkably effective for many tasks, there are some surprisingly easy-looking regular languages that they struggle with.

• Hahn shows that for languages where acceptance depends on a single input symbol, a transformer's classification decisions become less and less confident (that is, with cross-entropy approaching 1 bit per string) as input strings get longer and longer.
• We examine this limitation using two languages: PARITY, the language of bit strings with an odd number of 1s, and FIRST, the language of bit strings starting with a 1.
• We demonstrate three ways of overcoming the limitation suggested by Hahn's lemma.