Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion
Authors: Dylan Zhang
Curt Tigges
Zory Zhang
Stella Biderman
Maxim Raginsky
Talia Ringer
Venue: Accepted by TMLR ()

Abstract: This paper investigates the ability of transformer-based models to learn structural recursion from examples. Recursion is a universal concept in both natural and formal languages. Structural recursion is central to the programming language and formal mathematics tasks where symbolic tools currently excel beyond neural models, such as inferring semantic relations between datatypes and emulating program behavior. 
We introduce a general framework that nicely connects the abstract concepts of structural recursion in the programming language domain to concrete sequence modeling problems and learned models' behavior. The framework includes a representation that captures the general \textit{syntax} of structural recursion, coupled with two different frameworks for understanding their \textit{semantics}---one that is more natural from a programming languages perspective and one that helps bridge that perspective
with a mechanistic understanding of the underlying transformer architecture.

With our framework as a powerful conceptual tool, we identify different issues under various set-ups. The models trained to emulate recursive computations cannot fully capture the recursion yet instead fit short-cut algorithms and thus cannot solve certain edge cases that are under-represented in the training distribution. In addition, it is difficult for state-of-the-art large language models (LLMs) to mine recursive rules from in-context demonstrations. Meanwhile, these LLMs fail in interesting ways when emulating reduction (step-wise computation) of the recursive function.

Published in Transactions on Machine Learning Research (07/2024)
Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion
Shizhuo Dylan Zhang
shishuo2@rllinois.coo edu
University of Blinois Urbena- Chana-ng
Curt Tigges EleutherAI
curt&eeleuther.c ai
Zory Zhang
zory:2@illinois. edu
University of Blinois Urbona- Chanm-onn
Stella Biderman
stella@eleuther.co
EleutherAI
Booz Allen Hamilton
Maxim Raginsky
mazimmillinois. edu
University of Illinois Urbona- Urbona-Champae Champaign
Talia Ringer
tringer edu
University of Ilimois Urbona- Channpng
Reviewed on OpenReview: https: openrrevee.. net/ forum? id= Ry55X211s
Abstract
This paper investigates the ability of transformer-base models to learn structural recursion from examples. Recursion is universal concept in both natural and formal languages. Structural recursion central to the programming language and formal mathematics tasks where symbolic tools currently excel beyond neural models, such inferring semantic lations between datatypes and emulating program behavior. We introduce general con- ceptual framework that nicely connects the abstract concepts of structural recursion in the programming language domain to concrete sequence modeling problems and learned mod- els' behavior. The framework includes a representation that captures the general syntar of structural recursion, coupled with two different frameworks for understanding their se- mantics-one that more natural from a programming languages perspective and one that helps bridge that perspective with mechanistic understanding of the underlying trans- former architecture.
With our framework as powerful conceptual tool, we identify different issues under vari- ous set-ups. The models trained to emulate recursive computations cannot fully capture the recursion yet instcad fit short-cut algorithms and thus cannot solve cortain edge cases that are undeeeeeeeesenneed in the training distribution. In addition, it is difficult for state-of-thr large language models (LLMs) mine recursive rules from in-context demonstrations. Meanwhile, these LLMs fail in interesting ways when emulating reduction (step-wise com- putation) of the recursive function.
1 Introduction
A revolution in neural methods for programming language tasks is underway. Once confined to the realm of symbolic methods, of the most performant. tools for synthesizing (Chaudhuri al. 2021 Chen

---

Published in Transactions on Machine Learning Research (07 (024))
Expression
Expression
Expression
Expression
Expression
Expression
+ Expression
7
7
x
5
7x5
+
(6x8) + (9+1)
(a) Recursion in an expression. Assume binary operators '+' and 'x'. An expression can be number two expressions connected by '4' two expressions connected by 'x?
Alvin enjoys fishing.
Alvin, who studies in Chicago, enjoys fishing. Alvin, who studies in Chicago, which is city on Lake Michigan, enjoys fishing.
(b) Recursion in natural language. This nesting of clauses is classic example of recursiveness in a sentence, demonstrating how language can be structured in increasingly complex ways.
Figure 1: Some examples of recursive patterns.
et al.
2021
Li et al.
b022b Chowdhery et al. 2022). repairing (Gupta et al., 2017 Saha al.) 2017 Xia
et al. 2023). and even formally verifying (Agrawal et al.) 2023 Yang & Deng 2019 First & Brun 2022; Sanchez-Stern et al. 2023 2020
First et al. 2023 programs now rest in part or in whole upon neural
foundations.
But how sturdy are these foundations? At the core of many of these tools are transformer- based large language models (Chen al.) 2001 Chowdhery et al.) 2022 First et al.) 2023). It is an open question what degree these models are simply repeating program syntax, and to what degree they have some model of program semantics how programs behave and what they mean. Recursive programs are one class of programs for which program semantics are especially useful and interesting. In fact, recursion is fundamental across many different disciplines beyond program semantics: It is fundamental to parsing program syntax (Figure Tab and omnipresent in natural language (Figure 1bp. Tt is also fundamental to logical reasoning and mathematics the formal definition of the original Peano natural numbers, for example, is recursive in that it has a base case "one" and recursive "successor" function, where the successor any natural number is also a natural number.
In this paper, investigate the degree to which transformers-basel models (Vaswani et al. 2017 learn to model particular kind of recursion. In doing so, we join long line of work that studies the representation capabilities of ML models through formal language lens. The close connection between formal languages and neural network systems can be traced back to the early chapters of computer science (e.g., one key purpose introducing regular expressions by Kleene et al. in 1951 Kleene 1951 was to understand the nerve nets (McCulloch & Pitts 1943)).
Due to the omnipresence of recursion, in broad sense, transformer-based models are already used solve problems that rely in some way recursion. However, these models are occasionally observed to fail in cases that demand strong understanding of recursive structures. For example, models trained for programming tasks may misunderstand programs with nested blocks or produced imbalanced brackets. This highlights the necessity of examining the ability of machine learning (ML) models to capture recursive patterns, especially in a world where ML-assisted programming and mathematical reasoning are growing at explosive rates.
Our work focuses particular on structural recursion: a restricted but powerful class of recursive functions that are defined in structurally decreasing manner, and so must terminate. A program is an example of structural recursion if it is defined over some data structure (say, binary trees) by recursively calling itself over smaller substructures (say, left and right subtrecs). Structural recursion is at the heart of important programming and formal theorem-proving tasks (which are important in software verification and mathe- matics) for which neural methods st.ill lag behind symbolic methods, like inferring semantic relations wetw datatypes (Ringer et al. 2021 Ringer 2021
The difficulty of learning tasks similar to the structurally recursive ones we are interested in has manifested in prior work. For example, Zhang al. (202bb) identify "statistical shortcuts" simple propositional
2

---

Published in Transactions on Machine Learning Research (07/2024)
logic, where the model fits statistical features instead of the correct reasoning steps. van der Poel et al. (2023) observe failures of neural networks on certain types of cases for regular languages, an even simpler class of formal languages than those we are interested in. Our work identifies the root of similar brittleness in the context of structurally recursive functions by further reconstructing the algorithms emulated by the learned models that lead to those errors.
Our contributions are twofold: First, we introduce general framework for representing and rea- soning about structural recursion with sequence models. Second, we use our framework to conduct an empirical investigation of learned models' algorithmic behaviors recursive tasks. Our framework and empirical results are important steps towards understanding how to better handle recursion with sequence models, paving the path towards better and more reliable performance on the wealth of tasks to which recursion is fundamental.
structurally
Contribution 1: Conceptual Framework
Our first contribution is a comprehensive and general conceptual framework for modeling structurally recur- sive tasks in a way that makes it possible to analyze sequence models (like transformers trained or prompted to execute recursive computation) used to solve those tasks (Section 2 The goal of this framework is to help us connect the world of ML with the world of programming languages, so that we can clearly define what it means for sequence models "learn to represent structural recursion."
To that end, our framework reasons about both the syntor (form) and the semantics (meaning) of structural recursion. Our framework supports syntax by way of a new sequential encoding (Section 3 based on inductive representations of recursively defined datatypes. Our framework supports semantics by way of both (a) a stepwise reduction semantics (Section 4.1) and (b) an Abstract-State Machine (ASM) semantics (Section 4.2 The reduction semantics helps us bridge the syntax with the traditional programming language semantics of that syntax; the ASM semantics makes it possible to interpret and analyze the algorithmic behavior of learned models in implementing those semantics, even when those models are not architecturally recursive.
Our framework takes into consideration the following complexities: Transformer models are not architec- turally recursive-the they do not call themselves. The situation can become even more complex when consider- ing pre-trained LLMs, which are more than mere architectural frameworks they are sophisticated systems enriched with knowledge and capabilities acquired during pre-training. In-context learning capabilities of these models add even more complexity to our goal of reasoning about recursive problem-solving capabilities. For these reasons, we design our framework be comprchensive and adaptable, with the general principles allowing us to abstract away the complexities and focus just the concept of recursion.
Contribution 2: Empirical Investigation
Our second contribution an empirical investigation of sequence model behavior on structurally recursive tasks, using our framework as basis. We instantiate our framework different variants of two concrete structurally recursive tasks: (a) learning the binary successor function (Section 5.1 and (b) learning various tree traversals (Section 5.2). We have chosen these tasks to be simple in that they demand minimal prior knowledge from the model, yet interesting since they capture nontrivial recursive structure.
Guided by our semantic framework, we design (Section 6 and conduct (Sections and experiments to better understand the behavior of small transformer models trained from scratch on variants of these two tasks. As bonus, we also bricfly investigate the ability for pro-trained language models to learn the recursive algorithm for one of these lasks from fine-tuning (Section 9 Finally, we analyze the in-context learning paradigm with LLMs (Section 10
Our results are multifaccted. On small transformer models trained from scratch, we reconstruct the learned algorithrm and find specific non-recursive shortcuts that these models take. From there, we are able to reverse engineer failure cases and understand the weaknesses of these models. Our findings suggest that transformer models trained on input-output pairs do not fully encode the recursion semantics for these tasks. Rather, they fit shorteuts pruned to edge cases, despite the possibility of constructing a transformer model to solve it up to bounded length (Pérez al. 2021). We use these insights to mitigate these failures.
3

---

Published in Transactions on Machine Learning Research (07/2024)
Our fine-tuning experiments highlight potential practical issues with tokenization and pre-training data. We find the code-LMs (e-g., Code-T5) outperform general-purpose LMs with the same architecture. Tn the in-context learning paradigm, these weaknesses persist. Our exploration of LLM performance on these tasks (like GPT-3.5-turbo and GPT-4) shows these models' inability to mine and exccute the corresponding recursive algorithms from in-conlext demonstrations. Our exploration also identifies common patterns of erroncous behaviors for these models. We find that. LLMs struggle to find the correct rules from in-context examples and fail in interesting ways when performing in-context step-wise reduction (producing the trace of intermediate computations), like failing to terminate executing incorrectly, Taken together, results help bridge the theory and practice of learning recursion (Section 11
2 Framework
At the core of our work is conceptual framework designed to systematically investigate the capabilities of models, specifically sequence models, in performing structural recursion. We first define our framework for reasoning about structural recursion (Section 2.1j, then describe how we apply it (Section 2.2 Throughout, we reference Figure 2 which shows how all of this comes together.
2.1 Defining the Framework
Sequence models such as transformers have demonstrated remarkable capabilities in capturing patterns and dependencies in data. To delve into their ability to handle structural recursion, we separate the problem into its two core facets: syntax and semantics. Syntar refers purely to the form of a program (which strings of characters comprise a valid program), while semantics refers to its mcaning. Our conceptual framework for representing structural recursion encompasses both of these and how they interact, which is crucial for a thorough analysis.
Representing Syntax For Sequence Models: Sequential Encoding The first challenge that our framework addresses is representing the syntax (form) of structurally recursive datatypes (like binary trees) and functions (like tree traversals) sequentially, in a form that is amenable to sequence models (Figure 2 top left). This involves mapping recursive structures to linear sequences while preserving the underlying relationships and the synlactic hierarchy. We do this a highly general way by introducing sequential encoding adapted from the programming languages literature. The trick is to represent inputs and outputs of structurally recursive functions in terms of the language used to inductively construct those inputs and outputs-a trick will describe in detail in Section 3 By doing so, bridge well-unerstood representation of structural recursion in programming languages with the requence-bssed paradigm of transformers, setting the stage for a detailed exploration of their capabilities.
Representing Semantics: Bridging two Worlds The second challenge that our framework addresses is representing the semantics (meaning) of structurally recursive functions in a way that helps us understand the learned behavior of sequence models trained on input-output pairs of syntax (Figure 2 top right). This involves bridging the common semantics of programming languages with semantics that model behavior. The gap between these is too wide to consider just one semantic model, so our framework considers two. Briefly, the first semantic model is stepwise operational semantics that models the symbolic reduction behavior of the programming language from which we build our syntax, while the second model uses Abstmact State Machines (ASMs) to bridge reduction with the learned behavior of the non-recursive neural models we train. We describe these both in detail in Section ] This approach of one syntax with two semantics makes our framework useful for reconciling symbolic and learned neural behavior for structurally recursive tasks.
elucidate
2.2 Applying the Framework
We apply our framework to create representative structurally recursive tasks and use our syntactic represen- tation to generate data for those tasks, then use our semantics make sense of qualitative and quantitative evaluations for those tasks.
4

---

Published in Transactions on Machine Learning Research (07/2024)
Syntax (form)
Semantics (meaning)
How fruin the problets as segbbce taak?
How de we craming the "recursive problcts salving" abilit?
Sequential
Operational Semantics: Reduction
Semantics model-leamt program:
encedig
dets
How structural recuraion meant be computtd
Abstract State Machine
Icazch "3" (acazch L-"
conceptiaal tool to view leamned model 45 program to analyard at ape distraction level
Presending
XB
x1
(01
-24 xa
xi3
x0 x0
model recogrize
recuring?
Tisks
Linoar
Regreenntativn
Analysis Approaches
depth)
taak
Dinary Successsor
Gradient- Based Training
shw-shot Learning
Inispectatioo
Atalycic
Recuraion
Structural
Counterfactual Patching
Pertrtattion
Brecution enuiste stip-wtse
reduction
Tree-iike (Mulliglo recuriive calla dupth)
Representative
Tree Traversals
Quanitation perfiemanee under differess
task
Questions Want To Answer
Mitigations
Representation: What program are they representing"
Is the learned program recursive? Is learned program correct!
Model learzed algurillame
edge Diste
Capacity: Are they able to regresent a proggrm well?
Scale
Execution: How well do they execute?
Why did the model fall?
Figure 2: An overview of our framework for reasoning about sequence model performance on structurally recursive tasks, and how we apply it in this work.
Applying the Syntax: Tasks and Data Our approach to contextualizing the transformers' proficiency in recursive computations is anchored in how we apply our framework's syntax to syuthesize the training and testing data (Figure D center left). Specifically, we use the sequential encodings we have defined to craft the input/output (I/O) examples for our data. This construction of I/O examples concretizes the use of the syntax in practical experimental context, allowing to later our framework's semantics make sense of the experimental results. We instantiate this framework on two simple but interesting classes of tasks: learning a binary successor function (one recursive subcase) and learning various tree traversals (multiple recursive subcases). We describe these tasks in more detail, along with how we instantiate our syntax to
these tasks, in Section 3
Applying the Semantics: Evaluation Finally, we use our framework's semantics to interpret the be- havior of learned models on these tasks (Figure 2 center right). For a task that involves learning a particular structurally recursive function, our framework gives us the desired behavior desired behavior using stepwise operational semantics- standard way of describing semantics for programs in a programming language. The challenge is bridging this with the actual learned behavior of the models trained on T/O examples. To do this, we adopt the ASM framework to reconstruct the learned "algorithm" at similar levels of abstraction to the desired recursive program. We can then analyze the learned model by looking at two key aspects: (1) the semantics of the program represented by the learned model and (2) its precision in executing that program. We devote particular attention to model behavior in edge cases, which serve as stringent tests of the robustness the learned attempts to solve structurally recursive problems. These tell us where the models are currently falling short.
3 Representing Syntax: Sequential Encoding
The first component of our framework sequential encoding of structural recursion, which is a method of representing data in sequence that retains its recursive structure. This approach helps us organize data points in way that maintains their inherent recursive properties. The sequential encoding in our framework represents inputs and outputs to structurally recursive functions in terms of sequences of constructors of inductive types (Section 3.1 While these inductive types are not a new concept, our key insight is to use them to build a conceptual framework that grants us independence from character representations and underlying associations a model may have learned, and it general enough to sequentially encode trees, language grammars, and even type chockers (Section 3.2 Furthermore, aligns with the well-studied semantics of functions over these datatypes, which will be advantagcous when we define the Section All of this makes it perfect for exploring structural recursion in sequence-to-sequeeee model.
5

---

Published in Transactions on Machine Learning Research (07 (2742)
Fixpoint add (n peano) peano
Inductive peano
match n with (+ break into cases *)
I peano (+ base case +)
I => S (+ if is one, return S m +)
v (n peano), peano. (* inductive case *)
S p => s (add p =) (* otherise, recurse +) end.
(a) Inductive type for the Peano natural numbers.
(b) Addition using structural recursion.
Figure 3: Representing the Peano natural numbers using an inductive type, and writing structurally recursive function defined over that type.
3.1 What: Inductive Types
Summary: The representation uses the concept of induction. Think of each data point as being constructed from one or more base cases by applying inductive steps. In this way we can encode the recursive structure into sequence representation.
Our sequential encoding employs the synlax of inductive lypes. An inductive type way of representing a datatype in terms of all ways of constructing elements of those types- itss constructors (Coquand & Paulin 1990). There are two main kinds of constructors: some of those constructors have no recursive references to the type itself-these are called base cases. Others include recursive references to the original datatype- these are called inductive cases. These types also come equipped with eliminalors or induction principles that make it possible to write structurally recursive functions and inductive proofs about those datatypes.
As an example, suppose we would like to train a model to approximate the behavior of a structurally recursive function that adds two Peano natural mumbers. We start by defining the datatype representing those numbers
inductive type in Figure 3a (the syntax here comes from widely-used proof tool called Coq (Bertot & Castéran 2013)) This inductive type describes how to construct an instance of Peano natural number. There are exactly two cases: (1) a single base case that constructs the natural number one (denoted I), and (2) a single inductive case that, given some Peano natural number n, constructs its successor (denoted s n).
We can then generate I/O examples train model to approximate an addition function defined over the Peano natural numbers by using a reference addition function as ground truth. In languages like Coq that have these inductive types, can write functions (and even proofs) about these datatypes using pattern matching and terminating (structurally decreasing) structural recursion (or, equally expressively, induction). We write the reference addition function this way in Figure 3b)
Before we describe the behavior of this function, there are a few syntactic points to clarify about the language we are using: first., Coq uses parentheses only for grouping, not for function calls, so what in Python would be written add (p, m) is here written add p m. Second, the match statement breaks into cases based on the structure of the input: the base case and the inductive case The variable p that comes after in the inductive case is arbitrary, and matches the input, if you pass in S (two) then p will bind to I (one), and so will have that value in the recursive to add p
What that in mind, the behavior of the add function is as follows: We are given input numbers n and m. We break into cases based on the structure of n. In the base case, when n is I, we get that adding one to m computes the successor- of some other number p. we get that adding the successor of p to m is the same as recursively adding p to m, then taking the successor of the result- that. is, add (s p) m computes to (add p m).
is, add computes to m. In the inductive case, when
the successor
As we will see later, can use these reference structurally recursive functions to generate 1/O examples to train our model. For example, if we call the add function on S I and S (S (S I)), we get S (S (S (s (S I)))); in other words, 2 4 6.
CCoq was used verify the ACM award-winning CompCert Leroy et al. 2016 Compiler for C.

---

Published in Transactions on Machine Learning Research (07 (07/2024)
3.2 Why: Independence and Generality
While the Peano natural numbers are quite simple to encode sequentially without this gemeral encoding, it turns out that we can use this same inductive representation to sequentially encode more interesting data types like binary trees and language grammars. We can also use it to draw a bridge between expected and actual model behavior and to generate I/O examples to train and test a model. What makes this choice of sequential encoding shine is its independence from specific character representations (Section 3.2.1 1 and its generality (Section 3.2.2
3.2.1 Independence
Summary: The arrangement of tokens already fully encodes the structure. How we spell these tokens does not matter.
One nice thing about this encoding and data generation process is that it is fully independent of specific character representations and any preexisting associations (for example, to numbers or trees) that model may have learned; what call these datatypes is irrelevant. We could just as well rename peano to dinosaur, to shampoo, and S to pencil:
Inductive dinosaur shampoo dinosaur (+ base case +)
pencil Y (n dinosaur), dinosaur. (* inductive case +)
and then we could add dinosaurs.
This independence makes this representation interesting from the perspective of investigating how models trained to learn structurally recursive functions perform without worrying about possible associations with characters that particularly important for experiments the small transformer models that train from scratch. But it will be very important when consider the behavior of pre-trained language models similar tasks, model that has already learned associations with, say, numbers, may have misleadingly strong performance numeric task despite not learning the structurally recursive behavior we care about. Thanks to this independence, we can control for said associations and know when performance is truly meaningful.
to-oouuue--- model may have picked up on from other training data. It will not be
3.2.2 Generality of Sequential Encoding
Summary: This sequential encoding represents complex data types and functions while preserving all necessary information.
So far, the example of peano natural numbers has been quite simple. But it turns out that this simple representation is highly general. It corresponds to broad class of datatypes well studied in programming languages, making it simple for to define important recursive tasks. It lets represent binary trees and even entire programming languages- all sequentially.
Binary Trees First we consider encoding the type of binary trees. We start with binary trees that store character values in their nodes. We can write this type as follows:
Inductive tree
Leaf : tree (+ base case: empty leaf +)
Branch (v char) (1 rr: tree) tree (* inductive case: branch with character value & two subtrees +)
That is, a binary tree is either an empty Leaf, or it is a Branch that stores a character value and two subtrees: the left subtree 1 and the right subtree r. We will show functions defined over this type in Section 5
The thing notice for the tree type is that, contrast with the peano example, the inductive Branch case has two recursive references to the datatype one corresponding to each subtree. In other words, binary

---

Published in Transactions on Machine Learning Research (07/2024)
trees are not naturally sequential in the way that unary Peano natural numbers are. Still, by using this syntax, we obtain sequential encoding. For example, we can represent tree with 'aa at the root, 'e? in node to its left, and 't' in node to its right as follows:
Branch (Branch ' Leaf Leaf) (Branch 't' Leaf Leaf)
where 'a', ' and 't' are characters that is, terms of type char. This is a sequence.
It is worth noting that, using this syntax, could also generalize this type to represent trees with any kind of value, not just characters:
Inductive tree (A Type) :=
Leaf : tree A (* base case: empty leaf x)
Branch (v A) (1 tree) tree A. (+ inductive case: branch with value & two subtrees +)
This represents kind of polymorphism (in this case, types that depend types) (Cardelli & Wegner 1985 insofar the type tree depends on the type Here, is the type of the value v stored in the nodes. There are infinitely many ways to instantiate A for such datatype, which makes this extremely expressive-we can use this type to derive trees of characters (tree char), trees of Peano natural numbers (tree peano), trees of trees of characters (tree (tree char)), and so on.
For our purposes, is worth noting that this expressiveness comes at a cost the ease of data generation. After all, could also instantiate A to be an uninhabitable type like False. In such case, the only constructor could call would be Leaf. In fact, knowing if we ever invoke the Branch case of a tree A without knowing anything about A is undecidable problem, one as general as arbitrary proof search in a higher-order logic, It is for decidability of data generation that, for the binary tree tasks in Section 5 we will stick with the first definition of tree and consider only character values. Still, in the remainder this section, we will show two more examples that highlight the generality of types one can express with this sequential encoding, even when it comes at the cost of decidable data generation.
Programming Languages Those who are familiar with language grammars might see a similarity be- tween these datatypes and the ways one might represent the grammar of formal language. Indeed, is typical to encode abstract syntax trees corresponding to parsed programs for context-free languages using these datatypes. Consider, for example, the untyped lambda calculus:
<expr> ::- <expr> <expr>
x <expr> x (<expr>)
We can encode a datatype for abstract syntax trees for this grammar inductively:
Inductive expr
App expr -> expr -> expr e1 c2 +) Lam char -> expr -> expr (* X x. c)) Var char. (+
We could write structurally recursive functions over this datatype, like an interpreter for this small but Turing-complete language that this grammar represents syntactically. (Such an interpreter would need to be structurally decreasing over some commonly some natural number representing unbounded "fuel" the interpreter takes and therefore terminating.) The abstract syntax trees for programs in that language would still be expressible sequentially, and could even be generated by enumerating the datatype (up to some size bound for the sake of termination). For example, the w-combinator infinitely recursive program:
(x x x) x
would be represented as: App (Lam (App (Var 'x') (Var 'x)))) (Lam 'x' (App (Var 'x') (Var 'x')))
Thus, we could use this syntactic representation encode the abstract syntax trees corresponding to arbi- trary inputs and outputs to train model to approximate interpreter for Turing-complete programming
8

---

Published in Transactions on Machine Learning Research (07/2024)
language. The trouble, of course, would be that would need to supply the necssarlly-temminatnn in- terpreter with some "fuel" representing for how long it should try to interpret potentialy--onternnnnill input program before giving up.
In fact, we can get even fancier we can also use this representation to encode relations over datatypes. Notably, these relations can encode things like the operational semanlics of a programmiing language, and can be used to prove correctness of an interpreter like the one above. They can also encode well- typedness relations relations-giving exceptionally general sequential encoding that builds bridges to two well-understood semantic models.
sequential encoding for type derivation trees-and more This gives us
4 Representing Semantics: Bridging two Worlds
We introduce two semantic models: a stepwise reduction semantics (Section 4.1) that represents how recur- sive computations evaluated step-by-step in programming languages, and ASM semantics (Section (.2) that allows to analyze models trained to perform recursive tasks in the way would analyze an al- gorithm. While these semantic models draw heavily on prior work, our key insight is to apply them in our conceptual framework to analyze the ideal and actual behavior of models trained to approximate the behavior of structurally recursive functions.
4.1 Semantic Model 1: Step-wise Reduction
The desired "semantics" (meaning) of the sequential encoding is revealed through step- wise reduction, process by which we compute the output of the recursive function step by step. Examining the models' ability to perform such reductions subtasks allow us evaluate whether they can represent the semantics of structural recursion.
Summary:
Our first semantic model maps function inputs and outputs from their synlax (the sequential encoding from Section 3 to their corresponding semantics in the programming language from which we borrow that syntax. In the broader framework, this represents the desired behavior a learned model structurally recursive function, though its utility limited for understanding the actual learned behavior.
Our semantics of choice model the reduction behavior of a function applied to its inputs-a kind of evaluation behavior. We consider in particular a small-step operational semantics corresponding to this reduction behavior-that is, semanties that specifies how to reduce (evaluate) function applied to its inputs one step at a time, until what left cannot reduce any further, at which point we have the outputs (Section[4.1.1 Importantly, this helps us decompose the task of learning the structurally recursive function into smaller pieces, making easier to bridge theoretical and empirical behavior (Section 4.1.2).
4.1.1 What: 83t-reduction
At high level, the semantics operate in terms of reduction rules (named after various Greek letters) that describe how to reduce programs that take different forms (Chlipala) 2013). There are three reduction rules are relevant to this paper:
5-expansion unfolds a constant and replaces by its definition.
2. 3-reduction applies function to its arguments.
3. i-reduction chooses the appropriate case of pattern matching.
To turn these reduction rules into an operational semantics, we apply the reduction rules one at time until there are no more rules to apply: this is called 6f1-reduction. Note that, in our language of choice,
We refer interested readers the Software Foundations book series PPerce datatypes for relations, along with the challenges these relations introduce to data generation.
2024 understand how

---

Published in Transactions on Machine Learning Research (07/2024)
structurally recursive functions must terminate, do not have to worry about reduction continuing forever. Note also that the question of evaluation order of these steps does not matter in this language but of course must be handled in any implementation. These semantics are well understood already, and for that we refer the reader to the relevant literature (Krivinc 2007
For example, consider evaluating the function from Figure 3b Section 3.1 Suppose that we call add on the inputs and to compute 1. Using the three rules above, we can compute what we will call one "step" of computation for the sake of this paper (we take some liberty with these steps for the sake of presentation):
add 50 (add I)
This unfolds add, applics it to its two arguments S I and I, and then chooses the appropriate case. More granularly, we have:
(fun peano
match I) with
match n with
add (s I
4
I => S I
=> S (add m) 4. (add I I)
p (add p m)
end
end) (S I) I
We can keep going. Composing the same three steps again, we get:
(fun peano match with
8 (match I with
(add I I)
4
=> S m
4
S => S (add p m)
=> SI
4 (S D)
S p => S (add p m)
end)
end)
Hence:
add 1) 6gc
49.
(add I)
(S 1)
Note that here, we cannot reduce any further we are done computing. This means we can say that, in some number of steps, add (s I) I evaluates to (s I). We represent this using the transitive closure of the step relation, denoted:
53c
add (S 1)
S (S I)
In other words, 2 + 3.
4.1.2 Why: Task Decomposition
Using a well-understood programming languages semantics of course helps us draw bridges between desired and actual behavior of the models we train. But this particular choice of semantics has an additional benefit it allows us to break down the larger task when models struggle. The key to this is that, for every function we wish to model, can train models for two variants of the same task:
53c *, and
one representing the transitive closure on the step relation
60.
one representing a single step at a time
For a given task, the first task variant represents training a model to learn the end-lo-end computation behavior of the chosen function, while the second task variant represents learning a single computation step at time. When the model succoeds the first task variant, the second task variant not very important. But when the model struggles with the first task variant as we will see for the tree traversal functions later on- on-this lets us break down the task into simpler subtasks.
10

---

Published in Transactions on Machine Learning Research (07/2024)
In other words, we can think of the computation of structurally recursive functions reduction (a single step) and composition (the transitive closure). So it is natural to ask-when a model struggles to approximate a structurally recursive function, where does it go wrong? Can it perfectly approximate a single reduction step? Can it compose two reduction steps? What about three? At what point does performance docay?
This choice of semantics gives us a way to answer these questions empirically. It. also allows us to bridge the theoretical with the empirical can we build transformer models from scratch that perform a single reduction step? Can build transformer models from scratch that compose the right mumber of reduction steps? Need that number be fixed in advance? And how does this relate to what observe empirically?
We will employ this semantic model in Section b to motivate our choice of task variants that we investigate and the different ways we investigate them. All of this helps us understand the desired behavior; the second semantic model will help us relate that to the actual learned behavior of the models we train.
4.2 Semantic Model 2: Abstract State Machines
Summary: Our ASM-based semantic framework is a powerful conceptual tool view a trained model as a program. By choosing the appropriate level of abstraction, it allows us to ignore the low-level "implementation" of the program, and instead focus the essential aspects that are useful for mechanistic analysis of programs. This unifies the analysis of different models under different setups (c.g., prompting). Morcover, any mechanistic interpretability analysis involves working with an ASM al some appropriately chosen level of abstraction.
To answer the question of whether a neural model has "learned" structural recursion, an important step is to (at least approximately) recover the semantics of the model's learned algorithm. This is nontrivial undertaking-ght given the complex nonlinear computations both during and after training, it is challenging to understand, interpret, and verify the exact algorithm or process the model has learned. Consequently, it is challenging to ascertain whether the model has truly learned structural recursion.
Transformer models, by architectural design, are not recursive. We thus cannot expect to easily analyze a transformer the (relatively low) level of abstraction of internal activations and model parameters. Furthermore, there are data-driven learning paradigms that even more challenging to reason about, such in-context learning (by demonstration instruction) in LLMs. Our ASM framework addresses these challenges and gives us a unified way to reason about learned model behavior.
4.2.1 Concept of Abstract State Machines
The notion of an ASM |Gurevich 1995 Börger 2005 has emerged a crucial tool in the world of formal methods, offering a structured yet adaptable framework for modeling of systems and algorithms. An ASM is a particular extension of the Finite State Machine (FSM) model. An FSM is writlen as: FSM out, 8, w) if defined(in) then = 5(S, in), out == in,
where S is the machine's state taking values in a fixed finite set of states, 8 the state transition function, and w is the output function. An FSM has only 3 locations to be read or updated: in, S, and out. An ASM, in contrast, extends the notion of an FSM by admitting infinite state spaces under certain structural restrictions (see below) and by allowing the machine to read and update arbitrarily many, possibly parameterized, locations whose values can be of arbitrary type, and to have arbitrary conditions as rule guards (not only input definedness) at cach step. The basic structure of an ASM is finite set of rules of the form:
if Cond then Update
At each time step i, it decides all the executable rules (i.e., those cases where the Cond is true), then performs the updates under those logic blocks.
Coneretely, the states of an ASM are general first-order Tarski structures (Bergman 2015 of the form (U. fu..... fL), where U denotes the algorithm's universe that contains constants such as true, false, undef, and fi U.. - U is finite set of functions. Some of the the functions ft may be partial Boolean
11

---

Published in Transactions on Machine Learning Research (07/2024)
functions; they can be turned into total functions using the standard technique of setting fi(u,..... Uns) to undef whenever the value of f at the input tuple (#1,..., Wn;)) is undefined. The purpose of these Boolean functions is to handle flow control via conditional execution according to the rule template shown above.
The generality of the definition of states is the most important aspect of ASMs. The first-order Tarski structures at their foundation represent the most general notion structure that can model various structures of mathematies, abstract data types, and even key concepts of object-oriented programming like classes, It is broad enough to provide the ficxibility to view a program a system at different abstraction levels, giving the freedom to analyze the behavior characteristics of interest as long as one can fit the system at that abstraction level into the framework and inspect the state transitions implemented at that level.
In other words, according to the ASM framework, a suitable computation model should (1) operate at the same abstraction level as the original algorithm, (2) implement its computation through state transitions or updates, and (3) exccute only a bounded number of instructions from a fixed set for state updates. ASMs satisfy these criteria and so form a perfect foundation for our second semantic framework.
4.2.2 Recursive ASMs
In this paper, we are concerned particularly with the behavior of a class of recursive programs. In this light, it makes sense to consider Recursive Abstract State Machines (RASMs)-est extensiiosn of ASMs that are specifically designed to capture recursive algorithms and processes elegantly. At the level of our framework, ASMs allow us to consider the actual behavior of transformer models as programs; RASMs help us inspect whether there is anything resembling recursion that happens inside of these programs.
The definition of a RASM built on top of the definition of a sequential ASM (Börger Schewe 2020). A recursive ASM, from high level, can be expressed the form of "lct-in" statements, each of which invokes sub-machine that performs certain computations and directly updates the global state by returning values. This description blends in the concept of stateless recursive calls in functional programming to characterize the machine that performs recursive computation [Börger & Bolognesi 2003
For example, a quicksort algorithm written as follows:
QUICKSORT(L)
if | < then result L else
let
T = QUCCKSORT (Dbec)))) y = QUICKSORRT(allL))2aaada
result concatenate(z, head()))
It provides a natural sequentialization of the computation when abstracting away the actual implementation of the QUICKSORT sub-machine, the procedure becomes "evaluate conditions, compule some values, and pass on the values to continuation."
This yields the opportunity to examine whether a sequential model (in our case, a transformer with an auto-regressive decoding mechanism) implements recursive algorithm by inspecting the model's internals at each time step, and determining whether those internals reflect the sequence of computations needed in the recursive algorithm by an ASM.
4.2.3 Why ASMs?
ASMs form an appropriate basis for analyzing the behavior of learned models since they provide a com- putational model encompassing the original recursive implementation and its approzimale simulation by a learned transformer network. ASMs are perhaps not an obvious choice for a computational model, but they are crucial to preventing loss of interpretability. In contrast, what we at first considered to be the more obvious choice methoodoloyy--sttaaing situating the original recursive implementation at an appropriate level in the usual hierarchy of formal computational models and then investigating the ability of transformers to
12

---

Published in Transactions on Machine Learning Research (07/2024)
simulate the models at that abstraction.
not capture the relevant aspects of the problem at the right level of
To see the loss of interpretability inherent in the above methodology relative to the ASM framework, consider modeling a function that computes the successor of a binary number. We can write a reference function for this by structural recursion quite an elegant way, as we will see in Figure $ in Section 5.1 We can define binary natural numbers inductively in just three cases, and define the successor by pattern matching over those three cases. Just one case requires recursive computation.
It is natural to consider constructing an iterative implementation of that recursive function using a stack, and then instantiating this iterative implementation using a Turing machine. This is doable. However, the inevitable (and unfortunate) consequence is that, since the Turing machine implementation operates at a much lower level of abstraction, the original recursive definition's 's elegance, parsimony, and interpretability are lost. One can appreciate this loss of interpretability by noting that, even though both the recursive and the Turing machine implementations of binary successor admit finite descriptions, it is much harder to infer program semantics from the latter than from the former. The ASM framework does not have this problem.
Another benefit of the ASM framework is that it allows us to analyze transformer models without needing a persistent state structure. Note that transformers do not implement stacks to trace recursion; instead, they are sequence models by construction. The ASM framework naturally captures this sequential structure without persistent state.
4.2.4 Analyzing a Learned Transformer Model with the ASM framework
In the case of analyzing transformers, the universe, U, can potentially include various datatype, from real matrices to token- and positional embeddings, while the functions f. might encompass operations ranging from matrix multiplications to transformer network building blocks (Phuong & Hutter 2022: Weiss et al. 2021).
A practical example of this ASM-style update within transformers is the one-step decoding. In this process, given the string of imput tokens (M1,...,,Wll and the current context (V1,..., Pk), ) a probability vector P for the next token is produced. The next output token Uk+1 is sampled from P, thereby determining the subsequent token in the sequence. The context is then updated to incorporate this new token, resulting in (vi,..., 2k+1). This explicit representation of the one-step decoding process underlines how each decoding step in transformer parallels an ASM update.
Two noteworthy ASM characteristics are finite instruction set and potentially infinite state. From this viewpoint, amalyzing algorithms implemented by learned transformers entails searching for their pattern classifiers, analyzing the resulting if-else structures, and identifying the functions applied in cach situation at every time step. A simple illustrative example of such a procedure would be "if {the sequence to be generated is complete] then generate [EOS] token." We omitted the underlying computation of the token probabilities inside the transformer model but only focused on the state where some boolean guards of 'sequence generation complete' are evaluated to True, and the state transition controlled by it, which is closing the generated sequence with [EOS].
ASM analysis can be performed in a lower level of groups of model parameters (e.g., attention heads, embedding layers, etc.) to view the model as a system and analyze how the model utilizes different parts to implement the computation. In fact, the popular concept of mechanistic interpretability, which assumes the model learned to implement some algorithm and attempts to reverso-cngincer that, is exactly an excrcise of ASM-style analysis of the model.
In this work, the demonstrations of 1/O pairs provide a partial eztensional 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. We therefore adopt various techniques to reconstruct the ASM implemented by the model. However, in cases where accurately identifying the entire ASM implemented by the model is impossible, one could test whether the boolean guards for the invocation of recursive rules or for a neural network model, a pattern classifier, can be found as a necessary condition of the recursiveness of the approximated ASM by the model.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Finally, a few comments on ASM, program semanties, and mechanistic interpretability are in order. An ASM description of a program belongs to the domain of operational semanlics, where one analyzes (or reverse- engineers) program by constructing a model of a computer (or a virtual machine) on which the program runs and describing how the program "runs" on this virtual machine (Manes & Arbib, 1986). The structure of the virtual machine model reflects the chosen level of abstraction. This would involve interpreting the synlax of the program as a data-dependent sequence of instructions, which can be thought of as state transformations of an ASM For example, replacing Peano natural numbers with dinosaurs (as in Section 3.2.1 may be thought of as replacing semantics while preserving syntax only if this replacement would also affect the abstract interpreter that. "runs" the program and thus generates its operational semantics. As long as the functional form of the instruction updates is not altered, the replacement of natural numbers with dinosaurs would leave the operational semantics invariant.
Morcover, there is a natural link between operational semantics of programs and mechanistic interpretability OOlh 2022p. This is accord with the distinction between the denotational semantics and the operational semantics ies of program, where the former describes the function implemented by the program from the input- output (extensional) point of view, while the latter provides "reverse-engine engineered" (intensional) view through the lens of a particular kind of virtual machine (Manes & Arbib 1986). In the context of neural nets, the trained Transformer provides the denotational semantics, and the goal of mechanistic interpretability analysis is to furnish an operational semantics grounded in the Transformer architecture. The ASM framework is rather flexible for this purpose and may allow for fairly complicated primitives that come up in formal analyses of programs implemented by Transformers Phuong & Hutter 2022 Weiss et al. 2021
5 Tasks
Now that we have our framework defined, we instantiate to model variants two tasks: the binary successor function (Section 5.1) and a tree traversal (Section 5.2 For each task, we choose:
1. an inductive representation of datatype (like peano) to use for our syntactic framework,
2. recursive function over that datatype (like add) to target for learned semantics, and
3. variants of a learning task to approximate the semantics of that function.
Note that, since our interest in whether the model can learn to emulate recursion, we train each model approximate the function's 's semantics behavior, rather than to explicitly represent the function's 's syntax or form. Nonetheless, for many tasks, it will be important also to reify these functions explicitly as syntax (for example, by synthesizing programs); we leave this to future work.
5.1 Single Recursive Sub-case: Binary Successor
Our first task targets the binary successor function a function that is simple and useful, yet st.ill structurally interesting in that it does not just amount to counting. This task is simplification of common benchmark used for over two decades of symbolic proof automation (Magaud & Bertot 2000 Ringer 2021 The target function for this task is significant in that it entirely grounds binary positive numbers in the semantics of other number formats. In fact, finding something that behaves like this function is both necessary and sufficient for aligning unary (peano) and binary positive natural numbers, then porting functions and proofs between the two number formats (Ringer et al. (021).. Such an alignment non-obvious, since the structures of unary and binary natural numbers are different from one another (Ringer 2021 This makes the binary successor function apt target function for our first task, in that it gets closer to discovering the semantic relations current neural tools struggle to infer.
Datatype Syntax number:
We instantiate our syntactic framework with an inductive definition of a positive binary
Inductive bin_pos :=
14

---

Published in Transactions on Machine Learning Research (07 2022)
Patterm fatching
Fixpoint
XO 01
match n with (+ break into cases *)
01 => xo 01 (* n is one, return two *)
X
01
XO b X1 b (+ the LSB is zero, flip it +)
^
x1 b => XD (s b) (* otherwise, recurse and shift +)
x
X1
end.
X
X1
XO
sIX1 01)
Recursive Case
A
sib)
Figure 4: Code (Ieft) and illustration (right) of pattern matching for binary successor computation.
01 bin_pos (+ base case +)
xo v (b bin_pos), bin_pos (+ first inductive case: shift left +)
X1 : V (b bin bin_pos), bin_pos. (+ second inductive case: shift right and increment +)
That is, positive binary number is either (1) one (the base case, denoted 01), (2) any another positive binary number shifted to the left. (the first inductive case, denoted xo b for positive binary b), or (3) any other positive binary number shifted to the left and then incremented by one (the second inductive case, denoted x1 b for positive binary b).
One can uniquely construct all positive binary numbers by making sequencos of xD and X1 calls on 01. For example, two can be written as xo 01: shift 01 to the left. Three can be written and then increment. Four can be written as XO XO 1: shift to the left twice. And
shift to the left
If we are used to thinking about binary numbers on paper, we might notice that these inductively constructed binary numbers are written backwards. We call this the "reverse" ordering. The "reverse" ordering makes it easy to define funct ions recursively since it is structurally decreasing functions on sequences can be defined in terms of functions on the subsequences that follow. To recover the "natural" ordering we might write on papor, we can reverse the result and remove the Xs. So, for example, xo xo 01 becomes 100 (four).
Target Function Semantics Figure 4 contains the code for the function we target, as well as illus- tration of its I/O behavior our target semantics for this task. We target the successor function which increments any positive binary number by 1. The function matches over the first character (the least signif- icant bit or LSB in short) and increments. first inductive case, given some binary number shifted to the left (xo b), it increments by flipping the LSB from zero to one (x1 b). In the second inductive case, given some binary number b shifted to the left and incremented by one (x1 b), increments by recursively computing the successor of (s b), and then shifting the result to the left (xo (a b)). For example, the successor of eleven (1011, represented x1 X1 xo 01) is twelve (1100, represented as XO XO X1 01), since:
the base case, it increments one (01) to two (xo 01). In the
(X1 X1 01) 8A.
(s (X1 01)) 69
XO (s (XO 01)) 49c
XO
X1
Task Variants We train our binary successor models on I/O pairs representing the computational behavior of the successor function. For inspiration and understanding, it worth thinking through how to learn the binary successor function from examples as a human. We can learn this function from a small number of I/O examples, without invoking knowledge of numbers:
8 01 = xO 01 (xo 01) X1 01
8 (XO XD 01) = X1 XO 01
(X1 XO 01) = XD X1 01
(X1 01) XO 01
(XO 01)
X1
These examples fully represent the three cases. We compose instances using only three symbols: x0, X1, and 01. Heuristics and prior knowledge guide us, considering pattern matching and recursion, and preferring simple functions. We can infer a template, match cases, and fill in the template based on 1/O examples.
Our goal for this task is to see how much of this semantic information a transformer model can learn without the priors we just described- -acur how it represents the information it learns, and where the learned
15

---

Published in Transactions on Machine Learning Research (07/2024)
algorithms fall short. It is because of this that must generate many more than just six examples. In addition to the many examples we generate for this task, we also consider few variants of this task. For example, we train separate models to learn from 1/O examples defined using each of the "natural" and "reverse" orderings separately, to see if the ordering makes a difference. We describe more task variants as well as training details and evaluation results in Sections and
5.2 Multiple Recursive Sub-cases: Tree Traversal
For second and more challenging task, we consider tree traversals. How transformer models approximate the behavior of tree traversals is informative for many important symbolic domains, since tree traversals are at the heart of the symbolic search procedures for programs, games, and proofs. If transformers can approximate tree traversals, this may mean better performance of neural tools for these procedures without the need for a symbolic search procedure to guide the way.
Datatype Syntax The representation of trees was introduced in Scction 3.2.2 As quick reminder, we consider binary trees of characters, whose synlax is represented by the following inductive dalatype:
Inductive tree := Leaf : tree (+ base case: empty leaf =)
Branch (v char) (1 tree) tree. (* inductive case: branch with character value & two subtrees *)
Target Function Semantics We target the semantics of both preorder and inorder tree traversals. An inorder Iree traversal, for example, can represented as follows:
Fixpoint inorder
match t with
I Leaf => []
Branch val 1 (inorder 1) [v] ++ (inorder r)
end.
Here, the base case returns the empty list Q] The inductive case recurses on the left and right subtrees, and composes those with the new value the appropriate order. For example, inorder of the tree:
Branch 'a (Branch 'c" Leaf Leaf) (Branch 't' Leaf Leaf)
from Section 3.2. evaluates to:
(inorder (Branch 'c²) Leaf Leaf) ++ ['a'] ++ (inorder (Branch 't') Leaf Leaf)
which is ['c;; ta'; *t]].
Task Variants As with the previous task, consider the problem of learning these recursive functions from T/O examples. Since the tree data structure is not sequential in its recursive structure (that is, each pass of recursion visits both the left and right subtrees), we introduce additional variants of the task that decompose these traversals into atomic computations and see if those are casier to learn. These atomic computations come from our framework's reduction semantics, decomposing recursion into one reduction step at time. For example, compute:
inorder (Branch 'a (Branch 'c² Leaf Leaf) (Branch 't> Leaf Leaf))
We can run the following sequence of òßt-reductions:
inorder (Branch 'a (Branch 'e² Leaf Leaf) (Branch 't> Leaf Leaf)) AM,
(inorder (Branch 'c. Leaf Leaf)) ++ ['a'] ++ (inorder (Branch 't" Leaf Leaf))
((inorder Leaf) De'] ++ (inorder Leaf)) [aa]] ((iordder Leaf) ['t'] ++ (inorder Leaf)) 88: Pe'; la tt
16

---

Published in Transactions on Machine Learning Research (07/2024)
In our experiments, look at task variants with different numbers of 8,d-reduutions at time: single step like the above, two reduction steps at time, and so on. Our default task variant corresponds to the transitive closure of reductions. This helps us understand to what degree the difficulty stems from inferring the basic reduction computations versus from inferring how to compose these computations. We provide more details as well as results in Sections and
6 Experiment Set-up
We set up experiments training and fine-tuning transformer models for variants of these two tasks (Sec- tion 6.1 We also set up experiments for in-context learning using LLMs (Section 6.2 to perform both rule summarization and output prediction for variants of these tasks. This section describes the set-up for each of these experiments; results are in subsequent sections.
6.1 Training and Fine- TuninT Models
Our experiments training the toy models from scratch and fine-tuning pre-trained language models both used the same basic experimental set-up with a few differences. This section descríbes the models we trained (Soction 6.1.1,, the training and evaluation data we used (Section 6.1.2). and additional training details (Section 1.1.3
6.1.1 Models
For each of the two tasks and their variants, we trained toy transformer models from scratch. For the binary successor task, additionally finc-tuned pre-trained language models.
Toy Models Though our framework is applicable to different architectures and modeling paradigms for sequence modeling, we focused primarily on encodor-decoder transformer models which demonstrated the strongest length generalization abilities in our set-up (see Appendix B]. Our default transformer models for the binary successor task were encoder-decoder transformer models with two encoder layers, two decoder layers, a hidden dimension of 128, and heads. The default model for tree traversals are also two-layer, two-head transformers, but with hidden dimension of 256. For simplicity of the mechanistic analysis, we used sinusoidal positional encoding and greedy decoding.
Pre- Trained Language Models For fine-tuning pre-trained language models, we focused primarily on encoder-decoder models, but also fine-tuned a decoder-only model. For the encoder-decoder models, we used T5-small (Raffel al. (2020b) and T5-base, CodeT5-small (Wang et al. (202)), and ByT5-small (Xue al. 2022 For the decoder-only model, used GPT-2 (Radford et al. 2019)
6.1.2 Data
We used the same training and evaluation data for training the toy transformer models and for fine-tuning the pre-trained language models. We generated the data for these experiments using the reference functions for each task, with strategically chosen train/test splits.
Binary Successor For binary successor experiments, we trained the model on all binary string pairs from to n, where n is the number of examples we wanted to use for training. For example, the maximum number we used for training 131072, which corresponds to a 17-bit string. One can observe that the distribution of depths is non-uniform, as it aligns with the natural occurrence of different dept In edge-case experiments in Section 7.3.2 randomly sampled sequences from 18 to 41-bit strings to form the 'Random' test set, and collected all edge cases unseen during training to form the two edge case test groups.
Tree Traversal For tree traversal experiments, by default, we split the train and test sets by tree struc- tures, as we hoped understand the models' abilities to deal with unseen topologies of the tree. In the experiments, we trained the models on 20,000 randomly generated trees of depths 5 and and tested on 1000 held-out trees (500 each for depths 5 and 6).
17

---

Published in Transactions on Machine Learning Research (07 (07/2
6.1.3 Training Details
To examine the performance of our models, we computed accuracy based on the exact match of complete sequences under greedy decoding sel-up, i.e.:
DieDren 1( = Yi)
Acc
[Deeat]
Length generalization major concern in experimental design. In order to address the inherent limitations of transformers in generating longer sequences beyond their training exposure, we implemented straightforward approach to eliminate the positional bias, inspired by previous research (Dehghani et al. 2019). This involved introducing a simple mechanism where we randomly adjust the positional encoding by adding random lengths of padding to the inputs. By doing so, we challenged the model to generate both the actual sequence and the corresponding padding accurately. We also applied this trick the pre-trained language models, by having the random padding token be new token added to the pre-trained tokenizer
6.2 In- Co-Coneext Learning of Pre- Trained LLMs
We evaluated the ability of LLMs (GPT-3.5-Turbe and GPT-4) execute both tasks within an in-context learning framework. Following framework's ASM semantics, evaluation included rule summarization as the step for us to understand the program implemented (pattern classification and function representation), as well rule execution. Following our framework's reduction semantics, we presented the model with instructions and in-context examples in the prompt in the form of a reduction trace. For example, (X1 xo X1 X1 01) = xо (xo X1 X1 01) XO X1 x1 x1 01 where the parentheses enclose the part to run the next step of reduction on.
Binary Successor As mentioned in Section 3.2.1 our framework's encoding is independent of the par- ticular choice of characters. To rule out the effect of memorization of certain encoding of binary numbers from pretraining, and to ensure we truly tested the model's ability to capture semantics, we also mapped the constructors to other characters (for example, oxX)) = a, (x1) = b, o(01) = c) and compared the results with the standard choice of characters. In rule summarization experiments, we manually evaluated the model-summarizeer rules. In execution experiments, we checked the complete reduction chain.
Tree Traversal The ability to parse tree-like structure is important for LLMs, especially considering the use cases of these models for parsing or producing structured data, as well as for planning tasks. We therefore prompted the LLM to solve the tree-traversal tasks by performing step-wise reduction. We experimented with trees from depths 3 to 6 using the same notation and presentation as in the fine-tuning experiments.
7 Binary Successor Experiment Results
The binary successor task's simplicity allowed for detailed analysis of model behavior. We conducted altention and perturbation analyses, uncovering that the model's failures on edge stemmed from its learned algorithm. Using data up-sampling, rate (LR) significantly impacted generalization, with different LRs leading to distinct algorithmic behaviors. The model relied more on positional information than content, especially in the natural order, and did not effectively simulate a recursive rbstract State Machine (RASM). This study reveals the model's adaptability and limitations in handling recursive tasks.
Summary:
mitigated these failures. Learning
The simplicity of the binary successor task made it useful for multifaceted analytical exploration of model behavior. We first performed preliminary attention analysis (Section 7.1). followed by perturbation anal- ysis to recover the underlying mechanism the model learned to perform the binary successor computations
Thougg the models are pre-trained longer sequences, we abserve these models have poor generalization capabilities this task without the random pre-padding trick.
18

---

Published in Transactions on Machine Learning Research (07 (07/202) 2224)
81
40
40
10
22
66
RS R56 2
000000
85. 0 www.odeedee.......
(a) Reverse order self-attention.
decoder
(b) Reverse order encoder self-attention.
(c) Natural order encoder self-attention.
Figure 5: Attention Maps
This gave us a reconstructed algorithm that explains why the model would fail on a specific class of edge cases; knowledge that equips us to employ other techniques overcome these edge case failures (Section 7.3 We found some additional interesting effects of the learning rate (LR) the model's ability to accurately perform procedure that generalizes across lengths and depths of recursion (Section 7.4.. Finally, following our semantic framework, we did not find evidence that the learned model's mechanistic behavior effectively simulated a recursive ASM (Section 7.5
(Section
Note that, in this section, we will focus solely on our analysis for this task for our toy models trained from scratch, since this was the main focus of our experimentation, We will describe our fine-tuning results for this task briefly in Section
7.1 Attention & Embeddings
Our first step understanding the algorithm implemented by the model was to visualize the attention maps of the model. For encoder-docoder transformer, three types of attention be analyzed: decoder self-attention, encoder-decoder cross-atlention, and encoder self-aliention. For this task, we found that cross-attention was not interesting, but decoder and encoder self-attention both were.
Our visualization decoder self-attention revealed a noteworthy phenomenon in the final pnyer-something we call a recursion head that specializes in recursive cases. This was present in both the natural and reverse orders, though it served different purposes in each order since each order implemented a different algorithm:
In the natural order (Figure 15c,, the model starts attending to the last bit prior to flipping from xo, and continues to do until the end of the sequence. Thereafter, the recursion head predominantly allocates its attention towards the token have described.
In the reverse order (Figure 5a.; the recursion head directs its attention towards the X1 tokens that have been generated earlier. This attention mechanism distinguishes between recursive segments which demand rewriting, and non-recursive segments, which do require any rewrites. The first occurrence of an token encountered by the recursion head serves boundary that separates these distinct segments.
In summary, we use the term "recursion head" to refer to those decoder self-attention heads whose attention values were concentrated to the bit before recursion starts for the natural order, and to the last bit of recursion for the reversed order.
The encoder self-attention maps suggest that encoders also play a part modeling semantics by helping differentiate between cases (Figure 5b and Figure particular, the model employs its low-level attention to identify and differentiate symbols by attending to tokens of the same kind.
19

---

Published in Transactions on Machine Learning Research (07 /024)
Decoder
01 X1 X1 X8
XB
Decoder
Interrupt recursive segment by randomly replacing generated XD with X1
XO X1
Mutated Sequence
Mutated Sequence
Parttally Gecoded Sequrce
61 X1 xe
Xe X0
X1 XB XB
Apply perturbation
Readonlly remove subotring
Parttally Decoded
XB XB
Apply perturbation
X8 X6
X8
X8
X1 X1 XX Change
X1
Encoder
Encoder [X1
(a) String manipulation workflow for natural order.
(b) String manipulation workflow for reversed order.
Figure 6: String manipulation workflows.
Decoder Token Embedding
Decoder Positional Encoding
[EOS]
Location before start of recursion
Location before [BOS]
(a) Start-of-recursion Perturb.
(b) End-of-sentence Perturb.
Figure 7: Positional-encoding perturbations "Start-of-recuusionn' stands for the start of the recursion process and 'End-of-sentence" indicates the ending of a sentence.
and 33c in Appendix E show T-SNE plots of the internal representation for the respec- tive layers, with recursive segments in red and non-recursive segments in blue. The encoder (Figure 33a distinguishes between recursive and non-recursive segments. The first decoder layer (Figure 33b) recognizes symbols. Finally, the cross-allention between the encoder and decoder (Figure 33c injects instructions from the encoder about the start of recursion and the end the sentence.
Figures 33a 33b
7.2 Algorithm Reconstruction by Perturbation Analysis
Attention maps are useful for forming hypotheses about model behavior, but they reveal only possible correlations. To understand the mechanisms the model employs to perform state transitions, need to identify the relevant part of the abstract state at each time step that will determine which transition rule will be invoked at that time step.
We achieved this mechanistic understanding of abstract state by focusing on the inputs and the partially generated outputs at specific time steps while abstracting away the learned weights within the attention mech- anisms of the model. In particular, we conducted perturbation analyscs-mutating tokens (i.c., randomly inserting, removing, or flipping, as illustrated in Figures 6a and 6b and swapping positional encodings (see Figures 7a and ?b) the fly the decoder side to see how this impacted the model's behavior. We then looked at the resulting attention maps (Figures Sal and Sbb well quantitative performance (Figures 9a and 9b This experimental design was instrumental in elucidating the internal rule-based or
state-transition-ike mechanisms the models employed.
From this analysis, we were able to reconstruct the algorithm the model learns for both the natural and reverse orders. The pseudocode for the reconstructed algorithms can be found in Appendix D in Figures 29 and 30 respectively. Informally, the learned natural order algorithm consists of two steps:
computes the total number of bits required based on the input, and identifies the position which the last bit of the subsequence eligible for direct copying from the input sequence located.
20

---

Published in Transactions on Machine Learning Research (07 (072)
01
-1.0
1.0
X0
XO
X1
XO
X1
0.6
0.6
X1
X0
XO
0.4
0.4
X0
0.2
0.2
XD
X0
X0
0.0
X1
-.00
<>>>>>
XX
XO
XD
XL
XO
X0
XO
X1
XX
XO
XO
X0
XX
X0
X0
X0
X0
XO
X0
XO
XO
X1
X2
X1
XI
X1
XO
XO
X1
XO
XO
X2
XO
XX
(a) Natural order start-of-recursion perturbation.
(b) Reverse order flip token perturbation.
Figure 8: Attention maps for perturbation analysis.
2. It copies this particular segment, followed by a single X1, followed by xo tokens until it reaches the designated halting position.
Interestingly, we found that the decoder exhibits a stronger reliance on positional information rather than the content. associated with each position. When we corrupted partial output using the token mutation process (Figure bap. the model could still recover the remaining sequence (sce Figure Pag. However, when we changod the iosalional encoding of the bit before the recursive segment to random location (Figure 7a), the model started behaving "recursively" the next time step by generating X1 followed by xOs. Furthermore, if we replaced the positional encoding just before [EOS] with non-terminal token, the model would immediately stop generation by producing [EOS]. This behavior, elucidated by perturbing token content and positional encodings, showcases the model's pronounced dependency on positional information, subtly suggesting a non-recursive, position- based logic rather than a recursive state-based one.
In the reverse order, the model behaves differently. Informally, this algorithm also has two steps:
1. Based the input sequence, it determines the appropriate position for generating the first X1 token.
The decoder, while generating subsequent tokens, examines the tokens it has previously generated to determine an x1 token has already been produced. The presence of an token signals to the model switch from generating tokens to copying the remaining portion of the sequence.
We determined this by systematically replacing each XO token within the recursive segment (excluding the last token) with X1 token. The purpose was to observe whether the model would indeed initiate the process of copying the remaining tokens. Intriguingly, our results indicate that 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 tokens, but exhibited confusion after a few tokens, deviating from the expected behavior. This systematic but non-rocursive approach, combined with the attention map observations, subtly reinforces the idea that, while transformers may learn perform systematic rule-based processing, the underlying algorithm they implement is decidedly non-recursive in nature.
Previous work has noted that, due to their architecture, transformer models have a structural inclination to find shortcut solutions in specific setlings Liu et al.] (2022). These investigations, however, have been limited to constructed models and have not explored this phenomenon in learned models. Our research addresses this void by uncovering analogous patterns in trainod transformer models, specifically within the context of the complex task of structural recursion. We have also delineated these patterns more precisely by systematically reconstructing the underlying algorithms employed by these models.
21

---

Published in Transactions on Machine Learning Research (07 (07/2024) 0024)
0.8
Porurretten Sucoes Rate
Pertorbation Sucaes Raw
04
Test Group
Group
0.4
to 220
to 45
Doat Reatt +10
622
Liman +18 Alveen +0
122 -2200-200
Leaming
0.1
0.1
- 1.0
-8 1.
Depth
Recursion Depth
(a) SOR. Perturbation.
(b) EOS Perturbation.
Figure 9: Results of positional embedding swap for natural order models. Perturbation success rate is the percentage of cases following the behavior described Section 7.2
7.3 Predicting &Overcoming Edge Case Failures
We found that the models fail in interesting ways. Our reconstructed algorithms empowered us to predict specific edge cases on which the models fail, even when accuracy is high (Section 7.3.1 As these edge cases are class of cases under-represented by the training distribution, tested strategies to overcome them, and found that the issue can be partially overcome by data up-sampling (Section 7.3.2).
7.3.1 Predicting Edge Case Failures
Though the models can achieve near-perfect. accuracy elsewhere, they constantly fail in cases close to the maximum possible recursion depth for each length, especially for the natural order. Interestingly, perturbation analysis let us correctly predict the cases the model fails on and gave us understanding of why that is true, too.
The specific failure cases are constructed by applying consecutive X1 operators immediately after the 01 case. The algorithu that the model learns in the natural order falls short for these cases: it identifies the location before recursion starts and generates an X1 followed by XOs, when the correct answer should be applying xOs immediately after 01. In these cases, the shortcut is not applicable.
In line with our understanding of the learned algorithm, the model fails on these cases 100% of the time for the natural order. Of 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. From observation, we saw that the model indeed attempts to play the same trick by finding the position right before recursion starts. However, that position is no longer within the actual sequence but rather the "pre-padding" location. It encounters confusion between generating an X1 01 start. It settles on 01, but this leads it terminate prematurely, generating sequence that one token too short.
7.3.2 Overcoming Edge Case Failures
The edge cases that we identified in our analysis are statistically underrepresented the training distribution, and are apparently ill-handled by trained models. A natural question that arises is whether we can train the model to learn edge cases better by putting more emphasis on these cases.
To determine this, we experimented with up-weighting and oversampling edge cases, two techniques that have been widely adopted in imbalanced classification scenarios. We used these strategies to attempt to overcome both kinds of edge cases:
1. the case where the last reduction step is S 01 xo 01, and
22

---

Published in Transactions on Machine Learning Research (07/2024)
Tedt
Tiit Date FCC
The Data Random
-2 23
23
35
100
8.50
0
1.50
1155
6:37
Accumey
Acturacy
Aomenyy
Figure 10: Reverse Order: Oversampling
Data- RC1
ECM
Random
13
42 13
13
25
03
Aommer
Arcurarty
Avermey
Figure 11: Natural Order: Oversampling
Toxt Data = RC1
Thet Data- = FX9
Toe Tara
Ram
13
-5 13
23
29
33
Aucuree
Accoracy
Aveunac
Figure 12: Reverse Order: Gradient Up-weighting
Test Data- BC
Toe Data- EXM
Toc. Data
Raadiam
00
41
32
8.3
0.5
355
Acreary
Avermey
Figure 13: Natural Order: Gradient Up-weighting
5,6 X1 01.
2. the case where the last reduction step is S (XO 01)
In gradient up-weighting experiments, we amplified the gradients with respect to each of the two kinds of edge case (if they occurred) by a factor we denote k; for edge case i (i.e., kn for edge case 1, and lz for edge case 2). In oversampling experiments, we duplicated the edge cases of kind i k; times in the training data.
We found that the oversampling strategy did significantly help the model improve on capturing the edge case patterns with minimal influence on the non-edge case data points for both orders (Figures 10 and 11 Tn
23

---

Published in Transactions on Machine Learning Research (07 (07/2024)
1.00
0.90
0.80
Peformanee
Test Group
Accuray
0.98
Test Group
0.90
12ral442 2 to EZaun
12ruin40 3 to 7. 23
(ara 44 to Maaee
0.97
Flaes 44 to
0.60
Learning Rate Factor
0.96
Leaming Rate Factor
-8
60000 Training Size
Training
(a) Natural Order
(b) Reverse Order
Figure 14: Performance versus number training examples. The performance is the average samples with all possible recursion depths with that length range. The error bar indicates the standard deviation across total of runs with different random seeds.
(a) 0.1
(b) C 0.3
(c) C = 0.5
(d) C 0.7
(e) C ==
Figure 15: Self-attention of the last decoder layer under different LR factor C's on natural order.
contrast, while gradient up-weighting also helped in the edge cases, it had a negative impact on the models' performance in non-edge cases (Figures 12 and 13
It important note that one cannot identify these edge cases beforchand because doing so requires an understanding of the algorithm that the model has learned. This unveils the brittleness of mining algorithmic rules from demonstrations, even with representation that inherently encodes the structure.
7.4 Generalization
One interesting thing that we observed in our experiments is that LRs affect model precision for the binary successor task. Thus, LRs also affect model generalization ability across lengths and to edge cases. In fact, it appears that changing the LR can even impact the intensional behavior (that is, the particular algorithm) that the model learns!
To determine this, we varied the LR following the original transformer LR scheduling scheme (Vawwan al. 2017): did min(s 8 update steps, Sw is the predefined warm-up step mumber, and C is the constant controlling the magnitude. The overall generalization performance across different LRs is in Figures 14a and 14b]
S where d the embedding size of the model, the current number of
To our surprise, we observed a significant difference in atlention patterns when trained with different values of C' on the natural order task, which could suggest behavioral differences in the model that might result in different generalization abilitics. As the LR grew, the model began to specialize one head into a recursion head gradually, as shown in Figure [5 In fact, smaller LR models learn the weaker notion of executing the algorithm in Section 7.2 for longer sequences (see Figures 9a and 9b
24

---

Published in Transactions on Machine Learning Research (07 (224))
mik
Eryph
04
Drecden Thesder
0.39
03
0.2
Pay PH00
Contrion
Condioan
(a) Probing average-pooled embedding to determine embedding to determine the current depth recursion. whether the transformation maximum depth of recursion. needs recursion.
(b) Probing average-pooled
(c) Probing each token embedding to determine the
Figure 16: RASM-Probing results.
We also looked at varying LR while constraining the training dataset to contain only shallow recursive depths for the binary successor task. In this case, we found that model trained on small LR sees a steeper drop in test performance while still attaining near-perfect training accuracy. However, for the reverse order, such depth constraint does not severely affect the model's performance either LR (sce Figure 25 in
Appendix D.1 b.
7.5 Probing: How Effectively Did the Transformer Simulate an RASM?
In alignment with the abstract state machine (ASM) framework discussed before, our empirical evaluation aimed to determine if trained transformers emulate a recursive ASM (RASM). One of the primary objectives of our study was to investigate whether the model implicitly implemented a recursive algorithm by pattern matching on the most significant bit, thereby simulating an RASM. To accomplish this, we conducted an initial analysis to examine the embeddings of the encoder and decoder for pattern-matching and recursion- depth-related information. Our ideal outcome was to identify evidence supporting the implementation of recursive Abstract State Machine (RASM) described in Section 4.2.2 as employing pattern- pattern-matching scheme. Alternatively, we expected that a sequentialized algorithm for the recursive task might exhibit indications tracking the depth of recursion.
To delve deeper into this matter, we designed straightforward experiment. We sought train a simple linear classifier capable of distinguishing between cases such as XO and X1 bb based on the model's internal reprosentations. We computed the average encoder output across the sequence and trained linear classifier the fixed encoder representations for binary herether recursive computation is required) and recursion- depth (the number of reductions needed to compute the successor) classification. The outcomes of these experiments are presented in Figure 16a Regrettably, our attempts to train a classifier to detect the distributional distinctions in the embeddings between the two cases proved unsuccessful.
Next, we aimod to investigate the extent to which the embeddings individual tokens contained information regarding the recursion depth. We found some evidence of this, but only in the natural order. To achieve this, trained classifier to recognize the recursion depth of each token using both the encoder embeddings and the output embedding of the final decoder layer. The results, presented in Figures 16b and [6c] demonstrate that the encoder embeddings do not contain information on the current depth of recursion, while the decoder embeddings do exhibit. a certain degree of such information in the natural order. However, we did not observe this phenomenon when considering the embeddings reverse order.
All of this evidence suggests that the transformer models we have trained do not strictly implement the kinds of state transitions might associate with an RASM. The encoder's 's absence of positional information and
25

---

Published in Transactions on Machine Learning Research (07/2024)
the decoder's limited positional information in the natural direction further underscore this deviation from the expected recursive behavior.
8 Tree Traversal Experiment Results
The transformer models trained from scratch fail to learn a recursive solution to tree traversal. They learn shortcuts from data for pre-order traversals, and learn depth-specific approaches for step-wise roductions, making generalization to unseen depths impossible without additional layers and heads.
Summary:
The tree traversal task is inherently more complex and challenging than the binary successor task, since performing each reduction step in tree traversal requires more sophisticated logical reasoning. To recover the algorithmic behavior of the model, we again performed an ASM-guided mechanistic analysis (Section 8.1 Though different traversals are of similar levels of difficulty, we found that the model still tends to pick up on shortcuts if possible (Section 8.2). The shortcuts we reconstructed (Section 8.3 are for fixed depths (Section 8.4 and do not strictly model recursion.
Taken together, our findings reveal that the models focus their attention different components of ASM-style update (ie., constituting logical guards and implementing the transitions), and that they exhibit distinct behaviors depending on the kind of traversal and the number of reduction steps (for step-wise reduction). The model picks upspecific solutions for solving the cases for given depth, which aligns with the formal language intuition of parsing using regular grammar (without counting).
8.1 Algorithm Reconstruction by Counterfactual Patching
Analyzing models trained for the tree traversal lask is more complicated than analyzing models trained for the binary successor task. We can see this by looking at both the ASM and reduction semantics in our framework: First, the ASM corresponding to each model trained for this task, in order to produce one symbol, needs to handle composite logic formulas and invoke multiple mechanisms (e.g., pointing to correct locations and extracting values). Second, each 8Be-reduction step in our reduction semantics for this task implicitly captures not just substitution, but rather two concurrent substitutions one in each of the left and right subtrees.
It is because of this complexity that, in order to analyze the intensional behavior of the learned model, we designed additional subtasks that broke down even a single roduction step further, in ways that align more naturally with learned transformer model behavior. Our process for analysis was the following:
decomposing the tree traversals and their reductions into these subtasks,
2. conducting "activation patching" in order to determine what parts of the network were most impor- tant to accomplishing each subtask, and
examining the attention pattern behavior for the most significant attention heads, well the patterns of earlier heads that likely contributed to each given head's behavior.
There are seven total subtasks that we tailored for this analysis, which are designed capture the key 'transi- tion' points in performing tree traversal. Not all applied to every case (e.g., some were relevant for only one of the preorder inorder traversal), but overall these subtasks include:
Copy initiation: the point which the model outputs the first token of copy of a sub-sequence of the input sequence.
Midpoint of left tree copy (for in-order traversal and reductions with depth 2 2): the point at which the model outputs the root of the left sub-tree in an in-order traversal. We want observe how the model fetches the right sub-tree
26

---

recover Published in Transactions on Machine Learning Research (07/2024)
Logit Difference
How much logit difference can we recover?
Clean Logits
Corrupted Logits
Partfally Recovered Logits
Clean Activations
Corrupted Artivations
Clean Activations
Attention Head
Atlention
Attention Head
(6 (Leaf Leaf) 8(Leaf Leaf))
(6 Leaf) (Leef 9))
3 (6 (Leaf Leaf) (Leaf 9))
Figure 17: Illustration of counterfactual patching process.
End of left tree copy (for inorder traversal): the completion of the in-order sequence of the left tree.
Insertion of root node: the point at which the model outputs the root node from the top level of the tree.
Insertion of REDUCE (for reductions): partial traversals, the point at which the model outputs the REDUCE token used to demarcate an untraversed sequence.
Resumption (for reductions): the point at which the model continues to copy the sequence after inserting REDUCE.
EOS: completion of the sequence.
To identify the most significant attention heads to the models' final output, we adopted an intuitive yet useful approach inspired by Meng et al. (2023) and Wang et al. (2023a) called counterfactual patching (Figure 17 From a high level, this method determines the importance of an attention head by replacing an activation when producing answer A with one that is obtained when the model is used to produce different answer B for different input, then observing how much the answer is drifted from A to B.
To perform this process, we first perform a clean run, where we directly feed the input sequence to the model as normal and collect the activations and logits l. Then we perform corrupted run by flipping a token which is tested to indeed inffuence the model outputs to obtaín the corrupted logits We then run the model on the corrupted embeddings while replacing the hidden state of some token on a particular head with the one from the clean run. The effect will propagate the subsequent layers. To measure the importance of this head, compute to what degree the logit difference between I and i can be recovered by bringing back the clean activation from that particular attention head. The extent to which the logit difference reflects the importance of this attention head.
We used this technique to determine which attention heads were most important to the final output of the transformer. This did not reveal the full circuit used to perform the task, but it did provide suggestive, causal evidence of what the learned model doing. After identifying these key components of the model, we focused our investigation the roles and composition behavior of these attention heads, leaving comprehensive analysis of the entire circuit for future research.
8.2 Identifying Learned Shortcuts
As shown in Figure 18 we found that models can perform full preorder traversals on unseen trees, but fail completely for inorder traversals. Even more interestingly, the model can learn the full preorder traversal better than it can learn the step-wise reductions because it learns shortcuts.
Examining the attention behavior of the model, we observed that the model primarily focuses on numerical values and disregards brackets and EMPTY tokens in preorder traversals, as observed through (see Figure 31b in Appendix D.2 The learned transformer attends only to node values while ignoring
its cross-attention
27

---

Published in Transactions on Machine Learning Research (07 (274))
Pre order
In order
1.0
Tree Depth
Accuracy
Accurayy
Trained On
Depth Only
0.4
Depth
Fill
Num. Unroll Sceps
Num. Unroll Steps
Figure 18: Accuracy of tree traversal.
parentheses and leaf nodes in first layer cross-altention, and additionally acquires information on the next token to be copied (i.e. the next node value token), shown by cross-attention in the second layer.
For inorder traversals, we hypothesize that there is no clear shortcut for sequence models to perform inorder traversals without stacks more sophisticated architecture (with more layers attention heads). Unlike preorder traversals, which can be done linearly, inorder traversals demand "understanding" and capturing recursive relationships between nodes.
8.3 Reconstructed Algorithms
The learned transformer model employs a set of logical rules and functions facilitated by the attention mechanism for tasks such as copying tree node values or producing special tokens. uses various types of attention keep track of important token locations for either logical control flow or invocation of the mechanisms to produce the next token in the output sequence.
In the task of inorder twice reduction, for instance, the model uses its attention to identify the appropriate reduction level and pinpoint the node whose values will be copied to the current output slot (see Figure 32b in Appendix D.2 The model combines multiple logical conditions to discern the boundary separating the remainiin sub-trees and the layers set for unrolling. To generate the "UNROLL [" statement in preorder reduction, the model's cross-attention is focused on three key positions: 1) the parenthesis immediately preceding the node where the "UNROLL[" [" token will be inserted, 2) the subsequent opening hesenthesis, and 3) the final closing parenthesis of the subsequence that will be copied into the "UNROLL ] statement.
8.4 Fixed-Depth Nature of Model-Learned Solutions
In the context of formal language theory, parsing tree involving fixed number of reduction steps using regular grammar is known to be feasible. This process can be exccuted scamlessly by predefining the handling of each possible patlern, thus simplifying tree parsing. Similarly, our experimental results show that transformers have demonstrated the capability to learn to parse reductions specific number of steps. They follow a similar route by learning to identify patterns inherent that particular depth. As illustratod in Figure 19 the model's learned solution peels off the fixed number of parentheses to locate the root of the tree reduction
28

---

Published in Transactions on Machine Learning Research (07 2024)
Step 1:
Step
Step
Start
Peel layers parentheses
Identify the current depth jointly attending to the parentheses on input side and the previously closed parentheses
applying Reduce
step reduction) find the
token copied
R[
3
Leaf
Leaf
Leaf
2
1
(
2
3
Figure 19: The illustration of how the model performs reduction with its attention in inorder traversal. The example is two-step reduction for the given tree.
Layera
2-Layer
1.0
E-Mocel
ThaRn
C-Mooul
0.0
08
0.9
0.01
0.G
04
0.4
0.2
0.2
Heads
Num
D-Mode
Figure 20: Results up-scaling trees. In the number of heads versus test accuracy experiment, we exper- imented with 4-layer transformers. To observe the trend with an increasing number of layers, we fixed the hidden dimension to be 256.
Yet vital limitation of regular grammar emerges when comes parsing tree of arbitrary depths. To accomplish such task, the need for counter becomes essential. Pressing further into the complexities of depth increases, the model requires a larger number of heads. Each head gathers specialization to manage parentheses of different depths. However, given that there is no clear constant-depth workaround for this task, and considcring the absence of a counter construct in the learned transformer, a performance decrease with increasing depth anticipated.
From the RASM perspective, a noteworthy feature of the learned algorithm becomes clear, In particular, the learned model does not implement modularized algorithm that could be viewed as two independent agents of the RASM.
Our experiments to change the model architecture by increasing the number of layers, hidden dimensions, and attention heads verified the reasoning in the previous subsection (see Figure 20). We did see an increase in test accuracy with the increase model depth and embedding size, which was natural to anticipate. We also found that, with the depth and embedding dimension held constant, simply increasing the number of attention heads allows the model parse more complex cases. As the maximum depth of trees increases, models need handle more different depths and thus need more heads to be specialized to each. Indeed, we increase the number of heads given the same embedding size, the performance increases.
These findings echo our earlier discussion on the fixed-depth nature of the algorithm transformers learn. We conjecture that the key to generalizable algorithm could be the specialization of some parameters to implement counting mochanism that tracks the depth of parenthesis, which may be hard learn from I/O examples of tree-traversal functions their reduction semantics alone using the existing transformer architecture.
29

---

Published in Transactions on Machine Learning Research (07 (22/4
1.0
Th-lasn
T5-Boow
0.5
ByT55-Smml
15-Smmall
0.8
ByTtS-Fmmwl
TS-Simall
0.040:44
0.4
11:38
1:22
0.2
0.2
Rondom
EC2
Than
EC1
Dota
Data
(a) Natural Order.
(b) Reverse Order.
Figure 21: Performances of pro-trained models on natural and reverse order traversals.
9 Can Pre- Trained LM be Mune-Tunddd to Perform Structural Recursion?
Summary: Pre-trained LMs finetuned on the binary successor tasks also struggle to generalize and the performance varies.
One step beyond working with toy models, we briefly investigated fine-tuning pre-trained models learn structural recursion. Our goals were to test whether the associations established by pre-training help with picking up the notion of recursion as found in Zhang et al. (2022c) and to identify the potential practical issues with pre-trained transformer models in performing symbolic tasks. We tested the models' performance on the binary successor task; results are in Figure 21
Similar to our experiment findings on length extrapolation with toy models Appendix we found that the decoder-only pre-trained GPT-2 model tends to generalize worse than T5 models, though achieving near- perfect accuracies on the train set. By comparing various T5 models, we found T5---allll outperforms T5-small models since it allows the model to better by-pass the meanings of specific tokens (e.g.. and pick up the semantics of transformation from pairs of inputs and outputs. Pre-training over code corpus equips CodcT5 with better-structured reasoning capabilitics and the inherently recursive and tree- like structures of programs allow il to better solve problems recursively. Therefore, Code T5-small achieves better overall performance. Another interesting observation revealed from the accuracy results is that the roverso-order represcntation is casier learn by both pro-trained and toy models than natural order.
B
By comparing performances of T5-small and T5-base models, we found evidence for pre-trained models to learn this simple task better better-even even though 2-layer toy transformer is enough to achieve high accuracy, showed in Section 7
10 In-Context Learning Results
This section evaluates GPT-3.5-Tures and GPT-4 in in-context learning for structural recursion tasks. They struggle with maintaining algorithmic consistency despite detailed prompts, often making errors in recursive rule exccution and termination. The experiments reveal that while in- context examples offer some guidance, they are insufficient for the models to learn correct recursive rules. Notably, the models perform better without in-context reductions, relying more effectively on pre-trained knowledge. This underscores the need for improved mechanisms to enhance their consistency and accuracy in handling complex recursive tasks.
Summary:
30

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Initial State
Invonntext exumples
Input Sequence 8 (X] X1 01)
ASM
ASM State Transition
Example
Example
Program mined from examples
State
xo S (X1 01)
Transition
Apply state transition the program
Figure 22: Example Analysis of In- In-Context Learning
Order
Tokenization
Examples
CoT
Examples
Model
Hit@1
Hit@3
Hit 85
Natural
Original
inorder
Full trace
10
GPT-
0.10
0.25
0.25
Natural
Original
inorder
Full
GPT-4
0.30
0.40
0.60
Natural
Original
inorder
No CoT
10
TPrro,5-Turbb
0.10
0.20
0.30
Original
inorder
CoT
GPT-4
0.30
0.30
Reverse
Original
inorder
Full trace
10
GPT-3.5-TTarb
0.10
0.15
0,20
Reverse
Original
inorder
Full
GPT-4
0.45
0.55
0.60
Reverse
Original
inorder
No CoT
10
GPT-b,5-Turbo
0.05
0.15
0.25
Original
inorder
CoT
GPT-4
Natural
Original
Random
Full trace
10
GPT-3.5-Turb
0.25
0:35
0.45
Natural
Original
Random
Full trace
10
GPT-4
0.10
0.50
0.50
Original
Random
Full
GPT-3.5-Turbo
0.50
Reverse
Original
Random
Full trace
10
GPT-4
0.00
0.30
0.40
Natural
Permuted
inorder
Full trace
10
GPT-3.5-Turb
0.10
0.20
0.20
Natural
Permuted
inorder
Full trace
10
GPT-4
0.20
0.30
0.40
Reverse
Permuted
inorder
Full trace
10
GPT-3.5-Turbo
0.10
0.30
0.30
Permuted
inorder
Full
GPT-4
Table 1: Learning to perform binary successor task with in-context examples. The text "inorder" in the "Examples" column means providing the model with examples starting from base case (i.e. the successor of 1, to 10,) in order. "Random" means randomly sampling 10 mumber-sucoesee pairs.
For in-context learning of LLMs, one can choose different levels of abstraction depending on the purpose of the study. In our case, we analyze the model from the text level, where we consider the model performing step-wise computation of the program in-context, and the current state is the context at that time step. We treat the programs the LLMs summarized from in-contexi examples to be the "learned" program of the model that it will subsequently execute, and we measure its ability to execute structural by producing the trace of reduction conditioned on examples and on the set of transition rules as instructions.
At this point, the flexibility of the ASM framework offers us the freedom to lift the level of raction where we assume the model is executing the program (including the pattern classification and transition) explicated in the text using its internal mochanism (sce Figure 22 This allows to unify the analysis framework of learned models via gradient updates and in-context learning.
Our rule-finding experiments show that the LLM under test (GPT-x) cannot summarize the correct recursive rules from the various combinations of in-context examples effectively, with an observed accuracy of only 18.75%. The pattern classifiers they learn from in-context examples are superficial, even with hints restricting the number of rules and how the rules should look, and non-exhaustive (the rules do not cover all cases the in-context examples).
From Table notice the model lacks the capability to accurately compute binary successors under various set-ups. Nevertheless, teaching the model to perform step-wise reduction to reach the final result does help the model solve more cases correctly by performing a simpler operation each time and allowing the model to store intermediate computationn ions in the context.
In addition, when presented with the state transition rules and step-wise reduction demonstrations a Mfain-of-thought style in the prompt, the LLM still struggled to execute the recursive rules correctly produce the successor of the test input. Some typical errors included accidental missing inserting tokens,
31

---

Published in Transactions on Machine Learning Research (07/2024)
No Reduction
Single Step Reduction
Full Reduction Trace
Depth
Model
Hita1
Hir83
Hita5
Hital
Hita33
Hita5
Hitea
Hite33
Hissk5
G.T--.55-urbb
1.00
0.30
0.45
GPT-4
1.00
1.00
1.00
0.95
0.95
0.95
1.00
1.00
1.00
Gur-b.5-Turbo
1.00
1.00
1.00
0.35
0.65
0.75
0.25
0.45
0.60
1
GPT-4
1.00
1.00
1.00
0.80
0.85
0.95
1.00
1.00
1.00
5
GPT-b.5-Turbo
0.70
1,00
1.00
0.35
0.65
0.70
0.05
0.10
0.15
GPT-4
1.00
1.00
1.00
0.95
1.00
1.00
0.80
1.00
1.00
6
GPT-3.5-Turbo
0.90
0.95
0.95
0.20
0.55
0.60
0.00
0.05
0.05
GPT-1
1.00
0.90
0.60
0.90
1.00
Table 2: Preorder Traversal with LLMs
No Reduction
Single Step Reduction
Full Reduction Trace
Depth
Model
Hit@l
Hite3
Hita5
Hit@1
Hitri3
Hit
Hit
Hit
Hit88
3
G-T-b.5-Turbo
0.45
0.75
0.80
0.45
0.55
0.65
0.45
0.75
0.85
3
GPT-44
0.70
0.95
1.00
0.80
0.90
0.95
0.85
1.00
1.00
4
GPT-3,5-Turbo
0.20
0.50
0.55
0.20
0.45
0.70
0.10
0.20
0.35
GPT'44
1.00
GPT-3.5-Turbo
0.05
0.10
0.25
0.10
0.30
0.40
0.00
0.00
0.10
GPTT44
0.50
0.90
0.95
0.60
0.90
0.90
0.10
0.25
0.45
GPT-3.5-Turbo
0.00
0.00
0.25
0.00
GPT144
0.15
0.35
0.40
0.55
0.75
0.75
0.00
0.20
0.20
Table 3: Inorder Traversal with LLMs
not handling the recursive cases properly, and, more predominantly, not being able to terminate the reduction process after mapping XO to X1 as illustrated in Figure 23 (71 percent for GPT-4).
In analyzing the capabilities of the GPT-x models, patterns among presented examples certain degree, they lack the intrinsic ability fully "comprehend" and execute the concept of structural recursion solely from these examples. This limitation is noteworthy, considering the models' demonstrated proficiency in myriad of other computational tasks.
evident that, while they can identify common
The insufficiency of these models in accurately performing step-wise reductions becomes particularly pro- nounced in the context of tree traversal experiments. In these experiments, the performance of LLMs exhibits a significant decline as the tree depth increases, correlating with a rise in the complexity and number of re- duction steps required. Interestingly, both models observably achieve better performance when no in-context reduction is required. These LLMs appear have have learned the specific concept of tree traversals from extensive pre-training and observed to be capable of performing rrvverslls in zero-shot up to accuracy, so inaccurate in-context reductions mislead the model to produce worse results.
Reduction Chain By GPT-4
S(X1 XI XI XI XI XI XO XO XO XO 01)
XO S(XI XI XI XI X1 XO XO XO XO 01)
....correct steps)
XO XO XO XO XO XO S(X0 XO XO XO 01)
XO XO XO XO XO XO X1 S(X0 XO XO 01) <- Error begins
XO XO XO XO XO XO X1 X1 S(XO XO 01)
XO XO XO XO XO XO X1
XI X1 S(X0 01)
XO XO XO XO XO XO X1 XI X1 X1 01
Figure 23:
Non-stopping Error Made By GPT-4.
32

---

Published in Transactions on Machine Learning Research (07 (07/2024)
The degradation in performance during in-context reduction of the preorder traversal (Table 2 serves rudimentary benchmark for understanding how the models' accuracy declines in relation to increased task length. The fundamental challenge in preorder traversal is the sequential reading of numbers and peeling off of parentheses, which becomes progressively difficult as the sequence extends. However, the same simple trick seen our toy models of copying node values for preorder traversals again exploited by the LLMs.
More complex the case of inorder traversal (Table 3), where a qualitative analysis reveals higher propen- sity for errors in the intermediate reduction steps. In these instances, the LLMs frequently deviate from the correct reduction algorithm. A typical error involves the misinterpretation of the reduction rule:
80 (inorder
inorder (Branch val r)
[v] ++ (inorder r)
to instead be:
inorder (Branch val 1 r) 504, [v] ++ (inorder 1) ++ (inorder r)
though we denote this slightly difforently in our prompting for convenience.
Reduction Chain By GPT-4
inorder(901 ( 907 LEAF ( (437 LEAF LEAF) )) LEAFJ
=inorder[907 LEAF ( (437 LEAF LEAF) ) 901 inorder LEAF
=inorder LEAF (437 LEAF LEAF) 907 inorder [LAFF] 901 <- Error begins
more steps
Figure 24: Example of mistake made by GPT-4 during in-order traversal.
This type of error underscores the challenges LLMs face maintaining algorithmic consistency over extended sequences, particularly when the task requires adherence to precise order of operations.
11 Discussion: Theory vs. Practice
One of the themes that permeated all the experiments we ran, and our design of the framework itself, is the gap between thoory and practice for lcarning emulate the behavior of recursive functions. There is long precedent of constructing models that behave exactly expected. But what does that mean with respect to what can actually practically be learned? How can observe this gap?
To revisit this gap in light of our empirical results, let us consider again the binary successor task. Following our framework's 's reduction semantics and viewing the constructor S as a function, a single-step reduction on the binary successor task breaks down into three cases, with each case effectively corresponding to a sub-string replacement:
1. S x0 +
X1
2. S o X1 53c
XX o
88. 01
3. S
As expected, transformer models can clearly learn each individual reduction step of this simple function form examples. To determine this, experimented with both 1-layer and 2-layer encoder-decoder transformers, and found that both kinds of transformer models indeed can solve such tasks with perfect accuracy (Table This indicates the sufficiency of the models' capabilities to solve such sub-string recognition and replacement tasks in both orders.
But recursion more than just reduction; it also composition. If the model were learn said composition organically, this would give rise OlI--layer transformer solution to compute binary successors where is the sequence length, assuming we also have some termination mechanism. This is bounded in size and quite
33

---

Published in Transactions on Machine Learning Research (07/2024)
Order
Model
L
-max
to
maa 4
+10
Lman + +20
Natural 1-Layer
2-Layer
L-Layer
Reverse
2-Layer
Table 4: One-step reduction results for binary successor task. denotes achieving >99% accuracy in each individual depth for all steps in a reduction in that test group.
inefficient, but it is possible if it can actually be learned. But experimenting to see whether this happens organically becomes quite intractable for larger sequences.
The manual construction of such a solution-the thoory- is also straightforward for this task. Transformers are shown to be constructed to achieve Turing completeness by way of repeatedly applying a transformer with a fixed depth. For this use case, one can construct single-layer causal transformer that performs one- step reduction for the binary successor task. By stacking these layers and implementing a simple mechanism that checks the convergence of the algorithm (i.e., searching for the existence of the S symbol), such model can compute the successor of binary string in the ronstr notation. For fixed recursive depth D, this would take D layers to construct. This is a bit less inefficient than length bounding, but it is still quite intractable to test empirically for high recursive depths.
There are also ways to construct by hand transformer models that perform the entire computation for the binary successor problem up a bounded length, without nccessarily being quite as intractable terms of depth. These models could work by searching for consecutive X1s at the end and deciding whether to produce X1 then copy the rest, to produce хо 01, based on what comes after the deepest X1. This is not quite what we saw learned in practice, but it does match our empirical findings that these models tend to learn shorteuts that are specific to particular sequence lengths or recursive depths.
The tree traversal is a much more difficult task. Building upon existing works on Dyck language generation and other constructions (Ebrahimi et al. 2020 Liu et al. 2022), we beleive that it should be straightforward to prove the existence of mamually constructed models that perform one-step reduction on the task of tree traversal by adding layers that copy node values with pre-labeled depths of parentheses. This does not match what observed in practice, and this gap warrants further exploration.
12 Related Work
Understanding Transformers As a predominant class of deep lcarning model architectures, the trans- former has shown promise in a wide range of tasks. Researchers have been attempting to understand the models via different approaches under different problem set-ups.
Methodology-weee a line of rescarch aims to characterize the modcls' capabilitics via thcoretical construc-
tions Bhhattamishr et al. 2020b Yun et al. 2020 Ebrahimi et al.) 2020 Wei et al. 2023 Pérez et all 2021 Liu et al. 2022 Merrill & Sabharwal 2022 Pérez et al. 2021 Hahn 2020). These studies effectively answer the questions revolving around the expressiveness of the transformer architecture by showing the existence of a model that satisfies the properties under study. Our work differs in methodology, as we adopt order answer the question of whether the models can learn to emulate recursive functions from I/O examples, where the emphasis is the ability to mine recursive rules from data in practice. Another class of work takes different approach where they seek to understand the functions of different
empirical methods
components of trained model via probing (Hewitt & Manning 2019 Belinkov 2022 analyzing attention
patterns Vigg& & Belinkov
2019 Sun & Marasović 2021), or linear layers (Geva et al. 2020
Our analyses of the algorithms performed by our trained models were inspired by existing work in the relatively new field mechanistic interpretability (Nanda et al., 2023 Chughtai et al. 2023) and include methods such as counterfactual patching (Meng et al. (022), circuit tracing (Wang et al. 2023a), automatic circuit discovery (Conmy et al. (023). and component ablation. Mechanistic interpretability encodes the merits of the ASM concept since assumes the learned model to be a program and attempts to understand
34

---

Published in Transactions on Machine Learning Research (07/2024)
the model by understanding the program it represented at certain level of abstraction. In our work, we use several of these techniques to reverse-engineer the critical components of the model and how they carry out the algorithm that solves the tasks in question.
One other key component of our framework is the introduction of structural recursion tasks formulated in a way that connects two paradigms (programming language and machine learning) and two key ingredients of programs (syntax and semantics). A stream of previous work (Delétang et al. 2022 Zhang al. 2022a Yao 2021 Liu et al., 2023a) also took the approach of designing toy task to understand the computational
et al. ability or isolate certain aspect of class of deep learning models.
Formal Theorem Proving and Program-Related Reasoning
The tasks we choose are inspired
by work in program and proof synthesis and repair (Gulwani et al. 2017 Lee & Cho 2023 Osera & Zdancewic 2015; Miltner et al.) 2019 Ringer et al., 2021 Ringer 2021
Magaud & Bertot 2000 Chaudhuri
ct al. 2021), ,, and are also an important class of functions for inductive logic programming (Cropper ct al.
2021
Transformer-based large language models have brought significant. progress
tasks related to pro-
grams
Chowdhery et al. 2022 Chen et al. 2021 Svyatkovskiy et al. 2020 Lu et al. 2021 Nijkamp et al.
2022
Xu et al.
2022
Zheng et al. 2023
Ahmad et al.
2021
Wang et al., 2021 Allal et al.] 2023 OpenAl 2023a b Thoppilan
Chakraborty et al. 2022
2023b
Li et al.
2022a
2023
Xu et al.) 2023
Fried et al.
2022:
et al.
2022) and proofs (Polu & Sutskever
2020: Han et al.
2022 First et al.
2023). Still, current tools
struggle to emnlate function behavior (Gu et al. 2024) without prompt engineering techniques like chain of
thought prompting (Wei et al.] 2022) or scratchpad reasoning (Nye et al. 2021).
On the other hand, execution turns out to be an essential element for better program synthesis with LLMs Olausson ct al. 2023 Le et al.
2022 Pan ct al.. 2023; Zhang et al. 2023) A series of code language models specializing in execution-related lasks have been introduced to lackle specific problems in software
engineering (Souza & Pradel 2023
Pei et al.
2023
Ding et al. 2023 Liu et al. 2023b).
Formal Languages and Deep Learning Models Formal languages exhibit clear structures, encode
cerlain rules, and can be easily generated; thus, they are particularly useful characterizing neural networks' representational capacities. They have long been used as tool study the learning abilities of machine
learning systems, espocially neural architectures (Kleene 1951 Cascy 1996
Smith & Zipser 1989).
More recently, the rapid advancement of deep learning technologies has made possible different applications of neural networks, such as modeling natural and programming languages. It has been argued that the ability to simulate formal language is correlated with the ability to capture natural language grammar and solve complex problems (Merrill 2023 Strobl et al.) 2023). In addition, compared with real-world tasks that often involve additional complexities, formal language modeling offers controlled setting where we can abstract away the irrelevant factors to better benchmark the capabilities and identify the limitations of the
models (van der Poel et al. 2023 Liu et al., 2022 2023a
Generalization Capabilities of Transformers Numerous studies have meticulously examined the limita- tions of transformers in out-of-distribution generalization through both algorithmic and formal tasks (Deló- lang et al. 2022 Anil et al.] 2022 Zhhnn et al.) 2022c Dziri el al. 2023 Velicković et al., 2022; Liu et al., 2022). Generalization can be assessed along different axes: length generalization, which pertains to the model's capacity handle longer sequences than those encountered during training; and algorithmic gener- alization, where the model must execute more complex procedures.
There have been many attempts to improve model's generalization to longer sequences through positional
encoding and data format (Shaw et al. 2018 Dai et al. 2019 Ruoss et al. 2023 Press et al. 2022
Raffel
et al.
2020a Zhou et al. 2024). On the other hand, algorithmic generalization has also been investigated
from architecture, training and task perspectives (Ouellette et al. 2024 Kamali & Kordjamshidi
2023 Weiss
et al. 2021 Zhou et al. 2023).
13 Conclusions, Limitations, and Future Work
In this paper, we proposed a comprehensive framework to study the sequence models' behaviors in learning to emulate structural recursion. The framework we proposed takes care of both pillars of the field of pro-
35

---

Published in Transactions on Machine Learning Research (07/2024)
gramming language domain: syntax and semantics. Syntax-wise, we introduced new sequential encoding that nicely transforms recursive data structures into sequences. Semantics-wise we connected the notion of structural recursion to a broad range of ML-based sequence models that encompass different settings both gradient-based training and in-context learning.
To cover two representative classes of recursion one that has only recursive sub-case at each reduction step (i.e., calls the reduction linearly) which is naturally sequential, and another that has multiple sub-cases each step that forms a tree structure- instantiated the framework to two simple yet structurally inter- esting tasks that are themselves meaningful to formal reasoning and programming: (1) binary successor, and (2) tree traversal.
We focused on studying the recursion problem-solving capabilities of the predominant transformer-based models. Guided by the proposed framework, we performed empirical studies and careful inspections into the model's Icarned mechanism. Our findings suggest that the models trained to approximate recursive computations learn programs that are non-recursive and thus fall for edge cases are limited in capacity to generalize across different depths of recursion. Our analysis and mitigation efforts show that data distribution and the model configuration could directly hinder the learned model's performance. However, we hypothesize the fundamental cause is that the model has not been optimized to represent recursive patterns well enough, Our in-context learning experiments revealed the lack of ability for LLMs to "think recursively" as it tends to mine non-recursive rules from data. Also, the models lack accuracy when performing step- wise reduction, where they may get lost in the middle or fail to apply the stopping condition.
Recursion as universal concept in language, computer science, and mathematics, is an inevitable challenge for any system to perform non-trivial problem-solving. Observing the lack of transformer-based models' abilities to capture structurally recursive patterns despite their impressive capabilities, we highlight the need to re-examine the extent to which recursive problem-solving capabilities have been effectively injected into transformer-based models through the existing training paradigm and whether&how it can be injocted.
Future works For future work, we are considering two directions: addressing the lack of success in recursion with current models and exploring their general ability to emulate program exccution. Additionally, we aim to design deep learning architectures that better learn algorithmic patterns. We hope this work will serve foundation for empirical studies on the computational capabilities of deep learning models.
On the other hand, we aim to enhance task docomposition, particularly within programmatic reasoning setups. Recent studies (Wen et al.] 2024 Drozdov et al. 2022 Yang et al. 2024 Shi et al. 2024) have explored task decomposition in programminn--relatee. contexts, highlighting its advantages. We envision a synergistic approach integrating these insights with emerging techniques such as reinforcement learning or preference learning (Mitra et al., 20244 Wang et al.. 2024), along with curriculum learning methods that start from foundational algorithmic structures.
Acknowledgeeents This research was developed with funding from the Defense Advanced Rescarch Projects Agency. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
References
Arpan Agrawal, Emily First, Zhanna Kaufman, Tom Reichel, Shizhuo Zhang, Timothy Zhou, Alex Sanchez- Stern, Talia Ringer, and Yuriy Brun. Proofster: Automated formal verification. In ICSE Demo, May 2023.
Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. Unified pre-training for program understanding and generation. ar preprint arXio:2103.0688 2021.
Loubna Ben Allal, Raymond Li, Denis Kocetkov, Chenghao Mou, Christopher Akiki, Carlos Munoz Ferran- dis, Niklas Muennighoff, Mayank Mishra, Alex Gu, Manan Dey, al. Santacoder: don't reach for the stars! ar Xie preprint arXim:2301.03966 2023.
36

---

Published in Transactions on Machine Learning Research (07/2024)
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowyez, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. arXiv preprint XrXio:2207. 04901,, 2022.
Yonatan Belinkov. Probing classifiers: Promises, shortcomings, and advances. Compulational Linguistics, 48 (1):207 219, March 2022. doi: 10.1162/coli a 00422. URL http:://aclaattoooogy wrgp//o2.....22222.../2 cl-1.7
Geogre M. Bergman. An Incitation to General Algebra and Universal Constructions. Springer, 2nd edition, 2015.
Yves Bertot and Pierre Castéran. Interactive theorem proving and program development: Coq'Art: Art: the calculus of inductive constructions. Springer Science & Business Media, 2013.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Transformers to Recognize Formal Languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (FMNLP), pp- 7096-7110 Online, November 2020a. Association for Computational Linguistics. doi: 10.18653/v1/2000 576. URL
wwwpi/ooooooooogg////eeo// prg/2020..oo...oo emnlp-main.577
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. In Raquel Fernández and Tal Linzen (eds.), Proceedings of the 24th Conference on Computational Natural Language Learning. pp. 2020b. Association for Computational Linguistics. doi: (11863//1/2020.oolll //cclaatbologg.oor//000.......l
Online, November URL https:
Egon Börger. Abstract state machines: a unifying view of models of computation and of system design frameworks. Ann. Pure Appl. Log., 133(1-3):149 171, 2005. doi: 10.1016/jappl..04410000 URL https:
//doi. 1.ool.org/1..016/...oo 1016/0001...... 2004. 10. 007
Egon Börger and Tommaso Bolognesi. Remarks on turbo asms for functional equations and recursion schemes. In Egon Börger, Angelo Gargantini, and Elvinia Riccobene (eds.), Abstract State Machines, Advances in Theory and Practice, 10th International Workshop, ASM 2003, Taormina, Italy, March 3-7, 2003, Proceedings, volume 2589 of Lecture Noles in Computer Science pp. 218 228. Springer, 2003. doi: 10.1007 (30007773---0--699---666 12. URL http:////.gaaaaatcccccocoo////pt
Egon Börger and Dieter Schewe. A behavioural theory of recursive algorithhns Sei. Compul. Program... 210:102691, 2020. URL httpp:///ppi..seaaniaaaaaaaaaaaa
Luca Cardelli and Peter Wegner. On understanding types, data abstraccion,, and polymorphism. ACM Comput. Surv. 17(4):471 523, dec 1985. ISSN 0360-0300. doi: 10.1145/6041.6042. URL https://doi,
org/10. 1115//04114// 6042
Mike Casey. The Dynamics of Discrete-Time Computation, with Application to Recurrent Neural Networks and Finite State Machine Extraction. Newnal Computation, ((6):1135-1178 08 1996. ISSN 0899-7667. doi: 10. 10.1162/neco.1996 199..8.6.169..3..... URL https: http::///ooo.oo//1...1 www.ooog//.............. 1ww..9996.... 8. 6135
Saikat Chakraborty, Toufique Ahmed, Yangruibo Ding, Premkumar T Devanbu, and Baishakhi Ray. Natgen: generative pre-training by "naturalizing" source code. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 18 30, 2022.
Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, al. Neurosymbolic programming. Foundations and Trends in Programming Languages, 7(3):188 243, 2021.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkinn Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pawlov, Alethea. Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe
37

---

Published in Transactions on Machine Learning Research (07/2024)
Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Nya Sutskever, and Woj- ciech Zaremba. Evaluating large language models trained on code. CoRR, abs/2107.0333 03334, 2021. URL (ttts://arxiv.org/aae 2207. 03374
Adam Chlipala. Certified Programming with Dependent Types: Pragmatic Introduction to the Coq Proof Assistant. The MIT Press, 2013. ISBN 0262026651.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gauray Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Scbastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengeheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thammmalyyan Sankaranarayana Pillai, Maric Pellat, Aitor Lewkowyzz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiodel. Palm: Scaling language modeling with pathways. CoRR. abs//2204.0233 2022. doi: 10. 10.48550/ arvv 2ww...2220.2211... URL https::/ddo..rrg///// 46550//rXiii 2204. 02311
Bilal Chughtai, Lawrence Chan, and Neel Nanda. A toy model of universality: Reverse engineering how networks learn group operations, 2023. URL
Arthur Conmy, Augustine N. Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Carriga-Alonss Towards automated circuit discovery for mechanistic interpretability, 2023.
Thierry Coquand and Christine Paulin. Inductively defined types. In Per Martin-Löf and Grigori Mints (eds.), COLOG-88, pp. 50-66, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg. ISBN 978-3-540-46963366
Andrew Cropper, Sebastijan Dumancic, Richard Evans, and Stephen H. Muggleton. Inductive logic pro- gramming at 30. CoRR, abs/2102.10556, 2021. URL
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe V Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.0228 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal trans- formers, 2019.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hierarchy, 2022. URL https: h //tp//aaxvvv.// www.aiiwwwaaaaaaaaeeeeeeeooeeeee abaaaba/22222 02098
Yangruibo Ding, Ben Steenhoek, Kexin Pei, Gail Kaiser, Wei Le, and Baishakhi Ray. Traced: aware pre-training for source code. arXio preprint arXim:2306.0744 07487, 2023.
Execution-
Andrew Drozdov, Nathanacl Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional semantic parsing with large language models, 2022. URL
https://arxiv, org/ abs///////// 2209.10000
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Scan Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi Faith and fate: Limits of transformers on compositionality, 2023. URL https://arrs www.vvv..../b////////ee. http:/ab/2305..1866 18654
38

---

Published in Transactions on Machine Learning Research (07/2024)
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize Dyck-n languages? In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Associalion for Compulational Linguistios: EMNLP 2020, pp. 4301 4306, Online, November 2020. Association for Computational Linguistics. doi:
10.18653/vl httpl//0....iniiiii. maningg--mmllp..e URL /ttpps//acclanbbooog.oorgg/
.fiddings emnlp.380
Emily First and Yuriy Brun. Diversity-driven aulomated formal verification. In ICSE, pp. 749 761, May 2022. doi: 00.1445/510000335100
Emily First, Markus N. Rabe, Talia Ringer, and Yuriy Brun. Baldur: phole-proof generation and repair with large language models, 2023.
Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis. Incoder: A generative model for code infilling and synthesis. arXiv preprint ar 2rXim:2004.066 005999, 2022.
Mor Geva, Roei Schuster, Jonathan Berant, and Omer Levy. Transformer feed-forward layers are key-value memorics, 2020. URL
14913
Alex Gu, Baptiste Rozière, Hugh Leather, Armando Solar-Lozama, Gabriel Synnacve, and Sida Wang. Cruxeval: A benchmark for code reasoning, understanding and execution. arXiv preprinl 2011v:2401.03065, 2024.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends0 in P Programming Languages, 4(1-2):1 119, 2017. ISSN 2325-1107. doi: 10.1561/2500000000. URL http: 10. 15611220000000000000
7/dx. doi. owgooo.///../.
Rahul Gupla, Soham Pal, Aditya Kanade, and Shirish K. Shevade. DeepFix: Fixing common C language errors by deep learning. In AAAI, 2017.
Yuri Gurevich. Evolving Algebras 1993: Liporí Guide, pp. 9-36. Oxford University Press, specification
and validation methods edition, January 1995. URL httph: wtwp:/mcrooooo..coooeeeeeeeeeeee publication/103-eront wtwp://///...ooooooooogaaggrreee -aagebrrr--9----ppr---------
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the
Association for Computational Linguisties, 8:156-171, dec 2020. doi: 10.1162/tacl a 00306. URL https:
//doi org/10. 1 6_00006
Jesse Michael Han, Jason Rute, Yuluai Wu, Edward W. Ayers, and Stanislas Polu. Proof artifact co-training for theorem proving with language models, 2022.
John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representations. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proccedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 1129-4138, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653/v1 /v1 /N199-449. URL
Danial Kamali and Parisa Kordjamshidi. Syntax-guided transformers: Elevating get.upoostiioaallneeelliilliii and grounding in multimodal environments, 2023. URL hatpe::/aarddv.orr/aa////33 04364
Stephen Cole Kleene. Representation of events in nerve nets and finite automata. 1951. URL https:
Louis Krivine. A call-by-name lambda-caleulus machine. Higher Order Symbol. Comput., 20(3):
199-207, sep 2007. ISSN 1388-3690. doi: 810990-007-9018-9
URL htttps://dii.or org/10. 1007/
Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven C. H. Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning, 2022.
39

---

Published in Transactions on Machine Learning Research (07/2024)
Woosuk Lee and Hangyeol Cho. Inductive synthesis of structurally recursive functional programs from non-recursive expressions. Proc. ACM Program. Lang., 7(POPT.), jan 2023. doi: /14453571263. URL
https://2oi.orr//0.. 1111/////1001144/1111182
Xavier Leroy, Sandrine Blazy, Daniel Kästner, Bernhard Schommer, Markus Pister, and Christian Ferdinand. CompCert A Formally Verified Optimizing Compiler. In ERTS 2016: Embedded Real Time Software and Systems, 8th European Congress, Toulouse, France, January 2016. SEE. URL https: homps://inriin //t//iiiaaaaal..... hal.
Seienneehall011211
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Mishig Davaadorj, Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming- Ho Yce, Logesh Kumar Umapathi, Jian Zhu, Ben- jamin Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jemnifer Ding, Claire Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Dan- ish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Gula, Leandro von Werra, and Harm de Vries. Starcoder: may the source be with you!, 2023.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(662)):1092 1097, 2022a.
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Ec- cles, James Koeling, Folix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Mas- son d' d'Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukeuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. DeepMind, 2022b.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata, 2022. URL
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Exposing attention glitches with flip-flop language modeling, 2023a.
Chenxiao Liu, Shuai Lu, Weizhu Chen, Daxin Jiang, Alexey Svyatkovskiy, Shengyu Fu, Neel Sundaresan, and Nan Duan. Code execution with pre-trained language models. In Anna Rogers, Jordan and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguisties: ACL, 2023, pp. 4984-4999, Toronto, Canada, July 2023b. Association for Computational Linguistics. doi: 10.18653/v1/ 2023. 1123.finding--cc.3300 URL https:://// http://aacaaatoog..orrooeee
findings-ac11.300
Shuai Lu, Daya Guo, Shuo Ren, Junjic Huang, Alexcy Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. Codexglue: A machine learning benchmark dataset for code understanding and generation. arXiv preprint wxX::2102.046600 2021.
Nicolas Magaud and Yves Bertot. Changing data structures in type theory:a study of natural mumbers. volume 2277, pp. 181-196, 12 2000. ISBN 978-3-540-43287-6 doi: 11111107--54045588 12.
Ernest G. Manes and Michael A. Arbib. Algebraic Ayprouches to Program Semantics. Springer, 1986.
Warren S McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 5:115 133, 1943.
Kevin Meng, David Ban, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in gpt, 2023.
40

---

Peter-Michael Osera and Steve 7dancewic. Type-and-exampe--irecte program synthesis. In Proceedings of the 36th ACM SIGPLAN Conference on Programméngg Language Design and Implementation, PLDI '15, pp. 619 630, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450334686. doi: (0.1145/2737924.27777 Published in Transactions on Machine Learning Research (07 (07/2024)
William Merrill. Formal languages and the nip black box. In Developments in Language Theory: 27th International Conference, DLT 2023, Umea, Sweden, June 12-16, 16, 2023, Proceedings, pp. 1 1-8, Berlin, Heidelberg, 2023. Springer- Verlag. ISBN 978-3-031-33262-00 doi: 10.1007/978---031-33326--
URL
William Merrill and Ashish Sabharwal. Transformers can be expressed in first-order logic with majority, 2022. URL
Anders Miltner, Solomon Maina, Kathleen Fisher, Benjamin C. Pierce, David Walker, and Steve Zdancewie. Synthesizing symmetric lenses. Proc. ACM Program. Lang. 3(CFFP), jul 2019. doi: 10.1145/3344 3341699.
URL https://doi org/10. wttg//..114///// 1145/3341699
Arindam Mitra, Hamed Khanpour, Corby Rosset, and Ahmed Awadallah. Orca-math: Unlocking the po- tential slms in grade school math, 2024. URL htttp:://rxii, www.oogg/abbaaooooe 14830
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. 2023. URL
Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong. Codegen: An open large language model for code with multi-turn program synthesis. arXvv preprint arXiv:2203. 19474, 2022.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXim:21 1111122.0114 2021.
Chris Olah, Mechanistic interpretability, variables, and the importance of interpretable bases, 2022. URL interp-ittrr--o essay
https://www http:///wwwwtaaafffroooo.o httprrrrrrcrcrutttt..pooppp///ee
Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar-Lezama. Is self-repair silver bullet. for code generation?, 2023.
OpenAL. Chatgpt: Optimizing language models for dialogue.
2023a.
OpenAl. Gpt-4 technical report. https:///rriv.org///oo /ttp///www..g//bb////////////// 2023b
URL https: wrtg//..114///331111 2T0117777779222..7777
Simon Ouellette, Rolf Pfister, and Hansueli Jud. Counting and algorithmic generalization with transformers. 2024. URL
08661
Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. Auto- matically correcting large language models: Surveying the landscape of diverse self-correction strategies, 2023.
Kexin Pei, David Bieber, Kensen Shi, Charles Sutton, and Pengeheng Yin. Can large language models reason about program invariants? In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 27496 27496-27520. PMLR, 23 29 Jul 2023. URL https://proceeddngss mlr. www..press/vvvvv v202/ http///22222...../ http:/epp2aaa....c. html
Jorge Pérez, Pablo Barceló, and Javier Marinkovic, Attention is turing-complete. Journal of Machine Learning Research, 22(75):1-35, 2021. URL
html
Mary Phuong and Marcus Hutter. Formal algorithms for transformers, 2022.
41

---

Published in Transactions on Machine Learning Research (07/2024)
Benjamin C. Pierce et al. Software Foundations. 2024. URL http::s://ssttrrretooaaaaassooos upenn.
edu/ [Online; accessed 13-Jamuary-2024).
Stanislas Polu and Ily Sutskever. Generative langnage modeling for automated theorem proving, 2020.
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapoaation. In International Conference on Learning Representations, 2022. URL https:
7/openreview.o //
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Πlya Sutskever. Language models are unsupervised multitask learners. 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485 5551, 2020a.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-5555 2020b.
Talia Ringer. Proof Repair. PhD thesis, 2021.
Talia Ringer, RanDair Porter, Nathaniel Yazdani, John Leo, and Dan Grossman. Proof repair across type equivalences. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, pp. 112 127, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383912. doi: 10.1115 1411144/3458488345540033 URL https:://oi...ooo org/ 10. 1 10111115544490 3454033
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers. arXiv preprint XrXi::2305. 16843, 2023.
Ripon K. Saha, Yingjun Lyu, Hiroaki Yoshida, and Mukul R. Prasad. ELIXIR: Effective object oriented program repair. In ASE, pp. 648 659, 2017.
Alex Sanchez-Stern, Yousef Alhessi, Lawrence Saul, and Sorin Lerner. Generating correctness proofs with neural networks. In Proceedings of the 4th ACM SIGPLAN International Workshop on Machine
Learning and Programming Longuages, MAPL 2020, pp. 1-10, New York, NY, USA, 2020. Associa-
tion for Computing Machinery. ISBN 9781450379960. doi: 10.1145/3394550:33774666
URL https:
1141/119411111 3397466
Alex Sanchez-Stern, Emily First, Timothy Zhou, Zhanna Kaufman, Yuriy Brun, and Talia Ringer. Passport:
Improving automated formal verification using identifiers. ACM TOPLAS, 2023.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Sell-attention with relative position representations. arXiv preprint arXiv:1803 021552 2018.
Kensen Shi, Joey Hong, Yinlin Deng, Pengcheng Yin, Manzil Zaheer, and Charles Sutton. Exedec: Execution decomposition for compositional generalization in neural program synthesis, 2024. URL https://arxiv. org/ 2307 13883
Smith and Zipser. Encoding sequential structure: experience with the real-time recurrent learning algorithm. In International 1989 Joint Conference on Newral Networks, pp. 645-648 vol.1, 1989. doi: 10.1109/IJCNN, 1989. 118446.
Beatriz Souza and Michael Pradel. Lexecutor: Learning-guided execution. arXiv preprint arXhv:2302.09343. 2023.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. Transformers as recognizers of formal languages: A survey expressivity, 2023.
42

---

Published in Transactions on Machine Learning Research (07/2024)
Kaiser Sun and Ana Marasovié. Effective attention sheds light interpretability. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Findings of the Association for Compulational Linguisties: ACL-IJCNLP 2021, pp. 4126 4135, Online, August 2021. Association for Computational Linguistics. doi: findings-diniin act.ddnnnnaa...111111
10.18653/v1/2021 http:///////222...nnnnooaaaoaa acl.ings-acl.611. URL
Alexcy Svyatkovskiy, Shao Kun Deng, Shengyu Fu, and Neel Sundaresan. Intellicode compose: Code gener- ation using transformer. In Proceedings of the 28th ACM Joinl Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp.
2020.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tie Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint ar 2tt::2201002239 2022.
Sam van der Poel, Dakotah Lambert, Kalina Kostyszyn, Tiantian Gao, Rahul Verma, Derek Andersen, Joanne Chau, Emily Peterson, Cody St. Clair, Paul Fodor, Chihiro Shibata, and Jeffrey Heinz. Mrregtest: A benchmark for the machine learning of regular languages, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances Newral Information Processing Systems, volume 30. Curran Associates, Inc., 2017. https:::t// http::ttttttteeeetiiiiiiee http:///oooeeeen..e/ee hewpeeeddinnnn..uuppssee www.wppp...pppppprereppeee /aape///prp////// 201ffffiilffee2225577ee111111363
Paper. pdf
Petar Veličković, Adrià Puigdomèncch Badia, David Budden, Razvan Pascamu, Andrea Banino, Misha Da- shevskly, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning benchmark, 2022. URL
https://arxii: www.orrgg///.eeeeeeee/..oeeeee/e aba22205 15659
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in a transformer language model. In Tal Linzen, Grzegorz Chrupala, Yonatan Belinkov, and Dieuwke Hupkes (eds.), Proceedings of the 2019 ACL Workshop BlackbozNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 63-76, Florence, Italy, August 2019. Association for Computational Linguisties. doi: 10.18633/v1/W199-
URL httpps///cclarhhoooooorrogg
Kevin Ro Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Inter- pretability in the wild: circuit for indirect object identification in GPT-2 small. In The Fleventh International Conference on Learning Hepresentations, 2023a. URL https://openrerier http:/iwwwwww......o.oee net/forumm id NpsVSSNN6l
Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifci Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce llms step-by-step without human annotations, 2024. URL https:
/aaxxiv.or// wwtp:/rrg/ab///2222// http://.1..09.333
Yue Wang, Weishi Wang, Shafiq Joty, and Steven C.H. Hoi. CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8696 8708, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: (18653//1/202..mm/ll caamnppmminn66... URL https://aclanthhology org/2011 emnlp-main. 685
Yue Wang, Hung Le, Akhilesh Deepak Gotmare, Nghi DQ Bui, Junnan Li, and Steven CH Hoi. Codet5+: Open code large language models for code understanding and generation. arXiv preprint orXiv:2305.0792. 2023b.
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: case study on approxi- mating turing machines with transformers, 2023.
Jason Wei, Xuczhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Mfaii--o--thuggee prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 95:24824-24833 2022.
43

---

Published in Transactions on Machine Learning Research (07/2024)
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11080-110000 2021. URL https://proceednnss.n /rtpp///eeecannn...rrrss//////// press/v139/ weiss21a.htm!
Jiaxin Wen, Ruiqi Zhong, Pei Ke, Zhihong Shao, Hongning Wang, and Minlie Huang. Learning task decom- position to assist humans in competitive programming, 2024. URL httttts:/aaxii...rrtt abs//a06/662 240.2040000004444
Chunqiu Steven Xia, Yuxiang Wei, and Lingming Zhang. Automated program repair in the era of large pre- trained language models. In Proceedings of the 45th International Conference on Software Engineering (ICSE 2023). Association for Computing Machinery, 2023.
Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. Wizardlm: Empowering large language models to follow complex instructions. arXiv preprint arXiv:2304. 1.t.22344..244. 12244, 2023.
Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn. A systematic evaluation of large language models code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, pp. 1-10, 2022.
Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. Byt5: Towards token-free future with pre-trained byte-to-byte models. Transactions of the Association for Compulational Linguistics, 10:291-306 2022.
Haoran Yang, Hongyuan Lu, Wai Lam, and Deng Cai. Exploring compositional generalization of large language models. In Yang (Trista) Cao, Isabel Papadimitrion, and Anaelia Ovalle (eds.), Proceedings of the 2024 Conference of the North Americon Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 4: Student Research Workshop), pp. 16 24, Mexico City, Mexico, June 2024. Association for Computational Lingnistics. URL https://aclaatthooogs org/2024 maacl-srw... 3,
Kaiyu Yang and Jia Deng. Learning to prove theorems via interacting with proof assistants. In International Conference Muchine Learning, pp. 6984 6994. PMLR, 2019.
Shunyu Yao, Binghui Pong, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeling of the Associalion for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3770-3785, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/200 waw.-.l..ll.o....... 292. URL
wwwp:/ooyy.rr/222......2 acl-looo...................o 292
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transform- ers universal approximators sequence to-ponce-----squeneeee functions? In International Conference on Learning Representations, 2020. URL.
Chiyuan Zhang, Maithra Raghu, Jon Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization, 2022a.
Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck. On the paradox of learning to reason from data. In International Joint Conference on Artificial Intelligence, 2022b. URL https://app. www.steesaannnnnite.e
Kechi Zhang, Zhuo Li, Jia Li, Ge Li, and Zhi Jin. Self-edit: Fault-aware code editor for code generation, 2023.
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthotic reasoning task, 2022c. URL https://arxiv. http://awxxx.ooorbb/////sa ab//a//b.../2../////////// 04301
Qinkai Zheng, Xiao Xia, Xu Zou, Yuxiao Dong, Shan Wang, Yufei Xue, Lei Shen, Zihan Wang, Andi Wang, Yang Li, et al. Codegeex: A pre-trained model for code generation with multilingual benchmarking on humaneval-x. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 5673 5684, 2023.
44

---

Published in Transactions on Machine Learning Research (07/2024)
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and
Preetum Nakkiran. What algorithms can transformers learn? study in length generalization, 2023. URL
Yongchao Zhou; Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers achieve length generalization but not robustly, 2024. URL http::///axxv..or////////0//00
45

---

Published in Transactions on Machine Learning Research (07 (07/2022 2024)
0.50
0.56
0.83
Test Group
Test Group
0.50
0.90
22 to 44
12asnn40 to Morus
to Ma
0.75
12202444 to 1aae -b
12 2
Fouee Faeer
Learning Rate Factor C
Leaming Rate Factor C
1.0
1.0
Training
Training Size
(a) Natural-Dethh3
(b) Natural-Depth6
0.90
0.59
Accursty
0.08
Test
0.98
Test
Train
Train
12 12
12holh 44 Drain +6
12 10
12 Frnss +20
172 Caga 4.00
0.165
Learning Rate Factor C
0.96
Learnnng Rate Factor C
0.1
0.1
-
1.0
-8
1.0
60000
20000
50030
60000
50000
100000
120000
Training Size
Training Size
(c)
Reversed-Depthh
(d) Reversed-Deeph6
Figure 25: Model performance when trained on data with more constrained recursion depths.
A Depth- Restricted Training
One of the important aspects of generalization in recursive problem is generalization across depths. We experimented with depth-restricted training, controlling the maximum depth the model saw during train- ing. Notably, the generalization performance between large and small learning rates exhibits a significant difference in natural order as shown in Figures 25a and 25b whereas the same phenomenon did not occur in reversed order.
B Extrapolation of Different Model Architectures
We were initially not whether to evaluate the tasks of interest on an encoder-only, decoder-only, encoder-decoder transformer model. To decide, ran preliminary experiments to evaluate these three architectures under our setup for related toy experiment and on one of our two tasks.
Our loy experiment. focused on string reversal. We trained models on strings ranging from 10 to 37 and tested up to length 50. We used three different architectures: a 2-layer encoder-decoder transformer model, a 4-layer encoder-only model, and a 4-layer dccoder-only model. We trained until we achieved perfect accuracy on both the training and in-domain validation datasets. We employed the same "random- paaddng" strategy in the main experiment.
46

---

Published in Transactions on Machine Learning Research (07/202) 2024)
1.00
99. 36
30
D0
90.91
07.84
96.90
98.77
92.
90
90.29
Rocodar-Only
86.36 .6
06.36
66
82.39
Encodee-Ont Only
0.50
70.09
74.12
69
89
91
Pefformacc
0.60
26 74
20.38
0.00
0.02
0.00
0.00
0.00
0.00
0.00
0.48
0.00
0.01
0.00
0.00
0.00
0.00
0.00
5
9
10
11
Extrapolation Length
Figure 26: Performance of Extrapolation Study
1.00
0.99
1.00
1.00
0.99
1.00
0.99
1.00
0.90
0.88
0.80
0.76
0.52
0.31
0.24
0.20
0.18
0.06
0.04
0.04
0.00 0.00 0.00
0.00
Encoder-Only Full Training
Encoder-Only Train Up To Depth
Encoder-Only Train Up To
Decoder-Only Full Training Range
Decoder-Only Train Up To Depth
Decoder-Orly Train Up To Depth
Range
Train
Train Length +2 to
Train Longth to +6
Train Length +8 to +1D
Train Longth +18 +20
Figure 27: Accuracy of encoder-only and decoder-only transformers on natural order binary successor task.
47

---

Published in Transactions on Machine Learning Research (07/202) 2024)
Num. Unroll Steps
3.0
Traversal
Order
Pre-Order
2.0
100
0.5
25 30
70
160
126
150
17G
Epoch
Figure 28: Tree Traversal Loss vs. Epochs
The encoder-decoder model exhibited the best extrapolation performance among the three archilectures (Figure 26 Both the encoder-only and decoder-only models experienced rapid decline in performance the extrapolation length increased. Interestingly, we also observed that the model failed to extrapolate when trained on fixed-length "lcarnable token" setup, even though we ensured that the positional embeddings were seen during training. Moreover, the model also struggled to extrapolate when padding was not applied.
The results the encoder-only and decoder-only transformers on the natural order binary successor task (each with four layers) are presented in Figure 27
C Sketch of Proof: Single layer transformer can solve one-step reduction of binary successor task.
Let us assume, for simplicity, 4 types of tokens: s, 01, xo, X1.
We assumee the token embeddings to be one-hot
Bm5)) [0, 0, 0,0,0,00,,00000 0]
Emb(S) 0, 0, 0,,0,,,0,,,0,00000
Emb(XO) |0,
Emb(X1) X1) = 1,.001,0,0,00000 Emb(01) = [0, 10,000,1,0,000,000
We assume the We matrix to extract the positional encoding of the previous token. Assuming the positional encoding onc-hot encoding of length L, the We should be able obtain the one-hot encodings of the preceding positions of each location (A permutation matrix). WK k should output 0, 0,1....,L (i.e. identity matrix). Wy should return token embedding of that token.
Assuming causal mask and residual connection after Softmax: attention output AttnOut = Sof Soffmar(QK*)) + X where X is the input to this layer. The goal is to encode the tokens preceding each Loken into the second four slots of the embedding vector. [BOS] token, with embedding vector being 0, will be written as 0 to it succeeding token's output vector. For simplicity, we write each entry in the output of this layer [x. yl where is the token embedding of this entry, y is that prior to this entry.
The MLP is supposed to perform simple non-linear operation on the output such that
48

---

Published in Transactions on Machine Learning Research (07/2024)
Procedure ShhrrsSiccessorkssurzarrrrrr
Input: BinarySequence
Output: BfnarySequence
HyperParaneters: maXDecodingLength
Initialize decodfincounterrl,, ioseererr
Initialize BinarySequence b [
]
while decodfingCuntter maxDecodiinLeength do
startRiecurstonFlag = Nodel. wwwpe//pccoor.eeeeeeeeerrrrrrrrr
Model. Decoder 1. postriicc.fcccciieeeeeeerrruuert
pecursionStartPosttioo
if not. startRecursionnLLL if startRecurs fonF Lag Sodee..Decoorr.r.cee.tsssssssss
Model.Decoder, hnttoinaanooodngeeeeeccgennnett
sequencelastPositioon
bit Model, becoder (eneddrrggneratee1100
else:
bit Model M wod....ecor...ccyyyddeeeednnneee
else:
isInRecursion:
isInRecursion=True
bit = Medel.Decoder.ggneeeee Decodee..gmmerateee1...
else:
bit bedel..ecoder.ggeerattee
b' (pptnd(bitt)
if Decoder Dec.adeessstttaaeaeeeaaaaaeeeeee
sequencelastPosiition
b' wap.peddd ("<
return b' else:
decodingCounter
Figure 29: Reconstructed Algorithm: Natural Order
maps the token embeddings of [s, X1] into the embeddings of [X1,S]
maps the token embeddings of X0] into that of [-, X1]
maps the token embeddings of 01] into that of [X1, 01]
maps the token embeddings of any other pairs to themselves.
We can implement an MLP layer such that it checks whether each pattern above occurs, and an additional condition of whether S ever appears in the input sequenco. The first part can be done casily by multiplying each embedding by a matrix M with row vectors denoting the pattern, and applying non-linearity on Mv- 1. To check if S ever appeared the sequence to determine whether or not halt, one could simply check the first row of the output O is positive by applying non-linearity.
D Reconstructed Algorithms
D.1 Algorithm Reconstruction for Binary Successor
We summarized our results for the binary successor task in Section Here, provide pseudocode for the reconstructed algorithms in both the natural (Figure 29 and reverse F Figure 30 orders.
D.2 Algorithm Reconstruction for Tree Traversals
Using the technique we introduced in 8.1 discover the algorithms learned by the model during tree traversals. The results indicate that one head prioritizes future EMPTY and parentheses tokens, while the other focuses on the token that requires copying from the original sequence. This provides insight into the attention patterns exhibited by the model al different processing stages, highlighting the key features that the model attends to.
The learned transformer model employs a set of logical rules and functions facilitated by the attention mechanism for tasks such copying tree node values producing special tokens. It uses various types
49

---

Published in Transactions on Machine Learning Research (07 (024)
Procedure SherrySiceesorreverreeddrd
Input: BinarySequence
Output: BinarySequence b
HyperParaneters: naxbecodingLengthh Initialize decod i Initíalize BinerySequence b' [
]
while decodingCounter < nexDecodingLength do:
inCopyNode andel.Decoder (aaooarrnaadeeeratee11100
1f inCopyMade:
bit bidecadinncounter]
else:
if Model.crossAtee ProssattentiooneekkfisskkkkkKk ( (t)())))
Model, (itrodrr.nterrnnsttte([(]]]
bit Beael.DDcoder..eeeraateee Generrtte11)
else:
bit
appapddd
decoeingCaunter +-
return
Figure 30: Reconstructed Algorithm: Reverse Order
(a) Layer cross-attention. The model attends only to nodes, not to parentheses or EMPTY tokens.
(b) Layer cross-attention. Attention consolidated the next node be copied, skipping all non-node items.
Figure 31: Cross-attention the pre-order full traversal task.
of attention to keep track of important token locations for either logical control flow or invocation of the mechanisms to produce the next token in the output sequence. In the task of in-order twice reduction, for instance, the model utilizes its attention mechanism to identify the appropriate reduction level and pinpoint the node whose values will be copied to the current output slot, as illustrated in Figure 325 The model combines multiple logical conditions to discern the boundary separating the remaining sub-trees and the layers set for unrolling. To generate the "UNROLL[" statement in pre-order reduction, the model's cross- attention is focused on three key positions: 1) the parenthesis immediately preceding the node where the "UNROLL [" token will be inserted, 2) the subsequent opening parenthesis, and 3) the final closing parenthesis of the subsequence that will be copied into the "UNROLL ]" statement.
In-order Partial Reduction Traversal (Example: Reduce Twice, Depth 2-3)
The network always starts by inserting an "UNROLL[" symbol.
50

---

Published in Transactions on Machine Learning Research (07/202) /224)
Need
Mozd 0
UNROLLE
425
ENTTY
ENFTY
-10
Head
Hixd]
425
6.0
P4PTY
part
(a) Layer decoder self-
attention during in-order
300
partial reduction higher
reduction depth.
(b) Layer cross-attention at the end of the left sub-tree to be unrolled.
Head 0
UNROLLI
<S>
109
390
97
ESP YY
595
EMPTY
EMPTY
579
340
EMPTY I
ESP ny
EXPTY
755
420
ESPTY TY
479
0..15
0.10
Head 1
<5>
UNROLLI
<5>
109
390
97
EMPTY
595
EMPTY
EMPTY
579-
340
EMPTY
EMPTY
EMPTY
735
420
EMPTY
479
EMPT Menn
(c) Layer cross-attention the start sub-tree be unrolled.
Head
UNROLLI
<S>
109
(-
390
97
EMPTY
$95
EMPTY
EMPTY
579
340
EMPTY
EMPTY
EMPTY
733
420
EMPTY
479-
EMPTY
EMPPTY
EMPTY 100
Head
0.2
<3>
0.0
U
<5>
1.
390
97
EMPTY
595
EMPTY:
EMPTY
579
340-
EMPTY
EMPTY
EMPTY
755
420
EMPTY
EMPTY
INPPY
EMPTY
(d) Layer cross-atlention
start sub-tree unrolled.
Figure 32: Cross-attention during inorder traversal task.
51

---

Published in Transactions on Machine Learning Research (07/2024)
2. Cross-attention attends to the token after pecling off two (since it is twice-reduction) layers of parentheses and writes this token into the final token position.
3. This process continues with the model attending to target tokens and parentheses in sequence until the first parenthesis is closed. It identifies the current depth by jointly attending to the open parentheses the input side and the previously closed parentheses
The model inserts a closing 'I' bracket. The left subtree is now complete.
5. The model attends to the token immediately preceding the closed first parenthesis and writes this token out.
6. The model then performs the same copy operation with the right subtree.
For higher depths, the model performs essentially the same operation but additionally uses decoder self- attention to attend to the beginning and end of the relevant bracket level as per Figure 32a] The significance of this attention pattern seems to suggest that it helps the network track which parent node to copy over. For shallower reductions, the model only needs to copy over the root node at the beginning of the encoder sequence, so it docs not need to track multiple parent nodes; however, for deeper trees, the model needs some indication of where the appropriate parent node can be found. Polentially, the model could use the start of the "UNROLL[] ]" sequence as a way to point to the token immediately after the appropriate parent node, which could then be used as a query to find the node prior to in the original encoder sequence.
Pre-order Partial Reduction Traversal (Example: Reduce Twice, Depth 2-3)
The model begins by copying node numbers without parentheses.
2. Depending on the depth, the model is trained to output an 'UNROLL[" token once two reductions have occurred. When writing out this token, cross-attention patterns of the key heads indicate that the model is attending to A). the parenthesis immediately prior to the node after which the 'UNROLL[" token is to be inserted, and B). the following opening parenthesis, and C). the final closing parenthesis of the subsequence that will be copied into the "UNROLL statement. This seemss to suggest that the model is keeping track of the parenthetical depth when deciding where insert the "UNROLL[...." wrapper.
3.
In parts of the output sequence into which an EMPTY token would normally be inserted with a simple copy operation, decoder self-attention is more significant to the final logit difference. Looking at attention patterns once again, we see that the model is attending to the preceding UNROLL token, if present, and is likely using it a basis for whether to output this token or not. (Subsequences inside the wrapper should contain "EMPTY" tokens, while those outside should not.)
The model completes the sequence with the end token ('<\s>"). is less clear what the model is doing here, but the most significant contributing heads attend combination of the final brackets and EMPTY tokens as well as the <\s> token of the original encoder output.
D.3 Separation of Tasks in Attention Heads
The analysis of attention patterns reveals important insights. In the in-order traversal task, Layer 1 cross- attention heads show distinct behavior: one head focuses on forward parenthesis, brackets, and EMPTY tokens, while the other attends to encoder sequence tokens linearly (Figure ??). At Layer 2 (Figure 32d both heads correctly attend to the token to be copied, suggesting they write out the next correct token based on Layer 0's output. Brackets and symbols play crucial rolc in signaling behavior changes, particularly in steps requiring the insertion of non-consecutive symbols. Decoder sell-attention heads attend to previous UNROLL [ symbols when determining the inclusion or omission of EMPTY tokens. For in-order traversal, higher depths involve attending to bracket statements for copying root nodes, unlike binary trecs with a single root node. This behavior may be utilized by decoder cross-attention heads to copy the first node within the UNROL. statement.
52

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Our analysis indicates that the individual encoder self-attention heads do not appear to play significant independent role in the transformer model's performance. This is demonstrated by our counterfactual patching experiments, which resulted in minimal changes to the network's s predictions. On the other hand, decoder cross-attention appears to be a crucial component of the transformer circuit. As the sequence progresses, however, decoder self-atiention becomes increasingly important and the model takes into account the structure of the previously-generen content (especially at higher depths, where keeping track of multiple levels of parent nodes becomes vital).
D.4 Pseudocode for dataset generation
from typing import List
def S(input_ _inauutbinnay: List [str]) -> List[str]:
if input_binary =- ['01]]: # Base
return ['X0', '01']
elif input_binaryl [0] -- ['X0']: # ren-recursive case
return ['x1'] imput_ input_binar binaryiiaaiii [1:]
elif input_ buput_binary// [o] ['x1]]: Recursive case
return ['X0'] + ((input_bina)) binary (1:])
from typing import List, Union
class TreeNodee:
def .iinit___ (self, val=0, left=None, right=None); self. val val
left = left self.right right
def print_treee tetetrreerrooo Union [TreeNode, None]) Union None]:
# Base case: If the root is None, return None to represent an empty subtree. if root is None: return None
Recursively print the left subtree and the right subtree. Left_aubtres trenttt.rrerroottee right_subtree subtree print_ tree (root.right)
# Construct branches for the left and right subtrees. if left_subtree is None:
branch ['LEAF']
elae:
left_branch ['(+] + Left_subtres [')']
if right_ subtree is None: right_branch ['LEAF']
else:
right_brant funttbbrncchee [* right_suus Sightreubbree_e + [))+]
# Construct the representation of the current tree node and its subtrees. tree_reet rww.rerereetttiionnnn [atr (rooot.vvv) val)] +
+ branch
return reeereppresnn
E Additional Visualizations
53

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
E CENNN
15
(a) T-SNE plot for the encoder bedding.
(b) T-SNE plot for the decoder layer 0 self-attention output (before cross- attention).
(c) T-SNE plot for the decoder layer self-attention output.
Figure 33: Visualization of T-SNE plots.
06
BC1
BC2
012
00
10
10
16 1788
206
Andhitenture (n.igN husudds d_mnde))
(a) Results up-scaling models binary-successor reverse order.
RCC
1009
236
250
512
200
510
250
012
250
112
120
315
125
532
135
012
125
012
128
Anchituctoro (nnlem
(b) Results up-scaling models binary-successor natural order.
Figure 34: Up-scaling models binary successor task. We observe slight benefits from increasing the model size (i.c. hidden dimension number of heads and layers.)
54


Reviews:
[{"review_id": "xhD5EjdnQJ", "reviewer": "Reviewer_iF1k", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe paper has several notable strengths:\n\n* The proposed framework is well-motivated, comprehensive and general. It provides a principled way to investigate structural recursion in sequence models by cleanly connecting abstract recursive concepts to concrete sequence modeling problems and model behaviors. The framework supports both syntax and semantics, and the dual semantic models (reduction and ASM) enable reconciling symbolic and neural behavior.\n* The framework is thoughtfully and flexibly designed to handle complexities like the non-recursive nature of transformers, the impacts of pre-training in large language models, and in-context learning.\n* The two chosen tasks - binary successor and tree traversal - are simple yet interesting, and capture different types of recursive structure. They serve as strong test cases for the framework.\n* The empirical methodology is thorough and multi-faceted. For each task and model, the authors examine representation capacity, execution ability, attention patterns, failure modes, and more. They employ techniques like perturbation analysis, counterfactual patching, and probing to reverse engineer learned algorithms.\n* The results are insightful and impactful. Key findings include: models learn non-recursive shortcuts that fail on edge cases; it's difficult for models to learn recursive patterns from a few examples; and models can perform partial recursion but struggle to fully capture semantics. Practical mitigations like data balancing are discussed.\n* Connections to theory and practice are emphasized throughout. The authors relate empirical results back to their theoretical framework, discuss gaps between theory and practice, and highlight how the work can guide more reliable use of sequence models for recursive tasks.\nThe paper is comprehensive, with many additional results and analyses provided in the appendix. Yet the main body is kept streamlined and digestible.\n\nIn summary, this is an impressive paper that advances our understanding of learning recursion and provides a solid foundation for future work at the intersection of sequence modeling and structural recursion. The framework is well-designed and general, the empirical investigations are extensive and insightful, and the discussion connects theory and practice.\n\n**Weakness**\n\nWhile the paper is strong overall, there are a few areas that could be improved:\n\n* The framework is complex and takes significant effort to fully understand. The connections between the syntactic encoding, reduction semantics, ASM semantics, and recursive/non-recursive model implementations are conceptually dense. More explanatory prose and figures could help make the framework more accessible to a broader audience. That said, given the inherent complexity of the topic, the authors do a commendable job laying out the framework piece by piece.\n* The empirical results, while extensive, can feel a bit scattered at times. The sheer number of model variations, task set-ups, and analysis techniques used makes it difficult to maintain a cohesive narrative throughout the experiments section. The authors could consider restructuring to prioritize the most important results and provide clearer takeaways before diving into additional variations. However, the overall empirical methodology is sound and justified given the goal of comprehensively stress-testing model capabilities.\n* Some of the experiments, such as in-context learning with very large language models, are less conclusive than others due to computational and API constraints. It would be ideal to further scale up these experiments, but the preliminary results still provide valuable insights and lay groundwork for future work. The authors are transparent about experimental limitations.\n* The paper is very long and dense, which may hinder broad readership. However, the length is justified by the scope of the contributions - the framework is nuanced and the empirical investigations are extensive. The authors balance this by keeping the main body focused and deferring many details to the appendix.\n* Societal impact and future directions could be discussed in more depth. However, this is understandable given the conceptual nature of the contributions, and the authors do touch on these points in the conclusion. Future work could further explore how the framework can translate to more reliable deployment of recursive models in real-world applications.\n\nIn summary, the weaknesses are relatively minor and do not significantly detract from the paper's contributions. The main points that could be improved are: 1) Making the dense theoretical framework more accessible, 2) Streamlining the presentation of empirical results, 3) Strengthening experiments that were limited by computation. However, the authors have clearly put a lot of thought into balancing the paper's complexity with explanatory clarity, and the results are significant despite any experimental constraints. Overall this is strong work that will likely have substantive impact on the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a comprehensive framework for investigating the ability of transformer-based models to learn structural recursion from examples. The core contributions are twofold:\n\n* First, the authors introduce a general framework for representing and reasoning about structural recursion with sequence models. The framework supports syntax through a sequential encoding based on inductive representations of recursively defined datatypes. It supports semantics through both a stepwise reduction semantics that connects the syntax to traditional programming language semantics, and an Abstract State Machine (ASM) semantics that enables interpreting and analyzing the algorithmic behavior of learned models in implementing those semantics, even when the models are not architecturally recursive. The framework takes into account the complexities of analyzing transformer models, which are not architecturally recursive, and the added intricacies introduced by the knowledge and capabilities acquired during pre-training in large language models.\n\n* Second, guided by their framework, the authors conduct an empirical investigation of sequence model behavior on structurally recursive tasks. They instantiate the framework to variants of two concrete tasks: learning the binary successor function and learning various tree traversals. For each task, they design and conduct experiments to understand the behavior of small transformer models trained from scratch. They reconstruct the learned algorithms and identify specific non-recursive shortcuts the models take, reverse engineer failure cases, and provide mitigations. Additionally, they briefly investigate the ability of pre-trained language models to learn recursive algorithms through fine-tuning and in-context learning. The results suggest transformer models trained on input-output pairs do not fully capture recursion semantics and instead fit shortcuts pruned to edge cases. The models also struggle to mine and execute recursive algorithms from a few in-context demonstrations.\n\nOverall, the paper takes important steps towards understanding how to better handle recursion with sequence models, helping bridge the theory and practice of learning recursion. The framework and empirical results pave a path towards more reliable performance on the many tasks for which recursion is fundamental.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please check the weakness part", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "u1Sxe1siAK", "reviewer": "Reviewer_APjT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: The paper provides both a framework for studying structural recursion, and also empirical investigations on the practical considerations of trained models. \n\n**Questions and comments**:\n- Could you explain why ASM is considered as a part of semantics rather than syntax (structure)? If we think of replacing natural numbers with dinosaurs as replacing semantics while preserving syntax, isn't this also allowed in ASM?\n- the phrase \"sequential encoding\" may cause potential confusion, if we think of Transformer as being more parallel than sequential as compared to, say, RNNs. Encoding may also be confused to encodings (e.g. hidden variables / outputs) of a neural network.\n    - Moreover, currently \"sequential encoding\" seems to be a special concept proposed in this work, but it is actually not as it is how the syntax for e.g. programming languages are described (as also mentioned in the paper).\n- task decomposition: this idea is related to chain of thought (CoT), where providing intermediate steps help with training or inference, but too many intermediate steps can be computationally inefficient. Hence an important question is to determine the type and granularity of intermediate supervisions. For instance, there could be some middle ground between the 2 cases in Sec 4.1.2, or potentially other (unintuitive) ways to decompose a recursive structure. Could you share your thoughts on this please?\n- A related question to the above is how to understand errors in learning compositions of rules: how can we understand the errors in end-to-end computation, if there are ways to decompose the task other than following the reductions specified by the grammar?\n- I don't necessarily agree with the comment in Sec 4.2.4 that mechanistic interpretability is an exercise of ASM-style analysis: mechanistic interpretability also involves discovering the algorithm implemented by a trained Transformer, which, although being (unavoidably) limited to the set of operations a person could think of, is more general than following the set of rules allowed by a given (but unknown) ASM. Please let me know if I misunderstand something.\n- Sec 7.2: should I think of the reliance on positional encoding as expected, if I think of the position to be related to the structure of the data and that the model learns such structure, especially if the training sequences are of the same length? In other words, some failure modes might be a natural consequence of the training recipe.\n- I'd suggest more clearly separating representational considerations and optimization challenges.\n    - Sec 8.4: about increasing the width/depth/heads: do you think the gain results more from optimization or representational benefits?\n    - Please consider adding a discussion on the relation to the literature on length generalization and even OOD challenges in general.\n\n**Clarifications**:\n- Sec 4.2.3: I don't understand what \"natural impulse\" means.\n- Sec 6.1.2: to clarify, do you use all $2^n$ binary strings during training for sequences of length $n$? Or is $2^n$ merely an upper bound?\n- Sec 6.2: there's a typo in the example in the first paragraph?\n- Sec 7.1: what are the criterions to determine whether an attention head is a recursive head?\n- Sec 7.4: what does it mean by \"the weaker notion of executing the algorithm\"?\n- Sec 8.4, \"transformers have demonstrated the capability to learn to parse reductions of a specific number of steps\": could you provide references please?\n- Sec 10: what does \"the model summarized program\" mean?\n- Sec 11: I'm not sure Perez et al. 2021 is closely related to the narrative of this paragraph, as Perez et al. uses repeated applications of a constant-depth Transformer, whereas this paragraph talks about a varying-depth Transformer (whose depth grows with the recursive depth).\n\n**Writing**: I appreciate it that the paper provides sufficient background and is self-contained. However, some discussions (e.g. some examples in Sec 3 & 4, and details in Sec 6) could be moved to the appendix to make the main paper cleaner to read. The empirical findings could be summarized more crisply.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a framework for understanding structural recursion that separates syntax and semantics.\n- For syntax, the paper proposes to describe it with an inductive type, which consist of base cases and inductive bases. Such description helps to separate syntax (i.e. structure) from semantics (i.e. meaning) while being sufficiently general. For example, it can capture programming languages.\n- For semantics, the paper provides two choices: 1) stepwise reduction, following the 3 types of rules specified in $\\delta\\beta\\iota$-reduction, and 2) abstract state machine (ASM) which provides a more general definition that can capture various structures encountered in math and programming.\n\nThe paper also conducts empirical investigation on Transformers' behaviors on 2 structurally recursive tasks, namely, learning the binary successor function and tree traversals. The paper includes interpretability analyses to understand the algorithms implemented by the learned models. The results suggest that Transformers do not necessarily follow the state transitions associated with an ASM, since Transformers may depend on spurious information such as the position. While the experiments mainly focus on models trained from scratched, there are also results on finetuned models and in-context learning, which find similar inability of learning recursive structures.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please help address the clarifications and writing suggestions mentioned above.", "broader_impact_concerns": "There is no direct ethical or societal implication of the current work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2udLCmtA0G", "reviewer": "Reviewer_QYN4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* It is unclear what is meant by \"framework\" in this paper. It is not a new system or algorithm. It appears the authors are calling their investigation/study a framework - but frameworks are reusable and to some extent widely applicable. Here, the study was limited to just two structurally recursive tasks: (a) learning the binary successor function and (b) learning tree traversals. The actual claims in the paper title, abstract and introduction are much broader starting from discussions on program synthesis, theorem proving, textual occurrences of recursion, etc. while the technical contribution is quite narrow. \n\n* There are some broad statements in the paper that are not well-supported by analytical reasoning or empirical data. They are alos not warranted for the main topic of the paper and could be dropped. \"Transformer models are not architecturally recursive—they do not call themselves.\" While this is true superficially, can we make such a categorical declaration ruling out the possibility that the attention learned within transformers are implementing recursion - particularly, with the new moving average attention mechanisms that allow mimicking memory across contexts. Also, when reporting hypothesis from the experiments, the claims are left rather soft such as \" the transformer models we have trained do not strictly implement the kinds of state transitions one might associate with an RASM\" - it would be good if the paper put forward some concrete observations even if they are conditioned rather than conclude with soft conjectures. \n\n* Leaving aside a rehash of standard literature in formal methods and PL, the main contribution of the paper is in Section 5 wherein experiments were conducted on binary succession and tree traversal datasets. Section 7.4 on varying LR is interesting and could be expanded with explanation of the observations. \n\n* The observation that transformer models can perform full preorder traversals on unseen trees, but fail completely for inorder traversals is very interesting and could have wider applicability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper belongs to a class of recent attempts to investigate the learning capability of transformers from the lens of formal grammar. It focuses on representing and reasoning about structural recursion - that is, recursion on data structures. It also reports on empirical investigation of learned models’ algorithmic behaviors on structurally recursive tasks. In particular, the paper studies two tasks: binary succession and tree traversal.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper's title, abstract and claims should be focussed to the actual investigation in the paper. Some of the unsupported claims in the paper can be dropped or provided with more evidence. \n\nThere is some repetition in the paper - defining and applying the framework can be merged. The discussion on representation of \"syntax\" and \"semantics\" can be consolidated into a single section. Similarly, the fact that only two tasks are being considered can be stated upfront and does not need to be repeated multiple times. \n\nThe discussion on the benefit of generalizability of inductive types is well-known in formal methods and several systems such as PVS, Coq, Lean have implemented these (in some cases for three decades). It seems to be orthogonal to the contributions of the paper. Similarly, the discussion on semantics and ASM is standard in any PL textbook and just a reference would suffice. \n\nFor \"in-context learning\", it is widely known that the models are sensitive to prompts - what measures were taken to ensure that the used examples and prompts were effective?", "broader_impact_concerns": "There are no broader impact concern with this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that the paper tackles an important research question. Two reviewers were most positive and further highlighted how the paper is well designed, bridges theory and practice and provides fruitful insights on how to investigate what complex ML models can learn through formal PL methods. At the same time, they raised a number of concerns pertaining the dense writing (the material is squeezed into ~34 pages + 10 pages appendix, but could likely benefit from more), the scattering of experimental results and the lack of a clear-cut message after some experiments (adding recap boxes and takeaway messages can help).

One reviewer has been skeptical about the claims of the paper and voted towards rejecting it considering that the two example scenarios analyzed are simple and might be too far from real-world reasoning scenarios. I agree on the simplicity of the scenarios investigated, but disagree that this invalidates the claims (one needs only one counterexample to disprove a "common hypothesis" which in this case is that Transformers can flawlessly handle recursion).

Authors in the rebuttal phase addressed the most important aspects in the comments, clarifying the major concerns of two reviewers. However, they did something "unorthodox" for TMLR by not uploading a revised version of the manuscript that includes all the promised changes. I am recommending acceptance nevertheless, as two reviewers were still happy after the discussion. Please note however that this *acceptance is conditional* on the fact that the authors implement all the reviewers' requests (especially APjT and iF1k) in their minor revision. These requests are not optional and the paper will only be published if all the comments have been addressed in the new revision. Also note that TMLR does not have multiple rounds of revision as other journals.
Decision: Accept (poster)