Why do standard transformers fail to encode recursive structure in their hidden states?

This reads the question as asking about a limit baked into the transformer's shape, not just a quirk of training: why don't hidden states naturally hold the kind of nested, stack-like structure that recursion (balanced brackets, grammar trees, multi-step plans) demands? The corpus points at two answers that pull in different directions.

The first is a hard ceiling. A standard transformer runs a fixed number of layers regardless of how deep the problem nests, which caps the 'computational depth' it can express — formally the AC0/TC0 complexity classes. The Hierarchical Reasoning Model makes this concrete: by coupling slow planning with fast computation across two timescales, a 27M-parameter recurrent model solves Sudoku and mazes where chain-of-thought transformers fail outright Can recurrent hierarchies achieve reasoning that transformers cannot?. Looping the same parameters repeatedly buys back some of the missing depth and unlocks compositional generalization vanilla transformers can't reach Can looped transformers generalize to unseen knowledge combinations?. So part of the failure is simply that recursion wants variable depth and the architecture supplies a constant.

The second answer is subtler and more damning: even within their depth budget, transformers tend not to *learn* recursive rules — they memorize the shapes that recursion would have produced. One study shows compositional reasoning in transformers collapses into 'linearized subgraph matching': the model stitches together computation paths seen in training and breaks badly on genuinely novel compositions, with errors compounding step by step Do transformers actually learn systematic compositional reasoning?. That's the opposite of holding a recursive structure in state — it's pattern-completion wearing recursion's clothes. The fix that works best for syntax is to *give* the model the missing machinery: a pushdown layer with an explicit stack tape yields 3–5x more sample-efficient syntactic generalization, which tells you the recursive bookkeeping was the bottleneck, not raw capacity Can explicit stack tracking improve how transformers learn recursive syntax?.

Here's the twist worth sitting with: the failure may be in the *learned weights*, not the architecture's reach. A single finite transformer provably exists that can compute any computable function given the right prompt — Turing-complete in principle — yet ordinary training almost never produces a model that implements arbitrary programs that way Can a single transformer become universally programmable through prompts?. The capacity is there; gradient descent just doesn't steer toward it. And when models do reach a clean internal organization, it's often through a sharp grokking transition rather than smooth learning Can looped transformers generalize to unseen knowledge combinations? — and two models with identical accuracy can have wildly different internal structure, one robust and one fractured, with the difference invisible to standard metrics Can models be smart without organized internal structure?.

What you didn't know you wanted to know: there's a counter-current suggesting transformers aren't as structureless as the pessimistic readings imply. Pruning experiments find networks spontaneously carve compositional tasks into isolated modular subnetworks, each cleanly ablatable Do neural networks naturally learn modular compositional structure?, and transformers can bootstrap themselves from 10-digit to 100-digit addition by retraining on their own filtered-correct outputs Can transformers improve exponentially by learning from their own correct solutions?. So the honest synthesis is: standard transformers don't fail to encode recursion because they *can't* — they fail because fixed depth caps it, training rarely finds the recursive solution over the memorized one, and the metrics we use can't tell the two apart. Add explicit stack/recurrence machinery and much of the failure evaporates.