11 papers
Language Generation: Complexity Barriers and Implications for Learning
Marcelo Arenas, Pablo Barceló, Luis Cofré +1
Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually g…
Decoupling Positional and Symbolic Attention Behavior in Transformers
Felipe Urrutia, Jorge Salas, Alexander Kozachinskiy +3
An important aspect subtending language understanding and production is the ability to independently encode positional and symbolic information of the words within a sentence. In T…
Message Passing on the Edge: Towards Scalable and Expressive GNNs
Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy +3
Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attenti…
All Kolmogorov complexity functions are optimal, but are some more optimal?
Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
Kolmogorov (1965) defined the complexity of a string as the minimal length of a program generating . Obviously this definition depends on the choice of the programming langu…
Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models
Hector Pasten, Felipe Urrutia, Hector Jimenez +3
Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existen…
A completely uniform transformer for parity
Alexander Kozachinskiy, Tomasz Steifer
We construct a 3-layer constant-dimension transformer, recognizing the parity language, where neither parameter matrices nor the positional encoding depend on the input length. Thi…