你让 AI 读一份很长的材料。为了回答末尾的问题，它可能要把当前问题同前文每一处内容逐一比较。材料长度翻倍，需要处理的配对数量大约变成四倍。这正是标准 Softmax attention（先计算“查询”与各个“键”的相关性，再把分数归一化为权重）的主要成本。
近似注意力试图少做一些比较：用抽样、压缩或稀疏连接换取速度。它在实际任务和部分输入上可以表现很好。但一个更强的问题一直没有彻底回答：能否设计一种真正快于二次时间的算法，不管输入多古怪，都至少给出一点有用的误差保证？
Lukas Haverbeck、Carmen Amo Alonso、Andres Felipe Posada-Moreno、Sebastian Trimpe 和 Marco Pavone 的论文《Efficiently Approximating Attention Is Hard》给出了否定答案。按照论文的条件，在标准复杂性理论假设成立时，对所有输入提供非平凡近似保证的算法，无法真正突破二次时间。结论还延伸到了预处理 KV cache 和稀疏注意力检索。
先说明信源边界：以下核心结论及其适用条件均来自这篇论文，尚无独立信源交叉印证。这是一组条件性理论下界，不是对现有加速方法的实测判决。
难点不只是“算得足够准”
注意力让模型处理一个词元时，按相关程度汇总其他词元的信息。每个词元会提供 query、key 和 value：query 像当前要找的问题，key 像索引标签，value 则是最终取回的内容。标准做法比较所有 query 和 key，再按权重混合 value。若序列有 个词元，需要考虑的配对规模约为 。
所谓“真正次二次”，不是只靠硬件或常数优化快一点，而是运行时间达到 ，其中 是某个固定正数。序列越长，它相对二次算法的优势越明显。
此前的理论下界主要说明：想在次二次时间里把注意力算得近乎精确，做不到。但这留下了一个很大的口子。也许我们不追求近乎精确，只要求结果别错得毫无意义，就能获得普遍适用的快速算法。
新论文声称堵上了这个口子。它同时考察两类误差。加性误差关注近似结果与真实结果相差多少；相对误差关注误差相对于真实结果有多大。作者给出的下界覆盖任何“非平凡”的加性或相对保证：也就是优于无需查看输入便能做到的平庸答案。
这里最关键的词是“一致保证”。它要求算法对所有符合条件的输入都控制住误差，而不只是对常见文本、平均情形或某类结构良好的数据有效。好比一条公路声称全天候通行，它必须把暴雪和洪水也算进去；现实中大多数日子通畅，并不能证明这个更强的承诺。
证明把注意力变成一道寻人题
论文沿用了一个核心思路：把注意力计算同“最近点对”问题连接起来。最近点对问题可以理解为，在两组高维向量中找出最相近的一对。已有复杂性结果表明，在论文采用的假设下，这类搜索不能普遍地比检查近乎所有配对快很多。
作者把两组向量编码成 query 和 key。距离近的向量会得到更高的注意力分数。这样一来，如果存在一种快速而且对所有输入都有保证的注意力近似算法，就可以借它更快地找出最近点对，从而与已有下界冲突。
麻烦在于，注意力算法不会直接交出全部配对分数。它返回的是分数经过 Softmax 归一化后，对 value 的加权汇总。单个近邻的信号可能被这个汇总过程遮住。旧证明因此需要近似结果非常精确，才能可靠地把近邻辨认出来。
新证明的关键，是反过来利用归一化。作者加入一批“虚拟 key”，并调整真实 query 和 key 的编码：近距离的真实 key 得分高于虚拟 key，远距离的真实 key 则低于它们。随后，value 被设置成测量总共有多少注意力落在真实 key 上。
这像是在票箱里放入一批基准票。只要存在一个足够近的真实 key，它就能压过全部基准；如果真实 key 都很远，它们合起来仍然几乎没有分量。最终输出接近一个二值指示器，用来判断某个距离阈值以内是否存在配对。即使近似很粗，只要仍比平庸答案好，也能区分两种情况。再测试若干不同阈值，便可恢复一个近似最近点对。
由此，论文把此前针对“近乎精确”的障碍推进到了“任何非平凡一致保证”。这个结论依赖 Strong Exponential Time Hypothesis（强指数时间假设，简称 SETH）——细粒度复杂性理论中常用、但尚未被证明的假设。它不是数学上无条件成立的禁令。
先整理 KV cache，也绕不过去
实际生成文本时，模型通常先一次性处理输入，这一步叫 prefill；随后逐词生成，这一步叫 autoregressive decoding（自回归解码）。解码必须按顺序进行，较难并行。模型还会保存 KV cache——可以把它理解为读长文时留下的中间索引和笔记，免得每生成一个词都从头计算。
一种自然的加速思路是：允许系统预先花很多时间压缩、整理或建立 KV cache 索引，之后每次查询只做少量工作。论文专门分析了这个更宽松的设定。其结论是，即便允许对 KV cache 做任意多项式时间的预处理，也无法在真正次线性的单次解码时间内，对所有输入给出非平凡的注意力近似保证。
理由仍来自最近点对问题。已有相关下界允许提前看到并预处理其中一组向量，另一组查询后来才出现。论文的注意力编码正好对应这种“先建索引、后查询”的结构。因此，把一次性成本移到前面，并没有消除最坏情形的搜索困难。
注意力很稀疏，也不等于容易找到重点
稀疏注意力的直觉很诱人：如果一次查询的大部分权重只落在少数 key 上，何必查看全部 key？先找出那几个重点，再只对它们计算即可。
论文研究了一个对算法相当有利的版本：预先承诺注意力确实高度集中，至少有一个 key 获得常数比例的权重；算法只需返回一个很小的 key 集合，让它们合计捕获常数比例的注意力。即便如此，作者仍给出条件性下界：经过多项式时间预处理后，算法也不能以真正次线性的查询时间，对所有输入完成这种检索。
这里还有一个证明障碍。如果许多近邻同样接近，注意力会分散，不符合稀疏承诺。作者因此随机扰动 key，制造少量副本，并让某个近邻以较高概率从其他候选者中突出出来。任何能够捕获足够注意力的小集合，都必须包含这个 key，于是算法又会暴露一个近似最近邻。
这项结论区分了两件容易混淆的事：权重集中，是输出具有稀疏结构；快速找出权重集中在哪里，则是一项计算任务。前者本身不自动保证后者容易。
它为加速承诺划了什么线
这篇论文并没有说线性注意力或稀疏注意力“无效”。摘要和正文都明确承认，近似算法可以在实践中、典型输入上或具有特定结构的输入上表现良好。下界针对的是更强的组合承诺：真正次二次或次线性的速度，加上不依赖具体输入结构、覆盖所有输入的非平凡误差保证。
它真正改变的是评价问题。看到一种新的注意力加速方法时，不能只问“是不是更快”，还要问：保证适用于所有输入，还是依赖稀疏、低秩、小范数等结构？这是理论保证，还是经验测试？最坏情形、平均情形和实际数据分布不是同一件事。
论文还把可行与困难的边界描述为一次“尖锐转变”：在足够低的维度和足够小的 query、key 范数下，已有方法能以近线性时间取得随序列长度快速缩小的误差；参数稍微越过其研究的边界后，论文便排除了任何非平凡的一致近似。由于供稿中的公式有部分缺失，这里不转述具体维度、范数阈值和常数范围，以免把边界写错。
局限与未知
- 所有不可能性结论都依赖 SETH 等复杂性理论假设。论文没有给出无条件的二次下界，“settle the computational limits”也应理解为在这些假设和问题定义之内。
- 下界约束的是覆盖所有输入的一致保证。它不排除算法在现实数据、平均情形或满足额外结构假设的输入上获得显著加速，也不说明现有方法的实际质量一定不好。
- “非平凡保证”“显著注意力”“高效”等词在定理中有精确定义和参数限制。供稿文本的部分数学符号未完整呈现，因此本文只说明结论结构，不补写缺失的阈值。
说白了，这项工作不是宣布“快注意力不可能”，而是指出：一种既普遍、又有保证、还从根本上更快的注意力算法，可能不存在。想跑得快，算法多半必须利用真实输入的某种结构。接下来的关键，不只是提出更多加速技巧，而是把这些技巧依赖什么条件、何时会失效，说得同速度数字一样清楚。