揭示Transformer能生成多少不同序列的上限及其规律。
How Many Different Outputs Can a Transformer Generate?
- 基于提示长度推导出输出序列数的理论上限。
- 输出序列可访问性随长度增长呈指数衰减，临界点后大幅下降。
- 适用于理解模型在复制等任务中的失败原因，适合研究者参考。
我们研究如何仅利用Transformer架构的少量特性，精确预测其可生成的不同序列数量，无论定性还是定量均有效。我们给出一个依赖于提示长度的上界，并在多种架构和模型规模下验证其紧致性，误差因子小于10。分析还为之前观察到的Transformer在简单序列任务（如复制和填塞）中的失败提供了理论解释。形式上证明：(i) 可访问序列的最大长度随提示长度线性增长；(ii) 超过临界阈值后，可访问序列比例随序列长度呈指数衰减；(iii) 提示长度与可访问序列长度之间的线性系数存在理论上限。这些结论即使在无限上下文与计算时间下依然成立。
原文摘要 · Abstract (English)
We study how we can leverage only a handful of characteristics of a transformer's architecture to closely predict the number of different sequences it can output, both qualitatively and quantitatively. We provide an upper bound depending on the length of the prompt, which we show empirically to be tight up to a factor less than 10, across architectures and model sizes. Our analysis also provides a theoretical explanation for previously observed empirical failures of transformers on simple sequence tasks, such as copying and cramming. Formally, we prove that (i) the maximal length of accessible sequences (those that the transformer can output for some prompt) grows linearly with the prompt length, (ii) beyond a critical threshold, the proportion of accessible sequences decays exponentially with sequence length, and (iii) the linear coefficient relating prompt length to accessible sequence length admits a theoretical upper bound. Notably, these results hold even with unbounded context and computation time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。