mlsanityData to 14 Oct 2026

Minimalist Softmax Attention Provably Learns Constrained Boolean Functions

arXiv 2505.19531 ↗First posted 26 May 2025cs.LG cs.AI stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the computational limits of learning k-bit Boolean functions (specifically, AND, OR, and their noisy variants), using a minimalist single-head softmax-attention mechanism, where k=Theta(d) relevant bits are selected from d inputs. We show that these simple AND and OR functions are unsolvable with a single-head softmax-attention mechanism alone. However, with teacher forcing, the same minimalist attention is capable of solving them. These findings offer two key insights: Architecturally, solving these Boolean tasks requires only minimalist attention, without deep Transformer blocks or FFNs. Methodologically, one gradient descent update with supervision suffices and replaces the multi-step Chain-of-Thought (CoT) reasoning scheme of [Kim and Suzuki, ICLR 2025] for solving Boolean problems. Together, the bounds expose a fundamental gap between what this minimal architecture achieves under ideal supervision and what is provably impossible under standard training.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 36 of its 53 references that are in the map. First posted on arXiv 26 May 2025.

Builds on

36 of 53 references.

References · 36

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  6. 2022Photorealistic Text-to-Image Diffusion Models with Deep Language Understandingcited by 6,355
  7. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  8. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  9. 2022Large Language Models Encode Clinical Knowledgecited by 1,830
  10. 2022Tune-A-Video: One-Shot Tuning of Image Diffusion Models for Text-to-Video Generationcited by 961
  11. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  12. 2024Omni-MATH: A Universal Olympiad Level Mathematic Benchmark For Large Language Modelscited by 284
24 more
  1. 2022Transformers Learn Shortcuts to Automatacited by 268
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  3. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 170
  4. 2023DNABERT-2: Efficient Foundation Model and Benchmark For Multi-Species Genomecited by 143
  5. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  6. 2023In-Context Convergence of Transformerscited by 115
  7. 2023Fast Attention Requires Bounded Entriescited by 102
  8. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  9. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 50
  10. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  11. 2024Transformers Learn Nonlinear Features In Context: Nonconvex Mean-field Dynamics on the Attention Landscapecited by 46
  12. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  13. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  14. 2025T2VPhysBench: A First-Principles Benchmark for Physical Consistency in Text-to-Video Generationcited by 39
  15. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  16. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 29
  17. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  18. 2025On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspectivecited by 14
  19. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  20. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  21. 2025Can You Count to Nine? A Human Evaluation Benchmark for Counting Limits in Modern Text-to-Video Modelscited by 10
  22. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  23. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  24. 2025Subquadratic Algorithms and Hardness for Attention with Any Temperaturecited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 18
  2. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 2
  3. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  4. 2026ANDRE: An Attention-based Neuro-symbolic Differentiable Rule Extractor for Inductive Logic Programmingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Learning with Boolean threshold functions
  2. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
  3. 2026Differentiable Logic Synthesis: Spectral Coefficient Selection via Sinkhorn-Constrained Composition
  4. 2026Fitting Multilinear Polynomials for Logic Gate Networks
  5. 2025Softpick: No Attention Sink, No Massive Activations with Rectified Softmax
  6. 2026Polynomial Surrogate Training for Differentiable Ternary Logic Gate Networks
  7. 2026Efficient Reasoning at Fixed Test-Time Cost via Length-Aware Attention Priors and Gain-Aware Training
  8. 2026Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent