What Neural Language Models Can Actually Compute

The previous lessons built a ladder of computational power and pinned language to it: morphology is regular, syntax is mildly context-sensitive. Modern language models are not written as grammars, but they are still computational devices, so the natural question is where they sit on the same ladder.

The way to ask it precisely is through formal language recognition. Take a synthetic language defined by a clean rule, such as strings of balanced brackets, or strings of the form a-to-the-n b-to-the-n, and test whether an architecture can learn to recognize it and, crucially, generalize to longer strings than it was trained on.

Length generalization is the sharp test. Any model can memorize a finite training set. Only a model that has actually captured the underlying rule keeps succeeding as the strings grow. This reframes a vague question, how smart is this network, into a precise one with a known answer.

Start with recurrent neural networks, which process a sequence one token at a time while carrying a hidden state, exactly the shape of a finite automaton reading input left to right.

In theory, with unbounded numerical precision, an RNN is extremely powerful. But real networks run in finite precision, and that changes the picture sharply. Gail Weiss, Yoav Goldberg, and Eran Yahav argued in their 2018 paper "On the Practical Computational Power of Finite Precision RNNs" that the picture depends on the cell: an LSTM can use its gates to maintain a counter and so recognize some counting patterns, while a simple GRU or basic RNN is closer to purely finite-state.

The practical takeaway is that a finite-precision recurrent network has a bounded memory, so like a finite automaton it eventually loses track of deep nested structure. Its natural home is low on the hierarchy.

Transformers, the architecture behind modern large language models, look far more powerful than recurrent networks. Attention lets every position see every other position directly, with no sequential bottleneck. The intuition is that this should place them high on the hierarchy.

The theory says the opposite, and this is the lesson's central surprise. William Merrill and Ashish Sabharwal, in their 2023 paper "The Parallelism Tradeoff: Limitations of Log-Precision Transformers", proved that a transformer with realistic finite precision can be simulated by a family of very shallow, highly parallel circuits, formally the class known as TC-zero.

What that means concretely is that a fixed-depth transformer cannot perform inherently sequential computation. Problems that require a long chain of dependent steps, where each step needs the previous one's result, are beyond it in a single forward pass, because the whole computation has only constant depth no matter how long the input is.

The name of Merrill and Sabharwal's paper points at the mechanism: a parallelism tradeoff. The very feature that makes transformers fast to train is what limits them.

A transformer processes all positions at once, in parallel, which is wonderful for hardware and terrible for problems that are irreducibly sequential. Some computations simply cannot be flattened: to know the state of a system after a long series of updates, you have to apply them in order, and no amount of parallel hardware collapses that chain. Determining whether a long string of brackets is balanced, or tracking a variable through many assignments, has this character.

So the strength and the weakness are the same property. Attention buys global, parallel access at the cost of sequential depth, and the class TC-zero is the precise statement of what falls outside its reach. A recurrent network, being sequential, does not share this particular limitation, though finite precision limits it in other ways.

These theoretical classes make empirical predictions, and a large study tested them directly. Gregoire Deletang and colleagues at DeepMind, in the 2023 paper "Neural Networks and the Chomsky Hierarchy", trained many architectures on synthetic tasks drawn from each rung of the hierarchy and measured length generalization.

The headline result is that a network's formal class predicts what it learns. Models generalized on tasks at or below their theoretical level and failed, often completely, above it, even with abundant data and training. Grouping tasks by the Chomsky hierarchy explained the successes and failures that raw capacity did not.

They also confirmed the fix the theory suggests. Bolting a differentiable stack or tape onto a network, giving it the memory the higher rungs require, let it climb: architectures that failed a task solved it once equipped with the right kind of memory. Theory predicted the failure, and theory predicted the remedy.

This theory quietly explains one of the most useful practical tricks with language models: chain-of-thought prompting, where the model is asked to write out intermediate steps before its answer.

Recall the limit. A single forward pass has constant depth, so it cannot carry out a long sequential computation internally. But when the model writes an intermediate result into its output and then reads its own output back as it generates the next token, it is using the generated text as external, rewritable memory. Each step gets a fresh forward pass, and the chain of steps unrolls the sequential computation the single pass could not do.

In effect, chain-of-thought lets a transformer trade tokens for depth, escaping the TC-zero ceiling by spreading a computation across many passes instead of one. A limitation that sounds purely academic turns out to explain why letting a model think step by step measurably extends what it can solve.

Pulling the results together, the architectures line up on the same ladder the grammars did.

The entries are approximate and depend on precise assumptions about precision and attention, which is an active research area rather than a closed book. But the qualitative message is firm and useful. These are not universal computers that can learn anything given data. Each has a formal ceiling, that ceiling predicts which structures it captures, and changing the ceiling requires changing the architecture, not the dataset.

This is the meeting point the first lesson promised. The formal tradition, born from Chomsky's grammars in the 1950s, and the statistical tradition, which produced today's neural language models, are not rivals but two views of one object.

The formal side supplies the measuring instrument. It tells you the computational class of an architecture, and therefore, before you train anything, which patterns it can represent and which are out of reach no matter the data. The statistical side supplies the systems that actually process language at scale. Reading them through the hierarchy is what turns a working black box into something understood.

That synthesis is much of what a modern computational linguist like Ryan Cotterell pursues: not just building language models, but proving what they can and cannot compute. The oldest tool in the field, the Chomsky hierarchy, turns out to be the sharpest lens on its newest artifacts.