Putting Transformer Theories to the Test

Awni Altabaa; Tobias Schnabel; Kiran Tomlinson

cs.LGOct 23, 2026

Putting Transformer Theories to the Test

Authors: Awni Altabaa, Tobias Schnabel, Kiran Tomlinson

Organizations: Yale University · Microsoft Research

Abstract

Several formal theories have been developed to characterize the capabilities and limitations of the transformer architecture, each employing different abstractions that capture different features of the architecture. Due to the differences in their underlying assumptions and conceptual frameworks, these theories can disagree in their predictions about what tasks transformers find easy or hard. We map out seven theories of transformer capability (Star-free, $\mathsf{AC}^0$ , $\mathsf{TC}^0$ , C-RASP, MPC, BAPO, and Sensitivity) and translate their results into a common matrix of predictions across a suite of tasks covering different computational structures. We provide new theoretical results to complete this matrix. We then evaluate theoretical predictions through controlled experiments measuring in-distribution sample complexity, length generalization, and pretrained language model performance. We find that no single theory explains the observed pattern of successes and failures. When a theory does not capture the transformer behaviors relevant to a task, its predictions break down; for instance, we show that the $k$ -hop induction task is predicted hard by C-RASP because it does not model content-dependent attention, but we train small transformers on this task that length-generalize. Similarly, theories assuming hard attention like $\mathsf{AC}^0$ and BAPO predict binary majority to be hard, for which we also find success in practice. Together, our results point to several specific features that a theory of transformers must capture: soft rather than hard attention, dynamic content-dependent retrieval, bounded computation at each position, an account of learnability and inductive biases, and a combination of upper and lower bounds.

Figures & tables

Panel of Figure 1 — Figure 1: Relationships between theories. Each region represents the tasks that a theory predicts are easy. Each dot is a task, drawn inside the regions of theories that predict it is easy and outside the regions of theories that predict it is hard. A filled dot means all of these placements are proved, while a hollow dot means at least one depends on a conjecture (e.g., $\textsf{TC}^{0}\neq\textsf{NC}^{1}$ ). Sensitivity is not plotted here because it is a theory of learnability rather than expressivity.

	Star-free	$\textsf{AC}^{0}$	$\textsf{TC}^{0}$	C-RASP	MPC	BAPO	Sensitivity
Key Assumptions
Token primitives	a symbols	01 bits	01 bits	a symbols	a symbols	a symbols	01 bits
Information flow	causal	bidirect.	bidirect.	causal	bidirect.	causal	bidirect.
Attention type	hard	hard	softmax	uniform	msg. passing	hard	softmax
Local computation	bounded	bounded	bounded	bounded	unbounded	unbounded	bounded
Formal relation to transformers	$=T^{\mbox{\hskip 0.7pt\hbox to5.29pt{\vbox to1.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.306pt\lower 1.13397pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces\lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap=round} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin=round} \lx@inpgf@ignorespaces{{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.48 1.99 L 0 1.99 L 2.29 3.89}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}_{\mathrm{hard}}$	$\supset T^{\mbox{\hskip 0.7pt\hbox to5.29pt{\vbox to4.79pt{\pgfpicture\makeatletter\hbox{\hskip 0.306pt\lower-0.81pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces\lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap=round} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin=round} \lx@inpgf@ignorespaces{{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.48 3.29 L 0 3.29 L 2.29 5.08}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 1.1 L 6.48 1.1 L 4.18 -0.7}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}_{\mathrm{hard}}$	$\supset T^{\mbox{\hskip 0.7pt\hbox to5.29pt{\vbox to4.79pt{\pgfpicture\makeatletter\hbox{\hskip 0.306pt\lower-0.81pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces\lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap=round} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin=round} \lx@inpgf@ignorespaces{{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.48 3.29 L 0 3.29 L 2.29 5.08}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 1.1 L 6.48 1.1 L 4.18 -0.7}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}_{\mathrm{soft}}$	$\subset T^{\mbox{\hskip 0.7pt\hbox to5.29pt{\vbox to1.98pt{\pgfpicture\makeatletter\hbox{\hskip 0.306pt\lower 1.13397pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces\lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap=round} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin=round} \lx@inpgf@ignorespaces{{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.48 1.99 L 0 1.99 L 2.29 3.89}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}_{\mathrm{soft}}$	$\supset T^{\mbox{\hskip 0.7pt\hbox to5.29pt{\vbox to4.79pt{\pgfpicture\makeatletter\hbox{\hskip 0.306pt\lower-0.81pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces\lxSVG@roundcap\lxSVG@begingroup@{stroke-linecap=round} \lx@inpgf@ignorespaces\lxSVG@roundjoin\lxSVG@begingroup@{stroke-linejoin=round} \lx@inpgf@ignorespaces{{}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.48 3.29 L 0 3.29 L 2.29 5.08}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {}{} {}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.612pt} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 1.1 L 6.48 1.1 L 4.18 -0.7}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}_{\mathrm{soft}}$	none	learnability

Table 1: Key features & assumptions of different theoretical frameworks. Each row summarizes how a theory models, or whether it captures, a particular feature of transformers.

Panel of Figure 2 — Figure 2: Formal expressivity relations between theories and transformer classes. The top row shows the theories, and the bottom row shows the classes of transformers they are compared to. Each edge denotes a containment (blue) or non-containment (red) between classes. An blue arrow pointing down ( ${\color[rgb]{0.1484,0.4531,0.6133}\downarrow}$ ) shows that the transformer class can express every task in the theory’s class (a lower bound). An blue arrow pointing up ( ${\color[rgb]{0.1484,0.4531,0.6133}\uparrow}$ ) shows that it cannot express any task outside that class (an upper bound). A red arrow indicates that the result in that direction does not hold. Some results have caveats or incompatible assumptions, so dashed arrows do not necessarily compose. See Appendix D for discussion and details of each result. BAPO is omitted because it has no known formal relation to transformers, and Sensitivity because it is a learnability theory.

Panel of Table 2 — Table 2: Theory–task predictions and experimental outcomes. Left: for each theory, we apply its hardness criterion, adapting tasks when necessary to fit within the theory’s assumptions about inputs. See Table 9 for an annotated version with explanations and references for each claim. Right: the outcome of each experiment in Section 4 : in-distribution learning (ID), length generalization (LG), and pretrained LLMs (LLM), graded as in Section 3.3 on the task settings of Figure 3 . ✗ ${}^{\text{}}$ : Hard , ✓ ${}^{\text{}}$ : Easy (for predictions, in some cases, not Hard ), $\blacksquare$ : non-trivial result proved here, ∗ : assuming a complexity theory conjecture, —: inapplicable. The bottom rows count, for each theory, the predictions that match each experiment, among cells with both a prediction and an outcome.

Figure 3: Results of the three experiments. Rows are task settings, and heatmap color shows mean normalized accuracy. Corner tabs, when present, show the minimum and maximum over five seeds in (a,b) or available models in (c). (a) In-distribution learning: each size $n$ shows the training-set size $N$ with the highest-scoring seed; the full $n\times N$ grid is in Figure 4 . (b) Length generalization: models train through $n=32$ (left of the black line). Each row uses the configuration that generalizes furthest among 27; the adjacent number counts configurations with a seed succeeding at every tested size through $n=256$ ; Section C.3 provides more details. (c) Pretrained LLMs: cells average the models available at each size; hatched rows are not applicable. In (a,c), ✓ ${}^{\text{}}$ marks Easy and ✗ ${}^{\text{}}$ marks Hard , using the $90\%$ threshold. A setting is Easy if it meets the threshold at the largest tested $n$ : in (a), with any seed at any $N$ ; in (c), with any single model.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Settings	Tokens	ID	LG	LLM
All , Any , Majority , Parity	one each	$n$	✓	✓	✓
Index	8 symbols	$n+1$	✓	✓	✓
Index-All , Index-Any , Index-Parity	$k\in\{2,3\}$	$n+k+1$	✓	✓	✓
Sparse-All , Sparse-Any , Sparse-Parity	$k\in\{2,3\}$	$n$	✓	✓	–
BinaryAdd	blocked or interleaved input; MSB- or LSB-first output	$3n+1$	✓	✓	✓
Dyck- $1$ , Dyck- $2$	depth bound $D\in\{4,8,\infty\}$	$2n+2$	✓	✓	✓

Appendix

Table 3: Task settings. Each row is one or more task settings. “Tokens” is the input length for models trained from scratch at size

n

. A check mark means the setting is used in the in-distribution (ID), length-generalization (LG), or pretrained-LLM (LLM) experiment. In total, ID uses 34 settings, LG uses 34, and LLM uses 27.

	In-distribution	Length generalization
Model sizes (layers, width, heads)	$(4,256,4)$	S $(2,64,2)$ , M $(4,128,4)$ , L $(8,256,8)$
Positional encoding	RoPE	9 encodings ( Table 5 ), plus uniform attention
Attention mask	causal	causal; also bidirectional where the task allows
Training sizes $n$	one of $8,16,32,64,128,256$	$8,16,20,24,32$ jointly
Evaluation sizes $n$	the training size	$8,16,20,24,32$ , and $48$ to $256$ in steps of $16$
Training examples $N$	$2^{8},2^{10},2^{12},2^{14},2^{16}$	$8{,}192$ , split evenly over training sizes

Appendix

Table 4: Training settings of the two from-scratch experiments. Settings shared by both experiments are given in the text.

Encoding	Position information
NoPE	None ( Kazemnejad et al., 2023 )
NoPE + BOS	None; a learned beginning-of-sequence token is prepended
Sinusoidal	Fixed sinusoidal encoding added to the input embeddings ( Vaswani et al., 2017 )
RoPE	Rotary encoding of queries and keys, base $10^{4}$ ( Su et al., 2024 )
YaRN	RoPE with YaRN dynamic scaling; the training length is the longest training input ( Peng et al., 2024a )
T5 bias	Learned relative attention bias, 32 buckets, maximum distance 128 ( Raffel et al., 2020 )

Appendix

Table 5: Positional encodings in the length-generalization experiment.

Model	Model ID	Reasoning control
GPT-5	gpt-5-2025-08-07	effort none ; also medium
GPT-5.4 mini	gpt-5.4-mini-2026-03-17	effort none
GPT-4o mini	gpt-4o-mini-2024-07-18	not applicable
DeepSeek-V3.2	DeepSeek-V3.2	effort none
Gemini 2.5 Flash	gemini-2.5-flash	thinking budget 0

Appendix

Table 6: Evaluated language models. Reasoning is disabled for all models in the main evaluation.

Tasks	Chance level $b$	Reason
All , Any , Parity , Index-All/Any , Index-Parity , Sparse-All/Any , Sparse-Parity	$1/2$	Bits are drawn with a per-bit probability that makes both labels equally likely.
Edge Existence , Directed Reachability , Undirected Reachability	$1/2$	Each graph yields one positive and one negative query. With dense supervision, the all-negative answer is correct exactly on negative queries.
Majority	$\tfrac{1}{2}+\binom{n}{n/2}2^{-(n+1)}$ ( $n$ even)	Bits are uniform and ties are labeled $1$ , so label $1$ is more likely: $0.64$ at $n=8$ , $0.52$ at $n=256$ .
Index	$1/8$	The queried symbol is uniform over $8$ values.
$k$ -Hop Induction	$\max\bigl(p_{\varnothing},\tfrac{1-p_{\varnothing}}{4}\bigr)$	$4$ equally likely symbols plus the null answer, which has probability $p_{\varnothing}(k,n)$ . For $k=3$ , $b=0.68$ at $n=8$ ; for $n\geq 32$ , $b\approx 1/4$ for all $k$ .
Dyck- $1$ , Dyck- $2$ , BinaryAdd	$0$ (full sequence)	Sequence answers: the legal next-token set after each prefix, or all $n{+}1$ bits of the sum. We do not normalize.

Appendix

Table 7: Chance level

b(\text{task},n)

: the accuracy of the best constant answer at input size

n

. Tasks with sequence answers use full-sequence accuracy without normalization. The same values are used in all three experiments.

Figure 4: In-distribution learning, all task settings. Each cell shows normalized accuracy for one task setting at input size $n$ (column groups) and training-set size $N$ (columns within a group). Each cell depicts the minimum, mean, and maximum over five seeds. Easy / Hard labeling criteria are described in Section B.2 .

Figure 5: Length generalization, all task settings. Same conventions as panel (b) of Figure 3 : for each task setting, we plot the best positional encoding and model size configuration, noted on the right.

Figure 6: Dependence of length generalization on positional encoding. Mean out-of-distribution normalized accuracy ( $n>32$ ) for each task and positional encoding, using causal attention and the best model size for each pair. Corner tabs show the minimum and maximum over seeds when they differ by more than $0.05$ . Some tasks like Sparse-All , Sparse-Parity , $1$ -Hop Induction , and Dyck- $1$ succeed only for certain positional encodings.

Figure 7: Length generalization with causal versus bidirectional attention. Here, we compare length generalization performance of the best configurations with causal and bidirectional attention. Cells show mean normalized accuracy across seeds, with a shared color scale. Corner tabs show the minimum and maximum over seeds when they differ by more than $0.05$ . Performance is fairly consistent between causal and bidirectional attention, although mean performance differs for some sparse tasks.

Figure 8: Length generalization with uniform attention versus the best configuration. This plot shows length generalization performance of uniform attention ( $W_{Q}=W_{K}=0$ , with a BOS token) at its best model size with causal attention, compared with the best configuration of the main search in Figure 5 . Uniform attention performs substantially worse across many problems.

Figure 9: GPT-5 with and without reasoning. Normalized accuracy for the same task settings and prompts, with reasoning disabled (left) or medium reasoning effort (right).

Panel of Figure 10 — Figure 10: Formal expressivity relations between theories and transformer classes (reproduced from Figure 2 ).

	Relation	Result
Star-free
a	Star-free $\mathrel{{\color[rgb]{0.1484,0.4531,0.6133}\subseteq}}$ Causal Hard Attn. with caveats	Yang et al. (2024, Theorem 5) show that strictly future-masked, rightmost-hard-attention transformers without positional encodings recognize every star-free language. The construction goes through the B-RASP programming language, which allows both strictly future-masked and strictly past-masked attention. B-RASP is equivalent to linear temporal logic with both since and until , which defines exactly the star-free languages. Every LTL formula is equivalent to one that uses only since when evaluated at the last position ( Kamp, 1968 ; Gabbay et al., 1980 ) , so every B-RASP program with both kinds of masking has an equivalent program that uses only causal future masking. However, this rewriting has a cost, as the past-only formula can be exponentially larger than an equivalent formula that uses both directions ( Artale et al., 2023 ) .
b	Causal Hard Attn. $\mathrel{{\color[rgb]{0.1484,0.4531,0.6133}\subseteq}}$ Star-free	By the same theorems ( Yang et al., 2024 , Theorems 2 and 4) , showing equivalence between masked hard-attention transformers, B-RASP , and LTL, every language recognized by masked hard-attention transformers is star-free; this direction preserves depth. This result describes masked hard-attention transformers without positional encoding, with positional information implicitly encoded in the masking. With rational sinusoidal encoding, the class of languages recognized by masked hard-attention transformers (with both past and future attention) grows to the regular languages in $\textsf{AC}^{0}$ ( Yang et al., 2024 , Corollary 8) .
c	Star-free $\mathrel{{\color[rgb]{0.1484,0.4531,0.6133}\subseteq}}$ Bidir. Hard Attn.	Barceló et al. (2024, Theorem 1) show that bidirectional unique-hard-attention transformers with positional encodings recognize every language definable in $\textsf{FO}[\mathrm{Mon}]$ , which contains $\textsf{FO}[<]$ and hence every star-free language.
d	Bidir. Hard Attn. $\mathrel{{\color[rgb]{0.7461,0.3164,0.1797}\nsubseteq}}$ Star-free	Bidirectional hard-attention transformers with positional encodings recognize every regular language in $\textsf{AC}^{0}$ ( Barceló et al., 2024 , Corollary 1) . This includes $(aa)^{*}$ , for example, which is regular and in $\textsf{AC}^{0}$ but not star-free ( Schützenberger, 1965 ) .
$\textsf{AC}^{0}$

Appendix

Table 8: Guide to the edges in Figures 2 and 10 .

Boolean
Task	Star-free	$\textsf{AC}^{0}$	$\textsf{TC}^{0}$	C-RASP	MPC	BAPO	Sensitivity
All / Any	✓ 1	✓ 2	✓ 2	✓ 3	✓ 4	✓ 5	✓ 6
Majority	✗ 7	✗ 7	✓ 8	✓ 9	✓ 10	✗ 11	✓ 12
Parity	✗ 7	✗ 7	✓ 8	✗ 13	✓ 4	✓ 5	✗ 14
Index
Index	✗ 15	✓ 16	✓ 16	✗ $\blacksquare$ 17	✓ 18	✓ 19	✓ 20

Appendix

Table 9: Theory–task prediction matrix. Annotated version of the theory-task predictions in Table 2 . For each theory, we apply its hardness criterion, adapting tasks when necessary to fit within the theory’s assumptions about inputs. Superscripts link to explanations and references in Table 10 . ✗

{}^{\text{}}

: Hard , ✓

{}^{\text{}}

: Easy (in some cases, not Hard ),

\blacksquare

: non-trivial result proved here, ∗ : assuming a complexity theory conjecture.

ID	Explanation
1	All / Any are star-free. They are defined in $\textsf{FO}[<]$ by $\forall i\,Q_{1}(i)$ and $\exists i\,Q_{1}(i)$ , respectively, where $Q_{1}(i)$ holds when position $i$ contains a one.
2	All / Any have depth-one circuits. All and Any are respectively a single unbounded-fan-in AND and OR gate, so they lie in both $\textsf{AC}^{0}$ and $\textsf{TC}^{0}$ .
3	All / Any have small C-RASP programs. All tests whether the prefix count of zeros is zero; Any tests whether the prefix count of ones is positive.
4	Regular languages have constant-round, sublinear-memory MPC algorithms. Gilbert & Hajiaghayi (2023, Theorem 3.2) give an $O(1/\delta)$ -round MPC algorithm with $O(n^{\delta})$ local memory for any fixed regular language. This covers Any / All , Parity , and constant-depth Dyck .
5	Regular languages are BAPO -easy. Schnabel et al. (2025, Theorem 2) show that every regular language has a constant-bandwidth BAPO ; this includes All / Any , Parity , and fixed-depth Dyck . For fixed alphabet $\Sigma$ and hop count $k$ , each output language of $k$ -Hop Induction is star-free and hence regular by Proposition 18 . Concatenating the finite-state summaries for the $\|\Sigma\|+1$ possible outputs gives a constant-bandwidth BAPO for the full output.
6	All / Any have low average sensitivity. Flipping a bit changes All ( Any ) exactly when all other bits are one (zero). Under uniform Boolean inputs, both therefore have average sensitivity $n/2^{n-1}=o(n)$ , giving an Easy prediction. This prediction uses the uniform distribution rather than the class-balanced distribution we use in experiments.

Appendix

Table 10: Explanations for the theory–task predictions. IDs correspond to the numbered links in Table 9 .

Figure 11: Softmax versus uniform attention on query-dependent retrieval. Accuracy against the key dimension

m

, for (a) width

d=m+2

with one layer and one head and (b) width 256 with four layers and four heads. Small markers are individual seeds.

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 540 papers

Sep 8, 2026

Length Generalization for Transformers via Compression

Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.

Georg Zetzsche, Hongjian Jiang, Andy Yang +4

Max Planck Institute for Software Systems (MPI-SWS) · RPTU Kaiserslautern-Landau · University of Notre Dame

Transformer Expressivity Transformer Length Generalization Generalization Bounds

Ask PDF

Jul 13, 2026

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the expressivity of attention-based models. By proposing handcrafted weights or using computational complexity arguments, a large amount of past theoretical works have sought to characterize which tasks are and which are not in the hypothesis class of Transformer models. However, little work investigates the learnability of such solutions. In this work, we make progress towards this goal. Inspired by recent loss landscape analysis work, we propose preliminary sample complexity bounds for learning C-RASP constructions with Transformers.

Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1

Mila & Universit´e de Montr´eal · University of Oxford · Saarland University

Transformer Sample Complexity

Ask PDF

Oct 26, 2026

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones

Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones. These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.

Marius Henry, Michael Rizvi-Martel, Michael Hahn

LaCoCo, Saarland University, Saarland Informatics Campus · Zuse School ELIZA · Mila & Université de Montréal

Language Model Generalization Generalization Bounds Length Generalization

Ask PDF

Abstract

Transformer

Explore similar work

Length Generalization for Transformers via Compression

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones