14 papers
Indexing: the Beginning and the End
Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia
We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of th…
Parity, Sensitivity, and Transformers
Alexander Kozachinskiy, Tomasz Steifer, PrzemysÅaw WaÅÈ©ga
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI. One of the fundamental problems in this context is the PARITY task, which…
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…
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…
Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth +2
Despite the wide use of -Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neigh…
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…