证明了Transformer在任意长度上泛化的界限不可计算。
Length Generalization Bounds for Transformers
- 提出不可计算性证明，揭示Transformer长度泛化能力的理论极限。
- 发现双层C-RASP无计算性边界，且正片段边界为指数级最优。
- 适用于关注模型可解释性与泛化理论的研究者。
长度泛化是学习算法的关键属性，使其能在有限训练数据下对任意长度输入做出正确预测。为提供此类保证，需能计算出模型保证泛化的长度边界。本文研究了与Transformer密切相关的语言类C-RASP的泛化边界可计算性这一开放问题。近期陈等人已对单层及受限双层情形给出正向结果。本文给出了完整解答：证明了即使双层情况下，C-RASP也不存在可计算的长度泛化边界，从而对Transformer亦然。作为补充，我们为C-RASP的正片段提供了可计算边界，并证明其等价于固定精度Transformer。对于正片段与固定精度Transformer，我们证明其长度复杂度为指数级，且所给边界为最优。
原文摘要 · Abstract (English)
Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a guarantee, one needs to be able to compute a length generalization bound, beyond which the model is guaranteed to generalize. This paper concerns the open problem of the computability of such generalization bounds for C-RASP, a class of languages which is closely linked to transformers. A positive partial result was recently shown by Chen et al. for C-RASP with only one layer and, under some restrictions, also with two layers. We provide complete answers to the above open problem. Our main result is the non-existence of computable length generalization bounds for C-RASP (already with two layers) and hence for transformers. To complement this, we provide a computable bound for the positive fragment of C-RASP, which we show equivalent to fixed-precision transformers. For both positive C-RASP and fixed-precision transformers, we show that the length complexity is exponential, and prove optimality of the bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。