Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent

• URL: http://arxiv.org/abs/2504.04702v1
• Date: Mon, 07 Apr 2025 03:08:12 GMT
• Title: Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
• Authors: Bo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang,
• Abstract summary: We investigate whether Transformers can truly learn simple majority functions when trained using gradient-based methods.<n>Our analysis demonstrates that even after $mathrmpoly(d)$ gradient queries, the generalization error of the Transformer model still remains substantially large.
• Score: 15.291830857281015
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advancements in Transformer-based architectures have led to impressive breakthroughs in natural language processing tasks, with models such as GPT-4, Claude, and Gemini demonstrating human-level reasoning abilities. However, despite their high performance, concerns remain about the inherent limitations of these models, especially when it comes to learning basic logical functions. While complexity-theoretic analyses indicate that Transformers can represent simple logic functions (e.g., $\mathsf{AND}$, $\mathsf{OR}$, and majority gates) by its nature of belonging to the $\mathsf{TC}^0$ class, these results assume ideal parameter settings and do not account for the constraints imposed by gradient descent-based training methods. In this work, we investigate whether Transformers can truly learn simple majority functions when trained using gradient-based methods. We focus on a simplified variant of the Transformer architecture and consider both $n=\mathrm{poly}(d)$ and $n=\exp(\Omega(d))$ number of training samples, where each sample is a $d$-size binary string paired with the output of a basic majority function. Our analysis demonstrates that even after $\mathrm{poly}(d)$ gradient queries, the generalization error of the Transformer model still remains substantially large, growing exponentially with $d$. This work highlights fundamental optimization challenges in training Transformers for the simplest logical reasoning tasks and provides new insights into their theoretical limitations.

Related papers

• Circuit Complexity Bounds for RoPE-based Transformer Architecture [25.2590541420499]
  Empirical evidence suggests that $mathsfRoPE$-based Transformer architectures demonstrate greater generalization capabilities than conventional Transformer models.<n>We show that unless $mathsfTC0 = mathsfNC1$, a $mathsfRoPE$-based Transformer with $mathrmpoly(n)$-precision, $O(1)$ layers, hidden dimension $d leq O(n)$ cannot solve the Arithmetic formula evaluation problem.
  arXiv  Detail & Related papers  (2024-11-12T07:24:41Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis [63.66763657191476]
  We show that efficient numerical training and inference algorithms as low-rank computation have impressive performance for learning Transformer-based adaption. We analyze how magnitude-based models affect generalization while improving adaption. We conclude that proper magnitude-based has a slight on the testing performance.
  arXiv  Detail & Related papers  (2024-06-24T23:00:58Z)
• Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics [45.69328374321502]
  Auto-regressive large language models (LLMs) show impressive capacities to solve many complex reasoning tasks. LLMs fail to conclude '$B gets A$' during inference even if the two sentences are semantically identical. We theoretically analyze the reversal curse via the training dynamics of gradient descent for two auto-regressive models.
  arXiv  Detail & Related papers  (2024-05-07T21:03:51Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• How do Transformers perform In-Context Autoregressive Learning? [76.18489638049545]
  We train a Transformer model on a simple next token prediction task. We show how a trained Transformer predicts the next token by first learning $W$ in-context, then applying a prediction mapping.
  arXiv  Detail & Related papers  (2024-02-08T16:24:44Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)

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.