1 citations · 2 across the 10 of their papers we have counts for
12 papers
A Compositional Theory of Causally Masked Transformers
Franz Nowak, Ryan Cotterell, Reda Boumasmoud
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 u…
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…
An Algorithm for Deterministic Weighted Regular Languages
Clemente Pasti, Talu Karagöz, Anej Svete +3
Extracting finite state automata (FSAs) from black-box models offers a powerful approach to gaining interpretable insights into complex model behaviors. To support this pursuit, we…
Surprise! Uniform Information Density Isn't the Whole Story: Predicting Surprisal Contours in Long-form Discourse
Eleftheria Tsipidi, Franz Nowak, Ryan Cotterell +3
The Uniform Information Density (UID) hypothesis posits that speakers tend to distribute information evenly across linguistic units to achieve efficient communication. Of course, i…
Lower Bounds on the Expressivity of Recurrent Neural Language Models
Anej Svete, Franz Nowak, Anisha Mohamed Sahabdeen +1
The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities thr…
On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
Franz Nowak, Anej Svete, Alexandra Butoi +1
The performance of modern language models (LMs) has been improved by chain-of-thought (CoT) reasoning, i.e., the process of generating intermediate results that guide the model tow…
What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages
Nadav Borenstein, Anej Svete, Robin Chan +5
What can large language models learn? By definition, language models (LM) are distributions over strings. Therefore, an intuitive way of addressing the above question is to formali…
On the Representational Capacity of Recurrent Neural Language Models
Franz Nowak, Anej Svete, Li Du +1
This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs wit…
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…