三令牌触发非负核注意力特征秩指数增长，揭示其表达瓶颈。
Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention
- 通过三令牌场景揭示非负核注意力的指数级特征需求
- 三元组任务中误差低于1/2需至少2^Ω(m)特征维度
- 适用于研究注意力机制表达能力的理论工作者
全注意力显式建模所有词对关系，而核注意力将序列压缩为固定维数的摘要。我们发现这一差异在首次出现两个竞争候选的上下文长度处呈现指数级分化。在布尔输入上的最小内积（Min-IP）任务中，一秩归一化核注意力可精确求解长度至多为2的任意序列。相反，任何能以严格低于1/2的误差处理所有三令牌序列的单个归一化非负核注意力头，即使使用任意有限维词元值和查询相关仿射读出，也需至少2^Ω(m)个特征。稠密Softmax则仅需m维分数和常数温度即可解决相同任务。该结论在位置依赖的词元映射和因果最终查询下依然成立。随着上下文长度增加，下界趋近于2^m特征的实际实现。此外，对于具有有限字母表的跨词元通道的确定性多头多层摘要模型，我们证明了其语料下界与独立答案数量线性相关，且与字母表大小对数相关。
原文摘要 · Abstract (English)
Full attention exposes every token pair, whereas kernel attention compresses a sequence into a fixed-dimensional sketch. We show that this distinction becomes exponential at the first context length containing two competing candidates. On Min-IP over Boolean inputs, rank-one normalized kernel attention solves every sequence of length at most two exactly. In contrast, any single normalized nonnegative kernel-attention head that succeeds on all three-token sequences with error strictly below $1/2$ requires $2^{Ω(m)}$ features, even with arbitrary finite-dimensional tokenwise values and an arbitrary query-dependent affine readout. Dense softmax solves the same task with $m$-dimensional scores and constant temperature. The conclusion survives position-dependent token maps and a causal final query. As context length grows, the lower bound approaches the exact $2^m$-feature realization. Separately, for deterministic multihead, multilayer sketch models whose cross-token channels have finite alphabets, we prove a transcript lower bound linear in the number of independent answers and logarithmic in their alphabet size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。