Specifying exact circuit algorithms in universal transformers

Understanding how transformers can execute specific algorithmic and symbolic computations remains a challenge in artificial intelligence. Prior work has demonstrated that standard transformers have trouble generalizing algorithmic problems of arbitrary length (i.e., length generalization), such as arithmetic problems. Here we present an interpretable and modular framework for specifying exact algorithmic computations with universal transformers that enable these models to perfectly solve algorithmic problems of arbitrary depth (length), without any training. In particular, by formulating algorithmic problems as computable circuits, we exactly map circuit computations onto components of the universal transformer architecture. We showcase this ability by specifying universal transformers that perfectly solve two fundamental algorithmic problems: modular arithmetic and Boolean logic. Notably, these two models demonstrate how transformers can generalize to problems of any length using interpretable architectural modifications. This framework can be naturally adopted for any algorithmic problem that can be formulated as a circuit, illustrating exactly how transformers can implement arbitrary circuit algorithms. More broadly, this framework provides an existence proof of transformer models capable of implementing exact algorithms, providing avenues of opportunity for exploring their learnability in future work.