# Context-Free Recognition with Transformers

arXiv: https://arxiv.org/abs/2601.01754 · HTML: https://mlsanity.com/paper/2601.01754/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 59 references that are in the map.
- First posted on arXiv 5 Jan 2026.

## Builds on (most cited first, 27 of 27)

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [We're Afraid Language Models Aren't Modeling Ambiguity](https://mlsanity.com/paper/2304.14399/) (2023)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent](https://mlsanity.com/paper/2010.09697/) (2020)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases](https://mlsanity.com/paper/2502.19249/) (2025)
- [(How) Do Language Models Track State?](https://mlsanity.com/paper/2503.02854/) (2025)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Exact Expressive Power of Transformers with Padding](https://mlsanity.com/paper/2505.18948/) (2025)
- [Probing for Constituency Structure in Neural Language Models](https://mlsanity.com/paper/2204.06201/) (2022)
- [How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias](https://mlsanity.com/paper/2505.00926/) (2025)
- [Unraveling Syntax: Language Modeling and the Substructure of Grammars](https://mlsanity.com/paper/2510.02524/) (2025)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)

## Built on by (most cited first, 4 of 4)

- [Bridging the Gap Between Latent and Explicit Reasoning with Looped Transformers](https://mlsanity.com/paper/2606.31779/) (2026)
- [Scale Dependent Data Duplication](https://mlsanity.com/paper/2603.06603/) (2026)
- [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026)
- [Constraint-Aware Training](https://mlsanity.com/paper/2610.02909/) (2026)

## 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.