Transformer Heads Looking for Order
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 3 of its 7 references that are in the map. First posted on arXiv 22 Sep 2026.
Builds on
3 of 7 references.
References · 3
- 2026Parity, Sensitivity, and Transformerscited by 5
- 2026The Head Complexity of Boolean Functions in Single-Layer Attentioncited by 2
- 2026The relaxation complexity of the standard simplex is logarithmiccited by 1
Built on by
Not cited yet.