Trapped by simplicity: When Transformers fail to learn from noisy features
Authors: Evan Peters
Matheus Hrabowec Zambianco
Ando Deng
Devin Blankespoor
Achim Kempf
Venue: ICLR 2026 Poster (2026)
Keywords: boolean analysis
simplicity bias
transformer
feature noise
Primary area: foundation or frontier models, including LLMs

Abstract: Noise is ubiquitous in data used to train large language models, but it is not well understood whether these models are able to correctly generalize to inputs generated without noise. Here, we study noise-robust learning: are transformers trained on data with noisy features able to find a target function that correctly predicts labels for noiseless features? We show that transformers succeed at noise-robust learning for a selection of $k$-sparse parity and majority functions, compared to LSTMs which fail at this task for even modest feature noise. However, we find that transformers typically fail at noise-robust learning of random $k$-juntas, especially when the boolean sensitivity of the optimal solution is smaller than that of the target function. We argue that this failure is due to a combination of two factors: transformers' bias toward simpler functions, combined with an observation that the empirically optimal function for noise-robust learning has lower sensitivity than the target function. We test this hypothesis by exploiting transformers' simplicity bias to trap them in an incorrect solution, but show that transformers can escape this trap by training with an additional loss term penalizing high-sensitivity solutions. Overall, we find that transformers are particularly ineffective for learning boolean functions in the presence of feature noise.

TRAPPED BY SIMPLICITY: WHEN TRANSFORMERS FAIL TO LEARN FROM NOISY FEATURES
Evan Peters!.2-g Ando Deng' & Matheus H. Zambianco 1.2
Devin Blankespoor' & Achim Kempfl.2 'University of Waterloo PPerimeter Institute for Theoretical Physics
ABSTRACT
Noise is ubiquitous in data used to train large language models, but it is not well understood whether these models are able to correctly generalize to inputs gener- ated without noise. Here, we study noise-robust learning: are transformers trained on data with noisy features able to find a target function that correctly predicts labels for noiseless features? We show that transformers succeed at noise-robust learning for selection of k-sparse parity and majority functions, compared to LSTMs which fail at this task for even modest feature noise. However, we find that transformers typically fail at noise-robust learning of random k-juntas, espe- cially when the boolean sensitivity of the optimal solution smaller than that of the target function. We argue that this failure is due to a combination of two fac- tors: transformers' bias toward simpler functions, combined with an observation that the optimal function for noisc-robust learning typically has lower sensitivity than the target function for random boolean functions. We test this hypothesis by exploiting transformers' simplicity bias to trap them in incorrect solution, but show that transformers can escape this trap by training with an additional loss term penalizing high-sensitivity solutions. Overall, find that transformers are particularly ineffective for learning boolean functions in the presence of feature noise.
INTRODUCTION
Large language models (LLMs) are powerful tools for natural language processing, code generation, scientific research, and reasoning across a wide range of domains. The training data for these models contain noise in the form of stochasticity and different modalities of errors, and yet LLMs trained on these noisy data are often applied in settings where next-token prediction highly sensitive to noise in the preceding tokens, such as solving arithmetic problems. This raises the question, are transformers actually capable of noise-robus! learning, i.e. can transformers trained on data with feature noise learn a target function that makes accurate predictions for noiseless data?
Boolean functions of binary input data provide a simplified setting for studying noise-robust learn- ing. Recent results demonstrate that transformers prefer to learn simple boolean functions for next- bit prediction tasks on binary input data (Bhattamishra et al.) 2023b Hahn Rofin 2024). An immediate consequence is that the functions learned by these models robust to input perturba- tions (i.e. noise) at evaluation time (Vasudeva et al.) 2025). Yet, less is known about the setting where training data themselves contain feature noise (for example, bitflips randomly applied the input bitstring). From another angle, Deletang et al. (2024) analyzed natural language modeling in terms of compression in the presence of an inherent amount of randomness found in natural language (Shannon 1951). However, such analyses neglect the effect of noise on information transmission (Shannon 1948). It is well-known that feature noise induces simpler solutions in ordinary least squares via attenuation Fuller (2009), but there is little empirical evidence describing how feature noise affects the learning behavior of transformers in discrete domains, like learning boolean func- tions. Our goal is study whether these models are capable noise-robust learning learning an underlying boolean function from training data with feature noise.
"66ptters @uwaterloo.ca

---

Our main finding is that transformers fail at noise-robust learning for a large class of boolean fune- tions. We attribute this outcome to a combination of two factors: (i) the simplicity bias of transform- ers makes them prefer simple functions that achieve low loss on the training data and (ii) empirical and theoretical arguments that the optimal solution for noise-robust learning is simpler than the tar- get function used to generate the data. Meanwhile, we find that long short-term memory networks (LSTMs), which exhibit less bias towards simple functions, also fail at noise-robust learning, albeit for different reasons. Thus, while neural network with an inductive bias towards complex functions might be capable of noise-robust learning in principle, we show that both transformers (with their simplicity bias) and LSTMs (without a simplicity bias) are poor candidates for this task.
These results imply that transformers are ill-suited to classification and generative modeling in bi- nary domains where feature noise is prevalent, such as learning to decode classical (Kim et al., 2018 Nachmani & Wolf, 2019; Choukroun & Wolf 2022 Cammerer et al. (2022) and quantum error cor- recting codes (Torlai & Melko 2017; Lange et al., 2025| |ausch et al., 2024 Peters] 2025). More broadly, our findings suggest that the simplicity bias of LLMs hurts their ability to learn complex relationships via natural language processing with sufficient feature noise. For instance, models trained on noisy data (e.g. high stochasticity, incorrect grammar semantics) will likely struggle to perform next-bit prediction for tasks such as arithmetic and discrete mathematics, where each next token depends preceding noiseless input text according some sensitive function. This complements observations that feature noise at evaluation time can reduce transformers' ability to do arithmetic and other discrete mathematics (Shi et al. 2023 Abedin al., 2025). Our work high- lights potential need to mitigate the simplicity biases of large language models, if we hope for these models to learn algorithmic tasks from noisy training data.
Our contributions we show mixed results for transformers' performance at noise-robust learning. (i We find that transformers succeed at this task for sparse parity and majority functions high rates of feature noise, while LSTMs generally fail at this task even for low levels of feature noise. (ii) We show that transformers fail at this task for random k-juntas while simultaneously reaching near-optimal accuracy on noisy validation data. (iii) We propose an explanation for this behavior: We observe that the sensitivity of the optimal solution for noise-robust learning is rarely greater than the sensitivity of the target function, and therefore transformers' simplicity bias will result in a solution that is suboptimal for noiseless evaluation. (iv) We explore this hypothesis by showing that transformers can be trapped by an incorrect solution that achieves similar accuracy as the target function on noisy validation data, and that transformers with a penalty for high-sensitivity solutions can escape this trap.
1.1 PRIOR WORK
Learning boolean functions with transformers: In an effort to understand the success of contem- porary LLMs, significant attention has been given to the ability of transformers to model formal languages (Bhattamishra et al. 2020) Chiang & Cholak 2022 Strobl et al. 2024), with some results showing shortcomings for modeling certain functions such PARITY (Hahn 2020: Bhattamishra ctt al. 2020). In turn, some work has shown that transformers are biased towards learning low- sensitivity Boolean functions, and that they are robust to label noise (Bhattamishra et al., 2023b Jonasson et al. 2023 (hhattaishha et al.] 2023a). Our work is distinct because we consider learning from examples with feature noise rather than label noise, which has a qualitatively different effect on the learning behavior of language models. The k-sparse parity problem is often used to evaluate the learning abilities of transformers (Barak et al. 2023 Michaud et al. 2024), but we show how performance at learning this function is somewhat deceptive in the setting of noise-robust learning.
Simplicity bias in transformers: A growing body of evidence shows that neural networks exhibit a bias towards learning simple functions for a variety of domains and simplicity measures (Arpit
al. 2017 Valle- Perez et al. 2019 Kalimeris et al. [2019] Mingard et al.) 2020) Cao et al., 2020) Yang & Salman 2020; Rahaman et al., 2019). (Bhattamishra et al. (202b)) showed empirically that transformers tasked with learning boolean functions are biased towards low-sensitivity solutions, compared to other recurrent models such as LSTMs. Later works provided additional theoretical and empirical evidence for this effect (Hahn & Rofin 2024, Vasudeva et al., 2025). Our work extends and applies these insights in two ways: We demonstrate that LSTMs generally fail to learn boolean functions given noisy input data, while transformers exhibit cunction-dependde learning abilities. Indeed, we argue that due their low sensitivity bias, transformers are fundamentally less
2

---

capable of learning boolean functions in the presence of feature noise, while such functions might in principle be learnable by a model with high sensitivity-bias
Information theory and noisy features: scribing any learner's ability to to predict subsequent or missing tokens of text in terms of the re- dundancy (or compressibility) of a source of randomness (Shannon 1951). Accordingly, prior work has related language modeling to compression in the context of Shannon source coding (Teahan & Harper 2003] Deletang et al. 2024) or Kolmogorov complexity (Sutskever) (023). However, our analysis differs by considering noisy features produced by some stochastic map acting on noiseless bitstrings, so that our setting is more related to noisy channel coding (Shannon 1948 1949) than
Information theory provides natural framework for de-
compression.
2 BACKGROUND
We first introduce some notation for dealing with distributions of random variables, and bitstring- valued variables in particular. We usually consider a random length-n bitstring X := (Xi...., xx)) taking value x == , E {0. 11th uniformly at random. The expected value of function f with domain {0, 1) ) is written Pxx [f(z)] == ExEx Px Px(x)) (x). or just E. [x=]] when there is no ambiguity. We define the conditional distribution PAJx of the n + 1 bit Y == f(X) generated by applying boolean function to the noiseless input bitstring X. Optimal performance
(noiseless)
next-bit prediction is related to the next-bit conditional entropy of Y given X: The entropy H (X)) := log (z) loosely, measures the uncertainty in predicting the value of X. The conditional entropy H (Y == Ey (x)()))((())))) describes the uncertainty about the value of X given that Y is known.
We model feature noise using independent, symmetric bitflip errors uniformly random input bitstrings. This error model is used broadly in both boolean analysis [O'Donnel] 2014). and com- munication theory (Cover, 1999). We describe bitflips using random variable E f0. 1)", where Pr(E;- = 1) := p. Then, the noisy bitstring Z = X @ E is generated by adding E to the noiseless bitstring X (mod 2). and induces a distribution pz- We generate training data point (Z,Y) for next-bit prediction with noisy features as follows: (i) Sample a noiseless bitstring X according to px, (ii) generate the next bit Y = f(X), (iii) apply iid bitflip errors E." create noisy features Z, and the goal of the learner is to predict Y given Z with (Z.Y) ~ pzy. Noisy validation data are generated in the same way, while noiseless test data (X, Y) are sampled directly from pxy. We define the noisy generalization error of a boolean function 9 with respect to a label function f (used to generate labels Y = =X() as
err e (g) = Pr (o(2) + f(x)) = (g(Z) XY), X.
(I)
2,
where (-x(-) denotes the probability with respect to X ~ px. We are mainly interested in a model's ability to learn the function f after training only on noisy training data Y), The noiseless gen- eralization error of model g evaluated on noiseless data is computed as Prx Prx(g(X) # f(X)). A learning algorithm succeeds at noise-robust learning if it learns boolean function with small noiseless generalization error, after being trained to minimize (empirical estimates of) crry(g). Throughout this work, we only consider training data with noisy features (Z, where 2 is a noisy version of X while Y is unaffected by label noise.
We will compare the noise-robust learning capabilities of self-attention network transformers (SANs) (Vaswani et al. (017) to LSTMs, continuing a recent line of investigation into the relative advantages and behaviors of these models (Bhattamishra et al.) (023b). Many of our experiments involve the parity function, PARITY(x)) := wt(x) mod 2, and the majority function MAJ(z) which outputs if and only if wt(x)= 2 n/2, where wt(z) denotes the Hamming weight. Importantly, MAJ is an imbalanced function when n is even. When relevant, we will use a subscript to refer to the input length (e.g. MAJ,). We will often consider sparse versions of these functions, whose output only depends on a subset of k S n input bits. We will denote this by an (n, k) pair, e.g. MAI(n, k) computes the majority for specific subset of k bits.
Performing experiments using boolean functions dependent on relatively few bits allows us to com- pare models' performance to an optimal prediction rule. We denote Bayes-optimal predictor for the distribution pzy as fy {0, 13 + {0, 1}, to be boolean function that satisfies err y (f*) S erry(g)
(2)
3

---

for all g: g: (0,1)" + {0. 13. The choice of optimal predictor is not unique in general (for instance, when f(z) = T1, fo (x) will not be influenced by Z2 ..... Tn.). We choose to evaluate a particular optimal predictor with the following formula:
[ix(t) == sign (p (x));
where [=](x)= == Ez(x== denotes the noise operator with respect to the distribution pxz with bitwise correlation p == 2s] O'Donnell (014)). We define (f) to be the set of all boolean functions/ h such that err(h) err(Jr). We defer further background on Boolean func- tions to Appendix [A] As mentioned before, the task of predicting [()) given z is rooted in noisy channel coding. Specificallly, the best possible accuracy err(fā) is bounded from above and below by (monotone decreasing) functions of the next bit (conditional) entropy (Feder& & Merhav 1994):
T )()())Z)) S <frr([f)> S ~- (H(Y)Z))-
Here, Φ is an invertible piece-wise linear function, while H(Y I ,(err((fū)) is Fano's in- equality (see Appendix A..)). The inequalities in Eq. aare analogous to upper (Candes & Tao 20066]
Donoho 2006) and lower bounds (Peters 2024) for certain learning tasks on continuous domains.
The dependence of next-bit prediction accuracy with noisy features the next-bit conditional en- tropy 2) captures a broader relationship between next-token prediction and noisy channel coding (Shannon 1948). We model next-token prediction as communication process between sender Alice and a receiver Bob, using a finite alphabet A. Alice first chooses a token of information Y = f(X) E E that she wishes communicate to Bob. She then encodes this token into the space of token sequences X E A", This encoding process contains some randomness (e.g. there are many ways to construct sentences that are semantically equivalent), as well noise (grammatical or syn- tactical errors), and so the map Y + X need not be one-to-on or even deterministie. Bob receives noisy bitstring Z A due to this combination of noise and stochasticity, and his goal is to decode the token f(X) of Alice's message given the string of noisy tokens 7 without knowledge of her encoding scheme. Thus, learning next-token prediction from noisy features is firmly rooted noisy channel coding, and is distinct from (but complements) alternative models based on source coding (compression) (Deletang et al. 2024) or Kolmogorov complexity (Sutskever) 2023). Since Bob does not priori know Alice's encoding scheme, he may not be capable of decoding her messages even in the noiseless setting. Eq. 4 thereefoe relates next-bit entropy to limitations on generalization per- formance in language modeling, and is related to noisy channel capacity in the asymptotic limit. In contrast, Bob's s ability to learn / from noisy features depends on properties of the noise and f, which we will return to in Section 3.1
TRANSFORMERS SUCCEED AT NOISE-ROBUST LEARNING OF SPARSE PARITIES AND ODD MAJORITIES
We now show that for a certain class of functions, transformers are able to learn a noiseless function when trained entirely with noisy features. This moves beyond prior work showing that transform- ers learn functions robust to noise at evaluation time /Vasudeva et al. 2025). Our experiments show that transformers are more robust than LSTMs at learning PARITY (n, A)) and MAJ(n, k) (but only when & is odd), when trained on data with iid bitflip noise applied to input features. We tested two kinds of boolean functions: sparse majorities and sparse parities. For each choice of biuflip rate p, we generated a size N dataset of (Z, f(X)) pairs, and then trained an LSTM or transformer to pre- dict the label for each point. We do not apply label noise any of our data. Since model's ability to learn is sensitive to initial parameter choice and hyperparameters, we repeated this process 300 times for each model with random initializations and random hyperparameters. We constructed the set of possible hyperparameters by iterative grid search while training each model on noiseless data, and then expanded this set slightly to account for hyperparameter optimality changing with noise strength. We provide detailed experiment descriptions in Appendix B
Fig. [ssows the relative performance of LSTMS versus SANs on learning several commonly-tested boolean functions with feature noise. We considered the sparse majority functions M2J 5), M40 5), MAJ 3) with N = 2000 noisy training data. In both cases, LSTMs and SANs reliably learn with zero feature noise. At modest noise strengths. the best of 300 LSTMs performs worse than the median transformer (which performs close to the information teormattion-theoretic optimal). We also compare both models' abilities to learn PARITY(n, k). However, sparse parity is significantly
4

---

median
opc
best LSTM [nalseles]]
median SAN [nolselesc]
opt [nolseless]
0.5
1.0
Fraction of model learning
SAN
Volidation accurocy
0.9
LSTN
0.3
PARITY(20, 4)
MAJ(20,5)
MAJ(40, 5)
MAJ(50, 0, 3)
0.6
0.5
0.0
0.0
0.5
1.0
0.0
0.5
1.0 0.0
0.5 Mext entropy
1.0
bit entropy
Next entropy
entropy
Figure I: Transformers learn MAJ, (with odd n) and PARITY robustly from noisy features. (a-c) For M2J 5) and MAJ(40, 5), the median transformer (SAN) reliably outperforms the best LSTM across 300 training runs with a variety of hyperparameters tuned to optimize both architec- tures' success probability. Validation accuracy approximates eIT ( using 10000 examples, where f is either an LSTM SAN prediction rule. Each point on the solid lines represents the best (me- dian) LSTM (SAN) from 300 training experiments. (d) While both LSTMs and SANs fail a large fraction of training experiments learning PARITY(20, 4) with feature noise, transformers suc- cessfully learn PARITY(20, 4) (defined as achieving noiseless accuracy 2 95%) more often than LSTMs, even when both architectures perform comparably zero noise rate. See Appendix for experiment details.
harder to learn: (i LSTMs generally fail learn (A k) for n 20 even with noiseless inputs (Bhattamishra et al. 2023b), and (ii) learning parity with feature noise rate corresponds to an instance of learning parity with noise (Blum al., 2003). an intractable learning problem. For := PARITY(20, 4). we compute the fraction of models that learned from noisy training data since the training process is highly sensitive to initial parameter choices. Among SAÑs and LSTMs that achieve comparable performance on learning PARITY(20, 4) in the noiseless setting, only SANs are capable of learning from noisy input features. We also found that this behavior extends to sparse multitask parities (Michaud et al., 2024), for which transformers succeeded at noise-robust learning while all LSTMs failed. Thus, for the commonly-studied PARITY and MAJ functions, we find that transformers achieve better learning outcomes across variety of hyperparameter choices and initializations.
3.1 NOISE ROBUSTNESS VERSUS SIMPLICITY BIAS
What explains transformers' impressive robustness to feature noise compared to LSTMs? Fig. demonstrated that transformers can learn from data with feature noise more robustly than LSTMs for few specific functions. One explanation for this behavior is the observed simplicity bias of deep
neural networks (Arpit et al. (017 Valle-Perez al. 2019 Mingard al. 2020 Cao al. 2020) as recent works demonstrate that transformers tend to learn simpler boolean functions compared
LSTMs without any explicit regularization (Bhattamishra et al.) [203b] Hahn & Rofin 2024)
Sensitivity is common measure of simplicity in the context of boolean functions (Kahn et al. 1988). The sensitivity of boolean function is defined
[0 Σ
Pr (f(x) f(z (0.13=
where @e denotes x with a bitflip location Simplicity bias helps explain why transformers trained noiseless data enjoy robustness to feature noise at evaluation time, since small test error noisy data combined with transformers' robustness implies small noisy generalization error (Eq. []: For uniformly distributed æ E 1]" and iid bitflip noise with probability p. function f obeys (f()) + f(z)) S plff] (ODDonlll 2014). Ordinarily, a transformer is trained to achieve low error noiseless inputs, such that Pr, (f(x) # f())) is small. Then, simple triangle
5

---

inequality gives
erry(f) (ey(f)s+pp Sctpf]]-
From this, we see that a transformer's simplicity bias (preference for ff with small Iff implies small error in predictions on noisy features at evaluation time. This intuitively explains observations that transformers trained on noiseless data can accurately classify noisy examples at evaluation time (Zhou et al. 2022), and has been referred to as noise robustness in other literature (Vasudeva et al. 2025).
However, in our setting we are concerned with training models on noisy features, which is a qual- itatively different than what is typically studied for boolean learning problems. Specifically, we ask: Will transformers trained on noisy features learn to make accurate predictions on noiseless data at evaluation time? The general answer is no. Our first clue that transformers can fail noise- robust learning is that the functions PA PARITY (rt k) and (AJ(n, k) analyzed above are actually special boolean functions that happen to be optimal for prediction on both noiseless and noisy features. The following proposition summarizes several results of (Weinberger & Shayevitz, 2018)) demonstrating how the majority and parity functions functions are qualitatively special among boolean functions: Proposition 1. For each function f E (MAJn; PARITY) (n odd). f is optimal for prediction on noisy features data, i.c. fN--
In the terminology of WWinberger & Shayevitz 2018), the majority and parity functions are self- predicting, as each function achieves optimal test error when evaluated on its respective noisy input distribution (Z, (X)) and can therefore, in principle, be learned by ordinary loss minimization (the self-predicting property immediately extends to sparse versions of each function). In this way, MAJ(n, k) with odd n and PA k) function are uniquely easy to learn with feature noise. We will now argue that for a typical boolean function f. it is instead true that f * fx- Therefore, we should expect that SANs and LSTMs will fail to learn f from noisy inputs, though we show an example of mitigating this shortcoming via tailored loss function.
4 TRAPPING TRANSFORMERS WITH SIMPLICITY BIAS
Section 3.1 suggested that transformers can learn boolean functions robustly in the presence of fea- ture noise for several hold in general, and should even be considered atypical. We will show that transformers generally fail at noise-robust learning due to a combination of their simplicity bias, and the observation that the optimal prediction rule for noisy data on average has lower sensitivity than the optimal predic- tion rule for noiseless data for randomly k-juntas with small k. Thus, whenever model with low sensitivity bias is trained via risk minimization on noisy examples (Z, fX)) on such functions, the model will typically fail to learn the target function f without further intervention.
functions. We now show that this behavior does not
Intuitively, feature noise should cause an optimal predictor f to be simpler than f. by some measure of simplicity. For example, if f is imbalanced function and p is sufficiently large, f& will be a constant function. The relative simplicity of S& compared to ʃ is also observed in least-squares regression atlenuation, wherein feature noise decreases the learned slope in ordinary least squares regression (Fuller) 2009). Similarly, feature noise can be understood to act as a regularization term in learning problems (Bishop 1995| Wager et al. 2013). Whenever fī * f. a model minimizing validation error by finding some f E (f) will forgo the possibility of learning f. In this case, might still be possible to learn of nobss-ro but only if the model has inductive biases towards learning / rather than alternative solutions g with erry(g) < (f) Conversely, the simplicity bias of transformers can actually harm their ability do noise-robust learning since the optimal solution fū for noise-robust learning often has lower sensitivity than the target function f, which we make concrete with the following proposition:
Proposition 2. Let f {0, 13" + {0, 1} be a function sampled uniformly at random from the set of all boolean functions n bits. Then, for sufficiently large the optimal predictor (x) := (fgn(Ti-pff(z)) has average sensitivity
2p(1-p) +2 (1-))
E, E ~ arecos
and in particular for forpe E 1/2].
E
(8)

---

Importantly, Eq. states that for uniformly random boolean functions on sufficiently many bits, the sensitivity f Is larger than the sensitivity of the optimal predictor fN on average. We observe that this inequality typically holds even for small n: Fig. 2 shows that [ 2 [[[2] holds for random k-juntas (k E (5, 6, 7,8), and additional simulations find violations of the inequality. On the other hand, there do exist functions for
We prove Proposition 2 in Appendix A.4
which [[f] < I[fīl, and so [[]] > 1[[]] can only hold as an average case statement. We discuss
these details further in Appendix A.4
(b)
noiselest val armo
noiseless val arror
0.030
0.75
0.2
0.025
0.50
(val erron- err
(val error) enr
0.020
-0.25
0.0
err-()- -em--/e
0.00
0.01
0.02
0.03
0.0
0.1
0.2
0.3
0.00
emif
emi(())
0.015
(d)
(e)
2.0
0.010
val ernor
1.5
0.005
0.2
1.0
0.5
0,000
0.0
0.0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.0
0.2
0.4
0.0
0.2
0.4
(1/) /o
em1()
Transformers generally fail at noise-robust learning for random k-juntas, and per- form worse as the difference in sensitivity and validation error for versus SN grows. (a) Each point represents a randomly sampled k-junta f (3200 total). Every randomly sample f obeys [[]] [[ while by definition erry(J) 2 err (fā)- Minimizing validation error in noise-robust. learning will only succeed for functions near the bottom of the plot, while a training algorithm with low sensitivity bias will only succeed for points near the left of the plot. By Prop. [ MAJ, (odd n. and PARITY are represented by the coordinate (0, 0). (b-c) Transformers only succeed at noise- robust learning when [f]] I[fğ] and erry(f) yfry(f)) (across 3200 learning experiments). Histograms of models' final validation error, train error, and optimal error demonstrate that noise- robust learning fails despite (d) near-optimal performance with (e) little overfitting. See Appendix B
Figure 2:
for additional experimental details.
Fig. demonstrates that the sensitivity difference between ʃ and J is usually large, with respect to random boolean functions. Correspondingly, across 3200 andomly-generateer k-sparse boolean functions (k-juntas), find that transformers tend to perform worse at noise-robust learning the difference (I[f] - I[f&x)) grows. This despite- - or because of achieving near-optimal validation error with minimal overfitting, and demonstrates correlation between the transformer's worsening performance and decreasing sensitivity of the optimal solution for noisy data. However, this rela- tionship is potentially confounded the difference (Jrry()) erry also grows, which will make the transformer less likely to learn / via loss-minimization regardless of [[]].
To isolate effect of simplicity bias transformers' and I.STMs' ability do noise-robust learning. we design a controlled experiment involving a trap function f such that erry(ft) R e but [[fī] < [[f]. In this case, a learning algorithm could learn f from noisy data principle, but will fail if it is biased towards lower sensitivity functions. Indeed, Figs. B(a-c) demonstrate that transformers fail to learn and instead converge towards the trap function J.. LSTMs also fail to leam f, but instead due to overfitting on training data. Thus, SANs and LSTMs both struggle with noise-robust learning, but fail to learn f from noisy data for completely different reasons.
A neural network might be capable of escaping the trap and learning f if we were replace its pref- erence for simple functions with a preference for complex functions. To test this possibility, we ran learning experiments for the same trap function but with additional term in the loss function that penalizes low- sensitivity solutions. We add additional loss term approximating -XI[f] each training step, which achieves a similar effect to penalizing high-weight components of the function's Fourier spectrum (Gorji et al. 2023). For a narrow choice of X, transformers were capable of
7

---

SAN+A
0.64
validation
1.0
naiseless validation
0.62
0.9
0.3
0.7
0.58
0.6
-2
(d)
(e)
(f)
(9)
1.0
1.0
0.705
0.9
0,700
0.9
validation
0.76
0.695
noiseless volldation
0.3
0.74
0.690
0.72
MAJ(30, 4)
0.6
0.685
0.7
0.70
0.5
10
10-1
10?
0.0
0.5
1.0
Sensitivity
Sensitivity
A (sonsitivtty regularization)
bit entrapy
Figure 3: LSTMs and transformers fail to learn f from training data with feature noise in distinet ways. (a)-(b) We consider particular trap function f such that err erry (ff ) e while [ff]] < I[f]. Blue and red lines show (smoothed) training dynamics of transformers and LSTMs trained on noisy inputs across a variety of hyperparameters and initializations. Each point represents (learned) boolean function. Trrasformmrs approach optimal validation accuracy (X) while RNNs perform no better than memorization of training data (X), and both models fail learn f (*). However, an explicit sensitivity penalty in the loss function A AIff] (A = 1) allows transformers to leamn (green lines) (c) There is clear optimum À for learning from noisy data using sensitivity penalty in the loss. (d-f) This behavior does not extend to functions where err < ( for example MAJ(30, 4) with p 0.32, for which SN is heavily biased function. (g) Overall, transformers do not outperform LSTMs at learning MAJ k) with even n (shown: MAJ(30, 4)) with feature noise. See Appendix B.3.2 for additional details.
caping the learning trap with this complexity bias (Fig. 3P), though this outcome depends on good choice for X, which may not be practical to optimize. Furthermore, learning algorithm is unlikely to learn f when err (f+) < (f)), even with a strong complexity bias. To demonstrate, we return to := MAI(n,A) k) (n even), for which f * f in general since / is imbalanced. Fig, d-f) shows that transformers typically fail to learn MAJ(30, 4) from noisy features (for many penalty pa- rameters A), while at the same time LSTMs become more capable learning the lower-sensitivity fā. As result, the performance gap between the median SAN and best LSTM for learning MAJ,, with even n almost completely disappears (Fig. B)).
5 DISCUSSION
Limitations: Our noise model and input data are limited in several ways: We have only considered noise in the form of independent bitflip errors on uniformly random input bitstrings, and is unclear if our findings would extend to other forms of noise. Many of the effects observed depend on the condition that / # /, which turn requires relatively high noise rates that may not be present in natural datasets. While have not considered label noise, previous analyses suggest that this would not affect the qualitative behavior our models (Bhattamishra et al. 2023b).
Here we have studied independent and identically distributed bitflip noise, toy model for noise occurring in real world data. Our observations should extend to other noise processes: For example, the mechanism by which T, decreases the sensitivity of boolean function does depend on identically distributed errors, and so the inequality I[fū] < I[f] should hold with high probability
for non-iid noise models. But here is reason expect that this inequality will hold for noise
8

---

models with arbitrary correlations between bitflips (see Appendix A.5 Moreover, bitflips lead to a qualitatively different form of noise than randomness introduced by generating bit sequences recurrently according some stochastic process. Future work will be necessary to determine the extent to which complex and realistic noise models obey T[A] 2 [[
Our experiments with noise-robust learning involved randomly -egnorrtdd k-juntas, which may be representative real noise-robust learning problems. Our trapping experiment using sensitivity penalties succeeded under tightly controlled conditions, though this experiment is provided only as a demonstration and this particular strategy may fail in general. It is likely that more sophisticated techniques will be needed improve transformers' ability to do noise-robust learning when f is much more accurate than f-
Our results suggest that transformers' simplicity bias has practical, negative con- sequences for learning boolean functions from training data with noisy features. Do these con- sequences extend domains with more complex inputs such as natural language processing? In certain natural language tasks like modular arithmetic (Liu et al., 2022), one hopes that transform- ers can learn input-sensitive discrete functions after training on text that contains both errors and stochasticity (i.e. entropy of written language). Our findings suggest that this may be impossible for sufficiently high-entropy inputs, since optimal prediction on noisy features corresponds to a low complexity predictor the training data. Our work complements recent observations that LLMs tend to perform poorly at math when exposed to noise at evaluation time (Shi et al. 2023 Abedin ett al. 2025), and suggests need for further experiments to examine how noise and stochasticity in training data affect LLMs reasoning abilities at evaluation time. Indeed, the mismatch between f and f in our experiments suggests that reducing model loss to the next-token conditional entropy may actually be detrimental for learning precise concepts from natural text.
Future work:
5.1 CONCLUSION
We have shown that transformers outperform LSTMs for learning sparse parities and (odd-length) sparse majorities in the presence of feature noise. But show that transformers fail at noise-robust learning of boolean functions more generally, and use controlled experiments with modified loss functions connect this failure specifically transformers' bias towards learning simple boolean functions. Our analysis suggests that transformers may be particularly unsuitable for learning sensi- tive functions in the presence of feature noise.
CODE AVAILABILITY
Code to reproduce experiments an analysis is available on Github: htttp:://ithhu.. com/
ACKNOWLEDGMENTS
We thank Cyril Goutte and Jackie Lo for helpful discussions. This work was supported by the Applied Quantum Computing Challenge Program the National Research Council of Canada. Re- search at Perimeter Institute is supported in part by the Government of Canada through the Depart- ment of Innovation, Science and Economic Development and by the Province of Ontario through the Ministry of Colleges and Universities. This work was supported in part by the Dieter Schwarz Foundation.
REFERENCES
Zain UI Abedin, Shahzeb Qamar, Lucie Flekk and Akbar Karimi. Arithmattack: Evaluating robust- ness of Ilms to noisy context in math problem solving. CoRR, 034/2501.08200 2025. URL
/ttp///...og/.....8/////////// wtt.///axi....m 2501. .02003
Devansh Arpit, Stanistaw Jastrzundefineddskii Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' pp. 232- JMLR.org, 2017.

---

Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: SGD learns parities near the computational limit, 2023. URL http://arxiv. org/ abs 2207.08799
Johannes Bausch, Andrew W Senior, Francisco JH Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, et al. Learning high-aceuracy error decoding for quantum processors. Nature, pp. 1-7, 2024.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of trans- formers to recognize formal languages. In Proceedings of the 2020 Conference on Empir- ical Methods in Natural Language Processing (EMNLPP, pp. 7096-7116, 2020. doi: 10. https//w11222..mmppmmmm....
URL http:::////// htwp:://wwww.oo www.wacll.. www.ww.wwwb.............. www.wwwwwwww.....ee.......ooee.e wtt..rrraooooooo/22222..2.2
emnlp main. 576
Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context
learning in transformers and Ilms by learning to learn discrete functions, 2023a. URL https:
03000
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. In Proceedings of the 6 Annual Meeting of the Association for Computational Linguistics (ACL), pp. 5767-5791, 2023b. doi: 10.18653/v1/ 2023.act-long.311
wwtp:yy..rgg22223./...g http:////....aaooooooooooooo///. long.
Chris M Bishop. Training with noise is equivalent tikhonov regularization. Neural computation, 7()):108-116, 1995.
Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 5064))506-519, July 2003. ISSN 0004-5411, doi: 10.1145/ 792538. 792544. ( URL httpt:://///m / //oii http:///0o..r1111111//////39//91 http:/100.115/799555333 792543
Sebastian Cammerer, Jakob Hoydis, Fayçal Ait Aoudia, and Alexander Keller. Graph neural net- works for channel decoding. In 2022 IEEE Globecom Workshops (GC Wkshps), pp. 486-491. IEEE, 2022.
Emmanuel J. Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory, 52(12):540655455 2006. doi: 10. 109/ TTT.2006.885500
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning, 2020. URL httph::tt/ttttttee htt.:t/ss//arraa..or////////11.1 0119
otgg
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention, 2022. URL http://arxivy wttp:/wwwwwgg/b/////..oooo
Yoni Choukroun and Lior Wolf. Error correction code transformer. In Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems (Neurips), 2022.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Gregoire Deletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christo- pher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. In The Twelfth International Confer- ence Learning Representations, 2024. URL httph: httt:::///peerevieee net forum?id- jzmbgi ynus
D.L. Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4):1289-1306 2006. doi: 10. 1109/TTT:2006.88 871582.
M. Feder and N. Merhav. Relations between entropy and error probability, JEEE Transactions In- formation Theory, (0(1):259-266 1994. ISSN 1557-9654. doi: 10.1109/18.272494 Conference Name: IEEE Transactions Information Theory.
10

---

Wayne A. Fuller. Measurement Error Models, volume 305 of Wiley Series in Probability and Statis- tics. John Wiley & Sons, Hoboken, NJ, 2009. ISBN 9780470317334
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings. 2010.
Ali Gorji, Andisheh Amrollahi, and Andreas Krause. scalable Halammrd regularizer to overcome the low-degree spectral bias of neural networks. In Robin J. Evans and Ilya Shpitser (eds.), Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, vol- ume 216 of Proceedings of Machine Learning Research, pp. 723-733 PMLR, 7 2023. URI.
https: httpp:s///roceeediee wgg..eeiing..... m www.srpress//ee v21
paaress/v16//oo/// jor 123 html
Michael Hahn. Theoretical limitations of self- in neural sequence models. Transactions of the Association for Computational Linguistics. 8:156-171, 2020. ISSN 2307-387X. doi: 10. 1162/tacl 00306. httphttt:///aiitit org. abs 1906. 06755
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.). Proceedings of the 62nd Anmual Meeting of the Associ- ation Computational Linguistics (Volume 1: Long Papers). pp. 14973-15008, Bangkok, Thai- land, August 2024, Association for Computational Linguisties. doi: 10. 10118633/112022.acllu 800. URL
www.244.cllllogg 800/
Johan Jonasson, Jeffrey E Steif, and Olof Zetterqvist.. Noise sensitivity and stability of deep neural networks for binary classification. Stochastic Processes and their Applications, 165:130-167, 2023.
J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In (Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pp. 68-80, 1988. doi: N0.1109/SFCS.198 198.FC2.1988.19999 219233.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complex- ity. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: pttpss:/ www.::nww......iee............ wwtp:sscccpppppppp fil ffle//22285555778877766333332222
Hyeji Kim, Yihan Jiang, Ranvir Rana, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Communication algorithms via deep learning. In International Conference Learning Repre- sentations (ICLR), 2018. URL htttts::://peeeeeeee
.nt. htw.:anneeeeeooomrrddeeaaaaaaaa
Moritz Lange Pontus Havström, Basudha Srivastava, Isak Bengtsson, Valdemar Bergentall, Karl Hammar, Olivia Heuts, Evert van Nieuwenburg, and Mats Granath. Data-driven decoding of quantum error correcting codes using graph neural networks. Phys. Rev. Res., 7:023181, 5 2025. doi: 10.1103/hysseeeessscchhhhh 7.02 URL //te::///iiikei.e wwi.nkapps.o..m ort.///ooo/////o////////oo
21c3/PayskevResearchh. 7.2331
Ziming Liu, Ouail Kitouni, Niklas Nolte, Eric J Michaud, Max Tegmark, and Mike Williams. To- wards understanding grokking: An effective theory of representation learning. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL
6at 6rt6rB322m
Eric J. Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling, 2024.
220.. 13506)
Chris Mingard, Joar Skalse, Guillermo Valle-Pérez, David Martinez-Rubio, Vladimir Mikulik, and Ard A. Louis. Neural networks are priori biased towards boolean functions with low entropy, 2020. URL http://pps//ppnneeeeeeeeeeeeeeee
Eliya Nachmani and Lior Wolf. flyper-graph-netweer decoders for block codes. Advances in Neural Information Processing Systems (Neurips), 32, 2019.

---

Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
Evan Peters. Bounds and guarantees for learning and entanglement, 2024.
URL https:
//aaxxv.orrg/bbb//44...000
Evan Peters. Importance sampling for data-driven decoding of quantum error-correcting codes,
2025. htl.tttss://arivv.oom abs htt.b////5555222.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learming Research, pp. 5301-5310. PMLR, 6 2019. wtt./tttpss//rrcceeddie
mlr.
wwwl:.pres///ee wwwps/v97777 rahaman1 9a html
C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27 (3):379-423, 1948. doi: 10.100 1538. 194...994.
Claude E Shannon. Communication in the presence of noise. Proceedings of the IRE, 37(1):10-21, 1949.
Claude E Shannon. Prediction and entropy of printed english. Bell system technical journal, 30(1):
50-64, 1951.
Freda Shi, Xinyum Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed H. Chi, Nathanael Schärli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 31210-31227. PMLR, 7 2023. URL httphhts//pprccceiiiiio wtw.a//ww.....pppe//e/sos htteess/v222/hh12222
ml
html
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? survey. Transactions of the Association for Computational Linguistics, 12:543-561, 2024.
Ilya Sutskever. An observation on generalization, 2023. URL https::t/// t/s simoos.........mmmmmmmm......o.m berkeler -eyy.y.... adt.nnes//bserree http:///erratttoooeeeeeeaaaaaaaa
William Teahan and David J Harper. Using compression-basee language models for text catego- rization. In Language modeling for information retrieval, pp. 141-165. Springer, 2003.
Giacomo Torlai and Roger G. Melko. Neural decoder for topological codes. Phys. Rev. Lett., 119 (3):030501, 2017. ISSN 0031-9007, 1079-7114. doi: 19.110 119.030501. URL http:// //t::///likk.. aps a dtt/10.i11111111 wwt.////s/yeyeeett...moo 11w.eettt..11..... 139.01
Guillermo Valle-Perez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes be- cause the parameter-function map is biased towards simple functions. In International Confer- ence on Learning Representations, 2019. URL httph: dectps://openrevieee wttp://wwwweteeetteeeeeeeee fodumiid rye4q3AqFm
Bhavya Vasudeva, Deqing Fu, Tianyi Zhou, Elliott Kau, Youqi Huang, and Vatsal Sharan. Trans- formers learn low sensitivity functions: Investigations and implications. In The Thirteenth In- ternational Conference on Learning Representations, 2025. URL /tttt::://openrvieee.
het/forum?id==1kk (WB33E
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Stefan Wager, Sida Wang, and Percy Liang. Dropout training as adaptive regularization. In Proceed- ings of the 27th International Conference Neural Information Processing Systems Volume 1, NIPS' 13, pp. 351-359, Red Hook, NY, USA, 2013. Curran Associates Inc.
Nir Weinberger and Ofer Shayevitz. Self-predicting boolean functions. In 2018 IEEE International Symposium Information Theory (ISIT), pp. 276-280, 2018. doi: 10.1 StW.I/SST..018.84377557
12

---

Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks, 2020. URL pattps:/arxiv..oo wttp:///ab//....10..1010
Daquan Zhou, Zhiding Yu, Enze Xie, Chaowei Xiao, Animashree Anandkumar, Jiashi Feng, and Jose M. Alvarez. Understanding the robustness in vision transformers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 117378227393 PMLR, 7 2022. URL https: pwoceedings.nu. mirr. press/vl v1 62 hwm222m html
13

---

APPENDICES
APPENDIX A BACKGROUND
A.1 BOOLEAN ANALYSIS
Unless otherwise noted, we will always consider uniform distributions of bitstrings E {0, 1)" i.e. (x 2 V vr We represent bitflips using an iid bitflip random variable E (E ........ En) where each E; takes values in {0. }} with Pr(E; 1) p. This means that Pr(wt(E) = w) = (1 p)" --0 "p"", , for instance. Then, Z := X @ E represents the string X that has undergone bitflip at each location where E is nonzero. The variables X and Z are not independent, but X and E are independent (written X [)). We can compute relationships of X and Z using this fact, for example:
px]z((/2)= Prx = =x, = 2)
(9)
(x
PTx,E(X- = E = 22)
(10)
px px(
= PE( + 2)
(11)
The sensitivity of f at æ is defined as the number of bit positions such that a single bitflip of changes the value f:
"
sff = Σ +(z
(12)
On the other hand, if we fix single bit then the influence of bit is defined as
[n == a Pr([(x) # f(x
(13)
The average sensitivity (or "total influence") of f is then defined as the average sensitivity over all inputs
I[fl = E=
1
Σ
s(f.z)
Infiff].
(14)
2
(E(0.1)
This takes values in the range [n], and thus I[f]/n gives the likelihood over random inputs that single bitflip changes the output value of f.
we alternatively represent bits {0, 1} as {1.-1}. we represent noise by considering pairs (a, 2) with sampled uniformly at random from 1)" and sampled conditionally such that each bit satisfies [[[r, p. In this case, we define the noise operator T, according to T, T Ex-p= [f()], where ~ denotes sampling conditionally on the way described above.
We will sometimes use Fourier analysis of Boolean. For a subset S C [n]]. the Fourier coefficient of f: -13" + R at subset S is defined
f(S) : Σ
f(x)xs(z)
(15)
=E(-1,1)"
where (s(x)) Iles Ni.
A.2 INFORMATION THEORY
We briefly introduce concepts from information theory. in order motivate how next-bit conditional entropy closely describes the hardness of next-bit prediction. Consider random variable X taking values x E X' with probability px (z:). The entropy of X is defined
H(X)
Σ (x log ZE
(16)
14

---

For joint distribution Xx over the pair of random variables (X1, X2), the conditional entropy of X2 given X1 is
x H(X,X2)
= Σ Px, F2) (2), 21.22
(12)a1).
(17)
The following theorem from Ref. Feder & Merhav (1994) shows how the error of a Bayes- next-token predictor is tightly controlled by the entropy of the next bit: Theorem 3. (Feder, 1994) Define the piecewise function ΦN [0, 1]
R and Φv [0, + R as
(A {ax (A - + log(k), 2 (A( = h2( + Alog(N -
K-1
< X K+I
(18)
(19)
with = k(k+ log( 1)/k) for t = 1... .. Let X and Y be random variables be a random variable taking values in alphabets X' and y respectively, with | N. Define the error probability of an optimal estimator as p. (Y (X) == miny + (r()(X) + Y). Then, N (p: (Y (Y ON (Y
(20)
Evidently, the optimal noisy generalization error erry(f%) is close to zero if and only if the cor- responding entropy H(f(X)IZ) is close to zero, and ert (fx) approaches 1/2 as H(f(X)) ap- proaches 1.
A.3 OPTIMAL NEXT-BIT PREDICTION
In this section, we show that fī from Eq. minimizes er and provide combinatorial proof for part of Proposition [ as an alternative to Ref. Weinberger & Shayevitz (2018). We will always assume uniform distribution of input bitstrings E {0, 1J". and a conditional distribution for noisy bitstrings z based on i.i.d. bitflips applied to each bit of x with probability p. The set of (Bayes- Joptimal predictors Fx (f) for set of boolean-labeled data with corrupted inputs {(2,, ((X))) is
given by all g satisfying
Pr(g(z) f())) 2 Pr(h(=) f(x))
(21)
2,2
for all boolean functions h. We will now show that f defined in Eq 2 of the main text an optimal predictor:
Lemma 4. For any symmetric bitflip rate p E [0, 0.5), then for p 1 2p we have
fM == sign (T,f) E FN())
(22)
Proof. Eq.
is equivalent
[1. Præ(f(x) - 1/2 2) 2 1/2
g(z) 1-,
(23)
11,
else
Compare this to
Txf(x) == ExrN((ol(())
(24)
-p((())f(())
(25)
Σ p(z1z) Σ p(2(z)
(26)
s:((===1
=;(()==11
Pr([(=)= = 2) - -Pr(f()) = -1 -P(((()==11xx = x)
(27)
= =B][[()]X xx]
(28)
Since pz|x (2|x) (2|x (x)2) we have Tzf(2) E. fz)) 2|. And so. ignoring the Tof
0
case
= =1 Pr(f() +a 12 = 2) > g =1
(29)
15

---

For the interested reader, provide simple combinatorial proof for part of Proposition of Weinberger & Shayevitz (2018).
Lemma 5. Fix a boolean function f and generate (X, 2) according to the bitflip scheme above. Then,
Pr (f(z) f())) > x X
Pr (f(z) + f(X)),
(30)
for all z implies that f (f).
Proof. We will show that the condition in Eq. 30 is sufficient for optimal prediction on noisy Z by showing that no other boolean function can do better than f when this condition holds. For any particular function g. define the set of inputs on which g agrees with f as
P(S.)) = (= E {0, 1)" g(z) = f())),
(31)
We may rewrite the output of as
g(2) = [f()),
2 P(f.g)
(32)
(-((2),
2E P(f.g)
Thus we find
Pr f(x)) Pr Pr (o(Z) f(X))
(33)
X,2
Σ
Pr (0(2) = f(X))
2
X|2=
=E(0,1}" n
Σ
Pr (ʃ(=) = ((X))
1
Σ
Pr (-f(z)
2n
X|Z==
2
x 7==
=EP(
sEP(J,))
Σ
Pr (f(2) = ((x)) +
Σ
Pr (f(z) # f(x))
2n
X|Z==
2
x Z=z
zEP(f.g)
zEP(f.g)
Σ
Pr (f(2) = f(X)) +
Σ
Pr (f(z) f(x))
2n
X|Z=
2
2=
=EP(f.9)
(())
(
(34)
X,2
where the final inequality follows from Eq. 30 and we have used the fact that the marginal distribu- tion of 6 is uniformly random whenever the distribution of X is uniformly random.
Note that Eq. 30 for optimality at noisy prediction is equivalent to
Pr(f(2) = f(2
(35)
Consider the dictator function DICT, which outputs the value of the first bit. It immediately follows that for f = DICT, fy DICT, since
Pr(DIcT(=) = DICT(= @ e)) = 2 2
(36)
We will next show that Eq. 35 holds for PARITY as well. Proposition 6 (PARITY is optimal for predicting noisy PARITY).
Proof. We will first show that for any noisy bitstring 2, the parity of the corresponding noiseless bitstring is most likely to match the parity of z. Using linearity and < 112 we have
Pr (PARITY(Z) = PARITY(X)) = Pr(PARITY(2) PARITY(2 @ E)) X -==
(37)
E
Pr(PARITY(2)) = PA @ PA)ITY(E))
(38)
E
(P(PARITY(E)) = 0)
(39)
E
Pr(wt(E) is even)
(40)
1 + 2p)"))
(41)
2
16

---

The final line is never less than 1/2 and therefore satisfies Eq. 35 By Lemma the proof is complete.
A combinatorial proof also exists showing that f ;= MAJ,, satisfies f f= f. for odd n. The proof is particularly illuminating, so we have excluded it.
A.4 PROOF OF PROPOSITION 2
Here we prove Proposition 2 and then discuss further the inequality
I 2 [
(42)
which holds with high probability for randomly sampled boolean functions (even for small n), but does not hold for all boolean functions.
Before proving asymptotic relationship between the influence of fā and f. we will need statistical moments random boolean functions. Recall that Rademacher random variable takes values in (1, with equal probability. Each Fourier coefficient
f(S)=
Σ (())x(()) =E(-1,13"
(43)
a sum of 2" independent Rademacher variables, since each fx) is itself Rademacher. As a result, the coefficients are distributed according to f(S) ~ 2 (2in () 2n) where Bin denotes the binomial distribution. Using standard results for the Binomial distribution yields
Eylf(s) 0
(44)
2 n ==T EfLf(S)((T)) = 0 else
(45)
and the Fourier coefficients of random function are, average, uncorrelated (they are not independent, we require Escla f(S)² 1). We may now prove the following proposition, which leads directly Proposition 2 in the main text.
Proposition Let f {1, 1 [1,-1} be uniformly random boolean function on bits, and define få == sign(T,f) for (0, 1). Then, for r(p)
(1-9²)
[I+p*]
[[f2] π
(rccos(r(p))
(46)
Proof. We will work with bitstrings taking values in {1, -13". Define kp(z|=) Pr(Z = 2|
r) denote the probability for noisy bitstring 2 given a p-correlated input bitstring x, i.e. (2
2- p) wtte) (1 + -)w-w(()) and so TT)((r) = Exer (p(xx)) For uniformly random f. f(z) is Rademacher, and we define family of two-dimensional random variables {Aa}
kp(z(x)
A =
(47)
For any particular f. we have [. = (x), T, (z)))) By the Central Limit Theorem, we have that [A[]]]] approaches a bivariate Gaussian distribution with covariance matrix
Ex (F.(T,
Eg (TTTT(()),,
Σ : E=
E. (a
(48)
By symmetry, we only need to compute two terms in this matrix. Recall that
Tpf(x)
Σ / (()
(49)
SCIn
17

---

and
[ =
p 11 ((3)
(50)
STTCMM
Σ
| "T T)xs(c)xr())
(51)
2-
X.s + +
(52)
2-
p² x.y1
(53)
where we have used Eq. 45 in the second equality. The terms in the covariance matrix E are then
R [T)T)(()) = [T } =2 2- )
(54)
Ey[T,f(e)T,f(1> = 20 p²) p²)n-1
(55)
Thus, we may define a unit-variance variable A == A²/ V (- p2)" which converges to bivariate Gaussian distribution with covariance matrix
1+p2
(56)
1-p"
I+
Then, Pr, (T.(s))(TT.((()) (Tg (z (1)) is equal to the probability that both components of A₃ are positive. Clearly this probability is unaffected by renormalization, and so we may apply Sheppard's formula (e.g. O'DDonell] (2014)): For standard Gaussian random variables an 02 with B[a102]= r
Pr(ai 0, 0) - 21 arccos(r)
(57)
π
Thus, we find that the limit of large n, the average sensitivity of f for randomly sampled obeys
E, Inf = 1 Pr (sign(T)f(c)) = sign(TT 1 / (P)(T 0, 0,T 20)
(58)
(59)
arccos(r(p))
(60)
7
Where we have invoked symmetry the distribution of f remove the averaging over æ in the definition of Tnf,, and further invocation of symmetry gives I[ʃ] n [n]. Substitution of - 2p recovers the result from the main text.
Additional observations We found that the inequality 42 holds for all Boolean functions of bits, and a large number of randomly-sampled boolean functions for larger For n 2 5. we tested this inequality with the following procedure: (1) sample a uniformly random element of 1-1,1)2", (2) generate f from this vector hash table, (3) compute Tp in the Fourier domain, (4) compute I[f*) and rif] in the Fourier domain. We repeated this procedure for several million boolean functions for {5, 6, 7, 8), for bitflip values in (0.01, 0.25, 0.49). No randomly sampled function violated inequality 42
Despite holding with high probability for random boolean functions, Eq. 42 does not hold for all boolean functions. A counterexample with T[sign ((signTT,f) (T,))) > T[ʃ] is given by the linear threshold
function (LTF) f(x) sign(a, (ag + Σn a,24) with
(oo, 41, a22 04, As. as) = 0.1, 0.1 0.3.0
(61)
and p = 0.2. Additional counterexamples may be found via grid search of LTFs over and (a:) for
larger n.. We unaware of any characterization of all such functions violating Eq. 42
18

---

A.5 DISCUSSION OF OTHER NOISE MODELS
We discuss how changes in the noise model might affect our findings. First, we argue that the noise is non-independent, then the relationship between [[ and [[] can easily break down as the noise on distinct bits starts to become more correlated. Second, we argue that independent (but non-identical noise) is less likely to affect our findings.
We first generalize the Bayes-optimal predictor to handle non-iid noise. An arbitrary noise distri- bution is defined according to conditional probability ((>]z) == Pr(Z = 2|X 2) of noisy bitstring z given noiseless input If is generated by flipping bits of independently of the value of æ, then we may write g(=|æ) == p=(= x). The generalization the noise operator Tp then
(T) [2x( =
(62)
(63)
(pE f)(),
(64)
where (f g) denotes convolution. As in Lemma one may verify that this generalized noise operator obeys fy == ff We may use Fourier theory to show that correlated noise can greatly increase the sensitivity of T, over the sensitivity of f. Applying the convolution theorem to (x)()) = (pE * (x) gives O'Donnell (2014):
Tyf(S) (s)))ss
(65)
The influence of f is I[f] = =E Esci..... |5]f(S), and so
[T, =
(S)EE())}((}}}
(66)
Sc......
distribution pg with strong correlations between individual bit flip events corresponds to large values of (S) for higher-order terms (larger [SS), in which case I[T,f] can become much larger than I[f]. While this argument is incomplete, the inequality [[ [[]] will often result in an inequality [[sign(T,J)] I[[].
On the other hand, noise that independent but non-identical will tend preserve the relationship between the sensitivity of f and the sensitivity of fř demonstrated in Proposition [ If the noise is uncorrelated, then pg is separable over bits, and so (S) = Thes Pt where pi is the correlation between z; and vi. So f acts like exponential filter in Fourier space, i.e.
f2f(S) = II
(67)
This is qualitatively similar behavior to the iid case where T,(S) = اك results in [[]]]] < [[]]. suggesting that observations about the relative sensitivity of f versus f (and specifically Propo- sition 2) likely extend to the case where noise is independent but non-identical across bits.
APPENDIX B EXPERIMENTAL METHODS
In this appendix, we describe in detail all the experimental methods used to obtain the results dis- played in figures [ 2 In what follows, we shall refer to the experiments performed to obtain the robustness results of section 3.1 as experiment 1, whereas experiment 3 shall refer to all the methods used to show how one can trap transformers with simplicity bias (section
B. DATASET GENERATION
We generate synthetic datasets for our experiments. for each dataset, we specify the number of validation samples nlal the number of training samples Raain- the number of bits in one data point Thas bit flip rate p, a seed for reproducibility and a boolean function f. Given these inputs, we generate the following:
19

---

1. Noiseless Data: uniformly sample Auaii + Roval many bitstrings, each of length Feut 1, compute the final bit for each using f. Take the first Uuai as the training data and the rest validation data.
2. Noisy Data: Take the noiseless data above, for each data point, apply symmetric bit flip rate p on each bit for the previous (Thit 1 bits, and keep the last bit unchanged.
Experiment 1 To obtain the results in Fig. [ the function f is taken MAJ 5), MAJ 5), MAJ(50, 3), and P2RITY(20, 4), respectively. For M20 5), MAJ(40, 5), and MAJ(50, 3), we chose Mirain 2000 and Thaa 10000, while for the function PARITY ; 4) we worked with Parain 5000 and Tvval = 10000.
Experiment 2 To obtain the results in Fig. 2 we generated 3200 random k-juntas (boolean functions
depending on only & bits) for & E {5,6, 6, J. All experiments used total of n = 10 bits, with the subset of bits chosen randomly. We generated noisy input data using a bitflip rate uniformly sampled from
{0, 0.05, 0.08, 0.10, 0.13, 0.16, 0.18, 0.2, 0.22, 0.244 0.26, 0.28, 0.3),
(68)
At bitflip rates lower than ~ 0.10, we found that f fā with high likelihood for our range of values. We generated training and validation sets with Duain = 5000, fvval = 10000 datapoints (smaller training datasets frequently resulted in underfitting).
Experiment For experiments shown in Fig. 3 we generated a "trap" function, i.c., a function f for which the corresponding f. is such that e x (fr and [[fk] < I[f]. To construct this function, we proceeded as follows. First, we restricted our search space to boolean functions f (0, {0,1)" 1)" > 1) satisfying f(x) f(wt(x)) (weight-based function), since only have 2n+1 such functions compared to the 2 number of all possible boolean functions over bits. Let us denote the space of weight-based functions by Wn. For each function in Wa (which can be completely characterized by n-bit string 8), we choose bitflip rate p (0, 1)- We iterated over the values n E {4, 44,550 6, 7, 8} and E {0.2, 0.22, 0.24, 0.26, 0.28, 0.303. For each combina- tion of n and p. we initially computed (fx) err (f), [[f). and [[ Since erry represents generalization error over an arbitrarily large dataset, for functions satisfying eIt y R (f),,),, we sampled finite training and validation datasets select dataset such that the performance of lookup table (which achieves optimal performance on validation data) was close to (f) This led specific dataset on n = 8, P- = 0.2, where f(i) == 8; with & = 0001 100000 We again use sparse functions depending
subset of Thbis = 14 that depends only on the embedded string s. The individual models (SAN, RNN, and regularized SAN) were trained using Paain = 10000 and Tval 20000. The resulting trap function that was used to generate the datasets used in experiment 3 will be denoted by 'T.
B.2 TRAINING AND HYPERPARAMETERS
Our experiments involve learning discrete functions, which can be sensitive to parameter initializa- tion and hyperparameter choice. In order to control for the effects of these choices, we chose to perform many trials of each learning experiment (with different initializations) over a range of hy- perparameters. In order to compare results across models and learning tasks, we used the following procedure to select hyperparameters for each experiment:
1. Select initial range of hyperparameters
2. Perform several hundred trials of the noiseless learning experiment (to learn either f or some randomly sampled f)
3. Prune the hyperparameter set to remove any ranges of hyperparameters for which models consistently failed to learn the target function
The result was a hyperparameter set for which large number (at least 70%) of the corresponding set of models were capable of learning the noiseless function. This implies that failure to learn the function (in the noisy setting) is not a capacity problem, and instead due to either bad initialization or limitations of the architecture. The exception for this procedure was learning PARITY (20, 4) (Fig. [T) which resulted in a bimodal distribution of models: Models were either able to learn parity, completely failed early in the experiment. This is in line with results reported in Ref. Bhattamishra
20

---

al. 2023b)) which observed that PARITY 4) was near the limit of what is learnable by (small) transformers.
All experiments cessors (20 cores, 2.1 GHz) and 768 GB of RAM each, or AMD EPYC 9754 processors (128 cores, 2.25 GHz) and 1.5 TB of RAM. On average, single hyperparameter tuning experiment took ap- proximately hours across 300 cores parallel. Total CPU estimates are
performed
CPU cluster consisting of either Intel Xeon Gold 6230 pro-
60, 000 CPU hours for Fig. 1
~~
100, 000 CPU hours for Experiment in total)
15000 CPU hours for Fig. 30000 CPU hours for Experiment total)
5000 CPU hours for Fig. 10000 CPU hours for Experiment 3 in total).
In each experiments, models were trained for up to 1000 epochs, with early stopping criterion of 300 epochs conditioned on no improvement in validation accuracy. All reported metrics correspond to the model performance at the epoch with maximum validation accuracy. We do not tokenize any these datasets, since both the underlying distribution and noise acting on our synthetic data depend on individual bits.
B.3 MODEL ARCHITECTURES
Transformer: Our experiments employ an encoder-only transformer with final linear layer to gen- erate outputs. We initialize with the Xavier uniform Glorot & Bengio (000)) (following Ref. [Bhat-] tamishra et al. (2023b)) and ReLU activation for the encoder's FFN and absolute positional encod- ing. We train using cross-entropy loss. The initial hyperparameter search space for Experiments 1, 2, and 3 is given in Table | and refers to hyperparameters as introduced in Ref. Vaswani et al. 2017).
Table 1: Hyperparameter search space for Transformer model for experiments 1-3. The final hyper- parameter sampling space across trials was tuned for each experiment separately (see above).
Hyperparameter
Values
Learning Rate (1x)
[1 x 10-5 10-$,6.31
6.31 x 10-21
Depth
1, 3, 5,
Model Dimension (d-model)
16, 32, 64, 128
Dropout Rate
0.05, 0.10
Number of Attention Heads
2, 4, 8
Feedforward Dimension (d.ffn)
32, 64, 128
LSTM: We used LSTMs with Xavier uniform initialization, log-likelihood loss and softmax acti- vation (i.e. cross-entropy loss). The initial hyperparameter search space for LSTMs is shown in Table
Table Hyperparameter search space for LSTM trials in Experiments 1 and 3.
Hyperpaarameter
Values
Learning Rate (1r)
[] x 10-4 2.78 x 10-1
Embedding Size (emb_size)
16, 32, 64, 128
Hidden Size (hidden size)
16, 32, 64, 128
Dropout Rate
0.05, 0.10
Depth
1,2,3,4, 4,
Our experiments are initialized with hyperparameters sampled from distribution such that models achieved Rs 70% on the corresponding noiseless learning task. This introduces significant variance in model architectures and parameter counts. Tables provide some typical parameter counts (and corresponding hyperparameters) for models initialized in this way in Experiment for the PARITY PARITY(20, 4) task.
21

---

Table 3: Parameter count and hyperparameter settings for three random transformers. Median pa-
rameter count for transformers was 32514 in the Experiment I PARITY(20,,, 4) task.
parameters
d.model
heads
d.ffn
depth
42562
64
32
2
11218
16
32
5
8738
32
64
1
Table 4: Parameter count and hyperparameters for three random LSTMs from the Experiment emb_size hidden_size
PARITY(20, 4) task. Median parameter count: 46530.
parameters
depth
54978
64
32
11938
64
16
29634
64
32
B.3.1 EXPERIMENT
Experiment I involved training transformers and LSTMs to learn MAJ and PARITY from noisy fea- tures. For each of E (2A) 5), MAJ 5), MAJ 3), (30 4), PARITY((0,, 4)}, we con- struct datasets (z, (z)) with range of bitflip error probabilities selected from [0, 0.49). For each dataset, we train 300 randomly initialized LSTMs and Transformers (each training run one trial) to minimize their corresponding loss function, with early stopping and model selection based on maximum validation accuracy.
Fig. 4 shows distributions of validation accuracies for all experiments involving MAJ functions. For all majority functions, the transformer validation accuracy concentrates near optimal for each bitflip rate. By contrast, from Fig 3g the noiseless performance of transformers faster than MAJ with odd n. We also find that the distribution LSTM validation accuracies for MAJ(30,4) 4) tends be more bimodal than for MAJ problems with odd n.
M30 4) degrades
For learning PARITY P20 4), Fig. 5 shows clear bimodal distribution in the final validation accuracy across a range of bitflip rates. Other than the noiseless scenario, LSTMs trained in our hyperparam- eter set were practically incapable of noise-robust learning.
22

---

0%
11.1%
25%
1%
14.0%
10%
MAJ(20,5)
500
MAJ(30, 4)
MAJ(40, 5)
MAJ(50. 3)
600
125
Number of LSTMs
250
500
100
200
100
400
75
800
50
50
100
25
Pof 0 0 0
600600
0.0
0'000 000000000
0
0.0
MA](20,5)
5)
MA]
MAJ(40,5)
MAJ(50, 3)
Number transtormers
200
550
250
250
00
150
150
150
10
50
50
50
50
0
Transformer val
Transformer
Transformer
Transformer
Figure 4: Validation accuracy for LSTMs (top row) and transformers (bottom row) for each sparse MAJ noise-robust learning task, colored according to bitflip rate. Each experiment with particular emor rate consists of 300 independent training runs with random initialization (maximum validation accuracy each training trial is shown).
PARITY(20, 4)
PARITY(20,
300
6.3%
3.1%
22.5%
250
2.2%
15.2%
200
200
150
150
0
Figure 5: Validation accuracy for LSTMs (left) and transformers (right) for the PARITY(2O, 4) noise- robust learning task (other details same as Fig.
23

---

B.3.2 EXPERIMENT 3
Figure 6 represents the collection of experiments that were used to show that transformers can be trapped due to their simplicity bias (refer to section D. Fig. [ compares the relationship between sensitivity and accuracy for different architectures for both noisy and noiseless validation datasets generated with the function T. Each plot shows training trajectories of individual models (colored lines) that end at the point where the model achieves maximum accuracy on the respective validation dataset (circular markers). In the presence of noise (Figs. aa). ((c), and ([)),, one sees that all the
models cluster in a relatively narrow accuracy band around (0.5, 0.6). As pointed out in Section the overall behavior of the SANs is to learn function that optimizes the validation accuracy Coptimal validation lookup table represented by X). Nonetheless, due to the unavoidable randomness in machine learning models, combined with the transformer simplicity bias, Fig. G(a) shows that some individual models can get significantly closer to the true function (represented by *). This is certainly not the case with LSTMs (Fig. 7 as all the individual models seem to cluster around the optimal training accuracy (lookup table for training set denoted by X). In Fig. 7c), we see that the presence of simplicity penalty helps to bring the vast majority of the individual models significantly closer to the true function.
On the other hand, when the models are evaluated on the noiseless (original) dataset (Figs. b(b), d), and ff)), the architectures SAN and LSTM fail to learn the original function. Nonetheless, SANs perform better than LSTMs and are generally more suitable for this problem. As before, the addition of a simplicity penalty improves the learning traces of the SANS.
The pattern no longer holds for the function (30, 4) (Fig. 7 Here, in both the noisy and noise- less validation cases, there seems to be no overall pattern followed by the individual learning traces. The overall behavior of the experiments indicates that LSTMs and SANs approach optimal valida- tion accuracy, with no clear differences in their sensitivity. Adding simplicity penalty to SANs has minimal effect on their performance. Across experiments, no model comes close to learning the true function.
SAN
5.33
3.5
3675
X
R323
142
0225
2535
3.5
3535
6553
Accuracy
6535
3223
115
1.
18
084
21
04-
24
2N
1.5 2.5
45
20
Sensitivity
Figure 6: Validation (top row) and poiseless-validatinn (bottom row) accuracies for each architecture (rows: SAN, RNN, SAN+X) trained on the dataset generated by the trap function T as a function of the sensitivity. Each colored curve is one of 19 independent runs, shown up to the epoch of its peak validation accuracy (blue, red, and green circles). The X represents a lookup table for the validation dataset; the X represents a lookup table on the training dataset; the * represents the true (noiseless) function.
24

---

SAN
68
0.
0.-
0.5
Accuracy
1/1 355
25
Sensitivity
Figure Validation (toprow) row) and
(bottom row) accuracies for each architecture
(rows: SAN, RNN, SAN+X) trained on datasets generated with MAJ(30, 4) function of the sensitivity. Each colored curve one 19 independent runs, shown up to the epoch of its peak validation accuracy (blue, red, and green circles). The X. X. * retain their meaning from Fig. 6
STATEMENT ON LLM USAGE
Large language models were used to assist in literature review, code development, theory develop- ment, and analysis for this project. None the text or equations in this manuscript were generated by an LLM.
25


Reviews:
[{"review_id": "qSsQ1niDmn", "reviewer": "Reviewer_TMxh", "summary": "This work analyzes the ability of transformers and LSTMs in learning boolean functions, in the feature noise setting (with no label noise). The motivation for this lies in the prevalence of noise in LLM training data, and boolean functions serve as a sandbox for understanding this phenomenon. Through extensive simulations, it is shown that for the majority function and certain sparse parity functions, transformers succeed with learning the optimal function while LSTMs fail. On the other hand, for most other random boolean functions, both of these architectures fail to learn in the feature noise setting, although for the case of transformers, this can be mitigated with a modified regularized loss function.", "questions": "- What are some of the main bottlenecks preventing the authors from making the conjecture rigorous?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The motivation for the theoretical setup is clear (e.g. inspiration from modern day LLM training).\n- Extensive experiments are provided for demonstrating when transformers can and cannot learn boolean functions (e.g. which $k$ in a $k$-sparse parity in which learning with feature noise is possible, as well as majority functions, and other $k$-juntas).\n- The analysis of the sensitivity of the optimal predictor under feature noise versus the teacher is an interesting perspective, and a conjecture regarding this is proposed, backed by simulations.", "weaknesses": "- The analysis for parity and majority seem quite straightforward, and it would be interesting if there was more theoretical analysis on progress towards the conjecture.\n- For the LSTM model, it would be useful to have some theoretical analysis of this setting for learning boolean functions too.\n- Perhaps an example of a realistic setting of feature noise in training transformers would be useful, and I believe this would better motivate this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1vLlANqoGJ", "reviewer": "Reviewer_RgtW", "summary": "The paper studies noise-robust learning: whether models trained only on inputs corrupted by feature noise can still learn the underlying noiseless target function. Using Boolean tasks, the authors:\n\n* Formalize the Bayes-optimal predictor under iid bit-flip noise as $f_N^*(x)=\\mathrm{sign}(T_{1-2p} f(x))$, where $T_\\rho$ is the standard noise operator. This links the problem to noisy-channel coding and bounds performance via conditional entropy. \n* Show empirically that transformers (encoder-only SANs) often succeed at noise-robust learning for sparse parity and odd-length sparse majority functions, while LSTMs generally fail even at modest noise rates. (Figure 1)\n* Demonstrate that transformers typically fail on random k‑juntas, even when they achieve near‑optimal accuracy on the noisy validation distribution; failure correlates with the gap between the sensitivity of $f$ and that of the optimal noisy predictor $f_N^*$. (Figure 2)\n* Argue the failure mechanism combines a simplicity bias in transformers toward low‑sensitivity functions and the empirical observation that $f_N^*$ tends to have lower sensitivity than $f$. (Conjecture 1)\n* Construct a controlled \"trap\" function where $f$ and $f\\_N^\\*$ have similar optimal noisy accuracy but very different sensitivities; transformers converge to the simpler $f\\_N^\\*$. Adding a differentiable sensitivity penalty helps \"escape\" in a narrow range of penalty weights, but when $f\\_N^\\*$ is much better than $f\\_N^\\*$, the penalty does not help.", "questions": "1. How sensitive are the main findings to non‑iid or structured noise (e.g., burst errors, deletions/insertions, or noise correlated with specific positions)? Could the channel view extend to these cases and does the simplicity gap persist? \n2. What happens when inputs are non‑uniform (e.g., biased bit marginals or low‑entropy substructures), closer to natural text statistics? Does the prevalence of self‑predicting functions change under such distributions? \n3. Can the authors provide explicit parameter counts to the models? It is a bit troublesome to compute them from the dimensions provided in the appendix. Does model size/capacity have any effect on the biases observed?\n4. Is there a practical diagnostic to detect, during training, when a model is converging to $f_N^*$ rather than $f$? The training‑trace figures suggest this might be possible.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Casting training-on-noisy-features as a noisy-channel problem, with $f_N^*$ characterized by the noise operator and performance tied to $H(Y|Z)$, gives a precise target for comparison. \n* Extensive hyperparameter sweeps and repeated trials (300 per condition) improve the reliability of the conclusions. \n* The use of total influence $I[f]$ to quantify simplicity connects to prior theory and cleanly explains why models can perform well on noisy validation yet fail on noiseless evaluation. \n* The “trap function” isolates simplicity bias from other confounders: with nearly equal noisy optimal errors for $f$ and $f_N^*$, any preference for $f_N^*$ reveals the inductive bias. Figure 8 show SANs drifting toward the trap unless regularized. \n* The discussion connects Boolean results to real LLM settings where training data are noisy/stochastic but downstream tasks are noise‑sensitive (e.g., arithmetic), cautioning that minimizing conditional entropy on noisy features might impede learning fine‑grained rules.", "weaknesses": "* Narrow noise model and data distribution. All inputs are uniformly random bitstrings with iid symmetric bit‑flip noise and memoryless corruption. Real text has structured distributions and correlated, non‑binary errors (insertions, deletions, paraphrases). The paper acknowledges this but leaves generality uncertain. \n* Task scope. Results hinge on Boolean functions; while parity/majority and k‑juntas are classic, evidence that the same mechanisms dominate in natural language or code remains indirect. No experiments on tokenized sequences, algorithmic datasets, or synthetic “text‑like” corruptions are provided. \n* The sensitivity penalty that helps in the trap requires a narrow range of $\\lambda$ and does not generalize when $f_N^*$ dominates $f$. This makes it difficult to apply similar ideas in practice\n* Conjecture 1—$I[f_N^*] \\le I[f]$—is well‑motivated and tested on small n and random samples, but remains unproven. Many conclusions rely on it conceptually; a counterexample would undercut the narrative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y57DChkb87", "reviewer": "Reviewer_NNLa", "summary": "This paper studies the capability of transformers on noise-robust learning. Transformers are compared to LSTMs for this task. Main contributions of this paper include the following.\n1. For sparse parity and majority functions at high rates of feature noise, transformers perform significantly better than LSTMs, and the latter fails even for low levels of feature noise.\n2. They observed that transformers do not have satisfactory performance for the task of random k-juntas.\n3. They proposed an explanation related to sensitivity of optimal solution and of target function.\n4. Solution: implementing penalty for high-sensitivity solutions", "questions": "My question is highly relevant with what I wrote in the weaknesses section: Does the theoretical insights obtained from your study have any implications on the robustness of transformers for more complicated tasks", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem formulation is novel by adding a perspective on robustness. Noise-robust learning is valuable but yet relatively under explored.\n\n2. The paper has sound theoretical analysis and the theoretical results provide significant insights. It deploys various mathematical tools efficiently, including Boolean analysis, information theory, and learning theory.\n\n3. Experiments, although relatively small-scaled, has a clear target on the conjecture and provides valuable support\n\n4. The paper is in general well-written and the logic flows smoothly", "weaknesses": "My main concern is on the applicability and scope of this study. The investigated problems (parity and junta) are binary-input problems with rigid mathematical structures. This fact provides simplicity for analysis, but at the same time they are restricted because real-world data and noises are much more complicated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)