Back

Why are Sensitive Functions Hard for Transformers?

Michael HahnMark Rofin

article2024ACL58 citationsBest Paper Award

Proves that transformers computing highly sensitive functions occupy extremely sharp, isolated parameter regions, mathematically explaining why these models inherently struggle to learn and generalize functions like PARITY despite having the expressive capacity to represent them.

Listen

Modern artificial intelligence heavily relies on the transformer architecture, yet these models consistently struggle to learn certain simple logical tasks, such as determining the parity of a bit string. While classical recurrent models solve parity easily, transformers fail to learn it reliably or generalize it to longer sequences. Previous theoretical research has produced a confusing contradiction: purely expressive models suggest transformers can easily represent parity in principle, whereas alternative mathematical bounds underpredict their ability to learn simple sparse patterns. Consequently, technical leaders and researchers lack a rigorous explanation for the fundamental learning biases and failure modes of transformer models.

The article establishes a unified theoretical framework explaining why sensitive functions—where changing a single input bit alters the overall output—are fundamentally difficult for transformers to learn. The authors evaluate the mathematical properties of transformer architectures with layer normalization and validate their findings through empirical experiments measuring loss landscape geometry, model parameter sensitivity, and training behavior across various boolean functions.

The investigation proves mathematically and confirms experimentally that fitting a highly sensitive function forces a transformer to occupy extremely sharp, brittle minima in its loss landscape. First, representing high-sensitivity functions requires an unavoidable mathematical trade-off between growing parameter norms and exploding layer normalization factors as input sequence lengths increase. Second, the authors prove that any transformer achieving high input sensitivity becomes excessively sensitive to tiny parameter perturbations; moving even slightly away from an optimal configuration causes severe performance collapse on long inputs. Empirically, training transformers on the parity function demonstrated a dramatic increase in loss sharpness as sequence length grew, exhibiting a regression slope roughly two orders of magnitude steeper than less sensitive functions like majority or sparse selection. Finally, breaking sensitive tasks into multi-step autoregressive scratchpad generation reduces step-level sensitivity to a small constant, completely eliminating this sharpness penalty.

These findings provide clear strategic implications for deploying transformers in complex reasoning domains. The core bottleneck is not representational capacity, but optimization geometry: standard gradient descent inherently prefers broad, flat minima, creating a natural architectural bias toward low-sensitivity and low-degree solutions. This explains why transformers struggle with length generalization on brittle, sensitive tasks when forced to answer in a single forward pass. Expecting a standard transformer encoder to solve highly sensitive global logic in one step introduces severe reliability risks and training failure.

Organizations developing machine learning systems should avoid relying on single-pass transformer architectures for high-sensitivity logical reasoning. Instead, teams should implement chain-of-thought prompting, scratchpads, or recurrent autoregressive generation to decompose sensitive tasks into low-sensitivity intermediate steps. Future technical efforts should prioritize developing quantitative finite-length bounds, investigating sequence-to-sequence transductions, and analyzing causal decoder architectures under this geometric framework.

While the theoretical proofs are asymptotic and focus on single-output boolean tasks within bounded-depth transformer encoders, the conclusions remain highly robust. The theoretical bounds closely match empirical observations across synthetic benchmark tasks, giving high confidence that optimization landscape sharpness is the primary driver of transformers' sensitivity limitations.

Saarland Informatics CampusSaarland Universityencoder-decodersub-arraysformal semanticssensitive functionslog-precision transformerssensitivity bounds
arXiv: 2402.09963lacoco-lab/sensitivity-hardness

No sufficiently relevant recommendations were found.

Cover for Why are Sensitive Functions Hard for Transformers?

Abstract

Empirical studies have identified a range of learnability biases and limitations of transformers, such as a persistent difficulty in learning to compute simple formal languages such as PARITY, and a bias towards low-degree functions. However, theoretical understanding remains limited, with existing expressiveness theory either overpredicting or underpredicting realistic learning abilities. We prove that, under the transformer architecture, the loss landscape is constrained by the input-space sensitivity: Transformers whose output is sensitive to many parts of the input string inhabit isolated points in parameter space, leading to a low-sensitivity bias in generalization. We show theoretically and empirically that this theory unifies a broad array of empirical observations about the learning abilities and biases of transformers, such as their generalization bias towards low sensitivity and low degree, and difficulty in length generalization for PARITY. This shows that understanding transformers' inductive biases requires studying not just their in-principle expressivity, but also their loss landscape.

Topics

encoder-decodersub-arraysformal semanticsparity bits

Keywords

sensitive functionslog-precision transformerssensitivity boundslow-sensitivity biasinput-space sensitivityFourier-Walsh transformcircuit complexitysharpness-aware minimizationpositional encodingsexpressive capacity

Table of Contents

  • 1 Introduction
  • 2 Model of Transformers
  • 3 Average Sensitivity
  • 4 Lower Bounds for Sensitive Functions
  • 5 Sensitive Transformers are Brittle
  • 6 Implications
  • 7 Experiments
  • 7.1 Setup
  • 7.2 Results
  • 8 Discussion
  • 9 Conclusion
  • Limitations
  • Acknowledgments
  • References
  • A Simple Constructions for PARITY
  • B Proof of Theorem 4 and Corollary 5
  • B.1 Bounding the Sensitivity of the Attention Heads
  • B.2 Impact of Layer Norm
  • B.3 Layerwise Bounds on Sensitivity
  • B.4 Relating Influence at First and Last Layers
  • B.5 Deriving Almost-Everywhere Pointwise Sensitivity Bounds
  • B.6 Deriving On-Average Sensitivity Bounds
  • C Theorem 6
  • D Theorem 7
  • E Further Experimental Results
  • E.1 The Details of Experimental Setup
  • E.2 Results

Knowls

  1. Knowl 1 — High input sensitivity forces sharp parameter-space minima

    theoretical result

    Let TθT_\theta be a transformer with LL layers and hidden dimension d>12Ld>12L, whose scalar predictions satisfy Tθ(x)∈[−1,1]T_\theta(x)\in[-1,1] for every bitstring x∈{−1,1}nx\in\{-1,1\}^n. Let θ\theta contain the model parameters other than positional encodings, and define its average directional sharpness at perturbation radius ρ\rho by

    Lρ,n(Tθ)=Ex∼Unif({−1,1}n) E∥Δ∥2=ρ[(Tθ+Δ(x)−Tθ(x))2],\mathcal{L}_{\rho,n}(T_\theta)=\mathbb{E}_{x\sim\mathrm{Unif}(\{-1,1\}^n)}\,\mathbb{E}_{\|\Delta\|_2=\rho}\left[(T_{\theta+\Delta}(x)-T_\theta(x))^2\right],

    where Δ\Delta is uniform on the radius-ρ\rho sphere in parameter space. If as⁡n(Tθ)\operatorname{as}_n(T_\theta) is the average sensitivity of the function computed on length-nn inputs, then

    lim⁡ρ→0lim inf⁡n→∞Lρ,n(Tθ)≥lim inf⁡n→∞as⁡n(Tθ)2n−Lexp⁡(−Ω(d)).\lim_{\rho\to0}\liminf_{n\to\infty}\mathcal{L}_{\rho,n}(T_\theta) \geq \liminf_{n\to\infty}\frac{\operatorname{as}_n(T_\theta)}{2n}-L\exp(-\Omega(d)).

    The term Ω(d)\Omega(d) grows positively with dd. If the transformer outputs only {−1,1}\{-1,1\}, the factor 22 in the sensitivity denominator can be removed. Thus, when sensitivity is proportional to input length, arbitrarily small random parameter perturbations still produce a nonvanishing expected prediction change on sufficiently long inputs. For PARITY, whose sensitivity is nn, the lower bound approaches 11 for Boolean outputs at large width. The result also applies to transformer families whose weights depend on nn if the parameter-dependent constant in the sensitivity bounds remains bounded. Positional encodings are excluded from the perturbed parameter vector.

  2. Knowl 2 — Average sensitivity requires parameter size or layer-normalization amplification

    theoretical result

    For a transformer on inputs x∈{−1,1}nx\in\{-1,1\}^n, let Yw(k)(x)Y_w^{(k)}(x) be the pre-normalization activation at position ww in layer kk, and let ε≥0\varepsilon\geq0 be the layer-normalization stabilizer. Define the normalization factor, maximum per-layer amplification, and total amplification by

    Nw(k)(x)=1Var⁡(Yw(k)(x))+ε,τ(k)(x)=max⁡1≤w≤n(1+Nw(k)(x)),Blowup⁡(x)=∏k=1Lτ(k)(x).N_w^{(k)}(x)=\frac{1}{\sqrt{\operatorname{Var}(Y_w^{(k)}(x))+\varepsilon}},\qquad \tau^{(k)}(x)=\max_{1\leq w\leq n}\bigl(1+N_w^{(k)}(x)\bigr),\qquad \operatorname{Blowup}(x)=\prod_{k=1}^{L}\tau^{(k)}(x).

    Here variance is computed across the hidden coordinates, and LL is the number of layers. There is a parameter- and architecture-dependent constant CC such that

    C Ex∼Unif({−1,1}n)[Blowup⁡(x)2]≥as⁡n(f)nlog⁡n−Hn,C\,\mathbb{E}_{x\sim\mathrm{Unif}(\{-1,1\}^n)}[\operatorname{Blowup}(x)^2] \geq \frac{\operatorname{as}_n(f)}{\sqrt{n\log n}}-\frac{H}{n},

    where ff is the function computed by the transformer and HH is its number of attention heads. The constant CC includes an exponential factor exp⁡ ⁣(4dmax⁡h∑k=2L∥Kk,hTQk,h∥2)\exp\!\left(4d\max_h\sum_{k=2}^{L}\|K_{k,h}^{T}Q_{k,h}\|_2\right) and a polynomial factor in width, number of heads, parameter-matrix norms, and embedding norms; dd is the hidden dimension and Kk,h,Qk,hK_{k,h},Q_{k,h} are the key and query matrices. Consequently, for fixed parameters representing PARITY, the expected squared blowup must grow at least on the order of n/log⁡n\sqrt{n/\log n}, whereas this bound does not force growing average blowup for functions with sensitivity such as FIRST's constant sensitivity or MAJORITY's Θ(n)\Theta(\sqrt n) sensitivity.

  3. Knowl 3 — Pointwise sensitivity is controlled by normalization on an input and its neighbors

    theoretical result

    For a transformer on {−1,1}n\{-1,1\}^n, define the input-specific sensitivity of its scalar output ff as s(x,f)=14∑i=1n∣f(x)−f(x⊕i)∣2s(x,f)=\frac14\sum_{i=1}^{n}|f(x)-f(x^{\oplus i})|^2, where x⊕ix^{\oplus i} flips bit ii. Let Blowup⁡(x)\operatorname{Blowup}(x) be the product across layers of the maximum, over token positions, of one plus the layer-normalization factor Nw(k)(x)=1/Var⁡(Yw(k)(x))+εN_w^{(k)}(x)=1/\sqrt{\operatorname{Var}(Y_w^{(k)}(x))+\varepsilon}; Yw(k)Y_w^{(k)} is the pre-normalization activation and ε≥0\varepsilon\geq0. For a transformer with HH heads, there is a parameter-dependent constant CC such that, for a uniformly random input xx, with probability at least 1−H/n21-H/n^2,

    s(x,f)Cnlog⁡n≤Blowup⁡(x)2+1n∑i=1nBlowup⁡(x⊕i)2.\frac{s(x,f)}{C\sqrt{n\log n}} \leq \operatorname{Blowup}(x)^2+\frac1n\sum_{i=1}^{n}\operatorname{Blowup}(x^{\oplus i})^2.

    This high-probability bound relates sensitivity at a typical input to normalization amplification both at that input and across its Hamming neighbors; it is not asserted pointwise for every input.

  4. Knowl 4 — Average sensitivity summarizes the Fourier degree profile

    definition

    For a real-valued function f:{−1,1}n→Rf:\{-1,1\}^n\to\mathbb{R}, define its sensitivity at input xx and its average sensitivity at length nn by

    s(x,f)=14∑i=1n∣f(x)−f(x⊕i)∣2,as⁡n(f)=2−n∑x∈{−1,1}ns(x,f),s(x,f)=\frac14\sum_{i=1}^{n}\left|f(x)-f(x^{\oplus i})\right|^2, \qquad \operatorname{as}_n(f)=2^{-n}\sum_{x\in\{-1,1\}^n}s(x,f),

    where x⊕ix^{\oplus i} is xx with bit ii flipped. If ff is Boolean-valued, s(x,f)s(x,f) counts the Hamming neighbors on which the output flips. Write the Fourier-Walsh expansion as f(x)=∑P⊆[n]λPχP(x)f(x)=\sum_{P\subseteq[n]}\lambda_P\chi_P(x), with χP(x)=∏i∈Pxi\chi_P(x)=\prod_{i\in P}x_i, and define degree-profile entries dj=∑∣P∣=jλP2d_j=\sum_{|P|=j}\lambda_P^2. Then

    as⁡n(f)=∑P⊆[n]λP2∣P∣=∑j=0nj dj.\operatorname{as}_n(f)=\sum_{P\subseteq[n]}\lambda_P^2|P|=\sum_{j=0}^{n}j\,d_j.

    Thus average sensitivity is the degree-weighted total Fourier mass: substantial mass on degrees proportional to nn implies sensitivity proportional to nn. This identity lets the paper's sensitivity-based transformer results also constrain the degree profiles of functions that transformers represent.

  5. Knowl 5 — Transformer architecture analyzed by the theory

    model/method

    The theoretical model takes a bitstring x∈{−1,1}nx\in\{-1,1\}^n, embeds each bit with a learned word embedding e(xi)∈Rde(x_i)\in\mathbb{R}^d, and adds a positional encoding pi∈Rdp_i\in\mathbb{R}^d, giving yi(0)=e(xi)+piy_i^{(0)}=e(x_i)+p_i. In layer kk, attention head hh uses learned query, key, and value matrices Qk,h,Kk,h,Vk,h∈Rd×dQ_{k,h},K_{k,h},V_{k,h}\in\mathbb{R}^{d\times d}. For positions i,j∈{1,…,n}i,j\in\{1,\ldots,n\}, its attention weight and output are

    αi,j(k,h)=exp⁡ ⁣((Kk,hyj(k−1))TQk,hyi(k−1))∑r=1nexp⁡ ⁣((Kk,hyr(k−1))TQk,hyi(k−1)),bi,h(k)=∑j=1nαi,j(k,h)Vk,hyj(k−1).\alpha_{i,j}^{(k,h)}= \frac{\exp\!\left((K_{k,h}y_j^{(k-1)})^TQ_{k,h}y_i^{(k-1)}\right)} {\sum_{r=1}^{n}\exp\!\left((K_{k,h}y_r^{(k-1)})^TQ_{k,h}y_i^{(k-1)}\right)}, \qquad b_{i,h}^{(k)}=\sum_{j=1}^{n}\alpha_{i,j}^{(k,h)}V_{k,h}y_j^{(k-1)}.

    The heads are combined with the residual activation and passed through a one-layer MLP, producing the pre-normalization activation Yi(k)=fMLP ⁣(yi(k−1)+∑h=1Hbi,h(k))Y_i^{(k)}=f_{\mathrm{MLP}}\!\left(y_i^{(k-1)}+\sum_{h=1}^{H}b_{i,h}^{(k)}\right). Layer normalization is applied as yi(k)=(Yi(k)−mean⁡(Yi(k)))/Var⁡(Yi(k))+εy_i^{(k)}=(Y_i^{(k)}-\operatorname{mean}(Y_i^{(k)}))/\sqrt{\operatorname{Var}(Y_i^{(k)})+\varepsilon}, with ε≥0\varepsilon\geq0. A scalar prediction is read from the final position: T(x)=voutTyn(L)T(x)=v_{\mathrm{out}}^T y_n^{(L)}, where vout∈Rdv_{\mathrm{out}}\in\mathbb{R}^d. The analysis assumes a fixed number of layers and at least one application of layer normalization; positional encodings are not included among the parameters perturbed in the sharpness result.

  6. Knowl 6 — Sharpness rises much faster with length for PARITY than for lower-sensitivity functions

    empirical result

    Transformers were trained to fit PARITY, MAJORITY, FIRST, and MEAN at sequence lengths n=4n=4 through 3030, with 10 random initializations per function and length. The encoder used hidden dimension 128, two layers, and two attention heads; AdamW training used learning rate 0.00030.0003, weight decay 0.10.1, batch size 1024, and 10,000 steps. Runs with evaluation MSE above 10−310^{-3} were excluded. Sharpness was estimated from prediction changes under Gaussian parameter perturbations with standard deviation 0.020.02 and rescaled for the experiments' {0,1}\{0,1\} outputs. The page-1 plot shows the sharpness curve increasing strongly for PARITY while remaining comparatively low for MAJORITY; the regression summary on page 28 quantifies the length-sharpness relationships over n∈[4,30]n\in[4,30]:

    Function Regression slope Pearson correlation pp-value (H0H_0: slope =0=0)
    PARITY 5.0⋅10−25.0\cdot10^{-2} 0.880.88 6⋅10−726\cdot10^{-72}
    MAJORITY 1.8⋅10−31.8\cdot10^{-3} 0.670.67 2⋅10−362\cdot10^{-36}
    FIRST 6.4⋅10−56.4\cdot10^{-5} 0.160.16 0.00750.0075
    MEAN −1.9⋅10−5-1.9\cdot10^{-5} −0.07-0.07 0.220.22

    The PARITY slope is about two orders of magnitude larger than MAJORITY's. FIRST has a statistically significant but very small fitted slope, while the MEAN relationship is not statistically significant at the reported pp-value. These observations match the theory's prediction that the sharpness cost is strongest when average sensitivity grows linearly with input length.

  7. Knowl 7 — Transformers generalize random Boolean functions toward lower sensitivity

    empirical result

    To test the sensitivity bias in generalization, the authors sampled 10 random Boolean functions f:{−1,1}10→{−1,1}f:\{-1,1\}^{10}\to\{-1,1\} and, for each function, random training subsets of sizes 128, 256, or 512. A transformer trained on each subset was evaluated on all 210=10242^{10}=1024 inputs to define its extrapolated function. These extrapolated functions had lower average sensitivity than their source random functions; the reduction was larger for smaller training sets. To compare minima, new transformers were trained on the full input domain to fit both each original random function and its extrapolated function. Across 10 random functions, 10 training sets per function and training size, and 5 refits per extrapolated function, models fitting the extrapolated functions had lower sharpness than models fitting the original functions. The page-8 scatterplot visualizes the association: the smaller-training-set groups lie at lower average sensitivity and lower sharpness. The paper also reports that sharpness measured only on the training examples closely tracked sharpness measured over the full domain.

  8. Knowl 8 — Parameter norm and layer-normalization blowup trade off when fitting functions

    empirical result

    The authors measured parameter norm (excluding positional-encoding matrices) and layer-normalization blowup for trained transformers. Experimental blowup was the product across normalization applications of the maximum normalization factor over token positions. To obtain varied solutions, they swept weight decay uniformly from 0 to 0.4 and learning rate from 0.0001 to 0.0005 while varying sequence length. Across PARITY, MAJORITY, FIRST, and MEAN, the plotted solutions show an inverse, approximately log-linear tradeoff: models with larger parameter norms can use less normalization blowup, and vice versa. For PARITY, the tradeoff shifts with input length: at a fixed blowup, longer inputs require larger parameter norm, or at a fixed norm, larger blowup. This length shift is not visible for the lower-sensitivity functions over the tested range. The page-32 plots display the function-wise tradeoffs, and the page-33 comparisons show the increasing separation of PARITY solutions at longer lengths. The result is an experimental counterpart to the theoretical requirement that sensitive functions incur parameter-dependent cost, normalization amplification, or both.

  9. Knowl 9 — An autoregressive scratchpad keeps automaton-step sensitivity bounded

    theoretical result

    Consider a fixed finite automaton with finite alphabet Σ\Sigma, state set XX, and transition rule T:X×Σ→XT:X\times\Sigma\to X. In direct computation, the final state is produced from the whole input string in one output. With a scratchpad, the model instead emits the successive states t1,…,tNt_1,\ldots,t_N autoregressively, where each step computes ti+1=T(ti,xi+1)t_{i+1}=T(t_i,x_{i+1}) from the previous state and next input symbol. If symbols and states use fixed-length encodings, each step's output depends only on a bounded number of encoded input bits, with the bound depending on the fixed automaton rather than total sequence length NN. Consequently, the sensitivity of each autoregressive step is O(1)O(1), independent of NN. This gives a sensitivity-based account of why decomposing a globally sensitive computation into intermediate state updates can avoid the sharpness lower bound that applies to a single output computing the whole function.

  10. Knowl 10 — Scratchpad PARITY has low sharpness even at long lengths

    empirical result

    An encoder-decoder transformer was trained to emit the parity of each input prefix at the corresponding autoregressive step: ti=PARITY⁡(x1:i)t_i=\operatorname{PARITY}(x_{1:i}), updated from xix_i and ti−1t_{i-1}. The model had hidden dimension 32, two layers, and two attention heads per block. Sharpness was measured by parameter perturbations as in the other experiments. Across tested sequence lengths extending to roughly 300 bits, sharpness stayed low and showed no clear increasing trend with length. The page-33 plot displays this near-flat pattern. This complements the bounded per-step sensitivity result: the scratchpad changes the computation into a sequence of locally sensitive updates rather than a single highly sensitive parity prediction.

Coverage note — The auxiliary construction expressing PARITY through nested majority and position comparisons, and the time-resolved plots of PARITY training dynamics, are omitted because they support the expressivity-gap framing and proposed mechanism rather than adding a comparably central result. The paper's stated limitations—long-input asymptotics, scalar-output functions, encoder-only theory, and no direct theorem about training dynamics—are reflected in the scope of the knowls rather than listed as separate contributions.

References

  1. 1.Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. 2023. Generalization on the unseen, logic reasoning and degree curriculum. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31–60. PMLR.
  2. 2.Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. 2023. Linear attention is (maybe) all you need (to understand transformer optimization).
  3. 3.Maksym Andriushchenko, Francesco Croce, Maximilian Müller, Matthias Hein, and Nicolas Flammarion. 2023. A modern look at the relationship between sharpness and generalization. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 840–902. PMLR.
  4. 4.Dana Angluin, David Chiang, and Andy Yang. 2023. Masked hard-attention transformers and boolean rasp recognize exactly the star-free languages. arXiv preprint arXiv:2310.13897.
  5. 5.Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35:38546–38556.
  6. 6.Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. CoRR, abs/1607.06450.
  7. 7.Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 7096–7116. Association for Computational Linguistics.
  8. 8.Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. 2023. Simplicity bias in transformers and their ability to learn sparse boolean functions. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023, pages 5767–5791. Association for Computational Linguistics.
  9. 9.David Chiang and Peter Cholak. 2022. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 7654–7664. Association for Computational Linguistics.
  10. 10.David Chiang, Peter Cholak, and Anand Pillay. 2023. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5544–5562. PMLR.
  11. 11.Alex Damian, Eshaan Nichani, and Jason D. Lee. 2023. Self-stabilization: The implicit bias of gradient descent at the edge of stability. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
  12. 12.Ronald De Wolf. 2008. A brief introduction to fourier analysis on the boolean cube. Theory of Computing, pages 1–20.
  13. 13.Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023. Neural networks and the chomsky hierarchy.
  14. 14.Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. 2022. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, pages 5793–5831. PMLR.
  15. 15.Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Thirty-seventh Conference on Neural Information Processing Systems.
  16. 16.Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. 2020. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412.
  17. 17.Sara Fridovich-Keil, Raphael Gontijo Lopes, and Rebecca Roelofs. 2022. Spectral bias in practice: The role of function frequency in generalization. In Advances in Neural Information Processing Systems, volume 35, pages 7368–7382. Curran Associates, Inc.
  18. 18.Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171.
  19. 19.Michael Hahn, Dan Jurafsky, and Richard Futrell. 2021. Sensitivity as a complexity measure for sequence classification tasks. Transactions of the Association for Computational Linguistics, 9:891–908.
  20. 20.Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800–810.
  21. 21.Johan Håstad. 1986. Computational limitations for small depth circuits. Ph.D. thesis, Massachusetts Institute of Technology.
  22. 22.Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. 2010. Variations on the sensitivity conjecture. Theory of Computing, 4:1–27.
  23. 23.Yiding Jiang, Behnam Neyshabur*, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. 2020. Fantastic generalization measures and where to find them. In International Conference on Learning Representations.
  24. 24.Stasys Jukna. 2012. Boolean Function Complexity: Advances and Frontiers.
  25. 25.J. Kahn, G. Kalai, and N. Linial. 1988. The influence of variables on boolean functions. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 68–80.
  26. 26.Simran Kaur, Jeremy Cohen, and Zachary Chase Lipton. 2023. On the maximum hessian eigenvalue and generalization. In Proceedings on, pages 51–65. PMLR.
  27. 27.Shengqiao Li. 2010. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics & Statistics, 4(1):66–70.
  28. 28.Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. 2023. Transformers as algorithms: Generalization and stability in in-context learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19565–19594. PMLR.
  29. 29.Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations.
  30. 30.Ilya Loshchilov and Frank Hutter. 2017. Decoupled weight decay regularization. In International Conference on Learning Representations.
  31. 31.William Merrill and Ashish Sabharwal. 2023a. The expressive power of transformers with chain of thought. In NeurIPS 2023 Workshop on Mathematics of Modern Machine Learning.
  32. 32.William Merrill and Ashish Sabharwal. 2023b. A logic for expressing log-precision transformers. In Thirty-seventh Conference on Neural Information Processing Systems.
  33. 33.William Merrill and Ashish Sabharwal. 2023c. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545.
  34. 34.William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022. Saturated transformers are constant-depth threshold circuits. Trans. Assoc. Comput. Linguistics, 10:843–856.
  35. 35.Ryan O’Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press.
  36. 36.Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  37. 37.Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. 2019. On the spectral bias of neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5301–5310. PMLR.
  38. 38.Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. 2023. Randomized positional encodings boost length generalization of transformers.
  39. 39.Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2023. Representational strengths and limitations of transformers. CoRR, abs/2306.02896.
  40. 40.Lena Strobl. 2023. Average-hard attention transformers are constant-depth uniform threshold circuits. CoRR, abs/2308.03212.
  41. 41.Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2023. Transformers as recognizers of formal languages: A survey on expressivity. CoRR, abs/2311.00208.
  42. 42.Sho Takase, Shun Kiyono, Sosuke Kobayashi, and Jun Suzuki. 2022. On layer normalizations and residual connections in transformers. arXiv preprint arXiv:2206.00330.
  43. 43.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008.
  44. 44.Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In International Conference on Machine Learning, pages 11080–11090. PMLR.
  45. 45.Kaiyue Wen, Tengyu Ma, and Zhiyuan Li. 2022. How does sharpness-aware minimization minimize sharpness? CoRR, abs/2211.05729.
  46. 46.Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). Association for Computational Linguistics.
  47. 47.Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2019. Are transformers universal approximators of sequence-to-sequence functions?
  48. 48.Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. 2023. What algorithms can transformers learn? a study in length generalization. arXiv preprint arXiv:2310.16028.

Citation

MLA
Hahn, M., and M. Rofin. “Why Are Sensitive Functions Hard for Transformers?”. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2024, pp. 14973–5008, https://doi.org/10.18653/v1/2024.acl-long.800.
APA
Hahn, M., & Rofin, M. (2024). Why are Sensitive Functions Hard for Transformers?. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 14973–15008. https://doi.org/10.18653/v1/2024.acl-long.800
Chicago
Hahn, M., and M. Rofin. 2024. “Why Are Sensitive Functions Hard for Transformers?”. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 14973–15008. https://doi.org/10.18653/v1/2024.acl-long.800.
Harvard
Hahn, M. and Rofin, M. (2024) “Why are Sensitive Functions Hard for Transformers?”, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pp. 14973–15008. Available at: https://doi.org/10.18653/v1/2024.acl-long.800.
Vancouver
1. Hahn M, Rofin M (2024) Why are Sensitive Functions Hard for Transformers?. In: Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, pp 14973–15008

BibTeX

@inproceedings{hahn-rofin-2024-sensitive,
    title = "Why are Sensitive Functions Hard for Transformers?",
    author = "Hahn, Michael  and
      Rofin, Mark",
    editor = "Ku, Lun-Wei  and
      Martins, Andre  and
      Srikumar, Vivek",
    booktitle = "Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    month = aug,
    year = "2024",
    address = "Bangkok, Thailand",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2024.acl-long.800/",
    doi = "10.18653/v1/2024.acl-long.800",
    pages = "14973--15008"
}
Metadata:ACL Anthology

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/