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

arXiv: https://arxiv.org/abs/2504.04702 · HTML: https://mlsanity.com/paper/2504.04702/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 7 Apr 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [How Good Are GPT Models at Machine Translation? A Comprehensive Evaluation](https://mlsanity.com/paper/2302.09210/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Adapted Large Language Models Can Outperform Medical Experts in Clinical Text Summarization](https://mlsanity.com/paper/2309.07430/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Learning-to-Cache: Accelerating Diffusion Transformer via Layer Caching](https://mlsanity.com/paper/2406.01733/) (2024)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [The Best of Both Worlds: Combining Recent Advances in Neural Machine Translation](https://mlsanity.com/paper/1804.09849/) (2018)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [Transformers Provably Solve Parity Efficiently with Chain of Thought](https://mlsanity.com/paper/2410.08633/) (2024)
- [Mitigating Object Hallucination via Concentric Causal Attention](https://mlsanity.com/paper/2410.15926/) (2024)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [VALHALLA: Visual Hallucination for Machine Translation](https://mlsanity.com/paper/2206.00100/) (2022)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent](https://mlsanity.com/paper/2410.11268/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [What is my math transformer doing? -- Three results on interpretability and generalization](https://mlsanity.com/paper/2211.00170/) (2022)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective](https://mlsanity.com/paper/2501.06444/) (2025)
- [On the Comparison between Multi-modal and Single-modal Contrastive Learning](https://mlsanity.com/paper/2411.02837/) (2024)
- [Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problems](https://mlsanity.com/paper/2412.05562/) (2024)

## Built on by (most cited first, 8 of 8)

- [T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generation](https://mlsanity.com/paper/2507.18107/) (2025)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models](https://mlsanity.com/paper/2505.04946/) (2025)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)
- [SciDocBench: A Workflow-Centered Benchmark and Data Pipeline for Scientific Document Understanding](https://mlsanity.com/paper/2609.05141/) (2026)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)

## Abstract (arXiv)

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., mathsfAND, mathsfOR, and majority gates) by its nature of belonging to the mathsfTC0 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=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 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.