Transformer Heads Looking for Order

Jasper van Doornmalen; Alexander Kozachinskiy; Corinna Mathwieser; Tomasz Steifer; Felipe Urrutia; Jos\'{e} Verschae; Przemys{\l}aw Andrzej Wa{\l}\c{e}ga

AI & machine learningLearning theory & optimization

Transformer Heads Looking for Order

Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser, Tomasz Steifer, Felipe Urrutia, Jos\'{e} Verschae, Przemys{\l}aw Andrzej Wa{\l}\c{e}ga

Preprint

In the authors' words

In this note, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transformer. Unlike similar previous results, our results assume the model where transformers have an output MLP.

Main resultLimitation the authors admit

Read the paper PDF

Appeared: Wednesday, September 23. arXiv. Preprint, not yet peer-reviewed.

AI & machine learning Learning theory & optimization Sep 23, 2026
Continuous Optimization for p-adic Models
We present the first method for native, continuous gradient descent for machine learning models with $p$ -adic parameters.
Julian Salazar, Dimitri Kanevsky, Matt Harvey and 2 more — arXiv
PreprintBold claims, read criticallyClaims a big stepCode available
AI & machine learning Learning theory & optimization Sep 23, 2026
xWhyL: Causal Interactive Learning
To fill this gap, we propose xWhyL, a formal framework connecting causality and XAI by learning causal models from explanations.
Nicholas Tagliapietra, Florian Peter Busch, Moritz Willig and 4 more — arXiv
Preprint
AI & machine learning Learning theory & optimization Sep 23, 2026
Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis
We propose DeepMVSA, which re-expresses the minimum-volume principle in neural implicit form: a lightweight coordinate network generates the mixing weights and a triangular LU-type parameterization the dual simplex matrix, reducing the trainable-state memory to $O (K^{2})$ , independent of $N$ , and the cost per data pass to $O (N K^{2})$ .
Jun LI, Yanlong Guo, Zhaozhao Zeng — arXiv
Preprint
AI & machine learning Learning theory & optimization Sep 23, 2026
Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
We give a new analysis of the ubiquitous Oja's algorithm [Oja82] for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underlying mean matrix, complemented by a nearly-matching lower bound.
Anming Gu, Syamantak Kumar, Kevin Tian and 1 more — arXiv
Preprint
AI & machine learning Learning theory & optimization Sep 23, 2026
Neutral-Atom-based Quantum Optimization for Resource Allocation in NOMA Networks
In this paper, we investigate the use of neutral-atom quantum platforms to solve the maximum access problem (MAP), formulated as a mixed-integer programming task that jointly considers admission control, user clustering, channel assignment, and power allocation in a non-orthogonal multiple access (NOMA)-enabled uplink network.
Patatchona Keyela, Remon Polus, Soumaya Cherkaoui and 1 more — arXiv
PreprintReal-world use

All new papers on Learning theory & optimization

Transformer Heads Looking for Order

In the authors' words

More on Learning theory & optimization that day

Continuous Optimization for p-adic Models

xWhyL: Causal Interactive Learning

Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis

Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

Neutral-Atom-based Quantum Optimization for Resource Allocation in NOMA Networks