5 papers
Generating in the Limit with Infinitely Many Hallucinations
Irene Strauss, Alexandra Butoi, Ryan Cotterell
The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner task…
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
Blanka Köver, Alexandra Butoi, Anej Svete +2
Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is p…
Training Neural Networks as Recognizers of Formal Languages
Alexandra Butoi, Ghazal Khalighinejad, Anej Svete +3
Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds…
Algorithms for Weighted Pushdown Automata
Alexandra Butoi, Brian DuSell, Tim Vieira +2
Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency pars…
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…