Two (narrow) heads are better than (an arbitrarily wide) one
Authors: Amanuel Tesfaye
Zeno Kujawa
Rajmohan Rajaraman
Ravi Sundaram
Venue: ICLR 2026 Poster (2026)
Keywords: Impossibility Result
Transformers
Attention mechanism
Graphs
Theory
Induction heads
In-context learning
Primary area: learning on graphs and other geometries & topologies
TL;DR: We prove a dimension-independent impossibility result for single-head transformers and study the representational limits of attention via a graph-based task.

Abstract: In this paper, we establish a dimension- and precision-independent impossibility result for a simplified transformer model. Due to their size, a comprehensive understanding of the internal operations of frontier large language models (LLMs) is beyond the reach of current methods, but research into small and interpretable models has proven successful. We study the representational limits of attention, the core of transformer models, through the lens of the Endpoint Selection Problem (ESP), a simple yet expressive learning task defined over arcs of a directed graph. 

Our main theoretical results are twofold: (i) 1-head, 1-layer, attention-only transformers cannot solve ESP on any graph containing a cycle, even with unbounded dimension and precision; but, all DAGs (Directed Acyclic Graph) are solvable with zero error (ii) in contrast, a 2-head, 1-layer, attention-only transformer can solve ESP on arbitrary directed graphs with constant embedding dimension and logarithmic precision. Prior lower bounds were conditional on bounds on dimension and precision. Through a transformation, we extend our impossibility result from ESP to the much studied 2-hop induction head problem. Further, we uncover a surprising connection to NP-completeness by showing that the optimal error of the 1-head transformer is exactly related to the size of MAS (Maximum Acyclic Subgraph) and hence inapproximable.

Finally, we validate our theory with experiments and observe that gradient-based optimization can reliably find 1-head solutions for DAGs and 2-head solutions for arbitrary graphs with cycles, whereas 1-head models struggle to reach the optimal solution in graphs with cycles.
We believe that our techniques are of independent interest and have the potential to establish a new fine-grained hierarchy of transformer architectures, each with greater problem-solving power than the last.

Published as a conference paper at ICLR 2026
TWO (NARROW) HEADS ARE BETTER THAN (AN ARBITRARILY WIDE) ONE"
Amanuel Tesfaye, Zeno Kujawa, Rajmohan Rajaraman & Ravi Sundaram Khoury College of Computer Sciences Northeastern University
ABSTRACT
In this paper, we establish a dimension- and precision-independent impossibility result for simplified transformer model. Due their size, comprehensive un- derstanding of the internal operations of frontier large language models (LLMs) is beyond the reach of current methods, but research into small and interpretable models has proven successful. We study the representational limits of attention, the core of transformer models, through the lens of the Endpoint Selection Prob- lem (ESP), simple yet expressive learning task defined over arcs of directed graph.
Our main theoretical results are twofold: (i) 1-head, 1-layer, attention-only trans- formers cannot solve ESP on any graph containing a cycle, even with unbounded dimension and precision; but, all DAGs (Directed Acyclic Graph) are solvable with zero error (ii) in contrast, a 2-head, 1-layer, attention-only transformer can solve ESP on arbitrary directed graphs with constant embedding dimension and logarithmic precision. Prior lower bounds (Peng et al., 2024; Sanford et al., 2024b) were conditional on bounds on dimension and precision. Through a transforma- tion, we extend our impossibility result from ESP to the much studied 2- 2-hop induction head problem. Further, we uncover a surprising connection to NP- completeness by showing that the optimal error of the 1-head transformer is ex- actly related to the size of MAS (Maximum Acyelic Subgraph) and hence inap- proximable.
Finally, we validate our theory with experiments and observe that gradient-basee optimization can reliably find 1-head solutions for DAGs and 2-head solutions for arbitrary graphs with cycles, whereas I-head models struggle to reach the optimal solution in graphs with cycles. We believe that techniques are of indepen- dent interest and have the potential to establish a new fine-gra -ee-graiied hierarchy transformer architectures, each with greater problem-solving power than the last.
INTRODUCTION
The transformer architecture (Vaswani et al., 2017) revolutionized artificial intelligence and made possible the astonishing performance of large language models (LLMs). These systems exhibit emergent abilitics, reasoning, planning, even apparent world knowledge, that seem disproportionate to the simplicity of their next-token prediction objective. However, despite this success, our under- standing why transformers work remains shallow. Fine-grained analyses of LLMs are far beyond the reach of current techniques. Their sheer scale, training complexity, and data dependence make rigorous proofs almost impossible. To make progress, researchers have turned to simplified trans- former models: one or two layers, few attention heads, and limited embedding dimensions, trading emergent phenomena for the possibility of mathematical analysis. Previous work has revealed sur- prising capabilities of such small transformers domains such as path-finding (Wang et al., 2024a), learning causal structures (Nichani et al., 2024), and compositional reasoning (Wang et al., 2025). However, unconditional boundaries, results that cleanly separate what a given architecture can and
PPartially supported by NSF CCF-2335187.
Emails: (tesfaye.am, kujawa.z, rrajaraman, r.sundara]] @northeastem.cdn

---

Published as a conference paper at ICLR 2026
cannot do, remain rare. Establishing such hierarchies is necessary stepping stone toward princi- pled understanding of how the emergent properties of full-scale LLMs arise and how we can further enhance them.
In this paper, we propose the Endpoint Selection Problem (ESP) as a natural test case. ESP requires selecting endpoint of an are in directed graph. This deceptively simple task is closely tied to graph traversal and selection primitives, which underlie many higher-level reasoning problems, from path-finding to decision making in structured domains. ESP can be generalized in multiple di- rections: hypergraphs, multi-step traversal, or probabilistic endpoint selection. Thus, understanding transformer performance on ESP is both intrinsically interesting and practically useful as a founda- tion for analyzing broader classes of algorithmic reasoning tasks.
Our central result establishes an unconditional impossibility; no 1-head, I-layer, attention-only transformer can solve ESP on any directed graph with cycles. This barrier is independent of preci- sion or embedding dimension (also referred to as width in the literature) in contrast to prior results that required stronger assumptions. At the same time, we demonstrate that a modest extension, two heads in a single layer, suffices to solve ESP on all directed graphs, with constant embedding di- mension and precision logarithmic in the number of vertices of the graph. Our proof techniques are not limited to ESP; rather, they provide a generalizable framework for analyzing transformer hierarchies. The typical transformer architecture consists of attention layers alternating with FFN (Feed-Forward Network) layers. Since a FFN with a single layer is already a universal approxima- tor (Hornik et al., 1989), in this paper focus attention-only transformers la (Nichani al., 2024). Recent theoretical work suggests that single attention layer with an exponential number of heads a universal sequence-ro-sqquenc approximator (Hu al., 2025). By charting the landscape of what successively more expressive transformer architectures can and cannot do, we aim to reveal the structure behind the 'magical' emergent properties of LLMs.
1.1 SUMMARY OF OUR RESULTS
Endpoint Selection Problem (ESP). We define ESP to be the task of correctly predicting the in- dicated endpoint (head or tail) of an arbitrary are directed graph. The input an ordered pair (representing the arc), a selector token, and fixed query token; the output should be the member of the ordered pair specified by the selector token. The input distribution is assumed to uniform over all ares and selectors, i... uniform over space of size 2m, given directed graph with arcs. A model is said to solve ESP perfectly, or with zero error, if it always seleets the correct endpoint. We set the temperature distribution (Hinton et al., 2015)) so that the model is deterministic.
(temperature is the hyperparameter that controls randomness in the output
1-head transformers. No model can solve ESP perfectly for any graphs with cycles, even embedding dimension and precision are unbounded (Theorem 2).
For any DAG with vertices, there exists 1-head model with embedding dimension O(n) that can solve ESP with zero error (Theorem 1).
No model can solve the well-studied 2-hop induction head problem (Olsson et al., 2022; Sanford et al., 2024c); our proof exploits a transformation from ESP to 2-hop induction head (Corollary l).
The optimal 1-head model's error is exactly 1 [MAS| where MAS is the Maximum Acyclic 2m
Subgraph, NP-complete problem (Theorem 1 and Corollary 2). It is NP-complete to even approximate the minimum error 1-head model for an arbitrary directed graph (Theorem 5).
2-head transformers. We prove that 2-head 1-layer attention-only transformer can solve ESP without error for any n-vertex directed graph, using (n)) dimension and ((1) precision (Theo- rem 3) or using O(1) embedding dimension and Olog rı) precision (Corollary 2).
Empirical analysis. Experiments corroborate our theoretical results gradient- based optimiza- tion can reliably find I-head solutions for ESP on DAGs and 2-head solutions for ESP on arbitrary graphs with cycles, whereas 1-head models struggle to reach the optimal solution in cyclic graphs.
Our ESP formulation is arguably the simplest problem yielding the impossibility and intractability results with attention-only models that we have derived. It enables us to extend our lower bounds to related well-studied problems. Furthermore, the graph-theoretic formulation establishes deeper connection between the representational capacity of a transformer for a given instance to the under- lying graph's structural properties.
2

---

Published as a conference paper at ICLR 2026
1.2
RELATED WORK
Our work contributes to the understanding of the capabilities of small transformer models. Several positive and negative results on transformer capabilities have been established in this field.
Transformer capabilities on graphs. In Wang et al. (2024a), it is demonstrated that constant-depth transformer models can be trained to find paths in a directed acyclic graph (DAG). The authors prove their claim by proposing a set of weights capable of achieving this task and showing that this set of weights can be found by using gradient descent. A classification of graph problems grouped by the model scales sufficient to solve them can be found in Sanford et al. (2024a). In Nichani et al. (2024), it is shown that a two-layer attention-oni only transformer model can learn latent causal structure in sequences. Further, they show that the transformer learns an induction head (Olsson et al., 2022) when sequences are generated from an in-context Markov chain.
Comparison to Index Lookup. Bhattamishra et al. (2024) analyze the Index Lookup problem, where a model must return the token at a specified position in a sequence using the index token as the query, and show that a I-layer, I-head transformer augmented with small FFN and logarithmic width can implement this task. Despite the similarity, the Index problem different from ESP, since in ESP the query token prevents the model from relying on direct key-query alignment between the selector token and the corresponding sequence position (or are endpoint). Indeed, our impossibilityy argument for ESP provides sharp separation from the logarithmie-width, logarithmic-precision model for Index in Bhattamishra et al. (2024). A second significant difference between the two formulations is that our ESP problem framework is defined over graphs and captures the limitations of one-head transformers and capability of two-head transformers to resolve the problem defined over different graph classes. In particular, our inapproximability result (Theorem 5) indicates that even finding 1- 1-head model that approximates accuracy to within 1.3606 factor is intractable. This enables us to identify limitations both the representation of the model as well as the intractability of finding weights in the model that will lead to desired level of accuracy.
Lower bound results. A lower bound for function composition is formally proved in Peng et al. (2024); using communication complexity arguments, they show that for attention-only 1 1-layer trans- former models with embedding dimension d, input domain size |.A| = |B] = |C|| = 71, with numbers represented with p bits, and H heads, function composition is impossible if (d 1)p < n nl n. Chen et al. (2024) extends this result to standard multi-layer transformers by showing that an L-layer transformer with sequence length n needs model dimension n ((1 to compose L functions.
Sanford, Hsu, and Telgarsky prove several complexity results for transformers in Sanford et al. (2023; 2024a) and Sanford et al. (2024c). They show that the I-hop induction head task (which is the task of returning, for two sequences of tokens (Ø1..... ox) and (TI...., Jx), where T; is the input token that follows the rightmost occurrence of the token equal to a, before position i) cannot be solved by I-layer attention-only transformer unless mph 2(n). where m is the embedding dimension, p is the precision, and is the number of attention heads. Since it is known from previous work that a 2-yayer attention-only transformer with h- O(1). m - 0(1). p = (log(n)) can solve this task, the size lower bound for l-layer attention-only transformers is exponentially larger than for 2-layer attention-only transformers (Sanford et al., 2024b; Bietti et al.. 2023). In Sanford et al. (2023), the tasks Match2 and Match3 are introduced, in which for a sequence X = [M] the output a vector V where V/2 = 1 iff there is a pair of elements in X such that x; + x, = mod M (or a triplet in the case of Match3). They then show that Match2 can be solved by 1-layer 1-head transformer, while a single-layer multihead transformer shown in Kozachinskiy et al. (2025) that even with infinite precision, a single-layer transformer with size n 2(1) can solve neither Match3 nor the composition task given in Peng et al. (2024).
II)) E
not sufficient for Match3. It is
Proofs of transformer advantages. In Sanford et al. (2023), the authors propose an averaging task that demonstrates the performance gained by increasing embedding dimension as well as an efficiency improvement of an attention-only 1-layer transformer over recurrent and fully connected neural networks. This result is expanded upon in Wang et al. (2024b), where a simpler version of this task is used to show that is efficiently learnable with a convergence guarantee for 1-layer attention-only transformer, while fully-connected neural network must have exponentially more neurons in its first layer than the minimum width required for the transformer.
3

---

Published as a conference paper at ICLR 2026
Circuit complexity results. Another set of complexity theoreeic results for Transformers can be found in Merrill & Sabharwal (2023; 2024a;b). In Merrill & Sabharwal (2023), it is shown that transformers with constant depth, context length n, and precision O n) can be simulated by uniform constant-depth threshold circuits, thus proving they cannot solve problems beyond uniform TC such graph connectivity. The same is shown be true for transformers using average-hard attention in Merrill et al. (2022), which is extended to uniform TC in Strobl (2023). Furthermore, in Chiang (2025), it is shown that transformers with either attention score computation method are in DLOGTIME-unifomm TC with softmax attention assuming in Merrill & Sabharwal (2024a) that log-depth transformers solve graph connectivity, improv- ing our understanding of the performance improvements attainable with increased depth. They also show that for fixed-depth transformer, the hidden dimension must grow superpolynomiall with input length in order for the transformer to solve regular language recognition and graph connectiv- ity. Furthermore. they prove that a transformer with Ollog n) chain-of-thouge steps cannot solve any problem outside of TC A function composition task is discussed in Wang et al. (2025), where the authors show that a complex compositional task called k-fold composition can be learned by transformer with Ollog k) layers. In Chen et al. (2025), it is shown that constant- depth transformer of poly(n) (niszz) -size with (oly(n)-pp))) -pplyii)-rreiiion using rotary position embeddings (RoPE) can be simulated by DLOGTIMEE-unffom TC circuit family unless TC" NC Other circuit complexity results are presented in Cao et al. (2025); Hahn (2020); Strobl et al. (2024).
-preeennciireeiionnn It was shown
Empirical evaluation of multi-head attention. In Michel al. (2019), the authors show that for some tasks, transformer models do not exploit the flexibility provided by multi-head attention and do not suffer from significant performance degradation when pruned from many heads to fewer heads per layer. Several other work exists in this area, such as Liu et al. (2021) and Voita et al. (2019).
2 PROBLEM SETUP AND TRANSFORMER MODEL
To analyze the representational power of attention heads, we introduce the Endpoint Selection Problem (ESP), supervised learning task defined ares of directed graph g (V, E). Its
vocabulary set S consists of:
S (UI,..., J
[1,2)
vertex tnkens V
indicator tokens I
token
Given an are (u, v) E E, an indicator E I, and the query #, the input sequence is (u, v, i, #), and the model must output if 1 and u if 2.
Fixing the query token restricts the model, effectively transforming ESP to a 2-hop induction head task (as we show in Appendix A). This task, studied in previous work (Sanford et al., 2024c), is natural extension of the original induction head problem analyzed in Olsson et al. (2022). Its more general form, the k-hop induction head, is closely related to other sequential reasoning problems, such as pointer chasing (Sanford et al., 2024c; Peng et al., 2024) and k-fold composition (Wang al., 2025).
Transformer model. For brevity, we follow notation similar to Nichani et al. (2024). Let the input sequence be SI.T = (si,..., ST) S"f where S is the vocabulary. The sequence embedded as X = embed S1.1; P), with:
X, E., P. fori=1,....
where X, Txd and E E T S]
where E and P are the token and positional embedding matrices, respectively. A single layer attention-only transformer consists of a Multi-Heaa Attention (MHA) mechanism which computes the weighted sum of value vectors across & heads:
MHA(X) Σ
(Mana(XaaXxaXX XV, Txxoo.
where Q, K, V are the query, key, and value parameter matrices of the attention mechanism and A, := K T E ddd The output of the MHA block is passed through final linear layer (parameterized by Wo) to produce the output logits over the vocabulary.
Z (Fo(S MHA(embed( r::; E, P) E T
4

---

Published as a conference paper at ICLR 2026
The full set of model parameters is 8 (E, (A,
Wo). The final predicted token, 8, is selected by finding the token with the highest logit score at the final sequence position T. We take the limit of the softmax distribution the arg max operation: 8 == arg max max
the temperature approaches zero, which is equivalent to
EEE 2T(8')
ANALYSIS OF 1 HEEDD TRANSFORMERS
3.1 1-HEAD MODELS CAN SOLVE ESP OVER DAGS
In this subsection, we prove that a 1-head transformer model can solve the selection problem over DAGs, if the dimension of the embedding space is at least the number of vertices the DAG. In fact, we establish a more general result by quantifying the least error that can be achieved by a 1-head model on arbitrary directed graphs.
Theorem 1. For any integer n and any directed graph G, which has n vertices, m edges, and an acyclic subgraph with m' edges, there exists I-head transformer model with embedding dimension n + that incurs error at most 1/2 - m' (2m) for ESP on G.
Proof. Let G be directed graph over a of vertices and m edges, and let H be an acyclic subgraph of G with m' edges. Consider the following labeling of the vertices of G: vertex denotes the ith vertex an arbitrary topologiaal ordering of H: so any edge (U,, (v,,2,) in H satisfies
j.
Our construction uses both token embedding and positional embedding. The embedding dimen- sion is d n + 1. For each token ot the token embedding is simply the unit vector with 1 in dimension i. For tokens 1 and 2, we set the embeddings to be the following vectors, respectively. (
7)² and (#
1
n 0)"
a
for parameters a and which we will set shortly. For the query token #. we set the embedding to be the vector (1
1)² The positional embedding for position 1 is (0
0 8)" and zero
for other positions, where 8 will be specified later the proof.
The attention matrix A is set to J. We now conduct the output analysis for an input of the form (n,, s, #). where s E {1,2} represents the selector. We determine the attention weights as follows:
e(#)² Ae(u:) = 5; ((t)TAe(r;) 1; e(#)²
e(#)T Ae(1) ann + 1)/2 + ar;; e(#)² Ae(2) = a<n 1)/2.
Here, e(-) simply denotes the embedding vector for each token. Following the softmax calculation, these attention weights lead to the convex coefficients for vi Uj selector s, and # as
6 1+5
(n 1)/2+a7
(a++1)/2
n+1
Wej
U2
where
0 + aln+1)/2tar + (n+1) and 02 = 6 + a(n+1)//2 + (a+1)
The final context vector can then be written as Wv, e(vx) + We e(v,) + w.e(s) + () Let ye denote the l-th component of the vector y. Then, we can expand the vector y as
(el+5 + ac ( + tett) (1 + (2)122) teat)
l and 1,
81
{ and s 2,
Be =
d2
1
(e + (n) [-++1 e-1)
f = and = 1,
(e + an 11/2 + t
l and 2, otherwise.
d
(aea(n+1)) 11/2 (n-(+1) ea+1)
0,
We set V and Wo to I (noting that dout = d); set a = 2/(n 2/
2/(n222 + +n)) to obtain e >> an++1/2 and (m+11/ > (c!tó -).
These ensure that ys: Vj
for * i, and, for the selector & = 2, we have yj > whenever i < j. Therefore, the model works correctly for all input instances (vi, uy. 2, #) whenever < j- By choosing < x+1 (In( (an(nt1) + In(e" - 1)), we satisfy c++ > + (n+ so that for any input instance (0ç. Uy, 1, #) ), we have y: Yj, ensuring that the model works correctly for this instance for all i * j. Thus, of the 2m input instances, the model incurs an error on m m' of the instances, leading an error of 1 /2 m (2m), completing the proof of the theorem.
0
5

---

Published as a conference paper at ICLR 2026
3.2 No 1-HEAD MODEL CAN SOLVE ESP OVER ANY GRAPH WITH CYCLES
In this section, we establish that no I-head 1-layer attention-only transformer model can solve the selection problem over any graph with cycles.
Lemma 1. For any vectors Da and Vt. there do not exist vectors 31, 22, Lob and Tba and non- negative reals rı, r2, Tab, and Tba satisfying the following four conditions:
(T) 32 + TabBab) (Ia - T2a) > 0, (r2202 + TabBBab) (Iaa - -Khh) <0
(T 2 + Tha (Ia xbb) < 0, (r242 + Tba (xa- Fb) >
Proof. Consider the two-dimensional plane spanned by the vectors Dn and Da; we refer to this as the x-y plane. Since the four conditions concern dot products with Pa 2b. it is sufficient consider the projections of œ1, 22, Lab, Tba on the z-y plane so that we can assume that Φ1, 22 Lob, Lba all lie on the z-y plane.
We first establish the claim for the case where Ta and Iú are orthogonal to each other, and then extend the argument the general case. If aa and xy are orthogonal to each other, then without loss of generality, let Ia and 2y be along the z- and y-axes, respectively. Furthermore, we can set z and 2, be unit vectors by scaling the x- and y-projections of other vectors without changing any of the dot products.
For any v, let Tu and ye be the projections of e on the x- and y-axes, and let A. denote Ie Ye- Then, the first condition can be rewritten as r (a) v1) + Tas(Faa - yab) > 0. Thus, all the four conditions can rewritten as:
r1 A + Aat > 0; r2 + rab < O; m1 + rba < 0: r242 + Aba > 0.
Adding the first and fourth inequalities and subtracting the second and third inequalities yields 0 >> O, a contradiction. thus follows that the four conditions cannot be simultaneously satisfied.
We now consider the case where Ia and 26 are not orthogonal. Note that each of the four conditions a requirement that the dot product of va 2g with a specific vector, which is independent of x and 2s, is either positive or negative. For any Ta and 26, we can find orthogonal vectors x', and z! satisfying x', 2 = Da Zb. This reduces the general case to that where Ia and 2; are orthogonal, thus completing the proof of the lemma.
Lemma 2. For any cycle C = (Ve, Fee, there do not exist vectors Dr 02 a set of vectors (arwe : (u,w) u) E Fee, set of vectors {ar, U Ve), and reals ri, fraw (u, E F such that for every (u, v) E Eg;
(M131 + TueTur) (I., xx) > 0 (r222 + Tuv (I xo).
Proof. The proof is by induction on the length of the cycle. For the induction base, we consider cycle of length 2 with two edges (a, and a). The non-existence of the vectors and reals satisying the desired conditions follows from Lemma 1.
For the induction step, suppose the claim holds for all cycles of length at most k where k 2 2. Consider a cycle C' of length & + 1. For the sake of contradiction, suppose there exist vectors and reals satisfying the conditions stated in Lemma 2.
Let a, b, and e be contiguous vertices on the cycle. Then, we have the following inequalities hold.
(r1 + osb (xa mz) > 0, (r202 + Fassas)) (Ia zz) < 0 (riæ1 + Tbc (xx, xx) > 0, ( Adding the first and third inequalities, and adding the second and fourth inequalities yield:
+ rbe (xx, xx) < 0.
r (Ia xe.) + Fat (It - 2b)) + The (as - x.)) > 0
T2 (I,, xx) + Tab (I,, xb) The (I) xx) < 0.
Set Foe and Fae so that Bac (IO - xx) = Tabaaa (x zb) + Tbe (xs - xa) ensuring
(riæ) + Fan (I., - xx) > 0 > (r23r2 + vao (#t, xt.).
We thus have found a solution to the set of inequalities for a cycle of length l that is obtained by replacing edges (a, b) and (b with (a, c). This contradicts the induction hypothesis.
0

---

Published as a conference paper at ICLR 2026
For any directed graph G with cycles. there is no I 1-head 1-layer attention-ont trans- former model that can solve the selection problem over G. even with unbounded dimension and unbounded precision.
Theorem 2.
Proof. Suppose there exists a 1-head model that accurately solves the selection problem over a directed graph G with cycles. Let C be arbitrary cycle in G. Then, in particular, the model accurately solves the endpoint selection problem for every directed edge in C.
Setup. Fix arbitrary directed edge (a,b) in C. Consider the following length 7 = 4: S = (41, b2, 13. #4) which must output a; S (a1, b2, 23. #a) which must output Let the pre-softmax score for a token at position p be denoted as 2sp # Ar For the two sequences. the attention weights are given by:
input sequences of
Softmax (# Ax # Aw # Aæ AA #.) Softmax(Za, 2b2 11 #
Softmax (oftma(##A.)) # A # #A #A #.) Softmax(2a, 2b2 22s 24,).
These weights determine the final output vectors, and a single-head model must learn one matrix A that works for all the 2|C' instances corresponding to the edges in C.
Preliminaries. The final context vector for each sequence, S, is the weighted sum of the input embeddings, v, w; X, The two context vectors can then be written as:
e Da.
t Dbe
E ##
11
11
+
Zi
Zi
c Bay Bay
+ th Dh2
##4 W
6 22g 272g
12 =
+
Zz
Zz
where Z, = Ejes, e for E {1,2). To simplify the above expression let us define vector, Tab. which represents the attention attention-weighred sum the non-indicator tokens:
c01 Da. + c Eb, #
Tab
e1 e + e
Using these definitions, express each of the final context vectors convex combination of the newly defined vectors and the indicator tokens.
5 + 2h #
1 (TabRaa (((11)))
U1
aab
+
31
Z1
Z1
Z1
e + ca22 + c#
e
1
U2
Lab +
32
(TabBab +22022)
Ze
Zz
Zg
Geometric interpretation. which side of the decision boundary
The selection between tokens a and depends on 2t the context vector lies.
The two resulting regions are the a-dominant half-space, H., (v/v To > v 26), and the b-dominant half-space,
H4 = (vlv Vy > v. wa). The two selection tasks for any
the context vectors v1 and U2: Un E H. and U2 E Hé. Therefore, we get the following inequality constraints for every edge (a, b) E C.
edge (a,b) impose the following constraints
74
abe
74
U1 (Ia v.)) > 0 = (rabCab + r1æ1) (xa
xb) > 0, (rabDaa r222) (xa σb)
U2 (I. xT) <0-
By Lemma 2, there not exist vectors (#. a E C),, (was
(a, b) E C). 2. and 22 and non-negative reals (Tab (a, b) E
Figure 1: 2-D decision plane.
C), r1, 12 that satisfy the above set of 2(C constraints.
Corollary 1. There is no I-head 1-layer attention-only transformer model that can solve the 2-hop induction head problem, with unbounded dimension and unbounded precision.
7

---

Published as a conference paper at ICLR 2026
Proof. Due to space constraints, we provide a brief proof sketch and defer all details, including for- mal definition of 2-hop induction head and the full proof, to Appendix A. We transform an instance of ESP to a 2-hop induction head instance follows: (a1, 83. #4) = (11, Q2. 23, 64, #s. 8 #7). In particular, note that in the 2-hop induction head instances created, the tokens positions 1, 3, and 5 always the same. Hence, any transformer circuit makes the next-token prediction based on the tokens in positions 2 and 4, position 6 (which contains token 1 or token 2) and the preceding token (which is #). This is identical to the transformer model that solving an ESP instance.
We formalize this idea, following the proof technique of Theorem 2. Consider the following two input sequences (11, 02 23. b4: #s. 1s. #7) which must output a and (11, 02, 23, b1 #t. 26. #7) which must output b. We derive the attention weights and define context vectors V1 and cor- responding to the two sequences and vector Tih the attention- attention-weighted sum over the non-indicator tokens. This enables us to express each of the final context vectors as convex combination of Tab and the indicator token vectors. (See Appendix A for the derivations.)
11= ab + T1 U2 = abb + T222,
We similarly define the vector The using the sequences. In order for the 1-head, 1-layer model to solve all 2-hop induction instances, we must have vectors Lab. Tho. 1gg and 22. that satisfy the following inequalities:
(TabDab + +1 (It 2b) 0, (TabFea + r2 (Ir 2b) < 0, (Tha + 11 (Iaa 2%,) < 0, (Tha + r22220) (æt, 2b,) > 0. By Lemma 2, such vectors do not exist, implying the desired impossibility result.
4 ANALYSIS OF 2-HEAD TRANSFORMERS
Theorem 3. For any directed graph with verfices, there exists 2-head aftention-only single-layer transformer model that can solve ESP with ((n) dimensions and ((1) precision.
Proof. We provide a constructive proof by showing the existence of a set of model parameters that can solve ESP. Let G (V, E) be a directed graph with vertex set V of size n and edge set E. Consider the input sequence S1,4 = (wi, v2, 8z #4) for an are (u, v) E E, where iž is the selector token, We set the embedding dimension d fei....,ea, C Rd. The selector token 2 embedded using only a token embedding to MM,,, where M is constant that will be set suitably large later in the proof. The token #4 is embedded as 63. Each vertex e E V appearing at position E (1, 2} is embedded as æ; = e043 + e, The resulting embeddings form the input matrix X [x [.1....,344] 24]] E 4x
+ 3, with standard basis vectors
Our model's final prediction for the correct endpoint vertex is given by
Softmax (aftmmax##4AAM) (#4A,X XV, Wo
= arg max VE
where He denotes the logit corresponding to vertex v E G. We define V1 = V22 V, set V. Wo, and calculate V VW, as follows:
V
T3xn
Osx3
Wo = In O Onxa]
R-
[0xx In
E R (*+3))x
In
Onx3
Given our construction of V and Wo. the final logit vector inside (+) above simplifies to (o) + X2)XR R. Here R fixed selection matrix that zeros out the first two dimensions while keeping the remaining n dimensions corresponding to the token embeddings for the vertices of our graph. Indeed, X RRis is [e,, e., 0, 0, Thus, the final prediction can be thought of selecting which of or receives the largest weight under a1 + 022-
We define the attention matrices: in matrix Aj. every element is 0 except for the element (3.j), which is set to 1. Hence, we obtain
#1A1 = [1 0
E
#,A, = 10 1 ... E Ixd
Here #4A, extracts the first row X (corresponding to position 1), while #4A2 extracts the second row of X (corresponding to position 2).
8

---

Published as a conference paper at ICLR 2026
Evaluating 01 a2g
Fix = 2 (the case 13 is symmetric). For the two heads, we get
#1A1X 21 1, 0, 0
# 22 [0. 1, -M, 0].
Softmax &1) =
1 c43 [e, 1, 1]. Softmax( = c+2+c [1, e, e M 1
Thus, the first and second coordinates of an + 02 are e/(e+3) e/(e + 2 - e=M)). By choosing M sufficiently large, we ensure that the second coordinate is larger than the first coordinate by a constant that can be made arbitrarily close to 1/((e + 3) 2)). Thus, the predicted token i is the letter v, ensuring that the correct endpoint vertex is selected. 0
and 1/(e 3) +
There exists 2-head, 1-layer, attention-only transformer model with constant em- bedding dimension -333 and precision O n) that solves ESP on any directed graph.
Corollary 2.
Proof. We first give a proof for unbounded precision, and then extend the argument to O(log n) precision. Instead of a token embedding that embeds vertices as basis vectors R", we embed them as well-separated unit vectors in 2 and pad with a suitable positional embedding. Number the vertices through n, and define
0₂ 2
p(u,) := [cos Og sin 0c] E R
For vertex position E 2). create its embedding by adding the positional basis vector e; E IR$ to the padded vertex encoding, i.e.,
x, = e, + (10, 0, (()( E R.
Next, we update the value and output projection matrices V and Wo and calculate R VWJ
= O3x2 I2
O3x3
TO 3xn
Wo = [ [ Onx3]
R= VW T
E 5x5
O2x3
where E E nx2x2 is the token embedding matrix for all the vertices of the graph. We obtain that X R the 4 n matrix whose first row is the vector with kth coordinate being @(k) o(u), second row is the vector with kth coordinate being <(k) )(v) and remaining vectors being zero. (Here, for any vertex k. ((k) is being viewed as two-dimensional vector.) Note that d(k) <(u) =
(0,) + sin (0..) = for k = u and is strictly less than for l * u. By the same argument as in the proof of Theorem 3, the coordinate of a1 +02 that is maximized is the selector 1.. Consequently, the n-dimenniioal vector (a1 + ax) X R has its maximum value the coordinate corresponding to the vertex that appears in position ig., yielding the desired result, assuming unbounded precision.
To obtain the result with O(log ni) precision, we observe that when k + u, d(k) ((u) equals cos(0%) cos(8.)+ sin(Os) sin().). which equals cos(E, f.). which is at most cos (os(2r//) By Taylor expansion, we have cos(2./n) = Q(1/n2). Therefore, it is sufficient to approximate cos(0z) and sin(O,) to additive bound of O(L/n²). Thus, we can replace cos(O,) and (0,) by the nearest multiple of a rational number 1 1/r, where is an integer, which is O(n²), This ensures that the coordinates with the largest value in the first two row vectors of X R continue be those corresponding to and v respectively, leading to the desired prediction. Since all weights in the embeddings and the attention matrix are multiples of O(log n), the result follows.
EXPERIMENTS
We validate our theoretical results and probe the expressivity of attention heads for ESP.
Experimental setup. We use a decoder-only transformer with causal self-attention and no feedfor- ward layers. Weights are tied between input embeddings and the output projection, and we retain residual connections and layer normalizations, We train with Adam and place no restrictions on embedding dimension or other sypee-parameten, (training iterations, learning rate, batch size, etc.). All experiments were run on A100 and L4 GPUs via Google Colab.
Datasets and metrics. We generate transitive tournaments (the largest DAG for given number of vertices) by labeling nodes 1 through [V| and including all ares (u, v) with u < v. To study cycles, we generate graphs with varying minimum feedback are set (MFAS) sizes (see figures in

---

Published as a conference paper at ICLR 2026
Appendix C.I). We define the accuracy the fraction of conrectly predicted ares all training sequences extracted from the graph.
1-head models sufficient for DAGs, insufficient for cycles; 2-head models solve all graphs. Consistent with Theorem 1, a single-head model solves ESP on DAGs. On graphs with cycles, approaches the global minimum only for simple cases with |MFAS| 1, i.e., achieving 100% accu- racy on the maximum acyclic subgraph (MAS) and 50% on the remaining (MFAS) ares, essentially guessing heads/tails. Performance degrades for more complex graphs with [MFASS] pendix C. for more details.) Adding a second head enables ESP to be solved on arbitrary directed graphs, consistent with Theorem 3 (see Figure 2(B))
(See Ap-
-Q- L-beed mocel [ESP over Transties Tesmunant) -O- 2-bced moedl (ESP ovat Translis Teamenent)
h-ba (ESP ove Complets Diaruph)
H-eac (ESP ove Complite Digraph)
Embeakiing Dimunaion
32
10
Embesding
8
20
6
400%
2007
2001
4.8
57
128
4.8
16
64
128
Number Graph
Graph Nodes
(A) Transitive tournament
(B) Complete digraph (bi-directed)
Figure 2: Accuracy plots for the best-performing models across different configurations.
Analysis of embedding dimension. We empirically study how the minimum dimension needed to solve ESP varies with graph size. In Figure 2(A), we observe that for DAGs, gradient-basee optimization can find accurate dimeeaot 2-head models and nearly-accurate 1-head mod- els with sublinear dimension (suggesting that the linear upper bound established in Theorem 1 can be improved). In Figure 2(B), we observe that for general graphs, gradient-based optimization finds accurate 2-head models with dimension that appears to grow logarithmically in the graph size, in contrast to the constant upper bound established in Corollary 2. Furthermore, 1-head models struggle on complete digraphs, and the gradient-based optimizer fails to find the best 1-head so- lution from Theorem Since a complete digraph on n vertices has m = (n - 1) edges and a transitive orientation yields an acyclic subgraph with m' (b) n(n 1)/2. the bound gives error n(n-1)/2 2x(n-1) 4. i.e., accuracy 2 3/4 = 75%. In practice, even with d > our I-head models fail get close the 75% accuracy level on complete digraphs. Figure reveals a clear separation: two narrow heads offer representational power that widening single head cannot match. Additional experimental results, which analyze how bounded-wiee FFN components affect the accuracy of I-head models for ESP, are provided in Appendix C.2.
6 LIMITATIONS, DISCUSSION AND CONCLUDING REMARKS
Our analysis focuses on a highly simplified setting: attention-only transformers with either one or two heads. While this abstraction allows to isolate fundamental representational limits, it does not account for components such as feedforward layers, residual connections, or training dynamics. Despite simplifications, our results highlight structural bottlenecks in attention itself, independent of embedding size numerical precision. The observed gap between a single-head and two-head mod- els suggests the emergence of a natural hierarchy in transformer capabilities, providing a framework for analyzing model design choices beyond empirical scaling.
In sum, our theoretical and experimental findings suggest that attention heads act as discrete units of computational power, with each additional head expanding the class of solvable problems opening the door to a principled taxonomy of transformer architectures characterizing the boundaries of deeper multi-head configurations. More broadly, approach demonstrates how simple formal tasks like ESP can serve as testbeds for probing the fundamental limits of large-scale sequence models.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
REPRODUCIBILITY STATEMENT
This paper contains both theoretical results and experimental analyses. The main body of the paper and the appendix together contain all the assumptions and complete proofs of all claims. We have submitted the source code for all of our experimental analyses supplementary material.
REFERENCES
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the repre- sentational capabilities of transformers and recurrent architectures. In NewrIPS, 2024.
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Hervé Jégou, and Léon Bottou. Birth transformer: memory viewpoint. In NeurlPS, 2023.
Yang Cao, Yubin Chen, Zhao Song, and Jiahao Zhang. Towards high-order mean flow generative models: feasibility, expressivity, and provably efficient criteria. arXiv:2508.07100 2025.
Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Jiahao Zhang. Circuit complexity bounds for RoPE-based transformer architecture. In EMNLP, 2025.
Lijie Chen, Binghui Peng, and Hongxun Wu. Thcoretical limitations of multi-layer transformer. arXiv:2412.02975, 2024.
David Chiang. Transformers in uniform TCº. TMLR, 2025.
Nelson Elhage. Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical frame- work for transformer cireuits. Transformer Circuits Thread, 2021. URL https:// transformer-cio www.eeererrrrruttteeeeeee wtw.irruuts.uub/////ee pubpppp//// fwamework/ inniex.ettt..
Michael R. Garey and David S. Johnson. Computers and intractability: guide to the theory of NP-completeness. W. H. Freeman, 1979.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. TACL, 2020.
Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. N.XW:11003.0531,, 2015.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 1989.
Jerry Yao-Chiel Hu, Hude Liu, Hong- Yu Chen, Weimin Wu, and Han Liu. Universal approximation with softmax attention. arXiv:2504. 15956, 2025.
Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology, Department Numerical Analysis and Computing Science, Stockholm, Sweden, 1992.
Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Com- putations, 1972.
Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian B. Calderon, and Cristóbal Rojas. Strassen attention: unlocking compositional abilities in transformers based on new lower bound method. arXiv:2501.19215. 2025.

---

Published as a conference paper at ICLR 2026
Liyua Liu, Jialu Liu, and Jiawei Han. Multi-head single-head? empirical comparison for transformer training. arXiv:2106.096500 2021.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: limitations of log- log-precision trans- formers. TACL, 2023.
William Merrill and Ashish Sabharwal. little depth goes a long way: the expressive power of log-depth transformers. In NeurIPS, 2024a.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In ICLR, 2024b.
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. TACL. 2022.
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? NeurIPS, 2019.
Eshaan Nichani, Alex Damian, and Jason D. Lee. How transformers learn causal structure with gradient descent. In ICML, 2024.
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. Transformer Circuits Thread, 2022. URL https /ttee:///raaaaeaeeeeee htt///aanfoorreeeeeeceeeee ci ciritts.. pub/2022/ htnp://nnconttttteee -earninggennn -wneiinng-nn-----eee and-annddndne inductiionnn wwweeiiinooohoeeeeeeeeeeeeeeeeee wiwex.inxxx////// html.
Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. In COLM, 2024.
Clayton Sanford, Daniel J. Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In NeurlPS, 2023.
Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiiv2405.15222 2024a.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induc- tion heads task. arXiv:2408. 74332, 2024b.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and loga- rithmic depth. In ICML, 2024c.
Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold circuits. arXiv:2308.03212, 2023.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? survey. TACL, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, 2017.
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: specialized heads do the heavy lifting, the rest can be pruned. In ACL, 2019.
Siwei Wang, Yifei Shen, Shi Feng, Haoran Sun, Shang- Teng, and Wei Chen. ALPINE: unveil- ing the planning capability of autoregressive learning in language models. In NewrIPS. 2024a.
Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason Lee. Transformers provably learn sparse token selection while fully-connected nets cannot. In ICML, 2024b.
Zixuan Wang. Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D. Lee, and Denny Wu. Learning compositional functions with transformers from easy-to-hard data. 2w8iv:2505.23683 2025.
12

---

Published as a conference paper at ICLR 2026
A ESP AS A SPECIAL CASE OF 2-HOP INDUCTION HEADS
Induction Heads. Induction heads are a well-studied circuit-level phenomenon in transformer
models (Elhage et al., 2021; Olsson al., 2022), implemented by pair of attention heads. They perform the following simple find-and-copy algorithm: given an input sequence S
($1..... St, S1+1.....
1. find the last position j < T where 8) 8T,
2. predict the subsequent token 8j+1.
For example, given the input sequence (a...., a, b.....a), a). the induction heads work together to pre- dict b, since b follows the previous occurrence of a. This framework generalizes out-of-distribution since it executes an input-agnostic algorithm rather than memorizing fixed patterns.
Two-Hop Induction. The two-hop induction problem, first noted in Sanford et al. (2024c), ex- tends this mechanism by chaining together two of the above find-and-copy operations. For example, given the sequence
(a.... b, C, ....., ..).
a),,
the correct prediction is since the model must first retrieve the following aj. and then output the token that followed the earlier occurrence of b, namely c. Thus, two-hop induction composes two one-hop induction steps, demonstrating how induction heads can be leveraged for more complex reasoning.
Relation to ESP. We show that the Endpoint Selection Problem (ESP) is special case of 2-hop induction head problem and present a full proof of Corollary 1. Recall that in ESP, the input sequence is of the form
a bi #
where a, b are endpoints of an arc, and i E {1,2} is an indicator token. The target outputs are as follows:
b # - a, a bb # - b, b
This input can pre-processed into form equivalent to 2-hop induction instance. Specifically, we can pad each sequence as
a 1
1a2b#2#
1b2a # #
In this representation, fixing the query token converts the task from a I-hop to 2-hop problem by "exhausting" single hop. In particular, note that in the 2-hop induction head instances created, the tokens in positions 1, 3, and 5 are always the same. Hence, any transformer circuit makes the next- token prediction based on the tokens in positions 2 and 4 (each either b), position (either 1 or 2) and the preceding token (which is #). This is identical to the transformer model that is solving an ESP instance. Therefore, one design transformer circuit for ESP by simply emulating one for 2-hop induction head. This implies that our impossibility result from Theorem also extends to the 2-hop induction head problem.
We formalize the above argument, following the proof technique of Theorem 2. Con- sider the following two input sequences (11, d2, 23, 64, #o, 1e, #7) which must output and (11, a2, 23, ba, #3 26, #7) which must output b. As before, let the pre-softmax score for token at position p be denoted as Zs, = #,Ax,, For the two sequences, the attention weights are given by:
(oftmax(#7Aa))) #7 Ax #7 Ax #7 AvT, #7 Ar # #7 Av # A #1)
Softmax(21, Zags 22 Rbs 74 2l 7
Softmax (1nmax(#AAa0)) Aa, #7 Ax #7 Ax #7 AxT # Ax #7 Ax #7 Am
Soottmxx (21, Rag 22g Abg 34 22 ##7)
13

---

Published as a conference paper at ICLR 2026
The final context vector for each sequence, S,, is the weighted sum of the input embeddings, 2z Wi X, The two context vectors can then be written as:
t 101 01, + e Daz + 2 + e Tbg + E a Ho s e=#r
c la
+
Z
Zi
02 e + 1002 + 22 + e Ib, + e #4 + #
t 26
Z2
Zz
where Z: = Ejes, e for i [1,2}. We next define ab. the attention- sum over the non-indicator tokens:
Tob e 11 + e Dag t 22, + Ib, + # e #
e + t02 22 + E + # + E
Using these definitions, we can express each of the final context vectors convex combination of the newly defined vectors and the indicator tokens.
3 502 + 22 t E E
E
01
Bab
31g = Tabaaah 1
Z1
71
e + e + c + ca + e + t
e²2o
U2
Lab +
U2 = Tabaoab 22
Z2
Z2
We similarly define the vector Tha using the sequences (11, b2, 23, a4 #5. 1s, #7), which must out- put and (11, b2, 23, a4, #s. 26, #7), which must output a. As we argue at the end of the proof of Theorem 2, Lemma 2 implies that there do not exist vectors Lad, æba, Vig. and 22. satisfying the four inequalities:
(TabDob + 11
(xa 1bb >
(TabRab + 22
(Ex 2b) < 0,
(Tha + r(
(#a (b) <
(Tba - T2 (xt - x3.) > 0.
This establishes that there is no 1-head, 1-layer attention-only transformer model for 2-hop induc- tion head, even with unbounded dimension and unbounded precision.
B NP-COMPLETENESS
We demonstrate the intractability of even approximating the minimum error of 1-head model for ESP on general directed graphs.
But first we state corollary that follows directly from the theorems in Section 3. We remind the reader that MAS stands for Maximum Acyclic Subgraph, MFAS for Minimum Feedback Are Set and for any directed graph with m ares, |MAS] + MMFS| = m.
Corollary 3. For any integer n. and any directed graph G, which has n vertices, m edges, and an acyelic subgraph with |MAS] edges, there exists a 1-head transformer model with embedding dimension + 1 that incurs an error exactly equal to 1/2 - |MAS\/ (2m) for ESP on G.
Theorem 4. Finding a I-head minimum error model for ESP is NP-complete.
Proof. For the sake of formalization, let us define IH-ESP to be the decision problem: given directed graph G and error accept if and only if there is 1-head model which achieves error at most on G. As always, n and m stand for the number of vertices and ares, respectively, G. The reduction from known NP-hard problem MAS (Maximum Acyclic Subgraph) Karp (1972); Garey & Johnson (1979), with the following definition as a decision problem: given a directed graph G and number m', accept if and only if there is DAG with at least m' ares that is subgraph of G. We prove NP-completeness of iH-ESP by first showing that is in NP and then showing that it is NP-hard by reduction from MAS.
14

---

Published as a conference paper at ICLR 2026
To that IH-ESP is in NP, guess any DAG contained in G with least m' ares and then follow the construction in the proof of Theorem to obtain a certificate (NP-witness) that the error is 1/2 m (2m).
Next, to see NP-hardness 1H-ESP here is the straightforward reduction. Given an instance (G, m²) of MAS transform it into instance (G, 1/2 m' mm/((2m)). By Corollary 3 we know that m' is the size the largest DAG if and only if the minimum error achievable is 1/2 m (2m), and hence it follows that the MAS instance is accepted if and only if the IH-ESP instance which it is reduced is accepted.
We now strengthen the NP-completeness to an APX-hardness.
Theorem 5. The minimum error of the best 1-head model for ESP cannot be approximated factor better than 1.3606.
Proof. The proof follows in straightforward fashion from the APX- -arddesssss of MFAS, the Mini- mum Feedback Are Set problem (Kann, 1992). which is known not to be approximable to factor better than 1.3606, unless = NP. Observe that the error in Corollary 3, 1/2 (MAS)/(2)) the same MMFAS/(2m) and thus the inapproximability factor carries exactly.
Corollary 4. Grudient descent cannot compute (even upproximate) the global minimum (to better than a factor of 1.3606) of ESP for 1-head models in polynomial time, unless NP.
C ADDITIONAL DETAILS FOR EXPERIMENTS WITH DIRECTED GRAPHS
C.1 GRAPH VISUALIZATIONS FOR ESP EXPERIMENTS
Figure 3 presents family of directed graphs (with cycles) over which we analyze the 1-head and 2-head transformer models. Empirically, the best accuracies were obtained after more than 50 runs with hyperparameter tuning for Figure 3(B) and Figure 3(C), and after more than 30 runs for Figure 3(A) and Figure 3(D), within 10k-20t training iterations each.
(A) 8-node cycle (15/16)
(B) Graph with [MFAS] = (32/34)
(C) Graph with [MFAS] = 2 (50/56)
Accurocy 50%
MIPAS (righlighe)
(D) Complete digraph (81/112)
Figure 3: Prediction accuracies for the best pest-performing 1-head model for different graphs. Note that (D) only shows edges adjacent to vertex 1, and MFAS highlight only applies to (A), (B), and (C).
15

---

Published as a conference paper at ICLR 2026
C.2 BOUNDED- WIDTH FFN EXPERIMENTS FOR ESP
To further investigate how bounded-widttl feed-forward (FFN) components affect the representa- tional limits of shallow transformer models, conducted additional experiment measuring the smallest model size required to solve ESP over complete directed graphs of varying sizes. For each graph size, we identify the minimum- parameeerr configuration of (i) 2-head attention-only transformer and (ii) a I-head transformer augmented with a bounded-width FFN that achieves near- perfect accuracy.
In this experiment, the parameter count refers to the total number of trainable parameters used by each respective model, including all attention matrices and (when present) the parameters in the FFN block.
Figure summarizes the results. The key takeaway is that 1-head transformer equipped with bounded-width FFN can match the expressivity of 2-head attention-only transformer when using a comparable number total parameters.
Smallest ESP Solvers over Complete Digraph
2-hwaed Attention-Only
2,500
I-head MLP
Total Number of Parameters
1,500
1,000
700%
400
300
500%
200
1.0
44%
32
Number Graph Nodes [G]
Figure Number of parameters of the smallest models that solve ESP over complete digraphs.
16

---

Published as a conference paper at ICLR 2026
D LLM USAGE
We used LLMs to help identify related work, transcribe handwritten equations into 18TxX, and polish writing and grammar.
17


Reviews:
[{"review_id": "jlNvfaMyNU", "reviewer": "Reviewer_WJsn", "summary": "The authors provide a theoretical analysis of single-layer attention-only transformers and their ability to solve a simple problem called the Endpoint Selection Problem (ESP). This problem is interesting and motivated by the fact that it is foundational in many reasoning tasks. They show that single-layer transformers with a single attention head are not able to solve this problem in its general form even with unbounded model dimension. On the other hand, the authors show that the same model with two attention heads can easily solve the problem with limited model dimension and precision. They provide experimental results that further corroborate their theoretical findings.", "questions": "In the ESP task, all of the information needed to solve the problem is given in the model's input: the ordered pair representing the edge as well as the selector. Then why is the model's ability to solve this task dependent on the distribution of edges/graph structure? Is it not possible to write/learn a distribution-agnostic circuit to solve ESP in one layer? For example, if the query token were excluded from the input (i.e., the input only consists of the vertex pair and the indicator), it would be straightforward to construct a single attention-head transformer to solve the task in a distribution-agnostic fashion: Set the token embedding for vertex v_i to be the unit vector with 1 in dimension i; the token embedding for 1 and 2 are unit vectors with 1 in dimensions n and n+1, respectively; the position embedding for position i is a unit vector with 1 in dimension n+2+i, and so the embedding dimension is n+5. The attention matrix A is set as follows: A[n+0,n+2+0]=C, A[n+1,n+2+1]=C, for some positive constant C and zeros elsewhere. The last token (the selector) would simply copy from the token at position 0 or 1 depending on the value of the selector. Given such a construction exists, why is it worthwhile to consider the case where the last token must be a query token?\n\nWhile the work focuses on attention-only transformers, since arbitrarily wide FF layers are universal approximators, it would still be interesting to explore how the analysis would change if we allow for bounded width FF layers. Would the ESP problem become much easier to solve? Similarly, would an attention-only transformer with one attention head and two layers be able to solve the ESP problem on cyclic graphs?\n\nThe font size in Figure 1 is rather small which makes it somewhat difficult to read (especially the expression in grey).\n\nFigure 2: The font size for the percentages is a bit too small.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written overall and the proofs are well-structured and easy to follow.\n - The authors show that even with unbounded model dimension, single-head attention-only transformers are not able to learn the ESP task for cyclic graphs (but they are able to easily do so for DAGs).\n - The authors also show that the same model with two attention heads is able to learn the ESP task on cyclic graphs with limited model dimension and precision.\n - Experiments are conducted to corroborate their theoretical observations.", "weaknesses": "- The scope and implications of the contributions are not immediately obvious (or they seem to be somewhat limited). Perhaps some discussion about how the findings would generalize to non-attention-only transformers or transformers with more than one layer would help.\n - It is unclear why it is not possible to write a construction that is agnostic to the distribution of the graphs (see below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hvq87IZusQ", "reviewer": "Reviewer_UJCu", "summary": "This paper investigates the representational limits of attention-only transformers through the Endpoint Selection Problem (ESP), where models must select endpoints of directed graph arcs based on an indicator token. The authors establish dimension- and precision-independent impossibility results: no 1-head, 1-layer attention-only transformer can solve ESP on graphs with cycles, while 2-head models can solve ESP on arbitrary graphs with $\\mathcal{O}(n)$ dimension and $\\mathcal{O}(1)$ precision, or $\\mathcal{O}(1)$ dimension and $\\mathcal{O}(\\log n)$ precision. For directed acyclic graphs (DAGs), 1-head models suffice with $\\mathcal{O}(n)$ dimension. The paper proves it is $\\mathsf{NP}$-complete to approximate the minimum error achievable by 1-head models and validates findings experimentally, demonstrating that gradient descent reliably finds 1-head solutions for DAGs and 2-head solutions for cyclic graphs.", "questions": "1. Does the 1-head impossibility result (Theorem 2) extend to transformers with feed-forward layers?\n2. Can your geometric proof framework establish similar hierarchies for other architectural dimensions beyond head count?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Strong theoretical contributions with unconditional lower bounds**. The paper's main result (Theorem 2) establishes impossibility for 1-head models on graphs with cycles without any restrictions on embedding dimension or precision, which is a significant advance over prior conditional lower bounds by Peng et al. (2024) and Sanford et al. (2024c) that required bounded dimension and precision. The geometric proof technique using Lemmas 1 and 2 is elegant and provides clear intuition through the half-space analysis shown in Figure 1. The matching upper bounds (Theorems 1 and 3) with constructive proofs and the computational hardness result (Theorem 5) create a complete characterization of the problem.\n\n2. **Clean problem formulation with practical relevance**. ESP provides a well-motivated testbed that connects to the important induction head phenomenon studied in transformer interpretability (Appendix A demonstrates ESP as a special case of 2-hop induction heads). The problem is simple enough to admit rigorous analysis yet expressive enough to capture fundamental graph traversal and selection primitives underlying many reasoning tasks. The experimental validation on transitive tournaments and complete digraphs (Figure 2) demonstrates practical implications of the theoretical results.\n\n3. **Comprehensive complexity-theoretic analysis**. Beyond expressivity results, the paper proves that finding optimal 1-head solutions is computationally intractable. Theorem 4 shows NP-completeness of finding minimum-error models, while Theorem 5 strengthens this to APX-hardness with an inapproximability factor of 1.3606 (lines 695-721). This is achieved through reduction from the Maximum Acyclic Subgraph problem, and Corollary 3 directly implies \"gradient descent cannot compute (even approximate) the global minimum...in polynomial time, unless P = NP.\" These results provide crucial theoretical justification for why the optimization gaps observed in experiments (Section 5) may be fundamental rather than artifacts of training procedures.", "weaknesses": "1. **Limited scope due to attention-only restriction**. The paper focuses exclusively on attention-only transformers without feed-forward networks (FFN), as acknowledged in lines 065-067: \"Since FFN with a single layer is already a universal approximator (Hornik et al., 1989), in this paper we focus on attention-only transformers.\" While this isolation enables clean theoretical analysis, it significantly limits practical relevance since real transformers crucially rely on FFN layers.\n\n2. **Incomplete coverage of related work on transformer depth and circuit complexity**. The related work section (lines 136-150) discusses some depth-related results, mentioning that \"transformers with constant depth, context length n, and precision O(log n) can be simulated by uniform constant-depth threshold circuits\" (Merrill & Sabharwal, 2023) and that \"log-depth transformers can solve graph connectivity\" (Merrill & Sabharwal, 2024a), but omits several highly relevant recent works establishing fundamental complexity bounds for transformer architectures. Chen et al. (2024) [1] analyze circuit complexity bounds for RoPE-based transformer architectures, Cao et al. (2025) [2] show the circuit complexity bounds for vision transformers and their application, and Chiang (2025) [3] proves transformers operate in uniform $\\mathsf{TC}^0$. These works are particularly relevant because RoPE is the dominant positional encoding in modern LLMs while this paper uses basic additive positional embeddings, and the circuit complexity perspective provides complementary lower bounds that could strengthen the impossibility results. \n\n### References\n\n[1] Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Jiahao Zhang. “Circuit Complexity Bounds for RoPE-based Transformer Architecture”. EMNLP 2025.\n\n[2] Yang Cao, Yubin Chen, Zhao Song, Jiahao Zhang. “Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria”. arXiv:2508.07102. \n\n[3] David Chiang. “Transformers in Uniform TC0”. TMLR 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FNKXhW9E3l", "reviewer": "Reviewer_LMjh", "summary": "In this article, the authors present new results about the expressivity of transformers.\n\nThe main contributions are:\n\n- the introduction of a problem as testbed: the Endpoint Selection Problem (ESP) to study the expressive power of Transformers\n\n- using this problem, the authors show a separation between one-head and two-heads transformers,  in the sense that (i) some instances of this problem cannot be solved exactly, for any one-head transformer, (ii) for any instance of this problem, there is a two-head transformer that solves it with zero error.\n\n- an NP-complete result for the approximation of the best single-head model to minimize error on the arcs of graph.\n\n- illustration of their results via experiments", "questions": "- In the Appendix A., the example given for Induction Heads, do the authors mean: (a,a,a, .., a, b, a, ..., a), where b is in i-th position? Similar question for the Two-Hop induction.\n\n- Could the authors elaborate on their choice of the ESP for the separation, in particular what lead them to consider this problem?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- At a high-level, the results are appealing and interesting for the science of transformers, which is a fundamental part of all the recent progress in AI.\n\n- Technically speaking the results hold for any dimension of the one-head, and there are quantitative bounds for the two-head, which gives a clean separation.\n\n- The authors give a good overview of the existing results in the literature of the expressivity of transformers.", "weaknesses": "- The authors do not elaborate and give convincing arguments on why ESP is interesting to study in the first place (except some mention of reductions in the beginning of page 4, but then it is unclear why focus not on the other reductions). Since the authors are introducing a first in-depth study via the ESP, this is an important part missing to the article in my opinion.\n\n- Related to the previous point, despite the clean seperation result, the nature of the result and significance feels limited. (to the authors: please feel free to clarify during rebuttal).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Ws5GK0oE1", "reviewer": "Reviewer_kCWe", "summary": "The authors analyze a simplified transformer model (1-layer, 1- or 2-head, attention-only) on the endpoint selection problem (ESP). Given a graph, ESP is a distribution of problem instances over the edges in the graph. Given a uniformly sampled edge $(u, v)$, the task is to select either $u$ or $v$, based on whether the next token is $1$ (select $u$) or $2$ (select $v$). The authors show that a 1-head, 1-layer, attention-only transformer can solve ESP in $n$-node DAGs with embedding dimension $n$ (Theorem 1 is slightly more general, applying to directed graphs with large enough acyclic subgraphs, with accuracy degrading as the subgraph shrinks). In contrast, the authors show that 1-head, 1-layer attention-only transformers cannot (exactly) solve ESP in cyclic graphs, and finding the best-approximating transformer is NP-complete. Additionally, they show 2-head models can solve ESP for any directed graph. Experimental results support the theory, but indicate bound are loose.", "questions": "### Suggestions/comments\n- In 1.1, the definition of ESP is confusing, as the first sentence of 1.1 says it's a problem in a graph and the second sentence has no graph in the input to the problem. Only after carefully thinking about the third sentence (where the graph affects the distribution of instances generated) does the problem begin to make sense. Clarifying sooner that ESP in a graph is not one input-out pair but a distribution over input-output pairs would help.\n- [1] should be cited and its Index result discussed wrt ESP (see question 2). \n- in the transformer model definition, all terms should be named in the text ($E$, $P$, $X$, $Q$, $K$, $V$), even if they are standard.\n- the style of plot in figure 2 (with accuracy shown as labels only and a hyperparameter on the y axis) is a bit odd, as it doesn't show the accuracy of models with other embedding dimensions. (e.g., how do we know there isn't a smaller one-head model with accuracy 100%, from that plot?) I'm not sure how to fix this best... maybe, for size $n$, also show the accuracy of the next-smaller model, so we see that shrinking it worsens performance?\n- Theorem 5 is only mentioned in the introduction; discussing it in the results section as well would be better. And theorem 4 is never mentioned! This is a nice result to complement theorem 2, which otherwise might feel overly restrictive with its exact solution requirement.\n - Great title. But I would suggest adding something about edge endpoint selection.\n - The related work does a reasonable job overall, but there are some other papers that could have been mentioned [3-9]. See [2] for a nice survey. Of course, no one paper needs a totally exhaustive related work (unless it's a survey), but these might be useful places for the authors to look--and at least pointing to the survey would be useful for readers. (And I was surprised to see no cited papers by several important people in this area, like Strobl, Hahn, Chiang, and Bhattamishra.) For a different perspective on several relevant problems like Index and graph reachability, see also [10].\n\n\n### Questions \n1. The connection between 2-hop induction heads feels quite tenuous, and it's not clear to me that we can say ESP reduces to 2-hop induction heads. This \"reduction\" requires transforming the input, so it's not clear that it's valid to say that \"a circuit capable of two-hop induction can directly solve ESP,\" (p. 13) as that circuit is not capable of performing the input transformation. If we allow arbitrary input transformations, then we could \"reduce\" any problem to another by placing the answer at the end of the new input. In Turing machine polynomial-time reductions, this style of issue is addressed by ensuring the TM itself can perform the input transformation in polynomial time. But here, it's not clear how to make the transformer do the input transformation to then apply the 2-hop induction heads circuit. How can we make this notion of reduction well-defined?\n2. Instead of drawing a parallel between an ESP instance and 2-hop induction heads, the much more natural analogy is to the Index problem: given an input and an index, retrieve the item at the index. This is exactly what ESP is. But [1], Theorem 1 shows that there is a 1-layer transformer with log width and precision that solves Index, and as far as I can tell their construction has only a single head, which seems to contradict the authors' Theorem 2. Their log-width also seems better than the O(n) embedding dimension of Theorem 1. What explains the differences in the results? Ah, I think it's that the results here are for attention-only transformers, whereas [1] uses a (small) feed-forward network. Does their construction become impossible with just a linear layer + softmax instead of the FFN? My intuition is that index still feels possible by attending to the position embedding.... (then again, the logic of theorem 2 makes sense, but it's worth identifying exactly what about their construction fails to translate)\n3. Defining ESP as including the query token seems unnecessary; why not just say the input is $(u, v, i)$?\n4. Given that the results of [1] on Index are for a more realistic transformer model than attention-only, why are the results here for attention-only transformers on a restricted Index problem still valuable? (I don't claim they are not, but this needs to be justified)\n\n\n### References\n[1] Bhattamishra, S., Hahn, M., Blunsom, P., & Kanade, V. (2024). Separations in the representational capabilities of transformers and recurrent architectures. Advances in Neural Information Processing Systems, 37, 36002-36045.\n\n[2] Strobl, L., Merrill, W., Weiss, G., Chiang, D., & Angluin, D. (2024). What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12, 543-561.\n\n[3] Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8, 156-171.\n\n[4] Hahn, M., & Rofin, M. (2024, August). Why are Sensitive Functions Hard for Transformers?. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (pp. 14973-15008).\n\n[5] Chiang, D. (2024). Transformers in uniform TC $^ 0$. arXiv preprint arXiv:2409.13629.\n\n[6] Strobl, L. (2023). Average-hard attention transformers are constant-depth uniform threshold circuits. arXiv preprint arXiv:2308.03212.\n\n[7] Bhattamishra, S., Ahuja, K., & Goyal, N. (2020, November). On the Ability and Limitations of Transformers to Recognize Formal Languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) (pp. 7096-7116).\n\n[8] Chiang, D., & Cholak, P. (2022, May). Overcoming a Theoretical Limitation of Self-Attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (pp. 7654-7664).\n\n[9] Strobl, L., Angluin, D., Chiang, D., Rawski, J., & Sabharwal, A. (2025). Transformers as transducers. Transactions of the Association for Computational Linguistics, 13, 200-219.\n\n[10] Schnabel, T., Tomlinson, K., Swaminathan, A., & Neville, J. (2025). Lost in transmission: When and why LLMs fail to reason globally. arXiv preprint arXiv:2505.08140.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Well-written paper overall and fairly clear, modulo some minor issues noted below\n2. Nice combination of theoretical results and experiments.\n3. Topic (analysis of transformers) is important and relevant. Significance is mixed; narrow problem and model, but the area is still under-explored, which I think overrules the narrowness\n4. Overall quality is high, what I checked of the proofs seems sound", "weaknesses": "1. The connection to induction heads felt shoe-horned in; the connection to index is much clearer, which highlights a critical piece of missing related work [1], whose results need to be discussed, as they at first seem to contradict the results here (see question 2)\n2. Given the results of [1] on Index for 1-layer transformers with FFN, the importance of this analysis of 1-layer attention-only transformers needs to be justified\n\n\n### Overall evalution\nI actually think this is a nice paper, but the relationship to [1] really needs to be addressed before publication, hence my initial low score. I am open to recommending acceptance if the authors can address these concerns in rebuttal/discussion and amend the paper accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)