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.
Abstract (translated)
最近基于Transformer架构的进展在自然语言处理任务中取得了显著突破，模型如GPT-4、Claude和Gemini展示了接近人类水平的理解能力。然而，尽管这些模型表现出色，人们依然对其内在局限性表示担忧，特别是在学习基本逻辑功能方面的问题。虽然复杂性理论分析表明，Transformer由于属于$\mathsf{TC}^0$类（理论上能够代表简单的逻辑函数如$\mathsf{AND}$、$\mathsf{OR}$和多数门），可以自然地表达这些简单逻辑函数，但这些结果假设了理想化的参数设置，并未考虑基于梯度下降的训练方法所施加的实际约束。本研究探讨了使用基于梯度的方法训练时，Transformer是否能够真正学会简单的多数表决函数（majority functions）。 我们专注于一个简化的Transformer架构变体，并考虑两种不同的样本数量：$n=\mathrm{poly}(d)$和$n=\exp(\Omega(d))$，其中每个样本由长度为$d$的二进制字符串与其对应的简单多数表决函数输出组成。我们的分析表明，在进行了$\mathrm{poly}(d)$次梯度查询之后，Transformer模型的泛化误差仍然显著较大，并且随着$d$的增长呈指数上升。 这项工作突显了在最简单的逻辑推理任务中训练Transformer时面临的根本性优化挑战，并为理解这些模型的理论局限提供了新的视角。
URL
https://arxiv.org/abs/2504.04702
