【Transformer 与注意力机制】55｜Transformer 的根本局限：为什么 O(n²) 是终极瓶颈

Transformer 是过去十年最成功的深度学习架构之一。它取代 RNN 成为序列建模主力，支撑了 BERT、GPT、T5、ViT、多模态模型和今天的大语言模型生态。正因为它如此成功，它的问题也被放大到了前所未有的程度。

早期讨论 Transformer 局限时，最常见的一句话是：attention 是 \(O(n^2)\)。这句话没错，但太粗，而且经常被当成”工程还没优化到位”的临时状态来理解——好像下一代 kernel 或者下一代硬件就能把它翻过去。2022 年以后陆续出现的一批复杂度理论工作说明，这个直觉是错的：在相当一般的假设下，标准 attention 的计算就是没有亚二次时间算法，这不是实现细节，是可以证明的下界。真正的限制因此分成两层——一层是可以被工程持续推远的瓶颈（FlashAttention 解决的 I/O 问题），另一层是工程推不动的架构瓶颈（关系数量、KV Cache 增长、自回归依赖，以及现在有了理论下界背书的计算复杂度本身）。除此之外还有一组更隐蔽的限制：长上下文不等于长期记忆、位置编码的结构性修复也有失效模式、模型的强大很大程度上是数据喂出来的、而喂养本身正在撞上供给上限。

本篇不是为了宣布 Transformer 过时。相反，要理解后 Transformer 时代的各种路线，必须先准确理解 Transformer 到底卡在哪里，卡在哪一层意义上的”卡”。56｜状态空间模型、57｜RWKV / RetNet / 线性注意力、58｜后 Transformer 时代 要回答的问题，都是同一件事的不同侧面：能不能在不越过下面这些下界的前提下，换一种方式计算”序列建模”这件事。

本篇能让你学会三件事：

1. 工程瓶颈和架构瓶颈的分界线在哪里，为什么这条线现在有了复杂度理论的支撑，而不只是经验总结；
2. 长上下文、KV Cache、自回归串行性、位置外推、数据效率这几件事看似独立，实际上共享同一个根源——一次前向计算能覆盖的信息量是有限的；
3. 新架构要挑战 Transformer，必须同时在质量、成本、稳定性、生态四条战线上证明自己，缺一条都不够。

一、工程瓶颈与架构瓶颈：一条现在有理论支撑的分界线

讨论 Transformer 局限时，最容易混淆两类问题。第一类是工程瓶颈：同样的数学公式，现有实现太慢、太耗显存、没有充分利用硬件。第二类是架构瓶颈：即使实现已经足够优秀，模型本身的依赖结构仍然带来成本。

42｜FlashAttention 是工程瓶颈被系统解决的典型案例，也恰好给出了这条分界线的一个精确样本。Dao et al.（NeurIPS 2022）的 Theorem 2 证明：设序列长度为 \(N\)、头维为 \(d\)、片上 SRAM 大小为 \(M\)，标准 attention 需要 \(\Theta(Nd + N^2)\) 次 HBM 访问，而 FlashAttention 只需要 \(\Theta(N^2d^2M^{-1})\) 次——这是数量级的降低。但同一篇论文的 Proposition 3 同时证明了一个更少被引用、却更关键的结果：不存在任何精确 attention 算法，能在所有 \(M\) 取值范围内进一步降低 HBM 访问次数。也就是说，FlashAttention 不是”还没做到最好的工程近似”，它已经是 I/O 复杂度意义上的最优解——工程瓶颈被推到了理论允许的边界，但这个边界仍然留在原地：FLOPs 始终是 \(\Theta(N^2d)\)，没有变成 \(\Theta(Nd)\)。

这条区分不是事后总结出来的。Vaswani et al.（NeurIPS 2017）的 Table 1 在提出 Transformer 的同一篇论文里，就把 self-attention 的 per-layer complexity（\(O(n^2 d)\)）、sequential operations（\(O(1)\)）、maximum path length（\(O(1)\)）和 recurrent layer（分别是 \(O(nd^2)\)、\(O(n)\)、\(O(n)\)）并排摆在一起：self-attention 用”任意两个位置一步直达”换来了并行训练，代价正是关系数量的平方增长——这是同一枚硬币的两面，论文作者自己写得很清楚。论文原文还补了一句容易被忽略的限定：当序列长度 \(n\) 小于表示维度 \(d\) 时（当年机器翻译场景下 word-piece/byte-pair 分句的常见情况），self-attention 比 recurrent 层更快。这条限定条件在 2017 年基本总是成立，\(n\) 通常是几十到几百，\(d\) 是 512 到 1024；但今天的长上下文场景里 \(n\) 常常是 \(d\) 的几十到几百倍，这条当年不算问题的假设已经反过来。论文同一节末尾甚至已经提到”计划研究把 self-attention 限制在局部邻域”作为未来工作——这正是几年后 Sparse Transformer、Longformer、BigBird（见 43｜稀疏与局部注意力）真正做的事。

理解这个区分很重要。否则每次出现新 kernel、新硬件、新 serving trick，人们就会误以为 Transformer 的根本问题已经解决。事实上，工程优化让 Transformer 继续保持竞争力，但也暴露了更深的架构问题：如果上下文继续变长、并发继续增加，现有结构还能撑多久。

二、O(n²) 不是”数字大”：它是一个可以证明的复杂度下界

标准 self-attention 中，每个 query 都要和所有 key 计算相似度，注意力分数矩阵是 \(n \times n\)。序列长度翻倍，关系数量变成四倍，这件事本身没有争议。真正值得深挖的问题是：这个二次关系到底是”当前算法不够聪明”，还是”任何算法都逃不掉”？2022 年之后的两项细粒度复杂度理论工作，把这个问题从工程直觉变成了可以证明的命题。

Alman 和 Song（NeurIPS 2023，“Fast Attention Requires Bounded Entries”）把注意力计算形式化为 \(\mathrm{Att}(Q,K,V) = \mathrm{diag}(A\mathbf{1}_n)^{-1}AV\)，其中 \(A=\exp(QK^\top/d)\)，\(Q,K,V \in [-B,B]^{n\times d}\)。他们证明了一个以 \(B=\Theta(\sqrt{\log n})\) 为界的尖锐相变：当 \(B=o(\sqrt{\log n})\)（矩阵元素幅度足够小）时，存在把 attention 近似到 \(1/\mathrm{poly}(n)\) 误差内的 \(n^{1+o(1)}\) 时间算法——接近线性；但当 \(B=\Theta(\sqrt{\log n})\) 或更大时，假设强指数时间假设（Strong Exponential Time Hypothesis, SETH）成立，不存在任何时间复杂度 \(n^{2-\Omega(1)}\) 的算法能把 attention 近似到同样精度内，不论用什么算法技巧。Duman Keles、Wijewardena 和 Hegde（ALT 2023，“On The Computational Complexity of Self-Attention”）给出了方向一致但更一般的结果：在 SETH 假设下，self-attention 的时间复杂度必然是输入长度的二次函数，这个结论对多种 attention 机制都成立，即便只要求近似计算；作为补充，他们同时证明用有限阶 Taylor 展开可以把点积 self-attention 近似成线性时间算法，代价是常数因子随展开阶数指数增长——线性时间不是免费的，是拿精度和常数因子换来的。

这两项结果的意义不在于”证明了 \(O(n^2)\)“——这早就是常识——而在于划清了这个下界的精确边界条件：它约束的是计算标准稠密 softmax attention 本身（精确或者要求特定误差保证的近似），并且需要输入矩阵元素幅度落在某个阈值以上。这和 43｜稀疏与局部注意力 里 BigBird 证明的 \(\tilde\Omega(n^{1-o(1)})\) 层下界是两类不同的结果：BigBird 的下界针对的是”用固定边数的稀疏图能不能在少层内模拟 full attention 的某个具体任务”，回答的是稀疏化的代价；Alman & Song 与 Duman Keles 的下界针对的是”计算标准 attention 这件事本身能不能被加速”，回答的是这件事在算法上是否可能。两者合在一起说明一件更完整的事：如果你坚持算的是标准稠密 softmax attention，二次时间几乎无法绕开；如果你想绕开，就必须换一个计算的目标——这正是稀疏、线性注意力、状态空间模型共同选择的路，代价是（按 BigBird、Zoology 等工作的量化结果，见 43、57）某些任务上可证明的表达力损失，不是免费的替代。

三、推理侧两条独立的代价：KV Cache 线性增长与自回归串行

训练阶段的主要矛盾是并行计算一整段序列；推理阶段的主要矛盾是逐 token 生成，而且这里的成本结构和训练阶段完全不是同一件事。

49｜KV Cache 给出的显存公式是 \(2 \times L \times B \times S \times H_{kv} \times D_h \times \text{bytes}\)：缓存大小随层数 \(L\)、batch \(B\)、上下文长度 \(S\)、KV head 数 \(H_{kv}\) 和 head 维度 \(D_h\) 线性增长。线性听起来比训练时的二次好，但在真实服务系统里，这个线性乘上并发请求数和长上下文窗口，同样会变成显存墙。MQA/GQA 通过压缩 \(H_{kv}\)、量化通过压缩 bytes 都能把这条线性关系的系数变小，PagedAttention（Kwon et al., SOSP 2023）通过分页管理消灭内存碎片，但没有一种方法能把 \(S\) 这一项从公式里去掉——只要模型架构要求”decode 时可以看到全部历史”，缓存量就必然随历史长度增长，这是同一类”关系不消失、只是系数变小”的工程让步，和第一节 FlashAttention 对 FLOPs 的态度是同一个模式。

自回归串行性是另一条独立的代价，不是显存问题，是依赖结构问题：必须先生成第 \(t\) 个 token，才能生成第 \(t+1\) 个 token。50｜Speculative Decoding 讲过接受-拒绝机制如何让小模型先草拟、大模型批量验证，并给出了严格保持目标分布不变的证明；但这个机制加速的是”验证多个候选的那一次 forward”，猜对时可以一次吐出多个 token，猜错时仍然要退回逐 token 生成——它没有、也不可能消除”下一个 token 依赖上一个 token”这条依赖链本身，只是把可以并行验证的部分尽量做大。

这两条代价加在一起，说明 Transformer 的推理瓶颈不是单一维度：prefill 阶段像大矩阵计算，受第二节的复杂度下界和 attention kernel 影响；decode 阶段像状态机循环，受 KV Cache 带宽和串行依赖影响。长上下文模型把两类问题都放大了，而且是用两种独立的物理资源（显存容量、时延）放大的，不能指望解决一个就自动解决另一个。

四、长上下文 ≠ 长期记忆

上下文窗口变长，很容易被宣传成”模型记忆更好”。这句话需要拆开。上下文窗口只是模型在一次前向过程中可访问的 token 范围，它不是长期记忆，不是数据库，也不是持续学习。长期记忆至少包含几个不同能力：能把过去事件持久保存；能在未来合适时间检索；能更新、压缩和遗忘；能跨会话保持一致。长上下文只解决其中一部分——把更多文本塞进当前 prompt，让 attention 有机会读取。

这不是一句空泛的区分，41｜位置编码演进 已经用两组实测数据把”能读到”和”会用”之间的鸿沟钉死。RULER（Hsieh et al., COLM 2024）在 needle-in-a-haystack 基础上扩出多针检索、多跳变量追踪、聚合统计等 13 个子任务，评测的 17 个模型几乎都能在原版 needle 测试上拿到接近满分，但当上下文长度增加时几乎所有模型在综合任务上出现明显下滑，而且这些模型都宣称支持 32K 或更长上下文，却只有一半能在 32K 长度上维持令人满意的表现——“跑得动某个长度”和”能在那个长度里可靠检索、推理”是两个不同的数字。Liu et al.（Transactions of the Association for Computational Linguistics, 2024，“Lost in the Middle”）在多文档问答和键值检索任务上发现另一个独立现象：模型对开头和结尾信息的利用率明显高于中间信息，形成 U 形曲线，即便是专门标注支持长上下文的模型也不例外，这个偏置和”距离多远”无关，是”位置在序列里的深度”造成的。

这两组证据合在一起说明：needle 类评测过关只能说明位置编码的几何结构没有严重失真，不能说明模型具备可靠的长程推理能力。所以长上下文和 RAG、外部记忆、数据库、工具调用不是替代关系，而是分工关系——58｜后 Transformer 时代 用 RETRO、RAG、ReAct、Toolformer、MemGPT 具体拆解了这条分工线：短期工作记忆放在上下文里，长期知识放在检索系统里，结构化状态放在数据库或分页式外部存储里，模型负责整合和生成。本篇不重复那条系统工程线，只钉住这里的判断：窗口变大解决的是”能不能看到”，不是”记不记得住”“用不用得对”，这两件事需要不同的机制去解决。

五、位置外推：结构性修复不是终点

Transformer 没有天然顺序感（见 21｜位置编码 的排列等变性证明），必须靠位置编码知道 token 顺序。sinusoidal 的相对位移可线性表达性质是一条”免费下限”，不保证模型真的学会用它；RoPE、ALiBi 把这条性质从”模型可能学到”焊死成”结构上保证”，代价是各自留下了新的失效模式——这条完整的推导、RoPE 频率通道的绕圈周期表、ALiBi 的近邻先验代价，41｜位置编码演进 已经用可核对的公式和实测数据讲清楚，这里不重复。

值得在这里点出的是一条尚无定论的争论，因为它直接关系到”训练变长就完事”这个直觉为什么不成立：Kazemnejad et al.（NeurIPS 2023）在算法推理类任务上系统对比 APE、T5 相对位置、ALiBi、RoPE 和完全不用显式位置编码（NoPE）的长度泛化能力，结论是三种最常用的显式位置编码方法都不适合这类任务的长度泛化，NoPE 反而更好——这和”RoPE/ALiBi 已经解决外推”的工程共识直接冲突。41｜位置编码演进 第五节已经指出，这条冲突可能来自两种实验设定的假设差异（分布外组合泛化 vs. 分布内长度延伸配合少量继续训练），目前没有定论。这里要强调的判断是：位置编码解决的是”结构上能不能表达相对距离”，不等于”模型在任意任务分布下都会正确使用这份能力”——这条鸿沟本身也是”新架构要不要重新面对同一个问题”的一部分，SSM、线性注意力同样需要各自的位置方案，不会因为换了架构就自动消失。

六、数据效率：强大是喂出来的，喂养本身有硬约束

34｜Scaling Laws 讲过，Kaplan 之后行业确认了继续加模型、加数据、加计算能换来平滑的 loss 改善；Chinchilla（Hoffmann et al., 2022）进一步纠正了”参数越大越好”的偏向，指出很多模型不是不够大，是每个参数看过的 token 不够多。这条规律隐含一个前提：训练数据是可以持续扩大的资源。这个前提正在变得不成立。

Muennighoff et al.（NeurIPS 2023，“Scaling Data-Constrained Language Models”）直接研究了”数据不够用怎么办”这个问题：他们训练了超过 400 个模型（参数量最高到 90 亿，训练 token 最多到 9000 亿），系统改变数据重复次数和计算预算，得到的核心结论是——在固定计算预算下，重复数据训练到大约 4 个 epoch 之内，损失和用同等数量的全新数据几乎没有差别；但重复超过这个范围后，继续投入计算的边际价值逐渐衰减到零。他们据此提出了一条把 Chinchilla scaling law 推广到”数据受限”场景的新公式，显式建模了重复 token 和超额参数的价值衰减。这条结果的意义很直接：数据不是可以无限重复就能等价于新数据的资源，“多训几轮”这条路本身也有天花板，而互联网可用文本的总量是有限的——35｜数据工程 已经指出高质量数据稀缺、重复和低质数据浪费训练预算、合成数据有分布坍缩风险，Muennighoff et al. 的工作把这条经验判断变成了一条可以量化拐点的 scaling law。

这一节和第二节共享同一个论证结构：不管是计算复杂度还是数据供给，都存在某种”能推远但推不没”的硬约束。新架构如果想挑战 Transformer，不能只说自己复杂度更低，还要在同样数据和算力约束下证明质量不掉——这一点直接引向第八节的评判标准。

七、可解释性与可控性：算力之外的另一类局限

Transformer 的局限不只在计算资源上。早期有一种直觉：attention weight 能告诉我们模型在关注哪里，所以 attention 就是解释。52｜可解释性入门 已经指出这个说法太简单——attention weight 只是相关性线索，不是因果证据；53｜机制可解释性 进一步用 induction head、IOI 电路、activation patching 说明，即便找到了能解释部分行为的电路，也远远不等于解释了整个模型，机制可解释性研究本身还在应对可扩展性和”解释幻觉”的问题。可控性也类似：指令微调和 RLHF 能让模型更像助手，但不能保证它在所有分布外输入上稳定遵循意图，幻觉、越狱、格式漂移都是复杂系统行为，不是单靠调整 attention 结构就能解决的问题。这条局限本篇不重复展开，只钉住一个判断：即使未来把前六节的每一条硬约束都推到理论允许的极限，如何理解、约束和验证模型行为，仍然是训练范式而不是复杂度理论能单独回答的问题。

八、新架构要同时赢什么：为 56-58 定坐标

既然 Transformer 有这么多可以证明或者可以实测的局限，为什么还没有被轻易替代？原因是 Transformer 不只是一个数学公式，而是一整套需要同时被超越的评判标准。一个新架构如果只在复杂度表格上赢，不足以构成替代的理由，它至少要同时回答四个问题：

1. 质量：同等训练算力和数据下，perplexity 和下游能力是否接近或更好——不能只展示复杂度更低，却回避同等约束下的质量对比；
2. 成本：真实硬件上的 wall-clock 吞吐和显存占用是否真的更省，不是理论 FLOPs 或渐近复杂度——第一节已经说明，理论复杂度和工程可兑现的效率是两件事，新架构同样要过这一关，不能只靠公式好看；
3. 训练稳定性：能不能在更大规模下稳定收敛，scaling 行为是否可预测——这本身也是一条经验规律，不会因为换了架构就自动继承 Transformer 已经摸索出的配方；
4. 生态：能不能接入现有的量化、并行训练、推理引擎、对齐流程——十年积累的 kernel、框架和工具链不会因为一篇论文证明了数学上的优势就自动配套。

这四条标准不是本篇提出的抽象要求，而是接下来三篇要用具体证据逐条核对的框架。56｜状态空间模型 和 57｜RWKV / RetNet / 线性注意力 会分别展示 Mamba、RWKV、RetNet、线性注意力在质量和成本这两条战线上的具体得分与失分——包括它们各自在检索密集型任务上可证明的表达力短板；58｜后 Transformer 时代 会用 Jamba、Griffin、NVIDIA 的受控对照实验，以及 Hardware Lottery 这篇文献，把训练稳定性和生态这两条更难量化的战线钉到具体数字上。本篇只负责把这四条战线本身列清楚，不重复它们各自的实验细节。

九、争论与开放问题

争论：\(O(n^2)\) 到底是”当前工程没做到位”，还是”数学上无法绕开”？ 这个问题在本篇写到这里，答案已经不是”看情况”式的空话，而是可以分层回答。如果问题是”能不能把标准稠密 softmax attention 的精确或近似计算做到亚二次时间”，第二节给出的答案是否定的——在 SETH 成立、输入元素幅度不太小的前提下，Alman & Song 和 Duman Keles et al. 的下界排除了这种可能性，这不是”还没找到更聪明的算法”，是可以证明的不可能性。但如果问题是”能不能换一个计算目标，绕开这条下界”，答案是肯定的，而且已经有整条研究路线在做——第二节末尾指出，稀疏 attention（第 43 篇）、线性注意力与状态空间模型（第 56、57 篇）都不是在挑战这条复杂度下界，而是主动放弃”精确计算标准 attention”这个目标，换成一个计算量更小、但可证明存在表达力损失的近似目标（BigBird 的层数下界、Zoology 的 MQAR 维度下界都是这类代价的量化）。两类工作因此不在同一个战场上——真正悬而未决的，不是”\(O(n^2)\) 能不能被打破”，而是”放弃精确计算标准 attention 之后，损失的表达力在多大程度上可以被工程手段（门控、混合局部精确 attention、更大状态维度）补回来，补到什么程度才够用”。

由此可以列出三个具体的开放问题：

1. 生产级 Transformer 里 Q、K 的实际元素幅度，是否系统性落在 Alman & Song 划定的”快”区间（\(B=o(\sqrt{\log n})\)）内？ 如果确实落在这个区间，理论上存在近乎线性时间的近似算法；但目前没有公开的、跨模型家族的系统测量能回答这个问题，也没有证据说明现有生产 kernel 是否已经在隐性利用这个区间（例如经过 LayerNorm 和 \(1/\sqrt d\) 缩放后的数值范围）。这是一个可以直接用现有模型权重测量、却还没人系统做过的实证空白。
2. Lost in the Middle 的 U 形偏置到底来自训练数据分布，还是 causal mask 本身的结构性倾向？ 第四节引用的证据显示这个现象独立于绝对距离衰减，但成因目前没有被归因到某个单一机制，41｜位置编码演进 已经把这一点列为未解决的问题，本篇不重复展开，只再次点名它属于”长上下文≠长期记忆”这条线索里最缺一手机制解释的一环。
3. 数据受限 scaling law 揭示的”重复价值衰减”拐点，会不会随模型规模继续右移？ Muennighoff et al. 的实验覆盖到 90 亿参数、9000 亿 token，更大规模下”4 个 epoch 内几乎无损”这条经验阈值是否成立，目前没有公开证据，这直接决定了”高质量数据枯竭”这件事对下一代更大模型是紧迫的硬约束，还是可以再往后推几年的问题。

这三个问题都指向具体的、可检验的实证工作，不接受”下一代硬件会解决一切”或者”scaling 会自然修复”这类空洞收尾。

十、关键概念回顾

• 工程瓶颈：实现和硬件利用效率带来的瓶颈，可以被推到理论允许的边界（如 FlashAttention 的 I/O 最优性），但推不没。
• 架构瓶颈：模型信息流和依赖结构本身造成的瓶颈，现在有复杂度理论下界背书——计算标准稠密 attention 在 SETH 假设下没有亚二次算法。
• KV Cache 线性增长：decode 中缓存历史 K/V，显存随上下文长度、batch、并发线性增加，和训练时的二次关系是两条独立的代价。
• 自回归串行性：生成第 \(t+1\) 个 token 依赖第 \(t\) 个 token；speculative decoding 并行验证候选，不消除这条依赖链。
• 长上下文≠长期记忆：窗口变大只解决”一次前向能访问多少 token”，不解决持久化、检索可靠性、更新遗忘、跨会话一致性。
• 数据受限 scaling law：重复数据在约 4 个 epoch 内价值接近全新数据，超过这个范围后继续投入计算的边际价值衰减到零。
• 后 Transformer 路线的评判坐标：质量、成本、训练稳定性、生态——四条战线必须同时赢，复杂度更低不构成单独的替代理由。

十一、常见误解

11.1 “\(O(n^2)\) 意味着 Transformer 马上过时”

不成立。\(O(n^2)\) 是真实且可证明的下界，但 Transformer 仍然有质量、生态、硬件优化和通用性优势。下界推动替代路线发展，不等于立刻替代——第八节的四条评判标准里，复杂度只是”成本”这一条的一部分。

11.2 “FlashAttention 已经解决长上下文的复杂度问题”

不对。FlashAttention 把 HBM 访问降到了理论最优（Dao et al. 的 Proposition 3 已经证明这一点），但 FLOPs 始终是 \(\Theta(N^2d)\)，没有变化。它解决的是 I/O 工程瓶颈，不是 \(O(n^2)\) 关系本身。

11.3 “既然理论上存在近乎线性的近似算法，现在的 kernel 就是没做好”

不准确。Alman & Song 的近乎线性算法只在输入元素幅度足够小（远小于 \(\sqrt{\log n}\)）时才存在，而且是在特定误差保证下的近似；第九节已经指出，生产 Transformer 的实际数值区间是否落在这个”快”区间，目前没有系统测量，不能直接下结论。

11.4 “长窗口就是长期记忆”

长窗口只是把更多 token 放进当前上下文。长期记忆还需要持久化、检索、更新、遗忘和跨会话一致性，RULER 和 Lost in the Middle 的实测数据已经证明”跑得动某个长度”和”在那个长度里可靠推理”是两个不同的能力。

11.5 “新架构只要复杂度低就会赢”

复杂度低只是第八节四条战线里”成本”的一部分，而且理论复杂度不等于真实吞吐。新架构还必须在质量、训练稳定性、生态上接近或超过 Transformer，任何一条掉链子都不够。

十二、下一步

理解 Transformer 的限制之后，下一步就可以认真看状态空间模型。Mamba、S4 这类路线不是凭空出现的，它们正是在尝试绕开本篇第二节证明的复杂度下界——不是打破它，而是主动改变计算目标，用一个大小固定的状态压缩历史，换取线性时间。问题是：用一个状态来压缩历史，究竟能保留多少信息，又会在哪些任务上付出第九节说的那种可证明的表达力代价？这会是下一篇的核心。

十三、参考文献

核心论文

1. Vaswani, A. et al. “Attention Is All You Need.” NeurIPS 2017. Table 1 给出 self-attention 与 recurrent/convolutional 层的 per-layer complexity、sequential operations、maximum path length 对照，是本篇第一节”训练并行性换关系数量”这条 trade-off 的原始出处。
2. Dao, T. et al. “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.” NeurIPS 2022. Theorem 2 给出标准 attention 与 FlashAttention 的 HBM 访问复杂度，Proposition 3 证明精确 attention 算法的 I/O 复杂度下界。
3. Alman, J. and Song, Z. “Fast Attention Requires Bounded Entries.” NeurIPS 2023（原 arXiv:2302.13214）。SETH 假设下 attention 近似计算的尖锐相变（\(B=\Theta(\sqrt{\log n})\)），本篇第二节、第九节的核心一手证据。
4. Duman Keles, F., Wijewardena, P. M., and Hegde, C. “On The Computational Complexity of Self-Attention.” ALT 2023（原 arXiv:2209.04881）。SETH 假设下 self-attention 时间复杂度必然二次的一般性证明，以及 Taylor 展开线性时间近似的代价。
5. Zaheer, M. et al. “Big Bird: Transformers for Longer Sequences.” NeurIPS 2020. §3.4 的 OVC 层数下界，详见 43｜稀疏与局部注意力；本篇用来说明它与 SETH 下界回答的是不同层面的问题。
6. Kwon, W. et al. “Efficient Memory Management for Large Language Model Serving with PagedAttention.” SOSP 2023. KV Cache 服务化瓶颈与分页管理的重要来源。
7. Liu, N. F. et al. “Lost in the Middle: How Language Models Use Long Contexts.” Transactions of the Association for Computational Linguistics, 12:157–173, 2024（原 arXiv:2307.03172）。长上下文 U 形位置利用偏置的实测证据。
8. Hsieh, C.-P. et al. “RULER: What’s the Real Context Size of Your Long-Context Language Models?” COLM 2024（原 arXiv:2404.06654）。有效上下文与宣称上下文差距的系统评测。
9. Kazemnejad, A. et al. “The Impact of Positional Encoding on Length Generalization in Transformers.” NeurIPS 2023. NoPE 在算法推理任务长度泛化上优于显式位置编码的系统实验，详见 41｜位置编码演进。
10. Hoffmann, J. et al. “Training Compute-Optimal Large Language Models.” arXiv:2203.15556, 2022. Chinchilla 法则原始论文，详见 34｜Scaling Laws。
11. Muennighoff, N. et al. “Scaling Data-Constrained Language Models.” NeurIPS 2023（原 arXiv:2305.16264）。数据受限场景下重复 token 价值衰减的 scaling law，本篇第六节的核心一手证据。

延伸对照

12. Su, J. et al. “RoFormer: Enhanced Transformer with Rotary Position Embedding.” Neurocomputing 2024（原 arXiv:2104.09864）。RoPE 位置编码来源论文，详见 41｜位置编码演进。
13. Press, O. et al. “Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation.” ICLR 2022. ALiBi 与长度外推，详见 41｜位置编码演进。
14. Gu, A. and Dao, T. “Mamba: Linear-Time Sequence Modeling with Selective State Spaces.” arXiv:2312.00752, 2023. 详见 56｜状态空间模型。

← 上一篇：54｜涌现能力　|　下一篇：56｜状态空间模型 →