Chain of thought is the memory transformers lack

A transformer of fixed depth, run once over an input, has no memory that grows with the input. Every layer sees the whole sequence at once and passes a fixed-width vector per position to the next, and the number of layers does not change when the input gets longer. That is a stronger limitation than it sounds. It means the model cannot, in general, simulate a finite-state machine over an arbitrarily long string, which means it cannot recognise every regular language at every length, let alone match brackets or check a grammar, tasks that need a stack. Chain of thought is the workaround, and the theory of the last few years says exactly what kind of workaround it is: it writes the missing memory into the output, one token at a time, and the number of tokens written is a hard budget on what the model can compute.

The ladder

Merrill and Sabharwal's ICLR 2024 paper gives the result as a ladder with three rungs, indexed by how many intermediate tokens the model is allowed to generate before answering. With a logarithmic number of steps in the input length, the limits of a standard transformer move only slightly. With a linear number of steps, the model gains a clearly new ability: it can recognise every regular language, which is to say it can simulate any finite-state machine over the input, one token per state transition. And with a polynomial number of steps, a transformer with a generalised pre-norm recognises exactly the class of problems solvable in polynomial time. The characterisation is exact, which is rare in this area, and it says something specific about parsing.

Li, Liu, Zhou and Ma's companion result at the same conference gives the mechanism from the circuit side: a constant-depth transformer with constant-precision arithmetic and no chain of thought computes only what shallow parallel circuits compute, a class properly inside the one usually quoted, and a transformer that writes T intermediate tokens can compute anything a boolean circuit of size T can. Their framing is that chain of thought supplies inherently serial computation, and their experiments show accuracy on tasks that resist parallel evaluation, composing permutations, iterated squaring, evaluating a circuit, improving dramatically once the model is allowed to write its working out. The two papers say the same thing in two vocabularies. The transformer's forward pass is parallel and shallow. Serial memory has to be written down.

The written stack rule

For parsing the consequence is a rule I call the written stack rule: if a task needs memory that grows with the input, a transformer must emit that memory as tokens, and the number of emitted tokens is a hard budget on the computation. A finite-state machine needs one state's worth of memory, so a linear scratchpad, one token per input symbol, is enough, and that is the second rung. A pushdown automaton needs a stack whose depth can grow with the input, so the scratchpad has to hold the stack, and a stack that is pushed and popped over the input needs the transcript of every push and pop, which is still linear in the input for a single pass but with the stack's contents repeated at each step if the model cannot look back, and that is where the budget starts to matter.

The rule says what a scratchpad has to contain, which is more specific than "think step by step". For bracket matching, the scratchpad has to contain the stack, or at least its depth and the last unmatched symbol, after each input symbol; a scratchpad that writes only a running commentary without the stack state is not doing the computation, and a model that appears to match brackets from such a scratchpad is doing it from the forward pass, which the theory says will fail past some length. For grammar checking against a context-free grammar, the scratchpad has to contain whatever the parser's state is, which for a shift-reduce parser is a stack of partial constituents and for a CYK-style parser is a chart, and the chart is quadratic in the input, so a scratchpad that faithfully wrote it would need quadratically many tokens. That is the third rung, polynomial, and it is where the budget becomes a cost that shows up on the bill.

The budget also explains a pattern anyone who has used long reasoning traces has seen: the trace is mostly bookkeeping. A model matching brackets in its scratchpad writes the depth after every symbol, and most of those lines change nothing but are required, because a line skipped is a stack state the forward pass would have to hold on its own. That is not verbosity in the ordinary sense. It is the memory being written where the architecture can read it back, and the rule says a shorter trace that omits it is a trace that has quietly moved the work back into the part of the model that cannot do it.

What this means for neural parsing

My paper related CYK recognition to what a transformer constrained by a grammar can and cannot do, and the written stack rule is the bridge between the two halves. A grammar-constrained decoder masks tokens against a pushdown automaton that runs beside the model, outside it; the automaton holds the stack, and the model never has to. That is why constrained decoding works for structure at any length: the memory the transformer lacks is supplied by a separate machine. Take the automaton away and ask the model to enforce the grammar itself, and the rule applies: it can do so only by writing the stack into its output, and the amount it writes bounds the depth it can handle.

There is a practical corollary for anyone using chain of thought to get structure out of a model. Length of reasoning is not a knob to turn for quality; it is a memory allocation, and the task sets its size. A task that needs a stack of depth d needs a scratchpad that can hold depth d, and a token budget below that is not a slightly worse answer, it is a task the model cannot do. When a model with a short reasoning budget fails on long nested inputs and succeeds on short ones, the written stack rule says why, and the fix is either more tokens or an external automaton, which is what grammar-constrained decoding is.

What the rule does not say

The rule is a statement about what must be written, not about what will be. A model allowed a linear scratchpad can recognise regular languages; nothing guarantees a given trained model uses its scratchpad that way, and the experiments in both papers are about models trained to. The theory draws the ceiling, and the ceiling is the useful part: it says which tasks are impossible without the written memory, at any model size, for reasons that no scaling will change, and it says how much memory each class of task needs. For a parser, the memory is a stack, the stack has to be written or held by a machine beside the model, and the tokens it costs are not overhead. They are the computation.