Abstract
We study the computational limits of learning $k$-bit Boolean functions (specifically, $\mathrm{AND}$, $\mathrm{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 $\mathrm{AND}$ and $\mathrm{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.
Abstract (translated)
我们研究了使用简约的单头softmax注意力机制（其中$ k=\Theta(d) $相关的位从$d$个输入中被选出）来学习$k$-位布尔函数（特别是$\mathrm{AND}$、$\mathrm{OR}$及其噪声变体）的计算极限。结果显示，这些简单的$\mathrm{AND}$和$\mathrm{OR}$函数仅靠单头softmax注意力机制是无法解决的。然而，在使用教师强制训练的情况下，相同的简约注意力机制能够解决这些问题。 这些发现提供了两个关键见解：从架构的角度来看，解决布尔任务只需要简约注意机制，而不需要深层Transformer块或全连接层（FFNs）。从方法论角度来看，一次带有监督的梯度下降更新足以替代[Kim和Suzuki, ICLR 2025]为解决布尔问题提出的多步骤链式思考（CoT）推理方案。总的来说，这些界限揭示了在理想监督下这种最小架构所能实现的效果与在标准训练条件下无法证明可能之间存在着一个根本性的差距。
URL
https://arxiv.org/abs/2505.19531
