Transformers are Efficient Compilers, Provably

## Abstract

Abstract Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks, including programming language understanding and generation. In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective. To this end, we introduce a representative programming language, Mini-Husky , which encapsulates key features of modern C-like languages. We show that if the input code sequence has a bounded depth in both the Abstract Syntax Tree (AST) and type inference (reasonable assumptions based on the clean code principle), then the number of parameters required by transformers depends only on the logarithm of the input sequence length to handle compilation tasks, such as AST construction, symbol resolution, and type analysis. A significant technical challenge stems from the fact that transformers operate at a low level, where each layer processes the input sequence as raw vectors without explicitly associating them with predefined structure or meaning. In contrast, high-level compiler tasks necessitate managing intricate relationships and structured program information. Our primary technical contribution is the development of a domain-specific language, Cybertron , which generates formal proofs of the transformer’s expressive power, scaling to address compiler tasks. We further establish that recurrent neural networks (RNNs) require at least a linear number of parameters relative to the input sequence, leading to an exponential separation between transformers and RNNs. Finally, we empirically validate our theoretical results by comparing transformers and RNNs on compiler tasks within Mini-Husky .

## 1 Introduction

Transformers (Vaswani, ) have demonstrated remarkable proficiency across various domains, achieving near-expert performance in solving International Mathematical Olympiad problems (Google Deepmind, ) and excelling in complex reasoning tasks in science, coding, and mathematics (OpenAI, ).. They also handle routine coding tasks with high precision, such as translating Agda code into TypeScript, outperforming the outdated and expensive-to-maintain AgdaJS compiler (Taelin, ), and integrating into code editors to significantly boost programmers’ productivity (cur, ; Taelin, ). Despite these advancements, the full extent of their underlying capabilities remains only partially understood.

In this paper, we aim to deepen our understanding of transformers’ abilities to perform compilation tasks. Empirically, transformer-based LLMs have shown rapid progress in code generation and compilation. For example, MetaLL  (Cummins et al., ) enables LLMs to optimize code by interpreting compiler intermediate representations (IRs), assembly language, and optimization techniques. Gu () highlights the ability of LLMs to generate high-quality test cases for Golang compilers. Surprisingly, Taelin ()demonstrates that models like Sonnet-3.5 can compile legacy code into modern languages like TypeScript, outperforming the now obsolete AgdaJS compiler (Agda Development Team, ).

To formally study this problem in a controlled setup, we designed a C-like programming language called mini-husky, which encapsulates key features of modern C-like languages such as (Flanagan, ) and Rust (Klabnik & Nichols, ). We focus on three representative compilation tasks: abstract syntax tree (AST) construction, symbol resolution, and type analysis. The AST is a recursive structure that represents the input as a tree. From the perspective of programming language design, the AST is considered the true representation of the input, with the textual code serving merely as a convenient interface for human users (Alfred et al., ). All syntactic and semantic processing can then be interpreted as specific operations on these trees. Symbol resolution involves verifying the validity of references to entities and flagging errors for undefined symbols. Type analysis encompasses both type inference, which assigns types to variables without explicit annotations, and type checking, which identifies mismatches between actual and expected types.

We demonstrate that, under the clean code principle (Martin, ), transformers with a number of parameters that scale logarithmically with the input length can efficiently perform AST construction, symbol resolution, and type analysis. To the best of our knowledge, this is the first theoretical demonstration that transformers can function as compilers in a parameter-efficient manner.

We further compare transformers and recurrent neural networks (RNNs). By connecting the type analysis task with the associative recall, we show even under the *clean code principle* (Martin, ), RNNs require a memory size that scales *linearly* with the input sequence length to successfully perform type analysis. Consequently, for type analysis in compilation, transformers can be *exponentially more efficient* than RNNs. We also empirically validate our theoretical findings by demonstrating the superiority of transformers in the type analysis task.

Technical Challenges and Our Technique.

Proving that transformers can perform compilation tasks presents several challenges:

- •
Transformers operate at too low a level. Transformers process sequences of floating-point vectors, akin to raw bits in computers, and proving their ability to perform specific tasks is similar to writing specialized parallel machine code. Previous work (Yao et al., ) often resorts to graphical illustrations for readability, even for basic tasks.
- •
Compilers are exceedingly high-level. Compilers are one of the most challenging programming projects in our era and early C compilers.
Compilers are among the most complex programming endeavors of our time. Compilation involves numerous sophisticated procedures, some of which are undecidable or computationally expensive, such as code optimization (Alfred et al., )) and type analysis  (Pierce, ). For example, type analysis in complex type systems poses significant challenges, often requiring the development of advanced logical frameworks  (Dunfield & Krishnaswami, ).

To overcome these challenges, we design a domain-specific language (DSL) called Cybertron to serve as the proof vehicle, i.e., a major part of our proof consists of reasoning about type-correct code in Cybertron that represents a transformer. Without using Cybertron, writing an equivalent natural language proof would be too complex and intractable.
Using code to prove propositions is not new to computer science; it is, in fact, the norm in interactive theorem proving (ITP)  (Harrison et al., ).
ITP focuses on generating computer-verifiable proofs through a combination of human-guided instructions and software automation. For instance, the correctness of the Kepler conjecture (Hales et al., ) is verified by the combination of the ITP theorem provers HOL Light (Harrison, ) and Isabelle (Paulson, ).
o our knowledge, we are the first to apply this approach to understanding neural networks.

Contributions. We summarize our contributions below:

- •
A testbed for compilation tasks: We introduce Mini-Husky, a simple yet representative C-like programming language, designed to formally assess transformers’ capabilities in programming language processing. We anticipate that Mini-Husky will become a standard testbed for this purpose.
- •
Expressive power theory of transformers as compiler: We provide a formal proof that, when the input code sequence has bounded AST depth and inference depth, the number of parameters in transformers only needs to scale logarithmically with the input sequence length to handle compilation tasks such as AST construction, symbol resolution, and type analysis. To the best of our knowledge, this is the first study exploring the power of transformers as compilers.
- •
Transformers vs. RNNs: Theoretically, we demonstrate a negative result, showing that the number of parameters in RNNs must scale linearly with the input sequence length to perform type analysis correctly. This result establishes an exponential separation between transformers and RNNs. We further empirically confirm the advantage of transformers for the type analysis task.
- •
A Domain-Specific Language for Proofs: Given the challenges in formal proofs, we design a domain-specific language, Cybertron, to serve as a proof vehicle. We believe that Cybertron, and the general approach of using DSLs for analysis, can have broader applications in understanding transformers and other architectures.

## 2 Related Work

Expressive Power of Transformers.
A line of work studies the expressive power of attention-based models. One direction focuses on the universal approximation power (Yun et al., ; Bhattamishra et al., ; ; Dehghani et al., ; Pérez et al., ). More recent works present fine-grained characterizations of the expressive power for certain functions in different settings, sometimes with statistical analyses (Edelman et al., ; Elhage et al., ; Likhosherstov et al., ; Akyürek et al., ; Zhao et al., ; Yao et al., ; Anil et al., ; Barak et al., ; Garg et al., ; Von Oswald et al., ; Bai et al., ; Olsson et al., ; Akyürek et al., ; Li et al., ; Hao et al., ; Pérez et al., ; Strobl, ; Chiang et al., ; Wei et al., ; Wang et al., ; Feng et al., ; Li et al., ; Reddit User, ).
The most related one is Yao et al. () where the authors prove constructively that bounded depth Dyck language can be recognized by encoder-only hard attention transformers, which has similarities to our settings of bounded depth programming language recognized encoder-only hard attention transformers.
The major difference is that we introduce concepts and tasks from programming language theory Pierce () to study the semantic powers of transformers.

Transformers vs. RNN.
It is important to understand the comparative advantages and disadvantages of transformers against RNNs.
Empirically, synthetic experiments have shown an advantage of transformers against RNNs for long range tasks (Bhattamishra et al., ; Arora et al., ). Theoretically, there has been a rich line of work focusing on comparing transformers and RNNs in terms of recognizing formal languages (Bhattamishra et al., ; Hahn, ; Merrill et al., ), which show that the lack of recursive structure of transformers prevent them from recognizing some formal languages that RNNs can recognize.
However, the gap can be mitigated when we consider the bounded length of input or bounded grammar depth (Liu et al., ; Yao et al., ), which is quite reasonable in practice and is used in this paper.
On the other side, prior work (Jelassi et al., ; Wen et al., ) proves a representation gap between RNNs and Transformers in repeating a long sequence.
In summary, it is somehow intuitive that recursive structures with limited memory perform badly at tasks which requires information retrieval. Our paper shows that semantic analysis for programming languages is such a task.

DSLs for Transformers.
We note that we are not exactly the first one to employ a domain-specific language to understand the expressive powers of transformers. Previously, DSLs with simple typings like RASP (Weiss et al., ) were proposed to prove constructively that transformers can do various basic sequence-to-sequence operations. Lindner et al. () writes a compiler that compiles RASP into actual transformers, Friedman et al. () shows that RASP can be learned, and Zhou et al. () uses RASP to prove that simple transformers can perform certain algorithms. The major difference between RASP and our DSL Cybertron is that Cybertron has a powerful algebraic type system that helps to prove complicated operations beyond simple algorithms.

## 3 Preliminaries

The major innovation in the transformer architecture is self-attention, which processes input tokens in a distributed manner. This capability enables the model to handle long-range dependencies, a crucial feature for langauge tasks.
We use hard attention and simplified position encoding to simplify our theoretical reasoning.

##### Attention.

In practice, attention heads use soft attention. Given model dimension $d_{\text{model}}$, number of heads $H$, and a finite set of token positions $\operatorname{Pos}$, an attention layer with simplified position encoding is defined as a function $f_{\text{attn}}:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\rightarrow\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$ given by

$$ $\forall p\in\operatorname{Pos},\quad{f_{\text{attn}}(X)}_{p}:=W_{O}\,\text{Concat}\left({\text{Attn}^{(1)}(X)}_{p},\ldots,{\text{Attn}^{(H)}(X)}_{p}\right),$ (1) $$

where the $h$th attention head is defined using soft attention as:
${\text{Attn}^{(h)}(X)}_{p}:=\sum_{p^{\prime}\in\operatorname{Pos}}\alpha_{p,p^{\prime}}^{(h)}V^{(h)}_{p^{\prime}}.$
The attention weights $\alpha_{p,p^{\prime}}^{(h)}$ given by:
$\alpha_{p,p^{\prime}}^{(h)}=\frac{\exp\left({Q^{(h)}_{p}}^{\top}K^{(h)}_{p^{\prime}}+\lambda^{(h)\top}\Psi_{p^{\prime}-p}\right)}{\sum_{p^{\prime\prime}\in\operatorname{Pos}}\exp\left({Q^{(h)}_{p}}^{\top}K^{(h)}_{p^{\prime\prime}}+\lambda^{(h)\top}\Psi_{p^{\prime\prime}-p}\right)},$
where $W_{O}\in\mathbb{R}^{d_{\text{model}}\times d_{\text{model}}}$ are trainable parameters, $Q^{(h)}_{p},K^{(h)}_{p},V^{(h)}_{p}\in\mathbb{R}^{d_{\text{model}}/H}$ are linear transformations of $X_{p}$, $\lambda^{(h)}\in\mathbb{R}^{2}$ depends on the head, and $\Psi_{q}=\begin{pmatrix}q\\
1_{q>0}\end{pmatrix}\in\mathbb{R}^{2}$ accounts for relative position.

For theoretical convenience, we use hard attention, commonly used in theoretical analysis of transformer (Yao et al., ; Hahn, ). Hard attention can be viewed as the limit of soft attention when the attention logits become infinitely large. The hard attention head is defined as:

$$ ${\text{Attn}^{(h)}(X)}_{p}:=\frac{1}{|S_{p}|}\sum_{p^{\prime}\in S_{p}}V^{(h)}_{p^{\prime}},\leavevmode\nobreak\ \leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\ S_{p}=\arg\max_{p^{\prime}\in\operatorname{Pos}}\left({Q^{(h)}_{p}}^{\top}K^{(h)}_{p^{\prime}}+\lambda^{(h)\top}\Psi_{p^{\prime}-p}\right)$ (2) $$

In other words, hard attention selects the positions $p^{\prime}$ that maximize the attention score for each position $p$, and averages the corresponding value vectors $V^{(h)}_{p^{\prime}}$.

##### Feed-Forward Layer.

Given model dimension $d_{\text{model}}$, and a finite set of token positions $\operatorname{Pos}$, a feed-forward layer is a fully connected layer applied independently to each position, defined as a function $f_{\text{ffn}}:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\rightarrow\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$ given by

$$ $\forall p\in\operatorname{Pos},\quad{f_{\text{ffn}}(X)}_{p}=W_{2}{\sigma_{\operatorname{ReLU}}}\left(W_{1}X_{p}+b_{1}\right)+b_{2},$ (3) $$

where $W_{1}\in\mathbb{R}^{d_{\text{ffn}}\times d_{\text{model}}}$ and $W_{2}\in\mathbb{R}^{d_{\text{model}}\times d_{\text{ffn}}}$ are trainable weight matrices, $b_{1}\in\mathbb{R}^{d_{\text{ffn}}}$ and $b_{2}\in\mathbb{R}^{d_{\text{model}}}$ are trainable bias vectors, $d_{\text{ffn}}$ is the hidden dimension of the feed-forward layer, chosen to be $2d_{\text{model}}$, as commonly used in practice, ${\sigma_{\operatorname{ReLU}}}$ is the ReLU activation function.

##### Encoder-Only Transformer.

Encoder-only transformers consist solely of the encoder stack, making them ideal for tasks like classification, regression, and sequence labeling that do not require sequence generation. Each encoder layer includes a multi-head self-attention mechanism and a feed-forward network, allowing the model to capture complex dependencies and contextual information.

One can define it using the following recursion,

- •
The input is given by: $X^{(0)}=X$.
- •
For each layer $l=1,2,\dots,L$:
–
Compute attention output:
$\hat{X}^{(l)}=X^{(l-1)}+f_{\text{attn}}^{(l)}\left(X^{(l-1)}\right),$
–
Compute feed-forward output:
$X^{(l)}=\hat{X}^{(l)}+f_{\text{ffn}}^{(l)}\left(\hat{X}^{(l)}\right).$

In the above, $f_{\text{attn}}^{(l)}$ are the attention layers, and $f_{\text{ffn}}^{(l)}$ are the feed-forward layers, with the same model dimension $d_{\text{model}}$, number of heads $H$, and set of token positions $\operatorname{Pos}$. For simplicity, layer normalization is ignored. See Appendix [C](#A3) for full details of transformers and other architectures.

## 4 Programming Language Processing and The Target C-Like Language: Mini-Husky

Recently, transformers have expanded to include code analysis and generation (Nijkamp et al., ; Chen et al., ; Anysphere, ).
Programming languages offer a cleaner foundation for studying language understanding, as their syntactic and semantic tasks are precisely defined.
To formally study the language processing capabilities of transformers,
we design Mini-Husky, a representative mix of modern C-like languages with strong typing and typical syntactic features. It supports user-defined types (e.g., structs, enums) and enforces strict type equality, disallowing implicit conversions. Lexical scoping, including shadowing, ensures proper variable accessibility based on block structures, type inference, and checking.
These features make *the Mini-Husky compiler* a representative task to evaluate transformers’ capabilities in syntactic and semantic tasks like symbol resolution and type checking. See Appendix [E](#A5) for the full details of Mini-Husky.

The standard pipeline of processing programming languages is shown in Figure [1](#S4.F1) (Alfred et al., ). The raw text is firstly segmented into parts like literals, identifiers, punctuations, keywords, etc, called token stream, then parsed into a tree like structure representation of the generation process of the input, finally syntactic and semantic analysis is performed on the tree.
In this paper, to simplify the presentation, we assume tokenizer has been provided priori.
Below we describe key tasks of programming language processing.

Figure: Figure 1: Programming language processing pipeline

Abstract Syntax Tree Construction. Abstract Syntax Tree (AST) is a hierarchical, tree-like representation of the syntactic structure of source code in a programming language. Unlike the raw text of the code, the AST abstracts away from surface syntax details, capturing the essential elements and their relationships in a structured form. Each node in the AST corresponds to a construct occurring in the source code, such as expressions, statements, or declarations. This representation is central to various stages of language processing, enabling efficient syntax checking, semantic analysis, and code generation.
The formal definition of ASTs is standard in the programming language literature but is lengthy, so we defer to Appendix [A](#A1).

The AST construction task’s final output is the collection all AST nodes.
We will show transformers can construct AST efficiently.

Symbol Resolution.
In programming languages, symbols are functions, types, generics, variables, macros, etc. They are defined in one place and can be used by referring to the corresponding identifier or path in a certain scope. The scope can be within a certain tree of modules, or within a certain curly bracketed scope within one module.
For simplicity, we only consider curly bracketed scope.

In Mini-Husky, the following showcases symbol resolution.

The outer function $f$ is accessible everywhere in the body of function $g$.
However, the inner function $f1$ can only be used inside the body of $f$ as it is defined within the body.
For variables with the same identifier \ColorboxmygrayInlinea, the first is accessible from lines 4 and 5, the second is accessible from line 12, the third is from line 10, and the fourth is not accessible from anywhere.
Thus $x=1,y=3,z=2$.

The output of the symbol resolution task is the collection of symbol resolution results on all applicable tokens.
More concretely, the output is a sequence of values of type \ColorboxmygrayInlineOption<SymbolResolution> where \ColorboxmygrayInlineOption<SymbolResolution> is the type \ColorboxmygrayInlineSymbolResolution with a null value added for non-applicability and \ColorboxmygrayInlineSymbolResolution is the type storing the result of the symbol resolution, being either a success with a resolved symbol of type \ColorboxmygrayInlineSymbol or a failure with an error of type \ColorboxmygrayInlineSymbolResolutionError.
We shall prove that transformers can do symbol resolution and that attention is crucial.

Type Analysis.
In general, type is essential for conveying the intended usage of the written functions and specifying constraints.
As a first exploration of this topic, we try to make the type analysis in Mini-Husky as simple as possible yet able to bring out the essential difficulty.
The type system consists of four sequential components: (1) Type definition, (2) Type specification, (3) Type inference, and (4) Type checking. Due to the page limit, here we only introduce (4) Type checking because it is the final step and this is a crucial step which separates transformers and RNNs.
See Appendix [E.1](#A5.SS1) for details of (1) Type definition, (2) Type specification, and (3) Type inference

(4) Type checking. Type checking ensures that the type expressions agree with its expectations. For simplicity, we do not allow implicit type conversion, so the agreement means exact equality of types. The arguments of function calls are expected to have types according to the definition of the function. The operand type of field access must be a struct type with a field of the same name. The type of the last expression of the function body or the expr in the return statement must be equal to the return type of the function. For variables defined in the \ColorboxmygrayInlinelet statement,
If the types are annotated, the types of the left-hand side and right-hand side should be in agreement.

The above incorporates typical examples of type disagreements that count as type errors. A compiler should be able to report these errors.

The type analysis task’s final output is the collection of all type errors. More concretely, the output is a sequence of \ColorboxmygrayInlineOption<TypeError>, where \ColorboxmygrayInlineOption<TypeError> denoted the type \ColorboxmygrayInlineTypeError will a null value added and \ColorboxmygrayInlineTypeError is the type storing the information of a type error. The position of type errors agrees with the source tokens leading to these errors.

## 5 Expressive Power of Transformers as Efficient Compilers

In this section we discuss main theoretical results about the expressive power of transformers to perform compilation tasks: AST construction, symbol resolution, and type analysis.
In Section [5.4](#S5.SS4), we discuss Cybertron, a DSL specifically designed for our proof.

### 5.1 Abstract Syntax Tree Construction

We start with a definition that characterizes low-complexity codes.

###### Definition 1 (Codes with Bounded AST-Depth) .

Let $\operatorname{MiniHusky}_{D}$ be the set of token sequences that can be parsed into valid ASTs in Mini-Husky with a depth less than $D$.

$D$ in the above definition is small in practice, and a linear dependency on $D$ is acceptable, but the linear dependency on $L$ is not.
The fundamental reason is that *the clean code principle* (Martin, ) requires one to write code with as little nested layer as possible for greater readility. Readability is of the utmost importance because “Programs are meant to be read by humans and only incidentally for computers to execute” (Abelson et al., ). This assumption of bounded hierarchical depth is not limited to just programming languages, but is often seen as applicable to natural languages (Frank et al., ; Brennan & Hale, ; Ding et al., ), motivating Yao et al. () to have a similar boundedness assumption.
Below is the main result for AST construction using transformers.

###### Theorem 1 .

There exists a transformer encoder of model dimension and number of layers being $O(\log L+D)$ and number of heads being $O(1)$ that represents a function that maps any token sequence of length $L$ in $\operatorname{MiniHusky}_{D}$ to its abstract syntax tree represented as a sequence.

We note $\log L$ is small because a 64-bit computers can only process context length at most $2^{64}$ and $D$ is small by assumption. Therefore, there exists a transformer with an almost constant number of parameters that is able to process comparatively much longer context length.

###### Proof Sketch.

The idea is to construct ASTs in a bottom-up manner with full parallelism.
We shall recursively produce the final ASTs in at most $D$ steps.
We shall maintain two values, called \ColorboxmygrayInlinepre_asts and \ColorboxmygrayInlineasts. \ColorboxmygrayInlineasts represents ASTs that have already been allocated, although they might not been fully initialized. \ColorboxmygrayInlinepre_asts represents tokens that have yet to form ASTs and new ASTs that have not been fully initialized.
For each round, we try to create new ASTs from \ColorboxmygrayInlinepre_asts and update \ColorboxmygrayInlineasts and \ColorboxmygrayInlinepre_asts. For the $n$-th round, we provably allocated all ASTs with depth no more than $n$. Then for the $D$-th round, all ASTs are properly constructed and allocated.
Each round can be represented by a transformer of a number of heads $O(1)$, model dimension $O(\log L+D)$, and a number of layers $O(1)$.
Therefore, The end-to-end process is then representable by a transformer of the number of heads $O(1)$, model dimension $O(\log L+D)$ and the number of layers $O(\log L+D)$.
See full details in in Appendix [F](#A6).
∎

###### Definition 1 (Codes with Bounded AST-Depth) .

###### Theorem 1 .

###### Proof Sketch.

### 5.2 Symbol Resolution

Next, we show that transformers can effectively perform symbolic resolution as $\log L$ and $D$ are almost constant as compared with context length $L$.

###### Theorem 2 .

There exists a transformer encoder of model dimension and number of layers being $O(\log L+D)$ and number of heads being $O(1)$ that represents a function that maps any token sequence of length $L$ in $\operatorname{MiniHusky}_{D}$ to its symbol resolution represented as a sequence of values of type \ColorboxmygrayInlineOption<SymbolResolution>.

###### Proof Sketch.

First, we need to define the type for scopes. It is represented by a tiny sequence of indices of curly brace block AST that enclose the type/function/variable.
We assign the scope by walking through the ASTs in a top-down manner. We not only assign scopes to item definitions, we also:
(1) assign scopes to ASTs representing curly brace blocks, with these scopes equal to the scope of block itself, and
(2) assign scopes to identifiers waiting to be resolved, with these scopes equal to the maximum possible scope of its resolved definition.
The computation process is easily represented in Cybertron, indicating attention is expressive enough for this calculation and it only takes $O(D)$ number of layers.

After obtaining all the scopes for all items, it takes only one additional layer to obtain the symbolic resolution through attention. As attention is expressed through the dot product of two linear projections $Q$ and $K$, we have to choose the representation of the scope type properly to finish the proof. The full details are in Appendix [G](#A7).
∎

###### Theorem 2 .

###### Proof Sketch.

### 5.3 Type Analysis

We need an additional definition to characterize the complexity of codes for type analysis.

###### Definition 2 (Codes with Bounded AST-Depth and Type-Inference-Depth) .

We use $\operatorname{MiniHuskyAnnotated}_{D,H}$ to denote the subset of $\operatorname{MiniHusky}_{D}$ with the depth of type inference no more than $H$. The depth of type inference is the number of rounds of computation needed to infer all the types using the type-inference algorithm (described in Appendix [E.1](#A5.SS1)).

In practice, $H$ is significantly smaller than with context length $L$ for reasonably written code because it is upper bounded by the number of statements in a function body which is required to be small according to clean code principle (Martin, ).
Below, we present the main result of using transformers for type analysis. See full details in Appendix [H](#A8).

###### Theorem 3 .

For $L,D,H\in\mathbb{N}$, there exists a transformer encoder of model dimension, and number of layers being $O(\log L+D+H)$ and number of heads being $O(1)$ that represents a function that maps any token sequence of length $L$ in $\operatorname{MiniHuskyAnnotated}_{D,H}$ to its type errors represented as a sequence of values of type \ColorboxmygrayInlineOption<TypeError>.

###### Definition 2 (Codes with Bounded AST-Depth and Type-Inference-Depth) .

###### Theorem 3 .

### 5.4 Proof Vehicle: Cybertron , a Domain-Specific Language

Here we highlight our main proof technique.
Proving that transformers can express complex algorithms and software like compilers is a significant challenge due to the inherent differences between how transformers operate and the nature of high-level tasks they are expected to perform. Transformers process input at a low level, where each layer manipulates raw token sequences as vectors without predefined structure or meaning. However, high-level tasks—such as constructing ASTs
and performing type and symbol analysis—require handling complex, structured information that depends on long-range relationships and interactions across the input. Bridging the gap between this raw, unstructured processing and the structured, multi-step logic required for these tasks introduces significant difficulty. Compilers, for instance, typically rely on rule-based, step-by-step operations that are abstract and sequential, which transformers must simulate through their attention mechanisms and feedforward layers. The challenge is further compounded by the need to formally prove that transformers can handle such tasks efficiently and accurately, despite operating in a fundamentally different manner. To address these challenges, we propose a domain-specific language (DSL) called Cybertron, which allows us to *systematically prove* that transformers are capable of expressing complex algorithms while maintaining sufficient readability.

A key feature of Cybertron is its expressive type system, which provides strong correctness guarantees. The type system ensures that every value is strongly typed, making it easier to reason about function composition and ensuring the validity of our proofs. This type system is crucial for managing how transformers represent and manipulate both local and global types—where local types correspond to individual tokens and global types refer to sequences of tokens, encapsulating broader program information.

What transformers output (possibly in the intermediate layers) is a representation in sequences of vector of sequences of values in these types. As types are mathematically interpreted in this paper a discrete subset of a vector space, Cybertron allows us to construct transformers with an automatic value validity guarantees if the Cybertron code is type-correct.

In Cybertron, complex functions are broken down into “atomic” operations through propositions on function compositions and computation graphs (Propositions [11](#Thmproposition11),[13](#Thmproposition13),[14](#Thmproposition14),[2](#Thmproposition2)). It is straightforward to prove that these “atomic” operations are representable by transformers, either by feedforward layers or attention layers. For example:

- •
Feedforward layers: boolean operations like AND (Proposition [6](#Thmproposition6)), OR (Proposition [7](#Thmproposition7)), or NOT (Proposition [5](#Thmproposition5)), or operations over option types like \ColorboxmygrayInlineOption::or (Proposition [9](#Thmproposition9)) being applied to each token in a sequence.
- •
Attention layers: operations that requires information transmission between tokens such as \ColorboxmygrayInlinenearest_left and \ColorboxmygrayInlinenearest_right that collect for each token the nearest left/right non-nil information (Proposition [15](#Thmproposition15)).

This approach allows us to break down complex operations into primitive tasks that transformers can simulate. Feedforward layers handle local operations on individual tokens, while attention layers manage long-range dependencies and interactions between tokens, simulating the multi-step reasoning required for higher-level tasks.

Cybertron’s expressive type system and function composition framework help bridge the gap between the low-level processing transformers perform and the high-level reasoning necessary for complex tasks like compilation. For full details, including the mathematical foundations of Cybertron’s type system and function composition, see Appendix [D](#A4).

## 6 Comparisons between Transformers and RNN

Now we compare transformers and RNNs from both theoretical and empirical perspectives.

### 6.1 A Lower Bound for RNNs for Type Checking

Previously, it has shown that RNN is provably less parameter efficient than transformers for associate recall (Wen et al., ). Intuitively speaking, type checking step covers associate recall.
Based on this observation, we obtain the following lower bound for RNNs.

###### Theorem 4 .

For $L,D,H\in\mathbb{N}$, for any RNN that represents a function that maps any token sequence of length $L$ in $\operatorname{MiniHuskyAnnotated}_{D,H}$ with $D,H=O(1)$ to its type errors represented as a sequence of values of type \ColorboxmygrayInlineOption<TypeError>, then its state space size is at least $\Omega(L)$.

Theorem [3](#Thmtheorem3) and Theorem [4](#Thmtheorem4) give a clear separation between transformers and RNNs in terms of the compilation capability.
Specifically, if the input codes satisfy $D,H\ll L$, which typically the case under the clean code principle (Martin, ), then transformers at most need $O\left((\log L+D+H)\right)$ number of parameters, which is significantly smaller what RNNs requires, $\Omega(L)$.

###### Theorem 4 .

### 6.2 Empirical Comparison between Transformers and RNNs

We validate our theoretical results by conducting experiments on synthetic data.

Dataset construction.
The synthetic dataset is parameterized by $n$ (the number of data pieces), $f$ (the number of functions in a data piece), $d$ (the minimum distance between the declaration and the first call of a function, as well as the minimum distance between its consecutive calls), $v$ (the probability of using a variable in a function call), and $e$ (the error rate of using an incorrect type in a function call).

The names of the functions are drawn randomly from f$x$ where $x\in\{0,1,\ldots,99\}$.
For each function, there is only one argument whose symbol is randomly drawn from $\{$a, b, …, z$\}$ and whose type is randomly drawn from $\{$Int, Float, Bool$\}$.
There are at most $5$ function calls in a function, and those called functions must be declared and not called by at least $d$ functions ahead of the current one.
In each function call, with probability $v$, the argument variable of the enclosing function is used regardless of its type, with probability $(1-v)(1-e)$, a literal of the correct type is used, and with probability $(1-v)e$ an incorrect type literal is used.
For integers, the literals are from $\{0,1,\ldots,99\}$; for floats, the literals are from $\{0.1,1.1,\ldots,99.1\}$; for booleans, the literals are from $\{$true, false$\}$.

Below is a data piece with $f=10,d=3,v=0.2,e=0.5$:

Model and training.
We use customized BERT models (Devlin et al., ) and bidirectional RNN models (Schuster & Paliwal, ) in our experiments. To control the model size (i.e., the number of trainable parameters), we adjust only the hidden sizes while keeping other hyperparameters constant. Detailed model specifications can be found in Table [2](#A10.T2). For both transformers and RNNs, we use the hyperparameters listed in Table [2](#A10.T2) in Appendix during the training process.

Results.
We experimented with multiple combinations of models (Table [2](#A10.T2)) and datasets (Table [2](#A10.T2)).
For each combination, we conducted independent runs using a fixed set of $k=5$ random seeds.
When plotting the figures, we took the top $t=5$ evaluation losses/accuracies from each run and averaged over all the $k\times t$ values.
We plotted separate figures for each dataset and separate sub-figures for each metric.
In each sub-figure, the $x$-axis represents the number of trainable parameters, and the $y$-axis represents the averaged values.
Results are shown in Figure [2](#S6.F2).
They demonstrate that customized BERT models are able to perform better at type checking than bidirectional RNN models when both sizes scale up, corroborating our theories.
Other results are in Appendix [J](#A10).

Figure: Figure 2: Figures depicting the evaluation accuracy of the expected type (see Section [5.3](#S5.SS3)) across different models, measured by their number of trainable parameters, when trained on various datasets. The first $8$ points of each model in each experiment are not aligned with the $x$-axis because the number of trainable parameters scales with hidden sizes differently for different models.
Refer to caption: /html/2410.14706/assets/x1.png

## 7 Conclusion

We demonstrated that transformers can efficiently handle syntactic and semantic analysis in C-like languages, using Cybertron to prove their capacity for tasks like AST generation, symbol resolution, and type analysis. We show a theoretical advantage of transformers over RNNs, particularly in their ability to manage long-range dependencies with logarithmic parameter scaling. In a sense, transformers have the right inductive bias for language tasks. Our experiments confirmed these theoretical insights, showing strong performance on synthetic and real datasets, underscoring the expressiveness and efficiency of transformers in sequence-based learning.

## Appendix A Tree

Trees are one of the most fundamental objects to study in computer science. However, its exact definition differs for different domains. The trees used in “abstract syntax tree” (Section [B](#A2)) is more restrictive than that in mathematics, which we call “typed tree”, so that one can define recursive computation more rigorously.

### A.1 What are Trees

Trees in data structures have slightly additional meaning as compared to trees in mathematics. In this paper, all trees are trees in data structures. For clarity, we lay down the precise definition of trees in data structure.

###### Definition 3 (Tree) .

A tree $T$ is a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following:

- •
If $T$ is not empty, it has a special node called the root that has no parent.
- •
Each node $v$ of $T$ other than the root has a unique parent node $w$; each node with parent $w$ is a child of $w$.

We denote the nodes of $T$ as $\operatorname{N}(T)$.

###### Definition 4 (Recursive Definition of a Tree) .

A tree $T$ is either empty or consists of a node $r$ (the root) and a possibly empty set of trees whose roots are the children of $r$.

However, the above definition is too permissive. We shall define a typed version as follows:

###### Definition 5 (Typed Tree) .

A tree type consists of a set of values $V$ and a set of relationships $C\subseteq V\times\mathbb{N}$, and a typed tree under this type is any tree $T$ such that for each node, a value $v\in V$ is assigned such that $(v,n)\in C$ where $n$ is the number of the children of the node.

All trees in this paper are typed.

###### Example 1 (Abstract syntax tree (AST) as Typed Tree) .

Consider an AST for a simple arithmetic expression. Let the set of values $V$ be:

$$ ${{{{{V=\{{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{num}}}}}}},{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{add}}}}}}},{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{sub}}}}}}},{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{mul}}}}}}},{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{div}}}}}}}\}$ $$

and the set of relationships $C\subseteq V\times\mathbb{N}$ specify the allowed number of children for each value:

$$ ${{{{{C=\{({\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{num}}}}}}},0),({\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{add}}}}}}},2),({\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{sub}}}}}}},2),({\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{mul}}}}}}},2),({\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{div}}}}}}},2)\}$ $$

An example AST for the arithmetic expression $(3+5)\times 2$ is the following typed tree:

- •
The root node is labeled \ColorboxmygrayInlinemul (multiplication), and it has two children.
–
The left child is labeled \ColorboxmygrayInlineadd (addition), and it has two children:
*
The left child of \ColorboxmygrayInlineadd is labeled \ColorboxmygrayInlinenum with the value 3.
*
The right child of \ColorboxmygrayInlineadd is labeled \ColorboxmygrayInlinenum with the value 5.
–
The right child of \ColorboxmygrayInlinemul is labeled \ColorboxmygrayInlinenum with the value 2.

This tree conforms to the typing rules because:

- •
\Colorbox
mygrayInlinenum has 0 children,
- •
\Colorbox
mygrayInlineadd has 2 children,
- •
\Colorbox
mygrayInlinemul has 2 children,

all of which satisfy the relationships in $C$.

###### Definition 3 (Tree) .

###### Definition 4 (Recursive Definition of a Tree) .

###### Definition 5 (Typed Tree) .

###### Example 1 (Abstract syntax tree (AST) as Typed Tree) .

### A.2 Representations of Trees

It’s also important to talk about tree representations. We are studying transformers, and then it’s necessary to represent large trees as a sequence, otherwise the model dimension is not large enough to contain the information locally. Let’s first talk about the classical arena pattern used in system programming for representing trees and we shall slightly adapt it to our use case for studying transformers.

##### Arena Pattern.

To represent trees efficiently in memory, especially when trees are frequently modified (such as insertions or deletions of nodes), an arena pattern is often used. The arena pattern provides a way to manage memory allocation for tree structures, allowing for efficient memory usage and avoiding fragmentation. Here’s how the arena pattern works in the context of tree representation:

###### Definition 6 (Arena Pattern in Tree Representation) .

In the arena pattern, a tree is represented by an array (or vector) of nodes, called an arena. Each node in the arena contains:

- •
An element or value stored in the node.
- •
References (often indices or pointers) to the node’s children and possibly to its parent.

The key characteristics of the arena pattern are:

- •
Memory Contiguity: All nodes are stored contiguously in memory within the arena, which allows for efficient traversal and modification operations.
- •
Fixed Capacity: The arena has a fixed or dynamically resizable capacity, and nodes are added sequentially. This avoids the overhead of allocating individual nodes on the heap.
- •
Index-based References: Instead of using pointers, the nodes reference each other using indices within the array, which simplifies memory management and can lead to cache-friendly operations.
- •
Efficient Allocation and Deallocation: Nodes can be efficiently allocated and deallocated within the arena without requiring complex memory management techniques like garbage collection or reference counting.

The arena pattern is particularly useful in scenarios where the structure of the tree is highly dynamic or when performance is critical. It allows for a simple and efficient way to manage and traverse trees without the typical overhead associated with more traditional pointer-based tree representations.

###### Definition 6 (Arena Pattern in Tree Representation) .

##### Adaptations for Transformers

For transformers, inputs, intermediate values and outputs are all sequences. So the trees are represented as sequences of nodes with node reference representable by token position encoding. Based on the representation, transformers will be able to perform various kinds of recursive tree operations, as we shall see.

## Appendix B Context Free Grammar

In this section, we lay down the well-known definitions of context free grammar, derivations, and parse trees.
To define an abstract syntax tree (AST), one commonly resorts to generation rules, such as context-free grammars (CFG) (Alfred et al., ) and parsing expression grammars (PEG) (Ford, ).
In most cases, just generation rules themselves are not sufficient to define properly a language. Many practical languages like C and C++ cannot be solely described by these rules (David, ) so that they can reuse the limited set of special characters on the keyboard. Furthermore, semantic constraints like type correctness are intrinsically contextual and cannot be expressed through CFG or similar rules. However, CFG or other rules provide a valuable construct, the AST. With an AST, one can refine the language definition by putting restrictions on the syntax tree through tree operations. Effectively, a language can be seen as a subset of trees, not as a subset of strings. Semantic analysis like symbol resolution and type checking can be described effectively based on trees. In short, CFG standalone is hardly practical but it provides a useful and clear foundation to build definitions upon.

A context-free grammar (CFG) is defined as a 4-tuple $G=(V,\Sigma,R,S)$, where:

- •
$V$ is a finite set of variables (non-terminal symbols).
- •
$\Sigma$ is a finite set of terminal symbols, disjoint from $V$. Sequences of $\Sigma$, i.e., elements of $\Sigma^{*}$ are called (literal) strings.
- •
$R\subset V\times(V\cup\Sigma)^{*}$ is a finite set of production rules, where each rule is of the form $A\rightarrow\alpha$, with $A\in V$ and $\alpha\in(V\cup\Sigma)^{*}$.
- •
$S\in V$ is the start symbol.

Given a context-free grammar $G=(V,\Sigma,R,S)$, we define derivation as follows:

- •
A derivation is a sequence of steps where, starting from the start symbol $S$, each step replaces a non-terminal with the right-hand side of a production rule.
- •
Formally, we write $u\Rightarrow v$ if $u=\alpha A\beta$ and $v=\alpha\gamma\beta$ for some production $A\rightarrow\gamma$ in $R$, where $\alpha,\beta\in(V\cup\Sigma)^{*}$ and $A\in V$.
- •
A leftmost derivation is a derivation in which, at each step, the leftmost non-terminal is replaced.
- •
A rightmost derivation is a derivation in which, at each step, the rightmost non-terminal is replaced.
- •
We denote a derivation sequence as $S\Rightarrow^{*}w$, where $w\in\Sigma^{*}$ is a string derived from $S$ in zero or more steps.

A parse tree (or syntax tree) for a context-free grammar $G=(V,\Sigma,R,S)$ is a tree that satisfies the following conditions:

- •
The root of the tree is labeled with the start symbol $S$.
- •
Each leaf of the tree is labeled with a terminal symbol from $\Sigma$ or the empty string $\epsilon$.
- •
Each internal node of the tree is labeled with a non-terminal symbol from $V$.
- •
If an internal node is labeled with a non-terminal $A$ and has children labeled with $X_{1},X_{2},\dots,X_{n}$, then there is a production rule $A\rightarrow X_{1}X_{2}\dots X_{n}$ in $R$.
- •
The yield of the parse tree, which is the concatenation of the labels of the leaves (in left-to-right order), forms a string in $\Sigma^{*}$ that is derived from the start symbol $S$.

## Appendix C Neural Architectures

In this section, we lay down the precise mathematical definitions of neural architectures we are going to use in our proof.

###### Definition 7 (Single-Layer Fully Connected Network with $4\times$ Intermediate Space) .

Given model dimension $d_{\text{model}}$, a single-layer feed-forward network with an intermediate space expanded to $4$ times the input dimension is a function from $\mathbb{R}^{d_{\text{model}}}$ to $\mathbb{R}^{d_{\text{model}}}$, denoted by ${f_{\text{fcn}}}$ and defined as follows:

given $X\in\mathbb{R}^{d_{\text{model}}}$, weights $W_{1}\in\mathbb{R}^{4d_{\text{model}}\times d_{\text{model}}}$, $W_{2}\in\mathbb{R}^{d_{\text{model}}\times 4d_{\text{model}}}$, and biases $B_{1}\in\mathbb{R}^{4d_{\text{model}}}$, $B_{2}\in\mathbb{R}^{d_{\text{model}}}$, the output ${f_{\text{fcn}}}(X)$ is computed as:

$$ ${f_{\text{fcn}}}(X)=W_{2}{\sigma_{\operatorname{ReLU}}}(W_{1}X+B_{1})+B_{2},$ $$

where ${\sigma_{\operatorname{ReLU}}}:\mathbb{R}^{4d_{\text{model}}}\rightarrow\mathbb{R}^{4d_{\text{model}}}$ is the Rectified Linear Unit activation function applied element-wise, defined by:

$$ ${\sigma_{\operatorname{ReLU}}}(z)={\left(\max(z_{1},0),\max(z_{2},0),\dots,\max(z_{4d_{\text{model}}},0)\right)}^{\top},$ $$

for $z=(z_{1},z_{2},\dots,z_{4d_{\text{model}}})^{\top}\in\mathbb{R}^{4d_{\text{model}}}$.

The choice of a $4\times$ intermediate space is common in practice, often used in Transformer architectures. Interestingly, this empirical choice turns out to have a useful theoretical property: it allows the network to express any affine transformation, as we’ll see in the following proposition.

###### Proposition 1 .

A single-layer fully connected network with a $4\times$ intermediate space, as defined previously, can express any affine map from $\mathbb{R}^{d_{\text{model}}}$ to $\mathbb{R}^{d_{\text{model}}}$.

###### Proof.

Let $f:\mathbb{R}^{d_{\text{model}}}\to\mathbb{R}^{d_{\text{model}}}$ be any affine map given by $f(X)=AX+b$, where $A\in\mathbb{R}^{d_{\text{model}}\times d_{\text{model}}}$ and $b\in\mathbb{R}^{d_{\text{model}}}$. We will construct weights $W_{1}\in\mathbb{R}^{4d_{\text{model}}\times d_{\text{model}}}$, $W_{2}\in\mathbb{R}^{d_{\text{model}}\times 4d_{\text{model}}}$ and biases $B_{1}\in\mathbb{R}^{4d_{\text{model}}}$, $B_{2}\in\mathbb{R}^{d_{\text{model}}}$ such that ${f_{\text{fcn}}}(X)=f(X)$ for all $X\in\mathbb{R}^{d_{\text{model}}}$.

Define:

$$ $W_{1}=\begin{pmatrix}I_{d_{\text{model}}}\\ -I_{d_{\text{model}}}\\ 0\\ 0\end{pmatrix},\quad B_{1}=0\in\mathbb{R}^{4d_{\text{model}}},$ $$

where $I_{d_{\text{model}}}$ is the $d_{\text{model}}\times d_{\text{model}}$ identity matrix, and 0 0 represents zero matrices of appropriate dimensions. Set:

$$ $W_{2}=\left(A\quad-A\quad 0\quad 0\right),\quad B_{2}=b.$ $$

For any $X\in\mathbb{R}^{d_{\text{model}}}$, compute:

$$ $\displaystyle{f_{\text{fcn}}}(X)$ $\displaystyle=W_{2}\,{\sigma_{\operatorname{ReLU}}}(W_{1}X+B_{1})+B_{2}$ $\displaystyle=\left(A\quad-A\quad 0\quad 0\right)\,{\sigma_{\operatorname{ReLU}}}\left(\begin{pmatrix}X\\ -X\\ 0\\ 0\end{pmatrix}\right)+b$ $\displaystyle=\left(A\quad-A\quad 0\quad 0\right)\begin{pmatrix}{\sigma_{\operatorname{ReLU}}\left(X\right)}\\ {\sigma_{\operatorname{ReLU}}\left(-X\right)}\\ 0\\ 0\end{pmatrix}+b$ $\displaystyle=A\,{\sigma_{\operatorname{ReLU}}\left(X\right)}-A\,{\sigma_{\operatorname{ReLU}}\left(-X\right)}+b.$ $$

Note that ${\sigma_{\operatorname{ReLU}}\left(X\right)}-{\sigma_{\operatorname{ReLU}}\left(-X\right)}=X$, we have:

$$ ${f_{\text{fcn}}}(X)=AX+b=f(X).$ $$

Therefore, the network can represent any affine map from $\mathbb{R}^{d_{\text{model}}}$ to $\mathbb{R}^{d_{\text{model}}}$.
∎

###### Definition 8 (Single-Layer Feed Forward Network with $4\times$ Intermediate Space) .

Given model dimension $d_{\text{model}}$ and position set $\operatorname{Pos}$, the Transformer Feed Forward Network is a function $f_{\text{ffn}}:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\rightarrow\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$ defined as follows:

For an input $X\in\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$, the output $f_{\text{ffn}}(X)$ is computed by applying the single-layer feed-forward network ${f_{\text{fcn}}}$ (as defined previously) independently to each position:

$$ $f_{\text{ffn}}(X)_{p}={f_{\text{fcn}}}(X_{p})\quad\forall p\in\operatorname{Pos}$ $$

where $X_{p}\in\mathbb{R}^{d_{\text{model}}}$ is the $p$-th row of $X$, corresponding to the $p$-th position in the input sequence.

Next, we define the attention mechanism, which is a key component of the Transformer architecture. This definition presents a hard attention layer with a simplified position encoding. We use hard attention here for theoretical simplicity, as it represents a discrete limit of the more commonly used soft attention mechanism. Hard attention forces the model to make a clear choice about which inputs to focus on, which can simplify analysis and provide clearer insights into the model’s behavior. It can be viewed as the limiting case of soft attention as the temperature approaches zero, where the softmax operation becomes increasingly peaked and eventually converges to a one-hot vector.

###### Definition 9 (Hard Attention Layer with Simplified Position Encoding) .

Given model dimension $d_{\text{model}}$, number of heads $H$, and number of layers $L$, a transformer with simplified position encoding and hard attention is defined to be a function $f_{\text{attn}}:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\rightarrow\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$ defined by

$$ $\forall p\in\operatorname{Pos},{f_{\text{attn}}(X)}_{p}:=W_{O}\text{Concat}\left({\text{Attn}^{(1)}(X)}_{p},\ldots,{\text{Attn}^{(H)}(X)}_{p}\right),$ (4) $$

where the $h$th attention head uses hard attention, defined as:

$$ ${\text{Attn}^{(h)}(X)}_{p}:=\frac{1}{|S_{p}|}\sum_{p^{\prime}\in S_{p}}V^{(h)}_{p^{\prime}},$ (5) $$

where

- •
$W_{O}\in\mathbb{R}^{d_{\text{model}}\times d_{\text{model}}}$ are trainable parameters;
- •
$S_{p}=\operatorname*{arg\,max}_{p^{\prime}\in\operatorname{Pos}}\left({Q^{(h)}_{p}}^{\top}K^{(h)}_{p^{\prime}}+\lambda^{(h)\top}\Psi_{p^{\prime}-p}\right)$ with $Q_{p}^{(h)},K_{p}^{(h)},V_{p}^{(h)},\lambda^{(h)},\Psi_{q}$ defined by
–
$Q_{p}^{(h)}=W_{Q}^{(h)}X_{p},K_{p}^{(h)}=W_{K}^{(h)}X_{p}$ are vectors of dimension $d_{\text{model}}/H$, with trainable parameters $W_{Q}^{(h)},W_{K}^{(h)}\in\mathbb{R}^{(d_{\text{model}}/H)\times d_{\text{model}}}$;
–
$V_{p}^{(h)}=W_{V}^{(h)}X_{p}$ are vectors of dimension $d_{\text{model}}/H$, linear transformations of $X_{p}$ with trainable parameters $W_{V}^{(h)}\in\mathbb{R}^{(d_{\text{model}}/H)\times d_{\text{model}}}$;
–
$\lambda^{(h)}\in\mathbb{R}^{2}$ are constants depending only on head count $h$;
–
$\Psi_{q}\in\mathbb{R}^{2}$ are 2-dimensional vectors depending on relative position $q$ but not on head count $h$. It is explicitly defined as
$\Psi_{q}=\begin{pmatrix}q\\
1_{q>0}\end{pmatrix}.$
(6)
This formulation allows for both past and future masking.

Having defined the basic components, we can now proceed to describe the full Transformer architecture. This definition builds upon the previously introduced concepts, incorporating them into a complete model structure.

###### Definition 10 (Transformer) .

A Transformer is a function $f_{\text{tf}}:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\rightarrow\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$ that maps an input sequence to an output sequence through a series of layers, each consisting of a multi-head attention mechanism and a position-wise feed-forward network (MLP).

Given:

- •
Input sequence $X\in\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$, where $\operatorname{Pos}$ is the set of positions and $d_{\text{model}}$ is the model dimension.
- •
Number of layers $L$.
- •
Number of attention heads $H$.

The Transformer computes the output $Y=X^{(L)}$ through recursive application of attention and feed-forward layers:

- •
Initialization is given by:
$X^{(0)}=X.$
- •
For each layer $l=1,2,\dots,L$:
–
Compute attention output:
$\hat{X}^{(l)}=X^{(l-1)}+f_{\text{attn}}^{(l)}\left(X^{(l-1)}\right)$
–
Compute feed-forward output:
$X^{(l)}=\hat{X}^{(l)}+f_{\text{ffn}}^{(l)}\left(\hat{X}^{(l)}\right)$

Here:

- •
$f_{\text{attn}}^{(l)}$ are hard attention layers with simplified position encoding as previously defined. It operates on $X^{(l-1)}$ and produces an output in $\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$.
- •
$f_{\text{ffn}}^{(l)}$ are feed-forward networks with $4\times$ intermediate space as previously defined. It operates position-wise on $\hat{X}^{(l)}$ and produces an output in $\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$.

###### Remark 1 .

For simplicity, we have omitted the Layer Normalization component typically present in Transformer architectures. This simplification allows us to focus on the core attention and feed-forward mechanisms while maintaining the essential structure of the Transformer.

We use ${\operatorname{Tf}^{d_{\text{model}}}_{H,L}}$ to denote the set of transformers of model size $d_{\text{model}}$, number of heads $H$ and number of layers $L$ as functions from $\mathbb{R}^{d_{\text{model}}*}$ to $\mathbb{R}^{d_{\text{model}}*}$.

For purpose of proof, we shall also need residual multi-layer perceptron. Functions over local types are first represented by multi-layer perception, then by Proposition [2](#Thmproposition2) applications of these functions over sequences can be representable by transformers. Residual multi-layer perceptron can be assembled through composition or computer graph, as we shall see.

Here’s the definition of a residual MLP Network.

###### Definition 11 (Residual Multi-Layer Perceptron) .

A *Residual Multi-Layer Perceptron* (ResMLP) is a function $f_{\text{resmlp}}:\mathbb{R}^{d_{\text{model}}}\to\mathbb{R}^{d_{\text{model}}}$ defined recursively by

$$ $X^{(0)}=X,\quad X^{(l)}=X^{(l-1)}+{f_{\text{fcn}}}\left(X^{(l-1)}\right),\quad l=1,2,\dots,L,f_{\text{resmlp}}(X)=X^{(L)}$ $$

where $X\in\mathbb{R}^{d_{\text{model}}}$ is the input vector, $L$ is the total number of layers, and ${f_{\text{fcn}}}:\mathbb{R}^{d_{\text{model}}}\to\mathbb{R}^{d_{\text{model}}}$ is the *Single-Layer Fully Connected Network with $4\times$ Intermediate Space* as previously defined in Definition [1](#Thmproposition1).

We use ${\operatorname{ResMlp}^{d_{\text{model}}}_{L}}\subset{\mathbb{R}^{d_{\text{model}}}}^{\mathbb{R}^{d_{\text{model}}}}$ to represent the set of residual MLPs with dimension $d_{\text{model}}$ and $L$ layers, as defined in Definition [11](#Thmdefinition11).

The following proposition is quite basic. It demonstrates that any function representable by a ResMLP can be applied position-wise by a Transformer.

###### Proposition 2 (Position-wise ResMLP Application is Representable by Transformers) .

Let $f:\mathbb{R}^{d_{\text{model}}}\to\mathbb{R}^{d_{\text{model}}}$ be a function representable by a Residual Multi-Layer Perceptron (ResMLP) as defined in Definition [11](#Thmdefinition11). Then the function $F:\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}\to\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$, defined by applying $f$ position-wise,

$$ $F(X)_{p}=f(X_{p}),\quad\forall p\in\operatorname{Pos},$ $$

is representable by a Transformer as defined in Definition [10](#Thmdefinition10).

###### Proof.

Since $f$ is representable by a ResMLP with $L$ layers, it is defined recursively by

$$ $X^{(0)}=X,\quad X^{(l)}=X^{(l-1)}+{f_{\text{fcn}}}\left(X^{(l-1)}\right)\text{ for }l=1,\dots,L,$ $$

and

$$ $f(X)=X^{(L)},$ $$

where ${f_{\text{fcn}}}:\mathbb{R}^{d_{\text{model}}}\to\mathbb{R}^{d_{\text{model}}}$ is the Single-Layer Fully Connected Network with $4\times$ intermediate space (Definition [1](#Thmproposition1)).

We construct a Transformer with $L$ layers such that, for any input sequence $X\in\mathbb{R}^{\operatorname{Pos}\times d_{\text{model}}}$, the output $Y=f_{\text{tf}}(X)$ satisfies $Y_{p}=f(X_{p})$ for all $p\in\operatorname{Pos}$.

To achieve this, we configure the Transformer so that the attention mechanism outputs zero at each layer. This can be done by setting the attention weights to zero, ensuring $f_{\text{attn}}(X^{(l-1)})=0$. Consequently, the update equations simplify to

$$ $\hat{X}^{(l)}=X^{(l-1)}.$ $$

We then set the feed-forward network $f_{\text{ffn}}$ in the Transformer to have the same weights and biases as ${f_{\text{fcn}}}$ in the ResMLP. The Transformer layer update becomes

$$ $X^{(l)}=\hat{X}^{(l)}+f_{\text{ffn}}\left(\hat{X}^{(l)}\right)=X^{(l-1)}+\left({f_{\text{fcn}}}\left(X^{(l-1)}_{p}\right)\right)_{p\in\operatorname{Pos}}.$ $$

This recursion matches that of the ResMLP applied position-wise to $X$. Therefore, after $L$ layers, the Transformer output satisfies ${f_{\text{tf}}(X)}_{p}=f(X_{p})$ for all $p\in\operatorname{Pos}$.

∎

###### Definition 7 (Single-Layer Fully Connected Network with 4 × 4\times Intermediate Space) .

###### Proposition 1 .

###### Proof.

###### Definition 8 (Single-Layer Feed Forward Network with 4 × 4\times Intermediate Space) .

###### Definition 9 (Hard Attention Layer with Simplified Position Encoding) .

###### Definition 10 (Transformer) .

###### Remark 1 .

###### Definition 11 (Residual Multi-Layer Perceptron) .

###### Proposition 2 (Position-wise ResMLP Application is Representable by Transformers) .

###### Proof.

## Appendix D Cybertron

### D.1 Introduction

It’s often difficult to directly prove that transformers or in general other low level forms of computation can express complicated algorithms and even complex software. There are way too many details as compared with typical mathematical proofs in machine learning theory. Hence, we propose the domain specific language Cybertron, where we can systematically prove transformers can express complicated algorithms and complex software with sufficient readability.

(Note: Cybertron is fundamentally different from Mini-Husky! Mini-Husky is the target language that we want transformers to analyze yet Cybertron is the domain specific language we use to prove that transformers can do that.)

RASP (Weiss et al., ) is quite close to Cybertron in terms of its design purpose. However, Cybertron is more powerful with advanced algebraic type system, global and local function constructions, etc. These additional mechanisms replace a significant part of the chore in proofs with automatic type checking. Thus, using Cybertron one can argue more complicated operations to be simulated by transformers rather than just simple algorithms.

In the broader perspective of computer science, it’s common to use code to prove things. In fact, in the formal verification community, mathematical proofs are viewed as a special case of a much larger universe of possible proof systems (mathlib Community, ; Massot, ) and constructive proof using code (Harrison et al., ; Farooqui, ; Jung et al., ) is far more applicable with great soundness to the most general settings. In our case, our code doesn’t serve as the whole proof but as an important part that contains most of the chores. However, it’s totally possible to build a full-fledged formalized proof, despite it might be too costly for a single paper to do.

Essentially, Cybertron works as follows:

- 1.
one builds complicated functions from the composition of smaller functions. We have lemmas that prove that the composed functions are representable by certain architecture given that smaller functions are representable.
- 2.
there is an algebraic type system and every value is strongly typed and immutable, making it highly readable and easy to reason about;
- 3.
there is a distinction between global and local types/functions. Local types are those information hovered over a single token, and global types are sequences of local types, i.e., the collection of information over the whole token stream. One can define a global function by mapping a local function.
- 4.
there are many functions that is defined externally, requiring external explanation that they can be represented by transformers.

It’s implemented as a subset of the Rust programming language that can be understood as computation graphs over sequences. It can be executed for testing purposes and we’ve tested our implementation for a range of inputs and validated its correctness.

### D.2 Philosophy: Sequential Representation of Everything

Before going through the full details, let’s first talk about the fundamental philosophy behind transformer and Cybertron.

One of the fundamental reasons transformers can be easily adapted across multiple modalities, including NLP and CV, is their sequence-to-sequence operation. Everything can be represented as an arbitrary-length sequence. Texts are sequences of words, images are sequences of image patches, videos are sequences of spacetime patches (OpenAI, ), and even graphs with sparse spatial structures can be represented as sequences of indexed nodes with additional information like parent node indices. Since inputs of various modalities can be cast into vector sequences, transformers can be applied to different domains without modifications to their architecture (Dosovitskiy et al., ).

Interestingly, this sequence-based thinking is not new. We’ve actually been representing everything as sequences since the very early days of computer science. This has been the foundation of how data is stored and processed in computers. However, sequence representations were traditionally viewed as low-level and sometimes inefficient for practical use, prompting the development of higher-level abstractions for programming. The rise of transformers, with their scalable learning capabilities, encourages us to reconsider the significance of sequence-based representations.

From a systems perspective, viewing everything as a sequence is the foundational approach in computer science. Data in a computer is stored as a continuous stream of bits. Whether it’s text, images, videos, or graphs, this data is represented in computer memory as an ordered sequence of bits. This aligns with how transformers handle different types of input by transforming them into sequences of vectors. Thus, the sequence-based operation of transformers mirrors the sequence-based representation of data in computer memory.

In essence, if a data structure can be represented in computer memory using $N$ bits, it can be processed as a sequence of bits of length $N$. This natural sequence representation in memory is consistent with how transformers process data, which makes them particularly flexible across different modalities. For example, recent state-of-the-art approaches Wu et al. () show that transformers can even be trained directly on raw bits of data, further emphasizing this connection.

Moreover, this sequence-based viewpoint offers fresh insights when applied to the domain of programming, particularly in areas such as code generation and analysis. With tools like ChatGPT and Copilot being widely used by developers, the impact of transformers on programming workflows is growing. Understanding the complexity of algorithms and programs expressed in sequence form becomes an interesting area of study, as it reveals new possibilities for how we approach computation.

In comparison to traditional systems like CPUs and human cognition, transformers are highly parallel but shallow in their operation. A transformer processes data in a fixed number of layers, while a CPU executes $10^{9}$ cycles per second, and humans may take days to process information like reading a book. Transformers, therefore, represent a fundamentally different computational model that is worth studying further in the context of sequence-based operations.

###### Example 2 .

Image to Sequence:
In computer memory, an image is typically stored as a continuous block of pixel values, often in row-major order, where each pixel’s value is encoded as bits in a sequence. When a transformer processes an image, it divides the image into patches (e.g., $16\times 16$ pixels), and each patch is flattened into a vector of pixel values. This creates a sequence of patches, where each patch corresponds to a vector. The way transformers represent these patches as a sequence closely aligns with how the image data is sequentially stored in computer memory.

###### Example 3 .

Video to Sequence:
A video is stored in computer memory as a sequence of frames, where each frame is essentially an image. In a similar manner to images, these frames are stored as continuous pixel values. Transformers process videos by dividing the frames into spacetime patches, where each patch captures a small region of space over a short segment of time. These spacetime patches are flattened and arranged into a sequence for the transformer to process. The sequential ordering of these patches matches how video frames and pixel data are stored in computer memory.

###### Example 4 .

Graph to Sequence:
In computer memory, a graph is typically stored using an adjacency list or adjacency matrix, where nodes and their connections (edges) are stored sequentially in a data structure. Transformers process graphs by representing each node and its features as a vector, and then creating a sequence of these vectors. The sequence may also encode additional information, such as the parent-child relationships between nodes. This sequence-based representation of graphs is consistent with how graph data is stored in memory, where nodes and edges are arranged in a structured order.

###### Example 5 .

Text to Sequence:
Text is naturally stored in computer memory as a sequence of characters or words, where each character is encoded as a sequence of bits (such as ASCII or Unicode values). When transformers process text, they convert each word into a word embedding, which is a vector of real numbers. The sequence of word embeddings corresponds to the sequence of characters or words stored in memory. This natural sequential representation of text in both memory and transformers ensures efficient handling of linguistic data.

###### Example 6 .

AST (Abstract Syntax Tree) to Sequence:
In computer memory, an abstract syntax tree (AST) is typically stored as a tree-like structure, where each node represents a component of the program (e.g., operators, variables, or statements). However, this tree can be linearized into a sequence by traversing it in a specific order (e.g., pre-order traversal). When transformers process an AST, they convert it into a sequence of tokens, where each token corresponds to a node in the tree. This sequential representation of the tree in transformers mirrors how the tree is stored as nodes and edges in memory, and how it can be flattened into a linear sequence.

In conclusion, the sequence-based representation in transformers is not just a novel approach for deep learning but is deeply rooted in how data has been stored and processed in computer memory since the early days of computing. This consistency between how data is stored in memory and how transformers process data as sequences is a key factor in their adaptability across different domains.

###### Example 2 .

###### Example 3 .

###### Example 4 .

###### Example 5 .

###### Example 6 .

### D.3 Local and Global Types

Now we define the type foundation of Cybertron.

Types are fundamental objects for programming language theory. Here we use types to faciliate our proofs. Type signatures contain rich information that help guarantee correctness of the program.
Here, we choose a mathematical definition of types that is most convenient for the discussion in this paper. We introduce the notion of “local type”. Roughly speaking, they are types without heap allocation and intended to be represented with $\mathbb{R}^{d_{\text{model}}}$ over a single token. For more complicated heap-allocated data structures like trees, graphs, etc., we shall represent them by sequences of these “local type”s, which translates directly to vector sequences for transformers.

###### Definition 12 (Local Type) .

Given a base space $B$ with at least two elements and a countably infinite identification space $\Psi$, a local type $\mathcal{T}$ over $B$ is a finite set $S$ together with an embedding $\phi$ from $S$ to $B^{d}$ and some fixed $d\in\mathbb{N}$ and an identification $\psi\in\Psi$.

For convenience, define ${\mathop{\text{Set}}\left(\mathcal{T}\right)}=S$, $d_{\mathcal{T}}=d$ and $\phi_{\mathcal{T}}=\phi$ and $\psi_{\mathcal{T}}=\psi$. And let $0_{B}$, and $1_{B}$ be two different elements of $B$. And $B^{0}:={\left\{0_{B}\right\}}$ so that ${\left|B^{i}\right|}={\left|B\right|}^{i}$ holds for all $i\in\mathbb{N}$.

###### Remark 2 .

We need $B$ to be at least size $2$, so that $B^{d}$ can be as large as we want for $d$ large enough.For typical computer representation, we can take $B$ to be $\mathbf{2}=\{0,1\}$. For transformers or neural networks in general, we can take $B$ to be $\mathbb{R}$ if we ignore precision. If we dont’ ignore precision, $B$ should be some finite set of floating point numbers. Thus, we shall keep the generality of $B$ throughout our discussion as all of these settings are important.

###### Remark 3 .

The role of identification $\psi_{\mathcal{T}}\in\Psi$ is to make two types mathematically different even if they have the same underlying set, encoding dimension, and encoding. Basically we are establishing a specialized type of theory tailored towards the expressive power of transformers upon a foundation of intuitive set theory.

###### Example 7 (Finite Set) .

In mathematics, we have the finite set denoted by $[n]={\left\{0,1,\ldots,n-1\right\}}$. Here we use a slightly different notation for a type with underlying set ${\left\llbracket{n}\right\rrbracket}$ and some encoding.

###### Example 8 (Position Encoding) .

Position encoding can be viewed as the encoding of a type denoted by ${\mathop{\text{Pos}}\left({n}\right)}$ with the underlying set being $[n]$ where $n$ is the context length. Although it has the same underlying set as type ${\left\llbracket{n}\right\rrbracket}$, it is a different type for a different purpose and might have different encoding.

If $B$ is $\mathbb{R}$, then the position encoding can be understood as the encoding of type ${\left\llbracket{L}\right\rrbracket}$ where $L$ is the context length. More explicitly, we have

$$ $\phi(x)=(e^{\mathbbm{i}L^{-i/d}x})_{i\in[d/2]},$ (7) $$

viewed as a $d$ dimensional $\mathbb{R}$-vector through the natural conversion of $\mathbb{C}$ to $\mathbb{R}^{2}$, since $d$ is even.

It’s too cumbersome to manually give the underlying set and the encoding. Here we introduce a classical concept from programming language theory Program () that makes it super easy to construct new types and make things fairly readable.

###### Definition 13 (Finite Algebraic Data Type, Mathematical Forms) .

We define two ways of creating new types by combining existing types:

- 1.
Sum type. Given types $\mathcal{T}_{i}=(S_{i},\phi_{i},d_{i})$ over base space $B$ for $i=1,\ldots,n$, we define the sum type of $\mathcal{T}_{i}$, denoted by $\sum_{i=1}^{n}\mathcal{T}_{i}$, as follows,
•
let $S=({\left\{1\right\}}\times S_{1})\sqcup\ldots\sqcup({\left\{n\right\}}\times S_{n})$;
•
let $d=d_{{\left\llbracket{n}\right\rrbracket}}+\max_{i=1}^{n}d_{i}$;
•
let $\phi:S\rightarrow B^{d}$ be such that
$\forall i\in{\left\llbracket{n}\right\rrbracket},s\in S_{i},\phi((i,s))=\phi_{{\left\llbracket{n}\right\rrbracket}}(i)\oplus\phi_{i}(s)\in B^{d_{{\left\llbracket{n}\right\rrbracket}}+d_{i}}\subseteq B^{d}.$
(8)
Note that ${\left|S\right|}=\sum_{i=1}^{n}{\left|S_{i}\right|}$, thus the name sum type.
- 2.
Product type. Given Local Types $\mathcal{T}_{i}=(S_{i},\phi_{i},d_{i})$ over base space $B$ for $i=1,\ldots,n$, we define the product type of $\mathcal{T}_{i}$, denoted by $\prod_{i=1}^{n}\mathcal{T}_{i}$, as follows,
•
let $S=S_{1}\times\ldots\times S_{n}$;
•
let $d=\sum_{i=1}^{n}d_{i}$;
•
let $\phi:S\rightarrow B^{d}$ be such that
$\forall s=(s_{1},\ldots,s_{n})\in S,\phi(s)=\phi_{1}(s_{1})\oplus\ldots\phi_{n}(s_{n})\in B^{d}.$
(9)
Note that ${\left|S\right|}=\prod_{i=1}^{n}{\left|S_{i}\right|}$, thus the name product type.

Although we can define things and refer to things in terms of mathematical equations, it’s sometimes cumbersome to do so. So we shall frequently refer to types using a programming language form, like \ColorboxmygrayInlineCybertronForm or more complicated things like \ColorboxmygrayInlineOption<T> a builtin generic type.

###### Definition 14 (Unit Type) .

The unit type is a type with $S={\left\{0\right\}}$ and $\phi:S\rightarrow B^{0},0\mapsto 0_{B}$. In Cybertron, it’s denoted as \ColorboxmygrayInline().

###### Definition 15 (Array Type) .

Given a type $\mathcal{T}$, the array type of $\mathcal{T}$ with length $\ell\in\mathbb{N}$ is the type with $S=\mathop{\text{S}}(\mathcal{T})^{\ell}$, $d=\ell d_{\mathcal{T}}$ and $\phi:S\rightarrow B^{\ell d_{\mathcal{T}}},(s_{1},\ldots,s_{\ell})\mapsto\phi_{\mathcal{T}}(s_{1})\oplus\ldots\oplus\phi_{\mathcal{T}}(s_{\ell})$. It’s denoted by $\mathcal{T}^{\ell}$. In Cybertron, it’s denoted as \ColorboxmygrayInline[T;N].

###### Definition 16 (Vector Type of Finite Capacity) .

Given a type $\mathcal{T}$, the vector type of finite capacity of $\mathcal{T}$ with maximal length $\ell\in\mathbb{N}$ is the type with $S=\bigsqcup_{i=1}^{\ell}{\mathop{\text{Set}}\left(\mathcal{T}\right)}^{i}$, $d=d_{{\left\llbracket{\ell}\right\rrbracket}}+\ell d_{\mathcal{T}}$ and $\phi:S\rightarrow B^{d_{{\left\llbracket{\ell}\right\rrbracket}}+\ell d_{\mathcal{T}}},(s_{1},\ldots,s_{i})\mapsto\phi_{{\left\llbracket{\ell}\right\rrbracket}}(i)\oplus\phi_{\mathcal{T}}(s_{1})\oplus\ldots\oplus\phi_{\mathcal{T}}(s_{i})\oplus 0_{B}\oplus\ldots\oplus 0_{B}$ with just enough number of copies of $0_{B}$ such that the dimensionality matches. It’s denoted by $\mathcal{T}^{\leq\ell}$.In cybertron, it’s denoted as \ColorboxmygrayInlineBoundedVec<T,N>.

However, it’s cumbersome and obtuse to define and operate in mathematical forms only. So we shall give a definition closer to actual programming that is more convenient and easy to read.

###### Definition 17 (Finite Algebraic Data Type, the Code Forms) .

We define two ways to create new types:

- 1.
Enum type. An enum type is the sum type of a finite set of variant types. Each variant type is associated with a different identifier and can be
•
unit like, a unit type;
•
struct like, a product of several types, each called a field of the variant, and associated with an identifier;
•
tuple like, a product of several types, each called a field of the variant, but not associated with an identifier.
Syntactically, an enum type is specified as follows,
[⬇](data:text/plain;base64,ZW51bSA8dHlwZS1uYW1lPiB7CiAgICA8aWRlbnRpZmllcj4geyAgICAgICAgICAgIC8vIDFzdCB2YXJpYW50LCBzdHJ1Y3QgbGlrZQogICAgICAgIDxpZGVudGlmaWVyPjogPHR5cGU+LCAvLyAxc3QgbmFtZWQgZmllbGQgb2YgMXN0IHZhcmlhbnQKICAgICAgICA8aWRlbnRpZmllcj46IDx0eXBlPiwgLy8gMm5kIG5hbWVkIGZpZWxkIG9mIDFzdCB2YXJpYW50CiAgICAgICAgLi4uCiAgICB9LAogICAgPGlkZW50aWZpZXI+IHsgICAgICAgICAgICAvLyAybmQgdmFyaWFudCwgc3RydWN0IGxpa2UKICAgICAgICA8aWRlbnRpZmllcj46IDx0eXBlPiwgLy8gMXN0IGZpZWxkIG9mIDJuZCB2YXJpYW50CiAgICAgICAgLi4uCiAgICB9LAogICAgPGlkZW50aWZpZXI+ICggICAgICAgICAgICAvLyAzcmQgdmFyaWFudCwgdHVwbGUgbGlrZQogICAgICAgIDx0eXBlPiwgICAgICAgICAgICAgICAvLyAxc3QgdHVwbGUgZmllbGQgb2YgM3JkIHZhcmlhbnQKICAgICAgICA8dHlwZT4sICAgICAgICAgICAgICAgLy8gMm5kIHR1cGxlIGZpZWxkIG9mIDNyZCB2YXJpYW50CiAgICAgICAgLi4uCiAgICApLAogICAgPGlkZW50aWZpZXI+LCAgICAgICAgICAgICAvLyA0dGggdmFyaWFudCwgdW5pdCBsaWtlCiAgICAuLi4KfQ==)
1enum <type-name> {
2 <identifier> { // 1st variant, struct like
3 <identifier>: <type>, // 1st named field of 1st variant
4 <identifier>: <type>, // 2nd named field of 1st variant
5 ...
6 },
7 <identifier> { // 2nd variant, struct like
8 <identifier>: <type>, // 1st field of 2nd variant
9 ...
10 },
11 <identifier> ( // 3rd variant, tuple like
12 <type>, // 1st tuple field of 3rd variant
13 <type>, // 2nd tuple field of 3rd variant
14 ...
15 ),
16 <identifier>, // 4th variant, unit like
17 ...
18}
For example,
[⬇](data:text/plain;base64,ZW51bSBFeHByIHsKICAgIFZhcmlhYmxlKElkZW50VG9rZW4pLCAgICAvLyAxc3QgdmFyaWFudCwgdHVwbGUgbGlrZQogICAgQmluYXJ5IHsgICAgICAgICAgICAgICAgIC8vIDJuZCB2YXJpYW50LCBzdHJ1Y3QgbGlrZQogICAgICAgIGxvcGQ6IEV4cHJJZCwKICAgICAgICBvcHI6IEJpbmFyeU9wclRva2VuLAogICAgICAgIHJvcGQ6IEV4cHJJZCwKICAgIH0sCiAgICBQcmVmaXggeyAgICAgICAgICAgICAgICAgLy8gM3JkIHZhcmlhbnQsIHN0cnVjdCBsaWtlCiAgICAgICAgb3ByOiBQcmVmaXhPcHJUb2tlbiwKICAgICAgICBvcGQ6IEV4cHJJZCwKICAgIH0sCiAgICBTdWZmaXggeyAgICAgICAgICAgICAgICAgLy8gNHRoIHZhcmlhbnQsIHN0cnVjdCBsaWtlCiAgICAgICAgb3BkOiBFeHBySWQsCiAgICAgICAgb3ByOiBTdWZmaXhPcHJUb2tlbiwKICAgIH0sCiAgICBQYW5pYywgICAgICAgICAgICAgICAgICAgLy8gNXRoIHZhcmlhbnQsIHVuaXQgbGlrZQp9)
1enum Expr {
2 Variable(IdentToken), // 1st variant, tuple like
3 Binary { // 2nd variant, struct like
4 lopd: ExprId,
5 opr: BinaryOprToken,
6 ropd: ExprId,
7 },
8 Prefix { // 3rd variant, struct like
9 opr: PrefixOprToken,
10 opd: ExprId,
11 },
12 Suffix { // 4th variant, struct like
13 opd: ExprId,
14 opr: SuffixOprToken,
15 },
16 Panic, // 5th variant, unit like
17}
- 2.
Struct type. A struct type is just the product type of
[⬇](data:text/plain;base64,c3RydWN0IDx0eXBlLW5hbWU+IHsKICAgIDxpZGVudGlmaWVyPjogPHR5cGU+LAogICAgPGlkZW50aWZpZXI+OiA8dHlwZT4sCiAgICAuLi4KfQ==)
1struct <type-name> {
2 <identifier>: <type>,
3 <identifier>: <type>,
4 ...
5}
[⬇](data:text/plain;base64,c3RydWN0IEEgewogICAgYTogaTMyCn0=)
1struct A {
2 a: i32
3}

To show how convenient this is, we can define the very useful option type as follows,

###### Definition 18 (Option type) .

For a local type \ColorboxmygrayInlineT, we can define the local as

###### Definition 19 (Global Types) .

Global types are defined to be sequences of local types.

###### Example 9 (Representation of Graphs) .

Graphs can be represented as sequences of its nodes. We can use position index to use as node references.

###### Definition 12 (Local Type) .

###### Remark 2 .

###### Remark 3 .

###### Example 7 (Finite Set) .

###### Example 8 (Position Encoding) .

###### Definition 13 (Finite Algebraic Data Type, Mathematical Forms) .

###### Definition 14 (Unit Type) .

###### Definition 15 (Array Type) .

###### Definition 16 (Vector Type of Finite Capacity) .

###### Definition 17 (Finite Algebraic Data Type, the Code Forms) .

###### Definition 18 (Option type) .

###### Definition 19 (Global Types) .

###### Example 9 (Representation of Graphs) .

### D.4 Computation Graph

For convenience, we shall use computation graph as a vehicle to describe complicated computation processes. Computation graph is close to actual computation process and one can derive an understanding of the computation difficulty from the graph’s mathematic properties (width, depth, etc.)

###### Definition 20 (Directed Simple Graph) .

A directed simple graph $G$ is a pair $(V,E)$ where $V$ is a finite set, and $E\subseteq V\times V$ is called edges.

In the following, we shall simplify the "directed simple graph" to just graph.

###### Definition 21 (Computation Graph) .

A computation graph is an acyclic directed graph $G=(V,E)$ with additional structures:

- 1.
for each vertex $v\in V$, there is an associated type, denoted by $T_{v}$;
- 2.
for each vertex $v\in V$ with a positive number of incoming edges, let $v_{1},\dots,v_{n}$ be the other vertices for the incoming edges, then there is an associated function $f_{v}$ from $T_{v_{1}}\times\dots\times T_{v_{n}}$ to $T_{v}$.

A computation graph naturally generates a function from source vertices to sink vertices. Let $v_{1}^{\operatorname{in}},\dots,v_{n}^{\operatorname{in}}$ be the set of vertices with no incoming edges, and let $v_{1}^{\operatorname{out}},\dots,v_{m}^{\operatorname{out}}$ be the set of vertices with no outgoing edges. Then we can construct a function from $T_{v^{\operatorname{in}}_{1}}\times\dots\times T_{v^{\operatorname{in}}_{n}}$ to $T_{v^{\operatorname{out}}_{1}}\times\dots\times T_{v^{\operatorname{out}}_{m}}$ in the following obvious manner:

- 1.
let $(x_{1},\dots,x_{n})\in T_{v^{\operatorname{in}}_{1}}\times\dots\times T_{v^{\operatorname{in}}_{n}}$ be an input;
- 2.
for each $v^{\operatorname{in}}_{i}$, assign it with value $x_{i}$;
- 3.
for each vertex $v\in V$ with all its incoming vertices $v_{1},\dots,v_{l}$ assigned with a value, assign it with the value $f_{v}(x_{v_{1}},\dots,x_{v_{l}})$ where $x_{v_{i}}$ denotes the value assigned to $v_{i}$;
- 4.
repeat the process until all vertices are assigned a value, then take $(x_{v^{\operatorname{out}}_{1}},\dots,x_{v^{\operatorname{out}}_{m}})$ as the output.

Our goal is to make a hypothesis class using the above graph. To control the statistical and computational complexity, we put restrictions on the choice of $T_{v}$ and $f_{v}$, as follows:

###### Definition 22 (Restricted Computation Graph) .

Let $\mathcal{U}$ be a set of types, and for any $A,B\in\mathcal{U}$, there is a set of functions $\operatorname{Mor}(A,B)$ from $A$ to $B$. We require that $T_{v},T_{v}^{\text{in}}\in\mathcal{U}$ and $f_{v}\in\operatorname{Mor}(T_{v}^{\text{in}},T_{v})$ where $T_{v}^{\text{in}}:=\prod\limits_{v^{\prime}v\in E}T_{v^{\prime}}$. We also require that the underlying graph $G$ satisfies certain conditions (width, depth, etc.)

###### Definition 23 (Restricted Computation Graph Of Sequences) .

Let $\mathcal{U}$ be a universe such that for a set of types $\mathcal{U}_{0}$ all types in $\mathcal{U}$ are of the form $A^{*}$ for some type $A\in\mathcal{U}_{0}$, and $\operatorname{Mor}(A^{*},B^{*})$ are functions that preserve sequence lengths.

Given a restriction, the class of functions generated by restricted computation graphs is the central object to study in this paper. We shall use an even more restricted computation graph of sequences. We shall argue about the class of functions formed that

- 1.
it’s rich enough to contain many interesting operations including SQL, compiler (type inference, static analysis)
- 2.
it’s computationally reasonable, and can be represented by transformers with pragmatic bounds
- 3.
it has a reasonable statistical complexity

As a corollary, our theories suggest that transformers can possibly learn to do many interesting things with reasonable computational and statistical complexity.

To our knowledge, this is the first theoretical paper that gives pragmatic optimistic bounds for the power of transformers in a wide range of meaningful language tasks.

Now we introduce graph-theoretical measures that will play key roles in our new complexity theory.

The most basic one is the following:

###### Definition 24 (Depth of Graph) .

The depth of a computation graph is defined to the length of the longest path, denoted by ${\operatorname{Depth}(G)}$.

For convenience, we define the following vertex-wise depth.

###### Definition 25 (Depth of Graph Vertex) .

The depth of a vertex $v$ of a computation graph is defined as the length of the longest path with end $v$, denoted by ${\operatorname{Depth}(v)}$.

The smaller $d_{G}$ is, the more parallel the computation is.

However, we shall discuss a more nuanced measure, containment, as follows:

###### Definition 20 (Directed Simple Graph) .

###### Definition 21 (Computation Graph) .

###### Definition 22 (Restricted Computation Graph) .

###### Definition 23 (Restricted Computation Graph Of Sequences) .

###### Definition 24 (Depth of Graph) .

###### Definition 25 (Depth of Graph Vertex) .

### D.5 Functions over Local Types

###### Definition 26 (Functions over Local Types) .

Given Local Types $\mathcal{T},\mathcal{R}$, the functions from $\mathcal{T}$ to $\mathcal{R}$ are defined to be just the functions from ${\mathop{\text{Set}}\left(\mathcal{T}\right)}$ to ${\mathop{\text{Set}}\left(\mathcal{R}\right)}$.

###### Remark 4 .

The domains and codomains are all finite sets, so there aren’t many constraints we want to enforce here. Basically, these are “discrete” functions.

###### Definition 27 (Functions over Algebraic Data Types) .

Let $\mathcal{T},\mathcal{S}_{1},\ldots,\mathcal{S}_{m},\mathcal{R}$ be Local Types, and suppose that $\mathcal{T}$ is an algebraic data type, then we can construct functions from $\mathcal{T}\times\mathcal{S}_{1}\times\ldots\times\mathcal{S}_{m}$ to $\mathcal{R}$ as follows,

- 1.
suppose that $\mathcal{T}$ is the sum type of $\mathcal{T}_{1},\ldots,\mathcal{T}_{n}$. Then given functions $f_{i}:\mathcal{T}_{i}\times\mathcal{S}_{1}\times\cdots\times\mathcal{S}_{m}$ for $i=1,\ldots,n$, we can construct a function $f$, by letting
$f((i,t),s_{1},\ldots,s_{m})=f_{i}(t,s_{1},\ldots,s_{m}),$
(10)
for each $t\in{\mathop{\text{Set}}\left(T_{i}\right)},s_{1}\in{\mathop{\text{Set}}\left(\mathcal{S}_{1}\right)},\ldots,s_{m}\in{\mathop{\text{Set}}\left(\mathcal{S}_{m}\right)}$.
(Note that we use the pair $(i,t)$ because the underlying set of $\mathcal{T}$ is $\bigsqcup_{i=1}^{n}{\left\{i\right\}}\times{\mathop{\text{Set}}\left(\mathcal{T}_{i}\right)}$.)
- 2.
suppose that $\mathcal{T}$ is the product type of $\mathcal{T}_{1},\ldots,\mathcal{T}_{n}$. Then given a function $f_{*}:\mathcal{T}_{1}\times\cdots\times\mathcal{T}_{n}\times\mathcal{S}_{1}\times\cdots\times\mathcal{S}_{m}$ for $i=1,\ldots,n$, we can construct a function $f$, by letting
$f((t_{1},\ldots,t_{n}),s_{1},\ldots,s_{m})=f_{*}(t_{1},\ldots,t_{n},s_{1},\ldots,s_{m}),$
(11)
for each $t\in{\mathop{\text{Set}}\left(T_{i}\right)},s_{1}\in{\mathop{\text{Set}}\left(\mathcal{S}_{1}\right)},\ldots,s_{m}\in{\mathop{\text{Set}}\left(\mathcal{S}_{m}\right)}$.

It is not enough to just mathematically construct. We should also discuss how neural networks can represent these functions. We define the representation of functions over Local Types formally as follows:

###### Definition 28 (Representation of Functions over Local Types Using Multi-Layer Perceptions) .

Let $\mathcal{T},\mathcal{R}$ be Local Types. Given a function $f$ from $\mathcal{T}$ to $\mathcal{R}$, we say it is representable by MLP of dimension $d\geq\max\left\{d_{\mathcal{T}},d_{\mathcal{R}}\right\}$ and number of layers $L$, if there exists $\tilde{f}\in{\operatorname{ResMlp}^{d}_{L}}$ such that

$$ $\iota_{1}\circ\phi_{\mathcal{R}}\circ f=\tilde{f}\circ\iota_{2}\circ\phi_{\mathcal{T}},$ (12) $$

where $\iota_{1}:\mathbb{R}^{d_{\mathcal{R}}}\rightarrow\mathbb{R}^{d}$ and $\iota_{2}:\mathbb{R}^{d_{\mathcal{T}}}\rightarrow\mathbb{R}^{d}$ are the canonical embeddings by putting zeros to fit the dimensionalities.

Here are some trivially true facts:

###### Proposition 3 .

[Identities are Representable] For any Local Type $\mathcal{T}$, the identity map $\operatorname{Id}_{\mathcal{T}}$ is representable in ${\operatorname{ResMlp}^{d_{\mathcal{T}}}_{1}}$.

###### Proof.

Just take $W_{0}^{(1)}=I_{d},W_{1}^{(1)}=W_{2}^{(2)}=0,B_{1}^{(1)}=B_{2}^{(2)}=0$.
∎

###### Proposition 4 .

[Equality is Representable]
The equality function for any local type $\mathcal{T}$ is representable in ${\operatorname{ResMlp}^{2d}_{2}}$, where $d$ is the encoding dimension of $\mathcal{T}$.

###### Proof.

Let $x,y\in\mathcal{T}$ be the inputs. We encode them as $\phi_{\mathcal{T}}(x),\phi_{\mathcal{T}}(y)\in\mathbb{R}^{d}$. The equality function can be represented as:

$$ $f_{\text{eq}}(x,y)=\min\left(1,A\sum_{i=1}^{d}{\left|\phi_{\mathcal{T}}(x)_{i}-\phi_{\mathcal{T}}(y)_{i}\right|}\right),$ $$

where $A$ is a large enough positive constant such that the RHS is either $1$ or 0 0.

This can be implemented in two-layer ResMLP with dimension $2d$.
∎

###### Proposition 5 .

[Boolean NOT is Representable]
The Boolean NOT function is representable in ${\operatorname{ResMlp}^{1}_{1}}$.

###### Proof.

It’s affine.
∎

###### Proposition 6 .

[Boolean AND is Representable]
The Boolean AND function is representable in ${\operatorname{ResMlp}^{2}_{1}}$.

###### Proof.

Represent each Boolean value as a binary flag within a $1$-dimensional vector. Then AND is just taking the minimum. By $\min(a,b)=b-{\sigma_{\operatorname{ReLU}}\left(b-a\right)}$, we’re done.
∎

###### Proposition 7 .

[Boolean OR is Representable]
The Boolean OR function is representable in ${\operatorname{ResMlp}^{2}_{1}}$.

###### Proof.

Represent each Boolean value as a binary flag within a $1$-dimensional vector. Then OR is just taking the maximum. By $\max(a,b)=a+{\sigma_{\operatorname{ReLU}}\left(b-a\right)}$, we’re done.
∎

###### Proposition 8 .

[THEN_SOME is Representable]
The function \ColorboxmygrayInlineBool::then_some: \ColorboxmygrayInlineBool $\times$ \ColorboxmygrayInlineT $\to$ \ColorboxmygrayInlineOption T returns \ColorboxmygrayInlineSome t if the boolean is true and \ColorboxmygrayInlineNone otherwise. This function is representable in ${\operatorname{ResMlp}^{d+1}_{1}}$.

###### Proof.

Encode the boolean as a binary flag in a $(d+1)$-dimensional vector, where the first component indicates the boolean value and the remaining $d$ components hold the value of type \ColorboxmygrayInlineT. The residual MLP $f_{\text{resmlp}}$ constructs the output \ColorboxmygrayInlineOption T by assembling the flag and the value split into positive and negative parts influenced by the flag:

$$ $f_{\text{resmlp}}(X)=\begin{pmatrix}x_{1}\\ {\sigma_{\operatorname{ReLU}}\left(x_{2:d+1}-Ax_{1}\right)}-{\sigma_{\operatorname{ReLU}}\left(-x_{2:d+1}-Ax_{1}\right)}\end{pmatrix}.$ $$

Here, $A$ is a vector of dimension $d$ with all entries positive and large enough to ensure proper thresholding. Specifically, each entry of $A$ should be larger than the maximum absolute value that can be represented in the corresponding dimension of type \ColorboxmygrayInlineT. This ensures that when $x_{1}=1$, the subtraction $x_{2:d+1}-A$ will always be negative, and when $x_{1}=0$, it will not affect the value.

When the flag is true ($x_{1}=1$), ${\sigma_{\operatorname{ReLU}}\left(x_{2:d+1}-A\right)}=0$
and ${\sigma_{\operatorname{ReLU}}\left(-x_{2:d+1}-A\right)}$ retains the negated value, resulting in \ColorboxmygrayInlineSome t. When the flag is false ($x_{1}=0$), both ReLU terms preserve the value, yielding \ColorboxmygrayInlineNone. Thus, $f_{\text{resmlp}}$ effectively implements \ColorboxmygrayInlineBool::then_some within a single layer of the MLP.
∎

###### Proposition 9 .

[Option Or is Representable] Let \ColorboxmygrayInlineT be a local type, let \ColorboxmygrayInlineOption::or be the function that maps two values \ColorboxmygrayInlinea,b of type \ColorboxmygrayInlineOption T to a value \ColorboxmygrayInlinec of type \ColorboxmygrayInlineOption T such that \ColorboxmygrayInlinec is equal to \ColorboxmygrayInlinea when \ColorboxmygrayInlinea is not none, and equal to \ColorboxmygrayInlineb otherwise. Then \ColorboxmygrayInlineOption::or is representable in ${\operatorname{ResMlp}^{2(d+1)}_{1}}$.

###### Proof.

Each \ColorboxmygrayInlineOption T is represented as a $(d+1)$-dimensional vector, where the first component is a binary flag indicating the presence (1 for \ColorboxmygrayInlineSome, 0 for \ColorboxmygrayInlineNone), and the remaining $d$ components encode the value. Given inputs ${a,b\in{\Colorbox{mygrayInline}{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language\lst@@@set@numbers\lst@@@set@rulecolor\lst@@@set@frame\lst@@@set@frame\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{Option}}{\@listingGroup{ltx_lst_space}{}}{\@listingGroup{ltx_lst_identifier}{T}}}}}}}$, the residual MLP $f_{\text{resmlp}}$ processes the concatenated vector

$$ $X=\begin{pmatrix}a_{\text{flag}}\\ a_{\text{val}}\\ b_{\text{flag}}\\ b_{\text{val}}\end{pmatrix}.$ $$

The MLP is designed to separate $b_{\text{val}}$ into positive and negative parts ($b_{+},b_{-}$ respectively) influenced by $a_{\text{flag}}$. Specifically, it computes:

$$ $\begin{split}f_{\text{resmlp}}(X)&=a_{\text{val}}+{\sigma_{\operatorname{ReLU}}\left(b_{+}-Aa_{\text{flag}}\right)}-{\sigma_{\operatorname{ReLU}}\left(b_{-}-Aa_{\text{flag}}\right)}\\ &=a_{\text{val}}+{\sigma_{\operatorname{ReLU}}\left(b_{\text{val}}-Aa_{\text{flag}}\right)}-{\sigma_{\operatorname{ReLU}}\left(-b_{\text{val}}-Aa_{\text{flag}}\right)},\end{split}$ (13) $$

where $A$ is a vector with large positive entries that ensures the ReLU activation zeroes out the non-selected parts based on the flag. When $a_{\text{flag}}=1$, the terms involving $b$ are suppressed, resulting in $c=a$. Conversely, when $a_{\text{flag}}=0$, the positive part of $b$ remains, effectively selecting $b$. Thus, $f_{\text{resmlp}}$ accurately implements the \ColorboxmygrayInlineOption::or function, demonstrating that it is representable within ${\operatorname{ResMlp}^{2(d+1)}_{1}}$.
∎

###### Proposition 10 (Field Access Is Representable in ResMlp) .

For algebraic data type, either struct field access, enum discriminator, and variant field access can be represented in ${\operatorname{ResMlp}^{d}_{1}}$ where $d$ is the encoding dimension.

###### Proof.

Obvious because these operations are linear.
∎

###### Proposition 11 .

[Composition of Functions Representable in ResMlp] For local types $\mathcal{T},\mathcal{S},\mathcal{R}$, with maps $f:\mathcal{T}\rightarrow\mathcal{S}$ and map $g:\mathcal{S}\rightarrow\mathcal{R}$ representable in ${\operatorname{ResMlp}^{d_{1}}_{L_{1}}}$ and ${\operatorname{ResMlp}^{d_{2}}_{L_{2}}}$ respectively. Then $g\circ f$ is representable in ${\operatorname{ResMlp}^{\max\left\{d_{1},d_{2}\right\}}_{L_{1}+L_{2}}}$.

###### Proof.

Obvious by using the first $L_{1}$ layers to map from $\mathcal{T}$ to $\mathcal{S}$ and using the rest $L_{2}$ layers to map from $\mathcal{S}$ to $\mathcal{R}$. The process can be visualized as in Figure [3](#A4.F3).

Figure: Figure 3: Transformation from $\phi_{\mathcal{T}}(x)$ to $\phi_{\mathcal{S}}(f(x))$ to $\phi_{\mathcal{R}}(g(f(x)))$ with MLP layers.

∎

###### Proposition 12 .

[Computation Graph of Functions Representable in ResMlp] Let $\mathcal{G}$ be a computation graph, with each vertex $v$ being of some local type $\mathcal{T}_{v}$, and the construction functions are representable in ${\operatorname{ResMlp}^{d_{v}}_{L_{v}}}$. For convenience, if $v$ is a source vertex, $d_{v}$ is defined to be the encoding dimension of $\mathcal{T}_{v}$ and $L_{v}=0$. Then the function induced by the computation graph is representable in ${\operatorname{ResMlp}^{\sum_{v\in\mathcal{G}}d_{v}}_{{\operatorname{Depth}(\mathcal{G})}(\max_{v\in\mathcal{G}}L_{v}+1)+1}}$.

###### Proof.

We construct a global residual multi-layer perceptron (ResMLP) that simulates the computation graph $\mathcal{G}$ by aggregating and updating the states of all vertices simultaneously. Let $D=\sum_{v\in\mathcal{G}}d_{v}$ be the total dimension, where $d_{v}$ is the dimension associated with vertex $v$. The global ResMLP will have a depth of ${\operatorname{Depth}(\mathcal{G})}(\max_{v}L_{v}+1)$.

Consider the concatenated state vector $X^{(t)}\in\mathbb{R}^{D}$, which is a concatenation of the states of all vertices:

$$ $X^{(t)}=\left(X_{v}^{(t)}\right)_{v\in\mathcal{G}},$ $$

where $X_{v}^{(t)}\in\mathbb{R}^{d_{v}}$ is the state of vertex $v$ at layer $t$.

Initialization occurs at depth zero, corresponding to the source vertices of the computation graph. The state vector $X^{(0)}$ is set by assigning the input vectors to the source vertices and initializing all other vertices to zero. Formally, if $V_{0}$ denotes the set of source vertices, then:

$$ $X_{v}^{(0)}=\begin{cases}x_{v}&\text{if }v\in V_{0},\\ 0&\text{otherwise},\end{cases}$ $$

where $x_{v}\in\mathbb{R}^{d_{v}}$ is the input to source vertex $v$. Because $X_{v}^{(0)}$ is of dimensionality $d_{v}$ equal to the encoding dimension, this agrees with our convention for representing functions over local types.

We proceed inductively over the depth levels of the computation graph. For each depth level $k=1,2,\dotsc,{\operatorname{Depth}(\mathcal{G})}$, we perform the following steps in the global ResMLP.

- 1.
Input Aggregation Layer. We apply a linear transformation to gather the outputs from the predecessor vertices of each vertex at depth $k$ and feed them as inputs to these vertices. Specifically, we define a linear mapping $W_{\text{agg}}^{(k)}\in\mathbb{R}^{D\times D}$ such that:
$\tilde{X}^{(t_{k})}=W_{\text{agg}}^{(k)}X^{(t_{k-1})},$
where $t_{k-1}$ is the layer after processing depth $k-1$, and $\tilde{X}^{(t_{k})}$ is the aggregated input for the vertices at depth $k$. The matrix $W_{\text{agg}}^{(k)}$ rearranges and combines the outputs from predecessor vertices to provide the correct inputs to each vertex at depth $k$.
Specifically, for each vertex $v$ at depth $k$, and for each predecessor $u$ of $v$ in the computation graph, the matrix $W_{\text{agg}}^{(k)}$ contains entries that copy the output of $u$ into the input positions of $v$. All other entries in $W_{\text{agg}}^{(k)}$ are set to zero or identity as appropriate.
- 2.
Local Computation Layers. For each vertex $v$ at depth $k$, we simulate its local ResMLP of depth $L_{v}$. Since the depths $L_{v}$ may vary, we pad the local ResMLPs to have a uniform depth $L=\max_{v}L_{v}$ by adding identity mappings where necessary. The updates for vertex $v$ are computed as:
$\displaystyle X_{v}^{(t_{k}+1)}$
$\displaystyle=\tilde{X}_{v}^{(t_{k})}+{f_{\text{fcn}}}_{v}\left(\tilde{X}_{v}^{(t_{k})}\right),$
$\displaystyle X_{v}^{(t_{k}+k^{\prime})}$
$\displaystyle=X_{v}^{(t_{k}+k^{\prime}-1)}+{f_{\text{fcn}}}_{v}\left(X_{v}^{(t_{k}+k^{\prime}-1)}\right),\quad\text{for }k^{\prime}=2,\dotsc,L_{v},$
$\displaystyle X_{v}^{(t_{k}+k^{\prime})}$
$\displaystyle=X_{v}^{(t_{k}+k^{\prime}-1)},\quad\text{for }k^{\prime}=L_{v}+1,\dotsc,L.$
Here, ${f_{\text{fcn}}}_{v}$ denotes the single-layer fully connected network (as per Definition [1](#Thmproposition1)) for vertex $v$.
- 3.
State Update. After completing the local computations for depth $k$, we update the global state vector $X^{(t_{k}+L)}$ by concatenating the updated states of all vertices:
$X^{(t_{k}+L)}=\left(X_{v}^{(t_{k}+L)}\right)_{v\in\mathcal{G}}.$

The total number of layers added for depth $k$ is $L+1$, accounting for the input aggregation layer and the $L$ layers simulating the local ResMLPs.

By repeating this process for each depth level $k=1,2,\dotsc,{\operatorname{Depth}(\mathcal{G})}$, we simulate the entire computation graph within a global ResMLP of depth ${\operatorname{Depth}(\mathcal{G})}(\max_{v}L_{v}+1)$.

Lastly, we use the final layer to perform a linear mapping so that the output is in the correct linear representation, clearing out the intermediate values.

Therefore, the function computed by the global ResMLP is equivalent to the function induced by the computation graph $\mathcal{G}$, and it is representable in ${\operatorname{ResMlp}^{D}_{{\operatorname{Depth}(\mathcal{G})}(\max_{v}L_{v}+1)}}$.
∎

###### Remark 5 .

We only prove things around MLPs here. Later, we shall show that this will imply that the induced map operation over sequences can be represented by transformers.

###### Definition 26 (Functions over Local Types) .

###### Remark 4 .

###### Definition 27 (Functions over Algebraic Data Types) .

###### Definition 28 (Representation of Functions over Local Types Using Multi-Layer Perceptions) .

###### Proposition 3 .

###### Proof.

###### Proposition 4 .

###### Proof.

###### Proposition 5 .

###### Proof.

###### Proposition 6 .

###### Proof.

###### Proposition 7 .

###### Proof.

###### Proposition 8 .

###### Proof.

###### Proposition 9 .

###### Proof.

###### Proposition 10 (Field Access Is Representable in ResMlp) .

###### Proof.

###### Proposition 11 .

###### Proof.

###### Proposition 12 .

###### Proof.

###### Remark 5 .

### D.6 Functions over Global Types

The task we want transformers to express is too complicated to be cleanly described in one shot. So we introduce the following lemma to significantly simplify things. The lemma shall be useful for our future papers on this topic.

###### Proposition 13 .

[Composition of Functions Representable in Transformers]
For local types $\mathcal{T}$, $\mathcal{S}$, $\mathcal{R}$, with maps $f:\mathcal{T}^{*}\rightarrow\mathcal{S}^{*}$ and $g:\mathcal{S}^{*}\rightarrow\mathcal{R}^{*}$ representable in ${\operatorname{Tf}^{d_{1}}_{H_{1},L_{1}}}$ and ${\operatorname{Tf}^{d_{2}}_{H_{2},L_{2}}}$ respectively. Then the composition $g\circ f$ is representable in ${\operatorname{Tf}^{\max\left\{d_{1},d_{2}\right\}}_{\max\left\{H_{1},H_{2}\right\},L_{1}+L_{2}}}$.

###### Proof.

This is basically the same as the proof of Proposition [11](#Thmproposition11).
∎

###### Proposition 14 .

[Computation Graphs of Functions Representable in Transformers]
Suppose we have a computation graph $G=(V,E)$ with types $\mathcal{T}_{v}=T_{v}^{*}$ together with encoding map $\psi_{v}:T_{v}\to\mathbb{R}^{d_{v}}$ and decoding map $\phi_{v}:\mathbb{R}^{d_{v}}\to T_{v}$, satisfying $\phi_{v}\circ\psi_{v}\equiv\operatorname{id}_{T_{v}}$, and there exists some positive integer $d_{0}$ such that for each $v\in V$, $f_{v}$ can be represented in

$$ ${\operatorname{Tf}^{d}_{H_{v},L_{v}}}$ $$

Let $f$ be the function generated by the computation graph. Then $f$ can be represented in ${\operatorname{Tf}^{d}_{H,L}}$ if $d\geq\sum_{v}d_{v}+Hd_{0}$, $L\geq\frac{|G|}{H}+d_{G}$ where $d_{G}$ is the depth of the graph.

###### Remark 6 .

This doesn’t really cover the above. The bound in Proposition [14](#Thmproposition14) isn’t always tight for model dimension when the computation graph is deep and Proposition [13](#Thmproposition13) complements it.

###### Proof.

WLOG, assume that $d=\sum_{v\in V}d_{v}+Hd_{0}$. Then

$$ $\mathbb{R}^{d}=\underbrace{{\left(\mathop{\bigoplus}\limits_{v\in V}\mathbb{R}^{d_{v}}\right)}}_{C}\oplus\underbrace{{\left(\mathop{\bigoplus}\limits_{h\in[H]}\mathbb{R}^{d_{0}}\right)}}_{A}.$ (14) $$

Here $C$ stands for "cache" used for storing computed values, and $A$ stands for "active" used for storing intermediate computation results.

Make an order of all the nodes in the graph, say $V={\left\{v_{1},\ldots,v_{|G|}\right\}}$ such that ${\operatorname{Depth}(v_{i})}\leq{\operatorname{Depth}(v_{j})}$ if $i\leq j$.

We now imagine the transformer computation process as gradually evaluating the value of each vertex, starting from $v_{1}$ to $v_{|G|}$. Every $\max_{v}L_{v}$ layers form a layer group, and after each layer group, at most $H$ vertices are assigned values. The equation [14](#A4.E14) implies that we have enough memory to cache the computed values and intermediate values in small transformers.

Now let this process continue until we compute all the values. It must be finite because after each layer group, at least one of the vertices is computed. But this bound is too loose. We claim the following:

Claim: the number of layer groups where less than $H$ vertices are assigned values is smaller than ${\operatorname{Depth}(G)}$.

Sketch of Proof of Claim: for any layer group where less than $H$ vertices are assigned, all the vertices that aren’t assigned after this layer group must have larger depth than any vertices that are assigned values before this layer group, otherwise such a vertice can be evaluated in this layer group. Define the depth of any layer group to be the smallest depth of vertices evaluated in this layer group. Then for any unsatiated layer group, it must have a larger depth than the previous layer group. But depth can only increase ${\operatorname{Depth}(G)}$ times, thus there are at most ${\operatorname{Depth}(G)}$ unsatiated layer groups.

Proof of Claim: let $V_{1},\ldots,V_{l}$ be the vertices evaluated at each layer group. Note that $l$ is a different symbol than $L$ and means that the number of layer groups rather than the number of layers.

For convenience, let $D_{i}$ be the minimum of the depths of vertices in $V_{i}$.

Suppose that the $i$th layer group is unsatiated, then $i<l$. We want to show that $D_{i}<D_{i+1}$. Suppose otherwise, i.e., $D_{i}=D_{i+1}$. Because the $i$th layer group is unsatiated, for any $v\in V_{i+1}$, $v$ must have dependencies that haven’t been evaluated before the $i$th layer group. Choose $v_{0}\in V_{i},v_{1}\in V_{i+1}$ such that ${\operatorname{Depth}(v_{0})}={\operatorname{Depth}(v_{1})}=D_{i}=D_{i+1}$. Note that any dependency of $v_{1}$ must have smaller depths than $v_{0}$, then must have already be evaluated before the $i$th layer group. Contradiction!

Now given the claim, we have that for all but at most ${\operatorname{Depth}(G)}$ choices of $i=1,\ldots,l$, we have ${\left|V_{i}\right|}=H$, then we have

$$ ${\left|G\right|}=\sum_{i=1}^{l}{\left|V_{i}\right|}\geq(l-{\operatorname{Depth}(G)})H$ (15) $$

Then $l\leq\frac{{\left|G\right|}}{H}+{\operatorname{Depth}(G)}$.

Then $L\leq l\cdot\max_{v\in G}L_{v}={\left(\frac{{\left|G\right|}}{H}+{\operatorname{Depth}(G)}\right)}\max_{v\in G}$.

∎

###### Proposition 15 .

[Nearest Left/Right]
For any local type \ColorboxmygrayInlineT, consider the function that maps a sequence of type \ColorboxmygrayInlineOption<T> to nearest left/right neighbors that are not none. It’s representable in ${\operatorname{Tf}^{d+1}_{1,1}}$

###### Proof.

There is only one layer and one head needed, so we can omit the layer and head index.

WLOG, we consider the nearest left case.

We just need to make the attention exponential look like this:

$$ $Q_{p}^{\top}K_{p^{\prime}}+\lambda\Psi_{p^{\prime}-p}=a_{\text{flag},p^{\prime}}-1_{p^{\prime}-p>0},$ (16) $$

where $a_{\text{flag},p^{\prime}}\in{\left\{0,1\right\}}$ indicates whether the value at position $p^{\prime}$ is some or none.

We set $V_{p^{\prime}}$ to represent the value of type \ColorboxmygrayInlineOption<T>.

For the starter token $p_{0}$, we make it such that

$$ $Q_{p}^{\top}K_{p_{0}}+\lambda\Psi_{p_{0}-p}=1,$ (17) $$

and

$$ $V_{p_{0}}=\bm{0},$ (18) $$

so that when there are no some to the left, it will give us none.
∎

###### Proposition 16 .

[Nearest Two Left/Right]
For any local type \ColorboxmygrayInlineT, consider the function that maps a sequence of type \ColorboxmygrayInlineOption<T> to nearest two left/right neighbors that are not none. It’s representable in ${\operatorname{Tf}^{O(d)}_{O(1),O(1)}}$ where $d$ is the encoding dimension of \ColorboxmygrayInlineT.

###### Proof.

We can utilize Proposition [15](#Thmproposition15) and [14](#Thmproposition14).

The nearest two left or right is equivalent to first computing the nearest left/right, and then packing them together into one and compute its nearest left/right. The process is represented by a small constant computation graph, then we’re done.
∎

###### Proposition 13 .

###### Proof.

###### Proposition 14 .

###### Remark 6 .

###### Proof.

###### Proposition 15 .

###### Proof.

###### Proposition 16 .

###### Proof.

### D.7 Syntax and Semantics of Cybertron

Having laid the necessary mathematical foundation behind Cybertron, we now turn to explaining its surface—its syntax and semantics. Cybertron serves as a syntax sugar for expressing local and global computation graphs, which are the vehicles used to demonstrate the expressive power of transformers. In Cybertron, computations are divided into two layers: the local world and the global world. These layers play distinct but complementary roles in constructing computation graphs.

#### D.7.1 Local World

The local world in Cybertron corresponds to the feed-forward layers of a transformer, focusing on computations over local types. Local types represent individual tokens or data points, and computations in this world handle operations on tokens independently of their surrounding context.

##### Data Types.

Local types in Cybertron include basic types such as \ColorboxmygrayInlineBool, \ColorboxmygrayInlineIdx, \ColorboxmygrayInlinePos, \ColorboxmygrayInlineFin<n>, \ColorboxmygrayInlineBoundedVec<T, N>, etc. These types are essential for building local computation graphs that operate over individual tokens. Compound types, like structs and enums, can also be defined for more complex token representations. These types serve as the building blocks for the local computation graphs that transform data at the token level.

##### Functions.

Functions in the local world define operations upon information over individual tokens. These operations form nodes in the local computation graphs. For instance, operations like binary or unary expressions, conditionals, and matches on token types are transformed into computation graphs by handling each individual token’s data.

##### Control Flow.

In the local world, control flow structures such as \ColorboxmygrayInlineif and \ColorboxmygrayInlinematch are transformed into computation graphs by treating each branch or arm as an expression that returns an \ColorboxmygrayInlineOption based on conditions. These \ColorboxmygrayInlineOption values are then combined using the \ColorboxmygrayInlineOption::or function. According to Proposition 9, \ColorboxmygrayInlineOption::or maps two \ColorboxmygrayInlineOption<T> values and returns the first non-\ColorboxmygrayInlineNone value, or the second one otherwise. This allows conditional branches to be represented in computation graphs as sequential option evaluations, where the first matching condition provides the result.

#### D.7.2 Global World

The global world extends beyond individual tokens to sequences of tokens, represented as global types. These global types are denoted as \ColorboxmygrayInlineSeq<T>, where \ColorboxmygrayInlineT is a local type. The global world represents the full transformer, focusing on operations involving sequences of tokens, including variable definitions, expressions involving variable references, and function calls.

##### Variable Definitions.

Variables in the global world are defined using global types, which represent sequences of local tokens. These definitions correspond to nodes in the global computation graph.

##### Expressions.

Expressions in the global world consist of references to variables or function calls. Since the global world operates over sequences of tokens, these expressions are translated into sequence-level operations in the computation graph.

##### Function Calls.

Function calls are key elements of the global world. They are represented by applying global functions to sequences of tokens. Cybertron provides map functions to elevate local functions to global functions by mapping them across sequences. Additionally, attention methods like \ColorboxmygrayInlinenearest_left and \ColorboxmygrayInlinenearest_right handle dependencies between tokens in the sequence by identifying relationships based on their positions.

In the global world, computation graphs are built by composing map functions and attention methods. These graphs, unlike those in the local world, do not include control flow mechanisms.

### D.8 Dyck Language

This section demonstrates how the local world in Cybertron operates over token-level computations and how the global world handles sequence-level operations. We use a Dyck language example to explain the interactions between these two worlds. The example processes a sequence of delimiters (like parentheses) and checks for matching pairs.

##### Local World.

In Cybertron, the local world operates on individual tokens. Here, the local types are simple, such as \ColorboxmygrayInlineDelimiter and \ColorboxmygrayInlinePreAst, which represent information associated with individual tokens. These types allow for token-level operations like comparisons and transformations.

We define a \ColorboxmygrayInlinestruct to represent a delimiter and an \ColorboxmygrayInlineenum to classify delimiters as either left or right. These definitions reflect local types, as they hold information over a single token.

Here, the local types \ColorboxmygrayInlineDelimiter and \ColorboxmygrayInlinePreAst define operations upon individual tokens, representing fundamental units of the computation graph at the local level. The local world is responsible for handling these small, token-level computations independently of the global sequence.

##### Global World.

In the global world, Cybertron operates on sequences of tokens, treating the collection of local types as a single unit of computation. The global world introduces global types such as \ColorboxmygrayInlineSeq<Option<PreAst>>, which represents a sequence of optional delimiters. The global world handles sequence-level operations by applying functions like \ColorboxmygrayInlinenearest_left and \ColorboxmygrayInlinenearest_right to capture the relationships between tokens in the sequence.

The following function operates on a sequence of \ColorboxmygrayInlinePreAst, reducing matched pre-asts. The recursive application of \ColorboxmygrayInlinestep gives us the classifier for Dyck language.

##### Local Worlds.

The \ColorboxmygrayInlinestep_aux function matches tokens based on their nearest neighbors within the sequence, eliminating pre-asts if a match is found.

In this example, the global function \ColorboxmygrayInlinestep uses \ColorboxmygrayInlinenearest_left and \ColorboxmygrayInlinenearest_right to capture sequence-level dependencies, while the local function \ColorboxmygrayInlinestep_aux uses conditional logic to check for matching pairs of delimiters. The local world handles token-level logic, while the global world coordinates operations across the entire sequence. This separation reflects how Cybertron handles computations at different levels of granularity.

Thus, this example illustrates how Cybertron leverages both the local and global worlds to build comprehensive computation graphs in a convenient, comprehensive yet rigorous manner. The local world performs individual tokenwise operations, and the global world captures relationships between tokens in a sequence, demonstrating how Cybertron enables transformers to express complex computations.

## Appendix E Mini-Husky Details

Here’s the BNF of the Mini-Husky language:

Below is a sample piece of codes:

It should be noted that the above is not the full story. There are additional constraints put on the ASTs. However, these can be easily implemented as tree functions that are easy for transformers to express. As we are focusing on higher level language processing capabilities, we ignore the details here.

Additionally, we need to require that for semantic correctness, we must have proper symbol resolution and type correctness.

### E.1 Additional Details about Compiler Tasks.

The outputs of the tasks are defined using Cybertron as follows:

- •
The construction of AST task’s final output is the collection all AST nodes. More concretely, the output is a sequence of \ColorboxmygrayInlineOption<Ast> with length equal to the input token sequence’s length, where \ColorboxmygrayInlineOption<Ast> denoted the type \ColorboxmygrayInlineAst will a null value added and \ColorboxmygrayInlineAst is the type storing the information of a node, including its parent, and its data of type \ColorboxmygrayInlineAstData. In Cybertron, we define \ColorboxmygrayInlineAst and \ColorboxmygrayInlineAstData explicitly as follows:
[⬇](data:text/plain;base64,Ly8vIFJlcHJlc2VudHMgYSBub2RlIGluIGFuIEFic3RyYWN0IFN5bnRheCBUcmVlIChBU1QpLgovLy8KLy8vIEVhY2ggYEFzdGAgbm9kZSBoYXMgYSByZWZlcmVuY2UgdG8gaXRzIHBhcmVudCBub2RlIChpZiBhbnkpIGFuZCBob2xkcwovLy8gdGhlIGFzc29jaWF0ZWQgc3ludGF4IGRhdGEgKHN1Y2ggYXMgZXhwcmVzc2lvbnMsIHN0YXRlbWVudHMsIG9yIG90aGVyCi8vLyBjb25zdHJ1Y3RzIGRlZmluZWQgaW4gdGhlIGBBc3REYXRhYCBlbnVtKS4KcHViIHN0cnVjdCBBc3QgewogICAgLy8vIFRoZSBpbmRleCBvZiB0aGUgcGFyZW50IG5vZGUgaW4gdGhlIEFTVCwgaWYgaXQgZXhpc3RzLgogICAgLy8vCiAgICAvLy8gLSBgU29tZShJZHgpYDogVGhlIG5vZGUgaGFzIGEgcGFyZW50LCBhbmQgYElkeGAgcmVwcmVzZW50cyBpdHMgcG9zaXRpb24uCiAgICAvLy8gLSBgTm9uZWA6IFRoZSBub2RlIGlzIHRoZSByb290IG9yIGRvZXMgbm90IGhhdmUgYSBwYXJlbnQuCiAgICBwdWIgcGFyZW50OiBPcHRpb248SWR4PiwKICAgIC8vLyBUaGUgZGF0YSBhc3NvY2lhdGVkIHdpdGggdGhpcyBBU1Qgbm9kZS4KICAgIHB1YiBkYXRhOiBBc3REYXRhLAp9CgovLy8gRW51bWVyYXRpb24gcmVwcmVzZW50aW5nIGRpZmZlcmVudCB0eXBlcyBvZiBBYnN0cmFjdCBTeW50YXggVHJlZSAoQVNUKSBub2RlcwpwdWIgZW51bSBBc3REYXRhIHsKICAgIC8vLyBSZXByZXNlbnRzIGEgbGl0ZXJhbCB2YWx1ZSAoZS5nLiwgaW50ZWdlciwgc3RyaW5nKQogICAgTGl0ZXJhbChMaXRlcmFsKSwKICAgIC8vLyBSZXByZXNlbnRzIGFuIGlkZW50aWZpZXIgKGUuZy4sIHZhcmlhYmxlIG5hbWUpCiAgICBJZGVudChJZGVudCksCiAgICAvLy8gUmVwcmVzZW50cyBhIGJpbmFyeSBleHByZXNzaW9uIChlLmcuLCBgeCArIHlgLCBgYSAqIGJgKQogICAgQmluYXJ5IHsKICAgICAgICAvLy8gSW5kZXggb2YgdGhlIGxlZnQgb3BlcmFuZAogICAgICAgIGxvcGQ6IElkeCwKICAgICAgICAvLy8gT3BlcmF0b3IgaW4gdGhlIGJpbmFyeSBleHByZXNzaW9uIChlLmcuLCBgK2AsIGAqYCkKICAgICAgICBvcHI6IEJpbmFyeU9wciwKICAgICAgICAvLy8gSW5kZXggb2YgdGhlIHJpZ2h0IG9wZXJhbmQKICAgICAgICByb3BkOiBJZHgsCiAgICB9LAogICAgLi4uIC8vIG90aGVyIHZhcmlhbnRzCn0=)
1/// Represents a node in an Abstract Syntax Tree (AST).
2///
3/// Each ‘Ast‘ node has a reference to its parent node (if any) and holds
4/// the associated syntax data (such as expressions, statements, or other
5/// constructs defined in the ‘AstData‘ enum).
6pub struct Ast {
7 /// The index of the parent node in the AST, if it exists.
8 ///
9 /// - ‘Some(Idx)‘: The node has a parent, and ‘Idx‘ represents its position.
10 /// - ‘None‘: The node is the root or does not have a parent.
11 pub parent: Option<Idx>,
12 /// The data associated with this AST node.
13 pub data: AstData,
14}
15
16/// Enumeration representing different types of Abstract Syntax Tree (AST) nodes
17pub enum AstData {
18 /// Represents a literal value (e.g., integer, string)
19 Literal(Literal),
20 /// Represents an identifier (e.g., variable name)
21 Ident(Ident),
22 /// Represents a binary expression (e.g., ‘x + y‘, ‘a * b‘)
23 Binary {
24 /// Index of the left operand
25 lopd: Idx,
26 /// Operator in the binary expression (e.g., ‘+‘, ‘*‘)
27 opr: BinaryOpr,
28 /// Index of the right operand
29 ropd: Idx,
30 },
31 ... // other variants
32}
- •
The output of the symbol resolution task is the collection of symbol resolution results on all applicable tokens. More concretely, the output is a sequence of values of type \ColorboxmygrayInlineOption<SymbolResolution> where \ColorboxmygrayInlineOption<SymbolResolution> is the type \ColorboxmygrayInlineSymbolResolution with a null value added for non-applicability and \ColorboxmygrayInlineSymbolResolution is the type storing the result of the symbol resolution, being either a success with a resolved symbol of type \ColorboxmygrayInlineSymbol or a failure with an error of type \ColorboxmygrayInlineSymbolResolutionError. In Cybertron, we define \ColorboxmygrayInlineSymbolResolution explicitly as follows:
[⬇](data:text/plain;base64,Ly8gYW4gZW51bSB0eXBlIGRlZmluaXRpb24sIGJhc2ljYWxseSBhIHRhZ2dlZCB1bmlvbiB0eXBlCnB1YiBlbnVtIFN5bWJvbFJlc29sdXRpb24gewogICAgT2soU3ltYm9sKSwgLy8gZW51bSB0eXBlIHZhcmlhbnQgZm9yIHN1Y2Nlc3Mgd2l0aCBhIHJlc29sdmVkIHN5bWJvbAogICAgRXJyKFN5bWJvbFJlc29sdXRpb25FcnJvciksIC8vIGVudW0gdHlwZSB2YXJpYW50IGZvciBmYWlsdXJlIHdpdGggYW4gZXJyb3IKfQ==)
1// an enum type definition, basically a tagged union type
2pub enum SymbolResolution {
3 Ok(Symbol), // enum type variant for success with a resolved symbol
4 Err(SymbolResolutionError), // enum type variant for failure with an error
5}
- •
The type analysis task’s final output is the collection of all type errors. More concretely, the output is a sequence of \ColorboxmygrayInlineOption<TypeError>, where \ColorboxmygrayInlineOption<TypeError> denoted the type \ColorboxmygrayInlineTypeError will a null value added and \ColorboxmygrayInlineTypeError is the type storing the information of a type error. The position of type errors agrees with the source tokens leading to these errors. In Cybertron, we define \ColorboxmygrayInlineTypeError explicitly as follows:
[⬇](data:text/plain;base64,Ly8gVGhpcyBlbnVtIHJlcHJlc2VudHMgdmFyaW91cyBraW5kcyBvZiB0eXBlIGVycm9ycwpwdWIgZW51bSBUeXBlRXJyb3IgewogICAgLy8gVGhpcyB2YXJpYW50IGluZGljYXRlcyBhIHR5cGUgbWlzbWF0Y2gKICAgIC8vIGBleHBlY3RlZGAgaXMgdGhlIHR5cGUgdGhhdCB3YXMgYW50aWNpcGF0ZWQKICAgIC8vIGBhY3R1YWxgIGlzIHRoZSB0eXBlIHRoYXQgd2FzIGVuY291bnRlcmVkCiAgICBUeXBlTWlzbWF0Y2ggeyBleHBlY3RlZDogVHlwZSwgYWN0dWFsOiBUeXBlIH0sCn0=)
1// This enum represents various kinds of type errors
2pub enum TypeError {
3 // This variant indicates a type mismatch
4 // ‘expected‘ is the type that was anticipated
5 // ‘actual‘ is the type that was encountered
6 TypeMismatch { expected: Type, actual: Type },
7}
One can expand the definition to include other kinds of type errors.

(1) Type definition. Types are either identified uniquely by a single identifier like \ColorboxmygrayInline<identifier>, or builtin generic types \ColorboxmygrayInlineOption<<identifier>> or \ColorboxmygrayInlineVec<<identifier>>. Users can define custom types without generics like the following (f32 means float32 and i32 means int32 below):

This part is actually a part of the AST task and type definition is a variant of the \ColorboxmygrayInlineAstData type:

(2) Type specification. Each appeared variable has a unique type, either by specification or speculation. All parameters of a function must be specified explicitly by users. Variables defined by let statements might or might not be specified, as follows:

The return type of functions must be specified. The field type of structs and enum variants must be specified. the type of expressions of function calls and field access will be determined correspondingly.

The output of the task is the collection of all type signatures, represented as a sequence of values of type \ColorboxmygrayInlineOption<TypeSignature> where \ColorboxmygrayInlineTypeSignature is the type holding the essential information of type specifications. In Cybertron, \ColorboxmygrayInlineTypeSignature is defined as,

(3) Type inference. As discussed above, not all variables have their types specified.

In the above code, $1$ is an ambiguous literal that can be of type \ColorboxmygrayInlinei32, \ColorboxmygrayInlinei64, \ColorboxmygrayInlineu32, \ColorboxmygrayInlineu64, etc, and the types of \ColorboxmygrayInliney and \ColorboxmygrayInlinez is not specified. However, one easily sees that there exists one and only one choice of the types of \ColorboxmygrayInline1, \ColorboxmygrayInliney, and \ColorboxmygrayInlinez such that the whole code is type correct. Utilizing this property, the user can opt out of a significant portion of type specification, achieving static guarantees.

A Type Inference Algorithm:
For simplicity, we shall prove transformers can implement a simple type inference algorithm:
we maintain a table of type assignments for variables. We update the entries of the table by means of reduction, i.e., assuming the whole code is correctly typed and infer more and more unspecified types until we encounter errors or all types are inferred. The process is largely parallel, and we call the number of rounds needed the depth of type inference.

In the above code, the first round, we determine that the type of both \ColorboxmygrayInline1 and the type of \ColorboxmygrayInliney are equal to the type of \ColorboxmygrayInlinex which is \ColorboxmygrayInlinei32. But we have no way to determine the type of \ColorboxmygrayInlinez because the type of \ColorboxmygrayInliney is unknown at the first round. In the second round, \ColorboxmygrayInlinez can be determined to be of type \ColorboxmygrayInlinei32 because the type of \ColorboxmygrayInliney is already inferred.

The output of the task is the collection all types inferred, represented as a sequence of values of type \ColorboxmygrayInlineOption<TypeInference> where \ColorboxmygrayInlineTypeInference is the type holding the inferred type. In Cybertron, \ColorboxmygrayInlineTypeSignature is defined as,

## Appendix F Transformer AST Proof

### F.1 High Level Overview

Here we give the full details of the proof of transformers being able to parse ASTs.

On a high level, we are going to see the parsing of ASTs as an assembly process. First, we immediately get the atomic ones, like identifiers, literals, etc. Then we assembly all composite ASTs with enough precedence util all tokens are consumed. We can prove that at the $n$th round, all ASTs with depth no more than $n$ are already constructed. In the process, we must keep track of the unconsumed tokens and newly constructed ASTs (to be consumed as children for new ASTs in the next round, as we are going bottom up). We use \ColorboxmygrayInlinepre_asts to denote all the unconsumed tokens and newly constructed ASTs and use \ColorboxmygrayInlineasts to denote all the constructed(allocated) ASTs. For correctness guarantees, we give detailed type specifications for tokens, ASTs, and PreASTs as follows.

We define the Token type as follows:

The type has an encoding dimenion $d_{\text{Token}}=\Theta(\log L)$, which is large enough to faithfully represent its information.

More specifically, the types \ColorboxmygrayInlineLiteral, \ColorboxmygrayInlineKeyword, \ColorboxmygrayInlineIdent, \ColorboxmygrayInlineOpr, \ColorboxmygrayInlineLeftDelimiter, \ColorboxmygrayInlineRightDelimiter, \ColorboxmygrayInlineSeparator are local types assumed to have encoding dimension less than $d_{\text{Token}}$. \ColorboxmygrayInlineKeyword, \ColorboxmygrayInlineOpr, \ColorboxmygrayInlineLeftDelimiter, \ColorboxmygrayInlineRightDelimiter, \ColorboxmygrayInlineSeparator are small, so they can be encoded in a straight-forward manner entirely using $d_{\text{Token}}$. However, \ColorboxmygrayInlineLiteral and \ColorboxmygrayInlineIdent are larger than representable by a limited number of bits because potentially a \ColorboxmygrayInlineLiteral can be a string literal of arbitrary length and an \ColorboxmygrayInlineIdent can also be of arbitrary length. This can be solved through methods like interning, which gives all literals and identifiers that actually appear in the input distinct encodings. As the context length is $L$, the number of different literals/identifiers are bounded by context length and interning needs $O(d_{\text{Token}})=O(\log L)$ to work. As far as our theories are concerned, it’s totally reasonable to assume that all these types are assumed to have encoding dimension less than $d_{\text{Token}}=O(\log L)$.

We define AST type as follows:

Note that we intentionally structure the tree by always storing the parent but not necessarily storing all children information. In our assumptions, we only control the depth of ASTs but don’t control the number of children. More specifically, a function can have as many statements as possible. To avoid overflowing, we don’t store all children information. As we shall see, parent information alone is enough for transformers to perform tree operations.

The \ColorboxmygrayInlineAstData is the most complicated we define in this paper, as follows:

The \ColorboxmygrayInlinereduce function in Cybertron is designed to progressively refine sequences of pre-abstract syntax trees (pre-ASTs) and allocated abstract syntax trees (ASTs). The function takes two input sequences: \ColorboxmygrayInlinepre_asts, which is a sequence of optional pre-ASTs, and \ColorboxmygrayInlineallocated_asts, which is a sequence of optional ASTs. It returns a tuple containing the reduced sequences of pre-ASTs and allocated ASTs.

The reduction process is carried out in multiple stages, each focusing on different syntactic constructs:

- 1.
\Colorbox
mygrayInlinereduce_by_opr: This step handles reduction by dealing with operators and their precedence. It simplifies expressions involving operations to form more compact ASTs.
- 2.
\Colorbox
mygrayInlinereduce_by_delimited: This step reduces constructs that are delimited, such as those involving parentheses, braces, or other grouping symbols. It ensures that delimited blocks are properly nested and combined in the AST.
- 3.
\Colorbox
mygrayInlinereduce_by_call: In this stage, function or method calls are reduced. This involves identifying and structuring calls within the AST, ensuring correct representation of function invocations.
- 4.
\Colorbox
mygrayInlinereduce_by_stmt: This reduction step addresses statements, ensuring that individual statements are correctly parsed and represented within the AST, such as assignment statements, loops, and conditionals.
- 5.
\Colorbox
mygrayInlinereduce_by_defn: Finally, reduction by definition handles the parsing of definitions, such as variable or function declarations. This step ensures that all definitions are correctly represented within the AST.

By sequentially applying these reduction steps, the \ColorboxmygrayInlinereduce function progressively transforms the initial sequences into their most refined forms, ready for further syntactic or semantic analysis.

In the above definition, we actually used Rust’s mutable variable semantics. However, it’s straightforward to see that it translates to a computation graph that is a sequential composition of subgraphs with sequential length $n$. Because the AST’s depth is bounded by $D$, we can just take $n$ to be $D$. Each subgraph is generated from the \ColorboxmygrayInlinereduce function, then they are all constant graphs constructed by global and local functions, then by Proposition [13](#Thmproposition13),[11](#Thmproposition11) and [2](#Thmproposition2) they translate to transformers with $O(\log L+D)$ depth, model dimension, and number of heads, where $\log L$ comes from the encoding of types like \ColorboxmygrayInlineToken.

Below we give full details of the various reduction functions.

As these are implemented as Rust functions, they have been tested against a number of inputs. We don’t guarantee an industry level of correctness, but the key point is well illustrated.

### F.2 Operators

In this section, we lay down the definition of \ColorboxmygrayInlinereduce_by_opr.

### F.3 Statements

In this section, we lay down the definition of \ColorboxmygrayInlinereduce_by_stmt.

### F.4 Generalized Call Forms

In this section, we lay down the definition of \ColorboxmygrayInlinereduce_by_call.

### F.5 Definitions

In this section, we lay down the definition of \ColorboxmygrayInlinereduce_by_defn.

## Appendix G Transformer Symbol Resolution Proof

Here we lay down the code for symbol resolution. The actual process involves many details such as computing ranks (the exact position of an AST node among its siblings), scopes, and roles (a more precise version of AST, computed from its parent recursively), definitions and resolutions.

### G.1 Ranks

In the above, \ColorboxmygrayInlinecount_past_by_attention that count is representable by transformers by utilizing directly hard attention and the starter token. If the count is $c$, we shall get $c/(c+1)$ from the attention directly.

### G.2 Scopes

### G.3 Roles

### G.4 Defns

### G.5 Resolutions

In the above code, we use a somehow complicated attention which we should illustrate why it’s representable by transformers. The essence is to prove \ColorboxmygrayInlinesymbol_defn_scope.contains(scope.unwrap()) can be represented as part of the inner product in $Q^{\top}K$. This can be done by looking closer to what \ColorboxmygrayInlinecontains does. Consider two scopes, \ColorboxmygrayInlinescope1 and \ColorboxmygrayInlinescope2, which are sequences of bracket ast indices (can be null). The function returns true if the sequence of \ColorboxmygrayInlinescope1 contains the sequence of \ColorboxmygrayInlinescope2 as prefix, which can be achieved by $\sum_{i}x_{i}^{\top}y_{i}$ where $x_{i},y_{i}$ are the encoding of $i$th ast indices of \ColorboxmygrayInlinescope1 and \ColorboxmygrayInlinescope2 after some transformations (different transformations because the function is asymmetric) so that $x_{i}^{\top}y_{i}=0$ if and only if either $x_{i}$ is a None or $x_{i}$ represents the same thing as $y_{i}$, and $x_{i}^{\top}y_{i}<0$ otherwise. More concretely, if $x_{i}$ is a None, $x_{i}=\bm{0}$ by choice, and equal to $(1,u_{i})$ otherwise where $u_{i}$ corresponds to the encoding of the $i$th ast index of \ColorboxmygrayInlinescope1; if $y_{i}$ is a None, $y_{i}=\bm{0}$ by choice, and equal to $(-1,v_{i})$ otherwise where $A>0$ and $v_{i}$ corresponds to the encoding of the $i$th ast index of \ColorboxmygrayInlinescope2. We should choose the encoding $u_{i},v_{i}$ such that $u_{i}^{\top}v_{i}=1$ if and only if they encode the same index, which is obviously easy enough.

## Appendix H Transformer Type Checking Proof

Here we lay down the code for type analysis. It should be noted that we didn’t completely implement all the details. Things like struct fields, enum variant fields are left out. However, we already cover the essential mechanism of type analysis, making it sufficient for proof purposes.

### H.1 Type Signatures

### H.2 Type Inference

### H.3 Type Expectations

### H.4 Type Errors

## Appendix I Lower Bounds

### I.1 Lower bounds for RNN: Easy Bounds due to Memory

###### Proof of Theorem 4 .

Our proof resonates with the proof of Theorem 4.6 in Wen et al. () and Theorem 8 in Bhattamishra et al. (). For $L,D,H\in\mathbb{N}$, suppose that $D$ makes $\operatorname{MiniHuskyAnnotated}_{D,H}$ to be nontrivial, i.e., one can define functions with one parameter and use function calls. Simple calculations shows we can choose $D=7$ and $H=1$.
If a RNN represents a function maps any token sequence of length $L$ in $\operatorname{MiniHuskyAnnotated}_{D,H}$ to its type errors represented as a sequence of values of type \ColorboxmygrayInlineOption<TypeError>, then the memory right before type checking must store all previous type signatures, the number of which can be as many as $\Omega(L)$ in the worst case. Assuming proper numerical discretization, the memorization of these type signatures would require the memory size to be $\Omega(L)$ in the worst case.
∎

###### Proof of Theorem 4 .

## Appendix J Additional Experiment Details

### J.1 Setups

Model details are shown in Table [2](#A10.T2), and other hyperparameters are shown in Table [2](#A10.T2).

**Table 1: Model specification**
| Specification | Value |
| --- | --- |
| Transformer |  |
| - Hidden size ($d_{h}$) | $\{8k|1\leq k\leq 8\}$ |
| $\cup\{208\}$ |  |
| - Num attention heads | $\min\{4,d_{h}\}$ |
| - Num hidden layers | $8$ |
| - Intermediate size | $2d_{h}$ |
| - Max position embeddings | $\leq 2048$ |
| RNN |  |
| - Hidden size | $\{8k|1\leq k\leq 8\}$ |
| $\cup\{256\}$ |  |
| - Num layers | $8$ |

### J.2 Additional Results

Figures [4](#A10.F4),[5](#A10.F5),[6](#A10.F6),[7](#A10.F7) are other metrics in the experiments.
Here the loss function is the summation of cross entropies for each sub task.

Figure: Figure 4: Figures for the dataset with $(f,d,v,e)=(10,3,0.2,0.5)$.
Refer to caption: /html/2410.14706/assets/x5.png

Figure: Figure 5: Figures for the dataset with $(f,d,v,e)=(20,5,0.2,0.5)$.
Refer to caption: /html/2410.14706/assets/x9.png

Figure: Figure 6: Figures for the dataset with $(f,d,v,e)=(40,10,0.2,0.5)$.
Refer to caption: /html/2410.14706/assets/x13.png

Figure: Figure 7: Figures for the dataset with $(f,d,v,e)=(80,20,0.2,0.5)$.
Refer to caption: /html/2410.14706/assets/x17.png

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: See above.
soundness: 1
strengths: * The authors attempt a formal analysis of Transformers.
summary: The submission discusses a (set of proofs) that show that Transformers are able to perform some analysis tasks required during compilation with a bounded number of parameters. To this end, a new programming language and a DSL are discussed (but not defined). Some empirical results show that there are tasks for which Transformers perform better than RNNs.
weaknesses: (1) The paper is fundamentally incomplete: while the authors claim to introduce Mini-Husky as a pared-down programming language, they do not do this at all in the main text of the paper, and even in the extensive appendix, they do not actually provide a full definitions of syntax or semantics.

As example, note that the BNF is Appendix D does not in any way correspond to the example given 5 lines under it, which uses keywords such as `mut` and assignment operators such as `+=`, `.` and `assert` statements; none of which appear in the BNF. Similarly, no semantics of the language are provided, so it is impossible to verify any proof about its properties. The BNF also does not cover the syntax for type annotations, which is crucial given the paper's focus on typing tasks.

(2) The paper is overclaiming: no attempt is made at showing the suitability of Transformers as "compiler", as two core phases (code generation and optimization) are not even discussed. Text and helpers such as Fig. 2 seem to be written as if compilers only analyze code, but do nothing else. The term "efficient" is used repeatedly without a definition, and it remains unclear what is viewed as efficient (is it meant as running in polynomial time, or in the less formal, but better understood way of being acceptably fast?)

(3) The paper is not well-written, often referring to concepts, identifiers or ideas not introduced. Examples:
* "the computation process is easily represented in Cybertron" (line 358), when Cybertron is only introduced in the following section
* $L$ in line 318 (its meant to be the sequence length I assume, but the last use of $L$ was in l196 and refers to the number of layers)
* "As types are mathematically interpreted in this paper a discrete subset of a vector space" is the only mention of a representation of types in the main text.

(4) The citing of related work is often incorrect. For example, Sect 3 starts with "The major innovation in the transformer architecture is self-attention", which is surprising given that the Transformers paper ("Attention is all you need") has a related work discussing prior uses of self-attention. On the other hand, the contrast to the most related work to the submitted paper (RASP, Weiss et al. 2021) is not discussed beyond a "Cybertron has a powerful algebraic type system that helps to prove complicated operations beyond simple algorithms" (though that type system is not actually introduced in the paper).

Let me be clear that none of the criticism above is about the actual research, but only about the presentation - I don't feel it's possible to fully grasp the proposed ideas given the paper. To some degree, this is a consequence of the ICLR page limit, and so I would make the following two suggestions to the authors:

(i) Submit to a venue with a longer page limit (e.g., TLMR, or POPL/PLDI/OOPSLA as conferences on the PL side that were open to such contributions in the past - in particular POPL seems appropriate). This will allow for a longer exposition and inclusion of more of the crucial details in the main text.

(ii) Think about the core ideas that make things work, and try to focus the exposition on that. For example, RASP already showed how to express primitive programming constructs as parts of a Transformer, so what is new here? What changes are required to make the proofs work? Think back on early steps of the work: what challenges did you need to overcome? These are the things most interesting for other researchers.

---

confidence: 3
contribution: 1
initial_rating: 1
presentation: 2
questions: Please provide a compact definition for "Cybertron", or alternatively concrete examples of step evaluations in this framework. Put these front and center e.g in section 3. This is, in this reviewer's opinion, essential for substantiating the claims in a bottom-up fashion (i.e. from the complexity of the proof building blocks).
soundness: 1
strengths: The paper is original in attempting to use a "bottom-up" formalism for proving the asymptotic memory requirements of LLMs for program compilation tasks.
summary: This paper introduces "Cybertron", a DSL for representing expressiveness proofs of transformer-based language models, as applied to programming language compilation tasks such as symbol resolution and syntax tree construction.
The main claim of this paper is that the number of LLM layers necessary for certain compiler operations as represented in Cybertron is logarithmic in the input sequence length L.
The contributions of the paper are a synthetic object language "MiniHusky" for generating valid programs, as well as the aforementioned proof language.
weaknesses: The paper does not convince the reader that its main claims are supported by proof or empirical evidence. Alternatively, the claims are moot since they only apply to a language whose semantic properties can be checked with bounded complexity (MiniHusky).

The exposition of this paper is too intricate, and most of the body of the paper is spent introducing background definitions and not the actual substance of the claims. 

* Theorem 1 is "proven" essentially by repeating the theorem statement. Thms 2 and 3 do not have a recognizable proof. Neither of these are proofs in any useful sense, which is problematic as the paper puts "provably" in its title.
* What is "Cybertron"? We don't see a compact definition of this proof language, which is unfortunate because this is the main technical device of the paper.  Only in the middle of Section 5.4 (line 409) do we get a hint of what is this Cybertron, whereas this should be moved up to where it's first mentioned. Appendix E starts with what are supposed to be examples but are exactly the same code snippet repeated 4 times.
* I do not find support for the claim of exponential separation between RNNs and transformer models wrt model size parameter in the type inference task (claim 3 in the Contributions section).  From figure 2 it seems that both model classes saturate in accuracy at comparable sizes.
* Section 3 the Preliminaries material could be easily moved to the appendices, as it's not used in the body of the paper.
* It should be stated more clearly that the claims are only relative to the object language introduced by the authors (MiniHusky). This language apparently is designed to have "shallow" ASTs and a bounded complexity of type inference, but neither claim is proven in the body of the paper. 
* The "clean code" heuristic suggested as a justification for MiniHusky is only cited but never formalized. On the other hand, this was a set of folklore programming practices and not grounded in theory since their inception.
* There is a lot of ad-hoc technical material in the appendices (which by the way does not cite any preexisting literature), but it is very hard to connect it to the main body of the paper. Much of the "proof" content is apparently limited to its Rust implementation, which is unfortunate for those who cannot easily compile and run it in their heads.
* Figure 2 is hard to read and does not make a clear claim, esp re. the "first 8 points" remark.  Similarly, the other figures with experimental results at the end of the appendices are given almost without comment.

Minor comment: it's unclear why the authors choose to repeatedly call out AgdaJS in the beginning.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Aside from what has been mentioned in the Weaknesses section, here are some more suggestions and questions:
- I would personally defer a portion of Section 3, especially the math definitions, to the appendices, and keep the rest that is actually relevant to understanding the rest of the main text.
- The authors categorize both symbolic resolution and type analysis as semantic analysis, when in fact symbolic resolution is purely syntactic and type checking/inference is also syntax-driven. While I think I know what the authors may mean by “semantic,” the paper could benefit from a brief discussion on the distinction between a syntactic task and a semantic task.
- It could have been more precise and to-the-point if the authors referred to the “AST construction” task simply as parsing (while briefly defining it).
- Regarding the use of “correctly” on line 108, I would use “effectively” instead, because after all there is no absolute guarantee on correctness.
- When explaining what symbol resolution does, the concept of shadowing would help with explaining the example program. In general, having some formal definitions for the three tasks would be nice, especially for symbol resolution and type analysis.
- While it is reasonable to assume that programs are written according to the clean code principle, that book is rather controversial and not everyone finds it to be completely reasonable in this day and age.
- Line 334 and 335: I would appreciate an explanation of what “allocated” and “initialized” mean in this context.
- Line 435: For readers not very familiar with associative recall, could the authors consider adding a brief explanation of why type checking covers associative recall?
- Line 503: Regarding “real datasets,” what would they be? I only see synthetic data mentioned.
- Line 1077: I would say “recurrence” instead of “recursion.”
- Line 1311-1313: If Cybertron’s semantics and type system had been proven correct, then the authors would not have needed to resort to testing and manually verifying outputs.
- Line 1586: Consider making notation consistent; I suggest going with $d_G$ (resp. $d_v$) instead of Depth(G) (resp. Depth(v)) because line 1809 uses it.
- One thing I am not entirely clear on is how much of what Cybertron’s type system guarantees would actually transfer over to trained transformer models that are architectured according to a correct Cybertron program. The authors claim that “Cybertron allows us to construct transformers with automatic value validity guarantees if the Cybertron code is type-correct.” But how could that be? I would be curious to hear more on this.
- Would I be correct in saying that the “customized BERT models” used in the evaluation are not constructed according to a Cybertron blueprint? It would be very interesting to actually train models architectured according to (or, even better, compiled from) Cybertron programs and see how well they fare. What are the authors’ thoughts on pursuing further research in this direction? Would external functions (that Cybertron itself cannot reason about) pose challenges?

Inexhaustive list of typos:
- Line 49: add space before “demonstrates”
- Line 67: use consistent type style for “clean code principle” (either use italics for all its occurrences or not at all)
- Line 80: remove “Compilers are one of the most challenging programming projects in our era and early C compilers.”
- Line 94: “_T_ o our knowledge”
- Line 149: “... helps ~~to~~ prove complicated operations…”
- Line 208: “... transformers have expanded to ~~include~~ _support_ code analysis and…”
- Line 214: “... type inference, and _type_ checking”
- Line 214: “These features make ~~the Mini-Husky compiler~~ _compiling Mini-Husky_ a representative task…”
- Line 229: “etc_._, ~~called the~~ _forming a_ token stream, ~~then~~ _to be_ parsed into…”
- Line 229: Fix “... into a tree like structure representation of the generation process of the input, finally syntactic and semantic analysis is performed on the tree”
- Line 231: “... we assume _the_ tokenizer has been provided _a_ priori”
- Line 235: “... the AST abstracts away ~~from~~ surface syntax details…”
- Line 240: “... so we defer _it_ to…”
- Line 245: “They are defined ~~in one place~~ _somewhere_ and can be…”
- Line 246: “... curly ~~bracketed~~ _braced_ scope… we only consider curly ~~bracketed~~ _braced_ scope.”
- Line 262: make the 1 in “f1” a subscript
- Line 263: line 4 of the code snippet is a variable def, not a variable use, so variable a is only accessible from line 5
- Line 264: “... is _accessible_ from line 10…”
- Line 264: the fourth instance of the variable a is accessible from within its scope – it is just not actually used
- Line 273: “In general, ~~type is~~ _types are_ essential…”
- Line 279-280: add period after “(3) Type inference” and remove “(4) type checking”
- Line 280: “... ensures that the ~~type~~ _typed_ expressions agree…”
- Line 292: “... the first argument of `f` ~~expects be~~ _is expected to be_ of type…”
- Line 300: “... ~~denoted~~ _denotes_ the type TypeError ~~will~~ _with_ a…”
- Line 313, 315, 367, 442, 1120: “~~codes~~ _code_”
- Line 328: “... because ~~a~~ 64-bit computers…”
- Line 334: “... although they might not _have_ been fully initialized.”
- Line 340: “Therefore, ~~The~~ _the_ end-to-end process…”
- Line 340: “... by a transformer _of O(1) number of heads_, …” and similarly for other such cases involving asymptotic complexities
- Line 342: “... in ~~in~~ Appendix F.”
- Line 373: “... smaller than ~~with~~ _the_ context length…”
- Line 404: fix “What transformers output (possibly in the intermediate layers) is a representation in sequences of vector of sequences of values in these types.”
- Line 405: “... interpreted in this paper _as_ a discrete subset…”
- Line 406: “... construct transformers with ~~an~~ automatic value validity guarantees…”
- Line 416: “... operations that ~~requires~~ _require_ information…”
- Line 434, 435: “~~associate~~ _associative_ recall”
- Line 435: “... _the_ type checking step covers…”
- Line 442: “... which _is_ typically the case …”
- Line 472: missing appendix number in “... in Table 2 in Appendix during…”
- Line 480: “... when both ~~sizes scale up~~ _scale up in size_, …”
- Line 950: “... the single-layer ~~feed-forward~~ _fully-connected_ network…”
- Line 1046: redundant superscript R^dmodel
- Line 1064: should be Definition 7
- Line 1083: “Here’s the BNF _grammar_ of…”
- Line 1277: change to “Thus, using Cybertron one can argue operations _more complicated than simple algorithms_ can be simulated by transformers.”
- Line 1284-1309: perhaps the authors forgot to replace the placeholder code snippets?
- Line 1284, 1291, 1296, 1304: capitalize the starting “in”
- Line 1285-1286: “... certain ~~architecture~~ _architectures_ given that…”
- Line 1398: “... which ~~translates~~ _translate_ directly to…”
- Line 1406: “... If we ~~dont’~~ _don't_ ignore…”
- Line 1514: “.. we can define ~~the local~~ _an option type_ as”?
- Line 1606: redundant “for i = 1, …, n”
- Line 1614: “... Using Multi-Layer ~~Perceptions~~ _Perceptrons_…”
soundness: 2
strengths: While transformer models have been extensively used to compile and generate code, how (well) they proceed with such tasks remains understudied, which is in part due to the significant gap between neural and symbolic methods in terms of the level of abstraction (which is further amplified in the context of compilation, as the authors have identified). Thus, I recognize this paper as an admirable and overall successful shot at the task of characterizing how transformers carry out compilation.

Although the idea of reasoning about neural networks through the lens of symbolic computational models is not new, the work done by the authors to (1) identify suitable symbolic abstractions to interface with components in the transformer architecture and (2) perform formal proofs of their “equivalence” quite significantly outgrows prior work like RASP. This aspect of the paper is also what I find most impressive.

Overall, I find the paper to be original and a meaningful contribution that helps advance our understanding of transformer characteristics on complex reasoning tasks. The quality and clarity of the writing could be improved (see Weaknesses) but for the most part do not pose significant challenges.
summary: This paper presents an attempt to characterize the expressiveness of transformers on compilation tasks (concretely, parsing, symbol resolution, and type analysis). For this purpose, the authors introduce Mini-Husky, a representative C-like programming language that is amenable to compilation, and Cybertron, a programming language in which compilation tasks are expressed in terms of computation graphs, which help symbolically represent transformer components.

Both theoretical and empirical results are presented. Theoretically, the authors prove (1) the feasibility of transformers simulating various Cybertron constructs, (2) that transformers require a logarithmic number of parameters to the input to carry out compilation tasks, and (3) that RNNs require a memory linear to the input on the type checking task. Empirically, the authors demonstrate the exponential divide between transformers and RNNs on type checking using synthetic data.
weaknesses: While the paper is overall coherent, I did find some bits to be unintuitive (due to the order in which concepts are introduced) and even obtuse (due to poor prose). For instance, I would suggest modifying/reordering Section 5.4 to first motivate the use of key abstractions (e.g., computation graphs), and then go over what constitutes types in Cybertron, followed by how such types constrain the use of abstractions and ensure the soundness of propositions (e.g., that there exists a transformer encoder capable of symbol resolution). I was unable to form a fully cohesive mental picture connecting these details until after reading this section a few times and referring to the appendices. I understand that the authors are constrained by the page limit, but I would appreciate it if they could smooth out such readability speedbumps. I would personally cut a significant portion of the first paragraph of Section 5.4, as it largely parrots what has been said in the abstract and introduction.

Related to the above point, it would have been better if the authors provided more intuition for the key abstractions (e.g., computation graphs and function compositions) ahead of time in the main text, leading up to the overview and exposition on the type system. I was only able to adequately grasp their roles after going through much of the appendices.

Other than the aforementioned structural issue, I would have to say that the prose of the paper can be dramatically improved. An inexhaustive list of typos I found is included at the end of the Questions section. While most of them do not impede understanding, there are a few more serious ones that do (e.g., line 405, incorrect examples in Appendix E.1). I would appreciate it if the authors could correct them and do one more pass to double check.

For the most part, I appreciate and enjoy the formal approach. But on the topic of soundness, I would have liked to see a precise specification of Cybertron’s type system and its correctness (via properties like progress and preservation), in addition to the properties stating whether specific constructs expressible in Cybertron can be represented using MLPs/transformers. In my opinion, this is a missing ingredient that is important for an approach akin to interactive theorem proving. For instance, such a specification would clarify which of the two type errors on line 9 of the code snippet in Section 4 would actually occur, blocking the other from occurring (or not, depending on the specification). Presently, I have no way of knowing such behaviors from the paper alone. On the same point, the authors could have further formally specified Cybertron’s semantics operationally/denotationally/etc. to be the most precise, and proved it correct, which is important for such a formal reasoning approach. Same applies to Mini-Husky.

---

confidence: 4
contribution: 4
initial_rating: 5
presentation: 2
questions: ## Technical questions:
**Architecture Choice**: Why focus only on encoder-only transformers? What are the theoretical implications if encoder-decoder or decoder-only architectures were considered? Would they enable additional compiler capabilities? I think the theoretical proof on them would be more meaningful since existing related researches are mostly encoder-decoder or decoder-only, like LLMs. 

**Compiler Output**: The current work focuses on semantic analysis rather than full compilation:
- Could the framework be extended to generate assembly or IR code output?
- Is the limitation to semantic analysis related to the choice of encoder-only models?

**Is Cybertron a DSL or a compiler?** From the code in the supplementary materials and the appendix, I find Cybertron more like a compiler with type system tailored to Mini-Husky rather than a DSL. Investigation on the Cybertron code makes me confused as there is no clear relations to transformers, the main study subject in this paper. Could the authors explain them?

**Additional Compiler Tasks**: Beyond the three investigated tasks (AST construction, symbol resolution, and type analysis), how might the framework extend to other crucial compiler components, for example:
- Translation Correctness: Reasoning about customized structs (size, offset, alignment), Stack space allocation, and Instruction binding, etc?
- Optimizations: Can transformers perform Register allocation, Dead code elimination, Constant propagation, etc?

## My expectations:
This is a strong theoretical paper that makes novel contributions to understanding transformer capabilities in compilation tasks. The integration of programming language theory with transformer analysis is particularly innovative, and the use of type systems to characterize transformer expressive power demonstrates deep expertise in PL and compiler theory and machine learning. However, several aspects of the presentation need significant revision as already illustrated in the weaknesses.
I look forward to seeing these weaknesses addressed and questions explained in the rebuttal phase. If most of them get addressed, I would recommend clear acceptance.
soundness: 2
strengths: This paper is quite novel in using expressive power theory to investigate transformers in compilation tasks, and they map the expressive power of transformers to the type system of Cybertron. The strengths are listed as follows:

- **Novel Theoretical Analysis of Expressive Power**: The paper provides the first formal analysis of transformers' capabilities as compilers, using expressive power theory to investigate their performance on compilation tasks. This moves beyond empirical observations to establish rigorous theoretical foundations.
- **Constructive Proof Methodology**: The authors introduce Cybertron, a domain-specific language (DSL) as an innovative proof vehicle. This allows them to constructively prove transformers can efficiently handle AST construction, symbol resolution, and type analysis, bridging the gap between low-level transformer operations and high-level compiler tasks.
- **Strong Theoretical Results**: The paper proves that under bounded conditions (AST depth and type inference depth), transformers require only logarithmic parameter scaling with input length for several compilation tasks. This provides strong theoretical support for using transformers in compilation, which will be a strong theoretical foundation for existing empirical research findings including but not limited to neural code translators, compilers, and decompilers.
- **Theoretical and Empirical Separation from RNNs**: The authors establish a clear exponential separation between transformers and RNNs specifically in type checking tasks, proving RNNs require linear parameter scaling while transformers need only logarithmic scaling. This theoretical finding is supported by experimental results showing transformers outperform RNNs in type checking tasks, providing practical validation of the framework.
summary: This paper investigates the theoretical capabilities of transformers in performing compilation tasks, specifically focusing on three key aspects:

- Abstract Syntax Tree (AST) construction
- Symbol resolution
- Type analysis

They introduce a simplified Rust-like language called Mini-Husky as their programming language for formal analysis. They prove the availability of encoder-only transformers in these three tasks by a constructive proof of certain transformer components' properties; therefore, they could further use same expressive power components to represent the model. They construct Cybertron, a type-checking compiler that accepts Mini-Husky input and generates type error information. They also prove the expressive power of transformers that surpasses RNNs in type checking subtask.
weaknesses: ## Major Theoretical Weaknesses:
- **Limited Illustration of Cybertron's Proof Mechanism**: The main body of the paper doesn't explain how Cybertron could serve for proving these subtasks that represent transformers clearly. The examples in the appendix are not intuitive for understanding, as they are too implementation-specific. The paper needs revisions on its writing to explain their ideas on how Cybertron is used for proving the capabilities of transformer models. For example, we need at least some detailed minimal end-to-end examples in Mini-Husky for basic statement-level and block-level constructs. I think at least a basic statement-level example, like "a = b + c * d" and a block-level example, like "if(){}" will be needed.
- **Language Design and Classification Issues**: Mini-Husky is more accurately characterized as a Rust-like language rather than C-like. The choice of Rust-like features may be beneficial for type analysis but should be explicitly justified. The language classification needs to be more precise and well-justified.
- **Limited Semantic Generalizability**: From a traditional compiler development view, the semantics cannot be fully presented through BNF grammars, as many language-specific features are configurable and implementation-dependent. For example, the authors limit their Mini-Husky language to avoid any type conversion for their type system's convenience; however, this limit also limits the language's generality. For Mini-Husky-2, which allows type conversion, the proof generated by Cybertron is not valid since we need Cybertron-2 to validate it. I think the authors should clarify this key challenge: semantics is different from syntax/grammar, which is why we need language manuals besides BNF grammars to define a programming language. The current presentation seems to overclaim their capability in semantic handling, as the type system in Cybertron is implementation-dependent on Mini-Husky, therefore not generalizable. Current Cybertron is therefore more like a partial compiler (not generating assembly or IR output currently) with type checking tailored to Mini-Husky rather than an extensible DSL, which makes me confused about its effectiveness on other programming languages with different semantics. Authors are encouraged to clarify what the common parts in PLs are that MiniHusky+Cybertron can prove transformers-capable and what are not and need extra development to prove.

## Empirical and Evaluation Weaknesses:
- **Limited Experimental Validation**: Empirical validation focuses only on type checking comparison with RNNs. Missing evaluation results for AST construction, symbol resolution, and comprehensive type analysis. The lack of practical validation weakens Mini-Husky's contributions.

## Technical Writing Issues
- **Non-standard ICLR template usage**: The template it used is not the newest ICLR-template as it differs significantly with other papers. 
- **Various writing errors**: Redundant sentences(line 079-081), Incorrect indentation( line 049: "Taelin (2023b)demonstrates", line 277-280), Incomplete words(line 053: "such as (missing JavaScript)(Flanagan, 2011) and Rust (Klabnik & Nichols, 2023)", line 094: "(T)o our knowledge").
- **Too long appendix**: Too many code snippets in the appendix, many of them are direct copies of code, which is inappropriate for a premier conference like ICLR. Simplifications and abstractions are needed. Current length in the appendix is too much for any readers to read, including reviewers.

Meta-review: This paper proposes a novel framework for reasoning about whether transformers can represent standard compiler passes such as type inference. They provide a proof language called Cybertron to help formalize these proofs. They also demonstrate gaps between transformers and RNNs at these tasks. A significant issue with this paper is its clarity and its positioning. If the main contribution is the collection of theorems they prove, then the tasks they are studying seem way too complicated to provide useful insights; using simpler languages and analyses would be equally effective while providing more clarity on the nature of the results. This is reflected in concerns raised by the reviewers about the correctness of the claims, whose proofs are too complex to check, even at a high level. If the main contribution is the proof language, Cybertron, then ICLR is likely not the right venue for this paper; a programming languages or formal methods venue might be more appropriate.

Decision: Reject