Ilmu Komputer & AI editorial
Open AccessOA2026
Transformer Heads Looking for Order
A 2-head 1-layer transformer can check bit sequence ordering, while 1-head 1-layer cannot, even with an output MLP.
Jasper van Doornmalen; Alexander Kozachinskiy; Corinna Mathwieser; Tomasz Steifer; Felipe Urrutia; José Verschae; Przemysław Andrzej Wałȩga· 2026· DOI 10.48550/arXiv.2609.25588
The core problem
The paper investigates the computational capabilities of transformers, specifically focusing on the problem of determining whether a sequence of bits is ordered (i.e., non-decreasing). Prior work has explored similar problems, but this study introduces a model where transformers include an output multi-layer perceptron (MLP). The central question is: can a transformer with a single layer and a limited number of attention heads solve the ordering task? The authors show a separation: 1-head 1-layer transformers cannot, but 2-head 1-layer transformers can. This result contributes to the understanding of how attention head count affects expressivity in transformer architectures.
Innovation
The main results are twofold:
1. **Impossibility for 1 head**: There is no 1-head 1-layer transformer with an output MLP that correctly checks whether a bit sequence is ordered for all input lengths.
2. **Possibility for 2 heads**: There exists a 2-head 1-layer transformer with an output MLP that correctly checks whether a bit sequence is ordered.
These results hold under the standard transformer model with an output MLP. The authors do not provide explicit error bounds or sample complexity, as the focus is on exact computation. The separation is strict: adding a second attention head enables the solution of a problem that is otherwise impossible.
The paper investigates the computational capabilities of transformers, specifically focusing on the problem of determining whether a sequence of bits is ordered (i.e., non-decreasing). Prior work has explored similar problems, but this study introduces a model where transformers include an output multi-layer perceptron (MLP). The central question is: can a transformer with a single layer and a limited number of attention heads solve the ordering task? The authors show a separation: 1-head 1-layer transformers cannot, but 2-head 1-layer transformers can. This result contributes to the understanding of how attention head count affects expressivity in transformer architectures.
The authors analyze the ordering problem under the transformer model with an output MLP. Formally, given an input sequence
, the task is to output 1 if
and 0 otherwise. The transformer architecture considered consists of a single layer with attention heads, followed by an output MLP. The attention mechanism computes for each position a weighted sum of values from all positions, with weights determined by softmax over query-key dot products. The output MLP then processes the concatenated attention outputs. The authors prove that for , no such transformer can solve the ordering problem, while for , there exists a transformer that does. The proof for the impossibility likely uses a counting or communication complexity argument, while the construction for explicitly designs attention patterns and MLP weights. A Mermaid diagram illustrating the architecture is shown below.
Why it matters
The findings highlight the role of attention head count in transformer expressivity. The ordering problem is a simple yet fundamental task that requires comparing adjacent elements. A single attention head can only compute a global average or a single pattern, which is insufficient to detect local violations of order. With two heads, the model can simultaneously attend to different aspects, such as the current bit and the previous bit, enabling the detection of inversions. This result complements previous work on transformer limitations, such as the inability to solve parity or majority with limited heads. The inclusion of an output MLP does not overcome the 1-head limitation, emphasizing that the bottleneck is in the attention mechanism. Future work could explore the minimum number of heads required for other sequence tasks and the impact of depth. The taxonomy candidates (Architecture, Cybersecurity, Network, Cryptography) suggest potential applications in security protocols where ordering checks are relevant, such as in cryptographic nonce validation or network packet ordering.
Who should read this
CS practitioners and researchers
Opening member content…