Algorithmic Capabilities of Random Transformers

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.

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. 2. **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. 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

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.

Rating

4

Confidence

3

Soundness

3

Presentation

1

Contribution

2

Limitations

The concept presented is intriguing; however, the paper's writing quality needs improvement to meet professional academic standards.

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.

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

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

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors properly discuss the possible limitations of their work.

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.

Strengths

* The observation that training only the embedding layers can lead to noticeable accuracy on tasks is interesting. * 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. * 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

* 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?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

Yes

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.

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. * Range of interesting tasks, which can be related to previous results in the literature and span a range of capabilities. * 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) * 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 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.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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’.

Thank you for the detailed clarifications, answers, and additional experiments/results.

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