7 papers
Length Generalization for Transformers via Compression
Georg Zetzsche, Hongjian Jiang, Andy Yang +4
Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a…
The Polynomial Counting Capabilities of Message Passing Neural Networks
Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin
The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshol…
Why Are Linear RNNs More Parallelizable?
William Merrill, Hongjian Jiang, Yanhong Li +2
The community is increasingly exploring linear RNNs (LRNNs) as language models, motivated by their expressive power and parallelizability. While prior work establishes the expressi…
Length Generalization Bounds for Transformers
Andy Yang, Pascal Bergsträßer, Georg Zetzsche +2
Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a g…
Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
Kilian Lichtner, Pascal Bergsträßer, Moses Ganardi +2
Ramsey quantifiers have recently been proposed as a unified framework for handling properties of interests in program verification involving proofs in the form of infinite cliques,…
Probability Distributions Computed by Autoregressive Transformers
Andy Yang, Anej Svete, Jiaoda Li +4
Most expressivity results for transformers treat them as language recognizers -- devices that accept or reject strings -- rather than as they are used in practice: as language mode…