Abstract
Language recognition tasks are fundamental in natural language processing (NLP) and have been widely used to benchmark the performance of large language models (LLMs). These tasks also play a crucial role in explaining the working mechanisms of transformers. In this work, we focus on two representative tasks in the category of regular language recognition, known as `even pairs' and `parity check', the aim of which is to determine whether the occurrences of certain subsequences in a given sequence are even. Our goal is to explore how a one-layer transformer, consisting of an attention layer followed by a linear layer, learns to solve these tasks by theoretically analyzing its training dynamics under gradient descent. While even pairs can be solved directly by a one-layer transformer, parity check need to be solved by integrating Chain-of-Thought (CoT), either into the inference stage of a transformer well-trained for the even pairs task, or into the training of a one-layer transformer. For both problems, our analysis shows that the joint training of attention and linear layers exhibits two distinct phases. In the first phase, the attention layer grows rapidly, mapping data sequences into separable vectors. In the second phase, the attention layer becomes stable, while the linear layer grows logarithmically and approaches in direction to a max-margin hyperplane that correctly separates the attention layer outputs into positive and negative samples, and the loss decreases at a rate of $O(1/t)$. Our experiments validate those theoretical results.
Abstract (translated)
语言识别任务是自然语言处理（NLP）中的基本任务，广泛用于评估大型语言模型（LLMs）的性能。这些任务在解释变压器的工作机制方面也扮演着重要角色。在这项工作中，我们专注于两类常规语言识别任务的代表性任务：即“偶数对”和“奇偶校验”，其目的是确定给定序列中某些子序列出现次数是否为偶数。我们的目标是通过理论分析单层变压器（由注意力层和线性层组成）在梯度下降训练过程中的学习动态，来探索它如何解决这些任务。“偶数对”可以直接使用单层变压器解决，“奇偶校验”则需要结合“链式思维”(Chain-of-Thought, CoT) 方法来解决。对于已经经过“偶数对”任务良好训练的变压器推理阶段中集成CoT，或是在单层变压器的训练过程中直接整合。 针对这两个问题，我们的分析表明注意力和线性层的联合训练展示了两个不同的阶段。在第一阶段，注意力层迅速增长，并将数据序列映射为可分向量。而在第二阶段，注意力层变得稳定，而线性层则以对数方式增长，在方向上逐渐接近于能够正确分离注意力层输出（将样本分为正负两类）的最大间隔超平面，并且损失函数的减少速度是$O(1/t)$。 实验结果验证了这些理论成果。
URL
https://arxiv.org/abs/2505.00926
