Transformers need glasses! Information over-squashing in language tasks
Authors: Federico Barbero
Andrea Banino
Steven Kapturowski
Dharshan Kumaran
João Guilherme Madeira Araújo
Alex Vitvitskyi
Razvan Pascanu
Petar Veličković
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformers
Over-squashing
Large Language Models
Primary area: natural_language_processing

Abstract: We study how information propagates in decoder-only Transformers, which are the architectural foundation of most existing frontier large language models (LLMs). We rely on a theoretical signal propagation analysis---specifically, we analyse the representations of the last token in the final layer of the Transformer, as this is the representation used for next-token prediction. Our analysis reveals a representational collapse phenomenon: we prove that certain distinct pairs of inputs to the Transformer can yield arbitrarily close representations in the final token. This effect is exacerbated by the low-precision floating-point formats frequently used in modern LLMs. As a result, the model is provably unable to respond to these sequences in different ways---leading to errors in, e.g., tasks involving counting or copying. Further, we show that decoder-only Transformer language models can lose sensitivity to specific tokens in the input, which relates to the well-known phenomenon of over-squashing in graph neural networks. We provide empirical evidence supporting our claims on contemporary LLMs. Our theory points to simple solutions towards ameliorating these issues.

Transformers need glasses! 6d Information over-squashing in language tasks
Federico Barbero*
Andrea Banino Google DeepMind abanino@google. com
University Oxford
federico. barbero@cs, ox ac. uk
Steven Kapturowski Google DeepMind skeptturowski@@gogleeecco
Dharshan Kumaran Google DeepMind dkumaran@google.com com
João G.M. Araújo Google Docp.ind
j joagui@googgee com
Alex Vitvitskyi Google DeepMind avlife@google.com com
Razvan Pascanu Google DeepMind razp@google.. com
Petar Veličković Google DeepMind petarvägoogle. com
A Abstract
We study how information propagates in decoder-only Transformers, which are the architectural backbone of most existing frontier large language models (LLMs). We rely on a theoretical signal propagation analysis specifically, we analyse the representations of the last token in the final layer of the Transformer, as this is the representation used for next-token prediction. Our analysis reveals representational collapse phenomenon: we prove that certain distinct sequences of inputs to the Transformer can yield arbitrarily close representations in the final token. This effect is exacerbated by the low-precision floating-poits formats frequently used in modern LLMs. As a result, the model is provably unable to respond to these sequences different ways leading to errors in, e.g., tasks involving counting or copying. Further, we show that decoder-only Transformer language models can lose sensilivity to specific tokens in the input, which relates to the well-known phenomenon squashing in graph neural networks. We provide empirical evidence supporting our claims contemporary LLMs. Our theory also points to simple solutions towards ameliorating these issues.
Introduction
In recent years the field of Natural Language Processing (NLP) has been revolutionised through the introduction of Transformer-bbsed architectures [30]. Large Transformers trained on some version of next-token prediction, known as Large Language Models (LLMs), have demonstrated impressive performance across different tasks, including conversational agents [10, 19]. understanding multi-modal inputs [1], and code completion [16]. Most contemporary LLMs specifically focus on the decoder part of the original Transformer architecture, and are commonly referred to as decoder-only Transformers. Consequently, we focus primarily on such models this paper.
However, despite the impressive performance of Transformers, recent works have uncovered surprising failures that may point to fundamental issucs in their architecture. For instance,
*Work performed while at Google DeepMind.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

(D)
1
0
11
(C)
111
V2
1111
LES
1111
1111...11
1lv50 Willooo <<
113
(a) Representational Collapse
(b) Over-squashing
Figure 1: (a) Representational Collapse (Theorem 4.2). From top to bottom, we have a series of sequences given to Transformer architectures, each comprising repeated tokens with a single 0 token at the end. The color and proximity of the curved lines illustrate how these representations converge sequence length increases. (b) Over-squashing (Theorem 5.1). Due to the architecture of decoder-only Transformers, tokens that are earlier in their imput sequence will have significantly more paths through which their data reach the representation used for next-token prediction, leading to overrsquashing. This effect is depicted here for an early token (blue) and later token (red) in a five-token sequence.
Transformer-basee LLMs scom to be particularly challenged by scemingly simple tasks requiring counting [32] or copying elements along imput sequences [17]. We find it important to study such failure cases, as these operations are fundamental building blocks of computation, and they are often necessary for solving reasoning lasks. A common strategy assist LLMs in solving such lasks is to supply them with 'tools' (e.g. 25). We argue that, while tool use will certainly help, it is still important to improve base model capabilities in this regard, because oftentimes, even producing accurate inputs to a tool may require complex reasoning operations. Specifically, often we need to copy some part of the Transformer's input into tool if the base model struggles with robust copying, even this operation can be in peril.
Accordingly, find it important to explain why docoder-only Transformers do not perform well when it comes to such problems not just as an intellectual endcavour, but also to help guide further practical improvements. While many works have studied the computational capabilities ies of Transformers [22, 18), they often make assumptions which do not correspond to present. practical limitations, such infinite inoating-point precision hardd attention', making their conclusions less directly practically applicable.
In this work, take a different approach and study what information be contained in the representation of the last token at the last layer, as this ultimately the information that will be used for next-token prediction the fundamental mechanism through which modern Transformer LLMs perform training and inference. In particular, we show that for cortain distinct sequences, their last-token representations can become arbitrarily close to each other. This leads to a representational collapse, exacerbated by the lower- ppeei-preissoo floating point types typically used by modern LLM stacks. As result Transformers incorrectly produce the same tokens on these sequence pairs see Figure (a).
Furthermore, reveal that the computation graph employed by decoder-only Transformers, with its unidirectional causal mask, contributes to the observed representational collapse. This unidirectional flow of information, converging at the final token, is in fact likely to lead to a loss information due to over-squashing, an effect that is well studied in graph neural networks (GNNs) 2, 29, 8, 3, 11], and related to vanishing gradients [14, 13). We hope that this result will be of independent interest to the GNN community, as a practical application of over-squashin results at scale. Finally, these issues are likely practical interest, and propose simple solutions directly stemming from theoretical study-to to help alleviate them.
provide supporting empirical evidence that
In summary, our paper provides the following contributions:
Theoretical analysis of decoder-only Transformer limitations: we formalise the concepts of 'representational collapse' (Section 4) and 'over-squashing (Section 5) in the context of Transformer-baa based architectures.
2

---

Impact of floating point precision: we explore how low floating point precision exacerbate the identified theoretical issues, causing them manifest even in relatively short input sequences.
Empirical validation of theoretical analysis: our theoretical findings are supported by real- world experiments conducted contemporary L.Ms,, demonstrating practical implications of the limitations we identified.
Background
In this work, study a class of Transformers which we believe forms the basis for large mumber of current LLMs. We let Q, V Raxd be the query, key, and value matrices respectively n tokens and d dimensions. We denote with qi k;, V; IR the d-dimensional query, key, and value vectors of the i-th token. We let Pij E R2e be the 2e-dimensional positional encoding information between tokens and j. We focus
the case in which the positional encodings are bounded, which is the case for the large majority of positional
encodings used in practice [26, 30]. The Transformer model we consider computes the values, for a single head, of the i-th token at the L-th Transformer layer v; (2) as
(2) exp (k (q kj Pij
49 = Σ aij
norm
(8)
(v!")
v! with 0jj
Ewss exp kk (q k! Piwr
jel
((t1)) = (0) [norm]
(E)
(1)
+
for a function k. : Rd x Rd x 2e - mapping queries, key, and positional encoding information to scalar value, MLP sb RR and normalization functions at the 6-th layer norm (f) and norm? (E) This specific interleaving of components is often referred to as Pre-LN Transformer [34]. We can view the output of the L-th layer of a Transformer as a sequence of d-dimensional vectors v(f) = (v( v(()). Importantly, duc to the causal attention mechanism, the vector (")) will only depend elements v (f-1) for j. We can group the attention weights into an attention matria the f-th layer which we define element-wise as A
3/ = This a row-stochastic triangular matrix that can also be interpreted as a probabilistic directed graph. After the last transformer block normalization is applied to the token representations:
y: = normg (L)
We note that the next-token prodiction usually depends purely yn the final represcntation of the last token.
Existing theory Transformers. The theoretical representational capacity of Trans- formers has become a popular area of study, providing interesting results on what classes of problems they are able to model. For instance, it has been pointed out that Transformers are not Turing-complote, but one can apply modifications which make Transformers Turing- complete under certain assumptions [6]. Works have also shown that Transformers using hhard attention' which replaccs softmax with onc-hot vectors alongside the use of infinite precision makes Transformers Turing-compled cuses on the more standard setting of Transformers using sofl-attention and finite precision, and shows the linitations imposed by it.
[22]. This contrasts with our work, which fo-
Works have also tried to study transformers capabilities through the lense of formal languages, such as Weiss et al. [33], which develops computational model of what transformers can represent in an analogous way to how Recurrent Neural Networks are associated with finite automata, and then derive an implementable programming language that represents
Note that rely abuse of notation. We ignore the linear projections used to compute the value (0) from the output of layer below / 1. This will not change our derivations, but would otherwise make notations more cumbersome.
3

---

A
B
Copying first and last tokens
Copying last token with hints
Copying last in interleaved sequence
X
X
200
400
500
100
400
500
100 200
300
400 500
Sequence Length
Sequence Length
Sequence Length
First Token
Last Token Hint
[ssq] length + [0]
Last Token
Last Token w/ Hint
[1,0]"seq length + [0]
Figure 2: Results on simple copying tasks. (a). Gemini was prompted to predict the last token (diamond) of sequences '1...10' or the first token (square) of sequence '01...1'. (b).
Same as (a) but with hints (see 3.2 for details) (c). Same as (a) but the sequences have interleaved Os and 1s. See C.1 for extra details
that model. Following that, Delétang et al. [7] place transformers within the Chomsky Hierarchy, showing that they are quite limited and cannot learn the decision problem for simple languages, which prompted authors to show that Transformer LIMs can perform substantially better they generate number of decoding tokens linear in the problem input size, through scratch-pad, Chain-of- Chain-of-Thought (CoT) or similar [18]. Finally, Peng et al. [21] show that the Transformer block with finite precision is fundamentally limited in its ability to represent compositional functions and solve simple problems that require it. Our work similarly analyses the Transformer's 's inability to solve simple computational tasks, and proves that even with techniques like Chain-of Maain-of-Thiee Thought that inability persists it is inherent to the combination of architecture, next-token prediction, and limited floating point precision.
Decay in attention mechanisms. Works have also studied the limitations of self-attention by showing that it can reach pathological states that limit what transformers are able to learn. For instance, it has been show how great reduction in the attention entropy can lead to unstable training occurring early, but even when occurring later training it can still lead to significantly lower performance [35]. Further, it has been shown that specific tokens can strongly concent.rate attention, leading to transformers being unable to learn to process simple languages, like PARITY and DYCK [12]. Our work will similarly focus showing how Transformers end-up effectively ignoring many tokens in their input which leads them to fail to solve simple computational problems, studying such phenomenon by directly analysing the representational capacity.
Over-squashing. Graph neural networks (GNNs) are neural networks designed to operate over graph structures. Importantly, Transformers, may be seen as types of altention-baser GNNs operaling over specific types of graphs. The difficulties of propagating information over a graph have been thoroughly analysed, with a notable phenomenon being that of over- squashing [2, 29, 8, 3). Over-squashing refers to the fact that propagating information over certain graphs that exhbit 'bottlenecks' is likely to induce a 'squashing' of information. This can be made more precise by studying this effect via the notion of a commate time [11] the expected number of steps that a random walk takes to travel from a node to another node and back. Information travelling between nodes with higher commute time will be squashed more.
common way to mcasure weerssqashhng is by looking at how sensitive the representation X of node after L GNN layers is to the initial representation (0) of another node u. In particular, the partial derivative ²x!4) /²x!!) may be shown to decay, especially for nodes with high commute times between them. Our work may be seen as acting as bridge between the analyse
well-studied phenomenon of squassing in GNNs and the loss of information in decoder-only Transformers specifically for language tasks. Note that this type of derivation is typical in the study of vanishing gradients for recurrent models well [14, 5, 20, 13).
3 Motivating Examples
This section presents a series of experiments focused on copying and counting tasks. These experiments reveal surprssing failure cases in modern decoder-only Transformer architectures,

---

Sum +
Count Ones 1...1
Count Ones in 1|0
Count Words in Sentence
175
175
175
175
Col
150
150
150
150
128
125
125
125
100
50
50
50
25
25
25
0
100
200
100
200
100
200
100
200
Absolute Error
Coft Col' Zero Shat
175
1715
175
150
150
150
150
125
125
125
125
1.00
100
100
100
78
75
35
25
0
0
100
200
100
200
100
200
100
200
Coll Shot
1.50
1.50
150
150
125
1255
125
125
100
100
100
100
7.5
75
755
75
50
50
0
100
200
0
100
200
100
200
100
200
Sequence Length
Figure 3: Gemini 1.5 being prompted to sum 1 + .... 1 (Column 1). Count the number of ones in a sequence of 1s (Column 2), Count the number of ones a sequence of ones and zeroes (the sequence is Bernoulli sequence with probability of sampling one being 0.7) (Column 3), and to counter the number of times a word appears sentence (Column 4).
providing concrete evidence that motivates the theoretical analysis presented in the following sections.
We start by providing motivaling examples that show surprisingly simple failure cases of frontier LLMs specifically on copying (Section 3.1) and counting (Section 3.2) tasks. By copying specifically mean tasks that involve the 'copying' 'recalling' of single or multiple tokens from the prompt. Instead, by counting, we mean the task of counting how many times specific token appears in a sequence. We focus evaluation Gemini 1.5 [10) as our frontier LLM (referred as Gemini) and later analyse the internal representations of the open-sourced Gemma model [27]. The goal is to showcase intriguing failure cases which will motivate our signal propagation analysis.
3.1 Copying
In this Section, we present surprising results on simple copying tasks. In particular, we focus on tasks that involve the copying of a single loken - Lee. what is the token occurring at particular position? The copy of a single token is in principle the most straightforward type of copying task, but still requires the LLM to accurately identify the token based on prompt and to then propagate its information correctly.
Importantly, we study cases in which the LLM is prompted to copy tokens either at the start or at the end of sequence. We avoid tasks that involve the copy of tokens at the 'n-th' position as most fronticr LLMs do not have absolute positional information, making it very challenging for them to solve tasks that require absolute position. We focus tasks that involve sequences of 'zeros' and 'ones' growing in length with specific palterns.
In Figure 2 (a), we prompt. Gemini to copy the last element of sequence 'I... 10' or the first element of a sequence '01... The answer for both zero, but we progressively grow the number of ones. We observe how the task seems considerably easier when asked to return the first rather than the last element. Surprisingly, already at a sequence length only 300 elements, Gemini incorrectly starts to output 'one' when trying to copy the last element. In Figure (b), we show that providing hints in the form of: " *Hint* It's not necessarily a 1, check carefully", helps significantly with the performance. Finally, in Figure 2 (c), we show that replacing the constant sequence of ones with alternating ones and zeros scems to also help. We refer to the Appendix (Section C.1) for further details on the experiments.
These three motivating experiments seem to point towards type vanishing of information, caused by the growing number of ones dominating the sequence. Interestingly, such
5

---

Group
Truc Allswer
Predictions Col
Prodictions
15
Frequency
10
50
100
125
150
175
200
Value
Figure 4: Frequency of different outputted values for Gemini 1.5 for the counting lasks. The large density at 100 suggests that Gemini is likely not counting, but instead possibly performing some crude form of subitising.
vanishing of information effect (a) seems to depend on the position in the sequence, (b) seems to be affected by the prompting, and (c) by the items that make up the sequence. We will later argue how all three of such observations can explained by our theoretical analysis.
3.2 Counting
We now turn attention to counting problems, i.e. tasks of the form given specific sequence, how many times does a particular token appear? Such problems are related to copying in the sense that they also require careful consideration of individual tokens in the sequence as ignoring even a single token may potentially lead to an incorrect output.
We consider four different tasks: (i) Summing +..... 1, (ii) Counting the nunber of ones in a sequence of ones, (iii) Counting the number of ones in a sequence ones and zeros, with ones being sampled with 70% probability, and (iv) Counting the number of times specific word appears in a sentence. We consider predictions of an LLM which (1) Is instructed to only output the answer, (2) Is prompted to break down the problem (CoT-no-shot),, and (3) Is prompted to break down the problem with few-shot in-context examples (CoT-few-shot) We refer to the Appendix (Section C.1) for more detailed description of the tasks.
Results are presented Figure 3. It clear that the performance rapidly deteriorates with the sequence length. It is also interesting to see that the error seems to increase with the sequence very rapidly. For instance in task (i), the LLM is quite likely to predict the value of '100' once the sequence reaches a size around larger than 100. Such observation provides motivating evidence for the argument that Transformers may not be in fact mechanically counting but rather perform type of crude subitising, This explains why arguably 'common' mumbers such as 100 are much more likely to be outputted by the LLM and why in tasks such as (i) and (ii) the values near 100 have relatively lower error. This does not happen in task (iii) as the response should actually be around 70% of the sequence length due to the sequence sampling procedure, explaining why the absolute error actually seems to increase around a sequence length of 100. Figure 4 further showcases this issuc, more clearly showing how 100 is by far the most common response.
4 Representational Collapse
We start our theoretical analysis by showcasing a type of loss of information which we call representational collapse. More precisely, show that under certain conditions, can find distinct sequences such that their final representations of the last tokon at the last layer become arbitrarily close the sequence length increases. As Transformer models operate over finite machine precision, this points to a fundamental representational incapacity of Transformers to distinguish certain prompts if the sequence long enough.
The key intuition that two sequences are similar everywhere except at the last token, as the sequences get larger, their final representations will become closer and closer until they

---

reach critical point which is below floating point precision. In other words, solving certain tasks would require infinite floating point precision. We will later show how this phenomenon is not only theoretical, but also occurs in practice sequences of reasonable length. In the Appendix (Section 4), we relate representational collapse the L1 distance or total variation between the softmax distributions of the two sequences. We start by presenting result that shows that the 1 difference tends to 0 as the sequence length grows, under some assumption on the sequences. We point to the Appendix (Lemma B.2) for the complete statement.
Lemma 4.1 (Informal). Consider two sequences x, x* E IR" such that lim,- z |x, x 0.
Then, the L1 difference of their softmar tends to O.
We now show, using Lemma 4.1, that we can find distinct sequences that will have arbitrarily close final representations. In particular, as language models often operate in low floating regimes, i.e. bf16, this can practically become catastrophic. The result is sunmarised in Theorem 4.2, which describes what we call representational collapse in this work. The complete statement is reported in the Appendix (Theorem B.3).
Theorem 4.2 (Representational Collapse informal). Let v(u) E Bnxd be a sequence and v*(0) E g(=+l)xd be another sequence equal to v(0) with the last token of v(0) repeated. Assume that the positional encoding information decays to O with the distance. Then, their representations become arbitrarily close as increases.
Theorem 4.2 shows that it becomes increasingly challenging for a Transformer to distinguish two sequences that only differ via repeated last token. We note that the repetition of the last token a technical consideration to show this direct representational collapse. As we will later show in Section 5.1, it is particularly problematic in general to depend on the last token due to a type of topological 'squashing' present in decoder-only Transformers.
Measuring representational collapse. We report experiments showcasing representa- tional collapse by measuring the internal representations of Gemma 7B [27]. For two sequencos v0) and (*( we report their difference in representation at the last layer ||v(2) - vz( llz averaged out over each head, alongside the minimum and maximum over each head. Figure shows the collapse occuring on (a) prompting the model to count the number of ones in a sequence of ones, with one having an additional one, and (b) prompting the model to count the number of ones for a sequences with digits sampled uniformly ending with either a single one two ones. The repeated digits seem to make the collapse occur much sooner with se- quence length of around 50 being near machine precision, while varying the digits seems to de- lay such collapse, but downward trend is maintained with respect to the sequence length.
Quantisation and Tokenisation. common technique used to speedup the inference of an LLM is that of quanlisation, a process that construcls an approximate version of an LLM that operates over lower precision datatypes. This helps drastically improve the inference speed of LLMs as modern accelerators produce significantly more FLOPs over lower precision datatypes. Of course quantisation usually comes at a cost. Our theoretical analysis points towards potentially catastrophic loss in representation due to quantisation. In particular, a lower machine precision will mcan that the convergence of representations in Thcorem 4.2 will occur much sooner, and consequently the LLM will not be able to distinguish even shorter sequences.
In practice, the direct application of theoretical results is made more complicated due to tokenisation. In particular, a sequence of repeated tokens '11111' for instance may not be necessarily tokenised into 5 distinct '1' tokens. In principle, this should help alleviate the direct collapse of the representations. Tokenisation in general makes more of a challenge to study such phenomena as it adds an additional layer of complexity to the experimental analysis. In our experiments, we took tokenisation into consideration and attempted to mitigate its effects.
A simple solution to representational collapse. An important consequence of Theorem 4.2 is that is challenging for a Transformer to deal with a long sequence of repeated lokens. A practical solution is to this issue is to introduce additional tokens throughout the sequence to help keep the represent ations distant. We provide direct evidence of this Figure (c,d), where we prompt the model on simple copying task of long string of ones. While the

---

Regresentatoon Difteraie
2.5
Counting 1s from a Sequence of 15
Sten (eppractiaiznal Dittnoos
Dufferance
0.6
Counting 1s from a Sequeence of Sampled Digits
Maun leerractiiizel Ditsnoos
2.0
0.5
0.4
1.5
Representatinn
0.3
1.0
0.2
0.5
0.1
0.0
0.0
31
53
101
501
1001
2001
11
53
103 1001
501
2001
Sequence Length
Sequence Length
(a) "How many ones are in the following sequences?" ? Followed by a sequence of ones.
(b) "How many ones are the following sequences?" Followed by sampled digits.
Representttogn Difference
Copying Sequenee of
Dufference
Copying Sequence of with Commas
Stere Hegreentiddin on Dillannan
2.5
Maus Regroctiutied Dillanaoo Precasso
2.0
Presisse
2.0
0.0
0.6
Represenattonl
1.5
0.4
1.0
0.2
0.5
0.0
0.0
11
51
101
501
1001
2001
11
51
101
501
1001
2001
Sequence Length
Sequence Length
(c) "Can you copy the following number?" Pollowed by sequence of ones.
(d) "Can you copy the following number?"
Followed by sequence of ones with commas.
Figure Representational collapse for counting (a, b) and copying (c, d) tasks.
representations collapse for the sequence of ones (c), adding commas every third digit. (d)
helps to keep the representations well-separated.
Over-squashing in Language Tasks
In this Section, we study a more general phenomenon related to representational collapsc- over-squashing. In particular, sequence affects the information contained within the representation of the last token in the final layer the represenlation ultimately used for next-token prediction. For this reason, we study the quantity dyn/ôv; which measures how sensitive is the final token to an input token at position i.
intcrested in analysing how information from the input
In graph neural network theory, the decay of such partial derivative is often associated with the 'squashing' of information, leading to the phenomenon of over-squashing [29, 8, 11), a problem related to the well-known vanishing gradients problem in RNNs [14, 5, 11]. The over-squashing analysis carry out in this work is particularly challenging due to the flexible nature of the attention mechanism and the many components that are part of decoder-only Transformers. Consequently, we make two simplifying assumptions in our analysis: (i) We summarise the effect of layer normalisation via a constant 3 for the i-th layer norm component, and (ii) the attention weights are treated as independent of the input. Such simplifications are not strictly necessary for our analysis, but they greatly simplify the resulting bound we derive and do not detract from the two key takcaways: (1) the sensitivity to an input token depends on its position in the sequence and (2) the sensitivity to an input token depends the attention weights. The result is summarised in Theorem 5.1. The full statement is reported in the Appendix (Theorem B.5).
Theorem 5.1 (Over-squashing in Transformers). Consider an input sequence v ...., v.
( + dign then:
Let C be some constant and a
82
õyn δv
Σ
(L-1)
Ke.ke
(t-1) (0)
Tki
(1)
k
k
E-2
8

---

Theorem 5.1 provides intuition on how information propagates in a decoder-only Transformer. In particular, there is a topological aspect present in the bound which is directly controlled by the attention mechanism. More concretely, the sensitivity depends on the sum of the weighted paths between the token at the imput and the final layer. In other words, for tokens coming sooner in the sequence, there will be more opportunity for their information to be preserved. This clear for instance for the last token, which will only be preserved by attention mechanism if the attention one path. The paths instead grow very quickly for tokens coming sooner in the sequence. A related observation, in terms of path counting, that such a bound explains the better performance when copying elements at the start of the sequence in Figure 2 (a), why hints help in Figure 2 (b), and why repeating the final elements within the sequence also helps in Figure 2 (c).
is large at every layer L, i.e. there is only
also made for deep RNNs [13]. We note
This analysis leads to an interesting limiting case described in Proposition 5.2, that shows type of exponential vanishing that can occur in some degenerate cases in which yn depends only on the starting input token Vi Fortunately, there are many mechanisms which prevent this from happening, but believe this to be an interesting limiting case which is a direct consequence of the topology of the causal attention mechanism. Further, it provides an interesting connection between the spectral theory of directed graphs and causal attention mechanisms. We report the formal statement in the Appendix (Proposition B.8).
Proposition 5.2 (Informal). Under certain assumptions on the effect of the normalisation and on the attention weights, in the limit of layers L - oc the output representation will only depend on the first input token.
U-shape effect. Theorem 5.1 in part also helps to explain the empirically observed U- shape effect the observation that LLMs seem to perform better at retrieval tasks when the information to be retrieved is located either near the start the end of the sequence. In fact, due to the topology of the causal mechanism, we find from Theorem 5.1 that tokens at the start of the sequence have more opportunity for the information to be maintained at the end. The final tokens being also casier instead can be explained from the recency bias that is learnt by the attention mechanism during training. In auto-regressive next-token prediction, it is in fact reasonable to assume that tokens that are closer to the end will be more important and this is likely bias that is learnt during training by the LLM.
6 Counting
We finally highlight another representational problem that arises specifically counting problems. Our analysis points to fundamental difficulty that emerges from the normalisation of the softmax. In particular, the normalisation of the softmax makes it hard for a model to take into account the length of sequence. This is exacerbated by the fact that positional encodings are often normalised and thus relative, meaning that they also do not hold absolute positional information. Intuitively, counting is problem that requires some notion of 'unboundedeess' of the representations, whilst the normalisations used inside Transformer work against this.
We start by showing that without causal masking and positional embeddings, a Transformer is immediately unable to count the number of tokens in sequence, highlighting pathological issue which stems directly from the softmax normalisation. We note that similar issues have been already pointed out jc.g. 22]. We show the result in Proposition 6.1 and report the full statement in the Appendix (Proposition B.9).
Proposition 6.1. Transformer without positional encodings and a causal attention mechanism is immediately unable to count.
While causal mechanisms and positional encodings help to break such representational issucs, they break the permutation invariance of the Transformer, meaning that the representations will be heavily miss-aligued with the lask, something which has been shown to hinder performance [9]. As permutations grow factorially with sequence length, this makes it practically very challenging for decoder-only Transformer to learn such a property simply from the data. This explains the extreme incapacity of counting highlighted in Section

---

3. Further, as corollary of Theorem 4.2, we have that even if model would be able to generalise perfectly, the problem of representational collapse points an impossibility result in counting regardless. The result is summarised in Corollary 6.2, with the full statement. in the Appendix (Corollary B.10).
Corollary 6.2 (Informal). Counling in cerlain silualions becomes impossible due to repre- sentational collapse and finite floating point precision.
Corollary 6.2 shows how our main result on representational collapse points to practical issues when it comes to certain styles of prompts. When paired with low floating point arithmetic precision, representation collapse becomes problematic.
Conclusion and Future Work
In this work, we first presented surprising failure cases of LLMs on simple copying and counting tasks. We then discussed how such failure cases can be explained by studying what can be contained inside the representation yn, and in particular how information may be lost. This lead the unvcaling of two phenomena representational collapse and over-squashing. We showed how we can mcasure these phenomena in practice and proposed simple solutions to help alleviate such information loss.
We believe that this work uncovers an interesting framework which can be used to study failure cases of Transformers and LLMs more generally. We believe that analysis could be extended in many practical different directions, for instance by understanding how to directly measure over-squahhing or how best use this newly-found understanding to improve current Transformer models. In our work, we focused on pointing out information- propagation issues in Transformer-basee architectures, but we hope that the findings may help better understand and improve language models available today.
8 Acknowledgements
We would like to thank Wojcieeh Marian Czarnecki (Google DeepMind), Simon Osindero (Google DeepMind), and Timothy Nguyen (Google DeepMind) for the valuable comments and suggestions regarding this work. We also thank Constantin Kogler (University of Oxford) for providing useful insights on the thcoretical aspects of the work.
10

---

References
[1] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, lain Barr, Yana Hasson, Karel Lene, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning, Advances neural information processing systems, 35:23716 23736, 2022.
[ Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
3 Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Giovanni. Locality-aware graph rewiring in GNNs. In The Twelfth Inter- national Conference on Learning Representations, 2024.
[4] Federico Barbero, Alex Vitvitskyi, Christos Perivolaropoulos, Razvan Pascanu, and Petar Veličković. Round and round we go! what makes rotary positional encodings useful? arXiv preprint arXiv:24 10. 10.06205, 2024.
5] Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Thansactions on Neural Networks, 5(2):157-166, 1994.
[6] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkorcit, and Eukasz Kaiser. Universal transformers, 2019.
[7] Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the chomsky hicrarchy, 2023.
[8] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pages 7865-7885. PMLR, 2023.
[9] Andrew Joseph Dudzik, Tamara von Glehn, Razvan Pascanu, and Petar Veličković. Asynchronous algorithmic alignment with cocycles. In Learning on Graphs Conference, pages 1. PMLR, 2024.
[10] Team Gemini. Gemini: a family of highly capable multimodal models. arXiv preprint ar arXiv:2312.1180 2023.
[11] Francesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, and Petar Veličkovié. How does over-squashing affect the power of GNNs? Transactions on Machine Learning Research, 2024.
[12] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
[13] Luca Herranz-Celotti and Jean Rouat. Stabilizing rmn gradients through pre-training, 2024.
[14] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computa- tion, 98):11335- 1997.
[15] Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in trans- formers. Advances in Neural Information Processing Systems, 36, 2024.
[16] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-less code generation with alphacode. Science, 378(6624):1092 10997 2022.
[17] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157-177 2024.
11

---

[18] William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. orXiv preprint arXiv:2310.0728 079229,9, 2023.
[19] OpenAl. Gpt-4 technical report. arxiv 2303.08774. View in Article, 2(5), 2023.
[20] Razvan Pascamu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training re- current neural networks. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 Proceedings of Machine Learning Research, pages 1310-1318, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[21] Binghui Peng, Srini Narayanan, and Christos Papadimitrion. On limitations of the transformer architecture, 2024.
[22) Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75))11355 2021.
[23] S Unnikrishna Pillai, Torsten Suel, and Seunghun Cha. The perron-frobenius theorem: some of its applications. IEEE Signal Processing Magazine, 22(2):62-75, 2005.
[24] Ofrr Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. ar preprint arXiv:2108. 12...22221 12409, 2021.
[25] Timo Schick, Jane Dwivedi-Yu, Roberto Dessi, Roberta Raileamu, Maria Lomeli, Fric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Lan- guage models can teach themselves to use tools. Advances in Neural Information Pro- cessing Systems, 36, 2024.
[26] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 567:127063, 2024.
[27] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXie preprint arXiv:2403. 08295, 2024.
[28] Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size. arXin preprint ar Xix:224008 001 18, 2024.
[29] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Underslanding over-squashing and bottlenecks on graphs via curvature. 2022.
[30] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[31] Petar Veličković, Christos Perivolaroponlos, Federico Barbero, and Razvan Pascanu. softmax is not enough (for sharp out-of-distributiion) arXiv preprint 2001:22400001104 2024.
[32] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Demny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint ar arXiv:2206.. 076882, 2022.
[33] Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers, 2021.
[34] Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the translormer architecture. In International Conference on Machine Learning, pages 10524-10538 PMLR, 2020.
12

---

[35] Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Busbridge, Jason Ramapuram, Yizhe Zhang, Jiatao Gu, and Joshua M Susskind. Stabilizing transformer training by preventing attention ion entropy collapse. In International Conference on Machine Learning, pages 40770 40770-40803, 40803. PMLR, 2023.
13

---

A Broader impact
This paper presents work whose goal is advance the field of Machine Learning. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here. In particular the limitations highlighted in the work can pose some issuc in terms of reliability of LLMs, so highlighting these issues can help fixing them.
B Proofs
We provide formal statements and proofs for the results shown in the main text. We follow the order in which they are presented in the main text. In Section B.1, present the proofs on representational collapse (Section 4), in Section B.2 the proofs on over-squashing (Section 5) over-squashing, and finally in Section B.3 the proofs counting (Section 6).
B.1 Representational Collapse
We start by showing that adding a new clement to sequence results in the softmax value of a specific token to decrease. In particular, and show that we can use this to construct an upper bound on the softmax value for any token.
consider the case in which the tokens are bounded
Lemma B.1. Consider a vector a E R and two scalars b, E R. Let x [a cf IR" and x* [a b c]" R with all entries bounded. Then, softmax (x), > softmax (x*) n+1 Moreover for any p 0 can find large enough N+ such that ssotmmax (x), softmax (x*)++1 <
Proof. We directly compute:
exp(c)
softmax(x),,
n- k- exp(a:) exp(c)
exp(c)
softmax(x*) )n+1
exp(b) + exp(c)
As assume that the entries bounded, have that -x= exp(c) ΣØ exp(a,) + exp(b) + exp(c), therefore softmax(x),, softmax(x*) (x*)
For the second part the statement, we compute:
exp(c)
exp(c)
|softmax(x),, softmax(x (x" )n+l
n- k-1 exp(ax) exp(c)
x-1 exp(as) exp(b) + exp(c)
exp(c)
exp(c)
n- -- exp(ar) + exp(c)
> - exp(ax) exp(b) + exp(c)
p
for some > 0, as the last step the summands tend to 0 as n - x0 We there- fore have that (softmax(x),, softmax(x* 1n 0 as
and for large enough |softmax(x),, - softmax(x (*xxx((**))xx)))) (x < for any 0 due to the previous statement.
Total variation. We now study a quantity known as the total variation between two distributions of interest. Given two categorical distributions p, v supported on the same space, we define their total variation 8(1, or equivalently L1 norm || pul-l as:
8(1, v) = Σ (m(x)) uxx))
(2)
14

---

The total variation is a distance between probabilty distributions. We note that oftentimes the quantity above is strictly called the L1 norm, while 1/2 of such quantity the total variation. For the scope of our work, the factor of 1/2 is not important so ignore it and use the two terms synonymously. Interestingly, the total variation is intimately related to the KT.-divergence, pointing towards potential connections to information theory. We leave such a connection to future work.
We now study how the total variation between two softmax distributions behaves in the limit of the sequence length. In particular, we show that the positional encoding information decays to 0 with the sequence length, then the total variation between the two sequences goes to with n. Such result is presented in Lemma B.2
Lemma B.2. Consider two sequences x, x* E I such that lim X,, x = 0, with X,, x bounded. Let y, E IR" be the softmar of and x* respectivcly. Then, as the total variation tends to O, i.e. limm-x ö(y, y*) O.
Proof. Let Z
Σx= ex and Z* Ei=ee ex be the partition functions for x and x*;
respectively. We start by bounding the quantity 1 - 2* In particular, let > 0, we first claim:
1 - z
&
Σ
e xx
<mminZ,
&
(3)
i-1
Consider some no 7 1 such that
ex
x
We note that this always possible as e/2.
|x* xi| by assumption. We compute:
c
+
Σ
x
1=1g
+ Σ
1
-
xx -xi
1=
xx
t=
x x
'z
eZ
Where the last step comes from the observation that the first sum fixed and Z is unbounded with Therefore, for n large enough, can also bound the left summand by Ze/2. The same argument also holds when bounding with z instead of Z, leading to the claim in Equation 3.
We now proceed with the following computation:
15

---

ex.
8(y,y")
7 7.
7. xx Ze
ZZ*
e Ze + Ze - Z
ZZ*
7 Ze
Ze Ze
ZZ
ZZ
Z*
Z
ex
7.7%*
7.7..
7 7
1
1ex1
-e
7,
ZZ*
Z*
minn Z, Z*
emin Z2 Z
7
Z
2c
which concludes the proof.
We are now ready to show the main result on representational collapse. In particular, we show that given two sequences of length n and n n where the second sequence is the same as the first with a final repeated token, their representations become arbitrarily close. Importantly, we require that the information from the positional encodings docays to the distance grows between tokens. The final token repetition is important as otherwise the residual connection in the Transformer would not make the representations necessarily converge.
Theorem B.3 (Representational Collapse). Let E R=-lxd be an underlying growing token sequence. Lel (() [v va]"e E Raxd and =0 [v v. va]" E Ra+lxd be lwo sequences for a final repeated token Xa E Rd, with all token representations bounded. Further, assume that the positional encodings decay with distance to O. Then, for large enough n E N+, we have that the representations are under any
|!!!
+(L) <.
Proof. We note that since the sequences are identical up to the n-th element, it is sufficient to only check the representations the final elements in both sequences. We therefore compare the n-th element of ()) with the 1-th element of 2 =0))
#(0)
Σ i<n
(0)
(0)
(0)
Σ iKn
aatiaVi + ( + a 12+1, v:
(0)
+(0)
2
n
n
v
+
an
(a
Σ
(0)
+(0)
V + (a..))
*(0)
+(0)
v(())
nn2
1.
0n41n
11+11111
(0)
+(0)
(0)
+(0)
+(0)
n,i
1ntla
1
(0)
+(0)
(0)
+00)
+00)
0 a
ann
antia
an+Intl
8
(0)
an
+00)
+ a
1nl1 <e
(0)
16

---

We assume for simplicity that the values are unit norm. This is not crucial as otherwise one would equivalently just need consider additional constant factors as we assume the token representations are bounded. We note that the term å (art.. Oniin goes to 0 with - db
+(0)
thanks to Lemma B.2 and our assumptions on the positional encodings. Similarly, the torm *(U) Ontla+1 goes to O due to Lemma B.1. We have also used the fact that vn v n+1 by
*(0)
construction to ignore the residual connection. As v. (f++)) (b(() [norm") (2)
(z!
+ v the
sequences will have arbitrarily close final token representations when entering the next layer. The result then follows via a simple inductive approach on the layers.
We also highlight negative decay result which highlights why the assumption the positional encodings is important. In particular, we show that given two sequences x = (1 O 1 O.... and x* (0 1 ...), the total variation of the softmax does not decay to O. This implics that there may be solutions to reprosentational collapse depending on how the positional encodings are chosen.
Proposition B.4. Consider two sequences x (1 (.000..)e R" andx* (0101... ) R for n even. Let y and y* be the softmar of x and x", respectively. Then the total variation y(y does not lend to as s0
Proof. Let Z = En= ext and Z* Ei ext be the partition functions for x and x", respectively. We directly compute:
lim 8(y, n1000
lim
y:
n00
Yi
lim
7 2
lim
11
2
(e
lim n-0
c+1
n
2
1
0.
6 1
B.2 Over-squashing
We now present our results on over-squashing, In our derivations, assume that the attention coefficients are independent of the values and that we can summarise the effect of the layer norms via a constant factor. These assumptions are not necessary for the same derivation process to hold, but they greatly simplify the obtained bound and help more clearly point out the main takeaways.
Theorem B.5 (Over-squashing in Transformers). Consider input sequence vi (including CoT). Let oo be the marimal Lipschitz constant of any 2b((), and a
v
( 6n.)
(1) the normalized attention coefficient, then:
Bioy
dyn ōv (0)
Σ
Σ
(L-1) ankk 1-2
I
(t-1) Keiken ahid
(4)
k 21
Proof. Note that for j 2 we have:
17

---

aviett)
(5(()
(norm)
(0)
(2) ) + 2
ov!"
-
(5
Ōzz
82
δv; (2)
a
Σ
(
norm
(0)
(v!)) + v!0
ōv; (8)
( +1 1
+
85,6
where we let 5 represent the effect of layer normalization i at the E-th layer and 2800 the Lipschitz constant of (ht For the case when j < i due to the causal mechanism we have that ovg)) /ōv = O. We compute the following bound:
oyn
δvn
(L)
L-1 1
δv
kg
ōv (0)
33 k1
hz
σV
(L-1)
RL
R2-1
2v; (0)
Ov (L)
L-1
δv
ki
33 h1
δv
(L-1)
(f-1)
dv: 00)
kr.ski.-1
ke
1-1
1
(1-1)
(f (1-1) 1) (0)
83 t=1
n,ke
ky - a
bpd
k1
C
Σ
Σ
an
(L-1)
akecker aki
(f-1)
(0)
2-2
where we let (1)
(2) + 83, and C= 1 Bs
11
ov ( +1)
We note that in this derivation, we use simplifying assumptions on the layer norms and attention coefficients, more specifically we assumee that they are independent of the v,s. Of course, there is nothing stopping us from avoiding such assumptions and pushing the partial derivatives inside these components as well. The drawback is that this would add a great deal of additional complexity the result and potentially distract from what we believe are the two key takeaways: (1) the position of the token matters, and (2) the attention coefficients matter.
Connection to the spectral theory of Markov chains. We now show some results on the spectral theory of matrices which relate to causal attention mechanisms. We emphasize that in this work, we view causal attention mechanisms as triangular row-stochastic matrices. We show that these matrices have interesting spectral propertics.
Lemma B.6. A row-stochastic triangular matria A has 1 its largest eigenvalue. Moreover, such eigenvalue has multiplicityy 1 if each row except the first has at least? non-zero entries.
Proof. We start by showing that A cannot have cigenvalues À 1. eigenvector with eigenvalue 1. We finally show that such an eigenvector is unique each row has at least. 2 non-zero entries.
We then provide
Assume X for some eigenvector d we then have that Aø = Xq. Consider de max; de > O. Now (AØ), = Ejst Aujo Xos. As the sum is a convex combination, the result cannot
18

---

be larger than the already maximal element oi. As À > 1, we however have that XØ; > O which contradiction and we conclude that À E
It is easy to find an eigenvector that always has eigenvalue 1. Consider a vector x which is constant vector of 1s. Then (Ax); Ljer Aij Xi, therefore x is an eigenvector with cigenvalue 1.
Finally, we show that when each row non-zero, the only eigenvector is the constant-values eigenvector. Consider the largest entry y; > O, then we have that (Ay); Ligs Aijy; y;. Again, as this defines convex combination, we must have that all tokens that i points to (i.e. the non-zero entries) are also equal to yı- The condition that each row has least two non-zero entries is important as it means that the condition y; jj is true for all tokens. L
Lemma B.7. The product of two row-stochastic matrices is again row-stochastic. Moreover, the producl of two triangular row-slochaslic malrices is a triangular row-slochaslic malria.
Proof. Lot A,B Raxn be two row-stochastic matricos. We compute:
(AB) = ΣΣ = EAa
The final statement follows immediately from the fact that the product of two triangular matrices triangular.
We now show that under specific conditions, our over-squashing bound converges to a steady state in which the final token yn only depends the initial imput token v as the number layers tends to infinity, i.c. -- OC.
Proposition B.8. Let ) .85 = 33 3//L = 4, ou 1. Furthermore, for simplicity, let -
the allention coefficients be equal al each layer and such that each row except the first of the causal mechanism has at least two non-zero elements. Then, we have L 1- co that when i= 1. In other words, yu will only be
,yn/ōv; (0) when # and dyn/Ov?
sensitive to the first token.
Proof. Let the associated attention matrix be A. We start by re-writing the following:
dyn ōv
1
Σ
Σ
(L-1) L-1
I1
(e-1) -(0)
00)
83
82
+
Onkk
ke 1
F-1
kr.
8-2
O
+1)
(
A + ( :
B//
B2
B1
[=1
(12 (A [A+
)))
n2,
We now point out that A (A+ is row-stochastic and with our assumptions is diagonalizable into Á WΣD. In particular, by Lemma B.7, also À is row-stochastic and each entry is non-negative. We now use the Perron-Frobes Frobenius theorem for nog-tegative matrices [23], which guarantees
that all eigenvalues A of A are bounded such that [Ael < 1. In particular, thanks to Lemma B.6, we know that there is a unique cigenvector (the constant cigenvector vi,) with cigenvalue X, = Denote the left eigenvectors by thk and the right eigenvectors on. we therefore have:
lim A = Σ NEvio = 1.
In particular, one can check that of 0... 0], meaning that vh has as first column constant vector of is and every other entry 0. This completes the proof. D
19

---

B.3 Counting
We finally show in this section our final results that apply specifically counting tasks. We start by highlighting a potential difficulty that the softmax layer encounters when counting, namely that the normalisation used makes hard for it to preserve a notion of magnitude present in the sequence.
Proposition B.9. A Transformer without positional encodings and a causal atlention mechanism is immedialely unable to solve the counting problem.
Proof. We show this statement by demonstrating that the only information preserved about the 'count' by the attention mechanism will be the ratio of the elements present in sequence. In particular, sequences with the same ratio of tokens will be assigned the exact same representation positional encodings and causal masking. Of course, having the same ratio of elements does not mean that the count will be the same, for instance the sequences '10' and '1100' have the same ratio of digits but clearly different counts.
this applics
specifically study an attention mechanism without
Consider a sequence of two values, Viero and vin with no and n being the number of zeros and ones respectively. We ignore in our calculations the MLPs & and the normalizations norm as these don't affect the argument. As this specific attention mechanism is permutation equivariant, the initial zero tokens will all be mapped to:
(0)T (0) Lzerok; J
exp
(I) Zorra
(0)
(0) Zero
+
En exp qeeroke
[0)T (0)
(U) (0) qãera Kzero
(0)T (0) qerro Kone
no exp
11 exp
(0)
zero +
v-(0) one + (0)
(0)T no exp qsero Ksero
(0)T (0)
(0y2' (0) A Azero
(0) Qsero Kone
2ero
+ n1 exp
Axero Kone
1o exp
+ exp
(0) (0) Qzarak k
(0)T (0) Eero Kone
exp
exp
q
(0) zero
(()) one + v
exp
(0Y2 Azera Kzero
+ mi exp
azero Kone
exp
(0) q quero Kzero
+ exp
(O)T Bberokond
zero
Similarly, the ones will be mapped lo:
cxp
Gone k
T (0)
(0)
(0)
Zone
Σn exp
qone (0)
(0)T
(0)T qone Kzero
(q
(0)T (0)
nh exp
1i exp
kone
Sero +
(0)
(0) + v (0)
ng exp
qoae kinno
(T) (0)
72 exp
qone kone
(0)T (0)
no exp
qone kzero
(0)T
+ n2 exp
qone k.:))
(0)
(U)T (0) qone ksero
qone (()
(0)T
exp
exp
(0)
(0)
+ v (0)
exp qone k kgero)
(0)7
exp
qone Kone
(0)T (0)
zero
exp
qeero kero exp
(O) (0)
gone Kone
(0)T (0)
one
one
no
Ag
(1) Assuming that Zzero # zome (to avoid the trivial case), we notice that the attention mochanism alongside the MLP ab define an isomorphism between sequences at different layers, updating all zeros and ones to a different value vector. The critical fact is that the representations only depend on the ratio between no and n1, meaning that sequences of different lengths (therefore different counts) will have the exact same representation. This respected at each layer, meaning that the LLM after L layers will assign the same representation to different
20

---

sequences as long as they have the same ratio. This points to a loss of representation for the counting problem.
Corollary B.10. Consider a task in which the goal to count how many Va tokens there are in the sequence. Let v(0) (v val E Raad and v*(0) [v Va vaj E [[(+1)xdd Due to representational collapse, least one sequence will be given the wrong count for large enough finite n.
Proof. This statement is direct consequence of representational collapse. In particular, as Yn and y will be indistinguishable for large enough n, the Transformer will be forced to make mistake for at least one of them. This points to an impossibility result of counting certain sequences due to floating point error. This holds regardless of the positional encodings used (as long they satisfy the required decay conditions) and causal mechanism.
C Experiments
The prompting done on Gemini 1.5 in our work does not require custom resources as we hosted Gemini instances. We local version of Gemma 7B modest hardware to analyse the internal representations.
C.1 Experimental Details
We detail the way in which execute the prompting for the various experiments.
Counting experiments. For the sum experiment we prompt as: Please perform the following sum: seq. Please give the answer the final line exactly as 'The final answer to your maths question is: xxxx', where 'xxxx' is your answer..
For the ones and zero sequences, we similarly prompt as Please count the number of ones in the following sequence seq. Please give the answer on the final line exactly as 'The final answer to your maths question is: Xxxx', where 'xxxx is your For the word counting experiment, we prompt as Please count the number of times 'car' appears in the following sentence: 'seq'. Please give the answer on the final line exactly as 'The final answer to your maths question is: xxxx', where 'xxxx' is your answer.
For the CoT experiments, we supply examples of the form: Let's think step by step, showing me your reasoning. Here are a few examples:
Please perform the following sum: + 1 1 + 1 + + 1 + 1 + 1 + 1
We divide the sum into groups of 5. (1 + 1 + 1) +1+1
1) (1 +
The answer is then * 5
12
The final answer to your maths question is: 12
Please perform the following sum: 1 1 1 +1+1
We divide the sum into groups of 5.
(1 + 1 1
1) +
The answer is then
5 + +
The final answer to your maths question is:
With similar strategies for the experiments.
Copying experiments. For the copying experiments, we use the following prompt: Consider the following sequence: seq. What is the last digit in this sequence? Please answer exactly as 'The answer to your question is: <ANSWER>'
and change appropriately the sequence described.
21

---

We commit to releasing the code we have used generate the prompts in the near future.
C.2 Counting with Gemma
We report similar results for the counting experiments using Gemma [27] in Figure 6 and 7. Compared to Gemini 1.5, Gemma seems to answer less accurately on the counting prompts.
Sum
Count Ones in 1...1
Count Ones in 1/0...|00
Count Words in Sentence
175
175
175
175
150
No
100
75
75
75
30
50
50
25
200
Absolute Error
Col Zero Shot
375
175
175
175
150
1.50
150
150
125
125
125
125
50
25
100
200
Col Few Shot
375
175
1.0
1.50
150
150
125
123
125
125
100
100
100
100
25
25
0
100
200
100
200
100
200
100
200
Sequence Length
Figure 6: Gemma 7B LLMs being prompted to (i) sum 1 + ... + 1 (left), (ii) Count the number of ones in a sequence of Is (center), and (iit) Count the number of ones a sequence of ones and zeroes (the sequence is a Bernoulli sequence with probability of sampling one being 0.7) (right).
Group
20
Predictions w/o Col
Predictions
15
Trequency
100
175
Value
Figure Frequency of different outputs for Gemma 7B
C.3 Synthetic Experiments on Representational Collapse
To provide further experimental evidence of representational collapse with other positional encodings, experiment using the original sinusoidal embeddings from [30]. We sample key, query, and values from Gaussian distribution with variance o² 1/d, with d the dimension of the embeddings. We set d = 64 and otherwise follow the exact structure of the decoder- only Transformer presented in the original Transformer paper. We experiment with single attention layer and check the convergence the representations of the final token between sequence of length and sequence of length + in which we simply copy the final token. We present the results in Figure 8. We see how also for sinusoidal PFs with key, queries, and values randomly sampled, the convergence still occurs.
22

---

Convergence of Sampled Embeddings with Sinusoidal PEs
Representationa Difference
Mean Representational Difference
bf16 Precision
10-2
5
10
100
500
1000
5000
10000
Sequence Length
Figure 8: Convergence behaviour with synthetic Transformer experiment. We sample the key, query, and values from a Gaussian distribution and apply the traditional sinnsoidal PEs from [30]. We apply logarithmic scale on the y-axis.
Finally, we test the decay of the total variation of the softmax distributions of two growing sequences, to experimentally verify Lemma B.2. We sample sequence of length n with values uniformly distributed in the range [0, 1]. We then create x* by adding to the first k 200 elements of x noise which is uniformly sampled between [0, 0.1]. In Figure 9, show how the total variation between their respective softmax distributions decays with the sequence length.
Representational Difference
Decay of Total Variation
Total Variation
0.025
bf16 Precision
0.020
0.015
0.010
0.005
500
750
1000
1500 2000 2500 3000 4000 5000 10000 Sequence Length
Figure 9: Total variation decay of softmax distributions with growing sequence length. We sample n elements uniformly from [0, 1] and then create related sequence by taking its first k = 200 and adding to these elements noise sampled uniformly from [0, 0.1]. We measure the total variation between their softmax distributions. It is clear how the total variation decays with length, in accordance with Lemma B.2. Error bars show minimum and maximum over scods.
C.4 Effect of Positional Encodings
We include a synthetic experiment where we verify the occurrence of the representational collapse phenomenon with different. Positional Encodings, namely: Alibi [24], the original Absolute Positional Encodings (APE) [30], and No Positional Encodings (NoPE) [15]. In our synthetic experiment, we sample n queries and keys independently directly from a standard Gaussian. We then construct related sequence of length n + 1 by repeating its last element. We report the Ia distance between the two sequences alter single decoder-Traie Transformer layer, done for the other representational collapse experiments. We consider Transformer with
23

---

hidden dimension of 64, single attention head, and we apply normalisations to simulate layer norm. The Transformer not trained, but only used simulate the propagation of information of queries and keys sampled from a Gaussian distribution. The results are shown Figure 10. Representational collapse seems to occur with all 4 positional encodings, with the convergence of the representations happening at a similar sequence lengths.
We would like highlight that our condition on the decay of RoPE necessary to fulfill the requirement of Theorem 4.2 is inspired by claims of the decay of RoPE coming from the original work by Su et al. [26]. However, recent work has shown that such claims may not be strictly always upheld [4], as the original claims relied on very specific conditions on the queries and keys. We are of the opinion; however, that the range of synthetic and real-world
experiments in this work support our representational collapse claims in practice with RoPE. more precise mathematical treatment of RoPF specifically is therefore left as future work.
Representational Collapse with Different PEs
Representationa Difference
100
Sinusoidal Absolute Encoding
RoPE
Alibi
No Positional Encoding
10-1
6 Precision
10-2
10-3
5
10
100
500
1000
5000
Sequence Length
Figure 10: We sample queries, keys, and values independently from a standard Gaussian, applying different positional encodings. We then construct sequences of length n + 1, by repeating the n-th token. We report the L, distance between the last tokens of the sequences of length n and n +1 after one decoder-only Transformer layer. We set the hidden dimension to 64, use single attention head, and normalise appropriately to simulate the effects of LayerNorm. The y-axis is shown in log-scale.
C.5 Ablation on Prompt Structure
We ablate the prompt structure specifically for the copying task. In particular, we consider the prompts: (Type 1) "What is the last digit of the following sequence? Please answer exactly 'The answer to your question is: <ANSWER>" ", Here is the sequence: {seq} and (Type 2) "Please answer exactly as 'The answer to your question is: <ANSWER>? What is the last digit of the following sequenee? {soq)". R The results are presented in Figure 11. We find that the prompt indeed does affect the performance on the task, as the prompt affects the distribution of the attention over the layer. However, for both types of prompts, the model ends up failing, in accordance with our theory. We also show for completeness, in Figure 12, that representational collapse occurs in Gemma 7B also for the 'Type 1' prompt.
C.6 Local sliding window attention
A fundamental limitation of an attention mechanism that leverages the softmax function is that it cannot remain sharp, espocially as the sequence length grows [31]. This is in fact key intuition that we exploit show our result on reprosentational collapse. A good way to address representational collapse and the related phenomenon of over-squashing is then that of limiting the spread of the softmax function, by directly limiting the amount of tokens the attention mechanism pays attention to. This mechanism is often referred to local sliding window and is a major architectural change present in Gemma 2 [28). We believe that such an architectural change elegantly addresses representational collapse and over-squashing at
24

---

Effect of Prompt Formatting
500
1000
1500
Sequence Length
Prompt Type 1
Prompt Type 2
Figure 11: Performance of Gemini model on the following prompts: (Type 1) "What is the last digit of the following sequence? Please answer exactly 'The answer to your question is: <ANSWER>" Here is the sequence: {seq} and (Type 2) "Please answer exactly as 'The answer your question <ANSWER>! What the last digit of the following sequence?
{seq}"
Representational Difference
Representational Collapse with Formatting Instructions
0.35
Mean Representational Difference
Precision
0.30
0.25
0.20
0.15
0.10
0.05
0.00
2
5
10
100
500
1000
Sequence Length
Representational collapse Gemma for the prompt: "What is the last digit of the following sequence? Please answer exactly as "The answer to your question is: <ANSWER> " Here is the sequence: {heq} and (Type 2)
Figure 12:
the source as it avoids the issues that come with growing token sequences something which our theory often exploits.
25

---

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

---

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

---

the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: the paper we describe in depth all the details to reproduce our work. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (attps://nips.
for more details.
While encourage the release of code and data, understand that this might not. be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guide- lines (https://nii cctpublic/guiiiiieccccc guides/ httpa///ggddee//ouiiiiississssss /cco/o/Suuiiiiiioooooiooo. details.
for more
The authors should provide instructions on data access and preparation, in- cluding how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Detaie
Question:
Docs 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: All the experimental details are shared with sufficient. details to evaluate them.
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 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.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments? Answer: [Yes]
Justification:
Where relevant we included the statistical significance analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
28

---

The authors should answer "Yes' if the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be carcful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negalive error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: We only run inference experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relovant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well as estimate the total compute.
The paper should disclosc whether the full rescarch project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurip:: httpc//cbc//ttticeeeouueeee ines?
Answer:
[Yes]
Justification:
We believe to have followed the details provided by the Ethics Guide-
lines
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 regulations in their jurisdiction).
10. Broader Impacts
Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
29

---

Justification:
There is no socictal impact of the work performed.
Guidelines:
The answer NA mcans that there is no socictal impact of the work performed. However put a broader impact statement in the Appendix.
If the authors answer NA or No, they should explain why their work has 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, generaling fake profiles, surveillance), fairness consid- erations (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 rescarch 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 legilimate to point out that an improvement in the quality of generalive models could be used lo generale deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arisc when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional
(oniteltiiona]] misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategics (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mochanisms to monitor how system learns from feedback over time, improving the elficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release data or models that have a high risk for misuse (e.g,, pretrained language models, image generators, scraped datasets)?
Answer: [Yes]
Justification: Our work does not pose the described risks.
Guidelines:
The answer NA means that the paper poses 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 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:
All the relevant work has been cited and the details where all reported.
Guidelines:
The answer NA mcans that the paper does not use cxisting asscts.
The authors should cite the original paper that produced the code package or dataset.
30

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are relcasod, the license, copyright information, and terms of use in the package should be provided. For popular datascts, paperswithe whwcdeeeteee.....m com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out. to the asset's 8 creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not use new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/con coode/modo as part of their submissions via structured templates. This includes details about training, license, limitations, elc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At. submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor rescarch with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [Yes]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
31

---

Guidelines:
new The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have clearly stated the assumptions and limitations of our theory, see e.g. Section 5
(c) Did you discuss any potential negative socictal impacts of your work? [Yes] We don't 't expect negative socictal impacts as direct result of the contributions in our paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are inchuding theoretical results...
(a) Did you state the full of assumptions of all thcorctical results? [Yos] Our results clearly state the assumptions and limitations.
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (cither in the supplemental material or as a URL)? [Yes] We included description of the prompting and experimental details carry out. We have used material publicly available our work. We commit to releasing prompting code used to generate our results.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [NA] We do not perform any training our work and use pre-trained models.
(c) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We provide description of the resources required in Appendix Section C.
4. If you are using existing assets (c.g., code, data, models) or assels...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix Section C.
(c) Did you include any new assets either the supplemental material or as
URL? [NA]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're
[NA] No human data collected.
(e) Did you discuss whether the data you using/ /curating contains personally
identifiable information or offensive content? [NA] No human data collected.
5. II you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots,
if applicable? [NA]
(b) Did you describe any potential participant risks, with links to Institutional
Review Board (TRB) approvals, if applicable? [NA]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [NA]
32


Reviews:
[{"review_id": "G7YVYAp7JC", "reviewer": "Reviewer_SAa1", "summary": "In the paper, the authors first discuss a phenomenon occurring in LLMs that they call \"representational collapse\". They provide empirical evidence of the phenomenon in state-of-the-art language models and they provide a theoretical justification for it. They then show that decoder-only transformers exhibit what is known in graph network theory as \"over-squashing\", which may cause loss of information in the final prediction.", "questions": "1) While the paper claims that the transformer architecture that they analyze is the most popular in state-of-the-art LLMs, it seems to me that they only consider relative positional embeddings and not absolute ones. To the best of my knowledge, current LLMs like GPT and Llama all use absolute positional embeddings. Would your results also extend to this case? In any case, I would highlight the use of relative positional embeddings more prominently in the main text.\n2) In the actual prompts used for the experiments, the sequence does not appear at the end of the prompt but somewhere in the middle. Would your theoretical results somehow generalize if the repeated token is not the last one? Would anything change in the experiments if the sequence appears exactly at the end?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper highlights a curious phenomenon in current language models, which shows their limitations even for extremely simple tasks like counting. The paper is well organized and well written. The observation of the over-squashing phenomenon is interesting.", "weaknesses": "The observed phenomenon, while interesting, has limited scope. Also, the representational collapse result is hardly surprising to me. It feels quite trivial that in the limit of a very long sequence, the importance of a single token out of many repeated ones becomes negligible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy that you found our paper well organized, well written, and the over-squashing phenomenon interesting. We would like to address your questions on positional encodings and on the prompting. \n\n**(Q1)** *[...] it seems to me that they only consider relative positional embeddings and not absolute ones. To the best of my knowledge, current LLMs like GPT and Llama all use absolute positional embeddings. Would your results also extend to this case?*\n\nWe thank you for the excellent comment. We would like to point out that according to Table 3 from the most recent Llama 3 [1] report, Llama 3 seems to be using the relative positional encoding RoPE. As far as we are aware, details regarding positional encodings used in most recent GPT models are not publicly available and as such we cannot comment with certainty on the positional encodings used for such models. \n\nRegardless, we agree with you that it is important to add more details on the type of positional encoding used. We clarify that our results still apply for absolute positional encodings as we never make any explicit assumptions on the formulation of the PE. What we do require is that the effect of the positional encoding decays with distance, a common design choice used to encode distance in PEs. We have further emphasized this in the main text and will add a detailed section in the Appendix covering RoPE, Alibi [2], absolute sinusoidal embeddings (APE) [3], and no positional encodings (NoPE) [4]. \n\nTo provide experimental evidence supporting such claims, we have designed a synthetic experiment showing that representational collapse occurs also for Alibi, sinusoidal absolute positional encodings, and NoPE. We refer to the global comment for the details and results. We thank you for helping to strengthen our work in this direction, which we believe is a very important one. \n\n**(Q2)** *In the actual prompts used for the experiments, the sequence does not appear at the end of the prompt but somewhere in the middle. Would your theoretical results somehow generalize if the repeated token is not the last one? Would anything change in the experiments if the sequence appears exactly at the end?*\n\nWe thank you for the great point you raise. In our prompts we add the formatting instructions at the end of the prompt in order to help with the automatic parsing of the output. We did not notice any qualitative difference in the counting tasks. On the copying tasks it seems like the formatting affects more the results. To explore this, we reformatted in 2 ways: \n\n1) \"What is the last digit of the following sequence? Please answer exactly as 'The answer to your question is: <ANSWER>'. Here is the sequence: {seq}\"\n\n2) \"Please answer exactly as 'The answer to your question is: <ANSWER>'. What is the last digit of the following sequence? {seq}\"\n\nThe results are in the supplementary PDF in Figure 2, with the first being called Prompt Type 1 and the second Prompt Type 2. We see that the model encounters the same failure for both prompts, with some prompts failing at a later point than others. \n\nThe theory applies most directly when the token difference occurs at the end, but it can also be applied to the prompts with the formatting instructions coming at the end. This holds due to a recursive argument. Once the representation has collapsed, the information for that token will be lost in the subsequent tokens as well. To confirm this, we plot the hidden representations of Gemma under the same prompt 3) used in the original copying experiments and show that the representations collapse in such a case – see Figure 3 in the supplementary PDF. We will add these two additional experiments to the appendix of our work. \n\n3) “Consider the following sequence: {seq} What is the last digit in this sequence? Please answer exactly as 'The answer to your question is: <ANSWER>'”\n\n\nWe thank you again for your comment and believe that these additional results help to strengthen our paper in this direction. \n\n**(W1)** *The observed phenomenon, while interesting, has limited scope. Also, the representational collapse result is hardly surprising to me [...]*\n\nWhile we are happy that you find the phenomenon to be interesting, we respectfully disagree that its scope is limited, as it highlights a fundamental issue of the Transformer architecture to perform important tasks. \n\nWe believe that there are two fundamental observations in our analysis of representational collapse that are valuable. (1) We believe that the idea of analysing what can be contained in the embeddings of the last token of the last layer is a novel approach that may provide an interesting new way of studying decoder-only Transformers. (2) We believe that tying representational collapse to an inability to generalize/solve problems like counting and copying due to floating point arithmetic errors is novel. We believe that connecting (1), (2), and representational collapse together creates an interesting way of understanding decoder-only Transformers. We emphasize that tasks such as copying are fundamental for settings in which an AI agent dispatches part of a computation to external tools, a paradigm that is becoming more and more frequent. \n\nWe thank you again for the great comments that have helped strengthen our work. We hope that our additional experiments and discussion make you more confident about our contributions. We are of course happy to clarify any further points in more detail and we thank you for endorsing our paper. \n\n[1] The Llama 3 Herd of Models, July 23, 2024. https://ai.meta.com/research/publications/the-llama-3-herd-of-models/. \n\n[2] Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation, Press et al. Arxiv, 2021.\n\n[3] Attention is all you need, Vaswani et al. Neurips, 2017.\n\n[4] The Impact of Positional Encoding on Length Generalization in Transformers, Kazemnejad et al, Neurips, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QiGjQ0nYd5", "reviewer": "Reviewer_GKd9", "summary": "The paper provides a theoretical and empirical analysis of the final representations of transformers, revealing the phenomenon of representational collapse.", "questions": "- What do the authors believe is the breadth of tasks affected by this fundamental issue in transformers?\n- What are the positional embeddings used for the experimental settings? Can these affect the representational collapse?\n- Minor: Some figures, like Figure 2, have a very small font size, making them hard to read.", "limitations": "See Questions and Weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written.\n- It highlights a problem in transformers that causes them to fail on a large set of tasks (assuming this extends to addition, etc.).\n- The paper provides empirical evidence supporting the theoretical claims, demonstrating the real-world relevance of the identified issues.\n- The impact of low-precision floating-point formats is interesting, which is highly relevant to current everyday practices", "weaknesses": "- There is no strong solution to this problem. Although the authors provide a simple approach, it is challenging to understand how to apply this approach in a practical setting.\n- The problems seem to be tied to the positional embeddings, as the authors stated. NoPE (https://arxiv.org/abs/2305.19466) and no causal mask would make this problem impossible. However, there are no experiments on how certain positional embeddings might be better than others.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for pointing out that our paper is well written and that you found it interesting and with real-world relevance. We would like to address your questions on the breadth of tasks affected and on positional encodings. \n\n**(Q1)** *What do the authors believe is the breadth of tasks affected by this fundamental issue in transformers?*\n\nWhile it is hard to comment on the entirety of the tasks affected by this issue, we believe that copying and counting are fundamental enough to claim that this is a rather wide-spread issue concerning the repetition of tokens. Copying is especially important as many LLM endpoints today benefit from tool-use, which relies on copying.\n\nWe suspect that tasks that see frequent repetition of tokens to be particularly problematic. For instance in finance it is common to see many consecutive 0s. For such a case we believe that our simple solution of including “,” every third digit is rather sensible and practical. We kindly refer to the global comment for a longer discussion on what we believe are the applications of our results.\n\n**(Q2)** *What are the positional embeddings used for the experimental settings? Can these affect the representational collapse?*\n\nWe thank you for the valuable question. Our experiments rely on the positional encodings used by Gemma (RoPE). We believe that RoPE is a wide-spread PE, for instance also used by Llama 3 [1]. Having said this, there is no particular reason that this issue is one of RoPE specifically. To demonstrate this, in the global comment we describe an ablation we have done showcasing representational collapse occurring with RoPE, Alibi [2], original sinusoidal embeddings (APE) [3], and No positional encodings (NoPE) [4].  We refer to the global comment for further details and to the supplementary PDF for the results.\n\n**(Q3)** *Minor: Some figures, like Figure 2, have a very small font size, making them hard to read.*\n\nWe thank you for pointing this out, we have now improved the readability and font size of the figures throughout the paper. \n\nWe hope that our response and additional experiments answer your questions. We are of course more than happy to keep engaging with you and thank you again for endorsing our paper.\n\n[1] The Llama 3 Herd of Models, July 23, 2024. https://ai.meta.com/research/publications/the-llama-3-herd-of-models/.\n\n[2] Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation, Press et al. Arxiv, 2021.\n\n[3] Attention is all you need, Vaswani et al. Neurips, 2017.\n\n[4] The Impact of Positional Encoding on Length Generalization in Transformers, Kazemnejad et al, Neurips, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3mMAk08JVU", "reviewer": "Reviewer_vhDf", "summary": "This paper presents an in-depth analysis of decoder-only Transformers, focusing on their limitations in handling information propagation. The authors identify two key phenomena: \"representational collapse\" due to \"over-squashing\" (line in Graph Neural Networks). These issues lead to a significant loss of information, especially in tasks involving counting and copying, which require precise handling of individual tokens. The paper combines theoretical analysis with empirical evidence to demonstrate these problems.", "questions": "1. Could you please include some statistics of difference of tokens' representations on the standard text corpora? It would be interesting to see does representational collapse happen in natural texts. \n2. How can you deal with representational collapse in real-world scenarios? Wouldn't it be worse to include random token for the information? \n3. Could this theoretical result be generalized to non-causal language modeling (different attention mask)?\n\nAlso here are some small remarks:\n\nLine 331 typo: summariesd\n\nLine 339 space in \"phenomena : representational\"", "limitations": "1. Theoretical analysis relies on several simplifying assumptions, which are justified but may not fully capture the complexities of real-world models.\n2. Empirical validation is conducted only on two specific models", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides a theoretical framework to understand the limitations of decoder-only Transformers. The concepts of representational collapse and over-squashing are well-formulated and offer valuable insights into why Transformers struggle with certain tasks.\n2. Very strong theoretical analysis is provided in paper, but the clarity of narrative is preserved. The quality of presentation is excellent.\n3. The authors provide empirical evidence from contemporary LLM, specifically Gemini 1.5 and Gemma 7B, supporting their theory. They also provide the analysis of effect of floating point precision.\n4. Authors carefully provide all the necessary details about experiment.", "weaknesses": "1. The experiments are primarily focused on specific artificial tasks (counting and copying), but the study lacks the analysis of the real-world texts. It would be beneficial to include some statistics of difference of tokens' representations on the standard text corpora. \n2. Authors provide only one artificial solution to split the sequence by different token.\n3. The theoretical analysis makes some simplifying assumptions, such as treating attention weights as independent of the input. While the authors justify these assumptions, it would be beneficial to explore their impact on the results more thoroughly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to hear that you believe our paper offers valuable insights into Transformers, has a very strong theoretical analysis, and excellent presentation. We would like to address your questions. \n\n**(Q1)** *Could you please include some statistics of difference of tokens' representations on the standard text corpora? It would be interesting to see does representational collapse happen in natural texts.*\n\nWe thank you for the thought-provoking question!\n\nHaving given it consideration, we believe that it is not sufficiently well-defined to measure token representation difference on generic natural text prompt pairs.\n\nGenerally, representational collapse can only be rigorously talked about w.r.t. a specific family of prompts which are all related by a certain property. Throughout our paper we explore a number of these.\n\nHence, to rigorously study representational collapse in general-purpose corpora, we would first need to have a method to detect specific subsets of inputs in these corpora that form a relevant family, and we find this to be a non-trivial endeavor beyond the scope of this rebuttal. Randomly-chosen pairs of natural prompts without clear relations to each other are highly unlikely to have collapsing representations due to the high diversity of tokens in both.\n\nAll this being said, we believe there are many domains where representational collapse, even just over families of prompts, can be a significant issue---some key examples include: (1) finance where it is common to find numbers with many zeros (share counts, acquisition amounts, etc…), (2) numerical spreadsheets, (3) LLMs operating over bit sequences. This list is of course not exhaustive, but provides some concrete examples in which our analysis would be likely very relevant. \n   \n**(Q2)** *How can you deal with representational collapse in real-world scenarios? Wouldn't it be worse to include random token for the information?*\n\nIn general, we believe that it is very hard to avoid the issue of representational collapse without modifying the architecture, or as you hinted in the next question, the attention mask. Solutions such as adding commas between repeated digits could work well for domains such as finance, where this is common practice to help parse large numbers. Similarly, adding “whitespace” or even avoiding repetition due to tokenization (as we touch upon in our paper)  will have the same effect. We believe that adding random tokens is likely to do more harm than good, but adding “filler” tokens is instead likely a practical solution, something that has already been observed to help in certain cases [2].\n\n**(Q3)** *Could this theoretical result be generalized to non-causal language modeling (different attention mask)?*\n\nThis is an excellent point and something that we think would be very important to comment on in our paper. Indeed different attention masks (such as the commonly used sliding-window attention), are going to behave differently to a full causal mask, both in regards to representational collapse and over-squashing. A sliding-window mask for instance can help with representational collapse as now the contribution of a single token is not forced to monotonically decrease with sequence length. It would also help fix the topological aspect of over-squashing in which tokens at the beginning of the sequence are favored, in fact it would flip this. We will add a more detailed analysis of this in a new section in the appendix, touching upon sliding-window attention and the common alternation between windowed (local attention) and standard causal attention as done in the new Gemma 2 models [1], for instance.  We once again thank you very much for this great comment and are happy to provide more details of our analysis. \n\nWe hope to have addressed your questions and point you to the global comment for additional ablations and discussions. We thank you once again for endorsing our paper. We are looking forward to the rebuttal period. \n\n[1] Gemma 2: Improving Open Language Models at a Practical Size. Google DeepMind, ArXiv, 2024. \n\n[2] Let’s Think Dot by Dot: Hidden Computation in Transformer Language Models. Pfau et al, ArXiv, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are delighted to see that our paper has been well-received by all reviewers, with comments on the high quality of the writing and presentation.

We would like to summarize the improvements we have made to our paper. We have added a supplementary one-page PDF with the additional experiments in our response as well.

- Improved discussion and experiments regarding positional encodings, now also including Alibi [1], Absolute Sinusoidal Embeddings (APE) [2], and no positional embeddings (NoPE) [3] (Reviewers SAa1 and GKd9)
- Ablation on the structure of the prompt (Reviewer SAa1)
- Added discussion on windowed masked attention (Reviewer vhDf)
- Improved figure readability (Reviewer GKd9) 

In this global comment we address in more detail topics that were touched upon by more than one reviewer.

**Effect of different positional encodings**

Reviewers SAa1 and GKd9 both asked how different positional encodings (PEs) play a role in representational collapse. The current experiments focus on RoPE, which is widely used in LLMs today, e.g. Gemma and Llama 3 [1]. 

The theory uses the fact that the effect of the positional encodings decreases with distance, which we believe applies to many of the popular encodings used today. To showcase this, we have designed a synthetic experiment testing the representational collapse using RoPE, Alibi [2], Absolute Sinusoidal Embeddings (APE) [3], and no positional embeddings (NoPE) [4]. The experiment serves as a very controlled setting to ablate positional encodings (absolute and relative) in isolation. 

In our experiment, we sample the entries of the queries, keys, and values from a standard Gaussian independently and then apply the various encodings, taking into account normalisations due to e.g. layer norm. We sample sequences of length n and create sequences of length n+1 by taking the sequence of length n and repeating the last token. We then measure the L1 distance between the two latent vectors of the last token of the two sequences. The result can be seen in Figure 1 in the supplementary PDF, noting that the y-axis is measured in log-scale. We set the hidden dimension to 64, use a single layer, and focus on a single attention head. It is clear that the different positional encodings converge very similarly, supporting our theoretical claims on representational collapse.

**Practical implications of our work**

All reviewers have asked for us to comment further on the practical implications of our work. We believe that highlighting the brittleness of fundamental operations of a Transformer-based model is important to increase our understanding of the robustness of such models and to ultimately help us improve them. The prompts we chose allowed us to more carefully measure and support our theory, as general-purpose queries may have many more confounding variables. 

We reiterate that the tasks we study (counting and copying) are essential for future agent-based AI systems. Especially in settings where AI off-loads most of the computation to other tools, it is important to be able to correctly copy the input into such tools.

We believe there are numerous real-world applications which this work could prove to be insightful for, particularly for tasks which see frequent repetition of tokens. One example is finance in which numbers could contain a large number of 0s (e.g. number of shares, company valuations, etc.), which was one of the motivations for us to test the introduction of “,” characters to delimit the repetitions. Other examples could be the processing of spreadsheets which could present many repeated values or LLMs operating over bit sequences. 

Further, we are excited by the prospects of using our work to explain existing observed phenomena in LLMs, for instance, the “lost-in-the-middle” phenomenon. We hope that our work acts as a foundation to understand further issues related to representational collapse and over-squashing in LLMs. 

We are very much looking forward to the rebuttal period and thank the reviewers for helping improve and strengthen our work with their valuable insights, questions, and comments. 

[1] The Llama 3 Herd of Models, July 23, 2024. https://ai.meta.com/research/publications/the-llama-3-herd-of-models/. 

[2] Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation, Press et al. Arxiv, 2021.

[3] Attention is all you need, Vaswani et al. Neurips, 2017.

[4] The Impact of Positional Encoding on Length Generalization in Transformers, Kazemnejad et al, Neurips, 2023.

Meta-review: The paper indicates some major shortcomings suffered by Transformer architectures via both empirical studies and theoretical analysis. The work could be further improved if the authors could explain their discoveries with more practical examples (in contrast to the toy tasks used in the paper), and it would be even greater if the authors could provide some insights for how to remedy the shortcomings. Despite these weakness, all reviewers are positive to the work, and I also agree that the work sheds light on the future studies of Transformers. Therefore, I would like to recommend an acceptance.
Decision: Accept (poster)