揭示Transformer在学习动态函数时的理论极限与计算难度
Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
- 推导单层线性自注意力模型全局最优解的闭式表达
- 证明恢复最优参数在一般情况下为NP难问题
- 发现多层结构可视为带预条件的梯度下降优化机制
Transformer架构可通过输入输出对在提示中实现上下文学习（ICL）。现有理论研究主要集中在独立同分布输入的线性回归任务。为理解Transformer在建模动态驱动函数时的ICL表达，本文通过结构化ICL设置研究马尔可夫函数学习，刻画损失曲面以揭示优化行为。具体而言：(1) 推导单层线性自注意力（LSA）模型在扩展参数空间下的全局最小值闭式解；(2) 证明在一般情况下恢复实现最优解的Transformer参数为NP-hard，揭示单层LSA在表达结构化动态函数时的根本局限；(3) 提出多层LSA可解释为对多个目标进行预条件梯度下降优化，超越平方损失。这些理论结果通过简化Transformer的数值实验得到验证。
原文摘要 · Abstract (English)
Transformer architectures can solve unseen tasks based on input-output pairs in a given prompt due to in-context learning (ICL). Existing theoretical studies on ICL have mainly focused on linear regression tasks, often with i.i.d. inputs. To understand how transformers express ICL when modeling dynamics-driven functions, we investigate Markovian function learning through a structured ICL setup, where we characterize the loss landscape to reveal underlying optimization behaviors. Specifically, we (1) provide the closed-form expression of the global minimizer (in an enlarged parameter space) for a single-layer linear self-attention (LSA) model; (2) prove that recovering transformer parameters that realize the optimal solution is NP-hard in general, revealing a fundamental limitation of one-layer LSA in representing structured dynamical functions; and (3) supply a novel interpretation of a multilayer LSA as performing preconditioned gradient descent to optimize multiple objectives beyond the square loss. These theoretical results are numerically validated using simplified transformers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。