Pith. sign in

REVIEW 3 major objections 4 minor 8 cited by

On the Ability and Limitations of Transformers to Recognize Formal Languages

T0 review · 3 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

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

Pith's one-line read Transformers can learn a subclass of counter languages by computing prefix ratios, but their ability on regular languages degrades as star-free dot-depth increases and fails outright on non-star-free languages such as Parity and $(aa)^*$.

desk verdict Useful systematic study of Transformers on formal languages, but the negative claims about non-star-free languages are more protocol-dependent than the conclusion suggests. read the letter →

arxiv 2009.11264 v2 pith:NPAZVVVT submitted 2020-09-23 cs.CL cs.LG

Satwik Bhattamishra , Kabir Ahuja , Navin Goyal This is my paper · ORCID
classification cs.CLcs.LG
keywords formallanguagestransformersself-attentionstar-freedot-depthhierarchycounterpositionalencodingslengthgeneralization
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

This paper asks which formal languages a Transformer can learn to recognize in practice, not just express in principle. It proves a construction in which a single-layer Transformer recognizes Shuffle-Dyck and n-ary Boolean Expressions by using uniform self-attention to compute, at every prefix, the ratio of the relevant counter value to the prefix length. Experiments on 27 languages then show that this mechanism is actually what small trained Transformers learn, and that the same models generalize reliably only on star-free regular languages of dot-depth 1. On higher dot-depths and on non-star-free languages that require modular counting or periodicity—Parity, $(aa)^*$, $(abab)^*$—their accuracy collapses on lengths beyond the training window, while LSTMs of similar size solve all of them. The paper reads this as the first practical-scale evidence that self-attention has a sharp learnability boundary tied to a classical measure of regular-language complexity.

What carries the argument

The load-bearing mechanism is uniform self-attention that computes depth-to-length ratios. In the construction, key vectors are set to zero so every prefix position attends equally to all previous tokens; value vectors place $+1$ and $-1$ in dedicated coordinates for each counter. Averaging these value vectors yields, at each prefix, the signed difference between opening and closing symbols divided by the prefix length—the depth-to-length ratio for Dyck-like languages, and the counter-value-to-length ratio for Boolean expressions. A ReLU feed-forward layer turns the sign pattern of these coordinates into the prediction of legal next characters, and a second attention layer performs final acceptance checks. The dot-depth hierarchy of star-free languages supplies the paper's complexity yardstick: languages of dot-depth 1 sit at the boundary of what trained Transformers learn, and the failure of higher dot-depths is traced to the inability of masked attention to distinguish positions within a run of identical symbols unless positional encodings are supplied.

What would settle it

Run the paper's exact character-prediction pipeline on Parity with a Transformer of hidden size 64, 6 layers, and 10k training samples in lengths 2–50; if validation accuracy on lengths 100–200 exceeds 90%, the claim that Transformers fail on this non-star-free language is an artifact of the small-model protocol rather than a limitation of the architecture. A cheaper variant: train on $D_2$ with absolute positional encodings and test on lengths 200–300, where the paper reports near-zero extrapolation; substantial success there would break the proposed dot-depth boundary.

Watch

Extended reading notes

Core claim

The central claim is that Transformers are able to generalize on star-free languages within dot-depth 1 but have difficulty with higher dot-depths or more complex classes like non-star-free languages. On the positive side, the paper exhibits a family of counter languages—Shuffle-Dyck and $n$-ary Boolean Expressions—that Transformers recognize for practical input lengths, and shows that the learned model does the task by the same route as the construction: attention weights are nearly uniform, value vectors encode per-symbol counter updates, and self-attention outputs track the depth-to-length (or counter-value-to-length) ratio with Pearson correlation $\sim 0.99$. The paper's limitation claims are empirical, made under a precise protocol: character prediction from positive examples with models up to 4 layers and hidden sizes 2–32. Under that protocol, Transformers fail on Parity, $(aa)^*$, $(abab)^*$, and on the star-free family $D_n$ for $n>1$, and a single-layer Transformer cannot implement a counter reset operation, while a two-layer one can.

Load-bearing premise

The paper defines "recognize" as perfect next-character prediction on positive examples only, using small Transformers with mean-squared error; if a differently trained or larger Transformer solved Parity or higher dot-depths, the reported limitations would be properties of this protocol, not of Transformers in general.

Editorial extensions

If this is right

  • A Transformer with only positional masking (no explicit encodings) can recognize Shuffle-Dyck and Boolean Expressions and extrapolate to lengths well beyond training; adding absolute or relative positional encodings degrades that extrapolation.
  • On regular languages, the paper predicts that the learnable class is roughly star-free dot-depth 1: languages like $(ab)^*$ and Tomita 1/2/4/7 generalize perfectly, while $D_2$, $D_4$, and $\{0,1,2\}^*02^*$ do not.
  • Non-star-free languages that need periodicity or modular counting—Parity, $(aa)^*$, $(aaaa)^*$, $(abab)^*$, Tomita 3/5/6—are effectively outside the reach of these Transformers under the training protocol, unlike LSTMs.
  • Positional encoding choice is decisive for modular counting: the periodic encoding $\cos(n\pi)$ makes $(aa)^*$ solvable, standard absolute/relative encodings fail, and trainable embeddings learn a similar pattern but cannot extrapolate beyond the training length.
  • Depth of the network restores some counter abilities: two layers are necessary and sufficient in the tested setup to handle reset operations that a single layer provably cannot implement.

Reading between the lines

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

  • A natural inference the paper does not draw: the dot-depth-1 boundary is a property of the next-character-prediction training signal and of small models, so it should not be read as an impossibility theorem for Transformers; larger models, scratchpads, or classification with negative examples may cross it.
  • The ratio-computation mechanism suggests a design heuristic for neuro-symbolic tasks: if a language's acceptance can be decided from aggregate prefix statistics alone, self-attention has a natural route to it; if it requires remembering a small local state (parity, period), attention needs an external memory or a task-specific positional code.
  • The paper's success with $\cos(n\pi)$ on $(aa)^*$ and failure on $(aaaa)^*$ suggests a testable extension: periodic positional encodings of period $k$ should solve $(a^k)^*$ but not $(a^{k+1})^*$, making the period of the encoding a controllable resource for modular counting.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies the ability of small Transformers to model counter and regular languages. It presents constructions showing that certain counter languages (Shuffle-Dyck, n-ary Boolean Expressions, and a restricted class of counter languages) can be recognized by Transformers that compute depth-to-length or counter-value-to-length ratios through uniform attention. Empirically, on a character-prediction task with positive examples only, Transformers with positional masking generalize well on several counter languages, while LSTMs generalize on all evaluated regular languages; Transformers do well on star-free regular languages of dot-depth 1 but poorly on higher dot-depth and on non-star-free languages under standard positional encodings. The paper further shows that custom positional encodings, such as cos(nπ), can make (aa)* solvable, indicating that the limitations are tied to encoding schemes.

Significance. The paper is useful as a controlled empirical study of Transformer biases: it covers 27 formal languages, reports held-out length bins, releases code, and offers an interpretable construction that matches post-hoc attention visualization (correlation around 0.99). The positive expressiveness results and the encoding-dependent failure analysis are valuable. However, the headline negative claim—that Transformers have limited ability on non-star-free regular languages—is not established as an architectural limitation; it is established only for a specific encoding family and a positive-only character-prediction protocol. This distinction is important for the paper's contribution.

major comments (3)
  1. [Section 7.2, Table 5] The paper's central limitation claim, first stated in Section 7.1 and repeated in Section 8 ('Transformers are able to generalize on star-free languages within dot-depth 1 but have difficulty ... non-star-free'), is not supported as an architectural statement. Table 5 itself reports 100.0/100.0 for (aa)* with cos(nπ) positional encoding across both bins, and 100.0/0.0 with trainable embeddings (100% within the training-length bin). Lemma C.4, which is cited to explain the failure, applies only to models with positional masking alone. The evidence therefore establishes a limitation of the particular encoding family and training setup, not of Transformers generally, and the conclusion should be narrowed to 'with absolute/relative positional encodings and positive-only character prediction, these models fail.'
  2. [Section 4, Proposition 4.1 and Lemma C.2] The expressiveness proofs are written for the architecture of Section 3, which includes residual connections and layer normalization, but the constructions set K to zero and V to identity and then identify the attention output a_i with the layer output z_i after a ReLU FFN. No residual term x_i is removed or accounted for in Proposition 4.1 or Lemma C.2. Lemma C.1 explicitly adds the residual term to a_i, but the main-paper constructions do not, so as written they prove expressiveness for a stripped-down variant rather than for the model that is trained in Section 6. Please either state that the constructions apply to the residual-free variant or show how the residual and normalization are absorbed into subsequent layers.
  3. [Section 5.1 and Table 4] The failure results for Parity and other non-star-free languages are conditional on positive-only character prediction with a k-hot MSE target. For Parity, at every prefix both 0 and 1 are valid continuations, so the only informative signal is whether the end-of-sequence symbol is allowed; with only positive samples this signal appears only at the final position of each training string and may be extremely sparse. Near-zero Bin-1 accuracy under this protocol does not establish that Transformers cannot learn or represent Parity. Report results with negative examples or a classification-style signal, or explicitly frame the negative results as properties of the positive-only character-prediction protocol.
minor comments (4)
  1. [Tables 3 and 9] It is unclear which configuration is reported under the 'Transformer' column in Table 3; Table 9 distinguishes 'Only Positional Masking' from 'with Position Encodings', and the values differ substantially (e.g., Tomita 4 Bin-0: 24.1 vs 100.0). Please label the reported configuration.
  2. [Section 5.1] Accuracies are reported as means of the top-5 hyperparameter configurations with no variance; near-zero numbers such as 0.2 in Table 9 would benefit from standard deviations or best-configuration details.
  3. [Section 6.1 and Figure 2] The correlation of 0.99 between attention outputs and depth-to-length ratios is shown for a single selected model; state how robust this is across seeds and hyperparameter settings.
  4. [Appendix Table 6] The first bin's range is defined by the training set and can differ from the stated Bin Width; please spell out ranges explicitly in a separate column for each language, especially for the (aa)* and (aaaa)* datasets where generation of all positive examples in a range is non-trivial.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is an explicit existence proof and the negative claims are empirical and conditional on a stated protocol.

full rationale

The paper's central derivation chain is not circular. Proposition 4.1 and Lemmas C.1-C.4 give explicit Transformer constructions and limitation proofs with specified weights and assumptions; these are not obtained by fitting the target languages into the model. The empirical evaluation uses held-out length bins (Bin-1/2/3) generated independently from the training window, so the generalization results are external rather than fitted. Section 6.1's visualization of self-attention outputs correlating with depth-to-length ratios is a post-hoc interpretation of trained models; it does not feed back into model selection or parameter fitting, so it does not constitute a fitted input being renamed as a prediction. The only self-citation (Bhattamishra et al., 2020) appears in related work as context and is not load-bearing for the current claims. The limitation claims about non-star-free languages are explicitly conditional: Section 5.1 defines 'recognize' as perfect character prediction on positive examples, and Section 7.2 reports that (aa)* reaches 100% with cos(nπ) encodings, so the paper itself flags that failures depend on the encoding family. This conditionality weakens the generality of the negative claim but is not circularity. Overall, no self-definitional, fitted-input, or self-citation chain reduces the results to their inputs.

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

The central theoretical construction uses explicit hand-set weights (e.g., +1/-1 embeddings, identity Q/V, zero K) that are not fitted to data; these are part of the proof rather than free parameters. The empirical claims rest on the task definition, the architecture variant (including residual connections), and the use of dot-depth as a complexity measure, listed as axioms.

assumptions (3)
  • domain assumption The constructions in Section 4 assume the Transformer architecture of Section 3 can be instantiated without residual connections and layer normalization affecting the result, since the proofs set attention weights directly but do not account for these components.
    Prop 4.1 and Lemma C.1 set K to zero and Q/V to identity, then apply an FFN; residual connections and LayerNorm are not mentioned, so the existence proof implicitly ignores them.
  • domain assumption Character prediction on only positive samples (Section 5.1) is a faithful measure of a model's ability to recognize a formal language.
    The paper equates 'recognize' with perfect character prediction; all empirical conclusions about limitations follow from this operationalization.
  • domain assumption The dot-depth hierarchy is the appropriate complexity measure for predicting Transformer generalization on regular languages.
    The paper hypothesizes that dot-depth captures the difficulty for Transformers, but this is tested only on the Dn family and Tomita grammars.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Ability and Limitations of Transformers to Recognize Formal Languages." pith.science (2026). https://pith.science/paper/NPAZVVVT

@misc{pith2026200911264,
  author       = {Pith},
  title        = {Pith review of: On the Ability and Limitations of Transformers to Recognize Formal Languages},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NPAZVVVT}},
  note         = {Machine review of arXiv:2009.11264}
}
read the original abstract

Transformers have supplanted recurrent models in a large number of NLP tasks. However, the differences in their abilities to model different syntactic properties remain largely unknown. Past works suggest that LSTMs generalize very well on regular languages and have close connections with counter languages. In this work, we systematically study the ability of Transformers to model such languages as well as the role of its individual components in doing so. We first provide a construction of Transformers for a subclass of counter languages, including well-studied languages such as n-ary Boolean Expressions, Dyck-1, and its generalizations. In experiments, we find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction. Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance as we make languages more complex according to a well-known measure of complexity. Our analysis also provides insights on the role of self-attention mechanism in modeling certain behaviors and the influence of positional encoding schemes on the learning and generalization abilities of the model.

Figures

Figures reproduced from arXiv: 2009.11264 by the authors.

Figure 1
Figure 1. Counter languages form a strict superset of [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Values of different coordinates of the output [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Plot of value vectors of transformer based [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Attention maps for models trained on Shuffle-2 and Boolean-3 languages. Similar to our constructions [PITH_FULL_IMAGE:figures/full_fig_p019_4.png]
Figure 5
Figure 5. Figure 5: Values of four different coordinates of the output of self-attention block. The model is trained to [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]
Figure 6
Figure 6. Figure 6: The values of coordiante 3 of the learned po [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Head Complexity of Boolean Functions in Single-Layer Attention

    cs.CC 2026-09 accept novelty 7.0 of 10

    In a single-layer attention-only transformer, m-bit parity needs exactly m attention heads, and a generic n-bit Boolean function needs about 2^n/poly(n) heads, with embedding dimension and precision provably unable to...

  2. Disentangling the Expressivity of RoPE

    cs.LG 2026-08 conditional novelty 7.0 of 10

    Periodic RoPE schedules yield exactly LTL with past operators and modular predicates, while conventional non-periodic RoPE provides only a bounded, precision-limited fixed-offset look-back mechanism.

  3. When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal

    cs.LG 2026-07 conditional novelty 7.0 of 10

    High reward in sparse RL does not imply latent-state recovery; a hidden-DFA instrument separates perception from planning gaps and flags group-language structure as a pre-training warning.

  4. Learning State-Tracking from Code Using Linear RNNs

    cs.LG 2026-02 unverdicted novelty 7.0 of 10

    Linear RNNs with negative eigenvalues track permutation state from REPL traces under next-token prediction, but probabilistic state-tracking with partial reveals forces exponential belief decay without nonlinear renor...

  5. Unraveling Syntax: Language Modeling and the Substructure of Grammars

    cs.CL 2025-10 conditional novelty 6.0 of 10

    Language-modeling loss decomposes linearly over the sub-grammars of a probabilistic context-free grammar, and models learn these sub-grammars in parallel rather than in stages.

  6. Rethinking Memorization Measures and their Implications in Large Language Models

    cs.LG 2025-07 conditional novelty 6.0 of 10

    Contextual memorization, defined by comparing a string's training loss against the best loss without training on that string, is stricter than counterfactual memorization and suggests that zero-memorization optimal le...

  7. How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias

    cs.LG 2025-05 conditional novelty 6.0 of 10

    A one-layer transformer trained on even pairs provably passes through a fast attention-growth phase into a slow max-margin phase, and with chain-of-thought the same model can solve parity checking.

  8. A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization

    cs.LG 2025-06 conditional novelty 5.0 of 10

    Single-layer linear self-attention can represent, train on, and length-generalize pairwise interaction functions under data-versatility and exact-realizability assumptions, and the paper introduces higher-order HyperA...

Reference graph

Works this paper leans on

42 extracted references · 37 canonical work pages · cited by 8 Pith papers

  1. [1]

    URL: " 'urlintro :=

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year eprint doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block STRINGS urlintro eprinturl eprintpr...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286

    work page Pith review arXiv 2020

  4. [4]

    Rina Cohen and Janusz Brzozowski. 1971. https://doi.org/10.1016/S0022-0000(71)80003-X Dot-depth of star-free events. Journal of Computer and System Sciences, 5:1--16

    work page doi:10.1016/s0022-0000(71)80003-x 1971

  5. [5]

    Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019. https://doi.org/10.18653/v1/P19-1285 Transformer- XL : Attentive language models beyond a fixed-length context . In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978--2988, Florence, Italy. Association for Compu...

    work page doi:10.18653/v1/p19-1285 2019

  6. [6]

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. https://doi.org/10.18653/v1/N19-1423 BERT : Pre-training of deep bidirectional transformers for language understanding . In Proceedings of the 2019 Conference of the North A merican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long a...

    work page doi:10.18653/v1/n19-1423 2019

  7. [7]

    Volker Diekert and Paul Gastin. 2008. First-order definable languages. In Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games, pages 261--306. Amsterdam University Press

    work page 2008

  8. [8]

    Patrick C Fischer, Albert R Meyer, and Arnold L Rosenberg. 1968. Counter machines and counter languages. Mathematical systems theory, 2(3):265--283

    work page 1968

Show all 42 references
  1. [9]

    Felix A Gers and E Schmidhuber. 2001. Lstm recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Neural Networks, 12(6):1333--1340

    2001

  2. [10]

    Michael Hahn. 2020. https://doi.org/10.1162/tacl\_a\_00306 Theoretical limitations of self-attention in neural sequence models . Transactions of the Association for Computational Linguistics, 8:156--171

    2020 doi

  3. [11]

    Sepp Hochreiter and J \"u rgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735--1780

    1997

  4. [12]

    Gerhard J \"a ger and James Rogers. 2012. Formal language theory: refining the chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956--1970

    2012

  5. [13]

    John F Kolen and Stefan C Kremer. 2001. A field guide to dynamical recurrent networks. John Wiley & Sons

    2001

  6. [14]

    Samuel A Korsky and Robert C Berwick. 2019. On the computational power of rnns. arXiv preprint arXiv:1906.06349

    2019 arXiv

  7. [15]

    Xuanqing Liu, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2020. Learning to encode position for transformer with continuous dynamical model. arXiv preprint arXiv:2003.09229

    2020 arXiv

  8. [16]

    Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692

    2019 arXiv

  9. [17]

    Robert McNaughton and Seymour A. Papert. 1971. Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press

    1971

  10. [18]

    William Merrill. 2019. https://doi.org/10.18653/v1/W19-3901 Sequential neural networks as automata . In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1--13, Florence. Association for Computational Linguistics

    2019 doi

  11. [19]

    William Merrill. 2020. On the linguistic capacity of real-time counter automata. arXiv preprint arXiv:2004.06866

    2020 arXiv

  12. [20]

    William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav. 2020. A formal hierarchy of rnn architectures. arXiv preprint arXiv:2004.08500

    2020 arXiv

  13. [21]

    Michalenko, Ameesh Shah, Abhinav Verma, Swarat Chaudhuri, and Ankit B

    Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Swarat Chaudhuri, and Ankit B. Patel. 2019. https://openreview.net/forum?id=H1zeHnA9KX Finite automata can be linearly decoded from language-recognizing RNN s . In International Conference on Learning Representations

    2019

  14. [22]

    Isabel Papadimitriou and Dan Jurafsky. 2020. Pretraining on non-linguistic structure as a tool for analyzing learning bias in language models. arXiv preprint arXiv:2004.14601

    2020 arXiv

  15. [23]

    Jorge P \'e rez, Javier Marinkovi \'c , and Pablo Barcel \'o . 2019. https://openreview.net/forum?id=HyGBdo0qFm On the turing completeness of modern neural network architectures . In International Conference on Learning Representations

    2019

  16. [24]

    Jean-Éric Pin. 2017. https://doi.org/10.1142/9789813148208_0008 The dot-depth hierarchy, 45 years later . In The Role of Theory in Computer Science, pages 177--201

    2017 doi

  17. [25]

    Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language understanding by generative pre-training. URL https://s3-us-west-2. amazonaws. com/openai-assets/researchcovers/languageunsupervised/language understanding paper. pdf

    2018

  18. [26]

    Emily Reif, Ann Yuan, Martin Wattenberg, Fernanda B Viegas, Andy Coenen, Adam Pearce, and Been Kim. 2019. Visualizing and measuring the geometry of bert. In Advances in Neural Information Processing Systems, pages 8592--8600

    2019

  19. [27]

    Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020. A primer in bertology: What we know about how bert works. arXiv preprint arXiv:2002.12327

    2020 arXiv

  20. [28]

    Luzi Sennhauser and Robert Berwick. 2018. https://doi.org/10.18653/v1/W18-5414 Evaluating the ability of LSTM s to learn context-free grammars . In Proceedings of the 2018 EMNLP Workshop B lackbox NLP : Analyzing and Interpreting Neural Networks for NLP , pages 115--124, Bruss...

    2018 doi

  21. [29]

    Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and C. Zhang. 2018. Disan: Directional self-attention network for rnn/cnn-free language understanding. In AAAI

    2018

  22. [30]

    Natalia Skachkova, Thomas Trost, and Dietrich Klakow. 2018. https://doi.org/10.18653/v1/W18-5425 Closing brackets with recurrent neural networks . In Proceedings of the 2018 EMNLP Workshop B lackbox NLP : Analyzing and Interpreting Neural Networks for NLP , pages 232--239, Bru...

    2018 doi

  23. [31]

    Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser Verlag, CHE

    1994

  24. [32]

    Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019 a . https://doi.org/10.18653/v1/W19-3905 LSTM networks can perform dynamic counting . In Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 44--54, Florence. As...

    2019 doi

  25. [33]

    Mirac Suzgun, Yonatan Belinkov, and Stuart M. Shieber. 2019 b . https://doi.org/10.7275/s02b-4d91 On evaluating the generalization of LSTM models in formal languages . In Proceedings of the Society for Computation in Linguistics ( SC i L ) 2019 , pages 277--286

    2019 doi

  26. [34]

    Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019. https://doi.org/10.18653/v1/D19-1443 Transformer dissection: An unified understanding for transformer ' s attention via the lens of kernel . In Proceedings of the 2019 Con...

    2019 doi

  27. [35]

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information processing systems, pages 5998--6008

    2017

  28. [36]

    Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. 2019. https://doi.org/10.18653/v1/P19-1580 Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned . In Proceedings of the 57th Annual Meeting of the Associatio...

    2019 doi

  29. [38]

    Qinglong Wang, Kaixuan Zhang, II Ororbia, G Alexander, Xinyu Xing, Xue Liu, and C Lee Giles. 2018 b . A comparative study of rule extraction for recurrent neural networks. arXiv preprint arXiv:1801.05420

    2018 arXiv

  30. [39]

    Alex Warstadt, Yu Cao, Ioana Grosu, Wei Peng, Hagen Blix, Yining Nie, Anna Alsop, Shikha Bordia, Haokun Liu, Alicia Parrish, Sheng-Fu Wang, Jason Phang, Anhad Mohananey, Phu Mon Htut, Paloma Jeretic, and Samuel R. Bowman. 2019. https://doi.org/10.18653/v1/D19-1286 Investigatin...

    2019 doi

  31. [40]

    Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. https://doi.org/10.18653/v1/P18-2117 On the practical computational power of finite precision RNN s for language recognition . In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2:...

    2018 doi

  32. [41]

    Gail Weiss, Yoav Goldberg, and Eran Yahav. 2019. http://papers.nips.cc/paper/9062-learning-deterministic-weighted-automata-with-queries-and-counterexamples.pdf Learning deterministic weighted automata with queries and counterexamples . In H. Wallach, H. Larochelle, A. Beygelzi...

    2019

  33. [42]

    Wong, Lidia S

    Baosong Yang, Longyue Wang, Derek F. Wong, Lidia S. Chao, and Zhaopeng Tu. 2019. https://doi.org/10.18653/v1/P19-1354 Assessing the ability of self-attention networks to learn word order . In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisti...

    2019 doi

  34. [43]

    Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. 2020. https://openreview.net/forum?id=ByxRM0Ntvr Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations

    2020

Pith tools

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