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. First, we settle an open question by
constructing a transformer that recognizes PARITY with perfect accuracy, and
similarly for FIRST. Second, we use layer normalization to bring the
cross-entropy of both models arbitrarily close to zero. Third, when
transformers need to focus on a single position, as for FIRST, we find that
they can fail to generalize to longer strings; we offer a simple remedy to this
problem that also improves length generalization in machine translation.

该研究研究了 Transformer 网络在接受依赖于单一输入符号的语言中的限制，并通过使用 PARITY 和 FIRST 语言作为例子，证明了三种克服该限制的方法。