Algorithmic Capabilities of Random Transformers

Authors: ziqian  zhong
jacob  andreas
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 07:32:31

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.

Main paper: 
 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 to other flexible neural models) at problems involving numerical reasoning [41, 24, 30] , string manipulation [28] , and various forms of in-context learning [7, 17, 1, 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-these 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 in which only the embedding layers are optimized, leaving all other model-internal parameters fixed. If such embedding-only training is successful, it implies that the randomly initialized model's behavior on some subspace already corresponds to the input-output mapping of interest, up to a choice of encoding scheme-in other words, that the randomly initialized model can already perform the target task, and it suffices to find an encoding of inputs and outputs that induces the target behavior.In experiments on seven tasks, we find that embedding-only training yields accurate models for a diverse set of problems spanning arithmetic, associative recall, and sequence generation-in some cases substantially outperforming similarly trained recurrent models. Remarkably, transformer language models trained in this fashion can even produce grammatical (though largely nonsensical) Figure 1 : 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-meaningful tasks. B: Task set. We evaluate the effectiveness of random transformers on a set of model problems involving arithmetic and memorization, as well as modeling of natural language text. natural language text. We explain these results by showing that embedding-only 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-only training is most successful when the target computation can be performed in a subspace that is low-dimensional relative to the ambient dimension of the model's hidden representations.These findings build on a long line of research aimed at understanding the effectiveness of deep networks in terms of their behavior at initialization-e.g. showing that random convolutional networks are high-quality feature extractors [3, 8] , or that overparameterized networks can be pruned down to sparse "lottery ticket" subnetworks that implement the correct behavior [16, 53, 39, 11] . But in contrast to past work, the solutions found by embedding-only 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 at 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 to 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 features 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 of 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. [15] as a way to exploit trained neural network served by existing providers, and it was later used as a resource-efficient domain-transfer technique [45, 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-trivial performance.The lottery ticket hypothesis was first proposed by Frankle and Carbin [16] : a randomly-initialized dense neural network contains subnetworks, the winning tickets, that when trained in isolation can match the performance of the original network. Zhou et al. [53] and Ramanujan et al. [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 [11, 44] . Similar to the hypothesis, our work also focuses on 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 in this paper, Nanda et al. [31] and Zhong et 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 a framework for computation. In the diagram, a blackbox reservoir receives data and updates its inner states there upon. A simple readout mechanism is then trained to map its inner states to 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 et al. [42] for a general overview for reservoir computing and Mantas et al. [29] for a survey on its applications on recurrent neural networks. 
setup: 
 Models We study the behavior of decoder-only transformer language models. In these models, inputs x (represented as sequence of token IDs) are first assigned vector embeddings h (0) = E(x) via an embedding layer E. These embeddings are then passed through a series of m intermediate layers F (1) , F (2) , • • • , F (m) so that h (i) = F (i) (h (i-1) ), with each F (i) (x) computing a hidden representation h (i) via a transformation:h (i) = F (i) (h (i-1) ) = FFN (i) (SelfAtt (i) (h (i-1) )) ,where FFN, SelfAtt are feed-forward and causal self-attention modules as in Radford et al. [38] (layer norms are omitted for simplicity). The final activation h (m) is mapped by a unembedding layer U to a 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 E token and a positional embedding matrix E pos . For an inputx = [x 1 , x 2 , • • • , x n ],we first calculate the initial activationsh (0) = E([x 1 , x 2 , • • • , x n ]) = [E token [x 1 ] + E pos [1], E token [x 2 ] + E pos [2], • • • , E token [x n ] + E pos [n]].Similarly, the unembedding layer is parameterized by a single matrix, and model predictions have the form:p(x n+1 | x 1•••n ; E, F, U ) ≜ softmax U h (m) n [x n+1 ],where (in a slight abuse of notation) E, 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 v and the maximum context length be n, the embedding layers have Ω((n + v)d) parameters as matrix E token and U have shape v × d and matrix E pos has shape n × d, while the full network has an extra Ω(md 2 ) 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.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 E and unembedding layer U . Our experiments thus compare:Full Training: arg min E,F,U x,n≥0 -log p(x n+1 | x 1•••n ; E, F, U ) Embedding-Only Training: arg min E,U x,n≥0 -log p(x n+1 | x 1•••n ; E, F, U )where the arg min is computed approximately via mini-batch stochastic gradient descent. 
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.Modular Addition This task evaluates models' ability to perform integer addition under a fixed prime modulus p = 199. Models receive a sequence of input tokens [a, b] for a, b ∈ [0, p -1] and must compute (a + b) mod p. When over-parameterized models are trained to perform this task, grokking (a long period of memorization followed by an abrupt transition to generalization [36] ) is typically observed [26, 18] . 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 to perform this task.Needle-in-a-Haystack This task evaluates models' abilities to process long input sequences [4] . In the variant we study, models receive as input a sequence of form[m 1 , c 1 , m 2 , c 2 , • • • , m k , c k , m u ].Here, m 1 , m 2 , • • • , m k are distinct markers (k ≤ 30) and c i 's are corresponding values. The input ends with a marker m u (u ∈ [1, k]), and models must search for the previous occurrence of that marker in the input sequence and output the corresponding c u . 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 represented 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 is encoded as a pair with input 9 3 1 7 and output 0 1 1. We use 10-digit numbers in our setup. Past work has found that fully trained models can reliably learn some versions of this task [32, 51, 43] .Parenthesis Balancing (Dyck Recognition) In this task, models are presented with a sequence of parentheses, and must predict whether they are balanced-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 to context-free models of natural language syntax [50, 47] . Note that this task has a vocabulary of size 4 (two parentheses and two labels), so only a very small number of parameters are optimized by embedding-only training. In our setup, the input parenthesis sequences have lengths at most 60.For the modular addition task, we partition the full set of well-formed input-output pairs into a 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.1.Results are shown in Table 1 . Here we compare random transformers with a hidden size of 1024 to fully trained models with hidden sizes of 16 and 1024. For reference, we also compare to a (fully trained) LSTM, a 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 embeddings and unembeddings obtain perfect accuracy on all four tasks consistently across restartssometimes outperforming fully trained recurrent networks (Table 1 ). These results thus point toward the role of a transformer-specific 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).Results are shown in Table 2 . All variants fail to reach perfect accuracy on at least one task. Notably, the variant that only trains the unembedding is unable to reach near-perfect accuracy on any task.Random transformers exhibit interpretable attention patterns A 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 in fully trained models for associative recall tasks (Figure 2 ).In the modular addition task, learned embeddings form circles in low-dimensional subspaces, another phenomenon observed in fully trained models for these tasks [26, 31] (Fig. 3 ). To better understand similarities between these models and their fully trained counterparts, we also computed the distance 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 a distance irrelevance of 0.88, consistent with a Clock-like solution. We plot the projection of the embedding matrix onto its first and third principal components, with tokens colored according to their numeric value.  
random transformers can memorize and generate structured sequences: 
 The preceding experiments evaluated the ability of random transformers to implement single, highly structured input-output mappings. Can these models scale to more challenging tasks, involving memorization of arbitrary associations or even free-form text generation?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 a similar scaling trend holds for random transformers.We study a simple memorization task in which we generate a random mapping from a two-integer key to a one-integer value, with all integers ranging from 1 to 512. Such a function requires 9 bits per input-output mapping to represent (log 2 512 = 9), and may be defined for up to 262144 (= 512 2 ) 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 in these embeddings.We evaluate fully trained and random transformers of width 128 and 2 layers (Table 3 ). We measure success using an 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.Modeling natural language requires both memorization of arbitrary associations (e.g. between words and their parts of speech, as in Section 5.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 on this task?We train models on the TinyStories dataset, a collection of easy-to-understand stories generated by GPT-3.5 and GPT-4 [14] which have been shown to induce fluent text generation when used to train Once upon a time, there was a little boy named Max. Max loved to play with his toy blocks. He had blocks of all colors and shapes. Max liked to build tall towers and big castles. One day, Max was playing with his blocks in his room. He built the tallest tower he had ever made. It 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 was a fun thing to play with. He jumped up and knocked the tower over. The blocks fell all over the floor. Max was very sad. He had worked so hard to build the tower, and now it was gone.Fully Trained Transformer: ... 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 understand why his sister was so upset. He thought he was just playing with them. So, he went to his room and looked for the blocks. After a while, he found them under the bed. Max was so happy that he hugged his sister and his sister. They played together and had a lot of fun. The end.Random Transformer (Completion 1): ... Suddenly, Max started to blow. Max saw a loud noise coming 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 so much fun and proud of himself.Max was happy to be able to help. Max was able to save the tower and help his tower. Max was so proud of himself. Max was happy to have such a good tower and could do it. Example outputs sampled from these models (on a newly generated prompt) are shown in Fig. 5 . 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 SubspacesCan we explain the success of random transformers in the tasks studied above? In this section, we present evidence that embedding-only 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 is distinct from sparsification, as these subspaces are 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 F). 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.2 we constructed a task that explicitly requires operating on high-dimensional spaces, circuit imitation, and indeed, the random transformers exhibit significant performance gap compared to normal transformers. 
low-dimensional hidden representations in algorithmic and memorization tasks: 
 To characterize the geometry of random transformers' internal representations, we present models (trained for all previously described tasks) with a set of randomly chosen inputs and collect their embeddings and hidden representations of these inputs at different layers. Using these representations, we perform two 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 a sparse sub-network).Both fully trained and random transformers exhibit subspace selection but not sparsification (Table 4 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-like circuits that operate in lowdimensional subspaces. On memorization and language modeling tasks, random transformers become much more concentrated on a small subspace than fully trained transformers, thus using a lower effective dimension (Table 4 bottom and Table 5 ). In the language modeling task, more than 30% of variance in hidden representations is explained by 10 components.To provide another window into these results, we characterize how large the hidden representations of a random model must be for it to simulate a random circuit that operates in a low-dimensional subspace.To do so, we first generate a small, random target transformer associated with a distribution over strings p, then perform embedding-only training in a different, randomly initialized transformer to simulate its behavior on some domain of interest by minimizing:arg minE,U E x [KL(p(• | x) ∥ p(• | x; E, F, U )]To construct target models, we begin with the same initialization scheme described in Section 3, then we scale the query and key parameters in the attention mechanism by a factor of 10, and and the feed forward weights and biases by a factor of 20. We also scale the final projection layer by 100/ √ width. (This initialization scheme increases variability of attention patterns and target model predictions across random restarts; see Appendix D.2.2 for additional discussion.) 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 (L1, L2, L3, L4) are collected from trained 4-layer models of width 512. As above, a substantial fraction of variance is explained by a 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 x consist of 40-token sequences generated uniformly at random.Results are shown in Fig. 6 . In general, random transformers can only match the behavior of shallower (3 vs 1) and or significantly narrower (512 vs 128) models, with a sharp increase in error moving from 12 → 16 → 32-dimensional models, suggesting that random transformers may only be able to learn computations that can be performed in lower-dimensional subspaces.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 of 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-dimensional subspaces in which these tasks are performed. However, our experiments have also highlighted several important differences between embeddingonly 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-only models relates to fully trained ones-e.g. whether, during full training, the mechanisms we have discovered here evolve gradually into their fully trained forms, or whether fully trained models use entirely different pathways [10] .We anticipate that these random transformers will also provide an interesting new test-bed for interpretability research, and future work might investigate how learned feature codebooks [12, 6] 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 a source of insight into differences between, and improvements upon, existing neural model architectures.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 a small part of this phase space. It is thus possible that some of the described trends will change as models grow or differ in parameterization details. Outside Section 4, 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 [19] families. Our discussion in Section 6 focused only on linear subspaces and used principal component analysis as the primary tool, but it is also possible that subspaces or latent semantics appear non-linearly which is not addressed by our current analysis.We do not anticipate any ethical concerns associated with these results and we believe understanding AI systems is a crucial step in harnessing their power for good.Roughly 154 GPU days of NVidia V100 were spent on this project.Fix modulus p = 199. We randomly shuffle all possible inputs (p 2 of them) perform a 95%: 5% for training and test set. The split is the same (generated with the same seed and procedure) for all runs across all architectures.For these tasks, we used a stream of training data and a heldout test set. The test set is fixed for all runs across all architectures. The training data is generated on the fly within the same distribution to avoid overfitting.Needle-in-a-Haystack 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 as distinct integers in [127 + 1, 128 + 30] . The final query token is the asked marker (uniformly chosen) plus The opening parenthesis has token id 1, the closing parenthesis has token id 2, and the question mark has token id 3. For the result, 2 signals balanced and 1 signals unbalanced. For example, (())()? in token ids will be [1, 1, 2, 2, 1, 2, 3] and the expected output is balanced, token 2.As sequences of uniformly random parentheses are (a) likely unbalanced (b) easier to validate, we performed a generate-then-mutate 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 a balanced parentheses sequence. We first uniformly choose the number of pairs of parentheses t in [1, 30] . We then generate recursively: when t ≥ 2, with 1/2 probability we generate a (t -1)parentheses sequence recursively and add a pair of parentheses on the outside, with 1/2 probability we uniformly sample u ∈ [1, t -1] and output the concatenation of a u-parentheses and a (t -u)parentheses sequence generated recursively.Mutate With 1/2 probability, we 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 are sampled according to a geometric distribution.The inputs are uniformly random 40-token sequences of integer tokens [0, 511].The target output is the distribution from a target transformer generated as in Appendix D.2.2 below. The width of the target transformer is chosen in [4, 128] (Figure 6 ).For every integer pair x ∈ [0, 511], y ∈ [512, 512 + 511], we generate one data point with input [x, y] and output z uniform in [0, 511]. There is no "test split" as the goal is to memorize all the associations.We used the original train-test split of the TinyStories dataset [14] . We trained a 10000-token BPE tokenizer from the training split alone.We use the GPT-2 [38] implementation of Huggingface [48] . Dropout and weight tying are 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 Gaussians with mean 0 and standard deviation 0.02/ √ 2n where n 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 0-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 be found in Table 6 . After such modifications, we measured the entropy of output distribution on two random inputs. Across all the widths, the mean entropy stays within [2.89, 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.We used textbook long short-term memory [22] with an encoding layer and an unembedding (projection) layer added.For synthetic experiments, we used AdamW optimizer [27] with a learning rate 10 -3 and weight decay 10 -3 . For LSTM a learning rate 5 × 10 -3 is used for faster convergence. For the language modeling task, we used AdamW optimizer with a learning rate 6 × 10 -4 and weight decay 0.1. We clip all gradient norms at 1.For random transformer experiments, the intermediate (query, embedding, unembedding, feedforward) layers are kept as randomly initialized. We use a fixed number of training steps and no early stopping.Modular Addition: 5000 epoches. Batch size 4000.Needle-in-a-Haystack, Decimal Addition, Parentheses Balancing, Circuit Imitation: 10 4 steps of batch size 1000. Again, the training data is generated dynamically.Memorization: 21000 epoches. Batch size 2 15 .Language Modeling: 5 epoches. Batch size 20 and context window 512.In Fig. 7 we provide the test accuracy of needle-in-a-haystack, 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-width models in these three tasks for completeness (Table 7 ). Generally more variances are explained from the top directions as the models are narrower. For example, a 2-layer transformer with intermediate width 2 starts by embed the tokens into the 2-dimensional hidden space, passes them through two transformer blocks of width 2, then linearly 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 2.If we consider the activations as the working memory of the LLM, intuitively a task has low intermediate complexity if it requires a low working memory per token. In the following, we show that all the synthetic tasks we proposed indeed have constant intermediate complexity for 2-layer transformers, thus they only require a constant-dimensional intermediate subspaces to work on.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 ≤ 6.Needle-in-a-Haystack We may use a transformer to implement induction heads [34] as follows:We first store each token'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.Parentheses Balancing Let the given sequence of parentheses bep 1 , p 2 , • • • , p n . Let x i = i j=1 c i where c i = 1 if p i isan open parenthesis and c i = -1 if p i is a closing parenthesis. The given sequence is a valid parentheses sequence if and only if x n = 0 and min n i=1 x i = 0. In a transformer, we can first compute x i /i with a uniform attention. Then, we attend to the position with minimum x i /i, breaking ties by position (let the attention on i pre-softmax be T (-x i /i + ϵ • i) for large enough T and small enough ϵ > 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 x i /i = 0 by computing squares of differences. The intermediate complexity for 2-layer transformers is thereby again constant. (note that a different construction for bounded-depth Dyck was given in [50] )Let the reversed list of digits of two numbers and their sum bea 1 , a 2 , • • • , a n , b 1 , b 2 , • • • , b n , and c 1 , c 2 , • • • . Let x i = i j=1 a j 10 j-i , y i = i j=1 b j 10 j-i , z i = i-1j=1 c j 10 j-i , we have c i = (x i + y i -z i ) mod 10: a + b ≡ i j=1 10 j-1 (a j + b j ) (mod 10 i ), (a + b) mod 10 i-1 = i-1 j=1 c j 10 j-1 , and c i = ((a + b) mod 10 i -(a + b) mod 10 i-1 )/10 i-1 .Prepare: Take small ϵ > 0. For positions 1, 2, • • • , n, let the positional embedding of position i be [1, 10 i , 10 -i ϵ]. 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 α i = 1 i i j=1 a j 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, so the contribution from the j-th position to the i-th position is 1 Zi e ϵ10 j-i ≈ ϵ 1 Zi (10 j-i + 1) (e c ≈ 1 + c for 0 < c ≪ 1) for normalizing constant Z i , we can then calculate β i = ϵ 1 Zi i j=1 a j (10 j-i + 1). We then have x i = Zi ϵ β i -iα i which we will utilize in the next step. Similarly, we can have y i and z i ready in the corresponding position (position of b i and c i-1 ). Generate x i + y i -z i : In the second layer, attend from the position of a i and b i at the position of c i-1 . Specifically, set the attention from the a k 's position to the c i-1 's position be ϵi -Λ cos((ki)/n) = ϵi -Λ(cos(k/n) cos(i/n) + sin(k/n) 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 i-1 's position be 1 pre-softmax. The attention from a k to c i-1 will be negligible if k ̸ = i and will be proportional to ϵi post-softmax for k = i. We can then calculate -iα i from it and similarly Zi ϵ β i , and thus x i , y i and z i .Approximate the Answer: As x i + y i -z i is an integer from [0, 19] and we can also compute an affine transform of it, we may now simply proceed with the universal approximation theorem. As an example, in ReLU networks we may check ifx i + y i -z i = v by noticing ReLU(x i +y i -z i -(v+1))+ReLU(x i +y i -z i -(v-1))-2ReLU(x i +y i -z i -v) = [x i +y i -z i = v],So to create an indicator variable [x i + y i -z i = 1] we simply need to generate x i + y i -z i ,x i + y i -z i -1, x i + y i -z i -2, pre-ReLU.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.Chomsky hierarchy has been found to be predictive of the neural architectures' performances, and especially length-generalization performances, in algorithmic setups [13] . We list the Chomsky hierarchy of the synthetic tasks we picked in Table 8 .Needle-in-a-Haystack 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 to be equal-lengthed) are considered within the language.We also examined a baseline with linearized transformer. In this variant of transformer, the attention matrix (softmax(QK T )) is replaced with a lower diagonal matrix of 1s. In other words, the attention is replaced by a simple token prefix sum mechanism. We tested such transformers with width 512 and 2 layers on the synthetic tasks as a baseline performance. The result is shown in Table 9 . We can see that such transformers have large performance gaps with normal transformers, confirming the difficulty of our chosen tasks.Accuracy (%) The accuracy curve in the memorization task during training is shown in Fig. 8 . Training of both transformers has converged. Justification: We plan to release code and data after finalizing.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We include the 80% CI bars in Appendix E. Some experiments are 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean. 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: We cited the original papers for each asset. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.Code is available at https://github.com/fjzzq2002/random_transformers. 
 
 Appendix:  


Decision: 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

Reviews: review: paper_summary: paper_summary: **Update after rebuttal:**
My 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.

The 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.
strength_weakness: strength_weakness: * 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)
* 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.
* (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.
* (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.

**Verdict:**
The 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. 

**Improvements:**
1. 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.
    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. 
    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).
    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.
2. More caveats:
    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.
    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.
    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.
3. 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.
4. 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.
questions: questions: **Questions and minor comments:**

1. 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.
2. 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?
3. 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?
4. 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.
5. 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.
6. L19: missing reference.
7. L128 (nit): While general Dyck recognition requires context-free grammars, parenthesis balancing with a single type of parenthesis should be context-sensitive, right?
8. For Table1 and Table2: state the number of trainable parameters for each setting (either in the table or the appendix).
9. 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.
10. 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.
11. 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?
12. 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.
13. 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.
14. (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.
15. NeurIPS Checklist, Q2 (Limitations): The reference in the justification to the limitations section in the appendix is broken.
limitations: 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’.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* 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.
questions: 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The 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).

The 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.
questions: questions: -	Algorithmic 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).
-	“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).
-	The analyses on the low-dimensional sub-spaces should be presented in a more formal and clear way.
-	The 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.
-	It 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).
-	Some error bars in Fig. 7 seem too large or even misaligned. Is that a formatting problem or does it indicate poor convergence of training?
-	In 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.
-	The metric described in the caption of Fig. 4 (log perplexity) is not coherent with the y-axis label (Cross-Entropy Loss). Please clarify.
limitations: limitations: The authors properly discuss the possible limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. **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.
questions: 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.

[1] Meng, Kevin, et al. "Locating and editing factual associations in GPT." Advances in Neural Information Processing Systems 35 (2022): 17359-17372.
limitations: limitations: The concept presented is intriguing; however, the paper's writing quality needs improvement to meet professional academic standards.

Comments: title: Thank you for the detailed clarifications, answers, and additional experiments/results.
Samples in the circuit imitation task
comment: I thank the authors for addressing my questions. I acknowledge that I have read the reviews posted by other reviewers and the authors' rebuttals. I will raise my score.
The extensive rebuttal has addressed all of my main issues, clarified some of my misunderstandings, and has added significant additional data (that was asked for). I agree with the answers / comments and do not have any further large open issues. I will therefore raise my score to a 7 since I think the paper provides some very interesting insights into capabilities of untrained transformers, and thus indirectly into their inductive biases, which is a very timely and important topic. I would not be surprised if the paper triggers quite a bit of follow-up work. 

**Minor:**
Re "Hierarchy of parenthesis balancing" - ignore my initial comment (not sure what I had in mind when I wrote it). As you correctly say, Dyck languages are context-free (which is a subset of context-sensitive) and parenthesis balancing is non-regular (context-free).
I appreciate the authors response, which addressed all my questions. I increase my score.
I appreciate the Authors' willingness to address the issues raised in my review and their replies to my comments. Having read the Author's responses and the comments posted by the other reviews, I opted to maintain my overall score: I still think this is a borderline paper, presenting some interesting and original ideas but (in my opinion) not always with the proper experimental support. Regarding the use of the term "algorithmic", I can see the Author's point but I believe that using it in the title and as a main argument could be misleading, since the paper does not contain experiments demonstrating a non-trivial degree of OOD extrapolation.
> Fig. 6: Clarify how large the KL divergence gap is.

We sampled some inputs (not cherry picked) and the following are the output distributions from the target model and the fully-trained / random transformers. Displayed are the top 5 entries. The KL and TVD at the end of rows are KL divergence and total variational distance (half of L1 distance) from the target distribution to the distribution from the transformers. Subjectively a KL of 0.2 is already quite bad.

```
input			 [9, 269, 291, 196, 125, ..., 261, 198, 248, 71, 320]
64 width target dist	 261(14.16%) 391(8.30%) 114(5.84%) 140(3.73%) 295(3.23%) 
w128_f0_l1(kl 0.117)	 261(9.97%) 114(5.35%) 391(4.39%) 295(3.79%) 140(3.58%)  		KL=0.07 TVD=0.15
w512_f0_l3(kl 0.001)	 261(13.78%) 391(8.43%) 114(6.20%) 140(3.57%) 295(3.26%)  		KL=0.00 TVD=0.01
w512_f1_l1(kl 0.247)	 261(10.77%) 295(5.19%) 27(4.95%) 134(3.60%) 350(2.91%)  		KL=0.17 TVD=0.24
w512_f1_l3(kl 0.258)	 261(9.16%) 114(5.89%) 295(5.31%) 27(4.65%) 391(3.22%)  		KL=0.14 TVD=0.21

input			 [354, 139, 431, 379, 334, ..., 240, 455, 390, 492, 218]
64 width target dist	 393(65.93%) 142(2.90%) 130(1.65%) 379(1.55%) 413(1.29%) 
w128_f0_l1(kl 0.117)	 393(53.46%) 142(3.02%) 413(2.99%) 130(2.28%) 472(2.23%)  		KL=0.08 TVD=0.16
w512_f0_l3(kl 0.001)	 393(66.30%) 142(2.70%) 379(1.55%) 130(1.54%) 413(1.21%)  		KL=0.00 TVD=0.01
w512_f1_l1(kl 0.247)	 393(19.74%) 130(5.98%) 413(4.44%) 142(2.10%) 41(2.02%)  		KL=0.65 TVD=0.51
w512_f1_l3(kl 0.258)	 393(13.00%) 130(7.41%) 413(4.24%) 142(2.43%) 152(2.28%)  		KL=0.90 TVD=0.57

input			 [268, 259, 117, 487, 483, ..., 59, 360, 419, 162, 333]
64 width target dist	 500(9.20%) 333(6.67%) 171(4.67%) 462(4.33%) 202(3.98%) 
w128_f0_l1(kl 0.117)	 500(9.89%) 101(5.20%) 39(4.61%) 462(4.23%) 155(3.99%)  		KL=0.17 TVD=0.22
w512_f0_l3(kl 0.001)	 500(9.89%) 333(7.00%) 171(4.87%) 462(4.20%) 202(4.00%)  		KL=0.00 TVD=0.02
w512_f1_l1(kl 0.247)	 500(8.47%) 101(4.10%) 462(3.68%) 39(3.21%) 333(3.05%)  		KL=0.14 TVD=0.21
w512_f1_l3(kl 0.258)	 500(8.00%) 101(5.95%) 39(4.75%) 171(3.70%) 462(3.46%)  		KL=0.19 TVD=0.25

input			 [377, 166, 258, 295, 300, ..., 106, 117, 23, 33, 159]
64 width target dist	 401(6.64%) 261(5.30%) 70(4.31%) 219(3.74%) 82(3.48%) 
w128_f0_l1(kl 0.117)	 401(6.73%) 29(5.05%) 261(3.30%) 503(3.04%) 386(2.89%)  		KL=0.15 TVD=0.21
w512_f0_l3(kl 0.001)	 401(6.84%) 261(5.37%) 70(4.30%) 219(3.73%) 82(3.56%)  			KL=0.00 TVD=0.01
w512_f1_l1(kl 0.247)	 29(5.72%) 401(5.24%) 261(3.41%) 295(3.16%) 162(2.65%)  		KL=0.20 TVD=0.27
w512_f1_l3(kl 0.258)	 401(6.22%) 29(5.46%) 295(5.00%) 261(4.02%) 162(2.79%)  		KL=0.25 TVD=0.29

input			 [214, 431, 443, 153, 276, ..., 304, 132, 315, 213, 330]
64 width target dist	 393(20.05%) 37(15.42%) 41(10.19%) 428(4.32%) 103(2.44%) 
w128_f0_l1(kl 0.117)	 393(21.93%) 41(12.27%) 37(7.86%) 428(3.89%) 173(2.47%)  		KL=0.09 TVD=0.16
w512_f0_l3(kl 0.001)	 393(20.26%) 37(15.12%) 41(10.68%) 428(4.15%) 103(2.38%)  		KL=0.00 TVD=0.01
w512_f1_l1(kl 0.247)	 41(13.53%) 393(11.35%) 37(8.00%) 428(5.61%) 462(2.78%)  		KL=0.19 TVD=0.26
w512_f1_l3(kl 0.258)	 41(10.51%) 393(10.18%) 37(9.57%) 428(5.00%) 54(3.95%)  		KL=0.21 TVD=0.26

input			 [6, 159, 424, 316, 370, ..., 158, 23, 70, 324, 214]
64 width target dist	 70(5.27%) 386(4.85%) 439(4.76%) 29(3.97%) 215(3.96%) 
w128_f0_l1(kl 0.117)	 215(6.72%) 386(6.50%) 70(4.02%) 29(3.61%) 39(2.48%)  			KL=0.11 TVD=0.19
w512_f0_l3(kl 0.001)	 70(5.25%) 386(4.77%) 439(4.75%) 215(4.03%) 29(3.76%)  			KL=0.00 TVD=0.02
w512_f1_l1(kl 0.247)	 215(7.09%) 386(7.05%) 357(3.14%) 168(2.50%) 230(2.47%)  		KL=0.25 TVD=0.27
w512_f1_l3(kl 0.258)	 386(6.14%) 215(4.86%) 29(2.81%) 357(2.61%) 401(2.26%)  		KL=0.25 TVD=0.27

input			 [150, 284, 450, 41, 414, ..., 415, 307, 394, 495, 495]
64 width target dist	 130(9.15%) 485(6.04%) 171(4.28%) 261(3.96%) 101(3.64%) 
w128_f0_l1(kl 0.117)	 425(6.22%) 485(5.24%) 130(4.67%) 132(4.13%) 65(3.71%)  		KL=0.11 TVD=0.19
w512_f0_l3(kl 0.001)	 130(9.75%) 485(5.86%) 261(4.11%) 171(4.07%) 101(3.47%)  		KL=0.00 TVD=0.02
w512_f1_l1(kl 0.247)	 425(10.05%) 130(6.46%) 132(5.33%) 65(3.84%) 485(2.92%)  		KL=0.23 TVD=0.29
w512_f1_l3(kl 0.258)	 425(9.15%) 130(7.98%) 132(4.38%) 485(4.15%) 101(2.79%)  		KL=0.16 TVD=0.23

input			 [219, 428, 440, 198, 404, ..., 468, 252, 223, 37, 204]
64 width target dist	 41(10.26%) 386(7.45%) 401(6.32%) 496(5.48%) 357(3.59%) 
w128_f0_l1(kl 0.117)	 41(8.47%) 401(7.66%) 386(5.60%) 133(3.48%) 413(2.33%)  		KL=0.10 TVD=0.17
w512_f0_l3(kl 0.001)	 41(9.87%) 386(7.50%) 401(6.51%) 496(5.64%) 357(3.62%)  		KL=0.00 TVD=0.02
w512_f1_l1(kl 0.247)	 386(11.59%) 401(7.91%) 41(4.64%) 413(2.83%) 280(2.12%)  		KL=0.34 TVD=0.32
w512_f1_l3(kl 0.258)	 386(8.80%) 401(6.11%) 41(4.32%) 357(3.04%) 413(2.96%)  		KL=0.34 TVD=0.32
```