4 papers
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…
Transformers are Inherently Succinct
Pascal BergsträÃer, Ryan Cotterell, Anthony W. Lin
We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a c…
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…
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,…