arXiv paper2026-09-22· theoretical computer science (machine learning theory, transformer expressivity)· theory/proof note (short paper)

Transformer Heads Looking for Order

Q: What is the main result of 'Transformer Heads Looking for Order'?

The paper proves that ORDERED — the language of binary strings with no 1 occurring before a 0 (e.g. 0011 is ordered, 0110 is not) — can be recognized by a one-layer transformer with 2 attention heads plus an output MLP, but cannot be recognized by any one-layer transformer with only 1 head, even when the input embedding is completely unrestricted.

Q: Why does the output MLP matter for this separation result?

Earlier examples of tasks separating 2 heads from 1 head were for attention-only transformers. With an output MLP those examples break: for a fixed input length the MLP could simply memorize the function. This note is a separation that remains valid in the harder model that includes the output MLP.

Q: How is the impossibility proof for 1 head constructed?

First, any 1-head 1-layer transformer's output is encoded as a quantifier-free formula over real addition and order, applied to linear (degree-1) polynomials of the input bits (Lemma 2). If it computed ORDERED, then a fixed number C of halfspaces would separate the ordered vertices of the n-dimensional Boolean cube from the non-ordered ones. A graph-coloring argument reduced to the Erdős–Rado Ramsey theorem shows that the number of halfspaces needed grows without bound as n increases (Lemma 3), a contradiction.

Q: Did the authors use AI to write the paper?

Partially disclosed in Remark 6: the idea to apply the hypergraph Ramsey theorem for the lower bound emerged from a conversation with an LLM. The authors state that all other parts of the proof and the writing of the paper were performed without AI assistance.

Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser, Tomasz Steifer, Felipe Urrutia, José Verschae, Przemysław Andrzej Wałȩga

View original paper ↗arXiv:2609.25588

cs.AI · cs.LG

Quick verdict

Proves ORDERED separates 2-head from 1-head 1-layer transformers with output MLP; sound, elegant Ramsey-based proof, but §3.1 case-split has a likely typo.

Summary

This short theory note proves a strict head-separation for 1-layer transformers that include an output MLP: the language ORDERED (binary strings with no 1 occurring before a 0, e.g. 0011 yes, 0110 no) is computable by a 2-head 1-layer transformer but not by any 1-head 1-layer transformer, even with arbitrary input embeddings (Theorem 1). The upper bound (§3.1) uses an additive, length-independent embedding (i, i², x_i): one head softly retrieves the position of the last 0, the other the first 1, and the output MLP compares the two, with special handling of all-constant inputs. The lower bound (Lemma 2) shows a 1-head 1-layer transformer's output can be written as a quantifier-free formula over real addition and order, (R,<,+), evaluated on degree-1 polynomials of the input bits — avoiding the multiplications required in the multi-head embedding of Kozachinskiy et al. (2026). Lemma 3 then proves the minimal number of halfspaces separating ordered from non-ordered vertices of the n-cube diverges, via a graph-coloring chain reduced to the Erdős–Rado Ramsey theorem. Unlike attention-only separations (Tesfaye et al.; Rajaraman et al.), the result survives the output MLP; it complements Steifer–Naskręcki's h+1-vs-h separations, which need non-additive embeddings. Limitations: the §3.1 case-split condition appears typo-swapped (as printed, '01' and constant strings are misclassified); several concentration bounds are asserted without proof; no experiments; the k ≥ 3 additive-embedding separation remains open.

Review complete

Assessment at a glance

theoretical computer science (machine learning theory, transformer expressivity)

risk flags identified

● high 0

● medium 1

● low 2

Reproducibility readinessmedium

Code & data availablenot stated

Review confidencehigh

AI text signal0/20 passages flagged

Deep research viableCode-reproducible

5 strengths · 5 weaknesses · 5 author questions

AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.

Levels reflect verification complexity — not a quality score. Evolve never rates your paper.

Key claims under review

ORDERED is computable by a 2-head 1-layer transformer with output MLP, using an additive length-independent embedding (i, i², x_i) (Theorem 1, §3.1).
ORDERED is not computable by any 1-head 1-layer transformer with output MLP, even with arbitrary non-additive input embeddings (Theorem 1, Lemmas 2–3).
One-head 1-layer transformers embed into quantifier-free first-order formulas over (R,<,+) evaluated on degree-1 polynomials of the input bits, avoiding the multiplications needed in the multi-head case of Kozachinskiy et al. (2026) (Lemma 2).
The minimal number of halfspaces separating ordered from non-ordered vertices of the n-cube, θn, diverges with n, proved via a graph-coloring chain and the Erdős–Rado Ramsey theorem (Lemma 3, §3.2).

Strengths

Separation survives the output MLP
Prior head-separations (Tesfaye et al., ICLR 2026; Rajaraman et al., arXiv:2609.04046) are attention-only and collapse once an output MLP is added, since for fixed input length the MLP can memorize the function (§1). Theorem 1 is a clean language separation (ORDERED) that holds in this harder model.
Multiplication-free FO embedding for one head
Lemma 2 embeds 1-head 1-layer transformers into quantifier-free (R,<,+) over degree-1 polynomials (Ferrante–Rackoff 1975); footnote 1 pinpoints why one head suffices — two heads yield two softmax denominators, and clearing them breaks linearity. This observation unlocks the whole lower-bound pipeline.
Elegant, self-contained geometric lower bound
Additive upper-bound embedding
Transparent AI-use disclosure

Weaknesses

Case-split condition in §3.1 is wrong as printed
Key bounds asserted, not proven
Limited novelty scope
No numerical validation whatsoever
Presentation errata

Full Review Report

$1.99 · one-time

Unlock the complete preliminary analysis Evolve produced for this paper.

Report preview

Scope & Claims

This is a short (8-page) theory note on the expressivity of one-layer transformers. The model is the standard softmax attention layer with a position-wise ReLU output MLP (eqs. (1)–(4)), fixed dimension and parameters, and an input embedding E(x_i, i, n) that may depend on token, position and length; for the lower bound even additivity of the embedding is not assumed. The single claim (Theorem 1) is a strict head-separation: ORDERED — the language of binary strings with no 1 before a 0 — is computed by a 2-head 1-layer transformer but by no 1-head 1-layer transformer, in both cases with the output MLP present. The abstract and §1 position this against attention-only separations (Tesfaye et al., ICLR 2026; Rajaraman et al., arXiv:2609.04046), which break in this model because a fixed input length lets the MLP memorize any function, and against Steifer–Naskręcki (2026), who already separate h+1 vs h heads for all h ≥ 1 with an output MLP but need a non-additive embedding for their upper bound. The scope is honest: the new ground is the k = 2-vs-1 case with an additive upper bound, and §1 explicitly states the k ≥ 3 additive-embedding open problem.

Methodology Assessment

The upper bound (§3.1) is clean in design: the additive embedding (i, i², x_i) makes head 1's logits i·n − x_i·n² maximal at the last 0 and head 2's logits x_i·n² − i·n maximal at the first 1, with margin ≥ n (eqs. (10)–(11)); soft-attention averaging then lands within 0.1 of the argmax positions, and the output MLP applies 0.2-threshold comparisons, with a special case for all-constant strings. However, the case-split condition is written as |i*0 − 1| + |i*1 − n| < 0.2, which is almost certainly a 1↔n swap. As printed, x = '01' (i0 = 1, i1 = 2 = n) enters the x*-com

The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.

All 5 strengths & 5 weaknesses, analyzed in detail
3 risk flags with severity, section & reviewer questions
Methods & statistical evidence assessment
5 questions a peer reviewer would ask
Full six-dimension evaluation report & recommendations

One-time purchase · this paper only

One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.

Frequently asked questions

What is the main result of 'Transformer Heads Looking for Order'?

The paper proves that ORDERED — the language of binary strings with no 1 occurring before a 0 (e.g. 0011 is ordered, 0110 is not) — can be recognized by a one-layer transformer with 2 attention heads plus an output MLP, but cannot be recognized by any one-layer transformer with only 1 head, even when the input embedding is completely unrestricted.

Why does the output MLP matter for this separation result?

Earlier examples of tasks separating 2 heads from 1 head were for attention-only transformers. With an output MLP those examples break: for a fixed input length the MLP could simply memorize the function. This note is a separation that remains valid in the harder model that includes the output MLP.

How is the impossibility proof for 1 head constructed?

First, any 1-head 1-layer transformer's output is encoded as a quantifier-free formula over real addition and order, applied to linear (degree-1) polynomials of the input bits (Lemma 2). If it computed ORDERED, then a fixed number C of halfspaces would separate the ordered vertices of the n-dimensional Boolean cube from the non-ordered ones. A graph-coloring argument reduced to the Erdős–Rado Ramsey theorem shows that the number of halfspaces needed grows without bound as n increases (Lemma 3), a contradiction.

Did the authors use AI to write the paper?

Partially disclosed in Remark 6: the idea to apply the hypergraph Ramsey theorem for the lower bound emerged from a conversation with an LLM. The authors state that all other parts of the proof and the writing of the paper were performed without AI assistance.

About this review

This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.

Math typesetting is heavily mangled in the extracted text (sub/superscripts, eq. (2)'s Σ artifact); judgments rest on the proof structure, which is fully present including all lemmas, proofs and references.
The §3.1 case-split condition was read from the extracted text; it appears identically in both occurrences, so the flagged error is very likely in the PDF itself, but the authors should confirm against the source.
The block table in §3.2 is hard to parse from the text extraction; the surrounding argument was reconstructed and verified independently.
No figures exist to analyze; the only loose end is whether the PDF resolves 'Pm' in eq. (2) as Σ_{i=1}^n.

Go deeper on this paper

Wrote a paper? Stress-test it before reviewers do.

Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.

Scan your paper