One-sentence Summary

Saarland University proves that transformer loss landscapes are constrained by input-space sensitivity, since functions whose output depends on many input positions inhabit isolated points in parameter space, a result that unifies empirical observations about low-sensitivity bias, degree bias, and difficulty learning $\text{PARITY}$PARITY, and demonstrates that understanding inductive biases requires studying loss landscapes beyond expressivity.

Key Contributions

• The transformer loss landscape constrains high input-space sensitivity to isolated sharp minima, creating a generalization bias toward low sensitivity.
• The theory links input sensitivity and Fourier degree, explaining easier learning of FIRST and MEAN and difficulty with PARITY and length generalization.
• Experiments on formal-language functions support the theory and shift focus from in-principle expressivity to quantitative loss-landscape analysis for understanding transformer biases.

Introduction

Transformers are widely used for sequence modeling and formal language tasks, yet experiments reveal surprising learning biases. In particular, transformers often struggle with highly sensitive functions such as PARITY, where flipping any input bit changes the output, and trained solutions frequently fail to generalize from short inputs to longer ones. Prior theoretical work mostly studied expressiveness, showing that some transformer variants can represent PARITY in principle or that individual input bits may have limited influence, but these results did not explain why learning such functions remains hard under gradient descent. The authors address this gap by linking input-space sensitivity to the transformer loss landscape. They prove that parameter settings achieving high sensitivity are brittle, because small parameter perturbations yield much less sensitive functions on long inputs, forcing high-sensitivity solutions into very sharp minima. This provides a theoretical account of the observed low-sensitivity bias, training difficulty, and poor length generalization in transformers.

Method

Formal Transformer Model and Sensitivity Analysis

The authors leverage a simplified but theoretically tractable transformer model to connect model expressiveness, layer norm behavior, and loss landscape geometry. The task is defined over Boolean strings $x \in \{\pm 1\}^n$x∈{±1}n. Each symbol is embedded into $\mathbb{R}^d$Rd by word embeddings $e(-1), e(+1)$e(−1),e(+1), and each position is embedded by positional encodings $p_1, p_2, \ldots \in \mathbb{R}^d$p1​,p2​,…∈Rd. The initial representation at position $i$i is therefore

$$y_i^{(0)} := e(x_i) + p_i,$$yi(0)​:=e(xi​)+pi​,

where $x_i \in \{\pm 1\}$xi​∈{±1} is the $i$i-th input bit.

The model has a fixed depth $L$L. At layer $k$k, each position $i$i has an activation $y_i^{(k)} \in \mathbb{R}^d$yi(k)​∈Rd. Each layer contains $H$H attention heads. For head $h$h in layer $k$k, the authors compute a pre softmax attention score using key and query matrices $K_{k,h}$Kk,h​ and $Q_{k,h}$Qk,h​:

$$a_{i,j}^{(k,h)} = \left(K_{k,h} y_j^{(k-1)}\right)^\top Q_{k,h} y_i^{(k-1)}.$$ai,j(k,h)​=(Kk,h​yj(k−1)​)⊤Qk,h​yi(k−1)​.

These scores are normalized into attention weights by a softmax operation:

$$\widehat{a}_{i,j}^{(k,h)} = \frac{\exp(a_{i,j}^{(k,h)})} {\sum_s \exp(a_{i,s}^{(k,h)})}.$$ai,j(k,h)​=∑s​exp(ai,s(k,h)​)exp(ai,j(k,h)​)​.

The output of head $h$h at position $i$i is a weighted sum of transformed activations:

$$b_{i,h}^{(k)} = \sum_{j=1}^n \widehat{a}_{i,j}^{(k,h)} V_{k,h} y_j^{(k-1)},$$bi,h(k)​=j=1∑n​ai,j(k,h)​Vk,h​yj(k−1)​,

where $V_{k,h}$Vk,h​ is the value matrix. The head outputs are summed and fed through a feedforward module with a skip connection:

$$Y_i^{(k)} := f^{\mathrm{MLP}} \left( y_i^{(k-1)} + \sum_{h=1}^H b_{i,h}^{(k)} \right).$$Yi(k)​:=fMLP(yi(k−1)​+h=1∑H​bi,h(k)​).

The authors then apply layer norm:

$$\mathrm{LayerNorm}(y) := \frac{y - \mathrm{mean}(y)} {\sqrt{\sigma^2(y) + \varepsilon}},$$LayerNorm(y):=σ2(y)+ε​y−mean(y)​,

where $\varepsilon \ge 0$ε≥0 is a small stabilizing constant and $\sigma^2(y)$σ2(y) denotes the variance of the vector entries. The output of layer $k$k at position $i$i is

$$y_i^{(k)} := \mathrm{LayerNorm}\left(Y_i^{(k)}\right).$$yi(k)​:=LayerNorm(Yi(k)​).

A central object in the analysis is the layer norm normalization factor

$$N_i^{(k)} := \frac{1} {\sqrt{\sigma^2(Y_i^{(k)}) + \varepsilon}}.$$Ni(k)​:=σ2(Yi(k)​)+ε​1​.

This quantity measures how strongly the layer norm rescales the pre normalized activation. If the variance of $Y_i^{(k)}$Yi(k)​ is small, then $N_i^{(k)}$Ni(k)​ becomes large, and layer norm can greatly amplify the effective magnitude of the representation. The authors use this mechanism to explain why transformers can express some functions only by entering regions of parameter space where small perturbations produce large changes in predictions.

The final prediction is made by taking the last position activation after the final layer and projecting it with an output vector $\nu_{\mathrm{out}}$νout​:

$$T(x) := \nu_{\mathrm{out}}^\top y_n^{(L)}.$$T(x):=νout⊤​yn(L)​.

The analysis then introduces sensitivity as the bridge between function complexity and training behavior. For a Boolean function, sensitivity measures how often flipping a single input bit changes the output. If $x^{\oplus i}$x⊕i denotes the string obtained by flipping the $i$i-th coordinate of $x$x, then the input sensitivity at $x$x can be written as

$$s(f,x) = \sum_{i=1}^n \mathbf{1}\left\{ f(x^{\oplus i}) \neq f(x) \right\}.$$s(f,x)=i=1∑n​1{f(x⊕i)=f(x)}.

The average sensitivity is

$$\mathrm{as}_n(f) = \mathbb{E}_{x \in \{\pm 1\}^n} s(f,x).$$asn​(f)=Ex∈{±1}n​s(f,x).

Functions such as parity have high average sensitivity because many bit flips can change the output, whereas functions such as mean, majority, or sparse lookup can have much smaller average sensitivity under uniform inputs.

The theoretical method first bounds the input space Lipschitzness of the transformer prediction. A global constant $C$C is introduced. It includes an exponential term depending on the spectral norms of key query products,

$$\exp \left( 4d \max_h \sum_{i=2}^L \|K_{i,h}^\top Q_{i,h}\|_2 \right),$$exp(4dhmax​i=2∑L​∥Ki,h⊤​Qi,h​∥2​),

and a polynomial factor in the width, depth, attention head count, spectral norms of the model matrices, and embedding norms. A classical style Lipschitz bound has the form

$$s(f,x) \le \frac{ C \exp\left(4d \max_h \|K_{1,h}^\top Q_{1,h}\|_2\right) } {e^{L/2}},$$s(f,x)≤eL/2Cexp(4dmaxh​∥K1,h⊤​Q1,h​∥2​)​,

which shows a possible exponential dependence on the input layer key query matrices. The authors then sharpen this dependence. Using concentration over attention weights, they show that for a large fraction of inputs, roughly $1 - H n^{-2}$1−Hn−2 of all inputs, the input layer exponential term can be replaced by a logarithmic factor, yielding a bound of the form

$$s(f,x) \le C \frac{\log n}{e^{L/2}}.$$s(f,x)≤CeL/2logn​.

This step is important because it separates two sources of difficulty: large model parameters, captured by $C$C, and large layer norm amplification.

To isolate the second source, the authors define a layer norm blowup term. At layer $k$k and input $x$x,

$$\tau^{(k)}(x) := \max_{w=1,\ldots,n} \left\{ 1 + N_w^{(k)}(x) \right\}.$$τ(k)(x):=w=1,…,nmax​{1+Nw(k)​(x)}.

The total blowup from input to output is

$$\mathrm{Blowup}(x) := \prod_{k=1}^L \tau^{(k)}(x).$$Blowup(x):=k=1∏L​τ(k)(x).

The addition of one is technical, but when the blowup is large, this term is governed by the normalization factors $N_w^{(k)}$Nw(k)​. Large layer norm blowup means that representations are repeatedly rescaled by very large factors, so small changes in activations can become large changes in predictions.

The method then localizes this blowup to the Hamming neighborhood of sensitive inputs. The authors establish that, with high probability over the choice of $x$x,

$$\frac{ s(f,x) } { C \sqrt{n \log n} } \le \mathrm{Blowup}(x)^2 + \frac{1}{n} \sum_{i=1}^n \mathrm{Blowup}(x^{\oplus i})^2.$$Cnlogn​s(f,x)​≤Blowup(x)2+n1​i=1∑n​Blowup(x⊕i)2.

Averaging this relationship over uniformly distributed inputs gives the central tradeoff:

$$C \cdot \mathbb{E} \left[ \mathrm{Blowup}(x)^2 \right] \ge \frac{ \mathrm{as}_n(f) } { \sqrt{n \log n} } - \frac{H}{n}.$$C⋅E[Blowup(x)2]≥nlogn​asn​(f)​−nH​.

For large $n$n, the $H/n$H/n term becomes small. Thus, if a transformer is to represent a function with large average sensitivity, then either the parameter constant $C$C must be large, or the layer norm blowup must be large. For parity, where $\mathrm{as}_n(f) = n$asn​(f)=n, the bound predicts

$$C \cdot \mathbb{E} \left[ \mathrm{Blowup}(x)^2 \right] = \Omega \left( \frac{\sqrt{n}}{\log n} \right),$$C⋅E[Blowup(x)2]=Ω(lognn​​),

which grows with input length. This suggests that representing parity for increasingly long inputs requires either growing parameters or growing layer norm amplification.

The analysis also explains why some functions are easier despite having nontrivial dependence on the input length. For sparse functions such as first, the average sensitivity is $O(1)$O(1), so the lower bound does not require large blowup. Transformers can represent such functions by scaling attention logits with $\log n$logn, which does not force the same kind of sharp minima. For mean, the local sensitivity is very small on most inputs, so little blowup is predicted. For majority, average sensitivity is sublinear, but local sensitivity becomes high near balanced inputs. The theory predicts that blowup is required on or near these sensitive neighborhoods.

The second major methodological component translates this input space sensitivity into parameter space sharpness. Given a transformer parameter vector $\theta$θ, the average directional sharpness is defined as

$$L_{\rho,n}(T) := \mathbb{E}_{x \in \{\pm 1\}^n} \mathbb{E}_{\|\Delta\|_2 = \rho} \left( T_{\theta+\Delta}(x) - T_\theta(x) \right)^2.$$Lρ,n​(T):=Ex∈{±1}n​E∥Δ∥2​=ρ​(Tθ+Δ​(x)−Tθ​(x))2.

This measures the expected change in the transformer output when the parameters are perturbed by a small vector $\Delta$Δ of radius $\rho$ρ in a random direction. Larger values of $L_{\rho,n}$Lρ,n​ indicate sharper minima. The authors exclude positional encodings from $\theta$θ in this definition because they are often fixed and because their number grows with $n$n, which would complicate comparisons across input lengths.

The key sharpness result states that, when the transformer width $d$d is sufficiently larger than its depth $L$L, small parameter perturbations cause large output changes for functions with high average sensitivity. More precisely,

$$\lim_{\rho \to 0} \liminf_{n \to \infty} L_{\rho,n}(T) \ge \liminf_{n \to \infty} \frac{ \mathrm{as}_n(T_\theta) } { 2n } - L \exp(-\Omega(d)).$$ρ→0lim​n→∞liminf​Lρ,n​(T)≥n→∞liminf​2nasn​(Tθ​)​−Lexp(−Ω(d)).

If the transformer output is Boolean, the constant $2$2 can be removed. The term $L\exp(-\Omega(d))$Lexp(−Ω(d)) becomes negligible when the model is wide relative to its depth, a regime common in practical transformers.

The logical chain is therefore: sensitive functions require high sensitivity in input space; representing such functions either requires large parameter norms or large layer norm blowup; large layer norm blowup makes the output highly vulnerable to small parameter perturbations; therefore the parameter space minima fitting sensitive functions are sharp. This sharpness has practical consequences. Randomly initialized transformers tend to occupy parameter regions with low sensitivity because high sensitivity requires a concentrated region of parameter space. Length generalization also becomes difficult for sensitive functions: even if a minimum exactly represents a length-generalizing solution, arbitrarily small deviations can cause failure on sufficiently long inputs.

The authors also connect the sensitivity framework to Fourier analysis on the Boolean cube. Any function $f: \{\pm 1\}^n \to \mathbb{R}$f:{±1}n→R can be written in the Fourier basis as

$$f(x) = \sum_{P \subseteq \{1,\ldots,n\}} \lambda_P \chi_P(x),$$f(x)=P⊆{1,…,n}∑​λP​χP​(x),

where

$$\chi_P(x) = \prod_{i \in P} x_i.$$χP​(x)=i∈P∏​xi​.

The average sensitivity can be expressed in terms of the Fourier weights:

$$\mathrm{as}_n(f) = \sum_{P \subseteq \{1,\ldots,n\}} \lambda_P^2 |P| = \sum_{i=0}^n i d_i,$$asn​(f)=P⊆{1,…,n}∑​λP2​∣P∣=i=0∑n​idi​,

where $d_i$di​ is the squared weight on degree $i$i monomials. Thus, a low sensitivity bias is equivalent to a bias away from functions whose Fourier mass sits on high degree interactions. This gives a structural explanation for why gradient trained transformers may prefer simple, low degree Boolean functions even when the training set does not explicitly reveal all sensitive perturbations.

Finally, the method treats scratchpad computation as a way to reduce the sensitivity required at each autoregressive step. Instead of asking the transformer to map an entire automaton input directly to the final state, the model can produce a sequence of intermediate states. This transforms a globally sensitive computation into a sequence of locally simple computations. In that setting, each step can have constant sensitivity, which alleviates the sharpness pressure imposed on a single step function. The authors leverage this to explain why intermediate computation can make hard Boolean reasoning problems much more trainable, not merely because it adds expressiveness, but because it lowers the sensitivity burden placed on each computational step.

Experiment

Experiments train PyTorch transformer encoders to compute sequence functions and measure sharpness, parameter norm, and LayerNorm blowup. They confirm that higher-sensitivity functions such as parity produce sharper minima that increase with sequence length, while a tradeoff emerges between parameter norm and logarithmic LayerNorm blowup. Generalizing models tend to prefer low-sensitivity extrapolations with flatter minima, and scratchpad computation of parity avoids sharpness growth by reducing per-step sensitivity. Training dynamics further show that sharpness rises when models enter a steep parity minimum, coinciding with LayerNorm blowup and later parameter-norm reduction.