9 papers
A Compositional Theory of Causally Masked Transformers
Franz Nowak, Ryan Cotterell, Reda Boumasmoud
The paper develops an algebraic framework to characterize what decision problems finite‑precision, causally masked transformers can solve, linking attention mechanisms to memory re…
An Algebraic View of the Expressivity of Recurrent Language Models
Franz Nowak, Ryan Cotterell, Reda Boumasmoud
What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equival…
From monoliths to modules: Decomposing transducers for efficient world modelling
Alexander Boyd, Franz Nowak, David Hyland +2
World models have been recently proposed as sandbox environments in which AI agents can be trained and evaluated before deployment. While realistic world models often have high com…
Bridging Expressivity and Scalability with Adaptive Unitary SSMs
Arjun Karuvally, Franz Nowak, Anderson T. Keller +3
Recent work has revealed that state space models (SSMs), while efficient for long-sequence processing, are fundamentally limited in their ability to represent formal languages-part…
The Harmonic Structure of Information Contours
Eleftheria Tsipidi, Samuel Kiegeland, Franz Nowak +5
The uniform information density (UID) hypothesis proposes that speakers aim to distribute information evenly throughout a text, balancing production effort and listener comprehensi…
A Fast Algorithm for Computing Prefix Probabilities
Franz Nowak, Ryan Cotterell
Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG). Good algorithms for the problem have…