Can Transformers Learn to Solve Problems Recursively?

ArXiv: 2305.14699

🎯 Pitch

Transformers trained to emulate structurally recursive functions do not learn the true recursion—instead, they discover a shortcut driven by a dedicated "recursion head." By reverse-engineering this shortcut, the authors correctly predict 91% of the model's failures, proving that these learned algorithms are systematic but brittle, and fail predictably when recursion depth exceeds the training distribution.

1. Executive Summary

This paper studies how small encoder-decoder transformer models learn to emulate the behavior of structurally recursive functions—algorithms that call themselves on smaller substructures—from input-output examples, using two representative tasks on the MATH benchmark: binary successor (a single-recursive-subcase function over binary natural numbers) and tree traversal (a dual-recursive-subcase function over binary trees). The authors perform mechanistic interpretability to reverse-engineer the “shortcut” algorithms the models learn, uncovering a recursion head (an attention head that specializes to recursive cases, such as attending to previously generated X1 tokens to demarcate recursive from non-recursive segments), and demonstrate through perturbation analysis that these shortcuts reliably succeed on in-distribution inputs but fail predictably on out-of-distribution recursion depths. By reconstructing the learned algorithm for the binary successor task, the authors correctly predict 91% of failure cases—establishing that transformer-learned recursive approximations are systematic and interpretable, but that their generalization is bounded by the specific positional-encoding and token-copying shortcuts the models discover during training.

2. Context and Motivation

The Core Problem: Do Transformers Model Program Semantics or Just Syntax?

The fundamental question driving this paper is deceptively simple: when a transformer learns to perform a computational task from input-output examples, does it learn something resembling the true recursive algorithm, or does it learn a non-recursive shortcut that happens to work on the training distribution? This matters because structural recursion—functions defined to call themselves on strictly smaller substructures—is a cornerstone of how programs and formal proofs are written. If transformers cannot faithfully model recursive semantics, it sets a hard boundary on their reliability for programming languages tasks.

The paper frames this as a question about semantic versus syntactic modeling. A model that has learned only "syntax" might exploit superficial patterns in the training data (e.g., memorizing specific input-output pairs, or learning to count tokens rather than understand recursive case decomposition). A model that has learned "semantics" would internally implement something analogous to pattern matching, recursive calls, and base-case handling—the actual computational structure of the function. The paper's goal is to determine which of these actually happens, and to characterize precisely where and why the learned approximations break.

Why This Problem Matters

The significance spans both practical engineering and theoretical understanding:

Practical stakes for neural program synthesis and verification. In recent years, transformer-based large language models have become central to tools that synthesize programs (Chen et al., 2021; Chowdhery et al., 2022), repair buggy code (Gupta et al., 2017; Saha et al., 2017), and even formally verify correctness (Agrawal et al., 2023; First and Brun, 2022; First et al., 2023). These tools rest on the assumption that the underlying model has some capacity to reason about what programs mean and how they behave, not just what they look like textually. The paper cites specific evidence that this assumption is questionable:

"State-of-the-art language models still rely on tricks like chain of thought prompting and scratchpadding to approximate program semantics. Even models trained on code often need to be finetuned to solve specific tasks instead of used in a multitask fashion."

If transformers fundamentally learn only shallow shortcuts rather than compositional algorithmic reasoning, then these models' reliability on unseen inputs—precisely the inputs that matter in verification and synthesis, where the correct answer is not known in advance—is inherently limited.

Specific relevance to structural recursion. The paper emphasizes that structural recursion is "at the heart of tasks on which symbolic tools currently outperform neural models, like inferring semantic relations between datatypes and emulating program behavior" (Section 1). This is a deliberate choice: structural recursion is the class of programs where the symbolic-vs-neural performance gap is largest. If transformers cannot learn even this restricted, well-behaved class of functions, then the gap is fundamental rather than merely a consequence of insufficient scale or data.

Foundations for prompt engineering. The paper observes that techniques like chain-of-thought prompting (Wei et al., 2022) and scratchpad reasoning (Nye et al., 2021) improve transformer performance on recursive tasks, but why they help is poorly understood. By reverse-engineering what happens without these techniques—what shortcuts the model discovers on its own—the paper aims to provide a baseline that explains when and why these interventions are necessary.

Where Prior Approaches Fall Short

The paper identifies several gaps in the existing literature that motivate its specific approach:

1. Mechanistic interpretability has not been applied to recursive program semantics. Prior work on understanding transformers' internal mechanisms has focused on domains like modular arithmetic (Nanda et al., 2023; Chughtai et al., 2023), language modeling phenomena like indirect object identification (Wang et al., 2022), factual association (Meng et al., 2023), and formal language recognition (Liu et al., 2022; Delétang et al., 2022). None of this work has examined how transformers approximate structurally recursive functions—a class of algorithms with a distinctive case-decomposition structure that makes it especially amenable to reverse engineering. The paper positions itself as extending mechanistic interpretability to this new domain.

2. Prior work on transformers and recursion focuses on capability boundaries, not learned mechanisms. Several papers have studied whether transformers can process hierarchical structures at all—for example, Yao et al. (2021) showed that self-attention networks can process bounded hierarchical languages, and theoretical work (Pérez et al., 2021; Hahn, 2020) has characterized expressiveness limitations. But these works ask what transformers can compute in principle, not how they actually compute it when trained, and not why their learned solutions fail on specific out-of-distribution inputs.

3. Program synthesis research treats neural models as black boxes. The program and proof synthesis literature (Gulwani et al., 2017; Lee and Cho, 2023; Miltner et al., 2019; Ringer, 2021; Ringer et al., 2021) has developed strong symbolic methods for synthesizing structurally recursive functions from examples. Recent work has incorporated neural components (Chaudhuri et al., 2021; Chen et al., 2021), but typically treats the neural model as a black-box proposal generator whose outputs are verified by symbolic tools. There has been almost no investigation of what algorithms the neural components themselves learn, which limits understanding of when and why the neural-symbolic combination succeeds or fails.

4. The gap between "can learn" and "does learn" is underexplored. Much theoretical work establishes transformers as Turing-complete (Pérez et al., 2019, 2021) or capable of expressing certain computations in principle. But capability in the expressiveness sense does not imply that gradient descent will discover the corresponding solution. The paper is interested precisely in this gap: given that a transformer could implement a recursive stack machine in its computations, does it actually discover something like that, or does it find a simpler shortcut? The answer has direct bearing on whether scaling model size and data will eventually close the neural-symbolic gap, or whether fundamental architectural innovations are needed.

How This Paper Positions Itself

The paper makes several deliberate scoping decisions that define its contribution relative to existing work:

Small, interpretable models over large black boxes. Rather than probing the behavior of a large pretrained language model (e.g., by prompting it with binary successor examples), the paper trains small encoder-decoder transformers from scratch on carefully controlled synthetic tasks. This allows full access to all weights, activations, and attention patterns, enabling the kind of detailed mechanism reconstruction that would be infeasible with a production-scale model. The trade-off is that the findings may not transfer directly to large pretrained models—a limitation the paper explicitly acknowledges (Section 7: "our main focus was on toy transformer models trained from scratch, while we deferred the understanding of large pretrained language models to future work").

Two tasks with different structural complexity. The binary successor function has one recursive subcase (when the least significant bit is X1), making it a minimal testbed for whether a model can learn to "recurse" at all. The tree traversal has two recursive subcases (left and right subtrees), making it representative of the tree-structured recursion that dominates symbolic search procedures for programs, games, and proofs. By studying both, the paper can distinguish between phenomena specific to linear recursion and those that emerge with true tree-structured recursion.

Focus on failure modes, not just success. The paper's emphasis is unusual: rather than maximizing accuracy or demonstrating that transformers "can" solve these tasks, it deliberately studies the ways in which the learned algorithms are wrong. This aligns with the broader mechanistic interpretability agenda of understanding model limitations from the inside, not just benchmarking them from the outside. The paper's central methodological contribution is showing that by reconstructing the learned algorithm, one can predict which inputs the model will fail on—and in the binary successor case, predict 91% of failures.

Abstract State Machines as a unifying framework. The paper introduces Abstract State Machines (Gurevich, 1995) as a formal computation model that can describe both the ground-truth recursive function and the transformer's learned approximation at a shared level of abstraction (Section 4). This is a deliberate choice to avoid the mismatch that would arise from comparing a high-level recursive description against low-level transformer operations. ASMs allow the paper to analyze the transformer's behavior as a sequential program with conditionals ("if the sequence is complete, generate [EOS]") and to ask whether that program correctly approximates the recursive target.

A step toward understanding why prompt engineering works. The paper explicitly positions its findings as groundwork for later understanding chain-of-thought and scratchpad reasoning. The atomic subtree reduction tasks for tree traversal (Section 3.2) are directly inspired by chain-of-thought decomposition: rather than training the model to produce the full traversal output at once, the paper trains it to produce intermediate reduction steps. By studying which reduction depths the model can handle and where the learned shortcuts break, the paper aims to illuminate why breaking computation into steps helps—a question that prior work on chain-of-thought has not answered mechanistically.

In summary, the paper occupies a unique intersection: it applies mechanistic interpretability techniques to program semantics tasks, with a deliberate focus on characterizing learned shortcuts and predicting their failure boundaries. It does not propose a new architecture or training method; instead, it provides a detailed empirical account of what happens when a standard transformer is asked to learn structural recursion, with the goal of informing future work on both neural architectures and hybrid neural-symbolic systems.

3. Technical Approach

3.1 Reader orientation (approachable technical breakdown)

This paper builds a set of controlled experiments where small encoder-decoder transformers are trained from scratch on synthetic sequence-to-sequence tasks that require emulating structurally recursive functions. The core problem is determining whether transformers learn genuine recursive algorithms or discover brittle non-recursive shortcuts, and the solution takes the form of a mechanistic interpretability pipeline: train a model → visualize its attention patterns to form hypotheses → perturb its inputs and internal activations to test causal mechanisms → reconstruct the learned algorithm as pseudocode → use that reconstruction to predict exactly which out-of-distribution inputs will cause failures.

3.2 Big-picture architecture (diagram in words)

The system has four major components:

1. Task Definition Module — specifies an inductive datatype (e.g., binary natural numbers, binary trees), a recursive function over that datatype (successor, inorder/preorder traversal), and an input-output pair generation procedure that produces training examples by enumerating datatype instances and computing the function.
2. Transformer Model (Encoder-Decoder) — a small, from-scratch transformer (2 encoder layers, 2 decoder layers, hidden dimension 128, 2 attention heads per layer) trained via teacher forcing on the generated input-output pairs to approximate the recursive function.
3. Mechanistic Analysis Toolkit — a suite of interpretability techniques including attention map visualization, counterfactual patching (replacing activations from one forward pass with those from another), and perturbation analysis (mutating tokens or swapping positional encodings on the fly during decoding) to reverse-engineer the learned algorithm.
4. Algorithm Reconstruction and Failure Prediction — the process of translating observed attention patterns and perturbation responses into explicit pseudocode for the learned algorithm, then using that pseudocode to mechanically derive the set of inputs on which the algorithm diverges from the ground-truth function.

Information flows as follows: the task definition module generates training data → the transformer is trained to map input sequences to output sequences → attention maps are collected from the trained model and visually inspected to identify "recursion heads" and other specialized components → perturbation experiments causally validate which attention patterns actually control behavior → the reconstructed algorithm is formalized, and its failure modes are compared against the model's actual test errors to quantify predictability.

3.3 Roadmap for the deep dive

• First, the task construction methodology (Section 3.1–3.2 in the paper): how the authors choose inductive datatypes, represent recursive functions, and generate training examples — since the entire analysis depends on having ground-truth semantics against which the learned shortcuts can be compared.
• Second, the transformer architecture and training configuration: model size, positional encoding, learning rate schedule, and the "random padding" extrapolation trick, because these design choices directly shape which shortcuts are learnable.
• Third, the Abstract State Machine (ASM) framework (Section 4): the formal model the authors use to reason about both the ground-truth recursion and the transformer's learned approximation at a shared level of abstraction.
• Fourth, the attention map visualization methodology: how the authors identify recursion heads and case-differentiation heads in encoder self-attention, decoder self-attention, and cross-attention.
• Fifth, the perturbation analysis methodology (Section 5.1.2): the specific manipulations applied to tokens and positional encodings, and how the model's response reveals the learned algorithm's control flow.
• Sixth, the counterfactual patching methodology (Section 5.2): how activations are swapped between forward passes to identify causally important attention heads for the tree traversal task.
• Seventh, the algorithm reconstruction and failure prediction methodology: the process of translating empirical observations into executable pseudocode, and the validation that reconstructed algorithms predict actual failure cases.

3.4 Detailed, sentence-based technical breakdown

This is fundamentally a mechanistic interpretability paper whose core idea is that small transformers trained to emulate recursive functions learn interpretable, systematic shortcut algorithms rather than genuine recursion, and that reconstructing those shortcuts allows precise prediction of generalization failures. The technical contribution is the methodology itself: a pipeline of attention analysis, perturbation experiments, and pseudocode reconstruction applied to a novel domain (program semantics).

Task Construction: Choosing Datatypes and Functions That Isolate Recursion

The central design challenge is constructing tasks that (1) require structural recursion in their ground-truth implementation, (2) have unambiguous correctness so model outputs can be graded exactly, and (3) use novel symbols to eliminate any possibility that the model is exploiting pre-trained semantic associations. The paper addresses all three through its choice of inductive datatypes.

Inductive datatypes as the substrate. The paper uses datatypes defined in the style of Coq (a proof assistant), where every instance is constructed from a fixed set of base-case and inductive-case constructors. This means the entire meaning of the datatype is intrinsic to its construction rules — there is no external semantics for the model to exploit. For example, binary positive natural numbers are defined as:

Inductive bin_pos :=
| 01 : bin_pos                  (* base case: the number one *)
| XO : ∀(b : bin_pos), bin_pos  (* inductive case: shift left *)
| X1 : ∀(b : bin_pos), bin_pos. (* inductive case: shift left and increment *)

A binary number like four is represented as XO XO 01 (read right-to-left: 01 shifted left twice gives binary 100). The symbols XO and X1 have no pre-existing meaning to the model — they are arbitrary tokens whose semantics are entirely determined by the input-output examples.

Why this matters for the research question. If the model were trained on "natural number successor" using Arabic numerals (e.g., 123 → 124), it could potentially succeed by learning digit-wise arithmetic rules that it acquired during pretraining, or by rote memorization of common numbers. By using a novel encoding with novel tokens, the paper ensures that any systematic behavior the model exhibits must have been learned from the task-specific training data. The Coq-style inductive representation also makes the recursive structure explicit in the syntax: whether a given input is a base case (01) or an inductive case (XO b or X1 b) is directly visible from the first token.

The binary successor function. The target function s (successor on binary positive naturals) is defined by structural pattern matching over the three cases (Section 3.1):

Fixpoint s n :=
  match n with
  | 01 => XO 01           (* base: 1 → 2 *)
  | XO b => X1 b          (* LSB zero: flip it *)
  | X1 b => XO (s b)      (* LSB one: recurse and shift *)
  end.

The paper emphasizes that this function is significant because it "captures the essence of what it means to adapt functions and proofs defined over the unary peano natural numbers so that they instead are defined over binary natural numbers" (Section 3.1). More concretely, it is the minimal example of a recursive function that is structurally interesting — the recursion depth depends on the input's trailing X1 count — yet simple enough that its learned approximation can be fully reverse-engineered.

Ordering matters: natural vs. reverse. The paper trains separate models on two input representations: natural order (most significant bit first, e.g., X1 XO 01 for three) and reverse order (least significant bit first, e.g., 01 XO X1). In the natural order, the recursive case is determined by the last bit (LSB), which the model must look ahead to find. In the reverse order, the recursive case is determined by the first bit, which is immediately available. This choice is deliberate: the two orders require qualitatively different algorithms, and comparing them reveals how the model's learned strategy adapts to the input structure.

The tree traversal tasks. For the second task, the paper uses binary trees with character values at nodes (Section 3.2). The inductive definition is:

Inductive tree :=
| Leaf
| Branch (v : char) (l r : tree).

A tree Branch 'a' (Branch 'c' Leaf Leaf) (Branch 't' Leaf Leaf) has 'a' at the root, 'c' in a left child, and 't' in a right child. The model is trained to produce the output of traversals:

• Preorder: visit the node, then left subtree, then right subtree — output a c t.
• Inorder: visit left subtree, then the node, then right subtree — output c a t.

Unlike the binary successor (which has linear recursive structure), tree traversal has branching recursion — each recursive call fans out to two subcalls. This tests whether the model can handle non-sequential recursive decomposition.

Atomic reduction subtasks. The paper decomposes the full traversal into partial reduction tasks, inspired by chain-of-thought reasoning. Rather than training the model to output the final traversal result directly, the paper trains variants to output the tree after one, two, or three reduction steps. For inorder traversal, a reduction step is defined as selecting the Branch case and substituting:

inorder (Branch 'a' (Branch 'c' Leaf Leaf) (Branch 't' Leaf Leaf))
→ (inorder (Branch 'c' Leaf Leaf)) ++ ['a'] ++ (inorder (Branch 't' Leaf Leaf))

This is a "one-step unroll." The paper introduces an UNROLL[...] wrapper to mark subexpressions that have been reduced. By training models on different numbers of unroll steps (1, 2, 3, or full traversal), the paper can identify at which point the model's learned shortcuts break down.

Training data generation. For binary successor, the paper generates input-output pairs by enumerating binary strings from 1 up to a specified maximum (e.g., 131,072, corresponding to 17-bit strings), computing s(n) for each, and pairing the input representation with the output representation. The distribution of recursion depths in the training data is non-uniform, because it follows the natural occurrence frequency of trailing X1 sequences. For tree traversal, the train/test split is by tree structure rather than by value — the model is tested on unseen tree topologies, not just unseen character values in known topologies. This tests generalization to new recursive patterns rather than mere memorization.

Model Architecture and Training Configuration

The paper makes specific architectural and training choices that are motivated by the goal of interpretability rather than maximum performance.

Architecture: encoder-decoder transformer. After preliminary experiments (Appendix E) comparing encoder-only, decoder-only, and encoder-decoder architectures on a string reversal extrapolation task, the authors selected encoder-decoder because it exhibited the best extrapolation to lengths beyond training. On the string reversal task with training lengths 10–37, the encoder-decoder model maintained accuracy above 70% even at 14 tokens beyond the training maximum, while encoder-only and decoder-only performance dropped precipitously (Figure 18). The paper attributes this to the encoder-decoder's natural decomposition of the task: the encoder processes the full input and identifies important positions (start of recursion, end of sequence), while the decoder generates outputs autoregressively conditioned on those encoder signals.

The specific configuration (Appendix A.1) is:

"We experimented with encoder-decoder transformer models with 2 encoder layers, 2 decoder layers, a hidden dimension of 128, and 2 heads."

This is deliberately small — the total parameter count is not stated explicitly, but with hidden dimension 128, feed-forward dimension (presumably 4× or 512 for standard transformer), 2 layers each, and embedding matrices, it is likely under 1 million parameters. The small size is essential for two reasons: first, it makes attention maps tractable to inspect visually (with only 2 heads per layer, each head's function can be characterized distinctly); second, it forces the model to learn a compact representation, which limits the space of possible algorithms and facilitates reconstruction.

Sinusoidal positional encoding. The paper uses the standard sinusoidal positional encoding from Vaswani et al. (2017). This is a critical detail because the learned algorithms — especially in the natural order binary successor task — depend heavily on the model's ability to compare positional encodings rather than token content. The sinusoidal encoding makes positional distances and comparisons computable via dot-product attention, which the model exploits to identify specific positions (start of recursion, end of sequence) regardless of content.

Random padding for extrapolation. A key methodological innovation is the training-time augmentation (Appendix A.1):

"In order to address the inherent limitation of transformers in generating longer sequences beyond their training exposure, and to explore whether the learned algorithms in transformers can extrapolate, we implemented a straightforward approach inspired by previous research. This involved introducing a simple mechanism where we randomly adjust the positional encoding by adding random lengths of padding to the inputs."

This means that during training, input sequences are sometimes prepended with random-length padding tokens, shifting the positional encodings of the actual content tokens. The decoder must learn to generate the correct output (including the padding) at the shifted positions. The rationale is that this prevents the model from overfitting to specific absolute positions and forces it to rely on relative positional relationships — precisely the kind of information that would be needed for genuine recursive computation.

Learning rate schedule. The paper follows the original transformer learning rate schedule (Vaswani et al., 2017) with a significant experimental variable (Section 5.1.4):

$\alpha = C \cdot d^{-\frac{1}{2}} \cdot \min\{s^{-\frac{1}{2}}, s \cdot S_w^{-\frac{3}{2}}\}$

where $d$ is the embedding size (128), $s$ is the current number of update steps, $S_w$ is the predefined warmup step number, and $C$ is a scaling constant that the paper varies systematically.

What it computes: the learning rate starts small (linear warmup for $S_w$ steps), then decays as $1/\sqrt{s}$. The constant $C$ controls overall magnitude; varying it changes how aggressively the optimizer explores the loss landscape.

Why this form: the $1/\sqrt{s}$ decay is the original transformer schedule, known to work well for sequence-to-sequence tasks. The warmup prevents early gradient variance from destabilizing training. The paper's novel contribution is systematically sweeping $C$ from 0.1 to 1.0 and discovering that different learning rates produce different learned algorithms — lower learning rates ($C=0.1$) produce models that copy tokens more faithfully but fail to develop "recursion heads," while higher learning rates ($C=1.0$) produce models with clear recursion heads that implement the shortcut algorithm.

Greedy decoding. All accuracy measurements use greedy decoding (selecting the most probable token at each step) rather than beam search or sampling. This simplifies the analysis: the model's behavior at each decoding step is deterministic given the input and the previously generated tokens, making it possible to attribute specific failures to specific decoding-time decisions.

Exact-match accuracy. The evaluation metric (Appendix A.1) is:

$\text{Acc} = \frac{\sum_{i \in \mathcal{D}_{\text{test}}} \mathbf{1}(\hat{Y}_i = Y_i)}{|\mathcal{D}_{\text{test}}|}$

where $\hat{Y}_i$ is the full generated sequence and $Y_i$ is the ground-truth target sequence.

What it computes: the fraction of test examples where every generated token exactly matches the target, with no partial credit. A single incorrect token anywhere in the sequence counts as a failure.

Why this form: for the binary successor task, a single token error (e.g., generating five X0 tokens instead of six in the recursive segment) changes the represented number and would be a semantically meaningful mistake. Partial credit would obscure whether the model's learned algorithm is actually correct. For tree traversal, the output is a list of characters where ordering matters, so token-level exact match is again the right granularity.

The Abstract State Machine (ASM) Computational Framework

The paper introduces Abstract State Machines (Gurevich, 1995) as the formal language for describing and comparing both the ground-truth recursive function and the transformer's learned approximation (Section 4). This framework is not an experimental tool but a conceptual lens — it determines what the authors look for in their analysis.

Definition of an ASM. An ASM is a state-transition system whose states are first-order structures:

$(U, f_1, \ldots, f_k)$

where $U$ is the algorithm's universe (a set that includes the constants true, false, undef), and each $f_i : U^{n_i} \to U$ is a function over that universe. The universe $U$ can be infinite and can include complex data types like real matrices, tensors, or streams. The functions $f_i$ can include operations like matrix multiplication, attention computation, or stream operations.

What it computes: an ASM execution is a sequence of state updates, where each update applies a finite set of conditional rules to the current state. At each step, rules of the form "if condition then update" are evaluated, and the matching updates are applied simultaneously. The computation terminates when no rules match.

Why this form matters for the paper: ASMs can describe programs at multiple levels of abstraction without committing to a specific implementation. A recursive function can be described as an ASM with explicit stack manipulation; a transformer can be described as an ASM whose functions include attention matrices and MLP layers. By describing both in the same formalism, the paper can ask a precise question: does the sequential ASM implemented by the transformer correctly approximate the recursive ASM of the target function?

Key features the paper exploits. The authors highlight two properties of ASMs that make them suitable for analyzing transformers:

1. Finite instruction set, infinite state. The transformer has a fixed set of operations (attention, feed-forward layers, layer norm) that are applied repeatedly. Its state — the activations at each layer, the generated tokens so far — can grow without bound. This matches the ASM template of finite rules operating on a potentially infinite state.

2. Sequential step-by-step execution. Each decoding step of an encoder-decoder transformer is naturally a sequential ASM update:

"Each decoding step of an encoder-decoder transformer is naturally a sequential ASM update."

This means the paper can analyze the transformer's behavior at each autoregressive step as a self-contained conditional computation, asking: which condition is being checked at this step, and what function is being applied?

The challenge of recursive approximation. The paper identifies a fundamental tension:

"The challenge arises when using learned transformer networks to approximate or simulate recursive algorithms. First, the ASM it simulates lacks recursive structure by nature. Also, training samples provide a partial extensional description of the unknown recursive function, while the pattern classifier determining recursive calls is an intensional description not encoded in the training objective or data."

In plain language: the transformer, being a feed-forward-plus-attention architecture, has no built-in mechanism for recursion (no call stack, no subroutine calls). The training data only shows input-output examples (extensional), not the internal pattern-matching logic (intensional). So the model must discover the intensional structure — which cases exist, which are base and which are recursive — purely from input-output examples. The ASM framework gives the authors a language for describing what the model does discover: a sequentialized approximation that replaces recursive calls with positional-encoding comparisons and token-copying operations.

How the framework guides analysis. The paper's reverse-engineering process is effectively a search for the ASM the transformer has learned:

"Starting from this perspective, we can analyze the algorithms implemented by learned transformers by attempting to search for its pattern classifiers and the if-else structure following each pattern, as well as the functions applied in each case at each time step."

For example, the binary successor task ASM might include:

• Pattern classifier: "if decodingCounter == recursionStartPosition then..."
• Function: "...generate X1 and set isInRecursion = True"

The pseudocode reconstructions in Appendix C (Figures 13 and 14) are explicitly ASM-style descriptions of the learned algorithms.

Attention Map Visualization Methodology

The first step in the reverse-engineering pipeline is visual inspection of attention maps to identify heads with specialized, interpretable behaviors (Section 5.1.1).

Three types of attention analyzed. For the encoder-decoder architecture, there are three attention mechanisms, each providing different information:

1. Encoder self-attention: how each input position attends to other input positions. The paper uses this to determine whether the encoder differentiates between cases — for example, whether XO tokens attend to other XO tokens, suggesting the encoder is performing case identification.

2. Decoder self-attention: how each output position attends to previously generated output positions. This is where the "recursion head" phenomenon appears: a specific head in the final decoder layer that attends to tokens that signal whether the model should be in "recursive mode" or "copying mode."

3. Encoder-decoder cross-attention: how each decoder position attends to encoder positions. The paper notes that for the binary successor task, cross-attention "was not interesting" — the model's behavior was primarily driven by decoder self-attention and positional encodings. For tree traversal, cross-attention becomes critically important.

Identification of the recursion head (natural order). Figure 6e shows the decoder self-attention map in the final layer for the natural order task. The key observation is:

"the model commences attending to the last bit prior to flipping from X1 to XO, and continues to do so until the end of the sequence. Thereafter, the recursion head predominantly allocates its attention towards the token we have described."

Concretely: suppose the input is X1 X1 X0 01 (which is eleven). The correct output is X0 X0 X1 01 (twelve). The decoder generates tokens left-to-right, and at the point where it needs to change from copying to generating new tokens (after outputting X1), the recursion head shifts its attention to a specific previously-generated token and holds it there for the remainder of generation. This is visual evidence that the model has learned a boundary detection mechanism: identify the position where the recursive segment begins, and use that position to control subsequent generation.

Identification of the recursion head (reverse order). Figure 2a shows the analogous pattern for the reverse order. Here, the recursion head:

"directs its attention towards the X1 tokens that have been generated earlier. This attention mechanism distinguishes between recursive segments, which necessitate modifications, and non-recursive segments, which do not require any rewrites."

In the reverse order, the input is processed right-to-left, so the recursive case is triggered by the first token. The recursion head attends to generated X1 tokens to determine whether an X1 has already been produced — if yes, switch to copying mode; if no, continue generating. The first occurrence of X1 serves as a boundary signal.

Encoder self-attention as case differentiation. Figures 2b and 2c show encoder self-attention maps, where the paper observes:

"the model employs its low-level attention to identify and differentiate symbols by attending to tokens of the same kind."

This means XO tokens in the input tend to attend to other XO tokens, and X1 tokens attend to other X1 tokens. This is a basic case-identification mechanism: the encoder is separating the input into "things that look like XO" and "things that look like X1," which provides the signal the decoder uses to determine whether the input is a base or recursive case.

For tree traversal, the analysis focuses on different patterns. Cross-attention in the preorder full traversal task (Figure 16) shows a clear separation between heads: Layer 0 heads attend broadly to nodes ahead and behind the current position, while Layer 1 heads consolidate attention exclusively on the next token to be copied. For inorder reduction (Figure 17), the model attends to parentheses, brackets, and EMPTY tokens in addition to node values — suggesting it is tracking the recursive depth of the tree structure through these syntactic markers.

Perturbation Analysis Methodology

Attention maps provide only correlational evidence. To establish causation, the paper performs perturbation analysis: mutating tokens and swapping positional encodings during decoding and observing how the model's behavior changes (Section 5.1.2).

Token content perturbations (Figures 3a and 3b). Three mutation operations are applied to the decoder's input at a specific decoding step:

• Deletion: remove a randomly chosen token from the partially-generated output.
• Insertion: insert a random string at a randomly chosen position.
• Flip: replace a randomly chosen token with a different token (e.g., X0 → X1).

The key insight from these experiments is that the model is robust to content perturbation. Even when the partially-generated output is corrupted, the model can recover and continue generating the correct remaining tokens. This suggests that the model's control flow is driven primarily by positional information, not by the specific token content at each position.

Positional encoding perturbations (Figures 3c and 3d). Two specific swaps are applied:

• SOR (Start of Recursion) perturbation (Figure 3c): Replace the positional encoding of a token at the position before the recursive segment with the positional encoding that would occur if that position were instead at a randomly chosen later location. In plain language: "trick the model into thinking we're at the start of recursion."
• EOS (End of Sequence) perturbation (Figure 3d): Replace the positional encoding just before the [EOS] token with that of a non-terminal position.

The results reveal the causal structure of the learned algorithm:

"when we changed the positional encoding of the bit before the recursive segment to a random location, the model started 'recursing' at the next time step by generating an X1 followed by XOs. Furthermore, if we replaced the positional encoding just before [EOS] with a non-terminal token, the model immediately stops generation by producing [EOS]."

This is the crux of the natural order algorithm: the model determines when to stop copying and start generating X1 + XOs by comparing the current positional encoding against a stored "recursion start" position encoded by the encoder. If the positional encoding matches, the trigger fires. The perturbation artificially fires the trigger at the wrong time, and the model obediently starts recursing.

Learning rate effects on perturbation success rate (Figure 4). The paper quantifies the perturbation success rate — the fraction of cases where the model's behavior follows the predicted pattern — as a function of recursion depth and learning rate factor $C$. Figure 4a (SOR perturbation) shows that:

• For $C = 0.1$ (low learning rate), the perturbation success rate is near 1.0 for in-distribution depths but rapidly drops to roughly 0.5–0.7 for depths beyond training.
• For $C = 1.0$ (high learning rate), the perturbation success rate is above 0.8 for all depths, including those far beyond the training maximum.

This is direct evidence that different learning rates produce different algorithms: the high learning rate model has learned a robust positional-comparison mechanism that generalizes, while the low learning rate model's mechanism is fragile and breaks down on longer sequences.

Reverse order perturbations (Section 5.1.2, Figure 3b). For the reverse order task, a different perturbation is applied: systematically replace each X0 token in the recursive segment with X1. The rationale is that the model uses the presence of an X1 token to switch from "generating mode" to "copying mode." If the experiment artificially introduces an X1 early, the model should switch to copying prematurely. The paper reports:

"in approximately 93.15% of the cases, the model successfully copied the remaining tokens with complete accuracy. However, in the remaining cases, the model initially began generating X1 tokens, but exhibited confusion after a few tokens, deviating from the expected behavior."

This confirms the reverse-order algorithm: the generation of the first X1 token (detected by the decoder self-attention mechanism) is the causal trigger for the mode switch. In most cases, the artificial trigger works as predicted; in a minority, the model's behavior degrades, suggesting secondary mechanisms come into play.

Counterfactual Patching Methodology (Tree Traversal)

For the more complex tree traversal task, the paper employs counterfactual patching (inspired by Meng et al., 2023) to identify causally important attention heads (Appendix D.3).

Procedure. The technique works by running two forward passes:

1. Clean pass: the model processes a given input and produces output $A$ (the correct answer).
2. Counterfactual pass: the model processes the same input but produces output $B$ (an incorrect answer — how this is induced is not specified in detail in the paper, but typically involves providing a different prompt or masking certain attention patterns).

Then, for each attention head, the activations from the clean pass are patched (substituted) into the counterfactual pass at that head's output. The change in logits is measured:

"The degree to which the patch restored the original logit difference was taken as a measure of significance for the corresponding head."

What it computes: for each attention head $h$, a significance score $\Delta_h = \text{logit}_A(\text{patch}_h) - \text{logit}_B(\text{patch}_h)$. A large positive score means that patching that head's clean activations into the counterfactual run strongly pushes the output back toward the correct answer $A$, implying the head is causally necessary for producing $A$.

Why this form: this is a causal intervention ($do$-calculus style) rather than a correlational measure. Attention weights alone might show that a head attends to certain positions, but they do not show that this attention actually causes the correct output. Counterfactual patching establishes necessity.

Application to tree traversal subtasks (Appendix D.2–3). The paper decomposes the traversal into seven key subtasks (e.g., copy initiation, insertion of root node, resumption of copy after insertion) and runs patching experiments on each. The key finding is:

"Typically, cross-attention heads most significantly affected the final result, but patching decoder self-attention also sometimes yielded significant, task-dependent changes in the logit difference."

For preorder full traversal, Layer 1 cross-attention heads are the most important. For inorder reduction at higher depths (3+ unroll steps), decoder self-attention becomes increasingly important, particularly attention to the UNROLL wrapper tokens — suggesting the model uses these markers to track which parent node should be copied next.

Algorithm Reconstruction and Failure Prediction Methodology

The final step is synthesizing all the empirical observations into explicit pseudocode and validating it against actual failure patterns (Section 5.1.3 and Appendix C).

Reconstruction process. The paper describes the process informally through the natural and reverse order examples. For the natural order, the key observations are:

1. The encoder identifies two critical positions: recursionStartPosition (the position where the recursive segment should begin in the output) and sequenceLastPosition (the position where the output should terminate).
2. The decoder maintains a boolean flag isInRecursion.
3. At each decoding step, the decoder compares the current positional encoding against recursionStartPosition. If it matches, the decoder generates an X1 and sets isInRecursion = True.
4. If isInRecursion is True, the decoder generates X0 tokens.
5. The decoder also compares the current positional encoding against sequenceLastPosition. If it matches, the decoder generates [EOS] and terminates.

The formal pseudocode is in Appendix C, Figure 13 (natural order) and Figure 14 (reverse order). These are not theoretical constructs — they are operational descriptions of what the model actually does, derived from the perturbation experiments.

How the pseudocode was derived. The paper does not describe an automated pipeline for extracting pseudocode from weights. Instead, the reconstruction is manual and hypothesis-driven: the authors observe attention patterns, formulate a hypothesis about the algorithm ("the model compares positional encodings to decide when to recurse"), design a perturbation experiment that would confirm or refute the hypothesis ("if we swap the positional encoding to trigger recursion early, the model should generate an X1"), and iterate. The pseudocode in Appendix C represents the final hypothesis after this iterative refinement.

Failure prediction methodology. Once the pseudocode is reconstructed, the paper uses it to mechanically predict which inputs will cause failures. The logic is:

For the natural order, the model's algorithm is: "find the position where the recursive segment starts, output an X1 there, and then output X0s until the end." The correct algorithm is: "recurse on the trailing X1 sequence, producing one X0 for each X1, then flip the next X0 to X1, and copy the rest."

The model's shortcut works when the recursive segment (trailing X1s) is fully contained within the output sequence. It fails when the recursion would need to propagate beyond the beginning of the sequence — i.e., when the input is entirely X1 tokens (e.g., X1 X1 X1 01, the maximum recursion depth for its length). In this case, the recursionStartPosition computed by the encoder is before the actual output begins (in the "pre-padding" region), and the model's positional comparison breaks down.

The paper validates this prediction quantitatively:

"The model fails on these cases 100% of the time for the natural order task. Among all failure cases (for C=1), 91% are due to one less XO token generated, which is a consequence of the flaw of the model's learned algorithm."

What this means operationally: for the maximum-recursion-depth inputs, the model attempts to find a recursionStartPosition, gets confused (because that position doesn't exist in the actual sequence), and either generates a 01 token prematurely (producing a sequence that is one X0 too short) or generates an incorrect token entirely. The 91% figure means that of all inputs on which the model makes any mistake, 91% of them are exactly this type of error — the remaining 9% are due to other, rarer failure modes.

The 91% is the paper's key quantitative validation. It shows that the reconstructed algorithm does not merely describe what the model does on average — it captures the model's behavior precisely enough to predict which specific inputs will fail and what the failure will look like. This is a much stronger claim than typical interpretability results, which often only provide post-hoc explanations of already-observed behaviors.

For the reverse order, the reconstruction is simpler. The pseudocode (Figure 14) shows a model that:

1. Generates X0 tokens until the encoder's cross-attention signals that an X1 should be generated.
2. After generating the first X1, switches to copying the remaining input tokens verbatim.

The paper's perturbation analysis (systematically replacing X0s with X1s) confirms this: in 93.15% of cases, the artificial X1 trigger causes the model to switch to copying mode as predicted. The model fails in the remaining 6.85% of cases, suggesting secondary mechanisms or edge cases that the simplified pseudocode does not capture.

Tree traversal algorithm reconstruction (Appendix D). For the tree traversal task, the paper describes reconstructed algorithms at a higher level, focusing on the rules the model follows for different reduction depths:

• For in-order reduction (shallow trees): the model starts with UNROLL[, copies the left subtree contents (tracking parentheses to know when the subtree is complete), inserts the parent node from the position immediately before the opening parenthesis of the completed subtree, copies the right subtree, and closes with ].
• For in-order reduction (deeper trees): the model uses decoder self-attention to attend to the beginning and end of the UNROLL[...] wrapper from previous reduction steps, using these as references to locate the appropriate parent node to copy.
• For preorder full traversal: the model does a straightforward copy of all node values, skipping parentheses, brackets, and EMPTY tokens. The attention heads separate into "broad attention" (attending to many nodes ahead and behind) and "focused attention" (attending only to the next node to copy), suggesting a two-stage pipeline.

These reconstructions are less formal than the binary successor pseudocode but follow the same logic: identify the key tokens the model uses as signals (parentheses, brackets, UNROLL markers), determine which attention heads track which signals, and describe the if-then rules that govern token generation.

The ASM connection. Each reconstructed algorithm is implicitly an ASM program: a set of conditional rules of the form "if the current state satisfies condition $P$, then apply function $f$ to produce the next token and update the state." The paper's contribution is showing that these ASM programs are (1) discoverable through careful perturbation analysis, (2) distinct from the ground-truth recursive ASM, and (3) sufficiently precise to predict where they break.

4. Key Insights and Innovations

Innovation 1: Learned Shortcuts Are Systematically Reconstructible — and Their Failures Are Predictable

The paper’s most distinctive intellectual contribution is not the observation that transformers learn shortcuts (that much is well-established), but rather the demonstration that these shortcuts are sufficiently systematic and interpretable to be reverse-engineered into explicit pseudocode, from which specific failure cases can be mechanically predicted. This converts what is typically a post-hoc lament (“the model learned a brittle heuristic”) into a diagnostic instrument: if you can reconstruct the learned algorithm, you can anticipate exactly where it will break without needing to run the model on those inputs.

Prior work on mechanistic interpretability has successfully reverse-engineered algorithms for modular arithmetic (Nanda et al., 2023), group operations (Chughtai et al., 2023), and indirect object identification in language models (Wang et al., 2022). But these reconstructions focused on correct algorithms — the model had learned something that generalized. This paper tackles the more common and practically important case: the model learns an approximation that works on the training distribution but fails systematically on out-of-distribution inputs. The key conceptual move is treating the shortcut not as a failure to be bemoaned but as a deterministic program whose logic can be uncovered and whose boundary conditions can be derived.

The 91% failure prediction rate for the binary successor task (Section 5.1.3) is the empirical anchor for this claim. This is not a post-hoc explanation of observed errors; it is a prospective prediction, validated against the model’s actual behavior on the full test set. The paper explicitly states:

“Among all failure cases (for C=1), 91% are due to one less XO token generated, which is a consequence of the flaw of the model’s learned algorithm.”

This is a fundamentally different standard of evidence from typical interpretability work, which often reports qualitative agreement between hypothesized mechanisms and observed behavior. Here, the hypothesis makes a precise, falsifiable, quantitative prediction — and it is confirmed.

The significance extends beyond this particular task. The paper establishes a methodological template: (1) train a small model on a synthetic task with known ground-truth semantics, (2) use attention visualization and perturbation analysis to reconstruct the learned algorithm as pseudocode, (3) mechanically derive the inputs on which that pseudocode diverges from the ground truth, (4) validate that the model actually fails on those inputs. This is a blueprint for studying learned shortcuts in any domain where the target function is known — program synthesis, mathematical reasoning, code generation — and it opens the door to proactive identification of model weaknesses rather than reactive discovery through benchmarking.

Innovation 2: The Recursion Head as a Diagnostic Primitive

The paper introduces recursion heads as a specific, identifiable class of attention head that emerges when transformers are trained on recursive tasks. In the natural order binary successor task, this head in the final decoder layer attends to a specific token (the last bit before the recursive segment) and maintains that attention for the remainder of generation (Figure 6e). In the reverse order, the recursion head attends to previously generated X1 tokens and uses their presence or absence to switch between generation modes (Figure 2a).

What makes this a conceptual contribution rather than merely an empirical observation is that it provides a concrete neural correlate of the model’s internal representation of “recursion.” The field has long debated whether transformers can represent recursive computation at all — theoretical work establishes that they can in principle (Pérez et al., 2021), but whether gradient descent discovers such representations in practice has been an open question. The recursion head is not a stack or a recursive subroutine call; it is a sequentialized proxy that replaces recursive case decomposition with a positional or token-based signal. The model does not learn to “recurse” in the sense of pushing and popping stack frames. It learns to detect a boundary condition (the start of the recursive segment) and then execute a fixed pattern (generate X1 then X0s) until termination.

This finding reframes the question from “can transformers learn recursion?” to “what does a transformer’s approximation of recursion actually look like, and when does it break?” The answer — a specialized attention head that tracks a boundary signal — is likely not unique to the binary successor task. The paper’s tree traversal analysis (Appendix D) shows that for more complex recursive structures, the model develops analogous mechanisms: attention heads that track parentheses, brackets, and UNROLL markers to determine depth and decide which parent node to copy. The recursion head is a diagnostic primitive: if you suspect a transformer has learned some approximation of recursion, look for heads whose attention patterns exhibit boundary-tracking or mode-switching behavior tied to the recursive structure.

This is a fundamental rather than incremental contribution because it gives the field a search target for studying recursive computation in larger, less interpretable models. Future work can ask: do large language models develop recursion heads when trained on code? Do chain-of-thought prompts induce recursion-head-like behavior? The paper does not answer these questions, but it provides the conceptual vocabulary and the empirical template for asking them.

Innovation 3: Learning Rate as an Algorithm Selector

A surprising and potentially significant finding is that different learning rates produce qualitatively different learned algorithms for the same task, model architecture, and training data (Section 5.1.4). At low learning rates (C = 0.1), the model learns a fragile token-copying strategy that does not develop clear recursion heads and degrades rapidly on out-of-distribution depths (Figure 4, Figure 6). At high learning rates (C = 1.0), the model develops robust recursion heads and a positional-comparison mechanism that generalizes well beyond the training distribution. When training is further constrained to shallow recursion depths (Figure 5b), the low-learning-rate model sees a steeper drop in test performance while the high-learning-rate model maintains better generalization.

This finding challenges the implicit assumption in much of deep learning that learning rate is primarily an optimization hyperparameter — something that affects convergence speed and final loss, but not the qualitative nature of the learned solution. Here, the learning rate selects between distinct algorithmic strategies. The paper does not fully explain why this happens, but the evidence is clear: the attention maps in Figures 6a–6e show a gradual emergence of the recursion head as C increases from 0.1 to 1.0, with the head becoming progressively more specialized and focused.

The intellectual significance is that optimization dynamics and algorithmic discovery are coupled in ways that are not captured by standard loss-landscape analyses. A smaller learning rate may trap the model in a local minimum corresponding to a simpler but less generalizable shortcut, while a larger learning rate allows the optimizer to escape that basin and discover a more structured solution. This has practical implications for training models on reasoning tasks: if the goal is to elicit genuine algorithmic reasoning rather than shallow pattern matching, learning rate may need to be treated as a first-class architectural choice rather than a nuisance parameter to be tuned for convergence speed. It also suggests a connection to the grokking literature (Nanda et al., 2023), where delayed generalization is associated with the discovery of structured representations — here, the high learning rate may accelerate or enable that discovery.

This is an incremental but important refinement of our understanding: the field already knows that different random seeds and hyperparameters can produce models with different generalization properties; this paper shows that for recursive tasks, the differences are algorithmically interpretable and can be traced to specific attention-head behaviors. It opens the door to studying learning rate as a dial for controlling the complexity of learned algorithms.

Innovation 4: Grounding Mechanistic Interpretability in Program Semantics

The paper makes a conceptual contribution by connecting mechanistic interpretability to program semantics research. The tasks are not arbitrary synthetic functions; they are structurally recursive programs defined over inductive datatypes — the same formal substrate used in proof assistants (Coq, Lean, Isabelle) and program synthesis tools. The analysis is framed through Abstract State Machines (Section 4), a formalism from theoretical computer science designed to describe programs at multiple levels of abstraction. The decomposition of tree traversal into atomic reduction steps (Section 3.2) draws directly on the programming languages concept of reduction semantics.

This matters because it establishes a shared vocabulary between two communities that rarely interact. Mechanistic interpretability researchers typically study neural networks through the lens of linear algebra, attention patterns, and circuit diagrams. Programming languages researchers study programs through the lens of operational semantics, type systems, and inductive definitions. The paper demonstrates that these perspectives are complementary: by choosing tasks with well-defined intensional semantics (the recursive case structure is known), the authors can evaluate the model’s learned algorithm against a formal specification, not just against test-set accuracy. The ASM framework provides a common language for describing both — the ground-truth recursion as an ASM with stack manipulation, and the learned shortcut as an ASM with positional-comparison triggers.

The significance is that this opens a bidirectional bridge. For the interpretability community, program semantics provides a rich source of tasks with known algorithmic structure, enabling precise reconstruction and failure analysis of the kind demonstrated here. For the programming languages community, mechanistic interpretability provides tools for understanding why neural program synthesis tools fail on certain inputs, potentially informing the design of hybrid neural-symbolic systems where the symbolic component compensates for specific neural weaknesses. The paper does not build such a system, but it lays the conceptual groundwork.

This is a fundamental reframing rather than an incremental advance: it changes the question from “how accurate is the model?” to “what program does the model implement, and how does it differ from the target program?” The ASM framework is the enabling abstraction that makes this reframing precise.

Innovation 5: Decomposing Recursive Tasks into Atomic Subtasks as an Interpretability Strategy

The paper’s approach to the tree traversal task — decomposing the full traversal into atomic reduction steps (one, two, or three unrolls) rather than training end-to-end — is a methodological innovation with implications beyond this study. The key finding is that models can learn individual reduction steps with high accuracy, even when they fail at the full end-to-end traversal (Figure 7): preorder full traversal works well, but inorder full traversal fails completely, while partial inorder reductions succeed.

This decomposition serves a dual purpose. First, it is an interpretability instrument: by training separate models on different numbers of reduction steps, the paper can isolate which aspect of the recursive computation the model struggles with. The finding that inorder reduction at shallow depths succeeds but deeper reductions require additional mechanisms (decoder self-attention to UNROLL markers) reveals that the bottleneck is tracking depth during composition — the model can execute a single reduction rule, but composing multiple reductions requires maintaining state across steps.

Second, the decomposition is implicitly a baseline for chain-of-thought prompting. The paper does not make this connection explicit, but the atomic reduction subtasks are exactly the kind of intermediate computation that chain-of-thought or scratchpad methods would expose. By showing that the model can perform individual reduction steps but fails when they must be composed internally, the paper provides mechanistic evidence for why making intermediate steps explicit helps: the transformer architecture struggles to maintain and compose recursive state across multiple levels, but can execute each level when it is presented sequentially. This is not a proof, but it is a suggestive alignment between the mechanistic findings and the empirical success of chain-of-thought methods.

This is an incremental methodological contribution: task decomposition for analysis is not new, but applying it to recursive program semantics and connecting it to chain-of-thought reasoning through attention-head analysis is novel. It provides a template for future work: when a transformer fails at a complex recursive task, decompose the task into atomic steps, train models on each step, and use the performance gradient to identify which compositional operation the model cannot internalize.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The two tasks—binary successor and tree traversal—are synthetic: training data is generated by enumerating instances of the target inductive datatype (binary positive naturals or binary trees) up to a specified bound, computing the ground-truth recursive function on each instance, and pairing input and output representations. For binary successor, the training set spans binary strings from 1 up to $n$, where $n$ is varied across experiments (2048, 4096, 8192, ..., 131072, corresponding to maximum bit-lengths of 12 to 17). The distribution of recursion depths is non-uniform because it follows the natural frequency of trailing X1 sequences in binary numbers. For tree traversal, the training and test sets are split by tree structure (topology), not by character values at nodes, so the model must generalize to unseen tree shapes rather than memorize specific value patterns. The exact sizes of these splits are not reported numerically in the paper, but the task descriptions in Appendix A.2 and performance curves in Figure 5 indicate that training set sizes range from 2,000 to over 130,000 examples depending on the maximum enumeration bound.

• Base model(s). All experiments use small encoder-decoder transformers trained from scratch with 2 encoder layers, 2 decoder layers, hidden dimension 128, and 2 attention heads per layer (Appendix A.1). The total parameter count is not explicitly stated but, with these dimensions and standard feed-forward width (typically 4× hidden dimension, or 512), the model likely has well under 1 million parameters. Sinusoidal positional encoding is used throughout. The choice of encoder-decoder architecture was determined by preliminary experiments on a string reversal extrapolation task (Appendix E, Figure 18), where encoder-decoder models substantially outperformed both encoder-only and decoder-only variants at lengths beyond the training distribution—maintaining accuracy above 70% at 14 tokens beyond the training maximum, versus near-zero for the alternatives. The small scale is intentional: with only 2 heads per layer, each head’s function can be distinctly characterized, and the limited capacity forces the model to learn a compact representation that is feasible to reverse-engineer.

• Metrics. The primary metric is exact-match sequence accuracy: the fraction of test examples for which the entire generated output sequence matches the ground-truth target sequence token-for-token, under greedy decoding (Appendix A.1, Equation 1). Formally, $\text{Acc} = \frac{\sum_{i \in \mathcal{D}_{\text{test}}} \mathbf{1}(\hat{Y}_i == Y_i)}{|\mathcal{D}_{\text{test}}|}$. There is no partial credit—a single incorrect token anywhere in the output counts as a failure. For the binary successor task, this means even one missing or extra X0 token in the recursive segment (which changes the represented number) is an error. For tree traversal, exact match applies to the full character sequence including brackets and UNROLL markers. In the perturbation analysis sections, a secondary metric is perturbation success rate: the fraction of cases where a specific perturbation (e.g., swapping a positional encoding) produces the behavior predicted by the reconstructed algorithm (Section 5.1.2, Figure 4).

• Baselines. The paper does not compare against prior neural or symbolic methods in a traditional sense—there is no external baseline model like "GPT-2 on binary successor" or "a symbolic program synthesizer." Instead, the ground-truth recursive function serves as the correctness oracle: the model’s output is compared directly against the mathematically correct result of applying the target function to the input. The baselines are architectural variants explored in Appendix E: encoder-only (4 layers) and decoder-only (4 layers) transformers on the natural order binary successor task (Figure 19), both of which perform substantially worse than the encoder-decoder architecture, and different learning rate settings (C = 0.1 vs. C = 1.0) which produce qualitatively different learned algorithms. Within the tree traversal analysis, the baseline is the full end-to-end traversal model, against which the atomic reduction step models are compared (Figure 7).

• Generation budget / compute accounting. There is no explicit "compute budget" framing in this paper—the authors are not comparing different inference-time strategies at a fixed FLOP count, as one would in a scaling laws paper. Instead, the relevant resource is training data quantity (number of enumerated input-output pairs), which is systematically varied across experiments (x-axis of Figures 5, 9, 20–25). For positional encoding and extrapolation experiments, the relevant resource is sequence length, with the "random padding" augmentation (Appendix A.1) used to train models to handle positions beyond those seen during training. Greedy decoding means inference cost per example is deterministic and proportional to output length.

• Cross-validation / statistical protocol. The paper does not use k-fold cross-validation on the binary successor task; instead, it reports accuracy as a function of recursion depth on a fixed test set, with error bars showing standard deviation across 3 runs with different random seeds (evident in Figures 20–25, though the main-text figures in Section 5 do not always display these bars). For the tree traversal task, the train/test split is by tree topology—models are evaluated on tree structures not seen during training. The perturbation analysis reports success rates aggregated across test examples without cross-validation, since the analysis is causal rather than accuracy-maximizing. The paper explicitly notes in Appendix A.1 that "for tree traversal experiments, by default, we split the train and test sets by tree structures, where we wish to understand the model’s capability of dealing with unseen topologies of the tree."

Main Quantitative Results

Binary Successor: Extrapolation Performance by Recursion Depth

The central quantitative finding for the binary successor task is that model accuracy degrades sharply at recursion depths beyond those seen during training, but the degradation pattern depends critically on learning rate and whether the task uses natural or reverse ordering (Figures 5, 20–25).

Natural order, full training range (Figure 5a). When trained on the full range of binary strings (maximum training depth extending to 131,072 examples), the model with high learning rate ($C = 1.0$) maintains near-perfect accuracy (above 0.95) on all test groups, including depths 2–4, 4–6, 8–10, and 18–20 tokens beyond the training maximum. The model with low learning rate ($C = 0.1$) shows a decline: accuracy on the $L_{\text{train}}^{\text{max}} + 18$ to $L_{\text{train}}^{\text{max}} + 20$ group drops below 0.8 with 120,000 training examples. The error bars (standard deviation across 3 runs) are noticeably wider for the low learning rate model on the farthest-out extrapolation groups, indicating higher variance in learned algorithms at low learning rates.

Natural order, constrained training depth (Figure 5b). When the model is trained only on examples with recursion depth up to 3 (meaning the maximum number of trailing X1 tokens is bounded), a stark difference emerges: the high-learning-rate model ($C = 1.0$) maintains accuracy above 0.85 even on depths 8–10 and 18–20 beyond training, while the low-learning-rate model ($C = 0.1$) drops to roughly 0.65 on the farthest extrapolation group at 120,000 training examples. This directly shows that the learning rate controls whether the model discovers a depth-generalizing algorithm, not just whether it fits the training data well.

Reverse order (Figure 5c). In the reverse order, the depth constraint has minimal impact: both learning rates produce near-perfect accuracy (above 0.95) on all test groups regardless of whether the training data included the full depth range or was constrained to depth 3 or 6 (see also Figure 9 in Appendix C, which shows the full reverse-order constrained curves). This is explained by the reconstructed algorithm (Section 5.1.2, Appendix C, Figure 14): in the reverse order, the recursive case is determined by the first token, so the model simply checks whether an X1 has been generated yet and switches modes accordingly—this mechanism does not depend on the depth of recursion, making it inherently length-generalizing.

Full per-depth breakdowns. Appendices F and H (Figures 20–25) provide granular accuracy-vs-recursion-depth curves for each training set size (2048 through 131072) under both natural and reverse orders, with and without depth constraints (max training depth 3 or 6), and with both learning rate settings. The consistent pattern is that natural order models trained with low learning rate show accuracy that peaks at in-distribution depths and then declines—sometimes to near-zero—for depths well beyond training (e.g., Figure 20a, where at training size 2048, accuracy is ~1.0 for depths below the training maximum and drops to ~0.1 for depths 25–30). Natural order models with high learning rate maintain flatter accuracy curves across depths. Reverse order models show uniformly high accuracy across all depths regardless of learning rate (Figures 21, 24, 25).

Binary Successor: Quantitative Perturbation Analysis

SOR (Start-of-Recursion) positional encoding perturbation (Figure 4a). The perturbation success rate—defined as the percentage of cases where swapping the positional encoding to mimic the start of recursion causes the model to initiate recursion (generate X1 followed by X0s)—shows a clear learning-rate effect:

• For $C = 0.1$ (low learning rate): success rate is near 1.0 for recursion depths within the training distribution, but drops to approximately 0.5–0.7 for depths 2–20 tokens beyond the training maximum. At the farthest extrapolation (18–20 tokens beyond training), the success rate falls below 0.5 for some configurations, indicating that the positional-comparison trigger becomes unreliable.
• For $C = 1.0$ (high learning rate): success rate remains above 0.8 across all tested recursion depths, including those 18–20 tokens beyond the training maximum. The perturbed positional encoding reliably triggers the recursive behavior regardless of absolute position.

EOS (End-of-Sequence) positional encoding perturbation (Figure 4b). The analogous perturbation—swapping the positional encoding just before [EOS] to a non-terminal position—shows a similar pattern: the high-learning-rate model reliably terminates generation at the perturbed position (success rate above 0.9), while the low-learning-rate model shows declining reliability (dropping to ~0.6 for some far-extrapolation groups). This confirms that the learned algorithm's termination condition, like its recursion initiation condition, is encoded as a positional-comparison mechanism that the high-learning-rate model implements more robustly.

Reverse order token-flipping perturbation (Section 5.1.2). When X0 tokens in the recursive segment are systematically replaced with X1 to test whether X1 triggers the mode switch to copying, the model copies the remaining tokens with complete accuracy in 93.15% of cases. The remaining 6.85% show partial confusion—the model initially generates X1 tokens as expected but deviates after a few steps. This confirms that the reverse-order algorithm's trigger (detection of the first generated X1 by the recursion head) is the dominant causal mechanism, with secondary failure modes in a minority of cases.

Binary Successor: Failure Prediction Accuracy

The paper's most striking quantitative claim is that the reconstructed algorithm correctly predicts 91% of failure cases for the natural order task with $C = 1.0$ (Section 5.1.3). The specific failure mode is: on inputs consisting entirely of X1 tokens (maximum recursion depth for their length, e.g., X1 X1 X1 01), the model generates a sequence that is one X0 token too short. The model fails on these maximum-recursion-depth cases 100% of the time.

The paper explains this mechanistically: the model's learned algorithm computes a recursionStartPosition where it should begin outputting X1 + X0s. On maximum-recursion-depth inputs, this position falls before the actual output sequence (in the prepadding region), causing the model to encounter confusion between generating X1 or 01, settle on 01, and terminate prematurely—producing an output one token too short. The 91% figure means that of all inputs on which the model makes any error, 91% are exactly this type of failure; the remaining 9% are due to rarer, secondary failure modes not captured by the simplified pseudocode. This is the central empirical validation of the paper's core methodological claim: that the reconstructed algorithm is precise enough to predict which specific inputs will fail and what the failure will look like.

Binary Successor: Learning Rate Controls Algorithm Discovery

The qualitative finding that different learning rates produce distinct algorithms (Section 5.1.4) is supported quantitatively by both attention map specialization (Figure 6) and the depth-constrained training results (Figures 5b, 5c, and Appendix C Figure 9).

Attention map specialization (Figure 6). The paper shows decoder self-attention maps for the final layer under five learning rate factors: $C = 0.1, 0.3, 0.5, 0.7, 1.0$. At $C = 0.1$ (Figure 6a), the attention is diffuse—no single head shows the focused, positional-attention pattern characteristic of the recursion head. As $C$ increases, one head progressively sharpens its attention: at $C = 0.3$ (Figure 6b), a slight concentration begins to appear; at $C = 0.5$ (Figure 6c), the pattern is moderately clear; at $C = 0.7$ and $C = 1.0$ (Figures 6d–e), the recursion head is fully specialized, attending strongly to a specific boundary token and maintaining that attention for the remainder of generation. This is a direct visualization of a learning-rate-driven phase transition in the model's internal organization.

Depth-constrained training (Appendix C, Figure 9). When models are trained with maximum recursion depth constrained to 3 or 6 (rather than the full natural depth distribution), the performance gap between high and low learning rate becomes stark. For natural order with depth-3 constraint (Figure 9a): the $C = 1.0$ model maintains accuracy above 0.95 on all test groups including depths 18–20 beyond training, while the $C = 0.1$ model drops to roughly 0.65 for the farthest extrapolation group at the largest training size. For reverse order with depth-3 constraint (Figure 9c): both learning rates maintain accuracy above 0.95 across all groups. The depth-6 constraint (Figures 9b, 9d) shows qualitatively similar but less extreme patterns since the model has seen deeper recursion during training. These results collectively show that the high learning rate enables discovery of a depth-generalizing algorithm (positional-comparison in the natural order, token-detection in the reverse order) while the low learning rate produces a strategy that works only on depths seen during training.

Binary Successor: Encoder and Decoder Embedding Analysis

The paper investigates whether the model's internal representations encode recursive-case information or recursion depth explicitly (Appendix B, Tables 1 and 2).

Sequence pattern-matching (Table 1). A linear classifier trained on the average encoder output to distinguish between XO b and X1 b cases achieves mediocre accuracy: roughly 0.66–0.68 train and 0.52–0.66 test for $C = 1.0$ models, and lower for $C = 0.1$ models (0.52–0.64 train, 0.51–0.52 test). For classifying recursion depth (how many trailing X1 tokens are present), the classifiers perform poorly: 0.20–0.22 train accuracy and 0.13–0.14 test accuracy across all configurations. This suggests that the encoder does not explicitly encode the recursive case or recursion depth in a linearly separable way, consistent with the finding that recursion-related information is encoded in positional comparisons rather than in static token embeddings.

Recursion-depth recognition from embeddings (Table 2). A classifier trained on individual token embeddings to predict recursion depth performs differently on encoder vs. decoder embeddings. Encoder embeddings: train accuracy ~0.32–0.33, test accuracy ~0.23–0.25 for all configurations—barely above random, confirming that encoder token representations do not carry recursion depth information. Decoder embeddings: train accuracy 0.68 for natural order $C = 1.0$ (test 0.54), but only 0.47 train / 0.37 test for reverse order $C = 1.0$. This shows that decoder token representations do contain some recursion-depth information in the natural order (but not the reverse order), consistent with the decoder's role in executing the positional-comparison algorithm—the information is in the dynamic decoding state, not in the static encoder output.

Tree Traversal: Full Traversal vs. Atomic Reduction Performance

Full traversals are hard; partial reductions are not (Figure 7, Section 5.2.1). The quantitative results show a sharp performance gradient based on traversal type and number of reduction steps:

• Preorder full traversal: Models trained on the full end-to-end preorder traversal achieve accuracy roughly 0.8–1.0 across tree depths 5 and 6, whether trained on depth-5-only data or on a mix of depths 5 and 6. This is the one case where a full traversal is successfully learned.
• Inorder full traversal: Accuracy drops to near-zero (below 0.1) for both depth-5-only and mixed depth-5/6 training. The model completely fails to learn the full inorder traversal from input-output examples.
• Inorder partial reduction: When the task is decomposed into 1, 2, or 3 reduction steps (rather than full traversal), models achieve near-perfect accuracy (close to 1.0) for 1 unroll step, high accuracy (~0.8–0.9) for 2 unroll steps, and moderate-to-high accuracy for 3 unroll steps (the exact values are visible in Figure 7 but not numerically specified in the text). The performance degrades gradually with the number of unroll steps, not abruptly.

The interpretation (Section 5.2.1) is that preorder traversals have a linear shortcut (the output order matches a simple left-to-right reading of node values, skipping brackets and EMPTY tokens—confirmed by cross-attention patterns in Figure 16 showing the model attending only to node tokens), while inorder traversals require tracking recursive structure that the sequence model cannot internalize without explicit intermediate steps. The atomic reduction task succeeds because the reduction step is a local rewriting rule that can be executed by pattern-matching on parentheses and brackets without requiring a global stack.

Depth-specific shortcuts in partial reductions (Section 5.2.3). The paper observes qualitatively—though without a dedicated quantitative figure—that models learn different mechanisms for different reduction depths. For 2-step reductions, the model can simply copy the root node from the beginning of a parenthesized sequence once the subtree has been unrolled (shallow tracking). For 3-step reductions, the model must distinguish between parent nodes at different depths, which requires attending to the UNROLL wrapper markers via decoder self-attention. The loss curves (Appendix G, Figure 26) show that models learning higher-order reductions converge to higher final loss values than those learning lower-order reductions—the 4-unroll-step inorder model converges to a loss above 1.0, while the 1-unroll-step models converge below 0.5. This quantitatively confirms that deeper composition incurs a penalty even during training.

Architecture Comparison: Encoder-Decoder vs. Encoder-Only vs. Decoder-Only

String reversal extrapolation (Appendix E, Figure 18). On a preliminary string reversal task (training lengths 10–37, testing up to length 50), the encoder-decoder model maintains accuracy above 70% for extrapolation lengths up to 14 tokens beyond training, while encoder-only accuracy drops to ~0.5 at 4 tokens beyond training and near-zero at 10+ tokens, and decoder-only drops to ~0.5 at 2 tokens beyond and near-zero at 8+ tokens. This justified the choice of encoder-decoder architecture for the main experiments.

Binary successor with alternative architectures (Appendix E, Figure 19). On the natural order binary successor task, encoder-only and decoder-only models (4 layers each, to roughly match total depth) perform substantially worse than the 2+2-layer encoder-decoder. Encoder-only trained on the full depth range: accuracy of 1.0 on training depths, dropping to 0.52 for depths 4–6 beyond training, and 0.04 for depths 8–10 beyond. Decoder-only is similar: 1.0 on training, 0.52 for 4–6 beyond, 0.18 for 8–10 beyond. Both architectures perform poorly when trained only on shallow depths (max depth 3 or 6): encoder-only drops to 0.31 (depths 2–4 beyond) and 0.09 (depths 8–10 beyond) when trained to depth 3; decoder-only drops to 0.01 (depths 8–10 beyond). These results confirm that the encoder-decoder architecture's separation of input processing (encoder identifies critical positions) and output generation (decoder compares positional encodings against those positions) is essential for the depth-generalizing algorithm to emerge.

Sequence Pattern-Matching and Recursion-Depth Classification

Classifier experiments (Appendix B, Tables 1–2). The negative results from the probing experiments are quantitatively informative:

• Binary classification of XO b vs. X1 b cases (Table 1): A linear classifier trained on averaged encoder outputs achieves at best 0.68 train / 0.66 test accuracy (natural order, $C = 1.0$). This is far from perfect—the encoder does not cleanly separate the two recursive cases in its static representation. The $C = 0.1$ models perform worse (0.62 train / 0.52 test for natural order), consistent with the finding that low-learning-rate models learn less structured internal representations.
• Recursion-depth classification from encoder embeddings (Table 1, right columns): 0.20–0.22 train accuracy across all configurations—essentially random for a 5-way classification problem (five depth quintiles), confirming that recursion depth is not encoded in the static encoder output.
• Recursion-depth recognition from decoder embeddings (Table 2): The decoder token embeddings (specifically, the output embedding of the final decoder layer) contain more depth information: natural order $C = 1.0$ achieves 0.68 train / 0.54 test accuracy, while reverse order achieves only 0.47 train / 0.37 test. This asymmetry—depth is more decodable from natural order decoder states than reverse order states—is consistent with the finding that the natural order algorithm relies on positional comparisons (which carry depth information implicitly through position), while the reverse order algorithm uses a simpler token-match trigger that is depth-agnostic.

Ablation Studies and Robustness Checks

Architecture choice (encoder-decoder vs. encoder-only vs. decoder-only): Encoder-decoder substantially outperforms alternatives on both string reversal extrapolation (Figure 18) and binary successor (Figure 19). Encoder-only and decoder-only models fail to extrapolate to longer sequences, with accuracy dropping to near-zero within 4–10 tokens beyond the training maximum, while encoder-decoder maintains high accuracy. This ablation confirms that the dual-architecture separation of input analysis (encoder) and autoregressive generation (decoder) is critical for the learned algorithms to generalize.

Learning rate factor C (0.1 vs. 1.0): This is the paper's most extensively analyzed ablation. Higher learning rates ($C = 1.0$) produce models with specialized recursion heads (Figure 6), robust positional-encoding perturbation responses (Figure 4), and strong depth generalization (Figure 5). Lower learning rates ($C = 0.1$) produce models without clear recursion heads, fragile perturbation responses, and rapid performance degradation on out-of-distribution depths. This is not merely a quantitative difference in accuracy—it is a qualitative difference in the algorithm learned. The paper does not ablate intermediate values of C beyond the visualization in Figure 6, which shows the recursion head emerging gradually as C increases from 0.1 to 1.0.

Training depth constraint (max recursion depth 3, 6, or full): When training is restricted to examples with recursion depth ≤ 3 or ≤ 6 (Appendix C, Figure 9; Figures 5b, 5c), the high-learning-rate natural order model maintains strong out-of-distribution depth generalization while the low-learning-rate model degrades significantly (Figure 5b). Reverse order models are robust to this constraint regardless of learning rate (Figure 5c), because the reverse-order algorithm's trigger mechanism is depth-independent. The depth-constrained experiments are effectively an ablation of whether the model needs to see deep recursion during training to learn a depth-generalizing algorithm—the answer is yes for low learning rates, no for high learning rates.

Training data quantity (systematic sweep from 2048 to 131072 examples): Every accuracy-vs-depth figure (Figures 20–25) shows results across 7 training set sizes, enabling assessment of how much data is needed for the learned algorithms to stabilize. For natural order with $C = 1.0$ (Figures 20a–g), performance on in-distribution depths is near-perfect even at 2048 training examples, but performance on far-extrapolation depths (18–20 tokens beyond training max) improves gradually as training data increases, reaching near-perfect only at 65536+ examples. For natural order with $C = 0.1$ (Figures 20a–g), far-extrapolation performance remains poor even at 131072 examples, again suggesting that more data alone does not fix the algorithm-selection problem—the learning rate matters more.

Ordering (natural vs. reverse, with and without depth constraints): The comparison between natural and reverse order task formulations is itself a major ablation. Reverse order uniformly outperforms natural order on depth generalization (Figures 5a vs. 5c, Figures 20 vs. 21), and reverse order models are robust to depth-constrained training while natural order models are not (Figures 22–25). This ablation confirms that the learned algorithm depends on whether the recursive case is signaled by the first token (reverse order, easy) or the last token (natural order, requiring positional lookahead).

Tree traversal: number of unroll steps (1, 2, 3, 4, or full): The performance gradient across unroll steps (Figure 7) is effectively an ablation of compositional depth. Models succeed on 1-step reductions, maintain high accuracy on 2-step reductions, and progressively degrade on 3-step and full reductions. The loss curves (Figure 26) show higher convergence loss for more unroll steps (4-step inorder converges above 1.0 loss, 1-step converges below 0.5). This ablation directly demonstrates that the transformer's difficulty with inorder traversal is not about the atomic operation (which it can learn) but about composing multiple operations without explicit intermediate state.

Tree traversal: cross-attention vs. decoder self-attention importance (counterfactual patching, Appendix D.3): Counterfactual patching reveals that cross-attention heads are most causally important for preorder full traversal (copying node values from the encoder), while decoder self-attention becomes increasingly important for deeper inorder reductions—specifically, attention to UNROLL markers is used to track which parent node to copy. This ablation of which attention mechanism matters when provides evidence for the reconstructed algorithms' division of labor between "reading from input" (cross-attention) and "tracking compositional state" (self-attention).

Perturbation type (token mutation vs. positional encoding swap): The contrast between token-content perturbations (which the model is robust to) and positional-encoding perturbations (which reliably trigger specific behaviors) is an implicit ablation establishing that the natural order algorithm is driven primarily by positional information, not token identity. The paper does not provide a dedicated ablation figure for this contrast, but the perturbation success rates (93.15% for reverse-order token flips, ~80–100% for natural-order positional swaps depending on learning rate and depth) quantify it.

Negative result: probing for recursive case information fails (Appendix B, Tables 1–2). The inability to train linear classifiers that reliably distinguish XO b from X1 b cases or predict recursion depth from encoder embeddings is an important negative result. It shows that the model does not explicitly encode the recursive case structure in a static, linearly accessible form—the information is in the dynamic computation (positional comparisons, attention patterns), not in the token representations themselves. This constrains what kinds of interpretability techniques can recover the learned algorithm: probing classifiers alone would miss the key mechanisms.

Negative result: encoder-only and decoder-only architectures fail (Appendix E, Figure 19). The poor performance of alternative architectures, particularly when trained on constrained depth ranges, demonstrates that the encoder-decoder separation is not merely an optimization convenience but is functionally necessary for the depth-generalizing shortcut to be discovered.

Tree traversal negative result: inorder full traversal fails completely (Figure 7). Despite succeeding on partial inorder reductions and full preorder traversals, the model achieves near-zero accuracy on full inorder traversal. This negative result is the paper's strongest evidence that the transformer architecture has a fundamental limitation with non-linear recursive structure—when the output order requires interleaving subtrees in a way that cannot be reduced to a linear scan, the model cannot discover a working shortcut.

Critical Assessment

Claim 1: "The model's attention maps exhibit clear recursion-capturing patterns."

Does the evidence support this? Partially. The attention map visualizations (Figures 2, 6) do show heads with distinctive, interpretable behavior aligned with the recursive task structure—the "recursion head" in the natural order attends to the boundary token before the recursive segment; the reverse order recursion head attends to previously generated X1 tokens. The perturbation experiments (Figures 3, 4) provide causal evidence that these attention patterns are functionally meaningful, not epiphenomenal: artificially triggering the attended-to condition (by swapping positional encodings or flipping tokens) causes the predicted behavioral change.

What the evidence does not show. The paper only visualizes attention patterns for successfully trained models (C = 0.1–1.0) and only for a small number of example inputs. There is no systematic quantification of how frequently the recursion head pattern appears across different random seeds, different training set sizes, or different input types. The claim that the pattern is "clear" is based on qualitative visual inspection of a few attention maps. For a stronger claim, one would want a metric—e.g., the attention weight concentrated on the boundary token as a fraction of total attention—computed across the full test set and across multiple training runs, with statistical comparisons against null models.

The causal evidence is strong for the cases tested but limited in scope. The SOR perturbation (Figure 3c) is applied to specific positions; the paper reports a success rate but does not describe how many distinct inputs were perturbed, whether the perturbation location was systematically varied, or whether the effect size depends on input properties beyond recursion depth. The 93.15% figure for reverse-order token flips is precise but the experimental protocol—how many tokens were flipped, on how many inputs, under what sampling—is not fully described.

Claim 2: "A perturbation analysis provides a granular explanation of the algorithm."

Does the evidence support this? Yes, with the important caveat that the "granular explanation" is a manually constructed interpretation of perturbation responses, not an automatically extracted program. The perturbation experiments (Section 5.1.2) successfully isolate two key mechanisms: (1) the natural order model uses positional encoding comparison to trigger recursion initiation and termination, and (2) the reverse order model uses generated-X1 detection as a mode-switch trigger. The fact that both mechanisms can be fooled by targeted perturbations (positional swaps, token flips) and that the fooling rates are high (80–100% for natural order high-C, 93% for reverse order) provides strong causal evidence for these specific mechanisms.

What the evidence does not show. The perturbation analysis tests the two hypothesized triggers in isolation. It does not provide a complete causal graph of the model's computation—for example, it does not show how the encoder computes recursionStartPosition from the input, or which attention heads in earlier layers contribute to that computation. The reconstructed pseudocode (Appendix C, Figures 13–14) includes functions like Model.Encoder.recognizeImportantPositions(b) and Model.Decoder.checkIsRecursionStart(...) that are treated as black boxes; the perturbation analysis only validates the existence of these functions, not their internal implementation. A more complete mechanistic account would require circuit-level analysis (as in Wang et al., 2022 or Nanda et al., 2023) tracing the computation from input tokens through attention heads and MLPs to the final trigger.

The tree traversal perturbation analysis (counterfactual patching) is even less granular. The paper identifies that certain attention heads are important (Appendix D.3) and describes their attention patterns (Figures 15–17), but does not perform the kind of targeted perturbation that would reveal the specific computational rule each head implements. The "reconstructed algorithms" for tree traversal (Appendix D.4) are higher-level descriptions of the model's apparent strategy, not validated by perturbation experiments of the kind done for binary successor.

Claim 3: "A majority of failures are foreseeable from the reconstructed algorithm (91% for natural order, C=1)."

Does the evidence support this? This is the paper's strongest claim and the evidence is reasonably strong, though some details are missing. The logic is clear: the reconstructed algorithm says the model identifies recursionStartPosition and starts outputting X1 + X0s from there; on maximum-recursion-depth inputs, that position falls before the sequence starts, confusing the model and causing it to generate one too few X0s. The paper reports two numbers: 100% failure rate on these maximum-depth cases, and 91% of all failures being this specific type. The 100% claim is binary and easily verified. The 91% claim depends on the denominator—"all failure cases"—which the paper does not explicitly enumerate: how many total failures were there, across how many test inputs, with what distribution of recursion depths? If most test inputs are at depths where the model succeeds, the denominator could be small, making the 91% figure less robust than it appears.

What would strengthen this claim. The paper could report a confusion matrix: for each recursion depth, what fraction of inputs does the model get correct vs. incorrect with one-missing-X0 vs. incorrect with other error types. This would show whether the 91% figure is stable across depths or is dominated by a particular depth range. The paper could also test whether the prediction holds for models trained with different random seeds, different training set sizes, and the lower learning rate (C=0.1)—is the failure mode the same even when the overall algorithm is different?

The claim is specific to one task and one learning rate. The paper notes that for the reverse order, the failure mode is different (and the model is more robust overall). The predictive power of the reconstructed algorithm is demonstrated only for binary successor natural order C=1—there is no equivalent quantitative failure prediction for the tree traversal tasks.

Claim 4: "Learning rates impact learned algorithms and generalization abilities."

Does the evidence support this? Yes, and this is the paper's most surprising and potentially impactful empirical finding. The evidence spans multiple independent measurements: attention map specialization (Figure 6), perturbation success rates (Figure 4), depth-constrained training accuracy (Figure 5b), and probing classifier accuracy (Appendix B). All four show consistent differences between C=0.1 and C=1.0 that cannot be explained as mere optimization speed or final loss differences—the models have qualitatively different internal organization and generalization behavior.

Limitations. The paper only tests two values of the learning rate factor C (0.1 and 1.0) for most experiments, with the intermediate values (0.3, 0.5, 0.7) shown only in the attention map visualization (Figure 6). This is enough to show a trend but not enough to characterize the phase transition—does the recursion head emerge sharply at some critical C between 0.3 and 0.7, or does it strengthen continuously? Does the generalization behavior track the attention-head specialization smoothly, or is there a threshold effect? The paper acknowledges this implicitly by describing the emergence as "gradual" (Section 5.1.4) but does not quantify it.

The mechanism linking learning rate to algorithm selection is unexplained. The paper shows that different learning rates produce different algorithms, but does not investigate why. Is the larger learning rate escaping a local minimum that the smaller learning rate gets stuck in? Is it a grokking-like phenomenon where the structured solution is present but takes longer to emerge, and the small learning rate model was simply not trained long enough? The paper does not report whether the C=0.1 model, if trained for many more epochs, would eventually develop recursion heads. This is a significant gap in the mechanistic story—without understanding the optimization dynamics, the finding is an empirical observation rather than an explained phenomenon.

Claim 5: "Models learn simple parenthesis and bracket tracking rules to perform reduction" (tree traversal).

Does the evidence support this? Qualitatively yes, but the evidence is thinner than for the binary successor claims. The attention maps (Figures 15–17) do show heads attending to parentheses, brackets, and EMPTY tokens at moments when those syntactic markers are relevant to the reduction task. The counterfactual patching (Appendix D.3) confirms that cross-attention heads are causally important, and the paper describes a plausible algorithm based on these observations (Appendix D.4: the model copies left subtree contents, tracks parenthesis closure to know when the subtree is complete, then inserts the parent node).

What the evidence does not show. There is no perturbation analysis for the tree traversal task comparable to the binary successor analysis—no targeted swapping of parentheses to see if the model miscopies the subtree, no deletion of UNROLL markers to see if parent-node tracking breaks. The algorithm reconstruction is a post-hoc interpretation of attention patterns, not a causally validated mechanism. The paper acknowledges this implicitly by describing the reconstruction as identifying "the most significant contributing heads" (Appendix D.3) rather than a complete circuit. The tree traversal analysis is best understood as groundwork—establishing that attention patterns are structured and interpretable—rather than a complete mechanistic account.

Overall Weaknesses in Experimental Design

Single architecture, single scale. All experiments use one model size (2 encoder layers, 2 decoder layers, hidden dim 128, 2 heads). There is no investigation of how the learned algorithms change with model scale—would a deeper or wider model learn a genuinely recursive algorithm rather than a shortcut? Would it learn the same shortcut but more robustly? The paper's title asks "Can Transformers Learn to Solve Problems Recursively?" but the experiments are restricted to very small transformers; the answer for larger models remains unknown.

No comparison to symbolic baselines or human performance. The paper is explicitly not benchmarking accuracy for its own sake, so this is not a major weakness. However, reporting human accuracy on the same tasks (or the accuracy of a simple symbolic program synthesizer) would contextualize the model's performance—is 91% failure predictability impressive because the model is otherwise highly accurate, or because it fails so often that predicting failures is easy?

Greedy decoding only. The paper uses greedy decoding throughout. Temperature sampling or beam search might produce different failure patterns, and the reconstructed algorithm (which assumes deterministic generation at each step) might not capture stochastic behavior. This is a reasonable choice for mechanistic analysis (deterministic behavior is easier to reverse-engineer), but it limits the generality of the findings.

Small number of random seeds. Error bars are shown for 3 runs in the depth-vs-accuracy figures (Figures 20–25) but not in the main-text figures. Three seeds is minimal for assessing variance in learned algorithms—especially given the paper's own finding that learning rate qualitatively changes the algorithm, suggesting that the optimization landscape has multiple distinct basins. More seeds would reveal whether the recursion head reliably emerges at high learning rates or is itself seed-dependent.

Missing ablation: number of attention heads. The paper uses 2 heads per layer. Would 4 or 8 heads produce the same specialization, or would the recursion head fail to emerge because attention is distributed across more heads? The paper does not ablate this architectural choice.

Missing ablation: positional encoding type. The paper uses sinusoidal positional encoding. The natural order algorithm depends critically on positional comparisons. Would a learned positional encoding produce the same algorithm? Would rotary position embeddings (which encode relative position differently) change the learned shortcut? This is relevant for connecting the findings to modern LLMs, which often use rotary embeddings.

Test set size unreported for tree traversal. The paper does not specify how many distinct tree topologies are in the tree traversal test set, making it impossible to assess the statistical reliability of the accuracy differences in Figure 7.

Do the Experiments Support the Paper's Central Narrative?

The paper's central narrative is that transformers do not learn genuine structural recursion—they learn interpretable shortcuts based on positional comparisons, token-boundary detection, and parenthesis tracking; that these shortcuts can be reverse-engineered; and that understanding the shortcuts allows predicting when the models will fail. The experiments strongly support this narrative for the binary successor task (particularly the natural order, C=1.0 configuration, where the reconstructed algorithm achieves 91% failure prediction). They partially support it for the reverse order binary successor (the algorithm is reconstructed and validated by perturbation but failure prediction isn't quantified). They weakly support it for the tree traversal task (attention patterns are interpretable and consistent with described shortcuts, but there is no perturbation-based causal validation and no quantitative failure prediction).

The broader implication—that this methodology can be applied to understand failures in large pretrained models on programming tasks—is not tested at all. The paper is transparent about this (Section 7: "our main focus was on toy transformer models trained from scratch, while we deferred the understanding of large pretrained language models to future work"), but the title and framing invite the reader to infer relevance to transformers in general, which the experiments do not directly establish.

The most robust contributions are the methodological template (attention analysis → perturbation → pseudocode reconstruction → failure prediction) and the specific finding that learning rate can act as an algorithm selector. The most speculative contribution is the ASM framework as an analytical tool—it is used as a conceptual framing device (Sections 4, Appendix B) but does not drive any experimental design or yield non-obvious predictions that wouldn't arise from attention analysis alone. The probing experiments (Appendix B) that explicitly test the ASM hypothesis (does the model implement a recursive ASM with pattern matching?) return negative results, suggesting the ASM framing describes what the model should do rather than what it does do.

6. Limitations and Trade-offs

Limitation 1: Single Architecture and Scale — Findings May Not Transfer to Larger or Differently-Structured Transformers

The assumption or constraint. All experiments in this paper use a single, very small transformer architecture: 2 encoder layers, 2 decoder layers, hidden dimension 128, and 2 attention heads per layer (Appendix A.1). This is likely under 1 million parameters — orders of magnitude smaller than the models used in practical program synthesis and verification tools, which are typically large pretrained language models. The paper is explicit about this scope:

"our main focus was on toy transformer models trained from scratch, while we deferred the understanding of large pretrained language models to future work" (Section 7).

Additionally, only one architectural variant (encoder-decoder) was studied in depth, with encoder-only and decoder-only alternatives examined only in a preliminary capacity (Appendix E) and found to underperform — but this does not establish whether the identified mechanisms are specific to the encoder-decoder design.

The consequence. The central findings — the existence of recursion heads, the learning of positional-comparison shortcuts rather than genuine recursion, the 91% failure predictability — may be specific to this particular model scale and architecture. A larger model with more layers, more heads, and greater capacity might discover genuinely recursive algorithms that this small model could not represent. Conversely, a larger pretrained model might bring different inductive biases (from its pretraining on code or natural language) that lead to qualitatively different learned algorithms. The paper cannot distinguish between "transformers at any scale learn these specific shortcuts" and "transformers at this small scale learn these specific shortcuts because they lack capacity for genuine recursion." The title asks "Can Transformers Learn to Solve Problems Recursively?" but the experiments only address what very small transformers learn.

What evidence exists in the paper. The architecture comparison in Appendix E (Figure 19) shows that encoder-only and decoder-only models of comparable depth perform substantially worse on binary successor extrapolation, but this comparison keeps total layer count roughly constant (4 layers) rather than matching parameter count or exploring larger configurations. There is no scaling analysis — no experiments with deeper encoders, wider hidden dimensions, or more attention heads that would reveal whether the learned algorithms change qualitatively with scale. The paper does not measure how the recursion head's properties (specialization, perturbation robustness, failure predictability) vary with model size.

Mitigation status. The paper acknowledges this limitation explicitly in the quoted statement from Section 7 and frames it as deferred future work. No mitigation is attempted within the paper itself. This is a reasonable scoping choice for a mechanistic interpretability study, but it means the paper's title and framing overclaim relative to the experimental evidence: the question "Can Transformers Learn to Solve Problems Recursively?" is answered only for one specific, very small transformer configuration.

Limitation 2: Difficulty Estimation and Strategy Selection Cost Are Not Accounted For — The Reconstructed Algorithms Require Full Attention Map Access and Manual Analysis

The assumption or constraint. The paper's core methodological contribution — reconstructing learned algorithms via attention visualization, perturbation analysis, and pseudocode synthesis — relies on full access to all model internals (attention maps, positional encodings, activations at every layer) and on manual, expert-driven hypothesis formation and testing. The perturbation experiments require the ability to modify token content, positional encodings, and activations on the fly during decoding at arbitrary positions. The algorithm reconstruction process is entirely manual: the authors inspect attention maps visually, formulate hypotheses about what triggers exist, design perturbation experiments to test those hypotheses, iterate, and finally write pseudocode by hand.

This is not a deployable diagnostic pipeline but a research methodology requiring deep expertise in both the model architecture and the target task semantics. The paper does not propose any automated procedure for extracting the learned algorithm or predicting failures without human analysis.

The consequence. The impressive 91% failure prediction rate is achieved through a labor-intensive process that is not scalable to larger models, more complex tasks, or production deployment. For a practitioner deciding whether to use a transformer for a recursive programming task, the paper offers no practical tool for determining whether the model is likely to fail on specific unseen inputs — it offers only a proof of concept that such prediction is possible in principle if one invests substantial expert effort in reverse engineering. The methodology also requires that the ground-truth semantics of the target function be fully known, which is precisely not the case in real program synthesis or verification tasks where the correct output is unknown.

Additionally, the perturbation analysis itself consumes inference compute: each perturbation experiment requires running the model on modified inputs to observe behavioral changes. This cost is not accounted for in any budget calculation because the paper's goal is analysis, not deployment. But it means the methodology cannot be straightforwardly adapted as a runtime verification mechanism (e.g., "run the model, perturb the input, check if the output changes in a way that reveals a shortcut").

What evidence exists in the paper. The entire experimental section (Section 5) is structured around manual analysis of specific models on specific tasks. The perturbation experiments in Section 5.1.2 involve hand-designed interventions (Figures 3a–3d) applied to individual example inputs. The pseudocode in Appendix C (Figures 13–14) is manually written based on the authors' interpretation of attention patterns and perturbation responses. There is no description of any automated circuit-discovery, pattern-mining, or failure-prediction tool. The probing experiments in Appendix B (Tables 1–2) attempt automated analysis (linear classifiers on embeddings) but return negative results — the information is not in static embeddings, making automated extraction harder.

Mitigation status. The paper does not claim or attempt to automate the analysis pipeline. It presents the methodology as a research contribution — a way of understanding what small transformers learn — rather than as a deployable tool. The "future work" discussion (Section 7) does not suggest automation as a direction, instead focusing on extending the analysis to larger pretrained models. A practitioner would need to substantially re-derive the analysis for their own model and task.

Limitation 3: The Difficulty of the Binary Successor Task Is Not Representative of Real Recursive Programs — The Shortcut Works Because the Task Is Structurally Simple

The assumption or constraint. The binary successor task, while carefully chosen to isolate structural recursion, is an extremely simple function by the standards of real programming tasks. The recursion follows a single linear chain (each recursive call is on the same argument with one X1 removed) with no branching, no multiple base cases beyond the trivial 01, and no dependence on values other than the immediate constructor tags (XO vs. X1). The output is always exactly the same length as the input (the successor of an n-bit number is at most n+1 bits, and the length change is deterministic). The ground-truth algorithm requires no arithmetic, no comparison of values, and no memory beyond the current position in the recursion chain.

The paper acknowledges that the tree traversal task is more challenging precisely because it has "two recursive subcases" (Section 3.2) — branching recursion — and indeed the model fails completely on full inorder traversal (Figure 7). This suggests that the binary successor task's simplicity is not a neutral choice but actively enables the specific shortcut the model discovers. The shortcut (Section 5.1.2) — compare positional encodings, output X1 then X0s — works because the recursive structure is so regular that the output can be predicted from a single boundary position without any iteration or conditional branching.

The consequence. The paper's most impressive quantitative result — 91% failure prediction — is demonstrated on a task where the learned algorithm is simple enough to be described in ~20 lines of pseudocode. It is unclear whether this level of reconstruction is achievable for functions with richer recursive structure: multiple arguments, nested recursion, conditional branching within cases, or recursion that depends on computed values rather than just constructor tags. The tree traversal results are cautionary: the reconstruction there (Appendix D.4) is higher-level and less precise, with no perturbation-based causal validation and no quantitative failure prediction. The gap between the binary successor analysis (granular pseudocode, causally validated triggers, 91% failure prediction) and the tree traversal analysis (attention pattern descriptions, plausible but unvalidated rules) suggests that the methodology's effectiveness degrades sharply as task complexity increases — and real recursive programs in synthesis and verification are far more complex than binary tree traversals.

What evidence exists in the paper. The contrast between Section 5.1 (binary successor: detailed pseudocode, perturbation validation, 91% failure prediction) and Section 5.2 (tree traversal: attention descriptions, no pseudocode, no failure prediction) demonstrates this limitation implicitly. The paper notes that for tree traversal, the counterfactual patching "did not reveal the full circuit used to perform the task, but did provide suggestive, causal evidence" (Appendix D.3) — acknowledging that the analysis is less complete. The inorder full traversal failure (Figure 7, near-zero accuracy) shows that even this moderately more complex task defeats the model entirely, so there is no algorithm to reconstruct.

Mitigation status. The paper does not claim that the methodology scales to arbitrary recursive functions. It presents the binary successor as a "minimal testbed" and the tree traversal as a more challenging extension. The limitation is inherent to the task choice rather than to the analysis — the paper shows what is possible when the task is simple enough for full reconstruction, but does not establish the complexity boundary beyond which reconstruction becomes infeasible. Future work would need to characterize this boundary by testing the methodology on a graded spectrum of recursive tasks with increasing structural complexity.

Limitation 4: The Training Setup Assumes Access to a Complete Enumerative Description of the Target Function — Input-Output Pairs Are Generated Deterministically from the Known Recursive Definition

The assumption or constraint. The training data for both tasks is generated by exhaustively enumerating instances of the target inductive datatype (binary strings up to length n, trees up to certain depths), computing the ground-truth recursive function on each instance, and pairing the input representation with the correct output. This means the training data provides complete, noise-free coverage of the function's behavior on all inputs within the enumeration bound. The model sees every possible input up to the maximum training size, and every output is guaranteed correct.

This is fundamentally different from the setting in which neural program synthesis tools are typically deployed. In real program synthesis, the model is given a small number of input-output examples (the specification) and must generalize to produce a program that works on all inputs — including inputs far outside the distribution of the provided examples. In real code generation, the model is given a natural language description or a partial program and must produce code that is correct in general, not just on the specific examples it was trained on. The paper's training paradigm (dense, exhaustive input-output pairs) teaches the model to emulate a specific function on a specific distribution, not to synthesize a general program from sparse examples.

The consequence. The paper's findings may not transfer to the sparse-example regime. When a model sees only a few examples of a recursive function's behavior (e.g., the six examples in Section 3.1), it must infer the recursive structure — base case, inductive cases, recursive calls — rather than interpolate between densely sampled input-output pairs. This inference task is precisely what program synthesis tools are designed to do, and it requires a different kind of generalization than the extrapolation-to-longer-sequences studied in this paper. A model trained on dense input-output pairs for the binary successor may learn the positional shortcut precisely because the dense coverage makes the shortcut discoverable — the model can observe that the mapping from input to output follows a simple positional rule across thousands of examples. In a sparse-example regime, the same shortcut might be undiscoverable, and the model might be forced to learn something closer to the true recursive mechanism (or fail entirely).

Additionally, the exhaustive enumeration means the training distribution is artificially uniform over the space of instances up to a given size. In real programming tasks, the distribution of inputs on which a function is called is often highly non-uniform and unknown at training time. The learned shortcut might be brittle to distribution shift in ways that go beyond the extrapolation-to-longer-sequences tested in this paper.

What evidence exists in the paper. The paper does not experiment with sparse-example training. The training set sizes (Figures 5, 20–25) range from 2,048 to 131,072 examples — these are full enumerations of binary strings up to the specified bit-length, not sparse samples. The binary successor function is simple enough that a human can infer it from 6 examples (Section 3.1), but the paper never tests whether a transformer can do the same. The paper's "few-shot" or "sparse" regime is not explored at all. The closest analogue is the depth-constrained training (Figures 5b, 9), where the model is trained only on examples with shallow recursion but tested on deeper recursion — but this is a constraint on the type of examples seen, not on their number. The model still sees all shallow-depth examples exhaustively.

Mitigation status. The paper does not address this limitation. The focus is explicitly on "learning to emulate the behavior of structurally recursive functions from input-output examples" (Section 1), and the training setup is designed to provide dense coverage. This is a reasonable choice for studying whether and how transformers approximate recursion when given sufficient data, but it means the results do not speak to the problem of program synthesis from sparse specifications — which is arguably the more practically important setting.

Limitation 5: The Method Cannot Distinguish Between "The Model Learned a Shortcut" and "The Task Is Inherently Solvable by a Shortcut" — The Binary Successor Function May Not Require Recursion

The assumption or constraint. The paper frames the binary successor task as one that "captures the essence of what it means to adapt functions and proofs defined over the unary peano natural numbers so that they instead are defined over binary natural numbers" (Section 3.1) and presents the ground-truth solution as a structurally recursive function with three cases. However, the binary successor on a fixed-width bit-string representation is actually computable by a purely iterative, non-recursive algorithm: scan the bits from right to left, flip the first XO to X1 (or 01 to XO 01), and flip all preceding X1s to XOs. This is exactly the standard ripple-carry increment operation on binary numbers, which requires no stack, no recursive calls, and no pattern matching beyond the immediate bit values. The "recursive" structure of the Coq definition is an artifact of defining the function over an inductive datatype, not an inherent requirement of the computation being performed.

This means the model's learned shortcut — find the boundary position, output X1, then output XOs — might not be a "non-recursive shortcut" at all, but rather a faithful implementation of the iterative version of the computation. The model may have discovered exactly the right algorithm for the actual mathematical operation (increment a binary number), just expressed as a positional rule rather than as structural recursion over an inductive type. The paper cannot distinguish between "the model learned a shallow shortcut" and "the ground-truth computation is shallow when viewed through the right representation."

The consequence. The paper's central narrative — that transformers fail to learn genuine recursion and instead learn brittle shortcuts — is weakened if the target function itself does not require recursion for efficient computation. The binary successor on fixed-width bit strings is in complexity class AC0 (constant-depth, polynomial-size circuits) and is computable by a simple feedforward network without any recurrence. A model that learns a non-recursive solution to this task is not failing to learn recursion; it is learning the most natural algorithm for the underlying operation. The task's "recursiveness" is an artifact of the Coq encoding, not an intrinsic property of the input-output mapping.

For the tree traversal task, this issue is less severe because tree traversals genuinely require tracking recursive depth if the tree structure is arbitrary. However, the preorder full traversal — which the model succeeds at — is also computable by a linear scan (just extract node values in order, skipping structure tokens), as the paper's own attention analysis confirms (Figure 16: the model attends only to node tokens). The inorder traversal — which the model fails at — is the one that genuinely requires recursive structure tracking. This pattern suggests that the models succeed precisely when the task reduces to a linear operation and fail when it requires true recursive state — which is consistent with the paper's thesis but also highlights that the binary successor task is a weak test case: it succeeds not because the model approximates recursion well, but because the task doesn't need recursion.

What evidence exists in the paper. The paper does not discuss this distinction between "structurally recursive definition" and "computationally shallow operation." The binary successor is presented as a recursive task throughout (Sections 1, 3.1, 5.1), and the learned algorithm is characterized as a "shortcut" or "sequentialized approximation." The fact that the learned algorithm is remarkably effective (near-perfect accuracy on all depths for the reverse order, strong generalization for natural order with C=1.0) and the fact that it corresponds closely to the ripple-carry algorithm are not connected. The probing experiments in Appendix B, which test whether the model encodes recursive case information, return negative results — which could be interpreted as evidence that the model correctly ignores the recursive structure because it's not needed.

Mitigation status. The paper does not address this limitation. The choice of the binary successor function is motivated by its significance in proof repair and type equivalence research (Section 3.1, Appendix A.2.1), not by an analysis of its computational depth. To establish that the model is failing to learn recursion when recursion is necessary, the paper would need to test on tasks that are provably not computable by shallow circuits without recurrent state — for example, tasks requiring matching parentheses of unbounded depth, or evaluating expressions with nested structure where the nesting depth is not bounded during training. The tree traversal results move in this direction, but the inorder full traversal failure leaves no algorithm to reconstruct, so the methodology's value for recursive failures is demonstrated only on a task where recursion may not be needed.

Limitation 6: No Combinatorial or Statistical Generalization Testing Beyond Length Extrapolation — Generalization Across Different Structural Distributions Is Untested

The assumption or constraint. The paper's generalization tests (Figures 5, 20–25) measure performance exclusively along one axis: recursion depth (for binary successor) or tree depth (for tree traversal). Test groups are defined by how many tokens beyond the training maximum the recursion extends (e.g., $L_{\text{train}}^{\text{max}} + 2$ to $L_{\text{train}}^{\text{max}} + 4$). This is a natural generalization axis because it tests whether the model can handle recursion depths it was not trained on — but it is only one specific kind of distribution shift.

Real program semantics involves many other forms of variation: different ratios of base cases to recursive cases, different patterns of recursive calls (e.g., some branches terminate early while others go deep), different mixtures of constructor frequencies (XO vs. X1), and entirely novel compositions of known sub-operations. The binary successor training data follows the natural distribution of trailing X1 sequences in binary numbers (which is non-uniform but fixed), and the tree traversal training data is split by topology but not systematically varied in structural properties (e.g., balanced vs. skewed trees, trees with varying ratios of internal nodes to leaves).

The consequence. The 91% failure prediction rate is demonstrated for one specific type of out-of-distribution input: maximum recursion depth inputs (all X1s) in the natural order. The paper does not test whether the reconstructed algorithm also predicts failures for inputs with unusual structural patterns that are still within the trained depth range — for example, inputs with alternating XO and X1 patterns that are rare or absent in the training data, or inputs where the recursive segment has an atypical ratio of X1 to XO tokens. If the learned shortcut depends on statistical regularities of the training distribution (e.g., "recursive segments are usually short," "most inputs have a mix of XO and X1"), then the model might fail on in-distribution inputs that violate those regularities, and the paper would not detect these failures because they don't correspond to longer recursion depths.

For tree traversal, the train/test split by topology (Appendix A.1) tests generalization to new tree shapes, but the paper does not characterize how different training topologies are from test topologies. A model that has seen only balanced trees during training might succeed on balanced test trees but fail on highly skewed test trees, even if both have the same depth. Without characterizing the structural distance between train and test distributions, it is unclear what kind of generalization the accuracy numbers actually measure.

What evidence exists in the paper. The binary successor test groups are defined purely by recursion depth (length beyond training max). The tree traversal train/test split is described as "by tree structures" but the distribution of structures is not quantified. There is no analysis of model accuracy as a function of structural properties other than depth — no breakdown by the number of recursive subcases triggered, the ratio of base to inductive cases, the "shape" of recursion, or the frequency of specific constructor sequences. The perturbation experiments (Section 5.1.2) test specific mechanistic hypotheses (does changing the positional encoding trigger recursion?) but do not systematically vary input structure in ways that would reveal distributional brittleness.

Mitigation status. The paper does not address this limitation. The depth-extrapolation framework is standard in the length-generalization literature and is appropriate for establishing basic algorithmic generalization. But the paper's claim that understanding the learned algorithm allows predicting failures is validated only for depth-extrapolation failures — not for distribution-shift failures within the trained depth range. This is a significant gap because many practical failures of neural program tools occur on inputs that are structurally unusual but not necessarily deeper than training examples. Extending the failure prediction methodology to cover these cases would require a richer characterization of the input distribution and the model's sensitivity to its statistical properties.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper does not introduce a new architecture, training algorithm, or benchmark — it introduces a diagnostic methodology for understanding when and why transformers fail on recursive tasks. The magnitude of this contribution is best characterized as a methodological reframing rather than a paradigm shift: the paper takes an existing set of tools (attention visualization, perturbation analysis, counterfactual patching) and demonstrates that, when applied systematically to tasks with known intensional semantics, they can yield reconstructed algorithms precise enough to predict specific failures before running the model on those inputs. The 91% failure prediction rate on the binary successor task (Section 5.1.3) is the empirical anchor — it converts mechanistic interpretability from a post-hoc explanatory enterprise into a prospective diagnostic one.

The most important conceptual shift is the move from "does the model generalize?" to "what program does the model implement, and what are its boundary conditions?" Prior work on length generalization (e.g., Liu et al., 2022; Delétang et al., 2022) asked whether models succeed on longer sequences. This work asks a deeper question: given that the model succeeds on some inputs and fails on others, can we characterize the dividing line mechanistically? The answer — yes, if you can reconstruct the learned algorithm — changes what it means to "understand" a model's behavior. Test-set accuracy becomes a downstream consequence of an algorithm's match to the target function, rather than the primary object of study. This is a direct intellectual descendant of the mechanistic interpretability program (Olah et al., 2020; Elhage et al., 2021; Wang et al., 2022; Nanda et al., 2023) but applied to a domain — program semantics — where the ground-truth algorithm is fully known, making the gap between learned and target algorithms precisely measurable.

The paper also reconciles a tension in the existing interpretability literature between "models learn interpretable algorithms" (Nanda et al., 2023; Chughtai et al., 2023) and "models learn brittle shortcuts" (common failure mode observations). These are not contradictory — they are two sides of the same phenomenon. The model does learn an algorithm, and that algorithm is interpretable, but it is not the target algorithm. The paper's key move is showing that the learned algorithm is systematic enough to be reconstructed and its failures predicted, which means the brittleness is not random or inscrutable. This reframes shortcut learning from a frustrating limitation into an analyzable property.

Research directions that become more attractive include:

• Extending the methodology to larger pretrained models on programming tasks, where the gap between learned and target semantics has direct practical consequences for code generation and verification.
• Using reconstructed algorithms to design training interventions (data augmentation, architectural modifications, auxiliary losses) that specifically target the identified failure boundary.
• Developing automated or semi-automated versions of the algorithm-reconstruction pipeline, making the methodology applicable at scale rather than requiring expert manual analysis per task.
• Characterizing the complexity boundary: for which classes of recursive functions can transformers discover genuine recursion, versus reliable shortcuts, versus no working solution at all?

Research directions that become less attractive include:

• Purely accuracy-maximizing approaches to neural program synthesis that treat the model as a black box and optimize only test-set metrics — this paper demonstrates that high accuracy can mask systematic, predictable failures that only mechanistic analysis reveals.
• Binary "can transformers do recursion?" debates that fail to distinguish between expressiveness (what the architecture can represent in principle) and discoverability (what gradient descent actually finds in practice). The paper shows that for a specific small transformer, the answer is "it discovers a non-recursive shortcut, and we can characterize it precisely." This is a more useful answer than a theoretical yes/no.

Follow-Up Research This Work Enables

Scaling the methodology: does a 100× larger transformer learn the same shortcut, a more robust version of it, or a genuinely recursive algorithm? The paper's central findings are demonstrated on models with ~1M parameters. A natural extension is to scale model size across several orders of magnitude (e.g., 1M → 10M → 100M → 1B parameters) on the same binary successor task, measuring (a) whether recursion heads still emerge, (b) whether the 91% failure prediction rate holds or changes, and (c) whether the perturbation success rates (Figures 4a–b) increase, suggesting the shortcut becomes more robust, or decrease, suggesting the model discovers a different mechanism. This would directly address the paper's own limitation acknowledged in Section 7. A strong result would identify a phase transition — a model size at which the learned algorithm shifts qualitatively from a positional shortcut to something approximating genuine recursive case decomposition. Such a finding would have immediate implications for the scale at which neural program synthesis tools become trustworthy.

Sparse-example regime: can a transformer induce the recursive function from 6 examples, and if so, what algorithm does it learn? The paper trains on exhaustive enumerations of input-output pairs. A critical follow-up is to replicate the analysis in a program synthesis setting: train on the six examples from Section 3.1 that fully specify the binary successor function, and test on the full range of inputs up to much larger recursion depths. The key questions are (a) whether the model can generalize at all from sparse examples, (b) whether the learned algorithm is the same positional shortcut (which requires dense coverage to discover the positional regularity), or a different mechanism forced by data scarcity, and (c) whether the reconstructed algorithm predicts failures as precisely as in the dense-training case. This would connect the paper's methodology to the program synthesis literature (Gulwani et al., 2017; Lee and Cho, 2023) that the paper cites as motivation but does not experimentally engage.

Stress-testing the methodology on recursively deeper tasks: parity, tree evaluation, or context-free grammar parsing. The binary successor's computational shallowness (Limitation 5 in Section 6) weakens the claim that the model is "failing to learn recursion." A strong follow-up would apply the same analysis pipeline to tasks that provably require recurrent state: computing the parity of a binary string (where the correct output depends on a global property), evaluating arithmetic expressions with nested parentheses of unbounded depth, or recognizing strings from a context-free grammar requiring stack-like state. For each, the ground-truth algorithm is known, so the gap between learned and target algorithms can be measured. The prediction: on tasks where the target computation has higher circuit complexity, the learned shortcuts will be more complex, the failure modes harder to predict, and the performance ceiling lower. The key measurement would be the failure prediction rate as a function of computational depth — does the 91% figure degrade smoothly or collapse at some complexity threshold?

Learning rate as an algorithm selector: characterizing the loss landscape bifurcation. The paper's most surprising finding — that different learning rates produce qualitatively different algorithms (Section 5.1.4) — is empirically demonstrated but mechanistically unexplained. A follow-up study would map the loss landscape for the binary successor task: train many models with different learning rates, random seeds, and initialization scales, and characterize the basins of attraction. Specific measurements include (a) the loss barrier between the "recursion head" solution and the "diffuse attention" solution, (b) whether the low-learning-rate model would eventually discover the recursion head if trained orders of magnitude longer (a grokking-like delay), (c) whether the phase transition in attention-head specialization (Figure 6) is sharp (suggesting distinct basins) or continuous (suggesting a single basin with a narrow path), and (d) whether larger models are more or less sensitive to learning rate in their algorithm selection. This connects to the grokking literature (Nanda et al., 2023; Power et al., 2022) and the broader question of why neural networks sometimes discover structured, generalizing solutions rather than shallow memorization.

Automating algorithm reconstruction: training a "mechanistic interpreter" model. The paper's reconstruction process is entirely manual and expert-driven. A more ambitious follow-up would attempt to automate parts of the pipeline: given a trained transformer and access to its weights and activations, train a separate model (or use program synthesis) to output pseudocode that predicts the transformer's behavior on novel inputs. This could be approached as a program synthesis problem — the target program is the pseudocode in Figures 13–14, and the training data is the perturbation experiment results (input modifications → behavioral changes). Even partial automation — e.g., automatically identifying attention heads with boundary-tracking behavior, automatically proposing perturbation experiments to test causal hypotheses — would substantially lower the barrier to applying this methodology to new tasks and models. A strong result would show that automated reconstruction achieves comparable failure prediction accuracy to the manual analysis, and that it transfers across related tasks without re-engineering.

Connecting to chain-of-thought: does explicit intermediate computation eliminate the learned shortcut? The paper notes (Section 1) that techniques like chain-of-thought prompting help for recursive tasks but "why they help is poorly understood." The atomic reduction subtasks for tree traversal (Section 3.2, Appendix D) are implicitly chain-of-thought steps. A direct follow-up would compare the learned algorithms of a model trained end-to-end on full inorder traversal (which fails, Figure 7) against a model trained to output intermediate reduction steps (which succeeds). The question: does the successful model learn a genuinely recursive mechanism (because the reduction steps force it to track recursive depth explicitly), or does it learn a different shortcut that works at the reduction-step granularity? The mechanistic analysis would involve the same attention visualization and perturbation techniques, applied to the intermediate tokens (UNROLL[...] markers) that the end-to-end model never sees. This would provide the first mechanistic explanation for why chain-of-thought helps on recursive tasks — not just that it improves accuracy, but what internal computation it enables or replaces.

Practical Applications and Downstream Use Cases

Diagnosing failures in neural code generation tools before deployment. The paper's methodology — training a model, reconstructing its learned algorithm, and mechanically predicting which inputs will cause failures — is directly applicable to deployed neural code generation systems. For a specific function or API that a code model is expected to handle correctly, a development team could: (1) define the function's intended semantics formally (e.g., as a reference implementation), (2) generate a dense training set of input-output pairs covering the expected input distribution, (3) fine-tune a small replica of the deployed model on this task, (4) apply the attention-and-perturbation pipeline to reconstruct the learned algorithm, and (5) use the reconstruction to identify specific input patterns on which the learned algorithm diverges from the reference implementation. These patterns could then be added to the test suite, used to generate targeted training data, or documented as known failure modes. The 91% failure prediction rate on the binary successor task suggests that, for functions of comparable complexity, this pipeline could identify the vast majority of systematic errors before they affect users.

Curriculum design for training neural program synthesizers. The finding that learning rate acts as an algorithm selector (Section 5.1.4, Figures 5–6) has direct implications for how neural program synthesis models should be trained. At low learning rates, the model learns a fragile token-copying strategy that fails on out-of-distribution depths; at high learning rates, it discovers a robust positional-comparison shortcut that generalizes. A practitioner training a model on a recursive programming task could use this insight to tune the learning rate schedule to favor algorithm discovery: start with a high learning rate to encourage exploration of structured solutions, then decay aggressively once the recursion head emerges (detectable via attention-map monitoring). The paper's Figure 5b quantifies the effect — on depth-constrained training, the high-learning-rate model maintains accuracy above 0.85 on depths 18–20 beyond training, while the low-learning-rate model drops to 0.65. This is a 20+ percentage point accuracy difference driven purely by a hyperparameter choice, with direct practical consequences for the reliability of generated code on unseen inputs.

Verification-guided fine-tuning for recursive functions in proof assistants. The paper's use of Coq-style inductive datatypes and structural recursion (Section 2, Appendix A.2) directly connects to interactive theorem provers like Coq, Lean, and Isabelle, where users write recursive functions and proofs over inductive types. A practical application is verification-guided fine-tuning: given a Coq function definition, generate input-output pairs exhaustively up to some bound, fine-tune a small transformer to emulate the function, reconstruct the learned algorithm, and compare it against the Coq specification. If the reconstruction reveals a shortcut that would fail on inputs beyond the training bound, the system could flag the function as "likely to be incorrectly approximated by neural tools" and either (a) increase the training bound, (b) add targeted training examples at the predicted failure points, or (c) fall back to the symbolic evaluator for inputs matching the failure pattern. This is a lightweight form of neural-symbolic integration enabled by the paper's diagnostic methodology — the symbolic component (the Coq specification) provides the ground truth, and the neural component is monitored rather than trusted.

Lightweight model auditing in safety-critical code generation. For applications where code correctness has safety implications (e.g., generating control logic, financial calculations, or cryptographic routines), the paper's perturbation analysis offers a runtime auditing mechanism. Before deploying a trained model, run the SOR and EOS perturbation experiments (Figures 3c–3d, 4) to measure the model's reliance on positional-comparison triggers. A model with a high perturbation success rate (above 0.8–0.9, like the C=1.0 model in Figure 4) reveals that its control flow is driven by specific, externally manipulable signals — meaning an adversary who can control input formatting could potentially trigger incorrect behavior by crafting inputs with unusual positional structures. A model with a low perturbation success rate (or one where the behavior does not follow a clean pattern) is less predictable but also less vulnerable to this specific class of adversarial manipulation. The perturbation success rate thus serves as an interpretability-derived safety metric — not just "is the model accurate?" but "what specific mechanisms does it rely on, and how easily can they be exploited?" </output>