Context-free Recognition with Transformers

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 $\mathcal{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 $\mathcal{O}(\log(N))$ looping layers and $\mathcal{O}(N^6)$ padding symbols can recognize all CFLs. However, training and inference with $\mathcal{O}(N^6)$ 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 $\mathcal{O}(N^3)$ 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.

Transformers, the networks behind today’s language and coding models, excel at texts that follow grammatical rules, like nested clauses or matched brackets in code. This structure is captured by what computer scientists call context-free grammars. Yet, there has been no clear theory of how a transformer could actually verify that an input obeys a grammar’s rules—and theory even suggests a standard fixed-size transformer cannot. This paper closes this gap via two modest changes to the standard transformer architecture. The first is the transformer’s depth: the number of layers grows with the input length. The second is the transformer’s memory space: we append scratch-pad slots to the input that serve as memory. Together, we show these changes enable transformers to robustly understand grammatical syntax. Precisely, we show a transformer can process an arbitrary grammar efficiently, at the cost of a large scratch-pad. Conveniently, the grammars we typically use (such as the ones that describe code) are what we call unambiguous—where a unique set of grammatical rules leads to text. We show that for unambiguous grammars, transformers can process sentences even more efficiently. This aligns with what we see in practice: modern language models sometimes struggle to understand ambiguous sentences in natural language, but seem exceedingly proficient on coding tasks. Our experiments vet our theory: transformers with more depth and space seem to better process grammatical syntax. Overall, our paper provides exact ways in which a transformer can process the syntax of some language, whether it be English or Python.