Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models
Authors: Hector Pasten
Felipe Urrutia
Hector Ignacio Jimenez Orellana
Cristian Buc Calderon
Cristobal Rojas
Alexander Kozachinskiy
Venue: NeurIPS 2025 poster ()
Keywords: transformers
continuity
representational collapse
Primary area: deep_learning

Abstract: Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existence of two phenomena in Transformers, namely _isolation_ and _continuity_. Both of these phenomena hinder  Transformers to learn even simple pattern sequences. Isolation expresses that any learnable sequence must be isolated from another learnable sequence, and hence some sequences cannot be learned by a single Transformer at the same time. Continuity entails that an attractor basin forms around a learned sequence, such that any sequence falling in that basin will collapse towards the learned sequence. Here, we mathematically prove these phenomena emerge in all Transformers that use compact positional encoding, and design rigorous experiments, demonstrating that the theoretical limitations we shed light on occur on the practical scale.

Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models
Hector Pasten
Felipe Urrutia University of Chile & CENIA cl
Faculty of Mathematics
Pontifical Catholic University of Chile & CENIA hector pastenluc.cl
furrutia@dim, uchile. www.aaadddmuuuiie..eeee.a
Hector Jimenez University Chile CENIA hj imenezddcc. uchile.cl cl
Cristian B. Calderon
CENIA cristian cristiann.ucoceeiaa www.bbuucaccccccmmccmo cl
Cristóbal Rojas
Institute for Mathematical and Computational Engineering Pontifical Catholic University of Chile & CENIA
luis. rowassuc.cc.
Alexander Kozachinskiy
CENIA
alexander wwwachinskiyyccmmia..... cl
Abstract
Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existence of two phenomena in Transformers, namely isolation and contimuity. Both of these phenomena hinder Transformers to learn even simple pattern sequences. Isolation expresses that any learnable sequence must be isolated from another learnable sequence, and hence some sequences cannot be learned by single Transformer the same time. Continuity entails that attractor basin forms around a learned sequence, such that any sequence falling in that basin will collapse towards the learned sequence. Here, mathematically prove these phenomena emerge in all Transformers that use compact positional encoding, and design rigorous experiments, demonstrating that the theoretical limitations shed light on occur on the practical scale.
Introduction
The massive adoption of generative artificial intelligence (AI), and in particular the use Large Language Models (LLMs), has lead to growing interest in understanding how these machines work and what they can and cannot compute [5]. While this endeavor has been primarily addressed from an empirical, task performance perspective [1 3] it has now become clear that fundamental theoretical understanding of the Transformer (the architecture behind the success LLLM- applications [19 is erucial step towards explaining and overcoming the observed limitations.
(2 20 7. This paper is a contribution to a recent trend of work devoted to the development of such an understanding by revealing the mathematical properties of Transformers 17 that underlie these limitations.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Our contribution
In this work, we identify two fundamental properties of Transformers: Isolation and continuity (see below), which severely constrain their core abilities to display basic elements of intelligent behavior.
As case study, consider the following scenario inspired by tests such IQ. Given sequence of symbols generated by simple rule, an "intelligent agent" (a human or an LLMM is presented with an initial finite portion of the sequence and asked to guess the next symbol. The agent is allowed to request to see more symbols in the sequence before providing an answer. Thus, the challenge is to eventually understand the underlying pattern and apply it.
For example, if the presented sequence is "00000000000000000 we would expect the agent to understand the underlying constant pattern and answer "0". If the presented sequence is now 21112211332222112211
we would still expect the agent to understand its periodic pattern and answer "2". A slightly more complicated sequence would be "10100100010". What is the underlying pattern? perhaps this sequence seems too short to confidently recognize it, so we request some more symbols and get
"101001
The pattern now is much more clear, let us call the increasing spacing pattern: the Is are separated by growing blocks of Os, each time with one more O. Before the last I, we see five Os, so expect the agent to answer "0" to complete, after the last 1, a block with six Os.
Given the immense practical success of LLMs, one could think that these and other sequences generated by a similarly simple rule would be easy for them to distinguish. this work, we challenge this view and argue that this is not the case for a large class of Transformers that includes most of the modern LLMs. Namely, we show that for decoder-only Transformers with compact positional encoding (CPE), the set of sequences that they can "distinguish" in the above sense is rather limited. As we will see below, these limitations have several strong practical implications.
We consider Transformers that, when presented with some prompt, compute a probability distribution over the set of tokens. Now, let us say that Transformer T eventually learns an infinite sequence of symbols a = a1 010203 ... if, for any long enough prefix of a that is presented to T, when asked "what the next symbol in the sequence?" the token that has the highest probability according to the distribution computed by T is the symbol in a that comes after this prefix.
Here, we require that the probability of the most likely token is at least some positive constant larger than the probability of any other token. This constant may depend on a and can be arbitrarily small, but it has to be independent of the length of the prompt. This is exactly when the top probability can be made arbitrarily close to 1 by setting the temperature to some small but fixed positive constant, making sure that T outputs the correct prediction with high probability.
Isolation. We establish phenomenon of isolation in the learnability landscape of any decoder- CPE Transformer T. More specifically, we show that any infinite sequence a that is eventually learned by T must necessarily be isolated from any other infinite sequence that is also eventually learned by T. This means that there is ball of positive radius around a in the space of infinite sequences such that no other sequence within this ball (except for those that differ from in only finitely many places) can also be eventually learned by T. The ball is taken with respect to the relative Hamming distance, that is, it consists of all sequences that differ from in set of positions whose asymptotic frequency is at most 8. This phenomenon is illustrated in Figure Tp. In other words, a Transformer required to learn two sequences that are too close to each other will face dilemma in the sense that can only learn one of them.
Representational collapse and continuity. What prevents ball around from containing other sequences that are also learnable by T is a strong form of representational collapse within the ball. Namely, for any sequence 3 within the ball, the output distributions T on any two long enough prefixes of a and 3 of the same length, will be so close that the top- popoobbbbylity token will be the same for both prefixes, namely the next symbol of a. Now, if 3 differs from infinitely many places, T must necessarily make infinitely many mistakes in predicting 3, which is therefore not eventually learned by T.
Such representational collapse follows from Theorem our main technical result, which is continuity of decoder-only CPE transformers. Intuitively, continuity means that making some small modifica-
2

---

tions to prompt cannot uncontrollably change the distribution computed by a Transformer. More precisely, as long as T is a decoder-only CPE Transformer, for any & > there exists threshold 5 > 0 such that, to produce a change by more than E in the distribution computed by T on given prompt, it is necessary to change at least a d-fraction of the tokens in the prompt (excluding the last token, which we always assume remains unchanged). Notably, the value of 5 for a given & depends only on I' and not on the length of the prompt. See Figure D for an illustration. In a sense, means that the only way out from isolation is for Transformer to give up certainty and thus provide its predictions with doubts. We note that Theorem ii is actually formulated for finite sequences. The conclusions derive from it for infinite sequences are meant to illustrate concrete limitation to perform inductive reasoning, understood as the ability to derive general rules and principles from the presented information. The limitation for infinite sequences means that the transformer will never be able to understand the rule that generates the sequence, regardless of how long the prompt is.
(a) Isolation
(b) Continuity
Represettatonal Collagse
Σ"
8
AΣ
T
α
B
E
8
Eventually learnable by T
Not
1/7 2/11 3/2
learnable by
da
G1
T(a) Ti
G
Figure I: Isolation and Continuity in decoder-only Transformers. (a) Isolation: Illustration of the isolation phenomenon in the space of infinite sequences V Only few sequences (black dots) are eventually learnable by the Transformer T. and each is surrounded by a region where no other distinet sequence is learnable (blue dot). (b) Continuity: This figure illustrates how two similar input sequences a, B E Σ" of length n 2 over the alphabet = {o1 22 Jy), which share the final token (a.,, 3,) and differ in two positions (dnr (a. 3) 2/n S 8), are mapped by the Transformer T to probability distributions with at most e distance in the simplex A(E).
Implications. is not hard see that for any particular infinite sequence a, there exists decoder- only CPE Transformer that eventually learns it (one can store a inside the positional encoding). Arguably, Transformer tailored like this to learn a single sequence is not very useful. We show that learning even a single additional sequence might already be problematic for LLMs. For example, isolation implies that there is no decoder-only CPE Transformer that can eventually learn both the all- O sequence and the increasing spacing pattern sequence illustrated in equation (I). Indeed, although they differ at infinitely many positions, the frequency of positions where they differ converges 0. This means that any positive-radius ball around the all-O sequence must also contain the increasing spacing sequence from [I]. Hence, by isolation, no decoder-only CPE Transformer T can eventually lean both sequences. As result, we see that not every pair of infinite sequences and B can be eventually learned by a single decoder-only CPE Transformer.
One may argue that the pattern in TT) is too complicated, since it essentially boils down to counting, a task in which Transformers have been reported to struggle before [T] (1). But what about periodic sequences? They are arguably the simplest infinite family of patterns. In fact, one can show that for any finite set of periodic sequences, there exists decoder-only CPE Transformer T that eventually learns them all. However, our results imply that the set of all periodic sequences is impossible to be eventually learned by any single Transformer. Indeed, for any T that learns the all-O sequence there is, by isolation, ball of some positive radius 5 around the all-O sequence such that no other sequence this ball that contains infinitely many I's can also be eventually learned by T. But for any k > 1/8, this ball includes the following periodic sequence:
B
00 01 00 01 00. 01
(2)
which therefore cannot be learned by T.
3

---

More generally, let us consider the concept of overwhelming strings introduced in [[]. For given transformer T. string of tokens s, fixed final token 9, and an integer m, we say that T is "overwhelmed" by if the output of 7 evaluated on 8 plus any additional string 1. and fixed final token q. T(s + + q); the same regardless of the chosen string f, as long as its length is at most m. In other words, being overwhelmed by some string means that T is completely insensitive to the part of the prompt that contains t. As pointed out by [16], this has several important practical consequences. For instance, it can be used to show "no-go" results in prompt engineering, or to prove severe limitations of transformers to compute highly sensitive functions (such as PARITY). As an immediate consequence of our work, it follows that if is infinite sequence eventually learned by T. then T must be overwhelmed by any sufficiently long prefix s of a. Indeed, by isolation, there exists 8 > 0 such that appending m arbitrary tokens to (but keeping the same final token) leaves the output of T unchanged whenever m/ /[(s| + m) < 6, where |s] denotes the length of 8. In particular, T will be overwhelmed by any such 8.
1.2 Related work
As have already mentioned, our work shows that every Transformer is overwhelmed by infinitely many strings, a concept introduced in [16]. Their results are however of a different nature, as they focus on developing algorithms to rigorously detect whether a given Transformer T is overwhelmed by a given string 8. Our work is of theoretical nature, proving continuity and isolation and stipulating the associated limitations in decoder-only Transformers.
Continuity has been used before to demonstrate difficulties that Transformers have in learning func- tions where small changes in the input leads to substantive change in the output (e.g.. PARITY) [6] Moreover, was shown that for such functions, as the sequence length increases, the loss landscape becomes more steep. leading to further complications in the learning process 77]. Importantly, previous continuity results have only been established for encoder-only Transformers, where each token attends to the whole input, not only previous tokens in the decoder-only case (i.e., with causal masking). Under the encoder-only assumption, due to dispersion of softmax coefficients (20) flipping the value of one token leads to a O(1//)(change in other tokens (6]
The same is not verbatim true for the decoder-only architecture, and this constitutes the main difficulty of extending continuity to it. The problem is that causal masking breaks the symmetry of tokens in softmax, and earlier tokens have more influence. Flipping, say, the first token, leads to significant changes not only in itself but in the few first tokens also, given that softmax coefficients not too dispersed for them yet. A careful argument is required to show that this effect can be controlled, and this is the main technical contribution of our paper.
Representational collapse in transformers, as far as we are aware, has been previously observed by Barbero et al. [ only in the special case of two input sequences that are identical except that we repeat the last token in one of them (which is therefore one token larger). Moreover, their result requires two important assumptions: (i) the distance between the coordinates defining the positional encoding tends to as the input sequence length increases, (ii) the absence of positional information at the level of Value matrices. Whereas the second assumption is in line with the widely used and state-of-the- rotatory positional encoding method (T8), it does nor allow to extrapolate the results to other positional encoding methods. The first assumption is simply absent from any standard application of LLMs.
In comparison, our results apply in much more generality. We just need the value, the attention, and the activation functions be continuous. Therefore, they apply far beyond the standard dot- product softmax attention with activations computed by MLPs, even the Lipschitz property, crucial for the Hahn's 's continuity argument [6), is not required for our proof. Besides, as mentioned before, we require compactness of the positional encoding, but in contrast to [I] we can freely use it at the level of values, not only in attention.
1.3 Experiments
In the remainder of the paper, we first define the continuity theorem (Section 3). followed by the isolation one (Section 4 All the proofs of our theorems and lemmas can be found in Appendix
A For each theorem we present a series of experimental results to illustrate the extent to which the limitations predicted by our theorems can be observed in practice. We do this for several of

---

the most recent versions of modern LLMs. We investigate continuity in three applications: the all-O sequence, a Python code syntax error detection task, and a natural language inference task. For isolation, we evaluate how well decoder-only models can generate periodic sequences. Our results not only provide strong evidence that our theoretical findings are relevant in practice, but also offer comprehensive picture of how the specific differences among these modern architec- tures affect the severity of the observed limitations. Code for our experiments can be found at ? furrutiav/dout wwwttts/wwoo-ooeeooaooao andoubbs-andddii and-dil emmas- commas-neuripee neur ip225
Preliminaries
By || || in this paper we mean the 5o norm, but all our results hold for any other norm due to the equivalence of any two norms in æ up to a constant factor.
Attention layers The main part of the Transformer architecture (see Figure 6 is the attention layer.
Definition A d-dimensional decoder-only attention layer a function L: (R + (I")',, given by "positional encoding" " p: N2 - Rd continuous "value function" val: Red - Rd confinuous "weight function" w: (Ra)3 + (0, +00), and continuous "activation function" " F: RR. x Rd + TR.d.
Given an imput sequence of vectors (Ii,..., In)) (IR")" "m, the layer L outputs a sequence of vectors y = (y1....., Un) = L(t), computed as follows. Pirst, one computes the "attention weights" and "values":
Wij w(a; Ff.
i = n. isi
V/ val(z,), j= L,...... n.
then sequence ā = (a1...., an) of "attention vectors" as follows:
W1 02 +...... + W4y 0j Wij w2j + ... Wii
j=
and finally, one sets Vj F(a,. 2z),
j 1.....m.
Observe that Vj. the j-th output of I. on input (.1,..., Fn), depends only on 21..... Fy. This implies that decoder-only attention layers are pprefix-monotone functions: if 81 is a prefix of T2, then L(ū1) is prefix of L(ū2).
positional encoding p: N2 + Rd is called compact there is a compact C Rd such that p(i.j) K for all i E N.
Transformers By Transformers we mean functions that maps finite words over some alphabet E to probability distributions over letters of Σ. To be more in line with terminology, accepted in the study of transformers, we refer "words" as "sequences" and to their "letters" "tokens".
The set of probability distributions over a finite set is denoted by A(E).
Definition 2. A d-dimensional k-layer decoder-only Transformer over finite alphabet Σ is function T; Σ - A(E), given by an input embedding e: Σ x + Rd, k d-dimensional attention layers Li..... Lt, and continuous function P: R.d A(E).
On an impul sequence of tokens a .....Oa E Σ", the outpul probability distribution T(a) is computed as follows. First, we
Tj = =((aj,)), j j= 1.....,11 Then compute the composition of attention layers Lı, La on the input sequence of vectors: (y1,..., Un) = Ta .... Ia (21,..., nn)
Finally, we sei T(w)= = P(yn).
An input embedding is compact if for some compact C Rd we have e(a, E K for all a e Σ, i E N. Overall, we call Transformer T compact if it uses compact input embedding and compact positional encoding in all layers.
For notational simplicity, we assume that each layer has just I attention head. However, our model subsumes the case when an attention layer can have ((1) attention heads as we can just compute each head in a separate layer.
5

---

3 Continuity
Let dh (a, denote the relativized Hamming distance between two sequences of tokens a, B E "":
H {I.....m] as + Bil
du (a,
Theorem 1. Let T be compact decoder-only Transformer. Then for any E O there exists > such that for any n E N. for any sequence of tokens a, 3 E En with the same last token, if du (a, B) S 8, then [T(a)) T(3)ll E.
Corollary 1 (Next-token propagation principle, informal). Given CPE decoder-only Transformer, two prompts are very similar, end in the same token, and the next token prediction for one of them computed with certainty, then one can expect that the next-token prediction for the other sequence is the same as for the first one.
3.1 Empirical support for continuity: Zero fundamental sequence
We investigate the behavior of decoder-only language models when presented with two highly similar prompts (whose Hamming distance small), denoted a and 3. According to Corollary I the Hamming distance is small enough, then expect the model to produce the same next-token prediction for both sequences. In order to test this (see more details in the Appendix [B.2. we define input prompt
sequence of 190 consecutive zero=]] We also generate 100 sequences
82. 2,. 80000 independently, where 33, is generated perturbing a at max LY 189]) positions chosen uniformly at random (ignoring the last position) and y E (0, 1/2] controls the proportion of differing positions. Thus, the relative Hamming distance between and B is (almost) 7. All the sequences (including ()) are appended to the common instruction prefix: "Complete the sequence with Os and 1s:", and submitted the model as input. We then generate the token (o) and N (Bt) for every = I,..., 100. We measure the model sensitivity, counting how many 3's produce the next token different from the next token of a (in our case 0), i.e.
(T) = { E {1, 2, ... 100} (st)) * N(a)).
where a higher count indicates greater sensitivity to changes in the input.
y<
0.2
Model
80
gpt2
llama-2-75
60
gpt2-large
Meta-Llama-3a Llama-3-88
gpt2-xl
Meta-Lama-3-88-instuu.
40
gemma-2b
20
gemma-2-2b
phi-1_5
gemma-3-4b.it
phi-4
0
.01 .05
.15
22
.25
3
.35
.4
.45
.5
Prop. differing symbols (y)
Figure 2: Sensitivity of decoder-only language models to input perturbations at < 0.2 and 2 0.2.
As shown in Figure 2 the results support the Corollary T If the proportion of differing symbols is small enough (y = 0.01, corresponding to symbols), the number diverging samples is null for all the models, suggesting the existence of an attractor (representational collapse) around the all-zero sequence. In fact, even at = 0.05 (9 symbols) the value of NTS., is 0 for all models except two, observe that smaller models sometimes expose larger sensitivity
phi-4. Somewhat surprisingly, (larger value of NTS.). for example, gpt-2 and gpt-2-x1.
Furthermore, we analyzed whether sensitivity is impacted by the location of the perturbations in the sequence. Across models, we found a consistent trend: sensitivity is the highest when perturbations occur at the end of the sequence (Appendix B.3).. Middle positions result in lower sensitivity, and carly tokens yield almost no sensitivity at all.
Additionally, we observe that modifying the standard attention (softmax) with the log-length scaled attention (ssmax) yields a marked increase in sensitivity (Appendix [B.4). This support the assump- tion that compact positional encoding in attention weight posses a key role on the effect of input perturbations.
We chose this number to ensure small enough ė for all selected models.

---

3.2 Empirical support for continuity: Code Syntax Verification
We now turn to LLM application. As in the previous section, we consider decoder-only language models that receive two similar prompts, ar and |8, differing up to a small Hamming distance. According to Corollary D for sufficiently small Hamming distances, we expect the model to produce the same next-token prediction for both prompts, even though the task requires the model to provide different outputs. Of course, different models will typically have different thresholds below which the Hamming distance classifies as being sufficiently small in this sense. However, even if some small Hamming distance is not quite below the theoretical threshold of a model, we still expect the model to predict the same next token on a large set of pairs of input sequences. SYNTAX VERIFICATIO is designed precisely to visualize the extent to which this phenomenon can be observed at scales of practical relevance.
(see Appendix B.5 for design explanation), more practical
Our and 3 prompts share the same structure, as illustrated in Figure T0 Each sequence begins with the same main instruction (MI), followed by three Exercises, namely, two example exercises (shots) and one test exercise. Each Exercise E; in the prompt consist of four components: an Instruction, a Python Code snippet, a Question and an Answer. The a and 3 prompts share the same first two Exercises, but they have a small discrepancy in the test case Exercise. The two prompts differ in a single token within the test Exercise (blue boxes Figure [O] Appendix [B.]]. In the particular case of Figure IO the prompt includes the "=" token in the correct version, which is replaced by the "for" token in the prompt (incorrect version P For all tests, we query the LLM in the same way: "Does the following Python code compile without syntax errors? If no error is detected, return 1; otherwise, return 0.".
We built dataset of 100 python function exercises presented in two versions, with and without syntax error. Each exercise embedded as a final test exercise in both (correct and incorrect) formats (Figure 10P. We consider model to be sensitive if it produces different answers when presented with the a and 3 prompts. More specifically, we give to the model the prompt a and generate a token o. Then we compare the probability of a under the prompt (denoted by P(ala)) with the probability of the same token a under the prompt 3 (denoted by P(a|3)) To visualize sensitivity, we plot a point with coordinates (a(ala). P(a (3)) Intuitively, any substantial deviation from the diagonal line should correspond to trials where the model is sensitive, and vice versa.
Our results are depicted in Figure While a vast majority of the examples do not show sensitivity. the proportion of trials where sensitivity is observed varies significantly across different models. First, we observe that model size (at least within the same family, see gemma-3 models) has an influence on sensitivity, with bigger models displaying more sensitivity. Second, phi-4, model that is primarily trained on code, fails spectacularly, providing the same output for all cases (a rather striking result). Lastly, Meta-llama -----a-------- Instructt displays sensitivity in 21% the examples. These results suggest that while the theoretically required Hamming distance might be quite small and heavily depend on the particular model, the consequences of its existence may well become relevant at scales of practical interest.
3.3 Empirical support for continuity: Natural Language Inference
To further provide support for the continuity phenomenon at the practical scale, we evalu- ate an LLM on natural language inference (NI.)) task analogous to the SYNTAXVERIFICA TION task. The new dataset consists of 50 examples derived from the babi-nli datasef") Each instance includes a premise, a hypothesis, and a label (0 or 1). To meet theoretical requirements, we lengthen the premise using neutral text from Wikipedia, creating a long- premise that preserves the original label and constitutes the sequence. To create the cor- responding 3 sequence we modified a single key word at the beginning making sure that it entails change to the original label. For example, we define premise a (with positive label) as "Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the apple there..." We define premise B (with the opposite label) as "Yann is hungry. Jason is bored. Antoine is hungry. Yann
In practice, we define a as the prompt generating the greater discrepancy between the top-1 and top-2 token probability.
7

---

Sensitivity
No Sensitivity
gemma-3-4b-it
9emma-3-12b-it
phi-4
Meta-Llama-33 8B-Instruct
1.00
0.75
P(a
0.50
0.25
7%
9%
0%
21%
0.00
P(oja)
task. This figure illustrates the sensitivity of five models to subtle syntactic changes Python functions for pairs of input prompts. Each dot represents the model's probability assigned target token under two prompts, and B. Blue dots indicate sensitive cases where the model's output changed in response to the syntactic errors, expected. Orange dots mark non-sensitive cases where the model failed to adapt its prediction, despite the change in input. Percentages in each subplot indicate the proportion of samples where the model exhibited sensitivity.
Figure 3: Sensitivity in the
went back to the kitchen. Yann picked up the pear there...". ". We then define the hypothesis as "Yann picked the apple because she was hungry.".
Considering that Meta-LLlma--3-B-- Instructt provided the best results in the VENTAXVERIFIE TION task, we tested this model on the new NLI task two scenarios with different input lengths, ranging from = 1000 tokens to = 7500 tokens. As depicted in figure our results show that both accuracy and sensitivity decline with input sequence length (as predicted by Corollary [T]
Our results demonstrate that, even in this simple natural language inference task, sensitivity remains fairly low. This experiment thus provides important limitation stemming from Theorem 1 the practical scale.
0.30
0.625
Sensitiity (96)
0.20
0.575
0.15
0.550
0.05
1000
3000
5000
7000
1000
3000
5000
7000
Figure Accuracy and Sensitivity of Meta-Llama-33 --------r-t---tuuttttt in the NLI task.
4
Isolation
We start with a formalization of the notion of eventual learnability. Definition 3. A decoder-only transformer T eventually learns infinite sequence 0'10203 DH if there exists e and ni such that for all 2 nig we have
T(a ... a.) 2 ... T(a))....,(())))
for any E E fan+1).
An casy consequence of Theorem I is that eventual learnability is not affected by making finitely many changes in sequence.
Proposition 1. Let T be compact decoder-only transformer, and ax, & E En be two infinite sequences, differing only in finitely many positions. Then T eventually learns a if and only if eventually learns å.

---

We now formulate our isolation theorem. For that, we require an extension of relative Hamming distance to infinite sequences:
d B) inf du (a1 ... .n.an ....8p)) B,),,
a, E"
n=000
Theorem 2. Let T be a decoder-only compact transformer. Then for any infinite sequence a, eventually learnable by T, there exists 5 0 such that infinite sequence that differs from or in infinitely many positions and satisfies d. (0, 33 S ó is eventually learnable by T.
Equivalently, this theorem states that if a set of infinite sequences S has point a E S such that arbitrarily close a in dy distance there is a sequence from S that differs from a at infinitely many positions, then no decoder-only compact transformer can eventually learn all sequences from S.
In particular, if two sequences o; 3 differ in infinitely many positions but satisfy du (a, 3) 0, then no compact decoder-only transformer T eventually learns both of them. For example, there is no decoder-only compact transformer that eventually learns more than one of the following sequences: (i) The all-zero sequence (0, O.... (ii) The indicator sequence of the powers of 2, (iii) The indicator sequence of the squares, and (iv) The indicator sequence of the primes. Indeed, we just have to note that any two of these sequences differ in infinitely many positions, but their relative Hamming distance is O.
One can show that for any finite family of infinite sequences that are all a positive du disttanecce away one from another, there is single decoder-only transformer T that eventually learns them all. In particular, this applies to any finite subfamily of the family of periodic sequences. However, the isolation theorem implies that this is not doable for the whole family of periodic sequences.
Corollary 2. There is no decoder-only compact transformer that eventually learns all periodic sequences.
4.1
Empirical support for isolation: Periodic Pattern Generation
To test Corollary
2
we consider periodic sequences of the form 88 = (0P-11)'0, i.e.
1st block
7th
8 01
0. 01
01
blocks of length
where p is the period and r the number of repetitions. We construct input sequences appending 3 to the common instruction prefix: "Complete the following periodic sequence with Os and 1s The model is then evaluated to continue the pattern over 505-autoregressive steps.
We assess performance using two metrics: (i) Success (binary metric) captures whether the model perfectly reproduces the correct continuation. A correct sequence yields a checkmark (V), while any deviation results in a cross (X), and (ii) Certainty (metric between 0 and 1) is measured as the difference between the top two probabilities for the next token after (p attorrrregee steps") larger difference indicates greater model confidence.
Figure 5 presents results from the .llam-227bb-be model across 1, 4, 10 repetitions and periods from 2 to 40 (see Appendix BB7 for an extended analysis to a broader set of models with varying sizes and architectures). Columns correspond to different numbers of pattern repetitions, which can be thought of varying the number of examples (here the pattern to be repeated) seen by the model prior to the generation phase. Our results show that there exists critical period beyond which the model cannor successfully learn the periodic sequence correctly (first row; predicted by Corollary 2}. This critical period seems to increase with the number r of examples the model is shown. Lastly, certainty (second row) shows that the difference in probability between the two top tokens displays small dip for the next-token. This dip becomes more pronounced around the critical period, where the model initially predicts the first one token (blue dots) correctly, but then begins to generate the zero token (pink dots) instead.
At this stage, expect to predict the first one token following the generation of p zeros.

---

1
10
Certainty Success
1
40
20
40
20
40
Period (p)
Figure 5: Evaluation of periodic sequence generation using Llama-2-7b--h 2--
5 Conclusion Doubts and Dilemmas
Our results show that Transformers (or, maybe, their developers) face inevitable dilemmas: even among very simple sequences they have to choose some that they will not be able to learn. This relies on fundamental properties of continuity and isolation but also of doubts - the next token has to be predicted with certainty, its probability has to be the largest one with some margin. One could avoid dilemmas by giving up the no-doubts assumption, but one cannot avoid both - continuity and isolation imply that either dilemmas or doubts (or both) will be faced.
assumption about the absence
It is worth noting that the limitations we identify are not inherent to all sequence models. As shown [1], simple state-space models such as RNNs can recognize any regular language. Thus, Theorem [ can be seen establishing formal separation between the representational abilities of RNNs and Transformer architectures. This suggests a principled reason for why augmenting Transformers with state-space components (as done in models like Jamba) may help overcome representational collapse.
Limitations The key requirement for our results is compactness of positional encoding (meaning that its vectors are bounded in norm by some absolute constant). This subsumes such standard positional encodings like sinusoidal [9 and rotary [18] but not some others like absolute positional encoding or log n-scaling
(now referred as scalable softmax (14). Local layer norm is subsumed by our model as well because it is continuous transformation, as long as some positive constant is worth to point out that some
e 0 is added to the denominator (as standard in practice). theoretical works have considered layer norm with = 0. In this regime, layer norm falls out of the scope of our results, as it is no longer continuous (and is not even defined when the denominator is 0). Using layer norm with E = O, Chiang and Cholak 4 compute PARITY with arbitrarily high certainty, thus escaping continuity limitations (see also g where these limitations are avoided due to the use of unbounded positional encoding).
Another potential way to escape continuity limitations the use of thain-of-thought (CoT; see Appendix [B66 for preliminary analyses). As long as just O(1) CoT iterations are allowed, this is subsumed by our results (our model allows for any constant number of layers, so we could just add more of them, simulating each CoT inference in new layer). Now, when the number of CoT iterations grows with the input length, this logic breaks, and the models might potentially become much more intelligent. Indeed, on the theory side, it was shown that transformers with unbounded number of CoT inferences become Turing complete [3 10). However, none of these results is obtained for softmax with compact positional encoding, leaving the theoretical power of CoTT-equipped transformers in this regime open.
Acknowledgments All authors are funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Kozachinskiy is supported by ANID Fondecyt Iniciación grant 11250060.
References
[1] Federico Barbero, Andrea Banino, Steven Kapturowski, Dharshan Kumaran, João Madeira Araújo, Oleksandr Vitvitskyi, Razvan Pascanu, and Petar Veličković. Transformers need glasses! information over-squashing language tasks. Advances in Neural Information Processing Systems, 37:981 17:98111-9988 11-98142 2024.
10

---

[2] Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006. 09286, 2020.
[3] Sébastien Bubeck, Varun Chadrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lec, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, 2023.
[4] David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7654-7664, 2022.
[5] Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems. 35:30583-30598, 2022.
[6] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 8:156-171, 2020.
[7] Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14973-15008, 2024.
[8] Alexander Kozachinskiy and Tomasz Steifer. A completely uniform transformer for parity. arXiv preprini arXiv:2501.02535 2025.
[9] Alexander Ku, Declan Camphell, Xuechunzi Bai, Jiayi Geng, Ryan Liu, Raja Marjieh, Thomas McCoy, Andrew Nam, Ilia Sucholutsky, Veniamin Veselovsky, et al. Using the tools of cognitive science understand large language models different levels of analysis. arXiv preprint 1rX1v:2503.13401, 2025.
[10] Zhiyuan Liu, Hong Liu, Denny Zhou, and Tengyu Ma. Chain thought empowers transformers solve inherently serial problems. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
[11] Kyle Mahowald, Anna A Ivanova, Idan Blank, Nancy Kanwisher, Joshua Tenenbaum, and Evelina Fedorenko. Dissociating language and thought in large language models. Trends in cognitive sciences, 2024.
[12] William Merrill. Sequential neural networks as automata. arXiv preprint arXiv: arXiv: 1906.06615 2019.
[13] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
[14] Ken M Nakanishi. Scalable-softmax is superior for attention. arXiv preprint arXiv:2501.19399 2025.
[15] Jorge Perez, Pablo Barcelo, and Javier Marinkovic, Attention is turing-complerd Journal of Machine Learning Research, 22(75):1-35, 2021.
[16] Lev Stambler, Seyed Sajjad Nezhadi, and Matthew Coudron. Provably overwhelming trans- former models with designed inputs. arXiv preprint arXiv:2502.06038, 2025.
[17] Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543-561, 2024.
[18] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, Neurocomputing, 168:637 2024.
11

---

[19] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances Neural Information Processing Systems 30: Annual Conference on Neural Information P Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998-6008, 2017.
[20] Petar Veličković, Christos Perivolaropoulos, Federico Barbero, and Razvan Pascanu. softmax is not enough (for sharp out-of-distribution) arXiv preprint arXiv:2410.01104 2024.
[21] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682, 2022.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we demonstrate theoretically the phenomenons of Isolation and continuity in Appendix and provide the theorems in the main text. We also test the corollaries in the main text, that give support to the theorems.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the limitations are discussed in paragraph within section 5
Guidelines:
The answer NA means that the paper has no 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 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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
12

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All complete and correct proofs are provide in appendix A
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 if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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 ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, all the information to replicate the paper is available in the text and appendices. Nonetheless provide the code that can replicate all the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
13

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Yes, the data and code are open and available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/ mablic/guidess CodeSubmissionnoll
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 new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwwpc/pwwcpp.pcdccoccooooo wwtp:///giiiiseee http//oeeeuaiiisioooooooooooee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, the paper does include all the experimental details to reproduce the work.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
14

---

Question: Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Although we have experiments, our results do not focus on statistical analysis to make our point.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi-
dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етгог rates).
If error bars are reported in tables or 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
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does include experiments, but only at the inference level and compute inference time is irrelevant to this work.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics ttttps//neuurps. http:p::///errrsss.ppppp//c/eeee cttpppublcc/Ehicccccueeeeeeee
Answer: [Yes]
Justification: Yes. the research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
15

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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]
Justification: There is no societal impact related to our work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.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]
16

---

Justification: All the creators and original owners of assets are properly credited and all use are respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thcode com dantsatsssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ss 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: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
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 an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
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 research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
17

---

Answer: [NA]
Justification:
same justification as question 14.
Guidelines:
The answer NA means that the paper does involve crowdsoureing 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used in the writing of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httpes///hecrrgpccc////ooeeeeeep for what should or should not be described.
18

---

A Missing Proofs
A.1 Proof of Theorem
Proof. Given two sequences of tokens 01 .......0 00, 01....0,;33 81 ... Pn En with the same last token and (a, () S 6, we input them into the Transformer as sequences of vectors
= e(a1, 1), ,IT = =(aa.:
= e()
(3)
Since the input embedding is compact, all vectors Ti, Ty belong to a fixed compact set K (not depending on n, u, v). The last vectors 2ny Fin coincide (given that the last token of and 3 coincide). Besides that, sequences of input vectors coincide in at least (1 - 6)n positions (ar and B coincide in least (1 8)n positions).
(t)) We have to show that the last vectors yn yn will stay sufficiently close throughout all layers of our transformer T,, where
(v1
(
,....!!!!!!"
output sequences after attention layers of T on (#1...... In) and on f ($1. 2,). respectively. More precisely, for any & > O, we have to show that the existence of å > 0 such that conditions d (u, v) S 6, un = Un imply I1 - In - Se.
We show that through induction by the number of layers. To make this work, have to strengthen the statement we are proving by induction - it will not be enough to just show that after one attention layer, the last vectors stay sufficiently close. We will also have maintain that sequences of vectors stay sufficiently close to each other "globally". We will establish this through a lemma, staying roughly the following: for any attention layer L, if two input sequences of vectors are sufficiently close globally, and their last vectors are also sufficiently close, then the output sequences stay sufficiently close globally, and the last output vector stay sufficiently close as well.
We define "global similarity" between two sequences of vectors as follows. Given x = (Zi,..., Fnn E (Id))" and F = (01, , 2n,) E )", define sim(z, T) as the minimal 6 2 such that || - T; S for at least (1 8)n positions
n.).
Observe that for input sequences in (3), we have sim .) S. 8 (just because they coincide least (1 - 8'nn positions). The following lemma finishes the proof of the theorem, establishing that global similarity last- dast-position similarity is preserved through an attention layer.
Lemma 1. Let L be decoder-only attention layer with compact positional encoding, and let K Rdd be a compact set. Then for any & > there exists > such that the following holds. For any n E N, and for any two sequences of vectors x, 22 E K", we have:
sim(x, S 28, || Enll S =
sim (y, 2 S,, 1ly. -iall Se.
where
(11 (U1,... ......;;'ll. vn) I(x),
1 ... Fm) = L(T)
The only thing it remains to note, besides the proof of Lemma] 1
why after any number of layers, the vectors yi ((() belong to some compact set K, depending solely on the transformer but not on n, u, v. This proved by induction over layers by continuity of the value and activation functions vol and F. The output in the n-th position of an attention layer is computed as yn. = F(a,,, Zn). where I, the input vector the attention layer in the n-th position, and a, is the attention vector in that position. All vectors Fn come from compact K. Value vectors 2n = val(x,,) thus belong to wal(K K), which a compact set by continuity of val. Take now any closed ball B containing both K and val(K) Vectors an, as convex combinations of u 's, belong to B. It remains to observe that F(B x B) is compact by continuity of F.
A.1.1 Proof of Lemma 1
turns out that it enough to establish the following weaker version of Lemma where we forget about global similarity of output sequences y, ÿ.
19

---

Lemma 2. Let L be decoder-only attention layer with compact positional encoding, and let K F. be a compact set. Then for any E >> there exists 5 > such that the the following holds. For any n E N, and for any two sequences of vectors x, E E K we have:
sim 3) S 8, 1|
Fn
Σ 8
11 Full S E.
where
y = .U........) = (xx),
y (11. Dn) = L(Φ).
Let us start by deriving Lemma | not only the last two output vectors ynu Un are E e-close (as Lemma 2 says), but at least (1 - E) output vectors e-close.
from Lemma 2
We have to derive that if 8 is small enough, then
Imagine we start with two sequences of vectors x, K" such that sim(a, 2) I and ||,,, F.1ll - 6. Let E S .I.....n} be the set of "bad positions" (where || Z > 8). By definition of the similarity distance, its "relative size" (the fraction [EI/n) is at most Next, for any 61 > 0, by choosing 5 to be small enough, we can achieve that the relative size of E in the restriction to the first j positions, for any j 2 en/2, does not exceed őj. For instance, by setting 8 (21e)/2, we can bound:
E (1,........ HHl <
E
8n
8nn. en/2
In particular, we can do that for 61 with which the conclusion of Lemma i true for E. As we are firee to choose 8, we also assume that å S. 81. We claim now that 3/ أ S for any j 2 en/2. j $ E. This because all input vectors in positions not from are 01 -cooee (because they even 5-close), this includes 2y. By j & E. and the number of the first j positions not from E is at least (1 - 81)j.
As result, we can have 11y;- 01 > only for j E E or for j < enn22. Thus, we can bound the number of such positions by em/2++ + 8n. By making sure that < <e/2, we obtain that sim(y. D) S e.
remains to establish Lemma
Proof of Lemma 2 Take closed ball B with the center 0 that contains K, val(K), and p(i, j) for all j E N. Such B exists because K is compact, vol is continuous which means that val () is compact, and because the positional encoding is compact meaning that j(i.j) all belong to some fixed compact for j E N. Observe that on both inputs, aj 's (attention vectors). also belong to B as convex combinations of values vectors. Let be the radius of B.
We have
Yn F(anz
On F(ān,,
where F is the activation function of L., and an; an are the n-th attention vectors on inputs x and T, respectively. By uniform continuity of F on the compact B x B, there exists 81 > such that
la,, a, S 81, ||=., xn s 81
[|F(an, Inn - F(ān. 2n) S
It now suffices to show the existence of 0 < < 81 such that
sim((x < 8, || - 2nll 8 - I|an - ān S ò1.
Let w: (Rd)3 - (0, +o)) be the weight function of L. We apply only inputs from a fixed compact set _3, Hence, we can assume that for some universal constants 0 < c < C. the function w takes values in [c. CJ. Moreover, by the uniform continuity of w on B3, if we change each of inputs by at most in the norm, the output value changes by at most cs, for some C5 - 0 as 8 + 0.
Similarly, there exists da with ds > 0 8 + 0 such that [|val(x) val( < ds for all 2, K with || - ell < 6.
The norm of the difference an Un can be bounded as:
(wnn;WW, Win 3g Wn)
Win Wn, - Wn
|a, - Tn.l
(4)
W.W.n.
W,, Wr
20

---

where
2/ val (x+),
6 va](()
= w 24, Fn p(i, n2),,
Win = w (2,, Tni n)),
i = ,,..., n,
W, Win .... + Wan:
W = Win +... ..... + Wan.
Let E denote the set of positions i {l...., m) with 12: Till > 8. Since si, 3) S 8, we have [E] s ón. Since we are additionally given that || Fall S 6, by definition of că, we have:
Win winl S
for i E.
(5)
In tur,, by definition of dg. we have:
104 0: - d8 for i $ E.
(6)
Now, since the function w takes values in the interval [c, C}, obtain the following bound:
WWin 0inl S 2C
for i E
(7)
From 5 using the bound |E| S on, derive:
W, Wn Win Winl +... Wnn Winl egn + 2C| S (cs + 2C8)n
(importantly, the coefficient before n in the last upper bound goes to 0 as 8 - 0).
We now upper bound the right-hand side of 4 First, the denominator there is at least n2n2 because the weight function is at least for inputs under consideration. It remains to upper bound the numerator by an expression 16))2 for some function ʃ(ő) as d + Each term in the numerator we bound using the triangle inequality:
Winn W. Win Wn
I [[ Win W
+ @| (wn wu
+ @ Wn - 0,)1|-
We have Win, Win I C, Wn, Wn I Cn, and ||w/]|, | < R (the weight function is bounded from above by C, and value vectors U, come from B, the ball of radius R with the center at the origin). Overall, we get:
||wia W G. W. & (Iw, - 0inl CR + WW. W./nl CR + ||0 - 0/ C²)n
For & E, this expression is bounded by o(1) as ō + xc by 5 6 and
8
For i E E, this
expression is On)) Overall, the numerator in (4) upper bounded by o(1 n
|E] O(n) S
o(1)n² + O(ōn²) o(1) (1) as 5 + 0, as required.
Remark 1. Since for Encoders the proportion of exceptions does not change with the iterations (as in the decoder-only), the Theorem also holds for them (and the argument is actually simpler).
A.2 Proof of Proposition 1
We show that if a compact decoder-oni, transformer T eventually learns a, and â differs from a in finitely many places, then T eventually learns à too. By definition, there exist E >> O and no such that for all n 2 no, we have:
T(a1...
for any a E Σ {ax+1). }. We show that the same holds for @ and for all large enough n with e/2. By Theorem [] there exists 8 > 0 such that on any two sequences of tokens with the same length, the same last token, and of relative Hamming distance at most 8, the output distributions of T are (E/ (E/10)-ue -clooe norm. Since a and differ just in finitely many places, we have a, = Ca, Ux+ = an+1 and d ...,, a ...) < 5 for all large enough n. For such if we replace every occurrence of by in (9). the left-hand and the right-hand side change by at most e e/10, preserving the inequality with e/ e/2, required.
21

---

A.3 Proof of Theorem 2
If is eventually learnable by T, by definition, there exist and ny such that for all nu. we have:
T(a ... (n)(n)+1) 2 T(a1
... ........))))))) (o) +
(10)
for any E Σ (an+1). By Theorem | there exists d > such that for any two finite sequences of tokens that have the same length, the same last token, and are of relative Hamming distance most the output distributions of 7 on them are s/3-close in the l -norm. We now take arbitrary infinite
sequence that differs from in infinitely many places and satisfies dæ B) 8 min{6/3, 1/33. and show that 3 is not eventually learnable by T'
To this end, it is enough to show that
T( ... (an(1)+1) > T(31..... (3))(11))))
(11)
for infinitely many n. This would contradict eventual learnability of by as Ba41 has to be the top-probability token of (33 ... ...) starting from some n.
We take an arbitrary No E N and show the existence of n 2 No for which holds. Since
du (a, 5) lim inf d (a) ... ... an, Bn) 2
15-000
there exists m 2 max m2.o 2ng} such that d ... Om: 31 Bm) S 1.15. The sequences Q1 ... O'm and B1 ......,. cannot differ in all positions of the second half of these sequences because
their relative Hamming distance is bounded by 1.18 < 1.1- (1/3) < 1/2. Hence, we have ay = 3 for some E (m/2, m). The relative Hamming distance between 01 ... Og and - is at most twice the relative Hamming distance between d1.... Om and 31 ...3mm Indeed, the first pair can only have fewer differences, and the length of sequences in the first pair (that goes into the denominator in the relative Hamming distance) is at most twice smaller than in the second pair. This gives us
33
du (n .1. 3.) < 2.25 < 2.2(6/3) <
for some 2 m/2 2 max No, not such that On+1 # Bn+1 which exists because a and have infinitely many differences. Observe that:
3.. Take the smallest 2 such that
d ... an ...). S dd ae, B .......3.. 31) 5
because 01 ... an and 81 .....& 3n obtained from a1... ... 0g and 31 ... 3g by appending some number of equal tokens. By definition of 6, the distributions [(a ... an. and T(31... 3,,) are (e/3)-close in the foe norm (observe that an 3n otherwise and continuity can be used). Since n 2 2 no. we have (IO) for n. we replace T(a ... ...aa))))))))) by T(3... .. 3r,), both the left-hand and the right-hand sides change by at most e/3, meaning striet inequality is preserved for any a, in particular for a = 33+1- We thus obtain 11 T for n 2 E 2 No. required.
could take smaller n, the last tokens coincide
A.4 Proofs of Corollary 2
For Corollary
2 assume for contradiction there decoder-only compact transformer T that
eventually learns all periodic sequences. In particular, it learns the all-O sequence, and by Theorem 2 there exists such that no sequences 3, having infinitely many and satisfying du 33) S
is eventually learnable by T. On the other hand, there is periodic sequence 3, satisfying these restrictions, namely
8 00 01 00 01.00.0......................... 010....01
for any 2 1/5. It has infinitely many 1s, but dh (a, 3) = 1/k < 8, a contradiction.
B Supporting figures
B.1 Visualization of Decoder-only Architecture
preseetss a high-level visualization of a standard decoder-only transformer, illustrating how an input string is processed through k attention layers in causal and sequential manner. Each
22

---

token is first embedded via function and then transformed layer by layer- respecting the prefix- monotonicity of the architecture, where the output at position depends only on the first j tokens. This structure enforces the autoregressive property fundamental to decoder-only transformers. The final layer produces a vector Yn, which is mapped to a probability distribution over the vocabulary via projection function P. This figure serves to clarify the computational assumptions underlying our theoretical results.
Output Probabilities
Attention Layer (Za)
Next-token Probubilities
Activation Function (F)
Attention (a:
Attention Layer (Ia)
Weight Function (vr)
Positional Encoding (P)
Attention I Layer (I.)
Value Fumction (vuz)
Inpul embedding (e)
X1,X2
X
0000010_0010000
Figure 6: Schematic of decoder-only transformer.
B.2
Visualization of Continuity
dh
Input Sequence
Next-token Probabilities
00000000.000000g
0
1/100
0001000..0000000
00000100.0010000
82 2/100
8 8/100
0010001..0100000
0 1 2
Figure 7: Illustration of continuity in decoder-only transformers under small input perturbations.
Figure / visualizes the continuity property established in Corollary [ which shows that decoder-only transformers are stable under small input perturbations. In this example, we compare two sequences: a, consisting of 100 zeros, and B, which derived from a by flipping some zeros to ones. The relative Hamming distance d (o, (3) determines whether the perturbation is within a predefined threshold
8. When this threshold is satisfied, the transformer's next-token output distribution remains within a small distance of the original. The figure highlights both perturbed sequences that respect the ô-constraint and those that do not, illustrating how small input changes can result in correspondingly small or large changes in the output distribution.
B.3 Effect of Divergent Positions
We explore how the sensitivity of models varies with the position of input perturbations. Specifically, we measure the behavior of the model when fraction of the symbols in sequence of zeros are flipped to ones. To parametrically control where these flips occur along the input sequence, we sample discrete positions using the Beta-Binomial distribution, whose probability mass function is given by
11
B(k + u. k + v)
BITAMINN n, u, v) =
k
B(u,v)
23

---

where & E f0.1....... n) denotes the position index, is the sequence length (equal to 189 in our experiments), -). denotes the Beta function, and u, are the shape parameters. These parameters control the positional bias of the perturbations: toward the beginning (u < v), center (u = with u, 1 1), or end (u > u) of the sequence.
The plots in Figure show the next-token sensitivity NTS,, over 8 different positional biases of the perturbed tokens. We observe clear trend across models: perturbations near the end of the input have a significantly greater impact on the model's output compared to those near the beginning or middle. This reflects a dettiineddeeeeeent sensitivity, where later tokens carry more influence over the model's immediate prediction.
Model
gpt2
gemma-2b
Ilama-2-7b-hf
phi-1
gpt2-large
gemma-2-2b
Meta-Llama-33-8
phi-1 5
gpt2-xl
gemma-3-4b-it
1eata-Laamaa3-8--instte
phi-4
0.999,
0.999
(0.5,0.5)
(2,2)
(5,5)
100
NTSy
(5,0.5)
(5,2)
(2,5)
(0.5,5)
100
50
0
.01
1
2
3
4
.5
.01
1
2
3
4
55
01
11
2
3
.4
.5
.01
11
2
3
.
.5
Prop. of
differing symbols (y)
Figure 8: Sensitivity of decoder-only language models to input perturbations, visualized across different -Bea-BBinomia settings. The corresponding shape parameters provided in the title and the probability mass function is displayed in the upper left corner of each panel.
B.4 Boosting sensitivity
We investigate how modifications the attention aggregation function affect model's sensitivity small input perturbations in the setup described in Section 3.1 In particular, we compare the standard softmax attention with ssmax)) variant designed increase sensitivity. Originally introduced as log-length scaled attention by Chiang and Cholak [4] and later revisited as scalable softmax by Nakanishi [14), this formulation amplifies differences in logits based sequence length. As illustrated in Figure [ replacing softmax with ssmax significantly increases next-token variability under small imput changes.
B.5 Visualization of Code Syntax Verification
Figure illluttrraes the VERTFXXERIIIATIOON task, where the model is presented with sequence of Python function snippets and asked to determine whether the final snippet is syntactically correct. Each prompt consists of two small examples (F, and F2)) with correctness annotations, followed by a third large example (Fa), which is the target for prediction. We construct two versions of each prompt-one where Fa is correct and where contains subtle syntax error (e.g., incorrect of a keyword such as for). These two prompts differ by only few tokens, allowing us to evaluate whether the model is sensitive small but meaningful syntactic changes.
We extend our analysis for SYNTAX VERIFICATION task for multiple models versions (see Figure As expected, instruct-tune ttrrructttteeddeeee models perform significantly better this task than base models,
"SSMAX. (x) SOFTMAX((s log n) z). where z denotes logits of length n, and s E (0, 1] is scaling factor. defaulting to
24

---

With Softmax
With SSMax
Model
80
ggenai-commuittyggnz
apenal.ommunittygz--largg
NTS
google/gemma
google/gemma-2226
40
meta-laamo/Lima--2TTAA
mets-lammeMete-llmme--
microsoft/phi-1
0
microsoft/Phi. mini 4k instruct
0.0
0.1
0.2
0.0
0.1
0.2
0.3
0.4
0.5
Prop. differing symbols (y)
Figure 9: Next-token sensitivity of decoder-only language models to input perturbations. Each line shows the number of sample sequences (out of 100) that produce different next-token than zero, as function of the proportion of differing symbols. Left: Models with standard softmax in attention layers. Right: Models replaced with ssmax attention layers.
Prompts
Instruct: Read the Fol lowing pyshon code and ansver question.
pythan (b)
zwbuzn
Question:
Roes the Python code compile withoat ayntax If is detected, return 17 ochervise, return O,
B
-23
Ansvez:
collowing pyshon
ensver the question,
.. "python
if da (a. & then:
de :bo
for 10
Prompt
Language
a or
Model
Question:
Pychon code compile without ayntax wrrons? If errer is detected, retura It othervise, zeturn O.
Figure 10: Visualization the SYNTAAVEEIFICATIOO task. The model is prompted with Python code snippets and must predict whether the final function contains syntax error. MI refers the main instruction in the prompt: You are Python expert. Read the following instructions carefully and respond the questions.
consistent with their enhanced ability to follow instructions and answer questions. Surprisingly, even for relative simple prompts error rates remain high. Instruct models still display levels of errors above 15%, while base models above 80%.
B.6 Syntax Code Verification Reasoning Models
We extend analysis for SYNTAXVRRIFICATINN task for reasoning models o3-mini and o4-mini, trained with long instances of CoT (Figure [2). Unsurprisingly, we observe that these models are much better solving the task. Strikingly, observe that for such simple task prompts, these powerful models still display levels of errors greater or equal to 20%. These result suggest that CoT cannot always escape continuity, which continues affect the performance scales of practical relevance, even for advanced reasoning models.
'Here we consider smaller function dataset compared to standard dataset used for models in Section 3.2 and reasoning models Section B.6
25

---

Liama 2-7b-hf
Meta Llama 3-80
phi- 1
phi-1_5
phi-2
1.0
Pla
0.5
15%
14%
9%
8%
66%
mnii--rini-kkiissruutt
Phi-3 -5-mmin--instrucc
128k-insruct
ge gemma-2-26
gem ma-2b
1.0
Pla(8)
0.5
0.0
gpt2
gat2-large
gpt2-xl
1.0
Plals)
Sensitivity Sensitivity
0.5
0%
3%
4%
0.0
0.0
0.5
1.0
0.0 0.5 1.0
Ploja)
Figure 11: Sensitivity in the SYNTAX VERIFICTIIIA task. This figure illustrates the sensitivity of five models subtle syntactic changes in Python functions for pairs of input prompts. Each dot represents the model's probability assigned to a target token a under two prompts, a and [3. Blue dots indicate sensitive cases where the model's output changed in response to the syntactic errors, as expected. Orange dots mark non-sensitive cases where the model failed to adapt its prediction, despite the change in input. Percentages in each subplot indicate the proportion of samples where the model exhibited sensitivity. For this analysis, we consider a simpler function dataset (i.e functions with less than 100 tokens) in contrast to the main experiment, which involves longer functions (over 100 tokens) for gemma- 3-4b- it, gemma -- 1-b-ibbtttt it, phi 44 and Meta-Llamd Llama- 3-8B- Instruct and reasoning models.
79
03-mini
20
74
o4-mini
Sensitivity No Sensitivity
20
40
60
80
Number of Samples
Sensitivity in the o4-mini. Each bar represents frequency of samples where the model was either sensitivity or not to syntactic changes, under two prompts, and 3 which differ by small number of token that change the expected output. Blue bars represent the sensitive cases where the model's 's output changed in response to the syntactic errors, as expected. Orange bars represent non-sensitive cases where the model failed adapt its prediction, despite the change in input.
Figure 12:
task for reasoning models o3-mini and
26

---

B.7 Effect of Different Models for Periodic Generation
We extend our analysis of periodic pattern generation, evaluating how various decoder-only language models perform when tasked with completing structured, periodic sequences 57 = (0 prefix is defined
10 repetitions of base pattern 0#-11 plus token zero.
Figure 1 presents results for several CPE transformer models of varying sizes. We observe that each model exhibits critical period-4 threshold value of beyond which the model fails to reliably complete the pattern. For smaller periods (e.g., p S 10), models achieve perfect or near-perfect extrapolation, while performance degrades the period increases, eventually resulting in complete failure for periods beyond the model-specific threshold. Notably, all models show this limitation except some of them: for examples gemma- 2b and gemma-2-20
C Prompt formatting
We present the prompt format used for test sensitivity in models for SYNTAX VERIFIATRIIIAT task. Here we follow the same intruction structure for all model adapting this to each specific special tokens. For reasoning model, consider the same structure in order to ensure comparable results.
gemma-3 --iit
<bos><atart, turuuure
You Python expert. Carefully read the following python codes and ansver the questions, <end_of_ turn?
<start_of. @itart_of_turntt sff_tnnnoddel
OX. <W.dsend_of. cend__f_ttrr>>> turn>>>
<start_od _f__urr>user
Inatruct: Read the following python code and answer the question.
"''python
((python_ehot.c _ho____ottufui
Question: Boes Python compile without syntax vise, zeturn 0. <eud_of_tuu turn>
datected, othar
Instruct: Read the following python code and ansver the question.
Ansver: 1send_of_ turn?
tetart_of_turo/ue
ctyython (fpython_shot_fuun shot__fuctciin2]]
Question: Does Python code compile without syntax errors? no error detected, return other vise, return Send__of turn>
<start_of_turrevoodell
Ansver: 0send_of_turm ofrn=
<atart_of_ _f_tobuuerr
Instruct:
following python
question.
(yyyhhon {[python_tese cttrihoo_teat_fuuctiiooo
Question: Does the Python code compile without syntax errors? If no error is detected, return 1; other
0_<and_of_tura ourntur>>
Ottart.of_turo>eee Ansver:
27

---

Success
Certainty
google gemma 2b
Nect:iokan
google gemma-2-2b
google gemmma-3-4--t
google
gemma-3-12b-t
meta-llama
Llama-2-7b-ht
meta-llama
Meta-Llama-3-8B
meta-llama
Meta-Llama-3-B8
opemal-communlty gpt2
openal-community gpt2-large
openai-community gpt2-xl
microsoft phi-1
microsoft phi-1.5
microsoft phi-2
microsoft Phi-3-mini-4kinssruuct
microsoft Phi-3-min-118kkinstrudd
microsoft Phi-3.5 5.5 m-nniit-nntruct
microsoft phi-4
Period
Figure 13: Evaluation of periodic sequence generation using diverse models. Rows correspond to fix language model with r = 10 repetitions.
28

---

phi-4
clin_etart ( iil ee_eep>>
Python expert. Carefully read following python ansver questions. <lin
<lin_etart Buatstttt//ueerccleeee keppl
Instruct: Read the following python code and answer the question. "pyyhho
Segython_shat_functee
Question: Does the Python code compile without syntax errors? If no erzor is datected, return 1; other vise, return o.<lin_end|>>
Ansver: 1<lin_end|>>
Inatruct: Read the rollosing python code and answer the question. "pyyhhon
(lgython_ehot_ffuctae
lic
Question: Does the Python code compile without syntax errora? If error datected, return other vise, return o.<lin_end|>>
[nn_attat//asstataatk/
Anaver: <<]innend]>>>>
<ling stin_start/aast <user</ in_ppl>>
Instruct: Read the following pythen code and ansker the question.
sppyttonn )
Question:
Python compile without syntax
detected, other
vise, return 0. 0.<lin_end] <lin_ biin__tart/>aaeeee < smmpp Ansuer:
Meta Hlet--Llma-33 Instruct
<lbegin Bectiit_ff_tetttteee text / sttetrr_deee paaauder_dlleyyereee lend_ header_id|>>
You are Python expert. Read the following instructions carefully and respond to the centtiins.<llo__ttt bir Inserr/end_hesdrrr
Inatruct: Read the follosing python code and answer the question. ([pythen_hhot_fuae fuuc_inccc
Question: Does the Pythen code compile without eyutax errors? If no error is dotected, return 1; other vise, (.a]aot httalattttttddrrr_._. bea__eeddddd__ hedddeeeddddasssiieeeeite adl>ascistant< ledd_heador_idd
Anaver: 1c|start_beeder. iddederrddDuuerdcc Puser<< baaeerr/end_headeee hdader__dd>>>
Instruct: Read the follosing python code and аnewеr the question. ((pythoa_ehot_funn funt_ffuccioa2))
Question: Does the Python code compile without syntax errors? If no error is dotected, return 1; other batadder_d/>assittttt heddheeerrddd
vise, raturn o.<|aor_id]><(atttt
Anaver: icleott.ddl><(sstttt.e. beaabrrtt_eeerr____ Puser< hender/eedd__eeeeeeeeee hedd_heeder_id1
Instruct:
Read the following python code and anewer the question. prrrbea_test_ffuctiioo
Question: Does the Python code compile without syntax errors? If no orror is dotected, return other viae, raturn b_<]eor_id|><{aa header, halp:/ttlassstannccceaa headd__earr__d13
Ansver:
29


Reviews:
[{"review_id": "OH5LMEwMNN", "reviewer": "Reviewer_yoGw", "summary": "This papers provides two interesting fundamental limitations in the learning capability of transformers, namely continuity and isolation. Continuity shows that prompts the are close enough always produces probability output that are also close. On the other hand, isolation shows that for any two infinitely long sequences that are learnable by a transformer, if the two sequences differ at infinitely many places, then they must be far enough in Hamming distance. The paper also shows experimental analysis showing the importance of the limits in learning in several synthetic as well as some practical scenarios.", "questions": "Please also see the weaknesses.\nAdditional questions:\nLine 223: \"Middle positions result in lower sensitivity, and early tokens yield almost no sensitivity at all\"\nQ: does the theory explain this observation?\n\nLine 196: \"same last token\"\nWhy is this condition in theorem 1 important, please explain intuitively.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper theoretically illustrates two fundamental limitations in the learning capability of transformers\n\n- The paper also shows experiments illustrating the continuity and isolation phenomenon on synthetic tasks such as number sequence generation as well as practical applications such as syntax verification tasks.\n\n- The paper is well written in terms of the clarity of the results and simple experiments supporting and illustrating the claims.\n\nWeaknesses: \n- The theorems are all claims for infinite sequences. Hence, it is difficult to judge how applicable they are practically beyond the illustrated synthetic examples. Is it possible to show more convincing practical usecases such as the code-syntax related.\n\n- For Fig. 3 the pattern does not seem to follow same as in Fig. 2 for continuity. Please explain if I am misunderstanding the figures.\n\n- As also mentioned in the limitations, the analysis lacks consideration of chain-of-thought reasoning generated by recent reasoning models. Is it possible that these reasoning traces allow different output after reasoning, hence, not be limited by the results in the theorem. Can we check it empirically on some of the synthetic datasets using some reasoning models?", "was_revised": true, "final_justification": "I thank the author for their detailed response with clarifications and the additional experiment.\n\nIt clarifies the concerns/questions I had regarding infinite sequence: I went through the proof again and I see that it is indeed for finite sequence. I was confused with the infinite sequence examples in the paper. I would suggest having some finite sequence example as well in the final version of the work to avoid any confusion for readers.\n\nThanks for clarification on the figures, I would suggest making the captions more detailed so that it is easy for the readers to understand the figure.\n\nThanks for the experiments on the reasoning models. It is indeed interesting that reasoning does not help much with the continuity issue.\nI have increased the score to reflect the above.", "rebuttal": "We thank the reviewer for the positive appraisal of our work and greatly appreciate the time invested in reviewing it. Below, we reply to the three weaknesses raised by the reviewer, followed by replies to the questions raised.\n\n* _(Weakness 1) The theorems are all claims for infinite sequences. Hence, it is difficult to judge how applicable they are practically beyond the illustrated synthetic examples. Is it possible to show more convincing practical use cases such as the code-syntax related._\n\nWe note that Theorem 1 (our main result) is in fact formulated for finite sequences. The conclusions for infinite sequences are presented only to illustrate clear limitations on a task requiring inductive reasoning, namely, the ability to derive general rules and principles from the presented information (an ability considered as a key aspect of intelligence behavior). In addition to the code syntax verification task, and to address the reviewers comment, we have tested the corollary of Theorem 1 on a new natural language task. \n\nWe evaluate LLMs on a natural language inference (NLI) task analogous to the Code Syntax Verification task. The new dataset consists of 56 examples derived from the \"babi-nli\" dataset. Each instance includes a premise, a hypothesis, and a label (0 or 1). To meet theoretical requirements, we lengthen the premise using neutral text from Wikipedia, creating a \"Long-Premise\" that preserves the original label and constitutes the alpha-sequence. To create the corresponding \"beta-sequence\" we modified a single key word at the beginning making sure that it entails a change to the original label. \n\nFor example,\nPremise Alpha (Label=True): Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the apple there....\n\nPremise Beta (Label=False):  Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the pear there....\n\nHypothesis: Yann picked the apple because she was hungry.\n\nConsidering that Meta-Llama-3-8B-Instruct provided the best results in the Code Syntax Verification task, we tested this model on the new NLI task in two scenarios with different input lengths. Namely ~1000 tokens and ~5000 tokens. The results were as follows:\n\nSensitivity:   25% (about 1000 tokens),   14% (about 5000 tokens)\n\nAccuracy:        62% (about 1000 tokens),   57% (about 5000 tokens)\n\nAs we can see from the results, even in this simple natural language inference task, the sensitivity remains fairly low. We acknowledge that this is an important practical application of Theorem 1. If the reviewer agrees we can add these findings in the revised version. \n \n* _(Weakness 2) For Fig. 3 the pattern does not seem to follow same as in Fig. 2 for continuity. Please explain if I am misunderstanding the figures._\n\nFigures 2 and 3 are plots of different things, it is therefore normal that the patterns are different. In Fig. 2 the x-axis corresponds to the percentage of tokens that were randomly changed in order to produce the perturbed sequence, while in Figure 3 this perturbation size is fixed. The purpose of Fig. 2 is to show the number of times (out of 100) a given perturbation size produced a change in the output. In contrast, in Fig. 3 the plot is meant to compare the output probability of the most likely token given the original sequence as input (alpha)  against the output probability of the same token, but given instead the perturbed sequence (beta). \n\n* _(Weakness 3) As also mentioned in the limitations, the analysis lacks consideration of chain-of-thought reasoning generated by recent reasoning models. Is it possible that these reasoning traces allow different output after reasoning, hence, not be limited by the results in the theorem. Can we check it empirically on some of the synthetic datasets using some reasoning models?_\n\nThis is an interesting point, which we in fact discuss in Section B.6 of the Appendix. In particular, we tested Open AI’s o4-mini and o3-mini models on the syntax verification task. Strikingly, we observe that even on our very simple task, these models still display a level of error greater than 20%. This suggests that while CoT may slow down the effect of continuity, it may not completely eliminate it. We acknowledge that these results are omitted from the main body of the paper. We will make sure to correct this in the revised version. \n\n*  _(Question 1) Line 223: \"Middle positions result in lower sensitivity, and early tokens yield almost no sensitivity at all\" Q: does the theory explain this observation?_\n\nNo, our theoretical results do not account for differences in sensitivity associated with the positions of the perturbations (beginning, middle or end). \n\n* _(Question 2) Line 196: \"same last token\" Why is this condition in theorem 1 important, please explain intuitively._\n\nIntuitively, because one can build a transformer that always outputs the last token (ignoring previous ones). \nFor that transformer, changing the last token changes the output regardless of the input length.\nHence, the condition about the last token is strictly necessary for the theorem 1."}, {"review_id": "fEVBE8wFkN", "reviewer": "Reviewer_taZZ", "summary": "The core of this paper is to deepen the understanding of the mechanism of Transformer by conceptualizing and analyzing two phenomenon: \n\n1)\tIsolation expresses that any learnable sequence must be isolated from another learnable sequence, and hence some sequences cannot be learned by a single Transformer at the same time. \n\n2)\tContinuity entails that an attractor basin forms around a learned sequence, such that any sequence falling in that basin will collapse towards the learned sequence.\n\nThe authors provide not only the mathematic proof, but also the careful designed experiment to verify the claim.", "questions": "Can similar findings be applied to RNNs? Additionally, could you suggest possible architectural designs that might address the limitations identified in this paper?", "limitations": "See weakness", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1.  Overall, this paper is well written.\n2.  The paper offers a valuable perspective on analyzing the Transformer architecture.\n\nWeakness:\n1.  The paper appears to be poorly positioned. While the title suggests a focus on large language models (LLMs), the main content primarily discusses Transformers. Although LLMs are typically built on Transformer architectures, the two are not synonymous, and this distinction is not clearly addressed.\n2. Several prior works [1,2,3] have explored the fundamental limitations of the general Transformer architecture, but this paper does not sufficiently engage with or contextualize those contributions.\n3.  The findings of this paper are limited to pattern discovery in purely numerical sequences. It remains unclear whether these results can be generalized to natural language. In most cases, natural language understanding does not rely on the kinds of patterns examined in the paper. Moreover, natural language carries significantly richer semantic content than the simplified tasks considered here.\n\n[1] Faith and Fate: Limits of Transformers on Compositionality\n\n[2] Limits of Transformer Language Models on Learning to Compose Algorithms\n\n[3] On Limitations of the Transformer Architecture", "was_revised": true, "final_justification": "1) The response to Question 1 was particularly insightful. I had previously misunderstood the limitations discussed as being common to all neural networks. However, the clarification that these limitations are specific to the Transformer architecture was very helpful.\n\n2) In addition, the new experimental results are quite compelling. The observed relationship between the number of tokens and sensitivity is especially interesting.\n\nThese two points have led me to reassess the contribution of this paper. I am now convinced that it offers valuable insights for the future development of neural network architectures.", "rebuttal": "We thank the reviewer for the careful read of our manuscript and the valuable comments raised. The reviewer is concerned about a better positioning of our work with respect to previous work, but also the scope of our findings. Below, we provide a point-by-point reply to the weaknesses and questions raised by the reviewer.\n\n\n* _(Weakness 1) The paper appears to be poorly positioned. While the title suggests a focus on large language models (LLMs), the main content primarily discusses Transformers. Although LLMs are typically built on Transformer architectures, the two are not synonymous, and this distinction is not clearly addressed._\n\n\nWe thank the reviewer for this remark. Our camera-ready version will position the scope of our paper taking into account this comment, and we will make sure to isolate our claims to transformer-based LLMs from the introduction onwards. \n\n* _(Weakness 2) Several prior works [1,2,3] have explored the fundamental limitations of the general Transformer architecture, but this paper does not sufficiently engage with or contextualize those contributions._\n\nWe thank the reviewer for pointing out these references. To improve the positioning of the paper, we will add the discussion of these references in the related work section.\n\n\n* _(Weakness 3) The findings of this paper are limited to pattern discovery in purely numerical sequences. It remains unclear whether these results can be generalized to natural language. In most cases, natural language understanding does not rely on the kinds of patterns examined in the paper. Moreover, natural language carries significantly richer semantic content than the simplified tasks considered here._\n\nWe note that Theorem 1 (our main result) is agnostic to the nature of the input and thus applies equally well to natural language or any other kind of input. The consequences we present for pattern recognition over numerical sequences are only meant as a concrete illustration of the limitations implied by Theorem 1 on inductive reasoning, understood as the ability to derive general rules and principles from the presented information (and usually considered as a key aspect for human intelligence). We also note that besides numerical sequences,  section 3.2 of our paper presents experiments on a syntax verification task that requires both advanced semantic and complex syntactic structure understanding. Nonetheless, to address the concern raised by the reviewer, we have performed an additional experiment on a novel natural language task, analogous to the Code Syntax Verification task.\n\nThe new dataset consists of 56 examples derived from the \"babi-nli\" dataset. Each instance includes a premise, a hypothesis, and a label (0 or 1). To meet theoretical requirements, we lengthen the premise using neutral text from Wikipedia, creating a \"Long-Premise\" that preserves the original label and constitutes the alpha-sequence. To create the corresponding \"beta-sequence\" we modified a single key word at the beginning making sure that it entails a change to the original label. \n\nFor example,\nPremise Alpha (Label=True): Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the apple there....\n\nPremise Beta (Label=False):  Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the pear there....\n\nHypothesis: Yann picked the apple because she was hungry.\n\nConsidering that Meta-Llama-3-8B-Instruct provided the best results in the Code Syntax Verification task, we tested this model on the new NLI task in two scenarios with different input lengths. Namely ~1000 tokens and ~5000 tokens. The results were as follows:\n\nSensitivity:   25% (about 1000 tokens),   14% (about 5000 tokens)\n\nAccuracy:    62%  (about 1000 tokens),   57% (about 5000 tokens)\n\nAs we can see from the results, even in this simple natural language inference task, the sensitivity remains fairly low. We acknowledge that this is an important practical application of Theorem 1. Sensitivity to small changes in a long text is critical for some real-life applications like analyzing legal documents.\n\n\n* _(Question 1) Can similar findings be applied to RNNs? Additionally, could you suggest possible architectural designs that might address the limitations identified in this paper?_\n\nThis is an interesting question. The Continuity phenomenon does not apply to RNNs. Indeed, Merrill [1] has shown that simple RNNs can recognize any regular language. In particular, there exists a simple RNN which on any long sequence input  like “0000…0” outputs 0 but on a sequence like “1000…0” outputs 1. At the same time, by Theorem 1, Transformers with compact positional encoding (such as RoPE) cannot do that. \n\n Theorem 1 can therefore be seen as a separation result between the capabilities of these two architectures. In turn, this suggests that suitably incorporating state space models modules into a transformer architecture (as in Jamba) may help to overcome the limitations imposed by continuity and isolation. Another possibility to overcome these limitations is to allow non-compact components. This is in fact illustrated in Appendix B.4 of our paper, where we tested the effect of replacing softmax in the attention layers by the so-called scalable softmax, which is a version of softmax that explicitly incorporates a term that grows logarithmically with the size of the input, therefore introducing non-compactness. As can be seen from Figure 8, our results unequivocally show that replacing standard softmax by scalable softmax (while leaving everything else unchanged) leads to a significant improvement in sensitivity. Finally, another possibility to overcome continuity limitations is to allow non-compact positional encodings.\n\n[1] William Merrill. 2019. Sequential neural networks as automata."}, {"review_id": "N7hpCT29Bo", "reviewer": "Reviewer_DY31", "summary": "The this paper really on two simple (yet non-trivial) observations:\n- Continuity: a Transformer outputs can not change too much when its prompt does not change much\n- Isolation: as a consequence, a Transformer can not learn simultaneously infinite sequences that are equal on a dense set, sooner or later it will have to make next token prediction error on one of the two sequences.", "questions": "It has been shown that hybrid models between Mamba and Transformers work better than Transformers for long context (https://github.com/NVIDIA/RULER). Do you have any intuition of what could explain these observations? Would your work allow you to shed some lights on that matter? (Maybe Mamba models suffers a representation collapse at a lower speed)\n\nDoes your study make you bullish on approaches such as https://arxiv.org/pdf/2501.19399?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n- In essence, the paper shows that Transformers sees infinite sequences from the Besicovitch space (which is much smaller than the Weyl or Cantor spaces).\n- The results do not see too toyish, but of practical relevance at scales in which Transformers operate in practice.\n- It could explain the difficulty to do long-context with transformers, and justify the use of CoT, memory layers, tools...\n- The paper is really well written.\n\n**Weaknesses**:\n- It would be nice to have a finer characterization of the modulus of continuity in Theorem 1. In particular, I assume that the MLP layers F could introduce big variations that may make this work irrelevant in practice (e.g. I won't be surprised if someone show that one can modify a single token in a prompt to lead to completely different outputs for any decently long sequences, and that the conflict with this paper would be due to the modulus of continuity of the MLP layers).\n- It may be the case that the results are brittle, and do not really explain as many practical observations on long context as one may want to believe. In particular, I am not sure that the theoretical tools used in this paper could explain the observations made on the RULER benchmark (see question below).", "was_revised": true, "final_justification": "I liked the paper overall. However, the authors’ answers to my questions seem relatively superficial, as I suspect some form of representational collapse in the state-space model, and the authors did not provide strong evidence that their theory explains the success of Jamba in practice. Nevertheless, in my view, the paper is an \"accept.\"", "rebuttal": "We thank the reviewer for the time invested in carefully reviewing our work and the valuable comments raised during this process. Below, we provide answers to the questions posed by the reviewer.\n\n* _(Question 1) It has been shown that hybrid models between Mamba and Transformers work better than Transformers for long context (https://github.com/NVIDIA/RULER). Do you have any intuition of what could explain these observations? Would your work allow you to shed some lights on that matter? (Maybe Mamba models suffers a representation collapse at a lower speed)._\n\nAs Merrill [1] has shown,  simple state space models as RNNs can recognize any regular language. In particular, there exists a simple RNN which on any long sequence input  like “0000…0” outputs 0 but on a sequence like “1000…0” outputs 1. At the same time, by Theorem 1, Transformers with compact positional encoding (such as RoPE) cannot do that.  Theorem 1 can therefore be seen as a separation result between the capabilities of these two architectures. In turn, this suggests an explanation why incorporating SSM modules into a transformer architecture (as in Jamba) may in principle result in models overcoming representational collapse.  \n\n* _(Question 2) Does your study make you bullish on approaches such as https://arxiv.org/pdf/2501.19399?_\n\nThis is also an interesting point. We have in fact analysed it in Section B.4 of the Appendix where we tested the effect of replacing softmax in the attention layers by the so-called scalable softmax, which is a way to incorporate non-compact components. The resulting model therefore escapes from the framework of our theory, and is thus not subordinated to the constraints imposed by our results. And indeed, as can be seen from Figure 8, our experiment shows a significant improvement in sensitivity. We acknowledge that this observation is absent from the main body of the paper. We will correct this in the revised version."}, {"review_id": "hv4c4Fxwl1", "reviewer": "Reviewer_RSLx", "summary": "This paper derives and demonstrates two phenomena that a decoder-only transformer with compact positional encoding exhibits. The first is continuity: given two similar tokenized sequences, the next token prediction is similar for one sequence as for the other sequence, if the sequences have a small enough Hamming distance. Their theoretical claim was examined by looking at LM’s sensitivity to small changes in the prompt, one on zero fundamental sequence and the other on a syntax verification task, in which the model needs to say whether the syntax is correct or not. They observed that most models do not change their predictions when there is a small change in syntax, supporting the continuity argument. The second is isolation, which is about no such transformer can learn all sequences of infinite length, for example, all periodic sequences, because they have a relative hamming distance of 0.  In practice, they demonstrate the effect of isolation on sequences with a small number of differing samples, supporting that decoder-only transformers with compact positional encoding learn a limited set of periodic sequences.", "questions": "Line 89, what is CPE transformer? \n\nWhat is the accuracy of the model in the syntax prediction error detection task? \n\nIs the model sensitivity dependent on sequence length?\n\nI guess figure 2’s emphasis is on the left figure, do we know in closer detail, the message is if there is a small number/proportion of differing signals, then the prediction results are insensitive, and the right plot suggests that the prediction results are sensitive when there is a substantial differing portion of signals, but you cannot see very well from the left side of figure 2. (How come there are still some models that are insensitive to a big portion of differing signals?) \n\nHow does the sensitivity result depend on the sequence length? I know it is 190 in the experiment, but what happens for sequence length in the common token range?\n\nWhat is the accuracy of the model in the syntax prediction error detection task?", "limitations": "Yes, limitations are sufficiently discussed in section 5 of the paper.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths:__\n\n I appreciated the mathematical rigor of the paper, and the theoretical claims are well-defined. The idea is original and connects analysis with understanding transformer behavior. There is a nice connection between the theoretical derivations and practical experiments. \n\n__Weaknesses:__\n\n My issue with this theoretical idea is that it is too much of a corner case. The authors claim that the lack of these abilities “*severely* constrains their (even mild) intelligent behavior”, which is a bit unsubstantiated. It is also bizarre to assume intelligence depends on the learnability of infinite sequences. I think the evaluation examinations are too tangential to their actual use cases.  Pragmatically, few give infinite sequences to transformers, but just missing this aspect of behaving properly with respect to infinite or very long sequences does not disqualify a transformer from being intelligent. The paper lacks an argument or a demonstration on why this can be a concerning characteristic of the transformer. \n\nThe title is not appropriate to its content, as it is unclear what these doubts and dilemmas refer to, the wording deviates from the main findings of the experiments.\n\nSomething is missing between the introduction and the contributions. I suggest putting related work before the contribution. \n\nLine 114, 115 on Page 3 is broken. \n\n321-322 is missing a comma\n\nsection 1.3’ s title does not match its content", "was_revised": true, "final_justification": "This paper gives clear and original mathematical proofs to show two tendencies and limitations for CPE transformers. Although experiments can be made more related to real-world applicable cases, the idea is original, well presented, and has important implications.", "rebuttal": "We thank the reviewer for carefully reviewing our work and the comments raised. Below, we provide answers to the weaknesses and questions posed by the reviewer.\n\nWeaknesses rebuttals:\n\n* _(Weakness 1)  My issue with this theoretical idea is that it is too much of a corner case. The authors claim that the lack of these abilities “severely constrains their (even mild) intelligent behavior”, which is a bit unsubstantiated. It is also bizarre to assume intelligence depends on the learnability of infinite sequences. I think the evaluation examinations are too tangential to their actual use cases. Pragmatically, few give infinite sequences to transformers, but just missing this aspect of behaving properly with respect to infinite or very long sequences does not disqualify a transformer from being intelligent. The paper lacks an argument or a demonstration on why this can be a concerning characteristic of the transformer._\n\n\nWe note that Theorem 1 (our main result) is actually formulated for finite sequences. The conclusions we derive from it for infinite sequences are meant to illustrate a concrete limitation to perform inductive reasoning, understood as the ability to derive general rules and principles from the presented information (an ability usually considered as a key aspect of intelligent behavior). The limitation for infinite sequences means that the transformer will never be able to understand the rule that generates the sequence, regardless of how long the prompt is. To substantiate even more our claims, we have performed an additional experiment on a novel natural language task, analogous to the Code Syntax Verification from our paper.\n\nThe new dataset consists of 56 examples derived from the \"babi-nli\" dataset. Each instance includes a premise, a hypothesis, and a label (0 or 1). To meet theoretical requirements, we lengthen the premise using neutral text from Wikipedia, creating a \"Long-Premise\" that preserves the original label and constitutes the alpha-sequence. To create the corresponding \"beta-sequence\" we modified a single key word at the beginning making sure that it entails a change to the original label. \n\nFor example,\nPremise Alpha (Label=True): Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the apple there....\n\nPremise Beta (Label=False):  Yann is hungry. Jason is bored. Antoine is hungry. Yann went back to the kitchen. Yann picked up the pear there....\n\nHypothesis: Yann picked the apple because she was hungry.\n\nConsidering that Meta-Llama-3-8B-Instruct provided the best results in the Code Syntax Verification task, we tested this model on the new NLI task in two scenarios with different input lengths. Namely ~1000 tokens and ~5000 tokens. The results were as follows:\n\nSensitivity:   25% (about 1000 tokens),   14% (about 5000 tokens)\nAccuracy:    62%  (about 1000 tokens),   57% (about 5000 tokens)\n\nAs we can see from the results, even in this simple natural language inference task, the sensitivity remains fairly low. We acknowledge that this is an important practical application of Theorem 1. Sensitivity to small changes in a long text is critical for some real-life applications like analyzing legal documents.\n\n* _(Weakness 2) The title is not appropriate to its content, as it is unclear what these doubts and dilemmas refer to, the wording deviates from the main findings of the experiments._\n\nThe term “doubts“ refers to the lack of certainty for the next token prediction, while “dilemmas” means that if two prompts are too similar then the transformer can make the right prediction with certainty for at most one of them (in a sense, “it has to choose”). As explained in the paper and tested in the experiments, these two features come from the continuity phenomenon that we study. This is discussed in Section 5 (Conclusion - Doubts and Dilemmas). The referee is correct in that we should explain this earlier in the paper, and we will do so in the CR-version. \n\n\n* _(Question 1) “Line 89, what is CPE transformer?”_\n\nCPE is first introduced in line 43 and stands for compact positional encoding. A formal definition of CPE is later given in line 174. The CR-version will formally define CPE when it first appears in the text. \n\n* _(Question 2) What is the accuracy of the model in the syntax prediction error detection task?_\n\nThe accuracies for the different models are 52% (gemma-3-4b-it), 54% (gemma-3-12b-it), 49% (phi-4) and 60% (Meta-Llama-3-8B-Instruct). We will add this information to the CR-version.\n\n* _(Question 3) Is the model sensitivity dependent on sequence length?_\n\nTheorem 1 imposes a universal relationship between epsilon and delta that does not depend on the length of the sequence. However, if for instance we are perturbing a single token (as in the syntax experiment), then the Normalized Hamming distance between the two prompts is 1/n where n is their length. Thus, for larger prompts the resulting perturbation is smaller, and therefore more likely to show non-sensitivity.  We have in fact tested this. In Appendix B.5, Figure 10, we present the results of the Code Syntax Verification task on a series of other models using prompts with around 300 tokens (as opposed to the results in the main body of the paper which stemmed from inputs of more than 1000 tokens) and observe improved sensitivity.\n\n* _(Question 4) I guess figure 2’s emphasis is on the left figure, do we know in closer detail, the message is if there is a small number/proportion of differing signals, then the prediction results are insensitive, and the right plot suggests that the prediction results are sensitive when there is a substantial differing portion of signals, but you cannot see very well from the left side of figure 2. (How come there are still some models that are insensitive to a big portion of differing signals?)_\n\nObserving insensitivity even for large perturbations is permitted by Theorem 1, although not guaranteed in all cases. Our results guarantee insensitivity for sufficiently small perturbations.\n\n* _(Question 5) “How does the sensitivity result depend on the sequence length? I know it is 190 in the experiment, but what happens for sequence length in the common token range?”_\n\nOur theoretical results predict that non-sensitivity is more likely to appear with longer sequences. Indeed, as illustrated in Appendix B.5 (Figure 10), on average we observe an improvement in sensitivity when the sequence length is shorter. Moreover, the novel natural language task described in weakness 1 also reveals this phenomenon."}]

Author rebuttal:

Meta-review: This article considers the ability of transformers that use compact positional encodings to distinguish strings of tokens from each other with ‘certainty’ defined as a guaranteed margin for correctly predicting the continuations of distinct strings.  A mathematical theory of novel termology is introduced, and two theorems and their informal corollaries are presented, with proofs in a supplement.  The key claim of the article, stated informally/approximately, is that as strings get longer distinctions can become harder to detect with certainty.   Conceptual examples center on easy to understand sequences like sequences of all 0’s or simple periodic sequences, while several practical examples are also considered, showing that all transformers tested have limits in their ability to produce valid responses for some long sequences while correctly producing distinct responses for other valid sequences.  

After reviews and rebuttals, the paper received ratings of 5,5,5, and 4 – that is 3 of four reviewers recommended acceptance while one rated the paper a borderline accept.  The strength of the paper, as the reviewers saw it, was that it clearly delineated in-principle limits on compact transformers potential, while also showing that these limits do show up in practice.   Several scores were initially lower but through the rebuttal process several reviewers came to understand the paper better, and a new practical example using natural language was introduced, addressing most of the weaknesses identified.

I am pleased to join the reviewers in recommending acceptance – it is clear that many members of the NeurIPS community will consider themselves to have been informed or to have had their understanding of phenomena they are dimly aware of clarified by the paper and its findings.   I do hope that the authors will revise the paper to ensure that some of the initial misunderstandings expressed by individual reviewers are addressed, and to include the new natural language task results, which one of the reviewers found illuminating.

I would, however, like to urge the authors to consider tempering some of the stronger statements in the paper and slightly adjusting their framing of the importance of their findings as I discuss below.

The paper argues that we should expect an intelligent system to be capable of processing distinct sequences of arbitrary length.   Certain computational systems may have this capability (under the assumption of infinite memory) but to consider a system intelligent only if it has this capability is not something that I think the field of computational intelligence should accept without discussion.  On this view, humans (without recourse to external supports such as the ability to read and write and or to rely on computer programs) would not be considered intelligent.  Chomsky made the move of accepting capacity limitations as a fact of human nature as part of his defense of a computational formulation of one important aspect of human intelligence.

A related point is that the models under consideration can be quite successful up to fairly long sequence lengths and thus they can be of considerable use in practice, and I think it would be worthwhile for the presentation to more explicitly acknowledge this point. Indeed in my view the paper’s value lies primarily in providing a starting place for considering the limitations of particular types of computational systems. While related points are currently made in the discussion and limitations section, it would strengthen the paper if this point could be more fully acknowledged.  Additionally and if possible, some of the other points that came up in the exchange with reviewers about the pros and cons of alternative architectures including state space machines and RNNs could at least be hinted at within the paper somewhere.
Decision: Accept (poster)