Context-Free Recognition with Transformers
Not on the map. Why?
Abstract (arXiv)
Transformers excel empirically on tasks that process well-formed inputs according to some grammar, such as natural language and code. However, it remains unclear how they can process grammatical syntax. In fact, under standard complexity conjectures, standard transformers cannot recognize context-free languages (CFLs), a canonical formalism to describe syntax, or even regular languages, a subclass of CFLs. Past work has shown that O(log(N)) looping layers (w.r.t. input length N) allow transformers to recognize regular languages, but the question of context-free recognition with looped transformers remained open. In this work, we show that looped transformers with O(log(N)) looping layers and O(N6) padding symbols can recognize all CFLs. However, training and inference with O(N6) padding symbols is potentially impractical. Fortunately, we show that, for natural subclasses such as unambiguous CFLs, the recognition problem on transformers becomes more tractable, requiring O(N3) padding. Empirically, looped and padded transformers perform better than fixed-depth transformers in recognizing CFLs. Overall, our results shed light on the intricacy of CFL recognition by transformers: while general recognition may require an intractable amount of padding, natural constraints such as unambiguity yield efficient recognition algorithms.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 27 of its 59 references that are in the map. First posted on arXiv 5 Jan 2026.
Builds on
27 of 59 references.
References · 27
- 2023Large Language Modelscited by 774
- 2024A Survey on Large Language Models for Code Generationcited by 646
- 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
- 2021Thinking Like Transformerscited by 182
- 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
- 2023We're Afraid Language Models Aren't Modeling Ambiguitycited by 124
- 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
- 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
- 2024Why are Sensitive Functions Hard for Transformers?cited by 74
- 2022A Logic for Expressing Log-Precision Transformerscited by 67
- 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
- 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
15 more
- 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
- 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 44
- 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
- 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
- 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 37
- 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 36
- 2025(How) Do Language Models Track State?cited by 31
- 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
- 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
- 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
- 2025Exact Expressive Power of Transformers with Paddingcited by 19
- 2022Probing for Constituency Structure in Neural Language Modelscited by 13
- 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 10
- 2025Unraveling Syntax: Language Modeling and the Substructure of Grammarscited by 4
- 2023Approximating CKY with Transformerscited by 3
Built on by
Citing papers per year: 2026: 3.
3 papers.