On the Expressive Power of Transformers

Phokion Kolaitis; Rik Sengupta

REVIEW 3 major objections 5 minor 31 references

On the Expressive Power of Transformers

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Transformer expressivity is calibrated by circuit classes, and chain-of-thought lifts decoders from AC0/TC0 to PTIME and Turing completeness.

desk verdict A compact, clearly written survey of transformer expressivity that maps known results onto circuit classes, with a few fixable presentation defects rather than any load-bearing flaw. read the letter →

arxiv 2608.12671 v1 pith:4MDNBB6Q submitted 2026-08-13 cs.AI cs.CC

Phokion Kolaitis , Rik Sengupta This is my paper · ORCID

classification cs.AIcs.CC

keywords transformersmodelsofcomputationcircuitcomplexityAC0TC0chain-of-thoughtnumericalprecisionlanguagerecognition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Transformers are usually judged by what they do in practice, but this paper treats them as formal language recognizers and asks which traditional complexity classes contain them. Its central claim is that circuit complexity supplies the right scale: constant-depth uniform circuits with AND/OR/NOT gates ($\mathsf{AC}^0$) and with majority gates ($\mathsf{TC}^0$) contain every transformer equipped with hard or soft attention, depending on numerical precision, when no chain-of-thought is allowed. Once a decoder can emit intermediate tokens, the same architectures climb through deterministic quadratic time, polynomial time, and, with unbounded chain-of-thought, can simulate arbitrary Turing machines. If this map is right, it tells a practitioner which tasks are structurally impossible for a given architecture, no matter how much data or training is used.

What carries the argument

The mechanism that carries the argument is the simulation of a constant-depth transformer by a constant-depth uniform circuit family. A transformer with a constant number of layers composes attention and feed-forward blocks whose computations on a fixed input length can be replaced by Boolean circuit gadgets; because the number of layers is constant, stitching the gadgets layer by layer yields a circuit of constant depth. Attention type and precision decide which gate basis the simulation needs: unique hard attention can be rendered with AND, OR, and NOT gates ($\mathsf{AC}^0$), while average-hard or softmax attention with enough precision must compute averages, which requires majority gates ($\mathsf{TC}^0$). For the chain-of-thought results, the decoder's generated tokens encode the state history of a Turing machine or finite-state machine, and the autoregressive loop plays the role of time, so the chain-of-thought length $f(n)$ acts as a time bound.

What would settle it

A single counterexample under the survey's stated assumptions would refute the calibration: exhibit a language computed by a constant-depth, $O(\log n)$-precision softmax-attention encoder, as defined in Section 2, that is provably not in $\mathsf{TC}^0$. Alternatively, re-derive the third bullet of Theorem 4.1 from its cited sources and check whether any source tacitly requires polynomial embedding dimension; if the inclusion fails without that condition, the theorem as printed is false.

Watch

Extended reading notes

Core claim

The paper assembles existing results into a single claim: transformer expressivity is not one point on a complexity scale but a family of points indexed by three architectural choices—attention type (unique hard, average hard, softmax), numerical precision (constant vs. $O(\log n)$), and chain-of-thought budget. Without chain-of-thought, unique-hard-attention encoders with arbitrary rational precision recognize only $\mathsf{AC}^0$ languages; softmax and average-hard encoders with $O(1)$ precision recognize only $\mathsf{AC}^0$; and softmax and average-hard encoders with $O(\log n)$ precision recognize only $\mathsf{TC}^0$, with the bounds nearly tight when embedding dimension is allowed to grow polynomially. With chain-of-thought, softmax decoders with $O(\log n)$ chain-of-thought stay in $\mathsf{AC}^0$ or $\mathsf{TC}^0$ depending on precision, average-hard decoders with $O(n)$ chain-of-thought reach $\mathsf{DTIME}[n^2]$, with polynomial chain-of-thought they recognize exactly $\mathsf{PTIME}$, and with unbounded chain-of-thought they can simulate arbitrary Turing machines. The intended upshot is that these containments, taken together, justify circuit complexity—rather than the Chomsky hierarchy—as the right yardstick for transformer power.

Load-bearing premise

The map is only as solid as the assumption that every cited upper-bound theorem was proved under the same architectural conventions—how precision is counted, whether embedding dimension may grow polynomially, what uniformity means, and whether the chain-of-thought length $f(n)$ is fixed in advance—that the survey uses in Theorems 4.1 and 4.2; the survey itself says to check the original papers for those details.

Editorial extensions

If this is right

Any task that cannot be decided by a constant-depth $\mathsf{TC}^0$ circuit is beyond every constant-depth, $O(\log n)$-precision softmax or average-hard attention encoder when no chain-of-thought is used, regardless of training.
Chain-of-thought is a resource that changes the complexity class: raising the budget from $O(\log n)$ to $O(n)$ to polynomial moves a decoder from $\mathsf{AC}^0$/ $\mathsf{TC}^0$ to $\mathsf{DTIME}[n^2]$ and then to exactly $\mathsf{PTIME}$.
With unbounded chain-of-thought, hard-attention decoders can simulate arbitrary Turing machines, so there is no formal upper bound on what such decoders can compute given enough intermediate tokens.
Precision is as decisive as attention: changing encoder precision from $O(1)$ bits to $O(\log n)$ bits is the difference between $\mathsf{AC}^0$ and $\mathsf{TC}^0$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The map implies a design rule the authors do not state: if a target task is outside $\mathsf{AC}^0$, a fixed-precision encoder cannot learn it, and the only architectural levers that move the boundary are chain-of-thought or a jump to $O(\log n)$ precision.
The tightness discussion suggests a testable hypothesis: with constant embedding dimension rather than polynomial, log-precision transformers may fail to capture all of $\mathsf{TC}^0$, which would make deployed fixed-width models strictly weaker than the clean asymptotics suggest.
A natural neighboring program is to measure a trained model's effective precision and chain-of-thought budget empirically, then read off the complexity class the model actually occupies on the scale this survey lays out.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This is a survey, not a research paper, and it should be read as one. The authors compile known results on transformer expressivity into a convenient map: UHAT encoders land in AC0; SMAT and AHAT encoders with O(1) precision stay in AC0; with O(log n) precision they reach TC0; and with chain-of-thought they jump to DTIME[n^2], PTIME, and Turing completeness. The abstract's claim that circuit complexity is the right lens for this literature is defensible, and the survey makes that case clearly.

What the paper does well: the architecture section is careful and readable. Treating attention type, precision, and chain-of-thought as explicit resources is exactly the right framing, and the discussion of why one might prefer circuit classes over the Chomsky hierarchy is sensible. The survey is honest about deferring to primary sources for exact hypotheses, and I see no self-citations or invented entities. For a newcomer, this is a genuinely useful entry point.

The soft spots are real but not fatal. After Theorem 4.2, the text says the fourth and fifth bullet points are equivalences and attributes them to UHAT, but bullet four is about AHAT with poly(n) CoT recognizing PTIME, and bullet five is about AHAT with unbounded CoT simulating Turing machines. "Simulate" is one direction, and "every recursively enumerable language is computable" requires the acceptance-token stopping rule that footnote 3 admits was never formalized. That footnote is important and should be elevated, because the formal definition in Section 2.4 fixes f(n) in advance while the theorem statement allows unbounded CoT. The other issue is that the tightness discussion introduces a poly(n) embedding-dimension condition that is absent from the theorem statements. The authors do point readers to the sources, so this is a presentation defect, but it matters for anyone trying to use the survey without reading the originals.

For a survey, this is a solid piece. It is not ground-breaking, but it does not need to be. The errors are fixable, and the core compilation appears faithful. I would send it to peer review with the expectation of minor revision: fix the UHAT/AHAT slip, qualify the "equivalence" language, and either formalize the acceptance-token model or explicitly mark the Turing-completeness bullet as informal.

Referee Report

3 major / 5 minor

Summary. The paper surveys recent results on the expressive power of transformer encoders and decoders as formal language recognizers, organized around a parameterized architecture (attention type, precision, chain-of-thought length) and compared against circuit and classical complexity classes. The main claims are Theorem 4.1, that UHAT encoders with arbitrary rational precision recognize only AC0 and that SMAT/AHAT encoders with O(1) or O(log n) precision recognize only AC0 or TC0 respectively, and Theorem 4.2, that chain-of-thought decoders range from AC0 up to PTIME and Turing completeness. The survey explicitly presents itself as a compilation of known results rather than a source of new derivations, but it asserts that circuit complexity has by and large emerged as the correct framework for calibrating transformer expressivity.

Significance. If the compilation is accurate, the paper provides a useful map of a rapidly moving literature, connecting transformer variants to AC0, TC0, DTIME[n^2], PTIME, and Turing completeness. Its strengths are a clean organization of the parameter space (attention mode, precision, chain-of-thought length, masking), a helpful descriptive-complexity section linking circuit classes to logical formalisms, and an honest acknowledgment that the reader must consult the primary sources for exact architectural assumptions. The paper ships no new proofs, code, or machine-checked artifacts; its value is as a literature survey. The significance of the central calibration claim is high, but only if the theorem statements are tied to the model formalized in Section 2; as written, the formal gaps discussed below prevent the paper from establishing that claim on its own terms.

major comments (3)

[§4.2 (discussion after Theorem 4.2)] The sentence "The fourth and fifth bullet points are equivalences: every recursively enumerable language is computable by a UHAT decoder with an unbounded amount of chain-of-thought" contradicts the bullet points it refers to: bullet 4 concerns AHAT decoders and PTIME, and bullet 5 concerns AHAT decoders and simulation of arbitrary Turing machines, not UHAT decoders or recursively enumerable languages. This is not a harmless slip: footnote 3 concedes that the unbounded-CoT Turing-completeness statement requires a stopping-token model "we have not formalized," whereas Section 2.4 defines chain-of-thought only for a pre-specified number f(n) of intermediate tokens. The strongest bullets of Theorem 4.2 are therefore not stated for the architecture formally defined in Section 2.4, and this undermines the paper's headline claim that the expressivity of transformers is calibrated by circuit and classical complexity classes.
[§4.1 (Theorem 4.1 and preceding paragraph)] The theorem statements omit the exact architectural hypotheses required to transfer the cited results to the architecture defined in Sections 2.3-2.4: the precision model (whether O(1) or O(log n) means fixed-precision arithmetic with specific rounding conventions, or exact rational arithmetic with bit-length bounds), the role of positional encodings, and the growth of the embedding dimension as a function of n. The sentence "we encourage the reader to refer to the relevant work for the exact assumptions on the architecture" makes the containments in Theorem 4.1 unverifiable from the paper's own definitions. Since these containments are the central evidence for the survey's calibration claim, the compilation is not yet a self-contained statement of the results it surveys.
[§4.1 (tightness discussion)] The tightness discussion introduces a condition absent from Theorem 4.1: "when one allows poly(n) embedding dimension, transformers with O(1) precision and O(log n) precision capture all of AC0 and TC0." The theorem statements and the parameter discussion in Section 2.2 do not specify any growth rate for the embedding dimension d, and the earlier text only says d "is allowed to depend on the context length n." As written, the "essentially tight" claim is not connected to the theorem it is meant to qualify, and the reader cannot tell whether the containments in Theorem 4.1 hold for the same parameter regime as the converse statements.

minor comments (5)

[§2.1] The sentence "The evolutions of LLMs has seen a shift from encoder models" should be "The evolution of LLMs has seen a shift," and a few other grammatical slips suggest the manuscript would benefit from a light copyedit.
[§2.3, Eq. (1)-(2)] The typesetting of the attention formula is inconsistent: the inner product q_i^T k_j / sqrt(d_key) is shown with the division inside the scalar product, and the display of Eq. (1) is malformed. This makes the definition of attention scores unnecessarily hard to read.
[§4 (precision discussion)] The discussion before Theorem 4.1 says "allowing this precision to arbitrary real numbers" can increase expressivity, but Theorem 4.1's first bullet restricts the claim to "arbitrary (rational) precision." The distinction between real and rational precision should be stated consistently, since the architecture in Section 2.3 uses real-valued vectors throughout.
[§2.4] In the decoder definition, the sentence "the output layer takes the d-dimensional vector x^{(L)}_{n+f(n)-1}" is correct but slightly confusing because it describes converting the final timestep to a probability; a brief pointer to the fact that this is the vector that would otherwise produce the final token would improve readability.
[References] The reference for Chen, Peng, and Wu lists both 2024 and 2025 (FOCS) identifiers; please unify the citation to the published version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the survey aggregates independently cited external results, with no self-citations, no fitted parameters, and no predictions derived from the survey's own inputs.

full rationale

This paper is an expository survey, not a derivation. Theorems 4.1 and 4.2 are explicitly attributed to external work (e.g., Hao et al. [10], Chiang [6], Li et al. [14], Merrill and Sabharwal [18,19], Strobl [24]), and the surrounding text describes, rather than creates, the simulation arguments. Neither author is cited in the reference list, so there is no self-citation chain to evaluate. There are no fitted parameters, no quantities are defined in terms of the claims they are used to prove, and no known result is repackaged as a new prediction. The paper's own caveats—that readers should consult the original papers for exact architectural assumptions, that tightness for the AC0 and TC0 bullets requires poly(n) embedding dimension, and footnote 3 conceding that the unbounded-CoT Turing-completeness bullets require an acceptance-token model not formalized in Section 2.4—are accuracy and scope concerns about how faithfully the survey states the imported results. They are not circularity: each theorem still rests on an external source rather than on the survey's own definitions. Under the stated rules, reliance on cited theorems is the normal contract of a survey and does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

As a survey, the paper introduces no fitted parameters and no new postulated entities. Its content is the cited literature, so the ledger records the three background assumptions the compilation rests on: the classical circuit hierarchy, the transformer-as-recognizer abstraction, and the fidelity of the survey's transmission of the primary sources. The fidelity assumption is the fragile one, since the paper itself notes that exact assumptions are deferred to the cited works.

assumptions (3)

standard math AC0 is strictly contained in TC0, and TC0 is contained in LOGSPACE which is contained in PTIME, with MAJ not in AC0 (Furst, Saxe, Sipser).
Invoked in equation (3), Section 3.2, to calibrate transformer expressivity against classical complexity classes; taken as background, not proved in the paper.
domain assumption Transformers can be treated as language recognizers over arbitrarily long strings, with constant depth and with precision, embedding dimension, and chain-of-thought length as functions of input length.
Section 2 frames transformers this way, the standard abstraction in the cited expressivity literature; the survey notes real context windows are bounded, so the abstraction is itself a modeling choice.
domain assumption The theorems compiled in Sections 4.1 and 4.2 are faithful restatements of the cited papers' results under the survey's simplified hypotheses.
The survey gives no proofs; its own disclaimer ('refer to the relevant work for the exact assumptions') means the reader must trust the compilation. Footnote 3 already shows one claim exceeds the formalized model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Expressive Power of Transformers." pith.science (2026). https://pith.science/paper/4MDNBB6Q

@misc{pith2026260812671,
  author       = {Pith},
  title        = {Pith review of: On the Expressive Power of Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4MDNBB6Q}},
  note         = {Machine review of arXiv:2608.12671}
}

read the original abstract

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.

Figures

Figures reproduced from arXiv: 2608.12671 by the authors.

**Figure 2.** An encoder (left) and a decoder (right). [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 19 canonical work pages

[1]

Ackerman and G

J. Ackerman and G. Cybenko. A survey of neural networks and formal languages, 2020. URL https://arxiv.org/abs/2006.01338

arXiv 2020
[2]

Barceló, A

P. Barceló, A. Kozachinskiy, A. W. Lin, and V. Podolskii. Logical languages accepted by transformer encoders with hard attention. InThe Twelfth International Conference on Learning Representations,

work page
[3]

A. A. Bavandpour, X. Huang, M. Rofin, and M. Hahn. Lower bounds for chain-of-thought reasoning in hard-attention transformers. InForty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=Oh9sG5ae2b

work page 2025
[4]

Onthecomputationalpoweroftransformersanditsimplications in sequence modeling

S.Bhattamishra,A.Patel,andN.Goyal. Onthecomputationalpoweroftransformersanditsimplications in sequence modeling. In R. Fernández and T. Linzen, editors,Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475, Online, Nov. 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.conll-1.37. URL https://acl...

doi:10.18653/v1/2020.conll-1.37 2020
[5]

L. Chen, B. Peng, and H. Wu. Theoretical limitations of multi-layer transformer.2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2631–2653, 2024. URL https://api.semanticscholar.org/CorpusID:274464787

work page 2025
[6]

D. Chiang. Transformers in uniform TC0.Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https://openreview.net/forum?id=ZA7D4nQuQF

work page 2025
[7]

Chiang, P

D. Chiang, P. Cholak, and A. Pillay. Tighter bounds on the expressivity of transformer encoders. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors,Proceedings of the 40th International Conference on Machine Learning, volume 202 ofProceedings of Machine Learning Research,pages5544–5562.PMLR,July2023. URLhttps://proceedi...

work page
[8]

M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy.Math. Syst. Theory, 17(1):13–27, 1984. doi: 10.1007/BF01744431. URL https://doi.org/10.1007/BF01744431. 11

doi:10.1007/bf01744431 1984

Show all 31 references

[9]

M. Hahn. Theoretical limitations of self-attention in neural sequence models.Transactions of the Association for Computational Linguistics, 8:156–171, 2020. doi: 10.1162/tacl_a_00306. URL https://aclanthology.org/2020.tacl-1.11/

2020 doi
[10]

Y. Hao, D. Angluin, and R. Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity.Transactions of the Association for Computational Linguistics, 10: 800–810, 2022. doi: 10.1162/tacl_a_00490. URL https://aclanthology.org/2022.tacl-1.46/

2022 doi
[11]

Holtzman, J

A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id= rygGQyrFvH

2020
[12]

Immerman.Descriptive complexity

N. Immerman.Descriptive complexity. Graduate texts in computer science. Springer, 1999. ISBN 978- 1-4612-6809-3. doi: 10.1007/978-1-4612-0539-5. URL https://doi.org/10.1007/978-1-4612-0539-5

1999 doi
[13]

Jiang, M

H. Jiang, M. Hahn, G. Zetzsche, and A. W. Lin. Softmax transformers are Turing-complete. InThe Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/ forum?id=FdkPOHlChS

2026
[14]

Chainofthoughtempowerstransformerstosolveinherentlyserialprob- lems

Z.Li,H.Liu,D.Zhou,andT.Ma. Chainofthoughtempowerstransformerstosolveinherentlyserialprob- lems. InB.Kim,Y.Yue,S.Chaudhuri,K.Fragkiadaki,M.Khan,andY.Sun,editors,InternationalCon- ferenceonLearningRepresentations,volume2024,pages11911–11943,2024. URLhttps://proceedings. iclr.cc/...

2024
[15]

E. Malach. Auto-regressive next-token predictors are universal learners. InForty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=i56plqPpEa

2024
[16]

W. Merrill. Formal languages and the NLP black box. InDevelopments in Language Theory: 27th International Conference, DLT 2023, Umeå, Sweden, June 12–16, 2023, Proceedings, page 1–8, Berlin, Heidelberg, 2023. Springer-Verlag. ISBN 978-3-031-33263-0. doi: 10.1007/978-3-031-3326...

2023 doi
[17]

Merrill and A

W. Merrill and A. Sabharwal. A logic for expressing log-precision transformers. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors,Advances in Neural Information Processing Systems, volume 36, pages 52453–52463. Curran Associates, Inc., 2023. URL h...

2023
[18]

Merrill and A

W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545, 2023. doi: 10.1162/tacl_a_ 00562. URL https://aclanthology.org/2023.tacl-1.31/

2023 doi
[19]

Merrill and A

W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. In B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun, editors,International Conference on Learning Representations, volume 2024, pages 7690–7706, 2024. URL https://proceedi...

2024
[20]

Merrill, V

W. Merrill, V. Ramanujan, Y. Goldberg, R. Schwartz, and N. A. Smith. Effects of parameter norm growth during transformer training: Inductive bias from gradient descent. In M.-F. Moens, X. Huang, L. Specia, and S. W.-t. Yih, editors,Proceedings of the 2021 Conference on Empiric...

2021
[21]

Merrill, A

W. Merrill, A. Sabharwal, and N. A. Smith. Saturated transformers are constant-depth threshold circuits.Transactions of the Association for Computational Linguistics, 10:843–856, 2022. doi: 10.1162/tacl_a_00493. URL https://aclanthology.org/2022.tacl-1.49/

2022 doi
[22]

Pérez, P

J. Pérez, P. Barceló, and J. Marinkovic. Attention is Turing complete.J. Mach. Learn. Res., 22(1), Jan
[23]

R. Qiu, Z. Xu, W. Bao, and H. Tong. Ask, and it shall be given: On the Turing completeness of prompting. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu, editors,International Conference on Learning Representations, volume 2025, pages 6286–6309, 2025. URL https://proceedings.ic...

2025
[24]

Average-hardattentiontransformersareconstant-depthuniformthresholdcircuits,2023

L.Strobl. Average-hardattentiontransformersareconstant-depthuniformthresholdcircuits,2023. URL https://arxiv.org/abs/2308.03212

2023 arXiv
[25]

Strobl, W

L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin. What formal languages can transformers express? A survey.Transactions of the Association for Computational Linguistics, 12:543–561, 2024. doi: 10.1162/tacl_a_00663. URL https://aclanthology.org/2024.tacl-1.30/

2024 doi
[26]

Vaswani, N

A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors,Advances in Neural Information Processing S...

2017
[27]

A. Yang, D. Chiang, and D. Angluin. Masked hard-attention transformers recognize exactly the star-free languages. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=FBMsBdH0yz

2024
[28]

A. Yang, L. Strobl, D. Chiang, and D. Angluin. Simulating hard attention using soft attention, 2025. URL https://arxiv.org/abs/2412.09925

2025 arXiv
[29]

A. Yang, C. Watson, A. Xue, S. Bhattamishra, J. Llarena, W. Merrill, E. D. S. Ferreira, A. Svete, and D. Chiang. The transformer cookbook.Transactions on Machine Learning Research, 2026. ISSN 2835-8856. URL https://openreview.net/forum?id=sPshCSvDrX. 13

2026
[2021]

doi: 10.18653/v1/2021.emnlp-main.133

Association for Computational Linguistics. doi: 10.18653/v1/2021.emnlp-main.133. URL https://aclanthology.org/2021.emnlp-main.133/. 12

2021 doi
[2024]

URL https://openreview.net/forum?id=gbrHZq07mq

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Ackerman and G

J. Ackerman and G. Cybenko. A survey of neural networks and formal languages, 2020. URL https://arxiv.org/abs/2006.01338

arXiv 2020

[2] [2]

Barceló, A

P. Barceló, A. Kozachinskiy, A. W. Lin, and V. Podolskii. Logical languages accepted by transformer encoders with hard attention. InThe Twelfth International Conference on Learning Representations,

work page

[3] [3]

A. A. Bavandpour, X. Huang, M. Rofin, and M. Hahn. Lower bounds for chain-of-thought reasoning in hard-attention transformers. InForty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=Oh9sG5ae2b

work page 2025

[4] [4]

Onthecomputationalpoweroftransformersanditsimplications in sequence modeling

S.Bhattamishra,A.Patel,andN.Goyal. Onthecomputationalpoweroftransformersanditsimplications in sequence modeling. In R. Fernández and T. Linzen, editors,Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475, Online, Nov. 2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.conll-1.37. URL https://acl...

doi:10.18653/v1/2020.conll-1.37 2020

[5] [5]

L. Chen, B. Peng, and H. Wu. Theoretical limitations of multi-layer transformer.2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2631–2653, 2024. URL https://api.semanticscholar.org/CorpusID:274464787

work page 2025

[6] [6]

D. Chiang. Transformers in uniform TC0.Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https://openreview.net/forum?id=ZA7D4nQuQF

work page 2025

[7] [7]

Chiang, P

D. Chiang, P. Cholak, and A. Pillay. Tighter bounds on the expressivity of transformer encoders. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors,Proceedings of the 40th International Conference on Machine Learning, volume 202 ofProceedings of Machine Learning Research,pages5544–5562.PMLR,July2023. URLhttps://proceedi...

work page

[8] [8]

M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy.Math. Syst. Theory, 17(1):13–27, 1984. doi: 10.1007/BF01744431. URL https://doi.org/10.1007/BF01744431. 11

doi:10.1007/bf01744431 1984