REVIEW 7 cited by
Why are Sensitive Functions Hard for Transformers?
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 7 Pith papers
-
When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
Weight-tied looped transformers on group prefix products implement a linear computation frontier whose speed matches the training loop budget, and a new convergence-time instrument reveals it.
-
Can Transformers Really Do It All? On the Compatibility of Inductive Biases Across Tasks
Learned replacement non-linearities show transformers are rarely optimal for algorithmic tasks, with benefits that are task-specific, while language/code gains are smaller and more transferable.
-
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Embedding a narrow C-RASP teacher into a wider quantized Transformer yields sample complexity O((L d log Q)/ε) under posterior sampling of zero-training-error models.
-
Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.
-
Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
For diagonal state space models, parity cannot be solved by combining input-dependent non-negative layers (Mamba) with input-independent negative-eigenvalue layers (S4D); a single layer needs both properties.
-
Rethinking Memorization Measures and their Implications in Large Language Models
Contextual memorization, defined by comparing a string's training loss against the best loss without training on that string, is stricter than counterfactual memorization and suggests that zero-memorization optimal le...
-
Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
With teacher forcing that reveals pairwise products of the relevant bits, one gradient step lets a single-head attention recover the support of a k-bit AND/OR; the paper's claimed end-to-end hardness lower bound is in...
Discussion (0). Continue with ORCID to comment.