Algorithmic Capabilities of Random Transformers
Authors: Ziqian Zhong
Jacob Andreas
Venue: NeurIPS 2024 poster (2024)
Keywords: transformer
deep learning
interpretability
capability
emergence
randomness
language models
Primary area: interpretability_and_explainability
TL;DR: Randomly initialized transformers may be more powerful than you think!

Abstract: Trained transformer models have been found to implement interpretable procedures for tasks like arithmetic and associative recall, but little is understood about how the circuits that implement these procedures originate during training. To what extent do they depend on the supervisory signal provided to models, and to what extent are they attributable to behavior already present in models at the beginning of training? To investigate these questions, we investigate what functions can be learned by randomly initialized transformers in which only the embedding layers are optimized, so that the only input--output mappings learnable from data are those already implemented (up to a choice of encoding scheme) by the randomly initialized model. We find that these random transformers can perform a wide range of meaningful algorithmic tasks, including modular arithmetic, in-weights and in-context associative recall, decimal addition, parenthesis balancing, and even some aspects of natural language text generation. Our results indicate that some algorithmic capabilities are present in transformers (and accessible via appropriately structured inputs) even before these models are trained.

Algorithmic Capabilities of Random Transformers
Ziqian Zhong, Jacob Andreas
Massachusetts Institute of Technology {ziqianz, jda) (dmi@mi edd
Abstract
Trained transformer models have been found to implement interpretable procedures for tasks like arithmetic and associative recall, but little is understood about how the circuits that implement these procedures originate during training. To what extent do they depend on the supervisory signal provided to models, and to what extent are they attributable to behavior already present in models the beginning of training? To investigate these questions, we investigate what functions can be learned by randomly initialized transformers in which only the embedding layers are optimized, so that the only input-output mappings learnable from data are those already implemented (up to a choice of encoding scheme) by the randomly initialized model. We find that these random transformers can perform wide range of meaningful algorithmic tasks, including modular arithmetic, in-weights and in-tentext associative recall, decimal addition, parenthesis balancing, and even some aspects natural language text generation. Our results indicate that some algorithmic capabilities are present in transformers (and accessible via appropriately structured inputs) even before these models are trained
Introduction
A large body of recent work has demonstrated the effectiveness of transformer language models (LMs) [46] on general sequence-modeling tasks. Transformers seem to be especially well-suited (relative other flexible neural models) at problems involving numerical reasoning 4 24 33).
string manipulation (28) and various forms of in-context learning 7
25
Why is this the case?
One possibility is that some aspect of the transformer architecture makes these behaviors easy to learn. Under this hypothesis, transformer models do not implement any useful functionality when initialized; however, their loss landscape is structured such that they can be (computation- and sample-) efficiently optimized for behaviors of interest. But another possibility is that-because of intrinsic properties of the transformer architecture and parameter initialization schemes-thes capabilities are already implemented in some fashion even in randomly initialized models.
To disentangle these possibilities, we investigate the behavior of randomly initialized transformer models which only the embedding layers are optimized, leaving all other model-interall parameters fixed. If such embedding-oni training is successful, it implies that the randomly initialized model's behavior on some subspace already corresponds to the input-output mapping interest, up to choice of encoding scheme-in other words, that the randomly initialized model can already perform target task, and suffices to find an encoding of inputs and outputs that induces the target behavior.
In experiments on seven tasks, we find that embedding-one training yields accurate models for diverse set of problems spanning arithmetic, associative recall, and sequence generation- some cases substantially outperforming similarly trained recurrent models. Remarkably, transformer language models trained in this fashion can even produce grammatical (though largely nonsensical)
'oode is available at httpp////gtthaacooooo//////////t
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

51
Trained
Needle iin hhystackk
addition
Aerdew suben
4dd exushere Aagh strags
Unembedding
markor
Isput: QZ
Outpat: 27
Tegutt a c.bb
Tepan 3..17
Randomly intielized
Oarpat:
Outgutt 1
Circuit imiiation
Attention
Miski dkotslatiion
reall rexicer maayfooee
Projection
Moduler arthmmtic
Parenthesis belancing
Ingutt ade cca oth
Outpon xh
Gives cangeet
Clead y' right los iolanced
Trained
Language modeling
Embeddling
Eujh
Inpui: 139 180 [for
Chrppt::
Imput: Mary cooked
Outgut:
150
100
Figure I: Overview of problem setup. A: Modeling approach. We initialize transformers randomly, then optimize only their input and output embedding layers on a dataset of interest. We find that these random transformers can be successfully trained to perform a diverse set of human-meaningfin meaningful tasks. B: Task set. We evaluate the effectiveness of random transformers on of model problems involving arithmetic and memorization, well as modeling of natural language text.
natural language text. We explain these results by showing that embedding oonly training steers both inputs and model-internal representations into low-dimensional subspaces on which the model implements the target computation, a phenomenon we call "subspace selection". Embedding-onl training is most successful when the target computation can be performed in subspace that is low-dimensional relative to the ambient dimension of the model's hidden representations.
These findings build on long line of research aimed at understanding the effectiveness of deep networks in terms of their behavior at initialization-e. showing that random convolutional networks high-quality feature extractors 3| g or that overparameterized networks can be pruned down to sparse "lottery ticket" subnetworks that implement the correct behavior [16] 53 39 M.] But in contrast to past work, the solutions found by embedding-on!l training involve algorithmic computation rather than feature extraction, performed in low-dimensional subspaces but not by sparse sub-networks.
Even more generally, our results show that pruning and optimization are not always necessary to surface useful capabilities at least in transformers, some capabilities are available as soon as models are initialized, requiring only a learned encoding of inputs. This in turn suggests that it may be possible to partially understand the effectiveness of transformers simply by understanding their behavior initialization.
Our work also has implications for research on circuit-level interpretability of transformers and other neural models: if even random models can perform structured, algorithmic tasks, then attempts to understand models by directly inspecting parameter matrices and not their behavior on natural data distributions may be fundamentally limited in their ability characterize learned behaviors.
Background and Related Work
Random feature extractors Random deep convolutional networks are highly effective visual feature extractors even without training. Jarrett et al. [23] first discovered that linearly combining fea- tures from a randomly initialized one-layer convolutional network achieved comparable performance to fully trained networks for downstream vision tasks. Saxe et al. [40] showed that performance improvements from training is relatively minor comparing to architectural changes. In this work, we expanded the discussion to language models and demonstrated that training embeddings alone is sufficient to succeed in many tasks, highlighting the strong inductive bias transformer architectures.
Neural reprogramming Neural reprogramming aims to repurpose existing neural networks for novel tasks via simple transformation layers. This technique was first purposed by Elsayed et al. [5] as a way to exploit trained neural network served by existing providers, and it was later used as a resource-efficient domain-transfer technique [5 49] In our work, we showed that in addition to neural networks trained for other tasks, even randomly initialized neural networks can be reprogrammed to achieve non- trivtriiil performance.

---

Sparse sub-networks and lottery tickets The lottery ticket hypothesis was first proposed by Frankle and Carbin [T6]: sundomly-initialize dense neural network contains subnetworks, the winning fickets, that when trained in isolation can match the performance of the original network. Zhou et al. [53] and Ramanujan
(39 strengthened the hypothesis by discovering pruned subnetworks that achieve comparable accuracy of the trained full network within untrained, randomly initialized networks winning tickets do not even need to be trained. The hypothesis also holds in transformers [ 44). Similar to the hypothesis, our work also focuses the models' capabilities at initialization, but we showed that these capabilities can be surfaced without any pruning.
Interpreting neural circuits Many efforts have been dedicated to the interpretation of neural networks. On the arithmetic task we study this paper, Nanda al. [31] and Zhong al. [52] described two different mechanisms in transformers on modular addition; Quirke and Barez [37 performed detailed mechanistic analysis for one-layer transformers trained on decimal addition. These studies provide insights into possible mechanisms transformers might employ to solve these tasks. With theoretical analysis, Wen et al. [47] proved that on the bounded Dyck task, the attention patterns and weights of neural circuits could be quite arbitrary, which we confirm in this work.
Reservoir computing Reservoir computing is framework for computation. In the diagram, blackbox reservoir receives data and updates its inner states there upon. A simple readout mechanism then trained to map its inner states the desired output. The reservior is generally kept untrained and only the readout part is trained. Under our notations, we can interpret the paradigm as training
only the unembedding part of random neural networks. See Benjamin al. [42) for a general overview for reservoir computing and Mantas et al. [29] for a survey on its applications on recurrent neural networks.
3 Setup
Models We study the behavior of decoder-only transformer language models. these models, inputs x (represented as sequence of token IDs) are first assigned vector embeddings h(0) (x)) via embedding layer E. These embeddings are then passed through a series of intermediate layers F(), F(),F() F(2) F(m) so that (i)) = F (1(-1)), with each (x) computing a hidden
representation (0) via a transformation:
h = ( ()(t-1)) = OF (SelfAn ( (M(1-1))
where FFN, SelfAtt are feed-forwart and causal self-attention modules as in Radford et al. (38 (layer norms are omitted for simplicity). The final activation ((()) is mapped by unembedding layer to distribution over next tokens.
To encode information about the ordering of input tokens, we implement the embedding layer E using two matrices: a token embedding matrix Ejkkn and positional embedding matrix Epux- For an input = [21, 22, ... NnI, we first calculate the initial activations
()) E( .I,)) Eooken [x1] Eps [1], Eukkeu [22] + Ep. Eroken [I,]] Epos [r]]].
Similarly, the unembedding layer is parameterized by single matrix, and model predictions have the form:
p(zn+1 Zi...ni E, F,U) & softmax (Ub(TT) [In+i]:
where (in a slight abuse of notation) F,, and U denote embedding, intermediate, and unembedding parameters respectively.
In terms of parameters, let the hidden dimension be d, the number of layers be m, the vocabulary size be u and the maximum context length be n, the embedding layers have [((n + v)d) parameters as matrix Euken and U have shape v and matrix Epos has shape n d, while the full network has an extra 2(md²) parameters.
Initialization Models are trained via gradient descent from some random initial parameterization. Following Radford et al. (38), parameters of feed-forward layers are initialized by sampling from isotropic Gaussians with mean 0 and standard deviation 0.02/ /2n. All the other weight matrices are initialized with 0-mean Gaussians with standard deviation 0.02. The affine transformations in layer normalizations are initialized as identity.
3

---

Training In this work, we examine language models with frozen intermediate layers, which we call random transformers. In these models, we fix the randomly chosen parameters intermediate layers. and train only the embedding layer Fl and unembedding layer U. Our experiments thus compare:
Full Training:
arg min B.F.U
Σ
- log p(In+1 Ti--n: E,
6,020
Enbedding-Only Training:
arg min E,U
- log ((gg((aa1 Ti.-ni E, F,U)
2,920
where the arg min is computed approximately via mini-batch stochastic gradient descent.
4
Random Transformers Can Perform Simple Algorithmic Tasks
Can random transformers be steered to perform meaningful tasks by optimizing only input and output tokens' embeddings? We begin by evaluating four widely-studied tasks that serve as toy models of important behaviors in large-scale LMs.
4.1 Tasks
Modular Addition This task evaluates models' ability perform integer addition under fixed prime modulus p = 199. Models receive sequence of input tokens (a, bj for a, b E [0,p p -1] and must compute (a + b) mod p. When wee-taaramtterized models are trained perform this task, grokking (a long period of memorization followed by an abrupt transition to generalization (36]) is typically observed [26] [8] Neural sequence models of different kinds have been found to implement two interpretable algorithms, sometimes referred to as the "Clock" 31 and "Pizza" [52 when
trained perform this task.
Weedle-in-a-Haystanr This task evaluates models' abilities to process long input sequences 4 In the variant we study, models receive as input sequence of form [m1, C1, m2, C mgg Cj.y myy Here, m., m2, my are distinct markers (k < 30) and c 'ss are corresponding values. The input ends with a marker ma (u E [1, k),, and models must search for the previous occurrence of that marker in the input sequence and output the corresponding Cu. Specific circuits like induction heads are often observed in models that perform this task 34
Decimal Addition This task evaluates models' ability to perform arithmetic operations distributed over sequences of multiple input tokens-in this case, addition of two equal-length numbers repre- sented as digit sequences in base 10. The order of digits of both numbers and the results are reversed to simplify the task. For example, the task 39+71=110 encoded as a pair with input output 0 1. We use 10-digit numbers in our setup. Past work has found that fully trained models
7 and
can reliably learn some versions of this task 32 51 43
Parenthesis Balancing (Dyck Recognition) In this task, models are presented with sequence of parentheses, and must predict whether they are balanced-ia. i.e. whether the sequence contain an equal number of opening and closing parentheses, and within every prefix, the number of closing parentheses is no greater than the opening parentheses. Such sequences are also called Dyck sequences, and have been widely studied in language models because of their connection context-frre models of natural language syntax [50 [47]. Note that this task has a vocabulary of size 4 (two parentheses and two optimized by embedding only training. In our
labels), so only very small number of parameters setup, the input parenthesis sequences have lengths at most 60.
For the modular addition task, we partition the full set of well-formed onput-output pairs into fixed train/test split; for the other problems, we pre-generate a fixed test set but randomly generate new pairs for each training batch. Additional details may be found in Appendix D.I
4.2 Results
Results are shown in Table Here we compare random transformers with a hidden size of 1024 to fully trained models with hidden sizes of 16 and 1024. For reference, also compare to (fully

---

Task
Random 1024
Random 16
Normal 1024
Normal 16
LSTM 1024
Modular Addition 100.0%
1.3%
100.0%
97.2%
100.0%
Boedle-i--a-Hastarr 100.0%
7.5%
100.0%
12.0%
99.5%
Decimal Addition
100.0%
26.6%
100.0%
67.5%
53.0%
Parenthesis Balancing
100.0%
87.3%
92.3%
100.0%
100.0%
Table 1: Test accuracy of fully trained and random transformers, as well as fully trained LSTMs, on algorithmic tasks. Denoted numbers (1024 and 16) hidden sizes; results median over 10 random restarts. Random models with only trained embeddings reliably perform all four tasks, and even outperform fully trained LSTMs. See Appendix for the accuracy curve on multiple hidden sizes.
Task
U only
only
Esoken & only
Modular Addition (Train)
47.9%
68.3%
100.0%
Modular Addition (Test)
0.4%
1.2%
100.0%
Needle-in-a- -at-s-Hayttack
17.7%
100.0%
98.5%
Decimal Addition
27.3%
100.0%
48.5%
Parenthesis Balancing
92.3%
100.0%
100.0%
Table Accuracy of embedding-only training with additional parameters fixed: optimizing only the unembedding layer, only the embedding layer, or only non-positional embeddings. Hidden sizes are all 1024; results are median over 10 random restarts. All three embedding matrices must optimized for models to reliably complete all tasks.
trained) LSTM, recurrent neural sequence model (22]. All models have two hidden layers, and all results are aggregated across ten random initializations.
Random transformers learn to perform all four tasks Random transformers with trained em- beddings and unembeddings obtain perfect accuracy on all four tasks consistently across restarts sometimes outperforming fully trained recurrent networks (Table These results thus point toward the role of transformer--pecific inductive bias in the effectiveness of embedding-only training.
In general, embedding and unembedding parameters must both be trained To further identify which model components must be optimized to obtain these results, we consider several variants of embedding-only training: (a) leaving both token and positional embeddings fixed (so only the unembedding is trained); (b) leaving the unembedding layer fixed (so only the embedding is trained); and (c) leaving positional embeddings fixed (so token embeddings and the unembedding is trained). All variants fail to reach perfect accuracy on at least one task. Notably, the variant that only trains the unembedding is unable reach near-perfect accuracy on any task.
Results are shown in Table 2
Random transformers exhibit interpretable attention patterns closer examination of the trained random models reveals similar mechanistic behaviors to their fully trained counterparts, For example, we observe attention patterns similar to "induction heads" 34 previously described fully trained models for associative recall tasks (Figure
Random transformers use structured embeddings In the modular addition task, learned em- beddings form circles low-dimensional subspaces, another phenomenon observed in fully trained models for these tasks [26] 31] (Fig. B). To better understand similarities between these models and their fully trained counterparts, we also computed the distunce irrelevance and gradient symmetricity metrics described by Zhong et al. (52) for distinguishing between networks that perform modular arithmetic via the "Clock" or "Pizza" algorithm. We find a gradient symmetricity of 0.88 and distance irrelevance of 0.88, consistent with Clock-like solution.
5

---

Layer
Layer
1.0
1.0
Tagget Telen
01
0.8
0.6
Siiee
02
0.2
0.2
2-
2-
-03
2
3
Source Tiken
Source Token
-0.2 0.0
0.2
Figure Attention patterns observed in 2-layer 1024-width random transformer trained on the needle-in-a-haystar input sequence is b 2 d 4 b. The layer-1 head is used by values to attend to their markers, and the layer-2 head is used by the query to attend to its associated value.
Figure 3: Circular embed-
task. The
ding observed in random trans- former on modular addition. We plot the projection of the embedding matrix onto its first and third principal compo- nents, with tokens colored ac- cording their numeric value.
Transformer Accuracy
Memorized bits
Trainable parameters
Bits per parameter
Normal
80.54%
1900177 106876
659584
Random
4.53%
262784
0.41
Table Comparison of normal and random transformer in the memorization task.
Random Transformers Can Memorize and Generate Structured Sequences
The preceding experiments evaluated the ability of random transformers implement single, highly structured input-output mappings. Can these models scale to more challenging tasks, involving memorization of arbitrary associations free-form text generation?
5.1 Memorization
Past work by Allen-Zhu and Li 2 has found that fully trained transformers can store roughly two bits of input per parameter. We investigate whether similar scaling trend holds for random transformers. We study a simple memorization task in which we generate random mapping from a two-integer key to one-integer value, with all integers ranging from 1 512. Such a function requires bits per input-output mapping to represent (log, 512 = 9), and may be defined for up to 262144 (= 512?) values. Unlike the algorithmic tasks above, here the learned function must be fully specified by embeddings rather than the pre-trained model, and these experiments mainly evaluate how efficiently information can be stored these embeddings.
We evaluate fully trained and random transformers of width 128 and layers (Table S sure success using exact-match metric- an input-output pair is considered to be successfully memorized if the output token assigned highest probability by the model matches the training data. Fully trained transformers memorized 80% of training examples, stored 2.9 bits per parameter, while random transformers memorized only 5% of examples, corresponding to 0.4 bits per trainable parameter.
We mea-
5.2 Language Modeling
Modeling natural language requires both memorization of arbitrary associations (e.g. between words and their parts of speech, as in Section (.1)), and structured sequence generation procedures (e.g. to enforce subject-verb agreement and close quotation marks, as in Section 4). Can random transformers make any headway this task?
We train models on the TinyStories dataset, a collection of GPT-3.5 and GPT-4 [4 which have been shown induce fluent text generation when used train
stories generated by

---

4.0
3.76
Evaluation Cross-Enin Entropy Loss
3.74
3.64
3.55
3.5
3.63
3.52
3.41
3.33
3.0
90
2.72
2.5
2.43
2.64
2.25
2.0
Normal, 2 layers
2.00
Normal, 4 layers
1.70
1.5
Random, layers
1.54
.335
Random, 4 layers
1.0
64
256
512
Network Width
Figure 4: Language modeling performances (measured in cross-entropy loss or equivalently log perplexity, lower better) for fully trained and random transformers. Comparatively large hidden sizes are needed for random models to match the performance of fully trained models.
Once upon time, there was little hoy named Max. Max loved play with his toy blocks. He had blocks of all colors and shapes. Max liked build tall towers and big castles. One day, Max was playing with his blocks in his room. He built the tallest tower he had over made. was so tall that it almost touched the ceiling! Max was very proud of his tower. Suddenly,
Reference (GPT-4o): Suddenly, Max's cat, Whiskers, ran into the room. Whiskers saw the tall tower and thought it fun thing to play with. He jumped up and knocked the tower The blocks fell all over floor. Max was very sad. He worked so hard to build the tower, and now it was gone.
Suddenly, Max's little sister came into the room. She wanted to play with Max's blocks too. But Max didn't want to share. He wanted to keep playing with his blocks. His sister started to cry and Max didn't 't understand why his sister was so upset. He thought he was just playing with them. So, he was so happy that he hugged his sister his sister. They played together and had lot fun. The end.
Fully Trained Transformer:
his room and looked for the blocks. After while, he found them under the bed. Max
Random Transformer (Completion I): ... Suddenly, Max started to blow. Max saw from the tower. Max's tower was very high and strong. Max wanted to play with his blocks. Max was very proud of himself for being so helpful. Max decided to take care of his tower and his tower. Max was so happy that he had done. Max wanted to keep himself. He had to be much fun and proud of himself. Max was happy be able help. Max able of himself. Max was happy to have such a good tower and could it.
noise coming
proud the tower and help his tower. Max
Random Transformer (Completion 2): ... Suddenly, Max's tower fell down landed on his floor. Max fell down and hurt his knee. Max cried and came to him. Max was very sad and didn't 't want to get hurt. Max's 's feelings. Max didn't want to get away. Max just wanted make it so badly! Max tried to take it break. Max put him back the floor. Max tried make up but Max didn't know what to do. Max was wrong. Max said, "Don't worry, Max. Max are very and Max. Max to play with Max and Max. Max was very sad. Max loved to play with his friends and Max played together and had lots of fun. Max played together all day. Max were happy that Max learned that sharing is caring. Max learned that being selfish and always had Iearned that sometimes things can share and others can make others happy again.
Max didn't it want to share
Figure 5: Sample completion generated by fully trained and random 5 512-width 2-layer transformers. While random models produce less coherent than fully trained models, they nonetheless generate text that is largely grammatical topically appropriate.
smaller models. As in previous sections, we evaluate both embedding and full training with 2- and 4-layer transformers with various hidden sizes. Scaling curves are shown in Fig. 4 Fully trained models obtain cross-entropy loss of 1.35, on par with the results reported by Eldan and Li [14]. Our trained random transformer with 512 width and -00 trainable parameters achieved a cross-entropy loss of 2.64, roughly on with the fully trained ones with 32 width and only ~0.7M trainable parameters. Moreover, adding additional hidden layers does not appear to improve performance verformance-22layy 2-layer random transformers in fact achieve better losses than 4-layer models.
7

---

Example outputs sampled from these models (on a newly generated prompt) are shown in Fig. S Even though random models obtain significantly worse perplexity than fully trained models, they could still perform several key sub-tasks needed for language generation: generated sentences are generally grammatical, topically coherent with the prompt, correctly resolve some long-distance dependencies (e.g. references to the name Max) and perhaps even high-level narrative structure.
6 Random Transformers Operate in Low-Dimensional Subspaces
Can we explain the success of random transformers in the tasks studied above? In this section, we present evidence that embedding-onie training steers the hidden computation in transformers into low-dimensional subspaces in which target functions are already implemented. We term this phenomenon subspace selection, and show that it distinct from sparsification, as these subspaces distributed across neurons.
In Section 6.1 we measured fraction of activation variance explained by top principal components in various tasks. For algorithmic tasks, we show that both normal and random transformers work in low-dimensional subspaces, which are sufficient for solving these tasks (Appendix FF. However, for language modeling and memorization, the random transformers displayed more subspace selection compared to the fully trained ones, and as a result, they attained lower performances. In Section 6.22 constructed a task that explicitly requires operating high-dimensional spaces, circuit imitation, and indeed, the random transformers exhibit significant performance gap compared to normal transformers,
6.1 Low-Dimensional Hidden Representations in Algorithmic and Memorization Tasks
To characterize the geometry random transformers' internal representations, we present models (trained for all previously described tasks) with set of randomly chosen inputs and collect their embeddings and hidden representations of these inputs at different layers. Using these representations, perform analyses: (1) the fraction of variance explained by the top principal components of these hidden representations (which will be large if representations lie in a low-dimensional subspace), and (2) the fraction of variance explained by the most variable entries in hidden state vectors, or neurons (which will be large if computation is confined to sparse sub-network).
Both fully trained and random transformers exhibit subspace selection but not sparsification (Table top) in the four algorithmic tasks. In Appendix [F] we show that this behavior is expected, insofar as all four algorithmic tasks can be solved by shallow transformer-lic like circuits that operate in low- dimensional subspaces. On memorization and language modeling tasks, random transformers become much more concentrated on small subspace than fully trained transformers, thus using lower effective dimension (Table bottom and Table 5). In the language modeling task, more than 30% of variance in hidden representations is explained by 10 components.
6.2 Subspace Selection in Circuit Imitation
To provide another window into these results, we characterize how large the hidden representations of random model must be for it simulate random circuit that operates in low-dimensional subspace.
To do so, first generate a small, random targer transformer associated with distribution over strings p. then perform embedding onllyng--nlyylioo training in a different, randomly initialized transformer to simulate its behavior some domain of interest by minimizing:
arg min Ex (KI(((( x)) || p( F,F,U) E,U
To construct target models, we begin with the same initialization scheme described Section then we scale the query and key parameters in the attention mechanism by factor of 10, and and the feed forward weights and biases by factor of 20. We also scale the final projection layer by 100/ 100/v /witth. (This initialization scheme increases variability of attention patterns and target model predictions across random restarts; see Appendix D.2.2 for additional discussion.)
8

---

Task and Transformer Type
Principal Component Basis
Neuron Basis
Task
Model
Emb
L1
1,2
Emb
L1
1.2
Normal 42.0%
21.5%
13.8%
3.8%
1.6%
3.4%
Modular Addition
Random
72.9%
63.6%
44.7%
2.8%
3.3%
2.9%
Normal 45.3%
87.0%
87.3%
1.7%
3.3%
2.6%
Multi-digit Addition
Random
55.1%
72.7%
63.5%
2.0%
3.9%
2.8%
Normal 35.5%
83.5%
47.7%
1.5%
5.2%
2.8%
Neeyle-i---Haystackk
Random
31.3%
30.0%
21.5%
1.8%
1.8%
1.6%
Normal 72.0%
99.4%
98.2%
2.9%
7.8%
18.0%
Balanced Parentheses
Random
74.9%
85.8%
80.9%
4.9%
4.0%
3.7%
Normal 15.0%
25.3%
23,4%
10.2%
12.2%
10.5%
Memorization
Random 27.5%
27.5%
24.7%
9.9%
9.8%
9.7%
Table 4: Median explained variance from top 10 directions under principal and neuron basis. Ac- tivations after embedding (Emb), layer 1 (LI) and layer 2 (L2) are collected from multiple trained 2-layer models of width 1024 and 128 (for memorization). Normal transformers are fully trained while Random transformers have only embedding and unembedding layers trained, in previous experiments. Across tasks, a large fraction variance in models' hidden representations is explained by small number of principal components, but these components do not appear to be aligned to individual neurons or sparse sub-networks.
Task and Transformer Type
Layer
Task
Model
Emb
L,2
L44
Principal Component Basis
Normal 29.5%
27.3% 30.2%
24.3% 31.8%
23.2%
17.6%
Language Modeling
Random 43.0%
32.1% %
31.7%
Neuron Basis
Normal 8.6%
16.4%
14.7%
13.9%
5.9%
Random 3.3%
2.9%
2.8%
2.9%
2.9%
Table 5: Median explained variance from top 10 directions under principal and neuron basis for language modeling task. Activations after embedding (Emb) and after every layer (L.1, 1.2, 1.3, 1.4) collected from trained 4-layer models of width 512. As above, substantial fraction of variance is explained by small number of principal components, especially in random transformers.
We evaluate fully trained and random transformers' ability to fit the target distribution for target models with a 512-token vocabulary, three layers, two attention heads, and varying hidden dimensions. Training inputs consist of 40-token sequences generated uniformly at random.
Results are shown in Fig. In general, random transformers can only match the behavior of shallower (3 vs 1) and or significantly narrower (512 vs 128) models, with sharp increase in error moving from 12 > 16 > 32-dimensional models, suggesting that random transformers may only able to learn computations that can be performed in lower-dimensional subspaces.
Discussion
We have shown that transformer sequence models can accomplish a variety of meaningful tasks when only their embedding layers are optimized. For tasks involving memorization, these results show that much of models' "knowledge" can be encapsulated by input embeddings rather than models' internal parameters. For more algorithmic tasks like arithmetic and parenthesis balancing, which require relatively sophisticated circuits to perform, our experiments show that versions these circuits can be accessed in random transformers (but not LSTM sequence models) simply by constructing appropriate input and output embeddings that confine models' internal states to low low-dimensional subspaces in which these tasks are performed.

---

0.8
10a
Divergence Evaluation Set
Normal, 3-layer, 512-width
Normal, 3-layer, 512-width
0.7
Normal, 1-layer. 128 2ihh
Normal, 1-layer, 128-width
Divergence Evaluation
0.6
Random, 3-layer. 512-width
10")-
Random, 3-layer, 512-width
Random, 1 layer. 512 width
Random, layer, 512 width
0.4
10
0.3
10-2-
0.2
10
0.0
12
128
Target Transformer Width
Target Transformer Width
Figure 6: Kullback-Leibler divergence of circuit imitation with fully trained and random transformers (the lower the better). Both plots show the same set of results with different scales (linear and log) on the vertical axis.
However, experiments have also highlighted several important differences between embedding- only and fully trained models, especially with regard to their parameter efficiency and information capacity. This paper leaves open the question of how computation in embedding to fully trained ones e.g. whether, during full training, the mechanisms we have discovered here evolve gradually into their fully trained forms, whether fully trained models entirely different pathways 10].
models relates
We anticipate that these random transformers will also provide interesting new test-bed for interpretability research, and future work might investigate how learned feature codebooks [12 and automated neuron labeling procedures [21 5 33 behave when applied to these models. Even more generally, these results motivate a closer study of the behavior of untrained models as source of insight into differences between, and improvements upon, existing neural model architectures.
Acknowledgement
We would like to thank MIT SuperCloud for computational resources and Mingyang Deng for valuable discussions.
References
[1] Ekin Akyürek, Bailin Wang, Yoon Kim, and Jacob Andreas. In-context language learning: Arhitectures and algorithms. arXiv preprint arXiv:2401. 12973, 2024.
[2] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 3.3, knowledge capacity scaling laws. arXiv preprint arXiv:2404.054005 2024.
[3] Ehsan Amid, Rohan Anil, Wojciech Kotlowski, and Manfred K Warmuth. Learning from randomly initialized neural network features. arXiv preprint arXiv:2202.06433, 2022.
[4] Anthropic. Long context prompting for Claude 2.1, 2023. URL homm/news/cllaueee211prropop
[5] Steven Bills, Nick Cammarata, Dan Mossing, Henk Tillman, Leo Gao, Gabriel Goh, Ilya Sutskever, Jan Leike, Jeff Wu, and William Saunders. Language models can ex- plain neurons in language models. OpenAI, 2023. URL httpps://openai.comm medeells-car--eplaair-eeeeooos explainn-nurons-iinne in- Language Language-mmeeess/
language-moded models-cam can-
[6] Trenton Bricken, Adly Templeton, Joshua Batson, Brian Chen, Adam Jermyn, Tom Con- erly, Nick Turner, Cem Anil, Carson Denison, Amanda Askell, Robert Lasenby, Yifan Wu, Shauna Kravec, Nicholas Schiefer, Tim Maxwell, Nicholas Joseph, Zac HatfieldDoddss, Alex Tamkin, Karina Nguyen, Brayden MeLean, Josiah Burke, Tristan Hume, Shan Carter, Tom Henighan, and Christopher Olah. Towards monosemanticity: Decomposing language
10

---

models with dictionary learning. Transformer Circuits Thread, 2023. https//transformer (rculisspu2220333mmmommaaaaaeeee heattttee-eaauurssnnxx..mtmt
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877711011, 2020.
[8] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In Seventh International Conference Learning Representations, pages 1-17, 2019.
[9] Devendra Singh Chaplot, Kanthashree Mysore Sathyendra, Rama Kumar Pasumarthi, Dheeraj Rajagopal, and Ruslan Salakhutdinov. Gated-attention architectures for task-oriented language grounding. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 201 8.
[10] Angelica Chen, Ravid Schwartz-Ziv, Kyunghyun Cho, Matthew L. Leavitt, and Naomi Saphra. Sudden drops in the loss: Syntax acquisition, phase transitions, and simplicity bias in mlms. arXiv preprint arXiv:2309.07311 2023.
[11] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained BERT networks. Advances in neural information processing systems, 33:15834-15846 2020.
[12] Hoagy Cunningham, Aidan Ewart, Logan Riggs, Robert Huben, and Lee Sharkey. Sparse autoen- coders find highly interpretable features in language models. arXiv preprint arXiv:2309.08600 2023.
[13] Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al. Neural networks and the chomsky hierarchy. arXiv preprint arXiv:2207.02060 000099 2022.
[14] Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english? arXiv preprint arXiv:2305.07759, 2023.
[15] Gamaleldin F Elsayed, Ian Goodfellow, and Jascha Sohl-Dickstein. Adversarial reprogramming of neural networks. In Seventh International Conference on Leurning Representations, 2019.
[16] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018
[17] Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30599 2022.
[18] Andrey Gromov. Grokking modular arithmetic. arXiv preprint arXiv:2301.0267> 2023.
[19] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprini urXiv:23/2.00753 2023.
[20] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). arXiv preprint 1rXiv:1606.08415. 2016.
[21] Evan Hernandez, Sarah Schwettmann, David Bau, Teona Bagashvili, Antonio Torralba, and Ja- cob Andreas. Natural language descriptions of deep visual features. In International Conference on Learning Representations, 2021.
[22] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
[23] Kevin Jarrett, Koray Kavukcuoglu, Marc' Aurelio Ranzato, and Yann LeCun. What is the best multi-stage architecture for object recognition? In 2009 IEEE 12th international conference on computer vision, pages 2146-2153 IEEE, 2009.

---

[24] Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, al. Solving quantitative reasoning problems with language models. Advances in Neural Information Processing Systems, 35:3843-3857 2022.
[25] Yingeong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Trans- formers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pages 19565-19594, PMLR, 2023.
[26] Ziming Liu, Ouail Kitouni, Niklas S Nolte, Eric Michaud, Max Tegmark, and Mike Williams. Towards understanding grokking: An effective theory of representation learning, Advances in Neural Information Processing Systems, 35:34651-34663 2022.
[27] Nya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05001, 2017.
[28] Cedric Lothritz, Kevin Allix, Lisa Veiber, Jacques Klein, and Tegawendé François D Assise Bissyande. Evaluating pretrained transformer-based models on the task of fine-grained named entity recognition. In 28th International Conference on Computational Linguistics, 2020.
[29] Mantas Lukoševičius and Herbert Jaeger. Reservoir computing approaches to recurrent neural network training. Computer science review, 3(3): (()):1271199) 2009.
[30] Arindam Mitra, Hamed Khanpour, Corby Rosset, and Ahmed Awadallah. Orca-Math: Unlock- ing the potential of SLMs in grade school math. arXiv preprint arXiv:2402.14830, 2024.
[31] Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability.. In International Conference Learning Representations, 2023.
[32] Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102. 13019, 2021.
[33] Tuomas Oikarinen and Tsui-Wei Weng. Clip-dissect: Automatic description of neuron repre- sentations in deep vision networks. In International Conference on Learning Representations, 2023.
[34] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209. /195, 2022.
[35] Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, al. Rwkv: Reinventing mns for the transformer era. arXiv preprint arXiv:2305.
2023.
[36] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gen- eralization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177 2022.
[37] Philip Quirke and Fazl Barez. Understanding addition in transformers. arXiv preprint arX1v:2310.13121, 2023.
[38] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 188)9, 2019.
[39] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in randomly weighted neural network? In Proceedings of the JEEE/CVF conference on computer vision and pattern recognition, pages 11893-11902, 2020.
[40] Andrew M Saxe, Pang Wei Koh, Zhenghao Chen, Maneesh Bhand, Bipin Suresh, and Andrew Ng. On random weights and unsupervised feature learning. In ICML, volume 2, page 6, 2011.
[41] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2018.
12

---

[42] Benjamin Schrauwen, David Verstraeten, and Jan Van Campenhout, An overview of reservoir computing: theory, applications and implementations. Proceedings of the 15th european symposium on artificial neural networks. p. 471-482 2007, pages 471 4722 2007.
[43] Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li, and Yi Zhang. Positional description matters for transformers arithmetic. arXiv preprint arXiv:2311. 147737,, 2023.
[44] Mingjie Sun, Zhuang Liu, Anna Bair, and Zico Kolter. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306.11695, 2023.
[45] Yun-Yun Tsai, Pin- Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Repro- gramming black-box machine learning models with scarce data and limited resources, In International Conference on Machine Learning, pages 9614-9624, PMLR, 2020.
[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[47] Kaiyue Wen, Yuchen Li, Bingbin Liu, and Andrej Risteski. Transformers are uninterpretable with myopic methods: case study with bounded dyck grammars. Advances in Neural Information Processing Systems, 36, 2024.
[48] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transform- ers: State-of-the-art natural language processing. arXiv preprint 1XXv.0991000771 2019.
[49] Chao-Han Huck Yang, Yun-Yun Tsai, and Pin- Yu Chen. Voice2series: Reprogramming acoustic models for time series classification. In International conference on machine learning, pages 1 11808-118 1819. PMLR, 2021.
[50] Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages -7770- 2021.
[51] Zheng Yuan, Hongyi Yuan, Chuanqi Tan, Wei Wang, and Songfang Huang. How well do large language models perform in arithmetic tasks? arXiv preprint arXiv:2304. 02015, 2023.
[52] Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[53] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
13

---

Supplementary material
A Limitations
Even within the class of transformers, the space of architectural decisions (both around model size and implementation of attention mechanisms, normalization procedures, tokenization, etc.) is very large; our experiments in this paper generally characterize small part of this phase space. is thus possible that some of the described trends will change as models grow or differ in parameterization details. Outside Section our experiments have focused on standard transformer models, and do not answer whether these trends hold in other related linear attention 9 35 or state-space model [9] families. Our discussion in Section focused only on linear subspaces and used principal component analysis as the primary tool, but is also possible that subspaces or latent semantics appear non-linearly which is not addressed by our current analysis.
B Impact statement
We do not anticipate any ethical concerns associated with these results and we believe understanding Al systems a crucial step harnessing their power for good.
C Computational Resources
Roughly 154 GPU days of NVidia V100 were spent on this project.
D Setup details
D.1 Data Curation and Tokenization Details
D.1.1 Modular Addition
Fix modulus 199. We randomly shuffle all possible inputs (p² of them) perform a 95%: 5% for training and test set. The split the (generated with the seed and procedure) for all across all architectures.
D.1.2 Dynamically Generated Tasks
For these tasks, we used stream of training data and heldout test set. The test is fixed for all runs across all architectures. The training data is generated on the fly within the same distribution to avoid overfitting.
The number of entities (marker-value pairs) is first uniformly generated in [1, 30). The values are generated as integers in [1, 127). The markers are generated distinct integers in [127 1, 128 + 30). The final query token is the asked marker (uniformly chosen) plus d in token ids would be [128, 1, 129, 2, 130, 3, 131, 4, 159) and the expected output will be token 2.
Bredle-in-a-Haysstae
30. For example,
b
Fix the number digits = 10. The two numbers to be added are independently uniformly generated within [10", 10 1]. The added numbers and the results are reversed. The
Decimal Addition
addition sign has token id 10 and the equal sign has id 11. For example, 1111111112+ 2222222223 = in token ids would be [2, 1.... 1, 10, 3, 2, ... 2, 11]. The result uses [20, 29 to represent digits and 30 to signal the end of output. For the example, the expected output will be 3333333335 encoded as [25, 23, 30).
Parentheses Balancing
The opening parenthesis has token id 1, the closing parenthesis has token id 2, and the question mark has token 3. For the result, signals balanced and signals unbalanced. example, (O) ()? in token ids will be [1, 1, 2, 2, 2, and the expected output is balanced, token 2.
14

---

As sequences of uniformly random parentheses are (a) likely unbalanced (b) easier to validate, we performed generate- senerate-then-men then--htateeeeeeee strategy to generate strong data for the task.
Generate With 1/3 probability, we generate a random sequence of at most 60 parentheses (length
uniformly chosen, then independently all the parentheses). With 2/3 probability, we generate balanced parentheses sequence. We first uniformly choose the number of pairs of parentheses t in [0.30]. We then generate recursively: when t 2 with 1/2 probability we generate (t 1)- parentheses sequence recursively and add pair of parentheses on the outside, with 1/2 probability we uniformly sample u E t 1] and output the concatenation of a u-parentheses and (t u)- parentheses sequence generated recursively.
Mutate With 1/2 probability, choose some random index pairs and swap the corresponding parentheses. Independently with 1/2 probability, we (then) choose some random indices and flip the corresponding parentheses. The number of pairs and indices sampled according to geometric distribution.
Circuit Imitation The inputs are uniformly random 40-token sequences of integer tokens 00 511]. The target output is the distribution from a target transformer generated as in Appendix b.l.ow The width of the target transformer chosen [4, 128] (Figure 6
D.1.3 Memorization
For every integer pair x: 5115 ]. y E [512, 512 511), we generate data point with input [x, y] and output 2 uniform [0, 511]. There no "test split" as the goal is to memorize all the associations.
D.1.4 Language Modeling
We used the original train-test split of the TinyStories dataset [4] We trained 10000-token BPE tokenizer from the training split alone.
D.2
Model Details
D.2.1
Transformers
We the GPT-2 38
implementation of Huggingface 48) Dropout and weight tying disabled.
The activation function is kept as the default GeLU 20
Specifically, all the weights of feed-forward layers are initialized by sampling from isotropic Gaus- sians with mean 0 and standard deviation 0.02/ /2i where in the number of layers. All the bias matrices are initialized with zeroes. All the other weight matrices (including key, value, query, embedding, unembedding matrices) are initialized with O-mean Gaussians with standard deviation 0.02. The affine transformations in layer normalizations are initialized as identity.
We used two layer transformers except for the language modeling and circuit imitation task. The number of parameters for the algorithmic tasks can found in Table 6
Task
Froken
Epos
U
Intermediate Layers F
Modular Addition
99,328
5,120
99,328
25,194,496
Needle-in-a--Haystade
262, 144
102,400
262, 144
25, 194,496
Decimal Addition
31,744
40,960
31,744
25,194,496
Parenthesis Balancing
4,096
81,920
4,096
19,194,496
Table Number of parameters of each type for the 2-layer 1024-width transformers in Section
D.2.2 Target Transformer in Circuit Imitation
Based the initialization in Appendix D.2.I make the following modifications.
forward Layers: Standard deviation scaled up by 20x: changed to 0.4/ V
15

---

Task and Transformer Type
Principal Component Basis
Neuron Basis
Task
Model
Emb
L1
1,2
Emb
L1
1,2
Normal
40.7%
91.6%
89.6%
3.3%
6.4%
6.8%
Decimal Addition
Random
73.3%
62.6%
51.4%
4.3%
4.0%
3.6%
Normal 31.4%
75,4%
42.5%
2.8%
5.6%
3.9%
Needle-in-a-Haystaee
Random
51.3%
42.6%
33.9%
4.4%
4.6%
3.9%
Normal 47.5%
100.0%
99.9%
7.0%
11.1%
9.4%
Balanced Parentheses
Random
85.2%
89.1% %
84.7%
9.7%
8.0%
6.7%
Table 7: Median explained variance from top 10 directions under principal and neuron basis collected from width 512 transformers. Rounded to one decimal piece. See Table 4 for more details.
Attention Matrices (key, value, query): Standard deviation scaled up by 10x: changed to 0.4.
Unembedding Matrix: Standard deviation changed to 2/ /n.
After such modifications, we measured the entropy of output distribution on two random inputs. Across all the widths, the mean entropy stays within [2899, 3.02). We also measured similarity of output distributions on different inputs to prevent mode-collapse-like results, and the mean KL divergence of output distributions on random inputs is [0.8, 3.3] across all widths.
D.2.3 LSTM
We used textbook long short-term memory tion) layer added.
22 with an encoding layer and an unembedding (projec-
D.3 Training Details
For synthetic experiments, we used AdamW optimizer (27 with a learning rate 10-3 3 and weight decay 10-3 For LSTM learning rate 5 x 10-3 is used for faster convergence. For the language modeling task, we used AdamW optimizer with learning rate 10-4 and weight decay 0.1. We clip all gradient norms 1.
For random transformer experiments, the intermediate (query, embedding. unembedding, feed- forward) layers are kept as randomly initialized. We use fixed number of training steps and no early stopping.
Modular Addition: 5000 epoches. Batch size 4000.
Needle-in-a-Haystacc, Decimal Addition, Parentheses Balancing, Circuit Imitation: 10 steps of batch size 1000. Again, the training data is generated dynamically.
Memorization: 21000 epoches. Batch size 215
Language Modeling: 5 epoches. Batch size 20 and context window 512.
E Performance on synthetic tasks across model scales
In Fig. we provide the test accuracy of -hasssian--aaaaackkk. decimal addition and parenthese balancing for fully trained and random transformers across different model widths. Note that the 1024-width fully trained transformer had trouble reaching perfect accuracy in parentheses balancing, likely due to imperfect hyperparameter choices.
We also include the explained variance measurements on 512 312-width models in these three tasks for completeness (Table Generally more variances are explained from the top directions as the models narrower.
16

---

Needle -eedle-in-a-ee H-Haystack (Normal)
Needle-ing an-a--ny--ttte (Random)
1.0
1.0
0.8
0.8
Test Accuracy
Test Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
128
256
512
1024
32
64
128
256
512
1024
Model Width
Model Width
Decimal Addition (Normal)
Decimal Addition (Random)
1.0
1.0
0.8
0.8
Test Accuracy
Test Accuracy
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
64
128
256
512
1024
64
128
512
1024
Model Width
Model Width
Parentheses Balancing (Normal)
Parentheses Balancing (Random)
1.0
1.0
0.8
Test Accuracy
Test Accuracy
0.6
0.4
0.2
0.2
0.0
16
32
64
128
256
512 1024
16
32
64
128
256
512
1024
Model Width
Model Width
Figure 7: Box plot of test accuracy of synthetic tasks across model scales.
F
Constant-dimensionaa subspaces are sufficient for many synthetic tasks
Definition F.1 (Intermediate complexity of tasks (informal)). For family of neural networks with varying intermediate width, we define the intermediate complexity of a task as the minimal width of intermediate layers required to succeed in the task.
For example, 2-layer transformer with intermediate width starts by embed the tokens into the 2-dimensional hidden space, passes them through two transformer blocks of width 2, then linearly
17

---

project the activation for the final output (unembedding). If one task could be solved with one such transformer, its intermediate complexity for 2-layer transformers would be at most
If we consider the activations the working memory of the LLM,, intuitively task has low
intermediate complexity if it requires a low working memory per token. In the following, we show that all the synthetic tasks proposed indeed have constant intermediate complexity for 2-layer transformers, thus they only require a constant-dimensionn intermediate subspaces to work on.
Modular Addition We may use a transformer to implement three instances of the Pizza algorithm described in Zhong et al. [52] (multiple copies are needed to avoid the "antipodal pairs" problem described there). Each implementation of this algorithm requires intermediate representations of size 2, so the intermediate complexity for 2-layer transformers is I 6.
We may use transformer to implement induction heads 34 as follows: We first store each token's 's preceding token in its activations by attending to the previous position. We then retrieve the answer by attending to the position storing the matching token in the previous step. Both steps could be done by using attention to compute squares of differences and take the minimum. The number of hidden states needed to distinguish each symbol scales only with the size of the vocabulary, and is at most equal to the vocabulary size, so the intermediate complexity is at most twice the vobaulary size.
Boadle-in-a-Haystae
Parentheses Balancing Let the given sequence of parentheses be pl, P2, ... Pn- Le = =ji= Co where Q; = 1 if p, is an open parenthesis and c = -1 if p. is a closing parenthesis. The given sequence is valid parentheses sequence if and only if z 0 and min 2; = 0. In transformer, we can first compute n;/i with a uniform attention. Then, we attend to the position with minimum zz/i, breaking ties by position (let the attention on i pre-softmax be T(-x,/i+ ci) for large enough and small enough c > 0). For valid parentheses sequences, the last position should only attend to itself. We then check if the attended position is indeed the last one and has v = 0 by computing squares of differences. The intermediate complexity for 2-layer transformers is thereby again constant.
(note that different construction for bounded-depth Dyck was given in (5
Decimal Addition
Let the reversed list of digits of two numbers and their sum be a1, a.,-.. Ons b1, b2. bns and
C1 c.. Let 2; Σj= a, 1010- y44 Σj= b, 1000i, 2, Σj c,10 - we have G (z+ +
yi 24) mod 10: + b ンドー 1a, + b;) (mod 10'), (a (b) mod 10i-1 Eド ej 10:-1
and C = ((a + b) mod 10 (a + b) mod 10 1/10=-1
let the positional embedding of position i be [1, 10', 10. In the first head of the first layer, take the first dimension in the positional embedding for both Q and K, so we get a uniform attention on the prefix from which o; 1 Σj= aj can be calculated. In the second head of the first layer, take the third dimension in the positional embedding for Q and the second dimension in the positional embedding for K, the contribution from the j-th position to the i-th position is i cl
Prepare: Take small > 0. For positions 1, 2,
for 0 c < 1) for normalizing constant Zz. we can then calculate = 2 Ej=1 1 (105 1). We then have
+10' + 1) (e x
2:
x; 2 B ia; which we will utilize in the next step. Similarly, we can have and 2; ready in the corresponding position (position of b, and 1-1))
Generate 2; - y; 2,: In the second layer, attend from the position of a, and by at the position of G-1- Specifically, set the attention from the as's 's's position to the c--1 's position be ei A cos((k: 0)/n) = é - A (cos(k/n cos(i/n) + sin(k/nu sin(i/n)) pre-softmax. This could be done using three dimensions in the positional embeddings. We also set the attention from the plus sign to the c--1's 's position be 1 pre-softmax. The attention from ag to C-11 will be negligible if k & and will be proportional to ei sostmax for k = i. We can then calculate ia; from it and similarly 4B, and thus vi, y/ and zz-
Approximate the Answer: As H4 + yi - zi is an integer from [0, 19) and we can also compute an affine transform of it, may now simply proceed with the universal approximation theorem. As an
18

---

example, in ReLU networks we may check if x; + - 2 U by noticing
+ ReLU((;; + -ー= - - :/ -4 2:- ((-1)) (2)))) + - = + y/ 2; = m),
So to create an indicator variable ni + y/i =i = we simply need generate di + yi Pio 2, pre-ReLU.
+ د 1, Vi
The intermediate complexity for 2-layer transformers is thereby again constant. This approach is quite crude so it is likely that the constant can be greatly improved.
G Difficulty of the synthetic tasks
Chomsky hierarchy has been found be predictive of the neural architectures' performances, and especially hierarchy of the synthetic tasks we picked in Table X
performances, in algorithmic setups [33
We list the Chomsky
Task
Chomsky Hierarchy
Needle-in-al Hayyle-i---HHyystckk
Regular
Decimal Addition
Context Sensitive
Parenthesis Balancing
Context Free
Table 8: Classification of tasks according to the Chomsky hierarchy. For the decimal addition task, we consider the most flexible setting where all the strings representing decimal additions (does not have be equal-lengthed) are considered within the language.
We also examined baseline with lincarized transformer. In this variant of transformer, the attention matrix (softmax (oottax(Q&<")) (QK")) is replaced with lower diagonal matrix of Is. In other words, the attention replaced by simple token prefix and layers on the synthetic tasks as a baseline performance. The result is shown in Table We can that such transformers have large performance gaps with normal transformers, confirming the difficulty of our chosen tasks.
mechanism. We tested such transformers with width 512
Task
Accuracy (%)
saalle-in---hystactt
17.67
Decimal Addition
26.39
Parenthesis Balancing
97.32
Table Linearized transformer performance terms of accuracy.
H
Accuracy curve of the memorization task
The accuracy curve in the memorization task during training is shown in Fig. Training of both transformers has converged.
19

---

Accuracy for random transformer
Accuracy for fully trained transformer
0.8
0.04
0.6
0.03
0.4
0.02
0.2
0.01
0.0
Figure 8: During training, the accuracy curve from fully trained and random transformers in the memorization task (Section 5.1) Note that the evaluation set is exactly the training set as the goal is memorize.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All our claims are based on empirical evidences.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
The only theoretical result is included in Appendix F where the full proof is given.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We tried our best to convey all the experiment details and we will also be releasing code and data after some final cleanup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We plan to release code and data after finalizing.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr Swwpsubbbsssoooooooooooooo for more details.
public/
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https ssionPolicy for more details.
/ //nips. wtnpps.cc/pbbl....
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Details are included in Appendix D Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We include the 80% CI bars in Appendix E Some experiments not repeated due to computational constraints.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
23

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp::/neuurisscccc/ http://uwwpp...ooobo//////ssstas
Answer: [Yes]
Justification: We reviewed the Code of Ethics and we believe our work will not cause potential harms and negative societal impacts.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Appendix B
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our results do not pose high risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cited the original papers for each asset.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssil swi thcode. thcoodee com/ datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We will release the code and trained models as well as documentation on how to apply them.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No crowdsoureing or human-subject research is involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing human-subject research is involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
26


Reviews:
[{"review_id": "tJCODHZIaD", "reviewer": "Reviewer_B9i5", "summary": "**Update after rebuttal:**\nMy main concerns have been addressed and/or clarified, and some interesting results have been added. I therefore raise my score from 6 to 7, and vote and argue for accepting the paper.\n\nThe paper investigates capabilities of randomly initialized, untrained transformers, where only a linear initial and final mapping (embedding and unembedding) are trained. The tasks investigated are: integer addition (with and without modulus), retrieval of a token in the context by specifying the preceding token as a marker, and parenthesis balancing. The paper shows that training only the embedding and unembedding suffices to solve these tasks, implying that untrained transformers have the algorithmic capability to do so. Ablations show that training both, embedding (incl. positional encoding) and unembedding is important to solve all tasks. Further experiments are performed to test capabilities when training only embedding and unembedding: (i) memorization capacity, and (ii) next-token prediction performance trained and evaluated on a dataset of natural language text. In all cases untrained transformers achieve non-trivial performance, but lag behind fully trained models. Finally, the paper tries to identify whether functions implementable by untrained transformers (with a trained linear input- and output-mapping) are limited to low-dimensional linear subspaces or sparse sub-networks - the former with somewhat mixed results but evidence pointing towards an effect, the latter with more consistently negative results (though pruning and knockout-experiments might be needed to be sure). The last experiment of the paper investigates the capability of untrained transformers (only embedding and unembedding are trained) to imitate the input-output mapping of smaller random transformers on random inputs - which works quite well as long as the transformers to imitate are not too large, but overall performance cannot be matched compared to full training of a comparable standard transformer on the task.", "questions": "**Questions and minor comments:**\n\n1. How are inputs tokenized (L82)? Standard tokenizers are usually optimized to (pre-)compress natural language text, which may skew the results Sec. 5.2, and may make some of the algorithmic problems harder (e.g. by mapping pairs or triplets of integers to tokens which may make the integer addition tasks harder). Ideally there would be an ablation in 5.2 without a tokenizer, but simply discussing this caveat should be fine.\n2. 4.1 Tasks: I had the following questions when reading (the answers are in the appendix, but it would be good to have them in the main paper). What is (the range of) $p$ for modular arithmetic tasks? What is (the range of) $k$ for Needle-in-a-Haystack? What is the (range of) length(s) of the decimal numbers? What is the range of input lengths for Parenthesis balancing?\n3. How are variable-length inputs dealt with (e.g. in the parenthesis matching task)? Padding with some token and loss masking? Related: what is the context-size of the transformers used?\n4. A recent paper investigated transformers’ capabilities across different kinds of algorithmic problems, using the Chomsky hierarchy [Neural Networks and the Chomsky Hierarchy, Deletang et al. 2022]. The main finding was that the algorithmic complexity class was highly predictive of the length-generalization capability of different architectures. It would be nice to state the algorithmic complexity (i.e. where they lie on the Chomsky hierarchy) of the tasks used in the paper.\n5. After L98: Unless I missed something this should be minimization of the negative log likelihood. Also $y$ has not been introduced and the notation $y \\min x$ may be confusing. Why not use $p(x_{n+1} | x_{1 \\ldots n}; E, F, U)$ which was introduced above L89? Maybe just write down the standard (cumulative) log-loss over a sequence of tokens, and then make the difference between full-training and embedding-only training clear by simply stating the arg min over the loss with the respective parameters.\n6. L19: missing reference.\n7. L128 (nit): While general Dyck recognition requires context-free grammars, parenthesis balancing with a single type of parenthesis should be context-sensitive, right?\n8. For Table1 and Table2: state the number of trainable parameters for each setting (either in the table or the appendix).\n9. L141-142: “These results thus point toward the role of a transformer-specific inductive bias in the effectiveness of embedding-only training.” to make this statement stronger, random recurrent nets would also need to be investigated, as the inductive biases may be neural-network specific and not just transformer-specific.\n10. Reporting only the median in the main paper is good. But it would be nice to show the whole distribution in the appendix (and maybe even a box-plot) to get a clearer picture.\n11. 5.1: For the memorization task - please show the learning curves in the appendix. I assume the random transformer and normal transformer use the same training settings: has the random transformer converged at the end of training?\n12. Fig. 4: it would be very nice to see another datapoint (ie., a width of 1024) since the cross-entropy loss for the random transformers seems to start to catch up to the normal transformer, which would be an interesting trend.\n13. L242: “(but not LSTM sequence models)” - unless I missed something, the paper has not shown results on randomly initialized frozen LSTMs with a trained embedding and unembedding; only fully trained LSTMs.\n14. (nit): NeurIPS Checklist, Q4 (Reproducibility): the question specifically asks whether all necessary details for reproducibility are given in the paper regardless of whether code and data are provided. The justification by the authors is: “We will be releasing code and data after some final cleanup.”, which does not address the question.\n15. NeurIPS Checklist, Q2 (Limitations): The reference in the justification to the limitations section in the appendix is broken.", "limitations": "There is a brief limitations section at the beginning of the appendix. I think it should be expanded by stating limitations regarding the generality of some findings and whether all reasonable alternative explanations can be ruled out given the current experiments and findings. I have listed these under ‘Improvements 1 and 2’.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Very timely question - while transformers’ inductive biases and implicit simplicity bias have been investigated before, the question of “Which algorithms are there from the beginning, even before training?” is an important piece of the puzzle and it is straightforwardly accessible to experimentation. \n* Range of interesting tasks, which can be related to previous results in the literature and span a range of capabilities.\n* Important control experiments w.r.t. which parts of the input- and output-mapping need to be trained (answer: neither only the input, nor only the output are sufficient).", "weaknesses": "* Perhaps the main weakness is that the paper aims to cover a lot of ground - which means that breadth of experiments is favored over depth. While I appreciate the breadth, and including the attempt to shed some light on the lower-dimensional subspace and sparse subnetwork hypotheses, this does come at the cost of missing some additional experiments and ablations, which in turn means that some of the results and interpretations must be taken with caution or be considered preliminary but not final answers. (see more under ‘Improvements’ below)\n* Some of the caveats and alternative explanations that could not be tested in the paper need to be explicitly mentioned (e.g., in the limitations section) and generality of the claims and findings must be explicitly put in relation to these caveats and limitations. I do not mean that the paper intentionally “shoves caveats under the carpet” (far from it), but since these results may receive a lot of attention, laying a solid groundwork for future work that includes pointing out where the foundations need to be strengthened is very valuable.\n* (Minor): While I appreciate that the paper is not bloated with overly complex formalism and vacuous math, I think that Section 3 could do with another pass to be slightly more rigorous.\n* (Very Minor): there is a fairly large body of literature (including quite a bit of theory) from the 90s and early 2000s on reservoir computing and echo state networks, where the central idea is that a random recurrent network implements virtually any function on the data, and so all that is needed is to train a linear readout while keeping the random recurrent reservoir’s weights frozen (paraphrasing informally, though there are formal function approximation statements for well-defined classes of functions). It would be good to include at least a pointer to this literature (maybe a good survey) in the related work section.\n\n**Verdict:**\nThe paper addresses a timely and important question with simple, yet insightful and original experiments that, without a doubt, start to fill an important gap in the literature. The paper is generally well-written, though the formalism (Sec. 3) could benefit from slightly more rigor. The main claims in the paper are supported by empirical evidence and the results are interesting and insightful. My main concern with the current manuscript is that it favors breadth of questions over depth. Just the results in Section 4 could easily be expanded into a full paper by adding more ablations and control experiments. Similarly, identifying whether (and how) random transformers implement functions in a lower-dimensional subspace or sparse subnetwork could easily fill a whole publication. Since the paper is pioneering to a large degree, going for breadth to plant several flags is OK, but I think this needs to be supported by a strong discussion of caveats, open questions, and alternative hypotheses that cannot be ruled out yet. I will be concrete in my suggested improvements below. Taking all of this together, I am leaning towards accepting the paper - I do believe it has the potential to become a landmark paper if more work (beyond the rebuttal) was spent, but even in its current state (and with some improvements after rebuttal) its findings will be interesting to a large audience and will spark follow-up work. \n\n**Improvements:**\n1. Here is a list of interesting control experiments and ablations that would make the paper stronger. This list is too extensive for the rebuttal phase and I do not expect to see these experiments. But it would be good if the paper could discuss all the unaddressed questions and add them as an explicit caveat to the limitations section w.r.t. the generality of the findings, and when discussing the particular results.\n    1. Control experiment: compare against a random LSTM where only the input and output mappings are trained. The paper compares against a fully trained LSTM (which is good), but the ‘Random LSTM’ is missing (this would also be interesting since it relates more directly to the reservoir computing literature). To complicate things, the LSTM may need a wider (or more narrow) hidden state and more layers to solve the task. If done exhaustively, and the current results hold, then the paper could make strong claims regarding the implicit abilities of Random Transformers that LSTMs do not possess, otherwise the observed abilities may apply to neural networks more generally. \n    2. Control experiment: replace the transformer with a random MLP - this helps answer how important the attention mechanism is for the algorithmic capabilities tested. The size of the MLP (width and number of layers) may need to differ from the Transformer (maybe having the same overall random parameter count).\n    3. Baseline: it would be good to establish a naive baseline difficulty of the tasks in the paper (particularly Sec. 4) and how well they can be solved by having a trainable linear matrix of a certain size. Off the top of my head this could look like replacing the transformer with a single nonlinear layer (with frozen weights) and training the embedding and unembedding - but maybe there is a better baseline for this. If even very simple baselines could solve the tasks by training a linear input and output projection (which I do not expect), then the corresponding tasks would be unsuitable to say much about the algorithmic capabilities of Random Transformers.\n2. More caveats:\n    1. PCA is linear, which means that it cannot help identify nonlinear lower-dimensional subspaces. There are more sophisticated methods than a PCA, but I think it suffices to just clearly spell out this caveat in Sec. 6 and in the interpretation of the results of that section.\n    2. For the neuron basis results in Sec. 6: it may be that one of the main functions of the unembedding is to “select” the outputs of one or more sparse sub-circuits that implement the required functionality. In this case, the activation of other neurons in the transformers is not suppressed and may easily have similar variance. The analysis in Sec. 6, unless I am mistaken, would not be able to separate these highly active but functionally irrelevant circuits from one (or a few) functionally highly relevant sparse subnetwork(s). To do this reliably, pruning experiments may be required. It is fine to not perform these experiments, but I think the results in Sec. 6 do not conclusively rule out with absolute certainty that the algorithms are not implemented via sparse subnetworks, they only show that these subnetworks cannot be identified by checking how much variance the highest-variance neurons explain, which should be added as a limitation.\n    3. Fig. 6: though the KL divergence for Random Transformers clearly shows their inferior performance compared to a fully trained full-size Transformer, I am wondering how large that gap is, because it seems that the Random Transformers still achieve non-trivial performance. It would be nice to have a naive baseline in the plot to see how bad the performance of a “bad” model gets (is a KL divergence of 0.8 “quite bad” or actually “still quite good but not optimal”?). A highly related question is whether the KL divergence is dominated by very bad performance on a few datapoints, or just marginally worse across most inputs? The current writing suggests that Random Transformers beyond a target width of 32 fail (more or less) catastrophically.\n3. Related work: Questions very related to the paper have spawned a whole research field (reservoir computing or echo state networks) at the end of the last century and I think readers would benefit from a brief pointer to that literature (either a good survey or a small number of important papers in that field). Similarly, certain prompt-tuning techniques can be related to partial training of input embeddings - while a thorough investigation of the connection between prompt tuning and virtually untrained “residue circuitry” in a trained transformer is far beyond the scope of the current paper, I think a sentence or two in the related work or discussion might spark such research.\n4. Sec. 3: The mathematical notation is understandable for people familiar with transformers, but could do with another pass to be more rigorous. Particularly important would be to define the dimensionality of the embedding-matrices and unembedding matrices, as this will determine the number of trainable parameters, and how inputs are tokenized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed and throughout review! The following are our responses.\n\n> Compare against random LSTM\n\nIn this paper, we are trying to narrow our already-pretty-broad discussion to random transformers instead of random neural architecture in general and we have shown that random transformers perform better than fully-trained LSTMs on some tasks, for example. And indeed, from our quick additional experiments it seems random LSTM does need even wider hidden states to solve the algorithmic tasks as 1024-width 2-layer randomly initialized frozen LSTMs (similar setup as transformers: only embedding and unembedding trained) on the needle-in-a-haystack task only reached a (test) accuracy of 16.85%. This is indeed an interesting future direction worth being explored in subsequent works.\n\n> Control experiment; Baseline\n\nWhile possible, a direct MLP implementation will be unnatural for the variable-lengthed tasks we addressed. As a slight modification, we studied the performance of a modified version of transformer where the attention matrices (specifically the $\\text{softmax}(QK^T)$; the V is still used) are placed with lower triangular matrices of 1s. One can also consider this model as a MLP with additional token-mixing prefix sum layers and layer normalizations. We trained such models of 512 width and 2 layers. The result accuracy is given as follows (included in appendix). We can see that such linearized transformers have large performance gaps, confirming the difficulty of our chosen tasks.\n\n- Parenthesis balancing: 97.32%\n- Needle-in-a-haystack: 17.67%\n- Decimal addition: 26.39%\n\n> PCA cannot identify nonlinear lower-dimensional subspaces\n\nHere by subspace we mean linear subspaces and our experiments and analysis are based on that. We have added this as a limitation in the working version.\n\n> Sec. 6 cannot separate active but functionally irrelevant circuits\n\nThis is a great point. We have added this as a limitation in the working version.\n\n> Fig. 6: Clarify how large KL divergence gap is\n\nSubjectively a KL of 0.2 is already quite bad. Due to limited space please see the official comment for samples.\n\n> Reservoir computing could be relevant\n\nThanks for pointing this out! This line of research is indeed very relevant. One tiny but important difference here is that we train both embedding and unembedding in our main settings, which deviates from the purpose of the reservoir computing diagram. We have added a brief introduction to reservoir computing and a few surveys in the related work section.\n\n> Refine mathematical notation in Sec. 3\n\nThanks for the suggestion! We have refined the writing and added a short paragraph discussing the shape of matrices and parameter counts.\n\n> Clarify tokenization\n\nTokenization is indeed an important factor in such algorithmic tasks and has been constantly evolving [1]. Due to the scope of the paper, we generally chose the simplest tokenization (e.g. one token per digit in the decimal addition task) in our setups and described the details of our tokenizations in Appendix D. We added the discussion in the limitation section.\n\n[1] Max Buckley. Right to Left (R2L) Integer Tokenization. https://www.beren.io/2024-07-07-Right-to-Left-Integer-Tokenization/\n\n> Specify parameter ranges\n\nThanks for pointing this out! We added the answers (p=199, at most 30 pairs, 10-digit, at most 60 parentheses) to the main text.\n\n> How are variable-length inputs dealt with? Context size?\n\nYes, the standard padding and loss masking. The context size generally has the same magnitude as the maximum possible length of the sequence (though usually slightly larger). For example, in the ten-digit decimal addition, we used context size 40. The numbers are also given in the attached code. We believe the result will stay unchanged qualitatively as long as the context lengths are of reasonable magnitudes.\n\n> L98 is off and confusing\n\nThanks for spotting this out! Following your suggestion we have modified the optimization goal to be $\\\\arg\\\\min_{E,U}$ and $\\\\arg\\\\min_{E,F,U} \\\\sum_{x,n\\ge 0} -\\\\log p(x_{n+1} \\\\mid x_{1\\cdots n};E,F,U).$\n\n> L19: missing reference; Broken link in Limitation\n\nFixed. Thanks!\n\n> Hierarchy of parenthesis balancing\n\nCorrect me if I'm wrong, but I think context-free grammar is a special case of context-sensitive grammar. If you mean regular, the language of balanced parentheses is not regular by the pumping lemma.\n\n> Table 1,2: state # of trainable parameters for each setting\n\nThanks for the suggestion! We have added the parameter counts in Appendix D.2.1. We also attached the table in the rebuttal pdf.\n    \n> L141-142: ... a transformer-specific inductive bias in the effectiveness of embedding-only training. Random recurrent nets also need to be investigated.\n\nThe “effectiveness” here is transformer-specific as the LSTMs we trained, fully trained or partially frozen, fail to complete the decimal addition task, thus worse performing compared to the random transformer. We do not plan to advocate for other randomly initialized neural architectures including LSTM due to the already pretty broad scope of the paper.\n\n> Show whole distribution\n\nGreat suggestion! Changed the plot to a box plot (also attached in the rebuttal pdf).\n\n> Show learning curves for memorization\n\nYes they converged. Attached the plot to both the appendix and the rebuttal pdf.\n\n> A datapoint of width of 1024 in Fig 4\n\nThat is a great suggestion! Unfortunately we are unable to run this experiment due to time and resource constraints. We will include that in the final version if time permits.\n\n> No results on randomly initialized frozen LSTMs with a trained embedding and unembedding; only fully trained\n\nYes, but here we assumed that randomly initialized LSTMs perform worse than fully trained LSTMs. See the top for additional experiment results.\n\n> Reproducibility\n\nChanged the line to `We tried our best to convey all the experiment details and we will also be releasing the code and data.` Thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cJcg4W44Gb", "reviewer": "Reviewer_wwwU", "summary": "This paper studies transformers with freezed random intermediate layers, and embedding-only trainable layers. The authors show that wide enough random transformers are capable of performing simple algorithmic tasks such as addition and parenthesis balancing. This study further investigates the reason behind such learnability, concluding that such transformers operate in low-dimensional subspaces.", "questions": "* From my understanding of the attached code, the LSTM is trained without gradient clipping. Since LSTMs are generally harder to train, and require small learning rates, with gradient clipping and larger number of optimization steps, I wonder if their performance would match with a normal Transformer in Table 1 if we apply such improvements? In other words, is it an optimization issue that LSTM is lagging behind, or a generalization issue?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The observation that training only the embedding layers can lead to noticeable accuracy on tasks is interesting. \n* The paper is well-written and easy to follow.", "weaknesses": "* It is not clear how this observation about random transformers is helpful and useful. Especially, given that the (1) studied tasks are very simple (2) random transformer needs to be very wide to compete with a normal transformer of much smaller width.\n* In Section 6 (Random Transformers Operate in Low-Dimensional Subspaces), the conclusions are a bit mixed and confusing. The text suggest that “Random” transformers operate in low-dim subspaces, but Table 4 does not show any difference between principal components of either normal or random transformers — in some tasks the former is larger, in other tasks the later. Perhaps, we could conclude “Transformers generally operate in in low-dim subspaces on these tasks”, but this conclusion is irrelevant to the motivation of the section to investigate the success of random transformers.\n* Some table results seem inconsistent: In Table 1, random transformer achieves 100% accuracy for the Decimal Addition. However, in Table 2,  “E_token & U only” achieves only 48.5%. From my understanding, these two numbers should match, unless they are run under different settings. The “Needle-in-a-Haystack” tasks seems to have the same issue as well. Please correct me if I am missing something here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed and insightful review! The following are our responses.\n\n> It is not clear how this observation about random transformers is helpful and useful. Especially, given that the (1) studied tasks are very simple (2) random transformer needs to be very wide to compete with a normal transformer of much smaller width.\n> \n\nOne main takeaway of the work, we believe, is that circuits capable of solving these simple tasks naturally exist in randomly initialized transformers, and could be activated merely by directing to these circuits by tuning the embedding and unembedding layers. We are not trying to advocate for actually employing them in everyday tasks instead of fully trained transformers, but we believe our work offers interesting and crucial insights that will help us understand (fully trained) transformers better. For example, an interesting follow-up question would be what abilities are newly developed in training rather than merely activated in a similar sense. We also studied language modeling as an example of a more complicated and less well-defined task.\n\n> In Section 6 (Random Transformers Operate in Low-Dimensional Subspaces), the conclusions are a bit mixed and confusing. The text suggest that “Random” transformers operate in low-dim subspaces, but Table 4 does not show any difference between principal components of either normal or random transformers — in some tasks the former is larger, in other tasks the later. Perhaps, we could conclude “Transformers generally operate in in low-dim subspaces on these tasks”, but this conclusion is irrelevant to the motivation of the section to investigate the success of random transformers.\n> \n\nThis is a good point and the following is our argument, rephrased. For the four simple synthetic tasks, it is known that working in low-dimensional subspaces suffices (see App F) so both normal and random transformers display some degree of subspace concentration (and indeed, they can all reach perfect or near-perfect accuracy in these tasks). For language modeling and memorization, the random transformers display more subspace concentration compared to the fully trained ones and as a result, have lower performances. Finally, we show that for a task that explicitly requires operating on high-dimensional spaces, circuit imitation, the random transformers fell short compared to normal transformers. Agreed that this argument is not clearly expressed in the paper and we are working to refine that.\n\n> Some table results seem inconsistent: In Table 1, random transformer achieves 100% accuracy for the Decimal Addition. However, in Table 2, “E_token & U only” achieves only 48.5%. From my understanding, these two numbers should match, unless they are run under different settings. The “Needle-in-a-Haystack” tasks seems to have the same issue as well. Please correct me if I am missing something here.\n> \n\nWe agree it is somewhat confusing. In the paper, by embedding we mean both the token embeddings E_token and the positional embeddings E_pos. It is the positional embeddings that are left untrained / as randomly initialized here, which accounts for the lowered performances. We also noted this in the table caption.\n\n> From my understanding of the attached code, the LSTM is trained without gradient clipping. Since LSTMs are generally harder to train, and require small learning rates, with gradient clipping and larger number of optimization steps, I wonder if their performance would match with a normal Transformer in Table 1 if we apply such improvements? In other words, is it an optimization issue that LSTM is lagging behind, or a generalization issue?\n> \n\nWe in fact clipped the gradient norm to 1, which is the default in the huggingface trainer, and hand-tuned the learning rate of LSTM for better convergence. We have added these missing training details in the working copy. Thanks! There are also literature echoing the imperfect LSTM performance in needle searching [1] and decimal addition [2] tasks.\n\n[1] Zhang, Wei, and Bowen Zhou. \"Learning to update auto-associative memory in recurrent neural networks for improving sequence memorization.\" arXiv preprint arXiv:1709.06493 (2017).\n\n[2] Bradbury, James, et al. \"Quasi-recurrent neural networks.\" arXiv preprint arXiv:1611.01576 (2016).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "72eD78sNq7", "reviewer": "Reviewer_ZcHJ", "summary": "The aim of the paper is to understand how much of the effectiveness of Transformer models depends on the architecture itself rather than the possibility to train its internal parameters. To this aim, the authors study causal Transformers where only the embedding matrix, the positional encodings and the final projection matrix are trained, while the rest of the parameters do not change after random initialization. The authors compare the performance of small-scale random Transformers to that of fully-trained ones (of the same size) on some synthetic and language modeling tasks. They observe that random Transformers (with properly optimized embeddings) are able to solve all the synthetic tasks, in some cases exhibiting computational circuits similar to those observed in trained models. Although random Transformers have weaker memorization capabilities, they can also generate grammatically correct (and often consistent) text.", "questions": "-\tAlgorithmic capabilities must be evaluated in the out-of-distribution regimen. I am not asking the authors to demonstrate that random Transformers can solve algorithmic problems OOD (this would be an extraordinary achievement), but rather to compare them with trained models using more sensitive versions of the synthetic tasks, and discuss the findings in a less overhyped fashion (starting from the title).\n-\t“Transformers seem to be especially well-suited at problems involving numerical reasoning”. This sentence relfects the overhyped interpretation of Transformers capabilities in algorithmic / numerical tasks (see https://arxiv.org/abs/2305.18654 and https://www.mdpi.com/2076-3417/14/2/744 for different perspectives).\n-\tThe analyses on the low-dimensional sub-spaces should be presented in a more formal and clear way.\n-\tThe presentation of results of a Normal 16-dimensional Transformer in Table 1 creates confusion: since similar accuracies are obtained with a Random 16-dimensional transformer (Appendix E) it would be better to include results for both Random and Normal 16-dimensional models or just show the 1024-dimensional models.\n-\tIt would be interesting to investigate the exceptionally poor performance in modular addition (Test) of the models in which only E or U are trained (Table 2).\n-\tSome error bars in Fig. 7 seem too large or even misaligned. Is that a formatting problem or does it indicate poor convergence of training?\n-\tIn the appendix, the input for the memorization task is described as two integers, one in [0, 511] and the other in [512, 512+511], which is not coherent with the description in the main text (section 5.1). Please clarify.\n-\tThe metric described in the caption of Fig. 4 (log perplexity) is not coherent with the y-axis label (Cross-Entropy Loss). Please clarify.", "limitations": "The authors properly discuss the possible limitations of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think that this work is original and relevant. The authors explore an interesting question drawing from the rich literature on randomly initialized neural networks and proposing a connection with circuit-based interpretability techniques. The experiments and findings are generally coherent with the conclusions drawn by the authors. The paper is well-written and the results are generally presented in a clear way.", "weaknesses": "In my opinion, the most critical issue is related to the use of the term “algorithmic capabilities”. In the literature this term is often misused (or even abused): a system has algorithmic capabilities when it can robustly (if not perfectly) extrapolate symbolic knowledge outside its training distribution. The synthetic problems investigated in the present study do not assess algorithmic capabilities, because the models are tested only within the ranges encountered during training. The case of modular addition is particularly representative: the authors only consider a subspace of the problem, shuffling the patterns and using 95% of them for training and 5% for testing. This is probably why performance is at ceiling even with random architectures. Comparing models using tasks that can be solved with 100% of accuracy (see Table 1) is not particularly meaningful. In light of this, I think that the significance and impact of the present work might be overall quite limited.\n\nThe results related to the attention patterns on the needle-in-a-haystack task are quite expected, since this problem can be solved by using only input embeddings (indeed, the model where the positional encodings are not trained still achieves almost perfect accuracy).\n\nThe authors should improve the presentation of the results related to the low-dimensional sub-space analysis. Saying that there exists a (small) width of hidden representations that is sufficient for a fixed-depth transformer to solve a task (Appendix F) seems analogous to saying that in a higher-dimensional space, it is enough to use a smaller number of dimensions (principal components) to solve the task. The authors should better clarify what they mean by “concentration in a low-dimensional sub-space” (even formally, if necessary) and better relate this to the notion of sparseness. The presentation of the results in section 6.2 is also not very clear: the authors say that they fit the distribution of outputs generated by a randomly initialized transformer with 3 layers and hidden representations of varying dimensions. However, they then say (and show in Fig. 6) that a random transformer can match the behavior of a shallower model of depth 1, which was not mentioned before. Finally, they comment on the capability of random Transformers of matching the behavior of significantly narrower (128) models, but the difference in linear scale (left panel in Fig. 6) appears still marked even compared to 128-width models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed and insightful review! The following are our responses.\n\n> Misuse of term \"algorithmic capabilities\"\n\nLet us humbly disagree. While a good algorithm should work for all possible data, in practice *implementations* often cannot extrapolate well, which does not disprove that the model class possesses algorithmic capabilities. For example, an algorithm in C might fail with a too large input array. Similarly, if a transformer uses absolute positional embedding, it might fail outside the training range. However, we can still claim that our C program or transformer possesses algorithmic capability. We will refine our wording to clarify that the algorithmic capabilities are for the model class, not a specific trained model. We are more than happy to discuss further on this topic!\n\n> Clarify meaning of “concentration in a low-dimensional sub-space”\n\nYes. What you stated is exactly what we are demonstrating in Sec 6.1. We have refined the introduction of Sec 6 and added a short formulation to clarify this.\n\n> Authors say and show that a random transformer can match behavior of a shallower model of depth 1, which was not mentioned before. They comment on capability of random Transformers matching behavior of significantly narrower (128) models.\n\nThis is not what we meant. We are matching the behavior of a target (carefully generated) transformer *with* either random or fully trained transformers, including a shallower model of depth 1. The target transformer is well-approximated by a depth 1 transformer in the low-width regime.\n\nWe agree that random transformers cannot match significantly narrower models - this is exactly we try to demonstrate here. The argument is that the random transformers can approximate or *act as* \"narrow\" circuits, but fail for moderately wide (128) circuits. This is their fundamental limitation. We apologize for the possible confusion and have revised this section for clarity.\n\n> Algorithmic capabilities must be evaluated OOD; Use more sensitive versions of tasks\n\nDemonstrating OOD problem-solving is out of the scope of this paper, but again we do not think this is a fundamental issue, and we want to point out that we are already using some of the more sensitive versions of this task. For the needle searching task, one common practice [1] is to insert an out-of-place sentence into a long text, easily spotted as an unconditional retrieval task. Our version requires key-value retrieval. For the parenthesis balancing task, many previous works focused on limited depth versions [2, 3], while our version features high-depth and close-to-correct data (see Appendix D.1.2).\n\n[1] Anthropic. Long context prompting for Claude 2.1, 2023. URL https://www.anthropic.com/news/claude-2-1-prompting\n\n[2] Wen et al. Transformers are uninterpretable with myopic methods: a case study with bounded dyck grammars.\n\n[3] Shunyu et al. Self-attention networks can process bounded hierarchical languages.\n\n> Transformers seem especially well-suited at problems involving numerical reasoning: overhyped\n\nThanks for the pointers. The main point we are trying to get through here is that transformers are superior in these tasks compared to other neural architectures, which is shown in e.g. [4] and perhaps in Table 1 of our paper. We have toned down the sentence in the working version.\n\n[4] Saxton et al. Analysing mathematical reasoning abilities of neural models.\n\n> Analyses on low-dimensional subspaces should be more formal and clear\n\nWe agree that our argument is somewhat convoluted and here is it rephrased. For simple synthetic tasks, working in low-dimensional subspaces suffices (see App F), so both normal and random transformers display subspace concentration. For language modeling and memorization, random transformers show more subspace concentration and thus lower performance. For a task requiring high-dimensional operations like circuit imitation, random transformers fall short. We have refined this argument and included a formal definition.\n\n> Table 1 is confusing\n\nGreat suggestion! We have included the results for the random 16-dimensional transformer in Table 1 in the working copy and rebuttal pdf.\n\n> Poor performances in modular addition of models where E or U are trained\n\nAn exact proof is a bit far-fetched, but both algorithms discussed in [5] requires the use of both embedding and unembedding, so if the model succeeded with only E or U trained, this suggests that a new algorithm is yet to be discovered.\n\n[5] Zhong et al. The clock and the pizza: Two stories in mechanistic explanation of neural networks.\n\n> Error bars in Fig. 7\n\nIt is not a formatting issue. For example, in the 16-width normal decimal addition training, 4 out of 10 runs had perfect accuracy, while the others had no more than 67.5%, with one run at 34.9%. This discontinuity might suggest a sharp phase transition similar to grokking [6]. We have refined the plot to be a box plot (see rebuttal pdf).\n\n[6] Power, Alethea, et al. \"Grokking: Generalization beyond overfitting on small algorithmic datasets.\"\n\n> Clarify input for memorization\n\nWe did not detail the exact formatting in the main text for the sake of simplicity, but a random function with key $[0,511]\\times[512,512+511]$ has the same distribution as a random function with key $[1,512]^2$. Alternatively, it could be considered as tokenizing the first input from 0 to 511 and the second from 512 to 1023. We did not ablate on this but the spirit here is to let the network focus on memorizing instead of distinguishing between the two parts of the key.\n\n> Metric log perplexity is not coherent with label Cross-Entropy Loss\n\nFor a generative process $p$, its perplexity on a sequence $x_1,x_2,\\cdots,x_n$ is $\\exp(-\\frac{1}{n}\\sum_{i=1}^n \\log p_\\theta(x_i\\mid x_{<i}))$. The cross-entropy loss on token $x_i$ is $-\\log p_\\theta(x_i\\mid x_{<i})$, so the log perplexity equals the cross-entropy loss averaged over the sequence. We have refined the caption.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t0CNBNj70k", "reviewer": "Reviewer_LwAU", "summary": "This paper explores the inherent algorithmic capabilities of randomly initialized transformer models, particularly focusing on the functions that can be learned when only the embedding layers are optimized. It demonstrates that even without training the internal transformer layers, these models can perform complex tasks such as modular arithmetic, decimal addition, and associative recall. This challenges the traditional belief that deep training is essential for achieving proficiency in these tasks.", "questions": "In Section 7, the paper discusses storing knowledge within the token embeddings.  [1] suggests that early-site MLPs retain knowledge about the tokens. I am curious whether similar results could be achieved by randomizing the embeddings while optimizing these early-site MLPs.\n\n[1] Meng, Kevin, et al. \"Locating and editing factual associations in GPT.\" Advances in Neural Information Processing Systems 35 (2022): 17359-17372.", "limitations": "The concept presented is intriguing; however, the paper's writing quality needs improvement to meet professional academic standards.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. **Insight into Model Initialization:** The research provides novel insights into the importance of model initialization, revealing that transformers possess intrinsic algorithmic abilities even prior to training.\n2. **Interpretability and Simplicity:** The study shows that these algorithmic tasks can be accomplished with straightforward modifications to the input and output embedding layers, thereby enhancing the interpretability of transformers at the initialization stage.", "weaknesses": "1. **Need for Improved Writing:** The paper's writing style and organization need enhancement. For instance, there is a missing reference in line 19 of the introduction's first paragraph. Additionally, a footnote on page 4 is left empty, and another reference is missing on page 18, line 559.\n2. **Generalization Concerns:** The findings are primarily demonstrated on synthetic tasks. The paper lacks a thorough discussion on the applicability of these findings to real-world datasets or tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful review! The following are our responses.\n\n> **Need for Improved Writing:** The paper's writing style and organization need enhancement. For instance, there is a missing reference in line 19 of the introduction's first paragraph. Additionally, a footnote on page 4 is left empty, and another reference is missing on page 18, line 559.\n> \n\nWe are sorry for these technical issues. We have fixed them and did some more passes on the writings. We also refined the presentation and arguments following suggestions from all the reviewers. If you have any questions with the content of the paper, please let us know.\n\n> **Generalization Concerns:** The findings are primarily demonstrated on synthetic tasks. The paper lacks a thorough discussion on the applicability of these findings to real-world datasets or tasks.\n> \n\nWhile our discussion is primarily focused on synthetic tasks as they correspond to well-defined abilities, we believe our work offers interesting and crucial insights that will also help us understand (fully trained) transformers better. For example, an interesting follow up question would be what abilities are newly developed in training rather than merely unlocked in a similar sense. We also examined language modeling as an example of more complicated and less well-defined task.\n\n> In Section 7, the paper discusses storing knowledge within the token embeddings. [1] suggests that early-site MLPs retain knowledge about the tokens. I am curious whether similar results could be achieved by randomizing the embeddings while optimizing these early-site MLPs.\n> \n\nThis question is unrelated to our current setup as the focus of our study is the expressiveness of the network with random / untrained intermediate layers instead of embedding layers. In fact, we believe the setup where the embeddings instead of intermediate layers are left untrained is much simpler, at least in the high-width regime, as the random embedding matrix will have a high probability possessing a full row rank, from which any embedding matrix could be simulated with the correct linear matrix applied on it. More formally, say the random embedding matrix is fixed to be $E$, when the width is high enough, with high probability for any desired embedding matrix $E’$ we will have some matrix $A$ so that $EA=E’$, hence the embedding and the first linear layer combined could act as $E’$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their detailed, thorough, insightful, and warm-hearted reviews. Your suggestions and criticisms definitely shaped the paper for better. We are especially pleased to see that most reviewers are generally satisfied with our presentation.

During the rebuttal phase, our efforts can be summarized as follows:

- **Establishing Task Difficulty:** We established the difficulty of the algorithmic tasks both theoretically and empirically. Theoretically, we classified the tasks with the Chomsky Hierarchy. Empirically, we measured performance from a baseline model—a linearized transformer. Please refer to our response to Reviewer B9i5 for more details.
- **Additional Experiment on Random LSTM:** Although our experiments primarily focus on random transformers, we conducted an additional experiment with randomly initialized, frozen LSTMs on the needle-in-a-haystack task. This model, with a 1024-width 2-layer setup, was outperformed by both fully trained LSTMs and random transformers, achieving a test accuracy of only 16.85%.
- **Presentation Refinement:** We improved the clarity and formality of Sections 3 and 6, and added discussions on reservoir computing. In the Appendix, we replaced Fig 7 with a box plot, added parameter counts and hyperparameter details, and included the accuracy curve of training. We also expanded discussions on the limitations of our work.

Please find our detailed responses to individual reviewers below. Once again, thank you for your invaluable feedback!

Meta-review: The paper presents an intriguing exploration of what can be achieved by transformer models that are randomly initialized, with only the input and output embedding layers trained. The authors' finding that such randomly initialized transformers can still perform remarkably well across various tasks is both surprising and thought-provoking. The paper is clearly written, and the results challenge conventional assumptions, contributing valuable insights to the ongoing discourse on the capabilities of transformer models.

However, a critical aspect that the paper currently overlooks is the connection to **neural reprogramming**, which is a significant and relevant area of research. I strongly recommend that the authors thoroughly review the existing literature on neural reprogramming. See [1,2] for instance. Integrating these insights into the discussion would not only strengthen the paper but also ensure that it aligns with current research trends. Without this connection, it is difficult to fully endorse the paper for acceptance. Therefore, I suggest a conditional accept, contingent upon the authors addressing this gap in the final version.

[1] https://arxiv.org/pdf/1806.11146

[2] https://arxiv.org/pdf/2202.10629
Decision: Accept (poster)