minimalist注意力机制在监督下可精准学习布尔函数
Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
- 用单头软注意力选关键比特，配合教师强制训练
- 仅一次梯度更新即可解决与非等布尔问题
- 证明简单架构在理想监督下远超常规训练能力
我们研究了使用极简单头软注意力机制学习 $k$-比特布尔函数（具体为 $ ext{AND}$、$ ext{OR}$ 及其噪声变体）的计算极限，其中 $k=Θ(d)$ 个相关比特从 $d$ 个输入中被选择。我们发现，仅靠单头软注意力机制无法求解这些 $ ext{AND}$ 与 $ ext{OR}$ 函数。然而，在教师强制（teacher forcing）条件下，相同的极简注意力机制却能成功解决它们。这一结果揭示两个核心洞见：架构上，解决此类布尔任务仅需极简注意力，无需深层 Transformer 块或前馈网络；方法上，一次梯度下降更新即可完成学习，取代 [Kim and Suzuki, ICLR 2025] 中多步链式思维（CoT）推理方案。整体结果揭示了理想监督下该极简架构所能达到的边界，与标准训练下不可行性的根本差距。
原文摘要 · Abstract (English)
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=Θ(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。