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

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...

arxiv.org

Clemente Pasti, Talu Karag\"oz, Anej Svete, Franz Nowak, Reda Boumasmoud, Ryan Cotterell An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages https://arxiv.org/abs/2411.06228

Eleftheria Tsipidi, Franz Nowak, Ryan Cotterell, Ethan Wilcox, Mario Giulianelli, Alex Warstadt Surprise! Uniform Information Density Isn't the Whole Story: Predicting Surprisal Contours in Long-form Discourse https://arxiv.org/abs/2410.16062

Anej Svete, Franz Nowak, Anisha Mohamed Sahabdeen, Ryan Cotterell Lower Bounds on the Expressivity of Recurrent Neural Language Models https://arxiv.org/abs/2405.19222

Franz Nowak, Anej Svete, Alexandra Butoi, Ryan Cotterell On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning https://arxiv.org/abs/2406.14197

Transformer language models like Chat GPT, when using chain-of-thought reasoning, are Turing complete. Specifically, they can execute probabilistic algorithms and generate any computable weighted language youtu.be/MMIJKKNxvec?...

Transformer LLMs are Turing Complete after all !?

YouTube video by AI Coffee Break with Letitia

youtu.be

Yes… turning 30 soon - am I old now??