Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

• URL: http://arxiv.org/abs/2606.08768v1
• Date: Sun, 07 Jun 2026 18:16:56 GMT
• Title: Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
• Abstract summary: We study the geometry of transformers' parameter space.<n>We prove that randomly compute functions which have low-sensitivity strings is provably unlearnable.
• Score: 85.5290722026859
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is particularly prominent for sensitive functions -- functions whose output is likely to change if a single bit of the input is flipped -- for example, PARITY. While prior work has established that transformers exhibit a bias toward functions with low average sensitivity, the precise mechanism underlying this bias remains poorly understood. To shed light on this phenomenon, we study the geometry of transformers' parameter space. We show that sensitive functions -- even when representable -- occupy a vanishingly small region that random initialization is very likely to miss. Specifically, we shift the focus from average sensitivity to the full sensitivity profile -- the distribution of sensitivity values across all inputs -- and prove that randomly initialized transformers almost surely compute functions which have low-sensitivity strings. Consequently, any function that lacks such strings is provably unlearnable.

Related papers

• Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
  We find that padded $textL$ constantprecision transformers are surprisingly robust to expressivity.<n>$logd-looped constant-precision transformers reach $textFO-uniform TCd$, and growing-precision ones reach $textFO-uniform TCd$.
  arXiv  Detail & Related papers  (2026-05-28T19:58:43Z)
• Trapped by simplicity: When Transformers fail to learn from noisy features [0.0]
  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?<n>We find that transformers typically fail at noise-robust learning of random $k$-juntas, especially when the sensitivity of the optimal solution is smaller than that of the target function.
  arXiv  Detail & Related papers  (2026-02-09T14:14:39Z)
• Provable In-Context Learning of Nonlinear Regression with Transformers [66.99048542127768]
  In-context learning (ICL) is the ability to perform unseen tasks using task specific prompts without updating parameters.<n>Recent research has actively explored the training dynamics behind ICL, with much of the focus on relatively simple tasks.<n>This paper investigates more complex nonlinear regression tasks, aiming to uncover how transformers acquire in-context learning capabilities.
  arXiv  Detail & Related papers  (2025-07-28T00:09:28Z)
• Are Transformers in Pre-trained LM A Good ASR Encoder? An Empirical Study [52.91899050612153]
  transformers within pre-trained language models (PLMs) when repurposed as encoders for Automatic Speech Recognition (ASR) Our findings reveal a notable improvement in Character Error Rate (CER) and Word Error Rate (WER) across diverse ASR tasks when transformers from pre-trained LMs are incorporated. This underscores the potential of leveraging the semantic prowess embedded within pre-trained transformers to advance ASR systems' capabilities.
  arXiv  Detail & Related papers  (2024-09-26T11:31:18Z)
• Transformers Learn Low Sensitivity Functions: Investigations and Implications [18.77893015276986]
  Transformers achieve state-of-the-art accuracy and robustness across many tasks.<n>We identify the sensitivity of the model to token-wise random perturbations in the input as a unified metric.<n>We show that transformers have lower sensitivity than CNNs, CNNs, ConvMixers and LSTMs, across both vision and language tasks.
  arXiv  Detail & Related papers  (2024-03-11T17:12:09Z)
• Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input [50.83356836818667]
  We study the approximation and estimation ability of Transformers as sequence-to-sequence functions with infinite dimensional inputs. Our theoretical results support the practical success of Transformers for high dimensional data.
  arXiv  Detail & Related papers  (2023-05-30T02:44:49Z)
• Mapping of attention mechanisms to a generalized Potts model [50.91742043564049]
  We show that training a neural network is exactly equivalent to solving the inverse Potts problem by the so-called pseudo-likelihood method. We also compute the generalization error of self-attention in a model scenario analytically using the replica method.
  arXiv  Detail & Related papers  (2023-04-14T16:32:56Z)
• Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions [29.461559919821802]
  Recent works have found that Transformers struggle to model several formal languages when compared to recurrent models. This raises the question of why Transformers perform well in practice and whether they have any properties that enable them to generalize better than recurrent models.
  arXiv  Detail & Related papers  (2022-11-22T15:10:48Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  We mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. We present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. We develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions.
  arXiv  Detail & Related papers  (2022-05-26T14:51:30Z)
• Differentiable Subset Pruning of Transformer Heads [71.7904179689271]
  We introduce a new head pruning technique that we term differentiable subset pruning. We show that differentiable subset pruning performs comparably or better than previous works while offering precise control of the sparsity level.
  arXiv  Detail & Related papers  (2021-08-10T13:08:34Z)
• Sensitivity as a Complexity Measure for Sequence Classification Tasks [24.246784593571626]
  We argue that standard sequence classification methods are biased towards learning low-sensitivity functions, so that tasks requiring high sensitivity are more difficult. We estimate sensitivity on 15 NLP tasks, finding that sensitivity is higher on challenging tasks collected in GLUE than on simple text classification tasks.
  arXiv  Detail & Related papers  (2021-04-21T03:56:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.