What tasks can transformers perform on sequences of any length? The answer depends on how attention is evaluated under the hood. With fixed evaluation order and finite precision, transformers are acyclic automata, meaning they can maintain finite memory but cannot count.
arxiv.org/abs/2607.26988
arxiv.org
A Compositional Theory of Causally Masked Transformers
What types of decision problems can a causally masked, finite-precision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precisio...
