7 papers
Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoders
Tomasz Steifer
We investigate the expressive power of hybrid recurrent-attention decoders, a class of architectures used in recent open-source language models such as Qwen3-Next and its successor…
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…
Computable universal online learning
Dariusz KalociÅski, Tomasz Steifer
Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learni…
Strassen Attention, Split VC Dimension and Compositionality in Transformers
Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez +6
We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations…
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…
Optimal bounds for dissatisfaction in perpetual voting
Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proport…